其它路径
我没有列举所有的存取路径，如果你感兴趣可以读一读 Oracle文档 。其它数据库里也许叫法不同但背后的概念是一样的 。
联接运算符
那么，我们知道如何获取数据了，那现在就把它们联接起来！
我要展现的是3个个常用联接运算符：合并联接（Merge join），哈希联接（Hash Join）和嵌套循环联接（Nested Loop Join） 。但是在此之前，我需要引入新词汇了：内关系和外关系（ inner relation and outer relation） 【译者注： “内关系和外关系” 这个说法来源不明，跟查询的“内联接（INNER JOIN） 、外联接（OUTER JOIN） ” 不是一个概念。只查到百度百科词条：关系数据库 里提到“每个表格（有时被称为一个关系）……”。其他参考链接 “Merge Join” “Hash Join” “Nested Loop Join”】。一个关系可以是：
- 一个表
- 一个索引
- 上一个运算的中间结果（比如上一个联接运算的结果）
- 外关系是左侧数据集
- 内关系是右侧数据集
多数情况下，A JOIN B 的成本跟 B JOIN A 的成本是不同的 。
在这一部分，我还将假定外关系有 N 个元素，内关系有 M 个元素 。要记住，真实的优化器通过统计知道 N 和 M 的值 。
注：N 和 M 是关系的基数 。
嵌套循环联接
嵌套循环联接是最简单的 。
文章插图
道理如下：
- 针对外关系的每一行
- 查看内关系里的所有行来寻找匹配的行
C
文章插图
由于这是个双迭代，时间复杂度是 O(N*M) 。
在磁盘 I/O 方面，针对 N 行外关系的每一行，内部循环需要从内关系读取 M 行 。这个算法需要从磁盘读取 N+ N*M 行 。但是，如果内关系足够小，你可以把它读入内存，那么就只剩下 M + N 次读取 。这样修改之后，内关系必须是最小的，因为它有更大机会装入内存 。
在CPU成本方面没有什么区别，但是在磁盘 I/O 方面，最好最好的，是每个关系只读取一次 。
当然，内关系可以由索引代替，对磁盘 I/O 更有利 。
由于这个算法非常简单，下面这个版本在内关系太大无法装入内存时，对磁盘 I/O 更加有利 。道理如下：
- 为了避免逐行读取两个关系，
- 你可以成簇读取，把（两个关系里读到的）两簇数据行保存在内存里，
- 比较两簇数据，保留匹配的，
- 然后从磁盘加载新的数据簇来继续比较
- 直到加载了所有数据 。
C
文章插图
使用这个版本，时间复杂度没有变化，但是磁盘访问降低了：
- 用前一个版本，算法需要 N + N*M 次访问（每次访问读取一行） 。
- 用新版本，磁盘访问变为 外关系的数据簇数量 + 外关系的数据簇数量 * 内关系的数据簇数量 。
- 增加数据簇的尺寸，可以降低磁盘访问 。
哈希联接更复杂，不过在很多场合比嵌套循环联接成本低 。
文章插图
哈希联接的道理是：
- 1) 读取内关系的所有元素
- 2) 在内存里建一个哈希表
- 3) 逐条读取外关系的所有元素
- 4) （用哈希表的哈希函数）计算每个元素的哈希值，来查找内关系里相关的哈希桶内
- 5) 是否与外关系的元素匹配 。
- 内关系被划分成 X 个哈希桶
- 哈希函数几乎均匀地分布每个关系内数据的哈希值，就是说哈希桶大小一致 。
- 外关系的元素与哈希桶内的所有元素的匹配，成本是哈希桶内元素的数量 。
还有个哈希联接的版本，对内存有利但是对磁盘 I/O 不够有利 。这回是这样的：
