limit/offset stránkování nemusí být pomalé
Stará poučka říká, že implementace stránkování pomocí SQL dotazů s limit/offset klauzulemi je pomalá.
Když tuto zásadu nedávno zopakoval Filip Procházka na nedávné Poslední Sobotě, napadlo mě, že to nemusí být nutně pravda. Stačilo by, aby každý uzel interního B-stromu obsahoval informaci jak je velký jeho podstrom a limit/offset stránkování by mohlo být stejně rychlé jako stránkování pomocí jiných metod.
Problém spočívá v tom, že limit/offset stránkování obvykle neumí najít bod, kde
stránka začíná. Databáze proto musí číst index, podle kterého se výsledky řadí,
od začátku a počítat na kolik záznamů narazila. Když přeskočí offset
položek, přečte
limit
záznamů a ty vrátí. Tohle je očividně lineární operace a když mám
velkou databázi a v dotazu uvedu limit 10 offset 100000000
mám o zábavu
postaráno, protože databáze musí proskenovat sto milionů řádků, než začne dělat
něco užitečného. Když nám v tabulce jen pár tisíc řádků, tohle nepředstavuje
velký problém. Ale když mám málo dat, nic nepředstavuje problém.
Následující obrázek ukazuje příklad, jak může vypadat kus B-stromu indexu se
150 záznamy. Pokud chci najít stránku limit 3 offset 147
, musím
projít všechno, protože nevím že začíná hodnotou 1257. Znám jen offset
.
Místo toho se silně doporučuje tzv. seek metoda, která nepřeskakuje
záznamy od začátku tabulky, ale v indexu přímo najde místo, kde stránka začíná
(nebo předchozí končí) a od toho místa přečte počet záznamů uvedených v
klauzuli limit
. Velice jednoduché a efektivní. Když můžu použít index je
nalezení záznamu velice rychlé (běží v logaritmickém čase) a protože mám
index1 , jsou záznamy seřazeny a tedy všechny potřebné záznamy
budou vedle sebe.
Seek metoda má drobný problém v tom, že s ní nemůžu skočit na libovolnou stránku, ale musím se na ní postupně dostat. To ale nevadí, protože postupné stránkování dává větší smysl než skok na libovolnou stránku. Navíc je tato metoda stabilní a nerozhodí ji nové položky přidané na začátek tabulky.
Rozdíl mezi seek metodou a offset metodou je jen v tom, že jedna umí najít přesné místo, kde stránka začíná a druhá nikoli a proto musí skenovat všechno od začátku. Otázka zní: proč ho neumí najít?
Databáze typicky pracují s bloky dat, které mají pevně danou velikost a jeden uzel B-stromu, ať už kořen, interní nodus nebo list, zabírají jeden blok. Kdyby šlo o kompletní, vyvážený strom, kde každý záznam má stejnou délku, mohl bych najít každý záznam podle offsetu velice jednoduše. Situace ale není tak jednoduchá, protože záznamy mají proměnlivou délku a mechanismus vyvažování B-stromu zaručuje, že uzly budou z části prázdné. Uzly můžou být rozdělené nebo sloučené, když jejich velikosti přesáhly určité meze.
Tady se dostávám k jádru věci: Jak se zbavit nutnosti skenovat všechno od začátku? Řešení je triviální: Stačí, když do každého uzlu přidám informaci o velikosti celého podstromu, jak je naznačeno v následujícím schématu. Jde o stejný strom, jen každý vnitřní uzel nese jednu anotaci navíc.
Do podstromu musím sestoupit jen pokud je z jeho velikosti jasné, že se záznam,
který potřebuji, nachází právě v něm, jinak ho přeskočím. Když bych položil
dotaz s limit 3 offset 147
je jasné, že do prvního podstromu obsahujícího 18
záznamů vůbec nemusím vstoupit a celý ho přeskočím. Po tomhle kroku mi zbývá
skočit přes 129 záznamů. Jestliže další podstrom obsahuje méně záznamů,
přeskočím ho, pokud má více, vlezu do něj a celý postup budu opakovat o úroveň
níž. S těmito změnami stránkování běží v logaritmickém čase místo lineárního,
tedy stejně jako seek metoda. A dokonce to funguje i když mám v dotazu
where
klauzule, které pokrývají prefix indexu použitého k řazení - stejně
jako seek metoda.
Jeden implementační problém tohoto přístupu představuje přidávání a mazání položek. Změna v listech se promítne do všech uzlů na cestě ke kořeni a to může vést k write amplification. To ale není nic, co by se nedalo vyřešit líným způsobem, kdy se změny zapisují do logu a jsou aplikovány na B-strom strom až později en masse. Ostatně relační databáze přesně tohle dělají už třicet let.
Aktualizace:
Když jsem začal přemýšlet, proč se tohle nepoužívá, napadlo mě vysvětlení, které je tak očividné, že se nelze divit, že jsem si ho neuvědomil dřív. Pod svícnem skutečně bývá největší tma.
Jde o to, že abych mohl dělat rychlé limit/offset stránkování popsané výše, potřebuji index. A když už nám index, můžu jednoduše použít seek metodu. Takže asi tak.
Dále k tématu:
- Order statistic tree
- Architecture of a Database System
- Kdy vám SQL_CALC_FOUND_ROWS zabije databázi
- R-trees Have Grown Everywhere (kapitola 2.4 se zmiňuje o něčem blízkém)
- Tady předpokládám index postavený na B-stromu. Existují i jiné způsoby indexování, které data neřadí, jako například hashování. To teď neberu v úvahu, protože téměř všechny RDBMS standardně používají nějakou verzi B-stromu.