Parmi toutes la pléthore de nouveautés de PostgreSQL 10, une un peu planquée est liée à la prise en compte de la corrélation des données par l’optimiseur.
(Refonte d’un billet d’août dont je n’étais pas content.)
En général, si les statistiques sont bien à jour, PostgreSQL estime correctement la volumétrie ramenée par un critère de filtrage portant sur un index, et s’en sert pour choisir le bon plan d’exécution. Par exemple : si un critère porte sur une colonne, il utilisera un index sur cette colonne pour chercher une poignée de lignes, et se reportera à la table ensuite. Mais si le résultat attendu implique une très grande partie de la table, PostgreSQL oubliera l’index et lira la table entièrement quitte à jeter les lignes ne vérifiant pas le critère.
La limite entre les deux comportements est fonction d’une multitude de critères comme les volumétries impliquées, le coût relatif d’un accès direct à un bloc (paramètre randompagecost) par rapport à un bloc au sein d’un parcours complet (seqpagecost), mais encore le parallélisme, l’estimation de l’utilisation du cache de l’OS, etc.
Ça se corse quand on veut mélanger deux critères de filtrage différents. S’ils sont totalement indépendants tout va bien : PostgreSQL suppose que deux critères ramenant chacun 10% de la table en ramèneront une fois combinés 10 % * 10 % = 1 %.
Cependant, dans le monde réel, les corrélations entre données plus ou moins directes abondent : nombre de données de gestion dépendent de l’heure (pas d’activité la nuit) ; des clients ne commandent pas des produits en ligne au hasard mais selon leur âge, leur situation financière, leur localisation ; ou les colonnes représentent une hiérarchie plus ou moins explicite (géographie…). En fait, les distributions uniformes des exemples des documentations sont plus l’exception que la règle.
J’ai donc tenté d’inventer un exemple grossièrement réaliste… et il n’est pas si évident d’en trouver un où le nouveau CREATE STATISTICS mène à un changement réel de plan d’exécution.
Exemple
Prenons une table de personnes de tous âges mais où les seniors seront massivement représentés. On crée des tranches d’âges et des statuts (« Retraités », « Jeunes », « Actifs »), tout cela étant évidemment fortement redondant. Rajoutons encore un flag « propriétaire » digne d’une gérontocratie où les retraités possèdent presque tout :
-- paramétrage de l'optimiseur : sans parallélisme pour simplifier SET max_parallel_workers_per_gather TO 0 ; -- disques durs classiques, donc coûteux pour les accès aléatoires SET seq_page_cost TO 4 ; SET random_page_cost TO 1 ; -- paramétrage mémoire figé SET work_mem TO '16MB'; SET effective_cache_size to '512MB'; -- shared_buffers+cache de l'OS
CREATE TABLE personnes (
id serial,
age INT NOT NULL,
tranche_age TEXT NOT NULL,
statut TEXT NOT NULL,
proprietaire BOOLEAN NOT NULL
);
INSERT INTO personnes (age, tranche_age, statut, proprietaire)
SELECT * FROM (
SELECT mod(i,18) as age, '0-17','Jeune', false
from generate_series(1,1000000) i
UNION ALL
SELECT 18+mod(i,42) , '18-59','Actif', mod(i,10)=0
from generate_series(1,1000000) i
UNION ALL
SELECT 60+mod(i,40), '60+','Retraité', mod(i,10)!=0
from generate_series(1,7000000) i
) z
ORDER BY random() ; -- on mélange bien les lignes
Et plein d’index pour les critères de recherche :
CREATE INDEX ix_statut ON personnes (statut); CREATE INDEX ix_tr_age ON personnes (tranche_age); CREATE INDEX ix_st_tr_age ON personnes (statut,tranche_age); CREATE INDEX ix_st_tr_age_prop ON personnes (statut,tranche_age, proprietaire); VACUUM ANALYZE personnes ;
On obtient donc une table d’environ 448 Mo (et le double en index…) comprenant 9 millions de personnes, où la tranche d’âge « Retraité » est surreprésentée (78 %) constituée de 60 ans et plus, presque tous propriétaires, et vice-versa :
SELECT statut, tranche_age, min(age), max(age), proprietaire,
COUNT(*), ROUND(100 * (COUNT(*) / SUM(COUNT(*)) OVER () ),1) AS "%"
FROM personnes
GROUP BY statut, tranche_age, proprietaire
ORDER BY COALESCE (statut,'aa') DESC, MIN(age);
statut │ tranche_age │ min │ max │ proprietaire │ count │ %
──────────┼─────────────┼─────┼─────┼──────────────┼─────────┼──────
Retraité │ 60+ │ 60 │ 90 │ f │ 700000 │ 7.8
Retraité │ 60+ │ 61 │ 99 │ t │ 6300000 │ 70.0
Jeune │ 0-17 │ 0 │ 17 │ f │ 1000000 │ 11.1
Actif │ 18-59 │ 18 │ 59 │ f │ 900000 │ 10.0
Actif │ 18-59 │ 18 │ 58 │ t │ 100000 │ 1.1
On peut aller voir les statistiques de l’optimiseur (SELECT * FROM pg_stats WHERE tablename = 'personnes'; ) mais on y constatera juste que les données dans les colonnes ne sont pas corrélées à leur emplacement physique, et que la proportion de retraités/plus de 60 ans s’y retrouve (les chiffres exacts dépendent de l’échantillonnage) :
\x auto
SELECT * FROM pg_stats
WHERE tablename = 'personnes';
...
tablename | personnes
attname | tranche_age
...
n_distinct | 3
most_common_vals | {60+,0-17,18-59}
most_common_freqs | {0.7751,0.112733,0.112167}
...
correlation | 0.630976
...
tablename | personnes
attname | statut
...
null_frac | 0
...
n_distinct | 4
most_common_vals | {Retraité,Actif,Jeune}
most_common_freqs | {0.7751,0.112733,0.112167}
...
correlation | 0.631054
tablename │ personnes
attname │ proprietaire
n_distinct │ 2
most_common_vals │ {t,f}
most_common_freqs │ {0.709433,0.290567}
...
correlation │ 0.594379
On peut vérifier qu’une requête sur statut = 'Retraité' ou tranche_age = '60+' mène à un parcours complet (Seq Scan). Dans les deux cas le nombre de lignes estimées et le nombre de lignes effectivement ramenées (les deux valeurs de rows) sont à peu près identiques (7 millions). Malgré l’index sur le statut, PostgreSQL préfère donc lire les 9 millions de ligne et en jeter 2 millions :
EXPLAIN (ANALYZE)
SELECT count(id), min(age), max(age)
FROM personnes
WHERE statut = 'Retraité' ;
Aggregate (cost=394265.26..394265.27 rows=1 width=16)
(actual time=2086.261..2086.261 rows=1 loops=1)
-> Seq Scan on personnes (cost=0.00..341799.84 rows=6995390 width=8)
(actual time=0.030..1270.082 rows=7000000 loops=1)
Filter: (statut = 'Retraité'::text)
Rows Removed by Filter: 2000000
Planning time: 3.341 ms
Execution time: 2086.337 ms
On aura le même comportement pour les « 60+ » ou les propriétaires. Le temps exact dépendra notamment des disques et des données dans les divers caches
Le problème
Les besoins fonctionnels sont souvent plus fins (et la réalité moins tranchée que ma requête d’insertion). On voudra par exemple préciser que l’on veut les retraités, de plus de 60 ans, et propriétaires. Mais là l’estimation de l’optimiseur est erronée :
EXPLAIN (ANALYZE)
SELECT count(id), min(age),max(age)
FROM personnes
WHERE tranche_age = '60+' AND statut = 'Retraité' and proprietaire ;
Aggregate (cost=380991.88..380991.89 rows=1 width=16)
(actual time=2635.944..2635.944 rows=1 loops=1)
-> Bitmap Heap Scan on personnes
(cost=64403.09..351895.62 rows=3879502 width=8)
(actual time=834.780..1984.364 rows=6300000 loops=1)
Recheck Cond: ( (statut = 'Retraité'::text) AND (tranche_age = '60+'::text) )
Filter: proprietaire
Heap Blocks: exact=57325
-> Bitmap Index Scan on ix_st_tr_age_prop
(cost=0.00..63433.21 rows=3879502 width=0)
(actual time=823.539..823.539 rows=6300000 loops=1)
Index Cond: ((statut = 'Retraité'::text) AND (tranche_age = '60+'::text) AND (proprietaire = true))
Planning time: 0.290 ms
Execution time: 2636.024 ms
L’optimiseur pense qu’il y a 3 879 502 lignes (9 millions * 0,7751 * 0,7751 * 0,7094 d’après les statistiques) alors qu’il en trouve en fait 6 300 000 : presque un facteur deux. D’où le choix d’un plan qui consiste à parcourir une bonne partie de l’index pour repérer les blocs intéressants (Bitmap Index Scan), puis à aller les lire dans la table même (Bitmap Heap Scan, 57 325 blocs soit… toute la table, lue dans son ordre physique et non dans celui, logique, trouvé dans l’index), et à chercher les lignes intéressantes dedans (clause Recheck qui reprend la clause de filtrage de l’index).
Est-ce une catastrophe ? Pas forcément, si le temps d’exécution est acceptable. Mais pourquoi passer par l’index si l’on lit tous les blocs de la table au final ? (Noter qu’avec des données moins mélangées ce serait peut-être différent).
Objet statistique
L’amélioration de PostgreSQL 10 consiste à créer un objet « statistique », dont le seul but sera de calculer la corrélation entre deux (ou plus) colonnes. L’ordre de création est simple, et je note que la clause FROM suggère que dans le futur on pourrait avoir beaucoup plus qu’une corrélation entre simples colonnes d’une table. Les perspectives sont alléchantes mais pour le moment il ne peut y avoir qu’une table.
Pour le moment on retiendra surtout que cet objet statistique doit être créé explicitement et qu’il est maintenu par les clauses ANALYZE habituelles (en arrière-plan grâce à l’autovacuum, ou explicite aussi pour être certain que les statistiques soient pris en compte dans la suite) :
CREATE STATISTICS pers_tr_age_statut_proprio ON tranche_age, statut, proprietaire FROM personnes ; ANALYZE personnes ;
Une clause dependencies oriente PostgreSQL vers la recherche de corrélations fonctionnelles entre colonnes. L’alternative (ndistinct) vise plutôt à résoudre les erreurs dans le nombre de valeurs distinctes dans les regroupements (voir la doc pour les détails). On peut utiliser les deux types dans le même objet par fainéantise, comme ici.
L’objet apparaît sous la table dans un \d+ :
Objets statistiques :
"public"."pers_tr_age_statut_proprio" (ndistinct, dependencies)
ON tranche_age, statut, proprietaire
FROM personnes
Qu’y a-t-il en fait dans cet objet statistique ? On peut voir son contenu dans la nouvelle vue pgstatisticext. Les keys mentionnées ci-dessous sont dans l’ordre de la table : tranche_age, statut et proprietaire. Leur corrélation est calculée dans les deux sens :
SELECT * FROM pg_statistic_ext
WHERE stxname = 'pers_tr_age_statut_proprio' ;
-[ RECORD 1 ]---+-----------------------------------------
stxrelid │ 10033457
stxname │ pers_tr_age_statut_proprio
stxnamespace │ 2200
stxowner │ 10
stxkeys │ 3 4 5
stxkind │ {d,f}
stxndistinct │ {"3, 4": 3, "3, 5": 5, "4, 5": 5, "3, 4, 5": 5}
stxdependencies │ {"3 => 4": 1.000000, "3 => 5": 0.113533,
"4 => 3": 1.000000, "4 => 5": 0.113533,
"3, 4 => 5": 0.113533, "3, 5 => 4": 1.000000,
"4, 5 => 3": 1.000000}
On note qu’il s’agit d’une moyenne sur la colonne. On est encore loin de détecter les corrélations réduites à certaines valeurs des données. Notamment, l’information sur proprietaire (5) n’indique pas grand-chose sur les autres colonnes. Par contre, les combinaisons de colonnes sont gérées.
Résultat
Quel est l’effet sur notre requête ?
EXPLAIN (ANALYZE,buffers)
SELECT count(id), min(age),max(age)
FROM personnes
WHERE tranche_age = '60+' AND statut = 'Retraité' and proprietaire;
Aggregate (cost=403078.89..403078.90 rows=1 width=16)
(actual time=2196.764..2196.764 rows=1 loops=1)
Buffers: shared hit=16211 read=41114
-> Seq Scan on personnes
(cost=0.00..364300.02 rows=5170516 width=8)
(actual time=6.715..1438.755 rows=6300000 loops=1)
Filter: (proprietaire AND (tranche_age = '60+'::text) AND (statut = 'Retraité'::text))
Rows Removed by Filter: 2700000
Buffers: shared hit=16211 read=41114
Planning time: 2.258 ms
Execution time: 2197.469 ms
Grâce au nouvel objet statistique, la volumétrie attendue avant l’agrégation a augmenté (5,1 millions au lieu de 3,2 précédemment et 6,3 réels), d’où le changement de stratégie.
Le plan est à présent un parcours complet (Seq Scan) : PostgreSQL calcule que finalement il vaut mieux parcourir directement toute la table pour en lire et filtrer les valeurs directement que d’aller voir dans un index pas si discriminant que ça finalement. Tout l‘overhead de lecture de l’index, de son chargement en cache éventuel, de construction du bitmap index… passe à la trappe.
On pourrait s’étonner que le coût ait monté (403 078 contre 380 991 précédemment) : en fait c’est l’ancien chiffre qui était faux puisque la volumétrie estimée était fausse. En interdisant les parcours complets (SET enable_seqscan TO off ;) pour revenir à l’ancien plan, PostgreSQL recalcule un coût de 431 471.
Quant au temps d’exécution : je passe sur mon portable avec SSD de 2,6 à 2,0 s. Je reproduis des écarts comparables sur une instance avec un disque dur classique, ou sur un Raspberry Pi B. Cependant, vues les volumétries, la présence ou non des données dans le cache a une grande importance.
Sensibilité aux paramètres
Évidemment, PostgreSQL ne change pas de plan à chaque petite évolution du coût : j’ai choisi un endroit proche du « point de bascule » entre deux plans pour mon exemple, et celui-ci est extrêmement sensible aux valeurs de work_mem, seqpagecost, randompagecost, effectivecachesize, voire aux statistiques qui varient après chaque ANALYZE, etc.
À titre d’exemple, un changement d’effectivecachesize à 3 Go fait basculer le plan vers un Index Scan. PostgreSQL juge que l’index et la table étant probablement dans le cache, il n’est pas trop coûteux de parcourir l’index et d’aller chercher chacun des blocs concernés dans la table pour y compter les id et voir les age. (Ne pas confondre avec l’Index Only Scan qui consisterait à se satisfaire uniquement de l’index quand toutes les colonnes intéressantes y figurent déjà.)
Moralité
On a obtenu ici un changement de plan en construisant un exemple encore un peu artificiel. Dans la réalité on étudie un plan d’une requête un peu lente et l’on trouve une volumétrie estimée aberrante. Plus le nombre de critères corrélés augmente, plus l’estimation est éloignée de la réalité. L’ajout d’un objet statistique peut corriger la chose, mais il a un coût en mise à jour : comme les index, on n’en ajoutera que si leur utilisation apporte un réel bénéfice. Mais il vaut mieux les utiliser que torturer une requête jusqu’à l’illisibilité ou dénormaliser le modèle.
Noter qu’un objet statistique reste utile même si l’on crée un index sur les deux champs concernés : celui-ci ne connaît ni ne contient la corrélation entre les champs qu’il indexe !
Les statistiques ne sont utiles que pour les égalités (ou une clause IN par exemple), pas si des inégalités sont impliquées. Selon la documentation :
« Les dépendances fonctionnelles sont pour le moment uniquement appliquées pour les conditions sur une simple égalité entre une colonne et une valeur constante. Elles ne sont pas utilisées pour améliorer l’estimation sur les conditions d’égalité entre deux colonnes ou la comparaison d’une colonne avec une expression, ni pour les clauses d’intervalle, LIKE ou tout autre type de condition. »
Évidemment, cela suppose déjà que les statistiques sont à jour : vérifiez que l’autovacuum passe assez régulièrement sur la table ; et que l’échantillonnage est suffisant pour les grosses tables.
Bibliographie
Quelques liens vers la doc officielle pour finir :
- CREATE statistics
- Statistiques utilisées par le planificateur
- Exemples de statistiques multivariées et la différence entre les deux types de statistiques étendues
- La vue pg_statistic_ext