Об индексах на столбцах с низкой кардинальностью
Ранее среди коллег по СУБД бытовало мнение, что не стоит использовать B-tree индексы на столбцах с малым количеством уникальных значений. Считалось, что планировщик почти никогда не будет использовать такие индексы, поскольку дешевле последовательно прочитать всю таблицу, чем использовать случайное чтение (Disk I/O) на индексе, а затем переходить по указанному TID (Tuple ID) в таблицу. В случае, если необходимо прочитать сначала большую долю индекса, а потом большую долю таблицы, то дешевле сразу прочитать таблицу, чем выполнять двойную работу.
Сейчас же мои коллеги иногда предпочитают обложить все поля индексами и положиться на волю оптимизатора, который в нужных случаях будет использовать индексы, достигая тем самым ощутимого выигрыша или минимального проигрыша. На последнем ревью глаз зацепился за индекс на boolean-столбце и весь мой опыт был против такого решения. Но прежде, чем писать замечания я решил разобраться и обнаружил интересные особенности. Об этом и будет статья.
Поэтому, рассмотрим вопрос: как ведет себя B-tree индекс на столбцах с низкой кардинальностью и различными уровнями неравномерности распределения данных в аспекте эффективности выборки данных?
Вводная. Но зачем это нужно?
А для чего же нужно строить b-tree индекс по полю с низкой кардинальностью?
В своей работе при проектировании баз данных мы используем прием Soft Delete (мягкое удаление) — метод работы с данными в базах данных, при котором записи не удаляются из базы данных физически, а лишь помечаются как удалённые. Это позволяет сохранять данные для возможного восстановления в будущем или для аудита. Для этого в таблицу вводится поле is_deleted bool default False - флаг удаления строки. При необходимости удаления строки флаг перекидывается в True, а все запросы выборки используют предикат where is_deleted = True. При необходимости истории изменений строка дополняется полем deleted_at timestamp default now() - время удаления строки.
Противоположный подход - hard delete, когда данные физически удаляются из таблицы.
Преимущества Soft Delete:
Возможность восстановления данных,
Сохранение истории изменений,
Сохранение целостности ссылок (внешние ключи продолжают работать),
Упрощение аудита и отчётности.
Недостатки:
Усложнение структуры таблиц и увеличение размера базы данных,
Необходимость учитывать флаг удаления во всех запросах,
Возможные проблемы с производительностью.
В статье попробуем оценить, как измениться скорость выборки данных, если по полю is_deleted построить B-tree индекс. Для этого мы заполним поле различным распределением True/False, проведем замеры для случаев с индексом и без индекса и попробуем оценить результаты.
Индексный доступ в PostgreSQL
Индексный доступ - это способ быстрого поиска данных с использованием специальных структур (индексов), которые позволяют избежать полного сканирования таблицы. Для B-Tree индексов это означает использование сбалансированного дерева для организации данных.
Индекс – это структура, которая определяет соответствие значения ключа записи (атрибута или группы атрибутов) и физического расположения этой записи (TID). Каждый индекс связан с определенной таблицей, но при этом является внешним по отношению к таблице, обычно хранится отдельно от неё и является прозрачным по отношению к выборке данных (не влияет). Получение данных с помощью индекса затрачивает время состоящее из поиска по дереву + чтение нужной строки с диска.
B-Tree (Balanced Tree, сбалансированное дерево) дерево - это самобалансирующаяся древовидная структура данных. Некоторые свойства:
Позволяет выполнять поиск, вставку и удаление за логарифмическое время, O(log N),
Сохраняет данные отсортированными,
Остается сбалансированной при модификациях (все листья находятся на одном уровне),
Между ключами хранятся ссылки на дочерние узлы, листья дерева хранят ключ и ссылку на строку. В PostgreSQL используется B+ tree структура, которая отличается тем, что каждый лист хранит ссылку на следующий лист дерева.
Недостатки индексного доступа:
Замедляет операций изменения данных (INSERT, UPDATE, DELETE), так как требуется обновлять индексы;
Занимает дополнительное пространство на диске. Индексы увеличивают объём базы данных за счёт хранения вспомогательных структур, размер которых зависит от количества и типа индексируемых столбцов.
Антиподом к индексному поиску является полное сканирование таблицы (sequential scan) с диска или из буфера. Сложность - O(N).
Условия эксперимента
CPU: i5-1335U
Disk: SSD SAMSUNG MZAL41T0HBLB-00BLL
СУБД: PostgreSQL 16.9
Расширения:
pg_hint_plan
Настройки:
shared_buffers - 4 Гб
random_page_cost - 4
Создадим таблицу:
CREATE TABLE tbl_data (
AAA TEXT,
BBB TEXT,
CCC TEXT,
is_deleted bool DEFAULT false NOT NULL
);
CREATE INDEX idx_tmp_data_is_deleted ON public.tmp_data USING btree (is_deleted);
Будем заполнять таблицу случайными значениями, 50 млн строк. Строковые поля всегда будут длиной 10 символов, а при заполнения поля is_deleted будет варьироваться доля значений True от 0.01% до 99.99%. Размер индекса: 330 Мб, размер таблицы: 3.2 Гб
При итерациях будем очищать таблицу через TRUNCATE и затем выполнять VACUUM FULL + ANALYZE.
Измерения будем проводить для случаев без индекса и с индексом фильтруя по полю is_deleted. Запросы проводятся с прогревом кэша. Замеряем время выполнения запросов и стоимость (cost) запроса:
select /*+ IndexOnlyScan(t idx_tmp_data_is_deleted) */ count(1) from tbl_data t where t.is_deleted = true;
select /*+ SeqScan(t) */ count(1) from tbl_data t where t.is_deleted = true;
В статье мы не будем рассматривать частичные индексы. Хотя в реальной жизни логичнее использовать индекс только по значениям is_deleted = True, т. к. удаленные строки чаще всего не нужны в постоянной работе. Частичный индекс формально уменьшает размер занимаемого места на диске и теоретически должен снижать накладные расходы на чтение. (При подготовке статьи не удалось обнаружить ускорения поиска при использовании частичного индекса, но специально на данном вопросе не останавливался. Этот вопрос требует отдельного исследования. А вот уменьшение размера индекса было значительным, что согласуется с предположениями).
В статье мы не будем рассматривать вопросы параллельного доступа (При подготовке статьи обнаружил ускорение выполнение запросов при использовании параллелизма, хотя специально этот вопрос не исследовал)
Результаты измерений
Проводились измерения времени выполнения и стоимости запроса для диапазона значений распределения True/False в поле is_deleted от 0.01% до 99.99%
Рис 1.
По оси X отложена доля записей со значением True в поле is_deleted. По оси Y - время выполнения запроса (psql \timing).
Мы видим, что время выполнения запроса линейно растет при увеличении количества True в данных постепенно приближаясь к времени выполнения запроса работающего в режиме полного сканирования (Seq Scan). Индекс дает значительное ускорение в соотношении по времени выполнения. Рассчитаем ускорение, которое дает индекс к случаю без индекса, т.е. отношение "Без индекса" / "С индексом":
Рис 2.
В случае небольшого количества значений True применение индекса дает значительное ускорение, что согласуется с теорией. Для случая, когда искомых значений True больше выигрыш тоже есть. Для уменьшения масштаба рассмотрим график для "Доля True" > 5%:
Рис 3.
В случае, когда доля True составляет 99.99%, индекс ускоряет выполнение запроса почти в 1.4 раза, что достаточно много.
О работе планировщика
Рассмотрим план запроса с использованием индекса для случая 50% True:
explain (analyze, verbose, buffers, settings, format text) SELECT /*+ IndexOnlyScan(t idx_tbl_data_is_deleted) */ count(1) FROM tbl_data AS t where t.is_deleted = true;
Finalize Aggregate (cost=404176.00..404176.01 rows=1 width=8) (actual time=576.711..583.116 rows=1 loops=1)
Output: count(1)
Buffers: shared hit=21086
-> Gather (cost=404175.78..404175.99 rows=2 width=8) (actual time=576.566..583.094 rows=3 loops=1)
Output: (PARTIAL count(1))
Workers Planned: 2
Workers Launched: 2
Buffers: shared hit=21086
-> Partial Aggregate (cost=403175.78..403175.79 rows=1 width=8) (actual time=563.323..563.323 rows=1 loops=3)
Output: PARTIAL count(1)
Buffers: shared hit=21086
Worker 0: actual time=556.752..556.752 rows=1 loops=1
JIT:
Functions: 3
Options: Inlining false, Optimization false, Expressions true, Deforming true
Timing: Generation 0.407 ms, Inlining 0.000 ms, Optimization 0.130 ms, Emission 2.069 ms, Total 2.606 ms
Buffers: shared hit=7723
Worker 1: actual time=556.781..556.782 rows=1 loops=1
JIT:
Functions: 3
Options: Inlining false, Optimization false, Expressions true, Deforming true
Timing: Generation 0.399 ms, Inlining 0.000 ms, Optimization 0.115 ms, Emission 1.780 ms, Total 2.294 ms
Buffers: shared hit=5441
-> Parallel Index Only Scan using idx_tbl_data_is_deleted on public.tbl_data t (cost=0.56..377078.71 rows=10438827 width=0) (actual time=0.249..332.615 rows=8332717 loops=3)
Output: is_deleted
Index Cond: (t.is_deleted = true)
Heap Fetches: 59
Buffers: shared hit=21086
Worker 0: actual time=0.698..322.261 rows=9159480 loops=1
Buffers: shared hit=7723
Worker 1: actual time=0.029..341.285 rows=6447846 loops=1
Buffers: shared hit=5441
Settings: work_mem = '128MB'
Planning Time: 0.072 ms
JIT:
Functions: 11
Options: Inlining false, Optimization false, Expressions true, Deforming true
Timing: Generation 0.972 ms, Inlining 0.000 ms, Optimization 0.345 ms, Emission 5.689 ms, Total 7.006 ms
Execution Time: 583.344 ms
(39 rows)
Нас будет интересовать метод доступа к данным - Parallel Index Only Scan и параметр Heap Fetches.
Parallel Index Only Scan - это метод выполнения запроса в PostgreSQL, который производит сканирование только индекса без обращения к таблице на основе данных индекса, без необходимости обращаться к самой таблице (heap). Это возможно, когда все необходимые столбцы содержатся в индексе (в ключе).
Heap Fetches - количество строк, которые пришлось извлечь непосредственно из таблицы (heap), а не только из индекса.
План запроса без использования индекса для случая 50% True:
`explain (analyze, verbose, buffers, settings, format text) SELECT /*+ SeqScan(t) */ count(1) FROM tbl_data AS t where t.is_deleted = true;
Finalize Aggregate (cost=652094.37..652094.38 rows=1 width=8) (actual time=3295.404..3300.655 rows=1 loops=1)
Output: count(1)
Buffers: shared hit=417 read=416248
-> Gather (cost=652094.15..652094.36 rows=2 width=8) (actual time=3295.308..3300.634 rows=3 loops=1)
Output: (PARTIAL count(1))
Workers Planned: 2
Workers Launched: 2
Buffers: shared hit=417 read=416248
-> Partial Aggregate (cost=651094.15..651094.16 rows=1 width=8) (actual time=3285.027..3285.028 rows=1 loops=3)
Output: PARTIAL count(1)
Buffers: shared hit=417 read=416248
Worker 0: actual time=3282.244..3282.244 rows=1 loops=1
JIT:
Functions: 4
Options: Inlining true, Optimization true, Expressions true, Deforming true
Timing: Generation 0.238 ms, Inlining 32.262 ms, Optimization 10.816 ms, Emission 9.892 ms, Total 53.207 ms
Buffers: shared hit=121 read=135897
Worker 1: actual time=3277.699..3277.700 rows=1 loops=1
JIT:
Functions: 4
Options: Inlining true, Optimization true, Expressions true, Deforming true
Timing: Generation 0.332 ms, Inlining 48.248 ms, Optimization 10.815 ms, Emission 9.017 ms, Total 68.411 ms
Buffers: shared hit=163 read=137976
-> Parallel Seq Scan on public.tbl_data t (cost=0.00..624997.08 rows=10438827 width=0) (actual time=50.867..3053.389 rows=8332717 loops=3)
Output: aaa, bbb, ccc, is_deleted
Filter: t.is_deleted
Rows Removed by Filter: 8333849
Buffers: shared hit=417 read=416248
Worker 0: actual time=55.735..3049.628 rows=8160368 loops=1
Buffers: shared hit=121 read=135897
Worker 1: actual time=68.180..3052.262 rows=8290198 loops=1
Buffers: shared hit=163 read=137976
Settings: work_mem = '128MB'
Planning Time: 0.096 ms
JIT:
Functions: 14
Options: Inlining true, Optimization true, Expressions true, Deforming true
Timing: Generation 0.843 ms, Inlining 83.418 ms, Optimization 36.309 ms, Emission 30.031 ms, Total 150.601 ms
Execution Time: 3301.000 ms
(39 rows)
Time: 3302.107 ms (00:03.302)
Из плана запроса мы видим, что большая часть данных читалась с диска, что и привело к значительному увеличению времени выдачи по сравнению с вариантом использования индекса.
Особенности методов доступа к данным по индексу
Попробуем провести эксперимент по выборке данных, где True составляет 95% таблицы. Загрузим 50 млн записей и сразу же выполним запрос:
select count(1) from tbl_data t where t.is_deleted = false;
План запроса:
Finalize Aggregate (cost=1078406.12..1078406.13 rows=1 width=8)
-> Gather (cost=1078405.91..1078406.12 rows=2 width=8)
Workers Planned: 2
-> Partial Aggregate (cost=1077405.91..1077405.92 rows=1 width=8)
-> Parallel Seq Scan on tbl_data t (cost=0.00..1028006.55 rows=19759743 width=0)
Filter: (NOT is_deleted)
Время выполнения запроса: 0.793 с.
Оптимизатор проигнорировал индекс и выполнил полное сканирование таблицы.
Давайте попробуем заставить оптимизатор использовать индекс в наиболее эффективном режиме Index Only Scan. Для этого используем расширение pg_hint_plan и закрепим план запроса хинтом IndexOnlyScan:
select /*+ IndexOnlyScan(t idx_tbl_data_is_deleted) */ count(1) from tbl_data t where t.is_deleted = false;
Время выполнения: 1.022 с
План запроса:
Finalize Aggregate (cost=15287926.97..15287926.98 rows=1 width=8) (actual time=4860.161..4869.313 rows=1 loops=1)
Output: count(1)
-> Gather (cost=15287926.76..15287926.97 rows=2 width=8) (actual time=4860.008..4869.294 rows=3 loops=1)
Output: (PARTIAL count(1))
Workers Planned: 2
Workers Launched: 2
-> Partial Aggregate (cost=15286926.76..15286926.77 rows=1 width=8) (actual time=4842.191..4842.192 rows=1 loops=3)
Output: PARTIAL count(1)
Worker 0: actual time=4832.626..4832.627 rows=1 loops=1
JIT:
Functions: 3
Options: Inlining true, Optimization true, Expressions true, Deforming true
Timing: Generation 0.247 ms, Inlining 45.698 ms, Optimization 2.478 ms, Emission 3.991 ms, Total 52.415 ms
Worker 1: actual time=4834.112..4834.112 rows=1 loops=1
JIT:
Functions: 3
Options: Inlining true, Optimization true, Expressions true, Deforming true
Timing: Generation 1.046 ms, Inlining 33.225 ms, Optimization 2.506 ms, Emission 4.128 ms, Total 40.905 ms
-> Parallel Index Only Scan using idx_tbl_data_is_deleted on public.tbl_data t (cost=0.56..15237527.40 rows=19759743 width=0) (actual time=4.460..4419.006 rows=15832631 loops=3)
Output: is_deleted
Index Cond: (t.is_deleted = false)
Heap Fetches: 47497894
Worker 0: actual time=0.186..4397.416 rows=15986916 loops=1
Worker 1: actual time=0.115..4410.642 rows=15082848 loops=1
Не смотря на использование индекса и метода Index Only Scan мы получили замедление:
По времени выполнения: +29%, по стоимости (cost): 1417%.
Сразу после вставки или обновления данных в таблице план выполнения запроса может быть не оптимальным. Например, Index Scan увеличивает затраты на выполнение запроса по сравнению с Index Scan Only примерно на 30% (по времени выполнения) и на 1417% (по стоимости, cost).
Обратите внимание, что Карта видимости (Visibility Map) не заполняется при выполнении команды VACUUM, только процессом autovacuum.
Получение данных о последнем запуске autovacuum:
SELECT
schemaname, relname, n_dead_tup, n_live_tup, last_autovacuum, last_autoanalyze, autovacuum_count, round(n_dead_tup::float / n_live_tup::float * 100) AS dead_pct
FROM pg_stat_all_tables
WHERE relname = 'tbl_data';
Пример выполнения autovacuum:
db=# SELECT * FROM pg_stat_progress_vacuum;
pid | datid | datname | relid | phase | heap_blks_total | heap_blks_scanned | heap_blks_vacuumed | index_vacuum_count | max_dead_tuples | num_dead_tuples
-------+-------+---------+--------+---------------+-----------------+-------------------+--------------------+--------------------+-----------------+-----------------
38518 | 16388 | db | 204569 | scanning heap | 416667 | 76586 | 0 | 0 | 11184809 | 100
(1 row)
Time: 8.296 ms
Почему же так произошло? По идее, если индекс (размер 330 Мб) меньше таблицы (размер 6404 Мб), а СУБД получает сразу данные из индекса, то процесс должен выполняться заметно быстрее. Но в нашем случае это не так, в плане запроса мы видим: Heap Fetches: 47497894. Это говорит о том, что был использован индекс, а непосредственно данные выбирались из таблицы. Получилась двойная работа 95% строк таблицы.
Но почему же Index Only Scan ведет себя как Index Scan?
Index Only Scan быстрый, но достаточно капризный метод, при невыполнении ряда условий и он начинает работать как обычный Index Scan и для получения данных производит обращение к таблице (heap). Это происходит, когда страница помечена в карте видимости (Visibility Map) как недоступная. Если же страница помечена как доступная и установлен бит карты видимости данных, all-visible, то данные будут взяты из ключа индекса. В обратном случае, будет выполнена двойная работа - нужно произвести поиск в индексе, а затем "сходить" в таблицу (heap), что приводит к дополнительным накладным расходам.
Бит all-visible - показывает, что все строки на странице видимы всем транзакциям, то есть страница не содержит мертвых кортежей (tuples) и не требует очистки. Документация говорит ( https://postgrespro.ru/docs/postgresql/15/storage-vm ):
Биты карты видимости устанавливаются только при очистке, а сбрасываются при любых операциях, изменяющих данные на странице.
Planner/Optimizer и его оценки SQL-запросов
А что же с оценками самого планировщика Planner/Optimizer? Рассмотрим какие стоимостные оценки он давал при выполнении запросов:
Рис 4.
Видим линейный рост стоимости при работе по индексу и практически константное значение стоимости при работе без индекса, что верно - приходится сканировать таблицу целиком. В графике есть момент (пересечение линий, доля True = ~85%), когда стоимость выполнения запроса по Index Only Scan превышает стоимость по методу Seq Scan. Построим диаграмму методов доступа, когда планировщик сам выбирал метод доступа к данным, т. е. мы не использовали хинты SeqScan, IndexOnlyScan:
Рис 5.
Видно, что планировщик ошибается и переключается в режим Seq Scan для количества True >= 85%, хотя как следует из рис. 1, время выполнения запроса по индексу меньше не менее чем в 1.43 раза.
А что будет с планировщиком при различных размерах таблицы. Возьмем размеры от 100 строк до 100 млн строк и возьмем 2 соотношения True/False: 5% и 50% и посмотрим какой будет план выполнения запроса для случая "С индексом":
Рис 6.
Видно, что оптимизатор уверенно себя ведет в случае высокой уникальности значения True (5%) и начинает переключаться между методами доступа для низкой уникальности (50%).
Нужно обратить внимание, что во время эксперимента система работает на SSD дисках, а большинство настроек СУБД остались по умолчанию и имеют значения больше подходящие для механических HDD:
random_page_cost (default 4.0) - определяет стоимость (в условных единицах) случайного доступа к странице данных на диске. Он используется оптимизатором запросов для оценки стоимости различных планов выполнения. Значение 4 подходит для механических HDD, когда они создают эффект бутылочного горлышка. При работе с SSD рекомендуется [1] [2] снижать random_page_cost до 1.1–1.3 или даже ниже (0.5 для производительных SSD и 0.1 для NVMe).
seq_page_cost (default 1.0) - задаёт стоимость чтения одной страницы с диска (в условных единицах), которое выполняется в серии последовательных чтений. Рекомендуется снизить значение соответственно параметру random_page_cost сохранив соотношение random_page_cost / seq_page_cost ≈ 2–4 .
И еще один момент, сразу после массовых DML-операций скорость выполнения запросов будет еще менее предсказуемой - приходится ожидать несколько минут до выполнения autovacuum, иначе планировщик постоянно уходит в полное сканирование таблицы (SeqScan). Из-за этого в реальных случаях можно столкнуться с необъяснимым падением производительности. При этом, как говорил раньше, не стоит полагаться на VACUUM, т.к. обновление карты видимости происходит после autovacuum (см поле pg_stat_all_tables.last_autovacuum).
Выводы
При использовании архитектурного приема
Soft deleteв СУБД PostgreSQL имеет смысл строить B-Tree-индекс по полюis_deleted bool(в каждой конкретной реальной системе нужно учесть все факторы влияющие на производительность). Индекс желательно строить частичным по значению False:
CREATE INDEX idx_tbl_data_is_deleted ON tbl_data (is_deleted) WHERE is_deleted = false;
При работе системы на SSD-дисках нужно настроить константы стоимости для планировщика.
Для снижения вероятности ошибки планировщика после массовых изменений в таблицах нужно подобрать значения запуска
autovacuumиautoanalyzeв соответствии с реальными условиями: autovacuum_vacuum_threshold, autovacuum_vacuum_scale_factor, autovacuum_analyze_threshold, autovacuum_analyze_scale_factor.
Источники:
https://habr.com/ru/companies/postgrespro/articles/326096/
https://postgrespro.ru/docs/postgrespro/9.5/storage-vm
https://habr.com/ru/companies/tensor/articles/751458/
https://postgrespro.ru/docs/enterprise/current/pg-hint-plan
https://www.postgresql.org/docs/current/runtime-config-query.html
https://interface31.ru/tech_it/2020/03/optimizaciya-proizvoditel-nosti-postgresql-dlya-raboty-s-1spredpriyatie.html
danolivo
Не очень понимаю, какой смысл в таком индексе. Если имеется 2-5 значений в колонке, то эффективнее сделать частичный индекс на каждое значение (или группу). Это сильно ускорит выполнение, уберет лишние выражения из дерева запроса и упростит жизнь планировщику.