Analytical query processing beyond main memory

The evolution of relational database management systems has been shaped by advancements in computing hardware. Early database systems were designed around the hardware constraints of their time, optimising for limited memory, slow storage, and single-threaded execution. As hardware has advanced, offering large memory capacities, high-speed storage, and massive parallelism, database systems have adapted to utilise these resources. However, when queries require more space for temporary data than fits in main memory, database systems often suffer sharp performance drops. Due to large differences between modern \emph{in-memory} query processing and traditional \emph{larger-than-memory} (also referred to as \emph{external}) query processing, execution times can increase by orders of magnitude when the memory limit is exceeded. This thesis aims to close this gap by designing query execution such that \emph{performance degrades gracefully}, rather than \emph{abruptly}, as the amount of temporary data exceeds the memory limit, but \emph{without sacrificing in-memory performance}. Database systems implement many query operators that use various algorithms and data structures. Due to the differences between operators, tackling external query execution as a whole is infeasible. Therefore, we approach this problem by addressing one operator at a time. Despite their differences, the operators we focus on have in common that they are \emph{blocking}, i.e., they must \emph{temporarily store intermediate relational data}. Therefore, we investigate how to store and manage these intermediates for efficient in-memory and external query processing, starting with the \emph{sort} and \emph{grouped aggregation} operators. Finally, we study the \emph{join} operator and how to manage the combined memory usage of multiple operators within a query plan. For the \emph{sort} operator, we research how \emph{data orientation} affects query performance. We build on prior work that showed that a row-oriented (as opposed to a column-oriented) data layout yields superior performance for grouped aggregation and joins. We demonstrate that the same holds for the sort operator. Then, we show that, with a minor modification that has a negligible impact on in-memory performance, the data stored in this row-oriented layout can be written to (and read from) storage \emph{without fully (de-)serialising} it. Avoiding serialisation overhead reduces the performance difference between in-memory and external query processing. For the \emph{grouped aggregation} operator, we research how to manage intermediate data. We identify shortcomings in traditional memory management and propose to use \emph{paged memory} to store intermediates, and unify the memory management of temporary and persistent data. Then, we propose a \emph{buffer page layout} for intermediates that builds on the previously proposed row-oriented data layout, improving it so that it can be written to storage \emph{without any additional serialisation costs}. We integrate the proposed techniques into the grouped aggregation operator and show that this enables larger-than-memory query processing with little additional operator complexity. \newpage For the \emph{join} operator, we research how to manage the memory of query plans. Unlike the sort and grouped aggregation operators, the join operator has two inputs, only one of which is \emph{blocking}; therefore, multiple operators can be active simultaneously. If multiple operators are active simultaneously, the memory of the \emph{entire query plan} must be managed, as the combined memory usage of the active operators cannot exceed the limit. We first integrate the previously proposed techniques for managing intermediate data into the join operator. Then, we propose a technique to dynamically assign memory to active join operators that maximises data throughput. We show that the proposed techniques allow for efficient external join processing, even in query plans with many joins. This thesis contributes to external query processing by allowing database systems to robustly process larger-than-memory intermediates without sacrificing in-memory performance. This increases the volume of data that can be efficiently processed on typical hardware.

• View at Publisher
• View at Worldcat

Free Full Text ( Final Version , 6mb )