[Commits] Rev 3382: Applied the patch from the code line of mysql-5.6 to maintain the order of best_ref[]. in file:///home/igor/maria/maria-5.3-trunk/

igor at askmonty.org igor at askmonty.org
Tue Jan 31 04:36:29 EET 2012


At file:///home/igor/maria/maria-5.3-trunk/

------------------------------------------------------------
revno: 3382
revision-id: igor at askmonty.org-20120131023545-i7q8bnoalyylu04j
parent: sanja at montyprogram.com-20120111083516-fei2c3fzara3n152
committer: Igor Babaev <igor at askmonty.org>
branch nick: maria-5.3-trunk
timestamp: Mon 2012-01-30 18:35:45 -0800
message:
  Applied the patch from the code line of mysql-5.6 to maintain the order of best_ref[].
  
  Here are the comments from mysql-5.6 tree for this patch:
  
  In order for the greedy optimizers 'prune' logic to quickly find a
  'good' execution plan, and prune the other less promising plans, best_ref[]
  is sorted by E(#rows) before we start calculating query plans.
  
  However, due to how swap_variables() was used inside
  best_extension_by_limited_search(), best_ref[] quickly
  became 'scrambled', and was no longer sorted when
  multiple partial plans had been evaluated.
  
  This patch maintains the order of the unevaluated part of
  best_ref[]. Besides reducing time to find the 'best' query plan,
  this also reduces the risk for incorrectly pruning away the optimal 
  query plan.
-------------- next part --------------
=== modified file 'sql/sql_select.cc'
--- a/sql/sql_select.cc	2012-01-11 08:35:16 +0000
+++ b/sql/sql_select.cc	2012-01-31 02:35:45 +0000
@@ -6063,8 +6063,14 @@
     while (pos && best_table != pos)
       pos= join->best_ref[++best_idx];
     DBUG_ASSERT((pos != NULL)); // should always find 'best_table'
-    /* move 'best_table' at the first free position in the array of joins */
-    swap_variables(JOIN_TAB*, join->best_ref[idx], join->best_ref[best_idx]);
+    /*
+      Maintain '#rows-sorted' order of 'best_ref[]':
+       - Shift 'best_ref[]' to make first position free. 
+       - Insert 'best_table' at the first free position in the array of joins.
+    */
+    memmove(join->best_ref + idx + 1, join->best_ref + idx,
+            sizeof(JOIN_TAB*) * (best_idx - idx));
+    join->best_ref[idx]= best_table;
 
     /* compute the cost of the new plan extended with 'best_table' */
     record_count*= join->positions[idx].records_read;
@@ -6382,8 +6388,20 @@
   if (join->emb_sjm_nest)
     allowed_tables= join->emb_sjm_nest->sj_inner_tables & ~join->const_table_map;
 
+  JOIN_TAB *saved_refs[MAX_TABLES];
+  /* Save 'best_ref[]' as we has to restore before return. */
+  memcpy(saved_refs, join->best_ref + idx, 
+         sizeof(JOIN_TAB*) * (join->table_count - idx));
+
   for (JOIN_TAB **pos= join->best_ref + idx ; (s= *pos) ; pos++)
   {
+    /*
+      Don't move swap inside conditional code: All items should
+      be uncond. swapped to maintain '#rows-ordered' best_ref[].
+      This is critical for early pruning of bad plans.
+    */
+    swap_variables(JOIN_TAB*, join->best_ref[idx], *pos);
+
     table_map real_table_bit= s->table->map;
     if ((remaining_tables & real_table_bit) && 
         (allowed_tables & real_table_bit) &&
@@ -6455,8 +6473,8 @@
       }
 
       if ( (search_depth > 1) && (remaining_tables & ~real_table_bit) & allowed_tables )
-      { /* Recursively expand the current partial plan */
-        swap_variables(JOIN_TAB*, join->best_ref[idx], *pos);
+      {
+        /* Explore more best extensions of plan */
         if (best_extension_by_limited_search(join,
                                              remaining_tables & ~real_table_bit,
                                              idx + 1,
@@ -6465,7 +6483,6 @@
                                              search_depth - 1,
                                              prune_level))
           DBUG_RETURN(TRUE);
-        swap_variables(JOIN_TAB*, join->best_ref[idx], *pos);
       }
       else
       { /*
@@ -6494,6 +6511,10 @@
       restore_prev_sj_state(remaining_tables, s, idx);
     }
   }
+
+  /* Restore previous #rows sorted best_ref[] */
+  memcpy(join->best_ref + idx, saved_refs,
+         sizeof(JOIN_TAB*) * (join->table_count-idx));
   DBUG_RETURN(FALSE);
 }
 



More information about the commits mailing list