summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--.bzrignore2
-rw-r--r--mysql-test/r/func_group.result2
-rw-r--r--mysql-test/r/func_test.result2
-rw-r--r--mysql-test/r/index_merge.result4
-rw-r--r--mysql-test/r/odbc.result2
-rw-r--r--mysql-test/r/range.result24
-rw-r--r--mysql-test/r/select.result2
-rw-r--r--mysql-test/t/range.test4
-rw-r--r--sql/item.cc27
-rw-r--r--sql/item.h29
-rw-r--r--sql/item_cmpfunc.cc326
-rw-r--r--sql/item_cmpfunc.h144
-rw-r--r--sql/item_func.cc39
-rw-r--r--sql/item_func.h7
-rw-r--r--sql/item_row.cc12
-rw-r--r--sql/item_row.h1
-rw-r--r--sql/item_strfunc.h8
-rw-r--r--sql/opt_range.cc207
-rw-r--r--sql/opt_sum.cc15
-rw-r--r--sql/sql_list.h45
-rw-r--r--sql/sql_select.cc892
-rw-r--r--sql/sql_select.h2
22 files changed, 1658 insertions, 138 deletions
diff --git a/.bzrignore b/.bzrignore
index 1feab85d33d..c55cf547450 100644
--- a/.bzrignore
+++ b/.bzrignore
@@ -508,6 +508,7 @@ mysql-test/install_test_db
mysql-test/mysql-test-run
mysql-test/ndb/ndbcluster
mysql-test/r/*.reject
+mysql-test/r/index_merge_load.result
mysql-test/r/rpl000001.eval
mysql-test/r/rpl000002.eval
mysql-test/r/rpl000014.eval
@@ -518,6 +519,7 @@ mysql-test/r/slave-running.eval
mysql-test/r/slave-stopped.eval
mysql-test/share/mysql
mysql-test/std_data/*.pem
+mysql-test/t/index_merge.load
mysql-test/var/*
mysql.kdevprj
mysql.proj
diff --git a/mysql-test/r/func_group.result b/mysql-test/r/func_group.result
index 9af8fa8c8cc..acc3205a63a 100644
--- a/mysql-test/r/func_group.result
+++ b/mysql-test/r/func_group.result
@@ -476,7 +476,7 @@ CHI Los Angeles
explain
select max(a3) from t1 where a2 is null and a2 = 2;
id select_type table type possible_keys key key_len ref rows Extra
-1 SIMPLE NULL NULL NULL NULL NULL NULL NULL Impossible WHERE noticed after reading const tables
+1 SIMPLE NULL NULL NULL NULL NULL NULL NULL Impossible WHERE
select max(a3) from t1 where a2 is null and a2 = 2;
max(a3)
NULL
diff --git a/mysql-test/r/func_test.result b/mysql-test/r/func_test.result
index 6f8bc702a80..a3a4f892975 100644
--- a/mysql-test/r/func_test.result
+++ b/mysql-test/r/func_test.result
@@ -77,7 +77,7 @@ select * from t1 where 1 xor 1;
a
explain extended select * from t1 where 1 xor 1;
id select_type table type possible_keys key key_len ref rows Extra
-1 SIMPLE NULL NULL NULL NULL NULL NULL NULL Impossible WHERE noticed after reading const tables
+1 SIMPLE NULL NULL NULL NULL NULL NULL NULL Impossible WHERE
Warnings:
Note 1003 select `test`.`t1`.`a` AS `a` from `test`.`t1` where (1 xor 1)
select - a from t1;
diff --git a/mysql-test/r/index_merge.result b/mysql-test/r/index_merge.result
index cb4b285430c..4055256f5ea 100644
--- a/mysql-test/r/index_merge.result
+++ b/mysql-test/r/index_merge.result
@@ -76,13 +76,13 @@ id select_type table type possible_keys key key_len ref rows Extra
1 SIMPLE t0 ALL i1,i2 NULL NULL NULL 1024 Using where
explain select * from t0 where key2 = 45 or key1 is null;
id select_type table type possible_keys key key_len ref rows Extra
-1 SIMPLE t0 range i1,i2 i2 4 NULL 1 Using where
+1 SIMPLE t0 ref i2 i2 4 const 1
explain select * from t0 where key2=10 or key3=3 or key4 <=> null;
id select_type table type possible_keys key key_len ref rows Extra
1 SIMPLE t0 index_merge i2,i3,i4 i2,i3 4,4 NULL 2 Using union(i2,i3); Using where
explain select * from t0 where key2=10 or key3=3 or key4 is null;
id select_type table type possible_keys key key_len ref rows Extra
-1 SIMPLE t0 index_merge i2,i3,i4 i2,i3 4,4 NULL 2 Using union(i2,i3); Using where
+1 SIMPLE t0 index_merge i2,i3 i2,i3 4,4 NULL 2 Using where
explain select key1 from t0 where (key1 <=> null) or (key2 < 5) or
(key3=10) or (key4 <=> null);
id select_type table type possible_keys key key_len ref rows Extra
diff --git a/mysql-test/r/odbc.result b/mysql-test/r/odbc.result
index c0b2ada0053..2d9d39393b1 100644
--- a/mysql-test/r/odbc.result
+++ b/mysql-test/r/odbc.result
@@ -12,5 +12,5 @@ select * from t1 where a is null;
a b
explain select * from t1 where b is null;
id select_type table type possible_keys key key_len ref rows Extra
-1 SIMPLE NULL NULL NULL NULL NULL NULL NULL Impossible WHERE noticed after reading const tables
+1 SIMPLE NULL NULL NULL NULL NULL NULL NULL Impossible WHERE
drop table t1;
diff --git a/mysql-test/r/range.result b/mysql-test/r/range.result
index 31c65f64256..add6d8f320d 100644
--- a/mysql-test/r/range.result
+++ b/mysql-test/r/range.result
@@ -220,24 +220,22 @@ insert into t1 (x) values (1),(2),(3),(4),(5),(6),(7),(8),(9);
update t1 set y=x;
explain select * from t1, t1 t2 where t1.y = 2 and t2.x between 7 and t1.y+0;
id select_type table type possible_keys key key_len ref rows Extra
-1 SIMPLE t1 ref y y 5 const 1 Using where
-1 SIMPLE t2 range x x 5 NULL 4 Using where
+1 SIMPLE NULL NULL NULL NULL NULL NULL NULL Impossible WHERE noticed after reading const tables
explain select * from t1, t1 t2 where t1.y = 2 and t2.x >= 7 and t2.x <= t1.y+0;
id select_type table type possible_keys key key_len ref rows Extra
-1 SIMPLE t1 ref y y 5 const 1 Using where
-1 SIMPLE t2 range x x 5 NULL 4 Using where
+1 SIMPLE NULL NULL NULL NULL NULL NULL NULL Impossible WHERE noticed after reading const tables
explain select * from t1, t1 t2 where t1.y = 2 and t2.x between t1.y-1 and t1.y+1;
id select_type table type possible_keys key key_len ref rows Extra
1 SIMPLE t1 ref y y 5 const 1 Using where
-1 SIMPLE t2 ALL x NULL NULL NULL 9 Range checked for each record (index map: 0x1)
+1 SIMPLE t2 range x x 5 NULL 3 Using where
explain select * from t1, t1 t2 where t1.y = 2 and t2.x >= t1.y-1 and t2.x <= t1.y+1;
id select_type table type possible_keys key key_len ref rows Extra
1 SIMPLE t1 ref y y 5 const 1 Using where
-1 SIMPLE t2 ALL x NULL NULL NULL 9 Range checked for each record (index map: 0x1)
+1 SIMPLE t2 range x x 5 NULL 3 Using where
explain select * from t1, t1 t2 where t1.y = 2 and t2.x between 0 and t1.y;
id select_type table type possible_keys key key_len ref rows Extra
1 SIMPLE t1 ref y y 5 const 1 Using where
-1 SIMPLE t2 ALL x NULL NULL NULL 9 Using where
+1 SIMPLE t2 range x x 5 NULL 2 Using where
explain select * from t1, t1 t2 where t1.y = 2 and t2.x >= 0 and t2.x <= t1.y;
id select_type table type possible_keys key key_len ref rows Extra
1 SIMPLE t1 ref y y 5 const 1 Using where
@@ -415,14 +413,26 @@ count(*)
select count(*) from t2;
count(*)
1026
+analyze table t1,t2;
+Table Op Msg_type Msg_text
+test.t1 analyze status OK
+test.t2 analyze status Table is already up to date
explain select * from t1, t2 where t1.uid=t2.uid AND t1.uid > 0;
id select_type table type possible_keys key key_len ref rows Extra
1 SIMPLE t1 range uid_index uid_index 4 NULL 128 Using where
1 SIMPLE t2 ref uid_index uid_index 4 test.t1.uid 38
+explain select * from t1, t2 where t1.uid=t2.uid AND t2.uid > 0;
+id select_type table type possible_keys key key_len ref rows Extra
+1 SIMPLE t1 range uid_index uid_index 4 NULL 128 Using where
+1 SIMPLE t2 ref uid_index uid_index 4 test.t1.uid 38
explain select * from t1, t2 where t1.uid=t2.uid AND t1.uid != 0;
id select_type table type possible_keys key key_len ref rows Extra
1 SIMPLE t1 range uid_index uid_index 4 NULL 129 Using where
1 SIMPLE t2 ref uid_index uid_index 4 test.t1.uid 38
+explain select * from t1, t2 where t1.uid=t2.uid AND t2.uid != 0;
+id select_type table type possible_keys key key_len ref rows Extra
+1 SIMPLE t1 range uid_index uid_index 4 NULL 129 Using where
+1 SIMPLE t2 ref uid_index uid_index 4 test.t1.uid 38
select * from t1, t2 where t1.uid=t2.uid AND t1.uid > 0;
id name uid id name uid
1001 A 1 1001 A 1
diff --git a/mysql-test/r/select.result b/mysql-test/r/select.result
index 41eae1700b1..59a378e5eb1 100644
--- a/mysql-test/r/select.result
+++ b/mysql-test/r/select.result
@@ -1375,7 +1375,7 @@ id select_type table type possible_keys key key_len ref rows Extra
explain select t2.companynr,companyname from t4 left join t2 using (companynr) where t2.companynr > 0 and t4.companynr > 0;
id select_type table type possible_keys key key_len ref rows Extra
1 SIMPLE t2 ALL NULL NULL NULL NULL 1199 Using where
-1 SIMPLE t4 eq_ref PRIMARY PRIMARY 1 test.t2.companynr 1 Using where
+1 SIMPLE t4 eq_ref PRIMARY PRIMARY 1 test.t2.companynr 1
explain select t2.companynr,companyname from t4 left join t2 using (companynr) where t2.companynr > 0 or t2.companynr is null;
id select_type table type possible_keys key key_len ref rows Extra
1 SIMPLE t4 ALL NULL NULL NULL NULL 12
diff --git a/mysql-test/t/range.test b/mysql-test/t/range.test
index 0059cd5bd37..336f89bf252 100644
--- a/mysql-test/t/range.test
+++ b/mysql-test/t/range.test
@@ -378,8 +378,12 @@ insert into t2(id, uid, name) select id, uid, name from t1;
select count(*) from t1;
select count(*) from t2;
+analyze table t1,t2;
+
explain select * from t1, t2 where t1.uid=t2.uid AND t1.uid > 0;
+explain select * from t1, t2 where t1.uid=t2.uid AND t2.uid > 0;
explain select * from t1, t2 where t1.uid=t2.uid AND t1.uid != 0;
+explain select * from t1, t2 where t1.uid=t2.uid AND t2.uid != 0;
select * from t1, t2 where t1.uid=t2.uid AND t1.uid > 0;
select * from t1, t2 where t1.uid=t2.uid AND t1.uid != 0;
diff --git a/sql/item.cc b/sql/item.cc
index 267560b0709..a17336ea634 100644
--- a/sql/item.cc
+++ b/sql/item.cc
@@ -408,6 +408,7 @@ bool DTCollation::aggregate(DTCollation &dt, bool superset_conversion)
Item_field::Item_field(Field *f)
:Item_ident(NullS, f->table_name, f->field_name),
+ item_equal(0),
have_privileges(0), any_privileges(0)
{
set_field(f);
@@ -418,6 +419,7 @@ Item_field::Item_field(Field *f)
Item_field::Item_field(THD *thd, Field *f)
:Item_ident(NullS, thd->strdup(f->table_name),
thd->strdup(f->field_name)),
+ item_equal(0),
have_privileges(0), any_privileges(0)
{
set_field(f);
@@ -434,6 +436,7 @@ Item_field::Item_field(THD *thd, Item_field *item)
any_privileges(item->any_privileges)
{
collation.set(DERIVATION_IMPLICIT);
+ item_equal= item->item_equal;
}
void Item_field::set_field(Field *field_par)
@@ -1582,7 +1585,29 @@ void Item_field::cleanup()
I.e. we can drop 'field'.
*/
field= result_field= 0;
- DBUG_VOID_RETURN;
+}
+
+/*
+ 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
+*/
+
}
void Item::init_make_field(Send_field *tmp_field,
diff --git a/sql/item.h b/sql/item.h
index 71db03ad687..9826bcb4a5a 100644
--- a/sql/item.h
+++ b/sql/item.h
@@ -90,6 +90,7 @@ public:
};
typedef bool (Item::*Item_processor)(byte *arg);
+typedef Item* (Item::*Item_transformer) (byte *arg);
class Item {
Item(const Item &); /* Prevent use of these */
@@ -261,8 +262,15 @@ public:
return (this->*processor)(arg);
}
+ virtual Item* transform(Item_transformer transformer, byte *arg)
+ {
+ return (this->*transformer)(arg);
+ }
+
virtual bool remove_dependence_processor(byte * arg) { return 0; }
virtual bool remove_fixed(byte * arg) { fixed= 0; return 0; }
+ virtual Item *equal_fields_propagator(byte * arg) { return this; }
+ virtual bool replace_equal_field_processor(byte * arg) { return 0; }
virtual Item *this_item() { return this; } /* For SPs mostly. */
virtual Item *this_const_item() const { return const_cast<Item*>(this); } /* For SPs mostly. */
@@ -440,6 +448,8 @@ public:
bool any_privileges, bool allocate_view_names);
};
+class Item_equal;
+class COND_EQUAL;
class Item_field :public Item_ident
{
@@ -458,7 +468,8 @@ public:
Item_field(const char *db_par,const char *table_name_par,
const char *field_name_par)
:Item_ident(db_par,table_name_par,field_name_par),
- field(0), result_field(0), have_privileges(0), any_privileges(0)
+ field(0), result_field(0), item_equal(0),}
+ have_privileges(0), any_privileges(0)
{ collation.set(DERIVATION_IMPLICIT); }
// Constructor need to process subselect with temporary tables (see Item)
Item_field(THD *thd, Item_field *item);
@@ -498,6 +509,9 @@ public:
bool is_null() { return field->is_null(); }
Item *get_tmp_table_item(THD *thd);
void cleanup();
+ Item_equal *find_item_equal(COND_EQUAL *cond_equal);
+ Item *equal_fields_propagator(byte *arg);
+ bool replace_equal_field_processor(byte *arg);
inline uint32 max_disp_length() { return field->max_length(); }
Item_field *filed_for_view_update() { return this; }
friend class Item_default_value;
@@ -1173,6 +1187,19 @@ public:
return arg->walk(processor, args) ||
(this->*processor)(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->transform(transformer, args);
+ if (!new_item)
+ return 0;
+ arg= new_item;
+ return (this->*transformer)(args);
+ }
};
class Item_insert_value : public Item_field
diff --git a/sql/item_cmpfunc.cc b/sql/item_cmpfunc.cc
index 582277cd142..1f2e744f714 100644
--- a/sql/item_cmpfunc.cc
+++ b/sql/item_cmpfunc.cc
@@ -256,7 +256,7 @@ void Item_bool_func2::fix_length_and_dec()
}
}
}
- if (args[1]->type() == FIELD_ITEM)
+ if (args[1]->type() == FIELD_ITEM /* && !args[1]->const_item() */)
{
Field *field=((Item_field*) args[1])->field;
if (field->store_for_compare())
@@ -2008,6 +2008,44 @@ bool Item_cond::walk(Item_processor processor, byte *arg)
return Item_func::walk(processor, 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->transform(transformer, arg);
+ if (!new_item)
+ return 0;
+ if (new_item != item)
+ li.replace(new_item);
+ }
+ return Item_func::transform(transformer, arg);
+}
+
+
void Item_cond::split_sum_func(Item **ref_pointer_array, List<Item> &fields)
{
List_iterator<Item> li(list);
@@ -2854,3 +2892,289 @@ Item *Item_bool_rowready_func2::negated_item()
DBUG_ASSERT(0);
return 0;
}
+
+Item_equal::Item_equal(Item_field *f1, Item_field *f2)
+ : Item_bool_func(), const_item(0), eval_item(0), cond_false(0)
+{
+ const_item_cache= 0;
+ fields.push_back(f1);
+ fields.push_back(f2);
+}
+
+Item_equal::Item_equal(Item *c, Item_field *f)
+ : Item_bool_func(), eval_item(0), cond_false(0)
+{
+ const_item_cache= 0;
+ fields.push_back(f);
+ const_item= c;
+}
+
+Item_equal::Item_equal(Item_equal *item_equal)
+ : Item_bool_func(), eval_item(0), cond_false(0)
+{
+ const_item_cache= 0;
+ List_iterator_fast<Item_field> li(item_equal->fields);
+ Item_field *item;
+ while ((item= li++))
+ {
+ fields.push_back(item);
+ }
+ const_item= item_equal->const_item;
+ cond_false= item_equal->cond_false;
+}
+
+void Item_equal::add(Item *c)
+{
+ if (cond_false)
+ return;
+ if (!const_item)
+ {
+ const_item= c;
+ return;
+ }
+ Item_func_eq *func= new Item_func_eq(c, const_item);
+ func->set_cmp_func();
+ cond_false = !(func->val_int());
+}
+
+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);
+ Item_field *item;
+ while ((item= it++))
+ {
+ if (field->eq(item->field))
+ return 1;
+ }
+ 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);
+ Item *c= item->const_item;
+ if (c)
+ {
+ /*
+ The flag cond_false will be set to 1 after this, if
+ the multiple equality already contains a constant and its
+ value is not equal to the value of c.
+ */
+ add(const_item);
+ }
+ cond_false|= item->cond_false;
+}
+
+
+/*
+ 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;
+ List_iterator<Item_field> it(fields);
+ do
+ {
+ Item_field *item1= it++;
+ Item_field **ref1= it.ref();
+ Item_field *item2;
+
+ swap= FALSE;
+ while ((item2= it++))
+ {
+ Item_field **ref2= it.ref();
+ if (cmp(item1, item2, arg) < 0)
+ {
+ Item_field *item= *ref1;
+ *ref1= *ref2;
+ *ref2= item;
+ swap= TRUE;
+ }
+ else
+ {
+ item1= item2;
+ ref1= ref2;
+ }
+ }
+ it.rewind();
+ } while (swap);
+}
+
+bool Item_equal::fix_fields(THD *thd, TABLE_LIST *tables, Item **ref)
+{
+ List_iterator_fast<Item_field> li(fields);
+ Item *item;
+ not_null_tables_cache= used_tables_cache= 0;
+ const_item_cache= 0;
+ while ((item=li++))
+ {
+ table_map tmp_table_map;
+ used_tables_cache|= item->used_tables();
+ tmp_table_map= item->not_null_tables();
+ not_null_tables_cache|= tmp_table_map;
+ if (item->maybe_null)
+ maybe_null=1;
+ }
+ fix_length_and_dec();
+ fixed= 1;
+ return 0;
+}
+
+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();
+ used_tables_cache|= item->used_tables();
+ const_item_cache&= item->const_item();
+ }
+}
+
+longlong Item_equal::val_int()
+{
+ if (cond_false)
+ return 0;
+ List_iterator_fast<Item_field> it(fields);
+ Item *item= const_item ? const_item : it++;
+ if ((null_value= item->null_value))
+ return 0;
+ eval_item->store_value(item);
+ while ((item= it++))
+ {
+ if ((null_value= item->null_value) || eval_item->cmp(item))
+ return 0;
+ }
+ return 1;
+}
+
+void Item_equal::fix_length_and_dec()
+{
+ Item *item= const_item ? const_item : get_first();
+ eval_item= cmp_item::get_comparator(item);
+ if (item->result_type() == STRING_RESULT)
+ eval_item->cmp_charset= cmp_collation.collation;
+}
+
+bool Item_equal::walk(Item_processor processor, byte *arg)
+{
+ List_iterator_fast<Item_field> it(fields);
+ Item *item;
+ while ((item= it++))
+ if (item->walk(processor, arg))
+ return 1;
+ return Item_func::walk(processor, 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->transform(transformer, arg);
+ if (!new_item)
+ return 0;
+ if (new_item != item)
+ it.replace((Item_field *) new_item);
+ }
+ return Item_func::transform(transformer, arg);
+}
+
+void Item_equal::print(String *str)
+{
+ str->append(func_name());
+ str->append('(');
+ List_iterator_fast<Item_field> it(fields);
+ Item *item;
+ if (const_item)
+ const_item->print(str);
+ else
+ {
+ item= it++;
+ item->print(str);
+ }
+ while ((item= it++))
+ {
+ str->append(',');
+ str->append(' ');
+ item->print(str);
+ }
+ str->append(')');
+}
+
diff --git a/sql/item_cmpfunc.h b/sql/item_cmpfunc.h
index e7bef18e629..a8382df20f5 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;
@@ -957,6 +962,7 @@ public:
Item_cond(List<Item> &nlist)
:Item_bool_func(), list(nlist), abort_on_null(0) {}
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; }
@@ -969,13 +975,151 @@ 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 *transform(Item_transformer transformer, byte *arg);
void neg_arguments(THD *thd);
};
+/*
+ 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 */
+ Item *const_item; /* optional constant item equal to fields items */
+ cmp_item *eval_item;
+ bool cond_false;
+ DTCollation cmp_collation;
+public:
+ inline Item_equal()
+ : Item_bool_func(), const_item(0), eval_item(0), cond_false(0)
+ { const_item_cache=0 ;}
+ Item_equal(Item_field *f1, Item_field *f2);
+ Item_equal(Item *c, Item_field *f);
+ Item_equal(Item_equal *item_equal);
+ inline Item* get_const() { return const_item; }
+ void add(Item *c);
+ void add(Item_field *f);
+ uint members();
+ bool contains(Field *field);
+ Item_field* get_first() { return fields.head(); }
+ void merge(Item_equal *item);
+ enum Functype functype() const { return MULT_EQUAL_FUNC; }
+ longlong val_int();
+ const char *func_name() const { return "multiple equal"; }
+ optimize_type select_optimize() const { return OPTIMIZE_EQUAL; }
+ 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 *transform(Item_transformer transformer, byte *arg);
+ void print(String *str);
+ CHARSET_INFO *compare_collation()
+ { return fields.head()->collation.collation; }
+};
+
+class COND_EQUAL
+{
+public:
+ 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;
+ }
+};
+
+
+class Item_equal_iterator :List_iterator_fast<Item_field>
+{
+public:
+ inline Item_equal_iterator(Item_equal &item_equal)
+ :List_iterator_fast<Item_field> (item_equal.fields)
+ {}
+ inline Item_field* operator++(int)
+ {
+ Item_field *item= (*(List_iterator_fast<Item_field> *) this)++;
+ return item;
+ }
+ inline void rewind(void)
+ {
+ List_iterator_fast<Item_field>::rewind();
+ }
+};
+
class Item_cond_and :public Item_cond
{
public:
+ 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 4aec7fea2d4..fe5112cd75b 100644
--- a/sql/item_func.cc
+++ b/sql/item_func.cc
@@ -260,6 +260,45 @@ bool Item_func::walk (Item_processor processor, byte *argument)
return (this->*processor)(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)->transform(transformer, argument);
+ if (!new_item)
+ return 0;
+ *arg= new_item;
+ }
+ }
+ return (this->*transformer)(argument);
+}
+
+
void Item_func::split_sum_func(Item **ref_pointer_array, List<Item> &fields)
{
Item **arg, **arg_end;
diff --git a/sql/item_func.h b/sql/item_func.h
index f1a74bdf3ab..a5448f54693 100644
--- a/sql/item_func.h
+++ b/sql/item_func.h
@@ -40,7 +40,8 @@ public:
enum Functype { UNKNOWN_FUNC,EQ_FUNC,EQUAL_FUNC,NE_FUNC,LT_FUNC,LE_FUNC,
GE_FUNC,GT_FUNC,FT_FUNC,
LIKE_FUNC,NOTLIKE_FUNC,ISNULL_FUNC,ISNOTNULL_FUNC,
- COND_AND_FUNC, COND_OR_FUNC, COND_XOR_FUNC, BETWEEN, IN_FUNC,
+ COND_AND_FUNC, COND_OR_FUNC, COND_XOR_FUNC,
+ BETWEEN, IN_FUNC, MULT_EQUAL_FUNC,
INTERVAL_FUNC, ISNOTNULLTEST_FUNC,
SP_EQUALS_FUNC, SP_DISJOINT_FUNC,SP_INTERSECTS_FUNC,
SP_TOUCHES_FUNC,SP_CROSSES_FUNC,SP_WITHIN_FUNC,
@@ -50,7 +51,8 @@ public:
NOT_FUNC, NOT_ALL_FUNC,
NOW_FUNC, TRIG_COND_FUNC,
GUSERVAR_FUNC};
- enum optimize_type { OPTIMIZE_NONE,OPTIMIZE_KEY,OPTIMIZE_OP, OPTIMIZE_NULL };
+ enum optimize_type { OPTIMIZE_NONE,OPTIMIZE_KEY,OPTIMIZE_OP, OPTIMIZE_NULL,
+ OPTIMIZE_EQUAL };
enum Type type() const { return FUNC_ITEM; }
virtual enum Functype functype() const { return UNKNOWN_FUNC; }
Item_func(void):
@@ -150,6 +152,7 @@ public:
bool allow_superset_comversion= FALSE);
bool walk(Item_processor processor, byte *arg);
+ Item *transform(Item_transformer transformer, byte *arg);
};
diff --git a/sql/item_row.cc b/sql/item_row.cc
index f6623e80734..8bf0d5061a7 100644
--- a/sql/item_row.cc
+++ b/sql/item_row.cc
@@ -145,6 +145,18 @@ bool Item_row::walk(Item_processor processor, byte *arg)
return (this->*processor)(arg);
}
+Item *Item_row::transform(Item_transformer transformer, byte *arg)
+{
+ for (uint i= 0; i < arg_count; i++)
+ {
+ Item *new_item= items[i]->transform(transformer, arg);
+ if (!new_item)
+ return 0;
+ items[i]= new_item;
+ }
+ return (this->*transformer)(arg);
+}
+
void Item_row::bring_value()
{
for (uint i= 0; i < arg_count; i++)
diff --git a/sql/item_row.h b/sql/item_row.h
index f87b4f66e80..ec5f0f1fc95 100644
--- a/sql/item_row.h
+++ b/sql/item_row.h
@@ -65,6 +65,7 @@ public:
void print(String *str);
bool walk(Item_processor processor, 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 111f0e20698..357ce0af45a 100644
--- a/sql/item_strfunc.h
+++ b/sql/item_strfunc.h
@@ -428,6 +428,14 @@ public:
return item->walk(processor, arg) ||
Item_str_func::walk(processor, arg);
}
+ Item *transform(Item_transformer transformer, byte *arg)
+ {
+ Item *new_item= item->transform(transformer, arg);
+ if (!new_item)
+ return 0;
+ item= new_item;
+ return Item_str_func::transform(transformer, arg);
+ }
void print(String *str);
};
diff --git a/sql/opt_range.cc b/sql/opt_range.cc
index ebb9c8098cf..502a8d51b07 100644
--- a/sql/opt_range.cc
+++ b/sql/opt_range.cc
@@ -3148,12 +3148,98 @@ QUICK_SELECT_I *TRP_ROR_UNION::make_quick(PARAM *param,
DBUG_RETURN(quick_roru);
}
-/****************************************************************************/
+
+/*
+ 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)
+{
+ SEL_TREE *tree= 0;
+ DBUG_ENTER("get_func_mm_tree");
+
+ switch (cond_func->functype()) {
+ case Item_func::NE_FUNC:
+ tree= get_mm_parts(param, cond_func, field, Item_func::LT_FUNC,
+ value, cmp_type);
+ if (tree)
+ {
+ tree= tree_or(param, tree, get_mm_parts(param, cond_func, field,
+ Item_func::GT_FUNC,
+ value, cmp_type));
+ }
+ break;
+ case Item_func::BETWEEN:
+ tree= get_mm_parts(param, cond_func, field, Item_func::GE_FUNC,
+ cond_func->arguments()[1],cmp_type);
+ if (tree)
+ {
+ tree= tree_and(param, tree, get_mm_parts(param, cond_func, field,
+ Item_func::LE_FUNC,
+ cond_func->arguments()[2],
+ cmp_type));
+ }
+ break;
+ case Item_func::IN_FUNC:
+ {
+ Item_func_in *func=(Item_func_in*) cond_func;
+ tree= get_mm_parts(param, cond_func, field, Item_func::EQ_FUNC,
+ func->arguments()[1], cmp_type);
+ if (tree)
+ {
+ 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, cond_func, field,
+ Item_func::EQ_FUNC,
+ *arg,
+ cmp_type));
+ }
+ }
+ break;
+ }
+ 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, cond_func, field, func_type, value, cmp_type);
+ }
+ }
+
+ DBUG_RETURN(tree);
+
+}
+
/* make a select tree of all keys in condition */
static SEL_TREE *get_mm_tree(PARAM *param,COND *cond)
{
SEL_TREE *tree=0;
+ SEL_TREE *ftree= 0;
+ Item_field *field_item= 0;
+ Item *value;
DBUG_ENTER("get_mm_tree");
if (cond->type() == Item::COND_ITEM)
@@ -3201,9 +3287,12 @@ static SEL_TREE *get_mm_tree(PARAM *param,COND *cond)
DBUG_RETURN(new SEL_TREE(SEL_TREE::IMPOSSIBLE));
}
- table_map ref_tables=cond->used_tables();
+ table_map ref_tables= 0;
+ table_map param_comp= ~(param->prev_tables | param->read_tables |
+ param->current_table);
if (cond->type() != Item::FUNC_ITEM)
{ // Should be a field
+ ref_tables= cond->used_tables();
if ((ref_tables & param->current_table) ||
(ref_tables & ~(param->prev_tables | param->read_tables)))
DBUG_RETURN(0);
@@ -3214,80 +3303,42 @@ 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
- param->cond= cond;
-
- if (cond_func->functype() == Item_func::BETWEEN)
+ switch (cond_func->functype()) {
+ case Item_func::BETWEEN:
+ if (cond_func->arguments()[0]->type() != Item::FIELD_ITEM)
+ DBUG_RETURN(0);
+ field_item= (Item_field*) (cond_func->arguments()[0]);
+ value= NULL;
+ break;
+ case Item_func::IN_FUNC:
{
- if (cond_func->arguments()[0]->type() == Item::FIELD_ITEM)
- {
- Field *field=((Item_field*) (cond_func->arguments()[0]))->field;
- Item_result cmp_type=field->cmp_type();
- DBUG_RETURN(tree_and(param,
- get_mm_parts(param, cond_func, field,
- Item_func::GE_FUNC,
- cond_func->arguments()[1], cmp_type),
- get_mm_parts(param, cond_func, field,
- Item_func::LE_FUNC,
- cond_func->arguments()[2], cmp_type)));
- }
- DBUG_RETURN(0);
- }
- if (cond_func->functype() == Item_func::IN_FUNC)
- { // COND OR
Item_func_in *func=(Item_func_in*) cond_func;
- if (func->key_item()->type() == Item::FIELD_ITEM)
+ if (func->key_item()->type() != Item::FIELD_ITEM)
+ DBUG_RETURN(0);
+ field_item= (Item_field*) (func->key_item());
+ value= NULL;
+ break;
+ }
+ case Item_func::MULT_EQUAL_FUNC:
+ {
+ Item_equal *item_equal= (Item_equal *) cond;
+ if (!(value= item_equal->get_const()))
+ DBUG_RETURN(0);
+ Item_equal_iterator it(*item_equal);
+ ref_tables= value->used_tables();
+ while ((field_item= it++))
{
- Field *field=((Item_field*) (func->key_item()))->field;
- Item_result cmp_type=field->cmp_type();
- tree= get_mm_parts(param,cond_func,field,Item_func::EQ_FUNC,
- func->arguments()[1],cmp_type);
- if (!tree)
- DBUG_RETURN(tree); // Not key field
- for (uint i=2 ; i < func->argument_count(); i++)
+ Field *field= field_item->field;
+ Item_result cmp_type= field->cmp_type();
+ if (!((ref_tables | field->table->map) & param_comp))
{
- SEL_TREE *new_tree=get_mm_parts(param,cond_func,field,
- Item_func::EQ_FUNC,
- func->arguments()[i],cmp_type);
- tree=tree_or(param,tree,new_tree);
+ tree= get_mm_parts(param, cond, field, Item_func::EQ_FUNC,
+ value,cmp_type);
+ ftree= !ftree ? tree : tree_and(param, ftree, tree);
}
- DBUG_RETURN(tree);
}
- DBUG_RETURN(0); // Can't optimize this IN
- }
-
- if (ref_tables & ~(param->prev_tables | param->read_tables |
- param->current_table))
- DBUG_RETURN(0); // Can't be calculated yet
- if (!(ref_tables & param->current_table))
- DBUG_RETURN(new SEL_TREE(SEL_TREE::MAYBE)); // This may be FALSE or TRUE
-
- /* check field op const */
- /* btw, ft_func's arguments()[0] isn't FIELD_ITEM. SerG*/
- if (cond_func->arguments()[0]->type() == Item::FIELD_ITEM)
- {
- tree= get_mm_parts(param, cond_func,
- ((Item_field*) (cond_func->arguments()[0]))->field,
- cond_func->functype(),
- cond_func->arg_count > 1 ? cond_func->arguments()[1] :
- 0,
- ((Item_field*) (cond_func->arguments()[0]))->field->
- cmp_type());
- }
- /* check const op field */
- if (!tree &&
- cond_func->have_rev_func() &&
- cond_func->arguments()[1]->type() == Item::FIELD_ITEM)
- {
- DBUG_RETURN(get_mm_parts(param, cond_func,
- ((Item_field*)
- (cond_func->arguments()[1]))->field,
- ((Item_bool_func2*) cond_func)->rev_functype(),
- cond_func->arguments()[0],
- ((Item_field*)
- (cond_func->arguments()[1]))->field->cmp_type()
- ));
- }
- DBUG_RETURN(tree);
+
+ DBUG_RETURN(ftree);
}
@@ -3296,17 +3347,10 @@ get_mm_parts(PARAM *param, COND *cond_func, Field *field,
Item_func::Functype type,
Item *value, Item_result cmp_type)
{
- bool ne_func= FALSE;
DBUG_ENTER("get_mm_parts");
if (field->table != param->table)
DBUG_RETURN(0);
- if (type == Item_func::NE_FUNC)
- {
- ne_func= TRUE;
- type= Item_func::LT_FUNC;
- }
-
KEY_PART *key_part = param->key_parts;
KEY_PART *end = param->key_parts_end;
SEL_TREE *tree=0;
@@ -3344,15 +3388,6 @@ get_mm_parts(PARAM *param, COND *cond_func, Field *field,
}
}
- if (ne_func)
- {
- SEL_TREE *tree2= get_mm_parts(param, cond_func,
- field, Item_func::GT_FUNC,
- value, cmp_type);
- if (tree2)
- tree= tree_or(param,tree,tree2);
- }
-
DBUG_RETURN(tree);
}
diff --git a/sql/opt_sum.cc b/sql/opt_sum.cc
index 314decb7041..a47f7eb4278 100644
--- a/sql/opt_sum.cc
+++ b/sql/opt_sum.cc
@@ -341,6 +341,18 @@ static bool simple_pred(Item_func *func_item, Item **args, bool *inv_order)
Item *item;
*inv_order= 0;
switch (func_item->argument_count()) {
+ case 0:
+ /* MULT_EQUAL_FUNC */
+ {
+ Item_equal *item_equal= (Item_equal *) func_item;
+ Item_equal_iterator it(*item_equal);
+ args[0]= it++;
+ if (it++)
+ return 0;
+ if (!(args[1]= item_equal->get_const()))
+ return 0;
+ }
+ break;
case 1:
/* field IS NULL */
item= func_item->arguments()[0];
@@ -481,6 +493,9 @@ static bool matching_cond(bool max_fl, TABLE_REF *ref, KEY *keyinfo,
case Item_func::BETWEEN:
between= 1;
break;
+ case Item_func::MULT_EQUAL_FUNC:
+ eq_type= 1;
+ break;
default:
return 0; // Can't optimize function
}
diff --git a/sql/sql_list.h b/sql/sql_list.h
index a4379b74c17..40530314893 100644
--- a/sql/sql_list.h
+++ b/sql/sql_list.h
@@ -127,10 +127,12 @@ public:
void remove(list_node **prev)
{
list_node *node=(*prev)->next;
- delete *prev;
- *prev=node;
if (!--elements)
last= &first;
+ else if (last == &(*prev)->next)
+ last= prev;
+ delete *prev;
+ *prev=node;
}
inline void *pop(void)
{
@@ -143,9 +145,36 @@ public:
}
inline void concat(base_list *list)
{
- *last= list->first;
- last= list->last;
- elements+= list->elements;
+ if (!list->is_empty())
+ {
+ *last= list->first;
+ last= list->last;
+ elements+= list->elements;
+ }
+ }
+ inline void disjoin(base_list *list)
+ {
+ list_node **prev= &first;
+ list_node *node= first;
+ list_node *list_first= list->first;
+ elements=0;
+ while (node && node != list_first)
+ {
+ prev= &node->next;
+ node= node->next;
+ elements++;
+ }
+ *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;}
@@ -257,6 +286,9 @@ public:
inline T* head() {return (T*) base_list::head(); }
inline T** head_ref() {return (T**) base_list::head_ref(); }
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;
@@ -267,7 +299,6 @@ public:
}
empty();
}
- inline void concat(List<T> *list) { base_list::concat(list); }
};
@@ -278,6 +309,8 @@ public:
inline T* operator++(int) { return (T*) base_list_iterator::next(); }
inline T *replace(T *a) { return (T*) base_list_iterator::replace(a); }
inline T *replace(List<T> &a) { return (T*) base_list_iterator::replace(a); }
+ inline void rewind(void) { base_list_iterator::rewind(); }
+ inline void remove() { base_list_iterator::remove(); }
inline void after(T *a) { base_list_iterator::after(a); }
inline T** ref(void) { return (T**) base_list_iterator::ref(); }
};
diff --git a/sql/sql_select.cc b/sql/sql_select.cc
index e104ac1ca38..b3355f6c57c 100644
--- a/sql/sql_select.cc
+++ b/sql/sql_select.cc
@@ -43,6 +43,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);
@@ -90,6 +91,11 @@ 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 COND *build_all_equal_items(COND *cond,
+ COND_EQUAL *inherited);
+static COND* substitute_for_best_equal_field(COND *cond,
+ COND_EQUAL *cond_equal,
+ void *table_join_idx);
static COND *simplify_joins(JOIN *join, List<TABLE_LIST> *join_list,
COND *conds, bool top);
static COND *optimize_cond(JOIN *join, COND *conds,
@@ -525,6 +531,52 @@ JOIN::optimize()
}
#endif
+ /* Eliminate NOT operators */
+ conds= eliminate_not_funcs(conds);
+ DBUG_EXECUTE("where", print_where(conds, "after negation elimination"););
+ {
+ TABLE_LIST *tables;
+ for (tables= tables_list; tables; tables= tables->next)
+ {
+ if (tables->on_expr)
+ tables->on_expr= eliminate_not_funcs(tables->on_expr);
+ }
+ }
+
+ /*
+ Build all multiple equality predicates and eliminate equality
+ predicates that can be inferred from these multiple equalities.
+ For each reference of a field included into a multiple equality
+ that occurs in a function set a pointer to the multiple equality
+ predicate. Substitute a constant instead of this field if the
+ multiple equality contains a constant.
+ */
+ if (conds)
+ {
+ conds= build_all_equal_items(conds, NULL);
+ conds->update_used_tables();
+ if (conds->type() == Item::COND_ITEM &&
+ ((Item_cond*) conds)->functype() == Item_func::COND_AND_FUNC)
+ cond_equal= &((Item_cond_and*) conds)->cond_equal;
+ else if (conds->type() == Item::FUNC_ITEM &&
+ ((Item_cond*) conds)->functype() == Item_func::MULT_EQUAL_FUNC)
+ {
+ cond_equal= new COND_EQUAL;
+ cond_equal->current_level.push_back((Item_equal *) conds);
+ }
+ }
+ {
+ TABLE_LIST *tables;
+ for (tables= tables_list; tables; tables= tables->next)
+ {
+ if (tables->on_expr)
+ {
+ tables->on_expr= build_all_equal_items(tables->on_expr, cond_equal);
+ tables->on_expr->update_used_tables();
+ }
+ }
+ }
+
conds= optimize_cond(this, conds,&cond_value);
if (thd->net.report_error)
{
@@ -617,7 +669,31 @@ JOIN::optimize()
if (const_tables && !thd->locked_tables &&
!(select_options & SELECT_NO_UNLOCK))
mysql_unlock_some_tables(thd, table, const_tables);
-
+ /*
+ Among the equal fields belonging to the same multiple equality
+ choose the one that is to be retrieved first and substitute
+ all references to these in where condition for a reference for
+ the selected field.
+ */
+ if (conds)
+ {
+ conds= substitute_for_best_equal_field(conds, cond_equal, map2table);
+ conds->update_used_tables();
+ }
+ {
+ TABLE_LIST *tables;
+ for (tables= tables_list; tables; tables= tables->next)
+ {
+ if (tables->on_expr)
+ {
+ tables->on_expr= substitute_for_best_equal_field(tables->on_expr,
+ cond_equal,
+ map2table);
+ tables->on_expr->update_used_tables();
+ map2table[tables->table->tablenr]->on_expr= tables->on_expr;
+ }
+ }
+ }
if (!conds && outer_join)
{
/* Handle the case where we have an OUTER JOIN without a WHERE */
@@ -2150,7 +2226,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) */
@@ -2482,6 +2559,7 @@ merge_key_fields(KEY_FIELD *start,KEY_FIELD *new_fields,KEY_FIELD *end,
add_key_field()
key_fields Pointer to add key, if usable
and_level And level, to be stored in KEY_FIELD
+ cond Condition predicate
field Field used in comparision
eq_func True if we used =, <=> or IS NULL
value Value used for comparison with field
@@ -2497,8 +2575,8 @@ merge_key_fields(KEY_FIELD *start,KEY_FIELD *new_fields,KEY_FIELD *end,
*/
static void
-add_key_field(KEY_FIELD **key_fields,uint and_level, COND *cond,
- Field *field,bool eq_func,Item **value, uint num_values,
+add_key_field(KEY_FIELD **key_fields, uint and_level, COND *cond,
+ Field *field, bool eq_func, Item **value, uint num_values,
table_map usable_tables)
{
uint exists_optimize= 0;
@@ -2603,6 +2681,57 @@ add_key_field(KEY_FIELD **key_fields,uint and_level, COND *cond,
}
+/*
+ Add possible keys to array of possible keys originated from a simple predicate
+
+ SYNPOSIS
+ add_key_equal_fields()
+ key_fields Pointer to add key, if usable
+ and_level And level, to be stored in KEY_FIELD
+ cond Condition predicate
+ 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,
+ COND *cond, Item_field *field_item,
+ bool eq_func, Item **val,
+ uint num_values, table_map usable_tables)
+{
+ Field *field= field_item->field;
+ add_key_field(key_fields, and_level, cond, field,
+ eq_func, val, num_values, usable_tables);
+ Item_equal *item_equal= field_item->item_equal;
+ if (item_equal)
+ {
+ /*
+ Add to the set of possible key values every substitution of
+ the field for an equal field included into item_equal
+ */
+ Item_equal_iterator it(*item_equal);
+ Item_field *item;
+ while ((item= it++))
+ {
+ if (!field->eq(item->field))
+ {
+ add_key_field(key_fields, and_level, cond, item->field,
+ eq_func, val, num_values, usable_tables);
+ }
+ }
+ }
+}
+
static void
add_key_fields(JOIN_TAB *stat,KEY_FIELD **key_fields,uint *and_level,
COND *cond, table_map usable_tables)
@@ -2663,21 +2792,19 @@ add_key_fields(JOIN_TAB *stat,KEY_FIELD **key_fields,uint *and_level,
if (cond_func->arguments()[0]->real_item()->type() == Item::FIELD_ITEM &&
!(cond_func->arguments()[0]->used_tables() & OUTER_REF_TABLE_BIT))
{
- add_key_field(key_fields,*and_level,cond_func,
- ((Item_field*) (cond_func->arguments()[0])->real_item())
- ->field,
- equal_func,
- cond_func->arguments()+1, 1, usable_tables);
+ add_key_equal_fields(key_fields, *and_level, cond_func,
+ (Item_field*) (cond_func->arguments()[0])->real_item(),
+ equal_func,
+ cond_func->arguments()+1, 1, usable_tables);
}
if (cond_func->arguments()[1]->real_item()->type() == Item::FIELD_ITEM &&
cond_func->functype() != Item_func::LIKE_FUNC &&
!(cond_func->arguments()[1]->used_tables() & OUTER_REF_TABLE_BIT))
{
- add_key_field(key_fields,*and_level,cond_func,
- ((Item_field*) (cond_func->arguments()[1])->real_item())
- ->field,
- equal_func,
- cond_func->arguments(),1,usable_tables);
+ add_key_equal_fields(key_fields, *and_level, cond_func,
+ (Item_field*) (cond_func->arguments()[1])->real_item(),
+ equal_func,
+ cond_func->arguments(),1,usable_tables);
}
break;
}
@@ -2689,15 +2816,55 @@ add_key_fields(JOIN_TAB *stat,KEY_FIELD **key_fields,uint *and_level,
Item *tmp=new Item_null;
if (unlikely(!tmp)) // Should never be true
return;
- add_key_field(key_fields,*and_level,cond_func,
- ((Item_field*) (cond_func->arguments()[0])->real_item())
- ->field,
+ add_key_equal_fields(key_fields, *and_level, cond_func,
+ (Item_field*) (cond_func->arguments()[0])->real_item(),
cond_func->functype() == Item_func::ISNULL_FUNC,
&tmp, 1, usable_tables);
}
break;
+ case Item_func::OPTIMIZE_EQUAL:
+ Item_equal *item_equal= (Item_equal *) cond;
+ Item *const_item= item_equal->get_const();
+ Item_equal_iterator it(*item_equal);
+ Item_field *item;
+ if (const_item)
+ {
+ /*
+ For each field field1 from item_equal consider the equality
+ field1=const_item as a condition allowing an index access of the table
+ with field1 by the keys value of field1.
+ */
+ while ((item= it++))
+ {
+ add_key_field(key_fields, *and_level, cond, item->field,
+ TRUE, &const_item, 1, usable_tables);
+ }
+ }
+ else
+ {
+ /*
+ Consider all pairs of different fields included into item_equal.
+ For each of them (field1, field1) consider the equality
+ field1=field2 as a condition allowing an index access of the table
+ with field1 by the keys value of field2.
+ */
+ Item_equal_iterator fi(*item_equal);
+ while ((item= fi++))
+ {
+ Field *field= item->field;
+ while ((item= it++))
+ {
+ if (!field->eq(item->field))
+ {
+ add_key_field(key_fields, *and_level, cond, field,
+ TRUE, (Item **) &item, 1, usable_tables);
+ }
+ }
+ it.rewind();
+ }
+ }
+ break;
}
- return;
}
/*
@@ -2840,15 +3007,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;
@@ -4953,7 +5124,7 @@ make_join_select(JOIN *join,SQL_SELECT *select,COND *cond)
}
COND *tmp=make_cond_for_table(cond,used_tables,current_map);
- if (!tmp && tab->quick)
+ if (!tmp && tab->quick && tab->type == JT_ALL)
{ // Outer join
if (tab->type != JT_ALL)
{
@@ -5757,6 +5928,668 @@ template class List<Item_func_match>;
template class List_iterator<Item_func_match>;
#endif
+
+/*
+ Find the multiple equality predicate containing a field
+
+ SYNOPSIS
+ find_item_equal()
+ cond_equal multiple equalities to search in
+ field field to look for
+ inherited_fl :out set up to TRUE iff multiple equality is found
+ on upper levels (not on current level of cond_equal)
+
+ DESCRIPTION
+ The function retrieves the multiple equalities accessed through
+ the con_equal structure from current level and up looking for
+ an equality containing field. It stops retrieval as soon as the equality
+ is found and set up inherited_fl to TRUE if it's found on upper levels.
+
+ RETURN
+ Item_equal for the found multiple equality predicate if a success;
+ NULL - otherwise.
+*/
+
+Item_equal *find_item_equal(COND_EQUAL *cond_equal, Field *field,
+ bool *inherited_fl)
+{
+ Item_equal *item= 0;
+ bool in_upper_level= FALSE;
+ while (cond_equal)
+ {
+ List_iterator_fast<Item_equal> li(cond_equal->current_level);
+ while ((item= li++))
+ {
+ if (item->contains(field))
+ goto finish;
+ }
+ in_upper_level= TRUE;
+ cond_equal= cond_equal->upper_levels;
+ }
+ in_upper_level= FALSE;
+finish:
+ *inherited_fl= in_upper_level;
+ return item;
+}
+
+
+/*
+ Check whether an item is a simple equality predicate and if so
+ create/find a multiple equality for this predicate
+
+ SYNOPSIS
+ check_equality()
+ item item to check
+ cond_equal multiple equalities that must hold together with the predicate
+
+ 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
+ (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 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 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
+ general case, its own constant for each fields from the multiple
+ equality. But at the same time it would allow us to get rid
+ of constant propagation completely: it would be done by the call
+ to build_all_equal_items.
+
+ IMPLEMENTATION
+ The implementation does not follow exactly the above rules to
+ 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 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
+ multiple equalities.
+ If the function processes the predicate of the form field1=const,
+ it looks for a multiple equality containing field1. If found, the
+ function checks the constant of the multiple equality. If the value
+ is unknown, it is setup to const. Otherwise the value is compared with
+ const and the evaluation of the equality predicate is performed.
+ When expanding/merging equality predicates from the upper levels
+ the function first copies them for the current level. It looks
+ acceptable, as this happens rarely. The implementation without
+ copying would be much more complicated.
+
+ RETURN
+ TRUE - if the predicate is a simple equality predicate
+ FALSE - otherwise
+*/
+
+static bool check_equality(Item *item, COND_EQUAL *cond_equal)
+{
+ if (item->type() == Item::FUNC_ITEM &&
+ ((Item_func*) item)->functype() == Item_func::EQ_FUNC)
+ {
+ Item *left_item= ((Item_func*) item)->arguments()[0];
+ Item *right_item= ((Item_func*) item)->arguments()[1];
+ if (left_item->type() == Item::FIELD_ITEM &&
+ right_item->type() == Item::FIELD_ITEM)
+ {
+ /* The predicate the form field1=field2 is processed */
+
+ Field *left_field= ((Item_field*) left_item)->field;
+ Field *right_field= ((Item_field*) right_item)->field;
+
+ if (!left_field->eq_def(right_field))
+ return FALSE;
+
+ if (left_field->eq(right_field)) /* f = f */
+ return TRUE;
+
+ /* Search for multiple equalities containing field1 and/or field2 */
+ bool left_copyfl, right_copyfl;
+ Item_equal *left_item_equal=
+ find_item_equal(cond_equal, left_field, &left_copyfl);
+ Item_equal *right_item_equal=
+ find_item_equal(cond_equal, right_field, &right_copyfl);
+
+ if (left_item_equal && left_item_equal == right_item_equal)
+ {
+ /*
+ The equality predicate is inference of one of the existing
+ multiple equalities, i.e the condition is already covered
+ by upper level equalities
+ */
+ return TRUE;
+ }
+
+ /* 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
+ {
+ /* Merge two multiple equalities forming a new one */
+ left_item_equal->merge(right_item_equal);
+ /* Remove the merged multiple equality from the list */
+ List_iterator<Item_equal> li(cond_equal->current_level);
+ while ((li++) != right_item_equal);
+ li.remove();
+ }
+ }
+ 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
+ {
+ /* 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);
+ }
+ }
+ return TRUE;
+ }
+
+ {
+ /* The predicate of the form field=const/const=field is processed */
+ Item *const_item= 0;
+ Item_field *field_item= 0;
+ if (left_item->type() == Item::FIELD_ITEM &&
+ right_item->const_item())
+ {
+ field_item= (Item_field*) left_item;
+ const_item= right_item;
+ }
+ else if (right_item->type() == Item::FIELD_ITEM &&
+ left_item->const_item())
+ {
+ field_item= (Item_field*) right_item;
+ const_item= left_item;
+ }
+ if (const_item &&
+ field_item->result_type() == const_item->result_type())
+ {
+ bool copyfl;
+
+ if (field_item->result_type() == STRING_RESULT &&
+ ((Field_str *) field_item)->charset() !=
+ ((Item_cond *) item)->compare_collation())
+ return FALSE;
+
+ Item_equal *item_equal = find_item_equal(cond_equal,
+ field_item->field, &copyfl);
+ if (copyfl)
+ {
+ item_equal= new Item_equal(item_equal);
+ cond_equal->current_level.push_back(item_equal);
+ }
+ if (item_equal)
+ {
+ /*
+ The flag cond_false will be set to 1 after this, if item_equal
+ already contains a constant and its value is not equal to
+ the value of const_item.
+ */
+ item_equal->add(const_item);
+ }
+ else
+ {
+ item_equal= new Item_equal(const_item, field_item);
+ cond_equal->current_level.push_back(item_equal);
+ }
+ return TRUE;
+ }
+ }
+ }
+ return FALSE;
+}
+
+/*
+ Replace all equality predicates in a condition by multiple equality items
+
+ SYNOPSIS
+ build_all_equal_items()
+ cond condition(expression) where to make replacement
+ inherited path to all inherited multiple equality items
+
+ DESCRIPTION
+ At each 'and' level the function detects items for equality predicates
+ and replaced them by a set of multiple equality items of class Item_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.
+ 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.
+ 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
+ f1=f2, .., fn-1=fn. It substitutes any inference from these
+ 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 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
+ (=(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)
+
+ IMPLEMENTATION
+ The function performs the substitution in a recursive descent by
+ the condtion tree, passing to the next AND level a chain of multiple
+ equality predicates which have been built at the upper levels.
+ The Item_equal items built at the level are attached to other
+ non-equality conjucts as a sublist. The pointer to the inherited
+ 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
+*/
+
+static COND *build_all_equal_items(COND *cond,
+ COND_EQUAL *inherited)
+{
+ Item_equal *item_equal;
+ uint members;
+ COND_EQUAL cond_equal;
+ cond_equal.upper_levels= inherited;
+
+ if (cond->type() == Item::COND_ITEM)
+ {
+ bool and_level= ((Item_cond*) cond)->functype() ==
+ Item_func::COND_AND_FUNC;
+ List<Item> *args= ((Item_cond*) cond)->argument_list();
+
+ List_iterator<Item> li(*args);
+ Item *item;
+
+ if (and_level)
+ {
+ /*
+ 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 having
+ found/created a multiple equality whose inference the predicate is.
+ */
+ while ((item= li++))
+ {
+ if (check_equality(item, &cond_equal))
+ li.remove();
+ }
+
+ List_iterator_fast<Item_equal> it(cond_equal.current_level);
+ 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)
+ {
+ 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);
+ }
+ /*
+ Make replacement of equality predicates for lower levels
+ of the condition expression.
+ */
+ 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 */
+ li.replace(new_item);
+ }
+ }
+ if (and_level)
+ args->concat((List<Item> *)&cond_equal.current_level);
+ }
+ else if (cond->type() == Item::FUNC_ITEM)
+ {
+ /*
+ 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_length_and_dec();
+ item_equal->update_used_tables();
+ return item_equal;
+ }
+ /*
+ 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
+
+ SYNOPSIS
+ eliminate_item_equal()
+ cond condition to add the generated equality to
+ upper_levels structure to access multiple equality of upper levels
+ item_equal multiple equality to generate simple equality from
+
+ DESCRIPTION
+ The function retrieves the fields of the multiple equality item
+ item_equal and for each field f:
+ - if item_equal contains const it generates the equality f=const_item;
+ - otherwise, if f is not the first field, generates the equality
+ f=item_equal->get_first().
+ All generated equality are added to the cond conjunction.
+
+ 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, if success.
+ 0, otherwise.
+*/
+
+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;
+ if (item_const)
+ head= item_const;
+ else
+ {
+ head= item_equal->get_first();
+ it++;
+ }
+ Item_field *item_field;
+ while ((item_field= it++))
+ {
+ Item_equal *upper= item_field->find_item_equal(upper_levels);
+ Item_field *item= item_field;
+ if (upper)
+ {
+ if (item_const && upper->get_const())
+ item= 0;
+ else
+ {
+ Item_equal_iterator li(*item_equal);
+ while ((item= li++) != item_field)
+ {
+ if (item->find_item_equal(upper_levels) == upper)
+ break;
+ }
+ }
+ }
+ if (item == item_field)
+ {
+ 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= new Item_cond_and(eq_list);
+ else
+ ((Item_cond *) cond)->add_at_head(&eq_list);
+
+ return cond;
+}
+
+
+/*
+ Substitute every field reference in a condition by the best equal field
+ and eliminate all multiplle equality predicates
+
+ SYNOPSIS
+ substitute_for_best_equal_field()
+ cond condition to process
+ cond_equal multiple equalities to take into consideration
+ table_join_idx index to tables determining field preference
+
+ DESCRIPTION
+ The function retrieves the cond condition and for each encountered
+ multiple equality predicate it sorts the field references in it
+ according to the order of tables specified by the table_join_idx
+ parameter. Then it eliminates the multiple equality predicate it
+ replacing it by the conjunction of simple equality predicates
+ equating every field from the multiple equality to the first
+ field in it, or to the constant, if there is any.
+ After this the function retrieves all other conjuncted
+ predicates substitute every field reference by the field reference
+ to the first equal field or equal constant if there are any.
+
+ NOTES
+ At the first glance full sort of fields in multiple equality
+ seems to be an overkill. Yet it's not the case due to possible
+ new fields in multiple equality item of lower levels. We want
+ the order in them to comply with the order of upper levels.
+
+ RETURN
+ The transformed condition
+*/
+
+static COND* substitute_for_best_equal_field(COND *cond,
+ COND_EQUAL *cond_equal,
+ void *table_join_idx)
+{
+ Item_equal *item_equal;
+
+ if (cond->type() == Item::COND_ITEM)
+ {
+ List<Item> *cond_list= ((Item_cond*) cond)->argument_list();
+
+ bool and_level= ((Item_cond*) cond)->functype() ==
+ Item_func::COND_AND_FUNC;
+ if (and_level)
+ {
+ cond_equal= &((Item_cond_and *) cond)->cond_equal;
+ cond_list->disjoin((List<Item> *) &cond_equal->current_level);
+
+ List_iterator_fast<Item_equal> it(cond_equal->current_level);
+ while ((item_equal= it++))
+ {
+ item_equal->sort(&compare_fields_by_table_order, table_join_idx);
+ }
+ }
+
+ List_iterator<Item> li(*cond_list);
+ Item *item;
+ while ((item= li++))
+ {
+ Item *new_item =substitute_for_best_equal_field(item, cond_equal,
+ table_join_idx);
+ if (new_item != item)
+ li.replace(new_item);
+ }
+
+ if (and_level)
+ {
+ List_iterator_fast<Item_equal> it(cond_equal->current_level);
+ while ((item_equal= it++))
+ {
+ eliminate_item_equal(cond, cond_equal->upper_levels, item_equal);
+ }
+ }
+ }
+ else if (cond->type() == Item::FUNC_ITEM &&
+ ((Item_cond*) cond)->functype() == Item_func::MULT_EQUAL_FUNC)
+ {
+ item_equal= (Item_equal *) cond;
+ 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);
+ }
+ else
+ cond->walk(&Item::replace_equal_field_processor, 0);
+ return cond;
+}
+
+
/*
change field = field to field = const for each found field = const in the
and_level
@@ -6164,15 +6997,13 @@ simplify_joins(JOIN *join, List<TABLE_LIST> *join_list, COND *conds, bool top)
li.replace(nested_join->join_list);
}
}
- DBUG_RETURN(conds);
-}
-
-
+ DBUG_RETURN(conds);
+
static COND *
optimize_cond(JOIN *join, COND *conds, Item::cond_result *cond_value)
{
THD *thd= join->thd;
- SELECT_LEX *select= thd->lex->current_select;
+ SELECT_LEX *select= thd->lex->current_select;}
DBUG_ENTER("optimize_cond");
if (select->first_cond_optimization)
@@ -6216,7 +7047,6 @@ optimize_cond(JOIN *join, COND *conds, Item::cond_result *cond_value)
DBUG_EXECUTE("where",print_where(conds,"after const change"););
conds= remove_eq_conds(thd, conds, cond_value) ;
DBUG_EXECUTE("info",print_where(conds,"after remove"););
- }
DBUG_RETURN(conds);
}
@@ -6340,6 +7170,11 @@ remove_eq_conds(THD *thd, COND *cond, Item::cond_result *cond_value)
}
}
}
+ if (cond->const_item())
+ {
+ *cond_value= eval_const_cond(cond) ? Item::COND_TRUE : Item::COND_FALSE;
+ return (COND*) 0;
+ }
}
else if (cond->const_item())
{
@@ -9843,6 +10678,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 */
diff --git a/sql/sql_select.h b/sql/sql_select.h
index eb80f3ee608..c9cfeb70225 100644
--- a/sql/sql_select.h
+++ b/sql/sql_select.h
@@ -222,6 +222,7 @@ class JOIN :public Sql_alloc
Item *conds_history; // store WHERE for explain
TABLE_LIST *tables_list; //hold 'tables' parameter of mysql_select
List<TABLE_LIST> *join_list; // list of joined tables in reverse order
+ COND_EQUAL *cond_equal;
SQL_SELECT *select; //created in optimisation phase
JOIN_TAB *return_tab; //used only for outer joins
Item **ref_pointer_array; //used pointer reference for this select
@@ -284,6 +285,7 @@ class JOIN :public Sql_alloc
ref_pointer_array_size= 0;
zero_result_cause= 0;
optimized= 0;
+ cond_equal= 0;
fields_list= fields_arg;
bzero((char*) &keyuse,sizeof(keyuse));
View Lorry Controller Status