Efficacité des index composites
(sujet préalablement traité avec les versions 9.5 et 11)
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 écrivait : "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.
Reprenons l’exemple classique de l’annuaire téléphonique que les plus anciens ont connu, 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, utilisons Oracle Database 19c Standard Edition 2 (le comportement est le même avec l'Enterprise Edition) :
Connected to:
Oracle Database 19c Standard Edition 2 Release 19.0.0.0.0 - Production
Version 19.13.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 created.
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 rows created.
commit;
Commit complete.
EXEC DBMS_STATS.GATHER_TABLE_STATS(OWNNAME => 'XXX', TABNAME => 'GEANTS', cascade => TRUE);
PL/SQL procedure successfully completed.
EXPLAIN PLAN FOR
SELECT valge1 FROM geants WHERE pmge = 'ABCDE';
Explained.
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 | 855 (1)| 00:00:01 |
|* 1 | TABLE ACCESS FULL| GEANTS | 1 | 66 | 855 (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 created.
EXEC DBMS_STATS.GATHER_TABLE_STATS(OWNNAME => 'XXX', TABNAME => 'GEANTS', cascade => TRUE);
PL/SQL procedure successfully completed.
EXPLAIN PLAN FOR
SELECT valge1 FROM geants WHERE pmge = 'ABCDE';
Explained.
SELECT * FROM table(dbms_xplan.display);
PLAN_TABLE_OUTPUT
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
Plan hash value: 3300993151
-----------------------------------------------------------------------------------------
| Id | Operation | Name | Rows | Bytes | Cost (%CPU)| Time |
-----------------------------------------------------------------------------------------
| 0 | SELECT STATEMENT | | 1 | 66 | 5 (0)| 00:00:01 |
| 1 | TABLE ACCESS BY INDEX ROWID| GEANTS | 1 | 66 | 5 (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 created.
EXEC DBMS_STATS.GATHER_TABLE_STATS(OWNNAME => 'XXX', TABNAME => 'GEANTS', cascade => TRUE);
PL/SQL procedure successfully completed.
EXPLAIN PLAN FOR
SELECT valge1 FROM geants WHERE pmge = 'ABCDE';
Explained.
SELECT * FROM table(dbms_xplan.display);
PLAN_TABLE_OUTPUT
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
Plan hash value: 1519430429
-----------------------------------------------------------------------------------------
| Id | Operation | Name | Rows | Bytes | Cost (%CPU)| Time |
-----------------------------------------------------------------------------------------
| 0 | SELECT STATEMENT | | 1 | 66 | 2 (0)| 00:00:01 |
| 1 | TABLE ACCESS BY INDEX ROWID| GEANTS | 1 | 66 | 2 (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êmement 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 19c Standard Edition 2 :
drop table geants;
Table dropped.
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 created.
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 rows created.
commit;
Commit complete.
EXEC DBMS_STATS.GATHER_TABLE_STATS(OWNNAME => 'XXX', TABNAME => 'GEANTS', cascade => TRUE);
PL/SQL procedure successfully completed.
EXPLAIN PLAN FOR
SELECT valge1 FROM geants WHERE pmge = 'ABCDE';
Explained.
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 | 855 (1)| 00:00:01 |
|* 1 | TABLE ACCESS FULL| GEANTS | 1 | 66 | 855 (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 created.
EXEC DBMS_STATS.GATHER_TABLE_STATS(OWNNAME => 'XXX', TABNAME => 'GEANTS', cascade => TRUE);
PL/SQL procedure successfully completed.
EXPLAIN PLAN FOR
SELECT valge1 FROM geants WHERE pmge = 'ABCDE';
Explained.
SELECT * FROM table(dbms_xplan.display);
PLAN_TABLE_OUTPUT
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
Plan hash value: 3300993151
-----------------------------------------------------------------------------------------
| Id | Operation | Name | Rows | Bytes | Cost (%CPU)| Time |
-----------------------------------------------------------------------------------------
| 0 | SELECT STATEMENT | | 1 | 66 | 704 (0)| 00:00:01 |
| 1 | TABLE ACCESS BY INDEX ROWID| 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 created.
EXEC DBMS_STATS.GATHER_TABLE_STATS(OWNNAME => 'XXX', TABNAME => 'GEANTS', cascade => TRUE);
PL/SQL procedure successfully completed.
EXPLAIN PLAN FOR
SELECT valge1 FROM geants WHERE pmge = 'ABCDE';
Explained.
SELECT * FROM table(dbms_xplan.display);
PLAN_TABLE_OUTPUT
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
Plan hash value: 1519430429
-----------------------------------------------------------------------------------------
| Id | Operation | Name | Rows | Bytes | Cost (%CPU)| Time |
-----------------------------------------------------------------------------------------
| 0 | SELECT STATEMENT | | 1 | 66 | 3 (0)| 00:00:01 |
| 1 | TABLE ACCESS BY INDEX ROWID| 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. Un commit de Peter Geoghegan du 4 avril 2025 introduit les "skip scan", reprenons le 1er exemple avec la version 18devel :
select version();
version
------------------------------------------------------------------------------------------------------------------------------------------------------------
PostgreSQL 18devel (Debian 18~~devel.20250405-1.pgdg120+~20250405.2227.g683df3f) on x86_64-pc-linux-gnu, compiled by gcc (Debian 12.2.0-14) 12.2.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..4192.00 rows=1 width=33) (actual time=13.591..13.592 rows=0.00 loops=1)
Filter: ((pmge)::text = 'ABCDE'::text)
Rows Removed by Filter: 100000
Buffers: shared hit=2942
Planning:
Buffers: shared hit=22 read=2
Planning Time: 0.213 ms
Execution Time: 13.612 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..17.29 rows=1 width=33) (actual time=0.196..0.197 rows=0.00 loops=1)
Index Cond: ((pmge)::text = 'ABCDE'::text)
Index Searches: 5
Buffers: shared hit=6 read=11
Planning:
Buffers: shared hit=9 read=1
Planning Time: 0.253 ms
Execution Time: 0.217 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.055..0.056 rows=0.00 loops=1)
Index Cond: ((pmge)::text = 'ABCDE'::text)
Index Searches: 1
Buffers: shared read=3
Planning:
Buffers: shared hit=6 read=1
Planning Time: 0.267 ms
Execution Time: 0.075 ms
Que remarque-t-on ? Dans mes tests précédents avec les versions 9.5 et 11, PostgreSQL effectuait un parcours complet de l’index geants_i1. Le gain par rapport à un balayage complet de la table provenait seulement du fait que l’index a une taille inférieure à la table. Ce n'est plus le cas, la fonctionnalité introduite par la version 18 est opérationnelle et utile : PostgreSQL tire à présent pleinement parti de la structure de l’index. Le gain attendu comme obtenu est similaire à celui observé avec Oracle dans le même cas. L’index geants_i2 fait toujours logiquement encore mieux bien sûr.
Comment se comporte PostgreSQL lorsque le nom est généré aléatoirement, un cas bien plus défavorable au "skip scan" ? Démonstration, toujours avec PostgreSQL 18devel :
drop table geants;
DROP TABLE
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) as
(select 1
UNION ALL
select i + 1 from serie where i < 100000)
select
substr(upper(md5(random()::text)),1,5),
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..4192.00 rows=1 width=33) (actual time=12.879..12.880 rows=0.00 loops=1)
Filter: ((pmge)::text = 'ABCDE'::text)
Rows Removed by Filter: 100000
Buffers: shared hit=2942
Planning:
Buffers: shared hit=13
Planning Time: 0.165 ms
Execution Time: 12.899 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..3634.43 rows=1 width=33) (actual time=8.999..9.000 rows=0.00 loops=1)
Index Cond: ((pmge)::text = 'ABCDE'::text)
Index Searches: 1
Buffers: shared read=717
Planning:
Buffers: shared hit=7 read=1
Planning Time: 0.270 ms
Execution Time: 9.020 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.057..0.057 rows=0.00 loops=1)
Index Cond: ((pmge)::text = 'ABCDE'::text)
Index Searches: 1
Buffers: shared read=3
Planning:
Buffers: shared hit=4 read=1
Planning Time: 0.292 ms
Execution Time: 0.079 ms
Cette fois, pas de différence significative de performance avec ce qui était observé dans les versions 9.5 et 11. PostgreSQL tire toujours parti de l'index geants_i1 mais le gain attendu comme obtenu est bien plus limité qu'il ne l'était dans le cas favorable au "skip scan". L'index geants_i2 est toujours ici immensément plus efficace pour cette requête.
Conclusion : Markus Winand avait tout à fait raison en énonçant le principe général. Cependant, dans certains cas favorables, Oracle >= 9i et PostgreSQL à partir de la version 18, peuvent tirer largement parti des index composés lorsqu’une recherche ne comporte pas la 1ère colonne comme critère. C'est appréciable de ne pas avoir à créer un index spécialisé lorsqu'un filtrage particulier est peu souvent effectué. Les index doivent être mis à jour et consomment des ressources lors de la manipulation de données (insert, update, delete, merge). Ils prennent de la place sur le stockage permanent comme en mémoire vive et créer trop d'index peut même être contre-productif pour les requêtes, comme je le montre dans cette page sur le stockage orienté colonne. Toutefois, il faut tout de même aussi retenir, pour les filtrages ne comportant pas la première colonne d'un index b-tree, que cet index pourra être utilisé via un balayage complet n'utilisant pas sa structure ou même par un "skip scan", mais que ce n’est jamais aussi efficace qu’avec un index sur la colonne seule ou concaténé en fonction de ce type de recherche. Si un filtrage est très fréquemment utilisé, il faut toujours créer l'index le plus adapté : les exemples confirment bien que voir "INDEX" dans un plan n’est pas la garantie d’avoir obtenu le meilleur plan possible.
Mise à jour : 06/04/2025