limit offset慢查询背后的原因与解法

问题

问题起源于一个涉及到数据遍历的脚本。

该脚本会对一个MySQL表中的数据进行有条件的全表遍历。SQL如下：

select * from table where update_time < CURDATE() order by update_time desc limit 100 offset 10000;

这样写看起来很正常，但实际在数据量大了之后，使用起来开始出现问题，越来越慢，慢到不可接受，甚至影响其他的读写操作。

分析

原因就是limit offset这个语句，并不如人们望文生义想的那样，直接定位到第10000位然后取后面的100条记录。

而是令人发指的先一直一条一条读取到10100条，然后再根据offset的设置，舍弃前10000条记录，返回后面的100条记录。

其实原因也好理解，MySQL的数据存储并不是一个数组，可以直接根据下标获取第X位。即使给你搜索的字段加了索引，也只是使用该字段的值去建立一个新的二叉树（索引二叉树），来方便你快速找到数据位置。

但是试想一下，当你要在二叉树中找到第n大的数时，你并不能像找一个具体的值一样利用二叉树的能力快速找到，因为你也不知道每个节点的左子树和右子树分别有多少记录。

因此只能借用索引二叉树是个B+树这一特点，去利用叶子节点上的链表，去遍历你要数的所有节点。

这还不止。

MySQL不仅仅会让你遍历一遍索引值，我们知道MySQL默认的InnoDB引擎分为主键索引二叉树和辅助索引二叉树，你使用其他自己定义的索引时，只是得到主键，真正取数据还得根据索引得到的主键，去主键索引二叉树获取到具体的数据。

那此时，实际上你不仅在无效遍历前10000个索引节点，MySQL还会让你去根据遍历到的这10000个无效索引节点去真正地查10000次数据，这就是10000次无效的数据查询。

为什么MySQL一定要让你去查这些无效数据呢？因为MySQL的实现分为引擎层和数据层，limit offset只能作用于引擎层返回的结果集，因此对引擎层来说，他也不知道前10000个是会扔掉的数据，只能先一股脑地往上传。

更进一步的，为什么MySQL不把limit offset直接传给引擎层呢？是因为查询语句实际是由一个个算子组合起来的，比如有选择算子（where条件）、连接算子（join）、投影算则（select的字段）、数据源等，不同的算子有计算顺序，导致底层的算子是不知道上层计算条件的。

总得来说，这种实现就导致，数据量越大，offset得越多，速度就会越慢，对MySQL的压力就会越大。

解法

知道了问题根源之后，就可以对应地找解法。

解法1

比如我这里是要遍历数据，既然用offset遍历有性能问题，那就直接用主键id的范围条件来缩小范围。

select * from table where id > 10000 limit 100;

根据上面的分析我们可以指导，这样做，一方面直接省去了一次查询索引二叉树后再查主键二叉树的过程，而是直接就查主键二叉树并获取其节点上的数据。

另一方面，用大于的条件，从而利用好二叉树的特性，快速查找到数据的起始节点，然后获取其后的100条记录数据即可。

理解清楚，这和offset找第100001条节点的实现机制有本质区别。

这种做法在20W的数据量级下，经过测试查询性能可以提升43倍。

解法2

上面的做法基本只适用于遍历的简单场景，从而可以直接使用主键去查询。

但大部分场景下，业务的查询都是附带条件的，也就是说必须要用到辅助的索引二叉树。

前面说了，如果用非主键的索引去遍历，会导致两次对二叉树的查询操作：先查索引二叉树找到节点的主键，再查主键索引二叉树取具体数据。

此时如果想实现一种条件下的翻页效果，直观可能会这样写SQL：

select * from table where update_time < CURDATE() limit 100 offset 10000;

此时MySQL经历的就是先根据条件找到10100条符合条件的记录（经过两个二叉树的查询），然后再抛弃前10000条。

那这里可以利用子查询不会真正获取数据的特性，进行优化：

select * from table where id in (select id from table where update_time < CURDATE()) limit 100 offset 10000;

注意这里子查询是根据辅助索引去查的，而主查询只根据了主键去查。

在子查询中并不会真正去访问主键索引二叉树获取数据，所以免去了10000次无效查询。

在子查询获取到id后，再用IN查询去在主键索引二叉树上遍历数据。

这种做法虽然也要查询10000条无用的数据，但由于是直接使用主键索引，所以比直接查询limit offset的做法会快两倍左右。

解法3

用IN操作，对于量大的情况始终不太优雅，因此还可以考虑用JOIN替代IN，自己JOIN自己：

select * from table as t1 inner join (select id from table where update_time < CURDATE() order by update_time desc limit 100 offset 10000) as t2 using (id);

这种做法经过测试会比最原始的SQL快10倍。

这里还需要注意的是，MySQL的JOIN有一个优化点，即用小表做驱动表去驱动大表。

比如对于 t1 left join t2 的情况，就建议把记录数较小的表放在前面，前面的表示驱动表，会扫描t1所有记录然后再去t2查询。

如果t1有M条记录，t2 N条，使用t2的索引的情况下，时间复杂度是M * logN左右，因此M的影响，也即t1的记录数对时间影响更大。

不过这里由于使用的是INNER JOIN，MySQL对INNER JOIN会自动使用小表，因此问题不大，实测下来耗时也相差无几。

更多解法

其实可以选择的解法还有很多，比如从业务层面限制要访问的数据，比如分表，比如其他奇诡的索引用法。

此外，这里介绍的解法，也更多地针对MySQL默认使用的InnoDB引擎去做优化，在不同的数据库存储引擎下，可能会有其他更合适的解法。