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);