PA152: Efektivní využívání DB 5. Hašování Vlastislav Dohnal PA152, Vlastislav Dohnal, FI MUNI, 2018 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, 2018 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, 2018 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, 2018 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, 2018 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, 2018 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, 2018 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, 2018 9 Ř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, 2018 10 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íč) Přeskoč opakování… PA152, Vlastislav Dohnal, FI MUNI, 2018 11 Příklad vkládání  h(„b“) = 2 0 1 2 3 b a c d PA152, Vlastislav Dohnal, FI MUNI, 2018 12 Příklad vkládání  h(„e“) = 1 0 1 2 3 b a c d e PA152, Vlastislav Dohnal, FI MUNI, 2018 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, 2018 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, 2018 15 Příklad mazání  Uvolňovat přetokové oblasti  Smaž „a” 0 1 2 3 a e d PA152, Vlastislav Dohnal, FI MUNI, 2018 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, 2018 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, 2018 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, 2018 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, 2018 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, 2018 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, 2018 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, 2018 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, 2018 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, 2018 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, 2018 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, 2018 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, 2018 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, 2018 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, 2018 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, 2018 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, 2018 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, 2018 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, 2018 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)  Komprimuj 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, 2018 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, 2018 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, 2018 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, 2018 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, 2018 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… PA152, Vlastislav Dohnal, FI MUNI, 2018 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, 2018 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, 2018 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, 2018 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, 2018 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, 2018 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, 2018 PA152, Vlastislav Dohnal, FI MUNI, 2018 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, 2018 48 Index pro jeden atribut  SELECT jméno, plat FROM zam WHERE oddělení=‘Hračky’ ANDplat < 10000  Index pro oddělení Nalezené záznamy načítej a filtruj pomocí plat < 10000 I1 PA152, Vlastislav Dohnal, FI MUNI, 2018 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, 2018 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, 2018 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, 2018 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, 2018 53 Spojení klíčů v jeden  Podobné indexu pro jeden klíč Hodnota klíče je spojená  Spojení řetězců, kombinace čísel, …  V indexování příliš se nepoužívá  V hašování dělená hašovací funkce (Partitioned hash function) PA152, Vlastislav Dohnal, FI MUNI, 2018 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, 2018 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, 2018 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, 2018 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, 2018 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, 2018 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, 2018 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, 2018 61 Grid: implementace X1 X2 X3 X4 X1 X2 X3 X4 X1 X2 X3 X4 V1 V2 V3 PA152, Vlastislav Dohnal, FI MUNI, 2018 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, 2018 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, 2018 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, 2018 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, 2018 66