Auf dem Weg zu einem lernbasierten Abfrageoptimierer

Die Abfrageoptimierung ist das Herzstück jedes Datenmanagement-/Analysesystems. Es ist der Prozess, bei dem bestimmt wird, wie eine Eingabeabfrage oder Aufgabe (d. h. ein Ausführungsplan) am besten ausgeführt werden kann. Die Abfrageoptimierung besteht aus mehreren drei Unterprozessen: (i) Die Aufzählung der verschiedenen Ausführungspläne, (ii) die Kosten von jedem Teilplan, der erforderlich ist, um zu bestimmen, welcher der beste ist, (iii) der Kardinalitätsschätzung von Teilplänen (d. h. wie viele Tupel ein Teilplan ausgeben wird), was entscheidend ist, da es sich auf die Kosten des Plans auswirkt. Neuere Forschungen auf dem Gebiet des Datenmanagements haben begonnen, die Möglichkeiten des maschinellen Lernens (ML) zu nutzen, um diese Aufgaben effektiver und effizienter zu lösen. In diesem Blogbeitrag konzentrieren wir uns auf die Verwendung von ML zur Schätzung der Kosten von Teilplänen.

Herkömmliche Optimierer verfügen über ein Kostenmodell. Dabei handelt es sich um mathematische Formeln, die die Kosten der einzelnen Operatoren kodieren und diese Kosten aggregieren, um die Kosten eines Abfrageplans abzuschätzen. Die Entwicklung eines Kostenmodells in einer Verbundumgebung, für die Blossom entwickelt wurde, ist jedoch nicht nur eine große Herausforderung, sondern kann auch zu einer suboptimalen Leistung führen. Dafür gibt es mehrere Gründe: (i) Kostenbasierte Optimierer gehen von linearen Funktionen aus, die das reale Systemverhalten nicht abbilden, (ii) sie benötigen Zugriff auf Statistiken, die auf den verschiedenen Plattformen gespeichert sind, was möglicherweise nicht möglich ist, und (iii) sie benötigen eine Feinabstimmung, um das Systemverhalten wirklich zu modellieren, was sehr zeitaufwändig, aber sehr wichtig sein kann. Das folgende Diagramm zeigt eine um bis zu einer Größenordnung bessere Leistung mit einem gut abgestimmten Kostenmodell.

‍

‍

Ein gut abgestimmter kostenbasierter Optimierer in einer föderierten Umgebung kann zu einer um eine Größenordnung besseren Leistung führen. Es ist jedoch sehr mühsam und zeitaufwändig.

‍

Die Optimierung eines Kostenmodells kann sehr mühsam und zeitaufwändig sein. Aus diesem Grund erwägen wir, die mathematischen Formeln des Kostenmodells, die die Systemleistung modellieren, durch ein ML-Modell zu ersetzen, das die Laufzeit eines (Teil-) Plans vorhersagt. Das klingt zwar trivial, bringt aber zwei Hauptherausforderungen mit sich, die wir im Folgenden analysieren.

Zunächst erstellt der Aufzählungsprozess Tausende oder Millionen von Abfrageplänen, und wir müssen wissen, wie kostspielig sie sind. Dazu müssen wir jeden einzelnen von ihnen in das ML-Modell einspeisen. Es gibt jedoch ein“ Impedanzfehlanpassung“: Die Abfragepläne sind normalerweise Objekte oder Strukturen, während die Eingabe des ML-Modells ein numerischer Vektor (Merkmale) ist. Daher müssen wir jeden aufgezählten Plan in einen Merkmalsvektor umwandeln. Diese Plantransformationen können aufgrund der exponentiellen Größe des Aufzählungs-Suchraums leicht in der Größenordnung von Millionen liegen, was zu einem hohen Zeitaufwand bei der Abfrageoptimierung führt. Beachten Sie, dass die Abfrageoptimierung zur Abfragelaufzeit erfolgt und ein kleines Fragment (oft in ms) der Abfragelaufzeit sein muss.

Die zweite Herausforderung bei der Verwendung eines ML-Modells zur Schätzung der Plankosten besteht darin, dass Trainingsdaten, d. h. Abfragen von Plänen mit ihrer Laufzeit, erforderlich sind, um ein solches Modell erstellen zu können. Wir haben bereits in unserem vorherigen Beitrag besprochen, wie wir mithilfe von DataFarm Trainingsdaten effizient generieren können. Mit DataFarm waren wir in der Lage, qualitativ hochwertige Trainingsdaten in nur 4 Stunden zu erhalten, während der naive Ansatz, alle Abfragepläne auszuführen, um ihr Label zu erhalten, 40 Stunden in Anspruch nahm!

Um die erste Herausforderung zu lösen, haben wir vorgeschlagen, unsere Aufzählungsalgorithmen komplett neu zu gestalten, um Operationen mit Vektoren durchführen zu können [1]. Aus diesem Grund haben wir eine vektorbasierte Planaufzählung entwickelt und schlagen damit zwei Fliegen mit einer Klappe: Wir vermeiden die kontinuierliche Plantransformation und können primitive Operationen und SIMD (Single Instruction Multiple Data) nutzen, um mehrere Vektoroperationen mit einer einzigen CPU-Instruktion durchzuführen (vektorisierte Ausführung), was den Abfrageoptimierungsprozess weiter beschleunigt. Die folgende Abbildung zeigt den Verbesserungsfaktor bei der Abfrageoptimierung durch die Verwendung von Vektoren mit einem ML-basierten Optimierer.

‍

Ein vektorbasierter Planaufzählungsansatz kann zu einer erheblichen Verbesserung der Abfrageoptimierungszeit für einen ML-basierten Optimierer führen.

Angesichts einer Reihe von vektorbasierten Operationen können wir eine effiziente vektorbasierte Planaufzählung definieren. Die folgende Abbildung zeigt die allgemeine Architektur eines ML-basierten Optimierers mit einer vektorbasierten Planaufzählung. Der logische Plan wird als Eingabe an den Optimierer übergeben, der den Plan zunächst in einen Vektor umwandelt. Anschließend erfolgt eine vektorgestützte Aufzählung und Bereinigung, wobei bei der Bereinigung ineffizienter Pläne auch das ML-Modell verwendet wird. Der billigste (d. h. effizienteste) Planvektor wird ausgegeben und dann in einen Ausführungsplan umgewandelt, den das System tatsächlich ausführen kann.

‍

Ein lernbasierter Optimierer kann zu signifikanten Ergebnissen führen. Nachfolgend finden Sie unsere vorläufigen Ergebnisse. Für k-means kann ein ML-basierter Optimierer bessere Pläne auswählen und Folgendes erreichen 7x bessere Laufzeit Leistung als ein hochoptimierter kostenbasierter Optimierer!

‍

Wir arbeiten derzeit daran, diese Architektur in den Optimierer von Blossom zu integrieren. Dies wird nicht nur die Zeit für die Abfrageoptimierung beschleunigen, sondern auch zu besseren Ausführungsplänen führen, was schnellere Ausführungslaufzeiten bedeutet. Bleiben Sie dran! ‍

‍

Referenzen

[1] Zoi Kaoudi, Jorge-Arnulfo Quiané-Ruiz, Bertty Contreras-Rojas, Rodrigo Pardo-Meza, Anis Troudi, Sanjay Chawla: ML-basierte plattformübergreifende Abfrageoptimierung. ICDE 2020:1489-1500.

‍