Fixed bug #29604.

A bug in the restore_prev_nj_state function allowed interleaving 
inner tables of outer join operations with outer tables. With the
current implementation of the nested loops algorithm it could lead
to wrong result sets for queries with nested outer joins.
Another bug in this procedure effectively blocked evaluation of some
valid execution plans for queries with nested outer joins. 

2 files changed, 225 insertions, 0 deletions

diff --git a/mysql-test/r/join_nested.result b/mysql-test/r/join_nested.result
index 006488f9d43..daf63579e9c 100644
--- a/mysql-test/r/join_nested.result
+++ b/mysql-test/r/join_nested.result
@@ -1632,4 +1632,115 @@ INSERT INTO t3 VALUES (1,1);
 SELECT * FROM t1 JOIN (t2 JOIN t3 USING (b)) USING (a);
 ERROR 23000: Column 'a' in from clause is ambiguous
 DROP TABLE t1,t2,t3;
+CREATE TABLE t1 (
+carrier char(2) default NULL,
+id int NOT NULL auto_increment PRIMARY KEY
+);
+INSERT INTO t1 VALUES
+('CO',235371754),('CO',235376554),('CO',235376884),('CO',235377874),
+('CO',231060394),('CO',231059224),('CO',231059314),('CO',231060484),
+('CO',231060274),('CO',231060124),('CO',231060244),('CO',231058594),
+('CO',231058924),('CO',231058504),('CO',231059344),('CO',231060424),
+('CO',231059554),('CO',231060304),('CO',231059644),('CO',231059464),
+('CO',231059764),('CO',231058294),('CO',231058624),('CO',231058864),
+('CO',231059374),('CO',231059584),('CO',231059734),('CO',231059014),
+('CO',231059854),('CO',231059494),('CO',231059794),('CO',231058534),
+('CO',231058324),('CO',231058684),('CO',231059524),('CO',231059974);
+CREATE TABLE t2 (
+scan_date date default NULL,
+package_id int default NULL,
+INDEX scan_date(scan_date),
+INDEX package_id(package_id)
+);
+INSERT INTO t2 VALUES
+('2008-12-29',231062944),('2008-12-29',231065764),('2008-12-29',231066124),
+('2008-12-29',231060094),('2008-12-29',231061054),('2008-12-29',231065644),
+('2008-12-29',231064384),('2008-12-29',231064444),('2008-12-29',231073774),
+('2008-12-29',231058594),('2008-12-29',231059374),('2008-12-29',231066004),
+('2008-12-29',231068494),('2008-12-29',231070174),('2008-12-29',231071884),
+('2008-12-29',231063274),('2008-12-29',231063754),('2008-12-29',231064144),
+('2008-12-29',231069424),('2008-12-29',231073714),('2008-12-29',231058414),
+('2008-12-29',231060994),('2008-12-29',231069154),('2008-12-29',231068614),
+('2008-12-29',231071464),('2008-12-29',231074014),('2008-12-29',231059614),
+('2008-12-29',231059074),('2008-12-29',231059464),('2008-12-29',231069094),
+('2008-12-29',231067294),('2008-12-29',231070144),('2008-12-29',231073804),
+('2008-12-29',231072634),('2008-12-29',231058294),('2008-12-29',231065344),
+('2008-12-29',231066094),('2008-12-29',231069034),('2008-12-29',231058594),
+('2008-12-29',231059854),('2008-12-29',231059884),('2008-12-29',231059914),
+('2008-12-29',231063664),('2008-12-29',231063814),('2008-12-29',231063904);
+CREATE TABLE t3 (
+package_id int default NULL,
+INDEX package_id(package_id)
+);
+INSERT INTO t3 VALUES
+(231058294),(231058324),(231058354),(231058384),(231058414),(231058444),
+(231058474),(231058504),(231058534),(231058564),(231058594),(231058624),
+(231058684),(231058744),(231058804),(231058864),(231058924),(231058954),
+(231059014),(231059074),(231059104),(231059134),(231059164),(231059194),
+(231059224),(231059254),(231059284),(231059314),(231059344),(231059374),
+(231059404),(231059434),(231059464),(231059494),(231059524),(231059554),
+(231059584),(231059614),(231059644),(231059674),(231059704),(231059734),
+(231059764),(231059794),(231059824),(231059854),(231059884),(231059914),
+(231059944),(231059974),(231060004),(231060034),(231060064),(231060094),
+(231060124),(231060154),(231060184),(231060214),(231060244),(231060274),
+(231060304),(231060334),(231060364),(231060394),(231060424),(231060454),
+(231060484),(231060514),(231060544),(231060574),(231060604),(231060634),
+(231060664),(231060694),(231060724),(231060754),(231060784),(231060814),
+(231060844),(231060874),(231060904),(231060934),(231060964),(231060994),
+(231061024),(231061054),(231061084),(231061144),(231061174),(231061204),
+(231061234),(231061294),(231061354),(231061384),(231061414),(231061474),
+(231061564),(231061594),(231061624),(231061684),(231061714),(231061774),
+(231061804),(231061894),(231061984),(231062074),(231062134),(231062224),
+(231062254),(231062314),(231062374),(231062434),(231062494),(231062554),
+(231062584),(231062614),(231062644),(231062704),(231062734),(231062794),
+(231062854),(231062884),(231062944),(231063004),(231063034),(231063064),
+(231063124),(231063154),(231063184),(231063214),(231063274),(231063334),
+(231063394),(231063424),(231063454),(231063514),(231063574),(231063664);
+CREATE TABLE t4 (
+carrier char(2) NOT NULL default '' PRIMARY KEY,
+id int(11) default NULL,
+INDEX id(id)
+);
+INSERT INTO t4 VALUES
+('99',6),('SK',456),('UA',486),('AI',1081),('OS',1111),('VS',1510);
+CREATE TABLE t5 (
+carrier_id int default NULL,
+INDEX carrier_id(carrier_id)
+);
+INSERT INTO t5 VALUES
+(6),(6),(6),(6),(6),(6),(6),(6),(6),(6),(6),(6),(6),(6),(6),(6),(6),(6),(6),
+(6),(6),(6),(6),(6),(6),(6),(6),(6),(6),(6),(6),(6),(6),(6),(6),(6),(6),(6),
+(6),(6),(6),(6),(6),(6),(6),(6),(6),(6),(6),(6),(6),(6),(6),(6),(6),(6),(6),
+(6),(6),(6),(6),(6),(6),(6),(6),(6),(6),(6),(6),(6),(6),(6),(6),(6),(6),(6),
+(6),(6),(6),(6),(6),(6),(6),(6),(6),(6),(6),(6),(6),(6),(6),(6),(6),(6),(6),
+(6),(6),(6),(6),(6),(6),(6),(6),(6),(6),(6),(6),(6),(6),(456),(456),(456),
+(456),(456),(456),(456),(456),(456),(456),(456),(456),(456),(456),(456),
+(456),(486),(1081),(1111),(1111),(1111),(1111),(1510);
+SELECT COUNT(*) 
+FROM((t2 JOIN t1 ON t2.package_id = t1.id) 
+JOIN t3 ON t3.package_id = t1.id);
+COUNT(*)
+6
+EXPLAIN
+SELECT COUNT(*) 
+FROM ((t2 JOIN t1 ON t2.package_id = t1.id) 
+JOIN t3 ON t3.package_id = t1.id)
+LEFT JOIN 
+(t5 JOIN t4 ON t5.carrier_id = t4.id)
+ON t4.carrier = t1.carrier;
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	t2	index	package_id	package_id	5	NULL	45	Using index
+1	SIMPLE	t1	eq_ref	PRIMARY	PRIMARY	4	test.t2.package_id	1	
+1	SIMPLE	t4	eq_ref	PRIMARY,id	PRIMARY	2	test.t1.carrier	1	
+1	SIMPLE	t5	ref	carrier_id	carrier_id	5	test.t4.id	22	Using index
+1	SIMPLE	t3	ref	package_id	package_id	5	test.t1.id	1	Using where; Using index
+SELECT COUNT(*) 
+FROM ((t2 JOIN t1 ON t2.package_id = t1.id) 
+JOIN t3 ON t3.package_id = t1.id)
+LEFT JOIN 
+(t5 JOIN t4 ON t5.carrier_id = t4.id)
+ON t4.carrier = t1.carrier;
+COUNT(*)
+6
+DROP TABLE t1,t2,t3,t4,t5;
 End of 5.0 tests
diff --git a/mysql-test/t/join_nested.test b/mysql-test/t/join_nested.test
index f29366797f6..5b07d8966f1 100644
--- a/mysql-test/t/join_nested.test
+++ b/mysql-test/t/join_nested.test
@@ -1083,4 +1083,118 @@ SELECT * FROM t1 JOIN (t2 JOIN t3 USING (b)) USING (a);
 
 DROP TABLE t1,t2,t3;
 
+#
+# BUG#29604: inner nest of left join interleaves with outer tables
+#
+
+CREATE TABLE t1 (
+  carrier char(2) default NULL,
+  id int NOT NULL auto_increment PRIMARY KEY
+);
+INSERT INTO t1 VALUES
+  ('CO',235371754),('CO',235376554),('CO',235376884),('CO',235377874),
+  ('CO',231060394),('CO',231059224),('CO',231059314),('CO',231060484),
+  ('CO',231060274),('CO',231060124),('CO',231060244),('CO',231058594),
+  ('CO',231058924),('CO',231058504),('CO',231059344),('CO',231060424),
+  ('CO',231059554),('CO',231060304),('CO',231059644),('CO',231059464),
+  ('CO',231059764),('CO',231058294),('CO',231058624),('CO',231058864),
+  ('CO',231059374),('CO',231059584),('CO',231059734),('CO',231059014),
+  ('CO',231059854),('CO',231059494),('CO',231059794),('CO',231058534),
+  ('CO',231058324),('CO',231058684),('CO',231059524),('CO',231059974);
+
+CREATE TABLE t2 (
+  scan_date date default NULL,
+  package_id int default NULL,
+  INDEX scan_date(scan_date),
+  INDEX package_id(package_id)
+);
+INSERT INTO t2 VALUES
+  ('2008-12-29',231062944),('2008-12-29',231065764),('2008-12-29',231066124),
+  ('2008-12-29',231060094),('2008-12-29',231061054),('2008-12-29',231065644),
+  ('2008-12-29',231064384),('2008-12-29',231064444),('2008-12-29',231073774),
+  ('2008-12-29',231058594),('2008-12-29',231059374),('2008-12-29',231066004),
+  ('2008-12-29',231068494),('2008-12-29',231070174),('2008-12-29',231071884),
+  ('2008-12-29',231063274),('2008-12-29',231063754),('2008-12-29',231064144),
+  ('2008-12-29',231069424),('2008-12-29',231073714),('2008-12-29',231058414),
+  ('2008-12-29',231060994),('2008-12-29',231069154),('2008-12-29',231068614),
+  ('2008-12-29',231071464),('2008-12-29',231074014),('2008-12-29',231059614),
+  ('2008-12-29',231059074),('2008-12-29',231059464),('2008-12-29',231069094),
+  ('2008-12-29',231067294),('2008-12-29',231070144),('2008-12-29',231073804),
+  ('2008-12-29',231072634),('2008-12-29',231058294),('2008-12-29',231065344),
+  ('2008-12-29',231066094),('2008-12-29',231069034),('2008-12-29',231058594),
+  ('2008-12-29',231059854),('2008-12-29',231059884),('2008-12-29',231059914),
+  ('2008-12-29',231063664),('2008-12-29',231063814),('2008-12-29',231063904);
+
+CREATE TABLE t3 (
+  package_id int default NULL,
+  INDEX package_id(package_id)
+);
+INSERT INTO t3 VALUES
+  (231058294),(231058324),(231058354),(231058384),(231058414),(231058444),
+  (231058474),(231058504),(231058534),(231058564),(231058594),(231058624),
+  (231058684),(231058744),(231058804),(231058864),(231058924),(231058954),
+  (231059014),(231059074),(231059104),(231059134),(231059164),(231059194),
+  (231059224),(231059254),(231059284),(231059314),(231059344),(231059374),
+  (231059404),(231059434),(231059464),(231059494),(231059524),(231059554),
+  (231059584),(231059614),(231059644),(231059674),(231059704),(231059734),
+  (231059764),(231059794),(231059824),(231059854),(231059884),(231059914),
+  (231059944),(231059974),(231060004),(231060034),(231060064),(231060094),
+  (231060124),(231060154),(231060184),(231060214),(231060244),(231060274),
+  (231060304),(231060334),(231060364),(231060394),(231060424),(231060454),
+  (231060484),(231060514),(231060544),(231060574),(231060604),(231060634),
+  (231060664),(231060694),(231060724),(231060754),(231060784),(231060814),
+  (231060844),(231060874),(231060904),(231060934),(231060964),(231060994),
+  (231061024),(231061054),(231061084),(231061144),(231061174),(231061204),
+  (231061234),(231061294),(231061354),(231061384),(231061414),(231061474),
+  (231061564),(231061594),(231061624),(231061684),(231061714),(231061774),
+  (231061804),(231061894),(231061984),(231062074),(231062134),(231062224),
+  (231062254),(231062314),(231062374),(231062434),(231062494),(231062554),
+  (231062584),(231062614),(231062644),(231062704),(231062734),(231062794),
+  (231062854),(231062884),(231062944),(231063004),(231063034),(231063064),
+  (231063124),(231063154),(231063184),(231063214),(231063274),(231063334),
+  (231063394),(231063424),(231063454),(231063514),(231063574),(231063664);
+ 
+CREATE TABLE t4 (
+  carrier char(2) NOT NULL default '' PRIMARY KEY,
+  id int(11) default NULL,
+  INDEX id(id)
+);
+INSERT INTO t4 VALUES
+  ('99',6),('SK',456),('UA',486),('AI',1081),('OS',1111),('VS',1510);
+
+CREATE TABLE t5 (
+  carrier_id int default NULL,
+  INDEX carrier_id(carrier_id)
+);
+INSERT INTO t5 VALUES
+  (6),(6),(6),(6),(6),(6),(6),(6),(6),(6),(6),(6),(6),(6),(6),(6),(6),(6),(6),
+  (6),(6),(6),(6),(6),(6),(6),(6),(6),(6),(6),(6),(6),(6),(6),(6),(6),(6),(6),
+  (6),(6),(6),(6),(6),(6),(6),(6),(6),(6),(6),(6),(6),(6),(6),(6),(6),(6),(6),
+  (6),(6),(6),(6),(6),(6),(6),(6),(6),(6),(6),(6),(6),(6),(6),(6),(6),(6),(6),
+  (6),(6),(6),(6),(6),(6),(6),(6),(6),(6),(6),(6),(6),(6),(6),(6),(6),(6),(6),
+  (6),(6),(6),(6),(6),(6),(6),(6),(6),(6),(6),(6),(6),(6),(456),(456),(456),
+  (456),(456),(456),(456),(456),(456),(456),(456),(456),(456),(456),(456),
+  (456),(486),(1081),(1111),(1111),(1111),(1111),(1510);
+
+SELECT COUNT(*) 
+  FROM((t2 JOIN t1 ON t2.package_id = t1.id) 
+        JOIN t3 ON t3.package_id = t1.id);
+
+EXPLAIN
+SELECT COUNT(*) 
+  FROM ((t2 JOIN t1 ON t2.package_id = t1.id) 
+         JOIN t3 ON t3.package_id = t1.id)
+       LEFT JOIN 
+       (t5 JOIN t4 ON t5.carrier_id = t4.id)
+       ON t4.carrier = t1.carrier;
+SELECT COUNT(*) 
+  FROM ((t2 JOIN t1 ON t2.package_id = t1.id) 
+        JOIN t3 ON t3.package_id = t1.id)
+       LEFT JOIN 
+       (t5 JOIN t4 ON t5.carrier_id = t4.id)
+       ON t4.carrier = t1.carrier;
+
+DROP TABLE t1,t2,t3,t4,t5;
+
 --echo End of 5.0 tests
+