
ЧИСЛО СТРОК
~~~~~~~~~~~

Создадим БД и таблицу с неравномерно распределенными данными.
Мы будем эмулировать наблюдения за температурой в течении нескольких лет.

        => create database db17;
        CREATE DATABASE

        => \c db17
        You are now connected to database "db17" as user "postgres".

        => create table weather(id serial primary key, observation_date date, temperature integer);
        CREATE TABLE

        => insert into weather(observation_date, temperature)
        => select gen.d,
        =>       -cos( extract(day from gen.d - '2010-01-01 00:00:00'::timestamp) / 365.0 * 2.0 * pi() )*30.0 + (random()*6.0-3.0)
        => from   generate_series('2000-01-01 00:00:00'::timestamp,'2015-12-31 00:00:00'::timestamp, '1 day') as gen(d);
        INSERT 0 5844

.......................................................................

У нас получилось вот такое распределение температуры по месяцам:

        => select extract(month from observation_date) mon, min(temperature), round(avg(temperature),1), max(temperature) from weather group by 1 order by 1;
         mon | min | round | max 
        -----+-----+-------+-----
           1 | -33 | -28.8 | -23
           2 | -29 | -21.6 | -13
           3 | -19 |  -9.0 |   2
           4 |  -4 |   6.5 |  16
           5 |  11 |  20.0 |  28
           6 |  22 |  28.2 |  33
           7 |  24 |  28.9 |  33
           8 |  13 |  21.6 |  29
           9 |  -2 |   8.5 |  18
          10 | -17 |  -7.0 |   3
          11 | -28 | -20.5 | -11
          12 | -33 | -28.5 | -22
        (12 rows)
        

.......................................................................

Причем значения температуры встречаются с разной частотой:

        => select temperature, count(*) from weather where temperature >= 0 group by temperature order by temperature;
         temperature | count 
        -------------+-------
                   0 |    74
                   1 |    64
                   2 |    56
                   3 |    64
                   4 |    53
                   5 |    57
                   6 |    66
                   7 |    65
                   8 |    64
                   9 |    64
                  10 |    70
                  11 |    69
                  12 |    61
                  13 |    72
                  14 |    77
                  15 |    67
                  16 |    80
                  17 |    81
                  18 |    71
                  19 |    77
                  20 |    89
                  21 |    77
                  22 |   104
                  23 |   105
                  24 |   101
                  25 |   114
                  26 |   130
                  27 |   198
                  28 |   191
                  29 |   159
                  30 |   128
                  31 |   102
                  32 |    77
                  33 |    24
        (34 rows)
        

.......................................................................

Проанализируем таблицу. Значение параметра, управляющего размером
статистики, по умолчанию равно 100:

        => show default_statistics_target;
         default_statistics_target 
        ---------------------------
         100
        (1 row)
        

        => analyze weather;
        ANALYZE

.......................................................................

Теперь посмотрим на оценку кардинальности в простом случае -
запрос без предикатов.

        => explain select * from weather;
                                 QUERY PLAN                         
        ------------------------------------------------------------
         Seq Scan on weather  (cost=0.00..87.44 rows=5844 width=12)
        (1 row)
        

Точное значение:

        => select count(*) from weather;
         count 
        -------
          5844
        (1 row)
        

.......................................................................

Оптимизатор получает значение из pg_class, куда оно записывается
при анализе:

        => select reltuples from pg_class where relname = 'weather';
         reltuples 
        -----------
              5844
        (1 row)
        

На самом деле при анализе таблицы учитывается 300*default_statistics_target
строк, поэтому в данном случае оценка всегда будет точной.

.......................................................................

ДОЛЯ NULL-ЗНАЧЕНИЙ
~~~~~~~~~~~~~~~~~~

Что, если часть значений будет содержать null?

        => update weather set temperature = null where mod(id,100) = 0;
        UPDATE 58

        => analyze weather;
        ANALYZE

        => explain select * from weather where temperature is null;
                                QUERY PLAN                        
        ----------------------------------------------------------
         Seq Scan on weather  (cost=0.00..87.44 rows=58 width=12)
           Filter: (temperature IS NULL)
        (2 rows)
        

.......................................................................

Оценка оптимизатора получена с учетом доли null-значений:

        => select null_frac from pg_stats where tablename = 'weather' and attname = 'temperature';
         null_frac  
        ------------
         0.00992471
        (1 row)
        

Умножив селективность на общее число строк, получаем оценку кардинальности:

        => select c.reltuples * s.null_frac
        => from   pg_class c, pg_stats s
        => where  c.relname = 'weather' and s.tablename = c.relname and s.attname = 'temperature';
         ?column? 
        ----------
               58
        (1 row)
        

.......................................................................

НАИБОЛЕЕ ЧАСТЫЕ ЗНАЧЕНИЯ
~~~~~~~~~~~~~~~~~~~~~~~~

Если значение есть в списке наиболее частых значений, то селективность
можно узнать непосредственно из статистики. Пример:

        => explain select * from weather where temperature = 27;
                                 QUERY PLAN                         
        ------------------------------------------------------------
         Seq Scan on weather  (cost=0.00..102.05 rows=198 width=12)
           Filter: (temperature = 27)
        (2 rows)
        

Точное значение:

        => select count(*) from weather where temperature = 27;
         count 
        -------
           198
        (1 row)
        

.......................................................................

Вот как выглядит список наиболее частых значений и частота их
втречаемости:

        => \x
        Expanded display is on.

        => select most_common_vals, most_common_freqs from pg_stats where tablename = 'weather' and attname = 'temperature';
        -[ RECORD 1 ] 
        most_common_vals  | {27,-28,-27,28,29,-29,-30,-26,26,30,25,-31,-23,-24,23,22,-25,-20,31,24,-32,20,-18,17,-17,16,-22,-14,19,21,32,-21,-19,-12,14,-13,-6,0,13,-7,18,-15,-3,10,11,15,6,-16,1,3,7,8,9,-1,12,-10,-11,-9,-8,-4,5,2,-2,4,-5,33,-33}
        most_common_freqs | {0.0338809,0.0331964,0.0323409,0.0321697,0.0272074,0.0253251,0.0239562,0.0219028,0.0219028,0.0213895,0.019165,0.0184805,0.0181383,0.0179671,0.0179671,0.017796,0.0172827,0.0172827,0.0172827,0.0169405,0.0157426,0.0147159,0.0145448,0.0136893,0.0135181,0.0135181,0.013347,0.013347,0.0131759,0.0131759,0.0131759,0.0130048,0.0130048,0.0130048,0.0128337,0.0126626,0.0126626,0.0124914,0.0123203,0.0121492,0.0119781,0.011807,0.011807,0.011807,0.011807,0.0112936,0.0111225,0.0109514,0.0109514,0.0109514,0.0109514,0.0107803,0.0107803,0.0104381,0.0104381,0.0102669,0.0100958,0.0100958,0.00975359,0.00975359,0.00975359,0.00958248,0.00941136,0.00906913,0.00889802,0.00410678,0.00376454}
        

        => \x
        Expanded display is off.

Значение параметра default_statistics_target определяет максимальное
число значений. В нашем случае сотни хватает, чтобы хранить все значения.

.......................................................................

Кардинальность вычисляется как число строк, умноженное на частоту значения:

        => select c.reltuples * s.most_common_freqs[array_position((s.most_common_vals::text::int[]),27)]
        => from   pg_class c, pg_stats s
        => where  c.relname = 'weather' and s.tablename = c.relname and s.attname = 'temperature';
         ?column? 
        ----------
              198
        (1 row)
        

.......................................................................

ЧИСЛО УНИКАЛЬНЫХ ЗНАЧЕНИЙ
~~~~~~~~~~~~~~~~~~~~~~~~~

Если же указанного значения нет в списке наиболее частых, то оно вычисляется
исходя из предположения, что все данные, кроме наиболее частых,
распределены равномерно.

Поскольку в нашем примере список содержит вообще все значения,
изменим значение параметра (на уровне столбца) и проанализируем
таблицу заново.

        => alter table weather alter temperature set statistics 10;
        ALTER TABLE

        => analyze weather;
        ANALYZE

.......................................................................

Вот как выглядит список наиболее частых значений теперь:

        => \x
        Expanded display is on.

        => select most_common_vals, most_common_freqs from pg_stats where tablename = 'weather' and attname = 'temperature';
        -[ RECORD 1 ]-----+------------------------------------------------------------------------------------------------------
        most_common_vals  | {27,-28,-27,28,29,-29,-30,-26,26,30}
        most_common_freqs | {0.0338809,0.0331964,0.0323409,0.0321697,0.0272074,0.0253251,0.0239562,0.0219028,0.0219028,0.0213895}
        

        => \x
        Expanded display is off.

.......................................................................

Например, в этом списке нет значения 0 - оно встречается не так часто.

        => explain select * from weather where temperature = 0;
                                QUERY PLAN                         
        -----------------------------------------------------------
         Seq Scan on weather  (cost=0.00..102.05 rows=73 width=12)
           Filter: (temperature = 0)
        (2 rows)
        

Точное значение:

        => select count(*) from weather where temperature = 0;
         count 
        -------
            73
        (1 row)
        

.......................................................................

Для получения оценки вычислим сумму частот наиболее частых значений:

        => select sum(f) from pg_stats s, unnest(s.most_common_freqs) f
        => where  s.tablename = 'weather' and s.attname = 'temperature';
           sum    
        ----------
         0.273272
        (1 row)
        

И запомним это значение:

        => select sum(f) as mcf from pg_stats s, unnest(s.most_common_freqs) f
        => where  s.tablename = 'weather' and s.attname = 'temperature'
        => \gset

.......................................................................

На менее частые значения приходятся оставшиеся строки.
Поскольку мы исходим из предположения о равномерности распределения
менее частых значений, селективность будет равна 1/nd,
где nd - число уникальных значений:

        => select n_distinct from pg_stats s where s.tablename = 'weather' and s.attname = 'temperature';
         n_distinct 
        ------------
                 67
        (1 row)
        

.......................................................................

Учитывая, что из этих значений 10 входят в список наиболее частых,
получаем следующую оценку:

        => select c.reltuples * (1 - s.null_frac) * (1 - :mcf) / (s.n_distinct - 10)
        => from   pg_class c, pg_stats s
        => where  c.relname = 'weather' and s.tablename = c.relname and s.attname = 'temperature';
             ?column?     
        ------------------
         73.7692668247336
        (1 row)
        

.......................................................................

ГИСТОГРАММА
~~~~~~~~~~~

При условиях "больше" и "меньше" для оценки будет использоваться
список наиболее частых значений, или гистограмма, или оба способа вместе.
Гистограмма стоится так, чтобы не включать наиболее частые значения и null:

        => select histogram_bounds from pg_stats s where s.tablename = 'weather' and s.attname = 'temperature';
                   histogram_bounds           
        --------------------------------------
         {-33,-24,-19,-13,-7,0,7,13,19,23,33}
        (1 row)
        

Число корзин гистограммы определяется параметром статистики, а границы
выбираются так, чтобы в каждой корзине находилось примерно одинаковое
количество значений.

.......................................................................

Рассмотрим пример:

        => explain select * from weather where temperature between 0 and 13;
                                 QUERY PLAN                         
        ------------------------------------------------------------
         Seq Scan on weather  (cost=0.00..116.66 rows=838 width=12)
           Filter: ((temperature >= 0) AND (temperature <= 13))
        (2 rows)
        

Точное значение:

        => select count(*) from weather where temperature between 0 and 13;
         count 
        -------
           893
        (1 row)
        

.......................................................................

Не будем приводить точный расчет, но:
* указанный интервал занимает примерно 2 корзины гистограммы из 10;
* указанный интервал не попадает на наиболее частые значения.
Поэтому кардинальность вычисляется примерно так:

        => select c.reltuples * (1 - s.null_frac) * (1 - :mcf) * (2.0 / 10.0)
        => from   pg_class c, pg_stats s
        => where  c.relname = 'weather' and s.tablename = c.relname and s.attname = 'temperature';
             ?column?     
        ------------------
         840.969641801963
        (1 row)
        

На самом деле учитываются и не полностью занятые корзины (с помощью
линейной аппроксимации).

.......................................................................

СОЕДИНЕНИЯ
~~~~~~~~~~

Селективность соединения - доля строк от декартового произведения
двух таблиц. Ее сложнее считать, чем селективность ограничивающих
условий, и точность обычно получается ниже.

Мы рассмотрим один простой пример.
Пусть имеется еще одна таблица, в которой могут храниться комментарии
к наблюдениям:

        => create table notes(weather_id integer references weather(id), note text);
        CREATE TABLE

        => insert into notes select id, 'test' from weather, generate_series(1,3) where temperature > 25 or temperature < -25;
        INSERT 0 6063

        => analyze notes;
        ANALYZE

.......................................................................

Пример:

        => explain select * from weather w join notes n on (w.id = n.weather_id);
                                        QUERY PLAN                                
        --------------------------------------------------------------------------
         Hash Join  (cost=160.49..334.49 rows=6063 width=21)
           Hash Cond: (n.weather_id = w.id)
           ->  Seq Scan on notes n  (cost=0.00..90.63 rows=6063 width=9)
           ->  Hash  (cost=87.44..87.44 rows=5844 width=12)
                 ->  Seq Scan on weather w  (cost=0.00..87.44 rows=5844 width=12)
        (5 rows)
        

Точное число строк:

        => select count(*) from weather w join notes n on (w.id = n.weather_id);
         count 
        -------
          6063
        (1 row)
        

.......................................................................

В таком простом случае оценка селективности получена как min(1/nd1, 1/nd2).

        => select s1.n_distinct, s2.n_distinct
        => from   pg_stats s1, pg_stats s2
        => where  s1.tablename = 'weather' and s1.attname = 'id'
        => and    s2.tablename = 'notes' and s2.attname = 'weather_id';
         n_distinct | n_distinct 
        ------------+------------
                 -1 |  -0.333333
        (1 row)
        

Обратите внимание, что в данном случае число уникальных значений
дано как доля от всех значений.

.......................................................................

Итоговая оценка:

        => select c1.reltuples * c2.reltuples * 
        =>        least(-1/s1.n_distinct/c1.reltuples, -1/s2.n_distinct/c2.reltuples)
        => from   pg_class c1, pg_stats s1, pg_class c2, pg_stats s2
        => where  c1.relname = 'weather' and s1.tablename = c1.relname and s1.attname = 'id'
        => and    c2.relname = 'notes' and s2.tablename = c2.relname and s2.attname = 'weather_id';
         ?column? 
        ----------
             6063
        (1 row)
        

В общем случае учитывается также наличие значений null, наличие списка
наиболее частых значений и т. д.


КОРРЕЛИРОВАННЫЕ ПРЕДИКАТЫ
~~~~~~~~~~~~~~~~~~~~~~~~~

Рассмотрим пример:

        => explain select * from weather where extract(month from observation_date) = 1 and temperature >= 0;
                                                                       QUERY PLAN                                                               
        ----------------------------------------------------------------------------------------------------------------------------------------
         Seq Scan on weather  (cost=0.00..145.88 rows=14 width=12)
           Filter: ((temperature >= 0) AND (date_part('month'::text, (observation_date)::timestamp without time zone) = '1'::double precision))
        (2 rows)
        

Планировщик ожидает, что в январе будет 14 дней с плюсовой температурой.
Почему так?

.......................................................................

Здесь две проблемы. Рассмотрим их по очереди.
Во-первых, сумеет ли планировщик определить, сколько измерений было сделано
в январе?

        => explain select * from weather where extract(month from observation_date) = 1;
                                                          QUERY PLAN                                                   
        ---------------------------------------------------------------------------------------------------------------
         Seq Scan on weather  (cost=0.00..131.27 rows=29 width=12)
           Filter: (date_part('month'::text, (observation_date)::timestamp without time zone) = '1'::double precision)
        (2 rows)
        

Выясняется, что нет:

        => select count(*) from weather where extract(month from observation_date) = 1;
         count 
        -------
           496
        (1 row)
        

.......................................................................

Проблема здесь в том, что планировщик ничего не знает про семантику
функции extract. С тем же успехом можно взять любую другую:

        => explain select * from weather where random() = 1;
                                QUERY PLAN                         
        -----------------------------------------------------------
         Seq Scan on weather  (cost=0.00..116.66 rows=29 width=12)
           Filter: (random() = '1'::double precision)
        (2 rows)
        

Оценка предикатов вида "функция = константа" оценивается просто как 0.5%
от общего числа строк:

        => select count(*) * 0.005 from weather;
         ?column? 
        ----------
           29.220
        (1 row)
        

.......................................................................

Справиться с неверной оценкой (если она представляет собой проблему,
конечно) можно, создав индекс по выражению. Для таких индексов
собирается отдельная статистика.

        => create index weather_month_idx on weather((
        =>   extract(month from observation_date)
        => ));
        CREATE INDEX

        => analyze weather;
        ANALYZE

.......................................................................

Статистика хранится в pg_stats в отдельной строке:

        => \x
        Expanded display is on.

        => select * from pg_stats where tablename = 'weather_month_idx';
        -[ RECORD 1 ]----------+--------------------------------------------------------------------------------------------------------------------------
        schemaname             | public
        tablename              | weather_month_idx
        attname                | date_part
        inherited              | f
        null_frac              | 0
        avg_width              | 8
        n_distinct             | 12
        most_common_vals       | {1,3,5,7,8,10,12,4,6,9,11,2}
        most_common_freqs      | {0.0848734,0.0848734,0.0848734,0.0848734,0.0848734,0.0848734,0.0848734,0.0821355,0.0821355,0.0821355,0.0821355,0.0773443}
        histogram_bounds       | 
        correlation            | 0.143237
        most_common_elems      | 
        most_common_elem_freqs | 
        elem_count_histogram   | 
        

        => \x
        Expanded display is off.

.......................................................................

Проверим снова:

        => explain select * from weather where extract(month from observation_date) = 1;
                                                               QUERY PLAN                                                        
        -------------------------------------------------------------------------------------------------------------------------
         Bitmap Heap Scan on weather  (cost=12.13..49.81 rows=496 width=12)
           Recheck Cond: (date_part('month'::text, (observation_date)::timestamp without time zone) = '1'::double precision)
           ->  Bitmap Index Scan on weather_month_idx  (cost=0.00..12.00 rows=496 width=0)
                 Index Cond: (date_part('month'::text, (observation_date)::timestamp without time zone) = '1'::double precision)
        (4 rows)
        

Теперь планировщик справляется с оценкой первой части условия.

.......................................................................

Рассмотрим вторую часть условия:

        => explain select * from weather where temperature >= 0;
                                 QUERY PLAN                          
        -------------------------------------------------------------
         Seq Scan on weather  (cost=0.00..102.05 rows=2893 width=12)
           Filter: (temperature >= 0)
        (2 rows)
        

Ожидается примерно 1/2 часть строк - здесь тоже оценка нормальная.

.......................................................................

Но что с итоговой селективностью?

        => explain select * from weather where extract(month from observation_date) = 1 and temperature >= 0;
                                                               QUERY PLAN                                                        
        -------------------------------------------------------------------------------------------------------------------------
         Bitmap Heap Scan on weather  (cost=12.06..50.98 rows=245 width=12)
           Recheck Cond: (date_part('month'::text, (observation_date)::timestamp without time zone) = '1'::double precision)
           Filter: (temperature >= 0)
           ->  Bitmap Index Scan on weather_month_idx  (cost=0.00..12.00 rows=496 width=0)
                 Index Cond: (date_part('month'::text, (observation_date)::timestamp without time zone) = '1'::double precision)
        (5 rows)
        

Парадоксально, но после того, как мы внесли исправления, оценка только
ухудшилась, причем сильно.

.......................................................................

Дело в том, что итоговая селективность рассчитывается как произведение
селективностей подусловий, то есть их взаимосвязь не принимается
во внимание.

К сожалению, пока в PostgreSQL нет возможности учитывать корреляцию
предикатов, так что подобных запросов следует избегать. Но иногда
дело может спасти уже известный индекс, построенный по двум полям:

        => create index weather_array_idx on weather((
        =>   array[ extract(month from observation_date), temperature ]
        => ));
        CREATE INDEX

        => analyze weather;
        ANALYZE

.......................................................................

Чтобы такая статистика учлась оптимизатором, запрос надо переписать:

        => explain select * from weather
        => where array[extract(month from observation_date),temperature]
        =>   between array[1::double precision,0]
        =>       and array[1::double precision,100];
                                                                                                                                                                 QUERY PLAN                                                                                                                                                          
        -----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
         Index Scan using weather_array_idx on weather  (cost=0.28..8.30 rows=1 width=12)
           Index Cond: ((ARRAY[date_part('month'::text, (observation_date)::timestamp without time zone), (temperature)::double precision] >= '{1,0}'::double precision[]) AND (ARRAY[date_part('month'::text, (observation_date)::timestamp without time zone), (temperature)::double precision] <= '{1,100}'::double precision[]))
        (2 rows)
        

Получили оценку в одну строку - это минимальная оценка, которую
в принципе дает планировщик.

.......................................................................

Попробуем заменить январь на июль:

        => explain select * from weather
        => where array[extract(month from observation_date),temperature]
        =>   between array[7::double precision,0]
        =>       and array[7::double precision,100];
                                                                                                                                                                    QUERY PLAN                                                                                                                                                             
        -----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
         Bitmap Heap Scan on weather  (cost=21.38..65.29 rows=497 width=12)
           Recheck Cond: ((ARRAY[date_part('month'::text, (observation_date)::timestamp without time zone), (temperature)::double precision] >= '{7,0}'::double precision[]) AND (ARRAY[date_part('month'::text, (observation_date)::timestamp without time zone), (temperature)::double precision] <= '{7,100}'::double precision[]))
           ->  Bitmap Index Scan on weather_array_idx  (cost=0.00..21.25 rows=497 width=0)
                 Index Cond: ((ARRAY[date_part('month'::text, (observation_date)::timestamp without time zone), (temperature)::double precision] >= '{7,0}'::double precision[]) AND (ARRAY[date_part('month'::text, (observation_date)::timestamp without time zone), (temperature)::double precision] <= '{7,100}'::double precision[]))
        (4 rows)
        

И эта оценка адекватна, точное значение:

        => select count(*) from weather where array[extract(month from observation_date),temperature] between array[7::double precision,0] and array[7::double precision,100];
         count 
        -------
           490
        (1 row)
        

.......................................................................

Можно улучшить оценки, увеличив параметр статистики. Для индекса это
можно сделать примерно так же, как и для таблицы:

        => alter index weather_array_idx alter "array" set statistics 300;
        ALTER INDEX

        => analyze weather;
        ANALYZE

Надо только учитывать, что имя "столбца" будет разным для разных
типов данных.

.......................................................................

Проверяем:

        => explain select * from weather where array[extract(month from observation_date),temperature] between array[7::double precision,0] and array[7::double precision,100];
                                                                                                                                                                    QUERY PLAN                                                                                                                                                             
        -----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
         Bitmap Heap Scan on weather  (cost=21.29..64.96 rows=489 width=12)
           Recheck Cond: ((ARRAY[date_part('month'::text, (observation_date)::timestamp without time zone), (temperature)::double precision] >= '{7,0}'::double precision[]) AND (ARRAY[date_part('month'::text, (observation_date)::timestamp without time zone), (temperature)::double precision] <= '{7,100}'::double precision[]))
           ->  Bitmap Index Scan on weather_array_idx  (cost=0.00..21.17 rows=489 width=0)
                 Index Cond: ((ARRAY[date_part('month'::text, (observation_date)::timestamp without time zone), (temperature)::double precision] >= '{7,0}'::double precision[]) AND (ARRAY[date_part('month'::text, (observation_date)::timestamp without time zone), (temperature)::double precision] <= '{7,100}'::double precision[]))
        (4 rows)
        

.......................................................................

Конец демонстрации.

.......................................................................

        => \q
