00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00054 #include <config.h>
00055
00056 #include <drizzled/sql_select.h>
00057 #include <drizzled/item/sum.h>
00058 #include <drizzled/item/cmpfunc.h>
00059 #include <drizzled/optimizer/sum.h>
00060 #include <drizzled/plugin/storage_engine.h>
00061 #include <drizzled/table_list.h>
00062 #include <drizzled/key.h>
00063
00064 namespace drizzled
00065 {
00066
00067 static bool find_key_for_maxmin(bool max_fl,
00068 table_reference_st *ref,
00069 Field* field,
00070 COND *cond,
00071 uint32_t *range_fl,
00072 uint32_t *key_prefix_length);
00073
00074 static int reckey_in_range(bool max_fl,
00075 table_reference_st *ref,
00076 Field* field,
00077 COND *cond,
00078 uint32_t range_fl,
00079 uint32_t prefix_len);
00080
00081 static int maxmin_in_range(bool max_fl, Field *field, COND *cond);
00082
00083
00084
00085
00086
00087
00088
00089
00090
00091
00092
00093
00094
00095
00096
00097
00098
00099 static uint64_t get_exact_record_count(TableList *tables)
00100 {
00101 uint64_t count= 1;
00102 for (TableList *tl= tables; tl; tl= tl->next_leaf)
00103 {
00104 ha_rows tmp= tl->table->cursor->records();
00105 if ((tmp == HA_POS_ERROR))
00106 {
00107 return UINT64_MAX;
00108 }
00109 count*= tmp;
00110 }
00111 return count;
00112 }
00113
00114
00115 int optimizer::sum_query(TableList *tables, List<Item> &all_fields, COND *conds)
00116 {
00117 List<Item>::iterator it(all_fields.begin());
00118 int const_result= 1;
00119 bool recalc_const_item= false;
00120 uint64_t count= 1;
00121 bool is_exact_count= true;
00122 bool maybe_exact_count= true;
00123 table_map removed_tables= 0;
00124 table_map outer_tables= 0;
00125 table_map used_tables= 0;
00126 table_map where_tables= 0;
00127 Item *item= NULL;
00128 int error;
00129
00130 if (conds)
00131 {
00132 where_tables= conds->used_tables();
00133 }
00134
00135
00136
00137
00138
00139 for (TableList *tl= tables; tl; tl= tl->next_leaf)
00140 {
00141 TableList *embedded= NULL;
00142 for (embedded= tl; embedded; embedded= embedded->getEmbedding())
00143 {
00144 if (embedded->on_expr)
00145 break;
00146 }
00147 if (embedded)
00148
00149 {
00150 outer_tables|= tl->table->map;
00151
00152
00153
00154
00155
00156
00157
00158 if (tl->table->map & where_tables)
00159 return 0;
00160 }
00161 else
00162 {
00163 used_tables|= tl->table->map;
00164 }
00165
00166
00167
00168
00169
00170
00171
00172
00173 if (! (tl->table->cursor->getEngine()->check_flag(HTON_BIT_STATS_RECORDS_IS_EXACT)))
00174 {
00175 maybe_exact_count&= test(tl->table->cursor->getEngine()->check_flag(HTON_BIT_HAS_RECORDS));
00176 is_exact_count= false;
00177 count= 1;
00178 }
00179 else
00180 {
00181 error= tl->table->cursor->info(HA_STATUS_VARIABLE | HA_STATUS_NO_LOCK);
00182 if(error)
00183 {
00184 tl->table->print_error(error, MYF(ME_FATALERROR));
00185 return error;
00186 }
00187 count*= tl->table->cursor->stats.records;
00188 }
00189 }
00190
00191
00192
00193
00194
00195
00196 while ((item= it++))
00197 {
00198 if (item->type() == Item::SUM_FUNC_ITEM)
00199 {
00200 Item_sum *item_sum= (((Item_sum*) item));
00201 switch (item_sum->sum_func())
00202 {
00203 case Item_sum::COUNT_FUNC:
00204
00205
00206
00207
00208
00209 if (! conds && ! ((Item_sum_count*) item)->args[0]->maybe_null &&
00210 ! outer_tables && maybe_exact_count)
00211 {
00212 if (! is_exact_count)
00213 {
00214 if ((count= get_exact_record_count(tables)) == UINT64_MAX)
00215 {
00216
00217 const_result= 0;
00218 continue;
00219 }
00220 is_exact_count= 1;
00221 }
00222 ((Item_sum_count*) item)->make_const_count((int64_t) count);
00223 recalc_const_item= 1;
00224 }
00225 else
00226 {
00227 const_result= 0;
00228 }
00229 break;
00230 case Item_sum::MIN_FUNC:
00231 {
00232
00233
00234
00235
00236
00237 Item *expr=item_sum->args[0];
00238 if (expr->real_item()->type() == Item::FIELD_ITEM)
00239 {
00240 unsigned char key_buff[MAX_KEY_LENGTH];
00241 table_reference_st ref;
00242 uint32_t range_fl, prefix_len;
00243
00244 ref.key_buff= key_buff;
00245 Item_field *item_field= (Item_field*) (expr->real_item());
00246 Table *table= item_field->field->getTable();
00247
00248
00249
00250
00251
00252
00253
00254
00255
00256 if (table->cursor->inited ||
00257 (outer_tables & table->map) ||
00258 ! find_key_for_maxmin(0,
00259 &ref,
00260 item_field->field,
00261 conds,
00262 &range_fl,
00263 &prefix_len))
00264 {
00265 const_result= 0;
00266 break;
00267 }
00268 error= table->cursor->startIndexScan(static_cast<uint32_t>(ref.key), 1);
00269 if (error)
00270 {
00271 if (table->key_read)
00272 {
00273 table->key_read= 0;
00274 table->cursor->extra(HA_EXTRA_NO_KEYREAD);
00275 }
00276 table->print_error(error, MYF(0));
00277 return error;
00278 }
00279
00280 if (! ref.key_length)
00281 {
00282 error= table->cursor->index_first(table->record[0]);
00283 }
00284 else
00285 {
00286
00287
00288
00289
00290
00291
00292
00293
00294
00295
00296
00297
00298
00299
00300 if (! (range_fl & NEAR_MIN))
00301 {
00302
00303
00304
00305
00306 error= table->cursor->index_read_map(table->record[0],
00307 ref.key_buff,
00308 make_prev_keypart_map(ref.key_parts),
00309 HA_READ_KEY_OR_NEXT);
00310 }
00311 else
00312 {
00313
00314
00315
00316
00317
00318
00319 error= table->cursor->index_read_map(table->record[0],
00320 ref.key_buff,
00321 make_prev_keypart_map(ref.key_parts),
00322 HA_READ_AFTER_KEY);
00323
00324
00325
00326
00327
00328
00329
00330
00331
00332 if (item_field->field->real_maybe_null() &&
00333 ref.key_buff[prefix_len] == 1 &&
00334
00335
00336
00337
00338
00339
00340
00341 (error == HA_ERR_KEY_NOT_FOUND ||
00342 key_cmp_if_same(table, ref.key_buff, ref.key, prefix_len)))
00343 {
00344 assert(item_field->field->real_maybe_null());
00345 error= table->cursor->index_read_map(table->record[0],
00346 ref.key_buff,
00347 make_prev_keypart_map(ref.key_parts),
00348 HA_READ_KEY_EXACT);
00349 }
00350 }
00351 }
00352
00353 if (! error &&
00354 reckey_in_range(0,
00355 &ref,
00356 item_field->field,
00357 conds,
00358 range_fl,
00359 prefix_len))
00360 {
00361 error= HA_ERR_KEY_NOT_FOUND;
00362 }
00363 if (table->key_read)
00364 {
00365 table->key_read= 0;
00366 table->cursor->extra(HA_EXTRA_NO_KEYREAD);
00367 }
00368 table->cursor->endIndexScan();
00369 if (error)
00370 {
00371 if (error == HA_ERR_KEY_NOT_FOUND || error == HA_ERR_END_OF_FILE)
00372 {
00373 return HA_ERR_KEY_NOT_FOUND;
00374 }
00375
00376 table->print_error(error, MYF(0));
00377 return error;
00378 }
00379 removed_tables|= table->map;
00380 }
00381 else if (! expr->const_item() || ! is_exact_count)
00382 {
00383
00384
00385
00386
00387
00388
00389
00390
00391
00392 const_result= 0;
00393 break;
00394 }
00395 if (! count)
00396 {
00397
00398 ((Item_sum_min*) item_sum)->clear();
00399 }
00400 else
00401 {
00402 ((Item_sum_min*) item_sum)->reset();
00403 }
00404 ((Item_sum_min*) item_sum)->make_const();
00405 recalc_const_item= 1;
00406 break;
00407 }
00408 case Item_sum::MAX_FUNC:
00409 {
00410
00411
00412
00413
00414
00415 Item *expr= item_sum->args[0];
00416 if (expr->real_item()->type() == Item::FIELD_ITEM)
00417 {
00418 unsigned char key_buff[MAX_KEY_LENGTH];
00419 table_reference_st ref;
00420 uint32_t range_fl, prefix_len;
00421
00422 ref.key_buff= key_buff;
00423 Item_field *item_field= (Item_field*) (expr->real_item());
00424 Table *table= item_field->field->getTable();
00425
00426
00427
00428
00429
00430
00431
00432
00433
00434 if (table->cursor->inited ||
00435 (outer_tables & table->map) ||
00436 ! find_key_for_maxmin(1,
00437 &ref,
00438 item_field->field,
00439 conds,
00440 &range_fl,
00441 &prefix_len))
00442 {
00443 const_result= 0;
00444 break;
00445 }
00446 error= table->cursor->startIndexScan(static_cast<uint32_t>(ref.key), 1);
00447
00448 if (! ref.key_length)
00449 {
00450 error= table->cursor->index_last(table->record[0]);
00451 }
00452 else
00453 {
00454 error= table->cursor->index_read_map(table->record[0],
00455 key_buff,
00456 make_prev_keypart_map(ref.key_parts),
00457 range_fl & NEAR_MAX ?
00458 HA_READ_BEFORE_KEY :
00459 HA_READ_PREFIX_LAST_OR_PREV);
00460 }
00461 if (! error &&
00462 reckey_in_range(1,
00463 &ref,
00464 item_field->field,
00465 conds,
00466 range_fl,
00467 prefix_len))
00468 {
00469 error= HA_ERR_KEY_NOT_FOUND;
00470 }
00471 if (table->key_read)
00472 {
00473 table->key_read= 0;
00474 table->cursor->extra(HA_EXTRA_NO_KEYREAD);
00475 }
00476 table->cursor->endIndexScan();
00477 if (error)
00478 {
00479 if (error == HA_ERR_KEY_NOT_FOUND || error == HA_ERR_END_OF_FILE)
00480 {
00481 return HA_ERR_KEY_NOT_FOUND;
00482 }
00483
00484 table->print_error(error, MYF(ME_FATALERROR));
00485 return error;
00486 }
00487 removed_tables|= table->map;
00488 }
00489 else if (! expr->const_item() || ! is_exact_count)
00490 {
00491
00492
00493
00494
00495
00496
00497
00498
00499
00500 const_result= 0;
00501 break;
00502 }
00503 if (! count)
00504 {
00505
00506 ((Item_sum_max*) item_sum)->clear();
00507 }
00508 else
00509 {
00510 ((Item_sum_max*) item_sum)->reset();
00511 }
00512 ((Item_sum_max*) item_sum)->make_const();
00513 recalc_const_item= 1;
00514 break;
00515 }
00516 default:
00517 const_result= 0;
00518 break;
00519 }
00520 }
00521 else if (const_result)
00522 {
00523 if (recalc_const_item)
00524 {
00525 item->update_used_tables();
00526 }
00527 if (! item->const_item())
00528 {
00529 const_result= 0;
00530 }
00531 }
00532 }
00533
00534
00535
00536
00537
00538
00539
00540 if (removed_tables && used_tables != removed_tables)
00541 {
00542 const_result= 0;
00543 }
00544 return const_result;
00545 }
00546
00547
00548 bool optimizer::simple_pred(Item_func *func_item, Item **args, bool &inv_order)
00549 {
00550 Item *item= NULL;
00551 inv_order= false;
00552 switch (func_item->argument_count())
00553 {
00554 case 0:
00555
00556 {
00557 Item_equal *item_equal= (Item_equal *) func_item;
00558 Item_equal_iterator it(item_equal->begin());
00559 args[0]= it++;
00560 if (it++)
00561 {
00562 return 0;
00563 }
00564 if (! (args[1]= item_equal->get_const()))
00565 {
00566 return 0;
00567 }
00568 }
00569 break;
00570 case 1:
00571
00572 item= func_item->arguments()[0];
00573 if (item->type() != Item::FIELD_ITEM)
00574 {
00575 return 0;
00576 }
00577 args[0]= item;
00578 break;
00579 case 2:
00580
00581 item= func_item->arguments()[0];
00582 if (item->type() == Item::FIELD_ITEM)
00583 {
00584 args[0]= item;
00585 item= func_item->arguments()[1];
00586 if (! item->const_item())
00587 {
00588 return 0;
00589 }
00590 args[1]= item;
00591 }
00592 else if (item->const_item())
00593 {
00594 args[1]= item;
00595 item= func_item->arguments()[1];
00596 if (item->type() != Item::FIELD_ITEM)
00597 {
00598 return 0;
00599 }
00600 args[0]= item;
00601 inv_order= true;
00602 }
00603 else
00604 {
00605 return 0;
00606 }
00607 break;
00608 case 3:
00609
00610 item= func_item->arguments()[0];
00611 if (item->type() == Item::FIELD_ITEM)
00612 {
00613 args[0]= item;
00614 for (int i= 1 ; i <= 2; i++)
00615 {
00616 item= func_item->arguments()[i];
00617 if (! item->const_item())
00618 {
00619 return 0;
00620 }
00621 args[i]= item;
00622 }
00623 }
00624 else
00625 {
00626 return 0;
00627 }
00628 }
00629 return 1;
00630 }
00631
00632
00662 static bool matching_cond(bool max_fl,
00663 table_reference_st *ref,
00664 KeyInfo *keyinfo,
00665 KeyPartInfo *field_part,
00666 COND *cond,
00667 key_part_map *key_part_used,
00668 uint32_t *range_fl,
00669 uint32_t *prefix_len)
00670 {
00671 if (! cond)
00672 {
00673 return 1;
00674 }
00675 Field *field= field_part->field;
00676
00677 field->setWriteSet();
00678
00679 if (! (cond->used_tables() & field->getTable()->map))
00680 {
00681
00682 return 1;
00683 }
00684 if (cond->type() == Item::COND_ITEM)
00685 {
00686 if (((Item_cond*) cond)->functype() == Item_func::COND_OR_FUNC)
00687 {
00688 return 0;
00689 }
00690
00691
00692 List<Item>::iterator li(((Item_cond*) cond)->argument_list()->begin());
00693 Item *item;
00694 while ((item= li++))
00695 {
00696 if (! matching_cond(max_fl,
00697 ref,
00698 keyinfo,
00699 field_part,
00700 item,
00701 key_part_used,
00702 range_fl,
00703 prefix_len))
00704 {
00705 return 0;
00706 }
00707 }
00708 return 1;
00709 }
00710
00711 if (cond->type() != Item::FUNC_ITEM)
00712 {
00713 return 0;
00714 }
00715
00716 bool eq_type= false;
00717 bool noeq_type= false;
00718 bool less_fl= false;
00719 bool is_null= false;
00720 bool between= false;
00721
00722 switch (((Item_func*) cond)->functype())
00723 {
00724 case Item_func::ISNULL_FUNC:
00725 is_null= 1;
00726 case Item_func::EQ_FUNC:
00727 case Item_func::EQUAL_FUNC:
00728 eq_type= 1;
00729 break;
00730 case Item_func::LT_FUNC:
00731 noeq_type= 1;
00732 case Item_func::LE_FUNC:
00733 less_fl= 1;
00734 break;
00735 case Item_func::GT_FUNC:
00736 noeq_type= 1;
00737 case Item_func::GE_FUNC:
00738 break;
00739 case Item_func::BETWEEN:
00740 between= 1;
00741 break;
00742 case Item_func::MULT_EQUAL_FUNC:
00743 eq_type= 1;
00744 break;
00745 default:
00746 return 0;
00747 }
00748
00749 Item *args[3];
00750 bool inv;
00751
00752
00753 if (! optimizer::simple_pred((Item_func*) cond, args, inv))
00754 {
00755 return 0;
00756 }
00757
00758 if (inv && ! eq_type)
00759 {
00760 less_fl= 1 - less_fl;
00761 }
00762
00763
00764 unsigned char *key_ptr= ref->key_buff;
00765 KeyPartInfo *part= NULL;
00766 for (part= keyinfo->key_part; ; key_ptr+= part++->store_length)
00767
00768 {
00769 if (part > field_part)
00770 {
00771 return 0;
00772 }
00773 if (part->field->eq(((Item_field*) args[0])->field))
00774 {
00775 break;
00776 }
00777 }
00778
00779 bool is_field_part= part == field_part;
00780 if (! (is_field_part || eq_type))
00781 {
00782 return 0;
00783 }
00784
00785 key_part_map org_key_part_used= *key_part_used;
00786 if (eq_type || between || max_fl == less_fl)
00787 {
00788 uint32_t length= (key_ptr-ref->key_buff)+part->store_length;
00789 if (ref->key_length < length)
00790 {
00791
00792 ref->key_length= length;
00793 ref->key_parts= (part - keyinfo->key_part) + 1;
00794 }
00795 if (! *prefix_len && part + 1 == field_part)
00796 {
00797 *prefix_len= length;
00798 }
00799 if (is_field_part && eq_type)
00800 {
00801 *prefix_len= ref->key_length;
00802 }
00803
00804 *key_part_used|= (key_part_map) 1 << (part - keyinfo->key_part);
00805 }
00806
00807 if (org_key_part_used != *key_part_used ||
00808 (is_field_part &&
00809 (between || eq_type || max_fl == less_fl) && ! cond->val_int()))
00810 {
00811
00812
00813
00814
00815
00816
00817
00818
00819
00820 if (is_null)
00821 {
00822 part->field->set_null();
00823 *key_ptr= (unsigned char) 1;
00824 }
00825 else
00826 {
00827 store_val_in_field(part->field, args[between && max_fl ? 2 : 1],
00828 CHECK_FIELD_IGNORE);
00829 if (part->null_bit)
00830 {
00831 *key_ptr++= (unsigned char) test(part->field->is_null());
00832 }
00833 part->field->get_key_image(key_ptr, part->length);
00834 }
00835 if (is_field_part)
00836 {
00837 if (between || eq_type)
00838 {
00839 *range_fl&= ~(NO_MAX_RANGE | NO_MIN_RANGE);
00840 }
00841 else
00842 {
00843 *range_fl&= ~(max_fl ? NO_MAX_RANGE : NO_MIN_RANGE);
00844 if (noeq_type)
00845 {
00846 *range_fl|= (max_fl ? NEAR_MAX : NEAR_MIN);
00847 }
00848 else
00849 {
00850 *range_fl&= ~(max_fl ? NEAR_MAX : NEAR_MIN);
00851 }
00852 }
00853 }
00854 }
00855 else if (eq_type)
00856 {
00857 if ((! is_null && !cond->val_int()) ||
00858 (is_null && !test(part->field->is_null())))
00859 {
00860 return 0;
00861 }
00862 }
00863 else if (is_field_part)
00864 {
00865 *range_fl&= ~(max_fl ? NO_MIN_RANGE : NO_MAX_RANGE);
00866 }
00867 return 1;
00868 }
00869
00870
00912 static bool find_key_for_maxmin(bool max_fl,
00913 table_reference_st *ref,
00914 Field* field,
00915 COND *cond,
00916 uint32_t *range_fl,
00917 uint32_t *prefix_len)
00918 {
00919 if (! (field->flags & PART_KEY_FLAG))
00920 {
00921 return 0;
00922 }
00923
00924 Table *table= field->getTable();
00925 uint32_t idx= 0;
00926
00927 KeyInfo *keyinfo,*keyinfo_end= NULL;
00928 for (keyinfo= table->key_info, keyinfo_end= keyinfo+table->getShare()->sizeKeys();
00929 keyinfo != keyinfo_end;
00930 keyinfo++,idx++)
00931 {
00932 KeyPartInfo *part= NULL;
00933 KeyPartInfo *part_end= NULL;
00934 key_part_map key_part_to_use= 0;
00935
00936
00937
00938
00939 if (! table->keys_in_use_for_query.test(idx))
00940 {
00941 continue;
00942 }
00943 uint32_t jdx= 0;
00944 *prefix_len= 0;
00945 for (part= keyinfo->key_part, part_end= part+keyinfo->key_parts;
00946 part != part_end;
00947 part++, jdx++, key_part_to_use= (key_part_to_use << 1) | 1)
00948 {
00949 if (! (table->index_flags(idx) & HA_READ_ORDER))
00950 {
00951 return 0;
00952 }
00953
00954
00955 Field *part_field= table->getField(part->fieldnr-1);
00956 part_field->setWriteSet();
00957
00958 if ((part_field->flags & BLOB_FLAG) ||
00959 part->length < part_field->key_length())
00960 {
00961 break;
00962 }
00963
00964 if (field->eq(part->field))
00965 {
00966 ref->key= idx;
00967 ref->key_length= 0;
00968 ref->key_parts= 0;
00969 key_part_map key_part_used= 0;
00970 *range_fl= NO_MIN_RANGE | NO_MAX_RANGE;
00971 if (matching_cond(max_fl,
00972 ref,
00973 keyinfo,
00974 part,
00975 cond,
00976 &key_part_used,
00977 range_fl,
00978 prefix_len) &&
00979 ! (key_part_to_use & ~key_part_used))
00980 {
00981 if (! max_fl && key_part_used == key_part_to_use && part->null_bit)
00982 {
00983
00984
00985
00986
00987
00988
00989
00990
00991
00992
00993
00994
00995
00996
00997
00998 ref->key_buff[ref->key_length]= 1;
00999 ref->key_length+= part->store_length;
01000 ref->key_parts++;
01001 assert(ref->key_parts == jdx+1);
01002 *range_fl&= ~NO_MIN_RANGE;
01003 *range_fl|= NEAR_MIN;
01004 }
01005
01006
01007
01008
01009 if (field->part_of_key.test(idx))
01010 {
01011 table->key_read= 1;
01012 table->cursor->extra(HA_EXTRA_KEYREAD);
01013 }
01014 return 1;
01015 }
01016 }
01017 }
01018 }
01019 return 0;
01020 }
01021
01022
01038 static int reckey_in_range(bool max_fl,
01039 table_reference_st *ref,
01040 Field* field,
01041 COND *cond,
01042 uint32_t range_fl,
01043 uint32_t prefix_len)
01044 {
01045 if (key_cmp_if_same(field->getTable(), ref->key_buff, ref->key, prefix_len))
01046 {
01047 return 1;
01048 }
01049 if (! cond || (range_fl & (max_fl ? NO_MIN_RANGE : NO_MAX_RANGE)))
01050 {
01051 return 0;
01052 }
01053 return maxmin_in_range(max_fl, field, cond);
01054 }
01055
01056
01069 static int maxmin_in_range(bool max_fl, Field* field, COND *cond)
01070 {
01071
01072 if (cond->type() == Item::COND_ITEM)
01073 {
01074 List<Item>::iterator li(((Item_cond*) cond)->argument_list()->begin());
01075 Item *item;
01076 while ((item= li++))
01077 {
01078 if (maxmin_in_range(max_fl, field, item))
01079 {
01080 return 1;
01081 }
01082 }
01083 return 0;
01084 }
01085
01086 if (cond->used_tables() != field->getTable()->map)
01087 {
01088 return 0;
01089 }
01090 bool less_fl= false;
01091 switch (((Item_func*) cond)->functype())
01092 {
01093 case Item_func::BETWEEN:
01094 return cond->val_int() == 0;
01095 case Item_func::LT_FUNC:
01096 case Item_func::LE_FUNC:
01097 less_fl= 1;
01098 case Item_func::GT_FUNC:
01099 case Item_func::GE_FUNC:
01100 {
01101 Item *item= ((Item_func*) cond)->arguments()[1];
01102
01103 if (! item->const_item())
01104 {
01105 less_fl= 1-less_fl;
01106 }
01107
01108
01109
01110
01111
01112
01113 if (max_fl != less_fl)
01114 {
01115 return cond->val_int() == 0;
01116 }
01117 return 0;
01118 }
01119 case Item_func::EQ_FUNC:
01120 case Item_func::EQUAL_FUNC:
01121 break;
01122 default:
01123 assert(1);
01124 break;
01125 }
01126 return 0;
01127 }
01128
01129 }
01130