Описание интерфейсных функций

GiST home | Introduction | GiST interface (Russian) | Readings
Search PostgreSQL resources | OpenFTS | PostgreSQL site

Обновление:

Более подробное и актуальное описание доступно в нашей статье GiST programming tutorial

Общие замечания

Небольшое описание GiST можно прочитать в тезисах нашего доклада.

GiST предоставляет разработчикам новых типов данных основные методы для работы с ними: SEARCH, INSERT, DELETE. Управлять этими методами можно с помощью 7 интерфейсных функций, которые разработчик должен специфицировать.

Большинство функций интерфейса работают с ключами, передаваемыми в следующей структуре:

typedef struct GISTENTRY
{
        Datum           key;     /* собственно ключ */
        Relation        rel;     /* индекс */ 
        Page            page;    /* страница индекса */
        OffsetNumber    offset;  /* положение в индексе */
        int             bytes;   /* длина ключа в байтах, может быть равной -1  */
        bool            leafkey; /* признак, указывающий, что в key находится не
				 ключ, а значение из таблицы */
} GISTENTRY;

Общие замечания:
  1. Ни одна из интерфейсных функций не имеет права вернуть NULL
  2. Всем функциям, кроме penalty(см описание), никогда не передаются NULL или GISTENTRY с значением key NULL.

Интерфейсные функции

1.
GISTENTRY *   compress( GISTENTRY * in ) 
GISTENTRY * decompress( GISTENTRY * in )
Эти функции отвечают за компрессию/декомпрессию ключей. Если функция меняет значение ключа (key), то:
  1. она должна возвращать заново palloc'оченное значение как структуры так и ключа( в случае pass-by-reference типа ключа).
  2. скопировать в новую структуру значения rel, page, offset, leafkey.
  3. правильно установить bytes.
  4. старую структуру (in) не трогать, и не делать pfree ни in ни in->key

При вызове compress in->leafkey выставлена в true если значение в key взято из таблицы, а не из индекса. В этом случае, даже если не меняется ключ, обязательно надо проставить bytes и установить leafkey=FALSE.

В случае если compress/decompress не делает реальной работы, то они могут выглядеть следующим образом:

  GISTENTRY *   compress( GISTENTRY * in ){
	return in;
  }
Всем остальным интерфейсным функциям ключи передаются только после обработки ключа функции decompress.

2.

bool equal( Datum a, Datum b);
Возвращает TRUE только в случае a=b.

3.

float * penalty( GISTENTRY *origentry, GISTENTRY *newentry, float *result)
Вычисляет меру увеличения origentry->key при его объединении с newentry->key. Вычисленное значение должна поместить в *result и вернуть указатель на него.

Если эта функция не помечена как isstrict, то key может быть NULL. Иначе функция не вызывается и считается, что мера = 0 если хотя бы один из параметров is NULL

4.

Datum union(bytea *entryvec, int *size)
Выполняет объединение ключей. Возвращает объединенный ключ (не GISTENTRY!). В *size помещает размер результирующего ключа в байтах.
entryvec - это указатель на массив GISTENTRY.
  int len = (VARSIZE(entryvec) - VARHDRSZ)/sizeof(GISTENTRY); - размер массива
  GISTENTRY arr = (GISTENTRY *) VARDATA(entryvec); - собственно указатель на массив 
Массив никогда не содержит NULL элементов.

5.

bool consistent( Datum key, Datum query, StrategyNumber strategy )
Тестирует ключ (key) на соответствие запроса (query) операцией с номером strategy и возвращает TRUE в случае соответствия, иначе FALSE

Если ключ находится на внутренней странице дерева, функция должна возвращать TRUE если key МОЖЕТ соответствовать query (FALSE если key ТОЧНО не соответствует query).

Смутный параграф: Если ключ находится на концевой (leaf) странице, то все определяется параметром RECHECK для конкретной операции (см. CREATE OPERATOR CLASS). RECHECK - обязан вернуть точный ответ, нет - может.

Макрос GIST_LEAF(key) возвращает TRUE если ключ находится на leaf странице.

Узнать, какие операции какой strategy соответствуют можно с помощью следующего SQL( на примере gist_box_ops, подробнее смотри раздел подключения ):

  select
        pg_amop.amopstrategy,
        pg_operator.oprname,
        pg_amop.amopreqcheck
  from
        pg_type,
        pg_operator,
        pg_opclass,
        pg_am,
        pg_amop
  where
        pg_type.typname = 'box' and
        pg_am.amname = 'gist' and
        pg_opclass.opcname = 'gist_box_ops' and
	pg_am.oid=pg_opclass.opcamid and
        pg_opclass.oid = pg_amop.amopclaid and
        pg_opclass.opcintype = pg_type.oid and
        pg_amop.amopopr = pg_operator.oid;
Соответственно, при внесении нового opclass и/или операций надо позаботиться об обновлении системных таблиц.

6.

GIST_SPLITVEC * split(bytea *entryvec, GIST_SPLITVEC *v)
Разделяет массив ключей entryvec на два. Массив entryvec не может содержать NULL значения

Структура GIST_SPLITVEC:

  typedef struct GIST_SPLITVEC
  {
        OffsetNumber *spl_left;         /* array of entries that go left */
        int           spl_nleft;        /* size of this array */
        Datum         spl_ldatum;       /* Union of keys in spl_left */
        OffsetNumber *spl_right;        /* array of entries that go right */
        int           spl_nright;       /* size of the array */
        Datum         spl_rdatum;       /* Union of keys in spl_right */
	...        
  } GIST_SPLITVEC;
Структура содержит бОльшее количество полей, чем указано здесь, но остальные поля не должны ею трогаться.

v->spl_left & v->spl_right должны аллоцироваться самостоятельно, при возврате они должны содержать номера элементов массива entryvec (один номер НЕ может содержаться в spl_left и spl_right одновременно). Значения в массиве entryvec начинаются с 1, а не с 0!! Также функция обязана сформировать spl_ldatum & spl_rdatum.

Подключение интерфейсных функций ( version 7.2)

Пример для версии 7.3 смотри ниже

В качестве примера рассмотрим реализацию R-tree для типа box.

Подключение интерфейсных функций (version 7.3)