WL#1724 "Min/Max Optimization for Queries with Group By Clause"

- after-review changes
- merged with the source tree from 204-08-27


mysql-test/r/distinct.result:
  Different plans due to group-by optimization.
sql/ha_myisam.cc:
  More general interface to key_copy.
sql/handler.cc:
  More general interface to key_copy.
sql/item.cc:
  New method to collect all Item_field objects. Used by Item::walk.
sql/item.h:
  Several methods to collect different kinds of items from expression trees.
  Used by Item::walk.
sql/item_sum.cc:
  Added helper to collect Item_sum objects.
sql/item_sum.h:
  Methods to collect and test Item_sum objects.
sql/key.cc:
  More general interface to key_copy and key_restore.
sql/mysql_priv.h:
  More general interface to key_copy and key_restore.
sql/opt_range.cc:
  Complete implementaion of WL#1724 "Min/Max Optimization for Queries with Group By Clause".
sql/opt_range.h:
  Complete implementaion of WL#1724 "Min/Max Optimization for Queries with Group By Clause".
sql/opt_sum.cc:
  simple_pred is re-used in opt_range.cc
sql/sql_acl.cc:
  More general interface to key_copy and key_restore.
sql/sql_handler.cc:
  More general interface to key_copy.
sql/sql_insert.cc:
  More general interface to key_copy.
sql/sql_select.cc:
  Changes to hook the new QUICK_GROUP_MIN_MAX_SELECT due to two differences from all other
  quick selects:
  1)
  This quick select may be created (and used) even if there is no WHERE clause.
  Several places assumed that a QUICK_SELECT is constructed only if there is a WHERE clause,
  which had to be changed so that QUICK_GROUP_MIN_MAX can be used.
  2)
  Unlike all other quick selects, this QUICK_GROUP_MIN_MAX_SELECT operates for GROUP BY queries.
  Since for the caller the quick select already produces one result tuple per group, there is
  no need to call end_send_group, instead we have to call end_send as for a regular quick select.
sql/sql_select.h:
  simple_pred is re-used in opt_range.cc

1 files changed, 101 insertions, 5 deletions

diff --git a/sql/opt_range.h b/sql/opt_range.h
index 974ed409a87..19234f61ea2 100644
--- a/sql/opt_range.h
+++ b/sql/opt_range.h
@@ -146,7 +146,8 @@ public:
     QS_TYPE_RANGE_DESC = 2,
     QS_TYPE_FULLTEXT   = 3,
     QS_TYPE_ROR_INTERSECT = 4,
-    QS_TYPE_ROR_UNION = 5
+    QS_TYPE_ROR_UNION = 5,
+    QS_TYPE_GROUP_MIN_MAX = 6
   };
 
   /* Get type of this quick select - one of the QS_TYPE_* values */
@@ -278,14 +279,12 @@ public:
   int init();
   int get_next();
   void range_end();
-
+  int get_next_prefix(uint prefix_length, byte *cur_prefix);
   bool reverse_sorted() { return 0; }
   bool unique_key_range();
   int init_ror_merged_scan(bool reuse_handler);
   void save_last_pos()
-  {
-    file->position(record);
-  };
+  { file->position(record); }
   int get_type() { return QS_TYPE_RANGE; }
   void add_keys_and_lengths(String *key_names, String *used_lengths);
   void add_info_string(String *str);
@@ -518,6 +517,103 @@ private:
 };
 
 
+/*
+  Index scan for GROUP-BY queries with MIN/MAX aggregate functions.
+
+  This class provides a specialized index access method for GROUP-BY queries
+  of the forms:
+
+       SELECT A_1,...,A_k, [B_1,...,B_m], [MIN(C)], [MAX(C)]
+         FROM T
+        WHERE [RNG(A_1,...,A_p ; where p <= k)]
+         [AND EQ(B_1,...,B_m)]
+         [AND PC(C)]
+         [AND PA(A_i1,...,A_iq)]
+       GROUP BY A_1,...,A_k;
+
+    or
+
+       SELECT DISTINCT A_i1,...,A_ik
+         FROM T
+        WHERE [RNG(A_1,...,A_p ; where p <= k)]
+         [AND PA(A_i1,...,A_iq)];
+
+  where all selected fields are parts of the same index.
+  The class of queries that can be processed by this quick select is fully
+  specified in the description of get_best_trp_group_min_max() in opt_range.cc.
+
+  The get_next() method directly produces result tuples, thus obviating the
+  need to call end_send_group() because all grouping is already done inside
+  get_next().
+
+  Since one of the requirements is that all select fields are part of the same
+  index, this class produces only index keys, and not complete records.
+*/
+
+class QUICK_GROUP_MIN_MAX_SELECT : public QUICK_SELECT_I
+{
+private:
+  handler *file;         /* The handler used to get data. */
+  JOIN *join;            /* Descriptor of the current query */
+  KEY  *index_info;      /* The index chosen for data access */
+  byte *record;          /* Buffer where the next record is returned. */
+  byte *tmp_record;      /* Temporary storage for next_min(), next_max(). */
+  byte *group_prefix;    /* Key prefix consisting of the GROUP fields. */
+  uint group_prefix_len; /* Length of the group prefix. */
+  byte *last_prefix;     /* Prefix of the last group for detecting EOF. */
+  bool have_min;         /* Specify whether we are computing */
+  bool have_max;         /*   a MIN, a MAX, or both.         */
+  bool seen_first_key;   /* Denotes whether the first key was retrieved.*/
+  KEY_PART_INFO *min_max_arg_part; /* The keypart of the only argument field */
+                                   /* of all MIN/MAX functions.              */
+  uint min_max_arg_len;  /* The length of the MIN/MAX argument field */
+  byte *key_infix;       /* Infix of constants from equality predicates. */
+  uint key_infix_len;
+  DYNAMIC_ARRAY min_max_ranges; /* Array of range ptrs for the MIN/MAX field. */
+  uint real_prefix_len; /* Length of key prefix extended with key_infix. */
+  List<Item_sum> *min_functions;
+  List<Item_sum> *max_functions;
+  List_iterator<Item_sum> *min_functions_it;
+  List_iterator<Item_sum> *max_functions_it;
+public:
+  /*
+    The following two members are public to allow easy access from
+    TRP_GROUP_MIN_MAX::make_quick()
+  */
+  MEM_ROOT alloc; /* Memory pool for this and quick_prefix_select data. */
+  QUICK_RANGE_SELECT *quick_prefix_select;/* For retrieval of group prefixes. */
+private:
+  int  next_prefix();
+  int  next_min_in_range();
+  int  next_max_in_range();
+  int  next_min();
+  int  next_max();
+  void update_min_result();
+  void update_max_result();
+public:
+  QUICK_GROUP_MIN_MAX_SELECT(TABLE *table, JOIN *join, bool have_min,
+                             bool have_max, KEY_PART_INFO *min_max_arg_part,
+                             uint group_prefix_len, uint used_key_parts,
+                             KEY *index_info, uint use_index, double read_cost,
+                             ha_rows records, uint key_infix_len,
+                             byte *key_infix, MEM_ROOT *parent_alloc);
+  ~QUICK_GROUP_MIN_MAX_SELECT();
+  bool add_range(SEL_ARG *sel_range);
+  void update_key_stat();
+  bool alloc_buffers();
+  int init();
+  int reset();
+  int get_next();
+  bool reverse_sorted() { return false; }
+  bool unique_key_range() { return false; }
+  int get_type() { return QS_TYPE_GROUP_MIN_MAX; }
+  void add_keys_and_lengths(String *key_names, String *used_lengths);
+#ifndef DBUG_OFF
+  void dbug_dump(int indent, bool verbose);
+#endif
+};
+
+
 class QUICK_SELECT_DESC: public QUICK_RANGE_SELECT
 {
 public: