hledat
Rozdíly
Zde můžete vidět rozdíly mezi vybranou verzí a aktuální verzí dané stránky.
| Obě strany předchozí revize Předchozí verze Následující verze | Předchozí verze | ||
|
mgr-szz:in-pos:3-pos [2019/06/13 17:51] lachmanfrantisek přepracování "organizace souborů" |
mgr-szz:in-pos:3-pos [2020/04/12 16:56] (aktuální) |
||
|---|---|---|---|
| Řádek 426: | Řádek 426: | ||
| * často stačí pro vyřešení některých dotazů zpřístupnit pouze malou část záznamů -- na základě indexů je možné efektivně provádět filtrování | * často stačí pro vyřešení některých dotazů zpřístupnit pouze malou část záznamů -- na základě indexů je možné efektivně provádět filtrování | ||
| * forma indexu: <color blue>{ vyhledávací klíč ; ukazatel na záznam }</color> | * forma indexu: <color blue>{ vyhledávací klíč ; ukazatel na záznam }</color> | ||
| - | * __typy indexů:__ | + | |
| - | *řádné, lineární indexy -- v tabulce uspořádané dvojice { vyhledávací klíč ; ukazatel na záznam } podle hodnoty vyhl. klíče | + | |
| - | *hašované indexy -- využití hašovací funkce vyhledávacího klíče | + | __typy indexů:__ |
| - | *stromové indexy -- využití grafové struktury strom | + | |
| - | *indexové bitové mapy -- pozice bitů v bitovém vektoru určují lokality záznamů | + | * **řádné, lineární indexy**: |
| - | * indexy mohou být víceúrovňové -- "index do indexu" -- nejnižší úroveň může být přímo primární soubor, výše jsou řídké indexy | + | * v tabulce uspořádané dvojice { vyhledávací klíč ; ukazatel na záznam } podle hodnoty vyhl. klíče |
| + | * **hašované indexy** | ||
| + | * využití hašovací funkce vyhledávacího klíče | ||
| + | * **stromové indexy** | ||
| + | * využití grafové struktury strom | ||
| + | * **indexové bitové mapy** | ||
| + | * pozice bitů v bitovém vektoru určují lokality záznamů | ||
| + | * vhodné pro atributy s malým množstvím různých hodnot (uchováváme bitovou mapu pro každou hodnotu) | ||
| + | |||
| + | Indexy mohou být víceúrovňové -- "index do indexu" -- nejnižší úroveň může být přímo primární soubor, výše jsou řídké indexy | ||
| === Řádné indexy === | === Řádné indexy === | ||
| + | |||
| Obvykle pokud se mluví o indexech, jsou myšleny řádné. | Obvykle pokud se mluví o indexech, jsou myšleny řádné. | ||
| - | **Dělení 1** | + | |
| - | - primární index -- podle jeho klíče je uspořádán primární soubor se záznamy; může být hustý nebo řídký | + | **Primární x sekundární** |
| - | - sekundární index -- určený pro dotazy založené na jiném vyhledávacím klíči než na primárním; musí být hustý | + | * **primární index** |
| - | **Dělení 2** | + | * podle jeho klíče je uspořádán primární soubor se záznamy |
| - | //hustý// -- indexový záznam pro každou hodnotu vyhledávacího klíče. Typicky bývá uspořádán podle hodnoty klíče | + | * může být hustý nebo řídký |
| + | * sekundární index | ||
| + | * určený pro dotazy založené na jiném vyhledávacím klíči než na primárním | ||
| + | * musí být hustý | ||
| + | |||
| + | **Hustý x řídký** | ||
| + | |||
| + | * **hustý** | ||
| + | * indexový záznam pro každou hodnotu vyhledávacího klíče. | ||
| + | * Typicky bývá uspořádán podle hodnoty klíče | ||
| {{:home:prog:husty.jpg?500|}} | {{:home:prog:husty.jpg?500|}} | ||
| - | //řídký// -- indexový záznam pouze pro některé hodnoty vyhledávacího klíče; použitelné pouze v případě, kdy je soubor podle tohoto klíče uspořádán | + | |
| + | * **řídký** | ||
| + | * indexový záznam pouze pro některé hodnoty vyhledávacího klíče | ||
| + | * použitelné pouze v případě, kdy je soubor podle tohoto klíče uspořádán | ||
| {{:home:prog:ridky.jpg?500|}} | {{:home:prog:ridky.jpg?500|}} | ||
| Řádek 476: | Řádek 500: | ||
| === Hašování === | === Hašování === | ||
| - | <box 90% round blue | Definice>**hašovací funkce (obecně)** = převedení libovolně dlouhého vstupu na výstup pevné délky | + | |
| - | **hašovací funkce (ve smyslu organizace souborů)** = funkce řešící přístup k záznamům souboru s konstantní složitostí | + | |
| + | <box 90% round blue | Definice> | ||
| + | |||
| + | **hašovací funkce (obecně)** = Funkce, která mapuje libovolně velký vstup na výstup fixní délky a není prostá. | ||
| + | **hašovací funkce (ve smyslu organizace souborů)** = Funkce řešící přístup k záznamům souboru s konstantní složitostí. | ||
| **kolize** = situace, kdy je pro více záznamů spočítána stejná adresa | **kolize** = situace, kdy je pro více záznamů spočítána stejná adresa | ||
| - | * obvykle se řeší pomocí bucketů -- každé paměťové místo má předepsanou kapacitu záznamů, ve které se následně vyhledává lineárně | + | * při nalezení kolize umisťujeme nový prvek: |
| + | * ve stejné paměti (**otevřené adresování**) | ||
| + | * lineární, kvadratické adresování | ||
| + | * řetězení kolizí | ||
| + | * násobné hašování | ||
| + | * v jiné paměťové oblasti (**closed addressing**) | ||
| + | * umístění do **kapes** | ||
| </box> | </box> | ||
| - | Perfektní hašovací funkce -- hašovací funkce //h//, která je prostá. | + | |
| Požadované vlastnosti hašovací funkce: | Požadované vlastnosti hašovací funkce: | ||
| * je deterministická | * je deterministická | ||
| Řádek 487: | Řádek 522: | ||
| * vypočítává se z hodnot všech nebo alespoň většiny bitů klíče | * vypočítává se z hodnot všech nebo alespoň většiny bitů klíče | ||
| * pokrývá cílový prostor rovnoměrně | * pokrývá cílový prostor rovnoměrně | ||
| + | * drobná změna ve vstupu vede k výrazné změně ve výstupu | ||
| + | * prostá = //perfektní hašování// | ||
| == Statické hašování == | == Statické hašování == | ||
| * používá se u souborů, které procházejí jen minimem změn | * používá se u souborů, které procházejí jen minimem změn | ||
| - | * případné změny mohou negativně ovlivnit efektivitu hašování -- pokud se sejde na stejné adrese více záznamů než je kapacita bucketu, vyhledávání v rámci těchto záznamů má lineární složitost | + | * případné změny mohou negativně ovlivnit efektivitu hašování |
| + | * pokud se sejde na stejné adrese více záznamů než je kapacita bucketu, vyhledávání v rámci těchto záznamů má lineární složitost | ||
| == Dynamické hašování == | == Dynamické hašování == | ||
| + | |||
| + | <box 90% blue|Rozšiřitelné hašování> | ||
| + | |||
| * k výpočtu adresy se používá pouze prvních //i// bitů z výstupu hašovací funkce; toto //i// se dynamicky mění -- pokud je potřeba více adres, tak se zvyšuje, naopak při malém počtu se //i// zmenšuje | * k výpočtu adresy se používá pouze prvních //i// bitů z výstupu hašovací funkce; toto //i// se dynamicky mění -- pokud je potřeba více adres, tak se zvyšuje, naopak při malém počtu se //i// zmenšuje | ||
| * používá se u souborů s proměnným počtem záznamů | * používá se u souborů s proměnným počtem záznamů | ||
| * buckety jsou naplněné rovnoměrně -- pokud jsou plné, tak se štěpí, pokud jsou prázdné, tak se spojují | * buckety jsou naplněné rovnoměrně -- pokud jsou plné, tak se štěpí, pokud jsou prázdné, tak se spojují | ||
| - | * Druhy: | + | |
| - | * rozšiřitelné hašování | + | |
| {{:home:prog:rozhas.jpg|}} | {{:home:prog:rozhas.jpg|}} | ||
| - | <note> | + | |
| * hašovací funkce rozmisťuje záznamy do kapes (kapsa = záznamy s jistou podmnožinou klíčů, vymezuje je hašovací funkce) | * hašovací funkce rozmisťuje záznamy do kapes (kapsa = záznamy s jistou podmnožinou klíčů, vymezuje je hašovací funkce) | ||
| * jako index v adresáři kapes se používá dynamicky určovaný prefix výsledku hašovací funkce **//h//(//k//)** | * jako index v adresáři kapes se používá dynamicky určovaný prefix výsledku hašovací funkce **//h//(//k//)** | ||
| Řádek 506: | Řádek 546: | ||
| * globální hloubka > lokální hloubka -- na blok ukazuje více ukazatelů, jednoduše se rozdělí na dva | * globální hloubka > lokální hloubka -- na blok ukazuje více ukazatelů, jednoduše se rozdělí na dva | ||
| * globální hloubka = lokální hloubka -- musí vzniknout nová kapsa a také se zdvojnásobí rozměr adresáře kapes | * globální hloubka = lokální hloubka -- musí vzniknout nová kapsa a také se zdvojnásobí rozměr adresáře kapes | ||
| - | </note> | + | </box> |
| - | * lineární hašování | + | |
| - | <note> | + | |
| + | <box 90% blue|Lineární hašování> | ||
| * řeší nedostatky rozšiřitelného hašování za cenu vyšší režie dané manipulací s **přetokovými kapsami** | * řeší nedostatky rozšiřitelného hašování za cenu vyšší režie dané manipulací s **přetokovými kapsami** | ||
| * počet kapes udržuje tak, aby byly naplněny z např. 80 % | * počet kapes udržuje tak, aby byly naplněny z např. 80 % | ||
| * rozdíl oproti rozšiřitelnému hašování: **nemusí se vytvářet ani udržovat adresář kapes**, přesto počet kapes roste **lineárně**. | * rozdíl oproti rozšiřitelnému hašování: **nemusí se vytvářet ani udržovat adresář kapes**, přesto počet kapes roste **lineárně**. | ||
| - | </note> | + | </box> |
| Řádek 524: | Řádek 565: | ||
| Postup zpracování a optimalizace dotazu: | Postup zpracování a optimalizace dotazu: | ||
| - | - dotaz | + | - Převod dotazu na **syntaktický strom** pomocí parseru. |
| - | - syntaktický strom dotazu | + | - Převod na **logický plán** ve formě výrazů relační algebry. |
| - | - logický plán dotazu - v pojmech relační algebry | + | - Aplikací transformačních pravidel (viz níže) vznikne **vylepšený logický plán** |
| - | - vylepšený logický plán dotazu | + | - Odhad ceny provedení na základě různých statistik (počet záznamů, velikost záznamů, počet unikátních hodnot, ...). |
| - | - logický plán dotazu s velikostmi - v PostgreSQL lze zobrazit příkazem EXPLAIN | + | - **logický plán dotazu s velikostmi** - v PostgreSQL lze zobrazit příkazem EXPLAIN |
| - | - fyzický plán dotazu | + | - Transformace na **fyzický plán** určující pořadí operací. |
| - | - vyhodnocení | + | - Výběr nejlevnějšího **fyzické plánu** (velikost výsledků, počet V/V operací). |
| - | + | - Vyhodnocení vybraného **fyzického plánu**. | |
| - | Dotaz se nejprve pomocí parseru převede na syntaktický strom reprezentující strukturu dotazu. Ten se po té zpracuje do výrazů relační algebry (logický plán dotazu). Pomocí transformačních pravidel (kombinace přirozeného spojení, kartézského součinu, sjednocení, selekce a projekce) dále vznikne vylepšený logický plán. Nyní se za pomocí různých statistik (počet záznamů, velikost záznamů v bajtech, počet obsazených bloků, počet unikátních hodnot daného atributu) odhadnou velikosti výsledků, které ovlivňují odhad ceny provedení. Následně se logický plán transformuje na fyzický plán, který určí pořadí operací nutných k vykonání. Porovnají se různé fyzické plány, odhadnou se náklady (velikost výsledků, počet V/V operací) a zvolí se nejlevnější. Nakonec se daný plán provede a tím se získá výsledek. | + | |
| === Transformační pravidla === | === Transformační pravidla === | ||
| - | * Přirozené spojení, kartézský součin, sjednocení, průnik | + | = Transformační vztahy relační algebry zachovávající výsledek. Mohou ale zefektivnit samotné vyhodnocování. |
| + | |||
| + | |||
| + | * Přirozené spojení + kartézský součin a sjednocení + průnik | ||
| * Protože jsou všechny atributy zachovány, není pořadí důležité. | * Protože jsou všechny atributy zachovány, není pořadí důležité. | ||
| Řádek 595: | Řádek 638: | ||
| * Techniky přepsání dotazu | * Techniky přepsání dotazu | ||
| - | * Použití indexů | ||
| * Rušení nadbytečných DISTINCT | * Rušení nadbytečných DISTINCT | ||
| * (Korelované) poddotazy | * (Korelované) poddotazy | ||
| Řádek 601: | Řádek 643: | ||
| * Používání HAVING | * Používání HAVING | ||
| * Používání pohledů (VIEW) | * Používání pohledů (VIEW) | ||
| + | * Použití indexů | ||
| * Uložené pohledy (materializedviews) | * Uložené pohledy (materializedviews) | ||
| + | |||
| * Vytvoření indexu | * Vytvoření indexu | ||
| Řádek 640: | Řádek 684: | ||
| - | + | <box 90% blue|klíče> | |
| - | + | **super klíč** = množina atributů jednoznačně určující každý záznam | |
| - | + | **kandidátský klíč** = super klíč bez nadbytečných atributů | |
| - | + | **primární klíč** = právě jeden vybraný kandidátský klíč | |
| - | + | </box> | |
| - | + | ||
| - | + | ||
