At file:///home/psergey/dev/maria-5.3-subqueries-r7/
------------------------------------------------------------
revno: 2774
revision-id: psergey@askmonty.org-20100313200452-kq4dxayp7b45zum1
parent: psergey@askmonty.org-20100307154145-ksby2b1l0sqm1xne
committer: Sergey Petrunya
branch nick: maria-5.3-subqueries-r7
timestamp: Sat 2010-03-13 23:04:52 +0300
message:
BUG#45174: XOR in subqueries produces differing results in 5.1 and 5.4
BUG#50019: Wrong result for IN-subquery with materialization
- Fix equality substitution in presense of semi-join materialization, lookup and scan variants
(started off from fix by Evgen Potemkin, then modified it to work in all cases)
=== modified file 'mysql-test/r/subselect_mat.result'
--- a/mysql-test/r/subselect_mat.result 2010-01-17 14:51:10 +0000
+++ b/mysql-test/r/subselect_mat.result 2010-03-13 20:04:52 +0000
@@ -1219,3 +1219,28 @@
pk
2
DROP TABLE t1, t2;
+#
+# BUG#50019: Wrong result for IN-subquery with materialization
+#
+create table t1(i int);
+insert into t1 values (1), (2), (3), (4), (5), (6), (7), (8), (9), (10);
+create table t2(i int);
+insert into t2 values (1), (2), (3), (4), (5), (6), (7), (8), (9), (10);
+create table t3(i int);
+insert into t3 values (1), (2), (3), (4), (5), (6), (7), (8), (9), (10);
+select * from t1 where t1.i in (select t2.i from t2 join t3 where t2.i + t3.i = 5);
+i
+1
+2
+3
+4
+set @save_optimizer_switch=@@optimizer_switch;
+set session optimizer_switch='materialization=off';
+select * from t1 where t1.i in (select t2.i from t2 join t3 where t2.i + t3.i = 5);
+i
+1
+2
+3
+4
+set session optimizer_switch=@save_optimizer_switch;
+drop table t1, t2, t3;
=== modified file 'mysql-test/r/subselect_sj.result'
--- a/mysql-test/r/subselect_sj.result 2010-02-24 11:33:42 +0000
+++ b/mysql-test/r/subselect_sj.result 2010-03-13 20:04:52 +0000
@@ -871,3 +871,39 @@
DROP TABLE t1, t2, t3;
DROP VIEW v2, v3;
# End of Bug#49198
+#
+# Bug#45174: Incorrectly applied equality propagation caused wrong
+# result on a query with a materialized semi-join.
+#
+CREATE TABLE `t1` (
+`pk` int(11) NOT NULL AUTO_INCREMENT,
+`varchar_key` varchar(1) NOT NULL,
+`varchar_nokey` varchar(1) NOT NULL,
+PRIMARY KEY (`pk`),
+KEY `varchar_key` (`varchar_key`)
+);
+INSERT INTO `t1` VALUES (11,'m','m'),(12,'j','j'),(13,'z','z'),(14,'a','a'),(15,'',''),(16,'e','e'),(17,'t','t'),(19,'b','b'),(20,'w','w'),(21,'m','m'),(23,'',''),(24,'w','w'),(26,'e','e'),(27,'e','e'),(28,'p','p');
+CREATE TABLE `t2` (
+`varchar_nokey` varchar(1) NOT NULL
+);
+INSERT INTO `t2` VALUES ('v'),('u'),('n'),('l'),('h'),('u'),('n'),('j'),('k'),('e'),('i'),('u'),('n'),('b'),('x'),(''),('q'),('u');
+EXPLAIN EXTENDED SELECT varchar_nokey
+FROM t2
+WHERE ( `varchar_nokey` , `varchar_nokey` ) IN (
+SELECT `varchar_key` , `varchar_nokey`
+FROM t1
+WHERE `varchar_nokey` < 'n' XOR `pk` ) ;
+id select_type table type possible_keys key key_len ref rows filtered Extra
+1 PRIMARY t2 ALL NULL NULL NULL NULL 18 100.00
+1 PRIMARY t1 ALL varchar_key NULL NULL NULL 15 100.00 Using where; Materialize
+Warnings:
+Note 1003 select `test`.`t2`.`varchar_nokey` AS `varchar_nokey` from `test`.`t2` semi join (`test`.`t1`) where ((`test`.`t1`.`varchar_nokey` = `test`.`t1`.`varchar_key`) and ((`test`.`t1`.`varchar_nokey` < 'n') xor `test`.`t1`.`pk`))
+SELECT varchar_nokey
+FROM t2
+WHERE ( `varchar_nokey` , `varchar_nokey` ) IN (
+SELECT `varchar_key` , `varchar_nokey`
+FROM t1
+WHERE `varchar_nokey` < 'n' XOR `pk` ) ;
+varchar_nokey
+DROP TABLE t1, t2;
+# End of the test for bug#45174.
=== modified file 'mysql-test/r/subselect_sj_jcl6.result'
--- a/mysql-test/r/subselect_sj_jcl6.result 2010-03-07 15:41:45 +0000
+++ b/mysql-test/r/subselect_sj_jcl6.result 2010-03-13 20:04:52 +0000
@@ -876,6 +876,42 @@
DROP VIEW v2, v3;
# End of Bug#49198
#
+# Bug#45174: Incorrectly applied equality propagation caused wrong
+# result on a query with a materialized semi-join.
+#
+CREATE TABLE `t1` (
+`pk` int(11) NOT NULL AUTO_INCREMENT,
+`varchar_key` varchar(1) NOT NULL,
+`varchar_nokey` varchar(1) NOT NULL,
+PRIMARY KEY (`pk`),
+KEY `varchar_key` (`varchar_key`)
+);
+INSERT INTO `t1` VALUES (11,'m','m'),(12,'j','j'),(13,'z','z'),(14,'a','a'),(15,'',''),(16,'e','e'),(17,'t','t'),(19,'b','b'),(20,'w','w'),(21,'m','m'),(23,'',''),(24,'w','w'),(26,'e','e'),(27,'e','e'),(28,'p','p');
+CREATE TABLE `t2` (
+`varchar_nokey` varchar(1) NOT NULL
+);
+INSERT INTO `t2` VALUES ('v'),('u'),('n'),('l'),('h'),('u'),('n'),('j'),('k'),('e'),('i'),('u'),('n'),('b'),('x'),(''),('q'),('u');
+EXPLAIN EXTENDED SELECT varchar_nokey
+FROM t2
+WHERE ( `varchar_nokey` , `varchar_nokey` ) IN (
+SELECT `varchar_key` , `varchar_nokey`
+FROM t1
+WHERE `varchar_nokey` < 'n' XOR `pk` ) ;
+id select_type table type possible_keys key key_len ref rows filtered Extra
+1 PRIMARY t2 ALL NULL NULL NULL NULL 18 100.00
+1 PRIMARY t1 ALL varchar_key NULL NULL NULL 15 100.00 Using where; Materialize
+Warnings:
+Note 1003 select `test`.`t2`.`varchar_nokey` AS `varchar_nokey` from `test`.`t2` semi join (`test`.`t1`) where ((`test`.`t1`.`varchar_nokey` = `test`.`t1`.`varchar_key`) and ((`test`.`t1`.`varchar_nokey` < 'n') xor `test`.`t1`.`pk`))
+SELECT varchar_nokey
+FROM t2
+WHERE ( `varchar_nokey` , `varchar_nokey` ) IN (
+SELECT `varchar_key` , `varchar_nokey`
+FROM t1
+WHERE `varchar_nokey` < 'n' XOR `pk` ) ;
+varchar_nokey
+DROP TABLE t1, t2;
+# End of the test for bug#45174.
+#
# BUG#49129: Wrong result with IN-subquery with join_cache_level=6 and firstmatch=off
#
CREATE TABLE t0 (a INT);
=== modified file 'mysql-test/t/subselect_mat.test'
--- a/mysql-test/t/subselect_mat.test 2010-01-17 14:51:10 +0000
+++ b/mysql-test/t/subselect_mat.test 2010-03-13 20:04:52 +0000
@@ -889,3 +889,19 @@
SELECT pk FROM t1 WHERE (b,c,d) IN (SELECT b,c,d FROM t2 WHERE pk > 0);
DROP TABLE t1, t2;
+--echo #
+--echo # BUG#50019: Wrong result for IN-subquery with materialization
+--echo #
+create table t1(i int);
+insert into t1 values (1), (2), (3), (4), (5), (6), (7), (8), (9), (10);
+create table t2(i int);
+insert into t2 values (1), (2), (3), (4), (5), (6), (7), (8), (9), (10);
+create table t3(i int);
+insert into t3 values (1), (2), (3), (4), (5), (6), (7), (8), (9), (10);
+select * from t1 where t1.i in (select t2.i from t2 join t3 where t2.i + t3.i = 5);
+set @save_optimizer_switch=@@optimizer_switch;
+set session optimizer_switch='materialization=off';
+select * from t1 where t1.i in (select t2.i from t2 join t3 where t2.i + t3.i = 5);
+set session optimizer_switch=@save_optimizer_switch;
+drop table t1, t2, t3;
+
=== modified file 'mysql-test/t/subselect_sj.test'
--- a/mysql-test/t/subselect_sj.test 2010-02-24 11:33:42 +0000
+++ b/mysql-test/t/subselect_sj.test 2010-03-13 20:04:52 +0000
@@ -770,3 +770,42 @@
DROP VIEW v2, v3;
--echo # End of Bug#49198
+
+--echo #
+--echo # Bug#45174: Incorrectly applied equality propagation caused wrong
+--echo # result on a query with a materialized semi-join.
+--echo #
+
+CREATE TABLE `t1` (
+ `pk` int(11) NOT NULL AUTO_INCREMENT,
+ `varchar_key` varchar(1) NOT NULL,
+ `varchar_nokey` varchar(1) NOT NULL,
+ PRIMARY KEY (`pk`),
+ KEY `varchar_key` (`varchar_key`)
+);
+
+INSERT INTO `t1` VALUES (11,'m','m'),(12,'j','j'),(13,'z','z'),(14,'a','a'),(15,'',''),(16,'e','e'),(17,'t','t'),(19,'b','b'),(20,'w','w'),(21,'m','m'),(23,'',''),(24,'w','w'),(26,'e','e'),(27,'e','e'),(28,'p','p');
+
+CREATE TABLE `t2` (
+ `varchar_nokey` varchar(1) NOT NULL
+);
+
+INSERT INTO `t2` VALUES ('v'),('u'),('n'),('l'),('h'),('u'),('n'),('j'),('k'),('e'),('i'),('u'),('n'),('b'),('x'),(''),('q'),('u');
+
+EXPLAIN EXTENDED SELECT varchar_nokey
+FROM t2
+WHERE ( `varchar_nokey` , `varchar_nokey` ) IN (
+SELECT `varchar_key` , `varchar_nokey`
+FROM t1
+WHERE `varchar_nokey` < 'n' XOR `pk` ) ;
+
+SELECT varchar_nokey
+FROM t2
+WHERE ( `varchar_nokey` , `varchar_nokey` ) IN (
+SELECT `varchar_key` , `varchar_nokey`
+FROM t1
+WHERE `varchar_nokey` < 'n' XOR `pk` ) ;
+
+DROP TABLE t1, t2;
+
+--echo # End of the test for bug#45174.
=== modified file 'sql/item.cc'
--- a/sql/item.cc 2010-02-24 11:33:42 +0000
+++ b/sql/item.cc 2010-03-13 20:04:52 +0000
@@ -4761,7 +4761,7 @@
return this;
return const_item;
}
- Item_field *subst= item_equal->get_first();
+ Item_field *subst= item_equal->get_first(this);
if (subst && field->table != subst->field->table && !field->eq(subst->field))
return subst;
}
=== modified file 'sql/item_cmpfunc.cc'
--- a/sql/item_cmpfunc.cc 2010-02-17 10:05:27 +0000
+++ b/sql/item_cmpfunc.cc 2010-03-13 20:04:52 +0000
@@ -5369,7 +5369,7 @@
void Item_equal::fix_length_and_dec()
{
- Item *item= get_first();
+ Item *item= get_first(NULL);
eval_item= cmp_item::get_comparator(item->result_type(),
item->collation.collation);
}
@@ -5432,3 +5432,128 @@
str->append(')');
}
+
+/*
+ @brief Get the first equal field of multiple equality.
+ @param[in] field the field to get equal field to
+
+ @details Get the first field of multiple equality that is equal to the
+ given field. In order to make semi-join materialization strategy work
+ correctly we can't propagate equal fields from upper select to a
+ materialized semi-join.
+ Thus the fields is returned according to following rules:
+
+ 1) If the given field belongs to a semi-join then the first field in
+ multiple equality which belong to the same semi-join is returned.
+ Otherwise NULL is returned.
+ 2) If the given field doesn't belong to a semi-join then
+ the first field in the multiple equality that doesn't belong to any
+ semi-join is returned.
+ If all fields in the equality are belong to semi-join(s) then NULL
+ is returned.
+ 3) If no field is given then the first field in the multiple equality
+ is returned without regarding whether it belongs to a semi-join or not.
+
+ @retval Found first field in the multiple equality.
+ @retval 0 if no field found.
+*/
+
+Item_field* Item_equal::get_first(Item_field *field)
+{
+ List_iterator it(fields);
+ Item_field *item;
+ JOIN_TAB *field_tab;
+
+ if (!field)
+ return fields.head();
+
+ /*
+ Of all equal fields, return the first one we can use. Normally, this is the
+ field which belongs to the table that is the first in the join order.
+
+ There is one exception to this: When semi-join materialization strategy is
+ used, and the given field belongs to a table within the semi-join nest, we
+ must pick the first field in the semi-join nest.
+
+ Example: suppose we have a join order:
+
+ ot1 ot2 SJ-Mat(it1 it2 it3) ot3
+
+ and equality ot2.col = it1.col = it2.col
+ If we're looking for best substitute for 'it2.col', we should pick it1.col
+ and not ot2.col.
+
+ eliminate_item_equal() also has code that deals with equality substitution
+ in presense of SJM nests.
+ */
+
+ field_tab= field->field->table->reginfo.join_tab;
+
+ TABLE_LIST *emb_nest= field->field->table->pos_in_table_list->embedding;
+
+ if (emb_nest && emb_nest->sj_mat_info && emb_nest->sj_mat_info->is_used)
+ {
+ /*
+ It's a field from an materialized semi-join. We can substitute it only
+ for a field from the same semi-join.
+ */
+ JOIN_TAB *first;
+ JOIN *join= field_tab->join;
+ uint tab_idx= field_tab - field_tab->join->join_tab;
+
+ /* Find the first table of this semi-join nest */
+ for (uint i= tab_idx; i != join->const_tables; i--)
+ {
+ if (join->join_tab[i].table->map & emb_nest->sj_inner_tables)
+ first= join->join_tab + i;
+ else
+ // Found first tab that doesn't belong to current SJ.
+ break;
+ }
+ /* Find an item to substitute for. */
+ while ((item= it++))
+ {
+ if (item->field->table->reginfo.join_tab >= first)
+ {
+ /*
+ If we found given field then return NULL to avoid unnecessary
+ substitution.
+ */
+ return (item != field) ? item : NULL;
+ }
+ }
+ }
+ else
+ {
+#if 0
+ /*
+ The field is not in SJ-Materialization nest. We must return the first
+ field that's not embedded in a SJ-Materialization nest.
+ Example: suppose we have a join order:
+
+ SJ-Mat(it1 it2) ot1 ot2
+
+ and equality ot2.col = ot1.col = it2.col
+ If we're looking for best substitute for 'ot2.col', we should pick ot1.col
+ and not it2.col, because when we run a join between ot1 and ot2
+ execution of SJ-Mat(...) has already finished and we can't rely on the
+ value of it*.*.
+ psergey-fix-fix: ^^ THAT IS INCORRECT ^^. Pick the first, whatever that
+ is.
+ */
+ while ((item= it++))
+ {
+ TABLE_LIST *emb_nest= item->field->table->pos_in_table_list->embedding;
+ if (!emb_nest || !emb_nest->sj_mat_info ||
+ !emb_nest->sj_mat_info->is_used)
+ {
+ return item;
+ }
+ }
+#endif
+ return fields.head();
+ }
+ // Shouldn't get here.
+ DBUG_ASSERT(0);
+ return NULL;
+}
=== modified file 'sql/item_cmpfunc.h'
--- a/sql/item_cmpfunc.h 2010-02-17 10:05:27 +0000
+++ b/sql/item_cmpfunc.h 2010-03-13 20:04:52 +0000
@@ -1589,7 +1589,7 @@
void add(Item_field *f);
uint members();
bool contains(Field *field);
- Item_field* get_first() { return fields.head(); }
+ Item_field* get_first(Item_field *field);
uint n_fields() { return fields.elements; }
void merge(Item_equal *item);
void update_const();
=== modified file 'sql/opt_subselect.cc'
--- a/sql/opt_subselect.cc 2010-03-07 15:41:45 +0000
+++ b/sql/opt_subselect.cc 2010-03-13 20:04:52 +0000
@@ -2159,6 +2159,8 @@
if (tablenr != first)
pos->sj_strategy= SJ_OPT_NONE;
remaining_tables |= s->table->map;
+ //s->sj_strategy= pos->sj_strategy;
+ join->join_tab[first].sj_strategy= join->best_positions[first].sj_strategy;
}
}
=== modified file 'sql/sql_select.cc'
--- a/sql/sql_select.cc 2010-03-07 15:41:45 +0000
+++ b/sql/sql_select.cc 2010-03-13 20:04:52 +0000
@@ -8867,6 +8867,15 @@
}
+static TABLE_LIST* embedding_sjm(Item_field *item_field)
+{
+ TABLE_LIST *nest= item_field->field->table->pos_in_table_list->embedding;
+ if (nest && nest->sj_mat_info && nest->sj_mat_info->is_used)
+ return nest;
+ else
+ return NULL;
+}
+
/**
Generate minimal set of simple equalities equivalent to a multiple equality.
@@ -8900,6 +8909,23 @@
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.
+
+ Equality substutution and semi-join materialization nests:
+
+ In case join order looks like this:
+
+ outer_tbl1 outer_tbl2 SJM (inner_tbl1 inner_tbl2) outer_tbl3
+
+ We must not construct equalities like
+
+ outer_tbl1.col = inner_tbl1.col
+
+ because they would get attached to inner_tbl1 and will get evaluated
+ during materialization phase, when we don't have current value of
+ outer_tbl1.col.
+
+ Item_equal::get_first() also takes similar measures for dealing with
+ equality substitution in presense of SJM nests.
@return
- The condition with generated simple equalities or
@@ -8917,18 +8943,44 @@
Item *item_const= item_equal->get_const();
Item_equal_iterator it(*item_equal);
Item *head;
+ TABLE_LIST *current_sjm= NULL;
+ Item *current_sjm_head= NULL;
+
+ /*
+ Pick the "head" item: the constant one or the first in the join order
+ that's not inside some SJM nest.
+ */
if (item_const)
head= item_const;
else
{
- head= item_equal->get_first();
+ TABLE_LIST *emb_nest;
+ Item_field *item_field;
+ head= item_field= item_equal->get_first(NULL);
it++;
+ if ((emb_nest= embedding_sjm(item_field)))
+ {
+ current_sjm= emb_nest;
+ current_sjm_head= head;
+ }
}
+
Item_field *item_field;
+ /*
+ For each other item, generate "item=head" equality (except the tables that
+ are within SJ-Materialization nests, for those "head" is defined
+ differently)
+ */
while ((item_field= it++))
{
Item_equal *upper= item_field->find_item_equal(upper_levels);
Item_field *item= item_field;
+ TABLE_LIST *field_sjm= embedding_sjm(item_field);
+
+ /*
+ Check if "item_field=head" equality is already guaranteed to be true
+ on upper AND-levels.
+ */
if (upper)
{
if (item_const && upper->get_const())
@@ -8943,65 +8995,29 @@
}
}
}
- if (item == item_field)
+
+ bool produce_equality= test(item == item_field);
+ if (!item_const && field_sjm && field_sjm != current_sjm)
+ {
+ /* Entering an SJM nest */
+ current_sjm_head= item_field;
+ if (!field_sjm->sj_mat_info->is_sj_scan)
+ produce_equality= FALSE;
+ }
+
+ if (produce_equality)
{
if (eq_item)
eq_list.push_back(eq_item);
- /*
- item_field might refer to a table that is within a semi-join
- materialization nest. In that case, the join order looks like this:
-
- outer_tbl1 outer_tbl2 SJM (inner_tbl1 inner_tbl2) outer_tbl3
-
- We must not construct equalities like
-
- outer_tbl1.col = inner_tbl1.col
-
- because they would get attached to inner_tbl1 and will get evaluated
- during materialization phase, when we don't have current value of
- outer_tbl1.col.
- */
- TABLE_LIST *emb_nest=
- item_field->field->table->pos_in_table_list->embedding;
- if (!item_const && emb_nest && emb_nest->sj_mat_info &&
- emb_nest->sj_mat_info->is_used)
- {
- /*
- Find the first equal expression that refers to a table that is
- within the semijoin nest. If we can't find it, do nothing
- */
- List_iterator fit(item_equal->fields);
- Item_field *head_in_sjm;
- bool found= FALSE;
- while ((head_in_sjm= fit++))
- {
- if (head_in_sjm->used_tables() & emb_nest->sj_inner_tables)
- {
- if (head_in_sjm == item_field)
- {
- /* This is the first table inside the semi-join*/
- eq_item= new Item_func_eq(item_field, head);
- /* Tell make_cond_for_table don't use this. */
- eq_item->marker=3;
- }
- else
- {
- eq_item= new Item_func_eq(item_field, head_in_sjm);
- found= TRUE;
- }
- break;
- }
- }
- if (!found)
- continue;
- }
- else
- eq_item= new Item_func_eq(item_field, head);
+
+ eq_item= new Item_func_eq(item_field, current_sjm? current_sjm_head: head);
+
if (!eq_item)
return 0;
eq_item->set_cmp_func();
eq_item->quick_fix_field();
}
+ current_sjm= field_sjm;
}
if (!cond && !eq_list.head())
=== modified file 'sql/sql_select.h'
--- a/sql/sql_select.h 2010-03-05 18:54:48 +0000
+++ b/sql/sql_select.h 2010-03-13 20:04:52 +0000
@@ -279,6 +279,13 @@
/* NestedOuterJoins: Bitmap of nested joins this table is part of */
nested_join_map embedding_map;
+ /*
+ Semi-join strategy to be used for this join table. This is a copy of
+ POSITION::sj_strategy field. This field is set up by the
+ fix_semijion_strategies_for_picked_join_order.
+ */
+ uint sj_strategy;
+
void cleanup();
inline bool is_using_loose_index_scan()
{
