Drizzled Public API Documentation

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