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

16.4.2023 18:47 | Přečteno: 1728× | Programovanie | | poslední úprava: 18.4.2023 15:08

Tento článok rozoberá rôzne spôsoby stránkovania v databáze, ich nevýhody a dôvody, prečo sú pomalé. Nakoniec predstavím aktuálne riešenie, ktoré používam pre stránkovanie vo veľkých tabuľkách.

Ako pokusnú databázu budem používať fiktívnu databázu kníh. Tabuľka book obsahuje ID a názov knihy. V tabuľke book_rating sú hodnotenia kníh (hodnotenie je hodnota od 1 do 5). Tabuľka book_order obsahuje fiktívne nákupy kníh (total_price pretože jeden nákup môže zahŕňať viac kusov).

Obrázok 1: Databázové modely

SQL pre vytvorenie databázy vyzerá nasledovne:

CREATE TABLE book (
    id bigint NOT NULL,
    name character varying(100) NOT NULL,
    year integer NOT NULL
);

ALTER TABLE book ALTER COLUMN id ADD GENERATED BY DEFAULT AS IDENTITY (
    SEQUENCE NAME book_id_seq
    START WITH 1
    INCREMENT BY 1
    NO MINVALUE
    NO MAXVALUE
    CACHE 1
);

CREATE TABLE book_order (
    id bigint NOT NULL,
    total_price numeric(10,2) NOT NULL,
    book_id bigint NOT NULL
);

ALTER TABLE book_order ALTER COLUMN id ADD GENERATED BY DEFAULT AS IDENTITY (
    SEQUENCE NAME book_order_id_seq
    START WITH 1
    INCREMENT BY 1
    NO MINVALUE
    NO MAXVALUE
    CACHE 1
);

CREATE TABLE book_rating (
    id bigint NOT NULL,
    rating integer NOT NULL,
    book_id bigint NOT NULL
);

ALTER TABLE book_rating ALTER COLUMN id ADD GENERATED BY DEFAULT AS IDENTITY (
    SEQUENCE NAME book_rating_id_seq
    START WITH 1
    INCREMENT BY 1
    NO MINVALUE
    NO MAXVALUE
    CACHE 1
);

ALTER TABLE ONLY book_order
    ADD CONSTRAINT book_order_pkey PRIMARY KEY (id);

ALTER TABLE ONLY book
    ADD CONSTRAINT book_pkey PRIMARY KEY (id);

ALTER TABLE ONLY book_rating
    ADD CONSTRAINT book_rating_pkey PRIMARY KEY (id);

CREATE INDEX book_order_book_id_idx ON book_order USING btree (book_id);

CREATE INDEX book_rating_book_id_idx ON book_rating USING btree (book_id);

CREATE INDEX book_year_56cba46b ON book USING btree (year);

ALTER TABLE ONLY book_order
    ADD CONSTRAINT book_order_book_id_idx_fk_book_id FOREIGN KEY (book_id) REFERENCES book(id) DEFERRABLE INITIALLY DEFERRED;

ALTER TABLE ONLY book_rating
    ADD CONSTRAINT book_rating_book_id_idx_fk_book_id FOREIGN KEY (book_id) REFERENCES book(id) DEFERRABLE INITIALLY DEFERRED;

Skript pre generovanie dát je s súbore load_data.sql.

Výber hodnotení kníh

Nasledujúci dotaz vyberie 10 hodnotení kníh podľa ID:

SELECT book_id, rating FROM book_rating ORDER BY id LIMIT 10;
┌─────────┬────────┐
│ book_id │ rating │
├─────────┼────────┤
│   91406 │      4 │
│    7794 │      1 │
│   11422 │      2 │
│   54729 │      4 │
│   24238 │      1 │
│   12438 │      2 │
│   79359 │      5 │
│   58785 │      4 │
│    3287 │      2 │
│   50076 │      5 │
└─────────┴────────┘
(10 rows)

Time: 0,371 ms

Zatiaľ všetko vyzerá v poriadku. Pre istotu sa pozrime na query plán:

EXPLAIN (COSTS FALSE, ANALYZE TRUE, TIMING FALSE) SELECT book_id, rating FROM book_rating ORDER BY id LIMIT 10;
┌─────────────────────────────────────────────────────────────────────────────────┐
│                                   QUERY PLAN                                    │
├─────────────────────────────────────────────────────────────────────────────────┤
│ Limit (actual rows=10 loops=1)                                                  │
│   ->  Index Scan using book_rating_pkey on book_rating (actual rows=10 loops=1) │
│ Planning Time: 0.133 ms                                                         │
│ Execution Time: 0.081 ms                                                        │
└─────────────────────────────────────────────────────────────────────────────────┘

Dotaz vykonáva rýchly index sken obmedzený na 10 riadkov. Samotný čas vykonávanie 0.081 ms je veľmi dobrá hodnota.

Count je pomalý

Typické stránkovanie potrebuje najskôr skontrolovať počet riadkov v tabuľke. Po pridaní štandardného stránkovania v djangu sa zrazu webová aplikácia spomalí. Zároveň medzi vykonanými dotazmi pribudol nový dotaz:

SELECT COUNT(*) FROM book_rating;
┌─────────┐
│  count  │
├─────────┤
│ 1000000 │
└─────────┘
(1 row)

Time: 34,262 ms

Žeby boli staré štatistiky? Tak skúsme vygenerovať nové a potom zopakujeme rovnaký dotaz:

ANALYZE
Time: 183,467 ms

SELECT COUNT(*) FROM book_rating;
┌─────────┐
│  count  │
├─────────┤
│ 1000000 │
└─────────┘
(1 row)

Time: 35,655 ms

Zdá sa, že vygenerovanie štatistík nemá žiaden vplyv na počítanie riadkov. Teraz sa pozrime na výstup explain:

EXPLAIN (COSTS FALSE, ANALYZE TRUE, TIMING FALSE) SELECT COUNT(*) FROM book_rating;
┌─────────────────────────────────────────────────────────────┐
│                         QUERY PLAN                          │
├─────────────────────────────────────────────────────────────┤
│ Aggregate (actual rows=1 loops=1)                           │
│   ->  Seq Scan on book_rating (actual rows=1000000 loops=1) │
│ Planning Time: 0.100 ms                                     │
│ Execution Time: 44.656 ms                                   │
└─────────────────────────────────────────────────────────────┘

Pre spočítanie riadkov v tabuľke musí databázový systém preskenovať (prečítať) kompletne celú tabuľku. Väčšina čitateľov, ktorá do hĺbky neštudovala databázové systémy si teraz asi hovorí, prečo databázový systém nepoužije index? Však uložiť počet riadkov ako metadáta tabuľky nemôže byť predsa nič ťažké.

Lenže ono to nie je ani ťažké, ono to je prakticky nemožné. Pre vysvetlenie je potrebné hlbšie poznať fungovanie databázového systému.

Ako funguje databázový systém

Programátori si často predstavujú databázový systém ako centralizovaný sklad dát, ktorý má jediný jednoznačne definovaný stav. Taký zjednodušený pohľad platí na niektoré No-SQL databázové systémy.

Pre plnohodnotné databázové systémy ACID (atomicity, consistency, isolation, durability) to však neplatí. V takom databázovom systéme môže prebiehať jedna transakcia, ktorá číta tabuľku zatiaľ čo v inej transakcii sa nahrali nové dáta (pričom ešte nie je commitnutá), v ďalšej transakcii sa niektoré riadky zmazali a v ďalšej sa niektoré riadky zmenili. Vďaka vlastnosti zvanej izolácia musí prvá transakcia vidieť celú databázu v stave, v ktorom bola na začiatku transakcie bez ohľadu na to, čo sa deje v ďalších transakciách.

Databázový systém poskytuje teda každej transakcii vlastný pohľad na dáta v určitom čase, pričom jednotlivé transakcie nesmú byť ovplyvnené inými transakciami. Aby bolo možno niečo také, musí databázový systém ukladať rôzne verzie toho istého riadku a ponechávať zmazané riadky kým sú prístupné z niektorej transakcie.

PostgreSQL implementuje izoláciu pomocou dodatočných metadát pri riadkoch tabuľky. Riadky majú informáciu o minimálnom čísle transakcia, od kedy je viditeľná a o maximálnom čísle transakcie (ak bola vymazaná). Zmena dát v databáze sa tak implementuje pridávaním nových riadkov do WAL (Write-ahead logging) súborov. Staré verzie sa môžu odstrániť až vtedy, keď nie sú dostupné zo žiadnej transakcie.

Ako teda spočítať riadky v tabuľke? Jednoducho, stačí vedieť číslo aktuálnej transakcie a postupne skenovať celú tabuľku a aplikovať pravidlá viditeľnosti pre každý riadok. Presne to PostgreSQL robí.

Čas spočítania riadkov v tabuľke má kvôli podmienke izolácie lineárnu závislosť od počtu riadkov.

Situácia môže byť aj horšia

Príklad trochu skomplikujem tým, že v zozname budem chcieť zobraziť názov knihy a tržby za predaj. Dotaz v Django ORM vyzerá nasledovne:

LIST_QUERY = (BookRating.objects
	.values('id', 'rating', 'book__name')
	.order_by('id'))

Výsledný dotaz vyzerá nasledovne:

SELECT
	"book_rating"."id",
	"book_rating"."rating",
	"book"."name" AS "name",
	SUM("book_order"."total_price") AS "total_revenue"
FROM "book_rating"
INNER JOIN "book"
	ON ("book_rating"."book_id" = "book"."id")
LEFT OUTER JOIN "book_order"
	ON ("book"."id" = "book_order"."book_id")
GROUP BY "book_rating"."id", 3
ORDER BY "book_rating"."id" ASC
LIMIT 10;

Samotný výber riadkov je celkom uspokojivý.

┌────┬────────┬─────────────────┬───────────────┐
│ id │ rating │      name       │ total_revenue │
├────┼────────┼─────────────────┼───────────────┤
│  1 │      4 │ mwJLdKU7i0Iqpe3 │        224.00 │
│  2 │      1 │ 4AYnAqiSSAmfDt5 │        232.00 │
│  3 │      2 │ EgYd9e4nYC1YX72 │        310.00 │
│  4 │      4 │ kFCMna9vycWFvNT │        337.00 │
│  5 │      1 │ 5Z9V3tTUCQPcWse │        243.00 │
│  6 │      2 │ fuQu2GhvrwMIPfE │         88.00 │
│  7 │      5 │ Wxn3gH6v2xeGD3p │        252.00 │
│  8 │      4 │ VaeKeqymBj6fOEH │        180.00 │
│  9 │      2 │ V3rkEJZ7ag8lAG0 │        310.00 │
│ 10 │      5 │ 0msAG9UwymXRs5Z │        239.00 │
└────┴────────┴─────────────────┴───────────────┘
(10 rows)

Time: 1,586 ms

Napriek tomu sa načítanie webu spomalilo na 3 s. Čo sa stalo?

Django rozpoznalo, že dotaz používa agregačné funkcie. Aby bolo možné spoľahlivo zistiť počet riadkov, musí sa dotaz spustiť ako subquery (ok, v tomto prípade by stačil jednoduchý count, ale logika za tým je pomerne zložitá, takže sa volí bezpečná aj keď pomalá metóda). Vygenerovaný dotaz vyzerá takto:

SELECT
	COUNT(*)
	FROM (
		SELECT
			"book_rating"."id" AS "col1",
			"book_rating"."rating" AS "col2"
		FROM "book_rating"
		INNER JOIN "book"
		ON ("book_rating"."book_id" = "book"."id")
		LEFT OUTER JOIN "book_order" ON ("book"."id" = "book_order"."book_id")
		GROUP BY 1, "book"."name"
	) subquery;

Výsledok je hrozný:

┌─────────┐
│  count  │
├─────────┤
│ 1000000 │
└─────────┘
(1 row)

Time: 2982,649 ms (00:02,983)

Pre doplnenie pridávam výstup z explainu:

┌───────────────────────────────────────────────────────────────────────────────┐
│                                  QUERY PLAN                                   │
├───────────────────────────────────────────────────────────────────────────────┤
│ Aggregate (actual rows=1 loops=1)                                             │
│   ->  HashAggregate (actual rows=1000000 loops=1)                             │
│         Group Key: book_rating.id, book.name                                  │
│         Batches: 257  Memory Usage: 9489kB  Disk Usage: 507472kB              │
│         ->  Hash Left Join (actual rows=10005165 loops=1)                     │
│               Hash Cond: (book.id = book_order.book_id)                       │
│               ->  Hash Join (actual rows=1000000 loops=1)                     │
│                     Hash Cond: (book_rating.book_id = book.id)                │
│                     ->  Seq Scan on book_rating (actual rows=1000000 loops=1) │
│                     ->  Hash (actual rows=100000 loops=1)                     │
│                           Buckets: 131072  Batches: 1  Memory Usage: 6493kB   │
│                           ->  Seq Scan on book (actual rows=100000 loops=1)   │
│               ->  Hash (actual rows=1000000 loops=1)                          │
│                     Buckets: 262144  Batches: 8  Memory Usage: 6981kB         │
│                     ->  Seq Scan on book_order (actual rows=1000000 loops=1)  │
│ Planning Time: 0.494 ms                                                       │
│ Execution Time: 3958.023 ms                                                   │
└───────────────────────────────────────────────────────────────────────────────┘

Len pre zaujímavosť, databázový systém musel zapísať zhruba 500 MB dát na disk, aby vykonal korektne agregáciu.

Optimalizácia pomocou subquery

V django ORM je lepšie v takýchto prípadoch použiť subquery. Vďaka tomu bude ORM schopné odstrániť prebytočné parametre a vygeneruje jednoduchý count a zároveň nehrozí problém pri kombinácii viacerých agregačných funkcií keby som chcel napríklad zároveň vybrať priemerné hodnotenie a celkový zisk. Nasledujúci dotaz využíva subquery:

REVENUE_QUERY = Subquery(BookOrder.objects
	.filter(book_id=OuterRef('book_id'))
	.values('book_id')
	.annotate(total=Sum('total_price'))
	.values('total')[:1])
LIST_QUERY = (BookRating.objects
	.annotate(name=F('book__name'), total_revenue=REVENUE_QUERY)
	.values('id', 'rating', 'name', 'total_revenue')
	.order_by('id'))

Vygenerovaný dotaz vyzerá nasledovne:

SELECT
	"book_rating"."id",
	"book_rating"."rating",
	"book"."name" AS "name",
	(SELECT
		SUM(U0."total_price") AS "total"
		FROM "book_order" U0
		WHERE U0."book_id" = ("book_rating"."book_id")
		GROUP BY U0."book_id"
		LIMIT 1
	) AS "total_revenue"
FROM "book_rating"
INNER JOIN "book"
	ON ("book_rating"."book_id" = "book"."id")
ORDER BY "book_rating"."id" ASC
LIMIT 10;

Výsledný plán skutočne potreboval prejsť len 10 riadkov a pri každom prechode robil dodatočnú agregáciu s použitím jednoduchého index scanu:

┌───────────────────────────────────────────────────────────────────────────────────────────────────────────────────┐
│                                                    QUERY PLAN                                                     │
├───────────────────────────────────────────────────────────────────────────────────────────────────────────────────┤
│ Limit (actual rows=10 loops=1)                                                                                    │
│   ->  Nested Loop (actual rows=10 loops=1)                                                                        │
│         ->  Index Scan using book_rating_pkey on book_rating (actual rows=10 loops=1)                             │
│         ->  Memoize (actual rows=1 loops=10)                                                                      │
│               Cache Key: book_rating.book_id                                                                      │
│               Cache Mode: logical                                                                                 │
│               Hits: 0  Misses: 10  Evictions: 0  Overflows: 0  Memory Usage: 2kB                                  │
│               ->  Index Scan using book_pkey on book (actual rows=1 loops=10)                                     │
│                     Index Cond: (id = book_rating.book_id)                                                        │
│         SubPlan 1                                                                                                 │
│           ->  Limit (actual rows=1 loops=10)                                                                      │
│                 ->  GroupAggregate (actual rows=1 loops=10)                                                       │
│                       Group Key: u0.book_id                                                                       │
│                       ->  Index Scan using book_order_book_id_4178112d on book_order u0 (actual rows=10 loops=10) │
│                             Index Cond: (book_id = book_rating.book_id)                                           │
│ Planning Time: 0.414 ms                                                                                           │
│ Execution Time: 0.891 ms                                                                                          │
└───────────────────────────────────────────────────────────────────────────────────────────────────────────────────┘

Spočítanie riadkov vyzerá nasledovne:

SELECT
	COUNT(*) AS "__count"
FROM "book_rating"
INNER JOIN "book"
	ON ("book_rating"."book_id" = "book"."id");

┌───────────────────────────────────────────────────────────────────┐
│                            QUERY PLAN                             │
├───────────────────────────────────────────────────────────────────┤
│ Aggregate (actual rows=1 loops=1)                                 │
│   ->  Hash Join (actual rows=1000000 loops=1)                     │
│         Hash Cond: (book_rating.book_id = book.id)                │
│         ->  Seq Scan on book_rating (actual rows=1000000 loops=1) │
│         ->  Hash (actual rows=100000 loops=1)                     │
│               Buckets: 131072  Batches: 1  Memory Usage: 4931kB   │
│               ->  Seq Scan on book (actual rows=100000 loops=1)   │
│ Planning Time: 0.267 ms                                           │
│ Execution Time: 172.868 ms                                        │
└───────────────────────────────────────────────────────────────────┘

Štatistiky

Ako sa teda zbaviť pomalých dotazov na počet riadkov? Na internete sa často uvádza použitie štatistík. V tomto prípade je získanie približného počtu riadkov pomerne jednoduché.

SELECT reltuples FROM pg_class WHERE relname = 'book_rating';
┌───────────┐
│ reltuples │
├───────────┤
│     1e+06 │
└───────────┘

Problém je, že počet je len približný a týmto spôsobom sa nedá zistiť ani približný počet riadkov pri použití where klauzuly.

Limit je pomalý

Takže zisťovanie počtu riadkov je pomalé a nedá sa s tým prakticky nič urobiť ak má byť zachovaná izolácia. Tak teda zobrazím stránkovač len s tlačidlom ďalej a na celý počet sa vykašlem.

Predstavme si však, že niekto chce skočiť na stránku číslo 5 000. Jednoducho v URL adrese prepíše parameter page. Pozrime sa teraz na dotaz:

SELECT
        "book_rating"."id",
        "book_rating"."rating",
        "book"."name" AS "name",
        SUM("book_order"."total_price") AS "total_revenue"
FROM "book_rating"
INNER JOIN "book"
        ON ("book_rating"."book_id" = "book"."id")
LEFT OUTER JOIN "book_order"
        ON ("book"."id" = "book_order"."book_id")
GROUP BY "book_rating"."id", 3
ORDER BY "book_rating"."id" ASC
LIMIT 10 OFFSET 50000;
┌───────┬────────┬─────────────────┬───────────────┐
│  id   │ rating │      name       │ total_revenue │
├───────┼────────┼─────────────────┼───────────────┤
│ 50001 │      3 │ 7vpPz7iymGQwFHz │        209.00 │
│ 50002 │      4 │ MsjncKx1KD32dRG │        164.00 │
│ 50003 │      2 │ tf4TYvrVXEJr2Zu │        268.00 │
│ 50004 │      3 │ 8ZHr2AVXDJhqIVS │        337.00 │
│ 50005 │      1 │ ScY0nNLn12lc18L │        118.00 │
│ 50006 │      1 │ kdvRYxl2VrOB7Ft │        352.00 │
│ 50007 │      5 │ zkeowCN1d83I17h │        202.00 │
│ 50008 │      1 │ YN9Wb2xR9m3n0FZ │        243.00 │
│ 50009 │      2 │ X07SIjFQ7J4TCB2 │        146.00 │
│ 50010 │      1 │ qDn3zOzAbPGXDN9 │        169.00 │
└───────┴────────┴─────────────────┴───────────────┘
(10 rows)

Time: 996,773 ms

Ajajaj čo sa to stalo?

Tým, že je použitý offset musí databázový systém zase skenovať celú tabuľku, aby sa dostal na konkrétny záznam. Podobne ako v prípade počtu tu neexistuje žiadna skratka na zrýchlenie. Jednoducho offset je pomalý a bude pomalý ak má databázový systém dodržiavať izoláciu transakcií.

Keyset stránkovanie

Čo tak stránkovať pomocou primárneho kľúča?

SELECT
	"book_rating"."id",
	"book_rating"."rating",
	"book"."name" AS "name",
	(SELECT
		SUM(U0."total_price") AS "total"
		FROM "book_order" U0
		WHERE U0."book_id" = ("book_rating"."book_id")
		GROUP BY U0."book_id"
		LIMIT 1
	) AS "total_revenue"
FROM "book_rating"
INNER JOIN "book"
	ON ("book_rating"."book_id" = "book"."id")
WHERE "book_rating"."id" > 50000
ORDER BY "book_rating"."id" ASC
LIMIT 10;

Výsledok je rovnaký, ako v predchádzajúcom príklade, ale čas je diametrálne odlišný:

┌───────┬────────┬─────────────────┬───────────────┐
│  id   │ rating │      name       │ total_revenue │
├───────┼────────┼─────────────────┼───────────────┤
│ 50001 │      3 │ 7vpPz7iymGQwFHz │        209.00 │
│ 50002 │      4 │ MsjncKx1KD32dRG │        164.00 │
│ 50003 │      2 │ tf4TYvrVXEJr2Zu │        268.00 │
│ 50004 │      3 │ 8ZHr2AVXDJhqIVS │        337.00 │
│ 50005 │      1 │ ScY0nNLn12lc18L │        118.00 │
│ 50006 │      1 │ kdvRYxl2VrOB7Ft │        352.00 │
│ 50007 │      5 │ zkeowCN1d83I17h │        202.00 │
│ 50008 │      1 │ YN9Wb2xR9m3n0FZ │        243.00 │
│ 50009 │      2 │ X07SIjFQ7J4TCB2 │        146.00 │
│ 50010 │      1 │ qDn3zOzAbPGXDN9 │        169.00 │
└───────┴────────┴─────────────────┴───────────────┘
(10 rows)

Time: 1,875 ms

V reálnom svete sa nestáva moc často s tým, aby tabuľky mali kľúče perfektne usporiadané bez akejkoľvek medzery. Na druhej strane samotná myšlienka začať s výpisom od určitého prvku nie je vôbec zlá.

Stránkovanie sa dá jednoducho implementovať tým, že namiesto čísla stránky sa zakóduje do URL adresy unikátny kľúč posledného prvku. Týmto spôsobom sa dá stránkovať tabuľka s miliardami riadkov rovnako rýchlo, ako tabuľka s 10 riadkami.

django-universal-paginator

Pôvodný stránkovač djanga nemal možnosť vynechať čísla stránok. Ak bolo napríklad 100 položiek v stránkovaní, vrátených bolo všetkých 100. Preto som si napísal vlastný interne používaný stránkovač - django-simple-paginator.

Medzitým django doplnilo podporu vynechávanie stránok a ja som svoj jednocuhý stránkovač vykastroval o túto funkciu. Zostali už len pomocné funkcie pre generovanie URL adries a šablóny pre django a jinja2.

Premýšľal som čo so svojim stránkovačom. Hodiť ho do archívneho režimu na githube? Premenovať na django-pagination-templates? Nakoniec som sa rozhodol implementovať keyset stránkovanie (nazývané niekedy aj cursor pagination). Preto som mu zmenil názov zo simple na universal, pretože podporuje obe metódy stránkovania - bežné a keyset.

Prečo ďalší stránkovač

Existuje množstvo podobných stránkovačov. Všetky sú však implementované zle. Moje stránkovanie má niektoré zásadné vlastnosti, ktoré inde chýbajú:

• je korektný (dokáže správne zistiť, či existuje nasledujúca, alebo predchádzajúca stránka)
• používa jediný select
• nie je potrebné explicitne definovať order (je odvodený z query)
• podporuje jinja2 šablóny
• má utility na automatické injektovanie stránok do URL
• podporuje obe metódy stránkovania bez modifikácie šablón

Zistenie prítomnosti nasledujúcej / predchádzajúcej stránky

Ostatné stránkovače používajú 2 rôzne prístupy. Buď nevedia, či sú na prvej / poslednej stránke a vrátia stále stránkovanie aj keď nasledujúca stránka bude prázdna, alebo okrem hlavného dotazu robia 2 dodatočné kvôli existencii nasledujúceho a predchádzajúceho riadku.

Môj prístup je odlišný. Na nasledujúcom obrázku je ukážka stránkovania s 5 stránkami. Ja robím select, ktorý začína riadkom z predchádzajúcej stránky vďaka čomu viem, že existuje predchádzajúca stránka a pokračujem až po riadok na nasledujúcej stránke. V iterátore odstránim prvý a posledný riadok, čím zároveň zistím existenciu nasledujúcej a predchádzajúcej strany.

Obrázok 2: Stránkovanie

Kódovanie kľúčov do URL adresy

Ako malú implementačnú pikošku ešte spomeniem kódovanie kľúčov. Kľúče sú kódované v binárnom formáte. Kóduje sa zoznam kľúčov (keďže kľúč môže byť zložený z viacerých zložiek). Každý argument začína 1-bytovou hlavičkou nasledovanou obsahom.

Hodnoty null, true a false majú vlastný typ a nulovú veľkosť. Preto sa kódujú do 1 bytu.

Typ text je trochu špeciálny, pretože jeho definícia zaberá 6 bitov z 8-bitovej hlavičky. Texty do dĺžky 64 bytov sa preto zakódujú do sekvencie dlhšej o jediný byte. Dlhšie texty do 320 bytov sa zakódujú do dĺžky textu + 2 byty. Nakoniec texty do 65856 B vyžadujú 3 dodatočné byty (16-bitová dĺžka + 1-bytová hlavička).

Celé čísla sú zakódované do 1-bytovej hlavičky nasledovanej 1, 2, 4, 8, alebo variabilnou dĺžkou ak je číslo dlhšie než 64 bytov. Čísla s pohyblivou desatinnou čiarkou sa kódujú do 9 bytov.

Čas sa kóduje do 3 - 12 bytov podľa typu, presnosti a časovej zóny.

Celý binárny reťazec sa zabalí do upraveného base64 a doplní sa príznakom smeru.

Príklad kódovaného kľúča: nBgo (podľa ID), bCABL (veľké ID, spätný chod), nHAAAADF6GpIgBgc (dátum, čas, id).

Môj balík je zverejnený v repozitári pypi.

       

Komentáře

[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).