Accelerating mono and multi-column selection predicates in modern main-memory database systems

Abstract

Ever-since, database system engineers are striving for peak performance of theirdatabase operators. However, this goal is a major endeavor since database opera-tors are influenced not only by thehardware(i.e., the executing processor or thememory hierarchy), but also by theworkload(i.e., data distribution, selectivity,etc.). Especially in today’s world of main-memory database systems, there are newprocessing capabilities (e.g., advanced vector instructions such as AVX-512), newstorage devices (e.g., Intel Optane as non-volatile RAM), or new diverse applicationsfor data management (e.g., in-database machine learning) frequently introduced thatbecome essential impact factors. Hence, a once optimal operator has to be frequentlyadapted with these new arising hardware and workloads.A typical database operator that is frequently tuned by researchers is the selectionoperator, because selections are essential to reduce the load of subsequent operatorsand 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 theimportance of tuning this data-intensive operator to avoid a serious bottleneck.Although the selection operator is frequently tuned for arbitrary use cases mentionedabove, there is no comprehensive and holistic way to tune this operator automatically.Furthermore, considering multiple selections on the same table, straight-forwardimplementations use candidate scans for several selection predicates. However,exploiting the interdependence and, hence, high selectivity is not investigated sofar. In this thesis, we tackle the aforementioned challenges of (1) creating hardware-sensitive operator implementations automatically and (2) exploiting the relationbetween multiple selection predicates.For solving the first challenge, we investigate the commonalities of different optimiza-tions for arbitrary hardware and workloads on the example of the selection operator.As a result, we introduce the abstraction ofcode optimizationsas a means to generatehardware-sensitive code variants automatically. The solution is completed by theconcept of a tuning framework for operators in main-memory database systems.As a solution for the second challenge, we propose to revive multi-dimensional indexstructures as a means to exploit the relation between selection predicates on severalcolumns in main-memory database management systems. In order to allow forhardware-sensitivity – especially cache consciousness – we propose our main-memoryindex structure Elf. Elf is a tree structure combining prefix-redundancy eliminationwith an optimized memory layout explicitly designed for efficient main-memoryaccess. 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 selectionpredicates and queries from the standard OLAP benchmark TPC-H. However, ourevaluation also identifies that an integration into the query engine of the main-memory database system MonetDB does not only show strengths but also limitationsthat any sort-based index structure is faced with.Overall, the resulting approaches can be used in future query engines to form a Swissarmy knife for arbitrary selection predicates. Hence, our contribution enriches aquery engine far beyond current state-of-the-art-approaches by allowing for efficientexecution of a single predicate (i.e.,mono-column selection predicates) atbare-metal speedas well as exploiting the combined selectivity of several predicates (i.e.,multi-column selection predicates).

Seit jeher streben Datenbankentwickler nach H ̈ochstleistungen ihrer Datenbankopera-toren. Dieses Ziel ist jedoch ein umf ̈angliches Unterfangen, da Datenbankoperatorennicht nur von der Hardware (d.h. dem ausf ̈uhrenden Prozessor oder der Speicher-hierarchie), sondern auch von den zu verarbeitenden Daten (d.h. Datenverteilung,Selektivit ̈at, etc.) beeinflusst werden. Mit dem Fortschreiten der Technik – vor allemin Hauptspeicherdatenbanken – gibt es st ̈andig neue Verarbeitungsm ̈oglichkeiten (z.B.erweiterte Vektorbefehle wie AVX-512), neue Speicherger ̈ate (z.B. Intel Optane alsnicht-fl ̈uchtiger RAM) oder neue vielf ̈altige Anwendungen f ̈ur das Datenmanagement(z.B. datenbankintegriertes maschinelles Lernen), die zu wesentlichen Einflussfaktorenwerden. Daher muss ein einst optimaler Operator h ̈aufig an diese neu entstehendeHardware und Anwendungsszenarien angepasst werden.Ein typischer Datenbankoperator, der von Forschern h ̈aufig getunt wird, ist derSelektionsoperator, denn Selektionen sind unerl ̈asslich, um die Last nachfolgenderOperatoren zu reduzieren. Des weiteren sind Selektionen in der Regel einer derersten Operatoren, die in einem Abfrageplan ausgef ̈uhrt werden. Daher arbeitet derSelektionsoperator auf der gesamten Datenmenge - eine Tatsache, die die Bedeutungdes Tunings dieses datenintensiven Operator unterstreicht, um einen schwerwiegendenEngpass zu vermeiden. Obwohl der Selektionsoperator h ̈aufig auf eine Vielzahl deroben genannten Einfl ̈usse abgestimmt ist, gibt es keine umfassende und ganzheitlicheM ̈oglichkeit, diesen Operator automatisch zu optimieren. Dar ̈uber hinaus verwen-den naive Implementierungen bei mehreren Selektionen auf derselben Tabelle einenKandidaten-Scan f ̈ur mehrere Selektionspr ̈adikate. Die Ausnutzung der Interdepen-denz und damit der hohen Selektivit ̈at wurde jedoch noch nicht untersucht. In dieserArbeit besch ̈aftigen wir uns mit den oben genannten Herausforderungen: (1) derautomatischen Erstellung von hardwaresensitiven Operatorimplementierungen und(2) der Ausnutzung der Beziehung zwischen mehreren Selektionspr ̈adikaten.Zur L ̈osung der ersten Herausforderung untersuchen wir die Gemeinsamkeiten ver-schiedener Optimierungen f ̈ur beliebige Hardware und Datencharacteristika amBeispiel des Selektionsoperators. Als Ergebnis f ̈uhren wir die Abstraktion vonCode-Optimierungen ein, um hardwaresensitive Codevarianten automatisch zu gener-ieren. Abgerundet wird die L ̈osung durch das Konzept eines Tuning-Frameworks f ̈urbeliebige Operatoren in Hauptspeicherdatenbanksystemen.Als L ̈osung f ̈ur die zweite Herausforderung schlagen wir vor, multidimensionale In-dexstrukturen wiederzubeleben, um die Beziehung zwischen Selektionspr ̈adikatenauf mehreren Spalten auszunutzen. Um die Hardware-Sensitivit ̈at – insbeson-dere die Optimierung auf CPU-Caches – zu ber ̈ucksichtigen, schlagen wir unsere Hauptspeicher-Indexstruktur Elf vor. Elf ist eine Baumstruktur, die die Eliminierungvon Pr ̈afixredundanzen mit einem optimierten Speicherlayout kombiniert und dessenspezielle Speicherorganisation f ̈ur einen effizienten Zugriff im Hauptspeicher optimiertist. Unsere Experimente zeigen, dass Elf in der Lage ist, mehrere hochpotenteKontrahenten (einschließlich generierter hardwaresensitiver Scans und modernermultidimensionaler Indexstrukturen) um mehrere Magnituden f ̈ur eine sinnvolleAuswahl von Abfragen aus dem Standard OLAP-Benchmark TPC-H zu ̈ubertreffen.Unsere Auswertung zeigt aber auch, dass eine Integration in die Query-Engine desHauptspeicher-Datenbanksystems MonetDB nicht nur St ̈arken, sondern auch Grenzenaufweist, mit denen jede sortierbasierte Indexstruktur konfrontiert ist.Insgesamt k ̈onnen die resultierenden Ans ̈atze in zuk ̈unftigen Anfrageverarbeitungs-Engine genutzt werden, um eine eierlegende Wollmilchsau f ̈ur beliebige Selektion-spr ̈adikate zu bilden. Daher bereichert unser Beitrag eine Anfrageverarbeitungs-Engine weit ̈uber den aktuellen Stand der Technik hinaus, indem er einerseits dieAusf ̈uhrung eines einzelnen Pr ̈adikats (d.h. einspaltiger Selektionspr ̈adikate) an dasobere Ende der technisch m ̈oglichen Performanz der CPU bringt und andererseits diekombinierte Selektivit ̈at mehrerer Pr ̈adikate (d.h. mehrspaltiger Selektionspr ̈adikate)effizient ausnutzen kann.