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

　　明确场景
　　要回答这个问题，我们一般分几步来走：
　　1.确认问题，对齐Sql语句；
　　2.解答问题本身，也就是时间复杂度分析；
　　3.针对本身提出这个场景，可能出现的性能瓶颈进行分析；
　　4.针对瓶颈，提出多种优化手段。
　　接下来我们就按照这个思路来一步步深入。
　　对齐Sql语句
　　通常而言，面试官抛出一个问题，不见得就是一个非常完善、非常准确的描述，他其实是希望你能提出问题，通过沟通对齐，这也是工作中必备的能力。
　　首先问面试官，目前表的结构大概是怎样，索引的建设，又是怎样的，假设通过沟通，我们得到如下简化过的表t_player：
　　字段名
　　类型
　　描述
　　id
　　bigint(20) unsigned
　　主键id
　　score
　　int(11) unsigned
　　分数
　　name
　　varchar(128)
　　姓名
　　只在score字段上建了二级索引，大小是从小到大。这里要找第k个，其实就是偏移k-1： select * from t_player order by  score desc offset k - 1 limit 1
　　时间复杂度分析
　　这个问题的核心就是查找语句的时间复杂度是多少？
　　这道题实际是有一定引导性的，故意说索引，就是想让你往树分支上引，我们都知道，走索引，按数值本身查找一个数据，那二级索引的时间复杂度，肯定是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 select score from t_player order by  score desc limit 20 --- 记录score为prev_score select score from t_player where  score < prev_score order by score  desc limit 20
　　使用这种模式，可以利用树索引直接找到目标，也绕过了无效回表问题，在Offset超过一万的情况下，性能通常都能提高两个量级以上。
　　当然，这种适合给分页做优化，如果回到我们题目本身来说，那查找第k大的数，就需要循环＂下一页＂下去，损耗反而更大。
　　2.硬碰硬
　　上面分析了，对无用数据还回表查询，导致大量随机IO，是性能的核心瓶颈，那我们对症下药，能否不回表呢？
　　当然可以，我们可以进行索引覆盖。
　　索引覆盖是说当二级索引查询的数据都在二级索引本身，比如索引Key或主键ID，那么就不必再去查聚簇索引。
　　那你可能会问，在我们的场景，还有其它需要查询的信息，比如名字，并不在二级索引上啊。
　　是的，但我们可以通过sql的拆分，来达到目的，思路如下： select * from t_player id in  (select id from t_player order by  score offset 10000 limit 1）
　　这句话是说，先从条件查询中，查找数据对应的数据库唯一id值，因为主键在辅助索引上就有，所以不用回归到聚簇索引的磁盘上拉取。
　　如此以来，offset部分均不需要去反查聚蔟索引，只有limit出来的10个主键id会去查询聚簇索引，这样只会1次IO。
　　在业务确实需要用分页的情况下，使用该方案可以大幅度提高性能，通常能满足性能要求。
　　有同学可能担心本身走B+树的双指针会是瓶颈，牛哥也做了测试：
　　一张500w的表，offset 10000，要是没索引覆盖，处理时间甚至可以达到十秒级，有了的话，能降低到十毫秒级，有质的飞跃。
　　ps:具体时耗和数据库性能等因素有关，以上数据只是参考。
　　3.预判边界值
　　这其实也是根据业务场景的做法，能通过业务预判边界，这种方式并不是通用解决方案，但因为《高性能MySQL》中提到了，也一并列出来。
　　深层次灵魂发问
　　为什么MySQL不直接丢掉无用数据，还要傻乎乎地回表？
　　也许你曾经听过一个词，叫索引下推，在MySQL5.6之后，MySQL通过索引下推提升了性能。
　　这个问题也类似，答案是Offset未曾下推！ 我们先review下查找流程：
　　1.存储引擎通过二级索引查找，获取主键值；
　　2.进行回表操作，将完整记录返回给上层；
　　3.上层判断是否需要该记录，需要则返回给客户端，不需要则跳过该记录；
　　4.存储引擎接着查找下一条；
　　5.重复第二步。
　　从流程其实我们能看出，存储引擎层是没有Offset信息的。
　　牛哥和咱们训练营导师虎哥也讨论过这个问题，虎哥的解释还是比较到位的：
　　MySQL不做的原因，无非两点：
　　1.限制场景太多，给多个引擎做有点得不偿失；
　　2.更核心的，分层设计理念，这件事本身是Sql层的，本就不该存储引擎做。
　　野生db
　　那我们现在来看看所谓的野生db的情况：
　　野生db1号：阿里云
　　野生db 2号：腾讯云
　　另外，腾讯云还描述了适用场景：
　　下推之后阿里云测试了性能，Q3即我们二级索引order by ... limit回表的场景，可以看到从25s降低到了329ms左右，相差75.82倍。
　　可以发现阿里腾讯两大云厂商MySQL自研版本都做了下推，那MySQL从技术上自然也能。
　　有大佬针对这个问题还给MySQL提了bug。 https://bugs.mysql.com/bug.php?id=109173
　　还带了修复方案：
　　https://bugs.mysql.com/file.php?id=31884&bug_id=109173
　　当然mysql有自己的设计理念和坚持，可能以后也不会采纳。
　　而将阿里云、腾讯云这些称为野生db，其实也只是调侃的说法。
　　实际上他们都遵循实用原则，是非常优秀的团队，自研产品的决策灵活性本身也更高一些。
　　这倒不是非要分个孰优孰劣，大家搞清楚前因后果即可。
　　补丁分析
　　虽然我们已经将前因后果弄得很清楚，但相信还是会有同学好奇，上面的大佬做的补丁，到底是怎样的。牛哥和虎哥，也做了一些分析。
　　核心要素就是在引擎层增加了这么一个函数，可以下推索引。
　　这个函数有几层，最核心的其实在这里：
　　其实就是offset判断，如果offset比现在的遍历偏移还大，就跳过。
　　Sql层会调用引擎层这个函数，当然调用之前会有个判断。
　　很复杂是吧，没事，咱们看注解：
　　其实就是限制了很多情况，比如group by，having这种推了也不顶用的，就不推了。
　　Review一下
　　可以看到，看起来很简单的一个问题，其实牵涉到的知识很广：
　　首先时间复杂度是多少？考察B+树结构；
　　Offset为什么慢？考察对底层行为一定程度的掌握；
　　几种解决方案？考察技术视野和解决问题的能力；
　　深层次行为原因？考察MySQL分层架构，及对开源社区的关注。
　　如果你只是背八股文，而不去深入探索其中的原理，那面试官随便问几个问题，就能看出你其实基础是不扎实的。
　　这里不是说八股文不好，而是不能觉得面试就是考八股文，这其实是一个很大的误区。