To rewrite or not to rewrite: Decision making in query optimization of SQL queries

Abstract

Eine typische Herausforderung für Datenbankmanagementsysteme (DBMSs) ist es, Queries effizient auszuwerten. Die einfachsten Queries sind Conjunctive Queries (CQs), die in SQL SELECT-FROM-WHERE Queries entsprechen, bei denen im WHERE statement nur Gleichheitsbedingungen und logische Unds (AND) erlaubt sind. Sogar das Auswerten dieser fundamentalen Queries ist ein NP-vollständiges Problem. In der Praxis ist ein erheblicher Teil aller Queries azyklisch oder fast azyklisch, die CQs mit einfacheren Strukturen sind. DBMSs berücksichtigen strukturelle Eigenschaften im Normalfall nicht, wohingegen in der Theorie mit dem Yannakakis Algorithmus eine effiziente Auswertungsmethode für azyklische Queries existiert. Um eine auf Yannakakis basierende Auswertungsmethode zu nutzen, muss die Query umgeschrieben werden, sodass das DBMS gezwungen wird, die Query in der Art auszuführen, die Yannakakis vorschlägt. Es gibt einen Ansatz, der solch eine Umschreibungsmethode, die on-top von einigen DBMSs benutzt werden kann, für azyklische CQs mit zusätzlichen Aggregaten bereitstellt. Theoretisch wird der asympotitische Worst-Case immer besser, wenn man diese Methode benutzt. Allerdings werden in der Praxis zusätzliche Overheads produziert und es ist unklar und schwierig zu entscheiden, ob die Umschreibungsmethode oder das Auswerten mit dem ursprünglichen DBMS vorteilhafter ist. Daher wird ein Entscheidungsprogramm benötigt, um herauszufinden, ob es besser ist, die Query umzuschreiben oder in ihrer originalen Form zu verwenden. Die Aufgabe dieser Arbeit ist es, solch ein Entscheidungsprogramm zu entwickeln und zu implementieren. Das wird mit Hilfe von umfangreichen Tests auf Benchmarkdatensätzen gemacht, um Features zu finden, mit denen man die Queries unterscheiden kann. Auf Basis dieser Features wird das Entscheidungsprogramm entwickelt und programmiert. Das Entscheidungsprogramm ist ein Machine Learning Modell, das aus einigen modernen Machine Learning Modellen ausgewählt wird. Bei unseren quantitativen und qualitativen Analysen zeigt sich, dass der Decision Tree am besten funktioniert. Dafür werden Metriken benutzt, die fehlklassifizierte Fälle untersuchen und statistische Tests herangezogen. Weiters sind Decision Trees Modelle, die interpretiert werden können und die keinen hohen Rechenaufwand erfordern. Mit diesem Decision Tree als Entscheidungsprogramm können wir drei komplett unterschiedliche DBMSs, nämlich PostgreSQL, DuckDB and SparkSQL, übertreffen.

A common challenge for database management systems (DBMSs) is efficiently evaluating queries. The most basic queries are conjunctive queries (CQs), which are SELECT-FROM-WHERE queries only allowing equality conditions with logical ands (AND) in the WHERE statement in SQL. Even the evaluation of these fundamental queries is an NP-complete problem. In practice a significant portion of queries is acyclic or almost acyclic, which are CQs with easier structures. DBMSs generally do not consider structural properties, but in theory Yannakakis' algorithm gives us an efficient evaluation for acyclic queries. To make use of Yannakakis-style evaluation the query has to be rewritten such that the DBMS is forced to execute the query like Yannakakis' algorithm would suggest. There is an approach providing such a rewriting method applicable on-top of several DBMSs for acyclic CQs allowing additional aggregates. In theory, the asymptotic worst case always gets better using this method. Nevertheless, in practice additional overheads are produced and it is unclear and hard to decide, whether it is preferable to use the rewriting method or the plain DBMS for the evaluation. Therefore, a decision program is needed to determine, if the query should be rewritten or evaluated in its original form. The purpose of this work is to design and implement such a program. This is done by using extensive testing on benchmark datasets to find out which features can be used to distinguish the queries. Based on these features the decision method is designed and implemented. The decision program is a Machine Learning model chosen out of a range of modern Machine Learning models. We see that the decision tree performs best in terms of quantitative and qualitative analysis, based on metrics, inspection of misclassifications and statistical tests. Moreover, decision trees are interpretable models, which are computationally not expensive. With this decision tree as decision program we can outperform three completely different existing DBMSs, namely PostgreSQL, DuckDB and SparkSQL.