性能优化技巧：有序定位关联提速主子关联后的过滤
一、 问题背景与适用场景
在《性能优化技巧：有序归并》中我们验证了有序归并算法提高关联性能的效果，那么还有没有进一步提升的空间呢？能不能再减少数据的读取量从而再提速呢？
通常主子关联后还会再施加更多运算，比如过滤。有序归并算法将主子表先分别读出再做关联，当其中一个关联表被过滤后剩下记录少了很多时，另一个关联表也会有大量记录不能关联上，但做归并关联之前并不知道，仍然会将这些不可能关联上的数据读出，浪费了时间。
如果我们能根据被过滤表的主键去另一个表查找可被关联记录再来做关联，那样就能省去很多读取动作了。而由于组表是按键有序存放的，恰恰能使我们可以用键值高速定位记录，从而实现这个想法。
下面我们就做个测试，与常规有序归并对比一下，看看性能提升的效果，并在测试过程中进一步分析一下提速原理。
二、 测试环境
测试机有两个Intel2670 CPU，主频2.6G，共16核，内存128G，SSD固态硬盘。
采用TPCH标准生成的200G数据，主表是orders，子表是lineitem。两表中记录分别按O_ORDERKEY、L_ORDERKEY升序排列。因数据量比较大，单线程运行时间较长，所以使用4线程并行测试。
三、 主表有过滤
查询时对主表的过滤条件是O_TOTALPRICE>price，price是个参数，用来测试主表过滤后不同数据规模下的效果。
1. 常规有序归并
编写SPL脚本如下：
A |
|
1 |
=now() |
2 |
=file("/home/ctx/orders.ctx").open().cursor@m(O_ORDERKEY,O_ORDERDATE;O_TOTALPRICE>price;4) |
3 |
=file("/home/ctx/lineitem.ctx").open().cursor(L_ORDERKEY,L_EXTENDEDPRICE,L_DISCOUNT;;A2) |
4 |
=joinx(A3:detail,L_ORDERKEY;A2:orders,O_ORDERKEY) |
5 |
=A4.groups(year(orders.O_ORDERDATE):year;sum(detail.L_EXTENDEDPRICE*(1-detail.L_DISCOUNT)):revenue) |
6 |
=interval@s(A1,now()) |
2. 有序定位关联
编写SPL脚本如下：
A |
|
1 |
=now() |
2 |
=file("/home/ctx/orders.ctx").open().cursor@m(O_ORDERKEY,O_ORDERDATE;O_TOTALPRICE>price;4) |
3 |
=file("/home/ctx/lineitem.ctx").open().news(A2,L_ORDERKEY,L_EXTENDEDPRICE,L_DISCOUNT,O_ORDERDATE) |
4 |
=A3.groups(year(O_ORDERDATE):year;sum(L_EXTENDEDPRICE*(1-L_DISCOUNT)):revenue) |
5 |
=interval@s(A1,now()) |
A3中创建子表游标时没有使用cursor函数，而是使用的news函数，表示在主表游标的基础上，用有序定位归并后生成主子表关联后的游标，所以也不需要再用joinx进行关联了。
3. 测试结果及分析
主表orders总记录3亿，测试结果列表如下：
主表过滤后记录数 |
2亿 |
1.4亿 |
0.9亿 |
0.17亿 |
常规有序归并(秒) |
131 |
115 |
94 |
57 |
有序定位关联(秒) |
105 |
87 |
69 |
35 |
比较两段SPL脚本，主表游标的创建是一样的，在常规有序归并中子表游标是独立创建，会把子表记录中的每条记录所需的3个字段全部读出，然后在joinx的时候再把两个游标的记录进行有序归并。而在有序定位关联中，是根据已经过滤后的主表记录的关联字段值，去子表有序查找所对应的关联字段值。组表数据是分块存储的，组表索引头会记着每块主键的最大最小值，如果发现关联键值大于当前块的最大值，就可以直接跳过这一块，再重新定位到包含这个键值的数据块去读。而且在比对的时候，只需要先读关联字段值，如果值不同而关联不上，则其它2个字段就不用读，值关联了才把其它2个字段读出来。
测试结果验证上述原理：在主表各种过滤规模下，使用有序定位关联均能较大地提高性能。
四、 子表有过滤
查询时对子表的过滤条件是L_QUANTITY >quantity，quantity是个参数，用来测试子表过滤后不同数据规模下的效果。
1. 常规有序归并
编写SPL脚本如下：
A |
|
1 |
=now() |
2 |
=file("/home/ctx/orders.ctx").open().cursor@m(O_ORDERKEY,O_ORDERDATE;;4) |
3 |
=file("/home/ctx/lineitem.ctx").open().cursor(L_ORDERKEY,L_EXTENDEDPRICE,L_DISCOUNT;L_QUANTITY>quantity;A2) |
4 |
=joinx(A3:detail,L_ORDERKEY;A2:orders,O_ORDERKEY) |
5 |
=A4.groups(year(orders.O_ORDERDATE):year; sum(detail.L_EXTENDEDPRICE*(1-detail.L_DISCOUNT)):revenue) |
6 |
=interval@s(A1,now()) |
2. 有序定位关联
编写SPL脚本如下：
A |
|
1 |
=now() |
2 |
=file("/home/ctx/lineitem.ctx").open().cursor@m(L_ORDERKEY,L_EXTENDEDPRICE,L_DISCOUNT;L_QUANTITY>quantity;4) |
3 |
=file("/home/ctx/orders.ctx").open().new(A2,O_ORDERKEY,O_ORDERDATE,sum(L_EXTENDEDPRICE*(1-L_DISCOUNT)):v) |
4 |
=A3.groups(year(O_ORDERDATE):year; sum(v):revenue) |
5 |
=interval@s(A1,now()) |
A3中使用new创建主表游标，同时用sum对子表数据按关联键分组求和后作为主表的一个字段值。
3. 测试结果及分析
子表lineitem总记录12亿，测试结果列表如下：
子表过滤后记录数 |
8.4亿 |
7.2亿 |
3.6亿 |
1.2亿 |
0.5亿 |
常规有序归并(秒) |
127 |
115 |
84 |
57 |
36 |
有序定位关联(秒) |
92 |
87 |
72 |
47 |
31 |
这两段SPL脚本和前面主表过滤的测试差不多，不同的只是使用过滤后的子表来关联主表，需要使用new函数。提速原理也和前面相同，已经过滤后的子表，再与主表关联时，只会读出能关联上的主表记录，不必完全遍历整个主表。从而减少数据读取量。
从测试结果看，随着过滤后剩下的子表记录越来越少，减少数据读取量的优势也越来越小，性能提升幅度变小。
五、 结论
对于有过滤的主子表关联查询，使用有序定位关联算法经常能获得更好的性能。
系列性能优化技巧：
性能优化技巧：遍历复用
性能优化技巧：TopN
性能优化技巧：预关联
性能优化技巧：部分预关联
性能优化技巧：外键序号化
性能优化技巧：维表过滤或计算时的关联
性能优化技巧：有序归并
性能优化技巧：有序定位关联提速主子关联后的过滤
性能优化技巧：附表
性能优化技巧：大维表查找
性能优化技巧：单边分堆
性能优化技巧：有序分组
性能优化技巧：后半有序分组
性能优化技巧：前半有序时的排序
