MDEV-28073 Query performance degradation in newer MariaDB versions when using many tables

The issue was that best_extension_by_limited_search() had to go through
too many plans with the same cost as there where many EQ_REF tables.

Fixed by shortcutting EQ_REF (AND REF) when the result only contains one
row. This got the optimization time down from hours to sub seconds.

The only known downside with this patch is that in some cases a table
with ref and 1 record may be used before on EQ_REF table. The faster
optimzation phase should compensate for this.

9 files changed, 164 insertions, 136 deletions

diff --git a/mysql-test/main/opt_trace.result b/mysql-test/main/opt_trace.result
index 044db82b961..5504f4da81e 100644
--- a/mysql-test/main/opt_trace.result
+++ b/mysql-test/main/opt_trace.result
@@ -145,8 +145,7 @@ select * from v1	{
                   }
                 },
                 "rows_for_plan": 1,
-                "cost_for_plan": 2.404394531,
-                "estimated_join_cardinality": 1
+                "cost_for_plan": 2.404394531
               }
             ]
           },
@@ -296,8 +295,7 @@ select * from (select * from t1 where t1.a=1)q	{
                   }
                 },
                 "rows_for_plan": 1,
-                "cost_for_plan": 2.404394531,
-                "estimated_join_cardinality": 1
+                "cost_for_plan": 2.404394531
               }
             ]
           },
@@ -454,8 +452,7 @@ select * from v2	{
                       },
                       "rows_for_plan": 1,
                       "cost_for_plan": 2.404394531,
-                      "cost_for_sorting": 1,
-                      "estimated_join_cardinality": 1
+                      "cost_for_sorting": 1
                     }
                   ]
                 },
@@ -525,8 +522,7 @@ select * from v2	{
                   }
                 },
                 "rows_for_plan": 2,
-                "cost_for_plan": 2.4,
-                "estimated_join_cardinality": 2
+                "cost_for_plan": 2.4
               }
             ]
           },
@@ -662,8 +658,7 @@ explain select * from v2	{
                   }
                 },
                 "rows_for_plan": 10,
-                "cost_for_plan": 4.021972656,
-                "estimated_join_cardinality": 10
+                "cost_for_plan": 4.021972656
               }
             ]
           },
@@ -780,8 +775,7 @@ explain select * from v1	{
                       },
                       "rows_for_plan": 10,
                       "cost_for_plan": 4.021972656,
-                      "cost_for_sorting": 10,
-                      "estimated_join_cardinality": 10
+                      "cost_for_sorting": 10
                     }
                   ]
                 },
@@ -845,8 +839,7 @@ explain select * from v1	{
                   }
                 },
                 "rows_for_plan": 10,
-                "cost_for_plan": 12,
-                "estimated_join_cardinality": 10
+                "cost_for_plan": 12
               }
             ]
           },
@@ -1047,7 +1040,7 @@ explain select * from t1,t2 where t1.a=t2.b+2 and t2.a= t1.b	{
                     },
                     "rows_for_plan": 100,
                     "cost_for_plan": 242.3759623,
-                    "estimated_join_cardinality": 100
+                    "pruned_by_hanging_leaf": true
                   }
                 ]
               },
@@ -1278,8 +1271,7 @@ EXPLAIN SELECT DISTINCT a FROM t1	{
                   }
                 },
                 "rows_for_plan": 5,
-                "cost_for_plan": 7.25,
-                "estimated_join_cardinality": 5
+                "cost_for_plan": 7.25
               }
             ]
           },
@@ -1470,8 +1462,7 @@ EXPLAIN SELECT MIN(d) FROM t1 where b=2 and c=3  group by a	{
                 },
                 "rows_for_plan": 8,
                 "cost_for_plan": 3.8,
-                "cost_for_sorting": 8,
-                "estimated_join_cardinality": 8
+                "cost_for_sorting": 8
               }
             ]
           },
@@ -1669,8 +1660,7 @@ EXPLAIN SELECT id,MIN(a),MAX(a) FROM t1 WHERE a>=20010104e0 GROUP BY id	{
                 },
                 "rows_for_plan": 9,
                 "cost_for_plan": 4.15,
-                "cost_for_sorting": 9,
-                "estimated_join_cardinality": 9
+                "cost_for_sorting": 9
               }
             ]
           },
@@ -1857,8 +1847,7 @@ EXPLAIN SELECT * FROM t1 WHERE a = 20010104e0 GROUP BY id	{
                 },
                 "rows_for_plan": 9,
                 "cost_for_plan": 4.15,
-                "cost_for_sorting": 9,
-                "estimated_join_cardinality": 9
+                "cost_for_sorting": 9
               }
             ]
           },
@@ -2140,8 +2129,7 @@ explain  select * from t1 where a=1 and b=2 order by c limit 1	{
                   }
                 },
                 "rows_for_plan": 21,
-                "cost_for_plan": 25.34242739,
-                "estimated_join_cardinality": 21
+                "cost_for_plan": 25.34242739
               }
             ]
           },
@@ -2392,8 +2380,7 @@ select t1.a from t1 left join t2 on t1.a=t2.a	{
                   }
                 },
                 "rows_for_plan": 4,
-                "cost_for_plan": 2.806835937,
-                "estimated_join_cardinality": 4
+                "cost_for_plan": 2.806835937
               }
             ]
           },
@@ -2561,7 +2548,7 @@ explain select * from t1 left join t2 on t2.a=t1.a	{
                     },
                     "rows_for_plan": 4,
                     "cost_for_plan": 7.606835937,
-                    "estimated_join_cardinality": 4
+                    "pruned_by_hanging_leaf": true
                   }
                 ]
               }
@@ -2740,8 +2727,7 @@ explain select t1.a from t1 left join (t2 join t3 on t2.b=t3.b) on t2.a=t1.a and
                   }
                 },
                 "rows_for_plan": 4,
-                "cost_for_plan": 2.806835937,
-                "estimated_join_cardinality": 4
+                "cost_for_plan": 2.806835937
               }
             ]
           },
@@ -2948,8 +2934,7 @@ explain extended select * from t1 where a in (select pk from t10)	{
                         }
                       },
                       "rows_for_plan": 10,
-                      "cost_for_plan": 4.021972656,
-                      "estimated_join_cardinality": 10
+                      "cost_for_plan": 4.021972656
                     }
                   ]
                 }
@@ -3021,8 +3006,7 @@ explain extended select * from t1 where a in (select pk from t10)	{
                       {
                         "chosen_strategy": "SJ-Materialization"
                       }
-                    ],
-                    "estimated_join_cardinality": 3
+                    ]
                   }
                 ]
               },
@@ -3427,7 +3411,7 @@ explain select * from t1 where pk = 2 and a=5 and b=1	{
                 },
                 "rows_for_plan": 1,
                 "cost_for_plan": 0.326073957,
-                "estimated_join_cardinality": 1
+                "pruned_by_hanging_leaf": true
               }
             ]
           },
@@ -3555,8 +3539,7 @@ select f1(a) from t1	{
                   }
                 },
                 "rows_for_plan": 4,
-                "cost_for_plan": 2.806835937,
-                "estimated_join_cardinality": 4
+                "cost_for_plan": 2.806835937
               }
             ]
           },
@@ -3652,8 +3635,7 @@ select f2(a) from t1	{
                   }
                 },
                 "rows_for_plan": 4,
-                "cost_for_plan": 2.806835937,
-                "estimated_join_cardinality": 4
+                "cost_for_plan": 2.806835937
               }
             ]
           },
@@ -3699,7 +3681,7 @@ a
 2
 select length(trace) from INFORMATION_SCHEMA.OPTIMIZER_TRACE;
 length(trace)
-2141
+2092
 set optimizer_trace_max_mem_size=100;
 select * from t1;
 a
@@ -3713,7 +3695,7 @@ select * from t1	{
       "join_preparation": {
         "select_id": 1,
         "steps": [
-        	2041	0
+        	1992	0
 set optimizer_trace_max_mem_size=0;
 select * from t1;
 a
@@ -3721,7 +3703,7 @@ a
 2
 select * from INFORMATION_SCHEMA.OPTIMIZER_TRACE;
 QUERY	TRACE	MISSING_BYTES_BEYOND_MAX_MEM_SIZE	INSUFFICIENT_PRIVILEGES
-select * from t1		2141	0
+select * from t1		2092	0
 drop table t1;
 set optimizer_trace='enabled=off';
 set @@optimizer_trace_max_mem_size= @save_optimizer_trace_max_mem_size;
@@ -4064,7 +4046,7 @@ explain delete t0,t1 from t0, t1 where t0.a=t1.a and t1.a<3	{
                     },
                     "rows_for_plan": 3,
                     "cost_for_plan": 4.948514767,
-                    "estimated_join_cardinality": 3
+                    "pruned_by_hanging_leaf": true
                   }
                 ]
               },
@@ -4263,8 +4245,7 @@ explain select * from (select rand() from t1)q	{
                         }
                       },
                       "rows_for_plan": 3,
-                      "cost_for_plan": 2.605126953,
-                      "estimated_join_cardinality": 3
+                      "cost_for_plan": 2.605126953
                     }
                   ]
                 },
@@ -4328,8 +4309,7 @@ explain select * from (select rand() from t1)q	{
                   }
                 },
                 "rows_for_plan": 3,
-                "cost_for_plan": 3.6,
-                "estimated_join_cardinality": 3
+                "cost_for_plan": 3.6
               }
             ]
           },
@@ -4557,8 +4537,7 @@ explain select * from t1 where a in (select t_inner_1.a from t1 t_inner_1, t1 t_
                             }
                           },
                           "rows_for_plan": 9,
-                          "cost_for_plan": 6.410253906,
-                          "estimated_join_cardinality": 9
+                          "cost_for_plan": 6.410253906
                         }
                       ]
                     },
@@ -4678,8 +4657,7 @@ explain select * from t1 where a in (select t_inner_1.a from t1 t_inner_1, t1 t_
                           {
                             "chosen_strategy": "SJ-Materialization"
                           }
-                        ],
-                        "estimated_join_cardinality": 3
+                        ]
                       }
                     ]
                   },
@@ -5222,8 +5200,7 @@ t_outer_2.a in (select t_inner_3.a from t2 t_inner_3, t1 t_inner_4)	{
                                       {
                                         "chosen_strategy": "DuplicateWeedout"
                                       }
-                                    ],
-                                    "estimated_join_cardinality": 27
+                                    ]
                                   }
                                 ]
                               },
@@ -5345,8 +5322,7 @@ t_outer_2.a in (select t_inner_3.a from t2 t_inner_3, t1 t_inner_4)	{
                                       {
                                         "chosen_strategy": "DuplicateWeedout"
                                       }
-                                    ],
-                                    "estimated_join_cardinality": 27
+                                    ]
                                   }
                                 ]
                               },
@@ -6667,8 +6643,7 @@ t_outer_2.a in (select t_inner_3.a from t2 t_inner_3, t1 t_inner_4)	{
                             }
                           },
                           "rows_for_plan": 27,
-                          "cost_for_plan": 10.02050781,
-                          "estimated_join_cardinality": 27
+                          "cost_for_plan": 10.02050781
                         }
                       ]
                     },
@@ -6741,8 +6716,7 @@ t_outer_2.a in (select t_inner_3.a from t2 t_inner_3, t1 t_inner_4)	{
                             }
                           },
                           "rows_for_plan": 27,
-                          "cost_for_plan": 10.02050781,
-                          "estimated_join_cardinality": 27
+                          "cost_for_plan": 10.02050781
                         }
                       ]
                     },
@@ -6961,8 +6935,7 @@ t_outer_2.a in (select t_inner_3.a from t2 t_inner_3, t1 t_inner_4)	{
                                       {
                                         "chosen_strategy": "SJ-Materialization"
                                       }
-                                    ],
-                                    "estimated_join_cardinality": 27
+                                    ]
                                   }
                                 ]
                               },
@@ -8124,8 +8097,7 @@ JSON_DETAILED(JSON_EXTRACT(trace, '$**.considered_execution_plans'))
                         }
                     },
                     "rows_for_plan": 4777.832031,
-                    "cost_for_plan": 1216.438354,
-                    "estimated_join_cardinality": 4777.832031
+                    "cost_for_plan": 1216.438354
                 }
             ]
         },
@@ -8466,7 +8438,7 @@ JSON_DETAILED(JSON_EXTRACT(trace, '$**.considered_execution_plans'))
                     "rows_for_plan": 10,
                     "cost_for_plan": 26.0278306,
                     "cost_for_sorting": 10,
-                    "estimated_join_cardinality": 10
+                    "pruned_by_hanging_leaf": true
                 }
             ]
         },
@@ -8786,8 +8758,7 @@ select count(*) from seq_1_to_10000000	{
                   }
                 },
                 "rows_for_plan": 10000000,
-                "cost_for_plan": 12000000,
-                "estimated_join_cardinality": 10000000
+                "cost_for_plan": 12000000
               }
             ]
           },
@@ -9202,8 +9173,7 @@ json_detailed(json_extract(trace, '$**.choose_best_splitting'))
                     },
                     "rows_for_plan": 1.8367,
                     "cost_for_plan": 2.367925794,
-                    "cost_for_sorting": 1.8367,
-                    "estimated_join_cardinality": 1.8367
+                    "cost_for_sorting": 1.8367
                 }
             ]
         },
diff --git a/mysql-test/main/opt_trace_index_merge.result b/mysql-test/main/opt_trace_index_merge.result
index f1e13586eda..335e408bddd 100644
--- a/mysql-test/main/opt_trace_index_merge.result
+++ b/mysql-test/main/opt_trace_index_merge.result
@@ -221,8 +221,7 @@ explain select * from t1 where a=1 or b=1	{
                   }
                 },
                 "rows_for_plan": 2,
-                "cost_for_plan": 2.884903732,
-                "estimated_join_cardinality": 2
+                "cost_for_plan": 2.884903732
               }
             ]
           },
diff --git a/mysql-test/main/opt_trace_index_merge_innodb.result b/mysql-test/main/opt_trace_index_merge_innodb.result
index fbc7faa0d04..b9c59c7a100 100644
--- a/mysql-test/main/opt_trace_index_merge_innodb.result
+++ b/mysql-test/main/opt_trace_index_merge_innodb.result
@@ -227,7 +227,7 @@ explain select * from t1 where pk1 != 0  and key1 = 1	{
                 },
                 "rows_for_plan": 1,
                 "cost_for_plan": 1.325146475,
-                "estimated_join_cardinality": 1
+                "pruned_by_hanging_leaf": true
               }
             ]
           },
diff --git a/mysql-test/main/opt_trace_security.result b/mysql-test/main/opt_trace_security.result
index e1937e744a4..83d98c4c183 100644
--- a/mysql-test/main/opt_trace_security.result
+++ b/mysql-test/main/opt_trace_security.result
@@ -107,8 +107,7 @@ select * from db1.t1	{
                   }
                 },
                 "rows_for_plan": 3,
-                "cost_for_plan": 2.605126953,
-                "estimated_join_cardinality": 3
+                "cost_for_plan": 2.605126953
               }
             ]
           },
@@ -229,8 +228,7 @@ select * from db1.v1	{
                   }
                 },
                 "rows_for_plan": 3,
-                "cost_for_plan": 2.605126953,
-                "estimated_join_cardinality": 3
+                "cost_for_plan": 2.605126953
               }
             ]
           },
diff --git a/mysql-test/main/subselect_sj2.result b/mysql-test/main/subselect_sj2.result
index 2d0df9a05d0..cdf9707dcbd 100644
--- a/mysql-test/main/subselect_sj2.result
+++ b/mysql-test/main/subselect_sj2.result
@@ -466,11 +466,11 @@ where t0.a in ( select t1.a from t1,t2 where t2.a=t0.a and
 t1.b=t2.b);
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	filtered	Extra
 1	PRIMARY	t0	ALL	NULL	NULL	NULL	NULL	5	100.00	Using where
-1	PRIMARY	t2	eq_ref	PRIMARY	PRIMARY	4	test.t0.a	1	100.00	
-1	PRIMARY	t1	ref	a	a	5	test.t0.a	1	100.00	Using where; FirstMatch(t2)
+1	PRIMARY	t1	ref	a	a	5	test.t0.a	1	100.00	Start temporary
+1	PRIMARY	t2	eq_ref	PRIMARY	PRIMARY	4	test.t0.a	1	100.00	Using where; End temporary
 Warnings:
 Note	1276	Field or reference 'test.t0.a' of SELECT #2 was resolved in SELECT #1
-Note	1003	select `test`.`t0`.`a` AS `a` from `test`.`t2` semi join (`test`.`t1`) join `test`.`t0` where `test`.`t2`.`a` = `test`.`t0`.`a` and `test`.`t1`.`a` = `test`.`t0`.`a` and `test`.`t1`.`b` = `test`.`t2`.`b`
+Note	1003	select `test`.`t0`.`a` AS `a` from `test`.`t2` semi join (`test`.`t1`) join `test`.`t0` where `test`.`t1`.`a` = `test`.`t0`.`a` and `test`.`t2`.`a` = `test`.`t0`.`a` and `test`.`t2`.`b` = `test`.`t1`.`b`
 update t1 set a=3, b=11 where a=4;
 update t2 set b=11 where a=3;
 select * from t0 where t0.a in 
diff --git a/mysql-test/main/subselect_sj2_jcl6.result b/mysql-test/main/subselect_sj2_jcl6.result
index f0e8e9b4881..84317467e8a 100644
--- a/mysql-test/main/subselect_sj2_jcl6.result
+++ b/mysql-test/main/subselect_sj2_jcl6.result
@@ -477,11 +477,11 @@ where t0.a in ( select t1.a from t1,t2 where t2.a=t0.a and
 t1.b=t2.b);
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	filtered	Extra
 1	PRIMARY	t0	ALL	NULL	NULL	NULL	NULL	5	100.00	Using where
-1	PRIMARY	t2	eq_ref	PRIMARY	PRIMARY	4	test.t0.a	1	100.00	Using join buffer (flat, BKA join); Key-ordered Rowid-ordered scan
-1	PRIMARY	t1	ref	a	a	5	test.t0.a	1	100.00	Using where; FirstMatch(t2); Using join buffer (incremental, BKA join); Key-ordered Rowid-ordered scan
+1	PRIMARY	t1	ref	a	a	5	test.t0.a	1	100.00	Start temporary; Using join buffer (flat, BKA join); Key-ordered Rowid-ordered scan
+1	PRIMARY	t2	eq_ref	PRIMARY	PRIMARY	4	test.t0.a	1	100.00	Using where; End temporary; Using join buffer (incremental, BKA join); Key-ordered Rowid-ordered scan
 Warnings:
 Note	1276	Field or reference 'test.t0.a' of SELECT #2 was resolved in SELECT #1
-Note	1003	select `test`.`t0`.`a` AS `a` from `test`.`t2` semi join (`test`.`t1`) join `test`.`t0` where `test`.`t2`.`a` = `test`.`t0`.`a` and `test`.`t1`.`a` = `test`.`t0`.`a` and `test`.`t1`.`b` = `test`.`t2`.`b`
+Note	1003	select `test`.`t0`.`a` AS `a` from `test`.`t2` semi join (`test`.`t1`) join `test`.`t0` where `test`.`t1`.`a` = `test`.`t0`.`a` and `test`.`t2`.`a` = `test`.`t0`.`a` and `test`.`t2`.`b` = `test`.`t1`.`b`
 update t1 set a=3, b=11 where a=4;
 update t2 set b=11 where a=3;
 # Not anymore:
diff --git a/mysql-test/main/subselect_sj2_mat.result b/mysql-test/main/subselect_sj2_mat.result
index 9b497ade58b..54286f1fa82 100644
--- a/mysql-test/main/subselect_sj2_mat.result
+++ b/mysql-test/main/subselect_sj2_mat.result
@@ -468,11 +468,11 @@ where t0.a in ( select t1.a from t1,t2 where t2.a=t0.a and
 t1.b=t2.b);
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	filtered	Extra
 1	PRIMARY	t0	ALL	NULL	NULL	NULL	NULL	5	100.00	Using where
-1	PRIMARY	t2	eq_ref	PRIMARY	PRIMARY	4	test.t0.a	1	100.00	
-1	PRIMARY	t1	ref	a	a	5	test.t0.a	1	100.00	Using where; FirstMatch(t2)
+1	PRIMARY	t1	ref	a	a	5	test.t0.a	1	100.00	Start temporary
+1	PRIMARY	t2	eq_ref	PRIMARY	PRIMARY	4	test.t0.a	1	100.00	Using where; End temporary
 Warnings:
 Note	1276	Field or reference 'test.t0.a' of SELECT #2 was resolved in SELECT #1
-Note	1003	select `test`.`t0`.`a` AS `a` from `test`.`t2` semi join (`test`.`t1`) join `test`.`t0` where `test`.`t2`.`a` = `test`.`t0`.`a` and `test`.`t1`.`a` = `test`.`t0`.`a` and `test`.`t1`.`b` = `test`.`t2`.`b`
+Note	1003	select `test`.`t0`.`a` AS `a` from `test`.`t2` semi join (`test`.`t1`) join `test`.`t0` where `test`.`t1`.`a` = `test`.`t0`.`a` and `test`.`t2`.`a` = `test`.`t0`.`a` and `test`.`t2`.`b` = `test`.`t1`.`b`
 update t1 set a=3, b=11 where a=4;
 update t2 set b=11 where a=3;
 select * from t0 where t0.a in 
diff --git a/sql/sql_select.cc b/sql/sql_select.cc
index 39673a0aaa7..5f4881b2f54 100644
--- a/sql/sql_select.cc
+++ b/sql/sql_select.cc
@@ -111,12 +111,19 @@ static void optimize_straight_join(JOIN *join, table_map join_tables);
 static bool greedy_search(JOIN *join, table_map remaining_tables,
                           uint depth, uint prune_level,
                           uint use_cond_selectivity);
-static bool best_extension_by_limited_search(JOIN *join,
-                                             table_map remaining_tables,
-                                             uint idx, double record_count,
-                                             double read_time, uint depth,
-                                             uint prune_level,
-                                             uint use_cond_selectivity);
+enum enum_best_search {
+  SEARCH_ABORT= -2,
+  SEARCH_ERROR= -1,
+  SEARCH_OK= 0,
+  SEARCH_FOUND_EDGE=1
+};
+static enum_best_search
+best_extension_by_limited_search(JOIN *join,
+                                 table_map remaining_tables,
+                                 uint idx, double record_count,
+                                 double read_time, uint depth,
+                                 uint prune_level,
+                                 uint use_cond_selectivity);
 static uint determine_search_depth(JOIN* join);
 C_MODE_START
 static int join_tab_cmp(const void *dummy, const void* ptr1, const void* ptr2);
@@ -8446,6 +8453,7 @@ best_access_path(JOIN      *join,
   pos->records_read= records;
   pos->read_time=    best;
   pos->key=          best_key;
+  pos->type=         best_type;
   pos->table=        s;
   pos->ref_depend_map= best_ref_depends_map;
   pos->loosescan_picker.loosescan_key= MAX_KEY;
@@ -9101,9 +9109,12 @@ greedy_search(JOIN      *join,
   do {
     /* Find the extension of the current QEP with the lowest cost */
     join->best_read= DBL_MAX;
-    if (best_extension_by_limited_search(join, remaining_tables, idx, record_count,
-                                         read_time, search_depth, prune_level,
-                                         use_cond_selectivity))
+    if ((int) best_extension_by_limited_search(join, remaining_tables, idx,
+                                               record_count,
+                                               read_time, search_depth,
+                                               prune_level,
+                                               use_cond_selectivity) <
+        (int) SEARCH_OK)
       DBUG_RETURN(TRUE);
     /*
       'best_read < DBL_MAX' means that optimizer managed to find
@@ -9739,6 +9750,28 @@ exit:
 }
 
 
+/*
+  Check if the table is an EQ_REF or similar table and there is no cost
+  to gain by moveing it to a later stage.
+  We call such a table a edge table (or hanging leaf) as it will read at
+  most one row and will not add to the number of row combinations in the join.
+*/
+
+static inline enum_best_search
+check_if_edge_table(POSITION *pos,
+                    double pushdown_cond_selectivity)
+{
+
+  if ((pos->type == JT_EQ_REF ||
+       (pos->type == JT_REF &&
+        pos->records_read == 1 &&
+        !pos->range_rowid_filter_info)) &&
+      pushdown_cond_selectivity >= 0.999)
+    return SEARCH_FOUND_EDGE;
+  return SEARCH_OK;
+}
+
+
 /**
   Find a good, possibly optimal, query execution plan (QEP) by a possibly
   exhaustive search.
@@ -9853,12 +9886,17 @@ exit:
                           pushed to a table should be taken into account
 
   @retval
-    FALSE       ok
+    enum_best_search::SEARCH_OK          All fine
   @retval
-    TRUE        Fatal error
+    enum_best_search::SEARCH_FOUND_EDGE  All remaning tables are edge tables
+  @retval
+    enum_best_search::SEARCH_ABORT       Killed by user
+  @retval
+    enum_best_search::SEARCH_ERROR       Fatal error
 */
 
-static bool
+
+static enum_best_search
 best_extension_by_limited_search(JOIN      *join,
                                  table_map remaining_tables,
                                  uint      idx,
@@ -9868,9 +9906,17 @@ best_extension_by_limited_search(JOIN      *join,
                                  uint      prune_level,
                                  uint      use_cond_selectivity)
 {
-  DBUG_ENTER("best_extension_by_limited_search");
-
   THD *thd= join->thd;
+  /*
+     '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;
+  double best_record_count= DBL_MAX;
+  double best_read_time=    DBL_MAX;
+  bool disable_jbuf= join->thd->variables.join_cache_level == 0;
+  enum_best_search best_res;
+  DBUG_ENTER("best_extension_by_limited_search");
 
   DBUG_EXECUTE_IF("show_explain_probe_best_ext_lim_search", 
                   if (dbug_user_var_equals_int(thd, 
@@ -9880,19 +9926,7 @@ best_extension_by_limited_search(JOIN      *join,
                  );
 
   if (unlikely(thd->check_killed()))  // Abort
-    DBUG_RETURN(TRUE);
-
-  DBUG_EXECUTE("opt", print_plan(join, idx, read_time, record_count, idx,
-                                 "SOFAR:"););
-
-  /* 
-     '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;
-  double best_record_count= DBL_MAX;
-  double best_read_time=    DBL_MAX;
-  bool disable_jbuf= join->thd->variables.join_cache_level == 0;
+    DBUG_RETURN(SEARCH_ABORT);
 
   DBUG_EXECUTE("opt", print_plan(join, idx, record_count, read_time, read_time,
                                 "part_plan"););
@@ -9914,9 +9948,11 @@ best_extension_by_limited_search(JOIN      *join,
         (!idx || !check_interleaving_with_nj(s)))
     {
       double current_record_count, current_read_time;
+      double partial_join_cardinality;
       POSITION *position= join->positions + idx;
-
+      POSITION loose_scan_pos;
       Json_writer_object trace_one_table(thd);
+
       if (unlikely(thd->trace_started()))
       {
         trace_plan_prefix(join, idx, remaining_tables);
@@ -9924,7 +9960,6 @@ best_extension_by_limited_search(JOIN      *join,
       }
 
       /* Find the best access method from 's' to the current partial plan */
-      POSITION loose_scan_pos;
       best_access_path(join, s, remaining_tables, join->positions, idx,
                        disable_jbuf, record_count, position, &loose_scan_pos);
 
@@ -9999,32 +10034,51 @@ best_extension_by_limited_search(JOIN      *join,
       double pushdown_cond_selectivity= 1.0;
       if (use_cond_selectivity > 1)
         pushdown_cond_selectivity= table_cond_selectivity(join, idx, s,
-				                          remaining_tables &
+                                                          remaining_tables &
                                                           ~real_table_bit);
       join->positions[idx].cond_selectivity= pushdown_cond_selectivity;
 
-      if (unlikely(thd->trace_started()) && pushdown_cond_selectivity < 1.0)
-        trace_one_table.add("selectivity", pushdown_cond_selectivity);
+      partial_join_cardinality= (current_record_count *
+                                 pushdown_cond_selectivity);
 
-      double partial_join_cardinality= current_record_count *
-                                        pushdown_cond_selectivity;
-      if ( (search_depth > 1) && (remaining_tables & ~real_table_bit) & allowed_tables )
-      { /* Recursively expand the current partial plan */
+      if (unlikely(thd->trace_started()))
+      {
+        if (pushdown_cond_selectivity < 1.0)
+        {
+          trace_one_table.add("selectivity", pushdown_cond_selectivity);
+          trace_one_table.add("estimated_join_cardinality",
+                              partial_join_cardinality);
+        }
+      }
+
+      if ((search_depth > 1) && (remaining_tables & ~real_table_bit) &
+          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");
-        if (best_extension_by_limited_search(join,
-                                             remaining_tables & ~real_table_bit,
-                                             idx + 1,
-                                             partial_join_cardinality,
-                                             current_read_time,
-                                             search_depth - 1,
-                                             prune_level,
-                                             use_cond_selectivity))
-          DBUG_RETURN(TRUE);
+        best_res=
+          best_extension_by_limited_search(join,
+                                           remaining_tables &
+                                           ~real_table_bit,
+                                           idx + 1,
+                                           partial_join_cardinality,
+                                           current_read_time,
+                                           search_depth - 1,
+                                           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);
+        if (best_res == SEARCH_FOUND_EDGE &&
+            check_if_edge_table(join->positions+ idx,
+                                pushdown_cond_selectivity) !=
+            SEARCH_FOUND_EDGE)
+          best_res= SEARCH_OK;
       }
       else
-      { /*
+      {
+        /*
           'join' is either the best partial QEP with 'search_depth' relations,
           or the best complete QEP so far, whichever is smaller.
         */
@@ -10033,15 +10087,13 @@ best_extension_by_limited_search(JOIN      *join,
             join->positions[join->const_tables].table->table)
         {
           /*
-             We may have to make a temp table, note that this is only a
-             heuristic since we cannot know for sure at this point.
-             Hence it may be wrong.
+            We may have to make a temp table, note that this is only a
+            heuristic since we cannot know for sure at this point.
+            Hence it may be wrong.
           */
           trace_one_table.add("cost_for_sorting", current_record_count);
           current_read_time= COST_ADD(current_read_time, current_record_count);
         }
-        trace_one_table.add("estimated_join_cardinality",
-                            partial_join_cardinality);
         if (current_read_time < join->best_read)
         {
           memcpy((uchar*) join->best_positions, (uchar*) join->positions,
@@ -10054,12 +10106,19 @@ best_extension_by_limited_search(JOIN      *join,
                                        read_time,
                                        current_read_time,
                                        "full_plan"););
+        best_res= check_if_edge_table(join->positions + idx,
+                                      pushdown_cond_selectivity);
       }
       restore_prev_nj_state(s);
       restore_prev_sj_state(remaining_tables, s, idx);
+      if (best_res == SEARCH_FOUND_EDGE)
+      {
+        trace_one_table.add("pruned_by_hanging_leaf", true);
+        DBUG_RETURN(best_res);
+      }
     }
   }
-  DBUG_RETURN(FALSE);
+  DBUG_RETURN(SEARCH_OK);
 }
 
 
diff --git a/sql/sql_select.h b/sql/sql_select.h
index e854792b073..4a2929207a5 100644
--- a/sql/sql_select.h
+++ b/sql/sql_select.h
@@ -989,6 +989,8 @@ public:
   */
   enum sj_strategy_enum sj_strategy;
 
+  /* Type of join (EQ_REF, REF etc) */
+  enum join_type type;
   /*
     Valid only after fix_semijoin_strategies_for_picked_join_order() call:
     if sj_strategy!=SJ_OPT_NONE, this is the number of subsequent tables that