diff options
| -rw-r--r-- | mysql-test/r/select.result | 2 | ||||
| -rw-r--r-- | mysql-test/r/subselect.result | 8 | ||||
| -rw-r--r-- | sql/item.cc | 89 | ||||
| -rw-r--r-- | sql/item.h | 16 | ||||
| -rw-r--r-- | sql/item_cmpfunc.cc | 131 | ||||
| -rw-r--r-- | sql/item_cmpfunc.h | 95 | ||||
| -rw-r--r-- | sql/item_func.cc | 45 | ||||
| -rw-r--r-- | sql/item_func.h | 3 | ||||
| -rw-r--r-- | sql/item_row.cc | 6 | ||||
| -rw-r--r-- | sql/item_row.h | 2 | ||||
| -rw-r--r-- | sql/item_strfunc.h | 6 | ||||
| -rw-r--r-- | sql/opt_range.cc | 148 | ||||
| -rw-r--r-- | sql/sql_list.h | 10 | ||||
| -rw-r--r-- | sql/sql_select.cc | 401 |
14 files changed, 677 insertions, 285 deletions
diff --git a/mysql-test/r/select.result b/mysql-test/r/select.result index d8cd0cf1037..a609cc20225 100644 --- a/mysql-test/r/select.result +++ b/mysql-test/r/select.result @@ -1470,7 +1470,7 @@ explain extended select count(*),min(fld4),max(fld4),sum(fld1),avg(fld1),std(fld id select_type table type possible_keys key key_len ref rows Extra 1 SIMPLE t2 ALL NULL NULL NULL NULL 1199 Using where Warnings: -Note 1003 select high_priority count(0) AS `count(*)`,min(test.t2.fld4) AS `min(fld4)`,max(test.t2.fld4) AS `max(fld4)`,sum(test.t2.fld1) AS `sum(fld1)`,avg(test.t2.fld1) AS `avg(fld1)`,std(test.t2.fld1) AS `std(fld1)`,variance(test.t2.fld1) AS `variance(fld1)` from test.t2 where ((test.t2.fld4 <> _latin1'') and (test.t2.companynr = 34)) +Note 1003 select high_priority count(0) AS `count(*)`,min(test.t2.fld4) AS `min(fld4)`,max(test.t2.fld4) AS `max(fld4)`,sum(test.t2.fld1) AS `sum(fld1)`,avg(test.t2.fld1) AS `avg(fld1)`,std(test.t2.fld1) AS `std(fld1)`,variance(test.t2.fld1) AS `variance(fld1)` from test.t2 where ((test.t2.companynr = 34) and (test.t2.fld4 <> _latin1'')) select companynr,count(*),min(fld4),max(fld4),sum(fld1),avg(fld1),std(fld1),variance(fld1) from t2 group by companynr limit 3; companynr count(*) min(fld4) max(fld4) sum(fld1) avg(fld1) std(fld1) variance(fld1) 00 82 Anthony windmills 10355753 126289.6707 115550.9757 13352027981.7087 diff --git a/mysql-test/r/subselect.result b/mysql-test/r/subselect.result index 8607fe6fe2d..3a2de4035eb 100644 --- a/mysql-test/r/subselect.result +++ b/mysql-test/r/subselect.result @@ -540,7 +540,7 @@ id select_type table type possible_keys key key_len ref rows Extra 1 PRIMARY t1 const PRIMARY,numreponse PRIMARY 7 const,const 1 2 SUBQUERY NULL NULL NULL NULL NULL NULL NULL Select tables optimized away Warnings: -Note 1003 select high_priority test.t1.numreponse AS `numreponse` from test.t1 where ((test.t1.numeropost = _latin1'1') and (test.t1.numreponse = (select max(test.t1.numreponse) AS `MAX(numreponse)` from test.t1 where (test.t1.numeropost = _latin1'1')))) +Note 1003 select high_priority test.t1.numreponse AS `numreponse` from test.t1 where ((test.t1.numreponse = (select max(test.t1.numreponse) AS `MAX(numreponse)` from test.t1 where (test.t1.numeropost = _latin1'1'))) and (test.t1.numeropost = _latin1'1')) drop table t1; CREATE TABLE t1 (a int(1)); INSERT INTO t1 VALUES (1); @@ -899,7 +899,7 @@ id select_type table type possible_keys key key_len ref rows Extra 2 DEPENDENT SUBQUERY t2 ref_or_null a a 5 func 2 Using where; Using index 2 DEPENDENT SUBQUERY t3 ALL NULL NULL NULL NULL 3 Using where Warnings: -Note 1003 select high_priority test.t1.a AS `a`,<in_optimizer>(test.t1.a,<exists>(select 1 AS `Not_used` from test.t2 join test.t3 where (((<cache>(test.t1.a) = test.t2.a) or isnull(test.t2.a)) and (test.t3.a = test.t2.a)) having <is_not_null_test>(test.t2.a) limit 1)) AS `t1.a in (select t2.a from t2,t3 where t3.a=t2.a)` from test.t1 +Note 1003 select high_priority test.t1.a AS `a`,<in_optimizer>(test.t1.a,<exists>(select 1 AS `Not_used` from test.t2 join test.t3 where ((test.t3.a = test.t2.a) and ((<cache>(test.t1.a) = test.t2.a) or isnull(test.t2.a))) having <is_not_null_test>(test.t2.a) limit 1)) AS `t1.a in (select t2.a from t2,t3 where t3.a=t2.a)` from test.t1 drop table t1,t2,t3; create table t1 (a float); select 10.5 IN (SELECT * from t1 LIMIT 1); @@ -1312,7 +1312,7 @@ id select_type table type possible_keys key key_len ref rows Extra 2 DEPENDENT SUBQUERY t1 eq_ref PRIMARY PRIMARY 4 func 1 Using where 2 DEPENDENT SUBQUERY t3 eq_ref PRIMARY PRIMARY 4 test.t1.b 1 Using where; Using index Warnings: -Note 1003 select high_priority test.t2.a AS `a` from test.t2 where <in_optimizer>(test.t2.a,<exists>(select 1 AS `Not_used` from test.t1 join test.t3 where ((<cache>(test.t2.a) = test.t1.a) and (test.t3.a = test.t1.b)) limit 1)) +Note 1003 select high_priority test.t2.a AS `a` from test.t2 where <in_optimizer>(test.t2.a,<exists>(select 1 AS `Not_used` from test.t1 join test.t3 where ((test.t3.a = test.t1.b) and (<cache>(test.t2.a) = test.t1.a)) limit 1)) drop table t1, t2, t3; create table t1 (a int, b int, index a (a,b)); create table t2 (a int, index a (a)); @@ -1351,7 +1351,7 @@ id select_type table type possible_keys key key_len ref rows Extra 2 DEPENDENT SUBQUERY t1 ref a a 5 func 1001 Using where; Using index 2 DEPENDENT SUBQUERY t3 index a a 5 NULL 3 Using where; Using index Warnings: -Note 1003 select high_priority test.t2.a AS `a` from test.t2 where <in_optimizer>(test.t2.a,<exists>(select 1 AS `Not_used` from test.t1 join test.t3 where ((<cache>(test.t2.a) = test.t1.a) and (test.t3.a = test.t1.b)) limit 1)) +Note 1003 select high_priority test.t2.a AS `a` from test.t2 where <in_optimizer>(test.t2.a,<exists>(select 1 AS `Not_used` from test.t1 join test.t3 where ((test.t3.a = test.t1.b) and (<cache>(test.t2.a) = test.t1.a)) limit 1)) insert into t1 values (3,31); select * from t2 where t2.a in (select a from t1 where t1.b <> 30); a diff --git a/sql/item.cc b/sql/item.cc index f9c1843707c..8744bc3574b 100644 --- a/sql/item.cc +++ b/sql/item.cc @@ -994,6 +994,28 @@ bool Item_field::fix_fields(THD *thd, TABLE_LIST *tables, Item **ref) return 0; } + +/* + Find a field among specified multiple equalities + + SYNOPSIS + find_item_equal() + cond_equal reference to list of multiple equalities where + the field (this object) is to be looked for + + DESCRIPTION + The function first searches the field among multiple equalities + of the current level (in the cond_equal->current_level list). + If it fails, it continues searching in upper levels accessed + through a pointer cond_equal->upper_levels. + The search terminates as soon as a multiple equality containing + the field is found. + + RETURN VALUES + First Item_equal containing the field, if success + 0, otherwise +*/ + Item_equal *Item_field::find_item_equal(COND_EQUAL *cond_equal) { Item_equal *item= 0; @@ -1005,31 +1027,82 @@ Item_equal *Item_field::find_item_equal(COND_EQUAL *cond_equal) if (item->contains(field)) return item; } - cond_equal= cond_equal->parent_level; + /* + The field is not found in any of the multiple equalities + of the current level. Look for it in upper levels + */ + cond_equal= cond_equal->upper_levels; } - return item; + return 0; } + +/* + Set a pointer to the multiple equality the field reference belongs to (if any) + + SYNOPSIS + equal_fields_propagator() + arg - reference to list of multiple equalities where + the field (this object) is to be looked for + + DESCRIPTION + The function looks for a multiple equality containing the field item + among those referenced by arg. + In the case such equality exists the function does the following. + If the found multiple equality contains a constant, then the field + reference is substituted for this constant, otherwise it sets a pointer + to the multiple equality in the field item. + + NOTES + This function is supposed to be called as a callback parameter in calls + of the transform method. + + RETURN VALUES + pointer to the replacing constant item, if the field item was substituted + pointer to the field item, otherwise. +*/ + Item *Item_field::equal_fields_propagator(byte *arg) { - COND_EQUAL *cond_equal= (COND_EQUAL *) arg; - item_equal= find_item_equal(cond_equal); + item_equal= find_item_equal((COND_EQUAL *) arg); Item *item= 0; if (item_equal) item= item_equal->get_const(); - if (item) - item->fixed= 0; - else + if (!item) item= this; return item; } + +/* + Set a pointer to the multiple equality the field reference belongs to (if any) + + SYNOPSIS + replace_equal_field_processor() + arg - a dummy parameter, is not used here + + DESCRIPTION + The function replaces a pointer to a field in the Item_field object + by a pointer to another field. + The replacement field is taken from the very beginning of + the item_equal list which the Item_field object refers to (belongs to) + If the Item_field object does not refer any Item_equal object, + nothing is done. + + NOTES + This function is supposed to be called as a callback parameter in calls + of the walk method. + + RETURN VALUES + 0 +*/ + bool Item_field::replace_equal_field_processor(byte *arg) { if (item_equal) { Item_field *subst= item_equal->get_first(); - if (subst && !field->eq(subst->field)) + if (!field->eq(subst->field)) { field= subst->field; return 0; diff --git a/sql/item.h b/sql/item.h index 1783fc6ef48..d4400f1058d 100644 --- a/sql/item.h +++ b/sql/item.h @@ -83,7 +83,7 @@ public: }; typedef bool (Item::*Item_processor)(byte *arg); -typedef Item* (Item::*Item_calculator) (byte *arg); +typedef Item* (Item::*Item_transformer) (byte *arg); class Item { Item(const Item &); /* Prevent use of these */ @@ -212,9 +212,9 @@ public: return (this->*processor)(arg); } - virtual Item* traverse(Item_calculator calculator, byte *arg) + virtual Item* transform(Item_transformer transformer, byte *arg) { - return (this->*calculator)(arg); + return (this->*transformer)(arg); } virtual bool remove_dependence_processor(byte * arg) { return 0; } @@ -949,13 +949,17 @@ public: (this->*processor)(args); } - Item *traverse(Item_calculator calculator, byte *args) + /* + This method like the walk method traverses the item tree, but + at the same time it can replace some nodes in the tree + */ + Item *transform(Item_transformer transformer, byte *args) { - Item *new_item= arg->traverse(calculator, args); + Item *new_item= arg->transform(transformer, args); if (!new_item) return 0; arg= new_item; - return (this->*calculator)(args); + return (this->*transformer)(args); } }; diff --git a/sql/item_cmpfunc.cc b/sql/item_cmpfunc.cc index f79e59b5e8f..e0bdae769ed 100644 --- a/sql/item_cmpfunc.cc +++ b/sql/item_cmpfunc.cc @@ -225,7 +225,7 @@ void Item_bool_func2::fix_length_and_dec() } // Make a special case of compare with fields to get nicer DATE comparisons - if (args[0]->type() == FIELD_ITEM && !args[0]->const_item()) + if (args[0]->type() == FIELD_ITEM /* && !args[0]->const_item() */ ) { Field *field=((Item_field*) args[0])->field; if (field->store_for_compare()) @@ -238,7 +238,7 @@ void Item_bool_func2::fix_length_and_dec() } } } - if (args[1]->type() == FIELD_ITEM && !args[1]->const_item()) + if (args[1]->type() == FIELD_ITEM /* && !args[1]->const_item() */) { Field *field=((Item_field*) args[1])->field; if (field->store_for_compare()) @@ -1739,21 +1739,44 @@ bool Item_cond::walk(Item_processor processor, byte *arg) return Item_func::walk(processor, arg); } -Item *Item_cond::traverse(Item_calculator calculator, byte *arg) + +/* + Transform an Item_cond object with a transformer callback function + + SYNOPSIS + transform() + transformer the transformer callback function to be applied to the nodes + of the tree of the object + arg parameter to be passed to the transformer + + DESCRIPTION + The function recursively applies the transform method with the + same transformer to each member item of the codition list. + If the call of the method for a member item returns a new item + the old item is substituted for a new one. + After this the transform method is applied to the root node + of the Item_cond object. + + RETURN VALUES + Item returned as the result of transformation of the root node +*/ + +Item *Item_cond::transform(Item_transformer transformer, byte *arg) { List_iterator<Item> li(list); Item *item; while ((item= li++)) { - Item *new_item= item->traverse(calculator, arg); + Item *new_item= item->transform(transformer, arg); if (!new_item) return 0; if (new_item != item) li.replace(new_item); } - return Item_func::traverse(calculator, arg); + return Item_func::transform(transformer, arg); } + void Item_cond::split_sum_func(Item **ref_pointer_array, List<Item> &fields) { List_iterator<Item> li(list); @@ -2591,6 +2614,32 @@ void Item_equal::add(Item_field *f) fields.push_back(f); } +uint Item_equal::members() +{ + uint count= 0; + List_iterator_fast<Item_field> li(fields); + Item_field *item; + while ((item= li++)) + count++; + return count; +} + + +/* + Check whether a field is referred in the multiple equality + + SYNOPSIS + contains() + field field whose occurence is to be checked + + DESCRIPTION + The function checks whether field is occured in the Item_equal object + + RETURN VALUES + 1 if nultiple equality contains a reference to field + 0 otherwise +*/ + bool Item_equal::contains(Field *field) { List_iterator_fast<Item_field> it(fields); @@ -2603,6 +2652,25 @@ bool Item_equal::contains(Field *field) return 0; } + +/* + Join members of another Item_equal object + + SYNOPSIS + merge() + item multiple equality whose members are to be joined + + DESCRIPTION + The function actually merges two multiple equalitis. + After this operation the Item_equal object additionally contains + the field items of another item of the type Item_equal. + If the optional constant items are not equal the cond_false flag is + set to 1. + + RETURN VALUES + none +*/ + void Item_equal::merge(Item_equal *item) { fields.concat(&item->fields); @@ -2619,26 +2687,46 @@ void Item_equal::merge(Item_equal *item) cond_false|= item->cond_false; } -void Item_equal::sort(void *table_join_idx) + +/* + Order field items in multiple equality according to a sorting criteria + + SYNOPSIS + sort() + cmp function to compare field item + arg context extra parameter for the cmp function + + DESCRIPTION + The function perform ordering of the field items in the Item_equal + object according to the criteria determined by the cmp callback parameter. + If cmp(item_field1,item_field2,arg)<0 than item_field1 must be + placed after item_fiel2. + + IMPLEMENTATION + The function sorts field items by the exchange sort algorithm. + The list of field items is looked through and whenever two neighboring + members follow in a wrong order they are swapped. This is performed + again and again until we get all members in a right order. + + RETURN VALUES + None +*/ + +void Item_equal::sort(Item_field_cmpfunc cmp, void *arg) { bool swap; - void **idx= (void **) table_join_idx; List_iterator<Item_field> it(fields); do { Item_field *item1= it++; Item_field **ref1= it.ref(); Item_field *item2; - Item_field **ref2; - if (!item1) - break; swap= FALSE; while ((item2= it++)) { - ref2= it.ref(); - if (idx[item1->field->table->tablenr] > - idx[item2->field->table->tablenr]) + Item_field **ref2= it.ref(); + if (cmp(item1, item2, arg) < 0) { Item_field *item= *ref1; *ref1= *ref2; @@ -2680,6 +2768,8 @@ void Item_equal::update_used_tables() List_iterator_fast<Item_field> li(fields); Item *item; not_null_tables_cache= used_tables_cache= 0; + if ((const_item_cache= cond_false)) + return; while ((item=li++)) { item->update_used_tables(); @@ -2697,7 +2787,7 @@ longlong Item_equal::val_int() if ((null_value= item->null_value)) return 0; eval_item->store_value(item); - while((item= it++)) + while ((item= it++)) { if ((null_value= item->null_value) || eval_item->cmp(item)) return 0; @@ -2723,19 +2813,19 @@ bool Item_equal::walk(Item_processor processor, byte *arg) return Item_func::walk(processor, arg); } -Item *Item_equal::traverse(Item_calculator calculator, byte *arg) +Item *Item_equal::transform(Item_transformer transformer, byte *arg) { List_iterator<Item_field> it(fields); Item *item; while ((item= it++)) { - Item *new_item= item->traverse(calculator, arg); + Item *new_item= item->transform(transformer, arg); if (!new_item) return 0; if (new_item != item) it.replace((Item_field *) new_item); } - return Item_func::traverse(calculator, arg); + return Item_func::transform(transformer, arg); } void Item_equal::print(String *str) @@ -2744,8 +2834,13 @@ void Item_equal::print(String *str) str->append('('); List_iterator_fast<Item_field> it(fields); Item *item; - if ((item= it++)) + if (const_item) + const_item->print(str); + else + { + item= it++; item->print(str); + } while ((item= it++)) { str->append(','); diff --git a/sql/item_cmpfunc.h b/sql/item_cmpfunc.h index 9d567bbc01b..d7cd0d93588 100644 --- a/sql/item_cmpfunc.h +++ b/sql/item_cmpfunc.h @@ -20,6 +20,9 @@ #ifdef __GNUC__ #pragma interface /* gcc class implementation */ #endif +#ifdef __GNUC__ +template class List_iterator_fast<Item_field>; +#endif extern Item_result item_cmp_type(Item_result a,Item_result b); class Item_bool_func2; @@ -27,6 +30,8 @@ class Arg_comparator; typedef int (Arg_comparator::*arg_cmp_func)(); +typedef int (*Item_field_cmpfunc)(Item_field *f1, Item_field *f2, void *arg); + class Arg_comparator: public Sql_alloc { Item **a, **b; @@ -890,6 +895,7 @@ public: :Item_bool_func(), list(nlist), abort_on_null(0) {} ~Item_cond() { list.delete_elements(); } bool add(Item *item) { return list.push_back(item); } + void add_at_head(List<Item> *nlist) { list.prepand(nlist); } bool fix_fields(THD *, struct st_table_list *, Item **ref); enum Type type() const { return COND_ITEM; } @@ -902,11 +908,75 @@ public: void top_level_item() { abort_on_null=1; } void copy_andor_arguments(THD *thd, Item_cond *item); bool walk(Item_processor processor, byte *arg); - Item *traverse(Item_calculator calculator, byte *arg); + Item *transform(Item_transformer transformer, byte *arg); void neg_arguments(); }; +/* + The class Item_equal is used to represent conjuctions of equality + predicates of the form field1 = field2, and field=const in where + conditions and on expressions. + + All equality predicates of the form field1=field2 contained in a + conjuction are substituted for a sequence of items of this class. + An item of this class Item_equal(f1,f2,...fk) respresents a + multiple equality f1=f2=...=fk. + + If a conjuction contains predicates f1=f2 and f2=f3, a new item of + this class is created Item_equal(f1,f2,f3) representing the multiple + equality f1=f2=f3 that substitutes the above equality predicates in + the conjuction. + A conjuction of the predicates f2=f1 and f3=f1 and f3=f2 will be + substituted for the item representing the same multiple equality + f1=f2=f3. + An item Item_equal(f1,f2) can appear instead of a conjuction of + f2=f1 and f1=f2, or instead of just the predicate f1=f2. + + An item of the class Item_equal inherites equalities from outer + conjunctive levels. + + Suppose we have a where condition of the following form: + WHERE f1=f2 AND f3=f4 AND f3=f5 AND ... AND (...OR (f1=f3 AND ...)). + In this case: + f1=f2 will be substituted for Item_equal(f1,f2); + f3=f4 and f3=f5 will be substituted for Item_equal(f3,f4,f5); + f1=f3 will be substituted for Item_equal(f1,f2,f3,f4,f5); + + An object of the class Item_equal can contain an optional constant + item c. Thenit represents a multiple equality of the form + c=f1=...=fk. + + Objects of the class Item_equal are used for the following: + + 1. An object Item_equal(t1.f1,...,tk.fk) allows us to consider any + pair of tables ti and tj as joined by an equi-condition. + Thus it provide us with additional access paths from table to table. + + 2. An object Item_equal(t1.f1,...,tk.fk) is applied to deduce new + SARGable predicates: + f1=...=fk AND P(fi) => f1=...=fk AND P(fi) AND P(fj). + It also can give us additional index scans and can allow us to + improve selectivity estimates. + + 3. An object Item_equal(t1.f1,...,tk.fk) is used to optimize the + selected execution plan for the query: if table ti is accessed + before the table tj then in any predicate P in the where condition + the occurence of tj.fj is substituted for ti.fi. This can allow + an evaluation of the predicate at an earlier step. + + When feature 1 is supported they say that join transitive closure + is employed. + When feature 2 is supported they say that search argument transitive + closure is employed. + Both features are usually supported by preprocessing original query and + adding additional predicates. + We do not just add predicates, we rather dynamically replace some + predicates that can not be used to access tables in the investigated + plan for those, obtained by substitution of some fields for equal fields, + that can be used. +*/ + class Item_equal: public Item_bool_func { List<Item_field> fields; /* list of equal field items */ @@ -924,7 +994,7 @@ public: inline Item* get_const() { return const_item; } void add(Item *c); void add(Item_field *f); - bool is_false() { return cond_false; } + uint members(); bool contains(Field *field); Item_field* get_first() { return fields.head(); } void merge(Item_equal *item); @@ -932,22 +1002,29 @@ public: longlong val_int(); const char *func_name() const { return "multiple equal"; } optimize_type select_optimize() const { return OPTIMIZE_EQUAL; } - void sort(void *table_join_idx); + void sort(Item_field_cmpfunc cmp, void *arg); friend class Item_equal_iterator; void fix_length_and_dec(); bool fix_fields(THD *thd, TABLE_LIST *tables, Item **ref); void update_used_tables(); bool walk(Item_processor processor, byte *arg); - Item *traverse(Item_calculator calculator, byte *arg); + Item *transform(Item_transformer transformer, byte *arg); void print(String *str); }; class COND_EQUAL { public: - COND_EQUAL *parent_level; - List<Item_equal> current_level; - COND_EQUAL() { parent_level= 0; } + uint max_members; /* max number of members the current level + list and all lower level lists */ + COND_EQUAL *upper_levels; /* multiple equalities of upper and levels */ + List<Item_equal> current_level; /* list of multiple equalities of + the current and level */ + COND_EQUAL() + { + max_members= 0; + upper_levels= 0; + } }; @@ -971,7 +1048,9 @@ public: class Item_cond_and :public Item_cond { public: - COND_EQUAL cond_equal; + COND_EQUAL cond_equal; /* contains list of Item_equal objects for + the current and level and reference + to multiple equalities of upper and levels */ Item_cond_and() :Item_cond() {} Item_cond_and(Item *i1,Item *i2) :Item_cond(i1,i2) {} Item_cond_and(THD *thd, Item_cond_and &item) :Item_cond(thd, item) {} diff --git a/sql/item_func.cc b/sql/item_func.cc index 10c22c2b386..14ce7f79f47 100644 --- a/sql/item_func.cc +++ b/sql/item_func.cc @@ -242,37 +242,42 @@ bool Item_func::walk (Item_processor processor, byte *argument) return (this->*processor)(argument); } -Item *Item_func::traverse(Item_calculator calculator, byte *argument) + +/* + Transform an Item_func object with a transformer callback function + + SYNOPSIS + transform() + transformer the transformer callback function to be applied to the nodes + of the tree of the object + argument parameter to be passed to the transformer + + DESCRIPTION + The function recursively applies the transform method with the + same transformer to each argument the function. + If the call of the method for a member item returns a new item + the old item is substituted for a new one. + After this the transform method is applied to the root node + of the Item_func object. + + RETURN VALUES + Item returned as the result of transformation of the root node +*/ + +Item *Item_func::transform(Item_transformer transformer, byte *argument) { if (arg_count) { Item **arg,**arg_end; for (arg= args, arg_end= args+arg_count; arg != arg_end; arg++) { - Item *new_item= (*arg)->traverse(calculator, argument); + Item *new_item= (*arg)->transform(transformer, argument); if (!new_item) return 0; *arg= new_item; } } - return (this->*calculator)(argument); -} - -Item *Item_func::equal_fields_propagator(byte *argument) -{ - if (arg_count) - { - Item **arg,**arg_end; - for (arg= args, arg_end= args+arg_count; arg != arg_end; arg++) - { - if (!(*arg)->fixed) - { - fix_fields(current_thd, 0, 0); - break; - } - } - } - return this; + return (this->*transformer)(argument); } diff --git a/sql/item_func.h b/sql/item_func.h index 5add4b8a739..1e274237cb8 100644 --- a/sql/item_func.h +++ b/sql/item_func.h @@ -148,8 +148,7 @@ public: bool agg_arg_collations_for_comparison(DTCollation &c, Item **items, uint nitems); bool walk(Item_processor processor, byte *arg); - Item *traverse(Item_calculator calculator, byte *arg); - Item *equal_fields_propagator(byte *arg); + Item *transform(Item_transformer transformer, byte *arg); }; diff --git a/sql/item_row.cc b/sql/item_row.cc index d7afe9ad5f0..7a457c9db7a 100644 --- a/sql/item_row.cc +++ b/sql/item_row.cc @@ -140,16 +140,16 @@ bool Item_row::walk(Item_processor processor, byte *arg) return (this->*processor)(arg); } -Item *Item_row::traverse(Item_calculator calculator, byte *arg) +Item *Item_row::transform(Item_transformer transformer, byte *arg) { for (uint i= 0; i < arg_count; i++) { - Item *new_item= items[i]->traverse(calculator, arg); + Item *new_item= items[i]->transform(transformer, arg); if (!new_item) return 0; items[i]= new_item; } - return (this->*calculator)(arg); + return (this->*transformer)(arg); } void Item_row::bring_value() diff --git a/sql/item_row.h b/sql/item_row.h index de6c18bf0d9..a550bce4b5a 100644 --- a/sql/item_row.h +++ b/sql/item_row.h @@ -71,7 +71,7 @@ public: void print(String *str); bool walk(Item_processor processor, byte *arg); - Item *traverse(Item_calculator calculator, byte *arg); + Item *transform(Item_transformer transformer, byte *arg); uint cols() { return arg_count; } Item* el(uint i) { return items[i]; } diff --git a/sql/item_strfunc.h b/sql/item_strfunc.h index 0bc02ca3dd5..2bc37de86d8 100644 --- a/sql/item_strfunc.h +++ b/sql/item_strfunc.h @@ -427,13 +427,13 @@ public: return item->walk(processor, arg) || Item_str_func::walk(processor, arg); } - Item *traverse(Item_calculator calculator, byte *arg) + Item *transform(Item_transformer transformer, byte *arg) { - Item *new_item= item->traverse(calculator, arg); + Item *new_item= item->transform(transformer, arg); if (!new_item) return 0; item= new_item; - return Item_str_func::traverse(calculator, arg); + return Item_str_func::transform(transformer, arg); } void print(String *str); }; diff --git a/sql/opt_range.cc b/sql/opt_range.cc index 80d9bf92b45..67603eeeccd 100644 --- a/sql/opt_range.cc +++ b/sql/opt_range.cc @@ -1494,6 +1494,21 @@ static int get_quick_select_params(SEL_TREE *tree, PARAM *param, } +/* + Build a SEL_TREE for a simple predicate + + SYNOPSIS + get_func_mm_tree() + param PARAM from SQL_SELECT::test_quick_select + cond_func item for the predicate + field field in the predicate + value constant in the predicate + cmp_type compare type for the field + + RETURN + Pointer to thre built tree +*/ + static SEL_TREE *get_func_mm_tree(PARAM *param, Item_func *cond_func, Field *field, Item *value, Item_result cmp_type) @@ -1501,21 +1516,18 @@ static SEL_TREE *get_func_mm_tree(PARAM *param, Item_func *cond_func, SEL_TREE *tree= 0; DBUG_ENTER("get_func_mm_tree"); - if (cond_func->functype() == Item_func::NE_FUNC) - { - + switch (cond_func->functype()) { + case Item_func::NE_FUNC: tree= get_mm_parts(param, field, Item_func::LT_FUNC, value, cmp_type); if (tree) { tree= tree_or(param, tree, get_mm_parts(param, field, - Item_func::GT_FUNC, - value, cmp_type)); + Item_func::GT_FUNC, + value, cmp_type)); } - } - else if (cond_func->functype() == Item_func::BETWEEN) - { - + break; + case Item_func::BETWEEN: tree= get_mm_parts(param, field, Item_func::GE_FUNC, cond_func->arguments()[1],cmp_type); if (tree) @@ -1525,30 +1537,42 @@ static SEL_TREE *get_func_mm_tree(PARAM *param, Item_func *cond_func, cond_func->arguments()[2], cmp_type)); } - } - else if (cond_func->functype() == Item_func::IN_FUNC) + break; + case Item_func::IN_FUNC: { Item_func_in *func=(Item_func_in*) cond_func; tree= get_mm_parts(param, field, Item_func::EQ_FUNC, func->arguments()[1], cmp_type); if (tree) { - for (uint i =2 ; i < func->argument_count() ; i++) + Item **arg, **end; + for (arg= func->arguments()+2, end= arg+func->argument_count()-2; + arg < end ; arg++) { tree= tree_or(param, tree, get_mm_parts(param, field, Item_func::EQ_FUNC, - func->arguments()[i], + *arg, cmp_type)); } } + break; } - else + default: { + /* + Here the function for the following predicates are processed: + <, <=, =, >=, >, LIKE, IS NULL, IS NOT NULL. + If the predicate is of the form (value op field) it is handled + as the equivalent predicate (field rev_op value), e.g. + 2 <= a is handled as a >= 2. + */ Item_func::Functype func_type= (value != cond_func->arguments()[0]) ? cond_func->functype() : ((Item_bool_func2*) cond_func)->rev_functype(); tree= get_mm_parts(param, field, func_type, value, cmp_type); } + } + DBUG_RETURN(tree); } @@ -1625,71 +1649,71 @@ static SEL_TREE *get_mm_tree(PARAM *param,COND *cond) if (cond_func->select_optimize() == Item_func::OPTIMIZE_NONE) DBUG_RETURN(0); // Can't be calculated - if (cond_func->functype() == Item_func::BETWEEN) - { - if (cond_func->arguments()[0]->type() == Item::FIELD_ITEM) - { - field_item= (Item_field*) (cond_func->arguments()[0]); - value= NULL; - } - else + switch (cond_func->functype()) { + case Item_func::BETWEEN: + if (cond_func->arguments()[0]->type() != Item::FIELD_ITEM) DBUG_RETURN(0); - } - else if (cond_func->functype() == Item_func::IN_FUNC) + field_item= (Item_field*) (cond_func->arguments()[0]); + value= NULL; + break; + case Item_func::IN_FUNC: { Item_func_in *func=(Item_func_in*) cond_func; - if (func->key_item()->type() == Item::FIELD_ITEM) - { - field_item= (Item_field*) (func->key_item()); - value= NULL; - } - else + if (func->key_item()->type() != Item::FIELD_ITEM) DBUG_RETURN(0); + field_item= (Item_field*) (func->key_item()); + value= NULL; + break; } - else if (cond_func->functype() == Item_func::MULT_EQUAL_FUNC) + case Item_func::MULT_EQUAL_FUNC: { Item_equal *item_equal= (Item_equal *) cond; - Item_equal_iterator it(*item_equal); if (!(value= item_equal->get_const())) - value= it++; - while (value) + DBUG_RETURN(0); + Item_equal_iterator it(*item_equal); + ref_tables= value->used_tables(); + while ((field_item= it++)) { - ref_tables= value->used_tables(); - Item_equal_iterator li(*item_equal); - while ((field_item= li++)) + Field *field= field_item->field; + Item_result cmp_type= field->cmp_type(); + if (!((ref_tables | field->table->map) & param_comp)) { - if (field_item != value) - { - Field *field= field_item->field; - Item_result cmp_type= field->cmp_type(); - if (!((ref_tables | field->table->map) & param_comp)) - { - tree= get_mm_parts(param, field, Item_func::EQ_FUNC, - value,cmp_type); - ftree= !ftree ? tree : tree_and(param, ftree, tree); - } - } + tree= get_mm_parts(param, field, Item_func::EQ_FUNC, + value,cmp_type); + ftree= !ftree ? tree : tree_and(param, ftree, tree); } - if (item_equal->get_const()) - break; - value= it++; } + DBUG_RETURN(ftree); } - else if (cond_func->arguments()[0]->type() == Item::FIELD_ITEM) - { - field_item= (Item_field*) (cond_func->arguments()[0]); - value= cond_func->arg_count > 1 ? cond_func->arguments()[1] : 0; - } - else if (cond_func->have_rev_func() && + default: + if (cond_func->arguments()[0]->type() == Item::FIELD_ITEM) + { + field_item= (Item_field*) (cond_func->arguments()[0]); + value= cond_func->arg_count > 1 ? cond_func->arguments()[1] : 0; + } + else if (cond_func->have_rev_func() && cond_func->arguments()[1]->type() == Item::FIELD_ITEM) - { - field_item= (Item_field*) (cond_func->arguments()[1]); - value= cond_func->arguments()[0]; + { + field_item= (Item_field*) (cond_func->arguments()[1]); + value= cond_func->arguments()[0]; + } + else + DBUG_RETURN(0); } - else - DBUG_RETURN(0); + /* + If the where condition contains a predicate (ti.field op const), + then not only SELL_TREE for this predicate is built, but + the trees for the results of substitution of ti.field for + each tj.field belonging to the same multiple equality as ti.field + are built as well. + E.g. for WHERE t1.a=t2.a AND t2.a > 10 + a SEL_TREE for t2.a > 10 will be built for quick select from t2 + and + a SEL_TREE for t1.a > 10 will be built for quick select from t1. + */ + for (uint i= 0; i < cond_func->arg_count; i++) { Item *arg= cond_func->arguments()[i]; diff --git a/sql/sql_list.h b/sql/sql_list.h index bac4a2a8655..5318237b786 100644 --- a/sql/sql_list.h +++ b/sql/sql_list.h @@ -161,6 +161,15 @@ public: *prev= *last; last= prev; } + inline void prepand(base_list *list) + { + if (!list->is_empty()) + { + *list->last= first; + first= list->first; + elements+= list->elements; + } + } inline list_node* last_node() { return *last; } inline list_node* first_node() { return first;} inline void *head() { return first->info; } @@ -273,6 +282,7 @@ public: inline T* pop() {return (T*) base_list::pop(); } inline void concat(List<T> *list) { base_list::concat(list); } inline void disjoin(List<T> *list) { base_list::disjoin(list); } + inline void prepand(List<T> *list) { base_list::prepand(list); } void delete_elements(void) { list_node *element,*next; diff --git a/sql/sql_select.cc b/sql/sql_select.cc index 4736cca1d41..ba911f47490 100644 --- a/sql/sql_select.cc +++ b/sql/sql_select.cc @@ -45,6 +45,7 @@ static bool make_join_statistics(JOIN *join,TABLE_LIST *tables,COND *conds, static bool update_ref_and_keys(THD *thd, DYNAMIC_ARRAY *keyuse, JOIN_TAB *join_tab, uint tables, COND *conds, + COND_EQUAL *cond_equal, table_map table_map, SELECT_LEX *select_lex); static int sort_keyuse(KEYUSE *a,KEYUSE *b); static void set_position(JOIN *join,uint index,JOIN_TAB *table,KEYUSE *key); @@ -73,7 +74,6 @@ static int return_zero_rows(JOIN *join, select_result *res,TABLE_LIST *tables, uint select_options, const char *info, Item *having, Procedure *proc, SELECT_LEX_UNIT *unit); -static Item *flatten_condition(COND *cond); static COND *build_all_equal_items(COND *cond, COND_EQUAL *inherited); static COND* substitute_for_best_equal_field(COND *cond, @@ -530,19 +530,15 @@ JOIN::optimize() } #endif - /* eliminate NOT operators */ + /* Eliminate NOT operators */ conds= eliminate_not_funcs(conds); DBUG_EXECUTE("where", print_where(conds, "after negation elimination");); - - /* Eliminate nested AND/OR in conditions */ - if (conds) - conds= flatten_condition(conds); { TABLE_LIST *tables; for (tables= tables_list; tables; tables= tables->next) { if (tables->on_expr) - tables->on_expr= flatten_condition(tables->on_expr); + tables->on_expr= eliminate_not_funcs(tables->on_expr); } } @@ -1868,7 +1864,8 @@ make_join_statistics(JOIN *join,TABLE_LIST *tables,COND *conds, if (conds || outer_join) if (update_ref_and_keys(join->thd, keyuse_array, stat, join->tables, - conds, ~outer_join, join->select_lex)) + conds, join->cond_equal, + ~outer_join, join->select_lex)) DBUG_RETURN(1); /* Read tables with 0 or 1 rows (system tables) */ @@ -2298,6 +2295,27 @@ add_key_field(KEY_FIELD **key_fields,uint and_level, } +/* + Add possible keys to array of possible keys originated from a simple predicate + + SYNPOSIS + add_key_equal_field() + key_fields Pointer to add key, if usable + and_level And level, to be stored in KEY_FIELD + field Field used in comparision + eq_func True if we used =, <=> or IS NULL + value Value used for comparison with field + Is NULL for BETWEEN and IN + usable_tables Tables which can be used for key optimization + + NOTES + If field items f1 and f2 belong to the same multiple equality and + a key is added for f1, the the same key is added for f2. + + RETURN + *key_fields is incremented if we stored a key in the array +*/ + static void add_key_equal_fields(KEY_FIELD **key_fields, uint and_level, Item_field *field_item, @@ -2601,15 +2619,19 @@ sort_keyuse(KEYUSE *a,KEYUSE *b) static bool update_ref_and_keys(THD *thd, DYNAMIC_ARRAY *keyuse,JOIN_TAB *join_tab, - uint tables, COND *cond, table_map normal_tables, - SELECT_LEX *select_lex) + uint tables, COND *cond, COND_EQUAL *cond_equal, + table_map normal_tables, SELECT_LEX *select_lex) { uint and_level,i,found_eq_constant; KEY_FIELD *key_fields, *end, *field; + uint m= 1; + + if (cond_equal && cond_equal->max_members) + m= cond_equal->max_members; if (!(key_fields=(KEY_FIELD*) thd->alloc(sizeof(key_fields[0])* - (thd->lex->current_select->cond_count+1)*2))) + (thd->lex->current_select->cond_count+1)*2*m))) return TRUE; /* purecov: inspected */ and_level= 0; field= end= key_fields; @@ -2838,8 +2860,6 @@ find_best(JOIN *join,table_map rest_tables,uint idx,double record_count, do { uint keypart=keyuse->keypart; - uint found_part_ref_or_null= KEY_OPTIMIZE_REF_OR_NULL; - bool usable= 0; table_map best_part_found_ref= 0; double best_prev_record_reads= DBL_MAX; do @@ -2848,8 +2868,9 @@ find_best(JOIN *join,table_map rest_tables,uint idx,double record_count, !(found_ref_or_null & keyuse->optimize)) { found_part|=keyuse->keypart_map; - double tmp= prev_record_reads(join, - (table_map) (found_ref | keyuse->used_tables)); + double tmp= prev_record_reads(join, + (found_ref | + keyuse->used_tables)); if (tmp < best_prev_record_reads) { best_part_found_ref= keyuse->used_tables; @@ -2857,15 +2878,17 @@ find_best(JOIN *join,table_map rest_tables,uint idx,double record_count, } if (rec > keyuse->ref_table_rows) rec= keyuse->ref_table_rows; - found_part_ref_or_null&= keyuse->optimize; - usable= 1; + /* + If there is one 'key_column IS NULL' expression, we can + use this ref_or_null optimsation of this field + */ + found_ref_or_null|= (keyuse->optimize & + KEY_OPTIMIZE_REF_OR_NULL); } keyuse++; - found_ref|= best_part_found_ref; } while (keyuse->table == table && keyuse->key == key && keyuse->keypart == keypart); - if (usable) - found_ref_or_null|= found_part_ref_or_null; + found_ref|= best_part_found_ref; } while (keyuse->table == table && keyuse->key == key); /* @@ -4274,55 +4297,6 @@ template class List<Item_func_match>; template class List_iterator<Item_func_match>; #endif -/* - Eliminate nesting in AND/OR subexpressions od a condition - - SYNOPSIS - flatten_condition() - cond condition where to eliminate nesting - - DESCRIPTION - The function traverse the condition and recursively eliminates - nesting for AND/OR subexpressions: - ... AND (p AND ... r) AND ... => ... AND p AND ... r AND ... - ... OR (p OR ... r) OR ... => ... OR p OR ... r OR ... - - NOTES - Nesting in AND/OR subexpresions inside of NOT/XOR formulas is not - eliminated. - - RETURN - The transformed condition -*/ -static Item *flatten_condition(COND *cond) -{ - if (cond->type() == Item::COND_ITEM) - { - Item_func::Functype functype= ((Item_cond*) cond)->functype(); - if (functype == Item_func::COND_AND_FUNC || - functype == Item_func::COND_OR_FUNC) - { - - List<Item> *args= ((Item_cond*) cond)->argument_list(); - List_iterator<Item> li(*args); - Item *item; - List<Item> list; - while ((item= li++)) - { - item= flatten_condition(item); - if (item->type() == Item::COND_ITEM && - ((Item_func*) item)->functype() == functype) - { - list.concat(((Item_cond*) item)->argument_list()); - li.remove(); - } - } - args->concat(&list); - } - } - return cond; -} - /* Find the multiple equality predicate containing a field @@ -4359,14 +4333,14 @@ Item_equal *find_item_equal(COND_EQUAL *cond_equal, Field *field, goto finish; } in_upper_level= TRUE; - cond_equal= cond_equal->parent_level; + cond_equal= cond_equal->upper_levels; } in_upper_level= FALSE; finish: - if (inherited_fl) - *inherited_fl= in_upper_level; + *inherited_fl= in_upper_level; return item; } + /* Check whether an item is a simple equality predicate and if so @@ -4379,22 +4353,40 @@ finish: DESCRIPTION This function first checks whether an item is a simple equality i.e. - the one that equates a field with another field or a constant. + the one that equates a field with another field or a constant + (item=constant_item or item=field_item). If this is the case the function looks a for a multiple equality - in the lists referenced directly or indirectly by cond_equal. If it - doesn't find any it builds a multiple equality that covers - the predicate, i.e. the predicate can be inferred from it. The built - multiple equality could be obtained in such a way: create a binary - multiple equality equivalent to the predicate, than merge it, if - possible, with one of old multiple equalities. This guarantees that - the set of multiple equalities covering equality predicates will + in the lists referenced directly or indirectly by cond_equal inferring + the given simple equality. If it doesn't find any, it builds a multiple + equality that covers the predicate, i.e. the predicate can be inferred + from it. + The built multiple equality could be obtained in such a way: + create a binary multiple equality equivalent to the predicate, then + merge it, if possible, with one of old multiple equalities. + This guarantees that the set of multiple equalities covering equality + predicates will be minimal. + EXAMPLE + For the where condition + WHERE a=b AND b=c AND + (b=2 OR f=e) + the check_equality will be called for the following equality + predicates a=b, b=c, b=2 and f=e. + For a=b it will be called with *cond_equal=(0,[]) and will transform + *cond_equal into (0,[Item_equal(a,b)]). + For b=c it will be called with *cond_equal=(0,[Item_equal(a,b)]) + and will transform *cond_equal into CE=(0,[Item_equal(a,b,c)]). + For b=2 it will be called with *cond_equal=(ptr(CE),[]) + and will transform *cond_equal into (ptr(CE,[Item_equal(2,a,b,c)]). + For f=e it will be called with *cond_equal=(ptr(CE), []) + and will transform *cond_equal into (ptr(CE,[Item_equal(f,e)]). + NOTES Now only fields that have the same type defintions (verified by the Field::eq_def method) are placed to the same multiple equalities. Because of this some equality predicates are not eliminated and - can be used in constant propagation procedure. + can be used in the constant propagation procedure. We could weeken the equlity test as soon as at least one of the equal fields is to be equal to a constant. It would require a more complicated implementation: we would have to store, in @@ -4408,7 +4400,7 @@ finish: build a new multiple equality for the equality predicate. If it processes the equality of the form field1=field2, it looks for multiple equalities me1 containig field1 and me2 containing - field2. If only one of them is found the fuction expand it by + field2. If only one of them is found the fuction expands it with the lacking field. If multiple equalities for both fields are found they are merged. If both searches fail a new multiple equality containing just field1 and field2 is added to the existing @@ -4446,7 +4438,7 @@ static bool check_equality(Item *item, COND_EQUAL *cond_equal) if (!left_field->eq_def(right_field)) return FALSE; - if (left_field->eq(right_field)) + if (left_field->eq(right_field)) /* f = f */ return TRUE; /* Search for multiple equalities containing field1 and/or field2 */ @@ -4460,7 +4452,8 @@ static bool check_equality(Item *item, COND_EQUAL *cond_equal) { /* The equality predicate is inference of one of the existing - multiple equalities + multiple equalities, i.e the condition is already covered + by upper level equalities */ return TRUE; } @@ -4468,17 +4461,20 @@ static bool check_equality(Item *item, COND_EQUAL *cond_equal) /* Copy the found multiple equalities at the current level if needed */ if (left_copyfl) { + /* left_item_equal of an upper level contains left_item */ left_item_equal= new Item_equal(left_item_equal); cond_equal->current_level.push_back(left_item_equal); } if (right_copyfl) { + /* right_item_equal of an upper level contains right_item */ right_item_equal= new Item_equal(right_item_equal); cond_equal->current_level.push_back(right_item_equal); } if (left_item_equal) { + /* left item was found in the current or one of the upper levels */ if (! right_item_equal) left_item_equal->add((Item_field *) right_item); else @@ -4493,11 +4489,12 @@ static bool check_equality(Item *item, COND_EQUAL *cond_equal) } else { + /* left item was not found neither the current nor in upper levels */ if (right_item_equal) right_item_equal->add((Item_field *) left_item); else { - /* Multiple equalities for neither of the fields has been found */ + /* None of the fields was found in multiple equalities */ Item_equal *item= new Item_equal((Item_field *) left_item, (Item_field *) right_item); cond_equal->current_level.push_back(item); @@ -4505,7 +4502,7 @@ static bool check_equality(Item *item, COND_EQUAL *cond_equal) } return TRUE; } - else + { /* The predicate of the form field=const/const=field is processed */ Item *const_item= 0; @@ -4568,10 +4565,17 @@ static bool check_equality(Item *item, COND_EQUAL *cond_equal) taking into account inherited equalities from upper levels. If an equality predicate is used not in a conjunction it's just replaced by a multiple equality predicate. - The functuion also traverse the cond tree and and for each field reference - sets a ponter to the multiple equality item containing the field, if there + For each 'and' level the function set a pointer to the inherited + multiple equalities in the cond_equal field of the associated + object of the type Item_cond_and. + The function also traverses the cond tree and and for each field reference + sets a pointer to the multiple equality item containing the field, if there is any. If this multiple equality equates fields to a constant the - function replace the field reference by the constant. + function replace the field reference by the constant. + The function also determines the maximum number of members in + equality lists of each Item_cond_and object assigning it to + cond_equal->max_members of this object and updating accordingly + the upper levels COND_EQUAL structures. NOTES Multiple equality predicate =(f1,..fn) is equivalent to the conjuction of @@ -4579,14 +4583,14 @@ static bool check_equality(Item *item, COND_EQUAL *cond_equal) equality predicates that is equivalent to the conjunction. Thus, =(a1,a2,a3) can substitute for ((a1=a3) AND (a2=a3) AND (a2=a1)) as it is equivalent to ((a1=a2) AND (a2=a3)). - The function always makes a subsitution of all equality predicates occured + The function always makes a substitution of all equality predicates occured in a conjuction for a minimal set of multiple equality predicates. This set can be considered as a canonical representation of the sub-conjunction of the equality predicates. E.g. (t1.a=t2.b AND t2.b>5 AND t1.a=t3.c) is replaced by (=(t1.a,t2.b,t3.c) AND t2.b>5), not by (=(t1.a,t2.b) AND =(t1.a,t3.c) AND t2.b>5); - while (t1.a=t2.b AND t2.b>5 AND t3.c,t4.d) is replaced by + while (t1.a=t2.b AND t2.b>5 AND t3.c=t4.d) is replaced by (=(t1.a,t2.b) AND =(t3.c=t4.d) AND t2.b>5), but if additionally =(t4.d,t2.b) is inherited, it will be replaced by (=(t1.a,t2.b,t3.c,t4.d) AND t2.b>5) @@ -4600,6 +4604,13 @@ static bool check_equality(Item *item, COND_EQUAL *cond_equal) multiple equalities is saved in the and condition object (Item_cond_and). This chain allows us for any field reference occurence easyly to find a multiple equality that must be held for this occurence. + For each AND level we do the following: + - scan it for all equality predicate (=) items + - join them into disjoint Item_equal() groups + - process the included OR conditions recursively to do the same for + lower AND levels. + We need to do things in this order as lower AND levels need to know about + all possible Item_equal objects in upper levels. RETURN pointer to the transformed condition @@ -4608,8 +4619,10 @@ static bool check_equality(Item *item, COND_EQUAL *cond_equal) static COND *build_all_equal_items(COND *cond, COND_EQUAL *inherited) { + Item_equal *item_equal; + uint members; COND_EQUAL cond_equal; - cond_equal.parent_level= inherited; + cond_equal.upper_levels= inherited; if (cond->type() == Item::COND_ITEM) { @@ -4625,7 +4638,7 @@ static COND *build_all_equal_items(COND *cond, /* Retrieve all conjucts of this level detecting the equality that are subject to substitution by multiple equality items and - removing each such predicate from the conjunction after after having + removing each such predicate from the conjunction after having found/created a multiple equality whose inference the predicate is. */ while ((item= li++)) @@ -4635,10 +4648,25 @@ static COND *build_all_equal_items(COND *cond, } List_iterator_fast<Item_equal> it(cond_equal.current_level); - while ((item= it++)) + while ((item_equal= it++)) + { + item_equal->fix_length_and_dec(); + item_equal->update_used_tables(); + members= item_equal->members(); + if (cond_equal.max_members < members) + cond_equal.max_members= members; + } + members= cond_equal.max_members; + if (inherited && inherited->max_members < members) { - item->fix_fields(current_thd, 0, 0); - } + do + { + inherited->max_members= members; + inherited= inherited->upper_levels; + } + while (inherited); + } + ((Item_cond_and*)cond)->cond_equal= cond_equal; inherited= &(((Item_cond_and*)cond)->cond_equal); } @@ -4646,14 +4674,14 @@ static COND *build_all_equal_items(COND *cond, Make replacement of equality predicates for lower levels of the condition expression. */ - List_iterator<Item> it(*args); - while((item= it++)) + li.rewind(); + while((item= li++)) { Item *new_item; if ((new_item = build_all_equal_items(item, inherited))!= item) { /* This replacement happens only for standalone equalities */ - it.replace(new_item); + li.replace(new_item); } } if (and_level) @@ -4661,24 +4689,78 @@ static COND *build_all_equal_items(COND *cond, } else if (cond->type() == Item::FUNC_ITEM) { - /* Standalone equalities are handled here */ - Item_equal *item_equal; + /* + If an equality predicate forms the whole and level, + we call it standalone equality and it's processed here. + E.g. in the following where condition + WHERE a=5 AND (b=5 or a=c) + (b=5) and (a=c) are standalone equalities. + In general we can't leave alone standalone eqalities: + for WHERE a=b AND c=d AND (b=c OR d=5) + b=c is replaced by =(a,b,c,d). + */ if (check_equality(cond, &cond_equal) && (item_equal= cond_equal.current_level.pop())) { - item_equal->fix_fields(current_thd, 0, 0); + item_equal->fix_length_and_dec(); + item_equal->update_used_tables(); return item_equal; } - else - { - cond= cond->traverse(&Item::equal_fields_propagator, - (byte *) inherited); - cond->update_used_tables(); - } + /* + For each field reference in cond, not from equalitym predicates, + set a pointer to the multiple equality if belongs to (if there is any) + */ + cond= cond->transform(&Item::equal_fields_propagator, + (byte *) inherited); + cond->update_used_tables(); } return cond; } +/* + Compare field items by table order in the execution plan + + SYNOPSIS + compare_fields_by_table_order() + field1 first field item to compare + field2 second field item to compare + table_join_idx index to tables determining table order + + DESCRIPTION + field1 considered as better than field2 if the table containing + field1 is accessed earlier than the table containing field2. + The function finds out what of two fields is better according + this criteria. + + RETURN + 1, if field1 is better than field2 + -1, if field2 is better than field1 + 0, otherwise +*/ + +static int compare_fields_by_table_order(Item_field *field1, + Item_field *field2, + void *table_join_idx) +{ + int cmp= 0; + bool outer_ref= 0; + if (field2->used_tables() & OUTER_REF_TABLE_BIT) + { + outer_ref= 1; + cmp= -1; + } + if (field2->used_tables() & OUTER_REF_TABLE_BIT) + { + outer_ref= 1; + cmp++; + } + if (outer_ref) + return cmp; + JOIN_TAB **idx= (JOIN_TAB **) table_join_idx; + cmp= idx[field2->field->table->tablenr]-idx[field1->field->table->tablenr]; + return cmp < 0 ? -1 : (cmp ? 1 : 0); +} + /* Generate minimal set of simple equalities equivalent to a multiple equality @@ -4686,7 +4768,7 @@ static COND *build_all_equal_items(COND *cond, SYNOPSIS eliminate_item_equal() cond condition to add the generated equality to - cond_equal structure to access multiple equality of upper levels + upper_levels structure to access multiple equality of upper levels item_equal multiple equality to generate simple equality from DESCRIPTION @@ -4700,20 +4782,37 @@ static COND *build_all_equal_items(COND *cond, NOTES Before generating an equality function checks that it has not been generated for multiple equalies of the upper levels. + E.g. for the following where condition + WHERE a=5 AND ((a=b AND b=c) OR c>4) + the upper level AND condition will contain =(5,a), + while the lower level AND condition will contain =(5,a,b,c). + When splitting =(5,a,b,c) into a separate equality predicates + we should omit 5=a, as we have it already in the upper level. + The following where condition gives us a more complicated case: + WHERE t1.a=t2.b AND t3.c=t4.d AND (t2.b=t3.c OR t4.e>5 ...) AND ... + Given the tables are accessed in the order t1->t2->t3->t4 for + the selected query execution plan the lower level multiple + equality =(t1.a,t2.b,t3.c,t4.d) formally should be converted to + t1.a=t2.b AND t1.a=t3.c AND t1.a=t4.d. But t1.a=t2.a will be + generated for the upper level. Also t3.c=t4.d will be generated there. + So only t1.a=t3.c should be left in the lower level. If cond is equal to 0, then not more then one equality is generated and a pointer to it is returned as the result of the function. RETURN The condition with generated simple equalities or - a pointer to the simple generated equality. + a pointer to the simple generated equality, if success. + 0, otherwise. */ -static Item *eliminate_item_equal(COND *cond, COND_EQUAL *cond_equal, +static Item *eliminate_item_equal(COND *cond, COND_EQUAL *upper_levels, Item_equal *item_equal) { + List<Item> eq_list; + Item_func_eq *eq_item= 0; Item *item_const= item_equal->get_const(); Item_equal_iterator it(*item_equal); - Item *head; + Item *head; if (item_const) head= item_const; else @@ -4722,10 +4821,9 @@ static Item *eliminate_item_equal(COND *cond, COND_EQUAL *cond_equal, it++; } Item_field *item_field; - Item *new_item= 0; while ((item_field= it++)) { - Item_equal *upper= item_field->find_item_equal(cond_equal); + Item_equal *upper= item_field->find_item_equal(upper_levels); Item_field *item= item_field; if (upper) { @@ -4736,27 +4834,31 @@ static Item *eliminate_item_equal(COND *cond, COND_EQUAL *cond_equal, Item_equal_iterator li(*item_equal); while ((item= li++) != item_field) { - if (item->find_item_equal(cond_equal) == upper) + if (item->find_item_equal(upper_levels) == upper) break; } } } if (item == item_field) { - if (!cond && new_item) - { - cond= new Item_cond_and(); - ((Item_cond *) cond)->add(new_item); - } - item_field->item_equal= item_equal; - new_item= new Item_func_eq(item_field, head); - ((Item_func_eq *) new_item)->fix_length_and_dec(); - if (cond) - ((Item_cond *) cond)->add(new_item); - } + if (eq_item) + eq_list.push_back(eq_item); + eq_item= new Item_func_eq(item_field, head); + if (!eq_item) + return 0; + eq_item->set_cmp_func(); + } } + + if (!cond && !eq_list.head()) + return eq_item; + + eq_list.push_back(eq_item); if (!cond) - cond= (COND *) new_item; + cond= new Item_cond_and(eq_list); + else + ((Item_cond *) cond)->add_at_head(&eq_list); + return cond; } @@ -4811,9 +4913,9 @@ static COND* substitute_for_best_equal_field(COND *cond, cond_list->disjoin((List<Item> *) &cond_equal->current_level); List_iterator_fast<Item_equal> it(cond_equal->current_level); - while((item_equal= it++)) + while ((item_equal= it++)) { - item_equal->sort(table_join_idx); + item_equal->sort(&compare_fields_by_table_order, table_join_idx); } } @@ -4830,9 +4932,9 @@ static COND* substitute_for_best_equal_field(COND *cond, if (and_level) { List_iterator_fast<Item_equal> it(cond_equal->current_level); - while((item_equal= it++)) + while ((item_equal= it++)) { - eliminate_item_equal(cond, cond_equal->parent_level, item_equal); + eliminate_item_equal(cond, cond_equal->upper_levels, item_equal); } } } @@ -4840,7 +4942,7 @@ static COND* substitute_for_best_equal_field(COND *cond, ((Item_cond*) cond)->functype() == Item_func::MULT_EQUAL_FUNC) { item_equal= (Item_equal *) cond; - item_equal->sort(table_join_idx); + item_equal->sort(&compare_fields_by_table_order, table_join_idx); if (cond_equal && cond_equal->current_level.head() == item_equal) cond_equal= 0; return eliminate_item_equal(0, cond_equal, item_equal); @@ -5050,7 +5152,23 @@ COND *eliminate_not_funcs(COND *cond) { Item *new_item= eliminate_not_funcs(item); if (item != new_item) - VOID(li.replace(new_item)); /* replace item with a new condition */ + { + /* + Replace item with a new condition. + Remove unnecessary and/or level + that might appear after the replacement. + */ + if (new_item->type() == Item::COND_ITEM && + ((Item_cond*) new_item)->functype() == + ((Item_cond*) cond)->functype()) + { + List<Item> *list= ((Item_cond*) new_item)->argument_list(); + li.replace(*list); + list->empty(); + } + else + li.replace(new_item); + } } } else if (cond->type() == Item::FUNC_ITEM && /* 'NOT' operation? */ @@ -5228,22 +5346,6 @@ remove_eq_conds(COND *cond,Item::cond_result *cond_value) return (COND*) 0; } } - else if (cond->type() == Item::FUNC_ITEM && - ((Item_func*) cond)->functype() == Item_func::MULT_EQUAL_FUNC) - { - /* - The is_false method for an multiple equality item returns 1 - when the conjunction with this item originally contained an - equality that was inconsistent with the multiple equality - predicate or has been inherited from other multiple equality - for which is_false returns 1. - */ - if (((Item_equal *) cond)->is_false()) - { - *cond_value= Item::COND_FALSE; - return (COND*) 0; - } - } else if (cond->const_item()) { *cond_value= eval_const_cond(cond) ? Item::COND_TRUE : Item::COND_FALSE; @@ -8357,6 +8459,7 @@ join_init_cache(THD *thd,JOIN_TAB *tables,uint table_count) } if (!(cache->field=(CACHE_FIELD*) sql_alloc(sizeof(CACHE_FIELD)*(cache->fields+table_count*2)+(blobs+1)* + sizeof(CACHE_FIELD*)))) { my_free((gptr) cache->buff,MYF(0)); /* purecov: inspected */ |