Thomas Neumann

In distributed OLAP databases, assigning data and tasks to compute nodes is a non-trivial problem with large performance impact. Common strategies include simple round-robin schedulers or minimizing network transfers. However, in some cases these techniques cannot deliver optimal query latency. For example, in scale-out scenarios, existing techniques fail to balance the trade-off between utilization of new nodes and increased network cost from cold caches, leaving substantial room for improvement. Addressing these problems in existing systems is difficult, because schedulers are often tightly integrated and cannot be easily adapted for experiments. Evaluating a new scheduler in a system is equally difficult, requiring time-consuming and costly experiments for many scenarios. To tackle this problem, we formalize the distributed task scheduling problem (DTS). Further, we present DQSim, a fine-grained simulator for distributed query execution that estimates the execution time of DTS schedules. This allows us to accurately model the effects of new scheduling algorithms without having to rebuild large parts of a system. DQSim can run thousands of experiments with user-defined system and cluster configurations and queries in seconds to evaluate scheduling techniques quickly. Finally, we propose two new scheduling algorithms, NetHEFT and cCEFT, that yield good results across a wide range of scenarios. They are on par with round-robin and network-minimizing baselines on simple scenarios where no improvement is expected. In more challenging scenarios, they can reduce query latency by over 2x.

Database users frequently utilise string data types for general-purpose storage, even when more specialised alternatives are available [18]. Thus, modern analytical database systems rely on lightweight string compression schemes, such as Fast Static Symbol Table (FSST) [2] or OnPair [6], to reduce memory footprint. However, evaluating SQL LIKE predicates on compressed strings typically requires full decompression, negating the benefits of compression. We present an approach that reverses this paradigm: instead of decompressing data to match patterns, we compress the pattern by constructing finite automata that parse FSST-encoded symbol sequences directly. Our technique partitions LIKE patterns into prefixes, suffixes, and substrings, building specialised automata for each, while considering the properties of FSST. We provide interpreted and compiled implementations along with optimisations, including early rejection and SIMD-accelerated self-loop traversal. Evaluation on TPC-H, StackOverflow, and IMDB datasets demonstrates speedups of 2.5–17 × over decompression-based pattern matching, suggesting that co-designing compression schemes and query operators, already successful for integer data, represents a promising direction for string-dominated analytical workloads.

To efficiently manage larger-than-memory datasets, storage-based database management systems (DBMSs) rely on buffer managers. These are traditionally implemented using hash tables to translate page identifiers (PIDs) to memory pointers. While this design offers many practical advantages, prior studies have shown its performance limitations and proposed alternative designs to close the gap with optimized in-memory DBMSs. However, these modern designs introduce systematic issues, such as intrusive implementations or reliance on kernel modules, which ultimately hinder their adoption. This paper challenges the notion that hash-table-based buffer pools cannot deliver high performance. We introduce predictive translation , a novel approach that combines the high performance of modern approaches with the qualitative benefits of traditional designs. Predictive translation achieves this by exploiting the capabilities of commodity CPUs – particularly their superscalar execution – through deterministic placement of pages to hide the excessive latency of software-level hash table lookups. Our evaluation demonstrates that our approach meets all practical requirements while delivering performance at least on par with state-of-the-art alternatives. We show that our design is a compelling solution for buffer management in modern DBMSs running on fast storage devices.

Query performance prediction is used for scheduling, resource scaling, tenant placement, and various other use-cases. Here, the main goal is to estimate the execution time of a query without running it. To be effective, predictors need to be both accurate and fast. In contrast, neural networks that were used in recent work deliver very accurate predictions but suffer from high latency. In this work, we propose the Tuple Time Tree (T3), a new model that is both accurate and fast. It is orders of magnitude faster than comparable methods and has competitive accuracy to state-of-the-art approaches. Additionally, T3 works for new database instances without re-training because it generalizes across database instances. We achieve T3's speed by relying on a low-latency decision tree model that is compiled to native machine code. We maintain high accuracy with two novel techniques: pipeline-based query plan representation and tuple-centric prediction targets. In our pipeline-based query plan representation, T3 decomposes query plans into pipelines. Then, T3 predicts the execution time of each pipeline individually, instead of the whole query in one step. With tuple-centric prediction targets, T3 predicts the expected time it takes to push a single tuple through a pipeline. It then multiplies this predicted value by the input cardinality of the pipeline to estimate its execution time. As a result, T3 achieves state-of-the-art accuracy with a low-latency decision tree model.

Parquet is the most commonly used file format to store data in a columnar, binary structure. The format also supports storing nested data in this flattened columnar layout. However, many query engines either do not support nested data or process it with substantially worse performance than relational data. In this work, we close this gap and present a new way to leverage relational query engines for nested data that is stored in this flat columnar file format. Specifically, we demonstrate how to process nested Parquet files much more efficiently. Our approach does not store a copy of the data in an internal format but reads directly from the Parquet file. During query computation, the required flat columns are scanned independently and the nesting is reconstructed using joins with on-the-fly generated join keys. Our approach can be easily integrated into existing query engines to support querying nested Parquet files. Furthermore, we achieve orders of magnitude faster analytical query performance than existing solutions, which makes it a valuable addition.

In the past, the common assumption was that main memory would become cheap and abundant enough to power database systems solely. This assumption did not hold. This chapter presents approaches on how modern database systems can scale beyond a single server’s main memory capacity by utilizing trends in modern hardware without sacrificing performance. To this end, we present four systems: Mosaic, a storage engine for analytical workloads; Plush, a PMem-optimized storage structure for transactional workloads; PMFDS, a novel programming model for fully disaggregated systems; and finally, FireArm, a just-in-time compilation framework for rising ARM systems in the server space.

This paper aims to bridge the gap between fast in-memory query engines and slow but robust engines that can utilize external storage. We find that current systems have to choose between fast in-memory operators and slower out-of-memory operators. We present a solution that leverages two independent but complementary techniques: First, we propose adaptive materialization, which can turn any hash-based in-memory operator into an out-of-memory operator without reducing in-memory performance. Second, we introduce self-regulating compression, which optimizes the throughput of spilling operators based on the current workload and available hardware. We evaluate these techniques using the prototype query engine Spilly, which matches the performance of state-of-the-art in-memory systems, but also efficiently executes large out-of-memory workloads by spilling to NVMe arrays.

When writing SQL queries, it is often convenient to use correlated subqueries. However, for the database engine, these correlated queries are very difficult to evaluate efficiently. The query optimizer will therefore try to eliminate the correlations, a process referred to as unnesting. Recent work has introduced a single pass top-down algorithm for unnesting arbitrary SQL queries. That work did not include a formal proof of correctness, though. In this work we provide the missing formalization by formally defining the operator semantics and proving that the unnesting algorithm is correct.