diff options
Diffstat (limited to 'sql/opt_range.cc')
| -rw-r--r-- | sql/opt_range.cc | 318 |
1 files changed, 276 insertions, 42 deletions
diff --git a/sql/opt_range.cc b/sql/opt_range.cc index 42f20c0f767..181d97ceacc 100644 --- a/sql/opt_range.cc +++ b/sql/opt_range.cc @@ -33,6 +33,7 @@ #include <m_ctype.h> #include <nisam.h> #include "sql_select.h" +#include <assert.h> #ifndef EXTRA_DEBUG @@ -66,7 +67,9 @@ public: SEL_ARG(Field *field, uint8 part, char *min_value, char *max_value, uint8 min_flag, uint8 max_flag, uint8 maybe_flag); SEL_ARG(enum Type type_arg) - :elements(1),use_count(1),left(0),next_key_part(0),type(type_arg) {} + :elements(1),use_count(1),left(0),next_key_part(0),color(BLACK), + type(type_arg) + {} inline bool is_same(SEL_ARG *arg) { if (type != arg->type) @@ -279,21 +282,21 @@ public: typedef struct st_qsel_param { - uint baseflag,keys,max_key_part; - table_map prev_tables,read_tables,current_table; TABLE *table; - bool quick; // Don't calulate possible keys KEY_PART *key_parts,*key_parts_end,*key[MAX_KEY]; + MEM_ROOT *mem_root; + table_map prev_tables,read_tables,current_table; + uint baseflag,keys,max_key_part; uint real_keynr[MAX_KEY]; char min_key[MAX_KEY_LENGTH+MAX_FIELD_WIDTH], max_key[MAX_KEY_LENGTH+MAX_FIELD_WIDTH]; + bool quick; // Don't calulate possible keys } PARAM; - static SEL_TREE * get_mm_parts(PARAM *param,Field *field, Item_func::Functype type,Item *value, Item_result cmp_type); -static SEL_ARG *get_mm_leaf(Field *field,KEY_PART *key_part, +static SEL_ARG *get_mm_leaf(PARAM *param,Field *field,KEY_PART *key_part, Item_func::Functype type,Item *value); static bool like_range(const char *ptr,uint length,char wild_prefix, uint field_length, char *min_str,char *max_str, @@ -382,7 +385,7 @@ SQL_SELECT::~SQL_SELECT() #undef index // Fix for Unixware 7 QUICK_SELECT::QUICK_SELECT(TABLE *table,uint key_nr,bool no_alloc) - :error(0),index(key_nr),max_used_key_length(0),head(table), + :dont_free(0),error(0),index(key_nr),max_used_key_length(0),head(table), it(ranges),range(0) { if (!no_alloc) @@ -399,13 +402,11 @@ QUICK_SELECT::QUICK_SELECT(TABLE *table,uint key_nr,bool no_alloc) QUICK_SELECT::~QUICK_SELECT() { - file->index_end(); - free_root(&alloc,MYF(0)); -} - -int QUICK_SELECT::init() -{ - return error=file->index_init(index); + if (!dont_free) + { + file->index_end(); + free_root(&alloc,MYF(0)); + } } QUICK_RANGE::QUICK_RANGE() @@ -533,7 +534,7 @@ static int sel_cmp(Field *field, char *a,char *b,uint8 a_flag,uint8 b_flag) } if (*a) goto end; // NULL where equal - a++; b++; // Skipp NULL marker + a++; b++; // Skip NULL marker } cmp=field->key_cmp((byte*) a,(byte*) b); if (cmp) return cmp < 0 ? -1 : 1; // The values differed @@ -586,6 +587,9 @@ int SQL_SELECT::test_quick_select(key_map keys_to_use, table_map prev_tables, uint idx; double scan_time; DBUG_ENTER("test_quick_select"); + DBUG_PRINT("enter",("keys_to_use: %lu prev_tables: %lu const_tables: %lu", + (ulong) keys_to_use, (ulong) prev_tables, + (ulong) const_tables)); delete quick; quick=0; @@ -593,7 +597,7 @@ int SQL_SELECT::test_quick_select(key_map keys_to_use, table_map prev_tables, if (!cond || (specialflag & SPECIAL_SAFE_MODE) && ! force_quick_range || !limit) DBUG_RETURN(0); /* purecov: inspected */ - if (!((basflag= head->file->option_flag()) & HA_KEYPOS_TO_RNDPOS) && + if (!((basflag= head->file->table_flags()) & HA_KEYPOS_TO_RNDPOS) && keys_to_use == (uint) ~0 || !keys_to_use) DBUG_RETURN(0); /* Not smart database */ records=head->file->records; @@ -604,7 +608,7 @@ int SQL_SELECT::test_quick_select(key_map keys_to_use, table_map prev_tables, if (limit < records) read_time=(double) records+scan_time+1; // Force to use index else if (read_time <= 2.0 && !force_quick_range) - DBUG_RETURN(0); /* No nead for quick select */ + DBUG_RETURN(0); /* No need for quick select */ DBUG_PRINT("info",("Time to scan table: %ld",(long) read_time)); @@ -623,6 +627,7 @@ int SQL_SELECT::test_quick_select(key_map keys_to_use, table_map prev_tables, param.current_table= head->map; param.table=head; param.keys=0; + param.mem_root= &alloc; current_thd->no_errors=1; // Don't warn about NULL init_sql_alloc(&alloc,2048,0); @@ -679,27 +684,27 @@ int SQL_SELECT::test_quick_select(key_map keys_to_use, table_map prev_tables, { ha_rows found_records; double found_read_time; - if (*key) { + uint keynr= param.real_keynr[idx]; if ((*key)->type == SEL_ARG::MAYBE_KEY || (*key)->maybe_flag) - needed_reg|= (key_map) 1 << param.real_keynr[idx]; + needed_reg|= (key_map) 1 << keynr; - found_records=check_quick_select(¶m,idx, *key); + found_records=check_quick_select(¶m, idx, *key); if (found_records != HA_POS_ERROR && found_records > 2 && - head->used_keys & ((table_map) 1 << param.real_keynr[idx]) && - (head->file->option_flag() & HA_HAVE_KEY_READ_ONLY)) + head->used_keys & ((table_map) 1 << keynr) && + (head->file->index_flags(keynr) & HA_KEY_READ_ONLY)) { /* - ** We can resolve this by only reading through this key - ** Assume that we will read trough the whole key range - ** and that all key blocks are half full (normally things are - ** much better) + We can resolve this by only reading through this key. + Assume that we will read trough the whole key range + and that all key blocks are half full (normally things are + much better). */ - uint keys_per_block= head->file->block_size/2/ - (head->key_info[param.real_keynr[idx]].key_length+ - head->file->ref_length) + 1; + uint keys_per_block= (head->file->block_size/2/ + (head->key_info[keynr].key_length+ + head->file->ref_length) + 1); found_read_time=((double) (found_records+keys_per_block-1)/ (double) keys_per_block); } @@ -882,7 +887,7 @@ get_mm_parts(PARAM *param,Field *field, Item_func::Functype type,Item *value, if (value && value->used_tables() & ~(param->prev_tables | param->read_tables)) DBUG_RETURN(0); - for ( ; key_part != end ; key_part++) + for (; key_part != end ; key_part++) { if (field->eq(key_part->field)) { @@ -891,7 +896,7 @@ get_mm_parts(PARAM *param,Field *field, Item_func::Functype type,Item *value, tree=new SEL_TREE(); if (!value || !(value->used_tables() & ~param->read_tables)) { - sel_arg=get_mm_leaf(key_part->field,key_part,type,value); + sel_arg=get_mm_leaf(param,key_part->field,key_part,type,value); if (!sel_arg) continue; if (sel_arg->type == SEL_ARG::IMPOSSIBLE) @@ -911,7 +916,7 @@ get_mm_parts(PARAM *param,Field *field, Item_func::Functype type,Item *value, static SEL_ARG * -get_mm_leaf(Field *field,KEY_PART *key_part, +get_mm_leaf(PARAM *param, Field *field, KEY_PART *key_part, Item_func::Functype type,Item *value) { uint maybe_null=(uint) field->real_maybe_null(); @@ -926,7 +931,7 @@ get_mm_leaf(Field *field,KEY_PART *key_part, String tmp(buff1,sizeof(buff1)),*res; uint length,offset,min_length,max_length; - if (!field->optimize_range()) + if (!field->optimize_range((uint) key_part->key)) DBUG_RETURN(0); // Can't optimize this if (!(res= value->val_str(&tmp))) DBUG_RETURN(&null_element); @@ -956,7 +961,7 @@ get_mm_leaf(Field *field,KEY_PART *key_part, field_length=length; } length+=offset; - if (!(min_str= (char*) sql_alloc(length*2))) + if (!(min_str= (char*) alloc_root(param->mem_root, length*2))) DBUG_RETURN(0); max_str=min_str+length; if (maybe_null) @@ -1007,7 +1012,8 @@ get_mm_leaf(Field *field,KEY_PART *key_part, DBUG_RETURN(tree); } - if (!field->optimize_range() && type != Item_func::EQ_FUNC && + if (!field->optimize_range((uint) key_part->key) && + type != Item_func::EQ_FUNC && type != Item_func::EQUAL_FUNC) DBUG_RETURN(0); // Can't optimize this @@ -1020,10 +1026,12 @@ get_mm_leaf(Field *field,KEY_PART *key_part, if (value->save_in_field(field)) { + // TODO; Check if we can we remove the following block. if (type == Item_func::EQUAL_FUNC) { /* convert column_name <=> NULL -> column_name IS NULL */ - char *str= (char*) sql_alloc(1); // Get local copy of key + // Get local copy of key + char *str= (char*) alloc_root(param->mem_root,1); if (!*str) DBUG_RETURN(0); *str = 1; @@ -1032,7 +1040,8 @@ get_mm_leaf(Field *field,KEY_PART *key_part, DBUG_RETURN(&null_element); // NULL is never true } // Get local copy of key - char *str= (char*) sql_alloc(key_part->part_length+maybe_null); + char *str= (char*) alloc_root(param->mem_root, + key_part->part_length+maybe_null); if (!str) DBUG_RETURN(0); if (maybe_null) @@ -1098,7 +1107,7 @@ static bool like_range(const char *ptr,uint ptr_length,char escape, { if (*ptr == escape && ptr+1 != end) { - ptr++; // Skipp escape + ptr++; // Skip escape *min_str++= *max_str++ = *ptr; continue; } @@ -2233,7 +2242,7 @@ get_quick_select(PARAM *param,uint idx,SEL_ARG *key_tree) else { quick->key_parts=(KEY_PART*) - sql_memdup(param->key[idx], + memdup_root(&quick->alloc,(char*) param->key[idx], sizeof(KEY_PART)* param->table->key_info[param->real_keynr[idx]].key_parts); } @@ -2404,7 +2413,7 @@ QUICK_SELECT *get_quick_select_for_ref(TABLE *table, TABLE_REF *ref) (key_info->flags & HA_NOSAME)) ? EQ_RANGE : 0); if (!(quick->key_parts=key_part=(KEY_PART *) - sql_alloc(sizeof(KEY_PART)*ref->key_parts))) + alloc_root(&quick->alloc,sizeof(KEY_PART)*ref->key_parts))) goto err; for (part=0 ; part < ref->key_parts ;part++,key_part++) @@ -2456,8 +2465,8 @@ int QUICK_SELECT::get_next() if ((error=file->index_first(record))) DBUG_RETURN(error); // Empty table if (cmp_next(range) == 0) - DBUG_RETURN(0); // No matching records - range=0; // To next range + DBUG_RETURN(0); + range=0; // No matching records; go to next range continue; } if ((result = file->index_read(record,(byte*) range->min_key, @@ -2517,6 +2526,231 @@ int QUICK_SELECT::cmp_next(QUICK_RANGE *range) return (range->flag & NEAR_MAX) ? 1 : 0; // Exact match } + +/* + This is a hack: we inherit from QUICK_SELECT so that we can use the + get_next() interface, but we have to hold a pointer to the original + QUICK_SELECT because its data are used all over the place. What + should be done is to factor out the data that is needed into a base + class (QUICK_SELECT), and then have two subclasses (_ASC and _DESC) + which handle the ranges and implement the get_next() function. But + for now, this seems to work right at least. + */ + +QUICK_SELECT_DESC::QUICK_SELECT_DESC(QUICK_SELECT *q, uint used_key_parts) + : QUICK_SELECT(*q), rev_it(rev_ranges) +{ + bool not_read_after_key = file->table_flags() & HA_NOT_READ_AFTER_KEY; + QUICK_RANGE *r; + + it.rewind(); + for (r = it++; r; r = it++) + { + rev_ranges.push_front(r); + if (not_read_after_key && range_reads_after_key(r) || + test_if_null_range(r,used_key_parts)) + { + it.rewind(); // Reset range + error = HA_ERR_UNSUPPORTED; + dont_free=1; // Don't free memory from 'q' + return; + } + } + /* Remove EQ_RANGE flag for keys that are not using the full key */ + for (r = rev_it++; r; r = rev_it++) + { + if ((r->flag & EQ_RANGE) && + head->key_info[index].key_length != r->max_length) + r->flag&= ~EQ_RANGE; + } + rev_it.rewind(); + q->dont_free=1; // Don't free shared mem + delete q; +} + + +int QUICK_SELECT_DESC::get_next() +{ + DBUG_ENTER("QUICK_SELECT_DESC::get_next"); + + /* The max key is handled as follows: + * - if there is NO_MAX_RANGE, start at the end and move backwards + * - if it is an EQ_RANGE, which means that max key covers the entire + * key, go directly to the key and read through it (sorting backwards is + * same as sorting forwards) + * - if it is NEAR_MAX, go to the key or next, step back once, and + * move backwards + * - otherwise (not NEAR_MAX == include the key), go after the key, + * step back once, and move backwards + */ + + for (;;) + { + int result; + if (range) + { // Already read through key + result = ((range->flag & EQ_RANGE) + ? file->index_next_same(record, (byte*) range->min_key, + range->min_length) : + file->index_prev(record)); + if (!result) + { + if (cmp_prev(*rev_it.ref()) == 0) + DBUG_RETURN(0); + } + else if (result != HA_ERR_END_OF_FILE) + DBUG_RETURN(result); + } + + if (!(range=rev_it++)) + DBUG_RETURN(HA_ERR_END_OF_FILE); // All ranges used + + if (range->flag & NO_MAX_RANGE) // Read last record + { + int error; + if ((error=file->index_last(record))) + DBUG_RETURN(error); // Empty table + if (cmp_prev(range) == 0) + DBUG_RETURN(0); + range=0; // No matching records; go to next range + continue; + } + + if (range->flag & EQ_RANGE) + { + result = file->index_read(record, (byte*) range->max_key, + range->max_length, HA_READ_KEY_EXACT); + } + else + { + /* Heikki changed Sept 11, 2002: since InnoDB does not store the cursor + position if READ_KEY_EXACT is used to a primary key with all + key columns specified, we must use below HA_READ_KEY_OR_NEXT, + so that InnoDB stores the cursor position and is able to move + the cursor one step backward after the search. */ + + DBUG_ASSERT(range->flag & NEAR_MAX || range_reads_after_key(range)); + /* Note: even if max_key is only a prefix, HA_READ_AFTER_KEY will + * do the right thing - go past all keys which match the prefix */ + result=file->index_read(record, (byte*) range->max_key, + range->max_length, + ((range->flag & NEAR_MAX) ? + HA_READ_KEY_OR_NEXT : HA_READ_AFTER_KEY)); + result = file->index_prev(record); + } + if (result) + { + if (result != HA_ERR_KEY_NOT_FOUND) + DBUG_RETURN(result); + range=0; // Not found, to next range + continue; + } + if (cmp_prev(range) == 0) + { + if (range->flag == (UNIQUE_RANGE | EQ_RANGE)) + range = 0; // Stop searching + DBUG_RETURN(0); // Found key is in range + } + range = 0; // To next range + } +} + +/* + * Returns 0 if found key is inside range (found key >= range->min_key). + */ +int QUICK_SELECT_DESC::cmp_prev(QUICK_RANGE *range) +{ + if (range->flag & NO_MIN_RANGE) + return (0); /* key can't be to small */ + + KEY_PART *key_part = key_parts; + for (char *key = range->min_key, *end = key + range->min_length; + key < end; + key += key_part++->part_length) + { + int cmp; + if (key_part->null_bit) + { + // this key part allows null values; NULL is lower than everything else + if (*key++) + { + // the range is expecting a null value + if (!key_part->field->is_null()) + return 0; // not null -- still inside the range + continue; // null -- exact match, go to next key part + } + else if (key_part->field->is_null()) + return 1; // null -- outside the range + } + if ((cmp = key_part->field->key_cmp((byte*) key, + key_part->part_length)) > 0) + return 0; + if (cmp < 0) + return 1; + } + return (range->flag & NEAR_MIN) ? 1 : 0; // Exact match +} + +/* + * True if this range will require using HA_READ_AFTER_KEY + See comment in get_next() about this + */ + +bool QUICK_SELECT_DESC::range_reads_after_key(QUICK_RANGE *range) +{ + return ((range->flag & (NO_MAX_RANGE | NEAR_MAX)) || + !(range->flag & EQ_RANGE) || + head->key_info[index].key_length != range->max_length) ? 1 : 0; +} + +/* True if we are reading over a key that may have a NULL value */ + +bool QUICK_SELECT_DESC::test_if_null_range(QUICK_RANGE *range, + uint used_key_parts) +{ + uint offset,end; + KEY_PART *key_part = key_parts, + *key_part_end= key_part+used_key_parts; + + for (offset= 0, end = min(range->min_length, range->max_length) ; + offset < end && key_part != key_part_end ; + offset += key_part++->part_length) + { + uint null_length=test(key_part->null_bit); + if (!memcmp((char*) range->min_key+offset, (char*) range->max_key+offset, + key_part->part_length + null_length)) + { + offset+=null_length; + continue; + } + if (null_length && range->min_key[offset]) + return 1; // min_key is null and max_key isn't + // Range doesn't cover NULL. This is ok if there is no more null parts + break; + } + /* + If the next min_range is > NULL, then we can use this, even if + it's a NULL key + Example: SELECT * FROM t1 WHERE a = 2 AND b >0 ORDER BY a DESC,b DESC; + + */ + if (key_part != key_part_end && key_part->null_bit) + { + if (offset >= range->min_length || range->min_key[offset]) + return 1; // Could be null + key_part++; + } + /* + If any of the key parts used in the ORDER BY could be NULL, we can't + use the key to sort the data. + */ + for (; key_part != key_part_end ; key_part++) + if (key_part->null_bit) + return 1; // Covers null part + return 0; +} + + /***************************************************************************** ** Print a quick range for debugging ** TODO: |