00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020 #include <config.h>
00021 #include <drizzled/session.h>
00022 #include <drizzled/sql_select.h>
00023 #include <drizzled/join.h>
00024 #include <drizzled/optimizer/range.h>
00025 #include <drizzled/optimizer/quick_group_min_max_select.h>
00026 #include <drizzled/optimizer/quick_range.h>
00027 #include <drizzled/optimizer/quick_range_select.h>
00028 #include <drizzled/optimizer/sel_arg.h>
00029 #include <drizzled/internal/m_string.h>
00030 #include <drizzled/util/functors.h>
00031 #include <drizzled/key.h>
00032 #include <drizzled/table.h>
00033
00034 #include <vector>
00035
00036 using namespace std;
00037
00038 namespace drizzled
00039 {
00040
00041 optimizer::QuickGroupMinMaxSelect::
00042 QuickGroupMinMaxSelect(Table *table,
00043 Join *join_arg,
00044 bool have_min_arg,
00045 bool have_max_arg,
00046 KeyPartInfo *min_max_arg_part_arg,
00047 uint32_t group_prefix_len_arg,
00048 uint32_t group_key_parts_arg,
00049 uint32_t used_key_parts_arg,
00050 KeyInfo *index_info_arg,
00051 uint32_t use_index,
00052 double read_cost_arg,
00053 ha_rows records_arg,
00054 uint32_t key_infix_len_arg,
00055 unsigned char *key_infix_arg,
00056 memory::Root *parent_alloc)
00057 :
00058 join(join_arg),
00059 index_info(index_info_arg),
00060 group_prefix_len(group_prefix_len_arg),
00061 group_key_parts(group_key_parts_arg),
00062 have_min(have_min_arg),
00063 have_max(have_max_arg),
00064 seen_first_key(false),
00065 min_max_arg_part(min_max_arg_part_arg),
00066 key_infix(key_infix_arg),
00067 key_infix_len(key_infix_len_arg),
00068 min_functions_it(NULL),
00069 max_functions_it(NULL)
00070 {
00071 head= table;
00072 cursor= head->cursor;
00073 index= use_index;
00074 record= head->record[0];
00075 tmp_record= head->getUpdateRecord();
00076 read_time= read_cost_arg;
00077 records= records_arg;
00078 used_key_parts= used_key_parts_arg;
00079 real_key_parts= used_key_parts_arg;
00080 real_prefix_len= group_prefix_len + key_infix_len;
00081 group_prefix= NULL;
00082 min_max_arg_len= min_max_arg_part ? min_max_arg_part->store_length : 0;
00083
00084
00085
00086
00087
00088 assert(! parent_alloc);
00089 if (! parent_alloc)
00090 {
00091 memory::init_sql_alloc(&alloc, join->session->variables.range_alloc_block_size, 0);
00092 join->session->mem_root= &alloc;
00093 }
00094 else
00095 memset(&alloc, 0, sizeof(memory::Root));
00096 }
00097
00098
00099 int optimizer::QuickGroupMinMaxSelect::init()
00100 {
00101 if (group_prefix)
00102 return 0;
00103
00104 if (! (last_prefix= (unsigned char*) alloc.alloc_root(group_prefix_len)))
00105 return 1;
00106
00107
00108
00109
00110 if (! (group_prefix= (unsigned char*) alloc.alloc_root(real_prefix_len + min_max_arg_len)))
00111 return 1;
00112
00113 if (key_infix_len > 0)
00114 {
00115
00116
00117
00118
00119 unsigned char *tmp_key_infix= (unsigned char*) alloc.alloc_root(key_infix_len);
00120 if (! tmp_key_infix)
00121 return 1;
00122 memcpy(tmp_key_infix, this->key_infix, key_infix_len);
00123 this->key_infix= tmp_key_infix;
00124 }
00125
00126 if (min_max_arg_part)
00127 {
00128 if (have_min)
00129 {
00130 if (! (min_functions= new List<Item_sum>))
00131 return 1;
00132 }
00133 else
00134 min_functions= NULL;
00135 if (have_max)
00136 {
00137 if (! (max_functions= new List<Item_sum>))
00138 return 1;
00139 }
00140 else
00141 max_functions= NULL;
00142
00143 Item_sum *min_max_item= NULL;
00144 Item_sum **func_ptr= join->sum_funcs;
00145 while ((min_max_item= *(func_ptr++)))
00146 {
00147 if (have_min && (min_max_item->sum_func() == Item_sum::MIN_FUNC))
00148 min_functions->push_back(min_max_item);
00149 else if (have_max && (min_max_item->sum_func() == Item_sum::MAX_FUNC))
00150 max_functions->push_back(min_max_item);
00151 }
00152
00153 if (have_min)
00154 {
00155 if (! (min_functions_it= new List<Item_sum>::iterator(min_functions->begin())))
00156 return 1;
00157 }
00158
00159 if (have_max)
00160 {
00161 if (! (max_functions_it= new List<Item_sum>::iterator(max_functions->begin())))
00162 return 1;
00163 }
00164 }
00165
00166 return 0;
00167 }
00168
00169
00170 optimizer::QuickGroupMinMaxSelect::~QuickGroupMinMaxSelect()
00171 {
00172 if (cursor->inited != Cursor::NONE)
00173 {
00174 cursor->endIndexScan();
00175 }
00176 if (min_max_arg_part)
00177 {
00178 for_each(min_max_ranges.begin(),
00179 min_max_ranges.end(),
00180 DeletePtr());
00181 }
00182 min_max_ranges.clear();
00183 alloc.free_root(MYF(0));
00184 delete min_functions_it;
00185 delete max_functions_it;
00186 delete quick_prefix_select;
00187 }
00188
00189
00190 bool optimizer::QuickGroupMinMaxSelect::add_range(optimizer::SEL_ARG *sel_range)
00191 {
00192 optimizer::QuickRange *range= NULL;
00193 uint32_t range_flag= sel_range->min_flag | sel_range->max_flag;
00194
00195
00196 if ((range_flag & NO_MIN_RANGE) && (range_flag & NO_MAX_RANGE))
00197 return false;
00198
00199 if (! (sel_range->min_flag & NO_MIN_RANGE) &&
00200 ! (sel_range->max_flag & NO_MAX_RANGE))
00201 {
00202 if (sel_range->maybe_null &&
00203 sel_range->min_value[0] && sel_range->max_value[0])
00204 range_flag|= NULL_RANGE;
00205 else if (memcmp(sel_range->min_value, sel_range->max_value,
00206 min_max_arg_len) == 0)
00207 range_flag|= EQ_RANGE;
00208 }
00209 range= new optimizer::QuickRange(sel_range->min_value,
00210 min_max_arg_len,
00211 make_keypart_map(sel_range->part),
00212 sel_range->max_value,
00213 min_max_arg_len,
00214 make_keypart_map(sel_range->part),
00215 range_flag);
00216 if (! range)
00217 return true;
00218 min_max_ranges.push_back(range);
00219 return false;
00220 }
00221
00222
00223 void optimizer::QuickGroupMinMaxSelect::adjust_prefix_ranges()
00224 {
00225 if (quick_prefix_select &&
00226 group_prefix_len < quick_prefix_select->max_used_key_length)
00227 {
00228 DYNAMIC_ARRAY& arr= quick_prefix_select->ranges;
00229 for (size_t inx= 0; inx < arr.size(); inx++)
00230 reinterpret_cast<optimizer::QuickRange**>(arr.buffer)[inx]->flag &= ~(NEAR_MIN | NEAR_MAX);
00231 }
00232 }
00233
00234
00235 void optimizer::QuickGroupMinMaxSelect::update_key_stat()
00236 {
00237 max_used_key_length= real_prefix_len;
00238 if (! min_max_ranges.empty())
00239 {
00240 optimizer::QuickRange *cur_range= NULL;
00241 if (have_min)
00242 {
00243 cur_range= min_max_ranges.back();
00244 if (! (cur_range->flag & NO_MIN_RANGE))
00245 {
00246 max_used_key_length+= min_max_arg_len;
00247 used_key_parts++;
00248 return;
00249 }
00250 }
00251 if (have_max)
00252 {
00253 cur_range= min_max_ranges.front();
00254 if (! (cur_range->flag & NO_MAX_RANGE))
00255 {
00256 max_used_key_length+= min_max_arg_len;
00257 used_key_parts++;
00258 return;
00259 }
00260 }
00261 }
00262 else if (have_min && min_max_arg_part &&
00263 min_max_arg_part->field->real_maybe_null())
00264 {
00265
00266
00267
00268
00269
00270
00271
00272
00273 max_used_key_length+= min_max_arg_len;
00274 used_key_parts++;
00275 }
00276 }
00277
00278
00279 int optimizer::QuickGroupMinMaxSelect::reset(void)
00280 {
00281 int result;
00282
00283 cursor->extra(HA_EXTRA_KEYREAD);
00284 if ((result= cursor->startIndexScan(index,1)))
00285 return result;
00286 if (quick_prefix_select && quick_prefix_select->reset())
00287 return 0;
00288 result= cursor->index_last(record);
00289 if (result == HA_ERR_END_OF_FILE)
00290 return 0;
00291
00292 key_copy(last_prefix, record, index_info, group_prefix_len);
00293
00294 return 0;
00295 }
00296
00297
00298 int optimizer::QuickGroupMinMaxSelect::get_next()
00299 {
00300 int min_res= 0;
00301 int max_res= 0;
00302 int result= 0;
00303 int is_last_prefix= 0;
00304
00305
00306
00307
00308
00309 do
00310 {
00311 result= next_prefix();
00312
00313
00314
00315
00316 if (! result)
00317 {
00318 is_last_prefix= key_cmp(index_info->key_part, last_prefix,
00319 group_prefix_len);
00320 assert(is_last_prefix <= 0);
00321 }
00322 else
00323 {
00324 if (result == HA_ERR_KEY_NOT_FOUND)
00325 continue;
00326 break;
00327 }
00328
00329 if (have_min)
00330 {
00331 min_res= next_min();
00332 if (min_res == 0)
00333 update_min_result();
00334 }
00335
00336 if ((have_max && !have_min) ||
00337 (have_max && have_min && (min_res == 0)))
00338 {
00339 max_res= next_max();
00340 if (max_res == 0)
00341 update_max_result();
00342
00343 assert(((have_max && !have_min) ||
00344 (have_max && have_min && (max_res == 0))));
00345 }
00346
00347
00348
00349
00350
00351 if (! have_min && ! have_max && key_infix_len > 0)
00352 result= cursor->index_read_map(record,
00353 group_prefix,
00354 make_prev_keypart_map(real_key_parts),
00355 HA_READ_KEY_EXACT);
00356
00357 result= have_min ? min_res : have_max ? max_res : result;
00358 } while ((result == HA_ERR_KEY_NOT_FOUND || result == HA_ERR_END_OF_FILE) &&
00359 is_last_prefix != 0);
00360
00361 if (result == 0)
00362 {
00363
00364
00365
00366
00367
00368
00369 copy_fields(&join->tmp_table_param);
00370 }
00371 else if (result == HA_ERR_KEY_NOT_FOUND)
00372 result= HA_ERR_END_OF_FILE;
00373
00374 return result;
00375 }
00376
00377
00378 int optimizer::QuickGroupMinMaxSelect::next_min()
00379 {
00380 int result= 0;
00381
00382
00383 if (! min_max_ranges.empty())
00384 {
00385 if ((result= next_min_in_range()))
00386 return result;
00387 }
00388 else
00389 {
00390
00391 if (key_infix_len > 0)
00392 {
00393 if ((result= cursor->index_read_map(record,
00394 group_prefix,
00395 make_prev_keypart_map(real_key_parts),
00396 HA_READ_KEY_EXACT)))
00397 return result;
00398 }
00399
00400
00401
00402
00403
00404
00405
00406
00407 if (min_max_arg_part && min_max_arg_part->field->is_null())
00408 {
00409
00410 key_copy(tmp_record, record, index_info, 0);
00411 result= cursor->index_read_map(record,
00412 tmp_record,
00413 make_keypart_map(real_key_parts),
00414 HA_READ_AFTER_KEY);
00415
00416
00417
00418
00419
00420
00421
00422
00423
00424
00425 if (! result)
00426 {
00427 if (key_cmp(index_info->key_part, group_prefix, real_prefix_len))
00428 key_restore(record, tmp_record, index_info, 0);
00429 }
00430 else if (result == HA_ERR_KEY_NOT_FOUND || result == HA_ERR_END_OF_FILE)
00431 result= 0;
00432 }
00433 }
00434
00435
00436
00437
00438
00439 return result;
00440 }
00441
00442
00443 int optimizer::QuickGroupMinMaxSelect::next_max()
00444 {
00445 int result= 0;
00446
00447
00448 if (! min_max_ranges.empty())
00449 result= next_max_in_range();
00450 else
00451 result= cursor->index_read_map(record,
00452 group_prefix,
00453 make_prev_keypart_map(real_key_parts),
00454 HA_READ_PREFIX_LAST);
00455 return result;
00456 }
00457
00458
00459 int optimizer::QuickGroupMinMaxSelect::next_prefix()
00460 {
00461 int result= 0;
00462
00463 if (quick_prefix_select)
00464 {
00465 unsigned char *cur_prefix= seen_first_key ? group_prefix : NULL;
00466 if ((result= quick_prefix_select->get_next_prefix(group_prefix_len,
00467 make_prev_keypart_map(group_key_parts),
00468 cur_prefix)))
00469 return result;
00470 seen_first_key= true;
00471 }
00472 else
00473 {
00474 if (! seen_first_key)
00475 {
00476 result= cursor->index_first(record);
00477 if (result)
00478 return result;
00479 seen_first_key= true;
00480 }
00481 else
00482 {
00483
00484 result= cursor->index_read_map(record,
00485 group_prefix,
00486 make_prev_keypart_map(group_key_parts),
00487 HA_READ_AFTER_KEY);
00488 if (result)
00489 return result;
00490 }
00491 }
00492
00493
00494 key_copy(group_prefix, record, index_info, group_prefix_len);
00495
00496 if (key_infix_len > 0)
00497 memcpy(group_prefix + group_prefix_len,
00498 key_infix,
00499 key_infix_len);
00500
00501 return 0;
00502 }
00503
00504
00505 int optimizer::QuickGroupMinMaxSelect::next_min_in_range()
00506 {
00507 ha_rkey_function find_flag;
00508 key_part_map keypart_map;
00509 optimizer::QuickRange *cur_range= NULL;
00510 bool found_null= false;
00511 int result= HA_ERR_KEY_NOT_FOUND;
00512 basic_string<unsigned char> max_key;
00513
00514 max_key.reserve(real_prefix_len + min_max_arg_len);
00515
00516 assert(! min_max_ranges.empty());
00517
00518 for (vector<optimizer::QuickRange *>::iterator it= min_max_ranges.begin();
00519 it != min_max_ranges.end();
00520 ++it)
00521 {
00522 cur_range= *it;
00523
00524
00525
00526
00527
00528 if (it != min_max_ranges.begin() &&
00529 ! (cur_range->flag & NO_MAX_RANGE) &&
00530 (key_cmp(min_max_arg_part,
00531 (const unsigned char*) cur_range->max_key,
00532 min_max_arg_len) == 1))
00533 continue;
00534
00535 if (cur_range->flag & NO_MIN_RANGE)
00536 {
00537 keypart_map= make_prev_keypart_map(real_key_parts);
00538 find_flag= HA_READ_KEY_EXACT;
00539 }
00540 else
00541 {
00542
00543 memcpy(group_prefix + real_prefix_len,
00544 cur_range->min_key,
00545 cur_range->min_length);
00546 keypart_map= make_keypart_map(real_key_parts);
00547 find_flag= (cur_range->flag & (EQ_RANGE | NULL_RANGE)) ?
00548 HA_READ_KEY_EXACT : (cur_range->flag & NEAR_MIN) ?
00549 HA_READ_AFTER_KEY : HA_READ_KEY_OR_NEXT;
00550 }
00551
00552 result= cursor->index_read_map(record, group_prefix, keypart_map, find_flag);
00553 if (result)
00554 {
00555 if ((result == HA_ERR_KEY_NOT_FOUND || result == HA_ERR_END_OF_FILE) &&
00556 (cur_range->flag & (EQ_RANGE | NULL_RANGE)))
00557 continue;
00558
00559
00560
00561
00562
00563
00564 break;
00565 }
00566
00567
00568 if (cur_range->flag & EQ_RANGE)
00569 break;
00570
00571 if (cur_range->flag & NULL_RANGE)
00572 {
00573
00574
00575
00576
00577 memcpy(tmp_record, record, head->getShare()->rec_buff_length);
00578 found_null= true;
00579 continue;
00580 }
00581
00582
00583 if (key_cmp(index_info->key_part, group_prefix, real_prefix_len))
00584 {
00585 result= HA_ERR_KEY_NOT_FOUND;
00586 continue;
00587 }
00588
00589
00590 if (! (cur_range->flag & NO_MAX_RANGE) )
00591 {
00592
00593 max_key.clear();
00594 max_key.append(group_prefix, real_prefix_len);
00595 max_key.append(cur_range->max_key, cur_range->max_length);
00596
00597 int cmp_res= key_cmp(index_info->key_part,
00598 max_key.data(),
00599 real_prefix_len + min_max_arg_len);
00600 if (! (((cur_range->flag & NEAR_MAX) && (cmp_res == -1)) ||
00601 (cmp_res <= 0)))
00602 {
00603 result= HA_ERR_KEY_NOT_FOUND;
00604 continue;
00605 }
00606 }
00607
00608 assert(result == 0);
00609 break;
00610 }
00611
00612
00613
00614
00615
00616 if (found_null && result)
00617 {
00618 memcpy(record, tmp_record, head->getShare()->rec_buff_length);
00619 result= 0;
00620 }
00621 return result;
00622 }
00623
00624
00625 int optimizer::QuickGroupMinMaxSelect::next_max_in_range()
00626 {
00627 ha_rkey_function find_flag;
00628 key_part_map keypart_map;
00629 optimizer::QuickRange *cur_range= NULL;
00630 int result= 0;
00631 basic_string<unsigned char> min_key;
00632 min_key.reserve(real_prefix_len + min_max_arg_len);
00633
00634 assert(! min_max_ranges.empty());
00635
00636 for (vector<optimizer::QuickRange *>::reverse_iterator rit= min_max_ranges.rbegin();
00637 rit != min_max_ranges.rend();
00638 ++rit)
00639 {
00640 cur_range= *rit;
00641
00642
00643
00644
00645
00646 if (rit != min_max_ranges.rbegin() &&
00647 ! (cur_range->flag & NO_MIN_RANGE) &&
00648 (key_cmp(min_max_arg_part,
00649 (const unsigned char*) cur_range->min_key,
00650 min_max_arg_len) == -1))
00651 continue;
00652
00653 if (cur_range->flag & NO_MAX_RANGE)
00654 {
00655 keypart_map= make_prev_keypart_map(real_key_parts);
00656 find_flag= HA_READ_PREFIX_LAST;
00657 }
00658 else
00659 {
00660
00661 memcpy(group_prefix + real_prefix_len,
00662 cur_range->max_key,
00663 cur_range->max_length);
00664 keypart_map= make_keypart_map(real_key_parts);
00665 find_flag= (cur_range->flag & EQ_RANGE) ?
00666 HA_READ_KEY_EXACT : (cur_range->flag & NEAR_MAX) ?
00667 HA_READ_BEFORE_KEY : HA_READ_PREFIX_LAST_OR_PREV;
00668 }
00669
00670 result= cursor->index_read_map(record, group_prefix, keypart_map, find_flag);
00671
00672 if (result)
00673 {
00674 if ((result == HA_ERR_KEY_NOT_FOUND || result == HA_ERR_END_OF_FILE) &&
00675 (cur_range->flag & EQ_RANGE))
00676 continue;
00677
00678
00679
00680
00681
00682 return result;
00683 }
00684
00685 if (cur_range->flag & EQ_RANGE)
00686 return 0;
00687
00688
00689 if (key_cmp(index_info->key_part, group_prefix, real_prefix_len))
00690 continue;
00691
00692
00693 if (! (cur_range->flag & NO_MIN_RANGE) )
00694 {
00695
00696 min_key.clear();
00697 min_key.append(group_prefix, real_prefix_len);
00698 min_key.append(cur_range->min_key, cur_range->min_length);
00699
00700
00701 int cmp_res= key_cmp(index_info->key_part,
00702 min_key.data(),
00703 real_prefix_len + min_max_arg_len);
00704 if (! (((cur_range->flag & NEAR_MIN) && (cmp_res == 1)) ||
00705 (cmp_res >= 0)))
00706 continue;
00707 }
00708
00709 return result;
00710 }
00711 return HA_ERR_KEY_NOT_FOUND;
00712 }
00713
00714
00715 void optimizer::QuickGroupMinMaxSelect::update_min_result()
00716 {
00717 *min_functions_it= min_functions->begin();
00718 for (Item_sum *min_func; (min_func= (*min_functions_it)++); )
00719 min_func->reset();
00720 }
00721
00722
00723 void optimizer::QuickGroupMinMaxSelect::update_max_result()
00724 {
00725 *max_functions_it= max_functions->begin();
00726 for (Item_sum *max_func; (max_func= (*max_functions_it)++); )
00727 max_func->reset();
00728 }
00729
00730
00731 void optimizer::QuickGroupMinMaxSelect::add_keys_and_lengths(string *key_names,
00732 string *used_lengths)
00733 {
00734 char buf[64];
00735 key_names->append(index_info->name);
00736 uint32_t length= internal::int64_t2str(max_used_key_length, buf, 10) - buf;
00737 used_lengths->append(buf, length);
00738 }
00739
00740 }