性能优化技巧:有序归并

一、   问题背景与适用场景

在以前的文章中我们介绍过,关系数据库在进行表间关联时是使用HASH分段技术。设两个关联表的规模(记录数)分别是 N M,则 HASH 分段技术的计算复杂度(关联字段的比较次数)大概是 SUM(Ni*Mi),其中 Ni Mi 分别是 HASH 值为 i 的两表记录数,满足 N=SUM(Ni) M=SUM(Mi),这大概率会比完全遍历时的复杂度 N*M 要小很多(运气较好的时候会小 K 倍,K HASH 值的取值范围)。

如果这两个表针对关联键都有序,那么我们就可以使用归并算法来处理关联,这时的复杂度是 N+M;在 N M 都较大的时候(一般都会远大于 K),这个数会远小于刚才那个 SUM(Ni*Mi)。因此有序归并关联的计算速度会比HASH分段关联快很多。

在实际应用中,因为同维表和主子表总是针对主键或主键的一部分关联,我们可以事先把这些关联表的数据按其主键排序,以后就可以总是使用归并算法实现关联,效率能提高很多。SPL即采用了这样的算法。

下面我们就用集算器SPL与关系数据库Oracle作个对比,来测试一下有序归并关联的效率。

 

二、   测试环境

1、小数据全内存测试

测试机有两个Intel2670 CPU,主频2.6G,共16核,内存128GSSD固态硬盘。

采用TPCH标准生成的50G数据,主表是orders,子表是orderdetail(lineitem表数据记录减少后生成)。两表中记录分别按O_ORDERKEYL_ORDERKEY升序排列。

OracleSPL均使用单线程测试。

2、大数据外存测试

采用前述测试机中的虚拟机,内存16GSSD固态硬盘。

采用TPCH标准生成的200G数据,主表是orders,子表是lineitem。两表中记录分别按O_ORDERKEYL_ORDERKEY升序排列。

因数据量比较大,OracleSPL均使用8线程并行测试。

三、   小数据全内存测试

1.  Oracle测试

1)无关联测试

测试的SQL语句如下:

select

       l_year,

       sum(volume) as revenu,

       sum(l_quantity) as quantity

from

       (

              select

                     extract(year from l_shipdate) as l_year,

                     (l_extendedprice * (1 - l_discount) ) as volume,

                     l_quantity

              from

                     orderdetail

       )

group by

       l_year

union all

select

       2019 as l_year,

       count(o_orderkey) as revenu,

       count(o_totalprice) as quantity

from

       orders;

 

2)有关联测试

测试的SQL语句如下:

select

       l_year,

       sum(volume) as revenu,

       sum(l_quantity) as quantity

from

       (

              select

                     extract(year from l_shipdate) as l_year,

                     (l_extendedprice * (1 - l_discount) ) as volume,

                     l_quantity

              from

                     orders,

                     orderdetail

              where

                     o_orderkey = l_orderkey

                     and l_quantity>0

       )

group by

       l_year;

查询条件 l_quantity>0 始终为真,没有过滤数据,是为了确保会读取这一列数据。

 

2.  SPL测试

1)无关联测试

编写SPL脚本如下:


A

1

>orders=file("/home/ctx/orders.ctx").open().memory()

2

>orderdetail=file("/home/ctx/orderdetail.ctx").open().memory()

3

=now()

4

=orderdetail.cursor(L_ORDERKEY,L_EXTENDEDPRICE,L_DISCOUNT,L_SHIPDATE,L_QUANTITY).groups(year(L_SHIPDATE):l_year; sum(L_EXTENDEDPRICE*(1-L_DISCOUNT)):revenue,sum(L_QUANTITY):quantity)

5

=orders.groups(;count(O_ORDERKEY),count(O_TOTALPRICE))

6

=interval@s(A3,now())

 

2)有关联测试

编写SPL脚本如下:


A

1

>orders=file("/home/ctx/orders.ctx").open().memory()

2

>orderdetail=file("/home/ctx/orderdetail.ctx").open().memory()

3

=now()

4

=orders.cursor(O_ORDERKEY,O_TOTALPRICE;O_TOTALPRICE>0)

5

=orderdetail.cursor(L_ORDERKEY,L_EXTENDEDPRICE,L_DISCOUNT,L_SHIPDATE,L_QUANTITY)

6

=joinx(A5:detail,L_ORDERKEY;A4:orders,O_ORDERKEY)

7

=A6.groups(year(detail.L_SHIPDATE):l_year;sum(detail.L_EXTENDEDPRICE*(1-detail.L_DISCOUNT)):revenue, sum(detail.L_QUANTITY):quantity)

8

=interval@s(A3,now())

A6中的joinx就是有序归并关联函数,要求关联字段都按升序排列。

 

3.  测试结果及分析

测试结果列表如下(单位:秒)

类别

无关联

有关联

变慢倍数

关联用时

Oracle

16

67

4.2

51

SPL

14

32

2.3

18

每种测试结果都是多次运行、数据充分缓存以后,取最快的一次。

分析两句SQL,无关联测试中对orders表读出O_ORDERKEYO_TOTALPRICE两列并统计记录数,对orderdetail表读出L_ORDERKEYL_EXTENDEDPRICEL_DISCOUNTL_SHIPDATE、L_QUANTITY 五列,并对销售价格求和、对L_QUANTITY求和。而在有关联测试中,对ordersorderdetail表的读取量相同,同时对关联后的销售价格求和、对L_QUANTITY求和。两种情况下的读取和计算量基本是相当的,多出的操作就是两表间的关联,所以两者的运行时间差就是关联操作用时。同理,SPL也是如此。

在同样的硬件设备和数据规模下,SPL关联用时18秒,Oracle关联用时51秒,几乎是前者的3倍,而且SPLJava编写的程序,而OracleC++实现的,这充分验证了有序归并关联能够极大地提高关联效率。SPL有关联比无关联时速度慢了2.3倍,Oracle慢了4.2倍,说明有序归并计算与普通计算速度相当,而HASH关联比普通计算要慢很多。

 

四、   大数据外存测试

当要 JOIN 的两个表都大到内存无法放下的时候,关系数据库仍然是使用 HASH 分段的技术。根据关联字段的 HASH 值,将数据分成若干段,每段都足够小到能装入内存再实施内存的 HASH 分段算法。但这会发生外存倒换的问题,数据需要先分段写出再读入,多出一写一读,外存读本来就不快,写就更慢,这样性能会差出很多。

有序归并关联则没有这个问题,两个表的数据都只要遍历一次就行了,不仅是 CPU 的计算量减少,外存的 IO 量也大幅下降。而且,执行归并算法需要的内存很少,只要在内存中为每个表保持数条缓存记录就可以了,几乎不会影响其它并发任务对内存的需求。

 

1.  Oracle测试

1)无关联测试

测试的SQL语句与小数据测试相同,只需把orderdetail表改成lineitem表,另在第一个select后添加“  /*+ parallel(8) */”使用8线程并行。

2)有关联测试

测试的SQL语句与小数据测试相同,只需把orderdetail表改成lineitem表,另在第一个select后添加“  /*+ parallel(8) */”使用8线程并行。

 

2.  SPL测试

1)无关联测试

编写SPL脚本如下:


A

1

=now()

2

=file("/home/ctx/lineitem.ctx").open().cursor@m(L_ORDERKEY,L_EXTENDEDPRICE,L_DISCOUNT,L_SHIPDATE,L_QUANTITY;;8)

3

=A2.groups(year(L_SHIPDATE):l_year; sum(L_EXTENDEDPRICE*(1-L_DISCOUNT)):revenue,sum(L_QUANTITY):quantity)

4

=file("/home/ctx/orders.ctx").open().cursor@m(O_ORDERKEY,O_TOTALPRICE;;8)

5

=A4.total(count(O_ORDERKEY),count(O_TOTALPRICE))

6

=interval@s(A1,now())

数据量大,A2A4都使用8路并行游标读数。

 

2)有关联测试

编写SPL脚本如下:


A

1

=now()

2

=file("/home/ctx/orders.ctx").open().cursor@m(O_ORDERKEY,O_TOTALPRICE;O_TOTALPRICE>0;8)

3

=file("/home/ctx/lineitem.ctx").open().cursor(L_ORDERKEY,L_EXTENDEDPRICE,L_DISCOUNT,L_SHIPDATE,L_QUANTITY;;A2)

4

=joinx(A3:detail,L_ORDERKEY;A2:orders,O_ORDERKEY)

5

=A4.groups(year(detail.L_SHIPDATE):l_year; sum(detail.L_EXTENDEDPRICE*(1-detail.L_DISCOUNT)):revenue,sum(detail.L_QUANTITY):quantity)

6

=interval@s(A1,now())

A3中生成游标时用了A2作为参数,表示与主表orders的主键同步分段读取。

A4中的joinx就是有序归并关联函数,要求关联字段都按升序排列。

 

3.   测试结果及分析

测试结果列表如下(单位:秒)

类别

无关联

有关联

变慢倍数

关联用时

Oracle

265

863

3.3

598

SPL

70

101

1.4

31

计算量分析及关联用时计算与小数据测试同理。

在同样的硬件设备和数据规模下,SPL关联用时31秒,Oracle关联用时598秒,是前者的19倍,更进一步验证了有序归并关联能够极大地提高关联效率。与小数据测试时相比,倍数大大增加,说明数据量越大,有序归并关联比HASH关联的性能提升优势越明显。

有关联比无关联变慢的倍数也可以得出与小数据测试时同样的结论,不过这里比小数据测试时多了读取数据的时间(小数据时数据全部缓存到内存了),所以无关联测试时的时间基数变大了,变慢倍数看起来反而比小数据测试时减小了。

 


系列性能优化技巧:
性能优化技巧:遍历复用
性能优化技巧:TopN
性能优化技巧:预关联
性能优化技巧:部分预关联
性能优化技巧:外键序号化
性能优化技巧:维表过滤或计算时的关联
性能优化技巧:有序归并
性能优化技巧:有序定位关联提速主子关联后的过滤
性能优化技巧:附表
性能优化技巧:大维表查找
性能优化技巧:单边分堆
性能优化技巧:有序分组
性能优化技巧:后半有序分组
性能优化技巧:前半有序时的排序