Références des nœuds

Module J6

Dalibo SCOP

25.09

5 septembre 2025

Sur ce document

Formation	Module J6
Titre	Références des nœuds
Révision	25.09
PDF	https://dali.bo/j6_pdf
EPUB	https://dali.bo/j6_epub
HTML	https://dali.bo/j6_html
Slides	https://dali.bo/j6_slides

Chers lectrices & lecteurs,

Nos formations PostgreSQL sont issues de nombreuses années d’études, d’expérience de terrain et de passion pour les logiciels libres. Pour Dalibo, l’utilisation de PostgreSQL n’est pas une marque d’opportunisme commercial, mais l’expression d’un engagement de longue date. Le choix de l’Open Source est aussi le choix de l’implication dans la communauté du logiciel.

Au‑delà du contenu technique en lui‑même, notre intention est de transmettre les valeurs qui animent et unissent les développeurs de PostgreSQL depuis toujours : partage, ouverture, transparence, créativité, dynamisme… Le but premier de nos formations est de vous aider à mieux exploiter toute la puissance de PostgreSQL mais nous espérons également qu’elles vous inciteront à devenir un membre actif de la communauté en partageant à votre tour le savoir‑faire que vous aurez acquis avec nous.

Nous mettons un point d’honneur à maintenir nos manuels à jour, avec des informations précises et des exemples détaillés. Toutefois malgré nos efforts et nos multiples relectures, il est probable que ce document contienne des oublis, des coquilles, des imprécisions ou des erreurs. Si vous constatez un souci, n’hésitez pas à le signaler via l’adresse formation@dalibo.com !

À propos de DALIBO

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

Retrouvez toutes nos formations sur https://dalibo.com/formations

Remerciements

Ce manuel de formation est une aventure collective qui se transmet au sein de notre société depuis des années. Nous remercions chaleureusement ici toutes les personnes qui ont contribué directement ou indirectement à cet ouvrage, notamment :

Alexandre Anriot, Jean‑Paul Argudo, Carole Arnaud, Alexandre Baron, David Bidoc, Sharon Bonan, Franck Boudehen, Arnaud Bruniquel, Pierrick Chovelon, Damien Clochard, Christophe Courtois, Marc Cousin, Gilles Darold, Ronan Dunklau, Vik Fearing, Stefan Fercot, Dimitri Fontaine, Pierre Giraud, Nicolas Gollet, Nizar Hamadi, Florent Jardin, Virginie Jourdan, Luc Lamarle, Denis Laxalde, Guillaume Lelarge, Alain Lesage, Benoit Lobréau, Jean‑Louis Louër, Thibaut Madelaine, Cédric Martin, Adrien Nayrat, Alexandre Pereira, Flavie Perette, Robin Portigliatti, Thomas Reiss, Maël Rimbault, Jehan-Guillaume de Rorthais, Julien Rouhaud, Stéphane Schildknecht, Julien Tachoires, Nicolas Thauvin, Be Hai Tran, Christophe Truffier, Arnaud de Vathaire, Cédric Villemain, Thibaud Walkowiak, Frédéric Yhuel.

Forme de ce manuel

Les versions PDF, EPUB ou HTML de ce document sont structurées autour des slides de nos formations. Le texte suivant chaque slide contient le cours et de nombreux détails qui ne peuvent être données à l’oral.

Licence Creative Commons CC-BY-NC-SA

Cette formation est sous licence CC-BY-NC-SA. Vous êtes libre de la redistribuer et/ou modifier aux conditions suivantes :

Paternité
Pas d’utilisation commerciale
Partage des conditions initiales à l’identique

Vous n’avez pas le droit d’utiliser cette création à des fins commerciales.

Si vous modifiez, transformez ou adaptez cette création, vous n’avez le droit de distribuer la création qui en résulte que sous un contrat identique à celui-ci.

Vous devez citer le nom de l’auteur original de la manière indiquée par l’auteur de l’œuvre ou le titulaire des droits qui vous confère cette autorisation (mais pas d’une manière qui suggérerait qu’ils vous soutiennent ou approuvent votre utilisation de l’œuvre). À chaque réutilisation ou distribution de cette création, vous devez faire apparaître clairement au public les conditions contractuelles de sa mise à disposition. La meilleure manière de les indiquer est un lien vers cette page web. Chacune de ces conditions peut être levée si vous obtenez l’autorisation du titulaire des droits sur cette œuvre. Rien dans ce contrat ne diminue ou ne restreint le droit moral de l’auteur ou des auteurs.

Le texte complet de la licence est disponible sur http://creativecommons.org/licenses/by-nc-sa/2.0/fr/legalcode

Cette licence interdit la réutilisation pour l’apprentissage d’une IA. Elle couvre les diapositives, les manuels eux-mêmes et les travaux pratiques.

Cette formation peut également contenir quelques images et schémas dont la redistribution est soumise à des licences différentes qui sont alors précisées.

Marques déposées

PostgreSQL® Postgres® et le logo Slonik sont des marques déposées par PostgreSQL Community Association of Canada.

Versions de PostgreSQL couvertes

Ce document ne couvre que les versions supportées de PostgreSQL au moment de sa rédaction, soit les versions 13 à 17.

Référence sur les nœuds d’exécution

Introduction

Types de nœuds principaux
- parcours de table (Seq Scan)
- parcours d’index (Index Scan & variantes)
- jointures (Nested Loop, Merge Join, Hash Join…)
- opérateurs sur des ensembles (Append, Except, Intersect…)
Et quelques autres :
- Sort, _*Aggregate_, Unique, Limit, Materialize, Memoize…
Plusieurs variantes pour chacun

Un plan d’exécution est un arbre. Chaque nœud de l’arbre est une opération à effectuer par l’exécuteur. Le planificateur arrange les nœuds pour que le résultat final soit le bon, et qu’il soit récupéré le plus rapidement possible.

Il y a plusieurs types de nœuds :

les parcours, qui permettent de lire les données dans les tables en passant, essentiellement :
- soit par la table ;
- soit par l’index ;
les jointures, qui permettent de joindre deux ensembles de données ;
les opérateurs sur des ensembles, qui là aussi vont joindre deux ensembles ou plus ;
et les opérations sur un seul ensemble : tri, limite, agrégat, etc.

Cet annexe a pour but d’entrer dans le détail de chaque type de nœuds, ses avantages et inconvénients.

Pour chacun il existe plusieurs variantes, par exemple les variantes parallélisées des parcours ou agrégats.

Les parcours

Un seq scan et deux index Scan à la base d’un plan

Principe des parcours

Rien en entrée
Renvoie un ensemble de données des tables
- trié ou non
- filtré ou non
Exemples :
- parcours séquentiel d’une table, avec ou sans filtrage des enregistrements produits
- parcours via un index, avec ou sans filtrage supplémentaire

Parcours de table

Seq Scan : principe

Parcours séquentiel de la table (Sequential Scan ou Seq Scan)
- parallélisation possible (Parallel Seq Scan)
La table est lue entièrement
- même si seulement quelques lignes satisfont la requête
- sauf avec LIMIT sans ORDER BY
Séquentiellement, par bloc de 8 ko

Seq Scan : performances

Idéal pour :
- petites tables
- % de retour élevé des blocs
- partitions entières
Contre-performant pour :
- quelques lignes d’une grande table
Optimisation : synchronize_seqscans

Le parcours de table est intéressant pour les performances dans deux cas :

Très petites tables :

Les très petites tables qui tiennent dans une poignée de blocs sont parcourues très vite. L’utilisation d’un index ne ferait pas gagner de temps.

Nombreuses lignes retournées :

Quand une partie significative d’une grosse table doit être retournée, les allers-retours entre la table et un index, et l’accès à l’index lui-même ne sont plus rentables. PostgreSQL peut alors juger qu’il vaut mieux lire toute la table et ignorer certaines lignes.

La ratio de lignes ramenées à partir duquel PostgreSQL bascule entre un appel d’index et un Seq Scan dépend en bonne partie des paramètres random_page_cost et seq_page_cost. Sur un disque rotatif, les accès de blocs isolés sont beaucoup plus coûteux que sur un SSD. Il dépend aussi d’autres choses comme la corrélation physique, c’est-à-dire la relation entre la valeur de la ligne dans la table et son emplacement sur disque. En effet, récupérer une ligne implique de récupérer tout le bloc où elle se trouve. Si les statistiques montrent que la corrélation est mauvaise, les lignes satisfaisant un critère sont dispersées, et la chance de devoir lire tous les blocs plus élevée.

Évidemment, si toute la table doit être lue sans filtrage, le Seq Scan demeure incontournable.

Exemples :

Voici quelques exemples à partir de ce jeu de tests :

CREATE TABLE t1 (c1 integer);
INSERT INTO t1 (c1) SELECT generate_series(1, 100000);
VACUUM ANALYZE t1;
SET jit TO off ; -- pour simplifier les plans suivants

Ici, nous faisons une lecture complète de la table. De ce fait, un parcours séquentiel sera plus rapide du fait de la rapidité de la lecture séquentielle des blocs :

EXPLAIN SELECT * FROM t1 ;

                        QUERY PLAN
----------------------------------------------------------
 Seq Scan on t1  (cost=0.00..1443.00 rows=100000 width=4)

Le coût est relatif au nombre de blocs lus, au nombre de lignes décodées et à la valeur des paramètres seq_page_cost et cpu_tuple_cost. Si un filtre est ajouté, cela aura un coût supplémentaire dû à l’application du filtre sur toutes les lignes de la table (pour trouver celles qui correspondent à ce filtre) :

EXPLAIN SELECT * FROM t1 WHERE c1=1000 ;

                     QUERY PLAN
-----------------------------------------------------
 Seq Scan on t1  (cost=0.00..1693.00 rows=1 width=4)
   Filter: (c1 = 1000)

Ce coût supplémentaire dépend du nombre de lignes dans la table et de la valeur du paramètre cpu_operator_cost (défaut 0,0025) ou de la valeur du paramètre COST de la fonction appelée. L’exemple ci-dessus montre le coût (1693) en utilisant l’opérateur standard d’égalité. Maintenant, si on crée une fonction qui utilise cet opérateur (écrite en PL/pgSQL, elle masque l’opérateur à l’optimiseur), avec un coût forcé à 10 000, cela donne :

CREATE FUNCTION egal(integer,integer) RETURNS boolean
LANGUAGE plpgsql AS $$
BEGIN
  RETURN $1 = $2;
END $$  COST 10000 ;

EXPLAIN SELECT * FROM t1 WHERE egal(c1, 1000) ;

                         QUERY PLAN
------------------------------------------------------------
 Seq Scan on t1  (cost=0.00..2501443.00 rows=33333 width=4)
   Filter: egal(c1, 1000)

La ligne Filter indique le filtre réalisé. Le nombre de lignes indiqué par rows= est le nombre de lignes après filtrage. Pour savoir combien de lignes ne satisfont pas le prédicat de la clause WHERE, il faut exécuter la requête et donc utiliser l’option EXPLAIN :

EXPLAIN (ANALYZE,BUFFERS)
SELECT * FROM t1 WHERE c1=1000 ;

                     QUERY PLAN
-----------------------------------------------------
 Seq Scan on t1  (cost=0.00..1693.00 rows=1 width=4) (actual time=0.093..6.032 rows=1 loops=1)
   Filter: (c1 = 1000)
   Rows Removed by Filter: 99999
   Buffers: shared hit=443
 Planning Time: 0.062 ms
 Execution Time: 6.052 ms

La ligne Rows Removed by Filter indique que 99 999 lignes ont été rencontrées et ignorées. La vision graphique du plan sur explain.dalibo.com affiche donc un avertissement sur ce taux élevé de rejet. Cela doit faire envisager la création d’un index.

L’option BUFFERS permet en plus de savoir le nombre de blocs lus dans le cache (hit) et hors du cache, (read). Les 443 blocs (3,5 Mo) de la table sont ici dans le cache.

Le calcul réalisé pour le coût final est le suivant :

SELECT
  round((
    current_setting('seq_page_cost')::numeric*relpages      +
    current_setting('cpu_tuple_cost')::numeric*reltuples    +
    current_setting('cpu_operator_cost')::numeric*reltuples
        )::numeric, 2)
  AS cout_final
FROM pg_class
WHERE relname='t1';

Synchronisation des Seq Scan :

Si le paramètre synchronize_seqscans est à on (et il l’est par défaut), le processus qui entame une lecture séquentielle cherche en premier lieu si un autre processus ne ferait pas une lecture séquentielle de la même table. Si c’est le cas, le second processus démarre son parcours de table à l’endroit où le premier processus est en train de lire, ce qui lui permet de profiter des données mises en cache par ce processus. L’accès au disque étant bien plus lent que l’accès mémoire, les processus restent naturellement synchronisés pour le reste du parcours de la table, et les lectures ne sont donc réalisées qu’une seule fois. Le début de la table restera à être lu indépendamment. Cette optimisation permet de diminuer le nombre de blocs lus par chaque processus en cas de lectures parallèles de la même table.

Sans autre tri, l’ordre des lignes retournées peut donc différer alors que les requêtes sont identiques et simultanées. Mais aucune application ne doit supposer que les lignes sont dans un certain ordre sans ORDER BY explicite.

Parcours parallélisé :

Une nouvelle optimisation vient de la parallélisation apparue avec PostgreSQL 9.6. Le nœud devient un Parallel Seq Scan. Le processus responsable de la requête demande l’exécution de plusieurs processus, appelés workers, qui ont tous pour charge de lire une partie de la table et d’appliquer le filtre. Les nouveaux blocs lus depuis le disque sont enregistrés en mémoire partagée. Chaque worker travaille sur des blocs différents. Quand il a terminé de travailler sur un bloc, il consulte la mémoire partagée pour s’attribuer d’autres blocs à traiter. Il n’y a aucune assurance que chaque worker travaillera sur le même nombre de blocs au final. Voici un exemple de plan parallélisé pour un parcours de table :

CREATE TABLE tp AS
SELECT i AS c1, i AS c2 FROM generate_series (1,1_000_000) i ;
VACUUM ANALYZE tp ; 

EXPLAIN (ANALYZE,BUFFERS)
SELECT sum(c1) FROM tp WHERE c1 BETWEEN 100000 AND 600000 ;

                                QUERY PLAN
-------------------------------------------------------------------------
 Finalize Aggregate  (cost=12246.29..12246.30 rows=1 width=8) (actual time=32.636..34.167 rows=1 loops=1)
   Buffers: shared hit=2304 read=2176
   I/O Timings: shared read=2.891
   ->  Gather  (cost=12246.08..12246.29 rows=2 width=8) (actual time=32.580..34.162 rows=3 loops=1)
         Workers Planned: 2
         Workers Launched: 2
         Buffers: shared hit=2304 read=2176
         I/O Timings: shared read=2.891
         ->  Partial Aggregate  (cost=11246.08..11246.09 rows=1 width=8) (actual time=22.147..22.147 rows=1 loops=3)
               Buffers: shared hit=2304 read=2176
               I/O Timings: shared read=2.891
               ->  Parallel Seq Scan on tp  (cost=0.00..10730.00 rows=206431 width=4) (actual time=2.225..15.961 rows=166667 loops=3)
                     Filter: ((c1 >= 100000) AND (c1 <= 600000))
                     Rows Removed by Filter: 166666
                     Buffers: shared hit=2304 read=2176
                     I/O Timings: shared read=2.891
 Planning:
   Buffers: shared hit=8
 Planning Time: 0.169 ms
 Execution Time: 34.199 ms

La vision graphique est sur https://explain.dalibo.com/plan/c92a611h5g4b33cg.

Dans ce cas, le planificateur a prévu l’exécution de deux workers, et deux ont bien été lancés lors de l’exécution de la requête. Deux Parallel Scan apparaissent, mais le processus principal participe aussi (par défaut), d’où la mention loops=3. Chacun des nœuds a en moyenne lu 2304 blocs dans le cache, 2176 hors du cache, ignoré 166 666 lignes et conservé 206 431 lignes. Une vision plus étoffée avec le détail des workers peut s’obtenir avec EXPLAIN (ANALYZE,BUFFERS,VERBOSE).

Le résultat de chaque Parallel Scan est récupéré par un Partial Aggregate, qui récupère les lignes et agrège au niveau d’un worker. Chaque Partial Aggregate renvoie 1 ligne de décompte (là encore 3 fois). Au-dessus, le nœud Gather est chargé de récupérer les 3 lignes des workers. La somme des agrégats partiels est réalisée tout en haut dans un nœud Finalize Aggregate qui renvoie l’unique ligne finale de résultat.

Partitionnement :

Un des intérêts du partitionnement est de favoriser les parcours complets sur un ensemble de données. Par exemple, un partitionnement par mois rendra optimales une requête agrégeant toutes les lignes d’un mois entier sans filtrage : il suffit de parcourir la partition (une table, en fait) du mois, sans index ni filtrage, et uniquement cette partition. Bien sûr, il faut choisir ce partitionnement en fonction des requêtes les plus sensibles.

Parcours d’index : Index Scan

Index Scan : principe

Parcours « aléatoire » de l’index
Pour chaque enregistrement correspondant à la recherche
- accès direct au bloc de la table
- vérification de la visibilité de la ligne
- renvoie des lignes triées

Parcourir une table prend du temps, surtout quand on cherche à ne récupérer que quelques lignes de cette table. Le but d’un index est donc d’utiliser une structure de données optimisée pour satisfaire une recherche particulière (on parle de prédicat).

Sur PostgreSQL, l’index est un fichier séparé de la table. Il ne contient que les données indexées, triées, et l’emplacement des lignes où se trouvent ces données dans la table (bloc et ligne).

La donnée indexée peut être :

le contenu d’un champ d’une table ;
le contenu de plusieurs champs, auquel cas l’ordre est important ;
le résultat d’une fonction sur ces champs.

Dans le cas de loin le plus courant, l’index est de type B-tree. Cette structure est un arbre. La recherche consiste à suivre la structure de l’arbre pour trouver le premier enregistrement correspondant au prédicat, puis suivre les feuilles de l’arbre jusqu’au dernier enregistrement vérifiant le prédicat. Étant donné la façon dont l’arbre est stocké sur disque, les accès concernent des blocs éparpillés, et, sur un disque rotatif, cela peut provoquer de nombreux déplacements de la tête de lecture. De plus, les enregistrements sont habituellement éparpillés dans la table, et retournés dans un ordre totalement différent de leur ordre physique par le parcours sur l’index. Cet accès à la table génère donc énormément d’accès aléatoires. Or, ce type d’activité est généralement le plus lent sur un disque magnétique. C’est pourquoi le parcours d’une large portion d’un index est très lent. PostgreSQL ne cherchera à utiliser un index que s’il suppose qu’il aura peu de lignes à récupérer.

Un autre problème des performances sur les index, spécifique à PostgreSQL, est que les informations de visibilité des lignes sont uniquement stockées dans la table. Quand une ligne est marquée comme effacée dans la table, l’index conserve un temps le pointeur vers cette ligne (il peut être nettoyé bien plus tard). Cela veut dire que, pour chaque élément de l’index correspondant au filtre, il faut lire la ligne dans la table pour vérifier qu’elle est bien visible pour la transaction en cours. Ce n’est pas vraiment un problème dans le cas général, où le but de la requête est justement de récupérer ces lignes, et les autres colonnes demandées, généralement absentes de l’index. Mais dans les cas où l’index contient déjà toute l’information pour satisfaire le filtre, l’accès à la table semble inutile. Nous verrons que l’Index Only Scan existe pour traiter ce cas précis.

Voici l’algorithme permettant un parcours d’index avec PostgreSQL :

Pour tous les éléments de l’index :
- chercher l’élément souhaité dans l’index ;
- récupérer le bloc de l’élément trouvé, puis la ligne ;
- vérifier sur la ligne qu’il est visible par la transaction ;
- lire les autres colonnes nécessaires ;
- filtrer les lignes trouvées en fonction des critères que l’index ne pouvait pas satisfaire.

Un Index Scan ne consiste donc pas qu’à consulter l’index, mais aussi la table, et à opérer des filtres supplémentaires sur les données récupérées dans la table.

Les autres types d’index connus de PostgreSQL (GiST, hash, GIN…) reposent généralement sur une variante de ce principe, chacun avec sa spécificité.

Index Scan : performances

Intéressant pour :
- les accès à peu de lignes dans la table
- les tris (ORDER BY…)
Non adapté à :
- récupération de trop nombreuses lignes
Coût en maintenance
Parallélisation (Parallel Index Scan)
- B-Tree uniquement

Un parcours d’index est donc très coûteux, principalement à cause des déplacements de la tête de lecture. Un parcours d’index n’est préférable à un parcours de table que si la recherche ne va ramener qu’un faible pourcentage de la table. Comme PostgreSQL calcule le nombre de blocs, la corrélation physique a aussi une influence.

Le gain possible est très important par rapport à un parcours séquentiel de table. Par contre, un parcours d’index se révèle très lent pour lire un gros pourcentage de la table. Les accès aléatoires diminuent spectaculairement les performances sur les disques rotatifs (par défaut, le paramètre random_page_cost, lié au coût de lecture aléatoire d’une page est 4 fois supérieur à celui de la lecture séquentielle d’une page, seq_page_cost). La situation est bien meilleure sur les disques SSD et NVMe récents mais le principe reste le même.

Il est à noter que, contrairement au parcours de table, le parcours d’index renvoie toujours les données triées. C’est le seul parcours à le faire. Il permet donc d’optimiser la clause ORDER BY d’une requête, et d’éviter un tri des résultats, parfois très lourd. L’index est aussi utilisable dans le cas des tris descendants, et dans ce cas, le nœud est nommé Index Scan Backward (sens inverse). Attention, l’ORDER BY doit être dans le même ordre que les champs de l’index pour être optimal.

Cet index peut aussi favoriser l’utilisation d’autres nœuds qui savent utiliser des données triées, en premier lieu les jointures par Merge Join, ou des agrégations.

Il ne faut pas oublier aussi le coût de mise à jour de l’index. Si un index n’est pas utilisé, il coûte cher en maintenance (ajout des nouvelles entrées, suppression des entrées obsolètes, place sur le disque et le cache, etc.). En général, ajouter un index reste « rentable» puisqu’il accélère les lectures, voire les écritures (sur l’index). Mais il faut vérifier que l’on n’a pas des index inutiles, en double (PostgreSQL le permet) ou redondants, et l’on n’indexera pas « à tout hasard » des champs.

Enfin, il est à noter que ce type de parcours est aussi consommateur en CPU.

Voici un exemple montrant les deux types de parcours et ce que cela occasionne comme lecture disque. Commençons par créer une toute petite table avec quelques données et un index :

DROP TABLE IF EXISTS t1 ;
CREATE TABLE t1 (c1 integer, c2 integer);
INSERT INTO t1 VALUES (1,2), (2,4), (3,6);
CREATE INDEX i1 ON t1(c1);
VACUUM ANALYZE t1;

Essayons maintenant de lire la table avec un simple parcours séquentiel :

EXPLAIN (ANALYZE,BUFFERS) SELECT * FROM t1 WHERE c1 = 2;

                  QUERY PLAN
--------------------------------------------------
 Seq Scan on t1  (cost=0.00..1.04 rows=1 width=8) (actual time=0.012..0.013 rows=1 loops=1)
   Filter: (c1 = 2)
   Rows Removed by Filter: 2
   Buffers: shared hit=1
 Planning:
   Buffers: shared hit=13 read=1
   I/O Timings: shared read=0.013
 Planning Time: 0.199 ms
 Execution Time: 0.031 ms

Nous obtenons un parcours séquentiel (Seq Scan). En effet, la table est tellement petite (elle tient dans un bloc de 8 ko) qu’utiliser l’index coûterait forcément plus cher. Grâce à l’option BUFFERS, nous savons d’ailleurs que seul un bloc a été lu.

À titre purement expérimental, pour forcer un parcours d’index, nous allons désactiver les parcours séquentiels et réinitialiser ses statistiques :

SET enable_seqscan TO off;
SELECT pg_stat_reset();

Il existe aussi un paramètre, appelé enable_indexscan, pour désactiver les parcours d’index, à titre expérimental.

Maintenant relançons la requête :

EXPLAIN (ANALYZE,BUFFERS) SELECT * FROM t1 WHERE c1 = 2;

                         QUERY PLAN
-------------------------------------------------------------
 Index Scan using i1 on t1  (cost=0.13..8.15 rows=1 width=8) (actual time=0.055..0.057 rows=1 loops=1)
   Index Cond: (c1 = 2)
   Buffers: shared hit=1 read=1
   I/O Timings: shared read=0.010
 Planning Time: 0.091 ms
 Execution Time: 0.077 ms

Nous avons bien un parcours d’index. Vérifions les statistiques sur l’activité :

SELECT relname, heap_blks_read, heap_blks_hit,
       idx_blks_read, idx_blks_hit
FROM   pg_statio_user_tables
WHERE  relname='t1';

 relname | heap_blks_read | heap_blks_hit | idx_blks_read | idx_blks_hit 
---------+----------------+---------------+---------------+--------------
 t1      |              0 |             1 |             0 |            2

Deux blocs ont été lus dans l’index (colonnes idx_blks_*) et un autre a été lu dans la table (colonnes heap_blks_* à 1). Le plus impactant est l’accès aléatoire sur l’index et la table. Ce n’est pas un souci avec peu de lignes, mais avec de gros volumes il serait bon d’avoir une lecture de l’index, puis une lecture séquentielle de la table. C’est le but du Bitmap Index Scan.

Parcours d’index bitmap

Bitmap Scan : principe

Bitmap Index Scan / Bitmap Heap Scan
Réduire les allers-retours index ⇆ table
- trouver les blocs de l’index
- puis lecture des blocs de la table
Combinaison de plusieurs index en mémoire
- nœud BitmapAnd
- nœud BitmapOr
Index B-tree, GIN, BRIN…

D’autres SGBD connaissent des index de type « bitmap », mais pas PostgreSQL. Celui-ci crée des structures bitmap en mémoire lorsque son utilisation a un intérêt. Cela se manifeste par le couple de nœuds Bitmap Index Scan et Bitmap Heap Scan.

Le principe est de diminuer les déplacements de la tête de lecture en découplant le parcours de l’index du parcours de la table. Même avec un SSD, cette méthode évite d’aller chercher trop souvent les mêmes blocs et améliore l’utilisation du cache.

Son principe est le suivant :

lecture en une passe de l’index (Bitmap Index Scan) ;
récupération des TID (tuple id) en mémoire (1 bit par ligne dans le cas idéal) ;
tri des blocs à parcourir dans la table dans l’ordre physique de la table (pas dans l’ordre logique de l’index) ;
lecture en une passe de la partie intéressante de la table (Bitmap Heap Scan).

Les parcours d’index bitmap sont utilisables sur les B-tree bien sûr, mais aussi sur d’autres types d’index comme GIN, GiST, BRIN… C’est parfois le seul parcours disponible, certains types ayant de toute façon besoin d’une phase de recheck des lignes trouvées dans la table.

Un bitmap est souvent utilisé quand il y a un grand nombre de valeurs à filtrer, notamment pour les clauses IN et ANY.

Ce type d’index présente un autre gros intérêt : pouvoir combiner plusieurs index en mémoire. Les bitmaps de TID obtenus se combinent facilement avec des opérations booléennes AND et OR.

Exemple :

Cet exemple utilise PostgreSQL 17 dans sa configuration par défaut. La table suivante possède trois champs indexés susceptibles de servir de critères de recherche :

DROP TABLE IF EXISTS tbt ;
CREATE UNLOGGED TABLE tbt
(i int GENERATED ALWAYS AS IDENTITY PRIMARY KEY, j int, k int, t text)  ;

INSERT INTO tbt (j,k,t)
SELECT (i / 1000) , i / 777, chr (64+ (i % 58))
FROM generate_series(1,10000000) i ;

CREATE INDEX tbt_j_idx ON tbt (j) ;
CREATE INDEX tbt_k_idx ON tbt (k) ;
CREATE INDEX tbt_t_idx ON tbt (t) ;

VACUUM ANALYZE tbt ;

Lors de la recherche sur plusieurs critères, les lignes renvoyées par les Bitmap Index Scan peuvent être combinées :

-- pour la lisibilité des plans
SET max_parallel_workers_per_gather  TO 0 ;
SET jit TO off ;

EXPLAIN (ANALYZE, BUFFERS, VERBOSE, SETTINGS)
SELECT i, j, k, t  FROM tbt
WHERE j = 8
AND k = 10
AND t = 'a';

                               QUERY PLAN
-------------------------------------------------------------------------------
 Bitmap Heap Scan on public.tbt  (cost=22.97..26.99 rows=1 width=14) (actual time=0.096..0.163 rows=9 loops=1)
   Output: i, j, k, t
   Recheck Cond: ((tbt.k = 10) AND (tbt.j = 8))
   Filter: (tbt.t = 'a'::text)
   Rows Removed by Filter: 538
   Heap Blocks: exact=4
   Buffers: shared read=11
   I/O Timings: shared read=0.028
   ->  BitmapAnd  (cost=22.97..22.97 rows=1 width=0) (actual time=0.075..0.075 rows=0 loops=1)
         Buffers: shared read=7
         I/O Timings: shared read=0.019
         ->  Bitmap Index Scan on tbt_k_idx  (cost=0.00..10.60 rows=822 width=0) (actual time=0.039..0.039 rows=777 loops=1)
               Index Cond: (tbt.k = 10)
               Buffers: shared read=4
               I/O Timings: shared read=0.011
         ->  Bitmap Index Scan on tbt_j_idx  (cost=0.00..12.12 rows=1025 width=0) (actual time=0.034..0.034 rows=1000 loops=1)
               Index Cond: (tbt.j = 8)
               Buffers: shared read=3
               I/O Timings: shared read=0.008
 Settings: search_path = '"$user", public, topology', max_parallel_workers_per_gather = '0', jit = 'off'
 Query Identifier: 6107944285316481754
 Planning:
   Buffers: shared hit=48 read=1
   I/O Timings: shared read=0.004
 Planning Time: 0.224 ms
 Execution Time: 0.181 ms

Dans le plan précédent :

deux Bitmap Index Scan parcourent séparément deux index, qui remontent l’un 777 lignes (toutes les lignes de la table où k vaut 10), l’autre 1000 lignes (où j vaut 8) ;
le troisième index sur t est ignoré : il y a trop de lignes avec cette valeur (un décompte en trouverait 172 414), et surtout dispersées dans toute la table ;
un nœud BitmapAnd se charge de récupérer les résultats et de faire la combinaison logique ;
il en résulte que seulement 4 blocs dans la table possédent des lignes correspondant aux deux critères (mention Heap Blocks) ;
le Bitmap Heap Scan va dans la table lire ces 4 blocs séquentiellement, et une seule fois chacun, et trouve 547 lignes ;
la clause Recheck vérifie que ces lignes sont réellement visibles par la transaction (ici rien n’est rejeté) ;
il reste à appliquer le critère non géré par les index utilisés, soit t = 'a' : c’est le rôle de la clause Filter, qui écarte 538 lignes et n’en garde que 9.

Clause OR :

Les index sont également utiles avec une clause OR :

EXPLAIN (ANALYZE,BUFFERS, COSTS)
SELECT i, j, k, t  FROM tbt
WHERE j = 8
OR k = 10
OR t = 'a';

                               QUERY PLAN
-------------------------------------------------------------------------------
 Bitmap Heap Scan on tbt  (cost=1997.64..59048.55 rows=171163 width=14) (actual time=26.325..166.924 rows=173623 loops=1)
   Recheck Cond: ((j = 8) OR (k = 10) OR (t = 'a'::text))
   Heap Blocks: exact=54054
   Buffers: shared hit=11 read=54198 written=10709
   I/O Timings: shared read=60.286 write=19.675
   ->  BitmapOr  (cost=1997.64..1997.64 rows=171195 width=0) (actual time=18.383..18.384 rows=0 loops=1)
         Buffers: shared hit=7 read=148
         I/O Timings: shared read=0.398
         ->  Bitmap Index Scan on tbt_j_idx  (cost=0.00..12.17 rows=1032 width=0) (actual time=0.040..0.040 rows=1000 loops=1)
               Index Cond: (j = 8)
               Buffers: shared hit=3
         ->  Bitmap Index Scan on tbt_k_idx  (cost=0.00..10.68 rows=832 width=0) (actual time=0.030..0.030 rows=777 loops=1)
               Index Cond: (k = 10)
               Buffers: shared hit=4
         ->  Bitmap Index Scan on tbt_t_idx  (cost=0.00..1846.42 rows=169331 width=0) (actual time=18.312..18.312 rows=172414 loops=1)
               Index Cond: (t = 'a'::text)
               Buffers: shared read=148
               I/O Timings: shared read=0.398
 Planning:
   Buffers: shared hit=107 read=4
   I/O Timings: shared read=0.038
 Planning Time: 0.526 ms
 Execution Time: 170.909 ms

Ce plan utilise cette fois les trois index.

Au final, le Bitmap Heap Scan lit quand même toute la table, qui fait 54 054 blocs ! En effet, il y a des t='a' dans tous les blocs (c’est le cas le plus défavorable).

Cependant, 98 % des comparaisons de critères sont tout de même évitées. Répéter le plan après avoir tapé ceci :

SET enable_bitmapscan TO off;

mènerait à un parcours de table séquentiel trois fois plus long. Réactiver la parallélisation donnerait un plan parallélisé encore un peu moins efficace. Ne pas oublier d’annuler ce paramétrage ensuite :

RESET enable_bitmapscan ;

Bitmap Scan : performances

Indiqué pour :
- de nombreuses lignes
- bonne corrélation
- combinaison de critères IN, ANY
- combinaison d’index AND/OR
Mais :
- coût de démarrage important
- pas intéressant avec LIMIT
Parallélisation possible
Sensible à :
- work_mem (sinon lossy)
- effective_cache_size
- effective_io_concurrency

Avec des B-tree, l’intérêt peut être énorme s’il y a une certaine corrélation des données avec l’emplacement physique. Il permet de réduire les accès aléatoires, ce qui est intéressant avec des disques qui ont un bon débit mais une mauvaise latence (disques mécaniques, baie surchargée).

Le coût de démarrage est généralement important à cause de la lecture préalable de l’index et du tri des TID. Ce type de parcours est donc moins intéressant quand on recherche un coût de démarrage faible (clause LIMIT, curseur…). Un parcours d’index simple sera généralement choisi dans ce cas.

Le paramètre enable_bitmapscan permet d’activer ou de désactiver l’utilisation des parcours d’index bitmap, à titre expérimental.

work_mem :

Si le paramètre work_mem est trop bas, PostgreSQL n’a plus la place de stocker un bit par ligne dans son tableau, mais utilise un bit par page. La mention lossy apparaît alors sur la ligne Heap Blocks, et toutes les lignes de la page doivent être vérifiées lors de la phase Recheck. Avec la requête précédente, la performance est cette fois bien pire qu’un parcours complet :

SET work_mem TO '256kB' ;

EXPLAIN (ANALYZE,BUFFERS, COSTS)
SELECT i, j, k, t  FROM tbt
WHERE j = 8
OR k = 10
OR t = 'a';

                               QUERY PLAN
-------------------------------------------------------------------------------
 Bitmap Heap Scan on tbt  (cost=1997.64..224533.50 rows=171163 width=14) (actual time=11.596..756.488 rows=173623 loops=1)
   Recheck Cond: ((j = 8) OR (k = 10) OR (t = 'a'::text))
   Rows Removed by Index Recheck: 9350021
   Heap Blocks: exact=2620 lossy=51434
   Buffers: shared read=54209
   I/O Timings: shared read=59.028
   ->  BitmapOr  (cost=1997.64..1997.64 rows=171195 width=0) (actual time=10.811..10.813 rows=0 loops=1)
         Buffers: shared read=155
         I/O Timings: shared read=0.360
         ->  Bitmap Index Scan on tbt_j_idx  (cost=0.00..12.17 rows=1032 width=0) (actual time=0.622..0.622 rows=1000 loops=1)
               Index Cond: (j = 8)
               Buffers: shared read=3
               I/O Timings: shared read=0.015
         ->  Bitmap Index Scan on tbt_k_idx  (cost=0.00..10.68 rows=832 width=0) (actual time=0.037..0.038 rows=777 loops=1)
               Index Cond: (k = 10)
               Buffers: shared read=4
               I/O Timings: shared read=0.012
         ->  Bitmap Index Scan on tbt_t_idx  (cost=0.00..1846.42 rows=169331 width=0) (actual time=10.150..10.150 rows=172414 loops=1)
               Index Cond: (t = 'a'::text)
               Buffers: shared read=148
               I/O Timings: shared read=0.334
 Planning Time: 0.108 ms
 Execution Time: 760.607 ms

effective_cache_size :

Les nœuds Bitmap Scan sont favorisés par une valeur importante du paramètre effective_cache_size, qui estime la quantité totale de cache disponible.

effective_io_concurrency :

Ce paramètre influe notablement sur la vitesse d’exécution des Bitmap Scan, entre autres. effective_io_concurrency a pour but d’indiquer le nombre d’opérations disques possibles en même temps pour un client (prefetch). Il n’a d’intérêt que si un nœud Bitmap Scan a été choisi. Cela n’arrive qu’avec un certain nombre de lignes à récupérer, et est favorisé par une valeur importante de effective_cache_size et un peu de corrélation physique dans la table.

La valeur d’effective_io_concurrency n’influe pas sur le choix du plan, mais sa valeur peut notablement accélérer l’exécution du Bitmap Heap Scan. Le temps de lecture peut fréquemment être divisé par 3 ou plus.

Les valeurs possibles d’effective_io_concurrency vont de 0 à 1000. En principe, sur un disque magnétique seul, la valeur 1 ou 0 peut convenir. Avec du SSD, et encore plus du NVMe, il est possible de monter à plusieurs centaines, étant donné la rapidité de ce type de disque. Trouver la bonne valeur dépend de divers paramètres liés aux caractérisques exactes des disques et de leur paramétrage noyau. Le read ahead du noyau intervient également. Le comportement de PostgreSQL sur ce point change aussi avec les versions. De plus, à partir d’un certain nombre de blocs, les I/O peuvent simplement saturer.

La valeur par défaut de 1 (jusque PostgreSQL 17) a été choisie de manière très conservatrice. Les développeurs ont décidé que la valeur 16 est plus intéressante, même sur de vieux disques, et que ce sera le défaut à partir de PostgreSQL 18, qui inclut d’autres améliorations.

À l’inverse, la mauvaise latence de certains systèmes aux disques en principe performants (baies surchargées, certains stockages cloud…) peut parfois être compensée par un effective_io_concurrency plus élevé.

Il faut tester avec vos requêtes qui utilisent des Bitmap Heap Scan, et tenir compte du nombre de requêtes simultanées, mais effective_io_concurrency = 16 semble un bon point de départ, même sur une configuration modeste. Montez si vous avez de bons disques.

Une valeur excessive de effective_io_concurrency mène à un gaspillage de CPU : ne pas monter trop haut sans preuve de l’utilité, surtout sur un système très chargé.

Pour les systèmes RAID matériels, selon la documentation, configurer ce paramètre en fonction du nombre n de disques utiles dans le RAID (n/2 s’il s’agit d’un RAID 1, n-1 s’il s’agit d’un RAID 5 ou 6, n/2 s’il s’agit d’un RAID 10).

(Avant la version 13, le principe d’effective_io_concurrency était le même, mais la valeur exacte de ce paramètre devait être 2 à 5 fois plus basse comme le précise la formule des notes de version de la version 13.)

Parcours d’index seul : Index Only Scan

CREATE INDEX ON t1 (c1) ;

SELECT c1 FROM t1 WHERE c1 < 10 ;

Avant 9.2 : PostgreSQL devait lire l’index + la table
À présent : le planificateur utilise la Visibility Map
- nœud Index Only Scan
- B-tree
- GiST, SP-GiST : selon opérateur

Répétons que les informations de visibilité d’une ligne sont stockées dans la table, pas dans l’index. C’est dommage pour la requête précédente, qui affiche juste le champ de la colonne indexée : ce qui est trouvé dans l’index suffit à répondre à la requête (il n’y a que le champ qui sert au filtrage). Il y a donc potentiellement des allers-retours inutiles vers la table.

Or, PostgreSQL maintient une visibility map des blocs totalement visibles, où le contrôle de visibilité est superflu. Un nœud spécifique, Index Only Scan, sait en tirer parti.

Voici un exemple sous PostgreSQL 9.1 (sorti en 2010), qui n’avait pas encore d’optimisation sur ce point. Un index est créé sur deux colonnes de la table, et la requête ne porte que sur ces deux colonnes :

DROP TABLE IF EXISTS demo_i_o_scan ;
-- Table d'un million de lignes
CREATE TABLE demo_i_o_scan (a int, b text, c text, d text) ;
INSERT INTO demo_i_o_scan
SELECT random()*10000000, i, i, i
FROM generate_series(1,10000000) i ;
-- Index sur deux champs
CREATE INDEX demo_idx ON demo_i_o_scan (a,b);
VACUUM ANALYZE demo_i_o_scan ;
-- Sélection sur un de ces champs, affichage du deuxième
EXPLAIN (ANALYZE,BUFFERS) SELECT b,a FROM demo_i_o_scan
WHERE a BETWEEN 10000 AND 100000 ;

                               QUERY PLAN
--------------------------------------------------------------------------------
 Bitmap Heap Scan on demo_i_o_scan  (cost=1205.00..56486.01 rows=85401 width=11) (actual time=10.058..436.445 rows=90118 loops=1)
   Recheck Cond: ((a >= 10000) AND (a <= 100000))
   Buffers: shared hit=2 read=52307 written=3964
   ->  Bitmap Index Scan on demo_idx  (cost=0.00..1183.65 rows=85401 width=0) (actual time=8.688..8.688 rows=90118 loops=1)
         Index Cond: ((a >= 10000) AND (a <= 100000))
         Buffers: shared hit=2 read=346 written=318
 Total runtime: 438.209 ms

Si l’on reproduit la même requête en 9.2 :

DROP TABLE IF EXISTS demo_i_o_scan ;
-- Table d'un million de lignes
CREATE TABLE demo_i_o_scan (a int, b text, c text, d text) ;
INSERT INTO demo_i_o_scan
SELECT random()*10000000, i, i, i
FROM generate_series(1,10000000) i ;
-- Index sur deux champs
CREATE INDEX demo_idx ON demo_i_o_scan (a,b);
VACUUM ANALYZE demo_i_o_scan ;
-- Sélection sur un de ces champs, affichage du deuxième
EXPLAIN (ANALYZE,BUFFERS) SELECT b,a FROM demo_i_o_scan
WHERE a BETWEEN 10000 AND 100000 ;

                               QUERY PLAN
--------------------------------------------------------------------------------
 Index Only Scan using demo_idx on demo_i_o_scan  (cost=0.00..2121.46 rows=88891 width=11) (actual time=0.013..8.847 rows=90167 loops=1)
   Index Cond: ((a >= 10000) AND (a <= 100000))
   Heap Fetches: 0
   Buffers: shared hit=17591 read=346 written=264
 Total runtime: 10.754 ms

On a donc un facteur 40 d’accélération (ici sur une machine moderne avec SSD, mais c’est au moins aussi intéressant sur des disques magnétiques avec une latence bien supérieure). La réduction du nombre de blocs lus (44 108 contre 347) explique en bonne partie le gain en temps. En effet, seul l’index est lu à présent. PostgreSQL 17 ne fait pas mieux.

Passer le enable_indexonlyscan à off désactive le nœud Index Only Scan, et revient au comportement de la 9.1.

Index Only Scan : performances

Extrêmement performant
- requêtes avec peu de colonnes
Conditions
- VACUUM fréquent
- …sinon Heap Fetches

Les nœuds Index Only Scan sont donc très intéressants pour toutes les requêtes avec peu de colonnes qui pourraient tenir dans un index.

Des index dits « couvrants », contenant d’abord les colonnes de filtrage, puis celles à retourner, peuvent être créés à destination de requêtes critiques afin de favoriser l’Index Only Scan.

Par contre, l’Index Only Scan est très sensible au nombre de lignes « mortes ». Si l’on modifie 10 % de la table et que l’on relance la requête avant qu’un autovacuum ait le temps de passer, le temps d’exécution devient bien moins bon :

UPDATE demo_i_o_scan SET c = 42 WHERE a > 900000;
EXPLAIN (ANALYZE,BUFFERS) SELECT b,a FROM demo_i_o_scan
WHERE a BETWEEN 10000 AND 100000 ;

                               QUERY PLAN
--------------------------------------------------------------------------------
 Index Only Scan using demo_idx on demo_i_o_scan  (cost=0.44..180640.78 rows=159025 width=11) (actual time=0.022..580.623 rows=89710 loops=1)
   Index Cond: ((a >= 10000) AND (a <= 100000))
   Heap Fetches: 89710
   Buffers: shared hit=70014 read=72409 dirtied=51877 written=60718
   I/O Timings: shared read=101.754 write=141.870
 Planning:
   Buffers: shared hit=6 read=4 dirtied=1 written=4
   I/O Timings: shared read=0.010 write=0.017
 Planning Time: 0.116 ms
 Execution Time: 583.106 ms

La version graphique montre bien la présence de 89 710 heap fetches, c’est-à-dire de contrôles de visibility de la ligne dans la table. Cela concerne la moitié des lignes récupérées.

Certes, les lignes retournées ne sont pas celles modifiées. Mais elles sont mélangées (la corrélation entre a et l’emplacement physique est ici nulle) et de nombreux blocs contiennent les unes et les autres, et ne sont donc pas intégralement visibles, d’où les rechecks.

Si une requête critique dépend d’un Index Only Scan, il faut s’assurer que l’autovacuum passe très souvent, et/ou planifier des VACUUM très fréquents sur la table.

Références :

Parcours d’index seul et index couvrants dans la documentation officielle
Article du blog A Hascker’s Diary (Satoshi Nagayasu, 2011)

Autres parcours

TID Scan
Function Scan
Values
Result

Il existe d’autres parcours, bien moins fréquents ceci dit.

TID Scan :

TID est l’acronyme de tuple ID. C’est en quelque sorte un pointeur vers une ligne (ou ctid). Ce type de parcours est exceptionnel en applicatif (et généralement une très mauvaise idée puisqu’il généralement utilisé en interne par PostgreSQL.

EXPLAIN SELECT * FROM pg_class WHERE ctid = '(1,1)';

                        QUERY PLAN
----------------------------------------------------------
 Tid Scan on pg_class  (cost=0.00..4.01 rows=1 width=674)
   TID Cond: (ctid = '(1,1)'::tid)

Il est possible de le désactiver via le paramètre enable_tidscan.

Function Scan :

Un Function Scan est utilisé par les fonctions renvoyant des ensembles de lignes (appelées SRF pour Set Returning Functions). Vous pouvez écrire les vôtres mais PostgreSQL en fournit de nombreuses, par exemple generate_series() :

EXPLAIN (ANALYZE,VERBOSE,BUFFERS)
SELECT * FROM generate_series(1, 1_000_000) ;

                               QUERY PLAN
------------------------------------------------------------------------
 Function Scan on pg_catalog.generate_series  (cost=0.00..10000.00 rows=1000000 width=4) (actual time=61.888..103.660 rows=1000000 loops=1)
   Output: generate_series
   Function Call: generate_series(1, 1000000)
   Buffers: temp read=1709 written=1709
   I/O Timings: temp read=1.972 write=6.779
 Query Identifier: -3923767323822397746
 Planning Time: 0.051 ms
 Execution Time: 125.887 ms

Noter que la génération de la fonction a donné lieu à l’utilisation d’un fichier temporaire. Pour l’éviter, il faut monter work_mem assez haut.

Values :

VALUES est une clause de l’instruction INSERT, mais VALUES peut aussi être utilisé comme une table dont on spécifie les valeurs. Par exemple :

VALUES (1), (2);

 column1
---------
       1
       2

Un alias permet de nommer les champs :

SELECT * FROM (VALUES ('a', 1), ('b', 2), ('c', 3)) AS tmp(c1, c2);

 c1 | c2
----+----
 a  |  1
 b  |  2
 c  |  3

Le planificateur utilise un nœud spécial appelé Values Scan pour indiquer un parcours sur cette clause :

EXPLAIN SELECT *
FROM (VALUES ('a', 1), ('b', 2), ('c', 3))  AS tmp(c1, c2) ;

                          QUERY PLAN
--------------------------------------------------------------
 Values Scan on "*VALUES*"  (cost=0.00..0.04 rows=3 width=36)

Result :

Enfin, le nœud Result n’est pas à proprement parler un nœud de type parcours. Il y ressemble dans le fait qu’il ne prend aucun ensemble de données en entrée et en renvoie un en sortie. Son but est de renvoyer un ensemble de données suite à un calcul. Par exemple :

EXPLAIN SELECT 1+2 ;

                QUERY PLAN
------------------------------------------
 Result  (cost=0.00..0.01 rows=1 width=4)

Jointures

Prend 2 ensembles de données en entrée
- inner (interne)
- outer (externe)
Et renvoie un seul ensemble de données
Nested Loop, Merge Join, Hash Join

Nested Loops

Nested Loops : principe

« Boucles imbriquées »

Ensemble externe parcouru une fois
Pour chaque ligne :
- chercher les lignes dans la relation interne selon la condition de jointure
  - émettre ces lignes en résultat

Les boucles imbriquées, ou nested loops, sont la manière la plus simple d’opérer une jointure entre deux ensembles issus de parcours de tables, de parcours d’index, ou de n’importe quels autres nœuds.

Un des deux ensembles, souvent le plus gros, est pris comme « relation externe », Il est parcouru une seule fois. Pour chacune de ses lignes, PostgreSQL recherche les lignes correspondantes à la condition de jointure dans l’autre ensemble. Cela peut être rapide (toute petite table, index pertinent…), ou très lent (parcours complet de la table sans index utilisable).

Le paramètre enable_nestloop permet d’activer ou de désactiver ce type de nœud à titre expérimental.

Prenons un exemple avec trois tables, dont une table de commandes, pointant vers des clients et une toute petite table de statuts de commandes. Il n’y a pas d’index, à part ceux automatiquement ajoutés sur les clés primaires des trois tables.

DROP TABLE IF EXISTS commandes ;
DROP TABLE IF EXISTS statuts ;
DROP TABLE IF EXISTS clients ;

CREATE TABLE statuts (  sid int PRIMARY KEY,
                        statut text) ;
INSERT INTO statuts VALUES (0,'à faire'),
                           (1,'en cours'),
                           (2,'archivé');

CREATE TABLE clients  (clid int PRIMARY KEY, nom text) ;
INSERT INTO clients SELECT i, 'Client '||i
                    FROM generate_series (0,100) i ;

CREATE TABLE commandes (cid int PRIMARY KEY,
                        sid int REFERENCES statuts,
                        clid int REFERENCES clients,
                        montant float
                        ) ;
INSERT INTO commandes
SELECT i, mod (i,2), mod (i,99), 3.14*i
FROM   generate_series (1,100000) i ;

VACUUM ANALYZE statuts, clients, commandes ;

Exemple 1 :

Cette première requête sélectionne une partie des commandes, puis opère une jointure pour obtenir le statut :

EXPLAIN (ANALYZE) SELECT cid, montant, statut
FROM  commandes INNER JOIN statuts USING (sid)
WHERE montant > 313000 ;

                               QUERY PLAN                                      
-------------------------------------------------------------------------------
 Nested Loop  (cost=0.00..1900.23 rows=325 width=21) (actual time=7.942..8.113 rows=319 loops=1)
   Join Filter: (statuts.sid = commandes.sid)
   Rows Removed by Join Filter: 159
   ->  Seq Scan on commandes  (cost=0.00..1887.00 rows=325 width=16) (actual time=7.924..7.968 rows=319 loops=1)
         Filter: (montant > '313000'::double precision)
         Rows Removed by Filter: 99681
   ->  Materialize  (cost=0.00..1.04 rows=3 width=13) (actual time=0.000..0.000 rows=1 loops=319)
         ->  Seq Scan on statuts  (cost=0.00..1.03 rows=3 width=13) (actual time=0.007..0.008 rows=2 loops=1)
 Planning Time: 0.390 ms
 Execution Time: 8.158 ms

La vision graphique est la suivante :

Le Seq Scan sur commandes parcourt la table une fois et trouve 319 lignes. La jointure Nested Loops prend ce résultat comme ensemble externe et appelle donc 319 fois l’ensemble interne (loops=319), ramenant une ligne en moyenne à chaque fois. L’ensemble interne n’est pas directement la petite table statuts, mais une version en mémoire préalablement obtenue avec un nœud Materialize.

Exemple 2 :

Pour les commandes de client d’identifiant 1, afficher les informations sur les clients :

EXPLAIN (ANALYZE) SELECT *
FROM  commandes INNER JOIN clients USING (clid)
WHERE clid = 1;

                               QUERY PLAN                                      
-------------------------------------------------------------------------------
 Nested Loop  (cost=0.00..1898.59 rows=933 width=29) (actual time=0.028..8.762 rows=1011 loops=1)
   ->  Seq Scan on clients  (cost=0.00..2.26 rows=1 width=13) (actual time=0.018..0.025 rows=1 loops=1)
         Filter: (clid = 1)
         Rows Removed by Filter: 100
   ->  Seq Scan on commandes  (cost=0.00..1887.00 rows=933 width=20) (actual time=0.007..8.564 rows=1011 loops=1)
         Filter: (clid = 1)
         Rows Removed by Filter: 98989
 Planning Time: 0.380 ms
 Execution Time: 8.870 ms

Noter que le filtre clid = 1 porte sur la condition de jointure, donc PostgreSQL peut l’appliquer aux deux Seq Scan. L’ensemble externe porte sur clients, et chaque ligne trouvée est cherchée dans commandes. C’est à première vue un peu étonnant, on s’attendrait à avoir la plus grosse table en table externe. Cependant, PostgreSQL a correctement estimé qu’il ne ramène qu’une ligne de clients, et la table commandes n’est donc parcourue qu’une fois (loops=1). Dans ce cas précis, commencer par l’une ou l’autre table est jugé équivalent par PostgreSQL.

Exemple 3 :

Il est généralement conseillé d’indexer les clés étrangères, on ajoute donc :

CREATE INDEX ON commandes (clid);

La requête suivante récupère les commandes d’un client identifié par son nom :

EXPLAIN (ANALYZE) SELECT *
FROM  commandes INNER JOIN clients USING (clid)
WHERE clients.nom  = 'Client 1' ;

                               QUERY PLAN                                      
-------------------------------------------------------------------------------
 Nested Loop  (cost=12.12..701.01 rows=990 width=29) (actual time=0.344..1.553 rows=1011 loops=1)
   ->  Seq Scan on clients  (cost=0.00..2.26 rows=1 width=13) (actual time=0.014..0.025 rows=1 loops=1)
         Filter: (nom = 'Client 1'::text)
         Rows Removed by Filter: 100
   ->  Bitmap Heap Scan on commandes  (cost=12.12..688.65 rows=1010 width=20) (actual time=0.325..1.365 rows=1011 loops=1)
         Recheck Cond: (clid = clients.clid)
         Heap Blocks: exact=637
         ->  Bitmap Index Scan on commandes_clid_idx  (cost=0.00..11.87 rows=1010 width=0) (actual time=0.145..0.145 rows=1011 loops=1)
               Index Cond: (clid = clients.clid)
 Planning Time: 0.435 ms
 Execution Time: 1.637 ms

La vision graphique est sur explain.dalibo.com. L’ensemble externe provient de clients, après récupération d’une seule ligne. L’ensemble interne est la table commandes. Pour y trouver les lignes avec le clid nécessaire, PostgreSQL utilise un Bitmap Scan sur l’index sur clid, qu’il estime plus efficace que 1011 appels dans le même index.

Nested Loops : performances

Coût proportionnel à la taille des ensembles
Intérêts
- démarrage rapide
- pas besoin de mémoire
- marche toujours
Inadapté à :
- grands nombre de lignes
Index chaudement conseillé

Le coût d’un nœud Nested Loop est proportionnel à la taille des ensembles. Il est donc intéressant pour les petits ensembles, et encore plus lorsque l’ensemble interne dispose d’un index satisfaisant la condition de jointure.

En théorie, il s’agit du type de jointure le plus lent. Mais il a un gros intérêt : il n’est pas nécessaire de trier les données (comme pour un Merge Join) ou de les hacher (comme pour un Hash Join) avant de commencer à traiter les données. Le coût de démarrage est donc très faible. Il est ainsi favorisé pour un petit ensemble externe, ou une clause LIMIT. Dès que le nombre de lignes augmente, PostgreSQL bascule sur d’autres types de nœuds.

Nested Loop est aussi le seul nœud capable de traiter des jointures sur des conditions différentes de l’égalité ainsi que des jointures de type CROSS JOIN.

Merge Join

Merge Join : principe

Jointure d’ensembles triés

Trier l’ensemble interne
Trier l’ensemble externe
Tant qu’il reste des lignes dans un des ensembles
- lire les deux ensembles en parallèle
- si condition de jointure émettre la ligne

L’algorithme est assez simple. Le prérequis est que les deux ensembles de données doivent être triés. Ils sont parcourus ensemble. Lorsque la condition de jointure est vraie, la ligne résultante est envoyée dans l’ensemble de données en sortie.

Voici un exemple basé sur une jointure entre une table des billets et une table des commentaires d’une plate-forme de blog.

DROP TABLE IF EXISTS commentaires ;
DROP TABLE IF EXISTS billets ;
CREATE TABLE billets (bid   bigint PRIMARY KEY,
                      d     timestamptz,
                      t     text) ;
CREATE TABLE commentaires (cid bigint PRIMARY KEY,
                           bid bigint REFERENCES billets,
                           d   timestamptz,
                           t   text) ;
INSERT INTO billets (bid, d, t)
SELECT i,
       '2010-01-01'::date + i*interval '1h',
       lpad('lorem ipsum',4000,'x')
FROM generate_series (1,10_000) i ;
INSERT INTO commentaires (cid, bid, d, t)
SELECT i,
       1+i/3,
       '2010-01-01'::date + (i/3)*interval '1h',
       lpad('lorem ipsum',300,'x')
FROM generate_series (4,30_000-3) i ;
-- Index sur clé étrangère
CREATE INDEX ON commentaires (bid) ;
VACUUM ANALYZE billets,commentaires;

EXPLAIN (ANALYZE)
SELECT *
FROM  billets INNER JOIN commentaires USING (bid)
WHERE billets.d > '2010-06-30'::date
ORDER BY bid ;

                               QUERY PLAN                                      
-------------------------------------------------------------------------------
 Merge Join  (cost=0.62..2600.41 rows=14996 width=397) (actual time=2.115..5.705 rows=14998 loops=1)
   Merge Cond: (billets.bid = commentaires.bid)
   ->  Index Scan using billets_pkey on billets  (cost=0.29..222.78 rows=5000 width=81) (actual time=0.010..0.409 rows=5000 loops=1)
         Index Cond: (bid > 5000)
   ->  Index Scan using commentaires_bid_idx on commentaires  (cost=0.29..2140.18 rows=29992 width=324) (actual time=0.005..3.404 rows=29994 loops=1)
         Filter: (d < '2012-12-31'::date)
 Planning Time: 0.234 ms
 Execution Time: 5.993 ms

Comme la clé primaire et la clé étrangère sont indexées, il n’y a rien à trier, le temps de démarrage est ici très rapide. L’ORDER BY encourage l’usage du Merge Join. (Sans cela, comme la volumétrie reste modeste, PostgreSQL a souvent tendance à préférer un Hash Join.)

Le paramètre enable_mergejoin permet d’ activer ou de désactiver ce type de nœud.

Merge Join : performances

Intérêt
- le plus rapide sur une grosse volumétrie
- pas de besoin de mémoire (si tri déjà fait…)
Limites
- uniquement les égalités
- besoin de données triées (Sort ou index)
Produit un résultat trié

Contrairement au Nested Loop, le Merge Join ne lit qu’une fois chaque ligne. Il n’a pas besoin de mémoire et peut démarrer rapidement une fois les données triées. Sur de gros volumes, il est optimal.

Les données étant triées en entrées, elles reviennent triées. Cela peut avoir son avantage dans certains cas, comme l’économie d’un tri pour un ORDER BY.

Son gros inconvénient est justement que les données en entrée doivent être triées. PostgreSQL peut alors décider de précéder le Merge Join d’un nœud de tri Sort. Or, trier beaucoup de données est coûteux et peut prendre du temps, consommer de la RAM ou du disque. Le coût de démarrage peut devenir alors rédhibitoire pour des requêtes avec un LIMIT par exemple.

L’idéal est que le Merge Join s’appuie sur un index pour accélérer l’opération de tri (on verra alors forcément un Index Scan).

Un autre inconvénient est que le Merge Join ne fonctionne que pour des conditions d’égalité, ce qui représente tout de même l’essentiel des clés de jointures.

Hash Join

Hash Join : principe

Jointure par hachage

Hacher les lignes de l’ensemble interne
Pour chaque ligne de l’ensemble externe
- hacher la ligne lue
- comparer ce hachage aux lignes hachées de l’ensemble interne
- si correspondance : émettre la ligne

À partir d’une certaine volumétrie, les Nested Loops et les Index Scan peuvent devenir trop lents. Le Hash Join cherche à supprimer ce problème en créant une table de hachage de la table interne, à priori la plus petite.

Sa première étape est le hachage de chaque clé de jointure de la table interne, ce qui consomme du CPU, puis le stockage de cette table de hachage, ce qui consomme de la mémoire, voire du disque.

Ensuite, en simplifiant, le nœud Hash Join parcourt la table externe, hache chaque clé de jointure l’une après l’autre et va trouver le ou les enregistrements de la table interne correspondant à la valeur hachée. PostgreSQL vérifie enfin d’éventuels prédicats supplémentaires à vérifier.

Voici un exemple de Hash Join sur des tables système d’une base de données vide de toute donnée utilisateur :

EXPLAIN (ANALYZE,BUFFERS) SELECT *
FROM  pg_class, pg_namespace
WHERE pg_class.relnamespace=pg_namespace.oid ;

                                QUERY PLAN                                
--------------------------------------------------------------------------
 Hash Join  (cost=1.09..21.49 rows=415 width=398) (actual time=0.041..0.405 rows=415 loops=1)
   Hash Cond: (pg_class.relnamespace = pg_namespace.oid)
   Buffers: shared hit=15
   ->  Seq Scan on pg_class  (cost=0.00..18.15 rows=415 width=273) (actual time=0.011..0.066 rows=415 loops=1)
         Buffers: shared hit=14
   ->  Hash  (cost=1.04..1.04 rows=4 width=125) (actual time=0.010..0.011 rows=4 loops=1)
         Buckets: 1024  Batches: 1  Memory Usage: 9kB
         Buffers: shared hit=1
         ->  Seq Scan on pg_namespace  (cost=0.00..1.04 rows=4 width=125) (actual time=0.004..0.005 rows=4 loops=1)
               Buffers: shared hit=1
 Planning:
   Buffers: shared hit=4
 Planning Time: 0.297 ms
 Execution Time: 0.477 ms

Graphiquement, cela donne ceci :

La table pg_namespace (la plus petite des deux) est parcourue et hachée, ce qui occupe 9 ko. Puis la table pg_class est parcourue, et le hachage de chacune de ses lignes est comparé au contenu de la table interne hachée.

Le paramètre enable_hashjoin permet d’ activer ou de désactiver ce type de nœud.

Hash Join : performances

Avantages :
- idéal pour joindre une grande table à une petite
Limites :
- uniquement conditions avec égalité
- coût de démarrage important
- mémoire, volumétrie !
- sensible aux mauvaises estimations
Paramétrage mémoire :
- work_mem × hash_mem_multiplier
Parallélisable

Ce type de nœud est très rapide à condition d’avoir suffisamment de mémoire pour stocker le résultat du hachage de l’ensemble interne. Si une des tables est relativement petite, ce hash tient en mémoire, c’est optimal.

Il y a cependant plusieurs limites.

D’abord, le coût de démarrage peut se révéler important à cause du hachage de la table interne. Ce nœud a des chances de ne pas être utilisé s’il y a une clause LIMIT après la jointure.

Un Hash Join consomme CPU et mémoire pour créer la table de hachage. Au-delà il peut utiliser des fichiers temporaires sur disque, ce qui ralentit la jointure. Le paramétrage de la mémoire utilisable est donc primordial :

work_mem est le premier paramètre qui limite cette mémoire, et le défaut est généralement augmenté ;
hash_mem_multiplier est un facteur multiplicateur de work_mem pour les nœuds utilisant un hachage, par défaut 2 depuis PostgreSQL 15 (1 avant), qui permet de ne pas gonfler work_mem de manière plus générale.

Ces deux paramètres peuvent bien sûr être modifiés dans une session ou une transaction.

Pour réduire la mémoire de hachage, il est conseillé de diminuer le nombre de colonnes récupérées. C’est une raison supplémentaire d’éviter les SELECT * aveugles.

Si la mémoire est insuffisante et qu’il faut utiliser des fichiers temporaires, l’algorithme travaille par groupe de lignes (batch). Cette version améliorée de l’algorithme partitionne la table interne. Pour des détails, voir la page Wikipédia de l’algorithme Grace hash join et celle de la variante qu’utilise PostgreSQL, l’Hybrid hash Join.

Un Hash Join peut être très lent si l’estimation de la taille des ensembles est mauvaise (ensemble interne beaucoup plus gros que prévu, notamment). De plus, avant PostgreSQL 14, un autre bug était lié à ces mauvaises estimations : la mémoire réellement consommée n’était pas limitée, work_mem ne jouant qu’à la planification, ce qui pouvait aller jusqu’à la saturation mémoire.

Le hachage de l’ensemble interne d’un Hash Join peut être parallélisé.

Accessoirement, les données retournées par un Hash Join ne sont pas triées.

Exemple :

Deux classiques tables d’entête et de détails, de 0,9 et 1,5 Go, sont jointes entre elles :

CREATE TABLE entetes ( eid bigint PRIMARY KEY,
                        a bigint,
                        filler char(40) default 'x') ;
CREATE TABLE details (  did bigint PRIMARY KEY,
                        eid bigint REFERENCES entetes,
                        b bigint,
                        filler char(40) default 'y') ;
INSERT INTO entetes
SELECT i, i FROM generate_series (0,10_000_000) i
ORDER BY random() ;
INSERT INTO details SELECT i, i/3, i
FROM generate_series (1,10_000_000 * 3) i
WHERE random() > 0.5 ;

VACUUM ANALYZE entetes, details;

-- Affichage du temps passé hors du cache
SET track_io_timing TO on ;
-- Simplification des plans affichés
SET jit TO off ;              
SET max_parallel_workers_per_gather TO 0 ;

-- Work_mem raisonnable
SET hash_mem_multiplier TO 2 ; -- défaut
SET work_mem TO '100MB';

EXPLAIN (ANALYZE,BUFFERS)
SELECT *
FROM entetes INNER JOIN details USING (eid)
WHERE a > 100 and b IS NOT NULL ;

                               QUERY PLAN
-----------------------------------------------------------------------------
 Hash Join  (cost=471037.90..1304805.07 rows=15003264 width=114) (actual time=1539.278..10372.297 rows=15004553 loops=1)
   Hash Cond: (details.eid = entetes.eid)
   Buffers: shared hit=15956 read=282925 written=8, temp read=229697 written=229697
   I/O Timings: shared read=260.851 write=0.023, temp read=325.657 write=804.411
   ->  Seq Scan on details  (cost=0.00..335291.64 rows=15004764 width=65) (actual time=0.008..1154.374 rows=15004703 loops=1)
         Filter: (b IS NOT NULL)
         Buffers: shared hit=1002 read=184242 written=8
         I/O Timings: shared read=173.003 write=0.023
   ->  Hash  (cost=238637.70..238637.70 rows=9999056 width=57) (actual time=1529.753..1529.754 rows=9999900 loops=1)
         Buckets: 2097152  Batches: 8  Memory Usage: 125027kB
         Buffers: shared hit=14954 read=98683, temp written=82241
         I/O Timings: shared read=87.848, temp write=270.981
         ->  Seq Scan on entetes  (cost=0.00..238637.70 rows=9999056 width=57) (actual time=0.018..583.625 rows=9999900 loops=1)
               Filter: (a > 100)
               Rows Removed by Filter: 101
               Buffers: shared hit=14954 read=98683
               I/O Timings: shared read=87.848
 Planning:
   Buffers: shared hit=98 read=7 dirtied=1
   I/O Timings: shared read=0.019
 Planning Time: 0.202 ms
 Execution Time: 10727.840 ms

Le plan précédent montre un Hash Join, où la table des entêtes, la plus petite, est la table interne. 643 Mo de fichiers temporaires (temp written=82241) sont utilisés. L’algorithme a utilisé 8 batchs consommant chacun 125 Mo de mémoire (ligne Buckets). Cette dernière information donne une idée approximative de la mémoire totale nécessaire (environ 1 Go).

Avec un work_mem × hash_mem_multiplier moitié plus bas, on aurait 16 batchs moitié plus petits.

Si le serveur a assez de mémoire à ce moment, on peut augmenter la mémoire autorisée un peu au-delà de 1 Go. Ce peut être ainsi :

SET work_mem TO '1200MB';
SET hash_mem_multiplier TO 1 ;

ou ainsi :

SET work_mem TO '400MB';
SET hash_mem_multiplier TO 3 ;

La différence peut être importante si le paramétrage n’est pas limité à la session.

Le hash peut alors s’effectuer complètement en RAM et est un peu plus rapide :

                               QUERY PLAN
-------------------------------------------------------------------------------
 Hash Join  (cost=363625.90..738205.96 rows=14999295 width=114) (actual time=2631.882..8422.888 rows=15000582 loops=1)
   Hash Cond: (details.eid = entetes.eid)
   Buffers: shared hit=16054 read=282778
   I/O Timings: shared read=287.729
   ->  Seq Scan on details  (cost=0.00..335202.95 rows=15000795 width=65) (actual time=0.020..1027.317 rows=15000737 loops=1)
         Filter: (b IS NOT NULL)
         Buffers: shared hit=1100 read=184095
         I/O Timings: shared read=172.991
   ->  Hash  (cost=238637.70..238637.70 rows=9999056 width=57) (actual time=2623.124..2623.125 rows=9999900 loops=1)
         Buckets: 16777216  Batches: 1  Memory Usage: 1000204kB
         Buffers: shared hit=14954 read=98683
         I/O Timings: shared read=114.738
         ->  Seq Scan on entetes  (cost=0.00..238637.70 rows=9999056 width=57) (actual time=0.033..682.189 rows=9999900 loops=1)
               Filter: (a > 100)
               Rows Removed by Filter: 101
               Buffers: shared hit=14954 read=98683
               I/O Timings: shared read=114.738
 Planning:
   Buffers: shared hit=8
 Planning Time: 0.119 ms
 Execution Time: 8810.939 ms

Avec moins de champs, la consommation mémoire peut grandement se réduire :

EXPLAIN (ANALYZE,BUFFERS)
SELECT b
FROM entetes INNER JOIN details USING (eid)
WHERE a > 100 and b IS NOT NULL ;

                               QUERY PLAN
-------------------------------------------------------------------------------
…
   ->  Hash  (cost=238637.70..238637.70 rows=9999056 width=8) (actual time=2707.913..2707.915 rows=9999900 loops=1)
         Buckets: 16777216  Batches: 1  Memory Usage: 521694kB
         Buffers: shared hit=15010 read=98627
…

Opérations ensemblistes

Entrée : un ou plusieurs ensembles de données
Sortie : un ensemble de données
Souvent des requêtes sur des tables partitionnées ou héritées
Exemples typiques
- Append et MergeAppend
- Intersect
- Except

Append

Entrée :
- plusieurs ensembles de données
Sortie :
- non triée, non dédupliquée
Utilisation :
- partitionnement, tables héritées
- UNION ALL et des UNION
- NB : UNION sans ALL élimine les doublons (lourd !)
Parallélisable

Un nœud Append a pour but de concaténer plusieurs ensembles de données pour n’en faire qu’un, non trié. Ce type de nœud est utilisé dans les requêtes concaténant explicitement des tables (clause UNION) ou implicitement (requêtes sur une table mère d’un héritage ou une table partitionnée).

Dans une base de données créée avec pgbench -i -s 10 --partitions=10, la table pgbench_accounts est partitionnée (voir au besoin le module V0 - Partitionnement déclaratif (introduction)) Accéder à cette table donne ce plan :

EXPLAIN (COSTS OFF) SELECT * FROM pgbench_accounts;

              QUERY PLAN               
---------------------------------------
 Append
   ->  Seq Scan on pgbench_accounts_1
   ->  Seq Scan on pgbench_accounts_2
   ->  Seq Scan on pgbench_accounts_3
   ->  Seq Scan on pgbench_accounts_4
   ->  Seq Scan on pgbench_accounts_5
   ->  Seq Scan on pgbench_accounts_6
   ->  Seq Scan on pgbench_accounts_7
   ->  Seq Scan on pgbench_accounts_8
   ->  Seq Scan on pgbench_accounts_9
   ->  Seq Scan on pgbench_accounts_10

Les nœuds sont exécutés les uns après les autres, et les résultats renvoyés les uns à la suite des autres, sans tri ni déduplication.

Les nœuds ne sont pas forcément identiques. Dans la requête suivante qui utilise UNION ALL, le planificateur récupère des valeurs de deux tables, dont la deuxième est partitionnée. Pour celle-ci il utilise un autre noeud Append, qui se limite aux deux partitions utiles pour la requête, avec un nœud différent sur chacune :

EXPLAIN (COSTS OFF)
SELECT COUNT(*) FROM pgbench_accounts
WHERE aid BETWEEN 1000001 AND 2000001 ;

                               QUERY PLAN
-------------------------------------------------------------------------------
 Finalize Aggregate
   ->  Gather
         Workers Planned: 2
         ->  Partial Aggregate
               ->  Parallel Append
                     ->  Parallel Index Only Scan using pgbench_accounts_3_pkey on pgbench_accounts_3 pgbench_accounts_2
                           Index Cond: ((aid >= 1000001) AND (aid <= 2000001))
                     ->  Parallel Seq Scan on pgbench_accounts_2 pgbench_accounts_1
                           Filter: ((aid >= 1000001) AND (aid <= 2000001))

UNION ALL récupère toutes les lignes des deux ensembles de données, même en cas de doublon. Pour n’avoir que des lignes distinctes, il est possible d’utiliser UNION sans la clause ALL mais cela entraîne une déduplication des données, ce qui est souvent coûteux :

EXPLAIN (COSTS OFF)
SELECT bid FROM pgbench_branches
UNION
SELECT bid FROM pgbench_accounts WHERE aid < 100000;

                               QUERY PLAN
-------------------------------------------------------------------------------
 HashAggregate
   Group Key: pgbench_branches.bid
   ->  Append
         ->  Seq Scan on pgbench_branches
         ->  Index Scan using pgbench_accounts_1_pkey on pgbench_accounts_1 pgbench_accounts
               Index Cond: (aid < 100000)

L’utilisation involontaire de UNION au lieu de UNION ALL est un problème de performance très fréquent !

Les nœuds enfants d’un nœud Append sont parallélisables.

Paramètres dans le cas des tables partitionnées ou héritées :

Le paramètre enable_partition_pruning permet d’activer l’élagage des partitions. Il peut prendre deux valeurs on (le défaut) ou off.

Avec le partitionnement par héritage (qui n’est plus guère utilisé, voir le chapitre de formation ici), le paramètre constraint_exclusion permet d’éviter de parcourir les tables filles qui ne peuvent pas accueillir les données qui nous intéressent.

MergeAppend

Append avec optimisation du tri
Sortie triée
Utilisation :
- UNION ALL, partitionnement/héritage
- avec parcours triés
- idéal avec LIMIT

Le nœud MergeAppend est une optimisation de Append apparue avec PostgreSQL 9.1, spécifiquement conçue pour le partitionnement. Elle optimise les requêtes effectuant un tri sur un UNION ALL, soit explicite, soit induit par partitionnement ou héritage.

Considérons la requête suivante qui concatène deux champs dans deux tables et trie sur un champ indexé :

CREATE TABLE liste1 (d timestamptz, v float) ;
CREATE TABLE liste2 (d timestamptz, v float) ;

-- Les dates des deux table sont entremêlées
INSERT INTO liste1
SELECT '2020-01-01'::timestamptz + i*interval '6min', random()
FROM generate_series(1,100000) i;
INSERT INTO liste2
SELECT '2020-01-01'::timestamptz + i*interval '10min', random()
FROM generate_series(1,100000) i;

CREATE INDEX ON liste1 (d);
CREATE INDEX ON liste2 (d);

EXPLAIN (COSTS OFF)
SELECT d, v FROM liste1
UNION ALL
SELECT d, v FROM liste2
ORDER BY d ;

                  QUERY PLAN                   
-----------------------------------------------
 Merge Append
   Sort Key: liste1.d
   ->  Index Scan using liste1_d_idx on liste1
   ->  Index Scan using liste2_d_idx on liste2

Il n’y a aucun tri, PostgreSQL déroule les deux index en parallèle bien que les dates soient entremêlées.

Pour voir d’où provient chaque ligne, utiliser le champ système tableoid :

SELECT tableoid::regclass, d, v FROM liste1
UNION ALL
SELECT tableoid::regclass, d, v FROM liste2
ORDER BY d 
LIMIT 5;

 tableoid |           d            |          v          
----------+------------------------+---------------------
 liste1   | 2020-01-01 00:06:00+01 |  0.3217132313176123
 liste2   | 2020-01-01 00:10:00+01 |  0.4255801913539963
 liste1   | 2020-01-01 00:12:00+01 | 0.29396898755013123
 liste1   | 2020-01-01 00:18:00+01 |  0.3339045666755862
 liste2   | 2020-01-01 00:20:00+01 |  0.1439201886655812

MergeAppend est encore plus intéressant avec une clause LIMIT.

Évidemment, sans les index, on aurait un Merge suivi d’un Sort global.

Nœuds ensemblistes

Nœud HashSetOp Except
- EXCEPT et EXCEPT ALL
Nœud HashSetOp Intersect
- INTERSECT et INTERSECT ALL

La clause UNION permet de concaténer deux ensembles de données. À l’inverse, les clauses EXCEPT et INTERSECT permettent de supprimer une partie de deux ensembles de données.

Voici un exemple basé sur EXCEPT, pour trouver les espaces de noms (schémas) non utilisés par des relations :

SELECT oid::regnamespace          FROM pg_namespace
EXCEPT
SELECT relnamespace::regnamespace FROM pg_class ;

                                 QUERY PLAN
-------------------------------------------------------------------------------
 HashSetOp Except  (cost=0.00..30.29 rows=31 width=8)
   ->  Append  (cost=0.00..28.90 rows=556 width=8)
         ->  Subquery Scan on "*SELECT* 1"  (cost=0.00..1.62 rows=31 width=8)
               ->  Seq Scan on pg_namespace  (cost=0.00..1.31 rows=31 width=4)
         ->  Subquery Scan on "*SELECT* 2"  (cost=0.00..24.50 rows=525 width=8)
               ->  Seq Scan on pg_class  (cost=0.00..19.25 rows=525 width=4)

Le résultat peut donner par exemple ceci, suivant l’historique de la base :

       oid        
------------------
 pg_toast_temp_40
 pg_temp_47
 pg_toast_temp_43
 pg_toast_temp_5
 …

Avec INTERSECT, on peut trouver les schémas utilisés dans les deux tables :

SELECT oid::regnamespace          FROM pg_namespace
INTERSECT
SELECT relnamespace::regnamespace FROM pg_class ;

                 QUERY PLAN                 
--------------------------------------------
 HashSetOp Intersect
   ->  Append
         ->  Subquery Scan on "*SELECT* 2"
               ->  Seq Scan on pg_class
         ->  Subquery Scan on "*SELECT* 1"
               ->  Seq Scan on pg_namespace

Et vous obtiendrez au moins ceci :

        oid         
--------------------
 pg_toast
 public
 information_schema
 pg_catalog

Comme pour UNION, préférer les variantes EXCEPT ALL et INTERSECT ALL si des doublons dans le résultat ne sont pas gênants ou s’ils sont logiquement impossibles.

Tris

Entrée :
- un ensemble de données
Renvoie :
- un ensemble trié
Nœuds
- Sort,
- Incremental Sort

Sort

Utilisé pour le ORDER BY
- mais aussi DISTINCT, GROUP BY, UNION
- souvent avant une jointure Merge Join
Gros délai de démarrage
Plusieurs méthodes :
- quicksort (en mémoire)
- top-N heapsort (en mémoire, si LIMIT)
- external merge (sur disque)

Le nœud Sort peut servir aux ORDER BY, mais aussi à d’autres nœuds, parfois en préalable à leur exécution, comme des GROUP BY des DISTINCT, ou des jointures Merge Join…

PostgreSQL peut faire un tri de plusieurs façons. Le choix dépend principalement de work_mem. S’il faut tout trier et qu’il calcule que la quantité de mémoire sera inférieure à ce que le paramètre work_mem indique, alors il trie en mémoire (quicksort). S’il ne faut pas tout trier car il y a un LIMIT, et que la mémoire suffit toujours, top N-heapsort sera utilisé, toujours en mémoire. Si PostgreSQL estime que work_mem est insuffisant, il procède à un tri sur disque (merge disk), ce qui est généralement beaucoup plus lent.

Voici quelques exemples dans une base pgbench de taille 100 :

Tri en mémoire :

EXPLAIN (ANALYZE)
SELECT bid FROM pgbench_branches
ORDER BY bbalance ;

                               QUERY PLAN
-------------------------------------------------------------------------------
 Sort  (cost=5.32..5.57 rows=100 width=8) (actual time=0.024..0.028 rows=100 loops=1)
   Sort Key: bbalance
   Sort Method: quicksort  Memory: 27kB
   ->  Seq Scan on pgbench_branches  (cost=0.00..2.00 rows=100 width=8) (actual time=0.007..0.013 rows=100 loops=1)
 Planning Time: 0.037 ms
 Execution Time: 0.046 ms

Il n’y a ici que 100 petites lignes à trier, 27 ko en RAM ont suffit.

Tri en mémoire avec LIMIT :

On bascule sur un nœud top N heapsort un peu moins consommateur :

EXPLAIN (ANALYZE)
SELECT bid FROM pgbench_branches
ORDER BY bbalance LIMIT 3 ;

                              QUERY PLAN
------------------------------------------------------------------------
 Limit  (cost=3.29..3.30 rows=3 width=8) (actual time=0.047..0.048 rows=3 loops=1)
   ->  Sort  (cost=3.29..3.54 rows=100 width=8) (actual time=0.046..0.047 rows=3 loops=1)
         Sort Key: bbalance
         Sort Method: top-N heapsort  Memory: 25kB
         ->  Seq Scan on pgbench_branches  (cost=0.00..2.00 rows=100 width=8) (actual time=0.006..0.024 rows=100 loops=1)
 Planning Time: 0.040 ms
 Execution Time: 0.065 ms

Tri sur disque :

SET max_parallel_workers_per_gather TO 0;
SET jit TO off ;
SET work_mem TO '4MB' ;
EXPLAIN (ANALYZE) SELECT aid FROM pgbench_accounts ORDER BY abalance ;

                               QUERY PLAN
-------------------------------------------------------------------------------
 Sort  (cost=1586743.21..1611742.82 rows=9999844 width=8) (actual time=3895.278..5098.186 rows=10000000 loops=1)
   Sort Key: abalance
   Sort Method: external merge  Disk: 176160kB
   Buffers: shared hit=417 read=163519, temp read=44038 written=44159
   ->  Seq Scan on pgbench_accounts  (cost=0.00..263933.44 rows=9999844 width=8) (actual time=0.028..1413.596 rows=10000000 loops=1)
         Buffers: shared hit=416 read=163519
 Planning Time: 0.043 ms
 Execution Time: 5810.752 ms

Cette fois, trier 10 millions de lignes n’a pas tenu dans le petit work_mem, PostgreSQL a créé un fichier temporaire de 176 Mo sur le disque.

Noter que le nœud Sort peut se paralléliser (ici sur 5 processus), le gain de temps est appréciable :

SET max_parallel_workers_per_gather TO 4;
EXPLAIN (ANALYZE)
SELECT aid FROM pgbench_accounts ORDER BY abalance ;

                               QUERY PLAN
-------------------------------------------------------------------------------
 Gather Merge  (cost=523960.95..1721288.68 rows=9999844 width=8) (actual time=529.038..1352.855 rows=10000000 loops=1)
   Workers Planned: 4
   Workers Launched: 4
   ->  Sort  (cost=522960.89..529210.80 rows=2499961 width=8) (actual time=480.241..582.130 rows=2000000 loops=5)
         Sort Key: abalance
         Sort Method: external merge  Disk: 40000kB
         Worker 0:  Sort Method: external merge  Disk: 22712kB
         Worker 1:  Sort Method: external merge  Disk: 37856kB
         Worker 2:  Sort Method: external merge  Disk: 38136kB
         Worker 3:  Sort Method: external merge  Disk: 37896kB
         ->  Parallel Seq Scan on pgbench_accounts  (cost=0.00..188934.61 rows=2499961 width=8) (actual time=0.043..158.185 rows=2000000 loops=5)
 Planning Time: 0.148 ms
 Execution Time: 1573.879 ms

Tri sur disque évité grâce à une clause LIMIT :

Un LIMIT 5 à la requête précédente refait basculer vers un top-N heapsort en RAM, car il n’y a pas besoin de beaucoup de RAM pour garder en mémoire les 5 premières pendant que la table est lue :

EXPLAIN (ANALYZE,BUFFERS)
SELECT   aid
FROM     pgbench_accounts
ORDER BY abalance
LIMIT    5 ;

                               QUERY PLAN
-------------------------------------------------------------------------------
 Limit  (cost=430027.25..430027.27 rows=5 width=8) (actual time=2121.489..2121.491 rows=5 loops=1)
   Buffers: shared hit=800 read=163135
   ->  Sort  (cost=430027.25..455026.86 rows=9999844 width=8) (actual time=2121.488..2121.489 rows=5 loops=1)
         Sort Key: abalance
         Sort Method: top-N heapsort  Memory: 25kB
         Buffers: shared hit=800 read=163135
         ->  Seq Scan on pgbench_accounts  (cost=0.00..263933.44 rows=9999844 width=8) (actual time=0.027..1103.317 rows=10000000 loops=1)
               Buffers: shared hit=800 read=163135
 Planning Time: 0.038 ms
 Execution Time: 2121.512 ms

Par contre, une valeur excessive de LIMIT, ou une clause OFFSET élevée fera rebasculer le plan vers un tri sur disque.

Tri par index :

Le tri le plus rapide est celui qu’on ne fait pas. Si un index existe sur les champs concernés (dans le bon ordre), le travail est déjà fait, et PostgreSQL sait utiliser cet index. Au lieu du Sort, apparaît alors un Index Scan, (voire un Index Only Scan dans le cas les plus favorable) :

EXPLAIN (ANALYZE)
SELECT * FROM pgbench_accounts
ORDER BY aid ;

                               QUERY PLAN
-------------------------------------------------------------------------------
 Index Scan using pgbench_accounts_pkey on pgbench_accounts  (cost=0.43..423624.09 rows=9999844 width=97) (actual time=0.022..1746.740 rows=10000000 loops=1)
 Planning Time: 65.105 ms
 Execution Time: 1982.572 ms

Si une requête doit renvoyer de nombreuses lignes triées, peut-être vaut-il la peine de rajouter un index pour accélérer ce tri.

Paramètres :

À titre expérimental, le paramètre enable_sort sert à décourager fortement l’utilisation d’un tri. Dans ce cas, le planificateur tend encore plus à utiliser un index, qui retourne les données déjà triées, même si cela implique de passer par un nœud moins optimal par ailleurs.

Augmenter la valeur du paramètre work_mem aura l’effet inverse : favoriser un tri plutôt que l’utilisation d’un index.

Incremental Sort

Pour tri multicolonnes,
- déjà partiellement triées
Idéal quand un index existe sur les premières colonnes du tri
- ORDER BY, GROUP BY, UNION
- DISTINCT (v16)
- jointures de type Merge Join
Délai de démarrage réduit
Moins de mémoire
PostgreSQL 16

Lorsqu’un tri est réalisé sur plusieurs champs, et que la ou les premiers champs sont déjà triées (par un index ou un autre nœud), PostgreSQL évite de faire un tri complet et ne trie que les derniers, ce qui peut notablement accélérer et réduire la consommation mémoire.

CREATE TABLE demo_is (i int PRIMARY KEY,
                      j int,
                      k int,
                      filler char(40) default ' ');
INSERT INTO demo_is (i,j,k) SELECT i, random()*10000, mod(i,3)
FROM generate_series(1,100000) i;
CREATE INDEX ON demo_is (j);
CREATE INDEX ON demo_is (k);
VACUUM ANALYZE demo_is ;

Ce tri utilise l’index existant sur j pour un Incremental Sort, avec une consommation mémoire maximale de 27 ko :

EXPLAIN (ANALYZE)
SELECT *
FROM demo_is
ORDER BY j,k ;

                               QUERY PLAN
----------------------------------------------------------------------
 Incremental Sort  (cost=1.09..9206.46 rows=100000 width=53) (actual time=0.108..46.284 rows=100000 loops=1)
   Sort Key: j, k
   Presorted Key: j
   Full-sort Groups: 2704  Sort Method: quicksort  Average Memory: 27kB  Peak Memory: 27kB
   ->  Index Scan using demo_is_j_idx on demo_is  (cost=0.29..6084.28 rows=100000 width=53) (actual time=0.046..30.360 rows=100000 loops=1)
 Planning Time: 0.208 ms
 Execution Time: 48.692 ms

Si l’on inverse les champs à trier, PostgreSQL repère que k possède très peu de valeurs différentes et est dispersé dans la table, et donc que trier sur j sera lourd. Il revient alors au classique Sort sur toute la table.

EXPLAIN (ANALYZE) SELECT * FROM demo_is ORDER BY k,j ;

                               QUERY PLAN
----------------------------------------------------------------------
 Sort  (cost=13755.32..14005.32 rows=100000 width=53) (actual time=43.834..50.645 rows=100000 loops=1)
   Sort Key: k, j
   Sort Method: external merge  Disk: 6176kB
   ->  Seq Scan on demo_is  (cost=0.00..2031.00 rows=100000 width=53) (actual time=0.003..5.306 rows=100000 loops=1)
 Planning Time: 0.173 ms
 Execution Time: 53.170 ms

Le tri se fait sur disque, monter work_mem pourrait se révéler utile.

PostgreSQL ne sait malheureusement pas repérer qu’un tri supplémentaire est inutile quand le premier champ est unique (ici la clé primaire) :

EXPLAIN SELECT * FROM demo_is ORDER BY i,j ;

                              QUERY PLAN                              
----------------------------------------------------------------------
 Incremental Sort  (cost=0.34..8138.29 rows=100000 width=53)
   Sort Key: i, j
   Presorted Key: i
   ->  Index Scan using demo_is_pkey on demo_is  (cost=0.29..3638.29 rows=100000 width=53)

Le DISTINCT utilise parfois un tri pour dédupliquer, et il peut profiter de l’Incremental Sort depuis PostgreSQL 16 :

EXPLAIN SELECT DISTINCT j,i  FROM demo_is ORDER BY j,i;

                              QUERY PLAN                              
----------------------------------------------------------------------
 Unique  (cost=1.08..9703.76 rows=100000 width=8)
   ->  Incremental Sort  (cost=1.08..9203.76 rows=100000 width=8)
         Sort Key: j, i
         Presorted Key: j
         ->  Index Scan using demo_is_j_idx on demo_is  (cost=0.29..6084.10 rows=100000 width=8)

Passer le paramètre enable_incremental_sort à off permet de décourager fortement le tri incrémental, auquel cas il sera sans doute remplacé par un tri classique.

Agrégats

Entrée :
- un ensemble de données
Renvoie :
- un ensemble trié
Nœuds
- Aggregate
- HashAggregate
- GroupAggregate

Aggregate

Pour un seul résultat
- SELECT max(…), count(*), sum(…)…
- plusieurs agrégats au besoin
Penser aux index pour accélérer
- count(*)
- max/min

Il existe plusieurs façons de réaliser un agrégat :

l’agrégat standard ;
l’agrégat par tri des données ;
et l’agrégat par hachage.

Les deux derniers sont utilisés quand la clause SELECT contient des colonnes en plus de la fonction d’agrégat.

Les exemples suivants utilisent une base pgbench.

Pour un seul résultat COUNT(*), nous aurons ce plan d’exécution :

EXPLAIN SELECT count(*) FROM pgbench_branches ;

                               QUERY PLAN                               
------------------------------------------------------------------------
 Aggregate  (cost=2.25..2.26 rows=1 width=8)
   ->  Seq Scan on pgbench_branches  (cost=0.00..2.00 rows=100 width=0)

La table est toute petite, donc PostgreSQL a considéré que le plus simple était de la parcourir entièrement.

Souvent le nœud Aggregate se reposera sur l’index de la clé primaire, généralement beaucoup plus petit, et il peut même utiliser un Index Only Scan dans le cas d’un simple count(*).

SET max_parallel_workers_per_gather TO 0 ;
SET jit TO off ;

EXPLAIN SELECT count(*) FROM pgbench_accounts ;

                               QUERY PLAN                               
------------------------------------------------------------------------
 Aggregate  (cost=28480.42..28480.43 rows=1 width=8)
   ->  Index Only Scan using pgbench_accounts_pkey on pgbench_accounts  (cost=0.42..25980.42 rows=1000000 width=0)

L’Aggregate se parallélise, ici toujours pour parcourir un index :

RESET max_parallel_workers_per_gather ;

EXPLAIN (COSTS OFF)
SELECT count(*) FROM pgbench_accounts ;

                               QUERY PLAN                               
------------------------------------------------------------------------
 Finalize Aggregate
   ->  Gather
         Workers Planned: 2
         ->  Partial Aggregate
               ->  Parallel Index Only Scan using pgbench_accounts_pkey on pgbench_accounts

Pour une somme, l’utilisation d’un index est en principe possible de la même manière, mais on indexe plus rarement des indicateurs qui servent aux sommes, et un Seq Scan ou Parallel Seq Scan sera plus fréquent :

EXPLAIN (COSTS OFF)
SELECT sum(abalance) FROM pgbench_accounts ;

                       QUERY PLAN                        
---------------------------------------------------------
 Finalize Aggregate
   ->  Gather
         Workers Planned: 2
         ->  Partial Aggregate
               ->  Parallel Seq Scan on pgbench_accounts

Il faut savoir que plusieurs agrégats peuvent être calculés dans un seul nœud Aggregate :

EXPLAIN (COSTS OFF)
SELECT sum(abalance), max(abalance), min(abalance)
FROM pgbench_accounts ;

                       QUERY PLAN                        
---------------------------------------------------------
 Finalize Aggregate
   ->  Gather
         Workers Planned: 2
         ->  Partial Aggregate
               ->  Parallel Seq Scan on pgbench_accounts

Pour les max et les min, il est également possible de passer par un index existant. Comme il est trié, il suffit d’aller chercher ses valeurs extrêmes, ce qui est très rapide. Si, là encore, un indicateur est rarement indexé, c’est assez fréquent pour des dates d’événements.

Le plan suivant récupère les deux extrémités de la clé primaire par son index :

EXPLAIN (ANALYZE,COSTS OFF,BUFFERS)
SELECT min(aid), max(aid)
FROM pgbench_accounts ;

                              QUERY PLAN
----------------------------------------------------------------------
 Result (actual time=0.101..0.104 rows=1 loops=1)
   Buffers: shared hit=8
   InitPlan 1
     ->  Limit (actual time=0.074..0.076 rows=1 loops=1)
           Buffers: shared hit=4
           ->  Index Only Scan using pgbench_accounts_pkey on pgbench_accounts (actual time=0.071..0.072 rows=1 loops=1)
                 Heap Fetches: 0
                 Buffers: shared hit=4
   InitPlan 2
     ->  Limit (actual time=0.017..0.017 rows=1 loops=1)
           Buffers: shared hit=4
           ->  Index Only Scan Backward using pgbench_accounts_pkey on pgbench_accounts pgbench_accounts_1 (actual time=0.016..0.016 rows=1 loops=1)
                 Heap Fetches: 0
                 Buffers: shared hit=4
 Planning Time: 0.303 ms
 Execution Time: 0.161 ms

Enfin, un décompte de valeurs distinctes est notoirement beaucoup plus lourd. Il implique souvent un tri :

EXPLAIN (ANALYZE,COSTS OFF,BUFFERS)
SELECT count(DISTINCT bid) FROM pgbench_accounts ;

                                        QUERY PLAN                                         
-------------------------------------------------------------------------------------------
 Aggregate (actual time=191.564..191.565 rows=1 loops=1)
   Buffers: shared hit=2566 read=13828, temp read=1471 written=1476
   ->  Sort (actual time=117.658..160.773 rows=1000000 loops=1)
         Sort Key: bid
         Sort Method: external merge  Disk: 11768kB
         Buffers: shared hit=2566 read=13828, temp read=1471 written=1476
         ->  Seq Scan on pgbench_accounts (actual time=0.062..65.713 rows=1000000 loops=1)
               Buffers: shared hit=2566 read=13828
 Planning:
   Buffers: shared hit=3
 Planning Time: 0.106 ms
 Execution Time: 192.717 ms

Là encore, un index peut accélérer le plan, car il contient toutes les valeurs triées, il suffit de parcourir l’index intégralement et de compter :

EXPLAIN (ANALYZE)
SELECT count(DISTINCT bid) FROM pgbench_accounts ;

 Aggregate  (cost=20900.42..20900.43 rows=1 width=8) (actual time=64.464..64.465 rows=1 loops=1)
   ->  Index Only Scan using pgbench_accounts_bid_idx on pgbench_accounts  (cost=0.42..18400.42 rows=1000000 width=4) (actual time=0.011..37.865 rows=1000000 loops=1)
         Heap Fetches: 0
 Planning Time: 0.050 ms
 Execution Time: 64.487 ms

HashAggregate

Hachage de chaque n-uplet de regroupement
Accès direct à chaque n-uplet pour appliquer la fonction d’agrégat
Typiquement : GROUP BY
Mémoire :
- work_mem×hash_mem_multiplier

Le HashAggregate apparaît quand le regroupement se fait avec d’autres champs, donc en premier lieu avec un GROUP BY :

SET max_parallel_workers_per_gather TO 0 ;
SET jit TO off;

EXPLAIN (ANALYZE)                                         
SELECT bid, sum(abalance)
FROM pgbench_accounts
GROUP BY bid ;

                              QUERY PLAN
----------------------------------------------------------------------
 HashAggregate  (cost=31394.00..31394.10 rows=10 width=12) (actual time=129.595..129.597 rows=10 loops=1)
   Group Key: bid
   Batches: 1  Memory Usage: 24kB
   ->  Seq Scan on pgbench_accounts  (cost=0.00..26394.00 rows=1000000 width=8) (actual time=0.045..50.752 rows=1000000 loops=1)
 Planning Time: 0.089 ms
 Execution Time: 129.635 ms

Le hachage occupe de la place en mémoire. Le plan n’est choisi que si PostgreSQL estime que si la table de hachage générée tient dans la mémoire autorisée, c’est-à-dire work_mem×hash_mem_multiplier, comme pour les Hash Join (voir cette partie plus haut pour ce paramètres). En cas de souci d’estimation, au pire, PostgreSQL écrit sur disque.

Par exemple, une erreur d’estimation a lieu à cause d’un regroupement sur un champ calculé, notoirement impossible à estimer :

EXPLAIN (ANALYZE,BUFFERS)
SELECT aid/100, sum(abalance) FROM pgbench_accounts
GROUP BY aid/100 ;

                              QUERY PLAN
----------------------------------------------------------------------
 HashAggregate  (cost=85144.00..105456.50 rows=1000000 width=12) (actual time=130.830..132.095 rows=10001 loops=1)
   Group Key: (aid / 100)
   Planned Partitions: 16  Batches: 1  Memory Usage: 3857kB
   Buffers: shared hit=13716 read=2678
   I/O Timings: shared read=2.706
   ->  Seq Scan on pgbench_accounts  (cost=0.00..28894.00 rows=1000000 width=8) (actual time=0.065..58.410 rows=1000000 loops=1)
         Buffers: shared hit=13716 read=2678
         I/O Timings: shared read=2.706
 Planning Time: 0.095 ms
 Execution Time: 133.805 ms

Ici, elle est dans le bon sens (moins de lignes que prévu). Si l’on veut améliorer ces statistiques, et que le critère de regroupement est assez simple (plus exactement une fonction immutable) il y a deux moyens :

créer un index sur sa valeur, qui ne sera vraiment utile que pour ses statistiques :

CREATE INDEX ON pgbench_accounts ((aid/100)); 
ANALYZE pgbench_accounts ;

ou créer un objet statistique, qui par expérience est moins précis :

CREATE STATISTICS pgbench_accounts_aid_sur_100 ON (aid/100) FROM pgbench_accounts ;
ANALYZE pgbench_accounts ;

On retrouve alors une bonne estimation (ici avec l’index), qui ne change cependant pas le plan :

EXPLAIN                                       
SELECT aid/100, sum(abalance)
FROM pgbench_accounts
GROUP BY aid/100 ;

                                   QUERY PLAN                                   
--------------------------------------------------------------------------------
 HashAggregate  (cost=33894.00..34019.05 rows=10004 width=12)
   Group Key: (aid / 100)
   ->  Seq Scan on pgbench_accounts  (cost=0.00..28894.00 rows=1000000 width=8)

Le HashAggregate peut se retrouver aussi avec des clauses de regroupement avancé comme les GROUPING SETS :

EXPLAIN (COSTS OFF)
SELECT piece,region,sum(quantite)
FROM   stock
GROUP BY GROUPING SETS (piece,region);

       QUERY PLAN
-------------------------
 HashAggregate
   Hash Key: piece
   Hash Key: region
   ->  Seq Scan on stock

Le paramètre enable_hashagg permet d’activer et de désactiver l’utilisation des HashAggregate.

GroupAggregate

Pré-requis :
- données déjà triées : Sort ou index
Parcours des données
- regroupement du groupe précédent arrivé à une donnée différente
GROUPING SETS, ROLLUP, CUBE…

Un GroupAggregate a besoin en entrée de données triées selon le regroupement demandé.

Son principe est de faire le regroupement par partie, une fois terminé le balayage.

Avec cette table d’exemple :

CREATE TABLE stats (id          serial PRIMARY KEY,
                    annee       int NOT NULL,
                    dateachat   date NOT NULL,
                    codeproduit char(4) NOT NULL,
                    typeclient  int,
                    typeproduit int,
                    qte         int
                    ) ;
INSERT INTO stats (annee, dateachat, codeproduit,
                typeclient, typeproduit, qte)
SELECT 2000+a,
       '2000-01-01'::date+a*interval'1 year'+d*interval '1 day',
       c, p, p+c, p*c*a/10000+j+d
FROM
      generate_series(14,24) a,
      generate_series(3000,9000,1000) c,
      generate_series(1,365,5) d,
      generate_series (1,200) j,
      generate_series (3,8) p
WHERE a-p > 16 ;
VACUUM ANALYZE stats;

La requête suivante utilise un GROUP BY sur deux champs :

SET max_parallel_workers_per_gather TO 0 ;
SET jit TO off ;

EXPLAIN
SELECT  annee, typeclient,
        count (*), count(distinct dateachat), min (dateachat), max(dateachat), sum(qte)
FROM    stats
WHERE   annee >2022
GROUP BY annee, typeclient ;

                              QUERY PLAN
----------------------------------------------------------------------
 GroupAggregate  (cost=137581.65..156029.00 rows=25 width=40)
   Group Key: annee, typeclient
   ->  Sort  (cost=137581.65..139887.54 rows=922355 width=16)
         Sort Key: annee, typeclient, dateachat
         ->  Seq Scan on stats  (cost=0.00..30435.50 rows=922355 width=16)
               Filter: (annee > 2022)

Le tri est bien sûr une opération lourde. En fait il est nécessaire au count(distinct), on le voit d’ailleurs dans Sort Key. Sans ce count distinct, le jeu de données est assez petit pour qu’un HashAggregate en mémoire suffise.

Un nouvel index permet au GroupAggregate d’éviter le tri :

CREATE INDEX stats2 ON stats (annee, typeclient, dateachat) ;

SELECT  annee, typeclient,
        count (*), count(distinct dateachat), min (dateachat), max(dateachat), sum(qte)
FROM    stats
WHERE   annee >2022
GROUP BY annee, typeclient ;

                              QUERY PLAN
----------------------------------------------------------------------
 GroupAggregate  (cost=0.43..79149.94 rows=25 width=40) (actual time=30.400..204.004 rows=9 loops=1)
   Group Key: annee, typeclient
   Buffers: shared hit=218359 read=806 written=17
   I/O Timings: shared read=1.288 write=0.354
   ->  Index Scan using stats2 on stats  (cost=0.43..63008.47 rows=922355 width=16) (actual time=0.063..125.070 rows=919800 loops=1)
         Index Cond: (annee > 2022)
         Buffers: shared hit=218359 read=806 written=17
         I/O Timings: shared read=1.288 write=0.354
 Planning:
   Buffers: shared hit=3
 Planning Time: 0.216 ms
 Execution Time: 204.052 ms

MixedAggregate

Pour plusieurs niveaux d’agrégation
Utilise des tables de hachage
Typiquement : ROLLUP, CUBE

Un MixedAggregate se rencontre quand il y a plusieurs niveau d’agrégation, par exemple quand on utilise des fonctionnalités OLAP comme ROLLUP ou CUBE (voir au besoin le module S70 - Analyse de données). Ce nœud utilise des tables de hachage.

Exemple :

EXPLAIN
SELECT  typeclient, typeproduit, sum(qte)
FROM    stats
WHERE   annee = 2021
GROUP BY CUBE (typeclient, typeproduit)  ;

                             QUERY PLAN
---------------------------------------------------------------------
 MixedAggregate  (cost=0.00..34479.66 rows=216 width=16)
   Hash Key: typeclient, typeproduit
   Hash Key: typeclient
   Hash Key: typeproduit
   Group Key: ()
   ->  Seq Scan on stats  (cost=0.00..30435.50 rows=202100 width=12)
         Filter: (annee = 2021)

Autres nœuds

Exemples typiques
- Unique
- Limit
- InitPlan, SubPlan

Unique

Pour DISTINCT
Entrée : données déjà triées
Renvoie : la donnée précédente une fois arrivé à une donnée différente
Résultat trié
Souvent remplacé par un agrégat

Le nœud Unique permet de ne conserver que les lignes différentes d’un résultat. Les données doivent être préalablement triées, et c’est souvent cette opération qui est trop lourde.

Rappelons que l’ajout de clauses DISTINCT inutiles est un souci de performance fréquent.

En voici un exemple, où la table est parcourue puis triée :

EXPLAIN (COSTS OFF)
SELECT DISTINCT bid FROM pgbench_accounts ;

                          QUERY PLAN
---------------------------------------------------------------
 Unique
   ->  Gather Merge
         Workers Planned: 2
         ->  Sort
               Sort Key: bid
               ->  HashAggregate
                     Group Key: bid
                     ->  Parallel Seq Scan on pgbench_accounts

Là aussi, un index aide à accélérer ce type de nœud :

CREATE INDEX ON pgbench_accounts (bid) ;

EXPLAIN (COSTS OFF)
SELECT DISTINCT bid FROM pgbench_accounts ;

                          QUERY PLAN
---------------------------------------------------------------
 Unique
   ->  Gather Merge
         Workers Planned: 2
         ->  Unique
               ->  Parallel Index Only Scan using pgbench_accounts_bid_idx on pgbench_accounts

Pour opérer un DISTINCT, l’optimiseur préfère souvent un agrégat à un nœud Unique :

EXPLAIN (COSTS OFF)
SELECT DISTINCT aid/100 FROM pgbench_accounts ;

                              QUERY PLAN
----------------------------------------------------------------------
 HashAggregate
   Group Key: (aid / 100)
   ->  Index Only Scan using pgbench_accounts_pkey on pgbench_accounts

L’opérateur ne sait pas non plus identifier un champ dont l’unicité est garantie dans la requête. Dans l’exemple suivant, aid est la clé primaire, il n’y a pas de jointure, le nœud Unique est ici :

EXPLAIN (COSTS OFF)
SELECT DISTINCT aid FROM pgbench_accounts ;

                              QUERY PLAN                               
-----------------------------------------------------------------------
 Unique
   ->  Index Only Scan using pgbench_accounts_pkey on pgbench_accounts

Limit

Limite le nombre de résultats renvoyés
LIMIT et OFFSET
Peut modifier complètement le plan
- favorise les nœuds au coût de démarrage réduit (Seq Scan, Nested Loop)

Un nœud Limit arrête l’émission des lignes une fois le seuil demandé. L’ajout de LIMIT modifie profondément le plan, car PostgreSQL cherche alors à obtenir le plus vite possible les premières lignes demandées, et non à optimiser la récupération d’un grand nombre de lignes. PostgreSQL favorise alors les nœuds à faible coût de démarrage comme Seq Scan ou Nested Loops,

OFFSET permet de parcourir un certain nombre de valeurs sans les renvoyer avant de commencer l’affichage. L’utilisation habituelle est la présentation de résultats page par page. Cependant, ces résultats seront quand même lus. Attention, l’utilisation d’une valeur élevée pour OFFSET est une mauvaise pratique.

Ce plan ne contient pas de LIMIT. Comme il y a 10 millions de lignes à lire et à joindre, PostgreSQL décide d’un Hash Join :

EXPLAIN
SELECT * FROM pgbench_accounts
INNER JOIN pgbench_branches USING (bid) ;

                          QUERY PLAN
---------------------------------------------------------------
 Hash Join  (cost=3.25..291298.76 rows=9999844 width=457)
   Hash Cond: (pgbench_accounts.bid = pgbench_branches.bid)
   ->  Seq Scan on pgbench_accounts  (cost=0.00..263933.44 rows=9999844 width=97)
   ->  Hash  (cost=2.00..2.00 rows=100 width=364)
         ->  Seq Scan on pgbench_branches  (cost=0.00..2.00 rows=100 width=364)

L’ajout de LIMIT 5 fait basculer le plan vers un Nested Loop dont le coût de démarrage est nul :

EXPLAIN
SELECT * FROM pgbench_accounts
INNER JOIN pgbench_branches USING (bid)
LIMIT 5 ;

                          QUERY PLAN
---------------------------------------------------------------
 Limit  (cost=0.15..0.41 rows=5 width=457)
   ->  Nested Loop  (cost=0.15..512475.41 rows=9999844 width=457)
         ->  Seq Scan on pgbench_accounts  (cost=0.00..263933.44 rows=9999844 width=97)
         ->  Memoize  (cost=0.15..0.17 rows=1 width=364)
               Cache Key: pgbench_accounts.bid
               Cache Mode: logical
               ->  Index Scan using pgbench_branches_pkey on pgbench_branches  (cost=0.14..0.16 rows=1 width=364)
                     Index Cond: (bid = pgbench_accounts.bid)

Attention, avec LIMIT, la lecture des plan se complique. Dans le plan suivant, les valeurs estimées peuvent porter sur l’intégralité de la table et non sur ce qui doit être réellement récupérées :

EXPLAIN (ANALYZE)
SELECT * FROM pgbench_accounts
INNER JOIN pgbench_branches USING (bid)
LIMIT 5 OFFSET 20 ;

                          QUERY PLAN
---------------------------------------------------------------
 Limit  (cost=1.18..1.43 rows=5 width=457) (actual time=0.046..0.051 rows=5 loops=1)
   ->  Nested Loop  (cost=0.15..512475.41 rows=9999844 width=457) (actual time=0.027..0.047 rows=25 loops=1)
         ->  Seq Scan on pgbench_accounts  (cost=0.00..263933.44 rows=9999844 width=97) (actual time=0.010..0.012 rows=25 loops=1)
         ->  Memoize  (cost=0.15..0.17 rows=1 width=364) (actual time=0.001..0.001 rows=1 loops=25)
               Cache Key: pgbench_accounts.bid
               Cache Mode: logical
               Hits: 24  Misses: 1  Evictions: 0  Overflows: 0  Memory Usage: 1kB
               ->  Index Scan using pgbench_branches_pkey on pgbench_branches  (cost=0.14..0.16 rows=1 width=364) (actual time=0.007..0.007 rows=1 loops=1)
                     Index Cond: (bid = pgbench_accounts.bid)
 Planning Time: 0.240 ms
 Execution Time: 0.084 ms

Le Seq Scan et le Nested Loops affichent 9 999 844 lignes dans leur estimation alors que 25 lignes (20 d’offset et 5 affichées) sont récupérées par l’un et l’autre.

Memoize

Cache de résultat
Utilisable par la table interne des Nested Loop
Utile si :
- peu de valeurs distinctes dans l’ensemble interne
- beaucoup de valeurs dans l’ensemble externe
- peu de correspondance entre les deux ensembles
Paramètres : work_mem×hash_mem_multiplier
Sensible à ndistinct

Apparu avec PostgreSQL 14, le nœud Memoize est un cache de résultat qui permet d’optimiser les performances d’autres nœuds en mémorisant des données qui risquent d’être accédées plusieurs fois de suite. Pour le moment, ce nœud n’est utilisable que pour les données de l’ensemble interne d’un Nested Loop généré par une jointure classique ou LATERAL.

Le cas idéal pour cette optimisation concerne des jointures où de large portions des lignes de l’ensemble interne de la jointure n’ont pas de correspondance dans l’ensemble externe. Dans ce genre de cas, un Hash Join serait moins efficace car il devrait calculer la clé de hachage de valeurs qui ne seront jamais utilisées ; et le Merge Join devrait ignorer un grand nombre de lignes dans son parcours de la table interne.

L’intérêt du cache de résultat augmente lorsqu’il y a peu de valeurs distinctes dans l’ensemble interne et que le nombre de valeurs dans l’ensemble externe est grand, ce qui provoque beaucoup de boucles. Ce nœud est donc très sensible aux statistiques sur le nombre de valeurs distinctes (ndistinct).

Cette fonctionnalité utilise une table de hachage pour stocker les résultats. Cette table est dimensionnée grâce aux paramètres work_mem et hash_mem_multiplier. Si le cache se remplit, les valeurs les plus anciennes sont exclues du cache.

Exemple :

DROP TABLE IF EXISTS t1;
DROP TABLE IF EXISTS t2;
CREATE TABLE t1(i int, j int);
CREATE TABLE t2(k int, l int);
INSERT INTO t1 SELECT x,x FROM generate_series(1, 400000) AS F(x) ;
INSERT INTO t2 SELECT x % 20,x FROM generate_series(1, 3000000) AS F(x);
CREATE INDEX ON t1(j) ;
VACUUM ANALYZE t1,t2 ;

EXPLAIN (TIMING off, COSTS off, SUMMARY off, ANALYZE)
SELECT * FROM t1 INNER JOIN t2 ON (t1.j = t2.k) ;

                                  QUERY PLAN
------------------------------------------------------------------------------
 Nested Loop (actual rows=2850000 loops=1)
   ->  Seq Scan on t2 (actual rows=3000000 loops=1)
   ->  Memoize (actual rows=1 loops=3000000)
         Cache Key: t2.k
         Cache Mode: logical
         Hits: 2999980  Misses: 20  Evictions: 0  Overflows: 0  Memory Usage: 3kB
         ->  Index Scan using t1_j_idx on t1 (actual rows=1 loops=20)
               Index Cond: (j = t2.k)

Il n’y a que 20 valeurs différentes pour t2.k, le cache ne fait donc que 3 ko. Il a permis 2 999 980 accès au cache, et seulement 20 valeurs ont dû être cherchées dans l’index (loops=20). Aucune valeur n’a été exclue du cache (Evictions: 0).

En désactivant ce nœud, on bascule sur un Hash Join:

SET enable_memoize TO off;
EXPLAIN (TIMING off, COSTS off, SUMMARY off, ANALYZE)
SELECT * FROM t1 INNER JOIN t2 ON t1.j = t2.k;

                      QUERY PLAN
-------------------------------------------------------
 Hash Join (actual rows=2850000 loops=1)
   Hash Cond: (t2.k = t1.j)
   ->  Seq Scan on t2 (actual rows=3000000 loops=1)
   ->  Hash (actual rows=400000 loops=1)
         Buckets: 262144  Batches: 4  Memory Usage: 5956kB
         ->  Seq Scan on t1 (actual rows=400000 loops=1)

Conclusion

De nombreux nœuds
Qu’il faut apprendre
Expérimentez !

Questions

EXPLAIN (VERBOSE)
SELECT * FROM questions ;