Jointures complexes, opérateurs ensemblistes

Un petit coup de pouce au planner

      Tout ce qui suit est inspiré d'un cas réel rencontré sur une base de production.
      Il y a du changement dans les clans de géants (table GEANTS). Ils lancent toujours des rochers (table LANCERS) mais ils ont mis en place un nouveau système pour gérer leurs identités tout en n'abandonnant pas complètement leur ancien système. Les tables GEANTS et LANCERS ont ainsi toujours la colonne idg (INTEGER) mais aussi la colonne idgu (UUID).
      Tous les géants n'ont pas encore reçu un nouvel identifiant au niveau de la table GEANTS.
      En ce qui concerne la table LANCERS, les performances sont parfois enregistrées avec l'ancien système basé sur idg, parfois avec le nouveau système basé sur l'idgu et parfois dans les deux systèmes.
      Contexte :

select version(); version -------------------------------------------------------------------------------------------------------------------------------------------- PostgreSQL 10.2 (Ubuntu 10.2-1.pgdg16.04+1) on x86_64-pc-linux-gnu, compiled by gcc (Ubuntu 5.4.0-6ubuntu1~16.04.4) 5.4.0 20160609, 64-bit (1 ligne) create table geants( idg integer generated by default as identity primary key, idgu uuid unique, genre char(1), taille smallint, masse smallint, actif boolean, devise varchar(128), pw smallint, heureux boolean, couleur varchar(8), veteran boolean, clan smallint, gabarit varchar(8), revenu integer, pm smallint, berserk boolean, tutelaire smallint, ere varchar(10), cyclope boolean); CREATE TABLE with recursive serie(i, r1) as (select 100000, random() UNION ALL select i - 1, random() from serie where i > 1) insert into geants(idgu, genre, taille, masse, actif, devise, pw, heureux, couleur, veteran, clan, gabarit, revenu, pm, berserk, tutelaire, ere, cyclope) select case when random() <= 0.75 then uuid_generate_v4() else null end, case when random() < 0.45 then 'M' else 'F' end, 200 + (trunc(random() * 200 + 1)), 300 + (trunc(random() * 200 + 1)), case when random() < 0.01 then false when random() > 0.5 and random() < 0.99 then false else true end, upper(md5(random()::text)), (trunc(random()*100 + 1)), case when random() < 0.1 then false else true end, case when r1 <= 0.29998 then 'GRIS' when r1 <= 0.59998 then 'NOIR' else 'BLEU' end, case when random() < 0.9 then false else true end, (trunc(random()*1000 + 1)), case when r1 <= 0.29999 then 'PETIT' when r1 <= 0.59999 then 'MOYEN' else 'GRAND' end, (trunc(random()*1000000 + 1)), (trunc(random()*10 + 1)), case when r1 <= 0.3 then true when r1 <= 0.6 then false else null end, (trunc(random()*10 + 1)), case when r1 <= 0.30001 then 'TAUREAU' when r1 <= 0.60001 then 'LICORNE' else 'DRAGON' end, case when r1 <= 0.30002 then true when r1 <= 0.60002 then false else null end from serie; INSERT 0 100000 create table lancers(dtl timestamp, idg integer references geants(idg), idgu uuid references geants(idgu), perf integer); CREATE TABLE WITH serie(i, r1, r2) AS (SELECT generate_series(100000000,1,-1), random(), random()) insert into lancers(dtl, idg, idgu, perf) select current_timestamp - (i || ' minutes')::interval, case when r1 <= 0.1 and (select idgu from geants where idg = trunc(r2 * 100000 + 1)::int) is not null then case when random() <= 0.1 then trunc(r2 * 100000 + 1)::int else null end else trunc(r2 * 100000 + 1)::int end, case when r1 <= 0.1 then (select idgu from geants where idg = trunc(r2 * 100000 + 1)::int) end, case when random() <= 0.0001 then 50000 + trunc(random() * 50000 + 1) else trunc(random() * 50000 + 1) end from serie; INSERT 0 100000000 create unique index lancers_i1 on lancers(dtl, idg, idgu); CREATE INDEX create index lancers_fk1 on lancers(idg); CREATE INDEX create index lancers_fk2 on lancers(idgu); CREATE INDEX \d+ Liste des relations Schéma | Nom | Type | Propriétaire | Taille | Description --------+----------------+----------+--------------+------------+------------- public | geants | table | postgres | 12 MB | public | geants_idg_seq | séquence | postgres | 8192 bytes | public | lancers | table | postgres | 4336 MB | (3 lignes) create statistics geants_couleur_gabarit_ere_berserk_cyclope(dependencies, ndistinct) on couleur, gabarit, ere, berserk, cyclope from geants; CREATE STATISTICS analyze geants; ANALYZE analyze lancers; ANALYZE


      Comme dans la page consacrée aux statistiques étendues, nous allons déterminer la performance moyenne de tous les géants "PETITS TAUREAUX GRIS BERSERKS CYCLOPES".
      Première idée, réaliser une jointure avec une condition comprenant un OR :

explain select g.idg, g.idgu, g.devise, avg(l.perf) from geants g join lancers l on (g.idg = l.idg or g.idgu = l.idgu) where g.couleur = 'GRIS' and g.gabarit = 'PETIT' and g.ere = 'TAUREAU' and berserk and cyclope group by g.idg; QUERY PLAN ------------------------------------------------------------------------------------------------------------------------------------------------------------------------ Finalize GroupAggregate (cost=1024.38..22275663.02 rows=23668 width=85) Group Key: g.idg -> Gather Merge (cost=1024.38..22275130.49 rows=47336 width=85) Workers Planned: 2 -> Partial GroupAggregate (cost=24.36..22268666.72 rows=23668 width=85) Group Key: g.idg -> Nested Loop (cost=24.36..22218760.14 rows=9933979 width=57) -> Parallel Index Scan using geants_pkey on geants g (cost=0.29..3930.46 rows=9862 width=53) Filter: (berserk AND cyclope AND ((couleur)::text = 'GRIS'::text) AND ((gabarit)::text = 'PETIT'::text) AND ((ere)::text = 'TAUREAU'::text)) -> Bitmap Heap Scan on lancers l (cost=24.06..2241.99 rows=1058 width=24) Recheck Cond: ((g.idg = idg) OR (g.idgu = idgu)) -> BitmapOr (cost=24.06..24.06 rows=1058 width=0) -> Bitmap Index Scan on lancers_fk1 (cost=0.00..18.39 rows=960 width=0) Index Cond: (g.idg = idg) -> Bitmap Index Scan on lancers_fk2 (cost=0.00..5.14 rows=98 width=0) Index Cond: (g.idgu = idgu) \timing -- environnement SSD select g.idg, g.idgu, g.devise, avg(l.perf) from geants g join lancers l on (g.idg = l.idg or g.idgu = l.idgu) where g.couleur = 'GRIS' and g.gabarit = 'PETIT' and g.ere = 'TAUREAU' and berserk and cyclope group by g.idg; Durée : 64017,556 ms (01:04,018) ... Durée : 63588,611 ms (01:03,589) ... Durée : 63487,252 ms (01:03,487) -- environnement HDD archa├»que, RAM insuffisante select g.idg, g.idgu, g.devise, avg(l.perf) from geants g join lancers l on (g.idg = l.idg or g.idgu = l.idgu) where g.couleur = 'GRIS' and g.gabarit = 'PETIT' and g.ere = 'TAUREAU' and berserk and cyclope group by g.idg; Durée : 58643569,524 ms (16:17:23,570)


      Le planner choisit d'effectuer la jointure entre GEANTS et LANCERS à l'aide de boucles imbriquées (NESTED LOOP). Les index de LANCERS sont utilisés de manière assez élaborée pour créer dynamiquement des structures bitmap et réaliser le OR. Le temps d'exécution global est assez décevant avec la configuration basée sur du stockage SSD (un peu plus d'une minute) et catastrophique avec la configuration basée sur un stockage très lent (plus de 16 heures).
      La meilleure solution serait bien sûr de clarifier ce double système d'identification. Il faudrait par exemple affecter un idgu à chaque géant puis mettre à jour la table lancers et supprimer complètement la possibilité d'enregistrer les performances avec idg. Ou encore laisser tomber ce nouveau système, peu importe.
      Les géants sont costauds et nous ne pouvons pas vraiment les contraindre à effectuer ces modifications donc, en attendant de disposer d'une solution pérenne, nous allons tenter d'aider le planner en modifiant la requête. L'idée va être d'effectuer 2 sous-requêtes, ici à l'aide de CTE (common table expressions, with queries) :

      Nous allons ensuite réaliser une union des 2 jeux de résultats et appliquer une fonction de regroupement sur l'ensemble.
      Démonstration :

explain with lancers_nouveau_systeme as (select g.idg, g.idgu, g.devise, sum(l.perf) somme, count(1) compte from geants g join lancers l on (g.idgu = l.idgu) where g.couleur = 'GRIS' and g.gabarit = 'PETIT' and g.ere = 'TAUREAU' and berserk and cyclope group by g.idg), lancers_uniquement_ancien_systeme as (select g.idg, g.idgu, g.devise, sum(l.perf) somme, count(1) compte from geants g join lancers l on (g.idg = l.idg) where g.couleur = 'GRIS' and g.gabarit = 'PETIT' and g.ere = 'TAUREAU' and berserk and cyclope and l.idgu is null group by g.idg) select idg, idgu, devise, sum(somme)/sum(compte) from (select * from lancers_nouveau_systeme union all select * from lancers_uniquement_ancien_systeme) ua group by idg, idgu, devise; QUERY PLAN -------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- HashAggregate (cost=3132705.23..3132788.08 rows=4734 width=326) Group Key: lancers_nouveau_systeme.idg, lancers_nouveau_systeme.idgu, lancers_nouveau_systeme.devise CTE lancers_nouveau_systeme -> Finalize GroupAggregate (cost=1586765.00..1587475.04 rows=23668 width=69) Group Key: g.idg -> Sort (cost=1586765.00..1586883.34 rows=47336 width=69) Sort Key: g.idg -> Gather (cost=1576176.42..1581146.70 rows=47336 width=69) Workers Planned: 2 -> Partial HashAggregate (cost=1575176.42..1575413.10 rows=23668 width=69) Group Key: g.idg -> Hash Join (cost=3639.85..1501213.92 rows=9861667 width=57) Hash Cond: (l.idgu = g.idgu) -> Parallel Seq Scan on lancers l (cost=0.00..971532.67 rows=41666667 width=20) -> Hash (cost=3344.00..3344.00 rows=23668 width=53) -> Seq Scan on geants g (cost=0.00..3344.00 rows=23668 width=53) Filter: (berserk AND cyclope AND ((couleur)::text = 'GRIS'::text) AND ((gabarit)::text = 'PETIT'::text) AND ((ere)::text = 'TAUREAU'::text)) CTE lancers_uniquement_ancien_systeme -> Finalize GroupAggregate (cost=1542981.73..1543691.77 rows=23668 width=69) Group Key: g_1.idg -> Sort (cost=1542981.73..1543100.07 rows=47336 width=69) Sort Key: g_1.idg -> Gather (cost=1532393.16..1537363.44 rows=47336 width=69) Workers Planned: 2 -> Partial HashAggregate (cost=1531393.16..1531629.84 rows=23668 width=69) Group Key: g_1.idg -> Hash Join (cost=3639.85..1462827.46 rows=9142093 width=57) Hash Cond: (l_1.idg = g_1.idg) -> Parallel Seq Scan on lancers l_1 (cost=0.00..971532.67 rows=38626388 width=8) Filter: (idgu IS NULL) -> Hash (cost=3344.00..3344.00 rows=23668 width=53) -> Seq Scan on geants g_1 (cost=0.00..3344.00 rows=23668 width=53) Filter: (berserk AND cyclope AND ((couleur)::text = 'GRIS'::text) AND ((gabarit)::text = 'PETIT'::text) AND ((ere)::text = 'TAUREAU'::text)) -> Append (cost=0.00..946.72 rows=47336 width=310) -> CTE Scan on lancers_nouveau_systeme (cost=0.00..473.36 rows=23668 width=310) -> CTE Scan on lancers_uniquement_ancien_systeme (cost=0.00..473.36 rows=23668 width=310) -- environnement SSD with lancers_nouveau_systeme as (select g.idg, g.idgu, g.devise, sum(l.perf) somme, count(1) compte from geants g join lancers l on (g.idgu = l.idgu) where g.couleur = 'GRIS' and g.gabarit = 'PETIT' and g.ere = 'TAUREAU' and berserk and cyclope group by g.idg), lancers_uniquement_ancien_systeme as (select g.idg, g.idgu, g.devise, sum(l.perf) somme, count(1) compte from geants g join lancers l on (g.idg = l.idg) where g.couleur = 'GRIS' and g.gabarit = 'PETIT' and g.ere = 'TAUREAU' and berserk and cyclope and l.idgu is null group by g.idg) select idg, idgu, devise, sum(somme)/sum(compte) from (select * from lancers_nouveau_systeme union all select * from lancers_uniquement_ancien_systeme) ua group by idg, idgu, devise; Durée : 15013,505 ms (00:15,014) ... Durée : 14316,468 ms (00:14,316) ... Durée : 14693,860 ms (00:14,694) -- environnement HDD archa├»que, RAM insuffisante with lancers_nouveau_systeme as (select g.idg, g.idgu, g.devise, sum(l.perf) somme, count(1) compte from geants g join lancers l on (g.idgu = l.idgu) where g.couleur = 'GRIS' and g.gabarit = 'PETIT' and g.ere = 'TAUREAU' and berserk and cyclope group by g.idg), lancers_uniquement_ancien_systeme as (select g.idg, g.idgu, g.devise, sum(l.perf) somme, count(1) compte from geants g join lancers l on (g.idg = l.idg) where g.couleur = 'GRIS' and g.gabarit = 'PETIT' and g.ere = 'TAUREAU' and berserk and cyclope and l.idgu is null group by g.idg) select idg, idgu, devise, sum(somme)/sum(compte) from (select * from lancers_nouveau_systeme union all select * from lancers_uniquement_ancien_systeme) ua group by idg, idgu, devise; Durée : 5178934,893 ms (01:26:18,935)


      Le planner réalise 2 jointures par hachage (HASH JOIN). Aucun index n'est utilisé et pourtant le temps d'exéution global est bien meilleur dans cet exemple. La durée est en effet divisée par 4 par rapport à celle de la requête initiale dans l'environnement disposant d'un stockage SSD et divisée par 11 dans l'environnement disposant d'un stockage HDD particulièrement lent.
      Comme d'habitude, il n'y pas de vérité absolue. Tout dépend des ressources matérielles à disposition, de la quantité de données, de la version de PostgreSQL et donc du planner etc. De manière générale, la jointure par hachage (hash join) est tout de même souvent particulièrement efficace pour joindre de grands ensembles de données en décisionnel alors que la jointure par boucle imbriquée (nested loop) est souvent la méthode adaptée pour le travail transactionnel.

Mise à jour : 16/02/2018