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

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

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

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

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

Реализация GIN в Digital Q.DataBase в основном поддерживается Теодором Сигаевым и Олегом Бартуновым. Дополнительная информация о GIN на их веб-сайте.

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

В основной состав Digital Q.DataBase дистрибутива входят GIN классы операторов, перечисленные в Таблица 7.14.3. (Некоторые дополнительные модули, описанные в, Приложение 8.6 предоставляют дополнительные GIN классы операторов.)

Таблица 7.14.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 поддерживает меньшее количество операторов, но обеспечивает более высокую производительность для этих операторов. См. Раздел 2.5.14.4 для получения подробных сведений.

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

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

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

Класс операторов для GIN должен предоставлять:

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

Возвращает выделенный через palloc массив ключей для индексируемого элемента. Количество возвращаемых ключей должно быть сохранено по адресу *nkeys. Если какой-либо из ключей может иметь значение NULL, необходимо также выделить через palloc массив *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 — это номер стратегии оператора в рамках класса операторов (см. Раздел 5.1.16.2). Часто extractQuery требуется обратиться к n для определения типа данных query и метода, который должен использоваться для извлечения значений ключей. Количество возвращаемых ключей должно быть сохранено в *nkeys. Если какой-либо из ключей может иметь значение NULL, необходимо также выделить через palloc массив *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 охватывает функциональность обоих вариантов, поэтому предоставления triConsistent одной этой функции достаточно. Однако если вычисление логического варианта обходится значительно дешевле, может быть выгодно реализовать оба варианта. Если предоставлен только логический вариант, некоторые оптимизации, основанные на исключении элементов индекса до извлечения всех ключей, будут отключены.

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

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

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

В случае успешного завершения *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.

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

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

int compare(Datum a, Datum b): Сравнивает два ключа (не индексируемые элементы!) и возвращает целое число меньше нуля, равное нулю или больше нуля, что указывает, является ли первый ключ меньшим, равным или большим, чем второй. Ключи со значением NULL этой функции никогда не передаются.

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

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

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

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

void options(local_relopts *relopts)

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

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

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

Для поддержки «частичного совпадения» запросов класс операторов должен предоставить comparePartial метод, и его extractQuery метод должен устанавливать pmatch параметр при обнаружении запроса с частичным совпадением. См. Раздел 7.14.4.4.2 для получения подробных сведений.

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

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

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

Начиная с версии Digital Q.DataBase 9.1, в индекс могут быть включены значения ключей NULL. Кроме того, в индекс включаются заполнители NULL для индексируемых элементов, которые сами являются NULL или не содержат ключей согласно extractValue. Это позволяет выполнять поиск, который должен находить пустые элементы.

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

Рисунок 7.14.1. Внутреннее устройство индексов GIN

7.14.4.4.1. Механизм быстрого обновления GIN #

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

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

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

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

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

7.14.4.5. Советы и рекомендации по использованию GIN #

Создание индекса и вставка данных

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

Когда fastupdate включен для GIN (подробнее см. Раздел 7.14.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_fuzzy_search_limit

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

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

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

Как показывает опыт, значения в пределах нескольких тысяч (например, 5000 — 20000) обеспечивают хорошую производительность.

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

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

7.14.4.7. Примеры #

В основной состав Digital Q.DataBase дистрибутива входят GIN классы операторов, описанные ранее в Таблица 7.14.3. Следующие contrib модули также содержат GIN классы операторов:

btree_gin: Функциональность, эквивалентная B-дереву, для нескольких типов данных
hstore: Модуль для хранения пар (ключ, значение)
intarray: Расширенная поддержка для int[]
pg_trgm: Определение сходства текста с использованием сопоставления триграмм

Наверх