При создании индексов типа btree в PostgreSQL есть опции DESC и NULLS FIRST. В статье рассматривается как эти опции влияют на производительность и размер btree-индексов PostgreSQL.
По умолчанию индекс строится в возрастающем порядке (ASC), то есть в дереве индекса "слева" меньшие значения, "справа" большие. При создании индекса можно указать обратный порядок: DESC. Свойство ASC и DESC при создании индекса не влияет на эффективность использования индекса планировщиком (ORDER BY ASC или DESC). Это свойство влияет на заполнение индекса: правые блоки в индексе отличаются от остальных тем, что оптимизированы для вставок.
Тест: создание таблицы и индекса в прямом и обратном порядке сортировки:
\timing on \\
drop table if exists t3;
create table t3 (id bigserial, s int4) with (autovacuum_enabled=off, fillfactor=100);
create unique index if not exists t3_pkey on t3 using btree (id) include (s) with (fillfactor=100, deduplicate_items=off);
insert into t3 (s) select * from generate_series(1, 1000000);
select pg_relation_size('t3_pkey', 'main');
drop table if exists t3;
create table t3 (id bigserial, s int4) with (autovacuum_enabled=off, fillfactor=100);
create unique index if not exists t3_pkey on t3 using btree (id DESC nulls first) include (s) with (fillfactor=100, deduplicate_items=off);
insert into t3 (s) select * from generate_series(1, 1000000);
select pg_relation_size('t3_pkey', 'main');
..
INSERT 0 1000000
Time: 4351.432 ms (00:04.351)
pg_relation_size
------------------
28467200
..
INSERT 0 1000000
Time: 5740.328 ms (00:05.740)
pg_relation_size
------------------
56401920
Изменение порядка существенно повлияло на скорость вставки и размер индекса. Размер индекса увеличился в 2 раза. Время вставки увеличилось на треть: с 4351.432 ms до 5740.328 ms.
Перестроим индекс, созданный в убывающем порядке (DESC) и посмотрим уменьшится ли размер индекса:
reindex index t3_pkey;
select pg_relation_size('t3_pkey', 'main');
pg_relation_size
------------------
28475392
(1 row)
Time: 1077.214 ms (00:01.077)В примере fillfactor 100, так как более практичен для таблиц, в которых данные после вставки не меняются. Автовакуум отключён, чтобы не повлиял на результаты теста. Значения по умолчанию для в btree индексов и правила их применения:
90% для листовых блоков (BTREE_DEFAULT_FILLFACTOR)
70% для нелистовых блоков и это не меняется (BTREE_NONLEAF_FILLFACTOR)
96% при разделении любого листового блока, который полностью заполнен дубликатами, то есть одинаковым значением (BTREE_SINGLEVAL_FILLFACTOR).
Для листовых блоков fillfactor применяется:
во время построения индекса
при разделении крайней правой страницы как листового, так и промежуточных уровней. При разделении не самых правых страниц данные перераспределяются поровну между разделяемой и добавляемой страницами. В родительский блок вставляется ссылка на добавляемую страницу. Если в родительском блоке нет места, то он делится и так до корневого блока. Если в корневом блоке нет места, то добавляется новый уровень.
Размер индекса после перестройки уменьшился до размера аналогичного индексу, созданному в возрастающем порядке. Это значит, что при вставке строк в таблицу индекс в убывающем порядке обновлялся неэффективно. Обновления происходили в левых блоках индекса, которые не оптимизированы для вставок, в отличие от правых блоков индекса btree.
При вставке строк в таблицу значениями, которые попадают не в правый блок структура индекса заполняется неэффективно и вставки замедляются.
Причина же замедления вставок не столько в излишнем делении блоков, сколько в отсутствии оптимизации fastpath. Процесс, который выполнил вставку в правый листовой блок, запоминает ссылку на него и при последующей вставке, если новое значение больше предыдущего (или пусто) и не проходит путь от корня до листового блока. Оптимизация fastpath также используется при вставке в датавременной столбец, заполняемый по DEFAULT временем вставки. Процесс забывает адрес блока и снова начинает поиск с корня, если по какой-либо причине выполнил вставку (в индекс записи только вставляются, они не меняются, а удаляются только вакуумом) не в самый правый блок. Fastpath применяется при числе уровней в индексе 2 и больше.
Если бы таблица заполнялась убывающими значениями, то индекс DESC был бы эффективнее, чем ASC.
Опция NULLS FIRST
Индексы типа btree в PostgreSQL индексируют пустые значения. По умолчанию пустые значения сохраняются "справа" (в правых блоках индекса). Это можно переопределить указав NULLS FIRST.
При переопределении порядка, обычно исходят из того, что должно выдаваться преимущественно первым при сортировке, но серверный процесс скользит по блокам в обе стороны с одинаковой эффективностью.
Использование NULLS FIRST может повлиять на производительность: если при вставке строк в таблицу в индекс вставляется NULL (при вставке строки в таблицу значение индексированного столбца не задаётся, а обновляется позже и обновления распределены по времени, а не массовые), то оптимизация fastpath перестает работать, так как NULL будут в самом левом листовом блоке, а fastpath работает только с правым блоком. Вставки строк с NULL замедлятся при использовании NULLS FIRST. Если вставлять в таблицу примера строки с пустыми значениями, то деградация производительности будет ровно такая же, как при вставке возрастающих значений в индекс, созданный в убывающем порядке.
Если стоит задача улучшить производительность работы приложения, то можно добавить проверку: нет ли индексов с опциями DESC и NULLS FIRST. Также, если в таблице будет много пустых значений и искать с помощью индекса такие значения не нужно, то можно создать частичный индекс: чтобы пустые значения не индексировались.