PA152: Efektivní využívání DB 5. Hašování Vlastislav Dohnal PA152, Vlastislav Dohnal, FI MUNI, 2019 2 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, 2019 3 Možnosti implementace ◼ Přímá adresace Adresa záznamu ◼ Obvykle adresa bloku ◼ Vhodné pro hašovaný soubor Soubor (seznam bloků) klíč h (klíč) . . . Záznam s . . . PA152, Vlastislav Dohnal, FI MUNI, 2019 4 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 Přeskoč opakování… PA152, Vlastislav Dohnal, FI MUNI, 2019 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, FI MUNI, 2019 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, 2019 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, FI MUNI, 2019 8 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, 2019 9 Řešení kolizí ◼ Uzavřené adresování (otevř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é adresování (uzavřené hašování) Existence kolizní funkce ◼ Lineární, kvadratické, dvojité hašování ◼ Viz Organizace souborů PA152, Vlastislav Dohnal, FI MUNI, 2019 10 Příklad ◼ Statické uzavřené adresování Kolize pomocí přetokových oblastí Kapacita kyblíku = 2 klíče 0 1 2 3 h (klíč) Přeskoč opakování… Oddělené zřetězení kapes PA152, Vlastislav Dohnal, FI MUNI, 2019 11 Příklad vkládání ◼ h(„b“) = 2 0 1 2 3 b a c d PA152, Vlastislav Dohnal, FI MUNI, 2019 12 Příklad vkládání ◼ h(„e“) = 1 0 1 2 3 b a c d e PA152, Vlastislav Dohnal, FI MUNI, 2019 13 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, 2019 14 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, 2019 15 Příklad mazání ◼ Uvolňovat přetokové oblasti ◼ Smaž „a” 0 1 2 3 a e d PA152, Vlastislav Dohnal, FI MUNI, 2019 16 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, 2019 17 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, 2019 18 Rozšiřitelné hašování ◼ Idea: Využití pouze několika prvních (horní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 0001 PA152, Vlastislav Dohnal, FI MUNI, 2019 19 Rozšiřitelné hašování: vkládání ◼ Příklad: h(x) = x, tj. identita ◼ 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 2 1010 ◼ Při vkládání 1010 Rozštěpení kyblíku 1010 1111 1111 PA152, Vlastislav Dohnal, FI MUNI, 2019 20 Rozšiřitelné hašování: vkládání 200 01 10 11 1000 1 0100 2 0001 2 2 2 PA152, Vlastislav Dohnal, FI MUNI, 2019 21 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, 2019 22 Rozšiřitelné hašování: mazání ◼ Mazání klíče Smaž klíč Kyblík je prázdný a) Nedělej nic → předpoklad nového vkládání b) 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, 2019 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, 2019 24 Lineární hašování ◼ Idea: Využití pouze několika posledních (dolní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, 2019 25 Lineární hašování: vkládání ◼ Parametry: i – délka sufixu => h(k)[i] n – počet kyblíků ◼ Vlož 1011b h(1011b)[2] = 11b = m ◼ Pokud m < n, vlož do kyblíku m ◼ Jinak vlož do kyblíku m – 2i-1 h(1011b)[2] 00 1000 1100 1 0001 1011 10 0010 i=2, n=3 PA152, Vlastislav Dohnal, FI MUNI, 2019 26 Lineární hašování: vkládání ◼ Vlož 1001 h(1001)[2] = 01 Není místo → přetoková oblast h(1001)[2] 00 1000 1100 1 0001 1011 10 0010 1001 PA152, Vlastislav Dohnal, FI MUNI, 2019 27 Lineární hašování: štěpení kyblíku ◼ Při vkládání kontroluj naplnění kyblíku >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 Dělí se vždy adresa (n – 2i-1), tj. 3 – 21 = 1 h(1001)[2] 00 1000 1100 01 0001 1001 10 0010 1001 11 1011 n=4 i=3 PA152, Vlastislav Dohnal, FI MUNI, 2019 28 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 -1 PA152, Vlastislav Dohnal, FI MUNI, 2019 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, 2019 30 Lineární hašování: příklad ◼ „Chybná“ data Poslední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, 2019 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, 2019 32 Bitmapový / Rastrový index ◼ Atribut X má h unikátních hodnot ◼ Kolekce h bitových polí Pro každou hodnotu je jedno pole Délka pole je počet záznamů (n) = invertovaný soubor ◼ Vhodné pro atributy s „malým“ počtem hodnot Typicky <10% záznamů ◼ Relace R(F,G) ◼ Bitmapový index pro G PA152, Vlastislav Dohnal, FI MUNI, 2019 33 Bitmapový index: příklad 50 foo 30 foo 30 bar 40 baz 30 baz 40 bar F G foo 1001001 bar 0100100 baz 0010010 Hodnota Vektor 34 foo PA152, Vlastislav Dohnal, FI MUNI, 2019 34 Bitmapový index: vlastnosti ◼ Nevýhody Paměťová náročnost ◼ Pokud je klíč primárním klíčem, pak n(n + log2 n) bitů ◼ Mnoho záznamů se stejnou hodnotou (mnoho jedniček)  Změň na bitové pole bloků (a nikoli záznamů) Aktualizace záznamů ◼ Nová hodnota → nové bitové pole ◼ Nový záznam → rozšíření všech polí PA152, Vlastislav Dohnal, FI MUNI, 2019 35 Bitmapový index: vlastnosti ◼ Výhody Rychlé operace na bitech (AND, OR) Použitelné i pro rozsahové dotazy Snadné kombinace více indexů dohromady ◼ Typicky jedno-atributové indexy PA152, Vlastislav Dohnal, FI MUNI, 2019 36 Bitmapový index: komprese ◼ Zmenšení polí  Málo 1, hodně 0  Obvykle Run-Length Encoding (RLE) ◼ RLE Rozdělení na části ◼ Sekvence „i“ nul následovaná jedničkou Číslo „i“ uložit binárně Kód čísla „i“ je „Délka binárního kódu i, vlastní číslo i“ ◼ Vlastnost Sekvence vždy končí jedničkou Chybějící nuly na konci lze doplnit podle počtu záznamů PA152, Vlastislav Dohnal, FI MUNI, 2019 37 Bitmapový index: RLE ◼ Příklad komprese – 24 bitů  Sekvence: 0000 0000 0000 0110 0010 0000 ◼ 13x nula, 1x jednička ◼ 0x nula, 1x jednička ◼ 3x nula, 1x jednička ◼ 5x nula a nic…. → ignoruji  Binárně tedy: ◼ 13d → 1101b ◼ 0d → 0b ◼ 3d → 11b Kód RLE: ◼ Posloupnost „částí“:  délka čísla v prefixovém kódu, pak binární číslo ◼ Kód: 11101101001011 PA152, Vlastislav Dohnal, FI MUNI, 2019 38 Bitmapový index: RLE ◼ Příklad dekomprese Kód 11101101001011 Rozdělení na části a dekomprese… ◼ Délka binárního čísla:  počet bitů (jednička a pak nula) ◼ 11101101001011 Dekódovaní částí ◼ 11101101 → 0000 0000 0000 01 ◼ 00 → 1 ◼ 1011 → 0 001 Výsledná sekvence: ◼ 0000 0000 0000 0110 001 ◼ Chybějící nuly na konci lze doplnit podle počtu záznamů PA152, Vlastislav Dohnal, FI MUNI, 2019 39 Bitmapový index: operace ◼ Bitové operace AND, OR ◼ RLE řetězce Dekomprimovat → snadné Bez dekomprese ◼ Složitější algoritmus, ale možné ◼ AND: suma čísel i v kódech se musí shodovat ◼ OR: analogicky… ◼ 11101101001011 OR/AND 1101011101001010 PA152, Vlastislav Dohnal, FI MUNI, 2019 40 Bitmapový index: implementace ◼ 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, 2019 41 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 r (pořadí záznamu) ◼ Sekundární index pro čísla záznamů ◼ Pole odkazů na záznamy (náhrada za bit. pole) ◼ Seznam počtu záznamů v blocích PA152, Vlastislav Dohnal, FI MUNI, 2019 42 Bitmapový index: řešení ◼ Ad 3: (Aktualizace záznamů, co s indexem?) Čísla záznamů jsou fixní ◼ Mazání záznamu → náhrobek v indexu/souboru a změna 1 na 0 v jednom bitovém poli ◼ 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é PA152, Vlastislav Dohnal, FI MUNI, 2019 43 Bitmapový index: řešení ◼ Ad 3: (Aktualizace záznamů, co s indexem?) Čísla záznamů nejsou fixní ◼ Reorganizace všech polí (zrušení 1 bitu) ◼ Aktualizace pole s odkazy na záznamy ◼ Málo používaná verze Bitmaps -- data Settings: lineitem ( L_ORDERKEY, L_PARTKEY , L_SUPPKEY, L_LINENUMBER, L_QUANTITY, L_EXTENDEDPRICE , L_DISCOUNT, L_TAX , L_RETURNFLAG, L_LINESTATUS , L_SHIPDATE, L_COMMITDATE, L_RECEIPTDATE, L_SHIPINSTRUCT , L_SHIPMODE , L_COMMENT ); create bitmap index b_lin_2 on lineitem(l_returnflag); create bitmap index b_lin_3 on lineitem(l_linestatus); create bitmap index b_lin_4 on lineitem(l_linenumber);  100000 rows ; cold buffer  Dual Pentium II (450MHz, 512KB), 512 MB RAM, 3x18GB drives (10000RPM), Windows 2000. PA152, Vlastislav Dohnal, FI MUNI, 2019 44 Bitmaps -- queries Queries:  1 attribute select count(*) from lineitem where l_returnflag = 'N';  2 attributes select count(*) from lineitem where l_returnflag = 'N' and l_linenumber > 3;  3 attributes select count(*) from lineitem where l_returnflag = 'N' and l_linenumber > 3 and l_linestatus = 'F'; PA152, Vlastislav Dohnal, FI MUNI, 2019 45 46 Bitmaps ◼ Order of magnitude improvement compared to scan. ◼ Bitmaps are best suited for multiple conditions on several attributes, each having a low selectivity. A N R l_returnflag O F l_linestatus 0 2 4 6 8 10 12 1 2 3 Throughput(Queries/sec) linear scan bitmap PA152, Vlastislav Dohnal, FI MUNI, 2019 PA152, Vlastislav Dohnal, FI MUNI, 2019 47 Víceklíčový / Kompozitní index ◼ Index nad více atributy ◼ 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) Nezávislé indexy pro atributy + průnik vyhovujících c) Index v indexu d) Spojení klíčů v jeden PA152, Vlastislav Dohnal, FI MUNI, 2019 48 Index pro jeden atribut ◼ SELECT jméno, plat FROM zam WHERE oddělení=‘Hračky’ AND plat < 10000 ◼ Index pro oddělení Nalezené záznamy načítej a filtruj pomocí plat < 10000 I1 PA152, Vlastislav Dohnal, FI MUNI, 2019 49 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, 2019 50 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, 2019 51 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, 2019 52 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, 2019 53 Spojení klíčů v jeden ◼ Podobné indexu pro jeden klíč Hodnota klíče je spojená ◼ Spojení řetězců, kombinace čísel, … ◼ V indexování bez komprimace se příliš nepoužívá ◼ V hašování dělená hašovací funkce (Partitioned hash function) PA152, Vlastislav Dohnal, FI MUNI, 2019 54 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, 2019 55 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 k vložení  000 001 010 011 100 101 110 111 PA152, Vlastislav Dohnal, FI MUNI, 2019 56 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, 2019 57 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, 2019 58 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, 2019 59 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, 2019 60 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 ◼ 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 PA152, Vlastislav Dohnal, FI MUNI, 2019 61 Grid: implementace X1 X2 X3 X4 X1 X2 X3 X4 X1 X2 X3 X4 V1 V2 V3 PA152, Vlastislav Dohnal, FI MUNI, 2019 62 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, 2019 63 Grid: definice mřížky ◼ Analýzou dat a požadavků na hledání Zjistíme rozměry mřížky Hodnota osy mřížky může být i interval ◼ 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, 2019 64 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 Další pojmy ◼ Clustered index  = index-sekvenční soubor / B-file  Záznamy jsou v listech indexu a nelze je načítat jinak než prostřednictvím indexu ◼ Non-clustered index  = sekundární index / B-strom ◼ Pokrývající index (Covering index)  Význam: dotaz lze vyřešit použitím indexu a bez přístupu k celým záznamům  MS SQL Server: Index se zahrnutými sloupci ◼ Není více atributovým indexem, ale obsahuje v listech hodnoty i pro další atributy ◼ Indexovaný pohled  materializovaný pohled s clustered indexem PA152, Vlastislav Dohnal, FI MUNI, 2019 65 Návrh indexů ◼ Dobrá selektivita ◼ Co „nejkratší“ atributy zvýšení arity stromu ◼ Pro atributy pro spojení více relací ◼ Raději více indexů než jeden víceatributový ◼ Málo indexů pro často aktualizované tabulky ◼ Žádné indexy pro malinké tabulky PA152, Vlastislav Dohnal, FI MUNI, 2019 66