分页场景慢？MySQL 迷惑行为解读~
从一个问题说起
牛牛六年前刚工作的时候，发现分页场景下，当 offset 变大，MySQL 处理速度非常慢！具体 sql 如下：
下表所示为表 t_record 结构，为了简单起见，只列了我们将讨论的字段，其余字段省略。
其中 t_record 是要查询的数据表，表中一共有 50000 条记录，age 字段上有索引，且 age>10 的记录有 20000 条。
这条语句非常慢，基本达到了秒级延迟，在第二次请求有缓存之后，才变快。
在数据量这么少的情况下，走索引还这么慢，这完全不能接受，我就问我导师为什么，他反问“索引场景，MySQL 中获得第 n 大的数，时间复杂度是多少？”
答案的追寻
小白直觉作答
当时只知道 MySQL 索引使用的是树，瞎猜了个 O(logn)，心想二叉树找一个节点不就是 O(logn)么。自然而然，导师白了一眼，让我自己去研究。
继续解答
想来想去...只能从底层结构分析了，MySQL 的索引是 B+树。仔细想一下，就会发现通过索引去找很别扭。因为你不知道前 n 个数在其他子树的分布情况，也没有标记让你能快速选择去哪个子树寻找，我们无法利用 B+树分支过滤的查找特性。
这下我明白导师的用意了——offset n，就是从第 n 大的数开始找！第 n 大的数没法使用树分支查找，所以 offset，也不能！
回到我们一开始的问题：
通过二级索引 age，我们只能找到对应的起始节点，但无法通过树结构过滤掉 10000 个节点，再获取 10 个节点，因为我们无法知道某个子树下有多少数据，就无法通过分支进行排除。
那该怎么办呢？
我们来仔细看下 B+树的结构，它不光有常规树的分支结构，底部还有一个由叶子节点组成链表。
显而易见，最方便最快的方式，就是用树定位到起始位置，然后直接通过叶子节点组成的链表，以 O(n)的复杂度找到第 n 大的数据。
回到我们最初的问题，总结一下：问题的本质其实就是让 offset 找到第 n 大的数，再通过链表遍历，在数据量很大的情况下，确实会慢。
但是即使是 O(n)，也不至于仅有几万数据就慢得令人发指。
是不是还有其他影响因素？
系统学习
牛牛决定深入研究，带着问题去查找了很多资料。
这里推荐两本书，一本《MySQL 技术内幕 InnoDB 存储引擎》，通过它可以对 InnoDB 的底层机制，如 acid、mvcc、索引实现、文件存储，有更深的理解。
第二本是《高性能 MySQL》，这本书从使用层面着手，讲得比较深入，并提到了很多设计和优化的思路，对日常工作和学习都有很大的帮助。
两本书相结合，反复领会，MySQL 就差不多能登堂入室了。
针对我们的问题，这里介绍两个相关的概念：
聚簇索引：包含主键索引和对应的实际数据，索引的叶子节点就是数据节点；
辅助索引：也叫二级节点，其叶子节点还是索引节点，并没有完整的数据，仅包含了索引值本身和主键 id，用主键 id 反查聚蔟索引才能获取完整数据。
如图所示，offset 会先从二级索引的链表顺序找 10000 个节点。
注意，即使这 10000 个节点会被扔掉，MySQL 也会通过二级索引上的主键 id，去聚簇索引上查一遍数据，这可是 10000 次随机 IO，自然慢成哈士奇。
大家读到这里可能会提出疑问，为什么 MySQL 会有这种行为？
这和它的优化器有关系，也算是 MySQL 的一个大坑，时至今日，也没有优化。
问题的解决
针对分页性能问题，《高性能 MySQL》中提到了两种方案，让我们一起来看看：
方案一：产品上绕过
根据业务实际需求，看能否替换为上一页、下一页的功能，这样子就可以通过和上次返回数据进行比较，搭上树分支过滤的便车。
特别在 ios，android 端，以前那种完全的分页是不常见的。即转换为如下 sql，第一次 last_id 传 0 即可。
优点
1.能利用树的分支结构，过滤掉第 n 个数之前的数据集；
2.直接通过主键索引查找，省略了二级索引查找过程，性能会更高。
缺点
1.使用场景其实是受限制的。比如，如果是针对 age 字段有条件判断，再分页，那么使用主键 id 查找就不满足需求；
2.把主键 id 暴露出去了，这个本身不应该是业务层面关心的字段。
可以看到，该方案在我们的场景中，是不适用的。
因为我们还有 age 做过滤条件，此时用大于主键 id 的方式，虽然看起来变成顺序 IO 了，但由于是根据主键 id 排列来寻找，而不是根据需要的 age 索引，所以会导致 MySQL 去查更多的数据。虽然不符合我们案例的需求，但还是来看看优缺点：
方案二：正面刚
这里先介绍一个概念：
索引覆盖：当辅助索引查询的数据只有主键 id 和辅助索引本身，那么就不必再去查聚簇索引。
思路如下：
这句话是说，先从条件查询中，查找数据对应的数据库唯一 id 值，因为主键在辅助索引上就有，所以不用回归到聚簇索引的磁盘上拉取。
如此以来，offset 部分均不需要去反查聚蔟索引，只有 limit 出来的 10 个主键 id 会去查询聚簇索引，这样只会十次随机 IO。
在业务确实需要用分页的情况下，使用该方案可以大幅度提高性能。通常能满足性能要求。
优点
1.维持了分页需求，适用所有 limit offset 场景，大大减少随机 IO，提高了性能；
2.二级索引上，只查找 id，传输的数据包也变小。
缺点
二级索引上还是会走下面的链表来遍历，这部分时间复杂度还是 O(n)。
方案选型
如果产品本身的需求，是分上下页，且没用其他过滤条件，可以用方案一。
方案二更具有普适性，同时由于合理分表的大小，一般也就 500w，二级索引上 O(n)的查找损耗，通常也在可接受范围。
总结
从一个小问题，往下深究，不仅可以深入理解这个问题，在面试和工作中大放异彩，同时在探索的过程中，自身的知识储备也能得到拓展，是技术的一个提升捷径。祝大家工作顺利，牛牛码特！
推荐阅读
看完三件事
如果你觉得这篇内容对你还蛮有帮助，我想邀请你帮我三个小忙：
点赞，转发，有你们的 『点赞和评论』，才是我创造的动力。
关注公众号 『 Java 斗帝 』，不定期分享原创知识。
同时可以期待后续文章 ing🚀
还未添加个人签名 2020.09.07 加入
还未添加个人简介
评论