Advanced téma jön, de nagyon fincsi.
Star join az, amikor egy táblához sok másik táblát kapcsoluk hozzá. Tipikusan adattárházakban van ilyen, ahogy egy hatalmas ténytáblához sok kisebb, de még azok is akár millió soros dimenzió tábla tartozik.
Az AdventureWorksDW példaadatbázis egy ilyen tárházi minta (DataWarehouse).
Ezek az adattárházi táblák elég speciálisan vannak tervezve, nem a hagyományos normalizált módon.
Például a FactInternetSales táblában a dátumok nem datetime-ként, hanem intként vannak tárolva. 20010701, ez egy egész szám, amit dátumként értelmezünk. Azért van ez a bizarr felállás, mert integereket nagyon gyorsan lehet összehasonlítani, ami a join szempontjából fontos.
No, amikor ezeket a b. nagy táblákat joinoljuk, akkor általában szóba se jöhet a loop join a világ legjobb indexei mellett se, mert százmilliószor nekifutni egy táblának még index mellett is nagyon költséges. Ilyen nagy tábláknál merge vagy hash join jöhet szóba. A merge csak a kulcsok azonos rendezettsége, azaz általában akkor működik, ha mindkét oszlopon clustered index van. Ez ritkán jön össze mindkét oldalnál, ezért elég ritkán látni merge joint nagy táblák esetén. Kis tábláknál egyébként még arra is hajlandó a szerver, hogy az kisebb táblát lerendezi úgy, mint a nagyot, aztán merge-öl. De ezt csak pár százezer soros táblákig vállalja be, és csak akkor, ha jó sok ram van a gépben.
Azaz, a legtöbb esetben az adattárházakban hash joinokat fogunk látni. A merge és a hash join is azért jobb a ciklusosnál nagy táblák esetén, mert mindkettő csak egyszer járja be a táblákat. Igaz, hogy akkor az egészet, de legalább nem esik neki sok milliószor, mint a loop join.
A hash join azt csinálja, hogy a kisebb táblát a joinolandó oszlop mentén lehasheli. Azaz általában az adott dimenziótáblát. Azaz épít egy hashtable-t a kulcs alapján. Aki valamely programozási frameworkből ismeri a hashtable-t, az tudja, hogy ez egy olyan memóriastrukrúra, ami piszok gyors keresést tesz lehetővé a hash key alapján. A kiinduló értékek hash-ei között lesz ütközés, azaz a 123 és a 3455 is lehet, hogy ugyanarra a hash értékre, mondjuk 12-re képeződik le. Az ütköző értékeket ún. vödrökbe rakják, amiben lineáris listában tárolódnak az eredeti kulcsok, azaz egy vödrön belül a keresés már nem gyors, csak lineáris, és nem a hasheket, hanem az eredeti típusokat kell komparálni.
No, amikor a build input kész az egész (de a kisebb) táblára, akkor elkezdenek végigmenni a nagyobbik táblán, és megnézik, benne van-e a join kulcsa a build inputban. Ehhez ugye lehashelik ennek is a kulcsát, majd a vödrök között felezős kereséssel gyorsan megtalálják azokat a sorokat, amelyekhez tartozó hash kulcs ugyanennyi. Ez eddig gyors. Azonban a vödrön belül lehet számtalan tétel, amelyekkel már ténylegesen össze kell hasonlítani a kulcsokat, és ez már nem túl gyors (főleg, ha nem int a kulcs, hanem pl. varchar, mindenféle collation szarakodással).
No, ez a sima hash join, ez elég gyors még indexeletlen táblákra is, de mindkét táblán egyszer végigmegy. Eszetlen nagy tábláknál (100m sorok) azonban még a bináris keresés, amivel a hashek között keresnek is lassúvá válik, főleg, hogy mondjuk 30 tábla esetén mindegyik hashtáblájában keresni kell. Azaz nem válik lassúvá, csak annyi sorra kell végrehajtani, hogy a végén mégis csak sok lesz a költsége.
Ezt akarja valamelyest csökkenteni a bitmap filter, azaz eleve kidobni azokat a sorokat a probe inputból, a ténytáblából, amelyekről valamilyen mágikus módon tudjuk, hogy biztos nincs hozzájuk passzoló sor a többi táblában. Az SQL Server 2008 ún. Bloom filtert használ (gugliék is használják ezt több termékükben is). Ez egy nagyon érdekes adatstruktúra, amellyel halmazokat lehet nagyon hatékonyan kezelni. (Akit érdekelnek a részletek, érdemes megnézni ezt a C# implementációt. Ez csak két hash függvénnyel dolgozik, és ha több mint két hash eredmény kell, akkor ezekből származtatja a többit is, így nem kell annyit hash-elnie.) Érdekessége a Bloom filternek, hogy lehet, hogy egy elemre tévesen azt mondja, hogy benne van a halmazban, pedig nincs, de sose mondja azt, hogy nincs benne egy elem a halmazban, ami pedig a valóságban beleraktak. Mivel a szerver ezt a garantáltan nem egyező sorok kiszűrésére használja nem probléma valamennyi false pozítív (azt hiszi, hogy benne van, de nincs), mert után hagyományos hash join-nal úgyis megnézik a potenciális sorokra, hogy tényleg egyeznek-e a join feltételnek megfelelően.
A Bloom filter úgy működik, hogy ha be akarnak rakni egy elemet a halmazba, akkor azt n féle hash függvénnyel is lehashelik, és a hash értéknek megfelelő bitet egyre állítják egy bitarrayben. Azaz pl. n=10 hash függvény alkalmazása esetén 10 bitpozíció lesz 1-re állítva. Más elemeket hozzáadva persze egyre több olyan bit lesz, ami már eleve 1 volt a korábban behelyezett elemek miatt.
Hogy egy elem eleme-e a halmaznak, azt úgy nézik meg, hogy lehashelik a példabeli 10 hash függvénnyel, és megnézik, hogy ezok a bitek 1-re vannak-e állítva? Ha igen, akkor az elem VALÓSZÍNŰLEG eleme a halmaznak. De nem biztos. Nyilván minél kisebb a tömb és minél több elemet tárolunk benne, annál többször hazudik, jól kell belőni a méretét és a hashek számát is. Aki szereti a valszámot, nézze meg a wikis cikket.
No, az SQL Server Star Join esetén, azaz, amikor egy nagy ténytáblához sok kisebb dimenziótáblát joinolunk hozzá, miközben minden egyes dimenziótáblához felépíti a build inputot, azaz lehasheli a kulcsaikat, közben közben építi a Bloom filtereket is, ezt hívja Bitmap Filternek. Minden egyes dimenziótáblához készül tehát egy bitmap filter. Ezek után nekilát a ténytáblát soronként felolvasni. Normál esetben le kellene hashelni az összes oszlop értéket a sorból, amely valamelyik join feltételben szerepel, és rápróbálni a megfelelő dimenziótábla hashtáblájára. Ez lenne a sima hash join. Ehelyett azt csinálja, hogy megcsinálja a bitmap filterhez tartozó n féle hashképzést, és rápróbálja azokat az első, általa legszelektívebbek gondolt dimenzió tábla bitmap filterére. Ha az azt mondja nincs benne az elem a halmazban, akkor ez garantáltan azt jelenti, hogy ez a sor kiesik a join miatt, így se ezen dimenziótábla hash table-jében, se a többiében nem érdemes megnézni, benne van-e az elem. Ha az első bitmap filter nem ejtette ki a sort, akkor jön a következő. Ha mindegyiken átment a dolog, akkor még mindig megvan, ha nagyon kicsi is a valószínűsége, hogy fals pozitív a sor, azaz valójában nincs is párja a többi táblában, ezért ilyenkor még meg kell csinálni a hash joint erre a sorra a hagyományos módon, összepárosítva az összes táblával.
Jól látszik, hogy ha egy olyan bitmap filtereket csinál a szerver, amelyek nem elég szelektívek, azaz nem ejtenek ki elég sort, akkor nyereség helyett veszteség lesz a sok felesleges hashelés miatt. Ezért van troubleshooting cikk a témáról. :)
Persze, okos a szerver, ha menet közben észreveszi, hogy nem a legszelektívebb filter van elöl, átrendezi a listáját. Ez végül is minimális statisztikázással nyomonkövethető a részéről.

A bitmap filtert csak párhuzamos tervek esetén használja az SQL Server. Meg lehet nézni, hogy mutat ez a végrehajtási tervben, némi magyarázattal. Berakom ide a is a képet, szokjuk:

A végrehajtási terven látható, hogy a FactInternetSales tábla tartalmát előszűri a fenti két bitmap filterrel.
Az SQL 2005 is tudta már ezt, csak az statikusan, a terv generálása közben döntötte el, hogy használni fog filtert, míg az SQL 2008 a közbenső join-ok végrehajtása közben is dinamikusan tud dönteni róla, ej, elég volt a hagyományos hash joinból, itt bizony bitmap filtereket kell építeni.
Jó, mi?

Could you hire me? Contact me if you like what I’ve done in this article and think I can create value for your company with my skills.