109 #include "sql_parse.h"
110 #include "sql_partition.h"
112 #include "sql_base.h"
117 #include "filesort.h"
118 #include "sql_optimizer.h"
127 #define double2rows(x) ((ha_rows)(x))
129 static int sel_cmp(
Field *f,uchar *a,uchar *b,uint8 a_flag,uint8 b_flag);
131 static uchar is_null_string[2]= {1,0};
360 uint8 min_flag,max_flag,maybe_flag;
376 uchar *min_value,*max_value;
391 enum leaf_color { BLACK,RED } color;
402 enum Type { IMPOSSIBLE, ALWAYS, MAYBE, MAYBE_KEY, KEY_RANGE } type;
404 enum { MAX_SEL_ARGS = 16000 };
409 SEL_ARG(
Field *field, uint8 part, uchar *min_value, uchar *max_value,
410 uint8 min_flag, uint8 max_flag, uint8 maybe_flag);
417 :min_flag(0),elements(1),use_count(1),left(NULL),right(NULL),
418 next_key_part(0), color(BLACK), type(type_arg)
420 DBUG_ASSERT(type_arg == MAYBE_KEY || type_arg == IMPOSSIBLE);
422 inline bool is_same(
SEL_ARG *arg)
424 if (type != arg->type || part != arg->part)
426 if (type != KEY_RANGE)
428 return cmp_min_to_min(arg) == 0 && cmp_max_to_max(arg) == 0;
430 inline void merge_flags(
SEL_ARG *arg) { maybe_flag|=arg->maybe_flag; }
431 inline void maybe_smaller() { maybe_flag=1; }
433 inline bool is_null_interval() {
return maybe_null && max_value[0] == 1; }
434 inline int cmp_min_to_min(
SEL_ARG* arg)
436 return sel_cmp(field,min_value, arg->min_value, min_flag, arg->min_flag);
438 inline int cmp_min_to_max(
SEL_ARG* arg)
440 return sel_cmp(field,min_value, arg->max_value, min_flag, arg->max_flag);
442 inline int cmp_max_to_max(
SEL_ARG* arg)
444 return sel_cmp(field,max_value, arg->max_value, max_flag, arg->max_flag);
446 inline int cmp_max_to_min(
SEL_ARG* arg)
448 return sel_cmp(field,max_value, arg->min_value, max_flag, arg->min_flag);
452 uchar *new_min,*new_max;
453 uint8 flag_min,flag_max;
454 if (cmp_min_to_min(arg) >= 0)
456 new_min=min_value; flag_min=min_flag;
460 new_min=arg->min_value; flag_min=arg->min_flag;
462 if (cmp_max_to_max(arg) <= 0)
464 new_max=max_value; flag_max=max_flag;
468 new_max=arg->max_value; flag_max=arg->max_flag;
470 return new SEL_ARG(field, part, new_min, new_max, flag_min, flag_max,
471 test(maybe_flag && arg->maybe_flag));
475 return new SEL_ARG(field,part, min_value, arg->min_value,
476 min_flag, arg->min_flag & NEAR_MIN ? 0 : NEAR_MAX,
477 maybe_flag | arg->maybe_flag);
481 return new SEL_ARG(field, part, min_value, arg->max_value,
482 min_flag, arg->max_flag, maybe_flag | arg->maybe_flag);
488 if (cmp_min_to_min(arg) > 0)
490 min_value=arg->min_value; min_flag=arg->min_flag;
491 if ((max_flag & NO_MAX_RANGE) && (min_flag & NO_MIN_RANGE))
494 maybe_flag|=arg->maybe_flag;
499 if (cmp_max_to_max(arg) <= 0)
501 max_value=arg->max_value; max_flag=arg->max_flag;
502 if ((max_flag & NO_MAX_RANGE) && (min_flag & NO_MIN_RANGE))
505 maybe_flag|=arg->maybe_flag;
509 void copy_min_to_min(
SEL_ARG *arg)
511 min_value=arg->min_value; min_flag=arg->min_flag;
513 void copy_min_to_max(
SEL_ARG *arg)
515 max_value=arg->min_value;
516 max_flag=arg->min_flag & NEAR_MIN ? 0 : NEAR_MAX;
518 void copy_max_to_min(
SEL_ARG *arg)
520 min_value=arg->max_value;
521 min_flag=arg->max_flag & NEAR_MAX ? 0 : NEAR_MIN;
524 int store_min(uint length, uchar **min_key,uint min_key_flag)
527 if ((min_flag & GEOM_FLAG) ||
528 (!(min_flag & NO_MIN_RANGE) &&
529 !(min_key_flag & (NO_MIN_RANGE | NEAR_MIN))))
531 if (maybe_null && *min_value)
534 memset(*min_key+1, 0, length-1);
537 memcpy(*min_key,min_value,length);
544 int store_max(uint length, uchar **max_key, uint max_key_flag)
546 if (!(max_flag & NO_MAX_RANGE) &&
547 !(max_key_flag & (NO_MAX_RANGE | NEAR_MAX)))
549 if (maybe_null && *max_value)
552 memset(*max_key+1, 0, length-1);
555 memcpy(*max_key,max_value,length);
573 uint *range_key_flag,
577 uint res= key_tree->store_min(key[key_tree->part].store_length,
578 range_key, *range_key_flag);
579 *range_key_flag|= key_tree->min_flag;
581 if (key_tree->next_key_part &&
582 key_tree->next_key_part->type == SEL_ARG::KEY_RANGE &&
583 key_tree->part != last_part &&
584 key_tree->next_key_part->part == key_tree->part+1 &&
585 !(*range_key_flag & (NO_MIN_RANGE | NEAR_MIN)))
586 res+= key_tree->next_key_part->store_min_key(key,
596 uint *range_key_flag,
600 uint res=key_tree->store_max(key[key_tree->part].store_length,
601 range_key, *range_key_flag);
602 (*range_key_flag)|= key_tree->max_flag;
603 if (key_tree->next_key_part &&
604 key_tree->next_key_part->type == SEL_ARG::KEY_RANGE &&
605 key_tree->part != last_part &&
606 key_tree->next_key_part->part == key_tree->part+1 &&
607 !(*range_key_flag & (NO_MAX_RANGE | NEAR_MAX)))
608 res+= key_tree->next_key_part->store_max_key(key,
622 void test_use_count(
SEL_ARG *root);
627 inline bool simple_key()
629 return !next_key_part && elements == 1;
631 void increment_use_count(
long count)
635 next_key_part->use_count+=count;
636 for (
SEL_ARG *pos=next_key_part->first(); pos ; pos=pos->next)
637 if (pos->next_key_part)
638 pos->increment_use_count(count);
643 for (
SEL_ARG *pos=first(); pos ; pos=pos->next)
644 if (pos->next_key_part)
646 pos->next_key_part->use_count--;
647 pos->next_key_part->free_tree();
653 return parent->left ==
this ? &parent->left : &parent->right;
673 bool is_singlepoint()
const
679 if (min_flag || max_flag)
681 uchar *min_val= min_value;
682 uchar *max_val= max_value;
687 if (*min_val != *max_val)
695 return !field->key_cmp(min_val, max_val);
729 enum Type { IMPOSSIBLE, ALWAYS, MAYBE,
KEY, KEY_SMALLER } type;
730 SEL_TREE(
enum Type type_arg) :type(type_arg) {}
733 memset(keys, 0,
sizeof(keys));
789 table_map prev_tables;
790 table_map read_tables;
791 table_map current_table;
810 bool using_real_indexes;
817 bool remove_jump_scans;
823 uint real_keynr[MAX_KEY];
829 uchar min_key[MAX_KEY_LENGTH+MAX_FIELD_WIDTH],
830 max_key[MAX_KEY_LENGTH+MAX_FIELD_WIDTH];
833 uint alloced_sel_args;
834 bool force_default_mrr;
842 bool statement_should_be_aborted()
const
845 thd->is_fatal_error ||
847 alloced_sel_args > SEL_ARG::MAX_SEL_ARGS;
863 uint fields_bitmap_size;
869 uint *imerge_cost_buff;
870 uint imerge_cost_buff_size;
881 ORDER::enum_order order_direction;
895 Item_func::Functype
type,
Item *value,
896 Item_result cmp_type);
899 Item_func::Functype
type,
Item *value);
902 static bool is_key_scan_ror(
PARAM *param, uint
keynr, uint nparts);
903 static ha_rows check_quick_select(
PARAM *param, uint
idx,
bool index_only,
904 SEL_ARG *tree,
bool update_tbl_stats,
905 uint *mrr_flags, uint *bufsize,
908 SEL_ARG *key_tree, uint mrr_flags,
909 uint mrr_buf_size,
MEM_ROOT *alloc);
911 bool index_read_must_be_used,
912 bool update_tbl_stats,
926 static void print_ror_scans_arr(
TABLE *
table,
const char *
msg,
937 static inline void dbug_print_tree(
const char *tree_name,
941 void append_range(
String *out,
943 const uchar *min_key,
const uchar *max_key,
954 SEL_ARG *key_tree, uchar *min_key,uint min_key_flag,
955 uchar *max_key,uint max_key_flag);
957 static bool eq_ranges_exceeds_limit(
SEL_ARG *keypart_root, uint* count,
960 static SEL_ARG null_element(SEL_ARG::IMPOSSIBLE);
961 static bool null_part_in_key(
KEY_PART *key_part,
const uchar *key,
981 enum { PREALLOCED_TREES= 10};
983 SEL_TREE *trees_prealloced[PREALLOCED_TREES];
991 trees(&trees_prealloced[0]),
993 trees_end(trees + PREALLOCED_TREES)
1016 if (trees_next == trees_end)
1018 const int realloc_ratio= 2;
1019 uint old_elements= (trees_end - trees);
1020 uint old_size=
sizeof(
SEL_TREE**) * old_elements;
1021 uint new_size= old_size * realloc_ratio;
1023 if (!(new_trees= (
SEL_TREE**)alloc_root(param->mem_root, new_size)))
1025 memcpy(new_trees, trees, old_size);
1027 trees_next= trees + old_elements;
1028 trees_end= trees + old_elements * realloc_ratio;
1030 *(trees_next++)= tree;
1071 if (sel_trees_can_be_ored(*tree, new_tree, param))
1073 *tree = tree_or(param, *tree, new_tree);
1076 if (((*tree)->type == SEL_TREE::MAYBE) ||
1077 ((*tree)->type == SEL_TREE::ALWAYS))
1085 return or_sel_tree(param, new_tree);
1101 for (
SEL_TREE** tree= imerge->trees;
1102 tree != imerge->trees_next;
1105 if (or_sel_tree_with_checks(param, *tree))
1114 keys_map= arg->keys_map;
1116 for (uint idx= 0; idx < MAX_KEY; idx++)
1118 if ((keys[idx]= arg->keys[idx]))
1120 keys[idx]->use_count++;
1121 keys[idx]->increment_use_count(1);
1129 if (!merge || merge->trees == merge->trees_next)
1134 merges.push_back (merge);
1141 uint elements= (arg->trees_end - arg->trees);
1142 if (elements > PREALLOCED_TREES)
1145 if (!(trees= (
SEL_TREE **)alloc_root(param->mem_root, size)))
1149 trees= &trees_prealloced[0];
1152 trees_end= trees + elements;
1154 for (
SEL_TREE **tree = trees, **arg_tree= arg->trees; tree < trees_end;
1157 if (!(*tree=
new SEL_TREE(*arg_tree, param)))
1164 trees= &trees_prealloced[0];
1209 im1->push_back(imerge);
1211 return imerge->or_sel_imerge_with_checks(param, im2->head());
1227 DBUG_ENTER(
"imerge_list_or_tree");
1231 uint remaining_trees= im1->elements;
1232 while ((imerge= it++))
1239 if (--remaining_trees == 0)
1243 or_tree=
new SEL_TREE (tree, param);
1246 if (or_tree->keys_map.is_clear_all() && or_tree->merges.is_empty())
1250 int result_or= imerge->or_sel_tree_with_checks(param, or_tree);
1253 else if (result_or == -1)
1256 DBUG_ASSERT(remaining_trees == 0);
1257 DBUG_RETURN(im1->is_empty());
1272 table_map read_tables,
Item *conds,
1273 bool allow_null_cond,
1277 DBUG_ENTER(
"make_select");
1281 if (!conds && !allow_null_cond)
1288 select->read_tables=read_tables;
1289 select->const_tables=const_tables;
1293 if (head->sort.io_cache)
1295 select->file= *head->sort.io_cache;
1296 select->records=(ha_rows) (select->file.end_of_file/
1298 my_free(head->sort.io_cache);
1299 head->sort.io_cache=0;
1301 DBUG_RETURN(select);
1305 SQL_SELECT::SQL_SELECT() :
1306 quick(0), cond(0), icp_cond(0),
1307 free_cond(0), traced_before(false)
1313 void SQL_SELECT::cleanup()
1322 close_cached_file(&file);
1327 SQL_SELECT::~SQL_SELECT()
1332 #undef index // Fix for Unixware 7
1334 QUICK_SELECT_I::QUICK_SELECT_I()
1335 :max_used_key_length(0),
1339 QUICK_RANGE_SELECT::QUICK_RANGE_SELECT(THD *thd,
TABLE *
table, uint key_nr,
1340 bool no_alloc,
MEM_ROOT *parent_alloc,
1342 :free_file(0), cur_range(NULL), last_range(0),
1343 mrr_flags(0), mrr_buf_size(0), mrr_buf_desc(NULL),
1346 my_bitmap_map *bitmap;
1347 DBUG_ENTER(
"QUICK_RANGE_SELECT::QUICK_RANGE_SELECT");
1349 in_ror_merged_scan= 0;
1352 key_part_info= head->key_info[
index].key_part;
1353 my_init_dynamic_array(&ranges,
sizeof(
QUICK_RANGE*), 16, 16);
1356 mrr_buf_size= thd->variables.read_rnd_buff_size;
1358 if (!no_alloc && !parent_alloc)
1361 init_sql_alloc(&alloc, thd->variables.range_alloc_block_size, 0);
1362 thd->mem_root= &alloc;
1365 memset(&alloc, 0,
sizeof(alloc));
1370 if (!(bitmap= (my_bitmap_map*) my_malloc(head->s->column_bitmap_size,
1373 column_bitmap.bitmap= 0;
1377 bitmap_init(&column_bitmap, bitmap, head->s->fields, FALSE);
1382 void QUICK_RANGE_SELECT::need_sorted_output()
1384 mrr_flags |= HA_MRR_SORTED;
1388 int QUICK_RANGE_SELECT::init()
1390 DBUG_ENTER(
"QUICK_RANGE_SELECT::init");
1393 file->ha_index_or_rnd_end();
1398 void QUICK_RANGE_SELECT::range_end()
1401 file->ha_index_or_rnd_end();
1405 QUICK_RANGE_SELECT::~QUICK_RANGE_SELECT()
1407 DBUG_ENTER(
"QUICK_RANGE_SELECT::~QUICK_RANGE_SELECT");
1416 DBUG_PRINT(
"info", (
"Freeing separate handler %p (free: %d)", file,
1423 delete_dynamic(&ranges);
1424 free_root(&alloc,MYF(0));
1425 my_free(column_bitmap.bitmap);
1427 my_free(mrr_buf_desc);
1432 QUICK_INDEX_MERGE_SELECT::QUICK_INDEX_MERGE_SELECT(THD *thd_param,
1434 :unique(NULL), pk_quick_select(NULL), thd(thd_param)
1436 DBUG_ENTER(
"QUICK_INDEX_MERGE_SELECT::QUICK_INDEX_MERGE_SELECT");
1439 memset(&read_record, 0,
sizeof(read_record));
1440 init_sql_alloc(&alloc, thd->variables.range_alloc_block_size, 0);
1444 int QUICK_INDEX_MERGE_SELECT::init()
1446 DBUG_ENTER(
"QUICK_INDEX_MERGE_SELECT::init");
1450 int QUICK_INDEX_MERGE_SELECT::reset()
1452 DBUG_ENTER(
"QUICK_INDEX_MERGE_SELECT::reset");
1453 const int retval= read_keys_and_merge();
1454 DBUG_RETURN(retval);
1464 if (head->file->primary_key_is_clustered() &&
1465 quick_sel_range->index == head->s->primary_key)
1466 pk_quick_select= quick_sel_range;
1468 return quick_selects.push_back(quick_sel_range);
1472 QUICK_INDEX_MERGE_SELECT::~QUICK_INDEX_MERGE_SELECT()
1476 DBUG_ENTER(
"QUICK_INDEX_MERGE_SELECT::~QUICK_INDEX_MERGE_SELECT");
1479 while ((quick= quick_it++))
1481 quick_selects.delete_elements();
1482 delete pk_quick_select;
1484 end_read_record(&read_record);
1485 free_io_cache(head);
1486 free_root(&alloc,MYF(0));
1491 QUICK_ROR_INTERSECT_SELECT::QUICK_ROR_INTERSECT_SELECT(THD *thd_param,
1493 bool retrieve_full_rows,
1495 : cpk_quick(NULL), thd(thd_param), need_to_fetch_row(retrieve_full_rows),
1502 init_sql_alloc(&alloc, thd->variables.range_alloc_block_size, 0);
1504 memset(&alloc, 0,
sizeof(
MEM_ROOT));
1505 last_rowid= (uchar*) alloc_root(parent_alloc? parent_alloc : &alloc,
1520 int QUICK_ROR_INTERSECT_SELECT::init()
1522 DBUG_ENTER(
"QUICK_ROR_INTERSECT_SELECT::init");
1524 DBUG_RETURN(!last_rowid);
1550 int QUICK_RANGE_SELECT::init_ror_merged_scan(
bool reuse_handler)
1552 handler *save_file= file, *org_file;
1554 MY_BITMAP *
const save_read_set= head->read_set;
1555 MY_BITMAP *
const save_write_set= head->write_set;
1556 DBUG_ENTER(
"QUICK_RANGE_SELECT::init_ror_merged_scan");
1558 in_ror_merged_scan= 1;
1561 DBUG_PRINT(
"info", (
"Reusing handler %p", file));
1562 if (init() || reset())
1566 head->column_bitmaps_set(&column_bitmap, &column_bitmap);
1578 if (!(file= head->file->clone(head->s->normalized_path.str, thd->mem_root)))
1587 my_error(ER_OUT_OF_RESOURCES, MYF(0));
1592 head->column_bitmaps_set(&column_bitmap, &column_bitmap);
1597 if (init() || reset())
1604 last_rowid= file->ref;
1613 org_file= head->file;
1616 if (!head->no_keyread)
1617 head->mark_columns_used_by_index(index);
1619 head->file= org_file;
1620 bitmap_copy(&column_bitmap, head->read_set);
1627 head->column_bitmaps_set(save_read_set, save_write_set);
1632 head->column_bitmaps_set(save_read_set, save_write_set);
1649 int QUICK_ROR_INTERSECT_SELECT::init_ror_merged_scan(
bool reuse_handler)
1654 DBUG_ENTER(
"QUICK_ROR_INTERSECT_SELECT::init_ror_merged_scan");
1657 DBUG_ASSERT(!need_to_fetch_row || reuse_handler);
1658 if (!need_to_fetch_row && reuse_handler)
1665 int error= quick->init_ror_merged_scan(TRUE);
1668 quick->file->extra(HA_EXTRA_KEYREAD_PRESERVE_FIELDS);
1670 while ((quick= quick_it++))
1673 const MY_BITMAP *
const save_read_set= quick->head->read_set;
1674 const MY_BITMAP *
const save_write_set= quick->head->write_set;
1676 if ((error= quick->init_ror_merged_scan(FALSE)))
1678 quick->file->extra(HA_EXTRA_KEYREAD_PRESERVE_FIELDS);
1680 DBUG_ASSERT(quick->head->read_set == save_read_set);
1681 DBUG_ASSERT(quick->head->write_set == save_write_set);
1683 quick->record= head->record[0];
1687 if (need_to_fetch_row && (error= head->file->
ha_rnd_init(
false)))
1689 DBUG_PRINT(
"error", (
"ROR index_merge rnd_init call failed"));
1705 int QUICK_ROR_INTERSECT_SELECT::reset()
1707 DBUG_ENTER(
"QUICK_ROR_INTERSECT_SELECT::reset");
1708 if (!scans_inited && init_ror_merged_scan(TRUE))
1713 while ((quick= it++))
1737 return quick_selects.push_back(quick);
1740 QUICK_ROR_INTERSECT_SELECT::~QUICK_ROR_INTERSECT_SELECT()
1742 DBUG_ENTER(
"QUICK_ROR_INTERSECT_SELECT::~QUICK_ROR_INTERSECT_SELECT");
1743 quick_selects.delete_elements();
1745 free_root(&alloc,MYF(0));
1746 if (need_to_fetch_row && head->file->inited)
1752 QUICK_ROR_UNION_SELECT::QUICK_ROR_UNION_SELECT(THD *thd_param,
1754 : thd(thd_param), scans_inited(FALSE)
1760 init_sql_alloc(&alloc, thd->variables.range_alloc_block_size, 0);
1761 thd_param->mem_root= &alloc;
1778 static int QUICK_ROR_UNION_SELECT_queue_cmp(
void *arg, uchar *val1, uchar *val2)
1781 return self->head->file->cmp_ref(((
QUICK_SELECT_I*)val1)->last_rowid,
1798 int QUICK_ROR_UNION_SELECT::init()
1800 DBUG_ENTER(
"QUICK_ROR_UNION_SELECT::init");
1801 if (init_queue(&queue, quick_selects.elements, 0,
1802 FALSE , QUICK_ROR_UNION_SELECT_queue_cmp,
1805 memset(&queue, 0,
sizeof(
QUEUE));
1809 if (!(cur_rowid= (uchar*) alloc_root(&alloc, 2*head->file->
ref_length)))
1811 prev_rowid= cur_rowid + head->file->
ref_length;
1826 int QUICK_ROR_UNION_SELECT::reset()
1830 DBUG_ENTER(
"QUICK_ROR_UNION_SELECT::reset");
1831 have_prev_rowid= FALSE;
1835 while ((quick= it++))
1837 if (quick->init_ror_merged_scan(FALSE))
1842 queue_remove_all(&queue);
1848 while ((quick= it++))
1850 if ((error= quick->reset()))
1852 if ((error= quick->get_next()))
1854 if (error == HA_ERR_END_OF_FILE)
1858 quick->save_last_pos();
1859 queue_insert(&queue, (uchar*)quick);
1863 if (head->file->inited && (error= head->file->
ha_rnd_end()))
1865 DBUG_PRINT(
"error", (
"ROR index_merge rnd_end call failed"));
1870 DBUG_PRINT(
"error", (
"ROR index_merge rnd_init call failed"));
1879 QUICK_ROR_UNION_SELECT::push_quick_back(
QUICK_SELECT_I *quick_sel_range)
1881 return quick_selects.push_back(quick_sel_range);
1884 QUICK_ROR_UNION_SELECT::~QUICK_ROR_UNION_SELECT()
1886 DBUG_ENTER(
"QUICK_ROR_UNION_SELECT::~QUICK_ROR_UNION_SELECT");
1887 delete_queue(&queue);
1888 quick_selects.delete_elements();
1889 if (head->file->inited)
1891 free_root(&alloc,MYF(0));
1896 QUICK_RANGE::QUICK_RANGE()
1897 :min_key(0),max_key(0),min_length(0),max_length(0),
1898 flag(NO_MIN_RANGE | NO_MAX_RANGE),
1899 min_keypart_map(0), max_keypart_map(0)
1902 QUICK_RANGE::QUICK_RANGE(
const uchar *min_key_arg, uint min_length_arg,
1903 key_part_map min_keypart_map_arg,
1904 const uchar *max_key_arg, uint max_length_arg,
1905 key_part_map max_keypart_map_arg,
1909 min_length((uint16) min_length_arg),
1910 max_length((uint16) max_length_arg),
1911 flag((uint16) flag_arg),
1912 min_keypart_map(min_keypart_map_arg),
1913 max_keypart_map(max_keypart_map_arg)
1915 min_key=
static_cast<uchar*
>(sql_memdup(min_key_arg, min_length_arg + 1));
1916 max_key=
static_cast<uchar*
>(sql_memdup(max_key_arg, max_length_arg + 1));
1918 DBUG_ASSERT(min_key_arg != is_null_string);
1919 DBUG_ASSERT(max_key_arg != is_null_string);
1924 DBUG_ASSERT(arg.type != MAYBE_KEY);
1925 left=right= &null_element;
1928 min_flag=arg.min_flag;
1929 max_flag=arg.max_flag;
1930 maybe_flag=arg.maybe_flag;
1931 maybe_null=arg.maybe_null;
1934 min_value=arg.min_value;
1935 max_value=arg.max_value;
1936 next_key_part=arg.next_key_part;
1937 use_count=1; elements=1;
1941 inline void SEL_ARG::make_root()
1943 left=right= &null_element;
1946 use_count=0; elements=1;
1949 SEL_ARG::SEL_ARG(
Field *f,
const uchar *min_value_arg,
1950 const uchar *max_value_arg)
1951 :min_flag(0), max_flag(0), maybe_flag(0), maybe_null(f->real_maybe_null()),
1952 elements(1), use_count(1), field(f), min_value((uchar*) min_value_arg),
1953 max_value((uchar*) max_value_arg), next(NULL), prev(NULL),
1954 next_key_part(0), color(BLACK),
type(KEY_RANGE)
1956 left=right= &null_element;
1959 SEL_ARG::SEL_ARG(
Field *field_,uint8 part_,
1960 uchar *min_value_, uchar *max_value_,
1961 uint8 min_flag_,uint8 max_flag_,uint8 maybe_flag_)
1962 :min_flag(min_flag_),max_flag(max_flag_),maybe_flag(maybe_flag_),
1963 part(part_),maybe_null(field_->real_maybe_null()), elements(1),use_count(1),
1964 field(field_), min_value(min_value_), max_value(max_value_),
1965 next(NULL), prev(NULL), next_key_part(0), color(BLACK),
type(KEY_RANGE)
1967 left=right= &null_element;
1976 if (++param->alloced_sel_args > MAX_SEL_ARGS)
1979 if (type != KEY_RANGE)
1981 if (!(tmp=
new (param->mem_root)
SEL_ARG(type)))
1983 tmp->prev= *next_arg;
1984 (*next_arg)->next=tmp;
1986 tmp->part= this->part;
1990 if (!(tmp=
new (param->mem_root)
SEL_ARG(field,part, min_value,max_value,
1991 min_flag, max_flag, maybe_flag)))
1993 tmp->parent=new_parent;
1994 tmp->next_key_part=next_key_part;
1995 if (left != &null_element)
1996 if (!(tmp->left=left->clone(param, tmp, next_arg)))
1999 tmp->prev= *next_arg;
2000 (*next_arg)->next=tmp;
2003 if (right != &null_element)
2004 if (!(tmp->right= right->clone(param, tmp, next_arg)))
2007 increment_use_count(1);
2009 tmp->elements= this->elements;
2016 if (!next_arg->left)
2018 while (next_arg->left != &null_element)
2019 next_arg=next_arg->left;
2026 if (!next_arg->right)
2028 while (next_arg->right != &null_element)
2029 next_arg=next_arg->right;
2039 static int sel_cmp(
Field *field, uchar *a, uchar *b, uint8 a_flag,
2044 if (a_flag & (NO_MIN_RANGE | NO_MAX_RANGE))
2046 if ((a_flag & (NO_MIN_RANGE | NO_MAX_RANGE)) ==
2047 (b_flag & (NO_MIN_RANGE | NO_MAX_RANGE)))
2049 return (a_flag & NO_MIN_RANGE) ? -1 : 1;
2051 if (b_flag & (NO_MIN_RANGE | NO_MAX_RANGE))
2052 return (b_flag & NO_MIN_RANGE) ? 1 : -1;
2064 cmp=field->key_cmp(a , b);
2065 if (cmp)
return cmp < 0 ? -1 : 1;
2069 if (a_flag & (NEAR_MIN | NEAR_MAX))
2071 if ((a_flag & (NEAR_MIN | NEAR_MAX)) == (b_flag & (NEAR_MIN | NEAR_MAX)))
2073 if (!(b_flag & (NEAR_MIN | NEAR_MAX)))
2074 return (a_flag & NEAR_MIN) ? 2 : -2;
2075 return (a_flag & NEAR_MIN) ? 1 : -1;
2077 if (b_flag & (NEAR_MIN | NEAR_MAX))
2078 return (b_flag & NEAR_MIN) ? -2 : 2;
2085 SEL_ARG tmp_link,*next_arg,*root;
2086 next_arg= &tmp_link;
2087 if (!(root= clone(param, (
SEL_ARG *) 0, &next_arg)))
2090 tmp_link.next->prev=0;
2134 bool retrieve_full_rows,
2138 static void *
operator new(
size_t size,
MEM_ROOT *mem_root)
2139 {
return (
void*) alloc_root(mem_root, (uint) size); }
2140 static void operator delete(
void *ptr,
size_t size) { TRASH(ptr, size); }
2141 static void operator delete(
void *ptr,
MEM_ROOT *mem_root) { }
2174 : key(key_arg), key_idx(idx_arg), mrr_flags(mrr_flags_arg)
2181 DBUG_ENTER(
"TRP_RANGE::make_quick");
2183 if ((quick= get_quick_select(param, key_idx, key, mrr_flags, mrr_buf_size,
2186 quick->records= records;
2187 quick->read_time= read_cost;
2199 #ifdef OPTIMIZER_TRACE
2200 DBUG_ASSERT(param->using_real_indexes);
2201 const uint keynr_in_table= param->real_keynr[key_idx];
2203 const KEY &cur_key= param->table->key_info[keynr_in_table];
2206 trace_object->add_alnum(
"type",
"range_scan").
2207 add_utf8(
"index", cur_key.
name).add(
"rows", records);
2215 range_info.set_charset(system_charset_info);
2216 append_range_all_keyparts(&trace_range, NULL, &range_info, key, key_part);
2264 double index_scan_costs;
2273 #ifdef OPTIMIZER_TRACE
2274 trace_object->add_alnum(
"type",
"index_roworder_intersect").
2276 add(
"cost", read_cost).
2277 add(
"covering", is_covering).
2278 add(
"clustered_pk_scan", cpk_scan != NULL);
2283 cur_scan != last_scan;
2286 const KEY &cur_key= param->table->key_info[(*cur_scan)->keynr];
2290 trace_isect_idx.add_alnum(
"type",
"range_scan").
2291 add_utf8(
"index", cur_key.
name).add(
"rows", (*cur_scan)->records);
2294 for (
const SEL_ARG *current= (*cur_scan)->sel_arg;
2296 current= current->next)
2299 range_info.set_charset(system_charset_info);
2300 for (
const SEL_ARG *part= current;
2302 part= part->next_key_part)
2305 append_range(&range_info, cur_key_part,
2306 part->min_value, part->max_value,
2307 part->min_flag | part->max_flag);
2309 trace_range.add_utf8(range_info.ptr(), range_info.length());
2338 #ifdef OPTIMIZER_TRACE
2340 trace_object->add_alnum(
"type",
"index_roworder_union");
2343 current != last_ror;
2347 (*current)->trace_basic_info(param, &trp_info);
2375 #ifdef OPTIMIZER_TRACE
2377 trace_object->add_alnum(
"type",
"index_merge");
2380 current != range_scans_end;
2384 (*current)->trace_basic_info(param, &trp_info);
2402 bool have_agg_distinct;
2409 uint group_prefix_len;
2410 uint used_key_parts;
2411 uint group_key_parts;
2414 uchar key_infix[MAX_KEY_LENGTH];
2429 bool have_agg_distinct_arg,
2431 uint group_prefix_len_arg, uint used_key_parts_arg,
2432 uint group_key_parts_arg,
KEY *index_info_arg,
2433 uint index_arg, uint key_infix_len_arg,
2434 uchar *key_infix_arg,
2436 uint param_idx_arg, ha_rows quick_prefix_records_arg)
2437 : have_min(have_min_arg), have_max(have_max_arg),
2438 have_agg_distinct(have_agg_distinct_arg),
2439 min_max_arg_part(min_max_arg_part_arg),
2440 group_prefix_len(group_prefix_len_arg), used_key_parts(used_key_parts_arg),
2441 group_key_parts(group_key_parts_arg), index_info(index_info_arg),
2442 index(index_arg), key_infix_len(key_infix_len_arg), range_tree(tree_arg),
2443 index_tree(index_tree_arg), param_idx(param_idx_arg), is_index_scan(FALSE),
2447 memcpy(this->key_infix, key_infix_arg, key_infix_len);
2453 void use_index_scan() { is_index_scan= TRUE; }
2459 #ifdef OPTIMIZER_TRACE
2460 trace_object->add_alnum(
"type",
"index_group").
2461 add_utf8(
"index", index_info->
name);
2462 if (min_max_arg_part)
2463 trace_object->add_utf8(
"group_attribute",
2464 min_max_arg_part->field->field_name);
2466 trace_object->add_null(
"group_attribute");
2467 trace_object->add(
"min_aggregate", have_min).
2468 add(
"max_aggregate", have_max).
2469 add(
"distinct_aggregate", have_agg_distinct).
2470 add(
"rows", records).
2471 add(
"cost", read_cost);
2477 for (uint partno= 0; partno < used_key_parts; partno++)
2480 trace_keyparts.add_utf8(cur_key_part->field->field_name);
2489 range_info.set_charset(system_charset_info);
2490 append_range_all_keyparts(&trace_range, NULL,
2491 &range_info, index_tree, key_part);
2510 static int fill_used_fields_bitmap(
PARAM *param)
2512 TABLE *table= param->table;
2515 param->tmp_covered_fields.bitmap= 0;
2516 param->fields_bitmap_size= table->s->column_bitmap_size;
2517 if (!(tmp= (my_bitmap_map*) alloc_root(param->mem_root,
2518 param->fields_bitmap_size)) ||
2519 bitmap_init(¶m->needed_fields, tmp, table->s->fields, FALSE))
2522 bitmap_copy(¶m->needed_fields, table->read_set);
2523 bitmap_union(¶m->needed_fields, table->write_set);
2525 pk= param->table->s->primary_key;
2526 if (pk != MAX_KEY && param->table->file->primary_key_is_clustered())
2529 KEY_PART_INFO *key_part= param->table->key_info[pk].key_part;
2532 for (;key_part != key_part_end; ++key_part)
2533 bitmap_clear_bit(¶m->needed_fields, key_part->fieldnr-1);
2607 int SQL_SELECT::test_quick_select(THD *thd,
key_map keys_to_use,
2608 table_map prev_tables,
2609 ha_rows
limit,
bool force_quick_range,
2610 const ORDER::enum_order interesting_order)
2614 DBUG_ENTER(
"SQL_SELECT::test_quick_select");
2615 DBUG_PRINT(
"enter",(
"keys_to_use: %lu prev_tables: %lu const_tables: %lu",
2616 (ulong) keys_to_use.to_ulonglong(), (ulong) prev_tables,
2617 (ulong) const_tables));
2620 needed_reg.clear_all();
2621 quick_keys.clear_all();
2622 if (keys_to_use.is_clear_all())
2624 records= head->file->stats.records;
2628 read_time= head->file->scan_time() + scan_time + 1.1;
2629 if (head->force_index)
2630 scan_time= read_time= DBL_MAX;
2631 if (limit < records)
2632 read_time= (double) records + scan_time + 1;
2633 else if (read_time <= 2.0 && !force_quick_range)
2639 add(
"rows", head->file->stats.records).
2640 add(
"cost", read_time);
2642 keys_to_use.intersect(head->keys_in_use_for_query);
2643 if (!keys_to_use.is_clear_all())
2663 param.prev_tables=prev_tables | const_tables;
2664 param.read_tables=read_tables;
2665 param.current_table= head->map;
2668 param.mem_root= &alloc;
2669 param.old_root= thd->mem_root;
2670 param.needed_reg= &needed_reg;
2671 param.imerge_cost_buff_size= 0;
2672 param.using_real_indexes= TRUE;
2673 param.remove_jump_scans= TRUE;
2674 param.force_default_mrr= (interesting_order == ORDER::ORDER_DESC);
2675 param.order_direction= interesting_order;
2679 init_sql_alloc(&alloc, thd->variables.range_alloc_block_size, 0);
2680 if (!(param.key_parts= (
KEY_PART*) alloc_root(&alloc,
2682 head->s->key_parts)) ||
2683 fill_used_fields_bitmap(¶m))
2686 free_root(&alloc,MYF(0));
2689 key_parts= param.key_parts;
2690 thd->mem_root= &alloc;
2694 "potential_range_indices",
2695 Opt_trace_context::RANGE_OPTIMIZER);
2700 key_info= head->key_info;
2701 for (idx=0 ; idx < head->s->keys ; idx++, key_info++)
2704 trace_idx_details.add_utf8(
"index", key_info->
name);
2706 if (!keys_to_use.is_set(idx))
2708 trace_idx_details.add(
"usable",
false).
2709 add_alnum(
"cause",
"not_applicable");
2712 if (key_info->
flags & HA_FULLTEXT)
2714 trace_idx_details.add(
"usable",
false).
2715 add_alnum(
"cause",
"fulltext");
2719 trace_idx_details.add(
"usable",
true);
2721 param.key[param.keys]=key_parts;
2722 key_part_info= key_info->key_part;
2725 part++, key_parts++, key_part_info++)
2727 key_parts->key= param.keys;
2728 key_parts->part= part;
2729 key_parts->length= key_part_info->length;
2730 key_parts->store_length= key_part_info->store_length;
2731 key_parts->field= key_part_info->field;
2732 key_parts->null_bit= key_part_info->null_bit;
2733 key_parts->image_type =
2734 (key_info->
flags & HA_SPATIAL) ? Field::itMBR : Field::itRAW;
2736 key_parts->flag= (uint8) key_part_info->key_part_flag;
2737 trace_keypart.add_utf8(key_parts->field->field_name);
2739 param.real_keynr[param.keys++]=idx;
2742 param.key_parts_end=key_parts;
2743 param.alloced_sel_args= 0;
2746 if (!head->covering_keys.is_clear_all())
2749 double key_read_time=
2751 rows2double(records)) +
2755 if (key_read_time < read_time)
2757 read_time= key_read_time;
2762 "best_covering_index_scan",
2763 Opt_trace_context::RANGE_OPTIMIZER);
2764 trace_cov.add_utf8(
"index", head->key_info[key_for_use].
name).
2765 add(
"cost", key_read_time).add(
"chosen", chosen);
2767 trace_cov.add_alnum(
"cause",
"cost");
2772 double best_read_time= read_time;
2778 tree= get_mm_tree(¶m,cond);
2782 if (tree->type == SEL_TREE::IMPOSSIBLE)
2784 trace_range.add(
"impossible_range",
true);
2786 read_time= (double) HA_POS_ERROR;
2793 if (tree->type != SEL_TREE::KEY && tree->type != SEL_TREE::KEY_SMALLER)
2795 trace_range.add(
"range_scan_possible",
false);
2796 if (tree->type == SEL_TREE::ALWAYS)
2797 trace_range.add_alnum(
"cause",
"condition_always_true");
2808 group_trp= get_best_group_min_max(¶m, tree, best_read_time);
2811 param.table->quick_condition_rows= min(group_trp->records,
2812 head->file->stats.records);
2814 "best_group_range_summary",
2815 Opt_trace_context::RANGE_OPTIMIZER);
2816 if (unlikely(trace->is_started()))
2818 if (group_trp->read_cost < best_read_time)
2820 grp_summary.add(
"chosen",
true);
2821 best_trp= group_trp;
2822 best_read_time= best_trp->read_cost;
2825 grp_summary.add(
"chosen",
false).add_alnum(
"cause",
"cost");
2834 dbug_print_tree(
"final_tree", tree, ¶m);
2842 "analyzing_range_alternatives",
2843 Opt_trace_context::RANGE_OPTIMIZER);
2848 if ((range_trp= get_key_scans_params(¶m, tree, FALSE, TRUE,
2851 best_trp= range_trp;
2852 best_read_time= best_trp->read_cost;
2861 if ((thd->lex->sql_command != SQLCOM_DELETE) &&
2862 thd->optimizer_switch_flag(OPTIMIZER_SWITCH_INDEX_MERGE) &&
2863 interesting_order != ORDER::ORDER_DESC)
2869 if ((rori_trp= get_best_ror_intersect(¶m, tree, best_read_time)))
2872 best_read_time= best_trp->read_cost;
2878 if (!tree->merges.is_empty())
2881 if (thd->optimizer_switch_flag(OPTIMIZER_SWITCH_INDEX_MERGE) &&
2882 interesting_order != ORDER::ORDER_DESC &&
2883 param.table->file->stats.records)
2888 LINT_INIT(new_conj_trp);
2891 "analyzing_index_merge",
2892 Opt_trace_context::RANGE_OPTIMIZER);
2893 while ((imerge= it++))
2895 new_conj_trp= get_best_disjunct_quick(¶m, imerge,
2898 set_if_smaller(param.table->quick_condition_rows,
2899 new_conj_trp->records);
2900 if (!best_conj_trp ||
2902 new_conj_trp->read_cost < best_conj_trp->read_cost))
2904 best_conj_trp= new_conj_trp;
2908 best_trp= best_conj_trp;
2913 thd->mem_root= param.old_root;
2918 records= best_trp->records;
2919 if (!(quick= best_trp->make_quick(¶m, TRUE)) || quick->init())
2924 if (unlikely(quick && trace->is_started() && best_trp))
2928 "chosen_range_access_summary");
2931 "range_access_plan");
2934 trace_range_summary.add(
"rows_for_plan", quick->records).
2935 add(
"cost_for_plan", quick->read_time).
2936 add(
"chosen",
true);
2939 free_root(&alloc,MYF(0));
2940 thd->mem_root= param.old_root;
2944 DBUG_EXECUTE(
"info", print_quick(quick, &needed_reg););
2950 DBUG_RETURN(records ?
test(quick) : -1);
2956 #ifdef WITH_PARTITION_STORAGE_ENGINE
3039 struct st_part_prune_param;
3040 struct st_part_opt_info;
3047 typedef struct st_part_prune_param
3055 partition_info *part_info;
3057 get_part_id_func get_top_partition_id_func;
3059 mark_full_part_func mark_full_partition_used;
3070 uint subpart_fields;
3076 int last_part_partno;
3077 int last_subpart_partno;
3084 my_bool *is_part_keypart;
3086 my_bool *is_subpart_keypart;
3088 my_bool ignore_part_fields;
3096 uint cur_part_fields;
3098 uint cur_subpart_fields;
3109 uint cur_min_flag, cur_max_flag;
3112 static bool create_partition_index_description(PART_PRUNE_PARAM *prune_par);
3113 static int find_used_partitions(PART_PRUNE_PARAM *ppar,
SEL_ARG *key_tree);
3114 static int find_used_partitions_imerge(PART_PRUNE_PARAM *ppar,
3116 static int find_used_partitions_imerge_list(PART_PRUNE_PARAM *ppar,
3118 static void mark_all_partitions_as_used(partition_info *part_info);
3121 static void print_partitioning_index(
KEY_PART *parts,
KEY_PART *parts_end);
3123 static void dbug_print_singlepoint_range(
SEL_ARG **start, uint num);
3149 bool prune_partitions(THD *thd,
TABLE *table,
Item *pprune_cond)
3151 partition_info *part_info = table->part_info;
3152 DBUG_ENTER(
"prune_partitions");
3153 table->all_partitions_pruned_away=
false;
3158 if (table->s->db_type()->partition_flags() & HA_USE_AUTO_PARTITION &&
3159 part_info->is_auto_partitioned)
3164 mark_all_partitions_as_used(part_info);
3169 if (bitmap_is_clear_all(&part_info->lock_partitions))
3170 bitmap_clear_all(&part_info->read_partitions);
3171 if (bitmap_is_clear_all(&part_info->read_partitions))
3173 table->all_partitions_pruned_away=
true;
3186 PART_PRUNE_PARAM prune_param;
3189 my_bitmap_map *old_sets[2];
3191 prune_param.part_info= part_info;
3192 init_sql_alloc(&alloc, thd->variables.range_alloc_block_size, 0);
3193 range_par->mem_root= &alloc;
3194 range_par->old_root= thd->mem_root;
3196 if (create_partition_index_description(&prune_param))
3198 mark_all_partitions_as_used(part_info);
3199 free_root(&alloc,MYF(0));
3203 dbug_tmp_use_all_columns(table, old_sets,
3204 table->read_set, table->write_set);
3205 range_par->thd= thd;
3206 range_par->table=
table;
3208 range_par->prev_tables= range_par->read_tables= 0;
3209 range_par->current_table= table->map;
3212 range_par->using_real_indexes= FALSE;
3213 range_par->remove_jump_scans= FALSE;
3214 range_par->real_keynr[0]= 0;
3215 range_par->alloced_sel_args= 0;
3218 thd->mem_root=&alloc;
3220 bitmap_clear_all(&part_info->read_partitions);
3222 prune_param.key= prune_param.range_param.key_parts;
3226 tree= get_mm_tree(range_par, pprune_cond);
3230 if (tree->type == SEL_TREE::IMPOSSIBLE)
3237 if (tree->type != SEL_TREE::KEY && tree->type != SEL_TREE::KEY_SMALLER)
3240 if (tree->merges.is_empty())
3243 prune_param.arg_stack_end= prune_param.arg_stack;
3244 prune_param.cur_part_fields= 0;
3245 prune_param.cur_subpart_fields= 0;
3247 prune_param.cur_min_key= prune_param.range_param.min_key;
3248 prune_param.cur_max_key= prune_param.range_param.max_key;
3249 prune_param.cur_min_flag= prune_param.cur_max_flag= 0;
3251 init_all_partitions_iterator(part_info, &prune_param.part_iter);
3252 if (!tree->keys[0] || (-1 == (res= find_used_partitions(&prune_param,
3258 if (tree->merges.elements == 1)
3269 if (-1 == (res= find_used_partitions_imerge(&prune_param,
3270 tree->merges.head())))
3282 if (-1 == (res= find_used_partitions_imerge_list(&prune_param,
3301 mark_all_partitions_as_used(prune_param.part_info);
3303 dbug_tmp_restore_column_maps(table->read_set, table->write_set, old_sets);
3305 thd->mem_root= range_par->old_root;
3306 free_root(&alloc,MYF(0));
3313 bitmap_intersect(&prune_param.part_info->read_partitions,
3314 &prune_param.part_info->lock_partitions);
3323 if (!thd->lex->is_query_tables_locked() &&
3324 !partition_key_modified(table, table->write_set))
3326 bitmap_copy(&prune_param.part_info->lock_partitions,
3327 &prune_param.part_info->read_partitions);
3329 if (bitmap_is_clear_all(&(prune_param.part_info->read_partitions)))
3330 table->all_partitions_pruned_away=
true;
3351 void store_key_image_to_rec(
Field *field, uchar *ptr, uint len)
3354 my_bitmap_map *old_map;
3363 field->set_notnull();
3366 old_map= dbug_tmp_use_all_columns(field->table,
3367 field->table->write_set);
3368 field->set_key_image(ptr, len);
3369 dbug_tmp_restore_column_map(field->table->write_set, old_map);
3387 static void store_selargs_to_rec(PART_PRUNE_PARAM *ppar,
SEL_ARG **start,
3390 KEY_PART *parts= ppar->range_param.key_parts;
3391 for (
SEL_ARG **end= start + num; start != end; start++)
3394 store_key_image_to_rec(sel_arg->field, sel_arg->min_value,
3395 parts[sel_arg->part].length);
3401 static void mark_full_partition_used_no_parts(partition_info* part_info,
3404 DBUG_ENTER(
"mark_full_partition_used_no_parts");
3405 DBUG_PRINT(
"enter", (
"Mark partition %u as used", part_id));
3406 bitmap_set_bit(&part_info->read_partitions, part_id);
3412 static void mark_full_partition_used_with_parts(partition_info *part_info,
3415 uint32 start= part_id * part_info->num_subparts;
3416 uint32 end= start + part_info->num_subparts;
3417 DBUG_ENTER(
"mark_full_partition_used_with_parts");
3419 for (; start != end; start++)
3421 DBUG_PRINT(
"info", (
"1:Mark subpartition %u as used", start));
3422 bitmap_set_bit(&part_info->read_partitions, start);
3444 static int find_used_partitions_imerge_list(PART_PRUNE_PARAM *ppar,
3449 my_bitmap_map *bitmap_buf;
3450 uint n_bits= ppar->part_info->read_partitions.n_bits;
3451 bitmap_bytes= bitmap_buffer_size(n_bits);
3452 if (!(bitmap_buf= (my_bitmap_map*) alloc_root(ppar->range_param.mem_root,
3459 return find_used_partitions_imerge(ppar, merges.head());
3461 bitmap_init(&all_merges, bitmap_buf, n_bits, FALSE);
3462 bitmap_set_prefix(&all_merges, n_bits);
3466 while ((imerge=it++))
3468 int res= find_used_partitions_imerge(ppar, imerge);
3476 bitmap_intersect(&all_merges, &ppar->part_info->read_partitions);
3478 if (bitmap_is_clear_all(&all_merges))
3481 bitmap_clear_all(&ppar->part_info->read_partitions);
3483 memcpy(ppar->part_info->read_partitions.bitmap, all_merges.bitmap,
3506 int find_used_partitions_imerge(PART_PRUNE_PARAM *ppar,
SEL_IMERGE *imerge)
3509 for (
SEL_TREE **ptree= imerge->trees; ptree < imerge->trees_next; ptree++)
3511 ppar->arg_stack_end= ppar->arg_stack;
3512 ppar->cur_part_fields= 0;
3513 ppar->cur_subpart_fields= 0;
3515 ppar->cur_min_key= ppar->range_param.min_key;
3516 ppar->cur_max_key= ppar->range_param.max_key;
3517 ppar->cur_min_flag= ppar->cur_max_flag= 0;
3519 init_all_partitions_iterator(ppar->part_info, &ppar->part_iter);
3520 SEL_ARG *key_tree= (*ptree)->keys[0];
3521 if (!key_tree || (-1 == (res |= find_used_partitions(ppar, key_tree))))
3639 int find_used_partitions(PART_PRUNE_PARAM *ppar,
SEL_ARG *key_tree)
3641 int res, left_res=0, right_res=0;
3642 int key_tree_part= (int)key_tree->part;
3643 bool set_full_part_if_bad_ret= FALSE;
3644 bool ignore_part_fields= ppar->ignore_part_fields;
3645 bool did_set_ignore_part_fields= FALSE;
3651 if (key_tree->left != &null_element)
3653 if (-1 == (left_res= find_used_partitions(ppar,key_tree->left)))
3658 ppar->cur_part_fields+= ppar->is_part_keypart[key_tree_part];
3659 ppar->cur_subpart_fields+= ppar->is_subpart_keypart[key_tree_part];
3660 *(ppar->arg_stack_end++)= key_tree;
3662 if (ignore_part_fields)
3672 if (key_tree->next_key_part)
3673 res= find_used_partitions(ppar, key_tree->next_key_part);
3676 goto pop_and_go_right;
3679 if (key_tree->type == SEL_ARG::KEY_RANGE)
3681 if (ppar->part_info->get_part_iter_for_interval &&
3682 key_tree->part <= ppar->last_part_partno)
3685 uchar *min_key= ppar->cur_min_key;
3686 uchar *max_key= ppar->cur_max_key;
3687 uchar *tmp_min_key= min_key;
3688 uchar *tmp_max_key= max_key;
3689 key_tree->store_min(ppar->key[key_tree->part].store_length,
3690 &tmp_min_key, ppar->cur_min_flag);
3691 key_tree->store_max(ppar->key[key_tree->part].store_length,
3692 &tmp_max_key, ppar->cur_max_flag);
3694 if (key_tree->next_key_part &&
3695 key_tree->next_key_part->part == key_tree->part+1 &&
3696 key_tree->next_key_part->part <= ppar->last_part_partno &&
3697 key_tree->next_key_part->type == SEL_ARG::KEY_RANGE)
3704 if ((tmp_min_key - min_key) == (tmp_max_key - max_key) &&
3705 (memcmp(min_key, max_key, (uint)(tmp_max_key - max_key)) == 0) &&
3706 !key_tree->min_flag && !key_tree->max_flag)
3709 ppar->cur_min_key= tmp_min_key;
3710 ppar->cur_max_key= tmp_max_key;
3711 uint save_min_flag= ppar->cur_min_flag;
3712 uint save_max_flag= ppar->cur_max_flag;
3714 ppar->cur_min_flag|= key_tree->min_flag;
3715 ppar->cur_max_flag|= key_tree->max_flag;
3717 res= find_used_partitions(ppar, key_tree->next_key_part);
3720 ppar->cur_min_key= min_key;
3721 ppar->cur_max_key= max_key;
3723 ppar->cur_min_flag= save_min_flag;
3724 ppar->cur_max_flag= save_max_flag;
3725 goto pop_and_go_right;
3728 uint tmp_min_flag= key_tree->min_flag,
3729 tmp_max_flag= key_tree->max_flag;
3731 key_tree->next_key_part->store_min_key(ppar->key,
3734 ppar->last_part_partno);
3736 key_tree->next_key_part->store_max_key(ppar->key,
3739 ppar->last_part_partno);
3740 flag= tmp_min_flag | tmp_max_flag;
3743 flag= key_tree->min_flag | key_tree->max_flag;
3745 if (tmp_min_key != range_par->min_key)
3746 flag&= ~NO_MIN_RANGE;
3748 flag|= NO_MIN_RANGE;
3749 if (tmp_max_key != range_par->max_key)
3750 flag&= ~NO_MAX_RANGE;
3752 flag|= NO_MAX_RANGE;
3764 if (ppar->arg_stack[0]->part == 0)
3767 uint32 store_length_array[MAX_KEY];
3768 uint32 num_keys= ppar->part_fields;
3770 for (i= 0; i < num_keys; i++)
3771 store_length_array[i]= ppar->key[i].store_length;
3772 res= ppar->part_info->
3773 get_part_iter_for_interval(ppar->part_info,
3778 tmp_min_key - range_par->min_key,
3779 tmp_max_key - range_par->max_key,
3783 goto pop_and_go_right;
3791 init_all_partitions_iterator(ppar->part_info, &ppar->part_iter);
3797 if (key_tree_part < ppar->last_part_partno)
3803 did_set_ignore_part_fields= TRUE;
3804 ppar->ignore_part_fields= TRUE;
3806 set_full_part_if_bad_ret= TRUE;
3807 goto process_next_key_part;
3810 if (key_tree_part == ppar->last_subpart_partno &&
3811 (NULL != ppar->part_info->get_subpart_iter_for_interval))
3814 DBUG_EXECUTE(
"info", dbug_print_segment_range(key_tree,
3815 range_par->key_parts););
3816 res= ppar->part_info->
3817 get_subpart_iter_for_interval(ppar->part_info,
3820 key_tree->min_value,
3821 key_tree->max_value,
3823 key_tree->min_flag |
3828 goto pop_and_go_right;
3831 bitmap_clear_all(&ppar->subparts_bitmap);
3832 while ((subpart_id= subpart_iter.get_next(&subpart_iter)) !=
3834 bitmap_set_bit(&ppar->subparts_bitmap, subpart_id);
3838 while ((part_id= ppar->part_iter.get_next(&ppar->part_iter)) !=
3841 for (uint i= 0; i < ppar->part_info->num_subparts; i++)
3842 if (bitmap_is_set(&ppar->subparts_bitmap, i))
3843 bitmap_set_bit(&ppar->part_info->read_partitions,
3844 part_id * ppar->part_info->num_subparts + i);
3846 goto pop_and_go_right;
3849 if (key_tree->is_singlepoint())
3851 if (key_tree_part == ppar->last_part_partno &&
3852 ppar->cur_part_fields == ppar->part_fields &&
3853 ppar->part_info->get_part_iter_for_interval == NULL)
3859 store_selargs_to_rec(ppar, ppar->arg_stack, ppar->part_fields);
3860 DBUG_EXECUTE(
"info", dbug_print_singlepoint_range(ppar->arg_stack,
3861 ppar->part_fields););
3863 longlong func_value;
3865 if (ppar->get_top_partition_id_func(ppar->part_info, &part_id,
3869 goto pop_and_go_right;
3872 init_single_partition_iterator(part_id, &ppar->part_iter);
3878 set_full_part_if_bad_ret= TRUE;
3879 goto process_next_key_part;
3882 if (key_tree_part == ppar->last_subpart_partno &&
3883 ppar->cur_subpart_fields == ppar->subpart_fields)
3889 store_selargs_to_rec(ppar, ppar->arg_stack_end - ppar->subpart_fields,
3890 ppar->subpart_fields);
3891 DBUG_EXECUTE(
"info", dbug_print_singlepoint_range(ppar->arg_stack_end-
3892 ppar->subpart_fields,
3893 ppar->subpart_fields););
3895 partition_info *part_info= ppar->part_info;
3896 uint32 part_id, subpart_id;
3898 if (part_info->get_subpartition_id(part_info, &subpart_id))
3902 while ((part_id= ppar->part_iter.get_next(&ppar->part_iter)) !=
3905 bitmap_set_bit(&part_info->read_partitions,
3906 part_id * part_info->num_subparts + subpart_id);
3909 goto pop_and_go_right;
3919 if (key_tree_part >= ppar->last_part_partno)
3922 goto pop_and_go_right;
3928 ppar->ignore_part_fields=
true;
3929 did_set_ignore_part_fields=
true;
3930 goto process_next_key_part;
3934 process_next_key_part:
3935 if (key_tree->next_key_part)
3936 res= find_used_partitions(ppar, key_tree->next_key_part);
3940 if (did_set_ignore_part_fields)
3948 ppar->ignore_part_fields= FALSE;
3950 if (set_full_part_if_bad_ret)
3957 while ((part_id= ppar->part_iter.get_next(&ppar->part_iter)) !=
3960 ppar->mark_full_partition_used(ppar->part_info, part_id);
3969 init_all_partitions_iterator(ppar->part_info, &ppar->part_iter);
3974 ppar->arg_stack_end--;
3975 ppar->cur_part_fields-= ppar->is_part_keypart[key_tree_part];
3976 ppar->cur_subpart_fields-= ppar->is_subpart_keypart[key_tree_part];
3980 if (key_tree->right != &null_element)
3982 if (-1 == (right_res= find_used_partitions(ppar,key_tree->right)))
3985 return (left_res || right_res || res);
3989 static void mark_all_partitions_as_used(partition_info *part_info)
3991 bitmap_copy(&(part_info->read_partitions),
3992 &(part_info->lock_partitions));
4019 static bool fields_ok_for_partition_index(
Field **pfield)
4023 for (; (*pfield); pfield++)
4025 enum_field_types ftype= (*pfield)->real_type();
4026 if (ftype == MYSQL_TYPE_ENUM || ftype == MYSQL_TYPE_GEOMETRY)
4055 static bool create_partition_index_description(PART_PRUNE_PARAM *ppar)
4058 partition_info *part_info= ppar->part_info;
4059 uint used_part_fields, used_subpart_fields;
4061 used_part_fields= fields_ok_for_partition_index(part_info->part_field_array) ?
4062 part_info->num_part_fields : 0;
4063 used_subpart_fields=
4064 fields_ok_for_partition_index(part_info->subpart_field_array)?
4065 part_info->num_subpart_fields : 0;
4067 uint total_parts= used_part_fields + used_subpart_fields;
4069 ppar->ignore_part_fields= FALSE;
4070 ppar->part_fields= used_part_fields;
4071 ppar->last_part_partno= (int)used_part_fields - 1;
4073 ppar->subpart_fields= used_subpart_fields;
4074 ppar->last_subpart_partno=
4075 used_subpart_fields?(int)(used_part_fields + used_subpart_fields - 1): -1;
4077 if (part_info->is_sub_partitioned())
4079 ppar->mark_full_partition_used= mark_full_partition_used_with_parts;
4080 ppar->get_top_partition_id_func= part_info->get_part_partition_id;
4084 ppar->mark_full_partition_used= mark_full_partition_used_no_parts;
4085 ppar->get_top_partition_id_func= part_info->get_partition_id;
4089 MEM_ROOT *alloc= range_par->mem_root;
4093 !(ppar->arg_stack= (
SEL_ARG**)alloc_root(alloc,
sizeof(
SEL_ARG*)*
4095 !(ppar->is_part_keypart= (my_bool*)alloc_root(alloc,
sizeof(my_bool)*
4097 !(ppar->is_subpart_keypart= (my_bool*)alloc_root(alloc,
sizeof(my_bool)*
4101 if (ppar->subpart_fields)
4104 uint32 bufsize= bitmap_buffer_size(ppar->part_info->num_subparts);
4105 if (!(buf= (my_bitmap_map*) alloc_root(alloc, bufsize)))
4107 bitmap_init(&ppar->subparts_bitmap, buf, ppar->part_info->num_subparts,
4110 range_par->key_parts= key_part;
4111 Field **field= (ppar->part_fields)? part_info->part_field_array :
4112 part_info->subpart_field_array;
4113 bool in_subpart_fields= FALSE;
4114 for (uint part= 0; part < total_parts; part++, key_part++)
4117 key_part->part= part;
4118 key_part->length= (uint16)(*field)->key_length();
4119 key_part->store_length= (uint16)get_partition_field_store_length(*field);
4121 DBUG_PRINT(
"info", (
"part %u length %u store_length %u", part,
4122 key_part->length, key_part->store_length));
4124 key_part->field= (*field);
4125 key_part->image_type = Field::itRAW;
4133 ppar->is_part_keypart[part]= !in_subpart_fields;
4134 ppar->is_subpart_keypart[part]= in_subpart_fields;
4143 field= part_info->subpart_field_array;
4144 in_subpart_fields= TRUE;
4147 range_par->key_parts_end= key_part;
4149 DBUG_EXECUTE(
"info", print_partitioning_index(range_par->key_parts,
4150 range_par->key_parts_end););
4159 DBUG_ENTER(
"print_partitioning_index");
4161 fprintf(DBUG_FILE,
"partitioning INDEX(");
4162 for (
KEY_PART *p=parts; p != parts_end; p++)
4164 fprintf(DBUG_FILE,
"%s%s", p==parts?
"":
" ,", p->field->field_name);
4166 fputs(
");\n", DBUG_FILE);
4175 DBUG_ENTER(
"dbug_print_segment_range");
4177 if (!(arg->min_flag & NO_MIN_RANGE))
4179 store_key_image_to_rec(part->field, arg->min_value, part->length);
4180 part->field->dbug_print();
4181 if (arg->min_flag & NEAR_MIN)
4182 fputs(
" < ", DBUG_FILE);
4184 fputs(
" <= ", DBUG_FILE);
4187 fprintf(DBUG_FILE,
"%s", part->field->field_name);
4189 if (!(arg->max_flag & NO_MAX_RANGE))
4191 if (arg->max_flag & NEAR_MAX)
4192 fputs(
" < ", DBUG_FILE);
4194 fputs(
" <= ", DBUG_FILE);
4195 store_key_image_to_rec(part->field, arg->max_value, part->length);
4196 part->field->dbug_print();
4198 fputs(
"\n", DBUG_FILE);
4217 static void dbug_print_singlepoint_range(
SEL_ARG **start, uint num)
4219 DBUG_ENTER(
"dbug_print_singlepoint_range");
4223 for (
SEL_ARG **arg= start; arg != end; arg++)
4225 Field *field= (*arg)->field;
4226 fprintf(DBUG_FILE,
"%s%s=", (arg==start)?
"":
", ", field->field_name);
4227 field->dbug_print();
4229 fputs(
"\n", DBUG_FILE);
4312 uint n_child_scans= imerge->trees_next - imerge->trees;
4316 bool imerge_too_expensive= FALSE;
4317 double imerge_cost= 0.0;
4318 ha_rows cpk_scan_records= 0;
4319 ha_rows non_cpk_scan_records= 0;
4320 bool pk_is_clustered= param->table->file->primary_key_is_clustered();
4321 bool all_scans_ror_able= TRUE;
4322 bool all_scans_rors= TRUE;
4323 uint unique_calc_buff_size;
4326 double roru_index_costs;
4327 ha_rows roru_total_records;
4328 double roru_intersect_part= 1.0;
4329 DBUG_ENTER(
"get_best_disjunct_quick");
4330 DBUG_PRINT(
"info", (
"Full table scan cost: %g", read_time));
4332 DBUG_ASSERT(param->table->file->stats.records);
4336 if (!(range_scans= (
TRP_RANGE**)alloc_root(param->mem_root,
4347 for (ptree= imerge->trees, cur_child= range_scans;
4348 ptree != imerge->trees_next;
4349 ptree++, cur_child++)
4351 DBUG_EXECUTE(
"info", print_sel_tree(param, *ptree, &(*ptree)->keys_map,
4352 "tree in SEL_IMERGE"););
4355 get_key_scans_params(param, *ptree,
true,
false, read_time)))
4363 imerge_too_expensive=
true;
4365 if (imerge_too_expensive)
4367 trace_idx.add(
"chosen",
false).add_alnum(
"cause",
"cost");
4371 const uint keynr_in_table= param->real_keynr[(*cur_child)->key_idx];
4372 imerge_cost += (*cur_child)->read_cost;
4373 all_scans_ror_able &= ((*ptree)->n_ror_scans > 0);
4374 all_scans_rors &= (*cur_child)->is_ror;
4375 if (pk_is_clustered &&
4376 keynr_in_table == param->table->s->primary_key)
4378 cpk_scan= cur_child;
4379 cpk_scan_records= (*cur_child)->records;
4382 non_cpk_scan_records += (*cur_child)->records;
4385 add_utf8(
"index_to_merge", param->table->key_info[keynr_in_table].
name).
4386 add(
"cumulated_cost", imerge_cost);
4393 trace_best_disjunct.add(
"cost_of_reading_ranges", imerge_cost);
4394 if (imerge_too_expensive || (imerge_cost > read_time) ||
4395 ((non_cpk_scan_records+cpk_scan_records >= param->table->file->stats.records) &&
4396 read_time != DBL_MAX))
4402 DBUG_PRINT(
"info", (
"Sum of index_merge scans is more expensive than "
4403 "full table scan, bailing out"));
4404 trace_best_disjunct.add(
"chosen",
false).add_alnum(
"cause",
"cost");
4413 if (all_scans_rors &&
4414 param->thd->optimizer_switch_flag(OPTIMIZER_SWITCH_INDEX_MERGE_UNION))
4417 trace_best_disjunct.add(
"use_roworder_union",
true).
4418 add_alnum(
"cause",
"always_cheaper_than_not_roworder_retrieval");
4419 goto skip_to_ror_scan;
4429 imerge_cost+= rid_comp_cost;
4430 trace_best_disjunct.add(
"cost_of_mapping_rowid_in_non_clustered_pk_scan",
4437 JOIN *join= param->thd->lex->select_lex.join;
4438 const bool is_interrupted= join && join->
tables != 1;
4441 const double sweep_total_cost= sweep_cost.
total_cost();
4442 imerge_cost+= sweep_total_cost;
4443 trace_best_disjunct.add(
"cost_sort_rowid_and_read_disk",
4446 DBUG_PRINT(
"info",(
"index_merge cost with rowid-to-row scan: %g",
4448 if (imerge_cost > read_time ||
4449 !param->thd->optimizer_switch_flag(OPTIMIZER_SWITCH_INDEX_MERGE_SORT_UNION))
4451 trace_best_disjunct.add(
"use_roworder_index_merge",
true).
4452 add_alnum(
"cause",
"cost");
4453 goto build_ror_index_merge;
4457 unique_calc_buff_size=
4458 Unique::get_cost_calc_buff_size((ulong)non_cpk_scan_records,
4460 param->thd->variables.sortbuff_size);
4461 if (param->imerge_cost_buff_size < unique_calc_buff_size)
4463 if (!(param->imerge_cost_buff= (uint*)alloc_root(param->mem_root,
4464 unique_calc_buff_size)))
4466 param->imerge_cost_buff_size= unique_calc_buff_size;
4470 const double dup_removal_cost=
4471 Unique::get_use_cost(param->imerge_cost_buff,
4472 (uint)non_cpk_scan_records,
4474 param->thd->variables.sortbuff_size);
4476 trace_best_disjunct.add(
"cost_duplicate_removal", dup_removal_cost);
4477 imerge_cost += dup_removal_cost;
4478 trace_best_disjunct.add(
"total_cost", imerge_cost);
4479 DBUG_PRINT(
"info",(
"index_merge total cost: %g (wanted: less then %g)",
4480 imerge_cost, read_time));
4482 if (imerge_cost < read_time)
4486 imerge_trp->read_cost= imerge_cost;
4487 imerge_trp->records= non_cpk_scan_records + cpk_scan_records;
4488 imerge_trp->records= min(imerge_trp->records,
4489 param->table->file->stats.records);
4490 imerge_trp->range_scans= range_scans;
4491 imerge_trp->range_scans_end= range_scans + n_child_scans;
4492 read_time= imerge_cost;
4496 build_ror_index_merge:
4497 if (!all_scans_ror_able ||
4498 param->thd->lex->sql_command == SQLCOM_DELETE ||
4499 !param->thd->optimizer_switch_flag(OPTIMIZER_SWITCH_INDEX_MERGE_UNION))
4500 DBUG_RETURN(imerge_trp);
4503 if (!(roru_read_plans=
4507 DBUG_RETURN(imerge_trp);
4509 roru_index_costs= 0.0;
4510 roru_total_records= 0;
4511 cur_roru_plan= roru_read_plans;
4519 for (ptree= imerge->trees, cur_child= range_scans;
4520 ptree != imerge->trees_next;
4521 ptree++, cur_child++, cur_roru_plan++)
4524 if (unlikely(trace->is_started()))
4525 (*cur_child)->trace_basic_info(param, &trp_info);
4534 if ((*cur_child)->is_ror)
4537 cost= param->table->file->
4538 read_time(param->real_keynr[(*cur_child)->key_idx], 1,
4539 (*cur_child)->records) +
4546 if (!(*cur_roru_plan= get_best_ror_intersect(param, *ptree, cost)))
4548 if (prev_plan->is_ror)
4549 *cur_roru_plan= prev_plan;
4551 DBUG_RETURN(imerge_trp);
4552 roru_index_costs += (*cur_roru_plan)->read_cost;
4557 roru_total_records += (*cur_roru_plan)->records;
4558 roru_intersect_part *= (*cur_roru_plan)->records /
4559 param->table->file->stats.records;
4562 trace_analyze_ror.end();
4570 roru_total_records -= (ha_rows)(roru_intersect_part*
4571 param->table->file->stats.records);
4580 double roru_total_cost;
4583 JOIN *join= param->thd->lex->select_lex.join;
4584 const bool is_interrupted= join && join->
tables != 1;
4587 roru_total_cost= roru_index_costs +
4588 rows2double(roru_total_records) *
4589 log((
double)n_child_scans) * ROWID_COMPARE_COST / M_LN2 +
4593 trace_best_disjunct.add(
"index_roworder_union_cost", roru_total_cost).
4594 add(
"members", n_child_scans);
4596 if (roru_total_cost < read_time)
4600 trace_best_disjunct.add(
"chosen",
true);
4601 roru->first_ror= roru_read_plans;
4602 roru->last_ror= roru_read_plans + n_child_scans;
4603 roru->read_cost= roru_total_cost;
4604 roru->records= roru_total_records;
4608 trace_best_disjunct.add(
"chosen",
false);
4610 DBUG_RETURN(imerge_trp);
4633 my_bitmap_map *bitmap_buf1;
4634 my_bitmap_map *bitmap_buf2;
4636 DBUG_ENTER(
"make_ror_scan");
4643 ror_scan->
keynr= keynr= param->real_keynr[idx];
4645 ror_scan->
records= param->table->quick_rows[keynr];
4647 if (!(bitmap_buf1= (my_bitmap_map*) alloc_root(param->mem_root,
4648 param->fields_bitmap_size)))
4650 if (!(bitmap_buf2= (my_bitmap_map*) alloc_root(param->mem_root,
4651 param->fields_bitmap_size)))
4655 param->table->s->fields, FALSE))
4658 param->table->s->fields, FALSE))
4663 KEY_PART_INFO *key_part= param->table->key_info[keynr].key_part;
4666 for (;key_part != key_part_end; ++key_part)
4668 if (bitmap_is_set(¶m->needed_fields, key_part->fieldnr-1))
4673 double rows= rows2double(param->table->quick_rows[ror_scan->
keynr]);
4676 DBUG_RETURN(ror_scan);
4691 static bool is_better_intersect_match(
const ROR_SCAN_INFO *scan1,
4732 if ((start == end) || (start + 1 == end))
4743 if (!(map= (my_bitmap_map*) alloc_root(param->mem_root,
4744 param->fields_bitmap_size)))
4746 bitmap_init(&fields_to_cover, map, param->needed_fields.n_bits, FALSE);
4747 bitmap_copy(&fields_to_cover, ¶m->needed_fields);
4750 for (
ROR_SCAN_INFO **place= start; place < (end - 1); place++)
4763 bitmap_intersect(&(*best)->covered_fields_remaining, &fields_to_cover);
4764 (*best)->num_covered_fields_remaining=
4765 bitmap_bits_set(&(*best)->covered_fields_remaining);
4767 for (; current < end; current++)
4776 bitmap_intersect(&(*current)->covered_fields_remaining,
4778 (*current)->num_covered_fields_remaining=
4779 bitmap_bits_set(&(*current)->covered_fields_remaining);
4785 if ((*current)->num_covered_fields_remaining == 0)
4789 if (is_better_intersect_match(*best, *current))
4798 bitmap_subtract(&fields_to_cover, &(*best)->covered_fields);
4802 if (bitmap_is_clear_all(&fields_to_cover))
4821 ha_rows index_records;
4822 double index_scan_costs;
4848 if (!(buf= (my_bitmap_map*) alloc_root(param->mem_root,
4849 param->fields_bitmap_size)))
4851 if (bitmap_init(&info->covered_fields, buf, param->table->s->fields,
4854 info->is_covering= FALSE;
4855 info->index_scan_costs= 0.0;
4856 info->total_cost= 0.0;
4857 info->index_records= 0;
4858 info->out_rows= (double) param->table->file->stats.records;
4859 bitmap_clear_all(&info->covered_fields);
4865 dst->param= src->param;
4866 memcpy(dst->covered_fields.bitmap, src->covered_fields.bitmap,
4867 no_bytes_in_map(&src->covered_fields));
4868 dst->out_rows= src->out_rows;
4869 dst->is_covering= src->is_covering;
4870 dst->index_records= src->index_records;
4871 dst->index_scan_costs= src->index_scan_costs;
4872 dst->total_cost= src->total_cost;
4976 double selectivity_mult= 1.0;
4977 const TABLE *
const table= info->param->table;
4986 uchar key_val[MAX_KEY_LENGTH+MAX_FIELD_WIDTH];
4987 uchar *key_ptr= key_val;
4988 SEL_ARG *sel_arg, *tuple_arg= NULL;
4989 key_part_map keypart_map= 0;
4991 bool prev_covered=
test(bitmap_is_set(&info->covered_fields,
4992 key_part->fieldnr-1));
4995 min_range.key= key_val;
4996 min_range.flag= HA_READ_KEY_EXACT;
4997 max_range.key= key_val;
4998 max_range.flag= HA_READ_AFTER_KEY;
4999 ha_rows prev_records= table->file->stats.records;
5000 DBUG_ENTER(
"ror_scan_selectivity");
5002 for (sel_arg= scan->
sel_arg; sel_arg;
5003 sel_arg= sel_arg->next_key_part)
5005 DBUG_PRINT(
"info",(
"sel_arg step"));
5006 cur_covered=
test(bitmap_is_set(&info->covered_fields,
5007 key_part[sel_arg->part].fieldnr-1));
5008 if (cur_covered != prev_covered)
5011 bool is_null_range=
false;
5017 tuple_arg->store_min(key_part[0].store_length, &key_ptr, 0);
5018 is_null_range|= tuple_arg->is_null_interval();
5021 while (tuple_arg->next_key_part != sel_arg)
5023 tuple_arg= tuple_arg->next_key_part;
5024 tuple_arg->store_min(key_part[tuple_arg->part].store_length,
5026 is_null_range|= tuple_arg->is_null_interval();
5027 keypart_map= (keypart_map << 1) | 1;
5029 min_range.length= max_range.length= (size_t) (key_ptr - key_val);
5030 min_range.keypart_map= max_range.keypart_map= keypart_map;
5046 !(records= table->key_info[scan->
keynr].
5047 rec_per_key[tuple_arg->part]))
5049 DBUG_EXECUTE_IF(
"crash_records_in_range", DBUG_SUICIDE(););
5050 DBUG_ASSERT(min_range.length > 0);
5051 records= (table->file->
5052 records_in_range(scan->
keynr, &min_range, &max_range));
5057 double tmp= rows2double(records)/rows2double(prev_records);
5058 DBUG_PRINT(
"info", (
"Selectivity multiplier: %g", tmp));
5059 selectivity_mult *= tmp;
5060 prev_records= HA_POS_ERROR;
5065 prev_records= records;
5068 prev_covered= cur_covered;
5072 double tmp= rows2double(table->quick_rows[scan->
keynr]) /
5073 rows2double(prev_records);
5074 DBUG_PRINT(
"info", (
"Selectivity multiplier: %g", tmp));
5075 selectivity_mult *= tmp;
5079 DBUG_PRINT(
"info", (
"Returning multiplier: %g", selectivity_mult));
5080 DBUG_RETURN(selectivity_mult);
5125 double selectivity_mult= 1.0;
5127 DBUG_ENTER(
"ror_intersect_add");
5128 DBUG_PRINT(
"info", (
"Current out_rows= %g", info->out_rows));
5129 DBUG_PRINT(
"info", (
"Adding scan on %s",
5130 info->param->table->key_info[ror_scan->
keynr].
name));
5131 DBUG_PRINT(
"info", (
"is_cpk_scan: %d",is_cpk_scan));
5133 selectivity_mult = ror_scan_selectivity(info, ror_scan);
5134 if (selectivity_mult == 1.0)
5137 DBUG_PRINT(
"info", (
"The scan doesn't improve selectivity."));
5141 info->out_rows *= selectivity_mult;
5150 const double idx_cost=
5152 info->index_scan_costs+= idx_cost;
5153 trace_costs->add(
"index_scan_cost", idx_cost);
5157 info->index_records += info->param->table->quick_rows[ror_scan->
keynr];
5161 if (!info->is_covering && bitmap_is_subset(&info->param->needed_fields,
5162 &info->covered_fields))
5164 DBUG_PRINT(
"info", (
"ROR-intersect is covering now"));
5165 info->is_covering= TRUE;
5169 info->total_cost= info->index_scan_costs;
5170 trace_costs->add(
"cumulated_index_scan_cost", info->index_scan_costs);
5172 if (!info->is_covering)
5175 JOIN *join= info->param->thd->lex->select_lex.join;
5176 const bool is_interrupted= join && join->
tables == 1;
5178 is_interrupted, &sweep_cost);
5180 trace_costs->add(
"disk_sweep_cost", sweep_cost.
total_cost());
5183 trace_costs->add(
"disk_sweep_cost", 0);
5185 DBUG_PRINT(
"info", (
"New out_rows: %g", info->out_rows));
5186 DBUG_PRINT(
"info", (
"New cost: %g, %scovering", info->total_cost,
5187 info->is_covering?
"" :
"non-"));
5261 double min_cost= DBL_MAX;
5263 DBUG_ENTER(
"get_best_ror_intersect");
5267 if ((tree->n_ror_scans < 2) || !param->table->file->stats.records ||
5268 !param->thd->optimizer_switch_flag(OPTIMIZER_SWITCH_INDEX_MERGE_INTERSECT))
5270 trace_ror.add(
"usable",
false);
5271 if (tree->n_ror_scans < 2)
5272 trace_ror.add_alnum(
"cause",
"too_few_roworder_scans");
5274 trace_ror.add(
"need_tracing",
true);
5278 if (param->order_direction == ORDER::ORDER_DESC)
5288 bool cpk_scan_used= FALSE;
5290 if (!(tree->ror_scans= (
ROR_SCAN_INFO**)alloc_root(param->mem_root,
5294 cpk_no= ((param->table->file->primary_key_is_clustered()) ?
5295 param->table->s->primary_key : MAX_KEY);
5297 for (idx= 0, cur_ror_scan= tree->ror_scans; idx < param->keys; idx++)
5300 if (!tree->ror_scans_map.is_set(idx))
5302 if (!(scan= make_ror_scan(param, idx, tree->keys[idx])))
5304 if (param->real_keynr[idx] == cpk_no)
5307 tree->n_ror_scans--;
5310 *(cur_ror_scan++)= scan;
5313 tree->ror_scans_end= cur_ror_scan;
5314 DBUG_EXECUTE(
"info",print_ror_scans_arr(param->table,
"original",
5316 tree->ror_scans_end););
5322 find_intersect_order(tree->ror_scans, tree->ror_scans_end, param);
5324 DBUG_EXECUTE(
"info",print_ror_scans_arr(param->table,
"ordered",
5326 tree->ror_scans_end););
5330 if (!(intersect_scans= (
ROR_SCAN_INFO**)alloc_root(param->mem_root,
5332 tree->n_ror_scans)))
5334 intersect_scans_end= intersect_scans;
5338 if (!(intersect= ror_intersect_init(param)) ||
5339 !(intersect_best= ror_intersect_init(param)))
5344 cur_ror_scan= tree->ror_scans;
5345 intersect_scans_best= intersect_scans;
5351 while (cur_ror_scan != tree->ror_scans_end && !intersect->is_covering)
5354 trace_idx.add_utf8(
"index",
5355 param->table->key_info[(*cur_ror_scan)->keynr].
name);
5357 if (!ror_intersect_add(intersect, *cur_ror_scan, FALSE, &trace_idx))
5359 trace_idx.add(
"cumulated_total_cost", intersect->total_cost).
5360 add(
"usable",
false).
5361 add_alnum(
"cause",
"does_not_reduce_cost_of_intersect");
5366 trace_idx.add(
"cumulated_total_cost", intersect->total_cost).
5367 add(
"usable",
true).
5368 add(
"matching_rows_now", intersect->out_rows).
5369 add(
"isect_covering_with_this_index", intersect->is_covering);
5371 *(intersect_scans_end++)= *(cur_ror_scan++);
5373 if (intersect->total_cost < min_cost)
5376 ror_intersect_cpy(intersect_best, intersect);
5377 intersect_scans_best= intersect_scans_end;
5378 min_cost = intersect->total_cost;
5379 trace_idx.add(
"chosen",
true);
5383 trace_idx.add(
"chosen",
false).
5384 add_alnum(
"cause",
"does_not_reduce_cost");
5388 trace_isect_idx.end();
5390 if (intersect_scans_best == intersect_scans)
5392 trace_ror.add(
"chosen",
false).
5393 add_alnum(
"cause",
"does_not_increase_selectivity");
5394 DBUG_PRINT(
"info", (
"None of scans increase selectivity"));
5398 DBUG_EXECUTE(
"info",print_ror_scans_arr(param->table,
5399 "best ROR-intersection",
5401 intersect_scans_best););
5403 uint best_num= intersect_scans_best - intersect_scans;
5404 ror_intersect_cpy(intersect, intersect_best);
5413 if (cpk_scan && !intersect->is_covering)
5415 if (ror_intersect_add(intersect, cpk_scan, TRUE, &trace_cpk) &&
5416 (intersect->total_cost < min_cost))
5418 trace_cpk.add(
"clustered_pk_scan_added_to_intersect",
true).
5419 add(
"cumulated_cost", intersect->total_cost);
5420 cpk_scan_used= TRUE;
5421 intersect_best= intersect;
5424 trace_cpk.add(
"clustered_pk_added_to_intersect",
false).
5425 add_alnum(
"cause",
"cost");
5429 trace_cpk.add(
"clustered_pk_added_to_intersect",
false).
5430 add_alnum(
"cause", cpk_scan ?
5431 "roworder_is_covering" :
"no_clustered_pk_index");
5436 if (min_cost < read_time && (cpk_scan_used || best_num > 1))
5440 if (!(trp->first_scan=
5444 memcpy(trp->first_scan, intersect_scans, best_num*
sizeof(
ROR_SCAN_INFO*));
5445 trp->last_scan= trp->first_scan + best_num;
5446 trp->is_covering= intersect_best->is_covering;
5447 trp->read_cost= intersect_best->total_cost;
5449 ha_rows best_rows = double2rows(intersect_best->out_rows);
5452 set_if_smaller(param->table->quick_condition_rows, best_rows);
5453 trp->records= best_rows;
5454 trp->index_scan_costs= intersect_best->index_scan_costs;
5455 trp->cpk_scan= cpk_scan_used? cpk_scan: NULL;
5457 trace_ror.add(
"rows", trp->records).
5458 add(
"cost", trp->read_cost).
5459 add(
"covering", trp->is_covering).
5460 add(
"chosen",
true);
5462 DBUG_PRINT(
"info", (
"Returning non-covering ROR-intersect plan:"
5463 "cost %g, records %lu",
5464 trp->read_cost, (ulong) trp->records));
5468 trace_ror.add(
"chosen",
false).
5469 add_alnum(
"cause", (min_cost >= read_time) ?
"cost" :
5470 "too_few_indexes_to_merge");
5503 bool index_read_must_be_used,
5504 bool update_tbl_stats,
5508 SEL_ARG **key,**end, **key_to_read= NULL;
5509 ha_rows UNINIT_VAR(best_records);
5510 uint best_mrr_flags, best_buf_size;
5512 DBUG_ENTER(
"get_key_scans_params");
5513 LINT_INIT(best_mrr_flags);
5514 LINT_INIT(best_buf_size);
5521 DBUG_EXECUTE(
"info", print_sel_tree(param, tree, &tree->keys_map,
5525 tree->ror_scans_map.clear_all();
5526 tree->n_ror_scans= 0;
5527 for (idx= 0,key=tree->keys, end=key+param->keys; key != end; key++,idx++)
5531 ha_rows found_records;
5533 double found_read_time;
5534 uint mrr_flags, buf_size;
5535 uint keynr= param->real_keynr[idx];
5536 if ((*key)->type == SEL_ARG::MAYBE_KEY ||
5538 param->needed_reg->set_bit(keynr);
5540 bool read_index_only= index_read_must_be_used ? TRUE :
5541 (bool) param->table->covering_keys.is_set(keynr);
5544 trace_idx.add_utf8(
"index", param->table->key_info[keynr].
name);
5546 found_records= check_quick_select(param, idx, read_index_only, *key,
5547 update_tbl_stats, &mrr_flags,
5550 #ifdef OPTIMIZER_TRACE
5552 if (found_records != HA_POS_ERROR &&
5553 param->thd->opt_trace.is_started())
5557 const KEY &cur_key= param->table->key_info[keynr];
5561 range_info.set_charset(system_charset_info);
5562 append_range_all_keyparts(&trace_range, NULL,
5563 &range_info, *key, key_part);
5567 add(
"rowid_ordered", param->is_ror_scan).
5568 add(
"using_mrr", !(mrr_flags & HA_MRR_USE_DEFAULT_IMPL)).
5569 add(
"index_only", read_index_only).
5570 add(
"rows", found_records).
5575 if ((found_records != HA_POS_ERROR) && param->is_ror_scan)
5577 tree->n_ror_scans++;
5578 tree->ror_scans_map.set_bit(idx);
5582 if (found_records != HA_POS_ERROR &&
5583 read_time > (found_read_time= cost.
total_cost()))
5585 trace_idx.add(
"chosen",
true);
5586 read_time= found_read_time;
5587 best_records= found_records;
5589 best_mrr_flags= mrr_flags;
5590 best_buf_size= buf_size;
5593 trace_idx.add(
"chosen",
false).
5595 (found_records == HA_POS_ERROR) ?
"unknown" :
"cost");
5600 DBUG_EXECUTE(
"info", print_sel_tree(param, tree, &tree->ror_scans_map,
5604 idx= key_to_read - tree->keys;
5605 if ((read_plan=
new (param->mem_root)
TRP_RANGE(*key_to_read, idx,
5608 read_plan->records= best_records;
5609 read_plan->is_ror= tree->ror_scans_map.is_set(idx);
5610 read_plan->read_cost= read_time;
5611 read_plan->mrr_buf_size= best_buf_size;
5613 (
"Returning range plan for key %s, cost %g, records %lu",
5614 param->table->key_info[param->real_keynr[idx]].
name,
5615 read_plan->read_cost, (ulong) read_plan->records));
5619 DBUG_PRINT(
"info", (
"No 'range' table read plan found"));
5621 DBUG_RETURN(read_plan);
5626 bool retrieve_full_rows,
5635 quick_imerge->records= records;
5636 quick_imerge->read_time= read_cost;
5637 for (
TRP_RANGE **range_scan= range_scans; range_scan != range_scans_end;
5641 ((*range_scan)->make_quick(param, FALSE, &quick_imerge->alloc)))||
5642 quick_imerge->push_quick_back(quick))
5645 delete quick_imerge;
5649 return quick_imerge;
5653 bool retrieve_full_rows,
5658 DBUG_ENTER(
"TRP_ROR_INTERSECT::make_quick");
5661 if ((quick_intrsect=
5663 (retrieve_full_rows? (!is_covering) :
5667 DBUG_EXECUTE(
"info", print_ror_scans_arr(param->table,
5668 "creating ROR-intersect",
5669 first_scan, last_scan););
5670 alloc= parent_alloc? parent_alloc: &quick_intrsect->alloc;
5672 current != last_scan;
5675 if (!(quick= get_quick_select(param, (*current)->idx,
5676 (*current)->sel_arg,
5679 quick_intrsect->push_quick_back(quick))
5681 delete quick_intrsect;
5687 if (!(quick= get_quick_select(param, cpk_scan->
idx,
5692 delete quick_intrsect;
5696 quick_intrsect->cpk_quick= quick;
5698 quick_intrsect->records= records;
5699 quick_intrsect->read_time= read_cost;
5701 DBUG_RETURN(quick_intrsect);
5706 bool retrieve_full_rows,
5712 DBUG_ENTER(
"TRP_ROR_UNION::make_quick");
5719 for (scan= first_ror; scan != last_ror; scan++)
5721 if (!(quick= (*scan)->make_quick(param, FALSE, &quick_roru->alloc)) ||
5722 quick_roru->push_quick_back(quick))
5725 quick_roru->records= records;
5726 quick_roru->read_time= read_cost;
5728 DBUG_RETURN(quick_roru);
5742 if_extended_explain_warn_index_not_applicable(
const RANGE_OPT_PARAM *param,
5746 if (param->using_real_indexes &&
5747 param->thd->lex->describe & DESCRIBE_EXTENDED)
5748 push_warning_printf(
5750 Sql_condition::WARN_LEVEL_WARN,
5751 ER_WARN_INDEX_NOT_APPLICABLE,
5752 ER(ER_WARN_INDEX_NOT_APPLICABLE),
5754 field->table->key_info[param->real_keynr[key_num]].
name,
5778 Item_result cmp_type)
5781 tree= get_mm_parts(param, cond_func, field, Item_func::LT_FUNC,
5782 lt_value, cmp_type);
5785 tree= tree_or(param, tree, get_mm_parts(param, cond_func, field,
5787 gt_value, cmp_type));
5812 Item_result cmp_type,
bool inv)
5815 DBUG_ENTER(
"get_func_mm_tree");
5817 switch (cond_func->functype()) {
5819 case Item_func::XOR_FUNC:
5823 case Item_func::NE_FUNC:
5824 tree= get_ne_mm_tree(param, cond_func, field, value, value, cmp_type);
5827 case Item_func::BETWEEN:
5833 tree= get_ne_mm_tree(param, cond_func, field, cond_func->arguments()[1],
5834 cond_func->arguments()[2], cmp_type);
5838 tree= get_mm_parts(param, cond_func, field, Item_func::GE_FUNC,
5839 cond_func->arguments()[1],cmp_type);
5842 tree= tree_and(param, tree, get_mm_parts(param, cond_func, field,
5844 cond_func->arguments()[2],
5850 tree= get_mm_parts(param, cond_func, field,
5852 (value == (
Item*)1 ? Item_func::GT_FUNC :
5853 Item_func::LT_FUNC):
5854 (value == (
Item*)1 ? Item_func::LE_FUNC :
5855 Item_func::GE_FUNC)),
5856 cond_func->arguments()[0], cmp_type);
5859 case Item_func::IN_FUNC:
5868 if (!func->arg_types_compatible)
5873 if (func->array && func->array->result_type() != ROW_RESULT)
5902 #define NOT_IN_IGNORE_THRESHOLD 1000
5903 MEM_ROOT *tmp_root= param->mem_root;
5904 param->thd->mem_root= param->old_root;
5913 Item *value_item= func->array->create_item();
5914 param->thd->mem_root= tmp_root;
5916 if (func->array->count > NOT_IN_IGNORE_THRESHOLD || !value_item)
5923 func->array->value_to_item(i, value_item);
5924 tree= get_mm_parts(param, cond_func, field, Item_func::LT_FUNC,
5925 value_item, cmp_type);
5929 }
while (i < func->array->count && tree->type == SEL_TREE::IMPOSSIBLE);
5931 if (!tree || tree->type == SEL_TREE::IMPOSSIBLE)
5938 for (; i < func->array->count; i++)
5940 if (func->array->compare_elems(i, i-1))
5943 func->array->value_to_item(i, value_item);
5944 tree2= get_mm_parts(param, cond_func, field, Item_func::LT_FUNC,
5945 value_item, cmp_type);
5953 for (uint idx= 0; idx < param->keys; idx++)
5955 SEL_ARG *new_interval, *last_val;
5956 if (((new_interval= tree2->keys[idx])) &&
5957 (tree->keys[idx]) &&
5958 ((last_val= tree->keys[idx]->last())))
5960 new_interval->min_value= last_val->max_value;
5961 new_interval->min_flag= NEAR_MIN;
5981 if (param->using_real_indexes)
5984 param->table->key_info[param->real_keynr[idx]];
5985 const KEY_PART_INFO *kpi= key.key_part + new_interval->part;
5987 if (kpi->key_part_flag & HA_PART_KEY_SEG)
5988 new_interval->min_flag= 0;
5996 tree= tree_or(param, tree, tree2);
6000 if (tree && tree->type != SEL_TREE::IMPOSSIBLE)
6006 tree2= get_mm_parts(param, cond_func, field, Item_func::GT_FUNC,
6007 value_item, cmp_type);
6008 tree= tree_or(param, tree, tree2);
6013 tree= get_ne_mm_tree(param, cond_func, field,
6014 func->arguments()[1], func->arguments()[1],
6019 for (arg= func->arguments()+2, end= arg+func->argument_count()-2;
6022 tree= tree_and(param, tree, get_ne_mm_tree(param, cond_func, field,
6023 *arg, *arg, cmp_type));
6030 tree= get_mm_parts(param, cond_func, field, Item_func::EQ_FUNC,
6031 func->arguments()[1], cmp_type);
6035 for (arg= func->arguments()+2, end= arg+func->argument_count()-2;
6038 tree= tree_or(param, tree, get_mm_parts(param, cond_func, field,
6055 Item_func::Functype func_type=
6056 (value != cond_func->arguments()[0]) ? cond_func->functype() :
6058 tree= get_mm_parts(param, cond_func, field, func_type, value, cmp_type);
6144 table_map ref_tables= 0;
6145 table_map param_comp= ~(param->prev_tables | param->read_tables |
6146 param->current_table);
6147 DBUG_ENTER(
"get_full_func_mm_tree");
6149 for (uint i= 0; i < cond_func->arg_count; i++)
6151 Item *arg= cond_func->arguments()[
i]->real_item();
6152 if (arg != field_item)
6153 ref_tables|= arg->used_tables();
6155 Field *field= field_item->field;
6156 Item_result cmp_type= field->cmp_type();
6157 if (!((ref_tables | field->table->map) & param_comp))
6158 ftree= get_func_mm_tree(param, cond_func, field, value, cmp_type, inv);
6159 Item_equal *item_equal= field_item->item_equal;
6164 while ((item= it++))
6166 Field *f= item->field;
6169 if (!((ref_tables | f->table->map) & param_comp))
6171 tree= get_func_mm_tree(param, cond_func, f, value, cmp_type, inv);
6172 ftree= !ftree ? tree : tree_and(param, ftree, tree);
6219 DBUG_ENTER(
"get_mm_tree");
6221 if (cond->type() == Item::COND_ITEM)
6225 if (((
Item_cond*) cond)->functype() == Item_func::COND_AND_FUNC)
6231 SEL_TREE *new_tree= get_mm_tree(param,item);
6232 if (param->statement_should_be_aborted())
6234 tree= tree_and(param,tree,new_tree);
6235 dbug_print_tree(
"after_and", tree, param);
6236 if (tree && tree->type == SEL_TREE::IMPOSSIBLE)
6242 tree= get_mm_tree(param,li++);
6243 if (param->statement_should_be_aborted())
6250 SEL_TREE *new_tree=get_mm_tree(param,item);
6251 if (new_tree == NULL || param->statement_should_be_aborted())
6253 tree= tree_or(param,tree,new_tree);
6254 dbug_print_tree(
"after_or", tree, param);
6255 if (tree == NULL || tree->type == SEL_TREE::ALWAYS)
6260 dbug_print_tree(
"tree_returned", tree, param);
6269 if (cond->const_item() && !cond->is_expensive() && !cond->
has_subquery())
6277 MEM_ROOT *tmp_root= param->mem_root;
6278 param->thd->mem_root= param->old_root;
6279 tree= cond->val_int() ?
new(tmp_root)
SEL_TREE(SEL_TREE::ALWAYS) :
6280 new(tmp_root)
SEL_TREE(SEL_TREE::IMPOSSIBLE);
6281 param->thd->mem_root= tmp_root;
6282 dbug_print_tree(
"tree_returned", tree, param);
6286 table_map ref_tables= 0;
6287 table_map param_comp= ~(param->prev_tables | param->read_tables |
6288 param->current_table);
6289 if (cond->type() != Item::FUNC_ITEM)
6291 ref_tables= cond->used_tables();
6292 if ((ref_tables & param->current_table) ||
6293 (ref_tables & ~(param->prev_tables | param->read_tables)))
6295 DBUG_RETURN(
new SEL_TREE(SEL_TREE::MAYBE));
6299 if (cond_func->functype() == Item_func::BETWEEN ||
6300 cond_func->functype() == Item_func::IN_FUNC)
6310 MEM_ROOT *tmp_root= param->mem_root;
6311 param->thd->mem_root= param->old_root;
6312 Item_func::optimize_type opt_type= cond_func->select_optimize();
6313 param->thd->mem_root= tmp_root;
6314 if (opt_type == Item_func::OPTIMIZE_NONE)
6320 switch (cond_func->functype()) {
6321 case Item_func::BETWEEN:
6322 if (cond_func->arguments()[0]->real_item()->type() == Item::FIELD_ITEM)
6324 field_item= (
Item_field*) (cond_func->arguments()[0]->real_item());
6325 ftree= get_full_func_mm_tree(param, cond_func, field_item, NULL, inv);
6332 for (uint i= 1 ; i < cond_func->arg_count ; i++)
6334 if (cond_func->arguments()[
i]->real_item()->type() == Item::FIELD_ITEM)
6336 field_item= (
Item_field*) (cond_func->arguments()[
i]->real_item());
6337 SEL_TREE *tmp= get_full_func_mm_tree(param, cond_func,
6338 field_item, (
Item*)(intptr)i, inv);
6341 tree= !tree ? tmp : tree_or(param, tree, tmp);
6346 tree= tree_and(param, tree, tmp);
6355 ftree = tree_and(param, ftree, tree);
6357 case Item_func::IN_FUNC:
6360 if (func->key_item()->real_item()->type() != Item::FIELD_ITEM)
6362 field_item= (
Item_field*) (func->key_item()->real_item());
6363 ftree= get_full_func_mm_tree(param, cond_func, field_item, NULL, inv);
6366 case Item_func::MULT_EQUAL_FUNC:
6369 if (!(value= item_equal->get_const()))
6372 ref_tables= value->used_tables();
6373 while ((field_item= it++))
6375 Field *field= field_item->field;
6376 Item_result cmp_type= field->cmp_type();
6377 if (!((ref_tables | field->table->map) & param_comp))
6379 tree= get_mm_parts(param, item_equal, field, Item_func::EQ_FUNC,
6381 ftree= !ftree ? tree : tree_and(param, ftree, tree);
6385 dbug_print_tree(
"tree_returned", ftree, param);
6390 DBUG_ASSERT (!ftree);
6391 if (cond_func->arguments()[0]->real_item()->type() == Item::FIELD_ITEM)
6393 field_item= (
Item_field*) (cond_func->arguments()[0]->real_item());
6394 value= cond_func->arg_count > 1 ? cond_func->arguments()[1] : NULL;
6395 ftree= get_full_func_mm_tree(param, cond_func, field_item, value, inv);
6413 if (!ftree && cond_func->have_rev_func() &&
6414 cond_func->arguments()[1]->real_item()->type() == Item::FIELD_ITEM)
6416 field_item= (
Item_field*) (cond_func->arguments()[1]->real_item());
6417 value= cond_func->arguments()[0];
6418 ftree= get_full_func_mm_tree(param, cond_func, field_item, value, inv);
6422 dbug_print_tree(
"tree_returned", ftree, param);
6437 bool is_spatial_operator(Item_func::Functype op_type)
6441 case Item_func::SP_EQUALS_FUNC:
6442 case Item_func::SP_DISJOINT_FUNC:
6443 case Item_func::SP_INTERSECTS_FUNC:
6444 case Item_func::SP_TOUCHES_FUNC:
6445 case Item_func::SP_CROSSES_FUNC:
6446 case Item_func::SP_WITHIN_FUNC:
6447 case Item_func::SP_CONTAINS_FUNC:
6448 case Item_func::SP_OVERLAPS_FUNC:
6449 case Item_func::SP_STARTPOINT:
6450 case Item_func::SP_ENDPOINT:
6451 case Item_func::SP_EXTERIORRING:
6452 case Item_func::SP_POINTN:
6453 case Item_func::SP_GEOMETRYN:
6454 case Item_func::SP_INTERIORRINGN:
6463 Item_func::Functype
type,
6464 Item *value, Item_result cmp_type)
6466 DBUG_ENTER(
"get_mm_parts");
6467 if (field->table != param->table)
6470 KEY_PART *key_part = param->key_parts;
6471 KEY_PART *end = param->key_parts_end;
6474 value->used_tables() & ~(param->prev_tables | param->read_tables))
6476 for (; key_part != end ; key_part++)
6478 if (field->eq(key_part->field))
6484 if (key_part->image_type != Field::itMBR &&
6485 is_spatial_operator(cond_func->functype()))
6489 if (!tree && !(tree=
new SEL_TREE()))
6491 if (!value || !(value->used_tables() & ~param->read_tables))
6493 sel_arg=get_mm_leaf(param,cond_func,
6494 key_part->field,key_part,type,value);
6497 if (sel_arg->type == SEL_ARG::IMPOSSIBLE)
6499 tree->type=SEL_TREE::IMPOSSIBLE;
6506 if (!(sel_arg=
new SEL_ARG(SEL_ARG::MAYBE_KEY)))
6509 sel_arg->part=(uchar) key_part->part;
6510 tree->keys[key_part->key]=sel_add(tree->keys[key_part->key],sel_arg);
6511 tree->keys_map.set_bit(key_part->key);
6515 if (tree && tree->merges.is_empty() && tree->keys_map.is_clear_all())
6543 static bool save_value_and_handle_conversion(
SEL_ARG **tree,
6545 const Item_func::Functype comp_op,
6547 const char **impossible_cond_cause,
6551 DBUG_ASSERT(*tree == NULL);
6564 const sql_mode_t orig_sql_mode= field->table->in_use->variables.sql_mode;
6565 field->table->in_use->variables.sql_mode|= MODE_INVALID_DATES;
6582 const type_conversion_status err= value->save_in_field_no_warnings(field, 1);
6583 field->table->in_use->variables.sql_mode= orig_sql_mode;
6587 case TYPE_NOTE_TRUNCATED:
6589 case TYPE_ERR_BAD_VALUE:
6601 case TYPE_ERR_NULL_CONSTRAINT_VIOLATION:
6603 *impossible_cond_cause=
"null_field_in_non_null_column";
6604 goto impossible_cond;
6605 case TYPE_WARN_OUT_OF_RANGE:
6611 if (comp_op == Item_func::EQUAL_FUNC || comp_op == Item_func::EQ_FUNC)
6617 *impossible_cond_cause=
"value_out_of_range";
6618 goto impossible_cond;
6622 if ((field->type() != FIELD_TYPE_BIT) &&
6623 (field->result_type() == REAL_RESULT ||
6624 field->result_type() == INT_RESULT ||
6625 field->result_type() == DECIMAL_RESULT))
6633 if ((field->val_int() > 0) ||
6634 (static_cast<Field_num*>(field)->unsigned_flag &&
6635 field->val_int() < 0))
6637 if (comp_op == Item_func::LT_FUNC || comp_op == Item_func::LE_FUNC)
6645 if (comp_op == Item_func::GT_FUNC || comp_op == Item_func::GE_FUNC)
6651 *impossible_cond_cause=
"value_out_of_range";
6652 goto impossible_cond;
6657 if (comp_op == Item_func::GT_FUNC || comp_op == Item_func::GE_FUNC)
6665 if (comp_op == Item_func::LT_FUNC || comp_op == Item_func::LE_FUNC)
6671 *impossible_cond_cause=
"value_out_of_range";
6672 goto impossible_cond;
6683 case TYPE_NOTE_TIME_TRUNCATED:
6684 if (field->type() == FIELD_TYPE_DATE &&
6685 (comp_op == Item_func::GT_FUNC || comp_op == Item_func::GE_FUNC ||
6686 comp_op == Item_func::LT_FUNC || comp_op == Item_func::LE_FUNC))
6708 if (comp_op == Item_func::EQ_FUNC || comp_op == Item_func::EQUAL_FUNC)
6711 goto impossible_cond;
6721 *tree=
new (memroot)
SEL_ARG(field, 0, 0);
6722 (*tree)->type= SEL_ARG::IMPOSSIBLE;
6728 KEY_PART *key_part, Item_func::Functype type,
Item *value)
6731 bool optimize_range;
6735 const char *impossible_cond_cause= NULL;
6736 DBUG_ENTER(
"get_mm_leaf");
6746 param->thd->mem_root= param->old_root;
6749 if (field->table->maybe_null)
6753 if (type == Item_func::ISNULL_FUNC)
6754 tree= &null_element;
6758 static_cast<uchar*
>(alloc_root(alloc, key_part->store_length + 1));
6762 TRASH(null_string, key_part->store_length + 1);
6763 memcpy(null_string, is_null_string,
sizeof(is_null_string));
6765 if (!(tree=
new (alloc)
SEL_ARG(field, null_string, null_string)))
6767 if (type == Item_func::ISNOTNULL_FUNC)
6769 tree->min_flag=NEAR_MIN;
6770 tree->max_flag=NO_MAX_RANGE;
6786 if ((field->result_type() == STRING_RESULT &&
6787 field->match_collation_to_optimize_range() &&
6788 value->result_type() == STRING_RESULT &&
6789 key_part->image_type == Field::itRAW &&
6790 field->charset() != conf_func->compare_collation() &&
6791 !(conf_func->compare_collation()->state & MY_CS_BINSORT &&
6792 (type == Item_func::EQUAL_FUNC || type == Item_func::EQ_FUNC))))
6794 if_extended_explain_warn_index_not_applicable(param, key_part->key, field);
6821 if ((!field->is_temporal() && value->is_temporal()) ||
6822 field_time_cmp_date(field, value))
6824 if_extended_explain_warn_index_not_applicable(param, key_part->key, field);
6828 if (key_part->image_type == Field::itMBR)
6832 case Item_func::SP_EQUALS_FUNC:
6833 case Item_func::SP_DISJOINT_FUNC:
6834 case Item_func::SP_INTERSECTS_FUNC:
6835 case Item_func::SP_TOUCHES_FUNC:
6836 case Item_func::SP_CROSSES_FUNC:
6837 case Item_func::SP_WITHIN_FUNC:
6838 case Item_func::SP_CONTAINS_FUNC:
6839 case Item_func::SP_OVERLAPS_FUNC:
6850 if (param->using_real_indexes)
6851 optimize_range= field->optimize_range(param->real_keynr[key_part->key],
6854 optimize_range= TRUE;
6856 if (type == Item_func::LIKE_FUNC)
6859 char buff1[MAX_FIELD_WIDTH];
6860 uchar *min_str,*max_str;
6861 String tmp(buff1,
sizeof(buff1),value->collation.collation),*res;
6862 size_t length,
offset, min_length, max_length;
6863 uint field_length= field->pack_length()+maybe_null;
6865 if (!optimize_range)
6867 if (!(res= value->val_str(&tmp)))
6869 tree= &null_element;
6883 if (field->cmp_type() != STRING_RESULT)
6887 length=key_part->store_length;
6889 if (length != key_part->length + maybe_null)
6892 offset+= HA_KEY_BLOB_LENGTH;
6893 field_length= length - HA_KEY_BLOB_LENGTH;
6897 if (unlikely(length < field_length))
6903 length= field_length;
6906 field_length= length;
6909 if (!(min_str= (uchar*) alloc_root(alloc, length*2)))
6912 max_str=min_str+length;
6914 max_str[0]= min_str[0]=0;
6916 field_length-= maybe_null;
6917 like_error= my_like_range(field->charset(),
6918 res->ptr(), res->length(),
6920 wild_one, wild_many,
6922 (
char*) min_str+
offset, (
char*) max_str+offset,
6923 &min_length, &max_length);
6927 if (offset != maybe_null)
6929 int2store(min_str+maybe_null,min_length);
6930 int2store(max_str+maybe_null,max_length);
6932 tree=
new (alloc)
SEL_ARG(field, min_str, max_str);
6936 if (!optimize_range &&
6937 type != Item_func::EQ_FUNC &&
6938 type != Item_func::EQUAL_FUNC)
6945 if (field->result_type() == STRING_RESULT &&
6946 value->result_type() != STRING_RESULT &&
6947 field->cmp_type() != value->result_type())
6949 if_extended_explain_warn_index_not_applicable(param, key_part->key, field);
6953 if (save_value_and_handle_conversion(&tree, value, type, field,
6954 &impossible_cond_cause, alloc))
6961 if (type != Item_func::EQUAL_FUNC && field->is_real_null())
6963 impossible_cond_cause=
"comparison_with_null_always_false";
6964 tree= &null_element;
6968 str= (uchar*) alloc_root(alloc, key_part->store_length+1);
6972 *str= (uchar) field->is_real_null();
6973 field->get_key_image(str+maybe_null, key_part->length,
6974 key_part->image_type);
6975 if (!(tree=
new (alloc)
SEL_ARG(field, str, str)))
6989 if (field->result_type() == INT_RESULT &&
6990 value->result_type() == INT_RESULT &&
6991 ((field->type() == FIELD_TYPE_BIT ||
6992 ((
Field_num *) field)->unsigned_flag) &&
6993 !((
Item_int*) value)->unsigned_flag))
6995 longlong item_val= value->val_int();
6998 if (type == Item_func::LT_FUNC || type == Item_func::LE_FUNC)
7000 impossible_cond_cause=
"unsigned_int_cannot_be_negative";
7001 tree->type= SEL_ARG::IMPOSSIBLE;
7004 if (type == Item_func::GT_FUNC || type == Item_func::GE_FUNC)
7013 case Item_func::LT_FUNC:
7014 if (stored_field_cmp_to_item(param->thd, field, value) == 0)
7015 tree->max_flag=NEAR_MAX;
7017 case Item_func::LE_FUNC:
7019 tree->min_flag=NO_MIN_RANGE;
7022 if (!(tree->min_value=
7023 static_cast<uchar*>(alloc_root(alloc, key_part->store_length+1))))
7025 TRASH(tree->min_value, key_part->store_length + 1);
7026 memcpy(tree->min_value, is_null_string,
sizeof(is_null_string));
7027 tree->min_flag=NEAR_MIN;
7030 case Item_func::GT_FUNC:
7032 if ((!(key_part->flag & HA_PART_KEY_SEG)) &&
7033 (stored_field_cmp_to_item(param->thd, field, value) <= 0))
7034 tree->min_flag=NEAR_MIN;
7035 tree->max_flag= NO_MAX_RANGE;
7037 case Item_func::GE_FUNC:
7039 if ((!(key_part->flag & HA_PART_KEY_SEG)) &&
7040 (stored_field_cmp_to_item(param->thd, field, value) < 0))
7041 tree->min_flag= NEAR_MIN;
7042 tree->max_flag=NO_MAX_RANGE;
7044 case Item_func::SP_EQUALS_FUNC:
7045 tree->min_flag=GEOM_FLAG | HA_READ_MBR_EQUAL;
7046 tree->max_flag=NO_MAX_RANGE;
7048 case Item_func::SP_DISJOINT_FUNC:
7049 tree->min_flag=GEOM_FLAG | HA_READ_MBR_DISJOINT;
7050 tree->max_flag=NO_MAX_RANGE;
7052 case Item_func::SP_INTERSECTS_FUNC:
7053 tree->min_flag=GEOM_FLAG | HA_READ_MBR_INTERSECT;
7054 tree->max_flag=NO_MAX_RANGE;
7056 case Item_func::SP_TOUCHES_FUNC:
7057 tree->min_flag=GEOM_FLAG | HA_READ_MBR_INTERSECT;
7058 tree->max_flag=NO_MAX_RANGE;
7061 case Item_func::SP_CROSSES_FUNC:
7062 tree->min_flag=GEOM_FLAG | HA_READ_MBR_INTERSECT;
7063 tree->max_flag=NO_MAX_RANGE;
7065 case Item_func::SP_WITHIN_FUNC:
7070 tree->min_flag=GEOM_FLAG | HA_READ_MBR_CONTAIN;
7071 tree->max_flag=NO_MAX_RANGE;
7074 case Item_func::SP_CONTAINS_FUNC:
7079 tree->min_flag=GEOM_FLAG | HA_READ_MBR_WITHIN;
7080 tree->max_flag=NO_MAX_RANGE;
7082 case Item_func::SP_OVERLAPS_FUNC:
7083 tree->min_flag=GEOM_FLAG | HA_READ_MBR_INTERSECT;
7084 tree->max_flag=NO_MAX_RANGE;
7092 if (impossible_cond_cause != NULL)
7096 Opt_trace_context::RANGE_OPTIMIZER).
7097 add_alnum(
"cause", impossible_cond_cause);
7099 param->thd->mem_root= alloc;
7132 while (key1 && key2)
7134 if (key1->part < key2->part)
7137 key_link= &key1->next_key_part;
7138 key1=key1->next_key_part;
7143 key_link= &key2->next_key_part;
7144 key2=key2->next_key_part;
7147 *key_link=key1 ? key1 : key2;
7151 #define CLONE_KEY1_MAYBE 1
7152 #define CLONE_KEY2_MAYBE 2
7153 #define swap_clone_flag(A) ((A & 1) << 1) | ((A & 2) >> 1)
7159 DBUG_ENTER(
"tree_and");
7164 if (tree1->type == SEL_TREE::IMPOSSIBLE || tree2->type == SEL_TREE::ALWAYS)
7166 if (tree2->type == SEL_TREE::IMPOSSIBLE || tree1->type == SEL_TREE::ALWAYS)
7168 if (tree1->type == SEL_TREE::MAYBE)
7170 if (tree2->type == SEL_TREE::KEY)
7171 tree2->type=SEL_TREE::KEY_SMALLER;
7174 if (tree2->type == SEL_TREE::MAYBE)
7176 tree1->type=SEL_TREE::KEY_SMALLER;
7180 dbug_print_tree(
"tree1", tree1, param);
7181 dbug_print_tree(
"tree2", tree2, param);
7187 for (key1= tree1->keys,key2= tree2->keys,end=key1+param->keys ;
7188 key1 != end ; key1++,key2++)
7193 if (*key1 && !(*key1)->simple_key())
7194 flag|=CLONE_KEY1_MAYBE;
7195 if (*key2 && !(*key2)->simple_key())
7196 flag|=CLONE_KEY2_MAYBE;
7197 *key1=key_and(param, *key1, *key2, flag);
7198 if (*key1 && (*key1)->type == SEL_ARG::IMPOSSIBLE)
7200 tree1->type= SEL_TREE::IMPOSSIBLE;
7203 result_keys.set_bit(key1 - tree1->keys);
7205 if (*key1 && param->alloced_sel_args < SEL_ARG::MAX_SEL_ARGS)
7206 (*key1)->test_use_count(*key1);
7210 tree1->keys_map= result_keys;
7213 imerge_list_and_list(&tree1->merges, &tree2->merges);
7227 key_map common_keys= tree1->keys_map;
7228 DBUG_ENTER(
"sel_trees_can_be_ored");
7229 common_keys.intersect(tree2->keys_map);
7231 dbug_print_tree(
"tree1", tree1, param);
7232 dbug_print_tree(
"tree2", tree2, param);
7234 if (common_keys.is_clear_all())
7239 for (uint key_no=0; key_no < param->keys; key_no++)
7241 if (common_keys.is_set(key_no))
7243 key1= tree1->keys + key_no;
7244 key2= tree2->keys + key_no;
7245 if ((*key1)->part == (*key2)->part)
7311 for (uint i=0; i < param->keys; i++)
7315 if (tree->keys[i]->part)
7317 tree->keys[
i]= NULL;
7318 tree->keys_map.clear_bit(i);
7331 DBUG_ENTER(
"tree_or");
7332 if (!tree1 || !tree2)
7334 if (tree1->type == SEL_TREE::IMPOSSIBLE || tree2->type == SEL_TREE::ALWAYS)
7336 if (tree2->type == SEL_TREE::IMPOSSIBLE || tree1->type == SEL_TREE::ALWAYS)
7338 if (tree1->type == SEL_TREE::MAYBE)
7340 if (tree2->type == SEL_TREE::MAYBE)
7359 if (!tree1->merges.is_empty())
7361 for (uint i= 0; i < param->keys; i++)
7362 if (tree1->keys[i] != NULL && tree2->keys[i] != &null_element)
7364 tree1->merges.empty();
7368 if (!tree2->merges.is_empty())
7370 for (uint i= 0; i< param->keys; i++)
7371 if (tree2->keys[i] != NULL && tree2->keys[i] != &null_element)
7373 tree2->merges.empty();
7380 if (sel_trees_can_be_ored(tree1, tree2, param))
7384 for (key1= tree1->keys,key2= tree2->keys,end= key1+param->keys ;
7385 key1 != end ; key1++,key2++)
7387 *key1=key_or(param, *key1, *key2);
7391 result_keys.set_bit(key1 - tree1->keys);
7393 if (param->alloced_sel_args < SEL_ARG::MAX_SEL_ARGS)
7394 (*key1)->test_use_count(*key1);
7399 result->keys_map= result_keys;
7404 if (tree1->merges.is_empty() && tree2->merges.is_empty())
7406 if (param->remove_jump_scans)
7408 bool no_trees= remove_nonrange_trees(param, tree1);
7409 no_trees= no_trees || remove_nonrange_trees(param, tree2);
7411 DBUG_RETURN(
new SEL_TREE(SEL_TREE::ALWAYS));
7416 (result->merges.push_back(merge)) ||
7417 (merge->or_sel_tree(param, tree1)) ||
7418 (merge->or_sel_tree(param, tree2)))
7421 result->type= tree1->type;
7423 else if (!tree1->merges.is_empty() && !tree2->merges.is_empty())
7425 if (imerge_list_or_list(param, &tree1->merges, &tree2->merges))
7426 result=
new SEL_TREE(SEL_TREE::ALWAYS);
7433 if (tree1->merges.is_empty())
7434 swap_variables(
SEL_TREE*, tree1, tree2);
7436 if (param->remove_jump_scans && remove_nonrange_trees(param, tree2))
7437 DBUG_RETURN(
new SEL_TREE(SEL_TREE::ALWAYS));
7439 if (imerge_list_or_tree(param, &tree1->merges, tree2))
7440 result=
new SEL_TREE(SEL_TREE::ALWAYS);
7445 DBUG_RETURN(result);
7456 ulong use_count=key1->use_count;
7458 if (key1->elements != 1)
7460 key2->use_count+=key1->elements-1;
7461 key2->increment_use_count((
int) key1->elements-1);
7463 if (key1->type == SEL_ARG::MAYBE_KEY)
7466 DBUG_ASSERT(!key1->left);
7467 DBUG_ASSERT(!key1->right);
7468 key1->next= key1->prev= 0;
7470 for (next=key1->first(); next ; next=next->next)
7472 if (next->next_key_part)
7474 SEL_ARG *tmp= key_and(param, next->next_key_part, key2, clone_flag);
7475 if (tmp && tmp->type == SEL_ARG::IMPOSSIBLE)
7477 key1=key1->tree_delete(next);
7480 next->next_key_part=tmp;
7482 next->increment_use_count(use_count);
7483 if (param->alloced_sel_args > SEL_ARG::MAX_SEL_ARGS)
7487 next->next_key_part=key2;
7490 return &null_element;
7518 if (key1->part != key2->part)
7520 if (key1->part > key2->part)
7522 swap_variables(
SEL_ARG *, key1, key2);
7523 clone_flag=swap_clone_flag(clone_flag);
7527 if (key1->use_count > 0)
7528 if (!(key1= key1->clone_tree(param)))
7530 return and_all_keys(param, key1, key2, clone_flag);
7533 if (((clone_flag & CLONE_KEY2_MAYBE) &&
7534 !(clone_flag & CLONE_KEY1_MAYBE) &&
7535 key2->type != SEL_ARG::MAYBE_KEY) ||
7536 key1->type == SEL_ARG::MAYBE_KEY)
7538 swap_variables(
SEL_ARG *, key1, key2);
7539 clone_flag=swap_clone_flag(clone_flag);
7543 if (key2->type == SEL_ARG::MAYBE_KEY)
7545 if (key1->use_count > 1)
7548 if (!(key1=key1->clone_tree(param)))
7552 if (key1->type == SEL_ARG::MAYBE_KEY)
7554 key1->next_key_part=key_and(param, key1->next_key_part,
7555 key2->next_key_part, clone_flag);
7556 if (key1->next_key_part &&
7557 key1->next_key_part->type == SEL_ARG::IMPOSSIBLE)
7562 key1->maybe_smaller();
7563 if (key2->next_key_part)
7566 return and_all_keys(param, key1, key2, clone_flag);
7573 if ((key1->min_flag | key2->min_flag) & GEOM_FLAG)
7583 SEL_ARG *e1=key1->first(), *e2=key2->first(), *new_tree=0;
7587 int cmp=e1->cmp_min_to_min(e2);
7590 if (get_range(&e1,&e2,key1))
7593 else if (get_range(&e2,&e1,key2))
7595 SEL_ARG *next=key_and(param, e1->next_key_part, e2->next_key_part,
7597 e1->increment_use_count(1);
7598 e2->increment_use_count(1);
7599 if (!next || next->type != SEL_ARG::IMPOSSIBLE)
7601 SEL_ARG *new_arg= e1->clone_and(e2);
7603 return &null_element;
7604 new_arg->next_key_part=next;
7610 new_tree=new_tree->insert(new_arg);
7612 if (e1->cmp_max_to_max(e2) < 0)
7620 return &null_element;
7628 (*e1)=root1->find_range(*e2);
7629 if ((*e1)->cmp_max_to_min(*e2) < 0)
7631 if (!((*e1)=(*e1)->next))
7633 if ((*e1)->cmp_min_to_max(*e2) > 0)
7725 if (key1->part != key2->part ||
7726 (key1->min_flag | key2->min_flag) & GEOM_FLAG)
7734 if (key1->type == SEL_ARG::MAYBE_KEY)
7740 if (key2->type == SEL_ARG::MAYBE_KEY)
7747 if (key1->use_count > 0)
7749 if (key2->use_count == 0 || key1->elements > key2->elements)
7751 swap_variables(
SEL_ARG *,key1,key2);
7753 if (key1->use_count > 0 || !(key1=key1->clone_tree(param)))
7758 const bool key2_shared= (key2->use_count != 0);
7759 key1->maybe_flag|= key2->maybe_flag;
7784 SEL_ARG *cur_key2= key2->first();
7799 SEL_ARG *cur_key1= key1->find_range(cur_key2);
7833 cur_key1= key1->first();
7836 else if ((cmp= cur_key1->cmp_max_to_min(cur_key2)) < 0)
7843 SEL_ARG *next_key1= cur_key1->next;
7845 eq_tree(cur_key1->next_key_part, cur_key2->next_key_part))
7858 SEL_ARG *next_key2= cur_key2->next;
7861 if (!(cur_key2=
new SEL_ARG(*cur_key2)))
7863 cur_key2->increment_use_count(key1->use_count+1);
7864 cur_key2->next= next_key2;
7867 if (cur_key2->copy_min(cur_key1))
7872 key1->type= SEL_ARG::ALWAYS;
7873 key2->type= SEL_ARG::ALWAYS;
7874 if (key1->maybe_flag)
7875 return new SEL_ARG(SEL_ARG::MAYBE_KEY);
7879 if (!(key1= key1->tree_delete(cur_key1)))
7887 cur_key2= next_key2;
7892 if (!(cur_key1= next_key1))
7904 if ((cur_key1_cmp= cur_key1->cmp_min_to_max(cur_key2)) > 0)
7911 if (cur_key1_cmp == 2 &&
7912 eq_tree(cur_key1->next_key_part, cur_key2->next_key_part))
7927 cur_key1->copy_min_to_min(cur_key2);
7928 key1->merge_flags(cur_key2);
7929 if (cur_key1->min_flag & NO_MIN_RANGE &&
7930 cur_key1->max_flag & NO_MAX_RANGE)
7932 if (key1->maybe_flag)
7933 return new SEL_ARG(SEL_ARG::MAYBE_KEY);
7936 cur_key2->increment_use_count(-1);
7937 cur_key2=cur_key2->next;
7955 SEL_ARG *next_key2= cur_key2->next;
7961 key1= key1->insert(cpy);
7962 cur_key2->increment_use_count(key1->use_count+1);
7965 key1= key1->insert(cur_key2);
7966 cur_key2= next_key2;
7980 if (eq_tree(cur_key1->next_key_part, cur_key2->next_key_part))
7983 if (cur_key1->is_same(cur_key2))
7989 cur_key1->merge_flags(cur_key2);
7990 cur_key2->increment_use_count(-1);
8024 while (last->next && last->next->cmp_min_to_max(cur_key2) <= 0 &&
8025 eq_tree(last->next->next_key_part, cur_key2->next_key_part))
8033 key1= key1->tree_delete(save);
8044 bool full_range= last->copy_min(first);
8046 full_range= last->copy_min(cur_key2);
8050 if (last->next && cur_key2->cmp_max_to_min(last->next) >= 0)
8063 last->copy_min_to_max(last->next);
8077 full_range= last->copy_max(cur_key2);
8082 key1->type= SEL_ARG::ALWAYS;
8083 key2->type= SEL_ARG::ALWAYS;
8084 for (; cur_key2 ; cur_key2= cur_key2->next)
8085 cur_key2->increment_use_count(-1);
8086 if (key1->maybe_flag)
8087 return new SEL_ARG(SEL_ARG::MAYBE_KEY);
8093 if (cmp >= 0 && cur_key1->cmp_min_to_min(cur_key2) < 0)
8101 if (!cur_key1->next_key_part)
8111 if (cur_key1->cmp_max_to_max(cur_key2) >= 0)
8120 cur_key2->increment_use_count(-1);
8121 cur_key2= cur_key2->next;
8135 cur_key2->copy_max_to_min(cur_key1);
8152 SEL_ARG *new_arg= cur_key1->clone_first(cur_key2);
8155 if ((new_arg->next_key_part= cur_key1->next_key_part))
8156 new_arg->increment_use_count(key1->use_count+1);
8157 cur_key1->copy_min_to_min(cur_key2);
8158 key1= key1->insert(new_arg);
8169 if (cur_key1->cmp_min_to_min(&key2_cpy) > 0)
8184 SEL_ARG *new_arg=key2_cpy.clone_first(cur_key1);
8187 if ((new_arg->next_key_part=key2_cpy.next_key_part))
8188 new_arg->increment_use_count(key1->use_count+1);
8189 key1= key1->insert(new_arg);
8190 key2_cpy.copy_min_to_min(cur_key1);
8194 if ((cmp= cur_key1->cmp_max_to_max(&key2_cpy)) <= 0)
8211 cur_key1->maybe_flag|= key2_cpy.maybe_flag;
8212 key2_cpy.increment_use_count(key1->use_count+1);
8213 cur_key1->next_key_part=
8214 key_or(param, cur_key1->next_key_part, key2_cpy.next_key_part);
8220 key2_cpy.copy_max_to_min(cur_key1);
8221 if (!(cur_key1= cur_key1->next))
8228 if (!new_key1_range)
8230 key1= key1->insert(new_key1_range);
8231 cur_key2= cur_key2->next;
8234 if (cur_key1->cmp_min_to_max(&key2_cpy) > 0)
8242 if (!new_key1_range)
8244 key1= key1->insert(new_key1_range);
8279 if (!cur_key1->next_key_part)
8281 key2_cpy.increment_use_count(-1);
8284 SEL_ARG *new_arg= cur_key1->clone_last(&key2_cpy);
8287 cur_key1->copy_max_to_min(&key2_cpy);
8288 cur_key1->increment_use_count(key1->use_count+1);
8290 key2_cpy.increment_use_count(1);
8291 new_arg->next_key_part= key_or(param, cur_key1->next_key_part,
8292 key2_cpy.next_key_part);
8293 key1= key1->insert(new_arg);
8298 cur_key2= cur_key2->next;
8308 SEL_ARG *next= cur_key2->next;
8314 cur_key2->increment_use_count(key1->use_count+1);
8315 key1= key1->insert(key2_cpy);
8318 key1= key1->insert(cur_key2);
8333 if (!a || !b || !a->is_same(b))
8335 if (a->left != &null_element && b->left != &null_element)
8337 if (!eq_tree(a->left,b->left))
8340 else if (a->left != &null_element || b->left != &null_element)
8342 if (a->right != &null_element && b->right != &null_element)
8344 if (!eq_tree(a->right,b->right))
8347 else if (a->right != &null_element || b->right != &null_element)
8349 if (a->next_key_part != b->next_key_part)
8351 if (!a->next_key_part != !b->next_key_part ||
8352 !eq_tree(a->next_key_part, b->next_key_part))
8362 SEL_ARG *element,**UNINIT_VAR(par),*UNINIT_VAR(last_element);
8364 for (element=
this; element != &null_element ; )
8366 last_element=element;
8367 if (key->cmp_min_to_min(element) > 0)
8369 par= &element->right; element= element->right;
8373 par = &element->left; element= element->left;
8377 key->parent=last_element;
8379 if (par == &last_element->left)
8381 key->next=last_element;
8382 if ((key->prev=last_element->prev))
8383 key->prev->next=key;
8384 last_element->prev=key;
8388 if ((key->next=last_element->next))
8389 key->next->prev=key;
8390 key->prev=last_element;
8391 last_element->next=key;
8393 key->left=key->right= &null_element;
8395 root->use_count=this->use_count;
8396 root->elements= this->elements+1;
8397 root->maybe_flag=this->maybe_flag;
8408 SEL_ARG::find_range(
SEL_ARG *key)
8410 SEL_ARG *element=
this,*found=0;
8414 if (element == &null_element)
8416 int cmp=element->cmp_min_to_min(key);
8422 element=element->right;
8425 element=element->left;
8445 SEL_ARG::tree_delete(
SEL_ARG *key)
8447 enum leaf_color remove_color;
8448 SEL_ARG *root,*nod,**par,*fix_par;
8449 DBUG_ENTER(
"tree_delete");
8456 key->prev->next=key->next;
8458 key->next->prev=key->prev;
8459 key->increment_use_count(-1);
8463 par=key->parent_ptr();
8465 if (key->left == &null_element)
8467 *par=nod=key->right;
8468 fix_par=key->parent;
8469 if (nod != &null_element)
8470 nod->parent=fix_par;
8471 remove_color= key->color;
8473 else if (key->right == &null_element)
8475 *par= nod=key->left;
8476 nod->parent=fix_par=key->parent;
8477 remove_color= key->color;
8482 nod= *tmp->parent_ptr()= tmp->right;
8483 fix_par=tmp->parent;
8484 if (nod != &null_element)
8485 nod->parent=fix_par;
8486 remove_color= tmp->color;
8488 tmp->parent=key->parent;
8489 (tmp->left=key->left)->parent=tmp;
8490 if ((tmp->right=key->right) != &null_element)
8491 tmp->right->parent=tmp;
8492 tmp->color=key->color;
8498 if (root == &null_element)
8500 if (remove_color == BLACK)
8501 root=rb_delete_fixup(root,nod,fix_par);
8503 test_rb_tree(root,root->parent);
8505 root->use_count=this->use_count;
8506 root->elements=this->elements-1;
8507 root->maybe_flag=this->maybe_flag;
8517 leaf->right=y->left;
8518 if (y->left != &null_element)
8519 y->left->parent=leaf;
8520 if (!(y->parent=leaf->parent))
8523 *leaf->parent_ptr()=y;
8531 leaf->left=y->right;
8532 if (y->right != &null_element)
8533 y->right->parent=leaf;
8534 if (!(y->parent=leaf->parent))
8537 *leaf->parent_ptr()=y;
8544 SEL_ARG::rb_insert(
SEL_ARG *leaf)
8547 root=
this; root->parent= 0;
8550 while (leaf != root && (par= leaf->parent)->color == RED)
8552 if (par == (par2= leaf->parent->parent)->left)
8555 if (y->color == RED)
8564 if (leaf == par->right)
8566 left_rotate(&root,leaf->parent);
8571 right_rotate(&root,par2);
8578 if (y->color == RED)
8587 if (leaf == par->left)
8589 right_rotate(&root,par);
8594 left_rotate(&root,par2);
8601 test_rb_tree(root,root->parent);
8613 while (x != root && x->color == SEL_ARG::BLACK)
8618 if (w->color == SEL_ARG::RED)
8620 w->color=SEL_ARG::BLACK;
8621 par->color=SEL_ARG::RED;
8622 left_rotate(&root,par);
8625 if (w->left->color == SEL_ARG::BLACK && w->right->color == SEL_ARG::BLACK)
8627 w->color=SEL_ARG::RED;
8632 if (w->right->color == SEL_ARG::BLACK)
8634 w->left->color=SEL_ARG::BLACK;
8635 w->color=SEL_ARG::RED;
8636 right_rotate(&root,w);
8639 w->color=par->color;
8640 par->color=SEL_ARG::BLACK;
8641 w->right->color=SEL_ARG::BLACK;
8642 left_rotate(&root,par);
8650 if (w->color == SEL_ARG::RED)
8652 w->color=SEL_ARG::BLACK;
8653 par->color=SEL_ARG::RED;
8654 right_rotate(&root,par);
8657 if (w->right->color == SEL_ARG::BLACK && w->left->color == SEL_ARG::BLACK)
8659 w->color=SEL_ARG::RED;
8664 if (w->left->color == SEL_ARG::BLACK)
8666 w->right->color=SEL_ARG::BLACK;
8667 w->color=SEL_ARG::RED;
8668 left_rotate(&root,w);
8671 w->color=par->color;
8672 par->color=SEL_ARG::BLACK;
8673 w->left->color=SEL_ARG::BLACK;
8674 right_rotate(&root,par);
8681 x->color=SEL_ARG::BLACK;
8691 int count_l,count_r;
8693 if (element == &null_element)
8695 if (element->parent != parent)
8697 sql_print_error(
"Wrong tree: Parent doesn't point at parent");
8700 if (element->color == SEL_ARG::RED &&
8701 (element->left->color == SEL_ARG::RED ||
8702 element->right->color == SEL_ARG::RED))
8704 sql_print_error(
"Wrong tree: Found two red in a row");
8707 if (element->left == element->right && element->left != &null_element)
8709 sql_print_error(
"Wrong tree: Found right == left");
8712 count_l=test_rb_tree(element->left,element);
8713 count_r=test_rb_tree(element->right,element);
8714 if (count_l >= 0 && count_r >= 0)
8716 if (count_l == count_r)
8717 return count_l+(element->color == SEL_ARG::BLACK);
8718 sql_print_error(
"Wrong tree: Incorrect black-count: %d - %d",
8771 for (root=root->first(); root ; root=root->next)
8773 if (root->next_key_part)
8775 if (root->next_key_part == key)
8777 if (root->next_key_part->part < key->part)
8778 count+=count_key_part_usage(root->next_key_part,key);
8800 void SEL_ARG::test_use_count(
SEL_ARG *root)
8803 if (
this == root && use_count != 1)
8805 sql_print_information(
"Use_count: Wrong count %lu for root",use_count);
8809 if (this->type != SEL_ARG::KEY_RANGE)
8811 for (
SEL_ARG *pos=first(); pos ; pos=pos->next)
8814 if (pos->next_key_part)
8816 ulong count=count_key_part_usage(root,pos->next_key_part);
8817 if (count > pos->next_key_part->use_count)
8819 sql_print_information(
"Use_count: Wrong count for key at 0x%lx, %lu "
8820 "should be %lu", (
long unsigned int)pos,
8821 pos->next_key_part->use_count, count);
8825 pos->next_key_part->test_use_count(root);
8828 if (e_count != elements)
8830 sql_print_warning(
"Wrong use count: %u (should be %u) for tree at 0x%lx",
8831 e_count, elements, (
long unsigned int)
this);
8848 uchar *min_key, *max_key;
8854 uint min_key_flag, max_key_flag;
8857 uint min_key_parts, max_key_parts;
8928 PARAM *
const param;
8936 stack[0].min_key= (uchar*)param->min_key;
8937 stack[0].min_key_flag= 0;
8938 stack[0].min_key_parts= 0;
8940 stack[0].max_key= (uchar*)param->max_key;
8941 stack[0].max_key_flag= 0;
8942 stack[0].max_key_parts= 0;
8946 bool stack_empty()
const {
return (curr_kp == -1); }
8948 void stack_push_range(
SEL_ARG *key_tree);
8950 void stack_pop_range()
8952 DBUG_ASSERT(!stack_empty());
8959 int stack_size()
const {
return curr_kp + 1; }
8963 return stack_empty() ? NULL : &stack[curr_kp];
8981 range_seq_t sel_arg_range_seq_init(
void *init_param, uint n_ranges, uint
flags)
8990 void Sel_arg_range_sequence::stack_push_range(
SEL_ARG *key_tree)
8993 DBUG_ASSERT((uint)curr_kp+1 < MAX_REF_PARTS);
9012 push_position->min_key_flag= key_tree->min_flag;
9013 push_position->max_key_flag= key_tree->max_flag;
9017 push_position->min_key= last_added_kp->min_key;
9018 push_position->max_key= last_added_kp->max_key;
9019 push_position->min_key_parts= last_added_kp->min_key_parts;
9020 push_position->max_key_parts= last_added_kp->max_key_parts;
9021 push_position->min_key_flag= last_added_kp->min_key_flag |
9023 push_position->max_key_flag= last_added_kp->max_key_flag |
9028 uint16 stor_length= param->key[keyno][key_tree->part].store_length;
9034 push_position->min_key_parts+=
9035 key_tree->store_min(stor_length, &push_position->min_key,
9036 last_added_kp ? last_added_kp->min_key_flag : 0);
9037 push_position->max_key_parts+=
9038 key_tree->store_max(stor_length, &push_position->max_key,
9039 last_added_kp ? last_added_kp->max_key_flag : 0);
9041 if (key_tree->is_null_interval())
9042 push_position->min_key_flag |= NULL_RANGE;
9081 if (seq->stack_empty())
9088 key_tree= seq->start;
9095 key_tree= key_tree->first();
9096 seq->stack_push_range(key_tree);
9111 key_tree= seq->stack_top()->
key_tree;
9112 seq->stack_pop_range();
9116 DBUG_ASSERT(key_tree->next != &null_element);
9117 key_tree= key_tree->next;
9123 seq->stack_push_range(key_tree);
9124 seq->param->is_ror_scan= FALSE;
9128 if (seq->stack_empty())
9141 DBUG_ASSERT(!seq->stack_empty());
9151 while (key_tree->next_key_part &&
9152 key_tree->next_key_part != &null_element &&
9153 key_tree->next_key_part->part == key_tree->part + 1 &&
9154 key_tree->next_key_part->type == SEL_ARG::KEY_RANGE)
9157 DBUG_PRINT(
"info", (
"while(): key_tree->part %d",key_tree->part));
9159 const uint min_key_total_length= cur->min_key - seq->param->min_key;
9160 const uint max_key_total_length= cur->max_key - seq->param->max_key;
9176 uchar* min_key_start;
9177 uchar* max_key_start;
9178 uint cur_key_length;
9180 if (seq->stack_size() == 1)
9182 min_key_start= seq->param->min_key;
9183 max_key_start= seq->param->max_key;
9184 cur_key_length= min_key_total_length;
9189 min_key_start= prev.min_key;
9190 max_key_start= prev.max_key;
9191 cur_key_length= cur->min_key - prev.min_key;
9194 if ((min_key_total_length != max_key_total_length) ||
9195 (memcmp(min_key_start, max_key_start, cur_key_length)) ||
9196 (key_tree->min_flag || key_tree->max_flag))
9198 DBUG_PRINT(
"info", (
"while(): inside if()"));
9226 SEL_ARG *store_key_part= key_tree->next_key_part;
9227 seq->param->is_ror_scan= FALSE;
9228 if (!key_tree->min_flag)
9229 cur->min_key_parts +=
9230 store_key_part->store_min_key(seq->param->key[seq->keyno],
9234 if (!key_tree->max_flag)
9235 cur->max_key_parts +=
9236 store_key_part->store_max_key(seq->param->key[seq->keyno],
9251 key_tree= key_tree->next_key_part->first();
9252 seq->stack_push_range(key_tree);
9255 DBUG_ASSERT(!seq->stack_empty() && (seq->stack_top() != NULL));
9259 PARAM *param= seq->param;
9260 uint min_key_length= cur->min_key - param->min_key;
9262 if (cur->min_key_flag & GEOM_FLAG)
9264 range->range_flag= cur->min_key_flag;
9267 range->start_key.key= param->min_key;
9268 range->start_key.length= min_key_length;
9269 range->start_key.keypart_map= make_prev_keypart_map(cur->min_key_parts);
9270 range->start_key.flag= (ha_rkey_function) (cur->min_key_flag ^ GEOM_FLAG);
9275 DBUG_ASSERT(!param->is_ror_scan);
9279 const KEY *cur_key_info= ¶m->table->key_info[seq->real_keyno];
9280 range->range_flag= cur->min_key_flag | cur->max_key_flag;
9282 range->start_key.key= param->min_key;
9283 range->start_key.length= cur->min_key - param->min_key;
9284 range->start_key.keypart_map= make_prev_keypart_map(cur->min_key_parts);
9285 range->start_key.flag= (cur->min_key_flag & NEAR_MIN ? HA_READ_AFTER_KEY :
9288 range->end_key.key= param->max_key;
9289 range->end_key.length= cur->max_key - param->max_key;
9290 range->end_key.keypart_map= make_prev_keypart_map(cur->max_key_parts);
9291 range->end_key.flag= (cur->max_key_flag & NEAR_MAX ? HA_READ_BEFORE_KEY :
9301 const uint is_open_range= (NO_MIN_RANGE | NO_MAX_RANGE |
9302 NEAR_MIN | NEAR_MAX | GEOM_FLAG);
9303 const bool is_eq_range_pred=
9304 !(cur->min_key_flag & is_open_range) &&
9305 !(cur->max_key_flag & is_open_range) &&
9306 range->start_key.length == range->end_key.length &&
9307 !memcmp(param->min_key, param->max_key, range->start_key.length);
9309 if (is_eq_range_pred)
9311 range->range_flag= EQ_RANGE;
9317 range->range_flag|= USE_INDEX_STATISTICS;
9325 if (cur_key_info->
flags & HA_NOSAME &&
9327 range->range_flag|= UNIQUE_RANGE | (cur->min_key_flag & NULL_RANGE);
9330 if (param->is_ror_scan)
9332 const uint key_part_number= key_tree->part + 1;
9346 if ((!is_eq_range_pred &&
9347 key_part_number <= cur_key_info->user_defined_key_parts) ||
9348 !is_key_scan_ror(param, seq->real_keyno, key_part_number))
9349 param->is_ror_scan= FALSE;
9353 seq->param->range_count++;
9354 seq->param->max_key_part=max<uint>(seq->param->max_key_part,key_tree->part);
9389 ha_rows check_quick_select(
PARAM *param, uint idx,
bool index_only,
9390 SEL_ARG *tree,
bool update_tbl_stats,
9394 RANGE_SEQ_IF seq_if = {sel_arg_range_seq_init, sel_arg_range_seq_next, 0, 0};
9397 uint keynr= param->real_keynr[idx];
9398 DBUG_ENTER(
"check_quick_select");
9402 DBUG_RETURN(HA_POS_ERROR);
9403 if (tree->type == SEL_ARG::IMPOSSIBLE)
9405 if (tree->type != SEL_ARG::KEY_RANGE || tree->part != 0)
9406 DBUG_RETURN(HA_POS_ERROR);
9409 seq.real_keyno= keynr;
9412 param->range_count=0;
9413 param->max_key_part=0;
9420 uint range_count= 0;
9422 eq_ranges_exceeds_limit(tree, &range_count,
9423 param->thd->variables.eq_range_index_dive_limit);
9425 param->is_ror_scan= TRUE;
9426 if (file->index_flags(keynr, 0, TRUE) & HA_KEY_SCAN_NOT_ROR)
9427 param->is_ror_scan= FALSE;
9429 *mrr_flags= param->force_default_mrr? HA_MRR_USE_DEFAULT_IMPL: 0;
9430 *mrr_flags|= HA_MRR_NO_ASSOCIATION;
9434 if (param->order_direction != ORDER::ORDER_NOT_RELEVANT)
9435 *mrr_flags|= HA_MRR_SORTED;
9437 bool pk_is_clustered= file->primary_key_is_clustered();
9439 (file->index_flags(keynr, param->max_key_part, 1) & HA_KEYREAD_ONLY) &&
9440 !(pk_is_clustered && keynr == param->table->s->primary_key))
9441 *mrr_flags |= HA_MRR_INDEX_ONLY;
9443 if (current_thd->lex->sql_command != SQLCOM_SELECT)
9444 *mrr_flags|= HA_MRR_SORTED;
9446 *bufsize= param->thd->variables.read_rnd_buff_size;
9449 bufsize, mrr_flags, cost);
9450 if (rows != HA_POS_ERROR)
9452 param->table->quick_rows[keynr]=rows;
9453 if (update_tbl_stats)
9455 param->table->quick_keys.set_bit(keynr);
9456 param->table->quick_key_parts[keynr]=param->max_key_part+1;
9457 param->table->quick_n_ranges[keynr]= param->range_count;
9458 param->table->quick_condition_rows=
9459 min(param->table->quick_condition_rows, rows);
9461 param->table->possible_quick_keys.set_bit(keynr);
9464 enum ha_key_alg key_alg= param->table->key_info[seq.real_keyno].algorithm;
9465 if ((key_alg != HA_KEY_ALG_BTREE) && (key_alg!= HA_KEY_ALG_UNDEF))
9472 param->is_ror_scan= FALSE;
9477 if (param->table->s->primary_key == keynr && pk_is_clustered)
9478 param->is_ror_scan= TRUE;
9480 if (param->table->file->index_flags(keynr, 0, TRUE) & HA_KEY_SCAN_NOT_ROR)
9481 param->is_ror_scan= FALSE;
9482 DBUG_PRINT(
"exit", (
"Records: %lu", (ulong) rows));
9525 static bool is_key_scan_ror(
PARAM *param, uint keynr, uint nparts)
9527 KEY *table_key= param->table->key_info + keynr;
9534 const uint user_defined_nparts=
9537 KEY_PART_INFO *key_part= table_key->key_part + user_defined_nparts;
9542 for (
KEY_PART_INFO *kp= table_key->key_part; kp < key_part; kp++)
9544 uint16 fieldnr= param->table->key_info[keynr].
9545 key_part[kp - table_key->key_part].fieldnr - 1;
9546 if (param->table->field[fieldnr]->key_length() != kp->length)
9550 if (key_part == key_part_end)
9553 key_part= table_key->key_part + user_defined_nparts;
9554 pk_number= param->table->s->primary_key;
9555 if (!param->table->file->primary_key_is_clustered() || pk_number == MAX_KEY)
9558 KEY_PART_INFO *pk_part= param->table->key_info[pk_number].key_part;
9561 for (;(key_part!=key_part_end) && (pk_part != pk_part_end);
9562 ++key_part, ++pk_part)
9564 if ((key_part->field != pk_part->field) ||
9565 (key_part->length != pk_part->length))
9568 return (key_part == key_part_end);
9596 get_quick_select(
PARAM *param,uint idx,
SEL_ARG *key_tree, uint mrr_flags,
9597 uint mrr_buf_size,
MEM_ROOT *parent_alloc)
9600 bool create_err= FALSE;
9601 DBUG_ENTER(
"get_quick_select");
9603 if (param->table->key_info[param->real_keynr[idx]].
flags & HA_SPATIAL)
9605 param->real_keynr[idx],
9607 parent_alloc, &create_err);
9610 param->real_keynr[idx],
9611 test(parent_alloc), NULL, &create_err);
9616 get_quick_keys(param,quick,param->key[idx],key_tree,param->min_key,0,
9624 quick->mrr_flags= mrr_flags;
9625 quick->mrr_buf_size= mrr_buf_size;
9627 memdup_root(parent_alloc? parent_alloc : &quick->alloc,
9628 (
char*) param->key[idx],
9631 table->key_info[param->real_keynr[idx]]));
9643 SEL_ARG *key_tree, uchar *min_key,uint min_key_flag,
9644 uchar *max_key, uint max_key_flag)
9648 int min_part= key_tree->part-1,
9649 max_part= key_tree->part-1;
9651 if (key_tree->left != &null_element)
9653 if (get_quick_keys(param,quick,key,key_tree->left,
9654 min_key,min_key_flag, max_key, max_key_flag))
9657 uchar *tmp_min_key=min_key,*tmp_max_key=max_key;
9658 min_part+= key_tree->store_min(key[key_tree->part].store_length,
9659 &tmp_min_key,min_key_flag);
9660 max_part+= key_tree->store_max(key[key_tree->part].store_length,
9661 &tmp_max_key,max_key_flag);
9663 if (key_tree->next_key_part &&
9664 key_tree->next_key_part->type == SEL_ARG::KEY_RANGE &&
9665 key_tree->next_key_part->part == key_tree->part+1)
9667 if ((tmp_min_key - min_key) == (tmp_max_key - max_key) &&
9668 memcmp(min_key, max_key, (uint)(tmp_max_key - max_key))==0 &&
9669 key_tree->min_flag==0 && key_tree->max_flag==0)
9671 if (get_quick_keys(param,quick,key,key_tree->next_key_part,
9672 tmp_min_key, min_key_flag | key_tree->min_flag,
9673 tmp_max_key, max_key_flag | key_tree->max_flag))
9678 uint tmp_min_flag=key_tree->min_flag,tmp_max_flag=key_tree->max_flag;
9680 min_part+= key_tree->next_key_part->store_min_key(key,
9685 max_part+= key_tree->next_key_part->store_max_key(key,
9689 flag=tmp_min_flag | tmp_max_flag;
9694 flag = (key_tree->min_flag & GEOM_FLAG) ?
9695 key_tree->min_flag : key_tree->min_flag | key_tree->max_flag;
9702 if ((flag & GEOM_FLAG) == 0)
9704 if (tmp_min_key != param->min_key)
9705 flag&= ~NO_MIN_RANGE;
9707 flag|= NO_MIN_RANGE;
9708 if (tmp_max_key != param->max_key)
9709 flag&= ~NO_MAX_RANGE;
9711 flag|= NO_MAX_RANGE;
9715 uint length= (uint) (tmp_min_key - param->min_key);
9716 if (length == (uint) (tmp_max_key - param->max_key) &&
9717 !memcmp(param->min_key,param->max_key,length))
9719 const KEY *table_key=quick->head->key_info+quick->index;
9725 if ((table_key->
flags & HA_NOSAME) &&
9728 if (!(table_key->
flags & HA_NULL_PART_KEY) ||
9729 !null_part_in_key(key,
9731 (uint) (tmp_min_key - param->min_key)))
9732 flag|= UNIQUE_RANGE;
9741 (uint) (tmp_min_key - param->min_key),
9742 min_part >=0 ? make_keypart_map(min_part) : 0,
9744 (uint) (tmp_max_key - param->max_key),
9745 max_part >=0 ? make_keypart_map(max_part) : 0,
9749 set_if_bigger(quick->max_used_key_length, range->min_length);
9750 set_if_bigger(quick->max_used_key_length, range->max_length);
9751 set_if_bigger(quick->used_key_parts, (uint) key_tree->part+1);
9752 if (insert_dynamic(&quick->ranges, &range))
9756 if (key_tree->right != &null_element)
9757 return get_quick_keys(param,quick,key,key_tree->right,
9758 min_key,min_key_flag,
9759 max_key,max_key_flag);
9767 bool QUICK_RANGE_SELECT::unique_key_range()
9769 if (ranges.elements == 1)
9772 if ((tmp->flag & (EQ_RANGE | NULL_RANGE)) == EQ_RANGE)
9774 KEY *key=head->key_info+index;
9775 return (key->
flags & HA_NOSAME) && key->
key_length == tmp->min_length;
9797 static bool null_part_in_key(
KEY_PART *key_part,
const uchar *key, uint length)
9799 for (
const uchar *end=key+length ;
9801 key+= key_part++->store_length)
9803 if (key_part->null_bit && *key)
9810 bool QUICK_SELECT_I::is_keys_used(
const MY_BITMAP *fields)
9812 return is_key_used(head, index, fields);
9815 bool QUICK_INDEX_MERGE_SELECT::is_keys_used(
const MY_BITMAP *fields)
9819 while ((quick= it++))
9821 if (is_key_used(head, quick->index, fields))
9827 bool QUICK_ROR_INTERSECT_SELECT::is_keys_used(
const MY_BITMAP *fields)
9831 while ((quick= it++))
9833 if (is_key_used(head, quick->index, fields))
9839 bool QUICK_ROR_UNION_SELECT::is_keys_used(
const MY_BITMAP *fields)
9843 while ((quick= it++))
9845 if (quick->is_keys_used(fields))
9854 bool create_err= FALSE;
9865 #ifdef WITH_NDBCLUSTER_STORAGE_ENGINE
9867 key_has_nulls(
const KEY* key_info,
const uchar *key, uint key_len)
9870 const uchar* end_ptr= key + key_len;
9871 curr_part= key_info->key_part;
9874 for (; curr_part != end_part && key < end_ptr; curr_part++)
9876 if (curr_part->null_bit && *key)
9879 key += curr_part->store_length;
9909 KEY *key_info = &table->key_info[ref->
key];
9913 bool create_err= FALSE;
9916 old_root= thd->mem_root;
9920 alloc= thd->mem_root;
9925 thd->mem_root= old_root;
9927 if (!quick || create_err)
9931 quick->records= records;
9933 if ((cp_buffer_from_ref(thd, table, ref) && thd->is_fatal_error) ||
9937 range->min_key= range->max_key= ref->
key_buff;
9938 range->min_length= range->max_length= ref->
key_length;
9939 range->min_keypart_map= range->max_keypart_map=
9943 if (!(quick->key_parts=key_part=(
KEY_PART *)
9947 for (part=0 ; part < ref->
key_parts ;part++,key_part++)
9949 key_part->part=part;
9950 key_part->field= key_info->key_part[part].field;
9951 key_part->length= key_info->key_part[part].length;
9952 key_part->store_length= key_info->key_part[part].store_length;
9953 key_part->null_bit= key_info->key_part[part].null_bit;
9954 key_part->flag= (uint8) key_info->key_part[part].key_part_flag;
9956 if (insert_dynamic(&quick->ranges, &range))
9965 if (ref->null_ref_key)
9969 *ref->null_ref_key= 1;
9970 if (!(null_range=
new (alloc)
9974 make_prev_keypart_map(ref->
key_parts), EQ_RANGE)))
9976 *ref->null_ref_key= 0;
9977 if (insert_dynamic(&quick->ranges, &null_range))
9982 quick->mrr_flags= HA_MRR_NO_ASSOCIATION |
9983 (table->
key_read ? HA_MRR_INDEX_ONLY : 0);
9984 if (thd->lex->sql_command != SQLCOM_SELECT)
9985 quick->mrr_flags|= HA_MRR_SORTED;
9986 #ifdef WITH_NDBCLUSTER_STORAGE_ENGINE
9987 if (!ref->null_ref_key && !key_has_nulls(key_info, range->min_key,
9989 quick->mrr_flags |= HA_MRR_NO_NULL_ENDPOINTS;
9992 quick->mrr_buf_size= thd->variables.read_rnd_buff_size;
9994 &quick->mrr_buf_size,
9995 &quick->mrr_flags, &cost))
10022 int QUICK_INDEX_MERGE_SELECT::read_keys_and_merge()
10028 DBUG_ENTER(
"QUICK_INDEX_MERGE_SELECT::read_keys_and_merge");
10031 head->set_keyread(TRUE);
10034 cur_quick_it.rewind();
10035 cur_quick= cur_quick_it++;
10036 DBUG_ASSERT(cur_quick != 0);
10038 DBUG_EXECUTE_IF(
"simulate_bug13919180",
10040 my_error(ER_UNKNOWN_ERROR, MYF(0));
10047 if (cur_quick->init() || cur_quick->reset())
10050 if (unique == NULL)
10052 DBUG_EXECUTE_IF(
"index_merge_may_not_create_a_Unique", DBUG_ABORT(); );
10053 DBUG_EXECUTE_IF(
"only_one_Unique_may_be_created",
10054 DBUG_SET(
"+d,index_merge_may_not_create_a_Unique"); );
10056 unique=
new Unique(refpos_order_cmp, (
void *)file,
10058 thd->variables.sortbuff_size);
10063 filesort_free_buffers(head,
false);
10066 DBUG_ASSERT(file->
ref_length == unique->get_size());
10067 DBUG_ASSERT(thd->variables.sortbuff_size == unique->get_max_in_memory_size());
10073 while ((result= cur_quick->get_next()) == HA_ERR_END_OF_FILE)
10075 cur_quick->range_end();
10076 cur_quick= cur_quick_it++;
10080 if (cur_quick->file->inited)
10082 if (cur_quick->init() || cur_quick->reset())
10088 if (result != HA_ERR_END_OF_FILE)
10090 cur_quick->range_end();
10091 DBUG_RETURN(result);
10100 if (pk_quick_select && pk_quick_select->row_in_ranges())
10103 cur_quick->file->position(cur_quick->record);
10104 result= unique->unique_add((
char*)cur_quick->file->ref);
10114 result= unique->get(head);
10115 doing_pk_scan= FALSE;
10117 head->set_keyread(FALSE);
10118 if (init_read_record(&read_record, thd, head, (
SQL_SELECT*) 0, 1, 1, TRUE))
10120 DBUG_RETURN(result);
10133 int QUICK_INDEX_MERGE_SELECT::get_next()
10136 DBUG_ENTER(
"QUICK_INDEX_MERGE_SELECT::get_next");
10139 DBUG_RETURN(pk_quick_select->get_next());
10141 if ((result= read_record.read_record(&read_record)) == -1)
10143 result= HA_ERR_END_OF_FILE;
10144 end_read_record(&read_record);
10145 free_io_cache(head);
10147 if (pk_quick_select)
10149 doing_pk_scan= TRUE;
10150 if ((result= pk_quick_select->init()) ||
10151 (result= pk_quick_select->reset()))
10152 DBUG_RETURN(result);
10153 DBUG_RETURN(pk_quick_select->get_next());
10157 DBUG_RETURN(result);
10188 int QUICK_ROR_INTERSECT_SELECT::get_next()
10199 uint last_rowid_count=0;
10200 DBUG_ENTER(
"QUICK_ROR_INTERSECT_SELECT::get_next");
10206 error= quick->get_next();
10209 while (!error && !cpk_quick->row_in_ranges())
10211 quick->file->unlock_row();
10212 error= quick->get_next();
10216 DBUG_RETURN(error);
10218 quick->file->position(quick->record);
10219 memcpy(last_rowid, quick->file->ref, head->file->
ref_length);
10220 last_rowid_count= 1;
10221 quick_with_last_rowid= quick;
10223 while (last_rowid_count < quick_selects.elements)
10225 if (!(quick= quick_it++))
10233 DBUG_EXECUTE_IF(
"innodb_quick_report_deadlock",
10234 DBUG_SET(
"+d,innodb_report_deadlock"););
10235 if ((error= quick->get_next()))
10238 if (!current_thd->transaction_rollback_request)
10239 quick_with_last_rowid->file->unlock_row();
10240 DBUG_RETURN(error);
10242 quick->file->position(quick->record);
10243 cmp= head->file->cmp_ref(quick->file->ref, last_rowid);
10247 quick->file->unlock_row();
10257 while (!cpk_quick->row_in_ranges())
10259 quick->file->unlock_row();
10260 if ((error= quick->get_next()))
10263 if (!current_thd->transaction_rollback_request)
10264 quick_with_last_rowid->file->unlock_row();
10265 DBUG_RETURN(error);
10268 quick->file->position(quick->record);
10270 memcpy(last_rowid, quick->file->ref, head->file->
ref_length);
10271 quick_with_last_rowid->file->unlock_row();
10272 last_rowid_count= 1;
10273 quick_with_last_rowid= quick;
10278 last_rowid_count++;
10283 if (need_to_fetch_row)
10284 error= head->file->
ha_rnd_pos(head->record[0], last_rowid);
10285 }
while (error == HA_ERR_RECORD_DELETED);
10286 DBUG_RETURN(error);
10305 int QUICK_ROR_UNION_SELECT::get_next()
10307 int error, dup_row;
10310 DBUG_ENTER(
"QUICK_ROR_UNION_SELECT::get_next");
10316 if (!queue.elements)
10317 DBUG_RETURN(HA_ERR_END_OF_FILE);
10321 memcpy(cur_rowid, quick->last_rowid, rowid_length);
10324 if ((error= quick->get_next()))
10326 if (error != HA_ERR_END_OF_FILE)
10327 DBUG_RETURN(error);
10328 queue_remove(&queue, 0);
10332 quick->save_last_pos();
10333 queue_replaced(&queue);
10336 if (!have_prev_rowid)
10340 have_prev_rowid= TRUE;
10343 dup_row= !head->file->cmp_ref(cur_rowid, prev_rowid);
10347 cur_rowid= prev_rowid;
10350 error= head->file->
ha_rnd_pos(quick->record, prev_rowid);
10351 }
while (error == HA_ERR_RECORD_DELETED);
10352 DBUG_RETURN(error);
10356 int QUICK_RANGE_SELECT::reset()
10359 uchar *mrange_buff;
10362 DBUG_ENTER(
"QUICK_RANGE_SELECT::reset");
10367 if(!head->no_keyread && head->covering_keys.is_set(index))
10368 head->set_keyread(
true);
10370 head->set_keyread(
false);
10374 if (in_ror_merged_scan)
10375 head->column_bitmaps_set_no_signal(&column_bitmap, &column_bitmap);
10376 const bool sorted= (mrr_flags & HA_MRR_SORTED);
10377 DBUG_EXECUTE_IF(
"bug14365043_2",
10378 DBUG_SET(
"+d,ha_index_init_fail"););
10382 DBUG_RETURN(error);
10387 if (mrr_buf_size && !mrr_buf_desc)
10389 buf_size= mrr_buf_size;
10390 while (buf_size && !my_multi_malloc(MYF(MY_WME),
10391 &mrr_buf_desc,
sizeof(*mrr_buf_desc),
10392 &mrange_buff, buf_size,
10399 DBUG_RETURN(HA_ERR_OUT_OF_MEM);
10402 mrr_buf_desc->buffer= mrange_buff;
10403 mrr_buf_desc->buffer_end= mrange_buff + buf_size;
10404 mrr_buf_desc->end_of_used_area= mrange_buff;
10411 memset(mrange_buff, 0, buf_size);
10416 empty_buf.buffer= empty_buf.buffer_end= empty_buf.end_of_used_area= NULL;
10418 RANGE_SEQ_IF seq_funcs= {quick_range_seq_init, quick_range_seq_next, 0, 0};
10420 mrr_flags, mrr_buf_desc? mrr_buf_desc:
10422 DBUG_RETURN(error);
10439 range_seq_t quick_range_seq_init(
void *init_param, uint n_ranges, uint flags)
10442 quick->qr_traversal_ctx.first= (
QUICK_RANGE**)quick->ranges.buffer;
10443 quick->qr_traversal_ctx.cur= (
QUICK_RANGE**)quick->ranges.buffer;
10444 quick->qr_traversal_ctx.last= quick->qr_traversal_ctx.cur +
10445 quick->ranges.elements;
10446 return &quick->qr_traversal_ctx;
10467 if (ctx->cur == ctx->last)
10471 key_range *start_key= &range->start_key;
10474 start_key->key= cur->min_key;
10475 start_key->length= cur->min_length;
10476 start_key->keypart_map= cur->min_keypart_map;
10477 start_key->flag= ((cur->flag & NEAR_MIN) ? HA_READ_AFTER_KEY :
10478 (cur->flag & EQ_RANGE) ?
10479 HA_READ_KEY_EXACT : HA_READ_KEY_OR_NEXT);
10480 end_key->key= cur->max_key;
10481 end_key->length= cur->max_length;
10482 end_key->keypart_map= cur->max_keypart_map;
10487 end_key->flag= (cur->flag & NEAR_MAX ? HA_READ_BEFORE_KEY :
10488 HA_READ_AFTER_KEY);
10489 range->range_flag= cur->flag;
10515 uint16 &mrr_persistent_flag_storage(range_seq_t seq, uint idx)
10518 return ctx->first[idx]->flag;
10547 char* &mrr_get_ptr_by_idx(range_seq_t seq, uint idx)
10549 static char *dummy;
10569 int QUICK_RANGE_SELECT::get_next()
10572 MY_BITMAP *
const save_read_set= head->read_set;
10573 MY_BITMAP *
const save_write_set= head->write_set;
10574 DBUG_ENTER(
"QUICK_RANGE_SELECT::get_next");
10576 if (in_ror_merged_scan)
10582 head->column_bitmaps_set_no_signal(&column_bitmap, &column_bitmap);
10587 if (in_ror_merged_scan)
10590 head->column_bitmaps_set_no_signal(save_read_set, save_write_set);
10592 DBUG_RETURN(result);
10622 int QUICK_RANGE_SELECT::get_next_prefix(uint prefix_length,
10623 uint group_key_parts,
10626 DBUG_ENTER(
"QUICK_RANGE_SELECT::get_next_prefix");
10627 const key_part_map keypart_map= make_prev_keypart_map(group_key_parts);
10635 DBUG_ASSERT(cur_prefix != NULL);
10637 HA_READ_AFTER_KEY);
10638 if (result || last_range->max_keypart_map == 0)
10639 DBUG_RETURN(result);
10647 uint count= ranges.elements - (cur_range - (
QUICK_RANGE**) ranges.buffer);
10652 DBUG_RETURN(HA_ERR_END_OF_FILE);
10654 last_range= *(cur_range++);
10660 const bool sorted= (mrr_flags & HA_MRR_SORTED);
10661 result= file->
read_range_first(last_range->min_keypart_map ? &start_key : 0,
10662 last_range->max_keypart_map ? &end_key : 0,
10663 test(last_range->flag & EQ_RANGE),
10665 if (last_range->flag == (UNIQUE_RANGE | EQ_RANGE))
10668 if (result != HA_ERR_END_OF_FILE)
10669 DBUG_RETURN(result);
10677 int QUICK_RANGE_SELECT_GEOM::get_next()
10679 DBUG_ENTER(
"QUICK_RANGE_SELECT_GEOM::get_next");
10688 last_range->min_length);
10689 if (result != HA_ERR_END_OF_FILE)
10690 DBUG_RETURN(result);
10693 uint count= ranges.elements - (cur_range - (
QUICK_RANGE**) ranges.buffer);
10698 DBUG_RETURN(HA_ERR_END_OF_FILE);
10700 last_range= *(cur_range++);
10703 last_range->min_keypart_map,
10704 (ha_rkey_function)(last_range->flag ^
10706 if (result != HA_ERR_KEY_NOT_FOUND && result != HA_ERR_END_OF_FILE)
10707 DBUG_RETURN(result);
10731 bool QUICK_RANGE_SELECT::row_in_ranges()
10735 uint max= ranges.elements - 1;
10736 uint mid= (max + min)/2;
10740 if (cmp_next(*(
QUICK_RANGE**)dynamic_array_ptr(&ranges, mid)))
10747 mid= (min + max) / 2;
10749 res= *(
QUICK_RANGE**)dynamic_array_ptr(&ranges, mid);
10750 return (!cmp_next(res) && !cmp_prev(res));
10764 uint used_key_parts_arg,
10767 used_key_parts (used_key_parts_arg)
10774 mrr_buf_desc= NULL;
10775 mrr_flags |= HA_MRR_USE_DEFAULT_IMPL;
10776 mrr_flags |= HA_MRR_SORTED;
10782 for (; pr!=end_range; pr++)
10783 rev_ranges.push_front(*pr);
10786 for (r = rev_it++; r; r = rev_it++)
10788 if ((r->flag & EQ_RANGE) &&
10790 r->flag&= ~EQ_RANGE;
10797 int QUICK_SELECT_DESC::get_next()
10799 DBUG_ENTER(
"QUICK_SELECT_DESC::get_next");
10819 result = ((last_range->flag & EQ_RANGE &&
10823 last_range->min_length) :
10827 if (cmp_prev(*rev_it.ref()) == 0)
10830 else if (result != HA_ERR_END_OF_FILE)
10831 DBUG_RETURN(result);
10834 if (!(last_range= rev_it++))
10835 DBUG_RETURN(HA_ERR_END_OF_FILE);
10838 const bool eqrange_all_keyparts= (last_range->flag & EQ_RANGE) &&
10839 (used_key_parts <= head->key_info[index].user_defined_key_parts);
10847 if (file->pushed_idx_cond)
10849 if (!eqrange_all_keyparts)
10853 if(min_range.length > 0)
10868 if (last_range->flag & NO_MAX_RANGE)
10880 if (local_error != HA_ERR_END_OF_FILE)
10881 DBUG_RETURN(local_error);
10886 if (cmp_prev(last_range) == 0)
10892 if (eqrange_all_keyparts)
10896 last_range->max_keypart_map,
10897 HA_READ_KEY_EXACT);
10901 DBUG_ASSERT(last_range->flag & NEAR_MAX ||
10902 (last_range->flag & EQ_RANGE &&
10905 range_reads_after_key(last_range));
10907 last_range->max_keypart_map,
10908 ((last_range->flag & NEAR_MAX) ?
10909 HA_READ_BEFORE_KEY :
10910 HA_READ_PREFIX_LAST_OR_PREV));
10914 if (result != HA_ERR_KEY_NOT_FOUND && result != HA_ERR_END_OF_FILE)
10915 DBUG_RETURN(result);
10919 if (cmp_prev(last_range) == 0)
10921 if (last_range->flag == (UNIQUE_RANGE | EQ_RANGE))
10944 if (new_quick == NULL || error)
10959 int QUICK_RANGE_SELECT::cmp_next(
QUICK_RANGE *range_arg)
10961 if (range_arg->flag & NO_MAX_RANGE)
10967 for (uchar *key=range_arg->max_key, *end=key+range_arg->max_length;
10969 key+= store_length, key_part++)
10972 store_length= key_part->store_length;
10973 if (key_part->null_bit)
10977 if (!key_part->field->is_null())
10981 else if (key_part->field->is_null())
10986 if ((cmp=key_part->field->key_cmp(key, key_part->length)) < 0)
10991 return (range_arg->flag & NEAR_MAX) ? 1 : 0;
10999 int QUICK_RANGE_SELECT::cmp_prev(
QUICK_RANGE *range_arg)
11002 if (range_arg->flag & NO_MIN_RANGE)
11005 cmp= key_cmp(key_part_info, range_arg->min_key,
11006 range_arg->min_length);
11007 if (cmp > 0 || (cmp == 0 && !(range_arg->flag & NEAR_MIN)))
11018 bool QUICK_SELECT_DESC::range_reads_after_key(
QUICK_RANGE *range_arg)
11020 return ((range_arg->flag & (NO_MAX_RANGE | NEAR_MAX)) ||
11021 !(range_arg->flag & EQ_RANGE) ||
11022 head->key_info[index].
key_length != range_arg->max_length) ? 1 : 0;
11026 void QUICK_RANGE_SELECT::add_info_string(
String *str)
11028 KEY *key_info= head->key_info + index;
11029 str->append(key_info->
name);
11032 void QUICK_INDEX_MERGE_SELECT::add_info_string(
String *str)
11037 str->append(STRING_WITH_LEN(
"sort_union("));
11038 while ((quick= it++))
11044 quick->add_info_string(str);
11046 if (pk_quick_select)
11049 pk_quick_select->add_info_string(str);
11054 void QUICK_ROR_INTERSECT_SELECT::add_info_string(
String *str)
11059 str->append(STRING_WITH_LEN(
"intersect("));
11060 while ((quick= it++))
11062 KEY *key_info= head->key_info + quick->index;
11067 str->append(key_info->
name);
11071 KEY *key_info= head->key_info + cpk_quick->index;
11073 str->append(key_info->
name);
11078 void QUICK_ROR_UNION_SELECT::add_info_string(
String *str)
11083 str->append(STRING_WITH_LEN(
"union("));
11084 while ((quick= it++))
11090 quick->add_info_string(str);
11096 void QUICK_RANGE_SELECT::add_keys_and_lengths(
String *key_names,
11101 KEY *key_info= head->key_info + index;
11102 key_names->append(key_info->
name);
11103 length= longlong2str(max_used_key_length, buf, 10) -
buf;
11104 used_lengths->append(buf, length);
11107 void QUICK_INDEX_MERGE_SELECT::add_keys_and_lengths(
String *key_names,
11116 while ((quick= it++))
11122 key_names->append(
',');
11123 used_lengths->append(
',');
11126 KEY *key_info= head->key_info + quick->index;
11127 key_names->append(key_info->
name);
11128 length= longlong2str(quick->max_used_key_length, buf, 10) -
buf;
11129 used_lengths->append(buf, length);
11131 if (pk_quick_select)
11133 KEY *key_info= head->key_info + pk_quick_select->index;
11134 key_names->append(
',');
11135 key_names->append(key_info->
name);
11136 length= longlong2str(pk_quick_select->max_used_key_length, buf, 10) -
buf;
11137 used_lengths->append(
',');
11138 used_lengths->append(buf, length);
11142 void QUICK_ROR_INTERSECT_SELECT::add_keys_and_lengths(
String *key_names,
11150 while ((quick= it++))
11152 KEY *key_info= head->key_info + quick->index;
11157 key_names->append(
',');
11158 used_lengths->append(
',');
11160 key_names->append(key_info->
name);
11161 length= longlong2str(quick->max_used_key_length, buf, 10) -
buf;
11162 used_lengths->append(buf, length);
11167 KEY *key_info= head->key_info + cpk_quick->index;
11168 key_names->append(
',');
11169 key_names->append(key_info->
name);
11170 length= longlong2str(cpk_quick->max_used_key_length, buf, 10) -
buf;
11171 used_lengths->append(
',');
11172 used_lengths->append(buf, length);
11176 void QUICK_ROR_UNION_SELECT::add_keys_and_lengths(
String *key_names,
11182 while ((quick= it++))
11188 used_lengths->append(
',');
11189 key_names->append(
',');
11191 quick->add_keys_and_lengths(key_names, used_lengths);
11200 static inline uint get_field_keypart(
KEY *
index,
Field *field);
11202 PARAM *param, uint *param_idx);
11203 static bool get_constant_key_infix(
KEY *index_info,
SEL_ARG *index_range_tree,
11207 uchar *key_infix, uint *key_infix_len,
11210 check_group_min_max_predicates(
Item *cond,
Item_field *min_max_arg_item,
11211 Field::imagetype image_type);
11214 cost_group_min_max(
TABLE* table,
KEY *index_info, uint used_key_parts,
11215 uint group_key_parts,
SEL_TREE *range_tree,
11216 SEL_ARG *index_tree, ha_rows quick_prefix_records,
11217 bool have_min,
bool have_max,
11218 double *read_cost, ha_rows *records);
11351 get_best_group_min_max(
PARAM *param,
SEL_TREE *tree,
double read_time)
11353 THD *thd= param->thd;
11354 JOIN *join= thd->lex->current_select->join;
11355 TABLE *table= param->table;
11356 bool have_min= FALSE;
11357 bool have_max= FALSE;
11360 uint group_prefix_len= 0;
11361 KEY *index_info= NULL;
11363 uint group_key_parts= 0;
11364 uint used_key_parts= 0;
11365 uchar key_infix[MAX_KEY_LENGTH];
11366 uint key_infix_len= 0;
11372 bool is_agg_distinct;
11375 double best_read_cost= DBL_MAX;
11376 ha_rows best_records= 0;
11377 SEL_ARG *best_index_tree= NULL;
11378 ha_rows best_quick_prefix_records= 0;
11379 uint best_param_idx= 0;
11383 DBUG_ENTER(
"get_best_group_min_max");
11386 Opt_trace_context::RANGE_OPTIMIZER);
11387 const char* cause= NULL;
11393 cause=
"not_single_table";
11394 else if (join->
select_lex->olap == ROLLUP_TYPE)
11396 else if (table->s->keys == 0)
11398 else if (param->order_direction == ORDER::ORDER_DESC)
11399 cause=
"cannot_do_reverse_ordering";
11402 trace_group.add(
"chosen",
false).add_alnum(
"cause", cause);
11409 if ((!join->group_list) &&
11413 trace_group.add(
"chosen",
false).
11414 add_alnum(
"cause",
"not_group_by_or_distinct");
11419 if (join->sum_funcs[0])
11422 Item_sum **func_ptr= join->sum_funcs;
11423 while ((min_max_item= *(func_ptr++)))
11425 if (min_max_item->sum_func() == Item_sum::MIN_FUNC)
11427 else if (min_max_item->sum_func() == Item_sum::MAX_FUNC)
11429 else if (is_agg_distinct &&
11430 (min_max_item->sum_func() == Item_sum::COUNT_DISTINCT_FUNC ||
11431 min_max_item->sum_func() == Item_sum::SUM_DISTINCT_FUNC ||
11432 min_max_item->sum_func() == Item_sum::AVG_DISTINCT_FUNC))
11436 trace_group.add(
"chosen",
false).
11437 add_alnum(
"cause",
"not_applicable_aggregate_function");
11442 Item *expr= min_max_item->get_arg(0)->real_item();
11443 if (expr->type() == Item::FIELD_ITEM)
11445 if (! min_max_arg_item)
11447 else if (! min_max_arg_item->
eq(expr, 1))
11459 trace_group.add(
"distinct_query",
true);
11460 while ((item= select_items_it++))
11462 if (item->real_item()->type() != Item::FIELD_ITEM)
11468 for (tmp_group= join->group_list; tmp_group; tmp_group= tmp_group->next)
11470 if ((*tmp_group->item)->real_item()->type() != Item::FIELD_ITEM)
11472 trace_group.add(
"chosen",
false).
11473 add_alnum(
"cause",
"group_field_is_expression");
11484 const uint pk= param->table->s->primary_key;
11485 KEY *cur_index_info= table->key_info;
11486 KEY *cur_index_info_end= cur_index_info + table->s->keys;
11487 SEL_ARG *cur_index_tree= NULL;
11488 ha_rows cur_quick_prefix_records= 0;
11489 uint cur_param_idx= MAX_KEY;
11490 Opt_trace_array trace_indices(trace,
"potential_group_range_indices");
11491 for (uint cur_index= 0 ; cur_index_info != cur_index_info_end ;
11492 cur_index_info++, cur_index++)
11495 trace_idx.add_utf8(
"index", cur_index_info->
name);
11502 uint key_infix_parts;
11503 uint cur_group_key_parts= 0;
11504 uint cur_group_prefix_len= 0;
11505 double cur_read_cost;
11506 ha_rows cur_records;
11508 uint max_key_part= 0;
11509 uint cur_key_infix_len= 0;
11510 uchar cur_key_infix[MAX_KEY_LENGTH];
11511 uint cur_used_key_parts;
11514 if (!table->covering_keys.is_set(cur_index))
11516 cause=
"not_covering";
11529 if (pk < MAX_KEY && cur_index != pk &&
11533 for (uint i= 0; i < table->s->fields; i++)
11535 Field *cur_field= table->field[
i];
11540 if (bitmap_is_set(table->read_set, cur_field->field_index) &&
11541 !cur_field->part_of_key_not_clustered.is_set(cur_index))
11543 cause=
"not_covering";
11548 trace_idx.add(
"covering",
true);
11553 if (join->group_list)
11555 cur_part= cur_index_info->key_part;
11558 for (tmp_group= join->group_list; tmp_group && (cur_part != end_part);
11559 tmp_group= tmp_group->next, cur_part++)
11567 DBUG_ASSERT((*tmp_group->item)->real_item()->type() == Item::FIELD_ITEM);
11569 if (group_field->field->eq(cur_part->field))
11571 cur_group_prefix_len+= cur_part->store_length;
11572 ++cur_group_key_parts;
11573 max_key_part= cur_part - cur_index_info->key_part + 1;
11574 used_key_parts_map.set_bit(max_key_part);
11578 cause=
"group_attribute_not_prefix_in_index";
11595 if (!is_agg_distinct)
11597 select_items_it.rewind();
11602 (item= (is_agg_distinct ?
11603 (
Item *) agg_distinct_flds_it++ : select_items_it++)))
11606 item_field= (
Item_field*) item->real_item();
11607 DBUG_ASSERT(item->real_item()->type() == Item::FIELD_ITEM);
11610 if (!item_field->field)
11612 cause=
"derived_table";
11617 key_part_nr= get_field_keypart(cur_index_info, item_field->field);
11622 if (used_key_parts_map.is_set(key_part_nr))
11624 if (key_part_nr < 1 ||
11625 (!is_agg_distinct && key_part_nr > join->
fields_list.elements))
11627 cause=
"select_attribute_not_prefix_in_index";
11630 cur_part= cur_index_info->key_part + key_part_nr - 1;
11631 cur_group_prefix_len+= cur_part->store_length;
11632 used_key_parts_map.set_bit(key_part_nr);
11633 ++cur_group_key_parts;
11634 max_key_part= max(max_key_part,key_part_nr);
11642 ulonglong all_parts, cur_parts;
11643 all_parts= (1ULL << max_key_part) - 1;
11644 cur_parts= used_key_parts_map.to_ulonglong() >> 1;
11645 if (all_parts != cur_parts)
11650 if (min_max_arg_item)
11652 key_part_nr= get_field_keypart(cur_index_info, min_max_arg_item->field);
11653 if (key_part_nr <= cur_group_key_parts)
11655 cause=
"aggregate_column_not_suffix_in_idx";
11658 min_max_arg_part= cur_index_info->key_part + key_part_nr - 1;
11662 if (is_agg_distinct && cur_index == table->s->primary_key &&
11663 table->file->primary_key_is_clustered())
11665 cause=
"primary_key_is_clustered";
11685 first_non_group_part=
11687 cur_index_info->key_part + cur_group_key_parts :
11689 first_non_infix_part= min_max_arg_part ?
11690 (min_max_arg_part < last_part) ?
11694 if (first_non_group_part &&
11695 (!min_max_arg_part || (min_max_arg_part - first_non_group_part > 0)))
11700 SEL_ARG *index_range_tree= get_index_range_tree(cur_index, tree, param,
11702 if (!get_constant_key_infix(cur_index_info, index_range_tree,
11703 first_non_group_part, min_max_arg_part,
11704 last_part, thd, cur_key_infix,
11705 &cur_key_infix_len,
11706 &first_non_infix_part))
11708 cause=
"nonconst_equality_gap_attribute";
11712 else if (min_max_arg_part &&
11713 (min_max_arg_part - first_non_group_part > 0))
11719 cause=
"no_nongroup_keypart_predicate";
11722 else if (first_non_group_part && join->
conds)
11737 key_part_range[0]= first_non_group_part;
11738 key_part_range[1]= last_part;
11741 if (join->
conds->walk(&Item::find_item_in_field_list_processor, 0,
11742 (uchar*) key_part_range))
11744 cause=
"keypart_reference_from_where_clause";
11754 if (first_non_infix_part)
11756 cur_part= first_non_infix_part +
11757 (min_max_arg_part && (min_max_arg_part < last_part));
11758 for (; cur_part != last_part; cur_part++)
11760 if (bitmap_is_set(table->read_set, cur_part->field->field_index))
11762 cause=
"keypart_after_infix_in_query";
11769 key_infix_parts= cur_key_infix_len ? (uint)
11770 (first_non_infix_part - first_non_group_part) : 0;
11771 cur_used_key_parts= cur_group_key_parts + key_infix_parts;
11777 cur_index_tree= get_index_range_tree(cur_index, tree, param,
11781 uint mrr_flags= HA_MRR_SORTED;
11782 uint mrr_bufsize=0;
11783 cur_quick_prefix_records= check_quick_select(param, cur_param_idx,
11785 cur_index_tree, TRUE,
11786 &mrr_flags, &mrr_bufsize,
11788 #ifdef OPTIMIZER_TRACE
11789 if (unlikely(cur_index_tree && trace->is_started()))
11797 range_info.set_charset(system_charset_info);
11798 append_range_all_keyparts(&trace_range, NULL, &range_info,
11799 cur_index_tree, key_part);
11803 cost_group_min_max(table, cur_index_info, cur_used_key_parts,
11804 cur_group_key_parts, tree, cur_index_tree,
11805 cur_quick_prefix_records, have_min, have_max,
11806 &cur_read_cost, &cur_records);
11812 trace_idx.add(
"rows", cur_records).add(
"cost", cur_read_cost);
11813 if (cur_read_cost < best_read_cost - (DBL_EPSILON * cur_read_cost))
11815 index_info= cur_index_info;
11817 best_read_cost= cur_read_cost;
11818 best_records= cur_records;
11819 best_index_tree= cur_index_tree;
11820 best_quick_prefix_records= cur_quick_prefix_records;
11821 best_param_idx= cur_param_idx;
11822 group_key_parts= cur_group_key_parts;
11823 group_prefix_len= cur_group_prefix_len;
11824 key_infix_len= cur_key_infix_len;
11826 memcpy (key_infix, cur_key_infix,
sizeof (key_infix));
11827 used_key_parts= cur_used_key_parts;
11833 trace_idx.add(
"usable",
false).add_alnum(
"cause", cause);
11837 trace_indices.end();
11843 if (join->
conds && min_max_arg_item &&
11844 !check_group_min_max_predicates(join->
conds, min_max_arg_item,
11845 (index_info->
flags & HA_SPATIAL) ?
11846 Field::itMBR : Field::itRAW))
11848 trace_group.add(
"usable",
false).
11849 add_alnum(
"cause",
"unsupported_predicate_on_agg_attribute");
11854 read_plan=
new (param->mem_root)
11857 group_prefix_len, used_key_parts,
11858 group_key_parts, index_info, index,
11860 (key_infix_len > 0) ? key_infix : NULL,
11861 tree, best_index_tree, best_param_idx,
11862 best_quick_prefix_records);
11868 read_plan->read_cost= best_read_cost;
11869 read_plan->records= best_records;
11870 if (read_time < best_read_cost && is_agg_distinct)
11872 trace_group.add(
"index_scan",
true);
11873 read_plan->read_cost= 0;
11874 read_plan->use_index_scan();
11878 (
"Returning group min/max plan: cost: %g, records: %lu",
11879 read_plan->read_cost, (ulong) read_plan->records));
11882 DBUG_RETURN(read_plan);
11909 check_group_min_max_predicates(
Item *cond,
Item_field *min_max_arg_item,
11910 Field::imagetype image_type)
11912 DBUG_ENTER(
"check_group_min_max_predicates");
11913 DBUG_ASSERT(cond && min_max_arg_item);
11915 cond= cond->real_item();
11916 Item::Type cond_type= cond->type();
11917 if (cond_type == Item::COND_ITEM)
11919 DBUG_PRINT(
"info", (
"Analyzing: %s", ((
Item_func*) cond)->func_name()));
11922 while ((and_or_arg= li++))
11924 if (!check_group_min_max_predicates(and_or_arg, min_max_arg_item,
11926 DBUG_RETURN(FALSE);
11940 if (cond_type == Item::SUBSELECT_ITEM)
11941 DBUG_RETURN(FALSE);
11947 if (cond_type == Item::FIELD_ITEM)
11949 DBUG_PRINT(
"info", (
"Analyzing: %s", cond->full_name()));
11954 DBUG_ASSERT(cond_type == Item::FUNC_ITEM);
11959 DBUG_PRINT(
"info", (
"Analyzing: %s", pred->func_name()));
11960 for (uint arg_idx= 0; arg_idx < pred->argument_count (); arg_idx++)
11962 Item **arguments= pred->arguments();
11963 cur_arg= arguments[arg_idx]->real_item();
11964 DBUG_PRINT(
"info", (
"cur_arg: %s", cur_arg->full_name()));
11965 if (cur_arg->type() == Item::FIELD_ITEM)
11967 if (min_max_arg_item->
eq(cur_arg, 1))
11973 Item_func::Functype pred_type= pred->functype();
11974 if (pred_type != Item_func::EQUAL_FUNC &&
11975 pred_type != Item_func::LT_FUNC &&
11976 pred_type != Item_func::LE_FUNC &&
11977 pred_type != Item_func::GT_FUNC &&
11978 pred_type != Item_func::GE_FUNC &&
11979 pred_type != Item_func::BETWEEN &&
11980 pred_type != Item_func::ISNULL_FUNC &&
11981 pred_type != Item_func::ISNOTNULL_FUNC &&
11982 pred_type != Item_func::EQ_FUNC &&
11983 pred_type != Item_func::NE_FUNC)
11984 DBUG_RETURN(FALSE);
11988 memset(args, 0, 3 *
sizeof(
Item*));
11992 DBUG_RETURN(FALSE);
11995 if (args[0] && args[1] && !args[2] &&
11996 min_max_arg_item->result_type() == STRING_RESULT &&
12000 ((args[1]->result_type() == STRING_RESULT &&
12001 image_type == Field::itRAW &&
12002 min_max_arg_item->field->charset() != pred->compare_collation())
12008 (args[1]->result_type() != STRING_RESULT &&
12009 min_max_arg_item->field->cmp_type() != args[1]->result_type())))
12010 DBUG_RETURN(FALSE);
12013 else if (cur_arg->type() == Item::FUNC_ITEM)
12015 if (!check_group_min_max_predicates(cur_arg, min_max_arg_item,
12017 DBUG_RETURN(FALSE);
12019 else if (cur_arg->const_item())
12028 DBUG_RETURN(FALSE);
12058 get_sel_arg_for_keypart(
Field *nga_field,
12062 if(keypart_tree == NULL)
12064 if(keypart_tree->type != SEL_ARG::KEY_RANGE)
12071 *cur_range= keypart_tree;
12074 if(keypart_tree->field->eq(nga_field))
12080 if (keypart_tree->prev || keypart_tree->next)
12083 *cur_range= keypart_tree;
12088 SEL_ARG *first_kp= keypart_tree->first();
12090 for (
SEL_ARG *cur_kp= first_kp; cur_kp && !found_tree;
12091 cur_kp= cur_kp->next)
12093 if (cur_kp->next_key_part)
12095 if (get_sel_arg_for_keypart(nga_field,
12096 cur_kp->next_key_part,
12105 if (found_tree && found_tree->type == SEL_ARG::KEY_RANGE && first_kp->next)
12108 *cur_range= found_tree;
12145 get_constant_key_infix(
KEY *index_info,
SEL_ARG *index_range_tree,
12149 uchar *key_infix, uint *key_infix_len,
12155 KEY_PART_INFO *end_part= min_max_arg_part ? min_max_arg_part : last_part;
12158 uchar *key_ptr= key_infix;
12159 for (cur_part= first_non_group_part; cur_part != end_part; cur_part++)
12166 if(get_sel_arg_for_keypart(cur_part->field, index_range_tree, &cur_range))
12169 if (!cur_range || cur_range->type != SEL_ARG::KEY_RANGE)
12171 if (min_max_arg_part)
12175 *first_non_infix_part= cur_part;
12180 if ((cur_range->min_flag & NO_MIN_RANGE) ||
12181 (cur_range->max_flag & NO_MAX_RANGE) ||
12182 (cur_range->min_flag & NEAR_MIN) || (cur_range->max_flag & NEAR_MAX))
12185 uint field_length= cur_part->store_length;
12186 if (cur_range->maybe_null &&
12187 cur_range->min_value[0] && cur_range->max_value[0])
12194 DBUG_ASSERT (field_length > 0);
12196 key_ptr+= field_length;
12197 *key_infix_len+= field_length;
12199 else if (memcmp(cur_range->min_value, cur_range->max_value, field_length) == 0)
12201 memcpy(key_ptr, cur_range->min_value, field_length);
12202 key_ptr+= field_length;
12203 *key_infix_len+= field_length;
12209 if (!min_max_arg_part && (cur_part == last_part))
12210 *first_non_infix_part= last_part;
12234 get_field_keypart(
KEY *index,
Field *field)
12239 part < end; part++)
12241 if (field->eq(part->field))
12242 return part - index->key_part + 1;
12275 while (idx < param->keys)
12277 if (index == param->real_keynr[idx])
12282 return(range_tree->keys[idx]);
12346 void cost_group_min_max(
TABLE* table,
KEY *index_info, uint used_key_parts,
12347 uint group_key_parts,
SEL_TREE *range_tree,
12348 SEL_ARG *index_tree, ha_rows quick_prefix_records,
12349 bool have_min,
bool have_max,
12350 double *read_cost, ha_rows *records)
12352 ha_rows table_records;
12355 uint keys_per_block;
12356 uint keys_per_group;
12357 uint keys_per_subgroup;
12360 double quick_prefix_selectivity;
12362 DBUG_ENTER(
"cost_group_min_max");
12364 table_records= table->file->stats.records;
12365 keys_per_block= (table->file->stats.block_size / 2 /
12368 num_blocks= (uint)(table_records / keys_per_block) + 1;
12371 keys_per_group= index_info->
rec_per_key[group_key_parts - 1];
12372 if (keys_per_group == 0)
12374 keys_per_group= (uint)(table_records / 10) + 1;
12375 num_groups= (uint)(table_records / keys_per_group) + 1;
12378 if (range_tree && (quick_prefix_records != HA_POS_ERROR))
12380 quick_prefix_selectivity= (double) quick_prefix_records /
12381 (
double) table_records;
12382 num_groups= (uint) rint(num_groups * quick_prefix_selectivity);
12383 set_if_bigger(num_groups, 1);
12386 if (used_key_parts > group_key_parts)
12391 keys_per_subgroup= index_info->
rec_per_key[used_key_parts - 1];
12392 if (keys_per_subgroup >= keys_per_block)
12396 double blocks_per_group= (double) num_blocks / (
double) num_groups;
12397 p_overlap= (blocks_per_group * (keys_per_subgroup - 1)) / keys_per_group;
12398 p_overlap= min(p_overlap, 1.0);
12400 io_cost= min<double>(num_groups * (1 + p_overlap), num_blocks);
12403 io_cost= (keys_per_group > keys_per_block) ?
12404 (have_min && have_max) ? (double) (num_groups + 1) :
12405 (double) num_groups :
12406 (
double) num_blocks;
12421 const double tree_traversal_cost=
12422 ceil(log(static_cast<double>(table_records))/
12427 *read_cost= io_cost + cpu_cost;
12428 *records= num_groups;
12431 (
"table rows: %lu keys/block: %u keys/group: %u result rows: %lu blocks: %u",
12432 (ulong)table_records, keys_per_block, keys_per_group,
12433 (ulong) *records, num_blocks));
12460 TRP_GROUP_MIN_MAX::make_quick(
PARAM *param,
bool retrieve_full_rows,
12464 DBUG_ENTER(
"TRP_GROUP_MIN_MAX::make_quick");
12467 param->thd->lex->current_select->join,
12468 have_min, have_max,
12469 have_agg_distinct, min_max_arg_part,
12470 group_prefix_len, group_key_parts,
12471 used_key_parts, index_info, index,
12472 read_cost, records, key_infix_len,
12473 key_infix, parent_alloc, is_index_scan);
12485 DBUG_ASSERT(quick_prefix_records > 0);
12486 if (quick_prefix_records == HA_POS_ERROR)
12487 quick->quick_prefix_select= NULL;
12491 quick->quick_prefix_select= get_quick_select(param, param_idx,
12496 if (!quick->quick_prefix_select)
12507 if (min_max_arg_part)
12509 SEL_ARG *min_max_range= index_tree;
12510 while (min_max_range)
12512 if (min_max_range->field->eq(min_max_arg_part->field))
12514 min_max_range= min_max_range->next_key_part;
12517 while (min_max_range && min_max_range->prev)
12518 min_max_range= min_max_range->prev;
12520 while (min_max_range)
12522 if (quick->add_range(min_max_range))
12528 min_max_range= min_max_range->next;
12533 quick->quick_prefix_select= NULL;
12535 quick->update_key_stat();
12536 quick->adjust_prefix_ranges();
12538 DBUG_RETURN(quick);
12569 QUICK_GROUP_MIN_MAX_SELECT::
12570 QUICK_GROUP_MIN_MAX_SELECT(
TABLE *table,
JOIN *join_arg,
bool have_min_arg,
12571 bool have_max_arg,
bool have_agg_distinct_arg,
12573 uint group_prefix_len_arg, uint group_key_parts_arg,
12574 uint used_key_parts_arg,
KEY *index_info_arg,
12575 uint use_index,
double read_cost_arg,
12576 ha_rows records_arg, uint key_infix_len_arg,
12577 uchar *key_infix_arg,
MEM_ROOT *parent_alloc,
12578 bool is_index_scan_arg)
12579 :join(join_arg), index_info(index_info_arg),
12580 group_prefix_len(group_prefix_len_arg),
12581 group_key_parts(group_key_parts_arg), have_min(have_min_arg),
12582 have_max(have_max_arg), have_agg_distinct(have_agg_distinct_arg),
12583 seen_first_key(FALSE), min_max_arg_part(min_max_arg_part_arg),
12584 key_infix(key_infix_arg), key_infix_len(key_infix_len_arg),
12585 min_functions_it(NULL), max_functions_it(NULL),
12586 is_index_scan(is_index_scan_arg)
12590 record= head->record[0];
12591 tmp_record= head->record[1];
12592 read_time= read_cost_arg;
12593 records= records_arg;
12594 used_key_parts= used_key_parts_arg;
12595 real_key_parts= used_key_parts_arg;
12596 real_prefix_len= group_prefix_len + key_infix_len;
12597 group_prefix= NULL;
12598 min_max_arg_len= min_max_arg_part ? min_max_arg_part->store_length : 0;
12604 DBUG_ASSERT(!parent_alloc);
12607 init_sql_alloc(&alloc, join->thd->variables.range_alloc_block_size, 0);
12608 join->thd->mem_root= &alloc;
12611 memset(&alloc, 0,
sizeof(
MEM_ROOT));
12632 int QUICK_GROUP_MIN_MAX_SELECT::init()
12637 if (!(last_prefix= (uchar*) alloc_root(&alloc, group_prefix_len)))
12643 if (!(group_prefix= (uchar*) alloc_root(&alloc,
12644 real_prefix_len + min_max_arg_len)))
12647 if (key_infix_len > 0)
12653 uchar *tmp_key_infix= (uchar*) alloc_root(&alloc, key_infix_len);
12654 if (!tmp_key_infix)
12656 memcpy(tmp_key_infix, this->key_infix, key_infix_len);
12657 this->key_infix= tmp_key_infix;
12660 if (min_max_arg_part)
12662 if (my_init_dynamic_array(&min_max_ranges,
sizeof(
QUICK_RANGE*), 16, 16))
12671 min_functions= NULL;
12678 max_functions= NULL;
12681 Item_sum **func_ptr= join->sum_funcs;
12682 while ((min_max_item= *(func_ptr++)))
12684 if (have_min && (min_max_item->sum_func() == Item_sum::MIN_FUNC))
12685 min_functions->push_back(min_max_item);
12686 else if (have_max && (min_max_item->sum_func() == Item_sum::MAX_FUNC))
12687 max_functions->push_back(min_max_item);
12703 min_max_ranges.elements= 0;
12709 QUICK_GROUP_MIN_MAX_SELECT::~QUICK_GROUP_MIN_MAX_SELECT()
12711 DBUG_ENTER(
"QUICK_GROUP_MIN_MAX_SELECT::~QUICK_GROUP_MIN_MAX_SELECT");
12712 if (head->file->inited)
12719 head->file->ha_index_or_rnd_end();
12720 if (min_max_arg_part)
12721 delete_dynamic(&min_max_ranges);
12722 free_root(&alloc,MYF(0));
12723 delete min_functions_it;
12724 delete max_functions_it;
12725 delete quick_prefix_select;
12748 bool QUICK_GROUP_MIN_MAX_SELECT::add_range(
SEL_ARG *sel_range)
12751 uint range_flag= sel_range->min_flag | sel_range->max_flag;
12754 if ((range_flag & NO_MIN_RANGE) && (range_flag & NO_MAX_RANGE))
12757 if (!(sel_range->min_flag & NO_MIN_RANGE) &&
12758 !(sel_range->max_flag & NO_MAX_RANGE))
12760 if (sel_range->maybe_null &&
12761 sel_range->min_value[0] && sel_range->max_value[0])
12762 range_flag|= NULL_RANGE;
12763 else if (memcmp(sel_range->min_value, sel_range->max_value,
12764 min_max_arg_len) == 0)
12765 range_flag|= EQ_RANGE;
12767 range=
new QUICK_RANGE(sel_range->min_value, min_max_arg_len,
12768 make_keypart_map(sel_range->part),
12769 sel_range->max_value, min_max_arg_len,
12770 make_keypart_map(sel_range->part),
12774 if (insert_dynamic(&min_max_ranges, &range))
12797 void QUICK_GROUP_MIN_MAX_SELECT::adjust_prefix_ranges ()
12799 if (quick_prefix_select &&
12800 group_prefix_len < quick_prefix_select->max_used_key_length)
12805 for (inx= 0, arr= &quick_prefix_select->ranges; inx < arr->elements; inx++)
12809 get_dynamic(arr, (uchar*)&range, inx);
12810 range->flag &= ~(NEAR_MIN | NEAR_MAX);
12837 void QUICK_GROUP_MIN_MAX_SELECT::update_key_stat()
12839 max_used_key_length= real_prefix_len;
12840 if (min_max_ranges.elements > 0)
12845 get_dynamic(&min_max_ranges, (uchar*)&cur_range,
12846 min_max_ranges.elements - 1);
12847 if (!(cur_range->flag & NO_MIN_RANGE))
12849 max_used_key_length+= min_max_arg_len;
12856 get_dynamic(&min_max_ranges, (uchar*)&cur_range, 0);
12857 if (!(cur_range->flag & NO_MAX_RANGE))
12859 max_used_key_length+= min_max_arg_len;
12865 else if (have_min && min_max_arg_part &&
12876 max_used_key_length+= min_max_arg_len;
12897 int QUICK_GROUP_MIN_MAX_SELECT::reset(
void)
12900 DBUG_ENTER(
"QUICK_GROUP_MIN_MAX_SELECT::reset");
12902 seen_first_key=
false;
12903 head->set_keyread(TRUE);
12911 DBUG_RETURN(result);
12913 if (quick_prefix_select && quick_prefix_select->reset())
12916 if (result == HA_ERR_END_OF_FILE)
12919 key_copy(last_prefix,
record, index_info, group_prefix_len);
12953 int QUICK_GROUP_MIN_MAX_SELECT::get_next()
12962 volatile int result;
12966 int is_last_prefix= 0;
12968 DBUG_ENTER(
"QUICK_GROUP_MIN_MAX_SELECT::get_next");
12976 result= next_prefix();
12983 is_last_prefix= key_cmp(index_info->key_part, last_prefix,
12985 DBUG_ASSERT(is_last_prefix <= 0);
12989 if (result == HA_ERR_KEY_NOT_FOUND)
12996 min_res= next_min();
12998 update_min_result();
13001 if ((have_max && !have_min) ||
13002 (have_max && have_min && (min_res == 0)))
13004 max_res= next_max();
13006 update_max_result();
13008 DBUG_ASSERT((have_max && !have_min) ||
13009 (have_max && have_min && (max_res == 0)));
13016 if (!have_min && !have_max && key_infix_len > 0)
13018 make_prev_keypart_map(real_key_parts),
13019 HA_READ_KEY_EXACT);
13021 result= have_min ? min_res : have_max ? max_res : result;
13022 }
while ((result == HA_ERR_KEY_NOT_FOUND || result == HA_ERR_END_OF_FILE) &&
13023 is_last_prefix != 0);
13025 if (result == HA_ERR_KEY_NOT_FOUND)
13026 result= HA_ERR_END_OF_FILE;
13028 DBUG_RETURN(result);
13055 int QUICK_GROUP_MIN_MAX_SELECT::next_min()
13058 DBUG_ENTER(
"QUICK_GROUP_MIN_MAX_SELECT::next_min");
13061 if (min_max_ranges.elements > 0)
13063 if ((result= next_min_in_range()))
13064 DBUG_RETURN(result);
13069 if (key_infix_len > 0)
13072 make_prev_keypart_map(real_key_parts),
13073 HA_READ_KEY_EXACT)))
13074 DBUG_RETURN(result);
13084 if (min_max_arg_part && min_max_arg_part->field->is_null())
13086 uchar key_buf[MAX_KEY_LENGTH];
13089 key_copy(key_buf,
record, index_info, max_used_key_length);
13091 make_keypart_map(real_key_parts),
13092 HA_READ_AFTER_KEY);
13105 if (key_cmp(index_info->key_part, group_prefix, real_prefix_len))
13106 key_restore(
record, key_buf, index_info, 0);
13108 else if (result == HA_ERR_KEY_NOT_FOUND || result == HA_ERR_END_OF_FILE)
13117 DBUG_RETURN(result);
13137 int QUICK_GROUP_MIN_MAX_SELECT::next_max()
13141 DBUG_ENTER(
"QUICK_GROUP_MIN_MAX_SELECT::next_max");
13144 if (min_max_ranges.elements > 0)
13145 result= next_max_in_range();
13148 make_prev_keypart_map(real_key_parts),
13149 HA_READ_PREFIX_LAST);
13150 DBUG_RETURN(result);
13179 static int index_next_different (
bool is_index_scan,
handler *file,
13181 const uchar * group_prefix,
13182 uint group_prefix_len,
13183 uint group_key_parts)
13189 while (!key_cmp (key_part, group_prefix, group_prefix_len))
13199 make_prev_keypart_map(group_key_parts),
13200 HA_READ_AFTER_KEY);
13225 int QUICK_GROUP_MIN_MAX_SELECT::next_prefix()
13228 DBUG_ENTER(
"QUICK_GROUP_MIN_MAX_SELECT::next_prefix");
13230 if (quick_prefix_select)
13232 uchar *cur_prefix= seen_first_key ? group_prefix : NULL;
13233 if ((result= quick_prefix_select->get_next_prefix(group_prefix_len,
13236 DBUG_RETURN(result);
13237 seen_first_key= TRUE;
13241 if (!seen_first_key)
13245 DBUG_RETURN(result);
13246 seen_first_key= TRUE;
13251 result= index_next_different (is_index_scan, head->file,
13252 index_info->key_part,
13253 record, group_prefix, group_prefix_len,
13256 DBUG_RETURN(result);
13261 key_copy(group_prefix, record, index_info, group_prefix_len);
13263 if (key_infix_len > 0)
13264 memcpy(group_prefix + group_prefix_len,
13265 key_infix, key_infix_len);
13292 int QUICK_GROUP_MIN_MAX_SELECT::next_min_in_range()
13294 ha_rkey_function find_flag;
13295 key_part_map keypart_map;
13297 bool found_null= FALSE;
13298 int result= HA_ERR_KEY_NOT_FOUND;
13300 DBUG_ASSERT(min_max_ranges.elements > 0);
13302 for (uint range_idx= 0; range_idx < min_max_ranges.elements; range_idx++)
13304 get_dynamic(&min_max_ranges, (uchar*)&cur_range, range_idx);
13310 if (range_idx != 0 && !(cur_range->flag & NO_MAX_RANGE) &&
13311 (key_cmp(min_max_arg_part, (
const uchar*) cur_range->max_key,
13312 min_max_arg_len) == 1))
13315 if (cur_range->flag & NO_MIN_RANGE)
13317 keypart_map= make_prev_keypart_map(real_key_parts);
13318 find_flag= HA_READ_KEY_EXACT;
13323 memcpy(group_prefix + real_prefix_len, cur_range->min_key,
13324 cur_range->min_length);
13325 keypart_map= make_keypart_map(real_key_parts);
13326 find_flag= (cur_range->flag & (EQ_RANGE | NULL_RANGE)) ?
13327 HA_READ_KEY_EXACT : (cur_range->flag & NEAR_MIN) ?
13328 HA_READ_AFTER_KEY : HA_READ_KEY_OR_NEXT;
13335 if ((result == HA_ERR_KEY_NOT_FOUND || result == HA_ERR_END_OF_FILE) &&
13336 (cur_range->flag & (EQ_RANGE | NULL_RANGE)))
13348 if (cur_range->flag & EQ_RANGE)
13351 if (cur_range->flag & NULL_RANGE)
13357 memcpy(tmp_record, record, head->s->rec_buff_length);
13363 if (key_cmp(index_info->key_part, group_prefix, real_prefix_len))
13365 result= HA_ERR_KEY_NOT_FOUND;
13370 if ( !(cur_range->flag & NO_MAX_RANGE) )
13373 uchar *max_key= (uchar*) my_alloca(real_prefix_len + min_max_arg_len);
13374 memcpy(max_key, group_prefix, real_prefix_len);
13375 memcpy(max_key + real_prefix_len, cur_range->max_key,
13376 cur_range->max_length);
13378 int cmp_res= key_cmp(index_info->key_part, max_key,
13379 real_prefix_len + min_max_arg_len);
13386 if (((cur_range->flag & NEAR_MAX) && cmp_res == 0) ||
13389 result= HA_ERR_KEY_NOT_FOUND;
13394 DBUG_ASSERT(result == 0);
13402 if (found_null && result)
13404 memcpy(record, tmp_record, head->s->rec_buff_length);
13432 int QUICK_GROUP_MIN_MAX_SELECT::next_max_in_range()
13434 ha_rkey_function find_flag;
13435 key_part_map keypart_map;
13439 DBUG_ASSERT(min_max_ranges.elements > 0);
13441 for (uint range_idx= min_max_ranges.elements; range_idx > 0; range_idx--)
13443 get_dynamic(&min_max_ranges, (uchar*)&cur_range, range_idx - 1);
13449 if (range_idx != min_max_ranges.elements &&
13450 !(cur_range->flag & NO_MIN_RANGE) &&
13451 (key_cmp(min_max_arg_part, (
const uchar*) cur_range->min_key,
13452 min_max_arg_len) == -1))
13455 if (cur_range->flag & NO_MAX_RANGE)
13457 keypart_map= make_prev_keypart_map(real_key_parts);
13458 find_flag= HA_READ_PREFIX_LAST;
13463 memcpy(group_prefix + real_prefix_len, cur_range->max_key,
13464 cur_range->max_length);
13465 keypart_map= make_keypart_map(real_key_parts);
13466 find_flag= (cur_range->flag & EQ_RANGE) ?
13467 HA_READ_KEY_EXACT : (cur_range->flag & NEAR_MAX) ?
13468 HA_READ_BEFORE_KEY : HA_READ_PREFIX_LAST_OR_PREV;
13476 if ((result == HA_ERR_KEY_NOT_FOUND || result == HA_ERR_END_OF_FILE) &&
13477 (cur_range->flag & EQ_RANGE))
13487 if (cur_range->flag & EQ_RANGE)
13491 if (key_cmp(index_info->key_part, group_prefix, real_prefix_len))
13495 if ( !(cur_range->flag & NO_MIN_RANGE) )
13498 uchar *min_key= (uchar*) my_alloca(real_prefix_len + min_max_arg_len);
13499 memcpy(min_key, group_prefix, real_prefix_len);
13500 memcpy(min_key + real_prefix_len, cur_range->min_key,
13501 cur_range->min_length);
13503 int cmp_res= key_cmp(index_info->key_part, min_key,
13504 real_prefix_len + min_max_arg_len);
13511 if (((cur_range->flag & NEAR_MIN) && cmp_res == 0) ||
13518 return HA_ERR_KEY_NOT_FOUND;
13545 void QUICK_GROUP_MIN_MAX_SELECT::update_min_result()
13549 min_functions_it->rewind();
13550 while ((min_func= (*min_functions_it)++))
13577 void QUICK_GROUP_MIN_MAX_SELECT::update_max_result()
13581 max_functions_it->rewind();
13582 while ((max_func= (*max_functions_it)++))
13602 void QUICK_GROUP_MIN_MAX_SELECT::add_keys_and_lengths(
String *key_names,
13607 key_names->append(index_info->
name);
13608 length= longlong2str(max_used_key_length, buf, 10) -
buf;
13609 used_lengths->append(buf, length);
13627 static bool eq_ranges_exceeds_limit(
SEL_ARG *keypart_root, uint* count, uint limit)
13642 for(
SEL_ARG *keypart_range= keypart_root->first();
13643 keypart_range; keypart_range= keypart_range->next)
13656 if (!keypart_range->min_flag && !keypart_range->max_flag &&
13657 !keypart_range->cmp_max_to_min(keypart_range) &&
13658 !keypart_range->is_null_interval())
13664 if (keypart_range->next_key_part &&
13665 keypart_range->next_key_part->part == keypart_range->part + 1)
13666 eq_ranges_exceeds_limit(keypart_range->next_key_part, count, limit);
13671 if (*count >= limit)
13686 DBUG_ENTER(
"print_sel_tree");
13688 String tmp(buff,
sizeof(buff),&my_charset_bin);
13690 for (idx= 0,key=tree->keys, end=key+param->keys ;
13694 if (tree_map->is_set(idx))
13696 uint keynr= param->real_keynr[idx];
13699 tmp.append(param->table->key_info[keynr].
name);
13703 tmp.append(STRING_WITH_LEN(
"(empty)"));
13705 DBUG_PRINT(
"info", (
"SEL_TREE: %p (%s) scans: %s", tree, msg, tmp.ptr()));
13710 static void print_ror_scans_arr(
TABLE *table,
const char *msg,
13714 DBUG_ENTER(
"print_ror_scans_arr");
13717 String tmp(buff,
sizeof(buff),&my_charset_bin);
13719 for (;start != end; start++)
13723 tmp.append(table->key_info[(*start)->keynr].
name);
13726 tmp.append(STRING_WITH_LEN(
"(empty)"));
13727 DBUG_PRINT(
"info", (
"ROR key scans (%s): %s", msg, tmp.ptr()));
13728 fprintf(DBUG_FILE,
"ROR key scans (%s): %s", msg, tmp.ptr());
13747 Field *field= key_part->field;
13749 if (field->flags & BLOB_FLAG)
13751 out->append(STRING_WITH_LEN(
"unprintable_blob_value"));
13756 String tmp(buff,
sizeof(buff), system_charset_info);
13759 TABLE *table= field->table;
13760 my_bitmap_map *old_sets[2];
13762 dbug_tmp_use_all_columns(table, old_sets, table->read_set,
13765 uint store_length= key_part->store_length;
13776 out->append(STRING_WITH_LEN(
"NULL"));
13777 goto restore_col_map;
13782 field->set_key_image(key, key_part->length);
13783 if (field->type() == MYSQL_TYPE_BIT)
13786 field->val_str(&tmp);
13787 out->append(tmp.ptr(), tmp.length(), tmp.charset());
13790 dbug_tmp_restore_column_maps(table->read_set, table->write_set, old_sets);
13803 void append_range(
String *out,
13805 const uchar *min_key,
const uchar *max_key,
13808 if (out->length() > 0)
13809 out->append(STRING_WITH_LEN(
" AND "));
13811 if (!(flag & NO_MIN_RANGE))
13813 print_key_value(out, key_part, min_key);
13814 if (flag & NEAR_MIN)
13815 out->append(STRING_WITH_LEN(
" < "));
13817 out->append(STRING_WITH_LEN(
" <= "));
13820 out->append(key_part->field->field_name);
13822 if (!(flag & NO_MAX_RANGE))
13824 if (flag & NEAR_MAX)
13825 out->append(STRING_WITH_LEN(
" < "));
13827 out->append(STRING_WITH_LEN(
" <= "));
13828 print_key_value(out, key_part, max_key);
13857 DBUG_ASSERT(keypart_root && keypart_root != &null_element);
13859 const bool append_to_trace= (range_trace != NULL);
13862 DBUG_ASSERT(append_to_trace ? !range_string : (range_string != NULL));
13865 const KEY_PART_INFO *cur_key_part= key_parts + keypart_root->part;
13866 const SEL_ARG *keypart_range= keypart_root->first();
13868 const uint save_range_so_far_length= range_so_far->length();
13870 while (keypart_range)
13877 if (!append_to_trace && range_string->length() > 500)
13879 range_string->append(STRING_WITH_LEN(
"..."));
13884 append_range(range_so_far, cur_key_part,
13885 keypart_range->min_value, keypart_range->max_value,
13886 keypart_range->min_flag | keypart_range->max_flag);
13895 if (keypart_range->next_key_part &&
13896 keypart_range->next_key_part->part == keypart_range->part + 1 &&
13897 keypart_range->is_singlepoint())
13899 append_range_all_keyparts(range_trace, range_string, range_so_far,
13900 keypart_range->next_key_part, key_parts);
13908 if (append_to_trace)
13909 range_trace->add_utf8(range_so_far->ptr(),
13910 range_so_far->length());
13913 if (range_string->length() == 0)
13914 range_string->append(STRING_WITH_LEN(
"("));
13916 range_string->append(STRING_WITH_LEN(
" OR ("));
13918 range_string->append(range_so_far->ptr(), range_so_far->length());
13919 range_string->append(STRING_WITH_LEN(
")"));
13922 keypart_range= keypart_range->next;
13928 range_so_far->length(save_range_so_far_length);
13939 static inline void dbug_print_tree(
const char *tree_name,
13944 if (!param->using_real_indexes)
13948 "%s uses a partitioned index and cannot be printed",
13955 DBUG_PRINT(
"info", (
"sel_tree: %s is NULL", tree_name));
13959 if (tree->type == SEL_TREE::IMPOSSIBLE)
13961 DBUG_PRINT(
"info", (
"sel_tree: %s is IMPOSSIBLE", tree_name));
13965 if (tree->type == SEL_TREE::ALWAYS)
13967 DBUG_PRINT(
"info", (
"sel_tree: %s is ALWAYS", tree_name));
13971 if (tree->type == SEL_TREE::MAYBE)
13973 DBUG_PRINT(
"info", (
"sel_tree: %s is MAYBE", tree_name));
13977 if (!tree->merges.is_empty())
13981 "%s contains the following merges", tree_name));
13985 for (
SEL_IMERGE *el= it++; el; el= it++, i++)
13987 for (
SEL_TREE** current= el->trees;
13988 current != el->trees_next;
13990 dbug_print_tree(
" merge_tree", *current, param);
13994 for (uint i= 0; i< param->keys; i++)
13996 if (tree->keys[i] == NULL || tree->keys[i] == &null_element)
13999 uint real_key_nr= param->real_keynr[
i];
14001 const KEY &cur_key= param->table->key_info[real_key_nr];
14009 String range_result(buff1,
sizeof(buff1), system_charset_info);
14010 range_result.length(0);
14017 String range_so_far(buff2,
sizeof(buff2), system_charset_info);
14018 range_so_far.length(0);
14020 append_range_all_keyparts(NULL, &range_result, &range_so_far,
14021 tree->keys[i], key_part);
14024 (
"sel_tree: %s->keys[%d(real_keynr: %d)]: %s",
14025 tree_name, i, real_key_nr, range_result.ptr()));
14040 print_multiple_key_values(
KEY_PART *key_part,
const uchar *key,
14044 const uchar *key_end= key+used_length;
14045 String tmp(buff,
sizeof(buff),&my_charset_bin);
14047 TABLE *table= key_part->field->table;
14048 my_bitmap_map *old_sets[2];
14050 dbug_tmp_use_all_columns(table, old_sets, table->read_set, table->write_set);
14052 for (; key < key_end; key+=store_length, key_part++)
14054 Field *field= key_part->field;
14055 store_length= key_part->store_length;
14061 fwrite(
"NULL",
sizeof(
char),4,DBUG_FILE);
14067 field->set_key_image(key, key_part->length);
14068 if (field->type() == MYSQL_TYPE_BIT)
14071 field->val_str(&tmp);
14072 fwrite(tmp.ptr(),
sizeof(char),tmp.length(),DBUG_FILE);
14073 if (key+store_length < key_end)
14074 fputc(
'/',DBUG_FILE);
14076 dbug_tmp_restore_column_maps(table->read_set, table->write_set, old_sets);
14081 char buf[MAX_KEY/8+1];
14083 my_bitmap_map *old_sets[2];
14084 DBUG_ENTER(
"print_quick");
14089 table= quick->head;
14090 dbug_tmp_use_all_columns(table, old_sets, table->read_set, table->write_set);
14091 quick->dbug_dump(0, TRUE);
14092 dbug_tmp_restore_column_maps(table->read_set, table->write_set, old_sets);
14094 fprintf(DBUG_FILE,
"other_keys: 0x%s:\n", needed_reg->print(buf));
14100 void QUICK_RANGE_SELECT::dbug_dump(
int indent,
bool verbose)
14103 fprintf(DBUG_FILE,
"%*squick range select, key %s, length: %d\n",
14104 indent,
"", head->key_info[index].
name, max_used_key_length);
14111 for (; pr != end_range; ++pr)
14113 fprintf(DBUG_FILE,
"%*s", indent + 2,
"");
14115 if (!(range->flag & NO_MIN_RANGE))
14117 print_multiple_key_values(key_parts, range->min_key,
14118 range->min_length);
14119 if (range->flag & NEAR_MIN)
14120 fputs(
" < ",DBUG_FILE);
14122 fputs(
" <= ",DBUG_FILE);
14124 fputs(
"X",DBUG_FILE);
14126 if (!(range->flag & NO_MAX_RANGE))
14128 if (range->flag & NEAR_MAX)
14129 fputs(
" < ",DBUG_FILE);
14131 fputs(
" <= ",DBUG_FILE);
14132 print_multiple_key_values(key_parts, range->max_key,
14133 range->max_length);
14135 fputs(
"\n",DBUG_FILE);
14141 void QUICK_INDEX_MERGE_SELECT::dbug_dump(
int indent,
bool verbose)
14145 fprintf(DBUG_FILE,
"%*squick index_merge select\n", indent,
"");
14146 fprintf(DBUG_FILE,
"%*smerged scans {\n", indent,
"");
14147 while ((quick= it++))
14148 quick->dbug_dump(indent+2, verbose);
14149 if (pk_quick_select)
14151 fprintf(DBUG_FILE,
"%*sclustered PK quick:\n", indent,
"");
14152 pk_quick_select->dbug_dump(indent+2, verbose);
14154 fprintf(DBUG_FILE,
"%*s}\n", indent,
"");
14157 void QUICK_ROR_INTERSECT_SELECT::dbug_dump(
int indent,
bool verbose)
14161 fprintf(DBUG_FILE,
"%*squick ROR-intersect select, %scovering\n",
14162 indent,
"", need_to_fetch_row?
"":
"non-");
14163 fprintf(DBUG_FILE,
"%*smerged scans {\n", indent,
"");
14164 while ((quick= it++))
14165 quick->dbug_dump(indent+2, verbose);
14168 fprintf(DBUG_FILE,
"%*sclustered PK quick:\n", indent,
"");
14169 cpk_quick->dbug_dump(indent+2, verbose);
14171 fprintf(DBUG_FILE,
"%*s}\n", indent,
"");
14174 void QUICK_ROR_UNION_SELECT::dbug_dump(
int indent,
bool verbose)
14178 fprintf(DBUG_FILE,
"%*squick ROR-union select\n", indent,
"");
14179 fprintf(DBUG_FILE,
"%*smerged scans {\n", indent,
"");
14180 while ((quick= it++))
14181 quick->dbug_dump(indent+2, verbose);
14182 fprintf(DBUG_FILE,
"%*s}\n", indent,
"");
14205 void QUICK_GROUP_MIN_MAX_SELECT::dbug_dump(
int indent,
bool verbose)
14208 "%*squick_group_min_max_select: index %s (%d), length: %d\n",
14209 indent,
"", index_info->
name, index, max_used_key_length);
14210 if (key_infix_len > 0)
14212 fprintf(DBUG_FILE,
"%*susing key_infix with length %d:\n",
14213 indent,
"", key_infix_len);
14215 if (quick_prefix_select)
14217 fprintf(DBUG_FILE,
"%*susing quick_range_select:\n", indent,
"");
14218 quick_prefix_select->dbug_dump(indent + 2, verbose);
14220 if (min_max_ranges.elements > 0)
14222 fprintf(DBUG_FILE,
"%*susing %d quick_ranges for MIN/MAX:\n",
14223 indent,
"", min_max_ranges.elements);