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, 68 insertions, 72 deletions

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
                           }
                         ]
                       }