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

每天10分钟，用去食堂吃饭的时间解决一个知识点。

优化器

今天的内容相对来说清汤寡水一点，就梳理下优化器（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表上也有索引且有个选择操作的话，行数会大大减少。使用索引会比块嵌套要快得多得多。

好，今天就到这里。