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. 


mysql-test/r/partition_pruning.result:
  WL#2985 "Partition Pruning": tests for "integer range walking"
mysql-test/t/partition.test:
  WL#2985 "Partition Pruning": post-review fixes
mysql-test/t/partition_pruning.test:
  WL#2985 "Partition Pruning": tests for "integer range walking"
sql/handler.h:
  WL#2985 "Partition Pruning": "integer range walking": 
  - class partition_info now has pointers to "partitioning interval analysis" functions
  - added "partition set iterator" definitions.
sql/opt_range.cc:
  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/sql_partition.cc:
  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/sql_select.cc:
  WL#2985 "Partition pruning": added comments.

4 files changed, 712 insertions, 182 deletions

diff --git a/sql/handler.h b/sql/handler.h
index 9c67bb8a1f4..931527ecedd 100644
--- a/sql/handler.h
+++ b/sql/handler.h
@@ -474,6 +474,8 @@ typedef struct {
   uint32 end_part;
   bool use_bit_array;
 } part_id_range;
+
+
 /**
  * An enum and a struct to handle partitioning and subpartitioning.
  */
@@ -537,7 +539,109 @@ typedef bool (*get_part_id_func)(partition_info *part_info,
                                  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 @@ public:
     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 @@ public:
     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 @@ public:
 
 
 #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
diff --git a/sql/opt_range.cc b/sql/opt_range.cc
index a2fdea1bf6e..331261c26cd 100644
--- a/sql/opt_range.cc
+++ b/sql/opt_range.cc
@@ -2070,7 +2070,7 @@ int SQL_SELECT::test_quick_select(THD *thd, key_map keys_to_use,
 }
 
 /****************************************************************************
- * Partition pruning starts
+ * Partition pruning module
  ****************************************************************************/
 #ifdef WITH_PARTITION_STORAGE_ENGINE
 
@@ -2159,10 +2159,6 @@ struct st_part_prune_param;
 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 uint32 (*get_endpoint_func)(partition_info*, bool left_endpoint,
 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 @@ typedef struct st_part_prune_param
   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 @@ typedef struct st_part_prune_param
   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 @@ bool prune_partitions(THD *thd, TABLE *table, Item *pprune_cond)
     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 @@ end:
     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 @@ static void mark_full_partition_used_with_parts(partition_info *part_info,
     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 @@ int find_used_partitions_imerge(PART_PRUNE_PARAM *ppar, SEL_IMERGE *imerge)
     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 @@ int find_used_partitions(PART_PRUNE_PARAM *ppar, SEL_ARG *key_tree)
 
   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;
-        }
+        //get a full range iterator
+        init_all_partitions_iterator(ppar->part_info, &ppar->part_iter);
       }
-
-      /* 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;
-        }
-      }
-      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 @@ int find_used_partitions(PART_PRUNE_PARAM *ppar, SEL_ARG *key_tree)
       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 @@ int find_used_partitions(PART_PRUNE_PARAM *ppar, SEL_ARG *key_tree)
           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 @@ int find_used_partitions(PART_PRUNE_PARAM *ppar, SEL_ARG *key_tree)
         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 @@ int find_used_partitions(PART_PRUNE_PARAM *ppar, SEL_ARG *key_tree)
         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 @@ int find_used_partitions(PART_PRUNE_PARAM *ppar, SEL_ARG *key_tree)
 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 @@ pop_and_go_right:
     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 @@ static bool create_partition_index_description(PART_PRUNE_PARAM *ppar)
     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 @@ static bool create_partition_index_description(PART_PRUNE_PARAM *ppar)
       !(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 @@ static bool create_partition_index_description(PART_PRUNE_PARAM *ppar)
     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;
diff --git a/sql/sql_partition.cc b/sql/sql_partition.cc
index 498cd4e20e8..5e859761ace 100644
--- a/sql/sql_partition.cc
+++ b/sql/sql_partition.cc
@@ -91,6 +91,21 @@ uint32 get_partition_id_linear_hash_sub(partition_info *part_info);
 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 @@ static void set_up_partition_func_pointers(partition_info *part_info)
     }
   }
 }
-          
-        
+
+
 /*
   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 @@ bool fix_partition_func(THD *thd, const char *name, TABLE *table)
   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 @@ void make_used_partitions_str(partition_info *part_info, String *parts_str)
   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++))
@@ -3529,3 +3545,437 @@ void make_used_partitions_str(partition_info *part_info, String *parts_str)
   }
 }
 
+
+/****************************************************************************
+ * 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);
+}
+
diff --git a/sql/sql_select.cc b/sql/sql_select.cc
index d5a38b13a0e..2a32a6d354f 100644
--- a/sql/sql_select.cc
+++ b/sql/sql_select.cc
@@ -638,6 +638,11 @@ JOIN::optimize()
     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;