1

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;
10
  • What version of MySQL, and what engine for the table?
    – Strawberry
    Dec 17, 2019 at 20:32
  • Can you really create the B table like that? Doesn't the SERIAL column have to be the primary key?
    – Barmar
    Dec 17, 2019 at 20:32
  • Wouldn't adding an index on A.val do it?
    – Barmar
    Dec 17, 2019 at 20:37
  • @Strawberry, my playground runs on MySQL 8.0.18. Dec 17, 2019 at 22:06
  • @Barmar - No, serial automatically makes it unique, you can make it the primary key too or make other column(s) the primary key. Making val column the primary key has no practical impact on performance. Please run the example code that I added. Dec 17, 2019 at 22:12

1 Answer 1

1

There is an O(1) solution for finding whether one A is in B, but it requires a different way of storing the non-overlaping ranges of table B. By having all possible ranges included in B and then keeping either lo or hi since the other one is redundant with the adjacent row. (I pick lo.) Each row would say whether it is included or is a gap. Then a simple

SELECT included FROM B WHERE some_val >= lo ORDER BY lo DESC LIMIT 1

will say whether val is "included" in B. Note: B should have PRIMARY KEY(lo).

For more discussion, see http://mysql.rjweb.org/doc.php/ipranges , especially the code for IPv4 ranges, which could be a model for B if the ranges include the entire INT UNSIGNED range.

Presumably, the best way to do this for all values in A is

SELECT id
    FROM A
    WHERE ( SELECT included FROM B
              WHERE some_val >= lo
              ORDER BY lo DESC LIMIT 1 )

(I am assuming that included is true (1) or false (0). In the reference, I was returning an "owner_id", which was 0 for "not owned".)

This should involve a scan of A, but (roughly) a point-query into B for each A.

(OP devised this test case:)

Setup:

create table A (
    id serial, 
    val int );
create table B (
    id serial, 
    lo int primary key, 
    included boolean );
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 < 100000
  ) select n from r;
insert into B( lo, included )
  with recursive r as
  ( select 1 i, 1 n
    union all
    select i + 1, n + 1 + 40 * rand() from r where i < 200000
  ) select n, i % 2 from r;

Test:

select count( * ) from A where
   ( select B.included from B
        where B.lo <= A.val order by B.lo desc limit 1
   );

Hmmm... This seems to be a case where changing from a subquery to a Function greatly speeds up the query:

CREATE DEFINER = `ip`@`localhost` FUNCTION Included(
        _val INT UNSIGNED)
    RETURNS BOOLEAN
    DETERMINISTIC
BEGIN
    DECLARE _included BOOLEAN;
    SELECT included INTO _included
        FROM B
        WHERE lo <= _val
        ORDER BY lo DESC
        LIMIT 1;
    RETURN _included;
END //
DELIMITER ;

And change query to:

    select count( * ) from A
        WHERE Included(A.val);

As "proof", I see that Handler_read_prev was about N*M beforehand, but afterward Handler_read_prev and Handler_read_rnd_next were about the size N. (FLUSH STATUS and SHOW STATUS LIKE 'Handler%' are handy for performance testing with small datasets.)

6
  • Thank you for the suggestion, however, it does not seem to solve the issue. I test it with 100k values in table A and 100k ranges. Each range is represented by 2 rows in B. The odd rows are included and the even excluded. There is a primary key on lo column. MySQL optimizer ignores the possible index search and goes for a consecutive scan on both tables. As result the complexity is O( N * M ) -> 100k * 200k = 20 billion steps and the example bellow runs for 36 minutes instead of sub-second time with desired complexity of O( N * log2( M ) ) -> 100k * 17.6 -> ~1.8 million steps. Dec 26, 2019 at 16:43
  • set cte_max_recursion_depth = 200000; drop table if exists A, B; create table A ( id serial, val int ); create table B ( id serial, lo int primary key, included boolean ); 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 < 100000 ) select n from r; insert into B( lo, included ) with recursive r as ( select 1 i, 1 n union all select i + 1, n + 1 + 40 * rand() from r where i < 200000 ) select n, i % 2 from r; select count( * ) from A where ( select included from B where lo <= val order by lo desc limit 1 ); Dec 26, 2019 at 16:46
  • @user9526573 - See update. It seems that using the Function is important for performance.
    – Rick James
    Dec 26, 2019 at 23:50
  • Well, replacing a join with a user-defined function with an independent query inside speeded up the query 406 times. It feels like a pretty clumsy way to force the execution planner to use an index, but it works. I removed the deterministic (drops the cache, not need in my case) and the function variable and got an additional 15% performance increase. Dec 27, 2019 at 17:12
  • @user9526573 - Good. I was disappointed that the JOIN failed to optimize well, and I could not see a way to reformulate it. So, I, too, was surprised at how much better the Function was. I was not sure about DETERMINISTIC. Please post your working version of the Function.
    – Rick James
    Dec 27, 2019 at 22:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.