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

7) 数据的分布: 如果数据在关联条件下是有偏向的（比如根据姓氏来关联人，但是很多人同姓），使用哈希关联将是一场灾难，因为哈希函数将创建分布不均匀的桶。
8) 如果希望连接由多个线程/进程执行有关更多信息，您可以阅读DB2，或 SQL 文档。
简单的例子
我们刚刚看到了3种类型的关联操作。现在，我们需要关联5个表来表示一个人的信息。一个人要可能有：
换个话说，我们需要用下面的查询快速得到答案
SELECT * from PERSON, MOBILES, MAILS,ADRESSES, BANK_ACCOUNTSWHEREPERSON.PERSON_ID = MOBILES.PERSON_IDAND PERSON.PERSON_ID = MAILS.PERSON_IDAND PERSON.PERSON_ID = ADRESSES.PERSON_IDAND PERSON.PERSON_ID = BANK_ACCOUNTS.PERSON_ID
作为查询优化器，我必须找到处理数据的最佳方法。但是有两个问题：
每次关联应该使用什么样类型？
我有3个可能的关联（哈希关联，合并关联，嵌套关联），有可能使用 0，1 或者 2个索引(更不用说有不同类型的索引)
我应该选择什么顺序来计算关联？
例如，下图显示了4个表上3个关联的可能不同情况
所以这是我觉得的可能性：
1) 我用暴力遍历的方式使用数据库的统计信息，我计算每个方案的成本并得到最好的方案，但这也太多中方案了吧。对于给定的关联顺序，每个关联有3个可能性: 哈希关联、合并关联、嵌套关联。所以会有 3^4 中可能性。确定关联的顺序是个二叉树排列问题，有会有 (2*4)!/(4+1)! 种可能的顺序。而本例这这个相当简单的问题，我最后会得到 3^4*(2*4)!/(4+1)! 种可能。抛开专业术语，那相当于 27,216 种可能性。如果给合并联接加上使用 0,1 或 2 个 B+树索引，可能性就变成了 210,000种。我忘了提到这个查询非常简单吗？
2) 我哭了，并退出这个任务这很诱人，但你也不得到你想要结果，毕竟我需要钱来支付账单。
3) 我只尝试几种计划并采取成本最低的计划。由于我不是超人，我无法计算每个计划的成本。相反，我可以任意选择所有可能计划的子集，计算其成本并为你提供该子集的最佳计划。
4）我使用智能规则来减少可能的计划数量下面有两种的规则： 1. 我可以使用“逻辑”规则来消除无用的可能性，但它们不会过滤很多方案。比如：内部关系要用循环嵌套关联一定要是最好的数据集 2. 我可以接受不寻找最好的方案并用更积极的规则减少大量的可能性。比如：如何关系很少，使用循环嵌套关联并永远不使用合并关联或者哈希关联在这个简单的例子中，我最终得到很多的可能性。但现实中的查询还会有其他关系运算符，像 OUTER JOIN, CROSS JOIN, GROUP BY, ORDER BY, , UNION, ,… 这意味着更多的可能性。那么，数据库是如何做到的呢？
动态规划、贪心算法和启发式算法
关系数据库尝试过我刚才说过的多种方法。大多数情况下，优化器找不到最佳解决方案，而是“好”解决方案对于小型查询，可以采用暴力遍历的方法。但是有一种方法可以避免不必要的计算，因此即使是中等查询也可以使用暴力方法。这叫为动态规划编程。
动态规划
它们用了相同的（A JOIN B）子树。所以，我们可以只计算这棵树一次，保存这树的城下，当看到这棵树的时候再次使用，而不是每次看到这棵树都重新计算一次。更正规地说，我们面对的是重复计算的问题。为了避免额外计算结果的部分，我们使用了记忆术。
使用了这个技术，不再是 (2*N)!/(N+1)! 的时间复杂度了，我们只有 3^N。在我们之前的例子中有4个连接，这意味着 336个关联顺序会降到 81 个。如果你有一个大的查询有 8 个关联（也不是很大），这意味着会从 57,657,600 降到 6561