Kostenbasierte Optimierung mit Postgres

Mit den Details der kostenbasierten Optimierung von SQL-Queries in Oracle beschäftige ich mich, seit ich Jonathan Lewis' Standardwerk Cost Based Oracle zum ersten Mal gelesen habe - was ziemlich bald nach seiner Veröffentlichung im Jahr 2005 geschehen sein dürfte. Nachdem ich inzwischen etwa ein halbes Jahr lang mehr oder minder intensiv mit Postgres gearbeitet habe, bin ich nun endlich dazu gekommen, einen etwas genaueren Blick auf die kostenbasierte Optimierung in diesem RDBMS zu werfen, und dabei unter anderem zu folgenden Erkenntnissen gekommen:

• Die beeindruckend klar strukturierte online-Dokumentation für postgres enthält eine Menge von Detailinformationen zum Ablauf der Erzeugung des Ausführungsplans für eine Query und auch einige Erläuterungen zum Costing.
• Darüber hinaus kann man sich auch noch den Code der Costing-Komponente anschauen, insbesondere die Implementierung von costsize.c, die letztlich alle Fragen zum Costing beantworten dürfte. Wenn man aus dem Oracle-Kosmos kommt, in dem die Entscheidungen des Optimizers nur durch Induktion - sprich: Beobachtung und Interpretation des Verhaltens - zu erklären sind, ist diese Basis natürlich ein erstaunlicher Luxus. Wobei ich an dieser Stelle noch ergänzen möchte, dass der Oracle-Optimizer in dieser Hinsicht meiner Einschätzung nach sehr viel intensiver untersucht wurde als die entsprechenden Komponenten anderer RDBMS, die ihren Quellcode nicht offen legen.
• Da mir die Analyse des recht umfangreichen Codes in costsize.c zu aufwändig ist (was möglicherweise mehr über meine Code-Analyse-Fähigkeiten aussagt als über den Code), beschränke ich mich doch wieder auf die angesprochenen induktiven Strategien (und die allgemein bekannten Formeln).
• Die kostenbasierte Optimierung verwendet in ihren Kalkulationen diverse statistische Informationen zu den verwendeten Objekten (Tabellen, Indizes) und einige fest definierte Parameterwerte. Die statistischen Informationen können explizit über das ANALYZE-Kommando ermittelt werden, aber in der Regel übernimmt der autovacuum deamon diesen Job, der für diverse Maintenance-Aufgaben zuständig ist (vor allem auch für die automatische Reorganisation von Objekten zur Freigabe von Speicherplatz durch Ausführung des VACUUM-Kommandos).
• Zu den statistischen Informationen, die über ANALYZE gesammelt werden, gehören:
• die Tabellenstatistiken in pg_class:
• relpages: Anzahl der pages des Objekts auf der Festplatte (wobei eine page dem Block der Oracle-Nomenklatur entspricht).
• pg_class.reltuples: Anzahl der Datensätze.
• die Spaltenstatistiken in pg_stats:
• null_frac: Anteil von NULL-Werten.
• avg_width: durchschnittliche Spaltenbreite in Byte.
• n_distinct: Anzahl distinkter Werte in der Spalte.
• most_common_vals: eine Liste der populärsten (= am häufigsten auftretenden) Werte in der Spalte. Für Oracle entspricht diese Angabe den Informationen eines Histogramms - tatsächlich eines top-n-frequency Histogramms, das für Oracle erst in 12c eingeführt wurde, also eines Histogramms, das sich auf Informationen zur Häufigkeit der Top-n-Werte mit den meisten Wiederholungen beschränkt.
• most_common_freqs: die zu den Angaben in most_common_vals gehörigen Angaben zur Wiederholungshäufigkeit der Werte.
• correlation: die statistische Korrelation der logischen Sortierung der Spaltenwerte und ihrer physikalischen Sortierung auf der Platte. Diese Angabe besitzt also eine relativ große Nähe zum Clustering-Factor für Oracle-Indizes.
• Zusätzlich zu den statistischen Informationen werden im Costing unter anderem folgende Parameter berücksichtigt:
• seq_page_cost (default: 1): die Kosten eines Page-Zugriffs im Rahmen eines sequenziellen Scans (also eines Full Table Scans).
• random_page_cost (default: 4): Kosten für einen nicht-sequenziellen Page-Scan (also z.B. einen Index-Zugriff). Tatsächlich ist der nicht-sequenziellen Page-Scan im Verhältnis zum sequenziellen Scan deutlich teurer als der default-Faktor 4 andeutet, aber bei der Wahl der Defaults liegt die (durchaus plausible) Annahme zugrunde, dass die Index-Blocks relativ häufig im Cache zu finden sind.
• cpu_tuple_cost (default: 0.01): Kosten für das Abrufen einer Ergebniszeile in einem Select.
• cpu_index_tuple_cost (default: 0.005): Kosten für den Zugriff auf einen Index-Eintrag.
• cpu_operator_cost (default: 0.0025): Kosten für die Verwendung eines Operators oder einer Funktion.
• effective_cache_size (default: 128MB): Informationen zur Größe des Caches. Ein höherer Wert macht Index-Zugriffe wahrscheinlicher.

Dazu noch ein kleines Beispiel mit einigen harmlosen Costing-Berechnungen:

-- 9.3
-- Anlage einer Testtabelle mit 10000 Datensätzen
drop table t;

create table t
as
with
basedata as (
select * from generate_series(1, 10000) id
)
select id
     , mod(id, 10) col1
     , '**********************************'::text col2
  from basedata
;

-- manuelle Statistikerfassung
analyze t;

-- Ausgabe der erstellten Statistiken
select * from pg_class where relname = 't';
-[ RECORD 1 ]--+-------
relname        | t
relnamespace   | 2200
reltype        | 112466
reloftype      | 0
relowner       | 10
relam          | 0
relfilenode    | 112464
reltablespace  | 0
relpages       | 94
reltuples      | 10000
relallvisible  | 0
reltoastrelid  | 112467
reltoastidxid  | 0
relhasindex    | f
relisshared    | f
relpersistence | p
relkind        | r
relnatts       | 3
relchecks      | 0
relhasoids     | f
relhaspkey     | f
relhasrules    | f
relhastriggers | f
relhassubclass | f
relfrozenxid   | 23527
relacl         |
reloptions     |

select * from pg_stats where tablename = 't';
-[ RECORD 1 ]----------+-------------------------------------------------
schemaname             | public
tablename              | t
attname                | id
inherited              | f
null_frac              | 0
avg_width              | 4
n_distinct             | -1
most_common_vals       |
most_common_freqs      |
histogram_bounds       | {1,100,200,300,400,500,600,700,800,900,1000,1100
correlation            | 1
most_common_elems      |
most_common_elem_freqs |
elem_count_histogram   |
-[ RECORD 2 ]----------+-------------------------------------------------
schemaname             | public
tablename              | t
attname                | col1
inherited              | f
null_frac              | 0
avg_width              | 4
n_distinct             | 10
most_common_vals       | {0,1,2,3,4,5,6,7,8,9}
most_common_freqs      | {0.1,0.1,0.1,0.1,0.1,0.1,0.1,0.1,0.1,0.1}
histogram_bounds       |
correlation            | 0.10045
most_common_elems      |
most_common_elem_freqs |
elem_count_histogram   |
-[ RECORD 3 ]----------+-------------------------------------------------
schemaname             | public
tablename              | t
attname                | col2
inherited              | f
null_frac              | 0
avg_width              | 35
n_distinct             | 1
most_common_vals       | {**********************************}
most_common_freqs      | {1}
histogram_bounds       |
correlation            | 1
most_common_elems      |
most_common_elem_freqs |
elem_count_histogram   |

Erwähnenswert ist an dieser Stelle vielleicht noch, dass das Erzeugen von Datensätzen mit Hilfe von generate_series nicht nur komfortabel, sondern auch sehr schnell ist - was im Fall von 10000 Datensätzen natürlich noch keine Rolle spielt - und dass der über \x aktivierte erweiterte Ausgabemodus für psql eine nette Sache ist, da er eine automatische Transformation der Ausgabe von Spalten zu Zeilen hervorruft.

Costing für Full Table Scan

Das Costing für den Full Table Scan, der im postgres-Kontext als sequenzieller Scan bezeichnet wird, wird in der Dokumentation explizit erläutert und beruht auf der Kombination der Kosten für das Lesen der Tabellen-Pages mit den Kosten für den Zugriff auf die einzelnen Datensätze, also:

(disk pages read * seq_page_cost) 
+ (rows scanned * cpu_tuple_cost)

-- im Beispiel also:
(94 * 1.0) + (10000 * 0.01) = 194.00

-- explain liefert dazu:
explain select * from t;

                       QUERY PLAN
--------------------------------------------------------
 Seq Scan on t  (cost=0.00..194.00 rows=10000 width=43)

Die Kosten unterteilen sich dabei in start-up cost (0.00 für den sequentiellen Scan) und total cost, wobei letztere exakt der Formel entsprechen. Auch die width ergibt sich exakt aus den Angaben zu den Spalten (4 + 4 + 35 = 43).

Zusätzliche Filter-Bedingungen erhöhen im Fall des sequentiellen Scans die Kosten, da sie eine zusätzliche Prüfung erforderlich machen, die erst nach der Ermittlung aller Datensätze erfolgen kann - im gegebenen Fall steigen die Kosten um 25 (= rows scanned * cpu_operator_cost):

dbadmin=# explain select * from t where id = 1;
                     QUERY PLAN
----------------------------------------------------
 Seq Scan on t  (cost=0.00..219.00 rows=1 width=43)
   Filter: (id = 1)

Costing für Index-Zugriffe

Im Fall von Index-Zugriffen ist die Kostenberechnung deutlich schwieriger. Zunächst sind ein paar Punkte erwähnenswert, in denen sich postgres anders verhält als Oracle:

• Ein Index-Zugriff, der entweder sehr selektiv ist, oder über einen Index erfolgt, dessen Sortierung sehr stark der physikalischen Sortierung der Tabelle entspricht (also eine starke correlation der fraglichen Spalte in pg_stats besitzt; in Oracle wäre das ein günstiger Clustering Factor), wird über einen "Index Scan" durchgeführt.
• Für Zugriffe, bei denen eine relativ große Abweichung der Sortierung von Index und Tabelle zu erwarten ist, steigt postgres auf einen "Bitmap Index Scan" mit folgendem "Bitmap Heap Scan" um. Das bedeutet: postgres liest die Index-Einträge, sortiert dann die enthaltenen row locations und greift dann mit der sortierten Ergebnisliste auf die Tabellen-Pages zu. Der Sinn der Übung ist die Vermeidung von Mehrfachzugriffen auf die Tabellen-Pages die sich ergeben würden, wenn die row locations ungeordnet besucht werden würden. Das wäre jetzt ein guter Moment für den Einsatz einer illustrierenden Grafik, aber die habe ich gerade nicht zur Hand. Das Vorgehen gibt es seit Version 11 auch in Oracle und tritt in 12c als TABLE ACCESS BY INDEX ROWID BATCHED in Zugriffsplänen auf.
• Postgres neigt zur Verknüpfung mehrerer Indizes über BitmapOr- und BitmapAnd-Verknüpfungen. Oracle kann das grundsätzlich auch (mit Hilfe einer BITMAP CONVERSION TO ROWID), neigt aber fast immer zur Verwendung des am besten geeigneten Index und zur anschließenden Filterung der zurückgelieferten Ergebnisse (für bitmap Indizes verwendet Oracle natürlich auch die entsprechenden Kombinationsverfahren, aber ich betrachte hier zunächst nur normale B*Tree-Indizes).

Das Costing für den "Index Scan" basiert, so weit ich sehen kann, auf folgender Formel:

(index pages read * random_page_cost * 2) 
+ (cpu_tuple_cost * rows scanned) 
+ (cpu_index_tuple_cost * scanned rows) 
+ (cpu_operator_cost * x)

-- im Beispiel für eine Query mit Einzelsatzzugriff:
(1 * 4 * 2) + (0.01 * 1) + (0.005 * 1) + (0.0025 * 100)
= 8 + 0.01 + 0.005 + 0.25

-- also:
create index t_idx0 on t(id);
create index t_idx1 on t(col1);

explain select * from t where id = 1;

                           QUERY PLAN
-----------------------------------------------------------------
 Index Scan using t_idx0 on t  (cost=0.00..8.27 rows=1 width=43)
   Index Cond: (id = 1)

So weit ist das ganz plausibel und vermutlich auch mehr oder minder zutreffend, aber die Frage ist: wie komme ich auf die 100 als Multiplikator für cpu_operator_cost? Die Antwort lautet: durch Einsetzen. Wenn ich für den Parameter cpu_operator_cost unterschiedliche Werte einsetze, dann liefert explain das passende Ergebnis zu meiner Formel. Für cpu_operator_cost = 0 ergibt sich ein Cost-Wert von 8.02. Allerdings bekomme ich für veränderte Einschränkungen auch einen veränderten Multiplikator:

set cpu_operator_cost = 0;

explain select * from t where id <= 100;

                            QUERY PLAN
-------------------------------------------------------------------
 Index Scan using t_idx0 on t  (cost=0.00..9.50 rows=100 width=43)
   Index Cond: (id <= 100)

--> (1 * 4 * 2) + (0.01 * 100) + (0.005 * 100) = 9.5

set cpu_operator_cost = 0.1;

explain select * from t where id <= 100;

                             QUERY PLAN
--------------------------------------------------------------------
 Index Scan using t_idx0 on t  (cost=0.00..29.50 rows=100 width=43)
   Index Cond: (id <= 100)

--> (1 * 4 * 2) + (0.01 * 100) + (0.005 * 100) + (0.1 * (100 + 100))

explain select * from t where id <= 200;

                             QUERY PLAN
--------------------------------------------------------------------
 Index Scan using t_idx0 on t  (cost=0.00..42.00 rows=200 width=43)
   Index Cond: (id <= 200)
--> (1 * 4 * 2) + (0.01 * 200) + (0.005 * 200) + (0.1 * (200 + 110))

Demnach scheint cpu_operator_cost immer mit (scanned rows + 100 + x) multipliziert zu werden, wobei das x vermutlich in einem bestimmten Verhältnis zu scanned rows steht. Vermutlich ändern sich die Details auch, wenn mehr als ein Index-Block gelesen werden muss, was bei 30 Index-Blocks und 10000 Datensätzen etwa nach 333 Sätzen erfolgen sollte (= 10000/30).

An dieser Stelle soll mir dieses Zwischenergebnis bis auf weiteres genügen. Klar ist, dass das Costing für postgres - wie im Fall von Oracle - relativ klaren und relativ einfachen Regeln unterliegt; wobei das "relativ einfach" vermutlich nur so lange gilt, wie man überschaubare Fälle untersucht. Mit der Kenntnis dieser Regeln sollte es dann auch möglich sein, die Schwächen des Modells in entsprechenden Fällen zu erkennen und auszugleichen - und muss sich nicht auf die eigene Kreativität im Umformulieren von SQL verlassen (wobei man dann so lange umbaut, bis sich etwas ergibt, was dem Optimizer gerade gefällt - was durchaus zu Ergebnissen führen kann, aber nicht unbedingt effektiv ist).