五 [译]数据库是如何工作查询管理器( 六 ) _关联

对于计算机科学的 GEEKS 。这里有个算法，是在我曾经介绍给你正式课程找到的。我不会去解释这个算法，所以只有你已经明白动态规划编程或者你算法很好（你已经被警告过了）时才去读它：
procedure findbestplan(S)if (bestplan[S].cost infinite)return bestplan[S]// else bestplan[S] has not been computed earlier, compute it nowif (S contains only 1 relation)set bestplan[S].plan and bestplan[S].cost based on the best wayof accessing S/* Using selections on S and indices on S */else for each non-empty subset S1 of S such that S1 != SP1= findbestplan(S1)P2= findbestplan(S - S1)A = best algorithm for joining results of P1 and P2cost = P1.cost + P2.cost + cost of Aif cost < bestplan[S].costbestplan[S].cost = costbestplan[S].plan = “execute P1.plan; execute P2.plan;join results of P1 and P2 using A”return bestplan[S]
对于大型查询你仍然可以用动态规划处理，但是还得要用额外的规则（或启发式算法）来消除可能性
贪婪算法
但对一个大型的查询或者要快速得到答案(但查询速度不太快)，就会有使用另一种类型的算法，叫贪婪算法。
想法是通过一个规则（或者启发）以增量的方式构建查询计划。使用这个规则。贪婪算法能每次每步地找到问题的最好解决方案。算法从一个关联开始查询计划，然后每一步，算法会使用通过的规制把新的关联添加到新的查询计划
我们举个简单的例子吧。假设我们有个 5张表(A,B,C,D和E) 和 4次关联。为了简化问题，我们用可能会用到嵌套关联。现在使用规则是 “用最小成本关联”
我们是从A开始的，我们用同样的算法应用到 B 上，然后 C ,然后 D，然后 E 。我们可以保持这个计算是最少成本的。
顺便说一下，这个算法的名字叫最近邻居法
我不会详细介绍，但上面的问题(可能性很多的问题) 通过良好的建模和在复杂度是 N*log(N) 的排序就能很容易地解决。而这个算法的成本在 O(N*log(N)) 。而完全动态规划的版本要用 O(3^N)。如果是有20个连接的大查询，则意味着26 VS 3,486,784,401，这是一个巨大的差异！
这算法的问题是，我们假设了：找到2个表的最佳关联，保存这个关联，下个新关联加进来，也会是最佳的成本，但：
为了改善这情况，您可以基于不同的规则运行多个贪婪算法并保持最佳计划。、
其他算法
[如果你已经厌倦了算法，请跳到下一部分，这里说的对于文章的其余部分并不重要]
寻找最好的可能性计划对于计算机科学的研究者来讲是一个活跃的话题。他们经常为特定的问题/模式尝试寻找更好的的解决方案。例如：
还研究了其他算法来替换大型查询的动态规划。贪婪算法属于称为启发式算法的大家族。贪心算法遵循规则（或启发式），保留在上一步找到的解决方案并将它追加到当前步骤的解决方案中。一些算法遵循规则并逐步应用(apply),蛋不用总是保留上一步的最佳解决方案。他们统称启发式算法。
比如，遗传算法遵循规则，但最后一步的最佳解决方案通常不会保留：
循环次数越多，计划就越好。这是魔术？
不，这是自然法则：适者生存！
实现了遗传算法，但我并没有知道它会不会默认使用这种算法的。
数据库中还使用了其它启发式算法，像『模拟退火算法（）』、『交互式改良算法（）』、『双阶段优化算法（Two-Phase ）』…..不过，我不知道这些算法现在是否在企业级数据库应用了，还是只是用于研究型数据库。
如果想了解更多，你可以读这篇文章，它还介绍更多可能用到的算法《数据库查询优化中关联排序问题的算法综述》