von Markus Winand.

Inhaltsverzeichnis › Die Join-Operation ›

Nested Loops – verschachtelte Schleifen

Der Nested-Loops-Join ist der einfachste Join-Algorithmus. Er verwendet zwei verschachtelte Abfragen: eine äußere oder treibende Abfrage und eine innere Abfrage, die für jede Zeile der äußeren ausgeführt wird, um die zugehörigen Daten aus der anderen Tabelle zu laden.

Den Nested-Loop-Algorithmus kann man auch selbst umsetzen, indem man „verschachtelte Abfragen“ verwendet. Das ist allerdings ein problematischer Ansatz, da dabei zusätzlich zu den Festplatten-Latenzen noch Netzwerk-Latenzen anfallen. Dennoch sind verschachtelte Abfragen weit verbreitet – vermutlich, weil man sie ohne es zu wissen implementieren kann. Objekt-relationale Mapper (ORM) sind dabei besonders „hilfreich“ – dort hat das sogenannte „N+1 selects Problem“ eine traurige Berühmtheit erlangt.

Die folgenden Beispiele zeigen verschachtelte Abfragen, die mit ver­schie­denen ORM-Werkzeugen „versehentlich“ umgesetzt wurden. Die Beispiele suchen Mitarbeiter, deren Nachnamen mit 'WIN' beginnen, und laden alle Verkäufe dieser Mitarbeiter.

Java

Mit dem CriteriaBuilder-Interface von JPA.

CriteriaBuilder queryBuilder = em.getCriteriaBuilder();
CriteriaQuery<Employees>
   query = queryBuilder.createQuery(Employees.class);
Root<Employees> r = query.from(Employees.class); 
query.where(
  queryBuilder.like(
    queryBuilder.upper(r.get(Employees_.lastName)),
    "WIN%"
  )
);

List<Employees> emp = em.createQuery(query).getResultList();

for (Employees e: emp) {
  // process Employee
  for (Sales s: e.getSales()) {
    // process sale for Employee
  }
}

Hibernate 3.6.0 generiert dafür N+1 select-Abfragen:

select employees0_.subsidiary_id as subsidiary1_0_
       -- MORE COLUMNS
  from employees employees0_ 
 where upper(employees0_.last_name) like ?
  select sales0_.subsidiary_id as subsidiary4_0_1_
         -- MORE COLUMNS
    from sales sales0_
   where sales0_.subsidiary_id=? 
     and sales0_.employee_id=?
  select sales0_.subsidiary_id as subsidiary4_0_1_
         -- MORE COLUMNS
    from sales sales0_
   where sales0_.subsidiary_id=? 
     and sales0_.employee_id=?
Perl

Mit dem DBIx::Class-Framework für Perl:

my @employees = 
   $schema->resultset('Employees')
          ->search({'UPPER(last_name)' => {-like=>'WIN%'}});

foreach my $employee (@employees) {
   # process Employee
   foreach my $sale ($employee->sales) {
      # process Sale for Employee
   }
}

DBIx::Class 0.08192 generiert dafür N+1 select-Abfragen:

SELECT me.employee_id, me.subsidiary_id
     , me.last_name, me.first_name, me.date_of_birth 
  FROM employees me 
 WHERE ( UPPER(last_name) LIKE ? )
   SELECT me.sale_id, me.employee_id, me.subsidiary_id
        , me.sale_date, me.eur_value
     FROM sales me
    WHERE ( ( me.employee_id = ? 
      AND me.subsidiary_id = ? ) )
   SELECT me.sale_id, me.employee_id, me.subsidiary_id
        , me.sale_date, me.eur_value
     FROM sales me
    WHERE ( ( me.employee_id = ? 
      AND me.subsidiary_id = ? ) )
PHP

Mit dem QueryBuilder-Interface des Doctrine-Frameworks:

$qb = $em->createQueryBuilder();
$qb->select('e')
   ->from('Employees', 'e')
   ->where("upper(e.last_name) like :last_name")
   ->setParameter('last_name', 'WIN%');
$r = $qb->getQuery()->getResult();
foreach ($r as $row) {
   // process Employee
   foreach ($row->getSales() as $sale) {
      // process Sale for Employee
   }
}

Doctrine 2.0.5 generiert dafür N+1 select-Abfragen:

SELECT e0_.employee_id AS employee_id0 -- MORE COLUMNS
  FROM employees e0_
 WHERE UPPER(e0_.last_name) LIKE ?
   SELECT t0.sale_id AS SALE_ID1 -- MORE COLUMNS
     FROM sales t0 
    WHERE t0.subsidiary_id = ? 
      AND t0.employee_id = ?
   SELECT t0.sale_id AS SALE_ID1 -- MORE COLUMNS
     FROM sales t0 
    WHERE t0.subsidiary_id = ? 
      AND t0.employee_id = ?

Die ORM-Werkzeuge generieren keine SQL-Joins – sie fragen die SALES-Tabelle gesondert ab. Dieser Effekt ist als „N+1 selects Problem“ oder kurz „N+1 Problem“ bekannt geworden, weil die Anzahl der select-Abfragen insgesamt N+1 ist, wenn die treibende Abfrage N Zeilen liefert.

Tipp: SQL-Logging aktivieren

Aktiviere das SQL-Logging während der Entwicklung und überprüfe die generierten SQL-Anweisungen.

DBIx::Class

export DBIC_TRACE=1 in der Shell.

Doctrine

Nur programmatisch – vergiss nicht, es für die Produktion zu de­aktivieren!

$logger = new \Doctrine\DBAL\Logging\EchoSqlLogger;
$config->setSQLLogger($logger);
Hibernate (native)

<property name="show_sql">true</property> in App.config oder hibernate.cfg.xml.

JPA

In persistence.xml, aber abhängig vom verwendeten Tool – z. B. für eclipselink, Hibernate und OpenJPA:

<property name="eclipselink.logging.level" value="FINE"/>
<property name="hibernate.show_sql" value="TRUE"/>
<property name="openjpa.Log" value="SQL=TRACE"/>

Die meisten ORM-Werkzeuge bieten auch einen programmatischen Weg an, das SQL-Logging zu aktivieren. Das erhöht aber das Risiko, das Logging versehentlich auch in Produktion zu aktivieren.

Verschachtelte Abfragen sollte man zwar vermeiden, sie beschreiben den Nested-Loops-Algorithmus aber sehr gut. Die Datenbank führt einen Nested-Loops-Join genauso durch, wie es die ORM-Werkzeuge oben machen. Für die Indizierung eines Nested-Loops-Join bedeutet das, dass man Indizes für die oberen Abfragen benötigt. Das ist also ein Funktions-basierter Index auf der Tabelle EMPLOYEES und ein zweispaltiger Index für die Join-Prädikate auf der SALES-Tabelle.

CREATE INDEX emp_up_name ON employees (UPPER(last_name))
CREATE INDEX sales_emp ON sales (subsidiary_id, employee_id)

Ein SQL-Join ist dennoch effizienter als verschachtelte Abfragen – obwohl er dieselben Indexzugriffe durchführt. Das kommt daher, dass der Großteil der Netzwerk-Kommunikation vermieden wird. Er ist sogar dann schneller, wenn insgesamt mehr Daten übertragen werden, weil die Spalten der Tabelle EMPLOYEES für jeden Verkauf dupliziert werden. Das liegt an den zwei Dimensionen der Performance: Antwortzeit und Durchsatz. Bei Netz­werken spricht man von Latenz und Bandbreite. Die Bandbreite beeinflusst die Antwortzeit kaum, die Latenzen aber sehr. Das bedeutet, dass die Anzahl der Datenbankabfragen mehr Einfluss auf die Antwortzeit hat als die transferierte Datenmenge.

Tipp

Führe Join-Operationen in der Datenbank aus.

ORM-Werkzeuge bieten verschiedene Methoden an, SQL-Joins zu gene­rie­ren. Das sogenannte „gierige Laden“ (eager fetching) ist wohl die Wichtigste. Es wird im Entity-Mapping auf Attribut-Ebene aktiviert – also zum Beispiel für das Attribut EMPLOYEES in der SALES-Klasse. Dadurch wird bei jedem Zugriff auf die SALES-Tabelle ein SQL-Join mit der Tabelle EMPLOYEES durch­ge­führt. Die Konfiguration im Entity-Mapping ist also nur sinnvoll, wenn man die Mitarbeiterdaten immer benötigt, wenn man auf Verkäufe zugreift.

Hinweis in eigener Sache

Ich lebe von SQL-Schulungen, SQL-Tuning und Beratung sowie dem Verkauf meines Buches „SQL Performance Explained“. Mehr auf winand.at.

Gieriges Laden ist aber kontraproduktiv, wenn das entsprechende Attribut nur selten benötigt wird. Bei einer Telefonbuch-Anwendung wäre es zum Beispiel nicht sinnvoll, sämtliche SALES-Einträge zu den gefundenen Mit­ar­bei­tern automatisch mit zu laden. Wenn man einen Mitarbeiter lädt, kann es in manchen Fällen sein, dass man die zugehörigen SALES-Daten braucht, in anderen aber nicht. Eine statische Konfiguration im Entity-Mapping ist daher keine Lösung.

Um die beste Performance zu erreichen braucht man die volle Kontrolle über Joins. Die folgenden Beispiele zeigen daher, wie man das Join-Ver­hal­ten zur Laufzeit steuern kann, um die höchste Flexibilität zu erhalten.

Java

Beim CriteriaBuilder-Interface von JPA steuert man Joins mit der Methode Root<>.fetch(). Damit kann man angeben, ob und wie die referenzierten Objekte durch einen SQL-Join mitgeladen werden sollen. Für unser Beispiel benötigen wir einen Left-Join für die SALES-Tabelle, damit auch Mitarbeiter ohne Verkäufe im Telefonbuch aufscheinen.

Warnung

JPA und Hibernate liefern die Mitarbeiter für jeden Verkauf.

Das bedeutet, dass ein Mitarbeiter mit 30 Verkäufen 30-mal ge­lie­fert wird. Das ist zwar störend, aber das spezifizierte Verhalten (EJB 3.0 persistency, Absatz 4.4.5.3 „Fetch Joins“). Man kann die Daten entweder manuell de-duplizieren oder ein LinkedHashSet dafür verwenden oder die Funktion distinct(), wie im Beispiel, verwenden.

CriteriaBuilder qb = em.getCriteriaBuilder();
CriteriaQuery<Employees> q = qb.createQuery(Employees.class);
Root<Employees> r = q.from(Employees.class); 
q.where(queryBuilder.like(
    queryBuilder.upper(r.get(Employees_.lastName)),
    "WIN%")
);

r.fetch("sales", JoinType.LEFT);
// needed to avoid duplication of Employee records
q.distinct(true);

List<Employees> emp = em.createQuery(q).getResultList();

Hibernate 3.6.0 generiert die folgende SQL-Abfrage:

select distinct 
       employees0_.subsidiary_id as subsidiary1_0_0_
     , employees0_.employee_id as employee2_0_0_
       -- MORE COLUMNS
     , sales1_.sale_id as sale1_0__
  from employees employees0_
  left outer join sales sales1_ 
          on employees0_.subsidiary_id=sales1_.subsidiary_id
         and employees0_.employee_id=sales1_.employee_id 
 where upper(employees0_.last_name) like ?

Die Abfrage hat den gewünschten Left-Join, aber auch das distinct-Schlüsselwort. JPA bietet leider keine Möglichkeit, die doppelten Haupt-Einträge zu verwerfen, ohne auch die referenzierten Objekte zu de-duplizieren. Die Verwendung des distinct-Schlüsselwortes in der Abfrage ist bedenklich, weil die meisten Datenbanken tatsächlich eine Filterung durchführen. Nur wenige Datenbanken erkennen aufgrund des Primärschlüssels, dass das Ergebnis ohnehin keine Duplikate ent­hal­ten kann.

Die native Hibernate-API löst das Problem mit einem Ergebnis-Trans­for­mator (result set transformer).

Criteria c = session.createCriteria(Employees.class);
c.add(Restrictions.ilike("lastName", 'Win%'));

c.setFetchMode("sales", FetchMode.JOIN);
c.setResultTransformer(Criteria.DISTINCT_ROOT_ENTITY);

List<Employees> result = c.list();

Damit wird die folgende Abfrage generiert:

select this_.subsidiary_id as subsidiary1_0_1_
     , this_.employee_id as employee2_0_1_
       -- MORE this_ columns on employees
     , sales2_.sale_id as sale1_3_
       -- MORE sales2_ columns on sales
  from employees this_ 
  left outer join sales sales2_ 
          on this_.subsidiary_id=sales2_.subsidiary_id 
         and this_.employee_id=sales2_.employee_id 
 where lower(this_.last_name) like ?

Die SQL-Abfrage hat keine unnötigen Klauseln. Man sollte jedoch beachten, dass Hibernate die Funktion LOWER verwendet, um die Groß- und Kleinschreibung zu ignorieren – ein wichtiges Detail bei der Funktions-basierten Indizierung.

Perl

Mit dem DBIx::Class-Framework für Perl:

my @employees = 
   $schema->resultset('Employees')
          ->search({ 'UPPER(last_name)' => {-like => 'WIN%'}
                   , {prefetch => ['sales']}
                   });

DBIx::Class 0.08192 generiert die folgende Abfrage:

SELECT me.employee_id, me.subsidiary_id, me.last_name
       -- MORE COLUMNS
  FROM employees me 
  LEFT JOIN sales sales 
         ON (sales.employee_id   = me.employee_id 
        AND  sales.subsidiary_id = me.subsidiary_id) 
 WHERE ( UPPER(last_name) LIKE ? )
 ORDER BY sales.employee_id, sales.subsidiary_id

Beachte die order by-Klausel – sie wurde von der Applikation nicht gefordert. Die Datenbank muss das Ergebnis dementsprechend sor­tie­ren – das dauert natürlich.

PHP

Mit dem Doctrine-Framework für PHP:

$qb = $em->createQueryBuilder();
$qb->select('e,s')
   ->from('Employees', 'e')
   ->leftJoin('e.sales', 's')
   ->where("upper(e.last_name) like :last_name")
   ->setParameter('last_name', 'WIN%');
$r = $qb->getQuery()->getResult();

Doctrine 2.0.5 generiert dafür die folgende Abfrage:

SELECT e0_.employee_id AS employee_id0
       -- MORE COLUMNS
  FROM employees e0_ 
  LEFT JOIN sales s1_ 
         ON e0_.subsidiary_id = s1_.subsidiary_id 
        AND e0_.employee_id = s1_.employee_id 
 WHERE UPPER(e0_.last_name) LIKE ?

Im Ausführungsplan erscheint die Operation NESTED LOOPS mit dem Zusatz OUTER:

Die Datenbank lädt das Ergebnis der ersten Tabelle (EMPLOYEES über den Index EMP_UP_NAME) und holt für jede Zeile den entsprechenden Eintrag aus der zweiten Tabelle (SALES über den Index SALES_EMP).

Tipp

Lerne dein ORM-Tool kennen und übernimm die Kontrolle über Join-Operationen.

Ein Nested-Loops-Join liefert gute Performance, wenn die treibende Abfrage nur wenige Zeilen liefert. Andernfalls kann sich der Optimizer auch für einen gänzlich anderen Join-Algorithmus entscheiden – wie zum Beispiel den Hash-Join-Algorithmus, der im nächsten Abschnitt beschrieben wird. Das ist aber nur möglich, wenn die Applikation einen SQL-Join verwendet, um alle Daten auf einmal zu laden.

Vorherige SeiteNächste Seite

Über den Autor

Foto von Markus Winand

Markus Winand ist der SQL Renaissance Botschafter auf der Mission, Entwickler auf die Evolution von SQL im 21. Jahrhundert aufmerksam zu machen. Markus kann als Trainer, Sprecher und Berater auf winand.at engagiert werden.

Sein Buch kaufen

Titelbild von „SQL Performance Explained“: Eichhörnchen läuft durchs Grass

Die Essenz: SQL-Tuning auf 200 Seiten

Jetzt Kaufen
(Taschenbuch und/oder PDF)

Sein Training

Markus verwandelt veraltetes SQL-92-Wissen in solides und zeitgemäßes SQL-Know-how

Erfahren Sie mehr»

Der 3-Minuten Test

Inhaltsverzeichnis

Aktuelle Blog Posts

Geek-Ware

Nicht mit OFFSET blättern

Mehr info

Besuche meine Schwester-Seite!Seit SQL-92 hat sich einiges getan!

Die Use The Index, Luke! Tasse

Aufkleber, Bierdeckel, Bücher und Kaffeetassen. Alles was man beim Lernen braucht!

Zum Shop

Mit Markus Winand verbinden

Markus Winand auf LinkedInMarkus Winand auf XINGMarkus Winand auf Twitter
„Use The Index, Luke!“ von Markus Winand ist unter einer Creative Commons Attribution-Noncommercial-No Derivative Works 3.0 Unported License lizenziert.
Impressum | Kontakt | KEINE GEWÄHR | Handelsmarken | Datenschutz und DSGVO | CC-BY-NC-ND 3.0 Lizenz