---

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.

---

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

---