避免用 SQL 的 OFFSET 實做 Pager

發現以前沒有提到過...?

WordPress.com Developer Resources 寫的這篇「An efficient alternative to paging with SQL OFFSETs」提到了用 OFFSET 實做 Pager 的效率問題。

因為 RDBMS 是人寫的,所以人想不到的方法,程式也做不到,像是這樣的 SQL query 效率不會好:

SELECT * FROM my_table ORDER BY pk LIMIT 8000000, 100;

如果這是一般以 B+tree 儲存的 RDBMS (或是類似的資料結構),會先把 pk 拿出來,從最小的開始計算,掃過八百萬次後再去抓一百筆 pk 的值,最後再回到 my_table 內把所有資料拉出來。

這個方法當 offset 小的時候不會有感覺,但大了以後就會爆炸。就算 primary key 都在記憶體內,仍然是狂操 CPU L2/L3 以及記憶體的存取速度。

目前常見的分頁作法是在 url 上妥協,只提供「下一頁」或「下 n 頁」的功能。如此一來,url 變成:

https://www.example.com/blog?page=10&started_at=12345678
https://www.example.com/blog?page=11&started_at=12345690
https://www.example.com/blog?page=12&started_at=12345710

started_at 變成 unix timestamp,而資料庫對時間欄位 index。如此一來,資料庫在查詢的時候就可以先 B+tree 找到 started_at 的節點 (或是小於他最近的節點),然後連續抽出一百筆。

另外一種則是在產品面上「妥協」,也就是方法保持不變,但限制「一個 thread 最多只能回 1000 篇」,這在 2ch 或是論壇上很常看到。

This entry was posted in Computer, Database, Murmuring, Software and tagged , , , , . Bookmark the permalink.

One Response to 避免用 SQL 的 OFFSET 實做 Pager

  1. Pingback: 好站與連結分享 2014/02 (2) | Vixual

Leave a Reply

Your email address will not be published. Required fields are marked *