Table des matières

Rappels statistiques, cardinalité, sélectivité

Le SQL est un language dit “déclaratif”. C’est un language où l’utilisateur demande ce qu’il souhaite. Sans préciser comment l’ordinateur doit procéder pour obtenir les résultats.

C’est le SGBD qui doit trouver “comment” réaliser l’opération en s’assurant de :

Retourner le résultat juste
Idéalement, le plus vite possible

“Le plus vite possible” se traduit par :

Réduire au maximum les accès disques
Privilégier les lectures séquentielles (praticulièrement important pour les disques mécaniques)
Réduire le nombre d’opérations CPU
Réduire l’empreinte mémoire

Pour se faire, un SGBD possède ce que l’on appèle un optimiseur dont le rôle est de trouver le meilleur plan d’exécution.

PostgreSQL possède un optimiseur basé sur un mécanisme de coût. Sans rentrer dans les détails, chaque opération a un cout unitaire (lecture d’un bloc séquentiel, traitement CPU d’un enregistrement…). Le moteur calcule le coût de plusieurs plans d’exécution (si la requête est simple) et choisi le moins couteux.

Comment le moteur peut estimer le coût d’un plan? En estimant le coût de chaque noeud du plan en se basant sur des statistiques. PostgreSQL analyse les tables pour d’obtenir un échantillon statistique (opération normalement réalisée par l’autovacuum).

Quelques mots de vocabulaire :

Cardinalité : Dans la théorie des ensemble, c’est le nombre d’éléments dans un ensemble. Dans les bases de données, ça sera le nombre de lignes d’une table ou après application d’un prédicat.

Sélectivité : Fraction d’enregistrements retournés après application d’un prédicat. Par exemple, une table contenant des personnes et dont environ un tier correspond à des enfants. La sélectivité du prédicat personne = 'enfant' sera de 0.33.

Si cette table contient 300 personnes (c’est la cardinalité de l’ensemble “personnes”), on peut estimer le nombre d’enfants car on sait que le prédicat personne = 'enfant' est de 0.33 :

300 * 0.33 = 99

On peut obtenir ces estimations avec EXPLAIN qui affiche le plan d’exécution.

Exemple (simplifié) :

1explain (analyze, timing off) select * from t1 WHERE c1=1;
2                                  QUERY PLAN
3------------------------------------------------------------------------------
4 Seq Scan on t1  (cost=0.00..5.75 rows=100 ...) (actual rows=100 ...)
5   Filter: (c1 = 1)
6   Rows Removed by Filter: 200

(cost=0.00..5.75 rows=100 …) : Indique le coût estimé et le nombre d’enregistrements estimé (rows).

(actual rows=100 …) : Indique le nombre d’enregistrement réellement obtenu.

La documentation de PostgreSQL fourni des exemples de calculs d’estimation : Row Estimation Examples

Il est assez facile de comprendre comment obtenir des estimations à partir de types de données scalaires.

Comment ça se passe pour des types particuliers? Par exemple le JSON?

Recherche sur du JSONB

Jeu de données

Comme dans les précédents articles, j’ai utilisé le jeu de données de stackoverflow. J’ai créé une nouvelle table en aggrégeant les données de plusieurs tables dans un objet JSON :

 1CREATE TABLE json_stack AS
 2SELECT t.post_id,
 3       row_to_json(t,
 4                   TRUE)::jsonb json
 5FROM
 6  (SELECT posts.id post_id,
 7          posts.owneruserid,
 8          users.id,
 9          title,
10          tags,
11          BODY,
12          displayname,
13          websiteurl,
14          LOCATION,
15          aboutme,
16          age
17   FROM posts
18   JOIN users ON posts.owneruserid = users.id) t;

Le traitement est assez long car les deux tables concernées totalisent près de 40Go.

J’obtiens donc une table de 40Go qui ressemble à ça :

 1 \dt+ json_stack
 2                      List of relations
 3 Schema |    Name    | Type  |  Owner   | Size  | Description
 4--------+------------+-------+----------+-------+-------------
 5 public | json_stack | table | postgres | 40 GB |
 6(1 row)
 7
 8
 9\d json_stack
10             Table "public.json_stack"
11 Column  |  Type   | Collation | Nullable | Default
12---------+---------+-----------+----------+---------
13 post_id | integer |           |          |
14 json    | jsonb   |           |          |
15
16
17select post_id,jsonb_pretty(json) from json_stack
18    where json_displayname(json) = 'anayrat' limit 1;
19 post_id  |
20----------+-----------------------------------------------------------------------------------------
21 26653490 | {
22          |     "id": 4197886,
23          |     "age": null,
24          |     "body": "<p>I have an issue with date filter. I follow [...]
25          |     "tags": "<java><logstash>",
26          |     "title": "Logstash date filter failed parsing",
27          |     "aboutme": "<p>Sysadmin, Postgres DBA</p>\n",
28          |     "post_id": 26653490,
29          |     "location": "Valence",
30          |     "websiteurl": "https://blog.anayrat.info",
31          |     "displayname": "anayrat",
32          |     "owneruserid": 4197886
33          | }

Opérateurs et indexation sur du JSONB

PostgreSQL propose plusieurs opérateurs pour interroger du JSONB ¹. Nous allons utiliser l’opérateur @>.

Il est également possible d’indexer du JSONB grâce aux index GIN :

1create index ON json_stack using gin (json );

Enfin, voici un exemple de requête :

 1explain (analyze,buffers)  select * from json_stack
 2    where json @>  '{"displayname":"anayrat"}'::jsonb;
 3                                  QUERY PLAN
 4---------------------------------------------------------------------------------------
 5 Bitmap Heap Scan on json_stack
 6                (cost=286.95..33866.98 rows=33283 width=1011)
 7                (actual time=0.099..0.102 rows=2 loops=1)
 8   Recheck Cond: (json @> '{"displayname": "anayrat"}'::jsonb)
 9   Heap Blocks: exact=2
10   Buffers: shared hit=17
11   ->  Bitmap Index Scan on json_stack_json_idx
12                          (cost=0.00..278.62 rows=33283 width=0)
13                          (actual time=0.092..0.092 rows=2 loops=1)
14         Index Cond: (json @> '{"displayname": "anayrat"}'::jsonb)
15         Buffers: shared hit=15
16 Planning time: 0.088 ms
17 Execution time: 0.121 ms
18(9 rows)

En lisant ce plan on constate que le moteur se trompe complètement. Il estime obtenir 33 283 lignes, or la requête retourne seulement deux enregistrements. Le facteur d’erreur est d’environ 15 000!

Sélectivité sur du JSONB

Quelle est la cardinalité de la table? L’information est contenue dans le catalogue système :

1select reltuples from pg_class where relname = 'json_stack';
2  reltuples
3-------------
4 3.32833e+07

Quelle est la sélectivité estimée?

1select 33283 / 3.32833e+07;
2        ?column?
3------------------------
4 0.00099999098647069251

En gros 0.001.

Plongée dans le code

Je me suis amusé à sortir le débugueur GDB pour trouver d’où pouvait venir ce chiffre. J’ai fini par arriver dans cette fonction :

 1[...]
 279 /*
 380  *  contsel -- How likely is a box to contain (be contained by) a given box?
 481  *
 582  * This is a tighter constraint than "overlap", so produce a smaller
 683  * estimate than areasel does.
 784  */
 885
 986 Datum
1087 contsel(PG_FUNCTION_ARGS)
1188 {
1289     PG_RETURN_FLOAT8(0.001);
1390 }
14[...]

Le calcul de la sélectivité dépend du type de l’opérateur. Regardons dans le catalogue système :

 1select oprname,typname,oprrest from pg_operator op
 2    join pg_type typ ON op.oprleft= typ.oid where oprname = '@>';
 3 oprname | typname  |   oprrest
 4---------+----------+--------------
 5 @>      | polygon  | contsel
 6 @>      | box      | contsel
 7 @>      | box      | contsel
 8 @>      | path     | -
 9 @>      | polygon  | contsel
10 @>      | circle   | contsel
11 @>      | _aclitem | -
12 @>      | circle   | contsel
13 @>      | anyarray | arraycontsel
14 @>      | tsquery  | contsel
15 @>      | anyrange | rangesel
16 @>      | anyrange | rangesel
17 @>      | jsonb    | contsel

On retrouve plusieurs types, en effet l’opérateur @>signifie (en gros) : “Est-ce que l’objet de gauche contient l’élément de droite?”. Il est utilisé pour différents types : géométrie, tableaux…

Dans notre cas, est-ce que l’objet JSONB de gauche contient l’élément '{"displayname":"anayrat"}' ?

Un objet JSON est un type particulier. Déterminer la sélectivité d’un élément serait assez complexe. Le commentaire est assez explicite :

 1 25 /*
 2 26  *  Selectivity functions for geometric operators.  These are bogus -- unless
 3 27  *  we know the actual key distribution in the index, we can't make a good
 4 28  *  prediction of the selectivity of these operators.
 5 29  *
 6 30  *  Note: the values used here may look unreasonably small.  Perhaps they
 7 31  *  are.  For now, we want to make sure that the optimizer will make use
 8 32  *  of a geometric index if one is available, so the selectivity had better
 9 33  *  be fairly small.
10[...]

Il n’est donc pas possible (actuellement) de déterminer la sélectivité sur des objets JSONB.

Mais tout n’est pas perdu 😉

Index fonctionnels

PostgreSQL permet de créer des index dits fonctionnels. On crée un index à partir d’une fonction.

Vous allez me dire : “Oui mais on n’en a pas besoin. Dans ton exemple, postgres utilise déjà un index”.

C’est vrai, la différence, c’est que le moteur collecte des statistiques à propos de cet index. Comme si le résultat de la fonction était une nouvelle colonne.

Création de la fonction et de l’index

C’est très simple :

1CREATE or replace FUNCTION json_displayname (jsonb )
2RETURNS text
3AS $$
4select $1->>'displayname'
5$$
6LANGUAGE SQL IMMUTABLE PARALLEL SAFE
7;
8
9create index ON json_stack (json_displayname(json));

Recherche en utilisant une fonction

Pour utiliser l’index que nous venons de créer, il faut l’utiliser dans la requête :

 1explain (analyze,verbose,buffers) select * from json_stack
 2        where json_displayname(json) = 'anayrat';
 3                        QUERY PLAN
 4----------------------------------------------------------------------------
 5 Index Scan using json_stack_json_displayname_idx on public.json_stack
 6            (cost=0.56..371.70 rows=363 width=1011)
 7            (actual time=0.021..0.023 rows=2 loops=1)
 8   Output: post_id, json
 9   Index Cond: ((json_stack.json ->> 'displayname'::text) = 'anayrat'::text)
10   Buffers: shared hit=7
11 Planning time: 0.107 ms
12 Execution time: 0.037 ms
13(6 rows)

Cette fois le moteur estime obtenir 363 lignes, ce qui est bien plus proche du résultat final (2).

Autre exemple et calcul de sélectivité

Cette fois nous allons effectuer une recherche sur le champ “age” de l’objet JSON :

 1explain (analyze,buffers)  select * from json_stack
 2      where json @>  '{"age":27}'::jsonb;
 3                      QUERY PLAN
 4---------------------------------------------------------------------
 5 Bitmap Heap Scan on json_stack
 6        (cost=286.95..33866.98 rows=33283 width=1011)
 7        (actual time=667.411..12723.906 rows=804630 loops=1)
 8   Recheck Cond: (json @> '{"age": 27}'::jsonb)
 9   Rows Removed by Index Recheck: 2211190
10   Heap Blocks: exact=391448 lossy=344083
11   Buffers: shared hit=576350 read=881510
12   I/O Timings: read=2947.458
13   ->  Bitmap Index Scan on json_stack_json_idx
14        (cost=0.00..278.62 rows=33283 width=0)
15        (actual time=562.648..562.648 rows=804644 loops=1)
16         Index Cond: (json @> '{"age": 27}'::jsonb)
17         Buffers: shared hit=9612 read=5140
18         I/O Timings: read=11.195
19 Planning time: 0.073 ms
20 Execution time: 12809.392 ms
21(12 lignes)
22
23set work_mem = '100MB';
24
25explain (analyze,buffers)  select * from json_stack
26      where json @>  '{"age":27}'::jsonb;
27                      QUERY PLAN
28---------------------------------------------------------------------
29 Bitmap Heap Scan on json_stack
30        (cost=286.95..33866.98 rows=33283 width=1011)
31        (actual time=748.968..5720.628 rows=804630 loops=1)
32   Recheck Cond: (json @> '{"age": 27}'::jsonb)
33   Rows Removed by Index Recheck: 14
34   Heap Blocks: exact=735531
35   Buffers: shared hit=123417 read=780542
36   I/O Timings: read=1550.124
37   ->  Bitmap Index Scan on json_stack_json_idx
38        (cost=0.00..278.62 rows=33283 width=0)
39        (actual time=545.553..545.553 rows=804644 loops=1)
40         Index Cond: (json @> '{"age": 27}'::jsonb)
41         Buffers: shared hit=9612 read=5140
42         I/O Timings: read=11.265
43 Planning time: 0.079 ms
44 Execution time: 5796.219 ms
45(12 lignes)

Dans cet exemple on constate que le moteur estime toujours obtenir 33 283 enregistrements. Or il en obtient 804 644. Cette fois il est beaucoup trop optimiste.

PS : Dans mon exemple vous verrez que j’ai joué la même requête en modifiant la work_mem. C’est pour éviter que le bitmap ne soit lossy ²

Comme vu ci-dessus nous pouvons créer une fonction :

1CREATE or replace FUNCTION json_age (jsonb )
2RETURNS text
3AS $$
4select $1->>'age'
5$$
6LANGUAGE SQL IMMUTABLE PARALLEL SAFE
7;
8
9create index ON json_stack (json_age(json));

A nouveau l’estimation est bien meilleure:

 1explain (analyze,buffers)   select * from json_stack
 2      where json_age(json) = '27';
 3                         QUERY PLAN
 4------------------------------------------------------------------------
 5 Index Scan using json_stack_json_age_idx on json_stack
 6  (cost=0.56..733177.05 rows=799908 width=1011)
 7  (actual time=0.042..2355.179 rows=804630 loops=1)
 8   Index Cond: ((json ->> 'age'::text) = '27'::text)
 9   Buffers: shared read=737720
10   I/O Timings: read=1431.275
11 Planning time: 0.087 ms
12 Execution time: 2410.269 ms

Le moteur estime obtenir 799 908 enregistrements. nous allons le vérifier.

Comme je l’ai précisé, le moteur possède des informations de statistiques basées sur un échantillon de données. Ces informations sont stockées dans un catalogue système lisible grâce à la vue pg_stats. Avec un index fonctionnel, le moteur le voit comme une nouvelle colonne.

1schemaname             | public
2tablename              | json_stack_json_age_idx
3attname                | json_age
4[...]
5most_common_vals       | {28,27,29,31,26,30,32,25,33,34,36,24,[...]}
6most_common_freqs      | {0.0248,0.0240333,0.0237333,0.0236333,0.0234,0.0229333,[...]}
7[...]

La colonne most_common_vals contient les valeurs les plus fréquentes et la colonne most_common_freqs la sélectivité correspondante.

Donc pour age=27 on a une sélectivité de 0.0240333.

Ensuite il suffit de multiplier la sélectivité par la cardinalité de la table :

 1select n_live_tup from pg_stat_all_tables where relname ='json_stack';
 2 n_live_tup
 3------------
 4   33283258
 5
 6
 7select 0.0240333 * 33283258;
 8    ?column?
 9----------------
10 799906.5244914

D’accord, l’estimation est bien meilleure. Mais est-ce grave si le moteur se trompe? Dans les deux requêtes ci-dessus on constate que le moteur exploite bien un index et que le résultat est obtenu rapidement.

Conséquences d’une mauvaise estimation

En quoi une mauvaise estimation peut poser problème?

Quand ça entraine le choix d’un mauvais plan.

Par exemple cette requête d’aggregation qui compte le nombre de posts par age:

 1explain (analyze,buffers)  select json->'age',count(json->'age')
 2                          from json_stack group by json->'age' ;
 3                             QUERY PLAN
 4--------------------------------------------------------------------------------------
 5 Finalize GroupAggregate
 6  (cost=10067631.49..14135810.84 rows=33283256 width=40)
 7  (actual time=364151.518..411524.862 rows=86 loops=1)
 8   Group Key: ((json -> 'age'::text))
 9   Buffers: shared hit=1949354 read=1723941, temp read=1403174 written=1403189
10   I/O Timings: read=155401.828
11   ->  Gather Merge
12        (cost=10067631.49..13581089.91 rows=27736046 width=40)
13        (actual time=364151.056..411524.589 rows=256 loops=1)
14         Workers Planned: 2
15         Workers Launched: 2
16         Buffers: shared hit=1949354 read=1723941, temp read=1403174 written=1403189
17         I/O Timings: read=155401.828
18         ->  Partial GroupAggregate
19            (cost=10066631.46..10378661.98 rows=13868023 width=40)
20            (actual time=363797.836..409187.566 rows=85 loops=3)
21               Group Key: ((json -> 'age'::text))
22               Buffers: shared hit=5843962 read=5177836,
23                        temp read=4212551 written=4212596
24               I/O Timings: read=478460.123
25               ->  Sort
26                  (cost=10066631.46..10101301.52 rows=13868023 width=1042)
27                  (actual time=299775.029..404358.743 rows=11094533 loops=3)
28                     Sort Key: ((json -> 'age'::text))
29                     Sort Method: external merge  Disk: 11225392kB
30                     Buffers: shared hit=5843962 read=5177836,
31                              temp read=4212551 written=4212596
32                     I/O Timings: read=478460.123
33                     ->  Parallel Seq Scan on json_stack
34                        (cost=0.00..4791997.29 rows=13868023 width=1042)
35                        (actual time=0.684..202361.133 rows=11094533 loops=3)
36                           Buffers: shared hit=5843864 read=5177836
37                           I/O Timings: read=478460.123
38 Planning time: 0.080 ms
39 Execution time: 411688.165 ms

Le moteur s’attend à obtenir 33 283 256 d’enregistrement au lieu de 86. Il a également effectué un tri très couteux puisqu’il a généré plus de 33Go (11GO * 3 loops) de fichiers temporaires.

La même requête en utilisant la fonction json_age :

 1explain (analyze,buffers)   select json_age(json),count(json_age(json))
 2                              from json_stack group by json_age(json);
 3                                             QUERY PLAN
 4--------------------------------------------------------------------------------------
 5 Finalize GroupAggregate
 6  (cost=4897031.22..4897033.50 rows=83 width=40)
 7  (actual time=153985.585..153985.667 rows=86 loops=1)
 8   Group Key: ((json ->> 'age'::text))
 9   Buffers: shared hit=1938334 read=1736761
10   I/O Timings: read=106883.908
11   ->  Sort
12      (cost=4897031.22..4897031.64 rows=166 width=40)
13      (actual time=153985.581..153985.598 rows=256 loops=1)
14         Sort Key: ((json ->> 'age'::text))
15         Sort Method: quicksort  Memory: 37kB
16         Buffers: shared hit=1938334 read=1736761
17         I/O Timings: read=106883.908
18         ->  Gather
19            (cost=4897007.46..4897025.10 rows=166 width=40)
20            (actual time=153985.264..153985.360 rows=256 loops=1)
21               Workers Planned: 2
22               Workers Launched: 2
23               Buffers: shared hit=1938334 read=1736761
24               I/O Timings: read=106883.908
25               ->  Partial HashAggregate
26                  (cost=4896007.46..4896008.50 rows=83 width=40)
27                  (actual time=153976.620..153976.635 rows=85 loops=3)
28                     Group Key: (json ->> 'age'::text)
29                     Buffers: shared hit=5811206 read=5210494
30                     I/O Timings: read=320684.515
31                     ->  Parallel Seq Scan on json_stack
32                     (cost=0.00..4791997.29 rows=13868023 width=1042)
33                     (actual time=0.090..148691.566 rows=11094533 loops=3)
34                           Buffers: shared hit=5811206 read=5210494
35                           I/O Timings: read=320684.515
36 Planning time: 0.118 ms
37 Execution time: 154086.685 ms

Ici le moteur effectue le tri plus tard sur beaucoup moins de lignes. Le temps d’exécution est nettement réduit et on s’épargne surtout 33Go de fichiers temporaires.

Mot de la fin

Les statistiques sont indispensables pour choisir les meilleurs plan d’exécution. Actuellement Postgres dispose de fonctionnalités avancées pour le JSON ³ Malheureusement il n’y a pas encore de possibilité d’ajouter de statistiques sur le type JSONB. A noter que PostgreSQL 10 apporte l’infrastructure pour étendre les statistiques. Espérons que dans le futur il sera possible de les étendre pour des types spéciaux.

En attendant il est possible de contourner cette limitation en utilisant les index fonctionnels.

https://www.postgresql.org/docs/current/static/functions-json.html ↩︎
Un noeud bitmap devient lossy lorsque le moteur ne peut pas faire un bitmap de tous les enregistrements. Il passe donc en mode dit “lossy” où le bitmap ne se fait plus sur l’enregistrement mais pour le bloc entier. Ce qui nécessite de lire plus de blocs et de faire un “recheck” qui consiste à filter les enregistrements obtenus. ↩︎
La documentation est très complète et fournie de nombreux exemples : usage des opérateurs, indexation. ↩︎

No results found

PostgreSQL - JSONB et Statistiques