Написание расширений для PostgreSQL с использованием GiST

Авторы: Олег Бартунов и Фёдор Сигаев

Написание расширений для PostgreSQL с использованием GiST

Приводится краткое описание обобщенного поискового дерева (GiST), его реализация в ORDBMS PostgreSQL, пример написания пользовательских расширений с использованием GiST.

Введение

При построении современных информационных систем приходится решать разнообразные технологические задачи, связанные с хранением, доступом и поиском информации. Учитывая современные требования к производительности, надежности и шкалированию таких систем, такие задачи требуют использования достаточно сложных алгоритмов и специализированных структур данных (abstract data type, ADT).

Эффективный доступ к данным является одной из важнейшей задачей базы данных. Мы рассматриваем большие базы данных, которые не помещаются в оперативную память. Для таких БД эффективность доступа к данным определяется, в основном, количеством обращений к диску, поэтому основной задачей СУБД является минимизация этих обращений. Обычно, это достигается использованием индекса, который представляет собой вспомогательную структуру данных, предназначенную для ускорения получения данных удовлетворяющих определенным поисковым критериям. Индекс позволяет уменьшить количество дисковых операций необходимых для считывания данных с диска. Обычно, индекс представляет собой файл на диске, и, если этот файл становится очень большим, то может потребоваться дополнительный индекс для ускорения работы самого индекса. Методами доступа (access methods,AM), обычно, называют организацию (структуру) индексного файла и методы работы с ней. В традиционных реляционных СУБД для работы с одномерными данными, такими как строки, цифры, используются B+-tree и хэш, для которых разработаны очень эффективные алгоритмы работы. Однако, современные приложения, такие как ГИС (GIS), мультимедийные системы, CAD, цифровые библиотеки, которые по-сути используют многомерные данные, требуют других, более эффективных AM. Например, в ГИС основными типами данных являются точки, линии, полигоны. За последние годы было разработано десятки (около 70) различных специализированных AM, однако их реализация в серьезных СУБД связана с большими затратами из-за собственно программирования AM и обеспечения соответствующего уровня надежности, конкурентности, предоставляемых СУБД для обычных AM. Следует отметить, что для этого требуется работа очень квалифицированных программистов, знакомых с ядром СУБД, а также, тщательное и продолжительное тестирование.

Вместо написания новых AM для каждого нового типа данных, Майкл Стоунбрейкер [Sto86] предложил использовать существующие, хорошо изученные структуры, такие как B+-tree и R-tree. Эта идея нашла воплощение в СУБД Postgres, развиваемой в Беркли в 80-х годах (см. детали в [B05]). Идея Стоунбрейкера заключалась в повышении степени абстракции процедур доступа и обновления записей, которые и составляют АМ. Так, например, достаточно определить операторы сравнения, чтобы использовать B+-tree AM. На примере типа данных box Стоунбрейкер показал, как B+-tree можно использовать для операций AE (равенство), AL (меньше) и AG (больше). Однако, такой подход, несмотря на свои возможности, сильно ограничен, так как несмотря на тип данных, который хранится в B+-tree, нельзя использовать запросы кроме тех, которые предоставляет B+tree. Другими словами, этот подход поддерживал расширяемость типов, но не запросов и методов доступа.

Для того, чтобы преодолеть это ограничение, Hellerstein et al. [HNP95] предложили структуру индекса, называемую GiST ( Generalized Search Tree, Обобщенное поисковое дерево), которое является обобщенной разновидностью R-tree и предоставляет стандартные методы навигации по дереву и его обновления (расщепление и удаление узлов). Было отмечено, что очень многие AM можно представить как иерархию предикатов, в которой каждый предикат выполняется для всех ключей, содержащихся в подузлах этой иерархии. Таким образом, такая структура данных может служить шаблоном для реализации многих AM, не накладывая существенных ограничений. Например, в B+-tree записи во внутренних узлах представляют диапазоны, которые задают ограничения на ключи в концевых узлах соответствующего поддерева. GiST предоставляет индексный доступ к новым типам данным и поддерживает расширяемый набор запросов. Это позволяет разрабатывать расширения экспертам в области данных, не будучи экспертами-разработчиками ядра СУБД. Кроме этого, эти новые ADT автоматически наследуют конкурентный доступ и восстановление после краха (concurrency and recovery), реализация которых с нуля, является очень большой задачей, предоставленные ядром GiST.

Следует отметить, что первый рабочий прототип был реализован в СУБД Postgres Дж. Хеллерстейном и П. Аоки [GBK] и практические все коммерческие СУБД (IDS/UDO Virtual Index Interface, DB2 UDB table functions, Oracle Extensible Indexing Interface) тем или иным образом используют идеи и результаты этой исследовательской СУБД. Однако, в самом Postgres (PostgreSQL), GiST до 2000 года практически не развивался и не использовался. Более того, его реализация не поддерживала конкурентного доступа и восстановления после краха системы, что мешало его использования в промышленных системах.

Авторы этой статьи, при работе над порталом "Рамблер", начали использовать GiST и занялись исправлением ошибок и его улучшением. Так, авторы добавили поддержку ключей переменной длины, композитных ключей (multi-key), оптимизировали алгоритм вставки (однопроходный вместо рекурсивного). Кроме того, для версии 8.1 авторы добавили поддержку конкурентного доступа к GiST индексам и восстановление после краха системы, используя модифицированные алгоритмы из работы Корнакера и др. [KMH97], что окончательно сняло все ограничения, мешающие использование его в сильно нагруженных системах и работе с критическими данными. Отметим, что большое количество модулей, написанных на базе GiST, автоматически "приобрели" всю эту индустриальную мощь без какого-либо изменения !

GiST представляет собой сбалансированное (по высоте) дерево, концевые узлы (листья) которого содержат пары (key, rid), где key - ключ, а rid - указатель на соответствующую запись на странице данных. Внутренние узлы содержат пары (p,ptr), где p - это некий предикат (используется как поисковый ключ), выполняющийся для *всех* наследных узлов, а ptr - указатель на другой узел в дереве. Для этого дерева определены базовые методы SEARCH, INSERT, DELETE, и интерфейс для написания пользовательских методов, которыми можно управлять работой этих (базовых) методов.

Метод SEARCH управляется функцией Consistent, возвращающая 'true', если узел удовлетворяет предикату, метод INSERT - функциями penalty, picksplit и union, которые позволяют оценить сложность операции вставки в узел, разделить узел при переполнении и перестроить дерево при необходимости, метод DELETE находит лист дерева, содержащий ключ, удаляет пару (key, rid) и, если нужно, с помощью функции union перестраивает родительские узлы.

Программный интерфейс GiST

Для дальнейшего ознакомления полезно ознакомиться с некоторыми особенностями программирования функция для PostgreSQL на языке C, которые приведены в приложении.

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

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

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

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

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

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

Для упрощения описания в объявлениях функций используется псевдосинтаксис, реальные определения должны соответствовать принятым соглашениям. В последующей секции рассматривается пример реализации R-tree.

  1. GISTENTRY *   compress( GISTENTRY * IN )<br> 
    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 взято из таблицы, а не из индекса. В этом случае, если эта функция нетривиальна, даже если не меняется ключ, надо обязательно определить in->bytes и установить in->leafkey=FALSE.

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

  4.  Datum UNION(GistEntryVector *entryvec, int *size)

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

    typedef struct
    {  
            int32           n;          /* количество элементов в поле vector*/
            GISTENTRY       vector[1];
    } GistEntryVector;
    

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

  5.  bool consistent( GISTENTRY *entry, Datum query, StrategyNumber strategy )

    Проверяет ключ (entry->key) на соответствие запросу (query) с помощью операции с номером strategy и возвращает TRUE в случае соответствия, или FALSE в противном.

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

    Если ключ находится на концевой странице (leaf page), то поведение определяется параметром RECHECK для конкретной операции (см. CREATE OPERATOR CLASS). Если задан параметр RECHECK, то это означает, что индекс является неточным ("lossy"), т.е. результат поиска требуется проверить на соответствие запросу (поведение consistent аналогично поведению на внутренних страницах в этом случае), в противном случае требуется вернуть ТОЧНЫЙ ответ.

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

    Узнать, какие операции какой strategy соответствуют можно с помощью следующего SQL( на примере 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 = '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(GistEntryVector *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 должны аллоцироваться(palloc) самостоятельно, при возврате они должны содержать номера элементов массива entryvec. При этом, один номер НЕ может содержаться в spl_left и spl_right одновременно.

    Внимание:

    • Значения в массиве entryvec начинаются с 1, а не с 0
    • Функция обязана определить spl_ldatum и spl_rdatum - объединяющие ключи, соответственно, для левого и правого массива.

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

Процедура регистрации расширения в БД состоит из нескольких этапов (приводятся только SQL команды):
  1. Создание нового типа данных (если требуется)
    • Написание функций преобразования типа в C-строку и обратно: _in, _out. Например:
      CREATE FUNCTION ltree_in(cstring)
      RETURNS ltree
      AS '$libdir/ltree'
      LANGUAGE 'C' WITH (isstrict);
      
    • Создание типа с помощью CREATE TYPE.
      CREATE TYPE ltree (
              INTERNALLENGTH = -1,
              INPUT = ltree_in,
              OUTPUT = ltree_out,
              STORAGE = extended
      );
      
  2. Создание новых операторов (если требуется)
    • Создание функций (CREATE FUNCTION) для работы операторов, например, функции сравнения типов для операторов сравнения. Например,
      CREATE FUNCTION ltree_eq(ltree,ltree)
      RETURNS bool
      AS '$libdir/ltree'
      LANGUAGE 'C' WITH (isstrict,iscachable);
      
    • Создание операторов с помощью CREATE OPERATOR. При этом задается соответствие знаков операторов, используемые в SQL, с вызываемыми функциями.
      CREATE OPERATOR = (
              LEFTARG = ltree,
              RIGHTARG = ltree,
              PROCEDURE = ltree_eq,
              COMMUTATOR = '=',
              NEGATOR = '<>',
              RESTRICT = eqsel,
              JOIN = eqjoinsel,
              SORT1 = '<',
              SORT2 = '<'
      );
      
  3. Регистрация интерфейсных функций GiST
    • Создать новый тип для хранения в GiST, если необходимо (это может потребоваться если тип ключа хранимый в дереве отличается от исходного типа данных, например, в модуле tsearch2 базовым типом является tsvector, а для хранения используется тип gtsvector, представляющий сигнатуру документа. В этом случае, для отладки с помощью модуля gevel необходимо написать функцию _out.
    • Создать интерфейсные функции GiST. Например, для метода consistent:
      CREATE FUNCTION ltree_consistent(internal,internal,int2)
      RETURNS bool as '$libdir/ltree' language 'C';
      
    • Создать новый оператор класс (opclass), см. CREATE OPERATOR CLASS, например, для типа данных box:
      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 (internal, box, int4),
               FUNCTION        2       gbox_union (internal, internal),
               FUNCTION        3       gbox_compress (internal),
               FUNCTION        4       rtree_decompress (internal),
               FUNCTION        5       gbox_penalty (internal, internal, internal),
               FUNCTION        6       gbox_picksplit (internal, internal),
               FUNCTION        7       gbox_same (box, box, internal);
      
      
      Здесь, номер FUNCTION используется в core GiST для идентификации интерфейсных функций. Номер OPERATOR должен совпадать с номером strategy в методе consistent, который используется для определения типа операции. Другими словами, стратегия - это уникальный номер оператора для данного opclass-а.
Полный пример можно посмотреть в ltree.sql из модуля ltree, который находится в поддиректории contrib в дистрибутиве PostgreSQL. Также, смотри раздел документации Interfacing Extensions To Indexes.

Пример: R-Tree GiST для прямоугольников

Для описания сложных объектов часто используют более простые фигуры, аппроксимирующие сложную форму, которые характерны тем, что полностью содержат в себе эти объекты. Такие фигуры называют bounding volume и их гораздо проще использовать для проверки на различные условия, например, на пересечение двух объектов. В качестве bounding volume часто используют сферу, цилиндр или куб. Мы будем рассматривать куб, который называют bounding box,или BB.

R-Tree - это структура данных, которая используется для индексирования многомерных данных. Она была предложена Гуттманом [Gut84] как расширение B-tree на многомерное пространство, которое разбивается на иерархически вложенные и возможно перекрывающиеся BB (прямоугольники для двумерного случая, в случае 3-х измерений - кубики), Каждый узел R-Tree может содержать переменное количество записей, но не больше заранее определенного максимума. Каждая запись во внутренних узлах содержит ссылку на дочерний узел и BB, который содержит все записи этого дочернего узла. Каждая запись концевого узла (leaf node) содержит ссылку на данные и BB этих данных. При вставке новых данных отслеживается, чтобы близкие данные лежали "близко", в одном концевом узле, в частности, это достигается с помощью правила наименьшего увеличения BB этого узла после вставки. При поиске сравниваются BB-ы запроса и текущего узла и если нет пересечений, то последующие проверки с узлами этого поддерева уже не нужны, чем сильно уменьшается количество просмотренных узлов и достигается выигрыш в производительности.

MBR of Greece cities (fragment)

R-tree для для городов и деревень Греции. Данные взяты с rtreeportal.org

На рисунке изображен фрагмент дерева (полное дерево), построенного с помощью модуля rtree_gist и gevel - специального модуля, предназначенного для разработчиков расширений с использованием GiST. Исходными данными являются MBR (minimum bounding rectangles) городов и деревень Греции. Изображены данные на концевых узлах (маленькие прямоугольники) и на 1-м уровне (большие прямоугольники). Подробнее можно прочитать здесь.
compress, decompress
Функции тривиальны, просто возвращают то, что получили.
Datum
gist_box_compress(PG_FUNCTION_ARGS) {                       
        PG_RETURN_POINTER(PG_GETARG_POINTER(0));
}

Datum
gist_box_decompress(PG_FUNCTION_ARGS) {
        PG_RETURN_POINTER(PG_GETARG_POINTER(0));
}
<b>equal</b>
Сравнивает два прямоугольника и возвращает true если они равны или оба равны NULL
Datum
gist_box_same(PG_FUNCTION_ARGS) {
        BOX                *b1 = PG_GETARG_BOX_P(0);
        BOX                *b2 = PG_GETARG_BOX_P(1);
        bool       *result = (bool *) PG_GETARG_POINTER(2);

        if (b1 && b2)
                *result = DatumGetBool(DirectFunctionCall2(box_same,
                                  PointerGetDatum(b1),
                                  PointerGetDatum(b2)));
        else
                *result = (b1 == NULL && b2 == NULL) ? TRUE : FALSE;
        PG_RETURN_POINTER(result);
}
Кстати, тут присутствует вызов встроенной в PostgreSQL функции box_same. Следует также обратить внимание на работу с переменной result: эта интерфейсная функция является исключением из правил и функция должна изменить значения своего параметра. Но это не касается двух первых аргументов.
<b>penalty</b>
Функция возвращает изменение (увеличение) площади прямоугольника после объединения обоих (получение bounding box) как меру изменения.
static double
size_box(Datum dbox) { /* Вычисление площади прямоугольника */  
        BOX        *box = DatumGetBoxP(dbox);

        if (box == NULL || box->high.x <= box->low.x || box->high.y <= box->low.y)
                return 0.0;
        return (box->high.x - box->low.x) * (box->high.y - box->low.y);
}

Datum
gist_box_penalty(PG_FUNCTION_ARGS) {
	/* исходный прямоугольник */
        GISTENTRY  *origentry = (GISTENTRY *) PG_GETARG_POINTER(0);
	/* добавляемый прямоугольник */
        GISTENTRY  *newentry = (GISTENTRY *) PG_GETARG_POINTER(1);
        float      *result = (float *) PG_GETARG_POINTER(2);
        Datum           ud;

	/* получаем объединяющий прямоугольник */
        ud = DirectFunctionCall2(rt_box_union, origentry->key, newentry->key);
	/* вычитаем площадь исходниго из полученного прямоугольника */	
        *result = (float) (size_box(ud) - size_box(origentry->key));

        PG_RETURN_POINTER(result);
} 
<b>union</b>
Функция возвращает объединяющий прямоугольник для всех входящих прямоугольников
Datum
gist_box_union(PG_FUNCTION_ARGS) {
        GistEntryVector *entryvec = (GistEntryVector *) PG_GETARG_POINTER(0);
        int                *sizep = (int *) PG_GETARG_POINTER(1);
        int                     numranges,
                                i;
        BOX                *cur,
                           *pageunion;

        numranges = entryvec->n;
	/* возвращаемое значение должно быть palloc'ировано! */	
        pageunion = (BOX *) palloc(sizeof(BOX));
	/* инициация объединяющего прямоугольника первым прямоугольником */
        cur = DatumGetBoxP(entryvec->vector[0].key);
        memcpy((void *) pageunion, (void *) cur, sizeof(BOX));

        for (i = 1; i < numranges; i++)
        {
                cur = DatumGetBoxP(entryvec->vector[i].key);
                if (pageunion->high.x < cur->high.x)
                        pageunion->high.x = cur->high.x;
                if (pageunion->low.x > cur->low.x)
                        pageunion->low.x = cur->low.x;
                if (pageunion->high.y < cur->high.y)
                        pageunion->high.y = cur->high.y;
                if (pageunion->low.y > cur->low.y)
                        pageunion->low.y = cur->low.y;
        }

	/* размер возвращаемого значения в байтах */
        *sizep = sizeof(BOX);

        PG_RETURN_POINTER(pageunion);
}

<b>consistent</b>
Datum
gist_box_consistent(PG_FUNCTION_ARGS)
{
        GISTENTRY  *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
        BOX                *query = PG_GETARG_BOX_P(1);
        StrategyNumber strategy = (StrategyNumber) PG_GETARG_UINT16(2);

        if (DatumGetBoxP(entry->key) == NULL || query == NULL)
                PG_RETURN_BOOL(FALSE);
 
	/* если значение находится на концевой странице, то выполняется точное сравнение,
           на внутренней мы должны вернуть true если значения на последующих 
           страницах (детях) МОГУТ удовлетворять условию */ 
        if (GIST_LEAF(entry))
                PG_RETURN_BOOL(gist_box_leaf_consistent(DatumGetBoxP(entry->key),
                                    query,
                                    strategy));
        else
                PG_RETURN_BOOL(rtree_internal_consistent(DatumGetBoxP(entry->key),
                                    query,
                                    strategy));
}
Реальные функции gist_box_leaf_consistent и rtree_internal_consistent довольно объемны, ограничимся их вариантами только для поиска на совпадение.
static bool
gist_box_leaf_consistent(BOX *key, BOX *query, StrategyNumber strategy) {
        bool            retval = FALSE;
        switch (strategy) {
                case RTSameStrategyNumber:
                        retval = DatumGetBool(DirectFunctionCall2(box_same,
                                                                  PointerGetDatum(key),
                                                                  PointerGetDatum(query)));
			break;
		default:
			elog(NOTICE,"Unsupported StrategyNumber %d", strategy);
	}
	return retval;
}

static bool
rtree_internal_consistent(BOX *key, BOX *query, StrategyNumber strategy) {
	bool            retval=FALSE;
	switch (strategy) {
                case RTSameStrategyNumber:
                        retval = DatumGetBool(DirectFunctionCall2(box_contain,
                                                                  PointerGetDatum(key),
                                                                  PointerGetDatum(query)));
                        break;
		default:
			elog(NOTICE,"Unsupported StrategyNumber %d", strategy);
	}
	return retval;
}
Обратите внимание, что в функции gist_box_leaf_consistent поисковый прямоугольник тестируется на полное совпадение с испытуемым значением, а в rtree_internal_consistent поисковый прямоугольник должен полностью содержаться в испытуемом значении. Очевидно, что если поисковый прямоугольник не содержится, то совпадающих с ним прямоугольников в страница-наследниках просто не может быть.
<b>picksplit</b>
Обычно самая сложная функция в интерфейсе GiST. Полную версию можно найти в исходниках PostgreSQL, файл ./src/backend/access/gist/gistproc.c Можно использовать обычный Гуттмановский (квадратичный) алгоритм ([Gut84]). Для полноты мы будем использовать простой (неэффективный) алгоритм, который помещает четные элементы в "левый" массив, в нечетный - в "правый".
Datum
gist_box_picksplit(PG_FUNCTION_ARGS) {
        GistEntryVector *entryvec = (GistEntryVector *) PG_GETARG_POINTER(0);
        GIST_SPLITVEC *v = (GIST_SPLITVEC *) PG_GETARG_POINTER(1);
	OffsetNumber	i, maxoff = entryvec->n - 1;
	int	nbytes;

	nbytes = (maxoff + 2) * sizeof(OffsetNumber);
	v->spl_left = (OffsetNumber *) palloc(nbytes);
	v->spl_right = (OffsetNumber *) palloc(nbytes);
	v->spl_ldatum = PointerGetDatum( palloc( sizeof(BOX) ) );
	v->spl_rdatum = PointerGetDatum( palloc( sizeof(BOX) ) );
	v->spl_nleft = 0;
	v->spl_nright = 0;

	for (i = FirstOffsetNumber; i <= maxoff; i = OffsetNumberNext(i)) {
		BOX	*pageunion; /* указатель на объединяющий прямоугольник для страницы */

		if ( i%2 == 0 ) {
			v->spl_left[ v->spl_nleft ] = i;
			v->spl_nleft++;
			pageunion = DatumGetBoxP( v->spl_ldatum );
		} else {
			v->spl_right[ v->spl_nright ] = i;
			v->spl_nright++;
			pageunion = DatumGetBoxP( v->spl_rdatum );
		}

		if ( i<=OffsetNumberNext( FirstOffsetNumber ) ) {
			/* первоначальная инициализация объединяющего прямоугольника */
			memcpy( pageunion, DatumGetBoxP(entryvec->vector[i].key), sizeof(BOX) );
		} else {
                	BOX *curbox = DatumGetBoxP(entryvec->vector[i].key);
                	if (pageunion->high.x < curbox->high.x)
                	        pageunion->high.x = curbox->high.x;
                	if (pageunion->low.x > curbox->low.x)
                	        pageunion->low.x = curbox->low.x;
                	if (pageunion->high.y < curbox->high.y)
                	        pageunion->high.y = curbox->high.y;
                	if (pageunion->low.y > curbox->low.y)
                	        pageunion->low.y = curbox->low.y;
		}
	}

	PG_RETURN_POINTER(v);
}


Пример: R-Tree GiST для полигонов

Хранимыми ключами для полигонов являются также прямоугольники, описывающие полигоны. Таким образом, все отличия от варианта R-Tree для прямоугольников заключаются всего в двух функциях. Такой индекс называют "with lossy compression" (неточный индекс) и это означает, что все данные, которые он выдает при поиске, необходимо проверить, т.е., сравнить с исходным значением, хранящимся в таблице.

<b>compress</b>
Datum
gist_poly_compress(PG_FUNCTION_ARGS) {
        GISTENTRY  *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
        GISTENTRY  *retval;

        if (entry->leafkey) {
		/* значение entry->key содержит полигон, т.е.
		   это новое значение для вставки в индекс */
                retval = palloc(sizeof(GISTENTRY));
                if (DatumGetPointer(entry->key) != NULL) {
                        POLYGON    *in = DatumGetPolygonP(entry->key);
                        BOX                *r;

                        r = (BOX *) palloc(sizeof(BOX));
                        memcpy((void *) r, (void *) &(in->boundbox), sizeof(BOX));
                        gistentryinit(*retval, PointerGetDatum(r),
                                                  entry->rel, entry->page,
                                                  entry->offset, sizeof(BOX), FALSE);

                } else {
                        gistentryinit(*retval, (Datum) 0,
                                                  entry->rel, entry->page,
                                                  entry->offset, 0, FALSE);
                }
        } else
                retval = entry;
        PG_RETURN_POINTER(retval);
}
<b>consistent</b>
Обратите внимание, что всегда вызывается rtree_internal_consistent, даже для конечных страниц. Т.е. функция возвращает TRUE когда настоящее, точное сравнение МОЖЕТ быть истинно.
Datum
gist_poly_consistent(PG_FUNCTION_ARGS) {
        GISTENTRY  *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
        POLYGON    *query = PG_GETARG_POLYGON_P(1);
        StrategyNumber strategy = (StrategyNumber) PG_GETARG_UINT16(2);
        bool            result;

        if (DatumGetBoxP(entry->key) == NULL || query == NULL)
                PG_RETURN_BOOL(FALSE);
                                
        result = rtree_internal_consistent(DatumGetBoxP(entry->key),
                                           &(query->boundbox), strategy);
                        
        PG_FREE_IF_COPY(query, 1);
         
        PG_RETURN_BOOL(result);
}

Примеры использования GiST

Для того, чтобы использовать модуль в вашей БД, необходимо установить модуль, загрузить расширение в вашу БД. Установка модуля обычно заключается в последовательности команд (на примере tsearch2):

cd contrib/tsearch2
make && make install && make installcheck

Если все прошло нормально (все тесты прошли), то можно загрузить расширение в вашу БД, например:
psql foodb < /usr/local/pgsql/share/contrib/tsearch2.sql
После этого вы можете использовать новые типы данных, предоставляемые модулем, операции, указанные в CREATE OPERATOR CLASS и функции. Например, для модуля tsearch2:
create table fts ( id integer, title text, body text, ftsindex tsvector);
create index fts_idx on fts using gist(ftsindex);
Здесь колонка ftsindex в таблице fts имеет тип tsvector, который и был предоставлен модулем tsearch2. Обратите внимание на указание метода (gist), который используется при построении индекса. Иногда, можно указать параметр opclass для метода, если требуется использовать оператор отличный от умолчания для данного типа колонки. Например, для модуля contrib/intarray можно указать opclass gist__intbig_ops для эффективной работы с большими массивами, в то время как по умолчанию используется gist__int_ops, достаточный для работы с небольшими массивами. Разница между gist__intbig_ops и gist__int_ops заключается в том, что первый opclass использует специальное представление массива битовой сигнатурой ( superimposed signature ) длиной 4096 бит и поэтому индекс является "lossy", в то время как во втором случае индекс является точным и не требует проверки найденных записей на соответствие запросу.
-- default opclass, could be omitted
CREATE INDEX message_rdtree_idx on message using gist ( sections gist__int_ops);
-- opclass for large arrays 
CREATE INDEX message_rdtree_idx on message using gist ( sections gist__intbig_ops);
Более подробно см. документацию CREATE INDEX

Используя GiST, авторами были разработаны ряд популярных расширений, которые входят в дистрибутив PostgreSQL. Все модули реализуют типы данных, оптимизированных под конкретную задачу, хранилище, индексный доступ к нему и специализированные запросы. Ниже приводится очень краткий обзор использования этих расширений. Формальное описание содержится в документации к модулю, а примеры использования можно найти в архивах списков рассылок PostgreSQL и c помощью поисковой машины www.pgsql.ru.

tsearch2 - реализация полнотекстового поиска

Этот модуль предназначен для организации полнотекстового поиска в БД. Его отличительной особенностью является online-индекс и полная интеграция с БД, что дает возможность проводить полнотекстовый поиск с ограничениями по атрибутам. Например, искать по документам, в зависимости от уровня доступа клиента и дате публикации. Tsearch2 поддерживает использование словарей, предоставляет API для их создания. Поддержка словарей популярных форматов ispell (для приведения слов к их нормальной форме) и стемминга на основе snowball позволяет использовать tsearch2 со многими языками. Гибкость настройки tsearch2, конфигурация которого хранится в базе данных и доступна с помощью стандартных команд SQL, позволяет разрабатывать различные поиски ориентированные на разные задачи. Модуль предоставляет два вида ранжирующих функций, использующие координатную информацию, и которые можно использовать для сортировки результатов поиска по их релевантности запросу.

С модулем tsearch2 полнотекстовый поиск становится простой и рутинной задачей. Пример поиска документов, которые содержат слова 'собака', 'на', 'сене':

SELECT mid, title from messages where 
		ftsindex @@ to_tsquery('собака & на & сене');
Аналогично, но ищутся 10 самых релевантных запросу документов:
SELECT mid, title, rank(ftsindex,to_tsquery('собака & на & сене')) as rank
	from messages where 
	ftsindex @@ to_tsquery('собака & на & сене')
	ORDER BY rank DESC LIMIT 10;

Модуль поддерживает структурность документа, т.е. словам из разных частей документа (всего можно использовать 4 части) можно задавать разные веса. Так, например, вес слова, входящего в название документа, можно увеличить, по сравнению с другими частями. Также, можно ограничивать поиск по различным частям документов, используя один и тот же индекс. В примере ниже, поле ftsindex включает поле title и тело документа.

UPDATE messages SET ftsindex=setweight( to_tsvector(title), 'A' ) || 
					to_tsvector(body);
Можно поискать только по названиям документов:
SELECT mid, title FROM messages WHERE 
	ftsindex @@ to_tsquery('собака:a & на & сене');

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

SELECT mid, headline(body, to_tsquery('собака & на & сене')),
   rank(fts_index,to_tsquery('собака & на & сене')) AS rank  
FROM messages
WHERE ftsindex @@ to_tsquery('собака & на & сене') 
ORDER BY rank DESC LIMIT 10;

Отметим, что в этом запросе, функция headline вызывается для каждого найденного документа, что может существенно влиять на время исполнения запроса. Это связано с тем как в PostgreSQL реализован LIMIT. Оптимизированный запрос с использованием подзапроса (subselect) выглядит следующим образом:
SELECT mid, headline(body, to_tsquery('собака & на & сене')) FROM
(SELECT mid, body, rank(fts_index,to_tsquery('собака & на & сене')) AS rank  
FROM messages
WHERE 
ftsindex @@ to_tsquery('собака & на & сене') 
ORDER BY rank DESC LIMIT 10) AS foo;
Здесь функция headline вызывается только нужное (максимум 10) количество раз.

ltree - поддержка данных с древовидной структурой

Стандартный способ работы с иерархическими данными, например, с каталогами, заключается в использовании таблиц связей (parent_id,child_id), что приводит ,так или иначе, к необходимости использования рекурсивных запросов. Идея модуля ltree состоит в том, чтобы хранить иерархию связей в специальном типе данных ltree и предоставлять индексную поддержку для основных операций. Например, для данных изображенных на рисунке

                            TOP
                         /   |  \     
                 Science Hobbies Collections  
                     /       |              \
            Astronomy   Amateurs_Astronomy Pictures
               /  \                            |
    Astrophysics  Cosmology                Astronomy
                                            /  |    \
                                     Galaxies Stars Astronauts

запрос на поиска всех потомков, например, узла 'Top.Science' выглядит:
SELECT path FROM test WHERE path <@ 'Top.Science';
                path                
------------------------------------
 Top.Science
 Top.Science.Astronomy
 Top.Science.Astronomy.Astrophysics
 Top.Science.Astronomy.Cosmology
Кроме работы со связями, ltree предоставляет возможность поиска с использованием регулярных выражений и модификаторов. Например, запрос
                Top.*{0,2}.sport*@.!football|tennis.Russ*|Spain
                a)  b)     c)      d)               e)
                                
означает, что узел должен:
  • a) - начинаться с узла с меткой 'Top'
  • b) - дальше могут идти вплоть до 2-х узлов с произвольной меткой
  • c) - после чего идет узел с именем начинающимся на 'sport' (маленькие и большие буквы не различаются)
  • d) - далее идет узел, имя которого не должно содержать 'footbal' или 'tennis'
  • e) - и кончаться на узел, начинающийся 'Russ' или 'Spain' (маленькие и большие буквы отличаются)
Пример:
SELECT path FROM test WHERE path ~ '*.!pictures@.*.Astronomy.*';
                path                
------------------------------------
 Top.Science.Astronomy
 Top.Science.Astronomy.Astrophysics
 Top.Science.Astronomy.Cosmology
Также, можно использовать поиск по названиям узлов, например, найти все узлы, которые содержать слово 'Europe', слово, начинающееся с 'Russia' (case insensitive), и не содержащее слово 'Transportation':
'Europe &  Russia*@ & !Transportation'
Пример:
SELECT path FROM test WHERE path @ 'Astro*% & !pictures@';
                path                
------------------------------------
 Top.Science.Astronomy
 Top.Science.Astronomy.Astrophysics
 Top.Science.Astronomy.Cosmology
 Top.Hobbies.Amateurs_Astronomy

Удобство использования этого модуля и большое количество полезных функций делает ltree очень полезным для решения типичных портальных задач.

intarray - индексная поддержка целочисленных массивов

Этот модуль часто используется в тех случаях, когда требуется денормализовать БД для повышения производительности. Например, типичная задача поиска документов из нескольких разделов. Классическая нормализованная схема предусматривает использование трех таблиц - messages, sections и message_section_map. Документ может принадлежать нескольким секциям, так что таблица message_section_map содержит связи многие-ко-многим. При этом, поиск всех документов из секций 1,2 будет содержать связку (join) двух таблиц messages и message_section_map, что влияет на производительность и в некоторых случаях просто неприемлемо. Денормализация приводит к тому, что в таблицу messages добавляется поле sections которое является массивом целых чисел - идентификаторов секций, к которым принадлежит данный документ. Однако, несмотря на то, что теперь не требуется вторая таблица, поиск будет все равно медленным из-за того, что операция поиск в массиве не использует индекс. Наш модуль intarray как раз и решает эту проблему - он обеспечивает индексную поддержку для операций над целочисленными массивами.

CREATE TABLE message (mid int not null,sections int[]);
-- select some messages with section in 1 OR 2 - OVERLAP operator
SELECT message.mid FROM messages WHERE messages.sections && '{1,2}';  
    
-- select messages contains in sections 1 AND 2 - CONTAINS operator
SELECT message.mid FROM messages WHERE messages.sections @ '{1,2}';
-- the same, CONTAINED operator
SELECT message.mid FROM messages WHERE '{1,2}' ~ messages.sections;
Другой интересный пример использования массивов - это реализация генеалогического подхода для работы с древовидной структурой, т.е. для каждого узла хранить путь от него до корня дерева (пример сообщил Achilleus Mantzios).
CREATE TABLE tree(
	id integer PRIMARY KEY,
	name text not null,
	parents integer[]
)
CREATE INDEX tree_parents on tree using gist (parents gist__int_ops);
INSERT INTO tree  VALUES (1,'root',null);
INSERT INTO tree  VALUES (2,'kid1',intset(1));
INSERT INTO tree  VALUES (3,'kid2',intset(1));
INSERT INTO tree  VALUES (4,'kid1.1',intset(2)+'{1}'::int4[]);
INSERT INTO tree  VALUES (5,'kid1.2',intset(2)+'{1}'::int4[]);
Здесь функция intset преобразует integer в элемент массива, а оператор '+' соединяет два массива. Теперь мы имеем дерево следующего вида:
			(1,root,null)
			/          \
		       /            \
		      /		     \
		    (2,kid1,'{1}')   (3,kid2,'{1}')
		    /	\
		   /	 \
		  /       \
   (4,kid1.1,'{2,1}')	(5,kid1.2,'{2,1}')
Теперь мы можем найти прямых потомков узла id=1 (root)
SELECT * FROM tree WHERE intset(1) ~ parents and icount(parents)=1;

Функция icount дает количество элементов в массиве или "глубину" узла в нашем примере. Чтобы найти всех потомков узла id:
SELECT * FROM tree WHERE intset() ~ parents;

pg_trgm - поиск похожих строк на основе триграм
Этот модель не только позволяет быстро находить похожие строки, но еще и не зависит от языка, так как использует только статистику используемых триграмм. Триграмма - это последовательность из трех соседних букв. Например, слово 'собака' содержит триграммы 'соб', 'оба', 'бак', 'ака'. Используя pg_trgm, можно найти все слова, упорядоченные по похожести слову 'собака':

CREATE INDEX trgm_idx ON foo USING gist (word gist_trgm_ops);
        
SELECT word, similarity(word, 'собака') AS sml FROM foo 
      WHERE word % 'собака' 
      ORDER BY sml DESC, word;
При этом, будет использоваться индекс trgm_idx, построенный по полю word, что обеспечивает хорошую производительность даже для большого количества слов.

Этот модуль можно использовать вместе с tsearch2 для полнотекстового поиска с коррекцией ошибок ввода.

rtree_gist - реализация R-tree с использованием GiST

Этот модуль позволяет эффективно работать с данными с пространственными атрибутами. Начиная с 8.1 этот модуль интегрирован в ядро PostgreSQL.

btree_gist - реализация B-tree с использованием GiST

Модуль поддерживает практические все основные типы данных, используемые в PostgreSQL и самостоятельной ценности не имеет, так как встроенный btree гораздо лучше. btree_gist применяется для создания композитных индексов, так как PostgreSQL не поддерживает композитные индексы, созданные с разными AM, например, gist и btree. Типичным примером использования является создание индекса по (ftsindex, ts), где ftsindex - колонка типа tsvector, а ts - timestamp. Такой индекс можно использовать не только для обычного полнотекстового поиска, но и для его ускорения поиска в определенном временном интервале.

CREATE INDEX fts_ts_idx ON foo USING gist(ftsindex,ts);
Здесь, по полю ts будет автоматически использоваться методы модуля btree_gist, а не btree.

gevel - набор функций для изучения GiST индекса

Этот модуль предназначен в первую очередь для разработчиков расширений с использованием GiST. Мы будем использовать модуль rtree_gist и данные, которые использовались для получения этой картинки. в виде:

create table cities (id int4, b box);
\copy cities from 'cities_mbr.copy' with delimiter as '|'
rtree=# \d bix
Index "public.bix"
 Column | Type 
 --------+------
  b      | box
  gist, for table "public.cities"
Показать статистику об индексе:
rtree=# select gist_stat('bix');
 Number of levels:          2
 Number of pages:           64
 Number of leaf pages:      63
 Number of tuples:          6782
 Number of leaf tuples:     6719
 Total size of tuples:      298408 bytes
 Total size of leaf tuples: 295636 bytes
 Total size of index:       524288 bytes
Вывести информацию о дереве, вплоть до уровня MAXLEVEL -
gist_tree(INDEXNAME,MAXLEVEL)</a>
<pre>
regression=# select gist_tree('pix',0);
 0(l:0) blk: 0 numTuple: 29 free: 6888b(15.63%)
</pre>
Здесь  (слева направо):
<ul  style="list-style-type:none">
     <li> 0 - page number
     <li> (l:0) - tree level
     <li> blk: 0 - block number
     <li> numTuple: 29 - the number of tuples
     <li> free: 6888b - free space IN bytes
     <li> (15.63%) - occupied space IN percents
 
</ul>
Для визуализации дерева (смотри <a href="#rtreepic">рисунок</a>) можно использовать
функцию <code>gist_print(INDEXNAME)
. Например, для визуализации разбиения на уровне 1, мы направляем вывод в файл:
\pset tuples_only
\o cities-l-1.leaf
-- для версии PostgreSQL < 8.1
SELECT * FROM gist_print('bix') AS t(level int, a box) WHERE level = 1;
-- для версии PostgreSQL начиная с 8.1
SELECT * FROM gist_print('bix') AS t(level int, valid bool, a box) 
	WHERE level =1;
Обратите внимание на разницу в запросах ! Аналогично, можно получить данные для концевых узлов (уровень 2). Полученные данные использовались для получения рисунка дерева.

Внимание: Функция gist_print(INDEXNAME) можно использовать только для объектов в индексе, которые имеют текстовое представление. Для этого необходимо написать функцию type_out для рассматриваемого типа объекта, например, tsvector_out для полнотекстового типа tsvector из модуля tsearch2. Функция box_out определена в ./backend/utils/adt/geo_ops.c и для полноты приведем ее здесь:

/* box_out - convert a box to external form */
 Datum
 box_out(PG_FUNCTION_ARGS)
 {
         BOX  *box = PG_GETARG_BOX_P(0);
         PG_RETURN_CSTRING(path_encode(-1, 2, &(box->high)));
 }
                 

Полный список расширений и документацию можно прочитать на странице разработчиков GiST.

Ограничения и TODO

Несмотря на значительный прогресс в развитии GiST, существуют некоторые ограничения в текущей реализации (в основном, не критические), которые мы планируем в будущем снять.
  • Хранение NULL - существенно только для кластеризации данных.
    Существующий интерфейс GiST запрещает использование NULL, так как пока непонятно, каким образом эффективно помечать эти значения.
  • Поддержка уникальных индексов
  • Поддержка упорядоченных данных (ordered domains) - использование знания о порядке для оптимизации хранения данных и улучшения производительности.

Кроме того, оригинальный интерфейс GiST [HNP95] требует модификаций, см. работы Корнакер [Kor99] и Аоки [Aok98], необходимые как для поддержки более широкого класса данных и запросов, так и для повышения производительности поискового дерева. Например, оригинальный алгоритм поиска в GiST использует стратегию поиска в глубину (depth-first), что неявно предполагает использование запросов вида "содержит", "пересекается", но не поддерживает запросы вида "похожий", как подметил Аоки [Aok98], который и предложил расширение GiST для поддержки пользовательской стратегии поиска, например, поиска в ширину (breadth-first) для SS-tree (similarity tree), которое используется в задачах кластеризации данных.

Следует отметить SP-GiST - расширение GiST интерфейса для поддержки специального вида деревьев, используемых в GIS, CAD/CAM, цифровых деревьев (tries). Mohamed Eltabakh работает над реализацией SP-GiST в виде модуля для PostgreSQL.

Несмотря на то, что изменение интерфейса GiST является "трудной" операцией, необходимо изучить все варианты и выделить оптимальное подмножество изменений, которое позволит с одной стороны улучшить "расширяемость" и производительность GiST, а с другой - сохранить простоту разработки расширений ([Kor99], например, предлагает использовать 11 интерфейсных функций, а [Aok98] - 13, вместо 7).

Для упрощения написания новых расширений мы планируем добавить некоторые методы в core GiST, которые можно использовать по умолчанию:

  • picksplit, реализующий Гуттмановский алгоритм. Практика показала, что во многих случаях этот алгоритм показывает удовлетворительные результаты.
  • R-tree интерфейс для GiST может быть полезен для быстрого создания opclass'ов подобных 2-D R-tree: индексы для n-размерных объектов, некоторые виды индексирования массивов (см. обсуждение).

Заключение

Возможность разработки пользовательских расширений, которые оптимизированы для конкретной задачи, является неотъемлемой составляющей любой современной ORDBMS.

Обобщенное поисковое дерево (GiST), которое входит в ядро PostgreSQL, дает возможность специалистам в конкретной области знаний создавать специализированные типы данных и обеспечивает индексный доступ к ним не будучи экспертами в области баз данных. При этом, пользовательские расширения будут отвечать всем требованиям безопасности данных, накладываемых на ORDMBS, и поддерживать конкурентный доступ к данным.

Благодарности

Авторы благодарят Российский Фонд Фундаментальных Исследований (РФФИ) за поддержку грантов 03-07-90187-в, 05-07-90225-в и компанию Дельта-Софт за многолетнюю поддержку наших работ по PostgreSQL.

Ссылки

  • www.postgresql.org - сервер проекта PostgreSQL
  • [B05] Олег Бартунов, Что такое PostgreSQL? - обзорная статья (на русском) о PostgreSQL
  • www.pgsql.ru - поиск по PostgreSQL ресурсам
  • [GBK] The GiST Indexing Project at Berkeley
  • PostgreSQL GiST development page
  • [Sto86] Michael Stonebraker. "Inclusion of new types in relational database systems.", In Proceedings of the 4th IEEE International Conference on Data Engineering, pp. 262-269, Washington, D.C., 1986
  • [HNP95] J. M. Hellerstein, J. F. Naughton, and Avi Pfeffer. "Generalized search trees for database systems." In Proceedings of the 21st International Conference on Very Large Data Bases, Zurich, Switzerland, 1995.
  • [Gut84] Antonin Guttman. "R-trees: a dynamic index structure for spatial searching." In ACM SIGMOD International Conference on Management of Data, pp. 47-54, 1984.
  • [Aok98] P.Aoki."Generalized 'Search' in Generalized Search Trees." In Proc. of the 14th Int. Conf. on Data Engineering, Orlando, USA, pp.380-389,1998.
  • [KMH97] Marcel Kornacker, C. Mohan, Joseph M. Hellerstein. "Concurrency and Recovery in Generalized Search Trees." SIGMOD Conference 1997, pp. 62-72.
  • [Kor99] Marcel Kornacker. "High-Performance Extensible Indexing." VLDB 1999, pp. 699-708.

Авторы

Олег Бартунов и Федор Сигаев являются членами PostgreSQL Global Development Group (поддержка и развитие GiST в PostgreSQL) и авторами информационно-поисковой системы по PostgreSQL ресурсам. Они являются авторами целого ряда популярных расширений PostgreSQL, в том числе, модуль полнотекстового поиска tsearch2, поддержка иерархических типов данных ltree, работа с целочисленными массивами intarray. Более подробная информация доступна на странице PostgreSQL GiST development.

Общие замечания по программированию на С под PostgreSQL

Для понимания примеров мы приводим особенности написания пользовательских функций на языке C для PostgreSQL, полное описание можно найти в разделе C-Language Functions документации.

Функции должны использовать интерфейс версии 1, версия 0 deprecated, хотя пока и поддерживается.

  • На уровне С PostgreSQL оперирует с базовыми типами данных или SQL-типами в представлении С-типа Datum. Datum имеет размер, равный размеру указателя на данной архитектуре (PostgreSQL не поддерживает архитектуры с указателем, меньшим 32 бит). SQL-типы в PostgreSQL делятся на передаваемые по значению и по указателю. Передаваемые по значению типы не должны превышать размер 32 бита. Передаваемые по указателю типы подразделяются на типы с фиксированной длиной и переменной. Для типов с переменной длиной первым полем всегда должна быть длина значения int4 (в байтах, с учетом размера поля длины). Для преобразования Datum в тип и обратно существует набор макросов, см.,например, файлы postgres.h, fmgr.h:
    • int32 i = DatumGetInt32(datum);
    • Datum datum = BoolGetDatum( true );
    • text *sometext = DatumGetTextP( datum );
    • Для абстрактного типа, передаваемого по указателю, можно использовать преобразование в указатель:
      • SOMETYPE  *ptr = (SOMETYPE*)DatumGetPointer(datum);
      • Datum datum = PointerGetDatum( ptr );
  • Длинные значения типов с переменной длиной могут "тоститься", то есть нарезаться маленькими кусочками (TOAST - The Oversized Attribute Storage Technique, подробнее). Макросы для встроенных типов учитывают эту возможность, для user-defined это должно указываться непосредственно:
    SOMETYPE  *ptr = (SOMETYPE*)PG_DETOAST_DATUM( DatumGetPointer(datum) );
  • Для работы с типами переменной длины есть дополнительные макросы:
    • VARSIZE( ptr ) - размер в байтах
    • VARDATA( ptr ) - возвращает указатель на данные после поля длины.
    Т.е., если для типа определена структура:
    typedef struct {
    	int32	length;
    	char	data[1];
    } FOO;
    FOO *foo = f();
    
    то f->length == VARSIZE(f) и f->data == (char*)VARDATA(f) всегда. Заметим, что длина поля не может превышать 1Gb. Два бита в поле длина используются PostgreSQL в своих целях.
  • Функция должна возвращать тип Datum и объявляться как:
    PG_FUNCTION_INFO_V1(FUNCTION);<br>
     
    Datum FUNCTION(PG_FUNCTION_ARGS);
  • Передача параметров вызываемой функции и возвращаемое значение прозводится посредством макросов. Порядковый номер аргумента задается параметром макроса.
    Datum
    function(PG_FUNCTION_ARGS) {
    	/* целое число, передается по значению */
    	int32	i  = PG_GETARG_INT32(0);
    	/* указатель на прямоугольник */
    	BOX	*b = PG_GETARG_BOX_P(1);
    	/* указатель на текст */
    	text	*t = PG_GETARG_TEXT_P(2);
    	/* пользовательский тип с переменной длиной */
    	FOO	*f = (FOO*)DatumGetPointer(PG_DETOAST_DATUM(PG_GETARG_DATUM(3));
    
    	....
    
    	/* 
             * после того, как работа произведена, не плохо бы очистить память
             *  "потостенных" значений, Аргументы: 
    	 *   первый - имя переменной-параметра функции,
    	 *   второй - порядковый номер 
    	 */
    	PG_FREE_IF_COPY(t,2);
    	PG_FREE_IF_COPY(f,3);
    	
    	PG_RETURN_INT32( i );
    }
    
  • Функциям запрещено менять значения своих аргументов. Это правило не относится к некоторым специальным функциям, например к функциям penalty, equal, union и picksplit интерфейса к GiST.
  • Все управление динамической памятью должно осуществляться PostgreSQL-аналогами palloc/repalloc/pfree. Их использование, как правило, предохраняет от утечек памяти, быстрее, и облегчает отладку (если PostgreSQL скомпилен с флагами --enable-debug и --enable-cassert)
  • Память для типов, передаваемых по указателю и соответствующих какому-либо SQL-типу, должна быть зарезервирована вызовом palloc.

Back to top

(С) Виктор Вислобоков, 2008-2023