很清楚这个场景。要回答这个问题，我们一般分为几个步骤：1、确认问题，对齐Sql语句；2、自己回答问题，即分析时间复杂度；3、分析本场景可能出现的性能瓶颈；4.针对瓶颈提出各种优化方法。接下来，我们就按照这个思路一步一步来。AligningSqlstatements一般而言，面试官提出的一个问题可能不是一个非常完整和准确的描述。他其实是希望你能提出问题，通过沟通来对齐。这也是工作中必备的能力。先问面试官，当前表的结构是什么，索引是怎么构建的？假设通过通信，我们得到如下简化表t_player：只在score字段上建立了二级索引，size从小到小。大的。这里要找到第k个其实就是k-1的偏移量：select*fromt_playerorder按时间复杂度分析这个问题的核心是查找语句的时间复杂度是多少？这个问题其实有点启发意义。索引的目的是让你通向树枝。我们都知道，如果去索引，根据值本身去查找一个数据，那么二级索引的时间复杂度肯定是O(logN)。但是这道题不一样，是求第k个，比如第100个，我们其实并不知道树的分支结构是什么，也就是说不知道左边有多少个节点子树以及右子树节点中有多少个。此外，我们无法确定走哪条路，树的分支结构也不可行。所以这里其实是考察对B+树的理解。除了B+树的分支，最底层还有一个双向链表。直接查询双链表速度更快。读起来时间复杂O(N)。让我们反过来想一想。来问你，只有真正了解它的作用，你才能快速回答。这就是结局？当然不是，这只是一个开始。下一步，面试官肯定会问你这个操作的性能如何。当然，你也可以主动说说。offset慢问题如果offset大于10000，数据查询会很慢。为什么慢？一般答案是因为遍历，时间复杂度是O(N)。但实际上，如果你测试一下，你会发现这个语句会慢的离谱，这绝对不是所谓的遍历造成的。更深层次的原因是，前10000条不需要的数据，MySQL每次都要回表查，导致10000次随机IO，当然慢。优化方案如果有开发经验，很容易想到从业务形态上进行优化，这里就不啰嗦了。这种场景通常有三种解决方案。1、业务中，把limit和offset改成next，也就是把pagex改成下一页，这样就可以通过树枝搜索了。比如百度的搜索界面就是一个典型的子页面。但是现在移动互联网时代，上一页、下一页等翻页逻辑用的比较多，微博和抖音就用到了这样的逻辑。---将分数记录为prev_score并使用此模式。可以使用树索引直接找到目标，也可以绕过返回无效表的问题。当Offset超过10000时，性能通常可以提升两个数量级以上。当然，这适合优化分页。如果回到我们的话题本身，那么要找到第k大的数，就需要循环遍历“下一页”，损失会更大。2.头对头上面分析过，回表查询无用的数据，导致大量的随机IO，是性能的核心瓶颈，那我们就可以对症下药，能不能不回表？当然，我们可以进行索引覆盖。索引覆盖是指当二级索引查询到的数据本身就在二级索引中，比如索引键或者主键ID，那么就不需要去查找聚簇索引了。那么你可能会问，在我们的场景中，还有其他的信息需要查询，比如姓名，这些信息是不在二级索引上的。可以，但是我们可以通过拆分sql来达到目的。思路如下：select*fromt_playeridin这句话的意思是先从条件查询中查找数据对应的数据库的唯一id值，因为主键在辅助索引上存在，所以不需要返回聚集索引的磁盘来拉取它。这样offset部分就不需要去检查聚集索引了。只有限制中的10个主键ID将用于查询聚簇索引，因此只会执行一次IO。在业务确实需要使用分页的情况下，采用这种方案可以大大提升性能，通常可以满足性能需求。可能有同学会担心B+树的双指针会成为瓶颈。牛哥也做过测试：一个500w的表，offset10000，如果没有索引覆盖，处理时间甚至可以达到十秒。如果你有它，你可以将它减少到十毫秒，这是一个质的飞跃。ps：具体耗时与数据库性能等因素有关，以上数据仅供参考。3.预测边界值这个其实是基于业务场景的实践，可以通过业务来预测边界。这个方法不是通用的解决方法，但是因为在《高性能MySQL》中提到了，所以也列出来了。灵魂深处追问，为什么MySQL不把没用的数据直接扔掉，而是傻傻的把表还回去？也许你听说过一个词叫索引下推。MySQL5.6之后，MySQL通过索引下推来提升性能。这道题也类似，答案是Offset没有被推下来！先回顾一下查找过程：1.存储引擎通过二级索引查找得到主键值；2、执行回表操作，将完整的记录返回给上层；3、上层判断是否需要这条记录，如果需要则返回给客户结束，如果不需要则跳过这条记录；4、存储引擎接着搜索下一个；5.重复第二步。从流程中我们其实可以看出，存储引擎层是没有Offset信息的。牛大哥和我们的训练营导师胡大哥也讨论过这个问题。胡大哥解释的很到位：MySQL不做的原因无外乎两点：1、受限场景太多，多引擎做不划算；2..更核心的，分层设计理念，这件事本身属于Sql层，不应该由存储引擎去做。Wilddb下面我们来看看所谓的wilddb：WilddbNo.1：阿里云WilddbNo.2：腾讯云此外，腾讯云还描述了适用场景：下推后，阿里云测试了性能方面，Q3是我们在二级索引orderby...limit返回表的场景中，可以看到时间从25s减少到329ms左右，相差75.82倍。可以发现阿里和腾讯两大云厂商MySQL的自研版本已经下推，技术上MySQL自然可以做到。一些大佬针对这个问题给MySQL提了bug。https://bugs.mysql.com/bug.ph...还带来了修复方案：https://bugs.mysql.com/file.p...当然mysql有自己的设计理念和坚持，也许以后也不会采用。称阿里云和腾讯云为野db，其实只是一个笑话。事实上，他们都遵循务实的原则，是一个非常优秀的团队。自主研发产品的决策灵活性也更高。不必分清好坏，大家弄清楚前因后果就够了。补丁分析虽然我们已经把前因后果说的很清楚了，但是相信有同学还是会很好奇上面大佬们打的补丁是什么样子的。牛哥和虎哥也做了一些分析。核心要素是在引擎层添加这样一个功能，可以下推索引。这个函数有好几层，其实核心就在这里：其实就是offset的判断。如果偏移量大于当前遍历偏移量，则跳过它。Sql层会调用引擎层的函数，调用前当然会有判断。这很复杂，对吧？没关系。我们看注解：其实限制了很多情况，比如groupby，having，push了也没用，所以我们不push。复习一下就会发现，看似简单的一道题，其实涉及的知识非常多：首先，什么是时间复杂度？考察B+树结构；为什么Offset很慢？调查对潜在行为的一定程度的掌握；几种解决方案？考察技术眼光和解决问题的能力；深层次的行为原因？考察MySQL分层架构，关注开源社区。如果你只是死记硬背八股文，没有深入探究其中的原理，那么面试官随便问几个问题就能看出你基础不扎实。这并不是说八股文不好，而是大家不要认为面试只是八股文的考试。这其实是一个很大的误会。
