# Число строк

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

    => SHOW default_statistics_target;

     default_statistics_target
    ---------------------------
     100
    (1 row)

Уменьшим его до 10 в целях демонстрации:

    => SET default_statistics_target = 10;

    SET

    => ANALYZE;

    ANALYZE

Поскольку при анализе таблицы учитывается 300*default_statistics_target строк, то оценки, как правило, не будут абсолютно точными.

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

    => EXPLAIN SELECT * FROM flights;

                               QUERY PLAN
    ----------------------------------------------------------------
     Seq Scan on flights  (cost=0.00..4564.67 rows=214867 width=63)
    (1 row)

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

    => SELECT count(*) FROM flights;

     count
    --------
     214867
    (1 row)

Оптимизатор получает значение из pg_class:

    => SELECT reltuples, relpages FROM pg_class WHERE relname = 'flights';

     reltuples | relpages
    -----------+----------
        214867 |     2416
    (1 row)

# Доля неопределенных значений

Часть рейсов еще не отправились, поэтому время вылета для них не определено:

    => EXPLAIN SELECT * FROM flights WHERE actual_departure IS NULL;

                              QUERY PLAN
    ---------------------------------------------------------------
     Seq Scan on flights  (cost=0.00..4564.67 rows=17261 width=63)
       Filter: (actual_departure IS NULL)
    (2 rows)

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

    => SELECT count(*) FROM flights WHERE actual_departure IS NULL;

     count
    -------
     16348
    (1 row)

Оценка оптимизатора получена как общее число строк, умноженное на долю NULL-значений:

    => SELECT 214867 * null_frac FROM pg_stats
      WHERE tablename = 'flights' AND attname = 'actual_departure';

        ?column?
    ----------------
     17260.98156064
    (1 row)

# Наиболее частые значения

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

    => EXPLAIN SELECT * FROM flights WHERE departure_airport = 'SVO';

                              QUERY PLAN
    ---------------------------------------------------------------
     Seq Scan on flights  (cost=0.00..5101.84 rows=19195 width=63)
       Filter: (departure_airport = 'SVO'::bpchar)
    (2 rows)

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

    => SELECT count(*) FROM flights WHERE departure_airport = 'SVO';

     count
    -------
     19347
    (1 row)

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

    => SELECT most_common_vals, most_common_freqs
      FROM pg_stats
      WHERE tablename = 'flights' AND attname = 'departure_airport' \gx

    -[ RECORD 1 ]-----+--------------------------------------------------------------------------------------
    most_common_vals  | {DME,SVO,VKO,LED,OVB,KJA,ROV,NUX,AER,BZK}
    most_common_freqs | {0.0986667,0.0893333,0.0543333,0.0533333,0.031,0.023,0.0203333,0.0193333,0.019,0.019}

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

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

    => SELECT 214867 * s.most_common_freqs[array_position((s.most_common_vals::text::text[]),'SVO')]
      FROM pg_stats s
      WHERE s.tablename = 'flights' AND s.attname = 'departure_airport';

        ?column?
    -----------------
     19194.785277836
    (1 row)

# Число уникальных значений

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

Например, в списке частых значений нет Владивостока.

    => EXPLAIN SELECT * FROM flights WHERE departure_airport = 'VVO';

                              QUERY PLAN
    --------------------------------------------------------------
     Seq Scan on flights  (cost=0.00..5101.84 rows=1323 width=63)
       Filter: (departure_airport = 'VVO'::bpchar)
    (2 rows)

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

    => SELECT count(*) FROM flights WHERE departure_airport = 'VVO';

     count
    -------
      1188
    (1 row)

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

    => SELECT sum(f) FROM pg_stats s, unnest(s.most_common_freqs) f
      WHERE s.tablename = 'flights' AND s.attname = 'departure_airport';

       sum
    ----------
     0.427333
    (1 row)

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

    => SELECT n_distinct
      FROM pg_stats s
      WHERE s.tablename = 'flights' AND s.attname = 'departure_airport';

     n_distinct
    ------------
            103
    (1 row)

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

    => SELECT 214867 * (1 - 0.427333) / (103 - 10);

           ?column?
    -----------------------
     1323.0886052580645161
    (1 row)

# Гистограмма

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

    => SELECT histogram_bounds
      FROM pg_stats s
      WHERE s.tablename = 'flights' AND s.attname = 'departure_airport';

                   histogram_bounds
    -----------------------------------------------
     {AAQ,CSY,HMA,KRO,MJZ,NOZ,PEE,SCW,TBW,ULY,YKS}
    (1 row)

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

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

    => EXPLAIN SELECT * FROM flights WHERE departure_airport < 'HMA';

                              QUERY PLAN
    ---------------------------------------------------------------
     Seq Scan on flights  (cost=0.00..5101.84 rows=53975 width=63)
       Filter: (departure_airport < 'HMA'::bpchar)
    (2 rows)

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

    => SELECT count(*) FROM flights WHERE departure_airport < 'HMA';

     count
    -------
     50972
    (1 row)

Как получена оценка?

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

    => SELECT sum( s.most_common_freqs[array_position((s.most_common_vals::text::text[]),v)] )
      FROM pg_stats s, unnest(s.most_common_vals::text::text[]) v
      WHERE s.tablename = 'flights' AND s.attname = 'departure_airport' AND v < 'HMA';

       sum
    ----------
     0.136667
    (1 row)

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

    => SELECT 214867 * (1 - 0.427333) * (2.0 / 10.0) + 214867 * 0.136667;

                 ?column?
    ----------------------------------
     53974.67634680000000000000000000
    (1 row)

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

# Расширенная статистика

Рассмотрим запрос с двумя условиями:

    => SELECT count(*)
      FROM flights
      WHERE flight_no = 'PG0007' AND departure_airport = 'VKO';

     count
    -------
       396
    (1 row)

Оценка оказывается сильно заниженной:

    => EXPLAIN SELECT *
      FROM flights
      WHERE flight_no = 'PG0007' AND departure_airport = 'VKO';

                                                    QUERY PLAN
    -----------------------------------------------------------------------------------------------------------
     Bitmap Heap Scan on flights  (cost=10.77..883.79 rows=17 width=63)
       Recheck Cond: (flight_no = 'PG0007'::bpchar)
       Filter: (departure_airport = 'VKO'::bpchar)
       ->  Bitmap Index Scan on flights_flight_no_scheduled_departure_key  (cost=0.00..10.77 rows=313 width=0)
             Index Cond: (flight_no = 'PG0007'::bpchar)
    (5 rows)

Причина в том, что планировщик полагается на то, что предикаты не коррелированы и считает общую селективность как произведение селективностей условий, объединенных логическим "и". Это хорошо видно в приведенном плане: оценка в узле Bitmap Index Scan (условие на flight_no) одна, а после фильтрации в узле Bitmap Heap Scan (условие на departure_airport) - другая.

Однако мы понимаем, что номер рейса однозначно определяет аэропорт отправления: фактически, второе условие избыточно (конечно, считая, что аэропорт указан правильно).

Начиная с версии PostgreSQL 10, это можно объяснить и планировщику с помощью статистики по функциональной зависимости:

    => CREATE STATISTICS flights1(dependencies)
      ON flight_no, departure_airport FROM flights;

    CREATE STATISTICS

    => ANALYZE flights;

    ANALYZE

    => EXPLAIN SELECT *
      FROM flights
      WHERE flight_no = 'PG0007' AND departure_airport = 'VKO';

                                                    QUERY PLAN
    -----------------------------------------------------------------------------------------------------------
     Bitmap Heap Scan on flights  (cost=10.82..878.93 rows=310 width=63)
       Recheck Cond: (flight_no = 'PG0007'::bpchar)
       Filter: (departure_airport = 'VKO'::bpchar)
       ->  Bitmap Index Scan on flights_flight_no_scheduled_departure_key  (cost=0.00..10.74 rows=310 width=0)
             Index Cond: (flight_no = 'PG0007'::bpchar)
    (5 rows)

Теперь оценка улучшилась.

Другая ситуация, в которой планировщик ошибается с оценкой, связана с группировкой:

    => SELECT count(*) FROM (
      SELECT DISTINCT departure_airport, arrival_airport FROM flights
    ) t;

     count
    -------
       618
    (1 row)

    => EXPLAIN SELECT DISTINCT departure_airport, arrival_airport FROM flights;

                                 QUERY PLAN
    ---------------------------------------------------------------------
     HashAggregate  (cost=5639.01..5745.10 rows=10609 width=8)
       Group Key: departure_airport, arrival_airport
       ->  Seq Scan on flights  (cost=0.00..4564.67 rows=214867 width=8)
    (3 rows)

Расширенная статистика позволяет исправить и эту оценку:

    => CREATE STATISTICS flights2(ndistinct)
      ON departure_airport, arrival_airport FROM flights;

    CREATE STATISTICS

    => ANALYZE flights;

    ANALYZE

    => EXPLAIN SELECT DISTINCT departure_airport, arrival_airport FROM flights;

                                 QUERY PLAN
    ---------------------------------------------------------------------
     HashAggregate  (cost=5639.01..5644.72 rows=571 width=8)
       Group Key: departure_airport, arrival_airport
       ->  Seq Scan on flights  (cost=0.00..4564.67 rows=214867 width=8)
    (3 rows)

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

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

    => SELECT * FROM pg_statistic_ext \gx

    -[ RECORD 1 ]---+-----------------------------------------
    stxrelid        | 16415
    stxname         | flights2
    stxnamespace    | 16385
    stxowner        | 10
    stxkeys         | 5 6
    stxkind         | {d}
    stxndistinct    | {"5, 6": 571}
    stxdependencies |
    -[ RECORD 2 ]---+-----------------------------------------
    stxrelid        | 16415
    stxname         | flights1
    stxnamespace    | 16385
    stxowner        | 10
    stxkeys         | 2 5
    stxkind         | {f}
    stxndistinct    |
    stxdependencies | {"2 => 5": 1.000000, "5 => 2": 0.015000}

# Статистика для индексов по выражению

Если в условиях используются обращения к функциям, планировщик не учитывает возможных значений. Например, рейсов, совершенных в январе, будет примерно 1/12 от общего количества:

    => SELECT count(*) FROM flights
      WHERE extract(month FROM scheduled_departure) = 1;

     count
    -------
     16831
    (1 row)

Однако планировщик не понимает смысла функции extract и использует фиксированную селективность 0,5%:

    => EXPLAIN SELECT * FROM flights
      WHERE extract(month FROM scheduled_departure) = 1;

                                           QUERY PLAN
    -----------------------------------------------------------------------------------------
     Gather  (cost=1000.00..5419.29 rows=1074 width=63)
       Workers Planned: 1
       ->  Parallel Seq Scan on flights  (cost=0.00..4311.89 rows=632 width=63)
             Filter: (date_part('month'::text, scheduled_departure) = '1'::double precision)
    (4 rows)

    => SELECT 214867 * 0.005;

     ?column?
    ----------
     1074.335
    (1 row)

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

    => CREATE FUNCTION get_month(t timestamptz) RETURNS integer AS $$
      SELECT extract(month FROM t)::integer
    $$ IMMUTABLE LANGUAGE SQL;

    CREATE FUNCTION

    => CREATE INDEX ON flights(get_month(scheduled_departure));

    CREATE INDEX

    => ANALYZE flights;

    ANALYZE

    => EXPLAIN SELECT * FROM flights
      WHERE get_month(scheduled_departure) = 1;

                                            QUERY PLAN
    ------------------------------------------------------------------------------------------
     Bitmap Heap Scan on flights  (cost=276.64..7035.71 rows=16545 width=63)
       Recheck Cond: (get_month(scheduled_departure) = 1)
       ->  Bitmap Index Scan on flights_get_month_idx  (cost=0.00..272.51 rows=16545 width=0)
             Index Cond: (get_month(scheduled_departure) = 1)
    (4 rows)

Оценка исправилась.

Статистика для индексов по выражению хранится вместе со статистикой для таблиц:

    => SELECT n_distinct FROM pg_stats WHERE tablename = 'flights_get_month_idx';

     n_distinct
    ------------
             12
    (1 row)

# Соединения

Селективность соединения - доля строк от декартового произведения двух таблиц. Рассмотрим пример:

    => EXPLAIN SELECT *
      FROM flights f JOIN aircrafts a ON a.aircraft_code = f.aircraft_code;

                                      QUERY PLAN
    ------------------------------------------------------------------------------
     Hash Join  (cost=1.20..59649.41 rows=214867 width=103)
       Hash Cond: (f.aircraft_code = ml.aircraft_code)
       ->  Seq Scan on flights f  (cost=0.00..4564.67 rows=214867 width=63)
       ->  Hash  (cost=1.09..1.09 rows=9 width=72)
             ->  Seq Scan on aircrafts_data ml  (cost=0.00..1.09 rows=9 width=72)
    (5 rows)

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

    => SELECT count(*)
      FROM flights f JOIN aircrafts a ON a.aircraft_code = f.aircraft_code;

     count
    --------
     214867
    (1 row)

"Базовая" формула для расчета селективности соединения (в предположении равномерного распределения) - минимальное из значений 1/nd1 и 1/nd2, где

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

    => SELECT s1.n_distinct, s2.n_distinct
      FROM pg_stats s1, pg_stats s2
      WHERE s1.tablename = 'flights' and s1.attname = 'aircraft_code'
        AND s2.tablename = 'aircrafts_data' and s2.attname = 'aircraft_code';

     n_distinct | n_distinct
    ------------+------------
              8 |         -1
    (1 row)

В данном случае получаем:

    => SELECT 214867 * 9 * least(1.0/8, 1.0/9);

              ?column?
    -----------------------------
     214866.99999999999999785133
    (1 row)

В более сложных случаях приведенная формула дала бы неправильный результат. Например, рейсы совершают разные модели самолетов с разной вместимостью, и для соединения рейсов с местами получили бы:

    => SELECT 214867 * 1339 * least(1.0/8, 1.0/8);

               ?column?
    -------------------------------
     35963364.12500000000000000000
    (1 row)

При этом точное значение:

    => SELECT count(*)
      FROM flights f JOIN seats s ON f.aircraft_code = s.aircraft_code;

      count
    ----------
     16518865
    (1 row)

Однако планировщик умеет учитывать списки наиболее частых значений и гистограммы, и получает практически точную оценку:

    => EXPLAIN SELECT *
      FROM flights f JOIN seats s ON f.aircraft_code = s.aircraft_code;

                                   QUERY PLAN
    ------------------------------------------------------------------------
     Hash Join  (cost=38.13..281145.22 rows=16803459 width=78)
       Hash Cond: (f.aircraft_code = s.aircraft_code)
       ->  Seq Scan on flights f  (cost=0.00..4564.67 rows=214867 width=63)
       ->  Hash  (cost=21.39..21.39 rows=1339 width=15)
             ->  Seq Scan on seats s  (cost=0.00..21.39 rows=1339 width=15)
    (5 rows)

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

    => SELECT count(*)
      FROM flights f
        JOIN aircrafts a ON a.aircraft_code = f.aircraft_code
        JOIN seats s ON a.aircraft_code = s.aircraft_code;

      count
    ----------
     16518865
    (1 row)

Однако теперь планировщик ошибается:

    => EXPLAIN SELECT *
      FROM flights f
        JOIN aircrafts a ON a.aircraft_code = f.aircraft_code
        JOIN seats s ON a.aircraft_code = s.aircraft_code;

                                      QUERY PLAN
    ------------------------------------------------------------------------------
     Hash Join  (cost=39.33..8417803.78 rows=31967435 width=118)
       Hash Cond: (f.aircraft_code = ml.aircraft_code)
       ->  Hash Join  (cost=38.13..281145.22 rows=16803459 width=78)
             Hash Cond: (f.aircraft_code = s.aircraft_code)
             ->  Seq Scan on flights f  (cost=0.00..4564.67 rows=214867 width=63)
             ->  Hash  (cost=21.39..21.39 rows=1339 width=15)
                   ->  Seq Scan on seats s  (cost=0.00..21.39 rows=1339 width=15)
       ->  Hash  (cost=1.09..1.09 rows=9 width=72)
             ->  Seq Scan on aircrafts_data ml  (cost=0.00..1.09 rows=9 width=72)
    (9 rows)

Причина в том, что, соединив первые две таблицы, планировщик не имеет детальной статистики о результирующем наборе строк.

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