Paging Problem

Troubleshooting

在實務上，我們常常會實作 paging 功能，
並且使用 limit 與 offset 來完成，
一頁 10 筆 records，
略過前面 30 筆資料，到達第四頁，
像是下面這樣。

select * from letters
order by createTime DESC
limit 10 OFFSET 30

如果在資料不多的情況下，可能毫無感覺，但果今天資料量大時，可能就不一樣了。

select * from letters
order by createTime DESC
limit 10 OFFSET 400000

咦？奇怪，怎麼突然感覺翻頁越翻越慢了？
或許是沒在createTime建立 index。
CREATE INDEX ON letters (createTime);
查了一下 Explain，如果<1 萬筆，都會正常使用 index 做 query。
但>時，就又開始使用Seq Scan。
崩潰，到底發生什麼事情了！

Explain

先來 explain 看看加完 index 後的結果

owl_conference=# EXPLAIN ANALYZE SELECT * FROM letters
                 ORDER BY createTime DESC OFFSET 400000 LIMIT 10;
                 QUERY PLAN
-------------------------------------------------------------------------
 Limit  (cost=23710.66..23711.25 rows=10 width=24)
        (actual time=881.710..881.718 rows=10 loops=1)
   ->  Index Scan Backward using letters_delivered_by_idx on letters
       (cost=0.42..24532.28 rows=413861 width=24)
       (actual time=0.013..854.924 rows=400010 loops=1)
 Planning time: 0.106 ms
 Execution time: 654.810 ms
(4 rows)

可以看到雖然使用了 index 但Index Scan還是非常的耗時啊！
我們其實只需要 10 筆 records，但他撈出了 400010 筆，這感覺是個可以突破的缺口。

Try1: 400010 只撈 index，其餘 10 筆再做 join

注意！這個地方只對 Index Organized Table 有優化效果，
Heap Organized Table 早已經沒這個問題。

我們回想一下 Index Organized Table 的 index，
會先 query Secondary Index，然後取得 pk，
再到 Clustered Index 取出最終的 records。

所以好好利用Index Only這個 query，直接在 index 中取值，
不要讓它到 Clustered Index 中取值。

SELECT id FROM letters
ORDER BY createTime DESC
LIMIT 10 OFFSET 400010;

可以順利地利用Index Only直接取到 pk，然後再去 Clustered Index 中取值了。

SELECT * FROM card AS main
INNER JOIN (
    SELECT id
    FROM card
    ORDER BY createTime DESC
    LIMIT 10 OFFSET 400010
) AS sub
ON main.id = sub.id
ORDER BY createTime DESC;

雖然避開了去 Clustered Index 中取值，但 Index Only Scan 仍然是花非常多時間的，
而且如果你是 query Heap Organized Table的 table 本來就不需要這樣做，
因為他不需要再去 Clustered Index 中取值。

Try2: 使用 where 取代 offset

OFFSET 400000 LIMIT 10造成了(actual time=0.013..854.924 rows=400010 loops=1)
讓 Scan Index跑了 400000 才抓到想要的內容。
何不直接使用 where 來將資料直接鎖定開頭，然候單單指抓取想要的資料呢？
變成這樣子。

SELECT ...
  FROM ...
 WHERE ...
   AND id < ?last_seen_id
 ORDER BY id DESC
 FETCH FIRST 10 ROWS ONLY

我們常常會使用 createTime 作為定位點，但如果 createTime 不是 unique key，
那麼將會造成很大的困擾，可能會發生多筆 records 甚至 n 頁在同一個 createTime 上，
這時，我們必須為 index 做點手腳，使用 compose index 將 createTime 與 pk 做上綁定，
這麼一來就可以確定這個定位點是唯一值了。
CREATE INDEX id_t_idx ON sales (createTime，id)
特別注意，這裡做的 compose index 順序必須要對喔!
經過優化後，來 Explain 看看。

SELECT *
  FROM letters
 WHERE ...
   AND createTime> xxx AND id < last_seen_id
 ORDER BY createTime DESC
 FETCH FIRST 10 ROWS ONLY

這麼一來每次的翻頁就只會查找該段的 index 了！

參考資料

1. Ordering and a word on offset
2. Paging Through Results
3. Querying Top-N Rows
4. Indexing Order By
5. PostgreSQL execution plan visualizer