# Building Efficient Query Engines in a High-Level Language

arXiv: https://arxiv.org/abs/1612.05566 · HTML: https://mlsanity.com/paper/1612.05566/

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 16 Dec 2016.

## Built on by (most cited first, 6 of 6)

- [GeCo: Quality Counterfactual Explanations in Real Time](https://mlsanity.com/paper/2101.01292/) (2021)
- [Functional Collection Programming with Semi-Ring Dictionaries](https://mlsanity.com/paper/2103.06376/) (2021)
- [GenDB: The Next Generation of Query Processing -- Synthesized, Not Engineered](https://mlsanity.com/paper/2603.02081/) (2026)
- [Demonstrating GenDB: Instance-Optimized and Customized Query Processing Code Generation via LLM Agents](https://mlsanity.com/paper/2607.20630/) (2026)
- [Fine-Tuning Data Structures for Analytical Query Processing](https://mlsanity.com/paper/2112.13099/) (2021)
- [A Methodology and Software Architecture to Support Explainability-by-Design](https://mlsanity.com/paper/2206.06251/) (2022)

## Abstract (arXiv)

Abstraction without regret refers to the vision of using high-level programming languages for systems development without experiencing a negative impact on performance. A database system designed according to this vision offers both increased productivity and high performance, instead of sacrificing the former for the latter as is the case with existing, monolithic implementations that are hard to maintain and extend. In this article, we realize this vision in the domain of analytical query processing. We present LegoBase, a query engine written in the high-level language Scala. The key technique to regain efficiency is to apply generative programming: LegoBase performs source-to-source compilation and optimizes the entire query engine by converting the high-level Scala code to specialized, low-level C code. We show how generative programming allows to easily implement a wide spectrum of optimizations, such as introducing data partitioning or switching from a row to a column data layout, which are difficult to achieve with existing low-level query compilers that handle only queries. We demonstrate that sufficiently powerful abstractions are essential for dealing with the complexity of the optimization effort, shielding developers from compiler internals and decoupling individual optimizations from each other. We evaluate our approach with the TPC-H benchmark and show that: (a) With all optimizations enabled, LegoBase significantly outperforms a commercial database and an existing query compiler. (b) Programmers need to provide just a few hundred lines of high-level code for implementing the optimizations, instead of complicated low-level code that is required by existing query compilation approaches. (c) The compilation overhead is low compared to the overall execution time, thus making our approach usable in practice for compiling query engines.