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

SELECT TYPE_PERSON.CATEGORY from PERSON ,TYPE_PERSONWHERE PERSON.AGE = TYPE_PERSON.AGE
上的索引将用于与关联，但由于你没有询问表的信息，因此不会通过行ID访问表。虽然它在少量访问的时候非常好用，但此操作的真正问题是磁盘I/O 。如果你按行ID进行过多访问，则数据库可能会选择完整扫描。
其他访问方式
我没有介绍所有访问路径。如果您想了解更多信息，可以阅读文档。其他数据库的名称可能不同，但背后的概念是相同的。
JOIN 操作符
所以，我们知道如何获取我们的数据，让我们来 JOIN 下他们吧！我将介绍3个常见的关联运算符：合并关联(Merge Join)，哈希关联(Hash Join) 和嵌套循环关联( Loop Join) 但在此之前，我需要引入新的词汇：内部联系(inner )和外部联系(outer ) 。联系可以是：
当你正在关联两个联系时，关联算法会有两种不同方式管理这两种联系。在本文的剩余部分，我会假设：
举个栗子，A JOIN B 就是 A 和 B 之间的关联，而 A 就是外部联系，B就是内部联系。大多数时候，A JOIN B 的成本和 B JOIN A 的成本是不一样的在这部分，我也会假设外部联系有 N 个元素，内部关系有 M 个元素。请记得，真正的优化器会通过信息统计知道 N 和 M 的值。注意：N 和 M 的关系是基数()
嵌套循环关联
嵌套循环关联是最简单的

文章插图
这是是它的思想：
下面是伪代码：

nested_loop_join(array outer, array inner)for each row a in outerfor each row b in innerif (match_join_condition(a,b))write_result_in_output(a,b)end ifend forend for

由于它是双重迭代，时间复杂度为O(N * M)
就磁盘 I/O 而言, 外部关系中(N行)要找每行的(对应关系)，都需要内部关系中循环 M 遍。所以这算法需要从磁盘中读取 N + N*M 次。但是，如果内部关系是足够小的，你可以把内部关系放到内存中，那么你只需要读取磁盘 N+M 次了(M的数据写到内存) 。这种修改，内部联系一定是最小的，因为这才能更好放进内存
对于时间复杂度而言，没有区别，但对磁盘I/O来讲，上面那种方式更好。两条数据建立联系都只需读一次磁盘。
当然，内部关联可以被索引代替，这会对磁盘 I/O 更好
由于这个算法是很简单的，如果内部关联太大以致于不易放进内存，这是另一个对磁盘更友好的版本。构思如下：
【五[译]数据库是如何工作查询管理器】下载是可能的算法

//改进版本以减少磁盘I / O.nested_loop_join_v2(file outer, file inner)for each bunch ba in outer// ba 现在在内存中了for each bunch bb in inner // bb 现在在内存中了for each row a in bafor each row b in bbif (match_join_condition(a,b))write_result_in_output(a,b)end ifend forend forend forend for

使用此版本时，时间复杂度保持不变，但磁盘访问次数减少：
注意：每个磁盘访问都会采集比以前算法更多的数据，但这并不重要，因为它们是顺序访问（机械磁盘的真正问题是获取第一个数据的时间）。
哈希关联
哈希关联的思想是：
1) 从内部关联中获取所有元素
2) 创建内存哈希表
3) 逐一获取外部关系中的所有元素
4) 计算哈希表的每个元素的哈希码(通过哈希表的哈希函数)，用于寻找对应的内部联系桶()
5) 查看桶中的元素是否和外部表的元素匹配对于时间复杂度来讲，我需要假设一些东西去简化问题：
所有总共时间复杂度：(M/X) * N + 创建哈希表的成本(M) + 哈希函数的成本 * N。如果哈希函数创建了哈希桶的大小足够小(size小，桶数更多，X越大)，那么复杂度就是 O(M+N)? 这是哈希连接的另一个版本，更节省内存但对磁盘 I/O不友好，这次：