PA152: Efektivní využívání DB 5. Hašování Vlastislav Dohnal "a1 ^^^^^^^^^^^^^^^^^^^^^^^^^^^ 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 2 Hašování ■ Transformace klíče na adresu □ Funkce vracející adresu pro vstupní klíč ■ Idea: klíč ^ h (klíč) Kyblíky (obvykle 1 blok) PA152, Vlastislav Dohnal, FI MUNI, 2009 v ^^^^^^^^^^^^^^^^^^^^^^^^ Možnosti implementace ■ Přímá adresace □ Adresa záznamu ■ Obvykle adresa bloku , klíč Záznam s Soubor (seznam bloků) PA152, Vlastislav Dohnal, FI MUNI, 2009 4 Možnosti implementace ■ Nepřímá adresace □ Vhodné pro sekundární indexy □ Pridáva rezu klíč h (klíč) Kyblíky (obvykle 1 blok) /v ■ ■ Záznam s ■ ■ ■ ■ ■ ■ Soubor (seznam bloků) PA152, Vlastislav Dohnal, FI MUNI, 2009 5 ■ ^^^^^^^^^^^^^^^^^^^^^^^^^^^ 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, Fl MUNl, 2009 6 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 7 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, Fl MUNI, 2009 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, Fl MUNI, 2009 Ř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, Fl MUNI, 2009 in Příklad ■ Statické uzavřené hašování □ Kolize pomocí přetokových oblastí □ Kapacita kyblíku = 2 klíče h (klíč) 0 i 2 3 PA152, Vlastislav Dohnal, FI MUNI, 2009 11 Příklad vkládání ■ 0 d 1 a c 2 b 3 PA152, Vlastislav Dohnal, FI MUNI, 2009 12 Příklad vkládání ■ h(e) = 1 0 1 2 3 d a c b Kil e PA152, Vlastislav Dohnal, FI MUNI, 2009 13 Příklad mazání ■ Uvolňovat přetokové oblasti ■ Smaž □ b 0 i 2 3 d a KU c b e PA152, Vlastislav Dohnal, FI MUNI, 2009 14 Príklad mazaní ■ Uvolňovat pretokové oblasti ■ SmaZ □ c 0 1 2 3 a c e PA152, Vlastislav Dohnal, FI MUNI, 2009 15 Príklad mazaní ■ Uvolňovat pretokové oblasti ■ SmaZ □ a 0 1 2 3 e PA152, Vlastislav Dohnal, FI MUNI, 2009 16 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 17 "a1 ^^^^^^^^^^^^^^^^^^^^^^^^^^^ 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, Fl MUNl, 2009 18 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íč)[/ ] 0 1 2 Adresář 2 2 1 Kyblíky PA152, Vlastislav Dohnal, FI MUNI, 2009 19 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 00 01 10 ► 0 i 2 0001 0100 1000 2 2 1 1010 ...........................................I -•- Nrf 1111 I PA152, Vlastislav Dohnal, Fl MUNl, 2009 2n Rozšiřitelné hašování: vkládání ■ Vložení □ 1010 □ Rozštěpení kyblíku 00 01 10 11 0001 2 0100 2 1000 2 1010 1111 2 PA152, Vlastislav Dohnal, FI MUNI, 2009 21 Rozšiřitelné hašování: vkládání ■ Vložení 1011 □ Adresář je plný zdvojnásobení (přidání bitu) 000 001 010 011 100 101 110 111 0001 2 0100 2 1000 3 1010 3 1011 1111 2 PA152, Vlastislav Dohnal, Fl MUNl, 2009 22 BJ ^^^^^^^^^^^^^^^^^^^^^^^^^^^ Rozšiřitelné hašovaní: mazaní ■ 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 23 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 24 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ě 00 i_i ! i_i 10 PA152, Vlastislav Dohnal, FI MUNI, 2009 25 Lineární hašování: vkládání ■ Parametry: /=2, n=3 ■ Vlož 1011 □ h(1011)[2] = 11 = m ■ Pokud m < n, vlož do kyblíku m ■ Jinak vlož do kyblíku m - 2M 1000 I 0001 I 0010 1100 1011 PA152, Vlastislav Dohnal, FI MUNI, 2009 26 Lineární hašovaní: vkladaní ■ VloZ 1001 □ h(1001)[2] = 01 □ Není místo -> přetokova oblast h (klíč)[/ ] 1000 0001 0010 1100 nn 1 1011 1 i *•< 1001 PA152, Vlastislav Dohnal, FI MUNI, 2009 27 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 1000 0001 0010 I 1011 1100 1001 00 01 Lv 10 l-1 11 1001 PA152, Vlastislav Dohnal, Fl MUNl, 2009 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čí 2' PA152, Vlastislav Dohnal, FI MUNI, 2009 29 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 .in "J ^^^^^^^^^^^^^^^^^^^^^^^^^^^ Lineární hašování: příklad ■ „Chybná" data □ Prvních x bitů nerozliší klíče h (klíč)[/]-—\ □ Jeden kyblík má všechna data, ostatní nic ■ Faktor naplnění vysoký — stále se štěpí PA152, Vlastislav Dohnal, Fl MUNl, 2009 31 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 32 Bitmapový index ■ Kolekce bitových polí □ Pro každou hodnotu je jedno pole □ Délka pole je počet záznamů □ Tj. je to invertovaný soubor ■ Vhodné pro atributy s „malým" počtem hodnot PA152, Vlastislav Dohnal, FI MUNI, 2009 33 Bitmapový index: příklad m Relace R(F,G) F G BO foo BO bar 4O baz SO foo 4O bar BO baz ■ Bitmapový index pro G Hodnota Vektor foo lOOlOO bar OlOOlO baz OOlOOl PA152, Vlastislav Dohnal, FI MUNI, 2009 34 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 .15 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 36 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 37 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 38 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, 2009 39 "d ^^^^^^^^^^^^^^^^^^^^^^^^^^^ 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, 2009 40 Víceklíčový index ■ Index pro více atributů ■ Důvod: SELECT ... WHERE oddělení='Hračky' AND plat < 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, 2009 41 Index pro jeden atribut ■ SELECT ... WHERE oddělení=tHračky' AND plat < 10000 ■ Index pro oddělení □ Nalezené záznamy filtruj pomocí plat < 10000 PA152, Vlastislav Dohnal, FI MUNI, 2009 42 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 PA152, Vlastislav Dohnal, FI MUNI, 2009 43 Index v indexu ■ Index pro první atribut □ V listu je odkaz na index pro druhý atribut Elektro^ 10000 c) oddělení = 'Hračky' d) plat = 10000 Elektro - Hračky Zahrada v V Index oddělení Indexy platů Jméno=Petr Oddělení=Hračky Plat=7000 Záznam PA152, Vlastislav Dohnal, Fl MUNI, 2009 46 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 47 Dělená hašovací funkce ■ Idea: □ Dva klíče □ Dvě hašovací funkce □ Jedna adresa Adresa 010110 1110010 Y Y í í Klíč1 —► (h!) (h2) <— Klíč2 PA152, Vlastislav Dohnal, FI MUNI, 2009 48 Dělená hašovací funkce: ■ Oddělení ■ ■ h1(Elektro) =0 000 h1(Hračky) =1 h1(Zahrada) =1 001 Plat 010 h2(10000) =01 011 h2(20000) =11 100 h2(30000) =10 101 h2(40000) =00 110 Záznamy ke vložení 111 □ □ □ příklad PA152, Vlastislav Dohnal, FI MUNI, 2009 49 Dělená hašovací funkce: ■ Oddělení h1(Elektro) h1(Hračky) h1(Zahrada) Plat h2(10000) h2(20000) h2(30000) h2(40000) Najdi příklad ■ ■ =0 =1 =1 000 001 010 011 =01 100 =11 101 =10 110 =00 111 □ zaměstnance z oddělení hraček a platem 40000. PA152, Vlastislav Dohnal, FI MUNI, 2009 50 m Dělená hašovací funkce: ■ Oddělení h1(Elektro) h1(Hračky) h1(Zahrada) Plat h2(10000) h2(20000) h2(30000) h2(40000) Najdi □ zaměstnance s platem 30000 příklad ■ =0 =1 =1 000 001 010 011 =01 100 =11 101 =10 110 =00 111 PA152, Vlastislav Dohnal, FI MUNI, 2009 51 Dělená hašovací funkce: ■ Oddělení h1(Elektro) h1(Hračky) h1(Zahrada) Plat h2(10000) h2(20000) h2(30000) h2(40000) Najdi □ zaměstnance z oddělení hraček příklad ■ ■ =0 =1 =1 000 001 010 011 =01 100 =11 101 =10 110 =00 111 PA152, Vlastislav Dohnal, FI MUNI, 2009 52 Jiný víceklíčový index m Grid (mřížka) a Idea: r Vi V2 Klíčl < K. Vn Klíč2 Xm Záznamy s klíčeml=V3, klíčem2=X2 PA152, Vlastislav Dohnal, FI MUNI, 2009 53 Grid: vlastnosti ■ ■ Rychlé pro přesné dotazy □ klíč1 = Vi a klíč2 = Xj □ klíč1 = Vi □ klíč2 = Xj Rozsahové dotazy □ klíč1 > V3 a klíč2 < X3 ■ Vznikne čtvercová oblast r Klíq < v1 vn Klíč2 X1 X2 X3 PA152, Vlastislav Dohnal, FI MUNI, 2009 54 Grid: implementace ■ Jak ukládat mřížku na disku? □ Jako pole Vi V2 V3 i r\i! H <\H XI XI XI -ť1Ji i-Í Csl CO XX X ! X! t4 c4 h <šT X! XI XI X □ Problém: rozměr Gridu vs. velikost buňky Gridu ■ Nevýhoda □ Potřeba pevného rozměru Gridu pro výpočet indexu políčka v poli. □ Omezená velikost políčka Gridu PA152, Vlastislav Dohnal, Fl MUNI, 2009 55 Grid: implementace ■ Použití kyblíků, tj. nepřímé adresování □ Políčko mřížky odkazuje na kyblík X1 X2 X3 ■ V1 V2 V4 Nyní je mřížka pevné velikosti □ Ovšem přibyla režie s odkazy ■ ■ ■ PA152, Vlastislav Dohnal, FI MUNI, 2009 56 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 Grid Plat G-2GGGG i - 2GGGG-5GGGG 2 - 5OOOO-00 3 - Oddělení 21 V 3 Hračky Elektro Zahrada PA152, Vlastislav Dohnal, FI MUNI, 2009 57 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 PA152, Vlastislav Dohnal, FI MUNI, 2009 58