funkcionálně.cz

Přední český blog o funkcionálním programování, kde se o funkcionálním programování nepíše
««« »»»

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

10. 11. 2015 — k47

Stará poučka říká, že im­ple­men­tace strán­ko­vání pomocí SQL dotazů s limit/offset klau­zu­lemi je pomalá.

Když tuto zásadu ne­dávno zo­pa­ko­val Filip Pro­cházka na ne­dávné Po­slední Sobotě, na­padlo mě, že to nemusí být nutně pravda. Sta­čilo by, aby každý uzel in­ter­ního B-stromu ob­sa­ho­val in­for­maci jak je velký jeho pod­strom a limit/offset strán­ko­vání by mohlo být stejně rychlé jako strán­ko­vání pomocí jiných metod.

Pro­blém spo­čívá v tom, že limit/offset strán­ko­vání ob­vykle neumí najít bod, kde stránka začíná. Da­ta­báze proto musí číst index, podle kte­rého se vý­sledky řadí, od za­čátku a po­čí­tat na kolik zá­znamů na­ra­zila. Když pře­skočí offset po­lo­žek, přečte limit zá­znamů a ty vrátí. Tohle je oči­vidně li­ne­ární ope­race a když mám velkou da­ta­bázi a v dotazu uvedu limit 10 offset 100000000 mám o zábavu po­sta­ráno, pro­tože da­ta­báze musí pros­ke­no­vat sto mi­li­onů řádků, než začne dělat něco uži­teč­ného. Když nám v ta­bulce jen pár tisíc řádků, tohle ne­před­sta­vuje velký pro­blém. Ale když mám málo dat, nic ne­před­sta­vuje pro­blém.

Ná­sle­du­jící ob­rá­zek uka­zuje pří­klad, jak může vy­pa­dat kus B-stromu indexu se 150 zá­znamy. Pokud chci najít stránku limit 3 offset 147, musím projít všechno, pro­tože nevím že začíná hod­no­tou 1257. Znám jen offset.

Místo toho se silně do­po­ru­čuje tzv. seek metoda, která ne­pře­ska­kuje zá­znamy od za­čátku ta­bulky, ale v indexu přímo najde místo, kde stránka začíná (nebo před­chozí končí) a od toho místa přečte počet zá­znamů uve­de­ných v klau­zuli limit. Velice jed­no­du­ché a efek­tivní. Když můžu použít index je na­le­zení zá­znamu velice rychlé (běží v lo­ga­rit­mic­kém čase) a pro­tože mám index1, jsou zá­znamy se­řa­zeny a tedy všechny po­třebné zá­znamy budou vedle sebe.

Seek metoda má drobný pro­blém v tom, že s ní nemůžu skočit na li­bo­vol­nou stránku, ale musím se na ní po­stupně dostat. To ale nevadí, pro­tože po­stupné strán­ko­vání dává větší smysl než skok na li­bo­vol­nou stránku. Navíc je tato metoda sta­bilní a ne­roz­hodí ji nové po­ložky při­dané na za­čá­tek ta­bulky.

Rozdíl mezi seek me­to­dou a offset me­to­dou je jen v tom, že jedna umí najít přesné místo, kde stránka začíná a druhá nikoli a proto musí ske­no­vat všechno od za­čátku. Otázka zní: proč ho neumí najít?

Da­ta­báze ty­picky pra­cují s bloky dat, které mají pevně danou ve­li­kost a jeden uzel B-stromu, ať už kořen, in­terní nodus nebo list, za­bí­rají jeden blok. Kdyby šlo o kom­pletní, vy­vá­žený strom, kde každý záznam má stej­nou délku, mohl bych najít každý záznam podle off­setu velice jed­no­duše. Si­tu­ace ale není tak jed­no­du­chá, pro­tože zá­znamy mají pro­měn­li­vou délku a me­cha­nis­mus vy­va­žo­vání B-stromu za­ru­čuje, že uzly budou z části prázdné. Uzly můžou být roz­dě­lené nebo slou­čené, když jejich ve­li­kosti pře­sáhly určité meze.

Tady se do­stá­vám k jádru věci: Jak se zbavit nut­nosti ske­no­vat všechno od za­čátku? Řešení je tri­vi­ální: Stačí, když do kaž­dého uzlu přidám in­for­maci o ve­li­kosti celého pod­stromu, jak je na­zna­čeno v ná­sle­du­jí­cím sché­matu. Jde o stejný strom, jen každý vnitřní uzel nese jednu ano­taci navíc.

Do pod­stromu musím se­stou­pit jen pokud je z jeho ve­li­kosti jasné, že se záznam, který po­tře­buji, na­chází právě v něm, jinak ho pře­sko­čím. Když bych po­lo­žil dotaz s limit 3 offset 147 je jasné, že do prv­ního pod­stromu ob­sa­hu­jí­cího 18 zá­znamů vůbec ne­mu­sím vstou­pit a celý ho pře­sko­čím. Po tomhle kroku mi zbývá skočit přes 129 zá­znamů. Jestliže další pod­strom ob­sa­huje méně zá­znamů, pře­sko­čím ho, pokud má více, vlezu do něj a celý postup budu opa­ko­vat o úroveň níž. S těmito změ­nami strán­ko­vání běží v lo­ga­rit­mic­kém čase místo li­ne­ár­ního, tedy stejně jako seek metoda. A do­konce to fun­guje i když mám v dotazu where klau­zule, které po­krý­vají prefix indexu po­u­ži­tého k řazení – stejně jako seek metoda.

Jeden im­ple­men­tační pro­blém tohoto pří­stupu před­sta­vuje při­dá­vání a mazání po­lo­žek. Změna v lis­tech se pro­mítne do všech uzlů na cestě ke kořeni a to může vést k write am­pli­fi­cation. To ale není nic, co by se nedalo vy­ře­šit líným způ­so­bem, kdy se změny za­pi­sují do logu a jsou apli­ko­vány na B-strom strom až poz­ději en masse. Ostatně re­lační da­ta­báze přesně tohle dělají už třicet let.

Ak­tu­a­li­zace:

Když jsem začal pře­mýš­let, proč se tohle ne­po­u­žívá, na­padlo mě vy­svět­lení, které je tak oči­vidné, že se nelze divit, že jsem si ho ne­u­vě­do­mil dřív. Pod svíc­nem sku­tečně bývá nej­větší tma.

Jde o to, že abych mohl dělat rychlé limit/offset strán­ko­vání po­psané výše, po­tře­buji index. A když už nám index, můžu jed­no­duše použít seek metodu. Takže asi tak.


Dále k tématu:

  1. Tady před­po­klá­dám index po­sta­vený na B-stromu. Exis­tují i jiné způ­soby in­de­xo­vání, které data neřadí, jako na­pří­klad ha­sho­vání. To teď neberu v úvahu, pro­tože téměř všechny RDBMS stan­dardně po­u­ží­vají ně­ja­kou verzi B-stromu.
@kaja47, kaja47@k47.cz, deadbeef.k47.cz, starší články