Elf meets MonetDB

The emergence of main-memory DBMS brought about the need of cache-conscious structures and algorithms. For the workload of OLAP scenarios, column stores like MonetDB have a favourable memory layout, allowing sequential scans over contiguous memory. When facing selection predicates for multiple columns, however, they offer little to accelerate them. Multi-dimensional index structures such as kd-trees attempt to improve on plain scans, but face the curse of dimensionality when many columns are queried. In this work, we integrate the multi-dimensional main-memory index structure Elf, which does not suffer from said curse, into the DBMS MonetDB. Since Elf only supports select queries, we provide interoperability with MonetDB's query engine and show various improvements of the naive approach. To enable real-world use, we propose two competing approaches of querying string-typed columns with Elf. As modern CPUs feature lengthy pipelines and out-of-order execution, we also explore the possible trade-off between branching complexity and early termination for Elf traversal.

Autorentext

Bachelor in Computer Science, Master in Data and Knowledge Engineering. Researcher in Computer Graphics at the Technical University of Clausthal.