Demi jointures
Vous êtes confronté au cas suivant : remonter les infos d'une table A et seulement d'une table A mais uniquement si des informations correspondantes existent dans une table B. On peut dans ce cas parler de SEMI ou DEMI JOINTURE entre A et B.
Je montre qu'écrire une telle requête avec IN ou EXISTS n'a pas d'incidence sur les performances avec un optimiseur moderne basé sur des statistiques comme le planner de PostgreSQL.
Qu'en est-il si vous choisissez d'écrire cette requête avec une jointure classique (JOIN) ?
Nous allons utiliser les tables GEANTS (table mère) et LANCERS (table fille). Démonstration avec PostgreSQL 11 en commençant par une demi jointure entre GEANTS et LANCERS avec un filtrage très sélectif sur LANCERS :
select version();
version
---------------------------------------------------------------------------------------------------------------
PostgreSQL 11.1 (Debian 11.1-1.pgdg+1) on x86_64-pc-linux-gnu, compiled by gcc (Debian 8.2.0-9) 8.2.0, 64-bit
create table geants( idg integer generated by default as identity, dtn timestamp, taille smallint, devise varchar(128), dicton varchar(128), berserk boolean);
CREATE TABLE
with recursive serie(i) as
(select 1
UNION ALL
select i + 1 from serie where i < 1000)
insert into geants(dtn, taille, devise, dicton, berserk)
select
current_date - 3650 - trunc(random() * 10000 + 1)::int,
200 + (trunc(random() * 200 + 1)),
upper(md5(random()::text)),upper(md5(random()::text)),
case when random() < 0.001 then true else false end
from serie;
INSERT 0 1000
create table lancers ( dtl timestamp, idg integer, perf integer );
CREATE TABLE
insert into lancers(dtl, idg, perf) with recursive serie(i) as (select 1 UNION ALL select i + 1 from serie where i < 100000)
select current_timestamp - ((i || ' minutes')::interval)::interval, trunc(random() * 1000 + 1), trunc(random() * 100000 + 1) from serie;
INSERT 0 100000
create unique index geants_pk on geants(idg);
CREATE INDEX
alter table geants add primary key using index geants_pk;
ALTER TABLE
alter table lancers add foreign key(idg) references geants(idg) on delete cascade;
ALTER TABLE
create index lancers_i1 on lancers(idg);
CREATE INDEX
create index lancers_br1 on lancers using brin(dtl);
CREATE INDEX
-- tous les geants (idg / taille) ayant lance aujourd'hui ou hier
explain select distinct g.idg, g.taille
from geants g join lancers l on (g.idg = l.idg)
where l.dtl > current_date - 1
order by 1, 2;
QUERY PLAN
-------------------------------------------------------------------------------------------------
Sort (cost=1019.80..1022.30 rows=1000 width=6)
Sort Key: g.idg, g.taille
-> HashAggregate (cost=959.97..969.97 rows=1000 width=6)
Group Key: g.idg, g.taille
-> Hash Join (cost=50.15..947.65 rows=2465 width=6)
Hash Cond: (l.idg = g.idg)
-> Bitmap Heap Scan on lancers l (cost=12.65..903.65 rows=2465 width=4)
Recheck Cond: (dtl > (CURRENT_DATE - 1))
-> Bitmap Index Scan on lancers_br1 (cost=0.00..12.04 rows=20000 width=0)
Index Cond: (dtl > (CURRENT_DATE - 1))
-> Hash (cost=25.00..25.00 rows=1000 width=6)
-> Seq Scan on geants g (cost=0.00..25.00 rows=1000 width=6)
select distinct g.idg, g.taille
from geants g join lancers l on (g.idg = l.idg)
where l.dtl > current_date - 1
order by 1, 2;
...
Temps : 22,917 ms
Temps : 22,704 ms
Temps : 22,738 ms
explain select g.idg, g.taille
from geants g
where g.idg in (select idg from lancers l where l.dtl > current_date - 1)
order by 1,2;
QUERY PLAN
-------------------------------------------------------------------------------------------------------
Sort (cost=1019.05..1021.55 rows=1000 width=6)
Sort Key: g.idg, g.taille
-> Hash Join (cost=930.47..969.22 rows=1000 width=6)
Hash Cond: (g.idg = l.idg)
-> Seq Scan on geants g (cost=0.00..25.00 rows=1000 width=6)
-> Hash (cost=919.00..919.00 rows=918 width=4)
-> HashAggregate (cost=909.82..919.00 rows=918 width=4)
Group Key: l.idg
-> Bitmap Heap Scan on lancers l (cost=12.65..903.65 rows=2465 width=4)
Recheck Cond: (dtl > (CURRENT_DATE - 1))
-> Bitmap Index Scan on lancers_br1 (cost=0.00..12.04 rows=20000 width=0)
Index Cond: (dtl > (CURRENT_DATE - 1))
select g.idg, g.taille
from geants g
where g.idg in (select idg from lancers l where l.dtl > current_date - 1)
order by 1,2;
Temps : 21,949 ms
Temps : 21,829 ms
Temps : 21,871 ms
select g.idg, g.taille
from geants g
where exists (select 1 from lancers l where l.idg = g.idg and l.dtl > current_date - 1)
order by 1,2;
Temps : 22,090 ms
Temps : 22,455 ms
Temps : 21,557 ms
Dans ce premier cas, il n'y a guère de différence de performance entre une syntaxe basée sur JOIN et une syntaxe basée sur IN ou EXISTS, au niveau des estimations comme des résultats observés. Le filtrage effectué sur LANCERS est efficace grâce à l'index BRIN et l'élimination des quelques doublons est rapide.
Que se passe-t-il à présent si ce filtrage sur LANCERS n'est plus effectué ?
-- tous les geants (idg / taille) ayant deja lance
explain select distinct g.idg, g.taille
from geants g join lancers l on (g.idg = l.idg);
QUERY PLAN
------------------------------------------------------------------------------
HashAggregate (cost=2342.11..2352.11 rows=1000 width=6)
Group Key: g.idg, g.taille
-> Hash Join (cost=37.50..1842.11 rows=100000 width=6)
Hash Cond: (l.idg = g.idg)
-> Seq Scan on lancers l (cost=0.00..1541.00 rows=100000 width=4)
-> Hash (cost=25.00..25.00 rows=1000 width=6)
-> Seq Scan on geants g (cost=0.00..25.00 rows=1000 width=6)
select distinct g.idg, g.taille
from geants g join lancers l on (g.idg = l.idg);
Temps : 90,347 ms
Temps : 87,447 ms
Temps : 89,867 ms
explain select g.idg, g.taille
from geants g join lancers l on (g.idg = l.idg)
group by g.idg, g.taille;
QUERY PLAN
------------------------------------------------------------------------------
HashAggregate (cost=2092.11..2102.11 rows=1000 width=6)
Group Key: g.idg
-> Hash Join (cost=37.50..1842.11 rows=100000 width=6)
Hash Cond: (l.idg = g.idg)
-> Seq Scan on lancers l (cost=0.00..1541.00 rows=100000 width=4)
-> Hash (cost=25.00..25.00 rows=1000 width=6)
-> Seq Scan on geants g (cost=0.00..25.00 rows=1000 width=6)
select g.idg, g.taille
from geants g join lancers l on (g.idg = l.idg)
group by g.idg, g.taille;
Temps : 83,725 ms
Temps : 82,985 ms
Temps : 83,315 ms
explain select g.idg, g.taille
from geants g
where g.idg in (select idg from lancers l);
QUERY PLAN
-----------------------------------------------------------------------------------------
Nested Loop Semi Join (cost=0.29..398.89 rows=1000 width=6)
-> Seq Scan on geants g (cost=0.00..25.00 rows=1000 width=6)
-> Index Only Scan using lancers_i1 on lancers l (cost=0.29..3.40 rows=100 width=4)
Index Cond: (idg = g.idg)
select g.idg, g.taille
from geants g
where g.idg in (select idg from lancers l);
Temps : 14,843 ms
Temps : 15,102 ms
Temps : 14,913 ms
select g.idg, g.taille
from geants g
where exists (select 1 from lancers l where l.idg = g.idg);
Temps : 15,205 ms
Temps : 14,898 ms
Temps : 14,943 ms
Cette fois, la différence dans les coûts estimés comme dans les résultats observés est très importante. Le syntaxe basée sur IN ou EXISTS est ici bien plus efficace que la syntaxe basée sur JOIN (facteur de 1 à 5). Avec JOIN, c'est une jointure par hachage avec aggrégation des résultats qui est choisie par le planner. Avec IN ou EXISTS, ce sont des boucles imbriquées avec un parcours d'index seul tirant parti de l'indexation de la clé étrangère de LANCERS. Il est à noter que la détection d'un cas de DEMI JOINTURE apparaît de manière lisible dans le plan (NESTED LOOP SEMI JOIN).
Que se passe-t-il à présent dans le cas d'une demi jointure entre LANCERS et GEANTS ?
-- tous les lancers (perf) des geants berserk puis non berserk
explain select l.perf
from lancers l join geants g on (l.idg = g.idg)
where g.berserk;
QUERY PLAN
---------------------------------------------------------------------------------
Nested Loop (cost=5.07..517.48 rows=200 width=4)
-> Seq Scan on geants g (cost=0.00..25.00 rows=2 width=4)
Filter: berserk
-> Bitmap Heap Scan on lancers l (cost=5.07..245.24 rows=100 width=8)
Recheck Cond: (idg = g.idg)
-> Bitmap Index Scan on lancers_i1 (cost=0.00..5.04 rows=100 width=0)
Index Cond: (idg = g.idg)
Temps : 2,738 ms
Temps : 3,014 ms
Temps : 2,823 ms
explain select l.perf
from lancers l
where l.idg in (select idg from geants where berserk);
QUERY PLAN
---------------------------------------------------------------------------------
Nested Loop (cost=5.07..517.48 rows=200 width=4)
-> Seq Scan on geants (cost=0.00..25.00 rows=2 width=4)
Filter: berserk
-> Bitmap Heap Scan on lancers l (cost=5.07..245.24 rows=100 width=8)
Recheck Cond: (idg = geants.idg)
-> Bitmap Index Scan on lancers_i1 (cost=0.00..5.04 rows=100 width=0)
Index Cond: (idg = geants.idg)
select l.perf
from lancers l
where l.idg in (select idg from geants where berserk);
Temps : 2,696 ms
Temps : 2,692 ms
Temps : 2,518 ms
select l.perf
from lancers l
where exists (select 1 from geants g where g.idg = l.idg and berserk);
Temps : 2,591 ms
Temps : 2,675 ms
Temps : 2,729 ms
explain select l.perf
from lancers l join geants g on (l.idg = g.idg)
where not g.berserk;
QUERY PLAN
-----------------------------------------------------------------------
Hash Join (cost=37.48..1842.09 rows=99800 width=4)
Hash Cond: (l.idg = g.idg)
-> Seq Scan on lancers l (cost=0.00..1541.00 rows=100000 width=8)
-> Hash (cost=25.00..25.00 rows=998 width=4)
-> Seq Scan on geants g (cost=0.00..25.00 rows=998 width=4)
Filter: (NOT berserk)
select l.perf
from lancers l join geants g on (l.idg = g.idg)
where not g.berserk;
Temps : 93,028 ms
Temps : 92,826 ms
Temps : 92,620 ms
explain select l.perf
from lancers l
where l.idg in (select idg from geants where not berserk);
QUERY PLAN
-----------------------------------------------------------------------
Hash Join (cost=37.48..1842.09 rows=99800 width=4)
Hash Cond: (l.idg = geants.idg)
-> Seq Scan on lancers l (cost=0.00..1541.00 rows=100000 width=8)
-> Hash (cost=25.00..25.00 rows=998 width=4)
-> Seq Scan on geants (cost=0.00..25.00 rows=998 width=4)
Filter: (NOT berserk)
select l.perf
from lancers l
where l.idg in (select idg from geants where not berserk);
Temps : 93,013 ms
Temps : 93,174 ms
Temps : 93,121 ms
select l.perf
from lancers l
where exists (select 1 from geants g where g.idg = l.idg and not berserk);
Temps : 92,825 ms
Temps : 92,932 ms
Temps : 93,089 ms
Dans ce sens, bien sûr pas de doublon à éliminer au niveau des jeux de résultats aprés la jointure. Les coûts estimés et les performances réellement observées sont identiques que la requête soit basée sur JOIN ou sur IN/EXISTS.
Conclusion
Le débat IN vs EXISTS n'a plus réellement de sens avec le planner de PostgreSQL.
En revanche, utiliser une jointure (JOIN) lorsque vous souhaitez en fait réaliser une demi-jointure n'est PAS toujours optimal.
Le planner effectuera potentiellement un travail d'optimisation plus efficace si la requête est écrite avec IN ou EXISTS. C'est globalement toujours valable mais c'est évidemment plus important dans le cas d'une demi jointure entre une table mère (1) et une table fille (0..N) avec par ailleurs un filtrage peu sélectif ou inexistant.
Mise à jour : 12/12/2018