Vysvětlete mi indexování v databázi

Re:Vysvětlete mi indexování v databázi
« Odpověď #30 kdy: 15. 06. 2018, 19:36:58 »
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.


Re:Vysvětlete mi indexování v databázi
« Odpověď #31 kdy: 15. 06. 2018, 19:45:53 »
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…

Lothic

Re:Vysvětlete mi indexování v databázi
« Odpověď #32 kdy: 15. 06. 2018, 20:01:10 »
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?

Re:Vysvětlete mi indexování v databázi
« Odpověď #33 kdy: 15. 06. 2018, 20:18:32 »
Č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).

Kit

Re:Vysvětlete mi indexování v databázi
« Odpověď #34 kdy: 15. 06. 2018, 22:08:24 »
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.


Lothric

Re:Vysvětlete mi indexování v databázi
« Odpověď #35 kdy: 16. 06. 2018, 12:52:42 »
Č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 :)

BoneFlute

  • *****
  • 1 981
    • Zobrazit profil
Re:Vysvětlete mi indexování v databázi
« Odpověď #36 kdy: 16. 06. 2018, 13:02:10 »
Č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.

Re:Vysvětlete mi indexování v databázi
« Odpověď #37 kdy: 16. 06. 2018, 13:43:51 »
Č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.

Re:Vysvětlete mi indexování v databázi
« Odpověď #38 kdy: 16. 06. 2018, 15:24:26 »
Č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 2 , 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 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 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 - 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. Tuhle fintu umí syscall mmap(). Přesněji řečeno, mmap() je třeba zavolat na otevřený file descriptor (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.

Kit

Re:Vysvětlete mi indexování v databázi
« Odpověď #39 kdy: 16. 06. 2018, 16:52:09 »
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.

BoneFlute

  • *****
  • 1 981
    • Zobrazit profil
Re:Vysvětlete mi indexování v databázi
« Odpověď #40 kdy: 16. 06. 2018, 20:27:46 »
budu nakonec se svým tapetováním vypadat jako břídil.
Náhodou, pěkný čtení.

lmdb

Re:Vysvětlete mi indexování v databázi
« Odpověď #41 kdy: 16. 06. 2018, 23:04:15 »
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

Re:Vysvětlete mi indexování v databázi
« Odpověď #42 kdy: 16. 06. 2018, 23:24:36 »
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.