共计 2972 个字符,预计需要花费 8 分钟才能阅读完成。
明确场景
要答复这个问题,咱们个别分几步来走:
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》中提到了,也一并列进去。
深层次灵魂提问
为什么 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.ph…
还带了修复计划:
https://bugs.mysql.com/file.p…
当然 mysql 有本人的设计理念和保持,可能当前也不会驳回。
而将阿里云、腾讯云这些称为家养 db,其实也只是调侃的说法。
实际上他们都遵循实用准则,是十分优良的团队,自研产品的决策灵活性自身也更高一些。
这倒不是非要分个孰优孰劣,大家搞清楚前因后果即可。
补丁剖析
尽管咱们曾经将前因后果弄得很分明,但置信还是会有同学好奇,下面的大佬做的补丁,到底是怎么的。牛哥和虎哥,也做了一些剖析。
外围因素就是在引擎层减少了这么一个函数,能够下推索引。
这个函数有几层,最外围的其实在这里:
其实就是 offset 判断,如果 offset 比当初的遍历偏移还大,就跳过。
Sql 层会调用引擎层这个函数,当然调用之前会有个判断。
很简单是吧,没事,咱们看注解:
其实就是限度了很多状况,比方 group by,having 这种推了也不顶用的,就不推了。
Review 一下
能够看到,看起来很简略的一个问题,其实牵涉到的常识很广:
首先工夫复杂度是多少?考查 B + 树结构;
Offset 为什么慢?考查对底层行为肯定水平的把握;
几种解决方案?考查技术视线和解决问题的能力;
深层次行为起因?考查 MySQL 分层架构,及对开源社区的关注。
如果你只是背八股文,而不去深刻摸索其中的原理,那面试官轻易问几个问题,就能看出你其实根底是不扎实的。
这里不是说八股文不好,而是不能感觉面试就是考八股文,这其实是一个很大的误区。