Das fehlende Stück in der lernbasierten Abfrageoptimierung

Maschinelles Lernen (ML) ist nicht nur in unserem Alltag allgegenwärtig geworden (mit selbstfahrenden Autos, digitalen persönlichen Assistenten, Chatbots usw.), sondern hat auch begonnen, sich auf unsere technologischen Kernsysteme wie Datenbanken und Betriebssysteme auszubreiten. Im Bereich der Datenbanken wird viel an der Optimierung der Datenverwaltungskomponenten gearbeitet, von der Indexbildung über die Knob-Tuning bis hin zur Abfrageoptimierung. Gerade bei der Abfrageoptimierung wird ML anstelle vieler Optimierungskomponenten wie Kardinalitätsschätzung, Kostenmodellierung und Join-Enumeration verwendet. In diesem Blogbeitrag konzentrieren wir uns auf den Fall der Verwendung eines ML anstelle eines Kostenmodells und gehen von der traditionellen kostenbasierten Abfrageoptimierung zur neu vorgeschlagenen ML-basierten Abfrageoptimierung über.

‍

ML-basierte Abfrageoptimierung

Im Allgemeinen findet ein Abfrageoptimierer bei einer Benutzerabfrage den besten Weg, diese Abfrage auszuführen (d. h. einen Ausführungsplan), sodass die Laufzeit minimiert wird. Zum Beispiel Blossom Sky's Der Abfrageoptimierer ist dafür verantwortlich, herauszufinden, welche Plattformkombination führt eine Abfrage am besten so aus, dass die Laufzeit der angegebenen Abfrage so gering wie möglich ist. Zu diesem Zweck verwenden herkömmliche kostenorientierte Optimierer eine Kostenmodell (eine Reihe mathematischer Formeln), die die Kosten für die Ausführung eines Plans und eine Aufzählungsalgorithmus das nach verschiedenen Plänen sucht, bis es das mit den geringsten Kosten findet. Beim Übergang von einem kostenbasierten Abfrageoptimierer zu einem ML-basierten Modell wird das Kostenmodell durch ein ML-Modell (normalerweise ein Regressionsmodell) ersetzt, das eine Schätzung der Laufzeit eines Plans ausgibt [1]. Dann ruft der Aufzählungsalgorithmus einfach das ML-Modell auf, während er verschiedene Pläne durchsucht, um den Plan mit der niedrigsten Laufzeitschätzung auf der Grundlage des ML-Modells zu ermitteln.

Die Hürde der Trainingsdatenerfassung

Es ist inzwischen bekannt, dass ML-Modelle so gut sein können wie ihre Trainingsdaten. Bei der ML-basierten Abfrageoptimierung ist es genauso:

„Die Effektivität eines ML-basierten Abfrageoptimierers hängt in hohem Maße von der Quantität und Qualität der Trainingsdaten sowie von der Verfügbarkeit wertvoller Ground-Truth-Labels ab. “

In diesem Fall enthält ein Trainingsdatensatz eine große Menge von Abfrageplänen zusammen mit ihrer Laufzeit, die als Bezeichnung dient. Die Erfassung von Trainingsdaten stellt einen Engpass dar, da dafür (i) Tausende heterogener Abfragepläne gesammelt und (ii) alle ausgeführt werden müssen, um ihre Laufzeit zu erhalten. Letzteres ist eine sehr zeitaufwändige Aufgabe, da es nicht nur zur Ausführung einer großen Anzahl von Plänen, sondern auch zu suboptimalen Plänen führt. Um eine bessere Vorstellung davon zu bekommen, wie viel Zeit benötigt wird, um diese Beschriftungen zu erhalten, sehen Sie sich die beiden folgenden Abbildungen an. Das Sammeln von Labels für nur 500 OLAP-Pläne mit Eingabedaten von etwa 1 TB in unserem Cluster mit vier Quad-Core-Nodes dauert fast 10 Tage, während die Ausführung von 10.000 Plänen mit nur 1 GB an Daten etwas mehr als 4 Tage in Anspruch nimmt. Wenn wir das auf 10.000 Pläne mit 1 TB an Daten hochrechnen, würde das mehr als 6 Monate dauern!

‍

‍

‍

Die Ausführung von 10.000 Plänen mit 1 TB an Daten zur Erfassung ihrer Labels würde mehr als 6 Monate in Anspruch nehmen!

Selbst wenn Protokolle von zuvor ausgeführten Abfragen verfügbar sind, sind die Pläne in den Protokollen diejenigen, für deren Ausführung der Optimierer ausgewählt hat, und daher sind die meisten von ihnen (nahezu) optimal. Das Trainieren eines Modells mit nur optimalen Plänen würde zu einem verzerrten Modell führen.

DataFarm: Generativer Trainingsdatengenerator für ML-basierte Abfrageoptimierer

DataFarm [2] ist ein Framework zur effizienten Generierung von Trainingsdaten (Abfragepläne mit ihrer Ausführungslaufzeit).

DataFarm ermöglicht es Benutzern, die Kosten für Labelabfrage-Workloads im Vergleich zu herkömmlichen manuellen Ansätzen um das 54-fache zu reduzieren.

Es basiert auf einem datengesteuerten White-Box-Ansatz. Ein Benutzer gibt einen typischerweise sehr kleinen Satz von Abfrageplänen ein (z. B. 10), und DataFarm erweitert ihn, um zu Tausenden von Plänen zu gelangen, und fügt jedem generierten Plan Beschriftungen (zur Laufzeit) mit Unsicherheitswerten hinzu. Die folgende Abbildung zeigt einen Überblick über DataFarm.

‍

Der Abstract Plan Generator lernt Muster aus der Eingabeabfrage-Workload als Markov-Ketten und generiert neue heterogene abstrakte Pläne (Pläne ohne spezifische UDF-Werte), wobei die Verteilungen der realen Operatoren ausgenutzt werden. Diese Pläne folgen den im Eingabe-Workload angegebenen Mustern. Wenn beispielsweise im Eingabe-Workload in den meisten Fällen ein Operator „Nach gruppieren“ einem Sortieroperator vorausgeht, gilt dasselbe für die generierten Pläne. Die in dieser Phase generierten abstrakten Pläne können noch nicht ausgeführt werden, da ihre Operatoren weder benutzerdefinierte Werte wie den Join-Schlüssel oder das Auswahlprädikat noch die Plattform angeben, auf der sie ausgeführt werden müssen.

Der Planinstantiator empfängt dann die generierten abstrakten Pläne und erstellt einen erweiterten Satz ausführbarer Pläne, indem er für jeden abstrakten Plan verschiedene Varianten instanziiert, z. B. indem unterschiedliche Auswahlprädikate gesetzt werden. Um dies zu erreichen, nutzt er die Metadaten der Eingabedaten des Benutzers. Dies ist entscheidend, damit die generierten Pläne aussagekräftig sind und tatsächlich ohne Ausnahmen oder leere Ergebnisse ausgeführt werden können.

Sobald wir die generierten Pläne haben, verwendet der Label Forecaster einen aktiven Lernansatz, um den generierten Abfrage-Workload effizient zu kennzeichnen. Er führt nur einige der generierten Pläne aus und prognostiziert die Labels der übrigen Pläne mit einem interpretierbaren ML-Modell, das auf einer Quantil-Regressionsforst basiert. Es nutzt iterativ die Unsicherheit des Modells aus, um eine kleine Anzahl von auszuführenden Jobs auszuwählen, und gibt die prognostizierten Labels für die nicht ausgeführten Jobs zusammen mit ihren Unsicherheitswerten aus. Nachgelagerte Betriebe können diese Unsicherheitswerte dann nutzen, um ihre Leistung zu verbessern, z. B. indem sie sie als Geräuschindikator verwenden.

‍

Von Menschen gesteuerte Generierung von Trainingsdaten

Da Benutzer oft wissen, welchen Workload sie für Abfragen benötigen, haben wir Menschen in den aktiven Lernschritt des Label Forecaster eingeführt. Dies führt zu einer Steigerung der Qualität der Trainingsdaten und damit des nachgelagerten ML-Modells. Der Mensch gibt dem Label Forecaster Einblicke in die Frage, welche Jobs besser ausgeführt werden können, um eine bessere Schätzung der Etiketten zu erhalten. Da Menschen allein nicht manuell aus Tausenden von Plänen auswählen können, schlägt der Label Forecaster dem Benutzer iterativ eine kleine Gruppe von Plänen vor, die zur Ausführung in Frage kommen. Anschließend kann der Benutzer diese Kandidaten überprüfen und über eine intuitive grafische Benutzeroberfläche (GUI) Pläne entfernen oder neue hinzufügen. Die GUI von DataFarm bietet nützliche Einblicke, wie z. B. die Bedeutung von Merkmalen und die Analyse der Modellerklärungen, sodass die Benutzer fundierte Entscheidungen treffen können [3].

‍

Ergebnisse

Um die Qualität der Trainingsdaten von DataFarm zu bewerten, haben wir aus nur 6 ersten Abfragen 2000 Pläne generiert. Wir konstruieren vier Trainingssätze, die sich im Prozess der Erfassung der Bezeichnungen unterscheiden: Der erste Trainingssatz enthält Ground-Truth-Labels, die wir nach der Ausführung aller Jobs erhalten, während die anderen drei Labels enthalten, die ausgeführt werden sollen, indem wir 166 auszuführende Jobs auswählen und das ML-Modell des Label Forecaster verwenden, um die Bezeichnungen der übrigen vorherzusagen. Wir verwendeten drei verschiedene Probenahmemechanismen: (i) zufälliges, (ii) agglomeratives Clustering (DATAFARM ohne den Menschen) und (iii) manuelles Modifizieren des durch das agglomerative Clustering vorgeschlagenen Satzes (DATAFARM mit dem Menschen). Basierend auf diesen vier Trainingssätzen erstellen wir jeweils vier ML-Modelle und prognostizieren anhand jedes Modells die Laufzeiten unserer Eingabeabfragen. Die Ergebnisse sind unten dargestellt.

‍

Wir stellen fest, dass die Qualität der von DataFarm generierten Trainingsdaten so gut ist wie die Realität (grüne bzw. blaue Balken). Am wichtigsten ist, dass wir das beobachten

DataFarms für generatives KI-Training mit menschlicher Interaktion und verstärktem Lernen übertrifft DataFarms mit Autark- und Selbsttraining sowie das Ground-Truth-Modell.

Dieses Ergebnis ist möglich, weil die Benutzerin die wesentlichen Merkmale für das ML-Modell bestimmen und entsprechend ihren Beobachtungen Änderungen vornehmen kann (Hinzufügen und Entfernen von Jobs).

‍

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.
[2] Francesco Ventura, Zoi Kaoudi, Jorge-Arnulfo Quiané-Ruiz, Volker Markl: Erweitere deine Trainingsgrenzen! Generierung von Trainingsdaten für ML-basiertes Datenmanagement. SIGMOD-Konferenz 2021:1865-1878.
[3] Robin P. van de Water, Francesco Ventura, Zoi Kaoudi, Jorge Arnulfo Quiane Ruiz, Volker Markl: Farmen Sie die Nahrung Ihres ML-basierten Abfrageoptimierers! — Generierung von Trainingsdaten durch den Menschen —. CIDR 2022 (Zusammenfassung).
[4] Robin P. van de Water, Francesco Ventura, Zoi Kaoudi, Jorge Arnulfo Quiane Ruiz, Volker Markl: Farming Your ML-based Query Optimizer's Food ICDE 2022 (Demo), wird erscheinen.