67.4. Реализация#

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

67.4. Реализация #

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

Начиная с PostgreSQL 9.1, в индекс можно включать значения null ключей. Кроме того, в индекс включаются заполнители null для индексированных элементов, которые являются null или не содержат ключей в соответствии с функцией extractValue. Это позволяет выполнять поиски, которые должны находить пустые элементы.

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

Диаграмма 67.1. Внутреннее устройство GIN


67.4.1. Техника быстрого обновления GIN #

Обновление индекса GIN обычно происходит медленно из-за внутренней природы инвертированных индексов: вставка или обновление одной строки в куче может вызвать множество вставок в индекс (по одной для каждого ключа, извлеченного из индексируемого элемента). GIN способен отложить большую часть этой работы, вставляя новые кортежи во временный неотсортированный список ожидающих записей. Когда таблица очищается или автоанализируется, или когда вызывается функция gin_clean_pending_list, или если список ожидающих записей становится больше, чем gin_pending_list_limit, записи перемещаются в основную структуру данных GIN с использованием тех же методов массовой вставки, которые использовались при создании индекса. Это значительно улучшает скорость обновления индекса GIN, даже с учетом дополнительных издержек на очистку. Более того, эту работу можно выполнить фоновым процессом, а не в процессе обработки запроса на переднем плане.

Основным недостатком такого подхода является то, что при поиске необходимо просматривать список ожидающих записей, в дополнение к поиску в обычном индексе, и поэтому большой список ожидающих записей замедлит поиск значительно. Еще одним недостатком является то, что, хотя большинство обновлений выполняются быстро, обновление, которое приводит к тому, что список ожидающих записей становится "слишком большим", вызовет немедленный цикл очистки и, следовательно, будет намного медленнее, чем другие обновления. Правильное использование автоочистки может минимизировать оба этих проблемы.

Если более важно поддержание стабильного времени ответа, чем скорость обновления, можно отключить использование ожидающих записей, отключив параметр хранения fastupdate для индекса GIN. Подробности см. в разделе CREATE INDEX.

67.4.2. Алгоритм частичного совпадения #

GIN может поддерживать запросы с частичным совпадением, в которых запрос не определяет точное совпадение для одного или нескольких ключей, но возможные совпадения попадают в достаточно узкий диапазон значений ключей (в пределах порядка сортировки ключей, определенного методом поддержки compare). Метод extractQuery, вместо возврата точного значения ключа для сопоставления, возвращает значение ключа, которое является нижней границей диапазона для поиска и устанавливает флаг pmatch в значение true. Затем диапазон ключей сканируется с использованием метода comparePartial. Метод comparePartial должен возвращать ноль для совпадающего индексного ключа, отрицательное значение для несовпадения, которое все еще находится в пределах диапазона поиска, или положительное значение, если индексный ключ находится за пределами диапазона, который может совпадать.