Column-oriented GPU-accelerated Database Management System
CoGaDB
|
In this section, we describe important concepts and design decisions in CoGaDB. We start with one of the most important building blocks of the query processor, the LookupTables. Then, we discuss the design and capabilities of CoGaDB'S optimizer, divided in the logical and physical optimizer.
A Lookup Table is a view on one or multiple tables. They are the bridge between the table-based operators and the internal column-based operators.
Internally, each operator returns the result as a list of TIDs. A LookupTable is basically a list of a pointer to a table, a pointer to a TID list, indicating which tuples of the underlying table belong to the Lookup Table, and a attribute list, specifying which columns of the table are included in the LookupTable. Therefore, LookupTables are a cheap mechanism to store intermediate results. Furthermore, they behave as they were "normal" tables, with the exception that LookupTables cannot be updated. Columns of LookupTables are LookupArrays, which consist of a pointer to a materialized column from a materialized table and a pointer to a TID list. To keep track of which LookupArray indexes a column from which table, we use a helper data structure called LookupColumn. A LookupColumn describes which part of one materialized table is part of a LookupTable, which can be the result of an arbitrary sequence of operators, including binary operators such as joins.
CoGaDB implements a simple logical optimizer. It basically implements two of the most basic optimizations: push down selections and resolve cross products by merging them with join conditions to natural joins. To achieve this, CoGaDB has currently four optimizer rules:
The core of CoGaDB's physical optimization is the HyPE Library, which is our Hybrid Query Processing Engine. It allocates for each operator in a query plan a processing device and decides on the most suitable algorithm on the selected processing device. Thus, HyPE takes care of the complete physical optimization in CoGaDB.