Rýchle stránkovanie v relačných databázach (diskuse)

[mirec]

Přílohy:

• models.svg (9472 bytů)
• pagination.svg (269112 bytů)
• load_data.sql (4239 bytů)

Hmm k blogu sa nedajú pridať prílohy? Tak teda pridávam sem.

[webovka]

Neznáš nějaký stránkovač, který umí garantovat, že se mu nezměnila data při přepínání na předchozí/následující (nebo i stejnou!) stránku?

Zhruba tyto situace:

1. Na právě zobrazené stránce někdo jiný změnil v DB jednu ze zobrazených položek (mohl ale také nemusel se změnit klíč/ID v závislosti na DBMS a v závislosti na velikosti změny - zdali se vešla do již alokovaného místa pro daný řádek).

2. Na předchozí než právě zobrazené stránce bylo odebráno nenulové množství řádků (čímž mj. vznikla/y, popř. byla vyřešena diskontinuita/y v ID/klíčích).

3. Na předchozí než právě zobrazenou stránku bylo přidáno nenulové množství řádků (některé mohly ale také nemusely mít ID vyhovující té diskontinuitě, pokud tam nějaká již byla).

Tyhle chyby pak vedou k fatální ztrátě dat např. když tam jsou tlačítka "vymaž celý seznam". Jenomže ten seznam co vidím není "živý" a tedy mezitím než stihnu zmáčkout tlačítko "vymaž celý seznam", tak ten seznam mohl být stokrát jakkoliv modifikovaný. Ale já přeci chci smazat pouze to co vidím a nikoliv to, co je ve skutečnosti v DB (tom se dá předejít tak, že to tlačítko je funkční pouze pro nějaký stav toho zobrazeného seznamu - např. tlačítko funguje pouze pokud sedí hash který byl tlačítku přiřazen při posledním renderu seznamu). Tyto situace jsou umocněné právě ještě chybným stránkováním.

[J]

Kdyz to kodite jako kkti tak si nic jineho nez smazat vse nezaslouzite.

[mirec]

Budem predpokladať, že záznamy sa mažú bežným POST dotazom:

Vytvorím teda tlačidlo so zoznamom ID na aktuálnej stránke:

<button type="submit" name="delete" value="1,2,3,5,7">

Po stlačení sa mi zašle zoznam ID na vymazanie a ja vymažem len to, čo bolo viditeľné v dobe vyrenderovania stránky.

Alebo iný spôsob:

<form action="...">
	<input type="hidden" name="delete" value="1">
	<input type="hidden" name="delete" value="2">
	<input type="hidden" name="delete" value="3">
	<input type="hidden" name="delete" value="5">
	<input type="hidden" name="delete" value="7">
	<input type="submit" value="Vymazať">
</form>

Ak je aplikácia v PHP, potom pole delete musí mať názov "delete[]". V ostatných jazykoch (aspoň s ktorými som robil) sa dá spracovať pole s ľubovoľným názvom.

Alebo ku každému záznamu dám checkbox a javascriptom implementujem označiť všetky:

<form action="...">
	<input type="checkbox" name="delete_1" value="1">
	<input type="checkbox" name="delete_2" value="1">
	<input type="checkbox" name="delete_3" value="1">
	<input type="checkbox" name="delete_5" value="1">
	<input type="checkbox" name="delete_7" value="1">
	<button type="button">Vybrať všetky</button>
	<input type="submit" value="Vymazať">
</form>

[webovky]

Pardón, já zmínil mazací tlačítko úplně naokraj jako ukázku kam tohle naprosto zcestné přemýšlení ("zobrazený seznam je to co je v DB") vede i v jiných případech než je stránkování.

Mě zajímá to, jak řeší tvůj stránkovač ty případy 1, 2, 3. Dle mého chápání to stránkovač(e) popsaný/é v blogu vůbec neřeší a tudíž zobrazují naprosté nesmysly v tom lepším případě a nebo se úplně rozbijou v tom běžnějším (horším) případě.

Hint: např. ty indexy co si iterátor pamatuje atd. ty vůbec nemusí existovat a nebo budou ukazovat na úplně jiné části DB atd.

[mirec]

Konkrétne čísla stránok sa nezobrazujú, sú tam len tlačidlá ďalej a späť.

Ak je stránkovanie povedzme po 10 položkách a zoradenie je podľa ID a začínam na čísle 50, potom zobrazím maximálne 10 riadkov väčších než 50. Že sa tie pred číslom 50 zmazali, zmenili, alebo sa s nimi urobilo neviem čo ma nemusí zaujímať. Dokonca môžem kľudne zmazať aj rozsah 50-55 a nič sa nestane, jednoducho sa zobrazí rozsah od 56 a odkaz na ďalšiu stranu bude od čísla 65.

[webovky]

Natvrdlost je mi vlastní. Zkusme to po douškách.

Jak vyřešíš zmizelé ID, které sis uložil do URL? Ten iterátor se ti pak musí rozbít ať chceš či nechceš, či? Pokud ti také zmizí všechna ID "okolo" těch v URL, tak se nemáš čeho chytit ani heuristikou. Co pak udělá stránkovač?

[mirec]

Ok, skúsim to vysvetliť jednoduchšie. Vysvetľovať to budem na poslednom obrázku s číslami od 1 do 15.

Na začiatok zdôrazňujem, tie čísla sú uložené fyzicky v databáze. Nie je to číslo objektu na strane, ale unikátny kľúč, podľa ktorého mám údaje zoradené.

Ak som teda na prvej strane a chcem 5 riadkov tak robím niečo typu SELECT * FROM t ORDER BY id LIMIT 6.

Chcel som teda 5 riadkov, vyberám 6. Ten 6. riadok sa odstráni v iterátore a slúži na zistenie, či existuje nasledujúca strana.

Odkaz na nasledujúcu stranu bude mať zakódovanú hodnotu (ja používam binárne kódovanie, ale je to úplne jedno aj keby som to tam posielal ako string) [5]. Teda pole obsahujúce číslo 5 (keďže som zoradil podľa jediného stĺpca, ak ich používam viacej, musím kódovať viacej hodnôt).

Ak kliknem na tlačidlo ďalej, urobím zase select typu SELECT * FROM t WHERE id > 5 ORDER BY id LIMIT 6.

Čiže zase sa odkazujem na všetky objekty nasledujúce za posledným objektom, ktorý som mal zobrazený na stránke. Keď sa medzitým zmazal objekt s ID 6, tak jednoducho dostanem [7, 8, 9, 10, 11]. Jednoducho sa vygeneroval odkaz, ktorý mi vráti to, čo nasleduje za posledným objektom (všetko, čo má ID väčšie než 5). Najhoršie, čo sa mi môže stať je, že po ďalšom kliknutí budem mať prázdnu stránku, pretože niekto vymazal všetko, čo malo ID väčšie než 5.

Ak je kľúč zoradenia kompozitný tak samozrejme tie podmienky budú vyzerať zložitejšie. Napríklad pri takom zoradení podľa date_created, id to bude WHERE date_created > ... OR (date_created = ... AND id > ...)..

Nevyhnutnou podmienkou je samozrejme, aby kombinácia kľúčov bola vždy unikátna. Prinajhoršom sa v normalizovanej databáze dá na koniec každého orderu pridať ID, čím sa podmienka zaistí v každej situácii.

[webovky]

Díky za to pomalé vysvětlení a potvrzení. Vážím si tvého času! Naštěstí jsem to přesně takhle pochopila z blogu.

Toto však předpokládá, že ID (resp. celý složený klíč) bude splňovat tři požadavky:

1. je vždy za jakýchkoliv okolností seřaditelné (i po změnách jako přidání a odebrání řádků) 2. existující pořadí se nikdy nezmění ani přidáním ani odebráním položek 3. nikdy nejsou recyklována již neobsazená ID (ani přetečením)

Bod (1) je asi pohoda. Bod (2) už může být problém (zejm. u složených klíčů). A bod (3) je myslím nesplnitelný, či?

[mirec]

1 nie je problém, začnem teda 2:

Pridaním, alebo odobraním riadkov sa nič nezmení na podmienke typu ID > 6. Príklad:

Databáza je v stave [1, 2, 4, 5, 6, 7, 8], vyrenderujem [1, 2, 4, 5, 6], link bude obsahovať [6].

Ak som medzitým pridal do databázy riadok s ID 3, aj tak po kliknutí na ďalšiu stránku budem mať [7, 8]. Žiadne opakovanie [6].

Ak sa medzitým zmazal riadok s ID 7, nasledujúca strana bude mať na základe podmienky ID > 6 položky [8]. Či je to zlé, alebo dobré nechcem hodnotiť, jednoducho je to vlastnosť a myslím, že je to konzistentnejšie než robiť limit, offset, kde by v týchto prípadoch boli riadky opakovane.

3. je zaujímavejšia a s ID moc nedáva zmysel. Budem teda stále používať tie isté čísla, ale povedzme, že reprezentujú časový okamih poslednej aktualizáie. Ak sa napríklad 1 zvýši na 9, potom na prvej strane som mal [1, 2, 4, 5, 6] a po kliknutí na ďalej budem vidieť duplicitne 1 - [7, 8, 9 (pôvodne 1)]. V zmysle chcem vidieť novšie úpravy oproti 6 je to logicky správne aj keď v inom kontexte to môže byť považované z chybu.

[podlesh]

Tohle je jeden z důvodů, proč se stal populární koncept "kurzoru" (společně s popularitou nekonečného skrolování). Já osobně tedy moc fanoušek nejsem.

V případě normálního stránkování rozhodně platí že žádné tlačítko nesmí spoléhat na to že znova provede tentýž dotaz a dostane stejné výsledky! Operace musí pracovat s tím co je skutečně zobrazeno, například ve formě seznamu ID. ID můžeš poslat z frontendu (jak tu napsal mirec) nebo si je můžeš pamatovat na serveru (v session). V tom druhém případě si dokonce můžeš pamatovat kompletní seznam všech ID celého seznamu, před stránkováním (a stránkování jako takové tedy vůbec nemusí provádět celý dotaz jako takový - z DB jen dotahneš detaily pro zobrazení).

Je dokonce možné mít tento seznam (tj. celý výsledek hledání) v databázi, jako temporary tabulku. Moc to neškáluje, ale pro různé "intranetové tabulky" je to ideální. Bývala to běžná praxe, ale to bylo v dřevních dobách kdy se nahrazovaly různé FoxPro appky a uživatelé měli jiné nároky a očekávání.

[webovky]

Pokud myslíš kurzor v jedné transakci (long-running transaction), tak ano.

Ale jinak netransakční kurzor vůbec nic neřeší pokud ti někdo ten záznam pod kurzorem smaže (a např. smaže i ty záznamy "okolo" kurzoru). Nebo máš na mysli ještě něco jiného?

[mirec]

Kurzorové stránkovanie je medzi web vývojármi bežne používaný termín pre stránkovanie pomocou unikátnej kombinácie kľúčov pričom kľúče sa serializujú do URL adresy.

Pri tejto technike je úplne jedno, či riadok obsahujúci sadu kľúčov v dobe ďalšieho requestu existuje v databáze, alebo nie pretože stránkovanie sa dotazuje na objekty nasledujúce po tejto kombinácii kľúčov. Neodkazuje sa na samotný riadok a je teda úplne irelevantné, či riadok ešte existuje, alebo nie.

To je vec, ktorú som implementoval a v blogu sa tak trochu vyhýbam ustálenejšiemu spojenu kurzorové stránkovanie, pretože databázisti si hneď predstavia server side kurzor, čo je niečo úplne iné.

Tu je pod pojmom kurzor myslená sada serializovaných kľúčov od ktorej začínam získavať riadky. Nič viac, nič menej.

[podlesh]

Pokud myslíš kurzor v jedné transakci (long-running transaction), tak ano.

Ale jinak netransakční kurzor vůbec nic neřeší pokud ti někdo ten záznam pod kurzorem smaže (a např. smaže i ty záznamy "okolo" kurzoru). Nebo máš na mysli ještě něco jiného?

Ne, nejedná se o databázový kurzor. Ten se v 21. století nepoužívá, jelikož MySQL nic takového nemá.

Zjednodušeně: Jedná se o API kdy místo tradičního indexu řádky (offsetu) má každá řádka nějakou unikátní hodnotu (a doporučení je používat "opaque token") a request je pak "X rádek za řádkou TOKEN", případně "X řádek před řádkou TOKEN". Reálně se pak většinou použije PK a server pak jen přidá něco jako "id>?" - nicméně funguje to i pro složené klíče aniž by to frontend tušil (složený klíč se nějak efektivně zaserializuje+base64 nebo tak něco).

[plostenka]

Jak casto budes hledat pocet radku pres SELECT COUNT()? No... furt. Je to draha operace? Je, proto to resis.

Jak casto budes pridavat knihu do DB? V pomeru k SELECTum vyjimecne. Takze pridej UPDATE stats SET pocetknih=pocetknih+1; jako trigger na INSERT do tabulky s knizkama, ekvivalentne pro DELETE; Pocet radku pak nebude agregovana funkce, ale trivialni SELECT pocetknih FROM stats;

[mirec]

To síce rieši časť problému, ale ani neviem kedy som písal niečo tak jednoduché.

Tam, kde pracujem, mám vždy za úlohu robiť komplexné pohľady s flexibilnými možnosťami filtrovania. Niektoré vrátia iba pár riadkov, to by šlo, ale iné vrátia povedzme 80% pôvodných riadkov. Aby bola väčšia sranda, filtre sa dajú kombinovať. Keby som to teda chcel riešiť takto, musel by som generovať rozsiahle štatistiky pre všetky kombinácie filtrov, ktorých výsledkom je veľký počet riadkov. Viem si síce teoreticky predstaviť vytiahnuť niektoré štatistiky zo štatistických tabuliek postgresu, urobiť algoritmus, ktorý mi optimalizuje zoznam kombinácií a tie by som ukladal do vlastnej tabuľky štatistík, ale znie to tak šialene, že by som týmto smerom nechcel ísť.

[plostenka]

Pak jedine poradne promyslet indexy a delat COUNT() pres indexovane radky. Ono kdyz si zapnes logy, tak uvidis ze uzivatele nejcastejsi filtruji podle X, a muzes optimalizovat dal.

[johnyK]

ja se v tom porad neorientuji a rad bych se zeptal: (nejdriv ale ty okrajove podminky)

mejme tabulku 'sklad' pro historii skladu, ve ktere se zaznamenavaji ty pohyby zbozi na skladu. Tabulka sestava z nasledujicich sloupcu:

id (int)  primary key 
user (char)
datum_pohybu (datum)
cislo_zbozi (char) (index)
akt_mnozstvi_na_sklade (decimal)
....
....

Obvykle chce zakaznik z takove tabulky videt prehled setrideny podle cisla_zbozi, pricemz ten prehled zacina nejakym konkternim cislem zbozi. To cislo zbozi je nejaka identifikace napr. sroubu, matic, podlozek, kompresoru, .... . Napr. sroub M6x40 ma oznaceni '02.00.1845'. Pak vypada ten prikaz:

select * from sklad where cislo_zbozi>='02.00.1845' order by cislo_zbozi.

Pri milionech zaznamu by ta vysledkova mnozina byla prilis velka a je treba to strankovani. Rekneme, ze se pouzije tedy limit 20, kdyz chceme strankovat po 20 zaznamech.

select * from sklad where cislo_zbozi>='02.00.1845' order by cislo_zbozi limit 20

Jak vypada ted ten prisiti prikaz, ktery nacte tech 20 dalsich radku? Je mi jasne, ze se do toho prikazu musi zamontovat nejak ty hodnoty ktere se zjisti z toho posledniho, prave nacteneho radku.

Co vse muusi byt jeste splneno aby to bezelo rychle.

Jeste bych chtel poznamenat, ze zatim jsem mel zato, ze to strankovani se da udelat 'rozumne' pouze tak, jak je popsano napr. zde:

https://use-the-index-luke.com/sql/partial-results/fetch-next-page

Ten vyse popsany zpusob ma tu nevyhodu v tom, ze to funguje spravne pouze u postgresql a oracle, protoze se vyuziva ten 'row-value-syntax' ve where klausuli, ktery rada databazi neumi spravne realizovat. Jestlize mate tedy nejaky jiny, obecnejsi pristup, tak to by bylo velmi zajimave.

[mirec]

Začnem odspoedu. Row value tam vôbec nie je potrebný, vlastne oproti limitu je to hrozná otrava.

Mnou popisovaná metóda je identická s metódou v linku.

Zoradenie musí byť vždy podľa sady kľúčov, ktorá dá jednoznačné zoradenie. Predpokladám, že označenie 02.00.1845 nie je unikátne (alebo je?). Ak by bolo unikátne, potom by stačilo WHERE cislo_zbozi > '02.00.1866' ak je '02.00.1866' posledným záznamom.

Teraz väčšia sranda, čo ak to unikátne nie je. V tomto prípade musí byť zoradenie podľa kombinácie kľúčov, ktorá je unikátna, napr. ORDER BY cislo_zbozi, id. Podmienka teda bude vyzerať WHERE cislo_zbozi > '02.00.1845' OR cislo_zbozi = '02.00.1845' AND id > 20 (za predpokladu, že posledný riadok má id = 20).

Teraz k tomu, čo musí byť splnené, aby to fungovalo rýchlo ...

Najskôr si predstavme situáciu, že cislo_zbozi má samostatný, nie kompozitný index.

Databázový systém ako Postgresql má k stĺpcom štatistiky. Dokonca si uchováva aj zoznam najčastejších hodnôt, takže vie zhruba odhadnú počet vrátených riadkov pre dotaz celkom presne pre bežné aj často vyskytujúce sa riadky. Ak cislo_zbozi tvorí malé clustre, potom dotaz bude prechádzať riadky podľa indexu cislo_zbozi jednoduchým index scanom v poradí a zároveň bude sortovať riadky podľa ID metódou incremental sort.

Ak je tam veľa opakujúcich sa riadkov, bude lepšie definovať kompozitný index cislo_zbozi, id, takže selecty budú len scanovať index podľa kompozitného kľúča, čo má zložitosť LOG(m) + n pričom m je počet riadkov v tabuľke a n je počet požadovaných riadkov (hodnota LIMIT).