Hash-Join

Der Hash-Join-Algorithmus versucht die Schwachstelle des Nested-Loops-Joins zu umgehen: das häufige Durchwandern des Indexbaumes für die innere Abfrage. Stattdessen werden alle potenziell passenden Zeilen in eine Hash-Tabelle geladen, die dann sehr effizient abgefragt werden kann. Zur Optimierung eines Hash-Joins benötigt man eine völlig andere Indizierungs-Strategie als bei einem Nested-Loops-Join. Darüber hinaus kann man die Performance eines Hash-Joins verbessern, indem man weniger Spalten selektiert. Das ist allerdings eine Herausforderung für die meisten ORM-Werkzeuge.

Die Indizierungs-Strategie für einen Hash-Join ist deshalb völlig anders, weil man nicht die Join-Prädikate, sondern die unabhängigen where-Prädikate indiziert.

Betrachten wir das folgende Beispiel. Es lädt alle Verkäufe der letzten 6 Monate mit den zugehörigen Mitarbeiter-Daten.

SELECT *
  FROM sales s
  JOIN employees e ON (s.subsidiary_id = e.subsidiary_id
                  AND  s.employee_id   = e.employee_id  )
 WHERE s.sale_date > trunc(sysdate) - INTERVAL '6' MONTH

Die Bedingung auf SALE_DATE ist das einzige unabhängige Prädikat – es bezieht sich nur auf eine Tabelle und gehört nicht zu den Join-Prädikaten.

Die Ausführung beginnt mit dem Zugriff auf die Tabelle EMPLOYEES. Sie wird mit einem Full-Table-Scan vollständig in die Hash-Tabelle geladen. Dabei werden die Join-Spalten als Schlüssel für die Hash-Tabelle verwendet. Danach liest die Datenbank die SALES-Tabelle mit einem Full-Table-Scan und verwirft dabei alle Einträge, die das Filterprädikat auf SALE_DATE nicht erfüllen. Für die verbliebenen Einträge wird ein Zugriff auf die Hash-Tabelle durchgeführt, um die Mitarbeiter-Daten zu laden.

Die Hash-Tabelle wird dabei nur als Zwischenspeicher verwendet, damit die häufigen Zugriffe auf die Tabelle EMPLOYEES vermieden werden. Da die Hash-Tabelle am Beginn der Ausführung in einem Zug aufgebaut wird, gibt es keine Verwendung für einen Index auf den Join-Prädikaten. Dieser Index wäre nur nützlich, wenn man die Zeilen einzeln sucht.

Das heißt aber nicht, dass man einen Hash-Join nicht indizieren kann. Die unabhängigen Prädikate können indiziert werden. Das sind jene Be­din­gungen, die im Ausführungsplan bei den Tabellenzugriffen angezeigt werden. Bei diesem Beispiel also die Bedingung auf SALE_DATE.

CREATE INDEX sales_date ON sales (sale_date)

Der nächste Ausführungsplan nutzt diesen Index. Der Full-Table-Scan auf der Tabelle EMPLOYEES bleibt jedoch, weil es bei dieser Abfrage keine unab­hängigen Bedingungen dafür gibt.

Im Gegensatz zum Nested-Loops-Join ist die Indizierung für einen Hash-Join symmetrisch. Das bedeutet, dass die Join-Richtung die Indizierung nicht beeinflusst. Der Index SALES_DATE könnte auch beim Laden der Hash-Tabelle genutzt werden, wenn man die Join-Richtung umdreht.

Eine völlig andere Methode, die Hash-Join-Performance zu verbessern, ist die Größe der Hash-Tabelle zu verringern. Ein Hash-Join funktioniert nämlich am besten, wenn die Hash-Tabelle vollständig in den Hauptspei­cher passt. Daher wählt der Optimizer die Join-Richtung immer so, dass das kleinere Zwischenergebnis in die Hash-Tabelle geladen wird. Im Aus­füh­rungs­plan kann man die geschätzte Größe der beiden Zwischenergebnisse in der Bytes-Spalte ablesen. Die Tabelle EMPLOYEES ist mit 9 Megabyte etwas kleiner.

Man kann die Größe der Hash-Tabelle verkleinern, indem man die Anzahl der potenziell passenden Zeilen reduziert. Dafür könnte man zum Beispiel anstatt aller Mitarbeiter nur die Verkäufer in die Hash-Tabelle laden. Die Voraussetzung dafür ist, dass man Verkäufer in der Tabelle EMPLOYEES erkennen kann, um eine entsprechende where-Klausel zu formulieren. Selbst wenn es keinen Index für diese Bedingung gibt, wird der Hash-Join dadurch schneller, weil die Hash-Tabelle kleiner wird. Dabei muss man natürlich auch sicherstellen, dass es keine SALES-Einträge zu Mitarbeitern gibt, die keine Verkäufer sind – am besten mit einem Constraint.

Der relevante Faktor beim Verkleinern der Hash-Tabelle ist aber nicht die Anzahl der Zeilen, sondern der Speicherbedarf. Man kann die Größe also auch verkleinern, indem man weniger Spalten selektiert – also nur die Attribute, die man tatsächlich braucht.

SELECT s.sale_date, s.eur_value
     , e.last_name, e.first_name
  FROM sales s
  JOIN employees e ON (s.subsidiary_id = e.subsidiary_id
                  AND  s.employee_id   = e.employee_id  )
 WHERE s.sale_date > trunc(sysdate) - INTERVAL '6' MONTH

Mit dieser Methode kann man kaum einen Bug einschleppen: Löscht man die falsche Spalte, bemerkt man den Fehler wahrscheinlich sehr schnell. Dennoch kann man den Speicherbedarf der Hash-Tabelle damit enorm verringern. In diesem Fall von 9 Megabyte auf 234 Kilobyte – eine Reduktion um 97%.

--------------------------------------------------------------
| Id | Operation                    | Name      | Bytes| Cost|
--------------------------------------------------------------
|  0 | SELECT STATEMENT             |           | 2067K| 2202|
|* 1 |  HASH JOIN                   |           | 2067K| 2202|
|  2 |   TABLE ACCESS FULL          | EMPLOYEES |  234K|  478|
|  3 |   TABLE ACCESS BY INDEX ROWID| SALES     |  913K| 1724|
|* 4 |    INDEX RANGE SCAN          | SALES_DATE|      |  133|
--------------------------------------------------------------

Es scheint zwar auf den ersten Blick einfach, ein paar Spalten aus der select-Klausel zu entfernen, es ist aber eine echte Herausforderung, wenn man einen Objekt-relationalen Mapper (ORM) verwendet. Die Unter­stützung sogenannter Teil-Objekte (partial objects) ist sehr spärlich. Die folgenden Beispiele zeigen einige Möglichkeiten dafür: