PaperlayerView exact revision on arXiv

Source-linked AI summary

Building Efficient Query Engines in a High-Level Language

Amir Shaikhha, Yannis Klonatos, Christoph Koch

arXiv:1612.05566v1cs.DB

TL;DR

Existing database systems often trade high-level-language productivity for performance, motivating the search for abstraction without regret. The paper presents LegoBase, which uses Scala-based generative programming and whole-system source-to-source compilation to specialized C. In TPC-H evaluation, the approach is competitive with established systems while requiring only a few hundred lines for optimizations and incurring negligible compilation overhead.

  • Problem

    Database systems remain difficult to develop and maintain because high-level languages can impose abstraction overhead, while low-level implementations sacrifice productivity for performance.

  • Method

    LegoBase uses generative programming to compile the entire Scala query engine, including its data structures, into specialized low-level C, with SC exposing high-level optimization abstractions.

  • Results

    TPC-H evaluation shows LegoBase is competitive with a commercial in-memory database and HyPer-generated code, while optimizations require only a few hundred lines and compilation overhead is negligible relative to query execution.

  • Takeaways & Limitations

    Whole-system generative compilation supports high-level, composable database optimizations while preserving competitive execution performance.

  • Takeaways & Limitations

    String dictionaries increase query loading time and memory use, and may increase memory pressure depending on the use case and data characteristics.

Abstract

from arXiv · show

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.

1. INTRODUCTION

The paper pursues abstraction without regret for analytical query processing: LegoBase uses high-level Scala abstractions while recovering efficiency through whole-system generative compilation. Its SC compiler and optimization interfaces aim to make extensive query-engine optimization productive, composable, and competitive with existing systems.

  • Motivation: High-level languages improve productivity and abstraction but can impose performance costs through indirection, object creation, and memory allocation.These costs motivate the paper’s abstraction-without-regret goal.
  • Contribution: LegoBase is an in-memory query execution engine written in Scala for ad-hoc analytical query processing.It is presented as a step toward a full DBMS written in a high-level language.
  • Method: Generative programming source-to-source compiles high-level Scala into specialized low-level C while optimizing the entire query engine, including its data structures and auxiliary functions.Whole-system specialization addresses overheads that query-only compilers leave in precompiled database components.
  • Compiler design: SC gives developers control over optimization phases and high-level abstractions without exposing compiler internals, addressing phase-ordering and debugging complexity.The compiler supports custom phase orderings while keeping optimizations expressed in plain Scala.
  • Compiler design: LegoBase optimizations are separated into library components and can be adjusted, configured, and composed across distinct optimization phases.The design separates optimizations from base query-engine code and from one another.
  • Evaluation: TPC-H experiments show performance competitive with a commercial in-memory database and HyPer-generated code, while complicated optimizations require only a few hundred lines and compilation adds negligible query-execution overhead.The evaluation also compares architectural decisions using a shared codebase and examines individual optimization trade-offs.

2. SYSTEM DESIGN

LegoBase compiles an entire high-level Scala query engine, rather than only individual queries or operators, into specialized C code through SC. SC exposes high-level transformation APIs and staged pipelines so database-specific optimizations remain configurable, composable, and separate from compiler internals.

  • System architecture: The system obtains a physical plan, instantiates corresponding Scala operators, and compiles the resulting operator tree before returning query results.Traditional query optimization is treated as an orthogonal step before LegoBase receives the physical plan.
  • System architecture: LegoBase converts the entire Scala query engine, including operators, data structures, and auxiliary functions, into specialized C code for each query.SC uses query-specific information and progressively applies domain-specific optimizations during compilation.
  • The SC compiler framework: SC provides high-level analyze and rewrite primitives for expressing program transformations without exposing its internal intermediate representation.Transformations are specified as compiler-agnostic Scala programs rather than low-level IR operations.
  • Efficiently compiling high-level query engines: The approach separates optimizations from base query-engine code and from one another while supporting a wide range of database-specific transformations.The optimizations are implemented as library components and can be adjusted, enabled or disabled, and composed.
  • The SC compiler framework: Developers explicitly compose black-box transformers into configurable pipelines, allowing optimization phases and their orderings to vary with queries, workloads, or architectures.The pipeline can enable partitioning, data-layout changes, and other transformations independently.
  • Efficiently compiling high-level query engines: Progressive lowering maps Scala abstractions to progressively lower-level representations, eventually producing C constructs such as structs, arrays, loops, and variables.Objects, classes, inheritance, and hash maps can be optimized away before final code generation.
  • Efficiently compiling high-level query engines: Source-to-source compilation must explicitly manage memory because Scala uses garbage collection whereas generated C requires explicit allocation and deallocation.For this work, allocations and deallocations are made explicit in Scala code, and allocated memory is freed after each query.

3. COMPILER OPTIMIZATIONS

LegoBase expresses a broad range of query-engine optimizations as high-level Scala transformations, including cross-operator rewrites that remove redundant materializations. These optimizations preserve high-level development while later compiler stages handle low-level code generation.

  • LegoBase demonstrates optimizations for query plans, data structures, data layout, strings, code motion, and dead code elimination.
  • Inter-Operator Optimizations: Existing query compilers can introduce redundant computation because operators are unaware of each other and materialize intermediate results separately.
  • Inter-Operator Optimizations: LegoBase matches chains of Scala operator objects and can merge an aggregate with a join, eliminating a distinct materialization point.
  • Inter-Operator Optimizations: The inter-operator optimization is written as ordinary Scala code at the same abstraction level as the query engine, avoiding duplicated development code and explicit code-generation concerns.

3.2. Data-Structure Specialization

LegoBase specializes data structures using schema, query, and workload information, especially for joins and intermediate computations. These transformations replace generic structures and avoid tuple-copying and allocation overhead while preserving high-level operator code.

  • Data-structure specialization targets input-relation storage, hash maps, and inferred date indices to improve execution efficiency.
  • Data Partitioning: LegoBase annotates primary and foreign keys, then constructs specialized structures that support faster matching-tuple extraction for primary-foreign-key joins.
  • Data Partitioning: Single-attribute primary keys can index tuples in one-dimensional arrays, while composite keys require alternative handling because individual attributes may conflict.
  • Data Partitioning: Foreign-key partitioning creates two-dimensional arrays whose buckets contain tuples sharing a foreign-key value, with loaded partitions selected from the physical query plan and statistics.
  • Data Partitioning: Multi-way joins can eliminate intermediate data structures and tuple copying, reducing memory pressure, improving cache locality, and avoiding related system calls.
  • Hash-Map Specialization: Generic hash maps incur allocation, hashing, comparison, and often virtual-call overhead, which LegoBase resolves through compiler specialization without changing operator code.

3.3. Changing Data Layout

LegoBase changes row-oriented storage to a column-oriented representation as an optimization rather than redesigning the query engine. Type-directed rewriting and dead code elimination remove the associated abstraction overhead, although this does not make the system a complete column store.

  • The row-versus-column choice is expressed as an optimization, avoiding a complete query-engine redesign when columnar processing is beneficial.
  • Changing Data Layout: The transformation converts an array of records into a record of arrays, applying only when the array elements have record type.
  • Changing Data Layout: Operations on the column layout rewrite updates into operations on the underlying attribute arrays.
  • Changing Data Layout: Dead code elimination can remove intermediate record reconstructions and unused attributes introduced by the column-layout transformation.
  • Scope: Changing the data layout does not by itself make LegoBase a column store because other aspects of column-store systems remain unhandled.
  • Changing Data Layout: The data-layout transformation is isolated in an array-specific optimization phase rather than depending on other optimizations or query-engine code.

3.4. String Dictionaries

LegoBase replaces string values with integer dictionary codes to reduce the overhead of string operations. Specialized ordered and word-tokenizing dictionaries support ordering and substring-like workloads, but dictionary construction can substantially hurt loading performance.

  • String operations on non-primitive values incur function-call, looping, branch-prediction, and cache-locality overhead.
  • Dictionary Encoding: String dictionaries map each attribute’s string values to integer codes associated with its distinct values.
  • Ordered Dictionaries: Ordered dictionaries preserve lexicographic order so ordering-dependent string operations can be lowered to integer operations and ranges.
  • Word Tokenization: Word-tokenizing dictionaries represent words rather than whole strings for word-slice searches such as Q13’s indexOfSlice operation.
  • Word Tokenization: The integer loop used for word-slice matching can outperform C-library strstr because it may be easier for the C compiler to vectorize.
  • Costs and Limitations: String dictionaries improve query execution but can substantially degrade data loading, especially for word tokenization, primary keys, or high-cardinality attributes.

3.5. Domain-Specific Code Motion

Domain-specific code motion shifts selected initialization and allocation work from query execution to data loading, reducing critical-path overhead while accepting higher loading cost or constrained applicability.

  • Domain-Specific Code Motion: Domain-specific code motion moves performance-costly logic from query execution into data loading, trading increased loading time for faster queries.The category targets code segments on the execution critical path.
  • Allocation Removal: Type information gathered during query compilation lets LegoBase replace runtime allocations with references to specialized memory pools.The compiler analyzes lowered C code because Scala’s implicit memory management is not currently optimized by SC.
  • Allocation Removal: Contiguous memory pools reduce executed instructions and improve cache locality, while composite-type dependencies are resolved through topological sorting.Pool sizing uses worst-case analysis and may overallocate, although the reported estimates avoid unnecessary memory pressure.
  • Data-Structure Initialization: LegoBase removes data-structure initialization from the critical path by inferring aggregation-key domains from statistics collected during data loading.Aggregations can generally be initialized statically with zero for each inferred key.
  • Data-Structure Initialization: The initialization optimization is not fully general because it depends on predicting key values, with TPC-H Q18 requiring a specialized structure for sparse O_ORDERKEY values.Within the TPC-H workload, the approach removes initialization overhead and associated unnecessary computation across the queries described.

3.6. Traditional Compiler Optimizations

LegoBase combines traditional, fine-grained, and data-access compiler optimizations to reduce unnecessary code, memory accesses, branches, and critical-path work under query-specific conditions.

  • Generic Optimizations: The SC compiler provides generic optimizations such as dead-code elimination, common-subexpression elimination, partial evaluation, and scalar replacement.These optimizations are TPC-H compliant and do not require domain-specific knowledge.
  • Data Access and Code Shape: Query analysis removes unreferenced relational attributes before loading, while parameter promotion flattens eligible struct fields into local variables.These transformations reduce loaded data and remove an indirect memory access from the execution path.
  • Data Access and Code Shape: Scalar replacement is also known as parameter promotion in the programming-language literature.The optimization removes structs whose fields can be represented as local variables.
  • Fine-Grained Optimizations: Fine-grained optimizations transform eligible arrays, boolean conditions, and compile-time-known loop ranges into more efficient representations.Array lowering requires static size and indices; boolean rewriting requires side-effect-free operands.
  • Fine-Grained Optimizations: Fine-grained optimizations can be implemented in under a hundred lines and improve selected queries without adding performance overhead.Their benefits depend on the characteristics of the input query.

3.7. Discussion

LegoBase organizes its optimizations by generality and TPC-H compliance, spanning generic compiler techniques, data-access improvements, query-specific transformations, and domain-dependent partitioning or indexing.

  • Classification: LegoBase classifies optimizations using generality and TPC-H compliance, producing six groups ordered across Figure 15.These dimensions indicate which database systems can benefit from each category.
  • Generic Compiler Optimizations: Generic compiler optimizations are TPC-H compliant and applicable to any input query without domain-specific knowledge.Examples include dead-code elimination, common-subexpression elimination, partial evaluation, and scalar replacement.
  • Fine-Grained Optimizations: Fine-grained optimizations target individual statements, but their benefit depends on analyzing the input query before application.They are also TPC-H compliant.
  • Optimizing Data Accesses: Data-access optimizations improve function calls, memory access, and code compactness while remaining TPC-H compliant and independent of query-specific type information.They are coarse-grained despite affecting large code segments.
  • Partitioning and Indexing Optimizations: Partitioning and indexing can significantly improve execution but are not TPC-H compliant, making them most suitable for known data or precomputed indexing views.Their transformations require data replication or advance knowledge of aggregation-key domains.
  • Query-Specific Optimizations: Inter-operator, string-dictionary, and domain-specific hoisting optimizations remove materialization or computation from the critical path but require a known query and type information.Struct field removal is more aggressive, query specific, type dependent, and not TPC-H compliant.

4. EVALUATION

LegoBase’s evaluation shows that whole-engine specialization and Scala-to-C compilation deliver strong analytical-query performance, while individual optimizations contribute unevenly and can introduce costs. Across TPC-H, the system outperforms alternative approaches and exposes optimization opportunities that query-only or general-purpose compilers miss.

  • Comparison with query compilation: A 1.06× performance difference separates LegoBase(StrDict/C) from HyPer after adding string dictionaries.The TPC-H-compliant LegoBase(TPC-H/C) configuration is 4.4x DBX execution time, whereas HyPer improves performance by 6.4× over DBX.
  • Overall performance: 45.4× performance improvement over DBX is achieved by LegoBase with all optimizations enabled.Query-specific attribute removal, computation hoisting, and multi-attribute repartitioning improve memory behavior and join processing.
  • Scala-to-C compilation: 10× slower execution remains for optimized Scala code compared with optimized C code.Optimized Scala is 40.3× faster than naive Scala, but profiling attributes the remaining gap to more branch mispredictions, LLC misses, and 6.2× more CPU instructions.
  • Individual optimizations: 30× average performance improvement comes from data-structure specialization, with at least 22× speedups for several join-intensive queries.The benefit is not directly dependent on the number of joins or input relations; single-join queries can benefit similarly.
  • Individual optimizations: 1.06× to 5.5× speedups result from string dictionaries, averaging 2.41× for TPC-H queries with expensive string operations.The optimization’s benefit depends on query characteristics, especially where string operations occur.
  • Optimization costs: String dictionaries increase query loading time and require additional memory for a string-to-integer dictionary.Their use can increase memory pressure and potentially reduce performance depending on data characteristics.

5. RELATED WORK

Related work spans query compilation, intra-operator specialization, broader query-processing techniques, and domain-specific compilation. LegoBase instead advocates expressing the entire query engine and its optimizations in a high-level language, addressing maintainability and optimization scope.

  • Previous Compilation Approaches: Existing query-compilation systems reduce abstraction overhead but commonly retain precompiled database components or target only query operators.This limits whole-system and cross-operator optimization opportunities.
  • Previous Compilation Approaches: Template-based query-compilation approaches require low-level code that is hard to maintain and extend.LegoBase addresses this limitation by expressing query engines and optimizations in a high-level language.
  • Frameworks for Applying Intra-Operator Optimizations: Micro-Specialization supports systematic intra-operator optimization, but its low-level development process can take days for a single optimization.The cited comparison presents LegoBase as enabling coarser-grained optimizations with less development effort.
  • Techniques to Speed Up Query Processing: Broader query-processing research includes block-wise processing, vectorized execution, compression, and column-oriented layouts.These techniques improve how data is processed rather than focusing only on individual operators.
  • Domain-Specific Compilation: Domain-specific compilation restricts the language or domain so program analysis can enable more powerful global transformations than general-purpose compilers.LegoBase builds on this direction for query-engine optimization.
  • Previous Realization of Abstraction Without Regret: This article presents a from-scratch realization using the SC optimizing compiler, with a more detailed analysis and broader optimization coverage than the earlier realization.The comparison concerns a new compiler and a significantly more thorough set of supported optimizations.

6. CONCLUSIONS

The conclusion presents LegoBase as a high-level Scala query-execution system that uses generative programming to compile the entire engine into efficient C. Experiments report significant performance gains with only a few hundred lines of high-level optimization code.

  • 6. CONCLUSIONS: LegoBase uses source-to-source compilation to translate high-level Scala query-engine code into efficient low-level C code.Generative programming is the mechanism used to combine productivity with execution efficiency.
  • 6. CONCLUSIONS: Database-specific optimizations can be expressed at a high level as a library and applied across the entire query engine.The conclusion contrasts this scope with existing compilers that handle only queries.
  • 6. CONCLUSIONS: Programmers need only a few hundred lines of high-level code to implement optimizations that produce significant performance improvement.The paper presents this as difficult to achieve with template-based approaches requiring low-level code.
  • 6. CONCLUSIONS: Experiments show that LegoBase significantly outperforms both a commercial in-memory database system and an existing query compiler.This is the paper’s reported comparative evaluation outcome.

A. ABSOLUTE EXECUTION TIMES

The appendix lists absolute performance and resource measurements for evaluated systems and LegoBase configurations. The supplied appendix passages identify execution-time, memory, loading-time, and compilation-time materials but provide no numerical entries.

  • A. ABSOLUTE EXECUTION TIMES: Absolute performance results are presented for all evaluated systems and metrics.The supplied passage introduces these tables without reproducing their numerical values.
  • A. ABSOLUTE EXECUTION TIMES: Table V reports execution times in milliseconds for the configurations shown in Figures 16 and 17.The configurations are explained in Table III.
  • A. ABSOLUTE EXECUTION TIMES: Table VI reports TPC-H execution times in milliseconds as individual optimizations are cumulatively added.Each listed optimization is applied in addition to the configuration above it.
  • A. ABSOLUTE EXECUTION TIMES: Table VII covers memory consumption, input-data loading time, and optimization or compilation time.Its units are gigabytes, seconds, and milliseconds, respectively.

B. CODE SNIPPET FOR THE PARTITIONING TRANSFORMER

The partitioning transformer analyzes MultiMap usage and rewrites eligible joins to use partitioned arrays instead of generic map operations. The rules remove redundant operations, preserve join processing, and rely on later optimizations for cleanup.

  • Analysis Phase: The transformer identifies MultiMaps holding records and tracks their surrounding loops and partitioning metadata.The analysis records symbols, loop scope, binding loops, structures, and partitioning field names.
  • Rewriting Phase: For partitioned joins, the transformer removes MultiMap binding, lookup, and related-loop operations from the generated code.Dead-code elimination later removes the now-unused MultiMap itself.
  • Rewriting Phase: Eligible MultiMaps are replaced with corresponding one- or two-dimensional partitioned arrays constructed during data loading.The selected array shape depends on primary- and foreign-key properties.
  • Rewriting Phase: Join matching is rewritten to iterate over the bucket selected by the partitioning key and inline the join-condition and output logic.The original HashMap-based extraction is moved inside the loop over the right relation.
  • Rewriting Phase: The transformer converts MultiMap operations to native Array operations as part of the partitioning and indexing transformation.A later optimization can flatten the resulting loop, while another removes the constant emptiness check.
Loading 1612.05566v1…