Algoritmi di join: Nested Loop, Hash, Merge

Lei conosce già INNER JOIN come sintassi. Nei colloqui per ruoli senior, gli intervistatori chiedono come il database esegue fisicamente un join. Esistono tre algoritmi:

• Nested Loop Join
• Hash Join
• Merge Join (sort-merge)

Il tipo logico di join (INNER, LEFT) è indipendente dall'algoritmo. Il planner sceglie l'algoritmo in base alle dimensioni delle tabelle, agli indici e all'ordinamento. Capire quando ciascuno offre i risultati migliori è il fulcro di questa lezione.

Il Nested Loop è il metodo più semplice: per ogni riga della tabella esterna, esamina la tabella interna alla ricerca delle corrispondenze. In pseudocodice, sono due cicli, uno annidato nell'altro.

In modo ingenuo, ha complessità O(outer * inner), quindi è pessimo per le tabelle grandi. Tuttavia, diventa eccellente quando il lato inner ha un indice sulla chiave di join: ogni riga del lato esterno attiva una ricerca rapida nell'indice invece di una scansione completa del lato interno.

È il metodo preferito dal planner quando la tabella esterna è piccola e la colonna di join della tabella interna è indicizzata.

L'indizio rivelatore di un nested loop è la presenza di loops sul nodo interno. L'esempio mostra loops=3 perché il lato esterno ha prodotto 3 righe, quindi la scansione dell'indice interno è stata eseguita 3 volte.

Il problema emerge quando il lato esterno è grande. Se produce 2 milioni di righe, il lato interno viene eseguito 2 milioni di volte. Anche una ricerca rapida da 0.01ms diventa così un'attesa di 20 secondi.

Nei colloqui, segnali qualsiasi nested loop con un valore elevato di loops su una tabella interna priva di un buon indice: quella è la query lenta.

Il Hash Join gestisce bene le tabelle grandi non ordinate. Funziona in due fasi:

• Build: legge la tabella più piccola e la carica in una hash table in memoria, indicizzata sulla colonna di join.
• Probe: esegue la scansione della tabella più grande; per ogni riga, calcola l'hash della chiave di join e lo cerca nella hash table.

Ogni tabella viene letta una sola volta, con una complessità approssimativa O(outer + inner). Non richiede né indici né dati già ordinati, per questo prevale nei join analitici di grandi dimensioni basati su condizioni di uguaglianza.

Ci sono due aspetti da citare assolutamente sugli hash join:

• Funzionano solo con condizioni di join basate sull'uguaglianza (a.id = b.id). Una condizione su un intervallo come a.x < b.y non può usare un hash join.
• Il lato di build deve entrare in work_mem. In caso contrario, Postgres scrive i batch su disco (si vedranno Batches: > 1 e l'uso del disco), rallentando notevolmente il join.

Quindi, un hash join con un lato di build enorme e un valore di work_mem molto basso è un vero problema di prestazioni da segnalare.

Il Merge Join (sort-merge) richiede che entrambi gli input siano ordinati in base alla chiave di join. Poi li percorre in parallelo, come quando si fondono due liste ordinate, facendo avanzare il puntatore che si trova più indietro.

È efficiente quando gli input sono già ordinati, per esempio perché provengono direttamente da un indice nell'ordine della chiave: in questo caso non serve alcun passaggio di ordinamento. Supporta inoltre i join su intervalli e sulle disuguaglianze, a differenza dell'hash join.

Se gli input non sono preordinati, il planner aggiunge nodi Sort espliciti e il costo dell'ordinamento può rendere più conveniente un hash join.

Memorizzi quando ciascun algoritmo offre i risultati migliori:

• Nested Loop, tabella esterna piccola e chiave di join interna indicizzata; è anche l'unica opzione per i join basati su disuguaglianze quando l'input non è ordinato.
• Hash Join, tabelle grandi non ordinate unite con una condizione di uguaglianza; non servono indici.
• Merge Join, entrambi gli input già ordinati in base alla chiave, spesso tramite indici, oppure join su intervalli; ideale per insiemi molto grandi e già ordinati.

Il planner stima il costo di ciascuna alternativa e sceglie quella meno costosa in base alle stime del numero di righe.

L'uso delle risorse varia notevolmente, ed è un aspetto su cui gli intervistatori insistono:

• Nested Loop, usa poca memoria; il costo è dominato dalle ricerche ripetute nel lato interno.
• Hash Join, richiede memoria per la hash table e scrive su disco se questa è troppo grande.
• Merge Join, è economico da eseguire ma costoso se prima deve ordinare i dati; anche gli ordinamenti usano work_mem e possono scrivere su disco.

Aumentare work_mem può quindi trasformare un hash join o un ordinamento lento perché scrive su disco in un'operazione eseguita interamente in memoria: è una risposta concreta quando si parla di ottimizzazione.

Scenario classico: una query era veloce in sviluppo, ma lenta in produzione. Il piano mostra un Nested Loop con loops=3000000.

Il planner ha sottostimato il numero di righe del lato esterno (le statistiche obsolete indicavano 3 righe, mentre nella realtà erano 3 milioni), quindi ha scelto un nested loop. Con statistiche accurate avrebbe scelto un hash join.

La risposta da dare al colloquio è: esegua ANALYZE per correggere la stima; a quel punto il planner passerà a un hash join e la query diventerà molto più veloce.

In genere non dovrebbe forzare gli algoritmi, ma può farlo nei test per confrontarli. Postgres espone impostazioni per attivare o disattivare ciascun metodo:

SET enable_nestloop = off; e impostazioni analoghe per enable_hashjoin e enable_mergejoin. Ne disattivi una, esegua di nuovo EXPLAIN ANALYZE e osservi se l'alternativa è effettivamente più veloce.

Le correzioni appropriate restano: statistiche aggiornate, indici adeguati, un valore sufficiente di work_mem e predicati selettivi. La forzatura serve solo per la diagnosi.

Applichiamo tutto a un carico analitico che unisce due grandi tabelle dei fatti e delle dimensioni tramite un id:

• Se la dimension table entra in memoria, è probabile un Hash Join, spesso la scelta migliore.
• Se entrambe le tabelle arrivano già ordinate dagli indici, un Merge Join può evitare la fase di build dell'hash.
• In questo caso, un Nested Loop sarebbe un segnale d'allarme, solitamente causato da una stima errata.

Leggere quale algoritmo ha scelto il planner e valutare se avrebbe dovuto sceglierne un altro è esattamente la competenza senior che queste domande intendono verificare.

Si uniscono due tabelle grandi e non ordinate con una condizione di uguaglianza a.id = b.id; nessuna delle due ha un indice utile e le statistiche sono accurate. Quale algoritmo di join sceglierà con maggiore probabilità il planner?

I tre algoritmi di join:

• Nested Loop, una riga esterna alla volta con una ricerca interna; ottimo con un lato esterno piccolo e una chiave interna indicizzata, ma rischioso quando loops è enorme.
• Hash Join, costruzione e ricerca; ideale per join grandi, non ordinati e basati sull'uguaglianza, limitato alle uguaglianze e vincolato da work_mem.
• Merge Join, percorre in parallelo input ordinati; ideale quando i dati sono già ordinati o per i join su intervalli.

Il planner sceglie in base a costi e statistiche. Un nested loop sorprendente con un numero enorme di cicli indica quasi sempre una stima errata delle righe: corregga le statistiche.