[Commits] Rev 2811: MWL#89: Cost-based choice between Materialization and IN->EXISTS transformation in file:///home/tsk/mprog/src/5.3-mwl89/

timour at askmonty.org timour at askmonty.org
Fri Sep 24 15:58:11 EEST 2010


At file:///home/tsk/mprog/src/5.3-mwl89/

------------------------------------------------------------
revno: 2811
revision-id: timour at askmonty.org-20100924125800-4frug7qib5v5jaok
parent: timour at askmonty.org-20100917101727-tzznd9k9wrm9jadf
committer: timour at askmonty.org
branch nick: 5.3-mwl89
timestamp: Fri 2010-09-24 15:58:00 +0300
message:
  MWL#89: Cost-based choice between Materialization and IN->EXISTS transformation
  
    Phase 3: Implementation of re-optimization of subqueries with injected predicates
  
  This is a temporary commit as a checkpoint before several changes in order to handle
  sevarl problems with the current implementation.
-------------- next part --------------
=== modified file 'sql/item_subselect.cc'
--- a/sql/item_subselect.cc	2010-09-16 14:06:58 +0000
+++ b/sql/item_subselect.cc	2010-09-24 12:58:00 +0000
@@ -1555,6 +1555,19 @@ Item_in_subselect::single_value_transfor
 }
 
 
+bool Item_in_subselect::fix_having(Item *having, SELECT_LEX *select_lex)
+{
+  bool fix_res= 0;
+  if (!having->fixed)
+  {
+    select_lex->having_fix_field= 1;
+    fix_res= having->fix_fields(thd, 0);
+    select_lex->having_fix_field= 0;
+  }
+  return fix_res;
+}
+
+
 /**
   Transofrm an IN predicate into EXISTS via predicate injection.
 
@@ -1607,6 +1620,9 @@ Item_in_subselect::create_single_in_to_e
 
   DBUG_ENTER("Item_in_subselect::create_single_in_to_exists_cond");
 
+  *where_item= NULL;
+  *having_item= NULL;
+
   if (join_having || select_lex->with_sum_func ||
       select_lex->group_list.elements)
   {
@@ -1626,11 +1642,11 @@ Item_in_subselect::create_single_in_to_e
       item= new Item_func_trig_cond(item, get_cond_guard(0));
     }
 
-    if (item->fix_fields(thd, 0))
+    if (!join_having)
+      item->name= (char*) in_having_cond;
+    *having_item= and_items(join_having, item);
+    if (fix_having(*having_item, select_lex))
       DBUG_RETURN(RES_ERROR);
-
-    *having_item= item;
-    *where_item= NULL;
   }
   else
   {
@@ -1651,11 +1667,10 @@ Item_in_subselect::create_single_in_to_e
                                                 get_cond_guard(0))))
             DBUG_RETURN(RES_ERROR);
         }
-
-        if (having->fix_fields(thd, 0))
-          DBUG_RETURN(RES_ERROR);
-
+        having->name= (char*) in_having_cond;
         *having_item= having;
+        if (fix_having(*having_item, select_lex))
+          DBUG_RETURN(RES_ERROR);
 
         item= new Item_cond_or(item,
                                new Item_func_isnull(orig_item));
@@ -1670,20 +1685,20 @@ Item_in_subselect::create_single_in_to_e
           DBUG_RETURN(RES_ERROR);
       }
 
-      if (item->fix_fields(thd, 0))
-        DBUG_RETURN(RES_ERROR);
-
-      *where_item= item;
+      /*
+        TODO: figure out why the following is done here in 
+        single_value_transformer but there is no corresponding action in
+        row_value_transformer?
+      */
+      item->name= (char *) in_additional_cond;
+      *where_item= and_items(join->conds, item);
+      if (!(*where_item)->fixed && (*where_item)->fix_fields(thd, 0))
+        DBUG_RETURN(RES_ERROR);
     }
     else
     {
       if (select_lex->master_unit()->is_union())
       {
-        /*
-          comparison functions can't be changed during fix_fields()
-          we can assign select_lex->having here, and pass 0 as last
-          argument (reference) to fix_fields()
-        */
         Item *new_having=
           func->create(expr,
                        new Item_ref_null_helper(&select_lex->context, this,
@@ -1697,19 +1712,13 @@ Item_in_subselect::create_single_in_to_e
             DBUG_RETURN(RES_ERROR);
         }
 
-        if (new_having->fix_fields(thd, 0))
-          DBUG_RETURN(RES_ERROR);
-
+        new_having->name= (char*)in_having_cond;
         *having_item= new_having;
-        *where_item= NULL;
+        if (fix_having(*having_item, select_lex))
+          DBUG_RETURN(RES_ERROR);
       }
       else
-      {
         DBUG_ASSERT(FALSE);
-        /* TIMOUR TODO */
-        *having_item= NULL;
-        *where_item= (Item*) select_lex->item_list.head();
-      }
     }
   }
 
@@ -1731,31 +1740,17 @@ Item_in_subselect::inject_single_in_to_e
     this->having= 0;
   */
   Item* join_having= join->having ? join->having : join->tmp_having;
-  bool fix_res= 0;
   DBUG_ENTER("Item_in_subselect::inject_single_in_to_exists_cond");
 
+  /* Both arguments should have been fixed during creation. */
+  DBUG_ASSERT(!having_item || having_item->fixed);
+  DBUG_ASSERT(!where_item  || where_item->fixed);
+
   if (join_having || select_lex->with_sum_func ||
       select_lex->group_list.elements)
   {
-    /*
-      AND and comparison functions can't be changed during fix_fields()
-      we can assign select_lex->having here, and pass 0 as last
-      argument (reference) to fix_fields()
-    */
-    thd->change_item_tree(&select_lex->having, and_items(join_having, having_item));
+    thd->change_item_tree(&select_lex->having, having_item);
     join->having= select_lex->having;
-    if (join->having == having_item)
-      having_item->name= (char*)in_having_cond;
-    select_lex->having_fix_field= 1;
-    /*
-      we do not check join->having->fixed, because Item_and (from and_items)
-      or comparison function (from func->create) can't be fixed after creation
-    */
-    if (!join->having->fixed)
-      fix_res= join->having->fix_fields(thd, 0);
-    select_lex->having_fix_field= 0;
-    if (fix_res)
-      DBUG_RETURN(RES_ERROR);
   }
   else
   {
@@ -1763,66 +1758,24 @@ Item_in_subselect::inject_single_in_to_e
     {
       if (!abort_on_null && select_lex->item_list.head()->maybe_null)
       {
-        /*
-          Item_is_not_null_test can't be changed during fix_fields()
-          we can assign select_lex->having here, and pass 0 as last
-          argument (reference) to fix_fields()
-        */
-        having_item->name= (char*)in_having_cond;
         thd->change_item_tree(&select_lex->having, having_item);
         join->having= select_lex->having;
-        select_lex->having_fix_field= 1;
-        /*
-          we do not check join->having->fixed, because Item_and (from
-          and_items) or comparison function (from func->create) can't be
-          fixed after creation
-        */
-        if (!join->having->fixed)
-          fix_res= join->having->fix_fields(thd, 0);
-        select_lex->having_fix_field= 0;
-        if (fix_res)
-          DBUG_RETURN(RES_ERROR);
       }
-      /*
-        TODO: figure out why the following is done here in 
-        single_value_transformer but there is no corresponding action in
-        row_value_transformer?
-      */
-      where_item->name= (char *)in_additional_cond;
-
-      /*
-        AND can't be changed during fix_fields()
-        we can assign select_lex->having here, and pass 0 as last
-        argument (reference) to fix_fields()
-      */
-      thd->change_item_tree(&select_lex->where, and_items(join->conds, where_item));
+      thd->change_item_tree(&select_lex->where, where_item);
       join->conds= select_lex->where;
       select_lex->where->top_level_item();
-      /*
-        we do not check join->conds->fixed, because Item_and can't be fixed
-        after creation
-      */
-      if (!join->conds->fixed && join->conds->fix_fields(thd, 0))
-        DBUG_RETURN(RES_ERROR);
     }
     else
     {
       if (select_lex->master_unit()->is_union())
       {
-        having_item->name= (char*)in_having_cond;
         thd->change_item_tree(&select_lex->having, having_item);
         join->having= select_lex->having;
-        select_lex->having_fix_field= 1;
-        
         /*
-          we do not check join->having->fixed, because comparison function
-          (from func->create) can't be fixed after creation
+          TODO: why do we set this to 1 here? In all other places we wrap
+          the call to fix_fields inhaving_fix_field=1 / having_fix_field=0.
         */
-        if (!join->having->fixed)
-          fix_res= join->having->fix_fields(thd, 0);
-        select_lex->having_fix_field= 0;
-        if (fix_res)
-          DBUG_RETURN(RES_ERROR);
+        select_lex->having_fix_field= 1;
       }
       else
         DBUG_ASSERT(FALSE);
@@ -1992,7 +1945,6 @@ Item_in_subselect::create_row_in_to_exis
       item_having_part2->top_level_item();
     }
     *having_item= and_items(*having_item, item_having_part2);
-    (*having_item)->top_level_item();
   }
   else
   {
@@ -2074,7 +2026,24 @@ Item_in_subselect::create_row_in_to_exis
       }
       *where_item= and_items(*where_item, item);
     }
-    (*where_item)->fix_fields(thd, 0);
+  }
+
+  if (*where_item)
+  {
+    *where_item= and_items(join->conds, *where_item);
+    if (!(*where_item)->fixed && (*where_item)->fix_fields(thd, 0))
+      DBUG_RETURN(RES_ERROR);
+    (*where_item)->top_level_item();
+  }
+
+  if (*having_item)
+  {
+    if (!join_having)
+      (*having_item)->name= (char*)in_having_cond;
+    *having_item= and_items(join_having, *having_item);
+    if (fix_having(*having_item, select_lex))
+      DBUG_RETURN(RES_ERROR);
+    (*having_item)->top_level_item();
   }
 
   DBUG_RETURN(RES_OK);
@@ -2087,53 +2056,19 @@ Item_in_subselect::inject_row_in_to_exis
                                                 Item *having_item)
 {
   SELECT_LEX *select_lex= join->select_lex;
-  /*
-    The non-transformed HAVING clause of 'join' may be stored differently in
-    JOIN::optimize:
-    this->tmp_having= this->having
-    this->having= 0;
-  */
-  Item* join_having= join->having ? join->having : join->tmp_having;
-  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::inject_row_in_to_exists_cond");
 
-  if (!is_having_used)
+  if (where_item)
   {
-    /*
-      AND can't be changed during fix_fields()
-      we can assign select_lex->where here, and pass 0 as last
-      argument (reference) to fix_fields()
-    */
-    thd->change_item_tree(&select_lex->where, and_items(join->conds, where_item));
+    thd->change_item_tree(&select_lex->where, where_item);
     join->conds= select_lex->where;
-    select_lex->where->top_level_item();
-    if (!join->conds->fixed && join->conds->fix_fields(thd, 0))
-      DBUG_RETURN(RES_ERROR);
   }
 
   if (having_item)
   {
-    bool res;
-    thd->change_item_tree(&select_lex->having,
-                          and_items(join_having, having_item));
+    thd->change_item_tree(&select_lex->having, having_item);
     join->having= select_lex->having;
-    if (having_item == select_lex->having)
-      having_item->name= (char*)in_having_cond;
-    select_lex->having->top_level_item();
-    /*
-      AND can't be changed during fix_fields()
-      we can assign select_lex->having here, and pass 0 as last
-      argument (reference) to fix_fields()
-    */
-    select_lex->having_fix_field= 1;
-    if (!join->having->fixed)
-      res= join->having->fix_fields(thd, 0);
-    select_lex->having_fix_field= 0;
-    if (res)
-      DBUG_RETURN(RES_ERROR);
   }
 
   DBUG_RETURN(RES_OK);

=== modified file 'sql/item_subselect.h'
--- a/sql/item_subselect.h	2010-09-05 15:43:47 +0000
+++ b/sql/item_subselect.h	2010-09-24 12:58:00 +0000
@@ -362,6 +362,7 @@ protected:
   trans_res select_in_like_transformer(JOIN *join);
   trans_res single_value_transformer(JOIN *join);
   trans_res row_value_transformer(JOIN * join);
+  bool fix_having(Item *having, st_select_lex *select_lex);
   trans_res create_single_in_to_exists_cond(JOIN * join,
                                             Item **where_item,
                                             Item **having_item);

=== modified file 'sql/opt_subselect.cc'
--- a/sql/opt_subselect.cc	2010-09-17 10:17:27 +0000
+++ b/sql/opt_subselect.cc	2010-09-24 12:58:00 +0000
@@ -3564,13 +3565,27 @@ bool JOIN::optimize_unflattened_subqueri
 }
 
 
-bool JOIN::choose_subquery_plan()
+bool JOIN::choose_subquery_plan(table_map join_tables)
 {
-  double mat_strategy_cost;    /* The cost to compute IN via materialization. */
-  double in_exists_strategy_cost; /* The cost of the IN->EXISTS strategy. */
-  bool res;
+  /* The original QEP of the subquery. */
+  DYNAMIC_ARRAY save_keyuse; /* Copy of the JOIN::keyuse array. */
+  POSITION save_best_positions[MAX_TABLES+1]; /* Copy of JOIN::best_positions */
+  /* Copies of the JOIN_TAB::keyuse pointers for each JOIN_TAB. */
+  KEYUSE *save_join_tab_keyuse[MAX_TABLES];
+  /* Copies of JOIN_TAB::checked_keys for each JOIN_TAB. */
+  key_map save_join_tab_checked_keys[MAX_TABLES];
+
+  bool in_exists_reoptimized= false;
+  /* The cost to compute IN via materialization. */
+  double materialize_strategy_cost= 1;
+  /* The cost of the IN->EXISTS strategy. */
+  double in_exists_strategy_cost= 0;
+
+  Item_in_subselect *in_subs;
 
   DBUG_ASSERT(in_to_exists_where || in_to_exists_having);
+  DBUG_ASSERT(!in_to_exists_where || in_to_exists_where->fixed);
+  DBUG_ASSERT(!in_to_exists_having || in_to_exists_having->fixed);
   DBUG_ASSERT(select_lex->master_unit()->item &&
               (select_lex->master_unit()->item->substype() ==
                Item_subselect::IN_SUBS ||
@@ -3579,41 +3594,124 @@ bool JOIN::choose_subquery_plan()
                select_lex->master_unit()->item->substype() ==
                Item_subselect::ANY_SUBS));
 
-  Item_in_subselect *in_subs= (Item_in_subselect*)
-                              select_lex->master_unit()->item;
+  in_subs= (Item_in_subselect*) select_lex->master_unit()->item;
+  save_keyuse.elements= 0;
+  save_keyuse.buffer= NULL;
+
+  /*
+    Compute and compare the costs of materialization and in-exists only
+    if materialization is a possible strategy, and if injecting the
+    in-exists conditions may result in a cheaper strategy.
+  */
+  if (in_subs->exec_method == Item_in_subselect::MATERIALIZATION &&
+      in_to_exists_where && const_tables != tables)
+  {
+    JOIN *outer_join= unit->outer_select()->join;
+    JOIN *inner_join= this;
+    /* Cost of the outer JOIN. */
+    double outer_read_time, outer_record_count;
+    /* Cost of the unmodified subquery. */
+    double inner_read_time_1, inner_record_count_1;
+    /* Cost of the subquery with injected IN-EXISTS predicates. */
+    double inner_read_time_2, inner_record_count_2;
+
+    if (outer_join)
+      get_partial_join_cost(outer_join, outer_join->tables,
+                            &outer_read_time, &outer_record_count);
+    else
+    {
+      /* TODO: outer_join can be NULL for DELETE statements. */
+      outer_read_time= 1; /* TODO */
+      outer_record_count= 1;  /* TODO */
+    }
+
+    get_partial_join_cost(inner_join, inner_join->tables,
+                          &inner_read_time_1, &inner_record_count_1);
 
-  /* Always revert to IN->EXISTS. */
-  mat_strategy_cost= 0;
+    /*
+      Re-optimize and cost the subquery taking into account the IN-EXISTS
+      conditions.
+    */
+    if (save_query_plan(&save_keyuse, save_best_positions,
+                        save_join_tab_keyuse, save_join_tab_checked_keys) ||
+        reoptimize(in_to_exists_where, join_tables, save_best_positions))
+      return TRUE;
+    in_exists_reoptimized= true;
+
+    get_partial_join_cost(inner_join, inner_join->tables,
+                          &inner_read_time_2, &inner_record_count_2);
+
+    /* Compute execution costs. */
+    /*
+      1. Compute the cost of the materialization strategy.
+    */
+    double materialization_cost; /* The cost of executing the subquery and */
+                                 /* storing its result in an indexed temp table.*/
+    /* The cost of a lookup into the unique index of the materialized table. */
+    double lookup_cost;
+    double write_row_cost= 1; /* TODO: what is the real cost to write a row? */
+    materialization_cost= inner_read_time_1 +
+                          inner_record_count_1 * write_row_cost;
+    /*
+      The cost of a hash/btree lookup into a unique index of a materialized
+      subquery.
+      TIMOUR: TODO: the block of code below is exact copy/paste from
+      opt_subselect.cc:optimize_semi_join_nests() - refactor it.
+    */
+    uint rowlen= get_tmp_table_rec_length(unit->first_select()->item_list);
+    if (rowlen * inner_record_count_1 < thd->variables.max_heap_table_size)
+      lookup_cost= HEAP_TEMPTABLE_LOOKUP_COST;
+    else
+      lookup_cost= DISK_TEMPTABLE_LOOKUP_COST;
+    materialize_strategy_cost= materialization_cost + outer_record_count * lookup_cost;
+
+    /*
+      2. Compute the cost of the IN=>EXISTS strategy.
+    */
+    /*
+      TODO: There are three sub-strategies to execute an IN-EXISTS subquery:
+      subselect_single_select_engine, subselect_uniquesubquery_engine, and
+      subselect_indexsubquery_engine. Currently we don't take them into account.
+    */
+    in_exists_strategy_cost= outer_record_count * inner_read_time_2;
+  }
+
+  /* TODO: only for testing, remove */
+  materialize_strategy_cost= 0;
   in_exists_strategy_cost= 1;
 
   /*
-    If (1) materialization is a possible strategy based on static analysis, and
-    (2) it is cheaper strategy than the IN->EXISTS transformation, then compute
-    in_subs via the materialization trategy.
+    If (1) materialization is a possible strategy based on static analysis
+    during the prepare phase, then if
+      (2) it is more expensive than the IN->EXISTS transformation, and
+      (3) it is not possible to create usable indexes for the materialization
+          strategy,
+      fall back to IN->EXISTS.
+    otherwise use materialization.
   */
-  if (in_subs->exec_method == Item_in_subselect::MATERIALIZATION && // 1
-      mat_strategy_cost < in_exists_strategy_cost)                  // 2
+  if (in_subs->exec_method == Item_in_subselect::MATERIALIZATION) // 1
   {
-    if (in_subs->setup_mat_engine())
-    {
-      /*
-        In some cases it is not possible to create usable indexes for the
-        materialization strategy, so fall back to IN->EXISTS.
-      */
+    if (materialize_strategy_cost >= in_exists_strategy_cost)     // 2
+      in_subs->exec_method= Item_in_subselect::IN_TO_EXISTS;
+    else if (in_subs->setup_mat_engine())                         // 3
       in_subs->exec_method= Item_in_subselect::IN_TO_EXISTS;
-    }
   }
   else
   {
     /*
-      Previous optimizer phases should have chosen either a materialization
-      or IN->EXISTS strategy.
+      Previous optimizer phases should have chosen either materialization
+      or IN->EXISTS.
     */
     DBUG_ASSERT(in_subs->exec_method == Item_in_subselect::IN_TO_EXISTS);
   }
 
   if (in_subs->exec_method == Item_in_subselect::MATERIALIZATION)
   {
+    /* Restore orginal query plan used for materialization. */
+    if (in_exists_reoptimized)
+      restore_query_plan(&save_keyuse, save_best_positions,
+                         save_join_tab_keyuse, save_join_tab_checked_keys);
+
     /* TODO: should we set/unset this flag for both select_lex and its unit? */
     in_subs->unit->uncacheable&= ~UNCACHEABLE_DEPENDENT;
     select_lex->uncacheable&= ~UNCACHEABLE_DEPENDENT;
@@ -3633,13 +3731,30 @@ bool JOIN::choose_subquery_plan()
       set in the beginning of JOIN::optimize, which was already done.
     */
     select_limit= in_subs->unit->select_limit_cnt;
-
-    // TODO: inner_join->restore_plan (keyuse, best_positions, best_read)
   }
   else if (in_subs->exec_method == Item_in_subselect::IN_TO_EXISTS)
-    res= in_subs->inject_in_to_exists_cond(this);
+  {
+    /* Keep the new query plan with injected conditions, delete the old one. */
+    if (save_keyuse.elements)
+      delete_dynamic(&save_keyuse);
+
+    if (!in_exists_reoptimized && in_to_exists_where && const_tables != tables)
+    {
+      for (uint i= 0; i < tables; i++)
+      {
+        join_tab[i].keyuse= NULL;
+        join_tab[i].checked_keys.clear_all();
+      }
+      reset_dynamic(&keyuse);
+      if (reoptimize(in_to_exists_where, join_tables, NULL))
+        return TRUE;
+    }
+
+    if (in_subs->inject_in_to_exists_cond(this))
+      return TRUE;
+  }
   else
     DBUG_ASSERT(FALSE);
 
-  return res;
+  return FALSE;
 }

=== modified file 'sql/sql_select.cc'
--- a/sql/sql_select.cc	2010-09-17 10:17:27 +0000
+++ b/sql/sql_select.cc	2010-09-24 12:58:00 +0000
@@ -53,7 +53,6 @@ static bool make_join_statistics(JOIN *j
 static bool update_ref_and_keys(THD *thd, DYNAMIC_ARRAY *keyuse,
                                 JOIN_TAB *join_tab,
                                 uint tables, COND *conds,
-                                COND_EQUAL *cond_equal,
                                 table_map table_map, SELECT_LEX *select_lex,
                                 st_sargable_param **sargables);
 static int sort_keyuse(KEYUSE *a,KEYUSE *b);
@@ -936,7 +935,7 @@ JOIN::optimize()
       Item_in_subselect *in_subs= (Item_in_subselect*)
         select_lex->master_unit()->item;
 
-      if (in_subs->exec_method ==  Item_in_subselect::MATERIALIZATION)
+      if (in_subs->exec_method == Item_in_subselect::MATERIALIZATION)
         ; // setup materialized execution structures
       else if (in_subs->exec_method == Item_in_subselect::IN_TO_EXISTS)
       {
@@ -2829,8 +2828,7 @@ make_join_statistics(JOIN *join, TABLE_L
 
   if (conds || outer_join)
     if (update_ref_and_keys(join->thd, keyuse_array, stat, join->tables,
-                            conds, join->cond_equal,
-                            ~outer_join, join->select_lex, &sargables))
+                            conds, ~outer_join, join->select_lex, &sargables))
       goto error;
 
   join->const_table_map= no_rows_const_tables;
@@ -3136,7 +3134,7 @@ make_join_statistics(JOIN *join, TABLE_L
     join->best_read=1.0;
   }
   if ((join->in_to_exists_where || join->in_to_exists_having)
-      && join->choose_subquery_plan())
+      && join->choose_subquery_plan(all_table_map & ~join->const_table_map))
     goto error;
 
   /* Generate an execution plan from the found optimal join order. */
@@ -4089,9 +4087,8 @@ static void add_key_fields_for_nj(JOIN *
 
 static bool
 update_ref_and_keys(THD *thd, DYNAMIC_ARRAY *keyuse,JOIN_TAB *join_tab,
-                    uint tables, COND *cond, COND_EQUAL *cond_equal,
-                    table_map normal_tables, SELECT_LEX *select_lex,
-                    SARGABLE_PARAM **sargables)
+                    uint tables, COND *cond, table_map normal_tables,
+                    SELECT_LEX *select_lex, SARGABLE_PARAM **sargables)
 {
   uint  and_level,i,found_eq_constant;
   KEY_FIELD *key_fields, *end, *field;
@@ -19265,6 +19262,157 @@ bool JOIN::change_result(select_result *
   DBUG_RETURN(FALSE);
 }
 
+
+/**
+  Save the original query execution plan so that the caller can revert to it
+  if needed.
+*/
+int JOIN::save_query_plan(DYNAMIC_ARRAY *save_keyuse,
+                          POSITION *save_best_positions,
+                          KEYUSE **save_join_tab_keyuse,
+                          key_map *save_join_tab_checked_keys)
+{
+  if (keyuse.elements)
+  {
+    DYNAMIC_ARRAY tmp_keyuse;
+    if (my_init_dynamic_array(save_keyuse, sizeof(KEYUSE), 20, 64))
+      return 1;
+    /* Swap the current and the backup keyuse arrays. */
+    tmp_keyuse= keyuse;
+    keyuse= (*save_keyuse);
+    (*save_keyuse)= tmp_keyuse;
+
+    for (uint i= 0; i < tables; i++)
+    {
+      save_join_tab_keyuse[i]= join_tab[i].keyuse;
+      join_tab[i].keyuse= NULL;
+      save_join_tab_checked_keys[i]= join_tab[i].checked_keys;
+      join_tab[i].checked_keys.clear_all();
+    }
+  }
+  memcpy((uchar*) save_best_positions, (uchar*) best_positions,
+         sizeof(POSITION) * (tables + 1));
+  // TODO try remove
+  memset(best_positions, 0, sizeof(POSITION) * (tables + 1));
+  return 0;
+}
+
+
+/**
+  Restore the query plan saved before reoptimization with additional
+  conditions.
+*/
+
+void JOIN::restore_query_plan(DYNAMIC_ARRAY *save_keyuse,
+                              POSITION *save_best_positions,
+                              KEYUSE **save_join_tab_keyuse,
+                              key_map *save_join_tab_checked_keys)
+{
+  if (save_keyuse->elements)
+  {
+    DYNAMIC_ARRAY tmp_keyuse;
+    /*
+      REF analysis is additive - after reoptimization with a conjunction of
+      additional conditions there should be no less access methods than before
+      reoptimizing.
+    */
+    DBUG_ASSERT(keyuse.elements >= save_keyuse->elements);
+    tmp_keyuse= keyuse;
+    keyuse= (*save_keyuse);
+    (*save_keyuse)= tmp_keyuse;
+    delete_dynamic(save_keyuse);
+
+    for (uint i= 0; i < tables; i++)
+    {
+      join_tab[i].keyuse= save_join_tab_keyuse[i];
+      join_tab[i].checked_keys= save_join_tab_checked_keys[i];
+    }
+
+  }
+  memcpy((uchar*) best_positions, (uchar*) save_best_positions,
+         sizeof(POSITION) * (tables + 1));
+}
+
+
+// int JOIN::save_query_plan(DYNAMIC_ARRAY *save_keyuse,
+//                           POSITION *save_best_positions)
+// {
+//   if (keyuse.elements)
+//   {
+//     uint keyuse_buffer_size= keyuse.size_of_element * keyuse.elements;
+//     (*save_keyuse)= keyuse;
+//     if (!(save_keyuse->buffer= (uchar*) my_malloc(keyuse_buffer_size, MYF(0))))
+//       return 1;
+//     memcpy(save_keyuse->buffer, keyuse.buffer, keyuse_buffer_size);
+//     reset_dynamic(&keyuse);
+//   }
+//   memcpy((uchar*) save_best_positions, (uchar*) best_positions,
+//          sizeof(POSITION) * (tables + 1));
+//   return 0;
+// }
+// void JOIN::restore_query_plan(DYNAMIC_ARRAY *save_keyuse,
+//                               POSITION *save_best_positions)
+// {
+//   if (save_keyuse->elements)
+//   {
+//     /*
+//       REF analysis is additive - there should be no less access methods than before
+//       reoptimizing.
+//     */
+//     DBUG_ASSERT(keyuse.elements >= save_keyuse->elements);
+//     uint keyuse_buffer_size= save_keyuse->size_of_element * save_keyuse->elements;
+//     uchar *org_buffer= keyuse.buffer;
+//     keyuse= *save_keyuse;
+//     /*
+//       The above assignment overrides the buffer pointer, restore the original
+//       pointer.
+//     */
+//     keyuse.buffer= org_buffer;
+//     memcpy(keyuse.buffer, save_keyuse->buffer, keyuse_buffer_size);
+//     my_free(save_keyuse->buffer, MYF(0));
+//     reset_dynamic(save_keyuse);
+//   }
+//   memcpy((uchar*) best_positions, (uchar*) save_best_positions,
+//          sizeof(POSITION) * (tables + 1));
+// }
+
+
+/**
+   Reoptimize a query plan taking into account a rewritten WHERE clause.
+*/
+
+int JOIN::reoptimize(Item *rewritten_where, table_map join_tables,
+                     POSITION *save_best_positions)
+{
+  SARGABLE_PARAM *sargables= 0; /* Used only as a dummy parameter. */
+  /* Number of elements in the keyuse array before reoptimization. */
+  uint old_elements= keyuse.elements;
+
+  /* Re-run the REF optimizer to take into account the new conditions. */
+  if (update_ref_and_keys(thd, &keyuse, join_tab, tables, rewritten_where,
+                          ~outer_join, select_lex, &sargables))
+    return 1;
+
+  if (keyuse.elements == old_elements)
+  {
+    /*
+      No need to optimize if no new access methods were discovered.
+    */
+    if (save_best_positions)
+      memcpy((uchar*) best_positions, (uchar*) save_best_positions,
+             sizeof(POSITION) * (tables + 1));
+    return 0;
+  }
+
+  optimize_keyuse(this, &keyuse);
+
+  /* Re-run the join optimizer to compute a new query plan. */
+  if (choose_plan(this, join_tables))
+    return 1;
+
+  return 0;
+}
+
 /**
   @} (end of group Query_Optimizer)
 */

=== modified file 'sql/sql_select.h'
--- a/sql/sql_select.h	2010-09-05 15:43:47 +0000
+++ b/sql/sql_select.h	2010-09-24 12:58:00 +0000
@@ -1369,8 +1369,21 @@ inline bool sj_is_materialize_strategy(u
 
 class JOIN :public Sql_alloc
 {
+private:
   JOIN(const JOIN &rhs);                        /**< not implemented */
   JOIN& operator=(const JOIN &rhs);             /**< not implemented */
+
+protected:
+  /* Support for plan reoptimization with rewritten conditions. */
+  int reoptimize(Item *rewritten_where, table_map join_tables,
+                 POSITION *save_best_positions);
+  int save_query_plan(DYNAMIC_ARRAY *save_keyuse, POSITION *save_positions,
+                      KEYUSE **save_join_tab_keyuse,
+                      key_map *save_join_tab_checked_keys);
+  void restore_query_plan(DYNAMIC_ARRAY *save_keyuse, POSITION *save_positions,
+                      KEYUSE **save_join_tab_keyuse,
+                      key_map *save_join_tab_checked_keys);
+
 public:
   JOIN_TAB *join_tab,**best_ref;
   JOIN_TAB **map2table;    ///< mapping between table indexes and JOIN_TABs
@@ -1746,7 +1759,7 @@ public:
               NULL : join_tab+const_tables;
   }
   bool setup_subquery_caches();
-  bool choose_subquery_plan();
+  bool choose_subquery_plan(table_map join_tables);
 private:
   /**
     TRUE if the query contains an aggregate function but has no GROUP



More information about the commits mailing list