# Statistics, cardinality, selectivity

SQL is a declarative language. It is a language where the user asks what he wants. Without specifying how the computer should proceed to get the results.

It is the DBMS that must find “how” to perform the operation by ensuring:

• Return the right result
• Ideally, as soon as possible

“As soon as possible” means:

• Minimize disk access
• Give priority to sequential readings (especially important for mechanical disks)
• Reduce the number of CPU operations
• Reduce memory footprint

To do this, a DBMS has an optimizer whose role is to find the best execution plan.

PostgreSQL has an optimizer based on a cost mechanism. Without going into details, each operation has a unit cost (reading a sequential block, CPU processing of a record …). Postgres calculates the cost of several execution plans (if the query is simple) and chooses the least expensive.

How can postgres estimate the cost of a plan? By estimating the cost of each node of the plan based on statistics. PostgreSQL analyzes tables to obtain a statistical sample (this operation is normally performed by the autovacuum daemon).

Some words of vocabulary:

Cardinality: In set theory, it is the number of elements in a set. In databases, it will be the number of rows in a table or after applying a predicate.

Selectivity: Fraction of records returned after applying a predicate. For example, a table containing people and about one third of them are children. The selectivity of the predicate `person = 'child'` will be 0.33.

If this table contains 300 people (this is the cardinality of the “people” set), we can estimate the number of children because we know that the predicate `person = 'child'` is 0.33:

300 * 0.33 = 99

These estimates can be obtained with `EXPLAIN` which displays the execution plan.

Example (simplified):

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

(cost=0.00..5.75 rows=100 …) : Indicates the estimated cost and the estimated number of records (rows).

(actual rows=100 …) : Indicates the number of records obtained.

PostgreSQL documentation provides examples of estimation calculations : Row Estimation Examples

It is quite easy to understand how to obtain estimates from scalar data types.

How are things going for particular types? For example JSON?

# Search on JSONB

## Dataset

As in previous articles, I used the stackoverflow dataset. I created a new table by aggregating data from multiple tables into a JSON object:

``````CREATE TABLE json_stack AS
SELECT t.post_id,
row_to_json(t,
TRUE)::jsonb json
FROM
(SELECT posts.id post_id,
posts.owneruserid,
users.id,
title,
tags,
BODY,
displayname,
websiteurl,
LOCATION,
age
FROM posts
``````

The processing is quite long because the two tables involved total nearly 40GB.

So I get a 40GB table that looks like this:

`````` \dt+ json_stack
List of relations
Schema |    Name    | Type  |  Owner   | Size  | Description
--------+------------+-------+----------+-------+-------------
public | json_stack | table | postgres | 40 GB |
(1 row)

\d json_stack
Table "public.json_stack"
Column  |  Type   | Collation | Nullable | Default
---------+---------+-----------+----------+---------
post_id | integer |           |          |
json    | jsonb   |           |          |

select post_id,jsonb_pretty(json) from json_stack
where json_displayname(json) = 'anayrat' limit 1;
post_id  |
----------+-----------------------------------------------------------------------------------------
26653490 | {
|     "id": 4197886,
|     "age": null,
|     "body": "<p>I have an issue with date filter. I follow [...]
|     "tags": "<java><logstash>",
|     "title": "Logstash date filter failed parsing",
|     "post_id": 26653490,
|     "location": "Valence",
|     "websiteurl": "https://blog.anayrat.info",
|     "displayname": "anayrat",
|     "owneruserid": 4197886
| }
``````

## Operators and indexing for JSONB

PostgreSQL provides several operators for querying JSONB 1. We will use the operator `@>`.

It is also possible to index JSONB using GIN indexes:

``````create index ON json_stack using gin (json );
``````

Finally, here is an example of query:

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

Reading this plan we see that postgres is completely wrong. He estimates getting 33,283 lines, but the query returns only two rows. The error factor is around 15,000!

## Selectivity on JSONB

What is the cardinality of the table? The information is contained in the system catalog:

``````select reltuples from pg_class where relname = 'json_stack';
reltuples
-------------
3.32833e+07
``````

What is the estimated selectivity?

``````select 33283 / 3.32833e+07;
?column?
------------------------
0.00099999098647069251
``````

Arround 0.001.

## Diving in the code

I had fun taking out the debugger GDB to find out where this number could come from. I ended up arriving in this function:

``````[...]
79 /*
80  *  contsel -- How likely is a box to contain (be contained by) a given box?
81  *
82  * This is a tighter constraint than "overlap", so produce a smaller
83  * estimate than areasel does.
84  */
85
86 Datum
87 contsel(PG_FUNCTION_ARGS)
88 {
89     PG_RETURN_FLOAT8(0.001);
90 }
[...]
``````

The selectivity depends on the type of the operator. Let’s look in the system catalog:

``````select oprname,typname,oprrest from pg_operator op
join pg_type typ ON op.oprleft= typ.oid where oprname = '@>';
oprname | typname  |   oprrest
---------+----------+--------------
@>      | polygon  | contsel
@>      | box      | contsel
@>      | box      | contsel
@>      | path     | -
@>      | polygon  | contsel
@>      | circle   | contsel
@>      | _aclitem | -
@>      | circle   | contsel
@>      | anyarray | arraycontsel
@>      | tsquery  | contsel
@>      | anyrange | rangesel
@>      | anyrange | rangesel
@>      | jsonb    | contsel
``````

There are several types, in fact the operator `@>` means (roughly): “Does the object on the left contain the right element?”. It is used for different types: geometry, array …

In our case, does the left JSONB object contain the `''{" displayname ":" anayrat "}''` element?

A JSON object is a special type. Determining the selectivity of an element would be quite complex. The comment is quite explicit:

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

It is therefore not possible (currently) to determine the selectivity of JSONB objects.

But all is not lost 😉

# Functional indexes

PostgreSQL permits to creates so-called functional indexes. We create an index on a fonction.

You’re going to say, “Yes, but we do not need it.” In your example, postgres is already using an index.

That’s right, the difference is that postgres collects statistics about this index. As if the result of the function was a new column.

## Creating the function and the index

It is very simple :

``````CREATE or replace FUNCTION json_displayname (jsonb )
RETURNS text
AS \$\$
select \$1->>'displayname'
\$\$
LANGUAGE SQL IMMUTABLE PARALLEL SAFE
;

create index ON json_stack (json_displayname(json));
``````

## Search using a function

To use the index we just created, use it in the query:

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

This time postgres estimates to get 363 rows, which is much closer to the final result (2).

## Another example and selectivity calculation

This time we will search on the “age” field of the JSON object:

``````explain (analyze,buffers)  select * from json_stack
where json @>  '{"age":27}'::jsonb;
QUERY PLAN
---------------------------------------------------------------------
Bitmap Heap Scan on json_stack
(cost=286.95..33866.98 rows=33283 width=1011)
(actual time=667.411..12723.906 rows=804630 loops=1)
Recheck Cond: (json @> '{"age": 27}'::jsonb)
Rows Removed by Index Recheck: 2211190
Heap Blocks: exact=391448 lossy=344083
->  Bitmap Index Scan on json_stack_json_idx
(cost=0.00..278.62 rows=33283 width=0)
(actual time=562.648..562.648 rows=804644 loops=1)
Index Cond: (json @> '{"age": 27}'::jsonb)
Planning time: 0.073 ms
Execution time: 12809.392 ms
(12 lignes)

set work_mem = '100MB';

explain (analyze,buffers)  select * from json_stack
where json @>  '{"age":27}'::jsonb;
QUERY PLAN
---------------------------------------------------------------------
Bitmap Heap Scan on json_stack
(cost=286.95..33866.98 rows=33283 width=1011)
(actual time=748.968..5720.628 rows=804630 loops=1)
Recheck Cond: (json @> '{"age": 27}'::jsonb)
Rows Removed by Index Recheck: 14
Heap Blocks: exact=735531
->  Bitmap Index Scan on json_stack_json_idx
(cost=0.00..278.62 rows=33283 width=0)
(actual time=545.553..545.553 rows=804644 loops=1)
Index Cond: (json @> '{"age": 27}'::jsonb)
Planning time: 0.079 ms
Execution time: 5796.219 ms
(12 lignes)
``````

In this example we see that postgres still estimates 33,283 records. Out he gets 804 644. This time he is too much optimistic.

P.S: In my example you will see that I run the same query by modifying `work_mem`. This is to prevent the bitmap from being `lossy` 2

As seen above we can create a function:

``````CREATE or replace FUNCTION json_age (jsonb )
RETURNS text
AS \$\$
select \$1->>'age'
\$\$
LANGUAGE SQL IMMUTABLE PARALLEL SAFE
;

create index ON json_stack (json_age(json));
``````

Again the estimate is much better:

``````explain (analyze,buffers)   select * from json_stack
where json_age(json) = '27';
QUERY PLAN
------------------------------------------------------------------------
Index Scan using json_stack_json_age_idx on json_stack
(cost=0.56..733177.05 rows=799908 width=1011)
(actual time=0.042..2355.179 rows=804630 loops=1)
Index Cond: ((json ->> 'age'::text) = '27'::text)
Planning time: 0.087 ms
Execution time: 2410.269 ms
``````

Postgres estimates to get 799,908 records. we will check it.

As I said, Postgres has statistics information based on a sample of data. This information is stored in a readable system catalog with the `pg_stats` view. With a functional index, Postgres sees it as a new column.

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

The column most_common_vals contains the most common values and the column most_common_freqs the corresponding selectivity.

So for `age = 27` we have a selectivity of 0.0240333.

Then we just have to multiply the selectivity by the cardinality of the table:

``````select n_live_tup from pg_stat_all_tables where relname ='json_stack';
n_live_tup
------------
33283258

select 0.0240333 * 33283258;
?column?
----------------
799906.5244914
``````

Okay, estimate is much better. But is it serious if postgres is wrong? In the two queries above we see that postgres uses an index and that the result is obtained quickly.

# Consequences of a bad estimate

How can a bad estimate be a problem?

For example, this aggregation query that counts the number of posts by age:

``````explain (analyze,buffers)  select json->'age',count(json->'age')
from json_stack group by json->'age' ;
QUERY PLAN
--------------------------------------------------------------------------------------
Finalize GroupAggregate
(cost=10067631.49..14135810.84 rows=33283256 width=40)
(actual time=364151.518..411524.862 rows=86 loops=1)
Group Key: ((json -> 'age'::text))
->  Gather Merge
(cost=10067631.49..13581089.91 rows=27736046 width=40)
(actual time=364151.056..411524.589 rows=256 loops=1)
Workers Planned: 2
Workers Launched: 2
->  Partial GroupAggregate
(cost=10066631.46..10378661.98 rows=13868023 width=40)
(actual time=363797.836..409187.566 rows=85 loops=3)
Group Key: ((json -> 'age'::text))
->  Sort
(cost=10066631.46..10101301.52 rows=13868023 width=1042)
(actual time=299775.029..404358.743 rows=11094533 loops=3)
Sort Key: ((json -> 'age'::text))
Sort Method: external merge  Disk: 11225392kB
->  Parallel Seq Scan on json_stack
(cost=0.00..4791997.29 rows=13868023 width=1042)
(actual time=0.684..202361.133 rows=11094533 loops=3)
Planning time: 0.080 ms
Execution time: 411688.165 ms
``````

Postgres expects to get 33,283,256 records instead of 86. It also performed a very expensive sort since it generated more than 33GB (11GB * 3 loops) of temporary files.

The same query using the json_age function:

``````explain (analyze,buffers)   select json_age(json),count(json_age(json))
from json_stack group by json_age(json);
QUERY PLAN
--------------------------------------------------------------------------------------
Finalize GroupAggregate
(cost=4897031.22..4897033.50 rows=83 width=40)
(actual time=153985.585..153985.667 rows=86 loops=1)
Group Key: ((json ->> 'age'::text))
->  Sort
(cost=4897031.22..4897031.64 rows=166 width=40)
(actual time=153985.581..153985.598 rows=256 loops=1)
Sort Key: ((json ->> 'age'::text))
Sort Method: quicksort  Memory: 37kB
->  Gather
(cost=4897007.46..4897025.10 rows=166 width=40)
(actual time=153985.264..153985.360 rows=256 loops=1)
Workers Planned: 2
Workers Launched: 2
->  Partial HashAggregate
(cost=4896007.46..4896008.50 rows=83 width=40)
(actual time=153976.620..153976.635 rows=85 loops=3)
Group Key: (json ->> 'age'::text)
->  Parallel Seq Scan on json_stack
(cost=0.00..4791997.29 rows=13868023 width=1042)
(actual time=0.090..148691.566 rows=11094533 loops=3)
Planning time: 0.118 ms
Execution time: 154086.685 ms

``````

Here postgres sorts later on a lot less lines. The execution time is significantly reduced and we save especially 33GB of temporary files.

# Last word

Statistics are essential for choosing the best execution plan. Currently Postgres has advanced features for JSON 3 Unfortunately there is no possibility to add statistics on the JSONB type. Note that PostgreSQL 10 provides the infrastructure to extend statistics. Hopefully in the future it will be possible to extend them for special types.

In the meantime, it is possible to work around this limitation by using functional indexes.

1. A bitmap node becomes lossy when postgres can not make a bitmap of all tuples. It thus passes in so-called “lossy” mode where the bitmap is no longer on the tuple but for the entire block. This requires reading more blocks and doing a “recheck” which consists in filtering obtained tuples. ↩︎

2. The documentation is very complete and provides many examples: use of operators, indexing. ↩︎ 