Challenging Traditional Views and Techniques in Relational Query Processing and Indexing

Abstract

Query processing and indexing are fundamental components of every relational database management system. These areas are concerned with core aspects such as performance, design, and maintenance, which have been the subject of extensive, longstanding research. As a result, well-established methods and paradigms have emerged, particularly in query optimization, index construction, and the design and functionality of SQL. In this thesis, we aim to challenge and redefine some of these traditional views and techniques. In the first part of this thesis, we question the translation of a logical plan to a physical plan on the granularity of complete operators during query optimization. Instead, we propose to deepen this process by breaking up the abstraction of an operator to consider more fine-granular subcomponents, enabling additional optimization potential. Our experimental validation demonstrates the impact of varying physical representations of a logical operator and highlights that a more holistic optimization approach can significantly improve estimated query plan quality. In the second part of this thesis, we aim to apply this approach specifically to index structures, which are generally considered monolithic and hand-crafted entities tailored to specific use cases. We propose a generic indexing framework that breaks up index structures by separating a logical index from a physical index similar to the split into logical and physical operators. Furthermore, we formulate index construction as an optimization problem that we solve using genetic programming. Our experiments show that our approach successfully rediscovers existing baselines. In addition, an optimized index tailored to a specific dataset and workload not only matches, but in some cases, surpasses the performance of traditional indexes. In the third part of this thesis, we propose a single keyword extension to SQL that breaks up the single-table result limitation by allowing to return a subdatabase. This subdatabase contains the tables that participate in the query, each reduced to those tuples that contribute to the traditional query result. We present four SQL-based rewrite methods and an efficient native algorithm that we implemented in a database system with a state-of-the-art compiling query execution engine. The experimental evaluation shows that multiple individual result sets significantly reduce the overall result set size, with our methods adding minimal overhead to the query execution time and, in some cases, even outperforming traditional, single-table execution.

Abfrageverarbeitung und Indizierung sind grundlegende Komponenten jedes relationalen Datenbankmanagementsystems. Diese Bereiche befassen sich mit zentralen Aspekten wie Leistung, Design und Wartung, die seit langem Gegenstand umfangreicher Forschung sind. Infolgedessen sind fest etablierte Methoden und Paradigmen entstanden, insbesondere in der Abfrageoptimierung, der Indexkonstruktion sowie im Design und der Funktionalität von SQL. In dieser Arbeit wollen wir einige dieser traditionellen Ansichten und Techniken infrage stellen und neu definieren. Im ersten Teil dieser Arbeit hinterfragen wir die Übersetzung eines logischen Plans in einen physischen Plan auf der Granularität vollständiger Operatoren während der Abfrageoptimierung. Stattdessen schlagen wir vor, diesen Prozess zu vertiefen, indem wir die Abstraktion eines Operators aufbrechen, um feingranularere Teilkomponenten zu betrachten, die zusätzliches Optimierungspotenzial ermöglichen. Unsere experimentelle Validierung zeigt die Auswirkungen unterschiedlicher physischer Repräsentationen eines logischen Operators und hebt hervor, dass ein ganzheitlicherer Optimierungsansatz die geschätzte Qualität des Abfrageplans erheblich verbessern kann. Im zweiten Teil dieser Arbeit wollen wir diesen Ansatz speziell auf Indexstrukturen anwenden, die im Allgemeinen als monolithische und handgefertigte Einheiten betrachtet werden, die auf spezifische Anwendungsfälle zugeschnitten sind. Wir schlagen ein generisches Index-Framework vor, das Indexstrukturen aufbricht, indem es einen logischen Index von einem physischen Index trennt, ähnlich wie bei der Aufteilung in logische und physische Operatoren. Darüber hinaus formulieren wir die Indexkonstruktion als ein Optimierungsproblem, das wir mithilfe genetischer Programmierung lösen. Unsere Experimente zeigen, dass unser Ansatz in der Lage ist, bestehende Referenzindexe wiederzuentdecken. Des Weiteren ist ein optimierter Index, der auf einen spezifischen Datensatz und Arbeitslast zugeschnitten ist, nicht nur in der Lage die Leistung traditioneller Indexe zu erreichen, sondern diese in bestimmten Szenarien sogar zu übertreffen. Im dritten Teil dieser Arbeit schlagen wir eine Erweiterung von SQL um ein einziges Schlüsselwort vor, die die Einschränkung des Ergebnisses auf eine einzige Tabelle aufbricht, indem sie die Rückgabe einer Teildatenbank ermöglicht. Diese Teildatenbank enthält die an der Abfrage beteiligten Tabellen, die jeweils auf die Tupel reduziert sind, die zum traditionellen Abfrageergebnis beitragen. Wir stellen vier SQL-basierte Umformungsmethoden und einen effizienten nativen Algorithmus vor, den wir in einem Datenbanksystem mit einer modernen kompilierenden Engine zur Ausführung von Abfragen implementiert haben. Die experimentelle Auswertung zeigt, dass mehrere individuelle Ergebnisse die Gesamtgröße des Ergebnisses erheblich reduzieren, wobei unsere Methoden nur minimalen zusätzlichen Aufwand bezüglich der Ausführungszeit der Abfrage verursachen und in einigen Fällen sogar die traditionelle Ausführung mit nur einer Ergebnistabelle übertreffen.