Is it possible to join two tables by matching value in the first towards a range in the second while forcing the optimizer to use index instead of table scan?
Table A has an integer column val. Table B has lo and hi columns presenting a range. The ranges in B do not overlap.
Example DDL:
drop schema if exists dropMe; create schema dropMe; use dropMe;
create table A ( id serial, val int );
create table B ( id serial, lo int, hi int, primary key ( lo, hi ) );
Example query:
select A.id aId, B.id bId from A join B on A.val between B.lo and B.hi;
The issue is complexity. Without the use of the b-tree index the complexity is O(N*M) where N = 700K for table A and M = 2 million for table B, thus the DB engine processes 1.4 trillion combinations before returning the result. It is not computable in a reasonable time.
My goal is to force the optimizer to use an index and get a complexity of O(N*log2(M)), thus 10 million steps. In other words, 140,000 times faster, or every second from the fast execution plan will be equal to 38 hours in the slow.
Here I am, trying to squeeze 2 days in a second. Please help.
The test code follows. It required MySQL version 8 or later to run the recursion.
# init
set @testRecotds = 100000;
set cte_max_recursion_depth = @testRecotds;
# DDL - creates tmp schema then creates A and B tables
drop schema if exists dropMe; create schema dropMe; use dropMe;
create table A ( id serial, val int unique );
create table B ( id serial, lo int, hi int, primary key ( lo, hi ) );
# DML - inserts semi-random 100k integers in A table and ranges in B table
insert into A( val ) with recursive r as ( select 1 i, 1 n union all select i + 1, n + 1 + 80 * rand() from r where i < @testRecotds ) select n from r;
insert into B( lo, hi )
with recursive
r as (
select 1 i, 1 lo, 1 + 40 * rand() hi
union all
select i + 1, lo + 41 + 40 * rand() nLo, ( select nLo ) + 40 * rand()
from r
where i < @testRecotds
)
select lo, hi from r;
# The actual query - optimize the join
select count( * ) from A join B on val between lo and hi;
# MySQL uses full table scan on A and full index scan B on id column, which has no practical performance improvement
drop schema dropMe;
I tried to find a workaround and found that Postgres has a simple solution, but failed to find a solution for MySQL.
The test code below targets a subset of the issue above, it is simplified. Solving it will help resolve the issue above if there is no better direct solution.
Two tables x and y. Both contain 100k records with semi-random integers. The goal is for every integer in y table to find the highest integer in x table that is equal or smaller than the current integer from y table.
Postgres joined and summed all the integers for 1 second, MySQL for 27 minutes and 6 seconds. Internally MySQL scans both tables, whereas PG scans one table and uses the index on the second.
-- MySQL --
set cte_max_recursion_depth = 100000;
drop schema if exists dropMe; create schema dropMe; use dropMe;
create table x( x int primary key );
create table y( y int );
insert into x with recursive r as ( select 1 i, 1 n union all select i + 1, n + 1 + 40 * rand() from r where i < 100000 ) select n from r;
insert into y with recursive r as ( select 1 i, 1 n union all select i + 1, n + 1 + 40 * rand() from r where i < 100000 ) select n from r;
select sum( y ), sum( x ) from ( select y, ( select max( x ) from x where x <= y ) x from y ) z;
drop schema dropMe;
-- PG --
drop schema if exists dropMe; create schema dropMe;
create table dropMe.x( x int primary key );
create table dropMe.y( y int );
insert into dropMe.x with recursive r as ( select 1 i, 1 n union all select i + 1, n + 1 + ( 40 * random() ) :: int from r where i < 100000 ) select n from r;
insert into dropMe.y with recursive r as ( select 1 i, 1 n union all select i + 1, n + 1 + ( 40 * random() ) :: int from r where i < 100000 ) select n from r;
select sum( y ), sum( x ) from ( select y, ( select max( x ) from dropMe.x where x <= y ) x from dropMe.y ) z; -- 1 second
drop schema dropMe;
Have fun guys. It gave me more than enough, so I share it here. 🙂
ADDED ON 2019-12-30
The following test code implements Rick James suggestion to use a function. The upper and lower boundaries are in the same row and the function returns three columns from the range table.
# init
set @testRecords = 100000;
set cte_max_recursion_depth = @testRecords;
set group_concat_max_len = @testRecords;
# DDL - creates tmp schema then creates A and B tables
drop schema if exists dropMe; create schema dropMe; use dropMe;
create table A ( id serial, val int primary key );
create table B ( id serial, lo int primary key, hi int, c1 int, c2 int, c3 char );
# DML - inserts semi-random 100k integers in A table and ranges in B table
insert into A( val ) with recursive r as ( select 1 i, 1 n union all select i + 1, n + 2 + 80 * rand() from r where i < @testRecords ) select n from r;
insert into B( lo, hi, c1, c2, c3 )
with recursive
r as (
select 1 i, 1 lo, floor( 40 * rand() ) hi, 10 * rand() c1, 10000 * rand() c2, char( 65 + floor( 26 * rand() ) ) c3
union all
select i + 1, hi + 1 + 40 * rand(), hi + 41 + 40 * rand(), 10 * rand() c1, 10000 * rand() c2, char( 65 + floor( 26 * rand() ) ) c3
from r
where i < @testRecords
)
select lo, hi, c1, c2, c3 from r;
# function definition
delimiter !!
create function searchB( val int ) returns json
begin
return ( select case when val <= hi then json_object( 'c1', c1, 'c2', c2, 'c3', c3 ) end from B where lo <= val order by lo desc limit 1 );
end !!
delimiter ;
## TESTS follow ##
# The original query - simple and slow
select count( * ), sum( c1 ), sum( c2 ), group_concat( c3 separator '' )
from A join B on val between lo and hi;
# MySQL optimizer applies full scans on A and B tables, ignoring the indexes the query runs for 13:56.138
# using function - the following query run for 5.558 seconds
select count( * ), sum( c1 ), sum( c2 ), group_concat( c3 separator '' )
from A join json_table( searchB( A.val ), '$' columns( c1 int path '$.c1', c2 int path '$.c2', c3 char path '$.c3' ) ) X;
# the optimized uses the primary key index on table B thus reducing the execution time 150 times
# drops the test schema
drop schema dropMe;
SERIAL
column have to be the primary key?A.val
do it?