64.2. Индексы GiST #
64.2.1. Введение #
GiST расшифровывается как «Generalized Search Tree» (Обобщённое поисковое дерево). Это сбалансированный иерархический метод доступа, который представляет собой базовый шаблон, на основе которого могут реализовываться произвольные схемы индексации. На базе GiST могут быть реализованы B-деревья, R-деревья и многие другие схемы индексации.
Ключевым преимуществом GiST является то, что он позволяет разрабатывать дополнительные типы данных с соответствующими методами доступа экспертам в предметной области типа данных, а не специалистам по СУБД.
Представленная здесь информация частично позаимствована с сайта Проекта индексации GiST Калифорнийского университета в Беркли и из диссертации Марселя Корнакера Методы доступа для СУБД следующего поколения. Сопровождением реализации GiST в PostgreSQL в основном занимаются Фёдор Сигаев и Олег Бартунов; дополнительные сведения можно получить на их сайте.
64.2.2. Встроенные классы операторов #
В базовый дистрибутив PostgreSQL включены классы операторов GiST, перечисленные в Таблице 64.1. (Некоторые дополнительные модули, описанные в Приложении F, добавляют другие классы операторов GiST.)
Таблица 64.1. Встроенные классы операторов GiST
Имя | Индексируемые операторы | Операторы упорядочивания |
---|---|---|
box_ops | << (box, box) | <-> (box, point) |
&< (box, box) | ||
&& (box, box) | ||
&> (box, box) | ||
>> (box, box) | ||
~= (box, box) | ||
@> (box, box) | ||
<@ (box, box) | ||
&<| (box, box) | ||
<<| (box, box) | ||
|>> (box, box) | ||
|&> (box, box) | ||
circle_ops | << (circle, circle) | <-> (circle, point) |
&< (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, polygon) | <-> (polygon, point) |
&< (polygon, polygon) | ||
&> (polygon, polygon) | ||
>> (polygon, polygon) | ||
<@ (polygon, polygon) | ||
@> (polygon, polygon) | ||
~= (polygon, polygon) | ||
&& (polygon, polygon) | ||
<<| (polygon, polygon) | ||
&<| (polygon, polygon) | ||
|&> (polygon, polygon) | ||
|>> (polygon, polygon) | ||
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);
64.2.3. Расширяемость #
Реализация нового метода доступа индекса традиционно была большой и сложной задачей. Чтобы её решить, необходимо было понимать внутреннее устройство базы данных, в частности работу менеджера блокировок и журнала предзаписи. Но с интерфейсом GiST, реализующим высокий уровень абстракции, разработчик метода доступа должен реализовать только смысловое наполнение индексируемого типа данных. Уровень GiST берёт на себя заботу о параллельном доступе, поддержке журнала и поиске в структуре дерева.
Эту расширяемость не следует путать с расширяемостью других стандартных деревьев поиска в смысле поддержки различных типов данных. Например, PostgreSQL поддерживает расширяемость B-деревьев и индексов по хешу. Это означает, что в PostgreSQL вы можете построить B-дерево или хеш-таблицу по любому желаемому типу данных. Но такие B-деревья будут поддерживать только предикаты сравнений (<
, =
, >
), а индексы по хешу только запросы с равенством.
Поэтому, если вы проиндексируете в PostgreSQL в B-дереве, например, коллекцию изображений, вы сможете выполнять только проверки вида «равны ли изображения X и Y», «меньше ли изображение X изображения Y» и «больше ли изображение X изображения Y». Это может быть полезно, в зависимости от того, как вы определите операции «равно», «меньше» и «больше». Однако используя индекс на базе GiST, возможно удовлетворять и запросы из предметной области, например, «найти все изображения лошадей» или «найти все пересвеченные изображения».
Всё, что нужно, чтобы получить работающий метод доступа GiST — это реализовать несколько методов, определяющих поведение ключей в дереве. Конечно, эти методы должны быть довольно изощрёнными, чтобы поддерживать изощрённые запросы, но для всех стандартных запросов (B-деревьев, R-деревьев и т. д.) они относительно просты. Словом, GiST сочетает расширяемость с универсальностью, повторным использованием кода и аккуратным интерфейсом.
Класс операторов индекса GiST должен предоставить пять методов и может дополнительно предоставлять ещё шесть. Корректность индекса обеспечивается реализацией методов same
, consistent
и union
, а его эффективность (по размеру и скорости) будет зависеть от методов penalty
и picksplit
. Два необязательных метода, compress
и decompress
, позволяют реализовать внутреннее представление данных дерева, не совпадающее с типом индексируемых данных. Данные листьев индекса должны быть индексируемого типа, тогда как в остальных узлах дерева могут быть произвольные структуры C (но при этом должны соблюдаться правила, предъявляемые PostgreSQL к типам данных; прочитайте о varlena
для данных переменного размера). Если внутренний тип данных дерева существует на уровне SQL, в команде CREATE OPERATOR CLASS
можно использовать указание STORAGE
. Необязательный восьмой метод distance
нужно реализовать, только если класс операторов желает поддерживать упорядоченные сканирования (поиск ближайших соседей). Необязательный девятый метод fetch
требуется, если класс операторов должен поддерживать сканирование только индекса и при этом предоставляется метод compress
. Необязательный десятый метод options
необходим, если класс операторов содержит определяемые пользователем параметры. Необязательный одиннадцатый метод sortsupport
используется для ускорения построения индекса GiST.
consistent
Для переданной записи индекса
p
и значения запросаq
эта функция определяет, является ли запись индекса «соответствующей» запросу; то есть, может ли предикат «индексированный_столбец
индексируемый_оператор
q
» удовлетворяться для какой-либо строки, представленной данной записью индекса? Для записей на уровне листьев это равносильно проверке индексируемого условия, тогда как для внутреннего узла дерева требуется определить, нужно ли сканировать поддерево индекса, относящееся к данному узлу. Когда результат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), чтобы узнать текущую позицию в дереве индекса, * что удобно, например для поддержки оператора = (вы можете проверить * равенство в листьях дерева и непустое пересечение в остальных * узлах). */ *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
опускается, подразумевается, что эти методы могут работать непосредственно с форматом хранения данных. (Метод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 **) malloc(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
не просто возвращает результат булевого типа; вместо этого она должна сохранить флаг по адресу, указанному третьим аргументом. Собственно возвращаемое значение игнорируется, хотя в нём принято возвращать этот же адрес.расстояние
Для переданной записи индекса
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
. (Это необязательно для внутренних узлов дерева; для них результат всегда считается неточным.) В этом случае исполнитель вычислит точную дистанцию, выбрав кортеж из кучи, и переупорядочит кортежи при необходимости.Если функция distance возвращает
*recheck = true
для любого узла на уровне листьев, типом результата исходного оператора упорядочивания должен бытьfloat8
илиfloat4
, и значения результата функции distance должны быть сравнимы с результатами исходного оператора упорядочивания, так как исполнитель будет выполнять сортировку, используя и результаты функции distance, и уточнённые результаты оператора упорядочивания. В противном случае значениями результата distance могут быть любые конечные значения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
содержит те же данные в исходной, развёрнутой форме. Если функция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 исходного типа данных. */ /* Заполнить *retval из fetch_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
. Как минимум, данная функция должна заполнить в ней полеcomparator
. Компаратору передаются три аргумента: два элемента Datum для сравнения и указатель на структуруSortSupport
. В данном случае в Datum передаются индексированные значения в том формате, в котором они хранятся в индексе; то есть в формате, возвращаемом методомcompress
. Полный API определён в файлеsrc/include/utils/sortsupport.h
.Соответствующий код в модуле C должен реализовываться по такому шаблону:
PG_FUNCTION_INFO_V1(my_sortsupport); static int my_fastcmp(Datum x, Datum y, SortSupport ssup) { /* establish order between x and y by computing some sorting value 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
сбрасывается после обработки каждого кортежа. Таким образом можно не заботиться об освобождении любых блоков памяти, выделенных функцией palloc. Однако в некоторых случаях для опорного метода полезно кешировать какие-либо данные между вызовами. Для этого нужно разместить долгоживущие данные в контексте fcinfo->flinfo->fn_mcxt
и сохранить указатель на них в fcinfo->flinfo->fn_extra
. Такие данные смогут просуществовать всё время операции с индексом (например, одно сканирование индекса GiST, построение индекса или добавление кортежа в индекс). Не забудьте вызвать pfree для предыдущего значения, заменяя значение в fn_extra
, чтобы не допустить накопления утечек памяти в ходе операции.
64.2.4. Реализация #
64.2.4.1. Способы построения индексов GiST #
Самый простой способ построить индекс GiST — просто добавлять все записи одну за другой. Но для больших индексов это может занять много времени, поскольку если индексные кортежи разбросаны по всему индексу и он настолько велик, что не помещается в кеше, потребуется выполнить множество неупорядоченных операций ввода-вывода. PostgreSQL поддерживает два альтернативных метода начального построения индекса GiST: с сортировкой и с буферизацией.
Построение индекса с сортировкой возможно, только если все классы операторов, используемые индексом, предоставляют функцию sortsupport
, как описано в Подраздел 64.2.3. В таком случае данный метод используется по умолчанию, как оптимальный.
При построении индекса с буферизацией кортежи не вставляются в индекс немедленно. Это позволяет кардинально сократить число операций произвольного доступа, требующихся при обработке неупорядоченных наборов данных. Для хорошо упорядоченных наборов выигрыш может быть минимальным или вообще отсутствовать, так как всего несколько страниц будут принимать новые кортежи в один момент времени и эти страницы будут умещаться в кеше, даже если весь индекс очень большой.
При построении индекса с буферизацией приходится гораздо чаще вызывать функцию penalty
по сравнению с обычным построением, на что уходят дополнительные ресурсы процессора. Кроме того, буферам требуется временное место на диске, вплоть до размера результирующего индекса. Буферизация также может повлиять на качество результирующего индекса, как в положительную, так и в отрицательную сторону. Это влияние зависит от различных факторов, например, от распределения поступающих данных и от реализации класса операторов.
Если сортировка невозможна, по умолчанию при построении индекса GiST включается буферизация, когда размер индекса достигает значения effective_cache_size. Буферизацию можно принудительно включить или отключить вручную с помощью параметра buffering
команды CREATE INDEX. Поведение по умолчанию достаточно эффективно в большинстве случаев, но если входные данные упорядочены, выключив буферизацию, можно получить некоторое ускорение.
64.2.5. Примеры #
В дистрибутив исходного кода PostgreSQL включены несколько примеров методов индексов, реализованных на базе GiST. В настоящее время ядро системы обеспечивает поддержку текстового поиска (индексацию типов tsvector
и tsquery
), а также функциональность R-дерева для некоторых встроенных геометрических типов данных (см. src/backend/access/gist/gistproc.c
). Классы операторов GiST содержатся также и в следующих дополнительных модулях (contrib
):
btree_gist
Функциональность B-дерева для различных типов данных
cube
Индексирование для многомерных кубов
hstore
Модуль для хранения пар (ключ, значение)
intarray
RD-дерево для одномерных массивов значений int4
ltree
Индексирование древовидных структур
pg_trgm
Схожесть текста на основе статистики триграмм
seg
Индексирование «диапазонов чисел с плавающей точкой»