Index composites et deuxième colonne

Efficacité des index composites

(sujet préalablement traité avec la version 9.5)

La malédiction de la 2ème colonne...

      Dans "SQL, au coeur des performances" traduit en français par Guillaume Lelarge de Dalibo, Markus Winand écrit : "l’ordre d’un index à deux colonnes ressemble à l’ordre d’un annuaire téléphonique : il est tout d’abord trié par le nom, puis par le prénom. Cela signifie qu’un index à deux colonnes ne permet pas une recherche sur la deuxième colonne seule. Cela reviendrait à rechercher dans un annuaire en ayant seulement le prénom."
      De ce raisonnement découle la règle suivante : si des recherches sont parfois faites sur les 2 colonnes et parfois sur 1 des 2 colonnes d’un index concaténé alors la 1ère colonne (leading column) de l’index doit être celle sur laquelle sont parfois faites les recherches portant sur une seule colonne. Bien sûr, le principe général est juste et si vous êtes développeur je vous conseille de l’appliquer. Cependant, dans certains cas, les moteurs Oracle et PostgreSQL peuvent bénéficier d’un index même si la recherche porte uniquement sur la 2ème colonne. Il faut savoir que c’est possible, ne serait-ce que pour ne pas se satisfaire d’un plan qui comprendrait "INDEX QUELQUE CHOSE" en se disant qu’il est automatiquement optimal.
      Pour reprendre l’exemple de l’annuaire téléphonique, imaginons une table geants avec notamment des colonnes "nmge" (nom du géant) et "pmge" (prénom du géant).
      Dans un premier temps nous allons supposer qu’il n’y a que 2 noms de géants possibles les MOGOR et les GORMI. Les prénoms "pmge" sont en revanche choisis aléatoirement. On veut obtenir la valeur de la colonne "valge1" uniquement grâce à un prénom alors que la table n’a pas d’index, puis un index geants_i1 sur (pmge, nmge) et enfin un index geants_i2 sur (pmge).
      Tout d’abord Oracle Database 18c dans sa version Express Edition :

Connecte a : Oracle Database 18c Express Edition Release 18.0.0.0.0 - Production Version 18.4.0.0.0 create table geants( idge INTEGER GENERATED BY DEFAULT AS IDENTITY PRIMARY KEY, nmge CHARACTER VARYING(128), pmge CHARACTER VARYING(128), devge CHARACTER VARYING(128), valge1 CHARACTER VARYING(128), valge2 CHARACTER VARYING(128), valge3 CHARACTER VARYING(128), valge4 CHARACTER VARYING(128)); Table creee. insert into geants(nmge, pmge, devge, valge1, valge2, valge3, valge4) with serie(i, r) as (select 1, dbms_random.value from dual UNION ALL select i + 1, dbms_random.value from serie where i < 100000) select case when r <= 0.5 then 'MOGOR' else 'GORMI' end, DBMS_RANDOM.string('x',32), DBMS_RANDOM.string('x',32), DBMS_RANDOM.string('x',32), DBMS_RANDOM.string('x',32), DBMS_RANDOM.string('x',32), DBMS_RANDOM.string('x',32) from serie; 100000 lignes creees. commit; Validation effectuee. EXEC DBMS_STATS.GATHER_TABLE_STATS(OWNNAME => 'CSS', TABNAME => 'GEANTS', cascade => TRUE); Procedure PL/SQL terminee avec succes. EXPLAIN PLAN FOR SELECT valge1 FROM geants WHERE pmge = 'ABCDE'; Explicite. SELECT * FROM table(dbms_xplan.display); PLAN_TABLE_OUTPUT Plan hash value: 2409905289 ---------------------------------------------------------------------------- | Id | Operation | Name | Rows | Bytes | Cost (%CPU)| Time | ---------------------------------------------------------------------------- | 0 | SELECT STATEMENT | | 1 | 66 | 854 (1)| 00:00:01 | |* 1 | TABLE ACCESS FULL| GEANTS | 1 | 66 | 854 (1)| 00:00:01 | ---------------------------------------------------------------------------- Predicate Information (identified by operation id): PLAN_TABLE_OUTPUT 1 - filter("PMGE"='ABCDE') CREATE INDEX geants_i1 ON geants(nmge, pmge); Index cree. EXEC DBMS_STATS.GATHER_TABLE_STATS(OWNNAME => 'CSS', TABNAME => 'GEANTS', cascade => TRUE); Procedure PL/SQL terminee avec succes. EXPLAIN PLAN FOR SELECT valge1 FROM geants WHERE pmge = 'ABCDE'; Explicite. SELECT * FROM table(dbms_xplan.display); PLAN_TABLE_OUTPUT Plan hash value: 143543663 ------------------------------------------------------------------------------------------------- | Id | Operation | Name | Rows | Bytes | Cost (%CPU)| Time | ------------------------------------------------------------------------------------------------- | 0 | SELECT STATEMENT | | 1 | 66 | 6 (0)| 00:00:01 | | 1 | TABLE ACCESS BY INDEX ROWID BATCHED| GEANTS | 1 | 66 | 6 (0)| 00:00:01 | |* 2 | INDEX SKIP SCAN | GEANTS_I1 | 1 | | 4 (0)| 00:00:01 | ------------------------------------------------------------------------------------------------- Predicate Information (identified by operation id): PLAN_TABLE_OUTPUT 2 - access("PMGE"='ABCDE') filter("PMGE"='ABCDE') CREATE INDEX geants_i2 ON geants(pmge); Index cree. EXEC DBMS_STATS.GATHER_TABLE_STATS(OWNNAME => 'CSS', TABNAME => 'GEANTS', cascade => TRUE); Procedure PL/SQL terminee avec succes. EXPLAIN PLAN FOR SELECT valge1 FROM geants WHERE pmge = 'ABCDE'; Explicite. SELECT * FROM table(dbms_xplan.display); PLAN_TABLE_OUTPUT Plan hash value: 1159007847 ------------------------------------------------------------------------------------------------- | Id | Operation | Name | Rows | Bytes | Cost (%CPU)| Time | ------------------------------------------------------------------------------------------------- | 0 | SELECT STATEMENT | | 1 | 66 | 3 (0)| 00:00:01 | | 1 | TABLE ACCESS BY INDEX ROWID BATCHED| GEANTS | 1 | 66 | 3 (0)| 00:00:01 | |* 2 | INDEX RANGE SCAN | GEANTS_I2 | 1 | | 1 (0)| 00:00:01 | ------------------------------------------------------------------------------------------------- Predicate Information (identified by operation id): PLAN_TABLE_OUTPUT 2 - access("PMGE"='ABCDE')

Que remarque-t-on ? Oracle est capable depuis la 9i de tirer parti de l’index composé geants_i1 en "sautant" la "leading column", on parle de "SKIP SCAN". Pour simplifier le moteur fait un RANGE SCAN pour chacune des valeurs possibles de la 1ère colonne, ce qui implique que cela n’est vraiment efficace que si la première colonne a une faible cardinalité. Le cas est donc extrêmeme favorable au SKIP SCAN qui permet ici un énorme gain par rapport au balayage complet de la table.
Qu'en est-il dans un cas beaucoup plus défavorable ? Nous allons générer complètement aléatoirement le contenu de la colonne "nmge", toujours avec Oracle Express Edition 18c :

create table geants( idge INTEGER GENERATED BY DEFAULT AS IDENTITY PRIMARY KEY, nmge CHARACTER VARYING(128), pmge CHARACTER VARYING(128), devge CHARACTER VARYING(128), valge1 CHARACTER VARYING(128), valge2 CHARACTER VARYING(128), valge3 CHARACTER VARYING(128), valge4 CHARACTER VARYING(128)); Table creee. insert into geants(nmge, pmge, devge, valge1, valge2, valge3, valge4) with serie(i) as (select 1 from dual UNION ALL select i + 1 from serie where i < 100000) select DBMS_RANDOM.string('x',5), DBMS_RANDOM.string('x',32), DBMS_RANDOM.string('x',32), DBMS_RANDOM.string('x',32), DBMS_RANDOM.string('x',32), DBMS_RANDOM.string('x',32), DBMS_RANDOM.string('x',32) from serie; 100000 lignes creees. commit; Validation effectuee. EXEC DBMS_STATS.GATHER_TABLE_STATS(OWNNAME => 'CSS', TABNAME => 'GEANTS', cascade => TRUE); Procedure PL/SQL terminee avec succes. EXPLAIN PLAN FOR SELECT valge1 FROM geants WHERE pmge = 'ABCDE'; Explicite. SELECT * FROM table(dbms_xplan.display); PLAN_TABLE_OUTPUT Plan hash value: 2409905289 ---------------------------------------------------------------------------- | Id | Operation | Name | Rows | Bytes | Cost (%CPU)| Time | ---------------------------------------------------------------------------- | 0 | SELECT STATEMENT | | 1 | 66 | 854 (1)| 00:00:01 | |* 1 | TABLE ACCESS FULL| GEANTS | 1 | 66 | 854 (1)| 00:00:01 | ---------------------------------------------------------------------------- Predicate Information (identified by operation id): --------------------------------------------------- PLAN_TABLE_OUTPUT 1 - filter("PMGE"='ABCDE') CREATE INDEX geants_i1 ON geants(nmge, pmge); Index cree. EXEC DBMS_STATS.GATHER_TABLE_STATS(OWNNAME => 'CSS', TABNAME => 'GEANTS', cascade => TRUE); Procedure PL/SQL terminee avec succes. EXPLAIN PLAN FOR SELECT valge1 FROM geants WHERE pmge = 'ABCDE'; Explicite. SELECT * FROM table(dbms_xplan.display); PLAN_TABLE_OUTPUT Plan hash value: 143543663 ------------------------------------------------------------------------------------------------- | Id | Operation | Name | Rows | Bytes | Cost (%CPU)| Time | ------------------------------------------------------------------------------------------------- | 0 | SELECT STATEMENT | | 1 | 66 | 704 (0)| 00:00:01 | | 1 | TABLE ACCESS BY INDEX ROWID BATCHED| GEANTS | 1 | 66 | 704 (0)| 00:00:01 | |* 2 | INDEX SKIP SCAN | GEANTS_I1 | 1 | | 702 (0)| 00:00:01 | ------------------------------------------------------------------------------------------------- Predicate Information (identified by operation id): PLAN_TABLE_OUTPUT 2 - access("PMGE"='ABCDE') filter("PMGE"='ABCDE') CREATE INDEX geants_i2 ON geants(pmge); Index cree. EXEC DBMS_STATS.GATHER_TABLE_STATS(OWNNAME => 'CSS', TABNAME => 'GEANTS', cascade => TRUE); Procedure PL/SQL terminee avec succes. EXPLAIN PLAN FOR SELECT valge1 FROM geants WHERE pmge = 'ABCDE'; Explicite. SELECT * FROM table(dbms_xplan.display); PLAN_TABLE_OUTPUT Plan hash value: 1159007847 ------------------------------------------------------------------------------------------------- | Id | Operation | Name | Rows | Bytes | Cost (%CPU)| Time | ------------------------------------------------------------------------------------------------- | 0 | SELECT STATEMENT | | 1 | 66 | 3 (0)| 00:00:01 | | 1 | TABLE ACCESS BY INDEX ROWID BATCHED| GEANTS | 1 | 66 | 3 (0)| 00:00:01 | |* 2 | INDEX RANGE SCAN | GEANTS_I2 | 1 | | 1 (0)| 00:00:01 | ------------------------------------------------------------------------------------------------- Predicate Information (identified by operation id): PLAN_TABLE_OUTPUT 2 - access("PMGE"='ABCDE')

Que remarque-t-on ? Encore une fois, Oracle réaliserait un "SKIP SCAN" avec l’index geants_i1 mais le coût estimé est proche de celui du balayage complet de la table, ce qui rend l’index quasi inutile dans ce cas. Dans tous les cas, voir "SKIP SCAN" dans un plan doit attirer votre attention. Est-ce une requête peu exécutée ou une requête fréquemment utilisée ? Le "SKIP SCAN" est-il suffisamment efficace pour qu’un index plus adapté ne soit pas nécessaire ?
Place à PostgreSQL à présent. Reprenons le 1er exemple avec la version 11 :

select version(); version ----------------------------------------------------------------------------------------------------------------------------------- PostgreSQL 11.4 (Ubuntu 11.4-1.pgdg18.04+1) on x86_64-pc-linux-gnu, compiled by gcc (Ubuntu 7.4.0-1ubuntu1~18.04.1) 7.4.0, 64-bit create table geants( idge INTEGER GENERATED BY DEFAULT AS IDENTITY PRIMARY KEY, nmge CHARACTER VARYING(128), pmge CHARACTER VARYING(128), devge CHARACTER VARYING(128), valge1 CHARACTER VARYING(128), valge2 CHARACTER VARYING(128), valge3 CHARACTER VARYING(128), valge4 CHARACTER VARYING(128)); CREATE TABLE insert into geants(nmge, pmge, devge, valge1, valge2, valge3, valge4) with recursive serie(i, r) as (select 1, random() UNION ALL select i + 1, random() from serie where i < 100000) select case when r <= 0.5 then 'MOGOR' else 'GORMI' end, upper(md5(random()::text)), upper(md5(random()::text)), upper(md5(random()::text)), upper(md5(random()::text)), upper(md5(random()::text)), upper(md5(random()::text)) from serie; INSERT 0 100000 commit; COMMIT analyze geants; ANALYZE EXPLAIN ANALYZE SELECT valge1 FROM geants WHERE pmge = 'ABCDE'; QUERY PLAN -------------------------------------------------------------------------------------------------------- Seq Scan on geants (cost=0.00..3089.10 rows=59 width=274) (actual time=15.285..15.285 rows=0 loops=1) Filter: ((pmge)::text = 'ABCDE'::text) Rows Removed by Filter: 100000 Planning Time: 0.072 ms Execution Time: 15.300 ms CREATE INDEX geants_i1 ON geants(nmge, pmge); CREATE INDEX EXPLAIN ANALYZE SELECT valge1 FROM geants WHERE pmge = 'ABCDE'; QUERY PLAN ------------------------------------------------------------------------------------------------------------------------ Index Scan using geants_i1 on geants (cost=0.42..3650.43 rows=1 width=33) (actual time=11.539..11.539 rows=0 loops=1) Index Cond: ((pmge)::text = 'ABCDE'::text) Planning Time: 0.125 ms Execution Time: 11.577 ms CREATE INDEX geants_i2 ON geants(pmge); CREATE INDEX EXPLAIN ANALYZE SELECT valge1 FROM geants WHERE pmge = 'ABCDE'; QUERY PLAN ------------------------------------------------------------------------------------------------------------------- Index Scan using geants_i2 on geants (cost=0.42..8.44 rows=1 width=33) (actual time=0.035..0.035 rows=0 loops=1) Index Cond: ((pmge)::text = 'ABCDE'::text) Planning Time: 0.139 ms Execution Time: 0.047 ms

Que remarque-t-on ? PostgreSQL a tiré parti de l’index mais le gain attendu (et obtenu) est inférieur à celui observé avec Oracle dans le même cas. En fait PostgreSQL a effectué un balayage complet de l’index geants_i1 et le gain par rapport à un balayage complet de la table provient seulement du fait que l’index a une taille inférieure à la table. En revanche, l’index geants_i2 est parcouru d’une manière tirant parti de sa structure et le temps de réponse est excellent.
Logiquement, puisque PostgreSQL réalise un balayage complet de l’index geants_i1, les résultats devaient être similaires si le nom est généré aléatoirement, au contraire de ce qui se passe avec Oracle :

Comme prévu, pas de différence entre les 2 cas avec PostgreSQL si l’index geants_i1 est utilisé pour une recherche portant uniquement sur "pmge". Il apporte un gain significatif par rapport à un balayage complet de la table mais il est bien moins efficace que l’index geants_i2.

Conclusion : Markus Winand avait tout à fait raison en énonçant le principal général. Certes, PostgreSQL et surtout Oracle dans certains cas favorables, peuvent tirer parti des index composés lorsqu’une recherche ne comporte pas la 1ère colonne comme critère. Mais ce n’est jamais aussi efficace qu’avec un index sur la colonne seule ou concaténé en fonction de ce type de recherche. Les exemples confirment bien que voir "INDEX" dans un plan n’est pas la garantie d’avoir obtenu le meilleur plan possible.

Efficacité des index composites

(sujet préalablement traité avec la version 9.5)

Mise à jour : 21/07/2019