Bug #46135 LIMIT + JOIN problem
Submitted: 12 Jul 2009 19:03 Modified: 24 Jul 2010 21:19
Reporter: Pavel Bazanov Email Updates:
Status: Verified Impact on me:
None 
Category:MySQL Server: Optimizer Severity:S2 (Serious)
Version:5.0, 5.1, next, 6.0.0, 6.0.2, 5.1.36 OS:Any
Assigned to: CPU Architecture:Any
Tags: join, limit, stored function
Triage: Triaged: D5 (Feature request)

[12 Jul 2009 19:03] Pavel Bazanov
Description:
Hello,
Imaging such a query:

SELECT ol.ID, ol.PartNumber, SlowFunction(ol.ID)
FROM orderlines ol
WHERE SomeFilter
LIMIT 1;

This query works great. The server finds rows matching WHERE filter, selects only 1 row and executes SlowFunction(ol.ID) only for that row.

But what happens if we add a simple join to the query?:

SELECT ol.ID, ol.PartNumber, SlowFunction(ol.ID)
FROM orderlines ol
INNER JOIN orders o ON (o.ID = ol.OrderID)
WHERE SomeFilter
LIMIT 1;

The query becomes very-very slow. SlowFunction is now executed for ALL rows matching WHERE filter! So, if 100K rows match WHERE filter, SlowFunction() will be executed 100K times, not 1 time!!!

How to repeat:
See description.
[12 Jul 2009 19:11] Pavel Bazanov
PS. Temporary workaround:

SELECT t.*, SlowFunction(t.ID) 
FROM
(SELECT ol.ID, ol.PartNumber
FROM orderlines ol
INNER JOIN orders o ON (o.ID = ol.OrderID)
WHERE SomeFilter
LIMIT 1);
[12 Jul 2009 19:46] Peter Laursen
In my (recent!) understanding this is not a bug. .I posted a similar bug report (with UNION - not JOIN) a few weeks ago here:
http://bugs.mysql.com/bug.php?id=45907
.. but was taught about how the parser interprets such ambigous statements. 

I think that if you do not use paranthesis'es (as in your workaround) it will be executed like 

(SELECT ol.ID, ol.PartNumber, SlowFunction(ol.ID)
FROM orderlines ol
INNER JOIN orders o ON (o.ID = ol.OrderID)
WHERE SomeFilter)
LIMIT 1;
[12 Jul 2009 21:40] Pavel Bazanov
No, this is an incorrect behavior.
In all other DBMS such a query works as expected, and the function is executed only LIMIT/TOP times.
[13 Jul 2009 6:01] Valeriy Kravchuk
Thank you for the problem report. Please, send the results of:

EXPLAIN SELECT ol.ID, ol.PartNumber, SlowFunction(ol.ID)
FROM orderlines ol
INNER JOIN orders o ON (o.ID = ol.OrderID)
WHERE SomeFilter
LIMIT 1;
[13 Jul 2009 12:47] Pavel Bazanov
EXPLAIN SELECT SlowFunction(parts.ID)
FROM orderlines ol
INNER JOIN orders o ON (o.ID = ol.OrderID) 
WHERE ol.Closed = false AND ol.TS >= '2009-06-01' 
ORDER BY ol.ID  
LIMIT 1

--------------------------------------------------------------------------
id		1			1
select_type	SIMPLE			SIMPLE
table		o			ol
type		index			ref
possible_keys	PRIMARY			FK_orderlines_OrderID_TO_orders_ID
key		PRIMARY			FK_orderlines_OrderID_TO_orders_ID
key_len		4			5
ref		NULL			rabase.o.ID
rows		15636			12
Extra		Using index; 
		Using temporary; 
		Using filesort		Using where
[13 Jul 2009 12:49] Pavel Bazanov
EXPLAIN SELECT SlowFunction(ol.ID) ... *** (mistyped in a preceeding comment)
[13 Jul 2009 13:06] Valeriy Kravchuk
Please, send SHOW CREATE TABLE results for both tables also. I assume they are InnoDB ones. Send also the results of:

SELECT count(*)
FROM orderlines ol
INNER JOIN orders o ON (o.ID = ol.OrderID) 
WHERE ol.Closed = false AND ol.TS >= '2009-06-01';

This may be related to infamous bug #28404...
[14 Jul 2009 16:13] Pavel Bazanov
This is very strange... When I added index on column in where clause, it started to work as expected - i.e. function is executed only 1 time. But after I removed the index it still works correctly... Or, for example, if I dump the database, drop it, and then import it back - the problem may not appear anymore.
I feel it's somehow related to "estimated execution time"...

mysql> SHOW CREATE TABLE orders;
+------------------------------------------------------------------------------+
CREATE TABLE `orders` (
  `ID` int(11) NOT NULL AUTO_INCREMENT,
  `CustomerID` int(11) unsigned NOT NULL,
  `OrderN` int(11) DEFAULT NULL,
  `IsDDP` tinyint(1) DEFAULT '0',
  `AddedTS` timestamp NOT NULL DEFAULT CURRENT_TIMESTAMP,
  PRIMARY KEY (`ID`),
  UNIQUE KEY `OrderN_CustomerID` (`CustomerID`,`OrderN`),
  KEY `CustomerID` (`CustomerID`),
  CONSTRAINT `FK_Orders_CustomerID_TO_Customers_ID` FOREIGN KEY (`CustomerID`) R
EFERENCES `customers` (`ID`) ON DELETE CASCADE ON UPDATE CASCADE
) ENGINE=InnoDB AUTO_INCREMENT=31768 DEFAULT CHARSET=utf8 |
+------------------------------------------------------------------------------+
1 row in set (0.00 sec)

mysql> SHOW CREATE TABLE orderlines;
+------------------------------------------------------------------------------+
 CREATE TABLE `orderlines` (
  `ID` int(11) unsigned NOT NULL AUTO_INCREMENT,
  `PartN` varchar(20) DEFAULT NULL,
  `ManufacturerID` int(11) DEFAULT NULL,
  `Quantity` smallint(5) DEFAULT '0',
  `OrderDate` datetime DEFAULT NULL,
  `TS` timestamp NOT NULL DEFAULT CURRENT_TIMESTAMP,
  `Closed` tinyint(1) NOT NULL DEFAULT '0',
  `OrderID` int(11) DEFAULT NULL,
  PRIMARY KEY (`ID`),
  KEY `OrderID` (`OrderID`),
  KEY `ManufacturerID` (`ManufacturerID`),
  CONSTRAINT `FK_orderlines_OrderID_TO_orders_ID` FOREIGN KEY (`OrderID`) REFERE
NCES `orders` (`ID`) ON DELETE CASCADE ON UPDATE CASCADE
) ENGINE=InnoDB AUTO_INCREMENT=560146 DEFAULT CHARSET=utf8 ROW_FORMAT=DYNAMIC |
+------------------------------------------------------------------------------+
1 row in set (0.00 sec)

mysql> SELECT count(*)
    -> FROM orderlines ol
    -> INNER JOIN orders o ON (o.ID = ol.OrderID)
    -> WHERE ol.Closed = false AND ol.TS >= '2009-06-01';
+----------+
| count(*) |
+----------+
|    72258 |
+----------+
1 row in set (0.00 sec)
[25 Jul 2009 15:58] Pavel Bazanov
Any news?
[26 Jul 2009 9:48] Valeriy Kravchuk
I assume that this problem happens when the ol table (the one you call function on column from...) is NOT the first one in EXPLAIN results for the query (and, thus, "Using filesort" is present). In this case server creates temporary table with result set (and call your functiion many times during that process) and then its content is sorted according to the ORDER BY and LIMIT 1 is applied.

So, I think, the result depends on execution plan. Please, check if EXPLAIN gives different results for the query when function is called once vs. many times.

There are many possible reasons for different execution plans used for the same query, from some known bugs to just imperfect statistics (and it is "random" enough for InnoDB tables).
[26 Jul 2009 11:59] Pavel Bazanov
One more strange thing. I tried the query and it worked fast (function was executed only 1 time). I tried it several more times and still the same - worked fast. Then I opened orderlines table in EMS MySql Manager and read a few pages of data from the table, and then scrolled to the last page (LIMIT XXXXXXX, 1000). Then I tried to run the query again and it worked slow, the function was executed many times. Mysticism! :)

As for your question. Yes, there are different EXPLAIN results when the function is executed 1 time and when it is executed many times. And when it is executed many times, the orderlines table comes as a first row in EXPLAIN results. When it is executed 1 time, the orderlines table comes second.
[26 Jul 2009 12:00] Pavel Bazanov
And when it is executed many times, the orderlines table comes as a second row in EXPLAIN results. When it is executed 1 time, the orderlines table comes first. ************ (I made a mistake in the previous message)
[26 Jul 2009 12:18] Valeriy Kravchuk
That EMS MySql Manager, does it execute SHOW TABLE STATUS or SHOW INDEXES when you use it the way yo described? Please, check with general query log if you are not sure. The fact is: statements mentioned above re-estimate statistics for the InnoDB table, and as it is "random" to some extent they may change the plan (to worse, in your case).
[26 Jul 2009 16:09] Pavel Bazanov
Here is the part of query log file:

090726 21:01:28	    3 Query	COMMIT
		    3 Query	BEGIN
		    3 Query	SHOW COLUMNS FROM `orderlines`
		    3 Query	SHOW INDEX FROM `orderlines`
		    3 Query	SHOW COLUMNS FROM `orders`
		    3 Query	SHOW INDEX FROM `orders`
		    3 Query	SELECT SlowFunction(ol.ID)
FROM orderlines ol
INNER JOIN orders o ON (o.ID = ol.OrderID) 
WHERE ol.Closed = false AND ol.TS >= '2009-06-01' 
ORDER BY ol.ID  
LIMIT 1

# THE FOLLOWING QUERY IS EXECUTED INSIDE SLOWFUNCTION() JUST FOR LOG PURPOSES AND TO MAKE IT SLOW :)

		    3 Query	INSERT INTO table1 SET A =  NAME_CONST('ID_',342383)

# THE OVERALL QUERY ABOVE WORKED FAST AND THE SLOWFUNCTION() IS EXECUTED ONLY 1 TIME

#NOW I BROWSE ORDERLINES TABLE IN EMS MYSQL MANAGER:

090726 21:02:18	    4 Connect	root@localhost on testdb
		    4 Query	BEGIN
		    5 Connect	root@localhost on testdb
		    5 Query	SHOW COLUMNS FROM `orderlines`
		    4 Query	SHOW COLUMNS FROM `orderlines`
		    5 Query	SHOW INDEX FROM `orderlines`
		    4 Query	SHOW INDEX FROM `orderlines`
090726 21:02:19	    5 Query	SELECT COUNT(*) FROM `orderlines`
		    4 Query	SELECT * FROM `orderlines` ORDER BY `ID` LIMIT 0, 1000
090726 21:02:21	    4 Query	SHOW COLUMNS FROM `orderlines`
		    4 Query	SHOW INDEX FROM `orderlines`
		    4 Query	SELECT * FROM `orderlines` ORDER BY `ID` LIMIT 1000, 1000
090726 21:02:22	    4 Query	SHOW COLUMNS FROM `orderlines`
		    4 Query	SHOW INDEX FROM `orderlines`
		    4 Query	SELECT * FROM `orderlines` ORDER BY `ID` LIMIT 556000, 1000

# AND NOW I EXECUTE THE QUERY AGAIN:

090726 21:02:31	    3 Query	COMMIT
		    3 Query	BEGIN
		    3 Query	SHOW COLUMNS FROM `orderlines`
		    3 Query	SHOW INDEX FROM `orderlines`
		    3 Query	SHOW COLUMNS FROM `orders`
		    3 Query	SHOW INDEX FROM `orders`
		    3 Query	SELECT SlowFunction(ol.ID)
FROM orderlines ol
INNER JOIN orders o ON (o.ID = ol.OrderID) 
WHERE ol.Closed = false AND ol.TS >= '2009-06-01' 
ORDER BY ol.ID  
LIMIT 1
090726 21:02:33	    3 Query	INSERT INTO table1 SET A =  NAME_CONST('ID_',342383)
		    3 Query	INSERT INTO table1 SET A =  NAME_CONST('ID_',354181)
		    3 Query	INSERT INTO table1 SET A =  NAME_CONST('ID_',379592) 
		    ... # MANY MANY SIMILAR LINES BECAUSE SLOWFUNCTION() IS EXECUTED MANY TIMES NOW.

#NOW THE QUERY IS EXECUTED VERY SLOW AND THE SLOWFUNCTION() IS EXECUTED MANY TIMES
[26 Jul 2009 16:30] Valeriy Kravchuk
Here it is, in your general query log:

SHOW INDEX FROM `orderlines`
...

For InnoDB table it forces re-calculation of statistics using "random dives" (see http://dev.mysql.com/doc/refman/5.1/en/innodb-restrictions.html also), and the resulting statistics may be "wrong enough" to change join order. So, either use STRAIGHT_JOIN to force join order, or do NOT use tools that runs SHOW INDEX commands without any real need.
[27 Jul 2009 10:07] Pavel Bazanov
The problem is - it's not EMS fault. I can turn on my computer, run mysql.exe, execute the query - and it might be executed slowly. That's all. It works somehow randomly.
[29 Jul 2009 8:51] Valeriy Kravchuk
Yes, when you re-start server statistics for InnoDB tables is re-estimated, with the same "random dives". So, surely, you may get a different plan. This is expected and documented (http://dev.mysql.com/doc/refman/5.1/en/innodb-restrictions.html). 

If you need to fix execution plan once and forever use FORCE INDEX/STRAIGHT_JOIN hints. There is NO other way for it to be always "good" for InnoDB table.

InnoDB changed the way they estimate statistics to make it "more random" recently, but it is still estimated based on random pages being selected from the indexes. We can not force InnoDB to change the way they estimate statistics.

Some time ago we started a project to add engine-independent persistent statistics. I do not know when it will be included into the main trees though. It is definitely not for 5.1.x.
[29 Jul 2009 9:02] Pavel Bazanov
It was ok in previous versions of MySQL. I have been using MySql for 5 years and I never had such problems with previous versions. There is a simple query that works not as expected. If there is such an algorithm, then that is a bad and buggy algoritm that allows such problems.
[29 Jul 2009 9:32] Valeriy Kravchuk
As I already informed you, this problem may be related to bugs also, bug #28404 for example. The "fix" for it, pushed some time ago, had led to numerous problems with queries accessing InnoDB tables and having ORDER BY. Most of the negative effects of that "fix" should disappear in 5.1.37 to be released soon.

Please, check with 5.1.37 when you'll have a chance. If it will NOT fix the problem for you in all cases, then randomness feature of the problem will clearly show that it is related to the way InnoDB statistics is estimated.
[29 Aug 2009 23:00] Bugs System
No feedback was provided for this bug for over a month, so it is
being suspended automatically. If you are able to provide the
information that was originally requested, please do so and change
the status of the bug back to "Open".
[4 Sep 2009 23:44] Pavel Bazanov
The bug still appears in 5.1.38 :(
[15 Sep 2009 7:40] Sveta Smirnova
Thank you for the feedback.

Verified as described.

Test case:

create function f1(v1 int) returns int return sleep(3);

create table t1(
f1 int not null primary key auto_increment,
f2 text
);

create table t2(
f1 int not null primary key auto_increment,
f2 int,
ts timestamp not null default current_timestamp,
closed tinyint(1) not null default '0',
key(f2)
);

insert into t1 values(null, md5(rand()));
insert into t1 select null, md5(rand()) from t1;
insert into t1 select null, md5(rand()) from t1;
insert into t1 select null, md5(rand()) from t1;

insert into t2(f2, closed) select f1, f1%2 from t1;
insert into t2(f2, closed) select f1, f1%2 from t1;
insert into t2(f2, closed) select f1, f1%2 from t1;

select count(*) from t2 inner join t1 on(t1.f1=t2.f2) where t2.closed=false and t2.ts >= '2009-06-01' ORDER BY t2.f1;

explain select f1(t2.f1) from t2 inner join t1 on(t1.f1=t2.f2) where t2.closed=false and t2.ts >= '2009-06-01' ORDER BY t2.f1 limit 1;

select now();
select f1(t2.f1) from t2 where t2.closed=false and t2.ts>='2009-06-01' ORDER BY t2.f1 limit 1;
select now();
select f1(t2.f1) from t2 inner join t1 on(t1.f1=t2.f2) where t2.closed=false and t2.ts >= '2009-06-01' ORDER BY t2.f1 limit 1;
select now();
[15 Sep 2009 9:03] Pavel Bazanov
Thank you for your work, Sveta. This problem is very annoying and by now I've met more cases where this problem appears.
[25 Apr 2010 12:52] Pavel Bazanov
Hello,
Guys, I believe you should increase the severity of the problem, it's not a feature request, it's a bug.
And it's killing me - I have to write ugly queries (see my workaround in the initial post) when the result set is big and I have to limit it and when I have slow function calls in select part of the query.
Please, work on it..
[24 Jul 2010 21:19] Pavel Bazanov
Guys, it's been almost a year since I've posted the bug report and the bug is still not fixed in the latest 5.1.49 :(