Colonnes liées par une relation d'inégalité - nouvelle solution

Publié le 02/02/2023 par Marc Cousin, Frédéric Yhuel

Paris, le 2 février 2023

Une corrélation entre deux colonnes est une cause fréquente de plan d’exécution sous-optimal. Nous avons récemment publié un article à ce sujet. Peu de temps après, Marc Cousin nous a écrit pour nous proposer une autre solution, qui s’avère meilleure et très intéressante, alors nous la partageons avec vous ici !

Reprenons

Nous avons donc le jeu de test suivant :

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;

Et voici la requête initiale que nous cherchons à optimiser, avec son plan d’exécution :

EXPLAIN (ANALYZE)
 SELECT id FROM frequencies WHERE freqmax < 500000 AND freqmin >= 499000;
                          QUERY PLAN
-------------------------------------------------------------
 Seq Scan on frequencies
  (cost=0.00..25811.00 rows=250269 width=8)
  (actual time=5.553..74.537 rows=495 loops=1)
   Filter: ((freqmax < 500000) AND (freqmin >= 499000))
   Rows Removed by Filter: 999505
 Planning Time: 0.146 ms
 Execution Time: 74.592 ms

Comme expliqué dans l’article précédent, PostgreSQL estime 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é, le résultat ne comporte que 490 lignes.

La solution de Marc

Cependant, nous pouvons réécrire la requête en utilisant le type int4range, qui est un intervalle d’entiers sur 4 octets :

SELECT * FROM frequencies WHERE int4range(499000,500000,'[)') @> int4range(freqmin,freqmax,'[]');

L’expression int4range(499000,500000,'[)') utilise la fonction constructeur du type int4range pour créer un intervalle avec une borne inférieure inclusive, et une borne supérieure exclusive.

L’opérateur @> permet de tester si le premier argument contient le second.

Ce qui nous donne ce plan :

                                          QUERY PLAN
----------------------------------------------------------------------------------------------
 Gather  (cost=1000.00..18561.00 rows=5000 width=16)
         (actual time=6.013..95.742 rows=495 loops=1)
   Workers Planned: 2
   Workers Launched: 2
   ->  Parallel Seq Scan on frequencies
            (cost=0.00..17061.00 rows=2083 width=16)
            (actual time=2.099..88.181 rows=165 loops=3)
         Filter: ('[499000,500001)'::int4range @> int4range(freqmin, freqmax, '[]'::text))
         Rows Removed by Filter: 333168
 Planning Time: 0.372 ms
 Execution Time: 95.794 ms

Plus lent, mais une estimation meilleure. Cependant, la non-utilisation de l’index est logique vu que le filtre se fait sur le résultat d’une fonction.

Il nous faut donc un index fonctionnel de type GiST, plus adapté aux types complexes (intervalles, données géométriques, etc).

CREATE INDEX ON frequencies USING GIST (int4range(freqmin,freqmax,'[]') );
ANALYZE frequencies ;

Et tadam !

                                      QUERY PLAN
-----------------------------------------------------------------------------------------------
 Bitmap Heap Scan on frequencies
  (cost=20.17..1674.73 rows=501 width=16)
  (actual time=1.479..2.845 rows=495 loops=1)
   Recheck Cond: ('[499000,500001)'::int4range @> int4range(freqmin, freqmax, '[]'::text))
   Heap Blocks: exact=470
   ->  Bitmap Index Scan on frequencies_int4range_idx
         (cost=0.00..20.04 rows=501 width=0)
         (actual time=1.274..1.275 rows=495 loops=1)
         Index Cond: (int4range(freqmin, freqmax, '[]'::text) <@ '[499000,500001)'::int4range)
 Planning Time: 0.200 ms
 Execution Time: 2.947 ms

Le temps d’exécution est encore un peu meilleur qu’avec la solution proposée dans l’article précédent, et l’estimation est presque parfaite. De plus, celle-ci reste toujours excellente en faisant varier les différents paramètres du jeu de test (écart entre freqmin et freqmax, nombres de lignes insérées, etc), ce qui n’était pas vraiment le cas avec l’autre solution.

Un grand merci à Marc, en attendant de le voir au PGDay/FOSDEM.

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.