#At file:///work/bzrroot/45174-bug-azalea/ based on revid:alik@stripped
2814 Evgeny Potemkin 2009-10-13
Bug#45174: Incorrectly applied equality propagation caused wrong result
on a query with a materialized semi-join.
When a subquery is a subject to a semi-join optimization its tables are
merged to the upper query and later they treated as usual tables.
This allows a bunch of optimizations to be applied, equality
propagation is among them. Equality propagation is done after query execution
plan is chosen. It substitutes fields from tables being retrieved later for
fields from tables being retrieved earlier. However it can't be applied as is
to any semi-join table.
The semi-join materialization strategy differs from other semi-join
strategies that the data from materialized semi-join tables isn't used
directly but saved to a temporary table first. The materialization isn't
isolated is a separate step, it is done inline within the nested loop execution.
When it comes to fetch rows from the first table in
the block of materialized semi-join tables they are isolated and the
sub_select function is called to materialize result and save it in the
semi-join result table. Materialization is done once and later data from the
semi-join result table is used.
Due to this we can't substitute fields that belong to the semi-join
for fields from outer query and vice versa.
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.
For a field that is not in a materialized semi-join we must pick a field
that's not embedded in a materialized semi-join.
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*.*.
Now the Item_equal::get_first function accepts as a parameter a field being
substituted and checks whether it belongs to a materialized semi-join.
Depending on the check result a field to substitute for or NULL is returned.
The sj_strategy field is added to the st_join_table structure. It's a copy of the
POSITION::sj_strategy field and is used to easy checks.
@ mysql-test/r/subselect_sj.result
A test case added for the bug#45174.
@ mysql-test/r/subselect_sj_jcl6.result
A test case added for the bug#45174.
@ mysql-test/t/subselect_sj.test
A test case added for the bug#45174.
@ sql/item.cc
Bug#45174: Incorrectly applied equality propagation caused wrong result
on a query with a materialized semi-join.
Now the Item_equal::get_first function accepts as a parameter a field being
substituted.
@ sql/item_cmpfunc.cc
Bug#45174: Incorrectly applied equality propagation caused wrong result
on a query with a materialized semi-join.
Now the Item_equal::get_first function accepts a field being substituted and
checks whether it belongs to a materialized semi-join. Depending on the check
result a field to substitute for or NULL is returned.
@ sql/item_cmpfunc.h
Bug#45174: Incorrectly applied equality propagation caused wrong result
on a query with a materialized semi-join.
Now the Item_equal::get_first function accepts as a parameter a field being
substituted.
@ sql/sql_select.cc
Bug#45174: Incorrectly applied equality propagation caused wrong result
on a query with a materialized semi-join.
The is_sj_materialization_strategy method is added to the JOIN_TAB class to
check whether JOIN_TAB belongs to a materialized semi-join.
@ sql/sql_select.h
Bug#45174: Incorrectly applied equality propagation caused wrong result
on a query with a materialized semi-join.
The sj_strategy field is added to the st_join_table structure. It's a copy of the
POSITION::sj_strategy field and is used to easy checks.
modified:
mysql-test/r/subselect_sj.result
mysql-test/r/subselect_sj_jcl6.result
mysql-test/t/subselect_sj.test
sql/item.cc
sql/item_cmpfunc.cc
sql/item_cmpfunc.h
sql/sql_select.cc
sql/sql_select.h
=== modified file 'mysql-test/r/subselect_sj.result'
--- a/mysql-test/r/subselect_sj.result 2009-03-19 17:03:58 +0000
+++ b/mysql-test/r/subselect_sj.result 2009-10-13 09:38:46 +0000
@@ -327,3 +327,39 @@ AND OUTR . varchar_nokey <= 'w'
HAVING X > '2012-12-12';
X
drop table t1, t2;
+#
+# Bug#45174: Incorrectly applied equality propagation caused wrong
+# result on a query with a materialized semi-join.
+#
+CREATE TABLE `CC` (
+`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 `CC` 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 `C` (
+`varchar_nokey` varchar(1) NOT NULL
+);
+INSERT INTO `C` VALUES ('v'),('u'),('n'),('l'),('h'),('u'),('n'),('j'),('k'),('e'),('i'),('u'),('n'),('b'),('x'),(''),('q'),('u');
+EXPLAIN EXTENDED SELECT varchar_nokey
+FROM C
+WHERE ( `varchar_nokey` , `varchar_nokey` ) IN (
+SELECT `varchar_key` , `varchar_nokey`
+FROM CC
+WHERE `varchar_nokey` < 'n' XOR `pk` ) ;
+id select_type table type possible_keys key key_len ref rows filtered Extra
+1 PRIMARY C ALL NULL NULL NULL NULL 18 100.00
+1 PRIMARY CC ALL varchar_key NULL NULL NULL 15 100.00 Using where; Materialize
+Warnings:
+Note 1003 select `test`.`C`.`varchar_nokey` AS `varchar_nokey` from `test`.`C` semi join (`test`.`CC`) where ((`test`.`CC`.`varchar_key` = `test`.`C`.`varchar_nokey`) and (`test`.`CC`.`varchar_nokey` = `test`.`CC`.`varchar_key`) and ((`test`.`CC`.`varchar_nokey` < 'n') xor `test`.`CC`.`pk`))
+SELECT varchar_nokey
+FROM C
+WHERE ( `varchar_nokey` , `varchar_nokey` ) IN (
+SELECT `varchar_key` , `varchar_nokey`
+FROM CC
+WHERE `varchar_nokey` < 'n' XOR `pk` ) ;
+varchar_nokey
+DROP TABLE CC, C;
+# End of the test for bug#45174.
=== modified file 'mysql-test/r/subselect_sj_jcl6.result'
--- a/mysql-test/r/subselect_sj_jcl6.result 2009-03-19 17:03:58 +0000
+++ b/mysql-test/r/subselect_sj_jcl6.result 2009-10-13 09:38:46 +0000
@@ -331,6 +331,42 @@ AND OUTR . varchar_nokey <= 'w'
HAVING X > '2012-12-12';
X
drop table t1, t2;
+#
+# Bug#45174: Incorrectly applied equality propagation caused wrong
+# result on a query with a materialized semi-join.
+#
+CREATE TABLE `CC` (
+`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 `CC` 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 `C` (
+`varchar_nokey` varchar(1) NOT NULL
+);
+INSERT INTO `C` VALUES ('v'),('u'),('n'),('l'),('h'),('u'),('n'),('j'),('k'),('e'),('i'),('u'),('n'),('b'),('x'),(''),('q'),('u');
+EXPLAIN EXTENDED SELECT varchar_nokey
+FROM C
+WHERE ( `varchar_nokey` , `varchar_nokey` ) IN (
+SELECT `varchar_key` , `varchar_nokey`
+FROM CC
+WHERE `varchar_nokey` < 'n' XOR `pk` ) ;
+id select_type table type possible_keys key key_len ref rows filtered Extra
+1 PRIMARY C ALL NULL NULL NULL NULL 18 100.00
+1 PRIMARY CC ALL varchar_key NULL NULL NULL 15 100.00 Using where; Materialize
+Warnings:
+Note 1003 select `test`.`C`.`varchar_nokey` AS `varchar_nokey` from `test`.`C` semi join (`test`.`CC`) where ((`test`.`CC`.`varchar_key` = `test`.`C`.`varchar_nokey`) and (`test`.`CC`.`varchar_nokey` = `test`.`CC`.`varchar_key`) and ((`test`.`CC`.`varchar_nokey` < 'n') xor `test`.`CC`.`pk`))
+SELECT varchar_nokey
+FROM C
+WHERE ( `varchar_nokey` , `varchar_nokey` ) IN (
+SELECT `varchar_key` , `varchar_nokey`
+FROM CC
+WHERE `varchar_nokey` < 'n' XOR `pk` ) ;
+varchar_nokey
+DROP TABLE CC, C;
+# End of the test for bug#45174.
set join_cache_level=default;
show variables like 'join_cache_level';
Variable_name Value
=== modified file 'mysql-test/t/subselect_sj.test'
--- a/mysql-test/t/subselect_sj.test 2009-03-19 17:03:58 +0000
+++ b/mysql-test/t/subselect_sj.test 2009-10-13 09:38:46 +0000
@@ -216,4 +216,42 @@ WHERE
HAVING X > '2012-12-12';
drop table t1, t2;
+--echo #
+--echo # Bug#45174: Incorrectly applied equality propagation caused wrong
+--echo # result on a query with a materialized semi-join.
+--echo #
+
+CREATE TABLE `CC` (
+ `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 `CC` 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 `C` (
+ `varchar_nokey` varchar(1) NOT NULL
+);
+
+INSERT INTO `C` VALUES ('v'),('u'),('n'),('l'),('h'),('u'),('n'),('j'),('k'),('e'),('i'),('u'),('n'),('b'),('x'),(''),('q'),('u');
+
+EXPLAIN EXTENDED SELECT varchar_nokey
+FROM C
+WHERE ( `varchar_nokey` , `varchar_nokey` ) IN (
+SELECT `varchar_key` , `varchar_nokey`
+FROM CC
+WHERE `varchar_nokey` < 'n' XOR `pk` ) ;
+
+SELECT varchar_nokey
+FROM C
+WHERE ( `varchar_nokey` , `varchar_nokey` ) IN (
+SELECT `varchar_key` , `varchar_nokey`
+FROM CC
+WHERE `varchar_nokey` < 'n' XOR `pk` ) ;
+
+DROP TABLE CC, C;
+
+--echo # End of the test for bug#45174.
=== modified file 'sql/item.cc'
--- a/sql/item.cc 2009-06-09 16:53:34 +0000
+++ b/sql/item.cc 2009-10-13 09:38:46 +0000
@@ -4883,7 +4883,7 @@ Item *Item_field::replace_equal_field(uc
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 2009-06-09 16:53:34 +0000
+++ b/sql/item_cmpfunc.cc 2009-10-13 09:38:46 +0000
@@ -5376,7 +5376,7 @@ longlong Item_equal::val_int()
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);
}
@@ -5439,3 +5439,115 @@ void Item_equal::print(String *str, enum
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<Item_field> 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.
+ */
+
+ field_tab= field->field->table->reginfo.join_tab;
+ if (field_tab->sj_strategy == SJ_OPT_MATERIALIZE ||
+ field_tab->sj_strategy == SJ_OPT_MATERIALIZE_SCAN)
+ {
+ /*
+ 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 first table of this semi-join. */
+ for (int i=tab_idx; i >= join->const_tables; i--)
+ {
+ if (join->best_positions[i].sj_strategy == SJ_OPT_MATERIALIZE ||
+ join->best_positions[i].sj_strategy == SJ_OPT_MATERIALIZE_SCAN)
+ 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
+ {
+ /*
+ 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*.*.
+ */
+ while ((item= it++))
+ {
+ field_tab= item->field->table->reginfo.join_tab;
+ if (!(field_tab->sj_strategy == SJ_OPT_MATERIALIZE ||
+ field_tab->sj_strategy == SJ_OPT_MATERIALIZE_SCAN))
+ return item;
+ }
+ }
+ // Shouldn't get here.
+ DBUG_ASSERT(0);
+ return NULL;
+}
=== modified file 'sql/item_cmpfunc.h'
--- a/sql/item_cmpfunc.h 2009-01-26 16:03:39 +0000
+++ b/sql/item_cmpfunc.h 2009-10-13 09:38:46 +0000
@@ -1592,7 +1592,7 @@ public:
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);
void merge(Item_equal *item);
void update_const();
enum Functype functype() const { return MULT_EQUAL_FUNC; }
=== modified file 'sql/sql_select.cc'
--- a/sql/sql_select.cc 2009-06-30 08:03:05 +0000
+++ b/sql/sql_select.cc 2009-10-13 09:38:46 +0000
@@ -7911,6 +7911,7 @@ static void fix_semijoin_strategies_for_
if (tablenr != first)
pos->sj_strategy= SJ_OPT_NONE;
remaining_tables |= s->table->map;
+ s->sj_strategy= pos->sj_strategy;
}
}
@@ -11706,7 +11707,7 @@ Item *eliminate_item_equal(COND *cond, C
head= item_const;
else
{
- head= item_equal->get_first();
+ head= item_equal->get_first(NULL);
it++;
}
Item_field *item_field;
=== modified file 'sql/sql_select.h'
--- a/sql/sql_select.h 2009-05-07 20:48:24 +0000
+++ b/sql/sql_select.h 2009-10-13 09:38:46 +0000
@@ -274,6 +274,13 @@ typedef struct st_join_table
/* 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()
{
Attachment: [text/bzr-bundle] bzr/epotemkin@mysql.com-20091013093846-0633xigs7gnbgdt4.bundle
