mysql : inner join takes 3 minutes

Question

I had a similar question open on SO for postgres - now having the same issue with mysql..

I have two tables -

Table A : 1MM rows, AsOfDate, Id, BId (foreign key to table B)

Table B : 50k rows, Id, Flag, ValidFrom, ValidTo

Table A contains multiple records per day between 2011/01/01 and 2011/12/31 across 100 BId's. Table B contains multiple non overlapping (between validfrom and validto) records for 100 Bids.

The task of the join will be to return the flag that was active for the BId on the given AsOfDate.

select 
    a.AsOfDate, b.Flag 
from 
    A a inner Join B b on 
        a.BId = b.Id and b.ValidFrom <= a.AsOfDate and b.ValidTo >= a.AsOfDate
where
    a.AsOfDate >= 20110101 and a.AsOfDate <= 20111231

This query takes over 3 minutes on a very high end server (+3Ghz) with 64Gb of memory.

+-------+-------------------------+
| Table | Create Table            
|
+-------+-------------------------+
| a     | CREATE TABLE `a` (
  `asofdate` int(4) NOT NULL,
  `bid` int(4) NOT NULL,
  KEY `asofdate_bid` (`asofdate`,`bid`),
  KEY `bid` (`bid`),
  KEY `bid_asofdate` (`bid`,`asofdate`)
) ENGINE=InnoDB DEFAULT CHARSET=latin1 |
+-------+-------------------------+

+-------+-------------------------+
| Table | Create Table            |
+-------+-------------------------+
| b     | CREATE TABLE `b` (
  `key` int(4) NOT NULL,
  `id` int(4) NOT NULL,
  `flag` char(1) NOT NULL,
  `validfrom` int(4) NOT NULL,
  `validto` int(4) NOT NULL,
  KEY `id` (`id`),
  KEY `validfrom` (`validfrom`),
  KEY `validfrom_id` (`validfrom`,`id`),
  KEY `id_validfrom` (`id`,`validfrom`)
) ENGINE=InnoDB DEFAULT CHARSET=latin1 |
+-------+-------------------------+

Here is the explain :

mysql> explain select count(1) from a a inner join b b on a.bid = b.id and b.validfrom <= a.asofdate and b.validto >= a.asofdate where a.asofdate >= 20120101 and a.asofdate <= 20121231;

+----+-------------+-------+------+----------------------------------------+--------------+---------+----------+-------+-----------+
| id | select_type | table | type | possible_keys                          | key          | key_len | ref      | rows  | Extra
+----+-------------+-------+------+----------------------------------------+--------------+---------+----------+-------+-----------+
|  1 | SIMPLE      | b     | ALL  | id,validfrom,validfrom_id,id_validfrom | NULL         | NULL    | NULL     | 50510 |                          |
|  1 | SIMPLE      | a     | ref  | asofdate_bid,bid,bid_asofdate          | bid_asofdate | 4       | foo.b.id |  1433 | Using where; Using index |
+----+-------------+-------+------+----------------------------------------+--------------+---------+----------+-------+-----------+

SqlServer express and Postgres take ~300ms to execute the above query. I'm in the process of deciding on a multi-terabyte installation and it's not looking good for mySql (my preferred db) at the moment!

execution plan for the suggested queries

remove the join conditions (3 minutes):

mysql> EXPLAIN SELECT count(1) FROM a a 
    -> INNER JOIN b b ON a.bid = b.id 
    -> WHERE (a.asofdate >= 20120101 and a.asofdate <= 20121231) 
    ->  AND (b.validfrom <= a.asofdate AND b.validto >= a.asofdate);
+----+-------------+-------+------+----------------------------------------+--------------+---------+----------+-------+--------------------------+
| id | select_type | table | type | possible_keys                          | key          | key_len | ref      | rows  | Extra                    |
+----+-------------+-------+------+----------------------------------------+--------------+---------+----------+-------+--------------------------+
|  1 | SIMPLE      | b     | ALL  | id,validfrom,validfrom_id,id_validfrom | NULL         | NULL    | NULL     | 50510 |                          |
|  1 | SIMPLE      | a     | ref  | asofdate_bid,bid,bid_asofdate          | bid_asofdate | 4       | foo.b.id |  1433 | Using where; Using index |
+----+-------------+-------+------+----------------------------------------+--------------+---------+----------+-------+--------------------------+
2 rows in set (0.02 sec)

use straight_join actually changes the query plan and causes the time to go to 6 minutes:

mysql> EXPLAIN SELECT count(1) FROM a a  STRAIGHT_JOIN b b ON a.bid = b.id  WHERE (a.asofdate >= 20120101 and a.asofdate <= 20121231)   AND (b.validfrom <= a.asofdate AND b.validto >= a.asofdate);
+----+-------------+-------+-------+----------------------------------------+--------------+---------+-----------+--------+--------------------------+
| id | select_type | table | type  | possible_keys                          | key          | key_len | ref       | rows   | Extra                    |
+----+-------------+-------+-------+----------------------------------------+--------------+---------+-----------+--------+--------------------------+
|  1 | SIMPLE      | a     | range | asofdate_bid,bid,bid_asofdate          | asofdate_bid | 4       | NULL      | 500296 | Using where; Using index |
|  1 | SIMPLE      | b     | ref   | id,validfrom,validfrom_id,id_validfrom | id           | 4       | foo.a.bid |    255 | Using where              |
+----+-------------+-------+-------+----------------------------------------+--------------+---------+-----------+--------+--------------------------+

Answer 1

Here is your original query

select 
    a.AsOfDate, b.Flag 
from 
    A a inner Join B b on 
        a.BId = b.Id and b.ValidFrom <= a.AsOfDate and b.ValidTo >= a.AsOfDate
where
    a.AsOfDate >= 20110101 and a.AsOfDate <= 20111231

I would suggest refactoring your query in this instance:

select 
    a.AsOfDate, b.Flag 
from
    (
        select * from A
        WHERE AsOfDate >= 20110101
        AND AsOfDate <= 20111231
    ) a INNER JOIN B b ON a.bid=b.id
    AND b.validfrom <= a.asofdate
    AND b.validto   >= a.asofdate
;

That way, the A side's date range ( 20110101 - 20111231 ) gets handled first before the JOIN. An additional benefit of the refactored query is that the JOIN of A and B involves a smaller subset of A.

If you feel uncomfortable with the refactored query, here is another suggestion: switch the range-based WHERE and JOIN clauses

select 
    a.AsOfDate, b.Flag 
from 
    A a inner Join B b on 
        a.BId = b.Id and a.AsOfDate >= 20110101 and a.AsOfDate <= 20111231
where
    b.ValidFrom <= a.AsOfDate and b.ValidTo >= a.AsOfDate

Give it a Try !!!

Answer 2

My guess is that your join condition is confusing the the MySQL optimizer, and as the explain shows, it's loading the entire b table. What does this give you:

EXPLAIN SELECT count(1) FROM a a 
INNER JOIN b b ON a.bid = b.id 
WHERE (a.asofdate >= 20120101 and a.asofdate <= 20121231) 
 AND (b.validfrom <= a.asofdate AND b.validto >= a.asofdate);

Sidenote, you shouldn't need the KEY (bid) on table A, as KEY bid_asofdate (bid, asofdate) will take care of this, and the way InnoDB handles indexing, this just takes up more space than is needed.

Some further ramblings on indexing. Why don't you define a Primary Key in any of the tables? I would update your table b like this:

CREATE TABLE `b` (
  `key` int(4) NOT NULL PRIMARY KEY,
  `id` int(4) NOT NULL,
  `flag` char(1) NOT NULL,
  `validfrom` int(4) NOT NULL,
  `validto` int(4) NOT NULL,
  KEY `validfrom_id` (`validfrom`,`id`),
  KEY `id_validfrom_validto` (`id`,`validfrom`, `validto`)
) ENGINE=InnoDB DEFAULT CHARSET=latin1

with the assumption that id is really not the primary key and key is actually useful :)

Answer 3

First, try adding another index on table b that includes all columns in the query (id, validfrom, validto) should help.

Second, try adding another criterion in the where clause constraining table b on the date constants. This may help limit the number of rows scanned from b:

AND (b.validfrom <= 20120101 AND b.validto >= 20121231)

Lastly, MySQL doesn't have descending indexing capabilities. If it did you could create an index on id ascending, validfrom ascending, and validto descending which would align better with the query constraints. Such an index would allow for more efficient index scanning in the case.

The common workaround for this is to add a reverse column for the column you wish to index in descending order. See http://stackoverflow.com/questions/1255143/workaround-for-missing-descending-index-feature-in-mysql for an example.

In this case, add a reversevalidto column to table b. Then populate it with -validto. Next create an index on the id, validfrom, and reversevalidfrom columns. Lastly, replace every occurrence of b.validto >= with b.reversevalidto <= in the query.

Answer 4

even though subselects often, not always, perform worse in MySQL you could give the following a try

Select * from
(
select 
    a.AsOfDate,(Select  Flag from b where ValidTo >= a.AsOfDate order by ValidTo  limit 0, 1) as Flag
from 
    A 
where
    a.AsOfDate >= 20110101 and a.AsOfDate <= 20111231
)
where Flag is not NULL