Abfrageausführungsoperatoren

Abfrageausführungsoperatoren sind die physikalischen Algorithmen – Scans, Selektionen, Projektionen, Sortierungen, Aggregationen und Joins –, die eine Datenbank-Engine zu einem Plan zusammensetzt und ausführt, um das Ergebnis einer Abfrage zu erzeugen.

Definition

Ein Abfrageausführungsoperator ist eine Implementierung einer relationalen Algebraoperation als Algorithmus über Tupelströme; Operatoren werden zu einem Baum oder einer Pipeline zusammengesetzt, die bei Ausführung das Ergebnis einer Abfrage berechnet.

Scope

Dieses Thema behandelt die physikalischen Operatoren einer Abfrage-Engine und deren Organisation für die Ausführung: das Iterator-Modell (open-next-close), Pipelining versus Materialisierung, Tabellen- und Index-Scans, Selektion und Projektion, externes Mergesort, Gruppierung und Aggregation sowie Duplikatseliminierung. Es wird behandelt, wie Operatoren Tupelströme konsumieren und produzieren und wie Speicher und E/A deren Kosten beeinflussen. Spezifika von Join-Algorithmen und der Optimierer, der zwischen Operatoren wählt, werden als angrenzende Themen ausgeschlossen.

Core questions

• Wie ermöglicht das Iterator-Modell (open-next-close) die Zusammensetzung von Operatoren zu einer Pipeline?
• Wann wird ein Ergebnis gepipelined versus auf die Festplatte materialisiert?
• Wie werden Selektion, Projektion und Duplikatseliminierung physikalisch implementiert?
• Wie verarbeitet externes Mergesort Daten, die größer als der Speicher sind?
• Wie beeinflussen Speicherbudget und E/A-Kosten die Operatorleistung?

Key concepts

• Iterator / Open-Next-Close-Modell
• Tabellen- und Index-Scans
• Selektions- und Projektionsoperatoren
• externes Mergesort
• Hash-basierte Gruppierung
• Aggregationsoperatoren
• Duplikatseliminierung
• Pipelining versus Materialisierung

Key theories

Das Iterator-Modell (Volcano)

Jeder Operator stellt open-, next- und close-Methoden bereit und zieht bei Bedarf Tupel von seinen Kindern; diese einheitliche Schnittstelle ermöglicht die Zusammensetzung beliebiger Operatoren zu Pipelines und ist die Grundlage der meisten Abfrage-Engines.

Pipelining versus Materialisierung

Gepipelined-Operatoren geben Tupel direkt an ihr Elternelement weiter, ohne Zwischenergebnisse zu schreiben, was E/A spart, während blockierende Operatoren wie Sort ihre Eingabe materialisieren müssen, bevor sie eine Ausgabe erzeugen; der Optimierer gleicht die beiden aus.

Externes Sortieren und Aggregieren

Wenn Daten den Speicher überschreiten, verarbeiten externes Mergesort und Hash-basierte Gruppierung diese in Durchläufen über die Festplatte; diese Algorithmen liegen ORDER BY, GROUP BY, Duplikatseliminierung und Sort-Merge-Joins zugrunde.

Clinical relevance

Ausführungsoperatoren sind der Punkt, an dem die geschätzten Kosten eines Abfrageplans zu realer Laufzeit werden: Die Wahl und Implementierung der Operatoren und wie gut sie den Speicher nutzen und unnötige Festplatten-E/A vermeiden, bestimmen den Durchsatz und die Latenz jeder Abfrage, die eine Datenbank bedient.

History

Das Iterator-Modell wurde in Graefes Volcano-Abfrageauswertungs-Framework und seiner Übersicht über Abfrageauswertungstechniken von 1993, die die von relationalen Engines verwendeten physikalischen Operatoren katalogisierte, kristallisiert. Die einheitliche Schnittstelle des Modells machte erweiterbare, zusammensetzbare Abfrage-Engines praktikabel und bleibt Standard, wobei spätere Arbeiten vektorisierte und kompilierte Ausführung für größere Effizienz hinzufügten.

Key figures

• Goetz Graefe
• Jeffrey D. Ullman

Seminal works

• graefe1993
• garciamolina2008

Frequently asked questions

Was ist das Iterator-Modell?

Es ist ein Design, bei dem jeder physikalische Operator dieselbe Schnittstelle implementiert – typischerweise open, next und close – und Tupel einzeln produziert, wenn sein Elternelement next aufruft. Da alle Operatoren diese Schnittstelle teilen, können sie zu beliebigen Planbäumen zusammengesteckt werden, und Tupel fließen bei Bedarf den Baum hinauf.

Warum werden einige Operatoren als blockierend bezeichnet?

Ein blockierender Operator kann keine Ausgabe erzeugen, bevor er seine gesamte Eingabe konsumiert hat – Sortieren und bestimmte Aggregationen sind Beispiele, da das Endergebnis von jedem Eingabetupel abhängt. Blockierende Operatoren müssen ihre Eingabe materialisieren, während gepipelined-Operatoren wie die Selektion Ergebnisse fortlaufend ausgeben können.