京東面試：分庫分表後，如何設計深度翻頁？
單表場景，limit 深度分頁存在的嚴重性能問題
大家的業務接口，常常是分頁接口，這樣的接口，如果碰到深度分頁，都會有慢 sql 性能問題。
一個小夥伴反饋，他們公司今年 3 月份時候，線上發生一次大事故。主要後端服務器發生宕機，所有接口超時。宕機半小時後，又自動恢復正常。但是過了 2 小時，又再次發生宕機。
通過接口日誌定位，發現 MySQL 數據庫無法響應服務器。
被刷到 7000 多頁，偏移量（offset）高達 20w 多。
每當這條 SQL 執行時，數據庫 CPU 直接打滿。
查詢時間超過 1 分鐘纔有響應。
由於慢查詢導致數據庫 CPU 使用率爆滿，其他業務的數據庫請求無法得到及時響應，接口超時。最後，拖垮主服務器。
所以說，limit 深度分頁存在的嚴重性能問題。
MySQL Limit 語法格式：
SELECT * FROM table LIMIT [offset,] rows | rows OFFSET offset分頁查詢時，我們會在 LIMIT 後面傳兩個參數，一個是偏移量（offset），一個是獲取的條數（limit）。
當偏移量很小時，查詢速度很快，但是當 offset 很大時，查詢速度就會變慢。
假設有一張 300w 條數據的表，對其進行分頁查詢。
select * from user where sex = 'm' order by age limit 1, 10 // 32.8ms
select * from user where sex = 'm' order by age limit 10, 10 // 34.2ms
select * from user where sex = 'm' order by age limit 100, 10 // 35.4ms
select * from user where sex = 'm' order by age limit 1000, 10 // 39.6ms
select * from user where sex = 'm' order by age limit 10000, 10 // 5660ms
select * from user where sex = 'm' order by age limit 100000, 10 // 61.4 秒
select * from user where sex = 'm' order by age limit 1000000, 10 // 273 秒可以看到，隨着偏移量（offset）的增加，查詢時間變得越長。
上例中，當偏移的起始位置超過 10 萬時，分頁查詢的時間超過 61 秒。
當偏移量超過 100 萬時，查詢時間竟然長達 273 秒。
對於普通的業務而言，超過 1 秒的查詢是絕對不可以忍受的。
從上例中，我們可以總結出：LIMIT 分頁查詢的時間與偏移量值成正比。
當偏移量越大時，查詢時間越長。
這種情況，會隨着業務的增加，數據的增多，會越發的明顯。那麼，如何優化這種情況呢？答案是，索引覆蓋。
問題: 爲什麼 mysql 深度分頁會很慢？
包括兩層，server 層和存儲引擎層
server 層：查詢緩存，解析 sql 語句生成語法樹，執行 sql。在執行 sql 中包括預處理器，優化器和執行器。
-
預處理器：將查詢字段展開（如 select * 展開爲具體字段）並檢查字段是否合法
-
優化器：指定 sql 執行計劃，如選擇合適的索引
-
執行器：與存儲引擎層交互，執行 sql 語句
存儲引擎層 Engine 層：如 InnoDB 和 MyISAM。以 InnoDB 爲例，訪問 B + 樹數據結構獲取記錄（聚簇索引，二級索引等的訪問都在存儲引擎層）
limit 在深度翻頁場景下變成了： 全表掃描 + 文件排序 filesort
limit 是執行在 server 層，而不是 innodb 層。
也就是說， 在 server 層 需要獲取到 全部的 limit_cout 的結果，在發送給客戶端時，纔會進行 limit 操作。
比如如下 sql
select * from user where sex = 'm' order by age limit 1000000, 10 // 273 秒server 層 在執行器調存儲引擎 api 獲取到一條數據時，會查看數據是否是第 1000000 以後條數據，如果不是，就不會發送到客戶端，只進行 limit_cout 計數。
server 層 直到 10001 纔會發送到客戶端。也就是說，執行 limit m n 語句的場景下， Engine 層 實際上也會訪問前 m 條數據，然後返回後 n 條數據。
正是因爲 Engine 層 limit 會掃描每條記錄，因此如果我們查詢的字段需要回表掃描，每一次查詢都會拿着 age 列的二級索引查到的主鍵值去回表，limit 1000000 就會回表 1000000 次，效率極低。
所以如果我們使用 explain 查看查詢計劃：
explain select * from user where sex = 'm' order by age limit 1000000, 10其往往不會走 age 索引，而是全表掃描 + filesort，爲什麼？ 因爲優化器認爲選擇 age 索引的效率，甚至不如全表掃描 + 文件排序 filesort。
所以，當翻頁靠後時，查詢會變得很慢，因爲隨着偏移量的增加，我們需要排序和掃描的非目標行數據也會越來越多，這些數據再掃描後都會被丟棄。
單表場景 limit 深度分頁 的優化方法
對於 LIMIT 分頁查詢的性能優化，主要思路是利用 索引覆蓋 字段定位數據，然後再取出內容。
不使用索引覆蓋，查詢耗時情況：
SELECT * FROM `tbl_works` WHERE `status`=1 LIMIT 100000, 10 // 78.3 秒1）子查詢分頁方式
SELECT * FROM tbl_works
WHERE id >= (SELECT id FROM tbl_works limit 100000, 1)
LIMIT 20 // 54ms子查詢分頁方式，首先通過子查詢和索引覆蓋定位到起始位置 ID，然後再取所需條數的數據。
缺點是，不適用於結果集不以 ID 連續自增的分頁場景。
在複雜分頁場景，往往需要通過過濾條件，篩選到符合條件的 ID，此時的 ID 是離散且不連續的。
如果使用上述的方式，並不能篩選出目標數據。
當然，我們也可以對此方法做一些改進，首先利用子查詢獲取目標分頁的 ids，然後再根據 ids 獲取內容。 根據直覺將 SQL 改造如下：
SELECT * FROM tbl_works
WHERE id IN (SELECT id FROM tbl_works limit 100000, 10)
// 錯誤信息：
// This version of MySQL doesn't yet support 'LIMIT & IN/ALL/ANY/SOME subquery'然而，並不盡人意。我們得到一個錯誤提示。 錯誤信息的含義是，子查詢不能有 limit操作。於是，我們對 SQL 進行了改造，對子查詢包了一層：
SELECT t1.* FROM tbl_works t1
WHERE t1.id in (SELECT t2.id from (SELECT id FROM tbl_works limit 100000, 10) as t2) // 53.9ms執行成功，且查詢效率很高。
但是，這種寫法非常繁瑣。
我們可以使用下面的 join 分頁方式，達到相同的優化效果。實際上，兩者的原理是相同的。
2）join 分頁方式
SELECT * FROM tbl_works t1
JOIN (SELECT id from tbl_works WHERE status=1 limit 100000, 10) t2
ON t1.id = t2.id // 53.6 ms這條 SQL 的含義是，通過自連接與join定位到目標 ids，然後再將數據取出。
在定位目標 ids時，由於 SELECT的元素只有主鍵 ID，且status 存在索引，因此 MySQL 只需在索引中，就能定位到目標 ids，不用在數據文件上進行查找。
因而，查詢效率非常高。
基礎知識：什麼是 索引覆蓋（Cover Index）
如果索引包含所有滿足查詢需要的數據的索引，成爲索引覆蓋 (Covering Index)，也就是平時所說的不需要回表操作。
索引覆蓋（Index Covering）是指一個查詢可以完全通過索引來執行，而無需訪問實際的數據行。
在數據庫中，通常查詢語句包含了一系列的條件，這些條件用於篩選出符合特定條件的數據行。
如果這些條件能夠通過索引直接定位到符合條件的數據行，而無需訪問實際的數據頁，那麼就稱爲索引覆蓋。
比如我們有這樣一條 SQL 語句：
select name,age,level from user where name = "AAA" and age 17那麼，我們添加一個聯合索引，覆蓋所有的查詢內容, 聯合索引如下
key `idx_nal` (`name`,`age`,`level`) using btree有了這個聯合索引，我們在搜索的時候，只需要通過索引就能夠拿到我們需要的全部數據了。
簡單的說，索引覆蓋覆蓋所有需要查詢的字段（即，大於或等於所查詢的字段）。MySQL 可以通過索引獲取查詢數據， 這樣就避免了回表，不需要讀取數據行。
索引覆蓋注意事項：
- 如果一個索引包含了需要查詢的所有字段，那麼這個索引就是覆蓋索引。
2.MySQL 只能使用 B+Tree 索引做覆蓋索引，因爲只有 B + 樹能存儲索引列值
索引覆蓋的好處：
-
索引大小遠小於數據行大小。因而，如果只讀取索引，則能極大減少對數據訪問量。
-
索引按順序儲存。對於 IO 密集型的範圍查詢會比隨機從磁盤讀取每一行數據的 IO 要少。
-
避免對主鍵索引的二次查詢。二級索引的葉子節點包含了主鍵的值，如果二級索引包含所要查詢的值，則能避免二次查詢主鍵索引（聚簇索引，聚簇索引既存儲了索引，也儲存了值）。
單表場景 limit 深度分頁 總結
通過利用索引覆蓋，能極大的優化了 Limit 分頁查詢的效率。
在真正的實踐中，除了使用索引覆蓋，優化查詢速度外，我們還可以使用 Redis 緩存，將熱點數據進行緩存儲存。
背景描述的事故，我們考慮了時間成本和業務複雜度後，最後採取的是限制分頁和增加緩存。
所謂的限制分頁，即在不影響閱讀體驗的前提下，只允許用戶可以查看前幾千條的數據。
經測驗，偏移量較小時的查詢效率較令人滿意，查詢效率接近使用索引覆蓋查詢的速度。
分表場景，limit 深度分頁存在的嚴重性能問題
大家知道 ，當一個表（比如訂單表） 達到 500 萬條或 2GB 時，需要考慮水平分表。
具體請參見尼恩架構團隊的文章：
比如大型的電商系統中的訂單服務，業務量很少時，單庫單表基本扛得住，但是隨着時間推移，數據量越來越多，訂單服務在讀寫的性能上逐漸變差。
這個時候，選擇了分庫分表；至於如何拆分，分片鍵如何選擇等等細節。 請看尼恩的文章：
100 億級數據存儲架構：MYSQL 雙寫 + HABSE +Flink +ES 綜合大實操
這裏也介紹是，是 Sharding-JDBC 的 limit 深度分頁 執行邏輯和性能問題。
Sharding-JDBC 從多個分表獲取分頁數據，與單表分頁的執行邏輯，本質是不同的。
分表分頁場景下的 分頁邏輯， 並不是： 簡單的去 每個分表取到同樣的數量的數據， 簡單歸併 + 挑選 。
分表分頁場景下的 分頁邏輯，要從 0 開始去每一個分表 獲取到 limit 全部的數據， 而不是從 offset 開始。
如果是深度分頁， 比如說：
select * from user where sex = 'm' order by age limit 1000000, 10 // 273 秒那麼要去每一個 分表 獲取到 limit 全部的 1000000 + 10 條 數據 ， 會導致每一個分表都走 全表掃描 + 文件排序 filesort ， 每一個分表的性能都很低。
當然，尼恩在這裏帶大家首先要解決的問題是： 爲什麼 表分頁場景下的 分頁邏輯，要從 0 開始去每一個分表 獲取到 limit 全部的數據， 而不是從 offset 開始。
假設每 10 條數據爲一頁，取第 2 頁數據。
在分片環境下獲取 LIMIT 10, 10，歸併之後再根據排序條件取出前 10 條數據是不正確的。
舉例說明，若 SQL 爲：
SELECT score FROM t_score ORDER BY score DESC LIMIT 1, 2;下圖展示了不進行 SQL 的改寫的分頁執行結果：
通過圖中所示，想要取得兩個表中共同的按照分數排序的第 2 條和第 3 條數據，理論上，應該是 95 和 90。
實際上呢？
由於執行的 SQL 只能從每個表中獲取第 2 條和第 3 條數據，即:
-
從 t_score_0 表中獲取的是 90 和 80；
-
從 t_score_0 表中獲取的是 85 和 75。
因此進行結果歸併時，只能從獲取的 90，80，85 和 75 之中進行歸併，那麼，無論怎麼實現，結果歸併之後，都不可能獲得正確的結果。
正確的做法:
是將分頁條件改寫爲 LIMIT 0, 3，取出所有前兩頁數據，再結合排序條件計算出正確的數據。
下圖展示了進行 SQL 改寫之後的分頁執行結果。
回到問題： 爲什麼 表分頁場景下的 分頁邏輯，要從 0 開始去每一個分表 獲取到 limit 全部的數據， 而不是從 offset 開始。
答案是： 爲了合併之後的結果不出錯，每一個分表的查詢是必須 0 開始， 歸併之後的結果纔不會錯。
分表場景下 功能和性能的衝突：從 0 開始的性能瓶頸
注意，這裏有個大問題：
爲了結果不出錯，歸併之前的查詢，是 0 開始， 結果纔可能是對的。
所以，詢偏移量過大的分頁會導致數據庫獲取數據性能低下，
以 MySQL 爲例：
如果不是分庫分表，這句 SQL 會使得 MySQL 在無法利用索引的情況下跳過 1000000 條記錄後，再獲取 10 條記錄，其性能可想而知。
然而， 在分庫分表的情況下（假設分爲 2 個庫），爲了保證數據的正確性，SQL 會改寫爲：
所以， 分庫分表場景， Sharding-JDBC 需要將偏移量前的記錄全部取出，歸併排序後，挑選最後 10 條記錄。
這會在數據庫本身就執行很慢的情況下，進一步加劇性能瓶頸。
因爲原 SQL 僅需要傳輸 10 條記錄至客戶端，而改寫之後的 SQL 則會傳輸 1,000,010 * 2 的記錄至客戶端。
Sharding-JDBC 的性能優化措施
那麼，Sharding-JDBC 會將全量的記錄（如 1,000,010 * 2 記錄） 都全部加載至內存嗎？
不會，這樣加載，會佔用大量內存而導致內存溢出。
Sharding-JDBC 知道了問題所在，本身也會做優化。
Sharding-JDBC 的性能優化措施，主要如下：
（1）採用流式處理 + 歸併排序的方式來避免內存的過量佔用。
由於 SQL 改寫不可避免的佔用了額外的帶寬，但並不會導致內存暴漲。
與直覺不同，大多數人認爲 Sharding-JDBC 會將 1,000,010 * 2 記錄全部加載至內存，進而佔用大量內存而導致內存溢出。
但由於每個結果集的記錄是有序的，因此 Sharding-JDBC 每次僅獲取各個分片的當前結果集記錄，駐留在內存中的記錄僅爲當前路由到的分片的結果集的當前遊標指向而已。
對於本身即有序的待排序對象，歸併排序的時間複雜度僅爲 O(n)，性能損耗很小。
（2）Sharding-JDBC 對僅落至多分片的查詢進行進一步優化。
落至單分片查詢的請求並不需要改寫 SQL 也可以保證記錄的正確性，因此在此種情況下，Sharding-JDBC 並未進行 SQL 改寫，從而達到節省帶寬的目的。
一般情況下，性能慢，都是第一種情況。
當然，流式查詢的也是有弊端的
採用遊標查詢的方式的缺點很明顯。
流式（遊標）查詢需要注意：當前查詢會獨佔連接！
必須先讀取（或關閉）結果集中的所有行，然後才能對連接發出任何其他查詢，否則將引發異常！
執行一個流式查詢後，數據庫訪問框架就不負責關閉數據庫連接了，需要應用在取完數據後需要自己關閉。
由於 MySQL_Server 不知道客戶端什麼時候將數據消費完，而自身的對應表可能會有 DML 寫入操作，此時 MySQL_Server 需要建立一個臨時空間來存放需要拿走的數據。
因此對於當你啓用 useCursorFetch 讀取 大表的時候，會看到 MySQL 上的幾個現象：
-
IOPS 飆升，因爲需要返回的數據需要寫入到臨時空間中，存在大量的 IO 讀取和寫入，此流程可能會引起其它業務的寫入抖動
-
磁盤空間飆升，寫入臨時空間的數據會在讀取完成或客戶端發起 ResultSet#close 操作時由 MySQL_Server 回收
-
客戶端 JDBC 發起 sql_query，可能會有長時間等待，這段時間爲 MySQL_Server 準備數據階段。
但是 普通查詢等待時間與遊標查詢等待時間原理上是不一致的: 前者是在讀取網絡緩衝區的數據，沒有響應到業務層面；後者是 MySQL 在準備臨時數據空間，沒有響應到 JDBC
-
數據準備完成後，進行到傳輸數據階段，網絡響應開始飆升，IOPS 由 "寫" 轉變爲 "讀"
分表場景 + 大表場景，limit 嚴重性能問題 如何解決？
雖然有流式查詢，但是分表場景 + 大表場景，limit 深度翻頁還是存在的嚴重性能問題 ，基本上是分頁越大後續的查詢越耗資源並且越慢，如何解決呢？
優化方案 1： 禁止跳頁查詢法
由於 LIMIT 並不能通過索引查詢數據，
因此如果可以保證 ID 的連續性，通過 ID 進行分頁是比較好的解決方案：
或者：通過記錄上次查詢結果的最後一條記錄的 ID，進行下一頁的查詢：
如果不是 id 列， 假設排序的列爲 col，禁止跳頁查詢法的兩個步驟大致如下：
（1）用正常的方法取得第一頁數據，並得到第一頁記錄的 max_col 最大值；
（2）每次翻頁，將 order by col offset X limit Y; 改寫成 下面的語句
order by col where col>$max_col limit Y;以保證每次只返回一頁數據，性能爲常量。
優化方法 2：二次查詢法
假設排序的列爲 col，二次查詢法的兩個步驟大致如下：
（1）分頁偏移量平均 offset/N(分片數) ，將 order by col offset X limit Y; 改寫成
order by col offset X/N limit Y;（2）多頁返回，找到最小值 col_min 和 最大 值 col_max；
（3）between 二次查詢
order by col between col_min and col_i_max;（4）設置虛擬 col_min，找到 col_min 在各個分表的 offset，從而得到 col_min 在全局的 offset；
（5）得到了 col_min 在全局的 offset，自然得到了全局的 offset X limit Y；
二次查詢法的一個例子
例子：分表結構
CREATE TABLE `student_time_0` (
`id` int(11) unsigned NOT NULL AUTO_INCREMENT,
`user_id` int(11) NOT NULL,
`name` varchar(200) COLLATE utf8_bin DEFAULT NULL,
`age` tinyint(3) unsigned DEFAULT NULL,
`create_time` bigint(20) DEFAULT NULL,
PRIMARY KEY (`id`)
) ENGINE=InnoDB AUTO_INCREMENT=674 DEFAULT CHARSET=utf8 COLLATE=utf8_bin;有這樣的三個表
-
student_time_0, -
student_time_1, -
student_time_2,
以 user_id 作爲分表鍵，根據表數量取模作爲分表依據
這裏先構造點數據，
insert into student_time (`name`, `user_id`, `age`, `create_time`) values (?, ?, ?, ?)主要是爲了保證 create_time 唯一，比較好說明問題，
int i = 0;
try (
Connection conn = dataSource.getConnection();
PreparedStatement ps = conn.prepareStatement(insertSql)) {
do {
ps.setString(1, localName + new Random().nextInt(100));
ps.setLong(2, 10086L + (new Random().nextInt(100)));
ps.setInt(3, 18);
ps.setLong(4, new Date().getTime());
int result = ps.executeUpdate();
LOGGER.info("current execute result: {}", result);
Thread.sleep(new Random().nextInt(100));
i++;
} while (i <= 2000);三個表的數據分別是 673，678，650，各個表數據不一樣，
接下來，做一個這樣的分頁查詢
select * from student_time ORDER BY create_time ASC limit 1000, 5;student_time 對於我們使用的 sharding-jdbc 來說當然是邏輯表， sharding-jdbc 會改寫爲
select * from student_time ORDER BY create_time ASC limit 0, 1005;即使如 sharding-jdbc 對於合併排序的優化做得比較好，也還是需要傳輸那麼大量的數據，並且查詢也耗時，那麼有沒有解決方案呢
-
第一個辦法禁止跳頁，而是隻給下一頁，那麼我們就能把前一次的最大偏移量的 create_time 記錄下來，下一頁就可以拿着這個偏移量進行查詢
-
第二個辦法是二次查詢法
這個辦法的第一步跟前面那個錯誤的方法或者說不準確的方法一樣，先是將分頁偏移量平均 1000/3 = 333，根據這個 limit 333,5 在三個表裏進行查詢
t0
334 10158 nick95 18 1641548941767
335 10098 nick11 18 1641548941879
336 10167 nick51 18 1641548942089
337 10167 nick3 18 1641548942119
338 10170 nick57 18 1641548942169
t1
334 10105 nick98 18 1641548939071 最小
335 10174 nick94 18 1641548939377
336 10129 nick85 18 1641548939442
337 10141 nick84 18 1641548939480
338 10096 nick74 18 1641548939668
t2
334 10184 nick11 18 1641548945075
335 10109 nick93 18 1641548945382
336 10181 nick41 18 1641548945583
337 10130 nick80 18 1641548945993
338 10184 nick19 18 1641548946294 最大第一遍的目標是啥，查出來的最小的 create_time 和最大的 create_time 找出來，然後再去三個表裏查詢，
其實主要是最小值，因爲拿着最小值去查，就能知道這個最小值在每個表裏處在什麼位置，
order by col between col_min and col_i_max;接下來，將第一遍查出來的最小的 create_time 和最大的 create_time 找出來，然後再去三個表裏查詢，
t0
322 10161 nick81 18 1641548939284
323 10113 nick16 18 1641548939393
324 10110 nick56 18 1641548939577
325 10116 nick69 18 1641548939588
326 10173 nick51 18 1641548939646
t1
334 10105 nick98 18 1641548939071
335 10174 nick94 18 1641548939377
336 10129 nick85 18 1641548939442
337 10141 nick84 18 1641548939480
338 10096 nick74 18 1641548939668
t2
297 10136 nick28 18 1641548939161
298 10142 nick68 18 1641548939177
299 10124 nick41 18 1641548939237
300 10148 nick87 18 1641548939510
301 10169 nick23 18 1641548939715這裏只貼了前五條數據，爲了方便知道偏移量，每個分表都使用了自增主鍵，
我們可以看到前一次查詢的最小值分別在其他兩個表裏的位置分別是 322-1 和 297-1，
那麼，對於總體來說，這個時間的起始位置，應該是在 322 - 1 + 334-1 + 297 - 1 = 951，
那麼，只要對後面的數據最多每個表查 1000 - 951 + 5 = 54 條數據，再進行合併排序就可以獲得最終正確的結果。
這個就是的二次查詢法。
可見，二次查詢法很麻煩， 不如禁止跳頁法，或者 es 組合方法，直接，有效。
優化方案 3：使用 ES+HBASE 海量 NOSQL 架構方案
對於海量數據場景，建議使用 ES+HBASE 這樣的 海量 NOSQL 架構方案，具體如下：
100 億級數據存儲架構：MYSQL 雙寫 + HABSE +Flink +ES 綜合大實操
100 億級任務調度篇：從 0 到 1, 從入門到 XXLJOB 工業級使用
高併發搜索 ES 聖經：從 0 到 1, 從入門到 ElasticSearch 工業級使用
超級底層：10WQPS/PB 級海量存儲 HBase/RocksDB，底層 LSM 結構是什麼？
本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/Mx3G2R88EHO0koC8-HcWDA