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:

  1. 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.

Flattr this!

This entry was posted in DB, DS. Bookmark the permalink.

2 Responses to limit/offset stránkování nemusí být pomalé

  1. Pěkný! Myslíš že to autory databáze nenapadlo, nebo tam je nějaký problém který nenapadl tebe?

    • Kdybych měl spekulovat proč se to nepoužívá, vsadil bych na to, že jde o z části o potenciálně vysokou cenu aktualizace čítačů, faktu, že to v nějakých situacích není flexibilní jako jiné metody stránkování a pak toho, že se všichni více méně smířili se statusem quo, kdy limit/offset je na stránkování pomalý a nevolají po změně.

      Kdyby tohle některá databáze používala, mělo by to v podstatě režii jako jeden sekundární index na každé tabulce, nehledě jestli je to potřeba nebo ne.

Leave a Reply

Your email address will not be published. Required fields are marked *