← Back to team overview

maria-developers team mailing list archive

bzr commit into file:///home/tsk/mprog/src/5.3-mwl68/ branch (timour:2765)

 

#At file:///home/tsk/mprog/src/5.3-mwl68/ based on revid:timour@xxxxxxxxxxxx-20100222151655-ltjv0rlv6z2sdiiu

 2765 timour@xxxxxxxxxxxx	2010-03-09
      MWL#68 Subquery optimization: Efficient NOT IN execution with NULLs
      
      * Implemented a second partial matching strategy via table scan.
        This strategy is a fallback when there is no memory for rowid merging.
      
      * Refactored the selection and creation of partial matching strategies,
        so that the choice of strategy is encapsulated in a separate method
        choose_partial_match_strategy().
      
      * Refactored the representation of partial match strategies so that:
        - each strategy is represented by a polymorphic class, and
        - the base class for all partial match strategies contains common
          execution code.
      
      * Added an estimate of the memory needed for the rowid merge strategy,
        and the system variable "rowid_merge_buff_size" to control the maximum
        memory to be used by the rowid merge algorithm.
      
      * Added two optimizer_switch system variables to control the choice of
        partial match strategy:
        "partial_match_rowid_merge", "partial_match_table_scan".
      
      * Fixed multiple problems with deallocation of resources by the partial
        match strategies.
     @ sql/mysql_priv.h
        * Added two optimizer_switch system variables to control the choice of
          partial match strategy:
          "partial_match_rowid_merge", "partial_match_table_scan".
     @ sql/mysqld.cc
        * Added two optimizer_switch system variables to control the choice of
          partial match strategy:
          "partial_match_rowid_merge", "partial_match_table_scan".
        * Added a system variable "rowid_merge_buff_size" to control the maximum
          memory to be used by the rowid merge algorithm.
     @ sql/set_var.cc
        * Added a system variable "rowid_merge_buff_size" to control the maximum
          memory to be used by the rowid merge algorithm.
     @ sql/sql_class.h
        * Added a system variable "rowid_merge_buff_size" to control the maximum
          memory to be used by the rowid merge algorithm.
     @ support-files/build-tags
        Newer versions of BZR require the recursive flag in order to list all files.

    modified:
      sql/item_subselect.cc
      sql/item_subselect.h
      sql/mysql_priv.h
      sql/mysqld.cc
      sql/set_var.cc
      sql/sql_class.h
      support-files/build-tags
=== modified file 'sql/item_subselect.cc'
--- a/sql/item_subselect.cc	2010-02-22 15:16:55 +0000
+++ b/sql/item_subselect.cc	2010-03-09 10:14:06 +0000
@@ -2910,13 +2910,7 @@ int subselect_uniquesubquery_engine::exe
 
 
 /*
-  TIMOUR: this needs more thinking, as exec() is a wrong IMO because:
-  - we don't need empty_result_set, as it is == 1 <=> when
-    item->value == 0
-  - scan_table() returns >0 even when there was no actuall error,
-    but we only found EOF while scanning.
-  - scan_table should not check table->status, but it should check
-    HA_ERR_END_OF_FILE
+  TIMOUR: write comment
 */
 
 int subselect_uniquesubquery_engine::index_lookup()
@@ -2924,8 +2918,6 @@ int subselect_uniquesubquery_engine::ind
   DBUG_ENTER("subselect_uniquesubquery_engine::index_lookup");
   int error;
   TABLE *table= tab->table;
-  empty_result_set= TRUE;
-  table->status= 0;
  
   if (!table->file->inited)
     table->file->ha_index_init(tab->ref.key, 0);
@@ -2934,25 +2926,25 @@ int subselect_uniquesubquery_engine::ind
                                         make_prev_keypart_map(tab->
                                                               ref.key_parts),
                                         HA_READ_KEY_EXACT);
-
   DBUG_PRINT("info", ("lookup result: %i", error));
-  if (error &&
-      error != HA_ERR_KEY_NOT_FOUND && error != HA_ERR_END_OF_FILE)
-    error= report_error(table, error);
-  else
+
+  if (error && error != HA_ERR_KEY_NOT_FOUND && error != HA_ERR_END_OF_FILE)
   {
-    error= 0;
-    table->null_row= 0;
-    if (!table->status && (!cond || cond->val_int()))
-    {
-      ((Item_in_subselect *) item)->value= 1;
-      empty_result_set= FALSE;
-    }
-    else
-      ((Item_in_subselect *) item)->value= 0;
+    /*
+      TIMOUR: I don't understand at all when do we need to call report_error.
+      In most places where we access an index, we don't do this. Why here?
+    */
+    error= report_error(table, error);
+    DBUG_RETURN(error);
   }
 
-  DBUG_RETURN(error);
+  table->null_row= 0;
+  if (!error && (!cond || cond->val_int()))
+    ((Item_in_subselect *) item)->value= 1;
+  else
+    ((Item_in_subselect *) item)->value= 0;
+
+  DBUG_RETURN(0);
 }
 
 
@@ -3415,19 +3407,24 @@ bool subselect_uniquesubquery_engine::no
   If max_keys > 1, then we need partial matching because there are
   more indexes than just the one we use during materialization to
   remove duplicates.
+
+  @note
+  TIMOUR: The schema-based analysis for partial matching can be done once for
+  prepared statement and remembered. It is done here to remove the need to
+  save/restore all related variables between each re-execution, thus making
+  the code simpler.
+
+  @retval PARTIAL_MATCH  if a partial match should be used
+  @retval COMPLETE_MATCH if a complete match (index lookup) should be used
 */
 
-void subselect_hash_sj_engine::set_strategy_using_schema()
+subselect_hash_sj_engine::exec_strategy
+subselect_hash_sj_engine::get_strategy_using_schema()
 {
   Item_in_subselect *item_in= (Item_in_subselect *) item;
 
-  DBUG_ENTER("subselect_hash_sj_engine::set_strategy_using_schema");
-
   if (item_in->is_top_level_item())
-  {
-    strategy= COMPLETE_MATCH;
-    DBUG_VOID_RETURN;
-  }
+    return COMPLETE_MATCH;
   else
   {
     List_iterator<Item> inner_col_it(*item_in->unit->get_unit_column_types());
@@ -3450,10 +3447,8 @@ void subselect_hash_sj_engine::set_strat
 
   /* If no column contains NULLs use regular hash index lookups. */
   if (count_partial_match_columns)
-    strategy= PARTIAL_MATCH;
-  else
-    strategy= COMPLETE_MATCH;
-  DBUG_VOID_RETURN;
+    return PARTIAL_MATCH;
+  return COMPLETE_MATCH;
 }
 
 
@@ -3465,19 +3460,25 @@ void subselect_hash_sj_engine::set_strat
   matching type of columns that cannot be NULL or that contain only NULLs.
   Based on this, the procedure determines the final execution strategy for
   the [NOT] IN predicate.
+
+  @retval PARTIAL_MATCH  if a partial match should be used
+  @retval COMPLETE_MATCH if a complete match (index lookup) should be used
 */
 
-void subselect_hash_sj_engine::set_strategy_using_data()
+subselect_hash_sj_engine::exec_strategy
+subselect_hash_sj_engine::get_strategy_using_data()
 {
   Item_in_subselect *item_in= (Item_in_subselect *) item;
   select_materialize_with_stats *result_sink=
     (select_materialize_with_stats *) result;
   Item *outer_col;
 
-  DBUG_ENTER("subselect_hash_sj_engine::set_strategy_using_data");
-
-  /* Call this procedure only if already selected partial matching. */
-  DBUG_ASSERT(strategy == PARTIAL_MATCH);
+  /*
+    If we already determined that a complete match is enough based on schema
+    information, nothing can be better.
+  */
+  if (strategy == COMPLETE_MATCH)
+    return COMPLETE_MATCH;
 
   for (uint i= 0; i < item_in->left_expr->cols(); i++)
   {
@@ -3501,9 +3502,117 @@ void subselect_hash_sj_engine::set_strat
 
   /* If no column contains NULLs use regular hash index lookups. */
   if (!count_partial_match_columns)
-    strategy= COMPLETE_MATCH;
+    return COMPLETE_MATCH;
+  return PARTIAL_MATCH;
+}
+
+
+void
+subselect_hash_sj_engine::choose_partial_match_strategy(
+  bool has_non_null_key, bool has_covering_null_row,
+  MY_BITMAP *partial_match_key_parts)
+{
+  size_t pm_buff_size;
 
-  DBUG_VOID_RETURN;
+  DBUG_ASSERT(strategy == PARTIAL_MATCH);
+  /*
+    Choose according to global optimizer switch. If only one of the switches is
+    'ON', then the remaining strategy is the only possible one. The only cases
+    when this will be overriden is when the total size of all buffers for the
+    merge strategy is bigger than the 'rowid_merge_buff_size' system variable,
+    or if there isn't enough physical memory to allocate the buffers.
+  */
+  if (!optimizer_flag(thd, OPTIMIZER_SWITCH_PARTIAL_MATCH_ROWID_MERGE) &&
+       optimizer_flag(thd, OPTIMIZER_SWITCH_PARTIAL_MATCH_TABLE_SCAN))
+    strategy= PARTIAL_MATCH_SCAN;
+  else if
+     ( optimizer_flag(thd, OPTIMIZER_SWITCH_PARTIAL_MATCH_ROWID_MERGE) &&
+      !optimizer_flag(thd, OPTIMIZER_SWITCH_PARTIAL_MATCH_TABLE_SCAN))
+    strategy= PARTIAL_MATCH_MERGE;
+
+  /*
+    If both switches are ON, or both are OFF, we interpret that as "let the
+    optimizer decide". Perform a cost based choice between the two partial
+    matching strategies.
+  */
+  /*
+    TIMOUR: the above interpretation of the switch values could be changed to:
+    - if both are ON - let the optimizer decide,
+    - if both are OFF - do not use partial matching, therefore do not use
+      materialization in non-top-level predicates.
+    The problem with this is that we know for sure if we need partial matching
+    only after the subquery is materialized, and this is too late to revert to
+    the IN=>EXISTS strategy.
+  */
+  if (strategy == PARTIAL_MATCH)
+  {
+    /*
+      TIMOUR: Currently we use a super simplistic measure. This will be
+      addressed in a separate task.
+    */
+    if (tmp_table->file->stats.records < 100)
+      strategy= PARTIAL_MATCH_SCAN;
+    else
+      strategy= PARTIAL_MATCH_MERGE;
+  }
+
+  /* Check if there is enough memory for the rowid merge strategy. */
+  if (strategy == PARTIAL_MATCH_MERGE)
+  {
+    pm_buff_size= rowid_merge_buff_size(has_non_null_key,
+                                        has_covering_null_row,
+                                        partial_match_key_parts);
+    if (pm_buff_size > thd->variables.rowid_merge_buff_size)
+      strategy= PARTIAL_MATCH_SCAN;
+  }
+}
+
+
+/*
+  Compute the memory size of all buffers proportional to the number of rows
+  in tmp_table.
+
+  @details
+  If the result is bigger than thd->variables.rowid_merge_buff_size, partial
+  matching via merging is not applicable.
+*/
+
+size_t subselect_hash_sj_engine::rowid_merge_buff_size(
+  bool has_non_null_key, bool has_covering_null_row,
+  MY_BITMAP *partial_match_key_parts)
+{
+  size_t buff_size; /* Total size of all buffers used by partial matching. */
+  ha_rows row_count= tmp_table->file->stats.records;
+  uint rowid_length= tmp_table->file->ref_length;
+  select_materialize_with_stats *result_sink=
+    (select_materialize_with_stats *) result;
+
+  /* Size of the subselect_rowid_merge_engine::row_num_to_rowid buffer. */
+  buff_size= row_count * rowid_length * sizeof(uchar);
+
+  if (has_non_null_key)
+  {
+    /* Add the size of Ordered_key::key_buff of the only non-NULL key. */
+    buff_size+= row_count * sizeof(rownum_t);
+  }
+
+  if (!has_covering_null_row)
+  {
+    for (uint i= 0; i < partial_match_key_parts->n_bits; i++)
+    {
+      if (!bitmap_is_set(partial_match_key_parts, i) ||
+          result_sink->get_null_count_of_col(i) == row_count)
+        continue; /* In these cases we wouldn't construct Ordered keys. */
+
+      /* Add the size of Ordered_key::key_buff */
+      buff_size+= (row_count - result_sink->get_null_count_of_col(i)) *
+                         sizeof(rownum_t);
+      /* Add the size of Ordered_key::null_key */
+      buff_size+= bitmap_buffer_size(result_sink->get_max_null_of_col(i));
+    }
+  }
+
+  return buff_size;
 }
 
 
@@ -3561,7 +3670,6 @@ bool subselect_hash_sj_engine::init_perm
                             thd->mem_root))
     DBUG_RETURN(TRUE);
 
-  set_strategy_using_schema();
   /*
     Create and initialize a select result interceptor that stores the
     result stream in a temporary table. The temporary table itself is
@@ -3623,7 +3731,9 @@ bool subselect_hash_sj_engine::init_perm
               ((Item_in_subselect *) item)->left_expr->cols() ==
               tmp_table->key_info->key_parts);
 
-  if (make_semi_join_conds())
+  if (make_semi_join_conds() ||
+      /* A unique_engine is used both for complete and partial matching. */
+      !(lookup_engine= make_unique_engine()))
     DBUG_RETURN(TRUE);
 
   DBUG_RETURN(FALSE);
@@ -3691,7 +3801,7 @@ bool subselect_hash_sj_engine::make_semi
       DBUG_RETURN(TRUE);
     }
   }
-  if (semi_join_conds->fix_fields(thd, &semi_join_conds))
+  if (semi_join_conds->fix_fields(thd, (Item**)&semi_join_conds))
     DBUG_RETURN(TRUE);
 
   DBUG_RETURN(FALSE);
@@ -3791,7 +3901,7 @@ bool subselect_hash_sj_engine::init_runt
     clause of the query, and it is not 'fixed' during JOIN::prepare.
   */
   if (semi_join_conds && !semi_join_conds->fixed &&
-      semi_join_conds->fix_fields(thd, &semi_join_conds))
+      semi_join_conds->fix_fields(thd, (Item**)&semi_join_conds))
     return TRUE;
   /* Let our engine reuse this query plan for materialization. */
   materialize_join= materialize_engine->join;
@@ -3802,6 +3912,7 @@ bool subselect_hash_sj_engine::init_runt
 
 subselect_hash_sj_engine::~subselect_hash_sj_engine()
 {
+  delete lookup_engine;
   delete result;
   if (tmp_table)
     free_tmp_table(thd, tmp_table);
@@ -3817,9 +3928,30 @@ subselect_hash_sj_engine::~subselect_has
 
 void subselect_hash_sj_engine::cleanup()
 {
+  enum_engine_type lookup_engine_type= lookup_engine->engine_type();
   is_materialized= FALSE;
-  result->cleanup(); /* Resets the temp table as well. */
+  bitmap_clear_all(&non_null_key_parts);
+  bitmap_clear_all(&partial_match_key_parts);
+  count_partial_match_columns= 0;
+  count_null_only_columns= 0;
+  strategy= UNDEFINED;
   materialize_engine->cleanup();
+  if (lookup_engine_type == TABLE_SCAN_ENGINE ||
+      lookup_engine_type == ROWID_MERGE_ENGINE)
+  {
+    subselect_engine *inner_lookup_engine;
+    inner_lookup_engine=
+      ((subselect_partial_match_engine*) lookup_engine)->lookup_engine;
+    /*
+      Partial match engines are recreated for each PS execution inside
+      subselect_hash_sj_engine::exec().
+    */
+    delete lookup_engine;
+    lookup_engine= inner_lookup_engine;
+  }
+  DBUG_ASSERT(lookup_engine->engine_type() == UNIQUESUBQUERY_ENGINE);
+  lookup_engine->cleanup();
+  result->cleanup(); /* Resets the temp table as well. */
 }
 
 
@@ -3838,6 +3970,7 @@ int subselect_hash_sj_engine::exec()
 {
   Item_in_subselect *item_in= (Item_in_subselect *) item;
   SELECT_LEX *save_select= thd->lex->current_select;
+  subselect_partial_match_engine *pm_engine= NULL;
   int res= 0;
 
   DBUG_ENTER("subselect_hash_sj_engine::exec");
@@ -3881,59 +4014,86 @@ int subselect_hash_sj_engine::exec()
     DBUG_RETURN(FALSE);
   }
 
-  if (strategy == PARTIAL_MATCH)
-    set_strategy_using_data();
-
-  /* A unique_engine is used both for complete and partial matching. */
-  if (!(lookup_engine= make_unique_engine()))
-  {
-    res= 1;
-    goto err;
-  }
-
+  /*
+    TIMOUR: The schema-based analysis for partial matching can be done once for
+    prepared statement and remembered. It is done here to remove the need to
+    save/restore all related variables between each re-execution, thus making
+    the code simpler.
+  */
+  strategy= get_strategy_using_schema();
+  /* This call may discover that we don't need partial matching at all. */
+  strategy= get_strategy_using_data();
   if (strategy == PARTIAL_MATCH)
   {
-    subselect_rowid_merge_engine *rowid_merge_engine;
-    uint count_pm_keys;
-    MY_BITMAP *nn_key_parts;
-    bool has_covering_null_row;
+    uint count_pm_keys; /* Total number of keys needed for partial matching. */
+    MY_BITMAP *nn_key_parts; /* The key parts of the only non-NULL index. */
+    uint covering_null_row_width;
     select_materialize_with_stats *result_sink=
       (select_materialize_with_stats *) result;
 
-    /* Total number of keys needed for partial matching. */
     nn_key_parts= (count_partial_match_columns < tmp_table->s->fields) ?
                   &non_null_key_parts : NULL;
 
-    has_covering_null_row= (result_sink->get_max_nulls_in_row() ==
-                            tmp_table->s->fields -
-                            (nn_key_parts ? bitmap_bits_set(nn_key_parts) : 0));
+    if (result_sink->get_max_nulls_in_row() ==
+        tmp_table->s->fields -
+        (nn_key_parts ? bitmap_bits_set(nn_key_parts) : 0))
+      covering_null_row_width= result_sink->get_max_nulls_in_row();
+    else
+      covering_null_row_width= 0;
 
-    if (has_covering_null_row)
+    if (covering_null_row_width)
       count_pm_keys= nn_key_parts ? 1 : 0;
     else
       count_pm_keys= count_partial_match_columns - count_null_only_columns +
         (nn_key_parts ? 1 : 0);
 
-    if (!(rowid_merge_engine=
-          new subselect_rowid_merge_engine((subselect_uniquesubquery_engine*)
-                                           lookup_engine,
-                                           tmp_table,
-                                           count_pm_keys,
-                                           has_covering_null_row,
-                                           item, result)) ||
-        rowid_merge_engine->init(nn_key_parts, &partial_match_key_parts))
-    {
-      strategy= PARTIAL_MATCH_SCAN;
-      delete rowid_merge_engine;
-      /* TIMOUR: setup execution structures for partial match via scanning. */
+    choose_partial_match_strategy(test(nn_key_parts),
+                                  test(covering_null_row_width),
+                                  &partial_match_key_parts);
+    DBUG_ASSERT(strategy == PARTIAL_MATCH_MERGE ||
+                strategy == PARTIAL_MATCH_SCAN);
+    if (strategy == PARTIAL_MATCH_MERGE)
+    {
+      pm_engine=
+        new subselect_rowid_merge_engine((subselect_uniquesubquery_engine*)
+                                         lookup_engine, tmp_table,
+                                         count_pm_keys,
+                                         covering_null_row_width,
+                                         item, result,
+                                         semi_join_conds->argument_list());
+      if (!pm_engine ||
+          ((subselect_rowid_merge_engine*) pm_engine)->
+            init(nn_key_parts, &partial_match_key_parts))
+      {
+        /*
+          The call to init() would fail if there was not enough memory to allocate
+          all buffers for the rowid merge strategy. In this case revert to table
+          scanning which doesn't need any big buffers.
+        */
+        delete pm_engine;
+        pm_engine= NULL;
+        strategy= PARTIAL_MATCH_SCAN;
+      }
     }
-    else
+
+    if (strategy == PARTIAL_MATCH_SCAN)
     {
-      strategy= PARTIAL_MATCH_INDEX;
-      lookup_engine= rowid_merge_engine;
+      if (!(pm_engine=
+            new subselect_table_scan_engine((subselect_uniquesubquery_engine*)
+                                            lookup_engine, tmp_table,
+                                            item, result,
+                                            semi_join_conds->argument_list(),
+                                            covering_null_row_width)))
+      {
+        /* This is an irrecoverable error. */
+        res= 1;
+        goto err;
+      }
     }
   }
 
+  if (pm_engine)
+    lookup_engine= pm_engine;
   item_in->change_engine(lookup_engine);
 
 err:
@@ -4009,10 +4169,8 @@ Ordered_key::Ordered_key(uint keyid_arg,
 
 Ordered_key::~Ordered_key()
 {
-  /*
-    All data structures are allocated on thd->mem_root, thus we don't
-    free them here.
-  */
+  my_free((char*) key_buff, MYF(0));
+  bitmap_free(&null_key);
 }
 
 
@@ -4030,6 +4188,7 @@ void Ordered_key::cleanup()
   */
 }
 
+
 /*
   Initialize a multi-column index.
 */
@@ -4103,14 +4262,16 @@ bool Ordered_key::init(int col_idx)
 }
 
 
+/*
+  Allocate the buffers for both the row number, and the NULL-bitmap indexes.
+*/
+
 bool Ordered_key::alloc_keys_buffers()
 {
-  THD *thd= tbl->in_use;
-
   DBUG_ASSERT(key_buff_elements > 0);
 
-  if (!(key_buff= (rownum_t*) thd->alloc(key_buff_elements *
-                                         sizeof(rownum_t))))
+  if (!(key_buff= (rownum_t*) my_malloc(key_buff_elements * sizeof(rownum_t),
+                                        MYF(MY_WME))))
     return TRUE;
 
   /*
@@ -4118,10 +4279,8 @@ bool Ordered_key::alloc_keys_buffers()
     (max_null_row - min_null_row), and then use min_null_row as
     lookup offset.
   */
-  if (bitmap_init_memroot(&null_key,
-                          /* this is max array index, we need count, so +1. */
-                          max_null_row + 1,
-                          thd->mem_root))
+  /* Notice that max_null_row is max array index, we need count, so +1. */
+  if (bitmap_init(&null_key, NULL, max_null_row + 1, FALSE))
     return TRUE;
 
   cur_key_idx= HA_POS_ERROR;
@@ -4193,8 +4352,9 @@ void Ordered_key::sort_keys()
 
 
 /*
-  The probability that a certain row does not contain a NULL in some row in
-  a NULL-indexed column.
+  The fraction of rows that do not contain NULL in the columns indexed by
+  this key.
+
   @retval  1  if there are no NULLs
   @retval  0  if only NULLs
 */
@@ -4353,10 +4513,122 @@ void Ordered_key::print(String *str)
 }
 
 
+subselect_partial_match_engine::subselect_partial_match_engine(
+  subselect_uniquesubquery_engine *engine_arg,
+  TABLE *tmp_table_arg, Item_subselect *item_arg,
+  select_result_interceptor *result_arg,
+  List<Item> *equi_join_conds_arg,
+  uint covering_null_row_width_arg)
+  :subselect_engine(item_arg, result_arg),
+   tmp_table(tmp_table_arg), lookup_engine(engine_arg),
+   equi_join_conds(equi_join_conds_arg),
+   covering_null_row_width(covering_null_row_width_arg)
+{}
+
+
+int subselect_partial_match_engine::exec()
+{
+  Item_in_subselect *item_in= (Item_in_subselect *) item;
+  int res;
+
+  /* Try to find a matching row by index lookup. */
+  res= lookup_engine->copy_ref_key_simple();
+  if (res == -1)
+  {
+    /* The result is FALSE based on the outer reference. */
+    item_in->value= 0;
+    item_in->null_value= 0;
+    return 0;
+  }
+  else if (res == 0)
+  {
+    /* Search for a complete match. */
+    if ((res= lookup_engine->index_lookup()))
+    {
+      /* An error occured during lookup(). */
+      item_in->value= 0;
+      item_in->null_value= 0;
+      return res;
+    }
+    else if (item_in->value)
+    {
+      /*
+        A complete match was found, the result of IN is TRUE.
+        Notice: (this->item == lookup_engine->item)
+      */
+      return 0;
+    }
+  }
+
+  if (covering_null_row_width == tmp_table->s->fields)
+  {
+    /*
+      If there is a NULL-only row that coveres all columns the result of IN
+      is UNKNOWN. 
+    */
+    item_in->value= 0;
+    /*
+      TIMOUR: which one is the right way to propagate an UNKNOWN result?
+      Should we also set empty_result_set= FALSE; ???
+    */
+    //item_in->was_null= 1;
+    item_in->null_value= 1;
+    return 0;
+  }
+
+  /*
+    There is no complete match. Look for a partial match (UNKNOWN result), or
+    no match (FALSE).
+  */
+  if (tmp_table->file->inited)
+    tmp_table->file->ha_index_end();
+
+  if (partial_match())
+  {
+    /* The result of IN is UNKNOWN. */
+    item_in->value= 0;
+    /*
+      TIMOUR: which one is the right way to propagate an UNKNOWN result?
+      Should we also set empty_result_set= FALSE; ???
+    */
+    //item_in->was_null= 1;
+    item_in->null_value= 1;
+  }
+  else
+  {
+    /* The result of IN is FALSE. */
+    item_in->value= 0;
+    /*
+      TIMOUR: which one is the right way to propagate an UNKNOWN result?
+      Should we also set empty_result_set= FALSE; ???
+    */
+    //item_in->was_null= 0;
+    item_in->null_value= 0;
+  }
+
+  return 0;
+}
+
+
+void subselect_partial_match_engine::print(String *str,
+                                           enum_query_type query_type)
+{
+  /*
+    Should never be called as the actual engine cannot be known at query
+    optimization time.
+  */
+  DBUG_ASSERT(FALSE);
+}
+
+
 /*
   @param non_null_key_parts  
   @param partial_match_key_parts  A union of all single-column NULL key parts.
   @param count_partial_match_columns Number of NULL keyparts (set bits above).
+
+  @retval FALSE  the engine was initialized successfully
+  @retval TRUE   there was some (memory allocation) error during initialization,
+                 such errors should be interpreted as revert to other strategy
 */
 
 bool
@@ -4379,14 +4651,17 @@ subselect_rowid_merge_engine::init(MY_BI
     return FALSE;
   }
 
-  DBUG_ASSERT(!has_covering_null_row || (has_covering_null_row &&
-                                         keys_count == 1 &&
-                                         non_null_key_parts));
-
+  DBUG_ASSERT(!covering_null_row_width || (covering_null_row_width &&
+                                           keys_count == 1 &&
+                                           non_null_key_parts));
+  /*
+    Allocate buffers to hold the merged keys and the mapping between rowids and
+    row numbers.
+  */
   if (!(merge_keys= (Ordered_key**) thd->alloc(keys_count *
                                                sizeof(Ordered_key*))) ||
-      !(row_num_to_rowid= (uchar*) thd->alloc(row_count * rowid_length *
-                                              sizeof(uchar))))
+      !(row_num_to_rowid= (uchar*) my_malloc(row_count * rowid_length *
+                                             sizeof(uchar), MYF(MY_WME))))
     return TRUE;
 
   /* Create the only non-NULL key if there is any. */
@@ -4395,10 +4670,7 @@ subselect_rowid_merge_engine::init(MY_BI
     non_null_key= new Ordered_key(cur_keyid, tmp_table, item_in->left_expr,
                                   0, 0, 0, row_num_to_rowid);
     if (non_null_key->init(non_null_key_parts))
-    {
-      // TIMOUR: revert to partial matching via scanning
       return TRUE;
-    }
     merge_keys[cur_keyid]= non_null_key;
     merge_keys[cur_keyid]->first();
     ++cur_keyid;
@@ -4406,9 +4678,10 @@ subselect_rowid_merge_engine::init(MY_BI
 
   /*
     If there is a covering NULL row, the only key that is needed is the
-    only non-NULL key that is already created above.
+    only non-NULL key that is already created above. We create keys on
+    NULL-able columns only if there is no covering NULL row.
   */
-  if (!has_covering_null_row)
+  if (!covering_null_row_width)
   {
     if (bitmap_init_memroot(&matching_keys, keys_count, thd->mem_root) ||
         bitmap_init_memroot(&matching_outer_cols, keys_count, thd->mem_root) ||
@@ -4436,10 +4709,7 @@ subselect_rowid_merge_engine::init(MY_BI
                                      result_sink->get_max_null_of_col(i),
                                      row_num_to_rowid);
         if (merge_keys[cur_keyid]->init(i))
-        {
-          // TIMOUR: revert to partial matching via scanning
           return TRUE;
-        }
         merge_keys[cur_keyid]->first();
       }
       ++cur_keyid;
@@ -4510,10 +4780,7 @@ subselect_rowid_merge_engine::init(MY_BI
 
   if (init_queue(&pq, keys_count, 0, FALSE,
                  subselect_rowid_merge_engine::cmp_keys_by_cur_rownum, NULL))
-  {
-    // TIMOUR: revert to partial matching via scanning
     return TRUE;
-  }
 
   return FALSE;
 }
@@ -4521,26 +4788,21 @@ subselect_rowid_merge_engine::init(MY_BI
 
 subselect_rowid_merge_engine::~subselect_rowid_merge_engine()
 {
-  delete_queue(&pq);
+  /* None of the resources below is allocated if there are no ordered keys. */
+  if (keys_count)
+  {
+    my_free((char*) row_num_to_rowid, MYF(0));
+    for (uint i= 0; i < keys_count; i++)
+      delete merge_keys[i];
+    delete_queue(&pq);
+    if (tmp_table->file->inited == handler::RND)
+      tmp_table->file->ha_rnd_end();
+  }
 }
 
 
 void subselect_rowid_merge_engine::cleanup()
 {
-  lookup_engine->cleanup();
-  /* Tell handler we don't need the index anymore */
-  if (tmp_table->file->inited)
-    tmp_table->file->ha_rnd_end();
-  queue_remove_all(&pq);
-}
-
-
-void subselect_rowid_merge_engine::print(String *str, enum_query_type query_type)
-{
-  str->append(STRING_WITH_LEN("<rowid_merge>("));
-  for (uint i= 0; i < keys_count; i++)
-    merge_keys[i]->print(str);
-  str->append(')');
 }
 
 
@@ -4627,20 +4889,31 @@ bool subselect_rowid_merge_engine::parti
   Ordered_key *cur_key;
   rownum_t cur_row_num;
   uint count_nulls_in_search_key= 0;
+  bool res= FALSE;
 
   /* If there is a non-NULL key, it must be the first key in the keys array. */
   DBUG_ASSERT(!non_null_key || (non_null_key && merge_keys[0] == non_null_key));
+
+  /* All data accesses during execution are via handler::ha_rnd_pos() */
+  tmp_table->file->ha_rnd_init(0);
+
   /* Check if there is a match for the columns of the only non-NULL key. */
   if (non_null_key && !non_null_key->lookup())
-    return FALSE;
+  {
+    res= FALSE;
+    goto end;
+  }
 
   /*
     If there is a NULL (sub)row that covers all NULL-able columns,
     then there is a guranteed partial match, and we don't need to search
     for the matching row.
    */
-  if (has_covering_null_row)
-    return TRUE;
+  if (covering_null_row_width)
+  {
+    res= TRUE;
+    goto end;
+  }
 
   if (non_null_key)
     queue_insert(&pq, (uchar *) non_null_key);
@@ -4667,14 +4940,20 @@ bool subselect_rowid_merge_engine::parti
   if (count_nulls_in_search_key ==
       ((Item_in_subselect *) item)->left_expr->cols() -
       (non_null_key ? non_null_key->get_column_count() : 0))
-    return TRUE;
+  {
+    res= TRUE;
+    goto end;
+  }
 
   /*
     If there is no NULL (sub)row that covers all NULL columns, and there is no
     single match for any of the NULL columns, the result is FALSE.
   */
   if (pq.elements - test(non_null_key) == 0)
-    return FALSE;
+  {
+    res= FALSE;
+    goto end;
+  }
 
   DBUG_ASSERT(pq.elements);
 
@@ -4692,10 +4971,8 @@ bool subselect_rowid_merge_engine::parti
       Check the only matching row of the only key min_key for NULL matches
       in the other columns.
     */
-    if (test_null_row(min_row_num))
-      return TRUE;
-    else
-      return FALSE;
+    res= test_null_row(min_row_num);
+    goto end;
   }
 
   while (TRUE)
@@ -4710,7 +4987,10 @@ bool subselect_rowid_merge_engine::parti
       /* Follows from the correct use of priority queue. */
       DBUG_ASSERT(cur_row_num > min_row_num);
       if (test_null_row(min_row_num))
-        return TRUE;
+      {
+        res= TRUE;
+        goto end;
+      }
       else
       {
         min_key= cur_key;
@@ -4727,99 +5007,112 @@ bool subselect_rowid_merge_engine::parti
     if (pq.elements == 0)
     {
       /* Check the last row of the last column in PQ for NULL matches. */
-      if (test_null_row(min_row_num))
-        return TRUE;
-      else
-        return FALSE;
+      res= test_null_row(min_row_num);
+      goto end;
     }
   }
 
-  /* We should never get here. */
+  /* We should never get here - all branches must be handled explicitly above. */
   DBUG_ASSERT(FALSE);
-  return FALSE;
+
+end:
+  tmp_table->file->ha_rnd_end();
+  return res;
 }
 
 
-int subselect_rowid_merge_engine::exec()
-{
-  Item_in_subselect *item_in= (Item_in_subselect *) item;
-  int res;
+subselect_table_scan_engine::subselect_table_scan_engine(
+  subselect_uniquesubquery_engine *engine_arg,
+  TABLE *tmp_table_arg,
+  Item_subselect *item_arg,
+  select_result_interceptor *result_arg,
+  List<Item> *equi_join_conds_arg,
+  uint covering_null_row_width_arg)
+  :subselect_partial_match_engine(engine_arg, tmp_table_arg, item_arg,
+                                  result_arg, equi_join_conds_arg,
+                                  covering_null_row_width_arg)
+{}
 
-  /* Try to find a matching row by index lookup. */
-  res= lookup_engine->copy_ref_key_simple();
-  if (res == -1)
-  {
-    /* The result is FALSE based on the outer reference. */
-    item_in->value= 0;
-    item_in->null_value= 0;
-    return 0;
-  }
-  else if (res == 0)
+
+/*
+  TIMOUR:
+  This method is based on subselect_uniquesubquery_engine::scan_table().
+  Consider refactoring somehow, 80% of the code is the same.
+
+  for each row_i in tmp_table
   {
-    if ((res= lookup_engine->index_lookup()))
-    {
-      /* An error occured during lookup(). */
-      item_in->value= 0;
-      item_in->null_value= 0;
-      return res;
-    }
-    else if (item_in->value)
+    count_matches= 0;
+    for each row element row_i[j]
     {
-      /*
-        A complete match was found, the result of IN is TRUE.
-        Notice: (this->item == lookup_engine->item)
-      */
-      return 0;
+      if (outer_ref[j] is NULL || row_i[j] is NULL || outer_ref[j] == row_i[j])
+        ++count_matches;
     }
+    if (count_matches == outer_ref.elements)
+      return TRUE
   }
+  return FALSE
+*/
 
-  if (has_covering_null_row && !keys_count)
-  {
-    /*
-      If there is a NULL-only row that coveres all columns the result of IN
-      is UNKNOWN. 
-    */
-    item_in->value= 0;
-    /*
-      TIMOUR: which one is the right way to propagate an UNKNOWN result?
-      Should we also set empty_result_set= FALSE; ???
-    */
-    //item_in->was_null= 1;
-    item_in->null_value= 1;
-    return 0;
-  }
+bool subselect_table_scan_engine::partial_match()
+{
+  List_iterator_fast<Item> equality_it(*equi_join_conds);
+  Item *cur_eq;
+  uint count_matches;
+  int error;
+  bool res;
 
-  /* All data accesses during execution are via handler::ha_rnd_pos() */
-  if (tmp_table->file->inited)
-    tmp_table->file->ha_index_end();
-  tmp_table->file->ha_rnd_init(0);
+  tmp_table->file->ha_rnd_init(1);
+  tmp_table->file->extra_opt(HA_EXTRA_CACHE,
+                             current_thd->variables.read_buff_size);
   /*
-    There is no complete match. Look for a partial match (UNKNOWN result), or
-    no match (FALSE).
+  TIMOUR:
+  scan_table() also calls "table->null_row= 0;", why, do we need it?
   */
-  if (partial_match())
-  {
-    /* The result of IN is UNKNOWN. */
-    item_in->value= 0;
-    /*
-      TIMOUR: which one is the right way to propagate an UNKNOWN result?
-      Should we also set empty_result_set= FALSE; ???
-    */
-    //item_in->was_null= 1;
-    item_in->null_value= 1;
-  }
-  else
+  for (;;)
   {
-    /* The result of IN is FALSE. */
-    item_in->value= 0;
-    /*
-      TIMOUR: which one is the right way to propagate an UNKNOWN result?
-      Should we also set empty_result_set= FALSE; ???
-    */
-    //item_in->was_null= 0;
-    item_in->null_value= 0;
+    error= tmp_table->file->ha_rnd_next(tmp_table->record[0]);
+    if (error) {
+      if (error == HA_ERR_RECORD_DELETED)
+      {
+        error= 0;
+        continue;
+      }
+      if (error == HA_ERR_END_OF_FILE)
+      {
+        error= 0;
+        break;
+      }
+      else
+      {
+        error= report_error(tmp_table, error);
+        break;
+      }
+    }
+
+    equality_it.rewind();
+    count_matches= 0;
+    while ((cur_eq= equality_it++))
+    {
+      DBUG_ASSERT(cur_eq->type() == Item::FUNC_ITEM &&
+                  ((Item_func*)cur_eq)->functype() == Item_func::EQ_FUNC);
+      if (!cur_eq->val_int() && !cur_eq->null_value)
+        break;
+      ++count_matches;
+    }
+    if (count_matches == tmp_table->s->fields)
+    {
+      res= TRUE; /* Found a matching row. */
+      goto end;
+    }
   }
+
+  res= FALSE;
+end:
   tmp_table->file->ha_rnd_end();
+  return res;
+}
 
-  return 0;
+
+void subselect_table_scan_engine::cleanup()
+{
 }

=== modified file 'sql/item_subselect.h'
--- a/sql/item_subselect.h	2010-02-22 15:16:55 +0000
+++ b/sql/item_subselect.h	2010-03-09 10:14:06 +0000
@@ -436,7 +436,7 @@ public:
   friend class Item_in_optimizer;
   friend class subselect_indexsubquery_engine;
   friend class subselect_hash_sj_engine;
-  friend class subselect_rowid_merge_engine;
+  friend class subselect_partial_match_engine;
 };
 
 
@@ -472,7 +472,7 @@ public:
   enum enum_engine_type {ABSTRACT_ENGINE, SINGLE_SELECT_ENGINE,
                          UNION_ENGINE, UNIQUESUBQUERY_ENGINE,
                          INDEXSUBQUERY_ENGINE, HASH_SJ_ENGINE,
-                         ROR_INTERSECT_ENGINE};
+                         ROWID_MERGE_ENGINE, TABLE_SCAN_ENGINE};
 
   subselect_engine(Item_subselect *si, select_result_interceptor *res)
     :thd(0)
@@ -716,6 +716,109 @@ inline bool Item_subselect::is_uncacheab
 }
 
 
+/**
+  Compute an IN predicate via a hash semi-join. This class is responsible for
+  the materialization of the subquery, and the selection of the correct and
+  optimal execution method (e.g. direct index lookup, or partial matching) for
+  the IN predicate.
+*/
+
+class subselect_hash_sj_engine : public subselect_engine
+{
+protected:
+  /* The table into which the subquery is materialized. */
+  TABLE *tmp_table;
+  /* 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 also reuse the functionality
+    of subselect_single_select_engine::[prepare | cols].
+  */
+  subselect_single_select_engine *materialize_engine;
+  /* The engine used to compute the IN predicate. */
+  subselect_engine *lookup_engine;
+  /*
+    QEP to execute the subquery and materialize its result into a
+    temporary table. Created during the first call to exec().
+  */
+  JOIN *materialize_join;
+
+  /* Keyparts of the only non-NULL composite index in a rowid merge. */
+  MY_BITMAP non_null_key_parts;
+  /* Keyparts of the single column indexes with NULL, one keypart per index. */
+  MY_BITMAP partial_match_key_parts;
+  uint count_partial_match_columns;
+  uint count_null_only_columns;
+  /*
+    A conjunction of all the equality condtions between all pairs of expressions
+    that are arguments of an IN predicate. We need these to post-filter some
+    IN results because index lookups sometimes match values that are actually
+    not equal to the search key in SQL terms.
+ */
+  Item_cond_and *semi_join_conds;
+  /* Possible execution strategies that can be used to compute hash semi-join.*/
+  enum exec_strategy {
+    UNDEFINED,
+    COMPLETE_MATCH, /* Use regular index lookups. */
+    PARTIAL_MATCH,  /* Use some partial matching strategy. */
+    PARTIAL_MATCH_MERGE, /* Use partial matching through index merging. */
+    PARTIAL_MATCH_SCAN,  /* Use partial matching through table scan. */
+    IMPOSSIBLE      /* Subquery materialization is not applicable. */
+  };
+  /* The chosen execution strategy. Computed after materialization. */
+  exec_strategy strategy;
+protected:
+  exec_strategy get_strategy_using_schema();
+  exec_strategy get_strategy_using_data();
+  size_t rowid_merge_buff_size(bool has_non_null_key,
+                               bool has_covering_null_row,
+                               MY_BITMAP *partial_match_key_parts);
+  void choose_partial_match_strategy(bool has_non_null_key,
+                                     bool has_covering_null_row,
+                                     MY_BITMAP *partial_match_key_parts);
+  bool make_semi_join_conds();
+  subselect_uniquesubquery_engine* make_unique_engine();
+
+public:
+  subselect_hash_sj_engine(THD *thd, Item_subselect *in_predicate,
+                           subselect_single_select_engine *old_engine)
+    :subselect_engine(in_predicate, NULL), tmp_table(NULL),
+    is_materialized(FALSE), materialize_engine(old_engine), lookup_engine(NULL),
+    materialize_join(NULL), count_partial_match_columns(0),
+    count_null_only_columns(0), semi_join_conds(NULL), strategy(UNDEFINED)
+  {
+    set_thd(thd);
+  }
+  ~subselect_hash_sj_engine();
+
+  bool init_permanent(List<Item> *tmp_columns);
+  bool init_runtime();
+  void cleanup();
+  int prepare() { return 0; } /* Override virtual function in base class. */
+  int exec();
+  virtual void print(String *str, enum_query_type query_type);
+  uint cols()
+  {
+    return materialize_engine->cols();
+  }
+  uint8 uncacheable() { return UNCACHEABLE_DEPENDENT; }
+  table_map upper_select_const_tables() { return 0; }
+  bool no_rows() { return !tmp_table->file->stats.records; }
+  virtual enum_engine_type engine_type() { return HASH_SJ_ENGINE; }
+  /*
+    TODO: factor out all these methods in a base subselect_index_engine class
+    because all of them have dummy implementations and should never be called.
+  */
+  void fix_length_and_dec(Item_cache** row);//=>base class
+  void exclude(); //=>base class
+  //=>base class
+  bool change_result(Item_subselect *si, select_result_interceptor *result);
+  bool no_tables();//=>base class
+};
+
+
 /*
   Distinguish the type od (0-based) row numbers from the type of the index into
   an array of row numbers.
@@ -745,7 +848,7 @@ typedef ha_rows rownum_t;
     PS (re)execution, however most of the comprising objects can be reused.
 */
 
-class Ordered_key
+class Ordered_key : public Sql_alloc
 {
 protected:
   /*
@@ -761,6 +864,8 @@ protected:
   uint key_column_count;
   /*
     An expression, or sequence of expressions that forms the search key.
+    The search key is a sequence when it is Item_row. Each element of the
+    sequence is accessible via Item::element_index(int i).
   */
   Item *search_key;
 
@@ -808,8 +913,6 @@ protected:
   int cmp_key_with_search_key(rownum_t row_num);
 
 public:
-  static void *operator new(size_t size) throw ()
-  { return sql_alloc(size); }
   Ordered_key(uint keyid_arg, TABLE *tbl_arg,
               Item *search_key_arg, ha_rows null_count_arg,
               ha_rows min_null_row_arg, ha_rows max_null_row_arg,
@@ -828,6 +931,10 @@ public:
     DBUG_ASSERT(i < key_column_count);
     return key_columns[i]->field->field_index;
   }
+  /*
+    Get the search key element that corresponds to the i-th key part of this
+    index.
+  */
   Item *get_search_key(uint i)
   {
     return search_key->element_index(key_columns[i]->field->field_index);
@@ -899,7 +1006,7 @@ public:
 };
 
 
-class subselect_rowid_merge_engine: public subselect_engine
+class subselect_partial_match_engine : public subselect_engine
 {
 protected:
   /* The temporary table that contains a materialized subquery. */
@@ -910,6 +1017,51 @@ protected:
     FALSE and UNKNOWN.
   */
   subselect_uniquesubquery_engine *lookup_engine;
+  /* A list of equalities between each pair of IN operands. */
+  List<Item> *equi_join_conds;
+  /*
+    If there is a row, such that all its NULL-able components are NULL, this
+    member is set to the number of covered columns. If there is no covering
+    row, then this is 0.
+  */
+  uint covering_null_row_width;
+protected:
+  virtual bool partial_match()= 0;
+public:
+  subselect_partial_match_engine(subselect_uniquesubquery_engine *engine_arg,
+                                 TABLE *tmp_table_arg, Item_subselect *item_arg,
+                                 select_result_interceptor *result_arg,
+                                 List<Item> *equi_join_conds_arg,
+                                 uint covering_null_row_width_arg);
+  int prepare() { return 0; }
+  int exec();
+  void fix_length_and_dec(Item_cache**) {}
+  uint cols() { /* TODO: what is the correct value? */ return 1; }
+  uint8 uncacheable() { return UNCACHEABLE_DEPENDENT; }
+  void exclude() {}
+  table_map upper_select_const_tables() { return 0; }
+  bool change_result(Item_subselect*, select_result_interceptor*)
+  { DBUG_ASSERT(FALSE); return false; }
+  bool no_tables() { return false; }
+  bool no_rows()
+  {
+    /*
+      TODO: It is completely unclear what is the semantics of this
+      method. The current result is computed so that the call to no_rows()
+      from Item_in_optimizer::val_int() sets Item_in_optimizer::null_value
+      correctly.
+    */
+    return !(((Item_in_subselect *) item)->null_value);
+  }
+  void print(String*, enum_query_type);
+
+  friend void subselect_hash_sj_engine::cleanup();
+};
+
+
+class subselect_rowid_merge_engine: public subselect_partial_match_engine
+{
+protected:
   /*
     Mapping from row numbers to row ids. The rowids are stored sequentially
     in the array - rowid[i] is located in row_num_to_rowid + i * rowid_length.
@@ -953,8 +1105,6 @@ protected:
     This queue is used by the partial match algorithm in method exec().
   */
   QUEUE pq;
-  /* True if there is a NULL (sub)row that covers all NULLable columns. */
-  bool has_covering_null_row;
 protected:
   /*
     Comparison function to compare keys in order of decreasing bitmap
@@ -972,143 +1122,34 @@ protected:
 public:
   subselect_rowid_merge_engine(subselect_uniquesubquery_engine *engine_arg,
                                TABLE *tmp_table_arg, uint keys_count_arg,
-                               uint has_covering_null_row_arg,
+                               uint covering_null_row_width_arg,
                                Item_subselect *item_arg,
-                               select_result_interceptor *result_arg)
-    :subselect_engine(item_arg, result_arg),
-    tmp_table(tmp_table_arg), lookup_engine(engine_arg),
-    keys_count(keys_count_arg), non_null_key(NULL),
-    has_covering_null_row(has_covering_null_row_arg)
+                               select_result_interceptor *result_arg,
+                               List<Item> *equi_join_conds_arg)
+    :subselect_partial_match_engine(engine_arg, tmp_table_arg, item_arg,
+                                    result_arg, equi_join_conds_arg,
+                                    covering_null_row_width_arg),
+    keys_count(keys_count_arg), non_null_key(NULL)
   {
     thd= lookup_engine->get_thd();
   }
   ~subselect_rowid_merge_engine();
   bool init(MY_BITMAP *non_null_key_parts, MY_BITMAP *partial_match_key_parts);
   void cleanup();
-  int prepare() { return 0; }
-  void fix_length_and_dec(Item_cache**) {}
-  int exec();
-  uint cols() { /* TODO: what is the correct value? */ return 1; }
-  uint8 uncacheable() { return UNCACHEABLE_DEPENDENT; }
-  void exclude() {}
-  table_map upper_select_const_tables() { return 0; }
-  void print(String*, enum_query_type);
-  bool change_result(Item_subselect*, select_result_interceptor*)
-  { DBUG_ASSERT(FALSE); return false; }
-  bool no_tables() { return false; }
-  bool no_rows()
-  {
-    /*
-      TODO: It is completely unclear what is the semantics of this
-      method. The current result is computed so that the call to no_rows()
-      from Item_in_optimizer::val_int() sets Item_in_optimizer::null_value
-      correctly.
-    */
-    return !(((Item_in_subselect *) item)->null_value);
-  }
+  virtual enum_engine_type engine_type() { return ROWID_MERGE_ENGINE; }
 };
 
 
-/**
-  Compute an IN predicate via a hash semi-join. This class is responsible for
-  the materialization of the subquery, and the selection of the correct and
-  optimal execution method (e.g. direct index lookup, or partial matching) for
-  the IN predicate.
-*/
-
-class subselect_hash_sj_engine : public subselect_engine
+class subselect_table_scan_engine: public subselect_partial_match_engine
 {
 protected:
-  /* The table into which the subquery is materialized. */
-  TABLE *tmp_table;
-  /* 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 also reuse the functionality
-    of subselect_single_select_engine::[prepare | cols].
-  */
-  subselect_single_select_engine *materialize_engine;
-  /* The engine used to compute the IN predicate. */
-  subselect_engine *lookup_engine;
-  /*
-    QEP to execute the subquery and materialize its result into a
-    temporary table. Created during the first call to exec().
-  */
-  JOIN *materialize_join;
-  /*
-    TRUE if the subquery result has an all-NULL column, which means that
-    there at best can be a partial match for any IN execution.
-  */
-  bool inner_partial_match;
-  /*
-    TRUE if the materialized subquery contains a whole row only of NULLs.
-  */
-  bool has_null_row;
-
-  /* Keyparts of the only non-NULL composite index in a rowid merge. */
-  MY_BITMAP non_null_key_parts;
-  /* Keyparts of the single column indexes with NULL, one keypart per index. */
-  MY_BITMAP partial_match_key_parts;
-  uint count_partial_match_columns;
-  uint count_null_only_columns;
-  /*
-    A conjunction of all the equality condtions between all pairs of expressions
-    that are arguments of an IN predicate. We need these to post-filter some
-    IN results because index lookups sometimes match values that are actually
-    not equal to the search key in SQL terms.
- */
-  Item *semi_join_conds;
-  /* Possible execution strategies that can be used to compute hash semi-join.*/
-  enum exec_strategy {
-    COMPLETE_MATCH, /* Use regular index lookups. */
-    PARTIAL_MATCH,  /* Use some partial matching strategy. */
-    PARTIAL_MATCH_INDEX, /* Use partial matching through index merging. */
-    PARTIAL_MATCH_SCAN,  /* Use partial matching through table scan. */
-    IMPOSSIBLE      /* Subquery materialization is not applicable. */
-  };
-  /* The chosen execution strategy. Computed after materialization. */
-  exec_strategy strategy;
-protected:
-  void set_strategy_using_schema();
-  void set_strategy_using_data();
-  bool make_semi_join_conds();
-  subselect_uniquesubquery_engine* make_unique_engine();
-
+  bool partial_match();
 public:
-  subselect_hash_sj_engine(THD *thd, Item_subselect *in_predicate,
-                           subselect_single_select_engine *old_engine)
-    :subselect_engine(in_predicate, NULL), tmp_table(NULL),
-    is_materialized(FALSE), materialize_engine(old_engine), lookup_engine(NULL),
-    materialize_join(NULL), count_partial_match_columns(0),
-    count_null_only_columns(0), semi_join_conds(NULL)
-  {
-    set_thd(thd);
-  }
-  ~subselect_hash_sj_engine();
-
-  bool init_permanent(List<Item> *tmp_columns);
-  bool init_runtime();
+  subselect_table_scan_engine(subselect_uniquesubquery_engine *engine_arg,
+                              TABLE *tmp_table_arg, Item_subselect *item_arg,
+                              select_result_interceptor *result_arg,
+                              List<Item> *equi_join_conds_arg,
+                              uint covering_null_row_width_arg);
   void cleanup();
-  int prepare() { return 0; } /* Override virtual function in base class. */
-  int exec();
-  virtual void print (String *str, enum_query_type query_type);
-  uint cols()
-  {
-    return materialize_engine->cols();
-  }
-  uint8 uncacheable() { return UNCACHEABLE_DEPENDENT; }
-  table_map upper_select_const_tables() { return 0; }
-  bool no_rows() { return !tmp_table->file->stats.records; }
-  virtual enum_engine_type engine_type() { return HASH_SJ_ENGINE; }
-  /*
-    TODO: factor out all these methods in a base subselect_index_engine class
-    because all of them have dummy implementations and should never be called.
-  */
-  void fix_length_and_dec(Item_cache** row);//=>base class
-  void exclude(); //=>base class
-  //=>base class
-  bool change_result(Item_subselect *si, select_result_interceptor *result);
-  bool no_tables();//=>base class
+  virtual enum_engine_type engine_type() { return TABLE_SCAN_ENGINE; }
 };

=== modified file 'sql/mysql_priv.h'
--- a/sql/mysql_priv.h	2010-01-17 14:55:08 +0000
+++ b/sql/mysql_priv.h	2010-03-09 10:14:06 +0000
@@ -552,12 +552,14 @@ protected:
 #define OPTIMIZER_SWITCH_LOOSE_SCAN 64
 #define OPTIMIZER_SWITCH_MATERIALIZATION 128
 #define OPTIMIZER_SWITCH_SEMIJOIN 256
+#define OPTIMIZER_SWITCH_PARTIAL_MATCH_ROWID_MERGE 512
+#define OPTIMIZER_SWITCH_PARTIAL_MATCH_TABLE_SCAN 1024
 
 #ifdef DBUG_OFF
-#  define OPTIMIZER_SWITCH_LAST 512
+#  define OPTIMIZER_SWITCH_LAST 2048
 #else
-#  define OPTIMIZER_SWITCH_TABLE_ELIMINATION 512
-#  define OPTIMIZER_SWITCH_LAST 1024
+#  define OPTIMIZER_SWITCH_TABLE_ELIMINATION 2048
+#  define OPTIMIZER_SWITCH_LAST 4096
 #endif
 
 #ifdef DBUG_OFF 
@@ -570,8 +572,10 @@ protected:
                                     OPTIMIZER_SWITCH_FIRSTMATCH | \
                                     OPTIMIZER_SWITCH_LOOSE_SCAN | \
                                     OPTIMIZER_SWITCH_MATERIALIZATION | \
-                                    OPTIMIZER_SWITCH_SEMIJOIN)
-#else 
+                                    OPTIMIZER_SWITCH_SEMIJOIN | \
+                                    OPTIMIZER_SWITCH_PARTIAL_MATCH_ROWID_MERGE|\
+                                    OPTIMIZER_SWITCH_PARTIAL_MATCH_TABLE_SCAN)
+#else
 #  define OPTIMIZER_SWITCH_DEFAULT (OPTIMIZER_SWITCH_INDEX_MERGE | \
                                     OPTIMIZER_SWITCH_INDEX_MERGE_UNION | \
                                     OPTIMIZER_SWITCH_INDEX_MERGE_SORT_UNION | \
@@ -581,7 +585,9 @@ protected:
                                     OPTIMIZER_SWITCH_FIRSTMATCH | \
                                     OPTIMIZER_SWITCH_LOOSE_SCAN | \
                                     OPTIMIZER_SWITCH_MATERIALIZATION | \
-                                    OPTIMIZER_SWITCH_SEMIJOIN)
+                                    OPTIMIZER_SWITCH_SEMIJOIN | \
+                                    OPTIMIZER_SWITCH_PARTIAL_MATCH_ROWID_MERGE|\
+                                    OPTIMIZER_SWITCH_PARTIAL_MATCH_TABLE_SCAN)
 #endif
 
 /*

=== modified file 'sql/mysqld.cc'
--- a/sql/mysqld.cc	2010-01-17 14:55:08 +0000
+++ b/sql/mysqld.cc	2010-03-09 10:14:06 +0000
@@ -301,7 +301,9 @@ static const char *optimizer_switch_name
   "index_merge","index_merge_union","index_merge_sort_union",
   "index_merge_intersection",
   "index_condition_pushdown",
-  "firstmatch","loosescan","materialization", "semijoin", 
+  "firstmatch","loosescan","materialization", "semijoin",
+  "partial_match_rowid_merge",
+  "partial_match_table_scan",
 #ifndef DBUG_OFF
   "table_elimination",
 #endif
@@ -320,6 +322,8 @@ static const unsigned int optimizer_swit
   sizeof("loosescan") - 1,
   sizeof("materialization") - 1,
   sizeof("semijoin") - 1,
+  sizeof("partial_match_rowid_merge") - 1,
+  sizeof("partial_match_table_scan") - 1,
 #ifndef DBUG_OFF
   sizeof("table_elimination") - 1,
 #endif
@@ -5794,7 +5798,8 @@ enum options_mysqld
   OPT_RECORD_RND_BUFFER, OPT_DIV_PRECINCREMENT, OPT_RELAY_LOG_SPACE_LIMIT,
   OPT_RELAY_LOG_PURGE,
   OPT_SLAVE_NET_TIMEOUT, OPT_SLAVE_COMPRESSED_PROTOCOL, OPT_SLOW_LAUNCH_TIME,
-  OPT_SLAVE_TRANS_RETRIES, OPT_READONLY, OPT_DEBUGGING, OPT_DEBUG_FLUSH,
+  OPT_SLAVE_TRANS_RETRIES, OPT_READONLY, OPT_ROWID_MERGE_BUFF_SIZE,
+  OPT_DEBUGGING, OPT_DEBUG_FLUSH,
   OPT_SORT_BUFFER, OPT_TABLE_OPEN_CACHE, OPT_TABLE_DEF_CACHE,
   OPT_THREAD_CONCURRENCY, OPT_THREAD_CACHE_SIZE,
   OPT_TMP_TABLE_SIZE, OPT_THREAD_STACK,
@@ -7130,6 +7135,11 @@ The minimum value for this variable is 4
    (uchar**) &max_system_variables.range_alloc_block_size, 0, GET_ULONG,
    REQUIRED_ARG, RANGE_ALLOC_BLOCK_SIZE, RANGE_ALLOC_BLOCK_SIZE,
    (longlong) ULONG_MAX, 0, 1024, 0},
+  {"rowid_merge_buff_size", OPT_ROWID_MERGE_BUFF_SIZE,
+   "The size of the buffers used [NOT] IN evaluation via partial matching.",
+   (uchar**) &global_system_variables.rowid_merge_buff_size,
+   (uchar**) &max_system_variables.rowid_merge_buff_size, 0, GET_ULONG,
+   REQUIRED_ARG, 8*1024*1024L, 0, MAX_MEM_TABLE_SIZE/2, 0, 1, 0},
   {"read_buffer_size", OPT_RECORD_BUFFER,
    "Each thread that does a sequential scan allocates a buffer of this size for each table it scans. If you do many sequential scans, you may want to increase this value.",
    (uchar**) &global_system_variables.read_buff_size,

=== modified file 'sql/set_var.cc'
--- a/sql/set_var.cc	2009-12-22 12:49:15 +0000
+++ b/sql/set_var.cc	2010-03-09 10:14:06 +0000
@@ -540,6 +540,9 @@ static sys_var_long_ptr	sys_query_cache_
 
 static sys_var_thd_ulong	sys_range_alloc_block_size(&vars, "range_alloc_block_size",
 						   &SV::range_alloc_block_size);
+static sys_var_thd_ulong	sys_rowid_merge_buff_size(&vars, "rowid_merge_buff_size",
+					   &SV::rowid_merge_buff_size);
+
 static sys_var_thd_ulong	sys_query_alloc_block_size(&vars, "query_alloc_block_size",
 						   &SV::query_alloc_block_size,
 						   0, fix_thd_mem_root);

=== modified file 'sql/sql_class.h'
--- a/sql/sql_class.h	2010-02-19 21:55:57 +0000
+++ b/sql/sql_class.h	2010-03-09 10:14:06 +0000
@@ -343,6 +343,8 @@ struct system_variables
   ulong mrr_buff_size;
   ulong div_precincrement;
   ulong sortbuff_size;
+  /* Total size of all buffers used by the subselect_rowid_merge_engine. */
+  ulong rowid_merge_buff_size;
   ulong thread_handling;
   ulong tx_isolation;
   ulong completion_type;

=== modified file 'support-files/build-tags'
--- a/support-files/build-tags	2009-12-15 07:16:46 +0000
+++ b/support-files/build-tags	2010-03-09 10:14:06 +0000
@@ -4,7 +4,7 @@ rm -f TAGS
 filter='\.cc$\|\.c$\|\.h$\|\.yy$'
 
 list="find . -type f"
-bzr root >/dev/null 2>/dev/null && list="bzr ls --from-root --kind=file --versioned"
+bzr root >/dev/null 2>/dev/null && list="bzr ls --from-root -R --kind=file --versioned"
 
 $list |grep $filter |while read f; 
 do

# Bazaar merge directive format 2 (Bazaar 0.90)
# revision_id: timour@xxxxxxxxxxxx-20100309101406-xygkt2sgftvjvevg
# target_branch: file:///home/tsk/mprog/src/5.3-mwl68/
# testament_sha1: 08bedb08796c2d4f47c3ec878f0bfab56ab70221
# timestamp: 2010-03-09 12:14:13 +0200
# base_revision_id: timour@xxxxxxxxxxxx-20100222151655-\
#   ltjv0rlv6z2sdiiu
# 
# Begin bundle
IyBCYXphYXIgcmV2aXNpb24gYnVuZGxlIHY0CiMKQlpoOTFBWSZTWWDuuJwAFvB/gH13Art/////
/////r////9gLt7vc3lmz7en2fe2l5oyBRUqfWqbYrs+vefcz7vvFrN2m8oUHRRoBqILbV9b3vjm
9PeaQLt9fID77KKfYt1Xsd17eB73aXecelN6DLbZG2zRibZ1R13d6ePbalbMXm3Xrvvd20eG3a2W
954XZ987qpRd7jvCU0ggAIJiZCMBNTE8pppk1MJP1TaYUeo9GiMaDUNDGgEpoIECmhMU9Cps1Eb1
JhNABk00aAGhoBoGhoANA000hU8Ip6PUgP0oGR6hoaBoNBoDQAADQANAAEmlEIg1DIxATUM0xNT0
1MgzUaA0AANAAABoaCJSAgaaRiCME2kyNT00kxiT0pm1NT0yhieofqT2lMn6oHqB6R5BEkQCBGgS
eKGCKflT9KPKeyjJqaeUDTE00BpoDQAD0h4TWK9MADMRBHNBEY090OiB+Pnh19fXWww38JaBdpcS
H4MBzIaLhwCm1yLBOqys16MhpWa1ov9+LE65+voxLaMSJqtOB05vw7s6djXbG1Crq5R6/g/rRn6v
VljXmHnh92OFF1E6ZW/x3cH2Pvf7/v0FOut2r4W/HsDQeNZaNtqEyGtao9hNS2vLidn/imcavnd6
8ZUwqri/3I3F07YchpyFyFRoZV/BWECAHfFrqeXbhzhjueVLWQVtsdbqa+ft+NtNxdc1aq2raQ/x
XhA34bcfre69tfi8og9fVe9kN4biMnKxPszBTn88Vvjv+rftbbG2IEmFuoDZmrlzrGJKbGuTIXFJ
1sKWOckLHbhomA3KcAfIOrKAxgikQ6pTNJc7LJhn5cWq3Pcs46NsZ+VM+zY8E1ihDRtzIF4m8ehs
uzDCdddsstDiPMhxYO5bDjz5d/V52N+f2jqeFLKyUd8ES6mI1HjelHMWmRexDrCpqcg5FrvW4GQH
7AUwZzb6yo0qLm/Jlq4bQPag9TSxF8zNErLRgyG+VVVFQsrA6Ck9ghnzZJY2bakwPEkiccHAkiH5
YGVu/X9fm6X4jNIbWO+3odM3SdkFLiBW9Mam17oZvl3cDKZoQ0ohDGlJpmml8DjcgBlmzMqqQ67r
4RjrpLtjbO84vbVXeotUYy71nCxDivJgu8cVVpvNPexLYu5DloUWViq1D4Sl4RQp1n1NyFZ8e+D0
N5psU2EL9cds7UEQ2QRFC5QU2xVApBQPbZKMiK4tiRkBhIdwZAKRFgAnvykqST8YyQrIBo1WQgeb
kIHVBy1MVNgCIQAwP0/+7oV/YuyiJU7V9bXIZ1lrieyrvsjn4UlzfexIaRci1L8UbWNSbs/unRKh
erRUJu79mDtNAURWK7mr6PNwDxksdMI939ToFgNfon7htq3sfh56ciz7c8LXn909kpMB0CHrJ5GY
RE9RUr6QPTJ7MiRZFIsAFJIqkWAb/DtOXxZILIqqIOPdgTw8H8vn61BoP3iO/wFCaeA+HhC3XGj4
C//e6+37Kb1vnCDpa7PHdPdlX7IvYtGKF23Vuw3flmDWLbl53s0/4cxxxyZWuZjOltLsTviD8zZj
aLZTxeoNKY2jSNJjDhMM3pl2alZllRZlmzsQ3Ny4u/XjquNQGtO+bYFOyCUzbIHi0Qmd3Wzu77LK
YpZ04+nMWtM5xGmicTGHvfVvn4NbOStIwoUKY2GtM22nJUKkkrGzYzWHmIWFdFvAfdLbGiESpCTU
eLzcxwN1RJzdPtIjgUD9vdRD2P3zqhztaB8LDJeG85eUIyO9Loc600ISor41UzVEJQCdeHicK6Et
t1oWERn7Lvv4Q/AOYEF4Bw7bfXuUeHELfcnYlmsaHQ4h04LWOWt2MtuJmNcVmagSPivfTVW8BUZf
awPlWTpuwh1A7hcoTWICWS8/zj61W6O72+yvHJNj2qsUh/ZDae0PinaJcPycBWxOdOVLaLYp17kx
ZNqRC8caxYgp6dd6vRPmycs+H/9mzfJRS7qxj4+luxpy7qXDsE3NILHwgejZkxkJmLEZ3q5PG2+c
7ZMhFzwO9XJhYYoHs0QT0+BXQZeYZqj3Q6bbB6Q2aer8eLf0Lmbf3QRri+5NM1yMTtBz3u671ghw
SbGrv15dFwt7Vi/q+/fmj+zodltwKzIzfy24bds9Aa63YzRYvJleQxo9/ZOZZ6zhnGmu6Pu4FUit
uWmO/9+VkrLLMvG+6R6NeBtcPcVkd67uP+fMe8wPr0iIe24+Lm7+vphLm1T1QAoatblNPabJOScV
YwkMkN8QjedGedmOFUJLLpgcRvfn7r6sa3t21xpjbH+erAvlsncNa12D7ZUEuRdw5buSXuq2XpAu
+zlnDjU47LEWB4eunfXvD2lVuC00qcKOV3PS5q411c+fGGBZs2hW0jVnHyZk7pOJIMJphnD4CYlD
ec57+LeVZCfOAz9Kt/ShVkL6Ao4fujfTvMX7HXuSG1hkgtN2cI43Cg119m4mSFShvGY7TsASaogG
FDumJiD6U8he7pycWmFwzng23MFJsr399Rr7nc2W4c6t6fUeOc+LN23zfbzajHBsy0g9DQSeqig5
NcbcsHOLO2ujHSFtJjO8pKG1fFi8nPJeDsLYUGTmZ19nU6ZcFvC45ZB14ne7PRZzR74oPa46QJeR
zEts2s16HbR4tUNni29E82sp1cJ8tmbO+xctr06MdkKHYzHmhQ3A8t3t1ykUet26QfJ4IfZjs294
1hW6eg0cyPardTRmfqQ+FTcbMmGeHrNt0pCJGJLOm5lgh4liTWLDdirOF8BhtaGzYxhX2ZOSls4j
aM1pfXlpS0PbZeUxfzaI06oY02+KvmjQqfNlGMveK9L8bVQXqUUQ1855s97FvRN2uHTRnWCMO2rY
kwmrQ+hDOjeI3qpUl5s8bcFzae8UXQg8GIgz0uBk3TYDn4VvU9yxxZkz0pMxLsrgbwKKO3aPNIKW
QJD5nnYrE1smuysuCKZr1jM0jTLxptd9JLxpX58r76n6q6s2NS3S7vlzfswcKEyLIKesaXz23n5+
+bAeqMFQRVYxTdv0JOzpMkDp5e/6fZwX4eyGnZRH4tv4vT870+42lnkHMimqxm/p8cI/Losolxhz
IXxJwS3YQaC7gCjZ0at0mZIm4oeGoJEPjlSBID9LzxqckT1iRG5n3UOgWHT9UwyGj1o+mIe1DeU8
svM7n6/tutIlJ5fsges4drcjPwrToAggHZiTN1Mi6giDvZuisqoRDvD1Ukpipe+f3yB/Nc4XsIc0
dgeGwc7HntTRNh3uQzTvqZs13DdR7GTn3EOvLl9lqXbvPvU15HRSN5rOX7mu2JqRyMiHLnyPSGP6
0d+exZPA1I9Xu67WjDxxpsXzQL4OfTh64Qrj0T/0mXv88c/aXlV9Nmq32XefhbTqqxhZfq+GeSxM
ikhQXv8hNw9S56aGYh0i4JhoKblTUmn4F6eVRjDjt34LVNoPbwrz42puLdo0rZor/xe1s7oyi9Ot
Oalz1p90c69s9uK6t+COF6ayQi6gOV1md7hdE130z39sD3qdPg+yBEayej6YiWVWMIqaXwSjWxYK
ttVWq78WOFyczlnppPTTRTQZJJCQe7sop6Yibv00TVBE8Tzma/JZg2nSbeP68p9fAH61vkxv53Ca
EiEIJ5cvVnx0ShVhD+EmgWNWTcsRja50ZUtFLxlMfju7K+zC+EKrmd+7GrGIVfPj/LHLTTSitQ67
y2hybZLid9XuUdRRzV0bVxYfQ9FtxOwid/vTY9A9hF5h7XTsaipMgL8Q/O+UwuMFjEYV9aWQtLVR
81uhLAWOu14kppeHM+4TzBnpDUfX5v1fZZcGp5C7m+hPI/TcPHe2acvlDpudgxjo2YaRCxuqvqRX
zbeTnc4U7lU/WudWUPKcH9WnRHOi9VC7E8cIWOtl9FF88bMK5zueNtO6i5cfPS0VbhONhDF52LlR
RaRz8Ox0x7ujXYIU1O/df9OUY0SuKLQWgepQDzknrge17fzZnBlqwK1hYmWBlPSZng9wMgVfUQb6
95gOGIobmZbs5M270cvd3IHMBmSG449cJow9jawWsNE87IGdKaISVIab6TcwmqGqGmmzg90jNwJj
O3Fi7QMFhGQiec2oRwQuh56LNhC163Z3xULvynAwtvyzyEJYHSiaKmsugSOSL2qgkfT4eBgh/lFo
uVU8GG0VSW1j903LEvVjcYJIkchgk4EBhxFfto3GgfLmdyZHDSnMg2irnBtWdhIu/PSh7mLcrlTh
Ti31/GwS32HbCyMNhx2Bxgc+gKGD4mujesIlfHuJgtjV96D8N5gabHYHvKwdlZooF5mONc5venyc
+Xntpqw7/Ic9wTx9OTeg7hguA+MIVGML7WTOheD9w2fBlveeX2uOt+MWkwwc+bCaWMZbK37Wh7OF
dernMq8iHiZ8E3L1AaPymbk8zRcsbFgY+GWA4TJEoLw8ezaDbq627s3xEWzSPZCSzTor6G2L7Vjv
ZjDIGazX0CHZrPFxOos7D022z7lzac5C5kZ8MIvOzeNbW2zPoemtFhF/O/1m6ldGC77E1TlC+TXD
RzYsm8hMXEzQY7GQggYnyPURg6NzjY9pJY/hbcmbGi2sb+zHujBVfTXhr6ZBGpzUhaU8URRrqlVn
OJrGHvaw8O/dK9m+/zs43vw0sw2Sc8NHDVO493EPe0z6pmDK5w77QQ54ZMy00P877paynh9vd0V2
o2hmUifRnpiR5b5BAaRUj1xLmAPUyRkcbS2LcBuu31lw+bumuQWQuhF9a1vjmPUQm9SoqpVrv3Wj
WQ1jWQVDeUvYYNOUmhgvmCUXgd0SbaveLBZILq9q1m9myhvmPhBtLJNWlnG8PXAm3Jo8Tkqs8kDb
gsISGSyJ6u9aKJQbRbl8LEhowxJI4EPInwAbY4m4o7C51PgzWb6Tc9+7cqE+oU9TWsVe8XHKeZor
qe+2e1rN6GDDE/T3DCIkrT7tTZD22Yuxyxce5PvPfYOTZF2c0fKfMNtVn4NkSc4s/DFiHLFkXXYi
T5mze+crIuB6iiGyixuPNWYIo9CjcW+cnJ6mCxc9hlsmxgNGj09zabmWw0tjkbu0/K24dI5zW25l
YQ+Jl9WVqeLDAr0jkyepc2ozjEs8jk0TB7DENBgnGs2Y3zZvhMtQmOBysng2b5NyCOx4Hj1Ldywd
jJHPf/TeJHOOIuSh10wdqNQiczSeQjcZEGrKT0aqzUN3MaeRF2eGJVIdKRja2qv7J5zbNRGqtasx
hYYEZKKIlJXUlGnRQcjt9Y3FKdVG0768FxqRpvlHHGGUdZSXlxEgTMm2E9RiaeVLbSVOY54dJdng
YGeBuJ676KVSxD3aPFfJgrJnE3U3a2/hytY2WrluO1nbI3l+nSm1VqrbGI/AhVKOQpNYLOs+uxFj
T2xWneJdN5fEtxa19nx8dEWvgg4PQopycaE7X34pzJxwHwLhJ4HxOdkm6x1M4nfPGFYTwRzbeq1b
F+cDZZBtYqB2xQhgfFoLxM3uLBTdsbes8PvtIrHDtCW7uaw5YRso4LQkpvZguKhSUR8Dc20mDJZX
zUbiuWtyQKRy0tMTKBu4m1w/MlkOUXx3r/5Cg0SEEGkwvveMNvZy1CoNcWUH/ca9B2wzIBO1N1m8
LJQDjsC9jC5BBaAI5XlF3eZGPo+GE71rsxHzewXp4tvVomDopyf8kkIc+XwlGKr4FVsiU2c+RfIo
LAIKg3HTmGWa+2ggx61Ri1jOZ41YUYcfdRZq6nsTppo4L5sR8VNN56GcIYO6LgtwjFrZ8tcpWPWp
1IFJoEXRDRIk9myjoalBz8bdFqr3tABZh8KbbI/2W/4+7ikS1Js17ydG8fwUM/eI0xoFNQcMWf6R
NIhvaIQIoHfn3wRVJO6W/D3keiqzRR9BO6quRsS0pOvJHa80iY6ZCeD6IZ9Nh7py40XzteaecDX1
zLDlnqUEES8BDjf87TWVmOnOEAaAfR8FDcnUQT+xp9QB9qrUD6I+5fx+1V7qL5ytUPDSl1iZ1NEN
7yDJEkZkXP9qB/Kox+FZC+mFcPsV3wC9goWueBdbSqDPwpCG+6ikslMkI+02b93IxY5473d2PvPE
wSJ0T4CIR1+Iqb1MuQJO7ppajPeeD+FM8hyvkbdZcTA+2GX3sQDAMl3cFeVckM3l7c/tsYKbAB2D
8ewiZ7/tBRD1ggNxeWm1k2mJQTKsZEKi52A2oTv98DrgGSb+iygXg3sq2/SJr2m454iOufCCVRWO
9cmGPDh/7uV6PwrxdZJy8h4bVqTmE+AClWIMiPcNt/KTJzE5IaIP6ohaXYDkOHmAqBpvIPiANuFF
XD8Pw/lUb0NOXhXFUK94ogVmKjxgTotP/pxQ9emhoNMzTlKE3BGvfLrVygudSYRxCymMoCy1X+7T
uHJcd9sY50gaYNj00O3sdjUZj8XxgVav4U4r6IlnNyPL1KcIlQ2jiuuib0SQ0pCkCksZIW7UT00Y
+bzdOZ3evwU7TbeZbU8NADHI8mCY/+SjFTJVyArpCK4HVe2KvaAQ5LtpVkzsu+G/P/LFXry59TR4
MNjbkuRc9PprUYzgAcCDBIDGJwqAbaKvSrkbzhUprPNbXvp6tbAcaOOpIFfowTOSJPdVQZAy3ges
70ZzAd/jkTf063KiWU7jusG7qwEpXx1LDYmotutU010Nghj81/q/p/XJOas+89xvR/Zfd4/iX41x
NFRKDZm55ofyKhjjKqt/bX8BtLGQIEkA3jvi0IxeEKE0y8di7chpIEGMNxVWxVoe+IqGmOxfqjZF
gedqEpi/ThBJAkugQ4QdkCFD9z9/7EvdHONSXholHmdcrSiYZomh+ENiQSyIb77bm34HNsJbAgc+
Fc8cVDqly6kuTUZulbLTaGQmFZXxCpMO8xaJteHZ1ZDgmEE4jmTUgWzMDBTiGSUsA0boHAiX/tme
85Nltq1o+ZEwxiEdeBJaqKjUKlctjJTEtOJoTi7GJqimCHAjkC0hRqJnTCHQC0cksZByxLAGgaqF
OtzFN7jbc5WMlp3aDw0MyAaQogp+dumOaZXa0B4OxSYlwNoSIcQcIrS6I/nGBQ7g3pIBi7+WwXDp
xIq5pmhwIaYuQ7iJGcoaAYJxgWHDU7BIal9fnXWyVixQi4wkIVntNAB7j6T83wWm1uLCo+41vEVH
CZtkWozn+ftOR0h9ZnYMiN4qaSQBpIETm8SB2Y/DFyDjy16QzMfpgflOZuMDcmr5F1E4ptDumBs1
Di/xH3pVKgHVdqjzWFzailmAV2QK1So+qDnEkIz6Sb7Fti7ul86cSJsCanGIb7pkEZ7xECjkR3YU
jRg33FBiVuTGlIW/sOnqxyXelE5lBmtRgDsKn5C2Csl1/aiCmivoCSZAaO0cIsKkcfxRdIJr071p
qRSESj0BBFNPjcam+8saQbspsIuzgCX4Jb4SZXtad0tMYXyiXNu4xU+Nyay6X6vvbRfcazlOkiaj
gBM6Txn6DWRNnccwb26xBtJ1CKgTh9lDgQi5jfo5Ins/d1GY4EOwkhIguJBedeiorch+7JQykF/v
4KDleV3Z1e+z9j2tYCGoE7jgolrJIJd+/Y1CVYb8QW6ApIJoA425trNMviBA0EvIQPIdJ2FN3fsO
BYdQjrMTPcOxY7C5XUj5hCWjzC4yQyPKfoR4HfDDXdGCOeg8sDWh7R5TU6Q0rdrthmZiGIKN7UBn
BWoLvfDA80kMg5DiGcAck7YeKdmc5yG+tzDvoiidqG7xmLx5PMG2gYiasKZAgBp6asKQhHzkXDDs
jY88cQJHmf1EdmRIm/2Xjhwka5vDumtBkR/pLh5owuuzRIdLIEKdq1pL+zk3v87zcX/t8J7IJvE9
S8tuBEI+glywHDSpjBbSwMoZxAuYwwYEKDZSmKXyxqyDiN79C+2oaoWA7eDNMiFLsctPaWWFgdYr
WCwoLArrYO+fYUBqWyZIEgaKE9M7YGpDAMBWjl0+L6zifO3aaB2a2vUyN4nkV1iMQvEzn/Yjn8XU
9ZpuQ2/6L/hKgT3mheMDrS+4teKgu86v6Cu3DXelYQS5AKbile1w0T3PQ4bp93xfg97B4z5eEqsy
BlM4YOoc7z8+zUkEsXjh3nuCHKr76bYbajHP0XpBBbGYliIGduErJzSzgwfYk5ZXYFGxEFZ2I2bU
vrN8WMpjLdJ+to21lzenGV0M6W9m4kenNm0zJX06lG7s2y52a8VuaikwJA0iA34HYnoHYdDY4TQu
jLwOPR1wwc71baXbV3joN0gVkQefaHIO5tsDs5eXUJ+0vBdMkySpuw64mKuMQ4GZrrypgtugFCCi
kKmSVU1OGN90I0uKmce1yTN6DsKS9HpLjRGC8ie7iOp/0MTA0o+XEo6c1DqYOsOMKt3G67cGPbDS
A9EDbkOjb3d6HSzdsijBNoBqpvqMboxpSjYMrFlf8TAMgaKOJqfIeU3Hee/6YPK0HybwPw9DzwH5
DcfQmZwO8sPgXN2ug7lIshA6ASmwTIZXWI0341xpiya6ONHUe2rV4384M00lpa3m5IUXy1y13Wlg
2NigmQ0RHL37TEzKeIbTiGB+shpSZxkBHZ4gwazxpgApxP5+/15k4vPynnvKTS8UA44iBQcNGoKL
mDIl0bg3LmLh5Mcqa3WtCRw8xn0HJ+cwApWEIQFD1+4IUP1XZVbxgcc4d81hUpYzjRK7m14WUxT+
uHkX5jMwU8q7hxTXIfFsUOIouKxdu7Ym2PBcU+cojPmpNcV2SpgIjA7GnYxu6WuBsAWzNCBbK/2d
oodIRzBKuK6Fk6LEPp5tHXVSqPuPZW5DjMzjHYfFGLtZkJaNnHrHeiielRiptKfZ7YhJa3ioM1gV
MkRGxnZse97aDXctUzULc7G8CKJo51sfiut1IPThgDJWY36sEQg51gaZdDd5iEFof20tQLTrIwi8
EH8xW0LsVenyimoII/5DCc3T0RIQ7tgUGRPy0MWzxsJXLBpJGhSlFr7gSzvPQen0HKWD9HB8XKfI
cvS+oyGnKYtKEUc7x1MDsqKwMpCyCeIANYEB+rsHubOTKQ/1960R2/GvAmIHRNxMUltxQsfY0zBQ
dG4rHxkGQTJ10a5ykvYejR2nzHkENVVxcY7Q5DveVzYdxEOSBhBDVWhUFEqgEirIKxPpl1x1eHrf
kMRA0cfqdRbLFSCXKnMnR0JzokMA2EOJ5V+g+6+q76jvHciLo9ohQM33bXqG8OXkPkoE+R2plHRo
eccrUCOY8m7oBgs7jSNoWlBQ6hgYZhq2y+GWFLQFBSWSAFIBdSikKAO8e/rwI2Kemh74eqEgdSlo
nIQaoo/tiSDCKiwiMigoqhERZFIKbg3/BwM5JsVFdkNkKJi3JBnx54tCZMsAZrJJAjHGBtYlaX5a
DqT54R2WmTs3GDnfEWns046O4RTE11XDsrhHV5SlfKeB+EvwbTK+/I+WEgSQDmHjVzgIQJAZE0L1
7q6BIFXwL5EudpimXnz5+vLPugxCJOSSCEFd2nMlxJDihgztyETmPIKx8lRUpbCtYoSQkiOIHa3v
dUmzy6DamzSilRXTQqmOePtCsIPODDmLGREh9fjRvImu31KZ4kTCHOFHsp7Fc0iIOk+H5c+ns3Ea
80aMpRIeEKnS4cOVZ2pgJGTs9frJ8NOwJoTs3hteqEXqopnTq7NiluOHce3K9naCMkBhCEnJTXTo
xt2HwjbpYvjAaYupSUwiEikDlXHTIW3wh/SskreYxhVHevPax1mD+TrrsIQrhjGkCn1Nfp5CQwwH
ANBp6ekDAhz1puS5N/hD28Da3RllIB3wQKLAgEWppELTuPBTsS1T6zQeh1uvGUIKb/QmIhvPZsCx
M/Q0gbw6HYMQhH2le+WBKCQh+D4L3lxOOZqi4Hzvgex9YhyADJ8CDCQaIUklAdcbSwErQapTaymI
hUELGWd4lQ2nFAuPA5cjc3DDIxGIpAokECkA7bU7OwE4VmY0O+BI7GqfFcvimD4DDlTUgx3RZBqI
wCMjAiRYhEYLZ2AwAZivsUoBQIfQNAkQYKRMLnvlQIZMtPhYZhouDkbEq6LwNil/HBCwAEWiJTJg
YDDlNIHbscSDRF+tzdJdrybTpubC6WsHJAYLwETG9daS/URQyB+FLYnm8omtFPncszQMS2lrCwgW
+INmwh3MYhgFANFNCxYhy4px5mphwsRcLsAKsFEAGLzjDXnpzsOy6XUwo7rUT02HFyRUeuca9hYG
FtaxOFKeiy5kZLBhHVJBSJp6E9fyWu9Ez1bnKjoMcLBekbnSjwjZ3ovw5Qc+RBo7/AwBmBE9qLQE
pq8Z2cbqHhe1cwXRv+XlyluR39Z3LZeByHGyTmLYoWUOGR8eMhpoaB4s3JVE7u6op++zsCKlqkIJ
eAoQ8CJHdw8d7omWCSMMjRx5pcCB4rCGkmJzQSGAWBgonYgdE6PeZyajNTHkiFDdblNFSql4XtYS
wkq5xHC4JZuDIpSpEkSIJPXSIVASaqXK2b3fv+303cYISKjkGyItBB8DyW13KUplBiPl84fHdymD
yxHQPm7KnPCyH9cxDxnX1vCPhdXEPfrd7opBGocfRBmJARiIsWULSykGAOCBYTqvcvdj7GrLZWIt
HpOxP1IdkZFDoIKVUWhdCL4wo7E5HQmV5GnO8GHkd0QnjSEIraUT0u9taoOEjIwLswx6x1uGadxw
hBNO0PMErzVovPEDWutyvFennB5FHUAuZc7lt6d1YB32mxKkfXCEv2cYhSEIHNidaQWCRsYBpBTA
sH4JRPoxx7TLtxCR4eBuC7RcLoRfPwz05wA5lTalNbblaMwoTV5cdZUo/SPhs4c88GENwM4yUswl
ZvucF4tgtFim2WBAsYR+tFnqCydOAZ5jbGKQrwToJX4pljVz3gPszhWgcx4Wx7zgh87fKMM+CboM
+bVWi4oPMaA59NZCwQK8rm46K54qJVBOu+HUJvTOo+M2NbbaEtAaNAA63PYwuQi9vy9qFR3wRpv0
PEAeQ7j2UpLLD5UxCJM7ShDNOrfxAwUMej4TC2dD4jPse97p0LusYaB3vjLq7YQb2Pp9WJLkqWTW
Qt4xZqmNJoODJszbIaUxB5/ic0otLqm3RKWExycjIf5AvJhh4NmAZ1xb0vKD6Xmfndhf5XJVHeLR
6LTnlhwBeaT1HeJ9kV4GzHePxu9Nh87DnxV8hUlwKuE7XYAlGIgvWphxpZcoUzbFBBDHKxRGJreS
0JLJD0fAeTlcPDJKug5EG1gCMP4yMdEPRQwzRdM1yQo/tSBBMDOPVXsBZ4UVGPIL2+b9V2fY/ch9
ODv0m0K013Ubmig8C4vI8CZ8hbAJlyLCKXrWnYWUTrnUQh+ApQpiBlHSWQIAWg6BZiw8DoMKw/kM
jRrHspSKiLKwrX3iIex5bJyMx1djo5ySCEaRSn2sVpE5cztNG/wE8jpLWBeh8+AUnK/1JVYQJ4hl
6rnHkG8+AzAaDtwutE0gkD5cxkXttgsGpZ3qKSnnuMSQsBGKfsD9eFrndaNWSYhKkeflOYd3ou9b
LoNpUDLFM5rgsyFAgUtJBwTAc+3W5zo02WMV3JPcwUQFh8/zcfoTdpcew+BOLHCde63YM4FjrQMJ
XO72ddTS3LMCypRFmvcom/FntRZN3kTDD5caLZym+naZsVbeJxPtnZiS0UjCYlr7w6RDpC966+bJ
3d6emyQ+iGOUmQmEnTdTvHK01z6bI5m5cS5cz3XfW2bQwssmOkNV5UREQ91EEiGaBTxQDsdw0GR2
C0qK0Xu9+dHkNo2Is8PVVmGnlTed0Z2zTiN21v0FTK3ozoahvDSGoyPWZTq9UgcogiKE9TaiM9/t
99TWqRLSeo+u883f5MTeLzjnOHHv65dYGBnHPT1vyY+o1O8Q2R3AagYrwx80PifLYxxe8ZRDmF5b
5cb9LLQIIEfNH/SfvlamkV6kOx5Or6O3qwQMHbk6noaqtttttuDtkoYszzCbhxgsE06SjyO63X1W
tDAqlyhY7CYcHr5nrd4meWXQJRn5CLme+B9tFkkjIQTx+A91VaZJ1rDeBggU0eIfieu7qFJmPGmE
qHxNcSusowh+U6cyiUt45TZ621waw/KIUOl1BuZgdtU7lKDeQoEgmkHm6gcqSQBLMVhaHMNCa/zH
tu/8SQ7VgkMx7qUbSSgcWkoEUyvsbfOaxvgS0O3duSErT0/68nFkkatBNuMRYa32xDRubaVkBo1c
tlgF4uamhFLASy4WQsZJTYiWRxooGsHNbNDS4jZcSsbAUmYdG0YCT0UlE6YtEAOz2sy0OkNjKBa8
pOk2F4hAJAUhEHLanKF7SrIIShCEzcxQVirVEBCJ5BxhmrxnQCByEJAIsSKxWDQrc3L6sm9TsKm/
Ot4JtpZt9/xuAa9n3Hr9pNjmydkKsBskwjGAWNE6ID27n4oFWJBvBZFQNILIJeYhyYcPoGleAwSN
V0TOMjfOmSqREZuPmSDuHYGTU7vUPLVLYiURQROPF5+knDbSgcOzwhzPO+szAr798eJrhCw4hAO1
AYQr0zhLxbR0zVpRqb22PytZzwRfoawKS42ceyvbK2qlFcGNrFVSGFcm+6JLoh8IhB3hiYGSLCjg
6gO7JRCvoeMYPXIk03ri6iKCbIdqb8XlHYOJSOwjCIe4FOa0pSdKeBH1en1aCtu3acoucEDhNt1g
ifFIFgpc7+INnMyZ+OGpY1EpF6vzZewgQF35EaMMUHvGFytwe8q0fuz5DQ+AnfBeA89svEJCgoTW
PhS81psTZpHm8kt0UhEkhIYMGCUKE+rltwSjm59rG4gfvT07XeQhBDtej6MAbi9b0iHtuhDUDAgh
2+PY2VDFOpjyd7QBqOmzYfNBkzUTsFOBYxzWgueBwyTUMDK/tLarBt+UeDMAcISg+B9pUI1w+psX
7Htr/TMBSZAFlLbxg8RS1u/Rm/kiViYHgRNr81CLqZtg+ffmtXtCLiFkV2FNlBFKJGdms1VDu1Ji
SWhnL2uWjki2955t3BgmBSGLiBqXYXUOize0TEfn0eIJoHucnNQy+A8zdH3zjmcBLCc3udPcnQ/m
6vIBwe4oACmAnzPjpj4G3jNrxup6udU6QkPkGoahYQ+8Yx/xKIYP+jNcENRg2MpDKsMRn3NDXB/8
XckU4UJBg7ricA==