Otto-von-Guericke-Universität Magdeburg

 
 
 
 
 
 
 
 

The Elf Approach

News

Our paper "Accelerating multi-column selection predicates in main-memory – the Elf approach" has been accepted for publication and presentation at the ICDE 2017 in San Diego, California.

Description

Evaluating selection predicates is a data-intensive task that reduces intermediate results, which will be the input for further operations such as joins. With analytical queries getting more and more complex, the number of evaluated selection predicates per query rises as well. This leads to numerous multi-column selection predicates. Recent approaches to increase the performance of main-memory databases for selection-predicate evaluation aim at optimally exploiting the speed of the CPU by using accelerated scans. However, scanning each column one by one leaves tuning opportunities open that arise if all predicates are considered together. To this end, we introduce Elf, a storage structure that is able to exploit the relation between several selection predicates. Our Elf features cache sensitivity, an optimized storage layout, fixed search paths, and slight data compression. In our evaluation, we compare its query performance to two state-of-the-art approaches and a sequential scan using the concept of single instruction multiple data (SIMD). Our results indicate a clear superiority of our approach. For TPC-H queries with multi-column selection predicates, we achieve a speed-up between factor five and two orders of magnitude, mainly depending on the selectivity of the predicates. 

Elf_Website  

Persons

David Broneske (University of Magdeburg)
Veit Köppen (University of Magdeburg)
Gunter Saake (University of Magdeburg)
Martin Schäler (Karlsruhe Institute of Technology)

 

Materials

The source code for the ICDE 2017 Paper is available at: http://git.iti.cs.ovgu.de/dbronesk/ICDE-elf

Required Libraries: Boost, CMake 

Test data can be found in the source code repository above in the folder OP (TPC-H with scale factor 1).

 

 

Paper

David Broneske, Veit Köppen, Gunter Saake, and Martin Schäler. Accelerating multi-column selection predicates in main-memory – the Elf approach. In IEEE International Conference on Data Engineering (ICDE), 2017.

 Veit Köppen, David Broneske, Gunter Saake, and Martin Schäler. Elf: A Main-Memory Structure for Efficient Multi-Dimensional Range and Partial Match Queries. Technical Report 002-2015, Otto-von-Guericke-University Magdeburg, Magdeburg, #dec# 2015.

Jonas Schneider. Analytic Performance Model of a Main-Memory Index Structure. In CoRR, arXiv.org, 2016.

Letzte Änderung: 13.03.2017 - Contact Person: Webmaster