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

14 minút

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 po­kus­nú da­ta­bá­zu bu­dem po­u­ží­vať fik­tív­nu da­ta­bá­zu kníh. Ta­buľ­ka book ob­sa­hu­je ID a ná­zov kni­hy. V ta­buľ­ke book_rating sú hod­no­te­nia kníh (hod­no­te­nie je hod­no­ta od 1 do 5). Ta­buľ­ka book_order ob­sa­hu­je fik­tív­ne ná­ku­py kníh (total_price pre­to­že je­den ná­kup mô­že za­hŕňať viac ku­sov).

Databázové modely
Ob­rá­zok 1: Da­ta­bá­zo­vé mo­de­ly

SQL pre vy­tvo­re­nie da­ta­bá­zy vy­ze­rá na­sle­dov­ne:

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 ge­ne­ro­va­nie dát je s sú­bo­re lo­ad_da­ta.sql.

Výber hodnotení kníh

Na­sle­du­jú­ci do­taz vy­be­rie 10 hod­no­te­ní 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

Za­tiaľ všet­ko vy­ze­rá v po­riad­ku. Pre is­to­tu sa po­zri­me na qu­e­ry 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                                                        |
+---------------------------------------------------------------------------------+

Do­taz vy­ko­ná­va rých­ly in­dex sken ob­me­dze­ný na 10 riad­kov. Sa­mot­ný čas vy­ko­ná­va­nie 0.081 ms je veľ­mi dob­rá hod­no­ta.

Count je pomalý

Ty­pic­ké strán­ko­va­nie po­tre­bu­je naj­skôr skon­tro­lo­vať po­čet riad­kov v ta­buľ­ke. Po pri­da­ní štan­dard­né­ho strán­ko­va­nia v djan­gu sa zra­zu we­bo­vá ap­li­ká­cia spo­ma­lí. Zá­ro­veň me­dzi vy­ko­na­ný­mi do­taz­mi pri­bu­dol no­vý do­taz:

SELECT COUNT(*) FROM book_rating;
+---------+
|  count  |
+---------+
| 1000000 |
+---------+
(1 row)

Time: 34,262 ms

Že­by bo­li sta­ré šta­tis­ti­ky? Tak skús­me vy­ge­ne­ro­vať no­vé a po­tom zo­pa­ku­je­me rov­na­ký do­taz:

ANALYZE
Time: 183,467 ms

SELECT COUNT(*) FROM book_rating;
+---------+
|  count  |
+---------+
| 1000000 |
+---------+
(1 row)

Time: 35,655 ms

Zdá sa, že vy­ge­ne­ro­va­nie šta­tis­tík ne­má žia­den vplyv na po­čí­ta­nie riad­kov. Te­raz sa po­zri­me na vý­stup ex­plain:

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­čí­ta­nie riad­kov v ta­buľ­ke mu­sí da­ta­bá­zo­vý sys­tém pre­ske­no­vať (pre­čí­tať) kom­plet­ne ce­lú ta­buľ­ku. Väč­ši­na či­ta­te­ľov, kto­rá do hĺb­ky ne­štu­do­va­la da­ta­bá­zo­vé sys­té­my si te­raz asi ho­vo­rí, pre­čo da­ta­bá­zo­vý sys­tém ne­pou­ži­je in­dex? Však ulo­žiť po­čet riad­kov ako me­ta­dá­ta ta­buľ­ky ne­mô­že byť pred­sa nič ťaž­ké.

Len­že ono to nie je ani ťaž­ké, ono to je prak­tic­ky ne­mož­né. Pre vy­svet­le­nie je po­treb­né hl­b­šie po­znať fun­go­va­nie da­ta­bá­zo­vé­ho sys­té­mu.

We need to go deeper

Ako funguje databázový systém

Prog­ra­má­to­ri si čas­to pred­sta­vu­jú da­ta­bá­zo­vý sys­tém ako cen­tra­li­zo­va­ný sklad dát, kto­rý má je­di­ný jed­no­znač­ne de­fi­no­va­ný stav. Ta­ký zjed­no­du­še­ný po­hľad pla­tí na nie­kto­ré No-SQL da­ta­bá­zo­vé sys­té­my.

Pre pl­no­hod­not­né da­ta­bá­zo­vé sys­té­my ACID (ato­mi­ci­ty, con­sis­ten­cy, iso­la­ti­on, du­ra­bi­li­ty) to však ne­pla­tí. V ta­kom da­ta­bá­zo­vom sys­té­me mô­že pre­bie­hať jed­na trans­ak­cia, kto­rá čí­ta ta­buľ­ku za­tiaľ čo v inej trans­ak­cii sa na­hra­li no­vé dá­ta (pri­čom eš­te nie je com­mit­nu­tá), v ďal­šej trans­ak­cii sa nie­kto­ré riad­ky zma­za­li a v ďal­šej sa nie­kto­ré riad­ky zme­ni­li. Vďa­ka vlast­nos­ti zva­nej izo­lá­cia mu­sí pr­vá trans­ak­cia vi­dieť ce­lú da­ta­bá­zu v sta­ve, v kto­rom bo­la na za­čiat­ku trans­ak­cie bez ohľa­du na to, čo sa de­je v ďal­ších trans­ak­ciách.

Da­ta­bá­zo­vý sys­tém po­sky­tu­je te­da kaž­dej trans­ak­cii vlast­ný po­hľad na dá­ta v ur­či­tom ča­se, pri­čom jed­not­li­vé trans­ak­cie ne­smú byť ovplyv­ne­né iný­mi trans­ak­ci­ami. Aby bo­lo mož­no nie­čo ta­ké, mu­sí da­ta­bá­zo­vý sys­tém ukla­dať rôz­ne ver­zie to­ho is­té­ho riad­ku a po­ne­chá­vať zma­za­né riad­ky kým sú prí­stup­né z nie­kto­rej trans­ak­cie.

Post­gre­SQL im­ple­men­tu­je izo­lá­ciu po­mo­cou do­da­toč­ných me­ta­dát pri riad­koch ta­buľ­ky. Riad­ky ma­jú in­for­má­ciu o mi­ni­mál­nom čís­le trans­ak­cia, od ke­dy je vi­di­teľ­ná a o ma­xi­mál­nom čís­le trans­ak­cie (ak bo­la vy­ma­za­ná). Zme­na dát v da­ta­bá­ze sa tak im­ple­men­tu­je pri­dá­va­ním no­vých riad­kov do WAL (Wri­te-ahe­ad log­ging) sú­bo­rov. Sta­ré ver­zie sa mô­žu od­strá­niť až vte­dy, keď nie sú do­stup­né zo žiad­nej trans­ak­cie.

Ako te­da spo­čí­tať riad­ky v ta­buľ­ke? Jed­no­du­cho, sta­čí ve­dieť čís­lo ak­tu­ál­nej trans­ak­cie a po­stup­ne ske­no­vať ce­lú ta­buľ­ku a ap­li­ko­vať pra­vid­lá vi­di­teľ­nos­ti pre kaž­dý ria­dok. Pres­ne to Post­gre­SQL ro­bí.

Čas spo­čí­ta­nia riad­kov v ta­buľ­ke má kvô­li pod­mien­ke izo­lá­cie li­ne­ár­nu zá­vis­losť od po­čtu riad­kov.

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

Prí­klad tro­chu skom­pli­ku­jem tým, že v zo­zna­me bu­dem chcieť zo­bra­ziť ná­zov kni­hy a trž­by za pre­daj. Do­taz v Djan­go ORM vy­ze­rá na­sle­dov­ne:

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

Vý­sled­ný do­taz vy­ze­rá na­sle­dov­ne:

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;

Sa­mot­ný vý­ber riad­kov je cel­kom uspo­ko­ji­vý.

+----+--------+-----------------+---------------+
| 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

Na­priek to­mu sa na­čí­ta­nie we­bu spo­ma­li­lo na 3 s. Čo sa sta­lo?

Djan­go roz­poz­na­lo, že do­taz po­u­ží­va ag­re­gač­né fun­kcie. Aby bo­lo mož­né spo­ľah­li­vo zis­tiť po­čet riad­kov, mu­sí sa do­taz spus­tiť ako su­bqu­e­ry (ok, v tom­to prí­pa­de by sta­čil jed­no­du­chý count, ale lo­gi­ka za tým je po­mer­ne zlo­ži­tá, tak­že sa vo­lí bez­peč­ná aj keď po­ma­lá me­tó­da). Vy­ge­ne­ro­va­ný do­taz vy­ze­rá tak­to:

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ý­sle­dok je hroz­ný:

+---------+
|  count  |
+---------+
| 1000000 |
+---------+
(1 row)

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

Pre do­pl­ne­nie pri­dá­vam vý­stup z ex­plai­nu:

+-------------------------------------------------------------------------------+
|                                  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 zau­jí­ma­vosť, da­ta­bá­zo­vý sys­tém mu­sel za­pí­sať zhru­ba 500 MB dát na disk, aby vy­ko­nal ko­rekt­ne ag­re­gá­ciu.

Optimalizácia pomocou subquery

V djan­go ORM je lep­šie v ta­kých­to prí­pa­doch po­u­žiť su­bqu­e­ry. Vďa­ka to­mu bu­de ORM schop­né od­strá­niť pre­by­toč­né pa­ra­met­re a vy­ge­ne­ru­je jed­no­du­chý count a zá­ro­veň ne­hro­zí prob­lém pri kom­bi­ná­cii via­ce­rých ag­re­gač­ných fun­kcií ke­by som chcel na­prí­klad zá­ro­veň vy­brať prie­mer­né hod­no­te­nie a cel­ko­vý zisk. Na­sle­du­jú­ci do­taz vy­uží­va su­bqu­e­ry:

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'))

Vy­ge­ne­ro­va­ný do­taz vy­ze­rá na­sle­dov­ne:

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ý­sled­ný plán sku­toč­ne po­tre­bo­val prejsť len 10 riad­kov a pri kaž­dom pre­cho­de ro­bil do­da­toč­nú ag­re­gá­ciu s po­u­ži­tím jed­no­du­ché­ho in­dex sca­nu:

+-------------------------------------------------------------------------------------------------------------------+
|                                                    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­čí­ta­nie riad­kov vy­ze­rá na­sle­dov­ne:

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 te­da zba­viť po­ma­lých do­ta­zov na po­čet riad­kov? Na in­ter­ne­te sa čas­to uvá­dza po­u­ži­tie šta­tis­tík. V tom­to prí­pa­de je zís­ka­nie pri­bliž­né­ho po­čtu riad­kov po­mer­ne jed­no­du­ché.

SELECT reltuples FROM pg_class WHERE relname = 'book_rating';
+-----------+
| reltuples |
+-----------+
|     1e+06 |
+-----------+

Prob­lém je, že po­čet je len pri­bliž­ný a tým­to spô­so­bom sa ne­dá zis­tiť ani pri­bliž­ný po­čet riad­kov pri po­u­ži­tí whe­re klau­zu­ly.

Limit je pomalý

Tak­že zis­ťo­va­nie po­čtu riad­kov je po­ma­lé a ne­dá sa s tým prak­tic­ky nič uro­biť ak má byť za­cho­va­ná izo­lá­cia. Tak te­da zo­bra­zím strán­ko­vač len s tla­čid­lom ďa­lej a na ce­lý po­čet sa vy­kaš­lem.

Pred­stav­me si však, že nie­kto chce sko­čiť na strán­ku čís­lo 5 000. Jed­no­du­cho v URL ad­re­se pre­pí­še pa­ra­me­ter page. Po­zri­me sa te­raz na do­taz:

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

Aja­jaj čo sa to sta­lo?

Tým, že je po­u­ži­tý off­set mu­sí da­ta­bá­zo­vý sys­tém za­se ske­no­vať ce­lú ta­buľ­ku, aby sa do­stal na kon­krét­ny zá­znam. Po­dob­ne ako v prí­pa­de po­čtu tu ne­exis­tu­je žiad­na skrat­ka na zrých­le­nie. Jed­no­du­cho off­set je po­ma­lý a bu­de po­ma­lý ak má da­ta­bá­zo­vý sys­tém do­dr­žia­vať izo­lá­ciu trans­ak­cií.

Keyset stránkovanie

Čo tak strán­ko­vať po­mo­cou pri­már­ne­ho 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ý­sle­dok je rov­na­ký, ako v pred­chá­dza­jú­com prí­kla­de, ale čas je dia­met­rál­ne od­liš­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­ál­nom sve­te sa ne­stá­va moc čas­to s tým, aby ta­buľ­ky ma­li kľú­če per­fekt­ne uspo­ria­da­né bez akej­koľ­vek me­dze­ry. Na dru­hej stra­ne sa­mot­ná myš­lien­ka za­čať s vý­pi­som od ur­či­té­ho prv­ku nie je vô­bec zlá.

Strán­ko­va­nie sa dá jed­no­du­cho im­ple­men­to­vať tým, že na­mies­to čís­la strán­ky sa za­kó­du­je do URL ad­re­sy uni­kát­ny kľúč po­sled­né­ho prv­ku. Tým­to spô­so­bom sa dá strán­ko­vať ta­buľ­ka s mi­liar­da­mi riad­kov rov­na­ko rých­lo, ako ta­buľ­ka s 10 riad­ka­mi.

django-universal-paginator

Pô­vod­ný strán­ko­vač djan­ga ne­mal mož­nosť vy­ne­chať čís­la strá­nok. Ak bo­lo na­prí­klad 100 po­lo­žiek v strán­ko­va­ní, vrá­te­ných bo­lo všet­kých 100. Pre­to som si na­pí­sal vlast­ný in­ter­ne po­u­ží­va­ný strán­ko­vač - django-simple-paginator.

Me­dzi­tým djan­go do­pl­ni­lo pod­po­ru vy­ne­chá­va­nie strá­nok a ja som svoj jed­no­cu­hý strán­ko­vač vy­kas­tro­val o tú­to fun­kciu. Zo­sta­li už len po­moc­né fun­kcie pre ge­ne­ro­va­nie URL ad­ries a šab­ló­ny pre djan­go a jin­ja2.

Pre­mýš­ľal som čo so svo­jim strán­ko­va­čom. Ho­diť ho do ar­chív­ne­ho re­ži­mu na git­hu­be? Pre­me­no­vať na djan­go-pa­gi­na­ti­on-tem­pla­tes? Na­ko­niec som sa roz­ho­dol im­ple­men­to­vať ke­y­set strán­ko­va­nie (na­zý­va­né nie­ke­dy aj cur­sor pa­gi­na­ti­on). Pre­to som mu zme­nil ná­zov zo sim­ple na uni­ver­sal, pre­to­že pod­po­ru­je obe me­tó­dy strán­ko­va­nia - bež­né a ke­y­set.

Prečo ďalší stránkovač

Exis­tu­je množ­stvo po­dob­ných strán­ko­va­čov. Všet­ky sú však im­ple­men­to­va­né zle. Mo­je strán­ko­va­nie má nie­kto­ré zá­sad­né vlast­nos­ti, kto­ré in­de chý­ba­jú:

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

Os­tat­né strán­ko­va­če po­u­ží­va­jú 2 rôz­ne prí­stu­py. Buď ne­ve­dia, či sú na pr­vej / po­sled­nej strán­ke a vrá­tia stá­le strán­ko­va­nie aj keď na­sle­du­jú­ca strán­ka bu­de prázd­na, ale­bo ok­rem hlav­né­ho do­ta­zu ro­bia 2 do­da­toč­né kvô­li exis­ten­cii na­sle­du­jú­ce­ho a pred­chá­dza­jú­ce­ho riad­ku.

Môj prí­stup je od­liš­ný. Na na­sle­du­jú­com ob­ráz­ku je ukáž­ka strán­ko­va­nia s 5 strán­ka­mi. Ja ro­bím se­lect, kto­rý za­čí­na riad­kom z pred­chá­dza­jú­cej strán­ky vďa­ka čo­mu viem, že exis­tu­je pred­chá­dza­jú­ca strán­ka a po­kra­ču­jem až po ria­dok na na­sle­du­jú­cej strán­ke. V ite­rá­to­re od­strá­nim pr­vý a po­sled­ný ria­dok, čím zá­ro­veň zis­tím exis­ten­ciu na­sle­du­jú­cej a pred­chá­dza­jú­cej stra­ny.

Stránkovanie
Ob­rá­zok 2: Strán­ko­va­nie

Kódovanie kľúčov do URL adresy

Ako ma­lú im­ple­men­tač­nú pi­koš­ku eš­te spo­me­niem kó­do­va­nie kľú­čov. Kľú­če sú kó­do­va­né v bi­nár­nom for­má­te. Kó­du­je sa zo­znam kľú­čov (keď­že kľúč mô­že byť zlo­že­ný z via­ce­rých zlo­žiek). Kaž­dý ar­gu­ment za­čí­na 1-by­to­vou hla­vič­kou na­sle­do­va­nou ob­sa­hom.

Hod­no­ty null, true a fal­se ma­jú vlast­ný typ a nu­lo­vú veľ­kosť. Pre­to sa kó­du­jú do 1 by­tu.

Typ text je tro­chu špe­ciál­ny, pre­to­že je­ho de­fi­ní­cia za­be­rá 6 bi­tov z 8-bi­to­vej hla­vič­ky. Tex­ty do dĺž­ky 64 by­tov sa pre­to za­kó­du­jú do sek­ven­cie dl­h­šej o je­di­ný by­te. Dl­h­šie tex­ty do 320 by­tov sa za­kó­du­jú do dĺž­ky tex­tu + 2 by­ty. Na­ko­niec tex­ty do 65856 B vy­ža­du­jú 3 do­da­toč­né by­ty (16-bi­to­vá dĺž­ka + 1-by­to­vá hla­vič­ka).

Ce­lé čís­la sú za­kó­do­va­né do 1-by­to­vej hla­vič­ky na­sle­do­va­nej 1, 2, 4, 8, ale­bo va­ria­bil­nou dĺž­kou ak je čís­lo dl­h­šie než 64 by­tov. Čís­la s po­hyb­li­vou de­sa­tin­nou čiar­kou sa kó­du­jú do 9 by­tov.

Čas sa kó­du­je do 3 - 12 by­tov pod­ľa ty­pu, pres­nos­ti a ča­so­vej zó­ny.

Ce­lý bi­nár­ny re­ťa­zec sa za­ba­lí do upra­ve­né­ho ba­se­64 a do­pl­ní sa prí­zna­kom sme­ru.

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

Môj ba­lík je zve­rej­ne­ný v re­po­zi­tá­ri py­pi.