Liitosalgoritmit: Nested Loop, Hash, Merge

Tunnette jo INNER JOIN -syntaksin. Senioritason haastatteluissa kysytään, miten tietokanta suorittaa liitoksen fyysisesti. Algoritmeja on kolme:

• Nested Loop -liitos
• Hash Join
• Merge Join (lajittele ja yhdistä)

Looginen liitostyyppi (INNER, LEFT) on riippumaton algoritmista. Suunnittelija valitsee algoritmin taulujen koon, indeksien ja lajittelujärjestyksen perusteella. Tämän oppitunnin ydin on ymmärtää, milloin kukin algoritmi on tehokkain.

Nested Loop on yksinkertaisin: jokaiselle ulomman taulun riville etsitään vastaavuudet käymällä sisempi taulu läpi. Pseudokoodissa tämä tarkoittaa kahta sisäkkäistä silmukkaa.

Suoraviivaisesti toteutettuna aikavaativuus on O(outer * inner), mikä on suurilla tauluilla erittäin huono. Menetelmästä tulee kuitenkin erinomainen, kun sisemmällä puolella on liitosavaimen indeksi: jokainen ulomman taulun rivi käynnistää halvan indeksihakun koko sisemmän taulun läpikäynnin sijaan.

Suunnittelija suosii tätä menetelmää, kun ulompi taulu on pieni ja sisemmän taulun liitossarakkeella on indeksi.

Sisäkkäisen silmukan tunnistaa sisemmän solmun loops-arvosta. Esimerkissä näkyy loops=3, koska ulompi puoli tuotti 3 riviä ja sisempi indeksihaku suoritettiin siksi 3 kertaa.

Ongelma ilmenee, kun ulompi puoli on suuri. Jos ulompi puoli tuottaa 2 miljoonaa riviä, sisempi puoli suoritetaan 2 miljoonaa kertaa. Silloinkin kun yksi haku kestää vain 0,01 ms, kokonaisajaksi tulee 20 sekuntia.

Haastattelussa kannattaa huomauttaa jokaisesta sisäkkäisestä silmukasta, jossa loops on suuri ja sisemmällä taululla ei ole hyvää indeksiä: kyseessä on hidas kysely.

Hash Join käsittelee suuria lajittelemattomia tauluja tehokkaasti. Se toimii kahdessa vaiheessa:

• Build: luetaan pienempi taulu ja ladataan se liitossarakkeen perusteella avaimettuun muistissa olevaan hajautustauluun.
• Probe: käydään suurempi taulu läpi; jokaisella rivillä liitosavain hajautetaan ja sitä etsitään hajautustaulusta.

Kumpikin taulu luetaan vain kerran, joten aikavaativuus on suunnilleen O(outer + inner). Menetelmä ei tarvitse indeksejä eikä valmiiksi lajiteltua syötettä, minkä vuoksi se on yleensä paras vaihtoehto suurissa yhtäläisyyteen perustuvissa analyyttisissa liitoksissa.

Hash Join -liitoksista on mainittava kaksi asiaa:

• Ne toimivat vain yhtäläisyyteen perustuvilla liitosehdoilla (a.id = b.id). Alue-ehto, kuten a.x < b.y, ei voi käyttää Hash Joinia.
• Build-puolen on mahduttava work_mem-muistiin. Jos se ei mahdu, Postgres kirjoittaa erät levylle (näkyviin tulee Batches: > 1 ja levyn käyttö), mikä hidastaa liitosta huomattavasti.

Siksi valtava build-puoli ja liian pieni work_mem muodostavat käytännön suorituskykyongelman, joka kannattaa tuoda esiin.

Merge Join (lajittele ja yhdistä) edellyttää, että molemmat syötteet on lajiteltu liitosavaimen mukaan. Tämän jälkeen se etenee molemmissa samanaikaisesti kuin kaksi lajiteltua listaa yhdistettäessä ja siirtää sitä osoitinta, joka on jäljessä.

Menetelmä on tehokas, kun syötteet ovat jo valmiiksi lajiteltuja, esimerkiksi kun ne tulevat suoraan indeksistä avainten mukaisessa järjestyksessä, koska erillistä lajitteluvaihetta ei silloin tarvita. Se tukee myös alue- ja epäyhtälöliitoksia toisin kuin Hash Join.

Jos syötteitä ei ole lajiteltu etukäteen, suunnittelija lisää erilliset Sort-solmut, ja lajittelun kustannus voi tehdä Hash Joinista edullisemman vaihtoehdon.

Opetelkaa ulkoa, milloin kukin algoritmi on tehokkain:

• Nested Loop: pieni ulompi taulu ja indeksoitu sisemmän taulun liitosavain; lisäksi ainoa vaihtoehto epäyhtälöliitoksille, kun syöte ei ole lajiteltu.
• Hash Join: suuret lajittelemattomat taulut, jotka yhdistetään yhtäläisyyden perusteella; indeksejä ei tarvita.
• Merge Join: molemmat syötteet on jo lajiteltu avaimen mukaan (usein indeksien avulla), tai kyseessä on alueeseen perustuva liitos; erinomainen erittäin suurille valmiiksi lajitelluille aineistoille.

Suunnittelija arvioi kunkin vaihtoehdon kustannukset ja valitsee halvimman vaihtoehdon rivimääräarvioidensa perusteella.

Resurssien käyttö vaihtelee huomattavasti, ja haastattelijat kysyvät tästä usein:

• Nested Loop: käyttää vain vähän muistia; kustannukset syntyvät toistuvista sisemmän puolen hauista.
• Hash Join: tarvitsee muistia hajautustaululle; liian suuri taulu kirjoitetaan levylle.
• Merge Join: yhdistäminen on edullista, mutta ensin tehtävä lajittelu on kallista; lajittelut käyttävät myös work_mem-muistia ja voivat siirtyä levylle.

Siksi work_mem-arvon kasvattaminen voi muuttaa hitaan, levylle tietoa kirjoittavan hash- tai lajitteluoperaation muistissa suoritettavaksi operaatioksi. Tämä on konkreettinen optimointivastaus.

Tyypillinen tilanne: kysely oli kehitysympäristössä nopea mutta tuotannossa hidas. Suunnitelmassa näkyy Nested Loop ja loops=3000000.

Suunnittelija arvioi ulomman puolen rivimäärän liian pieneksi (vanhentuneet tilastot ilmoittivat 3 riviä, vaikka todellinen määrä on 3 miljoonaa), joten se valitsi sisäkkäisen silmukan. Jos tilastot olisivat ajan tasalla, se olisi valinnut Hash Joinin.

Haastattelussa vastauksenne voisi olla: Suoritetaan ANALYZE, jotta arvio on oikea. Sen jälkeen suunnittelija vaihtaa Hash Joiniin ja kysely nopeutuu huomattavasti.

Algoritmeja ei yleensä pidä pakottaa, mutta testauksessa niitä voi käyttää vaihtoehtojen vertailuun. Postgres tarjoaa menetelmäkohtaiset kytkimet:

SET enable_nestloop = off; ja vastaavat asetukset enable_hashjoin- ja enable_mergejoin-menetelmille. Poistakaa yksi menetelmä käytöstä, suorittakaa EXPLAIN ANALYZE uudelleen ja tarkkailkaa, onko vaihtoehto todella nopeampi.

Oikeat korjaukset ovat edelleen ajan tasalla olevat tilastot, oikeat indeksit, riittävä work_mem ja valikoivat ehdot. Pakottaminen on tarkoitettu vain vianmääritykseen.

Sovelletaan tätä analyyttiseen työkuormaan, jossa kaksi suurta fakta- ja dimensiotaulua yhdistetään tunnisteen perusteella:

• Jos dimensio mahtuu muistiin, odotettavissa on Hash Join, joka on usein paras vaihtoehto.
• Jos molemmat syötteet tulevat indekseistä valmiiksi lajiteltuina, Merge Join voi välttää hash-taulun rakentamisen.
• Nested Loop olisi tässä varoitusmerkki, jonka syynä on yleensä virheellinen arvio.

Juuri sen arviointi, minkä vaihtoehdon suunnittelija valitsi ja olisiko sen pitänyt valita jokin muu, kertoo senioritason osaamisesta, jota näillä kysymyksillä testataan.

Kolme liitosalgoritmia:

• Nested Loop: ulomman puolen rivit kerrottuna sisemmän puolen hauilla; erinomainen, kun ulompi puoli on pieni ja sisempi liitosavain indeksoitu, mutta vaarallinen, kun loops on valtava.
• Hash Join: hajautustaulun rakentaminen ja sen avulla etsiminen; paras suurille lajittelemattomille yhtäläisyysliitoksille, rajoittuu yhtäläisyyteen ja work_mem rajoittaa sitä.
• Merge Join: eteneminen rinnakkain lajiteltujen syötteiden läpi; ihanteellinen, kun data on jo lajiteltu tai kyseessä on alueeseen perustuva liitos.

Suunnittelija valitsee menetelmän kustannusten ja tilastojen perusteella. Yllättävä sisäkkäinen silmukka, jossa silmukkamäärä on valtava, tarkoittaa lähes aina virheellistä rivimääräarviota, joten tilastot on korjattava.