List:Commits« Previous MessageNext Message »
From:Roy Lyseng Date:April 14 2011 11:57am
Subject:bzr push into mysql-trunk branch (roy.lyseng:3362 to 3363) Bug#11822517
View as plain text  
 3363 Roy Lyseng	2011-04-14
      Bug#11822517: Refactor call interface of choose_plan()
      Part 2 - Change meaning of greedy_search() argument 'remaining_tables'.
      The purpose of this patch is to make the interface of greedy_search()
      and related functions simpler.
      It is also a preparatory step for a simpler test for dependencies when
      doing semi-join materialization together with outer join (WL#5561).
      The meaning of the argument remaining_tables to greedy_search() is changed:
      Before this patch, it meant all tables not yet added to the current
      join plan, regardless of whether the tables were to be optimized or not.
      After the patch, it means all tables remaining to be added, but not
      including tables that will not be optimized.
      The difference is important when making a plan for a materialized
      semi-join nest. Before, remaining_tables included also the tables
      belonging to the query, but not part of the semi-join nest being
      optimized. This makes for simpler implementation of
      best_extension_by_limited_search() and easier maintenance.
      However, best_access_path() requires that information about all tables
      not yet added to the plan be available. We implement this by adding
      a member variable excluded_tables in the Optimize_table_order class,
      which contains the set of all tables in the query block that are not
      to be optimized in the current operation. Notice that excluded_tables
      is passed to best_access_path() only where it can be non-empty.
        New member variable excluded_tables is added to Optimize_table_order.
        In choose_table_order(), join_tables is calculated as the set of
        tables to be optimized.
        In best_extension_by_limited_search(), use of allowed_tables is
        eliminated, and logic has been slightly simplified.

 3362 Roy Lyseng	2011-04-14
      Bug#11822517: Refactor call interface of choose_plan()
      Part 1 - create class Optimize_table_order.
      This patch creates a class that is used to optimize the join order of
      tables in a query. The main purpose of the refactoring is to simplify
      function interfaces and to encapsulate information needed to perform
      optimization in a dedicated class.
      The following existing functions are added to the class:
        choose_table_order() - renamed from choose_plan()
        New class definition, see above for details.
        make_join_statistics() is now taking full responsibility for error
        checking, so there is longer need for testing is_fatal_error() after
        calling this function.
        Added all_table_map (map of tables in query) to JOIN class.
        cur_embedding_map has been moved to class Optimize_table_order.
        Commented const_table_map, found_const_table_map and outer_join.

=== modified file 'sql/'
--- a/sql/	2011-04-14 10:56:57 +0000
+++ b/sql/	2011-04-14 11:54:52 +0000
@@ -284,7 +284,10 @@ public:
                                         join->tables - join->const_tables)),
     thd(thd), join(join),
-    cur_embedding_map(0)
+    cur_embedding_map(0),
+    excluded_tables(sjm_nest ?
+                    join->all_table_map & ~sjm_nest->sj_inner_tables :
+                    0)
     this->join->emb_sjm_nest= sjm_nest;
@@ -312,6 +315,15 @@ private:
   nested_join_map cur_embedding_map;
+    When calculating a plan for a materialized semi-join nest,
+    best_access_plan() needs to know not only the remaining tables within the
+    semi-join nest, but also all tables outside of this nest, because there may
+    be key references between the semi-join nest and the outside tables
+    that should not be considered when materializing the semi-join nest.
+    @c excluded_tables tracks these tables.
+  */
+  const table_map excluded_tables;
+  /**
     @todo: Add remaining Join optimization state members here,
     ie emb_sjm_nest, positions, cur_sj_inner_tables.
     This is not yet possible because (some of them) are accessed through
@@ -7017,6 +7029,12 @@ public:
   semijoin nest and those outside of it. The way to control this is to add
   the set of outside tables to the @c remaining_tables argument.
+  @todo: Add this function to class Optimize_table_order. When this is done,
+  best_access_path() will have access to the excluded_tables member, and
+  there will no longer be a need to pass that set of tables as part of
+  remaining_tables. Notice also that excluded_tables can be non-empty only
+  at those places where it is actually passed as argument.
   @param join             pointer to the structure providing all context info
                           for the query
   @param s                the table to be joined by the function
@@ -7032,9 +7050,6 @@ public:
   @param[out] pos         Table access plan
   @param[out] loose_scan_pos  Table plan that uses loosescan, or set cost to 
                               DBL_MAX if not possible.
-  @return
-    None
 static void
@@ -7653,7 +7668,7 @@ bool Optimize_table_order::choose_table_
        tables from this semi-join as first
     jtab_sort_func= join_tab_cmp_embedded_first;
-    join_tables= join->all_table_map & ~join->const_table_map;
+    join_tables= join->emb_sjm_nest->sj_inner_tables;
@@ -7888,7 +7903,8 @@ void Optimize_table_order::optimize_stra
     /* Find the best access method from 's' to the current partial plan */
     POSITION  loose_scan_pos;
-    best_access_path(join, s, join_tables, idx, FALSE, record_count,
+    best_access_path(join, s, excluded_tables | join_tables,
+                     idx, FALSE, record_count,
                      join->positions + idx, &loose_scan_pos);
     /* compute the cost of the new plan extended with 's' */
@@ -8079,10 +8095,7 @@ bool Optimize_table_order::greedy_search
   /* Number of tables that we are optimizing */
-  const uint n_tables= my_count_bits(remaining_tables &
-                                     (join->emb_sjm_nest? 
-                                       join->emb_sjm_nest->sj_inner_tables :
-                                       ~(table_map)0));
+  const uint n_tables= my_count_bits(remaining_tables);
   /* Number of tables remaining to be optimized */
   uint size_remain= n_tables;
@@ -8334,10 +8347,6 @@ bool Optimize_table_order::best_extensio
   DBUG_EXECUTE("opt", print_plan(join, idx, record_count, read_time, read_time,
-  table_map allowed_tables= ~(table_map)0;
-  if (join->emb_sjm_nest)
-    allowed_tables= join->emb_sjm_nest->sj_inner_tables;
     No need to call advance_sj_state() when
      1) there are no semijoin nests or
@@ -8364,7 +8373,6 @@ bool Optimize_table_order::best_extensio
     swap_variables(JOIN_TAB*, join->best_ref[idx], *pos);
     if ((remaining_tables & real_table_bit) && 
-        (allowed_tables & real_table_bit) &&
         !(remaining_tables & s->dependent) && 
         (!idx || !check_interleaving_with_nj(s)))
@@ -8373,7 +8381,7 @@ bool Optimize_table_order::best_extensio
       /* Find the best access method from 's' to the current partial plan */
       POSITION loose_scan_pos;
-      best_access_path(join, s, remaining_tables,
+      best_access_path(join, s, excluded_tables | remaining_tables,
                        idx, false, record_count, 
                        position, &loose_scan_pos);
@@ -8445,8 +8453,7 @@ bool Optimize_table_order::best_extensio
-      if ((current_search_depth > 1) &&
-          (remaining_tables & ~real_table_bit) & allowed_tables )
+      if ((current_search_depth > 1) && (remaining_tables & ~real_table_bit))
         /* Explore more best extensions of plan */
         if (best_extension_by_limited_search(remaining_tables & ~real_table_bit,

No bundle (reason: useless for push emails).
bzr push into mysql-trunk branch (roy.lyseng:3362 to 3363) Bug#11822517Roy Lyseng14 Apr