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

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

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

Реализация R-Tree для прямоугольников для GiST

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));
}

equal

Сравнивает два прямугольника и возвращает 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);
}

Кстати, тут присутствует вызов встроенной в постгрес ф-ции box_same. Следует также обратить внимание на работу с переменной result: эта интерфейсная ф-ция является исключением из правил и ф-ция должна изменить значения своего параметра. Но это не касается двух первых аргументов.

penalty

Функция возвращает изменение (увеличение) площади прямоугольника после объединения обоих (получение 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);
} 

union

Функция возвращает объединяющий прямоугольник для всех входящих прямоугольников

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);
}

consistent

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

picksplit

Обычно самая сложная фукция в интерфейсе GiST. Полнаю версию можно найти в исходниках постгреса, файл gistproc.c. Можно использовать обычный Гуттмановский (квадратичный) алгоритм. В примере используем простое распределение (четные налево, нечетные направо) - исключительно для краткости.

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

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

compress

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);
}

consistent

Обратите внимание, что всегда вызывается 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);
}