# I Problem introduction & solving

Relational databases use segmented hash table approach to join tables. Suppose two tables to be joined have sizes (record count) of N and M respectively, then the computational complexity (i.e. the join field comparison count) can be represented as SUM(Ni*Mi), in which Ni and Mi are respectively counts of records whose hash values are i in the two tables and meet expressions N=SUM(Ni) and M=SUM(Mi). The value of SUM(Ni*Mi) is, at almost all times, much smaller than N*M, even K (K is the range of hash values) times smaller sometimes.

If both tables are ordered by join keys, we can implement the join using MERGE algorithm. In that case the complexity is N+M. If both N and M are large (generally much greater than K), N+M is far smaller than SUM(Ni*Mi). That is, the MERGE algorithm is a lot faster than segmented hash table approach.

In real-world businesses, homo-dimension tables and main-sub tables are joined by the primary key or part of the primary key. So if we sort tables by their primary keys, we can always join them using the efficient MERGE. SPL encapsulates MERGE to facilitate a join.

In the following part well test how fast the SPL ordered merge is by comparing it with Oracle joins.

# IITest environment

1. Whole RAM small data calculation

There are two test computers. Each has an Intel2670 16-core CPU, a 2.6 GHz processor, a 128GB RAM and an SSD.

A total of 50G data has been generated according to TPCH benchmark. The main table is called orders and the subtable is orderdetail (which is generated based on a slimed lineitem). The two tables are ordered by O_ORDERKEY and L_ORDERKEY respectively in ascending order.

2. External memory big data calculation

Here we use the virtual machine running on the above test computers, with 16G RAM and an SSD.

A total of 200G data has been generated according to TPCH benchmark. The main table is called orders and the subtable is lineitem. The two tables are ordered respectively by O_ORDERKEY and L_ORDERKEY in ascending order.

The tests use an 8-threads parallel processing to handle the huge volume of data.

# III Whole RAM small data calculation test

## 1. Oracle

(1) Non-join query test

SQL statements:

select

l_year,

sum(volume) as revenu,

sum(l_discount) as discount

from

(

select

extract(year from l_shipdate) as l_year,

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

l_discount

from

orderdetail

)

group by

l_year

union all

select

2019 as l_year,

count(o_orderkey) as revenu,

count(o_totalprice) as discount

from

orders;

(2) Join query test

SQL statements:

select

l_year,

sum(volume) as revenu,

sum(o_totalprice) as totalprice

from

(

select

extract(year from l_shipdate) as l_year,

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

o_totalprice

from

orders,

orderdetail

where

o_orderkey = l_orderkey

)

group by

l_year;

2. SPL

(1) Non-join query test

SPL script:

 A 1 >orders=file("/home/ctx/orders.ctx").create().memory() 2 >orderdetail=file("/home/ctx/orderdetail.ctx").create().memory() 3 =now() 4 =orderdetail.cursor(L_ORDERKEY,L_EXTENDEDPRICE,L_DISCOUNT,L_SHIPDATE).groups(year(L_SHIPDATE):l_year;  sum(L_EXTENDEDPRICE * (1 - L_DISCOUNT)):revenue,sum(L_DISCOUNT):discount) 5 =orders.groups(;count(O_ORDERKEY),count(O_TOTALPRICE)) 6 =interval@s(A3,now())

(2) Join query test

SPL script:

 A 1 >orders=file("/home/ctx/orders.ctx").create().memory() 2 >orderdetail=file("/home/ctx/orderdetail.ctx").create().memory() 3 =now() 4 =orders.cursor(O_ORDERKEY,O_TOTALPRICE) 5 =orderdetail.cursor(L_ORDERKEY,L_EXTENDEDPRICE,L_DISCOUNT,L_SHIPDATE) 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(orders.O_TOTALPRICE):totalprice) 8 =interval@s(A3,now())

A6 uses the order-based merge function joinx() to perform a join. The function requires that join keys should be ordered in ascending order.

3. Test results & analysis

Here are test results (Unit: second):

 Language Non-join Join Decrease (times) Query time Oracle 16 67 4.2 51 SPL 14 32 2.3 18

Each result is the best-performing among multiple executions with data fully buffered.

Some explanations about the above SQL statements. In the non-join query test, we retrieve O_ORDERKEY field and O_TOTALPRICE field from orders table and count records; we retrieve L_ORDERKEY, L_EXTENDEDPRICE, L_DISCOUNT and L_SHIPDATE fields from orderdetail table and sum sales prices and L_DISCOUNT. In the join query test, we retrieve equal amount of data from the two tables and sum sales prices and O_TOTALPRICE over the joining result set. The retrieval and computing amount in both scenarios are same, so the difference between them lies in the time spent in performing the join. This applies to SPL.

Under equal external storage devices and data sizes, it takes SPL 18 seconds and Oracle 51 seconds to perform the join. The Java-based SPL is nearly 3 times faster than C++-driven Oracle. This confirms that the order-based merge can greatly speed up a join. On the other hand, a SPL join query is 2.3 times slower and an Oracle join query is 4.2 slower than a non-join query. That means an order-based merge is much faster than the segmented hash table approach.

# IV External memory big data calculation test

When both tables to be joined cant fit into the memory, relational databases still use segmented hash table approach to perform the join. The approach divides records in each table into multiple segments according to join field hash values, loads each segment into the memory and uses the segmented hash table approach again to perform the join. Read and write data on an external storage device is slow. And the data transfer from external storage to the memory involves extra export and load by segments, which seriously slows the computation.

Order-based merge only needs a traverse of each table. The CPU load reduces and the external memory IO amount considerably decreases. The algorithm requires a very small share of memory space to buffer a number of records for each table. That almost wont affect memory requirements for other concurrent tasks.

## 1.Oracle

(1) Non-join query test

The test SQL statements are similar to those for small data calculation. We just need to change orderdetail table to lineitem table and add “/*+ parallel(8) */” after the first select word to enable an 8-thread parallel processing.

(2) Join query test

The test SQL statements are similar to those for small data calculation. We just need to change orderdetail table to lineitem table and add “/*+ parallel(8) */” after the first select word to enable an 8-thread parallel processing.

## 2.SPL

1Non-join query test

SPL script:

 A 1 =now() 2 =file("/home/ctx/lineitem.ctx").create().cursor@m(L_ORDERKEY,L_EXTENDEDPRICE,L_DISCOUNT,L_SHIPDATE;;8) 3 =A2.groups(year(L_SHIPDATE):l_year;  sum(L_EXTENDEDPRICE * (1 - L_DISCOUNT)):revenue,sum(L_DISCOUNT):discount) 4 =file("/home/ctx/orders.ctx").create().cursor@m(O_ORDERKEY,O_TOTALPRICE;;8) 5 =A4.total(count(O_ORDERKEY),count(O_TOTALPRICE)) 6 =interval@s(A1,now())

Both A2 and A4 retrieve data with an 8-thread multicursor.

2Join query test

SPL script:

 A 1 =now() 2 =file("/home/ctx/orders.ctx").create().cursor@m(O_ORDERKEY,O_TOTALPRICE;;8) 3 =file("/home/ctx/lineitem.ctx").create().cursor(L_ORDERKEY,L_EXTENDEDPRICE,L_DISCOUNT,L_SHIPDATE;;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(orders.O_TOTALPRICE):totalprice) 6 =interval@s(A1,now())

A3 uses A2 as a parameter to retrieve data from lineitem table by segments according to orders tables segmented primary key.

A4 uses joinx() function, which requires that join keys should be ordered in ascending order, to perform the order-based merge.

## 3. Test results & analysis

Here are test results (Unit: second):

 Language Non-join Join Decrease (times) Query time Oracle 265 863 3.3 598 SPL 70 101 1.4 31

About the computing amount and join query time, you can refer to explanations for the small data calculation.

Under equal external storage devices and data sizes, it takes SPL 31 seconds and Oracle 598 seconds to perform the join. SPL is over 19 times faster than the database product, which is strong evidence about the order-based merge ability and which is far greater than that for the small data calculation. That means the larger the data size becomes, the greater the impact of the order-based merge algorithm on performance.

Same conclusion can be drawn from the decrease times of the join query. But compared with the small data calculation test where data is fully buffered to the memory, the external memory big data calculation spends more time in data retrieval. That makes longer non-join query time and explains why the decrease stats become smaller.