64.3. Индексы SP-GiST #
64.3.1. Введение #
Аббревиатура SP-GiST расшифровывается как «Space-Partitioned GiST» (GiST с разбиением пространства). SP-GiST поддерживает деревья поиска с разбиением, что облегчает разработку широкого спектра различных несбалансированных структур данных, в том числе деревьев квадрантов, а также k-мерных и префиксных деревьев. Общей характеристикой этих структур является то, что они последовательно разбивают пространство поиска на сегменты, которые не обязательно должны быть равного размера. При этом поиск, хорошо соответствующий правилу разбиения, с таким индексом может быть очень быстрым.
Эти популярные структуры данных изначально конструировались для работы в памяти. При таком применении они обычно представляются в виде набора динамически выделяемых узлов, связываемых указателями. Однако подобную схему нельзя в таком виде перенести на диск, так как цепочки указателей могут быть довольно длинными, и поэтому потребуется слишком много обращений к диску. Структуры данных для хранения на диске, напротив, должны иметь большую разветвлённость для минимизации объёма ввода/вывода. Для решения этой задачи SP-GiST сопоставляет узлы дерева поиска со страницами на диске так, чтобы при поиске требовалось обращаться только к нескольким страницам на диске, даже если при этом нужно просмотреть множество узлов.
Как и GiST, SP-GiST призван дать возможность разрабатывать дополнительные типы данных с соответствующими методами доступа экспертам в предметной области типа данных, а не специалистам по СУБД.
Представленная здесь информация частично позаимствована с сайта Проекта индексации SP-GiST Университета Пердью. Сопровождением реализации SP-GiST в PostgreSQL в основном занимаются Фёдор Сигаев и Олег Бартунов; дополнительные сведения можно получить на их сайте.
64.3.2. Встроенные классы операторов #
В базовый дистрибутив PostgreSQL включены классы операторов SP-GiST, перечисленные в Таблице 64.2.
Таблица 64.2. Встроенные классы операторов SP-GiST
Имя | Индексируемые операторы | Операторы упорядочивания |
---|---|---|
box_ops | << (box,box) | <-> (box,point) |
&< (box,box) | ||
&> (box,box) | ||
>> (box,box) | ||
<@ (box,box) | ||
@> (box,box) | ||
~= (box,box) | ||
&& (box,box) | ||
<<| (box,box) | ||
&<| (box,box) | ||
|&> (box,box) | ||
|>> (box,box) | ||
inet_ops | << (inet,inet) | |
<<= (inet,inet) | ||
>> (inet,inet) | ||
>>= (inet,inet) | ||
= (inet,inet) | ||
<> (inet,inet) | ||
< (inet,inet) | ||
<= (inet,inet) | ||
> (inet,inet) | ||
>= (inet,inet) | ||
&& (inet,inet) | ||
kd_point_ops | |>> (point,point) | <-> (point,point) |
<< (point,point) | ||
>> (point,point) | ||
<<| (point,point) | ||
~= (point,point) | ||
<@ (point,box) | ||
poly_ops | << (polygon,polygon) | <-> (polygon,point) |
&< (polygon,polygon) | ||
&> (polygon,polygon) | ||
>> (polygon,polygon) | ||
<@ (polygon,polygon) | ||
@> (polygon,polygon) | ||
~= (polygon,polygon) | ||
&& (polygon,polygon) | ||
<<| (polygon,polygon) | ||
&<| (polygon,polygon) | ||
|>> (polygon,polygon) | ||
|&> (polygon,polygon) | ||
quad_point_ops | |>> (point,point) | <-> (point,point) |
<< (point,point) | ||
>> (point,point) | ||
<<| (point,point) | ||
~= (point,point) | ||
<@ (point,box) | ||
range_ops | = (anyrange,anyrange) | |
&& (anyrange,anyrange) | ||
@> (anyrange,anyelement) | ||
@> (anyrange,anyrange) | ||
<@ (anyrange,anyrange) | ||
<< (anyrange,anyrange) | ||
>> (anyrange,anyrange) | ||
&< (anyrange,anyrange) | ||
&> (anyrange,anyrange) | ||
-|- (anyrange,anyrange) | ||
text_ops | = (text,text) | |
< (text,text) | ||
<= (text,text) | ||
> (text,text) | ||
>= (text,text) | ||
~<~ (text,text) | ||
~<=~ (text,text) | ||
~>=~ (text,text) | ||
~>~ (text,text) | ||
^@ (text,text) |
Из двух классов операторов для типа point
классом по умолчанию является quad_point_ops
. Класс kd_point_ops
поддерживает те же операторы, но использует другую структуру данных индекса, которая может дать выигрыш в скорости для некоторых приложений.
Классы операторов quad_point_ops
, kd_point_ops
и poly_ops
поддерживают оператор упорядочивания <->
, позволяющий выполнить поиск k ближайших соседей (k-NN
) по индексированному набору точек или многоугольников.
64.3.3. Расширяемость #
SP-GiST предлагает интерфейс с высоким уровнем абстракции и таким образом требует от разработчика метода доступа реализовать только методы, специфичные для конкретного типа данных. Ядро SP-GiST отвечает за эффективную схему обращений к диску и поиск в структуре дерева, а также берёт на себя заботу о параллельном доступе и поддержке журнала.
Кортежи в листьях дерева SP-GiST обычно содержат значения того же типа данных, что и индексируемый столбец, но могут содержать и неточное представление индексируемого столбца. На верхнем уровне эти кортежи содержат исходное индексируемое значение данных, но на более нижних могут содержать только часть значения, например, суффикс. В этом случае опорные функции класса операторов должны уметь восстанавливать исходное значение, собирая его из внутренних кортежей, которые нужно пройти для достижения уровня конкретного листа.
Когда создаётся индекс SP-GiST с неключевыми столбцами (INCLUDE
), значения этих столбцов также будут храниться в кортежах уровня листьев. Класс операторов SP-GiST не обращает внимания на неключевые столбцы, поэтому здесь они рассматриваться не будут.
Внутренние кортежи устроены сложнее, так как они представляют собой точки разветвления в дереве поиска. Каждый внутренний кортеж содержит набор из одного или нескольких узлов, представляющих группы сходных значений листьев. Узел содержит ответвление, приводящее либо к другому, внутреннему кортежу нижнего уровня, либо к короткому списку кортежей в листьях, лежащих в одной странице индекса. Для каждого узла обычно задаётся метка, описывающая его; например, в префиксном дереве меткой может быть очередной символ в строковом значении. (С другой стороны, класс операторов может опускать метки узлов, если он имеет дело с фиксированным набором узлов во всех внутренних кортежах; см. Подраздел 64.3.4.2.) Дополнительно внутренний кортеж может хранить префикс, описывающий все его члены. В префиксном дереве это может быть общий префикс всех представленных ниже строк. Значением префикса не обязательно должен быть префикс, а могут быть любые данные, требующиеся классу операторов; например, в дереве квадрантов это может быть центральная точка, от которой отмеряются четыре квадранта. В этом случае внутренний кортеж дерева квадрантов будет также содержать четыре узла, соответствующие квадрантам вокруг этой центральной точки.
Некоторые алгоритмы деревьев требует знания уровня (или глубины) текущего кортежа, так что ядро SP-GiST даёт возможность классам операторов контролировать число уровней при спуске по дереву. Также имеется поддержка пошагового восстановления представленного значения, когда это требуется, и передачи вниз дополнительных данных (так называемых переходящих значений) при спуске.
Примечание
Ядро SP-GiST берёт на себя заботу о значениях NULL. Хотя в индексах SP-GiST не хранятся записи для NULL в индексируемых столбцах, это скрыто от кода класса операторов; записи индексов или условия поиска с NULL никогда не передаются методам класса операторов. (Предполагается, что операторы SP-GiST строгие и не могут возвращать положительный результат для значений NULL.) Поэтому значения NULL здесь больше обсуждаться не будут.
Класс операторов индекса для SP-GiST должен предоставить пять методов и может дополнительно предоставить ещё два. Все пять обязательных методов должны по единому соглашению принимать два аргумента internal
, первым из которых будет указатель на структуру C, содержащую входные значения для опорного метода, а вторым — указатель на структуру C, в которую должны помещаться выходные значения. Четыре из этих методов должны возвращать просто void
, так как их результаты помещаются в выходную структуру; однако leaf_consistent
возвращает результат boolean
. Эти методы не должны менять никакие поля в их входных структурах. Выходная структура всегда обнуляется перед вызовом пользовательского метода. Необязательный шестой метод compress
принимает в единственном аргументе значение datum
, подлежащее индексированию, и возвращает значение, подходящее для физического хранения в кортеже уровня листьев. Необязательный седьмой метод options
принимает указатель типа internal
на структуру C, в которую должны помещаться параметры для класса операторов, и возвращает void
.
Пользователь должен определить следующие пять обязательных методов:
конфигурация
Возвращает статическую информацию о реализации индекса, включая OID типов данных префикса и метки узла.
В SQL эта функция должна объявляться так:
CREATE FUNCTION my_config(internal, internal) RETURNS void ...
В первом аргументе передаётся указатель на структуру
spgConfigIn
языка C, содержащие входные данные для функции. Во втором аргументе передаётся указатель на структуруspgConfigOut
языка C, в которую функция должна поместить результат.typedef struct spgConfigIn { Oid attType; /* Индексируемый тип данных */ } spgConfigIn; typedef struct spgConfigOut { Oid prefixType; /* Тип данных префикса во внутренних кортежах */ Oid labelType; /* Тип данных метки узла во внутренних кортежах */ Oid leafType; /* Тип данных в кортежах уровня листьев */ bool canReturnData; /* Класс операторов может восстановить исходные данные */ bool longValuesOK; /* Класс может принимать значения, не умещающиеся на одной странице */ } spgConfigOut;
Поле
attType
передаётся для поддержки полиморфных классов операторов; для обычных классов операторов с фиксированным типом оно будет всегда содержать одно значение и поэтому его можно просто игнорировать.Для классов операторов, не использующих префиксы, в
prefixType
можно установитьVOIDOID
. Подобным образом, для классов операторов, не использующих метки узлов, вlabelType
тоже можно установитьVOIDOID
. ПризнакcanReturnData
следует установить, если класс операторов может восстановить изначально переданное в индекс значение. ПризнакlongValuesOK
должен устанавливаться, только еслиattType
переменной длины и класс операторов может фрагментировать длинные значения, повторяя суффиксы (см. Подраздел 64.3.4.1).Значение
leafType
должно соответствовать типу хранения индекса, заданному в полеopckeytype
записи, которая описывает этот класс операторов в каталоге. (Обратите внимание, чтоopckeytype
может быть нулевым, тогда тип хранения определяется входным типом класса операторов, как бывает чаще всего.) Для обеспечения обратной совместимости методуconfig
разрешается задатьleafType
другое значение (которое и будет использоваться); в результате содержимое индекса нельзя будет правильно идентифицировать в каталогах, поэтому данная возможность считается устаревшей. Кроме того, допускается оставитьleafType
неинициализированным (нулевым), что будет означать, что тип хранения индекса определяется значениемopckeytype
.Когда
attType
иleafType
различаются, должен предоставляться необязательный методcompress
. Методcompress
отвечает за преобразование данных, подлежащих индексации, из типаattType
в типleafType
.choose
Выбирает метод для добавления нового значения во внутренний кортеж.
В SQL эта функция должна объявляться так:
CREATE FUNCTION my_choose(internal, internal) RETURNS void ...
В первом аргументе передаётся указатель на структуру
spgChooseIn
языка C, содержащую входные данные для функции. Во втором аргументе передаётся указатель на структуруspgChooseOut
, в которую функция должна поместить результат.typedef struct spgChooseIn { Datum datum; /* исходное значение, которое должно индексироваться */ Datum leafDatum; /* текущее значение, которое должно сохраниться в листе */ int level; /* текущий уровень (начиная с нуля) */ /* Данные из текущего внутреннего кортежа */ bool allTheSame; /* кортеж с признаком все-равны? */ bool hasPrefix; /* у кортежа есть префикс? */ Datum prefixDatum; /* если да, то это значение префикса */ int nNodes; /* число узлов во внутреннем кортеже */ Datum *nodeLabels; /* значения меток узлов (NULL, если их нет) */ } spgChooseIn; typedef enum spgChooseResultType { spgMatchNode = 1, /* спуститься в существующий узел */ spgAddNode, /* добавить узел во внутренний кортеж */ spgSplitTuple /* разделить внутренний кортеж (изменить его префикс) */ } spgChooseResultType; typedef struct spgChooseOut { spgChooseResultType resultType; /* код действия, см. выше */ union { struct /* результаты для spgMatchNode */ { int nodeN; /* спуститься к этому узлу (нумерация с 0) */ int levelAdd; /* шаг увеличения уровня */ Datum restDatum; /* новое значение листа */ } matchNode; struct /* результаты для spgAddNode */ { Datum nodeLabel; /* метка нового узла */ int nodeN; /* куда вставлять её (нумерация с 0) */ } addNode; struct /* результаты для spgSplitTuple */ { /* Информация для формирования нового внутреннего кортежа верхнего уровня с одним дочерним кортежем */ bool prefixHasPrefix; /* кортеж должен иметь префикс? */ Datum prefixPrefixDatum; /* если да, его значение */ int prefixNNodes; /* число узлов */ Datum *prefixNodeLabels; /* их метки (или NULL, если * меток нет) */ int childNodeN; /* узел, который получит дочерний кортеж */ /* Информация для формирования нового внутреннего кортежа нижнего уровня со всеми старыми узлами */ bool postfixHasPrefix; /* кортеж должен иметь префикс? */ Datum postfixPrefixDatum; /* если да, его значение */ } splitTuple; } result; } spgChooseOut;
В
datum
передаётся исходное значение типаspgConfigIn
.attType
, которое должно быть вставлено в индекс. ВleafDatum
содержится значение типаspgConfigOut
.leafType
, изначально представляющее собой результат методаcompress
, применённого кdatum
, если методcompress
реализован, а иначе — собственно значениеdatum
.leafDatum
может быть другим на нижних уровнях дерева, если его изменят функцииchoose
илиpicksplit
. Когда поиск места добавления достигает страницы уровня листа, в создаваемом кортеже листа сохраняется текущее значениеleafDatum
. Вlevel
задаётся текущий уровень внутреннего кортежа, начиная с нуля для уровня корня. ПризнакallTheSame
устанавливается, если текущий внутренний кортеж содержит несколько равнозначных узлов (см. Подраздел 64.3.4.3). ПризнакhasPrefix
устанавливается, если текущий внутренний кортеж содержит префикс; в этом случае вprefixDatum
задаётся его значение. ПолеnNodes
задаёт число дочерних узлов, содержащихся во внутреннем кортеже, аnodeLabels
представляет массив их меток или NULL, если меток у них нет.Функция
choose
может определить, соответствует ли новое значение одному из существующих дочерних узлов, или что нужно добавить новый дочерний узел, или что новое значение не согласуется с префиксом кортежа и внутренний кортеж нужно разделить, чтобы получить менее ограничивающий префикс.Если новое значение соответствует одному из существующих дочерних узлов, установите в
resultType
значениеspgMatchNode
. Установите вnodeN
номер этого узла в массиве узлов (нумерация начинается с нуля). Установите вlevelAdd
значение, на которое должен увеличиваться уровень (level
) при спуске через этот узел, либо оставьте его нулевым, если класс операторов не отслеживает уровни. УстановитеrestDatum
, равнымleafDatum
, если класс операторов не меняет значения данных от уровня к уровню, а в противном случае запишите в него изменённое значение, которое должно использоваться в качествеleafDatum
на следующем уровне.Если нужно добавить новый дочерний узел, установите в
resultType
значениеspgAddNode
. ВnodeLabel
задайте метку для нового узла, а вnodeN
позицию (отсчитываемую от нуля), в которую должен вставляться узел в массиве узлов. После того как узел будет добавлен, функцияchoose
вызывается снова с изменённым внутренним кортежем; в результате этого вызова должен быть получен результатspgMatchNode
.Если новое значение не согласуется с префиксом кортежа, установите в
resultType
значениеspgSplitTuple
. Это действие приводит к перемещению всех существующих узлов в новый внутренний кортеж нижнего уровня и замене существующего внутреннего кортежа кортежем, содержащим одну ссылку вниз на новый внутренний кортеж. Установите признакprefixHasPrefix
, чтобы указать, должен ли новый верхний кортеж иметь префикс, и если да, задайте вprefixPrefixDatum
значение префикса. Это новое значение префикса должно быть в достаточной мере менее ограничивающим, чем исходное, чтобы в индекс было принято новое значение. Запишите вprefixNNodes
число требующихся узлов в новом кортеже, а вprefixNodeLabels
— указатель на выделенный через palloc массив с их метками или NULL, если метки узлов не нужны. Заметьте, что общий размер нового кортежа верхнего уровня не должен превышать общий размер кортежа, который он замещает; это ограничивает длины нового префикса и новых меток. Установите вchildNodeN
индекс (начиная с нуля) узла, который будет ссылаться на новый внутренний кортеж нижнего уровня. Установите признакpostfixHasPrefix
, чтобы указать, должен ли новый внутренний кортеж нижнего уровня иметь префикс, и если да, задайте вpostfixPrefixDatum
значение префикса. Сочетание этих двух префиксов и метки узла, ссылающегося вниз, (если она есть) должно иметь то же значение, что и исходный префикс, так как нет возможности ни изменить метки узлов, перемещённых в новый кортеж нижнего уровня, ни изменить какие-либо нижние записи индекса. После того как узел разделён, функцияchoose
будет вызвана снова с заменяемым внутренним кортежем. При этом вызове может быть возвращён результатspgAddNode
, если подходящий узел не был создан действиемspgSplitTuple
. В конце концовchoose
должна вернутьspgMatchNode
, чтобы операция добавления могла перейти на следующий уровень.picksplit
Выбирает, как создать новый внутренний кортеж по набору кортежей в листьях.
В SQL эта функция должна объявляться так:
CREATE FUNCTION my_picksplit(internal, internal) RETURNS void ...
В первом аргументе передаётся указатель на структуру
spgPickSplitIn
языка C, содержащую входные данные для функции. Во втором аргументе передаётся указатель на структуруspgPickSplitOut
языка C, в которую функция должна поместить результат.typedef struct spgPickSplitIn { int nTuples; /* число кортежей в листьях */ Datum *datums; /* их значения (массив длины nTuples) */ int level; /* текущий уровень (отсчитывая от 0) */ } spgPickSplitIn; typedef struct spgPickSplitOut { bool hasPrefix; /* новый внутренний кортеж должен иметь префикс? */ Datum prefixDatum; /* если да, его значение */ int nNodes; /* число узлов для нового внутреннего кортежа */ Datum *nodeLabels; /* их метки (или NULL, если их нет) */ int *mapTuplesToNodes; /* номер узла для каждого кортежа в листе */ Datum *leafTupleDatums; /* значения, помещаемые в каждый новый кортеж */ } spgPickSplitOut;
В
nTuples
задаётся число предоставленных кортежей уровня листьев, а вdatums
— массив их значений типаspgConfigOut
.leafType
. Вlevel
указывается текущий уровень, который должны разделять все кортежи листьев, и который станет уровнем нового внутреннего кортежа.Установите признак
hasPrefix
, чтобы указать, должен ли новый внутренний кортеж иметь префикс, и если да, задайте вprefixDatum
значение префикса. Установите вnNodes
количество узлов, которые будут содержаться во внутреннем кортеже, а вnodeLabels
— массив значений их меток либо NULL, если узлам не нужны метки. Поместите вmapTuplesToNodes
указатель на массив, назначающий номера узлов (начиная с нуля) каждому кортежу листа. ВleafTupleDatums
передайте массив значений, которые должны быть сохранены в новых кортежах листьев (они будут совпадать со входными значениями (datums
), если класс операторов не изменяет значения от уровня к следующему). Заметьте, что функцияpicksplit
сама должна выделить память, используя palloc, для массивовnodeLabels
,mapTuplesToNodes
иleafTupleDatums
.Если передаётся несколько кортежей листьев, ожидается, что функция
picksplit
классифицирует их и разделит на несколько узлов; иначе нельзя будет разнести кортежи листьев по разным страницам, что является конечной целью этой операции. Таким образом, еслиpicksplit
в итоге помещает все кортежи листьев в один узел, ядро SP-GiST меняет это решение и создаёт внутренний кортеж, в котором кортежи листьев связываются случайным образом с несколькими узлами с одинаковыми метками. Такой кортеж помечается флагомallTheSame
, показывающим, что все узлы равны. Функцииchoose
иinner_consistent
должны работать с такими внутренними кортежами особым образом. За дополнительными сведениями обратитесь к Подразделу 64.3.4.3.picksplit
может применяться к одному кортежу на уровне листьев, только когда функцияconfig
установила вlongValuesOK
значение true и было передано входное значение, большее страницы. В этом случае цель операции — отделить префикс и получить новое, более короткое значение для листа. Этот вызов будет повторяться, пока значение уровня листа не уменьшится настолько, чтобы уместиться в странице. За дополнительными сведениями обратитесь к Подразделу 64.3.4.1.inner_consistent
Возвращает набор узлов (ветвей), по которым надо продолжать поиск.
В SQL эта функция должна объявляться так:
CREATE FUNCTION my_inner_consistent(internal, internal) RETURNS void ...
В первом аргументе передаётся указатель на структуру
spgInnerConsistentIn
языка C, содержащую входные данные для функции. Во втором аргументе передаётся указатель на структуруspgInnerConsistentOut
языка C, в которую функция должна поместить результат.typedef struct spgInnerConsistentIn { ScanKey scankeys; /* массив операторов и искомых значений */ ScanKey orderbys; /* массив операторов упорядочивания и * сравниваемых значений */ int nkeys; /* длина массива scankeys */ int norderbys; /* длина массива orderbys */ Datum reconstructedValue; /* значение, восстановленное для родителя */ void *traversalValue; /* переходящее значение, специфичное для класса операторов */ MemoryContext traversalMemoryContext; /* переходящие значения нужно помещать сюда */ int level; /* текущий уровень (отсчитывается от нуля) */ bool returnData; /* нужно ли возвращать исходные данные? */ /* Данные из текущего внутреннего кортежа */ bool allTheSame; /* кортеж с признаком все-равны? */ bool hasPrefix; /* у кортежа есть префикс? */ Datum prefixDatum; /* если да, то это значение префикса */ int nNodes; /* число узлов во внутреннем кортеже */ Datum *nodeLabels; /* значения меток узлов (NULL, если их нет) */ } spgInnerConsistentIn; typedef struct spgInnerConsistentOut { int nNodes; /* число дочерних узлов, которые нужно посетить */ int *nodeNumbers; /* их номера в массиве узлов */ int *levelAdds; /* шаги увеличения уровня для этих узлов */ Datum *reconstructedValues; /* связанные восстановленные значения */ void **traversalValues; /* переходящие значения, специфичные для класса операторов */ double **distances; /* связанные расстояния */ } spgInnerConsistentOut;
Массив
scankeys
длиныnkeys
описывает условия поиска по индексу. Эти условия объединяются операцией И — найдены должны быть только те записи, которые удовлетворяют всем условиям. (Заметьте, что сnkeys
= 0 подразумевается, что запросу удовлетворяют все записи в индексе.) Обычно эту функцию интересуют только поляsk_strategy
иsk_argument
в каждой записи массива, в которых определяется соответственно индексируемый оператор и искомое значение. В частности, нет необходимости проверятьsk_flags
, чтобы распознать NULL в искомом значении, так как ядро SP-GiST отфильтрует такие условия. Массивorderbys
длиныnorderbys
подобным образом описывает упорядочивающие операторы (если они есть). ВreconstructedValue
передаётся значение, восстановленное для родительского кортежа; это может быть(Datum) 0
на уровне корня или если функцияinner_consistent
не установила значение на предыдущем уровне. ВtraversalValue
передаётся указатель на переходящие данные, полученные из предыдущего вызоваinner_consistent
для родительского кортежа индекса, либо NULL на уровне корня. ПолеtraversalMemoryContext
указывает на контекст памяти, в котором нужно сохранить выходные переходящие данные (см. ниже). Вlevel
передаётся уровень текущего внутреннего кортежа (уровень корня считается нулевым). ФлагreturnData
устанавливается, когда для этого запроса нужно получить восстановленные данные; это возможно, только если функцияconfig
установила признакcanReturnData
. ПризнакallTheSame
устанавливается, если текущий внутренний кортеж имеет пометку «все-равны»; в этом случае все узлы имеют одну метку (если имеют) и значит, либо все они, либо никакой не соответствует запросу (см. Подраздел 64.3.4.3). ПризнакhasPrefix
устанавливается, если текущий внутренний кортеж содержит префикс; в этом случае вprefixDatum
находится его значение. ВnNodes
задаётся число дочерних узлов, содержащихся во внутреннем кортеже, а вnodeLabels
— массив их меток либо NULL, если они не имеют меток.В
nNodes
нужно записать число дочерних узлов, которые потребуется посетить при поиске, а вnodeNumbers
— массив их индексов. Если класс операторов отслеживает уровни, вlevelAdds
нужно передать массив с шагами увеличения уровня при посещении каждого узла. (Часто шаг будет одним для всех узлов, но может быть и по-другому, поэтому применяется массив.) Если потребовалось восстановить значения, поместите вreconstructedValues
массив значений, восстановленных для каждого дочернего узла, который нужно посетить; в противном случае оставьтеreconstructedValues
равным NULL. Предполагается, что восстановленные значения имеют типspgConfigOut
.leafType
. (Однако ядро системы ничего не будет делать с ними, кроме как, возможно, копировать, поэтому они должны иметь такие жеtyplen
иtypbyval
, что иleafType
.) Если выполняется поиск с упорядочиванием, поместите вdistances
массив расстояний в соответствии с массивомorderbys
(узлы с меньшими расстояниями будут обрабатываться первыми). В противном случае оставьте в этом поле NULL. Если желательно передать дополнительные данные («переходящие значения») на нижние уровни при поиске по дереву, поместите вtraversalValues
указатель на массив соответствующих переходящих значений, по одному для каждого дочернего узла, который нужно посетить; в противном случае оставьте вtraversalValues
значение NULL. Заметьте, что функцияinner_consistent
сама должна выделять память, используя palloc, для массивовnodeNumbers
,levelAdds
,distances
,reconstructedValues
иtraversalValues
в текущем контексте памяти. Однако выходные переходящие значения, на которые указывает массивtraversalValues
, должны размещаться в контекстеtraversalMemoryContext
. При этом каждое переходящее значения должно располагаться в отдельном блоке памяти palloc.leaf_consistent
Возвращает true, если кортеж листа удовлетворяет запросу.
В SQL эта функция должна объявляться так:
CREATE FUNCTION my_leaf_consistent(internal, internal) RETURNS bool ...
В первом аргументе передаётся указатель на структуру
spgLeafConsistentIn
языка C, содержащую входные данные для функции. Во втором аргументе передаётся указатель на структуруspgLeafConsistentOut
языка C, в которую функция должна поместить результат.typedef struct spgLeafConsistentIn { ScanKey scankeys; /* массив операторов и искомых значений */ ScanKey orderbys; /* массив операторов упорядочивания и * сравниваемых значений */ int nkeys; /* длина массива scankeys */ int norderbys; /* длина массива orderbys */ Datum reconstructedValue; /* значение, восстановленное для родителя */ void *traversalValue; /* переходящее значение, специфичное для класса операторов */ int level; /* текущий уровень (отсчитывая от нуля) */ bool returnData; /* нужно ли возвращать исходные данные? */ Datum leafDatum; /* значение в кортеже листа */ } spgLeafConsistentIn; typedef struct spgLeafConsistentOut { Datum leafValue; /* восстановленные исходные данные, при наличии */ bool recheck; /* true, если оператор нужно перепроверить */ bool recheckDistances; /* true, если расстояния нужно перепроверить */ double *distances; /* связанные расстояния */ } spgLeafConsistentOut;
Массив
scankeys
длиныnkeys
описывает условия поиска по индексу. Эти условия объединяются операцией И — запросу удовлетворяют только те записи в индексе, которые удовлетворяют всем этим условиям. (Заметьте, что сnkeys
= 0 подразумевается, что запросу удовлетворяют все записи в индексе.) Обычно эту функцию интересуют только поляsk_strategy
иsk_argument
в каждой записи массива, в которых определяются соответственно индексируемый оператор и искомое значение. В частности, нет необходимости проверятьsk_flags
, чтобы распознать NULL в искомом значении, так как ядро SP-GiST отфильтрует такие условия. Массивorderbys
длиныnorderbys
подобным образом описывает упорядочивающие операторы. ВreconstructedValue
передаётся значение, восстановленное для родительского кортежа; это может быть(Datum) 0
на уровне корня или если функцияinner_consistent
не установила значение на предыдущем уровне. ВtraversalValue
передаётся указатель на переходящие данные, полученные из предыдущего вызоваinner_consistent
для родительского кортежа индекса, либо NULL на уровне корня. Вlevel
передаётся уровень текущего внутреннего кортежа (уровень корня считается нулевым). ФлагreturnData
устанавливается, когда для этого запроса нужно получить восстановленные данные; это возможно, только если функцияconfig
установила признакcanReturnData
. ВleafDatum
передаётся значение ключа, записанное в текущем кортеже листа.Эта функция должна вернуть
true
, если кортеж листа соответствует запросу, илиfalse
в противном случае. В случае положительного результата, если в полеreturnData
переданоtrue
, нужно поместить вleafValue
значение (типаspgConfigIn
.attType
), изначально переданное для индексации в этот кортеж. Кроме того, флагуrecheck
можно присвоитьtrue
, если соответствие неточное, так что для установления точного результата проверки нужно повторно применить оператор(ы) к собственно кортежу данных. Если выполняется упорядочивающий поиск, поместите вdistances
массив со значениями расстояния, соответствующими массивуorderbys
. В противном случае оставьте в этом поле NULL. Если хотя бы одно из возвращаемых расстояний определено неточно, присвойте true полюrecheckDistances
. В этом случае исполнитель вычислит точные расстояния после получения кортежа из кучи и переупорядочит кортежи, если потребуется.
Дополнительно пользователь может определить методы:
Datum compress(Datum in)
Преобразует элемент данных в формат, подходящий для физического хранения в кортеже уровня листьев в индексе. Эта функция принимает значение типа
spgConfigIn
.attType
и возвращает значение типаspgConfigOut
.leafType
. Возвращаемое значение не должно содержать указатель на внешние TOAST-данные.Обратите внимание, что метод
compress
применяется только к сохраняемым значениям. Методы, оценивающие согласованность, получают сканируемые в запросе ключи (scankeys
) неизменёнными, без обработки функциейcompress
.options
Определяет набор видимых пользователю параметров, управляющих поведением класса операторов.
В SQL эта функция должна объявляться так:
CREATE OR REPLACE FUNCTION my_options(internal) RETURNS void AS 'MODULE_PATHNAME' LANGUAGE C STRICT;
Этой функции передаётся указатель на структуру
local_relopts
, в которую нужно внести набор параметров, относящихся к классу операторов. Обращаться к этим параметрам из других опорных функций можно с помощью макросовPG_HAS_OPCLASS_OPTIONS()
иPG_GET_OPCLASS_OPTIONS()
.Так как в SP-GiST представление ключа допускает гибкость, могут быть полезны параметры для настройки этого индекса.
Все опорные методы SP-GiST обычно вызываются в кратковременных контекстах памяти; то есть CurrentMemoryContext
сбрасывается после обработки каждого кортежа. Таким образом, можно не заботиться об освобождении любых блоков памяти, выделенных функцией palloc. (Метод config
является исключением: в нём нужно не допускать утечек памяти. Но обычно метод config
не делает ничего, кроме как присваивает константы переданной структуре параметров.)
Если индексируемый столбец имеет сортируемый тип данных, правило сортировки индекса будет передаваться всем опорным методам, используя стандартный механизм PG_GET_COLLATION()
.
64.3.4. Реализация #
В этом разделе освещаются тонкости реализации и особенности, о которых полезно знать тем, кто будет реализовывать классы операторов SP-GiST.
64.3.4.1. Ограничения SP-GiST #
Отдельные кортежи листьев и внутренние кортежи должны умещаться в одной странице индекса (по умолчанию её размер 8 Кбайт). Таким образом при индексировании значений типов данных переменной длины большие значения могут поддерживаться только такими схемами, как префиксные деревья, в которых каждый уровень дерева включает префикс, достаточно короткий для помещения в страницу, и на конечном уровне листьев содержится суффикс, который также достаточно мал, чтобы поместиться в странице. Класс операторов должен устанавливать признак longValuesOK
, только если он готов организовывать такую структуру. Если этот признак не установлен, ядро SP-GiST не примет запрос на индексацию значения, которое слишком велико для одной страницы индекса.
Также класс операторов должен отвечать за то, чтобы внутренние кортежи при расширении не выходили за пределы страницы индекса; это ограничивает число дочерних узлов, которые могут принадлежать одному внутреннему кортежу, а также максимальный размер значения префикса.
Ещё одно ограничение состоит в том, что когда узел внутреннего кортежа указывает на набор кортежей листьев, все эти кортежи должны находиться в одной странице индекса. (Это конструктивное ограничение введено для оптимизации позиционирования и экономии места на ссылках, связывающих такие кортежи вместе.) Если набор кортежей листьев оказывается слишком большим для одной страницы, выполняется разделение и вставляется промежуточный внутренний кортеж. Чтобы устранить возникшую проблему, новый внутренний кортеж должен разделять набор значений в листе на несколько групп узлов. Если функция picksplit
класса операторов не может сделать это, ядро SP-GiST переходит к чрезвычайным мерам, описанным в Подразделе 64.3.4.3.
Когда longValuesOK
имеет значение true, ожидается, что последующие уровни дерева SP-GiST будут включать всё больше и больше информации в префиксы и метки узлов внутренних кортежей, постепенно уменьшая значение, которое нужно сохранить на уровне листьев, чтобы оно в конце концов уместилось на странице. Чтобы в случае ошибки в классах операторах исключить бесконечные циклы при добавлении записи, ядро SP-GiST выдаст ошибку, если значение для листа не уменьшится за 10 вызовов метода choose
.
64.3.4.2. SP-GiST без меток узлов #
В некоторых древовидных схемах каждый внутренний кортеж содержит фиксированный набор узлов; например, в дереве квадрантов это всегда четыре узла, соответствующие четырём квадрантам вокруг центральной точки внутреннего кортежа. В таком случае код обычно работает с узлами по номерам и необходимости в явных метках узлов нет. Чтобы убрать метки узлов (и таким образом сэкономить место), функция picksplit
может возвратить NULL вместо массива nodeLabels
, а функция choose
аналогично может возвратить NULL вместо массива prefixNodeLabels
во время действия spgSplitTuple
. В результате при последующих вызовах функций choose
и inner_consistent
им вместо nodeLabels
будет передаваться NULL. В принципе метки узлов могут применяться для одних внутренних кортежей и отсутствовать у других в том же индексе.
Когда внутренний кортеж содержит узлы без меток, функция choose
не может выбрать действие spgAddNode
, так как в этом случае предполагается, что набор узлов фиксированный.
64.3.4.3. Внутренние кортежи «все-равны» #
Ядро SP-GiST может переопределить результаты функции picksplit
класса операторов, когда эта функция не может разделить поступившие значения листьев на минимум две категории узлов. Когда это происходит, создаётся новый внутренний кортеж с несколькими узлами, каждый из которых имеет одну метку (если имеет), которую picksplit
дала одному узлу, а значения листьев распределяются случайно между этими равнозначными узлами. Для этого внутреннего кортежа устанавливается флаг allTheSame
, который предупреждает функции choose
и inner_consistent
, что кортеж не содержит набор узлов, который они обычно ожидают.
Когда обрабатывается кортеж с флагом allTheSame
, выбранное функцией choose
действие spgMatchNode
воспринимается как указание, что новое значение можно присвоить одному из равнозначных узлов; код ядра будет игнорировать полученное значение nodeN
и спустится в один из узлов, выбранный случайно (чтобы дерево было сбалансированным). Будет считаться ошибкой, если choose
выберет действие spgAddNode
, так как при этом не все узлы окажутся равны; если добавляемое значение не соответствует существующим узлам, должно выбираться действие spgSplitTuple
.
Также, когда обрабатывается кортеж с флагом allTheSame
, функция inner_consistent
должна вернуть все или не возвращать никакие узлы для продолжения поиска по индексу, так как все узлы равнозначны. Для этого может потребоваться, а может и не потребоваться код обработки особого случая, в зависимости от того, как inner_consistent
обычно воспринимает узлы.
64.3.5. Примеры #
Дистрибутив исходного кода PostgreSQL содержит несколько примеров классов операторов индекса SP-GiST, перечисленных в Таблице 64.2. Код их реализации вы можете найти в src/backend/access/spgist/
и src/backend/utils/adt/
.