Text Search in PostgreSQL

Le ricerche testuali sono molto utili e con Postgres e' possibile eseguirle in modo molto efficiente con l'SQL.
Con una serie di esempi pratici, partendo dai costrutti SQL piu' semplici ed arrivando a quelli piu' specializzati, vederemo come eseguire alcune ricerche testuali in Postgres.

Il documento ha un taglio molto pratico con esempi funzionanti ed immediatamente applicabili in SQL.

I LIKE

"I LIKE" vuol dire mi piace in inglese ma il titolo e' una battuta per introdurre il primo e notissimo operatore di ricerca su stringa: LIKE.

L'operatore LIKE, ed il corrispondente ILIKE che e' case-insensitive, consentono di ricercare stringhe in una colonna testuale. Le stringhe possono essere confrontate con un testo fisso e con i caratteri speciali _ e % che indicano rispettivamente un qualsiasi carattere ed una qualsiasi stringa, anche vuota, di caratteri.

Per utilizzare la LIKE abbiamo bisogno di qualche dato di esempio:

CREATE TABLE test (t text); INSERT INTO test VALUES ('Nel mezzo del cammin di nostra vita'); INSERT INTO test VALUES ('mi ritrovai per una selva oscura'); INSERT INTO test VALUES ('che la diritta via era smarrita'); INSERT INTO test SELECT * FROM test; INSERT INTO test SELECT * FROM test; INSERT INTO test SELECT * FROM test; INSERT INTO test SELECT * FROM test; INSERT INTO test SELECT * FROM test; INSERT INTO test SELECT * FROM test; INSERT INTO test SELECT * FROM test; INSERT INTO test SELECT * FROM test; INSERT INTO test SELECT * FROM test; INSERT INTO test VALUES ('L''amor che move il sole e l''altre stelle');

Abbiamo inserito qualche riga utilizzando il trucco di ripetere le stesse righe. Un'alternativa, forse tecnicamente migliore, sarebbe stata quella di utilizzare:
 insert into test (t) select md5(random()::text) from generate_series(1,10000);
Ma in questo modo l'esempio e' piu' divino...

Ora che abbiamo qualche dato e' possibile eseguire alcune semplici ricerche come:

select t from test where t like 'L''amor%'; select count(*) from test where t like '%selva%';

L'operatore ILIKE e' analogo alla LIKE ma e' case-insensitive.

Ma quanto sono efficienti queste ricerche in SQL? Non molto: per renderle performanti abbiamo bisogno di indici!

Indici B-Tree

Per creare un indice B-tree, il tipo di indice piu' utilizzato sui database relazionali, basta il comando:

CREATE INDEX test_idx01 ON test (t);

Per analizzare il query plan e verificare l'utizzo degli indici in Postgres si utilizza l'EXPLAIN: 

EXPLAIN SELECT * FROM test WHERE t LIKE 'L''amor%';
                                   QUERY PLAN                                    
---------------------------------------------------------------------------------
 Index Only Scan using test_btree_idx on test  (cost=0.28..4.30 rows=1 width=33)
   Index Cond: ((t >= 'L''amor'::text) AND (t < 'L''amos'::text))
   Filter: (t ~~ 'L''amor%'::text)
(3 rows)

Bene: l'indice viene utilizzato con una condizione di disugaglianza come indicato dallo step Index Only Scan.

Pero' se controlliamo la seconda query: 

EXPLAIN SELECT * FROM test WHERE t LIKE '%sole%';
                      QUERY PLAN                      
------------------------------------------------------
 Seq Scan on test  (cost=0.00..32.21 rows=1 width=33)
   Filter: (t ~~ '%sole%'::text)
(2 rows)

L'indice B-tree non puo' essere utilizzato perche' la stringa di confronto inizia con %; in questo caso viene eseguito un Seq Scan e quindi viene scandita l'intera tabella. Se la tabella e' di grandi dimensioni la query puo' essere molto pesante. Il problema e' che gli indici B-Tree possono essere utilizzati con la LIKE solo con una parte iniziale fissa [NdA e solo se la collation e' "C" oppure viene utilizzata un'opportuna operator class... ma sono dettagli complicati da vedere in seguito].

Conclusione (parziale): gli indici B-Tree possono essere utilizzati nelle ricerche LIKE solo se la la parte iniziale della stringa ricercata e' una costante. Per eseguire ricerche di parole all'interno di un testo efficienti e' necessario utilizzare altri tipi di indice.

Trigrammi

Per ricercare una parola all'interno di un testo risulta utile operare con l'estensione pg_trgm che introduce una serie di funzioni ed operatori basati sui trigrammi e molto utili per le ricerche testuali.

Le funzioni presenti nell'estensione pg_trgm sono molteplici [NdA un'estensione in Postgres e' una componente opzionale che introduce ulteriori funzionalita' al database, di solito basta il comando CREATE per attivarla], ma utilizziamo solo quello che serve al nostro esempio creando un nuovo indice:

CREATE EXTENSION pg_trgm; CREATE INDEX test_idx02 ON test USING GIN (t gin_trgm_ops); 
EXPLAIN ANALYZE SELECT * FROM test WHERE t LIKE '%sole%';
                                QUERY PLAN                                
--------------------------------------------------------------------------------------------------------------------
 Bitmap Heap Scan on test  (cost=20.00..24.01 rows=1 width=33) (actual time=0.027..0.027 rows=1 loops=1)
   Recheck Cond: (t ~~ '%sole%'::text)
   Heap Blocks: exact=1
   ->  Bitmap Index Scan on test_idx02  (cost=0.00..20.00 rows=1 width=0) (actual time=0.023..0.023 rows=1 loops=1)
         Index Cond: (t ~~ '%sole%'::text)
 Planning Time: 0.113 ms
 Execution Time: 0.041 ms

Creando un indice GIN (Generalized Inverted Index) con l'operatore gin_trgm_ops fornito dall'estensione pg_trgm la ricerca di una parola nel testo utilizza l'indice e sara' molto piu' efficiente.

E' possibile in alternativa utilizzare un indice GiST (Generalized Search Tree):

CREATE INDEX test_idx03 ON test USING GIST (t gist_trgm_ops); 
EXPLAIN SELECT * FROM test WHERE t LIKE '%sole%';
------------------------------------------------------------------------
 Index Scan using test_idx03 on test  (cost=0.14..8.16 rows=1 width=33)
   Index Cond: (t ~~ '%sole%'::text)

In questo caso viene usato un Index Scan che risulta anch'esso efficiente.

Conclusione (parziale): utilizzando l'estensione pg_trgm tutte le ricerche LIKE possono essere eseguite in modo efficiente con indici GIN e GiST.

Text search

Lasciate ogne speranza, voi ch'intrate

Fino ad ora abbiamo eseguito semplici ricerche di stringhe ma in realta' Postgres puo' fare molto di piu'. Se vi accontentate di far eseguire velocemente una query con la LIKE potete fermarvi qui; altrimenti potete proseguire... ma vi ho avvertiti, questa e' la parte piu' difficile!

Riprendiamo il nostro esempio creando un indice sfruttando la funzione to_tsvector():

CREATE INDEX test_idx04 ON test USING gin (to_tsvector('italian', t)); -- CREATE INDEX test_idx05 ON test USING gist (to_tsvector('italian', t)); explain select t from test where to_tsvector('italian', t) @@ to_tsquery('italian', 'sole'); 
                                    QUERY PLAN                                    
----------------------------------------------------------------------------------
 Bitmap Heap Scan on test  (cost=8.06..22.75 rows=8 width=33)
   Recheck Cond: (to_tsvector('italian'::regconfig, t) @@ '''sol'''::tsquery)
   ->  Bitmap Index Scan on test_idx04  (cost=0.00..8.06 rows=8 width=0)
         Index Cond: (to_tsvector('italian'::regconfig, t) @@ '''sol'''::tsquery)

Anche in questo caso la ricerca funziona per indice ed e' quindi efficiente con tabelle di grandi dimensioni. Pero' la ricerca e' stata eseguita con l'operatore @@ e con alcune speciali funzioni.

In precedenza abbiamo utilizzato la LIKE che consente ricerche piuttosto semplici. La nuova query che abbiamo utilizzato e' piu' complicata e restituisce lo stesso risultato, perche' utilizzarla?
In realta' i tipi di ricerca testuale possono essere molto piu' complessi: si puo' cercare in un testo la presenza di piu' parole, la posizione reciproca, l'assenza di alcuni termini, puo' essere utile poter indicare dove in un testo abbiamo trovato una corrispondenza; spesso e' necessario ordinare i risultati per importanza; la ricerca deve avvenire tenendo conto che alcune parole possono essere al plurale, al singolare, al maschile, al femminile, in maiuscolo, in minuscolo, con character set diversi, che i verbi possono essere coniugati, e che esistono importanti differenze tra le lingue e linguaggi disponibili.
Per disporre di tutte queste possibilita' e' necessario qualcosa di leggermente piu' complicato delle semplici LIKE/ILIKE.

Per comprendere meglio le possibilita' del text search in Postgres dobbiamo vedere le funzioni to_tsvector() e to_tsquery(). Iniziamo da to_tsvector():

select to_tsvector('Nel mezzo del cammin di nostra vita'); to_tsvector ----------------------------------------------------------------- 'cammin':4 'del':3 'di':5 'mezzo':2 'nel':1 'nostra':6 'vita':7 select to_tsvector('italian', 'Nel mezzo del cammin di nostra vita'); to_tsvector ----------------------------- 'cammin':4 'mezz':2 'vit':7

Con la prima selezione abbiamo trasformato un testo in un vettore. Il risultato e' un vettore ordinato con la lista delle posizioni.
Nella seconda selezione abbiamo indicato che la lingua da utilizzare e' l'italiano: di conseguenza sono state eliminate le preposizioni e le parole sono riportate senza desinenza perche' in italiano puo' cambiare a seconda dei casi [NdA il termine corretto per indicare "parole senza desinenza" e' lessema].

La funzione to_tsquery() consente di definire le query testuali e consente di utilizzare come operatori & (AND), | (OR), ! (NOT), <-> (FOLLOWED BY), <N> (FOLLOWED BY a distanza I). Inoltre e' possibile utilizzare le parentesi per trattare condizioni complesse.

Ora che conosciamo le funzioni da utilizzare vediamo qualche esempio:

-- Ricerca di due parole select * from test where to_tsvector('italian', t) @@ to_tsquery('italian', 'sole & stella'); -- Ricerca in forma semplificata (non conosce l'italiano e quindi stella != stelle) select * from test where t @@ 'sole & stelle'; -- Statistica lessemi SELECT * FROM ts_stat('SELECT to_tsvector(''italian'', t) FROM test') ORDER BY nentry DESC, ndoc DESC, word LIMIT 10;

Tutto qui?

Non e' tutto qui!

Le funzioni di text search sono molte ed hanno molte piu' opzioni di quelle descritte fino ad ora. Molto utili sono ad esempio le funzioni ts_rank() per ordinare i risultati delle ricerche come avviene, ad esempio, su un motore di ricerca e ts_headline() che consente di evidenziare la parte del testo su cui e' stato trovato il match. Tra le funzionalita' avanzate vi e' la possibilita' di configurare parser e dictionary.

Dal punto di vista prestazionale ogni caso puo' essere diverso ed e' quindi importante analizzare le diverse alternative. Gli strumenti di base sono sempre gli stessi: misurare i tempi di risposta ed analizzare i piani di esecuzione con EXPLAIN o EXPLAIN ANALYZE.
Utile e' anche controllare la dimensione degli indici.
A volte puo' essere utile modificare la struttura delle tabelle, precalcolare to_tsvector(), concatenare stringhe, ...

Le differenze tecniche tra i due tipi di indici GIN e GiST sono importanti. Un indice GIN e' un inverted index quindi contiene ogni parola ed una lista delle righe in cui e' contenuta.
Un indice GiST utilizza una funzione di hash per mappare le parole su una signature. Quando si verificano collisioni due parole sono mappate sullo stesso bit e quindi possono verificarsi falsi positivi che debbono essere verificati accedendo alla heap. Di converso pero' gli indici GiST sono piu' veloci da mantenere ed occupano meno spazio.

La scelta tra i due tipi di indice non e' facile e, anche se generalmente si preferiscono gli indici GIN per il text search su tabelle di grandi dimensioni e modificate di rado, sicuramente vale la pena di effettuare qualche benchmark con dati reali per scegliere l'alternativa migliore.

La dimensione della signature di un indice GiST e' configurabile con gist_trgm_ops (siglen='256'). Il default di siglen e' 124, il massimo 1024. Aumentando la dimensione della signature diminuisce la probabilita' delle collisioni ma aumenta la dimensione dell'indice. Un indice GiST puo' utilizzare la clausola INCLUDING e quindi essere usato come covering index.
I tempi di creazione di un indice GIN possono essere migliorati incrementando il parametro maintenance_work_mem.

Questo vale gia' per gli indici B-Tree ma e' ancora piu' importante per gli indici GIN e GiST: quando vengono eseguiti pesanti caricamenti tipicamente e' meglio cancellare l'indice all'inizio del batch e ricrearlo al termine.

Varie ed eventuali

In questa paginetta sono stati riportati semplici esempi di ricerche di stringhe cercando di renderle efficienti... e poi abbiamo dato un veloce sguardo al grande mondo delle ricerche testuale.
Maggiori informazioni si trovano ovviamente sulla documentazione ufficiale: LIKE, text search, indici text search, trigrammi, indici GIN, indici GiST, ...

Oltre alla LIKE in Postgres sono disponibili anche le ricerche di espressioni regolari con SIMILAR TO e l'operatore ~ (POSIX). Tecnicamente si tratta di pattern matching e non di text search... quindi non li abbiamo trattati in questa pagina.

Titolo: Text Search in PostgreSQL
Livello: Avanzato (3/5)
Data: 14 Febbraio 2021 ❤️
Versione: 1.0.1 - 1 Aprile 2023
Autore: mail [AT] meo.bogliolo.name