【性能优化】6.1 [外键关联] 外键地址化
6.1 外键地址化
我们简单回顾一下外键关联的概念：数据表 T 中字段 F 和数据表 D 的主键 K 关联时，D 称为 T 的外键表，又称维表，T 称为事实表，字段 F 称为外键字段。如果 D 的主键有多个字段也可以类似定义出外键关联。外键关联的目标在于访问 T 的记录时，能够引用其字段 F 对应的 D 表中的记录的字段。
外键关联的特点是事实表的外键必须和维表的主键关联，而主键具有唯一性，也就是事实表的记录只会和唯一的维表记录关联，是典型的多对一关联。做性能优化时要利用这一点。
如果数据量不是非常大，事实表和维表都可以装入内存。我们可以先把关联关系建好，就可以快速引用到维表的字段了。
设订单表 orders 中有外键 p_id 关联产品表 prodcut 的主键 pid（实际表结构设计中常常会把外键字段和对应的主键字段用相同命名，这里故意有微小不同以示区分），需要从产品表中取出产品单价与订单表中的销售数量相乘得到订单金额，然后统计不同厂商（也是产品表的字段）的总订单金额。
A |
|
1 |
=file("product.btx").import@b() |
2 |
=file("orders.btx").import@b() |
3 |
>A1.keys@i(pid) |
4 |
>A2.switch(p_id,A1) |
5 |
=A2.groups(p_id.vendor;sum(p_id.price*quantity)) |
A1 读出产品表，A2 读出订单表，A3 为产品表设置主键并建立索引。A4 的动作是将 A2 的外键字段 p_id 转换成对应的 A1 的记录，即在 A4 执行完之后，A2 的字段 p_id 将变成 A1 中的某条记录，相当于执行了：
A2.run(p_id=A1.find(p_id))
A3 建了索引能让 switch 更快，因为通常事实表远大于维表，这个索引能被复用很多次。
A5 遍历事实表时，由于 p_id 字段取值现在已经是一条记录，那么可以直接用. 操作符引用其字段了，p_id.vendor 和 p_id.price 都可以正常执行。
完成 switch 操作之后，内存中事实表 A2 的 p_id 字段存储内容已经是维表 A1 的某条记录的地址，这个动作称为外键地址化。这时候使用. 操作符引用维表字段时，就可以直接取出了，而不需要再用外键值在 A2 中查找，相当于常数时间内就能取到维表的字段。否则即使是使用快速的哈希索引查找也需要一些时间，而且和维表的规模相关。
这相当于复用了第三步 switch 的成果。而前三步，即读入表、建索引和用 switch 做好关联，都可以事先一次性做好。之后针对事实表的运算，都可以快速引用维表字段了。
能够这样做，正是利用了前面说过的外键关联在维表这一方具有的唯一性，一个外键字段值只会唯一对应一条维表记录，可以把每个 p_id 转换成它唯一对应的那条 A2 的记录。
其实，外键属性化之后的代码书写也变得更简单易懂了。
这种运算在数据库中就是连接，关系代数没有约定关联的一方必须是主键， 不能保证关联中某一方的唯一性，也不能预先将外键字段转换成维表记录。数据库通常使用哈希算法来做内存连接，即计算两表关联字段的哈希值，把相同哈希值的记录分到一组再做遍历对应。做一次连接运算的复杂度，相当于在某个表（无主键假定时没有维表和事实表的明确定义）的关联键上建索引，然后遍历另一个表用其每一条记录的关联键在这个表中做查找。也就是本例中 A3 和 A4 做的运算量。
外键地址化的准备工作也会做同样事情（即 A3 和 A4），但做完之后就可以复用了，不必每次做连接运算时再建索引并基于索引查找，后续计算的性能就会好很多。如果只做一次运算，加上这些准备工作的时间，那就不会比数据库的哈希方法更快了。
我们可以在系统启动时把数据表读入后做好外键地址化，这个动作称为预关联。之后就能高速应对关联查询和统计，这个手段对于建设高性能内存数据库非常有意义。而基于关系代数理论体系的内存数据库做不到这一点。
如果事实表有多个外键关联不同的维表，以及维表可能还有维表，都可以事先做好预关联：
A |
|
1 |
=file("area.btx").import@b().keys(aid) |
2 |
=file("product.btx").import@b().keys@i(pid) |
3 |
=file("orders.btx").import@b() |
4 |
>A2.switch(a_id,A1) |
5 |
>A3.switch(p_id,A2;a_id,A1) |
6 |
=A3.select(p_id.a_id.state==a_id.state ) |
7 |
=A6.groups(p_id.vendor;sum(p_id.price*quantity)) |
A1、A2、A3 读入数据，A4、A5 做好预关联。A6、A7 是运算代码。
这段代码会选出订单交易地与产地相同的订单再按厂商统计总订单额。涉及三个表关联，其中订单表有两个外键及维表，地区表被两次作为维表和其它表关联。
哈希连接算法原则上一次只能解析一个关联关系，有多个关联关系就需要解析多次，也要对相关表遍历多次。而区分事实表和维表之后，可以一次遍历中把同一事实表的多个外键都完成地址化。从理论分析上看，多次遍历分别解析的哈希计算和比对次数并不会比一次遍历做多个地址化更大，但每次遍历都会伴随着一批数据记录的产生和复制动作，实际的运算量要远远大于一次遍历。
而且，在关联层数和涉及数据表较多时，数据库的优化器常常不能找出最合适的解析次序，而不同的次序会导致不同的数据产生和复制运算量，如果每次关联都有大表参与，这些额外的计算量就会很大。我们会观察到，数据量并没有增大多少时，而只是增加关联表数和层数，数据库的计算性能却可能急剧下降。
明确区分事实表和维表后，多个表的多层关联仍然很清晰。小表之间的关联可以独立地址化，不会牵扯其它大表。性能下降程度只和数据量和关联层数线性相关。
实际业务中关联关系常常比这里例子中的还要复杂得多，外键地址化的优势会更明显。
使用 switch 实现外键地址化后，能获得更好的性能，但它还有几个问题：
1) 地址化之后，外键字段的本身值失去了，必须到维表中取主键才能获得，速度会变慢。
上节例中，地址化后如果还想取得 pid，要用 p_id.pid 才可以。
2) 如果在维表中找不到关联记录，外键字段会转换成 null，将彻底丢失原值。
3) 外键有可能由多个字段构成，这时候就不能用 switch 函数来转换了。
SPL 还提供了 join 函数来适应这些场景：
A |
|
1 |
=file("area.btx").import@b().keys(aid) |
2 |
=file("product.btx").import@b() |
3 |
=A2.join(a_id,A1,~:area).keys@i(pid) |
4 |
=file("orders.btx").import@b() |
5 |
=A4.join(p_id,A3,~:product;a_id,A1,~:area) |
6 |
=A5.select(product.area.state==area.state ) |
7 |
=A6.groups(product.vendor;sum(product.price*quantity)) |
join 将在原序表上增加字段来保存维表记录的地址，原字段值并不改变，上面的问题都能得到解决。不同的是，join 将返回新的序表，在做地址化时要注意次序，即是事实表又是维表的数据表，要先关联自己的维表后得到新的数据表，然后再用来被事实表关联。
