62.3. Индексы SP-GiST#
62.3. Индексы SP-GiST #
62.3.1. Введение #
SP-GiST - это сокращение от пространственно-секционированного GiST. SP-GiST поддерживает секционированные деревья поиска, которые облегчают разработку широкого спектра различных несбалансированных структур данных, таких как квад-деревья, k-d деревья и радикс деревья (tries). Общей особенностью этих структур является то, что они повторно делят пространство поиска на секции, которые не обязательно имеют одинаковый размер. Поиски, которые хорошо соответствуют правилу секционирования, могут быть очень быстрыми.
Эти популярные структуры данных изначально были разработаны для использования в памяти. В оперативной памяти они обычно представляют собой набор динамически выделенных узлов, связанных указателями. Это не подходит для прямого хранения на диске, поскольку эти цепочки указателей могут быть достаточно длинными, что потребует слишком много обращений к диску. В отличие от этого, структуры данных, основанные на диске, должны иметь высокий коэффициент ветвления, чтобы минимизировать ввод-вывод. Задача, решаемая SP-GiST, заключается в том, чтобы отображать узлы дерева поиска на страницы диска таким образом, чтобы поиск требовал доступа только к нескольким страницам диска, даже если он проходит через множество узлов.
Подобно GiST, SP-GiST предназначен для разработки пользовательских типов данных с соответствующими методами доступа, экспертом в области данного типа данных, а не экспертом баз данных.
Некоторая приведенная информация взята из проекта индексирования SP-GiST университета Пёрдью веб-сайта. Реализация SP-GiST в PostgreSQL в основном поддерживается Федором Сигаевым и Олегом Бартуновым; более подробно см. web site.
62.3.2. Встроенные классы операторов #
Содержание основного дистрибутива PostgreSQL включает классы операторов SP-GiST, показанные в таблице Таблица 62.2.
Таблица 62.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
)
в индексированных наборах данных точек или полигонов.
62.3.3. Расширяемость #
SP-GiST предлагает интерфейс с высоким уровнем абстракции, требуя от разработчика метода доступа реализовать только методы, специфичные для определенного типа данных. Основная часть SP-GiST отвечает за эффективное отображение на диске и поиск в структуре дерева. Он также заботится о параллельности и рассмотрении журнала.
Все листовые кортежи дерева SP-GiST обычно содержат значения того же типа данных, что и индексируемый столбец, хотя также возможно, что они содержат упрощенные представления индексируемого столбца. Листовые кортежи, хранящиеся на корневом уровне, будут напрямую представлять исходное значение индексируемых данных, но листовые кортежи на более низких уровнях могут содержать только частичное значение, например, суффикс. В этом случае функции поддержки класса операторов должны быть способны восстановить исходное значение, используя информацию, накопленную из внутренних кортежей, которые передаются для достижения листового уровня.
Когда индекс SP-GiST создается с использованием
колонок INCLUDE
, значения этих колонок также
хранятся в листовых кортежах. Колонки INCLUDE
не
имеют значения для класса операторов SP-GiST, поэтому
они здесь не обсуждаются далее.
Внутренние кортежи более сложны, поскольку они являются точками разветвления в дереве поиска. Каждый внутренний кортеж содержит набор одного или более узлов, которые представляют группы похожих листовых значений. Узел содержит ссылку, которая ведет либо к другому, более низкоуровневому внутреннему кортежу, либо к короткому списку листовых кортежей, которые все находятся на одной странице индекса. Каждый узел обычно имеет метку, которая его описывает; например, в радиксном дереве меткой узла может быть следующий символ строки значения. (В качестве альтернативы, класс оператора может опустить метки узлов, если он работает с фиксированным набором узлов для всех внутренних кортежей; см. Раздел 62.3.4.2). По желанию, внутренний кортеж может иметь префиксное значение, которое описывает всех его членов. В радиксном дереве это может быть общий префикс представленных строк. Значение префикса не обязательно является действительным префиксом, но может быть любыми данными, необходимыми классу оператора; например, в квадродереве оно может хранить центральную точку, относительно которой измеряются четыре квадранта. Внутренний кортеж квадродерева также содержит четыре узла, соответствующих квадрантам вокруг этой центральной точки.
Некоторые алгоритмы деревьев требуют знания уровня (или глубины) текущей кортежа, поэтому ядро SP-GiST предоставляет возможность операторным классам управлять подсчетом уровня при спуске по дереву. Также поддерживается инкрементальное восстановление представленного значения, когда это необходимо, и передача дополнительных данных (называемых значениями обхода) во время спуска по дереву.
Примечание
Основной код SP-GiST заботится о пустых записях. Хотя индексы SP-GiST хранят записи для пустых значений в индексируемых столбцах, это скрыто от кода класса оператора индекса: никакие записи индекса или условия поиска для пустых значений никогда не передаются методам класса оператора. (Предполагается, что операторы SP-GiST являются строгими и поэтому не могут быть успешными для пустых значений). Пустые значения здесь далее не обсуждаются.
Всего существует пять пользовательских методов, которые должен предоставить класс операторов индекса для SP-GiST, и два из них являются необязательными. Все пять обязательных методов следуют соглашению о принятии двух аргументов типа internal
, первый из которых является указателем на структуру C, содержащую входные значения для метода поддержки, а второй аргумент является указателем на структуру C, в которую должны быть помещены выходные значения. Четыре из обязательных методов просто возвращают void
, так как все их результаты появляются в выходной структуре; но метод leaf_consistent
возвращает логическое значение boolean
. Методы не должны изменять никакие поля своих входных структур. Во всех случаях выходная структура инициализируется нулями перед вызовом пользовательского метода. Необязательный шестой метод compress
принимает значение типа datum
, которое должно быть проиндексировано, в качестве единственного аргумента и возвращает значение, подходящее для физического хранения в кортеже листа. Необязательный седьмой метод options
принимает указатель типа internal
на структуру C, в которую должны быть помещены параметры, специфичные для opclass, и возвращает void
.
Все пять обязательных пользовательских методов:
config
Возвращает статическую информацию о реализации индекса, включая типы данных OIDs префикса и типов данных меток узлов.
Декларация функции SQL должна выглядеть так:
CREATE FUNCTION my_config(internal, internal) RETURNS void ...
Первый аргумент - указатель на структуру C
spgConfigIn
, содержащую входные данные для функции. Второй аргумент - указатель на структуру CspgConfigOut
, которую функция должна заполнить данными результата.typedef struct spgConfigIn { Oid attType; /* Data type to be indexed */ } spgConfigIn; typedef struct spgConfigOut { Oid prefixType; /* Data type of inner-tuple prefixes */ Oid labelType; /* Data type of inner-tuple node labels */ Oid leafType; /* Data type of leaf-tuple values */ bool canReturnData; /* Opclass can reconstruct original data */ bool longValuesOK; /* Opclass can cope with values > 1 page */ } spgConfigOut;
attType
передается для поддержки полиморфных классов операторов индекса; для обычных классов операторов с фиксированным типом данных он всегда будет иметь одно и то же значение и поэтому может быть проигнорирован.Для классов операторов, которые не используют префиксы,
prefixType
может быть установлен вVOIDOID
. Аналогично, для классов операторов, которые не используют метки узлов,labelType
может быть установлен вVOIDOID
.canReturnData
должно быть установлено в true, если класс операторов способен восстановить исходное значение индекса.longValuesOK
должно быть установлено в true только тогда, когдаattType
имеет переменную длину, и класс операторов способен разделить длинные значения путем повторного добавления суффиксов (см. Раздел 62.3.4.1).Соответствие типа хранения индекса, определенного типом ключа операторного класса
opckeytype
, должно совпадать сleafType
в каталоге записи. (Обратите внимание, чтоopckeytype
может быть равен нулю, что означает, что тип хранения совпадает с типом ввода операторного класса, что является наиболее распространенной ситуацией). По соображениям обратной совместимости методconfig
может устанавливатьleafType
в другое значение, и это значение будет использоваться; но это устарело, так как содержимое индекса неправильно идентифицируется в каталогах. Также допускается оставитьleafType
неинициализированным (нулевым); это интерпретируется как означающее тип хранения индекса, производный отopckeytype
.Когда
attType
иleafType
отличаются, необходимо предоставить необязательный методcompress
. Методcompress
отвечает за преобразование данных, которые будут индексироваться, изattType
вleafType
.choose
Выбирает метод для вставки нового значения во внутренний кортеж.
Декларация функции SQL должна выглядеть так:
CREATE FUNCTION my_choose(internal, internal) RETURNS void ...
Первый аргумент - указатель на структуру C
spgChooseIn
, содержащую входные данные для функции. Второй аргумент - указатель на структуру CspgChooseOut
, которую функция должна заполнить данными результата.typedef struct spgChooseIn { Datum datum; /* original datum to be indexed */ Datum leafDatum; /* current datum to be stored at leaf */ int level; /* current level (counting from zero) */ /* Data from current inner tuple */ bool allTheSame; /* tuple is marked all-the-same? */ bool hasPrefix; /* tuple has a prefix? */ Datum prefixDatum; /* if so, the prefix value */ int nNodes; /* number of nodes in the inner tuple */ Datum *nodeLabels; /* node label values (NULL if none) */ } spgChooseIn; typedef enum spgChooseResultType { spgMatchNode = 1, /* descend into existing node */ spgAddNode, /* add a node to the inner tuple */ spgSplitTuple /* split inner tuple (change its prefix) */ } spgChooseResultType; typedef struct spgChooseOut { spgChooseResultType resultType; /* action code, see above */ union { struct /* results for spgMatchNode */ { int nodeN; /* descend to this node (index from 0) */ int levelAdd; /* increment level by this much */ Datum restDatum; /* new leaf datum */ } matchNode; struct /* results for spgAddNode */ { Datum nodeLabel; /* new node's label */ int nodeN; /* where to insert it (index from 0) */ } addNode; struct /* results for spgSplitTuple */ { /* Info to form new upper-level inner tuple with one child tuple */ bool prefixHasPrefix; /* tuple should have a prefix? */ Datum prefixPrefixDatum; /* if so, its value */ int prefixNNodes; /* number of nodes */ Datum *prefixNodeLabels; /* their labels (or NULL for * no labels) */ int childNodeN; /* which node gets child tuple */ /* Info to form new lower-level inner tuple with all old nodes */ bool postfixHasPrefix; /* tuple should have a prefix? */ Datum postfixPrefixDatum; /* if so, its value */ } splitTuple; } result; } spgChooseOut;
datum
- это исходный датумspgConfigIn
.attType
, который должен быть вставлен в индекс.leafDatum
- это значение типаspgConfigOut
.leafType
, которое изначально является результатом применения методаcompress
кdatum
, если методcompress
предоставлен, или то же значение, что иdatum
в противном случае.leafDatum
может изменяться на более низких уровнях дерева, если методыchoose
илиpicksplit
его изменяют. Когда поиск вставки достигает листовой страницы, текущее значениеleafDatum
будет сохранено во вновь созданном листовом кортеже.level
- это текущий уровень внутреннего кортежа, начиная с нуля для корневого уровня.allTheSame
- это значение true, если текущий внутренний кортеж помечен как содержащий несколько эквивалентных узлов (см. Раздел 62.3.4.3).hasPrefix
- это значение true, если текущий внутренний кортеж содержит префикс; если это так, то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 ...
Первый аргумент - указатель на структуру C
spgPickSplitIn
, содержащую входные данные для функции. Второй аргумент - указатель на структуру CspgPickSplitOut
, которую функция должна заполнить результатами.typedef struct spgPickSplitIn { int nTuples; /* number of leaf tuples */ Datum *datums; /* their datums (array of length nTuples) */ int level; /* current level (counting from zero) */ } spgPickSplitIn; typedef struct spgPickSplitOut { bool hasPrefix; /* new inner tuple should have a prefix? */ Datum prefixDatum; /* if so, its value */ int nNodes; /* number of nodes for new inner tuple */ Datum *nodeLabels; /* their labels (or NULL for no labels) */ int *mapTuplesToNodes; /* node index for each leaf tuple */ Datum *leafTupleDatums; /* datum to store in each new leaf tuple */ } spgPickSplitOut;
nTuples
- это количество предоставленных листовых кортежей.datums
- это массив значений их данных для типаspgConfigOut
.leafType
.level
- это текущий уровень, который все листовые кортежи разделяют, и который станет уровнем нового внутреннего кортежа.Установите
hasPrefix
для указания, должен ли новый внутренний кортеж иметь префикс, и если да, установитеprefixDatum
в значение префикса. УстановитеnNodes
для указания количества узлов, которые будут содержаться в новом внутреннем кортеже, и установитеnodeLabels
в массив их меток значений или в NULL, если метки узлов не требуются. УстановитеmapTuplesToNodes
в массив, который указывает индекс (от нуля) узла, к которому должен быть присвоен каждый листовой кортеж. УстановитеleafTupleDatums
в массив значений, которые должны быть сохранены в новых листовых кортежах (они будут такими же, какdatums
ввода, если класс оператора не изменяет значения от одного уровня к другому). Обратите внимание, что функцияpicksplit
отвечает за выделение памяти для массивовnodeLabels
,mapTuplesToNodes
иleafTupleDatums
.Если предоставлено более одной листовой кортеж, ожидается, что функция
picksplit
классифицирует их в более чем один узел; в противном случае невозможно разделить листовые кортежи на несколько страниц, что является конечной целью этой операции. Поэтому, если функцияpicksplit
размещает все листовые кортежи в одном узле, код ядра SP-GiST переопределит это решение и сгенерирует внутренний кортеж, в котором листовые кортежи случайным образом распределяются по нескольким узлам с одинаковыми метками. Такой кортеж помечен какallTheSame
для обозначения этого события. Функцииchoose
иinner_consistent
должны принимать соответствующие меры с такими внутренними кортежами. См. Раздел 62.3.4.3 для получения дополнительной информации.picksplit
может быть применена только к одной листовой кортежу в случае, если функцияconfig
установилаlongValuesOK
в true и было предоставлено значение, превышающее размер страницы. В этом случае цель операции - удалить префикс и создать новое, более короткое значение листа. Вызов будет повторяться, пока не будет создано значение листа достаточно короткое для помещения на страницу. См. Раздел 62.3.4.1 для получения дополнительной информации.inner_consistent
Возвращает набор узлов (ветвей), которые нужно проследовать во время поиска по дереву.
Декларация функции SQL должна выглядеть так:
CREATE FUNCTION my_inner_consistent(internal, internal) RETURNS void ...
Первый аргумент - указатель на структуру C
spgInnerConsistentIn
, содержащую входные данные для функции. Второй аргумент - указатель на структуру CspgInnerConsistentOut
, которую функция должна заполнить результатами.typedef struct spgInnerConsistentIn { ScanKey scankeys; /* array of operators and comparison values */ ScanKey orderbys; /* array of ordering operators and comparison * values */ int nkeys; /* length of scankeys array */ int norderbys; /* length of orderbys array */ Datum reconstructedValue; /* value reconstructed at parent */ void *traversalValue; /* opclass-specific traverse value */ MemoryContext traversalMemoryContext; /* put new traverse values here */ int level; /* current level (counting from zero) */ bool returnData; /* original data must be returned? */ /* Data from current inner tuple */ bool allTheSame; /* tuple is marked all-the-same? */ bool hasPrefix; /* tuple has a prefix? */ Datum prefixDatum; /* if so, the prefix value */ int nNodes; /* number of nodes in the inner tuple */ Datum *nodeLabels; /* node label values (NULL if none) */ } spgInnerConsistentIn; typedef struct spgInnerConsistentOut { int nNodes; /* number of child nodes to be visited */ int *nodeNumbers; /* their indexes in the node array */ int *levelAdds; /* increment level by this much for each */ Datum *reconstructedValues; /* associated reconstructed values */ void **traversalValues; /* opclass-specific traverse values */ double **distances; /* associated distances */ } spgInnerConsistentOut;
Массив
scankeys
, длинойnkeys
, описывает условия поиска индекса. Эти условия объединяются с помощью оператора AND — интересны только записи индекса, которые удовлетворяют всем условиям. (Обратите внимание, чтоnkeys
= 0 означает, что все записи индекса удовлетворяют запросу). Обычно функция consistent заботится только о поляхsk_strategy
иsk_argument
каждой записи массива, которые соответственно предоставляют оператор индексации и значение сравнения. В частности, необходимо проверятьsk_flags
для определения, является ли значение сравнения NULL, потому что ядро кода SP-GiST будет фильтровать такие условия. Массивorderbys
, длинойnorderbys
, описывает операторы сортировки (если они есть) таким же образом.reconstructedValue
- это значение, восстановленное для родительской кортежи; на корневом уровне или если функцияinner_consistent
не предоставила значение на родительском уровне, оно равно(Datum) 0
.traversalValue
- это указатель на любые данные обхода, переданные из предыдущего вызоваinner_consistent
для родительского индексного кортежа, или NULL на корневом уровне.traversalMemoryContext
- это контекст памяти, в котором хранятся значения обхода (см. ниже).level
- это текущий уровень внутреннего кортежа, начиная с нуля для корневого уровня.returnData
- этоtrue
, если требуется восстановленные данные для этого запроса; это будет так только в том случае, если функцияconfig
утверждаетcanReturnData
.allTheSame
- true, если текущий внутренний кортеж помечен как “all-the-same”; в этом случае все узлы имеют одинаковую метку (если есть) и поэтому либо все, либо ни один из них соответствуют запросу (см. Раздел 62.3.4.3).hasPrefix
- true, если текущий внутренний кортеж содержит префикс; если это так,prefixDatum
- это его значение.nNodes
- количество дочерних узлов, содержащихся во внутреннем кортеже, иnodeLabels
- это массив их меток, или NULL, если у узлов нет меток.nNodes
должно быть установлено на количество дочерних узлов, которые необходимо посетить в процессе поиска, аnodeNumbers
должно быть установлено на массив их индексов. Если класс операторов отслеживает уровни, установитеlevelAdds
на массив приращений уровня необходимых при спуске к каждому узлу, который нужно посетить. (Часто эти приращения будут одинаковыми для всех узлов, но это не обязательно так, поэтому используется массив). Если требуется восстановление значения, установитеreconstructedValues
на массив значений восстановленных для каждого дочернего узла, который нужно посетить; в противном случае оставьтеreconstructedValues
как NULL. Предполагается, что восстановленные значения имеют типspgConfigOut
.leafType
. (Однако, поскольку ядро системы ничего с ними не делает, кроме возможного копирования, достаточно, чтобы они имели те же свойстваtyplen
иtypbyval
что иleafType
). Если выполняется упорядоченный поиск, установитеdistances
на массив значений расстояния в соответствии с массивомorderbys
(узлы с наименьшими расстояниями будут обработаны первыми). В противном случае оставьте его NULL. Если требуется передать дополнительную информацию (“значения обхода”) на более низкие уровни поиска в дереве, установитеtraversalValues
на массив соответствующих значений обхода, по одному для каждого дочернего узла, который нужно посетить; в противном случае оставьтеtraversalValues
как NULL. Обратите внимание, что функцияinner_consistent
отвечает за выделение памяти для массивовnodeNumbers
,levelAdds
,distances
,reconstructedValues
иtraversalValues
в текущем контексте памяти. Однако, любые значения обхода, на которые указывает массивtraversalValues
, должны быть выделены вtraversalMemoryContext
. Каждое значение обхода должно быть выделено в отдельном блоке памяти, выделенном с помощью palloc.leaf_consistent
Возвращает true, если листовая кортеж удовлетворяет запросу.
Декларация функции SQL должна выглядеть так:
CREATE FUNCTION my_leaf_consistent(internal, internal) RETURNS bool ...
Первый аргумент - указатель на структуру C
spgLeafConsistentIn
, содержащую входные данные для функции. Второй аргумент - указатель на структуру CspgLeafConsistentOut
, которую функция должна заполнить данными результата.typedef struct spgLeafConsistentIn { ScanKey scankeys; /* array of operators and comparison values */ ScanKey orderbys; /* array of ordering operators and comparison * values */ int nkeys; /* length of scankeys array */ int norderbys; /* length of orderbys array */ Datum reconstructedValue; /* value reconstructed at parent */ void *traversalValue; /* opclass-specific traverse value */ int level; /* current level (counting from zero) */ bool returnData; /* original data must be returned? */ Datum leafDatum; /* datum in leaf tuple */ } spgLeafConsistentIn; typedef struct spgLeafConsistentOut { Datum leafValue; /* reconstructed original data, if any */ bool recheck; /* set true if operator must be rechecked */ bool recheckDistances; /* set true if distances must be rechecked */ double *distances; /* associated distances */ } spgLeafConsistentOut;
Массив
scankeys
, длинойnkeys
, описывает условия поиска индекса. Эти условия объединяются с помощью оператора AND — только записи индекса, удовлетворяющие всем условиям, удовлетворяют запросу. (Обратите внимание, чтоnkeys
= 0 означает, что все записи индекса удовлетворяют запросу). Обычно функция consistent заботится только о поляхsk_strategy
иsk_argument
каждой записи массива, которые соответственно предоставляют оператор индексации и значение сравнения. В частности, необходимо проверятьsk_flags
для определения, является ли значение сравнения NULL, поскольку ядро кода SP-GiST будет фильтровать такие условия. Массивorderbys
, длинойnorderbys
, описывает операторы сортировки аналогичным образом.reconstructedValue
- это значение, восстановленное для родительской кортежи; оно равно(Datum) 0
на корневом уровне или если функцияinner_consistent
не предоставила значение на родительском уровне.traversalValue
- это указатель на любые данные обхода, переданные из предыдущего вызоваinner_consistent
для родительского индексного кортежа или NULL на корневом уровне.level
- это текущий уровень листового кортежа, начиная с нуля для корневого уровня.returnData
равноtrue
, если для этого запроса требуется восстановленные данные; это будет так только в том случае, если функцияconfig
утверждаетcanReturnData
.leafDatum
- это значение ключаspgConfigOut
.leafType
, хранящееся в текущем листовом кортеже.Функция должна возвращать
true
, если листовой кортеж соответствует запросу, илиfalse
, если нет. В случаеtrue
, еслиreturnData
равноtrue
, тоleafValue
должно быть установлено в значение (типаspgConfigIn
.attType
), которое было изначально предоставлено для индексации этого листового кортежа. Кроме того,recheck
может быть установлено вtrue
, если совпадение неопределенно, и поэтому оператор(ы) должны быть повторно применены к фактическому кортежу кучи для проверки совпадения. Если выполняется упорядоченный поиск, установитеdistances
в массив значений расстояния в соответствии с массивомorderbys
. В противном случае оставьте его NULL. Если хотя бы одно из возвращенных расстояний не является точным, установитеrecheckDistances
в true. В этом случае исполнитель вычислит точные расстояния после получения кортежа из кучи и, при необходимости, переупорядочит кортежи.
Опциональные пользовательские методы:
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
будет сброшен после обработки каждой кортежи. Поэтому не очень важно беспокоиться о pfree'ing всего, что вы palloc'или. (Метод config
является исключением: он должен стараться избегать утечки памяти. Но обычно метод config
должен делать только присваивание констант в переданную структуру параметров).
Если индексируемый столбец имеет сортируемый тип данных, правило сортировки индекса будет передано всем поддерживаемым методам с использованием стандартного механизма PG_GET_COLLATION()
.
62.3.4. Реализация #
Содержание этого раздела охватывает детали реализации и другие хитрости, которые полезны для разработчиков классов операторов SP-GiST для их знания.
62.3.4.1. Ограничения SP-GiST #
Все отдельные листовые кортежи и внутренние кортежи должны помещаться на одной странице индекса (по умолчанию 8 КБ). Поэтому, при индексировании значений переменной длины, длинные значения могут быть поддержаны только с помощью методов, таких как радиксные деревья, в которых каждый уровень дерева включает префикс, достаточно короткий для помещения на страницу, а конечный листовой уровень включает суффикс, также достаточно короткий для помещения на страницу. Класс оператора должен установить longValuesOK
в true только если он готов организовать это. В противном случае, ядро SP-GiST будет отклонять любой запрос на индексирование значения, которое слишком велико для помещения на страницу индекса.
Точно так же, ответственность класса оператора заключается в том, чтобы внутренние кортежи не становились слишком большими, чтобы поместиться на странице индекса; это ограничивает количество дочерних узлов, которые могут быть использованы в одном внутреннем кортеже, а также максимальный размер префиксного значения.
Ограничение заключается в том, что когда узел внутренней кортежа указывает на набор
листовых кортежей, все эти кортежи должны находиться на одной странице индекса.
(Это решение проектирования, которое позволяет сократить поиск и сэкономить место в
связях, связывающих такие кортежи вместе). Если набор листовых кортежей
становится слишком большим для страницы, выполняется разделение и вставляется промежуточный
внутренний кортеж. Чтобы решить эту проблему, новый внутренний
кортеж должен разделить набор значений листовых кортежей на несколько
групп узлов. Если функция picksplit
класса оператора
не справляется с этим, ядро SP-GiST прибегает к
необычным мерам, описанным в Раздел 62.3.4.3.
Когда longValuesOK
равно true, ожидается, что последующие уровни дерева SP-GiST будут поглощать все больше информации в префиксы и метки узлов внутренних кортежей, делая требуемые листовые данные все меньше и меньше, так что в конечном итоге они поместятся на странице.
Чтобы предотвратить ошибки в классах операторов, вызывающие бесконечные циклы вставки, ядро SP-GiST выдаст ошибку, если листовые данные не станут меньше в течение десяти циклов вызовов метода choose
.
62.3.4.2. SP-GiST без меток узлов #
Некоторые алгоритмы деревьев используют фиксированный набор узлов для каждой внутренней кортежа; например, в квадродереве всегда ровно четыре узла, соответствующих четырем квадрантам вокруг центроида внутреннего кортежа. В таком случае код обычно работает с узлами по их номерам, и нет необходимости в явных метках узлов. Чтобы подавить метки узлов (и тем самым сэкономить некоторое пространство), функция picksplit
может возвращать NULL для массива nodeLabels
, а также функция choose
может возвращать NULL для массива prefixNodeLabels
во время действия spgSplitTuple
. В результате этого nodeLabels
также будет NULL при последующих вызовах функций choose
и inner_consistent
. В принципе, метки узлов могут использоваться для некоторых внутренних кортежей и опускаться для других в том же индексе.
Когда работа с внутренним кортежем, содержащим неименованные узлы, функция choose
не должна возвращать spgAddNode
, так как в таких случаях множество узлов должно быть фиксированным.
62.3.4.3. “Все-одинаковые” Внутренние кортежи #
Ядро SP-GiST может переопределить результаты функции picksplit
класса оператора, когда функция picksplit
не может разделить предоставленные значения листьев на по крайней мере две категории узлов. Когда это происходит, новый внутренний кортеж создается с несколькими узлами, каждый из которых имеет ту же метку (если есть), которую picksplit
дал одному из узлов, и значения листьев случайным образом разделены между этими эквивалентными узлами. Флаг allTheSame
устанавливается во внутреннем кортеже, чтобы предупредить функции choose
и inner_consistent
, что кортеж не имеет набора узлов, которые они могли бы ожидать.
При работе с кортежем allTheSame
интерпретация результата функции choose
spgMatchNode
означает, что новое значение может быть присвоено любому из эквивалентных узлов; основной код будет игнорировать предоставленное значение nodeN
и спускаться в один из узлов случайным образом (чтобы сохранить сбалансированность дерева). Ошибка будет, если функция choose
вернет spgAddNode
, так как это сделает узлы неэквивалентными; действие spgSplitTuple
должно быть использовано, если значение для вставки не соответствует существующим узлам.
При работе с кортежем allTheSame
функция inner_consistent
должна возвращать либо все, либо ни один из узлов в качестве целей для продолжения поиска по индексу, так как они все эквивалентны. Это может или не может потребовать специального кода, в зависимости от того, насколько функция inner_consistent
обычно предполагает о смысле узлов.
62.3.5. Примеры #
Дистрибутив исходного кода PostgreSQL включает
несколько примеров классов операторов индекса для SP-GiST,
как описано в Таблица 62.2. Код можно посмотреть в src/backend/access/spgist/
и src/backend/utils/adt/
.