Join-algoritmer: Nested Loop, Hash, Merge

Du kender allerede INNER JOIN som syntaks. På seniorniveau spørger interviewere, hvordan databasen rent faktisk udfører et join. Der er tre algoritmer:

• Nested Loop Join
• Hash Join
• Merge Join (sorteringsfletning)

Den logiske jointype (INNER, LEFT) er uafhængig af algoritmen. Planlæggeren vælger algoritmen ud fra tabellernes størrelse, indekser og sorteringsrækkefølge. At vide, hvornår hver algoritme er bedst, er kernen i denne lektion.

Nested Loop er den enkleste algoritme: For hver række i den ydre tabel gennemgås den indre tabel for at finde match. I pseudokode er det to løkker, hvor den ene ligger inden i den anden.

Naivt giver det O(ydre * indre), hvilket er meget langsomt for store tabeller. Men algoritmen bliver fremragende, når den indre side har et indeks på joinnøglen: Hver ydre række udløser et billigt indeksomslag i stedet for en fuld scanning af den indre tabel.

Det er planlæggerens favorit, når den ydre tabel er lille, og den indre joinkolonne er indekseret.

Det tydeligste tegn på en nested loop er loops på den indre node. Eksemplet viser loops=3, fordi den ydre side producerede 3 rækker, så den indre indeksscanning blev kørt 3 gange.

Problemet opstår, når den ydre side er stor. Hvis den ydre side producerer 2 millioner rækker, køres den indre side 2 millioner gange. Selv et hurtigt opslag på 0,01 ms bliver til 20 sekunder.

På et interview skal du påpege enhver nested loop, hvor loops er stort over en indre tabel uden et godt indeks. Det er den langsomme forespørgsel.

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

• Opbygning: Læs den mindre tabel, og indlæs den i en hash-tabel i hukommelsen med joinkolonnen som nøgle.
• Opslag: Gennemgå den større tabel; beregn hashværdien for joinnøglen for hver række, og slå den op i hash-tabellen.

Hver tabel læses kun én gang, hvilket giver cirka O(ydre + indre). Der kræves hverken indekser eller sorteret input, og derfor dominerer denne algoritme store analytiske joins med lighedsbetingelser.

Der er to ting, du skal nævne om hash joins:

• De fungerer kun med lighedsbetingelser (a.id = b.id). En intervalbetingelse som a.x < b.y kan ikke bruge en hash join.
• Opbygningssiden skal kunne være i work_mem. Hvis den ikke kan det, skriver Postgres batchene til disk (du vil se Batches: > 1 og diskforbrug), hvilket gør joinet markant langsommere.

En hash join med en enorm opbygningsside og en meget lille work_mem er derfor en reel performancefejl, som du bør påpege.

Merge Join (sorteringsfletning) kræver, at begge input er sorteret efter joinnøglen. Derefter gennemløber den begge synkront, ligesom når to sorterede lister flettes, og flytter den markør, der er bagefter.

Den er effektiv, når input allerede er sorteret, for eksempel når det kommer direkte fra et indeks i nøglens rækkefølge, fordi der så ikke er brug for et sorteringstrin. Den understøtter også interval- og ulighedsjoins i modsætning til hash join.

Hvis input ikke er sorteret på forhånd, tilføjer planlæggeren eksplicitte Sort-noder, og omkostningen ved sorteringen kan gøre hash join billigere i stedet.

Husk, hvornår hver algoritme er bedst:

• Nested Loop, når den ydre tabel er lille, og den indre joinnøgle er indekseret; det er også den eneste mulighed for joins uden lighedsbetingelser, når input ikke er sorteret.
• Hash Join, når store, usorterede tabeller joines med en lighedsbetingelse; der kræves ingen indekser.
• Merge Join, når begge input allerede er sorteret efter nøglen (ofte via indekser), eller ved intervaljoins; den er fremragende til meget store, forhåndssorterede datasæt.

Planlæggeren estimerer omkostningen ved hver mulighed og vælger den billigste ud fra sine estimater for antal rækker.

Ressourceforbruget varierer markant, og interviewere spørger ofte ind til det:

• Nested Loop, bruger minimal hukommelse; omkostningen domineres af gentagne opslag i den indre tabel.
• Hash Join, kræver hukommelse til hash-tabellen; skriver til disk, hvis den bliver for stor.
• Merge Join, er billig at flette, men dyr, hvis den først skal sortere; sorteringer bruger også work_mem og kan skrive til disk.

Hvis du øger work_mem, kan du derfor ændre en langsom hash join eller sortering, der skriver til disk, til en, der foregår i hukommelsen. Det er et konkret optimeringssvar.

Et klassisk scenarie: En forespørgsel var hurtig i udviklingsmiljøet, men langsom i produktionen. Planen viser en Nested Loop med loops=3000000.

Planlæggeren undervurderede antallet af rækker på den ydre side (forældede statistikker sagde 3 rækker, men virkeligheden er 3 millioner), så den valgte en nested loop. Med korrekte statistikker ville den have valgt en hash join.

Dit svar på interviewet: Kør ANALYZE, så estimatet bliver korrekt. Derefter skifter planlæggeren til en hash join, og forespørgslen bliver markant hurtigere.

Du bør normalt ikke tvinge algoritmer igennem, men du kan gøre det under test for at sammenligne dem. Postgres stiller metodebaserede indstillinger til rådighed:

SET enable_nestloop = off; og tilsvarende for enable_hashjoin og enable_mergejoin. Slå én indstilling fra, kør EXPLAIN ANALYZE igen, og se, om alternativet faktisk er hurtigere.

De rigtige løsninger er stadig friske statistikker, de rigtige indekser, tilstrækkelig work_mem og selektive prædikater. Tvangsvalg er kun til diagnosticering.

Lad os samle det for en analytisk arbejdsbelastning, der joiner to store faktatabeller og dimensionstabeller på et id:

• Hvis dimensionstabellen kan være i hukommelsen, kan du forvente en Hash Join, som ofte er bedst.
• Hvis begge tabeller kommer sorteret fra indekser, kan en Merge Join undgå opbygningen af en hash-tabel.
• En Nested Loop her ville være et advarselssignal og skyldes normalt et dårligt estimat.

At aflæse, hvilken algoritme planlæggeren valgte, og vurdere, om den burde have valgt den, er præcis det seniorniveau, disse spørgsmål tester.

De tre joinalgoritmer:

• Nested Loop, ydre række gange opslag i den indre tabel; fremragende med en lille ydre tabel og en indekseret indre nøgle, men farlig, når loops er enormt.
• Hash Join, opbygning og opslag; bedst til store, usorterede joins med lighedsbetingelser, begrænset til lighedsbetingelser og afgrænset af work_mem.
• Merge Join, synkront gennemløb af sorteret input; ideel, når data allerede er sorteret, eller ved intervaljoins.

Planlæggeren vælger ud fra omkostninger og statistikker. En overraskende nested loop med et enormt antal løkker betyder næsten altid et dårligt estimat af antallet af rækker. Opdatér statistikkerne.