Un index B-tree multicolonne n'est optimal que si la première colonne fait systématiquement partie des critères de recherche. En effet, les données sont triées dans l'index d'abord selon le premier champ (ici `c1`), puis selon le second (`c2`), etc. Si le critère de recherche ne porte que sur le second champ `c2`, l'index est peut-être en partie utilisable. PostgreSQL 17 et précédents ne peuvent accéder aux valeurs de `c2` directement, mais l'index peut être lu intégralement pour y trouver les diverses valeurs de `c2` qui y sont dispersées. C'est souvent mieux que parcourir toute la table, mais pas optimal. Plus l'index est gros par rapport à la table, plus l'optimiseur aura tendance à se rabattre sur un parcours complet de la table. PostgreSQL 18 connaît les _index skip scans_. Il change l'accès habituel à l'index en autant d'accès qu'il y a de valeurs de `c1`, comme s'il y avait autant d'index différents (« sous-index logiques ») ; puis il va dans chacun chercher les valeurs correspondant au critère sur `c2`. Il n'y a pas de nœud _Skip Scan_ dédié. Le degré de découpage est en pratique géré lors de l'exécution. S'il y a trop de valeurs de `c1` (des milliers), PostgreSQL peut revenir à un parcours intégral de l'index ou de la table. Avec les _skip scan_, l'accès à l'index n'est pas aussi optimal qu'un index commençant par `c2`, mais on peut beaucoup s'en rapprocher. Cette optimisation n'a vraiment d'intérêt que si les valeurs distinctes de `c1` sont assez peu nombreuses (des années, des statuts…). Au contraire, si les valeurs de `c1` sont trop diverses (champ très discriminant), l'intérêt est limité, car en pratique PostgreSQL parcourra tout l'index ou presque. Cette nouvelle fonctionnalité permet donc d'économiser des index. Des requêtes non critiques peuvent se satisfaire d'un index dont elles ne filtrent pas le premier champ. On peut éviter de créer le même index multicolonnes en deux versions dans des ordres différents pour satisfaire à des requêtes différentes : celui commençant par la colonne la moins discriminante sera peut-être suffisant pour toutes les requêtes. De même, on a couramment le dilemme suivant : créer un index pour optimiser un `ORDER BY` ou en créer un autre pour optimiser le critère de sélection ? À présent, l'index pour le tri suffira peut-être à la sélection des lignes. Cette amélioration ne concerne que les index B-tree, qui sont les plus courants. Il arrivait que des index GIN, voire bloom, soient utilisés pour cette [indexation multicolonne](https://dali.bo/j5_html#indexation-multicolonne-gin-gist-bloom), mais ils sont beaucoup plus lourds ou ont des limites. **Exemple** : Cette table contient des ID de commandes, avec un index sur `(annee, num_client)`. Elle est triée pour améliorer la corrélation physique et rendre plus évident les changements d'utilisation des blocs. ```sql DROP TABLE IF EXISTS demo ; CREATE TABLE demo (annee int NOT NULL, num_client varchar (5) NOT NULL, id_commande serial PRIMARY KEY, mois int , z int, filler char(10) default ' '); INSERT INTO demo (annee, num_client, mois) SELECT a, trim(to_char(cl,'00000') ), (cl+commandes)%12 FROM generate_series (2016,2025) a CROSS JOIN generate_series (30000,99999) cl CROSS JOIN generate_series (10,20) commandes ORDER BY a,cl,commandes; CREATE INDEX demo_annee_num_client_idx ON demo (annee, num_client) ; -- Ne pas oublier les statistiques VACUUM (ANALYZE) demo ; ``` La table pèse 442 Mo, l'index sur les deux champs 165 Mo. Ce qui suit suppose des bases PostgreSQL 17 et 18 avec le paramétrage par défaut, à part ceci pour simplifier les plans : ```sql SET jit TO off; SET max_parallel_workers_per_gather TO 0; ``` À cause de l'effet de cache en cas de répétition des requêtes, les plans peuvent différer de vos propres tests. Dans le cas idéal, avec une année et un numéro de client, récupérer une ligne via l'index ne nécessite que 4 blocs : ```sql EXPLAIN (ANALYZE,BUFFERS,SETTINGS) SELECT * FROM demo WHERE num_client = '50000' AND annee = 2024 ; ``` ```output Index Scan using demo_annee_num_client_idx on demo (cost=0.43..27.92 rows=12 width=33) (actual time=0.040..0.045 rows=11.00 loops=1) Index Cond: ((annee = 2024) AND ((num_client)::text = '50000'::text)) Index Searches: 1 Buffers: shared hit=4 Planning Time: 0.124 ms Execution Time: 0.068 ms ``` Dans le cas où nous cherchons les lignes d'un client pour toutes les années, PostgreSQL 17 utilise l'index, mais on constate qu'il le lit intégralement (l'index pèse 9640 blocs selon `pg_class.relpages`). On ne peut malheureusement distinguer ici les blocs lus dans l'index de ceux lus dans la table. ```sql EXPLAIN (ANALYZE,BUFFERS,SETTINGS) SELECT * FROM demo WHERE num_client = '50000' ; ``` ```output Index Scan using demo_annee_num_client_idx on demo (cost=0.43..96520.72 rows=118 width=33) (actual time=1.709..21.606 rows=110 loops=1) Index Cond: ((num_client)::text = '50000'::text) Buffers: shared hit=9603 Settings: search_path = '"$user", public, topology', jit = 'off', max_parallel_workers_per_gather = '0' Planning Time: 0.134 ms Execution Time: 21.641 ms ``` PostgreSQL 18 sait mieux utiliser l'index pour trouver la commande : seuls 47 blocs sont lus : ```output Index Scan using demo_annee_num_client_idx on demo (cost=0.43..257.84 rows=117 width=33) (actual time=0.031..0.108 rows=110.00 loops=1) Index Cond: ((num_client)::text = '50000'::text) Index Searches: 12 Buffers: shared hit=47 Planning Time: 0.068 ms Execution Time: 0.128 ms ``` La ligne `Index Searches` est une amélioration de PostgreSQL 18, qui indique le nombre de recherches indépendantes dans l'index, c'est-à-dire démarrant de la racine, et pouvant potentiellement lire de nombreuses feuilles. Pour l'efficacité, il vaut mieux qu'il y en ait le moins possible. Mais ici, 12 recherches permettent d'éviter de lire tout l'index. Il y a une recherche pour chacune des 10 années. S'il y a deux valeurs à chercher, `Index Searches` trahit ici un accès à chaque année pour chacune : ```sql EXPLAIN (ANALYZE,BUFFERS,SETTINGS,SUMMARY OFF) SELECT * FROM demo WHERE num_client = '30000' OR num_client = '90001' ; ``` ```output Index Scan using demo_annee_num_client_idx on demo (cost=0.43..513.98 rows=234 width=33) (actual time=0.036..0.283 rows=220.00 loops=1) Index Cond: (num_client = ANY ('{30000,90001}'::text[])) Index Searches: 21 Buffers: shared hit=83 ``` Si les valeurs des clients sont très proches, une autre optimisation entre en jeu et le nombre de recherches et de blocs chute : ```output Index Scan using demo_annee_num_client_idx on demo (cost=0.43..513.98 rows=234 width=33) (actual time=0.047..0.302 rows=220.00 loops=1) Index Cond: (num_client = ANY ('{30000,30009}'::text[])) Index Searches: 12 Buffers: shared hit=49 read=4 ``` En effet, PostgreSQL repère la proximité de valeurs et préfère parcourir plus de feuilles finales dans l'index pour éviter les quelques blocs d'une recherche complète de la deuxième valeur. La recherche d'un algorithme qui évite une régression (à quel point parcourt-on trop de feuilles inutiles ?) [a fait partie des travaux de la version 18](https://git.postgresql.org/gitweb/?p=postgresql.git;a=commitdiff;h=8a510275d). Cette requête calcule l'évolution des commandes par années et mois pour un client : ```sql EXPLAIN (ANALYZE,BUFFERS,SETTINGS) SELECT annee, mois, count(*) FROM demo WHERE num_client = '50000' GROUP BY annee, mois ORDER BY annee, mois ; ``` ```output GroupAggregate (cost=26.38..263.20 rows=75 width=16) (actual time=0.097..0.254 rows=110.00 loops=1) Group Key: annee, mois Buffers: shared hit=47 -> Incremental Sort (cost=26.38..261.57 rows=117 width=8) (actual time=0.089..0.196 rows=110.00 loops=1) Sort Key: annee, mois Presorted Key: annee Full-sort Groups: 4 Sort Method: quicksort Average Memory: 25kB Peak Memory: 25kB Buffers: shared hit=47 -> Index Scan using demo_annee_num_client_idx on demo (cost=0.43..257.84 rows=117 width=8) (actual time=0.030..0.137 rows=110.00 loops=1) Index Cond: ((num_client)::text = '50000'::text) Index Searches: 12 Buffers: shared hit=47 Planning: Buffers: shared hit=8 Planning Time: 0.201 ms Execution Time: 0.293 ms ``` La sélection des donnée se fait par l'index `(annee, num_client)` avec 12 recherches. Comme l'index est déjà trié par années, PostgreSQL peut utiliser l'`Incremental Sort`, une optimisation de PostgreSQL 13, pour ne pas tout trier. Un seul index à priori non optimal permet donc à la requête d'être très rapide. Avec PostgreSQL 17, la requête aurait dû parcourir tout l'index et aurait duré 20 ms (60 fois plus longtemps). **Exemple de recherche multicritère** : Une recherche multicritère est notoirement problématique pour un index B-tree quand aucun champ n'est obligatoire. ```sql CREATE TABLE demo_multi (n int, i int, j int, k int, l int, filler char(50) default ' ') ; SELECT * FROM demo_multi WHERE j=1 AND l=17 ; SELECT * FROM demo_multi WHERE k=3 AND l=1 ; SELECT * FROM demo_multi WHERE i=0 AND k=33 ; ``` Il est alors impossible de choisir une première colonne. Un index B-tree portant sur les différents critères est inutilisable par PostgreSQL 17 dans le cas général : ```sql CREATE INDEX demo_multi_idx ON demo_multi USING btree (i,j,k,l) ; ``` L'optimiseur utilise alors souvent un _Seq Scan_. On peut bien sûr définir un index sur chaque combinaison de critères, mais cela peut faire beaucoup d'index. [Cet exemple d'une de nos formations](https://dali.bo/j5_html#indexation-multicolonne-gin-gist-bloom) montre l'intérêt d'index GIN, GiST ou bloom pour une telle recherche multicritère. Avec PostgreSQL 18, le B-tree peut redevenir intéressant dans certains cas favorables : très peu de valeurs différentes sur les premières colonnes de l'index, et peu de colonnes. ```sql SELECT setseed (0.0); -- pour la reproductibilité INSERT INTO demo_multi SELECT n, random(0,2) AS i, random(0,2) AS j, random(0,2) AS k, n AS l FROM generate_series (1,1000000) n ORDER BY i,j,k,l; VACUUM ANALYZE demo_multi ; ``` ```sql EXPLAIN (ANALYZE, COSTS OFF) SELECT * FROM demo_multi WHERE k=0 AND l=200002 ; ``` La dernière colonne est trouvée avec 13 recherches différentes : ```output Index Scan using demo_multi_idx on demo_multi (actual time=0.096..0.116 rows=1.00 loops=1) Index Cond: ((k = 0) AND (l = 200002)) Index Searches: 13 Buffers: shared hit=40 Planning Time: 0.126 ms Execution Time: 0.140 ms ``` Cette recherche fonctionne aussi et donne lieu cette fois à un Bitmap Scan : ```sql EXPLAIN (ANALYZE, COSTS OFF) SELECT * FROM demo_multi WHERE j=0 AND k=0 ; ``` ```output Bitmap Heap Scan on demo_multi (actual time=7.341..20.521 rows=111392.00 loops=1) Recheck Cond: ((j = 0) AND (k = 0)) Heap Blocks: exact=1378 Buffers: shared hit=1677 read=141 -> Bitmap Index Scan on demo_multi_idx (actual time=7.025..7.026 rows=111392.00 loops=1) Index Cond: ((j = 0) AND (k = 0)) Index Searches: 4 Buffers: shared hit=299 read=141 Planning Time: 0.135 ms Execution Time: 26.388 ms ``` Cela reste plus intéressant qu'un _Seq Scan_. Au final, le B-tree redevient une option de plus à tester pour les recherches multicritères, mais tout dépend du nombre de champs, de leur sélectivité, etc.