greedy_search() and best_extension_by_limited_search() scrambled table order

best_extension_by_limited_search() assumes that tables should be sorted
according to size to be able to quickly disregard bad plans. However the
current usage of swap_variables() will change the table order to a not
sorted one for the next recursive call. This breaks the assumtion and
causes performance issues when using many tables (we have to examine
many more plans).

This patch fixes this by ensuring that the original table order is kept
for the not yet used tables when best_extension_by_limited_search() is
called.

This was done by always calling swap_variables() for each table and
restoring the original table order at exit.

Some test changed:
- In a majority of the test the change was that two "identical tables"
  where swapped and the optimzer is now using the first/smaller table
- In few test the table order was changed. The new plan looks identical
  or slighly better than the original.

13 files changed, 146 insertions, 129 deletions

diff --git a/mysql-test/main/derived_cond_pushdown.result b/mysql-test/main/derived_cond_pushdown.result
index 275459bd868..d15f368e08d 100644
--- a/mysql-test/main/derived_cond_pushdown.result
+++ b/mysql-test/main/derived_cond_pushdown.result
@@ -3454,10 +3454,10 @@ a	b	max_c	avg_c	a	b	max_c	avg_c	a	b	min_c	a	b	c	d
 6	20	315	279.3333	6	20	315	279.3333	6	20	214	6	20	315	279
 6	20	315	279.3333	6	20	315	279.3333	8	33	114	8	80	800	314
 6	20	315	279.3333	6	20	315	279.3333	6	20	214	6	23	303	909
-6	20	315	279.3333	8	33	404	213.6667	6	20	214	6	20	315	279
-6	20	315	279.3333	8	33	404	213.6667	6	20	214	6	23	303	909
 8	33	404	213.6667	6	20	315	279.3333	8	33	114	8	64	248	107
 8	33	404	213.6667	6	20	315	279.3333	8	33	114	8	80	800	314
+6	20	315	279.3333	8	33	404	213.6667	6	20	214	6	20	315	279
+6	20	315	279.3333	8	33	404	213.6667	6	20	214	6	23	303	909
 8	33	404	213.6667	8	33	404	213.6667	7	11	708	7	13	312	406
 8	33	404	213.6667	8	33	404	213.6667	8	33	114	8	64	248	107
 8	33	404	213.6667	8	33	404	213.6667	6	20	214	6	20	315	279
@@ -3472,10 +3472,10 @@ a	b	max_c	avg_c	a	b	max_c	avg_c	a	b	min_c	a	b	c	d
 6	20	315	279.3333	6	20	315	279.3333	6	20	214	6	20	315	279
 6	20	315	279.3333	6	20	315	279.3333	8	33	114	8	80	800	314
 6	20	315	279.3333	6	20	315	279.3333	6	20	214	6	23	303	909
-6	20	315	279.3333	8	33	404	213.6667	6	20	214	6	20	315	279
-6	20	315	279.3333	8	33	404	213.6667	6	20	214	6	23	303	909
 8	33	404	213.6667	6	20	315	279.3333	8	33	114	8	64	248	107
 8	33	404	213.6667	6	20	315	279.3333	8	33	114	8	80	800	314
+6	20	315	279.3333	8	33	404	213.6667	6	20	214	6	20	315	279
+6	20	315	279.3333	8	33	404	213.6667	6	20	214	6	23	303	909
 8	33	404	213.6667	8	33	404	213.6667	7	11	708	7	13	312	406
 8	33	404	213.6667	8	33	404	213.6667	8	33	114	8	64	248	107
 8	33	404	213.6667	8	33	404	213.6667	6	20	214	6	20	315	279
@@ -3487,8 +3487,8 @@ and (v1.max_c<500) and (v3.a=t2.a) and (v2.max_c>300);
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 1	PRIMARY	t2	ALL	NULL	NULL	NULL	NULL	9	Using where
 1	PRIMARY	<derived4>	ref	key0	key0	5	test.t2.a	2	Using where
-1	PRIMARY	<derived3>	ALL	NULL	NULL	NULL	NULL	20	Using where; Using join buffer (flat, BNL join)
-1	PRIMARY	<derived2>	ALL	NULL	NULL	NULL	NULL	20	Using where; Using join buffer (incremental, BNL join)
+1	PRIMARY	<derived2>	ALL	NULL	NULL	NULL	NULL	20	Using where; Using join buffer (flat, BNL join)
+1	PRIMARY	<derived3>	ALL	NULL	NULL	NULL	NULL	20	Using where; Using join buffer (incremental, BNL join)
 4	DERIVED	t1	ALL	NULL	NULL	NULL	NULL	20	Using where; Using temporary; Using filesort
 3	DERIVED	t1	ALL	NULL	NULL	NULL	NULL	20	Using where; Using temporary; Using filesort
 2	DERIVED	t1	ALL	NULL	NULL	NULL	NULL	20	Using temporary; Using filesort
@@ -3538,19 +3538,19 @@ EXPLAIN
     },
     "block-nl-join": {
       "table": {
-        "table_name": "<derived3>",
+        "table_name": "<derived2>",
         "access_type": "ALL",
         "rows": 20,
         "filtered": 100,
-        "attached_condition": "v2.max_c > 300"
+        "attached_condition": "v1.max_c < 500"
       },
       "buffer_type": "flat",
       "buffer_size": "715",
       "join_type": "BNL",
       "materialized": {
         "query_block": {
-          "select_id": 3,
-          "having_condition": "max_c < 707 and max_c > 300",
+          "select_id": 2,
+          "having_condition": "max_c < 707 and max_c < 500",
           "filesort": {
             "sort_key": "t1.a, t1.b",
             "temporary_table": {
@@ -3558,8 +3558,7 @@ EXPLAIN
                 "table_name": "t1",
                 "access_type": "ALL",
                 "rows": 20,
-                "filtered": 100,
-                "attached_condition": "t1.a > 5"
+                "filtered": 100
               }
             }
           }
@@ -3568,20 +3567,20 @@ EXPLAIN
     },
     "block-nl-join": {
       "table": {
-        "table_name": "<derived2>",
+        "table_name": "<derived3>",
         "access_type": "ALL",
         "rows": 20,
         "filtered": 100,
-        "attached_condition": "v1.max_c < 500"
+        "attached_condition": "v2.max_c > 300"
       },
       "buffer_type": "incremental",
       "buffer_size": "9Kb",
       "join_type": "BNL",
-      "attached_condition": "v1.a = v2.a or v1.a = t2.a",
+      "attached_condition": "v2.a = v1.a or v1.a = t2.a",
       "materialized": {
         "query_block": {
-          "select_id": 2,
-          "having_condition": "max_c < 707 and max_c < 500",
+          "select_id": 3,
+          "having_condition": "max_c < 707 and max_c > 300",
           "filesort": {
             "sort_key": "t1.a, t1.b",
             "temporary_table": {
@@ -3589,7 +3588,8 @@ EXPLAIN
                 "table_name": "t1",
                 "access_type": "ALL",
                 "rows": 20,
-                "filtered": 100
+                "filtered": 100,
+                "attached_condition": "t1.a > 5"
               }
             }
           }
diff --git a/mysql-test/main/join_nested.result b/mysql-test/main/join_nested.result
index b323190d8d5..0c7a1b48940 100644
--- a/mysql-test/main/join_nested.result
+++ b/mysql-test/main/join_nested.result
@@ -916,11 +916,11 @@ id	select_type	table	type	possible_keys	key	key_len	ref	rows	filtered	Extra
 1	SIMPLE	t6	ALL	NULL	NULL	NULL	NULL	3	100.00	Using where
 1	SIMPLE	t8	ALL	NULL	NULL	NULL	NULL	2	100.00	Using where
 1	SIMPLE	t2	ALL	NULL	NULL	NULL	NULL	8	100.00	Using where
-1	SIMPLE	t4	ALL	NULL	NULL	NULL	NULL	2	100.00	Using where
 1	SIMPLE	t3	ALL	NULL	NULL	NULL	NULL	2	100.00	Using where
+1	SIMPLE	t4	ALL	NULL	NULL	NULL	NULL	2	100.00	Using where
 1	SIMPLE	t9	ALL	NULL	NULL	NULL	NULL	3	100.00	Using where; Using join buffer (flat, BNL join)
 Warnings:
-Note	1003	select `test`.`t0`.`a` AS `a`,`test`.`t0`.`b` AS `b`,`test`.`t1`.`a` AS `a`,`test`.`t1`.`b` AS `b`,`test`.`t2`.`a` AS `a`,`test`.`t2`.`b` AS `b`,`test`.`t3`.`a` AS `a`,`test`.`t3`.`b` AS `b`,`test`.`t4`.`a` AS `a`,`test`.`t4`.`b` AS `b`,`test`.`t5`.`a` AS `a`,`test`.`t5`.`b` AS `b`,`test`.`t6`.`a` AS `a`,`test`.`t6`.`b` AS `b`,`test`.`t7`.`a` AS `a`,`test`.`t7`.`b` AS `b`,`test`.`t8`.`a` AS `a`,`test`.`t8`.`b` AS `b`,`test`.`t9`.`a` AS `a`,`test`.`t9`.`b` AS `b` from `test`.`t0` join `test`.`t1` left join (`test`.`t2` left join (`test`.`t3` join `test`.`t4`) on(`test`.`t3`.`a` = 1 and `test`.`t4`.`b` = `test`.`t2`.`b` and `test`.`t2`.`a` > 0) join `test`.`t5` left join (`test`.`t6` join `test`.`t7` left join `test`.`t8` on(`test`.`t8`.`b` = `test`.`t5`.`b` and `test`.`t6`.`b` < 10)) on(`test`.`t7`.`b` = `test`.`t5`.`b` and `test`.`t6`.`b` >= 2)) on((`test`.`t3`.`b` = 2 or `test`.`t3`.`c` is null) and (`test`.`t6`.`b` = 2 or `test`.`t6`.`c` is null) and (`test`.`t5`.`b` = `test`.`t0`.`b` or `test`.`t3`.`c` is null or `test`.`t6`.`c` is null or `test`.`t8`.`c` is null) and `test`.`t1`.`a` <> 2) join `test`.`t9` where `test`.`t0`.`a` = 1 and `test`.`t1`.`b` = `test`.`t0`.`b` and `test`.`t9`.`a` = 1 and (`test`.`t2`.`a` >= 4 or `test`.`t2`.`c` is null) and (`test`.`t3`.`a` < 5 or `test`.`t3`.`c` is null) and (`test`.`t3`.`b` = `test`.`t4`.`b` or `test`.`t3`.`c` is null or `test`.`t4`.`c` is null) and (`test`.`t5`.`a` >= 2 or `test`.`t5`.`c` is null) and (`test`.`t6`.`a` >= 4 or `test`.`t6`.`c` is null) and (`test`.`t7`.`a` <= 2 or `test`.`t7`.`c` is null) and (`test`.`t8`.`a` < 1 or `test`.`t8`.`c` is null) and (`test`.`t9`.`b` = `test`.`t8`.`b` or `test`.`t8`.`c` is null)
+Note	1003	select `test`.`t0`.`a` AS `a`,`test`.`t0`.`b` AS `b`,`test`.`t1`.`a` AS `a`,`test`.`t1`.`b` AS `b`,`test`.`t2`.`a` AS `a`,`test`.`t2`.`b` AS `b`,`test`.`t3`.`a` AS `a`,`test`.`t3`.`b` AS `b`,`test`.`t4`.`a` AS `a`,`test`.`t4`.`b` AS `b`,`test`.`t5`.`a` AS `a`,`test`.`t5`.`b` AS `b`,`test`.`t6`.`a` AS `a`,`test`.`t6`.`b` AS `b`,`test`.`t7`.`a` AS `a`,`test`.`t7`.`b` AS `b`,`test`.`t8`.`a` AS `a`,`test`.`t8`.`b` AS `b`,`test`.`t9`.`a` AS `a`,`test`.`t9`.`b` AS `b` from `test`.`t0` join `test`.`t1` left join (`test`.`t2` left join (`test`.`t3` join `test`.`t4`) on(`test`.`t3`.`a` = 1 and `test`.`t4`.`b` = `test`.`t2`.`b` and `test`.`t2`.`a` > 0) join `test`.`t5` left join (`test`.`t6` join `test`.`t7` left join `test`.`t8` on(`test`.`t8`.`b` = `test`.`t5`.`b` and `test`.`t6`.`b` < 10)) on(`test`.`t7`.`b` = `test`.`t5`.`b` and `test`.`t6`.`b` >= 2)) on((`test`.`t3`.`b` = 2 or `test`.`t3`.`c` is null) and (`test`.`t6`.`b` = 2 or `test`.`t6`.`c` is null) and (`test`.`t5`.`b` = `test`.`t0`.`b` or `test`.`t3`.`c` is null or `test`.`t6`.`c` is null or `test`.`t8`.`c` is null) and `test`.`t1`.`a` <> 2) join `test`.`t9` where `test`.`t0`.`a` = 1 and `test`.`t1`.`b` = `test`.`t0`.`b` and `test`.`t9`.`a` = 1 and (`test`.`t2`.`a` >= 4 or `test`.`t2`.`c` is null) and (`test`.`t3`.`a` < 5 or `test`.`t3`.`c` is null) and (`test`.`t4`.`b` = `test`.`t3`.`b` or `test`.`t3`.`c` is null or `test`.`t4`.`c` is null) and (`test`.`t5`.`a` >= 2 or `test`.`t5`.`c` is null) and (`test`.`t6`.`a` >= 4 or `test`.`t6`.`c` is null) and (`test`.`t7`.`a` <= 2 or `test`.`t7`.`c` is null) and (`test`.`t8`.`a` < 1 or `test`.`t8`.`c` is null) and (`test`.`t9`.`b` = `test`.`t8`.`b` or `test`.`t8`.`c` is null)
 INSERT INTO t4 VALUES (-3,12,0), (-4,13,0), (-1,11,0), (-3,11,0), (-5,15,0);
 INSERT INTO t5 VALUES (-3,11,0), (-2,12,0), (-3,13,0), (-4,12,0);
 CREATE INDEX idx_b ON t4(b);
diff --git a/mysql-test/main/join_nested_jcl6.result b/mysql-test/main/join_nested_jcl6.result
index f7d0242244d..31f5c794071 100644
--- a/mysql-test/main/join_nested_jcl6.result
+++ b/mysql-test/main/join_nested_jcl6.result
@@ -925,11 +925,11 @@ id	select_type	table	type	possible_keys	key	key_len	ref	rows	filtered	Extra
 1	SIMPLE	t6	ALL	NULL	NULL	NULL	NULL	3	100.00	Using where; Using join buffer (incremental, BNL join)
 1	SIMPLE	t8	hash_ALL	NULL	#hash#$hj	5	test.t5.b	2	100.00	Using where; Using join buffer (incremental, BNLH join)
 1	SIMPLE	t2	ALL	NULL	NULL	NULL	NULL	8	100.00	Using where; Using join buffer (incremental, BNL join)
-1	SIMPLE	t4	hash_ALL	NULL	#hash#$hj	5	test.t2.b	2	100.00	Using where; Using join buffer (incremental, BNLH join)
 1	SIMPLE	t3	ALL	NULL	NULL	NULL	NULL	2	100.00	Using where; Using join buffer (incremental, BNL join)
+1	SIMPLE	t4	hash_ALL	NULL	#hash#$hj	5	test.t2.b	2	100.00	Using where; Using join buffer (incremental, BNLH join)
 1	SIMPLE	t9	ALL	NULL	NULL	NULL	NULL	3	100.00	Using where; Using join buffer (incremental, BNL join)
 Warnings:
-Note	1003	select `test`.`t0`.`a` AS `a`,`test`.`t0`.`b` AS `b`,`test`.`t1`.`a` AS `a`,`test`.`t1`.`b` AS `b`,`test`.`t2`.`a` AS `a`,`test`.`t2`.`b` AS `b`,`test`.`t3`.`a` AS `a`,`test`.`t3`.`b` AS `b`,`test`.`t4`.`a` AS `a`,`test`.`t4`.`b` AS `b`,`test`.`t5`.`a` AS `a`,`test`.`t5`.`b` AS `b`,`test`.`t6`.`a` AS `a`,`test`.`t6`.`b` AS `b`,`test`.`t7`.`a` AS `a`,`test`.`t7`.`b` AS `b`,`test`.`t8`.`a` AS `a`,`test`.`t8`.`b` AS `b`,`test`.`t9`.`a` AS `a`,`test`.`t9`.`b` AS `b` from `test`.`t0` join `test`.`t1` left join (`test`.`t2` left join (`test`.`t3` join `test`.`t4`) on(`test`.`t3`.`a` = 1 and `test`.`t4`.`b` = `test`.`t2`.`b` and `test`.`t2`.`a` > 0 and `test`.`t2`.`b` is not null) join `test`.`t5` left join (`test`.`t6` join `test`.`t7` left join `test`.`t8` on(`test`.`t8`.`b` = `test`.`t5`.`b` and `test`.`t6`.`b` < 10 and `test`.`t5`.`b` is not null)) on(`test`.`t7`.`b` = `test`.`t5`.`b` and `test`.`t6`.`b` >= 2 and `test`.`t5`.`b` is not null)) on((`test`.`t3`.`b` = 2 or `test`.`t3`.`c` is null) and (`test`.`t6`.`b` = 2 or `test`.`t6`.`c` is null) and (`test`.`t5`.`b` = `test`.`t0`.`b` or `test`.`t3`.`c` is null or `test`.`t6`.`c` is null or `test`.`t8`.`c` is null) and `test`.`t1`.`a` <> 2) join `test`.`t9` where `test`.`t0`.`a` = 1 and `test`.`t1`.`b` = `test`.`t0`.`b` and `test`.`t9`.`a` = 1 and (`test`.`t2`.`a` >= 4 or `test`.`t2`.`c` is null) and (`test`.`t3`.`a` < 5 or `test`.`t3`.`c` is null) and (`test`.`t3`.`b` = `test`.`t4`.`b` or `test`.`t3`.`c` is null or `test`.`t4`.`c` is null) and (`test`.`t5`.`a` >= 2 or `test`.`t5`.`c` is null) and (`test`.`t6`.`a` >= 4 or `test`.`t6`.`c` is null) and (`test`.`t7`.`a` <= 2 or `test`.`t7`.`c` is null) and (`test`.`t8`.`a` < 1 or `test`.`t8`.`c` is null) and (`test`.`t9`.`b` = `test`.`t8`.`b` or `test`.`t8`.`c` is null)
+Note	1003	select `test`.`t0`.`a` AS `a`,`test`.`t0`.`b` AS `b`,`test`.`t1`.`a` AS `a`,`test`.`t1`.`b` AS `b`,`test`.`t2`.`a` AS `a`,`test`.`t2`.`b` AS `b`,`test`.`t3`.`a` AS `a`,`test`.`t3`.`b` AS `b`,`test`.`t4`.`a` AS `a`,`test`.`t4`.`b` AS `b`,`test`.`t5`.`a` AS `a`,`test`.`t5`.`b` AS `b`,`test`.`t6`.`a` AS `a`,`test`.`t6`.`b` AS `b`,`test`.`t7`.`a` AS `a`,`test`.`t7`.`b` AS `b`,`test`.`t8`.`a` AS `a`,`test`.`t8`.`b` AS `b`,`test`.`t9`.`a` AS `a`,`test`.`t9`.`b` AS `b` from `test`.`t0` join `test`.`t1` left join (`test`.`t2` left join (`test`.`t3` join `test`.`t4`) on(`test`.`t3`.`a` = 1 and `test`.`t4`.`b` = `test`.`t2`.`b` and `test`.`t2`.`a` > 0 and `test`.`t2`.`b` is not null) join `test`.`t5` left join (`test`.`t6` join `test`.`t7` left join `test`.`t8` on(`test`.`t8`.`b` = `test`.`t5`.`b` and `test`.`t6`.`b` < 10 and `test`.`t5`.`b` is not null)) on(`test`.`t7`.`b` = `test`.`t5`.`b` and `test`.`t6`.`b` >= 2 and `test`.`t5`.`b` is not null)) on((`test`.`t3`.`b` = 2 or `test`.`t3`.`c` is null) and (`test`.`t6`.`b` = 2 or `test`.`t6`.`c` is null) and (`test`.`t5`.`b` = `test`.`t0`.`b` or `test`.`t3`.`c` is null or `test`.`t6`.`c` is null or `test`.`t8`.`c` is null) and `test`.`t1`.`a` <> 2) join `test`.`t9` where `test`.`t0`.`a` = 1 and `test`.`t1`.`b` = `test`.`t0`.`b` and `test`.`t9`.`a` = 1 and (`test`.`t2`.`a` >= 4 or `test`.`t2`.`c` is null) and (`test`.`t3`.`a` < 5 or `test`.`t3`.`c` is null) and (`test`.`t4`.`b` = `test`.`t3`.`b` or `test`.`t3`.`c` is null or `test`.`t4`.`c` is null) and (`test`.`t5`.`a` >= 2 or `test`.`t5`.`c` is null) and (`test`.`t6`.`a` >= 4 or `test`.`t6`.`c` is null) and (`test`.`t7`.`a` <= 2 or `test`.`t7`.`c` is null) and (`test`.`t8`.`a` < 1 or `test`.`t8`.`c` is null) and (`test`.`t9`.`b` = `test`.`t8`.`b` or `test`.`t8`.`c` is null)
 INSERT INTO t4 VALUES (-3,12,0), (-4,13,0), (-1,11,0), (-3,11,0), (-5,15,0);
 INSERT INTO t5 VALUES (-3,11,0), (-2,12,0), (-3,13,0), (-4,12,0);
 CREATE INDEX idx_b ON t4(b);
@@ -1027,8 +1027,8 @@ id	select_type	table	type	possible_keys	key	key_len	ref	rows	filtered	Extra
 1	SIMPLE	t3	ALL	NULL	NULL	NULL	NULL	2	100.00	Using where; Using join buffer (incremental, BNL join)
 1	SIMPLE	t4	ref	idx_b	idx_b	5	test.t2.b	2	100.00	Using where; Using join buffer (incremental, BKA join); Key-ordered Rowid-ordered scan
 1	SIMPLE	t5	ALL	idx_b	NULL	NULL	NULL	7	100.00	Using where; Using join buffer (incremental, BNL join)
-1	SIMPLE	t6	ALL	NULL	NULL	NULL	NULL	3	100.00	Using where; Using join buffer (incremental, BNL join)
 1	SIMPLE	t7	hash_ALL	NULL	#hash#$hj	5	test.t5.b	2	100.00	Using where; Using join buffer (incremental, BNLH join)
+1	SIMPLE	t6	ALL	NULL	NULL	NULL	NULL	3	100.00	Using where; Using join buffer (incremental, BNL join)
 1	SIMPLE	t8	ref	idx_b	idx_b	5	test.t5.b	2	100.00	Using where; Using join buffer (incremental, BKA join); Key-ordered Rowid-ordered scan
 Warnings:
 Note	1003	select `test`.`t0`.`a` AS `a`,`test`.`t0`.`b` AS `b`,`test`.`t1`.`a` AS `a`,`test`.`t1`.`b` AS `b`,`test`.`t2`.`a` AS `a`,`test`.`t2`.`b` AS `b`,`test`.`t3`.`a` AS `a`,`test`.`t3`.`b` AS `b`,`test`.`t4`.`a` AS `a`,`test`.`t4`.`b` AS `b`,`test`.`t5`.`a` AS `a`,`test`.`t5`.`b` AS `b`,`test`.`t6`.`a` AS `a`,`test`.`t6`.`b` AS `b`,`test`.`t7`.`a` AS `a`,`test`.`t7`.`b` AS `b`,`test`.`t8`.`a` AS `a`,`test`.`t8`.`b` AS `b`,`test`.`t9`.`a` AS `a`,`test`.`t9`.`b` AS `b` from `test`.`t0` join `test`.`t1` left join (`test`.`t2` left join (`test`.`t3` join `test`.`t4`) on(`test`.`t3`.`a` = 1 and `test`.`t4`.`b` = `test`.`t2`.`b` and `test`.`t2`.`a` > 0 and `test`.`t4`.`a` > 0 and `test`.`t2`.`b` is not null) join `test`.`t5` left join (`test`.`t6` join `test`.`t7` left join `test`.`t8` on(`test`.`t8`.`b` = `test`.`t5`.`b` and `test`.`t6`.`b` < 10 and `test`.`t8`.`a` >= 0 and `test`.`t5`.`b` is not null)) on(`test`.`t7`.`b` = `test`.`t5`.`b` and `test`.`t6`.`b` >= 2 and `test`.`t5`.`a` > 0 and `test`.`t5`.`b` is not null)) on((`test`.`t3`.`b` = 2 or `test`.`t3`.`c` is null) and (`test`.`t6`.`b` = 2 or `test`.`t6`.`c` is null) and (`test`.`t5`.`b` = `test`.`t0`.`b` or `test`.`t3`.`c` is null or `test`.`t6`.`c` is null or `test`.`t8`.`c` is null) and `test`.`t1`.`a` <> 2) join `test`.`t9` where `test`.`t0`.`a` = 1 and `test`.`t1`.`b` = `test`.`t0`.`b` and `test`.`t9`.`a` = 1 and (`test`.`t2`.`a` >= 4 or `test`.`t2`.`c` is null) and (`test`.`t3`.`a` < 5 or `test`.`t3`.`c` is null) and (`test`.`t4`.`b` = `test`.`t3`.`b` or `test`.`t3`.`c` is null or `test`.`t4`.`c` is null) and (`test`.`t5`.`a` >= 2 or `test`.`t5`.`c` is null) and (`test`.`t6`.`a` >= 4 or `test`.`t6`.`c` is null) and (`test`.`t7`.`a` <= 2 or `test`.`t7`.`c` is null) and (`test`.`t8`.`a` < 1 or `test`.`t8`.`c` is null) and (`test`.`t8`.`b` = `test`.`t9`.`b` or `test`.`t8`.`c` is null)
diff --git a/mysql-test/main/opt_trace.result b/mysql-test/main/opt_trace.result
index 5504f4da81e..6d026bf7502 100644
--- a/mysql-test/main/opt_trace.result
+++ b/mysql-test/main/opt_trace.result
@@ -5495,6 +5495,11 @@ t_outer_2.a in (select t_inner_3.a from t2 t_inner_3, t1 t_inner_4)	{
                                     "cost_for_plan": 451.8615234,
                                     "semijoin_strategy_choice": [
                                       {
+                                        "strategy": "FirstMatch",
+                                        "records": 27,
+                                        "read_time": 665.225293
+                                      },
+                                      {
                                         "strategy": "DuplicateWeedout",
                                         "records": 27,
                                         "read_time": 565.2615234
@@ -5651,35 +5656,26 @@ t_outer_2.a in (select t_inner_3.a from t2 t_inner_3, t1 t_inner_4)	{
                                   "t_outer_2",
                                   "t_inner_3"
                                 ],
-                                "table": "t_inner_4",
+                                "table": "t_inner_2",
                                 "best_access_path": {
                                   "considered_access_paths": [
                                     {
                                       "access_type": "scan",
-                                      "resulting_rows": 3,
-                                      "cost": 2.005126953,
+                                      "resulting_rows": 9,
+                                      "cost": 2.015380859,
                                       "chosen": true
                                     }
                                   ],
                                   "chosen_access_method": {
                                     "type": "scan",
-                                    "records": 3,
-                                    "cost": 2.005126953,
+                                    "records": 9,
+                                    "cost": 2.015380859,
                                     "uses_join_buffering": true
                                   }
                                 },
-                                "rows_for_plan": 2187,
-                                "cost_for_plan": 611.8461426,
-                                "semijoin_strategy_choice": [
-                                  {
-                                    "strategy": "FirstMatch",
-                                    "records": 81,
-                                    "read_time": 2232.809033
-                                  },
-                                  {
-                                    "chosen_strategy": "FirstMatch"
-                                  }
-                                ],
+                                "rows_for_plan": 6561,
+                                "cost_for_plan": 1486.656396,
+                                "semijoin_strategy_choice": [],
                                 "pruned_by_cost": true
                               },
                               {
@@ -5689,25 +5685,25 @@ t_outer_2.a in (select t_inner_3.a from t2 t_inner_3, t1 t_inner_4)	{
                                   "t_outer_2",
                                   "t_inner_3"
                                 ],
-                                "table": "t_inner_2",
+                                "table": "t_inner_4",
                                 "best_access_path": {
                                   "considered_access_paths": [
                                     {
                                       "access_type": "scan",
-                                      "resulting_rows": 9,
-                                      "cost": 2.015380859,
+                                      "resulting_rows": 3,
+                                      "cost": 2.005126953,
                                       "chosen": true
                                     }
                                   ],
                                   "chosen_access_method": {
                                     "type": "scan",
-                                    "records": 9,
-                                    "cost": 2.015380859,
+                                    "records": 3,
+                                    "cost": 2.005126953,
                                     "uses_join_buffering": true
                                   }
                                 },
-                                "rows_for_plan": 6561,
-                                "cost_for_plan": 1486.656396,
+                                "rows_for_plan": 2187,
+                                "cost_for_plan": 611.8461426,
                                 "semijoin_strategy_choice": [],
                                 "pruned_by_cost": true
                               }
@@ -5740,7 +5736,7 @@ t_outer_2.a in (select t_inner_3.a from t2 t_inner_3, t1 t_inner_4)	{
                         "rest_of_plan": [
                           {
                             "plan_prefix": ["t_outer_1", "t_inner_1", "t_inner_4"],
-                            "table": "t_outer_2",
+                            "table": "t_inner_2",
                             "best_access_path": {
                               "considered_access_paths": [
                                 {
@@ -5766,9 +5762,9 @@ t_outer_2.a in (select t_inner_3.a from t2 t_inner_3, t1 t_inner_4)	{
                                   "t_outer_1",
                                   "t_inner_1",
                                   "t_inner_4",
-                                  "t_outer_2"
+                                  "t_inner_2"
                                 ],
-                                "table": "t_inner_2",
+                                "table": "t_outer_2",
                                 "best_access_path": {
                                   "considered_access_paths": [
                                     {
@@ -5795,7 +5791,7 @@ t_outer_2.a in (select t_inner_3.a from t2 t_inner_3, t1 t_inner_4)	{
                                   "t_outer_1",
                                   "t_inner_1",
                                   "t_inner_4",
-                                  "t_outer_2"
+                                  "t_inner_2"
                                 ],
                                 "table": "t_inner_3",
                                 "best_access_path": {
@@ -5823,7 +5819,7 @@ t_outer_2.a in (select t_inner_3.a from t2 t_inner_3, t1 t_inner_4)	{
                           },
                           {
                             "plan_prefix": ["t_outer_1", "t_inner_1", "t_inner_4"],
-                            "table": "t_inner_2",
+                            "table": "t_outer_2",
                             "best_access_path": {
                               "considered_access_paths": [
                                 {
@@ -5896,7 +5892,7 @@ t_outer_2.a in (select t_inner_3.a from t2 t_inner_3, t1 t_inner_4)	{
                         "rest_of_plan": [
                           {
                             "plan_prefix": ["t_outer_1", "t_inner_1", "t_inner_3"],
-                            "table": "t_outer_2",
+                            "table": "t_inner_2",
                             "best_access_path": {
                               "considered_access_paths": [
                                 {
@@ -5922,27 +5918,27 @@ t_outer_2.a in (select t_inner_3.a from t2 t_inner_3, t1 t_inner_4)	{
                                   "t_outer_1",
                                   "t_inner_1",
                                   "t_inner_3",
-                                  "t_outer_2"
+                                  "t_inner_2"
                                 ],
-                                "table": "t_inner_4",
+                                "table": "t_outer_2",
                                 "best_access_path": {
                                   "considered_access_paths": [
                                     {
                                       "access_type": "scan",
-                                      "resulting_rows": 3,
-                                      "cost": 2.005126953,
+                                      "resulting_rows": 9,
+                                      "cost": 2.015380859,
                                       "chosen": true
                                     }
                                   ],
                                   "chosen_access_method": {
                                     "type": "scan",
-                                    "records": 3,
-                                    "cost": 2.005126953,
+                                    "records": 9,
+                                    "cost": 2.015380859,
                                     "uses_join_buffering": true
                                   }
                                 },
-                                "rows_for_plan": 2187,
-                                "cost_for_plan": 611.8461426,
+                                "rows_for_plan": 6561,
+                                "cost_for_plan": 1486.656396,
                                 "semijoin_strategy_choice": [],
                                 "pruned_by_cost": true
                               },
@@ -5951,27 +5947,27 @@ t_outer_2.a in (select t_inner_3.a from t2 t_inner_3, t1 t_inner_4)	{
                                   "t_outer_1",
                                   "t_inner_1",
                                   "t_inner_3",
-                                  "t_outer_2"
+                                  "t_inner_2"
                                 ],
-                                "table": "t_inner_2",
+                                "table": "t_inner_4",
                                 "best_access_path": {
                                   "considered_access_paths": [
                                     {
                                       "access_type": "scan",
-                                      "resulting_rows": 9,
-                                      "cost": 2.015380859,
+                                      "resulting_rows": 3,
+                                      "cost": 2.005126953,
                                       "chosen": true
                                     }
                                   ],
                                   "chosen_access_method": {
                                     "type": "scan",
-                                    "records": 9,
-                                    "cost": 2.015380859,
+                                    "records": 3,
+                                    "cost": 2.005126953,
                                     "uses_join_buffering": true
                                   }
                                 },
-                                "rows_for_plan": 6561,
-                                "cost_for_plan": 1486.656396,
+                                "rows_for_plan": 2187,
+                                "cost_for_plan": 611.8461426,
                                 "semijoin_strategy_choice": [],
                                 "pruned_by_cost": true
                               }
@@ -5979,6 +5975,30 @@ t_outer_2.a in (select t_inner_3.a from t2 t_inner_3, t1 t_inner_4)	{
                           },
                           {
                             "plan_prefix": ["t_outer_1", "t_inner_1", "t_inner_3"],
+                            "table": "t_outer_2",
+                            "best_access_path": {
+                              "considered_access_paths": [
+                                {
+                                  "access_type": "scan",
+                                  "resulting_rows": 9,
+                                  "cost": 2.015380859,
+                                  "chosen": true
+                                }
+                              ],
+                              "chosen_access_method": {
+                                "type": "scan",
+                                "records": 9,
+                                "cost": 2.015380859,
+                                "uses_join_buffering": true
+                              }
+                            },
+                            "rows_for_plan": 729,
+                            "cost_for_plan": 172.4410156,
+                            "semijoin_strategy_choice": [],
+                            "pruned_by_heuristic": true
+                          },
+                          {
+                            "plan_prefix": ["t_outer_1", "t_inner_1", "t_inner_3"],
                             "table": "t_inner_4",
                             "best_access_path": {
                               "considered_access_paths": [
@@ -6007,7 +6027,7 @@ t_outer_2.a in (select t_inner_3.a from t2 t_inner_3, t1 t_inner_4)	{
                                   "t_inner_3",
                                   "t_inner_4"
                                 ],
-                                "table": "t_outer_2",
+                                "table": "t_inner_2",
                                 "best_access_path": {
                                   "considered_access_paths": [
                                     {
@@ -6036,7 +6056,7 @@ t_outer_2.a in (select t_inner_3.a from t2 t_inner_3, t1 t_inner_4)	{
                                   "t_inner_3",
                                   "t_inner_4"
                                 ],
-                                "table": "t_inner_2",
+                                "table": "t_outer_2",
                                 "best_access_path": {
                                   "considered_access_paths": [
                                     {
@@ -6059,30 +6079,6 @@ t_outer_2.a in (select t_inner_3.a from t2 t_inner_3, t1 t_inner_4)	{
                                 "pruned_by_cost": true
                               }
                             ]
-                          },
-                          {
-                            "plan_prefix": ["t_outer_1", "t_inner_1", "t_inner_3"],
-                            "table": "t_inner_2",
-                            "best_access_path": {
-                              "considered_access_paths": [
-                                {
-                                  "access_type": "scan",
-                                  "resulting_rows": 9,
-                                  "cost": 2.015380859,
-                                  "chosen": true
-                                }
-                              ],
-                              "chosen_access_method": {
-                                "type": "scan",
-                                "records": 9,
-                                "cost": 2.015380859,
-                                "uses_join_buffering": true
-                              }
-                            },
-                            "rows_for_plan": 729,
-                            "cost_for_plan": 172.4410156,
-                            "semijoin_strategy_choice": [],
-                            "pruned_by_heuristic": true
                           }
                         ]
                       }
diff --git a/mysql-test/main/selectivity.result b/mysql-test/main/selectivity.result
index 40ab309fffd..2cd3cbdd8eb 100644
--- a/mysql-test/main/selectivity.result
+++ b/mysql-test/main/selectivity.result
@@ -326,8 +326,8 @@ group by c_name, c_custkey, o_orderkey, o_orderdate, o_totalprice
 order by o_totalprice desc, o_orderdate;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	filtered	Extra
 1	PRIMARY	orders	ALL	PRIMARY,i_o_custkey	NULL	NULL	NULL	1500	100.00	Using where; Using temporary; Using filesort
-1	PRIMARY	<subquery2>	eq_ref	distinct_key	distinct_key	4	dbt3_s001.orders.o_orderkey	1	100.00	
 1	PRIMARY	customer	eq_ref	PRIMARY	PRIMARY	4	dbt3_s001.orders.o_custkey	1	100.00	
+1	PRIMARY	<subquery2>	eq_ref	distinct_key	distinct_key	4	dbt3_s001.orders.o_orderkey	1	100.00	
 1	PRIMARY	lineitem	ref	PRIMARY,i_l_orderkey,i_l_orderkey_quantity	i_l_orderkey_quantity	4	dbt3_s001.orders.o_orderkey	4	100.00	Using index
 2	MATERIALIZED	lineitem	index	NULL	i_l_orderkey_quantity	13	NULL	6005	100.00	Using index
 Warnings:
@@ -360,8 +360,8 @@ group by c_name, c_custkey, o_orderkey, o_orderdate, o_totalprice
 order by o_totalprice desc, o_orderdate;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	filtered	Extra
 1	PRIMARY	orders	ALL	PRIMARY,i_o_custkey	NULL	NULL	NULL	1500	100.00	Using where; Using temporary; Using filesort
-1	PRIMARY	<subquery2>	eq_ref	distinct_key	distinct_key	4	dbt3_s001.orders.o_orderkey	1	100.00	
 1	PRIMARY	customer	eq_ref	PRIMARY	PRIMARY	4	dbt3_s001.orders.o_custkey	1	100.00	
+1	PRIMARY	<subquery2>	eq_ref	distinct_key	distinct_key	4	dbt3_s001.orders.o_orderkey	1	100.00	
 1	PRIMARY	lineitem	ref	PRIMARY,i_l_orderkey,i_l_orderkey_quantity	i_l_orderkey_quantity	4	dbt3_s001.orders.o_orderkey	4	100.00	Using index
 2	MATERIALIZED	lineitem	index	NULL	i_l_orderkey_quantity	13	NULL	6005	100.00	Using index
 Warnings:
diff --git a/mysql-test/main/subselect3.result b/mysql-test/main/subselect3.result
index b3758a66a60..28187e0ffdd 100644
--- a/mysql-test/main/subselect3.result
+++ b/mysql-test/main/subselect3.result
@@ -1160,8 +1160,8 @@ id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 1	PRIMARY	A	ALL	NULL	NULL	NULL	NULL	10	
 1	PRIMARY	B	ALL	NULL	NULL	NULL	NULL	10	Using join buffer (flat, BNL join)
 1	PRIMARY	E	ALL	NULL	NULL	NULL	NULL	5	Start temporary; Using join buffer (flat, BNL join)
-1	PRIMARY	D	ALL	NULL	NULL	NULL	NULL	10	Using where; Using join buffer (flat, BNL join)
-1	PRIMARY	C	ALL	NULL	NULL	NULL	NULL	10	Using where; End temporary; Using join buffer (flat, BNL join)
+1	PRIMARY	C	ALL	NULL	NULL	NULL	NULL	10	Using where; Using join buffer (flat, BNL join)
+1	PRIMARY	D	ALL	NULL	NULL	NULL	NULL	10	Using where; End temporary; Using join buffer (flat, BNL join)
 flush status;
 select count(*) from t0 A, t0 B, t0 C, t0 D where D.a in (select a from t1 E where a+1 < 10000 + A.a + B.a +C.a+D.a);
 count(*)
diff --git a/mysql-test/main/subselect3_jcl6.result b/mysql-test/main/subselect3_jcl6.result
index ec799c07003..9df821e07dc 100644
--- a/mysql-test/main/subselect3_jcl6.result
+++ b/mysql-test/main/subselect3_jcl6.result
@@ -1163,8 +1163,8 @@ id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 1	PRIMARY	A	ALL	NULL	NULL	NULL	NULL	10	
 1	PRIMARY	B	ALL	NULL	NULL	NULL	NULL	10	Using join buffer (flat, BNL join)
 1	PRIMARY	E	ALL	NULL	NULL	NULL	NULL	5	Using where; Start temporary; Using join buffer (incremental, BNL join)
-1	PRIMARY	D	hash_ALL	NULL	#hash#$hj	5	test.E.a	10	Using where; Using join buffer (incremental, BNLH join)
-1	PRIMARY	C	ALL	NULL	NULL	NULL	NULL	10	Using where; End temporary; Using join buffer (incremental, BNL join)
+1	PRIMARY	C	ALL	NULL	NULL	NULL	NULL	10	Using where; Using join buffer (incremental, BNL join)
+1	PRIMARY	D	hash_ALL	NULL	#hash#$hj	5	test.E.a	10	Using where; End temporary; Using join buffer (incremental, BNLH join)
 flush status;
 select count(*) from t0 A, t0 B, t0 C, t0 D where D.a in (select a from t1 E where a+1 < 10000 + A.a + B.a +C.a+D.a);
 count(*)
diff --git a/mysql-test/main/subselect_sj.result b/mysql-test/main/subselect_sj.result
index e9a484bbcbf..9febf3d4e5f 100644
--- a/mysql-test/main/subselect_sj.result
+++ b/mysql-test/main/subselect_sj.result
@@ -2500,8 +2500,8 @@ WHERE t1.a = t2.a AND t2.a IN (SELECT b FROM t3 STRAIGHT_JOIN t4);
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 1	PRIMARY	t3	system	NULL	NULL	NULL	NULL	1	
 1	PRIMARY	<subquery2>	ALL	distinct_key	NULL	NULL	NULL	1	
-1	PRIMARY	t2	ref	a	a	5	const	1	Using index
-1	PRIMARY	t1	ref	a	a	5	func	1	Using index
+1	PRIMARY	t1	ref	a	a	5	const	1	Using index
+1	PRIMARY	t2	ref	a	a	5	func	1	Using index
 2	MATERIALIZED	t4	ALL	NULL	NULL	NULL	NULL	0	
 SELECT * FROM t1, t2
 WHERE t1.a = t2.a AND t2.a IN (SELECT b FROM t3 STRAIGHT_JOIN t4);
diff --git a/mysql-test/main/subselect_sj2.result b/mysql-test/main/subselect_sj2.result
index cdf9707dcbd..db6393b909d 100644
--- a/mysql-test/main/subselect_sj2.result
+++ b/mysql-test/main/subselect_sj2.result
@@ -1129,8 +1129,8 @@ id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 1	PRIMARY	alias3	ALL	PRIMARY	NULL	NULL	NULL	#	Using where
 1	PRIMARY	alias4	ref	PRIMARY,c	c	4	test.alias3.d	#	Using index
 1	PRIMARY	alias5	eq_ref	PRIMARY	PRIMARY	4	test.alias4.b	#	Using where; FirstMatch(alias3)
-1	PRIMARY	alias2	ALL	NULL	NULL	NULL	NULL	#	Using join buffer (flat, BNL join)
 1	PRIMARY	alias1	ALL	NULL	NULL	NULL	NULL	#	Using join buffer (flat, BNL join)
+1	PRIMARY	alias2	ALL	NULL	NULL	NULL	NULL	#	Using join buffer (flat, BNL join)
 SELECT COUNT(*) FROM t1 AS alias1, t1 AS alias2, t2 AS alias3
 WHERE alias3.d IN (
 SELECT alias4.c FROM t2 AS alias4, t2 AS alias5
@@ -1150,8 +1150,8 @@ id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 1	PRIMARY	alias3	ALL	PRIMARY	NULL	NULL	NULL	#	Using where
 1	PRIMARY	alias4	ref	PRIMARY,c	c	4	test.alias3.d	#	Using index
 1	PRIMARY	alias5	eq_ref	PRIMARY	PRIMARY	4	test.alias4.b	#	Using where; FirstMatch(alias3)
-1	PRIMARY	alias2	ALL	NULL	NULL	NULL	NULL	#	Using join buffer (flat, BNL join)
 1	PRIMARY	alias1	ALL	NULL	NULL	NULL	NULL	#	Using join buffer (flat, BNL join)
+1	PRIMARY	alias2	ALL	NULL	NULL	NULL	NULL	#	Using join buffer (flat, BNL join)
 SELECT COUNT(*) FROM t1 AS alias1, t1 AS alias2, t2 AS alias3
 WHERE alias3.d IN (
 SELECT alias4.c FROM t2 AS alias4, t2 AS alias5
diff --git a/mysql-test/main/subselect_sj2_jcl6.result b/mysql-test/main/subselect_sj2_jcl6.result
index 84317467e8a..b2ffb033788 100644
--- a/mysql-test/main/subselect_sj2_jcl6.result
+++ b/mysql-test/main/subselect_sj2_jcl6.result
@@ -1142,8 +1142,8 @@ id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 1	PRIMARY	alias3	ALL	PRIMARY	NULL	NULL	NULL	#	Using where
 1	PRIMARY	alias4	ref	PRIMARY,c	c	4	test.alias3.d	#	Using index
 1	PRIMARY	alias5	eq_ref	PRIMARY	PRIMARY	4	test.alias4.b	#	Using where; FirstMatch(alias3)
-1	PRIMARY	alias2	ALL	NULL	NULL	NULL	NULL	#	Using join buffer (flat, BNL join)
-1	PRIMARY	alias1	ALL	NULL	NULL	NULL	NULL	#	Using join buffer (incremental, BNL join)
+1	PRIMARY	alias1	ALL	NULL	NULL	NULL	NULL	#	Using join buffer (flat, BNL join)
+1	PRIMARY	alias2	ALL	NULL	NULL	NULL	NULL	#	Using join buffer (incremental, BNL join)
 SELECT COUNT(*) FROM t1 AS alias1, t1 AS alias2, t2 AS alias3
 WHERE alias3.d IN (
 SELECT alias4.c FROM t2 AS alias4, t2 AS alias5
@@ -1163,8 +1163,8 @@ id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 1	PRIMARY	alias3	ALL	PRIMARY	NULL	NULL	NULL	#	Using where
 1	PRIMARY	alias4	ref	PRIMARY,c	c	4	test.alias3.d	#	Using index
 1	PRIMARY	alias5	eq_ref	PRIMARY	PRIMARY	4	test.alias4.b	#	Using where; FirstMatch(alias3)
-1	PRIMARY	alias2	ALL	NULL	NULL	NULL	NULL	#	Using join buffer (flat, BNL join)
-1	PRIMARY	alias1	ALL	NULL	NULL	NULL	NULL	#	Using join buffer (incremental, BNL join)
+1	PRIMARY	alias1	ALL	NULL	NULL	NULL	NULL	#	Using join buffer (flat, BNL join)
+1	PRIMARY	alias2	ALL	NULL	NULL	NULL	NULL	#	Using join buffer (incremental, BNL join)
 SELECT COUNT(*) FROM t1 AS alias1, t1 AS alias2, t2 AS alias3
 WHERE alias3.d IN (
 SELECT alias4.c FROM t2 AS alias4, t2 AS alias5
diff --git a/mysql-test/main/subselect_sj2_mat.result b/mysql-test/main/subselect_sj2_mat.result
index 54286f1fa82..b5eaa258410 100644
--- a/mysql-test/main/subselect_sj2_mat.result
+++ b/mysql-test/main/subselect_sj2_mat.result
@@ -1131,8 +1131,8 @@ id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 1	PRIMARY	alias3	ALL	PRIMARY	NULL	NULL	NULL	#	Using where
 1	PRIMARY	alias4	ref	PRIMARY,c	c	4	test.alias3.d	#	Using index
 1	PRIMARY	alias5	eq_ref	PRIMARY	PRIMARY	4	test.alias4.b	#	Using where; FirstMatch(alias3)
-1	PRIMARY	alias2	ALL	NULL	NULL	NULL	NULL	#	Using join buffer (flat, BNL join)
 1	PRIMARY	alias1	ALL	NULL	NULL	NULL	NULL	#	Using join buffer (flat, BNL join)
+1	PRIMARY	alias2	ALL	NULL	NULL	NULL	NULL	#	Using join buffer (flat, BNL join)
 SELECT COUNT(*) FROM t1 AS alias1, t1 AS alias2, t2 AS alias3
 WHERE alias3.d IN (
 SELECT alias4.c FROM t2 AS alias4, t2 AS alias5
@@ -1152,8 +1152,8 @@ id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 1	PRIMARY	alias3	ALL	PRIMARY	NULL	NULL	NULL	#	Using where
 1	PRIMARY	alias4	ref	PRIMARY,c	c	4	test.alias3.d	#	Using index
 1	PRIMARY	alias5	eq_ref	PRIMARY	PRIMARY	4	test.alias4.b	#	Using where; FirstMatch(alias3)
-1	PRIMARY	alias2	ALL	NULL	NULL	NULL	NULL	#	Using join buffer (flat, BNL join)
 1	PRIMARY	alias1	ALL	NULL	NULL	NULL	NULL	#	Using join buffer (flat, BNL join)
+1	PRIMARY	alias2	ALL	NULL	NULL	NULL	NULL	#	Using join buffer (flat, BNL join)
 SELECT COUNT(*) FROM t1 AS alias1, t1 AS alias2, t2 AS alias3
 WHERE alias3.d IN (
 SELECT alias4.c FROM t2 AS alias4, t2 AS alias5
@@ -1933,19 +1933,19 @@ AND t3.id_product IN (SELECT id_product FROM t2 t2_4 WHERE t2_4.id_t2 = 34 OR t2
 AND t3.id_product IN (SELECT id_product FROM t2 t2_5 WHERE t2_5.id_t2 = 29 OR t2_5.id_t2 = 28 OR t2_5.id_t2 = 26);
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 1	PRIMARY	t3	index	PRIMARY	PRIMARY	4	NULL	18	Using index
-1	PRIMARY	<subquery3>	eq_ref	distinct_key	distinct_key	4	func	1	Using where
+1	PRIMARY	<subquery5>	eq_ref	distinct_key	distinct_key	4	func	1	Using where
 1	PRIMARY	t5	ALL	NULL	NULL	NULL	NULL	18	Using where; Using join buffer (flat, BNL join)
-1	PRIMARY	<subquery4>	eq_ref	distinct_key	distinct_key	4	func	1	Using where
 1	PRIMARY	<subquery6>	eq_ref	distinct_key	distinct_key	4	func	1	Using where
-1	PRIMARY	<subquery2>	eq_ref	distinct_key	distinct_key	4	func	1	Using where
 1	PRIMARY	t4	eq_ref	PRIMARY	PRIMARY	8	test.t3.id_product,const	1	Using where; Using index
-1	PRIMARY	<subquery5>	eq_ref	distinct_key	distinct_key	4	func	1	Using where
+1	PRIMARY	<subquery3>	eq_ref	distinct_key	distinct_key	4	func	1	Using where
 1	PRIMARY	t1	index	NULL	PRIMARY	8	NULL	73	Using where; Using index; Using join buffer (flat, BNL join)
+1	PRIMARY	<subquery4>	eq_ref	distinct_key	distinct_key	4	func	1	Using where
+1	PRIMARY	<subquery2>	eq_ref	distinct_key	distinct_key	4	func	1	Using where
+5	MATERIALIZED	t2_4	range	id_t2,id_product	id_t2	5	NULL	18	Using index condition; Using where
+6	MATERIALIZED	t2_5	range	id_t2,id_product	id_t2	5	NULL	31	Using index condition; Using where
 3	MATERIALIZED	t2_2	ref	id_t2,id_product	id_t2	5	const	12	
 4	MATERIALIZED	t2_3	range	id_t2,id_product	id_t2	5	NULL	33	Using index condition; Using where
-6	MATERIALIZED	t2_5	range	id_t2,id_product	id_t2	5	NULL	31	Using index condition; Using where
 2	MATERIALIZED	t2_1	ALL	id_t2,id_product	NULL	NULL	NULL	223	Using where
-5	MATERIALIZED	t2_4	range	id_t2,id_product	id_t2	5	NULL	18	Using index condition; Using where
 set optimizer_switch='rowid_filter=default';
 drop table t1,t2,t3,t4,t5;
 set global innodb_stats_persistent= @innodb_stats_persistent_save;
diff --git a/mysql-test/main/subselect_sj_jcl6.result b/mysql-test/main/subselect_sj_jcl6.result
index c485b5e5f39..9eac5c65f82 100644
--- a/mysql-test/main/subselect_sj_jcl6.result
+++ b/mysql-test/main/subselect_sj_jcl6.result
@@ -2511,8 +2511,8 @@ WHERE t1.a = t2.a AND t2.a IN (SELECT b FROM t3 STRAIGHT_JOIN t4);
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 1	PRIMARY	t3	system	NULL	NULL	NULL	NULL	1	
 1	PRIMARY	<subquery2>	ALL	distinct_key	NULL	NULL	NULL	1	
-1	PRIMARY	t2	ref	a	a	5	const	1	Using index
-1	PRIMARY	t1	ref	a	a	5	func	1	Using index
+1	PRIMARY	t1	ref	a	a	5	const	1	Using index
+1	PRIMARY	t2	ref	a	a	5	func	1	Using index
 2	MATERIALIZED	t4	ALL	NULL	NULL	NULL	NULL	0	
 SELECT * FROM t1, t2
 WHERE t1.a = t2.a AND t2.a IN (SELECT b FROM t3 STRAIGHT_JOIN t4);
diff --git a/sql/sql_select.cc b/sql/sql_select.cc
index a059986d611..32f5e41e50d 100644
--- a/sql/sql_select.cc
+++ b/sql/sql_select.cc
@@ -9176,8 +9176,13 @@ greedy_search(JOIN      *join,
     while (pos && best_table != pos)
       pos= join->best_ref[++best_idx];
     DBUG_ASSERT((pos != NULL)); // should always find 'best_table'
-    /* move 'best_table' at the first free position in the array of joins */
-    swap_variables(JOIN_TAB*, join->best_ref[idx], join->best_ref[best_idx]);
+    /*
+      move 'best_table' at the first free position in the array of joins,
+      keeping the sorted table order intact
+    */
+    memmove(join->best_ref + idx + 1, join->best_ref + idx,
+            sizeof(JOIN_TAB*) * (best_idx - idx));
+    join->best_ref[idx]= best_table;
 
     /* compute the cost of the new plan extended with 'best_table' */
     record_count= COST_MULT(record_count, join->positions[idx].records_read);
@@ -9924,7 +9929,7 @@ best_extension_by_limited_search(JOIN      *join,
      'join' is a partial plan with lower cost than the best plan so far,
      so continue expanding it further with the tables in 'remaining_tables'.
   */
-  JOIN_TAB *s;
+  JOIN_TAB *s, **pos;
   double best_record_count= DBL_MAX;
   double best_read_time=    DBL_MAX;
   bool disable_jbuf= join->thd->variables.join_cache_level == 0;
@@ -9944,7 +9949,7 @@ best_extension_by_limited_search(JOIN      *join,
   DBUG_EXECUTE("opt", print_plan(join, idx, record_count, read_time, read_time,
                                 "part_plan"););
 
-  /* 
+  /*
     If we are searching for the execution plan of a materialized semi-join nest
     then allowed_tables contains bits only for the tables from this nest.
   */
@@ -9952,11 +9957,13 @@ best_extension_by_limited_search(JOIN      *join,
   if (join->emb_sjm_nest)
     allowed_tables= join->emb_sjm_nest->sj_inner_tables & ~join->const_table_map;
 
-  for (JOIN_TAB **pos= join->best_ref + idx ; (s= *pos) ; pos++)
+  for (pos= join->best_ref + idx ; (s= *pos) ; pos++)
   {
     table_map real_table_bit= s->table->map;
     DBUG_ASSERT(remaining_tables & real_table_bit);
 
+    swap_variables(JOIN_TAB*, join->best_ref[idx], *pos);
+
     if ((allowed_tables & real_table_bit) &&
         !(remaining_tables & s->dependent) &&
         !check_interleaving_with_nj(s))
@@ -10069,7 +10076,6 @@ best_extension_by_limited_search(JOIN      *join,
           allowed_tables)
       {
         /* Recursively expand the current partial plan */
-        swap_variables(JOIN_TAB*, join->best_ref[idx], *pos);
         Json_writer_array trace_rest(thd, "rest_of_plan");
         best_res=
           best_extension_by_limited_search(join,
@@ -10082,8 +10088,7 @@ best_extension_by_limited_search(JOIN      *join,
                                            prune_level,
                                            use_cond_selectivity);
         if ((int) best_res < (int) SEARCH_OK)
-          DBUG_RETURN(best_res);                // Abort
-        swap_variables(JOIN_TAB*, join->best_ref[idx], *pos);
+          goto end;                             // Return best_res
         if (best_res == SEARCH_FOUND_EDGE &&
             check_if_edge_table(join->positions+ idx,
                                 pushdown_cond_selectivity) !=
@@ -10128,11 +10133,27 @@ best_extension_by_limited_search(JOIN      *join,
       if (best_res == SEARCH_FOUND_EDGE)
       {
         trace_one_table.add("pruned_by_hanging_leaf", true);
-        DBUG_RETURN(best_res);
+        goto end;
       }
     }
   }
-  DBUG_RETURN(SEARCH_OK);
+  best_res= SEARCH_OK;
+
+end:
+  /* Restore original table order */
+  if (!*pos)
+    pos--;                                      // Revert last pos++ in for loop
+  if (pos != join->best_ref + idx)
+  {
+    JOIN_TAB *tmp= join->best_ref[idx];
+    uint elements= (uint) (pos - (join->best_ref + idx));
+
+    memmove((void*) (join->best_ref + idx),
+            (void*) (join->best_ref + idx + 1),
+            elements * sizeof(JOIN_TAB*));
+    *pos= tmp;
+  }
+  DBUG_RETURN(best_res);
 }