【性能优化】6.8 [外键关联] 大维表查找
6.8 大维表查找
遍历事实表时用外键查找维表记录，每次只取一条记录；而事实表通常不会按外键字段有序（事实表可能有多个外键，对某一个外键有序就不会对另一个有序，大部分情况是对所有外键都无序），查找到的维表记录也就是随机的；如果事实表记录数稍多（不用多到内存装不下的地步），对维表的读取就是典型的频繁随机小量访问。这种访问方式对于硬盘来讲就意味着极低的性能。
好在维表稳定性较高，通常不会很大而可以放进内存之中。前面几节讨论的都是这种情况。
但我们还是偶而会碰到维表也很大而不能装入内存的情况。面对外存中的维表，就不能再使用上面的算法了，否则就会面临频繁随机小量访问。
我们先考虑事实表反而较小而能装入内存的情况。
用外键关联维表，本质上是个查找的动作，大维表时就是外存查找，回顾之前讲过的算法，想获得高性能，数据表要按被查找键（也就是维表的主键）有序存储或者建有索引。
事实表多条记录，也就有多个外键值，问题又转化成批量外存查找。要把事实表的外键值聚集起来一起查找，以避免单独查找时造成的频繁访问。
A |
|
1 |
=file("customer.btx") |
2 |
=file("orders.btx").import@b(c_id,amount) |
3 |
=A1.iselect(A2.id(c_id),cid;area,discount).fetch() |
4 |
=A2.switch(p_id,A3:pid).groups(p_id.area;sum(amount*discount)) |
存在集文件中的维表对主键有序，要对维表随机查找，所以不能以游标方式出现。将事实表的外键值拼成序列后，再用 iselect 函数（二分法）较快速地取需要的维表记录，而避免遍历整个大维表。事实表的外键值可能有重复，要用 id 做去重同时排序，再去维表文件中查找，最后再与事实表做关联。
SPL 将这个过程封装到一个 joinx@q 函数中：
A |
|
1 |
=file("customer.btx") |
2 |
=file("orders.btx").import@b(c_id,amount) |
3 |
=A2.joinx@q(c_id,A1:cid,area,discount) |
4 |
=A3.groups(area;amount*discount) |
和前面用过的地址化方法不同，从维表取出只是部分记录和字段，大部分情况仅是临时使用，再构成一个序表后做地址化的意义并不大，所以 joinx@q 函数直接把维表字段拼到了事实表记录上。
如果维表存入组表中，还可以利用索引来查找， 能获得更好的性能。
A |
|
1 |
=file("customer.ctx").open() |
2 |
=file("orders.btx").import@b(c_id,amount) |
3 |
=A2.joinx@q(c_id,A1:cid,area,discount) |
4 |
=A3.groups(area;amount*discount) |
组表一般会按主键排序，即使没有索引也能用二分法较快速地找出来。
和内存维表类似，这种方法也可以同时解析多个大维表的关联。解析完外存维表后，还可以继续在得到的序表上再解析内存维表。理清维表和事实表之间的关系是解决外键关系获得高性能的关键基础。
关系代数理论不区分维表和事实表，对于两个表的连接，很多数据库仍然是把小表读入内存去遍历大表，具体到当前的情况就是把事实表读入内存后去遍历维表。数据库对于大事实表小维表和大维表小事实表这两种情况的处理方式是相同的。
这里讨论的维表查找方法也要读入事实表，但并不需要遍历大维表。大事实表小维表和大维表小事实的处理方式并不对称。事实表的每一条记录都要参与计算，对它的遍历是不能避免的。维表却不同，并不是每一条维表记录都会参与计算（最多用到的记录数不超过事实表的记录数），小维表读入时间不多，全读入即使有浪费并不会有太大影响（而且在前几节讨论中这些维表通常还会被复用，也不会浪费）。但大维表被遍历就不划算了，事实表较小时，用到的维表记录只占很小部分，没有必要把整个大维表都遍历一次。
数据库，或者说关系代数体系，对数据关联理解较为简单，没有深刻体现出数据关联中更本质的特征，也就无法从理论上设计出更高性能的算法，只能寄希望于数据库的工程优化。具体到这个问题，有些做得好的数据库优化器能发现关联键之一是大表的主键，也会“聪明”地选择查找技术而不是去遍历，但是涉及表较多时也还是会“晕”。
