Statistiques étendues

(sujet préalablement traité avec la version 10 devel)

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 10 beta :

select version(); version ----------------------------------------------------------------------------------------------------- PostgreSQL 10beta1 on x86_64-pc-linux-gnu, compiled by gcc (Debian 6.3.0-18) 6.3.0 20170516, 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 | | 39938 NOIR | MOYEN | f | LICORNE | f | 30062 GRIS | PETIT | t | TAUREAU | t | 29991 NOIR | MOYEN | f | LICORNE | t | 3 NOIR | PETIT | t | TAUREAU | t | 2 BLEU | GRAND | f | LICORNE | f | 2 NOIR | MOYEN | t | TAUREAU | t | 1 BLEU | MOYEN | f | LICORNE | f | 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=1499245.79..1500088.23 rows=249 width=69) Group Key: g.idg -> Gather Merge (cost=1499245.79..1500082.63 rows=498 width=69) Workers Planned: 2 -> Partial GroupAggregate (cost=1498245.76..1499025.13 rows=249 width=69) Group Key: g.idg -> Sort (cost=1498245.76..1498504.72 rows=103583 width=41) Sort Key: g.idg -> Hash Join (cost=3182.11..1486428.58 rows=103583 width=41) Hash Cond: (l.idg = g.idg) -> Parallel Seq Scan on lancers l (cost=0.00..957208.03 rows=41666703 width=8) -> Hash (cost=3179.00..3179.00 rows=249 width=37) -> Seq Scan on geants g (cost=0.00..3179.00 rows=249 width=37) Filter: (berserk AND cyclope AND ((couleur)::text = 'GRIS'::text) AND ((gabarit)::text = 'PETIT'::text) AND ((ere)::text = 'TAUREAU'::text)) 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; Time: 41081,498 ms (00:41,081) .. Time: 41436,024 ms (00:41,436) .. Time: 42196,328 ms (00:42,196)


      L’exécution de la requête a pris un peu plus de 40 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 249 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é. 29991 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.60..338182.87 rows=249 width=69) Group Key: g.idg -> Gather Merge (cost=1024.60..338177.27 rows=498 width=69) Workers Planned: 2 -> Partial GroupAggregate (cost=24.58..337119.76 rows=249 width=69) Group Key: g.idg -> Nested Loop (cost=24.58..336599.36 rows=103583 width=41) -> Parallel Index Scan using geants_pkey on geants g (cost=0.29..3765.46 rows=104 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.29..3190.35 rows=998 width=8) Recheck Cond: (idg = g.idg) -> Bitmap Index Scan on lancers_i1 (cost=0.00..24.04 rows=998 width=0) Index Cond: (idg = g.idg) 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; Time: 148519,826 ms (02:28,520) .. Time: 148533,660 ms (02:28,534) .. Time: 148022,211 ms (02:28,022)


      Catastrophe, la durée augmente et atteint presque 2min30s, elle est donc multipliée par 3,5 ! 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 avons déjà tous les moyens 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=1488020.27..1488027.12 rows=249 width=69) Group Key: g.idg -> Sort (cost=1488020.27..1488021.52 rows=498 width=69) Sort Key: g.idg -> Gather (cost=1487945.67..1487997.96 rows=498 width=69) Workers Planned: 2 -> Partial HashAggregate (cost=1486945.67..1486948.16 rows=249 width=69) Group Key: g.idg -> Hash Join (cost=3182.11..1486427.76 rows=103583 width=41) Hash Cond: (l.idg = g.idg) -> Parallel Seq Scan on lancers l (cost=0.00..957207.67 rows=41666667 width=8) -> Hash (cost=3179.00..3179.00 rows=249 width=37) -> Seq Scan on geants g (cost=0.00..3179.00 rows=249 width=37) Filter: (berserk AND cyclope AND ((couleur)::text = 'GRIS'::text) AND ((gabarit)::text = 'PETIT'::text) AND ((ere)::text = 'TAUREAU'::text)) 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; Time: 20072,949 ms (00:20,073) .. Time: 19122,323 ms (00:19,122) .. Time: 22130,625 ms (00:22,131)


      Cela fonctionne, nous retournons sur de la jointure par HASH JOIN et le temps d’exécution passe à 20 secondes environ. Il serait cependant intéressant de pouvoir fournir au planner l’information dont nous disposons, 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 avec ANALYZE :

create statistics geants_couleur_gabarit_ere_berserk_cyclope(dependencies, ndistinct) on couleur, gabarit, ere, berserk, cyclope from geants; CREATE STATISTICS analyze geants; ANALYZE Time: 3140,037 ms (00:03,140) \x Affichage étendu activé. select * from pg_statistic_ext; stxrelid | 16386 stxname | geants_couleur_gabarit_ere_berserk_cyclope stxnamespace | 2200 stxowner | 10 stxkeys | 9 12 15 17 18 stxkind | {d,f} stxndistinct | {"9, 12": 3, "9, 15": 3, "9, 17": 3, "9, 18": 3, "12, 15": 3, "12, 17": 3, "12, 18": 3, "15, 17": 3, "15, 18": 3, "17, 18": 3, "9, 12, 15": 3, "9, 12, 17": 3, "9, 12, 18": 3, "9, 15, 17": 3, "9, 15, 18": 3, "9, 17, 18": 3, "12, 15, 17": 3, "12, 15, 18": 3, "12, 17, 18": 3, "15, 17, 18": 3, "9, 12, 15, 17": 3, "9, 12, 15, 18": 3, "9, 12, 17, 18": 3, "9, 15, 17, 18": 3, "12, 15, 17, 18": 3, "9, 12, 15, 17, 18": 3} stxdependencies | {"9 => 12": 1.000000, "9 => 15": 1.000000, "9 => 17": 1.000000, "9 => 18": 1.000000, "12 => 9": 1.000000, "12 => 15": 1.000000, "12 => 17": 1.000000, "12 => 18": 1.000000, "15 => 9": 1.000000, "15 => 12": 1.000000, "15 => 17": 1.000000, "15 => 18": 1.000000, "17 => 9": 1.000000, "17 => 12": 1.000000, "17 => 15": 1.000000, "17 => 18": 1.000000, "18 => 9": 1.000000, "18 => 12": 1.000000, "18 => 15": 1.000000, "18 => 17": 1.000000, "9, 12 => 15": 1.000000, "9, 12 => 17": 1.000000, "9, 12 => 18": 1.000000, "9, 15 => 12": 1.000000, "9, 15 => 17": 1.000000, "9, 15 => 18": 1.000000, "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": 1.000000, "12, 15 => 18": 1.000000, "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": 1.000000, "17, 18 => 12": 1.000000, "17, 18 => 15": 1.000000, "9, 12, 15 => 17": 1.000000, "9, 12, 15 => 18": 1.000000, "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} \x Affichage étendu désactivé.


      La syntaxe a été clarifiée depuis la 10 devel, la stabilité a été accrue et les statistiques ne présentent plus d’anomalies dans mon exemple.
      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 "9, 12": 3 qu’il existe 3 combinaisons COULEUR, GABARIT significatives.
      Enfin, la colonne stxdependencies nous informe par exemple via "9 => 12": 1.000000 que connaître la valeur de la colonne COULEUR pour une ligne permet de déduire la valeur de la colonne GABARIT.
      Il y a pour l’instant un ou deux Nota Bene, deux ou trois quiproquo comme dirait le Génie d’Aladdin. D’abord les statistiques étendues n’ont aucun effet dans mon exemple :

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=1024.60..338182.87 rows=249 width=69) Group Key: g.idg -> Gather Merge (cost=1024.60..338177.27 rows=498 width=69) Workers Planned: 2 -> Partial GroupAggregate (cost=24.58..337119.76 rows=249 width=69) Group Key: g.idg -> Nested Loop (cost=24.58..336599.36 rows=103583 width=41) -> Parallel Index Scan using geants_pkey on geants g (cost=0.29..3765.46 rows=104 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.29..3190.35 rows=998 width=8) Recheck Cond: (idg = g.idg) -> Bitmap Index Scan on lancers_i1 (cost=0.00..24.04 rows=998 width=0) Index Cond: (idg = g.idg)


      Toujours une estimation de 249 lignes, il existe pour l’instant des restrictions dans l’utilisation des statistiques étendues par le planner et c’est un aspect à creuser.
      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 ? Si les distributions de valeur étaient réparties de manière très différentes il pourrait à la rigueur le déduire des statistiques par colonne mais ici (en en général) c’est impossible. Vérification avec un exemple simple tiré de la documentation PostgreSQL :

CREATE TABLE t (a INT, b INT); CREATE TABLE INSERT INTO t SELECT i % 100, i % 100 FROM generate_series(1, 10000) s(i); INSERT 0 10000 CREATE STATISTICS stts(dependencies) ON a, b FROM t; CREATE STATISTICS analyze t; ANALYZE select * from pg_statistic_ext; stxrelid | stxname | stxnamespace | stxowner | stxkeys | stxkind | stxndistinct | stxdependencies ----------+---------+--------------+----------+---------+---------+--------------+------------------------------------------ 16399 | stts | 2200 | 10 | 1 2 | {f} | | {"1 => 2": 1.000000, "2 => 1": 1.000000} explain analyze select * from t where a = 1 and b = 1; QUERY PLAN ------------------------------------------------------------------------------------------------- Seq Scan on t (cost=0.00..195.00 rows=100 width=8) (actual time=0.024..2.139 rows=100 loops=1) Filter: ((a = 1) AND (b = 1)) Rows Removed by Filter: 9900 Planning time: 0.208 ms Execution time: 2.325 ms explain analyze select * from t where a = 1 and b = 2; QUERY PLAN ----------------------------------------------------------------------------------------------- Seq Scan on t (cost=0.00..195.00 rows=100 width=8) (actual time=1.931..1.931 rows=0 loops=1) Filter: ((a = 1) AND (b = 2)) Rows Removed by Filter: 10000 Planning time: 0.091 ms Execution time: 1.964 ms


      Pour a=1 et b=1, grâce aux statistiques étendues qui indiquent qu’il existe une dépendance entre a et b, le planner sait que la requête ne va pas retourner 1 ligne mais 100. Attention cependant aux limites que j’ai évoquées précédemment. Pour a = 1 et b = 2 il croit également que la requête va ramener 100 lignes alors qu’elle va évidemment en ramener...0. Cependant ce n’est pas si grave lorsque le but est d’éviter de surestimer la sélectivité, comme dans mon exemple du clan des géants.

Conclusion...provisoire

      Statistiques multi-colonnes, statistiques étendues : les bases sont posées pour une avancée majeure au niveau des capacités du planner de PostgreSQL. PostgreSQL 10 est encore en beta au 17 juin 2017 mais il sera très intéressant de suivre l’évolution de la fonctionnalité jusqu’à sa sortie et, surtout, au cours des futures versions.

Mise à jour : 17/06/2017