Double Range Join vs. MATCH_RECOGNIZE

View All Scripts Login to Run Script

Script Name Double Range Join vs. MATCH_RECOGNIZE
Description First, double range join: key A must be in range B, key B must be in range A. Next, MATCH_RECOGNIZE alternative if inequality joins are scaling badly.
Area SQL General
Contributor Stew Ashton
Created Friday March 02, 2018

Statement 1

In the range, start and end points are inclusive.

Create first table with key and range

create table ta(key_a, start_a, end_a) as 
with data as ( 
  select level n from dual 
  connect by level <= 2 
) 
select distinct a.n, b.n, c.n 
from data a, data b, data c 
where b.n <= c.n

Table created.

Statement 2

The second table also has key and range

create table tb(key_b, start_b, end_b) as  
select * from ta

Table created.

Statement 3

select * from ta order by 1,2,3


KEY_A START_A END_A
1 1 1
1 1 2
1 2 2
2 1 1
2 1 2
2 2 2

6 rows selected.

KEY_A	START_A	END_A
1	1	1
1	1	2
1	2	2
2	1	1
2	1	2
2	2	2

Statement 4

select * from tb order by 1,2,3


KEY_B START_B END_B
1 1 1
1 1 2
1 2 2
2 1 1
2 1 2
2 2 2

6 rows selected.

KEY_B	START_B	END_B
1	1	1
1	1	2
1	2	2
2	1	1
2	1	2
2	2	2

Statement 5

Key A must be within range B, and key B must be within range A. Again, the start and end points are inclusive so BETWEEN can be used. Since this is an inequality join, it scales badly with a large number of rows.

Classic join

select KEY_A, START_B, END_B, KEY_B, START_A, END_A   
from ta, tb    
where key_a between start_b and end_b    
and key_b between start_a and end_a   
order by 1,2,3,4,5,6


KEY_A START_B END_B KEY_B START_A END_A
1 1 1 1 1 1
1 1 1 1 1 2
1 1 1 2 1 2
1 1 1 2 2 2
1 1 2 1 1 1
1 1 2 1 1 2
1 1 2 2 1 2
1 1 2 2 2 2
2 1 2 1 1 1
2 1 2 1 1 2
2 1 2 2 1 2
2 1 2 2 2 2
2 2 2 1 1 1
2 2 2 1 1 2
2 2 2 2 1 2
2 2 2 2 2 2

16 rows selected.

KEY_A	START_B	END_B	KEY_B	START_A	END_A
1	1	1	1	1	1
1	1	1	1	1	2
1	1	1	2	1	2
1	1	1	2	2	2
1	1	2	1	1	1
1	1	2	1	1	2
1	1	2	2	1	2
1	1	2	2	2	2
2	1	2	1	1	1
2	1	2	1	1	2
2	1	2	2	1	2
2	1	2	2	2	2
2	2	2	1	1	1
2	2	2	1	1	2
2	2	2	2	1	2
2	2	2	2	2	2

Statement 6

The idea here is to sort the rows so that the condition START_A <= B_KEY is necessarily true if and only if the TA row precedes the TB row in order.

Prepare MATCH_RECOGNIZE alternative

with data (order_, tbl_id, key_, start_, end_) as ( 
  select start_a, 'TA', key_a, start_a, end_a from ta 
  union all 
  select   key_b, 'TB', key_b, start_b, end_b from tb 
) 
select * from data 
order by order_, tbl_id


ORDER_ TBL_ID KEY_ START_ END_
1 TA 1 1 2
1 TA 1 1 1
1 TA 2 1 1
1 TA 2 1 2
1 TB 1 1 2
1 TB 1 2 2
1 TB 1 1 1
2 TA 1 2 2
2 TA 2 2 2
2 TB 2 2 2
2 TB 2 1 2
2 TB 2 1 1

12 rows selected.

ORDER_	TBL_ID	KEY_	START_	END_
1	TA	1	1	2
1	TA	1	1	1
1	TA	2	1	1
1	TA	2	1	2
1	TB	1	1	2
1	TB	1	2	2
1	TB	1	1	1
2	TA	1	2	2
2	TA	2	2	2
2	TB	2	2	2
2	TB	2	1	2
2	TB	2	1	1

Statement 7

Here we start with the first TA row, which will meet condition A. Then we process all the following rows where the ORDER_ value is less than or equal to the A end point. Any row from the TB table that meets all the conditions is a B row; those that do not meet all the conditions are X rows that we will ignore. Once we process all the following rows, we look for another TA row, starting with the "next row" after the A row we just processed.

MATCH_RECOGNIZE: identify the rows to be "joined"

with data (order_, tbl_id, key_, start_, end_) as ( 
  select start_a, 'TA', key_a, start_a, end_a from ta 
  union all 
  select   key_b, 'TB', key_b, start_b, end_b from tb 
) 
select * 
from data 
match_recognize(  
  order by order_, tbl_id 
  measures classifier() classifier, match_number() match_number 
  all rows per match  
  after match skip to next row  
  pattern( A ( B | X )+ )  
  define A as tbl_id = 'TA', 
         B as tbl_id = 'TB' 
          and b.key_ <= a.end_ 
            -- because of the ORDER BY, b.key_ must be >= a.start_ 
          and a.key_ between b.start_ and b.end_, 
         X as order_ <= a.end_ 
)


ORDER_ TBL_ID CLASSIFIER MATCH_NUMBER KEY_ START_ END_
1 TA A 1 1 1 2
1 TA X 1 1 1 1
1 TA X 1 2 1 1
1 TA X 1 2 1 2
1 TB B 1 1 1 2
1 TB X 1 1 2 2
1 TB B 1 1 1 1
2 TA X 1 1 2 2
2 TA X 1 2 2 2
2 TB X 1 2 2 2
2 TB B 1 2 1 2
2 TB B 1 2 1 1
1 TA A 2 1 1 1
1 TA X 2 2 1 1
1 TA X 2 2 1 2
1 TB B 2 1 1 2
1 TB X 2 1 2 2
1 TB B 2 1 1 1
1 TA A 3 2 1 1
1 TA X 3 2 1 2
1 TB B 3 1 1 2
1 TB B 3 1 2 2
1 TB X 3 1 1 1
1 TA A 4 2 1 2
1 TB B 4 1 1 2
1 TB B 4 1 2 2
1 TB X 4 1 1 1
2 TA X 4 1 2 2
2 TA X 4 2 2 2
2 TB B 4 2 2 2
2 TB B 4 2 1 2
2 TB X 4 2 1 1
2 TA A 5 1 2 2
2 TA X 5 2 2 2
2 TB X 5 2 2 2
2 TB B 5 2 1 2
2 TB B 5 2 1 1
2 TA A 6 2 2 2
2 TB B 6 2 2 2
2 TB B 6 2 1 2
2 TB X 6 2 1 1

41 rows selected.

ORDER_	TBL_ID	CLASSIFIER	MATCH_NUMBER	KEY_	START_	END_
1	TA	A	1	1	1	2
1	TA	X	1	1	1	1
1	TA	X	1	2	1	1
1	TA	X	1	2	1	2
1	TB	B	1	1	1	2
1	TB	X	1	1	2	2
1	TB	B	1	1	1	1
2	TA	X	1	1	2	2
2	TA	X	1	2	2	2
2	TB	X	1	2	2	2
2	TB	B	1	2	1	2
2	TB	B	1	2	1	1
1	TA	A	2	1	1	1
1	TA	X	2	2	1	1
1	TA	X	2	2	1	2
1	TB	B	2	1	1	2
1	TB	X	2	1	2	2
1	TB	B	2	1	1	1
1	TA	A	3	2	1	1
1	TA	X	3	2	1	2
1	TB	B	3	1	1	2
1	TB	B	3	1	2	2
1	TB	X	3	1	1	1
1	TA	A	4	2	1	2
1	TB	B	4	1	1	2
1	TB	B	4	1	2	2
1	TB	X	4	1	1	1
2	TA	X	4	1	2	2
2	TA	X	4	2	2	2
2	TB	B	4	2	2	2
2	TB	B	4	2	1	2
2	TB	X	4	2	1	1
2	TA	A	5	1	2	2
2	TA	X	5	2	2	2
2	TB	X	5	2	2	2
2	TB	B	5	2	1	2
2	TB	B	5	2	1	1
2	TA	A	6	2	2	2
2	TB	B	6	2	2	2
2	TB	B	6	2	1	2
2	TB	X	6	2	1	1

Statement 8

To finish the job, we need to exclude the A and X rows from the output, and add the A columns to each B row. The PATTERN clause provides an "exclusion syntax": any part of the pattern that is enclosed in {- -} excludes those rows from the output. We add the A columns to the output using the MEASURES clause. The B columns are output automatically because we said "all rows per match".

MATCH_RECOGNIZE: "join" the A and B rows

with data (order_, tbl_id, key_, start_, end_) as ( 
  select start_a, 'TA', key_a, start_a, end_a from ta 
  union all 
  select   key_b, 'TB', key_b, start_b, end_b from tb 
) 
select         KEY_A, start_ as START_B, end_ as END_B, 
       key_ as KEY_B,           START_A,         END_A 
from data 
match_recognize(  
  order by order_, tbl_id 
  measures a.key_ as key_a, a.start_ as start_a, a.end_ as end_a 
  all rows per match  
  after match skip to next row  
  pattern( {-A-} ( B | {-X-} )+ )  
  define A as tbl_id = 'TA', 
         B as tbl_id = 'TB' 
          and b.key_ <= a.end_ 
            -- because of the ORDER BY, b.key_ must be >= a.start_ 
          and a.key_ between b.start_ and b.end_, 
         X as order_ <= a.end_ 
)


KEY_A START_B END_B KEY_B START_A END_A
1 1 2 1 1 2
1 1 1 1 1 2
1 1 2 2 1 2
1 1 1 2 1 2
1 1 2 1 1 1
1 1 1 1 1 1
2 1 2 1 1 1
2 2 2 1 1 1
2 1 2 1 1 2
2 2 2 1 1 2
2 2 2 2 1 2
2 1 2 2 1 2
1 1 2 2 2 2
1 1 1 2 2 2
2 2 2 2 2 2
2 1 2 2 2 2

16 rows selected.

KEY_A	START_B	END_B	KEY_B	START_A	END_A
1	1	2	1	1	2
1	1	1	1	1	2
1	1	2	2	1	2
1	1	1	2	1	2
1	1	2	1	1	1
1	1	1	1	1	1
2	1	2	1	1	1
2	2	2	1	1	1
2	1	2	1	1	2
2	2	2	1	1	2
2	2	2	2	1	2
2	1	2	2	1	2
1	1	2	2	2	2
1	1	1	2	2	2
2	2	2	2	2	2
2	1	2	2	2	2

Additional Information

Database on OTN SQL and PL/SQL Discussion forums
Oracle Database
Download Oracle Database

KEY_A	START_B	END_B	KEY_B	START_A	END_A
1	1	1	1	1	1
1	1	1	1	1	2
1	1	1	2	1	2
1	1	1	2	2	2
1	1	2	1	1	1
1	1	2	1	1	2
1	1	2	2	1	2
1	1	2	2	2	2
2	1	2	1	1	1
2	1	2	1	1	2
2	1	2	2	1	2
2	1	2	2	2	2
2	2	2	1	1	1
2	2	2	1	1	2
2	2	2	2	1	2
2	2	2	2	2	2

ORDER_	TBL_ID	KEY_	START_	END_
1	TA	1	1	2
1	TA	1	1	1
1	TA	2	1	1
1	TA	2	1	2
1	TB	1	1	2
1	TB	1	2	2
1	TB	1	1	1
2	TA	1	2	2
2	TA	2	2	2
2	TB	2	2	2
2	TB	2	1	2
2	TB	2	1	1

ORDER_	TBL_ID	CLASSIFIER	MATCH_NUMBER	KEY_	START_	END_
1	TA	A	1	1	1	2
1	TA	X	1	1	1	1
1	TA	X	1	2	1	1
1	TA	X	1	2	1	2
1	TB	B	1	1	1	2
1	TB	X	1	1	2	2
1	TB	B	1	1	1	1
2	TA	X	1	1	2	2
2	TA	X	1	2	2	2
2	TB	X	1	2	2	2
2	TB	B	1	2	1	2
2	TB	B	1	2	1	1
1	TA	A	2	1	1	1
1	TA	X	2	2	1	1
1	TA	X	2	2	1	2
1	TB	B	2	1	1	2
1	TB	X	2	1	2	2
1	TB	B	2	1	1	1
1	TA	A	3	2	1	1
1	TA	X	3	2	1	2
1	TB	B	3	1	1	2
1	TB	B	3	1	2	2
1	TB	X	3	1	1	1
1	TA	A	4	2	1	2
1	TB	B	4	1	1	2
1	TB	B	4	1	2	2
1	TB	X	4	1	1	1
2	TA	X	4	1	2	2
2	TA	X	4	2	2	2
2	TB	B	4	2	2	2
2	TB	B	4	2	1	2
2	TB	X	4	2	1	1
2	TA	A	5	1	2	2
2	TA	X	5	2	2	2
2	TB	X	5	2	2	2
2	TB	B	5	2	1	2
2	TB	B	5	2	1	1
2	TA	A	6	2	2	2
2	TB	B	6	2	2	2
2	TB	B	6	2	1	2
2	TB	X	6	2	1	1

KEY_A	START_B	END_B	KEY_B	START_A	END_A
1	1	2	1	1	2
1	1	1	1	1	2
1	1	2	2	1	2
1	1	1	2	1	2
1	1	2	1	1	1
1	1	1	1	1	1
2	1	2	1	1	1
2	2	2	1	1	1
2	1	2	1	1	2
2	2	2	1	1	2
2	2	2	2	1	2
2	1	2	2	1	2
1	1	2	2	2	2
1	1	1	2	2	2
2	2	2	2	2	2
2	1	2	2	2	2

KEY_A	START_B	END_B	KEY_B	START_A	END_A
1	1	1	1	1	1
1	1	1	1	1	2
1	1	1	2	1	2
1	1	1	2	2	2
1	1	2	1	1	1
1	1	2	1	1	2
1	1	2	2	1	2
1	1	2	2	2	2
2	1	2	1	1	1
2	1	2	1	1	2
2	1	2	2	1	2
2	1	2	2	2	2
2	2	2	1	1	1
2	2	2	1	1	2
2	2	2	2	1	2
2	2	2	2	2	2

ORDER_	TBL_ID	KEY_	START_	END_
1	TA	1	1	2
1	TA	1	1	1
1	TA	2	1	1
1	TA	2	1	2
1	TB	1	1	2
1	TB	1	2	2
1	TB	1	1	1
2	TA	1	2	2
2	TA	2	2	2
2	TB	2	2	2
2	TB	2	1	2
2	TB	2	1	1

ORDER_	TBL_ID	CLASSIFIER	MATCH_NUMBER	KEY_	START_	END_
1	TA	A	1	1	1	2
1	TA	X	1	1	1	1
1	TA	X	1	2	1	1
1	TA	X	1	2	1	2
1	TB	B	1	1	1	2
1	TB	X	1	1	2	2
1	TB	B	1	1	1	1
2	TA	X	1	1	2	2
2	TA	X	1	2	2	2
2	TB	X	1	2	2	2
2	TB	B	1	2	1	2
2	TB	B	1	2	1	1
1	TA	A	2	1	1	1
1	TA	X	2	2	1	1
1	TA	X	2	2	1	2
1	TB	B	2	1	1	2
1	TB	X	2	1	2	2
1	TB	B	2	1	1	1
1	TA	A	3	2	1	1
1	TA	X	3	2	1	2
1	TB	B	3	1	1	2
1	TB	B	3	1	2	2
1	TB	X	3	1	1	1
1	TA	A	4	2	1	2
1	TB	B	4	1	1	2
1	TB	B	4	1	2	2
1	TB	X	4	1	1	1
2	TA	X	4	1	2	2
2	TA	X	4	2	2	2
2	TB	B	4	2	2	2
2	TB	B	4	2	1	2
2	TB	X	4	2	1	1
2	TA	A	5	1	2	2
2	TA	X	5	2	2	2
2	TB	X	5	2	2	2
2	TB	B	5	2	1	2
2	TB	B	5	2	1	1
2	TA	A	6	2	2	2
2	TB	B	6	2	2	2
2	TB	B	6	2	1	2
2	TB	X	6	2	1	1

KEY_A	START_B	END_B	KEY_B	START_A	END_A
1	1	2	1	1	2
1	1	1	1	1	2
1	1	2	2	1	2
1	1	1	2	1	2
1	1	2	1	1	1
1	1	1	1	1	1
2	1	2	1	1	1
2	2	2	1	1	1
2	1	2	1	1	2
2	2	2	1	1	2
2	2	2	2	1	2
2	1	2	2	1	2
1	1	2	2	2	2
1	1	1	2	2	2
2	2	2	2	2	2
2	1	2	2	2	2

KEY_A	START_B	END_B	KEY_B	START_A	END_A
1	1	1	1	1	1
1	1	1	1	1	2
1	1	1	2	1	2
1	1	1	2	2	2
1	1	2	1	1	1
1	1	2	1	1	2
1	1	2	2	1	2
1	1	2	2	2	2
2	1	2	1	1	1
2	1	2	1	1	2
2	1	2	2	1	2
2	1	2	2	2	2
2	2	2	1	1	1
2	2	2	1	1	2
2	2	2	2	1	2
2	2	2	2	2	2

ORDER_	TBL_ID	KEY_	START_	END_
1	TA	1	1	2
1	TA	1	1	1
1	TA	2	1	1
1	TA	2	1	2
1	TB	1	1	2
1	TB	1	2	2
1	TB	1	1	1
2	TA	1	2	2
2	TA	2	2	2
2	TB	2	2	2
2	TB	2	1	2
2	TB	2	1	1

ORDER_	TBL_ID	CLASSIFIER	MATCH_NUMBER	KEY_	START_	END_
1	TA	A	1	1	1	2
1	TA	X	1	1	1	1
1	TA	X	1	2	1	1
1	TA	X	1	2	1	2
1	TB	B	1	1	1	2
1	TB	X	1	1	2	2
1	TB	B	1	1	1	1
2	TA	X	1	1	2	2
2	TA	X	1	2	2	2
2	TB	X	1	2	2	2
2	TB	B	1	2	1	2
2	TB	B	1	2	1	1
1	TA	A	2	1	1	1
1	TA	X	2	2	1	1
1	TA	X	2	2	1	2
1	TB	B	2	1	1	2
1	TB	X	2	1	2	2
1	TB	B	2	1	1	1
1	TA	A	3	2	1	1
1	TA	X	3	2	1	2
1	TB	B	3	1	1	2
1	TB	B	3	1	2	2
1	TB	X	3	1	1	1
1	TA	A	4	2	1	2
1	TB	B	4	1	1	2
1	TB	B	4	1	2	2
1	TB	X	4	1	1	1
2	TA	X	4	1	2	2
2	TA	X	4	2	2	2
2	TB	B	4	2	2	2
2	TB	B	4	2	1	2
2	TB	X	4	2	1	1
2	TA	A	5	1	2	2
2	TA	X	5	2	2	2
2	TB	X	5	2	2	2
2	TB	B	5	2	1	2
2	TB	B	5	2	1	1
2	TA	A	6	2	2	2
2	TB	B	6	2	2	2
2	TB	B	6	2	1	2
2	TB	X	6	2	1	1

KEY_A	START_B	END_B	KEY_B	START_A	END_A
1	1	2	1	1	2
1	1	1	1	1	2
1	1	2	2	1	2
1	1	1	2	1	2
1	1	2	1	1	1
1	1	1	1	1	1
2	1	2	1	1	1
2	2	2	1	1	1
2	1	2	1	1	2
2	2	2	1	1	2
2	2	2	2	1	2
2	1	2	2	1	2
1	1	2	2	2	2
1	1	1	2	2	2
2	2	2	2	2	2
2	1	2	2	2	2