GiST - programming interface

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

Обновление:

Более подробное и актуальное описание доступно в нашей статье 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;

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

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

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

GISTENTRY *   compress( GISTENTRY * in ) 
GISTENTRY * decompress( GISTENTRY * in )

Эти функции отвечают за компрессию/декомпрессию ключей. Если функция меняет значение ключа (key), то:

она должна возвращать заново palloc'оченное значение как структуры так и ключа( в случае pass-by-reference типа ключа).
скопировать в новую структуру значения rel, page, offset, leafkey.
правильно установить bytes.
старую структуру (in) не трогать, и не делать pfree ни in ни in->key

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

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

  GISTENTRY *   compress( GISTENTRY * in ){
	return in;
  }

Всем остальным интерфейсным функциям ключи передаются только после обработки ключа функции decompress.

bool equal( Datum a, Datum b);

Возвращает TRUE только в случае a=b.

float * penalty( GISTENTRY *origentry, GISTENTRY *newentry, float *result)

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

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

Datum union(bytea *entryvec, int *size)

Выполняет объединение ключей. Возвращает объединенный ключ (не GISTENTRY!). В *size помещает размер результирующего ключа в байтах.
entryvec - это указатель на массив GISTENTRY.

  int len = (VARSIZE(entryvec) - VARHDRSZ)/sizeof(GISTENTRY); - размер массива
  GISTENTRY arr = (GISTENTRY *) VARDATA(entryvec); - собственно указатель на массив

Массив никогда не содержит NULL элементов.

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 и/или операций надо позаботиться об обновлении системных таблиц.

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.

1. Создать и подключить все интерфейсные функции с помощью create function .
2. Вставить в pg_opclass новый opclass. Примеры:
- 1) Ключ такого же типа как и индексируемые значения.
```
	INSERT INTO pg_opclass (opcamid, opcname, opcintype,opckeytype, opcdefault)
           SELECT pg_am.oid, 'gist_box_ops', pg_type.oid, 0, true
           FROM pg_type, pg_am
           WHERE pg_type.typname = 'box' and
           pg_am.amname='gist';
```
- 2) Тип ключа отличен от типа индексируемого значения
```
        INSERT INTO pg_opclass (opcamid, opcname, opcintype,opckeytype, opcdefault)
           SELECT pg_am.oid, 'gist_int4_ops', pg_type.oid, pg_key.oid, true
           FROM pg_type, pg_am, pg_type pg_key
           WHERE pg_type.typname = 'int4' and
           pg_key.typname = 'int4key' and 
           pg_am.amname='gist';
```
  Назначение полей в pg_opclass:
  opcamid - oid типа индекса( pg_am )
  opcname - название opclass'a
  opcintype - oid типа, для индексирования которого предназначен этот opclass
  opckeytype - тип ключа в индексе, если = 0, то принимается, что тип ключа совпадает с типом индексируемого значения
  opcdefault является ли этот opclass default'ом для типа opcintype для данного opcamid
3. Для удобства и с целью более компактного SQLя создать временную таблицу, содержащую oid операций для выбранного типа и их мнемоническое название:
```
	SELECT o.oid AS opoid, o.oprname
	INTO TABLE rt_ops_tmp
	FROM pg_operator o, pg_type t
	WHERE o.oprleft = t.oid
   	and t.typname = 'box';
```
4. Для каждой операции вставить запись в pg_amop. Поле amopstrategy должно коррелировать со значением strategy в функции split.
Пример:
```
   INSERT INTO pg_amop (amopclaid, amopopr, amopstrategy, amopreqcheck)
   SELECT opcl.oid, c.opoid, 1, false 
   FROM pg_am am, pg_opclass opcl, rt_ops_tmp c
   WHERE am.amname = 'gist' and am.oid = opcl.opcamid and 
	opcl.opcname = 'gist_box_ops' and c.oprname = '<<';
```
поле pg_amop.amopreqcheck должно быть true, если index hit must be reevaluated against heap value to make sure it really is match, иначе false

5. Сделать доступным для core GiSTa интерфейсные функции. Для этого надо внести записи в таблицу pg_amproc, причем поле pg_amproc.amprocnum должно иметь следующие значения:

   функция      |   значение
   -------------+-----------
   consistent   | 1
   union        | 2
   compress     | 3
   decompress   | 4
   penalty      | 5
   picksplit    | 6
   equal        | 7

Пример:

  INSERT INTO pg_amproc (amopclaid, amproc, amprocnum)
   SELECT am.oid, opcl.oid, pro.oid, 3
   FROM pg_am am, pg_opclass opcl, pg_proc pro
   WHERE  am.amname = 'gist' and am.oid = opcl.opcamid and 
	opcl.opcname = 'gist_box_ops' and pro.proname = 'gbox_compress';

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

1. Создать все интерфейсные функции с помощью create function .

2. Создать opclass с помощью команды:

CREATE OPERATOR CLASS gist_box_ops
     DEFAULT FOR TYPE box USING gist AS
         OPERATOR        1       << ,
         OPERATOR        2       &< ,
         OPERATOR        3       && ,
         OPERATOR        4       &> ,
         OPERATOR        5       >> ,
         OPERATOR        6       ~= ,
         OPERATOR        7       ~ ,
         OPERATOR        8       @ ,
         FUNCTION        1       gbox_consistent (opaque, box, int4),
         FUNCTION        2       gbox_union (bytea, opaque),
         FUNCTION        3       gbox_compress (opaque),
         FUNCTION        4       rtree_decompress (opaque),
         FUNCTION        5       gbox_penalty (opaque, opaque, opaque),
         FUNCTION        6       gbox_picksplit (opaque, opaque),
         FUNCTION        7       gbox_same (box, box, opaque);

замечания

1. Номер FUNCTION должен быть такой как здесь указано, по этому номеру core GiST идентифицирует интерфейсные ф-ции
2. Номер OPERATOR должен совпадать с strategy в методе consistent. Стратегия используется в consistent методе для определения типа операции.
3. Подробнее о CREATE OPERATOR CLASS см PostgreSQL 7.3devel Programmer's Guide, глава II. Server Programming, разделы 17.6, 17.7 и описание в PostgreSQL 7.3devel Reference Manual, глава I. SQL Commands, раздел CREATE OPERATOR CLASS