Индексы SP-GiST

Введение

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

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

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

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

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

ИмяИндексированный Тип ДанныхИндексируемые ОператорыОператоры сортировки
kd_point_opspoint<< <@ <^ >> >^ ~=<->
quad_point_opspoint<< <@ <^ >> >^ ~=<->
range_opsлюбой диапазонный тип&& &< &> -|- << <@ = >> @>
box_opsbox<< &< && &> >> ~= @> <@ &<| <<| |>> |&><->
poly_opspolygon<< &< && &> >> ~= @> <@ &<| <<| |>> |&><->
text_opstext< <= = > >= ~<=~ ~<~ ~>=~ ~>~ ^@
inet_opsinet, cidr&& >> >>= > >= <> << <<= < <= =

Из двух классов операторов для типа point, quad_point_ops — это класс по умолчанию. kd_point_ops поддерживает те же операторы, но использует другую структуру данных индекса, которая может обеспечить лучшую производительность в некоторых приложениях.

Классы операторов quad_point_ops, kd_point_ops и poly_ops поддерживают оператор упорядочения <->, который позволяет выполнять поиск k ближайших соседей (k-NN search) среди проиндексированных точек или многоугольников.

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

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

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

Содержимое внутренние вершин более сложное. Каждая внутренняя вершина содержит набор из одного или нескольких узлов (nodes), каждый из которых является ветвью дерева (= областью пространства). Узел содержит либо ссылку на внутреннюю вершину (если ветвь дерева большая), либо короткий список листьев, все из которых располагаются на одной странице индекса (если ветвь маленькая). Каждый узел обычно имеет метку (label) которая описывает его; например, в префиксном дереве метка узла может быть следующей буквой строкового значения. (Класс оператора может опустить метки узлов, если он работает с фиксированным набором узлов для всех внутренних вершин, см. SP-GiST без меток узлов).

Внутренняя вершина опционально может иметь префикс (prefix), описывающее все его члены. В префиксном дереве это может быть общий префикс представленных строк. Значение prefix не обязательно является действительно префиксом, но может быть любыми данными, необходимыми классу операторов; например, в дереве квадрантов в prefix хранится центральная точка, по которой происходит разбиение на квадранты. (А 4 узла соответствуют 4-ем областям пространства после разбиения.). Зачем существуют и префиксы, и метки? Метка нужна для того, чтобы решить, в какую из дочерних вершин пойти, не обращаясь к этим вершинам; метки хранятся в родительской вершине. Префикс наоборот хранится в самой вершине, и позволяет делать некоторые операции к ней, не обращаясь к родителю.

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

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

Существует пять пользовательских методов, которые должен предоставить класс оператора индекса для SP-GiST, и один необязательный. Все пять обязательных методов принимают 2 аргумента типа internal, это указатели на структуры, в первой расположены все входные значения, а во вторую надо поместить выходные значения. Возвращаемое значение из 4-ех методов void, а метод leaf_consistent возвращает bool. Методы не должны изменять какие-либо поля своих входных структур. Во всех случаях выходная структура инициализируется нулями перед вызовом пользовательского метода. Необязательный шестой метод compress принимает единственный аргумент datum — значение, которое индексируем, и возвращает его же в формате для хранения в листовой вершине.

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

  • config

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

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

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

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

    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 должно быть установлено в true, если класс оператора способен восстанавливать исходное значение проиндексированного поля (для сканирования только по индексу). longValuesOK должно быть установлено true, только если attType имеет переменную длину, и класс оператора умеет нарезать длинные значения для размещения в нескольких узлах (см. Ограничения SP-GiST).

    leafType обычно используют равный attType (оставить leafType нулевым работает так же, но лучше явно выставьте leafType = attType). Если attType и leafType различаются, должен быть предоставлен необязательный метод compress. Метод compress переводит индексируемые значения из attType в leafType. Примечание: leaf_consistent и inner_consistent получают в качестве аргументов attType, leafType на них не влияет.

  • choose

    Решает, как именно будем вставлять новое значение в ветку дерева.

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

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

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

    typedef struct spgChooseIn
    {
        Datum       datum;          /* индексируемое значение */
        Datum       leafDatum;      /* данные для записи в лист (все или суффикс) */
        int         level;          /* текущая глубина в дереве, считая с 0 */
    
        /* Содержимое текущей вершины */
        bool        allTheSame;     /* вершина помечена all-the-same? */
        bool        hasPrefix;      /* у вершины есть prefix? */
        Datum       prefixDatum;    /* если да, то значение prefix */
        int         nNodes;         /* количество дочерних узлов */
        Datum      *nodeLabels;     /* label'ы дочерних узлов в виде линейного массива */
    } spgChooseIn;
    
    typedef enum spgChooseResultType
    {
        spgMatchNode = 1,           /* давайте спустимся в один из дочерних узлов */
        spgAddNode,                 /* давайте добавим новый дочерний узел этой вершине */
        spgSplitTuple               /* давайте разобьем текущую вершину (поменяет ее prefix) */
    } spgChooseResultType;
    
    typedef struct spgChooseOut
    {
        spgChooseResultType resultType;     /* тип действия, 3 варианта, см. выше */
        union
        {
            struct                  /* если тип spgMatchNode */
            {
                int         nodeN;      /* номер узла, в который пойдем (от 0) */
                int         levelAdd;   /* прибавить вот столько к глубине */
                Datum       restDatum;  /* новое значение leafDatum */
            }           matchNode;
            struct                  /* если тип spgAddNode */
            {
                Datum       nodeLabel;  /* label нового узла */
                int         nodeN;      /* позиция вставки (от 0) */
            }           addNode;
            struct                  /* если тип spgSplitTuple */
            {
                /* Информация для создания верхней из 2 вершин после разбиения */
                bool        prefixHasPrefix;    /* вершина будет иметь prefix? */
                Datum       prefixPrefixDatum;  /* если да, то значение prefix */
                int         prefixNNodes;       /* число дочерних узлов */
                Datum      *prefixNodeLabels;   /* их label'ы */
                int         childNodeN;         /* номер дочернего узла, куда класть вторую вершину,
                                                *   образующуюся при разбиении (от 0)
                                                */
    
                /* Информация для создания нижней из 2 вершин (делается из текущей вершины и получает ее содержимое) */
                bool        postfixHasPrefix;   /* вершина будет иметь prefix? */
                Datum       postfixPrefixDatum; /* если да, то значение prefix */
            }           splitTuple;
        }           result;
    } spgChooseOut;
    

    datum — это исходное значение типа attType, которое должно был быть вставлено в индекс. Если есть метод compress, то leafDatum — это значение типа leafType, которое сперва получают вызовом compress, а потом при спуске по дереву методы choose или picksplit меняют его; когда процесс вставки достигает конечной страницы, текущее значение параметра leafDatum это то, что будет сохранено во вновь созданной листовой вершине. Если нет метода compress, то leafDatum не меняется при спуске по дереву и совпадает с datum. level — текущая глубина в дереве (прибавляется не всегда на +1, а вы ее меняете по своему усмотрению), для корня дерева 0. allTheSame имеет значение true, если текущая внутренняя вершина помечена как содержащая несколько эквивалентных узлов (см. Внутренние вершины "all-the-same"). hasPrefix имеет значение true, если текущая внутренняя вершина содержит префикс; и если содержит, то prefixDatum является его значением. nNodes — это число дочерних узлов, содержащихся в вершине, а nodeLabels — это массив значений их меток, или NULL, если нет никаких меток.

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

    Если новое значение соответствует одному из существующих дочерних узлов, установите resultType равным spgMatchNode. Установите nodeN равным индексу (с нуля) этого узла в массиве узлов. levelAdd — сколько прибавить к глубине, например, если вашим методам глубина не интересна, то оставляйте ноль, и ее не будут считать. Если ваши методы реализуют хранение только суффикса, то в restDatum положите остаток суффикса, а если нет, то положите туда тоже, что и пришло (leafDatum).

    Если необходимо добавить новый дочерний узел, установите resultType равным spgAddNode. Положите в nodeLabel метку, которая будет использоваться для нового узла, а в nodeN индекс (от нуля), в который необходимо вставить узел в массив узлов. После добавления узла метод choose будет вызван снова для той же самой вершины, и на этот раз должен привести к результату spgMatchNode.

    Если новое значение не соответствует префиксу вершины, установите resultType равным spgSplitTuple. Это действие перемещает все существующие узлы в новую внутреннюю вершину более низкого уровня, а текущую вершину превращает в вершину, имеющую одну нисходящую ссылку, указывающую на новую вершину более низкого уровня. Установите prefixHasPrefix, чтобы указать, должна ли новая верхняя вершина иметь префикс, и если да, то заполните prefixPrefixDatum значением префикса. Это новое значение префикса должно быть менее строгим, чем исходное, достаточно нестрогим, чтобы новое значение подходило. Установите prefixNNodes равным числу узлов, необходимых в новой вершине, и сразу же задайте им всем метки: в prefixNodeLabels поместите указатель на массив, выделенный с помощью palloc, содержащий их метки, или, если метки не требуются, то prefixNodeLabels = NULL. Обратите внимание, что общий размер новой верхней вершины не должен превышать общего размера вершины, которую он замещает; это ограничивает длину нового префикса и новых меток. Задайте childNodeN — номер дочернего узла, соответствующего нижней вершине, образовавшейся при разбиении. Для нижнего узла нужно задать только postfixHasPrefix и postfixPrefixDatum. Сочетание префиксов двух вершин и, возможно, метки узла должно иметь такое же семантическое значение, что и префикс вершины до её разбиения, потому что нет возможности пойти в дочерние узлы и там что-то поправить. После того, как узел был разделен, то функция choose будет вызвана снова для верхней из двух вершин. Этот вызов скорее всего вернет результат spgAddNode: раз старая вершина не годилась для вставки, то после разбиения вы захотите создать ей сестринскую.

    Итого, вы можете строить дерево, либо добавляя детей в текущую вершину, либо вставляя вершину над текущей, и добавлять детей уже к ней. Перебалансировку сделать нельзя.

  • picksplit

    Решает, как создать новую внутреннюю вершину над набором листовых вершин. Вызывается, когда узел, содержащий листовые вершины, переполнился, и надо превратить его во внутреннюю вершину, содержащую несколько узлов с тем же контентом.

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

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

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

    typedef struct spgPickSplitIn
    {
        int         nTuples;        /* кол-во листовых вершин */
        Datum      *datums;         /* их значения (линейный массив длины nTuples) */
        int         level;          /* текущая глубина (считая от 0) */
    } spgPickSplitIn;
    
    typedef struct spgPickSplitOut
    {
        bool        hasPrefix;      /* нужен ли prefix? */
        Datum       prefixDatum;    /* если да, то значение prefix'а */
    
        int         nNodes;         /* кол-во дочерних узлов */
        Datum      *nodeLabels;     /* их label'ы (или NULL, если не надо меток) */
    
        int        *mapTuplesToNodes;   /* раскладка листьев по дочерним узлам */
        Datum      *leafTupleDatums;    /* новые значения листовых узлов */
    } spgPickSplitOut;
    

    nTuples — количество листовых вершин, которые сейчас раскладываем. datums — это массив их значений типа leafType level это текущий уровень (глубина), одинаковый у всех листовых вершин, и у новой внутренней вершины, предположительно, будет такой же.

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

    Если во входных аргументах больше одного листа, то ожидается, что picksplit их как-то отклассифицирует и разделит на несколько узлов (picksplit вызывают с этой целью). Если picksplit поместит все предложенные листы в один узел, то ядро SP-GiST делает вывод, что они условно одинаковые, разделит их на узлы случайным образом (делить всё-таки надо из-за ограничения на количество дочерних листов). Эти несколько узлов все получат одинаковую метку (ту, которую вернула picksplit) и флаг allTheSame чтобы показать, что это произошло. Функции choose и inner_consistent должны проявлять надлежащую осторожность с такими внутренними вершинами. Дополнительную информацию смотрите в Внутренние вершины "all-the-same".

    Функция picksplit может быть запущена для 1 листа только в том случае, если функция config установила longValuesOK = true, и встретилось значение длиннее, чем влезает на страницу. В этом случае смысл операции состоит в том, чтобы побить значение на префикс (который сохранят во внутренней вершине) и суффикс, который сохранят в листе или, если он всё ещё слишком длинный, снова вызовут picksplit. Дополнительную информацию смотрите в Ограничения SP-GiST.

  • inner_consistent

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

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

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

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

    typedef struct spgInnerConsistentIn
    {
        /* Свойства исходного поискового запроса */
        ScanKey     scankeys;       /* массив значений, которые ищем, и предикатов (операторов) */
        ScanKey     orderbys;       /* массив операторов упорядочивания и значений для них */
        int         nkeys;          /* длина массива scankeys */
        int         norderbys;      /* длина массива orderbys */
    
        /* Состояние алгоритма обхода дерева */
        Datum       reconstructedValue;     /* кумулятивный префикс родителей */
        void       *traversalValue; /* накопительный объект класса операторов */
        MemoryContext traversalMemoryContext;   /* контекст памяти, на котором аллокировать traversalValue */
        int         level;          /* текущая глубина (от 0) */
        bool        returnData;     /* нужно ли восстанавливать оригинальное значение? */
    
        /* Свойства текущей внутренней вершины */
        bool        allTheSame;     /* она помечена all-the-same? */
        bool        hasPrefix;      /* у нее есть prefix? */
        Datum       prefixDatum;    /* если да, то какой */
        int         nNodes;         /* количество дочерних узлов */
        Datum      *nodeLabels;     /* метки дочерних узлов (NULL, если нет меток) */
    } spgInnerConsistentIn;
    
    typedef struct spgInnerConsistentOut
    {
        int         nNodes;         /* в сколько узлов (веток) надо сходить */
        int        *nodeNumbers;    /* массив с номерами узлов длины nNodes */
        int        *levelAdds;      /* на сколько увеличить глубину при входе в узел (массив длины nNodes) */
        Datum      *reconstructedValues;    /* кумулятивный префикс при входе в узел (массив длины nNodes)*/
        void      **traversalValues;        /* накопительные объекты (массив длины nNodes) */
        double    **distances;      /* массив из nNodes массивов из norderbys расстояний до выбранных узлов */
    } spgInnerConsistentOut;
    

    Массив scankeys длины nkeys описывает условия поиска в индексе. Эти условия объединяются по И(AND) — только строки, удовлетворяющие всем из них считаются подходящими. (Обратите внимание, что возможен вариант nkeys = 0, и это означает, что условия нет, и нужны просто все записи индекса). Обычно inner_consistent волнуют только поля sk_strategy и sk_argument каждой записи массива scankeys, которые соответственно дают оператор и значение сравнения. В частности, нет необходимости проверять sk_flags на предмет, является ли значение сравнения NULL, потому что основной код SP-GiST отфильтрует такие условия. Массив orderbys длины norderbys описывает операторы упорядочивания (если таковые имеются) аналогичным образом.

    reconstructedValue — аккумулятор префикса, накапливаемый при проходе от корня (из префиксов вершин и, возможно, меток узлов). При заходе в корень это 0, а дальше зависит от выходных значений inner_consistent. Если ваш класс операторов не использует восстановление значений по префиксам внутренних вершин, то используйте 0 на всех уровнях. reconstructedValue всегда типа leafType.

    traversalValue — указатель на любой ваш объект, который вы вернули из inner_consistent при заходе в родителя; для корня traversalValue == NULL. traversalMemoryContext — это контекст памяти, в котором надо аллокировать элементы traversalValues (см. ниже). level — текущая глубина. returnData имеет значение true, если в рамках запроса требуются восстановленные данные (если config вернула !canReturnData, то их не затребуют). allTheSame — свойство текущей вершины, в этом случае все узлы имеют одинаковую метку (если таковая имеется), и поэтому либо все, либо ни один из них не соответствует запросу (см. Внутренние вершины "all-the-same" ). hasPrefix + prefixDatum — префикс текущей вершины. nNodes — это число дочерних узлов, а nodeLabels — их метки.

    В результате работы nNodes устанавливается в число дочерних узлов (ветвей дерева), которые надо посетить, потому что там могут быть результаты, подходящем под запрос. Часто это всего один узел, но потенциально может быть много, и это усложняет интерфейс: все выходные результаты являются массивами из nNodes элементов, индекс в которых — это номер узла среди рекомендуемых. nodeNumbers — номера рекомендуемых узлов среди дочерних узлов вершины. levelAdds — приращение глубины при спуске в данный узел; обычно это +1 для всех узлов, но вы можете решить, что какие-то узлы "особо заглубленные", например, на основании метки; если никакие методы вашего класса операторов не интересуется глубиной, то можете оставить указатель levelAdds нулевым. Если ваш класс операторов использует восстановление значений по префиксам внутренних вершин, то вам нужно заполнить reconstructedValues для передачи в дочерние вершины. Если происходит поиск ближайших соседей, заполните distances расстояниями до узлов, которые рекомендуете посетить (внешний массив по номеру узла, внутренний по номеру метрики из orderbys), если нет, то оставьте указатель distances нулевым; узлы с меньшим расстоянием будут посещены в первую очередь.

    Если вам нужно передать какую-то дополнительную информацию в методы вашего класса операторов, заполните traversalValues, иначе оставьте его нулевым. Учтите, что массивы nodeNumbers, levelAdds, distances, reconstructedValues, и traversalValues надо выделять palloc'ом в текущем контексте, а элементы traversalValues надо выделять в контексте аллокации traversalMemoryContext, при этом каждый элемент должен быть отдельной единицей аллокации (нельзя использовать 1 единицу аллокации и положить в массив traversalValues указатель на ее середину).

  • leaf_consistent

    Возвращает true, если листовая вершина удовлетворяет запросу.

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

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

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

    typedef struct spgLeafConsistentIn
    {
        /* Свойства исходного поискового запроса */
        ScanKey     scankeys;       /* массив значений, которые ищем, и предикатов (операторов) */
        ScanKey     orderbys;       /* массив операторов упорядочивания и значений для них */
        int         nkeys;          /* длина массива scankeys */
        int         norderbys;      /* длина массива orderbys */
    
        /* Состояние алгоритма обхода дерева */
        Datum       reconstructedValue;     /* кумулятивный префикс родителей */
        void       *traversalValue; /* накопительный объект класса операторов */
        int         level;          /* текущая глубина (от 0) */
        bool        returnData;     /* нужно ли возвращать оригинальное значение столбца? */
    
        /* Свойства текущей листовой вершины */
        Datum       leafDatum;      /* данные, хранящиеся в листе */
    } spgLeafConsistentIn;
    
    typedef struct spgLeafConsistentOut
    {
        Datum       leafValue;        /* оригинальное значение столбца, если надо */
        bool        recheck;          /* true, если надо перепроверить условие по значению из строки кучи */
        bool        recheckDistances; /* true, если расстояние надо уточнить по значению из строки кучи */
        double     *distances;        /* массив из norderbys расстояний до данного листа  */
    } spgLeafConsistentOut;
    

    Массив scankeys длины nkeys описывает условия поиска в индексе. Эти условия объединяются по И(AND) — только строки, удовлетворяющие всем из них считаются подходящими. (Обратите внимание, что возможен вариант nkeys = 0, и это означает, что любой лист подходит). Обычно leaf_consistent волнуют только поля sk_strategy и sk_argument каждой записи массива scankeys, которые соответственно дают оператор и значение сравнения. В частности, нет необходимости проверять sk_flags на предмет, является ли значение сравнения NULL, потому что основной код SP-GiST отфильтрует такие условия. Массив orderbys длины norderbys описывает операторы упорядочивания (если таковые имеются) аналогичным образом.

    reconstructedValue — аккумулятор префикса, накопленный при проходе от корня. Может быть NULL, если префикс не собирали; имеет тип leafType. traversalValue указатель на любой ваш объект, который вы вернули из inner_consistent при заходе в родителя. level — глубина листа (если вы ее считали). returnData имеет значение true, если нужно восстановить исходные данные столбца (если config вернула !canReturnData, то их не затребуют). leafDatum — это значение в листовой вершине типа leafType.

    Функция должна возвращать true, если лист соответствует запросу, иначе false. Если результат true, и returnData true, тогда надо заполнить leafValue значением столбца (типа attType). Это может быть в точности leafDatum или комбинация из reconstructedValue и leafDatum. Также, recheck может быть установлено в true, если соответствие является не стопроцентным, и надо перепроверить условие на значении, взятом из строки кучи. Если выполняется упорядоченный поиск, заполните массив distances для массива значений расстояний в соответствии с массивом orderbys. В противном случае оставьте его NULL. Если хотя бы одно из возвращенных расстояний не является точным, установите recheckDistances в true; в этом случае исполнитель вычислит точные расстояния после извлечения строки из кучи и при необходимости переупорядочит строки.

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

  • compress

    Преобразует индексируемое значение (типа attType) в формат для физического хранения в листовой вершине индекса (типа leafType). Выходное значение не должно быть помещенным в TOAST.

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

    CREATE FUNCTION my_compress(internal) RETURNS internal ...
    

Все вспомогательные методы SP-GiST обычно вызываются в контексте кратковременной памяти; то есть, CurrentMemoryContext сбрасывается после обработки каждой вершины, поэтому можно не освобождать память. Метод config является исключением: он должен стараться избегать утечки памяти. Но обычно методу config незачем выделять память.

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

Реализация

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

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

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

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

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

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

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

Внутренние вершины "all-the-same"

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

При работе choose с allTheSame-вершиной результат выбора spgMatchNode интерпретируется как "вставить в любой из узлов", значение nodeN игнорируется. Выбор spgAddNode вообще не допустим и вызовет ошибку (т.к. получилось бы, что часть узлов "all-the-same", а новый узел особенный).

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