Fix for Bug#14503142 PERFORMANCE REGRESSION FOR DESCENDING RANGE SCAN WHEN

Olav Sandstaa · Olav Sandstaa · commit da1d92fd4607 · 2012-08-30T10:05:31.000+02:00
USING ICP

The performance regression is caused by use of ICP in combination with
a descending range scan that is using QUICK_SELECT_DESC. The
QUICK_SELECT_DESC object executes the range scan by reading the index
using ha_index_prev() and then evaluating if the record is within the
current range. This works fine when we have not pushed any index
condition to the storage engine since every record will be returned
and evaluated by QUICK_SELECT_DESC.get_next(). When ICP is used, the
call to ha_index_prev() will only return records that do not get
filtered by the pushed index condition. In this case, as soon as
QUICK_SELECT_DESC.get_next() tries to read the first record that is
outside the current range, the ICP implementation in the storage
engine will filter it away and continue reading from the index without
finding any qualifying records. It will continue reading from the
index until it has read to the end of the index. The increased
execution time is caused by the ICP implementation reading to the
end of the index instead of stopping when it has reached the end of
the current range.

This patch solves this problem by adding a new handler call
handler::set_end_range() which informs the storage engine about the
end of the current index scan. The ICP implementation in the storage
engine will use this information and check that the next record is
within this range. For each range that QUICK_SELECT_DESC.get_next()
needs to read, it will use this call to let the storage engine know
about the end of the range.
diff --git a/sql/ha_partition.cc b/sql/ha_partition.cc
@@ -5390,6 +5390,7 @@ int ha_partition::read_range_first(const key_range *start_key,
     key_compare_result_on_equal=
       ((end_key->flag == HA_READ_BEFORE_KEY) ? 1 :
        (end_key->flag == HA_READ_AFTER_KEY) ? -1 : 0);
+    range_scan_direction= RANGE_SCAN_ASC;
   }
 
   range_key_part= m_curr_key_info[0]->key_part;
diff --git a/sql/handler.cc b/sql/handler.cc
@@ -6550,6 +6550,7 @@ int handler::read_range_first(const key_range *start_key,
     save_end_range= *end_key;
     key_compare_result_on_equal= ((end_key->flag == HA_READ_BEFORE_KEY) ? 1 :
 				  (end_key->flag == HA_READ_AFTER_KEY) ? -1 : 0);
+    range_scan_direction= RANGE_SCAN_ASC;
   }
   range_key_part= table->key_info[active_index].key_part;
 
@@ -6626,6 +6627,20 @@ int handler::read_range_next()
 }
 
 
+void handler::set_end_range(const key_range* range,
+                            enum_range_scan_direction direction)
+{
+  DBUG_ASSERT(range != NULL);
+
+  save_end_range= *range;
+  end_range= &save_end_range;
+  range_key_part= table->key_info[active_index].key_part;
+  key_compare_result_on_equal= ((range->flag == HA_READ_BEFORE_KEY) ? 1 :
+                                (range->flag == HA_READ_AFTER_KEY) ? -1 : 0);
+  range_scan_direction= direction;
+}
+
+
 /**
   Compare if found key (in row) is over max-value.
 
@@ -6654,18 +6669,35 @@ int handler::compare_key(key_range *range)
 
 
 /*
-  Same as compare_key() but doesn't check have in_range_check_pushed_down.
-  This is used by index condition pushdown implementation.
+  Compare if a found key (in row) is within the range.
+
+  This function is similar to compare_key() but checks the range scan
+  direction to determine if this is a descending scan. This function
+  is used by the index condition pushdown implementation to determine
+  if the read record is within the range scan.
+
+  @param range Range to compare to row. May be NULL for no range.
+
+  @seealso
+    handler::compare_key()
+
+  @return Returns whether the key is within the range
+
+    - 0   : Key is equal to range or 'range' == 0 (no range)
+    - -1  : Key is within the current range
+    - 1   : Key is outside the current range
 */
 
-int handler::compare_key2(key_range *range)
+int handler::compare_key_icp(const key_range *range) const
 {
   int cmp;
   if (!range)
     return 0;					// no max range
   cmp= key_cmp(range_key_part, range->key, range->length);
   if (!cmp)
     cmp= key_compare_result_on_equal;
+  if (range_scan_direction == RANGE_SCAN_DESC)
+    cmp= -cmp;
   return cmp;
 }
 
diff --git a/sql/handler.h b/sql/handler.h
@@ -1778,6 +1778,20 @@ class handler :public Sql_alloc
   KEY_PART_INFO *range_key_part;
   int key_compare_result_on_equal;
   bool eq_range;
+  
+  /*
+    The direction of the current range or index scan. This is used by
+    the ICP implementation to determine if it has reached the end
+    of the current range.
+  */
+  enum enum_range_scan_direction {
+    RANGE_SCAN_ASC,
+    RANGE_SCAN_DESC
+  };
+protected:
+  enum_range_scan_direction range_scan_direction;
+
+public:
   /* 
     TRUE <=> the engine guarantees that returned records are within the range
     being scanned.
@@ -1863,7 +1877,8 @@ class handler :public Sql_alloc
   handler(handlerton *ht_arg, TABLE_SHARE *share_arg)
     :table_share(share_arg), table(0),
     estimation_rows_to_insert(0), ht(ht_arg),
-    ref(0), end_range(NULL), in_range_check_pushed_down(false),
+    ref(0), end_range(NULL), range_scan_direction(RANGE_SCAN_ASC),
+    in_range_check_pushed_down(false),
     key_used_on_scan(MAX_KEY), active_index(MAX_KEY),
     ref_length(sizeof(my_off_t)),
     ft_handler(0), inited(NONE),
@@ -2203,8 +2218,19 @@ class handler :public Sql_alloc
                                const key_range *end_key,
                                bool eq_range, bool sorted);
   virtual int read_range_next();
+
+  /**
+    Set the end position for a range scan. This is used for checking
+    for when to end the range scan and by the ICP code to determine
+    that the next record is within the current range.
+
+    @param range     The end value for the range scan
+    @param direction Direction of the range scan
+  */
+  void set_end_range(const key_range* range,
+                     enum_range_scan_direction direction);
   int compare_key(key_range *range);
-  int compare_key2(key_range *range);
+  int compare_key_icp(const key_range *range) const;
   virtual int ft_init() { return HA_ERR_WRONG_COMMAND; }
   void ft_end() { ft_handler=NULL; }
   virtual FT_INFO *ft_init_ext(uint flags, uint inx,String *key)
diff --git a/sql/opt_range.cc b/sql/opt_range.cc
@@ -10441,9 +10441,11 @@ int QUICK_SELECT_DESC::get_next()
 
   /* The max key is handled as follows:
    *   - if there is NO_MAX_RANGE, start at the end and move backwards
-   *   - if it is an EQ_RANGE, which means that max key covers the entire
-   *     key, go directly to the key and read through it (sorting backwards is
-   *     same as sorting forwards)
+   *   - if it is an EQ_RANGE (which means that max key covers the entire
+   *     key) and the query does not use any hidden key fields that are
+   *     not considered when the range optimzier sets EQ_RANGE (e.g. the 
+   *     primary key added by InnoDB), then go directly to the key and 
+   *     read through it (sorting backwards is same as sorting forwards).
    *   - if it is NEAR_MAX, go to the key or next, step back once, and
    *     move backwards
    *   - otherwise (not NEAR_MAX == include the key), go after the key,
@@ -10472,6 +10474,24 @@ int QUICK_SELECT_DESC::get_next()
     if (!(last_range= rev_it++))
       DBUG_RETURN(HA_ERR_END_OF_FILE);		// All ranges used
 
+    // Case where we can avoid descending scan, see comment above
+    const bool eqrange_all_keyparts= (last_range->flag & EQ_RANGE) && 
+                          (used_key_parts <= head->key_info[index].key_parts);
+
+    /*
+      If we have pushed an index condition (ICP) and this quick select
+      will use ha_index_prev() to read data, we need to let the
+      handler know where to end the scan in order to avoid that the
+      ICP implemention continues to read past the range boundary.
+    */
+    if (file->pushed_idx_cond && !eqrange_all_keyparts)
+    {
+      key_range min_range;
+      last_range->make_min_endpoint(&min_range);
+      if(min_range.length > 0)
+        file->set_end_range(&min_range, handler::RANGE_SCAN_DESC);
+    }
+
     if (last_range->flag & NO_MAX_RANGE)        // Read last record
     {
       int local_error;
@@ -10483,8 +10503,7 @@ int QUICK_SELECT_DESC::get_next()
       continue;
     }
 
-    if (last_range->flag & EQ_RANGE &&
-        used_key_parts <= head->key_info[index].key_parts)
+    if (eqrange_all_keyparts)
 
     {
       result= file->ha_index_read_map(record, last_range->max_key,
diff --git a/storage/innobase/handler/ha_innodb.cc b/storage/innobase/handler/ha_innodb.cc
@@ -16332,7 +16332,7 @@ innobase_index_cond(
 	DBUG_ASSERT(h->pushed_idx_cond);
 	DBUG_ASSERT(h->pushed_idx_cond_keyno != MAX_KEY);
 
-	if (h->end_range && h->compare_key2(h->end_range) > 0) {
+	if (h->end_range && h->compare_key_icp(h->end_range) > 0) {
 
 		/* caller should return HA_ERR_END_OF_FILE already */
 		DBUG_RETURN(ICP_OUT_OF_RANGE);
diff --git a/storage/myisam/ha_myisam.cc b/storage/myisam/ha_myisam.cc
@@ -1605,11 +1605,10 @@ C_MODE_START
 ICP_RESULT index_cond_func_myisam(void *arg)
 {
   ha_myisam *h= (ha_myisam*)arg;
-  if (h->end_range)
-  {
-    if (h->compare_key2(h->end_range) > 0)
-      return ICP_OUT_OF_RANGE; /* caller should return HA_ERR_END_OF_FILE already */
-  }
+
+  if (h->end_range && h->compare_key_icp(h->end_range) > 0)
+    return ICP_OUT_OF_RANGE; /* caller should return HA_ERR_END_OF_FILE already */
+
   return (ICP_RESULT) test(h->pushed_idx_cond->val_int());
 }
 

Original file line number	Diff line number	Diff line change
`@@ -5390,6 +5390,7 @@ int ha_partition::read_range_first(const key_range *start_key,`
`5390`	`5390`	`key_compare_result_on_equal=`
`5391`	`5391`	`((end_key->flag == HA_READ_BEFORE_KEY) ? 1 :`
`5392`	`5392`	`(end_key->flag == HA_READ_AFTER_KEY) ? -1 : 0);`
	`5393`	`+ range_scan_direction= RANGE_SCAN_ASC;`
`5393`	`5394`	`}`
`5394`	`5395`
`5395`	`5396`	`range_key_part= m_curr_key_info[0]->key_part;`