В предыдущем уроке мы посчитали: высота B+tree-индекса для миллиарда строк — 4 уровня при fan-out 200. Но fan-out — не константа, это функция размера ключа. И есть две техники, которые радикально увеличивают этот fan-out: suffix truncation (Postgres 12+) и deduplication (Postgres 13+). Между ними индекс из 10 GiB может стать 3 GiB. На вопрос «почему мой prod-индекс на Postgres 11 такой большой, а на 13 такой маленький» — ответ здесь.

Internal-узлы: зачем им полный ключ

Вспомним: в B+tree internal-узлы содержат ключи-разделители. Если у тебя в листе L лежат ключи [Alice, Bob, Carol], а в листе R — [David, Eve], то в родительском узле достаточно одного ключа-разделителя, который скажет: «всё, что меньше или равно X, идёт в L; всё, что больше — в R». X может быть любым значением между Carol и David — например, Carol, или Cz, или даже D.

До

Suffix truncation: PG 12+

С Postgres 12 разделитель в internal-узле сокращается до минимального префикса, по которому можно однозначно разделить две дочерние страницы. Идея заимствована из академической литературы — в частности, из дизайна Bw-tree в Microsoft и из обычных оптимизаций B+tree, которые применялись в Oracle и SQL Server годами. Postgres дотянулся до них только в 12-й версии — это была одна из самых ожидаемых оптимизаций своего времени.

Конкретный пример. Допустим, в листе L последняя запись — 'Stephen', а в R первая — 'Thomas'. Минимальный префикс, по которому Postgres различит две страницы, — 'T' (одна буква). Полный ключ 'Stephen' (7 байт) ужимается до 'T' (1 байт). На многоколоночных индексах эффект ещё сильнее: вторая и далее колонки часто полностью обрезаются.

Что это даёт:

• Fan-out internal-узлов вырастает в разы, иногда на порядок (особенно для длинных текстовых ключей).
• Высота дерева уменьшается на один уровень для больших индексов.
• Меньше I/O при поиске: каждый Index Scan читает на одну страницу меньше.
• Buffer cache hit rate растёт: internal-узлы помещаются в RAM плотнее.

Важно: листья truncation не трогает — в них всё ещё хранится полный ключ, потому что лист нужен для возврата правильного TID и для возможной проверки качества кортежа.

Deduplication: PG 13+

Вторая оптимизация атакует другой случай: столбцы с большим числом дубликатов. Допустим, у тебя индекс по status в таблице из 100 миллионов заказов, и значений всего шесть: pending, paid, shipped, delivered, cancelled, refunded. До PG 13 каждое появление 'delivered' в листе занимало полные ~10-20 байт (ключ + TID + ItemId). На 100M строк и 6 значений получается ~16M записей каждого статуса × 20 байт = 320 MiB на статус, итого ~2 GiB только листьев — и это ещё без учёта internal-уровней.

В PG 13 появилась

В среднем для индекса с большим количеством дубликатов размер уменьшается в 2-3 раза. На многоколоночных индексах вида (low_cardinality_col, high_cardinality_col) — эффект скромнее, но всё ещё ощутим.

Deduplication автоматически выключается для:

• индексов с UNIQUE constraint (там по определению нет дубликатов);
• индексов по типам, для которых дедупликация не реализована (например, некоторые user-defined типы);
• индексов, где явно поставили WITH (deduplicate_items = off).

Posting list: формат внутри

Технически posting list — это один index tuple, у которого вместо одного t_tid хранится массив TID. В заголовке IndexTupleData.t_info поднят флаг INDEX_ALT_TID_MASK, который говорит «это posting tuple, а не обычный». За payload-частью следует массив ItemPointerData фиксированного размера (6 байт каждый).

Максимальный размер posting list ограничен BTreeTupleGetMaxHeapTIDOffset = 4096 TID (см. nbtree.h). Если дубликатов больше — Postgres хранит несколько posting tuples с одинаковым ключом (каждый до 4096 TID). На индексе с миллионом дубликатов получится ~250 posting tuples вместо миллиона обычных — всё ещё огромная экономия.

С точки зрения поиска posting list прозрачен: B-tree находит ключ как обычно, потом обходит массив TID и для каждого делает heap fetch (если не Index Only Scan).

Демонстрация: смотрим в pglite

Pglite основан на свежей версии Postgres, поэтому обе оптимизации включены по умолчанию. Создадим индекс по столбцу с большим количеством дубликатов и сравним размер с уникальным индексом.

Заметь: индекс по status (всего 6 значений на 100K строк) благодаря deduplication будет в разы меньше, чем индекс по id — несмотря на то, что в обоих случаях одинаковое число записей. До PG 13 оба индекса весили бы примерно одинаково.

Уровни оптимизации

Полезно представить иерархию того, что эти две оптимизации делают:

1. Размер ключа в листе. Это всегда полный ключ — ни suffix truncation, ни deduplication ничего не меняют на ключевом уровне в одиночных записях. Дедупликация лишь объединяет повторяющиеся ключи в posting list — но сам ключ один раз хранится полностью.

2. Размер ключа в internal. Здесь работает suffix truncation: ключ сокращается до минимального префикса. Эффект — рост fan-out.

3. Накладные расходы на entry в листе. Каждая запись = ItemId (4 байта) + IndexTupleData header (8) + ключ + TID (6) + alignment. Это ~20 байт минимум. Дедупликация уменьшает «эффективный» overhead на TID: вместо 20 байт на каждый дубликат — один общий ключ + 6 байт TID на каждый.

В сумме индекс становится 2-5x меньше на типовой OLTP-таблице. На индексах по low-cardinality колонках — до 10x.

Когда suffix truncation не работает

Suffix truncation — это внутрискоупная оптимизация: она применяется только в internal-узлах, при создании split’а или построении индекса с нуля (CREATE INDEX, REINDEX). Для существующего индекса, построенного на PG 11 и upgrade’нутого до PG 12, внутренние страницы не пересоздаются автоматически — нужно сделать REINDEX.

Это типичная ошибка миграции: «обновились с PG 11 на PG 14, ничего не поменялось». Правильный ответ — REINDEX CONCURRENTLY (см. урок 6), который пересоберёт индекс с применением всех оптимизаций.

Обрати внимание на Buffers: shared hit=N — для индекса с deduplication N будет значительно меньше, потому что листья компактнее.

Внутри Postgres: что меняется в коде

Если хочется заглянуть в исходники — реализация suffix truncation живёт в src/backend/access/nbtree/nbtutils.c, функция _bt_truncate(). Она вызывается во время split, когда нужно построить high_key. Логика грубо такая:

1. Берём последний live ключ старой страницы (после split) и первый ключ новой страницы.
2. Идём по колонкам слева направо.
3. Для каждой колонки сравниваем значения. Первая колонка, где значения различаются, — её сокращаем до минимального префикса, который различает значения.
4. Все следующие колонки (после первой различной) полностью отбрасываются.

Для текстовых полей «минимальный префикс» = байт, на котором различаются utf8-последовательности. Для целых чисел префикс не работает (надо хранить весь int), но в Postgres всё хранится по-байтно, и truncation просто отрежет хвост.

Реализация deduplication находится в nbtdedup.c, функция _bt_dedup_pass(). Срабатывает при «обычном» insert в лист — если перед split проверка показывает, что среди записей много одинаковых ключей, Postgres сначала пытается их объединить в posting list, и только потом, если места всё равно не хватает, делает split. Это типичная экономия: вместо split на каждые 10 одинаковых ключей — единая posting-list-запись.

Тонкости и подводные камни

1. Deduplication не помогает для UNIQUE-индексов. Это очевидно — там нет дубликатов. Но если у тебя композитный индекс (a UNIQUE, b), то по полному ключу дубликатов тоже нет, и dedup не сработает. А вот если ты переставишь столбцы — (b, a UNIQUE) — то по префиксу b будут дубликаты, и dedup включится. Это аргумент против naive-правила «всегда ставь UNIQUE-колонку первой».

2. На очень длинных дублирующихся ключах dedup идеален. Например, индекс по (text_column), где text_column — это длинный URL или JSON path. Длинный ключ × миллион повторений → сжатие в 5-10 раз.

3. Suffix truncation усложняет debug. Если ты используешь pg_visibility или pgstattuple и видишь, что internal-узлы выглядят странно — это нормально, там лежат обрезанные ключи. Реконструировать полный ключ можно только пройдя в лист.

4. fillfactor. По умолчанию для B-tree fillfactor = 90. То есть Postgres намеренно не заполняет страницы под завязку, чтобы оставить место под будущие inserts без split. Если у тебя append-only данные (sequence-PK), можно поставить fillfactor = 100 — индекс будет на 10% меньше. Если данные с частыми инсертами в середине — лучше оставить дефолт или даже понизить до 70-80.

5. Dedup ломается на разнотипных данных. Если ключ — это numeric с переменной точностью (например, '1.0' и '1.00' — разные на байтах, но равные семантически), Postgres не объединит их в posting list, потому что сравнение идёт по байтам. На практике это редкость, но при импорте из неоднородного источника может стрельнуть.

Влияние на write-нагрузку

Обе оптимизации не бесплатны на стороне записи:

• Suffix truncation добавляет CPU-цикл при каждом split (нужно вычислить минимальный префикс). Это микро-оптимизация, не заметная в overall throughput.
• Deduplication запускает _bt_dedup_pass перед split — тоже CPU. Но эта работа окупается тем, что split происходит реже (за счёт сжатия), и общий I/O меньше. Net effect — почти всегда положительный.

Только в одном сценарии deduplication потенциально ухудшает производительность: если у тебя высокий cardinality ключ (мало дубликатов) и высокий write rate. Тогда dedup делает бесполезную работу на каждом insert. Postgres адаптивно отключает dedup для конкретной страницы, если предыдущие попытки не дали выигрыша — это эвристика, заложенная в _bt_dedup_pass.

Если хочется явно отключить:

ALTER INDEX my_unique_idx SET (deduplicate_items = off);

или при создании:

CREATE INDEX my_idx ON t (col) WITH (deduplicate_items = off);

Это редко нужно, но удобно для бенчмарков, чтобы сравнить «до и после» на одном железе.

Бенчмарк: что говорят цифры

Реальные числа из community-бенчмарков и блогов Питера Гейгана:

• TPC-C benchmark, PK-индекс по order_line(o_w_id, o_d_id, o_id, ol_number): PG 11 → PG 13 размер сократился с 12 GiB до 7 GiB (≈40% экономии благодаря suffix truncation на 4-колоночном ключе).
• Индекс по low-cardinality колонке (~10 values, 100M rows): PG 12 → PG 13 размер сократился с 3.2 GiB до 0.6 GiB (≈80% экономии благодаря deduplication).
• Высота дерева на этом же индексе: было 4 уровня, стало 3 (один уровень меньше → -25% page reads на каждый поиск).

Эти цифры — типовые, не cherry-picked. На большинстве реальных индексов миграция PG 11/12 → PG 13/14 даёт уменьшение размера на 20-50%.

Совместимость и pg_upgrade

При major upgrade (pg_upgrade с PG 11 на PG 14, например) индексы не переписываются — они остаются в том формате, в котором были созданы. Это сделано осознанно: pg_upgrade должен работать за секунды, а не часы, и его задача — обновить только системный каталог, а не данные.

Что это значит на практике:

• На pre-PG-12 индексах не работает suffix truncation: internal-узлы такие же, как были.
• На pre-PG-13 индексах не работает deduplication: листья хранят дубликаты как обычные entries.
• Размер индекса после pg_upgrade — тот же, что был.

Чтобы получить оптимизации, нужно REINDEX (см. урок 6, желательно REINDEX CONCURRENTLY). В команде admin’а после upgrade пишут отдельный скрипт, который проходит по всем pg_class.relkind = 'i' и делает CONCURRENTLY реиндекс. На больших БД это растянуто на дни — реиндексят по таблице за раз в часы низкой нагрузки.

Альтернатива: дамп через pg_dump + restore. Тогда индексы пересоздаются с нуля и получают все оптимизации. Минус — даунтайм на время dump/restore, который на терабайтных БД нереалистичен.

DESC и NULLS FIRST

Полезный side-note: B-tree поддерживает любые комбинации ASC/DESC и NULLS FIRST/LAST в определении индекса:

CREATE INDEX orders_date_desc_idx ON orders (placed_at DESC NULLS LAST);

Зачем? Потому что range scan по индексу идёт в порядке индекса. Если самые горячие запросы — «последние N заказов» (ORDER BY placed_at DESC LIMIT 10), индекс с явным DESC отдаёт результат без сортировки — буквально первые 10 entries в первом листе.

Suffix truncation работает одинаково для ASC и DESC. Deduplication тоже. Размер индекса от направления сортировки не зависит. Но план запроса с правильно подобранным порядком может быть в разы быстрее за счёт устранённого Sort node.

Краткое сравнение: что когда применяется

Кратко, чтобы помнить:

• Suffix truncation (PG 12+): всегда, для всех B-tree-индексов. Работает только в internal-узлах. Применяется автоматически в момент split или CREATE INDEX. Не отключается параметром (это всегда выгодно).
• Deduplication (PG 13+): для индексов без UNIQUE. По умолчанию deduplicate_items = on. Применяется при insert в лист, перед split. Можно отключить через WITH (deduplicate_items = off) или ALTER INDEX SET.

Обе оптимизации применяются только при создании страницы — на унаследованных страницах из старой версии не применяются. Решение: REINDEX (CONCURRENTLY) после major upgrade.

Чек-лист

• Suffix truncation (PG 12+) сжимает разделители в internal-узлах до минимального префикса. Fan-out растёт, дерево становится ниже.
• Deduplication (PG 13+) хранит дубликаты в листьях как posting list (один ключ + массив TID). Работает для всех индексов без UNIQUE.
• Обе оптимизации применяются только при создании/перестройке индекса. После upgrade с PG 11 нужен REINDEX.
• На индексах по low-cardinality колонкам (типа status, country) deduplication даёт сжатие в 2-5 раз.
• WITH (deduplicate_items = off) отключает дедупликацию для конкретного индекса — полезно для бенчмарков.
• fillfactor = 90 по умолчанию для B-tree; для append-only можно поднять до 100.