List:Commits« Previous MessageNext Message »
From:Jan Wedvik Date:January 18 2011 8:14am
Subject:bzr commit into mysql-5.1-telco-7.0-spj-scan-vs-scan branch
(jan.wedvik:3409)
View as plain text  
#At file:///net/atum17/export/home/tmp/jw159207/mysql/repo/push-scan-scan/ based on revid:ole.john.aske@stripped

 3409 Jan Wedvik	2011-01-18
      This commit join two implementations of the same algorithm into one.
      This algorithm merges sets of possible parent operations for two different
      key fields.
      This is purely a refactoring to eliminate duplicate code. It should not alter 
      functionality in any way.

    modified:
      sql/ha_ndbcluster.cc
=== modified file 'sql/ha_ndbcluster.cc'
--- a/sql/ha_ndbcluster.cc	2011-01-17 14:33:23 +0000
+++ b/sql/ha_ndbcluster.cc	2011-01-18 08:13:59 +0000
@@ -554,11 +554,6 @@ public:
   const AQP::Table_access* get_referred_table_access(
                   const ndb_table_access_map& used_tables) const;
 
-  void add_parent_candidate(
-                  const ndb_table_access_map& table,
-                  const ndb_table_access_map& old_parents,
-                  ndb_table_access_map& parents) const;
-
   bool is_pushable_as_parent(
                   const AQP::Table_access* table);
 
@@ -832,49 +827,6 @@ ndb_pushed_builder_ctx::get_referred_tab
 } // ndb_pushed_builder_ctx::get_referred_table_access
 
 /**
- *  add_parent_candidate()
- *
- *  We have located a ref. to a parent table within our pushed join scope.
- *  Due to the possible equality set replacement which may take place, we may
- *  have multiple parent candidates for a single key_item in the join condition.
- *  
- *  Update our set of 'parents' references such that it only contain parent
- *  tables which are/may be directly refered by all key_items in the join condition
- *    or:
- *  the table refered by the join conditin should be reachable as a grand parent
- *  of the table(s) in the parents list.
- *
- *  - table: bitmap of table being added as parent candidate.
- *  - old_parents: Set of parents calculated for all the previous key_items.
- *  - parents: Set of parent candidates currently being calculated for this key_item.
- */
-void
-ndb_pushed_builder_ctx::add_parent_candidate(const ndb_table_access_map& table,
-                                             const ndb_table_access_map& old_parents,
-                                             ndb_table_access_map& parents) const
-
-{
-  DBUG_ASSERT(m_join_scope.contain(table));
-  if (!parents.contain(table)) // referred_table not already parent
-  {
-    if (old_parents.is_clear_all()  ||  // Initial assignment
-        old_parents.contain(table))     // Parent is common
-    {
-      parents.add(table);
-    }
-    else
-    {
-      const AQP::Table_access* const referred_table= get_referred_table_access(table);
-      ndb_table_access_map grandparents= m_tables[referred_table->get_access_no()].m_ancestors;
-      if (grandparents.is_overlapping(old_parents)) // Parent is real parent
-      {
-        parents.add(table);
-      }
-    }
-  }
-} // ndb_pushed_builder_ctx::add_parent_candidate
-
-/**
  * Set up the 'm_maybe_pushable' property of each table from the 'Abstract Query Plan' associated
  * with this ndb_pushed_builder_ctx. A table may be possibly pushable as both:
  * PUSHABLE_AS_CHILD and/or PUSHABLE_AS_PARENT.
@@ -968,16 +920,16 @@ ndb_pushed_builder_ctx::is_pushable_as_p
  * @param[in] table The table access operation to which the key item belongs.
  * @param[in] key_item The key_item to examine
  * @param[in] key_part_info Metatdata about the key item.
- * @param[in,out] parents In: The set of possible parents for all preceding key 
- *    items (or the empty set for the first key item). Out: The set of possible 
- *    parents for 'key_item' and all preceding key items.
- * @return True if at least one possible parent was found.
+ * @param[out] field_parents The set of possible parents for 'key_item' 
+ * ('join_root' if keys are constant).
+ * @return True if at least one possible parent was found. (False means that 
+ * operation cannot be pushed).
  */
 bool ndb_pushed_builder_ctx
 ::find_field_parents(const AQP::Table_access* table,
                      const Item* key_item, 
                      const KEY_PART_INFO* key_part_info,
-                     ndb_table_access_map& parents)
+                     ndb_table_access_map& field_parents)
 {
   DBUG_ENTER("find_field_parents()");
   const uint tab_no = table->get_access_no();
@@ -986,6 +938,7 @@ bool ndb_pushed_builder_ctx
   // mysql parameters in addition to contant values/expressions
   if (key_item->const_item())  // ...->const_during_execution() ?
   {
+    field_parents= ndb_table_access_map(join_root());
     DBUG_PRINT("info", (" Item type:%d is 'const_item'", key_item->type()));
     DBUG_RETURN(true);
   }
@@ -1033,18 +986,12 @@ bool ndb_pushed_builder_ctx
    *      pushed scope.
    *  2)  By using the equality set, we may find alternative parent references which
    *      may make this a pushed join.
-   *  3)  In the steps above we may have found parent references which was 
-   *      temp. rejected as they were not in the set of common parents (old_parents).
-   *      Take a second look at rejected 'old_parents' and add any of these which refer
-   *      a parent as a grandparent.
    */
 
   ///////////////////////////////////////////////////////////////////
   // 0) Prepare for calculating parent candidates for this FIELD_ITEM
   //
-  ndb_table_access_map field_possible_parents;
-  ndb_table_access_map old_parents(parents);
-  parents.clear_all();
+  field_parents.clear_all();
 
   ////////////////////////////////////////////////////////////////////
   // 1) Add our existing parent reference to the set of parent candidates
@@ -1053,8 +1000,7 @@ bool ndb_pushed_builder_ctx
 
   if (m_join_scope.contain(parent_map))
   {
-    field_possible_parents.add(parent_map);
-    add_parent_candidate (parent_map, old_parents, parents);
+    field_parents.add(parent_map);
   }
 
   //////////////////////////////////////////////////////////////////
@@ -1078,50 +1024,22 @@ bool ndb_pushed_builder_ctx
                     get_referred_table_access_name(substitute_field),
                     get_referred_field_name(substitute_field)));
 
-        field_possible_parents.add(substitute_table);
-        add_parent_candidate (substitute_table, old_parents, parents);
+        field_parents.add(substitute_table);
       }
     }
     substitute_field= equal_iter.next();
   } // while(substitute_field != NULL)
 
-  ////////////////////////////////////////////////////////////////////////////////
-  // 3) Handle possible rejected 'old_parents' which refer any possible_parents as
-  //    a grandparent
-  if (!field_possible_parents.is_clear_all())
-  {
-    old_parents.subtract(parents);
-    ndb_table_access_map inspected;
-
-    // Add all 'old_parents[parent_no]' with some of 'field_possible_parents' as grandparents
-    for (uint parent_no= join_root()->get_access_no();
-         !(inspected==old_parents);
-         parent_no++)
-    {
-      DBUG_ASSERT(parent_no < tab_no);
-      const AQP::Table_access* const table = m_plan.get_table_access(parent_no);
-      ndb_table_access_map table_map(table);
-      if (old_parents.contain(table_map))
-      {
-        inspected.add(table_map);
-        if (is_child_of(table,field_possible_parents))
-          parents.add(table_map);
-      }
-    }
-    if (parents.is_clear_all())
-    {
-      EXPLAIN_NO_PUSH("Can't push table '%s' as child of '%s', "
-                      "no parents found within scope",
-                      table->get_table()->alias, 
-                      join_root()->get_table()->alias);
-      DBUG_RETURN(false);
-    }
+  if (!field_parents.is_clear_all())
+  {
+    DBUG_RETURN(true);
   }
-  else if (m_const_scope.contain(parent_map))
+
+  if (m_const_scope.contain(parent_map))
   {
     // This key item is const. and did not cause the set of possible parents
     // to be recalculated. Reuse what we had before this key item.
-    DBUG_ASSERT(parents.is_clear_all());
+    DBUG_ASSERT(field_parents.is_clear_all());
     /** 
      * Scan queries cannot be pushed if the pushed query may refer column 
      * values (paramValues) from rows stored in a join cache.  
@@ -1149,7 +1067,8 @@ bool ndb_pushed_builder_ctx
                != referred_tab);
 
     } // if (!is_lookup_operation(root_type)
-    parents= old_parents;
+    field_parents= ndb_table_access_map(join_root());
+    DBUG_RETURN(true);
   }
   else
   {
@@ -1160,8 +1079,7 @@ bool ndb_pushed_builder_ctx
                      get_referred_field_name(key_item_field));
     DBUG_RETURN(false);
   }
-  DBUG_RETURN(true);
-}
+} // find_field_parents()
 
 /***************************************************************
  *  is_pushable_as_child()
@@ -1257,25 +1175,60 @@ ndb_pushed_builder_ctx::is_pushable_as_c
                       table->get_no_of_key_fields()));
 
   ndb_table_access_map current_parents;
-  ndb_table_access_map parents;
+  ndb_table_access_map parents(join_root());
 
   for (uint key_part_no= 0; 
        key_part_no < table->get_no_of_key_fields(); 
        key_part_no++)
   {
     const Item* const key_item= table->get_key_field(key_part_no);
-    join_items[key_part_no] = key_item;
+    join_items[key_part_no]= key_item;
+    current_parents.add(ndb_table_access_map(key_item->used_tables()));
+
     /* All parts of the key must be fields in some of the preceeding 
      * tables 
      */
+    ndb_table_access_map field_parents;
     if (!find_field_parents(table,
                             key_item,
                             table->get_key_part_info(key_part_no), 
-                            parents))
+                            field_parents))
     {
       DBUG_RETURN(false);
     }
-    current_parents.add(ndb_table_access_map(key_item->used_tables()));
+    /* Now we must merge the set of possible parents for this key with the set
+     * of possible parents for all preceding keys.
+     */
+    ndb_table_access_map new_parents(parents);
+    // First find the operations present in both sets.
+    new_parents.intersect(field_parents);
+
+    /* Secondly, add each operation which is only in one of the sets, but
+     * which is a descendant of some operation in the other set.
+     * The SPJ block can handle field references to any ancestor operation,
+     * not just the (direct) parent. 
+     */
+    for (uint parent_no= join_root()->get_access_no(); parent_no < tab_no;
+         parent_no++)
+    {
+      const AQP::Table_access* const parent_candidate= 
+        m_plan.get_table_access(parent_no);
+
+      if (parents.contain_table(parent_candidate) && 
+          !field_parents.contain_table(parent_candidate) &&
+          is_child_of(parent_candidate, field_parents))
+      {
+        new_parents.add(parent_candidate);
+      }
+      else if (!parents.contain_table(parent_candidate) && 
+          field_parents.contain_table(parent_candidate) &&
+          is_child_of(parent_candidate, parents))
+      {
+        new_parents.add(parent_candidate);
+      }
+    }
+    parents= new_parents;
+
   } // for (uint key_part_no= 0 ...
 
   join_items[table->get_no_of_key_fields()]= NULL;


Attachment: [text/bzr-bundle] bzr/jan.wedvik@sun.com-20110118081359-0n72j4s38myw954r.bundle
Thread
bzr commit into mysql-5.1-telco-7.0-spj-scan-vs-scan branch(jan.wedvik:3409) Jan Wedvik18 Jan