Adaptively Generating Heterogeneous Execution Strategies using the VOILA Framework

For decades, computers have been used for analyzing data, more recently (still decades ago) via database management systems (DBMS). DBMS are systems that facilitate data storage, modification and analysis, and on top of that, provide certain guarantees. With huge, and often increasing, data volumes, the efficiency of data analysis becomes increasingly important.

Commonly, queries are formulated in some high-level language (typically SQL) for which the DBMS has to find an "optimal" implementation in a lower-level language (which is afterward either interpreted or directly executed). This, typically, means restricting possible choices, which DBMS traditionally do by either fixing certain choices (like e.g. query execution technique/paradigm) or finding a cost-based optimum (for algorithms, ordering, etc.). The generated implementation (flavor) is rather oblivious to the data set (except for possibly relying on optimizer statistics) and environment (hardware, operating system ...), and is, therefore, likely not optimal on the data set and environment "at hand". With more knowledge of the current instance (data set, query, and environment), more efficient implementations, so-called instance-specific optimizations, should be possible.

This thesis investigates instance-specific optimizations and focuses on answering two questions: (1) How far can query plans be optimized to the specific instance and (2) how can query engines exploit increasingly heterogeneous modern hardware?

First, we explore the design space (of possible instance-specific optimizations) manually. We found certain techniques that can improve query performance: Thinner data types (Compact Data Types) can fit more data into SIMD registers which improves throughput for arithmetic operations and In-Register Aggregation is a special aggregation optimized for a group-bys with a low number of groups. Furthermore, it is possible to compress hash tables (assuming data distributions allow it) and optimistically compress strings using dictionaries. Both not only improve memory footprint but also runtime.

Second, we simplify the exploration of the design space by using a domain-specific language (VOILA) and synthesizing specific flavors from VOILA. We show that VOILA can not only generate state-of-the-art implementations (e.g. Vectorized and Data-centric Execution) with competitive performance, but also can generate variants as well as mixes thereof (across and within pipelines).

Third, we highlight that the optimal flavor depends on the environment and certain hardware choices can favor certain flavors. Therefore, more or less esoteric hardware choices can weaken/break rules of thumb (e.g. Vectorized Execution outperforms on join-heavy workloads). As the environment and hardware "at hand" are often not fully known ahead of time (i.e. when the DBMS is developed), neither is the optimal flavor. Therefore, more flexible and dynamic query execution is needed. One possible solution is adding another layer of abstraction, by using a virtual machine to execute queries.

Fourth, we propose such a virtual machine (Excalibur) that explores and exploits different instance-specific optimizations, while the query is running (on-the-fly). Possible flavors are explored automatically and good flavors are remembered, within and across similar queries. Excalibur demonstrates how a highly flexible and adaptive query engine could look like and how it can be integrated into a framework that uses Vectorized Execution.

In summary, this thesis explored the design space of instance-specific optimizations. We, first, explored the space manually and found points with improved performance. Afterward, we used a domain-specific language to simplify and automate the exploration process. Finally, we described a prototype that explores the space of possible optimizations, while the query is running.