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

直接从 5 个表里选一个开始（比如 A）
计算每一个与 A 的联接（A 作为内关系或外关系）
发现 “A JOIN B” 成本最低
计算每一个与 “A JOIN B” 的结果联接的成本（“A JOIN B” 作为内关系或外关系）
发现 “(A JOIN B) JOIN C” 成本最低
计算每一个与 “(A JOIN B) JOIN C” 的结果联接的成本 ……
最后确定执行计划 “( ( (A JOIN B) JOIN C) JOIN D ) JOIN E )”

因为我们是武断地从表 A 开始，我们可以把同样的算法用在 B，然后 C，然后 D, 然后 E 。最后保留成本最低的执行计划。
顺便说一句，这个算法有个名字，叫『最近邻居算法』。
抛开细节不谈，只需一个良好的模型和一个 N*log(N) 复杂度的排序，问题就轻松解决了。这个算法的复杂度是 O(N*log(N))，对比一下完全动态编程的 O(3^N) 。如果你有个20个联接的大型查询，这意味着 26 vs 3,486,784,401，天壤之别！
这个算法的问题是，我们做的假设是：找到 2 个表的最佳联接方法，保留这个联接结果，再联接下一个表，就能得到最低的成本。但是：

即使在 A, B, C 之间，A JOIN B 可得最低成本
(A JOIN C) JOIN B 也许比 (A JOIN B) JOIN C 更好。

为了改善这一状况，你可以多次使用基于不同规则的贪婪算法，并保留最佳的执行计划。
其他算法
[ 如果你已经受够了算法话题，就直接跳到下一部分。这部分对文章余下的内容不重要。]【我也很想把这段跳过去 -_- 】
很多计算机科学研究者热衷于寻找最佳的执行计划，他们经常为特定问题或模式探寻更好的解决方案，比如：

如果查询是星型联接（一种多联接查询），某些数据库使用一种特定的算法。
如果查询是并行的，某些数据库使用一种特定的算法。……

其他算法也在研究之中，就是为了替换在大型查询中的动态编程算法。贪婪算法属于一个叫做启发式算法的大家族，它根据一条规则（或启发），保存上一步找到的方法，『附加』到当前步骤来进一步搜寻解决方法。有些算法根据特定规则，一步步的应用规则但不总是保留上一步找到的最佳方法。它们统称启发式算法。
比如，基因算法就是一种：

一个方法代表一种可能的完整查询计划
每一步保留了 P 个方法（即计划），而不是一个。
0) P 个计划随机创建
1) 成本最低的计划才会保留
2) 这些最佳计划混合在一起产生 P 个新的计划
3) 一些新的计划被随机改写
4) 1，2，3步重复 T 次
5) 然后在最后一次循环，从 P 个计划里得到最佳计划。

循环次数越多，计划就越好。
这是魔术？不，这是自然法则：适者生存！
PostgreSQL 实现了基因算法，但我并没有发现它是不是默认使用这种算法的。
数据库中还使用了其它启发式算法，像『模拟退火算法（Simulated Annealing）』、『交互式改良算法（Iterative Improvement）』、『双阶段优化算法（Two-Phase Optimization）』…..不过，我不知道这些算法当前是否在企业级数据库应用了，还是仅仅用在研究型数据库。
如果想进一步了解，这篇研究文章介绍两个更多可能的算法《数据库查询优化中联接排序问题的算法综述》，你可以去阅读一下。
真实的优化器
[ 这段不重要，可以跳过 ]
然而，所有上述罗里罗嗦的都非常理论化，我是个开发者而不是研究者，我喜欢具体的例子。
我们来看看 SQLite 优化器是怎么工作的。这是个轻量化数据库，它使用一种简单优化器，基于带有附加规则的贪婪算法，来限制可能性的数量。