MySQL Bugs: #10266: Order of multiple left joins matters?

Bug #10266	Order of multiple left joins matters?
Submitted:	29 Apr 2005 15:47	Modified:	9 Jun 2005 17:17
Reporter:	Ronnie Paskin	Email Updates:
Status:	Not a Bug	Impact on me:	None
Category:	MySQL Server: Optimizer	Severity:	S2 (Serious)
Version:	4.1	OS:	Windows (Windows 2000)
Assigned to:	Igor Babaev	CPU Architecture:	Any

Description:
I'm not sure if it's a bug or if it's supposed to be like that, but the order of multiple LEFT JOIN statements seems to matter.

I have something like this:

SELECT *
FROM table1
LEFT OUTER JOIN table2
ON table1.table2ID=table2.ID
LEFT OUTER JOIN table3
ON table2.table3ID = table3.ID;

Which gives me an error:
ERROR 1120 (42000): Cross dependency found in OUTER JOIN; examine your ON conditions

Whereas this works fine:

SELECT *
FROM table1
LEFT OUTER JOIN table3
ON table2.table3ID = table3.ID
LEFT OUTER JOIN table2
ON table1.table2ID=table2.ID;

If this is expected behavior there should be something in the documentation here... is this an optimizer bug?

How to repeat:
SET FOREIGN_KEY_CHECKS=0;

/*
Table structure for table1
*/

CREATE TABLE `table1` (
  `ID` int(11) NOT NULL auto_increment,
  `table2ID` int(11) NOT NULL default '0',
  PRIMARY KEY  (`ID`),
  KEY `t2` (`table2ID`),
  CONSTRAINT `t2` FOREIGN KEY (`table2ID`) REFERENCES `table2` (`ID`)
) ENGINE=InnoDB DEFAULT CHARSET=latin1;

/*
Table data for test.table1
*/

INSERT INTO `table1` VALUES 
(1,1),
(2,2),
(3,3);

/*
Table structure for table2
*/

CREATE TABLE `table2` (
  `ID` int(11) NOT NULL default '0',
  `table3ID` int(11) default NULL,
  PRIMARY KEY  (`ID`),
  KEY `t3` (`table3ID`),
  CONSTRAINT `t3` FOREIGN KEY (`table3ID`) REFERENCES `table3` (`ID`)
) ENGINE=InnoDB DEFAULT CHARSET=latin1;

/*
Table data for test.table2
*/

INSERT INTO `table2` VALUES 
(1,1),
(2,2),
(3,3),
(4,4),
(5,5),
(6,6),
(7,7);

/*
Table structure for table3
*/

CREATE TABLE `table3` (
  `ID` int(11) NOT NULL default '0',
  PRIMARY KEY  (`ID`)
) ENGINE=InnoDB DEFAULT CHARSET=latin1;

/*
Table data for test.table3
*/

INSERT INTO `table3` VALUES 
(1),
(2),
(3),
(4),
(5),
(6),
(7);

SET FOREIGN_KEY_CHECKS=1;

Suggested fix:
Fix the optimizer... the order should not matter (I think). Or at least add a note to the documentation.

mysql> SELECT *
    -> FROM table1
    -> LEFT OUTER JOIN table2
    -> ON table1.table2ID=table2.ID
    -> LEFT OUTER JOIN table3
    -> ON table2.table3ID = table3.ID;
+----+----------+------+----------+------+
| ID | table2ID | ID   | table3ID | ID   |
+----+----------+------+----------+------+
|  1 |        1 |    1 |        1 |    1 |
|  2 |        2 |    2 |        2 |    2 |
|  3 |        3 |    3 |        3 |    3 |
+----+----------+------+----------+------+
3 rows in set (0.03 sec)

mysql> select version();
+-----------+
| version() |
+-----------+
| 4.1.12-nt |
+-----------+
1 row in set (0.00 sec)

mysql>

Thanks for checking.

Cut and paste hell... This is what I get (the SELECTS where switched on my original post). Note that for the error to happen, of course table3 must come before table2 on the query.

mysql> SELECT *
    -> FROM table1
    -> LEFT OUTER JOIN table2
    -> ON table1.table2ID=table2.ID
    -> LEFT OUTER JOIN table3
    -> ON table2.table3ID = table3.ID;
+----+----------+------+----------+------+
| ID | table2ID | ID   | table3ID | ID   |
+----+----------+------+----------+------+
|  1 |        1 |    1 |        1 |    1 |
|  2 |        2 |    2 |        2 |    2 |
|  3 |        3 |    3 |        3 |    3 |
+----+----------+------+----------+------+
3 rows in set (0.00 sec)

mysql> SELECT *
    -> FROM table1
    -> LEFT OUTER JOIN table3
    -> ON table2.table3ID = table3.ID
    -> LEFT OUTER JOIN table2
    -> ON table1.table2ID=table2.ID;
ERROR 1120 (42000): Cross dependency found in OUTER JOIN; examine your ON condit
ions
mysql> select version();
+-----------+
| version() |
+-----------+
| 4.1.10-nt |
+-----------+
1 row in set (0.00 sec)

Thank you for the feedback.

mysql> SELECT *
    -> FROM table1
    -> LEFT OUTER JOIN table3
    -> ON table2.table3ID = table3.ID
    -> LEFT OUTER JOIN table2
    -> ON table1.table2ID=table2.ID;
ERROR 1120 (42000): Cross dependency found in OUTER JOIN; examine your ON conditions
mysql> select version();
+-----------+
| version() |
+-----------+
| 4.1.13-nt |
+-----------+
1 row in set (0.00 sec)

This is not a bug. The server reports a problem with cross reference when it exists.

Please read the bug description.

I did not see any documentation stating that the order of the tables in multiple joins should cause cross-dependency problems.

All the information is there, the queries are the same except for the order of the left joins.

At the very least, the documentation should clearly say that the optimizer is unable to figure out how to order the left joins so that there's no cross-dependency problem.

By using LEFT JOIN you forced join order, optimizer have no freedom to reorder anything here.
So, the join order is fixed, dependencies are there, and they are not compatible with each other.

Ok... thanks for checking.

However, I still say that if this is the way it's supposed to work, the documentation is not clear.

I have spoken to a few experienced developers and this took them all by surprise. A quick note in the documentation may save people time.

thanks again,
Ronnie