Constructing a Relational Query Optimizer for Non-Relational Languages

Abstract

Flat, unordered table data and a declarative query language established today’s success of relational database systems. Provided with the freedom to choose the evaluation order and underlying algorithms, their complex query optimizers are geared to come up with the best execution plan for a given query. With over 30 years of development and research, relational database management systems belong to the most mature and efficient query processors (especially for substantial amounts of data).

In contrast, ordered lists of possibly nested data structures are used throughout in programming languages. Most developers handle these constructs on a daily basis and need to change their programming style, when confronted with a relational database system. To leverage the potential of the relational query processing facility in the context of non-relational languages—without the need for a context switch—we provide a query language that copes with order, nesting, and more complex data structures (such as tuples, named records, and XML data). Queries expressed in this language are compiled into relational queries over flat, unordered tables.

We take great care in the faithful mapping of the “alien” language constructs. This work describes the Pathfinder compiler achieving the transformation based on the loop lifting compilation strategy. The compiler transforms the input queries into logical algebra plans. The operators of this unordered algebra consist mainly of standard table algebra operators. Additional numbering and XML operators generate surrogate values to ensure an accurate representation of order, nesting, and more complex data structures.

Because of the exotic plan shape—the average plan consists of hundreds of operators and a large number of sharing points—and the numbering operators, the query optimizers of all tested database systems fail to come up with an efficient execution plan. We faced this challenge ourselves and describe an optimization framework that annotates the operators with plan properties and performs local rewrites based on the collected properties. The optimizations are guided by heuristics that are geared to significantly decrease the number of operators and order constraints.

The resulting plans are either turned into declarative SQL queries or scripts written for more specialized relational database systems, most notable MonetDB/XQuery. Whereas MonetDB/XQuery ships with a highly tuned runtime for XML processing, the generated SQL code allows to additionally benefit from the built-in optimizers of relational database systems. Experiments as well as plan analyses show that, in contrast to the initial plans, most optimized plans resemble queries from an ordinary database workload and are evaluated efficiently.

In summary, the compiler turns relational database systems into high-performance query processors for non-relational languages.

Die Speicherung von Daten in flachen, ungeordneten Tabellen sowie eine deklarative Anfragesprache sind Gründe für den Erfolg relationaler Datenbanksysteme: Sie erlauben einem Datenbankoptimierer nicht nur die Auswahl verschiedener Algorithmen, sondern auch die Wahl der besten Auswertungsreihenfolge. Dank jahrzehntelanger Forschung und Entwicklung zählen relationale Datenbanksysteme zu den besten Auswertungsplattformen für große Datenmengen.

In den meisten Programmiersprachen werden, im Gegensatz zu Datenbanksystemen, sortierte und mitunter verschachtelte Datenstrukturen verwendet. Die meisten Software-Entwickler arbeiten täglich mit diesen Datenstrukturen in der Programmiersprache ihrer Wahl, was dazu führt, dass das Schreiben von Datenbankanfragen oft ein Umdenken erfordert, beziehungsweise eine potentielle Fehlerquelle darstellt. Um die Vorteile von relationalen Datenbanksystemen für Entwickler in ihrer bekannten Umgebung nutzbar zu machen, stellen wir eine nicht-relationale Sprache vor, die mit Ordnung, verschachtelten Listen und komplexeren Datenstrukturen, wie zum Beispiel Tupeln, benannten Records und XML-Daten, umgehen kann. Wir übersetzen in dieser Sprache formulierte Anfragen in ungeordnete relationale Anfragen, die auf Tabellen arbeiten.

Die Übersetzung ist integraler Bestandteil des Compilers Pathfinder und beruht auf dem Konzept des loop lifting: Sie stellt die genaue Transformation der “fremden” Sprachkonzepte in die relationale Welt sicher. Die Zielsprache ist eine ungeordnete logische Algebra, deren Operatoren aus bekannten Algebra-Operatoren der Datenbankliteratur sowie zusätzlichen Nummerierungs- und XML-Operatoren besteht. Die zusätzlichen Operatoren ermöglichen die genaue Übersetzung von Ordnung, verschachtelten Listen und komplexeren Datenstrukturen.

Im Gegensatz zu normalen Datenbankanfragen besteht ein Algebraplan durchschnittlich nicht aus dutzenden, sondern aus hunderten von Operatoren. Die Kombination aus Größe des Plans, Vernetzung der Operatoren und Nummerierungsoperatoren überfordert alle von uns getesten Datenbankoptimierer. In dieser Arbeit stellen wir einen eigenen Optimierer vor, der die logischen Algebrapläne analysiert und jeden Operator mit Annotationen versieht. Diese Anmerkungen beschreiben Eigenschaften des umgebenden Planes und werden verwendet um gezielt lokale Plantransformationen vorzunehmen. Die Optimierungen werden durch Heuristiken gesteuert und führen jeweils zu einer inkrementellen Verbesserung des Plans. Ziel der Optimierungen ist das Entfernen möglichst vieler Operatoren—im Speziellen der Nummerierungsoperatoren—unter Berücksichtigung semantischer Äquivalenz.

Die vereinfachten Anfragepläne werden entweder in SQL-Anfragen oder in Skripte für das Hauptspeicher-Datenbanksystem MonetDB/XQuery übersetzt. MonetDB/XQuery kann, dank vieler XML-spezifischer Algorithmen und Erweiterungen, Anfragen auf XML-Daten sehr effizient auswerten. Die generierten SQL-Anfragen können stattdessen auf fast jedem relationalen Datenbanksystem ausgewertet werden und profitieren zusätzlich von den eingebauten Anfrageoptimierern der Datenbanksysteme. In unseren Experimenten analysieren wir die Qualität der optimierten Anfragepläne und vergleichen die Auswertungszeiten. Die untersuchten, optimierten Anfragen erinnern in ihrer Effizienz an handgeschriebene Anfragen.

Die Kombination aus Übersetzung in logische Algebrapläne, Optimierung und Generierung von Datenbankanfragen ergibt einen Compiler, der den Einsatz von relationalen Datenbanksystemen als effiziente Laufzeitumgebungen für nicht-relationale Sprachen ermöglicht.