Efficient Query Rewrite Rule Discovery via Standardized Enumeration and Learning-to-Rank(extend)

Die Arbeit stellt SLER vor, ein skalierbares System, das durch die Kombination standardisierter Template-Enumeration mit einem Learning-to-Rank-Ansatz effizient über eine Million effiziente Abfrage-Umschreibungsregeln für komplexe Datenbankabfragen automatisch entdeckt und dabei die Suchräume drastisch reduziert.

Das Wesentliche

Stellen Sie sich eine riesige Bibliothek vor, in der jeder Buchtitel eine komplexe Anweisung für einen Koch (den Datenbank-Optimierer) ist. Manchmal sind diese Anweisungen unnötig kompliziert, voller Wiederholungen und ineffizient. Das Ziel der Datenbank-Optimierung ist es, diese Anweisungen zu vereinfachen, damit das Essen (die Datenabfrage) schneller serviert wird.

Bisher gab es zwei Probleme:

1. Manuelle Arbeit: Experten mussten diese Vereinfachungen mühsam von Hand erfinden. Das ging zu langsam.
2. Der alte Roboter (WeTune): Es gab einen automatischen Roboter, der versuchen sollte, alle möglichen Vereinfachungen zu finden. Aber dieser Roboter war wie ein Kind, das versucht, jedes mögliche Wort in einem Wörterbuch zu kombinieren. Er verbrachte Jahre damit, nur um herauszufinden, dass "Apfel + Birne" dasselbe ist wie "Birne + Apfel". Er scheiterte, sobald die Anweisungen zu komplex wurden (mehr als 4 Schritte).

Hier kommt SLER ins Spiel – ein neuer, intelligenter Ansatz, der diese Probleme löst. Man kann sich SLER wie einen super-effizienten Küchenchef mit einem magischen Rezeptbuch vorstellen.

Wie funktioniert SLER? (Die drei Geheimwaffen)

SLER nutzt drei clevere Tricks, um das Chaos zu bändigen:

1. Der "Standardisierungs-Trick" (Das Ordnungsprinzip)

Stellen Sie sich vor, Sie haben einen Haufen Lego-Bausteine. Der alte Roboter hat versucht, jede denkbare Form daraus zu bauen, auch wenn die Steine nur umgedreht waren. Das war eine Verschwendung.
SLER sagt: "Halt! Wir bauen nur noch nach einem Standardplan."

• Die Analogie: Wenn Sie ein Haus bauen, sagen Sie: "Wir stellen immer zuerst die Wände auf, dann das Dach. Wir drehen nichts um."
• Der Effekt: SLER ignoriert alle unnötigen Variationen sofort. Es filtert heraus, dass "Wand zuerst, dann Dach" dasselbe ist wie "Dach zuerst, dann Wand" (wenn es logisch äquivalent ist). Dadurch wird der Suchraum von einem unendlichen Ozean auf einen überschaubaren Teich reduziert.

2. Der "RTP-Filter" (Der intelligente Ausreißer)

Selbst mit dem Standardplan gibt es noch viele Rezepte, die fast identisch sind.

• Die Analogie: Stellen Sie sich vor, Sie testen 100 neue Kuchenrezepte. Der RTP-Algorithmus ist wie ein erfahrener Konditor, der schon beim ersten Probieren sagt: "Moment, dieser Kuchen schmeckt genau wie der vorige, nur mit etwas mehr Zucker. Wir brauchen das nicht nochmal zu backen."
• Der Effekt: SLER prüft sofort, ob ein neues "Rezept" (eine Regel) wirklich etwas Neues bringt oder nur eine Wiederholung ist. Es spart enorm viel Zeit, indem es doppelte Arbeit vermeidet.

3. Der "Lernende Rangier-Meister" (Die KI-Vorhersage)

Das ist der coolste Teil. Selbst mit den ersten beiden Tricks wäre es immer noch zu viel Arbeit, alle komplexen Rezepte (mit 7, 8 oder mehr Schritten) zu testen.

• Die Analogie: Stellen Sie sich vor, Sie haben 1 Million neue Rezepte. Sie können nicht alle kochen. Also nutzen Sie einen KI-Koch, der die Rezepte nur anschaut und sagt: "Dieses hier sieht vielversprechend aus, das andere ist sicher langweilig."
• Der Effekt: SLER trainiert eine KI (ein "Learning-to-Rank"-Modell), die anhand der Struktur des Rezepts vorhersagt, ob es die Datenbank beschleunigt. Die KI sortiert die besten 100 Rezepte an die Spitze. SLER kocht nur diese Top-Rezepte. So kann es sogar extrem komplexe Rezepte finden, die für alte Roboter unmöglich waren.

Was hat SLER erreicht?

• Größe: SLER hat eine Bibliothek mit über 1 Million neuen Regeln erstellt. Der alte Roboter (WeTune) hatte nur Regeln für sehr einfache Rezepte (bis 4 Schritte). SLER findet Regeln für Rezepte mit 10 Schritten und mehr.
• Geschwindigkeit: Wo der alte Roboter Jahre gebraucht hätte, um komplexe Regeln zu finden, schafft SLER dies in Tagen oder Wochen.
• Qualität: SLER findet Vereinfachungen, die niemand vorher gesehen hat. In Tests konnte es komplexe Datenbankabfragen oft in einem einzigen Schritt vereinfachen, während der alte Roboter scheiterte oder viele kleine Schritte brauchte.

Zusammenfassung für den Alltag

Stellen Sie sich vor, Sie wollen den kürzesten Weg durch einen riesigen, verwirrenden Dschungel finden.

• Der alte Ansatz war: "Lauf jeden einzelnen Pfad ab, auch wenn er nur einen Schritt nach links oder rechts abweicht." (Das dauert ewig).
• SLER ist wie ein Drohnen-Team:
  1. Es ignoriert alle Pfade, die nur eine andere Bezeichnung haben, aber zum selben Ziel führen (Standardisierung).
  2. Es markiert sofort Pfade, die doppelt sind (RTP-Filter).
  3. Es nutzt eine KI, die aus der Luft schaut und sagt: "Die Pfade dort oben sehen vielversprechend aus, lasst uns nur die testen." (Ranking).

Das Ergebnis: SLER findet nicht nur den schnellsten Weg, sondern entdeckt auch völlig neue, kürzere Routen durch den Dschungel, die vorher niemand kannte. Es macht Datenbanken schneller, indem es die "Rezepte" für die Datenabfragen intelligenter und effizienter macht.

Technische Zusammenfassung

Hier ist eine detaillierte technische Zusammenfassung des Papers „Efficient Query Rewrite Rule Discovery via Standardized Enumeration and Learning-to-Rank" (SLER) auf Deutsch:

1. Problemstellung

Die Abfrageoptimierung in Datenbanksystemen ist entscheidend für die Leistung, stößt jedoch bei der automatischen Entdeckung von Umschreibungsregeln (Query Rewrite Rules) an fundamentale Grenzen:

• Exponentieller Suchraum: Bestehende Methoden wie der State-of-the-Art-Engine WeTune verwenden einen Brute-force-Ansatz, um Paare von Abfrageplan-Templates zu enumerieren. Dies führt zu einer exponentiellen Komplexität, insbesondere bei komplexen Abfragen mit mehr als vier Knoten (Operatoren).
• Skalierbarkeitsprobleme: WeTune benötigt für Regeln mit vier Knoten bereits etwa 9 Tage Rechenzeit. Für 5-Knoten-Regeln wären Monate, für 6-Knoten-Regeln sogar Jahrzehnte erforderlich.
• Redundanz und Ineffizienz: Über 90 % der von WeTune generierten Regeln sind redundant, und mehr als 50 % der verbleibenden sind trivial (ohne echten Optimierungswert).
• Unzureichende Abdeckung: Da reale Produktionsabfragen (z. B. in PostgreSQL) oft 5 bis 8 Knoten oder mehr aufweisen, sind die aktuellen Regelbasen (limitiert auf ≤4 Knoten) für komplexe Szenarien unzureichend.
• Fehlerhafte Hypothesen: Der Versuch, komplexe Regeln durch die Komposition einfacherer Regeln abzuleiten („Small-to-Large"-Hypothese), hat sich als ineffektiv erwiesen (nur 9 % der komplexen Regeln lassen sich so zusammensetzen).

2. Methodik: Das SLER-System

SLER (Scalable Learning-to-Rank for Efficient Rewrite Rule Discovery) ist ein Framework, das drei Hauptkomponenten kombiniert, um effiziente und effektive Regeln zu entdecken:

A. Standardisierte Template-Enumeration (Rule Enumerator)

Statt alle möglichen Template-Paare zu prüfen, führt SLER eine Standardisierung durch:

• Kanonsche Struktur: Abfragepläne werden in eine standardisierte Form gebracht, indem Operatoren (z. B. Projektion, Filter) basierend auf einer definierten Priorität (Project > Distinct > Filter) sortiert oder entfernt werden.
• Redundanzfilterung: Wenn ein Template durch Standardisierung in ein anderes überführt werden kann, wird es als redundant markiert und nicht weiter verifiziert.
• Komplexitätsreduktion: Dieser Ansatz reduziert die Verifikationskomplexität für redundante Templates von exponentiell auf polynomial (O(1) für bestimmte Fälle), indem er die Anzahl der zu prüfenden Template-Paare drastisch senkt.

B. RTP-basierter Deduplizierer (Rule Deduplicator)

Um die Verifikationskosten weiter zu senken, wird der Reduce by Template Pair (RTP) Algorithmus eingesetzt:

• Inkrementelle Deduplizierung: Anstatt alle Regeln am Ende zu vergleichen, wird die Redundanzprüfung bereits während der Enumeration pro Template-Paar durchgeführt.
• Logik: Für ein Template-Paar wird eine lokale Regelbasis aufgebaut. Eine neu generierte Regel wird nur dann hinzugefügt, wenn sie die Optimierungsergebnisse im Vergleich zur bestehenden Basis verbessert. Dies verhindert unnötige Aufrufe von SMT-Solvern (wie Z3) für redundante Regeln.

C. Learning-to-Rank (Rule Ranker)

Da die vollständige Enumeration für sehr große Templates (≥7 Knoten) selbst mit Optimierungen zu aufwendig bleibt, nutzt SLER ein Machine-Learning-Modell (LambdaMART):

• Vorhersage: Das Modell bewertet Template-Paare basierend auf Merkmalen wie Baum-Distanz, Ausdruckskomplexität und Operator-Typen.
• Filterung: Es priorisiert die vielversprechendsten Template-Paare (Top-k). Nur diese werden zur vollständigen Regelgenerierung und Verifikation ausgewählt.
• Ziel: Dies ermöglicht eine skalierbare Exploration von komplexen Mustern (bis zu 10+ Knoten), indem der Suchraum intelligent eingeschränkt wird, ohne die Entdeckung effektiver Regeln zu gefährden.

3. Hauptbeiträge

1. Entkräftung der „Small-to-Large"-Hypothese: Der Nachweis, dass komplexe Regeln nicht einfach aus einfachen zusammengesetzt werden können, und die Einführung einer direkten, aber standardisierten Enumeration.
2. Standardisierte Regel-Enumeration: Ein Algorithmus, der Redundanzen durch strukturelle Normalisierung eliminiert und die Verifikationskomplexität signifikant senkt.
3. RTP-Deduplizierung: Ein neuer Algorithmus zur frühzeitigen Redundanzeliminierung während der Enumeration, der die Anzahl der SMT-Verifikationen minimiert.
4. Learning-to-Rank Mechanismus: Die Integration eines LambdaMART-Modells, um effektive Regeln aus riesigen Suchräumen zu filtern und skalierbare Entdeckung für große Templates (n ≥ 7) zu ermöglichen.
5. Skalierbare Regelbasis: Aufbau einer der bisher größten empirisch validierten Regelbibliotheken mit über 1 Million Regeln.

4. Ergebnisse und Evaluation

Die Evaluation erfolgte an über 11.000 realen SQL-Abfragen aus Open-Source- und kommerziellen Workloads (inkl. Yashan DB und GitHub-Projekte).

• Effizienz:
  • SLER ist bei kleinen Templates (2–4 Knoten) deutlich schneller als WeTune (bis zu 99 % Zeitersparnis bei der Deduplizierung).
  • Skalierbarkeit: Während WeTune bei 5-Knoten-Regeln „timeout" (Zeitüberschreitung) meldet, generiert SLER erfolgreich Regeln für 5 und 6 Knoten (in ca. 30 bzw. 395 Tagen für die vollständige Enumeration, aber praktikabel durch Filterung).
  • Durch den Ranker kann SLER auch 10-Knoten-Templates in unter 9 Stunden verarbeiten und dabei über 5.000 effektive Regeln finden.
• Effektivität:
  • SLER hat eine Regelbasis mit 679.316 neuen Regeln aufgebaut (fast 100-mal mehr als WeTune).
  • Die Regeln ermöglichen einstufige Optimierungen komplexer Abfragen, für die WeTune mehrere Schritte benötigt oder gar keine Lösung findet.
  • Top-Ranking: Die Top-500 Regeln von SLER erzielen eine durchschnittliche Leistungsverbesserung von 98,6 %, während die unteren 50 % nur 11,9 % bringen. Dies bestätigt die hohe Qualität des Ranking-Modells.
• End-to-End-Leistung: In Tests mit realen Abfragen zeigte SLER in Szenarien, die WeTune nicht optimieren konnte (z. B. tiefe Verschachtelungen, redundante Joins), signifikante Latenzreduktionen.

5. Bedeutung und Ausblick

SLER stellt einen Paradigmenwechsel in der automatischen Abfrageoptimierung dar:

• Überwindung der Skalierungsgrenze: Es macht die Entdeckung von Regeln für komplexe, reale Abfragen (5+ Knoten) erstmals praktikabel.
• Datengetriebene Optimierung: Durch den Einsatz von Learning-to-Rank wird die Abhängigkeit von rein mathematischen Beweisen (die bei komplexen Mustern oft scheitern) zugunsten einer datengetriebenen Priorisierung reduziert.
• Zukunftsfähigkeit: Das Framework ist erweiterbar und kann durch Hinzufügen neuer Operatoren (z. B. Aggregationen) an neue Workloads angepasst werden.
• Praktische Relevanz: Die entdeckten Regeln können direkt in Datenbanksysteme integriert werden, um die Leistung von ORM-generierten Abfragen und komplexen analytischen Workloads sofort zu verbessern.

Zusammenfassend löst SLER das Problem der kombinatorischen Explosion bei der Regelgenerierung durch eine Kombination aus struktureller Standardisierung, intelligenter Deduplizierung und maschinellem Lernen und ebnet den Weg für die nächste Generation adaptiver Datenbankoptimierer.