Join-algoritmer: Nested Loop, Hash og Merge

Du kjenner allerede INNER JOIN som syntaks. På seniornivå spør intervjuere hvordan databasen fysisk utfører en join. Det finnes tre algoritmer:

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

Den logiske join-typen (INNER, LEFT) er uavhengig av algoritmen. Planleggeren velger algoritme basert på tabellstørrelser, indekser og sorteringsrekkefølge. Å vite når hver av dem er best, er kjernen i denne leksjonen.

Nested Loop er den enkleste: For hver rad i den ytre tabellen skannes den indre tabellen for å finne treff. I pseudokode er dette to løkker, der den ene ligger inni den andre.

Naivt sett er dette O(outer * inner), noe som er svært dårlig for store tabeller. Men det blir utmerket når den indre siden har en indeks på join-nøkkelen: Hver ytre rad utløser et billig indeksoppslag i stedet for en full skanning av den indre tabellen.

Dette er planleggerens favoritt når den ytre tabellen er liten og den indre join-kolonnen er indeksert.

Et tydelig kjennetegn på en nested loop er loops på den indre noden. Eksemplet viser loops=3 fordi den ytre siden produserte 3 rader, og den indre indeksskanningen derfor ble kjørt 3 ganger.

Faren oppstår når den ytre siden er stor. Hvis den ytre siden produserer 2 millioner rader, kjører den indre siden 2 millioner ganger. Selv et raskt oppslag på 0.01ms blir da 20 sekunder.

I intervjuer bør du påpeke alle nested loops der loops er høyt for en indre tabell uten en god indeks. Det er den trege spørringen.

Hash Join håndterer store, usorterte tabeller godt. Den kjører i to faser:

• Build: Les den minste tabellen og last den inn i en hash-tabell i minnet, med join-kolonnen som nøkkel.
• Probe: Skann den største tabellen. For hver rad hashes join-nøkkelen og slås opp i hash-tabellen.

Hver tabell leses bare én gang, noe som gir omtrent O(outer + inner). Det kreves verken indekser eller sortert inndata, og derfor dominerer denne algoritmen store analytiske joins på likhetsbetingelser.

Det er to ting du må nevne om hash joins:

• De fungerer bare for join-betingelser med likhet (a.id = b.id). En områdebetingelse som a.x < b.y kan ikke bruke en hash join.
• Build-siden må få plass i work_mem. Hvis den ikke gjør det, skriver Postgres batcher til disk (du vil se Batches: > 1 og diskbruk), noe som gjør joinen betydelig tregere.

En hash join med en enorm build-side og svært liten work_mem er derfor en reell ytelsesfeil som bør påpekes.

Merge Join (sort-merge) krever at begge inndataene er sortert etter join-nøkkelen. Deretter går den gjennom begge i takt, omtrent som når to sorterte lister flettes, ved å flytte pekeren som ligger etter.

Den er effektiv når inndataene allerede er sortert, for eksempel når de kommer direkte fra en indeks i nøkkelrekkefølge, fordi det ikke er nødvendig med et sorteringstrinn. Den støtter også område- og ulikhets-joins, i motsetning til hash join.

Hvis inndataene ikke er forhåndssortert, legger planleggeren til eksplisitte Sort-noder, og sorteringskostnaden kan gjøre hash join billigere i stedet.

Husk når hver algoritme er best:

• Nested Loop, en liten ytre tabell og en indeksert indre join-nøkkel; også det eneste alternativet for joins med ulikhetsbetingelser uten sortert inndata.
• Hash Join, store usorterte tabeller som joines med likhetsbetingelser; ingen indekser er nødvendig.
• Merge Join, når begge inndataene allerede er sortert etter nøkkelen (ofte via indekser), eller for område-joins; utmerket for svært store, forhåndssorterte datasett.

Planleggeren anslår kostnaden for hver algoritme og velger den billigste ut fra radestimatene.

Ressursbruken varierer kraftig, og intervjuere undersøker dette:

• Nested Loop, bruker minimalt med minne; kostnaden domineres av gjentatte oppslag i den indre tabellen.
• Hash Join, trenger minne til hash-tabellen; skriver til disk hvis den blir for stor.
• Merge Join, er billig å flette, men dyr hvis den først må sortere; sorteringer bruker også work_mem og kan skrive til disk.

Å øke work_mem kan derfor gjøre en treg hash join eller sortering som skriver til disk, om til en som får plass i minnet. Det er et konkret optimaliseringssvar.

Et klassisk scenario: En spørring var rask i utviklingsmiljøet, men treg i produksjon. Planen viser en Nested Loop med loops=3000000.

Planleggeren undervurderte antallet rader på den ytre siden (foreldet statistikk sa 3 rader, mens virkeligheten er 3 millioner), og valgte derfor en nested loop. Med korrekte statistikker ville den ha valgt en hash join.

Intervjusvaret ditt: Kjør ANALYZE slik at estimatet blir korrekt. Planleggeren vil da bytte til en hash join, og spørringen blir betydelig raskere.

Du bør vanligvis ikke tvinge frem algoritmer, men du kan gjøre det i testing for å sammenligne. Postgres tilbyr brytere for hver metode:

SET enable_nestloop = off; og tilsvarende for enable_hashjoin og enable_mergejoin. Slå av én av dem, kjør EXPLAIN ANALYZE på nytt, og se om alternativet faktisk er raskere.

De riktige løsningene er fortsatt ferske statistikker, de riktige indeksene, tilstrekkelig work_mem og selektive predikater. Tvang er bare til diagnostisering.

Sett dette sammen for en analytisk arbeidsbelastning som joiner to store fakta- og dimensjonstabeller på en id:

• Hvis dimensjonstabellen får plass i minnet, kan du forvente en Hash Join, som ofte er best.
• Hvis begge tabellene kommer sortert fra indekser, kan en Merge Join unngå å bygge en hash-tabell.
• En Nested Loop her ville vært et varselstegn, vanligvis forårsaket av et feilaktig estimat.

Å lese hvilken algoritme planleggeren valgte, og vurdere om den burde ha valgt den, er nettopp seniorferdigheten disse spørsmålene tester.

De tre join-algoritmene:

• Nested Loop, ytre rad ganger indre oppslag; utmerket med en liten ytre tabell og en indeksert indre nøkkel, men farlig når loops er svært høyt.
• Hash Join, bygg og slå opp; best for store, usorterte joins med likhetsbetingelser, begrenset til likhet og avhengig av work_mem.
• Merge Join, går parallelt gjennom sorterte inndata; ideell når dataene allerede er sortert eller for område-joins.

Planleggeren velger basert på kostnad og statistikk. En overraskende nested loop med svært mange løkker betyr nesten alltid et feilaktig radestimat. Rett statistikken.