Merge lp:maria -> lp:~maria-captains/maria/maria-5.1-merge

36 files changed, 2648 insertions, 205 deletions

diff --git a/sql/CMakeLists.txt b/sql/CMakeLists.txt
index 7ba0a4cceb2..58ba26782f9 100755
--- a/sql/CMakeLists.txt
+++ b/sql/CMakeLists.txt
@@ -25,7 +25,7 @@ INCLUDE_DIRECTORIES(${CMAKE_SOURCE_DIR}/include
                     ${CMAKE_SOURCE_DIR}/sql 
                     ${CMAKE_SOURCE_DIR}/regex 
                     ${CMAKE_SOURCE_DIR}/zlib
-                    ${CMAKE_SOURCE_DIR}/extra/libevent
+                    ${CMAKE_SOURCE_DIR}/extra/libevent 
 )
 
 SET_SOURCE_FILES_PROPERTIES(${CMAKE_SOURCE_DIR}/sql/sql_yacc.h 
@@ -75,7 +75,7 @@ SET (SQL_SOURCE
                partition_info.cc rpl_utility.cc rpl_injector.cc sql_locale.cc
                rpl_rli.cc rpl_mi.cc sql_servers.cc
                sql_connect.cc scheduler.cc 
-               sql_profile.cc event_parse_data.cc
+               sql_profile.cc event_parse_data.cc opt_table_elimination.cc
                ${PROJECT_SOURCE_DIR}/sql/sql_yacc.cc
                ${PROJECT_SOURCE_DIR}/sql/sql_yacc.h
                ${PROJECT_SOURCE_DIR}/include/mysqld_error.h
@@ -129,7 +129,7 @@ ADD_CUSTOM_COMMAND(
 
 # Gen_lex_hash
 ADD_EXECUTABLE(gen_lex_hash gen_lex_hash.cc)
-TARGET_LINK_LIBRARIES(gen_lex_hash debug dbug mysqlclient wsock32)
+TARGET_LINK_LIBRARIES(gen_lex_hash debug dbug mysqlclient strings wsock32)
 GET_TARGET_PROPERTY(GEN_LEX_HASH_EXE gen_lex_hash LOCATION)
 ADD_CUSTOM_COMMAND(
         OUTPUT ${PROJECT_SOURCE_DIR}/sql/lex_hash.h
diff --git a/sql/Makefile.am b/sql/Makefile.am
index 937acc95403..00342f7034e 100644
--- a/sql/Makefile.am
+++ b/sql/Makefile.am
@@ -61,7 +61,7 @@ noinst_HEADERS =	item.h item_func.h item_sum.h item_cmpfunc.h \
 			ha_partition.h rpl_constants.h \
 			opt_range.h protocol.h rpl_tblmap.h rpl_utility.h \
 			rpl_reporting.h \
-			log.h sql_show.h rpl_rli.h rpl_mi.h \
+			log.h log_slow.h sql_show.h rpl_rli.h rpl_mi.h \
 			sql_select.h structs.h table.h sql_udf.h hash_filo.h \
 			lex.h lex_symbol.h sql_acl.h sql_crypt.h  \
 			sql_repl.h slave.h rpl_filter.h rpl_injector.h \
@@ -121,7 +121,8 @@ mysqld_SOURCES =	sql_lex.cc sql_handler.cc sql_partition.cc \
                         event_queue.cc event_db_repository.cc events.cc \
 			sql_plugin.cc sql_binlog.cc \
 			sql_builtin.cc sql_tablespace.cc partition_info.cc \
-			sql_servers.cc event_parse_data.cc
+			sql_servers.cc event_parse_data.cc \
+                        opt_table_elimination.cc
 
 nodist_mysqld_SOURCES =	mini_client_errors.c pack.c client.c my_time.c my_user.c 
 
diff --git a/sql/event_data_objects.cc b/sql/event_data_objects.cc
index d11aa67ac65..331b437b7ff 100644
--- a/sql/event_data_objects.cc
+++ b/sql/event_data_objects.cc
@@ -1450,8 +1450,7 @@ Event_job_data::execute(THD *thd, bool drop)
 
     DBUG_ASSERT(sphead);
 
-    if (thd->enable_slow_log)
-      sphead->m_flags|= sp_head::LOG_SLOW_STATEMENTS;
+    sphead->m_flags|= sp_head::LOG_SLOW_STATEMENTS;
     sphead->m_flags|= sp_head::LOG_GENERAL_LOG;
 
     sphead->set_info(0, 0, &thd->lex->sp_chistics, sql_mode);
diff --git a/sql/events.cc b/sql/events.cc
index 17b00490495..c4c00e09b4a 100644
--- a/sql/events.cc
+++ b/sql/events.cc
@@ -697,8 +697,7 @@ send_show_create_event(THD *thd, Event_timed *et, Protocol *protocol)
 
   field_list.push_back(new Item_empty_string("Event", NAME_CHAR_LEN));
 
-  if (sys_var_thd_sql_mode::symbolic_mode_representation(thd, et->sql_mode,
-                                                         &sql_mode))
+  if (sys_var::make_set(thd, et->sql_mode, &sql_mode_typelib, &sql_mode))
     DBUG_RETURN(TRUE);
 
   field_list.push_back(new Item_empty_string("sql_mode", (uint) sql_mode.length));
diff --git a/sql/filesort.cc b/sql/filesort.cc
index f5fe17e6ff1..552ea27970f 100644
--- a/sql/filesort.cc
+++ b/sql/filesort.cc
@@ -188,6 +188,7 @@ ha_rows filesort(THD *thd, TABLE *table, SORT_FIELD *sortorder, uint s_length,
   {
     status_var_increment(thd->status_var.filesort_scan_count);
   }
+  thd->query_plan_flags|= QPLAN_FILESORT;
 #ifdef CAN_TRUST_RANGE
   if (select && select->quick && select->quick->records > 0L)
   {
@@ -253,6 +254,7 @@ ha_rows filesort(THD *thd, TABLE *table, SORT_FIELD *sortorder, uint s_length,
   }
   else
   {
+    thd->query_plan_flags|= QPLAN_FILESORT_DISK;
     if (table_sort.buffpek && table_sort.buffpek_len < maxbuffer)
     {
       x_free(table_sort.buffpek);
@@ -1199,6 +1201,7 @@ int merge_buffers(SORTPARAM *param, IO_CACHE *from_file,
   DBUG_ENTER("merge_buffers");
 
   status_var_increment(current_thd->status_var.filesort_merge_passes);
+  current_thd->query_plan_fsort_passes++;
   if (param->not_killable)
   {
     killed= &not_killable;
diff --git a/sql/item.cc b/sql/item.cc
index ec42b2b5886..b2ab28a77fd 100644
--- a/sql/item.cc
+++ b/sql/item.cc
@@ -1922,6 +1922,15 @@ void Item_field::reset_field(Field *f)
   name= (char*) f->field_name;
 }
 
+
+bool Item_field::enumerate_field_refs_processor(uchar *arg)
+{
+  Field_enumerator *fe= (Field_enumerator*)arg;
+  fe->visit_field(field);
+  return FALSE;
+}
+
+
 const char *Item_ident::full_name() const
 {
   char *tmp;
@@ -3599,7 +3608,7 @@ static void mark_as_dependent(THD *thd, SELECT_LEX *last, SELECT_LEX *current,
   /* store pointer on SELECT_LEX from which item is dependent */
   if (mark_item)
     mark_item->depended_from= last;
-  current->mark_as_dependent(last);
+  current->mark_as_dependent(last, resolved_item);
   if (thd->lex->describe & DESCRIBE_EXTENDED)
   {
     push_warning_printf(thd, MYSQL_ERROR::WARN_LEVEL_NOTE,
diff --git a/sql/item.h b/sql/item.h
index 2a9e5b00add..74c4ca701f7 100644
--- a/sql/item.h
+++ b/sql/item.h
@@ -731,7 +731,11 @@ public:
   virtual bool val_bool_result() { return val_bool(); }
   virtual bool is_null_result() { return is_null(); }
 
-  /* bit map of tables used by item */
+  /* 
+    Bitmap of tables used by item
+    (note: if you need to check dependencies on individual columns, check out
+     class Field_enumerator)
+  */
   virtual table_map used_tables() const { return (table_map) 0L; }
   /*
     Return table map of tables that can't be NULL tables (tables that are
@@ -888,6 +892,8 @@ public:
   virtual bool reset_query_id_processor(uchar *query_id_arg) { return 0; }
   virtual bool is_expensive_processor(uchar *arg) { return 0; }
   virtual bool register_field_in_read_map(uchar *arg) { return 0; }
+  virtual bool enumerate_field_refs_processor(uchar *arg) { return 0; }
+  virtual bool mark_as_eliminated_processor(uchar *arg) { return 0; }
   /*
     Check if a partition function is allowed
     SYNOPSIS
@@ -1012,6 +1018,29 @@ public:
 };
 
 
+/*
+  Class to be used to enumerate all field references in an item tree.
+  Suggested usage:
+
+    class My_enumerator : public Field_enumerator 
+    {
+      virtual void visit_field() { ... your actions ...} 
+    }
+
+    My_enumerator enumerator;
+    item->walk(Item::enumerate_field_refs_processor, ...,(uchar*)&enumerator);
+
+  This is similar to Visitor pattern.
+*/
+
+class Field_enumerator
+{
+public:
+  virtual void visit_field(Field *field)= 0;
+  virtual ~Field_enumerator() {}; /* purecov: inspected */
+};
+
+
 class sp_head;
 
 
@@ -1477,6 +1506,7 @@ public:
   bool find_item_in_field_list_processor(uchar *arg);
   bool register_field_in_read_map(uchar *arg);
   bool check_partition_func_processor(uchar *int_arg) {return FALSE;}
+  bool enumerate_field_refs_processor(uchar *arg);
   void cleanup();
   bool result_as_longlong()
   {
@@ -2203,6 +2233,10 @@ public:
     if (!depended_from) 
       (*ref)->update_used_tables(); 
   }
+  bool const_item() const 
+  {
+    return (*ref)->const_item();
+  }
   table_map not_null_tables() const { return (*ref)->not_null_tables(); }
   void set_result_field(Field *field)	{ result_field= field; }
   bool is_result_field() { return 1; }
diff --git a/sql/item_cmpfunc.cc b/sql/item_cmpfunc.cc
index bb391187fb9..b2e7be5ef09 100644
--- a/sql/item_cmpfunc.cc
+++ b/sql/item_cmpfunc.cc
@@ -5168,33 +5168,7 @@ void Item_equal::merge(Item_equal *item)
 
 void Item_equal::sort(Item_field_cmpfunc cmp, void *arg)
 {
-  bool swap;
-  List_iterator<Item_field> it(fields);
-  do
-  {
-    Item_field *item1= it++;
-    Item_field **ref1= it.ref();
-    Item_field *item2;
-
-    swap= FALSE;
-    while ((item2= it++))
-    {
-      Item_field **ref2= it.ref();
-      if (cmp(item1, item2, arg) < 0)
-      {
-        Item_field *item= *ref1;
-        *ref1= *ref2;
-        *ref2= item;
-        swap= TRUE;
-      }
-      else
-      {
-        item1= item2;
-        ref1= ref2;
-      }
-    }
-    it.rewind();
-  } while (swap);
+  exchange_sort<Item_field>(&fields, cmp, arg);
 }
 
 
diff --git a/sql/item_cmpfunc.h b/sql/item_cmpfunc.h
index c2227fa04e0..23f505182dd 100644
--- a/sql/item_cmpfunc.h
+++ b/sql/item_cmpfunc.h
@@ -1578,6 +1578,7 @@ public:
   uint members();
   bool contains(Field *field);
   Item_field* get_first() { return fields.head(); }
+  uint n_fields() { return fields.elements; }
   void merge(Item_equal *item);
   void update_const();
   enum Functype functype() const { return MULT_EQUAL_FUNC; }
diff --git a/sql/item_subselect.cc b/sql/item_subselect.cc
index 6fa23b77f0d..7ee22fb3c1c 100644
--- a/sql/item_subselect.cc
+++ b/sql/item_subselect.cc
@@ -39,7 +39,7 @@ inline Item * and_items(Item* cond, Item *item)
 Item_subselect::Item_subselect():
   Item_result_field(), value_assigned(0), thd(0), substitution(0),
   engine(0), old_engine(0), used_tables_cache(0), have_to_be_excluded(0),
-  const_item_cache(1), engine_changed(0), changed(0), is_correlated(FALSE)
+  const_item_cache(1), in_fix_fields(0), engine_changed(0), changed(0), is_correlated(FALSE)
 {
   with_subselect= 1;
   reset();
@@ -151,10 +151,14 @@ bool Item_subselect::fix_fields(THD *thd_param, Item **ref)
 
   DBUG_ASSERT(fixed == 0);
   engine->set_thd((thd= thd_param));
+  if (!in_fix_fields)
+    refers_to.empty();
+  eliminated= FALSE;
 
   if (check_stack_overrun(thd, STACK_MIN_SIZE, (uchar*)&res))
     return TRUE;
-
+  
+  in_fix_fields++;
   res= engine->prepare();
 
   // all transformation is done (used by prepared statements)
@@ -181,12 +185,14 @@ bool Item_subselect::fix_fields(THD *thd_param, Item **ref)
       if (!(*ref)->fixed)
 	ret= (*ref)->fix_fields(thd, ref);
       thd->where= save_where;
+      in_fix_fields--;
       return ret;
     }
     // Is it one field subselect?
     if (engine->cols() > max_columns)
     {
       my_error(ER_OPERAND_COLUMNS, MYF(0), 1);
+      in_fix_fields--;
       return TRUE;
     }
     fix_length_and_dec();
@@ -203,11 +209,30 @@ bool Item_subselect::fix_fields(THD *thd_param, Item **ref)
   fixed= 1;
 
 err:
+  in_fix_fields--;
   thd->where= save_where;
   return res;
 }
 
 
+bool Item_subselect::enumerate_field_refs_processor(uchar *arg)
+{
+  List_iterator<Item> it(refers_to);
+  Item *item;
+  while ((item= it++))
+  {
+    if (item->walk(&Item::enumerate_field_refs_processor, FALSE, arg))
+      return TRUE;
+  }
+  return FALSE;
+}
+
+bool Item_subselect::mark_as_eliminated_processor(uchar *arg)
+{
+  eliminated= TRUE;
+  return FALSE;
+}
+
 bool Item_subselect::walk(Item_processor processor, bool walk_subquery,
                           uchar *argument)
 {
@@ -225,6 +250,7 @@ bool Item_subselect::walk(Item_processor processor, bool walk_subquery,
       if (lex->having && (lex->having)->walk(processor, walk_subquery,
                                              argument))
         return 1;
+      /* TODO: why does this walk WHERE/HAVING but not ON expressions of outer joins? */
 
       while ((item=li++))
       {
diff --git a/sql/item_subselect.h b/sql/item_subselect.h
index d4aa621c083..19d58c65259 100644
--- a/sql/item_subselect.h
+++ b/sql/item_subselect.h
@@ -52,8 +52,16 @@ protected:
   bool have_to_be_excluded;
   /* cache of constant state */
   bool const_item_cache;
-
+  
 public:
+  /* 
+    References from inside the subquery to the select that this predicate is
+    in.  References to parent selects not included.
+  */
+  List<Item> refers_to;
+  int in_fix_fields;
+  bool eliminated;
+  
   /* changed engine indicator */
   bool engine_changed;
   /* subquery is transformed */
@@ -126,6 +134,8 @@ public:
   virtual void reset_value_registration() {}
   enum_parsing_place place() { return parsing_place; }
   bool walk(Item_processor processor, bool walk_subquery, uchar *arg);
+  bool mark_as_eliminated_processor(uchar *arg);
+  bool enumerate_field_refs_processor(uchar *arg);
 
   /**
     Get the SELECT_LEX structure associated with this Item.
diff --git a/sql/item_sum.cc b/sql/item_sum.cc
index 97779b6a2b7..ab2da503209 100644
--- a/sql/item_sum.cc
+++ b/sql/item_sum.cc
@@ -350,7 +350,7 @@ bool Item_sum::register_sum_func(THD *thd, Item **ref)
          sl= sl->master_unit()->outer_select() )
       sl->master_unit()->item->with_sum_func= 1;
   }
-  thd->lex->current_select->mark_as_dependent(aggr_sel);
+  thd->lex->current_select->mark_as_dependent(aggr_sel, NULL);
   return FALSE;
 }
 
@@ -542,11 +542,6 @@ void Item_sum::update_used_tables ()
       args[i]->update_used_tables();
       used_tables_cache|= args[i]->used_tables();
     }
-
-    used_tables_cache&= PSEUDO_TABLE_BITS;
-
-    /* the aggregate function is aggregated into its local context */
-    used_tables_cache |=  (1 << aggr_sel->join->tables) - 1;
   }
 }
 
diff --git a/sql/item_sum.h b/sql/item_sum.h
index d991327d847..e884452d6e6 100644
--- a/sql/item_sum.h
+++ b/sql/item_sum.h
@@ -255,6 +255,12 @@ protected:
   */
   Item **orig_args, *tmp_orig_args[2];
   table_map used_tables_cache;
+  
+  /*
+    TRUE <=> We've managed to calculate the value of this Item in
+    opt_sum_query(), hence it can be considered constant at all subsequent
+    steps.
+  */
   bool forced_const;
 
 public:  
@@ -341,6 +347,15 @@ public:
   virtual const char *func_name() const= 0;
   virtual Item *result_item(Field *field)
     { return new Item_field(field); }
+  /*
+    Return bitmap of tables that are needed to evaluate the item.
+
+    The implementation takes into account the used strategy: items resolved
+    at optimization phase will report 0.
+    Items that depend on the number of join output records, but not columns
+    of any particular table (like COUNT(*)) will report 0 from used_tables(),
+    but will still return false from const_item().
+  */
   table_map used_tables() const { return used_tables_cache; }
   void update_used_tables ();
   void cleanup() 
diff --git a/sql/log.cc b/sql/log.cc
index 58d00819cf7..ea71e6caefd 100644
--- a/sql/log.cc
+++ b/sql/log.cc
@@ -983,7 +983,7 @@ bool LOGGER::slow_log_print(THD *thd, const char *query, uint query_length,
     /* fill in user_host value: the format is "%s[%s] @ %s [%s]" */
     user_host_len= (strxnmov(user_host_buff, MAX_USER_HOST_SIZE,
                              sctx->priv_user ? sctx->priv_user : "", "[",
-                             sctx->user ? sctx->user : "", "] @ ",
+                             sctx->user ? sctx->user : (thd->slave_thread ? "SQL_SLAVE" : ""), "] @ ",
                              sctx->host ? sctx->host : "", " [",
                              sctx->ip ? sctx->ip : "", "]", NullS) -
                     user_host_buff);
@@ -1006,6 +1006,17 @@ bool LOGGER::slow_log_print(THD *thd, const char *query, uint query_length,
       query_length= command_name[thd->command].length;
     }
 
+    if (!query_length) 
+    {
+      /*
+        Not a real query; Reset counts for slow query logging
+        (QQ: Wonder if this is really needed)
+      */
+      thd->sent_row_count= thd->examined_row_count= 0;
+      thd->query_plan_flags= QPLAN_INIT;
+      thd->query_plan_fsort_passes= 0;
+    }
+
     for (current_handler= slow_log_handler_list; *current_handler ;)
       error= (*current_handler++)->log_slow(thd, current_time, thd->start_time,
                                             user_host_buff, user_host_len,
@@ -2295,19 +2306,39 @@ bool MYSQL_QUERY_LOG::write(THD *thd, time_t current_time,
       if (my_b_write(&log_file, (uchar*) "\n", 1))
         tmp_errno= errno;
     }
+    
     /* For slow query log */
     sprintf(query_time_buff, "%.6f", ulonglong2double(query_utime)/1000000.0);
     sprintf(lock_time_buff,  "%.6f", ulonglong2double(lock_utime)/1000000.0);
     if (my_b_printf(&log_file,
-                    "# Query_time: %s  Lock_time: %s"
-                    " Rows_sent: %lu  Rows_examined: %lu\n",
+                    "# Thread_id: %lu  Schema: %s  QC_hit: %s\n" \
+                    "# Query_time: %s  Lock_time: %s  Rows_sent: %lu  Rows_examined: %lu\n",
+                    (ulong) thd->thread_id, (thd->db ? thd->db : ""),
+                    ((thd->query_plan_flags & QPLAN_QC) ? "Yes" : "No"),
                     query_time_buff, lock_time_buff,
                     (ulong) thd->sent_row_count,
-                    (ulong) thd->examined_row_count) == (uint) -1)
+                    (ulong) thd->examined_row_count) == (size_t) -1)
       tmp_errno= errno;
+     if ((thd->variables.log_slow_verbosity & LOG_SLOW_VERBOSITY_QUERY_PLAN) &&
+         (thd->query_plan_flags &
+          (QPLAN_FULL_SCAN | QPLAN_FULL_JOIN | QPLAN_TMP_TABLE |
+           QPLAN_TMP_DISK | QPLAN_FILESORT | QPLAN_FILESORT_DISK)) &&
+         my_b_printf(&log_file,
+                     "# Full_scan: %s  Full_join: %s  "
+                     "Tmp_table: %s  Tmp_table_on_disk: %s\n"
+                     "# Filesort: %s  Filesort_on_disk: %s  Merge_passes: %lu\n",
+                     ((thd->query_plan_flags & QPLAN_FULL_SCAN) ? "Yes" : "No"),
+                     ((thd->query_plan_flags & QPLAN_FULL_JOIN) ? "Yes" : "No"),
+                     ((thd->query_plan_flags & QPLAN_TMP_TABLE) ? "Yes" : "No"),
+                     ((thd->query_plan_flags & QPLAN_TMP_DISK) ? "Yes" : "No"),
+                     ((thd->query_plan_flags & QPLAN_FILESORT) ? "Yes" : "No"),
+                     ((thd->query_plan_flags & QPLAN_FILESORT_DISK) ?
+                      "Yes" : "No"),
+                     thd->query_plan_fsort_passes) == (size_t) -1)
+       tmp_errno= errno;
     if (thd->db && strcmp(thd->db, db))
     {						// Database changed
-      if (my_b_printf(&log_file,"use %s;\n",thd->db) == (uint) -1)
+      if (my_b_printf(&log_file,"use %s;\n",thd->db) == (size_t) -1)
         tmp_errno= errno;
       strmov(db,thd->db);
     }
diff --git a/sql/log_slow.h b/sql/log_slow.h
new file mode 100644
index 00000000000..5559c002fde
--- /dev/null
+++ b/sql/log_slow.h
@@ -0,0 +1,107 @@
+/* Copyright (C) 2009 Monty Program Ab
+
+   This program is free software; you can redistribute it and/or modify
+   it under the terms of the GNU General Public License as published by
+   the Free Software Foundation; version 2 or later of the License.
+
+   This program is distributed in the hope that it will be useful,
+   but WITHOUT ANY WARRANTY; without even the implied warranty of
+   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+   GNU General Public License for more details.
+
+   You should have received a copy of the GNU General Public License
+   along with this program; if not, write to the Free Software
+   Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA */
+
+/* Defining what to log to slow log */
+
+#define LOG_SLOW_VERBOSITY_INIT           0
+#define LOG_SLOW_VERBOSITY_INNODB         1 << 0
+#define LOG_SLOW_VERBOSITY_QUERY_PLAN     1 << 1
+
+#ifdef DEFINE_VARIABLES_LOG_SLOW
+
+/* Names here must be in same order as the bit's above */
+static const char *log_slow_verbosity_names[]=
+{
+  "innodb","query_plan",
+  NullS
+};
+
+static const unsigned int log_slow_verbosity_names_len[]=
+{
+  sizeof("innodb") -1,
+  sizeof("query_plan")-1
+};
+
+TYPELIB log_slow_verbosity_typelib=
+{  array_elements(log_slow_verbosity_names)-1,"", log_slow_verbosity_names,
+   (unsigned int *) log_slow_verbosity_names_len };
+
+#else
+extern TYPELIB log_slow_verbosity_typelib;
+#endif /* DEFINE_VARIABLES_LOG_SLOW */
+
+/* Defines for what kind of query plan was used and what to log */
+
+/*
+  We init the used query plan with a bit that is alwyas set and all 'no' bits
+  to enable easy testing of what to log in sql_log.cc
+*/
+#define QPLAN_INIT            (QPLAN_ALWAYS_SET | QPLAN_QC_NO)
+
+#define QPLAN_ADMIN           1 << 0
+#define QPLAN_FILESORT        1 << 1
+#define QPLAN_FILESORT_DISK   1 << 2
+#define QPLAN_FULL_JOIN       1 << 3
+#define QPLAN_FULL_SCAN       1 << 4
+#define QPLAN_QC              1 << 5
+#define QPLAN_QC_NO           1 << 6
+#define QPLAN_TMP_DISK        1 << 7
+#define QPLAN_TMP_TABLE       1 << 8
+/* ... */
+#define QPLAN_MAX             ((ulong) 1) << 31 /* reserved as placeholder */
+#define QPLAN_ALWAYS_SET      QPLAN_MAX
+#define QPLAN_VISIBLE_MASK    (~(QPLAN_ALWAYS_SET))
+
+#ifdef DEFINE_VARIABLES_LOG_SLOW
+/* Names here must be in same order as the bit's above */
+static const char *log_slow_filter_names[]= 
+{
+  "admin",
+  "filesort",
+  "filesort_on_disk",
+  "full_join",
+  "full_scan",
+  "query_cache",
+  "query_cache_miss",
+  "tmp_table",
+  "tmp_table_on_disk",
+  NullS
+};
+
+static const unsigned int log_slow_filter_names_len[]=
+{
+  sizeof("admin")-1,
+  sizeof("filesort")-1,
+  sizeof("filesort_on_disk")-1,
+  sizeof("full_join")-1,
+  sizeof("full_scan")-1,
+  sizeof("query_cache")-1,
+  sizeof("query_cache_miss")-1,
+  sizeof("tmp_table")-1,
+  sizeof("tmp_table_on_disk")-1
+};
+
+TYPELIB log_slow_filter_typelib=
+{  array_elements(log_slow_filter_names)-1,"", log_slow_filter_names,
+   (unsigned int *) log_slow_filter_names_len };
+
+#else
+extern TYPELIB log_slow_filter_typelib;
+#endif /* DEFINE_VARIABLES_LOG_SLOW */
+
+static inline ulong fix_log_slow_filter(ulong org_filter)
+{
+  return org_filter ? org_filter : QPLAN_ALWAYS_SET;
+}
diff --git a/sql/mysql_priv.h b/sql/mysql_priv.h
index 3c46ba7ea3a..63d5621742e 100644
--- a/sql/mysql_priv.h
+++ b/sql/mysql_priv.h
@@ -43,6 +43,7 @@
 #include "sql_array.h"
 #include "sql_plugin.h"
 #include "scheduler.h"
+#include "log_slow.h"
 
 class Parser_state;
 
@@ -535,14 +536,27 @@ protected:
 #define OPTIMIZER_SWITCH_INDEX_MERGE_UNION 2
 #define OPTIMIZER_SWITCH_INDEX_MERGE_SORT_UNION 4
 #define OPTIMIZER_SWITCH_INDEX_MERGE_INTERSECT 8
-#define OPTIMIZER_SWITCH_LAST 16
 
-/* The following must be kept in sync with optimizer_switch_str in mysqld.cc */
-#define OPTIMIZER_SWITCH_DEFAULT (OPTIMIZER_SWITCH_INDEX_MERGE | \
-                                  OPTIMIZER_SWITCH_INDEX_MERGE_UNION | \
-                                  OPTIMIZER_SWITCH_INDEX_MERGE_SORT_UNION | \
-                                  OPTIMIZER_SWITCH_INDEX_MERGE_INTERSECT)
+#ifdef DBUG_OFF
+#  define OPTIMIZER_SWITCH_LAST 16
+#else
+#  define OPTIMIZER_SWITCH_TABLE_ELIMINATION 16
+#  define OPTIMIZER_SWITCH_LAST 32
+#endif
 
+#ifdef DBUG_OFF 
+/* The following must be kept in sync with optimizer_switch_str in mysqld.cc */
+#  define OPTIMIZER_SWITCH_DEFAULT (OPTIMIZER_SWITCH_INDEX_MERGE | \
+                                    OPTIMIZER_SWITCH_INDEX_MERGE_UNION | \
+                                    OPTIMIZER_SWITCH_INDEX_MERGE_SORT_UNION | \
+                                    OPTIMIZER_SWITCH_INDEX_MERGE_INTERSECT)
+#else 
+#  define OPTIMIZER_SWITCH_DEFAULT (OPTIMIZER_SWITCH_INDEX_MERGE | \
+                                    OPTIMIZER_SWITCH_INDEX_MERGE_UNION | \
+                                    OPTIMIZER_SWITCH_INDEX_MERGE_SORT_UNION | \
+                                    OPTIMIZER_SWITCH_INDEX_MERGE_INTERSECT | \
+                                    OPTIMIZER_SWITCH_TABLE_ELIMINATION)
+#endif
 
 /*
   Replication uses 8 bytes to store SQL_MODE in the binary log. The day you
diff --git a/sql/mysqld.cc b/sql/mysqld.cc
index 0cb8544b880..8988ad0671b 100644
--- a/sql/mysqld.cc
+++ b/sql/mysqld.cc
@@ -13,6 +13,7 @@
    along with this program; if not, write to the Free Software
    Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA */
 
+#define DEFINE_VARIABLES_LOG_SLOW          // Declare variables in log_slow.h
 #include "mysql_priv.h"
 #include <m_ctype.h>
 #include <my_dir.h>
@@ -297,9 +298,14 @@ TYPELIB sql_mode_typelib= { array_elements(sql_mode_names)-1,"",
 
 static const char *optimizer_switch_names[]=
 {
-  "index_merge","index_merge_union","index_merge_sort_union", 
-  "index_merge_intersection", "default", NullS
+  "index_merge","index_merge_union","index_merge_sort_union",
+  "index_merge_intersection",
+#ifndef DBUG_OFF
+  "table_elimination",
+#endif
+  "default", NullS
 };
+
 /* Corresponding defines are named OPTIMIZER_SWITCH_XXX */
 static const unsigned int optimizer_switch_names_len[]=
 {
@@ -307,6 +313,9 @@ static const unsigned int optimizer_switch_names_len[]=
   sizeof("index_merge_union") - 1,
   sizeof("index_merge_sort_union") - 1,
   sizeof("index_merge_intersection") - 1,
+#ifndef DBUG_OFF
+  sizeof("table_elimination") - 1,
+#endif
   sizeof("default") - 1
 };
 TYPELIB optimizer_switch_typelib= { array_elements(optimizer_switch_names)-1,"",
@@ -382,7 +391,12 @@ static const char *sql_mode_str= "OFF";
 /* Text representation for OPTIMIZER_SWITCH_DEFAULT */
 static const char *optimizer_switch_str="index_merge=on,index_merge_union=on,"
                                         "index_merge_sort_union=on,"
-                                        "index_merge_intersection=on";
+                                        "index_merge_intersection=on"
+#ifndef DBUG_OFF                                        
+                                        ",table_elimination=on";
+#else
+                                        ;
+#endif
 static char *mysqld_user, *mysqld_chroot, *log_error_file_ptr;
 static char *opt_init_slave, *language_ptr, *opt_init_connect;
 static char *default_character_set_name;
@@ -1020,6 +1034,7 @@ static void close_connections(void)
 }
 
 
+#ifdef HAVE_CLOSE_SERVER_SOCK
 static void close_socket(my_socket sock, const char *info)
 {
   DBUG_ENTER("close_socket");
@@ -1039,6 +1054,7 @@ static void close_socket(my_socket sock, const char *info)
   }
   DBUG_VOID_RETURN;
 }
+#endif
 
 
 static void close_server_sock()
@@ -5793,6 +5809,9 @@ enum options_mysqld
   OPT_DEADLOCK_SEARCH_DEPTH_LONG,
   OPT_DEADLOCK_TIMEOUT_SHORT,
   OPT_DEADLOCK_TIMEOUT_LONG,
+  OPT_LOG_SLOW_RATE_LIMIT, 
+  OPT_LOG_SLOW_VERBOSITY, 
+  OPT_LOG_SLOW_FILTER, 
   OPT_GENERAL_LOG_FILE,
   OPT_SLOW_QUERY_LOG_FILE,
   OPT_IGNORE_BUILTIN_INNODB
@@ -6135,7 +6154,7 @@ Disable with --skip-large-pages.",
    (uchar**) &opt_log_slave_updates, (uchar**) &opt_log_slave_updates, 0, GET_BOOL,
    NO_ARG, 0, 0, 0, 0, 0, 0},
   {"log-slow-admin-statements", OPT_LOG_SLOW_ADMIN_STATEMENTS,
-   "Log slow OPTIMIZE, ANALYZE, ALTER and other administrative statements to the slow log if it is open.",
+   "Log slow OPTIMIZE, ANALYZE, ALTER and other administrative statements to the slow log if it is open. .  Please note that this option is deprecated; see --log-slow-filter for filtering slow query log output",
    (uchar**) &opt_log_slow_admin_statements,
    (uchar**) &opt_log_slow_admin_statements,
    0, GET_BOOL, NO_ARG, 0, 0, 0, 0, 0, 0},
@@ -6144,15 +6163,15 @@ Disable with --skip-large-pages.",
   (uchar**) &opt_log_slow_slave_statements,
   (uchar**) &opt_log_slow_slave_statements,
   0, GET_BOOL, NO_ARG, 0, 0, 0, 0, 0, 0},
-  {"log_slow_queries", OPT_SLOW_QUERY_LOG,
+  {"log-slow-queries", OPT_SLOW_QUERY_LOG,
     "Log slow queries to a table or log file. Defaults logging to table "
     "mysql.slow_log or hostname-slow.log if --log-output=file is used. "
     "Must be enabled to activate other slow log options. "
     "(deprecated option, use --slow_query_log/--slow_query_log_file instead)",
    (uchar**) &opt_slow_logname, (uchar**) &opt_slow_logname, 0, GET_STR, OPT_ARG,
    0, 0, 0, 0, 0, 0},
-  {"slow_query_log_file", OPT_SLOW_QUERY_LOG_FILE,
-    "Log slow queries to given log file. Defaults logging to hostname-slow.log. Must be enabled to activate other slow log options.",
+  {"slow-query-log-file", OPT_SLOW_QUERY_LOG_FILE,
+    "Log slow queries to given log file. Defaults logging to hostname-slow.log.",
    (uchar**) &opt_slow_logname, (uchar**) &opt_slow_logname, 0, GET_STR,
    REQUIRED_ARG, 0, 0, 0, 0, 0, 0},
   {"log-tc", OPT_LOG_TC,
@@ -6772,11 +6791,31 @@ log and this option does nothing anymore.",
    (uchar**) 0,
    0, (GET_ULONG | GET_ASK_ADDR) , REQUIRED_ARG, 100,
    1, 100, 0, 1, 0},
+  {"log-slow-filter", OPT_LOG_SLOW_FILTER,
+   "Log only the queries that followed certain execution plan. Multiple flags allowed in a comma-separated string. [admin, filesort, filesort_on_disk, full_join, full_scan, query_cache, query_cache_miss, tmp_table, tmp_table_on_disk]. Sets log-slow-admin-command to ON",
+   0, 0, 0, GET_STR, REQUIRED_ARG, 0, 0, 0, QPLAN_ALWAYS_SET, 0, 0},
+  {"log-slow-rate_limit", OPT_LOG_SLOW_RATE_LIMIT,
+   "If set, only write to slow log every 'log_slow_rate_limit' query (use this to reduce output on slow query log)",
+   (uchar**) &global_system_variables.log_slow_rate_limit,
+   (uchar**) &max_system_variables.log_slow_rate_limit, 0, GET_ULONG,
+   REQUIRED_ARG, 1, 1, ~0L, 0, 1L, 0},
+  {"log-slow-verbosity", OPT_LOG_SLOW_VERBOSITY,
+   "Choose how verbose the messages to your slow log will be. Multiple flags allowed in a comma-separated string. [query_plan, innodb]",
+   0, 0, 0, GET_STR, REQUIRED_ARG, 0, 0, 0, 0, 0, 0 },
+  {"log-slow-file", OPT_SLOW_QUERY_LOG_FILE,
+    "Log slow queries to given log file. Defaults logging to hostname-slow.log",
+   (uchar**) &opt_slow_logname, (uchar**) &opt_slow_logname, 0, GET_STR,
+   REQUIRED_ARG, 0, 0, 0, 0, 0, 0},
   {"long_query_time", OPT_LONG_QUERY_TIME,
    "Log all queries that have taken more than long_query_time seconds to execute to file. "
    "The argument will be treated as a decimal value with microsecond precission.",
    (uchar**) &long_query_time, (uchar**) &long_query_time, 0, GET_DOUBLE,
    REQUIRED_ARG, 10, 0, LONG_TIMEOUT, 0, 0, 0},
+  {"log-slow-time", OPT_LONG_QUERY_TIME,
+   "Log all queries that have taken more than long_query_time seconds to execute to file. "
+   "The argument will be treated as a decimal value with microsecond precission.",
+   (uchar**) &long_query_time, (uchar**) &long_query_time, 0, GET_DOUBLE,
+   REQUIRED_ARG, 10, 0, LONG_TIMEOUT, 0, 0, 0},
   {"lower_case_table_names", OPT_LOWER_CASE_TABLE_NAMES,
    "If set to 1 table names are stored in lowercase on disk and table names will be case-insensitive.  Should be set to 2 if you are using a case insensitive file system",
    (uchar**) &lower_case_table_names,
@@ -6963,8 +7002,11 @@ The minimum value for this variable is 4096.",
    0, GET_ULONG, OPT_ARG, MAX_TABLES+1, 0, MAX_TABLES+2, 0, 1, 0},
   {"optimizer_switch", OPT_OPTIMIZER_SWITCH,
    "optimizer_switch=option=val[,option=val...], where option={index_merge, "
-   "index_merge_union, index_merge_sort_union, index_merge_intersection} and "
-   "val={on, off, default}.",
+   "index_merge_union, index_merge_sort_union, index_merge_intersection"
+#ifndef DBUG_OFF
+   ", table_elimination"
+#endif 
+   "} and val={on, off, default}.",
    (uchar**) &optimizer_switch_str, (uchar**) &optimizer_switch_str, 0, GET_STR, REQUIRED_ARG, 
    /*OPTIMIZER_SWITCH_DEFAULT*/0,
    0, 0, 0, 0, 0},
@@ -7877,6 +7919,9 @@ static int mysql_init_variables(void)
   global_system_variables.old_passwords= 0;
   global_system_variables.old_alter_table= 0;
   global_system_variables.binlog_format= BINLOG_FORMAT_UNSPEC;
+  global_system_variables.log_slow_verbosity= LOG_SLOW_VERBOSITY_INIT;
+  global_system_variables.log_slow_filter=    QPLAN_ALWAYS_SET;
+  
   /*
     Default behavior for 4.1 and 5.0 is to treat NULL values as unequal
     when collecting index statistics for MyISAM tables.
@@ -8231,7 +8276,7 @@ mysqld_get_one_option(int optid,
   }
 #endif /* HAVE_REPLICATION */
   case (int) OPT_SLOW_QUERY_LOG:
-    WARN_DEPRECATED(NULL, "7.0", "--log_slow_queries", "'--slow_query_log'/'--slow_query_log_file'");
+    WARN_DEPRECATED(NULL, "7.0", "--log_slow_queries", "'--slow_query_log'/'--log-slow-file'");
     opt_slow_log= 1;
     break;
 #ifdef WITH_CSV_STORAGE_ENGINE
@@ -8384,6 +8429,25 @@ mysqld_get_one_option(int optid,
   case OPT_BOOTSTRAP:
     opt_noacl=opt_bootstrap=1;
     break;
+  case OPT_LOG_SLOW_FILTER:
+    global_system_variables.log_slow_filter=
+      find_bit_type_or_exit(argument, &log_slow_verbosity_typelib,
+                            opt->name, &error);
+    /*
+      If we are using filters, we set opt_slow_admin_statements to be always
+      true so we can maintain everything with filters
+    */
+    opt_log_slow_admin_statements= 1;
+    if (error)
+      return 1;
+    break;
+  case OPT_LOG_SLOW_VERBOSITY:
+    global_system_variables.log_slow_verbosity=
+      find_bit_type_or_exit(argument, &log_slow_filter_typelib,
+                            opt->name, &error);
+    if (error)
+      return 1;
+    break;
   case OPT_SERVER_ID:
     server_id_supplied = 1;
     break;
@@ -8692,6 +8756,8 @@ static int get_options(int *argc,char **argv)
   /* Set global slave_exec_mode from its option */
   fix_slave_exec_mode(OPT_GLOBAL);
 
+  global_system_variables.log_slow_filter=
+    fix_log_slow_filter(global_system_variables.log_slow_filter);
 #ifndef EMBEDDED_LIBRARY
   if (mysqld_chroot)
     set_root(mysqld_chroot);
diff --git a/sql/opt_range.h b/sql/opt_range.h
index 225af276e55..6a0234e62fe 100644
--- a/sql/opt_range.h
+++ b/sql/opt_range.h
@@ -38,6 +38,12 @@ typedef struct st_key_part {
 } KEY_PART;
 
 
+/*
+  A "MIN_TUPLE < tbl.key_tuple < MAX_TUPLE" interval. 
+  
+  One of endpoints may be absent. 'flags' member has flags which tell whether
+  the endpoints are '<' or '<='.
+*/
 class QUICK_RANGE :public Sql_alloc {
  public:
   uchar *min_key,*max_key;
diff --git a/sql/opt_table_elimination.cc b/sql/opt_table_elimination.cc
new file mode 100644
index 00000000000..712572b07b5
--- /dev/null
+++ b/sql/opt_table_elimination.cc
@@ -0,0 +1,1853 @@
+/**
+  @file
+
+  @brief
+    Table Elimination Module
+
+  @defgroup Table_Elimination Table Elimination Module
+  @{
+*/
+
+#ifdef USE_PRAGMA_IMPLEMENTATION
+#pragma implementation				// gcc: Class implementation
+#endif
+
+#include "mysql_priv.h"
+#include "my_bit.h"
+#include "sql_select.h"
+
+/*
+  OVERVIEW
+  ========
+
+  This file contains table elimination module. The idea behind table
+  elimination is as follows: suppose we have a left join
+ 
+    SELECT * FROM t1 LEFT JOIN 
+      (t2 JOIN t3) ON t2.primary_key=t1.col AND 
+                      t2.primary_key=t2.col
+    WHERE ...
+
+  such that
+  * columns of the inner tables are not used anywhere ouside the outer join
+    (not in WHERE, not in GROUP/ORDER BY clause, not in select list etc etc),
+  * inner side of the outer join is guaranteed to produce at most one matching
+    record combination for each record combination of outer tables.
+  
+  then the inner side of the outer join can be removed from the query, as it 
+  will always produce only one record combination (either real or 
+  null-complemented one) and we don't care about what that record combination 
+  is.
+
+
+  MODULE INTERFACE
+  ================
+
+  The module has one entry point - the eliminate_tables() function, which one
+  needs to call (once) at some point before join optimization.
+  eliminate_tables() operates over the JOIN structures. Logically, it
+  removes the inner tables of an outer join operation together with the
+  operation itself. Physically, it changes the following members:
+
+  * Eliminated tables are marked as constant and moved to the front of the
+    join order.
+
+  * In addition to this, they are recorded in JOIN::eliminated_tables bitmap.
+
+  * Items that became disused because they were in the ON expression of an 
+    eliminated outer join are notified by means of the Item tree walk which 
+    calls Item::mark_as_eliminated_processor for every item
+    - At the moment the only Item that cares whether it was eliminated is 
+      Item_subselect with its Item_subselect::eliminated flag which is used
+      by EXPLAIN code to check if the subquery should be shown in EXPLAIN.
+
+  Table elimination is redone on every PS re-execution.
+
+
+  TABLE ELIMINATION ALGORITHM FOR ONE OUTER JOIN
+  ==============================================
+
+  As described above, we can remove inner side of an outer join if it is 
+
+    1. not referred to from any other parts of the query
+    2. always produces one matching record combination.
+
+  We check #1 by doing a recursive descent down the join->join_list while
+  maintaining a union of used_tables() attribute of all Item expressions in
+  other parts of the query. When we encounter an outer join, we check if the
+  bitmap of tables on its inner side has intersection with tables that are used
+  elsewhere. No intersection means that inner side of the outer join could 
+  potentially be eliminated.
+
+  In order to check #2, one needs to prove that inner side of an outer join 
+  is functionally dependent on the outside. The proof is constructed from
+  functional dependencies of intermediate objects:
+
+  - Inner side of outer join is functionally dependent when each of its tables
+    are functionally dependent. (We assume a table is functionally dependent 
+    when its dependencies allow to uniquely identify one table record, or no
+    records).
+
+  - Table is functionally dependent when it has got a unique key whose columns
+    are functionally dependent.
+
+  - A column is functionally dependent when we could locate an AND-part of a
+    certain ON clause in form 
+      
+      tblX.columnY= expr 
+    
+    where expr is functionally depdendent. expr is functionally dependent when 
+    all columns that it refers to are functionally dependent.
+
+  These relationships are modeled as a bipartite directed graph that has
+  dependencies as edges and two kinds of nodes:
+
+  Value nodes:
+   - Table column values (each is a value of tblX.columnY)
+   - Table values (each node represents a table inside the join nest we're
+     trying to eliminate).
+  A value has one attribute, it is either bound (i.e. functionally dependent) 
+  or not.
+
+  Module nodes:
+   - Modules representing tblX.colY=expr equalities. Equality module has 
+      = incoming edges from columns used in expr 
+      = outgoing edge to tblX.colY column.
+   - Nodes representing unique keys. Unique key has
+      = incoming edges from key component value modules
+      = outgoing edge to key's table module
+   - Inner side of outer join module. Outer join module has
+      = incoming edges from table value modules
+      = No outgoing edges. Once we reach it, we know we can eliminate the 
+        outer join.
+  A module may depend on multiple values, and hence its primary attribute is
+  the number of its arguments that are not bound. 
+
+  The algorithm starts with equality nodes that don't have any incoming edges
+  (their expressions are either constant or depend only on tables that are
+  outside of the outer join in question) and performns a breadth-first
+  traversal. If we reach the outer join nest node, it means outer join is
+  functionally dependent and can be eliminated. Otherwise it cannot be
+  eliminated.
+ 
+  HANDLING MULTIPLE NESTED OUTER JOINS
+  ====================================
+
+  Outer joins that are not nested one within another are eliminated
+  independently. For nested outer joins we have the following considerations:
+  
+  1. ON expressions from children outer joins must be taken into account 
+   
+  Consider this example:
+
+    SELECT t0.* 
+    FROM 
+      t0  
+    LEFT JOIN 
+      (t1 LEFT JOIN t2 ON t2.primary_key=t1.col1)
+    ON 
+      t1.primary_key=t0.col AND t2.col1=t1.col2
+
+  Here we cannot eliminate the "... LEFT JOIN t2 ON ..." part alone because the
+  ON clause of top level outer join has references to table t2. 
+  We can eliminate the entire  "... LEFT JOIN (t1 LEFT JOIN t2) ON .." part,
+  but in order to do that, we must look at both ON expressions.
+  
+  2. ON expressions of parent outer joins are useless.
+  Consider an example:
+
+    SELECT t0.* 
+    FROM
+      t0 
+    LEFT JOIN 
+      (t1 LEFT JOIN t2 ON some_expr)
+    ON
+      t2.primary_key=t1.col  -- (*)
+  
+  Here the uppermost ON expression has a clause that gives us functional
+  dependency of table t2 on t1 and hence could be used to eliminate the
+  "... LEFT JOIN t2 ON..." part.
+  However, we would not actually encounter this situation, because before the
+  table elimination we run simplify_joins(), which, among other things, upon
+  seeing a functional dependency condition like (*) will convert the outer join
+  of
+    
+    "... LEFT JOIN t2 ON ..."
+  
+  into inner join and thus make table elimination not to consider eliminating
+  table t2.
+*/
+
+class Dep_value;
+  class Dep_value_field;
+  class Dep_value_table;
+ 
+
+class Dep_module;
+  class Dep_module_expr;
+  class Dep_module_goal;
+  class Dep_module_key;
+
+class Dep_analysis_context;
+
+
+/*
+  A value, something that can be bound or not bound. One can also iterate over 
+  unbound modules that depend on this value
+*/
+
+class Dep_value : public Sql_alloc
+{
+public:
+  Dep_value(): bound(FALSE) {}
+  virtual ~Dep_value(){} /* purecov: inspected */ /* stop compiler warnings */
+  
+  bool is_bound() { return bound; }
+  void make_bound() { bound= TRUE; }
+
+  /* Iteration over unbound modules that depend on this value */
+  typedef char *Iterator;
+  virtual Iterator init_unbound_modules_iter(char *buf)=0;
+  virtual Dep_module* get_next_unbound_module(Dep_analysis_context *dac,
+                                              Iterator iter) = 0;
+  static const size_t iterator_size;
+protected:
+  bool bound;
+};
+
+
+/*
+  A table field value. There is exactly only one such object for any tblX.fieldY
+  - the field depends on its table and equalities
+  - expressions that use the field are its dependencies
+*/
+
+class Dep_value_field : public Dep_value
+{
+public:
+  Dep_value_field(Dep_value_table *table_arg, Field *field_arg) :
+    table(table_arg), field(field_arg)
+  {}
+
+  Dep_value_table *table; /* Table this field is from */
+  Field *field; /* Field this object is representing */
+  
+  /* Iteration over unbound modules that are our dependencies */
+  Iterator init_unbound_modules_iter(char *buf);
+  Dep_module* get_next_unbound_module(Dep_analysis_context *dac, 
+                                      Iterator iter);
+  
+  void make_unbound_modules_iter_skip_keys(Iterator iter);
+  
+  static const size_t iterator_size;
+private:
+  /* 
+    Field_deps that belong to one table form a linked list, ordered by
+    field_index 
+  */
+  Dep_value_field *next_table_field;
+
+  /*
+    Offset to bits in Dep_analysis_context::expr_deps (see comment to that 
+    member for semantics of the bits).
+  */
+  uint bitmap_offset;
+
+  class Module_iter
+  {
+  public:
+    /* if not null, return this and advance */
+    Dep_module_key *key_dep;
+    /* Otherwise, this and advance */
+    uint equality_no;
+  };
+  friend class Dep_analysis_context;
+  friend class Field_dependency_recorder; 
+  friend class Dep_value_table;
+};
+
+const size_t Dep_value_field::iterator_size=
+  ALIGN_SIZE(sizeof(Dep_value_field::Module_iter));
+
+
+/*
+  A table value. There is one Dep_value_table object for every table that can
+  potentially be eliminated.
+
+  Table becomes bound as soon as some of its unique keys becomes bound
+  Once the table is bound:
+   - all of its fields are bound
+   - its embedding outer join has one less unknown argument
+*/
+
+class Dep_value_table : public Dep_value
+{
+public:
+  Dep_value_table(TABLE *table_arg) : 
+    table(table_arg), fields(NULL), keys(NULL)
+  {}
+  TABLE *table;  /* Table this object is representing */
+  /* Ordered list of fields that belong to this table */
+  Dep_value_field *fields;
+  Dep_module_key *keys; /* Ordered list of Unique keys in this table */
+
+  /* Iteration over unbound modules that are our dependencies */
+  Iterator init_unbound_modules_iter(char *buf);
+  Dep_module* get_next_unbound_module(Dep_analysis_context *dac, 
+                                      Iterator iter);
+  static const size_t iterator_size;
+private:
+  class Module_iter
+  {
+  public:
+    /* Space for field iterator */
+    char buf[Dep_value_field::iterator_size];
+    /* !NULL <=> iterating over depdenent modules of this field */
+    Dep_value_field *field_dep; 
+    bool returned_goal;
+  };
+};
+
+
+const size_t Dep_value_table::iterator_size=
+  ALIGN_SIZE(sizeof(Dep_value_table::Module_iter));
+
+const size_t Dep_value::iterator_size=
+  max(Dep_value_table::iterator_size, Dep_value_field::iterator_size);
+
+
+/*
+  A 'module'. Module has unsatisfied dependencies, number of whose is stored in
+  unbound_args. Modules also can be linked together in a list.
+*/
+
+class Dep_module : public Sql_alloc
+{
+public:
+  virtual ~Dep_module(){}  /* purecov: inspected */ /* stop compiler warnings */
+  
+  /* Mark as bound. Currently is non-virtual and does nothing */
+  void make_bound() {};
+
+  /* 
+    The final module will return TRUE here. When we see that TRUE was returned,
+    that will mean that functional dependency check succeeded.
+  */
+  virtual bool is_final () { return FALSE; }
+
+  /* 
+    Increment number of bound arguments. this is expected to change
+    is_applicable() from false to true after sufficient set of arguments is
+    bound.
+  */
+  void touch() { unbound_args--; }
+  bool is_applicable() { return !test(unbound_args); }
+  
+  /* Iteration over values that */
+  typedef char *Iterator;
+  virtual Iterator init_unbound_values_iter(char *buf)=0;
+  virtual Dep_value* get_next_unbound_value(Dep_analysis_context *dac,
+                                            Iterator iter)=0;
+  static const size_t iterator_size;
+protected:
+  uint unbound_args;
+  
+  Dep_module() : unbound_args(0) {}
+  /* to bump unbound_args when constructing depedendencies */
+  friend class Field_dependency_recorder; 
+  friend class Dep_analysis_context;
+};
+
+
+/*
+  This represents either
+   - "tbl.column= expr" equality dependency, i.e. tbl.column depends on fields
+     used in the expression, or
+   - tbl1.col1=tbl2.col2=... multi-equality.
+*/
+
+class Dep_module_expr : public Dep_module
+{
+public:
+  Dep_value_field *field;
+  Item  *expr;
+  
+  List<Dep_value_field> *mult_equal_fields;
+  /* Used during condition analysis only, similar to KEYUSE::level */
+  uint level;
+
+  Iterator init_unbound_values_iter(char *buf);
+  Dep_value* get_next_unbound_value(Dep_analysis_context *dac, Iterator iter);
+  static const size_t iterator_size;
+private:
+  class Value_iter
+  {
+  public:
+    Dep_value_field *field;
+    List_iterator<Dep_value_field> it;
+  };
+};
+
+const size_t Dep_module_expr::iterator_size=
+  ALIGN_SIZE(sizeof(Dep_module_expr::Value_iter));
+
+
+/*
+  A Unique key module
+   - Unique key has all of its components as arguments
+   - Once unique key is bound, its table value is known
+*/
+
+class Dep_module_key: public Dep_module
+{
+public:
+  Dep_module_key(Dep_value_table *table_arg, uint keyno_arg, uint n_parts_arg) :
+    table(table_arg), keyno(keyno_arg), next_table_key(NULL)
+  {
+    unbound_args= n_parts_arg;
+  }
+  Dep_value_table *table; /* Table this key is from */
+  uint keyno;  /* The index we're representing */
+  /* Unique keys form a linked list, ordered by keyno */
+  Dep_module_key *next_table_key;
+  
+  Iterator init_unbound_values_iter(char *buf);
+  Dep_value* get_next_unbound_value(Dep_analysis_context *dac, Iterator iter);
+  static const size_t iterator_size;
+private:
+  class Value_iter
+  {
+  public:
+    Dep_value_table *table;
+  };
+};
+
+const size_t Dep_module_key::iterator_size= 
+  ALIGN_SIZE(sizeof(Dep_module_key::Value_iter));
+
+const size_t Dep_module::iterator_size=
+  max(Dep_module_expr::iterator_size, Dep_module_key::iterator_size);
+
+
+/*
+  A module that represents outer join that we're trying to eliminate. If we 
+  manage to declare this module to be bound, then outer join can be eliminated.
+*/
+
+class Dep_module_goal: public Dep_module
+{
+public:
+  Dep_module_goal(uint n_children)  
+  {
+    unbound_args= n_children;
+  }
+  bool is_final() { return TRUE; }
+  /* 
+    This is the goal module, so the running wave algorithm should terminate
+    once it sees that this module is applicable and should never try to apply
+    it, hence no use for unbound value iterator implementation.
+  */
+  Iterator init_unbound_values_iter(char *buf)
+  { 
+    DBUG_ASSERT(0); 
+    return NULL;
+  }
+  Dep_value* get_next_unbound_value(Dep_analysis_context *dac, Iterator iter)
+  {
+    DBUG_ASSERT(0); 
+    return NULL;
+  }
+};
+
+
+/*
+  Functional dependency analyzer context
+*/
+class Dep_analysis_context
+{
+public:
+  bool setup_equality_modules_deps(List<Dep_module> *bound_modules);
+  bool run_wave(List<Dep_module> *new_bound_modules);
+
+  /* Tables that we're looking at eliminating */
+  table_map usable_tables;
+  
+  /* Array of equality dependencies */
+  Dep_module_expr *equality_mods;
+  uint n_equality_mods; /* Number of elements in the array */
+  uint n_equality_mods_alloced;
+
+  /* tablenr -> Dep_value_table* mapping. */
+  Dep_value_table *table_deps[MAX_KEY];
+  
+  /* Element for the outer join we're attempting to eliminate */
+  Dep_module_goal *outer_join_dep;
+
+  /* 
+    Bitmap of how expressions depend on bits. Given a Dep_value_field object,
+    one can check bitmap_is_set(expr_deps, field_val->bitmap_offset + expr_no)
+    to see if expression equality_mods[expr_no] depends on the given field.
+  */
+  MY_BITMAP expr_deps;
+  
+  Dep_value_table *create_table_value(TABLE *table);
+  Dep_value_field *get_field_value(Field *field);
+
+#ifndef DBUG_OFF
+  void dbug_print_deps();
+#endif 
+};
+
+
+void eliminate_tables(JOIN *join);
+
+static bool
+eliminate_tables_for_list(JOIN *join, 
+                          List<TABLE_LIST> *join_list,
+                          table_map tables_in_list,
+                          Item *on_expr,
+                          table_map tables_used_elsewhere);
+static
+bool check_func_dependency(JOIN *join, 
+                           table_map dep_tables,
+                           List_iterator<TABLE_LIST> *it, 
+                           TABLE_LIST *oj_tbl,
+                           Item* cond);
+static 
+void build_eq_mods_for_cond(Dep_analysis_context *dac, 
+                            Dep_module_expr **eq_mod, uint *and_level, 
+                            Item *cond);
+static 
+void check_equality(Dep_analysis_context *dac, Dep_module_expr **eq_mod, 
+                    uint and_level, Item_func *cond, Item *left, Item *right);
+static 
+Dep_module_expr *merge_eq_mods(Dep_module_expr *start, 
+                                 Dep_module_expr *new_fields, 
+                                 Dep_module_expr *end, uint and_level);
+static void mark_as_eliminated(JOIN *join, TABLE_LIST *tbl);
+static 
+void add_module_expr(Dep_analysis_context *dac, Dep_module_expr **eq_mod,
+                     uint and_level, Dep_value_field *field_val, Item *right,
+                     List<Dep_value_field>* mult_equal_fields);
+
+
+/*****************************************************************************/
+
+/*
+  Perform table elimination
+
+  SYNOPSIS
+    eliminate_tables()
+      join                   Join to work on
+
+  DESCRIPTION
+    This is the entry point for table elimination. Grep for MODULE INTERFACE
+    section in this file for calling convention.
+
+    The idea behind table elimination is that if we have an outer join:
+   
+      SELECT * FROM t1 LEFT JOIN 
+        (t2 JOIN t3) ON t2.primary_key=t1.col AND 
+                        t3.primary_key=t2.col
+    such that
+
+    1. columns of the inner tables are not used anywhere ouside the outer
+       join (not in WHERE, not in GROUP/ORDER BY clause, not in select list 
+       etc etc), and
+    2. inner side of the outer join is guaranteed to produce at most one
+       record combination for each record combination of outer tables.
+    
+    then the inner side of the outer join can be removed from the query.
+    This is because it will always produce one matching record (either a
+    real match or a NULL-complemented record combination), and since there
+    are no references to columns of the inner tables anywhere, it doesn't
+    matter which record combination it was.
+
+    This function primary handles checking #1. It collects a bitmap of
+    tables that are not used in select list/GROUP BY/ORDER BY/HAVING/etc and
+    thus can possibly be eliminated.
+
+    After this, if #1 is met, the function calls eliminate_tables_for_list()
+    that checks #2.
+  
+  SIDE EFFECTS
+    See the OVERVIEW section at the top of this file.
+
+*/
+
+void eliminate_tables(JOIN *join)
+{
+  THD* thd= join->thd;
+  Item *item;
+  table_map used_tables;
+  DBUG_ENTER("eliminate_tables");
+  
+  DBUG_ASSERT(join->eliminated_tables == 0);
+
+  /* If there are no outer joins, we have nothing to eliminate: */
+  if (!join->outer_join)
+    DBUG_VOID_RETURN;
+
+#ifndef DBUG_OFF
+  if (!optimizer_flag(thd, OPTIMIZER_SWITCH_TABLE_ELIMINATION))
+    DBUG_VOID_RETURN; /* purecov: inspected */
+#endif
+
+  /* Find the tables that are referred to from WHERE/HAVING */
+  used_tables= (join->conds?  join->conds->used_tables() : 0) | 
+               (join->having? join->having->used_tables() : 0);
+  
+  /* Add tables referred to from the select list */
+  List_iterator<Item> it(join->fields_list);
+  while ((item= it++))
+    used_tables |= item->used_tables();
+ 
+  /* Add tables referred to from ORDER BY and GROUP BY lists */
+  ORDER *all_lists[]= { join->order, join->group_list};
+  for (int i=0; i < 2; i++)
+  {
+    for (ORDER *cur_list= all_lists[i]; cur_list; cur_list= cur_list->next)
+      used_tables |= (*(cur_list->item))->used_tables();
+  }
+  
+  if (join->select_lex == &thd->lex->select_lex)
+  {
+
+    /* Multi-table UPDATE: don't eliminate tables referred from SET statement */
+    if (thd->lex->sql_command == SQLCOM_UPDATE_MULTI)
+    {
+      /* Multi-table UPDATE and DELETE: don't eliminate the tables we modify: */
+      used_tables |= thd->table_map_for_update;
+      List_iterator<Item> it2(thd->lex->value_list);
+      while ((item= it2++))
+        used_tables |= item->used_tables();
+    }
+
+    if (thd->lex->sql_command == SQLCOM_DELETE_MULTI)
+    {
+      TABLE_LIST *tbl;
+      for (tbl= (TABLE_LIST*)thd->lex->auxiliary_table_list.first;
+           tbl; tbl= tbl->next_local)
+      {
+        used_tables |= tbl->table->map;
+      }
+    }
+  }
+  
+  table_map all_tables= join->all_tables_map();
+  if (all_tables & ~used_tables)
+  {
+    /* There are some tables that we probably could eliminate. Try it. */
+    eliminate_tables_for_list(join, join->join_list, all_tables, NULL,
+                              used_tables);
+  }
+  DBUG_VOID_RETURN;
+}
+
+
+/*
+  Perform table elimination in a given join list
+
+  SYNOPSIS
+    eliminate_tables_for_list()
+      join                    The join we're working on
+      join_list               Join list to eliminate tables from (and if
+                              on_expr !=NULL, then try eliminating join_list
+                              itself)
+      list_tables             Bitmap of tables embedded in the join_list.
+      on_expr                 ON expression, if the join list is the inner side
+                              of an outer join.
+                              NULL means it's not an outer join but rather a
+                              top-level join list.
+      tables_used_elsewhere   Bitmap of tables that are referred to from
+                              somewhere outside of the join list (e.g.
+                              select list, HAVING, other ON expressions, etc).
+
+  DESCRIPTION
+    Perform table elimination in a given join list:
+    - First, walk through join list members and try doing table elimination for
+      them.
+    - Then, if the join list itself is an inner side of outer join
+      (on_expr!=NULL), then try to eliminate the entire join list.
+
+    See "HANDLING MULTIPLE NESTED OUTER JOINS" section at the top of this file
+    for more detailed description and justification.
+    
+  RETURN
+    TRUE   The entire join list eliminated
+    FALSE  Join list wasn't eliminated (but some of its child outer joins 
+           possibly were)
+*/
+
+static bool
+eliminate_tables_for_list(JOIN *join, List<TABLE_LIST> *join_list,
+                          table_map list_tables, Item *on_expr,
+                          table_map tables_used_elsewhere)
+{
+  TABLE_LIST *tbl;
+  List_iterator<TABLE_LIST> it(*join_list);
+  table_map tables_used_on_left= 0;
+  bool all_eliminated= TRUE;
+
+  while ((tbl= it++))
+  {
+    if (tbl->on_expr)
+    {
+      table_map outside_used_tables= tables_used_elsewhere | 
+                                     tables_used_on_left;
+      if (tbl->nested_join)
+      {
+        /* This is  "... LEFT JOIN (join_nest) ON cond" */
+        if (eliminate_tables_for_list(join,
+                                      &tbl->nested_join->join_list, 
+                                      tbl->nested_join->used_tables, 
+                                      tbl->on_expr,
+                                      outside_used_tables))
+        {
+          mark_as_eliminated(join, tbl);
+        }
+        else
+          all_eliminated= FALSE;
+      }
+      else
+      {
+        /* This is  "... LEFT JOIN tbl ON cond" */
+        if (!(tbl->table->map & outside_used_tables) &&
+            check_func_dependency(join, tbl->table->map, NULL, tbl, 
+                                  tbl->on_expr))
+        {
+          mark_as_eliminated(join, tbl);
+        }
+        else
+          all_eliminated= FALSE;
+      }
+      tables_used_on_left |= tbl->on_expr->used_tables();
+    }
+    else
+    {
+      DBUG_ASSERT(!tbl->nested_join);
+    }
+  }
+
+  /* Try eliminating the nest we're called for */
+  if (all_eliminated && on_expr && !(list_tables & tables_used_elsewhere))
+  {
+    it.rewind();
+    return check_func_dependency(join, list_tables & ~join->eliminated_tables,
+                                 &it, NULL, on_expr);
+  }
+  return FALSE; /* not eliminated */
+}
+
+
+/*
+  Check if given condition makes given set of tables functionally dependent
+
+  SYNOPSIS
+    check_func_dependency()
+      join         Join we're procesing
+      dep_tables   Tables that we check to be functionally dependent (on
+                   everything else)
+      it           Iterator that enumerates these tables, or NULL if we're 
+                   checking one single table and it is specified in oj_tbl
+                   parameter.
+      oj_tbl       NULL, or one single table that we're checking
+      cond         Condition to use to prove functional dependency
+
+  DESCRIPTION
+    Check if we can use given condition to infer that the set of given tables
+    is functionally dependent on everything else.
+
+  RETURN 
+    TRUE  - Yes, functionally dependent
+    FALSE - No, or error
+*/
+
+static
+bool check_func_dependency(JOIN *join,
+                           table_map dep_tables,
+                           List_iterator<TABLE_LIST> *it, 
+                           TABLE_LIST *oj_tbl,
+                           Item* cond)
+{
+  Dep_analysis_context dac;
+  
+  /* 
+    Pre-alloc some Dep_module_expr structures. We don't need this to be
+    guaranteed upper bound.
+  */
+  dac.n_equality_mods_alloced= 
+    join->thd->lex->current_select->max_equal_elems +
+    (join->thd->lex->current_select->cond_count+1)*2 +
+    join->thd->lex->current_select->between_count;
+
+  bzero(dac.table_deps, sizeof(dac.table_deps));
+  if (!(dac.equality_mods= new Dep_module_expr[dac.n_equality_mods_alloced]))
+    return FALSE; /* purecov: inspected */
+
+  Dep_module_expr* last_eq_mod= dac.equality_mods;
+  
+  /* Create Dep_value_table objects for all tables we're trying to eliminate */
+  if (oj_tbl)
+  {
+    if (!dac.create_table_value(oj_tbl->table))
+      return FALSE; /* purecov: inspected */
+  }
+  else
+  {
+    TABLE_LIST *tbl; 
+    while ((tbl= (*it)++))
+    {
+      if (tbl->table && (tbl->table->map & dep_tables))
+      {
+        if (!dac.create_table_value(tbl->table))
+          return FALSE; /* purecov: inspected */
+      }
+    }
+  }
+  dac.usable_tables= dep_tables;
+
+  /*
+    Analyze the the ON expression and create Dep_module_expr objects and
+      Dep_value_field objects for the used fields.
+  */
+  uint and_level=0;
+  build_eq_mods_for_cond(&dac, &last_eq_mod, &and_level, cond);
+  if (!(dac.n_equality_mods= last_eq_mod - dac.equality_mods))
+    return FALSE;  /* No useful conditions */
+
+  List<Dep_module> bound_modules;
+
+  if (!(dac.outer_join_dep= new Dep_module_goal(my_count_bits(dep_tables))) ||
+      dac.setup_equality_modules_deps(&bound_modules))
+  {
+    return FALSE; /* OOM, default to non-dependent */ /* purecov: inspected */
+  }
+  
+  DBUG_EXECUTE("test", dac.dbug_print_deps(); );
+  
+  return dac.run_wave(&bound_modules);
+}
+
+
+/*
+  Running wave functional dependency check algorithm
+
+  SYNOPSIS
+   Dep_analysis_context::run_wave()
+     new_bound_modules  List of bound modules to start the running wave from. 
+                        The list is destroyed during execution
+  
+  DESCRIPTION
+    This function uses running wave algorithm to check if the join nest is
+    functionally-dependent. 
+    We start from provided list of bound modules, and then run the wave across 
+    dependency edges, trying the reach the Dep_module_goal module. If we manage
+    to reach it, then the join nest is functionally-dependent, otherwise it is
+    not.
+
+  RETURN 
+    TRUE   Yes, functionally dependent
+    FALSE  No.
+*/
+
+bool Dep_analysis_context::run_wave(List<Dep_module> *new_bound_modules)
+{
+  List<Dep_value> new_bound_values;
+  
+  Dep_value *value;
+  Dep_module *module;
+
+  while (!new_bound_modules->is_empty())
+  {
+    /*
+      The "wave" is in new_bound_modules list. Iterate over values that can be
+      reached from these modules but are not yet bound, and collect the next
+      wave generation in new_bound_values list.
+    */
+    List_iterator<Dep_module> modules_it(*new_bound_modules);
+    while ((module= modules_it++))
+    {
+      char iter_buf[Dep_module::iterator_size];
+      Dep_module::Iterator iter;
+      iter= module->init_unbound_values_iter(iter_buf);
+      while ((value= module->get_next_unbound_value(this, iter)))
+      {
+        value->make_bound();
+        new_bound_values.push_back(value);
+      }
+    }
+    new_bound_modules->empty();
+    
+    /*
+      Now walk over list of values we've just found to be bound and check which
+      unbound modules can be reached from them. If there are some modules that
+      became bound, collect them in new_bound_modules list.
+    */
+    List_iterator<Dep_value> value_it(new_bound_values);
+    while ((value= value_it++))
+    {
+      char iter_buf[Dep_value::iterator_size];
+      Dep_value::Iterator iter;
+      iter= value->init_unbound_modules_iter(iter_buf);
+      while ((module= value->get_next_unbound_module(this, iter)))
+      {
+        module->touch();
+        if (!module->is_applicable())
+          continue;
+        if (module->is_final())
+          return TRUE; /* Functionally dependent */
+        module->make_bound();
+        new_bound_modules->push_back(module);
+      }
+    }
+    new_bound_values.empty();
+  }
+  return FALSE;
+}
+
+
+/*
+  This is used to analyze expressions in "tbl.col=expr" dependencies so
+  that we can figure out which fields the expression depends on.
+*/
+
+class Field_dependency_recorder : public Field_enumerator
+{
+public:
+  Field_dependency_recorder(Dep_analysis_context *ctx_arg): ctx(ctx_arg)
+  {}
+  
+  void visit_field(Field *field)
+  {
+    Dep_value_table *tbl_dep;
+    if ((tbl_dep= ctx->table_deps[field->table->tablenr]))
+    {
+      for (Dep_value_field *field_dep= tbl_dep->fields; field_dep; 
+           field_dep= field_dep->next_table_field)
+      {
+        if (field->field_index == field_dep->field->field_index)
+        {
+          uint offs= field_dep->bitmap_offset + expr_offset;
+          if (!bitmap_is_set(&ctx->expr_deps, offs))
+            ctx->equality_mods[expr_offset].unbound_args++;
+          bitmap_set_bit(&ctx->expr_deps, offs);
+          return;
+        }
+      }
+      /* 
+        We got here if didn't find this field. It's not a part of 
+        a unique key, and/or there is no field=expr element for it.
+        Bump the dependency anyway, this will signal that this dependency
+        cannot be satisfied.
+      */
+      ctx->equality_mods[expr_offset].unbound_args++;
+    }
+    else
+      visited_other_tables= TRUE;
+  }
+
+  Dep_analysis_context *ctx;
+  /* Offset of the expression we're processing in the dependency bitmap */
+  uint expr_offset;
+
+  bool visited_other_tables;
+};
+
+
+
+
+/*
+  Setup inbound dependency relationships for tbl.col=expr equalities
+ 
+  SYNOPSIS
+    setup_equality_modules_deps()
+      bound_deps_list  Put here modules that were found not to depend on 
+                       any non-bound columns.
+
+  DESCRIPTION
+    Setup inbound dependency relationships for tbl.col=expr equalities:
+      - allocate a bitmap where we store such dependencies
+      - for each "tbl.col=expr" equality, analyze the expr part and find out
+        which fields it refers to and set appropriate dependencies.
+    
+  RETURN
+    FALSE  OK
+    TRUE   Out of memory
+*/
+
+bool Dep_analysis_context::setup_equality_modules_deps(List<Dep_module> 
+                                                       *bound_modules)
+{
+  DBUG_ENTER("setup_equality_modules_deps");
+ 
+  /*
+    Count Dep_value_field objects and assign each of them a unique 
+    bitmap_offset value.
+  */
+  uint offset= 0;
+  for (Dep_value_table **tbl_dep= table_deps; 
+       tbl_dep < table_deps + MAX_TABLES;
+       tbl_dep++)
+  {
+    if (*tbl_dep)
+    {
+      for (Dep_value_field *field_dep= (*tbl_dep)->fields;
+           field_dep;
+           field_dep= field_dep->next_table_field)
+      {
+        field_dep->bitmap_offset= offset;
+        offset += n_equality_mods;
+      }
+    }
+  }
+ 
+  void *buf;
+  if (!(buf= current_thd->alloc(bitmap_buffer_size(offset))) ||
+      bitmap_init(&expr_deps, (my_bitmap_map*)buf, offset, FALSE))
+  {
+    DBUG_RETURN(TRUE); /* purecov: inspected */
+  }
+  bitmap_clear_all(&expr_deps);
+
+  /* 
+    Analyze all "field=expr" dependencies, and have expr_deps encode
+    dependencies of expressions from fields.
+
+    Also collect a linked list of equalities that are bound.
+  */
+  Field_dependency_recorder deps_recorder(this);
+  for (Dep_module_expr *eq_mod= equality_mods; 
+       eq_mod < equality_mods + n_equality_mods;
+       eq_mod++)
+  {
+    deps_recorder.expr_offset= eq_mod - equality_mods;
+    deps_recorder.visited_other_tables= FALSE;
+    eq_mod->unbound_args= 0;
+    
+    if (eq_mod->field)
+    {
+      /* Regular tbl.col=expr(tblX1.col1, tblY1.col2, ...) */
+      eq_mod->expr->walk(&Item::enumerate_field_refs_processor, FALSE, 
+                               (uchar*)&deps_recorder);
+    }
+    else 
+    {
+      /* It's a multi-equality */
+      eq_mod->unbound_args= !test(eq_mod->expr);
+      List_iterator<Dep_value_field> it(*eq_mod->mult_equal_fields);
+      Dep_value_field* field_val;
+      while ((field_val= it++))
+      {
+        uint offs= field_val->bitmap_offset + eq_mod - equality_mods;
+        bitmap_set_bit(&expr_deps, offs);
+      }
+    }
+
+    if (!eq_mod->unbound_args)
+      bound_modules->push_back(eq_mod);
+  }
+
+  DBUG_RETURN(FALSE);
+}
+
+
+/*
+  Ordering that we're using whenever we need to maintain a no-duplicates list
+  of field value objects.
+*/
+
+static 
+int compare_field_values(Dep_value_field *a, Dep_value_field *b, void *unused)
+{
+  uint a_ratio= a->field->table->tablenr*MAX_FIELDS +
+                a->field->field_index;
+
+  uint b_ratio= b->field->table->tablenr*MAX_FIELDS +
+                b->field->field_index;
+  return (a_ratio < b_ratio)? -1 : ((a_ratio == b_ratio)? 0 : 1);
+}
+
+
+/*
+  Produce Dep_module_expr elements for given condition.
+
+  SYNOPSIS
+    build_eq_mods_for_cond()
+      ctx              Table elimination context
+      eq_mod    INOUT  Put produced equality conditions here
+      and_level INOUT  AND-level (like in add_key_fields)
+      cond             Condition to process
+
+  DESCRIPTION
+    Analyze the given condition and produce an array of Dep_module_expr 
+    dependencies from it. The idea of analysis is as follows:
+    There are useful equalities that have form 
+        
+        eliminable_tbl.field = expr      (denote as useful_equality)
+
+    The condition is composed of useful equalities and other conditions that
+    are combined together with AND and OR operators. We process the condition
+    in recursive fashion according to these basic rules:
+
+      useful_equality1 AND useful_equality2 -> make array of two 
+                                               Dep_module_expr objects
+
+      useful_equality AND other_cond -> discard other_cond
+      
+      useful_equality OR other_cond -> discard everything
+      
+      useful_equality1 OR useful_equality2 -> check if both sides of OR are the
+                                              same equality. If yes, that's the
+                                              result, otherwise discard 
+                                              everything.
+
+    The rules are used to map the condition into an array Dep_module_expr
+    elements. The array will specify functional dependencies that logically 
+    follow from the condition.
+
+  SEE ALSO
+    This function is modeled after add_key_fields()
+*/
+
+static 
+void build_eq_mods_for_cond(Dep_analysis_context *ctx, 
+                            Dep_module_expr **eq_mod,
+                            uint *and_level, Item *cond)
+{
+  if (cond->type() == Item_func::COND_ITEM)
+  {
+    List_iterator_fast<Item> li(*((Item_cond*) cond)->argument_list());
+    uint orig_offset= *eq_mod - ctx->equality_mods;
+    
+    /* AND/OR */
+    if (((Item_cond*) cond)->functype() == Item_func::COND_AND_FUNC)
+    {
+      Item *item;
+      while ((item=li++))
+        build_eq_mods_for_cond(ctx, eq_mod, and_level, item);
+
+      for (Dep_module_expr *mod_exp= ctx->equality_mods + orig_offset;
+           mod_exp != *eq_mod ; mod_exp++)
+      {
+        mod_exp->level= *and_level;
+      }
+    }
+    else
+    {
+      Item *item;
+      (*and_level)++;
+      build_eq_mods_for_cond(ctx, eq_mod, and_level, li++);
+      while ((item=li++))
+      {
+        Dep_module_expr *start_key_fields= *eq_mod;
+        (*and_level)++;
+        build_eq_mods_for_cond(ctx, eq_mod, and_level, item);
+        *eq_mod= merge_eq_mods(ctx->equality_mods + orig_offset, 
+                               start_key_fields, *eq_mod,
+                               ++(*and_level));
+      }
+    }
+    return;
+  }
+
+  if (cond->type() != Item::FUNC_ITEM)
+    return;
+
+  Item_func *cond_func= (Item_func*) cond;
+  Item **args= cond_func->arguments();
+
+  switch (cond_func->functype()) {
+  case Item_func::BETWEEN:
+  {
+    Item *fld;
+    if (!((Item_func_between*)cond)->negated &&
+        (fld= args[0]->real_item())->type() == Item::FIELD_ITEM &&
+        args[1]->eq(args[2], ((Item_field*)fld)->field->binary()))
+    {
+      check_equality(ctx, eq_mod, *and_level, cond_func, args[0], args[1]);
+      check_equality(ctx, eq_mod, *and_level, cond_func, args[1], args[0]);
+    }
+    break;
+  }
+  case Item_func::EQ_FUNC:
+  case Item_func::EQUAL_FUNC:
+  {
+    check_equality(ctx, eq_mod, *and_level, cond_func, args[0], args[1]);
+    check_equality(ctx, eq_mod, *and_level, cond_func, args[1], args[0]);
+    break;
+  }
+  case Item_func::ISNULL_FUNC:
+  {
+    Item *tmp=new Item_null;
+    if (tmp)
+      check_equality(ctx, eq_mod, *and_level, cond_func, args[0], tmp);
+    break;
+  }
+  case Item_func::MULT_EQUAL_FUNC:
+  {
+    /*
+      The condition is a 
+
+        tbl1.field1 = tbl2.field2 = tbl3.field3 [= const_expr]
+
+      multiple-equality. Do two things:
+       - Collect List<Dep_value_field> of tblX.colY where tblX is one of the
+         tables we're trying to eliminate.
+       - rembember if there was a bound value, either const_expr or tblY.colZ
+         swher tblY is not a table that we're trying to eliminate.
+      Store all collected information in a Dep_module_expr object.
+    */
+    Item_equal *item_equal= (Item_equal*)cond;
+    List<Dep_value_field> *fvl;
+    if (!(fvl= new List<Dep_value_field>))
+      break; /* purecov: inspected */
+
+    Item_equal_iterator it(*item_equal);
+    Item_field *item;
+    Item *bound_item= item_equal->get_const();
+    while ((item= it++))
+    {
+      if ((item->used_tables() & ctx->usable_tables))
+      {
+        Dep_value_field *field_val;
+        if ((field_val= ctx->get_field_value(item->field)))
+          fvl->push_back(field_val);
+      }
+      else
+      {
+        if (!bound_item)
+          bound_item= item;
+      }
+    }
+    exchange_sort<Dep_value_field>(fvl, compare_field_values, NULL);
+    add_module_expr(ctx, eq_mod, *and_level, NULL, bound_item, fvl);
+    break;
+  }
+  default:
+    break;
+  }
+}
+
+
+/*
+  Perform an OR operation on two (adjacent) Dep_module_expr arrays.
+
+  SYNOPSIS
+     merge_eq_mods()
+       start        Start of left OR-part
+       new_fields   Start of right OR-part
+       end          End of right OR-part
+       and_level    AND-level (like in add_key_fields)
+
+  DESCRIPTION
+  This function is invoked for two adjacent arrays of Dep_module_expr elements:
+
+                      $LEFT_PART             $RIGHT_PART
+             +-----------------------+-----------------------+
+            start                new_fields                 end
+         
+  The goal is to produce an array which would correspond to the combined 
+  
+    $LEFT_PART OR $RIGHT_PART
+  
+  condition. This is achieved as follows: First, we apply distrubutive law:
+  
+    (fdep_A_1 AND fdep_A_2 AND ...)  OR  (fdep_B_1 AND fdep_B_2 AND ...) =
+
+     = AND_ij (fdep_A_[i] OR fdep_B_[j])
+  
+  Then we walk over the obtained "fdep_A_[i] OR fdep_B_[j]" pairs, and 
+   - Discard those that that have left and right part referring to different
+     columns. We can't infer anything useful from "col1=expr1 OR col2=expr2".
+   - When left and right parts refer to the same column,  we check if they are 
+     essentially the same. 
+     = If they are the same, we keep one copy 
+       "t.col=expr OR t.col=expr"  -> "t.col=expr 
+     = if they are different , then we discard both
+      "t.col=expr1 OR t.col=expr2" -> (nothing useful)
+
+  (no per-table or for-index FUNC_DEPS exist yet at this phase).
+
+  See also merge_key_fields().
+
+  RETURN 
+    End of the result array
+*/
+
+static 
+Dep_module_expr *merge_eq_mods(Dep_module_expr *start, 
+                               Dep_module_expr *new_fields,
+                               Dep_module_expr *end, uint and_level)
+{
+  if (start == new_fields)
+    return start;  /*  (nothing) OR (...) -> (nothing) */
+  if (new_fields == end)
+    return start;  /*  (...) OR (nothing) -> (nothing) */
+
+  Dep_module_expr *first_free= new_fields;
+
+  for (; new_fields != end ; new_fields++)
+  {
+    for (Dep_module_expr *old=start ; old != first_free ; old++)
+    {
+      if (old->field == new_fields->field)
+      {
+        if (!old->field)
+        {
+          /*
+            OR-ing two multiple equalities. We must compute an intersection of
+            used fields, and check the constants according to these rules:
+
+              a=b=c=d  OR a=c=e=f   ->  a=c  (compute intersection)
+              a=const1 OR a=b       ->  (nothing)
+              a=const1 OR a=const1  ->  a=const1 
+              a=const1 OR a=const2  ->  (nothing)
+            
+            If we're performing an OR operation over multiple equalities, e.g.
+
+              (a=b=c AND p=q) OR (a=b AND v=z)
+            
+            then we'll need to try combining each equality with each. ANDed
+            equalities are guaranteed to be disjoint, so we'll only get one
+            hit.
+          */
+          Field *eq_field= old->mult_equal_fields->head()->field;
+          if (old->expr && new_fields->expr &&
+              old->expr->eq_by_collation(new_fields->expr, eq_field->binary(),
+                                         eq_field->charset()))
+          {
+            /* Ok, keep */
+          }
+          else
+          {
+            /* no single constant/bound item. */
+            old->expr= NULL;
+          }
+           
+          List <Dep_value_field> *fv;
+          if (!(fv= new List<Dep_value_field>))
+            break; /* purecov: inspected */
+
+          List_iterator<Dep_value_field> it1(*old->mult_equal_fields);
+          List_iterator<Dep_value_field> it2(*new_fields->mult_equal_fields);
+          Dep_value_field *lfield= it1++;
+          Dep_value_field *rfield= it2++;
+          /* Intersect two ordered lists */
+          while (lfield && rfield)
+          {
+            if (lfield == rfield)
+            {
+              fv->push_back(lfield);
+              lfield=it1++;
+              rfield=it2++;
+            }
+            else
+            {
+              if (compare_field_values(lfield, rfield, NULL) < 0)
+                lfield= it1++;
+              else
+                rfield= it2++;
+            }
+          }
+
+          if (fv->elements + test(old->expr) > 1)
+          {
+            old->mult_equal_fields= fv;
+            old->level= and_level;
+          }
+        }
+        else if (!new_fields->expr->const_item())
+        {
+          /*
+            If the value matches, we can use the key reference.
+            If not, we keep it until we have examined all new values
+          */
+          if (old->expr->eq(new_fields->expr, 
+                            old->field->field->binary()))
+          {
+            old->level= and_level;
+          }
+        }
+        else if (old->expr->eq_by_collation(new_fields->expr,
+                                            old->field->field->binary(),
+                                            old->field->field->charset()))
+        {
+          old->level= and_level;
+        }
+        else
+        {
+          /* The expressions are different. */
+          if (old == --first_free)                // If last item
+            break;
+          *old= *first_free;                        // Remove old value
+          old--;                                // Retry this value
+        }
+      }
+    }
+  }
+
+  /* 
+    Ok, the results are within the [start, first_free) range, and the useful
+    elements have level==and_level. Now, remove all unusable elements:
+  */
+  for (Dep_module_expr *old=start ; old != first_free ;)
+  {
+    if (old->level != and_level)
+    {                                                // Not used in all levels
+      if (old == --first_free)
+        break;
+      *old= *first_free;                        // Remove old value
+      continue;
+    }
+    old++;
+  }
+  return first_free;
+}
+
+
+/*
+  Add an Dep_module_expr element for left=right condition
+
+  SYNOPSIS
+    check_equality()
+      fda               Table elimination context
+      eq_mod     INOUT  Store created Dep_module_expr here and increment ptr if
+                        you do so
+      and_level         AND-level (like in add_key_fields)
+      cond              Condition we've inferred the left=right equality from.
+      left              Left expression
+      right             Right expression
+      usable_tables     Create Dep_module_expr only if Left_expression's table 
+                        belongs to this set.
+
+  DESCRIPTION 
+    Check if the passed left=right equality is such that 
+     - 'left' is an Item_field referring to a field in a table we're checking
+       to be functionally depdendent,
+     - the equality allows to conclude that 'left' expression is functionally 
+       dependent on the 'right',
+    and if so, create an Dep_module_expr object.
+*/
+
+static 
+void check_equality(Dep_analysis_context *ctx, Dep_module_expr **eq_mod,
+                    uint and_level, Item_func *cond, Item *left, Item *right)
+{
+  if ((left->used_tables() & ctx->usable_tables) &&
+      !(right->used_tables() & RAND_TABLE_BIT) &&
+      left->real_item()->type() == Item::FIELD_ITEM)
+  {
+    Field *field= ((Item_field*)left->real_item())->field;
+    if (field->result_type() == STRING_RESULT)
+    {
+      if (right->result_type() != STRING_RESULT)
+      {
+        if (field->cmp_type() != right->result_type())
+          return;
+      }
+      else
+      {
+        /*
+          We can't assume there's a functional dependency if the effective
+          collation of the operation differ from the field collation.
+        */
+        if (field->cmp_type() == STRING_RESULT &&
+            ((Field_str*)field)->charset() != cond->compare_collation())
+          return;
+      }
+    }
+    Dep_value_field *field_val;
+    if ((field_val= ctx->get_field_value(field)))
+      add_module_expr(ctx, eq_mod, and_level, field_val, right, NULL);
+  }
+}
+
+
+/* 
+  Add a Dep_module_expr object with the specified parameters. 
+  
+  DESCRIPTION
+    Add a Dep_module_expr object with the specified parameters. Re-allocate
+    the ctx->equality_mods array if it has no space left.
+*/
+
+static 
+void add_module_expr(Dep_analysis_context *ctx, Dep_module_expr **eq_mod,
+                     uint and_level, Dep_value_field *field_val, 
+                     Item *right, List<Dep_value_field>* mult_equal_fields)
+{
+  if (*eq_mod == ctx->equality_mods + ctx->n_equality_mods_alloced)
+  {
+    /* 
+      We've filled the entire equality_mods array. Replace it with a bigger
+      one. We do it somewhat inefficiently but it doesn't matter.
+    */
+    /* purecov: begin inspected */
+    Dep_module_expr *new_arr;
+    if (!(new_arr= new Dep_module_expr[ctx->n_equality_mods_alloced *2]))
+      return;
+    ctx->n_equality_mods_alloced *= 2;
+    for (int i= 0; i < *eq_mod - ctx->equality_mods; i++)
+      new_arr[i]= ctx->equality_mods[i];
+
+    ctx->equality_mods= new_arr;
+    *eq_mod= new_arr + (*eq_mod - ctx->equality_mods);
+    /* purecov: end */
+  }
+
+  (*eq_mod)->field= field_val;
+  (*eq_mod)->expr= right;
+  (*eq_mod)->level= and_level;
+  (*eq_mod)->mult_equal_fields= mult_equal_fields;
+  (*eq_mod)++;
+}
+
+
+/*
+  Create a Dep_value_table object for the given table
+
+  SYNOPSIS
+    Dep_analysis_context::create_table_value()
+      table  Table to create object for
+
+  DESCRIPTION
+    Create a Dep_value_table object for the given table. Also create
+    Dep_module_key objects for all unique keys in the table.
+
+  RETURN
+    Created table value object
+    NULL if out of memory
+*/
+
+Dep_value_table *Dep_analysis_context::create_table_value(TABLE *table)
+{
+  Dep_value_table *tbl_dep;
+  if (!(tbl_dep= new Dep_value_table(table)))
+    return NULL; /* purecov: inspected */
+
+  Dep_module_key **key_list= &(tbl_dep->keys);
+  /* Add dependencies for unique keys */
+  for (uint i=0; i < table->s->keys; i++)
+  {
+    KEY *key= table->key_info + i; 
+    if ((key->flags & (HA_NOSAME | HA_END_SPACE_KEY)) == HA_NOSAME)
+    {
+      Dep_module_key *key_dep;
+      if (!(key_dep= new Dep_module_key(tbl_dep, i, key->key_parts)))
+        return NULL;
+      *key_list= key_dep;
+      key_list= &(key_dep->next_table_key);
+    }
+  }
+  return table_deps[table->tablenr]= tbl_dep;
+}
+
+
+/* 
+  Get a Dep_value_field object for the given field, creating it if necessary
+
+  SYNOPSIS
+   Dep_analysis_context::get_field_value()
+      field  Field to create object for
+        
+  DESCRIPTION
+    Get a Dep_value_field object for the given field. First, we search for it 
+    in the list of Dep_value_field objects we have already created. If we don't 
+    find it, we create a new Dep_value_field and put it into the list of field
+    objects we have for the table.
+
+  RETURN
+    Created field value object
+    NULL if out of memory
+*/
+
+Dep_value_field *Dep_analysis_context::get_field_value(Field *field)
+{
+  TABLE *table= field->table;
+  Dep_value_table *tbl_dep= table_deps[table->tablenr];
+
+  /* Try finding the field in field list */
+  Dep_value_field **pfield= &(tbl_dep->fields);
+  while (*pfield && (*pfield)->field->field_index < field->field_index)
+  {
+    pfield= &((*pfield)->next_table_field);
+  }
+  if (*pfield && (*pfield)->field->field_index == field->field_index)
+    return *pfield;
+  
+  /* Create the field and insert it in the list */
+  Dep_value_field *new_field= new Dep_value_field(tbl_dep, field);
+  new_field->next_table_field= *pfield;
+  *pfield= new_field;
+
+  return new_field;
+}
+
+
+/* 
+  Iteration over unbound modules that are our dependencies.
+  for those we have:
+    - dependendencies of our fields
+    - outer join we're in 
+*/
+char *Dep_value_table::init_unbound_modules_iter(char *buf)
+{
+  Module_iter *iter= ALIGN_PTR(my_ptrdiff_t(buf), Module_iter);
+  iter->field_dep= fields;
+  if (fields)
+  {
+    fields->init_unbound_modules_iter(iter->buf);
+    fields->make_unbound_modules_iter_skip_keys(iter->buf);
+  }
+  iter->returned_goal= FALSE;
+  return (char*)iter;
+}
+
+
+Dep_module* 
+Dep_value_table::get_next_unbound_module(Dep_analysis_context *dac,
+                                         char *iter)
+{
+  Module_iter *di= (Module_iter*)iter;
+  while (di->field_dep)
+  {
+    Dep_module *res;
+    if ((res= di->field_dep->get_next_unbound_module(dac, di->buf)))
+      return res;
+    if ((di->field_dep= di->field_dep->next_table_field))
+    {
+      char *field_iter= ((Module_iter*)iter)->buf;
+      di->field_dep->init_unbound_modules_iter(field_iter);
+      di->field_dep->make_unbound_modules_iter_skip_keys(field_iter);
+    }
+  }
+  
+  if (!di->returned_goal)
+  {
+    di->returned_goal= TRUE;
+    return dac->outer_join_dep;
+  }
+  return NULL;
+}
+
+
+char *Dep_module_expr::init_unbound_values_iter(char *buf)
+{
+  Value_iter *iter= ALIGN_PTR(my_ptrdiff_t(buf), Value_iter);
+  iter->field= field;
+  if (!field)
+  {
+    new (&iter->it) List_iterator<Dep_value_field>(*mult_equal_fields);
+  }
+  return (char*)iter;
+}
+
+
+Dep_value* Dep_module_expr::get_next_unbound_value(Dep_analysis_context *dac,
+                                                   char *buf)
+{
+  Dep_value *res;
+  if (field)
+  {
+    res= ((Value_iter*)buf)->field;
+    ((Value_iter*)buf)->field= NULL;
+    return (!res || res->is_bound())? NULL : res;
+  }
+  else
+  {
+    while ((res= ((Value_iter*)buf)->it++))
+    {
+      if (!res->is_bound())
+        return res;
+    }
+    return NULL;
+  }
+}
+
+
+char *Dep_module_key::init_unbound_values_iter(char *buf)
+{
+  Value_iter *iter= ALIGN_PTR(my_ptrdiff_t(buf), Value_iter);
+  iter->table= table;
+  return (char*)iter;
+}
+
+
+Dep_value* Dep_module_key::get_next_unbound_value(Dep_analysis_context *dac,
+                                                  Dep_module::Iterator iter)
+{
+  Dep_value* res= ((Value_iter*)iter)->table;
+  ((Value_iter*)iter)->table= NULL;
+  return res;
+}
+
+
+Dep_value::Iterator Dep_value_field::init_unbound_modules_iter(char *buf)
+{
+  Module_iter *iter= ALIGN_PTR(my_ptrdiff_t(buf), Module_iter);
+  iter->key_dep= table->keys;
+  iter->equality_no= 0;
+  return (char*)iter;
+}
+
+
+void 
+Dep_value_field::make_unbound_modules_iter_skip_keys(Dep_value::Iterator iter)
+{
+  ((Module_iter*)iter)->key_dep= NULL;
+}
+
+
+Dep_module* Dep_value_field::get_next_unbound_module(Dep_analysis_context *dac,
+                                                     Dep_value::Iterator iter)
+{
+  Module_iter *di= (Module_iter*)iter;
+  Dep_module_key *key_dep= di->key_dep;
+  
+  /* 
+    First, enumerate all unique keys that are 
+    - not yet applicable
+    - have this field as a part of them
+  */
+  while (key_dep && (key_dep->is_applicable() ||
+         !field->part_of_key.is_set(key_dep->keyno)))
+  {
+    key_dep= key_dep->next_table_key;
+  }
+
+  if (key_dep)
+  {
+    di->key_dep= key_dep->next_table_key;
+    return key_dep;
+  }
+  else 
+    di->key_dep= NULL;
+  
+  /*
+    Then walk through [multi]equalities and find those that
+     - depend on this field
+     - and are not bound yet.
+  */
+  uint eq_no= di->equality_no;
+  while (eq_no < dac->n_equality_mods && 
+         (!bitmap_is_set(&dac->expr_deps, bitmap_offset + eq_no) ||
+         dac->equality_mods[eq_no].is_applicable()))
+  {
+    eq_no++;
+  }
+  
+  if (eq_no < dac->n_equality_mods)
+  {
+    di->equality_no= eq_no+1;
+    return &dac->equality_mods[eq_no];
+  }
+  return NULL;
+}
+
+
+/* 
+  Mark one table or the whole join nest as eliminated.
+*/
+
+static void mark_as_eliminated(JOIN *join, TABLE_LIST *tbl)
+{
+  TABLE *table;
+  /*
+    NOTE: there are TABLE_LIST object that have
+    tbl->table!= NULL && tbl->nested_join!=NULL and 
+    tbl->table == tbl->nested_join->join_list->element(..)->table
+  */
+  if (tbl->nested_join)
+  {
+    TABLE_LIST *child;
+    List_iterator<TABLE_LIST> it(tbl->nested_join->join_list);
+    while ((child= it++))
+      mark_as_eliminated(join, child);
+  }
+  else if ((table= tbl->table))
+  {
+    JOIN_TAB *tab= tbl->table->reginfo.join_tab;
+    if (!(join->const_table_map & tab->table->map))
+    {
+      DBUG_PRINT("info", ("Eliminated table %s", table->alias));
+      tab->type= JT_CONST;
+      join->eliminated_tables |= table->map;
+      join->const_table_map|= table->map;
+      set_position(join, join->const_tables++, tab, (KEYUSE*)0);
+    }
+  }
+
+  if (tbl->on_expr)
+    tbl->on_expr->walk(&Item::mark_as_eliminated_processor, FALSE, NULL);
+}
+
+
+#ifndef DBUG_OFF
+/* purecov: begin inspected */
+void Dep_analysis_context::dbug_print_deps()
+{
+  DBUG_ENTER("dbug_print_deps");
+  DBUG_LOCK_FILE;
+  
+  fprintf(DBUG_FILE,"deps {\n");
+  
+  /* Start with printing equalities */
+  for (Dep_module_expr *eq_mod= equality_mods; 
+       eq_mod != equality_mods + n_equality_mods; eq_mod++)
+  {
+    char buf[128];
+    String str(buf, sizeof(buf), &my_charset_bin);
+    str.length(0);
+    eq_mod->expr->print(&str, QT_ORDINARY);
+    if (eq_mod->field)
+    {
+      fprintf(DBUG_FILE, "  equality%ld: %s -> %s.%s\n", 
+              (long)(eq_mod - equality_mods),
+              str.c_ptr(),
+              eq_mod->field->table->table->alias,
+              eq_mod->field->field->field_name);
+    }
+    else
+    {
+      fprintf(DBUG_FILE, "  equality%ld: multi-equality", 
+              (long)(eq_mod - equality_mods));
+    }
+  }
+  fprintf(DBUG_FILE,"\n");
+
+  /* Then tables and their fields */
+  for (uint i=0; i < MAX_TABLES; i++)
+  {
+    Dep_value_table *table_dep;
+    if ((table_dep= table_deps[i]))
+    {
+      /* Print table */
+      fprintf(DBUG_FILE, "  table %s\n", table_dep->table->alias);
+      /* Print fields */
+      for (Dep_value_field *field_dep= table_dep->fields; field_dep; 
+           field_dep= field_dep->next_table_field)
+      {
+        fprintf(DBUG_FILE, "    field %s.%s ->", table_dep->table->alias,
+                field_dep->field->field_name);
+        uint ofs= field_dep->bitmap_offset;
+        for (uint bit= ofs; bit < ofs + n_equality_mods; bit++)
+        {
+          if (bitmap_is_set(&expr_deps, bit))
+            fprintf(DBUG_FILE, " equality%d ", bit - ofs);
+        }
+        fprintf(DBUG_FILE, "\n");
+      }
+    }
+  }
+  fprintf(DBUG_FILE,"\n}\n");
+  DBUG_UNLOCK_FILE;
+  DBUG_VOID_RETURN;
+}
+/* purecov: end */
+
+#endif 
+/**
+  @} (end of group Table_Elimination)
+*/
+
diff --git a/sql/set_var.cc b/sql/set_var.cc
index 3a19a4849d9..113e22c6aaa 100644
--- a/sql/set_var.cc
+++ b/sql/set_var.cc
@@ -147,6 +147,7 @@ static bool sys_update_general_log_path(THD *thd, set_var * var);
 static void sys_default_general_log_path(THD *thd, enum_var_type type);
 static bool sys_update_slow_log_path(THD *thd, set_var * var);
 static void sys_default_slow_log_path(THD *thd, enum_var_type type);
+static void fix_sys_log_slow_filter(THD *thd, enum_var_type);
 
 /*
   Variable definition list
@@ -359,6 +360,9 @@ static sys_var_bool_ptr
 static sys_var_thd_ulong	sys_log_warnings(&vars, "log_warnings", &SV::log_warnings);
 static sys_var_microseconds	sys_var_long_query_time(&vars, "long_query_time",
                                                         &SV::long_query_time);
+static sys_var_microseconds	sys_var_long_query_time2(&vars,
+                                                         "log_slow_time",
+                                                         &SV::long_query_time);
 static sys_var_thd_bool	sys_low_priority_updates(&vars, "low_priority_updates",
 						 &SV::low_priority_updates,
 						 fix_low_priority_updates);
@@ -852,6 +856,20 @@ sys_var_thd_ulong               sys_group_concat_max_len(&vars, "group_concat_ma
 sys_var_thd_time_zone sys_time_zone(&vars, "time_zone",
                                     sys_var::SESSION_VARIABLE_IN_BINLOG);
 
+/* Unique variables for MariaDB */
+static sys_var_thd_ulong  sys_log_slow_rate_limit(&vars,
+                                                  "log_slow_rate_limit",
+                                                  &SV::log_slow_rate_limit);
+static sys_var_thd_set sys_log_slow_filter(&vars, "log_slow_filter",
+                                           &SV::log_slow_filter,
+                                           &log_slow_filter_typelib,
+                                           QPLAN_VISIBLE_MASK,
+                                           fix_sys_log_slow_filter);
+static sys_var_thd_set sys_log_slow_verbosity(&vars,
+                                              "log_slow_verbosity",
+                                              &SV::log_slow_verbosity,
+                                              &log_slow_verbosity_typelib);
+
 /* Global read-only variable containing hostname */
 static sys_var_const_str        sys_hostname(&vars, "hostname", glob_hostname);
 
@@ -1850,11 +1868,17 @@ err:
   return 1;
 }
 
+/**
+   Check vality of set
+
+   Note that this sets 'save_result.ulong_value' for the update function,
+   which means that we don't need a separate sys_var::update() function
+*/
 
 bool sys_var::check_set(THD *thd, set_var *var, TYPELIB *enum_names)
 {
   bool not_used;
-  char buff[STRING_BUFFER_USUAL_SIZE], *error= 0;
+  char buff[256], *error= 0;
   uint error_len= 0;
   String str(buff, sizeof(buff) - 1, system_charset_info), *res;
 
@@ -1866,8 +1890,7 @@ bool sys_var::check_set(THD *thd, set_var *var, TYPELIB *enum_names)
       goto err;
     }
 
-    if (!m_allow_empty_value &&
-        res->length() == 0)
+    if (!m_allow_empty_value && res->length() == 0)
     {
       buff[0]= 0;
       goto err;
@@ -1889,8 +1912,7 @@ bool sys_var::check_set(THD *thd, set_var *var, TYPELIB *enum_names)
   {
     ulonglong tmp= var->value->val_int();
 
-    if (!m_allow_empty_value &&
-        tmp == 0)
+    if (!m_allow_empty_value && tmp == 0)
     {
       buff[0]= '0';
       buff[1]= 0;
@@ -1917,6 +1939,49 @@ err:
 }
 
 
+/**
+  Make string representation of set
+
+  @param[in]  thd    thread handler
+  @param[in]  val    sql_mode value
+  @param[in]  names  names for the different bits
+  @param[out] rep    Result string
+
+  @return
+    0 ok
+    1 end of memory
+*/
+
+bool sys_var::make_set(THD *thd, ulonglong val, TYPELIB *names,
+                       LEX_STRING *rep)
+{
+  /* Strings for typelib may be big; This is reallocated on demand */
+  char buff[256];
+  String tmp(buff, sizeof(buff) - 1, &my_charset_latin1);
+  bool error= 0;
+
+  tmp.length(0);
+  for (uint i= 0; val; val>>= 1, i++)
+  {
+    if (val & 1)
+    {
+      error|= tmp.append(names->type_names[i],
+                 names->type_lengths[i]);
+      error|= tmp.append(',');
+    }
+  }
+
+  if (tmp.length())
+    tmp.length(tmp.length() - 1); /* trim the trailing comma */
+
+  /* Allocate temporary copy of string */
+  if (!(rep->str= thd->strmake(tmp.ptr(), tmp.length())))
+    error= 1;
+  rep->length= tmp.length();
+  return error;                   /* Error in case of out of memory */
+}
+
+
 CHARSET_INFO *sys_var::charset(THD *thd)
 {
   return is_os_charset ? thd->variables.character_set_filesystem : 
@@ -1952,6 +2017,16 @@ uchar *sys_var_thd_enum::value_ptr(THD *thd, enum_var_type type,
   return (uchar*) enum_names->type_names[tmp];
 }
 
+uchar *sys_var_thd_set::value_ptr(THD *thd, enum_var_type type,
+                                  LEX_STRING *base)
+{
+  LEX_STRING sql_mode;
+  ulong val= ((type == OPT_GLOBAL) ? global_system_variables.*offset :
+              thd->variables.*offset);
+  (void) make_set(thd, val & visible_value_mask, enum_names, &sql_mode);
+  return (uchar *) sql_mode.str;
+}
+
 bool sys_var_thd_bit::check(THD *thd, set_var *var)
 {
   return (check_enum(thd, var, &bool_typelib) ||
@@ -3700,6 +3775,24 @@ int set_var_password::update(THD *thd)
 }
 
 /****************************************************************************
+ Functions to handle log_slow_filter
+****************************************************************************/
+  
+/* Ensure that the proper bits are set for easy test of logging */
+static void fix_sys_log_slow_filter(THD *thd, enum_var_type type)
+{
+  /* Maintain everything with filters */
+  opt_log_slow_admin_statements= 1;
+  if (type == OPT_GLOBAL)
+    global_system_variables.log_slow_filter=
+      fix_log_slow_filter(global_system_variables.log_slow_filter);
+  else
+    thd->variables.log_slow_filter=
+      fix_log_slow_filter(thd->variables.log_slow_filter);
+}
+
+
+/****************************************************************************
  Functions to handle table_type
 ****************************************************************************/
 
@@ -3810,67 +3903,6 @@ bool sys_var_thd_table_type::update(THD *thd, set_var *var)
  Functions to handle sql_mode
 ****************************************************************************/
 
-/**
-  Make string representation of mode.
-
-  @param[in]  thd    thread handler
-  @param[in]  val    sql_mode value
-  @param[out] len    pointer on length of string
-
-  @return
-    pointer to string with sql_mode representation
-*/
-
-bool
-sys_var_thd_sql_mode::
-symbolic_mode_representation(THD *thd, ulonglong val, LEX_STRING *rep)
-{
-  char buff[STRING_BUFFER_USUAL_SIZE*8];
-  String tmp(buff, sizeof(buff) - 1, &my_charset_latin1);
-
-  tmp.length(0);
-
-  for (uint i= 0; val; val>>= 1, i++)
-  {
-    if (val & 1)
-    {
-      tmp.append(sql_mode_typelib.type_names[i],
-                 sql_mode_typelib.type_lengths[i]);
-      tmp.append(',');
-    }
-  }
-
-  if (tmp.length())
-    tmp.length(tmp.length() - 1); /* trim the trailing comma */
-
-  rep->str= thd->strmake(tmp.ptr(), tmp.length());
-
-  rep->length= rep->str ? tmp.length() : 0;
-
-  return rep->length != tmp.length();
-}
-
-
-uchar *sys_var_thd_sql_mode::value_ptr(THD *thd, enum_var_type type,
-				      LEX_STRING *base)
-{
-  LEX_STRING sql_mode;
-  ulonglong val= ((type == OPT_GLOBAL) ? global_system_variables.*offset :
-                  thd->variables.*offset);
-  (void) symbolic_mode_representation(thd, val, &sql_mode);
-  return (uchar *) sql_mode.str;
-}
-
-
-void sys_var_thd_sql_mode::set_default(THD *thd, enum_var_type type)
-{
-  if (type == OPT_GLOBAL)
-    global_system_variables.*offset= 0;
-  else
-    thd->variables.*offset= global_system_variables.*offset;
-}
-
-
 void fix_sql_mode_var(THD *thd, enum_var_type type)
 {
   if (type == OPT_GLOBAL)
diff --git a/sql/set_var.h b/sql/set_var.h
index 10e6e0f9c35..f2c7c0ba30f 100644
--- a/sql/set_var.h
+++ b/sql/set_var.h
@@ -98,6 +98,8 @@ public:
   virtual bool check(THD *thd, set_var *var);
   bool check_enum(THD *thd, set_var *var, const TYPELIB *enum_names);
   bool check_set(THD *thd, set_var *var, TYPELIB *enum_names);
+  static bool make_set(THD *thd, ulonglong sql_mode, TYPELIB *names,
+                       LEX_STRING *rep);
   bool is_written_to_binlog(enum_var_type type)
   {
     return (type == OPT_SESSION || type == OPT_DEFAULT) &&
@@ -532,6 +534,25 @@ public:
 };
 
 
+class sys_var_thd_set :public sys_var_thd_enum
+{
+  ulong visible_value_mask; /* Mask away internal bits */
+public:
+  sys_var_thd_set(sys_var_chain *chain, const char *name_arg, 
+                  ulong SV::*offset_arg, TYPELIB *typelib,
+                  ulong value_mask= ~ (ulong) 0,
+                  sys_after_update_func func= NULL)
+    :sys_var_thd_enum(chain, name_arg, offset_arg, typelib,
+                      func), visible_value_mask(value_mask)
+    {}
+  bool check(THD *thd, set_var *var)
+  {
+    return check_set(thd, var, enum_names);
+  }
+  uchar *value_ptr(THD *thd, enum_var_type type, LEX_STRING *base);
+};
+
+
 class sys_var_thd_optimizer_switch :public sys_var_thd_enum
 {
 public:
@@ -548,22 +569,14 @@ public:
 
 extern void fix_sql_mode_var(THD *thd, enum_var_type type);
 
-class sys_var_thd_sql_mode :public sys_var_thd_enum
+class sys_var_thd_sql_mode :public sys_var_thd_set
 {
 public:
   sys_var_thd_sql_mode(sys_var_chain *chain, const char *name_arg, 
                        ulong SV::*offset_arg)
-    :sys_var_thd_enum(chain, name_arg, offset_arg, &sql_mode_typelib,
-                      fix_sql_mode_var)
+    :sys_var_thd_set(chain, name_arg, offset_arg, &sql_mode_typelib,
+                     ~(ulong) 0, fix_sql_mode_var)
   {}
-  bool check(THD *thd, set_var *var)
-  {
-    return check_set(thd, var, enum_names);
-  }
-  void set_default(THD *thd, enum_var_type type);
-  uchar *value_ptr(THD *thd, enum_var_type type, LEX_STRING *base);
-  static bool symbolic_mode_representation(THD *thd, ulonglong sql_mode,
-                                           LEX_STRING *rep);
 };
 
 
@@ -1184,7 +1197,6 @@ public:
   bool update(THD *thd, set_var *var);
 };
 
-
 /**
   Handler for setting the system variable --read-only.
 */
diff --git a/sql/slave.cc b/sql/slave.cc
index 84aae6eb683..926db30be15 100644
--- a/sql/slave.cc
+++ b/sql/slave.cc
@@ -1756,6 +1756,7 @@ static int init_slave_thread(THD* thd, SLAVE_THD_TYPE thd_type)
     + MAX_LOG_EVENT_HEADER;  /* note, incr over the global not session var */
   thd->slave_thread = 1;
   thd->enable_slow_log= opt_log_slow_slave_statements;
+  thd->variables.log_slow_filter= global_system_variables.log_slow_filter;
   set_slave_thread_options(thd);
   thd->client_capabilities = CLIENT_LOCAL_FILES;
   pthread_mutex_lock(&LOCK_thread_count);
diff --git a/sql/sp_head.cc b/sql/sp_head.cc
index 0736e5fc2a8..e7310787a35 100644
--- a/sql/sp_head.cc
+++ b/sql/sp_head.cc
@@ -1846,7 +1846,7 @@ sp_head::execute_procedure(THD *thd, List<Item> *args)
   uint params = m_pcont->context_var_count();
   sp_rcontext *save_spcont, *octx;
   sp_rcontext *nctx = NULL;
-  bool save_enable_slow_log= false;
+  bool save_enable_slow_log;
   bool save_log_general= false;
   DBUG_ENTER("sp_head::execute_procedure");
   DBUG_PRINT("info", ("procedure %s", m_name.str));
@@ -1957,10 +1957,10 @@ sp_head::execute_procedure(THD *thd, List<Item> *args)
     DBUG_PRINT("info",(" %.*s: eval args done", (int) m_name.length, 
                        m_name.str));
   }
-  if (!(m_flags & LOG_SLOW_STATEMENTS) && thd->enable_slow_log)
+  save_enable_slow_log= thd->enable_slow_log;
+  if (!(m_flags & LOG_SLOW_STATEMENTS) && save_enable_slow_log)
   {
     DBUG_PRINT("info", ("Disabling slow log for the execution"));
-    save_enable_slow_log= true;
     thd->enable_slow_log= FALSE;
   }
   if (!(m_flags & LOG_GENERAL_LOG) && !(thd->options & OPTION_LOG_OFF))
@@ -1983,8 +1983,7 @@ sp_head::execute_procedure(THD *thd, List<Item> *args)
 
   if (save_log_general)
     thd->options &= ~OPTION_LOG_OFF;
-  if (save_enable_slow_log)
-    thd->enable_slow_log= true;
+  thd->enable_slow_log= save_enable_slow_log;
   /*
     In the case when we weren't able to employ reuse mechanism for
     OUT/INOUT paranmeters, we should reallocate memory. This
@@ -2398,8 +2397,7 @@ sp_head::show_create_routine(THD *thd, int type)
   if (check_show_routine_access(thd, this, &full_access))
     DBUG_RETURN(TRUE);
 
-  sys_var_thd_sql_mode::symbolic_mode_representation(
-      thd, m_sql_mode, &sql_mode);
+    sys_var::make_set(thd, m_sql_mode, &sql_mode_typelib, &sql_mode);
 
   /* Send header. */
 
diff --git a/sql/sql_bitmap.h b/sql/sql_bitmap.h
index 97accefe8aa..e07806a56ab 100644
--- a/sql/sql_bitmap.h
+++ b/sql/sql_bitmap.h
@@ -93,6 +93,34 @@ public:
   }
 };
 
+/* An iterator to quickly walk over bits in unlonglong bitmap. */
+class Table_map_iterator
+{
+  ulonglong bmp;
+  uint no;
+public:
+  Table_map_iterator(ulonglong t) : bmp(t), no(0) {}
+  int next_bit()
+  {
+    static const char last_bit[16]= {32, 0, 1, 0, 
+                                      2, 0, 1, 0, 
+                                      3, 0, 1, 0,
+                                      2, 0, 1, 0};
+    uint bit;
+    while ((bit= last_bit[bmp & 0xF]) == 32)
+    {
+      no += 4;
+      bmp= bmp >> 4;
+      if (!bmp)
+        return BITMAP_END;
+    }
+    bmp &= ~(1LL << bit);
+    return no + bit;
+  }
+  int operator++(int) { return next_bit(); }
+  enum { BITMAP_END= 64 };
+};
+
 template <> class Bitmap<64>
 {
   ulonglong map;
@@ -136,5 +164,10 @@ public:
   my_bool operator==(const Bitmap<64>& map2) const { return map == map2.map; }
   char *print(char *buf) const { longlong2str(map,buf,16); return buf; }
   ulonglong to_ulonglong() const { return map; }
+  class Iterator : public Table_map_iterator
+  {
+  public:
+    Iterator(Bitmap<64> &bmp) : Table_map_iterator(bmp.map) {}
+  };
 };
 
diff --git a/sql/sql_cache.cc b/sql/sql_cache.cc
index 66e5775b534..a97dcab0b55 100644
--- a/sql/sql_cache.cc
+++ b/sql/sql_cache.cc
@@ -1627,6 +1627,7 @@ def_week_frmt: %lu, in_trans: %d, autocommit: %d",
 
   thd->limit_found_rows = query->found_rows();
   thd->status_var.last_query_cost= 0.0;
+  thd->query_plan_flags= (thd->query_plan_flags & ~QPLAN_QC_NO) | QPLAN_QC;
   thd->main_da.disable_status();
 
   BLOCK_UNLOCK_RD(query_block);
@@ -1635,6 +1636,10 @@ def_week_frmt: %lu, in_trans: %d, autocommit: %d",
 err_unlock:
   unlock();
 err:
+  /*
+    query_plan_flags doesn't have to be changed here as it contains
+    QPLAN_QC_NO by default
+  */
   DBUG_RETURN(0);				// Query was not cached
 }
 
diff --git a/sql/sql_class.cc b/sql/sql_class.cc
index cdd1a360144..0805eda59e4 100644
--- a/sql/sql_class.cc
+++ b/sql/sql_class.cc
@@ -3084,6 +3084,7 @@ void THD::reset_sub_statement_state(Sub_statement_state *backup,
   backup->options=         options;
   backup->in_sub_stmt=     in_sub_stmt;
   backup->enable_slow_log= enable_slow_log;
+  backup->query_plan_flags= query_plan_flags;
   backup->limit_found_rows= limit_found_rows;
   backup->examined_row_count= examined_row_count;
   backup->sent_row_count=   sent_row_count;
@@ -3148,6 +3149,7 @@ void THD::restore_sub_statement_state(Sub_statement_state *backup)
   options=          backup->options;
   in_sub_stmt=      backup->in_sub_stmt;
   enable_slow_log=  backup->enable_slow_log;
+  query_plan_flags= backup->query_plan_flags;
   first_successful_insert_id_in_prev_stmt= 
     backup->first_successful_insert_id_in_prev_stmt;
   first_successful_insert_id_in_cur_stmt= 
diff --git a/sql/sql_class.h b/sql/sql_class.h
index 3040b2080cf..60ab952a3ab 100644
--- a/sql/sql_class.h
+++ b/sql/sql_class.h
@@ -349,6 +349,10 @@ struct system_variables
   ulong trans_prealloc_size;
   ulong log_warnings;
   ulong group_concat_max_len;
+  /* Flags for slow log filtering */
+  ulong log_slow_rate_limit; 
+  ulong log_slow_filter; 
+  ulong log_slow_verbosity; 
   ulong ndb_autoincrement_prefetch_sz;
   ulong ndb_index_stat_cache_entries;
   ulong ndb_index_stat_update_freq;
@@ -989,6 +993,7 @@ public:
   ulonglong limit_found_rows;
   ha_rows    cuted_fields, sent_row_count, examined_row_count;
   ulong client_capabilities;
+  ulong query_plan_flags; 
   uint in_sub_stmt;
   bool enable_slow_log;
   bool last_insert_id_used;
@@ -1736,6 +1741,8 @@ public:
     create_sort_index(); may differ from examined_row_count.
   */
   ulong      row_count;
+  ulong      query_plan_flags; 
+  ulong      query_plan_fsort_passes; 
   pthread_t  real_id;                           /* For debugging */
   my_thread_id  thread_id;
   uint	     tmp_table, global_read_lock;
diff --git a/sql/sql_lex.cc b/sql/sql_lex.cc
index 54c06b1fb98..6d047197992 100644
--- a/sql/sql_lex.cc
+++ b/sql/sql_lex.cc
@@ -1839,8 +1839,9 @@ void st_select_lex_unit::exclude_tree()
     'last' should be reachable from this st_select_lex_node
 */
 
-void st_select_lex::mark_as_dependent(st_select_lex *last)
+void st_select_lex::mark_as_dependent(st_select_lex *last, Item *dependency)
 {
+  SELECT_LEX *next_to_last;
   /*
     Mark all selects from resolved to 1 before select where was
     found table as depended (of select where was found table)
@@ -1848,6 +1849,7 @@ void st_select_lex::mark_as_dependent(st_select_lex *last)
   for (SELECT_LEX *s= this;
        s && s != last;
        s= s->outer_select())
+  {
     if (!(s->uncacheable & UNCACHEABLE_DEPENDENT))
     {
       // Select is dependent of outer select
@@ -1863,8 +1865,12 @@ void st_select_lex::mark_as_dependent(st_select_lex *last)
           sl->uncacheable|= UNCACHEABLE_UNITED;
       }
     }
+    next_to_last= s;
+  }
   is_correlated= TRUE;
   this->master_unit()->item->is_correlated= TRUE;
+  if (dependency)
+    next_to_last->master_unit()->item->refers_to.push_back(dependency);
 }
 
 bool st_select_lex_node::set_braces(bool value)      { return 1; }
diff --git a/sql/sql_lex.h b/sql/sql_lex.h
index 76fd5354c51..4b9b35819fe 100644
--- a/sql/sql_lex.h
+++ b/sql/sql_lex.h
@@ -743,7 +743,7 @@ public:
     return master_unit()->return_after_parsing();
   }
 
-  void mark_as_dependent(st_select_lex *last);
+  void mark_as_dependent(st_select_lex *last, Item *dependency);
 
   bool set_braces(bool value);
   bool inc_in_sum_expr();
diff --git a/sql/sql_list.h b/sql/sql_list.h
index 2ed4a8060c4..93cdd20c299 100644
--- a/sql/sql_list.h
+++ b/sql/sql_list.h
@@ -443,6 +443,43 @@ public:
 
 
 /*
+  Exchange sort algorithm for List<T>.
+*/
+template <class T> 
+inline void exchange_sort(List<T> *list_to_sort,
+                          int (*sort_func)(T *a, T *b, void *arg), void *arg)
+{
+  bool swap;
+  List_iterator<T> it(*list_to_sort);
+  do
+  {
+    T *item1= it++;
+    T **ref1= it.ref();
+    T *item2;
+
+    swap= FALSE;
+    while ((item2= it++))
+    {
+      T **ref2= it.ref();
+      if (sort_func(item1, item2, arg) < 0)
+      {
+        T *item= *ref1;
+        *ref1= *ref2;
+        *ref2= item;
+        swap= TRUE;
+      }
+      else
+      {
+        item1= item2;
+        ref1= ref2;
+      }
+    }
+    it.rewind();
+  } while (swap);
+}
+
+
+/*
   A simple intrusive list which automaticly removes element from list
   on delete (for THD element)
 */
diff --git a/sql/sql_parse.cc b/sql/sql_parse.cc
index d9bc07064c3..20033e23b93 100644
--- a/sql/sql_parse.cc
+++ b/sql/sql_parse.cc
@@ -972,6 +972,7 @@ bool dispatch_command(enum enum_server_command command, THD *thd,
     the slow log only if opt_log_slow_admin_statements is set.
   */
   thd->enable_slow_log= TRUE;
+  thd->query_plan_flags= QPLAN_INIT;
   thd->lex->sql_command= SQLCOM_END; /* to avoid confusing VIEW detectors */
   thd->set_time();
   VOID(pthread_mutex_lock(&LOCK_thread_count));
@@ -1046,6 +1047,7 @@ bool dispatch_command(enum enum_server_command command, THD *thd,
 
     status_var_increment(thd->status_var.com_other);
     thd->enable_slow_log= opt_log_slow_admin_statements;
+    thd->query_plan_flags|= QPLAN_ADMIN;
     db.str= (char*) thd->alloc(db_len + tbl_len + 2);
     if (!db.str)
     {
@@ -1401,6 +1403,7 @@ bool dispatch_command(enum enum_server_command command, THD *thd,
 
       status_var_increment(thd->status_var.com_other);
       thd->enable_slow_log= opt_log_slow_admin_statements;
+      thd->query_plan_flags|= QPLAN_ADMIN;
       if (check_global_access(thd, REPL_SLAVE_ACL))
 	break;
 
@@ -1633,6 +1636,19 @@ void log_slow_statement(THD *thd)
   if (unlikely(thd->in_sub_stmt))
     DBUG_VOID_RETURN;                           // Don't set time for sub stmt
 
+  /* Follow the slow log filter configuration. */ 
+  DBUG_ASSERT(thd->variables.log_slow_filter != 0);
+  if (!(thd->variables.log_slow_filter & thd->query_plan_flags))
+    DBUG_VOID_RETURN; 
+ 
+  /* 
+     If rate limiting of slow log writes is enabled, decide whether to log
+     this query to the log or not.
+  */ 
+  if (thd->variables.log_slow_rate_limit > 1 &&
+      (global_query_id % thd->variables.log_slow_rate_limit) != 0)
+    DBUG_VOID_RETURN;
+
   /*
     Do not log administrative statements unless the appropriate option is
     set; do not log into slow log if reading from backup.
@@ -2355,6 +2371,7 @@ mysql_execute_command(THD *thd)
 	check_global_access(thd, FILE_ACL))
       goto error; /* purecov: inspected */
     thd->enable_slow_log= opt_log_slow_admin_statements;
+    thd->query_plan_flags|= QPLAN_ADMIN;
     res = mysql_backup_table(thd, first_table);
     select_lex->table_list.first= (uchar*) first_table;
     lex->query_tables=all_tables;
@@ -2367,6 +2384,7 @@ mysql_execute_command(THD *thd)
 	check_global_access(thd, FILE_ACL))
       goto error; /* purecov: inspected */
     thd->enable_slow_log= opt_log_slow_admin_statements;
+    thd->query_plan_flags|= QPLAN_ADMIN;
     res = mysql_restore_table(thd, first_table);
     select_lex->table_list.first= (uchar*) first_table;
     lex->query_tables=all_tables;
@@ -2752,6 +2770,7 @@ end_with_restore_list:
       ALTER TABLE.
     */
     thd->enable_slow_log= opt_log_slow_admin_statements;
+    thd->query_plan_flags|= QPLAN_ADMIN;
 
     bzero((char*) &create_info, sizeof(create_info));
     create_info.db_type= 0;
@@ -2871,6 +2890,7 @@ end_with_restore_list:
       }
 
       thd->enable_slow_log= opt_log_slow_admin_statements;
+      thd->query_plan_flags|= QPLAN_ADMIN;
       res= mysql_alter_table(thd, select_lex->db, lex->name.str,
                              &create_info,
                              first_table,
@@ -2958,6 +2978,7 @@ end_with_restore_list:
                            UINT_MAX, FALSE))
       goto error; /* purecov: inspected */
     thd->enable_slow_log= opt_log_slow_admin_statements;
+    thd->query_plan_flags|= QPLAN_ADMIN;
     res= mysql_repair_table(thd, first_table, &lex->check_opt);
     /* ! we write after unlocking the table */
     if (!res && !lex->no_write_to_binlog)
@@ -2978,6 +2999,7 @@ end_with_restore_list:
                            UINT_MAX, FALSE))
       goto error; /* purecov: inspected */
     thd->enable_slow_log= opt_log_slow_admin_statements;
+    thd->query_plan_flags|= QPLAN_ADMIN;
     res = mysql_check_table(thd, first_table, &lex->check_opt);
     select_lex->table_list.first= (uchar*) first_table;
     lex->query_tables=all_tables;
@@ -2990,6 +3012,7 @@ end_with_restore_list:
                            UINT_MAX, FALSE))
       goto error; /* purecov: inspected */
     thd->enable_slow_log= opt_log_slow_admin_statements;
+    thd->query_plan_flags|= QPLAN_ADMIN;
     res= mysql_analyze_table(thd, first_table, &lex->check_opt);
     /* ! we write after unlocking the table */
     if (!res && !lex->no_write_to_binlog)
@@ -3011,6 +3034,7 @@ end_with_restore_list:
                            UINT_MAX, FALSE))
       goto error; /* purecov: inspected */
     thd->enable_slow_log= opt_log_slow_admin_statements;
+    thd->query_plan_flags|= QPLAN_ADMIN;
     res= (specialflag & (SPECIAL_SAFE_MODE | SPECIAL_NO_NEW_FUNC)) ?
       mysql_recreate_table(thd, first_table) :
       mysql_optimize_table(thd, first_table, &lex->check_opt);
@@ -5687,6 +5711,8 @@ void mysql_reset_thd_for_next_command(THD *thd)
   thd->total_warn_count=0;			// Warnings for this query
   thd->rand_used= 0;
   thd->sent_row_count= thd->examined_row_count= 0;
+  thd->query_plan_flags= QPLAN_INIT;
+  thd->query_plan_fsort_passes= 0;
 
   /*
     Because we come here only for start of top-statements, binlog format is
diff --git a/sql/sql_select.cc b/sql/sql_select.cc
index ba38bb78ceb..014b63c057c 100644
--- a/sql/sql_select.cc
+++ b/sql/sql_select.cc
@@ -61,7 +61,6 @@ static bool update_ref_and_keys(THD *thd, DYNAMIC_ARRAY *keyuse,
                                 table_map table_map, SELECT_LEX *select_lex,
                                 st_sargable_param **sargables);
 static int sort_keyuse(KEYUSE *a,KEYUSE *b);
-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 bool choose_plan(JOIN *join,table_map join_tables);
@@ -116,7 +115,7 @@ static COND *simplify_joins(JOIN *join, List<TABLE_LIST> *join_list,
                             COND *conds, bool top);
 static bool check_interleaving_with_nj(JOIN_TAB *next);
 static void restore_prev_nj_state(JOIN_TAB *last);
-static void reset_nj_counters(List<TABLE_LIST> *join_list);
+static uint reset_nj_counters(JOIN *join, List<TABLE_LIST> *join_list);
 static uint build_bitmap_for_nested_joins(List<TABLE_LIST> *join_list,
                                           uint first_unused);
 
@@ -1013,7 +1012,7 @@ JOIN::optimize()
     DBUG_RETURN(1);
   }
   
-  reset_nj_counters(join_list);
+  reset_nj_counters(this, join_list);
   make_outerjoin_info(this);
 
   /*
@@ -2390,6 +2389,13 @@ mysql_select(THD *thd, Item ***rref_pointer_array,
   }
   else
   {
+    /*
+      When in EXPLAIN, delay deleting the joins so that they are still
+      available when we're producing EXPLAIN EXTENDED warning text.
+    */
+    if (select_options & SELECT_DESCRIBE)
+      free_join= 0;
+
     if (!(join= new JOIN(thd, fields, select_options, result)))
 	DBUG_RETURN(TRUE);
     thd_proc_info(thd, "init");
@@ -2655,24 +2661,31 @@ make_join_statistics(JOIN *join, TABLE_LIST *tables_arg, COND *conds,
                             ~outer_join, join->select_lex, &sargables))
       goto error;
 
-  /* Read tables with 0 or 1 rows (system tables) */
   join->const_table_map= 0;
+  join->const_tables= const_count;
+  eliminate_tables(join);
+  const_count= join->const_tables;
+  found_const_table_map= join->const_table_map;
 
+  /* Read tables with 0 or 1 rows (system tables) */
   for (POSITION *p_pos=join->positions, *p_end=p_pos+const_count;
        p_pos < p_end ;
        p_pos++)
   {
-    int tmp;
     s= p_pos->table;
-    s->type=JT_SYSTEM;
-    join->const_table_map|=s->table->map;
-    if ((tmp=join_read_const_table(s, p_pos)))
+    if (! (s->table->map & join->eliminated_tables))
     {
-      if (tmp > 0)
-	goto error;		// Fatal error
+      int tmp;
+      s->type=JT_SYSTEM;
+      join->const_table_map|=s->table->map;
+      if ((tmp=join_read_const_table(s, p_pos)))
+      {
+        if (tmp > 0)
+          goto error;		// Fatal error
+      }
+      else
+        found_const_table_map|= s->table->map;
     }
-    else
-      found_const_table_map|= s->table->map;
   }
 
   /* loop until no more const tables are found */
@@ -2697,7 +2710,8 @@ make_join_statistics(JOIN *join, TABLE_LIST *tables_arg, COND *conds,
         substitution of a const table the key value happens to be null
         then we can state that there are no matches for this equi-join.
       */  
-      if ((keyuse= s->keyuse) && *s->on_expr_ref && !s->embedding_map)
+      if ((keyuse= s->keyuse) && *s->on_expr_ref && !s->embedding_map &&
+         !(table->map & join->eliminated_tables))
       {
         /* 
           When performing an outer join operation if there are no matching rows
@@ -2974,14 +2988,45 @@ typedef struct key_field_t {
 
   This is called for OR between different levels.
 
-  To be able to do 'ref_or_null' we merge a comparison of a column
-  and 'column IS NULL' to one test.  This is useful for sub select queries
-  that are internally transformed to something like:.
+  That is, the function operates on an array of KEY_FIELD elements which has
+  two parts:
+
+                      $LEFT_PART             $RIGHT_PART
+             +-----------------------+-----------------------+
+            start                new_fields                 end
+         
+  $LEFT_PART and $RIGHT_PART are arrays that have KEY_FIELD elements for two
+  parts of the OR condition. Our task is to produce an array of KEY_FIELD 
+  elements that would correspond to "$LEFT_PART OR $RIGHT_PART". 
+  
+  The rules for combining elements are as follows:
+
+    (keyfieldA1 AND keyfieldA2 AND ...) OR (keyfieldB1 AND keyfieldB2 AND ...)=
+     
+     = AND_ij (keyfieldA_i OR keyfieldB_j)
+  
+  We discard all (keyfieldA_i OR keyfieldB_j) that refer to different
+  fields. For those referring to the same field, the logic is as follows:
+    
+    t.keycol=expr1 OR t.keycol=expr2 -> (since expr1 and expr2 are different 
+                                         we can't produce a single equality,
+                                         so produce nothing)
+
+    t.keycol=expr1 OR t.keycol=expr1 -> t.keycol=expr1
+
+    t.keycol=expr1 OR t.keycol IS NULL -> t.keycol=expr1, and also set
+                                          KEY_OPTIMIZE_REF_OR_NULL flag
+
+  The last one is for ref_or_null access. We have handling for this special
+  because it's needed for evaluating IN subqueries that are internally
+  transformed into 
 
   @code
-  SELECT * FROM t1 WHERE t1.key=outer_ref_field or t1.key IS NULL 
+    EXISTS(SELECT * FROM t1 WHERE t1.key=outer_ref_field or t1.key IS NULL)
   @endcode
 
+  See add_key_fields() for discussion of what is and_level.
+
   KEY_FIELD::null_rejecting is processed as follows: @n
   result has null_rejecting=true if it is set for both ORed references.
   for example:
@@ -3343,6 +3388,25 @@ is_local_field (Item *field)
 }
 
 
+/*
+  In this and other functions, and_level is a number that is ever-growing
+  and is different for the contents of every AND or OR clause. For example,
+  when processing clause
+
+     (a AND b AND c) OR (x AND y)
+  
+  we'll have
+   * KEY_FIELD elements for (a AND b AND c) are assigned and_level=1
+   * KEY_FIELD elements for (x AND y) are assigned and_level=2
+   * OR operation is performed, and whatever elements are left after it are
+     assigned and_level=3.
+
+  The primary reason for having and_level attribute is the OR operation which 
+  uses and_level to mark KEY_FIELDs that should get into the result of the OR
+  operation
+
+*/
+
 static void
 add_key_fields(JOIN *join, KEY_FIELD **key_fields, uint *and_level,
                COND *cond, table_map usable_tables,
@@ -4028,8 +4092,7 @@ add_group_and_distinct_keys(JOIN *join, JOIN_TAB *join_tab)
 
 /** Save const tables first as used tables. */
 
-static void
-set_position(JOIN *join,uint idx,JOIN_TAB *table,KEYUSE *key)
+void set_position(JOIN *join,uint idx,JOIN_TAB *table,KEYUSE *key)
 {
   join->positions[idx].table= table;
   join->positions[idx].key=key;
@@ -4630,7 +4693,7 @@ choose_plan(JOIN *join, table_map join_tables)
   DBUG_ENTER("choose_plan");
 
   join->cur_embedding_map= 0;
-  reset_nj_counters(join->join_list);
+  reset_nj_counters(join, join->join_list);
   /*
     if (SELECT_STRAIGHT_JOIN option is set)
       reorder tables so dependent tables come after tables they depend 
@@ -5795,6 +5858,7 @@ JOIN::make_simple_join(JOIN *parent, TABLE *tmp_table)
   tables= 1;
   const_tables= 0;
   const_table_map= 0;
+  eliminated_tables= 0;
   tmp_table_param.field_count= tmp_table_param.sum_func_count=
     tmp_table_param.func_count= 0;
   tmp_table_param.copy_field= tmp_table_param.copy_field_end=0;
@@ -6059,7 +6123,7 @@ make_outerjoin_info(JOIN *join)
       }
       if (!tab->first_inner)  
         tab->first_inner= nested_join->first_nested;
-      if (++nested_join->counter < nested_join->join_list.elements)
+      if (++nested_join->counter < nested_join->n_tables)
         break;
       /* Table tab is the last inner table for nested join. */
       nested_join->first_nested->last_inner= tab;
@@ -6585,7 +6649,10 @@ make_join_readinfo(JOIN *join, ulonglong options)
 	  {
 	    join->thd->server_status|=SERVER_QUERY_NO_INDEX_USED;
 	    if (statistics)
+	    {
 	      status_var_increment(join->thd->status_var.select_scan_count);
+	      join->thd->query_plan_flags|= QPLAN_FULL_SCAN;
+	    }
 	  }
 	}
 	else
@@ -6599,7 +6666,10 @@ make_join_readinfo(JOIN *join, ulonglong options)
 	  {
 	    join->thd->server_status|=SERVER_QUERY_NO_INDEX_USED;
 	    if (statistics)
+	    {
 	      status_var_increment(join->thd->status_var.select_full_join_count);
+	      join->thd->query_plan_flags|= QPLAN_FULL_JOIN;
+	    }
 	  }
 	}
 	if (!table->no_keyread)
@@ -8614,6 +8684,8 @@ simplify_joins(JOIN *join, List<TABLE_LIST> *join_list, COND *conds, bool top)
       conds= simplify_joins(join, &nested_join->join_list, conds, top);
       used_tables= nested_join->used_tables;
       not_null_tables= nested_join->not_null_tables;  
+      /* The following two might become unequal after table elimination: */
+      nested_join->n_tables= nested_join->join_list.elements;
     }
     else
     {
@@ -8772,7 +8844,7 @@ static uint build_bitmap_for_nested_joins(List<TABLE_LIST> *join_list,
             with anything)
         2. we could run out bits in nested_join_map otherwise.
       */
-      if (nested_join->join_list.elements != 1)
+      if (nested_join->n_tables != 1)
       {
         nested_join->nj_map= (nested_join_map) 1 << first_unused++;
         first_unused= build_bitmap_for_nested_joins(&nested_join->join_list,
@@ -8794,21 +8866,26 @@ static uint build_bitmap_for_nested_joins(List<TABLE_LIST> *join_list,
                     tables which will be ignored.
 */
 
-static void reset_nj_counters(List<TABLE_LIST> *join_list)
+static uint reset_nj_counters(JOIN *join, List<TABLE_LIST> *join_list)
 {
   List_iterator<TABLE_LIST> li(*join_list);
   TABLE_LIST *table;
   DBUG_ENTER("reset_nj_counters");
+  uint n=0;
   while ((table= li++))
   {
     NESTED_JOIN *nested_join;
     if ((nested_join= table->nested_join))
     {
       nested_join->counter= 0;
-      reset_nj_counters(&nested_join->join_list);
+      //nested_join->n_tables= my_count_bits(nested_join->used_tables & 
+      //                                     ~join->eliminated_tables);
+      nested_join->n_tables= reset_nj_counters(join, &nested_join->join_list);
     }
+    if (table->table && (table->table->map & ~join->eliminated_tables))
+      n++;
   }
-  DBUG_VOID_RETURN;
+  DBUG_RETURN(n);
 }
 
 
@@ -8933,7 +9010,7 @@ static bool check_interleaving_with_nj(JOIN_TAB *next_tab)
       join->cur_embedding_map |= next_emb->nested_join->nj_map;
     }
     
-    if (next_emb->nested_join->join_list.elements !=
+    if (next_emb->nested_join->n_tables !=
         next_emb->nested_join->counter)
       break;
 
@@ -8967,7 +9044,7 @@ static void restore_prev_nj_state(JOIN_TAB *last)
   {
     if (!(--last_emb->nested_join->counter))
       join->cur_embedding_map&= ~last_emb->nested_join->nj_map;
-    else if (last_emb->nested_join->join_list.elements-1 ==
+    else if (last_emb->nested_join->n_tables-1 ==
              last_emb->nested_join->counter) 
       join->cur_embedding_map|= last_emb->nested_join->nj_map;
     else
@@ -9763,6 +9840,7 @@ create_tmp_table(THD *thd,TMP_TABLE_PARAM *param,List<Item> &fields,
               (ulong) rows_limit,test(group)));
 
   status_var_increment(thd->status_var.created_tmp_tables);
+  thd->query_plan_flags|= QPLAN_TMP_TABLE;
 
   if (use_temp_pool && !(test_flags & TEST_KEEP_TMP_TABLES))
     temp_pool_slot = bitmap_lock_set_next(&temp_pool);
@@ -10649,6 +10727,7 @@ static bool create_internal_tmp_table(TABLE *table,TMP_TABLE_PARAM *param,
     goto err;
   }
   status_var_increment(table->in_use->status_var.created_tmp_disk_tables);
+  table->in_use->query_plan_flags|= QPLAN_TMP_DISK;
   share->db_record_offset= 1;
   DBUG_RETURN(0);
  err:
@@ -16304,6 +16383,14 @@ static void select_describe(JOIN *join, bool need_tmp_table, bool need_order,
       tmp3.length(0);
 
       quick_type= -1;
+
+      /* Don't show eliminated tables */
+      if (table->map & join->eliminated_tables)
+      {
+        used_tables|=table->map;
+        continue;
+      }
+
       item_list.empty();
       /* id */
       item_list.push_back(new Item_uint((uint32)
@@ -16626,8 +16713,11 @@ static void select_describe(JOIN *join, bool need_tmp_table, bool need_order,
        unit;
        unit= unit->next_unit())
   {
-    if (mysql_explain_union(thd, unit, result))
-      DBUG_VOID_RETURN;
+    if (!(unit->item && unit->item->eliminated))
+    {
+      if (mysql_explain_union(thd, unit, result))
+        DBUG_VOID_RETURN;
+    }
   }
   DBUG_VOID_RETURN;
 }
@@ -16668,7 +16758,6 @@ bool mysql_explain_union(THD *thd, SELECT_LEX_UNIT *unit, select_result *result)
     unit->fake_select_lex->options|= SELECT_DESCRIBE;
     if (!(res= unit->prepare(thd, result, SELECT_NO_UNLOCK | SELECT_DESCRIBE)))
       res= unit->exec();
-    res|= unit->cleanup();
   }
   else
   {
@@ -16701,6 +16790,7 @@ bool mysql_explain_union(THD *thd, SELECT_LEX_UNIT *unit, select_result *result)
 */
 
 static void print_join(THD *thd,
+                       table_map eliminated_tables,
                        String *str,
                        List<TABLE_LIST> *tables,
                        enum_query_type query_type)
@@ -16716,12 +16806,33 @@ static void print_join(THD *thd,
     *t= ti++;
 
   DBUG_ASSERT(tables->elements >= 1);
-  (*table)->print(thd, str, query_type);
+  /*
+    Assert that the first table in the list isn't eliminated. This comes from
+    the fact that the first table can't be inner table of an outer join.
+  */
+  DBUG_ASSERT(!eliminated_tables || 
+              !(((*table)->table && ((*table)->table->map & eliminated_tables)) ||
+                ((*table)->nested_join && !((*table)->nested_join->used_tables &
+                                           ~eliminated_tables))));
+  (*table)->print(thd, eliminated_tables, str, query_type);
 
   TABLE_LIST **end= table + tables->elements;
   for (TABLE_LIST **tbl= table + 1; tbl < end; tbl++)
   {
     TABLE_LIST *curr= *tbl;
+    /*
+      The "eliminated_tables &&" check guards againist the case of 
+      printing the query for CREATE VIEW. We do that without having run 
+      JOIN::optimize() and so will have nested_join->used_tables==0.
+    */
+    if (eliminated_tables &&
+        ((curr->table && (curr->table->map & eliminated_tables)) ||
+         (curr->nested_join && !(curr->nested_join->used_tables &
+                                ~eliminated_tables))))
+    {
+      continue;
+    }
+
     if (curr->outer_join)
     {
       /* MySQL converts right to left joins */
@@ -16731,7 +16842,7 @@ static void print_join(THD *thd,
       str->append(STRING_WITH_LEN(" straight_join "));
     else
       str->append(STRING_WITH_LEN(" join "));
-    curr->print(thd, str, query_type);
+    curr->print(thd, eliminated_tables, str, query_type);
     if (curr->on_expr)
     {
       str->append(STRING_WITH_LEN(" on("));
@@ -16785,12 +16896,13 @@ Index_hint::print(THD *thd, String *str)
   @param str   string where table should be printed
 */
 
-void TABLE_LIST::print(THD *thd, String *str, enum_query_type query_type)
+void TABLE_LIST::print(THD *thd, table_map eliminated_tables, String *str, 
+                       enum_query_type query_type)
 {
   if (nested_join)
   {
     str->append('(');
-    print_join(thd, str, &nested_join->join_list, query_type);
+    print_join(thd, eliminated_tables, str, &nested_join->join_list, query_type);
     str->append(')');
   }
   else
@@ -16932,7 +17044,7 @@ void st_select_lex::print(THD *thd, String *str, enum_query_type query_type)
   {
     str->append(STRING_WITH_LEN(" from "));
     /* go through join tree */
-    print_join(thd, str, &top_join_list, query_type);
+    print_join(thd, join? join->eliminated_tables: 0, str, &top_join_list, query_type);
   }
   else if (where)
   {
diff --git a/sql/sql_select.h b/sql/sql_select.h
index 5e97185a7b9..271c88ebf66 100644
--- a/sql/sql_select.h
+++ b/sql/sql_select.h
@@ -285,7 +285,15 @@ public:
     fetching data from a cursor
   */
   bool     resume_nested_loop;
-  table_map const_table_map,found_const_table_map;
+  table_map const_table_map;
+  /*
+    Constant tables for which we have found a row (as opposed to those for
+    which we didn't).
+  */
+  table_map found_const_table_map;
+  
+  /* Tables removed by table elimination. Set to 0 before the elimination. */
+  table_map eliminated_tables;
   /*
      Bitmap of all inner tables from outer joins
   */
@@ -425,6 +433,7 @@ public:
     table= 0;
     tables= 0;
     const_tables= 0;
+    eliminated_tables= 0;
     join_list= 0;
     sort_and_group= 0;
     first_record= 0;
@@ -530,6 +539,10 @@ public:
     return (unit == &thd->lex->unit && (unit->fake_select_lex == 0 ||
                                         select_lex == unit->fake_select_lex));
   }
+  inline table_map all_tables_map()
+  {
+    return (table_map(1) << tables) - 1;
+  }
 private:
   bool make_simple_join(JOIN *join, TABLE *tmp_table);
 };
@@ -730,9 +743,12 @@ bool error_if_full_join(JOIN *join);
 int report_error(TABLE *table, int error);
 int safe_index_read(JOIN_TAB *tab);
 COND *remove_eq_conds(THD *thd, COND *cond, Item::cond_result *cond_value);
+void set_position(JOIN *join,uint idx,JOIN_TAB *table,KEYUSE *key);
 
 inline bool optimizer_flag(THD *thd, uint flag)
 { 
   return (thd->variables.optimizer_switch & flag);
 }
 
+void eliminate_tables(JOIN *join);
+
diff --git a/sql/sql_show.cc b/sql/sql_show.cc
index c8936be1ea4..18e83498f7d 100644
--- a/sql/sql_show.cc
+++ b/sql/sql_show.cc
@@ -4570,8 +4570,7 @@ static bool store_trigger(THD *thd, TABLE *table, LEX_STRING *db_name,
   table->field[14]->store(STRING_WITH_LEN("OLD"), cs);
   table->field[15]->store(STRING_WITH_LEN("NEW"), cs);
 
-  sys_var_thd_sql_mode::symbolic_mode_representation(thd, sql_mode,
-                                                     &sql_mode_rep);
+  sys_var::make_set(thd, sql_mode, &sql_mode_typelib, &sql_mode_rep);
   table->field[17]->store(sql_mode_rep.str, sql_mode_rep.length, cs);
   table->field[18]->store(definer_buffer->str, definer_buffer->length, cs);
   table->field[19]->store(client_cs_name->str, client_cs_name->length, cs);
@@ -5164,8 +5163,7 @@ copy_event_to_schema_table(THD *thd, TABLE *sch_table, TABLE *event_table)
   /* SQL_MODE */
   {
     LEX_STRING sql_mode;
-    sys_var_thd_sql_mode::symbolic_mode_representation(thd, et.sql_mode,
-                                                       &sql_mode);
+    sys_var::make_set(thd, et.sql_mode, &sql_mode_typelib, &sql_mode);
     sch_table->field[ISE_SQL_MODE]->
                                 store(sql_mode.str, sql_mode.length, scs);
   }
@@ -6870,9 +6868,7 @@ static bool show_create_trigger_impl(THD *thd,
                              &trg_connection_cl_name,
                              &trg_db_cl_name);
 
-  sys_var_thd_sql_mode::symbolic_mode_representation(thd,
-                                                     trg_sql_mode,
-                                                     &trg_sql_mode_str);
+  sys_var::make_set(thd, trg_sql_mode, &sql_mode_typelib, &trg_sql_mode_str);
 
   /* Resolve trigger client character set. */
 
diff --git a/sql/strfunc.cc b/sql/strfunc.cc
index 5ff2efe2020..0153381f85b 100644
--- a/sql/strfunc.cc
+++ b/sql/strfunc.cc
@@ -45,6 +45,7 @@ ulonglong find_set(TYPELIB *lib, const char *str, uint length,
   CHARSET_INFO *strip= cs ? cs : &my_charset_latin1;
   const char *end= str + strip->cset->lengthsp(strip, str, length);
   ulonglong found= 0;
+
   *err_pos= 0;                  // No error yet
   if (str != end)
   {
@@ -74,9 +75,13 @@ ulonglong find_set(TYPELIB *lib, const char *str, uint length,
                       find_type(lib, start, var_len, (bool) 0);
       if (!find)
       {
-        *err_pos= (char*) start;
-        *err_len= var_len;
-        *set_warning= 1;
+        /* Report first error */
+        if (!*err_pos)
+        {
+          *err_pos= (char*) start;
+          *err_len= var_len;
+          *set_warning= 1;
+        }
       }
       else
         found|= ((longlong) 1 << (find - 1));
@@ -148,8 +153,10 @@ static uint parse_name(TYPELIB *lib, const char **strpos, const char *end,
     }
   }
   else
-    for (; pos != end && *pos != '=' && *pos !=',' ; pos++);
-
+  {
+    for (; pos != end && *pos != '=' && *pos !=',' ; pos++)
+      ;
+  }
   uint var_len= (uint) (pos - start);
   /* Determine which flag it is */
   uint find= cs ? find_type2(lib, start, var_len, cs) :
diff --git a/sql/table.h b/sql/table.h
index dad7762d63f..a7ae50b8e72 100644
--- a/sql/table.h
+++ b/sql/table.h
@@ -1374,7 +1374,8 @@ struct TABLE_LIST
     return (derived || view || schema_table || (create && !table->db_stat) ||
             !table);
   }
-  void print(THD *thd, String *str, enum_query_type query_type);
+  void print(THD *thd, table_map eliminated_tables, String *str, 
+             enum_query_type query_type);
   bool check_single_table(TABLE_LIST **table, table_map map,
                           TABLE_LIST *view);
   bool set_insert_values(MEM_ROOT *mem_root);
@@ -1623,7 +1624,11 @@ public:
 typedef struct st_nested_join
 {
   List<TABLE_LIST>  join_list;       /* list of elements in the nested join */
-  table_map         used_tables;     /* bitmap of tables in the nested join */
+  /* 
+    Bitmap of tables within this nested join (including those embedded within
+    its children), including tables removed by table elimination.
+  */
+  table_map         used_tables;
   table_map         not_null_tables; /* tables that rejects nulls           */
   struct st_join_table *first_nested;/* the first nested table in the plan  */
   /* 
@@ -1634,6 +1639,11 @@ typedef struct st_nested_join
     Before each use the counters are zeroed by reset_nj_counters.
   */
   uint              counter;
+  /*
+    Number of elements in join_list that were not (or contain table(s) that 
+    weren't) removed by table elimination.
+  */
+  uint              n_tables;
   nested_join_map   nj_map;          /* Bit used to identify this nested join*/
 } NESTED_JOIN;