Число строк

Посмотрим на статистику на примере таблицы рейсов 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, где 

=> 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)

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

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