Bug#13694811: THE OPTIMIZER WRONGLY USES THE FIRST INNODB

                           PARTITION STATISTICS

Problem was the fix for bug#11756867; It always used the first
partitions, and stopped after it checked 10 [sub]partitions.
(or until it found a partition which would contain a match).

This results in bad statistics for tables where the first 10 partitions
don't represent the majority of the data (like when the first 10
partitions only contained a few rows in total).

The solution was to take statisics from the partitions containing
the most rows instead:

Added an array of partition ids which is sorted by number of records
in descending order.

this array is used in records_in_range to cover as many records as
possible in as few calls as possible.

Also changed the limit of how many partitions to use for the statistics
from a static max of 10 partitions, into a dynamic model:
Maximum number of partitions is now log2(total number of partitions)
taken from the ordered array.
It will continue calling partitions records_in_range until it has 
checked:
(total rows in matching partitions) * (maximum number of partitions)
/ (number of used partitions)

Also reverted the changes for ha_partition::scan_time() and
ha_partition::estimate_rows_upper_bound() to before
the fix of  bug#11756867. Since they are not as slow as
records_in_range.

1 files changed, 12 insertions, 12 deletions

diff --git a/sql/ha_partition.h b/sql/ha_partition.h
index 46e2f447a47..49131518f8c 100644
--- a/sql/ha_partition.h
+++ b/sql/ha_partition.h
@@ -199,6 +199,12 @@ private:
   ha_rows   m_bulk_inserted_rows;
   /** used for prediction of start_bulk_insert rows */
   enum_monotonicity_info m_part_func_monotonicity_info;
+  /** Sorted array of partition ids in descending order of number of rows. */
+  uint32 *m_part_ids_sorted_by_num_of_records;
+  /* Compare function for my_qsort2, for reversed order. */
+  static int compare_number_of_records(ha_partition *me,
+                                       const uint32 *a,
+                                       const uint32 *b);
 public:
   handler *clone(const char *name, MEM_ROOT *mem_root);
   virtual void set_part_info(partition_info *part_info)
@@ -219,9 +225,9 @@ public:
   */
     ha_partition(handlerton *hton, TABLE_SHARE * table);
     ha_partition(handlerton *hton, partition_info * part_info);
-    ha_partition(handlerton *hton, TABLE_SHARE *share,

-                 partition_info *part_info_arg,

-                 ha_partition *clone_arg,

+    ha_partition(handlerton *hton, TABLE_SHARE *share,
+                 partition_info *part_info_arg,
+                 ha_partition *clone_arg,
                  MEM_ROOT *clone_mem_root_arg);
    ~ha_partition();
   /*
@@ -582,15 +588,9 @@ public:
   */
 
 private:
-  /*
-    Helper function to get the minimum number of partitions to use for
-    the optimizer hints/cost calls.
-  */
-  void partitions_optimizer_call_preparations(uint *num_used_parts,
-                                              uint *check_min_num,
-                                              uint *first);
-  ha_rows estimate_rows(bool is_records_in_range, uint inx,
-                        key_range *min_key, key_range *max_key);
+  /* Helper functions for optimizer hints. */
+  ha_rows min_rows_for_estimate();
+  uint get_biggest_used_partition(uint *part_index);
 public:
 
   /*