Jak databáze řeší indexy?

[klobások]

Ked si vezmem ze vsetky db pod kapotou pouzivaju na indexy btree(pripadne rtree na priestorove objekty) a hashmapy pre uchovanie riadkov v tabulkach, tak by ma vcelku zaujimalo, ako riesia porovnavanie vysledkov a radenie. Napriklad ak nejaka query vrati 100 000 zaznamov pre index A a rovnako pre index B, tak ratam ze db musi do pamete nacitat 200 000 zaznamov a potom to nejak porovnat a odfiltrovat tie ktore sa nezhoduju. Nehovoriac o tom ze ak mam par mega zaznamov tak cely index asi tiez nezaberie len par kB. Pripadne potom este aplikovat aj radenie. Cize ma zaujima to, ako to robia tak aby si nezaplnili pamet pokial ide o nejaku vytazenu db napriklad a stale vedia zabezpecit rychlost odozvy?

Davkovanie moze byt riesenie ale v konencom dosledku sa aj tak musia porovnat vsekty najdene vysledky cize tam uz davkovanie asi nepomoze, plus keby sa vysledky davok zapisovali na disk, kym sa spracuju zvysne ulohy na neskorsie porovnanie, tak by to najskor znacne spomalilo takuto db, takze davkovanie tam asi nebude.

[Reklama]

[Filip Jirsák]

Klasická databáze nenačítá vše do paměti, naopak jedna z podstatných věcí, které databáze dělaly, byla optimalizace umístění dat na disku – aby se využilo vlastností rotačních disků. Na druhou stranu dnes existují databáze, které vše uchovávají jenom v RAM, ty samozřejmě používají jiné datové struktury.

Ideální je, když databáze může pro porovnávání nebo řazení použít právě index. Pokud je dotaz napsaný tak, že databáze musí použít dva různé indexy, které vrátí zhruba stejné množství řádků, a následně je musí spojit (najít jen ty řádky, které jsou v obou indexech), je to jedna z nejnáročnějších operací, které může databáze s indexy dělat. A pokud se takový dotaz provádí častěji, měl by pro něj existovat jeden index, ve kterém databáze dohledá záznamy rovnou. Každopádně ale ani v tomhle případě nemusí databáze načíst všechny záznamy do paměti, prostě jen z indexu postupně načítá obě množiny záznamů a prosívá je tak, aby zbyly jen odkazy na řádky, které jsou v obou množinách. Pokud dotaz vyžaduje nějaká data z tabulky (nestačí data uložená v indexu), postupně pak pro ty nalezené odkazy načítá příslušné záznamy a vrací je klientovi.

[Pavel Stěhule]

Jak indexy, tak tabulky jsou na disku organizované pomocí stránek - vždy se načítají celé stránky a ukládají se do interní cache datových stránek - v Postgresu shared buffers, která je omezena počtem. Zpracování probíhá často po stránkách, načtu minimální sadu indexových stránek, abych se dostal k listům, získám adresy, a pro každou adresu dohledám záznam ve stránce, která už je v cache, nebo kterou musím načíst do cache. Pokud nestačí cache, tak přepisuji nejdéle nepoužité stránky. Díky tomu mohu provést operace nad tabulkami, které se mi ani náhodou nevejdou do RAM - za cenu, že některé stránky načítám z disku opakovaně. U datových stránek to nemusí být až takový problém. Naopak u klíčových (kořenových) stránek indexu to může mít fatální dopad na výkon.

I z tohoto důvodu má Postgres horní omezení velikosti použitého indexu. Pokud by hrozilo velké riziko, že index se nevejde do cache Pg případně FS cache, tak se prostě nepoužije, a úloha se provede sekvenčně - na což v podstatě není potřeba skoro žádná RAM.

[Pavel Stěhule]

Ideální je, když databáze může pro porovnávání nebo řazení použít právě index. Pokud je dotaz napsaný tak, že databáze musí použít dva různé indexy, které vrátí zhruba stejné množství řádků, a následně je musí spojit (najít jen ty řádky, které jsou v obou indexech), je to jedna z nejnáročnějších operací, které může databáze s indexy dělat.

Předpokládám, že se tady bavíme o indexech nad jednou tabulkou. Samozřejmě, více sloupcový index je efektivnější než dva jednousloupcové - nicméně spojení indexů zas až tak drahá operace není - v Postgresu se používá bitmap heap scan. To už kdysi umělo FoxPro. Tam hodně zaleží na datech, jak spolu korelují hodnoty ve sloupcích. Jsou situace, kdy je bitmap heap scan pomalý, ale ve většině případů je postačující. Každý index něco stojí - zpomaluje inserty, update, a je dobré jich mít co nejméně.

[Kit]

... Pokud nestačí cache, tak přepisuji nejdéle nepoužité stránky...

To by byl poněkud neefektivní algoritmus. Doufám, že v Pg je jiný.

[Reklama]

[Miroslav Šilhavý]

Předpokládám, že se tady bavíme o indexech nad jednou tabulkou.

Index nad více tabulkami? Tím máte na mysli co? Napadá mě snad jedině index nad zhmotněným pohledem..?

[ivoszz]

... Pokud nestačí cache, tak přepisuji nejdéle nepoužité stránky...

To by byl poněkud neefektivní algoritmus. Doufám, že v Pg je jiný.

Proč? LRU je pro cache jeden z nejpoužívanějších. Jednoduchý, levný a poměrně efektivní.

[ondrej _]

Cize ma zaujima to, ako to robia tak aby si nezaplnili pamet pokial ide o nejaku vytazenu db napriklad a stale vedia zabezpecit rychlost odozvy?

Nevedia. Bez dostatocnych prostriedkov a optimalizacie na strane DB a aplikacie to nejde. Dnes v dobe lacneho a vykonneho HW je to menej casty jav ale stale sa to deje. Databazy niesu zazracne a v kombinacii s HW na ktorom bezia maju svoje limity. Ak na nich narazia, tak odozva a vykon leti dole a niekedy aj cela DB.
Ako to konkretne robia sa pri closed source  DB len tak nedozvies a mozes len hadat. To je sucast know-how.

[Pavel Stěhule]

Předpokládám, že se tady bavíme o indexech nad jednou tabulkou.

Index nad více tabulkami? Tím máte na mysli co? Napadá mě snad jedině index nad zhmotněným pohledem..?

V rámci jednoho dotazu můžete mít více indexů nad různými tabulkami. Některé databáze umí, pro urychlení JOINu, jeden index pro více tabulek, ale to jsem tady nemyslel. Jak jsem psal - upřesňoval jsem situaci, kdy se v dotazu nad jednou tabulkou má aplikovat více indexů.

[Pavel Stěhule]

... Pokud nestačí cache, tak přepisuji nejdéle nepoužité stránky...

To by byl poněkud neefektivní algoritmus. Doufám, že v Pg je jiný.

Přesněji https://madusudanan.com/blog/understanding-postgres-caching-in-depth/

[Miroslav Šilhavý]

V rámci jednoho dotazu můžete mít více indexů nad různými tabulkami. Některé databáze umí, pro urychlení JOINu, jeden index pro více tabulek, ale to jsem tady nemyslel. Jak jsem psal - upřesňoval jsem situaci, kdy se v dotazu nad jednou tabulkou má aplikovat více indexů.

Mně Váš příspěvek vyzněl, jako kdyby měl být jeden index nad více tabulkami. V teorii si to dovedu představit (dvě tabulky a foreign key mezi nimi), v praxi měl ale nenapadlo nic jiného, než materialized view, proto jsem se ptal, jestli mi něco neuniklo.