Индексы GiST

Введение

GiST означает "обобщенное поисковое дерево" (Generalized Search Tree). Это сбалансированный, древовидный метод доступа, который работает как основа для произвольной схемы индексирования. B-деревья, R-деревья и многие другие схемы индексирования могут быть реализованы с помощью GiST.

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

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

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

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

По историческим причинам, класс операторов inet_ops не является классом по умолчанию для типов inet и cidr. Чтобы использовать его, указывайте имя класса явно в CREATE INDEX, например

CREATE INDEX ON my_table USING GIST (my_inet_column inet_ops);

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

Традиционно, внедрение нового метода доступа к индексам означало много сложной работы. Необходимо было разобраться во внутренней работе базы данных: принципах работы менеджера блокировок и журнала упреждающей записи. Интерфейс GiST имеет высокий уровень абстракции, требующий от автора метода доступа только реализации семантики типа данных, к которому происходит обращение. Сам слой GiST заботится о параллелизме, журналировании и поиске в древовидной структуре.

Эту расширяемость не следует путать с расширяемостью других стандартных поисковых деревьев в плане типов данных, которые они могут обрабатывать. Например, QHB поддерживает расширяемые B-деревья и хэш-индексы. Это означает, что в QHB вы можете построить B-дерево или хэш-индекс над любым типом данных, каким захотите. Но B-деревья поддерживают только предикаты диапазона (<, =, >), а хэш-индексы только равенства.

Таким образом, если вы проиндексируете, скажем, коллекцию изображений с помощью B-дерева, вы сможете делать только запросы вида “изображение А равно изображению Б?”, “изображение А меньше изображения Б?” и т.п. В зависимости от того, как вы определяете “равно”, “меньше” и “больше” в этом контексте, это может иметь какой-то смысл. Однако, используя индекс на основе GiST, вы можете поддержать запросы, специфичные для предметной области, например "найти все изображения лошадей” или "найти все засвеченные фотографии".

Все, что требуется для запуска метода доступа GiST, — это реализовать несколько пользовательских методов, которые определяют поведение ключей в дереве. Конечно, эти методы должны быть довольно причудливыми, чтобы поддерживать причудливые запросы, но для всех стандартных запросов (B-деревья, R-деревья и т. д.) они довольно прямолинейны. Короче говоря, GiST сочетает в себе расширяемость с универсальностью, переиспользованием кода и чистым интерфейсом.

Существует пять методов, которые должен предоставить класс оператора индекса для GiST, и четыре, которые являются необязательными. Корректность индекса обеспечивается правильной реализацией методов same, consistent и union, а эффективность (размер и скорость работы) определяется методами penalty и picksplit.

Два из опциональных методов: compress и decompress позволяют индексу хранить во внутренних (т.е. нелистовых) вершинах дерева данные другого типа, нежели индексируемый тип. Листья в любом случае будут хранить данные такого же типа, как и индексируемый столбец, а другие узлы могут хранить произвольную структуру (C-style-struct), но все же в рамках общих ограничений QHB на типы данных (про данные переменной длины см. varlena). Если тот тип данных, что будет лежать в промежуточных вершинах дерева, существует на уровне SQL, то можно задать ему свойство STORAGE в команде CREATE OPERATOR CLASS. На самом деле, можно иметь много разных типов содержимого вершин. Есть главный тип, в котором производятся все вычисления при построении и навигации индекса, а при сохранении в вершины индекса вызывается compress, и в compress можно преобразовать в любой бинарный формат, в том числе с потерей информации. Если compress нет, то главный тип и содержимое всех вершин совпадает с индексируемым типом.

Необязательный метод №8 — distance, который нужен, если класс операторов хочет поддержать упорядоченные сканирования (поиск N ближайших соседей). Девятый метод fetch нужен, если класс операторов хочет поддерживать сканирование только по индексу, но при этом хранит альтернативный тип в промежуточных вершинах (использует compress/decompress).

  • consistent

    Для значения p в вершине индекса и поискового значения q, эта функция возвращает, является ли запрос q "согласованным" cо значением p. Для листовых записей индекса это эквивалентно проверке индексируемого условия, а для внутренних вершин дерева это определяет, необходимо ли сканировать соответствующее поддерево. Когда функция возвращает истину, она должна также заполнить флаг перепроверки recheck. Это указывает, является ли q безусловно подходящим или только возможно подходящим. Выставьте recheck = false, когда индекс полностью проверил условие предиката, а если recheck = true, то эта строка является только кандидатом на совпадение. В этом случае система будет перепроверять запрос на значении, взятом из строки. Такое соглашение позволяет GiST поддерживать как точные (lossless) так и грубые (lossy) индексы.

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

    CREATE OR REPLACE FUNCTION my_consistent(internal, data_type, smallint, oid, internal)
    RETURNS bool
    AS 'MODULE_PATHNAME'
    LANGUAGE C STRICT;
    

    Примерный шаблон реализации на C:

    PG_FUNCTION_INFO_V1(my_consistent);
    
    Datum
    my_consistent(PG_FUNCTION_ARGS)
    {
        GISTENTRY  *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
        data_type  *query = PG_GETARG_DATA_TYPE_P(1);
        StrategyNumber strategy = (StrategyNumber) PG_GETARG_UINT16(2);
        /* Oid subtype = PG_GETARG_OID(3); */
        bool       *recheck = (bool *) PG_GETARG_POINTER(4);
        data_type  *key = DatumGetDataType(entry->key);
        bool        retval;
    
        /*
        * Рассчитать возвращаемое значение как функцию от стратегии, ключа и запроса.
        *
        * Используйте GIST_LEAF(entry) чтобы понять, в каком месте дерева вас вызвали.
        * Это очень полезно. Например, при реализации оператора =
        *  вы можете во внутренних вершинах проверять, что пересечение не пусто,
        *  а в листьях проверять на точное равенство.
        */
    
        *recheck = true;        /* ну или false, если проверка была 100%-ная */
    
        PG_RETURN_BOOL(retval);
    }
    

    Здесь, key является элементом в индексе, а query — значение, которое ищут. Параметр StrategyNumber указывает, какой из операторов вашего класса применяется: он соответствует номер одного из оператора из команды CREATE OPERATOR CLASS.

    В зависимости от того, какие операторы вы включили в класс, тип данных query может быть разными, в том числе разным для разных операторов. В любом случае, он будет соответствовать типу второго аргумента оператора, а первый аргумент оператора будет главного типа содержимого индекса. (Приведенная выше заготовка кода предполагает, что все запросы будет одинакового типа data_type; если это не так, то сначала надо узнать тип второго параметра оператора, а потом доставать значение из query.) В SQL-объявлении функции consistent рекомендуется указывать тип данных query совпадающим с индексируемым типом данных, даже если реально передаваемый тип данных может быть другим в зависимости от оператора.

  • union

    Этот метод объединяет информацию в дереве: получает на вход содержимое нескольких вершин, и создаёт подходящее содержимое для их общей родительской вершины.

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

    CREATE OR REPLACE FUNCTION my_union(internal, internal)
    RETURNS storage_type
    AS 'MODULE_PATHNAME'
    LANGUAGE C STRICT;
    

    Примерный шаблон реализации на C:

    PG_FUNCTION_INFO_V1(my_union);
    
    Datum
    my_union(PG_FUNCTION_ARGS)
    {
        GistEntryVector *entryvec = (GistEntryVector *) PG_GETARG_POINTER(0);
        GISTENTRY  *ent = entryvec->vector;
        data_type  *out,
                *tmp,
                *old;
        int         numranges,
                    i = 0;
    
        numranges = entryvec->n;
        tmp = DatumGetDataType(ent[0].key);
        out = tmp;
    
        if (numranges == 1)
        {
            out = data_type_deep_copy(tmp);
    
            PG_RETURN_DATA_TYPE_P(out);
        }
    
        for (i = 1; i < numranges; i++)
        {
            old = out;
            tmp = DatumGetDataType(ent[i].key);
            out = my_union_implementation(out, tmp);
        }
    
        PG_RETURN_DATA_TYPE_P(out);
    }
    

    Как вы можете видеть, в этой заготовке мы считаем, что для нашего типа данных union (X, Y, Z) = union(union(X, Y), Z). Но поддержать типы данных, для которых это не так, тоже будет несложно.

    Результатом функции объединения должно быть значение главного типа содержимого индекса (как говорилось выше, он может отличаться или не отличаться от индексируемого типа). Функция union должна возвращать указатель на кусок памяти, выделенной с помощью palloc. Даже если результат совпадает с одним из входных аргументов, вы не может просто вернуть на него указатель, вы должны склонировать содержимое.

    Как видно из примера, первый внутренний (internal) аргумент функции union — это указатель GistEntryVector. Второй аргумент является указателем на целочисленную переменную, которую можно игнорировать.

  • compress

    Преобразует элемент данных в формат, подходящий для физического хранения на странице индекса. Если метод отсутствует, то элементы данных хранятся в индексе без изменений.

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

    CREATE OR REPLACE FUNCTION my_compress(internal)
    RETURNS internal
    AS 'MODULE_PATHNAME'
    LANGUAGE C STRICT;
    

    Примерный шаблон реализации на C:

    PG_FUNCTION_INFO_V1(my_compress);
    
    Datum
    my_compress(PG_FUNCTION_ARGS)
    {
        GISTENTRY  *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
        GISTENTRY  *retval;
    
        if (entry->leafkey)
        {
            // заменить entry->key заархивированной версией
    
            compressed_data_type *compressed_data = palloc(sizeof(compressed_data_type));
    
            /* здесь заполнить *compressed_data на основании entry->key ... */
    
            retval = palloc(sizeof(GISTENTRY));
            gistentryinit(*retval, PointerGetDatum(compressed_data),
                        entry->rel, entry->page, entry->offset, FALSE);
        }
        else
        {
            // Как правило, для нелистовых вершин ничего не надо делать
            retval = entry;
        }
    
        PG_RETURN_POINTER(retval);
    }
    

    В этом коде нужно заменить compressed_data_type на индексируемый тип, так как содержимое листовых узлов должно быть такого типа.

  • decompress

    Преобразует сохраненное представление данных в главный тип содержимого, которым могут манипулировать другие методы GiST в классе операторов. Если метод декомпрессии отсутствует, предполагается, что другие методы GiST могут работать непосредственно на сохраненном формате данных. Декомпрессия не обязательно противоположна компрессии; в частности, если сжатие с потерями, для декомпрессии невозможно точно восстановить исходные данные. Поведение decompress и fetch также могут различаться т.к. первое возвращает главный тип содержимого индекса (например, тип первого аргумента consistent), а второе — индексируемый тип, и эти типы могут различаться.

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

    CREATE OR REPLACE FUNCTION my_decompress(internal)
    RETURNS internal
    AS 'MODULE_PATHNAME'
    LANGUAGE C STRICT;
    

    Тривиальная реализация на C:

    PG_FUNCTION_INFO_V1(my_decompress);
    
    Datum
    my_decompress(PG_FUNCTION_ARGS)
    {
        PG_RETURN_POINTER(PG_GETARG_POINTER(0));
    }
    

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

  • penalty

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

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

    CREATE OR REPLACE FUNCTION my_penalty(internal, internal, internal)
    RETURNS internal
    AS 'MODULE_PATHNAME'
    LANGUAGE C STRICT;  -- в некоторых случаях у вас получится нестрогая функция
    

    Шаблон реализации на C:

    PG_FUNCTION_INFO_V1(my_penalty);
    
    Datum
    my_penalty(PG_FUNCTION_ARGS)
    {
        GISTENTRY  *origentry = (GISTENTRY *) PG_GETARG_POINTER(0);
        GISTENTRY  *newentry = (GISTENTRY *) PG_GETARG_POINTER(1);
        float      *penalty = (float *) PG_GETARG_POINTER(2);
        data_type  *orig = DatumGetDataType(origentry->key);
        data_type  *new = DatumGetDataType(newentry->key);
    
        *penalty = my_penalty_implementation(orig, new);
        PG_RETURN_POINTER(penalty);
    }
    

    По историческим причинам, penalty не возвращает результат типа float, а кладет его по указателю, переданному третьим аргументом. А собственно возвращаемое значение функции игнорируется; но принято возвращать указатель на результат как в примере.

    Функция penalty имеет решающее значение для хорошей работы индекса. Она используется во время вставки, чтобы определить, в какую ветвь пойти при выборе места для добавления новой записи в дереве. Во время выполнения запроса, чем больше сбалансирован индекс, тем быстрее выполняется поиск.

  • picksplit

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

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

    CREATE OR REPLACE FUNCTION my_picksplit(internal, internal)
    RETURNS internal
    AS 'MODULE_PATHNAME'
    LANGUAGE C STRICT;
    

    Шаблон реализации на C:

    PG_FUNCTION_INFO_V1(my_picksplit);
    
    Datum
    my_picksplit(PG_FUNCTION_ARGS)
    {
        GistEntryVector *entryvec = (GistEntryVector *) PG_GETARG_POINTER(0);
        GIST_SPLITVEC *v = (GIST_SPLITVEC *) PG_GETARG_POINTER(1);
        OffsetNumber maxoff = entryvec->n - 1;
        GISTENTRY  *ent = entryvec->vector;
        int         i,
                    nbytes;
        OffsetNumber *left,
                *right;
        data_type  *tmp_union;
        data_type  *unionL;
        data_type  *unionR;
        GISTENTRY **raw_entryvec;
    
        maxoff = entryvec->n - 1;
        nbytes = (maxoff + 1) * sizeof(OffsetNumber);
    
        v->spl_left = (OffsetNumber *) palloc(nbytes);
        left = v->spl_left;
        v->spl_nleft = 0;
    
        v->spl_right = (OffsetNumber *) palloc(nbytes);
        right = v->spl_right;
        v->spl_nright = 0;
    
        unionL = NULL;
        unionR = NULL;
    
        /* Initialize the raw entry vector. */
        raw_entryvec = (GISTENTRY **) palloc(entryvec->n * sizeof(void *));
        for (i = FirstOffsetNumber; i <= maxoff; i = OffsetNumberNext(i))
            raw_entryvec[i] = &(entryvec->vector[i]);
    
        for (i = FirstOffsetNumber; i <= maxoff; i = OffsetNumberNext(i))
        {
            int         real_index = raw_entryvec[i] - entryvec->vector;
    
            tmp_union = DatumGetDataType(entryvec->vector[real_index].key);
            Assert(tmp_union != NULL);
    
            /*
            * Выбрать, куда положить элемент индекса и соответственно изменить unionL и unionR
            * Добавить его в v->spl_left, либо в v->spl_right, и счетчики тоже изменить соответственно.
            */
    
            if (my_choice_is_left(unionL, curl, unionR, curr))
            {
                if (unionL == NULL)
                    unionL = tmp_union;
                else
                    unionL = my_union_implementation(unionL, tmp_union);
    
                *left = real_index;
                ++left;
                ++(v->spl_nleft);
            }
            else
            {
                // то же самое для направо...
            }
        }
    
        v->spl_ldatum = DataTypeGetDatum(unionL);
        v->spl_rdatum = DataTypeGetDatum(unionR);
        PG_RETURN_POINTER(v);
    }
    

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

    Как и penalty, функция picksplit имеет решающее значение для хорошей работы индекса. Придумать, как будут работать penalty и picksplit — самое сложное в дизайне GiST-индекса.

  • same

    Возвращает true, если две записи индекса идентичны, в противном случае false.

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

    CREATE OR REPLACE FUNCTION my_same(storage_type, storage_type, internal)
    RETURNS internal
    AS 'MODULE_PATHNAME'
    LANGUAGE C STRICT;
    

    Шаблон реализации на C:

    PG_FUNCTION_INFO_V1(my_same);
    
    Datum
    my_same(PG_FUNCTION_ARGS)
    {
        prefix_range *v1 = PG_GETARG_PREFIX_RANGE_P(0);
        prefix_range *v2 = PG_GETARG_PREFIX_RANGE_P(1);
        bool       *result = (bool *) PG_GETARG_POINTER(2);
    
        *result = my_eq(v1, v2);
        PG_RETURN_POINTER(result);
    }
    

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

  • distance

    Для значения p в вершине индекса и поискового значения q, эта функция возвращает "расстояние" от q до p. Для листовой вершины это скорее всего точное расстояние между двумя точками, а для нелистовой вершины следует понимать это как расстояние от q до ближайшего элемента из поддерева (возможно, заниженное, но не завышенное). Эта функция должна быть предоставлена, если класс операторов содержит какие-либо операторы упорядочивания. Запрос, использующий оператор упорядочивания, будет реализован путем возврата записей индекса с наименьшими значениями "расстояния", поэтому работа distance должна быть согласованы с семантикой этого оператора.

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

    CREATE OR REPLACE FUNCTION my_distance(internal, data_type, smallint, oid, internal)
    RETURNS float8
    AS 'MODULE_PATHNAME'
    LANGUAGE C STRICT;
    

    Примерный шаблон реализации на C:

    PG_FUNCTION_INFO_V1(my_distance);
    
    Datum
    my_distance(PG_FUNCTION_ARGS)
    {
        GISTENTRY  *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
        data_type  *query = PG_GETARG_DATA_TYPE_P(1);
        StrategyNumber strategy = (StrategyNumber) PG_GETARG_UINT16(2);
        /* Oid subtype = PG_GETARG_OID(3); */
        /* bool *recheck = (bool *) PG_GETARG_POINTER(4); */
        data_type  *key = DatumGetDataType(entry->key);
        double      retval;
    
        /*
        * Вычисление результата как функции от стратегии(оператора), ключа и поискового значения
        */
    
        PG_RETURN_FLOAT8(retval);
    }
    

    Аргументы у distance такие же, как и у consistent.

    Допускаются неточности при вычислении расстояния, главное вернуть не больше, чем реальное расстояние. Например, в геометрических приложениях расстояние до группы обычно считают как расстояние до ограничивающего группу параллелипипеда. Для внутренней вершины дерева возвращаемое расстояние не должно быть больше расстояния до любого из дочерних вершин. Если возвращенное расстояние не является точным, функция должна установить *recheck в true. (Это не обязательно для внутренних вершин дерева; для них вычисление всегда предполагается неточным). В этом случае движок вычислит точное расстояние после извлечения строки из кучи и при необходимости пересортирует строки.

    Если функция расстояния хотя бы иногда возвращает *recheck = true, то тип (float8/float4) и масштаб значений должны быть такие же как и у исходного оператора упорядочивания, потому что будут сортировать результаты distance с результатами оператора вперемешку. А если всегда *recheck = false, то результаты distance могут быть любыми float8 значениями, несогласованными с оператором, т.к. их будут сравнивать только между собой. (Бесконечность и минус бесконечность зарезервированы для обработки специальных случаев, таких как NULL, поэтому не надо возвращать такие значения).

  • fetch

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

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

    CREATE OR REPLACE FUNCTION my_fetch(internal)
    RETURNS internal
    AS 'MODULE_PATHNAME'
    LANGUAGE C STRICT;
    

    Аргумент является указателем на структуру GISTENTRY. На входе, поле key — содержимое листа дерева в сжатом виде (т.е. результат работы compress), NOT NULL. Возвращаемое значение — другая GISTENTRY, чье поле key содержит те же данные в исходном, несжатом виде. Если функция compress класса операторов предостаелена, но ничего не делает для листовых записей, то метод fetch может возвращать аргумент без изменений. Если же функции compress вообще нет, тогда и fetch не нужна.

    Шаблон реализации на C:

    PG_FUNCTION_INFO_V1(my_fetch);
    
    Datum
    my_fetch(PG_FUNCTION_ARGS)
    {
        GISTENTRY  *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
        input_data_type *in = DatumGetPointer(entry->key);
        fetched_data_type *fetched_data;
        GISTENTRY  *retval;
    
        retval = palloc(sizeof(GISTENTRY));
        fetched_data = palloc(sizeof(fetched_data_type));
    
        /*
        * Собственно преобразовать fetched_data в Datum исходного индексируемого типа
        */
    
        /* fill *retval from fetched_data. */
        gistentryinit(*retval, PointerGetDatum(converted_datum),
                    entry->rel, entry->page, entry->offset, FALSE);
    
        PG_RETURN_POINTER(retval);
    }
    

    Если функция compress сохраняет данные в листах с искажением (с потерей информации), то класс оператора не может поддерживать сканирование только по индексу и не должен определять функцию fetch.

Все методы поддержки GiST обычно вызываются в короткоживущих контекстах памяти, то есть CurrentMemoryContext сбрасывается после обработки каждого кортежа. Это позволяет не беспокоиться о вызовах pfree. Однако в некоторых случаях хотелось бы иметь долгоживущий объект для кэширования данных при повторных вызовах. Чтобы сделать это, выделите память в контексте fcinfo->flinfo->fn_mcxt, и положите указатель в fcinfo->flinfo->fn_extra. Время жизни такого объекта — одна индексная операция (одно сканирование, одна вставка или построение индекса). Если вы заменяете fcinfo->flinfo->fn_extra, а там было ненулевое значение, то вы должны его освободить, иначе будут утечки.

Реализация

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

Однако для построения индекса с буферизацией будет больше вызовов penalty, т.е. больше нагрузка на процессор. Кроме того, требуется дополнительное временное пространство на диске, примерно равное итоговому размеру индекса. Также построение с буферизацией и без может приводить к разным по качеству индексам. Это зависит от реализации penalty, picksplit и операторов. Более качественный (сбалансированный) индекс может получиться как при одном, так и при другом алгоритме построения индекса.

Глобально поведение управляется параметром effective_cache_size: когда размер индекса превышает или явно собирается превысить effective_cache_size, построение GiST-индекса переключается на буферизованный метод. Также буферизацию можно включить/выключить явно для конкретного индекса. Для этого используется опция buffering команды CREATE INDEX. Поведение по умолчанию подходит для большинства случаев, но отключение буферизации может ускорить построение, если вам известно, что входные данные упорядочены.

Примеры

Исходный дистрибутив QHB содержит несколько примеров индексных методов, реализованных на основе GiST. В основной дистрибутив входит полнотекстовый поиск (типы tsvector и tsquery), а также R-Деревья для некоторых встроенных типов геометрических данных.

Следующие модули из contrib также содержат классы операторов GiST:

МодульОписание функционала
btree_gistФункциональность, эквивалентная B-дереву для некоторых типов данных
cubeИндексация многомерных кубов
hstoreМодуль для хранения пар (ключ, значение)
intarrayRD-дерево для одномерного массива int4
ltreeИндексирование древовидных путей
pg_trgmСтепень сходства текстов в метрике триграмм
segИндексирование интервалов действительных чисел