64.4. Индексы GIN #
64.4.1. Введение #
GIN расшифровывается как «Generalized Inverted Index» (Обобщённый инвертированный индекс). GIN предназначается для случаев, когда индексируемые значения являются составными, а запросы, на обработку которых рассчитан индекс, ищут значения элементов в этих составных объектах. Например, такими объектами могут быть документы, а запросы могут выполнять поиск документов, содержащих определённые слова.
Здесь мы используем термин объект, говоря о составном значении, которое индексируется, и термин ключ, говоря о включённом в него элементе. GIN всегда хранит и ищет ключи, а не объекты как таковые.
Индекс GIN сохраняет набор пар (ключ, список идентификаторов), где список идентификаторов содержит идентификаторы строк, в которых находится ключ. Один и тот же идентификатор строки может фигурировать в нескольких списках, так как объект может содержать больше одного ключа. Значение каждого ключа хранится только один раз, так что индекс GIN очень компактен в случаях, когда один ключ встречается много раз.
GIN является обобщённым в том смысле, что код метода доступа GIN не должен знать о конкретных операциях, которые он ускоряет. Вместо этого задаются специальные стратегии для конкретных типов данных. Стратегия определяет, как извлекаются ключи из индексируемых объектов и условий запросов, и как установить, действительно ли удовлетворяет запросу строка, содержащая некоторые значения ключей.
Ключевым преимуществом GIN является то, что он позволяет разрабатывать дополнительные типы данных с соответствующими методами доступа экспертам в предметной области типа данных, а не специалистам по СУБД. В этом аспекте он похож на GiST.
Сопровождением реализации GIN в PostgreSQL в основном занимаются Фёдор Сигаев и Олег Бартунов. Дополнительные сведения о GIN можно получить на их сайте.
64.4.2. Встроенные классы операторов #
В базовый дистрибутив PostgreSQL включены классы операторов GIN, перечисленные в Таблице 64.3. (Некоторые дополнительные модули, описанные в Приложении F, добавляют другие классы операторов GIN.)
Таблица 64.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.
64.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
задаёт номер стратегии оператора в классе операторов (см. Подраздел 36.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
, то в дополнение к объектам с минимум одним совпадением ключа, подходящими кандидатами будут считаться и объекты, вообще не содержащие ключей. (Этот режим полезен для реализации, например, операторов A-является-подмножеством-B.) Если в*searchMode
установлено значениеGIN_SEARCH_MODE_ALL
, подходящими кандидатами считаются все отличные от NULL объекты в индексе, независимо от того, встречаются ли в них возвращаемые ключи. (Этот режим намного медленнее двух других, так как он по сути требует сканирования всего индекса, но он может быть необходим для корректной обработки крайних случаев. Оператор, который выбирает этот режим в большинстве ситуаций, скорее всего не подходит для реализации в классе операторов GIN.) Символы для этих значений режима определены вaccess/gin.h
.Выходной аргумент
pmatch
используется, когда поддерживается частичное соответствие. Чтобы использовать его,extractQuery
должна выделить массив из*nkeys
логических элементов и сохранить его адрес в*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
присутствует в индексированном объекте. Исходное значениеquery
передаётся на случай, если оно потребуется методуconsistent
; с той же целью ему передаются массивыqueryKeys[]
иnullFlags[]
, ранее возвращённые функциейextractQuery
. В аргументеextra_data
передаётся массив дополнительных данных, возвращённый функциейextractQuery
, илиNULL
, если дополнительных данных нет.Когда
extractQuery
возвращает ключ NULL вqueryKeys[]
, соответствующий элементcheck[]
содержит true, если индексированный объект содержит ключ NULL; то есть можно считать, что элементыcheck[]
отражают условиеIS NOT DISTINCT FROM
. Функция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
.Когда в векторе
check
нет элементовGIN_MAYBE
, возвращаемое значение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
— соответствующий элемент массива дополнительных данных, сформированного функциейextractQuery
, либоNULL
, если дополнительных данных нет. Значения NULL этой функции никогда не передаются.void options(local_relopts *relopts)
Определяет набор видимых пользователю параметров, управляющих поведением класса операторов.
Функции
options
передаётся указатель на структуруlocal_relopts
, в которую нужно внести набор параметров, относящихся к классу операторов. Обращаться к этим параметрам из других опорных функций можно с помощью макросовPG_HAS_OPCLASS_OPTIONS()
иPG_GET_OPCLASS_OPTIONS()
.Так как в GIN и извлечение ключа из индексируемых значений, и его представление допускают гибкость, могут быть полезны параметры для настройки этого индекса.
Для поддержки проверок на «частичное соответствие» класс операторов должен предоставить метод comparePartial
, а метод extractQuery
должен устанавливать параметр pmatch
, когда встречается запрос на частичное соответствие. За подробностями обратитесь к Подразделу 64.4.4.2.
Фактические типы данных различных значений Datum
, упоминаемых выше, зависят от класса операторов. Значения объектов, передаваемые в extractValue
, всегда имеют входной тип класса операторов, а все значения ключей должны быть типа, заданного параметром STORAGE
для класса. Типом аргумента query
, передаваемого функциям extractQuery
, consistent
и triConsistent
, будет тот тип, что указан в качестве типа правого операнда оператора-члена класса, определяемого по номеру стратегии. Это не обязательно должен быть индексируемый тип, достаточно лишь, чтобы из него можно было извлечь значения ключей, имеющие нужный тип. Однако рекомендуется, чтобы в SQL-объявлениях этих трёх опорных функций для аргумента query
назначался индексируемый тип класса операторов, даже несмотря на то, что фактический тип может быть другим, в зависимости от оператора.
64.4.4. Реализация #
Внутри индекс GIN содержит B-дерево, построенное по ключам, где каждый ключ является элементом одного или нескольких индексированных объектов (например, членом массива) и где каждый кортеж на страницах листьев содержит либо указатель на B-дерево указателей на данные («дерево идентификаторов»), либо простой список указателей на данные («список идентификаторов»), когда этот список достаточно мал, чтобы уместиться в одном кортеже индекса вместе со значением ключа. Эти компоненты GIN-индекса показаны на Рисунке 64.1.
Начиная с PostgreSQL версии 9.1, в индекс могут быть включены значения ключей, равные NULL. Кроме того, в индекс вставляются NULL для индексируемых объектов, равных NULL или не содержащих ключей, согласно функции extractValue
. Это позволяет находить при поиске пустые объекты, когда они должны быть найдены.
Составные индексы GIN реализуются в виде одного B-дерева по составным значениям (номер столбца, значение ключа). Значения ключей для различных столбцов могут быть разных типов.
Рисунок 64.1. Внутреннее устройство GIN
64.4.4.1. Методика быстрого обновления GIN #
Природа инвертированного индекса такова, что обновление GIN обычно медленная операция: при добавлении или изменении одной строки данных может потребоваться выполнить множество добавлений записей в индекс (для каждого ключа, извлечённого из индексируемого объекта). GIN может отложить большой объём этой работы, вставляя новые кортежи во временный, несортированный список записей, ожидающих индексации. Когда таблица очищается, автоматически анализируется, вызывается функция gin_clean_pending_list
или размер этого списка временного списка становится больше чем gin_pending_list_limit, записи переносятся в основную структуру данных GIN теми же методами массового добавления данных, что и при начальном создании индекса. Это значительно увеличивает скорость обновления индекса GIN, даже с учётом дополнительных издержек при очистке. К тому же эту дополнительную работу можно выполнить в фоновом процессе, а не в процессе, непосредственно выполняющем запросы.
Основной недостаток такого подхода состоит в том, что при поиске необходимо не только проверить обычный индекс, но и просканировать список ожидающих записей, так что если этот список большой, поиск значительно замедляется. Ещё один недостаток состоит в том, что хотя в основном изменения производятся быстро, изменение, при котором этот список оказывается «слишком большим», влечёт необходимость немедленной очистки и поэтому выполняется гораздо дольше остальных изменений. Минимизировать эти недостатки можно, правильно организовав автоочистку.
Если выдержанность времени операций важнее скорости обновления, применение списка ожидающих записей можно отключить, выключив параметр хранения fastupdate
для индекса GIN. За подробностями обратитесь к CREATE INDEX.
64.4.4.2. Алгоритм частичного соответствия #
GIN может поддерживать проверки «частичного соответствия», когда запрос выявляет не точное соответствие одному или нескольким ключам, а возможные соответствия, попадающие в достаточно узкий диапазон значений ключей (при порядке сортировки ключей, определённым опорным методом compare
). В этом случае метод extractQuery
возвращает не значение ключа, которое должно соответствовать точно, а значение, определяющее нижнюю границу искомого диапазона, и устанавливает флаг pmatch
. Затем диапазон ключей сканируется методом comparePartial
. Метод comparePartial
должен вернуть ноль при соответствии ключа индекса, отрицательное значение, если соответствия нет, но нужно продолжать проверку диапазона, и положительное значение, если ключ индекса оказался за искомым диапазоном.
64.4.5. Приёмы и советы по применению GIN #
- Создание или добавление
Добавление объектов в индекс GIN может выполняться медленно, так как для каждого объекта скорее всего потребуется добавлять множество ключей. Поэтому при массовом добавлении данных в таблицу рекомендуется удалить индекс GIN и пересоздать его по окончании добавления.
Когда для GIN включён режим
fastupdate
(за подробностями обратитесь к Подразделу 64.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 было обеспечить поддержку хорошо расширяемого полнотекстового поиска в PostgreSQL, а при полнотекстовом поиске нередко возникают ситуации, когда возвращается очень большой набор результатов. Однако чаще всего так происходит, когда запрос содержит очень часто встречающиеся слова, так что полученный результат всё равно оказывается бесполезным. Так как чтение множества записей с диска и последующая сортировка их может занять много времени, это неприемлемо в производственных условиях. (Заметьте, что поиск по индексу при этом выполняется очень быстро.)
Для управляемого выполнения таких запросов в GIN введено настраиваемое мягкое ограничение сверху для числа возвращаемых строк: конфигурационный параметр
gin_fuzzy_search_limit
. По умолчанию он равен 0 (то есть ограничение отсутствует). Если он имеет ненулевое значение, возвращаемый набор строк будет случайно выбранным подмножеством всего набора результатов.«Мягким» оно называется потому, что фактическое число возвращаемых строк может несколько отличаться от заданного значения, в зависимости от запроса и качества системного генератора случайных чисел.
Из практики, со значениями в несколько тысяч (например, 5000 — 20000) получаются приемлемые результаты.
64.4.6. Ограничения #
GIN полагает, что индексируемые операторы являются строгими. Это означает, что функция extractValue
вовсе не будет вызываться для значений NULL (вместо этого будет автоматически создаваться пустая запись в индексе), так же как и extractQuery
не будет вызываться с искомым значением NULL (при этом сразу предполагается, что запрос не удовлетворяется). Заметьте однако, что при этом поддерживаются ключи NULL, содержащиеся в составных объектах или искомых значениях.
64.4.7. Примеры #
В базовый дистрибутив PostgreSQL включены классы операторов GIN, перечисленные ранее в Таблице 64.3. Также классы операторов GIN содержатся в следующих модулях contrib
:
btree_gin
Функциональность B-дерева для различных типов данных
hstore
Модуль для хранения пар (ключ, значение)
intarray
Расширенная поддержка
int[]
pg_trgm
Схожесть текста на основе статистики триграмм