Integration of structure guided query optimization into newSQL databases

Abstract

Seit jeher sind wir bestrebt die Leistung, Effizienz und Funktionalität von Datenbanksystemen zu verbessern. Dies beinhaltet auch Techniken zur Bewältigung des andauernden Anstieges der Datenmengen in Datenbanken. Ein Schritt zur Bewältigung dieser großen Datenmengen war die Einführung von NoSQL, und folgend für das relationale Datenmodell, sowie die Anforderungen von relationalen Datenbanken, NewSQL Datenbanken. Gleichzeitig müssen die Methoden zur Datenabfrage an die ständig steigenden Datenmengen angepasst werden. Ein derzeit kaum genutzter Ansatz ist strukturbasierte Abfrageoptimierung, welche die Struktur einer Abfrage nutzt, um einen optimalen Join-Baum, basierend auf einer Zerlegung der Abfrage, zu bilden. Darüber hinaus eliminiert der in der Datenbanktheorie bekannte Algorithmus von Yannakakis redundante Tupel, die nicht zum Endergebnis beitragen, durch zwei Runden Semi-Joins. Eine kürzlich durchgeführte Analyse hat gezeigt, dass die meisten realistischen Datenbankabfragen azyklisch oder fast azyklisch sind, so dass sie mit dem Algorithmus von Yannakakis gut verarbeitet werden können. Diese Technik löst zwei der größten Probleme bei der Auswertung von Datenbankabfragen: die Suche nach einer optimalen Join-Reihenfolge und die Vermeidung einer Explosion von Zwischenergebnissen bei der Auswertung einer konjunktiven Abfrage. Trotz der bewiesenen Leistungsvorteile für einige Abfragen wird dieser Algorithmus in der Praxis jedoch von keinem der großen Produktionsdatenbanksysteme verwendet. Das Ziel dieser Arbeit ist es, diese Lücke zwischen theoretisch möglicher Leistung und praktisch genutzten Ansätzen zu schließen, indem wir strukturbasierte Abfrageoptimierung in das NewSQL DBMS TiDB integrieren. TiDB zählt zu den bekanntesten Open-Source NewSQL DBMS. Die empirischen Auswertungen zeigten Leistungsvorteile für einige Abfragen durch strukturbasierte Abfrageauswertung. 40% unserer Full-Enumeration Testabfragen, sowie 30% unserer 0MA Testabfragen hatten mit unserer Implementierung eine geringere Laufzeit als mit herkömmlicher Abfrageauswertung. Der Bedarf an Hauptspeicher ist durch die temporäre Speicherung von Zwischenergebnissen während der Abfrageausführung leicht angestiegen. Besonderes Augenmerk fällt auf die Klasse der Full-Enumeration Abfragen, deren Ergebnis nicht leer ist. Unsere Implementierung hat die Mehrzahl dieser Instanzen mit niedrigerer Laufzeit als die konventionelle Abfrageauswertung gelöst. Die Ergebnisse verdeutlichen die Nützlichkeit der Integration von strukturbasierter Abfrageoptimierung als zusätzliche Abfrageoptimierungsoption in einem DBMS.

Ever since database systems exist, we strive to improve performance, efficiency, and functionalities of databases, including techniques to handle the ongoing trend of rising amounts of data in databases. One step towards dealing with these big amounts of data was the introduction of NoSQL, and subsequently for the relational data model and requirements of RDBMS, NewSQL databases. In parallel, querying of data needs to be adapted to handle the rising amounts of data. One possible approach, which is hardly used at all, is structure guided query optimization, leveraging the structure of a query to build an optimal join tree based on a decomposition of the query, without the need to find an optimal join ordering through traditional query optimization. Additionally, Yannakakis' algorithm, which is well known in database theory, eliminates redundant tuples not contributing to the end result by conducting two rounds of semi-joins, before the actual join of the remaining tuples. A recent analysis showed that most real-world database queries are acyclic, or at least almost acyclic, which can be handled well by Yannakakis' algorithm. This technique solves two of the most urgent problems in database query evaluation, finding an optimal join order, and avoiding an explosion of intermediate results during evaluation of a conjunctive query. However, no major production database system uses this algorithm in practice, despite these proven performance benefits for some queries. The aim of this thesis is to fill this gap between theoretically possible performance and practically used approaches, and integrate structure guided query optimization into the NewSQL DBMS TiDB, which lies among the most popular Open-Source NewSQL DBMS. Our empirical evaluations showed performance benefits for some queries through structure guided query evaluation. 40% of our full enumeration test queries, and 30% of our 0MA test queries were faster with our implementation. The memory usage slightly increased, due to the need for additional temporary tables to store intermediate results. Particular attention falls into the class of full enumeration queries whose result is not empty, for which the majority of instances were faster with our implementation. The results clearly show the benefit of integrating structure guided query optimization, as additional query optimization option, deeply and directly into a DBMS.