Bei einem INDEX RANGE SCAN liegt das größte Performance-Risiko beim Verfolgen der Blattknoten-Liste. Daher ist es die goldene Regel der Indizierung, den durchsuchten Indexbereich möglichst klein zu halten. Zur Kontrolle kann man sich fragen, wo eine Indexsuche beginnt und wo sie endet.
Die Frage ist einfach zu beantworten, wenn die Start- und Stopp-Bedingungen direkt in der SQL-Anweisung aufscheinen:
SELECT first_name, last_name, date_of_birth
FROM employees
WHERE date_of_birth >= TO_DATE(?, 'YYYY-MM-DD')
AND date_of_birth <= TO_DATE(?, 'YYYY-MM-DD')Ein Index auf DATE_OF_BIRTH wird nur im angegebenen Bereich durchsucht. Die Suche beginnt also beim ersten Datum und endet beim zweiten. Man kann den Indexbereich, der für diese Abfrage durchsucht wird, nicht weiter einschränken.
Die Antwort ist weniger offensichtlich, wenn mehrere Spalten betroffen sind:
SELECT first_name, last_name, date_of_birth
FROM employees
WHERE date_of_birth >= TO_DATE(?, 'YYYY-MM-DD')
AND date_of_birth <= TO_DATE(?, 'YYYY-MM-DD')
AND subsidiary_id = ?Ein optimaler Index muss natürlich beide Spalten beinhalten. Aber in welcher Reihenfolge?
Die folgenden Abbildungen zeigen, wie sich die Spaltenreihenfolge auf den durchsuchen Indexbereich auswirkt. Dafür suchen wir alle Mitarbeiter der Zweigstelle 27, die zwischen erstem und neuntem Jänner 1971 geboren wurden.
Abbildung 2.2 zeigt einen Ausschnitt aus dem Index auf DATE_OF_BIRTH und SUBSIDIARY_ID – in dieser Reihenfolge. Wo wird die Suche beginnen? Oder anders gefragt, wohin führt der Indexbaum?
Hinweis in eigener Sache
Ich biete SQL Schulungen, Optimierung und Beratung an. Auch der Kauf meines Buches „SQL Performance Explained“ (ab €9,95) unterstützt meine Arbeit an dieser Webseite.
Der Index ist vorrangig nach Geburtsdatum sortiert. Nur wenn zwei Mitarbeiter am selben Tag geboren wurden, wird die SUBSIDIARY_ID-Spalte zur weiteren Sortierung herangezogen. Da die Suche mehrere Tage abdeckt, ist die Sortierung der SUBSIDIARY_ID-Spalte beim Durchwandern des Indexbaumes nutzlos. Das wird offensichtlich, wenn man bedenkt, dass es keinen Eintrag für Zweigstelle 27 in den Zweigknoten gibt – obwohl es in den Blattknoten einen gibt. Der durchsuchte Indexbereich wird also nur von den Bedingungen auf der DATE_OF_BIRTH-Spalte definiert. Unabhängig vom SUBSIDIARY_ID-Filter beginnt die Suche also beim ersten Datum und endet beim zweiten. In der Abbildung sind das fünf Blattknoten.
Abbildung 2.2 Suche im (DATE_OF_BIRTH, SUBSIDIARY_ID)-Index
Die Situation ändert sich grundlegend, wenn man die Spaltenreihenfolge im Index umdreht und mit der Spalte SUBSIDIARY_ID beginnt. Abbildung 2.3 stellt die Suche in diesem Index dar.
Der Unterschied ist, dass die erste Indexspalte durch den Gleichheitsoperator auf einen einzigen Wert eingeschränkt wird. Innerhalb des Indexbereiches für diesen Wert (SUBSIDIARY_ID 27) ist der Index nach der zweiten Spalte, dem Geburtsdatum, sortiert. Dadurch ist schon im Zweigknoten zu erkennen, dass der erste Blattknoten keine Mitarbeiter der Zweigstelle 27 enthält, die nach dem 25. Juni 1969 geboren wurden.
Abbildung 2.3 Range Scan im (SUBSIDIARY_ID, DATE_OF_BIRTH)-Index
Der Indexbaum führt also direkt zum zweiten Blattknoten. In diesem Fall tragen alle Bedingungen dazu bei, den durchsuchten Indexbereich abzugrenzen, und die Suche kann noch im selben Blattknoten beendet werden.
Tipp
Faustregel: Indiziere zuerst für Ist-gleich-Bedingungen, dann für andere.
Der tatsächliche Geschwindigkeits-Unterschied hängt von den Daten und den Suchkriterien ab. Wenn die Datumsbedingung alleine schon sehr selektiv ist, kann der Unterschied gering ausfallen. Je größer der Datumsbereich wird, desto größer wird auch der Performance-Unterschied sein.
Anhand dieses Beispiels kann man auch den Mythos widerlegen, dass man die selektivste Spalte an die erste Indexposition stellen sollte. In den beiden Abbildungen ist die Selektivität jeder Spalte für sich genommen gleich. Egal ob man nur mit DATE_OF_BIRTH oder nur mit SUBSIDIARY_ID sucht: Jedes Mal erhält man 13 Treffer. Daher ist die Selektivität der einzelnen Spalten in diesem Fall keine Hilfe. Dennoch gibt es eine eindeutig bessere Spaltenreihenfolge.
Zur Optimierung der Performance ist es also wichtig, zu wissen, welcher Indexbereich durchsucht wird. Bei den meisten Datenbanken kann man das direkt im Ausführungsplan ablesen. Man muss nur wissen, worauf man achten muss. Der folgende Ausführungsplan gibt zum Beispiel einen eindeutigen Hinweis darauf, dass der Index EMP_TEST mit der Spalte DATE_OF_BIRTH beginnt.
- DB2
Explain Plan ---------------------------------------------------- ID | Operation | Rows | Cost 1 | RETURN | | 26 2 | FETCH EMPLOYEES | 3 of 3 (100.00%) | 26 3 | IXSCAN EMP_TEST | 3 of 10000 ( .03%) | 6 Predicate Information 3 - START ( TO_DATE(?, 'YYYY-MM-DD') <= Q1.DATE_OF_BIRTH) START (Q1.SUBSIDIARY_ID = ?) STOP (Q1.DATE_OF_BIRTH <= TO_DATE(?, 'YYYY-MM-DD')) STOP (Q1.SUBSIDIARY_ID = ?) SARG (Q1.SUBSIDIARY_ID = ?)In DB2 werden Zugriffsprädikate durch
STARTund/oderSTOPgekennzeichnet, Filterprädikate mitSARG.- Oracle
-------------------------------------------------------------- |Id | Operation | Name | Rows | Cost | -------------------------------------------------------------- | 0 | SELECT STATEMENT | | 1 | 4 | |*1 | FILTER | | | | | 2 | TABLE ACCESS BY INDEX ROWID| EMPLOYEES | 1 | 4 | |*3 | INDEX RANGE SCAN | EMP_TEST | 2 | 2 | -------------------------------------------------------------- Predicate Information (identified by operation id): --------------------------------------------------- 1 - filter(:END_DT >= :START_DT) 3 - access(DATE_OF_BIRTH >= :START_DT AND DATE_OF_BIRTH <= :END_DT) filter(SUBSIDIARY_ID = :SUBS_ID)- PostgreSQL
QUERY PLAN ------------------------------------------------------------------- Index Scan using emp_test on employees (cost=0.01..8.59 rows=1 width=16) Index Cond: (date_of_birth >= to_date('1971-01-01','YYYY-MM-DD')) AND (date_of_birth <= to_date('1971-01-10','YYYY-MM-DD')) AND (subsidiary_id = 27::numeric)Die PostgreSQL Datenbank zeigt Index-Zugriffs- bzw. Filterprädikate nicht direkt im Ausführungsplan an. Die Spalten im Bereich
Index Condwerden jedoch in der Reihenfolge des Indexes angezeigt—die beiden Bedingungen aufDATE_OF_BIRTHwerden zuerst angezeigt, dann erst die Bedingung aufSUBSIDIARY_ID. Wenn man weiß, dass die Prädikate die einer Bereichsbedingung folgen, nicht als Zugriffsprädikate genutzt werden können, kann man daraus schließen, dass die Bedingung mitSUBSIDIARY_IDnur als Filterprädikat genutzt werden kann. Siehe „PostgreSQL Zugriffs- und Filterprädikate unterscheiden“ für weitere Details.- SQL Server
|--Nested Loops(Inner Join) |--Index Seek(OBJECT:emp_test, | SEEK: (date_of_birth, subsidiary_id) | >= ('1971-01-01', 27) | AND (date_of_birth, subsidiary_id) | <= ('1971-01-10', 27), | WHERE:subsidiary_id=27 | ORDERED FORWARD) |--RID Lookup(OBJECT:employees, SEEK:Bmk1000=Bmk1000 LOOKUP ORDERED FORWARD)SQL Server 2012 zeigt die Seek-Prädikate (=Zugriffsprädikate) in der Row-Values Syntax an.
Der Hinweis ist im „Predicate Information“-Bereich der INDEX RANGE SCAN-Operation zu sehen. Dort werden die Bedingungen der where-Klausel als access- oder filter-Prädikate bezeichnet. Dadurch sagt uns die Datenbank, wie sie die einzelnen Bedingungen nutzt.
Beachte
Der Ausführungsplan wurde zum besseren Verständnis vereinfacht. In „Oracle Zugriffs- und Filterprädikate unterscheiden“ wird erklärt, worauf man bei der Bestimmung von Zugriffs- und Filterprädikaten genau achten muss.
Der Ausführungsplan zeigt nur die Bedingungen auf der Spalte DATE_OF_BIRTH als Zugriffsprädikate an. Das heißt, nur sie begrenzen den durchsuchten Indexbereich. Die Spalte DATE_OF_BIRTH ist also die erste im Index. Die SUBSIDIARY_ID-Bedingung wird lediglich als Filter benutzt.
Wichtig
Zugriffsprädikate (access predicates) drücken die Start- und Stopp-Bedingungen einer Indexsuche aus. Sie definieren den durchsuchten Indexbereich.
Index-Filterprädikate (filter predicates) werden nur während des Verfolgens der Blattknoten-Liste verwendet. Sie schränken den durchsuchten Indexbereich nicht ein.
Der Anhang zeigt, wie man Zugriffsprädikate bei MySQL, SQL Server und PostgreSQL erkennt.
Dreht man die Indexdefinition um, kann die Datenbank alle Bedingungen als Zugriffsprädikate nutzen.
- DB2
----------------------------------------------------- ID | Operation | Rows | Cost 1 | RETURN | | 13 2 | FETCH EMPLOYEES | 3 of 3 (100.00%) | 13 3 | IXSCAN EMP_TEST2 | 3 of 10000 ( .03%) | 6 Predicate Information 3 - START (Q1.SUBSIDIARY_ID = ?) START ( TO_DATE(?, 'YYYY-MM-DD') <= Q1.DATE_OF_BIRTH) STOP (Q1.SUBSIDIARY_ID = ?) STOP (Q1.DATE_OF_BIRTH <= TO_DATE(?, 'YYYY-MM-DD'))- Oracle
--------------------------------------------------------------- | Id | Operation | Name | Rows | Cost | --------------------------------------------------------------- | 0 | SELECT STATEMENT | | 1 | 3 | |* 1 | FILTER | | | | | 2 | TABLE ACCESS BY INDEX ROWID| EMPLOYEES | 1 | 3 | |* 3 | INDEX RANGE SCAN | EMP_TEST2 | 1 | 2 | --------------------------------------------------------------- Predicate Information (identified by operation id): --------------------------------------------------- 1 - filter(:END_DT >= :START_DT) 3 - access(SUBSIDIARY_ID = :SUBS_ID AND DATE_OF_BIRTH >= :START_DT AND DATE_OF_BIRTH <= :END_T)- PostgreSQL
QUERY PLAN ------------------------------------------------------------------- Index Scan using emp_test on employees (cost=0.01..8.29 rows=1 width=17) Index Cond: (subsidiary_id = 27::numeric) AND (date_of_birth >= to_date('1971-01-01', 'YYYY-MM-DD')) AND (date_of_birth <= to_date('1971-01-10', 'YYYY-MM-DD'))Die PostgreSQL Datenbank zeigt Index-Zugriffs- bzw. Filterprädikate nicht direkt im Ausführungsplan an. Die Spalten im Bereich
Index Condwerden jedoch in der Reihenfolge des Indexes angezeigt—die Bedingung aufSUBSIDIARY_IDwird zuerst angezeigt, dann erst die Bedingungen aufDATE_OF_BIRTH. In diesem Fall können alle Bedingungen als Zugriffsprädikat genutzt werden. Siehe „PostgreSQL Zugriffs- und Filterprädikate unterscheiden“ für weitere Details.- SQL Server
|--Nested Loops(Inner Join) |--Index Seek(OBJECT:emp_test, | SEEK: subsidiary_id=27 | AND date_of_birth >= '1971-01-01' | AND date_of_birth <= '1971-01-10' | ORDERED FORWARD) |--RID Lookup(OBJECT:employees), SEEK:Bmk1000=Bmk1000 LOOKUP ORDERED FORWARD)
Zu guter Letzt gibt es noch den between-Operator. Damit kann man die Ober- und Untergrenze einer Suche auf einmal angeben:
DATE_OF_BIRTH BETWEEN '01-JAN-71'
AND '10-JAN-71'between-Abfragen schließen die angegebenen Werte immer ein. So, als würde man die Operatoren kleiner-gleich (<=) und größer-gleich (>=) verwenden:
DATE_OF_BIRTH >= '01-JAN-71'
AND DATE_OF_BIRTH <= '10-JAN-71'
