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