2023-05-26

Korrelierte Subqueries in SQL

Mark Raasveldt

Subqueries in SQL sind eine mächtige Abstraktion: Einfache Abfragen werden zu zusammensetzbaren Bausteinen. Komplexe Probleme lassen sich in kleinere Teile zerlegen; große, komplexe Abfragen werden dadurch leichter zu schreiben, zu verstehen und zu warten.

DuckDB nutzt einen modernen Optimizer zur Dekorrelation von Subqueries, sodass Subqueries sehr effizient ausgeführt werden. Nutzer können Subqueries frei verwenden, um ausdrucksstarke Abfragen zu bauen, ohne sie manuell in Joins umschreiben zu müssen. Mehr dazu im Abschnitt Leistung.

Arten von Subqueries

SQL-Subqueries gibt es in zwei Hauptformen: Subqueries als Ausdrücke und Subqueries als Tabellen. Als Ausdrücke können sie in den Klauseln SELECT oder WHERE stehen. Als Tabellen können sie in der Klausel FROM stehen. In diesem Beitrag konzentrieren wir uns auf Subqueries als Ausdrücke. Ein späterer Beitrag behandelt Subqueries als Tabellen.

Subqueries als Ausdrücke gibt es in drei Formen.

• Skalare Subqueries
• EXISTS
• IN/ANY/ALL

Alle können korreliert oder unkorreliert sein. Eine unkorrelierte Subquery ist unabhängig von der äußeren Abfrage. Eine korrelierte Subquery enthält Ausdrücke aus der äußeren Abfrage. Korrelierte Subqueries lassen sich als parametrisierte Subqueries verstehen.

Unkorrelierte skalare Subqueries

Unkorrelierte skalare Subqueries können nur einen einzelnen Wert zurückgeben. Dieser konstante Wert wird dann in der Abfrage eingesetzt. Warum das nützlich ist: Stellen Sie sich vor, wir wollen alle kürzesten Flüge in unserem Datensatz. Die kürzeste Flugstrecke liefert:

SELECT min(distance)
FROM ontime;

Diesen Abstand könnten wir manuell in die Klausel WHERE einsetzen, um alle Flüge auf dieser Strecke zu holen.

SELECT uniquecarrier, origincityname, destcityname, flightdate
FROM ontime
WHERE distance = 31.0;

Dafür müssten wir die Konstante aber fest in die Abfrage schreiben. Nutzen wir die erste Abfrage als Subquery, berechnen wir die minimale Distanz als Teil der Abfrage.

SELECT uniquecarrier, origincityname, destcityname, flightdate
FROM ontime
WHERE distance = (
     SELECT min(distance)
     FROM ontime
);

Korrelierte skalare Subqueries

Unkorrelierte Subqueries sind mächtig, haben aber eine harte Grenze: Es darf nur ein einzelner Wert zurückkommen. Oft wollen wir die Abfrage parametrisieren, damit pro Zeile andere Werte zurückkommen.

Angenommen, wir wollen die kürzesten Flüge je Carrier finden. Den kürzesten Flug für einen bestimmten Carrier liefert die folgende parametrisierte Abfrage:

PREPARE min_distance_per_carrier AS
SELECT min(distance)
FROM ontime
WHERE uniquecarrier = ?;

Das Prepared Statement liefert die minimale Distanz für einen bestimmten Carrier.

EXECUTE min_distance_per_carrier('UA');

Wollen wir diese parametrisierte Abfrage als Subquery nutzen, brauchen wir eine korrelierte Subquery. Korrelierte Subqueries erlauben parametrisierte Abfragen als skalare Subqueries, indem sie Spalten aus der äußeren Abfrage referenzieren. Die Menge der kürzesten Flüge je Carrier erhalten wir so:

SELECT uniquecarrier, origincityname, destcityname, flightdate, distance
FROM ontime AS ontime_outer
WHERE distance = (
     SELECT min(distance)
     FROM ontime
     WHERE uniquecarrier = ontime_outer.uniquecarrier
);

Beachten Sie, wie die Spalte der äußeren Relation (ontime_outer) innerhalb der Abfrage genutzt wird. Das macht die Subquery zur korrelierten Subquery. Die Spalte der äußeren Relation (ontime_outer.uniquecarrier) ist ein Parameter der Subquery. Logisch wird die Subquery einmal für jede Zeile in ontime ausgeführt; der Spaltenwert dieser Zeile wird als Parameter eingesetzt.

Um deutlicher zu machen, dass die korrelierte Subquery im Kern eine parametrisierte Abfrage ist, können wir mit DuckDBs Macros ein skalares Macro anlegen, das die Abfrage enthält.

CREATE MACRO min_distance_per_carrier(param) AS (
     SELECT min(distance)
     FROM ontime
     WHERE uniquecarrier = param
);

Das Macro können wir in der ursprünglichen Abfrage wie eine Funktion nutzen.

SELECT uniquecarrier, origincityname, destcityname, flightdate, distance
FROM ontime AS ontime_outer
WHERE distance = min_distance_per_carrier(ontime_outer.uniquecarrier);

Das ergibt dasselbe wie die korrelierte Subquery in der Abfrage, ist aber sauberer, weil sich die Abfrage wirksamer in mehrere Teile zerlegen lässt.

EXISTS

EXISTS prüft, ob eine gegebene Subquery Ergebnisse hat. Als korrelierte Subquery ist das mächtig. Zum Beispiel, wenn wir den letzten Flug auf jeder Strecke holen wollen.

Alle Flüge auf einer gegebenen Strecke nach einem bestimmten Datum liefert:

PREPARE flights_after_date AS
SELECT uniquecarrier, origincityname, destcityname, flightdate, distance
FROM ontime
WHERE origin = ? AND dest = ? AND flightdate > ?;

EXECUTE flights_after_date('LAX', 'JFK', DATE '2017-05-01');

Für den letzten Flug auf einer Strecke brauchen wir Flüge, für die kein späterer Flug existiert.

SELECT uniquecarrier, origincityname, destcityname, flightdate, distance
FROM ontime AS ontime_outer
WHERE NOT EXISTS (
     SELECT uniquecarrier, origincityname, destcityname, flightdate, distance
     FROM ontime
     WHERE origin = ontime_outer.origin
       AND dest = ontime_outer.dest
       AND flightdate > ontime_outer.flightdate
);

IN / ANY / ALL

IN prüft, ob ein gegebener Wert im Ergebnis der Subquery vorkommt. Alle Carrier mit mehr als 250 000 Flügen im Datensatz liefert zum Beispiel:

SELECT uniquecarrier
FROM ontime
GROUP BY uniquecarrier
HAVING count(*) > 250000;

Über eine Klausel IN holen wir dann alle Flüge dieser Carrier.

SELECT *
FROM ontime
WHERE uniquecarrier IN (
     SELECT uniquecarrier
     FROM ontime
     GROUP BY uniquecarrier
     HAVING count(*) > 250000
);

Eine korrelierte Subquery ist hier nützlich, wenn wir nicht die Gesamtzahl der Flüge je Carrier zählen wollen, sondern die Gesamtzahl auf der gegebenen Strecke. Alle Flüge von Carriern mit mindestens 1000 Flügen auf einer gegebenen Strecke liefert:

SELECT *
FROM ontime AS ontime_outer
WHERE uniquecarrier IN (
     SELECT uniquecarrier
     FROM ontime
     WHERE ontime.origin = ontime_outer.origin
       AND ontime.dest = ontime_outer.dest
     GROUP BY uniquecarrier
     HAVING count(*) > 1000
);

ANY und ALL verallgemeinern IN. IN prüft, ob der Wert in der von der Subquery gelieferten Menge vorkommt. Das entspricht = ANY(...). Die Operatoren ANY und ALL erlauben andere Vergleichsoperatoren (etwa >, <, <>). Die obige Abfrage lässt sich so nach ANY umschreiben.

SELECT *
FROM ontime AS ontime_outer
WHERE uniquecarrier = ANY (
     SELECT uniquecarrier
     FROM ontime
     WHERE ontime.origin = ontime_outer.origin
       AND ontime.dest = ontime_outer.dest
     GROUP BY uniquecarrier
     HAVING count(*) > 1000
);

Leistung

Skalare Subqueries werden logisch einmal ausgeführt, korrelierte Subqueries logisch einmal pro Zeile. Natürlich denkt man daher, korrelierte Subqueries seien sehr teuer und aus Leistungsgründen zu vermeiden.

In vielen SQL-Systemen stimmt das – in DuckDB nicht. In DuckDB werden Subqueries immer dekorreliert. DuckDB nutzt einen modernen Algorithmus zur Dekorrelation, beschrieben im Paper Unnesting Arbitrary Queries. Alle Subqueries können dekorreliert und als eine einzige, deutlich effizientere Abfrage ausgeführt werden.

In DuckDB bedeutet Korrelation keine Leistungsverschlechterung.

Schauen wir uns den Query-Plan der korrelierten skalaren Subquery mit EXPLAIN an: Die Abfrage wurde in eine Hash-Aggregation und einen Hash-Join verwandelt. Damit läuft sie sehr effizient.

EXPLAIN SELECT uniquecarrier, origincityname, destcityname, flightdate, distance
FROM ontime AS ontime_outer
WHERE distance = (
     SELECT min(distance)
     FROM ontime
     WHERE uniquecarrier = ontime_outer.uniquecarrier
);

┌───────────────────────────┐
│         HASH_JOIN         │
│   ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─   │
│      uniquecarrier =      │
│       uniquecarrier       ├──────────────┐
└─────────────┬─────────────┘              │
┌─────────────┴─────────────┐┌─────────────┴─────────────┐
│         SEQ_SCAN          ││       HASH_GROUP_BY       │
│   ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─   ││   ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─   │
│           ontime          ││       uniquecarrier       │
└───────────────────────────┘│       min(distance)       │
                             └─────────────┬─────────────┘
                             ┌─────────────┴─────────────┐
                             │         SEQ_SCAN          │
                             │   ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─   │
                             │           ontime          │
                             └───────────────────────────┘

Den drastischen Leistungsunterschied der Dekorrelation sieht man, wenn man die Laufzeit dieser Abfrage in DuckDB mit Postgres und SQLite vergleicht. Auf dem ontime-Datensatz für 2017 mit etwa ~4 Millionen Zeilen ergeben sich:

Da Postgres und SQLite die Subquery nicht dekorrelieren, wird sie nicht nur logisch, sondern tatsächlich einmal pro Zeile ausgeführt. Die Subquery läuft in diesen Systemen also 4 Millionen Mal – das dauert enorm.

In diesem Fall lässt sich die Abfrage manuell dekorrelieren:

SELECT ontime.uniquecarrier, origincityname, destcityname, flightdate, distance
FROM ontime
JOIN (
     SELECT uniquecarrier, min(distance) AS min_distance
     FROM ontime
     GROUP BY uniquecarrier
  ) AS subquery
  ON ontime.uniquecarrier = subquery.uniquecarrier
 AND distance = min_distance;

Nach manueller Dekorrelation verbessert sich die Leistung von SQLite und Postgres deutlich. Beide Systeme bleiben aber über 30× langsamer als DuckDB.

Bestimmte Subqueries lassen sich durch Umschreiben des SQL manuell dekorrelieren – aber nicht immer. Wie im Paper Unnesting Arbitrary Queries beschrieben, braucht man zum Dekorrelieren beliebiger Abfragen spezielle Join-Typen, die in SQL nicht vorkommen.

In DuckDB erzeugt das System diese speziellen Join-Typen automatisch, um alle Subqueries zu dekorrelieren. DuckDB kann Subqueries, die nicht dekorreliert sind, gar nicht ausführen. Alle Subqueries werden vor der Ausführung dekorreliert.

Fazit

Subqueries sind ein sehr mächtiges Werkzeug: Beliebige Abfragen werden zu Ad-hoc-Funktionen. Zusammen mit DuckDBs starker Dekorrelation laufen sie extrem effizient – zuvor unhandhabbare Abfragen werden nicht nur möglich, sondern schnell.