Implementation of WL#1469 (Greedy algorithm to search for an optimal execution plan).

mysql-test/r/subselect.result:
  Table pre-sorting before optimization makes the optimizer select a different plan, this change fixes the plan.
sql/mysql_priv.h:
  Added new status variable last_query_cost that contains the cost of the last compiled query.
sql/mysqld.cc:
  * Added new system variable 'plan_search_depth' to control the exhaustiveness of the search for an optimal query plan.
  * Added new system variable 'heuristic' to control the use of query optimization heuristic.
  * Added new status variable 'last_query_cost' that contains the cost of the last compiled query.
sql/set_var.cc:
  * Added new system variable 'plan_search_depth' to control the exhaustiveness of the search for an optimal query plan.
  * Added new system variable 'heuristic' to control the use of query optimization heuristic.
sql/sql_class.h:
  * Added new system variable 'plan_search_depth' to control the exhaustiveness of the search for an optimal query plan.
  * Added new system variable 'heuristic' to control the use of query optimization heuristic.
sql/sql_select.cc:
  Added a combined greedy/exhaustive query optimization algorithm.
  * The greedy search algorithm is implemented in function 'greedy_search'.
  * The exhaustive search with controlled search depth is implemented in function 'find_best_limited_depth', a modification of 'find_best'.
  * The selection of the best access path and its cost computation is factored out from 'find_best' into function 'best_access_path'.
  * In addition:
    - added pre-sorting for the query tables before they get optimized
    - factored out the optimization of STRAIGHT_JOIN into a separate procedure
sql/sql_select.h:
  Added new field to st_position to support the greedy optimizer.
  Added a comment to class JOIN.
sql/sql_show.cc:
  Added a case to 'mysqld_show' to print double status variables.
sql/structs.h:
  Added a new type of status variables SHOW_DOUBLE
BitKeeper/etc/logging_ok:
  Logging to logging@openlogging.org accepted

1 files changed, 4 insertions, 2 deletions

diff --git a/sql/sql_select.h b/sql/sql_select.h
index e1fc5d1c1fe..e22acf4d186 100644
--- a/sql/sql_select.h
+++ b/sql/sql_select.h
@@ -116,6 +116,7 @@ typedef struct st_join_table {
 typedef struct st_position			/* Used in find_best */
 {
   double records_read;
+  double read_time;
   JOIN_TAB *table;
   KEYUSE *key;
 } POSITION;
@@ -133,8 +134,9 @@ typedef struct st_rollup
 class JOIN :public Sql_alloc
 {
  public:
-  JOIN_TAB *join_tab,**best_ref,**map2table;
-  JOIN_TAB *join_tab_save; //saved join_tab for subquery reexecution
+  JOIN_TAB *join_tab,**best_ref;
+  JOIN_TAB **map2table;    // mapping between table indexes and JOIN_TABs
+  JOIN_TAB *join_tab_save; // saved join_tab for subquery reexecution
   TABLE    **table,**all_tables,*sort_by_table;
   uint	   tables,const_tables;
   uint	   send_group_parts;