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/.