10 Jahre Verbesserungen am PostgreSQL-Optimizer

 (rmarcus.info)
2 Punkte von GN⁺ 2024-04-19 | 1 Kommentare | Auf WhatsApp teilen
  • Verglichen wurde die Abfragelatenz im 90. Perzentil von PostgreSQL 8 bis 16 anhand des Join Order Benchmark; damit werden langfristige Verbesserungen der Tail Performance empirisch belegt
  • Gegenüber PostgreSQL 8 hat PostgreSQL 16 die Tail-Latenz nahezu halbiert, während der Bereich von 13 bis 16 weitgehend stabil blieb
  • Die Regressionsanalyse zeigt im Schnitt eine Performance-Verbesserung von 15 % pro Major-Version, allerdings beschreibt ein lineares Modell den Verlauf der Veränderungen möglicherweise nicht gut
  • Das Experiment hielt die Bedingungen mit GCC 13.2, Arch Linux Docker, shared_buffers 8 GB und work_mem 8 MB konstant, um den Fokus auf die Qualität des Query Optimizers zu legen
  • Bei der Interpretation des Verbesserungsumfangs sollten neben dem Optimizer auch Änderungen an der Execution Engine wie Parallel Worker und JIT-Kompilierung berücksichtigt werden

Benchmark-Setup für PostgreSQL 8 bis 16

  • Analysiert wurden die Major-Versionen 8 bis 16 von PostgreSQL, einem Open-Source-Query-Optimizer
  • Als Benchmark wurde der Join Order Benchmark verwendet, eine Query-Sammlung mit vielen komplexen Joins
    • Dieser Benchmark wurde im Paper „How Good are Query Optimizers, Really?“ eingeführt
  • Jede PostgreSQL-Version wurde mit GCC 13.2 in einem Arch-Linux-Docker-Container gebaut
  • Die Messumgebung wurde so abgestimmt, dass statt Index- oder I/O-Performance vor allem die Qualität des Query Optimizers sichtbar wird
    • shared_buffers wurde auf 8 GB gesetzt, groß genug, um die gesamte Datenbank aufzunehmen
    • work_mem wurde für alle Versionen fest auf 8 MB gesetzt
  • Jede Query wurde zum Aufwärmen des Caches einmal ausgeführt; anschließend wurde die Median-Latenz aus fünf weiteren Ausführungen erfasst
  • Für jede Major-Version wurde die jeweils neueste Minor-Version verwendet
    • Für PostgreSQL 8 war dies zum Beispiel 8.4.22
    • Diese Minor-Versionen erschienen üblicherweise nach der nächsten Major-Version, enthalten aber in der Regel nur Bugfixes und keine neuen Funktionen oder Performance-Verbesserungen

Messergebnisse und Interpretation

  • Die Tail Performance von PostgreSQL hat sich insgesamt deutlich verbessert
    • Vergleicht man PostgreSQL 8 mit 16, wurde die Tail-Latenz nahezu halbiert
    • Von PostgreSQL 13 bis 16 blieb sie weitgehend auf stabilem Niveau
  • Die Regressionsanalyse wurde genutzt, um zu prüfen, ob der fallende Trend zwischen Major-Versionsnummer und Query-Latenz signifikant ist, und um die Verbesserungen je Version zu quantifizieren
    • Nach linearer Regression ergibt sich im Join Order Benchmark im Schnitt eine Performance-Verbesserung von 15 % pro neuer Major-Version
    • Allerdings kann ein lineares Modell ungeeignet sein, um den tatsächlichen Verlauf der Veränderungen zu messen
  • Nicht alle Verbesserungen lassen sich allein durch den Query Optimizer erklären
    • Auch Verbesserungen an der Execution Engine wie Parallel Worker und JIT-Kompilierung beeinflussen die Performance
    • Wie sich die einzelnen Query-Pläne im JOB von Jahr zu Jahr verändert haben, bleibt Gegenstand einer separaten Analyse
  • Beim Upgrade von PostgreSQL 8 auf 16 besteht die Möglichkeit, dass sich die Tail-Latenz der Workload deutlich verringert
  • Für Forschungs­vergleiche ist wichtig, dass PostgreSQL selbst ein immer stärkerer Bezugspunkt wird
    • Neo und Bao wurden mit PostgreSQL 11 verglichen, neuere Arbeiten dagegen mit PostgreSQL 14, 15 und 16
    • Selbst wenn frühere Verfahren gegenüber PostgreSQL 30 % und neuere Verfahren 25 % Verbesserung zeigen, können die neueren Verfahren mit einem stärkeren PostgreSQL verglichen worden sein
  • Die ursprünglichen Messwerte sind in den raw data einsehbar

Verwandte Beiträge

1 Kommentare

 
GN⁺ 2024-04-19
Meinungen auf Hacker News

  • Ich nutze Postgres seit 15 Jahren und habe den Großteil meiner Karriere damit verbracht, mathematische Optimierungsprobleme zu modellieren und zu lösen. Bei diesem Thema sehe ich drei Kernpunkte.
    Jedes Optimierungsproblem braucht Kostendaten, und je mehr und je besser die Daten sind, desto besser wird es. Postgres hat Verbesserungen wie spaltenübergreifende Statistiken bekommen, aber es gibt noch große Lücken, etwa bei der Latenz von Systemaufrufen. Die Latenz beim Lesen von Pages von der Festplatte unterscheidet sich je nach System stark, trotzdem misst Postgres sie nicht direkt, sondern verlässt sich auf Konfigurationswerte. Auch Statistiken zu Fremdschlüsseln fehlen; Joins entlang von Fremdschlüsseln sollten eigentlich nicht zu schlechten Plänen führen, tun es aber gelegentlich immer noch.
    Besonders für große und teure Queries braucht es verzögerte Planung oder Planung alternativer Szenarien. Derzeit wird der Plan vor der Ausführung festgelegt, aber die in frühen Ausführungsschritten gewonnenen Zeilenzahlen oder Kardinalitätsschätzungen könnten den späteren Plan stark verbessern.
    Machine Learning ist ebenfalls ein Bereich mit Verbesserungspotenzial, aber die Versuche, die ich bisher gesehen habe, waren nicht beeindruckend. Statt Machine Learning für die Planung selbst einzusetzen, sollte man es für Kostenermittlung und -schätzung nutzen. Man sollte bessere Kostenmodelle bauen und die Optimierungs-Engine diese Daten nutzen lassen.

    • Ich würde dazu gern mehr Meinungen hören. Zum Beispiel überrascht es mich, dass Latenz von Systemaufrufen so weit oben auf der Liste steht. Aus Sicht der Datenbank-Community ist das Kostenmodell im Allgemeinen ziemlich in Ordnung; wirklich schlecht sind eher die Kardinalitätsschätzungen.
      Bei verzögerter/alternativer Planung frage ich mich, ob adaptive Query-Ausführung ein sinnvoller Ansatz ist. Man kann zwar Informationen aus dem frühen Teil der Query-Ausführung in spätere Pläne einfließen lassen, aber wenn die ersten paar Joins falsch gewählt werden, ist das ein häufiges Problem, und ohne etwas wie Yannakakis/SIPs dürfte es schwer sein, sich davon zu erholen.
      Bei „Machine Learning für Query-Optimierung“ bin ich sicher voreingenommen. Allerdings verwenden alle Ansätze für „Machine Learning zur Planung“, die ich gesehen habe, intern letztlich Machine Learning für Kostenermittlung/-schätzung. Diese Ansätze versuchen, ein Gleichgewicht zwischen den gesammelten Daten, also Exploration, und der Qualität der erzeugten Pläne, also Exploitation, zu finden. Interessanterweise werden die Schätzungen zwar genauer, wenn man Machine Learning völlig getrennt von der Planung einsetzt, die tatsächlichen Query-Pläne werden aber schlechter: https://people.csail.mit.edu/tatbul/publications/flowloss_vl...
      Ich habe in diesem Feld eigene Interessen, also sollte man meine Meinung entsprechend einordnen.
    • Alternative Pläne klingen wirklich gut. Ein Query-Plan, den ich vor Kurzem gesehen habe, erwartete bei einer Subquery etwa 1.000 Zeilen und setzte deshalb auf einen Index Scan mit Nested Loop; tatsächlich waren es aber ungefähr 1 Milliarde Zeilen.
      Warum die Schätzung so danebenlag, weiß ich noch nicht, aber wenn man beim Überschreiten eines bestimmten Schwellenwerts bei der Zeilenzahl von Nested Loop auf Hash Join umschalten könnte, würde das sehr helfen, katastrophale Pläne zu vermeiden.
    • Ich frage mich, was genau damit gemeint ist, dass Statistiken zu Fremdschlüsseln fehlen. Postgres erzeugt, wie viele relationale Datenbanken, nicht automatisch Indizes auf Fremdschlüsseln; das dürfte dir aber schon bekannt sein.
      Geht es um Probleme bei der Join-Reihenfolge?
    • Ich frage mich, ob MSSQL in dieser Hinsicht besser ist.

  • Der Query-Optimizer von Postgres versucht, die Zahl der von der Festplatte gelesenen Pages und die Zahl der Pages zu reduzieren, die als Zwischenergebnisse auf die Festplatte geschrieben werden. Deshalb wirkt es falsch, shared buffers groß genug für alle Daten zu setzen und dann den Query-Optimizer zu benchmarken.
    Dann misst man nicht die Qualität der erzeugten Query-Pläne, sondern die Geschwindigkeit des Query-Optimizers und des Join-Prozessors. Es wäre nicht einmal überraschend, wenn die erzeugten Pläne in allen Versionen tatsächlich gleich wären und nur die Ausführungsgeschwindigkeit gemessen wurde.

    • Nein. Optimiert wird nicht nur auf von der Festplatte gelesene Pages, sondern auf Kosten, die auch Dinge wie CPU-Nutzung einschließen.
      Kosten sind eine willkürliche Einheit, die mit der benötigten Zeit korrelieren soll, nicht mit der Zahl der Disk-Lesevorgänge. Daher ist es völlig legitim, Pläne zu vergleichen, wenn alles im RAM liegt. Konventionell wird das Lesen einer Page von der Festplatte auf 1,0 skaliert, aber das ist nicht dasselbe wie zu sagen: „Der Optimizer minimiert die Zahl der gelesenen Disk-Pages.“ Man hätte auf einer beliebigen Maschine auch 1 ms als 1,0 festlegen können.
    • Es ist gut möglich, dass die Pläne ähnlich sind und Verbesserungen der Ausführungs-Engine gemessen wurden. Der Join Order Benchmark ist darauf ausgelegt, die Qualität des Optimizers zu testen.
      Der PG-Optimizer versucht nicht nur, die Zahl der von der Festplatte gelesenen Pages zu reduzieren, sondern auch die Zahl der von der CPU geprüften Tupel, die Anzahl der Auswertungen von Bedingungen usw.; all diese Zahlen werden zu „Kosten“ zusammengeführt, der Funktion, die der Optimizer minimiert.
      Messungen mit Cold Cache und Warm Cache können unterschiedliche Ergebnisse liefern, und dieses Experiment ist eindeutig ein Warm-Cache-Szenario. Aber auch Cold Cache hat das erwähnte Problem. Bei der Datengröße des Join Order Benchmark könnten die B-Tree-Verbesserungen von PG, die ein paar I/O-Operationen sparen, stärker ins Gewicht fallen als CPU-basierte Verbesserungen.
      Zur Einordnung: Der Plan der P90-Latenz-Query wechselte von einem Plan mit Loop Join und Merge Join in PG 8.4 zu einem Plan mit Hash Join in PG 16, und diese Query ist nicht mehr die P90-Query. Das kann man zumindest als teilweisen Beleg für Verbesserungen am Optimizer sehen.

  • Im Artikel wurde der JIT-Compiler von PostgreSQL erwähnt, aber bisher habe ich nur gesehen, dass er die Query-Performance verschlechtert. Ich habe ihn in meine Installations-Checkliste zum Deaktivieren aufgenommen.

    • Ein Kunde hatte nach dem Wechsel zu Postgres die schlimmsten Performance-Probleme. Seltsamerweise traten sie nur in der Docker- und Testserver-Konfiguration auf, nicht auf den Entwickler-Maschinen. Die Entwickler nutzten Postgres über Homebrew.
      Es stellte sich heraus, dass Homebrew Postgres ohne JIT-Unterstützung installierte. Auf den Entwickler-Maschinen lief eine bestimmte Query in 200 ms durch, in Umgebungen mit aktiviertem JIT dauerte sie aber 4 bis 5 Sekunden. Wir nutzen Postgres nicht besonders tiefgehend, daher dauerte es eine Weile, die Ursache zu finden; seitdem schalten wir JIT immer ab und schauen nicht zurück.
    • Der JIT-Compiler ist für analytische Queries großartig.
      In PostgreSQL kann man auch den Schwellenwert konfigurieren, ab dem JIT aktiviert wird, also kann man die Hürde für das Einschalten von JIT höher setzen.
    • Der JIT von pg zeigt ziemlich gut, dass LLVM für JIT nicht besonders gut geeignet ist, und dass Postgres keinen persistenten gemeinsamen Query-Cache hat, macht es noch schlimmer.
      Wenn man für zukünftige Queries asynchron kompilieren könnte, wäre es wohl weniger schädlich. Tatsächlich ist ein typischer JIT, besonders mit optimierendem Backend, eher näher an diesem Modell.
    • Kann Postgres eine Query nicht einmal JIT-kompilieren und die kompilierte Query dann mehrfach ausführen?

  • Interessant, aber das Versionsnummernschema von Postgres wurde mit v10 geändert. 9.6, 9.5, 9.4, 9.3, 9.2, 9.1, 9.0, 8.4, 8.3, 8.2, 8.1 und 8.0 sind im Grunde alle jeweils eigene Major-Versionen.
    Es wäre auch interessant zu sehen, wie sich die Performance in diesen Versionen verändert hat.

    • Trotzdem war ich dankbar, dass von v9.0 bis 9.6 die Dateisystemkompatibilität zwischen Major-Versionen gewahrt wurde, sodass schnellere In-Place-Upgrades möglich waren, bei denen man im Wesentlichen nur die Binaries austauschte.
      Das mag sie zwar ausgebremst haben, aber jährliche Updates, die mehr Downtime oder Reindexing erfordern, machen wenig Spaß und könnten ein Grund sein, warum viele Sites Upgrades bis zum Ende des Supports der alten Version aufschieben. Besonders dürfte das für AWS-RDS-Nutzer gelten.
      Upgrades per logischer Replikation ab v10 haben Vorteile bei der Verfügbarkeit, sind aber ein großes Projekt mit unvermeidbaren Kosten und erheblichen Risiken, wenn das Schema nicht relativ einfach ist.
    • Stimme völlig zu. Ich habe die Versionsnummern nach semver-Art interpretiert und die jeweils neueste Version jeder Major-Version ausgewählt, aber das entspricht nicht der Art, wie PostgreSQL traditionell mit Major-Versionsnummern umgegangen ist.
      Zum Beispiel sind PG 8.2 und 8.1 unterschiedliche Major-Versionen, ich habe sie aber wie Minor-Versionen interpretiert. Der Hauptgrund dafür war, die Zahl der zu testenden Versionen zu reduzieren, und ich stimme zu, dass eine vollständigere Analyse jede tatsächliche Major-Version testen müsste.

  • Es hieß: „Natürlich ist diese Verbesserung nicht vollständig dem Query-Optimizer zu verdanken“; interessant wäre zu sehen, ob es zwischen den Versionen Änderungen an den Ausführungsplänen gab.

  • Das erinnert an Proebstings Gesetz: https://proebsting.cs.arizona.edu/law.html

    • Das Gute an Compiler-Optimierung ist, dass man die Performance verbessern kann, ohne die vorhandene CPU physisch anzufassen. Jedes Jahr holt jemand mehr Leistung aus einer Maschine heraus, die jemand anderes entworfen hat, und kumuliert wird das groß.
      Stell dir vor, welche Umweltauswirkungen es hätte, die Performance von Python um 1 % zu optimieren. Wie viel CO2 in der Atmosphäre würde das einsparen? Wahrscheinlich mehr als der gesamte ökologische Fußabdruck von dir, deiner Familie und deinen Freunden zusammen. Vielleicht sogar so viel wie der deiner ganzen Stadt. Und das nur, weil jemand Zeit investiert hat, ein paar Bit-Twiddling-Tricks zu implementieren.
    • Ich weiß nicht, warum. Dieses Gesetz scheint eher zu sagen, dass Verbesserungen der Software-Performance kaum Bedeutung haben, während es in diesem Artikel darum geht, dass die Verbesserungen bei Postgres beträchtlich waren.
      Liegt es daran, dass 15 % als niedriger Wert gelten? In diesem Kontext ist das überhaupt nicht niedrig. Es ist weniger als die 60 % aus dem verlinkten Gesetz, und wenn man es als 15/10 aufteilt, noch weniger, aber man sollte Postgres-Performance nicht mit Hardware-Verbesserungen vergleichen. Um bei dem hier gemessenen Gegenstand einer Performance-Steigerung von 1 % zu entsprechen, bräuchte es eine enorme Hardware-Verbesserung.
      Ich finde dieses Gesetz nicht so lächerlich, wie manche es darstellen, aber es handelt von Kompilierzeiten von Programmiersprachen. Ich würde so etwas vergleichsweise Unwichtiges nicht mit Speicherung und Nutzung von Daten vergleichen, was man als eines der wichtigsten Themen der Informatik bezeichnen kann.
    • In diesem Fall hat der Forscher alle PostgreSQL-Versionen mit demselben GCC 13.2 gebaut und auf demselben Betriebssystem getestet.
    • Wirkt wie ein ziemlich schwaches „Gesetz“. War das als Witz gemeint? Die Grundlage sind Zahlen, deren Herkunft unklar ist, auf dem Niveau von „nehmen wir einmal an“, und die Schlussfolgerung liegt auch ziemlich daneben. Es scheint anzudeuten, dass Optimierungen, die die Performance vieler Software weltweit jedes Jahr um 4 % verbessern, Zeitverschwendung seien.
      Als Vergleich wird nur Murphys Gesetz angeführt. Ich würde gern wissen, wie groß der Kostenunterschied zwischen der Entwicklung schnellerer Hardware und der kontinuierlichen Verbesserung von Compilern ist. Je nachdem, wie der Return on Investment im Sinne von Dollar pro prozentualer Performance-Steigerung ausfällt, könnte dieses „Gesetz“ ein gewisses Gewicht bekommen.
      Andererseits scheint dieser Postgres-Artikel bei der Optimierung abnehmende Grenzerträge zu zeigen, was die Prämisse dieses „Gesetzes“ widerlegt, das von jährlich konstanten Gewinnen ausgeht. Zugleich könnte es Proebstings Andeutung bestätigen, dass Optimierung langfristig eine schlechte Investition ist.

  • Diese Analyse ist etwas verwirrend. Ich weiß nicht, wie in den Daten ein Abwärtstrend festgestellt wurde, der im Diagramm nicht zu sehen ist.
    Der Median scheint in den ersten paar Versionen etwas zu sinken und in den jüngsten Versionen wieder zu steigen. Weil R² sehr niedrig ist, wirkt die Korrelation nicht überzeugend. Im Grunde sieht es so aus, als hätte sich die Tail-Latenz verbessert und der Rest hänge von der Umgebung ab.

    • Ich bin der Autor des Blogbeitrags.
      Die Interpretation „die Tail-Latenz hat sich verbessert und der Rest hängt von der Umgebung ab“ halte ich für eine zutreffende, aber konservative Lesart. Natürlich ist Tail-Latenz in vielen, vielleicht den meisten Anwendungen sehr wichtig. Außerdem ist Tail-Latenz auch das, worauf Optimizer-Ingenieure hauptsächlich abzielen: die Laufzeit der am längsten dauernden Queries zu reduzieren.

  • Wie sieht Query-Optimierung eigentlich aus? Ich frage mich, ob auf SQL-Ebene optimiert wird oder auf Algorithmusebene.

    • In den Datenbanken, die ich verwendet habe – PostgreSQL ausgenommen –, passiert der Großteil der Optimierung auf Algorithmusebene. Das heißt, es geht darum, den besten Algorithmus und die Ausführungsreihenfolge für eine bestimmte Query auszuwählen.
      Das scheint daran zu liegen, dass mehrere unterschiedliche SQL-Queries in dieselbe „Anweisung“ bzw. denselben Ausführungsplan übersetzt werden können und die SQL-Semantik selbst auf Sprachebene nicht viel Raum für Optimierung lässt.
      Wie in einer anderen Antwort erwähnt, ist eine der wichtigen Entscheidungen, ob sich ein vollständiger Table Scan durch einen Index-Lookup oder Index Scan ersetzen lässt.
      Wenn zum Beispiel ein vollständiger Table Scan nötig ist und für jede Zeile erheblicher Rechenaufwand erforderlich ist, um zu entscheiden, ob sie in die Ergebnismenge gehört, kann der Optimizer den vollständigen Table Scan in einen parallelen Table Scan umwandeln und die Ergebnisse der einzelnen parallelen Tasks zusammenführen.
      Wenn man Hochleistungscode für Compiler schreibt, muss man wissen, wie der Compiler-Optimizer Quellcode in Maschinencode umwandelt. So kann man Code bevorzugen, mit dem der Optimizer gut zurechtkommt, und Muster vermeiden, die langsameren Maschinencode erzeugen. Letztlich ist der Optimizer darauf programmiert, bestimmte Muster zu erkennen und umzuwandeln.
      Bei Query-Optimizern und Ausführungsplänen ist es genauso. Man muss lernen, welche Muster der Query-Optimizer der verwendeten Datenbank verarbeiten kann, um effiziente Ausführungspläne zu erzeugen.
    • Man beschreibt alle Möglichkeiten, SQL auszuführen, und wählt dann den schnelleren Plan. Wenn man zum Beispiel die Benutzerzeile mit user_id gleich xx sucht, entscheidet man, ob die gesamte Tabelle gelesen und gefiltert wird oder ob eine spezielle Datenstruktur verwendet wird.
      Mit einem Index lässt sich das bezogen auf die Anzahl der Zeilen in logarithmischer Zeit finden. Daneben ist noch vieles möglich: Auswahl der Join-Reihenfolge, Auswahl der Join-Strategie, Pushdown von Filterbedingungen näher an die Quelle usw. Das ist der breite Bereich der SQL-Optimierung.
    • Auf sehr hoher Ebene ist das Ziel des Query Planners, die Kosten für das Lesen von Daten von der Festplatte zu minimieren. Er sammelt vorab berechnete Spaltenstatistiken wie Zeilenzahlen und die Anzahl eindeutiger Werte, um abzuschätzen, wie viele Zeilen eine Query treffen wird.
      Mit diesen Informationen legt er die Join-Reihenfolge fest, wählt Indizes aus und so weiter. Joins können mit verschiedenen Algorithmen ausgeführt werden, etwa Hash, Loop oder Merge. Die günstigste Wahl hängt von Faktoren ab, zum Beispiel ob eine Seite in den Arbeitsspeicher passt, ob beide Seiten bereits sortiert sind, etwa dank eines Index Scan.
    • Query-Optimierung bedeutet, den Algorithmus auszuwählen, der das von SQL angeforderte Ergebnis liefert.

  • Da die Website offenbar offline ist, kann man stattdessen dies ansehen: https://web.archive.org/web/20240417050840/https://rmarcus.i...