Индексы SP-GiST

Введение

SP-GiST является сокращением от Space-partitioned GiST (GiST с разбиением пространства). SP-GiST поддерживает партиционированные деревья поиска, что упрощает разработку широкого диапазона различных несбалансированных структур данных, например деревьев квадрантов, K-мерных и префиксных деревьев (Меркла). Общая особенность этих структур заключается в том, что они многократно разбивают пространство поиска на партиции, которые не обязательно должны быть одинакового размера. Поиск, хорошо соответствующий правилу разбиения, может быть очень быстрым.

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

Как и GiST, SP-GiST предназначен для разработки пользовательских типов данных с соответствующими методами доступа экспертом в области типа данных, а не специалистом по базам данных.

Часть представленной здесь информации взята с сайта Проекта индексации SP-GiST Университета Пердью.

---

---

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

В основной дистрибутив QHB включены классы операторов SP-GiST, перечисленные в Таблице 1.

Таблица 1. Встроенные классы операторов SP-GiST

Имя	Операторы упорядочивания	Индексируемые операторы
box_ops	<-> (box, point)	<< (box, box)
		&< (box, box)
		&> (box, box)
		>> (box, box)
		<@ (box, box)
		@> (box, box)
		~= (box, box)
		&& (box, box)
		<<| (box, box)
		&<| (box, box)
		|&> (box, box)
		|>> (box, box)
kd_point_ops	<-> (point,point)	|>> (point,point)
		<< (point,point)
		>> (point,point)
		<<| (point,point)
		~= (point,point)
		<@ (point,box)
network_ops		<< (inet, inet)
		<<= (inet, inet)
		>> (inet, inet)
		>>= (inet, inet)
		= (inet, inet)
		<> (inet, inet)
		< (inet, inet)
		<= (inet, inet)
		> (inet, inet)
		>= (inet, inet)
		&& (inet, inet)
poly_ops	<-> (polygon,point)	<< (polygon,polygon)
		&< (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) по индексированному набору данных точек или многоугольников.

---

---

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

SP-GiST предлагает интерфейс с высоким уровнем абстракции, требующий от разработчика методов доступа реализовать только методы, специфичные для указанного типа данных. Ядро SP-GiST отвечает за эффективное сопоставление с данными на диске и поиск в древовидной структуре. Кроме того он отвечает за конкурентный доступ и вопросы протоколирования.

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

Когда индекс SP-GiST создается с дополнительными столбцами (INCLUDE), значения этих столбцов тоже хранятся в листовых кортежах. Столбцы INCLUDE не представляют интереса для класса операторов SP-GiST, поэтому здесь они рассматриваться не будут.

Внутренние кортежи устроены сложнее, поскольку являются точками разветвления в дереве поиска. В каждом внутреннем кортеже содержится набор из одного или нескольких узлов, представляющих группы схожих между собой значений листьев. Узел содержит нисходящую ссылку, ведущую либо к другому, внутреннему кортежу нижнего уровня, либо к короткому списку листовых кортежей, лежащих в одной странице индекса. Обычно у каждого кортежа есть метка, описывающая его; например, в префиксном дереве меткой узла может быть следующий символ в строковом значении. (Как вариант, класс операторов может опускать метки узлов, если он работает с фиксированным набором узлов для всех внутренних кортежей; см. подраздел SP-GiST без меток узлов.) Дополнительно внутренний кортеж может иметь значение префикса, описывающего все его члены. В префиксном дереве это может быть общий префикс представленных строк. Значением префикса необязательно должен быть настоящий префикс — это могут быть любые данные, требующиеся классу операторов; например, в дереве квадрантов в нем может храниться центральная точка, относительно которой отмеряются четыре квадранта. Тогда внутренний кортеж дерева квадрантов тоже будет содержать четыре узла, соответствующих квадрантам вокруг этой центральной точки.

Некоторые алгоритмы деревьев требуют знания уровня (или глубины) текущего кортежа, поэтому ядро SP-GiST предоставляет классам операторов возможность контролировать число уровней при спуске по дереву. Также имеется поддержка постепенного восстановления представленного значения, если возникает такая необходимость, и передачи вниз дополнительных данных (так называемых перемещаемых значений) при спуске по дереву.

Примечание
Код ядра SP-GiST отвечает за записи NULL. Хотя индексы SP-GiST и хранят записи для NULL в индексируемых столбцах, это скрыто от кода классов операторов индекса: записи индекса или условия поиска с NULL никогда не будут передаваться методам класса операторов. (Предполагается, что операторы SP-GiST строгие и поэтому не могут выдавать положительный результат для значений NULL.) В связи с этим значения NULL здесь больше рассматриваться не будут.

Существует пять пользовательских методов, которые класс операторов индекса должен предоставить для SP-GiST, и еще два необязательных. Все пять обязательных методов следуют соглашению о принятии двух аргументов internal, первый из которых является указателем на структуру C/RUST, содержащую входные значения для вспомогательного метода, тогда как второй аргумент является указателем на структуру C/RUST, в которую следует поместить выходные значения. Четыре из обязательных методов просто возвращают void, поскольку все их результаты находятся в выходной структуре; но метод leaf_consistent возвращает результат boolean. Эти методы не должны изменять никакие поля своих входных структур. Во всех случаях выходная структура обнуляется перед вызовом пользовательского метода. Необязательный шестой метод compress принимает единственный аргумент datum, который индексируется и возвращает значение, подходящее для физического хранения в листовом кортеже. Необязательный седьмой метод options принимает указатель internal на структуру C/RUST, в которую должны помещаться параметры, специфичные для класса операторов, и возвращает void.

Пять обязательных пользовательских методов:

config

Возвращает статическую информацию о реализации индекса, включая OID типов данных префикса и метки узла.

SQL-объявление этой функции должно выглядеть следующим образом:

CREATE FUNCTION my_config(internal, internal) RETURNS void ...

Первый аргумент является указателем на структуру на C spgConfigIn, содержащую входные данные для функции. Второй аргумент является указателем на структуру на C spgConfigOut, которую функция должна заполнить результирующими данными.

typedef struct spgConfigIn
{
    Oid         attType;        /* Индексируемый тип данных */
} spgConfigIn;

typedef struct spgConfigOut
{
    Oid         prefixType;     /* Тип данных префикса внутреннего кортежа */
    Oid         labelType;      /* Тип данных метки внутреннего кортежа */
    Oid         leafType;       /* Тип данных значений листового кортежа */
    bool        canReturnData;  /* Класс операторов умеет реконструировать исходные данные */
    bool        longValuesOK;   /* Класс операторов умеет обрабатывать значения объемом > 1 страницы */
} spgConfigOut;

Поле attType передается для поддержки полиморфных классов операторов индекса; для обычных классов операторов с фиксированным типом данных оно всегда будет иметь одно и то же значение и поэтому может игнорироваться.

Для классов операторов, не использующих префиксы, в prefixType можно задать VOIDOID. Аналогично для классов операторов, не использующих метки узлов, в labelType можно задать VOIDOID. Флаг canReturnData следует установить в true, если класс операторов способен восстанавливать изначально предоставленное индексу значение. Флаг longValuesOK следует установить в true, только если attType имеет переменную длину и класс оператора умеет нарезать длинные значения, нарезая суффиксы (см. подраздел Ограничения SP-GiST).

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

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

choose

Выбирает метод добавления нового значения во внутренний кортеж.

SQL-объявление этой функции должно выглядеть следующим образом:

CREATE FUNCTION my_choose(internal, internal) RETURNS void ...

Первый аргумент является указателем на структуру на C 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, когда этот метод предоставляется, или, в противном случае, — самим значением datum. leafDatum может меняться на нижних уровнях дерева, если его меняют методы choose или picksplit. Когда поиск места добавления достигает листовой страницы, текущим значением leafDatum становятся данные, которые будут храниться во вновь созданном листовом кортеже. В level передается текущий уровень листового кортежа, начиная с нуля для уровня корня. allTheSame имеет значение true, если текущий внутренний кортеж помечен как содержащий несколько равнозначных узлов (см. подраздел Внутренние кортежи «все-равны»). Флаг 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, содержащую входные данные для функции. Второй аргумент является указателем на структуру на C spgPickSplitOut, которую функция должна заполнить результирующими данными.

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 сама отвечает за выделение памяти под массивы nodeLabels, mapTuplesToNodes и leafTupleDatums с помощью функции palloc.

Если предоставляется больше одного листового кортежа, то ожидается, что функция picksplit классифицирует их и разделит на несколько узлов; иначе невозможно разнести листовые кортежи на несколько страниц, что является конечной целью этой операции. Таким образом, если в итоге функция picksplit помещает все листовые кортежи в один узел, код ядра SP-GiST переопределит это решение и сгенерирует внутренний кортеж, в котором листовые кортежи будут случайным образом связываются с несколькими узлами с одинаковыми метками. Такой кортеж помечается флагом allTheSame, показывающим, что все узлы равны. Функции choose и inner_consistent должны обращаться с такими внутренними кортежами надлежащим образом. Подробную информацию см. в подразделе Внутренние кортежи «все-равны».

Функцию picksplit можно применить к одному листовому кортежу только в том случае, если функция config установила в longValuesOK значение true и на вход было передано значение, не помещающееся на одной странице. Тогда смысл этой операции состоит в том, чтобы убрать префикс и создать новое, более короткое значение листовых данных. Этот вызов будет повторяться, пока листовое значение не станет достаточно коротким, чтобы поместиться на странице. Подробную информацию см. в подразделе Ограничения SP-GiST.

inner_consistent

Возвращает набор узлов (ветвей), по которым надо следовать при поиске по дереву.

SQL-объявление этой функции должно выглядеть следующим образом:

CREATE FUNCTION my_inner_consistent(internal, internal) RETURNS void ...

Первый аргумент является указателем на структуру на C spgInnerConsistentIn, содержащую входные данные для этой функции. Второй аргумент является указателем на структуру на C spgInnerConsistentOut, которую функция должна заполнить результирующими данными.

typedef struct spgInnerConsistentIn
{
    ScanKey     scankeys;       /* массив операторов и сравниваемых значений */
    ScanKey     orderbys;       /* массив операторов упорядочивания и сравниваемых значений */
    int         nkeys;          /* длина массива scankeys */
    int         norderbys;      /* длина массива orderbys */

    Datum       reconstructedValue;     /* значение, восстановленное для родителя */
    void       *traversalValue; /* перемещаемое значение, специфичное для класса операторов */
    MemoryContext traversalMemoryContext;   /* поместить перемещаемые значения сюда */
    int         level;          /* текущий уровень (считая от 0) */
    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 имеет значение true, если для этого запроса требуются восстановленные данные; они понадобятся, только если функция config установила флаг canReturnData. Флаг allTheSame имеет значение true, если текущий внутренний кортеж помечен как имеющий свойство «все равны»; в этом случае у всех узлов будет одинаковая метка (если эта метка есть), и поэтому либо все, либо ни один из них не соответствует запросу (см. подраздел Внутренние кортежи «все-равны»). Флаг 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 сама отвечает за выделение памяти с помощью функции palloc под массивы nodeNumbers, levelAdds, distances, reconstructedValues и traversalValues в текущем контексте памяти. Однако любые выходные перемещаемые значения, на которые указывает массив traversalValues, должны размещаться в контексте traversalMemoryContext. Каждое перемещаемое значение должно находиться в отдельном блоке памяти, выделенном palloc.

leaf_consistent

Возвращает true, если листовой кортеж удовлетворяет запросу.

SQL-объявление этой функции должно выглядеть следующим образом:

CREATE FUNCTION my_leaf_consistent(internal, internal) RETURNS bool ...

Первый аргумент является указателем на структуру на C spgLeafConsistentIn, содержащую входные данные для этой функции. Второй аргумент является указателем на структуру на C spgLeafConsistentOut, которую функция должна заполнить результирующими данными.

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 равен 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 любых блоков памяти, выделенных функцией palloc. (Метод config является исключением: в нем следует избегать утечек памяти. Но обычно метод config не делает ничего, помимо присвоения констант переданной структуре параметров.)

Если индексируемый столбец имеет сортируемый тип данных, правило сортировки индекса будет передаваться всем вспомогательным методам с помощью стандартного механизма PG_GET_COLLATION().

---

---

Реализация

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

Ограничения SP-GiST

Отдельные листовые и внутренние кортежи должны помещаться на одной странице индекса (по умолчанию 8кБ). Поэтому при индексировании значений типов данных переменной длины длинные значения могут поддерживаться только такими методами, как префиксные деревья, в которых каждый уровень дерева включает префикс, достаточно короткий, чтобы уместиться на странице, а конечный уровень листьев включает аналогично короткий суффикс, который тоже помещается на странице. Класс операторов должен устанавливать в longValuesOK значение true, только если он готов это организовать. В противном случае ядро SP-GiST отклонит любой запрос на индексацию значения, которое слишком велико, чтобы поместиться на странице индекса.

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

Еще одно ограничение состоит в том, что когда узел внутреннего кортежа указывает на набор листовых кортежей, все эти кортежи должны находиться на одной странице индекса. (Это проектное решение для сокращения времени на поиск экономии места в ссылках, связывающих такие кортежи вместе.) Если набор листовых кортежей слишком увеличивается в размере, чтобы уместиться на странице, выполняется разбиение и добавляется промежуточный внутренний кортеж. Чтобы решить возникшую проблему, новый внутренний кортеж должен разделить набор листовых значение на несколько групп узлов. Если функция picksplit класса операторов не может этого сделать, ядро SP-GiST прибегает к чрезвычайным мерам, описанным в подразделе Внутренние кортежи «все-равны».

Когда longValuesOK равен true, ожидается, что последующие уровни дерева SP-GiST будут включать все больше и больше информации в префиксы и метки узлов внутренних кортежей, все уменьшая и уменьшая требуемое листовое значение, так что в итоге оно умещается на странице. Чтобы возможные ошибки в классах операторов не вызывали бесконечные циклы при добавлении записи, ядро SP-GiST выдаст ошибку, если листовое значение не уменьшится за десять циклов вызовов метода choose.

---

SP-GiST без меток узлов

Некоторые древовидные алгоритмы используют фиксированный набор узлов для каждого внутреннего кортежа; например, в дереве квадрантов всегда есть ровно четыре узла, соответствующих четырем квадрантам вокруг центральной точки внутреннего кортежа. В таком случае код обычно работает с узлами согласно их номерам, и в явных метках узлов нет необходимости. Чтобы убрать метки узлов (и тем самым сэкономить немного места), функция picksplit может возвращать NULL вместо массива nodeLabels, а функция choose аналогично может возвращать NULL вместо массива prefixNodeLabels во время действия spgSplitTuple. Это, в свою очередь, приведет к тому, что nodeLabels будет равен NULL во время последующих вызовов choose и inner_consistent. В принципе, в пределах одного индекса метки узлов можно использовать для некоторых внутренних кортежей, а для остальных — опускать.

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

---

Внутренние кортежи «все-равны»

Ядро SP-GiST может переопределять результаты вызова функции picksplit класса операторов, когда той не удается разделить переданные ей листовые значения как минимум на две категории узлов. Когда это происходит, создается новый внутренний кортеж с несколькими узлами, каждый из которых имеет ту же метку (если вообще имеет), как та, которую picksplit дала использованному ей одному узлу, а листовые значения делятся случайным образом между этими равнозначными узлами. Во внутреннем кортеже устанавливается флаг allTheSame, предупреждающий функции choose и inner_consistent о том, что у этого кортежа нет набора узлов, который они могли бы ожидать в ином случае.

При работе с кортежем allTheSame результат spgMatchNode функции choose воспринимается как то, что новое значение можно связать с любым из равнозначных узлов; код ядра проигнорирует переданное значение nodeN и спустится в один из узлов, выбранный случайно (чтобы сохранить дерево сбалансированным). Для choose будет ошибкой вернуть spgAddNode, поскольку это сделало бы узлы неравнозначными; если добавляемое значение не соответствует существующим узлам, следует применить действие spgSplitTuple.

При работе с кортежем allTheSame функция inner_consistent должна либо вернуть в качестве цели дальнейшего поиска по индексу все узлы, либо не вернуть ни одного, поскольку они все равнозначны. Для этого может потребоваться, а может и не потребоваться код особого случая, в зависимости от того, как функция inner_consistent обычно воспринимает содержание узлов.