The world's most popular open source database
mysql/src/5.1-dbg/sql/opt_range.cc File Reference
#include "mysql_priv.h"#include <m_ctype.h>#include "sql_select.h"Include dependency graph for opt_range.cc:
Go to the source code of this file.
Define Documentation
| #define CLONE_KEY1_MAYBE 1 |
| #define CLONE_KEY2_MAYBE 2 |
Definition at line 82 of file opt_range.cc.
Referenced by get_best_ror_intersect(), and ror_intersect_add().
| #define NOT_IN_IGNORE_THRESHOLD 1000 |
Referenced by get_func_mm_tree().
| #define test_rb_tree | ( | A, | |||
| B | ) | {} |
Definition at line 74 of file opt_range.cc.
Referenced by SEL_ARG::rb_insert(), test_rb_tree(), and SEL_ARG::tree_delete().
| #define test_use_count | ( | A | ) | {} |
Definition at line 75 of file opt_range.cc.
Typedef Documentation
| typedef struct st_ror_scan_info ROR_SCAN_INFO |
Function Documentation
Definition at line 5908 of file opt_range.cc.
References SEL_ARG::IMPOSSIBLE, SEL_ARG::increment_use_count(), key1, key2, key_and(), SEL_ARG::MAYBE_KEY, SEL_ARG::next, SEL_ARG::next_key_part, null_element, and SEL_ARG::type.
Referenced by key_and().
05909 { 05910 SEL_ARG *next; 05911 ulong use_count=key1->use_count; 05912 05913 if (key1->elements != 1) 05914 { 05915 key2->use_count+=key1->elements-1; 05916 key2->increment_use_count((int) key1->elements-1); 05917 } 05918 if (key1->type == SEL_ARG::MAYBE_KEY) 05919 { 05920 key1->right= key1->left= &null_element; 05921 key1->next= key1->prev= 0; 05922 } 05923 for (next=key1->first(); next ; next=next->next) 05924 { 05925 if (next->next_key_part) 05926 { 05927 SEL_ARG *tmp=key_and(next->next_key_part,key2,clone_flag); 05928 if (tmp && tmp->type == SEL_ARG::IMPOSSIBLE) 05929 { 05930 key1=key1->tree_delete(next); 05931 continue; 05932 } 05933 next->next_key_part=tmp; 05934 if (use_count) 05935 next->increment_use_count(use_count); 05936 } 05937 else 05938 next->next_key_part=key2; 05939 } 05940 if (!key1) 05941 return &null_element; // Impossible ranges 05942 key1->use_count++; 05943 return key1; 05944 }
Here is the call graph for this function:
Here is the caller graph for this function:
| static bool check_group_min_max_predicates | ( | COND * | cond, | |
| Item_field * | min_max_arg_item, | |||
| Field::imagetype | image_type | |||
| ) | [static] |
Definition at line 9172 of file opt_range.cc.
References args, Item_func::argument_count(), Item_func::arguments(), Item_func::BETWEEN, bzero, Field::cmp_type(), Item::compare_collation(), cond, Item::COND_ITEM, Item::const_item(), DBUG_ASSERT, DBUG_ENTER, DBUG_PRINT, DBUG_RETURN, Item_field::eq(), Item_func::EQ_FUNC, Item_func::EQUAL_FUNC, FALSE, Item_field::field, Item::FIELD_ITEM, Item::full_name(), Item::FUNC_ITEM, Item_func::func_name(), Item_func::functype(), Item_func::GE_FUNC, Item_func::GT_FUNC, Item_func::ISNOTNULL_FUNC, Item_func::ISNULL_FUNC, Field::itRAW, Item_func::LE_FUNC, Item_func::LT_FUNC, Item_func::NE_FUNC, Item_field::result_type(), simple_pred(), STRING_RESULT, Item::SUBSELECT_ITEM, TRUE, and Item::type().
Referenced by get_best_group_min_max().
09174 { 09175 DBUG_ENTER("check_group_min_max_predicates"); 09176 DBUG_ASSERT(cond && min_max_arg_item); 09177 09178 Item::Type cond_type= cond->type(); 09179 if (cond_type == Item::COND_ITEM) /* 'AND' or 'OR' */ 09180 { 09181 DBUG_PRINT("info", ("Analyzing: %s", ((Item_func*) cond)->func_name())); 09182 List_iterator_fast<Item> li(*((Item_cond*) cond)->argument_list()); 09183 Item *and_or_arg; 09184 while ((and_or_arg= li++)) 09185 { 09186 if (!check_group_min_max_predicates(and_or_arg, min_max_arg_item, 09187 image_type)) 09188 DBUG_RETURN(FALSE); 09189 } 09190 DBUG_RETURN(TRUE); 09191 } 09192 09193 /* 09194 TODO: 09195 This is a very crude fix to handle sub-selects in the WHERE clause 09196 (Item_subselect objects). With the test below we rule out from the 09197 optimization all queries with subselects in the WHERE clause. What has to 09198 be done, is that here we should analyze whether the subselect references 09199 the MIN/MAX argument field, and disallow the optimization only if this is 09200 so. 09201 */ 09202 if (cond_type == Item::SUBSELECT_ITEM) 09203 DBUG_RETURN(FALSE); 09204 09205 /* We presume that at this point there are no other Items than functions. */ 09206 DBUG_ASSERT(cond_type == Item::FUNC_ITEM); 09207 09208 /* Test if cond references only group-by or non-group fields. */ 09209 Item_func *pred= (Item_func*) cond; 09210 Item **arguments= pred->arguments(); 09211 Item *cur_arg; 09212 DBUG_PRINT("info", ("Analyzing: %s", pred->func_name())); 09213 for (uint arg_idx= 0; arg_idx < pred->argument_count (); arg_idx++) 09214 { 09215 cur_arg= arguments[arg_idx]; 09216 DBUG_PRINT("info", ("cur_arg: %s", cur_arg->full_name())); 09217 if (cur_arg->type() == Item::FIELD_ITEM) 09218 { 09219 if (min_max_arg_item->eq(cur_arg, 1)) 09220 { 09221 /* 09222 If pred references the MIN/MAX argument, check whether pred is a range 09223 condition that compares the MIN/MAX argument with a constant. 09224 */ 09225 Item_func::Functype pred_type= pred->functype(); 09226 if (pred_type != Item_func::EQUAL_FUNC && 09227 pred_type != Item_func::LT_FUNC && 09228 pred_type != Item_func::LE_FUNC && 09229 pred_type != Item_func::GT_FUNC && 09230 pred_type != Item_func::GE_FUNC && 09231 pred_type != Item_func::BETWEEN && 09232 pred_type != Item_func::ISNULL_FUNC && 09233 pred_type != Item_func::ISNOTNULL_FUNC && 09234 pred_type != Item_func::EQ_FUNC && 09235 pred_type != Item_func::NE_FUNC) 09236 DBUG_RETURN(FALSE); 09237 09238 /* Check that pred compares min_max_arg_item with a constant. */ 09239 Item *args[3]; 09240 bzero(args, 3 * sizeof(Item*)); 09241 bool inv; 09242 /* Test if this is a comparison of a field and a constant. */ 09243 if (!simple_pred(pred, args, &inv)) 09244 DBUG_RETURN(FALSE); 09245 09246 /* Check for compatible string comparisons - similar to get_mm_leaf. */ 09247 if (args[0] && args[1] && !args[2] && // this is a binary function 09248 min_max_arg_item->result_type() == STRING_RESULT && 09249 /* 09250 Don't use an index when comparing strings of different collations. 09251 */ 09252 ((args[1]->result_type() == STRING_RESULT && 09253 image_type == Field::itRAW && 09254 ((Field_str*) min_max_arg_item->field)->charset() != 09255 pred->compare_collation()) 09256 || 09257 /* 09258 We can't always use indexes when comparing a string index to a 09259 number. 09260 */ 09261 (args[1]->result_type() != STRING_RESULT && 09262 min_max_arg_item->field->cmp_type() != args[1]->result_type()))) 09263 DBUG_RETURN(FALSE); 09264 } 09265 } 09266 else if (cur_arg->type() == Item::FUNC_ITEM) 09267 { 09268 if (!check_group_min_max_predicates(cur_arg, min_max_arg_item, 09269 image_type)) 09270 DBUG_RETURN(FALSE); 09271 } 09272 else if (cur_arg->const_item()) 09273 { 09274 DBUG_RETURN(TRUE); 09275 } 09276 else 09277 DBUG_RETURN(FALSE); 09278 } 09279 09280 DBUG_RETURN(TRUE); 09281 }
Here is the call graph for this function:
Here is the caller graph for this function:
| static ha_rows check_quick_keys | ( | PARAM * | param, | |
| uint | index, | |||
| SEL_ARG * | key_tree, | |||
| char * | min_key, | |||
| uint | min_key_flag, | |||
| char * | max_key, | |||
| uint | max_key_flag | |||
| ) | [static] |
Definition at line 6982 of file opt_range.cc.
References FALSE, st_table::field, st_table::file, st_key_range::flag, st_key::flags, GEOM_FLAG, HA_END_SPACE_KEY, HA_NOSAME, HA_POS_ERROR, HA_READ_AFTER_KEY, HA_READ_BEFORE_KEY, HA_READ_KEY_EXACT, is_key_scan_ror(), PARAM::is_ror_scan, st_key_range::key, PARAM::key, st_table::key_info, Field::key_length(), st_key::key_parts, SEL_ARG::KEY_RANGE, SEL_ARG::left, st_key_range::length, st_key_part::length, max, SEL_ARG::max_flag, PARAM::max_key, PARAM::max_key_part, memcmp(), SEL_ARG::min_flag, PARAM::min_key, PARAM::n_ranges, NEAR_MAX, NEAR_MIN, SEL_ARG::next_key_part, null_element, SEL_ARG::part, PARAM::range_count, RANGE_OPT_PARAM::real_keynr, records, handler::records_in_range(), SEL_ARG::right, SEL_ARG::store(), SEL_ARG::store_max_key(), SEL_ARG::store_min_key(), RANGE_OPT_PARAM::table, and SEL_ARG::type.
Referenced by check_quick_select().
06985 { 06986 ha_rows records=0, tmp; 06987 uint tmp_min_flag, tmp_max_flag, keynr, min_key_length, max_key_length; 06988 char *tmp_min_key, *tmp_max_key; 06989 06990 param->max_key_part=max(param->max_key_part,key_tree->part); 06991 if (key_tree->left != &null_element) 06992 { 06993 /* 06994 There are at least two intervals for current key part, i.e. condition 06995 was converted to something like 06996 (keyXpartY less/equals c1) OR (keyXpartY more/equals c2). 06997 This is not a ROR scan if the key is not Clustered Primary Key. 06998 */ 06999 param->is_ror_scan= FALSE; 07000 records=check_quick_keys(param,idx,key_tree->left,min_key,min_key_flag, 07001 max_key,max_key_flag); 07002 if (records == HA_POS_ERROR) // Impossible 07003 return records; 07004 } 07005 07006 tmp_min_key= min_key; 07007 tmp_max_key= max_key; 07008 key_tree->store(param->key[idx][key_tree->part].store_length, 07009 &tmp_min_key,min_key_flag,&tmp_max_key,max_key_flag); 07010 min_key_length= (uint) (tmp_min_key- param->min_key); 07011 max_key_length= (uint) (tmp_max_key- param->max_key); 07012 07013 if (param->is_ror_scan) 07014 { 07015 /* 07016 If the index doesn't cover entire key, mark the scan as non-ROR scan. 07017 Actually we're cutting off some ROR scans here. 07018 */ 07019 uint16 fieldnr= param->table->key_info[param->real_keynr[idx]]. 07020 key_part[key_tree->part].fieldnr - 1; 07021 if (param->table->field[fieldnr]->key_length() != 07022 param->key[idx][key_tree->part].length) 07023 param->is_ror_scan= FALSE; 07024 } 07025 07026 if (key_tree->next_key_part && 07027 key_tree->next_key_part->part == key_tree->part+1 && 07028 key_tree->next_key_part->type == SEL_ARG::KEY_RANGE) 07029 { // const key as prefix 07030 if (min_key_length == max_key_length && 07031 !memcmp(min_key,max_key, (uint) (tmp_max_key - max_key)) && 07032 !key_tree->min_flag && !key_tree->max_flag) 07033 { 07034 tmp=check_quick_keys(param,idx,key_tree->next_key_part, 07035 tmp_min_key, min_key_flag | key_tree->min_flag, 07036 tmp_max_key, max_key_flag | key_tree->max_flag); 07037 goto end; // Ugly, but efficient 07038 } 07039 else 07040 { 07041 /* The interval for current key part is not c1 <= keyXpartY <= c1 */ 07042 param->is_ror_scan= FALSE; 07043 } 07044 07045 tmp_min_flag=key_tree->min_flag; 07046 tmp_max_flag=key_tree->max_flag; 07047 if (!tmp_min_flag) 07048 key_tree->next_key_part->store_min_key(param->key[idx], &tmp_min_key, 07049 &tmp_min_flag); 07050 if (!tmp_max_flag) 07051 key_tree->next_key_part->store_max_key(param->key[idx], &tmp_max_key, 07052 &tmp_max_flag); 07053 min_key_length= (uint) (tmp_min_key- param->min_key); 07054 max_key_length= (uint) (tmp_max_key- param->max_key); 07055 } 07056 else 07057 { 07058 tmp_min_flag=min_key_flag | key_tree->min_flag; 07059 tmp_max_flag=max_key_flag | key_tree->max_flag; 07060 } 07061 07062 keynr=param->real_keynr[idx]; 07063 param->range_count++; 07064 if (!tmp_min_flag && ! tmp_max_flag && 07065 (uint) key_tree->part+1 == param->table->key_info[keynr].key_parts && 07066 (param->table->key_info[keynr].flags & (HA_NOSAME | HA_END_SPACE_KEY)) == 07067 HA_NOSAME && 07068 min_key_length == max_key_length && 07069 !memcmp(param->min_key,param->max_key,min_key_length)) 07070 { 07071 tmp=1; // Max one record 07072 param->n_ranges++; 07073 } 07074 else 07075 { 07076 if (param->is_ror_scan) 07077 { 07078 /* 07079 If we get here, the condition on the key was converted to form 07080 "(keyXpart1 = c1) AND ... AND (keyXpart{key_tree->part - 1} = cN) AND 07081 somecond(keyXpart{key_tree->part})" 07082 Check if 07083 somecond is "keyXpart{key_tree->part} = const" and 07084 uncovered "tail" of KeyX parts is either empty or is identical to 07085 first members of clustered primary key. 07086 */ 07087 if (!(min_key_length == max_key_length && 07088 !memcmp(min_key,max_key, (uint) (tmp_max_key - max_key)) && 07089 !key_tree->min_flag && !key_tree->max_flag && 07090 is_key_scan_ror(param, keynr, key_tree->part + 1))) 07091 param->is_ror_scan= FALSE; 07092 } 07093 param->n_ranges++; 07094 07095 if (tmp_min_flag & GEOM_FLAG) 07096 { 07097 key_range min_range; 07098 min_range.key= (byte*) param->min_key; 07099 min_range.length= min_key_length; 07100 /* In this case tmp_min_flag contains the handler-read-function */ 07101 min_range.flag= (ha_rkey_function) (tmp_min_flag ^ GEOM_FLAG); 07102 07103 tmp= param->table->file->records_in_range(keynr, &min_range, 07104 (key_range*) 0); 07105 } 07106 else 07107 { 07108 key_range min_range, max_range; 07109 07110 min_range.key= (byte*) param->min_key; 07111 min_range.length= min_key_length; 07112 min_range.flag= (tmp_min_flag & NEAR_MIN ? HA_READ_AFTER_KEY : 07113 HA_READ_KEY_EXACT); 07114 max_range.key= (byte*) param->max_key; 07115 max_range.length= max_key_length; 07116 max_range.flag= (tmp_max_flag & NEAR_MAX ? 07117 HA_READ_BEFORE_KEY : HA_READ_AFTER_KEY); 07118 tmp=param->table->file->records_in_range(keynr, 07119 (min_key_length ? &min_range : 07120 (key_range*) 0), 07121 (max_key_length ? &max_range : 07122 (key_range*) 0)); 07123 } 07124 } 07125 end: 07126 if (tmp == HA_POS_ERROR) // Impossible range 07127 return tmp; 07128 records+=tmp; 07129 if (key_tree->right != &null_element) 07130 { 07131 /* 07132 There are at least two intervals for current key part, i.e. condition 07133 was converted to something like 07134 (keyXpartY less/equals c1) OR (keyXpartY more/equals c2). 07135 This is not a ROR scan if the key is not Clustered Primary Key. 07136 */ 07137 param->is_ror_scan= FALSE; 07138 tmp=check_quick_keys(param,idx,key_tree->right,min_key,min_key_flag, 07139 max_key,max_key_flag); 07140 if (tmp == HA_POS_ERROR) 07141 return tmp; 07142 records+=tmp; 07143 } 07144 return records; 07145 }
Here is the call graph for this function:
Here is the caller graph for this function:
| static ha_rows check_quick_select | ( | PARAM * | param, | |
| uint | index, | |||
| SEL_ARG * | key_tree, | |||
| bool | update_tbl_stats | |||
| ) | [static] |
Definition at line 6881 of file opt_range.cc.
References st_key::algorithm, check_quick_keys(), DBUG_ENTER, DBUG_PRINT, DBUG_RETURN, FALSE, st_table::file, HA_KEY_ALG_BTREE, HA_KEY_ALG_UNDEF, HA_KEY_SCAN_NOT_ROR, HA_POS_ERROR, SEL_ARG::IMPOSSIBLE, handler::index_flags(), PARAM::is_ror_scan, key, st_table::key_info, SEL_ARG::KEY_RANGE, PARAM::max_key, PARAM::max_key_part, min, PARAM::min_key, PARAM::n_ranges, SEL_ARG::part, st_table_share::primary_key, handler::primary_key_is_clustered(), st_table::quick_condition_rows, st_table::quick_key_parts, st_table::quick_keys, st_table::quick_n_ranges, st_table::quick_rows, PARAM::range_count, RANGE_OPT_PARAM::real_keynr, records, st_table::s, Bitmap< 64 >::set_bit(), RANGE_OPT_PARAM::table, TRUE, and SEL_ARG::type.
Referenced by get_best_group_min_max(), and get_key_scans_params().
06882 { 06883 ha_rows records; 06884 bool cpk_scan; 06885 uint key; 06886 DBUG_ENTER("check_quick_select"); 06887 06888 param->is_ror_scan= FALSE; 06889 06890 if (!tree) 06891 DBUG_RETURN(HA_POS_ERROR); // Can't use it 06892 param->max_key_part=0; 06893 param->range_count=0; 06894 key= param->real_keynr[idx]; 06895 06896 if (tree->type == SEL_ARG::IMPOSSIBLE) 06897 DBUG_RETURN(0L); // Impossible select. return 06898 if (tree->type != SEL_ARG::KEY_RANGE || tree->part != 0) 06899 DBUG_RETURN(HA_POS_ERROR); // Don't use tree 06900 06901 enum ha_key_alg key_alg= param->table->key_info[key].algorithm; 06902 if ((key_alg != HA_KEY_ALG_BTREE) && (key_alg!= HA_KEY_ALG_UNDEF)) 06903 { 06904 /* Records are not ordered by rowid for other types of indexes. */ 06905 cpk_scan= FALSE; 06906 } 06907 else 06908 { 06909 /* 06910 Clustered PK scan is a special case, check_quick_keys doesn't recognize 06911 CPK scans as ROR scans (while actually any CPK scan is a ROR scan). 06912 */ 06913 cpk_scan= ((param->table->s->primary_key == param->real_keynr[idx]) && 06914 param->table->file->primary_key_is_clustered()); 06915 param->is_ror_scan= !cpk_scan; 06916 } 06917 param->n_ranges= 0; 06918 06919 records=check_quick_keys(param,idx,tree,param->min_key,0,param->max_key,0); 06920 if (records != HA_POS_ERROR) 06921 { 06922 if (update_tbl_stats) 06923 { 06924 param->table->quick_keys.set_bit(key); 06925 param->table->quick_key_parts[key]=param->max_key_part+1; 06926 param->table->quick_n_ranges[key]= param->n_ranges; 06927 param->table->quick_condition_rows= 06928 min(param->table->quick_condition_rows, records); 06929 } 06930 /* 06931 Need to save quick_rows in any case as it is used when calculating 06932 cost of ROR intersection: 06933 */ 06934 param->table->quick_rows[key]=records; 06935 if (cpk_scan) 06936 param->is_ror_scan= TRUE; 06937 } 06938 if (param->table->file->index_flags(key, 0, TRUE) & HA_KEY_SCAN_NOT_ROR) 06939 param->is_ror_scan= FALSE; 06940 DBUG_PRINT("exit", ("Records: %lu", (ulong) records)); 06941 DBUG_RETURN(records); 06942 }
Here is the call graph for this function:
Here is the caller graph for this function:
| static int cmp_ror_scan_info | ( | ROR_SCAN_INFO ** | a, | |
| ROR_SCAN_INFO ** | b | |||
| ) | [static] |
Definition at line 3853 of file opt_range.cc.
References rows2double.
Referenced by get_best_ror_intersect().
03854 { 03855 double val1= rows2double((*a)->records) * (*a)->key_rec_length; 03856 double val2= rows2double((*b)->records) * (*b)->key_rec_length; 03857 return (val1 < val2)? -1: (val1 == val2)? 0 : 1; 03858 }
Here is the caller graph for this function:
| static int cmp_ror_scan_info_covering | ( | ROR_SCAN_INFO ** | a, | |
| ROR_SCAN_INFO ** | b | |||
| ) | [static] |
Definition at line 3877 of file opt_range.cc.
Referenced by get_best_covering_ror_intersect().
03878 { 03879 if ((*a)->used_fields_covered > (*b)->used_fields_covered) 03880 return -1; 03881 if ((*a)->used_fields_covered < (*b)->used_fields_covered) 03882 return 1; 03883 if ((*a)->key_components < (*b)->key_components) 03884 return -1; 03885 if ((*a)->key_components > (*b)->key_components) 03886 return 1; 03887 if ((*a)->first_uncovered_field < (*b)->first_uncovered_field) 03888 return -1; 03889 if ((*a)->first_uncovered_field > (*b)->first_uncovered_field) 03890 return 1; 03891 return 0; 03892 }
Here is the caller graph for this function:
| void cost_group_min_max | ( | TABLE * | table, | |
| KEY * | index_info, | |||
| uint | used_key_parts, | |||
| uint | group_key_parts, | |||
| SEL_TREE * | range_tree, | |||
| SEL_ARG * | index_tree, | |||
| ha_rows | quick_prefix_records, | |||
| bool | have_min, | |||
| bool | have_max, | |||
| double * | read_cost, | |||
| ha_rows * | records | |||
| ) | [static] |
Definition at line 9511 of file opt_range.cc.
References ha_statistics::block_size, DBUG_ENTER, DBUG_PRINT, DBUG_VOID_RETURN, st_table::file, HA_POS_ERROR, st_key::key_length, min, st_key::rec_per_key, ha_statistics::records, handler::ref_length, rint, set_if_bigger, handler::stats, and TIME_FOR_COMPARE.
Referenced by get_best_group_min_max().
09516 { 09517 uint table_records; 09518 uint num_groups; 09519 uint num_blocks; 09520 uint keys_per_block; 09521 uint keys_per_group; 09522 uint keys_per_subgroup; /* Average number of keys in sub-groups */ 09523 /* formed by a key infix. */ 09524 double p_overlap; /* Probability that a sub-group overlaps two blocks. */ 09525 double quick_prefix_selectivity; 09526 double io_cost; 09527 double cpu_cost= 0; /* TODO: CPU cost of index_read calls? */ 09528 DBUG_ENTER("cost_group_min_max"); 09529 09530 table_records= table->file->stats.records; 09531 keys_per_block= (table->file->stats.block_size / 2 / 09532 (index_info->key_length + table->file->ref_length) 09533 + 1); 09534 num_blocks= (table_records / keys_per_block) + 1; 09535 09536 /* Compute the number of keys in a group. */ 09537 keys_per_group= index_info->rec_per_key[group_key_parts - 1]; 09538 if (keys_per_group == 0) /* If there is no statistics try to guess */ 09539 /* each group contains 10% of all records */ 09540 keys_per_group= (table_records / 10) + 1; 09541 num_groups= (table_records / keys_per_group) + 1; 09542 09543 /* Apply the selectivity of the quick select for group prefixes. */ 09544 if (range_tree && (quick_prefix_records != HA_POS_ERROR)) 09545 { 09546 quick_prefix_selectivity= (double) quick_prefix_records / 09547 (double) table_records; 09548 num_groups= (uint) rint(num_groups * quick_prefix_selectivity); 09549 set_if_bigger(num_groups, 1); 09550 } 09551 09552 if (used_key_parts > group_key_parts) 09553 { /* 09554 Compute the probability that two ends of a subgroup are inside 09555 different blocks. 09556 */ 09557 keys_per_subgroup= index_info->rec_per_key[used_key_parts - 1]; 09558 if (keys_per_subgroup >= keys_per_block) /* If a subgroup is bigger than */ 09559 p_overlap= 1.0; /* a block, it will overlap at least two blocks. */ 09560 else 09561 { 09562 double blocks_per_group= (double) num_blocks / (double) num_groups; 09563 p_overlap= (blocks_per_group * (keys_per_subgroup - 1)) / keys_per_group; 09564 p_overlap= min(p_overlap, 1.0); 09565 } 09566 io_cost= (double) min(num_groups * (1 + p_overlap), num_blocks); 09567 } 09568 else 09569 io_cost= (keys_per_group > keys_per_block) ? 09570 (have_min && have_max) ? (double) (num_groups + 1) : 09571 (double) num_groups : 09572 (double) num_blocks; 09573 09574 /* 09575 TODO: If there is no WHERE clause and no other expressions, there should be 09576 no CPU cost. We leave it here to make this cost comparable to that of index 09577 scan as computed in SQL_SELECT::test_quick_select(). 09578 */ 09579 cpu_cost= (double) num_groups / TIME_FOR_COMPARE; 09580 09581 *read_cost= io_cost + cpu_cost; 09582 *records= num_groups; 09583 09584 DBUG_PRINT("info", 09585 ("table rows=%u, keys/block=%u, keys/group=%u, result rows=%u, blocks=%u", 09586 table_records, keys_per_block, keys_per_group, *records, 09587 num_blocks)); 09588 DBUG_VOID_RETURN; 09589 }
Here is the caller graph for this function:
Definition at line 6353 of file opt_range.cc.
References SEL_ARG::is_same(), SEL_ARG::left, SEL_ARG::next_key_part, null_element, and SEL_ARG::right.
Referenced by key_or().
06354 { 06355 if (a == b) 06356 return 1; 06357 if (!a || !b || !a->is_same(b)) 06358 return 0; 06359 if (a->left != &null_element && b->left != &null_element) 06360 { 06361 if (!eq_tree(a->left,b->left)) 06362 return 0; 06363 } 06364 else if (a->left != &null_element || b->left != &null_element) 06365 return 0; 06366 if (a->right != &null_element && b->right != &null_element) 06367 { 06368 if (!eq_tree(a->right,b->right)) 06369 return 0; 06370 } 06371 else if (a->right != &null_element || b->right != &null_element) 06372 return 0; 06373 if (a->next_key_part != b->next_key_part) 06374 { // Sub range 06375 if (!a->next_key_part != !b->next_key_part || 06376 !eq_tree(a->next_key_part, b->next_key_part)) 06377 return 0; 06378 } 06379 return 1; 06380 }
Here is the call graph for this function:
Here is the caller graph for this function:
| static int fill_used_fields_bitmap | ( | PARAM * | param | ) | [static] |
Definition at line 1914 of file opt_range.cc.
References alloc_root(), bitmap_clear_bit(), bitmap_copy(), bitmap_init(), bitmap_union(), st_table_share::column_bitmap_size, FALSE, st_table_share::fields, PARAM::fields_bitmap_size, st_table::file, st_table::key_info, st_key::key_part, st_key::key_parts, MAX_KEY, RANGE_OPT_PARAM::mem_root, PARAM::needed_fields, st_table_share::primary_key, handler::primary_key_is_clustered(), st_table::read_set, st_table::s, RANGE_OPT_PARAM::table, and st_table::write_set.
Referenced by SQL_SELECT::test_quick_select().
01915 { 01916 TABLE *table= param->table; 01917 my_bitmap_map *tmp; 01918 uint pk; 01919 param->fields_bitmap_size= table->s->column_bitmap_size; 01920 if (!(tmp= (my_bitmap_map*) alloc_root(param->mem_root, 01921 param->fields_bitmap_size)) || 01922 bitmap_init(¶m->needed_fields, tmp, table->s->fields, FALSE)) 01923 return 1; 01924 01925 bitmap_copy(¶m->needed_fields, table->read_set); 01926 bitmap_union(¶m->needed_fields, table->write_set); 01927 01928 pk= param->table->s->primary_key; 01929 if (pk != MAX_KEY && param->table->file->primary_key_is_clustered()) 01930 { 01931 /* The table uses clustered PK and it is not internally generated */ 01932 KEY_PART_INFO *key_part= param->table->key_info[pk].key_part; 01933 KEY_PART_INFO *key_part_end= key_part + 01934 param->table->key_info[pk].key_parts; 01935 for (;key_part != key_part_end; ++key_part) 01936 bitmap_clear_bit(¶m->needed_fields, key_part->fieldnr-1); 01937 } 01938 return 0; 01939 }
Here is the call graph for this function:
Here is the caller graph for this function:
| static TRP_ROR_INTERSECT * get_best_covering_ror_intersect | ( | PARAM * | param, | |
| SEL_TREE * | tree, | |||
| double | read_time | |||
| ) | [static] |
Definition at line 4477 of file opt_range.cc.
References alloc_root(), bitmap_bits_set(), bitmap_clear_all, bitmap_get_first(), bitmap_init(), bitmap_is_subset(), bitmap_subtract(), bitmap_union(), cmp_ror_scan_info_covering(), DBUG_ENTER, DBUG_EXECUTE, DBUG_PRINT, DBUG_RETURN, FALSE, st_table_share::fields, st_table::key_info, st_key::key_parts, log(), M_LN2, MAX_KEY, RANGE_OPT_PARAM::mem_root, memcpy, st_key::name, PARAM::needed_fields, NULL, print_ror_scans_arr(), qsort(), qsort_cmp, st_table::quick_condition_rows, records, SEL_TREE::ror_scans, SEL_TREE::ror_scans_end, rows2double, st_table::s, set_if_smaller, RANGE_OPT_PARAM::table, TIME_FOR_COMPARE_ROWID, and TRUE.
Referenced by SQL_SELECT::test_quick_select().
04480 { 04481 ROR_SCAN_INFO **ror_scan_mark; 04482 ROR_SCAN_INFO **ror_scans_end= tree->ror_scans_end; 04483 DBUG_ENTER("get_best_covering_ror_intersect"); 04484 04485 for (ROR_SCAN_INFO **scan= tree->ror_scans; scan != ror_scans_end; ++scan) 04486 (*scan)->key_components= 04487 param->table->key_info[(*scan)->keynr].key_parts; 04488 04489 /* 04490 Run covering-ROR-search algorithm. 04491 Assume set I is [ror_scan .. ror_scans_end) 04492 */ 04493 04494 /*I=set of all covering indexes */ 04495 ror_scan_mark= tree->ror_scans; 04496 04497 my_bitmap_map int_buf[MAX_KEY/(sizeof(my_bitmap_map)*8)+1]; 04498 MY_BITMAP covered_fields; 04499 if (bitmap_init(&covered_fields, int_buf, param->table->s->fields, FALSE)) 04500 DBUG_RETURN(0); 04501 bitmap_clear_all(&covered_fields); 04502 04503 double total_cost= 0.0f; 04504 ha_rows records=0; 04505 bool all_covered; 04506 04507 DBUG_PRINT("info", ("Building covering ROR-intersection")); 04508 DBUG_EXECUTE("info", print_ror_scans_arr(param->table, 04509 "building covering ROR-I", 04510 ror_scan_mark, ror_scans_end);); 04511 do 04512 { 04513 /* 04514 Update changed sorting info: 04515 #covered fields, 04516 number of first not covered component 04517 Calculate and save these values for each of remaining scans. 04518 */ 04519 for (ROR_SCAN_INFO **scan= ror_scan_mark; scan != ror_scans_end; ++scan) 04520 { 04521 bitmap_subtract(&(*scan)->covered_fields, &covered_fields); 04522 (*scan)->used_fields_covered= 04523 bitmap_bits_set(&(*scan)->covered_fields); 04524 (*scan)->first_uncovered_field= 04525 bitmap_get_first(&(*scan)->covered_fields); 04526 } 04527 04528 qsort(ror_scan_mark, ror_scans_end-ror_scan_mark, sizeof(ROR_SCAN_INFO*), 04529 (qsort_cmp)cmp_ror_scan_info_covering); 04530 04531 DBUG_EXECUTE("info", print_ror_scans_arr(param->table, 04532 "remaining scans", 04533 ror_scan_mark, ror_scans_end);); 04534 04535 /* I=I-first(I) */ 04536 total_cost += (*ror_scan_mark)->index_read_cost; 04537 records += (*ror_scan_mark)->records; 04538 DBUG_PRINT("info", ("Adding scan on %s", 04539 param->table->key_info[(*ror_scan_mark)->keynr].name)); 04540 if (total_cost > read_time) 04541 DBUG_RETURN(NULL); 04542 /* F=F-covered by first(I) */ 04543 bitmap_union(&covered_fields, &(*ror_scan_mark)->covered_fields); 04544 all_covered= bitmap_is_subset(¶m->needed_fields, &covered_fields); 04545 } while ((++ror_scan_mark < ror_scans_end) && !all_covered); 04546 04547 if (!all_covered || (ror_scan_mark - tree->ror_scans) == 1) 04548 DBUG_RETURN(NULL); 04549 04550 /* 04551 Ok, [tree->ror_scans .. ror_scan) holds covering index_intersection with 04552 cost total_cost. 04553 */ 04554 DBUG_PRINT("info", ("Covering ROR-intersect scans cost: %g", total_cost)); 04555 DBUG_EXECUTE("info", print_ror_scans_arr(param->table, 04556 "creating covering ROR-intersect", 04557 tree->ror_scans, ror_scan_mark);); 04558 04559 /* Add priority queue use cost. */ 04560 total_cost += rows2double(records)* 04561 log((double)(ror_scan_mark - tree->ror_scans)) / 04562 (TIME_FOR_COMPARE_ROWID * M_LN2); 04563 DBUG_PRINT("info", ("Covering ROR-intersect full cost: %g", total_cost)); 04564 04565 if (total_cost > read_time) 04566 DBUG_RETURN(NULL); 04567 04568 TRP_ROR_INTERSECT *trp; 04569 if (!(trp= new (param->mem_root) TRP_ROR_INTERSECT)) 04570 DBUG_RETURN(trp); 04571 uint best_num= (ror_scan_mark - tree->ror_scans); 04572 if (!(trp->first_scan= (ROR_SCAN_INFO**)alloc_root(param->mem_root, 04573 sizeof(ROR_SCAN_INFO*)* 04574 best_num))) 04575 DBUG_RETURN(NULL); 04576 memcpy(trp->first_scan, tree->ror_scans, best_num*sizeof(ROR_SCAN_INFO*)); 04577 trp->last_scan= trp->first_scan + best_num; 04578 trp->is_covering= TRUE; 04579 trp->read_cost= total_cost; 04580 trp->records= records; 04581 trp->cpk_scan= NULL; 04582 set_if_smaller(param->table->quick_condition_rows, records); 04583 04584 DBUG_PRINT("info", 04585 ("Returning covering ROR-intersect plan: cost %g, records %lu", 04586 trp->read_cost, (ulong) trp->records)); 04587 DBUG_RETURN(trp); 04588 }
Here is the call graph for this function:
Here is the caller graph for this function:
| static TABLE_READ_PLAN * get_best_disjunct_quick | ( | PARAM * | param, | |
| SEL_IMERGE * | imerge, | |||
| double | read_time | |||
| ) | [static] |
Definition at line 3490 of file opt_range.cc.
References alloc_root(), DBL_MAX, DBUG_ENTER, DBUG_EXECUTE, DBUG_PRINT, DBUG_RETURN, FALSE, st_table::file, TRP_ROR_UNION::first_ror, get_best_ror_intersect(), get_key_scans_params(), get_sweep_read_cost(), PARAM::imerge_cost_buff, PARAM::imerge_cost_buff_size, TABLE_READ_PLAN::is_ror, SEL_TREE::keys_map, TRP_ROR_UNION::last_ror, log(), M_LN2, RANGE_OPT_PARAM::mem_root, min, NULL, st_table_share::primary_key, handler::primary_key_is_clustered(), print_sel_tree(), TRP_INDEX_MERGE::range_scans, TRP_INDEX_MERGE::range_scans_end, TABLE_READ_PLAN::read_cost, RANGE_OPT_PARAM::real_keynr, ha_statistics::records, TABLE_READ_PLAN::records, handler::ref_length, rows2double, st_table::s, SQLCOM_DELETE, handler::stats, RANGE_OPT_PARAM::table, RANGE_OPT_PARAM::thd, TIME_FOR_COMPARE, TIME_FOR_COMPARE_ROWID, SEL_IMERGE::trees, SEL_IMERGE::trees_next, and TRUE.
Referenced by SQL_SELECT::test_quick_select().
03492 { 03493 SEL_TREE **ptree; 03494 TRP_INDEX_MERGE *imerge_trp= NULL; 03495 uint n_child_scans= imerge->trees_next - imerge->trees; 03496 TRP_RANGE **range_scans; 03497 TRP_RANGE **cur_child; 03498 TRP_RANGE **cpk_scan= NULL; 03499 bool imerge_too_expensive= FALSE; 03500 double imerge_cost= 0.0; 03501 ha_rows cpk_scan_records= 0; 03502 ha_rows non_cpk_scan_records= 0; 03503 bool pk_is_clustered= param->table->file->primary_key_is_clustered(); 03504 bool all_scans_ror_able= TRUE; 03505 bool all_scans_rors= TRUE; 03506 uint unique_calc_buff_size; 03507 TABLE_READ_PLAN **roru_read_plans; 03508 TABLE_READ_PLAN **cur_roru_plan; 03509 double roru_index_costs; 03510 ha_rows roru_total_records; 03511 double roru_intersect_part= 1.0; 03512 DBUG_ENTER("get_best_disjunct_quick"); 03513 DBUG_PRINT("info", ("Full table scan cost =%g", read_time)); 03514 03515 if (!(range_scans= (TRP_RANGE**)alloc_root(param->mem_root, 03516 sizeof(TRP_RANGE*)* 03517 n_child_scans))) 03518 DBUG_RETURN(NULL); 03519 /* 03520 Collect best 'range' scan for each of disjuncts, and, while doing so, 03521 analyze possibility of ROR scans. Also calculate some values needed by 03522 other parts of the code. 03523 */ 03524 for (ptree= imerge->trees, cur_child= range_scans; 03525 ptree != imerge->trees_next; 03526 ptree++, cur_child++) 03527 { 03528 DBUG_EXECUTE("info", print_sel_tree(param, *ptree, &(*ptree)->keys_map, 03529 "tree in SEL_IMERGE");); 03530 if (!(*cur_child= get_key_scans_params(param, *ptree, TRUE, FALSE, read_time))) 03531 { 03532 /* 03533 One of index scans in this index_merge is more expensive than entire 03534 table read for another available option. The entire index_merge (and 03535 any possible ROR-union) will be more expensive then, too. We continue 03536 here only to update SQL_SELECT members. 03537 */ 03538 imerge_too_expensive= TRUE; 03539 } 03540 if (imerge_too_expensive) 03541 continue; 03542 03543 imerge_cost += (*cur_child)->read_cost; 03544 all_scans_ror_able &= ((*ptree)->n_ror_scans > 0); 03545 all_scans_rors &= (*cur_child)->is_ror; 03546 if (pk_is_clustered && 03547 param->real_keynr[(*cur_child)->key_idx] == 03548 param->table->s->primary_key) 03549 { 03550 cpk_scan= cur_child; 03551 cpk_scan_records= (*cur_child)->records; 03552 } 03553 else 03554 non_cpk_scan_records += (*cur_child)->records; 03555 } 03556 03557 DBUG_PRINT("info", ("index_merge scans cost=%g", imerge_cost)); 03558 if (imerge_too_expensive || (imerge_cost > read_time) || 03559 (non_cpk_scan_records+cpk_scan_records >= param->table->file->stats.records) && 03560 read_time != DBL_MAX) 03561 { 03562 /* 03563 Bail out if it is obvious that both index_merge and ROR-union will be 03564 more expensive 03565 */ 03566 DBUG_PRINT("info", ("Sum of index_merge scans is more expensive than " 03567 "full table scan, bailing out")); 03568 DBUG_RETURN(NULL); 03569 } 03570 if (all_scans_rors) 03571 { 03572 roru_read_plans= (TABLE_READ_PLAN**)range_scans; 03573 goto skip_to_ror_scan; 03574 } 03575 if (cpk_scan) 03576 { 03577 /* 03578 Add one ROWID comparison for each row retrieved on non-CPK scan. (it 03579 is done in QUICK_RANGE_SELECT::row_in_ranges) 03580 */ 03581 imerge_cost += non_cpk_scan_records / TIME_FOR_COMPARE_ROWID; 03582 } 03583 03584 /* Calculate cost(rowid_to_row_scan) */ 03585 imerge_cost += get_sweep_read_cost(param, non_cpk_scan_records); 03586 DBUG_PRINT("info",("index_merge cost with rowid-to-row scan: %g", 03587 imerge_cost)); 03588 if (imerge_cost > read_time) 03589 goto build_ror_index_merge; 03590 03591 /* Add Unique operations cost */ 03592 unique_calc_buff_size= 03593 Unique::get_cost_calc_buff_size(non_cpk_scan_records, 03594 param->table->file->ref_length, 03595 param->thd->variables.sortbuff_size); 03596 if (param->imerge_cost_buff_size < unique_calc_buff_size) 03597 { 03598 if (!(param->imerge_cost_buff= (uint*)alloc_root(param->mem_root, 03599 unique_calc_buff_size))) 03600 DBUG_RETURN(NULL); 03601 param->imerge_cost_buff_size= unique_calc_buff_size; 03602 } 03603 03604 imerge_cost += 03605 Unique::get_use_cost(param->imerge_cost_buff, non_cpk_scan_records, 03606 param->table->file->ref_length, 03607 param->thd->variables.sortbuff_size); 03608 DBUG_PRINT("info",("index_merge total cost: %g (wanted: less then %g)", 03609 imerge_cost, read_time)); 03610 if (imerge_cost < read_time) 03611 { 03612 if ((imerge_trp= new (param->mem_root)TRP_INDEX_MERGE)) 03613 { 03614 imerge_trp->read_cost= imerge_cost; 03615 imerge_trp->records= non_cpk_scan_records + cpk_scan_records; 03616 imerge_trp->records= min(imerge_trp->records, 03617 param->table->file->stats.records); 03618 imerge_trp->range_scans= range_scans; 03619 imerge_trp->range_scans_end= range_scans + n_child_scans; 03620 read_time= imerge_cost; 03621 } 03622 } 03623 03624 build_ror_index_merge: 03625 if (!all_scans_ror_able || param->thd->lex->sql_command == SQLCOM_DELETE) 03626 DBUG_RETURN(imerge_trp); 03627 03628 /* Ok, it is possible to build a ROR-union, try it. */ 03629 bool dummy; 03630 if (!(roru_read_plans= 03631 (TABLE_READ_PLAN**)alloc_root(param->mem_root, 03632 sizeof(TABLE_READ_PLAN*)* 03633 n_child_scans))) 03634 DBUG_RETURN(imerge_trp); 03635 skip_to_ror_scan: 03636 roru_index_costs= 0.0; 03637 roru_total_records= 0; 03638 cur_roru_plan= roru_read_plans; 03639 03640 /* Find 'best' ROR scan for each of trees in disjunction */ 03641 for (ptree= imerge->trees, cur_child= range_scans; 03642 ptree != imerge->trees_next; 03643 ptree++, cur_child++, cur_roru_plan++) 03644 { 03645 /* 03646 Assume the best ROR scan is the one that has cheapest full-row-retrieval 03647 scan cost. 03648 Also accumulate index_only scan costs as we'll need them to calculate 03649 overall index_intersection cost. 03650 */ 03651 double cost; 03652 if ((*cur_child)->is_ror) 03653 { 03654 /* Ok, we have index_only cost, now get full rows scan cost */ 03655 cost= param->table->file-> 03656 read_time(param->real_keynr[(*cur_child)->key_idx], 1, 03657 (*cur_child)->records) + 03658 rows2double((*cur_child)->records) / TIME_FOR_COMPARE; 03659 } 03660 else 03661 cost= read_time; 03662 03663 TABLE_READ_PLAN *prev_plan= *cur_child; 03664 if (!(*cur_roru_plan= get_best_ror_intersect(param, *ptree, cost, 03665 &dummy))) 03666 { 03667 if (prev_plan->is_ror) 03668 *cur_roru_plan= prev_plan; 03669 else 03670 DBUG_RETURN(imerge_trp); 03671 roru_index_costs += (*cur_roru_plan)->read_cost; 03672 } 03673 else 03674 roru_index_costs += 03675 ((TRP_ROR_INTERSECT*)(*cur_roru_plan))->index_scan_costs; 03676 roru_total_records += (*cur_roru_plan)->records; 03677 roru_intersect_part *= (*cur_roru_plan)->records / 03678 param->table->file->stats.records; 03679 } 03680 03681 /* 03682 rows to retrieve= 03683 SUM(rows_in_scan_i) - table_rows * PROD(rows_in_scan_i / table_rows). 03684 This is valid because index_merge construction guarantees that conditions 03685 in disjunction do not share key parts. 03686 */ 03687 roru_total_records -= (ha_rows)(roru_intersect_part* 03688 param->table->file->stats.records); 03689 /* ok, got a ROR read plan for each of the disjuncts 03690 Calculate cost: 03691 cost(index_union_scan(scan_1, ... scan_n)) = 03692 SUM_i(cost_of_index_only_scan(scan_i)) + 03693 queue_use_cost(rowid_len, n) + 03694 cost_of_row_retrieval 03695 See get_merge_buffers_cost function for queue_use_cost formula derivation. 03696 */ 03697 03698 double roru_total_cost; 03699 roru_total_cost= roru_index_costs + 03700 rows2double(roru_total_records)*log((double)n_child_scans) / 03701 (TIME_FOR_COMPARE_ROWID * M_LN2) + 03702 get_sweep_read_cost(param, roru_total_records); 03703 03704 DBUG_PRINT("info", ("ROR-union: cost %g, %d members", roru_total_cost, 03705 n_child_scans)); 03706 TRP_ROR_UNION* roru; 03707 if (roru_total_cost < read_time) 03708 { 03709 if ((roru= new (param->mem_root) TRP_ROR_UNION)) 03710 { 03711 roru->first_ror= roru_read_plans; 03712 roru->last_ror= roru_read_plans + n_child_scans; 03713 roru->read_cost= roru_total_cost; 03714 roru->records= roru_total_records; 03715 DBUG_RETURN(roru); 03716 } 03717 } 03718 DBUG_RETURN(imerge_trp); 03719 }
Here is the call graph for this function:
Here is the caller graph for this function:
| static TRP_GROUP_MIN_MAX * get_best_group_min_max | ( | PARAM * | param, | |
| SEL_TREE * | tree | |||
| ) | [static] |
Definition at line 8756 of file opt_range.cc.
References JOIN::all_fields, Item_sum::args, bitmap_is_set(), check_group_min_max_predicates(), check_quick_select(), Bitmap< 64 >::clear_all(), JOIN::conds, cost_group_min_max(), DBL_MAX, DBUG_ASSERT, DBUG_ENTER, DBUG_PRINT, DBUG_RETURN, base_list::elements, Item_field::eq(), FALSE, Item_field::field, st_key_part_info::field, st_table::field, Field::field_index, Item::FIELD_ITEM, st_table_share::fields, JOIN::fields_list, st_table::file, Item::find_item_in_field_list_processor(), st_key::flags, get_constant_key_infix(), get_field_keypart(), get_index_range_tree(), JOIN::group_list, HA_PRIMARY_KEY_IN_READ_INDEX, HA_SPATIAL, handler::ha_table_flags(), index(), Bitmap< 64 >::is_set(), st_order::item, Field::itMBR, Field::itRAW, st_table::key_info, st_key::key_part, st_key::key_parts, st_table_share::keys, JOIN::make_sum_func_list(), max, Item_sum::MAX_FUNC, MAX_KEY, MAX_KEY_LENGTH, RANGE_OPT_PARAM::mem_root, Item_sum::MIN_FUNC, st_order::next, NULL, st_table_share::primary_key, TRP_GROUP_MIN_MAX::quick_prefix_records, TABLE_READ_PLAN::read_cost, st_table::read_set, TABLE_READ_PLAN::records, List_iterator< T >::rewind(), st_table::s, JOIN::select_distinct, Bitmap< 64 >::set_bit(), SQLCOM_SELECT, st_key_part_info::store_length, Item_sum::sum_func(), JOIN::sum_funcs, RANGE_OPT_PARAM::table, JOIN::tables, RANGE_OPT_PARAM::thd, Bitmap< 64 >::to_ulonglong(), TRUE, Item::type(), st_table::used_keys, and Item::walk().
Referenced by SQL_SELECT::test_quick_select().
08757 { 08758 THD *thd= param->thd; 08759 JOIN *join= thd->lex->select_lex.join; 08760 TABLE *table= param->table; 08761 bool have_min= FALSE; /* TRUE if there is a MIN function. */ 08762 bool have_max= FALSE; /* TRUE if there is a MAX function. */ 08763 Item_field *min_max_arg_item= NULL; // The argument of all MIN/MAX functions 08764 KEY_PART_INFO *min_max_arg_part= NULL; /* The corresponding keypart. */ 08765 uint group_prefix_len= 0; /* Length (in bytes) of the key prefix. */ 08766 KEY *index_info= NULL; /* The index chosen for data access. */ 08767 uint index= 0; /* The id of the chosen index. */ 08768 uint group_key_parts= 0; // Number of index key parts in the group prefix. 08769 uint used_key_parts= 0; /* Number of index key parts used for access. */ 08770 byte key_infix[MAX_KEY_LENGTH]; /* Constants from equality predicates.*/ 08771 uint key_infix_len= 0; /* Length of key_infix. */ 08772 TRP_GROUP_MIN_MAX *read_plan= NULL; /* The eventually constructed TRP. */ 08773 uint key_part_nr; 08774 ORDER *tmp_group; 08775 Item *item; 08776 Item_field *item_field; 08777 DBUG_ENTER("get_best_group_min_max"); 08778 08779 /* Perform few 'cheap' tests whether this access method is applicable. */ 08780 if (!join || (thd->lex->sql_command != SQLCOM_SELECT)) 08781 DBUG_RETURN(NULL); /* This is not a select statement. */ 08782 if ((join->tables != 1) || /* The query must reference one table. */ 08783 ((!join->group_list) && /* Neither GROUP BY nor a DISTINCT query. */ 08784 (!join->select_distinct)) || 08785 (thd->lex->select_lex.olap == ROLLUP_TYPE)) /* Check (B3) for ROLLUP */ 08786 DBUG_RETURN(NULL); 08787 if (table->s->keys == 0) /* There are no indexes to use. */ 08788 DBUG_RETURN(NULL); 08789 08790 /* Analyze the query in more detail. */ 08791 List_iterator<Item> select_items_it(join->fields_list); 08792 08793 /* Check (SA1,SA4) and store the only MIN/MAX argument - the C attribute.*/ 08794 if (join->make_sum_func_list(join->all_fields, join->fields_list, 1)) 08795 DBUG_RETURN(NULL); 08796 if (join->sum_funcs[0]) 08797 { 08798 Item_sum *min_max_item; 08799 Item_sum **func_ptr= join->sum_funcs; 08800 while ((min_max_item= *(func_ptr++))) 08801 { 08802 if (min_max_item->sum_func() == Item_sum::MIN_FUNC) 08803 have_min= TRUE; 08804 else if (min_max_item->sum_func() == Item_sum::MAX_FUNC) 08805 have_max= TRUE; 08806 else 08807 DBUG_RETURN(NULL); 08808 08809 Item *expr= min_max_item->args[0]; /* The argument of MIN/MAX. */ 08810 if (expr->type() == Item::FIELD_ITEM) /* Is it an attribute? */ 08811 { 08812 if (! min_max_arg_item) 08813 min_max_arg_item= (Item_field*) expr; 08814 else if (! min_max_arg_item->eq(expr, 1)) 08815 DBUG_RETURN(NULL); 08816 } 08817 else 08818 DBUG_RETURN(NULL); 08819 } 08820 } 08821 08822 /* Check (SA5). */ 08823 if (join->select_distinct) 08824 { 08825 while ((item= select_items_it++)) 08826 { 08827 if (item->type() != Item::FIELD_ITEM) 08828 DBUG_RETURN(NULL); 08829 } 08830 } 08831 08832 /* Check (GA4) - that there are no expressions among the group attributes. */ 08833 for (tmp_group= join->group_list; tmp_group; tmp_group= tmp_group->next) 08834 { 08835 if ((*tmp_group->item)->type() != Item::FIELD_ITEM) 08836 DBUG_RETURN(NULL); 08837 } 08838 08839 /* 08840 Check that table has at least one compound index such that the conditions 08841 (GA1,GA2) are all TRUE. If there is more than one such index, select the 08842 first one. Here we set the variables: group_prefix_len and index_info. 08843 */ 08844 KEY *cur_index_info= table->key_info; 08845 KEY *cur_index_info_end= cur_index_info + table->s->keys; 08846 KEY_PART_INFO *cur_part= NULL; 08847 KEY_PART_INFO *end_part; /* Last part for loops. */ 08848 /* Last index part. */ 08849 KEY_PART_INFO *last_part= NULL; 08850 KEY_PART_INFO *first_non_group_part= NULL; 08851 KEY_PART_INFO *first_non_infix_part= NULL; 08852 uint key_infix_parts= 0; 08853 uint cur_group_key_parts= 0; 08854 uint cur_group_prefix_len= 0; 08855 /* Cost-related variables for the best index so far. */ 08856 double best_read_cost= DBL_MAX; 08857 ha_rows best_records= 0; 08858 SEL_ARG *best_index_tree= NULL; 08859 ha_rows best_quick_prefix_records= 0; 08860 uint best_param_idx= 0; 08861 double cur_read_cost= DBL_MAX; 08862 ha_rows cur_records; 08863 SEL_ARG *cur_index_tree= NULL; 08864 ha_rows cur_quick_prefix_records= 0; 08865 uint cur_param_idx=MAX_KEY; 08866 key_map cur_used_key_parts; 08867 uint pk= param->table->s->primary_key; 08868 08869 for (uint cur_index= 0 ; cur_index_info != cur_index_info_end ; 08870 cur_index_info++, cur_index++) 08871 { 08872 /* Check (B1) - if current index is covering. */ 08873 if (!table->used_keys.is_set(cur_index)) 08874 goto next_index; 08875 08876 /* 08877 If the current storage manager is such that it appends the primary key to 08878 each index, then the above condition is insufficient to check if the 08879 index is covering. In such cases it may happen that some fields are 08880 covered by the PK index, but not by the current index. Since we can't 08881 use the concatenation of both indexes for index lookup, such an index 08882 does not qualify as covering in our case. If this is the case, below 08883 we check that all query fields are indeed covered by 'cur_index'. 08884 */ 08885 if (pk < MAX_KEY && cur_index != pk && 08886 (table->file->ha_table_flags() & HA_PRIMARY_KEY_IN_READ_INDEX)) 08887 { 08888 /* For each table field */ 08889 for (uint i= 0; i < table->s->fields; i++) 08890 { 08891 Field *cur_field= table->field[i]; 08892 /* 08893 If the field is used in the current query ensure that it's 08894 part of 'cur_index' 08895 */ 08896 if (bitmap_is_set(table->read_set, cur_field->field_index) && 08897 !cur_field->part_of_key_not_clustered.is_set(cur_index)) 08898 goto next_index; // Field was not part of key 08899 } 08900 } 08901 08902 /* 08903 Check (GA1) for GROUP BY queries. 08904 */ 08905 if (join->group_list) 08906 { 08907 cur_part= cur_index_info->key_part; 08908 end_part= cur_part + cur_index_info->key_parts; 08909 /* Iterate in parallel over the GROUP list and the index parts. */ 08910 for (tmp_group= join->group_list; tmp_group && (cur_part != end_part); 08911 tmp_group= tmp_group->next, cur_part++) 08912 { 08913 /* 08914 TODO: 08915 tmp_group::item is an array of Item, is it OK to consider only the 08916 first Item? If so, then why? What is the array for? 08917 */ 08918 /* Above we already checked that all group items are fields. */ 08919 DBUG_ASSERT((*tmp_group->item)->type() == Item::FIELD_ITEM); 08920 Item_field *group_field= (Item_field *) (*tmp_group->item); 08921 if (group_field->field->eq(cur_part->field)) 08922 { 08923 cur_group_prefix_len+= cur_part->store_length; 08924 ++cur_group_key_parts; 08925 } 08926 else 08927 goto next_index; 08928 } 08929 } 08930 /* 08931 Check (GA2) if this is a DISTINCT query. 08932 If GA2, then Store a new ORDER object in group_fields_array at the 08933 position of the key part of item_field->field. Thus we get the ORDER 08934 objects for each field ordered as the corresponding key parts. 08935 Later group_fields_array of ORDER objects is used to convert the query 08936 to a GROUP query. 08937 */ 08938 else if (join->select_distinct) 08939 { 08940 select_items_it.rewind(); 08941 cur_used_key_parts.clear_all(); 08942 uint max_key_part= 0; 08943 while ((item= select_items_it++)) 08944 { 08945 item_field= (Item_field*) item; /* (SA5) already checked above. */ 08946 /* Find the order of the key part in the index. */ 08947 key_part_nr= get_field_keypart(cur_index_info, item_field->field); 08948 /* 08949 Check if this attribute was already present in the select list. 08950 If it was present, then its corresponding key part was alredy used. 08951 */ 08952 if (cur_used_key_parts.is_set(key_part_nr)) 08953 continue; 08954 if (key_part_nr < 1 || key_part_nr > join->fields_list.elements) 08955 goto next_index; 08956 cur_part= cur_index_info->key_part + key_part_nr - 1; 08957 cur_group_prefix_len+= cur_part->store_length; 08958 cur_used_key_parts.set_bit(key_part_nr); 08959 ++cur_group_key_parts; 08960 max_key_part= max(max_key_part,key_part_nr); 08961 } 08962 /* 08963 Check that used key parts forms a prefix of the index. 08964 To check this we compare bits in all_parts and cur_parts. 08965 all_parts have all bits set from 0 to (max_key_part-1). 08966 cur_parts have bits set for only used keyparts. 08967 */ 08968 ulonglong all_parts, cur_parts; 08969 all_parts= (1<<max_key_part) - 1; 08970 cur_parts= cur_used_key_parts.to_ulonglong() >> 1; 08971 if (all_parts != cur_parts) 08972 goto next_index; 08973 } 08974 else 08975 DBUG_ASSERT(FALSE); 08976 08977 /* Check (SA2). */ 08978 if (min_max_arg_item) 08979 { 08980 key_part_nr= get_field_keypart(cur_index_info, min_max_arg_item->field); 08981 if (key_part_nr <= cur_group_key_parts) 08982 goto next_index; 08983 min_max_arg_part= cur_index_info->key_part + key_part_nr - 1; 08984 } 08985 08986 /* 08987 Check (NGA1, NGA2) and extract a sequence of constants to be used as part 08988 of all search keys. 08989 */ 08990 08991 /* 08992 If there is MIN/MAX, each keypart between the last group part and the 08993 MIN/MAX part must participate in one equality with constants, and all 08994 keyparts after the MIN/MAX part must not be referenced in the query. 08995 08996 If there is no MIN/MAX, the keyparts after the last group part can be 08997 referenced only in equalities with constants, and the referenced keyparts 08998 must form a sequence without any gaps that starts immediately after the 08999 last group keypart. 09000 */ 09001 last_part= cur_index_info->key_part + cur_index_info->key_parts; 09002 first_non_group_part= (cur_group_key_parts < cur_index_info->key_parts) ? 09003 cur_index_info->key_part + cur_group_key_parts : 09004 NULL; 09005 first_non_infix_part= min_max_arg_part ? 09006 (min_max_arg_part < last_part) ? 09007 min_max_arg_part + 1 : 09008 NULL : 09009 NULL; 09010 if (first_non_group_part && 09011 (!min_max_arg_part || (min_max_arg_part - first_non_group_part > 0))) 09012 { 09013 if (tree) 09014 { 09015 uint dummy; 09016 SEL_ARG *index_range_tree= get_index_range_tree(cur_index, tree, param, 09017 &dummy); 09018 if (!get_constant_key_infix(cur_index_info, index_range_tree, 09019 first_non_group_part, min_max_arg_part, 09020 last_part, thd, key_infix, &key_infix_len, 09021 &first_non_infix_part)) 09022 goto next_index; 09023 } 09024 else if (min_max_arg_part && 09025 (min_max_arg_part - first_non_group_part > 0)) 09026 { 09027 /* 09028 There is a gap but no range tree, thus no predicates at all for the 09029 non-group keyparts. 09030 */ 09031 goto next_index; 09032 } 09033 else if (first_non_group_part && join->conds) 09034 { 09035 /* 09036 If there is no MIN/MAX function in the query, but some index 09037 key part is referenced in the WHERE clause, then this index 09038 cannot be used because the WHERE condition over the keypart's 09039 field cannot be 'pushed' to the index (because there is no 09040 range 'tree'), and the WHERE clause must be evaluated before 09041 GROUP BY/DISTINCT. 09042 */ 09043 /* 09044 Store the first and last keyparts that need to be analyzed 09045 into one array that can be passed as parameter. 09046 */ 09047 KEY_PART_INFO *key_part_range[2]; 09048 key_part_range[0]= first_non_group_part; 09049 key_part_range[1]= last_part; 09050 09051 /* Check if cur_part is referenced in the WHERE clause. */ 09052 if (join->conds->walk(&Item::find_item_in_field_list_processor, 0, 09053 (byte*) key_part_range)) 09054 goto next_index; 09055 } 09056 } 09057 09058 /* 09059 Test (WA1) partially - that no other keypart after the last infix part is 09060 referenced in the query. 09061 */ 09062 if (first_non_infix_part) 09063 { 09064 for (cur_part= first_non_infix_part; cur_part != last_part; cur_part++) 09065 { 09066 if (bitmap_is_set(table->read_set, cur_part->field->field_index)) 09067 goto next_index; 09068 } 09069 } 09070 09071 /* If we got to this point, cur_index_info passes the test. */ 09072 key_infix_parts= key_infix_len ? 09073 (first_non_infix_part - first_non_group_part) : 0; 09074 used_key_parts= cur_group_key_parts + key_infix_parts; 09075 09076 /* Compute the cost of using this index. */ 09077 if (tree) 09078 { 09079 /* Find the SEL_ARG sub-tree that corresponds to the chosen index. */ 09080 cur_index_tree= get_index_range_tree(cur_index, tree, param, 09081 &cur_param_idx); 09082 /* Check if this range tree can be used for prefix retrieval. */ 09083 cur_quick_prefix_records= check_quick_select(param, cur_param_idx, 09084 cur_index_tree, TRUE); 09085 } 09086 cost_group_min_max(table, cur_index_info, used_key_parts, 09087 cur_group_key_parts, tree, cur_index_tree, 09088 cur_quick_prefix_records, have_min, have_max, 09089 &cur_read_cost, &cur_records); 09090 /* 09091 If cur_read_cost is lower than best_read_cost use cur_index. 09092 Do not compare doubles directly because they may have different 09093 representations (64 vs. 80 bits). 09094 */ 09095 if (cur_read_cost < best_read_cost - (DBL_EPSILON * cur_read_cost)) 09096 { 09097 DBUG_ASSERT(tree != 0 || cur_param_idx == MAX_KEY); 09098 index_info= cur_index_info; 09099 index= cur_index; 09100 best_read_cost= cur_read_cost; 09101 best_records= cur_records; 09102 best_index_tree= cur_index_tree; 09103 best_quick_prefix_records= cur_quick_prefix_records; 09104 best_param_idx= cur_param_idx; 09105 group_key_parts= cur_group_key_parts; 09106 group_prefix_len= cur_group_prefix_len; 09107 } 09108 09109 next_index: 09110 cur_group_key_parts= 0; 09111 cur_group_prefix_len= 0; 09112 } 09113 if (!index_info) /* No usable index found. */ 09114 DBUG_RETURN(NULL); 09115 09116 /* Check (SA3) for the where clause. */ 09117 if (join->conds && min_max_arg_item && 09118 !check_group_min_max_predicates(join->conds, min_max_arg_item, 09119 (index_info->flags & HA_SPATIAL) ? 09120 Field::itMBR : Field::itRAW)) 09121 DBUG_RETURN(NULL); 09122 09123 /* The query passes all tests, so construct a new TRP object. */ 09124 read_plan= new (param->mem_root) 09125 TRP_GROUP_MIN_MAX(have_min, have_max, min_max_arg_part, 09126 group_prefix_len, used_key_parts, 09127 group_key_parts, index_info, index, 09128 key_infix_len, 09129 (key_infix_len > 0) ? key_infix : NULL, 09130 tree, best_index_tree, best_param_idx, 09131 best_quick_prefix_records); 09132 if (read_plan) 09133 { 09134 if (tree && read_plan->quick_prefix_records == 0) 09135 DBUG_RETURN(NULL); 09136 09137 read_plan->read_cost= best_read_cost; 09138 read_plan->records= best_records; 09139 09140 DBUG_PRINT("info", 09141 ("Returning group min/max plan: cost: %g, records: %lu", 09142 read_plan->read_cost, (ulong) read_plan->records)); 09143 } 09144 09145 DBUG_RETURN(read_plan); 09146 }
Here is the call graph for this function:
Here is the caller graph for this function:
| static TRP_ROR_INTERSECT * get_best_ror_intersect | ( | const PARAM * | param, | |
| SEL_TREE * | tree, | |||
| double | read_time, | |||
| bool * | are_all_covering | |||
| ) | [static] |
Definition at line 4287 of file opt_range.cc.
References alloc_root(), cmp_ror_scan_info(), DBL_MAX, DBUG_ENTER, DBUG_EXECUTE, DBUG_PRINT, DBUG_RETURN, double2rows, FALSE, st_table::file, ROR_INTERSECT_INFO::index_scan_costs, ROR_INTERSECT_INFO::is_covering, Bitmap< 64 >::is_set(), SEL_TREE::keys, keys, RANGE_OPT_PARAM::keys, make_ror_scan(), MAX_KEY, RANGE_OPT_PARAM::mem_root, memcpy, SEL_TREE::n_ror_scans, NULL, ROR_INTERSECT_INFO::out_rows, st_table_share::primary_key, handler::primary_key_is_clustered(), print_ror_scans_arr(), qsort(), qsort_cmp, st_table::quick_condition_rows, RANGE_OPT_PARAM::real_keynr, ha_statistics::records, ror_intersect_add(), ror_intersect_cpy(), ror_intersect_init(), SEL_TREE::ror_scans, SEL_TREE::ror_scans_end, SEL_TREE::ror_scans_map, st_table::s, set_if_smaller, handler::stats, RANGE_OPT_PARAM::table, ROR_INTERSECT_INFO::total_cost, and TRUE.
Referenced by get_best_disjunct_quick(), and SQL_SELECT::test_quick_select().
04290 { 04291 uint idx; 04292 double min_cost= DBL_MAX; 04293 DBUG_ENTER("get_best_ror_intersect"); 04294 04295 if ((tree->n_ror_scans < 2) || !param->table->file->stats.records) 04296 DBUG_RETURN(NULL); 04297 04298 /* 04299 Step1: Collect ROR-able SEL_ARGs and create ROR_SCAN_INFO for each of 04300 them. Also find and save clustered PK scan if there is one. 04301 */ 04302 ROR_SCAN_INFO **cur_ror_scan; 04303 ROR_SCAN_INFO *cpk_scan= NULL; 04304 uint cpk_no; 04305 bool cpk_scan_used= FALSE; 04306 04307 if (!(tree->ror_scans= (ROR_SCAN_INFO**)alloc_root(param->mem_root, 04308 sizeof(ROR_SCAN_INFO*)* 04309 param->keys))) 04310 return NULL; 04311 cpk_no= ((param->table->file->primary_key_is_clustered()) ? 04312 param->table->s->primary_key : MAX_KEY); 04313 04314 for (idx= 0, cur_ror_scan= tree->ror_scans; idx < param->keys; idx++) 04315 { 04316 ROR_SCAN_INFO *scan; 04317 if (!tree->ror_scans_map.is_set(idx)) 04318 continue; 04319 if (!(scan= make_ror_scan(param, idx, tree->keys[idx]))) 04320 return NULL; 04321 if (param->real_keynr[idx] == cpk_no) 04322 { 04323 cpk_scan= scan; 04324 tree->n_ror_scans--; 04325 } 04326 else 04327 *(cur_ror_scan++)= scan; 04328 } 04329 04330 tree->ror_scans_end= cur_ror_scan; 04331 DBUG_EXECUTE("info",print_ror_scans_arr(param->table, "original", 04332 tree->ror_scans, 04333 tree->ror_scans_end);); 04334 /* 04335 Ok, [ror_scans, ror_scans_end) is array of ptrs to initialized 04336 ROR_SCAN_INFO's. 04337 Step 2: Get best ROR-intersection using an approximate algorithm. 04338 */ 04339 qsort(tree->ror_scans, tree->n_ror_scans, sizeof(ROR_SCAN_INFO*), 04340 (qsort_cmp)cmp_ror_scan_info); 04341 DBUG_EXECUTE("info",print_ror_scans_arr(param->table, "ordered", 04342 tree->ror_scans, 04343 tree->ror_scans_end);); 04344 04345 ROR_SCAN_INFO **intersect_scans; /* ROR scans used in index intersection */ 04346 ROR_SCAN_INFO **intersect_scans_end; 04347 if (!(intersect_scans= (ROR_SCAN_INFO**)alloc_root(param->mem_root, 04348 sizeof(ROR_SCAN_INFO*)* 04349 tree->n_ror_scans))) 04350 return NULL; 04351 intersect_scans_end= intersect_scans; 04352 04353 /* Create and incrementally update ROR intersection. */ 04354 ROR_INTERSECT_INFO *intersect, *intersect_best; 04355 if (!(intersect= ror_intersect_init(param)) || 04356 !(intersect_best= ror_intersect_init(param))) 04357 return NULL; 04358 04359 /* [intersect_scans,intersect_scans_best) will hold the best intersection */ 04360 ROR_SCAN_INFO **intersect_scans_best; 04361 cur_ror_scan= tree->ror_scans; 04362 intersect_scans_best= intersect_scans; 04363 while (cur_ror_scan != tree->ror_scans_end && !intersect->is_covering) 04364 { 04365 /* S= S + first(R); R= R - first(R); */ 04366 if (!ror_intersect_add(intersect, *cur_ror_scan, FALSE)) 04367 { 04368 cur_ror_scan++; 04369 continue; 04370 } 04371 04372 *(intersect_scans_end++)= *(cur_ror_scan++); 04373 04374 if (intersect->total_cost < min_cost) 04375 { 04376 /* Local minimum found, save it */ 04377 ror_intersect_cpy(intersect_best, intersect); 04378 intersect_scans_best= intersect_scans_end; 04379 min_cost = intersect->total_cost; 04380 } 04381 } 04382 04383 if (intersect_scans_best == intersect_scans) 04384 { 04385 DBUG_PRINT("info", ("None of scans increase selectivity")); 04386 DBUG_RETURN(NULL); 04387 } 04388 04389 DBUG_EXECUTE("info",print_ror_scans_arr(param->table, 04390 "best ROR-intersection", 04391 intersect_scans, 04392 intersect_scans_best);); 04393 04394 *are_all_covering= intersect->is_covering; 04395 uint best_num= intersect_scans_best - intersect_scans; 04396 ror_intersect_cpy(intersect, intersect_best); 04397 04398 /* 04399 Ok, found the best ROR-intersection of non-CPK key scans. 04400 Check if we should add a CPK scan. If the obtained ROR-intersection is 04401 covering, it doesn't make sense to add CPK scan. 04402 */ 04403 if (cpk_scan && !intersect->is_covering) 04404 { 04405 if (ror_intersect_add(intersect, cpk_scan, TRUE) && 04406 (intersect->total_cost < min_cost)) 04407 { 04408 cpk_scan_used= TRUE; 04409 intersect_best= intersect; //just set pointer here 04410 } 04411 } 04412 04413 /* Ok, return ROR-intersect plan if we have found one */ 04414 TRP_ROR_INTERSECT *trp= NULL; 04415 if (min_cost < read_time && (cpk_scan_used || best_num > 1)) 04416 { 04417 if (!(trp= new (param->mem_root) TRP_ROR_INTERSECT)) 04418 DBUG_RETURN(trp); 04419 if (!(trp->first_scan= 04420 (ROR_SCAN_INFO**)alloc_root(param->mem_root, 04421 sizeof(ROR_SCAN_INFO*)*best_num))) 04422 DBUG_RETURN(NULL); 04423 memcpy(trp->first_scan, intersect_scans, best_num*sizeof(ROR_SCAN_INFO*)); 04424 trp->last_scan= trp->first_scan + best_num; 04425 trp->is_covering= intersect_best->is_covering; 04426 trp->read_cost= intersect_best->total_cost; 04427 /* Prevent divisons by zero */ 04428 ha_rows best_rows = double2rows(intersect_best->out_rows); 04429 if (!best_rows) 04430 best_rows= 1; 04431 set_if_smaller(param->table->quick_condition_rows, best_rows); 04432 trp->records= best_rows; 04433 trp->index_scan_costs= intersect_best->index_scan_costs; 04434 trp->cpk_scan= cpk_scan_used? cpk_scan: NULL; 04435 DBUG_PRINT("info", ("Returning non-covering ROR-intersect plan:" 04436 "cost %g, records %lu", 04437 trp->read_cost, (ulong) trp->records)); 04438 } 04439 DBUG_RETURN(trp); 04440 }
Here is the call graph for this function:
Here is the caller graph for this function:
| static bool get_constant_key_infix | ( | KEY * | index_info, | |
| SEL_ARG * | index_range_tree, | |||
| KEY_PART_INFO * | first_non_group_part, | |||
| KEY_PART_INFO * | min_max_arg_part, | |||
| KEY_PART_INFO * | last_part, | |||
| THD * | thd, | |||
| byte * | key_infix, | |||
| uint * | key_infix_len, | |||
| KEY_PART_INFO ** | first_non_infix_part | |||
| ) | [static] |
Definition at line 9316 of file opt_range.cc.
References Field::eq(), FALSE, st_key_part_info::field, SEL_ARG::field, SEL_ARG::max_flag, SEL_ARG::max_value, SEL_ARG::maybe_null, memcmp(), memcpy, SEL_ARG::min_flag, SEL_ARG::min_value, NEAR_MAX, NEAR_MIN, SEL_ARG::next, SEL_ARG::next_key_part, NO_MAX_RANGE, NO_MIN_RANGE, SEL_ARG::prev, st_key_part_info::store_length, and TRUE.
Referenced by get_best_group_min_max().
09322 { 09323 SEL_ARG *cur_range; 09324 KEY_PART_INFO *cur_part; 09325 /* End part for the first loop below. */ 09326 KEY_PART_INFO *end_part= min_max_arg_part ? min_max_arg_part : last_part; 09327 09328 *key_infix_len= 0; 09329 byte *key_ptr= key_infix; 09330 for (cur_part= first_non_group_part; cur_part != end_part; cur_part++) 09331 { 09332 /* 09333 Find the range tree for the current keypart. We assume that 09334 index_range_tree points to the leftmost keypart in the index. 09335 */ 09336 for (cur_range= index_range_tree; cur_range; 09337 cur_range= cur_range->next_key_part) 09338 { 09339 if (cur_range->field->eq(cur_part->field)) 09340 break; 09341 } 09342 if (!cur_range) 09343 { 09344 if (min_max_arg_part) 09345 return FALSE; /* The current keypart has no range predicates at all. */ 09346 else 09347 { 09348 *first_non_infix_part= cur_part; 09349 return TRUE; 09350 } 09351 } 09352 09353 /* Check that the current range tree is a single point interval. */ 09354 if (cur_range->prev || cur_range->next) 09355 return FALSE; /* This is not the only range predicate for the field. */ 09356 if ((cur_range->min_flag & NO_MIN_RANGE) || 09357 (cur_range->max_flag & NO_MAX_RANGE) || 09358 (cur_range->min_flag & NEAR_MIN) || (cur_range->max_flag & NEAR_MAX)) 09359 return FALSE; 09360 09361 uint field_length= cur_part->store_length; 09362 if ((cur_range->maybe_null && 09363 cur_range->min_value[0] && cur_range->max_value[0]) || 09364 !memcmp(cur_range->min_value, cur_range->max_value, field_length)) 09365 { 09366 /* cur_range specifies 'IS NULL' or an equality condition. */ 09367 memcpy(key_ptr, cur_range->min_value, field_length); 09368 key_ptr+= field_length; 09369 *key_infix_len+= field_length; 09370 } 09371 else 09372 return FALSE; 09373 } 09374 09375 if (!min_max_arg_part && (cur_part == last_part)) 09376 *first_non_infix_part= last_part; 09377 09378 return TRUE; 09379 }
Here is the call graph for this function:
Here is the caller graph for this function:
Definition at line 9400 of file opt_range.cc.
References Field::eq(), st_key_part_info::field, and index().
Referenced by get_best_group_min_max().
09401 { 09402 KEY_PART_INFO *part, *end; 09403 09404 for (part= index->key_part, end= part + index->key_parts; part < end; part++) 09405 { 09406 if (field->eq(part->field)) 09407 return part - index->key_part + 1; 09408 } 09409 return 0; 09410 }
Here is the call graph for this function:
Here is the caller graph for this function:
| static SEL_TREE* get_func_mm_tree | ( | RANGE_OPT_PARAM * | param, | |
| Item_func * | cond_func, | |||
| Field * | field, | |||
| Item * | value, | |||
| Item_result | cmp_type, | |||
| bool | inv | |||
| ) | [static] |
Definition at line 4865 of file opt_range.cc.
References Item_func::arguments(), Item_func::BETWEEN, DBUG_ENTER, DBUG_RETURN, Item_func::EQ_FUNC, func, Item_func::functype(), Item_func::GE_FUNC, get_mm_parts(), get_ne_mm_tree(), Item_func::GT_FUNC, SEL_TREE::IMPOSSIBLE, Item_func::IN_FUNC, SEL_TREE::keys, RANGE_OPT_PARAM::keys, SEL_ARG::last(), Item_func::LE_FUNC, Item_func::LT_FUNC, RANGE_OPT_PARAM::mem_root, SEL_ARG::min_flag, SEL_ARG::min_value, Item_func::NE_FUNC, NEAR_MIN, NOT_IN_IGNORE_THRESHOLD, NULL, RANGE_OPT_PARAM::old_root, ROW_RESULT, RANGE_OPT_PARAM::thd, tree_and(), tree_or(), SEL_TREE::type, and value.
Referenced by get_mm_tree().
04868 { 04869 SEL_TREE *tree= 0; 04870 DBUG_ENTER("get_func_mm_tree"); 04871 04872 switch (cond_func->functype()) { 04873 04874 case Item_func::NE_FUNC: 04875 tree= get_ne_mm_tree(param, cond_func, field, value, value, cmp_type); 04876 break; 04877 04878 case Item_func::BETWEEN: 04879 if (inv) 04880 { 04881 tree= get_ne_mm_tree(param, cond_func, field, cond_func->arguments()[1], 04882 cond_func->arguments()[2], cmp_type); 04883 } 04884 else 04885 { 04886 tree= get_mm_parts(param, cond_func, field, Item_func::GE_FUNC, 04887 cond_func->arguments()[1],cmp_type); 04888 if (tree) 04889 { 04890 tree= tree_and(param, tree, get_mm_parts(param, cond_func, field, 04891 Item_func::LE_FUNC, 04892 cond_func->arguments()[2], 04893 cmp_type)); 04894 } 04895 } 04896 break; 04897 04898 case Item_func::IN_FUNC: 04899 { 04900 Item_func_in *func=(Item_func_in*) cond_func; 04901 04902 if (inv) 04903 { 04904 if (func->array && func->cmp_type != ROW_RESULT) 04905 { 04906 /* 04907 We get here for conditions in form "t.key NOT IN (c1, c2, ...)" 04908 (where c{i} are constants). 04909 Our goal is to produce a SEL_ARG graph that represents intervals: 04910 04911 ($MIN<t.key<c1) OR (c1<t.key<c2) OR (c2<t.key<c3) OR ... (*) 04912 04913 where $MIN is either "-inf" or NULL. 04914 04915 The most straightforward way to handle NOT IN would be to convert 04916 it to "(t.key != c1) AND (t.key != c2) AND ..." and let the range 04917 optimizer to build SEL_ARG graph from that. However that will cause 04918 the range optimizer to use O(N^2) memory (it's a bug, not filed), 04919 and people do use big NOT IN lists (see BUG#15872). Also, for big 04920 NOT IN lists constructing/using graph (*) does not make the query 04921 faster. 04922 04923 So, we will handle NOT IN manually in the following way: 04924 * if the number of entries in the NOT IN list is less then 04925 NOT_IN_IGNORE_THRESHOLD, we will construct SEL_ARG graph (*) 04926 manually. 04927 * Otherwise, we will construct a smaller graph: for 04928 "t.key NOT IN (c1,...cN)" we construct a graph representing 04929 ($MIN < t.key) OR (cN < t.key) // here sequence of c_i is 04930 // ordered. 04931 04932 A note about partially-covering indexes: for those (e.g. for 04933 "a CHAR(10), KEY(a(5))") the handling is correct (albeit not very 04934 efficient): 04935 Instead of "t.key < c1" we get "t.key <= prefix-val(c1)". 04936 Combining the intervals in (*) together, we get: 04937 (-inf<=t.key<=c1) OR (c1<=t.key<=c2) OR (c2<=t.key<=c3) OR ... 04938 i.e. actually we get intervals combined into one interval: 04939 (-inf<=t.key<=+inf). This doesn't make much sense but it doesn't 04940 cause any problems. 04941 */ 04942 MEM_ROOT *tmp_root= param->mem_root; 04943 param->thd->mem_root= param->old_root; 04944 /* 04945 Create one Item_type constant object. We'll need it as 04946 get_mm_parts only accepts constant values wrapped in Item_Type 04947 objects. 04948 We create the Item on param->mem_root which points to 04949 per-statement mem_root (while thd->mem_root is currently pointing 04950 to mem_root local to range optimizer). 04951 */ 04952 Item *value_item= func->array->create_item(); 04953 param->thd->mem_root= tmp_root; 04954 04955 if (!value_item) 04956 break; 04957 04958 /* Get a SEL_TREE for "(-inf|NULL) < X < c_0" interval. */ 04959 uint i=0; 04960 do 04961 { 04962 func->array->value_to_item(i, value_item); 04963 tree= get_mm_parts(param, cond_func, field, Item_func::LT_FUNC, 04964 value_item, cmp_type); 04965 if (!tree) 04966 break; 04967 i++; 04968 } while (i < func->array->count && tree->type == SEL_TREE::IMPOSSIBLE); 04969 04970 if (!tree || tree->type == SEL_TREE::IMPOSSIBLE) 04971 { 04972 /* We get here in cases like "t.unsigned NOT IN (-1,-2,-3) */ 04973 tree= NULL; 04974 break; 04975 } 04976 #define NOT_IN_IGNORE_THRESHOLD 1000 04977 SEL_TREE *tree2; 04978 if (func->array->count < NOT_IN_IGNORE_THRESHOLD) 04979 { 04980 for (; i < func->array->count; i++) 04981 { 04982 if (func->array->compare_elems(i, i-1)) 04983 { 04984 /* Get a SEL_TREE for "-inf < X < c_i" interval */ 04985 func->array->value_to_item(i, value_item); 04986 tree2= get_mm_parts(param, cond_func, field, Item_func::LT_FUNC, 04987 value_item, cmp_type); 04988 if (!tree2) 04989 { 04990 tree= NULL; 04991 break; 04992 } 04993 04994 /* Change all intervals to be "c_{i-1} < X < c_i" */ 04995 for (uint idx= 0; idx < param->keys; idx++) 04996 { 04997 SEL_ARG *new_interval, *last_val; 04998 if (((new_interval= tree2->keys[idx])) && 04999 ((last_val= tree->keys[idx]->last()))) 05000 { 05001 new_interval->min_value= last_val->max_value; 05002 new_interval->min_flag= NEAR_MIN; 05003 } 05004 } 05005 /* 05006 The following doesn't try to allocate memory so no need to 05007 check for NULL. 05008 */ 05009 tree= tree_or(param, tree, tree2); 05010 } 05011 } 05012 } 05013 else 05014 func->array->value_to_item(func->array->count - 1, value_item); 05015 05016 if (tree && tree->type != SEL_TREE::IMPOSSIBLE) 05017 { 05018 /* 05019 Get the SEL_TREE for the last "c_last < X < +inf" interval 05020 (value_item cotains c_last already) 05021 */ 05022 tree2= get_mm_parts(param, cond_func, field, Item_func::GT_FUNC, 05023 value_item, cmp_type); 05024 tree= tree_or(param, tree, tree2); 05025 } 05026 } 05027 else 05028 { 05029 tree= get_ne_mm_tree(param, cond_func, field, 05030 func->arguments()[1], func->arguments()[1], 05031 cmp_type); 05032 if (tree) 05033 { 05034 Item **arg, **end; 05035 for (arg= func->arguments()+2, end= arg+func->argument_count()-2; 05036 arg < end ; arg++) 05037 { 05038 tree= tree_and(param, tree, get_ne_mm_tree(param, cond_func, field, 05039 *arg, *arg, cmp_type)); 05040 } 05041 } 05042 } 05043 } 05044 else 05045 { 05046 tree= get_mm_parts(param, cond_func, field, Item_func::EQ_FUNC, 05047 func->arguments()[1], cmp_type); 05048 if (tree) 05049 { 05050 Item **arg, **end; 05051 for (arg= func->arguments()+2, end= arg+func->argument_count()-2; 05052 arg < end ; arg++) 05053 { 05054 tree= tree_or(param, tree, get_mm_parts(param, cond_func, field, 05055 Item_func::EQ_FUNC, 05056 *arg, cmp_type)); 05057 } 05058 } 05059 } 05060 break; 05061 } 05062 default: 05063 { 05064 /* 05065 Here the function for the following predicates are processed: 05066 <, <=, =, >=, >, LIKE, IS NULL, IS NOT NULL. 05067 If the predicate is of the form (value op field) it is handled 05068 as the equivalent predicate (field rev_op value), e.g. 05069 2 <= a is handled as a >= 2. 05070 */ 05071 Item_func::Functype func_type= 05072 (value != cond_func->arguments()[0]) ? cond_func->functype() : 05073 ((Item_bool_func2*) cond_func)->rev_functype(); 05074 tree= get_mm_parts(param, cond_func, field, func_type, value, cmp_type); 05075 } 05076 } 05077 05078 DBUG_RETURN(tree); 05079 05080 }
Here is the call graph for this function:
Here is the caller graph for this function:
Definition at line 1649 of file opt_range.cc.
References st_order::asc, Item::FIELD_ITEM, st_table::file, HA_READ_ORDER, handler::index_flags(), Bitmap< 64 >::is_set(), st_table::key_info, st_key::key_length, st_key::key_part, keyinfo, st_table_share::keys, st_table::keys_in_use_for_query, MAX_KEY, MAX_KEY_LENGTH, st_order::next, order, handler::read_time(), st_table::s, and handler::scan_time().
Referenced by mysql_delete().
01650 { 01651 uint idx; 01652 uint match_key= MAX_KEY, match_key_len= MAX_KEY_LENGTH + 1; 01653 ORDER *ord; 01654 01655 for (ord= order; ord; ord= ord->next) 01656 if (!ord->asc) 01657 return MAX_KEY; 01658 01659 for (idx= 0; idx < table->s->keys; idx++) 01660 { 01661 if (!(table->keys_in_use_for_query.is_set(idx))) 01662 continue; 01663 KEY_PART_INFO *keyinfo= table->key_info[idx].key_part; 01664 uint partno= 0; 01665 01666 /* 01667 The below check is sufficient considering we now have either BTREE 01668 indexes (records are returned in order for any index prefix) or HASH 01669 indexes (records are not returned in order for any index prefix). 01670 */ 01671 if (!(table->file->index_flags(idx, 0, 1) & HA_READ_ORDER)) 01672 continue; 01673 for (ord= order; ord; ord= ord->next, partno++) 01674 { 01675 Item *item= order->item[0]; 01676 if (!(item->type() == Item::FIELD_ITEM && 01677 ((Item_field*)item)->field->eq(keyinfo[partno].field))) 01678 break; 01679 } 01680 01681 if (!ord && table->key_info[idx].key_length < match_key_len) 01682 { 01683 /* 01684 Ok, the ordering is compatible and this key is shorter then 01685 previous match (we want shorter keys as we'll have to read fewer 01686 index pages for the same number of records) 01687 */ 01688 match_key= idx; 01689 match_key_len= table->key_info[idx].key_length; 01690 } 01691 } 01692 01693 if (match_key != MAX_KEY) 01694 { 01695 /* 01696 Found an index that allows records to be retrieved in the requested 01697 order. Now we'll check if using the index is cheaper then doing a table 01698 scan. 01699 */ 01700 double full_scan_time= table->file->scan_time(); 01701 double index_scan_time= table->file->read_time(match_key, 1, limit); 01702 if (index_scan_time > full_scan_time) 01703 match_key= MAX_KEY; 01704 } 01705 return match_key; 01706 }
Here is the call graph for this function:
Here is the caller graph for this function:
| static int get_index_merge_params | ( | PARAM * | param, | |
| key_map & | needed_reg, | |||
| SEL_IMERGE * | imerge, | |||
| double * | read_time, | |||
| ha_rows * | imerge_rows | |||
| ) | [static] |
Definition at line 3745 of file opt_range.cc.
References ha_statistics::block_size, st_table::file, st_table::key_info, st_key::key_length, handler::ref_length, handler::stats, and RANGE_OPT_PARAM::table.
Referenced by get_key_scans_params(), make_ror_scan(), and SQL_SELECT::test_quick_select().
03747 { 03748 double read_time; 03749 uint keys_per_block= (param->table->file->stats.block_size/2/ 03750 (param->table->key_info[keynr].key_length+ 03751 param->table->file->ref_length) + 1); 03752 read_time=((double) (records+keys_per_block-1)/ 03753 (double) keys_per_block); 03754 return read_time; 03755 }
Here is the caller graph for this function:
| SEL_ARG * get_index_range_tree | ( | uint | index, | |
| SEL_TREE * | range_tree, | |||
| PARAM * | param, | |||
| uint * | param_idx | |||
| ) | [inline, static] |
Definition at line 9436 of file opt_range.cc.
References SEL_TREE::keys, keys, and RANGE_OPT_PARAM::real_keynr.
Referenced by get_best_group_min_max().
09438 { 09439 uint idx= 0; /* Index nr in param->key_parts */ 09440 while (idx < param->keys) 09441 { 09442 if (index == param->real_keynr[idx]) 09443 break; 09444 idx++; 09445 } 09446 *param_idx= idx; 09447 return(range_tree->keys[idx]); 09448 }
Here is the caller graph for this function:
| static TRP_RANGE * get_key_scans_params | ( | PARAM * | param, | |
| SEL_TREE * | tree, | |||
| bool | index_read_must_be_used, | |||
| bool | update_tbl_stats, | |||
| double | read_time | |||
| ) | [static] |
Definition at line 4606 of file opt_range.cc.
References bool, check_quick_select(), Bitmap< 64 >::clear_all(), DBUG_ENTER, DBUG_EXECUTE, DBUG_PRINT, DBUG_RETURN, st_table::file, get_index_only_read_time(), HA_KEYREAD_ONLY, HA_POS_ERROR, handler::index_flags(), TABLE_READ_PLAN::is_ror, PARAM::is_ror_scan, Bitmap< 64 >::is_set(), key, st_table::key_info, RANGE_OPT_PARAM::keys, SEL_TREE::keys, SEL_TREE::keys_map, LINT_INIT, PARAM::max_key_part, SEL_ARG::MAYBE_KEY, RANGE_OPT_PARAM::mem_root, SEL_TREE::n_ror_scans, st_key::name, PARAM::needed_reg, NULL, st_table_share::primary_key, handler::primary_key_is_clustered(), print_sel_tree(), PARAM::range_count, TABLE_READ_PLAN::read_cost, handler::read_time(), RANGE_OPT_PARAM::real_keynr, TABLE_READ_PLAN::records, SEL_TREE::ror_scans_map, st_table::s, Bitmap< 64 >::set_bit(), RANGE_OPT_PARAM::table, TIME_FOR_COMPARE, TRUE, and st_table::used_keys.
Referenced by get_best_disjunct_quick(), and SQL_SELECT::test_quick_select().
04610 { 04611 int idx; 04612 SEL_ARG **key,**end, **key_to_read= NULL; 04613 ha_rows best_records; 04614 TRP_RANGE* read_plan= NULL; 04615 bool pk_is_clustered= param->table->file->primary_key_is_clustered(); 04616 DBUG_ENTER("get_key_scans_params"); 04617 LINT_INIT(best_records); /* protected by key_to_read */ 04618 /* 04619 Note that there may be trees that have type SEL_TREE::KEY but contain no 04620 key reads at all, e.g. tree for expression "key1 is not null" where key1 04621 is defined as "not null". 04622 */ 04623 DBUG_EXECUTE("info", print_sel_tree(param, tree, &tree->keys_map, 04624 "tree scans");); 04625 tree->ror_scans_map.clear_all(); 04626 tree->n_ror_scans= 0; 04627 for (idx= 0,key=tree->keys, end=key+param->keys; 04628 key != end ; 04629 key++,idx++) 04630 { 04631 ha_rows found_records; 04632 double found_read_time; 04633 if (*key) 04634 { 04635 uint keynr= param->real_keynr[idx]; 04636 if ((*key)->type == SEL_ARG::MAYBE_KEY || 04637 (*key)->maybe_flag) 04638 param->needed_reg->set_bit(keynr); 04639 04640 bool read_index_only= index_read_must_be_used ? TRUE : 04641 (bool) param->table->used_keys.is_set(keynr); 04642 04643 found_records= check_quick_select(param, idx, *key, update_tbl_stats); 04644 if (param->is_ror_scan) 04645 { 04646 tree->n_ror_scans++; 04647 tree->ror_scans_map.set_bit(idx); 04648 } 04649 double cpu_cost= (double) found_records / TIME_FOR_COMPARE; 04650 if (found_records != HA_POS_ERROR && found_records > 2 && 04651 read_index_only && 04652 (param->table->file->index_flags(keynr, param->max_key_part,1) & 04653 HA_KEYREAD_ONLY) && 04654 !(pk_is_clustered && keynr == param->table->s->primary_key)) 04655 { 04656 /* 04657 We can resolve this by only reading through this key. 04658 0.01 is added to avoid races between range and 'index' scan. 04659 */ 04660 found_read_time= get_index_only_read_time(param,found_records,keynr) + 04661 cpu_cost + 0.01; 04662 } 04663 else 04664 { 04665 /* 04666 cost(read_through_index) = cost(disk_io) + cost(row_in_range_checks) 04667 The row_in_range check is in QUICK_RANGE_SELECT::cmp_next function. 04668 */ 04669 found_read_time= param->table->file->read_time(keynr, 04670 param->range_count, 04671 found_records) + 04672 cpu_cost + 0.01; 04673 } 04674 DBUG_PRINT("info",("key %s: found_read_time: %g (cur. read_time: %g)", 04675 param->table->key_info[keynr].name, found_read_time, 04676 read_time)); 04677 04678 if (read_time > found_read_time && found_records != HA_POS_ERROR 04679 /*|| read_time == DBL_MAX*/ ) 04680 { 04681 read_time= found_read_time; 04682 best_records= found_records; 04683 key_to_read= key; 04684 } 04685 04686 } 04687 } 04688 04689 DBUG_EXECUTE("info", print_sel_tree(param, tree, &tree->ror_scans_map, 04690 "ROR scans");); 04691 if (key_to_read) 04692 { 04693 idx= key_to_read - tree->keys; 04694 if ((read_plan= new (param->mem_root) TRP_RANGE(*key_to_read, idx))) 04695 { 04696 read_plan->records= best_records; 04697 read_plan->is_ror= tree->ror_scans_map.is_set(idx); 04698 read_plan->read_cost= read_time; 04699 DBUG_PRINT("info", 04700 ("Returning range plan for key %s, cost %g, records %lu", 04701 param->table->key_info[param->real_keynr[idx]].name, 04702 read_plan->read_cost, (ulong) read_plan->records)); 04703 } 04704 } 04705 else 04706 DBUG_PRINT("info", ("No 'range' table read plan found")); 04707 04708 DBUG_RETURN(read_plan); 04709 }
Here is the call graph for this function:
Here is the caller graph for this function:
| static SEL_ARG * get_mm_leaf | ( | RANGE_OPT_PARAM * | param, | |
| COND * | cond_func, | |||
| Field * | field, | |||
| KEY_PART * | key_part, | |||
| Item_func::Functype | type, | |||
| Item * | value | |||
| ) | [static] |
Definition at line 5316 of file opt_range.cc.
References alloc_root(), Field::charset(), Field::cmp_type(), Item::compare_collation(), RANGE_OPT_PARAM::cond, DBUG_ENTER, DBUG_RETURN, Item_func::EQ_FUNC, Item_func::EQUAL_FUNC, field_is_equal_to_item(), FIELD_TYPE_DATE, FIELD_TYPE_DATETIME, Item_func::GE_FUNC, GEOM_FLAG, Field::get_key_image(), Item_func::GT_FUNC, HA_KEY_BLOB_LENGTH, HA_READ_MBR_CONTAIN, HA_READ_MBR_DISJOINT, HA_READ_MBR_EQUAL, HA_READ_MBR_INTERSECT, HA_READ_MBR_WITHIN, st_key_part::image_type, SEL_ARG::IMPOSSIBLE, st_table::in_use, int2store, INT_RESULT, is_null_string, Field::is_real_null(), Item_func::ISNOTNULL_FUNC, Item_func::ISNULL_FUNC, Field::itRAW, st_key_part::key, Item_func::LE_FUNC, String::length(), st_key_part::length, Item_func::LIKE_FUNC, Item_func::LT_FUNC, MAX_FIELD_WIDTH, SEL_ARG::max_flag, st_table::maybe_null, RANGE_OPT_PARAM::mem_root, SEL_ARG::min_flag, SEL_ARG::min_value, MODE_INVALID_DATES, MY_CS_BINSORT, my_like_range, NEAR_MAX, NEAR_MIN, NO_MAX_RANGE, NO_MIN_RANGE, null_element, offset, RANGE_OPT_PARAM::old_root, Field::optimize_range(), Field::pack_length(), st_key_part::part, String::ptr(), RANGE_OPT_PARAM::real_keynr, Field::real_maybe_null(), Field::result_type(), Item_func::SP_CONTAINS_FUNC, Item_func::SP_CROSSES_FUNC, Item_func::SP_DISJOINT_FUNC, Item_func::SP_EQUALS_FUNC, Item_func::SP_INTERSECTS_FUNC, Item_func::SP_OVERLAPS_FUNC, Item_func::SP_TOUCHES_FUNC, Item_func::SP_WITHIN_FUNC, charset_info_st::state, st_key_part::store_length, Item::STRING_ITEM, STRING_RESULT, Field::table, RANGE_OPT_PARAM::thd, TRUE, SEL_ARG::type, Field::type(), unlikely, RANGE_OPT_PARAM::using_real_indexes, value, wild_many, and wild_one.
Referenced by get_mm_parts().
05318 { 05319 uint maybe_null=(uint) field->real_maybe_null(); 05320 bool optimize_range; 05321 SEL_ARG *tree= 0; 05322 MEM_ROOT *alloc= param->mem_root; 05323 char *str; 05324 ulong orig_sql_mode; 05325 DBUG_ENTER("get_mm_leaf"); 05326 05327 /* 05328 We need to restore the runtime mem_root of the thread in this 05329 function because it evaluates the value of its argument, while 05330 the argument can be any, e.g. a subselect. The subselect 05331 items, in turn, assume that all the memory allocated during 05332 the evaluation has the same life span as the item itself. 05333 TODO: opt_range.cc should not reset thd->mem_root at all. 05334 */ 05335 param->thd->mem_root= param->old_root; 05336 if (!value) // IS NULL or IS NOT NULL 05337 { 05338 if (field->table->maybe_null) // Can't use a key on this 05339 goto end; 05340 if (!maybe_null) // Not null field 05341 { 05342 if (type == Item_func::ISNULL_FUNC) 05343 tree= &null_element; 05344 goto end; 05345 } 05346 if (!(tree= new (alloc) SEL_ARG(field,is_null_string,is_null_string))) 05347 goto end; // out of memory 05348 if (type == Item_func::ISNOTNULL_FUNC) 05349 { 05350 tree->min_flag=NEAR_MIN; /* IS NOT NULL -> X > NULL */ 05351 tree->max_flag=NO_MAX_RANGE; 05352 } 05353 goto end; 05354 } 05355 05356 /* 05357 1. Usually we can't use an index if the column collation 05358 differ from the operation collation. 05359 05360 2. However, we can reuse a case insensitive index for 05361 the binary searches: 05362 05363 WHERE latin1_swedish_ci_column = 'a' COLLATE lati1_bin; 05364 05365 WHERE latin1_swedish_ci_colimn = BINARY 'a ' 05366 05367 */ 05368 if (field->result_type() == STRING_RESULT && 05369 value->result_type() == STRING_RESULT && 05370 key_part->image_type == Field::itRAW && 05371 ((Field_str*)field)->charset() != conf_func->compare_collation() && 05372 !(conf_func->compare_collation()->state & MY_CS_BINSORT)) 05373 goto end; 05374 05375 if (param->using_real_indexes) 05376 optimize_range= field->optimize_range(param->real_keynr[key_part->key], 05377 key_part->part); 05378 else 05379 optimize_range= TRUE; 05380 05381 if (type == Item_func::LIKE_FUNC) 05382 { 05383 bool like_error; 05384 char buff1[MAX_FIELD_WIDTH],*min_str,*max_str; 05385 String tmp(buff1,sizeof(buff1),value->collation.collation),*res; 05386 uint length,offset,min_length,max_length; 05387 uint field_length= field->pack_length()+maybe_null; 05388 05389 if (!optimize_range) 05390 goto end; 05391 if (!(res= value->val_str(&tmp))) 05392 { 05393 tree= &null_element; 05394 goto end; 05395 } 05396 05397 /* 05398 TODO: 05399 Check if this was a function. This should have be optimized away 05400 in the sql_select.cc 05401 */ 05402 if (res != &tmp) 05403 { 05404 tmp.copy(*res); // Get own copy 05405 res= &tmp; 05406 } 05407 if (field->cmp_type() != STRING_RESULT) 05408 goto end; // Can only optimize strings 05409 05410 offset=maybe_null; 05411 length=key_part->store_length; 05412 05413 if (length != key_part->length + maybe_null) 05414 { 05415 /* key packed with length prefix */ 05416 offset+= HA_KEY_BLOB_LENGTH; 05417 field_length= length - HA_KEY_BLOB_LENGTH; 05418 } 05419 else 05420 { 05421 if (unlikely(length < field_length)) 05422 { 05423 /* 05424 This can only happen in a table created with UNIREG where one key 05425 overlaps many fields 05426 */ 05427 length= field_length; 05428 } 05429 else 05430 field_length= length; 05431 } 05432 length+=offset; 05433 if (!(min_str= (char*) alloc_root(alloc, length*2))) 05434 goto end; 05435 05436 max_str=min_str+length; 05437 if (maybe_null) 05438 max_str[0]= min_str[0]=0; 05439 05440 field_length-= maybe_null; 05441 like_error= my_like_range(field->charset(), 05442 res->ptr(), res->length(), 05443 ((Item_func_like*)(param->cond))->escape, 05444 wild_one, wild_many, 05445 field_length, 05446 min_str+offset, max_str+offset, 05447 &min_length, &max_length); 05448 if (like_error) // Can't optimize with LIKE 05449 goto end; 05450 05451 if (offset != maybe_null) // BLOB or VARCHAR 05452 { 05453 int2store(min_str+maybe_null,min_length); 05454 int2store(max_str+maybe_null,max_length); 05455 } 05456 tree= new (alloc) SEL_ARG(field, min_str, max_str); 05457 goto end; 05458 } 05459 05460 if (!optimize_range && 05461 type != Item_func::EQ_FUNC && 05462 type != Item_func::EQUAL_FUNC) 05463 goto end; // Can't optimize this 05464 05465 /* 05466 We can't always use indexes when comparing a string index to a number 05467 cmp_type() is checked to allow compare of dates to numbers 05468 */ 05469 if (field->result_type() == STRING_RESULT && 05470 value->result_type() != STRING_RESULT && 05471 field->cmp_type() != value->result_type()) 05472 goto end; 05473 /* For comparison purposes allow invalid dates like 2000-01-32 */ 05474 orig_sql_mode= field->table->in_use->variables.sql_mode; 05475 if (value->real_item()->type() == Item::STRING_ITEM && 05476 (field->type() == FIELD_TYPE_DATE || 05477 field->type() == FIELD_TYPE_DATETIME)) 05478 field->table->in_use->variables.sql_mode|= MODE_INVALID_DATES; 05479 if (value->save_in_field_no_warnings(field, 1) < 0) 05480 { 05481 field->table->in_use->variables.sql_mode= orig_sql_mode; 05482 /* This happens when we try to insert a NULL field in a not null column */ 05483 tree= &null_element; // cmp with NULL is never TRUE 05484 goto end; 05485 } 05486 field->table->in_use->variables.sql_mode= orig_sql_mode; 05487 str= (char*) alloc_root(alloc, key_part->store_length+1); 05488 if (!str) 05489 goto end; 05490 if (maybe_null) 05491 *str= (char) field->is_real_null(); // Set to 1 if null 05492 field->get_key_image(str+maybe_null, key_part->length, key_part->image_type); 05493 if (!(tree= new (alloc) SEL_ARG(field, str, str))) 05494 goto end; // out of memory 05495 05496 /* 05497 Check if we are comparing an UNSIGNED integer with a negative constant. 05498 In this case we know that: 05499 (a) (unsigned_int [< | <=] negative_constant) == FALSE 05500 (b) (unsigned_int [> | >=] negative_constant) == TRUE 05501 In case (a) the condition is false for all values, and in case (b) it 05502 is true for all values, so we can avoid unnecessary retrieval and condition 05503 testing, and we also get correct comparison of unsinged integers with 05504 negative integers (which otherwise fails because at query execution time 05505 negative integers are cast to unsigned if compared with unsigned). 05506 */ 05507 if (field->result_type() == INT_RESULT && 05508 value->result_type() == INT_RESULT && 05509 ((Field_num*)field)->unsigned_flag && !((Item_int*)value)->unsigned_flag) 05510 { 05511 longlong item_val= value->val_int(); 05512 if (item_val < 0) 05513 { 05514 if (type == Item_func::LT_FUNC || type == Item_func::LE_FUNC) 05515 { 05516 tree->type= SEL_ARG::IMPOSSIBLE; 05517 goto end; 05518 } 05519 if (type == Item_func::GT_FUNC || type == Item_func::GE_FUNC) 05520 { 05521 tree= 0; 05522 goto end; 05523 } 05524 } 05525 } 05526 05527 switch (type) { 05528 case Item_func::LT_FUNC: 05529 if (field_is_equal_to_item(field,value)) 05530 tree->max_flag=NEAR_MAX; 05531 /* fall through */ 05532 case Item_func::LE_FUNC: 05533 if (!maybe_null) 05534 tree->min_flag=NO_MIN_RANGE; /* From start */ 05535 else 05536 { // > NULL 05537 tree->min_value=is_null_string; 05538 tree->min_flag=NEAR_MIN; 05539 } 05540 break; 05541 case Item_func::GT_FUNC: 05542 if (field_is_equal_to_item(field,value)) 05543 tree->min_flag=NEAR_MIN; 05544 /* fall through */ 05545 case Item_func::GE_FUNC: 05546 tree->max_flag=NO_MAX_RANGE; 05547 break; 05548 case Item_func::SP_EQUALS_FUNC: 05549 tree->min_flag=GEOM_FLAG | HA_READ_MBR_EQUAL;// NEAR_MIN;//512; 05550 tree->max_flag=NO_MAX_RANGE; 05551 break; 05552 case Item_func::SP_DISJOINT_FUNC: 05553 tree->min_flag=GEOM_FLAG | HA_READ_MBR_DISJOINT;// NEAR_MIN;//512; 05554 tree->max_flag=NO_MAX_RANGE; 05555 break; 05556 case Item_func::SP_INTERSECTS_FUNC: 05557 tree->min_flag=GEOM_FLAG | HA_READ_MBR_INTERSECT;// NEAR_MIN;//512; 05558 tree->max_flag=NO_MAX_RANGE; 05559 break; 05560 case Item_func::SP_TOUCHES_FUNC: 05561 tree->min_flag=GEOM_FLAG | HA_READ_MBR_INTERSECT;// NEAR_MIN;//512; 05562 tree->max_flag=NO_MAX_RANGE; 05563 break; 05564 05565 case Item_func::SP_CROSSES_FUNC: 05566 tree->min_flag=GEOM_FLAG | HA_READ_MBR_INTERSECT;// NEAR_MIN;//512; 05567 tree->max_flag=NO_MAX_RANGE; 05568 break; 05569 case Item_func::SP_WITHIN_FUNC: 05570 tree->min_flag=GEOM_FLAG | HA_READ_MBR_WITHIN;// NEAR_MIN;//512; 05571 tree->max_flag=NO_MAX_RANGE; 05572 break; 05573 05574 case Item_func::SP_CONTAINS_FUNC: 05575 tree->min_flag=GEOM_FLAG | HA_READ_MBR_CONTAIN;// NEAR_MIN;//512; 05576 tree->max_flag=NO_MAX_RANGE; 05577 break; 05578 case Item_func::SP_OVERLAPS_FUNC: 05579 tree->min_flag=GEOM_FLAG | HA_READ_MBR_INTERSECT;// NEAR_MIN;//512; 05580 tree->max_flag=NO_MAX_RANGE; 05581 break; 05582 05583 default: 05584 break; 05585 } 05586 05587 end: 05588 param->thd->mem_root= alloc; 05589 DBUG_RETURN(tree); 05590 }
Here is the call graph for this function:
Here is the caller graph for this function:
| static SEL_TREE * get_mm_parts | ( | RANGE_OPT_PARAM * | param, | |
| COND * | cond_func, | |||
| Field * | field, | |||
| Item_func::Functype | type, | |||
| Item * | value, | |||
| Item_result | cmp_type | |||
| ) | [static] |
Definition at line 5266 of file opt_range.cc.
References DBUG_ENTER, DBUG_RETURN, Field::eq(), st_key_part::field, get_mm_leaf(), SEL_TREE::IMPOSSIBLE, SEL_ARG::IMPOSSIBLE, st_key_part::key, RANGE_OPT_PARAM::key_parts, RANGE_OPT_PARAM::key_parts_end, SEL_TREE::keys, SEL_TREE::keys_map, SEL_ARG::MAYBE_KEY, st_key_part::part, RANGE_OPT_PARAM::prev_tables, RANGE_OPT_PARAM::read_tables, sel_add(), Bitmap< 64 >::set_bit(), RANGE_OPT_PARAM::table, Field::table, SEL_TREE::type, and value.
Referenced by get_func_mm_tree(), get_mm_tree(), and get_ne_mm_tree().
05269 { 05270 DBUG_ENTER("get_mm_parts"); 05271 if (field->table != param->table) 05272 DBUG_RETURN(0); 05273 05274 KEY_PART *key_part = param->key_parts; 05275 KEY_PART *end = param->key_parts_end; 05276 SEL_TREE *tree=0; 05277 if (value && 05278 value->used_tables() & ~(param->prev_tables | param->read_tables)) 05279 DBUG_RETURN(0); 05280 for (; key_part != end ; key_part++) 05281 { 05282 if (field->eq(key_part->field)) 05283 { 05284 SEL_ARG *sel_arg=0; 05285 if (!tree && !(tree=new SEL_TREE())) 05286 DBUG_RETURN(0); // OOM 05287 if (!value || !(value->used_tables() & ~param->read_tables)) 05288 { 05289 sel_arg=get_mm_leaf(param,cond_func, 05290 key_part->field,key_part,type,value); 05291 if (!sel_arg) 05292 continue; 05293 if (sel_arg->type == SEL_ARG::IMPOSSIBLE) 05294 { 05295 tree->type=SEL_TREE::IMPOSSIBLE; 05296 DBUG_RETURN(tree); 05297 } 05298 } 05299 else 05300 { 05301 // This key may be used later 05302 if (!(sel_arg= new SEL_ARG(SEL_ARG::MAYBE_KEY))) 05303 DBUG_RETURN(0); // OOM 05304 } 05305 sel_arg->part=(uchar) key_part->part; 05306 tree->keys[key_part->key]=sel_add(tree->keys[key_part->key],sel_arg); 05307 tree->keys_map.set_bit(key_part->key); 05308 } 05309 } 05310 05311 DBUG_RETURN(tree); 05312 }
Here is the call graph for this function:
Here is the caller graph for this function:
| static SEL_TREE * get_mm_tree | ( | RANGE_OPT_PARAM * | param, | |
| COND * | cond | |||
| ) | [static] |
Definition at line 5084 of file opt_range.cc.
References SEL_TREE::ALWAYS, Item_func::arg_count, Item_func::arguments(), Item_func::BETWEEN, Field::cmp_type(), RANGE_OPT_PARAM::cond, cond, Item_func::COND_AND_FUNC, Item::COND_ITEM, RANGE_OPT_PARAM::current_table, DBUG_ENTER, DBUG_RETURN, Field::eq(), Item_func::EQ_FUNC, f, FALSE, Item_field::field, Item::FIELD_ITEM, func, Item::FUNC_ITEM, Item_func::functype(), Item_equal::get_const(), get_func_mm_tree(), get_mm_parts(), Item_func::have_rev_func(), SEL_TREE::IMPOSSIBLE, Item_func::IN_FUNC, Item_field::item_equal, st_table::map, SEL_TREE::MAYBE, RANGE_OPT_PARAM::mem_root, Item_func::MULT_EQUAL_FUNC, NULL, RANGE_OPT_PARAM::old_root, Item_func::OPTIMIZE_NONE, RANGE_OPT_PARAM::prev_tables, RANGE_OPT_PARAM::read_tables, Item::real_item(), Item_func::select_optimize(), Field::table, RANGE_OPT_PARAM::thd, tree_and(), tree_or(), Item::type(), SEL_TREE::type, and value.
Referenced by SQL_SELECT::test_quick_select().
05085 { 05086 SEL_TREE *tree=0; 05087 SEL_TREE *ftree= 0; 05088 Item_field *field_item= 0; 05089 bool inv= FALSE; 05090 Item *value; 05091 DBUG_ENTER("get_mm_tree"); 05092 05093 if (cond->type() == Item::COND_ITEM) 05094 { 05095 List_iterator<Item> li(*((Item_cond*) cond)->argument_list()); 05096 05097 if (((Item_cond*) cond)->functype() == Item_func::COND_AND_FUNC) 05098 { 05099 tree=0; 05100 Item *item; 05101 while ((item=li++)) 05102 { 05103 SEL_TREE *new_tree=get_mm_tree(param,item); 05104 if (param->thd->is_fatal_error) 05105 DBUG_RETURN(0); // out of memory 05106 tree=tree_and(param,tree,new_tree); 05107 if (tree && tree->type == SEL_TREE::IMPOSSIBLE) 05108 break; 05109 } 05110 } 05111 else 05112 { // COND OR 05113 tree=get_mm_tree(param,li++); 05114 if (tree) 05115 { 05116 Item *item; 05117 while ((item=li++)) 05118 { 05119 SEL_TREE *new_tree=get_mm_tree(param,item); 05120 if (!new_tree) 05121 DBUG_RETURN(0); // out of memory 05122 tree=tree_or(param,tree,new_tree); 05123 if (!tree || tree->type == SEL_TREE::ALWAYS) 05124 break; 05125 } 05126 } 05127 } 05128 DBUG_RETURN(tree); 05129 } 05130 /* Here when simple cond */ 05131 if (cond->const_item()) 05132 { 05133 /* 05134 During the cond->val_int() evaluation we can come across a subselect 05135 item which may allocate memory on the thd->mem_root and assumes 05136 all the memory allocated has the same life span as the subselect 05137 item itself. So we have to restore the thread's mem_root here. 05138 */ 05139 MEM_ROOT *tmp_root= param->mem_root; 05140 param->thd->mem_root= param->old_root; 05141 tree= cond->val_int() ? new(tmp_root) SEL_TREE(SEL_TREE::ALWAYS) : 05142 new(tmp_root) SEL_TREE(SEL_TREE::IMPOSSIBLE); 05143 param->thd->mem_root= tmp_root; 05144 DBUG_RETURN(tree); 05145 } 05146 05147 table_map ref_tables= 0; 05148 table_map param_comp= ~(param->prev_tables | param->read_tables | 05149 param->current_table); 05150 if (cond->type() != Item::FUNC_ITEM) 05151 { // Should be a field 05152 ref_tables= cond->used_tables(); 05153 if ((ref_tables & param->current_table) || 05154 (ref_tables & ~(param->prev_tables | param->read_tables))) 05155 DBUG_RETURN(0); 05156 DBUG_RETURN(new SEL_TREE(SEL_TREE::MAYBE)); 05157 } 05158 05159 Item_func *cond_func= (Item_func*) cond; 05160 if (cond_func->functype() == Item_func::BETWEEN || 05161 cond_func->functype() == Item_func::IN_FUNC) 05162 inv= ((Item_func_opt_neg *) cond_func)->negated; 05163 else if (cond_func->select_optimize() == Item_func::OPTIMIZE_NONE) 05164 DBUG_RETURN(0); 05165 05166 param->cond= cond; 05167 05168 switch (cond_func->functype()) { 05169 case Item_func::BETWEEN: 05170 if (cond_func->arguments()[0]->real_item()->type() != Item::FIELD_ITEM) 05171 DBUG_RETURN(0); 05172 field_item= (Item_field*) (cond_func->arguments()[0]->real_item()); 05173 value= NULL; 05174 break; 05175 case Item_func::IN_FUNC: 05176 { 05177 Item_func_in *func=(Item_func_in*) cond_func; 05178 if (func->key_item()->real_item()->type() != Item::FIELD_ITEM) 05179 DBUG_RETURN(0); 05180 field_item= (Item_field*) (func->key_item()->real_item()); 05181 value= NULL; 05182 break; 05183 } 05184 case Item_func::MULT_EQUAL_FUNC: 05185 { 05186 Item_equal *item_equal= (Item_equal *) cond; 05187 if (!(value= item_equal->get_const())) 05188 DBUG_RETURN(0); 05189 Item_equal_iterator it(*item_equal); 05190 ref_tables= value->used_tables(); 05191 while ((field_item= it++)) 05192 { 05193 Field *field= field_item->field; 05194 Item_result cmp_type= field->cmp_type(); 05195 if (!((ref_tables | field->table->map) & param_comp)) 05196 { 05197 tree= get_mm_parts(param, cond, field, Item_func::EQ_FUNC, 05198 value,cmp_type); 05199 ftree= !ftree ? tree : tree_and(param, ftree, tree); 05200 } 05201 } 05202 05203 DBUG_RETURN(ftree); 05204 } 05205 default: 05206 if (cond_func->arguments()[0]->real_item()->type() == Item::FIELD_ITEM) 05207 { 05208 field_item= (Item_field*) (cond_func->arguments()[0]->real_item()); 05209 value= cond_func->arg_count > 1 ? cond_func->arguments()[1] : 0; 05210 } 05211 else if (cond_func->have_rev_func() && 05212 cond_func->arguments()[1]->real_item()->type() == 05213 Item::FIELD_ITEM) 05214 { 05215 field_item= (Item_field*) (cond_func->arguments()[1]->real_item()); 05216 value= cond_func->arguments()[0]; 05217 } 05218 else 05219 DBUG_RETURN(0); 05220 } 05221 05222 /* 05223 If the where condition contains a predicate (ti.field op const), 05224 then not only SELL_TREE for this predicate is built, but 05225 the trees for the results of substitution of ti.field for 05226 each tj.field belonging to the same multiple equality as ti.field 05227 are built as well. 05228 E.g. for WHERE t1.a=t2.a AND t2.a > 10 05229 a SEL_TREE for t2.a > 10 will be built for quick select from t2 05230 and 05231 a SEL_TREE for t1.a > 10 will be built for quick select from t1. 05232 */ 05233 05234 for (uint i= 0; i < cond_func->arg_count; i++) 05235 { 05236 Item *arg= cond_func->arguments()[i]->real_item(); 05237 if (arg != field_item) 05238 ref_tables|= arg->used_tables(); 05239 } 05240 Field *field= field_item->field; 05241 Item_result cmp_type= field->cmp_type(); 05242 if (!((ref_tables | field->table->map) & param_comp)) 05243 ftree= get_func_mm_tree(param, cond_func, field, value, cmp_type, inv); 05244 Item_equal *item_equal= field_item->item_equal; 05245 if (item_equal) 05246 { 05247 Item_equal_iterator it(*item_equal); 05248 Item_field *item; 05249 while ((item= it++)) 05250 { 05251 Field *f= item->field; 05252 if (field->eq(f)) 05253 continue; 05254 if (!((ref_tables | f->table->map) & param_comp)) 05255 { 05256 tree= get_func_mm_tree(param, cond_func, f, value, cmp_type, inv); 05257 ftree= !ftree ? tree : tree_and(param, ftree, tree); 05258 } 05259 } 05260 } 05261 DBUG_RETURN(ftree); 05262 }
Here is the call graph for this function:
Here is the caller graph for this function:
| static SEL_TREE* get_ne_mm_tree | ( | RANGE_OPT_PARAM * | param, | |
| Item_func * | cond_func, | |||
| Field * | field, | |||
| Item * | lt_value, | |||
| Item * | gt_value, | |||
| Item_result | cmp_type | |||
| ) | [static] |
Definition at line 4830 of file opt_range.cc.
References get_mm_parts(), Item_func::GT_FUNC, Item_func::LT_FUNC, and tree_or().
Referenced by get_func_mm_tree().
04834 { 04835 SEL_TREE *tree; 04836 tree= get_mm_parts(param, cond_func, field, Item_func::LT_FUNC, 04837 lt_value, cmp_type); 04838 if (tree) 04839 { 04840 tree= tree_or(param, tree, get_mm_parts(param, cond_func, field, 04841 Item_func::GT_FUNC, 04842 gt_value, cmp_type)); 04843 } 04844 return tree; 04845 }
Here is the call graph for this function:
Here is the caller graph for this function:
| bool get_quick_keys | ( | PARAM * | param, | |
| QUICK_RANGE_SELECT * | quick, | |||
| KEY_PART * | key, | |||
| SEL_ARG * | key_tree, | |||
| char * | min_key, | |||
| uint | min_key_flag, | |||
| char * | max_key, | |||
| uint | max_key_flag | |||
| ) |
Definition at line 7279 of file opt_range.cc.
References EQ_RANGE, flag, st_key::flags, GEOM_FLAG, HA_END_SPACE_KEY, HA_NOSAME, HA_NULL_PART_KEY, insert_dynamic(), key, st_key::key_parts, SEL_ARG::KEY_RANGE, SEL_ARG::left, SEL_ARG::max_flag, PARAM::max_key, QUICK_RANGE::max_length, memcmp(), SEL_ARG::min_flag, PARAM::min_key, QUICK_RANGE::min_length, SEL_ARG::next_key_part, NO_MAX_RANGE, NO_MIN_RANGE, null_element, null_part_in_key(), NULL_RANGE, SEL_ARG::part, quick, SEL_ARG::right, set_if_bigger, SEL_ARG::store(), SEL_ARG::store_max_key(), SEL_ARG::store_min_key(), SEL_ARG::type, and UNIQUE_RANGE.
Referenced by get_quick_select().
07282 { 07283 QUICK_RANGE *range; 07284 uint flag; 07285 07286 if (key_tree->left != &null_element) 07287 { 07288 if (get_quick_keys(param,quick,key,key_tree->left, 07289 min_key,min_key_flag, max_key, max_key_flag)) 07290 return 1; 07291 } 07292 char *tmp_min_key=min_key,*tmp_max_key=max_key; 07293 key_tree->store(key[key_tree->part].store_length, 07294 &tmp_min_key,min_key_flag,&tmp_max_key,max_key_flag); 07295 07296 if (key_tree->next_key_part && 07297 key_tree->next_key_part->part == key_tree->part+1 && 07298 key_tree->next_key_part->type == SEL_ARG::KEY_RANGE) 07299 { // const key as prefix 07300 if (!((tmp_min_key - min_key) != (tmp_max_key - max_key) || 07301 memcmp(min_key,max_key, (uint) (tmp_max_key - max_key)) || 07302 key_tree->min_flag || key_tree->max_flag)) 07303 { 07304 if (get_quick_keys(param,quick,key,key_tree->next_key_part, 07305 tmp_min_key, min_key_flag | key_tree->min_flag, 07306 tmp_max_key, max_key_flag | key_tree->max_flag)) 07307 return 1; 07308 goto end; // Ugly, but efficient 07309 } 07310 { 07311 uint tmp_min_flag=key_tree->min_flag,tmp_max_flag=key_tree->max_flag; 07312 if (!tmp_min_flag) 07313 key_tree->next_key_part->store_min_key(key, &tmp_min_key, 07314 &tmp_min_flag); 07315 if (!tmp_max_flag) 07316 key_tree->next_key_part->store_max_key(key, &tmp_max_key, 07317 &tmp_max_flag); 07318 flag=tmp_min_flag | tmp_max_flag; 07319 } 07320 } 07321 else 07322 { 07323 flag = (key_tree->min_flag & GEOM_FLAG) ? 07324 key_tree->min_flag : key_tree->min_flag | key_tree->max_flag; 07325 } 07326 07327 /* 07328 Ensure that some part of min_key and max_key are used. If not, 07329 regard this as no lower/upper range 07330 */ 07331 if ((flag & GEOM_FLAG) == 0) 07332 { 07333 if (tmp_min_key != param->min_key) 07334 flag&= ~NO_MIN_RANGE; 07335 else 07336 flag|= NO_MIN_RANGE; 07337 if (tmp_max_key != param->max_key) 07338 flag&= ~NO_MAX_RANGE; 07339 else 07340 flag|= NO_MAX_RANGE; 07341 } 07342 if (flag == 0) 07343 { 07344 uint length= (uint) (tmp_min_key - param->min_key); 07345 if (length == (uint) (tmp_max_key - param->max_key) && 07346 !memcmp(param->min_key,param->max_key,length)) 07347 { 07348 KEY *table_key=quick->head->key_info+quick->index; 07349 flag=EQ_RANGE; 07350 if ((table_key->flags & (HA_NOSAME | HA_END_SPACE_KEY)) == HA_NOSAME && 07351 key->part == table_key->key_parts-1) 07352 { 07353 if (!(table_key->flags & HA_NULL_PART_KEY) || 07354 !null_part_in_key(key, 07355 param->min_key, 07356 (uint) (tmp_min_key - param->min_key))) 07357 flag|= UNIQUE_RANGE; 07358 else 07359 flag|= NULL_RANGE; 07360 } 07361 } 07362 } 07363 07364 /* Get range for retrieving rows in QUICK_SELECT::get_next */ 07365 if (!(range= new QUICK_RANGE((const char *) param->min_key, 07366 (uint) (tmp_min_key - param->min_key), 07367 (const char *) param->max_key, 07368 (uint) (tmp_max_key - param->max_key), 07369 flag))) 07370 return 1; // out of memory 07371 07372 set_if_bigger(quick->max_used_key_length,range->min_length); 07373 set_if_bigger(quick->max_used_key_length,range->max_length); 07374 set_if_bigger(quick->used_key_parts, (uint) key_tree->part+1); 07375 if (insert_dynamic(&quick->ranges, (gptr)&range)) 07376 return 1; 07377 07378 end: 07379 if (key_tree->right != &null_element) 07380 return get_quick_keys(param,quick,key,key_tree->right, 07381 min_key,min_key_flag, 07382 max_key,max_key_flag); 07383 return 0; 07384 }
Here is the call graph for this function:
Here is the caller graph for this function:
| QUICK_RANGE_SELECT * get_quick_select | ( | PARAM * | param, | |
| uint | index, | |||
| SEL_ARG * | key_tree, | |||
| MEM_ROOT * | alloc = NULL | |||
| ) |
Definition at line 7237 of file opt_range.cc.
References DBUG_ENTER, DBUG_RETURN, get_quick_keys(), HA_SPATIAL, PARAM::key, st_table::key_info, PARAM::max_key, memdup_root(), PARAM::min_key, quick, RANGE_OPT_PARAM::real_keynr, RANGE_OPT_PARAM::table, test, and RANGE_OPT_PARAM::thd.
Referenced by TRP_GROUP_MIN_MAX::make_quick(), TRP_ROR_INTERSECT::make_quick(), and TRP_RANGE::make_quick().
07239 { 07240 QUICK_RANGE_SELECT *quick; 07241 DBUG_ENTER("get_quick_select"); 07242 07243 if (param->table->key_info[param->real_keynr[idx]].flags & HA_SPATIAL) 07244 quick=new QUICK_RANGE_SELECT_GEOM(param->thd, param->table, 07245 param->real_keynr[idx], 07246 test(parent_alloc), 07247 parent_alloc); 07248 else 07249 quick=new QUICK_RANGE_SELECT(param->thd, param->table, 07250 param->real_keynr[idx], 07251 test(parent_alloc)); 07252 07253 if (quick) 07254 { 07255 if (quick->error || 07256 get_quick_keys(param,quick,param->key[idx],key_tree,param->min_key,0, 07257 param->max_key,0)) 07258 { 07259 delete quick; 07260 quick=0; 07261 } 07262 else 07263 { 07264 quick->key_parts=(KEY_PART*) 07265 memdup_root(parent_alloc? parent_alloc : &quick->alloc, 07266 (char*) param->key[idx], 07267 sizeof(KEY_PART)* 07268 param->table->key_info[param->real_keynr[idx]].key_parts); 07269 } 07270 } 07271 DBUG_RETURN(quick); 07272 }
Here is the call graph for this function:
Here is the caller graph for this function:
| QUICK_RANGE_SELECT* get_quick_select_for_ref | ( | THD * | thd, | |
| TABLE * | table, | |||
| TABLE_REF * | ref, | |||
| ha_rows | records | |||
| ) |
Definition at line 7482 of file opt_range.cc.
References alloc_root(), cp_buffer_from_ref(), EQ_RANGE, err, st_key_part::field, st_key_part_info::field, QUICK_RANGE::flag, st_key::flags, HA_END_SPACE_KEY, HA_NOSAME, insert_dynamic(), st_table_ref::key, st_table_ref::key_buff, st_table::key_info, st_table_ref::key_length, st_key::key_length, st_key::key_part, st_table_ref::key_parts, st_key_part::length, st_key_part_info::length, QUICK_RANGE::max_key, QUICK_RANGE::max_length, QUICK_RANGE::min_key, QUICK_RANGE::min_length, st_key_part::null_bit, st_key_part_info::null_bit, st_table_ref::null_ref_key, st_key_part::part, quick, st_key_part::store_length, and st_key_part_info::store_length.
Referenced by create_sort_index().
07484 { 07485 MEM_ROOT *old_root, *alloc; 07486 QUICK_RANGE_SELECT *quick; 07487 KEY *key_info = &table->key_info[ref->key]; 07488 KEY_PART *key_part; 07489 QUICK_RANGE *range; 07490 uint part; 07491 07492 old_root= thd->mem_root; 07493 /* The following call may change thd->mem_root */ 07494 quick= new QUICK_RANGE_SELECT(thd, table, ref->key, 0); 07495 /* save mem_root set by QUICK_RANGE_SELECT constructor */ 07496 alloc= thd->mem_root; 07497 /* 07498 return back default mem_root (thd->mem_root) changed by 07499 QUICK_RANGE_SELECT constructor 07500 */ 07501 thd->mem_root= old_root; 07502 07503 if (!quick) 07504 return 0; /* no ranges found */ 07505 if (quick->init()) 07506 goto err; 07507 quick->records= records; 07508 07509 if (cp_buffer_from_ref(thd, table, ref) && thd->is_fatal_error || 07510 !(range= new(alloc) QUICK_RANGE())) 07511 goto err; // out of memory 07512 07513 range->min_key=range->max_key=(char*) ref->key_buff; 07514 range->min_length=range->max_length=ref->key_length; 07515 range->flag= ((ref->key_length == key_info->key_length && 07516 (key_info->flags & (HA_NOSAME | HA_END_SPACE_KEY)) == 07517 HA_NOSAME) ? EQ_RANGE : 0); 07518 07519 if (!(quick->key_parts=key_part=(KEY_PART *) 07520 alloc_root(&quick->alloc,sizeof(KEY_PART)*ref->key_parts))) 07521 goto err; 07522 07523 for (part=0 ; part < ref->key_parts ;part++,key_part++) 07524 { 07525 key_part->part=part; 07526 key_part->field= key_info->key_part[part].field; 07527 key_part->length= key_info->key_part[part].length; 07528 key_part->store_length= key_info->key_part[part].store_length; 07529 key_part->null_bit= key_info->key_part[part].null_bit; 07530 } 07531 if (insert_dynamic(&quick->ranges,(gptr)&range)) 07532 goto err; 07533 07534 /* 07535 Add a NULL range if REF_OR_NULL optimization is used. 07536 For example: 07537 if we have "WHERE A=2 OR A IS NULL" we created the (A=2) range above 07538 and have ref->null_ref_key set. Will create a new NULL range here. 07539 */ 07540 if (ref->null_ref_key) 07541 { 07542 QUICK_RANGE *null_range; 07543 07544 *ref->null_ref_key= 1; // Set null byte then create a range 07545 if (!(null_range= new (alloc) QUICK_RANGE((char*)ref->key_buff, 07546 ref->key_length, 07547 (char*)ref->key_buff, 07548 ref->key_length, 07549 EQ_RANGE))) 07550 goto err; 07551 *ref->null_ref_key= 0; // Clear null byte 07552 if (insert_dynamic(&quick->ranges,(gptr)&null_range)) 07553 goto err; 07554 } 07555 07556 return quick; 07557 07558 err: 07559 delete quick; 07560 return 0; 07561 }
Here is the call graph for this function:
Here is the caller graph for this function:
Definition at line 6081 of file opt_range.cc.
References SEL_ARG::find_range(), and SEL_ARG::next.
Referenced by key_and().
06082 { 06083 (*e1)=root1->find_range(*e2); // first e1->min < e2->min 06084 if ((*e1)->cmp_max_to_min(*e2) < 0) 06085 { 06086 if (!((*e1)=(*e1)->next)) 06087 return 1; 06088 if ((*e1)->cmp_min_to_max(*e2) > 0) 06089 { 06090 (*e2)=(*e2)->next; 06091 return 1; 06092 } 06093 } 06094 return 0; 06095 }
Here is the call graph for this function:
Here is the caller graph for this function:
Definition at line 3377 of file opt_range.cc.
References ha_statistics::data_file_length, DBUG_ENTER, DBUG_PRINT, DBUG_RETURN, DISK_SEEK_BASE_COST, DISK_SEEK_PROP_COST, st_table::file, IO_SIZE, st_table_share::primary_key, handler::primary_key_is_clustered(), handler::read_time(), rows2double, st_table::s, handler::stats, RANGE_OPT_PARAM::table, JOIN::tables, RANGE_OPT_PARAM::thd, and ulonglong2double.
Referenced by get_best_disjunct_quick(), and ror_intersect_add().
03378 { 03379 double result; 03380 DBUG_ENTER("get_sweep_read_cost"); 03381 if (param->table->file->primary_key_is_clustered()) 03382 { 03383 result= param->table->file->read_time(param->table->s->primary_key, 03384 records, records); 03385 } 03386 else 03387 { 03388 double n_blocks= 03389 ceil(ulonglong2double(param->table->file->stats.data_file_length) / 03390 IO_SIZE); 03391 double busy_blocks= 03392 n_blocks * (1.0 - pow(1.0 - 1.0/n_blocks, rows2double(records))); 03393 if (busy_blocks < 1.0) 03394 busy_blocks= 1.0; 03395 DBUG_PRINT("info",("sweep: nblocks=%g, busy_blocks=%g", n_blocks, 03396 busy_blocks)); 03397 /* 03398 Disabled: Bail out if # of blocks to read is bigger than # of blocks in 03399 table data file. 03400 if (max_cost != DBL_MAX && (busy_blocks+index_reads_cost) >= n_blocks) 03401 return 1; 03402 */ 03403 JOIN *join= param->thd->lex->select_lex.join; 03404 if (!join || join->tables == 1) 03405 { 03406 /* No join, assume reading is done in one 'sweep' */ 03407 result= busy_blocks*(DISK_SEEK_BASE_COST + 03408 DISK_SEEK_PROP_COST*n_blocks/busy_blocks); 03409 } 03410 else 03411 { 03412 /* 03413 Possibly this is a join with source table being non-last table, so 03414 assume that disk seeks are random here. 03415 */ 03416 result= busy_blocks; 03417 } 03418 } 03419 DBUG_PRINT("info",("returning cost=%g", result)); 03420 DBUG_RETURN(result); 03421 }
Here is the call graph for this function:
Here is the caller graph for this function:
| void imerge_list_and_list | ( | List< SEL_IMERGE > * | im1, | |
| List< SEL_IMERGE > * | im2 | |||
| ) | [inline] |
Definition at line 790 of file opt_range.cc.
References List< T >::concat().
Referenced by tree_and().
00791 { 00792 im1->concat(im2); 00793 }
Here is the call graph for this function:
Here is the caller graph for this function:
| int imerge_list_or_list | ( | RANGE_OPT_PARAM * | param, | |
| List< SEL_IMERGE > * | im1, | |||
| List< SEL_IMERGE > * | im2 | |||
| ) |
Definition at line 819 of file opt_range.cc.
References base_list::empty(), List< T >::head(), SEL_IMERGE::or_sel_imerge_with_checks(), and List< T >::push_back().
Referenced by tree_or().
00822 { 00823 SEL_IMERGE *imerge= im1->head(); 00824 im1->empty(); 00825 im1->push_back(imerge); 00826 00827 return imerge->or_sel_imerge_with_checks(param, im2->head()); 00828 }
Here is the call graph for this function:
Here is the caller graph for this function:
| int imerge_list_or_tree | ( | RANGE_OPT_PARAM * | param, | |
| List< SEL_IMERGE > * | im1, | |||
| SEL_TREE * | tree | |||
| ) |
Definition at line 839 of file opt_range.cc.
References base_list::is_empty(), SEL_IMERGE::or_sel_tree_with_checks(), and List_iterator< T >::remove().
Referenced by tree_or().
00842 { 00843 SEL_IMERGE *imerge; 00844 List_iterator<SEL_IMERGE> it(*im1); 00845 while ((imerge= it++)) 00846 { 00847 if (imerge->or_sel_tree_with_checks(param, tree)) 00848 it.remove(); 00849 } 00850 return im1->is_empty(); 00851 }
Here is the call graph for this function:
Here is the caller graph for this function:
Definition at line 7187 of file opt_range.cc.
References FALSE, st_key_part_info::field, st_table::file, st_table::key_info, st_key::key_part, st_key::key_parts, st_key_part_info::length, MAX_KEY, st_table_share::primary_key, handler::primary_key_is_clustered(), st_table::s, RANGE_OPT_PARAM::table, and TRUE.
Referenced by check_quick_keys().
07188 { 07189 KEY *table_key= param->table->key_info + keynr; 07190 KEY_PART_INFO *key_part= table_key->key_part + nparts; 07191 KEY_PART_INFO *key_part_end= (table_key->key_part + 07192 table_key->key_parts); 07193 uint pk_number; 07194 07195 if (key_part == key_part_end) 07196 return TRUE; 07197 pk_number= param->table->s->primary_key; 07198 if (!param->table->file->primary_key_is_clustered() || pk_number == MAX_KEY) 07199 return FALSE; 07200 07201 KEY_PART_INFO *pk_part= param->table->key_info[pk_number].key_part; 07202 KEY_PART_INFO *pk_part_end= pk_part + 07203 param->table->key_info[pk_number].key_parts; 07204 for (;(key_part!=key_part_end) && (pk_part != pk_part_end); 07205 ++key_part, ++pk_part) 07206 { 07207 if ((key_part->field != pk_part->field) || 07208 (key_part->length != pk_part->length)) 07209 return FALSE; 07210 } 07211 return (key_part == key_part_end); 07212 }
Here is the call graph for this function:
Here is the caller graph for this function:
Definition at line 5961 of file opt_range.cc.
References and_all_keys(), SEL_ARG::clone_and(), CLONE_KEY1_MAYBE, CLONE_KEY2_MAYBE, cmp, SEL_ARG::cmp_max_to_max(), SEL_ARG::cmp_min_to_min(), GEOM_FLAG, get_range(), SEL_ARG::IMPOSSIBLE, SEL_ARG::increment_use_count(), SEL_ARG::insert(), key1, key2, SEL_ARG::MAYBE_KEY, SEL_ARG::next, SEL_ARG::next_key_part, null_element, swap_clone_flag, swap_variables, and SEL_ARG::type.
Referenced by and_all_keys(), and tree_and().
05962 { 05963 if (!key1) 05964 return key2; 05965 if (!key2) 05966 return key1; 05967 if (key1->part != key2->part) 05968 { 05969 if (key1->part > key2->part) 05970 { 05971 swap_variables(SEL_ARG *, key1, key2); 05972 clone_flag=swap_clone_flag(clone_flag); 05973 } 05974 // key1->part < key2->part 05975 key1->use_count--; 05976 if (key1->use_count > 0) 05977 if (!(key1= key1->clone_tree())) 05978 return 0; // OOM 05979 return and_all_keys(key1,key2,clone_flag); 05980 } 05981 05982 if (((clone_flag & CLONE_KEY2_MAYBE) && 05983 !(clone_flag & CLONE_KEY1_MAYBE) && 05984 key2->type != SEL_ARG::MAYBE_KEY) || 05985 key1->type == SEL_ARG::MAYBE_KEY) 05986 { // Put simple key in key2 05987 swap_variables(SEL_ARG *, key1, key2); 05988 clone_flag=swap_clone_flag(clone_flag); 05989 } 05990 05991 /* If one of the key is MAYBE_KEY then the found region may be smaller */ 05992 if (key2->type == SEL_ARG::MAYBE_KEY) 05993 { 05994 if (key1->use_count > 1) 05995 { 05996 key1->use_count--; 05997 if (!(key1=key1->clone_tree())) 05998 return 0; // OOM 05999 key1->use_count++; 06000 } 06001 if (key1->type == SEL_ARG::MAYBE_KEY) 06002 { // Both are maybe key 06003 key1->next_key_part=key_and(key1->next_key_part,key2->next_key_part, 06004 clone_flag); 06005 if (key1->next_key_part && 06006 key1->next_key_part->type == SEL_ARG::IMPOSSIBLE) 06007 return key1; 06008 } 06009 else 06010 { 06011 key1->maybe_smaller(); 06012 if (key2->next_key_part) 06013 { 06014 key1->use_count--; // Incremented in and_all_keys 06015 return and_all_keys(key1,key2,clone_flag); 06016 } 06017 key2->use_count--; // Key2 doesn't have a tree 06018 } 06019 return key1; 06020 } 06021 06022 if ((key1->min_flag | key2->min_flag) & GEOM_FLAG) 06023 { 06024 /* TODO: why not leave one of the trees? */ 06025 key1->free_tree(); 06026 key2->free_tree(); 06027 return 0; // Can't optimize this 06028 } 06029 06030 if ((key1->min_flag | key2->min_flag) & GEOM_FLAG) 06031 { 06032 key1->free_tree(); 06033 key2->free_tree(); 06034 return 0; // Can't optimize this 06035 } 06036 06037 key1->use_count--; 06038 key2->use_count--; 06039 SEL_ARG *e1=key1->first(), *e2=key2->first(), *new_tree=0; 06040 06041 while (e1 && e2) 06042 { 06043 int cmp=e1->cmp_min_to_min(e2); 06044 if (cmp < 0) 06045 { 06046 if (get_range(&e1,&e2,key1)) 06047 continue; 06048 } 06049 else if (get_range(&e2,&e1,key2)) 06050 continue; 06051 SEL_ARG *next=key_and(e1->next_key_part,e2->next_key_part,clone_flag); 06052 e1->increment_use_count(1); 06053 e2->increment_use_count(1); 06054 if (!next || next->type != SEL_ARG::IMPOSSIBLE) 06055 { 06056 SEL_ARG *new_arg= e1->clone_and(e2); 06057 if (!new_arg) 06058 return &null_element; // End of memory 06059 new_arg->next_key_part=next; 06060 if (!new_tree) 06061 { 06062 new_tree=new_arg; 06063 } 06064 else 06065 new_tree=new_tree->insert(new_arg); 06066 } 06067 if (e1->cmp_max_to_max(e2) < 0) 06068 e1=e1->next; // e1 can't overlapp next e2 06069 else 06070 e2=e2->next; 06071 } 06072 key1->free_tree(); 06073 key2->free_tree(); 06074 if (!new_tree) 06075 return &null_element; // Impossible range 06076 return new_tree; 06077 }
Here is the call graph for this function:
Here is the caller graph for this function:
Definition at line 6099 of file opt_range.cc.
References cmp, SEL_ARG::cmp_min_to_max(), SEL_ARG::copy_max(), SEL_ARG::copy_min(), eq_tree(), GEOM_FLAG, key, key1, key2, SEL_ARG::MAYBE_KEY, SEL_ARG::merge_flags(), SEL_ARG::next, SEL_ARG::next_key_part, NO_MAX_RANGE, NO_MIN_RANGE, swap_variables, and SEL_ARG::use_count.
Referenced by tree_or().
06100 { 06101 if (!key1) 06102 { 06103 if (key2) 06104 { 06105 key2->use_count--; 06106 key2->free_tree(); 06107 } 06108 return 0; 06109 } 06110 if (!key2) 06111 { 06112 key1->use_count--; 06113 key1->free_tree(); 06114 return 0; 06115 } 06116 key1->use_count--; 06117 key2->use_count--; 06118 06119 if (key1->part != key2->part || 06120 (key1->min_flag | key2->min_flag) & GEOM_FLAG) 06121 { 06122 key1->free_tree(); 06123 key2->free_tree(); 06124 return 0; // Can't optimize this 06125 } 06126 06127 // If one of the key is MAYBE_KEY then the found region may be bigger 06128 if (key1->type == SEL_ARG::MAYBE_KEY) 06129 { 06130 key2->free_tree(); 06131 key1->use_count++; 06132 return key1; 06133 } 06134 if (key2->type == SEL_ARG::MAYBE_KEY) 06135 { 06136 key1->free_tree(); 06137 key2->use_count++; 06138 return key2; 06139 } 06140 06141 if (key1->use_count > 0) 06142 { 06143 if (key2->use_count == 0 || key1->elements > key2->elements) 06144 { 06145 swap_variables(SEL_ARG *,key1,key2); 06146 } 06147 if (key1->use_count > 0 || !(key1=key1->clone_tree())) 06148 return 0; // OOM 06149 } 06150 06151 // Add tree at key2 to tree at key1 06152 bool key2_shared=key2->use_count != 0; 06153 key1->maybe_flag|=key2->maybe_flag; 06154 06155 for (key2=key2->first(); key2; ) 06156 { 06157 SEL_ARG *tmp=key1->find_range(key2); // Find key1.min <= key2.min 06158 int cmp; 06159 06160 if (!tmp) 06161 { 06162 tmp=key1->first(); // tmp.min > key2.min 06163 cmp= -1; 06164 } 06165 else if ((cmp=tmp->cmp_max_to_min(key2)) < 0) 06166 { // Found tmp.max < key2.min 06167 SEL_ARG *next=tmp->next; 06168 if (cmp == -2 && eq_tree(tmp->next_key_part,key2->next_key_part)) 06169 { 06170 // Join near ranges like tmp.max < 0 and key2.min >= 0 06171 SEL_ARG *key2_next=key2->next; 06172 if (key2_shared) 06173 { 06174 if (!(key2=new SEL_ARG(*key2))) 06175 return 0; // out of memory 06176 key2->increment_use_count(key1->use_count+1); 06177 key2->next=key2_next; // New copy of key2 06178 } 06179 key2->copy_min(tmp); 06180 if (!(key1=key1->tree_delete(tmp))) 06181 { // Only one key in tree 06182 key1=key2; 06183 key1->make_root(); 06184 key2=key2_next; 06185 break; 06186 } 06187 } 06188 if (!(tmp=next)) // tmp.min > key2.min 06189 break; // Copy rest of key2 06190 } 06191 if (cmp < 0) 06192 { // tmp.min > key2.min 06193 int tmp_cmp; 06194 if ((tmp_cmp=tmp->cmp_min_to_max(key2)) > 0) // if tmp.min > key2.max 06195 { 06196 if (tmp_cmp == 2 && eq_tree(tmp->next_key_part,key2->next_key_part)) 06197 { // ranges are connected 06198 tmp->copy_min_to_min(key2); 06199 key1->merge_flags(key2); 06200 if (tmp->min_flag & NO_MIN_RANGE && 06201 tmp->max_flag & NO_MAX_RANGE) 06202 { 06203 if (key1->maybe_flag) 06204 return new SEL_ARG(SEL_ARG::MAYBE_KEY); 06205 return 0; 06206 } 06207 key2->increment_use_count(-1); // Free not used tree 06208 key2=key2->next; 06209 continue; 06210 } 06211 else 06212 { 06213 SEL_ARG *next=key2->next; // Keys are not overlapping 06214 if (key2_shared) 06215 { 06216 SEL_ARG *cpy= new SEL_ARG(*key2); // Must make copy 06217 if (!cpy) 06218 return 0; // OOM 06219 key1=key1->insert(cpy); 06220 key2->increment_use_count(key1->use_count+1); 06221 } 06222 else 06223 key1=key1->insert(key2); // Will destroy key2_root 06224 key2=next; 06225 continue; 06226 } 06227 } 06228 } 06229 06230 // tmp.max >= key2.min && tmp.min <= key.max (overlapping ranges) 06231 if (eq_tree(tmp->next_key_part,key2->next_key_part)) 06232 { 06233 if (tmp->is_same(key2)) 06234 { 06235 tmp->merge_flags(key2); // Copy maybe flags 06236 key2->increment_use_count(-1); // Free not used tree 06237 } 06238 else 06239 { 06240 SEL_ARG *last=tmp; 06241 while (last->next && last->next->cmp_min_to_max(key2) <= 0 && 06242 eq_tree(last->next->next_key_part,key2->next_key_part)) 06243 { 06244 SEL_ARG *save=last; 06245 last=last->next; 06246 key1=key1->tree_delete(save); 06247 } 06248 last->copy_min(tmp); 06249 if (last->copy_min(key2) || last->copy_max(key2)) 06250 { // Full range 06251 key1->free_tree(); 06252 for (; key2 ; key2=key2->next) 06253 key2->increment_use_count(-1); // Free not used tree 06254 if (key1->maybe_flag) 06255 return new SEL_ARG(SEL_ARG::MAYBE_KEY); 06256 return 0; 06257 } 06258 } 06259 key2=key2->next; 06260 continue; 06261 } 06262 06263 if (cmp >= 0 && tmp->cmp_min_to_min(key2) < 0) 06264 { // tmp.min <= x < key2.min 06265 SEL_ARG *new_arg=tmp->clone_first(key2); 06266 if (!new_arg) 06267 return 0; // OOM 06268 if ((new_arg->next_key_part= key1->next_key_part)) 06269 new_arg->increment_use_count(key1->use_count+1); 06270 tmp->copy_min_to_min(key2); 06271 key1=key1->insert(new_arg); 06272 } 06273 06274 // tmp.min >= key2.min && tmp.min <= key2.max 06275 SEL_ARG key(*key2); // Get copy we can modify 06276 for (;;) 06277 { 06278 if (tmp->cmp_min_to_min(&key) > 0) 06279 { // key.min <= x < tmp.min 06280 SEL_ARG *new_arg=key.clone_first(tmp); 06281 if (!new_arg) 06282 return 0; // OOM 06283 if ((new_arg->next_key_part=key.next_key_part)) 06284 new_arg->increment_use_count(key1->use_count+1); 06285 key1=key1->insert(new_arg); 06286 } 06287 if ((cmp=tmp->cmp_max_to_max(&key)) <= 0) 06288 { // tmp.min. <= x <= tmp.max 06289 tmp->maybe_flag|= key.maybe_flag; 06290 key.increment_use_count(key1->use_count+1); 06291 tmp->next_key_part=key_or(tmp->next_key_part,key.next_key_part); 06292 if (!cmp) // Key2 is ready 06293 break; 06294 key.copy_max_to_min(tmp); 06295 if (!(tmp=tmp->next)) 06296 { 06297 SEL_ARG *tmp2= new SEL_ARG(key); 06298 if (!tmp2) 06299 return 0; // OOM 06300 key1=key1->insert(tmp2); 06301 key2=key2->next; 06302 goto end; 06303 } 06304 if (tmp->cmp_min_to_max(&key) > 0) 06305 { 06306 SEL_ARG *tmp2= new SEL_ARG(key); 06307 if (!tmp2) 06308 return 0; // OOM 06309 key1=key1->insert(tmp2); 06310 break; 06311 } 06312 } 06313 else 06314 { 06315 SEL_ARG *new_arg=tmp->clone_last(&key); // tmp.min <= x <= key.max 06316 if (!new_arg) 06317 return 0; // OOM 06318 tmp->copy_max_to_min(&key); 06319 tmp->increment_use_count(key1->use_count+1); 06320 /* Increment key count as it may be used for next loop */ 06321 key.increment_use_count(1); 06322 new_arg->next_key_part=key_or(tmp->next_key_part,key.next_key_part); 06323 key1=key1->insert(new_arg); 06324 break; 06325 } 06326 } 06327 key2=key2->next; 06328 } 06329 06330 end: 06331 while (key2) 06332 { 06333 SEL_ARG *next=key2->next; 06334 if (key2_shared) 06335 { 06336 SEL_ARG *tmp=new SEL_ARG(*key2); // Must make copy 06337 if (!tmp) 06338 return 0; 06339 key2->increment_use_count(key1->use_count+1); 06340 key1=key1->insert(tmp); 06341 } 06342 else 06343 key1=key1->insert(key2); // Will destroy key2_root 06344 key2=next; 06345 } 06346 key1->use_count++; 06347 return key1; 06348 }
Here is the call graph for this function:
Here is the caller graph for this function:
Definition at line 6539 of file opt_range.cc.
References SEL_ARG::left, null_element, SEL_ARG::parent, SEL_ARG::parent_ptr(), and SEL_ARG::right.
06540 { 06541 SEL_ARG *y=leaf->right; 06542 leaf->right=y->left; 06543 if (y->left != &null_element) 06544 y->left->parent=leaf; 06545 if (!(y->parent=leaf->parent)) 06546 *root=y; 06547 else 06548 *leaf->parent_ptr()=y; 06549 y->left=leaf; 06550 leaf->parent=y; 06551 }
Here is the call graph for this function:
| static ROR_SCAN_INFO* make_ror_scan | ( | const PARAM * | param, | |
| int | idx, | |||
| SEL_ARG * | sel_arg | |||
| ) | [static] |
Definition at line 3798 of file opt_range.cc.
References alloc_root(), bitmap_clear_all, bitmap_init(), bitmap_is_set(), bitmap_set_bit(), st_ror_scan_info::covered_fields, DBUG_ENTER, DBUG_RETURN, FALSE, st_key_part_info::fieldnr, st_table_share::fields, PARAM::fields_bitmap_size, st_table::file, get_index_only_read_time(), st_ror_scan_info::idx, st_ror_scan_info::index_read_cost, st_table::key_info, st_key::key_length, st_key::key_part, st_key::key_parts, st_ror_scan_info::key_rec_length, st_ror_scan_info::keynr, RANGE_OPT_PARAM::mem_root, PARAM::needed_fields, NULL, st_table::quick_rows, RANGE_OPT_PARAM::real_keynr, st_ror_scan_info::records, handler::ref_length, st_table::s, st_ror_scan_info::sel_arg, and RANGE_OPT_PARAM::table.
Referenced by get_best_ror_intersect().
03799 { 03800 ROR_SCAN_INFO *ror_scan; 03801 my_bitmap_map *bitmap_buf; 03802 uint keynr; 03803 DBUG_ENTER("make_ror_scan"); 03804 03805 if (!(ror_scan= (ROR_SCAN_INFO*)alloc_root(param->mem_root, 03806 sizeof(ROR_SCAN_INFO)))) 03807 DBUG_RETURN(NULL); 03808 03809 ror_scan->idx= idx; 03810 ror_scan->keynr= keynr= param->real_keynr[idx]; 03811 ror_scan->key_rec_length= (param->table->key_info[keynr].key_length + 03812 param->table->file->ref_length); 03813 ror_scan->sel_arg= sel_arg; 03814 ror_scan->records= param->table->quick_rows[keynr]; 03815 03816 if (!(bitmap_buf= (my_bitmap_map*) alloc_root(param->mem_root, 03817 param->fields_bitmap_size))) 03818 DBUG_RETURN(NULL); 03819 03820 if (bitmap_init(&ror_scan->covered_fields, bitmap_buf, 03821 param->table->s->fields, FALSE)) 03822 DBUG_RETURN(NULL); 03823 bitmap_clear_all(&ror_scan->covered_fields); 03824 03825 KEY_PART_INFO *key_part= param->table->key_info[keynr].key_part; 03826 KEY_PART_INFO *key_part_end= key_part + 03827 param->table->key_info[keynr].key_parts; 03828 for (;key_part != key_part_end; ++key_part) 03829 { 03830 if (bitmap_is_set(¶m->needed_fields, key_part->fieldnr-1)) 03831 bitmap_set_bit(&ror_scan->covered_fields, key_part->fieldnr-1); 03832 } 03833 ror_scan->index_read_cost= 03834 get_index_only_read_time(param, param->table->quick_rows[ror_scan->keynr], 03835 ror_scan->keynr); 03836 DBUG_RETURN(ror_scan); 03837 }
Here is the call graph for this function:
Here is the caller graph for this function:
| SQL_SELECT* make_select | ( | TABLE * | head, | |
| table_map | const_tables, | |||
| table_map | read_tables, | |||
| COND * | conds, | |||
| bool | allow_null_cond, | |||
| int * | error | |||
| ) |
Definition at line 863 of file opt_range.cc.
References SQL_SELECT::cond, SQL_SELECT::const_tables, DBUG_ENTER, DBUG_RETURN, st_io_cache::end_of_file, st_table::file, SQL_SELECT::file, SQL_SELECT::head, st_filesort_info::io_cache, my_free, MYF, SQL_SELECT::read_tables, SQL_SELECT::records, handler::ref_length, and st_table::sort.
Referenced by add_ref_to_table_cond(), mysql_delete(), JOIN::optimize(), and prepare_simple_select().
00867 { 00868 SQL_SELECT *select; 00869 DBUG_ENTER("make_select"); 00870 00871 *error=0; 00872 00873 if (!conds && !allow_null_cond) 00874 DBUG_RETURN(0); 00875 if (!(select= new SQL_SELECT)) 00876 { 00877 *error= 1; // out of memory 00878 DBUG_RETURN(0); /* purecov: inspected */ 00879 } 00880 select->read_tables=read_tables; 00881 select->const_tables=const_tables; 00882 select->head=head; 00883 select->cond=conds; 00884 00885 if (head->sort.io_cache) 00886 { 00887 select->file= *head->sort.io_cache; 00888 select->records=(ha_rows) (select->file.end_of_file/ 00889 head->file->ref_length); 00890 my_free((gptr) (head->sort.io_cache),MYF(0)); 00891 head->sort.io_cache=0; 00892 } 00893 DBUG_RETURN(select); 00894 }
Here is the caller graph for this function:
Definition at line 7408 of file opt_range.cc.
References st_key_part::null_bit, and st_key_part::store_length.
Referenced by get_quick_keys().
07409 { 07410 for (const char *end=key+length ; 07411 key < end; 07412 key+= key_part++->store_length) 07413 { 07414 if (key_part->null_bit && *key) 07415 return 1; 07416 } 07417 return 0; 07418 }
Here is the caller graph for this function:
Definition at line 10698 of file opt_range.cc.
References DBUG_FILE, dbug_tmp_restore_column_map(), dbug_tmp_use_all_columns(), st_key_part::field, key_end(), st_key_part::length, my_charset_bin, MYSQL_TYPE_BIT, st_table::read_set, Field::real_maybe_null(), Field::set_key_image(), st_key_part::store_length, store_length(), Field::table, Field::type(), Field::val_int_as_str(), Field::val_str(), and st_table::write_set.
Referenced by QUICK_RANGE_SELECT::dbug_dump().
10699 { 10700 char buff[1024]; 10701 const char *key_end= key+used_length; 10702 String tmp(buff,sizeof(buff),&my_charset_bin); 10703 uint store_length; 10704 TABLE *table= key_part->field->table; 10705 my_bitmap_map *old_write_set, *old_read_set; 10706 old_write_set= dbug_tmp_use_all_columns(table, table->write_set); 10707 old_read_set= dbug_tmp_use_all_columns(table, table->read_set); 10708 10709 for (; key < key_end; key+=store_length, key_part++) 10710 { 10711 Field *field= key_part->field; 10712 store_length= key_part->store_length; 10713 10714 if (field->real_maybe_null()) 10715 { 10716 if (*key) 10717 { 10718 fwrite("NULL",sizeof(char),4,DBUG_FILE); 10719 continue; 10720 } 10721 key++; // Skip null byte 10722 store_length--; 10723 } 10724 field->set_key_image((char*) key, key_part->length); 10725 if (field->type() == MYSQL_TYPE_BIT) 10726 (void) field->val_int_as_str(&tmp, 1); 10727 else 10728 field->val_str(&tmp); 10729 fwrite(tmp.ptr(),sizeof(char),tmp.length(),DBUG_FILE); 10730 if (key+store_length < key_end) 10731 fputc('/',DBUG_FILE); 10732 } 10733 dbug_tmp_restore_column_map(table->write_set, old_write_set); 10734 dbug_tmp_restore_column_map(table->read_set, old_read_set); 10735 }
Here is the call graph for this function:
Here is the caller graph for this function:
| static void print_quick | ( | QUICK_SELECT_I * | quick, | |
| const key_map * | needed_reg | |||
| ) | [static] |
Definition at line 10738 of file opt_range.cc.
References DBUG_ENTER, DBUG_FILE, DBUG_LOCK_FILE, dbug_tmp_restore_column_map(), dbug_tmp_use_all_columns(), DBUG_UNLOCK_FILE, DBUG_VOID_RETURN, MAX_KEY, Bitmap< 64 >::print(), quick, st_table::read_set, TRUE, and st_table::write_set.
Referenced by SQL_SELECT::test_quick_select().
10739 { 10740 char buf[MAX_KEY/8+1]; 10741 TABLE *table; 10742 my_bitmap_map *old_read_map, *old_write_map; 10743 DBUG_ENTER("print_quick"); 10744 if (!quick) 10745 DBUG_VOID_RETURN; 10746 DBUG_LOCK_FILE; 10747 10748 table= quick->head; 10749 old_read_map= dbug_tmp_use_all_columns(table, table->read_set); 10750 old_write_map= dbug_tmp_use_all_columns(table, table->write_set); 10751 quick->dbug_dump(0, TRUE); 10752 dbug_tmp_restore_column_map(table->read_set, old_read_map); 10753 dbug_tmp_restore_column_map(table->write_set, old_write_map); 10754 10755 fprintf(DBUG_FILE,"other_keys: 0x%s:\n", needed_reg->print(buf)); 10756 10757 DBUG_UNLOCK_FILE; 10758 DBUG_VOID_RETURN; 10759 }
Here is the call graph for this function:
Here is the caller graph for this function:
| static void print_ror_scans_arr | ( | TABLE * | table, | |
| const char * | msg, | |||
| struct st_ror_scan_info ** | start, | |||
| struct st_ror_scan_info ** | end | |||
| ) | [static] |
Definition at line 10668 of file opt_range.cc.
References String::append(), DBUG_ENTER, DBUG_PRINT, DBUG_VOID_RETURN, st_table::key_info, String::length(), my_charset_bin, st_key::name, String::ptr(), start(), and STRING_WITH_LEN.
Referenced by get_best_covering_ror_intersect(), get_best_ror_intersect(), and TRP_ROR_INTERSECT::make_quick().
10671 { 10672 DBUG_ENTER("print_ror_scans_arr"); 10673 10674 char buff[1024]; 10675 String tmp(buff,sizeof(buff),&my_charset_bin); 10676 tmp.length(0); 10677 for (;start != end; start++) 10678 { 10679 if (tmp.length()) 10680 tmp.append(','); 10681 tmp.append(table->key_info[(*start)->keynr].name); 10682 } 10683 if (!tmp.length()) 10684 tmp.append(STRING_WITH_LEN("(empty)")); 10685 DBUG_PRINT("info", ("ROR key scans (%s): %s", msg, tmp.ptr())); 10686 DBUG_VOID_RETURN; 10687 }
Here is the call graph for this function:
Here is the caller graph for this function:
| static void print_rowid | ( | byte * | val, | |
| int | len | |||
| ) | [static] |
Definition at line 10762 of file opt_range.cc.
References DBUG_FILE, DBUG_LOCK_FILE, and DBUG_UNLOCK_FILE.
10763 { 10764 byte *pb; 10765 DBUG_LOCK_FILE; 10766 fputc('\"', DBUG_FILE); 10767 for (pb= val; pb!= val + len; ++pb) 10768 fprintf(DBUG_FILE, "%c", *pb); 10769 fprintf(DBUG_FILE, "\", hex: "); 10770 10771 for (pb= val; pb!= val + len; ++pb) 10772 fprintf(DBUG_FILE, "%x ", *pb); 10773 fputc('\n', DBUG_FILE); 10774 DBUG_UNLOCK_FILE; 10775 }
| static void print_sel_tree | ( | PARAM * | param, | |
| SEL_TREE * | tree, | |||
| key_map * | tree_map, | |||
| const char * | msg | |||
| ) | [static] |
Definition at line 10637 of file opt_range.cc.
References String::append(), DBUG_ENTER, DBUG_PRINT, DBUG_VOID_RETURN, Bitmap< 64 >::is_set(), key, st_table::key_info, RANGE_OPT_PARAM::keys, SEL_TREE::keys, String::length(), my_charset_bin, st_key::name, String::ptr(), RANGE_OPT_PARAM::real_keynr, STRING_WITH_LEN, and RANGE_OPT_PARAM::table.
Referenced by get_best_disjunct_quick(), and get_key_scans_params().
10639 { 10640 SEL_ARG **key,**end; 10641 int idx; 10642 char buff[1024]; 10643 DBUG_ENTER("print_sel_tree"); 10644 10645 String tmp(buff,sizeof(buff),&my_charset_bin); 10646 tmp.length(0); 10647 for (idx= 0,key=tree->keys, end=key+param->keys ; 10648 key != end ; 10649 key++,idx++) 10650 { 10651 if (tree_map->is_set(idx)) 10652 { 10653 uint keynr= param->real_keynr[idx]; 10654 if (tmp.length()) 10655 tmp.append(','); 10656 tmp.append(param->table->key_info[keynr].name); 10657 } 10658 } 10659 if (!tmp.length()) 10660 tmp.append(STRING_WITH_LEN("(empty)")); 10661 10662 DBUG_PRINT("info", ("SEL_TREE %p (%s) scans:%s", tree, msg, tmp.ptr())); 10663 10664 DBUG_VOID_RETURN; 10665 }
Here is the call graph for this function:
Here is the caller graph for this function:
Definition at line 6630 of file opt_range.cc.
References SEL_ARG::BLACK, SEL_ARG::color, key, SEL_ARG::left, left_rotate(), SEL_ARG::parent, SEL_ARG::RED, SEL_ARG::right, right_rotate(), and x.
06631 { 06632 SEL_ARG *x,*w; 06633 root->parent=0; 06634 06635 x= key; 06636 while (x != root && x->color == SEL_ARG::BLACK) 06637 { 06638 if (x == par->left) 06639 { 06640 w=par->right; 06641 if (w->color == SEL_ARG::RED) 06642 { 06643 w->color=SEL_ARG::BLACK; 06644 par->color=SEL_ARG::RED; 06645 left_rotate(&root,par); 06646 w=par->right; 06647 } 06648 if (w->left->color == SEL_ARG::BLACK && w->right->color == SEL_ARG::BLACK) 06649 { 06650 w->color=SEL_ARG::RED; 06651 x=par; 06652 } 06653 else 06654 { 06655 if (w->right->color == SEL_ARG::BLACK) 06656 { 06657 w->left->color=SEL_ARG::BLACK; 06658 w->color=SEL_ARG::RED; 06659 right_rotate(&root,w); 06660 w=par->right; 06661 } 06662 w->color=par->color; 06663 par->color=SEL_ARG::BLACK; 06664 w->right->color=SEL_ARG::BLACK; 06665 left_rotate(&root,par); 06666 x=root; 06667 break; 06668 } 06669 } 06670 else 06671 { 06672 w=par->left; 06673 if (w->color == SEL_ARG::RED) 06674 { 06675 w->color=SEL_ARG::BLACK; 06676 par->color=SEL_ARG::RED; 06677 right_rotate(&root,par); 06678 w=par->left; 06679 } 06680 if (w->right->color == SEL_ARG::BLACK && w->left->color == SEL_ARG::BLACK) 06681 { 06682 w->color=SEL_ARG::RED; 06683 x=par; 06684 } 06685 else 06686 { 06687 if (w->left->color == SEL_ARG::BLACK) 06688 { 06689 w->right->color=SEL_ARG::BLACK; 06690 w->color=SEL_ARG::RED; 06691 left_rotate(&root,w); 06692 w=par->left; 06693 } 06694 w->color=par->color; 06695 par->color=SEL_ARG::BLACK; 06696 w->left->color=SEL_ARG::BLACK; 06697 right_rotate(&root,par); 06698 x=root; 06699 break; 06700 } 06701 } 06702 par=x->parent; 06703 } 06704 x->color=SEL_ARG::BLACK; 06705 return root; 06706 }
Here is the call graph for this function:
| static bool remove_nonrange_trees | ( | RANGE_OPT_PARAM * | param, | |
| SEL_TREE * | tree | |||
| ) | [static] |
Definition at line 5799 of file opt_range.cc.
References Bitmap< 64 >::clear_bit(), FALSE, SEL_TREE::keys, RANGE_OPT_PARAM::keys, SEL_TREE::keys_map, NULL, SEL_ARG::part, and TRUE.
Referenced by tree_or().
05800 { 05801 bool res= FALSE; 05802 for (uint i=0; i < param->keys; i++) 05803 { 05804 if (tree->keys[i]) 05805 { 05806 if (tree->keys[i]->part) 05807 { 05808 tree->keys[i]= NULL; 05809 tree->keys_map.clear_bit(i); 05810 } 05811 else 05812 res= TRUE; 05813 } 05814 } 05815 return !res; 05816 }
Here is the call graph for this function:
Here is the caller graph for this function:
Definition at line 6553 of file opt_range.cc.
References SEL_ARG::left, null_element, SEL_ARG::parent, SEL_ARG::parent_ptr(), and SEL_ARG::right.
06554 { 06555 SEL_ARG *y=leaf->left; 06556 leaf->left=y->right; 06557 if (y->right != &null_element) 06558 y->right->parent=leaf; 06559 if (!(y->parent=leaf->parent)) 06560 *root=y; 06561 else 06562 *leaf->parent_ptr()=y; 06563 y->right=leaf; 06564 leaf->parent=y; 06565 }
Here is the call graph for this function:
| static bool ror_intersect_add | ( | ROR_INTERSECT_INFO * | info, | |
| ROR_SCAN_INFO * | ror_scan, | |||
| bool | is_cpk_scan | |||
| ) | [static] |
Definition at line 4162 of file opt_range.cc.
References bitmap_is_subset(), bitmap_union(), st_ror_scan_info::covered_fields, ROR_INTERSECT_INFO::covered_fields, DBUG_ENTER, DBUG_PRINT, DBUG_RETURN, double2rows, FALSE, get_sweep_read_cost(), st_ror_scan_info::index_read_cost, ROR_INTERSECT_INFO::index_records, ROR_INTERSECT_INFO::index_scan_costs, ROR_INTERSECT_INFO::is_covering, st_table::key_info, st_ror_scan_info::keynr, PARAM::needed_fields, ROR_INTERSECT_INFO::out_rows, ROR_INTERSECT_INFO::param, st_table::quick_rows, ror_scan_selectivity(), rows2double, RANGE_OPT_PARAM::table, TIME_FOR_COMPARE_ROWID, ROR_INTERSECT_INFO::total_cost, and TRUE.
Referenced by get_best_ror_intersect().
04164 { 04165 double selectivity_mult= 1.0; 04166 04167 DBUG_ENTER("ror_intersect_add"); 04168 DBUG_PRINT("info", ("Current out_rows= %g", info->out_rows)); 04169 DBUG_PRINT("info", ("Adding scan on %s", 04170 info->param->table->key_info[ror_scan->keynr].name)); 04171 DBUG_PRINT("info", ("is_cpk_scan=%d",is_cpk_scan)); 04172 04173 selectivity_mult = ror_scan_selectivity(info, ror_scan); 04174 if (selectivity_mult == 1.0) 04175 { 04176 /* Don't add this scan if it doesn't improve selectivity. */ 04177 DBUG_PRINT("info", ("The scan doesn't improve selectivity.")); 04178 DBUG_RETURN(FALSE); 04179 } 04180 04181 info->out_rows *= selectivity_mult; 04182 DBUG_PRINT("info", ("info->total_cost= %g", info->total_cost)); 04183 04184 if (is_cpk_scan) 04185 { 04186 /* 04187 CPK scan is used to filter out rows. We apply filtering for 04188 each record of every scan. Assuming 1/TIME_FOR_COMPARE_ROWID 04189 per check this gives us: 04190 */ 04191 info->index_scan_costs += rows2double(info->index_records) / 04192 TIME_FOR_COMPARE_ROWID; 04193 } 04194 else 04195 { 04196 info->index_records += info->param->table->quick_rows[ror_scan->keynr]; 04197 info->index_scan_costs += ror_scan->index_read_cost; 04198 bitmap_union(&info->covered_fields, &ror_scan->covered_fields); 04199 if (!info->is_covering && bitmap_is_subset(&info->param->needed_fields, 04200 &info->covered_fields)) 04201 { 04202 DBUG_PRINT("info", ("ROR-intersect is covering now")); 04203 info->is_covering= TRUE; 04204 } 04205 } 04206 04207 info->total_cost= info->index_scan_costs; 04208 DBUG_PRINT("info", ("info->total_cost: %g", info->total_cost)); 04209 if (!info->is_covering) 04210 { 04211 info->total_cost += 04212 get_sweep_read_cost(info->param, double2rows(info->out_rows)); 04213 DBUG_PRINT("info", ("info->total_cost= %g", info->total_cost)); 04214 } 04215 DBUG_PRINT("info", ("New out_rows: %g", info->out_rows)); 04216 DBUG_PRINT("info", ("New cost: %g, %scovering", info->total_cost, 04217 info->is_covering?"" : "non-")); 04218 DBUG_RETURN(TRUE); 04219 }
Here is the call graph for this function:
Here is the caller graph for this function:
| void ror_intersect_cpy | ( | ROR_INTERSECT_INFO * | dst, | |
| const ROR_INTERSECT_INFO * | src | |||
| ) |
Definition at line 3950 of file opt_range.cc.
References st_bitmap::bitmap, ROR_INTERSECT_INFO::covered_fields, ROR_INTERSECT_INFO::index_records, ROR_INTERSECT_INFO::index_scan_costs, ROR_INTERSECT_INFO::is_covering, memcpy, no_bytes_in_map, ROR_INTERSECT_INFO::out_rows, ROR_INTERSECT_INFO::param, and ROR_INTERSECT_INFO::total_cost.
Referenced by get_best_ror_intersect().
03951 { 03952 dst->param= src->param; 03953 memcpy(dst->covered_fields.bitmap, src->covered_fields.bitmap, 03954 no_bytes_in_map(&src->covered_fields)); 03955 dst->out_rows= src->out_rows; 03956 dst->is_covering= src->is_covering; 03957 dst->index_records= src->index_records; 03958 dst->index_scan_costs= src->index_scan_costs; 03959 dst->total_cost= src->total_cost; 03960 }
Here is the caller graph for this function:
| static ROR_INTERSECT_INFO* ror_intersect_init | ( | const PARAM * | param | ) | [static] |
Definition at line 3928 of file opt_range.cc.
References alloc_root(), bitmap_clear_all, bitmap_init(), ROR_INTERSECT_INFO::covered_fields, FALSE, st_table_share::fields, PARAM::fields_bitmap_size, st_table::file, ROR_INTERSECT_INFO::index_records, ROR_INTERSECT_INFO::index_scan_costs, info, ROR_INTERSECT_INFO::is_covering, RANGE_OPT_PARAM::mem_root, NULL, ROR_INTERSECT_INFO::out_rows, ROR_INTERSECT_INFO::param, ha_statistics::records, st_table::s, handler::stats, and RANGE_OPT_PARAM::table.
Referenced by get_best_ror_intersect().
03929 { 03930 ROR_INTERSECT_INFO *info; 03931 my_bitmap_map* buf; 03932 if (!(info= (ROR_INTERSECT_INFO*)alloc_root(param->mem_root, 03933 sizeof(ROR_INTERSECT_INFO)))) 03934 return NULL; 03935 info->param= param; 03936 if (!(buf= (my_bitmap_map*) alloc_root(param->mem_root, 03937 param->fields_bitmap_size))) 03938 return NULL; 03939 if (bitmap_init(&info->covered_fields, buf, param->table->s->fields, 03940 FALSE)) 03941 return NULL; 03942 info->is_covering= FALSE; 03943 info->index_scan_costs= 0.0; 03944 info->index_records= 0; 03945 info->out_rows= param->table->file->stats.records; 03946 bitmap_clear_all(&info->covered_fields); 03947 return info; 03948 }
Here is the call graph for this function:
Here is the caller graph for this function:
| static double ror_scan_selectivity | ( | const ROR_INTERSECT_INFO * | info, | |
| const ROR_SCAN_INFO * | scan | |||
| ) | [static] |
Definition at line 4054 of file opt_range.cc.
References bitmap_is_set(), ROR_INTERSECT_INFO::covered_fields, DBUG_ENTER, DBUG_PRINT, DBUG_RETURN, st_key_part_info::fieldnr, st_table::file, st_key_range::flag, HA_POS_ERROR, HA_READ_AFTER_KEY, HA_READ_KEY_EXACT, st_key_range::key, st_table::key_info, st_key::key_part, st_ror_scan_info::keynr, st_key_range::length, MAX_FIELD_WIDTH, MAX_KEY_LENGTH, SEL_ARG::next_key_part, NULL, ROR_INTERSECT_INFO::param, SEL_ARG::part, st_table::quick_rows, records, ha_statistics::records, rows2double, st_ror_scan_info::sel_arg, handler::stats, st_key_part_info::store_length, SEL_ARG::store_min(), RANGE_OPT_PARAM::table, and test.
Referenced by ror_intersect_add().
04056 { 04057 double selectivity_mult= 1.0; 04058 KEY_PART_INFO *key_part= info->param->table->key_info[scan->keynr].key_part; 04059 byte key_val[MAX_KEY_LENGTH+MAX_FIELD_WIDTH]; /* key values tuple */ 04060 char *key_ptr= (char*) key_val; 04061 SEL_ARG *sel_arg, *tuple_arg= NULL; 04062 bool cur_covered; 04063 bool prev_covered= test(bitmap_is_set(&info->covered_fields, 04064 key_part->fieldnr-1)); 04065 key_range min_range; 04066 key_range max_range; 04067 min_range.key= (byte*) key_val; 04068 min_range.flag= HA_READ_KEY_EXACT; 04069 max_range.key= (byte*) key_val; 04070 max_range.flag= HA_READ_AFTER_KEY; 04071 ha_rows prev_records= info->param->table->file->stats.records; 04072 DBUG_ENTER("ror_intersect_selectivity"); 04073 04074 for (sel_arg= scan->sel_arg; sel_arg; 04075 sel_arg= sel_arg->next_key_part) 04076 { 04077 DBUG_PRINT("info",("sel_arg step")); 04078 cur_covered= test(bitmap_is_set(&info->covered_fields, 04079 key_part[sel_arg->part].fieldnr-1)); 04080 if (cur_covered != prev_covered) 04081 { 04082 /* create (part1val, ..., part{n-1}val) tuple. */ 04083 ha_rows records; 04084 if (!tuple_arg) 04085 { 04086 tuple_arg= scan->sel_arg; 04087 /* Here we use the length of the first key part */ 04088 tuple_arg->store_min(key_part->store_length, &key_ptr, 0); 04089 } 04090 while (tuple_arg->next_key_part != sel_arg) 04091 { 04092 tuple_arg= tuple_arg->next_key_part; 04093 tuple_arg->store_min(key_part[tuple_arg->part].store_length, &key_ptr, 0); 04094 } 04095 min_range.length= max_range.length= ((char*) key_ptr - (char*) key_val); 04096 records= (info->param->table->file-> 04097 records_in_range(scan->keynr, &min_range, &max_range)); 04098 if (cur_covered) 04099 { 04100 /* uncovered -> covered */ 04101 double tmp= rows2double(records)/rows2double(prev_records); 04102 DBUG_PRINT("info", ("Selectivity multiplier: %g", tmp)); 04103 selectivity_mult *= tmp; 04104 prev_records= HA_POS_ERROR; 04105 } 04106 else 04107 { 04108 /* covered -> uncovered */ 04109 prev_records= records; 04110 } 04111 } 04112 prev_covered= cur_covered; 04113 } 04114 if (!prev_covered) 04115 { 04116 double tmp= rows2double(info->param->table->quick_rows[scan->keynr]) / 04117 rows2double(prev_records); 04118 DBUG_PRINT("info", ("Selectivity multiplier: %g", tmp)); 04119 selectivity_mult *= tmp; 04120 } 04121 DBUG_PRINT("info", ("Returning multiplier: %g", selectivity_mult)); 04122 DBUG_RETURN(selectivity_mult); 04123 }
Here is the call graph for this function:
Here is the caller graph for this function:
Definition at line 5611 of file opt_range.cc.
Referenced by get_mm_parts().
05612 { 05613 SEL_ARG *root,**key_link; 05614 05615 if (!key1) 05616 return key2; 05617 if (!key2) 05618 return key1; 05619 05620 key_link= &root; 05621 while (key1 && key2) 05622 { 05623 if (key1->part < key2->part) 05624 { 05625 *key_link= key1; 05626 key_link= &key1->next_key_part; 05627 key1=key1->next_key_part; 05628 } 05629 else 05630 { 05631 *key_link= key2; 05632 key_link= &key2->next_key_part; 05633 key2=key2->next_key_part; 05634 } 05635 } 05636 *key_link=key1 ? key1 : key2; 05637 return root; 05638 }
Here is the caller graph for this function:
Definition at line 1564 of file opt_range.cc.
References cmp, Field::key_cmp(), NEAR_MAX, NEAR_MIN, NO_MAX_RANGE, NO_MIN_RANGE, and Field::real_maybe_null().
Referenced by SEL_ARG::cmp_max_to_max(), SEL_ARG::cmp_max_to_min(), SEL_ARG::cmp_min_to_max(), and SEL_ARG::cmp_min_to_min().
01565 { 01566 int cmp; 01567 /* First check if there was a compare to a min or max element */ 01568 if (a_flag & (NO_MIN_RANGE | NO_MAX_RANGE)) 01569 { 01570 if ((a_flag & (NO_MIN_RANGE | NO_MAX_RANGE)) == 01571 (b_flag & (NO_MIN_RANGE | NO_MAX_RANGE))) 01572 return 0; 01573 return (a_flag & NO_MIN_RANGE) ? -1 : 1; 01574 } 01575 if (b_flag & (NO_MIN_RANGE | NO_MAX_RANGE)) 01576 return (b_flag & NO_MIN_RANGE) ? 1 : -1; 01577 01578 if (field->real_maybe_null()) // If null is part of key 01579 { 01580 if (*a != *b) 01581 { 01582 return *a ? -1 : 1; 01583 } 01584 if (*a) 01585 goto end; // NULL where equal 01586 a++; b++; // Skip NULL marker 01587 } 01588 cmp=field->key_cmp((byte*) a,(byte*) b); 01589 if (cmp) return cmp < 0 ? -1 : 1; // The values differed 01590 01591 // Check if the compared equal arguments was defined with open/closed range 01592 end: 01593 if (a_flag & (NEAR_MIN | NEAR_MAX)) 01594 { 01595 if ((a_flag & (NEAR_MIN | NEAR_MAX)) == (b_flag & (NEAR_MIN | NEAR_MAX))) 01596 return 0; 01597 if (!(b_flag & (NEAR_MIN | NEAR_MAX))) 01598 return (a_flag & NEAR_MIN) ? 2 : -2; 01599 return (a_flag & NEAR_MIN) ? 1 : -1; 01600 } 01601 if (b_flag & (NEAR_MIN | NEAR_MAX)) 01602 return (b_flag & NEAR_MIN) ? -2 : 2; 01603 return 0; // The elements where equal 01604 }
Here is the call graph for this function:
Here is the caller graph for this function:
| bool sel_trees_can_be_ored | ( | SEL_TREE * | tree1, | |
| SEL_TREE * | tree2, | |||
| RANGE_OPT_PARAM * | param | |||
| ) |
Definition at line 5716 of file opt_range.cc.
References DBUG_ENTER, DBUG_RETURN, FALSE, Bitmap< 64 >::intersect(), Bitmap< 64 >::is_clear_all(), Bitmap< 64 >::is_set(), key1, key2, SEL_TREE::keys, RANGE_OPT_PARAM::keys, SEL_TREE::keys_map, and TRUE.
Referenced by SEL_IMERGE::or_sel_tree_with_checks(), and tree_or().
05718 { 05719 key_map common_keys= tree1->keys_map; 05720 DBUG_ENTER("sel_trees_can_be_ored"); 05721 common_keys.intersect(tree2->keys_map); 05722 05723 if (common_keys.is_clear_all()) 05724 DBUG_RETURN(FALSE); 05725 05726 /* trees have a common key, check if they refer to same key part */ 05727 SEL_ARG **key1,**key2; 05728 for (uint key_no=0; key_no < param->keys; key_no++) 05729 { 05730 if (common_keys.is_set(key_no)) 05731 { 05732 key1= tree1->keys + key_no; 05733 key2= tree2->keys + key_no; 05734 if ((*key1)->part == (*key2)->part) 05735 { 05736 DBUG_RETURN(TRUE); 05737 } 05738 } 05739 } 05740 DBUG_RETURN(FALSE); 05741 }
Here is the call graph for this function:
Here is the caller graph for this function:
| static SEL_TREE * tree_and | ( | RANGE_OPT_PARAM * | param, | |
| SEL_TREE * | tree1, | |||
| SEL_TREE * | tree2 | |||
| ) | [static] |
Definition at line 5646 of file opt_range.cc.
References SEL_TREE::ALWAYS, Bitmap< 64 >::clear_all(), CLONE_KEY1_MAYBE, CLONE_KEY2_MAYBE, DBUG_ENTER, DBUG_RETURN, flag, imerge_list_and_list(), SEL_ARG::IMPOSSIBLE, SEL_TREE::IMPOSSIBLE, Bitmap< 64 >::is_clear_all(), SEL_TREE::KEY, key1, key2, key_and(), SEL_TREE::KEY_SMALLER, RANGE_OPT_PARAM::keys, SEL_TREE::MAYBE, and Bitmap< 64 >::set_bit().
Referenced by get_func_mm_tree(), and get_mm_tree().
05647 { 05648 DBUG_ENTER("tree_and"); 05649 if (!tree1) 05650 DBUG_RETURN(tree2); 05651 if (!tree2) 05652 DBUG_RETURN(tree1); 05653 if (tree1->type == SEL_TREE::IMPOSSIBLE || tree2->type == SEL_TREE::ALWAYS) 05654 DBUG_RETURN(tree1); 05655 if (tree2->type == SEL_TREE::IMPOSSIBLE || tree1->type == SEL_TREE::ALWAYS) 05656 DBUG_RETURN(tree2); 05657 if (tree1->type == SEL_TREE::MAYBE) 05658 { 05659 if (tree2->type == SEL_TREE::KEY) 05660 tree2->type=SEL_TREE::KEY_SMALLER; 05661 DBUG_RETURN(tree2); 05662 } 05663 if (tree2->type == SEL_TREE::MAYBE) 05664 { 05665 tree1->type=SEL_TREE::KEY_SMALLER; 05666 DBUG_RETURN(tree1); 05667 } 05668 05669 key_map result_keys; 05670 result_keys.clear_all(); 05671 /* Join the trees key per key */ 05672 SEL_ARG **key1,**key2,**end; 05673 for (key1= tree1->keys,key2= tree2->keys,end=key1+param->keys ; 05674 key1 != end ; key1++,key2++) 05675 { 05676 uint flag=0; 05677 if (*key1 || *key2) 05678 { 05679 if (*key1 && !(*key1)->simple_key()) 05680 flag|=CLONE_KEY1_MAYBE; 05681 if (*key2 && !(*key2)->simple_key()) 05682 flag|=CLONE_KEY2_MAYBE; 05683 *key1=key_and(*key1,*key2,flag); 05684 if (*key1 && (*key1)->type == SEL_ARG::IMPOSSIBLE) 05685 { 05686 tree1->type= SEL_TREE::IMPOSSIBLE; 05687 DBUG_RETURN(tree1); 05688 } 05689 result_keys.set_bit(key1 - tree1->keys); 05690 #ifdef EXTRA_DEBUG 05691 if (*key1) 05692 (*key1)->test_use_count(*key1); 05693 #endif 05694 } 05695 } 05696 tree1->keys_map= result_keys; 05697 /* dispose index_merge if there is a "range" option */ 05698 if (!result_keys.is_clear_all()) 05699 { 05700 tree1->merges.empty(); 05701 DBUG_RETURN(tree1); 05702 } 05703 05704 /* ok, both trees are index_merge trees */ 05705 imerge_list_and_list(&tree1->merges, &tree2->merges); 05706 DBUG_RETURN(tree1); 05707 }
Here is the call graph for this function:
Here is the caller graph for this function:
| static SEL_TREE * tree_or | ( | RANGE_OPT_PARAM * | param, | |
| SEL_TREE * | tree1, | |||
| SEL_TREE * | tree2 | |||
| ) | [static] |
Definition at line 5820 of file opt_range.cc.
References SEL_TREE::ALWAYS, Bitmap< 64 >::clear_all(), DBUG_ENTER, DBUG_RETURN, imerge_list_or_list(), imerge_list_or_tree(), SEL_TREE::IMPOSSIBLE, key1, key2, key_or(), RANGE_OPT_PARAM::keys, SEL_TREE::keys_map, SEL_TREE::MAYBE, SEL_TREE::merges, NULL, SEL_IMERGE::or_sel_tree(), List< T >::push_back(), RANGE_OPT_PARAM::remove_jump_scans, remove_nonrange_trees(), sel_trees_can_be_ored(), Bitmap< 64 >::set_bit(), swap_variables, and SEL_TREE::type.
Referenced by get_func_mm_tree(), get_mm_tree(), get_ne_mm_tree(), and SEL_IMERGE::or_sel_tree_with_checks().
05821 { 05822 DBUG_ENTER("tree_or"); 05823 if (!tree1 || !tree2) 05824 DBUG_RETURN(0); 05825 if (tree1->type == SEL_TREE::IMPOSSIBLE || tree2->type == SEL_TREE::ALWAYS) 05826 DBUG_RETURN(tree2); 05827 if (tree2->type == SEL_TREE::IMPOSSIBLE || tree1->type == SEL_TREE::ALWAYS) 05828 DBUG_RETURN(tree1); 05829 if (tree1->type == SEL_TREE::MAYBE) 05830 DBUG_RETURN(tree1); // Can't use this 05831 if (tree2->type == SEL_TREE::MAYBE) 05832 DBUG_RETURN(tree2); 05833 05834 SEL_TREE *result= 0; 05835 key_map result_keys; 05836 result_keys.clear_all(); 05837 if (sel_trees_can_be_ored(tree1, tree2, param)) 05838 { 05839 /* Join the trees key per key */ 05840 SEL_ARG **key1,**key2,**end; 05841 for (key1= tree1->keys,key2= tree2->keys,end= key1+param->keys ; 05842 key1 != end ; key1++,key2++) 05843 { 05844 *key1=key_or(*key1,*key2); 05845 if (*key1) 05846 { 05847 result=tree1; // Added to tree1 05848 result_keys.set_bit(key1 - tree1->keys); 05849 #ifdef EXTRA_DEBUG 05850 (*key1)->test_use_count(*key1); 05851 #endif 05852 } 05853 } 05854 if (result) 05855 result->keys_map= result_keys; 05856 } 05857 else 05858 { 05859 /* ok, two trees have KEY type but cannot be used without index merge */ 05860 if (tree1->merges.is_empty() && tree2->merges.is_empty()) 05861 { 05862 if (param->remove_jump_scans) 05863 { 05864 bool no_trees= remove_nonrange_trees(param, tree1); 05865 no_trees= no_trees || remove_nonrange_trees(param, tree2); 05866 if (no_trees) 05867 DBUG_RETURN(new SEL_TREE(SEL_TREE::ALWAYS)); 05868 } 05869 SEL_IMERGE *merge; 05870 /* both trees are "range" trees, produce new index merge structure */ 05871 if (!(result= new SEL_TREE()) || !(merge= new SEL_IMERGE()) || 05872 (result->merges.push_back(merge)) || 05873 (merge->or_sel_tree(param, tree1)) || 05874 (merge->or_sel_tree(param, tree2))) 05875 result= NULL; 05876 else 05877 result->type= tree1->type; 05878 } 05879 else if (!tree1->merges.is_empty() && !tree2->merges.is_empty()) 05880 { 05881 if (imerge_list_or_list(param, &tree1->merges, &tree2->merges)) 05882 result= new SEL_TREE(SEL_TREE::ALWAYS); 05883 else 05884 result= tree1; 05885 } 05886 else 05887 { 05888 /* one tree is index merge tree and another is range tree */ 05889 if (tree1->merges.is_empty()) 05890 swap_variables(SEL_TREE*, tree1, tree2); 05891 05892 if (param->remove_jump_scans && remove_nonrange_trees(param, tree2)) 05893 DBUG_RETURN(new SEL_TREE(SEL_TREE::ALWAYS)); 05894 /* add tree2 to tree1->merges, checking if it collapses to ALWAYS */ 05895 if (imerge_list_or_tree(param, &tree1->merges, tree2)) 05896 result= new SEL_TREE(SEL_TREE::ALWAYS); 05897 else 05898 result= tree1; 05899 } 05900 } 05901 DBUG_RETURN(result); 05902 }
Here is the call graph for this function:
Here is the caller graph for this function:
Variable Documentation
char is_null_string[2] = {1,0} [static] |
SEL_ARG null_element(SEL_ARG::IMPOSSIBLE) [static] |
Referenced by and_all_keys(), check_quick_keys(), SEL_ARG::clone(), eq_tree(), SEL_ARG::find_range(), SEL_ARG::first(), get_mm_leaf(), get_quick_keys(), SEL_ARG::insert(), key_and(), SEL_ARG::last(), left_rotate(), SEL_ARG::make_root(), right_rotate(), SEL_ARG::SEL_ARG(), and SEL_ARG::tree_delete().
Generated on Sat Sep 9 02:44:54 2006 for MySQL 5.1 by
1.4.7