2024-11-14

Optimizer: Der unauffällige MVP

Tom Ebergen

Optimizer haben in der Datenbank-Community selten „Hauptfiguren-Energie“. Datenbanken sind meist wegen ihrer Performance, der einfachen Integration oder der Zuverlässigkeit beliebt. Als jemand, der vor allem am Optimizer in DuckDB arbeitet, wollte ich schon länger einen Blogbeitrag darüber schreiben, wie wichtig Optimizer sind und warum sie mehr Anerkennung verdienen. In diesem Beitrag analysieren wir Queries, die in eine von drei Kategorien fallen: unoptimiert, handoptimiert und vom DuckDB-Query-Optimizer optimiert. Ich erkläre außerdem, warum eingebaute Optimizer fast immer besser sind als jede Handoptimierung. Hoffentlich stimmen Sie am Ende zu, dass Optimizer beim Nutzen einer Datenbank eine stille, aber entscheidende Rolle spielen. Zuerst verstehen wir, wo in der Ausführungspipeline die Query-Optimierung stattfindet.

Bevor irgendwelche Daten aus der Datenbank gelesen werden, muss der übergebene SQL-Text geparst und validiert werden. Läuft das erfolgreich durch, entsteht ein baumbasierter Query-Plan. Der vom Parser erzeugte Query-Plan ist naiv und kann je nach Query extrem ineffizient sein. Hier kommt der Optimizer ins Spiel: Der ineffiziente Query-Plan wird zur Änderung und – Sie ahnen es – Optimierung an den Optimizer übergeben. Der Optimizer besteht aus vielen Optimierungsregeln. Jede Regel kann Query-Operationen umordnen, einfügen und löschen, um einen etwas effizienteren Query-Plan zu erzeugen, der logisch äquivalent bleibt. Sind alle Optimierungsregeln angewendet, kann der optimierte Plan deutlich effizienter sein als der vom Parser erzeugte Plan.

In der Praxis kann eine Optimierungsregel auch Optimizer genannt werden. Im Rest dieses Beitrags meint Optimizer-Regel eine konkrete Optimierung und Optimizer den Datenbank-Optimizer, außer das Wort Optimizer benennt eine konkrete Optimierungsregel (z. B. Join Order Optimizer).

Normale Queries vs. optimierte Queries

Um die Wirkung des DuckDB-Query-Optimizers zu betrachten, nutzen wir eine Teilmenge des NYC-Taxi-Datensatzes. Native DuckDB-Tabellen legen Sie mit den folgenden Befehlen an (Hinweis: taxi-data-2019.parquet ist etwa 1,3 GB):

CREATE TABLE taxi_data_2019 AS
    FROM 'https://blobs.duckdb.org/data/taxi-data-2019.parquet';
CREATE TABLE zone_lookups AS
    FROM 'https://blobs.duckdb.org/data/zone-lookups.parquet';

Jetzt, da wir alle Daten von 2019 haben, schauen wir uns die unoptimierten vs. optimierten Pläne für eine einfache Query an. Die folgende SQL-Query holt uns die häufigsten Pickup- und Drop-off-Paare im Borough Manhattan.

PRAGMA disable_optimizer;
PRAGMA explain_output = 'optimized_only';
EXPLAIN SELECT
    pickup.zone AS pickup_zone,
    dropoff.zone AS dropoff_zone,
    count(*) AS num_trips
FROM
    zone_lookups AS pickup,
    zone_lookups AS dropoff,
    taxi_data_2019 AS data
WHERE pickup.LocationID = data.pickup_location_id
  AND dropoff.LocationID = data.dropoff_location_id
  AND pickup.Borough = 'Manhattan'
  AND dropoff.Borough = 'Manhattan'
GROUP BY pickup_zone, dropoff_zone
ORDER BY num_trips DESC
LIMIT 5;

Diese EXPLAIN-Query liefert den folgenden Plan.

Allein die Kreuzprodukte machen diese Query extrem ineffizient. Die Kreuzprodukte erzeugen 256 * 256 * |taxi_data_2019| Zeilen, das sind 5 Billionen Zeilen. Der Filter trifft nur 71 Millionen Zeilen, also nur 0,001 % der Daten. Das Aggregat erzeugt 4.373 Zeilen, die von der ORDER BY-Operation sortiert werden müssen, die in O(N * log N) läuft. Allein 5 Billionen Tupel zu erzeugen, ist eine enorme Datenverarbeitung – das merkt man, wenn man die Query ausführt und feststellt, dass sie nicht fertig wird. Mit aktiviertem Optimizer ist der erzeugte Query-Plan deutlich effizienter, weil die Operationen so umgeordnet werden, dass viele Billionen Zwischenzeilen vermieden werden. Unten der Query-Plan mit aktiviertem Optimizer:

PRAGMA enable_optimizer;
EXPLAIN ...

Schauen wir uns zuerst die Unterschiede in den Ausführungszeiten auf meinem MacBook mit M1 Max und 32 GB Speicher an, bevor wir über die stattgefundenen Optimierungen sprechen.

Hoffentlich zeigt dieser Performance-Vorteil, wie mächtig der DuckDB-Optimizer ist. Welche Optimierungsregeln sind für diese drastischen Verbesserungen verantwortlich? Für die Query oben werden bei der Optimierung drei starke Regeln angewendet: Filter Pushdown, Join Order Optimization und TopN Optimization.

Der Filter-Pushdown-Optimizer ist sehr nützlich, weil er die Menge der verarbeiteten Zwischendaten reduziert. Es ist eine Optimierungsregel, die Menschen manchmal leicht übersehen, und sie führt immer zu schnelleren Ausführungszeiten, wenn der Filter irgendwie selektiv ist. Sie nimmt einen Filter wie Borough = 'Manhattan' und schiebt ihn zum Operator, der die gefilterte Spalte zuerst einführt, hier der Table Scan. Außerdem erkennt sie, wenn eine gefilterte Spalte wie col1 in einer Gleichheitsbedingung vorkommt (z. B. WHERE col1 = col2). In diesen Fällen wird der Filter verdoppelt und auf die andere Spalte col2 angewendet, wodurch die Zwischendatenmenge weiter sinkt.

Der Join Order Optimizer erkennt, dass die Filter pickup.LocationID = data.pickup_location_id und dropoff.LocationID = data.dropoff_location_id als Join-Bedingungen genutzt werden können, und ordnet Scans und Joins entsprechend um. Diese Optimizer-Regel leistet viel, um die Menge der verarbeiteten Zwischendaten zu reduzieren, weil sie für das Entfernen der Kreuzprodukte verantwortlich ist.

Der TopN-Optimizer ist sehr nützlich, wenn Aggregatdaten sortiert werden müssen. Hat eine Query einen ORDER BY- und einen LIMIT-Operator, kann ein TopN-Operator diese beiden ersetzen. Der TopN-Operator ordnet nur die höchsten/niedrigsten N Werte, statt aller Werte. Ist N 5, muss DuckDB nur 5 Zeilen mit den Minimum-/Maximumwerten im Speicher halten und kann den Rest verwerfen. Interessieren Sie sich also nur für die Top-N-Werte aus M, wobei N << M, kann der TopN-Operator in O(M + N * log N) statt O(M * log M) laufen.

Das sind nur ein paar der Optimierungen, die DuckDB hat. Weitere Optimierungen erklärt der Abschnitt Übersicht aller Optimizer.

Handoptimierte Queries

Für die Query oben ist es möglich, durch sorgfältiges von-Hand-Schreiben der SQL-Query fast denselben Plan zu erreichen. Um einen ähnlichen Plan wie den von DuckDB erzeugten zu bekommen, können Sie Folgendes schreiben.

SELECT
    pickup.zone AS pickup_zone,
    dropoff.zone AS dropoff_zone,
    count(*) AS num_trips
FROM
    taxi_data_2019 data
INNER JOIN
    (SELECT * FROM zone_lookups WHERE Borough = 'Manhattan') pickup
    ON pickup.LocationID = data.pickup_location_id
INNER JOIN
    (SELECT * FROM zone_lookups WHERE Borough = 'Manhattan') dropoff
    ON dropoff.LocationID = data.dropoff_location_id
GROUP BY pickup_zone, dropoff_zone
ORDER BY num_trips desc
LIMIT 5;

Schauen wir uns die Laufzeiten erneut an:

Das SQL oben führt zu einem Plan ähnlich dem DuckDB-optimierten Plan, ist aber wortreicher und fehleranfälliger zu schreiben, was potenziell zu Bugs führen kann. In sehr seltenen Fällen ist es möglich, von Hand eine Query zu schreiben, die einen effizienteren Plan erzeugt als ein Optimizer. Diese Fälle sind extreme Ausreißer, und in allen anderen Fällen erzeugt der Optimizer einen besseren Plan. Außerdem ist eine handoptimierte Query für den aktuellen Zustand der Daten optimiert, der sich durch viele Updates über die Zeit ändern kann. Sind genug Änderungen an den Daten angewendet, gelten die Annahmen einer handoptimierten Query möglicherweise nicht mehr, und die Performance wird schlecht. Schauen wir uns das folgende Beispiel an.

Angenommen, ein junges Unternehmen hat eine orders- und eine parts-Tabelle, und jedes Mal, wenn ein Dashboard lädt, müssen die beliebtesten bestellten Teile berechnet werden. Da das Unternehmen noch relativ neu ist, hat es nur wenige Bestellungen, der Teilekatalog ist aber noch recht groß. Eine handoptimierte Query sähe so aus:

CREATE OR REPLACE TABLE orders AS
    SELECT RANGE order_id, range % 10_000 pid FROM range(1_000);
CREATE TABLE parts AS
    SELECT range p_id, range::VARCHAR AS part_name FROM range(10_000);
SELECT
    parts.p_id,
    parts.part_name,
    count(*) AS ordered_amount
FROM parts
INNER JOIN orders
    ON orders.pid = parts.p_id
GROUP BY ALL;

Natürlich wächst die Zahl der Bestellungen, wenn das Unternehmen Kunden gewinnt und beliebter wird. Läuft die Query oben weiter ohne Optimizer, sinkt die Performance langsam. Das liegt daran, dass die Execution Engine die Hashtabelle auf der Orders-Tabelle aufbaut, die potenziell 100 Millionen Zeilen hat. Ist der Optimizer aktiviert, kann der Join Order Optimizer die Statistiken der Tabelle während der Optimierung inspizieren und einen neuen Plan entsprechend dem neuen Zustand der Daten erzeugen.

Hier die Aufschlüsselung der Queries mit und ohne Optimizer, während die Orders-Tabelle wächst.

Am Anfang ist der Unterschied in der Ausführungszeit kaum spürbar, niemand würde also an ein Query-Rewrite als Lösung denken. Sind aber genug Bestellungen erreicht, wird 2 Sekunden Warten bei jedem Dashboard-Laden mühsam. Ist der Optimizer aktiviert, verbessert sich die Query-Performance um den Faktor 10×. Wenn Sie also jemals denken, Sie hätten ein Szenario gefunden, in dem Sie schlauer sind als der Optimizer, stellen Sie sicher, dass Sie auch alle möglichen Updates der Daten bedacht und dafür ebenfalls von Hand optimiert haben.

Optimierungen, die von Hand unmöglich sind

Manche Optimierungsregeln sind auch von Hand unmöglich zu schreiben. Die TopN-Optimierung zum Beispiel lässt sich nicht von Hand optimieren.

Ein weiteres gutes Beispiel ist die Join-Filter-Pushdown-Optimierung. Die Join-Filter-Pushdown-Optimierung greift in Szenarien, in denen die Build-Seite eines Hash Joins eine Teilmenge der Join-Keys hat. In ihrem aktuellen Zustand merkt sich die Join-Filter-Pushdown-Optimierung den Minimalwert-Key und den Maximalwert-Key und schiebt einen Tabellenfilter in die Probe-Seite, um Keys größer als der maximale Join-Wert und kleiner als der minimale Join-Wert herauszufiltern.

Mit einer kleinen Änderung können wir die Query von oben nutzen, um das zu zeigen. Angenommen, wir filtern unsere parts-Tabelle zuerst so, dass nur Teile mit einem bestimmten Präfix im part_name enthalten sind. Hat die orders-Tabelle 100 Millionen Zeilen und die parts-Tabelle nach dem Filtern nur ~20.000, dann ist die orders-Tabelle die Probe-Seite und die parts-Tabelle die Hash-/Build-Seite. Wird die Hashtabelle gebaut, werden die Min- und Max-p_id-Werte in der parts-Tabelle festgehalten, in diesem Fall könnten das 20.000 und 80.000 sein. Diese Min- und Max-Werte werden als Filter in den Scan der orders-Tabelle geschoben und filtern alle Teile mit p_id > 80.000 und pid < 20.000 heraus. 40 % der orders-Tabelle haben eine pid größer als 80.000 und kleiner als 20.000, diese Optimierung leistet also in Join-Queries viel.

Stellen Sie sich vor, diese Logik in Ihrer Lieblings-Dataframe-API auszudrücken; das wäre extrem schwierig und fehleranfällig. Die Bibliothek müsste diese Optimierung automatisch für alle Hash Joins implementieren. Die Join-Filter-Pushdown-Optimierung kann die Query-Performance um 10× verbessern und sollte deshalb ein Schlüsselfaktor sein, wenn Sie entscheiden, welches analytische System Sie nutzen.

Nutzen Sie eine Dataframe-Bibliothek wie collapse, pandas, data.table, modin, dann genießen Sie die Vorteile von Query-Optimierungstechniken höchstwahrscheinlich nicht. Das heißt, Ihre Optimierungen müssen von Hand angewendet werden, was nicht nachhaltig ist, wenn sich Ihre Daten zu ändern beginnen. Außerdem schreiben Sie höchstwahrscheinlich imperativ, mit einer Syntax, die spezifisch für die Dataframe-Bibliothek ist. Das heißt, die Skripte, die für die Datenanalyse verantwortlich sind, sind nicht sehr portabel. SQL dagegen kann deutlich intuitiver zu schreiben sein, weil es eine deklarative Sprache ist, und lässt sich praktisch in jedes andere Datenbanksystem portieren.

Übersicht aller Optimizer

Unten eine nicht vollständige Liste aller Optimierungsregeln, die DuckDB anwendet.

Expression Rewriter

Der Expression Rewriter vereinfacht Ausdrücke innerhalb jedes Operators. Manchmal werden Queries mit Ausdrücken geschrieben, die nicht vollständig ausgewertet werden, oder sie lassen sich so umschreiben, dass Features der Execution Engine genutzt werden. Unten eine Tabelle gängiger Expression-Rewrites und der Optimierungsregeln, die dafür verantwortlich sind. Viele dieser Regeln schreiben Ausdrücke so um, dass spezialisierte DuckDB-Funktionen genutzt werden und die Ausdrucksauswertung zur Laufzeit deutlich schneller ist. Kann ein Ausdruck in der Optimizer-Phase zu true ausgewertet werden, muss der ursprüngliche Ausdruck nicht an die Execution Engine übergeben werden. Außerdem erlauben die optimierten Ausdrücke DuckDB eher, den Query-Plan weiter zu verbessern. Die Regel „Move constants“ könnte zum Beispiel Filter-Pushdown ermöglichen.

Filter Pull-Up & Filter Pushdown

Filter Pushdown wurde oben kurz erklärt. Filter Pull-Up ist ebenfalls wichtig, um Fälle zu erkennen, in denen ein Filter auf Spalten in anderen Tabellen angewendet werden kann. Die Query unten scannt zum Beispiel die Spalte a aus t1 und t2. t1.a hat einen Filter, aber wegen der Gleichheitsbedingung kann t2.a denselben Filter haben. Zum Beispiel:

SELECT *
FROM t1, t2
WHERE t1.a = t2.a
  AND t1.a = 50;

Das lässt sich optimieren zu:

SELECT *
FROM t1, t2
WHERE t1.a = t2.a
  AND t1.a = 50
  AND t2.a = 50;

Filter Pull-Up zieht den Filter t1.a = 50 über den Join hoch, und wenn der Filter wieder nach unten geschoben wird, erkennt die Optimizer-Regel, dass der Filter auf beide Spalten t1.a und t2.a angewendet werden kann.

IN Clause Rewriter

Gibt es einen Filter mit einer IN-Klausel, lässt er sich manchmal so umschreiben, dass die Ausführung effizienter ist. Einige Beispiele unten:

Außerdem wandelt der IN Clause Rewriter teure IN-Ausdrücke in MARK-Joins. Hat eine Query einen Ausdruck wie c1 IN (x1, ..., xn), wobei n recht groß ist, kann es teuer sein, diesen Ausdruck für jede Zeile der Tabelle auszuwerten. Die Laufzeit wäre O(n * m), wobei n die Zahl der Zeilen und m die Länge der Liste ist. Der IN-Clause-Rewriter wandelt den Ausdruck in SELECT c1 FROM t1, VALUES (x1, ..., xn) t(c0) WHERE c1 = c0 und macht daraus einen HASH-Join, der in O(n + m) fertig werden kann!

Join Order Optimizer

Der Join Order Optimizer kann einen enormen Performance-Vorteil bringen, indem er die Zahl der zwischen Joins verarbeiteten Zwischentupel begrenzt. Werden weniger Zwischentupel verarbeitet, kann die Query schneller ausführen.

Statistics Propagation

Statistics Propagation ist eine weitere Optimierung, die auch dann greift, wenn sich der Zustand der Daten ändert. Indem der Query-Plan durchlaufen und alle Gleichheits-Join-Bedingungen notiert werden, kann der Statistics-Propagation-Optimizer neue Filter erzeugen, indem er die Statistiken der Spalten inspiziert, die später gejoint werden. Angenommen, t1.a und t2.a werden mit der Gleichheitsbedingung t1.a = t2.a gejoint. Sagen uns unsere internen Statistiken, dass t1.a einen Maximalwert von 50 und einen Minimalwert von 25 hat, kann der Optimizer beim Scannen der Tabelle t2 einen neuen Filter erzeugen. Der Filter wäre t2.a >= 25 AND t2.a <= 50.

Filter umordnen

Gibt es mehrere Filter auf einer Spalte, wird auch die Reihenfolge wichtig, in der diese Filter ausgeführt werden. Am besten führt man die effizientesten Filter zuerst aus und spart teure Filter für später. DuckDB kann Gleichheit zum Beispiel sehr schnell auswerten. Für eine Query wie ... WHERE a = 50 AND md5(b) LIKE '%d77%' sagt der Optimizer DuckDB also, zuerst a = 50 auf jeder Spalte auszuwerten. Besteht der Wert in Spalte a die Prüfung a = 50, wertet DuckDB den md5-Hash für die Werte in Spalte b aus.

Fazit

Ein gut geschriebener Optimizer kann erhebliche Performance-Verbesserungen bringen, wenn er frei optimieren darf. Der Optimizer kann nicht nur die vielen Optimierungsregeln anwenden, die ein Mensch natürlich übersehen könnte, er kann auch auf Änderungen in den Daten reagieren. Manche Optimierungen können eine Performance-Verbesserung von 100× bringen – das kann der Unterschied sein, wenn Sie sich zwischen Analysesystem A und Analysesystem B entscheiden. Mit DuckDB werden alle Optimierungsregeln automatisch auf jede Query angewendet, Sie können die Vorteile also durchgehend genießen. Hoffentlich hat Sie dieser Blogbeitrag überzeugt, beim nächsten Datenbanksystem, das allen in den Ohren klingt, auch an den Optimizer zu denken.