{"id":495,"date":"2008-04-07T10:42:34","date_gmt":"2008-04-07T09:42:34","guid":{"rendered":"http:\/\/soci.hu\/blog\/?p=495"},"modified":"2008-04-07T10:48:13","modified_gmt":"2008-04-07T09:48:13","slug":"sql-server-2008-ujdonsagok-32-star-join-es-optimized-bitmap-filtering","status":"publish","type":"post","link":"https:\/\/soci.hu\/blog\/index.php\/2008\/04\/07\/sql-server-2008-ujdonsagok-32-star-join-es-optimized-bitmap-filtering\/","title":{"rendered":"SQL Server 2008 \u00fajdons\u00e1gok 32. – Star join \u00e9s Optimized Bitmap Filtering"},"content":{"rendered":"

Advanced t\u00e9ma j\u00f6n, de nagyon fincsi.
\nStar join az, amikor egy t\u00e1bl\u00e1hoz sok m\u00e1sik t\u00e1bl\u00e1t kapcsoluk hozz\u00e1. Tipikusan adatt\u00e1rh\u00e1zakban van ilyen, ahogy egy hatalmas t\u00e9nyt\u00e1bl\u00e1hoz sok kisebb, de m\u00e9g azok is ak\u00e1r milli\u00f3 soros dimenzi\u00f3 t\u00e1bla tartozik.
\nAz AdventureWorksDW<\/strong> p\u00e9ldaadatb\u00e1zis egy ilyen t\u00e1rh\u00e1zi minta (DataWarehouse).
\nEzek az adatt\u00e1rh\u00e1zi t\u00e1bl\u00e1k el\u00e9g speci\u00e1lisan vannak tervezve, nem a hagyom\u00e1nyos normaliz\u00e1lt m\u00f3don.
\nP\u00e9ld\u00e1ul a FactInternetSales t\u00e1bl\u00e1ban a d\u00e1tumok nem datetime-k\u00e9nt, hanem intk\u00e9nt vannak t\u00e1rolva. 20010701, ez egy eg\u00e9sz sz\u00e1m, amit d\u00e1tumk\u00e9nt \u00e9rtelmez\u00fcnk. Az\u00e9rt van ez a bizarr fel\u00e1ll\u00e1s, mert integereket nagyon gyorsan lehet \u00f6sszehasonl\u00edtani, ami a join szempontj\u00e1b\u00f3l fontos.
\nNo, amikor ezeket a b. nagy t\u00e1bl\u00e1kat joinoljuk, akkor \u00e1ltal\u00e1ban sz\u00f3ba se j\u00f6het a loop join a vil\u00e1g legjobb indexei mellett se, mert sz\u00e1zmilli\u00f3szor nekifutni egy t\u00e1bl\u00e1nak m\u00e9g index mellett is nagyon k\u00f6lts\u00e9ges. Ilyen nagy t\u00e1bl\u00e1kn\u00e1l merge vagy hash join j\u00f6het sz\u00f3ba. A merge csak a kulcsok azonos rendezetts\u00e9ge, azaz \u00e1ltal\u00e1ban akkor m\u0171k\u00f6dik, ha mindk\u00e9t oszlopon clustered index van. Ez ritk\u00e1n j\u00f6n \u00f6ssze mindk\u00e9t oldaln\u00e1l, ez\u00e9rt el\u00e9g ritk\u00e1n l\u00e1tni merge joint nagy t\u00e1bl\u00e1k eset\u00e9n. Kis t\u00e1bl\u00e1kn\u00e1l egy\u00e9bk\u00e9nt m\u00e9g arra is hajland\u00f3 a szerver, hogy az kisebb t\u00e1bl\u00e1t lerendezi \u00fagy, mint a nagyot, azt\u00e1n merge-\u00f6l. De ezt csak p\u00e1r sz\u00e1zezer soros t\u00e1bl\u00e1kig v\u00e1llalja be, \u00e9s csak akkor, ha j\u00f3 sok ram van a g\u00e9pben.
\nAzaz, a legt\u00f6bb esetben az adatt\u00e1rh\u00e1zakban hash joinokat fogunk l\u00e1tni. A merge \u00e9s a hash join is az\u00e9rt jobb a ciklusosn\u00e1l nagy t\u00e1bl\u00e1k eset\u00e9n, mert mindkett\u0151 csak egyszer j\u00e1rja be a t\u00e1bl\u00e1kat. Igaz, hogy akkor az eg\u00e9szet, de legal\u00e1bb nem esik neki sok milli\u00f3szor, mint a loop join.
\nA hash join azt csin\u00e1lja, hogy a kisebb t\u00e1bl\u00e1t a joinoland\u00f3 oszlop ment\u00e9n lehasheli. Azaz \u00e1ltal\u00e1ban az adott dimenzi\u00f3t\u00e1bl\u00e1t. Azaz \u00e9p\u00edt egy hashtable-t a kulcs alapj\u00e1n. Aki valamely programoz\u00e1si frameworkb\u0151l ismeri a hashtable-t, az tudja, hogy ez egy olyan mem\u00f3riastrukr\u00fara, ami piszok gyors keres\u00e9st tesz lehet\u0151v\u00e9 a hash key alapj\u00e1n. A kiindul\u00f3 \u00e9rt\u00e9kek hash-ei k\u00f6z\u00f6tt lesz \u00fctk\u00f6z\u00e9s, azaz a 123 \u00e9s a 3455 is lehet, hogy ugyanarra a hash \u00e9rt\u00e9kre, mondjuk 12-re k\u00e9pez\u0151dik le. Az \u00fctk\u00f6z\u0151 \u00e9rt\u00e9keket \u00fan. v\u00f6dr\u00f6kbe rakj\u00e1k, amiben line\u00e1ris list\u00e1ban t\u00e1rol\u00f3dnak az eredeti kulcsok, azaz egy v\u00f6dr\u00f6n bel\u00fcl a keres\u00e9s m\u00e1r nem gyors, csak line\u00e1ris, \u00e9s nem a hasheket, hanem az eredeti t\u00edpusokat kell kompar\u00e1lni.
\nNo, amikor a build input k\u00e9sz az eg\u00e9sz (de a kisebb) t\u00e1bl\u00e1ra, akkor elkezdenek v\u00e9gigmenni a nagyobbik t\u00e1bl\u00e1n, \u00e9s megn\u00e9zik, benne van-e a join kulcsa a build inputban. Ehhez ugye lehashelik ennek is a kulcs\u00e1t, majd a v\u00f6dr\u00f6k k\u00f6z\u00f6tt felez\u0151s keres\u00e9ssel gyorsan megtal\u00e1lj\u00e1k azokat a sorokat, amelyekhez tartoz\u00f3 hash kulcs ugyanennyi. Ez eddig gyors. Azonban a v\u00f6dr\u00f6n bel\u00fcl lehet sz\u00e1mtalan t\u00e9tel, amelyekkel m\u00e1r t\u00e9nylegesen \u00f6ssze kell hasonl\u00edtani a kulcsokat, \u00e9s ez m\u00e1r nem t\u00fal gyors (f\u0151leg, ha nem int a kulcs, hanem pl. varchar, mindenf\u00e9le collation szarakod\u00e1ssal).
\nNo, ez a sima hash join, ez el\u00e9g gyors m\u00e9g indexeletlen t\u00e1bl\u00e1kra is, de mindk\u00e9t t\u00e1bl\u00e1n egyszer v\u00e9gigmegy. Eszetlen nagy t\u00e1bl\u00e1kn\u00e1l (100m sorok) azonban m\u00e9g a bin\u00e1ris keres\u00e9s, amivel a hashek k\u00f6z\u00f6tt keresnek is lass\u00fav\u00e1 v\u00e1lik, f\u0151leg, hogy mondjuk 30 t\u00e1bla eset\u00e9n mindegyik hasht\u00e1bl\u00e1j\u00e1ban keresni kell. Azaz nem v\u00e1lik lass\u00fav\u00e1, csak annyi sorra kell v\u00e9grehajtani, hogy a v\u00e9g\u00e9n m\u00e9gis csak sok lesz a k\u00f6lts\u00e9ge.
\nEzt akarja valamelyest cs\u00f6kkenteni a bitmap filter, azaz eleve kidobni azokat a sorokat a probe inputb\u00f3l, a t\u00e9nyt\u00e1bl\u00e1b\u00f3l, amelyekr\u0151l valamilyen m\u00e1gikus m\u00f3don tudjuk, hogy biztos nincs hozz\u00e1juk passzol\u00f3 sor a t\u00f6bbi t\u00e1bl\u00e1ban. Az SQL Server 2008 \u00fan. Bloom filtert<\/a> haszn\u00e1l (gugli\u00e9k is haszn\u00e1lj\u00e1k ezt t\u00f6bb term\u00e9k\u00fckben is). Ez egy nagyon \u00e9rdekes adatstrukt\u00fara, amellyel halmazokat lehet nagyon hat\u00e9konyan kezelni. (Akit \u00e9rdekelnek a r\u00e9szletek, \u00e9rdemes megn\u00e9zni ezt a C# implement\u00e1ci\u00f3t<\/a>. Ez csak k\u00e9t hash f\u00fcggv\u00e9nnyel dolgozik, \u00e9s ha t\u00f6bb mint k\u00e9t hash eredm\u00e9ny kell, akkor ezekb\u0151l sz\u00e1rmaztatja a t\u00f6bbit is, \u00edgy nem kell annyit hash-elnie.) \u00c9rdekess\u00e9ge a Bloom filternek, hogy lehet, hogy egy elemre t\u00e9vesen azt mondja, hogy benne van a halmazban, pedig nincs, de sose mondja azt, hogy nincs benne egy elem a halmazban, ami pedig a val\u00f3s\u00e1gban beleraktak. Mivel a szerver ezt a garant\u00e1ltan nem egyez\u0151 sorok kisz\u0171r\u00e9s\u00e9re haszn\u00e1lja nem probl\u00e9ma valamennyi false poz\u00edt\u00edv (azt hiszi, hogy benne van, de nincs), mert ut\u00e1n hagyom\u00e1nyos hash join-nal \u00fagyis megn\u00e9zik a potenci\u00e1lis sorokra, hogy t\u00e9nyleg egyeznek-e a join felt\u00e9telnek megfelel\u0151en.
\nA Bloom filter \u00fagy m\u0171k\u00f6dik, hogy ha be akarnak rakni egy elemet a halmazba, akkor azt n f\u00e9le hash f\u00fcggv\u00e9nnyel is lehashelik, \u00e9s a hash \u00e9rt\u00e9knek megfelel\u0151 bitet egyre \u00e1ll\u00edtj\u00e1k egy bitarrayben. Azaz pl. n=10 hash f\u00fcggv\u00e9ny alkalmaz\u00e1sa eset\u00e9n 10 bitpoz\u00edci\u00f3 lesz 1-re \u00e1ll\u00edtva. M\u00e1s elemeket hozz\u00e1adva persze egyre t\u00f6bb olyan bit lesz, ami m\u00e1r eleve 1 volt a kor\u00e1bban behelyezett elemek miatt.
\nHogy egy elem eleme-e a halmaznak, azt \u00fagy n\u00e9zik meg, hogy lehashelik a p\u00e9ldabeli 10 hash f\u00fcggv\u00e9nnyel, \u00e9s megn\u00e9zik, hogy ezok a bitek 1-re vannak-e \u00e1ll\u00edtva? Ha igen, akkor az elem VAL\u00d3SZ\u00cdN\u0170LEG eleme a halmaznak. De nem biztos. Nyilv\u00e1n min\u00e9l kisebb a t\u00f6mb \u00e9s min\u00e9l t\u00f6bb elemet t\u00e1rolunk benne, ann\u00e1l t\u00f6bbsz\u00f6r hazudik, j\u00f3l kell bel\u0151ni a m\u00e9ret\u00e9t \u00e9s a hashek sz\u00e1m\u00e1t is. Aki szereti a valsz\u00e1mot, n\u00e9zze meg a wikis cikket.
\nNo, az SQL Server Star Join eset\u00e9n, azaz, amikor egy nagy t\u00e9nyt\u00e1bl\u00e1hoz sok kisebb dimenzi\u00f3t\u00e1bl\u00e1t joinolunk hozz\u00e1, mik\u00f6zben minden egyes dimenzi\u00f3t\u00e1bl\u00e1hoz fel\u00e9p\u00edti a build inputot, azaz lehasheli a kulcsaikat, k\u00f6zben k\u00f6zben \u00e9p\u00edti a Bloom filtereket is, ezt h\u00edvja Bitmap Filternek. Minden egyes dimenzi\u00f3t\u00e1bl\u00e1hoz k\u00e9sz\u00fcl teh\u00e1t egy bitmap filter. Ezek ut\u00e1n nekil\u00e1t a t\u00e9nyt\u00e1bl\u00e1t soronk\u00e9nt felolvasni. Norm\u00e1l esetben le kellene hashelni az \u00f6sszes oszlop \u00e9rt\u00e9ket a sorb\u00f3l, amely valamelyik join felt\u00e9telben szerepel, \u00e9s r\u00e1pr\u00f3b\u00e1lni a megfelel\u0151 dimenzi\u00f3t\u00e1bla hasht\u00e1bl\u00e1j\u00e1ra. Ez lenne a sima hash join. Ehelyett azt csin\u00e1lja, hogy megcsin\u00e1lja a bitmap filterhez tartoz\u00f3 n f\u00e9le hashk\u00e9pz\u00e9st, \u00e9s r\u00e1pr\u00f3b\u00e1lja azokat az els\u0151, \u00e1ltala legszelekt\u00edvebbek gondolt dimenzi\u00f3 t\u00e1bla bitmap filter\u00e9re. Ha az azt mondja nincs benne az elem a halmazban, akkor ez garant\u00e1ltan azt jelenti, hogy ez a sor kiesik a join miatt, \u00edgy se ezen dimenzi\u00f3t\u00e1bla hash table-j\u00e9ben, se a t\u00f6bbi\u00e9ben nem \u00e9rdemes megn\u00e9zni, benne van-e az elem. Ha az els\u0151 bitmap filter nem ejtette ki a sort, akkor j\u00f6n a k\u00f6vetkez\u0151. Ha mindegyiken \u00e1tment a dolog, akkor m\u00e9g mindig megvan, ha nagyon kicsi is a val\u00f3sz\u00edn\u0171s\u00e9ge, hogy fals pozit\u00edv a sor, azaz val\u00f3j\u00e1ban nincs is p\u00e1rja a t\u00f6bbi t\u00e1bl\u00e1ban, ez\u00e9rt ilyenkor m\u00e9g meg kell csin\u00e1lni a hash joint erre a sorra a hagyom\u00e1nyos m\u00f3don, \u00f6sszep\u00e1ros\u00edtva az \u00f6sszes t\u00e1bl\u00e1val.
\nJ\u00f3l l\u00e1tszik, hogy ha egy olyan bitmap filtereket csin\u00e1l a szerver, amelyek nem el\u00e9g szelekt\u00edvek, azaz nem ejtenek ki el\u00e9g sort, akkor nyeres\u00e9g helyett vesztes\u00e9g lesz a sok felesleges hashel\u00e9s miatt. Ez\u00e9rt van troubleshooting cikk<\/a> a t\u00e9m\u00e1r\u00f3l. :)
\nPersze, okos a szerver, ha menet k\u00f6zben \u00e9szreveszi, hogy nem a legszelekt\u00edvebb filter van el\u00f6l, \u00e1trendezi a list\u00e1j\u00e1t. Ez v\u00e9g\u00fcl is minim\u00e1lis statisztik\u00e1z\u00e1ssal nyomonk\u00f6vethet\u0151 a r\u00e9sz\u00e9r\u0151l.<\/p>\n

A bitmap filtert csak p\u00e1rhuzamos tervek eset\u00e9n haszn\u00e1lja az SQL Server. Meg lehet n\u00e9zni<\/a>, hogy mutat ez a v\u00e9grehajt\u00e1si tervben, n\u00e9mi magyar\u00e1zattal. Berakom ide a is a k\u00e9pet, szokjuk:<\/p>\n

\"Bitmap<\/a>
\nA v\u00e9grehajt\u00e1si terven l\u00e1that\u00f3, hogy a FactInternetSales t\u00e1bla tartalm\u00e1t el\u0151sz\u0171ri a fenti k\u00e9t bitmap filterrel.
\nAz SQL 2005 is tudta m\u00e1r ezt, csak az statikusan, a terv gener\u00e1l\u00e1sa k\u00f6zben d\u00f6nt\u00f6tte el, hogy haszn\u00e1lni fog filtert, m\u00edg az SQL 2008 a k\u00f6zbens\u0151 join-ok v\u00e9grehajt\u00e1sa k\u00f6zben is dinamikusan tud d\u00f6nteni r\u00f3la, ej, el\u00e9g volt a hagyom\u00e1nyos hash joinb\u00f3l, itt bizony bitmap filtereket kell \u00e9p\u00edteni.
\nJ\u00f3, mi?<\/p>\n","protected":false},"excerpt":{"rendered":"

Advanced t\u00e9ma j\u00f6n, de nagyon fincsi. Star join az, amikor egy t\u00e1bl\u00e1hoz sok m\u00e1sik t\u00e1bl\u00e1t kapcsoluk hozz\u00e1. Tipikusan adatt\u00e1rh\u00e1zakban van ilyen, ahogy…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[6,4,30,58],"tags":[],"class_list":["post-495","post","type-post","status-publish","format-standard","hentry","category-adatbazisok","category-szakmai-elet","category-sql-server","category-sql-server-2008"],"_links":{"self":[{"href":"https:\/\/soci.hu\/blog\/index.php\/wp-json\/wp\/v2\/posts\/495","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/soci.hu\/blog\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/soci.hu\/blog\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/soci.hu\/blog\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/soci.hu\/blog\/index.php\/wp-json\/wp\/v2\/comments?post=495"}],"version-history":[{"count":0,"href":"https:\/\/soci.hu\/blog\/index.php\/wp-json\/wp\/v2\/posts\/495\/revisions"}],"wp:attachment":[{"href":"https:\/\/soci.hu\/blog\/index.php\/wp-json\/wp\/v2\/media?parent=495"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/soci.hu\/blog\/index.php\/wp-json\/wp\/v2\/categories?post=495"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/soci.hu\/blog\/index.php\/wp-json\/wp\/v2\/tags?post=495"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}