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 Condsection lists the columns in order of the index definition. In that case, we see the twoDATE_OF_BIRTHpredicates first, than theSUBSIDIARY_ID. Knowing that any predicates following a range condition cannot be an access predicate theSUBSIDIARY_IDmust 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'information 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. « Distinguer les prédicats d'accès et de filtre » 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'))- 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'
