List:Commits« Previous MessageNext Message »
From:Sergey Petrunia Date:January 4 2006 8:09am
Subject:bk commit into 5.1 tree (sergefp:1.1999)
View as plain text  
Below is the list of changes that have just been committed into a local
5.1 repository of psergey. When psergey does a push these changes will
be propagated to the main repository and, within 24 hours after the
push, to the public repository.
For information on how to access the public repository
see http://dev.mysql.com/doc/mysql/en/installing-source-tree.html

ChangeSet
  1.1999 06/01/04 11:09:01 sergefp@stripped +7 -0
  WL#2985 "Partition Pruning":
  - post-...-post review fixes
  - Added "integer range walking" that allows to do partition pruning for "a <=? t.field <=? b"
    by finding used partitions for a, a+1, a+2, ..., b-1, b. 

  sql/sql_select.cc
    1.381 06/01/04 11:08:49 sergefp@stripped +5 -0
    WL#2985 "Partition pruning": added comments.

  sql/sql_partition.cc
    1.20 06/01/04 11:08:49 sergefp@stripped +453 -3
    WL#2985 "Partition Pruning": "integer range walking": 
    - Added "partitioning interval analysis" functions: get_part_iter_for_interval_via_mapping, 
      get_part_iter_for_interval_via_walking, 
    - Added appropriate partition-set-iterator implementations
    - Added a function to set up Partitioning Interval Analysis-related fields in partition_info.

  sql/opt_range.cc
    1.194 06/01/04 11:08:49 sergefp@stripped +96 -177
    WL#2985 "Partition Pruning": "integer range walking":
    - Switched to use "partitioning interval analysis" functions
    - Fixed two problems in find_used_partitions() that occur on complicated WHERE clauses.

  sql/handler.h
    1.176 06/01/04 11:08:49 sergefp@stripped +158 -2
    WL#2985 "Partition Pruning": "integer range walking": 
    - class partition_info now has pointers to "partitioning interval analysis" functions
    - added "partition set iterator" definitions.

  mysql-test/t/partition_pruning.test
    1.5 06/01/04 11:08:49 sergefp@stripped +23 -0
    WL#2985 "Partition Pruning": tests for "integer range walking"

  mysql-test/t/partition.test
    1.10 06/01/04 11:08:49 sergefp@stripped +1 -1
    WL#2985 "Partition Pruning": post-review fixes

  mysql-test/r/partition_pruning.result
    1.5 06/01/04 11:08:49 sergefp@stripped +30 -0
    WL#2985 "Partition Pruning": tests for "integer range walking"

# This is a BitKeeper patch.  What follows are the unified diffs for the
# set of deltas contained in the patch.  The rest of the patch, the part
# that BitKeeper cares about, is below these diffs.
# User:	sergefp
# Host:	newbox.mylan
# Root:	/home/psergey/mysql-5.1-ppruning-r4

--- 1.175/sql/handler.h	2005-12-29 09:32:38 +03:00
+++ 1.176/sql/handler.h	2006-01-04 11:08:49 +03:00
@@ -474,6 +474,8 @@
   uint32 end_part;
   bool use_bit_array;
 } part_id_range;
+
+
 /**
  * An enum and a struct to handle partitioning and subpartitioning.
  */
@@ -537,7 +539,109 @@
                                  uint32 *part_id);
 typedef uint32 (*get_subpart_id_func)(partition_info *part_info);
 
-class partition_info :public Sql_alloc {
+
+struct st_partition_iter;
+#define NOT_A_PARTITION_ID ((uint32)-1)
+
+/*
+  A "Get next" function for partition iterator.
+  SYNOPSIS
+    partition_iter_func()
+      part_iter  Partition iterator, you call only "iter.get_next(&iter)"
+
+  RETURN 
+    NOT_A_PARTITION_ID if there are no more partitions.
+    [sub]partition_id  of the next partition
+*/
+
+typedef uint32 (*partition_iter_func)(st_partition_iter* part_iter);
+
+
+/*
+  Partition set iterator. Used to enumerate a set of [sub]partitions
+  obtained in partition interval analysis (see get_partitions_in_range_iter).
+
+  For the user, the only meaningful field is get_next, which may be used as
+  follows:
+             part_iterator.get_next(&part_iterator);
+  
+  Initialization is done by any of the following calls:
+    - get_partitions_in_range_iter-type function call
+    - init_single_partition_iterator()
+    - init_all_partitions_iterator()
+  Cleanup is not needed.
+*/
+
+typedef struct st_partition_iter
+{
+  partition_iter_func get_next;
+
+  union {
+    struct {
+      uint32 start_part_num;
+      uint32 end_part_num;
+    };
+    struct {
+      longlong start_val;
+      longlong end_val;
+    };
+    bool null_returned;
+  };
+  partition_info *part_info;
+} PARTITION_ITERATOR;
+
+
+/*
+  Get an iterator for set of partitions that match given field-space interval
+
+  SYNOPSIS
+    get_partitions_in_range_iter()
+      part_info   Partitioning info
+      is_subpart  
+      min_val     Left edge,  field value in opt_range_key format.
+      max_val     Right edge, field value in opt_range_key format. 
+      flags       Some combination of NEAR_MIN, NEAR_MAX, NO_MIN_RANGE,
+                  NO_MAX_RANGE.
+      part_iter   Iterator structure to be initialized
+
+  DESCRIPTION
+    Functions with this signature are used to perform "Partitioning Interval
+    Analysis". This analysis is applicable for any type of [sub]partitioning 
+    by some function of a single fieldX. The idea is as follows:
+    Given an interval "const1 <=? fieldX <=? const2", find a set of partitions
+    that may contain records with value of fieldX within the given interval.
+
+    The min_val, max_val and flags parameters specify the interval.
+    The set of partitions is returned by initializing an iterator in *part_iter
+
+  NOTES
+    There are currently two functions of this type:
+     - get_part_iter_for_interval_via_walking
+     - get_part_iter_for_interval_via_mapping
+
+  RETURN 
+    0 - No matching partitions, iterator not initialized
+    1 - Some partitions would match, iterator intialized for traversing them
+   -1 - All partitions would match, iterator not initialized
+*/
+
+typedef int (*get_partitions_in_range_iter)(partition_info *part_info,
+                                            bool is_subpart,
+                                            byte *min_val, byte *max_val,
+                                            uint flags,
+                                            PARTITION_ITERATOR *part_iter);
+
+
+/* Initialize the iterator to return a single partition with given part_id */
+inline void init_single_partition_iterator(uint32 part_id,
+                                           PARTITION_ITERATOR *part_iter);
+
+/* Initialize the iterator to enumerate all partitions */
+inline void init_all_partitions_iterator(partition_info *part_info,
+                                         PARTITION_ITERATOR *part_iter);
+
+class partition_info : public Sql_alloc
+{
 public:
   /*
    * Here comes a set of definitions needed for partitioned table handlers.
@@ -566,7 +670,7 @@
     same in all subpartitions
   */
   get_subpart_id_func get_subpartition_id;
-  
+ 
   /* NULL-terminated array of fields used in partitioned expression */
   Field **part_field_array;
   /* NULL-terminated array of fields used in subpartitioned expression */
@@ -598,6 +702,39 @@
     longlong *range_int_array;
     LIST_PART_ENTRY *list_array;
   };
+  
+  /********************************************
+   * INTERVAL ANALYSIS
+   ********************************************/
+  /*
+    Partitioning interval analysis function for partitioning, or NULL if 
+    interval analysis is not supported for this kind of partitioning.
+  */
+  get_partitions_in_range_iter get_part_iter_for_interval;
+  /*
+    Partitioning interval analysis function for subpartitioning, or NULL if
+    interval analysis is not supported for this kind of partitioning.
+  */
+  get_partitions_in_range_iter get_subpart_iter_for_interval;
+  
+  /*
+    Valid iff
+    get_part_iter_for_interval=get_part_iter_for_interval_via_walking:
+      controls how we'll process "field < C" and "field > C" intervals.
+      If the partitioning function F is strictly increasing, then for any x, y
+      "x < y" => "F(x) < F(y)" (*), i.e. when we get interval "field < C" 
+      we can perform partition pruning on the equivalent "F(field) < F(C)".
+
+      If the partitioning function not strictly increasing (it is simply
+      increasing), then instead of (*) we get "x < y" => "F(x) <= F(y)"
+      i.e. for interval "field < C" we can perform partition pruning for
+      "F(field) <= F(C)".
+  */
+  bool range_analysis_include_bounds;
+  /********************************************
+   * INTERVAL ANALYSIS ENDS 
+   ********************************************/
+  
   char* part_info_string;
 
   char *part_func_string;
@@ -681,6 +818,25 @@
 
 
 #ifdef WITH_PARTITION_STORAGE_ENGINE
+uint32 get_next_partition_id_range(struct st_partition_iter* part_iter);
+
+inline void init_single_partition_iterator(uint32 part_id,
+                                           PARTITION_ITERATOR *part_iter)
+{
+  part_iter->start_part_num= part_id;
+  part_iter->end_part_num= part_id+1;
+  part_iter->get_next= get_next_partition_id_range;
+}
+
+inline 
+void init_all_partitions_iterator(partition_info *part_info,
+                                  PARTITION_ITERATOR *part_iter)
+{
+  part_iter->start_part_num= 0;
+  part_iter->end_part_num= part_info->no_parts;
+  part_iter->get_next= get_next_partition_id_range;
+}
+
 /*
   Answers the question if subpartitioning is used for a certain table
   SYNOPSIS

--- 1.193/sql/opt_range.cc	2005-12-29 09:32:38 +03:00
+++ 1.194/sql/opt_range.cc	2006-01-04 11:08:49 +03:00
@@ -2070,7 +2070,7 @@
 }
 
 /****************************************************************************
- * Partition pruning starts
+ * Partition pruning module
  ****************************************************************************/
 #ifdef WITH_PARTITION_STORAGE_ENGINE
 
@@ -2159,10 +2159,6 @@
 struct st_part_opt_info;
 
 typedef void (*mark_full_part_func)(partition_info*, uint32);
-typedef uint32 (*part_num_to_partition_id_func)(struct st_part_prune_param*,
-                                                uint32);
-typedef uint32 (*get_endpoint_func)(partition_info*, bool left_endpoint,
-                                    bool include_endpoint);
 
 /*
   Partition pruning operation context
@@ -2170,7 +2166,7 @@
 typedef struct st_part_prune_param
 {
   RANGE_OPT_PARAM range_param; /* Range analyzer parameters */
-  
+
   /***************************************************************
    Following fields are filled in based solely on partitioning 
    definition and not modified after that:
@@ -2200,32 +2196,6 @@
   int last_subpart_partno; /* Same as above for supartitioning */
 
   /*
-    Function to be used to analyze non-singlepoint intervals (Can be pointer
-    to one of two functions - for RANGE and for LIST types).  NULL means 
-    partitioning type and/or expression doesn't allow non-singlepoint interval
-    analysis.
-    See get_list_array_idx_for_endpoint (or get_range_...) for description of
-    what the function does.
-  */
-  get_endpoint_func   get_endpoint;
-
-  /* Maximum possible value that can be returned by get_endpoint function */
-  uint32  max_endpoint_val;
-
-  /* 
-    For RANGE partitioning, part_num_to_part_id_range, for LIST partitioning,
-    part_num_to_part_id_list. Just to avoid the if-else clutter.
-  */
-  part_num_to_partition_id_func endpoints_walk_func;
-
-  /*
-    If true, process "key < const" as "part_func(key) < part_func(const)",
-    otherwise as "part_func(key) <= part_func(const)". Same for '>' and '>='.
-    This is defined iff get_endpoint != NULL.
-  */
-  bool force_include_bounds;
- 
-  /*
     is_part_keypart[i] == test(keypart #i in partitioning index is a member
                                used in partitioning)
     Used to maintain current values of cur_part_fields and cur_subpart_fields
@@ -2243,25 +2213,12 @@
   uint cur_part_fields;
   /* Same as cur_part_fields, but for subpartitioning */
   uint cur_subpart_fields;
- 
-  /***************************************************************
-   Following fields are used to store an 'iterator' that can be 
-   used to obtain a set of used partitions.
-   **************************************************************/
-  /* 
-    Start and end+1 partition "numbers". They can have two meanings depending
-    of the value of part_num_to_part_id:
-    part_num_to_part_id_range - numbers are partition ids
-    part_num_to_part_id_list  - numbers are indexes in part_info->list_array
-  */
-  uint32 start_part_num;
-  uint32 end_part_num;
 
-  /* 
-    A function that should be used to convert two above "partition numbers"
-    to partition_ids.
-  */
-  part_num_to_partition_id_func part_num_to_part_id;
+  /* Iterator to be used to obtain the "current" set of used partitions */
+  PARTITION_ITERATOR part_iter;
+
+  /* Initialized bitmap of no_subparts size */
+  MY_BITMAP subparts_bitmap;
 } PART_PRUNE_PARAM;
 
 static bool create_partition_index_description(PART_PRUNE_PARAM *prune_par);
@@ -2377,9 +2334,7 @@
     prune_param.arg_stack_end= prune_param.arg_stack;
     prune_param.cur_part_fields= 0;
     prune_param.cur_subpart_fields= 0;
-    prune_param.part_num_to_part_id= part_num_to_part_id_range;
-    prune_param.start_part_num= 0;
-    prune_param.end_part_num= prune_param.part_info->no_parts;
+    init_all_partitions_iterator(part_info, &prune_param.part_iter);
     if (!tree->keys[0] || (-1 == (res= find_used_partitions(&prune_param,
                                                             tree->keys[0]))))
       goto all_used;
@@ -2451,7 +2406,7 @@
     format.
 */
 
-static void store_key_image_to_rec(Field *field, char *ptr, uint len)
+void store_key_image_to_rec(Field *field, char *ptr, uint len)
 {
   /* Do the same as print_key() does */ 
   if (field->real_maybe_null())
@@ -2512,19 +2467,6 @@
     bitmap_set_bit(&part_info->used_partitions, start);
 }
 
-/* See comment in PART_PRUNE_PARAM::part_num_to_part_id about what this is */
-static uint32 part_num_to_part_id_range(PART_PRUNE_PARAM* ppar, uint32 num)
-{
-  return num; 
-}
-
-/* See comment in PART_PRUNE_PARAM::part_num_to_part_id about what this is */
-static uint32 part_num_to_part_id_list(PART_PRUNE_PARAM* ppar, uint32 num)
-{
-  return ppar->part_info->list_array[num].partition_id;
-}
-
-
 /*
   Find the set of used partitions for List<SEL_IMERGE>
   SYNOPSIS
@@ -2612,9 +2554,7 @@
     ppar->arg_stack_end= ppar->arg_stack;
     ppar->cur_part_fields= 0;
     ppar->cur_subpart_fields= 0;
-    ppar->part_num_to_part_id= part_num_to_part_id_range;
-    ppar->start_part_num= 0;
-    ppar->end_part_num= ppar->part_info->no_parts;
+    init_all_partitions_iterator(ppar->part_info, &ppar->part_iter);
     if (-1 == (res |= find_used_partitions(ppar, (*ptree)->keys[0])))
       return -1;
   }
@@ -2683,58 +2623,29 @@
 
   if (key_tree->type == SEL_ARG::KEY_RANGE)
   {
-    if (partno == 0 && (NULL != ppar->get_endpoint))
+    if (partno == 0 && (NULL != ppar->part_info->get_part_iter_for_interval))
     {
       /* 
         Partitioning is done by RANGE|INTERVAL(monotonic_expr(fieldX)), and
-        we got "const1 CMP fieldX CMP const2" interval
+        we got "const1 CMP fieldX CMP const2" interval <-- psergey-todo: change
       */
       DBUG_EXECUTE("info", dbug_print_segment_range(key_tree,
                                                     ppar->range_param.
                                                     key_parts););
-      /* Find minimum */
-      if (key_tree->min_flag & NO_MIN_RANGE)
-        ppar->start_part_num= 0;
-      else
+      res= ppar->part_info->
+           get_part_iter_for_interval(ppar->part_info,
+                                      FALSE,
+                                      key_tree->min_value, 
+                                      key_tree->max_value,
+                                      key_tree->min_flag | key_tree->max_flag,
+                                      &ppar->part_iter);
+      if (!res)
+        goto go_right; /* res=0 --> no satisfying partitions */
+      if (res == -1)
       {
-        /*
-          Store the interval edge in the record buffer, and call the
-          function that maps the edge in table-field space to an edge
-          in ordered-set-of-partitions (for RANGE partitioning) or 
-          indexes-in-ordered-array-of-list-constants (for LIST) space.
-        */
-        store_key_image_to_rec(key_tree->field, key_tree->min_value, 
-                               ppar->range_param.key_parts[0].length);
-        bool include_endp= ppar->force_include_bounds ||
-                           !test(key_tree->min_flag & NEAR_MIN);
-        ppar->start_part_num= ppar->get_endpoint(ppar->part_info, 1,
-                                                 include_endp);
-        if (ppar->start_part_num == ppar->max_endpoint_val)
-        {
-          res= 0; /* No satisfying partitions */
-          goto pop_and_go_right;
-        }
-      }
-
-      /* Find maximum, do the same as above but for right interval bound */
-      if (key_tree->max_flag & NO_MAX_RANGE)
-        ppar->end_part_num= ppar->max_endpoint_val;
-      else
-      {
-        store_key_image_to_rec(key_tree->field, key_tree->max_value,
-                               ppar->range_param.key_parts[0].length);
-        bool include_endp= ppar->force_include_bounds ||
-                           !test(key_tree->max_flag & NEAR_MAX);
-        ppar->end_part_num= ppar->get_endpoint(ppar->part_info, 0,
-                                               include_endp);
-        if (ppar->start_part_num == ppar->end_part_num)
-        {
-          res= 0; /* No satisfying partitions */
-          goto pop_and_go_right;
-        }
+        //get a full range iterator
+        init_all_partitions_iterator(ppar->part_info, &ppar->part_iter);
       }
-      ppar->part_num_to_part_id= ppar->endpoints_walk_func;
-
       /* 
         Save our intent to mark full partition as used if we will not be able
         to obtain further limits on subpartitions
@@ -2743,6 +2654,42 @@
       goto process_next_key_part;
     }
 
+    if (partno == ppar->last_subpart_partno && 
+        (NULL != ppar->part_info->get_subpart_iter_for_interval))
+    {
+      PARTITION_ITERATOR subpart_iter;
+      DBUG_EXECUTE("info", dbug_print_segment_range(key_tree,
+                                                    ppar->range_param.
+                                                    key_parts););
+      res= ppar->part_info->
+           get_subpart_iter_for_interval(ppar->part_info,
+                                         TRUE,
+                                         key_tree->min_value, 
+                                         key_tree->max_value,
+                                         key_tree->min_flag | key_tree->max_flag,
+                                         &subpart_iter);
+      DBUG_ASSERT(res); /* We can't get "no satisfying subpartitions" */
+      if (res == -1)
+        return -1; /* all subpartitions satisfy */
+        
+      uint32 subpart_id;
+      bitmap_clear_all(&ppar->subparts_bitmap);
+      while ((subpart_id= subpart_iter.get_next(&subpart_iter)) != NOT_A_PARTITION_ID)
+        bitmap_set_bit(&ppar->subparts_bitmap, subpart_id);
+
+      /* Mark each partition as used in each subpartition.  */
+      uint32 part_id;
+      while ((part_id= ppar->part_iter.get_next(&ppar->part_iter)) !=
+              NOT_A_PARTITION_ID)
+      {
+        for (uint i= 0; i < ppar->part_info->no_subparts; i++)
+          if (bitmap_is_set(&ppar->subparts_bitmap, i))
+            bitmap_set_bit(&ppar->part_info->used_partitions,
+                           part_id * ppar->part_info->no_subparts + i);
+      }
+      goto go_right;
+    }
+
     if (key_tree->is_singlepoint())
     {
       pushed= TRUE;
@@ -2768,9 +2715,7 @@
           goto pop_and_go_right;
         }
         /* Rembember the limit we got - single partition #part_id */
-        ppar->part_num_to_part_id= part_num_to_part_id_range;
-        ppar->start_part_num= part_id;
-        ppar->end_part_num=   part_id + 1;
+        init_single_partition_iterator(part_id, &ppar->part_iter);
         
         /*
           If there are no subpartitions/we fail to get any limit for them, 
@@ -2780,7 +2725,8 @@
         goto process_next_key_part;
       }
 
-      if (partno == ppar->last_subpart_partno)
+      if (partno == ppar->last_subpart_partno &&
+          ppar->cur_subpart_fields == ppar->subpart_fields)
       {
         /* 
           Ok, we've got "fieldN<=>constN"-type SEL_ARGs for all subpartitioning
@@ -2796,12 +2742,12 @@
         uint32 subpart_id= part_info->get_subpartition_id(part_info);
         
         /* Mark this partition as used in each subpartition. */
-        for (uint32 num= ppar->start_part_num; num != ppar->end_part_num; 
-             num++)
+        uint32 part_id;
+        while ((part_id= ppar->part_iter.get_next(&ppar->part_iter)) !=
+                NOT_A_PARTITION_ID)
         {
           bitmap_set_bit(&part_info->used_partitions,
-                         ppar->part_num_to_part_id(ppar, num) * 
-                         part_info->no_subparts + subpart_id);
+                         part_id * part_info->no_subparts + subpart_id);
         }
         res= 1; /* Some partitions were marked as used */
         goto pop_and_go_right;
@@ -2822,34 +2768,28 @@
 process_next_key_part:
   if (key_tree->next_key_part)
     res= find_used_partitions(ppar, key_tree->next_key_part);
-  else 
+  else
     res= -1;
-  
-  if (res == -1) /* Got "full range" for key_tree->next_key_part call */
+ 
+  if (set_full_part_if_bad_ret)
   {
-    if (set_full_part_if_bad_ret)
+    if (res == -1)
     {
-      for (uint32 num= ppar->start_part_num; num != ppar->end_part_num; 
-           num++)
+      /* Got "full range" for subpartitioning fields */
+      uint32 part_id;
+      bool found= FALSE;
+      while ((part_id= ppar->part_iter.get_next(&ppar->part_iter)) != NOT_A_PARTITION_ID)
       {
-        ppar->mark_full_partition_used(ppar->part_info,
-                                       ppar->part_num_to_part_id(ppar, num));
+        ppar->mark_full_partition_used(ppar->part_info, part_id);
+        found= TRUE;
       }
-      res= 1;
+      res= test(found);
     }
-    else
-      return -1;
-  }
-
-  if (set_full_part_if_bad_ret)
-  {
     /*
       Restore the "used partitions iterator" to the default setting that
       specifies iteration over all partitions.
     */
-    ppar->part_num_to_part_id= part_num_to_part_id_range;
-    ppar->start_part_num= 0;
-    ppar->end_part_num= ppar->part_info->no_parts;
+    init_all_partitions_iterator(ppar->part_info, &ppar->part_iter);
   }
 
   if (pushed)
@@ -2860,7 +2800,10 @@
     ppar->cur_part_fields-=    ppar->is_part_keypart[partno];
     ppar->cur_subpart_fields-= ppar->is_subpart_keypart[partno];
   }
-  
+
+  if (res == -1)
+    return -1;
+go_right:
   if (key_tree->right != &null_element)
   {
     if (-1 == (right_res= find_used_partitions(ppar,key_tree->right)))
@@ -2967,38 +2910,6 @@
     ppar->get_top_partition_id_func= part_info->get_partition_id;
   }
 
-  enum_monotonicity_info minfo;
-  ppar->get_endpoint= NULL;
-  if (part_info->part_expr && 
-      (minfo= part_info->part_expr->get_monotonicity_info()) != NON_MONOTONIC)
-  {
-    /*
-      ppar->force_include_bounds controls how we'll process "field < C" and 
-      "field > C" intervals.
-      If the partitioning function F is strictly increasing, then for any x, y
-      "x < y" => "F(x) < F(y)" (*), i.e. when we get interval "field < C" 
-      we can perform partition pruning on the equivalent "F(field) < F(C)".
-
-      If the partitioning function not strictly increasing (it is simply
-      increasing), then instead of (*) we get "x < y" => "F(x) <= F(y)"
-      i.e. for interval "field < C" we can perform partition pruning for
-      "F(field) <= F(C)".
-    */
-    ppar->force_include_bounds= test(minfo == MONOTONIC_INCREASING);
-    if (part_info->part_type == RANGE_PARTITION)
-    {
-      ppar->get_endpoint=        get_partition_id_range_for_endpoint;
-      ppar->endpoints_walk_func= part_num_to_part_id_range;
-      ppar->max_endpoint_val=    part_info->no_parts;
-    }
-    else if (part_info->part_type == LIST_PARTITION)
-    {
-      ppar->get_endpoint=        get_list_array_idx_for_endpoint;
-      ppar->endpoints_walk_func= part_num_to_part_id_list;
-      ppar->max_endpoint_val=    part_info->no_list_values;
-    }
-  }
-
   KEY_PART *key_part;
   MEM_ROOT *alloc= range_par->mem_root;
   if (!total_parts || 
@@ -3011,11 +2922,19 @@
       !(ppar->is_subpart_keypart= (my_bool*)alloc_root(alloc, sizeof(my_bool)*
                                                            total_parts)))
     return TRUE;
-
+ 
+  if (ppar->subpart_fields)
+  {
+    uint32 *buf;
+    uint32 bufsize= bitmap_buffer_size(ppar->part_info->no_subparts);
+    if (!(buf= (uint32*)alloc_root(alloc, bufsize)))
+      return TRUE;
+    bitmap_init(&ppar->subparts_bitmap, buf, ppar->part_info->no_subparts, FALSE);
+  }
   range_par->key_parts= key_part;
   Field **field= (ppar->part_fields)? part_info->part_field_array :
                                            part_info->subpart_field_array;
-  bool subpart_fields= FALSE;
+  bool in_subpart_fields= FALSE;
   for (uint part= 0; part < total_parts; part++, key_part++)
   {
     key_part->key=          0;
@@ -3036,13 +2955,13 @@
     key_part->image_type =  Field::itRAW;
     /* We don't set key_parts->null_bit as it will not be used */
 
-    ppar->is_part_keypart[part]= !subpart_fields;
-    ppar->is_subpart_keypart[part]= subpart_fields;
+    ppar->is_part_keypart[part]= !in_subpart_fields;
+    ppar->is_subpart_keypart[part]= in_subpart_fields;
  
     if (!*(++field))
     {
       field= part_info->subpart_field_array;
-      subpart_fields= TRUE;
+      in_subpart_fields= TRUE;
     }
   }
   range_par->key_parts_end= key_part;

--- 1.380/sql/sql_select.cc	2005-12-26 19:45:58 +03:00
+++ 1.381/sql/sql_select.cc	2006-01-04 11:08:49 +03:00
@@ -638,6 +638,11 @@
     TABLE_LIST *tbl;
     for (tbl= select_lex->leaf_tables; tbl; tbl= tbl->next_leaf)
     {
+      /* 
+        If tbl->embedding!=NULL that means that this table is in the inner
+        part of the nested outer join, and we can't do partition pruning
+        (TODO: check if this limitation can be lifted)
+      */
       if (!tbl->embedding)
       {
         Item *prune_cond= tbl->on_expr? tbl->on_expr : conds;

--- 1.9/mysql-test/t/partition.test	2005-12-27 15:04:27 +03:00
+++ 1.10/mysql-test/t/partition.test	2006-01-04 11:08:49 +03:00
@@ -209,7 +209,7 @@
   partition p0 values in (12),
   partition p1 values in (14)
 );
---error 1500
+--error ER_NO_PARTITION_FOR_GIVEN_VALUE
 insert into t1 values (10,1);
 
 drop table t1;

--- 1.19/sql/sql_partition.cc	2005-12-27 15:04:27 +03:00
+++ 1.20/sql/sql_partition.cc	2006-01-04 11:08:49 +03:00
@@ -91,6 +91,21 @@
 uint32 get_partition_id_linear_key_sub(partition_info *part_info); 
 #endif
 
+static uint32 get_next_partition_via_walking(PARTITION_ITERATOR*);
+static uint32 get_next_subpartition_via_walking(PARTITION_ITERATOR*);
+uint32 get_next_partition_id_range(PARTITION_ITERATOR* part_iter);
+uint32 get_next_partition_id_list(PARTITION_ITERATOR* part_iter);
+int get_part_iter_for_interval_via_mapping(partition_info *part_info,
+                                           bool is_subpart,
+                                           byte *min_value, byte *max_value,
+                                           uint flags,
+                                           PARTITION_ITERATOR *part_iter);
+int get_part_iter_for_interval_via_walking(partition_info *part_info,
+                                           bool is_subpart,
+                                           byte *min_value, byte *max_value,
+                                           uint flags,
+                                           PARTITION_ITERATOR *part_iter);
+static void set_up_range_analysis_info(partition_info *part_info);
 
 /*
   A routine used by the parser to decide whether we are specifying a full
@@ -1603,8 +1618,8 @@
     }
   }
 }
-          
-        
+
+
 /*
   For linear hashing we need a mask which is on the form 2**n - 1 where
   2**n >= no_parts. Thus if no_parts is 6 then mask is 2**3 - 1 = 8 - 1 = 7.
@@ -1811,6 +1826,7 @@
   check_range_capable_PF(table);
   set_up_partition_key_maps(table, part_info);
   set_up_partition_func_pointers(part_info);
+  set_up_range_analysis_info(part_info);
   result= FALSE;
 end:
   thd->set_query_id= save_set_query_id;
@@ -3489,7 +3505,7 @@
   uint partition_id= 0;
   List_iterator<partition_element> it(part_info->partitions);
   
-  if (part_info->subpart_type != NOT_A_PARTITION)
+  if (is_sub_partitioned(part_info))
   {
     partition_element *head_pe;
     while ((head_pe= it++))
@@ -3527,5 +3543,439 @@
       partition_id++;
     }
   }
+}
+
+
+/****************************************************************************
+ * Partition interval analysis support
+ ***************************************************************************/
+
+/*
+  Setup partition_info::* members related to partitioning range analysis
+
+  SYNOPSIS
+    set_up_partition_func_pointers()
+      part_info  Partitioning info structure
+
+  DESCRIPTION
+    Assuming that passed partition_info structure already has correct values
+    for members that specify [sub]partitioning type, table fields, and
+    functions, set up partition_info::* members that are related to
+    Partitioning Interval Analysis (see get_partitions_in_range_iter for its
+    definition)
+
+  IMPLEMENTATION
+    There are two available interval analyzer functions:
+    (1) get_part_iter_for_interval_via_mapping 
+    (2) get_part_iter_for_interval_via_walking
+
+    They both have limited applicability:
+    (1) is applicable for "PARTITION BY <RANGE|LIST>(func(t.field))", where
+    func is a monotonic function.
+    
+    (2) is applicable for 
+      "[SUB]PARTITION BY <any-partitioning-type>(any_func(t.integer_field))"
+      
+    If both are applicable, (1) is preferred over (2).
+    
+    This function sets part_info::get_part_iter_for_interval according to
+    this criteria, and also sets some auxilary fields that the function
+    uses.
+*/
+
+static void set_up_range_analysis_info(partition_info *part_info)
+{
+  enum_monotonicity_info minfo;
+
+  /* Set the catch-all default */
+  part_info->get_part_iter_for_interval= NULL;
+  part_info->get_subpart_iter_for_interval= NULL;
+
+  /* 
+    Check if get_part_iter_for_interval_via_mapping() can be used for 
+    partitioning
+  */
+  switch (part_info->part_type) {
+  case RANGE_PARTITION:
+  case LIST_PARTITION:
+    minfo= part_info->part_expr->get_monotonicity_info();
+    if (minfo != NON_MONOTONIC)
+    {
+      part_info->range_analysis_include_bounds=
+        test(minfo == MONOTONIC_INCREASING);
+      part_info->get_part_iter_for_interval=
+        get_part_iter_for_interval_via_mapping;
+      goto setup_subparts;
+    }
+  default:
+    ;
+  }
+   
+  /*
+    Check get_part_iter_for_interval_via_walking() can be used for
+    partitioning
+  */
+  if (part_info->no_part_fields == 1)
+  {
+    Field *field= part_info->part_field_array[0];
+    switch (field->type()) {
+    case MYSQL_TYPE_TINY:
+    case MYSQL_TYPE_SHORT:
+    case MYSQL_TYPE_LONG:
+    case MYSQL_TYPE_LONGLONG:
+      part_info->get_part_iter_for_interval=
+        get_part_iter_for_interval_via_walking;
+      break;
+    default:
+      ;
+    }
+  }
+
+setup_subparts:
+  /*
+    Check get_part_iter_for_interval_via_walking() can be used for
+    subpartitioning
+  */
+  if (part_info->no_subpart_fields == 1)
+  {
+    Field *field= part_info->subpart_field_array[0];
+    switch (field->type()) {
+    case MYSQL_TYPE_TINY:
+    case MYSQL_TYPE_SHORT:
+    case MYSQL_TYPE_LONG:
+    case MYSQL_TYPE_LONGLONG:
+      part_info->get_subpart_iter_for_interval=
+        get_part_iter_for_interval_via_walking;
+      break;
+    default:
+      ;
+    }
+  }
+}
+
+
+typedef uint32 (*get_endpoint_func)(partition_info*, bool left_endpoint,
+                                    bool include_endpoint);
+
+/*
+  Partitioning Interval Analysis: Initialize the iterator for "mapping" case
+
+  SYNOPSIS
+    get_part_iter_for_interval_via_mapping()
+      part_info   Partition info
+      is_subpart  TRUE  - act for subpartitioning
+                  FALSE - act for partitioning
+      min_value   minimum field value, in opt_range key format.
+      max_value   minimum field value, in opt_range key format.
+      flags       Some combination of NEAR_MIN, NEAR_MAX, NO_MIN_RANGE,
+                  NO_MAX_RANGE.
+      part_iter   Iterator structure to be initialized
+
+  DESCRIPTION
+    Initialize partition set iterator to walk over the interval in
+    ordered-list-of-partitions (for RANGE partitioning) or 
+    ordered-list-of-list-constants (for LIST partitioning) space.
+
+  IMPLEMENTATION
+    This function is applied when partitioning is done by
+    <RANGE|LIST>(ascending_func(t.field)), and we can map an interval in
+    t.field space into a sub-array of partition_info::range_int_array or
+    partition_info::list_array (see get_partition_id_range_for_endpoint,
+    get_list_array_idx_for_endpoint for details).
+    
+    The function performs this interval mapping, and sets the iterator to
+    traverse the sub-array and return appropriate partitions.
+    
+  RETURN 
+    0 - No matching partitions (iterator not initialized)
+    1 - Ok, iterator intialized for traversal of matching partitions.
+   -1 - All partitions would match (iterator not initialized)
+*/
+
+int get_part_iter_for_interval_via_mapping(partition_info *part_info,
+                                           bool is_subpart,
+                                           byte *min_value, byte *max_value,
+                                           uint flags,
+                                           PARTITION_ITERATOR *part_iter)
+{
+  DBUG_ASSERT(!is_subpart);
+  Field *field= part_info->part_field_array[0];
+  uint32             max_endpoint_val;
+  get_endpoint_func  get_endpoint;
+  uint field_len= field->pack_length_in_rec();
+
+  if (part_info->part_type == RANGE_PARTITION)
+  {
+    get_endpoint=        get_partition_id_range_for_endpoint;
+    max_endpoint_val=    part_info->no_parts;
+    part_iter->get_next= get_next_partition_id_range;
+  }
+  else if (part_info->part_type == LIST_PARTITION)
+  {
+    get_endpoint=        get_list_array_idx_for_endpoint;
+    max_endpoint_val=    part_info->no_list_values;
+    part_iter->get_next= get_next_partition_id_list;
+    part_iter->part_info= part_info;
+  }
+  else
+    DBUG_ASSERT(0);
+
+  /* Find minimum */
+  if (flags & NO_MIN_RANGE)
+    part_iter->start_part_num= 0;
+  else
+  {
+    /*
+      Store the interval edge in the record buffer, and call the
+      function that maps the edge in table-field space to an edge
+      in ordered-set-of-partitions (for RANGE partitioning) or 
+      index-in-ordered-array-of-list-constants (for LIST) space.
+    */
+    store_key_image_to_rec(field, min_value, field_len);
+    bool include_endp= part_info->range_analysis_include_bounds ||
+                       !test(flags & NEAR_MIN);
+    part_iter->start_part_num= get_endpoint(part_info, 1, include_endp);
+    if (part_iter->start_part_num == max_endpoint_val)
+      return 0; /* No partitions */
+  }
+
+  /* Find maximum, do the same as above but for right interval bound */
+  if (flags & NO_MAX_RANGE)
+    part_iter->end_part_num= max_endpoint_val;
+  else
+  {
+    store_key_image_to_rec(field, max_value, field_len);
+    bool include_endp= part_info->range_analysis_include_bounds ||
+                       !test(flags & NEAR_MAX);
+    part_iter->end_part_num= get_endpoint(part_info, 0, include_endp);
+    if (part_iter->start_part_num == part_iter->end_part_num)
+      return 0; /* No partitions */
+  }
+  return 1; /* Ok, iterator initialized */
+}
+
+
+/* See get_part_iter_for_interval_via_walking for definition of what this is */
+#define MAX_RANGE_TO_WALK 10
+
+
+/*
+  Partitioning Interval Analysis: Initialize iterator to walk integer interval
+
+  SYNOPSIS
+    get_part_iter_for_interval_via_walking()
+      part_info   Partition info
+      is_subpart  TRUE  - act for subpartitioning
+                  FALSE - act for partitioning
+      min_value   minimum field value, in opt_range key format.
+      max_value   minimum field value, in opt_range key format.
+      flags       Some combination of NEAR_MIN, NEAR_MAX, NO_MIN_RANGE,
+                  NO_MAX_RANGE.
+      part_iter   Iterator structure to be initialized
+
+  DESCRIPTION
+    Initialize partition set iterator to walk over interval in integer field
+    space. That is, for "const1 <=? t.field <=? const2" interval, initialize 
+    the iterator to do this: 
+      get partition id for t.field = const1,   return it
+      get partition id for t.field = const1+1, return it
+       ...                 t.field = const1+2, ...
+       ...                           ...       ...
+       ...                 t.field = const2    ...
+
+  IMPLEMENTATION
+    See get_partitions_in_range_iter for general description of interval
+    analysis. We support walking over the following intervals: 
+      "t.field IS NULL" 
+      "c1 <=? t.field <=? c2", where c1 and c2 are finite. 
+    Intervals with +inf/-inf, and [NULL, c1] interval can be processed but
+    that is more tricky and I don't have time to do it right now.
+    
+    Additionally we have these requirements:
+    * number of values in the interval must be less then number of
+      [sub]partitions, and 
+    * Number of values in the interval must be less then MAX_RANGE_TO_WALK.
+    
+    The rationale behind these requirements is that if they are not met
+    we're likely to hit most of the partitions and traversing the interval
+    will only add overhead. So it's better return "all partitions used" in
+    this case.
+
+  RETURN
+    0 - No matching partitions, iterator not initialized
+    1 - Some partitions would match, iterator intialized for traversing them
+   -1 - All partitions would match, iterator not initialized
+*/
+
+int get_part_iter_for_interval_via_walking(partition_info *part_info,
+                                           bool is_subpart,
+                                           byte *min_value, byte *max_value,
+                                           uint flags,
+                                           PARTITION_ITERATOR *part_iter)
+{
+  Field *field;
+  uint total_parts;
+  partition_iter_func get_next_func;
+  if (is_subpart)
+  {
+    field= part_info->subpart_field_array[0];
+    total_parts= part_info->no_subparts;
+    get_next_func=  get_next_subpartition_via_walking;
+  }
+  else
+  {
+    field= part_info->part_field_array[0];
+    total_parts= part_info->no_parts;
+    get_next_func=  get_next_partition_via_walking;
+  }
+
+  /* Handle the "t.field IS NULL" interval, it is a special case */
+  if (field->real_maybe_null() && !(flags & (NO_MIN_RANGE | NO_MAX_RANGE)) &&
+      *min_value && *max_value)
+  {
+    /* 
+      We don't have a part_iter->get_next() function that would find which
+      partition "t.field IS NULL" belongs to, so find partition that contains 
+      NULL right here, and return an iterator over singleton set.
+    */
+    uint32 part_id;
+    field->set_null();
+    if (is_subpart)
+    {
+      part_id= part_info->get_subpartition_id(part_info);
+      init_single_partition_iterator(part_id, part_iter);
+      return 1; /* Ok, iterator initialized */
+    }
+    else
+    {
+      if (!part_info->get_partition_id(part_info, &part_id))
+      {
+        init_single_partition_iterator(part_id, part_iter);
+        return 1; /* Ok, iterator initialized */
+      }
+    }
+    return 0; /* No partitions match */
+  }
+
+  if (flags & (NO_MIN_RANGE | NO_MAX_RANGE))
+    return -1; /* Can't handle this interval, have to use all partitions */
+  
+  /* Get integers for left and right interval bound */
+  longlong a, b;
+  uint len= field->pack_length_in_rec();
+  store_key_image_to_rec(field, min_value, len);
+  a= field->val_int();
+  
+  store_key_image_to_rec(field, max_value, len);
+  b= field->val_int();
+
+  a += test(flags & NEAR_MIN);
+  b += test(!(flags & NEAR_MAX));
+  uint n_values= b - a;
+  
+  if (n_values > total_parts || n_values > MAX_RANGE_TO_WALK)
+    return -1;
+
+  part_iter->start_val= a;
+  part_iter->end_val=   b;
+  part_iter->part_info= part_info;
+  part_iter->get_next=  get_next_func;
+  return 1;
+}
+
+
+/*
+  PARTITION_ITERATOR::get_next implementation: enumerate partitions in range
+
+  SYNOPSIS
+    get_next_partition_id_list()
+      part_iter  Partition set iterator structure
+
+  DESCRIPTION
+    This is implementation of PARTITION_ITERATOR::get_next() that returns
+    [sub]partition ids in [min_partition_id, max_partition_id] range.
+
+  RETURN
+    partition id
+    NOT_A_PARTITION_ID if there are no more partitions
+*/
+
+uint32 get_next_partition_id_range(PARTITION_ITERATOR* part_iter)
+{
+  if (part_iter->start_part_num == part_iter->end_part_num)
+    return NOT_A_PARTITION_ID;
+  else
+    return part_iter->start_part_num++;
+}
+
+
+/*
+  PARTITION_ITERATOR::get_next implementation for LIST partitioning
+
+  SYNOPSIS
+    get_next_partition_id_list()
+      part_iter  Partition set iterator structure
+
+  DESCRIPTION
+    This is special implementation of PARTITION_ITERATOR::get_next() for
+    LIST partitioning: it enumerates partition ids in 
+    part_info->list_array[i] where i runs over [min_idx, max_idx] interval.
+
+  RETURN 
+    partition id
+    NOT_A_PARTITION_ID if there are no more partitions
+*/
+
+uint32 get_next_partition_id_list(PARTITION_ITERATOR *part_iter)
+{
+  if (part_iter->start_part_num == part_iter->end_part_num)
+    return NOT_A_PARTITION_ID;
+  else
+    return part_iter->part_info->list_array[part_iter->
+                                            start_part_num++].partition_id;
+}
+
+
+/*
+  PARTITION_ITERATOR::get_next implementation: walk over integer interval
+
+  SYNOPSIS
+    get_next_partition_via_walking()
+      part_iter  Partitioning iterator
+
+  DESCRIPTION
+
+  RETURN 
+    partition id
+    NOT_A_PARTITION_ID if there are no more partitioning.
+*/
+
+static uint32 get_next_partition_via_walking(PARTITION_ITERATOR *part_iter)
+{
+  uint32 part_id;
+  Field *field= part_iter->part_info->part_field_array[0];
+  while (part_iter->start_val != part_iter->end_val)
+  {
+    field->store(part_iter->start_val, FALSE);
+    part_iter->start_val++;
+    if (!part_iter->part_info->get_partition_id(part_iter->part_info, 
+                                                &part_id))
+      return part_id;
+  }
+  return NOT_A_PARTITION_ID;
+}
+
+
+/* Same as get_next_partition_via_walking, but for subpartitions */
+
+static uint32 get_next_subpartition_via_walking(PARTITION_ITERATOR *part_iter)
+{
+  uint32 part_id;
+  Field *field= part_iter->part_info->subpart_field_array[0];
+  if (part_iter->start_val == part_iter->end_val)
+    return NOT_A_PARTITION_ID;
+  field->store(part_iter->start_val, FALSE);
+  part_iter->start_val++;
+  return part_iter->part_info->get_subpartition_id(part_iter->part_info);
 }
 

--- 1.4/mysql-test/r/partition_pruning.result	2005-12-29 09:32:38 +03:00
+++ 1.5/mysql-test/r/partition_pruning.result	2006-01-04 11:08:49 +03:00
@@ -274,3 +274,33 @@
 1	SIMPLE	X	p1,p2	ALL	a	NULL	NULL	NULL	4	Using where
 1	SIMPLE	Y	p1,p2	ref	a	a	4	test.X.a	2	
 drop table t1;
+create table t1 (a int) partition by hash(a) partitions 20;
+insert into t1 values (1),(2),(3);
+explain partitions select * from t1 where a >  1 and a < 3;
+id	select_type	table	partitions	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	t1	p2	ALL	NULL	NULL	NULL	NULL	3	Using where
+explain partitions select * from t1 where a >= 1 and a < 3;
+id	select_type	table	partitions	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	t1	p1,p2	ALL	NULL	NULL	NULL	NULL	3	Using where
+explain partitions select * from t1 where a >  1 and a <= 3;
+id	select_type	table	partitions	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	t1	p2,p3	ALL	NULL	NULL	NULL	NULL	3	Using where
+explain partitions select * from t1 where a >= 1 and a <= 3;
+id	select_type	table	partitions	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	t1	p1,p2,p3	ALL	NULL	NULL	NULL	NULL	3	Using where
+drop table t1;
+create table t1 (a int, b int) 
+partition by list(a) subpartition by hash(b) subpartitions 20 
+(
+partition p0 values in (0),
+partition p1 values in (1),
+partition p2 values in (2),
+partition p3 values in (3)
+);
+insert into t1 values (1,1),(2,2),(3,3);
+explain partitions select * from t1 where b >  1 and b < 3;
+id	select_type	table	partitions	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	t1	p0_sp2,p1_sp2,p2_sp2,p3_sp2	ALL	NULL	NULL	NULL	NULL	3	Using where
+explain partitions select * from t1 where b >  1 and b < 3 and (a =1 or a =2);
+id	select_type	table	partitions	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	t1	p1_sp2,p2_sp2	ALL	NULL	NULL	NULL	NULL	3	Using where

--- 1.4/mysql-test/t/partition_pruning.test	2005-12-29 09:32:38 +03:00
+++ 1.5/mysql-test/t/partition_pruning.test	2006-01-04 11:08:49 +03:00
@@ -247,5 +247,28 @@
 select * from t1 X, t1 Y where X.a = Y.a and (X.a=1 or X.a=2);
 
 drop table t1;
+
+# Tests for "short ranges"
+create table t1 (a int) partition by hash(a) partitions 20;
+insert into t1 values (1),(2),(3);
+explain partitions select * from t1 where a >  1 and a < 3;
+explain partitions select * from t1 where a >= 1 and a < 3;
+explain partitions select * from t1 where a >  1 and a <= 3;
+explain partitions select * from t1 where a >= 1 and a <= 3;
+drop table t1;
+
+create table t1 (a int, b int) 
+ partition by list(a) subpartition by hash(b) subpartitions 20 
+(
+  partition p0 values in (0),
+  partition p1 values in (1),
+  partition p2 values in (2),
+  partition p3 values in (3)
+);
+insert into t1 values (1,1),(2,2),(3,3);
+
+explain partitions select * from t1 where b >  1 and b < 3;
+explain partitions select * from t1 where b >  1 and b < 3 and (a =1 or a =2);
+
 # No tests for NULLs in RANGE(monotonic_expr()) - they depend on BUG#15447
 # being fixed.
Thread
bk commit into 5.1 tree (sergefp:1.1999)Sergey Petrunia4 Jan