The Elf Approach

News

Visit our talk at HardBD-Workshop: "Selective Caching: A Persistent Memory Approach for Multi-Dimensional Index Structures" at ICDE 2020 in Dallas!
Our article " Efficient evaluation of multi-column selection predicates in main-memory" has been published under TKDE journal, 31(7):1296–1311, July 2019.

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).

Awards

Our Paper "Accelerating Multi-Column Selection Predicates in Main-Memory - The Elf Approach" has been awarded with the FIN Forschungspreis of the University of Magdeburg (PDF)

Publications

Muhammad Attahir Jibril, Philipp Götze, David Broneske, and Kai-Uwe Sattler. Selective Caching: A Persistent Memory Approach for Multi-Dimensional Index Structures. HardBD&Active'20@ICDE.

Since the proposal of Persistent Memory, researchhas focused on tuning a variety of data management problems tothe inherent properties of Persistent Memory – namely persistencebut also compromised read/write performance. These propertiesparticularly affect the performance of index structures, since theyare subject to frequent updates and queries. Nevertheless, themain research focuses on adapting B-Trees and its derivatives toPersistent Memory properties, aiming to reach DRAM processingspeed exploiting the persistence property of Persistent Memory.However, most of the found techniques for B-Trees are notdirectly applicable to other tree-based index structures or evenmulti-dimensional index structures.To exploit Persistent Memory properties for arbitrary indexstructures, we proposeselective caching. It bases on a mixtureof dynamic and static caching of tree nodes in DRAM to reachnear-DRAM access speeds for index structures. In this paper,we investigate the opportunities as well as limitations of selectivecaching on the OLAP-optimized main-memory index structureElf. Our experiments show that selective caching is keeping upwith pure DRAM storage of Elf while guaranteeing persistence.

David Broneske. Accelerating mono and multi-column selection predicates in modern main-memory database systems. PhD thesis, University of Magdeburg, May 2019.

Ever-since, database system engineers are striving for peak performance of their database operators. However, this goal is a major endeavor since database operators are influenced not only by the hardware (i.e., the executing processor or the memory hierarchy), but also by the workload (i.e., data distribution, selectivity, etc.). Especially in today’s world of main-memory database systems, there are new processing capabilities (e.g., advanced vector instructions such as AVX-512), new storage devices (e.g., Intel Optane as non-volatile RAM), or new diverse applications for data management (e.g., in-database machine learning) frequently introduced that become essential impact factors. Hence, a once optimal operator has to be frequently adapted with these new arising hardware and workloads.

A typical database operator that is frequently tuned by researchers is the selection operator, because selections are essential to reduce the load of subsequent operators and are usually one of the first operators that are executed in a query plan. Hence, a selection is working on the full amount of data – a fact that emphasizes the importance of tuning this data-intensive operator to avoid a serious bottleneck.

Although the selection operator is frequently tuned for arbitrary use cases mentioned above, there is no comprehensive and holistic way to tune this operator automatically. Furthermore, considering multiple selections on the same table, straight-forward implementations use candidate scans for several selection predicates. However, exploiting the interdependence and, hence, high selectivity is not investigated so far. In this thesis, we tackle the aforementioned challenges of (1) creating hardware-sensitive operator implementations automatically and (2) exploiting the relation between multiple selection predicates.

For solving the first challenge, we investigate the commonalities of different optimizations for arbitrary hardware and workloads on the example of the selection operator. As a result, we introduce the abstraction of code optimizations as a means to generate hardware-sensitive code variants automatically. The solution is completed by the concept of a tuning framework for operators in main-memory database systems.

As a solution for the second challenge, we propose to revive multi-dimensional index structures as a means to exploit the relation between selection predicates on several columns in main-memory database management systems. In order to allow for hardware-sensitivity – especially cache consciousness – we propose our main-memory index structure Elf. Elf is a tree structure combining prefix-redundancy elimination with an optimized memory layout explicitly designed for efficient main-memory access. Our experiments show that Elf is able to outperform several highly-potent baselines (including generated hardware-sensitive scans and state-of-the-art multi-dimensional index structures) by several orders of magnitude for reasonable selection predicates and queries from the standard OLAP benchmark TPC-H. However, our evaluation also identifies that an integration into the query engine of the main-memory database system MonetDB does not only show strengths but also limitations that any sort-based index structure is faced with.

Overall, the resulting approaches can be used in future query engines to form a Swiss army knife for arbitrary selection predicates. Hence, our contribution enriches a query engine far beyond current state-of-the-art-approaches by allowing for efficient execution of a single predicate (i.e., mono-column selection predicates) at bare-metal speed as well as exploiting the combined selectivity of several predicates (i.e., multi-column selection predicates).

David Broneske, Veit Köppen, Gunter Saake, and Martin Schäler. Efficient evaluation of multi-column selection predicates in main-memory. Transactions on Knowledge and Data Engineering, 31(7):1296–1311, July 2019.

Efficient evaluation of selection predicates is a performance-critical task, for instance to reduce intermediate result sizes being the input for further operations. With analytical queries getting more and more complex, the number of evaluated selection predicates per query and table rises, too. 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, an index structure that is able to exploit the relation between several selection predicates. Elf features cache sensitivity, an optimized storage layout, fixed search paths, and slight data compression. In a large-scale evaluation, we compare its query performance to state-of-the-art approaches and a sequential scan using SIMD capabilities. Our results indicate a clear superiority of our approach for queries returning less than 10% of all tuples – a selectivity almost one order of magnitude larger than observed for related indexing approaches. For TPC-H queries with multi-column selection predicates, we achieve a speedup between factor five and two orders of magnitude, mainly depending on the selectivity of the predicates. Further scaling experiments reveal that for large data sets, these speedup factors are expected to increase, due to more densely populated data spaces. Finally, our results indicate that using a delta-store like concept to support periodic insertions results in virtually no performance penalty for reasonable sizes of a write-optimized Elf as delta store.

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), pages 647 – 658, 2017. (PDF)

Evaluating selection predicates is a data-intensive task that reduces intermediate results, which are the input for further operations. With analytical queries getting more and more complex, the number of evaluated selection predicates per query and table rises, too. 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, an index structure that is able to exploit the relation between several selection predicates. Elf features cache sensitivity, an optimized storage layout, fixed search paths, and slight data compression. In our evaluation, we compare its query performance to state-of-the-art approaches and a sequential scan using SIMD capabilities. Our results indicate a clear superiority of our approach for multi-column selection predicate queries with a low combined selectivity. For TPC-H queries with multi-column selection predicates, we achieve a speed-up between a factor of five and two orders of magnitude, mainly depending on the selectivity of the predicates.

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, 2015.

Efficient evaluation of selection predicates (e.g., range predicates) defined on multiple columns of the same table is a difficult, but nevertheless important task. Especially for subsequent join processing or aggregation, we need to reduce the amount of tuples to be processed. As we have seen an enormous increase of data with the last decade, this kind of selection predicate became more important. Especially in OLAP scenarios or scientific data management tasks, we often face multi-dimensional data sets that need to be filtered based on several dimensions. So far, the state-of-the-art solution strategy is to apply highly optimized sequential scans. However, the intermediate results are often large, while the final query result often only contains a small fraction of the data set. This is due to the combined selectivity of all predicates. In this report, we propose Elf - a new tree-based approach to efficiently support such queries.

In contrast, to other tree-based approaches, we do not suffer from the curse of dimensionality. The main reason is that we do not apply space or data partitioning methods, like bounding boxes, but incrementally index sub-spaces. In addition, our Elf is cache sensitive, contains an optimized storage layout, fixed search paths, and even supports slight data compression rates. Our experimental results indicate a clear superiority of our approach compared to a highly optimized SIMD sequential scan as competitor. 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.

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

Efficient evaluation of multi-dimensional range queries in a main-memory database is an important, but difficult task. State-of-the-art techniques rely on optimised sequential scans or tree-based structures. For range queries with small result sets, sequential scans exhibit poor asymptotic performance. Also, as the dimensionality of the data set increases, the performance of tree-based structures degenerates due to the curse of dimensionality. Recent literature proposed the Elf, a main-memory structure that is optimised for the case of such multi-dimensional low-selectivity queries. The Elf outperforms other state-of-the-art methods in manually tuned scenarios. However, choosing an optimal parameter configuration for the Elf is vital, since for poor configurations, the search performance degrades rapidly. Consequently, further knowledge about the behaviour of the Elf in different configurations is required to achieve robust performance. In this thesis, we therefore propose a numerical cost model for the Elf. Like all main-memory index structures, the Elf response time is not dominated by disk accesses, refusing a straightforward analysis. Our model predicts the size and shape of the Elf region that is examined during search. We propose that the response time of a search is linear to the size of this region. Furthermore, we study the impact of skewed data distributions and correlations on the shape of the Elf. We find that they lead to behaviour that is accurately describable through simple reductions in attribute cardinality. Our experimental results indicate that for data sets of up to 15 dimensions, our cost model predicts the size of the examined Elf region with relative errors below 5%. Furthermore, we find that the size of the Elf region examined during search predicts the response time with an accuracy of 80%.