如果再有人问你数据库的原理，把这篇文章给他(11) _数据库

按什么顺序执行联接？
比如，下图显示了针对 4 个表仅仅 3 次联接，可能采用的执行计划：

文章插图

那么下面就是我可能采取的方法：

1) 采取粗暴的方式
用数据库统计，计算每种可能的执行计划的成本，保留最佳方案。但是，会有很多可能性。对于一个给定顺序的联接操作，每个联接有三种可能性：哈希、合并、嵌套，那么总共就有 3^4 种可能性。确定联接的顺序是个二叉树的排列问题，会有 (2*4)!/(4+1)! 种可能的顺序。对本例这个相当简化了的问题，我最后会得到 3^4*(2*4)!/(4+1)! 种可能。
抛开专业术语，那相当于 27,216 种可能性。如果给合并联接加上使用 0,1 或 2 个 B+树索引，可能性就变成了 210,000种。我是不是告诉过你这个查询其实非常简单吗？

2) 我大叫一声辞了这份工作
很有诱惑力，但是这样一来，你不会的到查询结果，而我需要钱来付账单。

3) 我只尝试几种执行计划，挑一个成本最低的。
由于不是超人，我不能算出所有计划的成本。相反，我可以武断地从全部可能的计划中选择一个子集，计算它们的成本，把最佳的计划给你。

4) 我用聪明的规则来降低可能性的数量
有两种规则：
我可以用『逻辑』规则，它能去除无用的可能性，但是无法过滤大量的可能性。比如：『嵌套联接的内关系必须是最小的数据集』。
我接受现实，不去找最佳方案，用更激进的规则来大大降低可能性的数量。比如：『如果一个关系很小，使用嵌套循环联接，绝不使用合并或哈希联接。』

在这个简单的例子中，我最后得到很多可能性。但现实世界的查询还会有其他关系运算符，像 OUTER JOIN, CROSS JOIN, GROUP BY, ORDER BY, PROJECTION, UNION, INTERSECT, DISTINCT … 这意味着更多的可能性。
那么，数据库是如何处理的呢？
动态编程，贪婪算法和启发式算法
关系型数据库会尝试我刚刚提到的多种方法，优化器真正的工作是在有限时间里找到一个好的解决方案。
多数时候，优化器找到的不是最佳的方案，而是一个『不错』的
对于小规模的查询，采取粗暴的方式是有可能的。但是为了让中等规模的查询也能采取粗暴的方式，我们有办法避免不必要的计算，这就是动态编程。
动态编程
这几个字背后的理念是，很多执行计划是非常相似的。看看下图这几种计划：

文章插图

它们都有相同的子树（A JOIN B），所以，不必在每个计划中计算这个子树的成本，计算一次，保存结果，当再遇到这个子树时重用。用更正规的说法，我们面对的是个重叠问题。为了避免对部分结果的重复计算，我们使用记忆法。
对于计算机极客，下面是我在先前给你的教程里找到的一个算法。我不提供解释，所以仅在你已经了解动态编程或者精通算法的情况下阅读（我提醒过你哦）：
C

文章插图

针对大规模查询，你也可以用动态编程方法，但是要附加额外的规则（或者称为启发式算法）来减少可能性。

如果我们仅分析一个特定类型的计划（例如左深树 left-deep tree，参考)，我们得到 n*2^n 而不是 3^n 。

文章插图

如果我们加上逻辑规则来避免一些模式的计划（像『如果一个表有针对指定谓词的索引，就不要对表尝试合并联接，要对索引』），就会在不给最佳方案造成过多伤害的前提下，减少可能性的数量。
如果我们在流程里增加规则（像『联接运算先于其他所有的关系运算』），也能减少大量的可能性。
……

贪婪算法
但是，优化器面对一个非常大的查询，或者为了尽快找到答案（然而查询速度就快不起来了），会应用另一种算法，叫贪婪算法。
原理是按照一个规则（或启发）以渐进的方式制定查询计划。在这个规则下，贪婪算法逐步寻找最佳算法，先处理一条JOIN，接着每一步按照同样规则加一条新的JOIN 。
我们来看个简单的例子。比如一个针对5张表（A,B,C,D,E）4次JOIN 的查询，为了简化我们把嵌套JOIN作为可能的联接方式，按照『使用最低成本的联接』规则。