连接运算 6- 外键预关联
我们再来研究如何利用 JOIN 的特征实现性能优化，这些内容的细节较多，我们挑一些易于理解的情况来举例，更完善的连接提速算法可以参考乾学院上的《性能优化》图书及课程。
六、外键预关联
先看全内存下外键关联的情况。
设有两个表：
customer 客户信息表
-
key 编号
-
name 名称
-
city 城市
-
…
orders 订单表
-
seq 序号
-
date 日期
-
custkey 客户编号
-
amount 金额
-
…
其中 orders 表中的 custkey 是指向 customer 表中 key 字段的外键，key 是 customer 表的主键。
现在我们各个城市的订单总额（为简化讨论，就不再设定条件了），用 SQL 写出来：
SELECT customer.city, SUM(orders.amount)
FROM orders
JOIN customer ON orders.custkey=customer.key
GROUP BY customer.city
数据库一般会使用 HASH JOIN 算法，需要分别两个表中关联键的 HASH 值并比对。
我们用前述的简化的 JOIN 语法写出这个运算：
SELECT custkey.city, SUM(amount)
FROM orders
GROUP BY custkey.city
这个写法其实也就预示了它还可以有更好的优化方案，下面来看看怎样实现。
如果所有数据都能够装入内存，我们可以实现外键地址化。
将事实表 orders 中的外键字段 custkey，转换成维表 customer 中关联记录的地址，即 orders 表的 custkey 的取值已经是某个 customer 表中的记录，那么就可以直接引用记录的字段进行计算了。
用 SQL 无法描述这个运算的细节过程，我们使用 SPL 来描述、并用文件作为数据源来说明计算过程：
A |
|
1 |
=file("customer.btx").import@b() |
2 |
>A1.keys@i(key) |
3 |
=file("orders.btx").import@b() |
4 |
>A3.switch(custkey,A1) |
5 |
=A3.groups(custkey.city;sum(amount)) |
A1 读出客户表，A2 为客户表设置主键并建立索引。A3 读出订单表，A4 的动作是将 A3 的外键字段 custkey 转换成对应的 A1 的记录，执行完后，订单表字段 custkey 将变成客户表的某条记录。A2 建了索引能让 switch 更快，因为通常事实表远大于维表，这个索引能被复用很多次。A5 就可以执行分组汇总了，遍历订单表时，由于 custkey 字段取值现在已经是一条记录，那么可以直接用. 操作符引用其字段了，custkey.city 就可以正常执行。
完成 A4 中的 switch 动作之后，内存中事实表 A3 的 custkey 字段存储内容已经是维表 A1 的某条记录的地址，这个动作即称为外键地址化。这时候引用维表字段时，可以直接取出，而不需要再用外键值在 A1 中查找，相当于在常数时间内就能取到维表的字段，避免了 HASH 值计算和比对。
不过，A2 建主键索引一般也会用 HASH 办法，对 key 计算 HASH 值，A4 转换地址时也是计算 custkey 的 HASH 值与 A2 的 HASH 索引表对比。如果只做一次关联运算，地址化的方案和传统 HASH 分段方案的计算量基本上一样，没有根本优势。
但不同的是，如果数据能在内存中放下，这个地址一旦转换之后可以复用，也就是说 A1 到 A4 只要做一次，下次再做关于这两个字段的关联运算时就不必再计算 HASH 值和比对了，性能就能大幅提高。
能够这样做，正是利用了前面说过的外键关联在维表这一方具有的唯一性，一个外键字段值只会唯一对应一条维表记录，可以把每个 custkey 转换成它唯一对应的那条 A1 的记录。
而延用 SQL 中对 JOIN 的定义，就不能假定外键指向记录的唯一性，无法使用这种表示法。而且 SQL 也没有记录地址这种数据类型，结果会导致每次关联时都要计算 HASH 值并比对。
而且，如果事实表中有多个外键分别指向多个维表，传统的 HASH 分段 JOIN 方案每次只能解析掉一个，有 N 个 JOIN 要执行 N 遍动作，每次关联后都需要保持中间结果供下一轮使用，计算过程复杂得多，数据也会被遍历多次。而外键地址化方案在面对多个外键时，只要对事实表遍历一次， 没有中间结果，计算过程要清晰很多。
还有一点，内存本来是很适合并行计算的，但 HASH 分段 JOIN 算法却不容易并行。即使把数据分段并行计算 HASH 值，但要把相同 HASH 值的记录归聚到一起供下一轮比对，还会发生共享资源抢占的事情，这将牺牲很多并行计算的优势。而外键式 JOIN 模型下，关联两表的地位不对等，明确区分出维表和事实表后，只要简单地将事实表分段就可以并行计算。
将 HASH 分段技术参照外键属性方案进行改造后，也能一定程度地改善多外键一次解析和并行能力，有些数据库能在工程层面上实施这种优化。不过，这种优化在只有两个表 JOIN 时问题不大，在有很多表及各种 JOIN 混在一起时，数据库并不容易识别出应当把哪个表当作事实表去并行遍历、而把其它表当作维表建立 HASH 索引，这时优化并不总是有效的。所以我们经常会发现当 JOIN 的表变多时性能会急剧下降的现象（常常到四五个表时就会发生，结果集并无显著增大）。而从 JOIN 模型上引入外键概念后，将这种 JOIN 专门处理时，就总能分清事实表和维表，更多的 JOIN 表只会导致性能的线性下降。
内存数据库是当前比较火热的技术，但上述分析表明，采用 SQL 模型的内存数据库在 JOIN 运算上是很难快起来的！
