10分钟梳理关系数据库基础知识 五:查询优化与连接算法

更多腾讯海量技术文章,请关注云加社区:https://cloud.tencent.com/developer

作者:刁寿钧

优化器

今天的内容相对来说清汤寡水一点,就梳理下优化器(optimizer)的内容。没什么复杂的。

数据库拿到我们给的SQL后,会解析成一棵语法树。而优化器做的事情,就是应用关系代数的知识,找出等价的多种计算路径(即对这棵树进行数学上等价的变换)。这个过程就是我们标题中的查询优化。

那么要衡量不同方案的好坏,就需要我们设计一个代价的评价标准,这就是代价模型。而优化的思路可以分基于代价和基于规则两种。

基于代价需要我们掌握数据库中的统计信息,比如表中的记录数,记录的大小,某个字段中不同取值的数目(即选择性的高低)等。MySQL8.0中会加入直方图。

基于规则就是变换执行计划时,有一些启发式规则。比如尽早执行选择操作,尽早执行投影操作,避免笛卡尔积等。指导思想就是尽早的缩减规模。

好,这一块基本上就这些要点了。我感觉抓住指导思想就显得很清晰,当然去细究细节的话也会很有意思,比如MySQL的代价模型是怎么算的,我以前听姜承尧说他觉得MySQL 5.7的代价模型有个bug,这个有兴趣可以一起看看源代码。

连接

顺便复习下做等值JOIN时不同的连接方式与代价,通过粗略的估算给大家一个直观的认识。

假设我们有s和t两张表,现在要做JOIN。s表的记录数设为5000,占据的块数设为100;t表的记录数设为10000,占据的块数设为400。

嵌套循环连接

就是最简单的,以一张表的每一行记录,与另一张表的每一行记录比较。直接来两层for循环。我们来估算下代价。

若从s表的每行记录出发,那么最坏情况下,块传输次数是5000×400+100=2000100,搜索次数是5000+100=5100。

若从t表的每行记录出发,那么最坏情况下,块传输次数是10000×100+400=1000400,搜索次数是10000+400=10400。

块嵌套循环连接

一个小小的优化思路是,我每次以块的方式处理关系,这样不就可以减少块读写次数了么。

若从s表的每块出发,最坏情况下,块传输次数是100×400+100=40100,搜索次数是2×100=200。与前面相比,思路上小小的变化造就了性能上大大的提升。

索引嵌套循环连接

如果连接的字段上有B+树索引,设每个节点有20个索引项,t表记录数为10000,那么树的高度就是4,回表假设再加一次磁盘IO,此时访问次数为100+5000×5=25100,每次访问都有一次搜索和一次块传输。咦,怎么用了索引反而代价更高了?大家注意下,这里只说了t表上有索引,如果s表上也有索引且有个选择操作的话,行数会大大减少。使用索引会比块嵌套要快得多得多。

好,今天就到这里。

  • 发表于:
  • 原文链接:http://kuaibao.qq.com/s/20180116A0FE7X00?refer=cp_1026

同媒体快讯

相关快讯

扫码关注云+社区