Description:
There seems to be a serious deficiency in the optimizer for dependent subqueries in the ON clause of a JOIN: This makes it impossible to execute some very common SQL queries to JOIN a row and its successor (with respect to a certain column) for larger tables.
A "momentarily constant" (regarding one execution of the dependent subquery) value from the outer query seems not to be identified as such. Even if EXPLAIN tells so, no index seems to be used in the subquery and a full table scan seems to be done for _every_ execution of the dependent subquery, even if that is absolutely not necessary.
How to repeat:
Execute the following test script and look at the execution times of the three SELECTs and at the output of the three EXPLAINs:
-- ----------------------------------------------------------------
--
-- CREATE THE TABLE AND FILL IT WITH 1'000'000 ROWS OF TEST DATA
--
CREATE TABLE IF NOT EXISTS test (i INT PRIMARY KEY);
DROP PROCEDURE IF EXISTS fill_test;
delimiter //
CREATE PROCEDURE fill_test(e INT)
BEGIN
DECLARE c INT DEFAULT 1;
WHILE c <= e DO
INSERT INTO test VALUES (c);
SET c := c + 1;
END WHILE;
END //
delimiter ;
CALL fill_test(1000000);
--
-- DO SOME QUERIES ON THE TABLE
-- (THE THIRD ONE IS THE BAD ONE)
--
EXPLAIN
SELECT MIN(i)
FROM test
WHERE i > 50;
EXPLAIN
SELECT o1.i AS o1,
o2.i AS o2
FROM test AS o1
INNER JOIN test AS o2
ON ( SELECT MIN(i)
FROM test
WHERE i > o1.i ) = o2.i
WHERE o1.i = 50;
EXPLAIN
SELECT o1.i AS o1, o2.i AS o2
FROM test AS o1
INNER JOIN test AS o2
ON ( SELECT MIN(i)
FROM test
WHERE i > o1.i ) = o2.i
WHERE o1.i BETWEEN 50 AND 51;
--
-- EXPLAIN THE THREE QUERIES
--
EXPLAIN
SELECT MIN(i)
FROM test
WHERE i > 50;
EXPLAIN
SELECT o1.i AS o1,
o2.i AS o2
FROM test AS o1
INNER JOIN test AS o2
ON ( SELECT MIN(i)
FROM test
WHERE i > o1.i ) = o2.i
WHERE o1.i = 50;
EXPLAIN
SELECT o1.i AS o1, o2.i AS o2
FROM test AS o1
INNER JOIN test AS o2
ON ( SELECT MIN(i)
FROM test
WHERE i > o1.i ) = o2.i
WHERE o1.i BETWEEN 50 AND 51;
--
-- CLEAN UP
--
DROP PROCEDURE fill_test;
DROP TABLE test;
-- ----------------------------------------------------------------
That's the output I get for the three SELECTs:
+--------+
| MIN(i) |
+--------+
| 51 |
+--------+
1 row in set (0.00 sec)
+----+----+
| o1 | o2 |
+----+----+
| 50 | 51 |
+----+----+
1 row in set (0.00 sec)
+----+----+
| o1 | o2 |
+----+----+
| 50 | 51 |
| 51 | 52 |
+----+----+
2 rows in set (3.15 sec)
The first two queries execute in almost no time, the third one needs over three seconds.
Now look at the EXPLAIN output for the three queries:
+----+-------------+-------+------+---------------+------+---------+------+------+------------------------------+
| id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra |
+----+-------------+-------+------+---------------+------+---------+------+------+------------------------------+
| 1 | SIMPLE | NULL | NULL | NULL | NULL | NULL | NULL | NULL | Select tables optimized away |
+----+-------------+-------+------+---------------+------+---------+------+------+------------------------------+
+----+--------------------+-------+-------+---------------+---------+---------+-------+------+------------------------------+
| id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra |
+----+--------------------+-------+-------+---------------+---------+---------+-------+------+------------------------------+
| 1 | PRIMARY | o1 | const | PRIMARY | PRIMARY | 4 | const | 1 | Using index |
| 1 | PRIMARY | o2 | const | PRIMARY | PRIMARY | 4 | const | 1 | Using index |
| 2 | DEPENDENT SUBQUERY | NULL | NULL | NULL | NULL | NULL | NULL | NULL | Select tables optimized away |
+----+--------------------+-------+-------+---------------+---------+---------+-------+------+------------------------------+
+----+--------------------+-------+--------+---------------+---------+---------+------+---------+--------------------------+
| id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra |
+----+--------------------+-------+--------+---------------+---------+---------+------+---------+--------------------------+
| 1 | PRIMARY | o1 | range | PRIMARY | PRIMARY | 4 | NULL | 2 | Using where; Using index |
| 1 | PRIMARY | o2 | eq_ref | PRIMARY | PRIMARY | 4 | func | 1 | Using where; Using index |
| 2 | DEPENDENT SUBQUERY | test | index | PRIMARY | PRIMARY | 4 | NULL | 1000000 | Using where; Using index |
+----+--------------------+-------+--------+---------------+---------+---------+------+---------+--------------------------+
3 rows in set (0.00 sec)
In the first two queries the dependent subquery can even be optimized away completely (in the second query the constant value for o1.i from the WHERE clause in the outer query will be propagated into the subquery) which is good and actually the expected behaviour. In the third query we ask for a range of rows in the outer query. Of course the dependent subquery now needs to be executed "as a function" once for every possible row from o1 (only two rows in this example) to find the according row from o2. The strange behaviour now is, that for every one of the rows from the outer query, the subquery has to scan _all_ the rows from the table (1'000'000). The EXPLAIN shows that the PRIMARY KEY is used in the subquery - but then no full table scan should be necessary. Only one row from the index should be retrieved, as the value for o1.i from the outer query actually is a constant for every single execution of the subquery.
Suggested fix:
The execution plan should be:
* Take one row from o1
** Execute dependent subquery with the constant value o1.i _using_ the KEY
** Find the according row from o2
Description: There seems to be a serious deficiency in the optimizer for dependent subqueries in the ON clause of a JOIN: This makes it impossible to execute some very common SQL queries to JOIN a row and its successor (with respect to a certain column) for larger tables. A "momentarily constant" (regarding one execution of the dependent subquery) value from the outer query seems not to be identified as such. Even if EXPLAIN tells so, no index seems to be used in the subquery and a full table scan seems to be done for _every_ execution of the dependent subquery, even if that is absolutely not necessary. How to repeat: Execute the following test script and look at the execution times of the three SELECTs and at the output of the three EXPLAINs: -- ---------------------------------------------------------------- -- -- CREATE THE TABLE AND FILL IT WITH 1'000'000 ROWS OF TEST DATA -- CREATE TABLE IF NOT EXISTS test (i INT PRIMARY KEY); DROP PROCEDURE IF EXISTS fill_test; delimiter // CREATE PROCEDURE fill_test(e INT) BEGIN DECLARE c INT DEFAULT 1; WHILE c <= e DO INSERT INTO test VALUES (c); SET c := c + 1; END WHILE; END // delimiter ; CALL fill_test(1000000); -- -- DO SOME QUERIES ON THE TABLE -- (THE THIRD ONE IS THE BAD ONE) -- EXPLAIN SELECT MIN(i) FROM test WHERE i > 50; EXPLAIN SELECT o1.i AS o1, o2.i AS o2 FROM test AS o1 INNER JOIN test AS o2 ON ( SELECT MIN(i) FROM test WHERE i > o1.i ) = o2.i WHERE o1.i = 50; EXPLAIN SELECT o1.i AS o1, o2.i AS o2 FROM test AS o1 INNER JOIN test AS o2 ON ( SELECT MIN(i) FROM test WHERE i > o1.i ) = o2.i WHERE o1.i BETWEEN 50 AND 51; -- -- EXPLAIN THE THREE QUERIES -- EXPLAIN SELECT MIN(i) FROM test WHERE i > 50; EXPLAIN SELECT o1.i AS o1, o2.i AS o2 FROM test AS o1 INNER JOIN test AS o2 ON ( SELECT MIN(i) FROM test WHERE i > o1.i ) = o2.i WHERE o1.i = 50; EXPLAIN SELECT o1.i AS o1, o2.i AS o2 FROM test AS o1 INNER JOIN test AS o2 ON ( SELECT MIN(i) FROM test WHERE i > o1.i ) = o2.i WHERE o1.i BETWEEN 50 AND 51; -- -- CLEAN UP -- DROP PROCEDURE fill_test; DROP TABLE test; -- ---------------------------------------------------------------- That's the output I get for the three SELECTs: +--------+ | MIN(i) | +--------+ | 51 | +--------+ 1 row in set (0.00 sec) +----+----+ | o1 | o2 | +----+----+ | 50 | 51 | +----+----+ 1 row in set (0.00 sec) +----+----+ | o1 | o2 | +----+----+ | 50 | 51 | | 51 | 52 | +----+----+ 2 rows in set (3.15 sec) The first two queries execute in almost no time, the third one needs over three seconds. Now look at the EXPLAIN output for the three queries: +----+-------------+-------+------+---------------+------+---------+------+------+------------------------------+ | id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra | +----+-------------+-------+------+---------------+------+---------+------+------+------------------------------+ | 1 | SIMPLE | NULL | NULL | NULL | NULL | NULL | NULL | NULL | Select tables optimized away | +----+-------------+-------+------+---------------+------+---------+------+------+------------------------------+ +----+--------------------+-------+-------+---------------+---------+---------+-------+------+------------------------------+ | id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra | +----+--------------------+-------+-------+---------------+---------+---------+-------+------+------------------------------+ | 1 | PRIMARY | o1 | const | PRIMARY | PRIMARY | 4 | const | 1 | Using index | | 1 | PRIMARY | o2 | const | PRIMARY | PRIMARY | 4 | const | 1 | Using index | | 2 | DEPENDENT SUBQUERY | NULL | NULL | NULL | NULL | NULL | NULL | NULL | Select tables optimized away | +----+--------------------+-------+-------+---------------+---------+---------+-------+------+------------------------------+ +----+--------------------+-------+--------+---------------+---------+---------+------+---------+--------------------------+ | id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra | +----+--------------------+-------+--------+---------------+---------+---------+------+---------+--------------------------+ | 1 | PRIMARY | o1 | range | PRIMARY | PRIMARY | 4 | NULL | 2 | Using where; Using index | | 1 | PRIMARY | o2 | eq_ref | PRIMARY | PRIMARY | 4 | func | 1 | Using where; Using index | | 2 | DEPENDENT SUBQUERY | test | index | PRIMARY | PRIMARY | 4 | NULL | 1000000 | Using where; Using index | +----+--------------------+-------+--------+---------------+---------+---------+------+---------+--------------------------+ 3 rows in set (0.00 sec) In the first two queries the dependent subquery can even be optimized away completely (in the second query the constant value for o1.i from the WHERE clause in the outer query will be propagated into the subquery) which is good and actually the expected behaviour. In the third query we ask for a range of rows in the outer query. Of course the dependent subquery now needs to be executed "as a function" once for every possible row from o1 (only two rows in this example) to find the according row from o2. The strange behaviour now is, that for every one of the rows from the outer query, the subquery has to scan _all_ the rows from the table (1'000'000). The EXPLAIN shows that the PRIMARY KEY is used in the subquery - but then no full table scan should be necessary. Only one row from the index should be retrieved, as the value for o1.i from the outer query actually is a constant for every single execution of the subquery. Suggested fix: The execution plan should be: * Take one row from o1 ** Execute dependent subquery with the constant value o1.i _using_ the KEY ** Find the according row from o2