Statistiques étendues

(sujet préalablement traité avec les versions 10 devel, 10 beta, 11 devel et 10)

Permettre à PostgreSQL de ne pas boucler jusqu’à la folie

      En complément du "clustering factor", la sélectivité est un critère important pour savoir si le passage par un index peut être bénéfique et, plus généralement, déterminer un plan d’exécution optimal. Des statistiques sont ainsi collectées afin de savoir si tel critère présent dans la clause de filtrage permet d’écarter un grand pourcentage de lignes du jeu de résultats. Ces statistiques sont calculées colonne par colonne.
      Le contexte est toujours celui du clan de géants lançant des rochers. Nous allons supposer en renseignant la colonne GABARIT de la table "geants" que chaque géant a environ 30% de chances d’avoir un PETIT gabarit, 30% de chance d’avoir un gabarit MOYEN tandis que les autres géants ont un GRAND gabarit. Nous allons faire quasi de même pour les colonnes COULEUR, ERE, BERSERK et CYCLOPE. Mais, au lieu d’utiliser une valeur aléatoire différente pour chaque colonne, nous allons réutiliser la même valeur aléatoire. Elle sera donc aléatoire pour une ligne donnée mais pas pour une colonne. Autrement dit, dans quasi tous les cas, si un géant a un PETIT gabarit alors il aime le GRIS, il est de l’ère du TAUREAU, est BERSERK et CYCLOPE. La table "lancers" est générée entièrement aléatoirement, chaque géant comptera environ 1000 lancers. Nous allons déterminer la performances moyenne des "PETITS TAUREAUX GRIS BERSERKS CYCLOPES".
      Démonstration avec PostgreSQL 12 beta :

select version(); version ------------------------------------------------------------------------------------------------------------------------------------------ PostgreSQL 12beta3 (Ubuntu 12~beta3-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( idg integer generated always as identity primary key, 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 serie(i, r1) AS (SELECT generate_series(1,100000,1), random()) insert into geants(genre, taille, masse, actif, devise, pw, heureux, couleur, veteran, clan, gabarit, revenu, pm, berserk, tutelaire, ere, cyclope) select 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 select couleur, gabarit, berserk, ere, cyclope , count(*) from geants group by couleur, gabarit, berserk, ere, cyclope order by 6 desc; couleur | gabarit | berserk | ere | cyclope | count ---------+---------+---------+---------+---------+------- BLEU | GRAND | | DRAGON | | 39857 NOIR | MOYEN | f | LICORNE | f | 30078 GRIS | PETIT | t | TAUREAU | t | 30061 NOIR | MOYEN | f | TAUREAU | t | 1 NOIR | MOYEN | f | LICORNE | t | 1 NOIR | MOYEN | t | TAUREAU | t | 1 NOIR | PETIT | t | TAUREAU | t | 1 create table lancers(dtl timestamp, idg integer, perf integer); CREATE TABLE WITH serie(i) AS (SELECT generate_series(100000000,1,-1)) insert into lancers(dtl, idg, perf) select current_timestamp - (i || ' minutes')::interval, trunc(random() * 100000 + 1), case when random() <= 0.0001 then 50000 + trunc(random() * 50000 + 1) else trunc(random() * 50000 + 1) end from serie; INSERT 0 100000000 analyze geants; ANALYZE analyze lancers; ANALYZE explain select g.idg, g.devise, avg(l.perf) 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 = true and cyclope = true group by g.idg, g.devise; QUERY PLAN ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ Finalize GroupAggregate (cost=1078478.84..1079304.36 rows=247 width=69) Group Key: g.idg -> Gather Merge (cost=1078478.84..1079298.80 rows=494 width=69) Workers Planned: 2 -> Partial GroupAggregate (cost=1077478.82..1078241.76 rows=247 width=69) Group Key: g.idg -> Sort (cost=1077478.82..1077732.31 rows=101396 width=41) Sort Key: g.idg -> Parallel Hash Join (cost=2460.22..1069047.93 rows=101396 width=41) Hash Cond: (l.idg = g.idg) -> Parallel Seq Scan on lancers l (cost=0.00..957208.03 rows=41666703 width=8) -> Parallel Hash (cost=2458.41..2458.41 rows=145 width=37) -> Parallel Seq Scan on geants g (cost=0.00..2458.41 rows=145 width=37) Filter: (berserk AND cyclope AND ((couleur)::text = 'GRIS'::text) AND ((gabarit)::text = 'PETIT'::text) AND ((ere)::text = 'TAUREAU'::text)) JIT: Functions: 19 Options: Inlining true, Optimization true, Expressions true, Deforming true \timing Chronométrage activé. select g.idg, g.devise, avg(l.perf) 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 = true and cyclope = true group by g.idg, g.devise; Durée : 11959,973 ms (00:11,960) Durée : 12076,202 ms (00:12,076) Durée : 12033,901 ms (00:12,034)


      L’exécution de la requête prend ici environ 12 secondes. Un balayage complet des tables GEANTS et LANCERS est effectué et la jointure réalisée est de type HASH JOIN. Nous pouvons remarquer que l’estimation du planner en ce qui concerne le nombre de ligne renvoyées était complètement erronée. Si les données avaient été générées aléatoirement nous aurions bien autour de 0,3 X 0,3 X 0,3 X 0,3 X 0,3 X 100 000 = 243 géants de PETIT gabarit, aimant le GRIS, de l’ère du TAUREAU, BERSERK et CYCLOPE. L’estimation de 247 apparaissant dans le plan serait donc excellente.
      Mais, malheureusement, ce n’est pas le cas. Nous avons une quasi dépendance entre les valeurs de ces 5 colonnes et le nombre de "PETITS TAUREAUX GRIS BERSERKS CYCLOPES" est bien plus élevé. 30061 géants sont en effet concernés.
      Cette estimation erronée n’a pas prêté à conséquence car, en l’absence d’index sur la table lancers, le planner n’avait pas trop le choix. Mais nous allons corser l’affaire. Un index composite est créé sur la table "lancers" pour les colonnes idg, dtl.
      Quel impact sur la requête ?

create index lancers_i1 on lancers(idg, dtl); CREATE INDEX explain select g.idg, g.devise, avg(l.perf) 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 = true and cyclope = true group by g.idg, g.devise; QUERY PLAN ------------------------------------------------------------------------------------------------------------------------------------------------------------------------ Finalize GroupAggregate (cost=1024.50..332172.04 rows=247 width=69) Group Key: g.idg -> Gather Merge (cost=1024.50..332166.49 rows=494 width=69) Workers Planned: 2 -> Partial GroupAggregate (cost=24.48..331109.44 rows=247 width=69) Group Key: g.idg -> Nested Loop (cost=24.48..330599.99 rows=101396 width=41) -> Parallel Index Scan using geants_pkey on geants g (cost=0.29..3765.46 rows=103 width=37) 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.19..3163.30 rows=985 width=8) Recheck Cond: (idg = g.idg) -> Bitmap Index Scan on lancers_i1 (cost=0.00..23.94 rows=985 width=0) Index Cond: (idg = g.idg) JIT: Functions: 13 Options: Inlining false, Optimization false, Expressions true, Deforming true select g.idg, g.devise, avg(l.perf) 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 = true and cyclope = true group by g.idg, g.devise; Durée : 67624,032 ms (01:07,624) Durée : 69484,180 ms (01:09,484) Durée : 64187,188 ms (01:04,187)


      L’exemple met à mal une idée communément répandue : "au pire, ajouter un index pénalise un peu les écritures mais jamais les lectures". Ce n’est PAS toujours vrai. Ici, la durée explose et dépasse la minute !
      Croyant à tort que le nombre de "PETITS TAUREAUX GRIS BERSERKS CYCLOPES" était faible, le planner a choisi les boucles imbriquées pour effectuer la jointure.
      Rassurez-vous. Nous avions déjà les moyens en version 9.6 de revenir au plan initial, par exemple en montant random_page_cost. Démonstration :

set random_page_cost=20; SET explain select g.idg, g.devise, avg(l.perf) 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 = true and cyclope = true group by g.idg, g.devise; QUERY PLAN ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ Finalize GroupAggregate (cost=1078478.38..1079303.90 rows=247 width=69) Group Key: g.idg -> Gather Merge (cost=1078478.38..1079298.34 rows=494 width=69) Workers Planned: 2 -> Partial GroupAggregate (cost=1077478.36..1078241.30 rows=247 width=69) Group Key: g.idg -> Sort (cost=1077478.36..1077731.85 rows=101396 width=41) Sort Key: g.idg -> Parallel Hash Join (cost=2460.22..1069047.46 rows=101396 width=41) Hash Cond: (l.idg = g.idg) -> Parallel Seq Scan on lancers l (cost=0.00..957207.67 rows=41666667 width=8) -> Parallel Hash (cost=2458.41..2458.41 rows=145 width=37) -> Parallel Seq Scan on geants g (cost=0.00..2458.41 rows=145 width=37) Filter: (berserk AND cyclope AND ((couleur)::text = 'GRIS'::text) AND ((gabarit)::text = 'PETIT'::text) AND ((ere)::text = 'TAUREAU'::text)) JIT: Functions: 19 Options: Inlining true, Optimization true, Expressions true, Deforming true select g.idg, g.devise, avg(l.perf) 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 = true and cyclope = true group by g.idg, g.devise; Durée : 11666,618 ms (00:11,667) Durée : 12068,435 ms (00:12,068) Durée : 11261,421 ms (00:11,261)


      Nous retrouvons une jointure par hachage (HASH JOIN) et le temps d’exécution repasse à 12 secondes environ. Le hic est que nous avons obtenu un peu artificiellement ce plan favorable. Il serait intéressant de l’obtenir en fournissant l’information dont nous disposons et que le planner ignore, c’est à dire la quasi dépendance entre les 5 colonnes.
      C’est là qu’interviennent les statistiques étendues introduites avec PostgreSQL 10. Elles sont créées avec CREATE STATISTICS mais, attention, sont effectivement calculées par la commande ANALYZE :

create statistics geants_couleur_gabarit_ere_berserk_cyclope(dependencies, ndistinct, mcv) on couleur, gabarit, ere, berserk, cyclope from geants; CREATE STATISTICS analyze geants; ANALYZE \x Affichage étendu activé. select * from pg_statistic_ext; oid | stxrelid | stxname | stxnamespace | stxowner | stxkeys | stxkind -------+----------+--------------------------------------------+--------------+----------+---------------+--------- 16433 | 16420 | geants_couleur_gabarit_ere_berserk_cyclope | 16384 | 10 | 9 12 15 17 18 | {d,f,m} select * from pg_statistic_ext_data; stxoid | 16433 stxdndistinct | {"9, 12": 3, "9, 15": 3, "9, 17": 4, "9, 18": 4, "12, 15": 3, "12, 17": 4, "12, 18": 4, "15, 17": 4, "15, 18": 4, "17, 18": 3, "9, 12, 15": 3, "9, 12, 17": 4, "9, 12, 18": 4, "9, 15, 17": 4, "9, 15, 18": 4, "9, 17, 18": 4, "12, 15, 17": 4, "12, 15, 18": 4, "12, 17, 18": 4, "15, 17, 18": 4, "9, 12, 15, 17": 4, "9, 12, 15, 18": 4, "9, 12, 17, 18": 4, "9, 15, 17, 18": 4, "12, 15, 17, 18": 4, "9, 12, 15, 17, 18": 4} stxddependencies | {"9 => 12": 1.000000, "9 => 15": 1.000000, "9 => 17": 0.697800, "9 => 18": 0.697800, "12 => 9": 1.000000, "12 => 15": 1.000000, "12 => 17": 0.697800, "12 => 18": 0.697800, "15 => 9": 1.000000, "15 => 12": 1.000000, "15 => 17": 0.697800, "15 => 18": 0.697800, "17 => 9": 0.699767, "17 => 12": 0.699767, "17 => 15": 0.699767, "17 => 18": 1.000000, "18 => 9": 0.699767, "18 => 12": 0.699767, "18 => 15": 0.699767, "18 => 17": 1.000000, "9, 12 => 15": 1.000000, "9, 12 => 17": 0.697800, "9, 12 => 18": 0.697800, "9, 15 => 12": 1.000000, "9, 15 => 17": 0.697800, "9, 15 => 18": 0.697800, "9, 17 => 12": 1.000000, "9, 17 => 15": 1.000000, "9, 17 => 18": 1.000000, "9, 18 => 12": 1.000000, "9, 18 => 15": 1.000000, "9, 18 => 17": 1.000000, "12, 15 => 9": 1.000000, "12, 15 => 17": 0.697800, "12, 15 => 18": 0.697800, "12, 17 => 9": 1.000000, "12, 17 => 15": 1.000000, "12, 17 => 18": 1.000000, "12, 18 => 9": 1.000000, "12, 18 => 15": 1.000000, "12, 18 => 17": 1.000000, "15, 17 => 9": 1.000000, "15, 17 => 12": 1.000000, "15, 17 => 18": 1.000000, "15, 18 => 9": 1.000000, "15, 18 => 12": 1.000000, "15, 18 => 17": 1.000000, "17, 18 => 9": 0.699767, "17, 18 => 12": 0.699767, "17, 18 => 15": 0.699767, "9, 12, 15 => 17": 0.697800, "9, 12, 15 => 18": 0.697800, "9, 12, 17 => 15": 1.000000, "9, 12, 17 => 18": 1.000000, "9, 12, 18 => 15": 1.000000, "9, 12, 18 => 17": 1.000000, "9, 15, 17 => 12": 1.000000, "9, 15, 17 => 18": 1.000000, "9, 15, 18 => 12": 1.000000, "9, 15, 18 => 17": 1.000000, "9, 17, 18 => 12": 1.000000, "9, 17, 18 => 15": 1.000000, "12, 15, 17 => 9": 1.000000, "12, 15, 17 => 18": 1.000000, "12, 15, 18 => 9": 1.000000, "12, 15, 18 => 17": 1.000000, "12, 17, 18 => 9": 1.000000, "12, 17, 18 => 15": 1.000000, "15, 17, 18 => 9": 1.000000, "15, 17, 18 => 12": 1.000000, "9, 12, 15, 17 => 18": 1.000000, "9, 12, 15, 18 => 17": 1.000000, "9, 12, 17, 18 => 15": 1.000000, "9, 15, 17, 18 => 12": 1.000000, "12, 15, 17, 18 => 9": 1.000000} stxdmcv | \xc251a6e1010000000300000005001304000013040000100000001304000010000000030000001800000018000000ffffffff00000000030000001b00000030000000ffffffff000000000200000002000000000000000100000001000000030000002000000030000000ffffffff00000000020000000200000000000000010000000100000004000000424c45550400000047524953040000004e4f4952050000004752414e44050000004d4f59454e050000005045544954000106000000445241474f4e070000004c49434f524e4507000000544155524541550001000001000135ef38454772d93f55c44bab9159843f0000000000000000000000000000002394d1dbb256d33f506cf0c487a4643f020001000000010000000000000000bc96900f7a36d33fd12a117939fa633f01000200010002000100 \x Affichage étendu désactivé.


      La colonne stxkeys nous informe que la statistique geants_couleur_gabarit_ere_berserk_cyclope concerne les colonnes 9 (COULEUR), 12 (GABARIT), 15 (BERSERK), 17 (ERE), 18 (CYCLOPE).
      La colonne stxndistinct nous informe par exemple via "12, 15": 3 qu’il existe 3 combinaisons GABARIT, BERSERK significatives.
      Enfin, la colonne stxdependencies nous informe par exemple via "9 => 12": 1.000000 que connaître la valeur de la colonne GABARIT pour une ligne permet de déduire la valeur de la colonne BERSERK.
      La théorie, c’est bien. Mais est-ce que ça marche ? Et bien OUI. Démonstration en reprenant l’exemple précédent :

set random_page_cost=4; SET explain select g.idg, g.devise, avg(l.perf) 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 = true and cyclope = true group by g.idg, g.devise; QUERY PLAN ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ Finalize GroupAggregate (cost=1134416.55..1142097.16 rows=30020 width=69) Group Key: g.idg -> Gather Merge (cost=1134416.55..1141421.71 rows=60040 width=69) Workers Planned: 2 -> Sort (cost=1133416.53..1133491.58 rows=30020 width=69) Sort Key: g.idg -> Partial HashAggregate (cost=1130883.79..1131183.99 rows=30020 width=69) Group Key: g.idg -> Parallel Hash Join (cost=2679.15..1069266.39 rows=12323481 width=41) Hash Cond: (l.idg = g.idg) -> Parallel Seq Scan on lancers l (cost=0.00..957207.67 rows=41666667 width=8) -> Parallel Hash (cost=2458.41..2458.41 rows=17659 width=37) -> Parallel Seq Scan on geants g (cost=0.00..2458.41 rows=17659 width=37) Filter: (berserk AND cyclope AND ((couleur)::text = 'GRIS'::text) AND ((gabarit)::text = 'PETIT'::text) AND ((ere)::text = 'TAUREAU'::text)) JIT: Functions: 18 Options: Inlining true, Optimization true, Expressions true, Deforming true select g.idg, g.devise, avg(l.perf) 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 = true and cyclope = true group by g.idg, g.devise; Durée : 8670,423 ms (00:08,670) Durée : 8582,431 ms (00:08,582) Durée : 8453,596 ms (00:08,454) explain select g.idg, g.devise, avg(l.perf) from geants g join lancers l on (g.idg = l.idg) where g.couleur = 'GRIS' and g.gabarit = 'PETIT' and g.ere = 'LICORNE' and berserk = true and cyclope = true group by g.idg, g.devise; QUERY PLAN ------------------------------------------------------------------------------------------------------------------------------------------------------------------------ Finalize GroupAggregate (cost=1024.52..8625.04 rows=3 width=69) Group Key: g.idg -> Gather Merge (cost=1024.52..8624.97 rows=6 width=69) Workers Planned: 2 -> Partial GroupAggregate (cost=24.49..7624.25 rows=3 width=69) Group Key: g.idg -> Nested Loop (cost=24.49..7618.06 rows=1232 width=41) -> Parallel Index Scan using geants_pkey on geants g (cost=0.29..3765.46 rows=1 width=37) Filter: (berserk AND cyclope AND ((couleur)::text = 'GRIS'::text) AND ((gabarit)::text = 'PETIT'::text) AND ((ere)::text = 'LICORNE'::text)) -> Bitmap Heap Scan on lancers l (cost=24.20..3842.76 rows=985 width=8) Recheck Cond: (idg = g.idg) -> Bitmap Index Scan on lancers_i1 (cost=0.00..23.95 rows=985 width=0) Index Cond: (idg = g.idg)


      L’estimation du nombre de lignes passe de 247 lignes à 30020 lignes, une exellente approximation puisque le nombre réel est 30061. Nous retrouvons le plan performant que nous avions obtenu en jouant sur random_page_cost. Le temps d'exécution est même ici en pratique un peu meilleur, autour des 9 secondes, avec une modification de l'utilisation de JIT.
      Il existe un autre problème potentiel. Comment le planner peut-il savoir que GABARIT=PETIT donne ERE=TAUREAU et pas ERE=LICORNE sur la base des informations de statistiques étendues ? Il en était incapable jusqu'à la version 11 incluse. Il aurait donc estimé à 30020 le nombre de "PETITES LICORNES GRISES BERSERKS CYCLOPES" et n'aurait potentiemment pas utilisé les boucles imbriquées dans certains cas favorables.
      PostgreSQL 12 apporte une avancée majeure à ce niveau. Nous avons en effet demandé à ANALYZE de relever les valeurs les plus courantes ("most common values") avec la syntaxe ", mcv" de la commande CREATE STATISTICS. Il estime ainsi à 3 le nombre de "PETITES LICORNES GRISES BERSERKS CYCLOPES" comme le montre la dernière instruction. Il y en a en fait 0 mais c'est une excellente estimation.

Conclusion

      Statistiques multi-colonnes, statistiques étendues : la fonctionnalité est déjà pleinement utilisable dans les versions 10 et 11.
      PostgreSQL 12 va plus loin. La limitation que j'avais notée est levée. Il s'agit d'un travail de fond tout à fait remarquable de la part des développeurs qui ne sont pas soumis à une pression commerciale ou marketing. Leur but n'est ainsi pas d'afficher à chaque version majeure le plus grand nombre de nouveautés possibles, au détriment de l'amélioration des fonctionnalités existantes. La version 12 s'annonce comme une grande réussite dans cette optique.

Mise à jour : 08/09/2019