GROUP BY indizieren


Gilt für
DB2Ja
MySQLJa
OracleJa
PostgreSQLJa
SQL ServerJa

SQL-Datenbanken verwenden zwei unterschiedliche group by-Algorith­men. Der erste, der Hash-Algorithmus, baut das aggregierte Ergebnis in einer Hash-Tabelle auf. Sobald die Quelldaten vollständig verarbeitet wurden, wird die Hash-Tabelle als Ergebnis ausgegeben. Der zweite Al­go­rithmus, der Sort/Group-Algorithmus, sortiert die Quelldaten zuerst nach dem Gruppierungs­schlüssel. Dadurch folgen die Zeilen jeder Gruppe unmittelbar hintereinander, sodass sie nur noch zusammengefasst werden müssen. Grundsätzlich müssen beide Algorithmen ein Zwischenergebnis materialisieren und werden daher nicht „am Fließband“ (pipelined) ausge­führt. Es sei denn, der Sort/Group-Algorithmus kann die Sortierung durch Indizierung ersetzen.

Beachte

Die MySQL Datenbank 5.6 verwendet den Hash-Algorithmus nicht. Die unten beschriebene Optimierung für den Sort/Group-Al­go­rith­mus funktioniert aber.

Als Beispiel betrachten wir die folgende Abfrage. Sie zeigt die Umsätze von gestern nach PRODUCT_ID gruppiert an:

SELECT product_id, sum(eur_value)
  FROM sales
 WHERE sale_date = TRUNC(sysdate) - INTERVAL '1' DAY
 GROUP BY product_id

Unter Berücksichtigung des Indexes auf SALE_DATE und PRODUCT_ID aus dem vorherigen Abschnitt ist der Sort/Group-Algorithmus in diesem Fall vorteilhaft, da der INDEX RANGE SCAN das Ergebnis bereits in der benötigten Reihenfolge liefert. Das bedeutet, dass die Datenbank die Materialisierung vermeiden kann, weil nicht extra sortiert werden muss. Das group by kann „am Fließband“ (pipelined) ausgeführt werden.

DB2
Explain Plan
------------------------------------------------------------
ID | Operation             |                     Rows | Cost
 1 | RETURN                |                          |  675
 2 |  GRPBY (COMPLETE)     |      25 of 387 (  6.46%) |  675
 3 |   FETCH SALES         |     387 of 387 (100.00%) |  675
 4 |    IXSCAN SALES_DT_PR | 387 of 1009326 (   .04%) |   24

Predicate Information
 4 - START (Q1.SALE_DATE = (CURRENT DATE - 1 DAYS))
      STOP (Q1.SALE_DATE = (CURRENT DATE - 1 DAYS))
Oracle
---------------------------------------------------------------
|Id |Operation                    | Name        | Rows | Cost |
---------------------------------------------------------------
| 0 |SELECT STATEMENT             |             |   17 |  192 |
| 1 | SORT GROUP BY NOSORT        |             |   17 |  192 |
| 2 |  TABLE ACCESS BY INDEX ROWID| SALES       |  321 |  192 |
|*3 |   INDEX RANGE SCAN          | SALES_DT_PR |  321 |    3 |
---------------------------------------------------------------

Die Oracle Datenbank kennzeichnet die Ausführung „am Fließband“ (pipe­lined) durch den Zusatz NOSORT. Bei anderen Datenbanken scheint die Sortierung erst gar nicht im Ausführungsplan auf.

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

Für ein pipelined group by gelten dieselben Voraussetzungen wie für ein piplined order by, nur dass es keine ASC/DESC-Spezifikationen gibt. Das bedeutet, dass die Indizierung mit ASC/DESC-Spezifikationen keinen Einfluss auf ein pipelined group by haben sollte. Dasselbe gilt auch für NULLS FIRST/LAST. Dennoch gibt es Datenbanken, bei denen ASC/DESC-Indizierung ein pipelined group by beeinflusst.

Achtung

Bei PostgreSQL muss man eine order by-Klausel angeben, damit ein Index mit NULLS LAST-Sortierung für ein pipelined group by ver­wendet werden kann.

Die Oracle Datenbank kann einen Index nicht rückwärts lesen, um ein pipelined group by durchzuführen, das von einem order by gefolgt wird.

Mehr Information finden Sie im Anhang für PostgreSQL und Oracle Datenbank.

Wir erweitern nun die Abfrage, um alle Verkäufe seit gestern zu be­rück­sichti­gen, wie wir es zuvor auch bei dem Beispiel für das pipelined order by getan haben. Diese Änderung unterbindet ein pipelined group by aus demselben Grund, aus dem auch das pipelined order by unterbunden wurde: Der INDEX RANGE SCAN liefert die Daten nicht mehr ausschließlich nach dem Gruppierungs­schlüssel sortiert (vergleiche Abbildung 6.1).

SELECT product_id, sum(eur_value)
  FROM sales
 WHERE sale_date >= TRUNC(sysdate) - INTERVAL '1' DAY
 GROUP BY product_id
DB2
Explain Plan
--------------------------------------------------------------------
ID | Operation                   |                      Rows |  Cost
 1 | RETURN                      |                           | 12527
 2 |  GRPBY (FINAL)              |        25 of 25 (100.00%) | 12527
 3 |   TBSCAN                    |        25 of 25 (100.00%) | 12527
 4 |    SORT (INTERMEDIATE)      |        25 of 25 (100.00%) | 12527
 5 |     GRPBY (HASHED PARTIAL)  |      25 of 8050 (   .31%) | 12527
 6 |      FETCH SALES            |    8050 of 8050 (100.00%) | 12526
 7 |       RIDSCN                |    8050 of 8050 (100.00%) |   375
 8 |        SORT (UNQIUE)        |    8050 of 8050 (100.00%) |   375
 9 |         IXSCAN SALES_DT_PR  | 8050 of 1009326 (   .80%) |   372

Um dieses Ergebnis zu erhalten wurde die folgende where-Klausel verwendet: WHERE sale_date >= CURRENT_DATE - 1 MONTH.

Im Vergleich zum Ausführunsplan der Oracle-Datenbank sieht der DB2-Ausführungsplan unverhältnismäßig komplex aus. Das hat zwei Gründe:

  • DB2 zeigt die Sortierung entsprechend des physischen Speicheraddresse zwischen Indexzugriff und Tabellenzugriff explizit an (Operationen 7 und 8).

  • DB2 führt die Aggregierung in zwei Phasen durch: zuerst eine Vor-Aggregierung um die Datenmenge möglichst früh zu reduzieren (Operation 5) und führt dann eine Sortierung und Gruppierung durch.

Oracle
---------------------------------------------------------------
|Id |Operation                    | Name        | Rows | Cost |
---------------------------------------------------------------
| 0 |SELECT STATEMENT             |             |   24 |  356 |
| 1 | HASH GROUP BY               |             |   24 |  356 |
| 2 |  TABLE ACCESS BY INDEX ROWID| SALES       |  596 |  355 |
|*3 |   INDEX RANGE SCAN          | SALES_DT_PR |  596 |    4 |
---------------------------------------------------------------

Daher bevorzugt die Datenbank den Hash-Algorithmus. Dessen Vorteil liegt darin, dass er nur das aggregierte Ergebnis materialisiert. Der Sort/Group-Algorithmus muss jedoch die gesamten Quelldaten zwischenspeichern. Kurz gesagt: Der Hash-Algorithmus benötigt weniger Speicher.

Wie auch beim pipelined order by, geht es beim piplined group by nicht unbedingt um eine schnellere Ausführung. Wichtig ist, dass die Datenbank die Aggregierung „am Fließband“ (pipelined) ausführt – das also das erste Ergebnis kommt, bevor Quelldaten vollständig verarbeitet wurden. Das ist die Voraussetzung für die Optimierungsmethoden des nächsten Kapitels.

Denksport

Gibt es neben Sortieren und Gruppieren noch andere Datenbank-Operationen, die einen Index nutzen könnten, um eine Sortierung zu vermeiden?

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.