Postgres - 各種分頁的方式介紹

發表於 更新於 分類於 Disqus： 文章字數： 8.1k 所需閱讀時間 ≈ 15 分鐘

今天來講講在設計 API 常見的需求：分頁，為什麼要進行分頁？不外乎就是不希望向資料庫一次拿大量的資料出來，造成資料庫的負擔，且前端頁面也不應該一次顯示過多的大量資料，需要進行分頁來提升使用者體驗。

那麼在 Postgres 要實現分頁的需求其實有很多種方法，每個方法使用情境也都不一樣，其 performance 也會有差別的，這篇文章應該是我好久以前就寫好的草稿，但一直沒時間好好整理筆記發在 blog，所以就一直擱置了，因為分頁的需求很常見，所以是應該好好記下來才行。

在前端還是後端做分頁

首先分頁可以先區分在 Client Side 還是 Server Side 去做，對於少量的資料，其實在 Client Side 做是沒問題的，也可以減少 HTTP Calls，前端也能夠事先知道資料的總數量，如果有總數量就可以做到顯示目前有幾頁，且當下的頁數是第幾頁。

如果是 Server Side 這邊要做分頁的話，不用再一次拉大量的資料，但是相對的會增加 HTTP Calls，且根據實現分頁的方法，有些方法是無法讓前端事先知道總數量會是多少，當然也不好做出顯示目前有幾頁，且當下的頁數是第幾頁。

事實上，現在大多數的新網站採用的分頁方式，在前端上來看不再是傳統那樣會看到有幾頁，目前在哪個頁碼等資訊，而是採用滾輪往下滾，滾到一定的位置就會自動往下加載更多的資料這種方式。而且如果是資料量越龐大的情況越有可能前端看到的分頁方式是自動往下加載的方式，為什麼呢？看完下面的各種分頁介紹就可以明白了。

先談談後端做分頁常見問題

在不論有哪些分頁的方式，如果做分頁通常會以下的問題需要考量：

  1. 分頁的資料會有順序性，不會想要下次再看的時候資料順序跟上次不一樣
    • 如果想要有順序性，下 Query 就一定要有 ORDER BY
  2. 分頁資料不想要看到重複的
    • 如果不想看到資料有重複的，就必須 ORDER BY 的欄位可以保證資料是有順序性且新加入的資料不會因為這個排序突然排在前面的位置
    • 要注意 ORDER BY 的欄位本身的資料是否會有重複的問題產生
  3. 分頁資料會有遺漏的情況發生
    • 如果在顯示分頁資料的時候，此時有新加入的資料會因為這個排序而突然排在前面的位置的話，有可能新加入的資料在這次的分頁到最後你都是無法看到的，因為這個新資料已經排在你這次拉的分頁的前面了。只有當你從前面的分頁開始重拉才能看到。
    • 如果在顯示分頁資料的時候，此時有人新增 / 刪除了資料，此時你使用 OFFSET 去計算目前是拉到第幾個資料的話，該 OFFSET 的數字會不準確，因此下次拉的時候有可能會少看到後面的資料，都是有可能發生的。

總結以上三個問題，如果你本身資料性質就會造成順序性或是重複的問題，那基本上是很難避免的，通常能做的就是也許前端去做去重複，或是後端多做一層 cache，讓前端拿的 cache 的資料，但如果你的 cache 資料會是變動的，那麼還是會出現以上的問題。

因此下面所介紹的分頁方式，也是要根據使用情境及它的優缺點去恆量該用哪種的。再講下面的分頁方式時，先建立好我們的資料情境：

1
2
3
4
5
CREATE TABLE posts (
  id INTEGER,
  uid TEXT,
  weight INTEGER
);

假設我們有 posts Table，id 是 integer，是方便示範 auto increment 的操作，uid 則是 TEXT 形態來代替 UUID，這樣比較好示範，兩者都是會拿來當作 pk 的欄位，weight 則是特別欄位，用來標示權重的意思，因為需求常常會是需要將某些文章的排序特別的放在前面，因此會透過 weight 去控制排序的順序，在這邊的定義是，weight 越小則排序越前面，而 weight 的值是可以重複的，所以可能會有多篇文章的權重是一樣的。

OFFSET + LIMIT 的實現

OFFSET + LIMIT 應該是大家最熟悉的實現分頁方式，其優缺點如下：

優點

  1. Query 簡單好寫，也能實現總數量或是顯示在第幾頁的效果

缺點

  1. 無法解決資料重複 / 遺失的問題，因為 OFFSET 的數字會根據資料的新增 / 刪除而導致不準確的問題發生

    • 假設使用者從第 n 頁移動到 n+1，同時一個新資料被插入到第 n 頁。這將導致重複資料的產生，因為第 n 頁的之前最後資料被推入第 n+1 頁，同時你也無法看到新資料。或者是當使用者移動到頁面 n+1 時從頁面 n 中刪除的元素。第 n+1 頁的之前的第一個資料將被移動到第 n 頁，因此看不到原本應該在第 n + 1 頁面的第一個資料。

  2. OFFSET 的效率差，相當於先撈了 OFFSET + LIMIT 的 row 出來後，再把 OFFSET 的 row 丟掉

    Ref：https://www.postgresql.org/docs/current/queries-limit.html

    The rows skipped by an OFFSET clause still have to be computed inside the server; therefore a large OFFSET might be inefficient.

上面提到第二種缺點是無法避免的，但是第一個缺點是可以避免的，必須 ORDER BY 的欄位可以保證資料是有順序性，且資料本身是不會重複的，那麼最簡單的方式就是 ORDER BY PRIMARY KEY。在現今的應用上，非 natural PK 無非是採用 AUTO INCREMENT OR UUID。

  • ORDER BY id (auto increment)：可以保證下一次加入的資料在不人為干擾下，新資料的 id 一定是遞增的，那 order by id + offset 不會有資料重複的問題發生
  • ORDER BY uuid：UUID 本身的性質無法保證是遞增的，所以下一次加入的資料會無法確定會排在哪個位置，所以 order by id + offset 會有資料重複的問題

要注意的是上面 OEDER BY 解法只能解決資料重複的問題，資料遺失的問題是仍舊無法解決的。

範例

講完上面的優缺點，那麼來一一看範例會更清楚。

order by uuid

1
2
3
4
5
6
7
INSERT INTO posts (id, uid, weight) VALUES (1, 'bbb', 1), (2, 'ccc', 2), (3, 'ddd', 3);
SELECT * FROM posts ORDER BY id LIMIT 2;
-- 這時候 OFFSET = 2
-- 接著來了個新資料
INSERT INTO posts (id, uid, weight) VALUES (4, 'aaa', 1);
-- 'ccc' 的資料又重複出現了
SELECT * FROM posts ORDER BY id LIMIT 2;

如果 order by 的欄位會重複

如果想要 ORDER BY weight，因為 weight 的值是可以重複的：

1
2
3
4
5
6
INSERT INTO posts (id, uid, weight) VALUES (1, 'bbb', 1), (2, 'ccc', 2), (3, 'ddd', 3);
SELECT * FROM posts ORDER BY weight LIMIT 2;
-- 此時 OFFSET = 2
INSERT INTO posts (id, uid, weight) VALUES (4, 'aaa', 1);
-- 'ccc' 的資料又重複出現了
SELECT * FROM posts ORDER BY weight OFFSET 2 LIMIT 2;

在這種情況下，又想要資料不重複怎麼辦呢？可以多加上一個排序的欄位，來解決重複問題。

透過使用 order by weight, id：使用 id 是因為 id 是 PK 的特性，本身不會有資料重複的問題產生，當 weight 相等的時候就用 id 去決定一致的順序性。

當這時要考慮的問題是 id 是 auto increment 還是 uuid？

  • 如果是 auto increment：在資料維持一樣的情況下，如果資料是 (id, weight) => (1, 2), (2, 2)，這樣可以透過 offset 正常拿出來資料且不會有重複問題，因為 id 一定是遞增的。因為如果新增 (3, 2) 的話，order by 的結果，(3, 2) 的新資料依然會在 (1, 2), (2, 2) 之後。
  • 如果是 uuid：(id, weight) => (‘bbb’, 1), (‘ccc’, 1) 可以透過 offset 正常拿出來不會有重複的問題，如果新增 (‘ddd’, 1) order by 的結果，(‘ddd’, 1) 的新資料依然後會在 (‘bbb’, 1), (‘ccc’, 1) 之後。但無法保證下一次新增的一定是遞增的 uuid，因此排序過後可能會排在前面，例如新增 (‘aaa’, 1) 就可能會拿到重複的資料。

Seek 的實現

Seek 的方式通常又被稱為 Cursor 的方式，但我這邊用 Seek 去形容它，是因為 Postgres 有提供另一種 Cursor 行為，這個我們後面會提到。

Seek 的方式其精髓就是透過比較大小的方式來快速定位，且可以善用到 index 加速查詢的效果。

優點

  1. Seek 的方式可以解決 OFFSET + LIMIT 上面遇到的問題
  2. 通常會需要寫成 subquery 的方式，多個欄位 seek 的話可以用 row compare 的方式來簡化寫 query 的複雜度，而速度上比 offset + limit 快很多，原因就在於 subquery 這段可以搭配 index 加速
  3. 可以解決資料重複的問題，但是關鍵還是在於要怎麼下 order by 及 seek 的方式

缺點

  1. 無法提供總數量及頁碼的資訊
  2. 要能提供的排序的欄位，通常都要上 index，如果給前端過多排序的欄位，那麼 index 就會需要加上不少。

範例

order by id (auto increment)

可以保證下一次加入的資料在不人為干擾下，新資料的 id 一定是遞增的，還不需要額外多下 index 去加速，因為 pk 本身就是 unique index。

1
2
3
4
INSERT INTO posts (id, weight) VALUES (1, 1), (2, 2), (3, 3);
SELECT * FROM posts ORDER BY id LIMIT 1
-- 這時候想拉下一次的數量
SELECT * FROM posts WHERE id > (SELECT id FROM posts WHERE id = 1) ORDER BY id LIMIT 3;
  1. 因為 pk 本身就是 index，所以 subquery 這段速度快
  2. 此外 order by id，又能吃到 index 早就排序好的效果，省了 sort 的時間，當然資料量一大如果沒有 LIMIT 的幫助，就無法吃到 index 的效果。所以才需要 LIMIT 做分頁且善用 index 的功能。
  3. 這樣的寫法速度上比 offset 好上太多，且 order by id 這樣撈取也保證不會撈到重複的資料

order by uuid

uuid 無法保證下一次加入的 uuid 一定是遞增的

1
2
INSERT INTO posts (uid, weight) VALUES ('aaa', 1), ('bbb', 2), ('ccc', 3);
SELECT * FROM posts WHERE uid > (SELECT uid FROM posts WHERE uid = 'bbb') ORDER BY uid LIMIT 2;

假設上面的 ‘aaa’, ‘bbb’, ‘ccc’ 是 UUID，因為這樣方便示範，可以看到這樣的效果：

  1. 速度也是很快，因為也能吃到 index
  2. 缺點就在於無法保證新加入的資料一定會在之後的分頁出現，因為有可能 order by uid 之後會出現在前面，但是即便出現在前面，在撈取的時候也不會遇到重複資料的問題，原因在於這邊有加 where uid > 的條件，只有當 uid 是大於上次撈的最後的 uid 才會出現，因此如果新加入的資料是排序在前面的 uid，就也不會在這 round 拿到。

如果 order by 的 column 會重複呢

1
2
3
4
5
INSERT INTO posts (uid, weight) VALUES ('aaa', 1), ('bbb', 2), ('ccc', 2);
SELECT * FROM posts ORDER BY weight LIMIT 2;
-- 這時候顯示 (aaa, 1), (bbb, 2) 兩筆資料
SELECT * FROM posts WHERE weight > (SELECT weight FROM posts WHERE id = 'bbb') ORDER BY weight LIMIT 1
-- 沒東西了，'ccc' 的資料拿不出來

所以缺點很明顯：

  1. 靜態重複的資料無法拿出來，如果此時也有一個新的 (‘ddd’, 2) 加入了，也一樣無法拿出來

  2. 要解決這個問題，就必須引入一個不會有重複值得欄位，來做第二順位的排序，最通用的方式是拿 id 來做排序，因為 pk 的特性一定不會重複，例如：

    1
    2
    3
    4
    5
    6
    7
    INSERT INTO posts (id, weight) VALUES (1, 1), (2, 2), (3, 2);
    -- 想要加速查詢並省下 sort 的時間，就必須為這兩個欄位建立 index
    CREATE INDEX posts_weight_id_idx ON posts USING btree (weight, id);
    SELECT * FROM posts ORDER BY weight, id LIMIT 2
    -- 顯示 (1, 1), (2, 2)
    SELECT * FROM posts WHERE weight > (SELECT weight FROM posts WHERE id = 2) OR (weight = (SELECT weight FROM posts WHERE id = 2) AND id > 2) ORDER BY weight, id LIMIT 1
    -- 顯示 (3, 2)

    可以發現這樣的查詢就能解決資料重複的問題但是寫起來很複雜，而這樣 subquery 的寫法就可以用 row compare 的方式簡化：

    1
    SELECT * FROM posts WHERE (weight, id) > (SELECT weight, id FROM posts WHERE id = 2) LIMIT 1

    這時如果加入了一個重複資料：(4, 2)，下一 round 一定也可以拿到的。但是如果加入的是 (1, 2) 下一 round 當然是無法拿到的，只有當重新拉第一 round 才會拿到新資料。

總結這邊的 seek index 要怎麼設計呢？

  1. 以上面的情境至少要有 (weight, id) 及 (id) 這兩個 index 才能加速，因為第一個 index 是為了省掉 sort 的時間，第二個 index 是為了 subquery 的加速

  2. seek 的方式還有一點需要考慮，weight 這個欄位如果隨時都會被更動的話：

    1
    2
    3
    4
    -- 此時('bbb', 2) => ('bbb', 0)
    UPDATE posts SET weight = 0 WHERE id = 'bbb'
    SELECT * FROM posts WHERE (weight, id) > (SELECT weight, id FROM posts WHERE id = 'bbb') ORDER BY weight, id LIMIT 2
    -- 這種情況下 ('ccc', 1) 會重複拿到

    所以如果 order by 的欄位隨時都有可能被更動的話，可以考慮寫死 seek value：

    1
    2
    3
    UPDATE campaigns SET weight = 2 WHERE id = 'bbb'
    SELECT * FROM campaigns WHERE (weight, id) > (2, 'bbb') ORDER BY weight, id LIMIT 1
    -- 這樣是可以確保這個分頁流程一定是按照上次分頁的順序往下跑，也可以避免排序是在後面的情況： ('bbb', 3)，這樣之間的資料不會 loss 掉沒拿出來，還可以省掉 subQuery 的時間

Postgres 13 WITH TIES 用法

WITH TIES 這功能是基於 FETCH 語法的，因為其實常用的 LIMIT 並不是 SQL 標準，FETCH 才是 SQL 標準但是也是相當於 LIMIT 的用法。

其語法如下：

1
SELECT * FROM posts ORDER BY id OFFSET start { ROW | ROWS } FETCH { FIRST | NEXT } [ count ] { ROW | ROWS } ONLY /

來看範例：

範例

1
2
3
4
5
6
CREATE TABLE scores(id TEXT, score integer);
INSERT INTO scores(id, score) VALUES('a','100'),('b','90'),('e','80'),('d','80'),('c','80');

SELECT * FROM scores ORDER BY score DESC FETCH FIRST 3 ROWS WITH TIES;
-- 雖然這邊寫 FETCH 3 ROWS，但是 WITH TIES 的特型會把 order by 欄位相同的值的資料一并都拿出來
-- 因此這邊等於直接拿出五筆資料出來

另外，WITH TIES 的語法一定要搭配 ORDER BY，且 ORDER BY 多個欄位要寫成 subquery 的方式才可以，不然會出現語法錯誤：

1
2
3
4
5
6
7
SELECT * FROM (
  SELECT * FROM scores
  ORDER BY score DESC
  OFFSET 0
  FETCH FIRST 3 ROWS WITH TIES
) s 
ORDER BY score DESC, id;

所以寫起來其實有點麻煩，另外 WITH TIES 也是可以結合 Seek 的方式：

1
2
SELECT * FROM scores ORDER BY score DESC FETCH FIRST 2 ROWS WITH TIES;
SELECT * FROM scores WHERE score < (SELECT score FROM scores WHERE id = 'e') ORDER BY score DESC FETCH FIRST 1 ROWS WITH TIES;
  1. 但是如果這時候突然加入了 (f, 80) 下一 round 也是拿不到的
  2. index 的效果一樣可以吃到，而且可以只下 (score) 及 (id)，這點比純 seek 的方式好
  3. 缺點是 response 的數量是不定數量，所以是有可能很多
  4. order by 多個欄位還要改寫 subquery，無法使用 row compare 的方式所以寫起來頗複雜
  5. 如果 order by 的欄位會變動，一樣可以考慮寫死 seek value 就可以解決

CURSOR 用法

CURSOR 用法是可以在 transaction 宣告並在 transaction 結束後釋放，在使用 CURSOR 的時候當下會有最新資料的 snapshot，加上 WITH HOLD 可以在這個 connection 中持有，只有當這個 connection 釋放後才會 close CURSOR。

範例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
CREATE TABLE t_random AS
SELECT random() AS r 
FROM generate_series(1, 1000000);

BEGIN;
DECLARE cur CURSOR FOR SELECT * FROM t_random ORDER BY r
-- 在第一次 fetch 才會在 server side 存最新的 snaphot 並讓 cur 指向
-- 速度會比較慢
fetch 100 from cur;
-- 速度才會恢復正常
fetch 100 from cur;
COMMIT;

BEGIN;
DECLARE cur CURSOR WITH HOLD FOR SELECT * from t_random ORDER BY r; 
-- commit 成功後需要在 server side 存最新的 snaphot 並讓 cur 指向
COMMIT;
-- 需要主動 close
CLOSE cur;

CURSOR 這樣的用法比較適合用在 background worker 要處理大量的資料，且無法將大量資料一次拉到 memory 處理的情境，所以其實是不太適合用在 API 分頁的。

總結

總結這四種分頁的實現，可以知道根據情境及需求我們可以這樣來區分：

  1. 在預期只有少量的資料可以採用 OFFSET，因為 performance 並不會太低，加上如果可以接受資料不一致的話是可以這樣做的，畢竟寫起來 query 簡單。
  2. 在預期有大量資料且前端上的設計是滾動的行為來進行加載新的分頁，那就可以採用 seek 的方式，但是要記得加入 index，order by 多欄位的時候要想想誰才能決定最後排序的關鍵
  3. 在預期有大量資料且可以知道 order by 的欄位重複數量不多，且 order by 欄位只會有一個，則適合用 WITH TIES + SEEK 的方式，此外也要能夠接受不定數量的 response 才行
  4. cursor 的用法比較適合在 background worker，當我想要批次處理資料庫的資料做其他用途時候，很適合。