Subquery optimizations: non-semijoin materialization

- Backport into Maria DB 5.3, part 1

12 files changed, 1118 insertions, 144 deletions

diff --git a/sql/item.h b/sql/item.h
index 497c2c1d840..ddb98b1f545 100644
--- a/sql/item.h
+++ b/sql/item.h
@@ -878,6 +878,9 @@ public:
   static CHARSET_INFO *default_charset();
   virtual CHARSET_INFO *compare_collation() { return NULL; }
 
+  /* Cache of the result of is_expensive(). */
+  int8 is_expensive_cache;
+  
   virtual bool walk(Item_processor processor, bool walk_subquery, uchar *arg)
   {
     return (this->*processor)(arg);
@@ -1081,6 +1084,29 @@ public:
   */
   virtual bool result_as_longlong() { return FALSE; }
   bool is_datetime();
+
+  /*
+    Test whether an expression is expensive to compute. Used during
+    optimization to avoid computing expensive expressions during this
+    phase. Also used to force temp tables when sorting on expensive
+    functions.
+    TODO:
+    Normally we should have a method:
+      cost Item::execution_cost(),
+    where 'cost' is either 'double' or some structure of various cost
+    parameters.
+
+    NOTE
+      This function is now used to prevent evaluation of materialized IN
+      subquery predicates before it is allowed. grep for 
+      DontEvaluateMaterializedSubqueryTooEarly to see the uses.
+  */
+  virtual bool is_expensive()
+  {
+    if (is_expensive_cache < 0)
+      is_expensive_cache= walk(&Item::is_expensive_processor, 0, (uchar*)0);
+    return test(is_expensive_cache);
+  }
   virtual Field::geometry_type get_geometry_type() const
     { return Field::GEOM_GEOMETRY; };
   String *check_well_formed_result(String *str, bool send_error= 0);
@@ -2842,9 +2868,10 @@ class Cached_item_field :public Cached_item
   uint length;
 
 public:
-  Cached_item_field(Item_field *item)
+  Cached_item_field(Field *arg_field) : field(arg_field)
   {
-    field= item->field;
+    field= arg_field;
+    /* TODO: take the memory allocation below out of the constructor. */
     buff= (uchar*) sql_calloc(length=field->pack_length());
   }
   bool cmp(void);
@@ -3271,7 +3298,8 @@ void mark_select_range_as_dependent(THD *thd,
                                     Field *found_field, Item *found_item,
                                     Item_ident *resolved_item);
 
-extern Cached_item *new_Cached_item(THD *thd, Item *item);
+extern Cached_item *new_Cached_item(THD *thd, Item *item,
+                                    bool use_result_field);
 extern Item_result item_cmp_type(Item_result a,Item_result b);
 extern void resolve_const_item(THD *thd, Item **ref, Item *cmp_item);
 extern int stored_field_cmp_to_item(Field *field, Item *item);
diff --git a/sql/item_buff.cc b/sql/item_buff.cc
index 2f45d0a17c2..037a988ebbc 100644
--- a/sql/item_buff.cc
+++ b/sql/item_buff.cc
@@ -27,11 +27,16 @@
   Create right type of Cached_item for an item.
 */
 
-Cached_item *new_Cached_item(THD *thd, Item *item)
+Cached_item *new_Cached_item(THD *thd, Item *item, bool use_result_field)
 {
   if (item->real_item()->type() == Item::FIELD_ITEM &&
       !(((Item_field *) (item->real_item()))->field->flags & BLOB_FLAG))
-    return new Cached_item_field((Item_field *) (item->real_item()));
+  {
+    Item_field *real_item= (Item_field *) item->real_item();
+    Field *cached_field= use_result_field ? real_item->result_field :
+                                            real_item->field;
+    return new Cached_item_field(cached_field);
+  }
   switch (item->result_type()) {
   case STRING_RESULT:
     return new Cached_item_str(thd, (Item_field *) item);
diff --git a/sql/item_func.cc b/sql/item_func.cc
index ed089a83561..a56944122db 100644
--- a/sql/item_func.cc
+++ b/sql/item_func.cc
@@ -490,12 +490,12 @@ Field *Item_func::tmp_table_field(TABLE *table)
   return field;
 }
 
-
+/*
 bool Item_func::is_expensive_processor(uchar *arg)
 {
   return is_expensive();
 }
-
+*/
 
 my_decimal *Item_func::val_decimal(my_decimal *decimal_value)
 {
diff --git a/sql/item_func.h b/sql/item_func.h
index 1043a72cdbb..70a88197b39 100644
--- a/sql/item_func.h
+++ b/sql/item_func.h
@@ -192,8 +192,8 @@ public:
                 Item_transformer transformer, uchar *arg_t);
   void traverse_cond(Cond_traverser traverser,
                      void * arg, traverse_order order);
-  bool is_expensive_processor(uchar *arg);
-  virtual bool is_expensive() { return 0; }
+ // bool is_expensive_processor(uchar *arg);
+ // virtual bool is_expensive() { return 0; }
   inline double fix_result(double value)
   {
     if (isfinite(value))
@@ -1053,6 +1053,7 @@ class Item_udf_func :public Item_func
 {
 protected:
   udf_handler udf;
+  bool is_expensive_processor(uchar *arg) { return TRUE; }
 
 public:
   Item_udf_func(udf_func *udf_arg)
@@ -1676,6 +1677,9 @@ private:
   bool execute();
   bool execute_impl(THD *thd);
   bool init_result_field(THD *thd);
+
+protected:
+  bool is_expensive_processor(uchar *arg) { return TRUE; }
   
 public:
 
diff --git a/sql/item_subselect.cc b/sql/item_subselect.cc
index a5219dbd6fb..5871b53ba35 100644
--- a/sql/item_subselect.cc
+++ b/sql/item_subselect.cc
@@ -39,12 +39,13 @@ 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), in_fix_fields(0), 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();
   /*
-    item value is NULL if select_subselect not changed this value
+    Item value is NULL if select_result_interceptor didn't change this value
     (i.e. some rows will be found returned)
   */
   null_value= 1;
@@ -52,7 +53,7 @@ Item_subselect::Item_subselect():
 
 
 void Item_subselect::init(st_select_lex *select_lex,
-			  select_subselect *result)
+			  select_result_interceptor *result)
 {
   /*
     Please see Item_singlerow_subselect::invalidate_and_restore_select_lex(),
@@ -130,6 +131,21 @@ void Item_singlerow_subselect::cleanup()
   DBUG_VOID_RETURN;
 }
 
+
+void Item_in_subselect::cleanup()
+{
+  DBUG_ENTER("Item_in_subselect::cleanup");
+  if (left_expr_cache)
+  {
+    left_expr_cache->delete_elements();
+    delete left_expr_cache;
+    left_expr_cache= NULL;
+  }
+  first_execution= TRUE;
+  Item_subselect::cleanup();
+  DBUG_VOID_RETURN;
+}
+
 Item_subselect::~Item_subselect()
 {
   delete engine;
@@ -166,6 +182,15 @@ bool Item_subselect::fix_fields(THD *thd_param, Item **ref)
 
   if (!res)
   {
+    // all transformation is done (used by prepared statements)
+    changed= 1;
+
+    /*
+      Substitute the current item with an Item_in_optimizer that was
+      created by Item_in_subselect::select_in_like_transformer and
+      call fix_fields for the substituted item which in turn calls
+      engine->prepare for the subquery predicate.
+    */
     if (substitution)
     {
       int ret= 0;
@@ -296,6 +321,50 @@ bool Item_subselect::exec()
   return (res);
 }
 
+
+/*
+  Compute the IN predicate if the left operand's cache changed.
+*/
+
+bool Item_in_subselect::exec()
+{
+  DBUG_ENTER("Item_in_subselect::exec");
+  DBUG_ASSERT(exec_method != MATERIALIZATION ||
+              (exec_method == MATERIALIZATION &&
+               engine->engine_type() == subselect_engine::HASH_SJ_ENGINE));
+  /*
+    Initialize the cache of the left predicate operand. This has to be done as
+    late as now, because Cached_item directly contains a resolved field (not
+    an item, and in some cases (when temp tables are created), these fields
+    end up pointing to the wrong field. One solution is to change Cached_item
+    to not resolve its field upon creation, but to resolve it dynamically
+    from a given Item_ref object.
+    TODO: the cache should be applied conditionally based on:
+    - rules - e.g. only if the left operand is known to be ordered, and/or
+    - on a cost-based basis, that takes into account the cost of a cache
+      lookup, the cache hit rate, and the savings per cache hit.
+  */
+  if (!left_expr_cache && exec_method == MATERIALIZATION)
+    init_left_expr_cache();
+
+  /* If the new left operand is already in the cache, reuse the old result. */
+  if (left_expr_cache && test_if_item_cache_changed(*left_expr_cache) < 0)
+  {
+    /* Always compute IN for the first row as the cache is not valid for it. */
+    if (!first_execution)
+      DBUG_RETURN(FALSE);
+    first_execution= FALSE;
+  }
+
+  /*
+    The exec() method below updates item::value, and item::null_value, thus if
+    we don't call it, the next call to item::val_int() will return whatever
+    result was computed by its previous call.
+  */
+  DBUG_RETURN(Item_subselect::exec());
+}
+
+
 Item::Type Item_subselect::type() const
 {
   return SUBSELECT_ITEM;
@@ -339,9 +408,14 @@ void Item_subselect::update_used_tables()
 
 void Item_subselect::print(String *str, enum_query_type query_type)
 {
-  str->append('(');
-  engine->print(str, query_type);
-  str->append(')');
+  if (engine)
+  {
+    str->append('(');
+    engine->print(str, query_type);
+    str->append(')');
+  }
+  else
+    str->append("(...)");
 }
 
 
@@ -450,8 +524,9 @@ void Item_singlerow_subselect::reset()
 Item_subselect::trans_res
 Item_singlerow_subselect::select_transformer(JOIN *join)
 {
+  DBUG_ENTER("Item_singlerow_subselect::select_transformer");
   if (changed)
-    return RES_OK;
+    DBUG_RETURN(RES_OK);
 
   SELECT_LEX *select_lex= join->select_lex;
   Query_arena *arena= thd->stmt_arena;
@@ -494,15 +569,17 @@ Item_singlerow_subselect::select_transformer(JOIN *join)
     */
     substitution->walk(&Item::remove_dependence_processor, 0,
 		       (uchar *) select_lex->outer_select());
-    return RES_REDUCE;
+    DBUG_RETURN(RES_REDUCE);
   }
-  return RES_OK;
+  DBUG_RETURN(RES_OK);
 }
 
 
 void Item_singlerow_subselect::store(uint i, Item *item)
 {
   row[i]->store(item);
+  //psergey-merge: can do without that: row[i]->cache_value();
+  //psergey-backport-timours: ^ really, without that ^ 
 }
 
 enum Item_result Item_singlerow_subselect::result_type() const
@@ -685,8 +762,9 @@ bool Item_in_subselect::test_limit(st_select_lex_unit *unit_arg)
 
 Item_in_subselect::Item_in_subselect(Item * left_exp,
 				     st_select_lex *select_lex):
-  Item_exists_subselect(), optimizer(0), transformed(0),
-  pushed_cond_guards(NULL), exec_method(NOT_TRANSFORMED), upper_item(0)
+  Item_exists_subselect(), left_expr_cache(0), first_execution(TRUE),
+  optimizer(0), pushed_cond_guards(NULL), exec_method(NOT_TRANSFORMED),
+  upper_item(0)
 {
   DBUG_ENTER("Item_in_subselect::Item_in_subselect");
   left_expr= left_exp;
@@ -706,7 +784,7 @@ Item_allany_subselect::Item_allany_subselect(Item * left_exp,
 					     bool all_arg)
   :Item_in_subselect(), func_creator(fc), all(all_arg)
 {
-  DBUG_ENTER("Item_in_subselect::Item_in_subselect");
+  DBUG_ENTER("Item_allany_subselect::Item_allany_subselect");
   left_expr= left_exp;
   func= func_creator(all_arg);
   init(select_lex, new select_exists_subselect(this));
@@ -962,10 +1040,10 @@ my_decimal *Item_in_subselect::val_decimal(my_decimal *decimal_value)
           HAVING trigcond(<is_not_null_test>(ie))
 
   RETURN
-    RES_OK     - OK, either subquery was transformed, or appopriate
-                 predicates where injected into it.
-    RES_REDUCE - The subquery was reduced to non-subquery
-    RES_ERROR  - Error
+    RES_OK     Either subquery was transformed, or appopriate
+                       predicates where injected into it.
+    RES_REDUCE The subquery was reduced to non-subquery
+    RES_ERROR  Error
 */
 
 Item_subselect::trans_res
@@ -979,6 +1057,7 @@ Item_in_subselect::single_value_transformer(JOIN *join,
     Check that the right part of the subselect contains no more than one
     column. E.g. in SELECT 1 IN (SELECT * ..) the right part is (SELECT * ...)
   */
+  // psergey: duplicated_subselect_card_check
   if (select_lex->item_list.elements > 1)
   {
     my_error(ER_OPERAND_COLUMNS, MYF(0), 1);
@@ -1084,10 +1163,8 @@ Item_in_subselect::single_value_transformer(JOIN *join,
     }
     thd->lex->current_select= current;
 
-    //psergey-merge-jan11:
     /* We will refer to upper level cache array => we have to save it for SP */
     optimizer->keep_top_level_cache();
-    //:psergey-merge-jan11
 
     /*
       As far as  Item_ref_in_optimizer do not substitute itself on fix_fields
@@ -1100,6 +1177,7 @@ Item_in_subselect::single_value_transformer(JOIN *join,
 
     master_unit->uncacheable|= UNCACHEABLE_DEPENDENT;
   }
+
   if (!abort_on_null && left_expr->maybe_null && !pushed_cond_guards)
   {
     if (!(pushed_cond_guards= (bool*)join->thd->alloc(sizeof(bool))))
@@ -1107,6 +1185,60 @@ Item_in_subselect::single_value_transformer(JOIN *join,
     pushed_cond_guards[0]= TRUE;
   }
 
+  /*
+    If this IN predicate can be computed via materialization, do not
+    perform the IN -> EXISTS transformation.
+  */
+  if (exec_method == MATERIALIZATION)
+    DBUG_RETURN(RES_OK);
+
+  /* Perform the IN=>EXISTS transformation. */
+  DBUG_RETURN(single_value_in_to_exists_transformer(join, func));
+}
+
+
+/**
+  Transofrm an IN predicate into EXISTS via predicate injection.
+
+  @details The transformation injects additional predicates into the subquery
+  (and makes the subquery correlated) as follows.
+
+  - If the subquery has aggregates, GROUP BY, or HAVING, convert to
+
+    SELECT ie FROM ...  HAVING subq_having AND 
+                               trigcond(oe $cmp$ ref_or_null_helper<ie>)
+                                   
+    the addition is wrapped into trigger only when we want to distinguish
+    between NULL and FALSE results.
+
+  - Otherwise (no aggregates/GROUP BY/HAVING) convert it to one of the
+    following:
+
+    = If we don't need to distinguish between NULL and FALSE subquery:
+        
+      SELECT 1 FROM ... WHERE (oe $cmp$ ie) AND subq_where
+
+    = If we need to distinguish between those:
+
+      SELECT 1 FROM ...
+        WHERE  subq_where AND trigcond((oe $cmp$ ie) OR (ie IS NULL))
+        HAVING trigcond(<is_not_null_test>(ie))
+
+    @param join  Join object of the subquery (i.e. 'child' join).
+    @param func  Subquery comparison creator
+
+    @retval RES_OK     Either subquery was transformed, or appopriate
+                       predicates where injected into it.
+    @retval RES_REDUCE The subquery was reduced to non-subquery
+    @retval RES_ERROR  Error
+*/
+
+Item_subselect::trans_res
+Item_in_subselect::single_value_in_to_exists_transformer(JOIN * join, Comp_creator *func)
+{
+  SELECT_LEX *select_lex= join->select_lex;
+  DBUG_ENTER("Item_in_subselect::single_value_in_to_exists_transformer");
+
   select_lex->uncacheable|= UNCACHEABLE_DEPENDENT;
   if (join->having || select_lex->with_sum_func ||
       select_lex->group_list.elements)
@@ -1286,19 +1418,21 @@ Item_subselect::trans_res
 Item_in_subselect::row_value_transformer(JOIN *join)
 {
   SELECT_LEX *select_lex= join->select_lex;
-  Item *having_item= 0;
   uint cols_num= left_expr->cols();
-  bool is_having_used= (join->having || select_lex->with_sum_func ||
-                        select_lex->group_list.first ||
-                        !select_lex->table_list.elements);
+
   DBUG_ENTER("Item_in_subselect::row_value_transformer");
 
+  // psergey: duplicated_subselect_card_check
   if (select_lex->item_list.elements != left_expr->cols())
   {
     my_error(ER_OPERAND_COLUMNS, MYF(0), left_expr->cols());
     DBUG_RETURN(RES_ERROR);
   }
 
+  /*
+    Wrap the current IN predicate in an Item_in_optimizer. The actual
+    substitution in the Item tree takes place in Item_subselect::fix_fields.
+  */
   if (!substitution)
   {
     //first call for this unit
@@ -1330,6 +1464,48 @@ Item_in_subselect::row_value_transformer(JOIN *join)
     }
   }
 
+  /*
+    If this IN predicate can be computed via materialization, do not
+    perform the IN -> EXISTS transformation.
+  */
+  if (exec_method == MATERIALIZATION)
+    DBUG_RETURN(RES_OK);
+
+  /* Perform the IN=>EXISTS transformation. */
+  DBUG_RETURN(row_value_in_to_exists_transformer(join));
+}
+
+
+/**
+  Tranform a (possibly non-correlated) IN subquery into a correlated EXISTS.
+
+  @todo
+  The IF-ELSE below can be refactored so that there is no duplication of the
+  statements that create the new conditions. For this we have to invert the IF
+  and the FOR statements as this:
+  for (each left operand)
+    create the equi-join condition
+    if (is_having_used || !abort_on_null)
+      create the "is null" and is_not_null_test items
+    if (is_having_used)
+      add the equi-join and the null tests to HAVING
+    else
+      add the equi-join and the "is null" to WHERE
+      add the is_not_null_test to HAVING
+*/
+
+Item_subselect::trans_res
+Item_in_subselect::row_value_in_to_exists_transformer(JOIN * join)
+{
+  SELECT_LEX *select_lex= join->select_lex;
+  Item *having_item= 0;
+  uint cols_num= left_expr->cols();
+  bool is_having_used= (join->having || select_lex->with_sum_func ||
+                        select_lex->group_list.first ||
+                        !select_lex->table_list.elements);
+
+  DBUG_ENTER("Item_in_subselect::row_value_in_to_exists_transformer");
+
   select_lex->uncacheable|= UNCACHEABLE_DEPENDENT;
   if (is_having_used)
   {
@@ -1350,7 +1526,7 @@ Item_in_subselect::row_value_transformer(JOIN *join)
     for (uint i= 0; i < cols_num; i++)
     {
       DBUG_ASSERT((left_expr->fixed &&
-                   select_lex->ref_pointer_array[i]->fixed) ||
+                  select_lex->ref_pointer_array[i]->fixed) ||
                   (select_lex->ref_pointer_array[i]->type() == REF_ITEM &&
                    ((Item_ref*)(select_lex->ref_pointer_array[i]))->ref_type() ==
                     Item_ref::OUTER_REF));
@@ -1428,7 +1604,7 @@ Item_in_subselect::row_value_transformer(JOIN *join)
     {
       Item *item, *item_isnull;
       DBUG_ASSERT((left_expr->fixed &&
-                   select_lex->ref_pointer_array[i]->fixed) ||
+                  select_lex->ref_pointer_array[i]->fixed) ||
                   (select_lex->ref_pointer_array[i]->type() == REF_ITEM &&
                    ((Item_ref*)(select_lex->ref_pointer_array[i]))->ref_type() ==
                     Item_ref::OUTER_REF));
@@ -1573,9 +1749,7 @@ Item_in_subselect::select_in_like_transformer(JOIN *join, Comp_creator *func)
   }
 
   if (changed)
-  {
     DBUG_RETURN(RES_OK);
-  }
 
   thd->where= "IN/ALL/ANY subquery";
 
@@ -1583,6 +1757,8 @@ Item_in_subselect::select_in_like_transformer(JOIN *join, Comp_creator *func)
     In some optimisation cases we will not need this Item_in_optimizer
     object, but we can't know it here, but here we need address correct
     reference on left expresion.
+
+    //psergey: he means confluent cases like "... IN (SELECT 1)"
   */
   if (!optimizer)
   {
@@ -1610,7 +1786,6 @@ Item_in_subselect::select_in_like_transformer(JOIN *join, Comp_creator *func)
   */
   if (exec_method == NOT_TRANSFORMED)
     exec_method= IN_TO_EXISTS;
-  transformed= 1;
   arena= thd->activate_stmt_arena_if_needed(&backup);
 
   /*
@@ -1644,7 +1819,7 @@ err:
 
 void Item_in_subselect::print(String *str, enum_query_type query_type)
 {
-  if (transformed)
+  if (exec_method == IN_TO_EXISTS)
     str->append(STRING_WITH_LEN("<exists>"));
   else
   {
@@ -1658,7 +1833,10 @@ void Item_in_subselect::print(String *str, enum_query_type query_type)
 bool Item_in_subselect::fix_fields(THD *thd_arg, Item **ref)
 {
   bool result = 0;
-  
+
+  if (exec_method == SEMI_JOIN)
+    return !( (*ref)= new Item_int(1));
+
   if (thd_arg->lex->view_prepare_mode && left_expr && !left_expr->fixed)
     result = left_expr->fix_fields(thd_arg, &left_expr);
 
@@ -1666,20 +1844,188 @@ bool Item_in_subselect::fix_fields(THD *thd_arg, Item **ref)
 }
 
 
+/**
+  Try to create an engine to compute the subselect via materialization,
+  and if this fails, revert to execution via the IN=>EXISTS transformation.
+
+  @details
+    The purpose of this method is to hide the implementation details
+    of this Item's execution. The method creates a new engine for
+    materialized execution, and initializes the engine.
+
+    If this initialization fails
+    - either because it wasn't possible to create the needed temporary table
+      and its index,
+    - or because of a memory allocation error,
+    then we revert back to execution via the IN=>EXISTS tranformation.
+
+    The initialization of the new engine is divided in two parts - a permanent
+    one that lives across prepared statements, and one that is repeated for each
+    execution.
+
+  @returns
+    @retval TRUE  memory allocation error occurred
+    @retval FALSE an execution method was chosen successfully
+*/
+
+bool Item_in_subselect::setup_engine()
+{
+  subselect_hash_sj_engine *new_engine= NULL;
+  bool res= FALSE;
+
+  DBUG_ENTER("Item_in_subselect::setup_engine");
+
+  if (engine->engine_type() == subselect_engine::SINGLE_SELECT_ENGINE)
+  {
+    /* Create/initialize objects in permanent memory. */
+    subselect_single_select_engine *old_engine;
+    Query_arena *arena= thd->stmt_arena, backup;
+
+    old_engine= (subselect_single_select_engine*) engine;
+
+    if (arena->is_conventional())
+      arena= 0;
+    else
+      thd->set_n_backup_active_arena(arena, &backup);
+
+    if (!(new_engine= new subselect_hash_sj_engine(thd, this,
+                                                   old_engine)) ||
+        new_engine->init_permanent(unit->get_unit_column_types()))
+    {
+      Item_subselect::trans_res trans_res;
+      /*
+        If for some reason we cannot use materialization for this IN predicate,
+        delete all materialization-related objects, and apply the IN=>EXISTS
+        transformation.
+      */
+      delete new_engine;
+      new_engine= NULL;
+      exec_method= NOT_TRANSFORMED;
+      if (left_expr->cols() == 1)
+        trans_res= single_value_in_to_exists_transformer(old_engine->join,
+                                                         &eq_creator);
+      else
+        trans_res= row_value_in_to_exists_transformer(old_engine->join);
+      res= (trans_res != Item_subselect::RES_OK);
+    }
+    if (new_engine)
+      engine= new_engine;
+
+    if (arena)
+      thd->restore_active_arena(arena, &backup);
+  }
+  else
+  {
+    DBUG_ASSERT(engine->engine_type() == subselect_engine::HASH_SJ_ENGINE);
+    new_engine= (subselect_hash_sj_engine*) engine;
+  }
+
+  /* Initilizations done in runtime memory, repeated for each execution. */
+  if (new_engine)
+  {
+    /*
+      Reset the LIMIT 1 set in Item_exists_subselect::fix_length_and_dec.
+      TODO:
+      Currently we set the subquery LIMIT to infinity, and this is correct
+      because we forbid at parse time LIMIT inside IN subqueries (see
+      Item_in_subselect::test_limit). However, once we allow this, here
+      we should set the correct limit if given in the query.
+    */
+    unit->global_parameters->select_limit= NULL;
+    if ((res= new_engine->init_runtime()))
+      DBUG_RETURN(res);
+  }
+
+  DBUG_RETURN(res);
+}
+
+
+/**
+  Initialize the cache of the left operand of the IN predicate.
+
+  @note This method has the same purpose as alloc_group_fields(),
+  but it takes a different kind of collection of items, and the
+  list we push to is dynamically allocated.
+
+  @retval TRUE  if a memory allocation error occurred or the cache is
+                not applicable to the current query
+  @retval FALSE if success
+*/
+
+bool Item_in_subselect::init_left_expr_cache()
+{
+  JOIN *outer_join;
+  Next_select_func end_select;
+  bool use_result_field= FALSE;
+
+  outer_join= unit->outer_select()->join;
+  /*
+    An IN predicate might be evaluated in a query for which all tables have
+    been optimzied away.
+  */ 
+  if (!outer_join || !outer_join->tables || !outer_join->tables_list)
+    return TRUE;
+  /*
+    If we use end_[send | write]_group to handle complete rows of the outer
+    query, make the cache of the left IN operand use Item_field::result_field
+    instead of Item_field::field.  We need this because normally
+    Cached_item_field uses Item::field to fetch field data, while
+    copy_ref_key() that copies the left IN operand into a lookup key uses
+    Item::result_field. In the case end_[send | write]_group result_field is
+    one row behind field.
+  */
+  end_select= outer_join->join_tab[outer_join->tables-1].next_select;
+  if (end_select == end_send_group || end_select == end_write_group)
+    use_result_field= TRUE;
+
+  if (!(left_expr_cache= new List<Cached_item>))
+    return TRUE;
+
+  for (uint i= 0; i < left_expr->cols(); i++)
+  {
+    Cached_item *cur_item_cache= new_Cached_item(thd,
+                                                 left_expr->element_index(i),
+                                                 use_result_field);
+    if (!cur_item_cache || left_expr_cache->push_front(cur_item_cache))
+      return TRUE;
+  }
+  return FALSE;
+}
+
+
+/*
+  Callback to test if an IN predicate is expensive.
+
+  @details
+    IN predicates are considered expensive only if they will be executed via
+    materialization. The return value affects the behavior of
+    make_cond_for_table() in such a way that it is unchanged when we use
+    the IN=>EXISTS transformation to compute IN.
+
+  @retval TRUE  if the predicate is expensive
+  @retval FALSE otherwise
+*/
+
+bool Item_in_subselect::is_expensive_processor(uchar *arg)
+{
+  return exec_method == MATERIALIZATION;
+}
+
+
 Item_subselect::trans_res
 Item_allany_subselect::select_transformer(JOIN *join)
 {
-  transformed= 1;
+  DBUG_ENTER("Item_allany_subselect::select_transformer");
   exec_method= IN_TO_EXISTS;
   if (upper_item)
     upper_item->show= 1;
-  return select_in_like_transformer(join, func);
+  DBUG_RETURN(select_in_like_transformer(join, func));
 }
 
 
 void Item_allany_subselect::print(String *str, enum_query_type query_type)
 {
-  if (transformed)
+  if (exec_method == IN_TO_EXISTS)
     str->append(STRING_WITH_LEN("<exists>"));
   else
   {
@@ -1702,11 +2048,10 @@ void subselect_engine::set_thd(THD *thd_arg)
 
 subselect_single_select_engine::
 subselect_single_select_engine(st_select_lex *select,
-			       select_subselect *result_arg,
+			       select_result_interceptor *result_arg,
 			       Item_subselect *item_arg)
   :subselect_engine(item_arg, result_arg),
-   prepared(0), optimized(0), executed(0),
-   select_lex(select), join(0)
+   prepared(0), executed(0), select_lex(select), join(0)
 {
   select_lex->master_unit()->item= item_arg;
 }
@@ -1715,7 +2060,7 @@ subselect_single_select_engine(st_select_lex *select,
 void subselect_single_select_engine::cleanup()
 {
   DBUG_ENTER("subselect_single_select_engine::cleanup");
-  prepared= optimized= executed= 0;
+  prepared= executed= 0;
   join= 0;
   result->cleanup();
   DBUG_VOID_RETURN;
@@ -1758,6 +2103,7 @@ bool subselect_union_engine::no_rows()
   return test(!unit->fake_select_lex->join->send_records);
 }
 
+
 void subselect_uniquesubquery_engine::cleanup()
 {
   DBUG_ENTER("subselect_uniquesubquery_engine::cleanup");
@@ -1770,7 +2116,7 @@ void subselect_uniquesubquery_engine::cleanup()
 
 
 subselect_union_engine::subselect_union_engine(st_select_lex_unit *u,
-					       select_subselect *result_arg,
+					       select_result_interceptor *result_arg,
 					       Item_subselect *item_arg)
   :subselect_engine(item_arg, result_arg)
 {
@@ -1781,6 +2127,32 @@ subselect_union_engine::subselect_union_engine(st_select_lex_unit *u,
 }
 
 
+/**
+  Create and prepare the JOIN object that represents the query execution
+  plan for the subquery.
+
+  @detail
+  This method is called from Item_subselect::fix_fields. For prepared
+  statements it is called both during the PREPARE and EXECUTE phases in the
+  following ways:
+  - During PREPARE the optimizer needs some properties
+    (join->fields_list.elements) of the JOIN to proceed with preparation of
+    the remaining query (namely to complete ::fix_fields for the subselect
+    related classes. In the end of PREPARE the JOIN is deleted.
+  - When we EXECUTE the query, Item_subselect::fix_fields is called again, and
+    the JOIN object is re-created again, prepared and executed. In the end of
+    execution it is deleted.
+  In all cases the JOIN is created in runtime memory (not in the permanent
+  memory root).
+
+  @todo
+  Re-check what properties of 'join' are needed during prepare, and see if
+  we can avoid creating a JOIN during JOIN::prepare of the outer join.
+
+  @retval 0  if success
+  @retval 1  if error
+*/
+
 int subselect_single_select_engine::prepare()
 {
   if (prepared)
@@ -1818,8 +2190,8 @@ int subselect_union_engine::prepare()
 
 int subselect_uniquesubquery_engine::prepare()
 {
-  //this never should be called
-  DBUG_ASSERT(0);
+  /* Should never be called. */
+  DBUG_ASSERT(FALSE);
   return 1;
 }
 
@@ -1866,6 +2238,7 @@ void subselect_engine::set_row(List<Item> &item_list, Item_cache **row)
     if (!(row[i]= Item_cache::get_cache(sel_item)))
       return;
     row[i]->setup(sel_item);
+ //psergey-backport-timours:   row[i]->store(sel_item);
   }
   if (item_list.elements > 1)
     res_type= ROW_RESULT;
@@ -1913,11 +2286,10 @@ int subselect_single_select_engine::exec()
   char const *save_where= thd->where;
   SELECT_LEX *save_select= thd->lex->current_select;
   thd->lex->current_select= select_lex;
-  if (!optimized)
+  if (!join->optimized)
   {
     SELECT_LEX_UNIT *unit= select_lex->master_unit();
 
-    optimized= 1;
     unit->set_limit(unit->global_parameters);
     if (join->optimize())
     {
@@ -2262,7 +2634,8 @@ int subselect_uniquesubquery_engine::exec()
 subselect_uniquesubquery_engine::~subselect_uniquesubquery_engine()
 {
   /* Tell handler we don't need the index anymore */
-  tab->table->file->ha_index_end();
+  //psergey-merge-todo: the following was gone in 6.0:
+ //psergey-merge: don't need this after all: tab->table->file->ha_index_end();
 }
 
 
@@ -2270,7 +2643,7 @@ subselect_uniquesubquery_engine::~subselect_uniquesubquery_engine()
   Index-lookup subselect 'engine' - run the subquery
 
   SYNOPSIS
-    subselect_uniquesubquery_engine:exec()
+    subselect_indexsubquery_engine:exec()
       full_scan 
 
   DESCRIPTION
@@ -2494,10 +2867,20 @@ void subselect_union_engine::print(String *str, enum_query_type query_type)
 void subselect_uniquesubquery_engine::print(String *str,
                                             enum_query_type query_type)
 {
+  char *table_name= tab->table->s->table_name.str;
   str->append(STRING_WITH_LEN("<primary_index_lookup>("));
   tab->ref.items[0]->print(str, query_type);
   str->append(STRING_WITH_LEN(" in "));
-  str->append(tab->table->s->table_name.str, tab->table->s->table_name.length);
+  if (tab->table->s->table_category == TABLE_CATEGORY_TEMPORARY)
+  {
+    /*
+      Temporary tables' names change across runs, so they can't be used for
+      EXPLAIN EXTENDED.
+    */
+    str->append(STRING_WITH_LEN("<temporary table>"));
+  }
+  else
+    str->append(table_name, tab->table->s->table_name.length);
   KEY *key_info= tab->table->key_info+ tab->ref.key;
   str->append(STRING_WITH_LEN(" on "));
   str->append(key_info->name);
@@ -2509,6 +2892,29 @@ void subselect_uniquesubquery_engine::print(String *str,
   str->append(')');
 }
 
+/*
+TODO:
+The above ::print method should be changed as below. Do it after
+all other tests pass.
+
+void subselect_uniquesubquery_engine::print(String *str)
+{
+  KEY *key_info= tab->table->key_info + tab->ref.key;
+  str->append(STRING_WITH_LEN("<primary_index_lookup>("));
+  for (uint i= 0; i < key_info->key_parts; i++)
+    tab->ref.items[i]->print(str);
+  str->append(STRING_WITH_LEN(" in "));
+  str->append(tab->table->s->table_name.str, tab->table->s->table_name.length);
+  str->append(STRING_WITH_LEN(" on "));
+  str->append(key_info->name);
+  if (cond)
+  {
+    str->append(STRING_WITH_LEN(" where "));
+    cond->print(str);
+  }
+  str->append(')');
+}
+*/
 
 void subselect_indexsubquery_engine::print(String *str,
                                            enum_query_type query_type)
@@ -2548,7 +2954,7 @@ void subselect_indexsubquery_engine::print(String *str,
 */
 
 bool subselect_single_select_engine::change_result(Item_subselect *si,
-                                                 select_subselect *res)
+                                                 select_result_interceptor *res)
 {
   item= si;
   result= res;
@@ -2569,7 +2975,7 @@ bool subselect_single_select_engine::change_result(Item_subselect *si,
 */
 
 bool subselect_union_engine::change_result(Item_subselect *si,
-                                         select_subselect *res)
+                                           select_result_interceptor *res)
 {
   item= si;
   int rc= unit->change_result(res, result);
@@ -2591,7 +2997,7 @@ bool subselect_union_engine::change_result(Item_subselect *si,
 */
 
 bool subselect_uniquesubquery_engine::change_result(Item_subselect *si,
-                                                  select_subselect *res)
+                                                    select_result_interceptor *res)
 {
   DBUG_ASSERT(0);
   return TRUE;
@@ -2661,3 +3067,334 @@ bool subselect_uniquesubquery_engine::no_tables()
   /* returning value is correct, but this method should never be called */
   return 0;
 }
+
+
+/******************************************************************************
+  WL#1110 - Implementation of class subselect_hash_sj_engine
+******************************************************************************/
+
+
+/**
+  Create all structures needed for IN execution that can live between PS
+  reexecution.
+
+  @detail
+  - Create a temporary table to store the result of the IN subquery. The
+    temporary table has one hash index on all its columns.
+  - Create a new result sink that sends the result stream of the subquery to
+    the temporary table,
+  - Create and initialize a new JOIN_TAB, and TABLE_REF objects to perform
+    lookups into the indexed temporary table.
+
+  @notice:
+    Currently Item_subselect::init() already chooses and creates at parse
+    time an engine with a corresponding JOIN to execute the subquery.
+
+  @retval TRUE  if error
+  @retval FALSE otherwise
+*/
+
+bool subselect_hash_sj_engine::init_permanent(List<Item> *tmp_columns)
+{
+  /* The result sink where we will materialize the subquery result. */
+  select_union  *tmp_result_sink;
+  /* The table into which the subquery is materialized. */
+  TABLE         *tmp_table;
+  KEY           *tmp_key; /* The only index on the temporary table. */
+  uint          tmp_key_parts; /* Number of keyparts in tmp_key. */
+  Item_in_subselect *item_in= (Item_in_subselect *) item;
+
+  DBUG_ENTER("subselect_hash_sj_engine::init_permanent");
+
+  /* 1. Create/initialize materialization related objects. */
+
+  /*
+    Create and initialize a select result interceptor that stores the
+    result stream in a temporary table. The temporary table itself is
+    managed (created/filled/etc) internally by the interceptor.
+  */
+  if (!(tmp_result_sink= new select_union))
+    DBUG_RETURN(TRUE);
+  if (tmp_result_sink->create_result_table(
+                         thd, tmp_columns, TRUE,
+                         thd->options | TMP_TABLE_ALL_COLUMNS,
+                         "materialized subselect"))
+    DBUG_RETURN(TRUE);
+
+  tmp_table= tmp_result_sink->table;
+  tmp_key= tmp_table->key_info;
+  tmp_key_parts= tmp_key->key_parts;
+
+  /*
+     If the subquery has blobs, or the total key lenght is bigger than some
+     length, then the created index cannot be used for lookups and we
+     can't use hash semi join. If this is the case, delete the temporary
+     table since it will not be used, and tell the caller we failed to
+     initialize the engine.
+  */
+  if (tmp_table->s->keys == 0)
+  {
+#ifndef DBUG_OFF
+    handlerton *tmp_table_hton= tmp_table->s->db_type();
+#ifdef USE_MARIA_FOR_TMP_TABLES 
+    DBUG_ASSERT(tmp_table_hton == maria_hton);
+#else
+    DBUG_ASSERT(tmp_table_hton == myisam_hton);
+#endif
+#endif
+    DBUG_ASSERT(
+      tmp_table->s->uniques ||
+      tmp_table->key_info->key_length >= tmp_table->file->max_key_length() ||
+      tmp_table->key_info->key_parts > tmp_table->file->max_key_parts());
+    free_tmp_table(thd, tmp_table);
+    delete result;
+    result= NULL;
+    DBUG_RETURN(TRUE);
+  }
+  result= tmp_result_sink;
+
+  /*
+    Make sure there is only one index on the temp table, and it doesn't have
+    the extra key part created when s->uniques > 0.
+  */
+  DBUG_ASSERT(tmp_table->s->keys == 1 && tmp_columns->elements == tmp_key_parts);
+
+
+  /* 2. Create/initialize execution related objects. */
+
+  /*
+    Create and initialize the JOIN_TAB that represents an index lookup
+    plan operator into the materialized subquery result. Notice that:
+    - this JOIN_TAB has no corresponding JOIN (and doesn't need one), and
+    - here we initialize only those members that are used by
+      subselect_uniquesubquery_engine, so these objects are incomplete.
+  */ 
+  if (!(tab= (JOIN_TAB*) thd->alloc(sizeof(JOIN_TAB))))
+    DBUG_RETURN(TRUE);
+  tab->table= tmp_table;
+  tab->ref.key= 0; /* The only temp table index. */
+  tab->ref.key_length= tmp_key->key_length;
+  if (!(tab->ref.key_buff=
+        (uchar*) thd->calloc(ALIGN_SIZE(tmp_key->key_length) * 2)) ||
+      !(tab->ref.key_copy=
+        (store_key**) thd->alloc((sizeof(store_key*) *
+                                  (tmp_key_parts + 1)))) ||
+      !(tab->ref.items=
+        (Item**) thd->alloc(sizeof(Item*) * tmp_key_parts)))
+    DBUG_RETURN(TRUE);
+
+  KEY_PART_INFO *cur_key_part= tmp_key->key_part;
+  store_key **ref_key= tab->ref.key_copy;
+  uchar *cur_ref_buff= tab->ref.key_buff;
+
+  /*
+    Create an artificial condition to post-filter those rows matched by index
+    lookups that cannot be distinguished by the index lookup procedure, e.g.
+    because of truncation. Prepared statements execution requires that
+    fix_fields is called for every execution. In order to call fix_fields we
+    need to create a Name_resolution_context and a corresponding TABLE_LIST
+    for the temporary table for the subquery, so that all column references
+    to the materialized subquery table can be resolved correctly.
+  */
+  DBUG_ASSERT(cond == NULL);
+  if (!(cond= new Item_cond_and))
+    DBUG_RETURN(TRUE);
+  /*
+    Table reference for tmp_table that is used to resolve column references
+    (Item_fields) to columns in tmp_table.
+  */
+  TABLE_LIST *tmp_table_ref;
+  if (!(tmp_table_ref= (TABLE_LIST*) thd->alloc(sizeof(TABLE_LIST))))
+    DBUG_RETURN(TRUE);
+
+  tmp_table_ref->init_one_table("", "materialized subselect", TL_READ);
+  tmp_table_ref->table= tmp_table;
+
+  /* Name resolution context for all tmp_table columns created below. */
+  Name_resolution_context *context= new Name_resolution_context;
+  context->init();
+  context->first_name_resolution_table=
+    context->last_name_resolution_table= tmp_table_ref;
+  
+  for (uint i= 0; i < tmp_key_parts; i++, cur_key_part++, ref_key++)
+  {
+    Item_func_eq *eq_cond; /* New equi-join condition for the current column. */
+    /* Item for the corresponding field from the materialized temp table. */
+    Item_field *right_col_item;
+    int null_count= test(cur_key_part->field->real_maybe_null());
+    tab->ref.items[i]= item_in->left_expr->element_index(i);
+
+    if (!(right_col_item= new Item_field(thd, context, cur_key_part->field)) ||
+        !(eq_cond= new Item_func_eq(tab->ref.items[i], right_col_item)) ||
+        ((Item_cond_and*)cond)->add(eq_cond))
+    {
+      delete cond;
+      cond= NULL;
+      DBUG_RETURN(TRUE);
+    }
+
+    *ref_key= new store_key_item(thd, cur_key_part->field,
+                                 /* TODO:
+                                    the NULL byte is taken into account in
+                                    cur_key_part->store_length, so instead of
+                                    cur_ref_buff + test(maybe_null), we could
+                                    use that information instead.
+                                 */
+                                 cur_ref_buff + null_count,
+                                 null_count ? tab->ref.key_buff : 0,
+                                 cur_key_part->length, tab->ref.items[i]);
+    cur_ref_buff+= cur_key_part->store_length;
+  }
+  *ref_key= NULL; /* End marker. */
+  tab->ref.key_err= 1;
+  tab->ref.key_parts= tmp_key_parts;
+
+  if (cond->fix_fields(thd, &cond))
+    DBUG_RETURN(TRUE);
+
+  DBUG_RETURN(FALSE);
+}
+
+
+/**
+  Initialize members of the engine that need to be re-initilized at each
+  execution.
+
+  @retval TRUE  if a memory allocation error occurred
+  @retval FALSE if success
+*/
+
+bool subselect_hash_sj_engine::init_runtime()
+{
+  /*
+    Create and optimize the JOIN that will be used to materialize
+    the subquery if not yet created.
+  */
+  materialize_engine->prepare();
+  /*
+    Repeat name resolution for 'cond' since cond is not part of any
+    clause of the query, and it is not 'fixed' during JOIN::prepare.
+  */
+  if (cond && !cond->fixed && cond->fix_fields(thd, &cond))
+    return TRUE;
+  /* Let our engine reuse this query plan for materialization. */
+  materialize_join= materialize_engine->join;
+  materialize_join->change_result(result);
+  return FALSE;
+}
+
+
+subselect_hash_sj_engine::~subselect_hash_sj_engine()
+{
+  delete result;
+  if (tab)
+    free_tmp_table(thd, tab->table);
+}
+
+
+/**
+  Cleanup performed after each PS execution.
+
+  @detail
+  Called in the end of JOIN::prepare for PS from Item_subselect::cleanup.
+*/
+
+void subselect_hash_sj_engine::cleanup()
+{
+  is_materialized= FALSE;
+  result->cleanup(); /* Resets the temp table as well. */
+  materialize_engine->cleanup();
+  subselect_uniquesubquery_engine::cleanup();
+}
+
+
+/**
+  Execute a subquery IN predicate via materialization.
+
+  @detail
+  If needed materialize the subquery into a temporary table, then
+  copmpute the predicate via a lookup into this table.
+
+  @retval TRUE  if error
+  @retval FALSE otherwise
+*/
+
+int subselect_hash_sj_engine::exec()
+{
+  Item_in_subselect *item_in= (Item_in_subselect *) item;
+
+  DBUG_ENTER("subselect_hash_sj_engine::exec");
+
+  /*
+    Optimize and materialize the subquery during the first execution of
+    the subquery predicate.
+  */
+  if (!is_materialized)
+  {
+    int res= 0;
+    SELECT_LEX *save_select= thd->lex->current_select;
+    thd->lex->current_select= materialize_engine->select_lex;
+    if ((res= materialize_join->optimize()))
+      goto err; /* purecov: inspected */
+    materialize_join->exec();
+    if ((res= test(materialize_join->error || thd->is_fatal_error)))
+      goto err;
+
+    /*
+      TODO:
+      - Unlock all subquery tables as we don't need them. To implement this
+        we need to add new functionality to JOIN::join_free that can unlock
+        all tables in a subquery (and all its subqueries).
+      - The temp table used for grouping in the subquery can be freed
+        immediately after materialization (yet it's done together with
+        unlocking).
+     */
+    is_materialized= TRUE;
+    /*
+      If the subquery returned no rows, the temporary table is empty, so we know
+      directly that the result of IN is FALSE. We first update the table
+      statistics, then we test if the temporary table for the query result is
+      empty.
+    */
+    tab->table->file->info(HA_STATUS_VARIABLE);
+    if (!tab->table->file->stats.records)
+    {
+      empty_result_set= TRUE;
+      item_in->value= FALSE;
+      /* TODO: check we need this: item_in->null_value= FALSE; */
+      DBUG_RETURN(FALSE);
+    }
+    /* Set tmp_param only if its usable, i.e. tmp_param->copy_field != NULL. */
+    tmp_param= &(item_in->unit->outer_select()->join->tmp_table_param);
+    if (tmp_param && !tmp_param->copy_field)
+      tmp_param= NULL;
+
+err:
+    thd->lex->current_select= save_select;
+    if (res)
+      DBUG_RETURN(res);
+  }
+
+  /*
+    Lookup the left IN operand in the hash index of the materialized subquery.
+  */
+  DBUG_RETURN(subselect_uniquesubquery_engine::exec());
+}
+
+
+/**
+  Print the state of this engine into a string for debugging and views.
+*/
+
+void subselect_hash_sj_engine::print(String *str, enum_query_type query_type)
+{
+  str->append(STRING_WITH_LEN(" <materialize> ("));
+  materialize_engine->print(str, query_type);
+  str->append(STRING_WITH_LEN(" ), "));
+  if (tab)
+    subselect_uniquesubquery_engine::print(str, query_type);
+  else
+    str->append(STRING_WITH_LEN(
+           "<the access method for lookups is not yet created>"
+         ));
+}
diff --git a/sql/item_subselect.h b/sql/item_subselect.h
index 1085011915d..74faa7b84ac 100644
--- a/sql/item_subselect.h
+++ b/sql/item_subselect.h
@@ -22,9 +22,11 @@
 class st_select_lex;
 class st_select_lex_unit;
 class JOIN;
-class select_subselect;
+class select_result_interceptor;
 class subselect_engine;
+class subselect_hash_sj_engine;
 class Item_bool_func2;
+class Cached_item;
 
 /* base class for subselects */
 
@@ -34,7 +36,18 @@ class Item_subselect :public Item_result_field
 public:
   /* thread handler, will be assigned in fix_fields only */
   THD *thd;
-  /* substitution instead of subselect in case of optimization */
+  /* 
+    Used inside Item_subselect::fix_fields() according to this scenario:
+      > Item_subselect::fix_fields
+        > engine->prepare
+          > child_join->prepare
+            (Here we realize we need to do the rewrite and set
+             substitution= some new Item, eg. Item_in_optimizer )
+          < child_join->prepare
+        < engine->prepare
+        *ref= substitution;
+      < Item_subselect::fix_fields
+  */
   Item *substitution;
 public:
   /* unit of subquery */
@@ -54,7 +67,7 @@ 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
@@ -81,12 +94,12 @@ public:
   virtual subs_type substype() { return UNKNOWN_SUBS; }
 
   /*
-     We need this method, because some compilers do not allow 'this'
-     pointer in constructor initialization list, but we need pass pointer
-     to subselect Item class to select_subselect classes constructor.
+    We need this method, because some compilers do not allow 'this'
+    pointer in constructor initialization list, but we need to pass a pointer
+    to subselect Item class to select_result_interceptor's constructor.
   */
   virtual void init (st_select_lex *select_lex,
-		     select_subselect *result);
+		     select_result_interceptor *result);
 
   ~Item_subselect();
   void cleanup();
@@ -148,8 +161,9 @@ public:
     @return the SELECT_LEX structure associated with this Item
   */
   st_select_lex* get_select_lex();
+  const char *func_name() const { DBUG_ASSERT(0); return "subselect"; }
 
-  friend class select_subselect;
+  friend class select_result_interceptor;
   friend class Item_in_optimizer;
   friend bool Item_field::fix_fields(THD *, Item **);
   friend int  Item_field::fix_outer_field(THD *, Field **, Item **);
@@ -258,14 +272,15 @@ public:
 };
 
 
-/*
-  IN subselect: this represents "left_exr IN (SELECT ...)"
+/**
+  Representation of IN subquery predicates of the form
+  "left_expr IN (SELECT ...)".
 
+  @detail
   This class has: 
-   - (as a descendant of Item_subselect) a "subquery execution engine" which 
-      allows it to evaluate subqueries. (and this class participates in
-      execution by having was_null variable where part of execution result
-      is stored.
+   - A "subquery execution engine" (as a subclass of Item_subselect) that allows
+     it to evaluate subqueries. (and this class participates in execution by
+     having was_null variable where part of execution result is stored.
    - Transformation methods (todo: more on this).
 
   This class is not used directly, it is "wrapped" into Item_in_optimizer
@@ -278,6 +293,13 @@ public:
   Item *left_expr;
 protected:
   /*
+    Cache of the left operand of the subquery predicate. Allocated in the
+    runtime memory root, for each execution, thus need not be freed.
+  */
+  List<Cached_item> *left_expr_cache;
+  bool first_execution;
+
+  /*
     expr & optimizer used in subselect rewriting to store Item for
     all JOIN in UNION
   */
@@ -285,7 +307,6 @@ protected:
   Item_in_optimizer *optimizer;
   bool was_null;
   bool abort_on_null;
-  bool transformed;
 public:
   /* Used to trigger on/off conditions that were pushed down to subselect */
   bool *pushed_cond_guards;
@@ -344,10 +365,11 @@ public:
 
   Item_in_subselect(Item * left_expr, st_select_lex *select_lex);
   Item_in_subselect()
-    :Item_exists_subselect(), optimizer(0), abort_on_null(0), transformed(0),
-     pushed_cond_guards(NULL), exec_method(NOT_TRANSFORMED), upper_item(0)
+    :Item_exists_subselect(), left_expr_cache(0), first_execution(TRUE),
+    optimizer(0), abort_on_null(0), pushed_cond_guards(NULL),
+    exec_method(NOT_TRANSFORMED), upper_item(0)
   {}
-
+  void cleanup();
   subs_type substype() { return IN_SUBS; }
   void reset() 
   {
@@ -359,6 +381,10 @@ public:
   trans_res select_in_like_transformer(JOIN *join, Comp_creator *func);
   trans_res single_value_transformer(JOIN *join, Comp_creator *func);
   trans_res row_value_transformer(JOIN * join);
+  trans_res single_value_in_to_exists_transformer(JOIN * join,
+                                                  Comp_creator *func);
+  trans_res row_value_in_to_exists_transformer(JOIN * join);
+  virtual bool exec();
   longlong val_int();
   double val_real();
   String *val_str(String*);
@@ -370,10 +396,15 @@ public:
   bool test_limit(st_select_lex_unit *unit);
   virtual void print(String *str, enum_query_type query_type);
   bool fix_fields(THD *thd, Item **ref);
+  bool setup_engine();
+  bool init_left_expr_cache();
+  bool is_expensive_processor(uchar *arg);
 
   friend class Item_ref_null_helper;
   friend class Item_is_not_null_test;
+  friend class Item_in_optimizer;
   friend class subselect_indexsubquery_engine;
+  friend class subselect_hash_sj_engine;
 };
 
 
@@ -398,7 +429,7 @@ public:
 class subselect_engine: public Sql_alloc
 {
 protected:
-  select_subselect *result; /* results storage class */
+  select_result_interceptor *result; /* results storage class */
   THD *thd; /* pointer to current THD */
   Item_subselect *item; /* item, that use this engine */
   enum Item_result res_type; /* type of results */
@@ -406,7 +437,11 @@ protected:
   bool maybe_null; /* may be null (first item in select) */
 public:
 
-  subselect_engine(Item_subselect *si, select_subselect *res)
+  enum enum_engine_type {ABSTRACT_ENGINE, SINGLE_SELECT_ENGINE,
+                         UNION_ENGINE, UNIQUESUBQUERY_ENGINE,
+                         INDEXSUBQUERY_ENGINE, HASH_SJ_ENGINE};
+
+  subselect_engine(Item_subselect *si, select_result_interceptor *res)
     :thd(0)
   {
     result= res;
@@ -456,11 +491,13 @@ public:
   virtual table_map upper_select_const_tables()= 0;
   static table_map calc_const_tables(TABLE_LIST *);
   virtual void print(String *str, enum_query_type query_type)= 0;
-  virtual bool change_result(Item_subselect *si, select_subselect *result)= 0;
+  virtual bool change_result(Item_subselect *si,
+                             select_result_interceptor *result)= 0;
   virtual bool no_tables()= 0;
   virtual bool is_executed() const { return FALSE; }
   /* Check if subquery produced any rows during last query execution */
   virtual bool no_rows() = 0;
+  virtual enum_engine_type engine_type() { return ABSTRACT_ENGINE; }
 
 protected:
   void set_row(List<Item> &item_list, Item_cache **row);
@@ -476,7 +513,7 @@ class subselect_single_select_engine: public subselect_engine
   JOIN * join; /* corresponding JOIN structure */
 public:
   subselect_single_select_engine(st_select_lex *select,
-				 select_subselect *result,
+				 select_result_interceptor *result,
 				 Item_subselect *item);
   void cleanup();
   int prepare();
@@ -487,11 +524,15 @@ public:
   void exclude();
   table_map upper_select_const_tables();
   virtual void print (String *str, enum_query_type query_type);
-  bool change_result(Item_subselect *si, select_subselect *result);
+  bool change_result(Item_subselect *si, select_result_interceptor *result);
   bool no_tables();
   bool may_be_null();
   bool is_executed() const { return executed; }
   bool no_rows();
+  virtual enum_engine_type engine_type() { return SINGLE_SELECT_ENGINE; }
+
+  friend class subselect_hash_sj_engine;
+  friend class Item_in_subselect;
 };
 
 
@@ -500,7 +541,7 @@ class subselect_union_engine: public subselect_engine
   st_select_lex_unit *unit;  /* corresponding unit structure */
 public:
   subselect_union_engine(st_select_lex_unit *u,
-			 select_subselect *result,
+			 select_result_interceptor *result,
 			 Item_subselect *item);
   void cleanup();
   int prepare();
@@ -511,10 +552,11 @@ public:
   void exclude();
   table_map upper_select_const_tables();
   virtual void print (String *str, enum_query_type query_type);
-  bool change_result(Item_subselect *si, select_subselect *result);
+  bool change_result(Item_subselect *si, select_result_interceptor *result);
   bool no_tables();
   bool is_executed() const;
   bool no_rows();
+  virtual enum_engine_type engine_type() { return UNION_ENGINE; }
 };
 
 
@@ -568,11 +610,12 @@ public:
   void exclude();
   table_map upper_select_const_tables() { return 0; }
   virtual void print (String *str, enum_query_type query_type);
-  bool change_result(Item_subselect *si, select_subselect *result);
+  bool change_result(Item_subselect *si, select_result_interceptor *result);
   bool no_tables();
   int scan_table();
   bool copy_ref_key();
   bool no_rows() { return empty_result_set; }
+  virtual enum_engine_type engine_type() { return UNIQUESUBQUERY_ENGINE; }
 };
 
 
@@ -622,6 +665,7 @@ public:
   {}
   int exec();
   virtual void print (String *str, enum_query_type query_type);
+  virtual enum_engine_type engine_type() { return INDEXSUBQUERY_ENGINE; }
 };
 
 
@@ -630,9 +674,58 @@ inline bool Item_subselect::is_evaluated() const
   return engine->is_executed();
 }
 
+
 inline bool Item_subselect::is_uncacheable() const
 {
   return engine->uncacheable();
 }
 
 
+/**
+  Compute an IN predicate via a hash semi-join. The subquery is materialized
+  during the first evaluation of the IN predicate. The IN predicate is executed
+  via the functionality inherited from subselect_uniquesubquery_engine.
+*/
+
+class subselect_hash_sj_engine: public subselect_uniquesubquery_engine
+{
+protected:
+  /* TRUE if the subquery was materialized into a temp table. */
+  bool is_materialized;
+  /*
+    The old engine already chosen at parse time and stored in permanent memory.
+    Through this member we can re-create and re-prepare materialize_join for
+    each execution of a prepared statement. We akso resuse the functionality
+    of subselect_single_select_engine::[prepare | cols].
+  */
+  subselect_single_select_engine *materialize_engine;
+  /*
+    QEP to execute the subquery and materialize its result into a
+    temporary table. Created during the first call to exec().
+  */
+  JOIN *materialize_join;
+  /* Temp table context of the outer select's JOIN. */
+  TMP_TABLE_PARAM *tmp_param;
+
+public:
+  subselect_hash_sj_engine(THD *thd, Item_subselect *in_predicate,
+                               subselect_single_select_engine *old_engine)
+    :subselect_uniquesubquery_engine(thd, NULL, in_predicate, NULL),
+    is_materialized(FALSE), materialize_engine(old_engine),
+    materialize_join(NULL), tmp_param(NULL)
+  {}
+  ~subselect_hash_sj_engine();
+
+  bool init_permanent(List<Item> *tmp_columns);
+  bool init_runtime();
+  void cleanup();
+  int prepare() { return 0; }
+  int exec();
+  virtual void print (String *str, enum_query_type query_type);
+  uint cols()
+  {
+    return materialize_engine->cols();
+  }
+  virtual enum_engine_type engine_type() { return HASH_SJ_ENGINE; }
+};
+
diff --git a/sql/opt_range.cc b/sql/opt_range.cc
index c985eb60ee1..ad0302bdb4d 100644
--- a/sql/opt_range.cc
+++ b/sql/opt_range.cc
@@ -5493,7 +5493,7 @@ static SEL_TREE *get_mm_tree(RANGE_OPT_PARAM *param,COND *cond)
     DBUG_RETURN(tree);
   }
   /* Here when simple cond */
-  if (cond->const_item())
+  if (cond->const_item() && !cond->is_expensive())
   {
     /*
       During the cond->val_int() evaluation we can come across a subselect 
diff --git a/sql/sql_lex.cc b/sql/sql_lex.cc
index b161da86dbd..2ee73ff962c 100644
--- a/sql/sql_lex.cc
+++ b/sql/sql_lex.cc
@@ -2076,16 +2076,28 @@ void st_select_lex::print_limit(THD *thd,
 {
   SELECT_LEX_UNIT *unit= master_unit();
   Item_subselect *item= unit->item;
-  if (item && unit->global_parameters == this &&
-      (item->substype() == Item_subselect::EXISTS_SUBS ||
-       item->substype() == Item_subselect::IN_SUBS ||
-       item->substype() == Item_subselect::ALL_SUBS))
+
+  if (item && unit->global_parameters == this)
   {
-    DBUG_ASSERT(!item->fixed ||
-                (select_limit->val_int() == LL(1) && offset_limit == 0));
-    return;
+    Item_subselect::subs_type subs_type= item->substype();
+    if (subs_type == Item_subselect::EXISTS_SUBS ||
+        subs_type == Item_subselect::IN_SUBS ||
+        subs_type == Item_subselect::ALL_SUBS)
+    {
+      DBUG_ASSERT(!item->fixed ||
+                  /*
+                    If not using materialization both:
+                    select_limit == 1, and there should be no offset_limit.
+                  */
+                  (((subs_type == Item_subselect::IN_SUBS) &&
+                    ((Item_in_subselect*)item)->exec_method ==
+                    Item_in_subselect::MATERIALIZATION) ?
+                   TRUE :
+                   (select_limit->val_int() == 1LL) &&
+                   offset_limit == 0));
+      return;
+    }
   }
-
   if (explicit_limit)
   {
     str->append(STRING_WITH_LEN(" limit "));
@@ -2098,6 +2110,7 @@ void st_select_lex::print_limit(THD *thd,
   }
 }
 
+
 /**
   @brief Restore the LEX and THD in case of a parse error.
 
diff --git a/sql/sql_lex.h b/sql/sql_lex.h
index 1bce1146154..72213a6df19 100644
--- a/sql/sql_lex.h
+++ b/sql/sql_lex.h
@@ -559,7 +559,8 @@ public:
   bool add_fake_select_lex(THD *thd);
   void init_prepare_fake_select_lex(THD *thd);
   inline bool is_prepared() { return prepared; }
-  bool change_result(select_subselect *result, select_subselect *old_result);
+  bool change_result(select_result_interceptor *result,
+                     select_result_interceptor *old_result);
   void set_limit(st_select_lex *values);
   void set_thd(THD *thd_arg) { thd= thd_arg; }
   inline bool is_union (); 
diff --git a/sql/sql_select.cc b/sql/sql_select.cc
index 877b2e5fae0..4f360267457 100644
--- a/sql/sql_select.cc
+++ b/sql/sql_select.cc
@@ -158,7 +158,7 @@ static enum_nested_loop_state
 evaluate_null_complemented_join_record(JOIN *join, JOIN_TAB *join_tab);
 static enum_nested_loop_state
 end_send(JOIN *join, JOIN_TAB *join_tab, bool end_of_records);
-static enum_nested_loop_state
+enum_nested_loop_state
 end_send_group(JOIN *join, JOIN_TAB *join_tab, bool end_of_records);
 static enum_nested_loop_state
 end_write(JOIN *join, JOIN_TAB *join_tab, bool end_of_records);
@@ -166,7 +166,7 @@ static enum_nested_loop_state
 end_update(JOIN *join, JOIN_TAB *join_tab, bool end_of_records);
 static enum_nested_loop_state
 end_unique_update(JOIN *join, JOIN_TAB *join_tab, bool end_of_records);
-static enum_nested_loop_state
+enum_nested_loop_state
 end_write_group(JOIN *join, JOIN_TAB *join_tab, bool end_of_records);
 
 static int test_if_group_changed(List<Cached_item> &list);
@@ -192,11 +192,14 @@ static int join_ft_read_first(JOIN_TAB *tab);
 static int join_ft_read_next(READ_RECORD *info);
 int join_read_always_key_or_null(JOIN_TAB *tab);
 int join_read_next_same_or_null(READ_RECORD *info);
-static COND *make_cond_for_table(COND *cond,table_map table,
-				 table_map used_table);
-static COND *make_cond_for_table_from_pred(COND *root_cond, COND *cond,
+static COND *make_cond_for_table(Item *cond,table_map table,
+				 table_map used_table,
+                                 bool exclude_expensive_cond);
+static COND *make_cond_for_table_from_pred(Item *root_cond, Item *cond,
                                            table_map tables,
-                                           table_map used_table);
+                                           table_map used_table,
+                                           bool exclude_expensive_cond);
+
 static Item* part_of_refkey(TABLE *form,Field *field);
 uint find_shortest_key(TABLE *table, const key_map *usable_keys);
 static bool test_if_skip_sort_order(JOIN_TAB *tab,ORDER *order,
@@ -707,8 +710,7 @@ JOIN::prepare(Item ***rref_pointer_array,
         // psergey-todo: duplicated_subselect_card_check: where it's done?
         if (in_subs->is_top_level_item() &&                             // 4
             !in_subs->is_correlated &&                                  // 5
-            in_subs->exec_method == Item_in_subselect::NOT_TRANSFORMED  // 6
-            && FALSE ) // psergey-merge: disable non-sj materialization
+            in_subs->exec_method == Item_in_subselect::NOT_TRANSFORMED) // 6
           in_subs->exec_method= Item_in_subselect::MATERIALIZATION;
       }
 
@@ -1501,7 +1503,7 @@ JOIN::optimize()
                            "Impossible HAVING" : "Impossible WHERE";
       tables= 0;
       error= 0;
-      DBUG_RETURN(0);
+      goto setup_subq_exit;
     }
   }
 
@@ -1543,7 +1545,7 @@ JOIN::optimize()
 	zero_result_cause= "No matching min/max row";
         tables= 0;
 	error=0;
-	DBUG_RETURN(0);
+        goto setup_subq_exit;
       }
       if (res > 1)
       {
@@ -1557,7 +1559,7 @@ JOIN::optimize()
         zero_result_cause= "No matching min/max row";
         tables= 0;
         error=0;
-        DBUG_RETURN(0);
+        goto setup_subq_exit;
       }
       DBUG_PRINT("info",("Select tables optimized away"));
       zero_result_cause= "Select tables optimized away";
@@ -1575,13 +1577,14 @@ JOIN::optimize()
       if (conds && !(thd->lex->describe & DESCRIBE_EXTENDED))
       {
         COND *table_independent_conds=
-          make_cond_for_table(conds, PSEUDO_TABLE_BITS, 0);
+          make_cond_for_table(conds, PSEUDO_TABLE_BITS, 0, FALSE);
         DBUG_EXECUTE("where",
                      print_where(table_independent_conds,
                                  "where after opt_sum_query()",
                                  QT_ORDINARY););
         conds= table_independent_conds;
       }
+      goto setup_subq_exit;
     }
   }
   if (!tables_list)
@@ -1619,7 +1622,7 @@ JOIN::optimize()
     zero_result_cause= "no matching row in const table";
     DBUG_PRINT("error",("Error: %s", zero_result_cause));
     error= 0;
-    DBUG_RETURN(0);
+    goto setup_subq_exit;
   }
   if (!(thd->options & OPTION_BIG_SELECTS) &&
       best_read > (double) thd->variables.max_join_size &&
@@ -1690,7 +1693,7 @@ JOIN::optimize()
   {
     zero_result_cause=
       "Impossible WHERE noticed after reading const tables";
-    DBUG_RETURN(0);				// error == 0
+    goto setup_subq_exit;
   }
 
   error= -1;					/* if goto err */
@@ -1920,6 +1923,10 @@ JOIN::optimize()
   if (!(select_options & SELECT_DESCRIBE))
     init_ftfuncs(thd, select_lex, test(order));
 
+  /* Create all structures needed for materialized subquery execution. */
+  if (setup_subquery_materialization())
+    DBUG_RETURN(1);
+
   /*
     is this simple IN subquery?
   */
@@ -2033,7 +2040,7 @@ JOIN::optimize()
       for (ORDER *tmp_order= order; tmp_order ; tmp_order=tmp_order->next)
       {
         Item *item= *tmp_order->item;
-        if (item->walk(&Item::is_expensive_processor, 0, (uchar*)0))
+        if (item->is_expensive())
         {
           /* Force tmp table without sort */
           need_tmp=1; simple_order=simple_group=0;
@@ -2185,6 +2192,18 @@ JOIN::optimize()
 
   error= 0;
   DBUG_RETURN(0);
+
+setup_subq_exit:
+  /*
+    Even with zero matching rows, subqueries in the HAVING clause may
+    need to be evaluated if there are aggregate functions in the
+    query. If we have planned to materialize the subquery, we need to
+    set it up properly before prematurely leaving optimize().
+  */
+  if (setup_subquery_materialization())
+    DBUG_RETURN(1);
+  error= 0;
+  DBUG_RETURN(0);
 }
 
 
@@ -2746,7 +2765,7 @@ JOIN::exec()
 
       Item* sort_table_cond= make_cond_for_table(curr_join->tmp_having,
 						 used_tables,
-						 used_tables);
+						 used_tables, FALSE);
       if (sort_table_cond)
       {
 	if (!curr_table->select)
@@ -2773,7 +2792,7 @@ JOIN::exec()
                                          QT_ORDINARY););
 	curr_join->tmp_having= make_cond_for_table(curr_join->tmp_having,
 						   ~ (table_map) 0,
-						   ~used_tables);
+						   ~used_tables, FALSE);
 	DBUG_EXECUTE("where",print_where(curr_join->tmp_having,
                                          "having after sort",
                                          QT_ORDINARY););
@@ -3656,7 +3675,6 @@ skip_conversion:
 bool JOIN::setup_subquery_materialization()
 {
   //psergey-merge: we don't have materialization so dont need that:
-#if 0 
   for (SELECT_LEX_UNIT *un= select_lex->first_inner_unit(); un;
        un= un->next_unit())
   {
@@ -3673,7 +3691,6 @@ bool JOIN::setup_subquery_materialization()
       }
     }
   }
-#endif
   return FALSE;
 }
 
@@ -8685,7 +8702,7 @@ make_join_select(JOIN *join,SQL_SELECT *select,COND *cond)
         COND *const_cond=
 	  make_cond_for_table(cond,
                               join->const_table_map,
-                              (table_map) 0);
+                              (table_map) 0, TRUE);
         DBUG_EXECUTE("where",print_where(const_cond,"constants", QT_ORDINARY););
         for (JOIN_TAB *tab= join->join_tab+join->const_tables;
              tab < join->join_tab+join->tables ; tab++)
@@ -8695,7 +8712,7 @@ make_join_select(JOIN *join,SQL_SELECT *select,COND *cond)
             JOIN_TAB *cond_tab= tab->first_inner;
             COND *tmp= make_cond_for_table(*tab->on_expr_ref,
                                            join->const_table_map,
-                                         (  table_map) 0);
+                                         (  table_map) 0, FALSE);
             if (!tmp)
               continue;
             tmp= new Item_func_trig_cond(tmp, &cond_tab->not_null_compl);
@@ -8783,7 +8800,7 @@ make_join_select(JOIN *join,SQL_SELECT *select,COND *cond)
 
       tmp= NULL;
       if (cond)
-        tmp= make_cond_for_table(cond,used_tables,current_map);
+        tmp= make_cond_for_table(cond, used_tables, current_map, FALSE);
       if (cond && !tmp && tab->quick)
       {						// Outer join
         if (tab->type != JT_ALL)
@@ -8839,7 +8856,7 @@ make_join_select(JOIN *join,SQL_SELECT *select,COND *cond)
 	  if (thd->variables.engine_condition_pushdown && !first_inner_tab)
           {
             COND *push_cond= 
-              make_cond_for_table(tmp, current_map, current_map);
+              make_cond_for_table(tmp, current_map, current_map, FALSE);
             if (push_cond)
             {
               /* Push condition to handler */
@@ -8968,7 +8985,7 @@ make_join_select(JOIN *join,SQL_SELECT *select,COND *cond)
                 (tmp=make_cond_for_table(cond,
 					 join->const_table_map |
 					 current_map,
-					 current_map)))
+					 current_map, FALSE)))
 	    {
               DBUG_EXECUTE("where",print_where(tmp,"cache", QT_ORDINARY););
 	      tab->cache_select=(SQL_SELECT*)
@@ -8998,7 +9015,7 @@ make_join_select(JOIN *join,SQL_SELECT *select,COND *cond)
           JOIN_TAB *cond_tab= join_tab->first_inner;
           COND *tmp= make_cond_for_table(*join_tab->on_expr_ref,
                                          join->const_table_map,
-                                         (table_map) 0);
+                                         (table_map) 0, FALSE);
           if (!tmp)
             continue;
           tmp= new Item_func_trig_cond(tmp, &cond_tab->not_null_compl);
@@ -9033,7 +9050,7 @@ make_join_select(JOIN *join,SQL_SELECT *select,COND *cond)
           current_map= tab->table->map;
           used_tables2|= current_map;
           COND *tmp_cond= make_cond_for_table(on_expr, used_tables2,
-                                             current_map);
+                                              current_map, FALSE);
           if (tmp_cond)
           {
             JOIN_TAB *cond_tab= tab < first_inner_tab ? first_inner_tab : tab;
@@ -13299,7 +13316,17 @@ remove_eq_conds(THD *thd, COND *cond, Item::cond_result *cond_value)
       return (COND*) 0;
     }
   }
-  else if (cond->const_item())
+  else if (cond->const_item() && !cond->is_expensive())
+  /*
+    DontEvaluateMaterializedSubqueryTooEarly:
+    TODO: 
+    Excluding all expensive functions is too restritive we should exclude only
+    materialized IN subquery predicates because they can't yet be evaluated
+    here (they need additional initialization that is done later on).
+
+    The proper way to exclude the subqueries would be to walk the cond tree and
+    check for materialized subqueries there.
+  */
   {
     *cond_value= eval_const_cond(cond) ? Item::COND_TRUE : Item::COND_FALSE;
     return (COND*) 0;
@@ -16164,6 +16191,8 @@ int do_sj_dups_weedout(THD *thd, SJ_TMP_TABLE *sjtbl)
   int error;
   SJ_TMP_TABLE::TAB *tab= sjtbl->tabs;
   SJ_TMP_TABLE::TAB *tab_end= sjtbl->tabs_end;
+  uchar *ptr;
+  uchar *nulls_ptr;
 
   DBUG_ENTER("do_sj_dups_weedout");
 
@@ -16171,15 +16200,13 @@ int do_sj_dups_weedout(THD *thd, SJ_TMP_TABLE *sjtbl)
   {
     if (sjtbl->have_confluent_row) 
       DBUG_RETURN(1);
-    else
-    {
-      sjtbl->have_confluent_row= TRUE;
-      DBUG_RETURN(0);
-    }
+
+    sjtbl->have_confluent_row= TRUE;
+    DBUG_RETURN(0);
   }
 
-  uchar *ptr= sjtbl->tmp_table->record[0] + 1;
-  uchar *nulls_ptr= ptr;
+  ptr= sjtbl->tmp_table->record[0] + 1;
+  nulls_ptr= ptr;
 
   /* Put the the rowids tuple into table->record[0]: */
 
@@ -17196,7 +17223,7 @@ end_send(JOIN *join, JOIN_TAB *join_tab __attribute__((unused)),
 
 
 	/* ARGSUSED */
-static enum_nested_loop_state
+enum_nested_loop_state
 end_send_group(JOIN *join, JOIN_TAB *join_tab __attribute__((unused)),
 	       bool end_of_records)
 {
@@ -17504,7 +17531,7 @@ end_unique_update(JOIN *join, JOIN_TAB *join_tab __attribute__((unused)),
 
 
 	/* ARGSUSED */
-static enum_nested_loop_state
+enum_nested_loop_state
 end_write_group(JOIN *join, JOIN_TAB *join_tab __attribute__((unused)),
 		bool end_of_records)
 {
@@ -17724,17 +17751,33 @@ static bool replace_where_subcondition(JOIN *join, Item **expr,
     Extracted condition
 */
 
-static COND *
-make_cond_for_table(COND *cond, table_map tables, table_map used_table)
+static Item *
+make_cond_for_table(Item *cond, table_map tables, table_map used_table,
+                    bool exclude_expensive_cond)
 {
-  return make_cond_for_table_from_pred(cond, cond, tables, used_table);
+  return make_cond_for_table_from_pred(cond, cond, tables, used_table,
+                                       exclude_expensive_cond);
 }
                
-static COND *
-make_cond_for_table_from_pred(COND *root_cond, COND *cond,
-                              table_map tables, table_map used_table)
+static Item *
+make_cond_for_table_from_pred(Item *root_cond, Item *cond,
+                              table_map tables, table_map used_table,
+                              bool exclude_expensive_cond)
+
 {
-  if (used_table && !(cond->used_tables() & used_table))
+  if (used_table && !(cond->used_tables() & used_table) &&
+      /*
+        Exclude constant conditions not checked at optimization time if
+        the table we are pushing conditions to is the first one.
+        As a result, such conditions are not considered as already checked
+        and will be checked at execution time, attached to the first table.
+
+        psergey: TODO: "used_table & 1" doesn't make sense in nearly any
+        context. Look at setup_table_map(), table bits reflect the order 
+        the tables were encountered by the parser. Check what we should
+        replace this condition with.
+      */
+      !((used_table & 1) && cond->is_expensive()))
     return (COND*) 0;				// Already checked
   if (cond->type() == Item::COND_ITEM)
   {
@@ -17748,7 +17791,9 @@ make_cond_for_table_from_pred(COND *root_cond, COND *cond,
       Item *item;
       while ((item=li++))
       {
-	Item *fix=make_cond_for_table_from_pred(root_cond, item, tables, used_table);
+	Item *fix=make_cond_for_table_from_pred(root_cond, item, 
+                                                tables, used_table,
+                                                exclude_expensive_cond);
 	if (fix)
 	  new_cond->argument_list()->push_back(fix);
       }
@@ -17778,7 +17823,9 @@ make_cond_for_table_from_pred(COND *root_cond, COND *cond,
       Item *item;
       while ((item=li++))
       {
-	Item *fix=make_cond_for_table_from_pred(root_cond, item, tables, 0L);
+	Item *fix=make_cond_for_table_from_pred(root_cond, item,
+                                                tables, 0L,
+                                                exclude_expensive_cond);
 	if (!fix)
 	  return (COND*) 0;			// Always true
 	new_cond->argument_list()->push_back(fix);
@@ -17799,8 +17846,12 @@ make_cond_for_table_from_pred(COND *root_cond, COND *cond,
     table_count times, we mark each item that we have examined with the result
     of the test
   */
-
-  if (cond->marker == 3 || (cond->used_tables() & ~tables))
+  if (cond->marker == 3 || (cond->used_tables() & ~tables) ||
+      /*
+        When extracting constant conditions, treat expensive conditions as
+        non-constant, so that they are not evaluated at optimization time.
+      */
+      (!used_table && exclude_expensive_cond && cond->is_expensive()))
     return (COND*) 0;				// Can't check this yet
   if (cond->marker == 2 || cond->eq_cmp_result() == Item::COND_OK)
     return cond;				// Not boolean op
@@ -18937,7 +18988,8 @@ static bool fix_having(JOIN *join, Item **having)
   table_map used_tables= join->const_table_map | table->table->map;
 
   DBUG_EXECUTE("where",print_where(*having,"having", QT_ORDINARY););
-  Item* sort_table_cond=make_cond_for_table(*having,used_tables,used_tables);
+  Item* sort_table_cond=make_cond_for_table(*having, used_tables, used_tables,
+                                            FALSE);
   if (sort_table_cond)
   {
     if (!table->select)
@@ -18955,7 +19007,7 @@ static bool fix_having(JOIN *join, Item **having)
     DBUG_EXECUTE("where",print_where(table->select_cond,
 				     "select and having",
                                      QT_ORDINARY););
-    *having=make_cond_for_table(*having,~ (table_map) 0,~used_tables);
+    *having= make_cond_for_table(*having,~ (table_map) 0,~used_tables, FALSE);
     DBUG_EXECUTE("where",
                  print_where(*having,"having after make_cond", QT_ORDINARY););
   }
@@ -20027,7 +20079,7 @@ alloc_group_fields(JOIN *join,ORDER *group)
   {
     for (; group ; group=group->next)
     {
-      Cached_item *tmp=new_Cached_item(join->thd, *group->item);
+      Cached_item *tmp=new_Cached_item(join->thd, *group->item, FALSE);
       if (!tmp || join->group_fields.push_front(tmp))
 	return TRUE;
     }
@@ -20037,6 +20089,38 @@ alloc_group_fields(JOIN *join,ORDER *group)
 }
 
 
+
+/*
+  Test if a single-row cache of items changed, and update the cache.
+
+  @details Test if a list of items that typically represents a result
+  row has changed. If the value of some item changed, update the cached
+  value for this item.
+  
+  @param list list of <item, cached_value> pairs stored as Cached_item.
+
+  @return -1 if no item changed
+  @return index of the first item that changed
+*/
+
+int test_if_item_cache_changed(List<Cached_item> &list)
+{
+  DBUG_ENTER("test_if_item_cache_changed");
+  List_iterator<Cached_item> li(list);
+  int idx= -1,i;
+  Cached_item *buff;
+
+  for (i=(int) list.elements-1 ; (buff=li++) ; i--)
+  {
+    if (buff->cmp())
+      idx=i;
+  }
+  DBUG_PRINT("info", ("idx: %d", idx));
+  DBUG_RETURN(idx);
+}
+
+
+
 static int
 test_if_group_changed(List<Cached_item> &list)
 {
diff --git a/sql/sql_select.h b/sql/sql_select.h
index 9fbf9621575..a0c35c3af07 100644
--- a/sql/sql_select.h
+++ b/sql/sql_select.h
@@ -1199,6 +1199,14 @@ enum_nested_loop_state sub_select_sjm(JOIN *join, JOIN_TAB *join_tab,
                                       bool end_of_records);
 int do_sj_dups_weedout(THD *thd, SJ_TMP_TABLE *sjtbl);
 
+enum_nested_loop_state
+end_send_group(JOIN *join, JOIN_TAB *join_tab __attribute__((unused)),
+	       bool end_of_records);
+enum_nested_loop_state
+end_write_group(JOIN *join, JOIN_TAB *join_tab __attribute__((unused)),
+		bool end_of_records);
+
+
 /**
   Information about a position of table within a join order. Used in join
   optimization.
@@ -1945,6 +1953,7 @@ 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);
+int test_if_item_cache_changed(List<Cached_item> &list);
 void calc_used_field_length(THD *thd, JOIN_TAB *join_tab);
 int join_init_read_record(JOIN_TAB *tab);
 void set_position(JOIN *join,uint idx,JOIN_TAB *table,KEYUSE *key);
diff --git a/sql/sql_union.cc b/sql/sql_union.cc
index 0f1270a5029..3ac91fc6a20 100644
--- a/sql/sql_union.cc
+++ b/sql/sql_union.cc
@@ -715,8 +715,8 @@ void st_select_lex_unit::reinit_exec_mechanism()
     TRUE  - error
 */
 
-bool st_select_lex_unit::change_result(select_subselect *new_result,
-                                       select_subselect *old_result)
+bool st_select_lex_unit::change_result(select_result_interceptor *new_result,
+                                       select_result_interceptor *old_result)
 {
   bool res= FALSE;
   for (SELECT_LEX *sl= first_select(); sl; sl= sl->next_select())