背景
大部分开发和DBA同行都对分页查询非常非常了解，看帖子翻页需要分页查询，搜索商品也需要分页查询。那么问题来了,遇到上千万或者上亿的数据量怎么快速的拉取全量，比如大商家拉取每月千万级别的订单数量到自己独立的ISV做财务统计;或者拥有百万千万粉丝的公众大号,给全部粉丝推送消息的场景。本文讲讲个人的优化分页查询的经验，抛砖引玉。
二 分析
在讲如何优化之前我们先来看看一个比较常见错误的写法
该SQL是一个非常典型的排序+分页查询：
MySQL 执行此类SQL时需要先扫描到N行，然后再去取 M行。对于此类操作，取前面少数几行数据会很快，但是扫描的记录数越多，SQL的性能就会越差，因为N越大，MySQL需要扫描越多的数据来定位到具体的N行，这样耗费大量的IO 成本和时间成本。一图胜千言，我们使用简单的图来解释为什么 上面的sql 的写法扫描数据会慢。
t 表是一个索引组织表，key idx_kid_type(kid,type) 。
符合kid=3 and type=1 的记录有很多行,我们取第 9，10行。
MySQL 是如何执行上面的sql 的？对于Innodb表，系统是根据 idx_kid_type 二级索引里面包含的主键去查找对应的行。对于百万千万级别的记录而言，索引大小可能和数据大小相差无几，cache在内存中的索引数量有限，而且二级索引和数据叶子节点不在同一个物理块儿上存储，二级索引与主键的相对无序映射关系，也会带来大量的随机IO请求，N值越大越需要遍历大量索引页和数据叶，需要耗费的时间就越久。
鉴于上面的大分页查询耗费时间长的原因，我们思考一个问题，是否需要完全遍历“无效的数据”？如果我们需要limit 8，2；我们跳过前面8行无关的数据页遍历，可以直接通过索引定位到第9，第10行，这样操作是不是更快了？依然是一图胜千言，通过这其实也是 延迟关联的 核心思思:通过使用覆盖索引查询返回需要的主键,再根据主键关联原表获得需要的数据,而不是通过二级索引获取主键再通过主键去遍历数据页。
通过上面的原理分析，我们知道通过常规方式进行大分页查询慢的原因，也知道了提高大分页查询的具体方法 ，下面我们讨论一下在线上业务系统中常用的解决方法。
三 实践出真知
针对limit 优化有很多种方式:
- 前端加缓存、搜索，减少落到库的查询操作。比如海量商品可以放到搜索里面，使用瀑布流的方式展现数据，很多电商网站采用了这种方式。
- 优化SQL 访问数据的方式，直接快速定位到要访问的数据行。
- 使用书签方式 ，记录上次查询最新/大的id值，向后追溯 M行记录。
对于第二种方式 我们推荐使用"延迟关联"的方法来优化排序操作，何谓"延迟关联" ：通过使用覆盖索引查询返回需要的主键,再根据主键关联原表获得需要的数据。
3.1 延迟关联
优化前
root@xxx 12:33:48>explain SELECT id, cu_id, name, info, biz_type, gmt_create, gmt_modified,start_time, end_time, market_type, back_leaf_category,item_status,picuture_url FROM relation where biz_type ='0' AND end_time >='2014-05-29' ORDER BY id asc LIMIT 149420 ,20;
+----+-------------+-------------+-------+---------------+-------------+---------+------+--------+-----+
| id | select_type | table | type | possible_keys | key | key\_len | ref | rows | Extra |
+----+-------------+-------------+-------+---------------+-------------+---------+------+--------+-----+
| 1 | SIMPLE | relation | range | ind\_endtime | ind\_endtime | 9 | NULL | 349622 | Using where; Using filesort |
+----+-------------+-------------+-------+---------------+-------------+---------+------+--------+-----+
1 row in set (0.00 sec)其执行时间：
优化后:
root@xxx 12:33:43>explain SELECT a.* FROM relation a, (select id from relation where biz_type ='0' AND end\_time >='2014-05-29' ORDER BY id asc LIMIT 149420 ,20 ) b where a.id=b.id;
+----+-------------+-------------+--------+---------------+---------+---------+------+--------+-------+
| id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra |
+----+-------------+-------------+--------+---------------+---------+---------+------+--------+-------+
| 1 | PRIMARY | <derived2> | ALL | NULL | NULL | NULL | NULL | 20 | |
| 1 | PRIMARY | a | eq_ref | PRIMARY | PRIMARY | 8 | b.id | 1 | |
| 2 | DERIVED | relation | index | ind_endtime | PRIMARY | 8 | NULL | 733552 | |
+----+-------------+-------------+--------+---------------+---------+---------+------+--------+-------+
3 rows in set (0.36 sec)执行时间:
优化后 执行时间 为原来的1/3 。
3.2 使用书签的方式
首先要获取复合条件的记录的最大 id和最小id(默认id是主键)
其次 根据id 大于最小值或者小于最大值 进行遍历。
案例
当遇到延迟关联也不能满足查询速度的要求时
使用延迟关联查询数据510ms ，使用基于书签模式的解决方法减少到10ms以内 绝对是一个质的飞跃。
SELECT * FROM t1 where client_id='xxxxx' and is_valid=1 and id<47399727 order by id desc LIMIT 100;
四 小结
从我们的优化经验和案例上来讲，根据主键定位数据的方式直接定位到主键起始位点，然后过滤所需要的数据 相对比延迟关联的速度更快些，查找数据的时候少了二级索引扫描。但是 优化方法没有银弹，没有一劳永逸的方法。比如下面的例子
order by id desc 和 order by asc 的结果相差70ms ，生产上的案例有limit 100 相差1.3s ，这是为什么呢？留给大家去思考吧。
最后，其实我相信还有其他优化方式，比如在使用不到组合索引的全部索引列进行覆盖索引扫描的时候使用 ICP 的方式 也能够加快大分页查询。
以上是我在优化分页查询方面的经验总结，抛砖引玉，有兴趣的朋友可以多交流，分享你们的优化经验案例。