List:Commits« Previous MessageNext Message »
From:Jorgen Loland Date:March 28 2011 8:45am
Subject:bzr commit into mysql-5.5 branch (jorgen.loland:3404) Bug#11882131
View as plain text  
#At file:///export/home/jl208045/mysql/mysql-5.5-11882131/ based on revid:alfranio.correia@stripped

 3404 Jorgen Loland	2011-03-28
      BUG#11882131: OPTIMIZER CHOOSES FILESORT WHEN REVERSE 
                    INDEX SCAN COULD BE USED
      
      Consider the following case:
      
      CREATE TABLE t1 (a INT,KEY (a));
      INSERT INTO t1 VALUES (1),(2),(3),(4),(5),(6),(7),(8),(9),(10);
      SELECT DISTINCT a,1 FROM t1 WHERE a <> 1 ORDER BY a DESC;
      
      This query could have been resolved by GROUP range access
      if it hadn't been for the descending ordering [1]. 
      
      To access this table, covering index scan is first chosen. 
      Later an attempt to avoid sorting is made by calling 
      test_if_skip_sort_order(). Range analysis now decides that
      GROUP range access is the most efficient access method, but
      since this access method cannot produce records in 
      descending order, it is scrapped by 
      test_if_skip_sort_order() before concluding that filesort 
      is required after all. 
      
      In this case, test_if_skip_sort_order() fails to check if 
      the descending ordering can be resolved by scanning the 
      covering index in reverse order instead. Because of this, 
      the resulting execution plan is to 1) scan the index and 2) 
      sort the result instead of simply do 1) scan the index in 
      reverse order.
      
      This patch adds an interesting_order parameter to 
      test_quick_select(). This parameter is ensure that only range 
      access plans that can produce rows in requested order are 
      considered.
      
      The gains from this change include:
       1) Optimizer will not spend time to calculate whether or not
          an unusable range access plan is cheap.
       2) Before, if two range access plans P1 and P2 were considered, 
          and P1 could produce the requested ordering but P2 could not,
          P2 would still be returned from test_quick_select() if it was
          cheaper than P1. test_if_skip_sort_order() would then discard
          the range access plan as not usable. With this patch, P2 will
          not be considered, so test_quick_select() will instead return
          the best *usable* plan P1.
       3) Due to #2, the aforementioned deficiency in 
          test_if_skip_sort_order() is no longer an issue: If 
          test_quick_select() returns a range access plan, that plan 
          will be able to resolve the requested ordering.
     @ mysql-test/r/order_by.result
        BUG#11882131: Changed test output
     @ sql/item_sum.cc
        Struct ORDER variable "bool asc" replaced with "enum_order order"
     @ sql/opt_range.cc
        Add parameter "interesting_order" to test_quick_select() and make the method only consider
        range access plans that are able to produce rows in requested order. Also add variable
        PARAM::order, defining whether the range access plan needs to produce ASC/DESC ordering
        (or no order)
     @ sql/opt_range.h
        Add method QUICK_SELECT_I::reverse_sort_possible().
     @ sql/sql_lex.cc
        Struct ORDER variable "bool asc" replaced with "enum_order order"
     @ sql/sql_parse.cc
        Struct ORDER variable "bool asc" replaced with "enum_order order"
     @ sql/sql_select.cc
        When calling test_quick_select(): define whether ascending/descending ordering will be 
        required.
     @ sql/sql_update.cc
        Struct ORDER variable "bool asc" replaced with "enum_order order"
     @ sql/table.h
        Struct ORDER variable "bool asc" replaced with "enum_order order"

    modified:
      mysql-test/r/order_by.result
      sql/item_sum.cc
      sql/opt_range.cc
      sql/opt_range.h
      sql/sql_lex.cc
      sql/sql_parse.cc
      sql/sql_select.cc
      sql/sql_update.cc
      sql/table.h
=== modified file 'mysql-test/r/order_by.result'
--- a/mysql-test/r/order_by.result	2011-02-07 09:40:42 +0000
+++ b/mysql-test/r/order_by.result	2011-03-28 08:45:06 +0000
@@ -1651,7 +1651,7 @@ CREATE TABLE t1 (a INT,KEY (a));
 INSERT INTO t1 VALUES (1),(2),(3),(4),(5),(6),(7),(8),(9),(10);
 EXPLAIN SELECT DISTINCT a,1 FROM t1 WHERE a <> 1 ORDER BY a DESC;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
-1	SIMPLE	t1	index	a	a	5	NULL	10	Using where; Using index; Using filesort
+1	SIMPLE	t1	index	a	a	5	NULL	10	Using where; Using index
 SELECT DISTINCT a,1 FROM t1 WHERE a <> 1 ORDER BY a DESC;
 a	1
 10	1

=== modified file 'sql/item_sum.cc'
--- a/sql/item_sum.cc	2011-03-16 14:11:20 +0000
+++ b/sql/item_sum.cc	2011-03-28 08:45:06 +0000
@@ -2894,7 +2894,7 @@ int group_concat_key_cmp_with_order(void
       uint offset= (field->offset(field->table->record[0]) -
                     table->s->null_bytes);
       if ((res= field->cmp((uchar*)key1 + offset, (uchar*)key2 + offset)))
-        return (*order_item)->asc ? res : -res;
+        return ((*order_item)->order == ORDER::ORDER_ASC) ? res : -res;
     }
   }
   /*
@@ -3435,7 +3435,7 @@ void Item_func_group_concat::print(Strin
       if (i)
         str->append(',');
       orig_args[i + arg_count_field]->print(str, query_type);
-      if (order[i]->asc)
+      if (order[i]->order == ORDER::ORDER_ASC)
         str->append(STRING_WITH_LEN(" ASC"));
       else
         str->append(STRING_WITH_LEN(" DESC"));

=== modified file 'sql/opt_range.cc'
--- a/sql/opt_range.cc	2010-12-29 00:26:31 +0000
+++ b/sql/opt_range.cc	2011-03-28 08:45:06 +0000
@@ -695,6 +695,8 @@ public:
   /* Number of ranges in the last checked tree->key */
   uint n_ranges;
   uint8 first_null_comp; /* first null component if any, 0 - otherwise */
+
+  ORDER::enum_order order;
 };
 
 class TABLE_READ_PLAN;
@@ -2147,8 +2149,9 @@ static int fill_used_fields_bitmap(PARAM
 */
 
 int SQL_SELECT::test_quick_select(THD *thd, key_map keys_to_use,
-				  table_map prev_tables,
-				  ha_rows limit, bool force_quick_range)
+                                  table_map prev_tables,
+                                  ha_rows limit, bool force_quick_range,
+                                  const ORDER::enum_order &interesting_order)
 {
   uint idx;
   double scan_time;
@@ -2204,6 +2207,7 @@ int SQL_SELECT::test_quick_select(THD *t
     param.imerge_cost_buff_size= 0;
     param.using_real_indexes= TRUE;
     param.remove_jump_scans= TRUE;
+    param.order= interesting_order;
 
     thd->no_errors=1;				// Don't warn about NULL
     init_sql_alloc(&alloc, thd->variables.range_alloc_block_size, 0);
@@ -2328,10 +2332,12 @@ int SQL_SELECT::test_quick_select(THD *t
         /*
           Simultaneous key scans and row deletes on several handler
           objects are not allowed so don't use ROR-intersection for
-          table deletes.
+          table deletes.Also, ROR-intersection cannot return rows in
+          descending order
         */
         if ((thd->lex->sql_command != SQLCOM_DELETE) && 
-             optimizer_flag(thd, OPTIMIZER_SWITCH_INDEX_MERGE))
+            optimizer_flag(thd, OPTIMIZER_SWITCH_INDEX_MERGE) &&
+            interesting_order != ORDER::ORDER_DESC)
         {
           /*
             Get best non-covering ROR-intersection plan and prepare data for
@@ -2355,7 +2361,9 @@ int SQL_SELECT::test_quick_select(THD *t
       }
       else
       {
-        if (optimizer_flag(thd, OPTIMIZER_SWITCH_INDEX_MERGE))
+        // Cannot return rows in descending order.
+        if (optimizer_flag(thd, OPTIMIZER_SWITCH_INDEX_MERGE) &&
+            interesting_order != ORDER::ORDER_DESC)
         {
           /* Try creating index_merge/ROR-union scan. */
           SEL_IMERGE *imerge;
@@ -4605,6 +4613,9 @@ TRP_ROR_INTERSECT *get_best_ror_intersec
       !optimizer_flag(param->thd, OPTIMIZER_SWITCH_INDEX_MERGE_INTERSECT))
     DBUG_RETURN(NULL);
 
+  if (param->order == ORDER::ORDER_DESC)
+    DBUG_RETURN(NULL);
+
   /*
     Step1: Collect ROR-able SEL_ARGs and create ROR_SCAN_INFO for each of 
     them. Also find and save clustered PK scan if there is one.
@@ -9434,6 +9445,8 @@ get_best_group_min_max(PARAM *param, SEL
     DBUG_RETURN(NULL);
   if (table->s->keys == 0)        /* There are no indexes to use. */
     DBUG_RETURN(NULL);
+  if (param->order == ORDER::ORDER_DESC)  /* Cannot do reverse ordering */
+    DBUG_RETURN(NULL);
 
   /* Check (SA1,SA4) and store the only MIN/MAX argument - the C attribute.*/
   if (join->make_sum_func_list(join->all_fields, join->fields_list, 1))

=== modified file 'sql/opt_range.h'
--- a/sql/opt_range.h	2010-12-17 12:52:39 +0000
+++ b/sql/opt_range.h	2011-03-28 08:45:06 +0000
@@ -278,6 +278,7 @@ public:
   virtual void range_end() {}
 
   virtual bool reverse_sorted() = 0;
+  virtual bool reverse_sort_possible() = 0;
   virtual bool unique_key_range() { return false; }
   virtual bool clustered_pk_range() { return false; }
 
@@ -439,7 +440,8 @@ public:
   void range_end();
   int get_next_prefix(uint prefix_length, uint group_key_parts, 
                       uchar *cur_prefix);
-  bool reverse_sorted() { return 0; }
+  bool reverse_sorted() { return false; }
+  bool reverse_sort_possible() { return true; }
   bool unique_key_range();
   int init_ror_merged_scan(bool reuse_handler);
   void save_last_pos()
@@ -537,6 +539,7 @@ public:
   int  reset(void);
   int  get_next();
   bool reverse_sorted() { return false; }
+  bool reverse_sort_possible() { return false; }
   bool unique_key_range() { return false; }
   int get_type() { return QS_TYPE_INDEX_MERGE; }
   void add_keys_and_lengths(String *key_names, String *used_lengths);
@@ -614,6 +617,7 @@ public:
   int  reset(void);
   int  get_next();
   bool reverse_sorted() { return false; }
+  bool reverse_sort_possible() { return false; }
   bool unique_key_range() { return false; }
   int get_type() { return QS_TYPE_ROR_INTERSECT; }
   void add_keys_and_lengths(String *key_names, String *used_lengths);
@@ -684,6 +688,7 @@ public:
   int  reset(void);
   int  get_next();
   bool reverse_sorted() { return false; }
+  bool reverse_sort_possible() { return false; }
   bool unique_key_range() { return false; }
   int get_type() { return QS_TYPE_ROR_UNION; }
   void add_keys_and_lengths(String *key_names, String *used_lengths);
@@ -825,6 +830,7 @@ public:
   int reset();
   int get_next();
   bool reverse_sorted() { return false; }
+  bool reverse_sort_possible() { return false; }
   bool unique_key_range() { return false; }
   int get_type() { return QS_TYPE_GROUP_MIN_MAX; }
   void add_keys_and_lengths(String *key_names, String *used_lengths);
@@ -845,7 +851,8 @@ class QUICK_SELECT_DESC: public QUICK_RA
 public:
   QUICK_SELECT_DESC(QUICK_RANGE_SELECT *q, uint used_key_parts);
   int get_next();
-  bool reverse_sorted() { return 1; }
+  bool reverse_sorted() { return true; }
+  bool reverse_sort_possible() { return true; }
   int get_type() { return QS_TYPE_RANGE_DESC; }
   QUICK_SELECT_I *make_reverse(uint used_key_parts_arg)
   {
@@ -881,7 +888,8 @@ class SQL_SELECT :public Sql_alloc {
   {
     key_map tmp;
     tmp.set_all();
-    return test_quick_select(thd, tmp, 0, limit, force_quick_range) < 0;
+    return test_quick_select(thd, tmp, 0, limit, force_quick_range,
+                             ORDER::ORDER_NOT_RELEVANT) < 0;
   }
   inline bool skip_record(THD *thd, bool *skip_record)
   {
@@ -889,7 +897,8 @@ class SQL_SELECT :public Sql_alloc {
     return thd->is_error();
   }
   int test_quick_select(THD *thd, key_map keys, table_map prev_tables,
-			ha_rows limit, bool force_quick_range);
+                        ha_rows limit, bool force_quick_range,
+                        const ORDER::enum_order &interesting_order);
 };
 
 

=== modified file 'sql/sql_lex.cc'
--- a/sql/sql_lex.cc	2011-03-08 17:39:25 +0000
+++ b/sql/sql_lex.cc	2011-03-28 08:45:06 +0000
@@ -2178,7 +2178,7 @@ void st_select_lex::print_order(String *
     }
     else
       (*order->item)->print(str, query_type);
-    if (!order->asc)
+    if (order->order == ORDER::ORDER_DESC)
       str->append(STRING_WITH_LEN(" desc"));
     if (order->next)
       str->append(',');

=== modified file 'sql/sql_parse.cc'
--- a/sql/sql_parse.cc	2011-03-08 17:39:25 +0000
+++ b/sql/sql_parse.cc	2011-03-28 08:45:06 +0000
@@ -5688,7 +5688,7 @@ bool add_to_list(THD *thd, SQL_I_List<OR
     DBUG_RETURN(1);
   order->item_ptr= item;
   order->item= &order->item_ptr;
-  order->asc = asc;
+  order->order = asc ? ORDER::ORDER_ASC : ORDER::ORDER_DESC;
   order->free_me=0;
   order->used=0;
   order->counter_used= 0;

=== modified file 'sql/sql_select.cc'
--- a/sql/sql_select.cc	2011-03-16 14:11:20 +0000
+++ b/sql/sql_select.cc	2011-03-28 08:45:06 +0000
@@ -2607,8 +2607,9 @@ static ha_rows get_quick_record_count(TH
   if (select)
   {
     select->head=table;
-    if ((error= select->test_quick_select(thd, *(key_map *)keys,(table_map) 0,
-                                          limit, 0)) == 1)
+    error= select->test_quick_select(thd, *(key_map *)keys,(table_map) 0,
+                                     limit, 0, ORDER::ORDER_NOT_RELEVANT);
+    if (error == 1)
       DBUG_RETURN(select->quick->records);
     if (error == -1)
     {
@@ -6580,12 +6581,13 @@ make_join_select(JOIN *join,SQL_SELECT *
 	    if (sel->cond && !sel->cond->fixed)
 	      sel->cond->quick_fix_field();
 
-	    if (sel->test_quick_select(thd, tab->keys,
-				       used_tables & ~ current_map,
-				       (join->select_options &
-					OPTION_FOUND_ROWS ?
-					HA_POS_ERROR :
-					join->unit->select_limit_cnt), 0) < 0)
+            if (sel->test_quick_select(thd, tab->keys,
+                                       used_tables & ~ current_map,
+                                       (join->select_options &
+                                        OPTION_FOUND_ROWS ?
+                                        HA_POS_ERROR :
+                                        join->unit->select_limit_cnt),
+                                       0, ORDER::ORDER_NOT_RELEVANT) < 0)
             {
 	      /*
 		Before reporting "Impossible WHERE" for the whole query
@@ -6598,7 +6600,9 @@ make_join_select(JOIN *join,SQL_SELECT *
                                          (join->select_options &
                                           OPTION_FOUND_ROWS ?
                                           HA_POS_ERROR :
-                                          join->unit->select_limit_cnt),0) < 0)
+                                          join->unit->select_limit_cnt),
+                                         0, ORDER::ORDER_NOT_RELEVANT)
+                  < 0)
 		DBUG_RETURN(1);			// Impossible WHERE
             }
             else
@@ -12436,7 +12440,8 @@ test_if_quick_select(JOIN_TAB *tab)
   delete tab->select->quick;
   tab->select->quick=0;
   return tab->select->test_quick_select(tab->join->thd, tab->keys,
-					(table_map) 0, HA_POS_ERROR, 0);
+                                        (table_map) 0, HA_POS_ERROR, 0,
+                                        ORDER::ORDER_NOT_RELEVANT);
 }
 
 
@@ -13298,7 +13303,8 @@ static int test_if_order_by_key(ORDER *o
       DBUG_RETURN(0);
 
     /* set flag to 1 if we can use read-next on key, else to -1 */
-    flag= ((order->asc == !(key_part->key_part_flag & HA_REVERSE_SORT)) ?
+    bool asc_order= (order->order == ORDER::ORDER_ASC);
+    flag= ((asc_order == !(key_part->key_part_flag & HA_REVERSE_SORT)) ?
            1 : -1);
     if (reverse && flag != reverse)
       DBUG_RETURN(0);
@@ -13739,8 +13745,8 @@ test_if_skip_sort_order(JOIN_TAB *tab,OR
                                         (tab->join->select_options &
                                          OPTION_FOUND_ROWS) ?
                                         HA_POS_ERROR :
-                                        tab->join->unit->select_limit_cnt,0) <=
-              0)
+                                        tab->join->unit->select_limit_cnt, 0,
+                                        order->order) <= 0)
             goto use_filesort;
 	}
         ref_key= new_ref_key;
@@ -13789,7 +13795,7 @@ test_if_skip_sort_order(JOIN_TAB *tab,OR
                                   join->select_options & OPTION_FOUND_ROWS ?
                                   HA_POS_ERROR :
                                   join->unit->select_limit_cnt,
-                                  0);
+                                  0, order->order);
       }
       order_direction= best_key_direction;
       /*
@@ -13818,18 +13824,13 @@ check_reverse_order:                  
       */
       if (select->quick->reverse_sorted())
         goto skipped_filesort;
-      else
-      {
-        int quick_type= select->quick->get_type();
-        if (quick_type == QUICK_SELECT_I::QS_TYPE_INDEX_MERGE ||
-            quick_type == QUICK_SELECT_I::QS_TYPE_ROR_INTERSECT ||
-            quick_type == QUICK_SELECT_I::QS_TYPE_ROR_UNION ||
-            quick_type == QUICK_SELECT_I::QS_TYPE_GROUP_MIN_MAX)
-        {
-          tab->limit= 0;
-          goto use_filesort;               // Use filesort
-        }
-      }
+
+      bool quick_created= (select->quick != save_quick);
+      /*
+        test_quick_select() should not create a quick that cannot do
+        reverse ordering
+      */
+      DBUG_ASSERT(!quick_created || select->quick->reverse_sort_possible());
     }
   }
 
@@ -13929,7 +13930,7 @@ check_reverse_order:                  
   /*
     Cleanup:
     We may have both a 'select->quick' and 'save_quick' (original)
-    at this point. Delete the one that we wan't use.
+    at this point. Delete the one that we won't use.
   */
 
 skipped_filesort:
@@ -14425,7 +14426,7 @@ SORT_FIELD *make_unireg_sortorder(ORDER 
     }
     else
       pos->item= *order->item;
-    pos->reverse=! order->asc;
+    pos->reverse= (order->order == ORDER::ORDER_DESC);
   }
   *length=count;
   DBUG_RETURN(sort);
@@ -15162,7 +15163,7 @@ create_distinct_group(THD *thd, Item **r
         */
         ord->item= ref_pointer_array;
       }
-      ord->asc=1;
+      ord->order= ORDER::ORDER_ASC;
       *prev=ord;
       prev= &ord->next;
     }
@@ -15239,7 +15240,7 @@ test_if_subpart(ORDER *a,ORDER *b)
   for (; a && b; a=a->next,b=b->next)
   {
     if ((*a->item)->eq(*b->item,1))
-      a->asc=b->asc;
+      a->order= b->order;
     else
       return 0;
   }

=== modified file 'sql/sql_update.cc'
--- a/sql/sql_update.cc	2011-02-21 15:49:03 +0000
+++ b/sql/sql_update.cc	2011-03-28 08:45:06 +0000
@@ -1731,7 +1731,7 @@ loop_end:
 
     /* Make an unique key over the first field to avoid duplicated updates */
     bzero((char*) &group, sizeof(group));
-    group.asc= 1;
+    group.order= ORDER::ORDER_ASC;
     group.item= (Item**) temp_fields.head_ref();
 
     tmp_param->quick_group=1;

=== modified file 'sql/table.h'
--- a/sql/table.h	2011-03-25 09:06:07 +0000
+++ b/sql/table.h	2011-03-28 08:45:06 +0000
@@ -194,7 +194,13 @@ typedef struct st_order {
   Item	 *item_ptr;			/* Storage for initial item */
   int    counter;                       /* position in SELECT list, correct
                                            only if counter_used is true*/
-  bool	 asc;				/* true if ascending */
+  enum enum_order {
+    ORDER_NOT_RELEVANT,
+    ORDER_ASC,
+    ORDER_DESC
+  };
+
+  enum_order order;                     /* Requested direction of ordering */
   bool	 free_me;			/* true if item isn't shared  */
   bool	 in_field_list;			/* true if in select field list */
   bool   counter_used;                  /* parameter was counter of columns */


Attachment: [text/bzr-bundle] bzr/jorgen.loland@oracle.com-20110328084506-64iqa40zsmr5ea7m.bundle
Thread
bzr commit into mysql-5.5 branch (jorgen.loland:3404) Bug#11882131Jorgen Loland28 Mar
  • Re: bzr commit into mysql-5.5 branch (jorgen.loland:3404) Bug#11882131Tor Didriksen28 Mar
    • Re: bzr commit into mysql-5.5 branch (jorgen.loland:3404) Bug#11882131Olav Sandstaa1 Apr
    • Re: bzr commit into mysql-5.5 branch (jorgen.loland:3404) Bug#11882131Jorgen Loland1 Apr
  • Re: bzr commit into mysql-5.5 branch (jorgen.loland:3404) Bug#11882131Olav Sandstaa1 Apr
    • Re: bzr commit into mysql-5.5 branch (jorgen.loland:3404) Bug#11882131Jorgen Loland1 Apr
      • Re: bzr commit into mysql-5.5 branch (jorgen.loland:3404) Bug#11882131Olav Sandstaa1 Apr