112#include <boost/dynamic_bitset.hpp>
114#include <drizzled/check_stack_overrun.h>
115#include <drizzled/error.h>
116#include <drizzled/field/num.h>
117#include <drizzled/internal/iocache.h>
118#include <drizzled/internal/my_sys.h>
119#include <drizzled/item/cmpfunc.h>
120#include <drizzled/optimizer/cost_vector.h>
121#include <drizzled/optimizer/quick_group_min_max_select.h>
122#include <drizzled/optimizer/quick_index_merge_select.h>
123#include <drizzled/optimizer/quick_range.h>
124#include <drizzled/optimizer/quick_range_select.h>
125#include <drizzled/optimizer/quick_ror_intersect_select.h>
126#include <drizzled/optimizer/quick_ror_union_select.h>
127#include <drizzled/optimizer/range.h>
128#include <drizzled/optimizer/range_param.h>
129#include <drizzled/optimizer/sel_arg.h>
130#include <drizzled/optimizer/sel_imerge.h>
131#include <drizzled/optimizer/sel_tree.h>
132#include <drizzled/optimizer/sum.h>
133#include <drizzled/optimizer/table_read_plan.h>
134#include <drizzled/plugin/storage_engine.h>
135#include <drizzled/records.h>
136#include <drizzled/sql_base.h>
137#include <drizzled/sql_select.h>
139#include <drizzled/session.h>
140#include <drizzled/key.h>
141#include <drizzled/unique.h>
143#include <drizzled/sql_lex.h>
144#include <drizzled/system_variables.h>
145#include <drizzled/key_part_info.h>
151static const int HA_END_SPACE_KEY= 0;
157static inline ha_rows double2rows(
double x)
159 return static_cast<ha_rows
>(x);
162static unsigned char is_null_string[2]= {1,0};
214 if (table->cursor->primary_key_is_clustered())
216 cost->setIOCount(table->cursor->read_time(table->getShare()->getPrimaryKey(),
217 static_cast<uint32_t
>(nrows),
223 ceil(
static_cast<double>(table->cursor->stats.data_file_length) / IO_SIZE);
225 n_blocks * (1.0 - pow(1.0 - 1.0/n_blocks,
static_cast<double>(nrows)));
226 if (busy_blocks < 1.0)
229 cost->setIOCount(busy_blocks);
234 cost->setAvgIOCost((DISK_SEEK_BASE_COST +
235 DISK_SEEK_PROP_COST*n_blocks/busy_blocks));
240static optimizer::SEL_TREE * get_mm_parts(optimizer::RangeParameter *param,
243 Item_func::Functype type,
245 Item_result cmp_type);
247static optimizer::SEL_ARG *get_mm_leaf(optimizer::RangeParameter *param,
251 Item_func::Functype type,
254static optimizer::SEL_TREE *get_mm_tree(optimizer::RangeParameter *param, COND *cond);
256static bool is_key_scan_ror(optimizer::Parameter *param, uint32_t keynr, uint8_t nparts);
258static ha_rows check_quick_select(Session *session,
259 optimizer::Parameter *param,
262 optimizer::SEL_ARG *tree,
263 bool update_tbl_stats,
266 optimizer::CostVector *cost);
268static optimizer::RangeReadPlan *get_key_scans_params(Session *session,
269 optimizer::Parameter *param,
270 optimizer::SEL_TREE *tree,
271 bool index_read_must_be_used,
272 bool update_tbl_stats,
276optimizer::RorIntersectReadPlan *get_best_ror_intersect(
const optimizer::Parameter *param,
277 optimizer::SEL_TREE *tree,
279 bool *are_all_covering);
282optimizer::RorIntersectReadPlan *get_best_covering_ror_intersect(optimizer::Parameter *param,
283 optimizer::SEL_TREE *tree,
287optimizer::TableReadPlan *get_best_disjunct_quick(Session *session,
288 optimizer::Parameter *param,
289 optimizer::SEL_IMERGE *imerge,
293optimizer::GroupMinMaxReadPlan *get_best_group_min_max(optimizer::Parameter *param, optimizer::SEL_TREE *tree);
295static optimizer::SEL_TREE *tree_and(optimizer::RangeParameter *param,
296 optimizer::SEL_TREE *tree1,
297 optimizer::SEL_TREE *tree2);
299static optimizer::SEL_ARG *sel_add(optimizer::SEL_ARG *key1, optimizer::SEL_ARG *key2);
301static optimizer::SEL_ARG *key_and(optimizer::RangeParameter *param,
302 optimizer::SEL_ARG *key1,
303 optimizer::SEL_ARG *key2,
304 uint32_t clone_flag);
306static bool get_range(optimizer::SEL_ARG **e1, optimizer::SEL_ARG **e2, optimizer::SEL_ARG *root1);
308optimizer::SEL_ARG optimizer::null_element(optimizer::SEL_ARG::IMPOSSIBLE);
310static bool null_part_in_key(KEY_PART *key_part,
311 const unsigned char *key,
314bool sel_trees_can_be_ored(optimizer::SEL_TREE *tree1,
315 optimizer::SEL_TREE *tree2,
316 optimizer::RangeParameter *param);
327inline void imerge_list_and_list(List<optimizer::SEL_IMERGE> *im1, List<optimizer::SEL_IMERGE> *im2)
344 table_map const_tables,
345 table_map read_tables,
347 bool allow_null_cond,
352 if (! conds && ! allow_null_cond)
357 select->read_tables=read_tables;
358 select->const_tables=const_tables;
362 if (head->sort.io_cache)
364 memcpy(
static_cast<void *
>(select->file),
365 static_cast<const void *
>(head->sort.io_cache),
367 select->records=(ha_rows) (select->file->end_of_file/
368 head->cursor->ref_length);
369 delete head->sort.io_cache;
370 head->sort.io_cache=0;
376optimizer::SqlSelect::SqlSelect()
380 file(static_cast<internal::io_cache_st *>(
memory::sql_calloc(sizeof(internal::io_cache_st)))),
389void optimizer::SqlSelect::cleanup()
400 file->close_cached_file();
404optimizer::SqlSelect::~SqlSelect()
410bool optimizer::SqlSelect::check_quick(Session *session,
411 bool force_quick_range,
416 return (test_quick_select(session,
425bool optimizer::SqlSelect::skip_record()
427 return (cond ? cond->val_int() == 0 : 0);
431optimizer::QuickSelectInterface::QuickSelectInterface()
433 max_used_key_length(0),
467uint32_t optimizer::get_index_for_order(Table *table, Order *order, ha_rows limit)
470 uint32_t match_key= MAX_KEY, match_key_len= MAX_KEY_LENGTH + 1;
473 for (ord= order; ord; ord= ord->next)
477 for (idx= 0; idx < table->getShare()->sizeKeys(); idx++)
479 if (!(table->keys_in_use_for_query.test(idx)))
481 KeyPartInfo *keyinfo= table->key_info[idx].key_part;
482 uint32_t n_parts= table->key_info[idx].key_parts;
490 if (! (table->index_flags(idx) & HA_READ_ORDER))
492 for (ord= order; ord && partno < n_parts; ord= ord->next, partno++)
494 Item *item= order->item[0];
495 if (! (item->type() == Item::FIELD_ITEM &&
496 ((Item_field*)item)->field->eq(keyinfo[partno].field)))
500 if (! ord && table->key_info[idx].key_length < match_key_len)
508 match_key_len= table->key_info[idx].key_length;
512 if (match_key != MAX_KEY)
519 double full_scan_time= table->cursor->scan_time();
520 double index_scan_time= table->cursor->read_time(match_key, 1, limit);
521 if (index_scan_time > full_scan_time)
543static int fill_used_fields_bitmap(optimizer::Parameter *param)
545 Table *table= param->table;
547 param->tmp_covered_fields.clear();
548 param->needed_fields.resize(table->getShare()->sizeFields());
549 param->needed_fields.reset();
551 param->needed_fields|= *table->read_set;
552 param->needed_fields|= *table->write_set;
554 pk= param->table->getShare()->getPrimaryKey();
555 if (pk != MAX_KEY && param->table->cursor->primary_key_is_clustered())
558 KeyPartInfo *key_part= param->table->key_info[pk].key_part;
559 KeyPartInfo *key_part_end= key_part +
560 param->table->key_info[pk].key_parts;
561 for (;key_part != key_part_end; ++key_part)
562 param->needed_fields.reset(key_part->fieldnr-1);
634int optimizer::SqlSelect::test_quick_select(Session *session,
636 table_map prev_tables,
638 bool force_quick_range,
649 if (keys_to_use.none())
651 records= head->cursor->stats.records;
655 read_time= (double) head->cursor->scan_time() + scan_time + 1.1;
656 if (head->force_index)
657 scan_time= read_time= DBL_MAX;
659 read_time= (double) records + scan_time + 1;
660 else if (read_time <= 2.0 && !force_quick_range)
663 keys_to_use&= head->keys_in_use_for_query;
664 if (keys_to_use.any())
667 optimizer::SEL_TREE *tree= NULL;
670 optimizer::Parameter param;
676 param.session= session;
677 param.prev_tables= prev_tables | const_tables;
678 param.read_tables= read_tables;
679 param.current_table= head->map;
682 param.mem_root= &alloc;
683 param.old_root= session->mem_root;
684 param.needed_reg= &needed_reg;
685 param.imerge_cost_buff_size= 0;
686 param.using_real_indexes=
true;
687 param.remove_jump_scans=
true;
688 param.force_default_mrr= ordered_output;
690 session->no_errors=1;
691 alloc.init(session->variables.range_alloc_block_size);
692 param.key_parts=
new (alloc) KEY_PART[head->getShare()->key_parts];
693 if (fill_used_fields_bitmap(¶m))
695 session->no_errors=0;
696 alloc.free_root(MYF(0));
700 key_parts= param.key_parts;
701 session->mem_root= &alloc;
707 key_info= head->key_info;
708 for (idx=0 ; idx < head->getShare()->sizeKeys() ; idx++, key_info++)
710 KeyPartInfo *key_part_info;
711 if (! keys_to_use.test(idx))
714 param.key[param.keys]=key_parts;
715 key_part_info= key_info->key_part;
716 for (uint32_t part=0;
717 part < key_info->key_parts;
718 part++, key_parts++, key_part_info++)
720 key_parts->key= param.keys;
721 key_parts->part= part;
722 key_parts->length= key_part_info->length;
723 key_parts->store_length= key_part_info->store_length;
724 key_parts->field= key_part_info->field;
725 key_parts->null_bit= key_part_info->null_bit;
727 key_parts->flag= (uint8_t) key_part_info->key_part_flag;
729 param.real_keynr[param.keys++]=idx;
731 param.key_parts_end=key_parts;
732 param.alloced_sel_args= 0;
735 if (!head->covering_keys.none())
737 int key_for_use= head->find_shortest_key(&head->covering_keys);
738 double key_read_time=
739 param.table->cursor->index_only_read_time(key_for_use, records) +
741 if (key_read_time < read_time)
742 read_time= key_read_time;
745 optimizer::TableReadPlan *best_trp= NULL;
746 optimizer::GroupMinMaxReadPlan *group_trp= NULL;
747 double best_read_time= read_time;
751 if ((tree= get_mm_tree(¶m,cond)))
753 if (tree->type == optimizer::SEL_TREE::IMPOSSIBLE)
756 read_time= (double) HA_POS_ERROR;
763 if (tree->type != optimizer::SEL_TREE::KEY && tree->type != optimizer::SEL_TREE::KEY_SMALLER)
772 group_trp= get_best_group_min_max(¶m, tree);
775 param.table->quick_condition_rows= min(group_trp->records,
776 head->cursor->stats.records);
777 if (group_trp->read_cost < best_read_time)
780 best_read_time= best_trp->read_cost;
790 if (tree->merges.is_empty())
792 optimizer::RangeReadPlan *range_trp= NULL;
793 optimizer::RorIntersectReadPlan *rori_trp= NULL;
794 bool can_build_covering=
false;
797 if ((range_trp= get_key_scans_params(session, ¶m, tree,
false,
true,
801 best_read_time= best_trp->read_cost;
809 if ((session->lex().sql_command != SQLCOM_DELETE))
815 if ((rori_trp= get_best_ror_intersect(¶m, tree, best_read_time,
816 &can_build_covering)))
819 best_read_time= best_trp->read_cost;
824 if (!rori_trp->is_covering && can_build_covering &&
825 (rori_trp= get_best_covering_ror_intersect(¶m, tree,
834 optimizer::SEL_IMERGE *imerge= NULL;
835 optimizer::TableReadPlan *best_conj_trp= NULL;
836 optimizer::TableReadPlan *new_conj_trp= NULL;
837 List<optimizer::SEL_IMERGE>::iterator it(tree->merges.begin());
838 while ((imerge= it++))
840 new_conj_trp= get_best_disjunct_quick(session, ¶m, imerge, best_read_time);
842 set_if_smaller(param.table->quick_condition_rows,
843 new_conj_trp->records);
844 if (!best_conj_trp || (new_conj_trp && new_conj_trp->read_cost <
845 best_conj_trp->read_cost))
846 best_conj_trp= new_conj_trp;
849 best_trp= best_conj_trp;
853 session->mem_root= param.old_root;
858 records= best_trp->records;
859 if (! (quick= best_trp->make_quick(¶m,
true)) || quick->init())
867 alloc.free_root(MYF(0));
868 session->mem_root= param.old_root;
869 session->no_errors=0;
876 return(records ? test(quick) : -1);
946optimizer::TableReadPlan *get_best_disjunct_quick(Session *session,
947 optimizer::Parameter *param,
948 optimizer::SEL_IMERGE *imerge,
951 optimizer::SEL_TREE **ptree= NULL;
952 optimizer::IndexMergeReadPlan *imerge_trp= NULL;
953 uint32_t n_child_scans= imerge->trees_next - imerge->trees;
954 optimizer::RangeReadPlan **range_scans= NULL;
955 optimizer::RangeReadPlan **cur_child= NULL;
956 optimizer::RangeReadPlan **cpk_scan= NULL;
957 bool imerge_too_expensive=
false;
958 double imerge_cost= 0.0;
959 ha_rows cpk_scan_records= 0;
960 ha_rows non_cpk_scan_records= 0;
961 bool pk_is_clustered= param->table->cursor->primary_key_is_clustered();
962 bool all_scans_ror_able=
true;
963 bool all_scans_rors=
true;
964 uint32_t unique_calc_buff_size;
965 optimizer::TableReadPlan **roru_read_plans= NULL;
966 optimizer::TableReadPlan **cur_roru_plan= NULL;
967 double roru_index_costs;
968 ha_rows roru_total_records;
969 double roru_intersect_part= 1.0;
971 range_scans=
new (*param->mem_root) optimizer::RangeReadPlan*[n_child_scans];
978 for (ptree= imerge->trees, cur_child= range_scans; ptree != imerge->trees_next; ptree++, cur_child++)
980 if (!(*cur_child= get_key_scans_params(session, param, *ptree,
true,
false, read_time)))
988 imerge_too_expensive=
true;
990 if (imerge_too_expensive)
993 imerge_cost += (*cur_child)->read_cost;
994 all_scans_ror_able &= ((*ptree)->n_ror_scans > 0);
995 all_scans_rors &= (*cur_child)->is_ror;
996 if (pk_is_clustered &&
997 param->real_keynr[(*cur_child)->key_idx] ==
998 param->table->getShare()->getPrimaryKey())
1000 cpk_scan= cur_child;
1001 cpk_scan_records= (*cur_child)->records;
1004 non_cpk_scan_records += (*cur_child)->records;
1007 if (imerge_too_expensive || (imerge_cost > read_time) ||
1008 ((non_cpk_scan_records+cpk_scan_records >= param->table->cursor->stats.records) && compare_ne_double(read_time, DBL_MAX)))
1018 roru_read_plans= (optimizer::TableReadPlan **) range_scans;
1019 goto skip_to_ror_scan;
1032 optimizer::CostVector sweep_cost;
1033 Join *join= param->session->lex().select_lex.join;
1034 bool is_interrupted= test(join && join->tables == 1);
1037 imerge_cost += sweep_cost.total_cost();
1039 if (imerge_cost > read_time)
1040 goto build_ror_index_merge;
1043 unique_calc_buff_size=
1044 Unique::get_cost_calc_buff_size((ulong)non_cpk_scan_records,
1045 param->table->cursor->ref_length,
1046 param->session->variables.sortbuff_size);
1047 if (param->imerge_cost_buff_size < unique_calc_buff_size)
1049 param->imerge_cost_buff= (uint*)param->mem_root->alloc(unique_calc_buff_size);
1050 param->imerge_cost_buff_size= unique_calc_buff_size;
1054 Unique::get_use_cost(param->imerge_cost_buff, (uint32_t)non_cpk_scan_records,
1055 param->table->cursor->ref_length,
1056 param->session->variables.sortbuff_size);
1057 if (imerge_cost < read_time)
1059 imerge_trp=
new (*param->mem_root) optimizer::IndexMergeReadPlan;
1060 imerge_trp->read_cost= imerge_cost;
1061 imerge_trp->records= non_cpk_scan_records + cpk_scan_records;
1062 imerge_trp->records= min(imerge_trp->records, param->table->cursor->stats.records);
1063 imerge_trp->range_scans= range_scans;
1064 imerge_trp->range_scans_end= range_scans + n_child_scans;
1065 read_time= imerge_cost;
1068build_ror_index_merge:
1069 if (!all_scans_ror_able || param->session->lex().sql_command == SQLCOM_DELETE)
1074 roru_read_plans=
new (*param->mem_root) optimizer::TableReadPlan*[n_child_scans];
1076 roru_index_costs= 0.0;
1077 roru_total_records= 0;
1078 cur_roru_plan= roru_read_plans;
1081 for (ptree= imerge->trees, cur_child= range_scans;
1082 ptree != imerge->trees_next;
1083 ptree++, cur_child++, cur_roru_plan++)
1092 if ((*cur_child)->is_ror)
1095 cost= param->table->cursor->
1096 read_time(param->real_keynr[(*cur_child)->key_idx], 1,
1097 (*cur_child)->records) +
1103 optimizer::TableReadPlan *prev_plan= *cur_child;
1104 if (!(*cur_roru_plan= get_best_ror_intersect(param, *ptree, cost,
1107 if (prev_plan->is_ror)
1108 *cur_roru_plan= prev_plan;
1111 roru_index_costs += (*cur_roru_plan)->read_cost;
1115 ((optimizer::RorIntersectReadPlan*)(*cur_roru_plan))->index_scan_costs;
1116 roru_total_records += (*cur_roru_plan)->records;
1117 roru_intersect_part *= (*cur_roru_plan)->records /
1118 param->table->cursor->stats.records;
1127 roru_total_records -= (ha_rows)(roru_intersect_part*
1128 param->table->cursor->stats.records);
1137 double roru_total_cost;
1139 optimizer::CostVector sweep_cost;
1140 Join *join= param->session->lex().select_lex.join;
1141 bool is_interrupted= test(join && join->tables == 1);
1144 roru_total_cost= roru_index_costs +
1145 static_cast<double>(roru_total_records)*log((
double)n_child_scans) /
1147 sweep_cost.total_cost();
1150 optimizer::RorUnionReadPlan *roru= NULL;
1151 if (roru_total_cost < read_time)
1153 if ((roru=
new (*param->mem_root) optimizer::RorUnionReadPlan))
1155 roru->first_ror= roru_read_plans;
1156 roru->last_ror= roru_read_plans + n_child_scans;
1157 roru->read_cost= roru_total_cost;
1158 roru->records= roru_total_records;
1183optimizer::RorScanInfo *make_ror_scan(
const optimizer::Parameter *param,
int idx, optimizer::SEL_ARG *sel_arg)
1186 optimizer::RorScanInfo* ror_scan=
new (*param->mem_root) optimizer::RorScanInfo;
1189 ror_scan->keynr= keynr= param->real_keynr[idx];
1190 ror_scan->key_rec_length= (param->table->key_info[keynr].key_length +
1191 param->table->cursor->ref_length);
1192 ror_scan->sel_arg= sel_arg;
1193 ror_scan->records= param->table->quick_rows[keynr];
1195 ror_scan->covered_fields_size= param->table->getShare()->sizeFields();
1196 boost::dynamic_bitset<> tmp_bitset(param->table->getShare()->sizeFields());
1199 KeyPartInfo *key_part= param->table->key_info[keynr].key_part;
1200 KeyPartInfo *key_part_end= key_part +
1201 param->table->key_info[keynr].key_parts;
1202 for (; key_part != key_part_end; ++key_part)
1204 if (param->needed_fields.test(key_part->fieldnr-1))
1205 tmp_bitset.set(key_part->fieldnr-1);
1207 double rows= param->table->quick_rows[ror_scan->keynr];
1208 ror_scan->index_read_cost=
1209 param->table->cursor->index_only_read_time(ror_scan->keynr, rows);
1210 ror_scan->covered_fields= tmp_bitset.to_ulong();
1228static int cmp_ror_scan_info(optimizer::RorScanInfo** a, optimizer::RorScanInfo** b)
1230 double val1=
static_cast<double>((*a)->records) * (*a)->key_rec_length;
1231 double val2=
static_cast<double>((*b)->records) * (*b)->key_rec_length;
1232 return (val1 < val2)? -1: (compare_double(val1, val2))? 0 : 1;
1253static int cmp_ror_scan_info_covering(optimizer::RorScanInfo** a, optimizer::RorScanInfo** b)
1255 if ((*a)->used_fields_covered > (*b)->used_fields_covered)
1257 if ((*a)->used_fields_covered < (*b)->used_fields_covered)
1259 if ((*a)->key_components < (*b)->key_components)
1261 if ((*a)->key_components > (*b)->key_components)
1263 if ((*a)->first_uncovered_field < (*b)->first_uncovered_field)
1265 if ((*a)->first_uncovered_field > (*b)->first_uncovered_field)
1271typedef struct st_ror_intersect_info
1273 st_ror_intersect_info()
1280 index_scan_costs(0.0),
1287 covered_fields(in_param->table->getShare()->sizeFields()),
1288 out_rows(in_param->table->
cursor->stats.records),
1291 index_scan_costs(0.0),
1294 covered_fields.reset();
1298 boost::dynamic_bitset<> covered_fields;
1308 ha_rows index_records;
1309 double index_scan_costs;
1311} ROR_INTERSECT_INFO;
1314static void ror_intersect_cpy(ROR_INTERSECT_INFO *dst,
1315 const ROR_INTERSECT_INFO *src)
1317 dst->param= src->param;
1318 dst->covered_fields= src->covered_fields;
1319 dst->out_rows= src->out_rows;
1320 dst->is_covering= src->is_covering;
1321 dst->index_records= src->index_records;
1322 dst->index_scan_costs= src->index_scan_costs;
1323 dst->total_cost= src->total_cost;
1417static double ror_scan_selectivity(
const ROR_INTERSECT_INFO *info,
1418 const optimizer::RorScanInfo *scan)
1420 double selectivity_mult= 1.0;
1421 KeyPartInfo *key_part= info->param->table->key_info[scan->keynr].key_part;
1422 unsigned char key_val[MAX_KEY_LENGTH+MAX_FIELD_WIDTH];
1423 unsigned char *key_ptr= key_val;
1424 optimizer::SEL_ARG *sel_arg= NULL;
1425 optimizer::SEL_ARG *tuple_arg= NULL;
1426 key_part_map keypart_map= 0;
1428 bool prev_covered= test(info->covered_fields.test(key_part->fieldnr-1));
1429 key_range min_range;
1430 key_range max_range;
1431 min_range.key= key_val;
1432 min_range.flag= HA_READ_KEY_EXACT;
1433 max_range.key= key_val;
1434 max_range.flag= HA_READ_AFTER_KEY;
1435 ha_rows prev_records= info->param->table->cursor->stats.records;
1437 for (sel_arg= scan->sel_arg; sel_arg;
1438 sel_arg= sel_arg->next_key_part)
1441 test(info->covered_fields.test(key_part[sel_arg->part].fieldnr-1));
1442 if (cur_covered != prev_covered)
1448 tuple_arg= scan->sel_arg;
1450 tuple_arg->store_min(key_part->store_length, &key_ptr, 0);
1453 while (tuple_arg->next_key_part != sel_arg)
1455 tuple_arg= tuple_arg->next_key_part;
1456 tuple_arg->store_min(key_part[tuple_arg->part].store_length,
1458 keypart_map= (keypart_map << 1) | 1;
1460 min_range.length= max_range.length= (size_t) (key_ptr - key_val);
1461 min_range.keypart_map= max_range.keypart_map= keypart_map;
1462 records= (info->param->table->cursor->
1463 records_in_range(scan->keynr, &min_range, &max_range));
1467 selectivity_mult *=
static_cast<double>(records) / prev_records;
1468 prev_records= HA_POS_ERROR;
1473 prev_records= records;
1476 prev_covered= cur_covered;
1480 selectivity_mult *=
static_cast<double>(info->param->table->quick_rows[scan->keynr]) / prev_records;
1482 return selectivity_mult;
1522static bool ror_intersect_add(ROR_INTERSECT_INFO *info,
1523 optimizer::RorScanInfo* ror_scan,
bool is_cpk_scan)
1525 double selectivity_mult= 1.0;
1527 selectivity_mult = ror_scan_selectivity(info, ror_scan);
1528 if (compare_double(selectivity_mult, 1.0))
1534 info->out_rows *= selectivity_mult;
1543 info->index_scan_costs +=
static_cast<double>(info->index_records) /
1548 info->index_records += info->param->table->quick_rows[ror_scan->keynr];
1549 info->index_scan_costs += ror_scan->index_read_cost;
1550 boost::dynamic_bitset<> tmp_bitset= ror_scan->bitsToBitset();
1551 info->covered_fields|= tmp_bitset;
1552 if (! info->is_covering && info->param->needed_fields.is_subset_of(info->covered_fields))
1554 info->is_covering=
true;
1558 info->total_cost= info->index_scan_costs;
1559 if (! info->is_covering)
1561 optimizer::CostVector sweep_cost;
1562 Join *join= info->param->session->lex().select_lex.join;
1563 bool is_interrupted= test(join && join->tables == 1);
1565 is_interrupted, &sweep_cost);
1566 info->total_cost += sweep_cost.total_cost();
1606optimizer::RorIntersectReadPlan *get_best_covering_ror_intersect(optimizer::Parameter *param,
1607 optimizer::SEL_TREE *tree,
1610 optimizer::RorScanInfo **ror_scan_mark;
1611 optimizer::RorScanInfo **ror_scans_end= tree->ror_scans_end;
1613 for (optimizer::RorScanInfo **scan= tree->ror_scans; scan != ror_scans_end; ++scan)
1614 (*scan)->key_components=
1615 param->table->key_info[(*scan)->keynr].key_parts;
1623 ror_scan_mark= tree->ror_scans;
1625 boost::dynamic_bitset<> *covered_fields= ¶m->tmp_covered_fields;
1626 if (covered_fields->empty())
1628 covered_fields->resize(param->table->getShare()->sizeFields());
1630 covered_fields->reset();
1632 double total_cost= 0.0f;
1644 for (optimizer::RorScanInfo **scan= ror_scan_mark; scan != ror_scans_end; ++scan)
1647 (*scan)->subtractBitset(*covered_fields);
1648 (*scan)->used_fields_covered=
1649 (*scan)->getBitCount();
1650 (*scan)->first_uncovered_field= (*scan)->findFirstNotSet();
1653 internal::my_qsort(ror_scan_mark, ror_scans_end-ror_scan_mark,
1654 sizeof(optimizer::RorScanInfo*),
1655 (qsort_cmp)cmp_ror_scan_info_covering);
1658 total_cost += (*ror_scan_mark)->index_read_cost;
1659 records += (*ror_scan_mark)->records;
1660 if (total_cost > read_time)
1663 boost::dynamic_bitset<> tmp_bitset= (*ror_scan_mark)->bitsToBitset();
1664 *covered_fields|= tmp_bitset;
1665 all_covered= param->needed_fields.is_subset_of(*covered_fields);
1666 }
while ((++ror_scan_mark < ror_scans_end) && ! all_covered);
1668 if (!all_covered || (ror_scan_mark - tree->ror_scans) == 1)
1676 total_cost +=
static_cast<double>(records) *
1677 log((
double)(ror_scan_mark - tree->ror_scans)) /
1680 if (total_cost > read_time)
1683 optimizer::RorIntersectReadPlan* trp=
new (*param->mem_root) optimizer::RorIntersectReadPlan;
1685 uint32_t best_num= (ror_scan_mark - tree->ror_scans);
1686 trp->first_scan=
new (*param->mem_root) optimizer::RorScanInfo*[best_num];
1687 memcpy(trp->first_scan, tree->ror_scans, best_num*
sizeof(optimizer::RorScanInfo*));
1688 trp->last_scan= trp->first_scan + best_num;
1689 trp->is_covering=
true;
1690 trp->read_cost= total_cost;
1691 trp->records= records;
1692 trp->cpk_scan= NULL;
1693 set_if_smaller(param->table->quick_condition_rows, records);
1764optimizer::RorIntersectReadPlan *get_best_ror_intersect(
const optimizer::Parameter *param,
1765 optimizer::SEL_TREE *tree,
1767 bool *are_all_covering)
1770 double min_cost= DBL_MAX;
1772 if ((tree->n_ror_scans < 2) || ! param->table->cursor->stats.records)
1779 optimizer::RorScanInfo **cur_ror_scan= NULL;
1780 optimizer::RorScanInfo *cpk_scan= NULL;
1782 bool cpk_scan_used=
false;
1784 tree->ror_scans=
new (*param->mem_root) optimizer::RorScanInfo*[param->keys];
1785 cpk_no= ((param->table->cursor->primary_key_is_clustered()) ? param->table->getShare()->getPrimaryKey() : MAX_KEY);
1787 for (idx= 0, cur_ror_scan= tree->ror_scans; idx < param->keys; idx++)
1789 optimizer::RorScanInfo *scan;
1790 if (! tree->ror_scans_map.test(idx))
1792 if (! (scan= make_ror_scan(param, idx, tree->keys[idx])))
1794 if (param->real_keynr[idx] == cpk_no)
1797 tree->n_ror_scans--;
1800 *(cur_ror_scan++)= scan;
1803 tree->ror_scans_end= cur_ror_scan;
1809 internal::my_qsort(tree->ror_scans, tree->n_ror_scans,
sizeof(optimizer::RorScanInfo*),
1810 (qsort_cmp)cmp_ror_scan_info);
1812 optimizer::RorScanInfo **intersect_scans= NULL;
1813 optimizer::RorScanInfo **intersect_scans_end= intersect_scans=
new (*param->mem_root) optimizer::RorScanInfo*[tree->n_ror_scans];
1814 intersect_scans_end= intersect_scans;
1817 ROR_INTERSECT_INFO intersect(param);
1818 ROR_INTERSECT_INFO intersect_best(param);
1821 optimizer::RorScanInfo **intersect_scans_best= NULL;
1822 cur_ror_scan= tree->ror_scans;
1823 intersect_scans_best= intersect_scans;
1824 while (cur_ror_scan != tree->ror_scans_end && ! intersect.is_covering)
1827 if (! ror_intersect_add(&intersect, *cur_ror_scan,
false))
1833 *(intersect_scans_end++)= *(cur_ror_scan++);
1835 if (intersect.total_cost < min_cost)
1838 ror_intersect_cpy(&intersect_best, &intersect);
1839 intersect_scans_best= intersect_scans_end;
1840 min_cost = intersect.total_cost;
1844 if (intersect_scans_best == intersect_scans)
1849 *are_all_covering= intersect.is_covering;
1850 uint32_t best_num= intersect_scans_best - intersect_scans;
1851 ror_intersect_cpy(&intersect, &intersect_best);
1858 if (cpk_scan && ! intersect.is_covering)
1860 if (ror_intersect_add(&intersect, cpk_scan,
true) &&
1861 (intersect.total_cost < min_cost))
1863 cpk_scan_used=
true;
1864 intersect_best= intersect;
1869 optimizer::RorIntersectReadPlan *trp= NULL;
1870 if (min_cost < read_time && (cpk_scan_used || best_num > 1))
1872 trp=
new (*param->mem_root) optimizer::RorIntersectReadPlan;
1873 trp->first_scan=
new (*param->mem_root) optimizer::RorScanInfo*[best_num];
1874 memcpy(trp->first_scan, intersect_scans, best_num*
sizeof(optimizer::RorScanInfo*));
1875 trp->last_scan= trp->first_scan + best_num;
1876 trp->is_covering= intersect_best.is_covering;
1877 trp->read_cost= intersect_best.total_cost;
1879 ha_rows best_rows = double2rows(intersect_best.out_rows);
1882 set_if_smaller(param->table->quick_condition_rows, best_rows);
1883 trp->records= best_rows;
1884 trp->index_scan_costs= intersect_best.index_scan_costs;
1885 trp->cpk_scan= cpk_scan_used? cpk_scan: NULL;
1918static optimizer::RangeReadPlan *get_key_scans_params(Session *session,
1919 optimizer::Parameter *param,
1920 optimizer::SEL_TREE *tree,
1921 bool index_read_must_be_used,
1922 bool update_tbl_stats,
1926 optimizer::SEL_ARG **key= NULL;
1927 optimizer::SEL_ARG **end= NULL;
1928 optimizer::SEL_ARG **key_to_read= NULL;
1929 ha_rows best_records= 0;
1930 uint32_t best_mrr_flags= 0;
1931 uint32_t best_buf_size= 0;
1932 optimizer::RangeReadPlan *read_plan= NULL;
1938 tree->ror_scans_map.reset();
1939 tree->n_ror_scans= 0;
1940 for (idx= 0,key=tree->keys, end=key+param->keys; key != end; key++,idx++)
1944 ha_rows found_records;
1945 optimizer::CostVector cost;
1946 double found_read_time= 0.0;
1947 uint32_t mrr_flags, buf_size;
1948 uint32_t keynr= param->real_keynr[idx];
1949 if ((*key)->type == optimizer::SEL_ARG::MAYBE_KEY ||
1951 param->needed_reg->set(keynr);
1953 bool read_index_only= index_read_must_be_used ||
1954 param->table->covering_keys.test(keynr);
1956 found_records= check_quick_select(session, param, idx, read_index_only, *key,
1957 update_tbl_stats, &mrr_flags,
1959 found_read_time= cost.total_cost();
1960 if ((found_records != HA_POS_ERROR) && param->is_ror_scan)
1962 tree->n_ror_scans++;
1963 tree->ror_scans_map.set(idx);
1965 if (read_time > found_read_time && found_records != HA_POS_ERROR)
1967 read_time= found_read_time;
1968 best_records= found_records;
1970 best_mrr_flags= mrr_flags;
1971 best_buf_size= buf_size;
1978 idx= key_to_read - tree->keys;
1979 read_plan=
new (*param->mem_root) optimizer::RangeReadPlan(*key_to_read, idx, best_mrr_flags);
1980 read_plan->records= best_records;
1981 read_plan->is_ror= tree->ror_scans_map.test(idx);
1982 read_plan->read_cost= read_time;
1983 read_plan->mrr_buf_size= best_buf_size;
1989optimizer::QuickSelectInterface *optimizer::IndexMergeReadPlan::make_quick(optimizer::Parameter *param,
bool, memory::Root *)
1992 optimizer::QuickIndexMergeSelect* quick_imerge=
new optimizer::QuickIndexMergeSelect(param->session, param->table);
1993 quick_imerge->records= records;
1994 quick_imerge->read_time= read_cost;
1995 for (optimizer::RangeReadPlan **range_scan= range_scans; range_scan != range_scans_end; range_scan++)
1997 optimizer::QuickRangeSelect* quick= (optimizer::QuickRangeSelect*)((*range_scan)->make_quick(param,
false, &quick_imerge->alloc));
2001 delete quick_imerge;
2004 quick_imerge->push_quick_back(quick);
2006 return quick_imerge;
2009optimizer::QuickSelectInterface *optimizer::RorIntersectReadPlan::make_quick(optimizer::Parameter *param,
2010 bool retrieve_full_rows,
2011 memory::Root *parent_alloc)
2013 optimizer::QuickRorIntersectSelect *quick_intersect= NULL;
2014 optimizer::QuickRangeSelect *quick= NULL;
2015 memory::Root *alloc= NULL;
2017 if ((quick_intersect=
2018 new optimizer::QuickRorIntersectSelect(param->session,
2020 (retrieve_full_rows? (! is_covering) :
false),
2023 alloc= parent_alloc ? parent_alloc : &quick_intersect->alloc;
2024 for (; first_scan != last_scan; ++first_scan)
2026 if (! (quick= optimizer::get_quick_select(param,
2028 (*first_scan)->sel_arg,
2029 HA_MRR_USE_DEFAULT_IMPL | HA_MRR_SORTED,
2033 delete quick_intersect;
2036 quick_intersect->push_quick_back(quick);
2040 if (! (quick= optimizer::get_quick_select(param,
2043 HA_MRR_USE_DEFAULT_IMPL | HA_MRR_SORTED,
2047 delete quick_intersect;
2050 quick->resetCursor();
2051 quick_intersect->cpk_quick= quick;
2053 quick_intersect->records= records;
2054 quick_intersect->read_time= read_cost;
2056 return quick_intersect;
2060optimizer::QuickSelectInterface *optimizer::RorUnionReadPlan::make_quick(optimizer::Parameter *param,
bool, memory::Root *)
2066 optimizer::QuickRorUnionSelect* quick_roru=
new optimizer::QuickRorUnionSelect(param->session, param->table);
2067 for (optimizer::TableReadPlan** scan= first_ror; scan != last_ror; scan++)
2069 optimizer::QuickSelectInterface* quick= (*scan)->make_quick(param,
false, &quick_roru->alloc);
2072 quick_roru->push_quick_back(quick);
2074 quick_roru->records= records;
2075 quick_roru->read_time= read_cost;
2096static optimizer::SEL_TREE *get_ne_mm_tree(optimizer::RangeParameter *param,
2097 Item_func *cond_func,
2099 Item *lt_value, Item *gt_value,
2100 Item_result cmp_type)
2102 optimizer::SEL_TREE *tree= NULL;
2103 tree= get_mm_parts(param, cond_func, field, Item_func::LT_FUNC,
2104 lt_value, cmp_type);
2107 tree= tree_or(param,
2109 get_mm_parts(param, cond_func, field,
2134static optimizer::SEL_TREE *get_func_mm_tree(optimizer::RangeParameter *param,
2135 Item_func *cond_func,
2138 Item_result cmp_type,
2141 optimizer::SEL_TREE *tree= NULL;
2143 switch (cond_func->functype())
2146 case Item_func::NE_FUNC:
2147 tree= get_ne_mm_tree(param, cond_func, field, value, value, cmp_type);
2150 case Item_func::BETWEEN:
2156 tree= get_ne_mm_tree(param,
2159 cond_func->arguments()[1],
2160 cond_func->arguments()[2],
2165 tree= get_mm_parts(param,
2169 cond_func->arguments()[1],
2173 tree= tree_and(param,
2175 get_mm_parts(param, cond_func, field,
2177 cond_func->arguments()[2],
2183 tree= get_mm_parts(param,
2187 (value == (Item*)1 ? Item_func::GT_FUNC :
2188 Item_func::LT_FUNC):
2189 (value == (Item*)1 ? Item_func::LE_FUNC :
2190 Item_func::GE_FUNC)),
2191 cond_func->arguments()[0],
2195 case Item_func::IN_FUNC:
2197 Item_func_in *func= (Item_func_in*) cond_func;
2204 if (! func->arg_types_compatible)
2209 if (func->array && func->array->result_type() != ROW_RESULT)
2238 const unsigned int NOT_IN_IGNORE_THRESHOLD= 1000;
2239 memory::Root *tmp_root= param->mem_root;
2240 param->session->mem_root= param->old_root;
2249 Item *value_item= func->array->create_item();
2250 param->session->mem_root= tmp_root;
2252 if (func->array->count > NOT_IN_IGNORE_THRESHOLD || ! value_item)
2259 func->array->value_to_item(i, value_item);
2260 tree= get_mm_parts(param,
2262 field, Item_func::LT_FUNC,
2268 }
while (i < func->array->count && tree->type == optimizer::SEL_TREE::IMPOSSIBLE);
2270 if (!tree || tree->type == optimizer::SEL_TREE::IMPOSSIBLE)
2276 optimizer::SEL_TREE *tree2= NULL;
2277 for (; i < func->array->count; i++)
2279 if (func->array->compare_elems(i, i-1))
2282 func->array->value_to_item(i, value_item);
2283 tree2= get_mm_parts(param, cond_func, field, Item_func::LT_FUNC,
2284 value_item, cmp_type);
2292 for (uint32_t idx= 0; idx < param->keys; idx++)
2294 optimizer::SEL_ARG *new_interval, *last_val;
2295 if (((new_interval= tree2->keys[idx])) &&
2296 (tree->keys[idx]) &&
2297 ((last_val= tree->keys[idx]->last())))
2299 new_interval->min_value= last_val->max_value;
2300 new_interval->min_flag= NEAR_MIN;
2307 tree= tree_or(param, tree, tree2);
2311 if (tree && tree->type != optimizer::SEL_TREE::IMPOSSIBLE)
2317 tree2= get_mm_parts(param, cond_func, field, Item_func::GT_FUNC,
2318 value_item, cmp_type);
2319 tree= tree_or(param, tree, tree2);
2324 tree= get_ne_mm_tree(param, cond_func, field,
2325 func->arguments()[1], func->arguments()[1],
2330 for (arg= func->arguments()+2, end= arg+func->argument_count()-2;
2333 tree= tree_and(param, tree, get_ne_mm_tree(param, cond_func, field,
2334 *arg, *arg, cmp_type));
2341 tree= get_mm_parts(param, cond_func, field, Item_func::EQ_FUNC,
2342 func->arguments()[1], cmp_type);
2346 for (arg= func->arguments()+2, end= arg+func->argument_count()-2;
2349 tree= tree_or(param, tree, get_mm_parts(param, cond_func, field,
2366 Item_func::Functype func_type=
2367 (value != cond_func->arguments()[0]) ? cond_func->functype() :
2368 ((Item_bool_func2*) cond_func)->rev_functype();
2369 tree= get_mm_parts(param, cond_func, field, func_type, value, cmp_type);
2447static optimizer::SEL_TREE *get_full_func_mm_tree(optimizer::RangeParameter *param,
2448 Item_func *cond_func,
2449 Item_field *field_item, Item *value,
2452 optimizer::SEL_TREE *tree= 0;
2453 optimizer::SEL_TREE *ftree= 0;
2454 table_map ref_tables= 0;
2455 table_map param_comp= ~(param->prev_tables | param->read_tables |
2456 param->current_table);
2458 for (uint32_t i= 0; i < cond_func->arg_count; i++)
2460 Item *arg= cond_func->arguments()[i]->real_item();
2461 if (arg != field_item)
2462 ref_tables|= arg->used_tables();
2465 Field *field= field_item->field;
2466 field->setWriteSet();
2468 Item_result cmp_type= field->cmp_type();
2469 if (!((ref_tables | field->getTable()->map) & param_comp))
2470 ftree= get_func_mm_tree(param, cond_func, field, value, cmp_type, inv);
2471 Item_equal *item_equal= field_item->item_equal;
2474 Item_equal_iterator it(item_equal->begin());
2476 while ((item= it++))
2478 Field *f= item->field;
2483 if (!((ref_tables | f->getTable()->map) & param_comp))
2485 tree= get_func_mm_tree(param, cond_func, f, value, cmp_type, inv);
2486 ftree= !ftree ? tree : tree_and(param, ftree, tree);
2495static optimizer::SEL_TREE *get_mm_tree(optimizer::RangeParameter *param, COND *cond)
2497 optimizer::SEL_TREE *tree=0;
2498 optimizer::SEL_TREE *ftree= 0;
2499 Item_field *field_item= 0;
2503 if (cond->type() == Item::COND_ITEM)
2505 List<Item>::iterator li(((Item_cond*) cond)->argument_list()->begin());
2507 if (((Item_cond*) cond)->functype() == Item_func::COND_AND_FUNC)
2510 while (Item* item=li++)
2512 optimizer::SEL_TREE *new_tree= get_mm_tree(param,item);
2513 if (param->session->is_fatal_error ||
2514 param->alloced_sel_args > optimizer::SEL_ARG::MAX_SEL_ARGS)
2516 tree=tree_and(param,tree,new_tree);
2517 if (tree && tree->type == optimizer::SEL_TREE::IMPOSSIBLE)
2523 tree= get_mm_tree(param,li++);
2526 while (Item* item= li++)
2528 optimizer::SEL_TREE *new_tree= get_mm_tree(param,item);
2531 tree=tree_or(param,tree,new_tree);
2532 if (!tree || tree->type == optimizer::SEL_TREE::ALWAYS)
2543 if (cond->const_item() && !cond->is_expensive())
2551 memory::Root *tmp_root= param->mem_root;
2552 param->session->mem_root= param->old_root;
2553 tree= cond->val_int() ?
new(tmp_root) optimizer::SEL_TREE(optimizer::SEL_TREE::ALWAYS) :
2554 new(tmp_root) optimizer::SEL_TREE(optimizer::SEL_TREE::IMPOSSIBLE);
2555 param->session->mem_root= tmp_root;
2559 table_map ref_tables= 0;
2560 table_map param_comp= ~(param->prev_tables | param->read_tables |
2561 param->current_table);
2562 if (cond->type() != Item::FUNC_ITEM)
2564 ref_tables= cond->used_tables();
2565 if ((ref_tables & param->current_table) ||
2566 (ref_tables & ~(param->prev_tables | param->read_tables)))
2568 return(
new optimizer::SEL_TREE(optimizer::SEL_TREE::MAYBE));
2571 Item_func *cond_func= (Item_func*) cond;
2572 if (cond_func->functype() == Item_func::BETWEEN ||
2573 cond_func->functype() == Item_func::IN_FUNC)
2574 inv= ((Item_func_opt_neg *) cond_func)->negated;
2575 else if (cond_func->select_optimize() == Item_func::OPTIMIZE_NONE)
2580 switch (cond_func->functype()) {
2581 case Item_func::BETWEEN:
2582 if (cond_func->arguments()[0]->real_item()->type() == Item::FIELD_ITEM)
2584 field_item= (Item_field*) (cond_func->arguments()[0]->real_item());
2585 ftree= get_full_func_mm_tree(param, cond_func, field_item, NULL, inv);
2592 for (uint32_t i= 1 ; i < cond_func->arg_count ; i++)
2594 if (cond_func->arguments()[i]->real_item()->type() == Item::FIELD_ITEM)
2596 field_item= (Item_field*) (cond_func->arguments()[i]->real_item());
2597 optimizer::SEL_TREE *tmp= get_full_func_mm_tree(param, cond_func,
2598 field_item, (Item*)(intptr_t)i, inv);
2600 tree= !tree ? tmp : tree_or(param, tree, tmp);
2602 tree= tree_and(param, tree, tmp);
2611 ftree = tree_and(param, ftree, tree);
2613 case Item_func::IN_FUNC:
2615 Item_func_in *func=(Item_func_in*) cond_func;
2616 if (func->key_item()->real_item()->type() != Item::FIELD_ITEM)
2618 field_item= (Item_field*) (func->key_item()->real_item());
2619 ftree= get_full_func_mm_tree(param, cond_func, field_item, NULL, inv);
2622 case Item_func::MULT_EQUAL_FUNC:
2624 Item_equal *item_equal= (Item_equal *) cond;
2625 if (!(value= item_equal->get_const()))
2627 Item_equal_iterator it(item_equal->begin());
2628 ref_tables= value->used_tables();
2629 while ((field_item= it++))
2631 Field *field= field_item->field;
2632 field->setWriteSet();
2634 Item_result cmp_type= field->cmp_type();
2635 if (!((ref_tables | field->getTable()->map) & param_comp))
2637 tree= get_mm_parts(param, cond, field, Item_func::EQ_FUNC,
2639 ftree= !ftree ? tree : tree_and(param, ftree, tree);
2646 if (cond_func->arguments()[0]->real_item()->type() == Item::FIELD_ITEM)
2648 field_item= (Item_field*) (cond_func->arguments()[0]->real_item());
2649 value= cond_func->arg_count > 1 ? cond_func->arguments()[1] : 0;
2651 else if (cond_func->have_rev_func() &&
2652 cond_func->arguments()[1]->real_item()->type() ==
2655 field_item= (Item_field*) (cond_func->arguments()[1]->real_item());
2656 value= cond_func->arguments()[0];
2660 ftree= get_full_func_mm_tree(param, cond_func, field_item, value, inv);
2667static optimizer::SEL_TREE *
2668get_mm_parts(optimizer::RangeParameter *param,
2671 Item_func::Functype type,
2672 Item *value, Item_result)
2674 if (field->getTable() != param->table)
2677 KEY_PART *key_part = param->key_parts;
2678 KEY_PART *end = param->key_parts_end;
2679 optimizer::SEL_TREE *tree=0;
2681 value->used_tables() & ~(param->prev_tables | param->read_tables))
2683 for (; key_part != end; key_part++)
2685 if (field->eq(key_part->field))
2687 optimizer::SEL_ARG *sel_arg=0;
2689 tree=
new optimizer::SEL_TREE;
2690 if (!value || !(value->used_tables() & ~param->read_tables))
2692 sel_arg= get_mm_leaf(param,cond_func, key_part->field,key_part,type,value);
2695 if (sel_arg->type == optimizer::SEL_ARG::IMPOSSIBLE)
2697 tree->type=optimizer::SEL_TREE::IMPOSSIBLE;
2704 sel_arg=
new optimizer::SEL_ARG(optimizer::SEL_ARG::MAYBE_KEY);
2706 sel_arg->part=(
unsigned char) key_part->part;
2707 tree->keys[key_part->key]=sel_add(tree->keys[key_part->key],sel_arg);
2708 tree->keys_map.set(key_part->key);
2716static optimizer::SEL_ARG *
2717get_mm_leaf(optimizer::RangeParameter *param,
2721 Item_func::Functype type,
2724 uint32_t maybe_null=(uint32_t) field->real_maybe_null();
2725 bool optimize_range;
2726 optimizer::SEL_ARG *tree= NULL;
2727 memory::Root *alloc= param->mem_root;
2739 param->session->mem_root= param->old_root;
2742 if (field->getTable()->maybe_null)
2746 if (type == Item_func::ISNULL_FUNC)
2747 tree= &optimizer::null_element;
2750 tree=
new (*alloc) optimizer::SEL_ARG(field,is_null_string,is_null_string);
2751 if (type == Item_func::ISNOTNULL_FUNC)
2753 tree->min_flag=NEAR_MIN;
2754 tree->max_flag=NO_MAX_RANGE;
2771 if (field->result_type() == STRING_RESULT &&
2772 value->result_type() == STRING_RESULT &&
2773 ((Field_str*)field)->charset() != conf_func->compare_collation() &&
2774 !(conf_func->compare_collation()->state & MY_CS_BINSORT))
2777 if (param->using_real_indexes)
2778 optimize_range= field->optimize_range(param->real_keynr[key_part->key], key_part->part);
2780 optimize_range=
true;
2782 if (type == Item_func::LIKE_FUNC)
2785 char buff1[MAX_FIELD_WIDTH];
2786 unsigned char *min_str,*max_str;
2787 String tmp(buff1,
sizeof(buff1),value->collation.collation),*res;
2788 size_t length, offset, min_length, max_length;
2789 uint32_t field_length= field->pack_length()+maybe_null;
2791 if (!optimize_range)
2793 if (!(res= value->val_str(&tmp)))
2795 tree= &optimizer::null_element;
2809 if (field->cmp_type() != STRING_RESULT)
2813 length=key_part->store_length;
2815 if (length != key_part->length + maybe_null)
2818 offset+= HA_KEY_BLOB_LENGTH;
2819 field_length= length - HA_KEY_BLOB_LENGTH;
2823 if (DRIZZLE_UNLIKELY(length < field_length))
2829 length= field_length;
2832 field_length= length;
2835 min_str= alloc->alloc(length*2);
2836 max_str=min_str+length;
2838 max_str[0]= min_str[0]=0;
2840 field_length-= maybe_null;
2841 int escape_code= make_escape_code(field->charset(), ((Item_func_like*)(param->cond))->escape);
2842 like_error= my_like_range(field->charset(),
2843 res->ptr(), res->length(),
2845 internal::wild_one, internal::wild_many,
2847 (
char*) min_str+offset, (
char*) max_str+offset,
2848 &min_length, &max_length);
2852 if (offset != maybe_null)
2854 int2store(min_str+maybe_null,min_length);
2855 int2store(max_str+maybe_null,max_length);
2857 tree=
new (alloc) optimizer::SEL_ARG(field, min_str, max_str);
2861 if (! optimize_range &&
2862 type != Item_func::EQ_FUNC &&
2863 type != Item_func::EQUAL_FUNC)
2870 if (field->result_type() == STRING_RESULT &&
2871 value->result_type() != STRING_RESULT &&
2872 field->cmp_type() != value->result_type())
2906 if (field->is_timestamp())
2914 if (value->real_item()->type() == Item::FIELD_ITEM
2915 && value->result_type() == STRING_RESULT)
2917 char buff[DateTime::MAX_STRING_LENGTH];
2918 String tmp(buff,
sizeof(buff), &my_charset_bin);
2919 String *res= value->val_str(&tmp);
2929 DateTime value_datetime;
2931 if (! value_datetime.from_string(res->c_ptr(), (
size_t) res->length()))
2934 Timestamp max_timestamp;
2935 Timestamp min_timestamp;
2937 (void) max_timestamp.from_time_t((time_t) INT32_MAX);
2938 (void) min_timestamp.from_time_t((time_t) 0);
2941 if (value_datetime < min_timestamp)
2947 char new_value_buff[DateTime::MAX_STRING_LENGTH];
2948 int new_value_length;
2949 String new_value_string(new_value_buff,
sizeof(new_value_buff), &my_charset_bin);
2951 new_value_length= min_timestamp.to_string(new_value_string.c_ptr(),
2952 DateTime::MAX_STRING_LENGTH);
2953 assert((new_value_length+1) < DateTime::MAX_STRING_LENGTH);
2954 new_value_string.length(new_value_length);
2955 err= value->save_str_value_in_field(field, &new_value_string);
2957 else if (value_datetime > max_timestamp)
2963 char new_value_buff[DateTime::MAX_STRING_LENGTH];
2964 int new_value_length;
2965 String new_value_string(new_value_buff,
sizeof(new_value_buff), &my_charset_bin);
2967 new_value_length= max_timestamp.to_string(new_value_string.c_ptr(),
2968 DateTime::MAX_STRING_LENGTH);
2969 assert((new_value_length+1) < DateTime::MAX_STRING_LENGTH);
2970 new_value_string.length(new_value_length);
2971 err= value->save_str_value_in_field(field, &new_value_string);
2974 err= value->save_in_field(field, 1);
2978 err= value->save_in_field(field, 1);
2981 err= value->save_in_field(field, 1);
2985 if (field->cmp_type() != value->result_type())
2987 if ((type == Item_func::EQ_FUNC || type == Item_func::EQUAL_FUNC) &&
2988 value->result_type() == item_cmp_type(field->result_type(),
2989 value->result_type()))
2991 tree=
new (alloc) optimizer::SEL_ARG(field, 0, 0);
2992 tree->type= optimizer::SEL_ARG::IMPOSSIBLE;
3002 if (err == 3 && field->type() == DRIZZLE_TYPE_DATE &&
3003 (type == Item_func::GT_FUNC || type == Item_func::GE_FUNC ||
3004 type == Item_func::LT_FUNC || type == Item_func::LE_FUNC) )
3035 else if (err == 1 && field->result_type() == INT_RESULT)
3037 if (type == Item_func::LT_FUNC && (value->val_int() > 0))
3038 type = Item_func::LE_FUNC;
3039 else if (type == Item_func::GT_FUNC &&
3040 !((Field_num*)field)->unsigned_flag &&
3041 !((Item_int*)value)->unsigned_flag &&
3042 (value->val_int() < 0))
3043 type = Item_func::GE_FUNC;
3047 tree=
new (alloc) optimizer::SEL_ARG(field, 0, 0);
3048 tree->type= optimizer::SEL_ARG::IMPOSSIBLE;
3055 tree= &optimizer::null_element;
3064 if (type != Item_func::EQUAL_FUNC && field->is_real_null())
3066 tree= &optimizer::null_element;
3070 str= alloc->alloc(key_part->store_length+1);
3072 *str= field->is_real_null();
3073 field->get_key_image(str+maybe_null, key_part->length);
3074 tree=
new (alloc) optimizer::SEL_ARG(field, str, str);
3087 if (field->result_type() == INT_RESULT &&
3088 value->result_type() == INT_RESULT &&
3089 ((Field_num*)field)->unsigned_flag && !((Item_int*)value)->unsigned_flag)
3091 int64_t item_val= value->val_int();
3094 if (type == Item_func::LT_FUNC || type == Item_func::LE_FUNC)
3096 tree->type= optimizer::SEL_ARG::IMPOSSIBLE;
3099 if (type == Item_func::GT_FUNC || type == Item_func::GE_FUNC)
3108 case Item_func::LT_FUNC:
3110 tree->max_flag=NEAR_MAX;
3112 case Item_func::LE_FUNC:
3114 tree->min_flag=NO_MIN_RANGE;
3117 tree->min_value=is_null_string;
3118 tree->min_flag=NEAR_MIN;
3121 case Item_func::GT_FUNC:
3124 !(key_part->flag & HA_PART_KEY_SEG))
3125 tree->min_flag=NEAR_MIN;
3127 case Item_func::GE_FUNC:
3128 tree->max_flag=NO_MAX_RANGE;
3135 param->session->mem_root= alloc;
3157static optimizer::SEL_ARG *
3158sel_add(optimizer::SEL_ARG *key1, optimizer::SEL_ARG *key2)
3160 optimizer::SEL_ARG *root= NULL;
3161 optimizer::SEL_ARG **key_link= NULL;
3169 while (key1 && key2)
3171 if (key1->part < key2->part)
3174 key_link= &key1->next_key_part;
3175 key1=key1->next_key_part;
3180 key_link= &key2->next_key_part;
3181 key2=key2->next_key_part;
3184 *key_link=key1 ? key1 : key2;
3188static const int CLONE_KEY1_MAYBE= 1;
3189static const int CLONE_KEY2_MAYBE= 2;
3191static uint32_t swap_clone_flag(uint32_t a)
3193 return ((a & 1) << 1) | ((a & 2) >> 1);
3196static optimizer::SEL_TREE *
3197tree_and(optimizer::RangeParameter *param, optimizer::SEL_TREE *tree1, optimizer::SEL_TREE *tree2)
3203 if (tree1->type == optimizer::SEL_TREE::IMPOSSIBLE || tree2->type == optimizer::SEL_TREE::ALWAYS)
3205 if (tree2->type == optimizer::SEL_TREE::IMPOSSIBLE || tree1->type == optimizer::SEL_TREE::ALWAYS)
3207 if (tree1->type == optimizer::SEL_TREE::MAYBE)
3209 if (tree2->type == optimizer::SEL_TREE::KEY)
3210 tree2->type=optimizer::SEL_TREE::KEY_SMALLER;
3213 if (tree2->type == optimizer::SEL_TREE::MAYBE)
3215 tree1->type=optimizer::SEL_TREE::KEY_SMALLER;
3218 key_map result_keys;
3219 result_keys.reset();
3222 optimizer::SEL_ARG **key1,**key2,**end;
3223 for (key1= tree1->keys,key2= tree2->keys,end=key1+param->keys ;
3224 key1 != end ; key1++,key2++)
3229 if (*key1 && !(*key1)->simple_key())
3230 flag|=CLONE_KEY1_MAYBE;
3231 if (*key2 && !(*key2)->simple_key())
3232 flag|=CLONE_KEY2_MAYBE;
3233 *key1=key_and(param, *key1, *key2, flag);
3234 if (*key1 && (*key1)->type == optimizer::SEL_ARG::IMPOSSIBLE)
3236 tree1->type= optimizer::SEL_TREE::IMPOSSIBLE;
3239 result_keys.set(key1 - tree1->keys);
3242 tree1->keys_map= result_keys;
3244 if (result_keys.any())
3246 tree1->merges.clear();
3251 imerge_list_and_list(&tree1->merges, &tree2->merges);
3259static optimizer::SEL_ARG *
3260and_all_keys(optimizer::RangeParameter *param,
3261 optimizer::SEL_ARG *key1,
3262 optimizer::SEL_ARG *key2,
3263 uint32_t clone_flag)
3265 optimizer::SEL_ARG *next= NULL;
3266 ulong use_count=key1->use_count;
3268 if (key1->size() != 1)
3270 key2->use_count+=key1->size()-1;
3271 key2->increment_use_count((
int) key1->size()-1);
3273 if (key1->type == optimizer::SEL_ARG::MAYBE_KEY)
3275 key1->right= key1->left= &optimizer::null_element;
3276 key1->next= key1->prev= 0;
3278 for (next= key1->first(); next ; next=next->next)
3280 if (next->next_key_part)
3282 optimizer::SEL_ARG *tmp= key_and(param, next->next_key_part, key2, clone_flag);
3283 if (tmp && tmp->type == optimizer::SEL_ARG::IMPOSSIBLE)
3285 key1=key1->tree_delete(next);
3288 next->next_key_part=tmp;
3290 next->increment_use_count(use_count);
3291 if (param->alloced_sel_args > optimizer::SEL_ARG::MAX_SEL_ARGS)
3295 next->next_key_part=key2;
3298 return &optimizer::null_element;
3319static optimizer::SEL_ARG *
3320key_and(optimizer::RangeParameter *param,
3321 optimizer::SEL_ARG *key1,
3322 optimizer::SEL_ARG *key2,
3323 uint32_t clone_flag)
3329 if (key1->part != key2->part)
3331 if (key1->part > key2->part)
3333 std::swap(key1, key2);
3334 clone_flag=swap_clone_flag(clone_flag);
3338 if (key1->use_count > 0)
3339 if (! (key1= key1->clone_tree(param)))
3341 return and_all_keys(param, key1, key2, clone_flag);
3344 if (((clone_flag & CLONE_KEY2_MAYBE) &&
3345 ! (clone_flag & CLONE_KEY1_MAYBE) &&
3346 key2->type != optimizer::SEL_ARG::MAYBE_KEY) ||
3347 key1->type == optimizer::SEL_ARG::MAYBE_KEY)
3349 std::swap(key1, key2);
3350 clone_flag= swap_clone_flag(clone_flag);
3354 if (key2->type == optimizer::SEL_ARG::MAYBE_KEY)
3356 if (key1->use_count > 1)
3359 if (! (key1=key1->clone_tree(param)))
3363 if (key1->type == optimizer::SEL_ARG::MAYBE_KEY)
3365 key1->next_key_part= key_and(param,
3366 key1->next_key_part,
3367 key2->next_key_part,
3369 if (key1->next_key_part &&
3370 key1->next_key_part->type == optimizer::SEL_ARG::IMPOSSIBLE)
3375 key1->maybe_smaller();
3376 if (key2->next_key_part)
3379 return and_all_keys(param, key1, key2, clone_flag);
3388 optimizer::SEL_ARG *e1= key1->first();
3389 optimizer::SEL_ARG *e2= key2->first();
3390 optimizer::SEL_ARG *new_tree= NULL;
3394 int cmp= e1->cmp_min_to_min(e2);
3397 if (get_range(&e1, &e2, key1))
3400 else if (get_range(&e2, &e1, key2))
3402 optimizer::SEL_ARG *next= key_and(param,
3406 e1->increment_use_count(1);
3407 e2->increment_use_count(1);
3408 if (! next || next->type != optimizer::SEL_ARG::IMPOSSIBLE)
3410 optimizer::SEL_ARG *new_arg= e1->clone_and(e2);
3411 new_arg->next_key_part=next;
3417 new_tree=new_tree->insert(new_arg);
3419 if (e1->cmp_max_to_max(e2) < 0)
3427 return &optimizer::null_element;
3433get_range(optimizer::SEL_ARG **e1, optimizer::SEL_ARG **e2, optimizer::SEL_ARG *root1)
3435 (*e1)= root1->find_range(*e2);
3436 if ((*e1)->cmp_max_to_min(*e2) < 0)
3438 if (! ((*e1)=(*e1)->next))
3440 if ((*e1)->cmp_min_to_max(*e2) > 0)
3461 unsigned char *min_key, *max_key;
3467 uint32_t min_key_flag, max_key_flag;
3470 uint32_t min_key_parts, max_key_parts;
3481 uint32_t real_keyno;
3485 RANGE_SEQ_ENTRY stack[MAX_REF_PARTS];
3505static range_seq_t sel_arg_range_seq_init(
void *init_param, uint32_t, uint32_t)
3507 SEL_ARG_RANGE_SEQ *seq= (SEL_ARG_RANGE_SEQ*)init_param;
3508 seq->at_start=
true;
3509 seq->stack[0].key_tree= NULL;
3510 seq->stack[0].min_key= seq->param->min_key;
3511 seq->stack[0].min_key_flag= 0;
3512 seq->stack[0].min_key_parts= 0;
3514 seq->stack[0].max_key= seq->param->max_key;
3515 seq->stack[0].max_key_flag= 0;
3516 seq->stack[0].max_key_parts= 0;
3522static void step_down_to(SEL_ARG_RANGE_SEQ *arg, optimizer::SEL_ARG *key_tree)
3524 RANGE_SEQ_ENTRY *cur= &arg->stack[arg->i+1];
3525 RANGE_SEQ_ENTRY *prev= &arg->stack[arg->i];
3527 cur->key_tree= key_tree;
3528 cur->min_key= prev->min_key;
3529 cur->max_key= prev->max_key;
3530 cur->min_key_parts= prev->min_key_parts;
3531 cur->max_key_parts= prev->max_key_parts;
3533 uint16_t stor_length= arg->param->key[arg->keyno][key_tree->part].store_length;
3534 cur->min_key_parts += key_tree->store_min(stor_length, &cur->min_key,
3535 prev->min_key_flag);
3536 cur->max_key_parts += key_tree->store_max(stor_length, &cur->max_key,
3537 prev->max_key_flag);
3539 cur->min_key_flag= prev->min_key_flag | key_tree->min_flag;
3540 cur->max_key_flag= prev->max_key_flag | key_tree->max_flag;
3542 if (key_tree->is_null_interval())
3543 cur->min_key_flag |= NULL_RANGE;
3572static uint32_t sel_arg_range_seq_next(range_seq_t rseq, KEY_MULTI_RANGE *range)
3574 optimizer::SEL_ARG *key_tree;
3575 SEL_ARG_RANGE_SEQ *seq= (SEL_ARG_RANGE_SEQ*)rseq;
3578 key_tree= seq->start;
3579 seq->at_start=
false;
3580 goto walk_up_n_right;
3583 key_tree= seq->stack[seq->i].key_tree;
3587 if (key_tree->next && key_tree->next != &optimizer::null_element)
3591 step_down_to(seq, key_tree->next);
3592 key_tree= key_tree->next;
3593 seq->param->is_ror_scan=
false;
3594 goto walk_right_n_up;
3604 key_tree= seq->stack[seq->i].key_tree;
3607 if (key_tree->next && key_tree->next != &optimizer::null_element)
3611 step_down_to(seq, key_tree->next);
3612 key_tree= key_tree->next;
3622 while (key_tree->next_key_part && key_tree->next_key_part != &optimizer::null_element &&
3623 key_tree->next_key_part->part == key_tree->part + 1 &&
3624 key_tree->next_key_part->type == optimizer::SEL_ARG::KEY_RANGE)
3627 RANGE_SEQ_ENTRY *cur= &seq->stack[seq->i];
3628 uint32_t min_key_length= cur->min_key - seq->param->min_key;
3629 uint32_t max_key_length= cur->max_key - seq->param->max_key;
3630 uint32_t len= cur->min_key - cur[-1].min_key;
3631 if (! (min_key_length == max_key_length &&
3632 ! memcmp(cur[-1].min_key, cur[-1].max_key, len) &&
3633 ! key_tree->min_flag && !key_tree->max_flag))
3635 seq->param->is_ror_scan=
false;
3636 if (! key_tree->min_flag)
3637 cur->min_key_parts +=
3638 key_tree->next_key_part->store_min_key(seq->param->key[seq->keyno],
3640 &cur->min_key_flag);
3641 if (! key_tree->max_flag)
3642 cur->max_key_parts +=
3643 key_tree->next_key_part->store_max_key(seq->param->key[seq->keyno],
3645 &cur->max_key_flag);
3654 key_tree= key_tree->next_key_part;
3657 while (key_tree->prev && key_tree->prev != &optimizer::null_element)
3660 key_tree= key_tree->prev;
3662 step_down_to(seq, key_tree);
3666 RANGE_SEQ_ENTRY *cur= &seq->stack[seq->i];
3668 range->ptr= (
char*)(
size_t)(key_tree->part);
3670 range->range_flag= cur->min_key_flag | cur->max_key_flag;
3672 range->start_key.key= seq->param->min_key;
3673 range->start_key.length= cur->min_key - seq->param->min_key;
3674 range->start_key.keypart_map= make_prev_keypart_map(cur->min_key_parts);
3675 range->start_key.flag= (cur->min_key_flag & NEAR_MIN ? HA_READ_AFTER_KEY :
3678 range->end_key.key= seq->param->max_key;
3679 range->end_key.length= cur->max_key - seq->param->max_key;
3680 range->end_key.flag= (cur->max_key_flag & NEAR_MAX ? HA_READ_BEFORE_KEY :
3682 range->end_key.keypart_map= make_prev_keypart_map(cur->max_key_parts);
3684 if (!(cur->min_key_flag & ~NULL_RANGE) && !cur->max_key_flag &&
3685 (uint32_t)key_tree->part+1 == seq->param->table->key_info[seq->real_keyno].key_parts &&
3686 (seq->param->table->key_info[seq->real_keyno].flags & (HA_NOSAME)) ==
3688 range->start_key.length == range->end_key.length &&
3689 !memcmp(seq->param->min_key,seq->param->max_key,range->start_key.length))
3690 range->range_flag= UNIQUE_RANGE | (cur->min_key_flag & NULL_RANGE);
3692 if (seq->param->is_ror_scan)
3703 if (!(!(cur->min_key_flag & ~NULL_RANGE) && !cur->max_key_flag &&
3704 (range->start_key.length == range->end_key.length) &&
3705 !memcmp(range->start_key.key, range->end_key.key, range->start_key.length) &&
3706 is_key_scan_ror(seq->param, seq->real_keyno, key_tree->part + 1)))
3707 seq->param->is_ror_scan=
false;
3710 seq->param->range_count++;
3711 seq->param->max_key_part= max(seq->param->max_key_part,(uint32_t)key_tree->part);
3744ha_rows check_quick_select(Session *session,
3745 optimizer::Parameter *param,
3748 optimizer::SEL_ARG *tree,
3749 bool update_tbl_stats,
3750 uint32_t *mrr_flags,
3752 optimizer::CostVector *cost)
3754 SEL_ARG_RANGE_SEQ seq;
3755 RANGE_SEQ_IF seq_if = {sel_arg_range_seq_init, sel_arg_range_seq_next};
3756 Cursor *cursor= param->table->cursor;
3758 uint32_t keynr= param->real_keynr[idx];
3762 return(HA_POS_ERROR);
3763 if (tree->type == optimizer::SEL_ARG::IMPOSSIBLE)
3765 if (tree->type != optimizer::SEL_ARG::KEY_RANGE || tree->part != 0)
3766 return(HA_POS_ERROR);
3769 seq.real_keyno= keynr;
3773 param->range_count=0;
3774 param->max_key_part=0;
3776 param->is_ror_scan=
true;
3777 if (param->table->index_flags(keynr) & HA_KEY_SCAN_NOT_ROR)
3778 param->is_ror_scan=
false;
3780 *mrr_flags= param->force_default_mrr? HA_MRR_USE_DEFAULT_IMPL: 0;
3781 *mrr_flags|= HA_MRR_NO_ASSOCIATION;
3783 bool pk_is_clustered= cursor->primary_key_is_clustered();
3785 (param->table->index_flags(keynr) & HA_KEYREAD_ONLY) &&
3786 !(pk_is_clustered && keynr == param->table->getShare()->getPrimaryKey()))
3787 *mrr_flags |= HA_MRR_INDEX_ONLY;
3789 if (session->lex().sql_command != SQLCOM_SELECT)
3790 *mrr_flags |= HA_MRR_USE_DEFAULT_IMPL;
3792 *bufsize= param->session->variables.read_rnd_buff_size;
3793 rows= cursor->multi_range_read_info_const(keynr, &seq_if, (
void*)&seq, 0,
3794 bufsize, mrr_flags, cost);
3795 if (rows != HA_POS_ERROR)
3797 param->table->quick_rows[keynr]=rows;
3798 if (update_tbl_stats)
3800 param->table->quick_keys.set(keynr);
3801 param->table->quick_key_parts[keynr]=param->max_key_part+1;
3802 param->table->quick_n_ranges[keynr]= param->range_count;
3803 param->table->quick_condition_rows=
3804 min(param->table->quick_condition_rows, rows);
3808 message::Table::Index::IndexType key_alg= param->table->key_info[seq.real_keyno].algorithm;
3809 if ((key_alg != message::Table::Index::BTREE)
3810 && (key_alg!= message::Table::Index::UNKNOWN_INDEX))
3817 param->is_ror_scan=
false;
3822 if (param->table->getShare()->getPrimaryKey() == keynr && pk_is_clustered)
3823 param->is_ror_scan=
true;
3867static bool is_key_scan_ror(optimizer::Parameter *param, uint32_t keynr, uint8_t nparts)
3869 KeyInfo *table_key= param->table->key_info + keynr;
3870 KeyPartInfo *key_part= table_key->key_part + nparts;
3871 KeyPartInfo *key_part_end= (table_key->key_part +
3872 table_key->key_parts);
3875 for (KeyPartInfo *kp= table_key->key_part; kp < key_part; kp++)
3877 uint16_t fieldnr= param->table->key_info[keynr].
3878 key_part[kp - table_key->key_part].fieldnr - 1;
3879 if (param->table->getField(fieldnr)->key_length() != kp->length)
3883 if (key_part == key_part_end)
3886 key_part= table_key->key_part + nparts;
3887 pk_number= param->table->getShare()->getPrimaryKey();
3888 if (!param->table->cursor->primary_key_is_clustered() || pk_number == MAX_KEY)
3891 KeyPartInfo *pk_part= param->table->key_info[pk_number].key_part;
3892 KeyPartInfo *pk_part_end= pk_part +
3893 param->table->key_info[pk_number].key_parts;
3894 for (;(key_part!=key_part_end) && (pk_part != pk_part_end);
3895 ++key_part, ++pk_part)
3897 if ((key_part->field != pk_part->field) ||
3898 (key_part->length != pk_part->length))
3901 return (key_part == key_part_end);
3905optimizer::QuickRangeSelect *
3906optimizer::get_quick_select(Parameter *param,
3908 optimizer::SEL_ARG *key_tree,
3910 uint32_t mrr_buf_size,
3911 memory::Root *parent_alloc)
3913 optimizer::QuickRangeSelect *quick=
new optimizer::QuickRangeSelect(param->session,
3915 param->real_keynr[idx],
3921 if (get_quick_keys(param,
3935 quick->mrr_flags= mrr_flags;
3936 quick->mrr_buf_size= mrr_buf_size;
3937 quick->key_parts= parent_alloc
3938 ? (KEY_PART*)parent_alloc->memdup(param->key[idx],
sizeof(KEY_PART)* param->table->key_info[param->real_keynr[idx]].key_parts)
3939 : (KEY_PART*)quick->alloc.memdup(param->key[idx],
sizeof(KEY_PART)* param->table->key_info[param->real_keynr[idx]].key_parts);
3950optimizer::get_quick_keys(optimizer::Parameter *param,
3951 optimizer::QuickRangeSelect *quick,
3953 optimizer::SEL_ARG *key_tree,
3954 unsigned char *min_key,
3955 uint32_t min_key_flag,
3956 unsigned char *max_key,
3957 uint32_t max_key_flag)
3959 optimizer::QuickRange *range= NULL;
3961 int min_part= key_tree->part - 1;
3962 int max_part= key_tree->part - 1;
3964 if (key_tree->left != &optimizer::null_element)
3966 if (get_quick_keys(param,
3978 unsigned char *tmp_min_key= min_key,*tmp_max_key= max_key;
3979 min_part+= key_tree->store_min(key[key_tree->part].store_length,
3980 &tmp_min_key,min_key_flag);
3981 max_part+= key_tree->store_max(key[key_tree->part].store_length,
3982 &tmp_max_key,max_key_flag);
3984 if (key_tree->next_key_part &&
3985 key_tree->next_key_part->part == key_tree->part+1 &&
3986 key_tree->next_key_part->type == optimizer::SEL_ARG::KEY_RANGE)
3988 if ((tmp_min_key - min_key) == (tmp_max_key - max_key) &&
3989 memcmp(min_key, max_key, (uint32_t)(tmp_max_key - max_key))==0 &&
3990 key_tree->min_flag==0 && key_tree->max_flag==0)
3992 if (get_quick_keys(param,
3995 key_tree->next_key_part,
3997 min_key_flag | key_tree->min_flag,
3999 max_key_flag | key_tree->max_flag))
4006 uint32_t tmp_min_flag=key_tree->min_flag,tmp_max_flag=key_tree->max_flag;
4009 min_part+= key_tree->next_key_part->store_min_key(key,
4015 max_part+= key_tree->next_key_part->store_max_key(key,
4019 flag=tmp_min_flag | tmp_max_flag;
4024 flag= key_tree->min_flag | key_tree->max_flag;
4031 if (tmp_min_key != param->min_key)
4033 flag&= ~NO_MIN_RANGE;
4037 flag|= NO_MIN_RANGE;
4039 if (tmp_max_key != param->max_key)
4041 flag&= ~NO_MAX_RANGE;
4045 flag|= NO_MAX_RANGE;
4049 uint32_t length= (uint32_t) (tmp_min_key - param->min_key);
4050 if (length == (uint32_t) (tmp_max_key - param->max_key) &&
4051 ! memcmp(param->min_key,param->max_key,length))
4053 KeyInfo *table_key= quick->head->key_info+quick->index;
4055 if ((table_key->flags & (HA_NOSAME)) == HA_NOSAME &&
4056 key->part == table_key->key_parts-1)
4058 if (! (table_key->flags & HA_NULL_PART_KEY) ||
4059 ! null_part_in_key(key,
4061 (uint32_t) (tmp_min_key - param->min_key)))
4063 flag|= UNIQUE_RANGE;
4074 range=
new optimizer::QuickRange(param->min_key,
4075 (uint32_t) (tmp_min_key - param->min_key),
4076 min_part >=0 ? make_keypart_map(min_part) : 0,
4078 (uint32_t) (tmp_max_key - param->max_key),
4079 max_part >=0 ? make_keypart_map(max_part) : 0,
4082 set_if_bigger(quick->max_used_key_length, (uint32_t)range->min_length);
4083 set_if_bigger(quick->max_used_key_length, (uint32_t)range->max_length);
4084 set_if_bigger(quick->used_key_parts, (uint32_t) key_tree->part+1);
4085 quick->ranges.push_back(&range);
4088 if (key_tree->right != &optimizer::null_element)
4090 return get_quick_keys(param,
4116static bool null_part_in_key(KEY_PART *key_part,
const unsigned char *key, uint32_t length)
4118 for (
const unsigned char *end=key+length ;
4120 key+= key_part++->store_length)
4122 if (key_part->null_bit && *key)
4131 return is_key_used(head,
index, fields);
4161 KeyInfo *key_info = &table->key_info[ref->
key];
4167 old_root= session->mem_root;
4171 alloc= session->mem_root;
4176 session->mem_root= old_root;
4184 if (cp_buffer_from_ref(session, ref) && session->is_fatal_error)
4188 range->min_key= range->max_key= ref->
key_buff;
4189 range->min_length= range->max_length= ref->
key_length;
4192 range->flag= (ref->
key_length == key_info->key_length && (key_info->flags & HA_END_SPACE_KEY) == 0) ? EQ_RANGE : 0;
4196 for (part=0 ; part < ref->
key_parts ;part++,key_part++)
4198 key_part->part=part;
4199 key_part->field= key_info->key_part[part].field;
4200 key_part->length= key_info->key_part[part].length;
4201 key_part->store_length= key_info->key_part[part].store_length;
4202 key_part->null_bit= key_info->key_part[part].null_bit;
4203 key_part->
flag= (uint8_t) key_info->key_part[part].key_part_flag;
4205 quick->
ranges.push_back(&range);
4218 null_range=
new (alloc)
4222 make_prev_keypart_map(ref->
key_parts), EQ_RANGE);
4224 quick->
ranges.push_back(&null_range);
4228 quick->
mrr_flags= HA_MRR_NO_ASSOCIATION |
4229 (table->key_read ? HA_MRR_INDEX_ONLY : 0);
4230 if (session->lex().sql_command != SQLCOM_SELECT)
4231 quick->
mrr_flags |= HA_MRR_USE_DEFAULT_IMPL;
4234 if (table->cursor->multi_range_read_info(quick->
index, 1, (uint32_t)records, &quick->
mrr_buf_size, &quick->
mrr_flags, &cost))
4257range_seq_t optimizer::quick_range_seq_init(
void *init_param, uint32_t, uint32_t)
4259 optimizer::QuickRangeSelect *quick= (optimizer::QuickRangeSelect*)init_param;
4260 quick->
qr_traversal_ctx.first= (optimizer::QuickRange**)quick->ranges.buffer;
4280uint32_t optimizer::quick_range_seq_next(range_seq_t rseq, KEY_MULTI_RANGE *range)
4282 QuickRangeSequenceContext *ctx= (QuickRangeSequenceContext*) rseq;
4284 if (ctx->cur == ctx->last)
4287 optimizer::QuickRange *cur= *(ctx->cur);
4288 key_range *start_key= &range->start_key;
4289 key_range *end_key= &range->end_key;
4291 start_key->key= cur->min_key;
4292 start_key->length= cur->min_length;
4293 start_key->keypart_map= cur->min_keypart_map;
4294 start_key->flag= ((cur->flag & NEAR_MIN) ? HA_READ_AFTER_KEY :
4295 (cur->flag & EQ_RANGE) ?
4296 HA_READ_KEY_EXACT : HA_READ_KEY_OR_NEXT);
4297 end_key->key= cur->max_key;
4298 end_key->length= cur->max_length;
4299 end_key->keypart_map= cur->max_keypart_map;
4304 end_key->flag= (cur->flag & NEAR_MAX ? HA_READ_BEFORE_KEY :
4306 range->range_flag= cur->flag;
4312static inline uint32_t get_field_keypart(KeyInfo *index, Field *field);
4314static inline optimizer::SEL_ARG * get_index_range_tree(uint32_t index,
4315 optimizer::SEL_TREE *range_tree,
4316 optimizer::Parameter *param,
4317 uint32_t *param_idx);
4319static bool get_constant_key_infix(KeyInfo *index_info,
4320 optimizer::SEL_ARG *index_range_tree,
4321 KeyPartInfo *first_non_group_part,
4322 KeyPartInfo *min_max_arg_part,
4323 KeyPartInfo *last_part,
4325 unsigned char *key_infix,
4326 uint32_t *key_infix_len,
4327 KeyPartInfo **first_non_infix_part);
4329static bool check_group_min_max_predicates(COND *cond, Item_field *min_max_arg_item);
4332cost_group_min_max(Table* table,
4333 KeyInfo *index_info,
4334 uint32_t used_key_parts,
4335 uint32_t group_key_parts,
4336 optimizer::SEL_TREE *range_tree,
4337 optimizer::SEL_ARG *index_tree,
4338 ha_rows quick_prefix_records,
4472static optimizer::GroupMinMaxReadPlan *
4473get_best_group_min_max(optimizer::Parameter *param, optimizer::SEL_TREE *tree)
4475 Session *session= param->session;
4476 Join *join= session->lex().current_select->join;
4477 Table *table= param->table;
4478 bool have_min=
false;
4479 bool have_max=
false;
4480 Item_field *min_max_arg_item= NULL;
4481 KeyPartInfo *min_max_arg_part= NULL;
4482 uint32_t group_prefix_len= 0;
4483 KeyInfo *index_info= NULL;
4485 uint32_t group_key_parts= 0;
4486 uint32_t used_key_parts= 0;
4487 unsigned char key_infix[MAX_KEY_LENGTH];
4488 uint32_t key_infix_len= 0;
4489 optimizer::GroupMinMaxReadPlan *read_plan= NULL;
4490 uint32_t key_part_nr;
4491 Order *tmp_group= NULL;
4493 Item_field *item_field= NULL;
4499 if ((join->tables != 1) ||
4500 ((! join->group_list) &&
4501 (! join->select_distinct)) ||
4502 (join->select_lex->olap == ROLLUP_TYPE))
4504 if (table->getShare()->sizeKeys() == 0)
4508 List<Item>::iterator select_items_it(join->fields_list.begin());
4511 if (join->make_sum_func_list(join->all_fields, join->fields_list, 1))
4514 if (join->sum_funcs[0])
4516 Item_sum *min_max_item= NULL;
4517 Item_sum **func_ptr= join->sum_funcs;
4518 while ((min_max_item= *(func_ptr++)))
4520 if (min_max_item->sum_func() == Item_sum::MIN_FUNC)
4522 else if (min_max_item->sum_func() == Item_sum::MAX_FUNC)
4528 Item *expr= min_max_item->args[0]->real_item();
4529 if (expr->type() == Item::FIELD_ITEM)
4531 if (! min_max_arg_item)
4532 min_max_arg_item= (Item_field*) expr;
4533 else if (! min_max_arg_item->eq(expr, 1))
4542 if (join->select_distinct)
4544 while ((item= select_items_it++))
4546 if (item->type() != Item::FIELD_ITEM)
4552 for (tmp_group= join->group_list; tmp_group; tmp_group= tmp_group->next)
4554 if ((*tmp_group->item)->type() != Item::FIELD_ITEM)
4563 KeyInfo *cur_index_info= table->key_info;
4564 KeyInfo *cur_index_info_end= cur_index_info + table->getShare()->sizeKeys();
4565 KeyPartInfo *cur_part= NULL;
4566 KeyPartInfo *end_part= NULL;
4568 KeyPartInfo *last_part= NULL;
4569 KeyPartInfo *first_non_group_part= NULL;
4570 KeyPartInfo *first_non_infix_part= NULL;
4571 uint32_t key_infix_parts= 0;
4572 uint32_t cur_group_key_parts= 0;
4573 uint32_t cur_group_prefix_len= 0;
4575 double best_read_cost= DBL_MAX;
4576 ha_rows best_records= 0;
4577 optimizer::SEL_ARG *best_index_tree= NULL;
4578 ha_rows best_quick_prefix_records= 0;
4579 uint32_t best_param_idx= 0;
4580 double cur_read_cost= DBL_MAX;
4581 ha_rows cur_records;
4582 optimizer::SEL_ARG *cur_index_tree= NULL;
4583 ha_rows cur_quick_prefix_records= 0;
4584 uint32_t cur_param_idx= MAX_KEY;
4585 key_map used_key_parts_map;
4586 uint32_t cur_key_infix_len= 0;
4587 unsigned char cur_key_infix[MAX_KEY_LENGTH];
4588 uint32_t cur_used_key_parts= 0;
4589 uint32_t pk= param->table->getShare()->getPrimaryKey();
4591 for (uint32_t cur_index= 0;
4592 cur_index_info != cur_index_info_end;
4593 cur_index_info++, cur_index++)
4596 if (! table->covering_keys.test(cur_index))
4608 if (pk < MAX_KEY && cur_index != pk &&
4609 (table->cursor->getEngine()->check_flag(HTON_BIT_PRIMARY_KEY_IN_READ_INDEX)))
4612 for (uint32_t i= 0; i < table->getShare()->sizeFields(); i++)
4614 Field *cur_field= table->getField(i);
4619 if ((cur_field->isReadSet()) &&
4620 ! cur_field->part_of_key_not_clustered.test(cur_index))
4628 if (join->group_list)
4630 cur_part= cur_index_info->key_part;
4631 end_part= cur_part + cur_index_info->key_parts;
4633 for (tmp_group= join->group_list;
4634 tmp_group && (cur_part != end_part);
4635 tmp_group= tmp_group->next, cur_part++)
4643 assert((*tmp_group->item)->type() == Item::FIELD_ITEM);
4644 Item_field *group_field= (Item_field *) (*tmp_group->item);
4645 if (group_field->field->eq(cur_part->field))
4647 cur_group_prefix_len+= cur_part->store_length;
4648 ++cur_group_key_parts;
4662 else if (join->select_distinct)
4664 select_items_it= join->fields_list.begin();
4665 used_key_parts_map.reset();
4666 uint32_t max_key_part= 0;
4667 while ((item= select_items_it++))
4669 item_field= (Item_field*) item;
4671 key_part_nr= get_field_keypart(cur_index_info, item_field->field);
4676 if (used_key_parts_map.test(key_part_nr))
4678 if (key_part_nr < 1 || key_part_nr > join->fields_list.size())
4680 cur_part= cur_index_info->key_part + key_part_nr - 1;
4681 cur_group_prefix_len+= cur_part->store_length;
4682 used_key_parts_map.set(key_part_nr);
4683 ++cur_group_key_parts;
4684 max_key_part= max(max_key_part,key_part_nr);
4694 for (uint32_t pos= 0; pos < max_key_part; pos++)
4696 cur_parts= used_key_parts_map >> 1;
4697 if (all_parts != cur_parts)
4704 if (min_max_arg_item)
4706 key_part_nr= get_field_keypart(cur_index_info, min_max_arg_item->field);
4707 if (key_part_nr <= cur_group_key_parts)
4709 min_max_arg_part= cur_index_info->key_part + key_part_nr - 1;
4727 last_part= cur_index_info->key_part + cur_index_info->key_parts;
4728 first_non_group_part= (cur_group_key_parts < cur_index_info->key_parts) ?
4729 cur_index_info->key_part + cur_group_key_parts :
4731 first_non_infix_part= min_max_arg_part ?
4732 (min_max_arg_part < last_part) ?
4736 if (first_non_group_part &&
4737 (! min_max_arg_part || (min_max_arg_part - first_non_group_part > 0)))
4742 optimizer::SEL_ARG *index_range_tree= get_index_range_tree(cur_index,
4746 if (! get_constant_key_infix(cur_index_info,
4748 first_non_group_part,
4754 &first_non_infix_part))
4759 else if (min_max_arg_part &&
4760 (min_max_arg_part - first_non_group_part > 0))
4768 else if (first_non_group_part && join->conds)
4782 KeyPartInfo *key_part_range[2];
4783 key_part_range[0]= first_non_group_part;
4784 key_part_range[1]= last_part;
4787 if (join->conds->walk(&Item::find_item_in_field_list_processor,
4789 (
unsigned char*) key_part_range))
4798 if (first_non_infix_part)
4800 cur_part= first_non_infix_part +
4801 (min_max_arg_part && (min_max_arg_part < last_part));
4802 for (; cur_part != last_part; cur_part++)
4804 if (cur_part->field->isReadSet())
4810 key_infix_parts= cur_key_infix_len ?
4811 (first_non_infix_part - first_non_group_part) : 0;
4812 cur_used_key_parts= cur_group_key_parts + key_infix_parts;
4818 cur_index_tree= get_index_range_tree(cur_index,
4823 optimizer::CostVector dummy_cost;
4824 uint32_t mrr_flags= HA_MRR_USE_DEFAULT_IMPL;
4825 uint32_t mrr_bufsize= 0;
4826 cur_quick_prefix_records= check_quick_select(session,
4836 cost_group_min_max(table,
4839 cur_group_key_parts,
4842 cur_quick_prefix_records,
4852 if (cur_read_cost < best_read_cost - (DBL_EPSILON * cur_read_cost))
4854 assert(tree != 0 || cur_param_idx == MAX_KEY);
4855 index_info= cur_index_info;
4857 best_read_cost= cur_read_cost;
4858 best_records= cur_records;
4859 best_index_tree= cur_index_tree;
4860 best_quick_prefix_records= cur_quick_prefix_records;
4861 best_param_idx= cur_param_idx;
4862 group_key_parts= cur_group_key_parts;
4863 group_prefix_len= cur_group_prefix_len;
4864 key_infix_len= cur_key_infix_len;
4868 memcpy(key_infix, cur_key_infix,
sizeof (key_infix));
4871 used_key_parts= cur_used_key_parts;
4875 cur_group_key_parts= 0;
4876 cur_group_prefix_len= 0;
4877 cur_key_infix_len= 0;
4883 if (join->conds && min_max_arg_item &&
4884 ! check_group_min_max_predicates(join->conds, min_max_arg_item))
4888 read_plan=
new (*param->mem_root) optimizer::GroupMinMaxReadPlan(have_min,
4897 (key_infix_len > 0) ? key_infix : NULL,
4901 best_quick_prefix_records);
4902 if (tree && read_plan->quick_prefix_records == 0)
4904 read_plan->read_cost= best_read_cost;
4905 read_plan->records= best_records;
4931static bool check_group_min_max_predicates(COND *cond, Item_field *min_max_arg_item)
4933 assert(cond && min_max_arg_item);
4935 cond= cond->real_item();
4936 Item::Type cond_type= cond->type();
4937 if (cond_type == Item::COND_ITEM)
4939 List<Item>::iterator li(((Item_cond*) cond)->argument_list()->begin());
4940 Item *and_or_arg= NULL;
4941 while ((and_or_arg= li++))
4943 if (! check_group_min_max_predicates(and_or_arg, min_max_arg_item))
4958 if (cond_type == Item::SUBSELECT_ITEM)
4962 assert(cond_type == Item::FUNC_ITEM);
4965 Item_func *pred= (Item_func*) cond;
4966 Item **arguments= pred->arguments();
4967 Item *cur_arg= NULL;
4968 for (uint32_t arg_idx= 0; arg_idx < pred->argument_count (); arg_idx++)
4970 cur_arg= arguments[arg_idx]->real_item();
4971 if (cur_arg->type() == Item::FIELD_ITEM)
4973 if (min_max_arg_item->eq(cur_arg, 1))
4979 Item_func::Functype pred_type= pred->functype();
4980 if (pred_type != Item_func::EQUAL_FUNC &&
4981 pred_type != Item_func::LT_FUNC &&
4982 pred_type != Item_func::LE_FUNC &&
4983 pred_type != Item_func::GT_FUNC &&
4984 pred_type != Item_func::GE_FUNC &&
4985 pred_type != Item_func::BETWEEN &&
4986 pred_type != Item_func::ISNULL_FUNC &&
4987 pred_type != Item_func::ISNOTNULL_FUNC &&
4988 pred_type != Item_func::EQ_FUNC &&
4989 pred_type != Item_func::NE_FUNC)
4994 memset(args, 0, 3 *
sizeof(Item*));
4997 if (! optimizer::simple_pred(pred, args, inv))
5001 if (args[0] && args[1] && !args[2] &&
5002 min_max_arg_item->result_type() == STRING_RESULT &&
5006 ((args[1]->result_type() == STRING_RESULT &&
5007 ((Field_str*) min_max_arg_item->field)->charset() !=
5008 pred->compare_collation())
5014 (args[1]->result_type() != STRING_RESULT &&
5015 min_max_arg_item->field->cmp_type() != args[1]->result_type())))
5021 else if (cur_arg->type() == Item::FUNC_ITEM)
5023 if (! check_group_min_max_predicates(cur_arg, min_max_arg_item))
5026 else if (cur_arg->const_item())
5069get_constant_key_infix(KeyInfo *,
5070 optimizer::SEL_ARG *index_range_tree,
5071 KeyPartInfo *first_non_group_part,
5072 KeyPartInfo *min_max_arg_part,
5073 KeyPartInfo *last_part,
5075 unsigned char *key_infix,
5076 uint32_t *key_infix_len,
5077 KeyPartInfo **first_non_infix_part)
5079 optimizer::SEL_ARG *cur_range= NULL;
5080 KeyPartInfo *cur_part= NULL;
5082 KeyPartInfo *end_part= min_max_arg_part ? min_max_arg_part : last_part;
5085 unsigned char *key_ptr= key_infix;
5086 for (cur_part= first_non_group_part; cur_part != end_part; cur_part++)
5092 for (cur_range= index_range_tree; cur_range;
5093 cur_range= cur_range->next_key_part)
5095 if (cur_range->field->eq(cur_part->field))
5100 if (min_max_arg_part)
5104 *first_non_infix_part= cur_part;
5110 if (cur_range->prev || cur_range->next)
5112 if ((cur_range->min_flag & NO_MIN_RANGE) ||
5113 (cur_range->max_flag & NO_MAX_RANGE) ||
5114 (cur_range->min_flag & NEAR_MIN) ||
5115 (cur_range->max_flag & NEAR_MAX))
5118 uint32_t field_length= cur_part->store_length;
5119 if ((cur_range->maybe_null &&
5120 cur_range->min_value[0] && cur_range->max_value[0]) ||
5121 !memcmp(cur_range->min_value, cur_range->max_value, field_length))
5124 memcpy(key_ptr, cur_range->min_value, field_length);
5125 key_ptr+= field_length;
5126 *key_infix_len+= field_length;
5132 if (!min_max_arg_part && (cur_part == last_part))
5133 *first_non_infix_part= last_part;
5156get_field_keypart(KeyInfo *index, Field *field)
5158 KeyPartInfo *part= NULL;
5159 KeyPartInfo *end= NULL;
5161 for (part= index->key_part, end= part + index->key_parts; part < end; part++)
5163 if (field->eq(part->field))
5164 return part - index->key_part + 1;
5192optimizer::SEL_ARG *get_index_range_tree(uint32_t index,
5193 optimizer::SEL_TREE* range_tree,
5194 optimizer::Parameter *param,
5195 uint32_t *param_idx)
5198 while (idx < param->keys)
5200 if (index == param->real_keynr[idx])
5205 return range_tree->keys[idx];
5268void cost_group_min_max(Table* table,
5269 KeyInfo *index_info,
5270 uint32_t used_key_parts,
5271 uint32_t group_key_parts,
5272 optimizer::SEL_TREE *range_tree,
5273 optimizer::SEL_ARG *,
5274 ha_rows quick_prefix_records,
5280 ha_rows table_records;
5281 uint32_t num_groups;
5282 uint32_t num_blocks;
5283 uint32_t keys_per_block;
5284 uint32_t keys_per_group;
5285 uint32_t keys_per_subgroup;
5288 double quick_prefix_selectivity;
5292 table_records= table->cursor->stats.records;
5293 keys_per_block= (table->cursor->stats.block_size / 2 /
5294 (index_info->key_length + table->cursor->ref_length)
5296 num_blocks= (uint32_t) (table_records / keys_per_block) + 1;
5299 keys_per_group= index_info->rec_per_key[group_key_parts - 1];
5300 if (keys_per_group == 0)
5302 keys_per_group= (uint32_t)(table_records / 10) + 1;
5303 num_groups= (uint32_t)(table_records / keys_per_group) + 1;
5306 if (range_tree && (quick_prefix_records != HA_POS_ERROR))
5308 quick_prefix_selectivity= (double) quick_prefix_records /
5309 (
double) table_records;
5310 num_groups= (uint32_t) rint(num_groups * quick_prefix_selectivity);
5311 set_if_bigger(num_groups, 1U);
5314 if (used_key_parts > group_key_parts)
5319 keys_per_subgroup= index_info->rec_per_key[used_key_parts - 1];
5320 if (keys_per_subgroup >= keys_per_block)
5324 double blocks_per_group= (double) num_blocks / (
double) num_groups;
5325 p_overlap= (blocks_per_group * (keys_per_subgroup - 1)) / keys_per_group;
5326 p_overlap= min(p_overlap, 1.0);
5328 io_cost= (double) min(num_groups * (1 + p_overlap), (
double)num_blocks);
5331 io_cost= (keys_per_group > keys_per_block) ?
5332 (have_min && have_max) ? (double) (num_groups + 1) :
5333 (double) num_groups :
5334 (double) num_blocks;
5343 *read_cost= io_cost + cpu_cost;
5344 *records= num_groups;
5368optimizer::QuickSelectInterface *
5369optimizer::GroupMinMaxReadPlan::make_quick(optimizer::Parameter *param,
bool, memory::Root *parent_alloc)
5371 optimizer::QuickGroupMinMaxSelect *quick=
new optimizer::QuickGroupMinMaxSelect(param->table,
5372 param->session->lex().current_select->join,
5394 assert(quick_prefix_records > 0);
5395 if (quick_prefix_records == HA_POS_ERROR)
5397 quick->quick_prefix_select= NULL;
5402 quick->quick_prefix_select= optimizer::get_quick_select(param,
5405 HA_MRR_USE_DEFAULT_IMPL,
5415 if (min_max_arg_part)
5417 optimizer::SEL_ARG *min_max_range= index_tree;
5418 while (min_max_range)
5420 if (min_max_range->field->eq(min_max_arg_part->field))
5422 min_max_range= min_max_range->next_key_part;
5425 while (min_max_range && min_max_range->prev)
5426 min_max_range= min_max_range->prev;
5428 while (min_max_range)
5430 if (quick->add_range(min_max_range))
5436 min_max_range= min_max_range->next;
5441 quick->quick_prefix_select= NULL;
5443 quick->update_key_stat();
5444 quick->adjust_prefix_ranges();
5450optimizer::QuickSelectInterface *optimizer::RangeReadPlan::make_quick(optimizer::Parameter *param,
bool, memory::Root *parent_alloc)
5452 optimizer::QuickRangeSelect *quick= optimizer::get_quick_select(param, key_idx, key, mrr_flags, mrr_buf_size, parent_alloc);
5455 quick->records= records;
5456 quick->read_time= read_cost;
5462uint32_t optimizer::RorScanInfo::findFirstNotSet()
const
5464 boost::dynamic_bitset<> map= bitsToBitset();
5465 for (boost::dynamic_bitset<>::size_type i= 0; i < map.size(); i++)
5467 if (not map.test(i))
5474size_t optimizer::RorScanInfo::getBitCount()
const
5476 boost::dynamic_bitset<> tmp_bitset= bitsToBitset();
5477 return tmp_bitset.count();
5481void optimizer::RorScanInfo::subtractBitset(
const boost::dynamic_bitset<>& in_bitset)
5483 boost::dynamic_bitset<> tmp_bitset= bitsToBitset();
5484 tmp_bitset-= in_bitset;
5485 covered_fields= tmp_bitset.to_ulong();
5489boost::dynamic_bitset<> optimizer::RorScanInfo::bitsToBitset()
const
5492 uint64_t conv= covered_fields;
5495 res.push_back((conv & 1) +
'0');
5500 std::reverse(res.begin(), res.end());
5502 string final(covered_fields_size - res.length(),
'0');
5504 return boost::dynamic_bitset<>(
final);
drizzle_system_variables & variables
QuickRangeSequenceContext qr_traversal_ctx
key_part_map min_keypart_map
key_part_map max_keypart_map
virtual bool is_keys_used(const boost::dynamic_bitset<> &fields)
#define TIME_FOR_COMPARE_ROWID
#define STACK_MIN_SIZE
Abort if less stack during eval.
TODO: Rename this file - func.h is stupid.
bool field_is_equal_to_item(Field *field, Item *item)
bool check_stack_overrun(Session *session, long margin, void *)
static void get_sweep_read_cost(Table *table, ha_rows nrows, bool interrupted, optimizer::CostVector *cost)
unsigned char * null_ref_key