62.4. Реализация

В этом разделе освещаются детали реализации индекса-B-дерева, знание которых может быть полезно для специалистов.

62.4.1. Структура B-дерева

Индексы-B-деревья в Postgres Pro Enterprise представляют собой многоуровневые иерархические структуры, в которых каждый уровень дерева может использоваться как двусвязный список страниц. Единственная метастраница индекса хранится в фиксированном положении в начале первого файла сегмента индекса. Все остальные страницы делятся на внутренние и на листовые. Листовые страницы находятся на самом нижнем уровне дерева. Все более высокие уровни состоят из внутренних страниц. Листовая страница содержит кортежи, указывающие на строки в таблице, а внутренняя страница — кортежи, указывающие на следующий уровень в дереве. Обычно листовые страницы составляют около 99% всех страниц индекса. И для тех, и для других страниц используется один стандартный формат, описанный в Разделе 67.6.

Новые листовые страницы добавляются в B-дерево когда существующая листовая страница не может вместить новый поступающий кортеж. При этом выполняется операция разделения страницы, освобождающая место на переполнившейся странице, перенося подмножество изначально содержащихся на ней элементов на новую страницу. При разделении страницы в её родительскую страницу также должна быть добавлена ссылка вниз, что может потребовать произвести разделение и этой родительской страницы. Разделение страниц «каскадно поднимается вверх» рекурсивным образом. Когда же и корневая страница не может вместить новую ссылку вниз, производится операция разделения корневой страницы. При этом в структуру дерева добавляется новый уровень, на котором оказывается новая корневая страница, стоящая над той, что была корневой ранее.

62.4.2. Исключение дубликатов

Дубликатом называется кортеж на листовой странице (кортеж, указывающий на строку таблицы), у которого все ключевые столбцы индекса имеют значения, соответствующие значениям столбцов из как минимум одного другого кортежа на листовой странице, находящейся рядом в том же индексе. Дублирующиеся кортежи довольно часто встречаются на практике. В индексах-B-деревьях такие дубликаты могут представляться особым экономичным образом при включении дополнительного механизма — исключения дубликатов.

Работа этого механизма заключается в периодическом объединении групп дублирующихся кортежей и формировании одного кортежа со списком идентификаторов для каждой группы. В таком представлении значения ключевых столбцов хранятся в единственном экземпляре, а за ними идёт отсортированный массив идентификаторов TID, указывающих на строки в таблице. Это существенно уменьшает размер хранимых индексов, в которых каждое значение (или каждое уникальное сочетание значений столбцов) появляется в среднем несколько раз. В результате может значительно увеличиться скорость выполнения запросов, а также могут сократиться издержки, связанные с регулярной очисткой индексов.

Примечание

Тогда как значения NULL вообще не считаются равными любому другому, включая NULL, для механизма B-дерева NULL — такое же значение в домене всех индексируемых значений, как и другие (если речь идёт не об ограничении уникальности в индексе). Поэтому исключение дубликатов в B-дереве работает эффективно и с «дубликатами», содержащими NULL.

Процедура исключения дубликатов производится по необходимости, когда вставляется новый элемент, не умещающийся на существующей листовой странице. Это предотвращает (или как минимум откладывает) разделение листовых страниц. В отличие от кортежей со списками идентификаторов GIN, в B-дереве эти кортежи не должны расширяться при каждом добавлении нового дубликата; они просто образуют другое физическое представление исходного логического содержания листовой страницы. При таком подходе обеспечивается стабильная производительность при смешанной нагрузке с чтением и записью. Исключение дубликатов должно дать как минимум заметное увеличение производительности для большинства клиентских приложений. По умолчанию оно включено.

Если же в профиле нагрузки преобладает запись и исключение дубликатов не приносит выигрыша ввиду отсутствия или небольшого числа дублирующихся значений, этот механизм может породить небольшие постоянные издержки (если он не отключён). В таких случаях его можно отключить для отдельных индексов с помощью параметра хранения deduplicate_items. При нагрузке только на чтение никакие дополнительные издержки не возникают, так как кортежи со списком идентификаторов читаются так же эффективно, как и кортежи в стандартном представлении. Поэтому чаще всего отключение этого механизма не будет полезным.

Индексы-B-деревья сами по себе не учитывают, что в среде MVCC может быть несколько версий одной логической строки таблицы; для индекса каждый кортеж является независимым объектом, для которого требуется отдельный элемент в индексе. Таким образом, при изменении строки для неё всегда создаются новые записи в индексах, даже если ключевые значения в ней не изменились. При некоторых видах нагрузки возникает замусоривание индекса из-за подобного дублирования версий (обычно это наблюдается при нагрузке с преобладанием UPDATE, когда не удаётся применить оптимизацию HOT вследствие изменения минимум одного индексированного столбца). Для механизма исключения дубликатов в B-дереве эти дубликаты версий на уровне реализации не отличаются от дубликатов в обычном смысле, и поэтому данный механизм помогает справиться и с замусориванием индексов, вызванным активной циркуляцией версий.

Подсказка

Для определения необходимости провести процедуру исключения дубликатов в уникальном индексе применяются дополнительные соображения. В таких индексах как правило можно перейти сразу к разделению листовой страницы, не расходуя лишние циклы на бесполезные проходы в поиске дубликатов. Если вас беспокоят возможные издержки, которые могут быть связаны с исключением дубликатов, вы можете установить значение deduplicate_items = off для отдельных индексов. Однако его вполне можно оставить включённым и для уникальных индексов.

Исключение дубликатов может применяться не всегда ввиду ограничений на уровне реализации. Возможность его применения определяется во время выполнения CREATE INDEX или REINDEX.

Учтите, что исключение дубликатов считается небезопасным и не может применяться в следующих случаях, когда возможны семантические различия равных значений:

  • Исключение дубликатов не может применяться с типами text, varchar и char в случае использования недетерминированных правил сортировки, так как в равных значениях должны сохраняться возможные различия в регистре и диакритических знаках.

  • Исключение дубликатов невозможно с типом numeric, так как для равных значений должен сохраняться числовой масштаб, который может быть разным.

  • Исключение дубликатов не может применяться с типом jsonb, так как внутри класса операторов B-дерева jsonb используется тип numeric.

  • Исключение дубликатов невозможно для типов float4 и float8. В этих типах имеются разные представления значений -0 и 0, которые при этом считаются равными. Однако отличие между ними должно сохраняться.

Имеется ещё одно ограничение на уровне реализации, которое может быть снято в будущих версиях Postgres Pro Enterprise:

  • Исключение дубликатов невозможно с типами-контейнерами (это составные, диапазонные типы, а также массивы).

Есть ещё одно ограничение на уровне реализации, действующее вне зависимости от применяемого класса операторов или правила сортировки:

  • Исключение дубликатов не может применяться в индексах с INCLUDE.