Fórum Root.cz
Hlavní témata => Server => Téma založeno: Droan 13. 06. 2018, 23:07:56
-
Ahoj,
snažím se pochopit, jak funguje indexování a mám v tom dost chaos.
Co jsem četl za články, tak jsem to pochopil stručně nějak takto:
Když nemám index, tak pokud zadám dotaz, tak se musí projet všechna data po jednom, pokud mám index, tak systém ví, kam má přesně jít a nemusí procházet všechna data. Index je datová struktura uložená v paměti a používá B+ stromy.
Nicméně... Jak je ten index uložený v paměti? Nedovedu si to prostě představit... to se vytvoří nová tabulka? Jak ta tabulka bude vypadat? Jak probíhá to "propojení"? Jak si zvolím ty hodnoty indexové? Když budu mít index na id nějakých zaměstnanců, tak z těch id se vytvoří ten b+ strom? Když budu chtít index na příjmení zaměstnanců a třeba budu hledat "Novák" - tak jak to bude konkrétně vypadat? To se projede ten index a index odkazuje na ty data přímo a projde se mnohem méně těch datových položek?
Mohl bych poprosit o osvětlení těhle věcí? Případně nějaké odkazy, kde je to hezky vysvětlené a s obrázky, z kterých se to lépe chápe?
Mockrát děkuji
-
Ano, index je typicky nějaký strom. Pro pole příjmení budou vrcholy reprezentovat jednotlivá příjmení. Každý vrchol pak obsahuje odkazy na příslušné záznamy, kde se vyskytuje v daném poli. Při hledání se strom prochází, na rozdíl od hledání bez použití indexu ovšem ne sekvenčně (tj. lineárně), ale rychleji (protože jde typicky o nějaký typ vyváženého stromu, kde je hloubka omezena logaritmicky). Wikipedie (aspoň ta anglická) to rozvádí velice názorně a podrobně.
-
Indexy obvykle nebývají v paměti, ale opět někde na disku. Bývají v blocích o velikosti alokační jednotky, aby práce s nimi byla rychlá. Obsahují klíč a adresu do souboru s daty, kde se indexovaný záznam nachází. Pokud podmínce vyhovuje víc než asi čtvrtina záznamů, tak bývá výhodnější ignorovat index a projít si všechny záznamy sekvenčně. Rovněž nemá moc velký význam dělat index pro méně než 1000 záznamů.
Existují i databázové systémy, které mají indexy výhradně v operační paměti. Tyto databáze sice trochu déle startují, ale pak běží velice rychle.
-
Velmi zjednodušeně, ale možná může pomoci:
Indexy nemusí být nutně v paměti, je to prostě další součást DB (vytvářená automaticky). Obvykle i ukládané spolu s DB. V paměti obvykle bývají, kvůli urychlení, ale to mohou být i vlastní položky.
Zapomeň na B+ tree a další specialitky, pro základní představu, nejjednodušší příklad, mysli, že index je opravdu jen další tabulka odkazů (tím "odkazem" si představ pořadí v základní tabulce). Index jsou tedy jen odkazy (pořadí, propojení), nic jiného. Akorát že seřazené.
Takže máš třeba DB čtyř jmen: Ondra, Jirka, Petr, Michal
Když si necháš oindexovat (dle jména), tak index bude vypadat třeba 2., 4., 1., 3. (tedy, seřazeně je jako první odkaz na 2. položku Jirka, pak Michal, Ondra, Petr).
- Výhody, když hledáš jméno, stačí půlením intervalu (přes ten index) dohledat seřazené, jinak bys musel projíždět položky jednu za druhou, než najdeš. Pro B tree index se pak projíždí ten strom.
- Nevýhody, když přidáš další jméno, musí se upravit i index (takže přidávání ubírání položek trvá déle než bez indexu). Příklad, přidáš "Karel" ... bude to vypadat Ondra, Jirka, Petr, Michal, Karel ... ale upravený index bude: index 2., 5., 4., 1., 3.
Indexů může být více (jméno, příjmení, ...), ale každé přidání a ubrání vždy znamená znovu opravit _všechny_ indexy. Ale vyhledávání je pak rychlé. Proto se jako index užívají různě B stromy a spol., aby se i pohyby (odebírání, přidávání) v rámci indexu prováděly rychle - není to jen prostá lineární tabulka pořadí (tam by se muselo celé posouvat, při přidání doprostřed).
V praxi v současných databázích to vypadá jen tak, že řekneš, že třeba pole "jméno" chceš indexovat a databáze už si vše dělá sama - jak upravuje index při přidávání/mazání, tak, pokud hledáš dle jména, tak využije index a vyhledá rychle. Stejně tak se nestaráš o to, jak to "propojení" vypadá ani jak vypadá zdrojová tabulka jmen - zda je index jen prosté pořadí, či něco více. Ona totiž ani ta původní tabulka jmen neznamená, že jsou někde za sebou, může to být list, cokoli. O to se nestaráš, to zvenku nevíš.
Prostě, Ty už se pak nestaráš o to, že nějaký index musíš upravovat, ani jaká je fyzická podoba zdrojové "tabulky". To už je starost DB. Ty se jen ptáš (SQL).
-
doporucuju si precist hledani v binarnim stromu.
https://en.wikipedia.org/wiki/Binary_search_tree
treba mas tabulku s cislama (jake jsou vyplaty), kdyz to mas ve vektoru, tak musis prochazet
cely vektor, abys nasel zaznamy s cislem vetsim X.
kdyz k tomu mas index jako binarni strom, tak staci najit odpovidajici vetev stromu a mas
vsechny zaznamy co potrebujes.
-
Když nemám index, tak pokud zadám dotaz, tak se musí projet všechna data po jednom, pokud mám index, tak systém ví, kam má přesně jít a nemusí procházet všechna data. Index je datová struktura uložená v paměti a používá B+ stromy.
Zaklínadlo je právě B-tree (https://en.wikipedia.org/wiki/B-tree). SELECT potom nemusí procházet (porovnávat) N záznamů, ale stačí mu log2(N) porovnání. Což znamená rozdíl 1000 vs. 10 nebo 1 000 000 vs 20. Ona údržba toho indexu taky něco stojí, ale odehrává se při vkládání záznamů (a i tak vložení záznamu opět NEznamená projít celou tabulku). Takže index má smysl pro velký počet záznamů a zejména pro tabulky (sloupce?) kde se často hledá (čte) a málo vkládá (zapisuje). Nebo nad sloupci, na které se provádí join mezi tabulkami!
B-tree má jeden obecný vtipný aspekt, přítomný v různých implementacích - pokud zkusíte používat nějaké B-tree knihovny v jazyce nízké úrovně, třeba v Cčku: samotná stromová struktura nijak těsně nezávisí na datovém typu, který stromem třídíte. Tzn. kostra stromu je prakticky stejná, ať se jedná o integer, nebo třeba o řetězec znaků o proměnlivé délce. (Nebo o Váš vlastní bizardní objekt se svéráznou sémantikou porovnávání.) Finta je v tom, že B-tree knihovně při vytvoření stromu předáte odkaz na "porovnávací funkci". V zásadě se jedná o funkci "je větší než", která bere dva argumenty "konkrétního cílového" datového typu. A pak už do stromu jenom sypete položky (resp. v našem případě odkazy na záznamy v DB) a on si porovnávací funkci úkoluje po svém. Vám při vyhledávání vypadnou hotové výsledky. Zdejší věrozvěsti funkcionálního programování zajisté pobaveně kroutí hlavou jak přednáším o vynálezu kola.
Nicméně... Jak je ten index uložený v paměti? Nedovedu si to prostě představit... to se vytvoří nová tabulka? Jak ta tabulka bude vypadat? Jak probíhá to "propojení"? Jak si zvolím ty hodnoty indexové? Když budu mít index na id nějakých zaměstnanců, tak z těch id se vytvoří ten b+ strom? Když budu chtít index na příjmení zaměstnanců a třeba budu hledat "Novák" - tak jak to bude konkrétně vypadat? To se projede ten index a index odkazuje na ty data přímo a projde se mnohem méně těch datových položek?
Jak je index uložený v paměti. Jak je binární strom uložený v paměti. Zkoušel jste programovat v Cčku, Pascalu, Perlu, nebo nějakém jiném jazyku, kde lze dynamicky alokovat "kompozitní" datové typy jako struct/record a odkazovat se na ně pointery/referencemi apod.? Většinou je tahle látka vyučována cca v pořadí pointer, struct, linked list, strom. Plus na to navazuje téma o "alokátorech" paměti = jak se z té "společné hromady" parcelují kousky RAMky pro jednotlivé structy = uzly stromu, tzn. co se skrývá za funkcemi jako malloc()/free(). To se pořád bavíme o RAMce / heapu. On se ale index nemusí do RAMky celý vejít, nebo není potřeba aby místo v RAMce trvale zabíral. A rozhodně potřebuje mít zajištěnu "perzistenci". Takže ano, ukládá se i na disk. Vlastně se dá i přímo na disku procházet, aniž by se celý do RAMky natáhl. Opět platí výše zmíněné "poměry akcelerace" - jenom už se nebavíme o porovnávacích operacích co operují čistě v RAMce, ale latence každého kroku bude určena latencí seeku na disk. (Nebo něco mezi, protože několik uzlů B-stromu bude na disku pohromadě v jedné alokační jednotce.) Navazuje problematika alokace místa na discích - a nebudu odkazovat striktně na souborové systémy, protože mnohé databáze rády fungují přímo na diskový oddíl (blokové zařízení) a spravují si alokaci "po svém". To je myslím už poměrně dost buzzwordů do googlu, co říkáte :-) Samozřejmě je index s tabulkou provázaný odkazy, jak v RAMce, tak na disku. Skutečné interní algoritmy indexování, alokování souvisejících datových struktur v RAMce a na disku, to je "sladké tajemství" každého DB enginu. U komerčních DB se jedná o obchodní tajemství / klíčové intelektuální vlastnictví, u open-source DBMS Vám nic nebrání ponořit se do zdrojáků a číst. V souvislosti s indexováním se zkuste mrknout vedle b-trees také na "hash" algoritmy, které k problému přistupují trochu jinak a mohou urychlit prohledávání indexu jiným způsobem.
Pro Vás jako uživatele RDBMS = programátora aplikace a SQL dotazů je důležité, že tohle všechno se děje "pod kapotou", kam v zájmu svého duševního zdraví nechcete moc nahlížet. Od toho Vám pánbůh seslal DB engine, aby se postaral o Vaše pohodlí. Takže na úrovni SQL není index sám o sobě moc vidět. Vy ho vytvoříte příkazem cca CREATE INDEX ON TABLE (https://www.w3schools.com/sql/sql_create_index.asp), čili vznikne tam jakýsi objekt ve "jmenném prostoru věcí co jste si v databázi vytvořil", ale je pevně přivázaný ke konkrétní tabulce, a při SELECT/INSERT/UPDATE/DELETE se každopádně bavíte pomocí SQL příkazů explicitně s _tabulkou_, nikoli s indexem. Čili Index je v tomto smyslu občanem nižší kategorie než třeba "view". Nebo jinak, Index je za provozu spíš jenom takový "astrální duch v pozadí", který na Vaši tabulku potichu dohlíží. Existuje také explicitní "DROP INDEX", v různých dialektech SQL buď samostatný, nebo v rámci "ALTER TABLE".
A ještě jedna poznámka: snad všechny DBMS vytvoří impliticní index (https://stackoverflow.com/questions/3292067/default-index-on-primary-key), pokud zmíníte klauzulku PRIMARY KEY v rámci SQL příkazu CREATE TABLE (https://www.w3schools.com/sql/sql_primarykey.asp). Prostě primární klíč bývá implicitně indexovaný, aniž byste si o index musel ještě nějak extra říct pomocí CREATE INDEX. Stačí že si řeknete o PRIMARY KEY.
-
"Ona údržba toho indexu taky něco stojí, ale odehrává se při vkládání záznamů (a i tak vložení záznamu opět NEznamená projít celou tabulku)."
nebo-li vyvazovani stromu.
-
Složitost log2(N) by byla jen u vyváženého binárního stromu. B+ strom však používá větší node. Obvykle tak, aby odpovídal velikosti alokační jednotky na disku. V tomto node se už většinou vyhledává sekvenčně. Tento postup snižuje počet přístupů na disk, což je u databází žádoucí.
-
Složitost log2(N) by byla jen u vyváženého binárního stromu. B+ strom však používá větší node. Obvykle tak, aby odpovídal velikosti alokační jednotky na disku. V tomto node se už většinou vyhledává sekvenčně. Tento postup snižuje počet přístupů na disk, což je u databází žádoucí.
Sekvenčně, ale v konstantním čase.
-
Ono ani tak nejde o rychlost prohledání toho stromu, ale o to, že se šetří ta nejdražší operace - nalezení a nahrání bloku z disku. Pokud mám tabulku o více sloupcích, která je v dejme tomu 20 blocích, tak pro nalezení zaznamů podle hodnoty nějakého sloupce musím nacist všech 20 bloku i když vracím jen jeden zaznam. Pokud použijí index, tak je velmi pravděpodobné, že se celý vejde do 1 bloku a tudíž nacitam jen blok s indexem a blok s hledaným záznamem.
-
Indexy navíc obvykle bývají v cache, což přináší další zrychlení.
-
Děkuji :), tak ještě shrnutí, jestli jsem to pochopil správně...
Nastavím si, že chci třeba indexovat seznam podle jména...
id | jmeno | telefon
1 | Petr | 123
2 | Jan | 222
3 | Dan | 333
4 | Jiri | 444
Takže se mi vytvoří struktura B strom v paměti s hodnotami - Petr, Jan, Dan, Jiri a díky složitosti log2n vyhledávání se mi rychleji najdou ty indexy, které dále ukazují na data v tabulce. Takže třeba když budu hledat Dan - tak index Dan bude ukazovat na ten řádek (s id=3) v tabulce. Pokud by bylo více Danů v tabulce, tak bude ukazovat na všechny Dany. Chápu to tak správně?
-
Takže třeba když budu hledat Dan - tak index Dan bude ukazovat na ten řádek (s id=3) v tabulce.
Ano. Terminologická poznámka: index je celý ten strom zkonstruovaný nad sloupcem "jméno". Položka "Dan" je jenom jeden záznam v indexu, koncový "list" stromu. A ano, záznam v indexu obsahuje nějaký low-level odkaz na záznam v "hostitelské" tabulce. (Tedy pokud se jedná o index unikátní. Jak jste sám správně poznamenal.)
Pokud by bylo více Danů v tabulce, tak bude ukazovat na všechny Dany.
Tak. V tom případě se nejedná o index unikátní. I tak má příznivý vliv na rychlost selectů apod., které nad pojednaným sloupcem budete provádět.
Mimochodem index se dá definovat i nad více sloupci - tzn. můžete si třeba oindexovat "složený klíč", třeba jméno+příjmení. Kombinací více sloupců dosáhnete unikátnosti záznamů v indexu (nebo téměř).
-
Tak. V tom případě se nejedná o index unikátní. I tak má příznivý vliv na rychlost selectů apod., které nad pojednaným sloupcem budete provádět.
Ono je to opačně – index se vytváří kvůli rychlému vyhledání určitého záznamu v tabulce, a když je potřeba zajistit unikátnost nějaké hodnoty, vytvoří se nad daným sloupcem index, protože vyhledávat danou hodnotu bude nutné při každém insertu a updatu.
složitosti log2n vyhledávání se mi rychleji najdou ty indexy, které dále ukazují na data v tabulce
Jsou různé druhy indexů, mají různou složitost pro vyhledávání i pro zápis, dokonce i různou složitost pro různé charakteristiky dat. Index je prostě struktura, která umožňuje rychlejší nalezení záznamů odpovídajících daným podmínkám. Index je česky rejstřík – a databázový rejstřík má úplně stejnou funkci, jako rejstřík v knize. Některá slova, o kterých se předpokládá, že je budete v knize hledat, máte vypsaná v rejstříku, spolu s odkazem na stránku v knize, kde se to slovo nalézá. A slova v rejstříku jsou seřazená abecedně, takže v tom seznamu požadované slovo rychle najdete. To, co je v knize napsané, se z rejstříku nedozvíte – jsou tam vypsaná jen některá slova, a navíc v abecedním pořadí, ne v pořadí, v jakém jsou ve větách, aby věty dávaly smysl. Když ale potřebujete najít, kde se nachází konkrétní slovo, najdete ho v rejstříku mnohem rychleji, než kdybyste četl knihu od začátku do konce. A k jedné knize můžete mít rejstříků několik – třeba jmenný rejstřík, rejstřík míst, věcný rejstřík.
Rozdíl knižního a databázového rejstříku je v tom, že kniha se nemění, tudíž ani rejstřík se nemění, takže je řazený abecedně, protože v tom se lidem snadno hledá. Databázový rejstřík počítá s tím, že se data mění, takže se musí měnit i rejstřík. kdybyste chtěl do abecedního rejstříku vložit nové slovo, musíte najít řádek, kam patří, a celý zbytek rejstříku od toho místa až do konce byste musel smazat a napsat znova, o řádek níž. Proto se v databázích používají jinak uspořádané rejstříky, ve kterých se docela snadno hledá, ale ani přidání nebo mazání není tak složitá operace. Třeba ty stromové indexy (např. různé varianty B-tree) fungují tak, že nezačínáte od kraje, ale zhruba uprostřed – takže by rejstřík začínal třeba „pokud slovo začíná od A–M, pokračujte na stránce 79, pokud začíná N–Ž, pokračujte na stránce 93“. Pokud budete hledat třeba slovo „KLÍČ“, budete pokračovat na stránce 79, a tam bude „pokud slovo začíná na A–G, pokračujte na stránce 85, pokud na H–M, pokračujte na 82“. A tak dále. Hledání v takovém stromu je pro počítač o něco obtížnější, než hledání v setříděném seznamu, ale úprava takového rejstříku je podstatně snazší – třeba při vkládání stačí přepsat nanejvýš jeden list, což je mnohem lepší, než kdybyste musel průměrně přepisovat půlku abecedního rejstříku.
-
Pokud by bylo více Danů v tabulce, tak bude ukazovat na všechny Dany.
Tak. V tom případě se nejedná o index unikátní. I tak má příznivý vliv na rychlost selectů apod., které nad pojednaným sloupcem budete provádět.
Ono je to opačně – index se vytváří kvůli rychlému vyhledání určitého záznamu v tabulce, a když je potřeba zajistit unikátnost nějaké hodnoty, vytvoří se nad daným sloupcem index, protože vyhledávat danou hodnotu bude nutné při každém insertu a updatu.
Já bych řekl, že naše tvrzení nejsou ve sporu :-)
Index v SQL lze vytvořit i bez požadavku na unikátnost (https://www.sqlservercentral.com/Forums/Topic651562-360-1.aspx). Proto souhlasím s tazatelem, že pak záznam v takovém indexu (např. btree koncový list) odkazuje na množinu/kolekci záznamů v "hostitelské" tabulce. A příznivě se projeví na rychlosti selectů / joinů apod. nad takto indexovaným sloupcem = neunikátní index je lepší než žádný index. A že není unikátní, to vyplývá z reality = z dat, která ten sloupec uchovává.
Teď mluvím na abstraktní úrovni - jak to vidí "uživatel DBMS" = SQL programátor. Jak je to implementováno pod kapotou by určitě vydalo na zajímavou další debatu. Sám občas v c++ takové "hybridní grafy" vytvářím, a to se pohybuju obvykle jenom na heapu, o perzistenci se nesnažím.
-
Index v SQL lze vytvořit i bez požadavku na unikátnost (https://www.sqlservercentral.com/Forums/Topic651562-360-1.aspx). Proto souhlasím s tazatelem, že pak záznam v takovém indexu (např. btree koncový list) odkazuje na množinu/kolekci záznamů v "hostitelské" tabulce. A příznivě se projeví na rychlosti selectů / joinů apod. nad takto indexovaným sloupcem = neunikátní index je lepší než žádný index. A že není unikátní, to vyplývá z reality = z dat, která ten sloupec uchovává.
Například jméno zákazníka rozhodně není unikátní a přitom se obvykle vyplatí ho indexovat. Dotaz přes takový index pak vrací množinu relací, které dotazu vyhovují, zatímco přes unikátní index vrací množinu s žádnou nebo jednou relací.
Když chci z databáze vytáhnout seznam položek faktury, tak je také netahám po jedné.
-
Vy to ale pořád píšete opačně. Index primárně slouží pro vyhledávání (a tudíž není unikátní). A s pomocí toho indexu se dá nastavit omezení na sloupci, aby byl unikátní, pro což se pak používá zkratka „unikátní index“. Samozřejmě, že pro vyhledávání je lepší mít index než ho nemít. A různé typy indexů mohou být pro určitý typ dat lepší než jiné – a unikátní index může být o něco efektivnější, než neunikátní. Což je ale jedno, protože unikátní index se nastavuje především kvůli tomu omezení unikátnosti dat.
-
S tvrzenim ze mit index se vzdy pro select vyplati bych byl velmi opatrny, protoze to neni pravda. Zalezi v prvni rade na datech (resp na jejich kardinalite/selectivite). Pokud totiz budu mit napriklad sloupec se jmeny a budu chtit podle nej vyhledavat tak v pripade ze budu it 100 hodnot a jmeno honza se bude vyskytovat v 50 z nich pak full scan bude rychlejs protoze hledani pres index jsou jen i/o navici. Pokud ovsem ve stejne tabulce bude jirka jen jednou a budu pro nej vyhledavat zaznam pak hledani dle indexu bude lepsi volbou. Zalezi tedy na datech a jak vyhledavam. Pokud mam unikatni data a chci one row je index jasna volba.
Jeste bych pro uplnost zminil ze nejsou pouze btree index ale pouzivaji se tez bitmap indexy nebu function based (klapu na mobilu nekdo dalsi necht pls vysvetli)
-
Vy to ale pořád píšete opačně. Index primárně slouží pro vyhledávání (a tudíž není unikátní). A s pomocí toho indexu se dá nastavit omezení na sloupci, aby byl unikátní, pro což se pak používá zkratka „unikátní index“. Samozřejmě, že pro vyhledávání je lepší mít index než ho nemít. A různé typy indexů mohou být pro určitý typ dat lepší než jiné – a unikátní index může být o něco efektivnější, než neunikátní. Což je ale jedno, protože unikátní index se nastavuje především kvůli tomu omezení unikátnosti dat.
Myslím, že jsem konečně pochopil, o co Vám jde. Děkuji za vysvětlení, že kočár patří za koně :-)
-
Pokud ovsem ve stejne tabulce bude jirka jen jednou a budu pro nej vyhledavat zaznam pak hledani dle indexu bude lepsi volbou. Zalezi tedy na datech a jak vyhledavam. Pokud mam unikatni data a chci one row je index jasna volba.
Ne tak docela. Pro 100 záznamů je index zbytečný, praktičtější je full-scan. Pokud tedy budu mít tabulku se sloupci ID a jméno, tak použiji primární index pro ID a hotovo. Jména mohu prohledávat sekvenčně, protože další index to neurychlí.
-
Indexy navíc obvykle bývají v cache, což přináší další zrychlení.
Nebo v jiném tablespace, což také přináší zrychlení. Data lze sypat na velký, levný HDD, indexy pak na dražší, menší, ale rychlejší SSD...
-
Index se prakticky nikdy nenavrhuje pro jeden konkrétní dotaz, ale pro množinu očekávaných dotazů. Jestli se konkrétní index použije si databáze rozhodne sama. Pokud bude mít v nějaké tabulce 50 % záznamů hledanou hodnotu, ve většině případů se opravdu nevyplatí index použít. Ale i v takovém případě může být dotaz na tyto hodnoty, kdy se použití indexu vyplatí – třeba když se budu ptát jenom na počet záznamů, nebo když budu z té tabulky potřebovat jen údaje, které jsou v tom indexu.
Pokud mám tabulku, která má jen 100 záznamů, je otázka, jestli vůbec potřebuji databázi.
Ne tak docela. Pro 100 záznamů je index zbytečný, praktičtější je full-scan. Pokud tedy budu mít tabulku se sloupci ID a jméno, tak použiji primární index pro ID a hotovo. Jména mohu prohledávat sekvenčně, protože další index to neurychlí.
Záleží na konkrétním případě, ale obvykle by i v takové situaci index hledání urychlil.
-
Ne tak docela. Pro 100 záznamů je index zbytečný, praktičtější je full-scan. Pokud tedy budu mít tabulku se sloupci ID a jméno, tak použiji primární index pro ID a hotovo. Jména mohu prohledávat sekvenčně, protože další index to neurychlí.
Záleží na konkrétním případě, ale obvykle by i v takové situaci index hledání urychlil.
Jak? Bez indexu se zmíněná data vejdou do jedné alokační jednotky na disku. Když použiji index, je potřeba načíst dvě alokační jednotky, což je pomalejší.
-
heh root nezklamal :) - 100 zaznamu byl samozrejme jen priklad, abych to mel na cem vysvetlit
-
heh root nezklamal :) - 100 zaznamu byl samozrejme jen priklad, abych to mel na cem vysvetlit
Nesváděj to na roota, když jsem se toho chytil já. Už jsem viděl hromadu tabulek s 50 záznamy, ke kterým někdo zbytečně dělal další indexy. Fakt to nemá význam.
-
ehh tak je pravda, ze se v praxi clovek setka clovek s ruznymi zhuverilostmi, ale tak nekdo musi proslapat tu slepou cesticku poznani :)
-
Jak? Bez indexu se zmíněná data vejdou do jedné alokační jednotky na disku. Když použiji index, je potřeba načíst dvě alokační jednotky, což je pomalejší.
Jestli budou data tabulky na jedné alokační jednotce disku závisí na tom, jak budou na disku zapsaná. Záznamy mohou být nějak zarovnané, navíc 100 záznamů neznamená, že jsou jeden za druhým – může tam být např. prázdné místo po smazaných záznamech, nebo se prostě záznamy jedné tabulky nezapisují souvisle za sebou.
Když se použije index, je větší pravděpodobnost, že budou data u sebe v jedné alokační jednotce disku. A explicitně jsem psal o případu, kdy jsou požadovaná data v indexu – takže odpadá čtení dat z tabulky, které mlčky předpokládáte.
-
Indexovat tabulku se 100 záznamy nemusí být nesmysl, ale naopak zcela racionální rozhodnutí.
1. spousta optimalizátoru dotazů nesmyslné penalizuje full table scan a u složitějších hodinu pak upřednostňuje málo selektivni scan obrovských indexu na velkých tabulkách před vysoce selektivnim full scanem minitabulky
2. cache vetsinou uprednostnuje indexy před datovými bloky a pokud jdu do tabulky jen pro indexovanou hodnotu, moderní engine ji vrátí přímo z indexu bez načítání datového bloku
3. i nad malou tabulkou můžu mít komplikovaný výraz, který může být výpočetně dráhy a má smysl použít funkcionální index
-
Indexovat tabulku se 100 záznamy nemusí být nesmysl, ale naopak zcela racionální rozhodnutí.
1. spousta optimalizátoru dotazů nesmyslné penalizuje full table scan a u složitějších hodinu pak upřednostňuje málo selektivni scan obrovských indexu na velkých tabulkách před vysoce selektivnim full scanem minitabulky
2. cache vetsinou uprednostnuje indexy před datovými bloky a pokud jdu do tabulky jen pro indexovanou hodnotu, moderní engine ji vrátí přímo z indexu bez načítání datového bloku
3. i nad malou tabulkou můžu mít komplikovaný výraz, který může být výpočetně dráhy a má smysl použít funkcionální index
Souhlasím s těmito výjimkami z uvedeného pravidla, že do 100 relací sekundární indexy v tabulce nepotřebuji.
-
Ještě bych měl otázku. Jak je to z hlediska práce s pamětí? Respektive, když použiji indexování, tak jak probíhá práce s pamětí? Je v tomhle směru nějaká výhoda vůči práce bez indexace?
-
Souhlasím s těmito výjimkami z uvedeného pravidla, že do 100 relací sekundární indexy v tabulce nepotřebuji.
Obecně se dá říct akorát to, že pro rychlejší nalezení záznamů se (obvykle) používají indexy. Tím obecná tvrzení končí, žádné obecné pravidlo pro 100 záznamů neplatí. Pak už vždy záleží na struktuře databáze, na uložených datech, na způsobu použití, na použitém databázovém stroji, a podle toho se databázový specialista rozhodna, zda vůbec použije index, případně jaký, z jakých dat se bude skládat, jaké bude mít parametry. A pak ještě může občas nastat případ, že databáze odhadne špatný exekuční plán, a bude potřeba jinou formulací dotazu nebo pomocí hintů přesvědčit databázi, aby data získávala jinak a třeba použila či nepoužila jiné indexy.
-
Ještě bych měl otázku. Jak je to z hlediska práce s pamětí? Respektive, když použiji indexování, tak jak probíhá práce s pamětí? Je v tomhle směru nějaká výhoda vůči práce bez indexace?
Záleží na tom, čemu říkáte „práce s pamětí“. Index je další datová struktura vedle primární tabulky, která musí být někde zapsaná (u relačních databází typicky na disku) a musí být aktualizovaná, pokud se změní příslušná data v primární tabulce. Změny v indexu jsou obvykle náročnější, než změny v primární tabulce (kde stačí data zapsat na do nějakého volného místa), – a to jak na paměť, tak na výpočetní výkon. Správně navržené a použité indexy pak zase šetří paměť při dotazování na data. A dál platí to, že RAM je rychlejší, než přístup na disk (zejména u rotačních disků), takže databáze se snaží data, která se nejčastěji používají, držet v paměti.
Dál to ale vždy záleží na konkrétním případu, někdy je efektivnější použít index, někdy by bylo index jen zbytečným plýtváním prostředků při zápisu. Někdy je efektivnější index založený na stromech, někdy bitmapový, někdy hash indexy, někdy indexy pro geografická data…
-
Ještě bych měl otázku. Jak je to z hlediska práce s pamětí? Respektive, když použiji indexování, tak jak probíhá práce s pamětí? Je v tomhle směru nějaká výhoda vůči práce bez indexace?
Záleží na tom, čemu říkáte „práce s pamětí“. Index je další datová struktura vedle primární tabulky, která musí být někde zapsaná (u relačních databází typicky na disku) a musí být aktualizovaná, pokud se změní příslušná data v primární tabulce. Změny v indexu jsou obvykle náročnější, než změny v primární tabulce (kde stačí data zapsat na do nějakého volného místa), – a to jak na paměť, tak na výpočetní výkon. Správně navržené a použité indexy pak zase šetří paměť při dotazování na data. A dál platí to, že RAM je rychlejší, než přístup na disk (zejména u rotačních disků), takže databáze se snaží data, která se nejčastěji používají, držet v paměti.
Dál to ale vždy záleží na konkrétním případu, někdy je efektivnější použít index, někdy by bylo index jen zbytečným plýtváním prostředků při zápisu. Někdy je efektivnější index založený na stromech, někdy bitmapový, někdy hash indexy, někdy indexy pro geografická data…
Čili index jakožto struktura je uložena na disku. Jaká data jsou uložena v té RAM? To jsou ta data, ke kterým se odkazujeme přes ty indexy nebo přímo ty indexy?
-
Čili index jakožto struktura je uložena na disku. Jaká data jsou uložena v té RAM? To jsou ta data, ke kterým se odkazujeme přes ty indexy nebo přímo ty indexy?
U běžné relační databáze je v souvislosti s daty v RAM v podstatě jen cache těch dat z disku (tj. to, co je právě potřeba, plus ve zbývající volné paměti další data, která jsou potřeba často).
-
Souhlasím s těmito výjimkami z uvedeného pravidla, že do 100 relací sekundární indexy v tabulce nepotřebuji.
Obecně se dá říct akorát to, že pro rychlejší nalezení záznamů se (obvykle) používají indexy. Tím obecná tvrzení končí, žádné obecné pravidlo pro 100 záznamů neplatí. Pak už vždy záleží na struktuře databáze, na uložených datech, na způsobu použití, na použitém databázovém stroji, a podle toho se databázový specialista rozhodna, zda vůbec použije index, případně jaký, z jakých dat se bude skládat, jaké bude mít parametry. A pak ještě může občas nastat případ, že databáze odhadne špatný exekuční plán, a bude potřeba jinou formulací dotazu nebo pomocí hintů přesvědčit databázi, aby data získávala jinak a třeba použila či nepoužila jiné indexy.
To je přece uvedeno v těch výjimkách, se kterými jsem souhlasil.
-
Čili index jakožto struktura je uložena na disku. Jaká data jsou uložena v té RAM? To jsou ta data, ke kterým se odkazujeme přes ty indexy nebo přímo ty indexy?
U běžné relační databáze je v souvislosti s daty v RAM v podstatě jen cache těch dat z disku (tj. to, co je právě potřeba, plus ve zbývající volné paměti další data, která jsou potřeba často).
Musím říct, že jsem stále v tom trošku zmatený. V té RAM paměti/cache je uložen i ten index, pokud se s ním pracuje? Nebo pouze ta data v tabulkách?
Děkuji :)
-
Čili index jakožto struktura je uložena na disku. Jaká data jsou uložena v té RAM? To jsou ta data, ke kterým se odkazujeme přes ty indexy nebo přímo ty indexy?
U běžné relační databáze je v souvislosti s daty v RAM v podstatě jen cache těch dat z disku (tj. to, co je právě potřeba, plus ve zbývající volné paměti další data, která jsou potřeba často).
Musím říct, že jsem stále v tom trošku zmatený. V té RAM paměti/cache je uložen i ten index, pokud se s ním pracuje? Nebo pouze ta data v tabulkách?
Děkuji :)
Tak to už je spíše otázka konkrétní implementace databáze, ne?
Skrze RAM dříve či později proteče všechno, jinak by se s tím nedalo pracovat.
Na disku máš soubor, ve kterém je tabulka. V jiném souboru (třeba) je index. Formát toho souboru může bejt klidně blob paměti (nějak šikovně rozkouskován). Když planer dospěje k závěru, že potřebuje vyhledat nějaká data z tabulky, tak se mrkne na index, a ten si (klidně jen část) načte do paměti, aby s ním pracoval. Když najde, který záznam potřebuje, tak podle informací v indexu zjistí, který soubor s tabulkou (nebo který seek tabulky) jej obsahuje, a ten načte do paměti.
Databáze pak samozřejmě kalkuluje, že když už to má v paměti, tak to pokud možno nevyhazovat. Takže třeba načítá pár bloků za sebou, nebo se snaží pamatovat časté dotazy, a ty upřednostňuje. Ale to už je konkrétní strategie (která se navíc dá různě ovlivňovat nastavením) té které databáze a to už je tak nějak nad rámec dotazu.
-
Čili index jakožto struktura je uložena na disku. Jaká data jsou uložena v té RAM? To jsou ta data, ke kterým se odkazujeme přes ty indexy nebo přímo ty indexy?
U běžné relační databáze je v souvislosti s daty v RAM v podstatě jen cache těch dat z disku (tj. to, co je právě potřeba, plus ve zbývající volné paměti další data, která jsou potřeba často).
Musím říct, že jsem stále v tom trošku zmatený. V té RAM paměti/cache je uložen i ten index, pokud se s ním pracuje? Nebo pouze ta data v tabulkách?
Děkuji :)
Za prvé, z hlediska uživatele databáze nemá cenu to řešit – je úlohou právě databáze zařídit, aby ta data byla získána co nejefektivněji, což i dnes znamená především vyhnout se zbytečnému čtení z disku.
Dnešní procesory fungují tak, že pracují vždy jen s daty v RAM, procesor neumí přečíst přímo data z disku, vždy je nejprve načte z disku do RAM a teprve pak s nimi pracuje. A databáze se snaží o to, aby často používaná data měla v RAM už předem a nemuselo se čekat, až se načtou z disku.
Takže obecně nemusí být v RAM nic, třeba po startu databáze nebo po té, kdy databáze řešila nějaký náročný dotaz a musela vyprázdnit všechny cache. Takže pokud bude při vykonání dotazu potřebovat nějaký index, načte ho disku (celý nebo část), případně donačítá další části indexu tak, jak zjišťuje, že jsou potřeba. Když potřebná data zjistí už z indexu, vrátí výsledek uživateli, pokud data v indexu nejsou, tak pokračuje tím, že načítá příslušné záznamy tabulky z disku. A když se databázi dobře podařil odhad, co bude potřebovat, nebo když má něco načtené v RAM díky předchozímu dotazu, který potřeboval ta samá data, tak to databáze samozřejmě nenačítá znovu z disku, ale použije to, co už má v RAM.
-
Čili index jakožto struktura je uložena na disku. Jaká data jsou uložena v té RAM? To jsou ta data, ke kterým se odkazujeme přes ty indexy nebo přímo ty indexy?
Vy si nedáte pokoj, dokud se nepustíme pod kapotu, žejo? Zkusím to nakousnout. Sám znám jenom obrysy. Možná vytrollím pár dalších, kteří doplní chybějící kousky, únavné podrobnosti, vyvrátí nepravdy atd.
No z velmi vysokého nadhledu potřebujete data v RAMce, aby s nimi kód běžící na CPU mohl pracovat, a potřebujete je i ukládat na disk - kvůli perzistenci (aby se počítač směl někdy vypnout) a taky proto, že se Vám celá databáze do RAMky často ani náhodou nevejde. Takže potřebujete mít převodní mechanismy mezi formátem v RAMce a na disku, a potřebujete algoritmy které si dokážou dotahovat z disku do RAM jenom nezbytné minimum, které momentálně potřebují k práci (a případně využití dostupné RAM nějak optimalizovat). A konkrétně u databází to znamená, že jak indexy tak "užitečná data tabulek" potřebujete na disku i v RAMce. (Byl by k něčemu užitečný index, který by se musel vejít do RAMky, a konstruoval by se vždy při startu RDBMS procesu?) Což nevylučuje možnost, že v RAMce budou nějaké pracovní, efemérní indexy a další struktury "navíc", které se na disk neukládají (po restartu se vytvoří znova).
V širším úhlu pohledu se opět jedná o obecný programátorský problém :-) Jiné datové struktury jsou vhodné pro manipulaci s daty v RAM, jiné pro uložení dat na disku. RAMka používá jiné alokační strategie a organizaci dat než diskový prostor, a jiné způsoby odkazování/adresace. V RAMce je výhodné (rychlé) používat přímé pointery na strojové adresy v paměťovém prostoru CPU, kde je alokován nějaký struct nebo jeho member, [ i ]tá položka v poli apod. Přímo nad těmito strukturami pracují algoritmy zkompilované do binárního strojového kódu, běžícího na CPU = přímo s nativními pointery pracují instrukce CPU. Samozřejmě by šlo i v RAMce letmo dohledávat nepřímé odkazy přes "lidské" identifikátory... možná to tak zrovna databáze dělají, nevím. (Teď bych sem nepletl interpretované jazyky a varianty jejich "vm" - v zásadě je tam tlustá vrstva abstrakce navíc.) Naproti tomu na disku je bloková vrstva adresace, nad ní oddíly, v nich souborový systém, a v rámci souboru ofsety po bajtech od začátku... a formát pro uložení v souboru může vypadat velmi různě. Každopádně "přímo na disku" nemůže nic běžet, protože v datech na disku se CPU přehrabuje hodně dlouhým klacíkem... Err... v dnes obvyklých architekturách :-)
Obecně čím víc má být formát na disku lidsky čitelný, tím víc bude tíhnout k využití lidsky čitelné znakové sady (ASCII, Unicode apod.), řádky a pole uvnitř řádků budou členěny "čitelnými" znaky (čárky, středníky, tabulátory, konce řádku apod.), formát může tolerovat volné místo, komentáře apod. Viz třeba CVS, YAML, XML apod. Zároveň "lidsky čitelné" formáty souborů vyžadují nejvíc zpracování při převodu mezi runtime podobou dat v RAMce a formátem souborů. Proto se často používají jako exportní/importní formáty.
Naopak "těžce binární" formáty umožňují přesouvat data mezi RAM a diskem s menší mírou letmého přežvykování. Binární formáty čísel a řetězců, odkazy na bajtové ofsety spíš než na "lidské" identifikátory / čísla řádek/záznamů, implicitní velikosti uložených "structů" apod. Dovedl bych si třeba představit, že v on-disk formátu s pevnou délkou "DB řádku" zůstanou volná místa pro machine-level pointery (pokud jsou potřeba) ale to si cucám z prstu. Binární formáty jsou obvyklejší jako "nativní pracovní formát" všelijakého softwaru. (Radši nebudu odbočovat, co je to relokovatelný executable kód, dynamické linkování sdílených knihoven apod.)
Přiznám bez mučení, že netuším, jak vypadá on-disk formát dnešních reálných RDBMS. Našel jsem nějaká hesla na wikipedii 1 (https://en.wikipedia.org/wiki/Database_storage_structures) 2 (https://en.wikipedia.org/wiki/Column-oriented_DBMS) , ale přijde mi to čtení stále dost abstraktní. Mohu jenom doporučit zdrojáky nějaké open-source DB.
Traduje se, že RDBMS nefungují příliš rády skrz souborový systém. Raději fungují přímo na vyhrazený diskový oddíl. Odpadne tím magie souborového systému, která může zpomalovat, násobit počet seeků apod. Ze stejného důvodu se tradovalo, že velikost stránky virtuální paměti hostitelského CPU (na x86 tradičně 4 kB) je pro RDBMS optimální alokační jednotkou na disku (sektor tradičně 512B, u nových disků točivých i SSD převažuje 4 kB). Ale celé to má další zádrhele, třeba huge pages apod. Chtěl jsem říct, že takovéto souznění velikosti stránek by nasvědčovalo přímočarému kopírování dat 1:1 mezi RAM a diskem, bez složitého přežvykování = on-disk formát velmi podobný pracovnímu formátu v RAM. Ale jestli je to tak doopravdy...
Jinak je asi vcelku známá věc, jak funguje swapování. RAMka je "overbooked". Virtuální paměťové prostory (https://en.wikipedia.org/wiki/Virtual_memory) user-space procesů jsou v součtu větší než skutečná fyzická RAM. User-space proces alokuje paměť podle potřeby. Stránky přidělené user-space procesům v kernelu eviduje memory management subsystém a pomocí LRU (https://en.wikipedia.org/wiki/Cache_replacement_policies#LRU) a spol si mezi stránkami vybírá ty "nejuleželejsí" - které v případě nedostatku RAM odkládá do swapu na disk. V tom případě se ovšem může snadno stát, že konkrétní user-space proces později sáhne "do prázdna" = chce stránku, která není v RAMce, protože byla odložena na disk. Tím vyvolá na procesoru výjimku zvanou page fault (https://en.wikipedia.org/wiki/Page_fault) - vlastně obsluhu IRQ a přepnutí kontextu do kernelu. Kernel si nějakou tu stránku v paměti uvolní (podle LRU), přimapuje ji procesu který zrovna způsobil page fault, loadne do ní příslušnou stránku ze swapu a proces může pokračovat v práci (je v plánovači vrácen mezi "běžící"). Proč to tady vytahuju? Hned to bude.
Se soubory se totiž dá pracovat dvěma způsoby:
- Jednak známějším open()/seek()/read()/write()/close() = soubor v programu otevřete a nějak ho žužláte, třeba do něj po jednom sekvenčně zapisujete ASCII řádky nebo nějaké binární "záznamy". Tzn. data podáváte syscallům skrz nějaký buffer v user space, a data se následně kopírují do kernelu.
- No a druhý způsob je, že se soubor dá namapovat do paměti (https://en.wikipedia.org/wiki/Memory-mapped_file). Tuhle fintu umí syscall mmap(). Přesněji řečeno, mmap() je třeba zavolat na otevřený file descriptor (https://stackoverflow.com/questions/7222164/mmap-an-entire-large-file) (tzn. napřed proběhne open()) a jsou tam nějaké nuance jaké flagy mmap()u předat. Tímto způsobem není potřeba data kopírovat mezi kernelem a user space - prostě se do user space namapuje pár stránek přímo z bufferu blokové vrstvy. A tento mechanismus funguje prakticky stejně jako paging podložený swapem (nuance/flagy stranou) tzn. dá se zařídit, aby se ze souboru dotahovaly stránky až když jsou potřeba (díky page faults). V těch heslech na wikipedii se dá dočíst, že page faultů je vlastně několik stupňů, a že se může stát, že bloková vrstva díky read-aheadu načte do bufferů pár stránek navíc, nepřimapují se všechny hned, ale příští page-fault třeba sáhne jenom po další stránce v bufferu (nemusí čekat na diskovou operaci).
Čili opravdu líný RDBMS engine (= user-space démon) by mohl třeba jenom namapovat z disku celý extent / table-space do svého adresního prostoru a těžkou práci s ládováním z disku do RAM (a naopak odkládáním na disk) nechat na memory-managementu hostitelského OS :-) = na jeho LRU, page-faultech, blokové vrstvě, managementu disk IO bufferů a tak. Nicméně pokud jsem měl možnost pozorovat, RDBMS si naopak tyhle věci rády spravují samy... naalokují si ze systému co nejvíc RAMky a pak si s ní interně hospodaří po svém.
Tohle jsou opravdu jenom velmi hrubé obrysy. Na rootu bacha, "kdo se moc ptá, moc se dozví." Jestli se návnady chytí někdo od fochu, budu nakonec se svým tapetováním vypadat jako břídil.
-
Musím říct, že jsem stále v tom trošku zmatený. V té RAM paměti/cache je uložen i ten index, pokud se s ním pracuje? Nebo pouze ta data v tabulkách?
Zkusím to napsat možná trochu nepřesně, ale stručně: Tabulková data i indexy jsou na úložném zařízení (disku). V RAM jsou pouze cache a buffery, které slouží k maximalizaci výkonu takové databáze.
-
budu nakonec se svým tapetováním vypadat jako břídil.
Náhodou, pěkný čtení.
-
Vidím, že má hodně lidí nejasno v tom, jak databáze přistupují k datům a k indexu v RAM a na disku. I když se v podstatě jedná o implementační detail, tak do toho vnesu ještě větší zmatek ;). Existují databáze, které neřeší, jestli jsou data v RAM nebo na disku, prostě je mmapují do paměti a špinavou práci s přesunem dat disk <--> RAM nechají na kernelu. Přitom nabízejí transakce, zaručují integritu dat a ještě navíc dosahují opravdu vysokého výkonu. Má to samozřejmě i nevýhody, vždycky je to něco za něco, např. zápis může být prováděn pouze jední uživatelem současně, ostatní si počkají.
https://en.wikipedia.org/wiki/Lightning_Memory-Mapped_Database
https://stackoverflow.com/questions/35279756/what-is-special-about-internal-design-of-lmdb/35732613#35732613
-
Vidím, že má hodně lidí nejasno v tom, jak databáze přistupují k datům a k indexu v RAM a na disku. I když se v podstatě jedná o implementační detail, tak do toho vnesu ještě větší zmatek ;). Existují databáze, které neřeší, jestli jsou data v RAM nebo na disku, prostě je mmapují do paměti a špinavou práci s přesunem dat disk <--> RAM nechají na kernelu.
Nemá smysl to komplikovat při vysvětlování někomu, kdo se ptá, jaký je rozdíl mezi tabulkou a indexem. Jestli databáze načítá data do paměti pomocí fread nebo mmap je implementační detail. Ony také třeba existují (obvykle clusterové) databáze, které data drží jenom v RAM a na disk případně umí data zazálohovat, aby bylo odkud je obnovit, pokud by bylo nutné vypnout celý cluster.