Joinstrategier

Joinstrategier er de algoritmene databassystemer bruker for å sette sammen rader fra to tabeller basert på en felles join-betingelse. En moderne databasenhet lar en kostnadsbasert optimiser velge en strategi basert på statistikk om tabellene, forventede utdata og minne- og I/O-kostnader. De vanligste strategiene er nested loop, sort-merge og hash join, ofte i ulike varianter eller i kombinasjon med indekser og parallellisering.

Nested loop join går gjennom den ytre relasjonen rad for rad og søker etter samsvarende rader i den indre relasjonen. Dette er enkelt og effektivt når en av tabellene er liten, eller når det finnes nyttig indeks på join-kolonnen. En blokk-nested loop prøver å redusere I/O ved å hente flere rader fra den ytre relasjonen ad gangen.

Indeks-nested loop join bruker et indeksert søk på den indre relasjonen for hver rad i den ytre, noe som ofte gjør operasjonen rask når indekser er tilgjengelige, selv om begge tabellene er store.

Sort-merge join sorterer begge relasjonene etter join-nøkkelen og merges dem i én pass. Den er spesielt gunstig når store mengder data må skannes og ingen effektive indekser finnes, eller når data allerede er sortert eller kan sorteres kostnadseffektivt.

Hash join bygger en hash-tabell på join-nøkkelen for den ene relasjonen og bruker den til å probe den andre. Den er effektiv for store, rene equi-joins og fungerer godt når tilstrekkelig minne er tilgjengelig; ved stor datamengde kan grace hash join brukes for å håndtere deler som ikke får plass i minne.

Valg av joinstrategi avhenger av datafordeling, indeksnivå, tilgjengelig minne og ønsket svarstid; moderne databaser bruker en optimisator som vurderer flere alternativer og velger den anatomisk billigste planen.