TU Darmstadt / ULB / TUprints

Data-Efficient Learned Database Components

Hilprecht, Benjamin (2022)
Data-Efficient Learned Database Components.
Technische Universität Darmstadt
doi: 10.26083/tuprints-00022531
Ph.D. Thesis, Primary publication, Publisher's Version

[img] Text
Dissertation_Hilprecht.pdf
Copyright Information: CC BY 4.0 International - Creative Commons, Attribution.

Download (2MB)
Item Type: Ph.D. Thesis
Type of entry: Primary publication
Title: Data-Efficient Learned Database Components
Language: English
Referees: Binnig, Prof. Dr. Carsten ; Trummer, Prof. Dr. Immanuel
Date: 2022
Place of Publication: Darmstadt
Collation: xxiii, 260 Seiten
Date of oral examination: 18 October 2022
DOI: 10.26083/tuprints-00022531
Abstract:

While databases are the backbone of many software systems, database components such as query optimizers often have to be redesigned to meet the increasing variety in workloads, data and hardware designs, which incurs significant engineering efforts to adapt their design. Recently, it was thus proposed to replace DBMS components such as optimizers, cardinality estimators, etc. by ML models, which not only eliminates the engineering efforts but also provides superior performance for many components.

The predominant approach to derive such learned components is workload-driven learning where ten thousands of queries have to be executed first to derive the necessary training data. Unfortunately, the training data collection, which can take days even for medium-sized datasets, has to be repeated for every new database (i.e., the combination of dataset, schema and workload) a component should be deployed for. This is especially problematic for cloud databases such as Snowflake or Redshift since this effort has to be incurred for every customer.

This dissertation thus proposes data-efficient learned database components, which either reduce or fully eliminate the high costs of training data collection for learned database components. In particular, three directions are proposed in this dissertation, namely (i) we first aim to reduce the number of training queries needed for workload-driven components before we (ii) propose data-driven learning, which uses the data stored in the database as training data instead of queries, and (iii) introduce zero-shot learned components, which can generalize to new databases out-of-the-box, s.t. no training data collection is required.

First, we strive to reduce the number of training queries required for workload-driven components by using simulation models to convey the basic tradeoffs of the underlying problem, e.g., that in database partitioning the network costs of shuffling tuples over the network for joins is the dominating factor. This substantially reduces the number of training queries since the basic principles are already covered by the simulation model and thus only subtleties not covered in the simulation model have to be learned by observing query executions, which we will demonstrate for the problem of database partitioning. An alternative direction is to incorporate domain knowledge (e.g., in a cost model we could encode that scan costs increase linearly with the number of tuples) into components by designing them using differentiable programming. This significantly reduces the number of learnable parameters and thus also the number of required training queries. We demonstrate the feasibility of the approach for the problem of cost estimation in databases. While both approaches reduce the number of training queries, there is still a significant number of training queries required for unseen databases.

This motivates our second approach of data-driven learning. In particular, we propose to train the database component by learning the data distribution present in a database instead of observing query executions. This not only completely eliminates the need to collect training data queries but can even improve the state-of-the-art in problems such as cardinality estimation or AQP. While we demonstrate the applicability to a wide range of additional database tasks such as the completion of incomplete relational datasets, data-driven learning is only useful for problems where the data distribution provides sufficient information for the underlying database task. However, for tasks where observations of query executions are indispensable such as cost estimation, data-driven learning cannot be leveraged.

In a third direction, we thus propose zero-shot learned database components, which are applicable to a broader set of tasks including those that require observations of queries. In particular, motivated by recent advances in transfer learning, we propose to pretrain a model once on a variety of databases and workloads and thus allow the component to generalize to unseen databases out-of-the-box. Hence, similar to data-driven learning no training queries have to be collected. In this dissertation, we demonstrate that zero-shot learning can indeed yield learned cost models which can predict query latencies on entirely unseen databases more accurately than state-of-the-art workload-driven approaches, which require ten thousands of query executions on every unseen database.

Overall, the proposed techniques yield state-of-the-art performance for many database tasks while significantly reducing or completely eliminating the expensive training data collection for unseen databases. However, while the proposed directions address the prevalent data-inefficiency of learned database components, there are still many opportunities to improve learned components in the future. First, the robustness and debuggability of learned components should be improved since as of today they do not offer the same transparency as standard code in databases, which can render the components less attractive to be deployed in production systems. Moreover, to increase the applicability of data-driven models it is desirable to increase the coverage of supported queries, e.g., queries involving wildcard predicates on string columns, which are currently not supported by data-driven learning. Finally, we envision that a broader set of tasks should be supported in the future by zero-shot models (e.g., query optimization) potentially converging towards complete zero-shot learned systems.

Alternative Abstract:
Alternative AbstractLanguage

Während Datenbanken das Fundament vieler Softwaresysteme bilden, müssen Datenbankkomponenten wie Anfrageoptimierer häufig neu entworfen werden, um der zunehmenden Vielfalt an Arbeitslasten, Daten und Hardwaredesigns gerecht zu werden, was einen erheblichen technischen Aufwand für die Anpassung ihres Designs bedeutet. Vor kurzem wurde daher vorgeschlagen, DBMS-Komponenten wie Optimierer, Kardinalitätsschätzer etc. durch ML-Modelle zu ersetzen, wodurch nicht nur der Entwicklungsaufwand entfällt, sondern auch eine bessere Leistung für viele Komponenten erzielt wird.

Der vorherrschende Ansatz zur Erstellung solcher gelernten Komponenten ist das Workload-getriebene Lernen, bei dem zunächst zehntausende Abfragen ausgeführt werden müssen, um die erforderlichen Trainingsdaten zu erhalten. Leider muss die Erhebung von Trainingsdaten, die selbst für mittelgroße Datensätze Tage dauern kann, für jede neue Datenbank (d. h. Kombination aus Datensatz, Schema und Arbeitslast) wiederholt werden. Dies ist vor allem bei Cloud-Datenbanken wie Snowflake oder Redshift problematisch, da dieser Aufwand für jeden Kunden anfällt.

In dieser Dissertation werden daher dateneffiziente gelernte Datenbankkomponenten vorgeschlagen, die die hohen Kosten der Trainingsdatenerhebung für gelernte Datenbankkomponenten entweder reduzieren oder ganz eliminieren. Insbesondere werden in dieser Dissertation drei Richtungen vorgeschlagen, nämlich zielen wir (i) zunächst darauf ab, die Anzahl der benötigten Trainingsabfragen für Workload-getrieben Komponenten zu reduzieren, bevor wir (ii) datengetriebenes Lernen vorschlagen, das die in der Datenbank gespeicherten Daten als Trainingsdaten anstelle von Abfragen verwendet, und (iii) gelernte Zero-Shot-Komponenten einführen, die out-of-the-Box auf neue Datenbanken verallgemeinert werden können, d.h. bei denen keine Trainingsdatenerfassung erforderlich ist.

Zunächst haben wir als Ziel, die Anzahl der für Workload-getriebene Komponenten erforderlichen Trainingsabfragen zu reduzieren, indem wir Simulationsmodelle verwenden, um die grundlegenden Effekte des zugrunde liegenden Problems zu vermitteln, z.B. dass bei der Datenbankpartitionierung die Netzwerkkosten für das Verteilen von Tupeln über das Netzwerk für Joins der dominierende Faktor sind. Dies reduziert die Anzahl der Trainingsabfragen erheblich, da die grundlegenden Prinzipien bereits durch das Simulationsmodell abgedeckt sind und somit nur noch die Feinheiten, die nicht durch das Simulationsmodell erfasst sind, durch Beobachtung von Abfrageausführungen erlernt werden müssen, was wir für das Problem der Datenbankpartitionierung demonstrieren werden. Eine alternative Richtung ist, Domänenwissen (z.B. könnten wir in einem Kostenmodell kodieren, dass die Scankosten linear mit der Anzahl der Tupel ansteigen) in die Komponenten einzubauen, indem wir sie mit differenzierbarer Programmierung entwerfen. Dies reduziert die Anzahl der lernbaren Parameter und damit auch die Anzahl der erforderlichen Trainingsabfragen erheblich. Wir demonstrieren die Machbarkeit des Ansatzes für das Problem der Kostenabschätzung in Datenbanken. Obwohl beide Ansätze die Anzahl der Trainingsabfragen reduzieren, ist immer noch eine erhebliche Anzahl von Trainingsabfragen für ungesehene Datenbanken erforderlich.

Dies motiviert unseren zweiten Ansatz des datengetriebenen Lernens. Wir schlagen insbesondere vor, die Datenbankkomponente zu trainieren, indem wir die Datenverteilung in einer Datenbank lernen, anstatt die Ausführung von Abfragen zu beobachten. Dies macht nicht nur das Sammeln von Trainingsdaten überflüssig, sondern kann sogar den Stand der Technik bei Problemen wie der Kardinalitätsschätzung oder AQP verbessern. Während wir die Anwendbarkeit auf eine breite Auswahl zusätzlicher Datenbankaufgaben wie die Vervollständigung unvollständiger relationaler Datensätze demonstrieren, ist datengetriebenes Lernen nur für Probleme nützlich, bei denen die Datenverteilung ausreichende Informationen für die zugrunde liegende Datenbankaufgabe liefert. Für Aufgaben, bei denen Beobachtungen von Abfrageausführungen unverzichtbar sind, wie z.B. bei der Kostenschätzung, kann datengetriebenes Lernen jedoch nicht genutzt werden.

In einer dritten Richtung schlagen wir daher Zero-Shot-gelernte Datenbankkomponenten vor, die auf eine breitere Palette von Aufgaben anwendbar sind, einschließlich solcher, die Beobachtungen von Abfragen erfordern. Motiviert durch die jüngsten Fortschritte im Transfer-Lernen schlagen wir vor, ein Modell einmalig auf einer Vielzahl von Datenbanken und Arbeitslasten vorzutrainieren und so der Komponente zu ermöglichen, sofort auf unbekannte Datenbanken zu generalisieren. Ähnlich wie beim datengesteuerten Lernen müssen also keine Trainingsabfragen gesammelt werden. In dieser Dissertation zeigen wir, dass Zero-Shot-Learning tatsächlich gelernte Kostenmodelle hervorbringen kann, die Abfragelatenzen auf gänzlich unbekannten Datenbanken genauer vorhersagen können als moderne Workload-getriebene Ansätze, die zehntausende von Abfrageausführungen auf jeder unbekannten Datenbank erfordern.

Insgesamt liefern die vorgeschlagenen Verfahren für viele Datenbankaufgaben eine Leistung auf dem neuesten Stand der Technik, während die teure Erhebung von Trainingsdaten für unbekannte Datenbanken erheblich reduziert oder ganz vermieden wird. Während die vorgeschlagenen Richtungen die vorherrschende Datenineffizienz von gelernten Datenbankkomponenten adressieren, gibt es jedoch noch viele Möglichkeiten, gelernte Komponenten in Zukunft zu verbessern. Erstens sollten die Robustheit und die Debugging-Fähigkeit der gelernten Komponenten verbessert werden, da sie derzeit nicht die gleiche Transparenz wie Standardcode in Datenbanken bieten, was die Komponenten für den Einsatz in Produktionssystemen weniger attraktiv machen kann. Um die Anwendbarkeit von datengetriebenen Modellen zu erhöhen, ist es außerdem wünschenswert, die Abdeckung der unterstützten Abfragen zu erhöhen, z.B. Abfragen mit Wildcard-Prädikaten auf String-Spalten, die derzeit nicht von datengetriebenem Lernen unterstützt werden. Schließlich könnten in Zukunft viele weitere Aufgaben durch Zero-Shot-Modelle unterstützt werden (z.B. Abfrageoptimierung), was vollständige Zero-Shot-gelernte Systemen ermöglichen könnte.

German
Status: Publisher's Version
URN: urn:nbn:de:tuda-tuprints-225311
Classification DDC: 000 Generalities, computers, information > 004 Computer science
Divisions: 20 Department of Computer Science > Data Management (2022 umbenannt in Data and AI Systems)
Date Deposited: 21 Oct 2022 12:02
Last Modified: 15 Jun 2023 13:37
URI: https://tuprints.ulb.tu-darmstadt.de/id/eprint/22531
PPN: 500716323
Export:
Actions (login required)
View Item View Item