Limitations du planner


      Je suis souvent questionné sur les capacités d'optimisation des requêtes de PostgreSQL. Sont-elles sans limite ? Est-il toujours possible d'obtenir le meilleur plan ? La réponse est "Non, elles ne sont pas sans limite" mais "Oui, il y a toujours moyen d'obtenir le bon plan s'il existe ou, au moins, un plan acceptable". Le passage d'une optimisation basée sur des règles à une optimisation basée sur des statistiques calculées sur les données fut une évolution majeure des SGBD dans les dernières années du 20ème siècle. Les capacités d'exécutions ont aussi beaucoup évolué.
      Statistiques étendues, indexation complète (b-tree, gin, gist, hash, bloom, brin, partielle, couvrante...), partitionnement, nouvelles possibilités d'exécution comme les tris incrémentaux...les capacités natives du moteur PostgreSQL sont à présent très vastes.
      Mais certains problèmes simples peuvent encore le faire trébucher. Dans cette page, chaque membre du clan de géants (table geants) a une arme favorite. Les armes (table armes) sont réparties en diverses catégories. Chaque géant lance par ailleurs des cailloux (table lancers). Les armes sont très diverses, il existe un million d'armes différentes et tout autant de catégories. Mais les géants utilisent en réalité à 80% la hache, une arme de catégorie "tranchante". Nous allons chercher à déterminer la moyenne des performances au lancer des géants utilisant une arme prise au hasard, puis une arme tranchante.

select version(); version --------------------------------------------------------------------------------------------------------------------------- PostgreSQL 13.5 (Debian 13.5-0+deb11u1) on x86_64-pc-linux-gnu, compiled by gcc (Debian 10.2.1-6) 10.2.1 20210110, 64-bit create table geants( idg integer generated by default as identity primary key, devise varchar(128), ida integer, berserk boolean ); CREATE TABLE with recursive serie(i, r1) as (select 1, random() UNION ALL select i + 1, random() from serie where i < 1000000) insert into geants(devise, ida, berserk) select upper(md5(random()::text)), case when r1 <= 0.1 then 1 when r1 > 0.1 and r1 <= 0.9 then 2 else trunc(random()*1000000 + 1) end, case when r1 <= 0.1 then true else false end from serie; INSERT 0 1000000 create index geants_fk1 on geants(ida); CREATE INDEX create table armes(ida integer primary key, libelle text, categorie text); CREATE TABLE insert into armes values(1, 'massue', 'contondante'); INSERT 0 1 insert into armes values(2, 'hache', 'tranchante'); INSERT 0 1 with recursive serie(i) as (select 3 UNION ALL select i + 1 from serie where i < 1000000) insert into armes select i,lower(md5(random()::text)), lower(md5(random()::text)) from serie; INSERT 0 999998 alter table geants add foreign key(ida) references armes(ida); ALTER TABLE create index armes_i1 on armes(categorie); CREATE INDEX 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 < 100000000) select clock_timestamp() - ((i)::int || ' minutes')::interval, trunc(random() * 1000000 + 1), trunc(random() * 100000 + 1) from serie; INSERT 0 100000000 create index lancers_fk1 on lancers(idg); CREATE INDEX alter table lancers add foreign key(idg) references geants(idg); ALTER TABLE analyse geants; ANALYZE analyze armes; ANALYZE analyze lancers; ANALYZE \d+ Liste des relations Schéma | Nom | Type | Propriétaire | Persistence | Taille | Description ----------+----------------+----------+--------------+-------------+------------+------------- postgres | armes | table | postgres | permanent | 97 MB | postgres | geants | table | postgres | permanent | 73 MB | postgres | geants_idg_seq | séquence | postgres | permanent | 8192 bytes | postgres | lancers | table | postgres | permanent | 5606 MB | commit; COMMIT explain with categorie_aleatoire(valeur) as (select lower(md5(random()::text))) select avg(perf) from geants join armes using(ida) join lancers using (idg) where categorie = (select valeur from categorie_aleatoire); QUERY PLAN ----------------------------------------------------------------------------------------------- Aggregate (cost=240.73..240.74 rows=1 width=32) CTE categorie_aleatoire -> Result (cost=0.00..0.02 rows=1 width=32) InitPlan 2 (returns $1) -> CTE Scan on categorie_aleatoire (cost=0.00..0.02 rows=1 width=32) -> Nested Loop (cost=1.42..240.44 rows=100 width=4) -> Nested Loop (cost=0.85..87.19 rows=1 width=4) -> Index Scan using armes_i1 on armes (cost=0.42..8.44 rows=1 width=4) Index Cond: (categorie = $1) -> Index Scan using geants_fk1 on geants (cost=0.42..78.44 rows=31 width=8) Index Cond: (ida = armes.ida) -> Index Scan using lancers_idg_idx on lancers (cost=0.57..152.23 rows=101 width=8) Index Cond: (idg = geants.idg) with categorie_aleatoire(valeur) as (select lower(md5(random()::text))) select avg(perf) from geants join armes using(ida) join lancers using (idg) where categorie = (select valeur from categorie_aleatoire); avg ----- (1 ligne) Temps : 54,183 ms explain with categorie_aleatoire(valeur) as (select lower(md5(random()::text))) select avg(perf) from geants join armes using(ida) join lancers using (idg) where categorie = 'tranchante'; QUERY PLAN ----------------------------------------------------------------------------------------------- Aggregate (cost=240.69..240.70 rows=1 width=32) -> Nested Loop (cost=1.42..240.44 rows=100 width=4) -> Nested Loop (cost=0.85..87.19 rows=1 width=4) -> Index Scan using armes_i1 on armes (cost=0.42..8.44 rows=1 width=4) Index Cond: (categorie = 'tranchante'::text) -> Index Scan using geants_fk1 on geants (cost=0.42..78.44 rows=31 width=8) Index Cond: (ida = armes.ida) -> Index Scan using lancers_idg_idx on lancers (cost=0.57..152.23 rows=101 width=8) Index Cond: (idg = geants.idg) with categorie_aleatoire(valeur) as (select lower(md5(random()::text))) select avg(perf) from geants join armes using(ida) join lancers using (idg) where categorie = 'tranchante'; ERREUR: annulation de la requête à la demande de l'utilisateur Durée : 23519147,262 ms (06:31:59,147)

      En prenant une catégorie au hasard, qui n'existe d'ailleurs pas, tout comme en considérant la catégorie "tranchante", PostgreSQL choisit les boucles imbriquées (nested loops) pour joindre les tables. C'est très bon avec la catégorie prise au hasard mais catastrophique avec la catégorie tranchante, elle est surreprésentée dans la table geants et j'ai arrêté l'exécution après 6h30. Statistiques étendues (multi-colonnes) ? Non, inutile en 2022. Elles s'appliquent sur les colonnes d'une même table et créer de telles statistiques sur (ida, categorie) au niveau de la table armes n'apporterait rien. Il y a en effet bien 1 ligne sur 1 million dans la table armes pour la catégorie tranchante.
      Quelle solution ? Il serait possible de dupliquer la colonne categorie dans la table geants, ce qui donnerait immédiatement la bonne cardinalité au planner sur les geants concernés, sans même nécessiter de statistiques étendues. Mais gérer une telle redondance pose bien sûr d'autres problèmes. Il est plus logique, exceptionnellement, d'aider le planner avec un hint ou, plus simplement, de désactiver les nested loops pour cette requête.

set enable_nestloop = off; SET explain with categorie_aleatoire(valeur) as (select lower(md5(random()::text))) select avg(perf) from geants join armes using(ida) join lancers using (idg) where categorie = 'tranchante'; QUERY PLAN ---------------------------------------------------------------------------------------------------------------- Finalize Aggregate (cost=1305974.36..1305974.37 rows=1 width=32) -> Gather (cost=1305974.14..1305974.35 rows=2 width=32) Workers Planned: 2 -> Partial Aggregate (cost=1304974.14..1304974.15 rows=1 width=32) -> Parallel Hash Join (cost=14614.89..1304974.04 rows=42 width=4) Hash Cond: (lancers.idg = geants.idg) -> Parallel Seq Scan on lancers (cost=0.00..1134082.53 rows=41673653 width=8) -> Parallel Hash (cost=14614.87..14614.87 rows=1 width=4) -> Hash Join (cost=8.46..14614.87 rows=1 width=4) Hash Cond: (geants.ida = armes.ida) -> Parallel Seq Scan on geants (cost=0.00..13512.67 rows=416667 width=8) -> Hash (cost=8.44..8.44 rows=1 width=4) -> Index Scan using armes_i1 on armes (cost=0.42..8.44 rows=1 width=4) Index Cond: (categorie = 'tranchante'::text) with categorie_aleatoire(valeur) as (select lower(md5(random()::text))) select avg(perf) from geants join armes using(ida) join lancers using (idg) where categorie = 'tranchante'; avg -------------------- 50001.386715393886 (1 ligne) Durée : 65501,967 ms (01:05,502) with categorie_aleatoire(valeur) as (select lower(md5(random()::text))) select avg(perf) from geants join armes using(ida) join lancers using (idg) where categorie = (select valeur from categorie_aleatoire); avg ----- (1 ligne) Temps : 191,195 ms

      Un peu plus d'une minute avec deux process parallèles venant à la rescousse, c'est correct sur mon serveur très lent. La recherche avec une catégorie quelconque a par ailleurs toujours des performances acceptables (0s2). Mission accomplie.

Futures évolutions

      Quelles sont les solutions qui permettraient au planner de PostgreSQL de s'en sortir seul dans ce cas ? S'il était possible de créer des statistiques étendues à des groupes de colonnes de différentes tables, de telles statistiques sur (geants(ida), armes(categorie)) permettraient à PostgreSQL de trouver aisément la bonne solution.
      Il serait aussi possible de s'apercevoir à l'exécution que le nombres d'enregistements après la jointure geants/armes est bien supérieure à celle initialement prévue. Il serait alors théoriquement possible de replanifier la suite de la requête en optant à la volée pour un hash join avec lancers. Optionnellement, en tâche de fond, pourquoi ne pas également prendre l'iniative de faire calculer les statistiques étendues évoquées par autovacuum pour permettre à de futures requétes d'obtenir le plan optimal dàs la phase initiale de planification ? Les statistiques étendues sur plusieurs tables ne sont pas disponible et leur calcul automatique n'est pas à l'ordre du jour à ma connaissance. Mais la capacité à s'adapter en cours de plan ou à l'issue du plan pour les futures requêtes est mentionné et même développé en partie sous la forme d'une extension. À suivre !
      Quid des autres SGBD ? Oracle Database n'a pas encore non plus de statistiques multi-colonnes sur plusieurs tables mais a déjà du "cardinality feedback", des "adaptive plans" etc. Ces fonctionnalités ont une efficacité parfois assez mitigée en pratique. Nos applications décisionnelles sont passées à PostgreSQL mais nous avons eu d'étranges plaintes sur les applications transactionnelles encore sous Oracle dans le style "la première fois que je lance une recherche dans la journée ,c'est rapide, et ensuite c'est lent !". Toutes ces fonctionnalités sont en cours de développement, d'amélioration et seront bien sûr pleinement opérationnelles au fil du temps. L'avantage avec PostgreSQL est qu'une nouvelle fonctionnalité est toujours utilisable dès son introduction, c'est l'esprit de ce projet qui n'est pas soumis à une logique marketing.

Mise à jour : 06/03/2022