Periodicamente si presenta la necessità di cercare dati correlati utilizzando un insieme di chiavi, fino a raggiungere il numero totale necessario di registrazioni.
Un esempio molto "concreto" è ottenere le 20 attività più datate, presenti nella lista dei dipendenti (ad esempio, all'interno di un singolo dipartimento). Per vari "dashboard" manageriali con sintesi brevi sulle aree di lavoro, una tematica simile è richiesta abbastanza frequentemente.
In questo articolo esamineremo l'implementazione in PostgreSQL di una soluzione "naïve", un algoritmo "più intelligente" e uno completamente complesso di un "ciclo" in SQL con una condizione di uscita dai dati trovati, che potrebbe essere utile sia per la crescita personale che per l'applicazione in altri casi simili.
Prenderemo un set di dati di prova da . Per evitare che le registrazioni visualizzate "saltino" di volta in volta in caso di valori ordinati coincidenti, amplieremo l'indice oggetto aggiungendo la chiave primaria. In questo modo, ne garantirà l'unicità e garantirà l'ordine di ordinamento:
CREATE INDEX ON task(owner_id, task_date, id);
-- e cancelleremo quello vecchio
DROP INDEX task_owner_id_task_date_idx;Come si sente, così si scrive
Iniziamo a scrivere la versione più semplice della query, passando gli ID dei membri del team :
SELECT
*
FROM
task
WHERE
owner_id = ANY('{1,2,4,8,16,32,64,128,256,512}'::integer[])
ORDER BY
task_date, id
LIMIT 20; 
È un po' triste: abbiamo richiesto solo 20 registrazioni, ma l'Index Scan ci ha restituito 960 righe, che abbiamo anche dovuto ordinare... Proviamo a leggere meno.
unnest + ARRAY
La prima considerazione che ci aiuterà è che, se ci servono solo 20 registrazioni ordinate, è sufficiente leggere non più di 20 registrazioni ordinate negli stessi termini per ciascuna chiave. Dopotutto, abbiamo un indice adatto (owner_id, task_date, id).
Useremo lo stesso meccanismo di estrazione e "distribuzione in colonne" di una registrazione intera della tabella, come in . Inoltre, applicheremo una riduzione in array utilizzando la funzione ARRAY():
WITH T AS (
SELECT
unnest(ARRAY(
SELECT
t
FROM
task t
WHERE
owner_id = unnest
ORDER BY
task_date, id
LIMIT 20 -- limitiamo qui...
)) r
FROM
unnest('{1,2,4,8,16,32,64,128,256,512}'::integer[])
)
SELECT
(r).*
FROM
T
ORDER BY
(r).task_date, (r).id
LIMIT 20; -- ... e qui - anch'esso 
Oh, è già molto meglio! 40% più veloce, e 4.5 volte meno dati abbiamo dovuto leggere.
La materializzazione delle registrazioni delle tabelle tramite CTEVoglio sottolineare che in alcuni casi il tentativo di lavorare immediatamente con i campi di registrazione dopo la loro ricerca in una subquery, senza "racchiuderli" in un CTE, può portare a una "moltiplicazione" di InitPlan proporzionale al numero di questi campi:
SELECT
((
SELECT
t
FROM
task t
WHERE
owner_id = 1
ORDER BY
task_date, id
LIMIT 1
).*);Risultato (costo=4.77..4.78 righe=1 larghezza=16) (tempo effettivo=0.063..0.063 righe=1 cicli=1)
Buffer: colpiti in comune=16
InitPlan 1 (restituisce $0)
-> Limit (costo=0.42..1.19 righe=1 larghezza=48) (tempo effettivo=0.031..0.032 righe=1 cicli=1)
Buffer: colpiti in comune=4
-> Scansione Indice usando task_owner_id_task_date_id_idx su task t (costo=0.42..387.57 righe=500 larghezza=48) (tempo effettivo=0.030..0.030 righe=1 cicli=1)
Condizione Indice: (owner_id = 1)
Buffer: colpiti in comune=4
InitPlan 2 (restituisce $1)
-> Limit (costo=0.42..1.19 righe=1 larghezza=48) (tempo effettivo=0.008..0.009 righe=1 cicli=1)
Buffer: colpiti in comune=4
-> Scansione Indice usando task_owner_id_task_date_id_idx su task t_1 (costo=0.42..387.57 righe=500 larghezza=48) (tempo effettivo=0.008..0.008 righe=1 cicli=1)
Condizione Indice: (owner_id = 1)
Buffer: colpiti in comune=4
InitPlan 3 (restituisce $2)
-> Limit (costo=0.42..1.19 righe=1 larghezza=48) (tempo effettivo=0.008..0.008 righe=1 cicli=1)
Buffer: colpiti in comune=4
-> Scansione Indice usando task_owner_id_task_date_id_idx su task t_2 (costo=0.42..387.57 righe=500 larghezza=48) (tempo effettivo=0.008..0.008 righe=1 cicli=1)
Condizione Indice: (owner_id = 1)
Buffer: colpiti in comune=4"
InitPlan 4 (restituisce $3)
-> Limit (costo=0.42..1.19 righe=1 larghezza=48) (tempo effettivo=0.009..0.009 righe=1 cicli=1)
Buffer: colpiti in comune=4
-> Scansione Indice usando task_owner_id_task_date_id_idx su task t_3 (costo=0.42..387.57 righe=500 larghezza=48) (tempo effettivo=0.009..0.009 righe=1 cicli=1)
Condizione Indice: (owner_id = 1)
Buffer: colpiti in comune=4
La stessa registrazione è stata "cercata" 4 volte… Fino a PostgreSQL 11 questo comportamento si verifica regolarmente, e la soluzione è "racchiudere" in CTE, che rappresenta un confine indiscutibile per l'ottimizzatore in queste versioni.
Accumulatore ricorsivo
Nella versione precedente abbiamo letto complessivamente 200 righe per ottenere le necessarie 20. Non più 960, ma ancora meno — è possibile?
Proviamo a sfruttare la conoscenza che ci servono solo 20 registrazioni. Quindi itereremo la lettura dei dati solo fino a raggiungere il numero che ci interessa.
Passo 1: lista iniziale
È evidente che la nostra lista "target" di 20 registrazioni deve iniziare con le "prime" registrazioni per uno dei nostri key owner_id. Pertanto, prima troviamo tali "primi" per ciascuna delle chiavi e li inseriamo nella lista, ordinandoli secondo l'ordine desiderato — (task_date, id).
Passo 2: troviamo le "successive" registrazioni
Ora, se prendiamo la prima registrazione dalla nostra lista e iniziamo a "procedere" ulteriormente secondo l'indice preservando la chiave owner_id, tutte le registrazioni trovate saranno proprio le successive nella selezione risultante. Certamente, solo fino a quando non incrociamo la chiave applicativa seconda voce nell'elenco.
Se è successo che abbiamo "incrociato" la seconda voce, allora l'ultima voce letta deve essere aggiunta all'elenco al posto della prima (con lo stesso owner_id), dopo di che l'elenco viene riordinato di nuovo.
Cioè abbiamo sempre la situazione in cui nell'elenco c'è al massimo una voce per ciascuna delle chiavi (se le voci sono terminate e non abbiamo "incrociato", allora la prima voce semplicemente scompare dall'elenco e non viene aggiunta nulla), e queste sono sempre ordinate in ordine crescente della chiave applicativa (task_date, id).
Passo 3: filtriamo e "espandiamo" le voci
In alcune righe della nostra selezione ricorsiva alcune voci rv si duplicano - prima troviamo quelle come "che incrociano il confine della 2ª voce dell'elenco", e poi le inseriamo come 1ª dell'elenco. Quindi la prima apparizione deve essere filtrata.
Richiesta finale terribile
CON WITH RECURSIVE T AS (
-- #1: inseriamo nel elenco le "prime" registrazioni per ciascuna delle chiavi del set
CON wrap AS ( -- "materializziamo" le registrazioni in modo che l'accesso ai campi non generi un moltiplicarsi di InitPlan/SubPlan
CON T AS (
SELECT
(
SELECT
r
FROM
task r
WHERE
owner_id = unnest
ORDER BY
task_date, id
LIMIT 1
) r
FROM
unnest('{1,2,4,8,16,32,64,128,256,512}'::integer[])
)
SELECT
array_agg(r ORDER BY (r).task_date, (r).id) list -- ordiniamo l'elenco nell'ordine richiesto
FROM
T
)
SELECT
list
, list[1] rv
, FALSE not_cross
, 0 size
FROM
wrap
UNION ALL
-- #2: leggiamo le registrazioni della prima chiave fino a quando non superiamo quella della seconda
SELECT
CASE
-- se nulla è stato trovato per la chiave della prima registrazione
WHEN X._r IS NOT DISTINCT FROM NULL THEN
T.list[2:] -- rimuoviamo dal elenco
-- se NON abbiamo incrociato la chiave applicativa della seconda registrazione
WHEN X.not_cross THEN
T.list -- semplicemente continuiamo con lo stesso elenco senza modifiche
-- se non c'è già la seconda registrazione nell'elenco
WHEN T.list[2] IS NULL THEN
-- restituiamo semplicemente un elenco vuoto
'{}'
-- riordiniamo il dizionario rimuovendo la prima registrazione e aggiungendo l'ultima trovata
ELSE (
SELECT
coalesce(T.list[2] || array_agg(r ORDER BY (r).task_date, (r).id), '{}')
FROM
unnest(T.list[3:] || X._r) r
)
END
, X._r
, X.not_cross
, T.size + X.not_cross::integer
FROM
T
, LATERAL(
CON wrap AS ( -- "materializziamo" la registrazione
SELECT
CASE
-- se abbiamo "superato" davvero la seconda registrazione
WHEN NOT T.not_cross
-- quindi la registrazione necessaria è la prima dell'elenco
THEN T.list[1]
ELSE ( -- se non abbiamo incrociato, la chiave è rimasta come nell'ultima registrazione - ci basiamo su di essa
SELECT
_r
FROM
task _r
WHERE
owner_id = (rv).owner_id AND
(task_date, id) > ((rv).task_date, (rv).id)
ORDER BY
task_date, id
LIMIT 1
)
END _r
)
SELECT
_r
, CASE
-- se la seconda registrazione non è già presente nell'elenco, ma abbiamo trovato qualcosa
WHEN list[2] IS NULL AND _r IS DISTINCT FROM NULL THEN
TRUE
ELSE -- non abbiamo trovato nulla o abbiamo "superato"
coalesce(((_r).task_date, (_r).id) < ((list[2]).task_date, (list[2]).id), FALSE)
END not_cross
FROM
wrap
) X
WHERE
T.size < 20 AND -- limitiamo qui il numero
T.list IS DISTINCT FROM '{}' -- o finché l'elenco non è esaurito
)
-- #3: "espandiamo" le registrazioni - l'ordine è garantito dalla costruzione
SELECT
(rv).*
FROM
T
WHERE
not_cross; -- prendiamo solo le registrazioni "non incrociate" 
Pertanto, noi abbiamo scambiato il 50% delle letture dei dati per il 20% del tempo di esecuzioneCioè, se hai motivi per ritenere che la lettura possa essere lunga (ad esempio, se i dati non sono frequentemente memorizzati nella cache e bisogna recuperarli dal disco), allora puoi dipendere meno dalla lettura in questo modo.
In ogni caso, il tempo di esecuzione è stato migliore rispetto alla prima versione "naïve". Ma quale di queste 3 opzioni utilizzare — sta a te decidere.
Fonte: habr.com
