Abfrageverarbeitung und -optimierung
Abfrageverarbeitung und -optimierung ist der Teil eines Datenbanksystems, der eine deklarative Abfrage in einen effizienten Ausführungsplan umwandelt, indem er physische Operatoren und Zugriffspfade auswählt, um die Kosten über große Datensätze hinweg zu minimieren.
Definition
Abfrageverarbeitung ist die Menge von Aktivitäten, durch die ein Datenbanksystem eine Abfrage parst, optimiert und ausführt; Abfrageoptimierung ist die Suche nach einem Ausführungsplan mit geringen geschätzten Kosten unter den vielen Plänen, die logisch äquivalent zur Abfrage sind.
Scope
Dieser Bereich umfasst die Pipeline von einer geparsten Abfrage bis zu den Ergebnissen: die Übersetzung von SQL in relational-algebraische Ausdrücke, die physischen Operatoren, die jede algebraische Operation implementieren (Scans, Joins, Sortierung, Aggregation), die Indizes und Zugriffsmethoden, die schnelle Pfade zu Daten bereitstellen, und den kostenbasierten Optimierer, der Statistiken verwendet, um zwischen äquivalenten Plänen zu wählen. Ausgenommen sind Transaktions- und Parallelitätskontrolle sowie das Design von Schemata; der Fokus liegt darauf, wie eine einzelne Abfrage effizient ausgewertet wird.
Sub-topics
Core questions
- Wie wird eine deklarative Abfrage in einen Baum physischer Operatoren übersetzt?
- Welche physikalischen Algorithmen implementieren Selektion, Join, Sortierung und Aggregation?
- Wie beschleunigen Indizes und Zugriffsmethoden den Datenabruf?
- Wie schätzt ein kostenbasierter Optimierer die Plankosten und wählt zwischen Plänen?
- Warum können sich logisch äquivalente Abfragen in den Ausführungskosten enorm unterscheiden?
Key concepts
- physischer Abfrageplan
- relational-algebraische Äquivalenzen
- Join-Algorithmen
- Sortierung und externer Mergesort
- Indizes und Zugriffsmethoden
- Selektivitäts- und Kardinalitätsschätzung
- Kostenmodell
- Join-Reihenfolge-Enumeration
- Pipelining und Materialisierung
Key theories
- Logische zu physische Plangenerierung
- Eine Abfrage wird zunächst unter Verwendung relational-algebraischer Äquivalenzen in Kandidaten für logische Pläne umgeschrieben, dann wird jeder algebraische Operator einem physischen Algorithmus zugeordnet, wodurch ausführbare Pläne entstehen, deren Kosten verglichen werden können.
- Kostenbasierte Optimierung
- Der Optimierer verwendet Statistiken über Tabellengrößen und Wertverteilungen, um die Kosten alternativer Pläne – insbesondere Join-Reihenfolgen und Zugriffspfade – zu schätzen und wählt den günstigsten aus, ein Ansatz, der vom Optimierer von System R entwickelt wurde.
- Zugriffspfadauswahl
- Die Entscheidung, ob eine Tabelle gescannt, ein Index verwendet oder Clustering für jede Operation genutzt werden soll, ist entscheidend für die Leistung; der Optimierer wägt Selektivitätsschätzungen und E/A-Kosten ab, um den besten Zugriffspfad zu wählen.
Clinical relevance
Abfrageoptimierung ist das, was relationale Datenbanken in großem Maßstab nutzbar macht: Dieselbe SQL-Abfrage kann je nach gewähltem Plan in Millisekunden oder Stunden ausgeführt werden, sodass die Qualität des Optimierers die Leistung von Geschäftsanalysen, Transaktionsverarbeitung und datenintensiven Anwendungen direkt bestimmt.
History
Der kostenbasierte Optimierer von IBMs System R (Selinger et al., 1979) etablierte den dominanten Ansatz: Pläne aufzählen, Kosten aus Statistiken schätzen und dynamische Programmierung für die Join-Reihenfolge verwenden. Jahrzehntelange Verfeinerungen fügten bessere Kardinalitätsschätzung, neue Operatoren und adaptive Techniken hinzu, aber der grundlegende Rahmen bleibt die Grundlage moderner Abfrageoptimierer.
Debates
- Zuverlässigkeit der Kardinalitätsschätzung
- Kostenbasierte Optimierer hängen von Schätzungen der Größen von Zwischenergebnissen ab, die bei korrelierten oder schiefen Daten stark falsch sein können; Forscher diskutieren, wie viel in bessere Statistiken und gelernte Schätzer im Vergleich zu adaptiver, Laufzeit-Re-Optimierung investiert werden sollte.
Key figures
- Patricia Selinger
- Jeffrey D. Ullman
- Michael Stonebraker
Related topics
Seminal works
- selinger1979
- garciamolina2008
- silberschatz2019
Frequently asked questions
- Warum läuft dieselbe Abfrage auf einem System schnell und auf einem anderen langsam?
- Die Leistung hängt vom Ausführungsplan ab, den der Optimierer wählt, was wiederum von verfügbaren Indizes, Statistiken über die Daten und dem Kostenmodell abhängt. Verschiedene Systeme oder dasselbe System mit veralteten Statistiken können sehr unterschiedliche Pläne wählen – zum Beispiel eine andere Join-Reihenfolge oder einen Index-Scan anstelle eines vollständigen Tabellen-Scans.
- Was ist der schwierigste Teil der Abfrageoptimierung?
- Die genaue Schätzung der Größen von Zwischenergebnissen (Kardinalitätsschätzung). Fehler summieren sich über Joins hinweg, sodass eine kleine Fehleinschätzung früh in einem Plan dazu führen kann, dass der Optimierer eine drastisch schlechtere Join-Reihenfolge oder einen schlechteren Zugriffspfad wählt. Dies ist der Grund, warum die Kardinalitätsschätzung ein aktives Forschungsproblem bleibt.