List:Commits« Previous MessageNext Message »
From:Ole John Aske Date:September 27 2011 1:34pm
Subject:bzr push into mysql-5.1-telco-7.0-spj-scan-vs-scan branch
(ole.john.aske:3565 to 3566)
View as plain text  
 3566 Ole John Aske	2011-09-27
      Optimization of how parent operations are choosen in SPJ queries.
      
      Patch introduce usage of fanout-statistics in optimization of
      how we select 'parent relations' for scan childs. 

    modified:
      sql/abstract_query_plan.cc
      sql/abstract_query_plan.h
      sql/ha_ndbcluster_push.cc
      sql/ha_ndbcluster_push.h
 3565 Ole John Aske	2011-09-27
      Changed some MTR tests which had detoriated such that they didn't test what they was
      supposed to (Due to improvements in the pushability analysis such that more of
      the query was pushed then intended)
      
      Furthermore changed some other test to make them more explicit 'scan-bushy' - as they
      are supposed to be in order to test what they are designed for.

    modified:
      mysql-test/suite/ndb/r/ndb_join_pushdown.result
      mysql-test/suite/ndb/t/ndb_join_pushdown.test
=== modified file 'sql/abstract_query_plan.cc'
--- a/sql/abstract_query_plan.cc	2011-07-01 06:25:45 +0000
+++ b/sql/abstract_query_plan.cc	2011-09-27 13:33:51 +0000
@@ -261,6 +261,33 @@ namespace AQP
     return get_join_tab()->table;
   }
 
+  double Table_access::get_fanout() const
+  {
+    switch (get_access_type())
+    {
+      case AT_PRIMARY_KEY:
+      case AT_UNIQUE_KEY:
+        return 1.0;
+
+      case AT_ORDERED_INDEX_SCAN:
+        DBUG_ASSERT(get_join_tab()->join->best_positions[m_tab_no].records_read>0.0);
+        return get_join_tab()->join->best_positions[m_tab_no].records_read;
+
+      case AT_MULTI_PRIMARY_KEY:
+      case AT_MULTI_UNIQUE_KEY:
+      case AT_MULTI_MIXED:
+        DBUG_ASSERT(get_join_tab()->join->best_positions[m_tab_no].records_read>0.0);
+        return get_join_tab()->join->best_positions[m_tab_no].records_read;
+
+      case AT_TABLE_SCAN:
+        DBUG_ASSERT(get_join_tab()->table->file->stats.records>0.0);
+        return get_join_tab()->table->file->stats.records;
+
+      default:
+        return 99999999.0;
+    }
+  }
+
   /** Get the JOIN_TAB object that corresponds to this operation.*/
   const JOIN_TAB* Table_access::get_join_tab() const
   {

=== modified file 'sql/abstract_query_plan.h'
--- a/sql/abstract_query_plan.h	2011-09-12 11:23:46 +0000
+++ b/sql/abstract_query_plan.h	2011-09-27 13:33:51 +0000
@@ -205,6 +205,8 @@ namespace AQP
 
     st_table* get_table() const;
 
+    double get_fanout() const;
+
     Item_equal* get_item_equal(const Item_field* field_item) const;
 
     void dbug_print() const;

=== modified file 'sql/ha_ndbcluster_push.cc'
--- a/sql/ha_ndbcluster_push.cc	2011-09-09 13:21:05 +0000
+++ b/sql/ha_ndbcluster_push.cc	2011-09-27 13:33:51 +0000
@@ -1063,12 +1063,20 @@ ndb_pushed_builder_ctx::optimize_query_p
   DBUG_ENTER("optimize_query_plan");
   const uint root_no= m_join_root->get_access_no();
 
+  for (uint tab_no= root_no; tab_no<m_plan.get_access_count(); tab_no++)
+  {
+    if (m_join_scope.contain(tab_no))
+    {
+      m_tables[tab_no].m_fanout = m_plan.get_table_access(tab_no)->get_fanout();
+      m_tables[tab_no].m_child_fanout = 1.0;
+    }
+  }
+
   // Find an optimal order for joining the tables
   for (uint tab_no= m_plan.get_access_count()-1;
        tab_no > root_no;
        tab_no--)
   {
-    struct pushed_tables &table= m_tables[tab_no];
     if (!m_join_scope.contain(tab_no))
       continue;
 
@@ -1078,6 +1086,7 @@ ndb_pushed_builder_ctx::optimize_query_p
      * don't skip any dependent parents from our ancestors
      * when selecting the actuall 'm_parent' to be used.
      */
+    pushed_tables &table= m_tables[tab_no];
     if (!table.m_depend_parents.is_clear_all())
     {
       ndb_table_access_map const &dependency= table.m_depend_parents;
@@ -1115,12 +1124,40 @@ ndb_pushed_builder_ctx::optimize_query_p
 
     /**
      * In order to take advantage of the parallelism in the SPJ block; 
-     * Choose the first possible parent candidate. Will result in the
-     * most 'bushy' query plan (aka: star-join)
+     * Initial parent candidate is the first possible among 'parents'.
+     * Will result in the most 'bushy' query plan (aka: star-join)
      */
     parent_no= parents.first_table(root_no);
+
+    if (table.m_fanout*table.m_child_fanout > 1.0 ||
+        !ndbcluster_is_lookup_operation(m_plan.get_table_access(tab_no)->get_access_type()))
+    {
+      /**
+       * This is a index-scan or lookup with scan childs.
+       * Push optimization for index-scan execute:
+       *
+       * These are relative expensive operation which we try to avoid to 
+       * execute whenever possible. By making them depending on parent 
+       * operations with high selectivity, they will be eliminated when
+       * the parent returns no matching rows.
+       *
+       * -> Execute index-scan after any such parents
+       */
+      for (uint candidate= parent_no+1; candidate<parents.length(); candidate++)
+      {
+        if (parents.contain(candidate))
+        {
+          if (m_tables[candidate].m_fanout > 1.0)
+            break;
+
+          parent_no= candidate;     // Parent candidate is selective, eval after
+        }
+      }
+    }
+
     DBUG_ASSERT(parent_no < tab_no);
     table.m_parent= parent_no;
+    m_tables[parent_no].m_child_fanout*= table.m_fanout*table.m_child_fanout;
 
     ndb_table_access_map dependency(table.m_depend_parents);
     dependency.clear_bit(parent_no);
@@ -1134,7 +1171,7 @@ ndb_pushed_builder_ctx::optimize_query_p
   {
     if (m_join_scope.contain(tab_no))
     {
-      struct pushed_tables &table= m_tables[tab_no];
+      pushed_tables &table= m_tables[tab_no];
       const uint parent_no= table.m_parent;
       table.m_ancestors= m_tables[parent_no].m_ancestors;
       table.m_ancestors.add(parent_no);

=== modified file 'sql/ha_ndbcluster_push.h'
--- a/sql/ha_ndbcluster_push.h	2011-09-09 13:21:05 +0000
+++ b/sql/ha_ndbcluster_push.h	2011-09-27 13:33:51 +0000
@@ -283,6 +283,8 @@ private:
       m_depend_parents(), 
       m_parent(MAX_TABLES), 
       m_ancestors(), 
+      m_fanout(1.0),
+      m_child_fanout(1.0),
       m_op(NULL) 
     {}
 
@@ -317,6 +319,16 @@ private:
      */
     ndb_table_access_map m_ancestors;
 
+    /**
+     * The fanout of this table.
+     */
+    double m_fanout;
+
+    /**
+     * The (cross) product of all child fanouts.
+     */
+    double m_child_fanout;
+
     const NdbQueryOperationDef* m_op;
   } m_tables[MAX_TABLES];
 

No bundle (reason: useless for push emails).
Thread
bzr push into mysql-5.1-telco-7.0-spj-scan-vs-scan branch(ole.john.aske:3565 to 3566) Ole John Aske29 Sep