par Guillaume Lelarge.

Plus grand, plus petit et entre


Le plus gros risque en terme de performances d'un INDEX RANGE SCAN est le parcours de nœuds feuilles. Du coup, la règle d'or de l'indexation est de conserver les intervalles parcourus aussi petits que possible. Vous pouvez le vérifier en vous demandant où le parcours d'un index commence et où il se termine.

Il est facile de répondre à cette question si la requête SQL mentionne explicitement les conditions de départ et d'arrivée :

SELECT prenom, nom, date_de_naissance
  FROM employes
 WHERE date_de_naissance >= TO_DATE(?, 'YYYY-MM-DD')
   AND date_de_naissance <= TO_DATE(?, 'YYYY-MM-DD')

Un index sur DATE_DE_NAISSANCE est seulement parcourue sur l'intervalle indiqué. Le parcours commence à la première date et se termine à la deuxième date. Nous ne pouvons pas diminuer l'intervalle parcouru.

Les conditions de départ et d'arrêt sont moins évidentes si une deuxième colonne est utilisée :

SELECT prenom, nom, date_de_naissance
  FROM employes
 WHERE date_de_naissance >= TO_DATE(?, 'YYYY-MM-DD')
   AND date_de_naissance <= TO_DATE(?, 'YYYY-MM-DD')
   AND id_supplementaire  = ?

Bien sûr, un index idéal doit couvrir les deux colonnes mais la question est de connaître l'ordre idéal.

Les graphes suivants montrent l'effet de l'ordre de la colonne sur l'intervalle parcouru dans l'index. Pour cette illustration, nous recherchons tous les employés de la société 27, nés entre le 1er janvier et le 9 janvier 1971.

La Figure 2.2 affiche un détail de l'index sur DATE_DE_NAISSANCE et ID_SUPPLEMENTAIRE, dans cet ordre. Par quel nœud feuille la base de données va-t-elle commencer son parcours ? ou autrement dit, à quel nœud feuille le parcours va-t-il s'arrêter ?

Figure 2.2 Parcours d'intervalle dans un index DATE_DE_NAISSANCE, ID_SUPPLEMENTAIRE

L'index est tout d'abord ordonné sur les dates de naissances. Ce n'est que si deux employés sont nés le même jour que ID_SUPPLEMENTAIRE est utilisé pour trier les enregistrements. Néanmoins, la requête couvre un intervalle de date. L'ordre de la colonne ID_SUPPLEMENTAIRE est inutile lors du parcours de l'arbre. Cela devient évident si vous comprenez qu'il n'y a pas d'enregistrements pour la société 27 dans les nœuds branches, bien qu'il y en ait dans les nœuds feuilles. Du coup, le filtre sur DATE_DE_NAISSANCE est la seule condition qui limite l'intervalle parcouru pour l'index. Cela commence avec la première entrée correspondant à la date de l'intervalle et se termine avec la dernière. Cela correspond aux cinq nœuds feuilles indiquées dans la Figure 2.2.

Le graphe est complètement différent si on inverse l'ordre des colonnes. La Figure 2.3 illustre le parcours si l'index commence avec la colonne ID_SUPPLEMENTAIRE.

Figure 2.3 Parcours d'intervalle avec l'index sur ID_SUPPLEMENTAIRE, DATE_DE_NAISSANCE

La différence tient dans le fait que l'opérateur d'égalité limite la première colonne d'index à une seule valeur. Dans l'intervalle pour cette valeur (ID_SUPPLEMENTAIRE 27), l'index est trié suivant la deuxième colonne, la date de naissance. Il n'y a donc pas besoin de visiter le premier nœud feuille car le nœud branche indique déjà qu'il n'y a pas d'employés pour la société 27, qui serait né après le 25 juin 1969 dans le premier nœud feuille.

Le parcours de l'arbre amène directement au deuxième nœud feuille. Dans ce cas, toutes les conditions de la clause where limitent l'intervalle d'index parcouru, pour que le parcours se termine sur le même nœud feuille.

Astuce

Règle d'or : indexer pour l'égalité, puis pour les intervalles.

La différence réelle de performances dépend des données et du critère de recherche. La différence est négligeable si le filtre sur DATE_DE_NAISSANCE est très sélectif. Plus l'intervalle de date est important, plus la différence de performances le sera aussi.

Avec cet exemple, nous pouvons aussi démonter ce mythe qui cherche à faire croire que la colonne la plus sélective doit être à la première colonne d'un index. Si nous regardons les graphes et si nous considérons la sélectivité de la première colonne seulement, nous voyons que les deux conditions correspondent à 13 enregistrements. C'est le cas que l'on filtre par la colonne DATE_DE_NAISSANCE seulement ou par la colonne ID_SUPPLEMENTAIRE seulement. La sélectivité n'a pas d'utilité ici mais un ordre de colonnes apporte plus de performances que l'autre.

Pour optimiser les performances, il est très important de connaître l'intervalle d'index parcouru. Avec la plupart des bases de données, vous pouvez le voir dans le plan d'exécution... si vous savez ce que vous cherchez. Le plan d'exécution suivant provenant de la base de données Oracle indique sans ambiguïté que l'index EMP_TEST commence avec la colonne DATE_DE_NAISSANCE.

Oracle

--------------------------------------------------------------
|Id | Operation                    | Name      | Rows | Cost |
--------------------------------------------------------------
| 0 | SELECT STATEMENT             |           |    1 |    4 |
|*1 |  FILTER                      |           |      |      |
| 2 |   TABLE ACCESS BY INDEX ROWID| EMPLOYES  |    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_DE_NAISSANCE >= :START_DT 
       AND DATE_DE_NAISSANCE <= :END_DT)
    filter(ID_SUPPLEMENTAIRE  = :SUBS_ID)

PostgreSQL

                            QUERY PLAN
-------------------------------------------------------------------
Index Scan using emp_test on employes
  (cost=0.01..8.59 rows=1 width=16)
  Index Cond: (date_de_naissance >= to_date('1971-01-01','YYYY-MM-DD'))
          AND (date_de_naissance <= to_date('1971-01-10','YYYY-MM-DD'))
          AND (id_supplementaire = 27::numeric)

The PostgreSQL database does not indicate index access and filter predicates in the execution plan. However, the Index Cond section lists the columns in order of the index definition. In that case, we see the two DATE_OF_BIRTH predicates first, than the SUBSIDIARY_ID. Knowing that any predicates following a range condition cannot be an access predicate the SUBSIDIARY_ID must be a filter predicate. See « Distinguer les prédicats d'accès et de filtre » for more details.

SQL Server

|--Nested Loops(Inner Join)
   |--Index Seek(OBJECT:emp_test,
   |               SEEK:       (date_de_naissance, id_supplementaire)
   |                        >= ('1971-01-01', 27)
   |                    AND    (date_de_naissance, id_supplementaire)
   |                        <= ('1971-01-10', 27),
   |              WHERE:id_supplementaire=27
   |            ORDERED FORWARD)
   |--RID Lookup(OBJECT:employes,
                   SEEK:Bmk1000=Bmk1000
                 LOOKUP ORDERED FORWARD)

SQL Server 2012 shows the seek predicates (=access predicates) using the row-value syntax.

L'information du prédicat pour l'opération INDEX RANGE SCAN donne l'infor­mation recherchée. Elle identifie les conditions de la clause where comme des prédicats accès ou filtre. C'est de cette façon que la base de données nous indique comment elle utilise chaque condition.

Remarque

Le plan d'exécution a été simplifié pour qu'il soit plus clair. explique les détails de la section « Predicate Information » dans un plan d'exécution Oracle.

Les conditions sur la colonne DATE_DE_NAISSANCE sont celles listées comme prédicat accès ; elles se limitent à l'intervalle d'index parcouru. Du coup, la colonne DATE_DE_NAISSANCE est la première colonne de l'index EMP_TEST. La colonne ID_SUPPLEMENTAIRE est utilisée seulement comme un filtre.

Important

Les prédicats accès sont les conditions de départ et d'arrivée pour une recherche par index. Ils définissent l'intervalle parcouru sur l'index.

Les prédicats filtres d'un index sont appliqués seulement lors du parcours des nœuds feuilles. Ils ne peuvent pas diminuer l'intervalle parcouru de l'index.

L'annexe explique comment reconnaître les prédicats index dans MySQL, SQL Server et PostgreSQL.

La base de données peut utiliser toutes les conditions comme prédicats accès si nous changeons la définition de l'index :

Oracle

---------------------------------------------------------------
| Id | Operation                    | Name      | Rows | Cost |
---------------------------------------------------------------
|  0 | SELECT STATEMENT             |           |    1 |    3 |
|* 1 |  FILTER                      |           |      |      |
|  2 |   TABLE ACCESS BY INDEX ROWID| EMPLOYES  |    1 |    3 |
|* 3 |    INDEX RANGE SCAN          | EMP_TEST2 |    1 |    2 |
---------------------------------------------------------------

Predicate Information (identified by operation id):
---------------------------------------------------
1 - filter(:END_DT >= :START_DT)
3 - access(ID_SUPPLEMENTAIRE  = :SUBS_ID
       AND DATE_DE_NAISSANCE >= :START_DT
       AND DATE_DE_NAISSANCE <= :END_T)

PostgreSQL

                            QUERY PLAN
-------------------------------------------------------------------
Index Scan using emp_test on employes
   (cost=0.01..8.29 rows=1 width=17)
   Index Cond: (id_supplementaire = 27::numeric)
           AND (date_de_naissance >= to_date('1971-01-01', 'YYYY-MM-DD'))
           AND (date_de_naissance <= to_date('1971-01-10', 'YYYY-MM-DD'))

The PostgreSQL database does not indicate index access and filter predicates in the execution plan. However, the Index Cond section lists the columns in order of the index definition. In that case, we see the SUBSIDIARY_ID predicate first, than the two on DATE_OF_BIRTH. As there is no further column filtered after the range condition on DATE_OF_BIRTH we know that all predicates can be used as access predicate. See « Distinguer les prédicats d'accès et de filtre » for more details.

SQL Server

|--Nested Loops(Inner Join)
   |--Index Seek(OBJECT:emp_test,
   |               SEEK: id_supplementaire=27
   |                 AND date_de_naissance >= '1971-01-01'
   |                 AND date_de_naissance <= '1971-01-10'
   |            ORDERED FORWARD)
   |--RID Lookup(OBJECT:employes),
                   SEEK:Bmk1000=Bmk1000
                 LOOKUP ORDERED FORWARD)

Enfin, il existe un opérateur between. Il vous permet de spécifier les limites haute et basse en une seule condition :

DATE_DE_NAISSANCE BETWEEN '01-JAN-71'
                      AND '10-JAN-71'

Notez que between inclut toujours les valeurs indiquées, tout comme les opérateurs inférieur ou égal (<=) et supérieur ou égal (>=) :

    DATE_DE_NAISSANCE >= '01-JAN-71' 
AND DATE_DE_NAISSANCE <= '10-JAN-71'

À propos de l'auteur

Photo de Markus Winand

Markus Winand teaches efficient SQL—inhouse and online. He minimizes the development time using modern SQL and optimizes the runtime with smart indexing—for that he also published the book SQL Performance Explained.

“Use The Index, Luke!” by Markus Winand and translated by Guillaume Lelarge is licensed under a Creative Commons Attribution-Noncommercial-No Derivative Works 3.0 Unported License.
Mentions légales | Contact | NO WARRANTY | Marque déposée | Privacy | CC-BY-NC-ND 3.0 license