🥇PostgreSQL Antipatterns: una storia sull'ottimizzazione iterativa della ricerca per nome, o "Ottimizzazione su e giù"

Migliaia di manager degli uffici vendite in tutto il paese registrano in il nostro sistema CRM decine di migliaia di contatti ogni giorno — eventi di comunicazione con potenziali o già clienti attivi. E per trovare questo cliente, bisogna farlo rapidamente. E questo avviene, per lo più, per titolo.

Pertanto, non sorprende che, analizzando per l'ennesima volta le richieste "pesanti" su uno dei database più sovraccarichi — il nostro account aziendale di SBIS , ho trovato al "top"una richiesta per la ricerca "rapida" per titolo per le schede delle organizzazioni. Inoltre, ulteriori indagini hanno rivelato un esempio interessante

inizialmente di ottimizzazione, e poi di degrado delle prestazioni della richiesta durante le sue continue revisioni da parte di più team, ognuno dei quali agiva esclusivamente con le migliori intenzioni. 0: cosa voleva l'utente

[КДПВ

[КДПВ da qui]

Cosa intende solitamente un utente quando parla di ricerca 'rapida' per titolo? Raramente si tratta di una ricerca 'onesta' per sottostringa tipo ... LIKE '%rosa%' — poiché in questo caso non si ottengono solo 'Rosalia' e 'Negozio Rosa', ma anche 'Grosa' e persino 'Casa di Nonno Morosa'.

L'utente presuppone a livello pratico che voi garantiate una ricerca all'inizio della parola nel titolo e mostrerete come più rilevanti quelli che iniziano con ciò che è stato inserito. E lo farete praticamente in tempo reale — all'inserimento della sottostringa.

1: limitiamo il compito

E tanto meno un utente digiterebbe appositamente 'rosa negozio', affinché ogni parola richieda una ricerca per prefisso. No, è molto più semplice per l'utente reagire al suggerimento veloce per l'ultima parola piuttosto che 'non inserire' intenzionalmente le precedenti — guardate come funziona per qualsiasi motore di ricerca.

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

Cosa fa quindi un sviluppatore astratto?

1.0: motore di ricerca esterno

Oh, la ricerca è difficile, non ho voglia di affrontarla — scegliamo di affidarla ai devops! Facciamo in modo che ci configurino un sistema di ricerca esterno basato su database: Sphinx, ElasticSearch,…

Una soluzione lavorativa, anche se laboriosa in termini di sincronizzazione e tempestività delle modifiche. Ma non è il nostro caso, poiché la ricerca viene effettuata per ciascun cliente solo nel contesto dei dati del suo account. E i dati possono cambiare frequentemente — e se ora il manager ha aggiunto una scheda 'Negozio Rosa', dopo 5-10 secondi potrebbe ricordarsi di aver dimenticato di inserire l'email e volerla trovare e modificare.

Pertanto — vediamo come cercare "direttamente nel database". Fortunatamente, PostgreSQL ci consente di farlo, e non in un solo modo — esamineremo le varie opzioni.

1.1: "sottostringa onesta"

Atteniamoci alla parola "sottostringa". Infatti, esiste un ottimo modulo pg_trgm! Solo che è necessario ordinare correttamente i risultati.

Proviamo a prendere un semplice esempio con una tabella come questa:

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

Carichiamo lì 7,8 milioni di record di aziende reali e indicizziamo:

CREA ESTENSIONE pg_trgm;
CREA INDICE SU firms UTILIZZANDO gin(lower(name) gin_trgm_ops);

Cerchiamo le prime 10 registrazioni per la ricerca testuale:

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 registrazioni filtrate — per 10 cercati. I costi sono troppo elevati, non possiamo fare qualcosa di più efficiente?

1.2: ricerca di testo? Questo è FTS!

In effetti, PostgreSQL offre un meccanismo molto potente per la ricerca testuale completa (Full Text Search), inclusa la possibilità di ricerca prefissata. Ottima opzione, non è necessario installare estensioni! Proviamo:

CREA INDICE SU firms UTILIZZANDO 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 dell'esecuzione della query, riducendo il tempo a 11ms. E abbiamo anche dovuto leggere 1.5 volte meno — solo 20MB. Qui meno è meglio, dato che maggiore è il volume che leggiamo, maggiori sono le possibilità di ottenere un cache miss, e ogni pagina di dati letta in eccesso dal disco può rallentare la richiesta.

1.3: e comunque LIKE?

La richiesta precedente è buona, ma se la eseguiamo centomila volte al giorno, accumulerà già 2TB di dati letti. Nel migliore dei casi da memoria, ma se non siamo fortunati, anche dal disco. Quindi cerchiamo di renderla più piccola.

Ricordiamo che l'utente vuole vedere prima "che iniziano con ...". Ma questo è puramente ricerca prefissata utilizzando text_pattern_ops! E solo se non arriviamo a 10 record cercati, dovremo leggerli con la ricerca FTS:

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

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

[guarda su explain.tensor.ru]

Ottimi risultati — solo 0.05ms e poco più di 100KB letto! Solo che abbiamo dimenticato l'ordinamento per nome, così l'utente non si perde nei risultati:

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

[guarda su explain.tensor.ru]

Oh, qualcosa non va più così bene: sembra che ci sia un indice, ma l'ordinamento non lo considera... Certo, è già di gran lunga più efficiente rispetto alla versione precedente, ma...

1.4: «ottimizzare con attenzione»

Ma c'è un indice che permette sia la ricerca per intervallo sia un ordinamento corretto — un normale btree!

CREATE INDEX ON firms(lower(name));

Solo che la query dovrà essere costruita «a mano»:

SELECT
  *
FROM
  firms
WHERE
  lower(name) >= 'rondi' AND
  lower(name) <= ('rondi' || 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 resta «microscopico», mille volte più efficiente rispetto al «puro» FTS! Rimane solo da unire in un'unica query:

(
  SELECT
    *
  FROM
    firms
  WHERE
    lower(name) >= 'rondi' AND
    lower(name) <= ('rondi' || 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', 'rondi:*') AND
    lower(name) NOT LIKE ('rondi' || '%') -- quelli «che iniziano con» li abbiamo già trovati sopra
  ORDER BY
    lower(name) ~ ('^' || 'rondi') DESC -- usiamo lo stesso ordinamento per NON andare sull'indice btree
  , lower(name)
  LIMIT 10
)
LIMIT 10;

Nota che il secondo sottoquery viene eseguito solo se il primo ha restituito meno del previsto l'ultimo LIMIT il numero di righe. Di questo tipo di ottimizzazione delle query ne ho già parlato in precedenza.

Ebbene sì, ora abbiamo nella tabella sia btree che gin, ma statisticamente risulta che meno del 10% delle query arriva all'esecuzione del secondo blocco. Questo significa che, date queste tipiche limitazioni già note per il compito, siamo riusciti a ridurre il consumo totale di risorse del server praticamente di mille volte!

1.5*: ci accontenteremo senza limare

Sopra LIKE ci ha impedito di usare un'ordinazione errata. Ma possiamo 'metterla sulla retta via' specificando 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 appartenere alla famiglia 'minore' o 'maggiore' di alcuni operatori dell'albero B. ASC generalmente equivalente a USING < e DESC generalmente 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 'acidiscono' le query

Ora lasciamo la nostra richiesta «risposare» per sei mesi o un anno, e con stupore la ritroviamo di nuovo «in cima» con indicatori del «potenziamento» della memoria giornaliera totale (buffers shared hit) in 5.5TB — cioè ancora di più di quanto fosse inizialmente.

Certo, abbiamo visto crescere il nostro business e l’afflusso è aumentato, ma non così tanto! Significa che c'è qualcosa che non va – analizziamo la situazione.

2.1: nascita del paging

Ad un certo punto, un altro team di sviluppatori ha voluto dare la possibilità di «saltare» dalla ricerca rapida a sottolinea al registro con gli stessi, ma risultati espansi. E quale registro è completo senza la navigazione per pagina? Aggiungiamo questa funzionalità!

( ... LIMIT <N> + 10)
UNION ALL
( ... LIMIT <N> + 10)
LIMIT 10 OFFSET <N>;

Adesso era possibile mostrare senza problemi per lo sviluppatore il registro dei risultati di ricerca con il caricamento «tipo-paginale».

Certo, in realtà, per ogni pagina successiva di dati si legge sempre di più e di più. (tutti quelli della volta precedente, che elimineremo, più il necessario «codino») — questo è senza dubbio un antipattern. Sarebbe più corretto avviare la ricerca nella prossima iterazione dall'ultima chiave memorizzata nell'interfaccia, ma di questo parleremo un'altra volta.

2.2: voglia di esotismo

A un certo punto, lo sviluppatore ha sentito il desiderio di variare il risultato dell'output con dati da un'altra tabella, per cui l'intera query precedente è stata inviata in CTE:

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

E anche così — non è male, poiché la query nidificata viene calcolata solo per i 10 record restituiti, se non fosse per...

2.3: DISTINCT senza senso e spietato

Da qualche parte nel processo di questa evoluzione, nel 2° sottoquery si è perso NOT LIKE la condizione. È chiaro che dopo questo UNION ALL ha iniziato a restituire alcuni record due volte — prima trovati all’inizio della stringa, e poi di nuovo — all’inizio della prima parola di quella stringa. In ultima analisi, tutti i record del 2° sottoquery potrebbero corrispondere ai record del primo.

Cosa fa lo sviluppatore invece di cercare la causa?.. Nessun problema!

raddoppieremo la dimensione dei risultati originali
applicheremo DISTINCT, per ottenere solo istanze singole di ogni riga

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

Cioè, è chiaro che il risultato, in fin dei conti, è esattamente lo stesso, ma la possibilità di "saltare" nella 2ª sottoquery CTE è aumentata notevolmente, e non solo per questo, si legge chiaramente di più.

Ma questo non è il dramma peggiore. Poiché lo sviluppatore ha richiesto di selezionare DISTINCT non per specifici, ma subito per tutti i campi record, quindi qui è finito automaticamente anche il campo sub_query — il risultato della sottoquery. Adesso, per eseguire DISTINCT, il database ha dovuto eseguire già non 10 sottoquery, ma tutte + 10!

2.4: la cooperazione prima di tutto!

Così, gli sviluppatori vivevano — senza preoccuparsi, perché nel registro "aggiungere" a valori significativi N con un cronico rallentamento nell'ottenere ogni successiva "pagina" per l'utente chiaramente non bastava la pazienza.

Finché non sono arrivati gli sviluppatori di un altro reparto e hanno voluto utilizzare un metodo così conveniente per la ricerca iterativa — cioè prendiamo un pezzo da un campione, filtriamo in base a condizioni aggiuntive, disegniamo il risultato, poi il pezzo successivo (cosa 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 prossimi a 17K, e in totale, nelle ultime 24 ore, sono stati eseguiti "a catena" non meno di 4K di tali richieste. Gli ultimi di esse sono stati eseguiti senza esitazione già a 1GB di memoria a ogni iterazione…