Di tanto in tanto nasce la necessità di trovare dati correlati a un insieme di chiavi, finché non raggiungiamo il numero totale desiderato di record.
Un esempio "realistico" è estrarre le 20 richieste più vecchie, registrate nella lista dei dipendenti (ad esempio, all'interno di una singola divisione). Per vari "dashboard" gestionali con sintesi brevi su aree di lavoro, questo tema è abbastanza comune.
Nell'articolo esamineremo l'implementazione in PostgreSQL di una soluzione "naïve" per questo tipo di problema, un algoritmo "più intelligente" e uno più complesso un "ciclo" in SQL con una condizione di uscita basata sui dati trovati, che può essere utile sia per la crescita personale che per applicazioni in casi simili.
Prenderemo un insieme di dati di test da . Per evitare che i record visualizzati "saltino" da un'istanza all'altra in caso di valori di ordinamento uguali, estenderemo l'indice del soggetto aggiungendo la chiave primaria. Allo stesso modo, questo gli conferisce un'unicità, garantendoci un ordine di classificazione chiaro:
CREA UN INDICE SU task(owner_id, task_date, id);
-- e l'antico - lo eliminiamo
DROP INDEX task_owner_id_task_date_idx;Come si sente, così si scrive
Iniziamo a buttar giù la versione più semplice della query, passando gli ID degli esecutori :
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 ordinato solo 20 record, ma l'Index Scan ci ha restituito 960 righe, che poi abbiamo dovuto ordinare… Proviamo a leggere di meno.
unnest + ARRAY
La prima considerazione che ci aiuterà — se abbiamo bisogno di soli 20 record ordinati , basta leggere non più di 20 ordinati nello stesso ordine per ogni chiave. Per fortuna, abbiamo un indice adeguato (owner_id, task_date, id).
Utilizzeremo lo stesso meccanismo di estrazione e "trasformazione in colonne" del record completo della tabella, come in . E applicheremo anche la riduzione a un array usando 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 -- qui limitiamo...
)) 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 - anche 
Oh, molto meglio già! 40% più veloce e con 4.5 volte meno dati è stato necessario leggere.
Materializzazione delle righe della tabella tramite CTEVoglio sottolineare che in alcuni casi tentare di lavorare direttamente con i campi della riga dopo averla cercata in una sottoquery, senza 'incapsularla' in CTE, può portare a una 'duplicazione' dell'InitPlan proporzionalmente 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: hit condiviso=16
InitPlan 1 (restituisce $0)
-> Limite (costo=0.42..1.19 righe=1 larghezza=48) (tempo effettivo=0.031..0.032 righe=1 cicli=1)
Buffer: hit condiviso=4
-> Scansione indice utilizzando 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: hit condiviso=4
InitPlan 2 (restituisce $1)
-> Limite (costo=0.42..1.19 righe=1 larghezza=48) (tempo effettivo=0.008..0.009 righe=1 cicli=1)
Buffer: hit condiviso=4
-> Scansione indice utilizzando 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: hit condiviso=4
InitPlan 3 (restituisce $2)
-> Limite (costo=0.42..1.19 righe=1 larghezza=48) (tempo effettivo=0.008..0.008 righe=1 cicli=1)
Buffer: hit condiviso=4
-> Scansione indice utilizzando 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: hit condiviso=4"
InitPlan 4 (restituisce $3)
-> Limite (costo=0.42..1.19 righe=1 larghezza=48) (tempo effettivo=0.009..0.009 righe=1 cicli=1)
Buffer: hit condiviso=4
-> Scansione indice utilizzando 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: hit condiviso=4
La stessa registrazione è stata "ricercata" 4 volte... Fino a PostgreSQL 11, questo comportamento si verifica regolarmente, e la soluzione consiste nel "rimuovere" in CTE, che è un confine imprescindibile per l'ottimizzatore in queste versioni.
Accumulatore ricorsivo
Nella versione precedente, abbiamo letto in totale 200 righe per ottenere le necessarie 20. Non più 960, ma ancora meno — è possibile?
Proviamo a utilizzare la consapevolezza che abbiamo bisogno di solo 20 registrazioni. Cioè, itereremo la lettura dei dati solo fino a raggiungere il numero che ci serve.
Passo 1: lista iniziale
È ovvio che la nostra lista "obiettivo" di 20 registrazioni deve iniziare con le "prime" registrazioni in base a uno dei nostri owner_id-chiave. Quindi, prima troviamo quelle "prime" per ciascuna delle chiavi e le inseriamo in una lista, ordinandola nel modo desiderato — (task_date, id).
Passo 2: troviamo le "seguenti" registrazioni
Ora, se prendiamo la prima registrazione dalla nostra lista e iniziamo a "passare" oltre nell'indice mantenendo la chiave owner_id, tutte le registrazioni trovate sono proprio quelle successive nel campione finale. Certamente, solo finché non attraversiamo la chiave applicativa della seconda registrazione nella lista.
Se è successo che abbiamo "intersecato" la seconda registrazione, allora l'ultima registrazione letta deve essere aggiunta alla lista al posto della prima (con lo stesso owner_id), dopo di che la lista deve essere risistemata nuovamente.
Cioè, abbiamo sempre un massimo di una registrazione per ciascuna delle chiavi (se le registrazioni sono terminate e non abbiamo "intersecato", la prima registrazione semplicemente scomparirà dalla lista e non verrà aggiunta nulla), e queste sono sempre ordinate in ordine crescente in base alla chiave applicativa (task_date, id).
Passaggio 3: filtriamo e "espandiamo" le registrazioni
In alcune righe della nostra selezione ricorsiva, alcune registrazioni rv si duplicano — prima troviamo quelle che "intersecano" il confine della 2ª registrazione della lista, e poi le sostituiamo come prima della lista. Quindi, la prima apparizione deve essere filtrata.
La terribile query finale
CON RICORSIONE T COME (
-- #1 : aggiungiamo alla lista i "primi" record per ciascuna delle chiavi del set
CON wrap COME ( -- "materializziamo" i record, in modo che la consultazione dei campi non causi multiplo InitPlan/SubPlan
CON T COME (
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 -- ordina la lista nel modo richiesto
FROM
T
)
SELECT
list
, list[1] rv
, FALSE not_cross
, 0 size
FROM
wrap
UNIONE TUTTO
-- #2 : leggiamo i record della prima chiave, finché non oltrepassiamo il record della seconda
SELECT
CASE
-- se non è stato trovato nulla per la prima chiave
WHEN X._r IS NOT DISTINCT FROM NULL THEN
T.list[2:] -- rimuoviamo dal lista
-- se NON abbiamo oltrepassato la chiave applicativa del secondo record
WHEN X.not_cross THEN
T.list -- proseguiamo con la stessa lista senza modifiche
-- se non c'è già il secondo record nella lista
WHEN T.list[2] IS NULL THEN
-- torniamo semplicemente una lista vuota
'{}'
-- riordiniamo il dizionario rimuovendo il primo record e aggiungendo l'ultimo trovato
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
, LATERALE(
CON wrap COME ( -- "materializziamo" il record
SELECT
CASE
-- se abbiamo "oltrepassato" il secondo record
WHEN NOT T.not_cross
-- allora il record necessario è il primo della lista
THEN T.list[1]
ELSE ( -- se non abbiamo oltrepassato, la chiave rimane come nel record precedente - 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 il secondo record non è già nella lista, ma abbiamo trovato qualcosa
WHEN list[2] IS NULL AND _r IS DISTINCT FROM NULL THEN
TRUE
ELSE -- non abbiamo trovato nulla o "ci siamo oltrepassati"
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é la lista non è finita
)
-- #3 : "espandiamo" i record - l'ordine è garantito dalla costruzione
SELECT
(rv).*
FROM
T
WHERE
not_cross; -- prendiamo solo i record "non sovrapposti" 
In questo modo, abbiamo scambiato il 50% delle letture dei dati con il 20% del tempo di esecuzione. Quindi, se hai motivi di credere che la lettura possa richiedere tempo (ad esempio, se i dati non sono spesso in cache e devi recuperarli dal disco), puoi quindi ridurre la dipendenza dalla lettura.
In ogni caso, il tempo di esecuzione è risultato migliore rispetto alla prima versione "naïve". Ma quale di queste 3 opzioni utilizzare è una tua scelta.
Fonte: habr.com
