ЧИСЛО СТРОК ~~~~~~~~~~~ Создадим БД и таблицу с неравномерно распределенными данными. Мы будем эмулировать наблюдения за температурой в течении нескольких лет. => 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.7 | -24 2 | -29 | -21.6 | -13 3 | -20 | -8.8 | 2 4 | -4 | 6.5 | 17 5 | 11 | 19.9 | 28 6 | 23 | 28.4 | 33 7 | 24 | 29.0 | 33 8 | 13 | 21.6 | 30 9 | -2 | 8.4 | 18 10 | -17 | -7.0 | 4 11 | -28 | -20.5 | -11 12 | -33 | -28.4 | -22 (12 rows) ....................................................................... Причем значения температуры встречаются с разной частотой: => select temperature, count(*) from weather where temperature >= 0 group by temperature order by temperature; temperature | count -------------+------- 0 | 68 1 | 71 2 | 65 3 | 64 4 | 69 5 | 64 6 | 56 7 | 46 8 | 65 9 | 71 10 | 60 11 | 83 12 | 54 13 | 82 14 | 69 15 | 76 16 | 72 17 | 60 18 | 81 19 | 85 20 | 83 21 | 100 22 | 97 23 | 103 24 | 102 25 | 122 26 | 132 27 | 166 28 | 176 29 | 137 30 | 156 31 | 104 32 | 102 33 | 22 (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=164 width=12) Filter: (temperature = 27) (2 rows) Точное значение: => select count(*) from weather where temperature = 27; count ------- 164 (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 | {-28,-27,28,27,-29,30,-26,29,-30,26,-25,25,-31,31,23,-21,24,32,-23,21,22,-24,-20,-19,19,-10,11,13,20,-22,18,-17,15,-16,-13,-32,-4,1,16,4,9,-15,14,-18,-12,-11,-8,0,8,-6,2,5,3,-7,-5,10,17,-3,-1,-14,6,12,-9,-2,7,-33,33} most_common_freqs | {0.0316564,0.0311431,0.0299452,0.028063,0.0265229,0.0261807,0.0256674,0.0234428,0.0231006,0.0220739,0.0208761,0.020705,0.0188227,0.017796,0.0176249,0.0172827,0.0172827,0.0171116,0.0169405,0.0169405,0.0165982,0.0157426,0.0150582,0.0145448,0.0145448,0.0143737,0.0142026,0.0138604,0.0138604,0.0135181,0.0135181,0.0130048,0.0126626,0.0124914,0.0123203,0.0121492,0.0121492,0.0121492,0.0121492,0.011807,0.011807,0.0116359,0.0116359,0.0114648,0.0114648,0.0114648,0.0114648,0.0112936,0.0111225,0.0109514,0.0109514,0.0109514,0.0107803,0.0106092,0.0106092,0.0102669,0.0102669,0.0100958,0.0100958,0.00975359,0.00941136,0.00924025,0.00855578,0.00838467,0.00787132,0.00427789,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? ---------- 164 (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 | {-28,-27,28,27,-29,30,-26,29,-30,26} most_common_freqs | {0.0316564,0.0311431,0.0299452,0.028063,0.0265229,0.0261807,0.0256674,0.0234428,0.0231006,0.0220739} => \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=74 width=12) Filter: (temperature = 0) (2 rows) Точное значение: => select count(*) from weather where temperature = 0; count ------- 66 (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.267796 (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? ------------------ 74.3251288599548 (1 row) ....................................................................... ГИСТОГРАММА ~~~~~~~~~~~ При условиях "больше" и "меньше" для оценки будет использоваться список наиболее частых значений, или гистограмма, или оба способа вместе. Гистограмма стоится так, чтобы не включать наиболее частые значения и null: => select histogram_bounds from pg_stats s where s.tablename = 'weather' and s.attname = 'temperature'; histogram_bounds -------------------------------------- {-33,-23,-19,-13,-6,0,7,13,19,24,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=844 width=12) Filter: ((temperature >= 0) AND (temperature <= 13)) (2 rows) Точное значение: => select count(*) from weather where temperature between 0 and 13; count ------- 910 (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? ------------------ 847.306469003484 (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 5991 => analyze notes; ANALYZE ....................................................................... Пример: => explain select * from weather w join notes n on (w.id = n.weather_id); QUERY PLAN -------------------------------------------------------------------------- Hash Join (cost=160.49..332.78 rows=5991 width=21) Hash Cond: (n.weather_id = w.id) -> Seq Scan on notes n (cost=0.00..89.91 rows=5991 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 ------- 5991 (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? ---------- 5991 (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=2869 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=243 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.39..65.33 rows=498 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.26 rows=498 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.24..64.76 rows=484 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.12 rows=484 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