Paris, le 3 janvier 2023

Une corrélation entre deux colonnes est une cause fréquente de plan d’exécution sous-optimal. La solution n’est pas toujours évidente…

Portrait de Frédéric

Une requête lente qui n’utilise pas l’index

En décembre 2022, un client de Dalibo a ouvert un ticket sur la plateforme de support, après avoir identifié une requête qui s’exécutait habituellement en 87 secondes, mais en seulement 600 ms avec le paramétrage enable_seqscan = off.

En cause, une erreur d’estimation sur le nombre de lignes retournées par un des nœuds : 386 807, au lieu de 24 en réalité. Comme 386 807 représente environ un quart des lignes de la table, le planificateur choisit logiquement un parcours séquentiel plutôt qu’un parcours d’index.

Quelles sont les causes habituelles d’une telle erreur d’estimation ? En voici quatre :

  • statistiques trop vieilles (potentiel problème avec l’autovacuum) ;
  • logique booléenne complexe entre plusieurs clauses WHERE ;
  • statistiques insuffisamment précises ;
  • corrélation entre différentes colonnes.

Cas simplifié

Ici nous sommes dans le dernier cas, mais avec une corrélation un peu particulière : les deux colonnes « freqmin » et « freqmax » sont liées par la relation freqmin < freqmax.

Nous pouvons simplifier le cas du client afin de pouvoir l’étudier plus facilement :

CREATE TABLE frequencies (id bigint generated always as identity, freqmin int, freqmax int);
INSERT INTO frequencies(freqmin) SELECT (random()*1000000)::int FROM generate_series(1,1000000);
UPDATE frequencies SET freqmax = freqmin + (random()*1000)::int;
CREATE INDEX ON frequencies(freqmin);
VACUUM ANALYZE frequencies ;
EXPLAIN (ANALYZE)
 SELECT id FROM frequencies WHERE freqmax < 500000 AND freqmin >= 499000;
                          QUERY PLAN
-------------------------------------------------------------
 Seq Scan on frequencies  
  (cost=0.00..25811.00 rows=250207 width=8)
  (actual time=5.553..74.537 rows=490 loops=1)
   Filter: ((freqmax < 500000) AND (freqmin >= 499000))
   Rows Removed by Filter: 999510
 Planning Time: 0.146 ms
 Execution Time: 74.592 ms

PostgreSQL estime donc qu’il va récupérer 250 207 lignes, ce qui est logique si les deux colonnes ne sont pas corrélées, car la probabilité qu’une ligne vérifie le premier filtre freqmax < 500000 est de 50%, même chose (ou presque) pour le deuxième filtre freqmin >= 499000, et les deux probabilités sont multipliées entre elles.

En réalité, on ne récupère que 490 lignes, ce qui est étonnant, car en général on obtient plutôt une sous-estimation de la volumétrie lorsque la corrélation entre en jeu.

Mais puisque l’on sait que freqmax est toujours supérieur à freqmin, la requête peut se ré-écrire comme ceci :

SELECT id FROM frequencies WHERE freqmax BETWEEN 499000 AND 500000 AND freqmin BETWEEN 499000 AND 500000;

Et voici son plan d’exécution :

                           QUERY PLAN    
------------------------------------------------------------------
 Bitmap Heap Scan on frequencies  
  (cost=22.08..2926.98 rows=1 width=8)
  (actual time=0.737..3.238 rows=490 loops=1)
   Recheck Cond: ((freqmin >= 499000) AND (freqmin <= 500000))
   Filter: ((freqmax >= 499000) AND (freqmax <= 500000))
   Rows Removed by Filter: 512
   Heap Blocks: exact=915
   ->  Bitmap Index Scan on frequencies_freqmin_idx 
        (cost=0.00..22.07 rows=965 width=0) 
        (actual time=0.344..0.345 rows=1002 loops=1)
         Index Cond: ((freqmin >= 499000) AND (freqmin <= 500000))
 Planning Time: 0.178 ms
 Execution Time: 3.340 ms

Le temps d’exécution est sensiblement réduit grâce à l’utilisation du Bitmap Index Scan. Cependant, on a maintenant une erreur d’estimation dans l’autre sens (une seule ligne attendue), toujours liée au fait que les deux colonnes sont corrélées.

Statistiques étendues ?

Pourrait-on utiliser les statistiques étendues pour améliorer ça ? Il y a plusieurs types :

  • dependencies ne convient pas, car freqmax n’est pas déterminé par freqmin ;
  • ndistinct ne convient pas pour des inégalités ;
  • mcv ne convient pas non plus pour des inégalités, et la cardinalité des deux colonnes est trop grande.

Le meilleur compromis

Il semble donc qu’il n’y ait pas de solution véritablement satisfaisante. Le mieux que l’on puisse faire est de tester différentes ré-écritures de la requête, celle-ci par exemple :

SELECT id FROM frequencies WHERE freqmin BETWEEN 499000 AND 500000 AND freqmax < 500000;

On obtient alors une meilleure estimation :

                            QUERY PLAN
-------------------------------------------------------------------
 Bitmap Heap Scan on frequencies  
  (cost=22.94..3104.98 rows=521 width=8) 
  (actual time=0.737..3.229 rows=490 loops=1)
   Recheck Cond: ((freqmin >= 499000) AND (freqmin <= 500000))
   Filter: (freqmax < 500000)
   Rows Removed by Filter: 512
   Heap Blocks: exact=915
   ->  Bitmap Index Scan on frequencies_freqmin_idx  
        (cost=0.00..22.81 rows=1038 width=0) 
        (actual time=0.345..0.346 rows=1002 loops=1)
         Index Cond: ((freqmin >= 499000) AND (freqmin <= 500000))
 Planning Time: 0.174 ms
 Execution Time: 3.329 ms

Conclusion

Lorsqu’on identifie une requête lente, on remarque parfois qu’en forçant l’utilisation d’un index (avec enable_seqscan = off), le temps d’exécution est sensiblement réduit, parfois d’un facteur 100 ou 1000. Un DBA peut alors être tenté de jouer sur le paramètre random_page_cost pour favoriser l’utilisation de l’index. Mais celui-ci ne devrait dépendre que de la performance du stockage.

Dans un cas comme celui-là, il est vraiment nécessaire de s’attaquer à la cause première, qui est l’erreur d’estimation sur le nombre de lignes retournées. Parfois, le nom des colonnes donne un indice sur la façon dont elles sont corrélées, comme ici avec freqmin < freqmax, hypothèse qu’il est nécessaire de faire valider par le métier, pour ensuite en tirer profit, avec des statistiques étendues lorsque cela est possible, ou avec une ré-écriture de la requête.

Pour aller plus loin :


Des questions, des commentaires ? Écrivez-nous !


DALIBO

DALIBO est le spécialiste français de PostgreSQL®. Nous proposons du support, de la formation et du conseil depuis 2005.