Paper notes - Efficiently Compiling Efficient Query Plans for Modern Hardware

(personal summary based on the paper)

A common approach to executing queries in database systems is the classical iterator model introduced in the Volcano paper. This model is simple and flexible, and operates by having each plan node implement a next() method that returns one tuple at a time when called repeatedly.

However, this model incurs performance overhead due to the large number of virtual function calls (next()), which often rely on function pointers or interface dispatching. These calls can become expensive when executed millions of times.

To address this, some systems reduce the overhead by passing batches of tuples instead of single tuples between operators, enabling vectorized execution and reducing call frequency.

The paper introduces a query compilation technique that translates SQL queries into efficient machine code using the LLVM compiler framework. Instead of pulling tuples via next() calls, the execution model pushes data from producers to consumers. This allows data to remain in CPU registers and minimizes the overhead of memory loads and function calls. LLVM’s intermediate representation supports an unbounded number of virtual registers, hiding the complexity of actual register allocation.

The core strategies of the compilation model are:

- Data locality: Process data in a way that it stays in CPU registers as
  long as possible.
- Push-based execution: Push data down the pipeline instead of pulling it,
  improving code locality and reducing branching.
- LLVM-based compilation: Compile the query plan into native machine code
  for optimal performance.

Compiling Expressions

SQL query compilation begins as in traditional systems: the query is parsed, converted into a logical plan, and optimized. The key difference is that, instead of generating a physical execution plan, the system compiles the query into an imperative program using LLVM IR.

Most of the database infrastructure—such as index structures—is still implemented in C++. The compiled LLVM code calls into these C++ routines, and vice versa, leading to mixed-mode execution where performance-critical logic is handled by generated code, while complex data structures remain in C++.

Large and complex queries can generate sizable machine code. To manage this, the system avoids generating everything in one monolithic function and instead breaks the compiled logic into modular, reusable fragments. The compilation process also attempts to minimize conditional branches, producing branch-predictable code, which, for example, improved hash lookup performance by over 20%.

Conclusion

The paper shows a technique to compile query plans into efficient machine code using LLVM. It's a very interesting approach that compiles the entire query plan, rather than just the expression evaluation like PostgreSQL does.

Comments

Post a Comment

Popular posts from this blog

Hacking PostgreSQL - How SQL is compiled using LLVM?

A few days ago, @eatonphil organized a Postgres Internals wehack group on Discord for people interested in understanding and contributing to the PostgreSQL source code. I had previously tried to understand more about how SQL expressions are compiled using LLVM but without much success, with this encouragement I decided to go deeper and understand how PostgreSQL compiles SQL code, and here I will describe my understanding notes. Please let me know if something is not right, I'm just a curious guy trying to understand Postgres source code. How Postgres decide if a SQL should be compiled or not? Postgres decide if a SQL expression should be compiled or not based on the cost of the query, if the estimated cost of the query is less than the setting jit_above_cost , then the query will be compiled using LLVM. Lets see a practical example (make sure that the jit is enabled): set jit_above_cost = 200 ; create table t (a int , b int ); insert into...
Read more

Paper notes - Exploiting Cloud Object Storage for High-Performance Analytics

(personal summary based on the paper) The paper presents the AnyBlob; A cloud based object store download manager based on io-uring for query engines that optimizes throughput while minimizing CPU usage. Due the recently improvements on network bandwidth on cloud providers it is more viable to use remote storages for high-performance query analytics. In 2018 AWS introduce instances with 100 Gbit/s networking, which improves severely the latency and close the gap between local file systems and remote storages. Previously researches focus mostly on OLTP databases and using cache to avoid fetch data from remote storage, Anyblob on the other hand demonstrate that even without caching it achieves similar performance to state-of-the-art cloud data warehouses that cache data on local SSDs while improving resource elasticity. Anyblob use io_uring to manage multiple object store downloads per thread asynchronously. With this model, the system does not have to spawn too many threads to downl...
Read more

Using git worktree to work with different PostgreSQL patches

PostgreSQL send patches over the email for contribution and code reviewing and some times organizing multiple patch versions of different works can be confusing. In this post, I’ll share how I use git worktree to organize the development and reviewing of different PostgreSQL patches. git worktree The git worktree command allows you to organize multiple working directories associated with a single Git repository. This is extremely useful when you need to check out different branches simultaneously without the overhead of cloning the repository multiple times. Each worktree acts as an independent checkout, sharing the same .git directory and object database. Untracked files in one worktree don’t exist in others. That isolation becomes really useful during development and review workflows. If you work on multiple patches at the same time—or if you frequently review patch series—it’s common to accumulate different versions of the same patch. For example, after working on the extensio...
Read more