Индексы GiST

Введение

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

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

Часть представленной здесь информации взята с сайта Проекта индексации GiST Калифорнийского университета в Беркли и из тезисов диссертации Марселя Корнакера (Marcel Kornacker) «Access Methods for Next-Generation Database Systems».

---

---

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

В основной дистрибутив QHB включены классы операторов GiST, перечисленные в Таблице 1. (Некоторые из специализированных модулей, описанных в главе Расширения, предоставляют дополнительные классы операторов GiST.)

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

Имя	Операторы упорядочивания	Индексируемые операторы
box_ops	<-> (box, point)	<< (box, box)
		&< (box, box)
		&& (box, box)
		&> (box, box)
		>> (box, box)
		~= (box, box)
		@> (box, box)
		<@ (box, box)
		&<| (box, box)
		<<| (box, box)
		|>> (box, box)
		|&> (box, box)
		~ (box, box)
		@ (box, box)
circle_ops	<-> (circle, point)	<< (circle, circle)
		&< (circle, circle)
		&> (circle, circle)
		>> (circle, circle)
		<@ (circle, circle)
		@> (circle, circle)
		~= (circle, circle)
		&& (circle, circle)
		|>> (circle, circle)
		<<| (circle, circle)
		&<| (circle, circle)
		|&> (circle, circle)
		@ (circle, circle)
		~ (circle, circle)
inet_ops		<< (inet, inet)
		<<= (inet, inet)
		>> (inet, inet)
		>>= (inet, inet)
		= (inet, inet)
		<> (inet, inet)
		< (inet, inet)
		<= (inet, inet)
		> (inet, inet)
		>= (inet, inet)
		&& (inet, inet)
multirange_ops		= (anymultirange, anymultirange)
		&& (anymultirange, anymultirange)
		&& (anymultirange, anyrange)
		@> (anymultirange, anyelement)
		@> (anymultirange, anymultirange)
		@> (anymultirange, anyrange)
		<@ (anymultirange, anymultirange)
		<@ (anymultirange, anyrange)
		<< (anymultirange, anymultirange)
		<< (anymultirange, anyrange)
		>> (anymultirange, anymultirange)
		>> (anymultirange, anyrange)
		&< (anymultirange, anymultirange)
		&< (anymultirange, anyrange)
		&> (anymultirange, anymultirange)
		&> (anymultirange, anyrange)
		-|- (anymultirange, anymultirange)
		-|- (anymultirange, anyrange)
point_ops	<-> (point, point)	|>> (point, point)
		<< (point, point)
		>> (point, point)
		<<| (point, point)
		~= (point, point)
		<@ (point, box)
		<@ (point, polygon)
		<@ (point, circle)
poly_ops	<-> (polygon, point)	<< (polygon, polygon)
		&< (polygon, polygon)
		&> (polygon, polygon)
		>> (polygon, polygon)
		<@ (polygon, polygon)
		@> (polygon, polygon)
		~= (polygon, polygon)
		&& (polygon, polygon)
		<<| (polygon, polygon)
		&<| (polygon, polygon)
		|&> (polygon, polygon)
		|>> (polygon, polygon)
		@ (polygon, polygon)
		~ (polygon, polygon)
range_ops		= (anyrange, anyrange)
		&& (anyrange, anyrange)
		&& (anyrange, anymultirange)
		@> (anyrange, anyelement)
		@> (anyrange, anyrange)
		@> (anyrange, anymultirange)
		<@ (anyrange, anyrange)
		<@ (anyrange, anymultirange)
		<< (anyrange, anyrange)
		<< (anyrange, anymultirange)
		>> (anyrange, anyrange)
		>> (anyrange, anymultirange)
		&< (anyrange, anyrange)
		&< (anyrange, anymultirange)
		&> (anyrange, anyrange)
		&> (anyrange, anymultirange)
		-|- (anyrange, anyrange)
		-|- (anyrange, anymultirange)
tsquery_ops		<@ (tsquery, tsquery)
		@> (tsquery, tsquery)
tsvector_ops		@@ (tsvector, tsquery)

По историческим причинам класс операторов 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-дерева QHB, то сможете делать только запросы вида «изображение А равно изображению Б?», «изображение А меньше изображения Б?» и т. п. В зависимости от того, как вы определяете «равно», «меньше» и «больше» в этом контексте, это может быть полезно. Однако с помощью индекса на основе GiST можно найти способы задавать специфичные для предметной области вопросы, например «найти все изображения лошадей» или «найти все засвеченные фотографии».

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

Существует пять методов, которые класс операторов индекса обязан предоставить для GiST, и шесть необязательных. Корректность индекса обеспечивается правильной реализацией методов same, consistent и union, а эффективность (размер и скорость работы) определяется методами penalty и picksplit. Два необязательных метода, compress и decompress, позволяют индексу хранить во внутренних (т.е. не листовых) вершинах дерева данные другого типа, нежели индексируемые. В листьях должны храниться данные индексируемого типа, тогда как в других узлах может храниться любая структура C/RUST (но все же в рамках общих правил QHB, касающихся типов данных; про данные переменной длины говорится в описании varlena). Если внутренний тип данных дерева существует на уровне SQL, в команде CREATE OPERATOR CLASS можно указать параметр STORAGE. Необязательный восьмой метод distance необходимо реализовывать, если классу операторов понадобится поддерживать упорядоченные сканирования (поиски ближайших соседей). Необязательный девятый метод fetch необходимо реализовывать, если классу операторов понадобится поддерживать сканирования только по индексу, за исключением случаев, когда метод compress опущен. Необязательный десятый метод options необходимо реализовывать, если класс операторов содержит параметры, определяемые пользователем. Необязательный одиннадцатый метод sortsupport используется для ускорения построения индекса GiST.

consistent

Для переданной записи индекса p и значения запроса q эта функция определяет, является ли запись индекса «согласованной» с запросом; то есть может ли предикат «индексированный_столбец индексируемый_оператор q» равняться true для какой-либо строки, представленной данной записью индекса? Для листовых записей индекса это равнозначно проверке индексируемого условия, в то время как для внутреннего узла дерева это определяет, необходимо ли сканировать поддерево индекса, представленного этим узлом дерева. Когда результат равен true, также должен вернуться флаг recheck. Это показывает, является ли предикат безусловно подходящим или только возможно подходящим. Если recheck = false, то индекс полностью проверил условие предиката, а если recheck = true, то эта строка является только кандидатом на соответствие. В этом случае система будет автоматически вычислять индексируемый_оператор по фактическому значению строки, чтобы точно узнать, действительно ли оно соответствует запросу. Это соглашение позволяет GiST поддерживать как точные, так и неточные индексы.

В 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), чтобы понять, в каком месте дерева произошел
     * вызов, что может быть полезно, например, при реализации оператора =
     * (можно проверить непустое union() в нелистовых узлах и равенство в листовых).
     */

    *recheck = true;        /* или false, если проверка точная */

    PG_RETURN_BOOL(retval);
}

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

В зависимости от того, какие операторы вы включили в этот класс, тип данных query может быть разным для разных операторов, поскольку это будет тот тип, который находится в правой части оператора, а он может отличаться от типа индексируемых данных, находящегося в левой части. (Приведенная выше заготовка кода предполагает, что возможен только один тип; в ином случае получение значения аргумента 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). Но поддержать типы данных, для которых это не так, тоже будет несложно, если реализовать соответствующий алгоритм объединения в этом вспомогательном методе GiST.

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

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

compress

Преобразует элемент данных в формат, подходящий для физического хранения на странице индекса. Если метод 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 в этом классе операторов. Если метод decompress опущен, предполагается, что другие методы GiST могут работать непосредственно с сохраненным форматом данных. (Метод decompress необязательно противоположен методу compress; в частности, если compress неточный, decompress не в состоянии точно восстановить исходные данные. Также decompress не обязательно равнозначен fetch, поскольку другим методам GiST может не требоваться полное восстановление данных.)

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

Возвращает значение, показывающее «стоимость» добавления новой записи в определенную ветвь дерева. Элементы будут добавлять по пути с наименьшим значением penalty в дереве. Значения, возвращаемые 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;

    /* Инициализировать чистый вектор записи. */
    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 является изменение переданной структуры v. Собственно возвращаемое значение функции игнорируется, хотя в нем принято возвращать адрес v.

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

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 эта функция определяет «расстояние» между записью индекса и значением запроса. Эту функцию необходимо представлять, если класс операторов содержит какие-либо операторы упорядочивания. Запрос, использующий оператор упорядочивания, будет реализован путем возвращения записей индекса с наименьшими значениями «расстояния» первыми, поэтому результат должен быть согласован с семантикой оператора. Для листовой записи индекса результат просто представляет расстояние до записи индекса; для внутреннего узла дерева результат должен быть наименьшим расстоянием, которое может быть получено среди дочерних записей.

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, а результирующие значения функции расстояния должны быть совместимы со значениями исходного оператора упорядочивания, поскольку исполнитель будет проводить сортировку, используя как результаты функции расстояния, так и пересчитанные результаты оператора упорядочивания. В противном случае результирующие значения функции расстояния могут быть любыми конечными значениями float8, при условии, что относительный порядок этих результирующих значений соответствует порядку, возвращенному оператором упорядочивания. (Бесконечность и минус бесконечность применяются внутри для работы с особыми случаями, например с NULL, поэтому возвращать такие значения из функций distance не рекомендуется.)

fetch

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

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

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

Аргумент является указателем на структуру GISTENTRY. В записи поле key содержит отличные от NULL листовые данные в сжатом виде. Возвращаемое значение — это еще одна структура GISTENTRY, чье поле key содержит те же данные в исходном, несжатом виде. Если функция сжатия класса операторов ничего не делает для листовых записей, то метод fetch может возвращать этот аргумент как есть. Или, если у класса операторов нет функции сжатия, метод 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 исходного типа данных.
     */

    /* заполнить *retval из fetched_data. */
    gistentryinit(*retval, PointerGetDatum(converted_datum),
                entry->rel, entry->page, entry->offset, FALSE);

    PG_RETURN_POINTER(retval);
}

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

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().

Ниже показан пример реализации функции my_options() и использования параметров из других вспомогательных функций:

typedef enum MyEnumType
{
    MY_ENUM_ON,
    MY_ENUM_OFF,
    MY_ENUM_AUTO
} MyEnumType;

typedef struct
{
    int32   vl_len_;    /* заголовок varlena (не затрагивайте его напрямую!) */
    int     int_param;  /* целочисленный параметр */
    double  real_param; /* параметр с плавающей запятой */
    MyEnumType enum_param; /* перечислимый параметр */
    int     str_param;  /* строковый параметр */
} MyOptionsStruct;

/* Строковое представление перечислимых значений */
static relopt_enum_elt_def myEnumValues[] =
{
    {"on", MY_ENUM_ON},
    {"off", MY_ENUM_OFF},
    {"auto", MY_ENUM_AUTO},
    {(const char *) NULL}   /* завершающий элемент списка */
};

static char *str_param_default = "default";

/*
 * Пример функции проверки допустимости: проверяет, что строка не длиннее 8 байт.
 */
static void
validate_my_string_relopt(const char *value)
{
    if (strlen(value) > 8)
        ereport(ERROR,
                (errcode(ERRCODE_INVALID_PARAMETER_VALUE),
                 errmsg("str_param must be at most 8 bytes")));
}

/*
 * Пример функции-заполнителя: переводит символы в нижний регистр.
 */
static Size
fill_my_string_relopt(const char *value, void *ptr)
{
    char   *tmp = str_tolower(value, strlen(value), DEFAULT_COLLATION_OID);
    int     len = strlen(tmp);

    if (ptr)
        strcpy((char *) ptr, tmp);

    pfree(tmp);
    return len + 1;
}

PG_FUNCTION_INFO_V1(my_options);

Datum
my_options(PG_FUNCTION_ARGS)
{
    local_relopts *relopts = (local_relopts *) PG_GETARG_POINTER(0);

    init_local_reloptions(relopts, sizeof(MyOptionsStruct));
    add_local_int_reloption(relopts, "int_param", "integer parameter",
                            100, 0, 1000000,
                            offsetof(MyOptionsStruct, int_param));
    add_local_real_reloption(relopts, "real_param", "real parameter",
                             1.0, 0.0, 1000000.0,
                             offsetof(MyOptionsStruct, real_param));
    add_local_enum_reloption(relopts, "enum_param", "enum parameter",
                             myEnumValues, MY_ENUM_ON,
                             "Valid values are: \"on\", \"off\" and \"auto\".",
                             offsetof(MyOptionsStruct, enum_param));
    add_local_string_reloption(relopts, "str_param", "string parameter",
                               str_param_default,
                               &validate_my_string_relopt,
                               &fill_my_string_relopt,
                               offsetof(MyOptionsStruct, str_param));

    PG_RETURN_VOID();
}

PG_FUNCTION_INFO_V1(my_compress);

Datum
my_compress(PG_FUNCTION_ARGS)
{
    int     int_param = 100;
    double  real_param = 1.0;
    MyEnumType enum_param = MY_ENUM_ON;
    char   *str_param = str_param_default;

    /*
     * Обычно когда класс операторов содержит метод 'options', параметры всегда
     * передаются вспомогательным функциям. Однако если вы добавите метод 'options'
     * в существующий класс операторов, в ранее определенных индексах параметров
     * не будет, поэтому необходима эта проверка.
     */
    if (PG_HAS_OPCLASS_OPTIONS())
    {
        MyOptionsStruct *options = (MyOptionsStruct *) PG_GET_OPCLASS_OPTIONS();

        int_param = options->int_param;
        real_param = options->real_param;
        enum_param = options->enum_param;
        str_param = GET_STRING_RELOPTION(options, str_param);
    }

    /* продолжение реализации вспомогательной функции */
}

Поскольку в GiST представление ключа гибкое, оно может зависеть от параметров, указанных пользователем. Например, можно задать длину ключа подписи. В качестве примера рассмотрите функцию gtsvector_options().

sortsupport

Возвращает функцию-компаратор для сортировки данных способом, сохраняющим локальность. Она используется командами CREATE INDEX и REINDEX. Качество построенного индекса зависит от того, насколько хорошо порядок сортировки, определенный функцией-компаратором, сохраняет локальность входных данных.

Метод sortsupport является необязательным. Если он не предоставляется, CREATE INDEX создает индекс путем добавления каждого кортежа в дерево с помощью функций penalty и picksplit, что происходит гораздо медленнее.

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

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

В аргументе передается указатель на структуру SortSupport. Как минимум, эта функция должна заполнить в ней поле компаратора. Компаратор принимает три аргумента: два элемента Datum для сравнения и указатель на структуру SortSupport. Элементы Datum представляют собой два индексированных значения в том формате, в котором они хранятся в индексе; то есть в формате, возвращаемом методом compress.

Соответствующий код в модуле C можно реализовать по этой заготовке:

PG_FUNCTION_INFO_V1(my_sortsupport);

static int
my_fastcmp(Datum x, Datum y, SortSupport ssup)
{
  /* установить порядок между x и y, вычислив некое сортирующее значение z */

  int z1 = ComputeSpatialCode(x);
  int z2 = ComputeSpatialCode(y);

  return z1 == z2 ? 0 : z1 > z2 ? 1 : -1;
}

Datum
my_sortsupport(PG_FUNCTION_ARGS)
{
  SortSupport ssup = (SortSupport) PG_GETARG_POINTER(0);

  ssup->comparator = my_fastcmp;
  PG_RETURN_VOID();
}

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

---

---

Реализация

Способы построения индексов GiST

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

Метод с сортировкой доступен, только если все классы операторов, используемые индексом, предоставляют функцию sortsupport, как описано в разделе Расширяемость. В таком случае этот метод обычно наиболее оптимален, поэтому используется по умолчанию.

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

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

Если сортировка невозможна, по умолчанию построение индекса GiST переключается на метод с буферизацией, когда размер индекса достигает значения effective_cache_size. Буферизацию можно принудительно включить или выключить вручную с помощью параметра buffering команды CREATE INDEX. Поведение по умолчанию подходит в большинстве случаев, но если входные данные упорядочены, выключение буферизации может некоторым образом ускорить построение индекса.

---

---

Примеры

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

Классы операторов GiST содержатся также в следующих модулях из share/extension:

btree_gist
Функциональность, равнозначная B-дереву, для нескольких типов данных

cube
Индексирование для многомерных кубов

hstore
Модуль для хранения пар (ключ, значение)

intarray
RD-дерево для одномерных массивов значений int4

ltree
Индексирование для древовидных структур

pg_trgm
Схожесть текстов с помощью сопоставления триграмм

seg
Индексирование «диапазонов чисел с плавающей запятой»