英文：Robert Eisele
譯者：Giraffe
連結：http://yemengying.com/2016/05/28/optimized-pagiantion-mysql/
一道面試的問題，當MySQL表中有資料量很大的時候如何做分頁。。。。當時隻知道在資料量很大的時候可以分表，但不知道不分表時可以怎麼做。。。。唉，誰讓代理商就那麼幾條資料，一個簡單的limit，offset就完全hold住了(捂臉)。。。
很多應用往往隻展示最新或最熱門的幾條記錄，但為了舊記錄仍然可通路，是以就需要個分頁的導航欄。然而，如何通過MySQL更好的實作分頁，始終是比較令人頭疼的問題。雖然沒有拿來就能用的解決辦法，但了解資料庫的底層或多或少有助于優化分頁查詢。
我們先從一個常用但性能很差的查詢來看一看。
SELECT *
FROM city
ORDER BY id DESC
LIMIT 0, 15
這個查詢耗時0.00sec。So，這個查詢有什麼問題呢？實際上，這個查詢語句和參數都沒有問題，因為它用到了下面表的主鍵，而且隻讀取15條記錄。
CREATE TABLE city (
id int(10) unsigned NOT NULL AUTO_INCREMENT,
city varchar(128) NOT NULL,
PRIMARY KEY (id)
) ENGINE=InnoDB;
真正的問題在于offset(分頁偏移量)很大的時候，像下面這樣：
LIMIT 100000, 15;
上面的查詢在有2M行記錄時需要0.22sec，通過EXPLAIN檢視SQL的執行計劃可以發現該SQL檢索了100015行，但最後隻需要15行。大的分頁偏移量會增加使用的資料，MySQL會将大量最終不會使用的資料加載到記憶體中。就算我們假設大部分網站的使用者隻通路前幾頁資料，但少量的大的分頁偏移量的請求也會對整個系統造成危害。Facebook意識到了這一點，但Facebook并沒有為了每秒可以處理更多的請求而去優化資料庫，而是将重心放在将請求響應時間的方差變小。
對于分頁請求，還有一個資訊也很重要，就是總共的記錄數。我們可以通過下面的查詢很容易的擷取總的記錄數。
SELECT COUNT(*)
FROM city;
然而，上面的SQL在采用InnoDB為存儲引擎時需要耗費9.28sec。一個不正确的優化是采用SQL_CALC_FOUND_ROWS,SQL_CALC_FOUND_ROWS可以在能夠在分頁查詢時事先準備好符合條件的記錄數，随後隻要執行一句select FOUND_ROWS(); 就能獲得總記錄數。但是在大多數情況下，查詢語句簡短并不意味着性能的提高。不幸的是，這種分頁查詢方式在許多主流架構中都有用到，下面看看這個語句的查詢性能。
SELECT SQL_CALC_FOUND_ROWS *
這個語句耗時20.02sec，是上一個的兩倍。事實證明使用SQL_CALC_FOUND_ROWS做分頁是很糟糕的想法。
下面來看看到底如何優化。文章分為兩部分，第一部分是如何擷取記錄的總數目，第二部分是擷取真正的記錄。
高效的計算行數
如果采用的引擎是MyISAM，可以直接執行COUNT(*)去擷取行數即可。相似的，在堆表中也會将行數存儲到表的元資訊中。但如果引擎是InnoDB情況就會複雜一些，因為InnoDB不儲存表的具體行數。
我們可以将行數緩存起來，然後可以通過一個守護程序定期更新或者使用者的某些操作導緻緩存失效時，執行下面的語句：
USE INDEX(PRIMARY);
擷取記錄
下面進入這篇文章最重要的部分，擷取分頁要展示的記錄。上面已經說過了，大的偏移量會影響性能，是以我們要重寫查詢語句。為了示範，我們建立一個新的表“news”，按照時事性排序(最新釋出的在最前面)，實作一個高性能的分頁。為了簡單，我們就假設最新釋出的新聞的Id也是最大的。
CREATE TABLE news(
id INT UNSIGNED PRIMARY KEY AUTO_INCREMENT,
title VARCHAR(128) NOT NULL
一個比較高效的方式是基于使用者展示的最後一個新聞Id。查詢下一頁的語句如下，需要傳入目前頁面展示的最後一個Id。
FROM news WHERE id < $last_id
LIMIT $perpage
查詢上一頁的語句類似，隻不過需要傳入目前頁的第一個Id，并且要逆序。
FROM news WHERE id > $last_id
ORDER BY id ASC
上面的查詢方式适合實作簡易的分頁，即不顯示具體的頁數導航，隻顯示“上一頁”和“下一頁”，例如部落格中頁腳顯示“上一頁”，“下一頁”的按鈕。但如果要實作真正的頁面導航還是很難的,下面看看另一種方式。
SELECT id
FROM (
SELECT id, ((@cnt:= @cnt + 1) + $perpage - 1) % $perpage cnt
FROM news
JOIN (SELECT @cnt:= 0)T
WHERE id < $last_id
ORDER BY id DESC
LIMIT $perpage * $buttons
)C
WHERE cnt = 0;
通過上面的語句可以為每一個分頁的按鈕計算出一個offset對應的id。這種方法還有一個好處。假設，網站上正在釋出一片新的文章，那麼所有文章的位置都會往後移一位，是以如果使用者在釋出文章時換頁，那麼他會看見一篇文章兩次。如果固定了每個按鈕的offset Id，這個問題就迎刃而解了。Mark Callaghan發表過一篇類似的部落格，利用了組合索引和兩個位置變量，但是基本思想是一緻的。
如果表中的記錄很少被删除、修改，還可以将記錄對應的頁碼存儲到表中，并在該列上建立合适的索引。采用這種方式，當新增一個記錄的時候，需要執行下面的查詢重新生成對應的頁号。
SET p:= 0;
UPDATE news SET page=CEIL((p:= p + 1) / $perpage) ORDER BY id DESC;
當然，也可以新增一個專用于分頁的表，可以用個背景程式來維護。
UPDATE pagination T
JOIN (
SELECT id, CEIL((p:= p + 1) / $perpage) page
ORDER BY id
ON C.id = T.id
SET T.page = C.page;
現在想擷取任意一頁的元素就很簡單了：
FROM news A
JOIN pagination B ON A.id=B.ID
WHERE page=$offset;
還有另外一種與上種方法比較相似的方法來做分頁，這種方式比較試用于資料集相對小，并且沒有可用的索引的情況下—比如處理搜尋結果時。在一個普通的伺服器上執行下面的查詢，當有2M條記錄時，要耗費2sec左右。這種方式比較簡單，建立一個用來存儲所有Id的臨時表即可(這也是最耗費性能的地方)。
CREATE TEMPORARY TABLE _tmp (KEY SORT(random))
SELECT id, FLOOR(RAND() * 0x8000000) random
ALTER TABLE _tmp ADD OFFSET INT UNSIGNED PRIMARY KEY AUTO_INCREMENT, DROP INDEX SORT, ORDER BY random;
接下來就可以向下面一樣執行分頁查詢了。
FROM _tmp
WHERE OFFSET >= $offset
ORDER BY OFFSET
LIMIT $perpage;
簡單來說，對于分頁的優化就是。。。避免資料量大時掃描過多的記錄。
部落格比較長，是以翻譯的有些粗糙。。。，之後會在好好檢查一遍的。在自己做測試時，有些查詢時間與作者有點不一緻，不過作者這篇部落格是寫于2011年的，so~不要在意具體資料，領會精神吧~~
歡迎指正錯誤，歡迎一起讨論！！！