← 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: Padraig O'Sullivan
  • Date: 2009-12-11 17:28:06 UTC
  • mto: (1241.2.6 build)
  • mto: This revision was merged to the branch mainline in revision 1243.
  • Revision ID: osullivan.padraig@gmail.com-20091211172806-7cn8hla63d42wofu
Corrected some style issues in the QuickGroupMinMaxSelect class.

Show diffs side-by-side

added added

removed removed

Lines of Context:
drizzled/optimizer/quick_group_min_max_select.h
60
60
  Since one of the requirements is that all select fields are part of the same
61
61
  index, this class produces only index keys, and not complete records.
62
62
*/
63
 
class QUICK_GROUP_MIN_MAX_SELECT : public QuickSelectInterface
 
63
class QuickGroupMinMaxSelect : public QuickSelectInterface
64
64
{
 
65
 
65
66
private:
 
67
 
66
68
  Cursor *cursor; /**< The Cursor used to get data. */
67
69
  JOIN *join; /**< Descriptor of the current query */
68
70
  KEY *index_info; /**< The index chosen for data access */
86
88
  List<Item_sum> *max_functions;
87
89
  List_iterator<Item_sum> *min_functions_it;
88
90
  List_iterator<Item_sum> *max_functions_it;
 
91
 
89
92
public:
 
93
 
90
94
  /*
91
95
    The following two members are public to allow easy access from
92
96
    TRP_GROUP_MIN_MAX::make_quick()
93
97
  */
94
98
  MEM_ROOT alloc; /**< Memory pool for this and quick_prefix_select data. */
95
99
  QuickRangeSelect *quick_prefix_select; /**< For retrieval of group prefixes. */
 
100
 
96
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
   */
97
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
   */
98
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
   */
99
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
   */
100
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
   */
101
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
   */
102
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
   */
103
254
  void update_max_result();
 
255
 
104
256
public:
105
 
  QUICK_GROUP_MIN_MAX_SELECT(Table *table, JOIN *join, bool have_min,
106
 
                             bool have_max, KEY_PART_INFO *min_max_arg_part,
107
 
                             uint32_t group_prefix_len, uint32_t group_key_parts,
108
 
                             uint32_t used_key_parts, KEY *index_info, uint
109
 
                             use_index, double read_cost, ha_rows records, uint
110
 
                             key_infix_len, unsigned char *key_infix, MEM_ROOT
111
 
                             *parent_alloc);
112
 
  ~QUICK_GROUP_MIN_MAX_SELECT();
 
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
   */
113
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
   */
114
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
   */
115
357
  void adjust_prefix_ranges();
 
358
 
116
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
   */
117
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
   */
118
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
   */
119
421
  int get_next();
120
422
 
121
423
  bool reverse_sorted() const
133
435
    return QS_TYPE_GROUP_MIN_MAX;
134
436
  }
135
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
   */
136
451
  void add_keys_and_lengths(String *key_names, String *used_lengths);
 
452
 
137
453
};
138
454
 
139
455