PostgreSQL^® Optimizer Bits: Semi und Anti Joins

In der Serie „PostgreSQL^® Optimizer Bits“ werden Strategien und Besonderheiten des PostgreSQL^® Optimizers vorgestellt. Den Startpunkt setzt ein neues Feature aus der Version 8.4: Semi und Anti Joins.

PostgreSQL^® bietet seit Version 8.4 eine neue Optimizerstrategie für die Optimierung von bestimmten Abfragen an: Semi und Anti Joins.
Ein Semi Join ist eine spezielle Form eines Joins, die nur die Schlüssel einer Relation a berücksichtigt, sobald diese ebenfalls in der verknüpften Tabelle b auftreten.

Ein Anti Join ist die negative Form eines Semi Join: Tritt ein in Tabelle a gewählter Schlüssel in Tabelle b nicht auf, so wird er bei dieser speziellen Form berücksichtigt. Ein Semi- bzw. Anti-Join sind also spezielle Formen eines Joins, die einen bestimmten Schlüssel nur auf der linken Seite berücksichtigen. Interessant wird dies nun für Abfragen, die nur ein Vorhandensein eines bestimmten Schlüssels prüfen wollen bzw. dies als Filterprädikat nutzen. Bekannt ist ein solches Vorgehen teils von Object Relation Mapper (ORM), die entsprechende Anfragen mit EXISTS() bzw. NOT EXISTS() formulieren.

Im Vergleich zu PostgreSQL^® 8.3 ergibt sich für dieselbe Anfrage ein unterschiedlicher und deutlich effizienter Abfrageplan, wie im folgenden Beispiel (mit relativ einfacher Abfrage) dargestellt. Gegeben seien zwei Tabellen a,b und eine Anfrage über EXISTS(). Es soll ein bestimmter Datensatz aus a ermittelt werden, der eine Entsprechung über a.id2 = b.id in b hat. Selbstverständlich lässt sich dies auch über einen Join lösen, beispielhaft soll dies jedoch zeigen, wie der Optimizer eine derartig formulierte Anfrage auflösen kann:

EXPLAIN SELECT id FROM a WHERE a.id = 200 AND EXISTS(SELECT id FROM b WHERE a.id2 = b.id);

Der Optimizer in PostgreSQL^® 8.3 ermittelt für dieses Beispiel in der Regel folgenden Plan (zu beachten ist, dass die beiden Tabellen a,b jeweils einen Index auf den Spalten id bzw. id2 haben):

                                QUERY PLAN
--------------------------------------------------------------------------
 Index Scan using a_id_idx on a  (cost=0.00..8355.27 rows=503 width=4)
   Index Cond: (id = 200)
   Filter: (subplan)
   SubPlan
     ->  Index Scan using b_id_idx on b  (cost=0.00..8.27 rows=1 width=4)
           Index Cond: ($0 = id)

Im Gegensatz dazu kann PostgreSQL^® 8.4 hash Semi Join nutzen:

                                QUERY PLAN
---------------------------------------------------------------------------
 Hash Semi Join  (cost=27.52..78.16 rows=969 width=4)
   Hash Cond: (a.id2 = b.id)
   ->  Index Scan using a_id_idx on a  (cost=0.00..37.32 rows=969 width=8)
         Index Cond: (id = 200)
   ->  Hash  (cost=15.01..15.01 rows=1001 width=4)
         ->  Seq Scan on b  (cost=0.00..15.01 rows=1001 width=4)

Man sieht deutlich die reduzierten Kosten des Planes, die auch weniger I/O-Zugriffe bedeuten. Für derartige Abfragen lohnt sich also ein genauerer Blick. So weit zum aktuellen Artikel der Serie, der nächste wird bald folgen. Alle Blog-Artikel zum Thema PostgresQL werden auch als Kategorie PostgreSQL^® samt eigenem Feed angeboten – und falls ihr nach Support und Services für PostgreSQL^® sucht, seit Ihr bei uns ebenfalls richtig.