[Commits] Rev 3758: MDEV-5470: Cost-based subquery item pushdown must take into account semi-joins

Sergei Petrunia psergey at askmonty.org
Thu Dec 19 00:49:22 EET 2013


At http://bazaar.launchpad.net/~maria-captains/maria/10.0-mdev83
 
------------------------------------------------------------

revno: 3758
committer: Sergey Petrunya <psergey at askmonty.org>
branch nick: 10.0-mdev83
timestamp: Thu 2013-12-19 06:50:28 +0400
message:
  MDEV-5470: Cost-based subquery item pushdown must take into account semi-joins
  - When moving expensive conditions, take into account that semi-joins limit
    where they can be moved.
  - This is only execution part in JOIN::setup_dynamic_conditions(). Optimization
    part is not yet present.
  - No testcases yet.
  - Moving inside SJ-Materialization nests doesn't seem to be supported (either 
    before this patch or after. This patch itself does take SJ-Materialization 
    into account) 

=== modified file 'sql/item_cmpfunc.cc'
--- sql/item_cmpfunc.cc	2013-11-01 11:10:38 +0000
+++ sql/item_cmpfunc.cc	2013-12-19 02:50:28 +0000
@@ -6591,6 +6591,8 @@ void Item_func_collect_stats::dbug_print
 }
 #endif /*DBUG_OFF*/
 
+JOIN_TAB *find_last_tab_for_dynamic_cond(table_map cond_tables,
+                                         JOIN *join, JOIN_TAB *join_tab);
 
 Item_func_dynamic_cond::Item_func_dynamic_cond(Item *cond, JOIN_TAB *atab, JOIN_TAB **ctab)
   : Item_func_collect_stats(cond)
@@ -6624,13 +6626,15 @@ Item_func_dynamic_cond::Item_func_dynami
   if (active_tab->bush_root_tab)
   {
     first_tab= active_tab->bush_root_tab->bush_children->start;
-    last_tab= active_tab->bush_root_tab->bush_children->end;
+    //last_tab= active_tab->bush_root_tab->bush_children->end;
   }
   else
   {
     first_tab= join->join_tab + join->const_tables;
-    last_tab= join->join_tab + join->top_join_tab_count;
+    //last_tab= join->join_tab + join->top_join_tab_count;
   }
+  last_tab= find_last_tab_for_dynamic_cond(cond->used_tables(), 
+                                           active_tab->join, active_tab);
 
   DBUG_ASSERT(active_tab >= first_tab && active_tab < last_tab);
 

=== modified file 'sql/item_cmpfunc.h'
--- sql/item_cmpfunc.h	2013-10-18 19:56:55 +0000
+++ sql/item_cmpfunc.h	2013-12-19 02:50:28 +0000
@@ -561,14 +561,20 @@ class Item_func_collect_stats : public I
 
 class Item_func_dynamic_cond : public Item_func_collect_stats
 {
-protected:
+protected: // as if there were any ancestor classes?
   List<Item_subselect> subqueries;
   /* The join_tab where the condition is currently 'pushed'.*/
   st_join_table *active_tab;
   /* The join_tab currently being executed. */
   st_join_table **exec_tab;
   /* The boundaries of the sub-plan where this predicate can be pushed. */
-  st_join_table *first_tab, *last_tab;
+  st_join_table *first_tab;
+  st_join_table *last_tab;  //psergey-todo: this should point to the last tab.
+                            // conditions depending on semi-join tables have 
+                            // limits re. how far they can be moved.
+public:
+  inline st_join_table * get_last_tab() { return last_tab; }
+protected:
   /*
     The relative access cost based on optimizer estimates. This is the cost
     of all access methods per one record from the first table in the plan.

=== modified file 'sql/opt_subselect.cc'
--- sql/opt_subselect.cc	2013-11-04 15:56:09 +0000
+++ sql/opt_subselect.cc	2013-12-19 02:50:28 +0000
@@ -1480,6 +1480,7 @@ static bool convert_subq_to_sj(JOIN *par
   sj_nest->sj_subq_pred= subq_pred;
   sj_nest->original_subq_pred_used_tables= subq_pred->used_tables() |
                                            subq_pred->left_expr->used_tables();
+  sj_nest->sj_strategys_join_tab= uint(-1);
   /* Nests do not participate in those 'chains', so: */
   /* sj_nest->next_leaf= sj_nest->next_local= sj_nest->next_global == NULL*/
   emb_join_list->push_back(sj_nest);
@@ -4321,6 +4322,21 @@ int init_dups_weedout(JOIN *join, uint f
 
 
 /*
+  For each SJ-inner table in [start_tab; end_tab], set emb_sj_nest to idx
+*/
+static void update_sj_strategys_join_tab(JOIN_TAB *start_tab, 
+                                         JOIN_TAB *end_tab,
+                                         uint idx)
+{
+  for (JOIN_TAB *j= start_tab; j < end_tab; j++)
+  {
+    TABLE_LIST *emb_nest;
+    if ((emb_nest= j->emb_sj_nest))
+      emb_nest->sj_strategys_join_tab= idx;
+  }
+}
+
+/*
   Setup the strategies to eliminate semi-join duplicates.
   
   SYNOPSIS
@@ -4448,6 +4464,10 @@ int setup_semijoin_dups_elimination(JOIN
 
         for (uint j= i; j < i + pos->n_sj_tables; j++)
           join->join_tab[j].inside_loosescan_range= TRUE;
+        
+        update_sj_strategys_join_tab(join->join_tab + i, 
+                                     join->join_tab + i + pos->n_sj_tables,
+                                     i + pos->n_sj_tables - 1);
 
         /* Calculate key length */
         keylen= 0;
@@ -4461,6 +4481,7 @@ int setup_semijoin_dups_elimination(JOIN
           tab[pos->n_sj_tables - 1].do_firstmatch= tab;
         i+= pos->n_sj_tables;
         pos+= pos->n_sj_tables;
+
         break;
       }
       case SJ_OPT_DUPS_WEEDOUT:
@@ -4503,6 +4524,9 @@ int setup_semijoin_dups_elimination(JOIN
             break;
           }
         }
+        update_sj_strategys_join_tab(join->join_tab + i, 
+                                     join->join_tab + i + pos->n_sj_tables,
+                                     i + pos->n_sj_tables - 1);
 
         init_dups_weedout(join, first_table, i, i + pos->n_sj_tables - first_table);
         i+= pos->n_sj_tables;
@@ -4558,6 +4582,9 @@ int setup_semijoin_dups_elimination(JOIN
           }
         }
         j[-1].do_firstmatch= jump_to;
+        update_sj_strategys_join_tab(join->join_tab + i, 
+                                     join->join_tab + i + pos->n_sj_tables,
+                                     i + pos->n_sj_tables - 1);
         i+= pos->n_sj_tables;
         pos+= pos->n_sj_tables;
 

=== modified file 'sql/sql_select.cc'
--- sql/sql_select.cc	2013-11-08 12:36:02 +0000
+++ sql/sql_select.cc	2013-12-19 02:50:28 +0000
@@ -24608,8 +24608,8 @@ double JOIN::static_pushdown_cost(uint i
   @param pred      the predicate to be wrapped in Item_func_dynamic_cond
   @param init_tab  the initial 'active' JOIN_TAB where the dynamic predicate
                    is pushed to
-  @param cur_tab   pointer to the JOIN_TAB* that stores the current JOIN_TAB
-                   during execution
+  @param active_tab_ptr   pointer to the JOIN_TAB* that stores the current JOIN_TAB
+                          during execution
 */
 static Item_func_collect_stats *
 wrap_with_dynamic_conds(Item *pred, JOIN_TAB *init_tab, JOIN_TAB **active_tab_ptr,
@@ -24674,6 +24674,81 @@ wrap_with_dynamic_conds(Item *pred, JOIN
 }
 
 
+/*
+  @brief Find the last JOIN_TAB that a condition can be attached.
+  
+
+  @param cond_tables  used_tables() of the condition that we intend to move.
+  @param join_tab     The left-most join tab where the condition can be
+                      attached (in other words, default attachment point)
+
+  @detail
+  In a regular inner join, one can take a condition that is attached to a
+  table $T, and move it to any table that comes after $T.
+
+  When semi-joins are present, this is no longer true. Detailed explanation
+  can be found in maria-developers@, email "Movable conditions and semi-joins".
+  In short:
+
+  - Inside an SJ-Materialization nest, a condition can be moved to any table to
+    the right, but it must stay within the nest. (We don't support nested 
+    semi-joins, so one will not find semi-joins inside an SJ-M nest)
+
+  - All other Semi-Join strategies have a "range" where they apply. If a
+    condition depends on a table that is within a semi-join, it must not be
+    moved over the right edge of the range.
+*/
+
+JOIN_TAB *find_last_tab_for_dynamic_cond(table_map cond_tables,
+                                         JOIN *join, JOIN_TAB *join_tab)
+{
+  if (join_tab->bush_root_tab)
+  {
+    /* 
+      We are inside SJ-Materialization nest. There are no semi-joins here, 
+      return the last tab in the nest.
+    */
+    return join_tab->bush_root_tab->bush_children->end;
+  }
+  
+  /* Start from the right-most bound */
+  uint last_tab = join->top_join_tab_count;
+
+  cond_tables= cond_tables & ~(PSEUDO_TABLE_BITS | join->const_table_map);
+  /*
+    Walk through semi-joins that this table depends on, and check their last
+    join tabs. The smallest last join tab sets the limit about how far right
+    the condition can be moved.
+  */
+  Table_map_iterator tm_it(cond_tables);
+  int tableno;
+  while ((tableno = tm_it.next_bit()) != Table_map_iterator::BITMAP_END)
+  {
+    TABLE_LIST *sj_nest;
+    if ((sj_nest= join->map2table[tableno]->emb_sj_nest))
+    {
+      if (sj_nest->is_active_sjm())
+      {
+        /*
+          Whoa this condition also depends on a table from within
+          SJ-Materialization nest. (Can happen possible because of equality
+          propagation/substitution).  If we didn't return earlier in this
+          function, we're not inside a semi-join nest.  A value that depends
+          on a table within a SJ-Materialization nest means that it depends on
+          the materialized table columns.
+        */
+        continue;
+      }
+
+      if (sj_nest->sj_strategys_join_tab != uint(-1) && 
+          sj_nest->sj_strategys_join_tab < last_tab)
+        last_tab= sj_nest->sj_strategys_join_tab;
+    }
+  }
+  return join->join_tab + last_tab;
+}
+
+
 /**
   Make expensive subqueries dynamically pushdownable.
 */
@@ -24703,7 +24778,12 @@ bool JOIN::setup_dynamic_conditions()
     Update the least cardinality join_tab for each tab for the chosen join order.
     Check if there are any conditions at all that need to be made dynamic.
   */
-  min_tab= NULL;
+  min_tab= NULL; 
+  /*
+    psergey-todo: the following loop should walk inside SJ-Materialization
+    nests, too. Maybe, this whole function should be invoked for each
+    SJ-Materilization nest.
+  */
   for (tab= last_tab - 1; tab >= first_tab; tab--)
   {
     if (optimizer_flag(thd, OPTIMIZER_SWITCH_STATIC_COND_PUSHDOWN))
@@ -24746,7 +24826,8 @@ bool JOIN::setup_dynamic_conditions()
   */
   for (tab= first_tab; tab < last_tab; tab++)
   {
-    Item_func_collect_stats *wrapped_select_cond= NULL, *cur_wrapped_cond;
+    Item_func_collect_stats *wrapped_select_cond= NULL;
+    Item_func_dynamic_cond *cur_wrapped_cond;
 
     if (tab->select_cond &&
         !(wrapped_select_cond=
@@ -24800,14 +24881,29 @@ bool JOIN::setup_dynamic_conditions()
       Add all dynamic conditions pushed to previous JOIN_TABs also to the
       current JOIN_TAB. This allows to "move" a dynamic condition
       from one tab to another by enabling it for the corrseponding tab.
+
+      psergey-todo: conditions have limits on how far to the right they can be
+      moved (Item_func_dynamic_cond::last_tab).  Don't attach conditions to
+      where they can't be moved.
     */
     if (!prev_dynamic_conds.is_empty())
     {
-      List_iterator_fast<Item_func_dynamic_cond> dyn_cond_it(prev_dynamic_conds);
-      if (!wrapped_select_cond)
-        wrapped_select_cond= dyn_cond_it++;
+      List_iterator<Item_func_dynamic_cond> dyn_cond_it(prev_dynamic_conds);
       while ((cur_wrapped_cond= dyn_cond_it++))
-        wrapped_select_cond->add_pred(cur_wrapped_cond);
+      {
+        if (!wrapped_select_cond)
+          wrapped_select_cond= cur_wrapped_cond;
+        else
+          wrapped_select_cond->add_pred(cur_wrapped_cond);
+        
+        /*
+          psergey-todo: conditions have limits on how far to the right they can be
+          moved (Item_func_dynamic_cond::last_tab).  Don't attach conditions to
+          where they can't be moved.
+        */
+        if (cur_wrapped_cond->get_last_tab() == tab)
+          dyn_cond_it.remove();
+      }
     }
     prev_dynamic_conds.concat(&cur_dynamic_conds);
     cur_dynamic_conds.empty();

=== modified file 'sql/table.h'
--- sql/table.h	2013-09-25 18:07:06 +0000
+++ sql/table.h	2013-12-19 02:50:28 +0000
@@ -1721,6 +1721,9 @@ struct TABLE_LIST
   table_map     sj_inner_tables;
   /* Number of IN-compared expressions */
   uint          sj_in_exprs;
+
+  //psergey-todo: add the index of last table in the join order
+  uint          sj_strategys_join_tab;
   
   /* If this is a non-jtbm semi-join nest: corresponding subselect predicate */
   Item_in_subselect  *sj_subq_pred;



More information about the commits mailing list