von Markus Winand.

Zusammengesetzte Schlüssel


Obwohl die Datenbank den Primärschlüssel automatisch indiziert, kann man den Index dennoch verfeinern, wenn der Primärschlüssel aus mehreren Spalten besteht. Dafür wird ein zusammengesetzter Index verwendet. Das ist ein Index, der alle Spalten des Primärschlüssels enthält. Die Reihenfolge der Spalten im Index hat jedoch einen großen Einfluss darauf, welche Abfragen ihn nutzen können. Die Spalten-Reihenfolge muss also sehr sorgfältig gewählt werden.

Zur Demonstration stellen wir uns eine Betriebsübernahme vor. Dabei werden die Mitarbeiter anderer Unternehmen in die EMPLOYEES-Tabelle übernommen, sodass diese insgesamt auf das Zehnfache anwächst. Das einzige Problem ist, dass die EMPLOYEE_ID nicht mehr eindeutig ist. Daher erweitern wir den Primärschlüssel um eine weitere Spalte: die Zweigstellen-Nummer. Der neue Primärschlüssel besteht also aus zwei Spalten: der EMPLOYEE_ID wie gehabt, und der SUBSIDIARY_ID, um die Eindeutigkeit wiederherzustellen.

Der Index für den Primärschlüssel ist also wie folgt definiert:

CREATE UNIQUE INDEX employee_pk
    ON employees (employee_id, subsidiary_id)

Eine Abfrage nach einem bestimmten Mitarbeiter muss den vollständigen Primärschlüssel verwenden, also auch die SUBSIDIARY_ID:

SELECT first_name, last_name
  FROM employees
 WHERE employee_id   = 123
   AND subsidiary_id = 30
DB2
Explain Plan
--------------------------------------------------------
ID | Operation             |                 Rows | Cost
 1 | RETURN                |                      |   13
 2 |  FETCH EMPLOYEES      |     1 of 1 (100.00%) |   13
 3 |   IXSCAN EMPLOYEES_PK | 1 of 10000 (   .01%) |    6

Predicate Information
 3 - START (Q1.EMPLOYEE_ID = +00123.)
     START (Q1.SUBSIDIARY_ID = +00030.)
      STOP (Q1.EMPLOYEE_ID = +00123.)
      STOP (Q1.SUBSIDIARY_ID = +00030.)
MySQL
+----+-----------+-------+---------+---------+------+-------+
| id | table     | type  | key     | key_len | rows | Extra |
+----+-----------+-------+---------+---------+------+-------+
|  1 | employees | const | PRIMARY | 10      |    1 |       |
+----+-----------+-------+---------+---------+------+-------+

Wie zuvor verwendet MySQL den Zugriffstypen const, weil die Abfrage nicht mehr als eine Zeile selektieren kann. Die verwendete Schlüssellänge (key_len) ist jedoch auf 10 gestiegen, da nun zwei Spalten des Indexes benutzt werden. Mehr dazu in MySQL Zugriffs- und Filterprädikate unterscheiden.

Oracle

---------------------------------------------------------------
|Id |Operation                   | Name         | Rows | Cost |
---------------------------------------------------------------
| 0 |SELECT STATEMENT            |              |    1 |    2 |
| 1 | TABLE ACCESS BY INDEX ROWID| EMPLOYEES    |    1 |    2 |
|*2 |  INDEX UNIQUE SCAN         | EMPLOYEES_PK |    1 |    1 |
---------------------------------------------------------------

Predicate Information (identified by operation id):
---------------------------------------------------
   2 - access("EMPLOYEE_ID"=123 AND "SUBSIDIARY_ID"=30)

PostgreSQL

                QUERY PLAN
-------------------------------------------
 Index Scan using employees_pk on employees 
   (cost=0.00..8.27 rows=1 width=14)
   Index Cond: ((employee_id   = 123::numeric)
            AND (subsidiary_id = 30::numeric))

SQL Server

|--Nested Loops(Inner Join)
   |--Index Seek(OBJECT:employees_pk,
   |               SEEK:employee_id=@1 AND subsidiary_id=@2
   |            ORDERED FORWARD)
   |--RID Lookup(OBJECT:employees,
                   SEEK:Bmk1000=Bmk1000
                 LOOKUP ORDERED FORWARD)

Wenn der Zugriff mit dem vollständigen Primärschlüssel erfolgt, kann die Datenbank einen INDEX UNIQUE SCAN durchführen – egal wie viele Spalten der Index hat. Aber was geschieht, wenn die Abfrage nur eine der beiden Spalten verwendet? Wenn zum Beispiel alle Mitarbeiter einer Zweigstelle gesucht werden:

SELECT first_name, last_name
  FROM employees
 WHERE subsidiary_id = 20
DB2

Explain Plan
-------------------------------------------------------
ID | Operation         |                    Rows | Cost
 1 | RETURN            |                         |  689
 2 |  TBSCAN EMPLOYEES | 1195 of 10000 ( 11.95%) |  689

Predicate Information
 2 - SARG (Q1.SUBSIDIARY_ID = +00002.)

Die Abfrage wurde mit SUBSIDIARY_ID = 2 ausgeführt, um das gewünschte Ergebnis zu erhalten. Das hat keine Auswirkung auf das Thema, das wir hier betrachten.

Die Operation TBSCAN zeigt bei DB2 an, dass die ganze Tabelle gelesen wird (entspricht Oracle TABLE ACCESS FULL).

MySQL

+----+-----------+------+------+-------+-------------+
| id | table     | type | key  | rows  | Extra       |
+----+-----------+------+------+-------+-------------+
|  1 | employees | ALL  | NULL | 11000 | Using where |
+----+-----------+------+------+-------+-------------+

Der MySQL Zugriffstyp ALL zeigt einen Full-Table-Scan an: es werden alle Zeilen gelesen und gegen die where-Klausel geprüft.

Oracle

----------------------------------------------------
| Id | Operation         | Name      | Rows | Cost |
----------------------------------------------------
|  0 | SELECT STATEMENT  |           |  106 |  478 |
|* 1 |  TABLE ACCESS FULL| EMPLOYEES |  106 |  478 |
----------------------------------------------------

Predicate Information (identified by operation id):
---------------------------------------------------
   1 - filter("SUBSIDIARY_ID"=20)

PostgreSQL

                QUERY PLAN
-------------------------------------------
 Seq Scan on employees 
   (cost=0.00..1398.50 rows=1070 width=14)
   Filter: (subsidiary_id = 2::numeric)

Die PostgreSQL-Operation Seq Scan zeigt einen Full-Table-Scan an.

SQL Server

|--Table Scan(OBJECT:employees,
               WHERE:subsidiary_id=30)

Der Ausführungsplan zeigt, dass der Index nicht benutzt wird. Stattdessen wird eine TABLE ACCESS FULL-Operation durchgeführt. Dabei liest die Daten­bank die ganze Tabelle und vergleicht jede Zeile mit der where-Klausel. Die Ausführungszeit steigt proportional mit der Tabellengröße. Wenn die Tabelle auf das Zehnfache wächst, dauert der TABLE ACCESS FULL auch zehn Mal so lange. Das Tückische an dieser Operation ist, dass sie in kleinen Entwicklungsumgebungen oft schnell genug ist, in Produktion aber zu Problemen führt.

Full-Table-Scan

Die Operation TABLE ACCESS FULL, auch Full-Table-Scan genannt, kann in manchen Fällen dennoch die beste Zugriffsmethode sein. Das trifft vor allem auf Abfragen zu, die einen großen Teil der Tabelle liefern.

Das liegt einerseits daran, dass der Indexzugriff selbst einen Mehrauf­wand darstellt, der bei einem TABLE ACCESS FULL nicht auftritt. Ande­rer­seits müssen die Datenblöcke bei einer Indexsuche einzeln gelesen werden. Schließlich erfährt die Datenbank erst durch das Lesen eines Blockes, welcher als Nächstes benötigt wird. Im Gegensatz dazu braucht ein TABLE ACCESS FULL ohnehin alle Blöcke und kann daher größere Tabellenbereiche auf einmal lesen (multi block read). Dabei werden zwar mehr Daten gelesen, es erfolgen aber nicht unbedingt mehr Zugriffe.

Die Datenbank verwendet den Index nicht, da man die einzelnen Spalten eines zusammengesetzten Indexes nicht willkürlich verwenden kann. Zum Verständnis betrachten wir den Aufbau eines zusammengesetzten Indexes genauer.

Auch ein zusammengesetzter Index ist ein B-Tree-Index, der die indizierten Daten als sortierte Liste verwaltet. Bei der Sortierung werden die Spalten entsprechend ihrer Position im Index berücksichtigt. Die erste Spalte wird also als vorrangiges Sortierkriterium herangezogen. Die zweite Spalte bestimmt die Reihenfolge nur dann, wenn zwei Einträge denselben Wert in der ersten Spalte haben. Und so fort.

Wichtig

Ein zusammengesetzter Index ist ein Index über mehrere Spalten.

Die Sortierung eines zweispaltigen Indexes erfolgt also wie bei einem Telefonbuch, das zuerst nach Nachname, dann nach Vorname sortiert ist. Daraus folgt, dass ein zweispaltiger Index nicht zur Suche auf der zweiten Spalte alleine verwendet werden kann. Das wäre, als würde man in einem Telefonbuch mit einem Vornamen suchen.

Abbildung 2.1 Zusammengesetzter Index

Der Indexausschnitt in Abbildung 2.1 zeigt, dass die Einträge mit SUBSIDIARY_ID = 20 nicht an einer zentralen Stelle liegen. Es ist auch zu sehen, dass SUBSIDIARY_ID = 20 nicht im Indexbaum aufscheint, obwohl entsprechende Einträge in den Blattknoten vorhanden sind.. Der Indexbaum ist für diese Abfrage völlig nutzlos.

Tipp

Die Visualisierung eines Indexes hilft zu verstehen, welche Abfragen unterstützt werden. Dazu kann man sich die Indexreihenfolge mit einer Abfrage ansehen (SQL:2008 Syntax, siehe für proprietäre Lösungen mit LIMIT, TOP oder ROWNUM):

SELECT <INDEX SPALTENLISTE> 
  FROM <TABELLE>  
 ORDER BY <INDEX SPALTENLISTE>
 FETCH FIRST 100 ROWS ONLY;
Wenn man die Indexdefinition und den Tabellennamen einsetzt, erhält man einen Auszug aus dem Index. Dabei sollte man sich fragen, ob die gesuchten Daten an einer zentralen Stelle zusammengefasst sind. Andernfalls kann man den Indexbaum nicht nutzen, um diese Stelle zu finden.

Um die Abfrage dennoch zu beschleunigen, kann man natürlich einen zweiten Index auf SUBSIDIARY_ID anlegen. Es gibt jedoch eine bessere Alternative – zumindest wenn man davon ausgeht, dass die Suche nach einer EMPLOYEE_ID alleine keinen Sinn ergibt.

Dafür macht man sich zunutze, dass die erste Spalte eines Indexes immer für Suchen herangezogen werden kann. In einem Telefonbuch kann man ja auch ohne einen Vornamen zu kennen, nach einem Nachnamen suchen. Der Trick besteht also darin, die Spaltenreihenfolge des Indexes umzudrehen, sodass SUBSIDIARY_ID an erster Position steht:

CREATE UNIQUE INDEX EMPLOYEES_PK 
    ON EMPLOYEES (SUBSIDIARY_ID, EMPLOYEE_ID)

Beide Spalten zusammen sind nach wie vor eindeutig, sodass der Zugriff über den vollständigen Primärschlüssel weiterhin als INDEX UNIQUE SCAN erfolgt. Die Index-Sortierung hat sich jedoch grundlegend geändert. Der neue Index ist vorrangig nach der SUBSIDIARY_ID sortiert. Das heißt, dass alle Mitarbeiter einer Zweigstelle unmittelbar hintereinander im Index stehen. Dadurch kann man den Indexbaum auch nutzen, um sie zu finden.

Wichtig

Die wichtigste Überlegung beim Erstellen eines zusammengesetzten Indexes ist, wie man die Spaltenreihenfolge wählt, damit er möglichst oft benutzt werden kann.

Der Ausführungsplan zeigt, dass der „umgedrehte“ Index benutzt wird. Da die Spalte SUBSIDIARY_ID alleine nicht eindeutig ist, muss die Datenbank die Blattknoten verfolgen, um alle Einträge zu finden. Es findet also ein INDEX RANGE SCAN statt:

DB2

Explain Plan
-------------------------------------------------------------
ID | Operation               |                    Rows | Cost
 1 | RETURN                  |                         |  128
 2 |  FETCH EMPLOYEES        |  1195 of 1195 (100.00%) |  128
 3 |   RIDSCN                |  1195 of 1195 (100.00%) |   43
 4 |    SORT (UNQIUE)        |  1195 of 1195 (100.00%) |   43
 5 |     IXSCAN EMPLOYEES_PK | 1195 of 10000 ( 11.95%) |   43

Predicate Information
 2 - SARG (Q1.SUBSIDIARY_ID = +00002.)
 5 - START (Q1.SUBSIDIARY_ID = +00002.)
      STOP (Q1.SUBSIDIARY_ID = +00002.)

Dieser Ausführungsplan sieht etwas komplexer aus, als bei der Nutzung des Indexes vorhin. Die Schlüssel-Operationen sind jedoch noch immer hier: die IXSCAN-Operation für den Indexzugriff und die FETCH-Operation für den Tabellenzugriff. Dazwischen tauchen jedoch die unerwarteten Operationen SORT und RIDSCAN auf: die SORT-Operation sortiert die Indexeinträge entsprechend der physischen Speicharaddresse der zugehörigen Zeile in der Heap-Tabelle – sinngemäß entsprechend der ROWID, die bei DB2 RID genannt wird. Die RIDSCN-Operation lädt dann alle betroffenen Datenseiten aus der Heap-Tabelle, wobei aufeinanderfolgende Blöcke in eine Leseoperation zusammengefasst werden.

MySQL

+----+-----------+------+---------+---------+------+-------+
| id | table     | type | key     | key_len | rows | Extra |
+----+-----------+------+---------+---------+------+-------+
|  1 | employees | ref  | PRIMARY | 5       |  123 |       |
+----+-----------+------+---------+---------+------+-------+

Der MySQL-Zugriffstyp ref enspricht einem INDEX RANGE SCAN der Oracle-Datenbank.

Oracle

--------------------------------------------------------------
|Id |Operation                   | Name        | Rows | Cost |
--------------------------------------------------------------
| 0 |SELECT STATEMENT            |             |  106 |   75 |
| 1 | TABLE ACCESS BY INDEX ROWID| EMPLOYEES   |  106 |   75 |
|*2 |  INDEX RANGE SCAN          | EMPLOYEE_PK |  106 |    2 |
--------------------------------------------------------------

Predicate Information (identified by operation id):
---------------------------------------------------
   2 - access("SUBSIDIARY_ID"=20)

PostgreSQL

                 QUERY PLAN
----------------------------------------------
 Bitmap Heap Scan on employees
 (cost=24.63..1529.17 rows=1080 width=13)
   Recheck Cond: (subsidiary_id = 2::numeric)
   -> Bitmap Index Scan on employees_pk
      (cost=0.00..24.36 rows=1080 width=0)
      Index Cond: (subsidiary_id = 2::numeric)

PostgreSQL führt hier zwei Operationen durch: einen Bitmap Index Scan gefolgt von einem Bitmap Heap Scan. Diese Operationen entsprechen ungefähr dem INDEX RANGE SCAN und dem TABLE ACCESS BY INDEX ROWID. Der Unterschied ist, dass das der Bitmap Index Scan zuerst alle passenden Zeilen aus dem Index holt, diese dann entsprechend ihrer physischen Speicherposition in der Tabelle sortiert und dann erst den Zugriff auf die Tabelle durchführt (Bitmap Heap Scan).

SQL Server

|--Nested Loops(Inner Join)
   |--Index Seek(OBJECT:employees_pk,
   |               SEEK:subsidiary_id=20
   |            ORDERED FORWARD)
   |--RID Lookup(OBJECT:employees,
                   SEEK:Bmk1000=Bmk1000
                 LOOKUP ORDERED FORWARD)

Ein zusammengesetzter Index kann benutzt werden, wenn mit den führenden Spalten gesucht wird. Das heißt, ein Index mit drei Spalten kann für Suchen mit der ersten Spalte alleine, mit den ersten beiden oder mit allen drei Spalten gemeinsam verwendet werden.

Obwohl die Lösung mit einem zweiten Index auch sehr gute select-Performance liefert, ist die Variante mit einem Index vorzuziehen. Dadurch wird nicht nur Speicherplatz gespart, sondern auch der Wartungs-Aufwand, den jeder Index nach sich zieht. Je weniger Indizes eine Tabelle hat, desto besser ist die insert-, delete- und update-Performance.

Zur optimalen Indexdefinition muss man also nicht nur wissen, wie ein Index funktioniert, man muss auch wissen, wie die Anwendung auf die Daten zugreift. Konkret heißt das, dass man wissen muss, welche Spaltenkombinationen in der where-Klausel vorkommen.

Für externe Berater kann es daher sehr schwierig sein, einen optimalen Index anzulegen, da die Übersicht über die Zugriffspfade fehlt. Daher wird oft nur eine einzelne SQL-Abfrage berücksichtigt. Den Mehrwert, den ein besser definierter Index für andere Abfragen bringen könnte, wird nicht ausgeschöpft. Datenbankadministratoren sind in einer ähnlichen Situation. Sie kennen die Daten zwar besser, einen umfassenden Überblick über die Zugriffspfade der Applikation haben sie aber auch nicht.

Die einzige Stelle, an der sowohl das Applikationswissen als auch Datenbankwissen vorhanden ist, ist die Entwicklung. Entwickler haben ein Gefühl für die Daten und kennen die Zugriffspfade. Damit können sie ohne großen Aufwand richtig indizieren, um einen optimalen Nutzen zu erzielen.

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

Über den Autor

Foto von Markus Winand

Markus Winand lehrt effizientes SQL – inhouse und online. Er minimiert die Entwicklungszeit durch modernes SQL und optimiert die Laufzeit durch schlaue Indizierung – dazu hat er auch das Buch SQL Performance Explained veröffentlicht.

„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 | CC-BY-NC-ND 3.0 Lizenz