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

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

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

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

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

Примечание

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

Класс операторов индекса для SP-GiST должен предоставить реализации пяти методов. Все пять методов должны по единому соглашению принимать два аргумента internal, первым из которых будет указатель на структуру C, содержащую входные значения для опорного метода, а вторым — указатель на структуру C, в которую должны помещаться выходные значения. Четыре из этих методов должны возвращать просто void, так как их результаты помещаются в выходную структуру; однако leaf_consistent дополнительно возвращает результат boolean. Эти методы не должны менять никакие поля в их входных структурах. Выходная структура всегда обнуляется перед вызовом пользовательского метода.

Пользователь должен определить следующие пять методов:

config

Возвращает статическую информацию о реализации индекса, включая 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;      /* Тип данных метки узла во внутренних кортежах */
    bool        canReturnData;  /* Класс операторов может восстановить исходные данные */
    bool        longValuesOK;   /* Класс может принимать значения, не умещающиеся на 1 странице */
} spgConfigOut;

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

Для классов операторов, не использующих префиксы, в prefixType можно установить VOIDOID. Подобным образом, для классов операторов, не использующих метки узлов, в labelType тоже можно установить VOIDOID. Признак canReturnData следует установить, если класс операторов может восстановить изначально переданное в индекс значение. Признак longValuesOK должен устанавливаться, только если attType переменной длины и класс операторов может фрагментировать длинные значения, повторяя суффиксы (см. Подраздел 60.4.1).

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 задаётся исходное значение, которое должно быть вставлено в индекс. Значение leafDatum изначально совпадает с datum, но может быть другим на низких уровнях дерева, если его изменят методы choose или picksplit. Когда поиск места добавления достигает страницы уровня листа, в создаваемом кортеже листа будет сохранено текущее значение leafDatum. В level задаётся текущий уровень внутреннего кортежа, начиная с нуля для уровня корня. Признак allTheSame устанавливается, если текущий внутренний кортеж содержит несколько равнозначных узлов (см. Подраздел 60.4.3). Признак hasPrefix устанавливается, если текущий внутренний кортеж содержит префикс; в этом случае в prefixDatum задаётся его значение. Поле nNodes задаёт число дочерних узлов, содержащихся во внутреннем кортеже, а nodeLabels представляет массив их меток, или NULL, если меток у них нет.

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

Если новое значение соответствует одному из существующих дочерних узлов, установите в resultType значение spgMatchNode. Установите в nodeN номер этого узла в массиве узлов (нумерация начинается с нуля). Установите в levelAdd значение, на которое должен увеличиваться уровень (level) при спуске через этот узел, либо оставьте его нулевым, если класс операторов не отслеживает уровни. Установите restDatum, равным datum, если класс операторов не меняет значения данных от уровня к следующему, а в противном случае запишите в него изменённое значение, которое должно использоваться в качестве 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 — массив их значений данных. В level указывается текущий уровень, который должны разделять все кортежи листьев, и который станет уровнем нового внутреннего кортежа.

Установите признак hasPrefix, чтобы указать, должен ли новый внутренний кортеж иметь префикс, и если да, задайте в prefixDatum значение префикса. Установите в nNodes количество узлов, которые будут содержаться во внутреннем кортеже, а в nodeLabels — массив значений их меток либо NULL, если узлам не нужны метки. Поместите в mapTuplesToNodes указатель на массив, назначающий номера узлов (начиная с нуля) каждому кортежу листа. В leafTupleDatums передайте массив значений, которые должны быть сохранены в новых кортежах листьев (они будут совпадать со входными значениями (datums), если класс операторов не изменяет значения от уровня к следующему). Заметьте, что функция picksplit сама должна выделить память, используя palloc, для массивов nodeLabels, mapTuplesToNodes и leafTupleDatums.

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

picksplit может применяться к одному кортежу на уровне листьев, только когда функция config установила в longValuesOK значение true и было передано входное значение, большее страницы. В этом случае цель операции — отделить префикс и получить новое, более короткое значение для листа. Этот вызов будет повторяться, пока значение уровня листа не уменьшится настолько, чтобы уместиться в странице. За дополнительными сведениями обратитесь к Подразделу 60.4.1.

inner_consistent

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

В SQL эта функция должна объявляться так:

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

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

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

    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;        /* переходящие значения, специфичные для класса операторов */
} spgInnerConsistentOut;

Массив scankeys длины nkeys описывает условия поиска по индексу. Эти условия объединяются операцией И — найдены должны быть только те записи, которые удовлетворяют всем условиям. (Заметьте, что с nkeys = 0 подразумевается, что запросу удовлетворяют все записи в индексе.) Обычно эту функцию интересуют только поля sk_strategy и sk_argument в каждой записи массива, в которых определяется соответственно индексируемый оператор и искомое значение. В частности, нет необходимости проверять sk_flags, чтобы распознать NULL в искомом значении, так как ядро SP-GiST отфильтрует такие условия. В reconstructedValue передаётся значение, восстановленное для родительского кортежа; это может быть (Datum) 0 на уровне корня или если функция inner_consistent не установила значение на предыдущем уровне. В traversalValue передаётся указатель на переходящие данные, полученные из предыдущего вызова inner_consistent для родительского кортежа индекса, либо NULL на уровне корня. Поле traversalMemoryContext указывает на контекст памяти, в котором нужно сохранить выходные переходящие данные (см. ниже). В level передаётся уровень текущего внутреннего кортежа (уровень корня считается нулевым). Флаг returnData устанавливается, когда для этого запроса нужно получить восстановленные данные; это возможно, только если функция config установила признак canReturnData. Признак allTheSame устанавливается, если текущий внутренний кортеж имеет пометку «все-равны»; в этом случае все узлы имеют одну метку (если имеют) и значит, либо все они, либо никакой не соответствует запросу (см. Подраздел 60.4.3). Признак hasPrefix устанавливается, если текущий внутренний кортеж содержит префикс; в этом случае в prefixDatum находится его значение. В nNodes задаётся число дочерних узлов, содержащихся во внутреннем кортеже, а в nodeLabels — массив их меток либо NULL, если они не имеют меток.

В nNodes нужно записать число дочерних узлов, которые потребуется посетить при поиске, а в nodeNumbers — массив их индексов. Если класс операторов отслеживает уровни, в levelAdds нужно передать массив с шагами увеличения уровня при посещении каждого узла. (Часто шаг будет одним для всех узлов, но может быть и по-другому, поэтому применяется массив.) Если потребовалось восстановить значения, поместите в reconstructedValues указатель на массив значений, восстановленных для каждого дочернего узла, который нужно посетить; в противном случае оставьте reconstructedValues равным 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;       /* массив операторов и искомых значений */
    int         nkeys;          /* длина массива */

    Datum       reconstructedValue;     /* значение, восстановленное для родителя */
    void       *traversalValue; /* переходящее значение, специфичное для класса операторов */
    int         level;          /* текущий уровень (отсчитывая от нуля) */
    bool        returnData;     /* нужно ли возвращать исходные данные? */

    Datum       leafDatum;      /* значение в кортеже листа */
} spgLeafConsistentIn;

typedef struct spgLeafConsistentOut
{
    Datum       leafValue;      /* восстановленные исходные данные, при наличии */
    bool        recheck;        /* true, если оператор нужно перепроверить */
} spgLeafConsistentOut;

Массив scankeys длины nkeys описывает условия поиска по индексу. Эти условия объединяются операцией И — запросу удовлетворяют только те записи в индексе, которые удовлетворяют всем этим условиям. (Заметьте, что с nkeys = 0 подразумевается, что запросу удовлетворяют все записи в индексе.) Обычно эту функцию интересуют только поля sk_strategy и sk_argument в каждой записи массива, в которых определяются соответственно индексируемый оператор и искомое значение. В частности, нет необходимости проверять sk_flags, чтобы распознать NULL в искомом значении, так как ядро SP-GiST отфильтрует такие условия. В reconstructedValue передаётся значение, восстановленное для родительского кортежа; это может быть (Datum) 0 на уровне корня или если функция inner_consistent не установила значение на предыдущем уровне. В traversalValue передаётся указатель на переходящие данные, полученные из предыдущего вызова inner_consistent для родительского кортежа индекса, либо NULL на уровне корня. В level передаётся уровень текущего внутреннего кортежа (уровень корня считается нулевым). Флаг returnData устанавливается, когда для этого запроса нужно получить восстановленные данные; это возможно, только если функция config установила признак canReturnData. В leafDatum передаётся значение ключа, записанное в текущем кортеже листа.

Эта функция должна вернуть true, если кортеж листа соответствует запросу, или false в противном случае. В случае положительного результата, если в поле returnData передано true, нужно поместить в leafValue значение, изначально переданное для индексации в этот кортеж. Кроме того, флагу recheck можно присвоить true, если соответствие неточное, так что для установления точного результата проверки нужно повторно применить оператор(ы) к актуальному кортежу данных.

Все опорные методы SP-GiST обычно вызываются в кратковременных контекстах памяти; то есть CurrentMemoryContext сбрасывается после обработки каждого кортежа. Таким образом, можно не заботиться об освобождении любых блоков памяти, выделенных функцией palloc. (Метод config является исключением: в нём нужно не допускать утечек памяти. Но обычно метод config не делает ничего, кроме как присваивает константы переданной структуре параметров.)

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