无效回表谁的锅？存储引擎：这事儿不赖我

作者：小小怪下士

2022-12-21
湖南
本文字数：2761 字
阅读完需：约 9 分钟

明确场景

要回答这个问题，我们一般分几步来走：

1.确认问题，对齐 Sql 语句；

2.解答问题本身，也就是时间复杂度分析；

3.针对本身提出这个场景，可能出现的性能瓶颈进行分析；

4.针对瓶颈，提出多种优化手段。

接下来我们就按照这个思路来一步步深入。

对齐 Sql 语句

通常而言，面试官抛出一个问题，不见得就是一个非常完善、非常准确的描述，他其实是希望你能提出问题，通过沟通对齐，这也是工作中必备的能力。

首先问面试官，目前表的结构大概是怎样，索引的建设，又是怎样的，假设通过沟通，我们得到如下简化过的表 t_player：

只在 score 字段上建了二级索引，大小是从小到大。这里要找第 k 个，其实就是偏移 k-1：

select * from t_player order by

复制代码

时间复杂度分析

这个问题的核心就是查找语句的时间复杂度是多少？

这道题实际是有一定引导性的，故意说索引，就是想让你往树分支上引，我们都知道，走索引，按数值本身查找一个数据，那二级索引的时间复杂度，肯定是 O(logN)。

但这题不一样，是找第 k 个，比如第 100 个，我们其实是不知道树的分支结构具体是怎样的，也就是说我们不知道左子树有多少个节点，右子树有多少个节点。

进一步而言，我们没法确定走哪条路，树的分支结构不可行。

所以这里其实是考察 B+树的理解，B+树除了分支，底层还有一个双链表，直接走双链表查询，反而是更快的了。

时间复杂读 O(N)，我们反过来想，其实这道题就是考你 B+树数据结构，如果直接问你 B+树结构，大多数有准备的同学，都能回答清楚，但是通过一个实际问题来问你，只有真正理解其作用，才能快速答出。

这就完了吗？当然没有，这只是一个起手式，下一步，面试官肯定会问你这个操作的性能如何，当然你也可以主动谈起。

offet 慢问题

如果 offset 大于 10000，这个数据查询就会非常的慢。为什么会慢呢，一般都会答因为遍历，时间复杂度是 O(N)。

但实际如果你测试一下，你会发现这条语句会慢得离谱，这绝不是所谓遍历能导致的。

更深层次的原因在于，对于前 10000 个不需要的数据，MySQL 每次也要回表去查找，这就导致了 10000 次随机 IO，当然慢成狗。

优化方案

如果有开发经验的同学，会很容易想到从业务形态上去优化，这里就不卖关子了，这种场景通常有三种解决方案。

1.业务上绕过

将 limit、offset，改为 next，也就是将第 x 页，改为下一页，这样就

可以通过树分支查找。

举个例子，百度的搜索界面，就是典型的分页面。

而现在移动互联网时代，用得更多的就是上一页、下一页这样的翻页逻辑，微博、抖音都是这样的逻辑。

--- 记录score为prev_score

复制代码

使用这种模式，可以利用树索引直接找到目标，也绕过了无效回表问题，在 Offset 超过一万的情况下，性能通常都能提高两个量级以上。

当然，这种适合给分页做优化，如果回到我们题目本身来说，那查找第 k 大的数，就需要循环“下一页”下去，损耗反而更大。

2.硬碰硬

上面分析了，对无用数据还回表查询，导致大量随机 IO，是性能的核心瓶颈，那我们对症下药，能否不回表呢？

当然可以，我们可以进行索引覆盖。

索引覆盖是说当二级索引查询的数据都在二级索引本身，比如索引 Key 或主键 ID，那么就不必再去查聚簇索引。

那你可能会问，在我们的场景，还有其它需要查询的信息，比如名字，并不在二级索引上啊。

是的，但我们可以通过 sql 的拆分，来达到目的，思路如下：

select * from t_player id in

复制代码

这句话是说，先从条件查询中，查找数据对应的数据库唯一 id 值，因为主键在辅助索引上就有，所以不用回归到聚簇索引的磁盘上拉取。

如此以来，offset 部分均不需要去反查聚蔟索引，只有 limit 出来的 10 个主键 id 会去查询聚簇索引，这样只会 1 次 IO。在业务确实需要用分页的情况下，使用该方案可以大幅度提高性能，通常能满足性能要求。有同学可能担心本身走 B+树的双指针会是瓶颈，牛哥也做了测试：一张 500w 的表，offset 10000，要是没索引覆盖，处理时间甚至可以达到十秒级，有了的话，能降低到十毫秒级，有质的飞跃。ps:具体时耗和数据库性能等因素有关，以上数据只是参考。

3.预判边界值

这其实也是根据业务场景的做法，能通过业务预判边界，这种方式并不是通用解决方案，但因为《高性能 MySQL》中提到了，也一并列出来。