Hablaremos de cómo extender sus capacidades con el uso de trigramas e índices GIN, para que sea incluso capaz de usar índices con patrones tipo ‘%postgres%’.

Al final del artículo seremos capaces de hacer búsquedas por cualquier tipo de dato texto con la eficiencia y velocidad que proporcionan los índices usando patrones de búsqueda muy complejos.

¡Empecemos!

El operador LIKE: conceptos básicos y ejemplos

En general, el operador LIKE, como su nombre indica, sirve para buscar registros cuyo valor se asemeje a un patrón de búsqueda. Se usan dos wildcards para representar expresiones regulares:

El wildcard ‘%’ reemplaza cualquier secuencia de cero o más caracteres.

Significado	Patrón	Resultado
Que empiece por	‘postgresql’ LIKE ‘postgres%’	true
Que acabe por	‘postgresql’ LIKE ‘%sql’	true
Que contenga	‘postgresql’ LIKE ‘%gres%’	true

El wildcard ‘_’ reemplaza un único carácter

Significado	Patrón	Resultado
Que la última letra sea cualquiera	‘postgresql’ LIKE ‘postgresq_’	true
Que la primera letra sea cualquiera	‘postgresql’ LIKE ‘_ostgresql’’	true
Que la primera letra y la ultima sean cualquiera	‘postgresql’ LIKE ‘_ostgresq_’	true

Uso de LIKE en una base de datos con collation “C”

Para empezar, vamos a probar el operador LIKE en una base de datos cuyo collation sea ‘C’, es decir que el texto se ordena por el valor de los bytes.

Creemos la base de datos en primer lugar. La creamos con encoding ASCII pero sería igual con encoding utf8 o latin1

postgres=# CREATE DATABASE like_test ENCODING = ‘SQL_ASCII’ LOCALE = ‘C’ TEMPLATE = ‘template0’;
CREATE DATABASE

Nos conectamos a la base de datos

postgres=# \c like_test ;
psql (14.17 (Ubuntu 14.17-0ubuntu0.22.04.1), server 14.15 (Ubuntu 14.15-1.pgdg22.04+1))
You are now connected to database «like_test» as user «postgres».

Creamos una tabla con un tipo de dato texto

like_test=# CREATE TABLE like_test(field text);
CREATE TABLE

Llenamos la tabla con datos de prueba

like_test=# INSERT INTO like_test SELECT md5(a::text) FROM generate_series(1, 1000000) AS a;
INSERT 0 1000000

Hemos insertado un millón de registros utilizando la función generate_series(1, 1000000), que emite una tabla con números secuenciales. A cada número generado, le hemos aplicado la función hash md5 para obtener una secuencia de caracteres pseudo-aleatoria. Finalmente insertamos un solo registro con el valor ‘postgres’ que nos servirá para las pruebas.

postgres=# INSERT INTO like_test(field) VALUES (‘postgres’);
INSERT 0 1

Finalmente, ya estamos listos para nuestras pruebas.

Búsqueda sin índice: Limitaciones y análisis

Busquemos sin índice usando EXPLAIN para ver qué estrategia sigue. Desactivamos el escaneo paralelo para hacer más comprensible la lectura del plan.

like_test=# SET max_parallel_workers_per_gather = 0;
SET
like_test=# EXPLAIN (ANALYZE, VERBOSE) SELECT * FROM like_test WHERE field LIKE ‘post%’;
QUERY PLAN
——————————————————————————————————————-
Seq Scan on public.like_test (cost=0.00..20834.01 rows=100 width=33) (actual time=45.528..45.530 rows=1 loops=1)
Output: field
Filter: (like_test.field ~~ ‘post%’::text)
Rows Removed by Filter: 1000000
Query Identifier: 2553294308349252460
Planning Time: 0.161 ms
Execution Time: 45.641 ms
(7 rows)

El plan de ejecución usa un Seq Scan, es decir, un escaneo de toda la tabla porque no tiene otra opción, no hay ningún índice. Filtra descartando todos los que no empiecen por post%. El operador LIKE se representa internamente como ‘~~’

Búsqueda con índice

Creamos un índice para el campo ‘field’. El índice que se crea por defecto es un btree, que es un árbol en el que se guardan los elementos ordenados alfabéticamente (según el collation) junto con el puntero a la página y registro.

like_test=# CREATE INDEX ON like_test(field);
CREATE INDEX

Repetimos ahora la búsqueda

like_test=# EXPLAIN (ANALYZE, VERBOSE) SELECT * FROM like_test WHERE field LIKE ‘post%’;
QUERY PLAN
———————————————————————————————————————————————-
Index Only Scan using like_test_field_idx on public.like_test (cost=0.42..4.45 rows=100 width=33) (actual time=0.010..0.011 rows=1 loops=1)
Output: field
Index Cond: ((like_test.field >= ‘post’::text) AND (like_test.field < ‘posu’::text))
Filter: (like_test.field ~~ ‘post%’::text)
Heap Fetches: 0
Query Identifier: 2553294308349252460
Planning Time: 0.469 ms
Execution Time: 0.162 ms
(8 rows)

Vemos que se usa el índice: ‘Index Only Scan’. El planner traduce el filtro a una condición de búsqueda para el índice: field >= ‘post’ AND field < ‘posu’. Es decir todo lo que empiece por ‘post’ pero que no llegue a ‘posu’, ya que la ‘u’ ya seria la letra posterior a la ‘t’ del filtro ‘post%’.

Recordemos que en una base de datos siempre hemos usar índices para las búsquedas si queremos que todo funcione bien y rápido.

Hasta aquí todo funciona según lo esperado.

Uso de LIKE en una base de datos con collate diferente de ‘C’

Lo más habitual en nuestra instalación de postgres es que el Encoding sea UTF8 y el Collate sea alguno de los xx_XX.utf8.

El encoding es cómo se codifican los caracteres a bytes, que en utf8 es variable de 1 a 4 bytes. Utf8 es el encoding más habitual y permite representar todos los idiomas.

El collate es como se ordenan, para el orden alfabético español sería el es_ES.utf8. En este orden por ejemplo la ‘Ñ’, va despues de la ‘N’ que en un colation ‘C’ es la ‘O’ la que va después de la ‘N’.

Vamos a crear una base de datos estándar para una configuración española.

Vemos que se ha creado con encoding utf8, con collate es_ES (español de España) y Ctype de es_ES también.

Vamos a crear una tabla con un campo de tipo texto.

Vamos a insertar un millón de registros con la función md5, para que me genere unos caracteres pseudoaleatorios.

Insertamos también un registro con el valor ‘postgres’ para nuestras pruebas.

like_test=# CREATE TABLE test(field text);
CREATE TABLE
like_test=# INSERT INTO test SELECT md5(a::text) FROM generate_series(1, 1000000) AS a;
INSERT 0 1000000
like_test=# INSERT INTO test VALUES(‘postgres’);
INSERT 0 1

Vamos a crear un índice btree y buscar por la expresión LIKE ‘post%’

like_test=# CREATE INDEX ON test(field);
CREATE INDEX
like_test=# EXPLAIN (ANALYZE, VERBOSE) SELECT * FROM test WHERE field LIKE ‘post%’;
QUERY PLAN
————————————————————————————————————–
Seq Scan on public.test (cost=0.00..20834.01 rows=100 width=33) (actual time=43.287..43.288 rows=1 loops=1)
Output: field
Filter: (test.field ~~ ‘post%’::text)
Rows Removed by Filter: 1000000
Query Identifier: -7947623456012888148
Planning Time: 0.088 ms
Execution Time: 43.378 ms

¡Sorpresa! No usa el índice.

Vamos a probar con otro operador como un mayor o igual que ‘>=’

like_test=# EXPLAIN (ANALYZE, VERBOSE) SELECT * FROM test WHERE field >= ‘post’;
QUERY PLAN
———————————————————————————————————————————-
Index Only Scan using test_field_idx on public.test (cost=0.42..4.44 rows=1 width=33) (actual time=0.014..0.015 rows=1 loops=1)
Output: field
Index Cond: (test.field >= ‘post’::text)
Heap Fetches: 0
Query Identifier: 2811854291613324436
Planning Time: 0.231 ms
Execution Time: 0.162 ms
(7 rows)

El índice si que se usa cuando uso el operador ‘>=’.

El problema viene porque la ordenación de texto con collation es_ES.utf8 o cualquier otra diferente de “C” no sirve para el algoritmo que se usa para poder usar el operador LIKE, LIKE necesita un orden a nivel bytes, que cuando se usa el collation “C” ya se tiene.

Para poder usar LIKE con un collation como es_ES.utf8 necesitamos crear un índice con un ‘operator class’ apropiado. En el caso de el tipo de dato text, el operator class que sirve para el operador LIKE se llama text_pattern_ops y no es el que se usa por defecto al crear el índice.

Para crear un índice que sirva para LIKE con un collation como es_ES.utf8 se hace de esta forma:

like_test=# CREATE INDEX ON test(field text_pattern_ops);
CREATE INDEX

Este índice ahora si que sirve para el operador LIKE. Veamos cómo se ejecuta ahora la consulta:

like_test=# EXPLAIN (ANALYZE, VERBOSE) SELECT * FROM test WHERE field LIKE ‘post%’;
QUERY PLAN
————————————————————————————————————————————
Index Only Scan using test_field_idx on public.test (cost=0.42..8.45 rows=100 width=33) (actual time=0.037..0.038 rows=1 loops=1)
Output: field
Index Cond: ((test.field ~>=~ ‘post’::text) AND (test.field ~<~ ‘posu’::text))
Filter: (test.field ~~ ‘post%’::text)
Heap Fetches: 1
Query Identifier: -938154872528654769
Planning Time: 0.266 ms
Execution Time: 0.156 ms
(8 rows)

Vemos que si se usa ahora el índice, y que los operadores internos que se usan para la condición del índice son ahora ‘~>=~’ y ‘~<~’ que sirven para trabajar con búsqueda de patrones.

Sin embargo si queremos usar también los operadores >, >=, <, <= tendremos que crear un índice con el operator class por defecto, porque con el operator class text_pattern_ops, estos operadores de índice no funcionaran.

like_test=# EXPLAIN (ANALYZE, VERBOSE) SELECT * FROM test WHERE field >= ‘post’;
QUERY PLAN
————————————————————————————————————–
Seq Scan on public.test (cost=0.00..20834.01 rows=100 width=33) (actual time=61.178..61.179 rows=1 loops=1)
Output: field
Filter: (test.field >= ‘post’::text)
Rows Removed by Filter: 1000000
Query Identifier: 7103150511126075852
Planning Time: 0.080 ms
Execution Time: 61.230 ms
(7 rows)

like_test=# CREATE INDEX ON test(field);
CREATE INDEX
like_test=# EXPLAIN (ANALYZE, VERBOSE) SELECT * FROM test WHERE field >= ‘post’;
QUERY PLAN
———————————————————————————————————————————–
Index Only Scan using test_field_idx1 on public.test (cost=0.42..8.44 rows=1 width=33) (actual time=0.010..0.011 rows=1 loops=1)
Output: field
Index Cond: (test.field >= ‘post’::text)
Heap Fetches: 1
Query Identifier: 7103150511126075852
Planning Time: 0.307 ms
Execution Time: 0.147 ms
(7 rows)

Vemos que después de crear el índice, este si que se usa cuando usamos el operador ‘>=’.

Si necesitamos usar el operador LIKE y los operadores relacionales >, >=, <, <= , para un collation distinto de ‘C’, necesitamos crear dos índices para el mismo campo.

Estos serían los dos índices creados:

Uso de LIKE para buscar un patrón que contenga una palabra. LIKE ‘%postgres%

Si hacemos una búsqueda con LIKE ‘%postgres%’ en nuestra base de datos de prueba anterior, veamos qué ocurre

like_test=# EXPLAIN (ANALYZE, VERBOSE) SELECT * FROM test WHERE field LIKE ‘%post%’;
QUERY PLAN
————————————————————————————————————–
Seq Scan on public.test (cost=0.00..20834.01 rows=100 width=33) (actual time=66.233..66.234 rows=1 loops=1)
Output: field
Filter: (test.field ~~ ‘%post%’::text)
Rows Removed by Filter: 1000000
Query Identifier: -938154872528654769
Planning Time: 0.125 ms
Execution Time: 66.319 ms
(7 rows)

No se usa el índice, porque el orden alfabético del índice no sirve para encontrar algo que no sabemos por qué secuencia de caracteres empieza.

En este caso postgres hace un Seq Scan y elimina todos los registros que no cumplen con la condición, algo que es tremendamente lento y nada deseable en una base de datos que funcione en producción.

Sin embargo hay una solución muy inteligente para poder usar índices con este tipo de consultas, vamos a explicarlo.

Trigramas: Qué son y cómo funcionan

Ejemplo práctico: Uso de trigramas en PostgreSQL

Un trigrama es simplemente un grupo de tres caracteres consecutivos dentro de un texto.

Por ejemplo la palabra postgres tiene estos trigramas

Un trigrama sirve por ejemplo para hacer búsquedas fuzzy,

Si en lugar de escribir postgres correctamente lo deletreamos mal y escribimos “postgress”

Los trigramas que daría son:

Tiene un trigrama más que postgress, pero es coincidente en 6 trigramas de 7.

En las búsquedas fuzzy podría encontrar postgress.

Para usar trigramas en postgres hay que crear la extensión primero.

like_test=# CREATE EXTENSION pg_trgm ;
CREATE EXTENSION

Vamos a ver cómo se descompone realmente una palabra en trigramas.

like_test=# SELECT show_trgm(‘postgres’);
show_trgm
———————————————
{» p»,» po»,»es «,gre,ost,pos,res,stg,tgr}

Vemos más trigramas que los que habíamos descompuesto antes.

Para el inicio de palabra se crean trigramas con dos espacios y con un espacio

“ p”
“ po”

Para el final de palabra se crea un trigrama adicional con un espacio al final

“es “

Veamos ahora una operación simple, ver el grado de similitud entre postgress y postgres usando trigramas.

like_test=# SELECT show_trgm(‘postgres’), show_trgm(‘postgress’), similarity(‘postgres’, ‘postgress’) \gx
-[ RECORD 1 ]———————————————–
show_trgm | {» p»,» po»,»es «,gre,ost,pos,res,stg,tgr}
show_trgm | {» p»,» po»,ess,gre,ost,pos,res,»ss «,stg,tgr}
similarity | 0.72727275

Según como se calcula la similaridad, son un 0,72% similares. La fórmula exacta de similitud no es importante ahora, no es de lo que queremos tratar.

Lo que queremos ver es cómo se usan los trigramas para que la búsqueda LIKE ‘%postgres%’ use un índice.

Índices GIN: Mejorando búsquedas con patrones complejos

Introducimos ahora otro concepto, el índice GIN.

Un índice GIN es un índice para localizar palabras en documentos.

Tengamos estos dos documentos

Documento	Texto
1	El perro de casa
2	La casa de arriba

Veamos cómo se localizan esas palabras en los documentos

Palabra	Documentos
El	1
perro	1
de	1, 2
casa	1, 2
La	2
arriba	2

Este tipo de índices se llaman invertidos, porque van de las palabras a los documentos.

Cómo funcionan los índices GIN con trigramas

Un índice GIN para un tipo de dato texto toma los trigramas y dice en qué registro están.

Si tenemos dos registros

id	field	trigrama simplificado resultante
1	uno	uno
2	unos	uno, nos

El índice de trigramas apuntando a los registros sería así:

Trigrama	Registro o documento en el que aparece
uno	1, 2
nos	2

Cómo se usa esto con una búsqueda LIKE ‘%unos%’

Descomponemos ‘unos’ en trigramas simplificados para este ejemplo, y tenemos: uno, nos
Buscamos en el índice los trigramas uno y nos.
Vemos que “uno” está en el registro 1 y 2
Vemos que “dos” está en el registro 2
Vemos que la coincidencia de los dos trigramas solo está en el registro 2
Encontramos el registro 2, solo el 2 porque el registro 1 no tiene los dos trigramas
Hacemos una segunda comprobación para ver que la palabra “unos” es la que está en el registro y la devolvemos.

Veamos como funciona esto con un ejemplo de verdad.

Vamos a crear un índice GIN con gin_trgm_ops, es decir con el operator class para trigramas, para la tabla de ejemplo que teníamos.

like_test=# CREATE INDEX ON test USING GIN (field gin_trgm_ops);
CREATE INDEX
like_test=# \d test
Table «public.test»
Column | Type | Collation | Nullable | Default
——–+——+———–+———-+———
field | text | | |
Indexes:
«test_field_idx» btree (field text_pattern_ops)
«test_field_idx1» btree (field)
«test_field_idx2» gin (field gin_trgm_ops)

Veamos ahora la búsqueda con un explain:

like_test=# EXPLAIN (ANALYZE, VERBOSE) SELECT * FROM test WHERE field LIKE ‘%ostgre%’;
QUERY PLAN
—————————————————————————————————————————
Bitmap Heap Scan on public.test (cost=96.78..465.16 rows=100 width=33) (actual time=0.030..0.031 rows=1 loops=1)
Output: field
Recheck Cond: (test.field ~~ ‘%ostgre%’::text)
Heap Blocks: exact=1
-> Bitmap Index Scan on test_field_idx2 (cost=0.00..96.75 rows=100 width=0) (actual time=0.021..0.021 rows=1 loops=1)
Index Cond: (test.field ~~ ‘%ostgre%’::text)
Query Identifier: -938154872528654769
Planning Time: 0.255 ms
Execution Time: 0.228 ms
(9 rows)

Vemos que el nodo más interno usa un Bitmap index Scan, este lo que hace es buscar en el índice los trigramas en los que se descompone la palabra ‘ostgre’, que son: ost, stg, gre.
Comprueba que los 3 estén presentes a la vez en el registro.
Luego en el Bitmap Heap Scan, Es decir en la tabla, vuelve a recheckear la palabra ‘ostgre’ y cómo ve que coincide, muestra el registro.

Podemos incluso buscar patrones más complejos como ‘_ost_res%’ y vemos que también funciona

like_test=# EXPLAIN (ANALYZE, VERBOSE) SELECT * FROM test WHERE field LIKE ‘_ost_res%’;
QUERY PLAN
—————————————————————————————————————————
Bitmap Heap Scan on public.test (cost=48.78..417.16 rows=100 width=33) (actual time=0.026..0.028 rows=1 loops=1)
Output: field
Recheck Cond: (test.field ~~ ‘_ost_res%’::text)
Heap Blocks: exact=1
-> Bitmap Index Scan on test_field_idx2 (cost=0.00..48.75 rows=100 width=0) (actual time=0.016..0.017 rows=1 loops=1)
Index Cond: (test.field ~~ ‘_ost_res%’::text)
Query Identifier: -938154872528654769
Planning Time: 0.108 ms
Execution Time: 0.157 ms
(9 rows)

Los índices GIN son muy voluminosos, crean varias entradas por documento, en el caso de trigramas, todos los trigramas en los que se descompone, que pueden ser varias decenas.

También cada inserción es muy costosa, cada registro tendrá varios trigramas. Por ello normalmente las inserciones se hacen en diferido, haciendo que cada x inserciones se dispare una actualización.

El uso de índices GIN con trigramas solo se recomienda para tablas que no tengan muchas actualizaciones por estas razones.

Resumen: Optimización de búsquedas con LIKE e índices

Hemos visto el uso de indices Btree para el operador LIKE.
Hemos visto que con collation diferente de ‘C’ hemos de usar el operator class text_pattern_ops para poder usar el operador LIKE.
Hemos visto que para usar índices con operadores relacionales para texto tenemos que crear índices Btree, con las opciones por defecto.
Hemos entendido que es un trigrama.
Hemos visto cómo se puede usar trigramas con índices GIN con gin_trgm_ops para buscar patrones complejos.
Hemos visto que los índices GIN son grandes porque tienen muchas entradas por cada registro y que las inserciones se demoran para agruparlas y hacerlas menos costosas.