← Back to branch summary

~drizzle-trunk/drizzle/development

« back to all changes in this revision

Viewing changes to drizzled/optimizer/quick_group_min_max_select.h

  • Committer: Brian Aker
  • Date: 2009-12-18 00:52:41 UTC
  • mfrom: (1241.2.6 build)
  • Revision ID: brian@gaz-20091218005241-z3w0etb2x3otmwks
Merge of Padraig/Monty/Trond

Show diffs side-by-side

added added

removed removed

Lines of Context:
drizzled/optimizer/quick_group_min_max_select.h
 
1
/* -*- mode: c++; c-basic-offset: 2; indent-tabs-mode: nil; -*-
 
2
 *  vim:expandtab:shiftwidth=2:tabstop=2:smarttab:
 
3
 *
 
4
 *  Copyright (C) 2008-2009 Sun Microsystems
 
5
 *
 
6
 *  This program is free software; you can redistribute it and/or modify
 
7
 *  it under the terms of the GNU General Public License as published by
 
8
 *  the Free Software Foundation; version 2 of the License.
 
9
 *
 
10
 *  This program is distributed in the hope that it will be useful,
 
11
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 
12
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 
13
 *  GNU General Public License for more details.
 
14
 *
 
15
 *  You should have received a copy of the GNU General Public License
 
16
 *  along with this program; if not, write to the Free Software
 
17
 *  Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
 
18
 */
 
19
 
 
20
#ifndef DRIZZLED_OPTIMIZER_QUICK_GROUP_MIN_MAX_SELECT_H
 
21
#define DRIZZLED_OPTIMIZER_QUICK_GROUP_MIN_MAX_SELECT_H
 
22
 
 
23
#include "drizzled/optimizer/range.h"
 
24
 
 
25
namespace drizzled
 
26
{
 
27
 
 
28
namespace optimizer
 
29
{
 
30
 
 
31
/**
 
32
  Index scan for GROUP-BY queries with MIN/MAX aggregate functions.
 
33
 
 
34
  This class provides a specialized index access method for GROUP-BY queries
 
35
  of the forms:
 
36
 
 
37
       SELECT A_1,...,A_k, [B_1,...,B_m], [MIN(C)], [MAX(C)]
 
38
         FROM T
 
39
        WHERE [RNG(A_1,...,A_p ; where p <= k)]
 
40
         [AND EQ(B_1,...,B_m)]
 
41
         [AND PC(C)]
 
42
         [AND PA(A_i1,...,A_iq)]
 
43
       GROUP BY A_1,...,A_k;
 
44
 
 
45
    or
 
46
 
 
47
       SELECT DISTINCT A_i1,...,A_ik
 
48
         FROM T
 
49
        WHERE [RNG(A_1,...,A_p ; where p <= k)]
 
50
         [AND PA(A_i1,...,A_iq)];
 
51
 
 
52
  where all selected fields are parts of the same index.
 
53
  The class of queries that can be processed by this quick select is fully
 
54
  specified in the description of get_best_trp_group_min_max() in optimizer/range.cc.
 
55
 
 
56
  The get_next() method directly produces result tuples, thus obviating the
 
57
  need to call end_send_group() because all grouping is already done inside
 
58
  get_next().
 
59
 
 
60
  Since one of the requirements is that all select fields are part of the same
 
61
  index, this class produces only index keys, and not complete records.
 
62
*/
 
63
class QuickGroupMinMaxSelect : public QuickSelectInterface
 
64
{
 
65
 
 
66
private:
 
67
 
 
68
  Cursor *cursor; /**< The Cursor used to get data. */
 
69
  JOIN *join; /**< Descriptor of the current query */
 
70
  KEY *index_info; /**< The index chosen for data access */
 
71
  unsigned char *record; /**< Buffer where the next record is returned. */
 
72
  unsigned char *tmp_record; /**< Temporary storage for next_min(), next_max(). */
 
73
  unsigned char *group_prefix; /**< Key prefix consisting of the GROUP fields. */
 
74
  uint32_t group_prefix_len; /**< Length of the group prefix. */
 
75
  uint32_t group_key_parts; /**< A number of keyparts in the group prefix */
 
76
  unsigned char *last_prefix; /**< Prefix of the last group for detecting EOF. */
 
77
  bool have_min; /**< Specify whether we are computing */
 
78
  bool have_max; /**< a MIN, a MAX, or both. */
 
79
  bool seen_first_key; /**< Denotes whether the first key was retrieved.*/
 
80
  KEY_PART_INFO *min_max_arg_part; /** The keypart of the only argument field of all MIN/MAX functions. */
 
81
  uint32_t min_max_arg_len; /**< The length of the MIN/MAX argument field */
 
82
  unsigned char *key_infix; /**< Infix of constants from equality predicates. */
 
83
  uint32_t key_infix_len;
 
84
  DYNAMIC_ARRAY min_max_ranges; /**< Array of range ptrs for the MIN/MAX field. */
 
85
  uint32_t real_prefix_len; /**< Length of key prefix extended with key_infix. */
 
86
  uint32_t real_key_parts;  /**< A number of keyparts in the above value.      */
 
87
  List<Item_sum> *min_functions;
 
88
  List<Item_sum> *max_functions;
 
89
  List_iterator<Item_sum> *min_functions_it;
 
90
  List_iterator<Item_sum> *max_functions_it;
 
91
 
 
92
public:
 
93
 
 
94
  /*
 
95
    The following two members are public to allow easy access from
 
96
    TRP_GROUP_MIN_MAX::make_quick()
 
97
  */
 
98
  MEM_ROOT alloc; /**< Memory pool for this and quick_prefix_select data. */
 
99
  QuickRangeSelect *quick_prefix_select; /**< For retrieval of group prefixes. */
 
100
 
 
101
private:
 
102
 
 
103
  /**
 
104
   * Determine the prefix of the next group.
 
105
   *
 
106
   * SYNOPSIS
 
107
   * QuickGroupMinMaxSelect::next_prefix()
 
108
   *
 
109
   * DESCRIPTION
 
110
   * Determine the prefix of the next group that satisfies the query conditions.
 
111
   * If there is a range condition referencing the group attributes, use a
 
112
   * QuickRangeSelect object to retrieve the *first* key that satisfies the
 
113
   * condition. If there is a key infix of constants, append this infix
 
114
   * immediately after the group attributes. The possibly extended prefix is
 
115
   * stored in this->group_prefix. The first key of the found group is stored in
 
116
   * this->record, on which relies this->next_min().
 
117
   *
 
118
   * RETURN
 
119
   * @retval 0                    on success
 
120
   * @retval HA_ERR_KEY_NOT_FOUND if there is no key with the formed prefix
 
121
   * @retval HA_ERR_END_OF_FILE   if there are no more keys
 
122
   * @retval other                if some error occurred
 
123
   */
 
124
  int next_prefix();
 
125
 
 
126
  /**
 
127
   * Find the minimal key in a group that satisfies some range conditions for the
 
128
   * min/max argument field.
 
129
   *
 
130
   * SYNOPSIS
 
131
   * QuickGroupMinMaxSelect::next_min_in_range()
 
132
   *
 
133
   * DESCRIPTION
 
134
   * Given the sequence of ranges min_max_ranges, find the minimal key that is
 
135
   * in the left-most possible range. If there is no such key, then the current
 
136
   * group does not have a MIN key that satisfies the WHERE clause. If a key is
 
137
   * found, its value is stored in this->record.
 
138
   *
 
139
   * RETURN
 
140
   * @retval 0                    on success
 
141
   * @retval HA_ERR_KEY_NOT_FOUND if there is no key with the given prefix in any of the ranges
 
142
   * @retval HA_ERR_END_OF_FILE   - "" -
 
143
   * @retval other                if some error
 
144
   */
 
145
  int next_min_in_range();
 
146
 
 
147
  /**
 
148
   * Find the maximal key in a group that satisfies some range conditions for the
 
149
   * min/max argument field.
 
150
   *
 
151
   * SYNOPSIS
 
152
   * QuickGroupMinMaxSelect::next_max_in_range()
 
153
   *
 
154
   * DESCRIPTION
 
155
   * Given the sequence of ranges min_max_ranges, find the maximal key that is
 
156
   * in the right-most possible range. If there is no such key, then the current
 
157
   * group does not have a MAX key that satisfies the WHERE clause. If a key is
 
158
   * found, its value is stored in this->record.
 
159
   *
 
160
   * RETURN
 
161
   * @retval 0                    on success
 
162
   * @retval HA_ERR_KEY_NOT_FOUND if there is no key with the given prefix in any of the ranges
 
163
   * @retval HA_ERR_END_OF_FILE   - "" -
 
164
   * @retval other                if some error
 
165
   */
 
166
  int next_max_in_range();
 
167
 
 
168
  /**
 
169
   * Retrieve the minimal key in the next group.
 
170
   *
 
171
   * SYNOPSIS
 
172
   * QuickGroupMinMaxSelect::next_min()
 
173
   *
 
174
   * DESCRIPTION
 
175
   * Find the minimal key within this group such that the key satisfies the query
 
176
   * conditions and NULL semantics. The found key is loaded into this->record.
 
177
   *
 
178
   * IMPLEMENTATION
 
179
   * Depending on the values of min_max_ranges.elements, key_infix_len, and
 
180
   * whether there is a  NULL in the MIN field, this function may directly
 
181
   * return without any data access. In this case we use the key loaded into
 
182
   * this->record by the call to this->next_prefix() just before this call.
 
183
   *
 
184
   * RETURN
 
185
   * @retval 0                    on success
 
186
   * @retval HA_ERR_KEY_NOT_FOUND if no MIN key was found that fulfills all conditions.
 
187
   * @retval HA_ERR_END_OF_FILE   - "" -
 
188
   * @retval other                if some error occurred
 
189
   */
 
190
  int next_min();
 
191
 
 
192
  /**
 
193
   * Retrieve the maximal key in the next group.
 
194
   *
 
195
   * SYNOPSIS
 
196
   * QuickGroupMinMaxSelect::next_max()
 
197
   *
 
198
   * DESCRIPTION
 
199
   * Lookup the maximal key of the group, and store it into this->record.
 
200
   *
 
201
   * RETURN
 
202
   * @retval 0                    on success
 
203
   * @retval HA_ERR_KEY_NOT_FOUND if no MAX key was found that fulfills all conditions.
 
204
   * @retval HA_ERR_END_OF_FILE  - "" -
 
205
   * @retval other                if some error occurred
 
206
   */
 
207
  int next_max();
 
208
 
 
209
  /**
 
210
   * Update all MIN function results with the newly found value.
 
211
   *
 
212
   * SYNOPSIS
 
213
   * QuickGroupMinMaxSelect::update_min_result()
 
214
   *
 
215
   * DESCRIPTION
 
216
   * The method iterates through all MIN functions and updates the result value
 
217
   * of each function by calling Item_sum::reset(), which in turn picks the new
 
218
   * result value from this->head->record[0], previously updated by
 
219
   * next_min(). The updated value is stored in a member variable of each of the
 
220
   * Item_sum objects, depending on the value type.
 
221
   *
 
222
   * IMPLEMENTATION
 
223
   * The update must be done separately for MIN and MAX, immediately after
 
224
   * next_min() was called and before next_max() is called, because both MIN and
 
225
   * MAX take their result value from the same buffer this->head->record[0]
 
226
   * (i.e.  this->record).
 
227
   *
 
228
   * RETURN
 
229
   * None
 
230
   */
 
231
  void update_min_result();
 
232
 
 
233
  /**
 
234
   * Update all MAX function results with the newly found value.
 
235
   *
 
236
   * SYNOPSIS
 
237
   * QuickGroupMinMaxSelect::update_max_result()
 
238
   *
 
239
   * DESCRIPTION
 
240
   * The method iterates through all MAX functions and updates the result value
 
241
   * of each function by calling Item_sum::reset(), which in turn picks the new
 
242
   * result value from this->head->record[0], previously updated by
 
243
   * next_max(). The updated value is stored in a member variable of each of the
 
244
   * Item_sum objects, depending on the value type.
 
245
   *
 
246
   * IMPLEMENTATION
 
247
   * The update must be done separately for MIN and MAX, immediately after
 
248
   * next_max() was called, because both MIN and MAX take their result value
 
249
   * from the same buffer this->head->record[0] (i.e.  this->record).
 
250
   *
 
251
   * RETURN
 
252
   * None
 
253
   */
 
254
  void update_max_result();
 
255
 
 
256
public:
 
257
 
 
258
  /*
 
259
     Construct new quick select for group queries with min/max.
 
260
 
 
261
     SYNOPSIS
 
262
     QuickGroupMinMaxSelect::QuickGroupMinMaxSelect()
 
263
     table             The table being accessed
 
264
     join              Descriptor of the current query
 
265
     have_min          true if the query selects a MIN function
 
266
     have_max          true if the query selects a MAX function
 
267
     min_max_arg_part  The only argument field of all MIN/MAX functions
 
268
     group_prefix_len  Length of all key parts in the group prefix
 
269
     prefix_key_parts  All key parts in the group prefix
 
270
     index_info        The index chosen for data access
 
271
     use_index         The id of index_info
 
272
     read_cost         Cost of this access method
 
273
     records           Number of records returned
 
274
     key_infix_len     Length of the key infix appended to the group prefix
 
275
     key_infix         Infix of constants from equality predicates
 
276
     parent_alloc      Memory pool for this and quick_prefix_select data
 
277
 
 
278
     RETURN
 
279
     None
 
280
   */
 
281
  QuickGroupMinMaxSelect(Table *table, 
 
282
                         JOIN *join, 
 
283
                         bool have_min,
 
284
                         bool have_max, 
 
285
                         KEY_PART_INFO *min_max_arg_part,
 
286
                         uint32_t group_prefix_len, 
 
287
                         uint32_t group_key_parts,
 
288
                         uint32_t used_key_parts, 
 
289
                         KEY *index_info,
 
290
                         uint use_index, 
 
291
                         double read_cost, 
 
292
                         ha_rows records,
 
293
                         uint key_infix_len, 
 
294
                         unsigned char *key_infix,
 
295
                         MEM_ROOT *parent_alloc);
 
296
 
 
297
  ~QuickGroupMinMaxSelect();
 
298
 
 
299
  /**
 
300
   * Eventually create and add a new quick range object.
 
301
   *
 
302
   * SYNOPSIS
 
303
   * QuickGroupMinMaxSelect::add_range()
 
304
   * @param[in] sel_range  Range object from which a new object is created
 
305
   *
 
306
   * NOTES
 
307
   * Construct a new QuickRange object from a SEL_ARG object, and
 
308
   * add it to the array min_max_ranges. If sel_arg is an infinite
 
309
   * range, e.g. (x < 5 or x > 4), then skip it and do not construct
 
310
   * a quick range.
 
311
   *
 
312
   * RETURN
 
313
   * @retval false on success
 
314
   * @retval true  otherwise
 
315
   */
 
316
  bool add_range(SEL_ARG *sel_range);
 
317
 
 
318
  /**
 
319
   * Determine the total number and length of the keys that will be used for
 
320
   * index lookup.
 
321
   *
 
322
   * SYNOPSIS
 
323
   * QuickGroupMinMaxSelect::update_key_stat()
 
324
   *
 
325
   * DESCRIPTION
 
326
   * The total length of the keys used for index lookup depends on whether
 
327
   * there are any predicates referencing the min/max argument, and/or if
 
328
   * the min/max argument field can be NULL.
 
329
   * This function does an optimistic analysis whether the search key might
 
330
   * be extended by a constant for the min/max keypart. It is 'optimistic'
 
331
   * because during actual execution it may happen that a particular range
 
332
   * is skipped, and then a shorter key will be used. However this is data
 
333
   * dependent and can't be easily estimated here.
 
334
   *
 
335
   * RETURN
 
336
   * None
 
337
   */
 
338
  void update_key_stat();
 
339
 
 
340
  /**
 
341
   * Opens the ranges if there are more conditions in quick_prefix_select than
 
342
   * the ones used for jumping through the prefixes.
 
343
   *
 
344
   * SYNOPSIS
 
345
   * QuickGroupMinMaxSelect::adjust_prefix_ranges()
 
346
   *
 
347
   * NOTES
 
348
   * quick_prefix_select is made over the conditions on the whole key.
 
349
   * It defines a number of ranges of length x.
 
350
   * However when jumping through the prefixes we use only the the first
 
351
   * few most significant keyparts in the range key. However if there
 
352
   * are more keyparts to follow the ones we are using we must make the
 
353
   * condition on the key inclusive (because x < "ab" means
 
354
   * x[0] < 'a' OR (x[0] == 'a' AND x[1] < 'b').
 
355
   * To achive the above we must turn off the NEAR_MIN/NEAR_MAX
 
356
   */
 
357
  void adjust_prefix_ranges();
 
358
 
 
359
  bool alloc_buffers();
 
360
 
 
361
  /**
 
362
   * Do post-constructor initialization.
 
363
   *
 
364
   * SYNOPSIS
 
365
   * QuickGroupMinMaxSelect::init()
 
366
   *
 
367
   * DESCRIPTION
 
368
   * The method performs initialization that cannot be done in the constructor
 
369
   * such as memory allocations that may fail. It allocates memory for the
 
370
   * group prefix and inifix buffers, and for the lists of MIN/MAX item to be
 
371
   * updated during execution.
 
372
   *
 
373
   * RETURN
 
374
   * @retval 0      OK
 
375
   * @retval other  Error code
 
376
   */
 
377
  int init();
 
378
 
 
379
  /**
 
380
   * Initialize a quick group min/max select for key retrieval.
 
381
   *
 
382
   * SYNOPSIS
 
383
   * QuickGroupMinMaxSelect::reset()
 
384
   *
 
385
   * DESCRIPTION
 
386
   * Initialize the index chosen for access and find and store the prefix
 
387
   * of the last group. The method is expensive since it performs disk access.
 
388
   *
 
389
   * RETURN
 
390
   * @retval 0      OK
 
391
   * @retval other  Error code
 
392
   */
 
393
  int reset();
 
394
 
 
395
  /**
 
396
   * Get the next key containing the MIN and/or MAX key for the next group.
 
397
   *
 
398
   * SYNOPSIS
 
399
   * QuickGroupMinMaxSelect::get_next()
 
400
   *
 
401
   * DESCRIPTION
 
402
   * The method finds the next subsequent group of records that satisfies the
 
403
   * query conditions and finds the keys that contain the MIN/MAX values for
 
404
   * the key part referenced by the MIN/MAX function(s). Once a group and its
 
405
   * MIN/MAX values are found, store these values in the Item_sum objects for
 
406
   * the MIN/MAX functions. The rest of the values in the result row are stored
 
407
   * in the Item_field::result_field of each select field. If the query does
 
408
   * not contain MIN and/or MAX functions, then the function only finds the
 
409
   * group prefix, which is a query answer itself.
 
410
   *
 
411
   * NOTES
 
412
   * If both MIN and MAX are computed, then we use the fact that if there is
 
413
   * no MIN key, there can't be a MAX key as well, so we can skip looking
 
414
   * for a MAX key in this case.
 
415
   *
 
416
   * RETURN
 
417
   * @retval 0                  on success
 
418
   * @retval HA_ERR_END_OF_FILE if returned all keys
 
419
   * @retval other              if some error occurred
 
420
   */
 
421
  int get_next();
 
422
 
 
423
  bool reverse_sorted() const
 
424
  {
 
425
    return false;
 
426
  }
 
427
 
 
428
  bool unique_key_range() const
 
429
  {
 
430
    return false;
 
431
  }
 
432
 
 
433
  int get_type() const
 
434
  {
 
435
    return QS_TYPE_GROUP_MIN_MAX;
 
436
  }
 
437
 
 
438
  /**
 
439
   * Append comma-separated list of keys this quick select uses to key_names;
 
440
   * append comma-separated list of corresponding used lengths to used_lengths.
 
441
   *
 
442
   * SYNOPSIS
 
443
   * QuickGroupMinMaxSelect::add_keys_and_lengths()
 
444
   * @param[out] key_names Names of used indexes
 
445
   * @param[out] used_lengths Corresponding lengths of the index names
 
446
   *
 
447
   * DESCRIPTION
 
448
   * This method is used by select_describe to extract the names of the
 
449
   * indexes used by a quick select.
 
450
   */
 
451
  void add_keys_and_lengths(String *key_names, String *used_lengths);
 
452
 
 
453
};
 
454
 
 
455
 
 
456
} /* namespace optimizer */
 
457
 
 
458
} /* namespace drizzled */
 
459
 
 
460
#endif /* DRIZZLED_OPTIMIZER_QUICK_GROUP_MIN_MAX_SELECT_H */