GIN significa Índice Invertido Generalizado (Generalized Inverted Index). GIN está diseñado para manejar casos donde los elementos a indexar son valores compuestos, y las consultas que debe manejar el índice necesitan buscar valores de elementos que aparecen dentro de los elementos compuestos. Por ejemplo, los elementos podrían ser documentos, y las consultas podrían ser búsquedas de documentos que contienen palabras específicas.
Usamos la palabra item (elemento) para referirnos a un valor compuesto que va a ser indexado, y la palabra key (clave) para referirnos al valor de un elemento individual. GIN siempre almacena y busca claves, no los valores de los ítems en sí.
Un índice GIN almacena un conjunto de pares (clave, posting list), donde una posting list (lista de apariciones) es un conjunto de IDs de fila en las que aparece la clave. El mismo ID de fila puede aparecer en múltiples posting lists, ya que un elemento puede contener más de una clave. Cada valor de clave se almacena una sola vez, por lo que un índice GIN es muy compacto en los casos en que la misma clave aparece muchas veces.
GIN es generalizado en el sentido de que el código del método de acceso de GIN no necesita conocer las operaciones específicas que acelera. En su lugar, utiliza estrategias personalizadas definidas para tipos de datos particulares. La estrategia define cómo se extraen las claves de los elementos indexados y de las condiciones de la consulta, y cómo determinar si una fila que contiene algunos de los valores de clave en una consulta realmente satisface la consulta.
Una ventaja de GIN 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. Esta es prácticamente la misma ventaja que tiene el uso de GiST.
La implementación de GIN en PostgreSQL es mantenida principalmente por Teodor Sigaev y Oleg Bartunov. Hay más información sobre GIN en su sitio web.
La distribución principal de PostgreSQL incluye las clases de operadores GIN mostradas en Table 65.3. (Algunos de los módulos opcionales descritos en la Appendix F proporcionan clases de operadores GIN adicionales).
Table 65.3. Clases de operadores GIN integradas
| Nombre | Operadores indexables |
|---|---|
array_ops | && (anyarray,anyarray) |
@> (anyarray,anyarray) | |
<@ (anyarray,anyarray) | |
= (anyarray,anyarray) | |
jsonb_ops | @> (jsonb,jsonb) |
@? (jsonb,jsonpath) | |
@@ (jsonb,jsonpath) | |
? (jsonb,text) | |
?| (jsonb,text[]) | |
?& (jsonb,text[]) | |
jsonb_path_ops | @> (jsonb,jsonb) |
@? (jsonb,jsonpath) | |
@@ (jsonb,jsonpath) | |
tsvector_ops | @@ (tsvector,tsquery) |
De las dos clases de operadores para el tipo jsonb, jsonb_ops
es la predeterminada. jsonb_path_ops admite menos operadores pero
ofrece un mejor rendimiento para dichos operadores.
Consulta la Section 8.14.4 para más detalles.
La interfaz de GIN 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 GIN se encarga de la concurrencia, el registro en el log y las búsquedas en la estructura del árbol.
Todo lo que se necesita para que un método de acceso GIN funcione es implementar unos pocos métodos definidos por el usuario, que definen el comportamiento de las claves en el árbol y las relaciones entre las claves, los elementos indexados y las consultas indexables. En resumen, GIN combina extensibilidad con generalidad, reutilización de código y una interfaz limpia.
Hay dos métodos que debe proporcionar una clase de operadores para GIN:
Datum *extractValue(Datum itemValue, int32 *nkeys,
bool **nullFlags)
Devuelve un array de claves asignado con palloc dado un elemento a indexar. El
número de claves devueltas debe almacenarse en *nkeys.
Si alguna de las claves puede ser nula, también debe asignarse con palloc un array de
*nkeys campos bool, almacenar su dirección en
*nullFlags y establecer estas flags nulas según sea necesario.
*nullFlags se puede dejar como NULL (su valor inicial)
si todas las claves no son nulas.
El valor de retorno puede ser NULL si el elemento no contiene claves.
Datum *extractQuery(Datum query, int32 *nkeys,
StrategyNumber n, bool **pmatch, Pointer **extra_data,
bool **nullFlags, int32 *searchMode)
Devuelve un array de claves asignado con palloc dado un valor a consultar; es decir,
query es el valor en el lado derecho de un operador
indexable cuyo lado izquierdo es la columna indexada.
n es el número de estrategia del operador dentro de la
clase de operadores (ver Section 36.16.2).
A menudo, extractQuery necesitará consultar
n para determinar el tipo de datos de
query y el método que debe usar para extraer los valores de clave.
El número de claves devueltas debe almacenarse en *nkeys.
Si alguna de las claves puede ser nula, también debe asignarse con palloc un array de
*nkeys campos bool, almacenar su dirección en
*nullFlags y establecer estas flags nulas según sea necesario.
*nullFlags se puede dejar como NULL (su valor inicial)
si todas las claves no son nulas.
El valor de retorno puede ser NULL si la consulta (query) no contiene claves.
searchMode es un argumento de salida que permite a
extractQuery especificar detalles sobre cómo se realizará la búsqueda.
Si *searchMode se establece en
GIN_SEARCH_MODE_DEFAULT (que es el valor con el que
se inicializa antes de la llamada), solo los elementos que coinciden con al menos una de
las claves devueltas se consideran candidatos a coincidir.
Si *searchMode se establece en
GIN_SEARCH_MODE_INCLUDE_EMPTY, además de los elementos que
contienen al menos una clave coincidente, los elementos que no contienen claves en
absoluto se consideran candidatos a coincidir. (Este modo es útil para
implementar operadores del tipo "es-subconjunto-de", por ejemplo).
Si *searchMode se establece en GIN_SEARCH_MODE_ALL,
todos los elementos no nulos en el índice se consideran candidatos a coincidir,
coincidan o no con alguna de las claves devueltas. (Este modo es mucho más
lento que las otras dos opciones, ya que requiere escanear esencialmente todo el índice,
pero puede ser necesario para implementar casos extremos correctamente. Un operador
que necesite este modo en la mayoría de los casos probablemente no sea un buen candidato
para una clase de operadores GIN).
Los símbolos que se deben usar para configurar este modo están definidos en
access/gin.h.
pmatch es un argumento de salida para usar cuando se admite
la coincidencia parcial. Para usarlo, extractQuery debe asignar
un array de *nkeys bools y almacenar su dirección en
*pmatch. Cada elemento del array debe establecerse en verdadero (true)
si la clave correspondiente requiere una coincidencia parcial, o en falso (false) si no.
Si *pmatch se establece en NULL, GIN asume que la coincidencia parcial
no es necesaria. La variable se inicializa en NULL antes de la llamada,
por lo que este argumento puede ser ignorado por las clases de operadores que no
admiten la coincidencia parcial.
extra_data es un argumento de salida que permite a
extractQuery pasar datos adicionales a los métodos
consistent y comparePartial.
Para usarlo, extractQuery debe asignar
un array de *nkeys punteros y almacenar su dirección en
*extra_data, luego almacenar lo que desee en los
punteros individuales. La variable se inicializa en NULL antes de la
llamada, por lo que este argumento puede ser ignorado por las clases de operadores que
no requieren datos adicionales. Si se establece *extra_data,
todo el array se pasa al método consistent, y
el elemento apropiado al método comparePartial.
Una clase de operadores también debe proporcionar una función para verificar si un elemento indexado
coincide con la consulta. Viene en dos variantes, una función booleana consistent
y una función ternaria triConsistent.
triConsistent cubre la funcionalidad de ambas, por lo que proporcionar
solo triConsistent es suficiente. Sin embargo, si la variante booleana
es significativamente más barata de calcular, puede ser ventajoso proporcionar ambas.
Si solo se proporciona la variante booleana, se desactivan algunas optimizaciones que
dependen de descartar elementos del índice antes de obtener todas las claves.
bool consistent(bool check[], StrategyNumber n, Datum query,
int32 nkeys, Pointer extra_data[], bool *recheck,
Datum queryKeys[], bool nullFlags[])
Devuelve verdadero si un elemento indexado satisface el operador de consulta con
el número de estrategia n (o podría satisfacerlo, si se devuelve la
indicación de recheck). Esta función no tiene acceso directo al valor del
elemento indexado, ya que GIN no almacena elementos de
forma explícita. En cambio, lo que está disponible es el conocimiento sobre qué
valores de clave extraídos de la consulta aparecen en un elemento indexado dado. El
array check tiene una longitud de nkeys, que es
la misma que la cantidad de claves devueltas previamente por
extractQuery para este dato query.
Cada elemento del array check es verdadero si el elemento indexado
contiene la clave de consulta correspondiente, es decir, si (check[i] == true) la i-ésima
clave del array de resultados de extractQuery está presente en el
elemento indexado. Se pasa el dato query original en caso de que el
método consistent necesite consultarlo, al igual que los arrays
queryKeys[] y nullFlags[] devueltos
previamente por extractQuery.
extra_data es el array de datos adicionales devuelto por
extractQuery, o NULL si no hay ninguno.
Cuando extractQuery devuelve una clave nula en
queryKeys[], el elemento check[] correspondiente
es verdadero si el elemento indexado contiene una clave nula; es decir, la
semántica de check[] es como IS NOT DISTINCT
FROM. La función consistent puede examinar el
elemento nullFlags[] correspondiente si necesita distinguir
entre una coincidencia de valor regular y una coincidencia nula.
Si tiene éxito, *recheck debe establecerse en verdadero si la tupla
del heap debe volver a verificarse con el operador de consulta, o en falso si
la prueba del índice es exacta. Es decir, un valor de retorno falso garantiza
que la tupla del heap no coincide con la consulta; un valor de retorno verdadero con
*recheck establecido en falso garantiza que la tupla del heap sí
coincide con la consulta; y un valor de retorno verdadero con
*recheck establecido en verdadero significa que la tupla del heap podría
coincidir con la consulta, por lo que debe ser obtenida y verificada de nuevo evaluando
el operador de consulta directamente contra el elemento originalmente indexado.
GinTernaryValue triConsistent(GinTernaryValue check[], StrategyNumber n, Datum query,
int32 nkeys, Pointer extra_data[],
Datum queryKeys[], bool nullFlags[])
triConsistent es similar a consistent,
but instead of Booleans in the check vector, there are
three possible values for each
key: GIN_TRUE, GIN_FALSE and
GIN_MAYBE. GIN_FALSE and GIN_TRUE
have the same meaning as regular Boolean values, while
GIN_MAYBE means that the presence of that key is not known.
When GIN_MAYBE values are present, the function should only
return GIN_TRUE if the item certainly matches whether or
not the index item contains the corresponding query keys. Likewise, the
function must return GIN_FALSE only if the item certainly
does not match, whether or not it contains the GIN_MAYBE
keys. If the result depends on the GIN_MAYBE entries, i.e.,
the match cannot be confirmed or refuted based on the known query keys,
the function must return GIN_MAYBE.
When there are no GIN_MAYBE values in the check
vector, a GIN_MAYBE return value is the equivalent of
setting the recheck flag in the
Boolean consistent function.
Además, GIN debe tener una forma de ordenar los valores de clave almacenados en el índice. La clase de operadores puede definir el orden de clasificación especificando un método de comparación:
int compare(Datum a, Datum b)Compara dos claves (¡no elementos indexados!) y devuelve un entero menor que cero, cero o mayor que cero, indicando si la primera clave es menor, igual o mayor que la segunda. Nunca se pasan claves nulas a esta función.
Alternativamente, si la clase de operadores no proporciona un método compare,
GIN buscará la clase de operadores btree predeterminada para el tipo de datos de la clave del
índice y utilizará su función de comparación. Se recomienda especificar la función de
comparación en una clase de operadores GIN que esté diseñada para un solo tipo de datos,
ya que buscar la clase de operadores btree cuesta algunos ciclos. Sin embargo, las clases
de operadores GIN polimórficas (como array_ops) normalmente no pueden
especificar una sola función de comparación.
Una clase de operadores para GIN puede proporcionar opcionalmente los siguientes métodos:
int comparePartial(Datum partial_key, Datum key, StrategyNumber n,
Pointer extra_data)
Compara una clave de consulta de coincidencia parcial con una clave de índice. Devuelve un
entero cuyo signo indica el resultado: menor que cero significa que la clave del
índice no coincide con la consulta, pero el escaneo del índice debe continuar; cero
significa que la clave del índice coincide con la consulta; mayor que cero indica
que el escaneo del índice debe detenerse porque no son posibles más coincidencias.
Se proporciona el número de estrategia n del operador que
generó la consulta de coincidencia parcial, en caso de que se necesite su semántica para
determinar cuándo finalizar el escaneo. Además, extra_data es el
elemento correspondiente del array de datos adicionales creado por
extractQuery, o NULL si no hay ninguno. Nunca se
pasan claves nulas a esta función.
void options(local_relopts *relopts)Define un conjunto de parámetros visibles para el usuario que controlan el comportamiento de la clase de operadores.
A la función options 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. Se puede acceder a las opciones desde otras
funciones de soporte utilizando las macros PG_HAS_OPCLASS_OPTIONS()
y PG_GET_OPCLASS_OPTIONS().
Dado que tanto la extracción de claves de los valores indexados como la representación de la clave en GIN son flexibles, pueden depender de parámetros especificados por el usuario.
Para admitir consultas de “coincidencia parcial”, una clase de operadores debe
proporcionar el método comparePartial, y su método
extractQuery debe establecer el parámetro pmatch
cuando se encuentra una consulta de coincidencia parcial. Consulta la
Section 65.4.4.2 para más detalles.
Los tipos de datos reales de los diversos valores Datum mencionados anteriormente
varían según la clase de operadores. Los valores de los elementos pasados a
extractValue siempre son del tipo de entrada de la clase de operadores, y
todos los valores de clave deben ser del tipo STORAGE de la clase. El tipo
del argumento query pasado a extractQuery,
consistent y triConsistent es el tipo de entrada de la
derecha del operador miembro de la clase identificado por el número de estrategia. Este no
tiene que ser el mismo que el tipo indexado, siempre que se puedan extraer valores de clave del
tipo correcto a partir de él. Sin embargo, se recomienda que las declaraciones SQL de estas
tres funciones de soporte utilicen el tipo de datos indexado de la opclass para el argumento
query, aunque el tipo real pueda ser otro según el operador.
Internamente, un índice GIN contiene un índice B-tree construido sobre las claves, donde cada clave es un elemento de uno o más elementos indexados (un miembro de un array, por ejemplo) y donde cada tupla en una página hoja contiene un puntero a un B-tree de punteros de heap (un “posting tree”), o una simple lista de punteros de heap (un “posting list”) cuando la lista es lo suficientemente pequeña como para caber en una sola tupla del índice junto con el valor de la clave. La Figure 65.1 ilustra estos componentes de un índice GIN.
A partir de PostgreSQL 9.1, se pueden incluir valores de clave
nulos en el índice. Además, se incluyen marcadores de posición nulos en el índice para
elementos indexados que son nulos o no contienen claves según
extractValue. Esto permite que las búsquedas que deberían encontrar
elementos vacíos puedan hacerlo.
Los índices GIN multicolumna se implementan construyendo un único B-tree sobre valores compuestos (número de columna, valor de la clave). Los valores de las claves para diferentes columnas pueden ser de diferentes tipos.
Figure 65.1. Componentes internos de GIN
La actualización de un índice GIN tiende a ser lenta debido a la propia
naturaleza de los índices invertidos: insertar o actualizar una fila en el heap puede causar
muchas inserciones en el índice (una por cada clave extraída del elemento indexado).
GIN puede posponer gran parte de este trabajo insertando nuevas tuplas
en una lista temporal y desordenada de entradas pendientes (pending entries).
Cuando la tabla es procesada por vacuum o autoanalyze, o cuando se llama a la función
gin_clean_pending_list, o si la lista de pendientes supera el límite
gin_pending_list_limit, las entradas se mueven a la estructura de
datos principal de GIN mediante las mismas técnicas de inserción masiva
que se utilizan durante la creación inicial del índice. Esto mejora enormemente la
velocidad de actualización de los índices GIN, incluso teniendo en cuenta
la sobrecarga de vacuum. Además, el trabajo de sobrecarga puede ser realizado por un
proceso en segundo plano en lugar de la ejecución de la consulta en primer plano.
La principal desventaja de este enfoque es que las búsquedas deben escanear la lista de entradas pendientes además de buscar en el índice normal, por lo que una lista grande de entradas pendientes ralentizará las búsquedas significativamente. Otra desventaja es que, aunque la mayoría de las actualizaciones son rápidas, una actualización que haga que la lista de pendientes sea “demasiado grande” provocará un ciclo de limpieza inmediato y será mucho más lenta que las demás. El uso adecuado de autovacuum puede minimizar ambos problemas.
Si el tiempo de respuesta constante es más importante que la velocidad de actualización, se
puede desactivar el uso de entradas pendientes apagando el parámetro de almacenamiento
fastupdate para un índice GIN. Consulta la
CREATE INDEX para más detalles.
GIN puede admitir consultas de “coincidencia parcial”, en las que la consulta no
determina una coincidencia exacta para una o más claves, pero las coincidencias posibles
caen dentro de un rango razonablemente estrecho de valores de clave (dentro del orden de
clasificación de claves determinado por el método de soporte compare). El
método extractQuery, en lugar de devolver un valor de clave para coincidir
exactamente, devuelve un valor de clave que es el límite inferior del rango a buscar y
establece la flag pmatch en verdadero. El rango de claves se escanea
luego utilizando el método comparePartial.
comparePartial debe devolver cero para una clave de índice que coincide,
menos de cero para una no coincidencia que todavía está dentro del rango a buscar, o mayor
que cero si la clave del índice está más allá del rango que podría coincidir.
La inserción en un índice GIN puede ser lenta debido a la probabilidad de que se inserten muchas claves por cada elemento. Por lo tanto, para inserciones masivas en una tabla se recomienda eliminar el índice GIN y volver a crearlo después de terminar la inserción masiva.
Cuando fastupdate está habilitado para GIN
(consulta la Section 65.4.4.1 para más detalles), la penalización es
menor que cuando no lo está. Pero para actualizaciones muy grandes, todavía puede ser
mejor eliminar y volver a crear el índice.
El tiempo de creación de un índice GIN es muy sensible al parámetro
maintenance_work_mem; no vale la pena escatimar en memoria de trabajo
durante la creación del índice.
Durante una serie de inserciones en un índice GIN existente que tiene
fastupdate habilitado, el sistema limpiará la lista de entradas
pendientes cada vez que la lista supere gin_pending_list_limit. Para
evitar fluctuaciones en el tiempo de respuesta observado, es deseable que la limpieza
de la lista de pendientes ocurra en segundo plano (es decir, a través de autovacuum). Las
operaciones de limpieza en primer plano se pueden evitar aumentando
gin_pending_list_limit o haciendo que autovacuum sea más agresivo. Sin
embargo, aumentar el umbral de la operación de limpieza significa que si ocurre una
limpieza en primer plano, tardará aún más.
gin_pending_list_limit se puede anular para índices GIN individuales
cambiando los parámetros de almacenamiento, lo que permite que cada índice GIN tenga su
propio umbral de limpieza. Por ejemplo, es posible aumentar el umbral solo para el índice
GIN que recibe muchas actualizaciones y disminuirlo en los demás casos.
El objetivo principal de desarrollar índices GIN fue crear soporte para búsquedas de texto completo altamente escalables en PostgreSQL, y a menudo hay situaciones en las que una búsqueda de texto completo devuelve un conjunto muy grande de resultados. Además, esto ocurre a menudo cuando la consulta contiene palabras muy frecuentes, por lo que el gran conjunto de resultados ni siquiera es útil. Dado que leer muchas tuplas del disco y ordenarlas podría llevar mucho tiempo, esto es inaceptable para producción. (Ten en cuenta que la búsqueda en el índice en sí es muy rápida).
Para facilitar la ejecución controlada de tales consultas, GIN tiene un
límite superior suave configurable en el número de filas devueltas: el parámetro de
configuración gin_fuzzy_search_limit. Está establecido en 0 (que significa
sin límite) de forma predeterminada. Si se establece un límite distinto de cero, entonces
el conjunto devuelto es un subconjunto del conjunto de resultados completo, elegido de
forma aleatoria.
“Suave” significa que el número real de resultados devueltos podría diferir un poco del límite especificado, dependiendo de la consulta y de la calidad del generador de números aleatorios del sistema.
Por experiencia, los valores en miles (por ejemplo, de 5000 a 20000) funcionan bien.
GIN asume que los operadores indexables son estrictos (strict). Esto
significa que no se llamará en absoluto a extractValue en un valor de
elemento nulo (en su lugar, se crea automáticamente una entrada de índice de marcador de
posición), y tampoco se llamará a extractQuery en un valor de consulta nulo
(en su lugar, se asume que la consulta no se puede satisfacer). Ten en cuenta, sin embargo,
que se admiten valores de clave nulos contenidos dentro de un elemento compuesto o valor de
consulta que no sea nulo.
La distribución principal de PostgreSQL
incluye las clases de operadores GIN mostradas anteriormente en la
Table 65.3.
Los siguientes módulos de contrib también contienen
clases de operadores GIN:
btree_ginFuncionalidad equivalente a B-tree para varios tipos de datos
hstoreMódulo para almacenar pares (clave, valor)
intarraySoporte mejorado para int[]
pg_trgmSimilitud de texto utilizando coincidencia de trigramas