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.

1 files changed, 8 insertions, 8 deletions

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;