← 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.cc

Merge Padraig

Show diffs side-by-side

added added

removed removed

Lines of Context:
drizzled/optimizer/quick_group_min_max_select.cc
 
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
#include "drizzled/server_includes.h"
 
21
#include "drizzled/session.h"
 
22
#include "drizzled/sql_select.h"
 
23
#include "drizzled/join.h"
 
24
#include "drizzled/optimizer/range.h"
 
25
#include "drizzled/optimizer/quick_group_min_max_select.h"
 
26
#include "drizzled/optimizer/quick_range.h"
 
27
#include "drizzled/optimizer/quick_range_select.h"
 
28
#include "drizzled/optimizer/sel_arg.h"
 
29
 
 
30
using namespace std;
 
31
using namespace drizzled;
 
32
 
 
33
 
 
34
optimizer::QuickGroupMinMaxSelect::
 
35
QuickGroupMinMaxSelect(Table *table,
 
36
                       JOIN *join_arg,
 
37
                       bool have_min_arg,
 
38
                       bool have_max_arg,
 
39
                       KEY_PART_INFO *min_max_arg_part_arg,
 
40
                       uint32_t group_prefix_len_arg,
 
41
                       uint32_t group_key_parts_arg,
 
42
                       uint32_t used_key_parts_arg,
 
43
                       KEY *index_info_arg,
 
44
                       uint32_t use_index,
 
45
                       double read_cost_arg,
 
46
                       ha_rows records_arg,
 
47
                       uint32_t key_infix_len_arg,
 
48
                       unsigned char *key_infix_arg,
 
49
                       MEM_ROOT *parent_alloc)
 
50
  :
 
51
    join(join_arg),
 
52
    index_info(index_info_arg),
 
53
    group_prefix_len(group_prefix_len_arg),
 
54
    group_key_parts(group_key_parts_arg),
 
55
    have_min(have_min_arg),
 
56
    have_max(have_max_arg),
 
57
    seen_first_key(false),
 
58
    min_max_arg_part(min_max_arg_part_arg),
 
59
    key_infix(key_infix_arg),
 
60
    key_infix_len(key_infix_len_arg),
 
61
    min_functions_it(NULL),
 
62
    max_functions_it(NULL)
 
63
{
 
64
  head= table;
 
65
  cursor= head->cursor;
 
66
  index= use_index;
 
67
  record= head->record[0];
 
68
  tmp_record= head->record[1];
 
69
  read_time= read_cost_arg;
 
70
  records= records_arg;
 
71
  used_key_parts= used_key_parts_arg;
 
72
  real_key_parts= used_key_parts_arg;
 
73
  real_prefix_len= group_prefix_len + key_infix_len;
 
74
  group_prefix= NULL;
 
75
  min_max_arg_len= min_max_arg_part ? min_max_arg_part->store_length : 0;
 
76
 
 
77
  /*
 
78
    We can't have parent_alloc set as the init function can't handle this case
 
79
    yet.
 
80
  */
 
81
  assert(! parent_alloc);
 
82
  if (! parent_alloc)
 
83
  {
 
84
    init_sql_alloc(&alloc, join->session->variables.range_alloc_block_size, 0);
 
85
    join->session->mem_root= &alloc;
 
86
  }
 
87
  else
 
88
    memset(&alloc, 0, sizeof(MEM_ROOT));  // ensure that it's not used
 
89
}
 
90
 
 
91
 
 
92
int optimizer::QuickGroupMinMaxSelect::init()
 
93
{
 
94
  if (group_prefix) /* Already initialized. */
 
95
    return 0;
 
96
 
 
97
  if (! (last_prefix= (unsigned char*) alloc_root(&alloc, group_prefix_len)))
 
98
      return 1;
 
99
  /*
 
100
    We may use group_prefix to store keys with all select fields, so allocate
 
101
    enough space for it.
 
102
  */
 
103
  if (! (group_prefix= (unsigned char*) alloc_root(&alloc,
 
104
                                                   real_prefix_len + min_max_arg_len)))
 
105
    return 1;
 
106
 
 
107
  if (key_infix_len > 0)
 
108
  {
 
109
    /*
 
110
      The memory location pointed to by key_infix will be deleted soon, so
 
111
      allocate a new buffer and copy the key_infix into it.
 
112
    */
 
113
    unsigned char *tmp_key_infix= (unsigned char*) alloc_root(&alloc, key_infix_len);
 
114
    if (! tmp_key_infix)
 
115
      return 1;
 
116
    memcpy(tmp_key_infix, this->key_infix, key_infix_len);
 
117
    this->key_infix= tmp_key_infix;
 
118
  }
 
119
 
 
120
  if (min_max_arg_part)
 
121
  {
 
122
    if (my_init_dynamic_array(&min_max_ranges, sizeof(optimizer::QuickRange*), 16, 16))
 
123
      return 1;
 
124
 
 
125
    if (have_min)
 
126
    {
 
127
      if (! (min_functions= new List<Item_sum>))
 
128
        return 1;
 
129
    }
 
130
    else
 
131
      min_functions= NULL;
 
132
    if (have_max)
 
133
    {
 
134
      if (! (max_functions= new List<Item_sum>))
 
135
        return 1;
 
136
    }
 
137
    else
 
138
      max_functions= NULL;
 
139
 
 
140
    Item_sum *min_max_item= NULL;
 
141
    Item_sum **func_ptr= join->sum_funcs;
 
142
    while ((min_max_item= *(func_ptr++)))
 
143
    {
 
144
      if (have_min && (min_max_item->sum_func() == Item_sum::MIN_FUNC))
 
145
        min_functions->push_back(min_max_item);
 
146
      else if (have_max && (min_max_item->sum_func() == Item_sum::MAX_FUNC))
 
147
        max_functions->push_back(min_max_item);
 
148
    }
 
149
 
 
150
    if (have_min)
 
151
    {
 
152
      if (! (min_functions_it= new List_iterator<Item_sum>(*min_functions)))
 
153
        return 1;
 
154
    }
 
155
 
 
156
    if (have_max)
 
157
    {
 
158
      if (! (max_functions_it= new List_iterator<Item_sum>(*max_functions)))
 
159
        return 1;
 
160
    }
 
161
  }
 
162
  else
 
163
    min_max_ranges.elements= 0;
 
164
 
 
165
  return 0;
 
166
}
 
167
 
 
168
 
 
169
optimizer::QuickGroupMinMaxSelect::~QuickGroupMinMaxSelect()
 
170
{
 
171
  if (cursor->inited != Cursor::NONE)
 
172
  {
 
173
    cursor->ha_index_end();
 
174
  }
 
175
  if (min_max_arg_part)
 
176
  {
 
177
    delete_dynamic(&min_max_ranges);
 
178
  }
 
179
  free_root(&alloc,MYF(0));
 
180
  delete min_functions_it;
 
181
  delete max_functions_it;
 
182
  delete quick_prefix_select;
 
183
}
 
184
 
 
185
 
 
186
bool optimizer::QuickGroupMinMaxSelect::add_range(optimizer::SEL_ARG *sel_range)
 
187
{
 
188
  optimizer::QuickRange *range= NULL;
 
189
  uint32_t range_flag= sel_range->min_flag | sel_range->max_flag;
 
190
 
 
191
  /* Skip (-inf,+inf) ranges, e.g. (x < 5 or x > 4). */
 
192
  if ((range_flag & NO_MIN_RANGE) && (range_flag & NO_MAX_RANGE))
 
193
    return false;
 
194
 
 
195
  if (! (sel_range->min_flag & NO_MIN_RANGE) &&
 
196
      ! (sel_range->max_flag & NO_MAX_RANGE))
 
197
  {
 
198
    if (sel_range->maybe_null &&
 
199
        sel_range->min_value[0] && sel_range->max_value[0])
 
200
      range_flag|= NULL_RANGE; /* IS NULL condition */
 
201
    else if (memcmp(sel_range->min_value, sel_range->max_value,
 
202
                    min_max_arg_len) == 0)
 
203
      range_flag|= EQ_RANGE;  /* equality condition */
 
204
  }
 
205
  range= new optimizer::QuickRange(sel_range->min_value,
 
206
                                   min_max_arg_len,
 
207
                                   make_keypart_map(sel_range->part),
 
208
                                   sel_range->max_value,
 
209
                                   min_max_arg_len,
 
210
                                   make_keypart_map(sel_range->part),
 
211
                                   range_flag);
 
212
  if (! range)
 
213
    return true;
 
214
  if (insert_dynamic(&min_max_ranges, (unsigned char*)&range))
 
215
    return true;
 
216
  return false;
 
217
}
 
218
 
 
219
 
 
220
void optimizer::QuickGroupMinMaxSelect::adjust_prefix_ranges()
 
221
{
 
222
  if (quick_prefix_select &&
 
223
      group_prefix_len < quick_prefix_select->max_used_key_length)
 
224
  {
 
225
    DYNAMIC_ARRAY *arr= NULL;
 
226
    uint32_t inx;
 
227
 
 
228
    for (inx= 0, arr= &quick_prefix_select->ranges; inx < arr->elements; inx++)
 
229
    {
 
230
      optimizer::QuickRange *range= NULL;
 
231
 
 
232
      get_dynamic(arr, (unsigned char*)&range, inx);
 
233
      range->flag &= ~(NEAR_MIN | NEAR_MAX);
 
234
    }
 
235
  }
 
236
}
 
237
 
 
238
 
 
239
void optimizer::QuickGroupMinMaxSelect::update_key_stat()
 
240
{
 
241
  max_used_key_length= real_prefix_len;
 
242
  if (min_max_ranges.elements > 0)
 
243
  {
 
244
    optimizer::QuickRange *cur_range= NULL;
 
245
    if (have_min)
 
246
    { /* Check if the right-most range has a lower boundary. */
 
247
      get_dynamic(&min_max_ranges,
 
248
                  (unsigned char*) &cur_range,
 
249
                  min_max_ranges.elements - 1);
 
250
      if (! (cur_range->flag & NO_MIN_RANGE))
 
251
      {
 
252
        max_used_key_length+= min_max_arg_len;
 
253
        used_key_parts++;
 
254
        return;
 
255
      }
 
256
    }
 
257
    if (have_max)
 
258
    { /* Check if the left-most range has an upper boundary. */
 
259
      get_dynamic(&min_max_ranges, (unsigned char*)&cur_range, 0);
 
260
      if (! (cur_range->flag & NO_MAX_RANGE))
 
261
      {
 
262
        max_used_key_length+= min_max_arg_len;
 
263
        used_key_parts++;
 
264
        return;
 
265
      }
 
266
    }
 
267
  }
 
268
  else if (have_min && min_max_arg_part &&
 
269
           min_max_arg_part->field->real_maybe_null())
 
270
  {
 
271
    /*
 
272
      If a MIN/MAX argument value is NULL, we can quickly determine
 
273
      that we're in the beginning of the next group, because NULLs
 
274
      are always < any other value. This allows us to quickly
 
275
      determine the end of the current group and jump to the next
 
276
      group (see next_min()) and thus effectively increases the
 
277
      usable key length.
 
278
    */
 
279
    max_used_key_length+= min_max_arg_len;
 
280
    used_key_parts++;
 
281
  }
 
282
}
 
283
 
 
284
 
 
285
int optimizer::QuickGroupMinMaxSelect::reset(void)
 
286
{
 
287
  int result;
 
288
 
 
289
  cursor->extra(HA_EXTRA_KEYREAD); /* We need only the key attributes */
 
290
  if ((result= cursor->ha_index_init(index,1)))
 
291
    return result;
 
292
  if (quick_prefix_select && quick_prefix_select->reset())
 
293
    return 0;
 
294
  result= cursor->index_last(record);
 
295
  if (result == HA_ERR_END_OF_FILE)
 
296
    return 0;
 
297
  /* Save the prefix of the last group. */
 
298
  key_copy(last_prefix, record, index_info, group_prefix_len);
 
299
 
 
300
  return 0;
 
301
}
 
302
 
 
303
 
 
304
int optimizer::QuickGroupMinMaxSelect::get_next()
 
305
{
 
306
  int min_res= 0;
 
307
  int max_res= 0;
 
308
  int result= 0;
 
309
  int is_last_prefix= 0;
 
310
 
 
311
  /*
 
312
    Loop until a group is found that satisfies all query conditions or the last
 
313
    group is reached.
 
314
  */
 
315
  do
 
316
  {
 
317
    result= next_prefix();
 
318
    /*
 
319
      Check if this is the last group prefix. Notice that at this point
 
320
      this->record contains the current prefix in record format.
 
321
    */
 
322
    if (! result)
 
323
    {
 
324
      is_last_prefix= key_cmp(index_info->key_part, last_prefix,
 
325
                              group_prefix_len);
 
326
      assert(is_last_prefix <= 0);
 
327
    }
 
328
    else
 
329
    {
 
330
      if (result == HA_ERR_KEY_NOT_FOUND)
 
331
        continue;
 
332
      break;
 
333
    }
 
334
 
 
335
    if (have_min)
 
336
    {
 
337
      min_res= next_min();
 
338
      if (min_res == 0)
 
339
        update_min_result();
 
340
    }
 
341
    /* If there is no MIN in the group, there is no MAX either. */
 
342
    if ((have_max && !have_min) ||
 
343
        (have_max && have_min && (min_res == 0)))
 
344
    {
 
345
      max_res= next_max();
 
346
      if (max_res == 0)
 
347
        update_max_result();
 
348
      /* If a MIN was found, a MAX must have been found as well. */
 
349
      assert(((have_max && !have_min) ||
 
350
                  (have_max && have_min && (max_res == 0))));
 
351
    }
 
352
    /*
 
353
      If this is just a GROUP BY or DISTINCT without MIN or MAX and there
 
354
      are equality predicates for the key parts after the group, find the
 
355
      first sub-group with the extended prefix.
 
356
    */
 
357
    if (! have_min && ! have_max && key_infix_len > 0)
 
358
      result= cursor->index_read_map(record,
 
359
                                     group_prefix,
 
360
                                     make_prev_keypart_map(real_key_parts),
 
361
                                     HA_READ_KEY_EXACT);
 
362
 
 
363
    result= have_min ? min_res : have_max ? max_res : result;
 
364
  } while ((result == HA_ERR_KEY_NOT_FOUND || result == HA_ERR_END_OF_FILE) &&
 
365
           is_last_prefix != 0);
 
366
 
 
367
  if (result == 0)
 
368
  {
 
369
    /*
 
370
      Partially mimic the behavior of end_select_send. Copy the
 
371
      field data from Item_field::field into Item_field::result_field
 
372
      of each non-aggregated field (the group fields, and optionally
 
373
      other fields in non-ANSI SQL mode).
 
374
    */
 
375
    copy_fields(&join->tmp_table_param);
 
376
  }
 
377
  else if (result == HA_ERR_KEY_NOT_FOUND)
 
378
    result= HA_ERR_END_OF_FILE;
 
379
 
 
380
  return result;
 
381
}
 
382
 
 
383
 
 
384
int optimizer::QuickGroupMinMaxSelect::next_min()
 
385
{
 
386
  int result= 0;
 
387
 
 
388
  /* Find the MIN key using the eventually extended group prefix. */
 
389
  if (min_max_ranges.elements > 0)
 
390
  {
 
391
    if ((result= next_min_in_range()))
 
392
      return result;
 
393
  }
 
394
  else
 
395
  {
 
396
    /* Apply the constant equality conditions to the non-group select fields */
 
397
    if (key_infix_len > 0)
 
398
    {
 
399
      if ((result= cursor->index_read_map(record,
 
400
                                          group_prefix,
 
401
                                          make_prev_keypart_map(real_key_parts),
 
402
                                          HA_READ_KEY_EXACT)))
 
403
        return result;
 
404
    }
 
405
 
 
406
    /*
 
407
      If the min/max argument field is NULL, skip subsequent rows in the same
 
408
      group with NULL in it. Notice that:
 
409
      - if the first row in a group doesn't have a NULL in the field, no row
 
410
      in the same group has (because NULL < any other value),
 
411
      - min_max_arg_part->field->ptr points to some place in 'record'.
 
412
    */
 
413
    if (min_max_arg_part && min_max_arg_part->field->is_null())
 
414
    {
 
415
      /* Find the first subsequent record without NULL in the MIN/MAX field. */
 
416
      key_copy(tmp_record, record, index_info, 0);
 
417
      result= cursor->index_read_map(record,
 
418
                                     tmp_record,
 
419
                                     make_keypart_map(real_key_parts),
 
420
                                     HA_READ_AFTER_KEY);
 
421
      /*
 
422
        Check if the new record belongs to the current group by comparing its
 
423
        prefix with the group's prefix. If it is from the next group, then the
 
424
        whole group has NULLs in the MIN/MAX field, so use the first record in
 
425
        the group as a result.
 
426
        TODO:
 
427
        It is possible to reuse this new record as the result candidate for the
 
428
        next call to next_min(), and to save one lookup in the next call. For
 
429
        this add a new member 'this->next_group_prefix'.
 
430
      */
 
431
      if (! result)
 
432
      {
 
433
        if (key_cmp(index_info->key_part, group_prefix, real_prefix_len))
 
434
          key_restore(record, tmp_record, index_info, 0);
 
435
      }
 
436
      else if (result == HA_ERR_KEY_NOT_FOUND || result == HA_ERR_END_OF_FILE)
 
437
        result= 0; /* There is a result in any case. */
 
438
    }
 
439
  }
 
440
 
 
441
  /*
 
442
    If the MIN attribute is non-nullable, this->record already contains the
 
443
    MIN key in the group, so just return.
 
444
  */
 
445
  return result;
 
446
}
 
447
 
 
448
 
 
449
int optimizer::QuickGroupMinMaxSelect::next_max()
 
450
{
 
451
  int result= 0;
 
452
 
 
453
  /* Get the last key in the (possibly extended) group. */
 
454
  if (min_max_ranges.elements > 0)
 
455
    result= next_max_in_range();
 
456
  else
 
457
    result= cursor->index_read_map(record,
 
458
                                   group_prefix,
 
459
                                   make_prev_keypart_map(real_key_parts),
 
460
                                   HA_READ_PREFIX_LAST);
 
461
  return result;
 
462
}
 
463
 
 
464
 
 
465
int optimizer::QuickGroupMinMaxSelect::next_prefix()
 
466
{
 
467
  int result= 0;
 
468
 
 
469
  if (quick_prefix_select)
 
470
  {
 
471
    unsigned char *cur_prefix= seen_first_key ? group_prefix : NULL;
 
472
    if ((result= quick_prefix_select->get_next_prefix(group_prefix_len,
 
473
                                                      make_prev_keypart_map(group_key_parts),
 
474
                                                      cur_prefix)))
 
475
      return result;
 
476
    seen_first_key= true;
 
477
  }
 
478
  else
 
479
  {
 
480
    if (! seen_first_key)
 
481
    {
 
482
      result= cursor->index_first(record);
 
483
      if (result)
 
484
        return result;
 
485
      seen_first_key= true;
 
486
    }
 
487
    else
 
488
    {
 
489
      /* Load the first key in this group into record. */
 
490
      result= cursor->index_read_map(record,
 
491
                                     group_prefix,
 
492
                                     make_prev_keypart_map(group_key_parts),
 
493
                                     HA_READ_AFTER_KEY);
 
494
      if (result)
 
495
        return result;
 
496
    }
 
497
  }
 
498
 
 
499
  /* Save the prefix of this group for subsequent calls. */
 
500
  key_copy(group_prefix, record, index_info, group_prefix_len);
 
501
  /* Append key_infix to group_prefix. */
 
502
  if (key_infix_len > 0)
 
503
    memcpy(group_prefix + group_prefix_len,
 
504
           key_infix,
 
505
           key_infix_len);
 
506
 
 
507
  return 0;
 
508
}
 
509
 
 
510
 
 
511
int optimizer::QuickGroupMinMaxSelect::next_min_in_range()
 
512
{
 
513
  ha_rkey_function find_flag;
 
514
  key_part_map keypart_map;
 
515
  optimizer::QuickRange *cur_range= NULL;
 
516
  bool found_null= false;
 
517
  int result= HA_ERR_KEY_NOT_FOUND;
 
518
  basic_string<unsigned char> max_key;
 
519
 
 
520
  max_key.reserve(real_prefix_len + min_max_arg_len);
 
521
 
 
522
  assert(min_max_ranges.elements > 0);
 
523
 
 
524
  for (uint32_t range_idx= 0; range_idx < min_max_ranges.elements; range_idx++)
 
525
  { /* Search from the left-most range to the right. */
 
526
    get_dynamic(&min_max_ranges, (unsigned char*)&cur_range, range_idx);
 
527
 
 
528
    /*
 
529
      If the current value for the min/max argument is bigger than the right
 
530
      boundary of cur_range, there is no need to check this range.
 
531
    */
 
532
    if (range_idx != 0 && !(cur_range->flag & NO_MAX_RANGE) &&
 
533
        (key_cmp(min_max_arg_part,
 
534
                 (const unsigned char*) cur_range->max_key,
 
535
                 min_max_arg_len) == 1))
 
536
      continue;
 
537
 
 
538
    if (cur_range->flag & NO_MIN_RANGE)
 
539
    {
 
540
      keypart_map= make_prev_keypart_map(real_key_parts);
 
541
      find_flag= HA_READ_KEY_EXACT;
 
542
    }
 
543
    else
 
544
    {
 
545
      /* Extend the search key with the lower boundary for this range. */
 
546
      memcpy(group_prefix + real_prefix_len,
 
547
             cur_range->min_key,
 
548
             cur_range->min_length);
 
549
      keypart_map= make_keypart_map(real_key_parts);
 
550
      find_flag= (cur_range->flag & (EQ_RANGE | NULL_RANGE)) ?
 
551
                 HA_READ_KEY_EXACT : (cur_range->flag & NEAR_MIN) ?
 
552
                 HA_READ_AFTER_KEY : HA_READ_KEY_OR_NEXT;
 
553
    }
 
554
 
 
555
    result= cursor->index_read_map(record, group_prefix, keypart_map, find_flag);
 
556
    if (result)
 
557
    {
 
558
      if ((result == HA_ERR_KEY_NOT_FOUND || result == HA_ERR_END_OF_FILE) &&
 
559
          (cur_range->flag & (EQ_RANGE | NULL_RANGE)))
 
560
        continue; /* Check the next range. */
 
561
 
 
562
      /*
 
563
        In all other cases (HA_ERR_*, HA_READ_KEY_EXACT with NO_MIN_RANGE,
 
564
        HA_READ_AFTER_KEY, HA_READ_KEY_OR_NEXT) if the lookup failed for this
 
565
        range, it can't succeed for any other subsequent range.
 
566
      */
 
567
      break;
 
568
    }
 
569
 
 
570
    /* A key was found. */
 
571
    if (cur_range->flag & EQ_RANGE)
 
572
      break; /* No need to perform the checks below for equal keys. */
 
573
 
 
574
    if (cur_range->flag & NULL_RANGE)
 
575
    {
 
576
      /*
 
577
        Remember this key, and continue looking for a non-NULL key that
 
578
        satisfies some other condition.
 
579
      */
 
580
      memcpy(tmp_record, record, head->s->rec_buff_length);
 
581
      found_null= true;
 
582
      continue;
 
583
    }
 
584
 
 
585
    /* Check if record belongs to the current group. */
 
586
    if (key_cmp(index_info->key_part, group_prefix, real_prefix_len))
 
587
    {
 
588
      result= HA_ERR_KEY_NOT_FOUND;
 
589
      continue;
 
590
    }
 
591
 
 
592
    /* If there is an upper limit, check if the found key is in the range. */
 
593
    if (! (cur_range->flag & NO_MAX_RANGE) )
 
594
    {
 
595
      /* Compose the MAX key for the range. */
 
596
      max_key.clear();
 
597
      max_key.append(group_prefix, real_prefix_len);
 
598
      max_key.append(cur_range->max_key, cur_range->max_length);
 
599
      /* Compare the found key with max_key. */
 
600
      int cmp_res= key_cmp(index_info->key_part,
 
601
                           max_key.data(),
 
602
                           real_prefix_len + min_max_arg_len);
 
603
      if (! (((cur_range->flag & NEAR_MAX) && (cmp_res == -1)) ||
 
604
          (cmp_res <= 0)))
 
605
      {
 
606
        result= HA_ERR_KEY_NOT_FOUND;
 
607
        continue;
 
608
      }
 
609
    }
 
610
    /* If we got to this point, the current key qualifies as MIN. */
 
611
    assert(result == 0);
 
612
    break;
 
613
  }
 
614
  /*
 
615
    If there was a key with NULL in the MIN/MAX field, and there was no other
 
616
    key without NULL from the same group that satisfies some other condition,
 
617
    then use the key with the NULL.
 
618
  */
 
619
  if (found_null && result)
 
620
  {
 
621
    memcpy(record, tmp_record, head->s->rec_buff_length);
 
622
    result= 0;
 
623
  }
 
624
  return result;
 
625
}
 
626
 
 
627
 
 
628
int optimizer::QuickGroupMinMaxSelect::next_max_in_range()
 
629
{
 
630
  ha_rkey_function find_flag;
 
631
  key_part_map keypart_map;
 
632
  optimizer::QuickRange *cur_range= NULL;
 
633
  int result= 0;
 
634
  basic_string<unsigned char> min_key;
 
635
  min_key.reserve(real_prefix_len + min_max_arg_len);
 
636
 
 
637
  assert(min_max_ranges.elements > 0);
 
638
 
 
639
  for (uint32_t range_idx= min_max_ranges.elements; range_idx > 0; range_idx--)
 
640
  { /* Search from the right-most range to the left. */
 
641
    get_dynamic(&min_max_ranges, (unsigned char*)&cur_range, range_idx - 1);
 
642
 
 
643
    /*
 
644
      If the current value for the min/max argument is smaller than the left
 
645
      boundary of cur_range, there is no need to check this range.
 
646
    */
 
647
    if (range_idx != min_max_ranges.elements &&
 
648
        ! (cur_range->flag & NO_MIN_RANGE) &&
 
649
        (key_cmp(min_max_arg_part,
 
650
                 (const unsigned char*) cur_range->min_key,
 
651
                 min_max_arg_len) == -1))
 
652
      continue;
 
653
 
 
654
    if (cur_range->flag & NO_MAX_RANGE)
 
655
    {
 
656
      keypart_map= make_prev_keypart_map(real_key_parts);
 
657
      find_flag= HA_READ_PREFIX_LAST;
 
658
    }
 
659
    else
 
660
    {
 
661
      /* Extend the search key with the upper boundary for this range. */
 
662
      memcpy(group_prefix + real_prefix_len,
 
663
             cur_range->max_key,
 
664
             cur_range->max_length);
 
665
      keypart_map= make_keypart_map(real_key_parts);
 
666
      find_flag= (cur_range->flag & EQ_RANGE) ?
 
667
                 HA_READ_KEY_EXACT : (cur_range->flag & NEAR_MAX) ?
 
668
                 HA_READ_BEFORE_KEY : HA_READ_PREFIX_LAST_OR_PREV;
 
669
    }
 
670
 
 
671
    result= cursor->index_read_map(record, group_prefix, keypart_map, find_flag);
 
672
 
 
673
    if (result)
 
674
    {
 
675
      if ((result == HA_ERR_KEY_NOT_FOUND || result == HA_ERR_END_OF_FILE) &&
 
676
          (cur_range->flag & EQ_RANGE))
 
677
        continue; /* Check the next range. */
 
678
 
 
679
      /*
 
680
        In no key was found with this upper bound, there certainly are no keys
 
681
        in the ranges to the left.
 
682
      */
 
683
      return result;
 
684
    }
 
685
    /* A key was found. */
 
686
    if (cur_range->flag & EQ_RANGE)
 
687
      return 0; /* No need to perform the checks below for equal keys. */
 
688
 
 
689
    /* Check if record belongs to the current group. */
 
690
    if (key_cmp(index_info->key_part, group_prefix, real_prefix_len))
 
691
      continue;                                 // Row not found
 
692
 
 
693
    /* If there is a lower limit, check if the found key is in the range. */
 
694
    if (! (cur_range->flag & NO_MIN_RANGE) )
 
695
    {
 
696
      /* Compose the MIN key for the range. */
 
697
      min_key.clear();
 
698
      min_key.append(group_prefix, real_prefix_len);
 
699
      min_key.append(cur_range->min_key, cur_range->min_length);
 
700
 
 
701
      /* Compare the found key with min_key. */
 
702
      int cmp_res= key_cmp(index_info->key_part,
 
703
                           min_key.data(),
 
704
                           real_prefix_len + min_max_arg_len);
 
705
      if (! (((cur_range->flag & NEAR_MIN) && (cmp_res == 1)) ||
 
706
          (cmp_res >= 0)))
 
707
        continue;
 
708
    }
 
709
    /* If we got to this point, the current key qualifies as MAX. */
 
710
    return result;
 
711
  }
 
712
  return HA_ERR_KEY_NOT_FOUND;
 
713
}
 
714
 
 
715
 
 
716
void optimizer::QuickGroupMinMaxSelect::update_min_result()
 
717
{
 
718
  Item_sum *min_func= NULL;
 
719
 
 
720
  min_functions_it->rewind();
 
721
  while ((min_func= (*min_functions_it)++))
 
722
    min_func->reset();
 
723
}
 
724
 
 
725
 
 
726
void optimizer::QuickGroupMinMaxSelect::update_max_result()
 
727
{
 
728
  Item_sum *max_func= NULL;
 
729
 
 
730
  max_functions_it->rewind();
 
731
  while ((max_func= (*max_functions_it)++))
 
732
    max_func->reset();
 
733
}
 
734
 
 
735
 
 
736
void optimizer::QuickGroupMinMaxSelect::add_keys_and_lengths(String *key_names,
 
737
                                                             String *used_lengths)
 
738
{
 
739
  char buf[64];
 
740
  key_names->append(index_info->name);
 
741
  uint32_t length= int64_t2str(max_used_key_length, buf, 10) - buf;
 
742
  used_lengths->append(buf, length);
 
743
}
 
744