Optimization and processing of relational database queries

Abstract

The purpose of this Ph.D. thesis is to advance the state of the art of query processing in relational database systems. As first contribution, I present a reduction of the classical, NP-hard join order opti- mization problem to a shortest path problem. Consequently, I develop a heuristic search algorithm for solving this reduced problem. I provide a strong theoretical foundation for the reduction and the search. A thorough evaluation shows improvements in optimization time of orders of magnitude. My second contribution is a simplified design for query execution by just-in-time compilation to machine code. Architecturally simple solutions such as query compilation with LLVM suffer from unacceptably high compilation times. Modern just-in-time query compilers with significantly reduced compilation times, on the other side, are extravagantly hand-crafted. Rather than reinventing compiler technology in a DBMS, I propose to embed an off-the-shelf just-in-time compiling engine that is designed, built, and tested by compiler experts. I am able to achieve the lowest compilation times and competitive execution performance in all experiments. As my third contribution, I design a relational DBMS as a software system that is composed of individual components, each implementing an isolated logical task. For example, join ordering is one such component of a composable DBMS. I describe the design principles that guide my and my colleagues’ efforts towards implementing such a DBMS. Most importantly, my thesis is accompanied by the release of our open-source research DBMS mutable, that implements this design of composition.

Ziel dieser Dissertation ist es, den Stand der Technik bei der Verarbeitung von Anfragen in relationalen Datenbanksystemen zu verbessern. Als ersten Beitrag präsentiere ich eine Reduktion des klassischen, NP-schweren Optimierungsproblems der Join-Reihenfolge auf ein Kürzester-Pfad-Problem. Folglich entwickle ich einen heuristischen Suchalgorithmus zur Lösung dieses reduzierten Problems. Ich biete eine starke theoretische Grundlage für die Reduktion und die Suche. Eine gründliche Auswertung zeigt eine Verbesserung der Optimierungszeit um Größenordnungen. Mein zweiter Beitrag ist ein vereinfachtes Design für die Ausführung von Anfragen durch just-in-time Kompilierung in Maschinencode. Architektonisch einfache Lösungen wie die Anfragekompilierung mit LLVM leiden unter inakzeptabel hohen Kompilierungszeiten. Moderne just-in-time Anfrage-Compiler mit deutlich reduzierten Kompilierzeiten sind dagegen aufwendig selbst entwickelt. Anstatt die Compilertechnologie in einem DBMS neu zu erfinden, schlage ich vor, eine gebrauchsfertige just-in-time Compiler-Engine einzubinden, die von Compiler- Experten entworfen, gebaut und getestet wurde. Ich bin in der Lage, in allen Experimenten die niedrigsten Kompilierzeiten und eine konkurrenzfähige Ausführungsleistung zu erzielen. In meinem dritten Beitrag entwerfe ich ein relationales DBMS als ein Softwaresystem, das aus einzelnen Komponenten zusammengesetzt ist, von denen jede eine isolierte logische Aufgabe implementiert. Zum Beispiel ist die Join-Anordnung eine solche Komponente eines zusammensetzbaren DBMS. Ich beschreibe die Designprinzipien, die mich und meine Kollegen bei der Implementierung eines solchen DBMS leiten. Am wichtigsten ist, dass meine Arbeit von der Veröffentlichung unseres Open-Source-Forschungs-DBMS mutable begleitet wird, das dieses Design der Zusammensetzung implementiert.