Joins planen in PostgreSQL
Der Planner erstellt zunächst Pläne zum Durchlaufen jeder Tabelle, die in der Abfrage benutzt wird. Diese Pläne werden von den Indexen für diese Tabellen bestimmt. Da ein seq scan immer möglich ist, wird auch immer ein Plan dafür erstellt. Gibt es für eine Tabelle einen oder mehrere Indexe, kann ein Plan für einen Index Scan oder einen Bitmap Index Scan erstellt werden.
Nachdem die Pläne für die einzelnen Tabellen erstellt sind, werden Pläne für Verbundoperationen (JOINS) erstellt, und zwar paarweise für alle Tabellen, für die in der Abfrage Joins existieren (alle Kombinationen). Die Kosten eines Knotens sind abhängig von seinen Eingabemengen: der Anzahl von Zeilen, die von seinen Kindknoten errechnet wurden.
Wenn auf einer unteren Ebene des Abfragebaums schlechte Entscheidungen getroffen werden, etwa, weil der Planner keine aktuellen Statistiken zur Verfügung hat, kann die Leistung stark sinken. (beispielsweise, wenn weit unten im Baum eine OR-Verknüpfung für große Zwischenergebnisse sorgt, die sich dann durch den gesamten Ausführungsplan fortpflanzen).
PostgreSQL verwendet für Joins drei unterschiedliche Algorithmen: Nested Loop, Merge Join oder Hash Join.
- Nested Loop
Für jeden gefundenen Datensatz der linken Tabelle wird die rechte Tabelle einmal durchlaufen. Wenn die rechte Tabelle indiziert ist, kann sie mit einem index-scan durchlaufen werden.
Da ein Nested Loop Join die rechte Seite mehrere Male liest, ist er sehr kostenintensiv. Wenn rechts ein Index Scan möglich ist oder nur eine kleine Tabelle, kann das Ergebnis wahrscheinlich unter Verwendung der im Cache abgelegten Seiten vorheriger Anfragen berechnet werden. Wenn es sich aber um einen Seq Scan handelt, der alle Zeilen vergleicht, dann muss die rechte Seite unter Umständen viele Male von der Festplatte gelesen werden.
Ein Nested Loop kann die erste übereinstimmende Zeile schneller zurückgeben als andere Join-Methoden, die erst ihr vollständiges Ergebnis berechnen müssen, bevor sie etwas zurückgeben. Ein Nested-Loop-Join ist immer anwendbar. - Merge Join
Jede Tabelle wird nach den JOIN-Attributen sortiert, bevor die JOIN-Operation ausgeführt wird. Dann werden die beiden Tabellen parallel gescannt und passende Zeilen werden miteinander kombiniert. Jede Tabelle muss dabei nur einmal gescannt werden. Die vorherige Sortierung der Tabellen erfolgt entweder in einem extra Sortiervorgang oder durch die Benutzung des Index, falls das Feld indiziert ist und der JOIN über dieses Attribut erfolgt.
Wenn die Eingaben nicht bereits nach Join-Attributen sortiert sind (vielleicht aufgrund eines früheren Merge-Joins oder weil ein Index verwendet wurde, um die Suchbedingung zu erfüllen), fügt der Planner eine Sortierung hinzu, um eine korrekte Zeilenfolge herzustellen. Diese Sortierung erhöht die Kosten des Merge-Joins.
Ein Vorteil des Merge-Joins ist, dass die Kosten für die Sortierung über mehrere Joins amortisiert werden können, vorausgesetzt die Merge-Joins verbinden dieselben Attribute.
Der Planner gibt dem Merge Join gegenüber einem Hash Join den Vorzug, wenn die Eingaben wahrscheinlich gleich groß sind bzw. wenn er die Kosten der Sortierung über mehrere Vorgänge amortisieren kann. - Hash-Join
Der Hash Join erzielt die beste Performance, wenn der Größenunterschied der Tabellen bedeutend ist und die kleinere Tabelle komplett in den Speicher passt.
Zuerst wird die kleinere Tabelle gescannt und in eine Hash-Table geladen, mit den JOIN-Attributen als Schlüssel. Dann wird die größere Tabelle gescannt und jeder gefundene passende Wert wird als Schlüssel benutzt, um über die Hash-Table den entsprechenden Datensatz in der kleineren Tabelle zu finden. Der Planner kann nur dann einen Hash-Join benutzen, wenn Spalten mit dem Operator = verglichen werden.
Jede Scan-Methode (enable_bitmapscan, enable_indexscan, enable_seqscan) und jede Join-Methode (enable_hashjoin, enable_mergejoin, enable_nestloop) kann zur Laufzeit an- bzw. abgeschaltet werden. So kann man den Planner zwingen, andere Ausführungspläne zu erzeugen, und die Ausführung von Abfragen beeinflussen. Die Einflussnahme ist aber begrenzt, der Planner lässt sich nicht zu unsinnigen Ausführungsplänen überreden.
set enable_hashjoin = false;
Beispiel: Ein JOIN über 3 Tabellen:
relname | reltuples
---------+-----------
anfrage | 39653
inserate | 8556
kontakt | 14022
phpugs=# explain analyze select trim(name), inserate.indate, anf_datum, chiffre
from anfrage, inserate, kontakt
where anf_datum > '2007-03-15' and chiffre > 28500
and chiffre = did and kontakt.kid=inserate.kid order by chiffre;
QUERY PLAN
-----------------------------------------------------------------------------
Sort (cost=45.08..45.08 rows=1 width=94)
Sort Key: anfrage.chiffre
-> Nested Loop (cost=31.75..45.07 rows=1 width=94)
-> Nested Loop (cost=31.75..44.05 rows=1 width=24)
-> Bitmap Heap Scan on anfrage (cost=31.75..35.77 rows=1 width=12)
Recheck Cond: ((anf_datum > '2007-03-15 00:00:00+01'::timestamp
with time zone) AND (chiffre > 28500))
-> BitmapAnd (cost=31.75..31.75 rows=1 width=0)
-> Bitmap Index Scan on i_anf_datum
(cost=0.00..4.36 rows=12 width=0)
Index Cond: (anf_datum > '2007-03-15 00:00:00+01'
::timestamp with time zone)
-> Bitmap Index Scan on i_chiffre
(cost=0.00..27.14 rows=382 width=0)
Index Cond: (chiffre > 28500)
-> Index Scan using i_did on inserate (cost=0.00..8.27 rows=1 width=16)
Index Cond: (anfrage.chiffre = inserate.did)
-> Index Scan using i_kontid on kontakt (cost=0.00..1.00 rows=1 width=78)
Index Cond: (kontakt.kid = inserate.kid)
Total runtime: 1.059 ms
-> Index Scan using i_kontid on kontakt (cost=0.00..1.00 rows=1 width=78)
Index Cond: (kontakt.kid = inserate.kid)
Total runtime: 1.059 ms
Hier wird ein Nested Loop geplant, dessen Eingabemengen aus einem anderen Nested Loop und einem Index Scan stammen. Der innere Nested Loop bekommt seine Daten aus einem Bitmap Heap Scan und einem Index Scan ...
Oft kann die Ausführungszeit allein durch Umschreiben einer Abfrage erheblich reduziert werden, weil der Planner dann auch einen anderen Ausführungsplan berechnet.
Ein Beispiel aus der PG-Mailingliste
Hier sind zwei äquivalente Abfragen, die dasselbe Ergebnis liefern. Durch Umformulieren der Abfrage konnte die Ausführungszeit von 708.316 ms auf 0.121 ms gesenkt werden.
EXPLAIN ANALYZE SELECT r.*
FROM raw_annonces r
LEFT JOIN annonces a ON a.id=r.id
LEFT JOIN archive_data d ON d.id=r.id
WHERE a.id IS NULL
AND d.id IS NULL
AND r.id >1130306 order by id limit 1;
QUERY PLAN
----------------------------------------------------------------------------------------
Limit (cost=0.00..2.54 rows=1 width=627) (actual time=708.167..708.168 rows=1 loops=1)
-> Merge Left Join (cost=0.00..128497.77 rows=50539 width=627)
(actual time=708.165..708.165 rows=1 loops=1)
Merge Cond: ("outer".id = "inner".id)
Filter: ("inner".id IS NULL)
-> Merge Left Join (cost=0.00..27918.92 rows=50539 width=627)
(actual time=144.519..144.519 rows=1 loops=1)
Merge Cond: ("outer".id = "inner".id)
Filter: ("inner".id IS NULL)
-> Index Scan using raw_annonces_pkey on raw_annonces r
(cost=0.00..11222.32 rows=50539 width=627)
(actual time=0.040..0.040 rows=1 loops=1)
Index Cond: (id > 1130306)
-> Index Scan using annonces_pkey on annonces a
(cost=0.00..16118.96 rows=65376 width=4)
(actual time=0.045..133.272 rows=65376 loops=1)
-> Index Scan using archive_data_pkey on archive_data d
(cost=0.00..98761.01 rows=474438 width=4)
(actual time=0.060..459.995 rows=474438 loops=1)
Total runtime: 708.316 ms
Nun die zweite Variante:
EXPLAIN ANALYZE SELECT *
FROM raw_annonces r
WHERE r.id>1130306
AND NOT EXISTS( SELECT id FROM annonces WHERE id=r.id )
AND NOT EXISTS( SELECT id FROM archive_data WHERE id=r.id )
ORDER BY id LIMIT 1;
QUERY PLAN
----------------------------------------------------------------------
Limit (cost=0.00..38.12 rows=1 width=627)
(actual time=0.040..0.041 rows=1 loops=1)
-> Index Scan using raw_annonces_pkey on raw_annonces r
(cost=0.00..481652.07 rows=12635 width=627)
(actual time=0.039..0.039 rows=1 loops=1)
Index Cond: (id > 1130306)
Filter: ((NOT (subplan)) AND (NOT (subplan)))
SubPlan
-> Index Scan using archive_data_pkey on archive_data
(cost=0.00..3.66 rows=1 width=4)
(actual time=0.007..0.007 rows=0 loops=1)
Index Cond: (id = $0)
-> Index Scan using annonces_pkey on annonces
(cost=0.00..5.65 rows=1 width=4)
(actual time=0.006..0.006 rows=0 loops=1)
Index Cond: (id = $0)
Total runtime: 0.121 ms