Эта статья написана по докладу Максима Старкова "Особенности определения селективности" на конференции PG BootCamp Russia 2025, которая прошла в апреле в Екатеринбурге. Доклад можно просмотреть, скачать презентацию, патч к докладу выложен здесь. Технически доклад довольно сложен, рассматривается в нём сразу несколько тем: алгоритм вычисления стоимости индексного доступа с точки зрения разработчика, проблема вычисления селективности при использовании предиката с несколькими условиями, проблема неиспользования расширенной статистики с параметризованным индексным доступом (parameterized scan), а также описывается патч, который позволяет её использовать. Каждая из этих тем сама по себе обширна и заслуживает отдельной статьи, мы же заострим внимание только на одной из заявленных проблем.
Суть проблемы: имеется несколько индексов с одинаковыми ведущими столбцами, выбирается не лучший индекс, и время выполнения запроса увеличивается на порядки. Такие индексы встречаются в сложных приложениях, но чаще всего в 1С:ERP, поскольку это приложение наиболее распространено. Как это обычно бывает: после миграции приложения на СУБД PostgreSQL часть запросов начинает выполняться медленнее. Планировщик выбирает индекс, созданный по меньшему числу столбцов, время выполнения увеличивается, потому что при использовании такого индекса индексные записи указывают на строки таблицы, которые не соответствуют условиям соединения. При выборе же индекса по большему числу задействованных в запросе столбцов время выполнения существенно снижается и практически не зависит от размера таблиц.
Создание таблиц для теста
Для упрощения тестирования создан запрос, две таблицы и два составных индекса на таблицу с большим числом строк.
drop table if exists wide_table;
create table wide_table (
c1 int not null, c2 int not null, c3 int not null, c4 int not null,
c5 int not null, c6 int not null, c7 int not null, c8 int not null,
c9 int not null, c10 int not null, c11 char(1000) not null,
c12 char(1000) not null);
insert into wide_table select
i % 3 as c1,
(i + 1) % 101010 as c2,
(i + 2) % 10101 as c3,
(i + 3) % 5 as c4,
(i + 4) % 13 as c5,
(i + 5) % 17 as c6,
(i + 6) % 19 as c7,
(i) as c8,
(i + 10) as c9,
(i + 20) as c10,
'FOO' as c11,
'BAR' as c12
from generate_series(1,1000000) as i;
-- Create wide unique index
create unique index idx_wide on
wide_table ( c1, c2, c3, c4, c5, c6, c7, c8, c11, c12);
-- Create narrow non-unique index
create index idx_narrow on wide_table (c1, c2, c3);
-- Analyze table
analyze wide_table;
vacuum wide_table;
-- Create table to store some of the data from the wide_table
drop table tt1;
create table tt1 (
c1 int not null, c2 int not null, c3 int not null, c4 int not null,
c5 int not null, c6 int not null, c7 int not null, c8 int not null,
c9 int not null, c10 int not null,
c11 char(1000) not null, c12 char(1000) not null);
-- Fill table with a random sample from the wide_table
insert into tt1 select c1, c2, c3, c4, c5, c6,
c7, c8, c9, c10, c11, c12 from wide_table
order by random()
limit 1000;
-- Analyze table
analyze tt1;
vacuum wide_table;
\timing on \\
\pset pager off \\В докладе таблица tt1 была временной, но это несущественно — проблема одинаково проявляется с таблицами любого типа. В докладе в таблице wide_table строк было 500 тысяч, однако при таком количестве разница во времени выполнения запросов заметна не на всех процессорах. Поэтому берем один миллион.
Зачем создавать второй индекс idx_narrow, если уже есть индекс idx_wide с теми же столбцами? Дело в том, что пример упрощён: в реальной системе в узком индексе присутствовали другие столбцы, и оба индекса эффективно обслуживали запросы, для которых они были созданы. Другими словами, удалить узкий индекс означало бы замедлить выполнение других запросов. Из-за общих ведущих столбцов в обоих индексах возникала проблема с запросом, пример которого будет приведён далее.
Познакомимся с объектами, чтобы представлять себе объёмы обрабатываемых данных. Размер таблицы — 1 116 Мб:
postgres=# \dt+ wide*
List of relations
Schema | Name | Type | Owner | Persistence | Access method | Size | Description
--------+------------+-------+----------+-------------+---------------+---------+-------------
public | wide_table | table | postgres | permanent | heap | 1116 MB |Размеры индексов:
postgres=# \di+ idx*
List of relations
Schema | Name | Type | Owner | Table | Persistence | Access method | Size | Description
--------+------------+-------+----------+------------+-------------+---------------+----------+-------------
public | idx_narrow | index | postgres | wide_table | permanent | btree | 10080 kB |
public | idx_wide | index | postgres | wide_table | permanent | btree | 108 MB |Индекс по 10 столбцам занимает 108 Мб, что составляет 9.6% от размера таблицы. Индекс по 3 столбцам занимает 0.88% от размера таблицы. Можно предположить, что при использовании индекса размером 108 Мб планировщик предположит, что придётся читать больше блоков и записей этого индекса, чем при использовании индекса размером в 10 раз меньше.
Тестовый запрос:
explain (analyze, buffers, timing off) select
t1.c1, t1.c2, t1.c3, t1.c4, t1.c5, t1.c6, t1.c7,
t1.c8, t1.c9 + t2.c9, t1.c10 + t2.c10, t1.c11,
t1.c12 from wide_table as t1
inner join tt1 as t2 on t1.c1 = t2.c1 and t1.c2 = t2.c2
and t1.c3 = t2.c3 and t1.c4 = t2.c4 and t1.c5 = t2.c5 and t1.c6 = t2.c6
and t1.c7 = t2.c7 and t1.c8 = t2.c8 and t1.c11 = t2.c11 and t1.c12 = t2.c12
where t1.c11 = 'FOO';В соединении и условии WHERE (столбец с11) используются все 10 столбцов, по которым создан индекс idx_wide. При выполнении запроса может использоваться любой из двух созданных на таблицу wide_table индексов.
Запрос с использованием индекса по меньшему числу столбцов
Выполним запрос несколько раз (до 10) на ванильной версии PostgreSQL и возьмём минимальное время (максимально возможную скорость выполнения запроса). При использовании индекса idx_narrow на таблице с 1 миллионом строк время составило 16,548 мс.
План тестового запроса:
Nested Loop (cost=0.42..7482.50 rows=1 width=1069) (actual rows=1000 loops=1)
Buffers: shared hit=8458
-> Seq Scan on tt1 t2 (cost=0.00..155.50 rows=1000 width=1069) (actual rows=1000 loops=1)
Filter: (c11 = 'FOO'::bpchar)
Buffers: shared hit=143
-> Index Scan using idx_narrow on wide_table t1 (cost=0.42..7.32 rows=1 width=1069) (actual rows=1 loops=1000)
Index Cond: ((c1 = t2.c1) AND (c2 = t2.c2) AND (c3 = t2.c3))
Filter: ((c11 = 'FOO'::bpchar) AND (t2.c4 = c4) AND (t2.c5 = c5) AND (t2.c6 = c6) AND (t2.c7 = c7) AND (t2.c8 = c8) AND (t2.c12 = c12))
Rows Removed by Filter: 4
Buffers: shared hit=8315
Planning Time: 0.257 ms
Execution Time: 15.917 ms
(12 rows)
Time: 16,548 msЗапрос с использованием индекса по большему числу столбцов
Посмотрим, какое время выполнения будет при использовании «широкого» индекса — то есть того, у которого в запросе задействовано больше столбцов, то есть лучше "покрывающего" запрос. Запретим использование узкого индекса:
update pg_index set indisvalid = false where indexrelid::regclass = 'idx_narrow'::regclass;План тестового запроса:
Nested Loop (cost=0.42..8468.51 rows=1 width=1069) (actual rows=1000 loops=1)
Buffers: shared hit=4143
-> Seq Scan on tt1 t2 (cost=0.00..155.50 rows=1000 width=1069) (actual rows=1000 loops=1)
Filter: (c11 = 'FOO'::bpchar)
Buffers: shared hit=143
-> Index Scan using idx_wide on wide_table t1 (cost=0.42..8.31 rows=1 width=1069) (actual rows=1 loops=1000)
Index Cond: ((c1 = t2.c1) AND (c2 = t2.c2) AND (c3 = t2.c3) AND (c4 = t2.c4) AND (c5 = t2.c5) AND (c6 = t2.c6) AND (c7 = t2.c7) AND (c8 = t2.c8) AND (c11 = 'FOO'::bpchar) AND (c12 = t2.c12))
Buffers: shared hit=4000
Planning Time: 0.240 ms
Execution Time: 12.350 ms
(10 rows)
Time: 12,939 msВремя выполнения запроса при использовании широкого индекса уменьшилось: с 16,548 ms до 12,939 ms. Чем отличаются планы, кроме времени выполнения?
Используются разные индексы — idx_wide и idx_narrow;
Отличается число считываемых буферов: shared hit=4000 и shared hit=8315;
Разнится стоимость индексного доступа: cost=8.31 и cost=7.32.
Стоимость складывается из чтения листовых страниц индекса и табличных страниц.
Зависимость времени выполнения запроса от числа строк
При увеличении числа строк меняется стоимость индексного сканирования, время выполнения запроса, а для узкого индекса — число прочитанных буферов:
для 2 млн. строк в таблице:
Index Scan using idx_narrow (cost=0.43..7.68 rows=1) hit=13737 Time: 26,675 ms
Index Scan using idx_wide (cost=0.55..8.52 rows=1) hit=5000 Time: 13,858 msдля 5 млн. строк в таблице:
Index Scan using idx_narrow (cost=0.43..8.13 rows=1) hit=38147 Time: 76,406 ms
Index Scan using idx_wide (cost=0.56..8.57 rows=1) hit=5000 Time: 14,390 msдля 20 млн. строк в таблице:
Index Scan using idx_narrow(cost=0.44..8.37 rows=1) Buffers: shared hit=101133 Time: 194,901 ms
Index Scan using idx_wide (cost=0.56..8.60 rows=1) Buffers: shared hit=5000 Time: 15,329 msдля 50 млн. строк в таблице:
Index Scan using idx_narrow (cost=0.56..8.56 rows=1) Buffers: shared hit=9538 read=243299 Time: 1837,796 ms
Index Scan using idx_wide (cost=0.56..8.61 rows=1) Buffers: shared hit=5000 Time: 15,493 msСтоимость доступа по узкому индексу растёт быстрее, чем по широкому, но даже при 50 млн строк она не сравнялась. Время выполнения при использовании узкого индекса больше, чем при использовании широкого, и при этом стоимость ниже. Вообще, стоимость должна быть прямо, а не обратно пропорциональна времени выполнения запроса. Такое расхождение указывает на ошибку в расчёте стоимости индексного доступа.
Время выполнения команды по широкому индексу почти не меняется.
При использовании узкого индекса число читаемых буферов растёт, и требуется увеличение размера буферного кэша, иначе выполнение запроса может замедлиться в несколько раз.
Хотя стоимость меняется, но при увеличении числа строк в таблице (то есть проиндексированных строк) стоимость доступа по узкому индексу не догнала стоимость доступа по широкому индексу. Есть расхождение между временем выполнения и стоимостью, а это значит, что формулы, по которым считается стоимость, имеют изъяны.
Использование широкого индекса, все ведущие столбцы которого задействованы в запросе, является более оптимальным по сравнению с узким индексом. Использование узкого индекса опасно тем, что при большом числе строк время выполнения запроса резко возрастает. В примере с 20 млн строк время выполнения увеличивается примерно на порядок. В случае с 50 млн строк размер буферного кэша уже перестал быть достаточным, и время выполнения запроса выросло более чем в 100 раз (на два порядка).
На СУБД Tantor Postgres SE 17.5, благодаря патчу Максима Старкова, выбирается широкий индекс.
Nested Loop (cost=0.42..8480.51 rows=1 width=1074) (actual rows=1000 loops=1)
Buffers: shared hit=4143
-> Seq Scan on tt1 t2 (cost=0.00..155.50 rows=1000 width=1074) (actual rows=1000 loops=1)
Filter: (c11 = 'FOO'::bpchar)
Buffers: shared hit=143
-> Index Scan using idx_wide on wide_table t1 (cost=0.42..8.33 rows=1 width=1074) (actual rows=1 loops=1000)
Index Cond: ((c1 = t2.c1) AND (c2 = t2.c2) AND (c3 = t2.c3) AND (c4 = t2.c4) AND (c5 = t2.c5) AND (c6 = t2.c6) AND (c7 = t2.c7) AND (c8 = t2.c8) AND (c11 = 'FOO'::bpchar) AND (c12 = t2.c12))
Buffers: shared hit=4000
Planning Time: 0.779 ms
Execution Time: 12.238 ms
(10 rows)
Time: 13.469 msПатч Максима Старкова сложнее патча, созданного для доклада: он содержит 750 строк, и для его работы не требуется расширенная статистика. Принцип работы патча заключается в том, что планировщик при выборе пути индекса корректирует выбор индекса с учетом лучшей селективности для перебираемых индексов, но только в случае, если:
ключи индексов таких путей непрерывно и последовательно покрывают предикаты соединения и/или отбора, а все такие предикаты используют только оператор "=";
индексы параметризованы одинаковым количеством соединяемых таблиц и их предикатов.
При таких условиях стоимостная оценка становится менее важной — индексы будут сравниваться по их селективности. Индекс с лучшей селективностью получит приоритет.
Подсчёт стоимости индексного доступа
В докладе приводится пример вычисления стоимости индексного доступа. Формула расчёта есть в исходном коде в функции btcostestimate(..) файла selfunc.c
В стоимость входят:
1) Index leaf pages cost — стоимость обращения к листовым блокам индекса и применения предикатов (в плане Index Cond). Учитываются IO и CPU.
Формулы и пример расчёта стоимости могут быть полезны для локализации того, в какой части ошибается планировщик и возможно ли исправить это с помощью параметра конфигурации, используемого в формуле.
Составляющая IO — число листовых страниц индекса — вносит наибольшую разницу в вычисление стоимости индексного доступа при выборе узкого и широкого индексов.
indexSelectivity * relpages * num_scans (в примере=1000) * random_page_costСоставляющая CPU:
reltuples * cpu_operator_cost + cpu_index_tuple_costeffective_cache_size учитывается, но изменение этого параметра не повлияет на выбор индекса.
2) Index traversal (descent) cost — стоимость прохода по дереву индекса до листовых блоков. Зависит от числа уровней индекса. Поскольку промежуточных блоков в индексе обычно существенно меньше, чем листовых, то IO не подсчитывается, учитывается только CPU.
ceil(log(строк в индексе) / log(2.0)) * cpu_operator_cost;плюс
(level + 1) * (DEFAULT_PAGE_CPU_MULTIPLIER=50) * cpu_operator_cost;Число уровней индекса для 1 млн. записей у широкого индекса 4 (level=3), у узкого 3 (level=2):
create extension if not exists pageinspect;
select fastroot,level from bt_metap('idx_wide');
select fastroot,level from bt_metap('idx_narrow');
fastroot | level
----------+-------
19615 | 3
fastroot | level
----------+-------
290 | 2Нумерация уровней начинается с нуля, поэтому при доступе к листовому блоку считывается level+1 блоков индекса. Число уровней растёт медленно. Эта составляющая вносит совсем небольшой вклад в общую стоимость плана запроса.
3) Heap pages cost — стоимость обращения к блокам таблицы и сравнения значений полей таблицы, которые не входят в индекс, но присутствуют в WHERE. Учитываются IO и CPU.
В докладе на 500 тысяч строк cost=6.93 для узкого индекса и cost=8.17 для широкого. Приведённые части внесли такой вклад в стоимость:
По картинке видно, что наибольший вклад в стоимость вносит доступ к блокам (IO cost). Index leaf pages cost соответствует реальности, так как в широком индексе больше листовых блоков. В Heap pages cost не учитываются дополнительные блоки таблицы, которые считываются при доступе к строкам с использованием узкого индекса.
Посмотрим сначала, что находится в листовых блоках обоих индексов.
Листовые блоки индексов
В записи листового блока широкого индекса хранится значение всех 10 ключевых столбцов. Широкий индекс уникален, поэтому сразу указывает на строку таблицы. При доступе по широкому индексу будет считан блок таблицы, чтобы проверить видимость строки, а также считаны значения столбцов, отсутствующих в индексе, но присутствующих в запросе.
\pset xheader_width column \\
Expanded header width is "column".
postgres=# select * from bt_page_items('idx_wide',100) offset 1 fetch next 1 rows only\gx
-[ RECORD 1 ]
itemoffset | 2
ctid | (129926,1)
itemlen | 104
nulls | f
vars | t
data | 00 00 00 00 8a 01 00 00 8b 01 00 00 01 00 00 00 07 00 00 00 05 00 00 00 10 00 00 00 ab e0 0d 00 7a 00 00 00 e8 03 00 00 f0 46 4f 4f 20 0f 01 ff 0f 01 ff 0f 01 ff 0f 01 9b 00 20 20 20 20 00 00 7a 00 00 00 e8 03 00 00 f0 42 41 52 20 0f 01 ff 0f 01 ff 0f 01 ff 0f 01 9b 00 20 20 20 20 00 00
dead | f
htid | (129926,1)
tids |В столбце data хранится значение 10 столбцов в строке таблицы. В столбце ctid хранится ссылка на блок таблицы (129926) и через запятую адрес строки в блоке (1).
Оговорка про многоверсионность. В индексе могут быть ссылки на мёртвые строки, но то же самое будет в узком индексе. При обновлении строки таблицы ссылка на новую версию строки будет вставлена в оба индекса. Поэтому многоверсионность увеличивает трудоемкость поиска по обоим индексам одинаково.
В узком индексе будут повторяющиеся значения. При дедуплицировании в индексе хранится массив ссылок на строки таблицы с одинаковыми значениями ключевых столбцов. Посмотрим, много ли их:
select * from bt_page_items('idx_narrow',100) offset 1 fetch next 1 rows only\gx
-[ RECORD 1 ]
itemoffset | 2
ctid | (24,8242)
itemlen | 328
nulls | f
vars | f
data | 00 00 00 00 48 19 00 00 49 19 00 00 00 00 00 00
dead | f
htid | (924,3)
tids | {"(924,3)","(15354,3)","(29784,3)","(44214,3)","(58644,3)","(73074,3)","(87504,3)","(101934,3)","(116364,3)","(130794,3)","(145224,3)","(159654,3)","(174084,3)","(188514,3)","(202944,3)","(217374,3)","(231804,3)","(246234,3)","(260664,3)","(275094,3)","(289524,3)","(303954,3)","(318384,3)","(332814,3)","(347244,3)","(361674,3)","(376104,3)","(390534,3)","(404964,3)","(419394,3)","(433824,3)","(448254,3)","(462684,3)","(477114,3)","(491544,3)","(505974,3)","(520404,3)","(534834,3)","(549264,3)","(563694,3)","(578124,3)","(592554,3)","(606984,3)","(621414,3)","(635844,3)","(650274,3)","(664704,3)","(679134,3)","(693564,3)","(707994,3)"}Взят случайный блок индекса с номером 100. Число листовых блоков на порядки превышает количество промежуточных (внутренних) блоков, поэтому с высокой вероятностью мы наталкиваемся на листовой блок. В столбце data хранится значение трёх столбцов, по которым создан индекс. В столбце tids хранятся ссылки на строки таблицы, в которых значения трёх проиндексированных столбцов одинаковы. Все эти блоки будут проверяться при индексном доступе. Блоков довольно много — 50. Будет сканироваться не меньше 50 блоков таблицы. Из-за этого число считываемых буферов при выполнении поиска по узкому индексу (для таблицы с 1 млн строк — Buffers: shared hit=8315) существенно больше, чем при использовании широкого — около 4000 буферов. Увеличение примерно в 2 раза, что, конечно, лучше, чем в 50 раз.
Проблема узкого индекса в том, что с увеличением числа строк в таблице растёт количество блоков, которые нужно прочитать при его использовании. Это, в свою очередь, увеличивает время выполнения команды. Более того, все прочитанные блоки будут считаны в буферный кэш.
При использовании же узкого индекса число блоков и время выполнения почти не увеличиваются.
В начале статьи приводился пример:
для 2 млн строк в таблице:
Index Scan using idx_narrow Buffers: shared hit=13737 Time: 26,675 ms
Index Scan using idx_wide Buffers: shared hit=5000 Time: 13,858 ms
для 5 млн:
Index Scan using idx_narrow Buffers: shared hit=38147 Time: 76,406 ms
Index Scan using idx_wide Buffers: shared hit=5000 Time: 14,390 ms
для 20 млн:
Index Scan using idx_narrow Buffers: shared hit=101133 Time: 194,901 ms
Index Scan using idx_wide Buffers: shared hit=5000 Time: 15,329 ms
Buffers: shared 101133 считанных блоков это 790Мб в буферном кэше. Для этого запроса пришлось увеличить буферный кэш с 128Мб до 1Гб. Без увеличения время выполнения запроса было бы гораздо больше.
для 50 млн строк в таблице:
Index Scan using idx_narrow Buffers: shared hit=9538 read=243299 Time: 1837,796 ms
Index Scan using idx_wide Buffers: shared hit=5000 Time: 15,493 ms
Для 50 млн строк не хватило буферного кэша размером в 1 Гб.В начале статьи приводился пример:
для 2 млн. строк в таблице:
Index Scan using idx_narrow Buffers: shared hit=13737 Time: 26,675 ms
Index Scan using idx_wide Buffers: shared hit=5000 Time: 13,858 msдля 5 млн.:
Index Scan using idx_narrow Buffers: shared hit=38147 Time: 76,406 ms
Index Scan using idx_wide Buffers: shared hit=5000 Time: 14,390 msдля 20 млн.:
Index Scan using idx_narrow Buffers: shared hit=101133 Time: 194,901 ms
Index Scan using idx_wide Buffers: shared hit=5000 Time: 15,329 msBuffers: shared 101133 считанных блоков это 790Мб в буферном кэше. Для этого запроса пришлось увеличить буферный кэш с 128Мб до 1Гб. Без увеличения время выполнения запроса было бы гораздо больше.
для 50 млн. строк в таблице:
Index Scan using idx_narrow Buffers: shared hit=9538 read=243299 Time: 1837,796 ms
Index Scan using idx_wide Buffers: shared hit=5000 Time: 15,493 msДля 50 млн строк не хватило буферного кэша размером в 1 Гб.
Heap pages cost
Стоимость Heap pages cost одинакова для обоих индексов, а это неверно. В этой части должны учитываться блоки таблицы, которые считываются при выполнении запроса. Для широкого индекса стоимость верна, поскольку каждая запись индекса ссылается на одну строку таблицы. Для узкого индекса не учитывается, что запись узкого индекса может ссылаться на десятки строк, находящихся в десятках блоков таблицы.
В докладе на слайдах 22–24 приводится формула расчета этой части стоимости — она сложна, и нет смысла её приводить. В неё входят селективность, число строк в таблице и параметр конфигурации random_page_cost, не влияющий на выбор узкого или широкого индекса. Корреляция pg_stats.correlation не влияет на выбор индекса, так как ведущие столбцы обоих индексов одинаковы. Единственное, что сможет повлиять на выбор индекса — селективность, она будет разной для узкого и широкого индексов.
Если в формулу подставить реальную селективность условий соединения строк, то стоимость для широкого индекса не изменится, а для узкого индекса — увеличится на 14.4648:
Патч в статье добавляет оценку стоимости считывания дополнительных блоков таблицы при доступе по узкому индексу (+14.4648). При увеличении стоимости индексного сканирования по узкому индексу до 21.5 он не будет выбран, поскольку стоимость сканирования по широкому индексу составляет 8.1705.
В файле selfuncs.s есть предупреждение: "clauselist_selectivity() is easily fooled into computing a too-low selectivity estimate". Предупреждение даётся для предикатов в частичных индексах, но в общем случае оно верно для любых ситуаций, где много условий (предикатов), соединённых оператором AND.
Спойлер
ANDing the index predicate with the explicitly given indexquals produces
a more accurate idea of the index's selectivity. However, we need to becareful not to insert redundant clauses, because clauselist_selectivity()is easily fooled into computing a too-low selectivity estimate. Ourapproach is to add only the predicate clause(s) that cannot be proven tobe implied by the given indexquals. This successfully handles cases suchas a qual "x = 42" used with a partial index "WHERE x >= 40 AND x < 50".There are many other cases where we won't detect redundancy, leading to atoo-low selectivity estimate, which will bias the system in favor of usingpartial indexes where possible.
В тестовом запросе 11 условий и вычисленная селективность на таблице с 500 тыс строк для широкого индекса 3e-20, для узкого — 3e-10. Числа запредельно низкие, поэтому предварительное (техническое) название доклада звучало как "Запредельная селективность".
Селективность AND вычисляется в функции clauselist_selectivity_ext(PlannerInfo..) файла clausesel.c
Если расширенная статистика отсутствует и зависимости не выявлены, селективности перемножаются, а перемножение 11 чисел даёт чрезвычайно низкую селективность. Пример для таблицы с миллионом строк:
select attname, correlation, n_distinct from pg_stats where tablename='wide_table';
attname | correlation | n_distinct
---------+-------------+------------
c1 | 1 | 3
c2 | 0.33610082 | 38708
c3 | 0.042892195 | 9640
c4 | 0.19834672 | 5
c5 | 0.086536884 | 13
c6 | 0.051232968 | 17
c7 | 0.046109326 | 19
c8 | 0.021048114 | -1
c9 | 0.021048114 | -1
c10 | 0.021048114 | -1
c11 | 1 | 1
c12 | 1 | 1Если перемножить обратные значения n_distinct, то получится огромное число 2e13 и запредельно низкая селективность 4e-14.
Реальное число уникальных значений по столбцам:
select count(distinct c1) c1_nd, count(distinct c2) c2_nd, count(distinct c3) c3_nd, count(distinct c4) c4_nd, count(distinct c5) c5_nd, count(distinct c6) c6_nd, count(distinct c7) c7_nd, count(distinct c8) c8_nd, count(distinct c9) c9_nd, count(distinct c11) c11_nd from wide_table;
c1_nd | c2_nd | c3_nd | c4_nd | c5_nd | c6_nd | c7_nd | c8_nd | c9_nd | c11_nd
-------+--------+-------+-------+-------+-------+-------+---------+---------+--------
3 | 101010 | 10101 | 5 | 13 | 17 | 19 | 1000000 | 1000000 | 1По второму столбцу статистика показывает число 38 708, тогда как в реальности значение составляет 101 010 (сто одна тысяча десять). Тема недооценки числа уникальных значений была раскрыта на этой же конференции PG BootCamp Russia 2025 Артемом Бугаенко (коллегой Максима Старкова). Ручная корректировка статистик (параметра n_distinct) приводилась также как пример в докладе Александра Никитина "Работа с запросами с точки зрения DBA".
В данном примере недооценка числа уникальных значений могла бы быть полезной, однако из-за перемножения селективностей даже значительная недооценка не повлияет на итоговую оценку.
Число уникальных значений по первым трем столбцам:
select count(1) idx_narrow_key_n_distinct from (select distinct c1, c2, c3 from wide_table);
idx_narrow_key_n_distinct
---------------------------
101010То есть при использовании узкого индекса селективность 1/101010 была бы более реалистичной. В докладе предлагается использовать расширенную статистику в соответствии с подходом, приведенным в комментарии к исходному коду PostgreSQL (/src/backend/optimizer/path/clausesel.c): «Базовый подход — сначала применять расширенную статистику к как можно большему числу выражений, чтобы учесть зависимости между столбцами и прочее. Оставшиеся выражения оценивать путём перемножения их селективностей, но это будет верно только для независимых условий, а в реальности условия НЕ являются независимыми, даже если относятся к одному и тому же столбцу. Поэтому мы хотим быть умнее везде, где это возможно».
Спойлер
The basic approach is to apply extended statistics first, on as manyclauses as possible,Расширенная статистика dependencies и ndistinct не работает при оценке селективности индексных сканирований, и патч из доклада добавляет такой функционал для расширенной статистики dependencies.in order to capture cross-column dependencies etc.The remaining clauses are then estimated by taking the product of theirselectivities, but that's only right if they have independentprobabilities, and in reality they are often NOT independent even if theyonly refer to a single column. So, we want to be smarter where we can.
Расширенная статистика dependencies и ndistinct не работает при оценке селективности индексных сканирований, и патч из доклада добавляет такой функционал для расширенной статистики dependencies.
