PA152: Efektivní využívání DB 5. Hašování Vlastislav Dohnal PA152, Vlastislav Dohnal, FI MUNI, 2012 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, 2012 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íč) adresa PA152, Vlastislav Dohnal, FI MUNI, 2012 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, 2012 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 . . . adresa odkaz na záznam PA152, Vlastislav Dohnal, FI MUNI, 2012 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, 2012 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, 2012 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, 2012 9 Základní pojmy  Hašovací funkce  Kolize Na vypočtené adrese je již něco uloženo Není problém, pokud lze uložit více klíčů  Přetečení Kapacita 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, 2012 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, 2012 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, 2012 12 Příklad vkládání  h(b) = 2 0 1 2 3 b a c d PA152, Vlastislav Dohnal, FI MUNI, 2012 13 Příklad vkládání  h(e) = 1 0 1 2 3 b a c d e PA152, Vlastislav Dohnal, FI MUNI, 2012 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, 2012 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, 2012 16 Příklad mazání  Uvolňovat přetokové oblasti  Smaž a 0 1 2 3 a e d PA152, Vlastislav Dohnal, FI MUNI, 2012 17 Empirická znalost  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, 2012 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, 2012 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, 2012 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, 2012 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, 2012 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, 2012 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, 2012 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, 2012 25 Lineární hašování  Idea: Využití pouze několika posledních bitů adresy  Konkrétně i bitů Žádný adresář Soubor roste lineárně h (klíč)[i ] 00 Kyblíky 1000 1100 0001 1011 0010 1 10 PA152, Vlastislav Dohnal, FI MUNI, 2012 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, 2012 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, 2012 28 Lineární hašování: štěpení kyblíku  Při vkládání kontroluj naplnění >80%, pak rozděl kyblík (jehož adresa je 0abcd…z)  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, 2012 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, 2012 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, 2012 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, 2012 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, 2012 33 Bitmapový (rastrový) index  Kolekce bitových polí Pro každou hodnotu je jedno pole Délka pole je počet záznamů = invertovaný soubor  Vhodné pro atributy s „malým“ počtem hodnot PA152, Vlastislav Dohnal, FI MUNI, 2012 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 Hodnota Vektor PA152, Vlastislav Dohnal, FI MUNI, 2012 35 Bitmapový index: vlastnosti  Nevýhody Paměťová náročnost  Pokud je klíč primárním klíčem, pak zabírá n(n log2 n) 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, 2012 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: 0000 0000 0000 0110 001  Najdi první nulu  počet bitů pro uložení i  Načti i  Vlastnost  Sekvence vždy končí jedničkou  Chybějící nuly lze doplnit podle počtu záznamů PA152, Vlastislav Dohnal, FI MUNI, 2012 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, 2012 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, 2012 39 Bitmapový index: řešení  Ad 1: (Nalezení bitového pole pro konkrétní hodnotu klíče) 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: (Mám bitové pole, jak načtu záznamy?) Nalezení záznamu x (pořadí záznamu)  Sekvenční soubor  snadné  Sekundární index pro čísla záznamů PA152, Vlastislav Dohnal, FI MUNI, 2012 40 Bitmapový index: řešení  Ad 3: (Aktualizace záznamů, co s indexem?) Čísla záznamů jsou fixní  Mazání záznamu  náhrobek v souboru a změna 1 na 0 v jednom bitovém poli  smazání 1 bitu ve všech 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, 2012 41 Víceklíčový index  Index pro více atributů  Důvod: SELECT jméno, plat FROM zam WHERE oddělení=‘Hračky’ ANDplat < 10000  Řešení a) Index pro jeden atribut + filtrování b) Oddělené indexy pro atributy + průnik vyhovujících c) Index v indexu d) Spojení klíčů v jeden PA152, Vlastislav Dohnal, FI MUNI, 2012 42 Index pro jeden atribut  SELECT jméno, plat FROM zam WHERE oddělení=‘Hračky’ ANDplat < 10000  Index pro oddělení Nalezené záznamy filtruj pomocí plat < 10000 I1 PA152, Vlastislav Dohnal, FI MUNI, 2012 43 Nezávislé indexy  Index pro oddělení  Index pro plat  Každý index vrátí seznam kandidátů Průnik seznamů  výsledek dotazu oddělení=‘Hračky’ plat<10000 bucket with record pointers PA152, Vlastislav Dohnal, FI MUNI, 2012 44 Index v indexu  Index pro první atribut V listu je odkaz na index pro druhý atribut I1 pro oddělení Ix, x=2..k pro plat  I2 obsahuje pouze záznamy se stejným oddělením (Elektro) I1 I2 I3 Elektro Hračky … PA152, Vlastislav Dohnal, FI MUNI, 2012 45 Index v indexu: příklad  SELECT jméno, plat FROM zam WHERE oddělení=‘Hračky’ ANDplat < 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, 2012 46 Index v indexu  Pro které dotazy je použitelný? SELECT jméno, plat FROM zam WHERE a) oddělení = ‘Hračky’ AND plat ≥ 10000 b) oddělení = ‘Hračky’ c) 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, 2012 47 Spojení klíčů v jeden  Podobné indexu pro jeden klíč Hodnota klíče je spojená  Spojení řetězců, vynásobení čísel, …  V indexování příliš nepoužívá  V hašování dělená hašovací funkce (Partitioned hash function) PA152, Vlastislav Dohnal, FI MUNI, 2012 48 Dělená hašovací funkce  Idea: Dva klíče Dvě hašovací funkce Jedna adresa h1 h2 010110 1110010 Klíč1 Klíč2 Adresa PA152, Vlastislav Dohnal, FI MUNI, 2012 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, 2012 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, 2012 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, 2012 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, 2012 53 Jiný víceklíčový index  Grid (mřížka)  Idea: Záznamy s klíč1=V3, klíč2=X2 V1 V2 Vn X1 X2 … Xm … Klíč1 Klíč2 PA152, Vlastislav Dohnal, FI MUNI, 2012 54 Grid: vlastnosti  Rychlé pro přesné dotazy klíč1 = Vi  klíč2 = Xj klíč1 = Vi klíč2 = Xj  Rozsahové dotazy klíč1  V3  klíč2 < X3  Vznikne čtvercová oblast V1 V2 Vn X1 X2 … Xm … Klíč1 Klíč2 V3 X3 PA152, Vlastislav Dohnal, FI MUNI, 2012 55 Grid: implementace  Jak ukládat mřížku na disku? Jako pole Problém: rozměr mřížky vs. velikost buňky  Nevýhoda Potřeba pevného rozměru mřížky pro výpočet indexu políčka v poli. Omezená velikost buňky X1 X2 X3 X4 X1 X2 X3 X4 X1 X2 X3 X4 V1 V2 V3 PA152, Vlastislav Dohnal, FI MUNI, 2012 56 Grid: implementace  Použití kyblíků, tj. nepřímé adresování Buňka 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, 2012 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 hodnot  Např. číselné domény Lineární růst 1 2 3 Hračky Elektro Zahrada 0-20000 1 20000-50000 2 50000- 3 Plat Grid Oddělení PA152, Vlastislav Dohnal, FI MUNI, 2012 58 Grid index: hodnocení  Výhody Vhodné pro víceklíčové indexy  Nevýhody Mřížka je pevná, zabírá místo  Řešením může být hierarchický grid Volba rozsahů mřížky  rovnoměrné rozdělení dat