LQRS: Learned Query Re-optimization Framework for Spark SQL

Das Paper stellt LQRS vor, ein auf Spark SQL basierendes Framework für gelerntes Query-Re-Optimierung, das durch die Nutzung von Curriculum-Reinforcement-Learning und Echtzeit-Beobachtungen während der Ausführung die End-zu-End-Ausführungszeit im Vergleich zu bestehenden Methoden um bis zu 90 % reduziert.

Das Wesentliche

Stellen Sie sich vor, Sie planen eine große Reise mit dem Zug.

Das alte Problem: Der starre Fahrplan
Traditionelle Datenbanken (wie Spark SQL) funktionieren wie ein Zugführer, der vor der Abfahrt einen Fahrplan erstellt. Er schätzt basierend auf alten Fahrplänen und groben Vermutungen, wie viele Passagiere in jedem Waggon sitzen werden und welche Strecke die schnellste ist.
Das Problem: Die Schätzungen sind oft falsch. Vielleicht ist auf der Strecke A plötzlich eine Baustelle, oder Waggon B ist viel voller als gedacht. Aber sobald der Zug losfährt, kann der Zugführer den Fahrplan nicht mehr ändern. Er muss den falschen Weg bis zum Ende abfahren, was Zeit kostet und den Zug ins Stocken bringt.

Die erste Verbesserung: Adaptive Fahrpläne (Spark AQE)
Spark hat eine Funktion namens "Adaptive Query Execution" (AQE). Das ist wie ein Zugführer, der an jeder Station kurz anhält, die Passagierzahlen zählt und sagt: "Oh, Waggon C ist leer, wir können ihn weglassen" oder "Waggon D ist überfüllt, wir brauchen mehr Lokomotiven". Das ist gut, aber es hat Grenzen: Der Zugführer kann zwar die Art der Lokomotive ändern, aber er kann den Reihenfolge der Stationen nicht mehr ändern, wenn der Zug erst einmal abgefahren ist. Wenn er zu Beginn einen schlechten Weg gewählt hat, bleibt er dabei.

Die Lösung: LQRS – Der lernende Reisebegleiter
Die Forscher von der Renmin-Universität in China haben LQRS entwickelt. Stellen Sie sich LQRS nicht als starren Fahrplan, sondern als einen intelligenten, lernenden Reisebegleiter vor, der den Zug begleitet.

Hier ist, wie LQRS funktioniert, einfach erklärt:

1. Er lernt durch Erfahrung (Reinforcement Learning):
   LQRS ist wie ein Schachspieler, der gegen sich selbst spielt. Er probiert verschiedene Routen aus. Wenn er eine gute Entscheidung trifft (z. B. "Wir fahren zuerst durch die kleine Stadt, weil dort weniger Verkehr ist"), bekommt er Punkte. Wenn er einen Fehler macht, verliert er Punkte. Mit der Zeit wird er immer besser darin, die perfekte Route vorherzusagen.

2. Er schaut in die Zukunft, aber auch in die Gegenwart:
   Anders als andere Systeme, die nur vor der Abfahrt planen, schaut LQRS auch während der Fahrt.

   • Vor der Fahrt: Er nutzt sein gelerntes Wissen, um einen guten Startfahrplan zu erstellen.
   • Während der Fahrt: Das ist der Clou! Sobald der Zug eine Station passiert hat, sieht LQRS die echten Zahlen (nicht nur Schätzungen). "Oh, die Station X war viel kleiner als gedacht! Wir sollten eigentlich zuerst dorthin fahren."
   • Die Aktion: LQRS kann dem Zugführer sagen: "Stop! Ändere die Reihenfolge! Wir fahren jetzt zuerst zu Station Y, nicht zu Z." Er kann den Fahrplan mitten in der Fahrt umschreiben.

3. Der "Kleiner-schritt-für-schritt"-Ansatz (Curriculum Learning):
   Niemand lernt alles auf einmal. LQRS wird nicht sofort mit dem schwierigsten Problem konfrontiert.

   • Anfangs: Er lernt nur, ob er überhaupt einen Zug starten soll oder welche Lokomotive er nimmt.
   • Mittendrin: Er lernt, kleine Änderungen an der Reihenfolge vorzunehmen.
   • Am Ende: Er darf den gesamten Fahrplan komplett umkrempeln, wenn nötig. So wird er nicht überfordert und lernt effizienter.

4. Der "Plug-and-Play"-Anschluss:
   LQRS ist so gebaut, dass es wie ein Zubehörteil in das bestehende Spark-System passt. Es muss nicht das ganze System neu erfunden werden. Es greift einfach in die bestehenden Haltestellen ein, macht seine Anpassungen und lässt den Zug weiterfahren.

Warum ist das so genial?
In einem Test mit einer komplexen Datenbank-Frage (die vier Tabellen verknüpft) passierte folgendes:

• Der alte Plan (Lero): Fuhren eine Route, die 21,5 Sekunden dauerte. Sie konnten nichts ändern.
• LQRS: Sah während der Fahrt, dass eine der Stationen (eine Tabelle) nur einen einzigen Passagier hatte.
• Die Reaktion: LQRS sagte: "Das ist zu klein! Wir müssen diese Station ganz an den Anfang setzen!" Er änderte die Reihenfolge sofort.
• Das Ergebnis: Die Reise dauerte nur noch 15,2 Sekunden. Das ist eine Ersparnis von über 30 %.

Zusammenfassung in einem Satz:
Während andere Systeme wie ein starrer Fahrplan sind, der Fehler nicht korrigieren kann, ist LQRS wie ein kluger Navigator, der während der Fahrt die echten Straßenverhältnisse beobachtet, den Kurs sofort korrigiert und dabei aus jeder Fahrt lernt, um beim nächsten Mal noch schneller zu sein.

Dank LQRS konnten die Forscher die Gesamtzeit für Datenbankabfragen in Tests um bis zu 90 % reduzieren. Das bedeutet: Schnelle Antworten, weniger Warten und effizientere Computer.

Technische Zusammenfassung

Hier ist eine detaillierte technische Zusammenfassung des Papers „LQRS: Learned Query Re-optimization Framework for Spark SQL" auf Deutsch:

1. Problemstellung

Der Query-Optimizer ist eine Kernkomponente moderner Datenbankmanagementsysteme (DBMS). Traditionelle, kostenbasierte Optimierer (CBO) leiden oft unter ungenauen Kostenmodellen, die auf manuell erstellten Formeln basieren. Zwar haben neuere „Learned Query Optimizer" (LQO) wie Lero gezeigt, dass maschinelle Lernmodelle bessere Pläne finden können, doch diese arbeiten meist nach dem Paradigma „Optimieren-dann-Ausführen".

Das Hauptproblem besteht darin, dass diese Modelle ihre Entscheidungen ausschließlich auf Basis von geschätzten Statistiken vor der Ausführung treffen. Sie können wichtige Laufzeitbeobachtungen (Runtime Observations), die während der Ausführung generiert werden (z. B. tatsächliche Kardinalitäten, die stark von den Schätzungen abweichen), nicht nutzen, um den Ausführungsplan dynamisch anzupassen. Dies führt dazu, dass suboptimale Join-Reihenfolgen oder Join-Strategien beibehalten werden, selbst wenn die Laufzeitdaten eine bessere Strategie nahelegen würden.

2. Methodik: LQRS Framework

Die Autoren stellen LQRS (Learned Query Re-optimization Framework) vor, das als erster gelernter Optimierer für Spark SQL sowohl eine Pre-Execution-Optimierung (vor der Ausführung) als auch eine In-Execution-Optimierung (während der Ausführung) ermöglicht.

Kernarchitektur

LQRS baut auf dem Adaptive Query Execution (AQE) Framework von Spark SQL auf und integriert zwei Hauptkomponenten:

1. Planner Extension (Planner-Erweiterung):

   • Diese Komponente ist als Erweiterung der AQE-Regeln in Spark SQL implementiert.
   • Sie nutzt die natürlichen Synchronisationspunkte von Spark (Ende von Query Stages/Shuffles), um den Ausführungsplan zu unterbrechen.
   • Sie extrahiert den teilweise ausgeführten Plan sowie echte Laufzeitstatistiken (tatsächliche Kardinalitäten, Datengrößen in Bytes) und sendet diese an das Entscheidungsmodell.
   • Nach Erhalt einer Optimierungsaktion wendet sie diese direkt auf den laufenden Plan an (z. B. Umordnen von Joins, Ändern von Join-Strategien), ohne die bereits abgeschlossenen Stages neu berechnen zu müssen.

2. Decision Model (Entscheidungsmodell):

   • Basierend auf dem Actor-Critic-Framework (Reinforcement Learning).
   • Zustand (State): Besteht aus dem teilweise ausgeführten Plan (kodiert als Vektor-Baum) und den gesammelten Laufzeitstatistiken.
   • Aktionen (Actions): Das Modell kann verschiedene Optimierungsmaßnahmen wählen:
     • init: Wahl der Initialisierungsstrategie des Plans.
     • swap: Tausch von zwei Blattknoten (Tabellen) im Join-Baum.
     • lead: Vorziehen einer bestimmten Tabelle in die Join-Reihenfolge.
     • broadcast: Erzwingen eines Broadcast-Joins für eine spezifische Tabelle (um die konservativen Schwellenwerte von Spark zu umgehen).
     • no-op: Keine Aktion (Abwarten weiterer Daten).
   • Belohnung (Reward): Das Reward-Signal berücksichtigt nicht nur die endgültige Ausführungszeit, sondern auch Zwischenbelohnungen basierend auf zusätzlichen Shuffle-Operationen, die durch Planänderungen verursacht werden. Dies fördert stabile Entscheidungen.
   • Modellarchitektur: Es wird ein TreeCNN (Tree Convolutional Neural Network) verwendet, um die Baumstruktur des Query-Plans effizient zu verarbeiten.

Lernstrategie: Curriculum Reinforcement Learning

Um die Stabilität des Trainings zu erhöhen, verwendet LQRS eine Curriculum-Learning-Strategie:

• Das Modell beginnt mit einfachen Entscheidungen (nur Initialisierung).
• Im Laufe des Trainings werden komplexere Aktionen (wie Join-Umordnungen während der Laufzeit) schrittweise freigeschaltet.
• Dies ermöglicht es dem Modell, erst grundlegende Strategien zu lernen, bevor es mit der dynamischen Anpassung während der Ausführung konfrontiert wird.

3. Wichtige Beiträge

• Erster gelernter Re-Optimierer für Spark SQL: LQRS ist das erste System, das maschinelles Lernen mit der adaptiven Plananpassung (AQE) von Spark SQL vereint, um sowohl vor als auch während der Ausführung zu optimieren.
• Dynamische Planverfeinerung: Durch die Nutzung echter Laufzeitdaten (z. B. tatsächliche Kardinalitäten) kann LQRS Pläne korrigieren, die auf falschen Schätzungen basieren, und so Join-Reihenfolgen und -Strategien (z. B. SMJ zu BHJ) dynamisch anpassen.
• Plug-and-Play Planner Extension: Die Implementierung nutzt die Erweiterbarkeitsschnittstellen von Spark SQL, um Planänderungen online vorzunehmen, ohne den Kern von Spark zu modifizieren.
• Effizientes Feedback-Design: Durch die Nutzung von Query-Stage-Level-Feedback ist das Feedback für das Lernmodell mindestens 3-mal dichter als bei herkömmlichen End-to-End-Ansätzen, was zu schnellerer Konvergenz führt.

4. Ergebnisse

Die Autoren führten umfangreiche Experimente auf vier Standard-Benchmarks durch: JOB, ExtJOB, STACK und TPC-H.

• Leistungssteigerung: LQRS reduziert die End-to-End-Ausführungszeit im Vergleich zu anderen gelernten Optimierern (wie Lero, AutoSteer) und herkömmlichen Re-Optimierungsmethoden (wie SSA/QuerySplit) um bis zu 90 %.
• Vergleich mit Baselines:
  • Gegenüber Spark SQL (Standard-AQE): Reduktion der Gesamtlaufzeit um 16,3 % bis 73,3 %.
  • Gegenüber Lero: LQRS erzielt ähnliche oder bessere Ergebnisse, vermeidet aber die hohen Overheads durch das vollständige Durchprobieren vieler Pläne vor der Ausführung. Zudem treten weniger Performance-Regressionen auf.
  • Gegenüber AutoSteer: LQRS zeigt deutlich robustere Ergebnisse, da AutoSteer oft zu viele Regeln deaktiviert, was bei komplexen Queries nachteilig ist.
• Dynamische Anpassung: In Fallstudien (z. B. STACK Query q1#1) konnte LQRS eine Join-Reihenfolge ändern, die zu einer drastischen Reduktion der Zwischenergebnisse führte und den Switch von Sort-Merge-Joins zu Broadcast-Joins ermöglichte, was die Laufzeit von 21,52s auf 15,24s senkte.
• Ressourcenverbrauch: LQRS hat den geringsten Optimierungs-Overhead aller getesteten Methoden, da es Entscheidungen basierend auf echten Daten trifft und unnötige Änderungen durch die no-op-Aktion vermeidet.

5. Bedeutung und Ausblick

LQRS demonstriert erfolgreich, dass die Trennung zwischen „Optimierung" und „Ausführung" in modernen Datenbanken überwunden werden kann. Durch die Integration von Reinforcement Learning in den AQE-Prozess von Spark SQL wird gezeigt, dass Laufzeitbeobachtungen genutzt werden können, um Pläne dynamisch zu korrigieren und so die Leistungsgrenzen statischer Optimierer zu durchbrechen.

Das Framework ist nicht nur auf Spark beschränkt; die Autoren argumentieren, dass das Konzept der Nutzung von Materialisierungsgrenzen (wie Shuffles oder Pipeline-Blockern) auch auf andere Systeme wie Flink, Presto oder PostgreSQL übertragbar ist. LQRS stellt somit einen wichtigen Schritt hin zu wirklich adaptiven und lernenden Datenbank-Optimierern dar, die sich an reale Datenverteilungen anpassen können.