62.4. Индексы GIN#

62.4. Индексы GIN

62.4. Индексы GIN #

62.4.1. Введение #

GIN означает Generalized Inverted Index. GIN предназначен для обработки случаев, когда элементы, которые должны быть проиндексированы, являются составными значениями, и запросы, которые должны обрабатываться индексом, должны искать значения элементов, которые появляются в составных элементах. Например, элементами могут быть документы, а запросами могут быть поиски документов, содержащих определенные слова.

Мы используем слово элемент для обозначения составного значения, которое должно быть проиндексировано, и слово ключ для обозначения значения элемента. GIN всегда хранит и ищет ключи, а не сами значения элементов.

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

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

Одним из преимуществ GIN является возможность разработки пользовательских типов данных с соответствующими методами доступа, экспертом в области данного типа данных, а не экспертом баз данных. Это во многом схожее преимущество с использованием GiST.

Реализация GIN в Tantor BE в основном поддерживается Федором Сигаевым и Олегом Бартуновым. Больше информации о GIN можно найти на их веб-сайте.

62.4.2. Встроенные классы операторов #

Основной дистрибутив Tantor BE включает классы операторов GIN, показанные в Таблица 62.3. (Некоторые из дополнительных модулей, описанных в Предметный указатель F, предоставляют дополнительные классы операторов GIN).

Таблица 62.3. Встроенные классы операторов GIN

ИмяИндексируемые операторы
array_ops&& (anyarray,anyarray)
@> (anyarray,anyarray)
<@ (anyarray,anyarray)
= (anyarray,anyarray)
jsonb_ops@> (jsonb,jsonb)
@? (jsonb,jsonpath)
@@ (jsonb,jsonpath)
? (jsonb,text)
?| (jsonb,text[])
?& (jsonb,text[])
jsonb_path_ops@> (jsonb,jsonb)
@? (jsonb,jsonpath)
@@ (jsonb,jsonpath)
tsvector_ops@@ (tsvector,tsquery)

Из двух классов операторов для типа jsonb, класс jsonb_ops является классом по умолчанию. Класс jsonb_path_ops поддерживает меньше операторов, но обеспечивает лучшую производительность для этих операторов. См. Раздел 8.14.4 для получения подробной информации.

62.4.3. Расширяемость #

Интерфейс GIN имеет высокий уровень абстракции, требуя от реализатора метода доступа только реализации семантики обрабатываемого типа данных. Сам уровень GIN заботится о параллельности, журналировании и поиске в структуре дерева.

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

Есть два метода, которые операторный класс для GIN должен предоставить:

Datum *extractValue(Datum itemValue, int32 *nkeys, bool **nullFlags)

Возвращает массив ключей, выделенный с помощью palloc, для заданного элемента, который должен быть проиндексирован. Количество возвращенных ключей должно быть сохранено в переменной *nkeys. Если какие-либо ключи могут быть null, также выделяется массив полей *nkeys типа bool, адрес которого сохраняется в **nullFlags, и устанавливаются соответствующие флаги null. *nullFlags может быть оставлен NULL (его начальное значение), если все ключи не являются null. Возвращаемое значение может быть NULL, если элемент не содержит ключей.

Datum *extractQuery(Datum query, int32 *nkeys, StrategyNumber n, bool **pmatch, Pointer **extra_data, bool **nullFlags, int32 *searchMode)

Возвращает массив ключей, выделенный с помощью palloc, при заданном значении для запроса; то есть, query - это значение справа от индексируемого оператора, левая часть которого - индексируемый столбец. n - это номер стратегии оператора внутри класса операторов (см. Раздел 34.15.2). Часто extractQuery должна обратиться к n, чтобы определить тип данных query и метод, который следует использовать для извлечения ключевых значений. Количество возвращаемых ключей должно быть сохранено в *nkeys. Если какие-либо ключи могут быть null, также нужно выделить массив *nkeys полей bool, сохранить его адрес в *nullFlags и установить эти флаги null по мере необходимости. *nullFlags может быть оставлено NULL (его начальное значение), если все ключи не являются null. Возвращаемое значение может быть NULL, если query не содержит ключей.

searchMode - это выходной аргумент, который позволяет extractQuery указать детали о том, как будет выполняться поиск. Если *searchMode установлено в GIN_SEARCH_MODE_DEFAULT (что является его исходным значением перед вызовом), рассматриваются только элементы, которые соответствуют хотя бы одному из возвращенных ключей. Если *searchMode установлено в GIN_SEARCH_MODE_INCLUDE_EMPTY, то помимо элементов, содержащих хотя бы один совпадающий ключ, рассматриваются также элементы, не содержащие ключей вообще. (Этот режим полезен для реализации операторов подмножества, например). Если *searchMode установлено в GIN_SEARCH_MODE_ALL, то все ненулевые элементы в индексе рассматриваются как возможные совпадения, независимо от того, соответствуют ли они какому-либо из возвращенных ключей или нет. (Этот режим гораздо медленнее других двух выборов, так как требует практически полного сканирования индекса, но может быть необходим для правильной реализации крайних случаев. Оператор, который в большинстве случаев требует этот режим, вероятно, не является хорошим кандидатом для класса операторов GIN). Символы для установки этого режима определены в access/gin.h.

pmatch - это выходной аргумент, используемый при поддержке частичного совпадения. Чтобы использовать его, extractQuery должна выделить массив из *nkeys элементов типа bool и сохранить его адрес в *pmatch. Каждый элемент массива должен быть установлен в true, если соответствующий ключ требует частичного совпадения, и в false, если нет. Если *pmatch установлено в NULL, то GIN предполагает, что частичное совпадение не требуется. Переменная инициализируется значением NULL перед вызовом, поэтому этот аргумент можно просто игнорировать операторными классами, которые не поддерживают частичное совпадение.

extra_data - это выходной аргумент, который позволяет extractQuery передавать дополнительные данные в методы consistent и comparePartial. Чтобы использовать его, extractQuery должен выделить массив указателей размером *nkeys и сохранить его адрес в *extra_data, а затем сохранить в него любые данные. Переменная инициализируется значением NULL перед вызовом, поэтому этот аргумент можно просто игнорировать классами операторов, которым не требуются дополнительные данные. Если *extra_data установлено, весь массив передается в метод consistent, а соответствующий элемент - в метод comparePartial.

Класс оператора также должен предоставлять функцию для проверки, соответствует ли индексированный элемент запросу. Она имеет два варианта: логическую функцию consistent и тернарную функцию triConsistent. Функция triConsistent объединяет функциональность обоих вариантов, поэтому достаточно предоставить только ее. Однако, если логический вариант значительно дешевле вычислять, может быть выгодно предоставить оба варианта. Если предоставлен только логический вариант, некоторые оптимизации, которые зависят от опровержения индексированных элементов перед получением всех ключей, отключаются.

bool consistent(bool check[], StrategyNumber n, Datum query, int32 nkeys, Pointer extra_data[], bool *recheck, Datum queryKeys[], bool nullFlags[])

Возвращает true, если индексированный элемент удовлетворяет оператору запроса с номером стратегии n (или может удовлетворять его, если возвращается индикация повторной проверки). Эта функция не имеет прямого доступа к значению индексированного элемента, так как GIN не хранит элементы явно. Вместо этого доступна информация о том, какие ключевые значения, извлеченные из запроса, присутствуют в данном индексированном элементе. Массив check имеет длину nkeys, которая совпадает с количеством ключей, ранее возвращенных функцией extractQuery для этого элемента запроса query. Каждый элемент массива check равен true, если индексированный элемент содержит соответствующий ключ запроса, то есть если (check[i] == true), i-й ключ массива результатов extractQuery присутствует в индексированном элементе. Исходный элемент запроса передается в случае, если метод consistent должен обратиться к нему, а также массивы queryKeys[] и nullFlags[], ранее возвращенные функцией extractQuery. extra_data - это массив дополнительных данных, возвращенных функцией extractQuery, или NULL, если таковых нет.

Когда функция extractQuery возвращает пустой ключ в queryKeys[], соответствующий элемент check[] становится true, если индексированный элемент содержит пустой ключ; то есть семантика check[] аналогична IS NOT DISTINCT FROM. Функция consistent может проверить соответствующий элемент nullFlags[], если ей нужно различать обычное совпадение значений и совпадение с пустым значением.

При успешном выполнении, значение *recheck должно быть установлено в true, если кортеж кучи должен быть проверен снова с помощью оператора запроса, или в false, если индексный тест является точным. То есть, значение false гарантирует, что кортеж кучи не соответствует запросу; значение true с установленным значением *recheck в false гарантирует, что кортеж кучи соответствует запросу; и значение true с установленным значением *recheck в true означает, что кортеж кучи может соответствовать запросу, поэтому его необходимо получить и проверить, выполнив оператор запроса непосредственно против исходного индексированного элемента.

GinTernaryValue triConsistent(GinTernaryValue check[], StrategyNumber n, Datum query, int32 nkeys, Pointer extra_data[], Datum queryKeys[], bool nullFlags[])

triConsistent похожа на consistent, но вместо логических значений в векторе check есть три возможных значения для каждого ключа: GIN_TRUE, GIN_FALSE и GIN_MAYBE. GIN_FALSE и GIN_TRUE имеют тот же смысл, что и обычные логические значения, в то время как GIN_MAYBE означает, что наличие этого ключа неизвестно. Когда присутствуют значения GIN_MAYBE, функция должна возвращать только GIN_TRUE, если элемент точно соответствует, независимо от того, содержит ли он соответствующие ключи запроса. Аналогично, функция должна возвращать GIN_FALSE только если элемент точно не соответствует, независимо от того, содержит ли он ключи GIN_MAYBE. Если результат зависит от записей GIN_MAYBE, то есть, соответствие нельзя подтвердить или опровергнуть на основе известных ключей запроса, функция должна возвращать GIN_MAYBE.

Когда в векторе проверки check нет значений GIN_MAYBE, возвращаемое значение GIN_MAYBE эквивалентно установке флага recheck в функции consistent типа Boolean.

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

int compare(Datum a, Datum b)

Сравнивает два ключа (неиндексированных элемента!) и возвращает целое число, меньшее нуля, ноль или большее нуля, указывающее, является ли первый ключ меньше, равным или больше второго. Нулевые ключи никогда не передаются этой функции.

В противном случае, если класс оператора не предоставляет метод compare, GIN будет искать класс оператора по умолчанию для типа данных ключа индекса и использовать его функцию сравнения. Рекомендуется указывать функцию сравнения в классе оператора GIN, предназначенном только для одного типа данных, так как поиск класса оператора btree требует несколько тактов. Однако полиморфные классы операторов GIN (например, array_ops) обычно не могут указать одну функцию сравнения.

Класс операторов для GIN может дополнительно предоставлять следующие методы:

int comparePartial(Datum partial_key, Datum key, StrategyNumber n, Pointer extra_data)

Сравните частично совпадающий ключ запроса с индексным ключом. Возвращает целое число, знак которого указывает на результат: отрицательное значение означает, что индексный ключ не соответствует запросу, но индексное сканирование должно продолжаться; ноль означает, что индексный ключ соответствует запросу; положительное значение указывает, что индексное сканирование должно остановиться, потому что больше нет совпадений возможно. Номер стратегии n оператора, который сгенерировал запрос с частичным совпадением, предоставляется, на случай, если его семантика необходима для определения момента окончания сканирования. Кроме того, extra_data - это соответствующий элемент массива extra-data, созданный с помощью extractQuery, или NULL, если таковой отсутствует. В эту функцию никогда не передаются пустые ключи.

void options(local_relopts *relopts)

Определяет набор параметров, видимых пользователем, которые управляют поведением класса операторов.

Функция options получает указатель на структуру local_relopts, которую необходимо заполнить набором специфичных для класса операторов опций. Опции могут быть доступны из других вспомогательных функций с использованием макросов PG_HAS_OPCLASS_OPTIONS() и PG_GET_OPCLASS_OPTIONS().

Поскольку и извлечение ключа из индексированных значений, и представление ключа в GIN являются гибкими, они могут зависеть от параметров, указанных пользователем.

Для поддержки запросов с частичным совпадением, класс операторов должен предоставлять метод comparePartial, а его метод extractQuery должен устанавливать параметр pmatch при обнаружении запроса с частичным совпадением. Подробности см. в разделе Раздел 62.4.4.2.

Самые фактические типы данных различных значений Datum, упомянутых выше, зависят от класса оператора. Значения элементов, передаваемые в extractValue, всегда являются типом ввода класса оператора, и все ключевые значения должны быть типом STORAGE класса. Тип аргумента query, передаваемого в extractQuery, consistent и triConsistent, является типом правого входного значения оператора-члена класса, идентифицированного номером стратегии. Это не обязательно должен быть тот же самый тип, что и индексируемый тип, при условии, что ключевые значения правильного типа могут быть извлечены из него. Однако рекомендуется, чтобы SQL-объявления этих трех вспомогательных функций использовали индексируемый тип данных opclass для аргумента query, даже если фактический тип может быть чем-то другим в зависимости от оператора.

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

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

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

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

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


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

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

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

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

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

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

62.4.5. Советы и хитрости по GIN #

Create vs. insert

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

Когда fastupdate включен для GIN (см. Раздел 62.4.4.1 для получения более подробной информации), штраф меньше, чем когда он отключен. Но для очень больших обновлений может быть лучше удалить и создать индекс заново.

maintenance_work_mem

Время сборки индекса GIN очень чувствительно к настройке maintenance_work_mem; не стоит экономить на рабочей памяти во время создания индекса.

gin_pending_list_limit

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

gin_pending_list_limit может быть переопределен для отдельных GIN-индексов путем изменения параметров хранения, что позволяет каждому GIN-индексу иметь свой собственный порог очистки. Например, возможно увеличить порог только для GIN-индекса, который может быть часто обновляемым, и уменьшить его в остальных случаях.

gin_fuzzy_search_limit

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

Для облегчения контролируемого выполнения таких запросов, GIN имеет настраиваемый мягкий верхний предел на количество возвращаемых строк: параметр конфигурации gin_fuzzy_search_limit. По умолчанию он установлен в 0 (что означает отсутствие ограничения). Если установлено ненулевое значение предела, то возвращаемое множество является подмножеством всего результирующего множества, выбранным случайным образом.

Soft означает, что фактическое количество возвращаемых результатов может немного отличаться от указанного лимита, в зависимости от запроса и качества генератора случайных чисел системы.

Из опыта, значения в тысячах (например, 5000 — 20000) работают хорошо.

62.4.6. Ограничения #

GIN предполагает, что индексируемые операторы являются строгими. Это означает, что extractValue вообще не будет вызываться для значения null (вместо этого автоматически создается заполнитель записи индекса), и extractQuery также не будет вызываться для значения null запроса (вместо этого предполагается, что запрос не может быть удовлетворен). Однако следует отметить, что поддерживаются значения null ключей, содержащиеся в ненулевом составном значении элемента или запроса.

62.4.7. Примеры #

Основной дистрибутив Tantor BE включает классы операторов GIN, показанные ранее в таблице Таблица 62.3. Следующие модули contrib также содержат классы операторов GIN:

btree_gin

Эквивалент функциональности B-дерева для нескольких типов данных

hstore

Модуль для хранения пар (ключ, значение)

intarray

Улучшенная поддержка для int[]

pg_trgm

Сходство текста с использованием сопоставления триграмм