使用limit,offset分页场景时为什么会慢
从一个问题说起
五年前在腾讯的时候，发现分页场景下，mysql请求速度非常慢。数据量只有10w的情况下，selectxxfrom单机大概2，3秒。
我就问我师父为什么，他反问“索引场景，mysql中获得第n大的数，时间复杂度是多少？”
答案的追寻
确认场景
假设status上面有索引。select*fromtablewherestatus=xxlimit10offset10000。
会非常慢。数据量不大的情况就有几秒延迟。
小白作答
那时候非常有安全感，有啥事都有师父兜着，反正技术都是组里最差的，就瞎猜了个log(N)，心想找一个节点不就是log(N)。自然而然，师父让我自己去研究。
这一阶段，用了10分钟。
继续解答
仔细分析一下，会发现通过索引去找很别扭。因为你不知道前100个数在左子树和右子数的分布情况，所以其是无法利用二叉树的查找特性。
通过学习，了解到mysql的索引是b+树。
看了这个图，就豁然开朗了。可以直接通过叶子节点组成的链表，以o(n)的复杂度找到第100大的树。但是即使是o(n)，也不至于慢得令人发指，是否还有原因。
这一阶段，主要是通过网上查资料，断断续续用了10天。
系统学习
这里推荐两本书，一本《MySQL技术内幕InnoDB存储引擎》，通过他可以对InnoDB的实现机制，如mvcc，索引实现，文件存储会有更深理解。
第二本是《高性能MySQL》，这本书从着手使用层面，但讲得比较深入，而且提到了很多设计的思路。
两本书相结合，反复领会，mysql就勉强能登堂入室了。
这里有两个关键概念：
- 聚簇索引：包含主键索引和对应的实际数据，索引的叶子节点就是数据节点
- 辅助索引：可以理解为二级节点，其叶子节点还是索引节点，包含了主键id。
即使前10000个会扔掉，mysql也会通过二级索引上的主键id,去聚簇索引上查一遍数据，这可是10000次随机io，自然慢成哈士奇。
这里可能会提出疑问，为什么会有这种行为，这是和mysql的分层有关系，limitoffset只能作用于引擎层返回的结果集。换句话说，引擎层也很无辜，他并不知道这10000个是要扔掉的。
以下是mysql分层示意图，可以看到，引擎层和server层，实际是分开的。
直到此时，大概明白了慢的原因。这一阶段，用了一年。
触类旁通
此时工作已经3年了，也开始看一些源码。在看完etcd之后，看了些tidb的源码。无论哪种数据库，其实一条语句的查询，是由逻辑算子组成。
逻辑算子介绍
在写具体的优化规则之前，先简单介绍查询计划里面的一些逻辑算子。
- DataSource这个就是数据源，也就是表，select*fromt里面的t。
- Selection选择，例如selectxxxfromtwherexx=5里面的where过滤条件。
- Projection投影，selectcfromt里面的取c列是投影操作。
- Join连接，selectxxfromt1,t2wheret1.c=t2.c就是把t1t2两个表做Join。
选择，投影，连接（简称SPJ）是最基本的算子。其中Join有内连接，左外右外连接等多种连接方式。
selectbfromt1,t2wheret1.c=t2.candt1.a>5变成逻辑查询计划之后，t1t2对应的DataSource，负责将数据捞上来。
上面接个Join算子，将两个表的结果按t1.c=t2.c连接，再按t1.a>5做一个Selection过滤，最后将b列投影。
下图是未经优化的表示：
所以说不是mysql不想把limit,offset传递给引擎层，而是因为划分了逻辑算子，所以导致无法直到具体算子包含了多少符合条件的数据。
怎么解决
《高性能MySQL》提到了两种方案
方案一
根据业务实际需求，看能否替换为下一页，上一页的功能，特别在ios,android端，以前那种完全的分页是不常见的。
这里是说，把limit,offset，替换为>辅助索引（即搜索条件）id的方式。该id再调用时，需要返回给前端。
方案二
正面刚。这里介绍一个概念：索引覆盖：当辅助索引查询的数据，只有id和辅助索引本身，那么就不必再去查聚簇索引。
思路如下：selectxxx,xxxfromin(selectidfromtablewheresecond_index=xxxlimit10offset10000)这句话是说，先从条件查询中，查找数据对应的数据库唯一id值，因为主键在辅助索引上就有，所以不用回归到聚簇索引的磁盘去拉取。再通过这些已经被limit出来的10个主键id，去查询聚簇索引。这样只会十次随机io。
在业务确实需要用分页的情况下，使用该方案可以大幅度提高性能。通常能满足性能要求。
写在最后
非常感谢我师父在我毕业前三年的指导，给了我很多耐心。在节假日给我布置看书任务，在午休时候考察我学习的进展，通过提问的方式引导我去探索问题，在我从腾讯毕业后，每次见面也给我出了很多主意，传授授业解惑，无一没有做到极致。
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持毛票票。
声明：本文内容来源于网络，版权归原作者所有，内容由互联网用户自发贡献自行上传，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任。如果您发现有涉嫌版权的内容，欢迎发送邮件至：czq8825#qq.com（发邮件时，请将#更换为@）进行举报，并提供相关证据，一经查实，本站将立刻删除涉嫌侵权内容。