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

8 files changed, 910 insertions, 8 deletions

diff --git a/sql/mysql_priv.h b/sql/mysql_priv.h
index e17847ebe24..4b32d012791 100644
--- a/sql/mysql_priv.h
+++ b/sql/mysql_priv.h
@@ -836,6 +836,7 @@ extern char glob_hostname[FN_REFLEN], mysql_home[FN_REFLEN];
 extern char pidfile_name[FN_REFLEN], time_zone[30], *opt_init_file;
 extern char log_error_file[FN_REFLEN];
 extern double log_10[32];
+extern double last_query_cost;
 extern ulonglong keybuff_size;
 extern ulong refresh_version,flush_version, thread_id,query_id,opened_tables;
 extern ulong created_tmp_tables, created_tmp_disk_tables;
diff --git a/sql/mysqld.cc b/sql/mysqld.cc
index 0a05da7491b..43d6528a425 100644
--- a/sql/mysqld.cc
+++ b/sql/mysqld.cc
@@ -311,6 +311,7 @@ ulong my_bind_addr;			/* the address we bind to */
 volatile ulong cached_thread_count= 0;
 
 double log_10[32];			/* 10 potences */
+double last_query_cost= -1; /* -1 denotes that no query was compiled yet */
 
 time_t start_time;
 
@@ -3706,7 +3707,9 @@ enum options_mysqld
   OPT_DATE_FORMAT,
   OPT_TIME_FORMAT,
   OPT_DATETIME_FORMAT,
-  OPT_LOG_QUERIES_NOT_USING_INDEXES
+  OPT_LOG_QUERIES_NOT_USING_INDEXES,
+  OPT_PLAN_SEARCH_DEPTH,
+  OPT_HEURISTIC
 };
 
 
@@ -4308,6 +4311,11 @@ log and this option does nothing anymore.",
     "Use stopwords from this file instead of built-in list.",
     (gptr*) &ft_stopword_file, (gptr*) &ft_stopword_file, 0, GET_STR,
     REQUIRED_ARG, 0, 0, 0, 0, 0, 0},
+  {"heuristic", OPT_HEURISTIC,
+   "Controls the heuristic(s) applied during query optimization to prune less-promising partial plans from the optimizer search space. Meaning: 0 - do not apply any heuristic, thus perform exhaustive search; 1 - prune plans based on rows and read time.",
+   (gptr*) &global_system_variables.heuristic,
+   (gptr*) &max_system_variables.heuristic,
+   0, GET_ULONG, OPT_ARG, 1, 0, 1, 0, 1, 0},
 #ifdef HAVE_INNOBASE_DB
   {"innodb_mirrored_log_groups", OPT_INNODB_MIRRORED_LOG_GROUPS,
    "Number of identical copies of log groups we keep for the database. Currently this should be set to 1.",
@@ -4542,6 +4550,11 @@ The minimum value for this variable is 4096.",
    "If this is not 0, then mysqld will use this value to reserve file descriptors to use with setrlimit(). If this value is 0 then mysqld will reserve max_connections*5 or max_connections + table_cache*2 (whichever is larger) number of files.",
    (gptr*) &open_files_limit, (gptr*) &open_files_limit, 0, GET_ULONG,
    REQUIRED_ARG, 0, 0, 65535, 0, 1, 0},
+  {"plan_search_depth", OPT_PLAN_SEARCH_DEPTH,
+   "Maximum depth of search performed by the query optimizer. Values larger than the number of relations in a query result in better query plans, but take longer to compile a query. Smaller values than the number of tables in a relation result in faster optimization, but may produce very bad query plans. If set to 0, the system will automatically pick a reasonable value; if set to MAX_TABLES+2, the optimizer will switch to the original find_best (used for testing/comparison).",
+   (gptr*) &global_system_variables.plan_search_depth,
+   (gptr*) &max_system_variables.plan_search_depth,
+   0, GET_ULONG, OPT_ARG, MAX_TABLES+1, 0, MAX_TABLES+2, 0, 1, 0},
    {"preload_buffer_size", OPT_PRELOAD_BUFFER_SIZE,
     "The size of the buffer that is allocated when preloading indexes",
     (gptr*) &global_system_variables.preload_buff_size,
@@ -4887,6 +4900,7 @@ struct show_var_st status_vars[]= {
   {"Threads_connected",        (char*) &thread_count,           SHOW_INT_CONST},
   {"Threads_running",          (char*) &thread_running,         SHOW_INT_CONST},
   {"Uptime",                   (char*) 0,                       SHOW_STARTTIME},
+  {"Last_query_cost",          (char*) &last_query_cost,        SHOW_DOUBLE},
   {NullS, NullS, SHOW_LONG}
 };
 
diff --git a/sql/set_var.cc b/sql/set_var.cc
index b74bf3e5f7b..9c8e17a6fde 100644
--- a/sql/set_var.cc
+++ b/sql/set_var.cc
@@ -149,6 +149,7 @@ sys_var_long_ptr	sys_expire_logs_days("expire_logs_days",
 					     &expire_logs_days);
 sys_var_bool_ptr	sys_flush("flush", &myisam_flush);
 sys_var_long_ptr	sys_flush_time("flush_time", &flush_time);
+sys_var_thd_ulong       sys_heuristic("heuristic", &SV::heuristic);
 sys_var_thd_ulong	sys_interactive_timeout("interactive_timeout",
 						&SV::net_interactive_timeout);
 sys_var_thd_ulong	sys_join_buffer_size("join_buffer_size",
@@ -241,6 +242,8 @@ sys_var_thd_ulong	sys_net_retry_count("net_retry_count",
 					    fix_net_retry_count);
 sys_var_thd_bool	sys_new_mode("new", &SV::new_mode);
 sys_var_thd_bool	sys_old_passwords("old_passwords", &SV::old_passwords);
+sys_var_thd_ulong       sys_plan_search_depth("plan_search_depth",
+                                              &SV::plan_search_depth);
 sys_var_thd_ulong       sys_preload_buff_size("preload_buffer_size",
                                               &SV::preload_buff_size);
 sys_var_thd_ulong	sys_read_buff_size("read_buffer_size",
@@ -447,6 +450,7 @@ sys_var *sys_variables[]=
   &sys_flush_time,
   &sys_foreign_key_checks,
   &sys_group_concat_max_len,
+  &sys_heuristic,
   &sys_identity,
   &sys_init_connect,
   &sys_init_slave,
@@ -492,6 +496,7 @@ sys_var *sys_variables[]=
   &sys_net_write_timeout,
   &sys_new_mode,
   &sys_old_passwords,
+  &sys_plan_search_depth,
   &sys_preload_buff_size,
   &sys_pseudo_thread_id,
   &sys_query_alloc_block_size,
@@ -760,6 +765,8 @@ struct show_var_st init_vars[]= {
   {"version_compile_machine", (char*) MACHINE_TYPE,		    SHOW_CHAR},
   {"version_compile_os",      (char*) SYSTEM_TYPE,		    SHOW_CHAR},
   {sys_net_wait_timeout.name, (char*) &sys_net_wait_timeout,	    SHOW_SYS},
+  {sys_heuristic.name,        (char*) &sys_heuristic,               SHOW_SYS},
+  {sys_plan_search_depth.name,(char*) &sys_plan_search_depth,       SHOW_SYS},
   {NullS, NullS, SHOW_LONG}
 };
 
diff --git a/sql/sql_class.h b/sql/sql_class.h
index b7ef30b4e79..1aa2a74fd17 100644
--- a/sql/sql_class.h
+++ b/sql/sql_class.h
@@ -390,6 +390,8 @@ struct system_variables
   ulong table_type;
   ulong tmp_table_size;
   ulong tx_isolation;
+  ulong heuristic;
+  ulong plan_search_depth;
   /* Determines which non-standard SQL behaviour should be enabled */
   ulong sql_mode;
   ulong default_week_format;
diff --git a/sql/sql_select.cc b/sql/sql_select.cc
index 8ee0601eb79..dad0d9553ea 100644
--- a/sql/sql_select.cc
+++ b/sql/sql_select.cc
@@ -49,6 +49,24 @@ static void set_position(JOIN *join,uint index,JOIN_TAB *table,KEYUSE *key);
 static bool create_ref_for_key(JOIN *join, JOIN_TAB *j, KEYUSE *org_keyuse,
 			       table_map used_tables);
 static void find_best_combination(JOIN *join,table_map rest_tables);
+
+static void best_access_path(JOIN *join, JOIN_TAB *s, THD *thd,
+                             table_map rest_tables, uint idx,
+                             double record_count, double read_time);
+static void optimize_straight_join(JOIN *join, table_map rest_tables);
+static void greedy_search(JOIN *join, table_map rest_tables,
+                             uint depth, uint heuristic);
+static void find_best_limited_depth(JOIN *join, table_map rest_tables, uint idx,
+                                    double record_count, double read_time,
+                                    uint depth, uint heuristic);
+static uint determine_search_depth(JOIN* join);
+static int join_tab_cmp(const void* ptr1, const void* ptr2);
+static void print_plan(JOIN* join, double read_time, double record_count,
+                       uint idx, const char *info);
+/*
+  TODO: 'find_best' is here only temporarily until 'greedy_search' is
+  tested and approved.
+*/
 static void find_best(JOIN *join,table_map rest_tables,uint index,
 		      double record_count,double read_time);
 static uint cache_record_length(JOIN *join,uint index);
@@ -2621,16 +2639,869 @@ set_position(JOIN *join,uint idx,JOIN_TAB *table,KEYUSE *key)
 }
 
 
+/*
+  Find the best access path (e.g. indexes) from table 's' to the tables in the
+  partial QEP 'join', and compute the cost of the new QEP that includes 's'.
+
+  SYNOPSIS
+    best_access_path()
+    join         Valid partial QEP.
+    s            Table access plan from join->best_ref being added to join.
+    rest_tables  A bit-map where a bit is set for each table accessed in 'join'.
+    idx          Index into 'join->positions' that points to the next undecided
+                 table access plan in 'join->positions' ('s' in this case).
+                 Thus: (idx == join->tables - card(rest_tables) - 1)
+    record_count The number of records acessed by the partial QEP 'join'.
+    read_time    Time needed to execute 'join'.
+
+  MODIFIES
+    join->positions The best access path from 's' to 'join' and the
+                    corresponding cost are stored in 'join->positions'.
+*/
+
 static void
-find_best_combination(JOIN *join, table_map rest_tables)
+best_access_path(JOIN      *join,             // in/out
+                 JOIN_TAB  *s,                // in
+                 THD       *thd,              // in
+                 table_map rest_tables,       // in
+                 uint      idx,               // in
+                 double    record_count,      // in
+                 double    read_time)         // in
+{
+  KEYUSE *best_key=         0;
+  uint best_max_key_part=   0;
+  my_bool found_constraint= 0;
+  double best=              DBL_MAX;
+  double best_time=         DBL_MAX;
+  double records=           DBL_MAX;
+  double tmp;
+  ha_rows rec;
+
+  DBUG_ENTER("best_access_path");
+
+  if (s->keyuse)
+  {						/* Use key if possible */
+    TABLE *table= s->table;
+    KEYUSE *keyuse,*start_key=0;
+    double best_records= DBL_MAX;
+    uint max_key_part=0;
+
+    /* Test how we can use keys */
+    rec= s->records/MATCHING_ROWS_IN_OTHER_TABLE;  // Assumed records/key
+    for (keyuse=s->keyuse ; keyuse->table == table ;)
+    {
+      key_part_map found_part= 0;
+      table_map found_ref=     0;
+      uint found_ref_or_null=  0;
+      uint key=     keyuse->key;
+      KEY *keyinfo= table->key_info+key;
+      bool ft_key=  (keyuse->keypart == FT_KEYPART);
+
+      /* Calculate how many key segments of the current key we can use */
+      start_key= keyuse;
+      do
+      { /* for each keypart */
+        uint keypart= keyuse->keypart;
+        uint found_part_ref_or_null= KEY_OPTIMIZE_REF_OR_NULL;
+        do
+        {
+          if (!(rest_tables & keyuse->used_tables) &&
+              !(found_ref_or_null & keyuse->optimize))
+          {
+            found_part|= keyuse->keypart_map;
+            found_ref|=  keyuse->used_tables;
+            if (rec > keyuse->ref_table_rows)
+              rec= keyuse->ref_table_rows;
+            found_part_ref_or_null&= keyuse->optimize;
+          }
+          keyuse++;
+          found_ref_or_null|= found_part_ref_or_null;
+        } while (keyuse->table == table && keyuse->key == key &&
+                 keyuse->keypart == keypart);
+      } while (keyuse->table == table && keyuse->key == key);
+
+      /*
+        Assume that that each key matches a proportional part of table.
+      */
+      if (!found_part && !ft_key)
+        continue;				// Nothing usable found
+
+      if (rec < MATCHING_ROWS_IN_OTHER_TABLE)
+        rec= MATCHING_ROWS_IN_OTHER_TABLE;	// Fix for small tables
+
+      /*
+        ft-keys require special treatment
+      */
+      if (ft_key)
+      {
+        /*
+          Really, there should be records=0.0 (yes!)
+          but 1.0 would be probably safer
+        */
+        tmp= prev_record_reads(join, found_ref);
+        records= 1.0;
+      }
+      else
+      {
+        found_constraint= 1;
+        /*
+          Check if we found full key
+        */
+        if (found_part == PREV_BITS(uint,keyinfo->key_parts) &&
+            !found_ref_or_null)
+        {				/* use eq key */
+          max_key_part= (uint) ~0;
+          if ((keyinfo->flags & (HA_NOSAME | HA_NULL_PART_KEY)) == HA_NOSAME)
+          {
+            tmp = prev_record_reads(join, found_ref);
+            records=1.0;
+          }
+          else
+          {
+            if (!found_ref)
+            {					// We found a const key
+              if (table->quick_keys.is_set(key))
+                records= (double) table->quick_rows[key];
+              else
+              {
+                /* quick_range couldn't use key! */
+                records= (double) s->records/rec;
+              }
+            }
+            else
+            {
+              if (!(records=keyinfo->rec_per_key[keyinfo->key_parts-1]))
+              {				// Prefere longer keys
+                records=
+                  ((double) s->records / (double) rec *
+                   (1.0 +
+                    ((double) (table->max_key_length-keyinfo->key_length) /
+                     (double) table->max_key_length)));
+                if (records < 2.0)
+                  records=2.0;		// Can't be as good as a unique
+              }
+            }
+            /* Limit the number of matched rows */
+            tmp = records;
+            set_if_smaller(tmp, (double) thd->variables.max_seeks_for_key);
+            if (table->used_keys.is_set(key))
+            {
+              /* we can use only index tree */
+              uint keys_per_block= table->file->block_size/2/
+                (keyinfo->key_length+table->file->ref_length)+1;
+              tmp = record_count*(tmp+keys_per_block-1)/keys_per_block;
+            }
+            else
+              tmp = record_count*min(tmp,s->worst_seeks);
+          }
+        }
+        else
+        {
+          /*
+            Use as much key-parts as possible and a uniq key is better
+            than a not unique key
+            Set tmp to (previous record count) * (records / combination)
+          */
+          if ((found_part & 1) &&
+              (!(table->file->index_flags(key) & HA_ONLY_WHOLE_INDEX) ||
+               found_part == PREV_BITS(uint,keyinfo->key_parts)))
+          {
+            max_key_part=max_part_bit(found_part);
+            /*
+              Check if quick_range could determinate how many rows we
+              will match
+            */
+            if (table->quick_keys.is_set(key) &&
+                table->quick_key_parts[key] <= max_key_part)
+              tmp = records = (double) table->quick_rows[key];
+            else
+            {
+              /* Check if we have statistic about the distribution */
+              if ((records = keyinfo->rec_per_key[max_key_part-1]))
+                tmp = records;
+              else
+              {
+                /*
+                  Assume that the first key part matches 1% of the file
+                  and that the hole key matches 10 (duplicates) or 1
+                  (unique) records.
+                  Assume also that more key matches proportionally more
+                  records
+                  This gives the formula:
+                  records = (x * (b-a) + a*c-b)/(c-1)
+
+                  b = records matched by whole key
+                  a = records matched by first key part (10% of all records?)
+                  c = number of key parts in key
+                  x = used key parts (1 <= x <= c)
+                */
+                double rec_per_key;
+                if (!(rec_per_key=(double)
+                      keyinfo->rec_per_key[keyinfo->key_parts-1]))
+                  rec_per_key=(double) s->records/rec+1;
+
+                if (!s->records)
+                  tmp = 0;
+                else if (rec_per_key/(double) s->records >= 0.01)
+                  tmp = rec_per_key;
+                else
+                {
+                  double a=s->records*0.01;
+                  tmp = (max_key_part * (rec_per_key - a) +
+                         a*keyinfo->key_parts - rec_per_key)/
+                    (keyinfo->key_parts-1);
+                  set_if_bigger(tmp,1.0);
+                }
+                records = (ulong) tmp;
+              }
+              if (found_ref_or_null)
+              {
+                /* We need to do two key searches to find key */
+                tmp *= 2.0;
+                records *= 2.0;
+              }
+            }
+            /* Limit the number of matched rows */
+            set_if_smaller(tmp, (double) thd->variables.max_seeks_for_key);
+            if (table->used_keys.is_set(key))
+            {
+              /* we can use only index tree */
+              uint keys_per_block= table->file->block_size/2/
+                (keyinfo->key_length+table->file->ref_length)+1;
+              tmp = record_count*(tmp+keys_per_block-1)/keys_per_block;
+            }
+            else
+              tmp = record_count*min(tmp,s->worst_seeks);
+          }
+          else
+            tmp = best_time;			// Do nothing
+        }
+      } /* not ft_key */
+      if (tmp < best_time - records/(double) TIME_FOR_COMPARE)
+      {
+        best_time= tmp + records/(double) TIME_FOR_COMPARE;
+        best= tmp;
+        best_records= records;
+        best_key= start_key;
+        best_max_key_part= max_key_part;
+      }
+    }
+    records= best_records;
+  }
+
+  /*
+    Don't test table scan if it can't be better.
+    Prefer key lookup if we would use the same key for scanning.
+
+    Don't do a table scan on InnoDB tables, if we can read the used
+    parts of the row from any of the used index.
+    This is because table scans uses index and we would not win
+    anything by using a table scan.
+  */
+  if ((records >= s->found_records || best > s->read_time) &&
+      !(s->quick && best_key && s->quick->index == best_key->key &&
+        best_max_key_part >= s->table->quick_key_parts[best_key->key]) &&
+      !((s->table->file->table_flags() & HA_TABLE_SCAN_ON_INDEX) &&
+        ! s->table->used_keys.is_clear_all() && best_key) &&
+      !(s->table->force_index && best_key))
+  {						// Check full join
+    ha_rows rnd_records= s->found_records;
+    /*
+      If there is a restriction on the table, assume that 25% of the
+      rows can be skipped on next part.
+      This is to force tables that this table depends on before this
+      table
+    */
+    if (found_constraint)
+      rnd_records-= rnd_records/4;
+
+    /*
+      Range optimizer never proposes a RANGE if it isn't better
+      than FULL: so if RANGE is present, it's always preferred to FULL.
+      Here we estimate its cost.
+    */
+    if (s->quick)
+    {
+      /*
+        For each record we:
+        - read record range through 'quick'
+        - skip rows which does not satisfy WHERE constraints
+      */
+      tmp= record_count *
+        (s->quick->read_time +
+         (s->found_records - rnd_records)/(double) TIME_FOR_COMPARE);
+    }
+    else
+    {
+      /* Estimate cost of reading table. */
+      tmp= s->table->file->scan_time();
+      if (s->on_expr)                         // Can't use join cache
+      {
+        /*
+          For each record we have to:
+          - read the whole table record 
+          - skip rows which does not satisfy join condition
+        */
+        tmp= record_count *
+          (tmp +
+           (s->records - rnd_records)/(double) TIME_FOR_COMPARE);
+      }
+      else
+      {
+        /* We read the table as many times as join buffer becomes full. */
+        tmp*= (1.0 + floor((double) cache_record_length(join,idx) *
+                           record_count /
+                           (double) thd->variables.join_buff_size));
+        /* 
+            We don't make full cartesian product between rows in the scanned
+           table and existing records because we skip all rows from the
+           scanned table, which does not satisfy join condition when 
+           we read the table (see flush_cached_records for details). Here we
+           take into account cost to read and skip these records.
+        */
+        tmp+= (s->records - rnd_records)/(double) TIME_FOR_COMPARE;
+      }
+    }
+
+    /*
+      We estimate the cost of evaluating WHERE clause for found records
+      as record_count * rnd_records / TIME_FOR_COMPARE. This cost plus
+      tmp give us total cost of using TABLE SCAN
+    */
+    if (best == DBL_MAX ||
+        (tmp  + record_count/(double) TIME_FOR_COMPARE*rnd_records <
+         best + record_count/(double) TIME_FOR_COMPARE*records))
+    {
+      /*
+        If the table has a range (s->quick is set) make_join_select()
+        will ensure that this will be used
+      */
+      best= tmp;
+      records= rows2double(rnd_records);
+      best_key= 0;
+    }
+  }
+
+  /* Update the cost information for the current partial plan */
+  join->positions[idx].records_read= records;
+  join->positions[idx].read_time=    best;
+  join->positions[idx].key=          best_key;
+  join->positions[idx].table=        s;
+
+  if (!best_key &&
+      idx == join->const_tables &&
+      s->table == join->sort_by_table &&
+      join->unit->select_limit_cnt >= records)
+    join->sort_by_table= (TABLE*) 1;	// Must use temporary table
+
+  DBUG_VOID_RETURN;
+}
+
+
+/*
+  Entry point to the MySQL optimizer. Selects a query optimzation method,
+  sets-up initial parameters and calls the actual optimization procedure.
+
+  SYNOPSIS
+    join        An unoptimized QEP.
+    rest_tables A bit-map where a bit is set for each table accessed in 'join'.
+
+  MODIFIES
+    join->best_positions Stores the final optimal plan.
+    join->best_read      Stores the corresponding cost of the optimal plan.
+    Depending on the optimization algorithm used, may modify other memebers
+    of 'join'.
+*/
+
+static void
+find_best_combination(JOIN *join /*in/out*/, table_map rest_tables /*in*/)
 {
+  uint search_depth= join->thd->variables.plan_search_depth;
+  uint heuristic=    join->thd->variables.heuristic;
+
   DBUG_ENTER("find_best_combination");
-  join->best_read=DBL_MAX;
-  find_best(join,rest_tables, join->const_tables,1.0,0.0);
+
+  if (join->select_options & SELECT_STRAIGHT_JOIN)
+  {
+    optimize_straight_join(join, rest_tables);
+  }
+  else
+  {
+    /*
+      Heuristic: pre-sort all access plans with respect to the number of records
+      accessed.
+    qsort(join->best_ref + join->const_tables, join->tables - join->const_tables,
+          sizeof(JOIN_TAB*), join_tab_cmp);
+    */
+
+    if (search_depth == MAX_TABLES+2)
+    { /*
+        TODO: 'MAX_TABLES+2' denotes the old implementation of find_best before
+        the greedy version. Will be removed when greedy_search is approved.
+      */
+      join->best_read= DBL_MAX;
+      find_best(join,rest_tables, join->const_tables, 1.0, 0.0);
+    } 
+    else
+    {
+      if (search_depth == 0)
+        /* Automatically determine a reasonable value for 'search_depth' */
+        search_depth= determine_search_depth(join);
+      greedy_search(join, rest_tables, search_depth, heuristic);
+    }
+  }
+
+  /* Store the cost of this query into a user variable */
+  last_query_cost= join->best_read;
+
   DBUG_VOID_RETURN;
 }
 
 
+/*
+  Compare two JOIN_TAB objects based on the number of records accessed
+  so that they can be sorted by qsort.
+
+  RETURN
+    1 if first is bigger
+   -1 if second is bigger
+    0 if equal
+*/
+
+static int
+join_tab_cmp(const void* ptr1, const void* ptr2)
+{
+  JOIN_TAB *jt1= *(JOIN_TAB**) ptr1;
+  JOIN_TAB *jt2= *(JOIN_TAB**) ptr2;
+  if (jt1->found_records > jt2->found_records)
+    return 1;
+  else if (jt1->found_records < jt2->found_records)
+    return -1;
+  else
+    return 0;
+}
+
+
+/*
+  Heuristic procedure to automatically guess the degree of exhaustiveness of the
+  'greedy_search' procedure. The goal of this procedure is to predict the
+  optimization time and to select a search depth big enough to result in a
+  near-otimal QEP, that doesn't take too long to find.
+
+  SYNOPSIS
+    determine_search_depth()
+    join  An unoptimized or partially optimized QEP.
+
+  NOTES
+    This is an extremely simplistic implementation that serves as a stub for a
+    more advanced analysis of the join. Ideally the search depth should be
+    determined by learning from old compilations, because it will depend on the
+    CPU power (and other factors).
+
+  RETURN
+    A positive integer that specifies the search depth (and thus the
+    exhaustiveness) of the depth-first search algorithm used by 'greedy_search'.
+*/
+
+static uint
+determine_search_depth(JOIN *join /*in*/)
+{
+  uint table_count=  join->tables - join->const_tables;
+  uint search_depth;
+  /* TODO: this value should be determined dynamically, based on statistics: */
+  uint max_tables_for_exhaustive_opt= 7;
+
+  if (table_count <= max_tables_for_exhaustive_opt)
+    search_depth= table_count+1; // use exhaustive for small number of tables
+  else
+    /*
+      TODO: this value could be determined by some mapping of the form:
+      depth : table_count -> [max_tables_for_exhaustive_opt..MAX_EXHAUSTIVE]
+    */
+    search_depth= max_tables_for_exhaustive_opt; // use greedy search
+
+  return search_depth;
+}
+
+
+/*
+  Find the best access paths for each query relation and their costs without
+  reordering the table access plans in a join.
+  This function can be applied to:
+  - queries with STRAIGHT_JOIN
+  - internally to compute the cost of an arbitrary QEP, thus 'optimize_straight_join'
+    can be used at any stage of the query optimization process to finalize a QEP as
+    it is.
+*/
+
+static void
+optimize_straight_join(JOIN *join /*in/out*/, table_map rest_tables /*in*/)
+{
+  JOIN_TAB *s;
+  uint idx= join->const_tables;
+  double    record_count= 1.0;
+  double    read_time=    0.0;
+
+  for (JOIN_TAB **pos= join->best_ref + idx ; (s= *pos) ; pos++)
+  {
+    /* Find the best access method from 's' to the current partial plan */
+    best_access_path(join, s, join->thd, rest_tables, idx, record_count, read_time);
+    /* compute the cost of the new plan extended with 's' */
+    record_count*= join->positions[idx].records_read;
+    read_time+=    join->positions[idx].read_time;
+    rest_tables&= ~(s->table->map);
+    ++idx;
+  }
+
+  read_time+= record_count / (double) TIME_FOR_COMPARE;
+  if (join->sort_by_table &&
+      join->sort_by_table != join->positions[join->const_tables].table->table)
+    read_time+= record_count;			// We have to make a temp table
+  memcpy((gptr) join->best_positions, (gptr) join->positions,
+         sizeof(POSITION)*idx);
+  join->best_read= read_time;
+}
+
+/*
+  Find a good (possibly optimal) query evaluation plan (QEP) for the table
+  access plans stored in 'join->best_ref'.
+
+  SYNOPSIS
+    join         An unoptimized QEP.
+    rest_tables  A bitmap where a bit is set for each corresponding table number.
+    search_depth Controlls the depth of the search. The higher the value, the
+                 longer optimizaton time and possibly the better the resulting
+                 plan. The lower the value, the fewer alternative plans are
+                 estimated, but the more likely to get a bad QEP.
+                 (0 < search_depth)
+    heuristic    Specifies the pruning heuristics that should be applied during
+                 optimization. Values: 0 = EXHAUSTIVE, 1 = PRUNE_BY_TIME_OR_ROWS.
+
+  DESCRIPTION
+    The search procedure uses a hybrid greedy/exhaustive search with controlled
+    exhaustiveness. The search is performed in N = card(rest_tables) steps.
+    Each step uses a procedure to estimate how promising is each of the
+    unoptimized tables, selects the most promising table, and extends the
+    current partial QEP with that table.
+    Currently this estimate is performed by calling 'find_best_limited_depth'
+    to evaluate all extensions of the current QEP with size 'search_depth'.
+    The most 'promising' table is the one with least expensive extension.
+    There are two extreme cases:
+    1. When (card(rest_tables) < search_depth), the estimate finds the best
+       complete continuation of the partial QEP. This continuation can be
+       used directly as a result of the search.
+    2. When (search_depth == 1) the 'find_best_limited_depth' consideres the
+       extension of the current QEP with each of the remaining unoptimized
+       tables.
+    All other cases are in-between these two extremes. Thus the parameter
+    'search_depth' controlls the exhaustiveness of the search.
+
+  MODIFIES
+    Intermediate and final results of the procedure are stored in 'join':
+    join->positions      modified for every partial QEP that is explored
+    join->best_positions modified for the current best complete QEP
+    join->best_read      modified for the current best complete QEP
+    join->best_ref       might be partially reordered
+    The final optimal plan is stored in 'join->best_positions'. The
+    corresponding cost of the optimal plan is in 'join->best_read'.
+*/
+
+static void
+greedy_search(JOIN      *join,        // in/out
+                 table_map rest_tables,  // in
+                 uint      search_depth, // in
+                 uint      heuristic)    // in
+{
+  double    record_count= 1.0;
+  double    read_time=    0.0;
+  uint      idx= join->const_tables; // index into 'join->best_ref'
+  uint      best_idx;
+  uint      rest_size;   // cardinality of rest_tables
+  POSITION  best_pos;
+  JOIN_TAB  *best_table; // the next plan node to be added to the curr QEP
+
+  DBUG_ENTER("greedy_search");
+
+  /* number of tables that remain to be optimized */
+  rest_size= my_count_bits(rest_tables);
+
+  do {
+    /* Find the extension of the current QEP with the lowest cost */
+    join->best_read= DBL_MAX;
+    find_best_limited_depth(join, rest_tables, idx, record_count, read_time,
+                            search_depth, heuristic);
+
+    if (rest_size <= search_depth)
+    {
+    /*
+      'join->best_positions' contains a complete optimal extension of the
+      current partial QEP.
+    */
+      DBUG_EXECUTE("opt", print_plan(join, read_time, record_count,
+				     join->tables, "optimal"););
+      DBUG_VOID_RETURN;
+    }
+
+    /* select the first table in the optimal extension as most promising */
+    best_pos= join->best_positions[idx];
+    best_table= best_pos.table;
+    /*
+      Each subsequent loop of 'find_best_limited_depth' uses 'join->positions'
+      for cost estimates, therefore we have to update its value.
+    */
+    join->positions[idx]= best_pos;
+
+    /* find the position of 'best_table' in 'join->best_ref' */
+    best_idx= idx;
+    JOIN_TAB *pos= join->best_ref[best_idx];
+    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(JOIN_TAB*, join->best_ref[idx], join->best_ref[best_idx]);
+
+    /* compute the cost of the new plan extended with 'best_table' */
+    record_count*= join->positions[idx].records_read;
+    read_time+=    join->positions[idx].read_time;
+
+    rest_tables&= ~(best_table->table->map);
+    --rest_size;
+    ++idx;
+
+    DBUG_EXECUTE("opt",
+                 print_plan(join, read_time, record_count, idx, "extended"););
+  } while (TRUE);
+}
+
+
+/*
+  Find an optimal ordering of the table access plans in 'join->best_ref' for
+  the tables contained in 'rest_tables'.
+
+  SYNOPSIS
+    join        Valid partial QEP. When 'find_best_limited_depth' is called for
+                the first time, 'join->best_read' must be set to the largest
+                possible value (e.g. DBL_MAX).
+    rest_tables A bit-map where a bit is set for each table accessed in 'join'.
+    idx         - length of the partial QEP 'join->positions',
+                - since a depth-first search is used, also corresponds to the
+                  current depth of the search tree,
+                - also an index in the array 'join->best_ref'.
+    record_count The current best number of records.
+                 (record_count >= 0)
+    read_time    The current best execution time.
+                 (read_time >= 0)
+    search_depth The maximum depth of the recursion and thus the size of the
+                 found optimal plan.
+                 (0 < search_depth <= join->tables+1)
+    heuristic    Specifies the pruning heuristics that should be applied during
+                 optimization. Values: 0 = EXHAUSTIVE, 1 = PRUNE_BY_TIME_OR_ROWS.
+
+  DESCRIPTION
+    The procedure uses a recursive depth-first search that may optionally use
+    pruning heuristics to reduce the search space. Each recursive step adds one
+    more table to the input partial QEP 'join'. The parameter 'search_depth'
+    provides control over the recursion depth, and thus the size of the
+    resulting optimal plan.
+
+  MODIFIES
+    Intermediate and final results of the procedure are stored in 'join':
+    join->positions      modified for every partial QEP that is explored
+    join->best_positions modified for the current best complete QEP
+    join->best_read      modified for the current best complete QEP
+    The final optimal plan is stored in 'join->best_positions'. The
+    corresponding cost of the optimal plan is in 'join->best_read'.
+*/
+
+static void
+find_best_limited_depth(JOIN      *join,        // in/out
+                        table_map rest_tables,  // in
+                        uint      idx,          // in
+                        double    record_count, // in
+                        double    read_time,    // in
+                        uint      search_depth, // in
+                        uint      heuristic)    // in
+{
+  THD *thd= join->thd;
+
+  DBUG_ENTER("find_best_limited_depth");
+
+  /*
+    'join' is either the best partial QEP with 'search_depth' relations,
+    or the best complete QEP so far, whichever is smaller.
+  */
+  if ((search_depth == 0) || !rest_tables)
+  {
+    read_time+= record_count / (double) TIME_FOR_COMPARE;
+    if (join->sort_by_table &&
+	join->sort_by_table != join->positions[join->const_tables].table->table)
+      read_time+= record_count;			// We have to make a temp table
+    if ((search_depth == 0) || (read_time < join->best_read))
+    {
+      memcpy((gptr) join->best_positions, (gptr) join->positions,
+	     sizeof(POSITION)*idx);
+      join->best_read= read_time;
+    }
+    DBUG_EXECUTE("opt",
+		 print_plan(join, read_time, record_count, idx, "full_plan"););
+    DBUG_VOID_RETURN;
+  }
+
+  /* 
+     'join' is a partial plan with lower cost than the best plan so far,
+     so continue expanding it further with the tables in 'rest_tables'.
+  */
+  JOIN_TAB *s;
+  double best_record_count= DBL_MAX;
+  double best_read_time=    DBL_MAX;
+
+  DBUG_EXECUTE("opt",
+	       print_plan(join, read_time, record_count, idx, "part_plan"););
+
+  for (JOIN_TAB **pos= join->best_ref + idx ; (s= *pos) ; pos++)
+  {
+    table_map real_table_bit= s->table->map;
+    if ((rest_tables & real_table_bit) && !(rest_tables & s->dependent))
+    {
+      double current_record_count, current_read_time;
+
+      /* Find the best access method from 's' to the current partial plan */
+      best_access_path(join, s, thd, rest_tables, idx, record_count, read_time);
+      /* Compute the cost of extending the plan with 's' */
+      current_record_count= record_count * join->positions[idx].records_read;
+      current_read_time=    read_time + join->positions[idx].read_time;
+
+      /* Expand only partial plans with lower cost than the best QEP so far */
+      if ((current_read_time +
+           current_record_count / (double) TIME_FOR_COMPARE) >= join->best_read)
+      {
+        DBUG_EXECUTE("opt", print_plan(join, read_time, record_count, idx,
+                                       "prune_by_cost"););
+        continue;
+      }
+
+      /*
+        Prune some less promising partial plans. This heuristic may miss
+        the optimal QEPs, thus it results in a non-exhaustive search.
+      */
+      if (heuristic == 1)
+      {
+        if (best_record_count > current_record_count ||
+            best_read_time > current_read_time ||
+            idx == join->const_tables &&  // 's' is the first table in the QEP
+            s->table == join->sort_by_table)
+        {
+          if (best_record_count >= current_record_count &&
+              best_read_time >= current_read_time &&
+              /* TODO: What is the reasoning behind this condition? */
+              (!(s->key_dependent & rest_tables) ||
+               join->positions[idx].records_read < 2.0))
+          {
+            best_record_count= current_record_count;
+            best_read_time=    current_read_time;
+          }
+        }
+        else
+        {
+          DBUG_EXECUTE("opt", print_plan(join, read_time, record_count, idx,
+                                         "prune_by_heuristic"););
+          continue;
+        }
+      }
+
+      /* Recursively expand the current partial plan */
+      swap(JOIN_TAB*, join->best_ref[idx], *pos);
+      find_best_limited_depth(join, rest_tables & ~real_table_bit, idx+1,
+                              current_record_count, current_read_time,
+                              search_depth-1, heuristic);
+      if (thd->killed)
+        DBUG_VOID_RETURN;
+      swap(JOIN_TAB*, join->best_ref[idx], *pos);
+    }
+  }
+  DBUG_VOID_RETURN;
+}
+
+
+
+/*
+  Print the current state of a 'join' that changes during query optimization.
+  Used to trace the 'find_best_xxx' optimizer functions.
+  TODO: move to sql_test.cc?
+*/
+void
+print_plan(JOIN* join, double read_time, double record_count,
+           uint idx, const char *info)
+{
+  uint i;
+  POSITION pos;
+  JOIN_TAB *join_table;
+  JOIN_TAB **plan_nodes;
+  TABLE*   table;
+
+  DBUG_LOCK_FILE;
+  if (join->best_read == DBL_MAX)
+  {
+    fprintf(DBUG_FILE,"%s; idx:%u, best: DBL_MAX, current:%g\n",
+            info, idx, read_time);
+  }
+  else
+  {
+    fprintf(DBUG_FILE,"%s; idx: %u, best: %g, current: %g\n",
+            info, idx, join->best_read, read_time);
+  }
+
+  /* Print the tables in JOIN->positions */
+  fputs("     POSITIONS: ", DBUG_FILE);
+  for (i= 0; i < idx ; i++)
+  {
+    pos = join->positions[i];
+    table= pos.table->table;
+    if (table)
+      fputs(table->real_name, DBUG_FILE);
+    fputc(' ', DBUG_FILE);
+  }
+  fputc('\n', DBUG_FILE);
+
+  /*
+    Print the tables in JOIN->best_positions only if at least one complete plan
+    has been found. An indicator for this is the value of 'join->best_read'.
+  */
+  fputs("BEST_POSITIONS: ", DBUG_FILE);
+  if (join->best_read < DBL_MAX)
+  {
+    for (i= 0; i < idx ; i++)
+    {
+      pos= join->best_positions[i];
+      table= pos.table->table;
+      if (table)
+        fputs(table->real_name, DBUG_FILE);
+      fputc(' ', DBUG_FILE);
+    }
+  }
+  fputc('\n', DBUG_FILE);
+
+  /* Print the tables in JOIN->best_ref */
+  fputs("      BEST_REF: ", DBUG_FILE);
+  for (plan_nodes= join->best_ref ; *plan_nodes ; plan_nodes++)
+  {
+    join_table= (*plan_nodes);
+    fputs(join_table->table->real_name, DBUG_FILE);
+    fprintf(DBUG_FILE, "(%u,%u,%u)",
+            join_table->found_records, join_table->records, join_table->read_time);
+    fputc(' ', DBUG_FILE);
+  }
+  fputc('\n', DBUG_FILE);
+
+  DBUG_UNLOCK_FILE;
+}
+
+
+
+/*
+  TODO: this function is here only temporarily until 'greedy_search' is
+  tested and accepted.
+*/
 static void
 find_best(JOIN *join,table_map rest_tables,uint idx,double record_count,
 	  double read_time)
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;
diff --git a/sql/sql_show.cc b/sql/sql_show.cc
index 158d9b1acb0..8ad0238e7c6 100644
--- a/sql/sql_show.cc
+++ b/sql/sql_show.cc
@@ -1831,6 +1831,11 @@ int mysqld_show(THD *thd, const char *wild, show_var_st *variables,
         end= strend(pos);
         break;
       }
+      case SHOW_DOUBLE:
+      {
+        end= buff + sprintf(buff, "%f", *(double*) value);
+        break;
+      }
 #ifdef HAVE_OPENSSL
 	/* First group - functions relying on CTX */
       case SHOW_SSL_CTX_SESS_ACCEPT:
diff --git a/sql/structs.h b/sql/structs.h
index 37208e63400..3279428c888 100644
--- a/sql/structs.h
+++ b/sql/structs.h
@@ -156,8 +156,8 @@ typedef struct st_known_date_time_format {
 enum SHOW_TYPE
 {
   SHOW_UNDEF,
-  SHOW_LONG, SHOW_LONGLONG, SHOW_INT, SHOW_CHAR, SHOW_CHAR_PTR, SHOW_BOOL,
-  SHOW_MY_BOOL, SHOW_OPENTABLES, SHOW_STARTTIME, SHOW_QUESTION,
+  SHOW_LONG, SHOW_LONGLONG, SHOW_INT, SHOW_CHAR, SHOW_CHAR_PTR, SHOW_DOUBLE,
+  SHOW_BOOL, SHOW_MY_BOOL, SHOW_OPENTABLES, SHOW_STARTTIME, SHOW_QUESTION,
   SHOW_LONG_CONST, SHOW_INT_CONST, SHOW_HAVE, SHOW_SYS, SHOW_HA_ROWS,
 #ifdef HAVE_OPENSSL
   SHOW_SSL_CTX_SESS_ACCEPT, 	SHOW_SSL_CTX_SESS_ACCEPT_GOOD,