65.2. Índices GiST #

65.2.1. Introducción
65.2.2. Clases de operadores integradas
65.2.3. Extensibilidad
65.2.4. Implementación
65.2.5. Ejemplos

65.2.1. Introducción #

GiST significa Árbol de Búsqueda Generalizado (Generalized Search Tree). Es un método de acceso estructurado en árbol balanceado, que actúa como una plantilla base en la cual implementar esquemas de indexación arbitrarios. Los B-trees, R-trees y muchos otros esquemas de indexación se pueden implementar en GiST.

Una ventaja de GiST es que permite el desarrollo de tipos de datos personalizados con sus métodos de acceso adecuados por parte de un experto en el dominio de ese tipo de datos, en lugar de un experto en bases de datos.

Parte de la información aquí expuesta procede del sitio web del proyecto de indexación GiST de la Universidad de California en Berkeley y de la tesis de Marcel Kornacker, Access Methods for Next-Generation Database Systems. La implementación de GiST en PostgreSQL es mantenida principalmente por Teodor Sigaev y Oleg Bartunov, y hay más información en su sitio web.

65.2.2. Clases de operadores integradas #

La distribución principal de PostgreSQL incluye las clases de operadores GiST mostradas en Table 65.1. (Algunos de los módulos opcionales descritos en la Appendix F proporcionan clases de operadores GiST adicionales).

Table 65.1. Clases de operadores GiST integradas

NombreOperadores indexablesOperadores de ordenamiento
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) 

Por razones históricas, la clase de operadores inet_ops no es la clase predeterminada para los tipos inet y cidr. Para usarla, menciona el nombre de la clase en CREATE INDEX, por ejemplo:

CREATE INDEX ON my_table USING GIST (my_inet_column inet_ops);

65.2.3. Extensibilidad #

Tradicionalmente, la implementación de un nuevo método de acceso a índices implicaba mucho trabajo difícil. Era necesario comprender el funcionamiento interno de la base de datos, como el gestor de bloqueos y el Write-Ahead Log. La interfaz de GiST tiene un alto nivel de abstracción, requiriendo que el implementador del método de acceso solo implemente la semántica del tipo de datos al que se está accediendo. La propia capa de GiST se encarga de la concurrencia, el registro en el log y las búsquedas en la estructura del árbol.

Esta extensibilidad no debe confundirse con la extensibilidad de los otros árboles de búsqueda estándar en cuanto a los datos que pueden manejar. Por ejemplo, PostgreSQL admite B-trees e índices hash extensibles. Eso significa que puedes utilizar PostgreSQL para construir un B-tree o un hash sobre cualquier tipo de datos que desees. Pero los B-trees solo admiten predicados de rango (<, =, >), y los índices hash solo admiten consultas de igualdad.

Así que si indexas, por ejemplo, una colección de imágenes con un B-tree de PostgreSQL, solo puedes realizar consultas como ¿es la imagenx igual a la imagemy?, ¿es la imagenx menor que la imagemy? y ¿es la imagenx mayor que la imagemy?. Dependiendo de cómo definas igual, menor que y mayor que en este contexto, esto podría ser útil. Sin embargo, al utilizar un índice basado en GiST, podrías crear formas de hacer preguntas específicas del dominio, tal vez buscar todas las imágenes de caballos o buscar todas las imágenes sobreexpuestas.

Todo lo que se necesita para poner en marcha un método de acceso GiST es implementar varios métodos definidos por el usuario, que definen el comportamiento de las claves en el árbol. Por supuesto, estos métodos tienen que ser bastante sofisticados para soportar consultas sofisticadas, pero para todas las consultas estándar (B-trees, R-trees, etc.) son relativamente sencillos. En resumen, GiST combina la extensibilidad junto con la generalidad, la reutilización de código y una interfaz limpia.

Hay cinco métodos que debe proporcionar una clase de operadores de índice para GiST, y siete que son opcionales. La corrección del índice se garantiza mediante la implementación adecuada de los métodos same, consistent y union, mientras que la eficiencia (tamaño y velocidad) del índice dependerá de los métodos penalty y picksplit. Dos métodos opcionales son compress y decompress, que permiten que un índice tenga datos internos del árbol de un tipo diferente al de los datos que indexa. Las hojas deben ser del tipo de datos indexado, mientras que los otros nodos del árbol pueden ser de cualquier estructura C (pero aún debes seguir las reglas de tipo de datos de PostgreSQL aquí, consulta sobre varlena para datos de tamaño variable). Si el tipo de datos interno del árbol existe a nivel de SQL, se puede utilizar la opción STORAGE del comando CREATE OPERATOR CLASS. El octavo método opcional es distance, que es necesario si la clase de operadores desea admitir escaneos ordenados (búsquedas del vecino más cercano). El noveno método opcional fetch es necesario si la clase de operadores desea admitir escaneos de solo índice (index-only scans), excepto cuando se omite el método compress. El décimo método opcional options es necesario si la clase de operadores tiene parámetros especificados por el usuario. El undécimo método opcional sortsupport se utiliza para acelerar la creación de un índice GiST. El duodécimo método opcional stratnum se utiliza para traducir los tipos de comparación (de src/include/access/cmptype.h) en números de estrategia utilizados por la clase de operadores. Esto permite que el código principal busque operadores para índices de restricciones temporales.

consistent

Dada una entrada de índice p y un valor de consulta q, esta función determina si la entrada del índice es consistente con la consulta; es decir, ¿podría el predicado column_indexada operador_indexable q ser verdadero para cualquier fila representada por la entrada del índice? Para una entrada de índice de tipo hoja esto equivale a probar la condición indexable, mientras que para un nodo interno del árbol esto determina si es necesario escanear el subárbol del índice representado por el nodo del árbol. Cuando el resultado es true, también se debe devolver una flag recheck. Esto indica si el predicado es ciertamente verdadero o solo posiblemente verdadero. Si recheck = false, el índice ha probado la condición del predicado exactamente, mientras que si recheck = true, la fila es solo una coincidencia candidata. En ese caso, el sistema evaluará automáticamente el operador_indexable contra el valor real de la fila para ver si es realmente una coincidencia. Esta convención permite que GiST admita estructuras de índice tanto con pérdida (lossy) como sin pérdida.

La declaración SQL de la función debe verse así:

CREATE OR REPLACE FUNCTION my_consistent(internal, data_type, smallint, oid, internal)
RETURNS bool
AS 'MODULE_PATHNAME'
LANGUAGE C STRICT;

Y el código coincidente en el módulo C podría seguir este esqueleto:

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;

    /*
     * determinar el valor de retorno en función de la estrategia, la clave y la consulta.
     *
     * Usa GIST_LEAF(entry) para saber dónde se te llama en el árbol del índice,
     * lo cual resulta útil cuando se admite el operador = por ejemplo (podrías
     * verificar si union() no está vacío en nodos que no son hojas y la igualdad en nodos
     * hojas).
     */

    *recheck = true;        /* o false si la comprobación es exacta */

    PG_RETURN_BOOL(retval);
}

Aquí, key es un elemento en el índice y query el valor que se busca en el índice. El parámetro StrategyNumber indica qué operador de tu clase de operadores se está aplicando; coincide con uno de los números de operador en el comando CREATE OPERATOR CLASS.

Dependiendo de qué operadores hayas incluido en la clase, el tipo de datos de query podría variar con el operador, ya que será el tipo que esté en el lado derecho del operador, el cual podría ser diferente del tipo de datos indexado que aparece en el lado izquierdo. (El esqueleto de código anterior asume que solo es posible un tipo; si no es así, la obtención del valor del argumento query tendría que depender del operador). Se recomienda que la declaración SQL de la función consistent utilice el tipo de datos indexado de la opclass para el argumento query, aunque el tipo real pueda ser otro según el operador.

union

Este método consolida la información en el árbol. Dado un conjunto de entradas, esta función genera una nueva entrada de índice que representa a todas las entradas dadas.

La declaración SQL de la función debe verse así:

CREATE OR REPLACE FUNCTION my_union(internal, internal)
RETURNS storage_type
AS 'MODULE_PATHNAME'
LANGUAGE C STRICT;

Y el código coincidente en el módulo C podría seguir este esqueleto:

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

Como puedes ver, en este esqueleto estamos tratando con un tipo de datos donde union(X, Y, Z) = union(union(X, Y), Z). Es bastante fácil admitir tipos de datos donde este no sea el caso, implementando el algoritmo de unión adecuado en este método de soporte de GiST.

El resultado de la función union debe ser un valor del tipo de almacenamiento del índice, cualquiera que sea (puede o no ser diferente del tipo de la columna indexada). La función union debe devolver un puntero a memoria recién asignada con palloc(). No puedes simplemente devolver el valor de entrada tal cual, incluso si no hay cambio de tipo.

Como se muestra arriba, el primer argumento de tipo internal de la función union es en realidad un puntero a GistEntryVector. El segundo argumento es un puntero a una variable entera, que puede ser ignorado. (Antes se requería que la función union almacenara el tamaño de su valor de resultado en esa variable, pero esto ya no es necesario).

compress

Convierte un elemento de datos en un formato adecuado para el almacenamiento físico en una página de índice. Si se omite el método compress, los elementos de datos se almacenan en el índice sin modificaciones.

La declaración SQL de la función debe verse así:

CREATE OR REPLACE FUNCTION my_compress(internal)
RETURNS internal
AS 'MODULE_PATHNAME'
LANGUAGE C STRICT;

Y el código coincidente en el módulo C podría seguir este esqueleto:

PG_FUNCTION_INFO_V1(my_compress);

Datum
my_compress(PG_FUNCTION_ARGS)
{
    GISTENTRY  *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
    GISTENTRY  *retval;

    if (entry->leafkey)
    {
        /* reemplazar entry->key con una versión comprimida */
        compressed_data_type *compressed_data = palloc(sizeof(compressed_data_type));

        /* llenar *compressed_data desde entry->key ... */

        retval = palloc(sizeof(GISTENTRY));
        gistentryinit(*retval, PointerGetDatum(compressed_data),
                      entry->rel, entry->page, entry->offset, FALSE);
    }
    else
    {
        /* normalmente no necesitamos hacer nada con las entradas que no son hojas */
        retval = entry;
    }

    PG_RETURN_POINTER(retval);
}

Por supuesto, tienes que adaptar compressed_data_type al tipo específico al que estás convirtiendo para comprimir tus nodos hoja.

decompress

Convierte la representación almacenada de un elemento de datos en un formato que puede ser manipulado por los otros métodos de GiST en la clase de operadores. Si se omite el método decompress, se asume que los otros métodos de GiST pueden trabajar directamente sobre el formato de datos almacenado. (decompress no es necesariamente lo inverso del método compress; en particular, si compress es con pérdida (lossy), es imposible que decompress reconstruya exactamente los datos originales. decompress tampoco es necesariamente equivalente a fetch, ya que los otros métodos de GiST podrían no requerir la reconstrucción completa de los datos).

La declaración SQL de la función debe verse así:

CREATE OR REPLACE FUNCTION my_decompress(internal)
RETURNS internal
AS 'MODULE_PATHNAME'
LANGUAGE C STRICT;

Y el código coincidente en el módulo C podría seguir este esqueleto:

PG_FUNCTION_INFO_V1(my_decompress);

Datum
my_decompress(PG_FUNCTION_ARGS)
{
    PG_RETURN_POINTER(PG_GETARG_POINTER(0));
}

El esqueleto anterior es adecuado para el caso en que no se necesita descompresión. (Pero, por supuesto, omitir el método por completo es aún más fácil y se recomienda en tales casos).

penalty

Devuelve un valor que indica el costo de insertar la nueva entrada en una rama particular del árbol. Los elementos se insertarán en la ruta con la menor penalización (penalty) en el árbol. Los valores devueltos por penalty deben ser no negativos. Si se devuelve un valor negativo, se tratará como cero.

La declaración SQL de la función debe verse así:

CREATE OR REPLACE FUNCTION my_penalty(internal, internal, internal)
RETURNS internal
AS 'MODULE_PATHNAME'
LANGUAGE C STRICT;  -- en algunos casos las funciones de penalización no necesitan ser strict

Y el código coincidente en el módulo C podría seguir este esqueleto:

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

Por razones históricas, la función penalty no solo devuelve un resultado de tipo float; en su lugar, tiene que almacenar el valor en la ubicación indicada por el tercer argumento. El valor de retorno en sí mismo es ignorado, aunque es convencional devolver la dirección de ese argumento.

La función penalty es crucial para el buen rendimiento del índice. Se utilizará en el momento de la inserción para determinar qué rama seguir al elegir dónde agregar la nueva entrada en el árbol. En el momento de la consulta, cuanto más equilibrado esté el índice, más rápida será la búsqueda.

picksplit

Cuando es necesaria una división de página de índice, esta función decide qué entradas de la página se quedan en la página antigua y cuáles se mueven a la nueva página.

La declaración SQL de la función debe verse así:

CREATE OR REPLACE FUNCTION my_picksplit(internal, internal)
RETURNS internal
AS 'MODULE_PATHNAME'
LANGUAGE C STRICT;

Y el código coincidente en el módulo C podría seguir este esqueleto:

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;

    /* Inicializar el vector de entradas sin procesar (raw entry vector). */
    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);

        /*
         * Elegir dónde colocar las entradas de índice y actualizar unionL y unionR
         * en consecuencia. Añadir las entradas a v->spl_left o v->spl_right,
         * y cuidar los contadores.
         */

        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
        {
            /*
             * Lo mismo a la derecha
             */
        }
    }

    v->spl_ldatum = DataTypeGetDatum(unionL);
    v->spl_rdatum = DataTypeGetDatum(unionR);
    PG_RETURN_POINTER(v);
}

Ten en cuenta que el resultado de la función picksplit se entrega modificando la estructura v pasada como argumento. El valor de retorno en sí es ignorado, aunque es convencional devolver la dirección de v.

Al igual que penalty, la función picksplit es crucial para el buen rendimiento del índice. Diseñar implementaciones adecuadas de penalty y picksplit es donde reside el desafío de implementar índices GiST de buen rendimiento.

same

Devuelve verdadero si dos entradas de índice son idénticas, y falso en caso contrario. (Una entrada de índice es un valor del tipo de almacenamiento del índice, no necesariamente el tipo original de la columna indexada).

La declaración SQL de la función debe verse así:

CREATE OR REPLACE FUNCTION my_same(storage_type, storage_type, internal)
RETURNS internal
AS 'MODULE_PATHNAME'
LANGUAGE C STRICT;

Y el código coincidente en el módulo C podría seguir este esqueleto:

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

Por razones históricas, la función same no solo devuelve un resultado booleano; en su lugar, tiene que almacenar la flag en la ubicación indicada por el tercer argumento. El valor de retorno en sí es ignorado, aunque es convencional devolver la dirección de ese argumento.

distance

Dada una entrada de índice p y un valor de consulta q, esta función determina la distancia de la entrada del índice con respecto al valor de consulta. Esta función debe proporcionarse si la clase de operadores contiene algún operador de ordenamiento. Una consulta que utilice el operador de ordenamiento se implementará devolviendo primero las entradas de índice con los valores de distancia más pequeños, por lo que los resultados deben ser coherentes con la semántica del operador. Para una entrada de índice de tipo hoja, el resultado simplemente representa la distancia a la entrada del índice; para un nodo interno del árbol, el resultado debe ser la distancia más pequeña que podría tener cualquier entrada hija.

La declaración SQL de la función debe verse así:

CREATE OR REPLACE FUNCTION my_distance(internal, data_type, smallint, oid, internal)
RETURNS float8
AS 'MODULE_PATHNAME'
LANGUAGE C STRICT;

Y el código coincidente en el módulo C podría seguir este esqueleto:

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;

    /*
     * determinar el valor de retorno en función de la estrategia, la clave y la consulta.
     */

    PG_RETURN_FLOAT8(retval);
}

Los argumentos de la función distance son idénticos a los argumentos de la función consistent.

Se permite cierta aproximación al determinar la distancia, siempre que el resultado nunca sea mayor que la distancia real de la entrada. Así, por ejemplo, la distancia a una caja delimitadora (bounding box) suele ser suficiente en aplicaciones geométricas. Para un nodo interno del árbol, la distancia devuelta no debe ser mayor que la distancia a cualquiera de los nodos hijos. Si la distancia devuelta no es exacta, la función debe establecer *recheck en verdadero. (Esto no es necesario para nodos internos del árbol; para ellos, siempre se asume que el cálculo es inexacto). En este caso, el ejecutor calculará la distancia exacta después de obtener la tupla del heap y reordenará las tuplas si es necesario.

Si la función de distancia devuelve *recheck = true para cualquier nodo hoja, el tipo de retorno del operador de ordenamiento original debe ser float8 o float4, y los valores de resultado de la función de distancia deben ser comparables a los del operador de ordenamiento original, ya que el ejecutor ordenará utilizando tanto los resultados de la función de distancia como los resultados del operador de ordenamiento recalculados. De lo contrario, los valores de resultado de la función de distancia pueden ser cualquier valor finito de tipo float8, siempre que el orden relativo de los valores de resultado coincida con el orden devuelto por el operador de ordenamiento. (El infinito y el menos infinito se utilizan internamente para manejar casos como los valores nulos, por lo que no se recomienda que las funciones de distance devuelvan estos valores).

fetch

Convierte la representación del índice comprimido de un elemento de datos en el tipo de datos original, para escaneos de solo índice (index-only scans). Los datos devueltos deben ser una copia exacta y sin pérdidas del valor originalmente indexado.

La declaración SQL de la función debe verse así:

CREATE OR REPLACE FUNCTION my_fetch(internal)
RETURNS internal
AS 'MODULE_PATHNAME'
LANGUAGE C STRICT;

El argumento es un puntero a una estructura GISTENTRY. Al entrar, su campo key contiene un dato hoja no nulo en forma comprimida. El valor de retorno es otra estructura GISTENTRY, cuyo campo key contiene el mismo dato en su forma original no comprimida. Si la función de compresión de la opclass no hace nada para las entradas de tipo hoja, el método fetch puede devolver el argumento tal cual. O bien, si la opclass no tiene una función de compresión, el método fetch también se puede omitir, ya que necesariamente sería una operación nula (no-op).

El código coincidente en el módulo C podría seguir este esqueleto:

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

    /*
     * Convertir 'fetched_data' en un Datum del tipo de datos original.
     */

    /* llenar *retval desde fetched_data. */
    gistentryinit(*retval, PointerGetDatum(converted_datum),
                  entry->rel, entry->page, entry->offset, FALSE);

    PG_RETURN_POINTER(retval);
}

Si el método de compresión tiene pérdidas (is lossy) para las entradas hoja, la clase de operadores no puede admitir escaneos de solo índice y no debe definir una función fetch.

options

Permite la definición de parámetros visibles para el usuario que controlan el comportamiento de la clase de operadores.

La declaración SQL de la función debe verse así:

CREATE OR REPLACE FUNCTION my_options(internal)
RETURNS void
AS 'MODULE_PATHNAME'
LANGUAGE C STRICT;

A la función se le pasa un puntero a una estructura local_relopts, que debe llenarse con un conjunto de opciones específicas de la clase de operadores. Las opciones se pueden acceder desde otras funciones de soporte utilizando las macros PG_HAS_OPCLASS_OPTIONS() y PG_GET_OPCLASS_OPTIONS().

A continuación se muestra un ejemplo de implementación de my_options() y el uso de parámetros desde otras funciones de soporte:

typedef enum MyEnumType
{
    MY_ENUM_ON,
    MY_ENUM_OFF,
    MY_ENUM_AUTO
} MyEnumType;

typedef struct
{
    int32   vl_len_;    /* cabecera varlena (¡no tocar directamente!) */
    int     int_param;  /* parámetro entero */
    double  real_param; /* parámetro real */
    MyEnumType enum_param; /* parámetro enum */
    int     str_param;  /* parámetro string */
} MyOptionsStruct;

/* Representación en cadena de los valores de enum */
static relopt_enum_elt_def myEnumValues[] =
{
    {"on", MY_ENUM_ON},
    {"off", MY_ENUM_OFF},
    {"auto", MY_ENUM_AUTO},
    {(const char *) NULL}   /* terminador de lista */
};

static char *str_param_default = "default";

/*
 * Validador de ejemplo: comprueba que el string no mida más de 8 bytes.
 */
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")));
}

/*
 * Rellenador de ejemplo: cambia los caracteres a minúsculas.
 */
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(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;

    /*
     * Normalmente, cuando la opclass contiene el método 'options', las opciones siempre
     * se pasan a las funciones de soporte. Sin embargo, si añades el método 'options' a una
     * opclass existente, los índices definidos anteriormente no tienen opciones, por lo que
     * la comprobación es necesaria.
     */
    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);
    }

    /* el resto de la implementación de la función de soporte */
}

Dado que la representación de la clave en GiST es flexible, puede depender de parámetros especificados por el usuario. Por ejemplo, se puede especificar la longitud de la firma de la clave. Véase gtsvector_options() como ejemplo.

sortsupport

Devuelve una función de comparación para ordenar los datos de forma que se preserve la localidad. Se utiliza en los comandos CREATE INDEX y REINDEX. La calidad del índice creado depende de qué tan bien el orden de clasificación determinado por la función de comparación preserva la localidad de las entradas.

El método sortsupport es opcional. Si no se proporciona, CREATE INDEX construye el índice insertando cada tupla al árbol mediante las funciones penalty y picksplit, lo cual es mucho más lento.

La declaración SQL de la función debe verse así:

CREATE OR REPLACE FUNCTION my_sortsupport(internal)
RETURNS void
AS 'MODULE_PATHNAME'
LANGUAGE C STRICT;

El argumento es un puntero a una estructura SortSupport. Como mínimo, la función debe rellenar su campo comparator. El comparator toma tres argumentos: dos Datums a comparar y un puntero a la estructura SortSupport. Los Datums son los dos valores indexados en el formato en que están almacenados en el índice; es decir, en el formato devuelto por el método compress. La API completa se define en el archivo src/include/utils/sortsupport.h.

El código coincidente en el módulo C podría seguir este esqueleto:

PG_FUNCTION_INFO_V1(my_sortsupport);

static int
my_fastcmp(Datum x, Datum y, SortSupport ssup)
{
  /* establecer el orden entre x e y calculando algún valor de ordenamiento 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();
}

translate_cmptype

Dado un valor de tipo CompareType del archivo src/include/access/cmptype.h, devuelve un número de estrategia utilizado por esta clase de operadores para la funcionalidad de coincidencia. La función debe devolver InvalidStrategy si la clase de operadores no tiene una estrategia coincidente.

Esto se utiliza para las restricciones de índice temporales (es decir, PRIMARY KEY y UNIQUE). Si la clase de operadores proporciona esta función y devuelve resultados para COMPARE_EQ, se puede utilizar en la(s) parte(s) que no sean WITHOUT OVERLAPS de una restricción de índice.

Esta función de soporte corresponde a la función de callback del método de acceso de índice amtranslatecmptype (ver Section 63.2). La función de callback amtranslatecmptype para los índices GiST simplemente llama a la función de soporte translate_cmptype de la familia de operadores respectiva, ya que el método de acceso al índice GiST no tiene números de estrategia fijos por sí mismo.

La declaración SQL de la función debe verse así:

CREATE OR REPLACE FUNCTION my_translate_cmptype(integer)
RETURNS smallint
AS 'MODULE_PATHNAME'
LANGUAGE C STRICT;

Y el registro de la familia de operadores debe verse así:

ALTER OPERATOR FAMILY my_opfamily USING gist ADD
    FUNCTION 12 ("any", "any") my_translate_cmptype(int);

El código coincidente en el módulo C podría seguir este esqueleto:

PG_FUNCTION_INFO_V1(my_translate_cmptype);

Datum
my_translate_cmptype(PG_FUNCTION_ARGS)
{
    CompareType cmptype = PG_GETARG_INT32(0);
    StrategyNumber ret = InvalidStrategy;

    switch (cmptype)
    {
        case COMPARE_EQ:
            ret = BTEqualStrategyNumber;
    }

    PG_RETURN_UINT16(ret);
}

PostgreSQL proporciona una función de traducción: gist_translate_cmptype_common es para las clases de operadores que utilizan las constantes RT*StrategyNumber. La extensión btree_gist define una segunda función de traducción, gist_translate_cmptype_btree, para las clases de operadores que utilizan las constantes BT*StrategyNumber.

Todos los métodos de soporte de GiST se llaman normalmente en contextos de memoria de corta duración; es decir, CurrentMemoryContext se reiniciará después de procesar cada tupla. Por lo tanto, no es muy importante preocuparse por liberar con pfree todo lo que asignes con palloc. Sin embargo, en algunos casos resulta útil que un método de soporte almacene datos en caché entre llamadas repetidas. Para hacer eso, asigna los datos de mayor duración en fcinfo->flinfo->fn_mcxt y mantén un puntero a ellos en fcinfo->flinfo->fn_extra. Dichos datos sobrevivirán durante la vida de la operación de índice (por ejemplo, un único escaneo de índice GiST, creación de índice o inserción de tupla de índice). Ten cuidado de liberar con pfree el valor anterior al reemplazar un valor fn_extra, o la fuga se acumulará durante la duración de la operación.

65.2.4. Implementación #

65.2.4.1. Métodos de creación de índices GiST #

La forma más sencilla de crear un índice GiST es simplemente insertar todas las entradas, una por una. Esto tiende a ser lento para índices grandes porque si las tuplas del índice están dispersas por todo el índice y este es lo suficientemente grande como para no caber en la caché, se necesitarán muchas operaciones de E/S aleatorias. PostgreSQL admite dos métodos alternativos para la creación inicial de un índice GiST: los modos ordenado (sorted) y con almacenamiento en búfer (buffered).

El método ordenado solo está disponible si cada una de las clases de operadores (opclasses) utilizadas por el índice proporciona una función sortsupport, como se describe en la Section 65.2.3. Si es así, este método suele ser el mejor, por lo que se utiliza de forma predeterminada.

El método con almacenamiento en búfer funciona al no insertar tuplas directamente en el índice de inmediato. Puede reducir drásticamente la cantidad de E/S aleatoria necesaria para conjuntos de datos no ordenados. Para conjuntos de datos bien ordenados, el beneficio es menor o inexistente, porque solo un pequeño número de páginas recibe tuplas nuevas a la vez, y esas páginas caben en la caché incluso si el índice en su totalidad no lo hace.

El método con almacenamiento en búfer necesita llamar a la función penalty con más frecuencia que el método sencillo, lo que consume algunos recursos adicionales de la CPU. Además, los búferes necesitan espacio en disco temporal, de hasta el tamaño del índice resultante. El almacenamiento en búfer también puede influir en la calidad del índice resultante, tanto en sentido positivo como negativo. Esa influencia depende de varios factores, como la distribución de los datos de entrada y la implementación de la clase de operadores.

Si el ordenamiento no es posible, de forma predeterminada la creación de un índice GiST cambia al método de almacenamiento en búfer cuando el tamaño del índice alcanza el valor de effective_cache_size. El almacenamiento en búfer se puede forzar o evitar manualmente mediante el parámetro buffering del comando CREATE INDEX. El comportamiento predeterminado es bueno para la mayoría de los casos, pero desactivar el almacenamiento en búfer podría acelerar la creación del índice si los datos de entrada están ordenados.

65.2.5. Ejemplos #

La distribución de fuentes de PostgreSQL incluye varios ejemplos de métodos de índice implementados mediante GiST. El sistema principal actualmente proporciona soporte para búsqueda de texto (indexación para tsvector y tsquery), así como una funcionalidad equivalente a R-Tree para algunos de los tipos de datos geométricos integrados (véase src/backend/access/gist/gistproc.c). Los siguientes módulos de contrib también contienen clases de operadores GiST:

btree_gist

Funcionalidad equivalente a B-tree para varios tipos de datos

cube

Indexación para cubos multidimensionales

hstore

Módulo para almacenar pares (clave, valor)

intarray

RD-Tree para arrays unidimensionales de valores int4

ltree

Indexación para estructuras similares a árboles

pg_trgm

Similitud de texto utilizando coincidencia de trigramas

seg

Indexación para rangos de números de punto flotante (float ranges)