PA152: Efektivní využívání DB 6. Hašování Vlastislav Dohnal PA152, Vlastislav Dohnal, FI MUNI, 2009 2 Poděkování Zdrojem materiálů tohoto předmětu jsou: Přednášky CS245, CS345, CS345 Hector Garcia-Molina, Jeffrey D. Ullman, Jennifer Widom Stanford University, California PA152, Vlastislav Dohnal, FI MUNI, 2009 3 Hašování Transformace klíče na adresu Funkce vracející adresu pro vstupní klíč Idea: . . . Kyblíky (obvykle 1 blok) klíč h (klíč) PA152, Vlastislav Dohnal, FI MUNI, 2009 4 Možnosti implementace Přímá adresace Adresa záznamu Obvykle adresa bloku Soubor (seznam bloků) klíč h (klíč) . . . Záznam s . . . PA152, Vlastislav Dohnal, FI MUNI, 2009 5 Možnosti implementace Nepřímá adresace Vhodné pro sekundární indexy Přidává režii . . . Kyblíky (obvykle 1 blok) klíč h (klíč) Soubor (seznam bloků) . . . Záznam s . . . PA152, Vlastislav Dohnal, FI MUNI, 2009 6 Příklad hašovací funkce Klíč je řetězec znaků n bajtů Adresní prostor B kyblíků Hašovací funkce h(x0x1...xn-1) (x0+x1+...+xn-1) mod B (x0*31n-1+x1*31n-2+...+xn-1) mod B Lze i na proměnlivou délku PA152, Vlastislav Dohnal, FI MUNI, 2009 7 Hašovací funkce Požadavky: Rovnoměrná Stejné obsazení všech kyblíků Náhodná Bez korelace vstupu a výstupu ,,Velká věda" speciální literatura Dobrá funkce je alespoň rovnoměrná PA152, Vlastislav Dohnal, FI MUNI, 2009 8 Použití kyblíků Kyblík má větší kapacitu než 1 Uspořádávat klíče? Ano, pokud chceme zrychlit přístup Ano, pokud je málo aktualizací Ne, pokud je hodně aktualizací PA152, Vlastislav Dohnal, FI MUNI, 2009 9 Základní pojmy Hašovací funkce Kolize Na vypočtené adrese je již něco uloženo Není problém, pokud je lze uložit více klíčů Přetečení Kapacity kyblíku je naplněna Přetoková oblast Statické vs. dynamické hašování Podle změny velikosti adresového prostoru PA152, Vlastislav Dohnal, FI MUNI, 2009 10 Řešení kolizí Uzavřené hašování Vypočtená adresa je fixní Při přetečení vytvoř nový kyblík (přetoková oblast) Řetězení přetokových oblastí Otevřené hašování Existence kolizní funkce Lineární, kvadratické, dvojité hašování Viz Organizace souborů PA152, Vlastislav Dohnal, FI MUNI, 2009 11 Příklad Statické uzavřené hašování Kolize pomocí přetokových oblastí Kapacita kyblíku = 2 klíče 0 1 2 3 h (klíč) PA152, Vlastislav Dohnal, FI MUNI, 2009 12 Příklad vkládání h(b) = 2 0 1 2 3 b a c d PA152, Vlastislav Dohnal, FI MUNI, 2009 13 Příklad vkládání h(e) = 1 0 1 2 3 b a c d e PA152, Vlastislav Dohnal, FI MUNI, 2009 14 Příklad mazání Uvolňovat přetokové oblasti Smaž b 0 1 2 3 b a c d e PA152, Vlastislav Dohnal, FI MUNI, 2009 15 Příklad mazání Uvolňovat přetokové oblasti Smaž c 0 1 2 3 a c e d e PA152, Vlastislav Dohnal, FI MUNI, 2009 16 Příklad mazání Uvolňovat přetokové oblasti Smaž a 0 1 2 3 a e d PA152, Vlastislav Dohnal, FI MUNI, 2009 17 Empirické zkušenosti Zaplnění udržovat mezi 50% a 80% Zaplněnost = počet klíčů / max. kapacita < 50% ­ plýtvání místem 80% ­ příliš mnoho kolizí Přetokové oblasti zpomalují vyhledávání i vkládání PA152, Vlastislav Dohnal, FI MUNI, 2009 18 Dynamická data Statické hašování Přetoky reorganizace Tj. vytvoření nové hašovací funkce Dynamické hašování Rozšiřitelné Lineární PA152, Vlastislav Dohnal, FI MUNI, 2009 19 Rozšiřitelné hašování Idea: Využití pouze několika prvních bitů adresy Přidání další tabulky ­ adresář Velikost je mocnina 2 h (klíč)[i ] 0 1 2 Kyblíky 1 2 2 Adresář 2 PA152, Vlastislav Dohnal, FI MUNI, 2009 20 Rozšiřitelné hašování: vkládání Najdi kyblík je volné místo ok není rozštěpení kyblíku přerozdělení obsahu Vložení 0001 1010 200 01 10 11 0 1 2 1000 1111 1 0100 2 0001 2 1010 PA152, Vlastislav Dohnal, FI MUNI, 2009 21 Rozšiřitelné hašování: vkládání Vložení 1010 Rozštěpení kyblíku 200 01 10 11 1000 1010 2 0100 2 0001 2 1111 2 PA152, Vlastislav Dohnal, FI MUNI, 2009 22 Rozšiřitelné hašování: vkládání Vložení 1011 Adresář je plný zdvojnásobení (přidání bitu) 3000 001 010 011 1000 3 0100 2 0001 2 1010 1011 3 100 101 110 111 1111 2 PA152, Vlastislav Dohnal, FI MUNI, 2009 23 Rozšiřitelné hašování: mazání Mazání klíče Smaž klíč Kyblík je prázdný Nedělej nic předpoklad nového vkládání Sloučení sousedních kyblíků Mající stejný prefix o jeden bit kratší Může být i zmenšen adresář PA152, Vlastislav Dohnal, FI MUNI, 2009 24 Rozšiřitelné hašování: hodnocení Výhody Měnící se data Méně plýtvá místem (než statické hašování) Lokální reorganizace Nevýhody Další úroveň nepřímých odkazů Ok, pokud je adresář v paměti Adresář se zdvojnásobuje Nemusí se vejít do paměti Ale kyblíky rostou lineárně! PA152, Vlastislav Dohnal, FI MUNI, 2009 25 Lineární hašování Idea: Využití pouze několika posledních bitů adresy Žádný adresář Soubor roste lineárně h (klíč)[i ] 00 Kyblíky 1000 1100 0001 1011 0010 1 10 PA152, Vlastislav Dohnal, FI MUNI, 2009 26 Lineární hašování: vkládání Parametry: i=2, n=3 Vlož 1011 h(1011)[2] = 11 = m Pokud m < n, vlož do kyblíku m Jinak vlož do kyblíku m ­ 2i-1 h (klíč)[i ] 00 1000 1100 1 0001 1011 10 0010 PA152, Vlastislav Dohnal, FI MUNI, 2009 27 Lineární hašování: vkládání Vlož 1001 h(1001)[2] = 01 Není místo přetoková oblast h (klíč)[i ] 00 1000 1100 1 0001 1011 10 0010 1001 PA152, Vlastislav Dohnal, FI MUNI, 2009 28 Lineární hašování: štěpení kyblíku Při vkládání kontroluj naplnění >80%, pak rozděl kyblík Resp. přidej nový adresa je 1abcd...z Rozděl data v kyblíku 0abcd...z mezi [01]abcd...z h (klíč)[i ] 00 1000 1100 01 0001 1001 10 0010 1001 11 1011 PA152, Vlastislav Dohnal, FI MUNI, 2009 29 Lineární hašování Vkládání nového klíče Může vést k přetokové oblasti Může způsobit větší naplnění než 80% Provede se štěpení kyblíku Štěpený kyblík může být různý od kyblíku, do kterého se vkládá! Po přidání 2i-tého kyblíku, zvětši i Tj. počet kyblíků překročí 2i PA152, Vlastislav Dohnal, FI MUNI, 2009 30 Lineární hašování: hodnocení Výhody Měnící se data Méně plýtvá místem (než statické hašování) Lokální reorganizace Žádná dodatečná překladová tabulka Nevýhody Přetokové oblasti PA152, Vlastislav Dohnal, FI MUNI, 2009 31 Lineární hašování: příklad ,,Chybná" data Prvních x bitů nerozliší klíče Jeden kyblík má všechna data, ostatní nic Faktor naplnění vysoký stále se štěpí h (klíč)[i ] ... PA152, Vlastislav Dohnal, FI MUNI, 2009 32 Hašování vs. indexování Hašování Vhodné pro přesné dotazy SELECT ... WHERE a=5 Indexování Vhodné pro rozsahové dotazy SELECT ... WHERE a>5 PA152, Vlastislav Dohnal, FI MUNI, 2009 33 Bitmapový index Kolekce bitových polí Pro každou hodnotu je jedno pole Délka pole je počet záznamů Vhodné pro atributy s ,,malým" počtem hodnot PA152, Vlastislav Dohnal, FI MUNI, 2009 34 Bitmapový index: příklad Relace R(F,G) Bitmapový index pro G 50 foo 30 foo 30 bar 40 baz 30 baz 40 bar F G foo 100100 bar 010010 baz 001001 Value Vector PA152, Vlastislav Dohnal, FI MUNI, 2009 35 Bitmapový index: vlastnosti Nevýhody Paměťová náročnost Pokud je klíč primárním klíčem, pak zabírá n2 bitů Aktualizace záznamů Vkládání, mazání Nová hodnota nové bitové pole Výhody Rychlé operace na bitech (AND, OR) Lze použít pro rozsahové dotazy Snadné kombinace více indexů dohromady PA152, Vlastislav Dohnal, FI MUNI, 2009 36 Bitmapový index: komprese Zmenšení polí Málo 1, hodně 0 Obvykle Run-Length Encoding (RLE) Sekvence i nul následovaná jedničkou Kódování je uložení čísla i binárně Příklad Kód: 11101101001011 Sekvence: 0000000000000110001 Najdi první nulu počet bitů pro uložení i Načti i Problém Sekvence vždy končí jedničkou! Chybějící nuly lze doplnit podle počtu záznamů PA152, Vlastislav Dohnal, FI MUNI, 2009 37 Bitmapový index: operace Bitové operace AND, OR RLE řetězce Dekomprimovat snadné Bez dekomprese Složitější algoritmus, ale možné AND: čísla i v kódech se musí shodovat OR: analogicky... PA152, Vlastislav Dohnal, FI MUNI, 2009 38 Bitmapový index: použití Otázky pro efektivní použití: 1. Nalezení bitového pole pro konkrétní hodnotu klíče 2. Mám bitové pole, jak načtu záznamy? 3. Aktualizace záznamů, co s indexem? PA152, Vlastislav Dohnal, FI MUNI, 2009 39 Bitmapový index: řešení Ad 1: Pro hodnotu klíče máme bitové pole B+-strom pro hodnoty klíče V listu odkaz na bitové pole Uložení bitových polí Záznamy variabilní délky Ad 2: Nalezení záznamu x (pořadí záznamu) Sekvenční soubor snadné Sekundární index pro čísla záznamů PA152, Vlastislav Dohnal, FI MUNI, 2009 40 Bitmapový index: řešení Ad 3: Čísla záznamů jsou fixní Mazání záznamu náhrobek v souboru změna na nuly ve všech bitových polích Vkládání záznamu přidej na konec souboru (nové číslo záznamu) do správného bitového pole připojit 1 pole nemusí existovat, vytvoř nové Čísla záznamů nejsou fixní Reorganizace všech polí Málo používaná verze PA152, Vlastislav Dohnal, FI MUNI, 2009 41 Víceklíčový index Index pro více atributů Důvod: SELECT ... WHERE oddělení=`Hračky' ANDplat < 10000 Řešení Index pro jeden atribut + filtrování Oddělené indexy pro atributy + průnik vyhovujících Index v indexu Spojení klíčů v jeden PA152, Vlastislav Dohnal, FI MUNI, 2009 42 Index pro jeden atribut SELECT ... WHERE oddělení=`Hračky' AND plat < 10000 Index pro oddělení Nalezené záznamy filtruj pomocí plat < 10000 I1 PA152, Vlastislav Dohnal, FI MUNI, 2009 43 Nezávislé indexy Index pro oddělení Index pro plat Každý index vrátí seznam kandidátů Průnik výsledek dotazu oddělení=`Hračky' plat<10000 PA152, Vlastislav Dohnal, FI MUNI, 2009 44 Index v indexu Index pro první atribut V listu je odkaz na index pro druhý atribut I1 pro oddělení I2 pro plat obsahuje pouze záznamy se stejným oddělením I1 I2 I3 PA152, Vlastislav Dohnal, FI MUNI, 2009 45 Index v indexu: příklad SELECT ... WHERE oddělení=`Hračky' AND plat < 10000 Jméno=Petr Oddělení=Hračky Plat=7000 Elektro Hračky Zahrada 10000 15000 17000 21000 5000 7000 15000 19000 Index oddělení Indexy platů Záznam PA152, Vlastislav Dohnal, FI MUNI, 2009 46 Index v indexu Pro které dotazy je použitelný? SELECT ... WHERE oddělení = `Hračky' AND plat = 10000 oddělení = `Hračky' AND plat 10000 oddělení = `Hračky' plat = 10000 PA152, Vlastislav Dohnal, FI MUNI, 2009 47 Spojení klíčů v jeden Podobné indexu pro jeden klíč Hodnota klíče je spojená Spojení řetězců, vynásobení čísel, ... V indexování se příliš nepoužívá V hašování tzv. dělená hašovací funkce Partitioned hash function PA152, Vlastislav Dohnal, FI MUNI, 2009 48 Dělená hašovací funkce Dva klíče Idea: h1 h2 010110 1110010 Klíč 1 Klíč 2 Adresa PA152, Vlastislav Dohnal, FI MUNI, 2009 49 Dělená hašovací funkce: příklad Oddělení h1(Elektro) =0 h1(Hračky) =1 h1(Zahrada) =1 Plat h2(10000) =01 h2(20000) =11 h2(30000) =10 h2(40000) =00 Záznamy ke vložení 000 001 010 011 100 101 110 111 PA152, Vlastislav Dohnal, FI MUNI, 2009 50 Dělená hašovací funkce: příklad Oddělení h1(Elektro) =0 h1(Hračky) =1 h1(Zahrada) =1 Plat h2(10000) =01 h2(20000) =11 h2(30000) =10 h2(40000) =00 Najdi zaměstnance z oddělení hraček a platem 40000 000 001 010 011 100 101 110 111 PA152, Vlastislav Dohnal, FI MUNI, 2009 51 Dělená hašovací funkce: příklad Oddělení h1(Elektro) =0 h1(Hračky) =1 h1(Zahrada) =1 Plat h2(10000) =01 h2(20000) =11 h2(30000) =10 h2(40000) =00 Najdi zaměstnance s platem 30000 000 001 010 011 100 101 110 111 PA152, Vlastislav Dohnal, FI MUNI, 2009 52 Dělená hašovací funkce: příklad Oddělení h1(Elektro) =0 h1(Hračky) =1 h1(Zahrada) =1 Plat h2(10000) =01 h2(20000) =11 h2(30000) =10 h2(40000) =00 Najdi zaměstnance z oddělení hraček 000 001 010 011 100 101 110 111 PA152, Vlastislav Dohnal, FI MUNI, 2009 53 Jiný víceklíčový index Grid (mřížka) Idea: Záznamy s klíčem1=V3, klíčem2=X2 V1 V2 Vn X1 X2 ... Xm ... Klíč1 Klíč2 PA152, Vlastislav Dohnal, FI MUNI, 2009 54 Grid: vlastnosti Rychlé pro přesné dotazy klíč1 = Vi klíč2 = Xj klíč1 = Vi klíč2 = Xj Rozsahové dotazy klíč1 Vi klíč2 < Xj Vznikne čtvercová oblast PA152, Vlastislav Dohnal, FI MUNI, 2009 55 Grid: implementace Jak ukládat mřížku na disku Jako pole Nevýhoda Potřeba pevné délky pro výpočet indexu políčka X1 X2 X3 X4 X1 X2 X3 X4 X1 X2 X3 X4 V1 V2 V3 PA152, Vlastislav Dohnal, FI MUNI, 2009 56 Grid: implementace Použití kyblíků, tj. nepřímé adresování Políčko mřížky odkazuje na kyblík Nyní je mřížka pevné velikosti Ovšem přibyla režie s odkazy V1 V2 X1 X2 X3 V3 V4 Kyblíky -- ---- -- ---- -- ---- -- ---- ... PA152, Vlastislav Dohnal, FI MUNI, 2009 57 Grid: definice mřížky Analýzou dat a požadavků na hledání Zjistíme rozměry mřížky Políčko mřížky může být i interval Např. číselné domény Lineární růst 1 2 3 Hračky Elektro Zahrada 0-20K 1 20K-50K 2 50K- 3 Plat Grid Oddělení PA152, Vlastislav Dohnal, FI MUNI, 2009 58 Grid index: hodnocení Výhody Vhodné pro víceklíčové indexy Nevýhody Mřížka je pevná, zabírá místo Volba rozsahů mřížky rovnoměrné rozdělení dat