From component to system: evaluating recursive model indexes and index scan execution strategies

Abstract

Indexes are crucial in database systems for ensuring efficient data retrieval and achieving peak query performance. Traditionally, indexes are general-purpose data structures, agnostic to data distributions. However, learned indexes, like the recursive model index (RMI), challenge this conventional approach by using machine-learned models that exploit data-specific patterns. This allows learned indexes to achieve both remarkable lookup performance and better space efficiency than traditional indexes. Constructing an RMI requires precise adjustment of multiple hyperparameters to attain optimal performance. Therefore, we conduct a thorough analysis of the RMI's hyperparameters in the first part of this thesis, developing a practical guideline for its configuration. Compared to exhaustive enumeration, our guideline achieves competitive lookup performance while being more efficient, training at most two RMIs. The performance is also validated against state-of-the-art indexes, both learned and traditional. We integrate RMIs into a database system with a compiling query engine in the second part of this thesis. We present a novel query engine that allows the query compiler to partially execute queries during compilation. Based on this architecture, we develop three strategies for accessing indexes in the context of an index scan. These strategies differ in which steps of the index scan are executed during compilation versus at runtime. We evaluate the three strategies based on query execution time, identifying the ideal query selectivities and workload characteristics for each. Despite their benefits, our experiments show that RMIs do not improve query performance of index scans compared to a simple baseline index, as index traversal time proved negligible compared to overall query execution time.

Indexe sind in Datenbanksystemen von entscheidender Bedeutung, um effiziente Datenabrufe zu gewährleisten und optimale Abfrageleistung zu erzielen. Üblicherweise sind Indexe universelle Datenstrukturen, deren Leistung unabhängig von der Datenverteilung ist. Gelernte Indexe wie der Recursive-Model-Index (RMI) stellen diesen konventionellen Ansatz jedoch zunehmend infrage, indem sie mittels maschinellem Lernen datenspezifische Muster ausnutzen und so Indizes durch gelernte Modelle ersetzen. Dadurch erzielen gelernte Indexe bemerkenswerte Abfrageleistung und sind zudem speicherplatzsparender als herkömmliche Indexe. Die Konstruktion eines RMI erfordert präzises Anpassen mehrerer Hyperparamter, um optimale Leistung zu erzielen. Daher führen wir im ersten Teil der Arbeit eine umfassende Analyse der Hyperparameter des RMI durch und entwickeln eine praxisorientierte Anleitung zum Konfigurieren von RMIs. Verglichen mit vollständigem Aufzählen aller Konfigurationen erzielt unser Ansatz konkurrenzfähige Abfrageleistung und ist gleichzeitig effizienter, da höchstens zwei RMIs trainiert werden müssen. Die Leistung wird zudem gegenüber hochmodernen Indexen, sowohl traditionellen als auch gelernten, validiert. Im zweiten Teil der Arbeit integrieren wir RMIs in ein Datenbanksystem mit kompilierender Query-Engine. Wir präsentieren eine neuartige Query-Engine, die es dem Query-Compiler ermöglicht, Abfragen bereits während der Kompilierung teilweise auszuführen. Basierend auf dieser Architektur entwickeln wir drei Strategien für den Indexzugriff im Kontext eines Index-Scans. Diese Strategien unterscheiden sich darin, welche Schritte des Index-Scans während des Kompilierens und welche zur Laufzeit ausgeführt werden. Wir vergleichen die drei Strategien hinsichtlich Abfrageleistung und ermitteln für jede Strategie die optimale Abfrageselektivitäten und Workload-Eigenschaften. Trotz ihrer Vorteile zeigen unsere Experimente, dass RMIs die Abfrageleistung von Index-Scans im Vergleich zu einem einfachen Referenzindex nicht verbessern, da die Indexzugriffszeit im Verhältnis zur gesamten Abfrageausführungszeit vernachlässigbar ist.