Größer, Kleiner und BETWEEN


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?

Bei unseren Schlulungs-, Tuning-, und
Literaturangeboten ist für jeden was dabei

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 Da­tums­bereich 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 bei­den 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.

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 Cond werden jedoch in der Reihenfolge des Indexes angezeigt—die beiden Bedingungen auf DATE_OF_BIRTH werden zuerst angezeigt, dann erst die Bedingung auf SUBSIDIARY_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 mit SUBSIDIARY_ID nur als Filterprädikat genutzt werden kann. Siehe Abschnitt 2.3 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 Abschnitt 1.3 wird erklärt, worauf man bei der Be­stim­mung 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.

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 Cond werden jedoch in der Reihenfolge des Indexes angezeigt—die Bedingung auf SUBSIDIARY_ID wird zuerst angezeigt, dann erst die Bedingungen auf DATE_OF_BIRTH. In diesem Fall können alle Bedingungen als Zugriffsprädikat genutzt werden. Siehe Abschnitt 2.3 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'

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.