Efficacité des index composites
(sujet mis à jour avec la version 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 é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 perso avec comme colonnes id INTEGER, nom CHARACTER VARYING(128), prenom CHARACTER VARYING(128), ville CHARACTER VARYING(128), adr CHARACTER VARYING(128), val1 CHARACTER VARYING(128), val2 CHARACTER VARYING(128), val3 CHARACTER VARYING(128). Dans un premier temps nous allons supposer qu’il n’y a que 2 noms de famille possibles les LI et les LEFEVRE. Les prénoms sont en revanche choisis aléatoirement. On veut trouver les "val1" uniquement gràce à un prénom alors que la table n’a pas d’index, puis un index perso_i1 sur (prenom, nom) et enfin un index perso_i2 sur (nom, prenom).
Tout d’abord Oracle Database 11.2.0.2 dans sa version Express Edition :
Connected to:
Oracle Database 11g Express Edition Release 11.2.0.2.0 - 64bit Production
create table perso(
id INTEGER PRIMARY KEY,
nom CHARACTER VARYING(128),
prenom CHARACTER VARYING(128),
ville CHARACTER VARYING(128),
adr CHARACTER VARYING(128),
val1 CHARACTER VARYING(128),
val2 CHARACTER VARYING(128),
val3 CHARACTER VARYING(128));
Table created.
create sequence perso_id;
Sequence created.
declare
x number := dbms_random.value();
begin
for i in 1..100000 loop
if x <= 0.5 then
insert into perso values(perso_id.nextval, 'LI', dbms_random.string('P', 32), dbms_random.string('P', 8), dbms_random.string('P', 32), dbms_random.string('P', 32), dbms_random.string('P', 32), dbms_random.string('P', 32));
else
insert into perso values(perso_id.nextval, 'LEFEVRE', dbms_random.string('P', 32), dbms_random.string('P', 8), dbms_random.string('P', 32), dbms_random.string('P', 32), dbms_random.string('P', 32), dbms_random.string('P', 32));
end if;
x := dbms_random.value();
end loop;
end;
PL/SQL procedure successfully completed.
commit;
Commit complete.
EXEC DBMS_STATS.GATHER_TABLE_STATS(OWNNAME => 'SYSTEM', TABNAME => 'PERSO', cascade => TRUE);
PL/SQL procedure successfully completed.
EXPLAIN PLAN FOR
SELECT val1 FROM perso WHERE prenom = 'ABCDEFGH';
Explained.
SELECT * FROM table(dbms_xplan.display);
PLAN_TABLE_OUTPUT
--------------------------------------------------------------------------------
Plan hash value: 2016054137
---------------------------------------------------------------------------
| Id | Operation | Name | Rows | Bytes | Cost (%CPU)| Time |
---------------------------------------------------------------------------
| 0 | SELECT STATEMENT | | 1 | 66 | 716 (1)| 00:00:09 |
|* 1 | TABLE ACCESS FULL| PERSO | 1 | 66 | 716 (1)| 00:00:09 |
---------------------------------------------------------------------------
Predicate Information (identified by operation id):
---------------------------------------------------
PLAN_TABLE_OUTPUT
--------------------------------------------------------------------------------
1 - filter("PRENOM"='ABCDEFGH')
CREATE INDEX perso_i1 ON perso(nom, prenom);
Index created.
EXEC DBMS_STATS.GATHER_TABLE_STATS(OWNNAME => 'SYSTEM', TABNAME => 'PERSO', cascade => TRUE);
PL/SQL procedure successfully completed.
EXPLAIN PLAN FOR
SELECT val1 FROM perso WHERE prenom = 'ABCDEFGH';
Explained.
SELECT * FROM table(dbms_xplan.display);
SQL> SELECT * FROM table(dbms_xplan.display);
PLAN_TABLE_OUTPUT
-----------------------------------------------------------------------------------------
Plan hash value: 2842113710
----------------------------------------------------------------------------------------
| Id | Operation | Name | Rows | Bytes | Cost (%CPU)| Time |
----------------------------------------------------------------------------------------
| 0 | SELECT STATEMENT | | 1 | 66 | 6 (0)| 00:00:01 |
| 1 | TABLE ACCESS BY INDEX ROWID| PERSO | 1 | 66 | 6 (0)| 00:00:01 |
|* 2 | INDEX SKIP SCAN | PERSO_I1 | 1 | | 4 (0)| 00:00:01 |
----------------------------------------------------------------------------------------
Predicate Information (identified by operation id):
PLAN_TABLE_OUTPUT
-----------------------------------------------------------------------------------------
---------------------------------------------------
2 - access("PRENOM"='ABCDEFGH')
filter("PRENOM"='ABCDEFGH')
DROP INDEX perso_i1;
Index dropped.
CREATE INDEX perso_i2 ON perso(prenom, nom);
Index created.
EXEC DBMS_STATS.GATHER_TABLE_STATS(OWNNAME => 'SYSTEM', TABNAME => 'PERSO', cascade => TRUE);
PL/SQL procedure successfully completed.
Explained.
EXPLAIN PLAN FOR
SELECT val1 FROM perso WHERE prenom = 'ABCDEFGH';
SELECT * FROM table(dbms_xplan.display);
PLAN_TABLE_OUTPUT
-----------------------------------------------------------------------------------------
Plan hash value: 3456061618
----------------------------------------------------------------------------------------
| Id | Operation | Name | Rows | Bytes | Cost (%CPU)| Time |
----------------------------------------------------------------------------------------
| 0 | SELECT STATEMENT | | 1 | 66 | 4 (0)| 00:00:01 |
| 1 | TABLE ACCESS BY INDEX ROWID| PERSO | 1 | 66 | 4 (0)| 00:00:01 |
|* 2 | INDEX RANGE SCAN | PERSO_I2 | 1 | | 2 (0)| 00:00:01 |
----------------------------------------------------------------------------------------
Predicate Information (identified by operation id):
PLAN_TABLE_OUTPUT
2 - access("PRENOM"='ABCDEFGH')
Que remarque-t-on ? Oracle est capable depuis la 9i de tirer parti de l’index composé perso_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é. Dans cet exemple le cas est extrêmeme favorable au SKIP SCAN qui est très efficace et permet un énorme gain par rapport au balayage complet de la table. Dans la réalité d’une table contenant des noms et des prénoms ce ne serait évidemment pas le cas.
Pour illustrer cela, nous allons générer complètement aléatoirement les noms et les prénoms, toujours avec Oracle Express Edition 11gR2 :
Connected to:
Oracle Database 11g Express Edition Release 11.2.0.2.0 - 64bit Production
create table perso(
id INTEGER PRIMARY KEY,
nom CHARACTER VARYING(128),
prenom CHARACTER VARYING(128),
ville CHARACTER VARYING(128),
adr CHARACTER VARYING(128),
val1 CHARACTER VARYING(128),
val2 CHARACTER VARYING(128),
val3 CHARACTER VARYING(128));
Table created.
create sequence perso_id;
Sequence created.
begin
for i in 1..100000 loop
insert into perso values(perso_id.nextval, dbms_random.string('P', 5), dbms_random.string('P', 32), dbms_random.string('P', 8), dbms_random.string('P', 32), dbms_random.string('P', 32), dbms_random.string('P', 32), dbms_random.string('P', 32));
end loop;
end;
/
PL/SQL procedure successfully completed.
commit;
Commit complete.
EXEC DBMS_STATS.GATHER_TABLE_STATS(OWNNAME => 'SYSTEM', TABNAME => 'PERSO', cascade => TRUE);
PL/SQL procedure successfully completed.
EXPLAIN PLAN FOR
SELECT val1 FROM perso WHERE prenom = 'ABCDEFGH';
Explained.
SELECT * FROM table(dbms_xplan.display);
PLAN_TABLE_OUTPUT
---------------------------------------------------------------------------
Plan hash value: 2016054137
---------------------------------------------------------------------------
| Id | Operation | Name | Rows | Bytes | Cost (%CPU)| Time |
---------------------------------------------------------------------------
| 0 | SELECT STATEMENT | | 1 | 66 | 716 (1)| 00:00:09 |
|* 1 | TABLE ACCESS FULL| PERSO | 1 | 66 | 716 (1)| 00:00:09 |
---------------------------------------------------------------------------
Predicate Information (identified by operation id):
---------------------------------------------------
PLAN_TABLE_OUTPUT
---------------------------------------------------------------------------
1 - filter("PRENOM"='ABCDEFGH')
CREATE INDEX perso_i1 ON perso(nom, prenom);
Index created.
EXEC DBMS_STATS.GATHER_TABLE_STATS(OWNNAME => 'SYSTEM', TABNAME => 'PERSO', cascade => TRUE);
PL/SQL procedure successfully completed.
EXPLAIN PLAN FOR
SELECT val1 FROM perso WHERE prenom = 'ABCDEFGH';
Explained.
SELECT * FROM table(dbms_xplan.display);
PLAN_TABLE_OUTPUT
-----------------------------------------------------------------------------------------
Plan hash value: 2842113710
----------------------------------------------------------------------------------------
| Id | Operation | Name | Rows | Bytes | Cost (%CPU)| Time |
----------------------------------------------------------------------------------------
| 0 | SELECT STATEMENT | | 1 | 66 | 702 (0)| 00:00:09 |
| 1 | TABLE ACCESS BY INDEX ROWID| PERSO | 1 | 66 | 702 (0)| 00:00:09 |
|* 2 | INDEX SKIP SCAN | PERSO_I1 | 1 | | 701 (0)| 00:00:09 |
----------------------------------------------------------------------------------------
Predicate Information (identified by operation id):
PLAN_TABLE_OUTPUT
-----------------------------------------------------------------------------------------
---------------------------------------------------
2 - access("PRENOM"='ABCDEFGH')
filter("PRENOM"='ABCDEFGH')
DROP INDEX perso_i1;
Index dropped.
CREATE INDEX perso_i2 ON perso(prenom, nom);
Index created.
EXEC DBMS_STATS.GATHER_TABLE_STATS(OWNNAME => 'SYSTEM', TABNAME => 'PERSO', cascade => TRUE);
PL/SQL procedure successfully completed.
Explained.
EXPLAIN PLAN FOR
SELECT val1 FROM perso WHERE prenom = 'ABCDEFGH';
SELECT * FROM table(dbms_xplan.display);
PLAN_TABLE_OUTPUT
-----------------------------------------------------------------------------------------
Plan hash value: 3456061618
----------------------------------------------------------------------------------------
| Id | Operation | Name | Rows | Bytes | Cost (%CPU)| Time |
----------------------------------------------------------------------------------------
| 0 | SELECT STATEMENT | | 1 | 66 | 3 (0)| 00:00:01 |
| 1 | TABLE ACCESS BY INDEX ROWID| PERSO | 1 | 66 | 3 (0)| 00:00:01 |
|* 2 | INDEX RANGE SCAN | PERSO_I2 | 1 | | 2 (0)| 00:00:01 |
----------------------------------------------------------------------------------------
Predicate Information (identified by operation id):
PLAN_TABLE_OUTPUT
-----------------------------------------------------------------------------------------
---------------------------------------------------
2 - access("PRENOM"='ABCDEFGH')
Que remarque-t-on ? Encore une fois Oracle réaliserait un "SKIP SCAN" avec l’index perso_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 9.5 :
select version();
version
-------------------------------------------------------------
PostgreSQL 9.5.4, compiled by Visual C++ build 1800, 64-bit
(1 ligne)
create table perso(
id SERIAL PRIMARY KEY,
nom CHARACTER VARYING(128),
prenom CHARACTER VARYING(128),
ville CHARACTER VARYING(128),
adr CHARACTER VARYING(128),
val1 CHARACTER VARYING(128),
val2 CHARACTER VARYING(128),
val3 CHARACTER VARYING(128));
CREATE TABLE
do
$$
begin
for i in 1..100000 loop
INSERT INTO perso(nom, prenom, ville, adr, val1, val2, val3) VALUES (CASE WHEN random() <= 0.5 THEN 'LEFEVRE' ELSE 'LI' END, md5(random()::text), substr(md5(random()::text),1,8), md5(random()::text), md5(random()::text), md5(random()::text), md5(random()::text)) ;
end loop;
end$$;
DO
postgres=# ANALYZE perso;
ANALYZE
postgres=# EXPLAIN ANALYZE SELECT val1 FROM perso WHERE prenom = 'ABCDEFGH';
QUERY PLAN
-----------------------------------------------------------------------------------------------------
Seq Scan on perso (cost=0.00..3948.00 rows=1 width=33) (actual time=41.526..41.526 rows=0 loops=1)
Filter: ((prenom)::text = 'ABCDEFGH'::text)
Rows Removed by Filter: 100000
Planning time: 0.122 ms
Execution time: 41.565 ms
CREATE INDEX perso_i1 ON perso(nom, prenom);
CREATE INDEX
EXPLAIN ANALYZE SELECT val1 FROM perso WHERE prenom = 'ABCDEFGH';
QUERY PLAN
----------------------------------------------------------------------------------------------------------------------
Index Scan using perso_i1 on perso (cost=0.42..3862.43 rows=1 width=33) (actual time=14.647..14.647 rows=0 loops=1)
Index Cond: ((prenom)::text = 'ABCDEFGH'::text)
Planning time: 0.161 ms
Execution time: 14.695 ms
\d+
Liste des relations
Schéma | Nom | Type | Propriétaire | Taille | Description
--------+---------------+----------+--------------+------------+-------------
public | perso | table | postgres | 21 MB |
\di+
Liste des relations
Schéma | Nom | Type | Propriétaire | Table | Taille | Description
--------+------------+-------+--------------+---------+---------+-------------
public | perso_i1 | index | postgres | perso | 6216 kB |
DROP INDEX perso_i1;
DROP INDEX
CREATE INDEX perso_i2 ON perso(prenom, nom);
CREATE INDEX
\di+
Liste des relations
Schéma | Nom | Type | Propriétaire | Table | Taille | Description
--------+------------+-------+--------------+---------+---------+-------------
public | perso_i2 | index | postgres | perso | 6224 kB |
EXPLAIN ANALYZE SELECT val1 FROM perso WHERE prenom = 'ABCDEFGH';
QUERY PLAN
-----------------------------------------------------------------------------------------------------------------
Index Scan using perso_i2 on perso (cost=0.42..8.44 rows=1 width=33) (actual time=0.051..0.051 rows=0 loops=1)
Index Cond: ((prenom)::text = 'ABCDEFGH'::text)
Planning time: 0.160 ms
Execution time: 0.091 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 perso_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 perso_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 perso_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 :
select version();
version
-------------------------------------------------------------
PostgreSQL 9.5.4, compiled by Visual C++ build 1800, 64-bit
(1 ligne)
create table perso(
id SERIAL PRIMARY KEY,
nom CHARACTER VARYING(128),
prenom CHARACTER VARYING(128),
ville CHARACTER VARYING(128),
adr CHARACTER VARYING(128),
val1 CHARACTER VARYING(128),
val2 CHARACTER VARYING(128),
val3 CHARACTER VARYING(128));
CREATE TABLE
do
$$
begin
for i in 1..100000 loop
INSERT INTO perso(nom, prenom, ville, adr, val1, val2, val3) VALUES (substr(md5(random()::text),1,5), md5(random()::text), substr(md5(random()::text),1,8), md5(random()::text), md5(random()::text), md5(random()::text), md5(random()::text)) ;
end loop;
end$$;
DO
postgres=# ANALYZE perso;
ANALYZE
postgres=# EXPLAIN ANALYZE SELECT val1 FROM perso WHERE prenom = 'ABCDEFGH';
QUERY PLAN
-----------------------------------------------------------------------------------------------------
Seq Scan on perso (cost=0.00..3882.00 rows=1 width=33) (actual time=40.878..40.878 rows=0 loops=1)
Filter: ((prenom)::text = 'ABCDEFGH'::text)
Rows Removed by Filter: 100000
Planning time: 0.142 ms
Execution time: 40.929 ms
CREATE INDEX perso_i1 ON perso(nom, prenom);
CREATE INDEX
EXPLAIN ANALYZE SELECT val1 FROM perso WHERE prenom = 'ABCDEFGH';
QUERY PLAN
----------------------------------------------------------------------------------------------------------------------
Index Scan using perso_i1 on perso (cost=0.42..3650.43 rows=1 width=33) (actual time=13.892..13.892 rows=0 loops=1)
Index Cond: ((prenom)::text = 'ABCDEFGH'::text)
Planning time: 0.171 ms
Execution time: 13.938 ms
\d+
Liste des relations
Schéma | Nom | Type | Propriétaire | Taille | Description
--------+---------------+----------+--------------+------------+-------------
public | perso | table | postgres | 21 MB |
\di+
Liste des relations
Schéma | Nom | Type | Propriétaire | Table | Taille | Description
--------+------------+-------+--------------+---------+---------+-------------
public | perso_i1 | index | postgres | perso | 5792 kB |
DROP INDEX perso_i1;
DROP INDEX
CREATE INDEX perso_i2 ON perso(prenom, nom);
CREATE INDEX
\di+
Liste des relations
Schéma | Nom | Type | Propriétaire | Table | Taille | Description
--------+------------+-------+--------------+---------+---------+-------------
public | perso_i2 | index | postgres | perso | 5792 kB |
EXPLAIN ANALYZE SELECT val1 FROM perso WHERE prenom = 'ABCDEFGH';
QUERY PLAN
----------------------------------------------------------------------------------------------------------------------
Index Scan using perso_i2 on perso (cost=0.42..8.44 rows=1 width=33) (actual time=0.116..0.116 rows=0 loops=1)
Index Cond: ((prenom)::text = 'ABCDEFGH'::text)
Planning time: 0.563 ms
Execution time: 0.154 ms
Comme prévu, pas de différence entre les 2 cas avec PostgreSQL si l’index perso_i1 est utilisé pour une recherche portant uniquement sur le prénom. Il apporte un gain significatif par rapport à un balayage complet de la table mais il est bien moins efficace que l’index perso_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.
Mise à jour : 03/09/2016