Реализация

В этом разделе описаны детали реализации индекса B-дерева, которые могут быть полезны опытным пользователям. Более подробное, сфокусированное на внутренностях описание реализации B-дерева смотрите в src/backend/access/nbtree/README в исходном дистрибутиве.

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

Индексы PostgreSQL B-дерева представляют собой многоуровневые древовидные структуры, где каждый уровень дерева может быть использован как дважды связанный список страниц. Одна метастраница хранится в фиксированной позиции в начале первого сегментного файла индекса. Все остальные страницы являются либо листовыми, либо внутренними. Листовые страницы - это страницы на самом нижнем уровне дерева. Все остальные уровни состоят из внутренних страниц. Каждая листовая страница содержит кортежи, указывающие на строки таблицы. Каждая внутренняя страница содержит кортежи, которые указывают на следующий уровень дерева. Как правило, более 99 % всех страниц - это листовые страницы. Как внутренние, так и листовые страницы используют стандартный формат страницы, описанный в разделе «Макет страницы базы данных».

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

Удаление индекса снизу вверх

Индексы B-дерева не учитывают, что в MVCC может существовать несколько версий одной и той же строки логической таблицы; для индекса каждый кортеж - это независимый объект, которому нужна своя запись в индексе. Кортежи с «оттоком версий» иногда могут накапливаться и негативно влиять на задержку и пропускную способность запросов. Обычно это происходит в нагрузках с большим количеством UPDATE, когда большинство отдельных обновлений не могут применить оптимизацию HOT. Изменение значения только одного столбца, покрываемого одним индексом, во время UPDATE всегда требует нового набора индексных кортежей - по одному для каждого индекса таблицы. Обратите особое внимание, что это касается и индексов, которые не были «логически модифицированы» при UPDATE. Всем индексам потребуется кортеж физического индекса-преемника, который будет указывать на последнюю версию в таблице. Каждый новый кортеж в каждом индексе, как правило, должен сосуществовать с оригинальным «обновленным» кортежем в течение короткого периода времени (обычно до момента фиксации транзакции UPDATE).

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

Примечание:

Не все операции удаления, выполняемые в индексах B-дерева, являются операциями удаления снизу вверх. Существует отдельная категория удаления кортежей индексов: простое удаление кортежей индексов. Это операция отложенного обслуживания, которая удаляет кортежи индексов, которые, как известно, можно безопасно удалить (те, чей бит идентификатора элемента LP_DEAD уже установлен). Как и удаление индекса снизу вверх, простое удаление индекса происходит в момент, когда ожидается разделение страницы, чтобы избежать разделения.

Простое удаление является оппортунистическим в том смысле, что оно может произойти только тогда, когда недавние сканирования индекса устанавливают биты LP_DEAD затронутых элементов в пути. До PostgreSQL 14 единственной категорией удаления B-дерева было простое удаление. Основные различия между ним и удалением снизу вверх заключаются в том, что только первое оппортунистически обусловлено активностью прохождения сканирования индекса, в то время как только последнее конкретно нацелено на отток версий из обновлений, которые логически не изменяют индексированные столбцы.

Удаление индекса снизу вверх выполняет подавляющее большинство всех операций по очистке кортежей индекса от мусора для определенных индексов с определенными рабочими нагрузками. Этого можно ожидать от любого индекса B-дерева, который подвержен значительному изменению версий от UPDATE, которые редко или никогда логически не изменяют столбцы, которые покрывает индекс. Среднее и наихудшее число версий на логическую строку можно поддерживать на низком уровне только за счет проходов инкрементального удаления. Вполне возможно, что размер некоторых индексов на диске никогда не увеличится даже на одну страницу/блок, несмотря на постоянное изменение версий в результате UPDATE. Но даже в этом случае для коллективной очистки таблицы и каждого из ее индексов в конечном итоге потребуется исчерпывающая «чистка» с помощью операции VACUUM (обычно выполняемой в рабочем процессе autovacuum).

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

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

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

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

Примечание:

Дедубликация B-дерева столь же эффективна с «дубликациями», которые содержат значение NULL, даже если значения NULL никогда не равны друг другу согласно = члену любого класса операторов B-дерева. Что касается любой части реализации, которая понимает структуру B-дерева на диске, NULL - это просто еще одно значение из области индексируемых значений

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

CREATE INDEX и REINDEX применяют дедупликацию для создания кортежей списка постинга, хотя используемая ими стратегия несколько отличается. Каждая группа дубликатов обычных кортежей, встречающихся в отсортированном вводе, взятом из таблицы, объединяется в кортеж списка постинга перед добавлением в текущую страницу листа ожидания. Отдельные кортежи списка постинга упаковываются с максимально возможным количеством TID. Листовые страницы записываются обычным способом, без отдельного прохода дедупликации. Эта стратегия хорошо подходит для CREATE INDEX и REINDEX, поскольку они являются одноразовыми пакетными операциями.

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

Иногда для уникальных индексов (а также уникальных ограничений) возможно использование дедупликации. Это позволяет листовым страницам временно «поглощать» лишние дубликаты из оттока версий. Дедупликация в уникальных индексах позволяет усилить удаление индексов снизу вверх, особенно в случаях, когда длительная транзакция хранит снимок, блокирующий сборку мусора. Цель - выиграть время, чтобы стратегия удаления индексов снизу вверх снова стала эффективной. Задержка разбиения страниц до тех пор, пока одна длительная транзакция естественным образом не исчезнет, может позволить выполнить удаление снизу вверх там, где предыдущее удаление не удалось.

Совет

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

Дедупликация не может использоваться во всех случаях из-за ограничений на уровне реализации. Безопасность дедупликации определяется при выполнении CREATE INDEX или REINDEX.

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

• text, varchar и char не могут использовать дедупликацию, если используется недетерминированная свертка. Различия в регистре и ударении должны сохраняться среди одинаковых данных.
• numeric не может использовать дедупликацию. Масштаб числового отображения должен сохраняться среди равных точек отсчета.
• jsonb не может использовать дедупликацию, поскольку класс оператора jsonb B-дерева внутренне использует числовые значения.
• float4 и float8 не могут использовать дедупликацию. Эти типы имеют различные представления для -0 и 0, которые, тем не менее, считаются равными. Это различие должно быть сохранено.

Существует еще одно ограничение на уровне реализации, которое может быть снято в будущей версии PostgreSQL:

• Контейнерные типы (такие как составные типы, массивы или типы диапазонов) не могут использовать дедупликацию.

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

• Индексы INCLUDE никогда не могут использовать дедупликацию.