Hash-Join


Gilt für
DB2Ja
MySQLNein
OracleJa
PostgreSQLJa
SQL ServerJa

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.

Tipp

Indiziere die unabhängigen Bedingungen, um die Hash-Join-Per­for­mance zu verbessern.

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.

DB2
Explain Plan
------------------------------------------------------------
ID | Operation          |                       Rows |  Cost
 1 | RETURN             |                            | 60750
 2 |  HSJOIN            |             50795 of 10000 | 60750
 3 |   TBSCAN SALES     | 50795 of 1011118 (  5.02%) | 60053
 4 |   TBSCAN EMPLOYEES |   10000 of 10000 (100.00%) |   688

Predicate Information
 2 - JOIN (Q2.SUBSIDIARY_ID = DECIMAL(Q1.SUBSIDIARY_ID, 10, 0))
     JOIN (Q2.EMPLOYEE_ID = DECIMAL(Q1.EMPLOYEE_ID, 10, 0))
 3 - SARG ((CURRENT DATE - 6 MONTHS) < Q2.SALE_DATE)

The where-Klausel wurde wie folgt and DB2 angepasst: WHERE s.sale_date > current_date - 6 MONTH.

Oracle
--------------------------------------------------------------
| Id | Operation          | Name      | Rows  | Bytes | Cost |
--------------------------------------------------------------
|  0 | SELECT STATEMENT   |           | 49244 |    59M| 12049|
|* 1 |  HASH JOIN         |           | 49244 |    59M| 12049|
|  2 |   TABLE ACCESS FULL| EMPLOYEES | 10000 |     9M|   478|
|* 3 |   TABLE ACCESS FULL| SALES     | 49244 |    10M| 10521|
--------------------------------------------------------------

Predicate Information (identified by operation id):
---------------------------------------------------
   1 - access("S"."SUBSIDIARY_ID"="E"."SUBSIDIARY_ID"
          AND "S"."EMPLOYEE_ID"  ="E"."EMPLOYEE_ID")
   3 - filter("S"."SALE_DATE">TRUNC(SYSDATE@!)
                           -INTERVAL'+00-06' YEAR(2) TO MONTH)

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.

Für alle Anwendungsentwickler […] sollte der schmale Band […] eine Pflichtlektüre sein — ADMIN-Magazin

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.

Wichtig

Ein Index auf den Join-Prädikaten verbessert die Hash-Join-Per­for­mance nicht.

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.

DB2
Explain Plan
----------------------------------------------------------------
ID | Operation              |                       Rows |  Cost
 1 | RETURN                 |                            | 16655
 2 |  HSJOIN                |             50795 of 10000 | 16655
 3 |   FETCH SALES          |   50795 of 50795 (100.00%) | 15958
 4 |    RIDSCN              |   50795 of 50795 (100.00%) |  1655
 5 |     SORT (UNQIUE)      |   50795 of 50795 (100.00%) |  1655
 6 |      IXSCAN SALES_DATE | 50795 of 1011118 (  5.02%) |  1631
 7 |   TBSCAN EMPLOYEES     |   10000 of 10000 (100.00%) |   688

Predicate Information
 2 - JOIN (Q2.SUBSIDIARY_ID = DECIMAL(Q1.SUBSIDIARY_ID, 10, 0))
     JOIN (Q2.EMPLOYEE_ID = DECIMAL(Q1.EMPLOYEE_ID, 10, 0))
 3 - SARG ((CURRENT DATE - 6 MONTHS) < Q2.SALE_DATE)
 6 - START ((CURRENT DATE - 6 MONTHS) < Q2.SALE_DATE)

The where-Klausel wurde wie folgt and DB2 angepasst: WHERE s.sale_date > current_date - 6 MONTH.

Oracle
--------------------------------------------------------------
| Id | Operation                    | Name      | Bytes| Cost|
--------------------------------------------------------------
|  0 | SELECT STATEMENT             |           |   59M| 3252|
|* 1 |  HASH JOIN                   |           |   59M| 3252|
|  2 |   TABLE ACCESS FULL          | EMPLOYEES |    9M|  478|
|  3 |   TABLE ACCESS BY INDEX ROWID| SALES     |   10M| 1724|
|* 4 |    INDEX RANGE SCAN          | SALES_DATE|      |     |
--------------------------------------------------------------

Predicate Information (identified by operation id):
---------------------------------------------------
   1 - access("S"."SUBSIDIARY_ID"="E"."SUBSIDIARY_ID"
          AND "S"."EMPLOYEE_ID"  ="E"."EMPLOYEE_ID"  )
   4 - access("S"."SALE_DATE" > TRUNC(SYSDATE@!)
                           -INTERVAL'+00-06' YEAR(2) TO MONTH)

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.

Beachte

Die Indizierung für einen Hash-Join ist unabhängig von der Join-Rich­tung.

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.

Die passende Tasse zu dieser Website findest du in unserem Shop.
Sieht gut aus und unterstützt meine Arbeit hier.

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|
--------------------------------------------------------------

Tipp

Selektiere weniger Spalten, um die Hash-Join-Performance zu verbessern.

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:

Java

JPA definiert FetchType.LAZY in der Annotation @Basic. Es kann auf Attribut-Ebene verwendet werden:

@Column(name="junk")
@Basic(fetch=FetchType.LAZY)
private String junk;

JPA-Provider dürfen diese Annotation aber ignorieren:

The LAZY strategy is a hint to the persistence provider runtime that data should be fetched lazily when it is first accessed. The implementation is permitted to eagerly fetch data for which the LAZY strategy hint has been specified.

Hibernate 3.6 unterstützt diese Annotation, indem es den Byte-Code zur Compile-Zeit instrumentiert. Dabei wird zusätzlicher Code in die kompilierten Klassen eingefügt, der LAZY-Attribute nachlädt, wenn darauf zugegriffen wird. Diese Methode ist für die Applikation nicht sichtbar, öffnet aber einer neuen Dimension von N+1-Problemen die Tür: ein select pro Zeile und Attribut. Das ist insbesondere kritisch, da JPA keine Methode vorsieht, die Attribute bei Bedarf „gierig“ zu laden. Siehe „Using lazy property fetching“ in der Hibernate-Dokumentation.

Die native Hibernate-Abfragesprache HQL löst das Problem mit der FETCH ALL PROPERTIES-Klausel (siehe FewerColumnsInstrumentedHibernate.java).

select s from Sales s FETCH ALL PROPERTIES
 inner join fetch s.employee e FETCH ALL PROPERTIES
 where s.saleDate >:dt

Damit kann man das gierige Laden für die Attribute einer Entity zur Laufzeit erzwingen – selbst wenn man instrumentieren Code und die LAZY-Annotation verwendet.

Eine andere Alternative, nicht alle Spalten einer Tabelle zu laden, ist Daten-Transport-Objekte (DTO) anstatt Entities zu verwenden. Das funktioniert sowohl in HQL als auch JP-QL, indem man das Objekt in der Abfrage instanziert (FewerColumnsJPA.java sample).

select new SalesHeadDTO(s.saleDate , s.eurValue
                       ,e.firstName, e.lastName)
  from Sales s
  join s.employee e
 where s.saleDate > :dt

Die Abfrage selektiert nur die gewünschten Daten und liefert SalesHeadDTO-Objekte als Ergebnis – ein einfaches Java-Objekt (POJO), kein Entity.

Perl

Da das DBIx::Class-Framework nicht als Entity-Manager agiert, kann man Klassen-Hierarchien verwenden, ohne Aliasing-Probleme zu be­kom­men. Diese Methode wird auch im Cookbook gezeigt. Bei der folgenden Schema-Definition wird die Sales-Klasse daher in zwei Ebenen definiert.

package UseTheIndexLuke::Schema::Result::SalesHead;
use base qw/DBIx::Class::Core/;

__PACKAGE__->table('sales');
__PACKAGE__->add_columns(qw/sale_id employee_id subsidiary_id
                            sale_date eur_value/);
__PACKAGE__->set_primary_key(qw/sale_id/);
__PACKAGE__->belongs_to('employee', 'Employees', 
           {'foreign.employee_id'   => 'self.employee_id'
           ,'foreign.subsidiary_id' => 'self.subsidiary_id'});

package UseTheIndexLuke::Schema::Result::Sales;
use base qw/UseTheIndexLuke::Schema::Result::SalesHead/;

__PACKAGE__->table('sales');
__PACKAGE__->add_columns(qw/junk/);

Die vollständige Sales-Klasse leitet sich von SalesHead ab und fügt das fehlende Attribut hinzu. Man kann dann jeweils die verwenden, die man gerade benötigt. Beachte, dass die Tabelle in beiden Klassen angegeben werden muss.

Die zugehörigen Mitarbeiter kann man entweder mittels prefetch vollständig, oder nur mit ausgewählten Spalten laden. Die Möglichkeit, die Spalten direkt in der Abfrage auszuwählen, gibt es bei der Haupt-Tabelle nicht.

my @sales =
   $schema->resultset('SalesHead')
          ->search($cond
                  ,{      join => 'employee'
                   ,'+columns' => ['employee.first_name'
                                  ,'employee.last_name']
                   }
                  );

DBIx::Class 0.08192 generiert die folgende SQL-Abfrage. Es werden alle Spalten für SalesHead und die ausgewählten Attribute der Mitarbeiter selektiert.

SELECT me.sale_id,
       me.employee_id,
       me.subsidiary_id,
       me.sale_date,
       me.eur_value,
       employee.first_name,
       employee.last_name
  FROM sales me
  JOIN employees employee
        ON( employee.employee_id   = me.employee_id
       AND  employee.subsidiary_id = me.subsidiary_id)
 WHERE(sale_date > ?)
PHP

Das Doctrine-Framework unterstützt in Version 2 die Auswahl der Attribute zur Laufzeit. Die Dokumentation sagt, dass sich Teil-Objekte „merkwürdig“ verhalten können. Daher ist das Schlüsselwort partial anzugeben, um die Gefahren zu akzeptieren. Darüber hinaus muss man die Primärschlüssel-Spalten explizit selektieren.

$qb = $em->createQueryBuilder();
$qb->select('partial s.{sale_id, sale_date, eur_value},'
          . 'partial e.{employee_id, subsidiary_id, '
                     . 'first_name , last_name}')
   ->from('Sales', 's')
   ->join('s.employee', 'e')
   ->where("s.sale_date > :dt")
   ->setParameter('dt', $dt, Type::DATETIME);

Die SQL-Abfrage beinhaltet die angeforderten Spalten und dann noch­mal die Spalten SUBSIDIARY_ID und EMPLOYEE_ID der Tabelle SALES.

SELECT s0_.sale_id       AS sale_id0,
       s0_.sale_date     AS sale_date1,
       s0_.eur_value     AS eur_value2,
       e1_.employee_id   AS employee_id3,
       e1_.subsidiary_id AS subsidiary_id4,
       e1_.first_name    AS first_name5,
       e1_.last_name     AS last_name6,
       s0_.subsidiary_id AS subsidiary_id7,
       s0_.employee_id   AS employee_id8
  FROM sales s0_
 INNER JOIN employees e1_
         ON s0_.subsidiary_id = e1_.subsidiary_id
        AND s0_.employee_id   = e1_.employee_id
 WHERE s0_.sale_date > ?

Die Ergebnis-Objekte sind kompatibel zu vollständig geladenen Objekten, die fehlenden Spalten sind aber uninitialisiert. Ein Zugriff darauf verursacht keine Exception.

Warnung

MySQL hat keinen Hash-Join (feature request #59025).

Fakten

  • Hash-Joins benötigen keine Indizes für die Join-Prädikate. Sie verwenden stattdessen die Hash-Tabelle.

  • Ein Hash-Join verwendet nur Indizes für die unabhängigen Prädiakte.

  • Reduziere die Größe der Hash-Tabelle um die Performance zu verbessern: entweder horizontal (weniger Zeilen) oder vertikal (weniger Spalten).

  • Der Hash-Join-Algorithmus kann nicht verwendet werden, wenn die Join-Prädikate Bereichs-Bedinungen verwenden (Theta-Joins).

Wenn dir gefällt, wie ich die Dinge erkläre, wirst du meine Kurse lieben.

Über den Autor

Photo of Markus Winand
Markus Winand stimmt Entwickler auf SQL-Performance ein. Er hat das Buch SQL Performance Explained veröffentlicht und bietet inhouse Schulungen sowie Tuning-Leistungen auf http://winand.at/ an.