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.
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
| Nombre | Operadores indexables | Operadores 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);
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.
unionEste 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.
picksplitCuando 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.
sameDevuelve 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).
fetchConvierte 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.
optionsPermite 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.
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.
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_gistFuncionalidad equivalente a B-tree para varios tipos de datos
cubeIndexación para cubos multidimensionales
hstoreMódulo para almacenar pares (clave, valor)
intarrayRD-Tree para arrays unidimensionales de valores int4
ltreeIndexación para estructuras similares a árboles
pg_trgmSimilitud de texto utilizando coincidencia de trigramas
segIndexación para rangos de números de punto flotante (“float ranges”)