🥇PostgreSQL Antipatterns: una storia sull'iterativa revisione della ricerca per nome, o "Ottimizzazione avanti e indietro"

Migliaia di manager degli uffici vendite in tutto il paese registrano in il nostro sistema CRM decine di migliaia di contatti ogni giorno — fatti di interazione con potenziali clienti o clienti già attivi. E per trovare questo cliente è necessario prima fare una ricerca e, se possibile, molto rapidamente. Questo avviene più spesso per nome.

Non sorprende quindi che, analizzando ancora una volta le "query pesanti" su uno dei nostri database più sollecitati — il nostro account aziendale di SBIS, ho scoperto al primo posto una query per la "ricerca rapida" per nome per le schede delle organizzazioni.

Inoltre, ulteriori indagini hanno rivelato un esempio interessante inizialmente di ottimizzazione, e poi di degrado delle prestazioni della query con successive migliorie svolte da diverse squadre, ognuna delle quali ha agito esclusivamente per le migliori intenzioni.

0: cosa voleva l'utente

[KДПВ da qui]

Cosa intende generalmente l'utente quando parla di "ricerca rapida" per nome? Quasi mai si tratta di una "vera" ricerca per sottostringa tipo ... LIKE '%rosa%' — perché in questo caso nei risultati rientrerebbero non solo 'Rosalia' e 'Negozio Rosa', ma anche 'Grosa' e persino 'Casa dello Zio Morosa'.

L'utente presuppone a livello pratico che gli si offra una ricerca per l'inizio della parola nel titolo e che ciò che inizia con ciò che è stato inserito. E lo farete praticamente istantaneamente — con l'inserimento parziale.

1: restrizioni sul compito

E tanto meno l'utente inserirà intenzionalmente 'ros negozio', affinché ogni parola debba essere cercata come prefisso. No, per l'utente è molto più facile rispondere a un suggerimento rapido per l'ultima parola piuttosto che intenzionalmente "non completare" le precedenti — guardate come funziona in qualsiasi motore di ricerca.

In generale, correttamente formulare i requisiti del compito è più della metà della soluzione. A volte, un'analisi attenta del caso d'uso può influire notevolmente sul risultato.

Cosa fa quindi uno sviluppatore astratto?

1.0: motore di ricerca esterno

Oh, la ricerca è complicata, non ho voglia di occuparmene — diamolo ai devops! Facciamoli configurare un sistema di ricerca esterno rispetto al DB: Sphinx, ElasticSearch,…

Una variante lavorativa, sebbene dispendiosa in termini di sincronizzazione e tempestività delle modifiche. Ma non nel nostro caso, poiché la ricerca viene effettuata per ciascun cliente esclusivamente all'interno dei dati del suo account. E i dati presentano una variabilità piuttosto elevata — e se adesso il manager ha inserito una scheda 'Negozio Rosa', dopo 5-10 secondi potrebbe già ricordarsi di non aver indicato l'email e volerla trovare e correggere.

Quindi — vediamo di cercare "direttamente nel database". Per fortuna, PostgreSQL ci consente di farlo e non solo con un'opzione — le esamineremo.

1.1: "sottostringa onesta"

Afferriamo la parola "sottostringa". Infatti, esiste un'ottima modulo pg_trgm! Solo dopo dovremo ordinare correttamente.

Proviamo a prendere per semplificare un modello di tabella:

CREATE TABLE firms(
  id
    serial
      PRIMARY KEY
, name
    text
);

Carichiamo lì 7.8 milioni di record di organizzazioni reali e indicizziamo:

CREATE EXTENSION pg_trgm;
CREATE INDEX ON firms USING gin(lower(name) gin_trgm_ops);

Cerchiamo le prime 10 voci per la ricerca di sottostringhe:

SELECT
  *
FROM
  firms
WHERE
  lower(name) ~ ('(^|s)' || 'rosa')
ORDER BY
  lower(name) ~ ('^' || 'rosa') DESC -- prima "che iniziano con"
, lower(name) -- il resto in ordine alfabetico
LIMIT 10;

[guarda su explain.tensor.ru]

Beh, così così… 26ms, 31MB di dati letti e oltre 1.7K di record filtrati — per 10 ricercati. Le spese generali sono troppo elevate, non si può fare in modo più efficiente?

1.2: ricerca per testo? è FTS!

Infatti, PostgreSQL offre un potente meccanismo di ricerca testuale completo (Full Text Search), compresa la possibilità di ricerca per prefissi. Ottima opzione, non è nemmeno necessario installare estensioni! Proviamo:

CREATE INDEX ON firms USING gin(to_tsvector('simple'::regconfig, lower(name)));

SELECT
  *
FROM
  firms
WHERE
  to_tsvector('simple'::regconfig, lower(name)) @@ to_tsquery('simple', 'rosa:*')
ORDER BY
  lower(name) ~ ('^' || 'rosa') DESC
, lower(name)
LIMIT 10;

[guarda su explain.tensor.ru]

Qui ci ha aiutato un po' la parallelizzazione nell'esecuzione della query, riducendo il tempo della metà a 11ms. E ci siamo dovuti leggere 1.5 volte di meno — solo 20MB. E meno leggiamo, meglio è, perché maggiore è il volume che leggiamo, maggiori sono le possibilità di ricevere un cache miss, e ogni pagina di dati letta in più dal disco è un potenziale "freno" per la query.

1.3: eppure LIKE?

Tutta la query precedente è buona, ma se la eseguiamo cento mila volte al giorno, si accumuleranno già 2TB dati letti. Nel migliore dei casi — dalla memoria, ma se va male, anche dal disco. Quindi proviamo a ridurlo.

Ricordiamo che l'utente vuole vedere prima "quelli che iniziano con ...". Ma questo è puro ricerca per prefisso utilizzando text_pattern_ops! E solo se non abbiamo "sufficienti" fino a 10 record cercati, dovremo recuperarli tramite la ricerca FTS:

CREATE INDEX ON firms(lower(name) text_pattern_ops);

SELECT
  *
FROM
  firms
WHERE
  lower(name) LIKE ('rosa' || '%')
LIMIT 10;

[guarda su explain.tensor.ru]

Ottimi risultati — solo 0.05ms e poco più di 100KB letto! Solo che ci siamo dimenticati l'ordinamento per nome, affinché l'utente non si perda nei risultati:

SELECT
  *
FROM
  firms
WHERE
  lower(name) LIKE ('rosa' || '%')
ORDER BY
  lower(name)
LIMIT 10;

[guarda su explain.tensor.ru]

Oh, già, non è così bello — sembra ci sia un indice, ma l'ordinamento non lo considera… Certo, è già di gran lunga più efficiente rispetto alla precedente opzione, però…

1.4: "rifinire con la lima"

Ma esiste un indice che permette di cercare per intervallo e usare l'ordinamento in modo corretto — btree normale!

CREATE INDEX ON firms(lower(name));

Solo che la query per questo dovremo "assemblare manualmente":

SELECT
  *
FROM
  firms
WHERE
  lower(name) >= 'rosa' AND
  lower(name) <= ('rosa' || chr(65535)) -- per UTF8, per codifiche a byte singolo - chr(255)
ORDER BY
   lower(name)
LIMIT 10;

[guarda su explain.tensor.ru]

Ottimo — l'ordinamento funziona e il consumo di risorse è rimasto "microscopico", migliaia di volte più efficiente rispetto al "puro" FTS! Resta da raccogliere in un'unica query:

(
  SELECT
    *
  FROM
    firms
  WHERE
    lower(name) >= 'rosa' AND
    lower(name) <= ('rosa' || chr(65535)) -- per UTF8, per codifiche a byte singolo - chr(255)
  ORDER BY
     lower(name)
  LIMIT 10
)
UNION ALL
(
  SELECT
    *
  FROM
    firms
  WHERE
    to_tsvector('simple'::regconfig, lower(name)) @@ to_tsquery('simple', 'rosa:*') AND
    lower(name) NOT LIKE ('rosa' || '%') -- "quelli che iniziano con" li abbiamo già trovati sopra
  ORDER BY
    lower(name) ~ ('^' || 'rosa') DESC -- usiamo lo stesso ordinamento, per NON passare per l'indice btree
  , lower(name)
  LIMIT 10
)
LIMIT 10;

Nota che il secondo sotto-query viene eseguito solo se la prima ha restituito meno di quanto atteso ultimo LIMIT numero di righe. Ho già scritto su questo metodo di ottimizzazione delle query in precedenza.

Sì, ora abbiamo sia btree che gin sulla tabella, però statisticamente si è visto che meno del 10% delle query raggiunge l'esecuzione del secondo blocco.Cioè, con tali vincoli tipici già noti per il problema, siamo riusciti a ridurre complessivamente il consumo di risorse del server praticamente di migliaia di volte!

1.5*: faremo senza lima

Sopra LIKE ci ha impedito di utilizzare un'ordinazione errata. Ma può essere 'riedirizzata' nella giusta via utilizzando l'operatore USING:

Per impostazione predefinita si intende ASC. Inoltre, è possibile specificare il nome di un operatore di ordinamento specifico nella clausola USING. L'operatore di ordinamento deve essere un membro di 'minore' o 'maggiore' di alcune famiglie di operatori B-tree. ASC di solito è equivalente a USING < e DESC di solito è equivalente a USING >.

Nel nostro caso 'minore' è ~<~:

SELECT
  *
FROM
  firms
WHERE
  lower(name) LIKE ('rosa' || '%')
ORDER BY
  lower(name) USING ~<~
LIMIT 10;

[guarda su explain.tensor.ru]

2: come 'inacidiscono' le query

Ora lasciamo la nostra query 'maturare' per sei mesi-un anno, e con sorpresa la scopriamo di nuovo 'in cima' con indicatori del totale giornaliero di 'sfruttamento' della memoria (buffers shared hit) a 5.5TB — cioè ancora di più rispetto a quanto inizialmente.

No, certo, e il nostro business è cresciuto, e il carico è aumentato, ma non in questo modo! Dunque, c'è qualcosa di strano — indaghiamo.

2.1: nascita del paging

A un certo punto, un altro team di sviluppatori ha voluto creare la possibilità di 'saltare' dalla ricerca rapida a vista nel registro con gli stessi, ma risultati amplificati. E quale registro senza navigazione paginata? Colleghiamoci!

( ... LIMIT  + 10)
UNION ALL
( ... LIMIT  + 10)
LIMIT 10 OFFSET ;

Ora era possibile mostrare senza problemi al programmatore il registro dei risultati della ricerca con un caricamento 'tipo paginato'.

Certo, in realtà, per ogni pagina successiva di dati vengono letti sempre più e più (tutto quello che abbiamo scartato dall'ultima volta, più il 'seghetto' necessario) — quindi questo è un evidente antipattern. E sarebbe stato più corretto far partire la ricerca alla successiva iterazione dall'ultima chiave memorizzata nell'interfaccia, ma di questo parleremo un'altra volta.

2.2: voglia di esotismo

A un certo punto, al programmatore è venuta voglia di variegare il campione di risultati con dati da un'altra tabella, per la quale l'intera query precedente è stata inviata in CTE:

WITH q AS (
  ...
  LIMIT  + 10
)
SELECT
  *
, (SELECT ...) sub_query -- una certa query a una tabella correlata
FROM
  q
LIMIT 10 OFFSET ;

E anche così — non male, poiché la query annidata viene calcolata solo per 10 record restituiti, se non fosse per…

2.3: DISTINCT senza senso e spietato

Da qualche parte nel corso di questa evoluzione, dal 2° sottocomando è andato perso NOT LIKE condizione. È chiaro che dopo questo UNION ALL ha iniziato a restituire alcuni record due volte — prima quelli trovati all'inizio della stringa, e poi ancora una volta — all'inizio della prima parola di questa stringa. In teoria, tutti i record della seconda sottoquery potrebbero coincidere con i record della prima.

Cosa fa lo sviluppatore invece di cercare la causa?.. Nessuna domanda!

dobliamo la dimensione dei campioni originali
applichiamo DISTINCT, in modo da ottenere solo singole occorrenze di ciascuna stringa

WITH q AS (
  ( ... LIMIT  + 10)
  UNION ALL
  ( ... LIMIT  + 10)
  LIMIT  + 10
)
SELECT DISTINCT
  *
, (SELECT ...) sub_query
FROM
  q
LIMIT 10 OFFSET ;

Quindi è chiaro che il risultato, alla fine, è esattamente lo stesso, ma la probabilità di "saltare" nella seconda sottoquery CTE è aumentata significativamente, e non solo per questo, si legge chiaramente di più.

Ma questo non è il dramma. Poiché lo sviluppatore ha chiesto di selezionare DISTINCT non per specifici, ma per tutti i campi i record, quindi è stato automaticamente incluso anche il campo sub_query — il risultato della sottoquery. Ora, per eseguire DISTINCT, il database ha dovuto eseguire già non 10 sottoquery, ma tutto + 10!

2.4: la cooperazione è tutto!

Ecco com'erano gli sviluppatori — non si preoccupavano, perché nel registro per "sistemare" a valori sostanziali N, con un rallentamento cronico nella ricezione di ogni "pagina" successiva, chiaramente mancava la pazienza.

Finché non sono arrivati gli sviluppatori di un altro reparto, e hanno voluto sfruttare un metodo così comodo per la ricerca iterativa — cioè prendiamo un pezzo da un campione, filtrando in base a condizioni aggiuntive, visualizziamo il risultato, poi il pezzo successivo (che nel nostro caso si ottiene aumentando N), e così via fino a riempire lo schermo.

In generale, nell'esemplare catturato N ha raggiunto valori di quasi 17K, e in un solo giorno sono state eseguite "in catena" non meno di 4K di tali richieste. Le ultime di esse scansionavano già circa 1GB di memoria ad ogni iterazione…