连接运算 6- 外键预关联

连接运算 5- 解决关联查询

我们再来研究如何利用 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 运算上是很难快起来的!

连接运算 7- 进一步的外键关联