| List: | Commits | « Previous MessageNext Message » | |
| From: | Roy Lyseng | Date: | January 5 2009 1:09pm |
| Subject: | bzr commit into mysql-6.0-exists2in branch (roy.lyseng:2726) WL#4389 | ||
| View as plain text | |||
#At file:///home/rl136806/mysql/repo/mysql-6.0-exists2in-work/ based on
revid:sergefp@stripped
2726 Roy Lyseng 2009-01-05
WL#4389 - Make EXISTS behave as IN
Added detection of trivial correlation.
EXISTS can be executed using materialization strategy
modified:
mysql-test/r/subselect_mat.result
mysql-test/r/subselect_systematic.result
mysql-test/t/subselect_systematic.test
sql/sql_select.cc
sql/table.h
per-file messages:
mysql-test/r/subselect_mat.result
Modified EXPLAIN result
mysql-test/r/subselect_systematic.result
Added new test output
mysql-test/t/subselect_systematic.test
Added new tests for subquery materialization
sql/sql_select.cc
JOIN::prepare - slight simplification of resolver actions
subquery_types_allow_materialization - eliminated expression resolution
decorrelate_subquery_search_cond - added routine that performs trivial decorrelation
of subqueries
convert_subq_to_sj - perform decorrelation if possible,
populate the sj_inner_exprs list with correlated expressions,
Uncorrelated EXISTS is extended with predicate "1=1", necessary
for materialization,
get_semi_join_select_list_index - modified to use sj_inner_exprs
make_join_select - changed comment
create_subq_equalities - renamed from create_subq_in_equalities
setup_sj_materialization - uses sj_outer_expr_list instead of IN subquery left_expr
make_cond_after_sjm - added routine comment
sql/table.h
Added list for subquery inner-expressions for semijoin - obsoletes subquery select
list for some uses
=== modified file 'mysql-test/r/subselect_mat.result'
--- a/mysql-test/r/subselect_mat.result 2008-11-26 14:36:11 +0000
+++ b/mysql-test/r/subselect_mat.result 2009-01-05 12:09:10 +0000
@@ -657,12 +657,12 @@ where t2.b2 = substring(t2_16.b2,1,6) an
t2.b1 IN (select c1 from t3 where c2 > '0')));
id select_type table type possible_keys key key_len ref rows filtered Extra
1 PRIMARY t1 ALL NULL NULL NULL NULL 3 100.00 Using where
-2 DEPENDENT SUBQUERY t1_16 ALL NULL NULL NULL NULL 3 100.00 Using where
+2 SUBQUERY t1_16 ALL NULL NULL NULL NULL 3 100.00 Using where
3 DEPENDENT SUBQUERY t2_16 ALL NULL NULL NULL NULL 3 100.00 Using where
3 DEPENDENT SUBQUERY t2 ALL NULL NULL NULL NULL 5 100.00 Using where; Using join buffer
4 SUBQUERY t3 ALL NULL NULL NULL NULL 4 100.00 Using where
Warnings:
-Note 1003 select `test`.`t1`.`a1` AS `a1`,`test`.`t1`.`a2` AS `a2` from `test`.`t1` where
<in_optimizer>(concat(`test`.`t1`.`a1`,'x'),<exists>(select 1 AS `Not_used`
from `test`.`t1_16` where
(<in_optimizer>((`test`.`t1_16`.`a1`,`test`.`t1_16`.`a2`),(`test`.`t1_16`.`a1`,`test`.`t1_16`.`a2`)
in (select `test`.`t2_16`.`b1` AS `b1`,`test`.`t2_16`.`b2` AS `b2` from `test`.`t2_16`
join `test`.`t2` where ((`test`.`t2`.`b2` = substr(`test`.`t2_16`.`b2`,1,6)) and
<in_optimizer>(`test`.`t2`.`b1`,`test`.`t2`.`b1` in ( <materialize> (select
`test`.`t3`.`c1` AS `c1` from `test`.`t3` where (`test`.`t3`.`c2` > '0') ),
<primary_index_lookup>(`test`.`t2`.`b1` in <temporary table> on distinct_key
where ((`test`.`t2`.`b1` = `materialized subselect`.`c1`))))) and
(<cache>(`test`.`t1_16`.`a1`) = `test`.`t2_16`.`b1`) and
(<cache>(`test`.`t1_16`.`a2`) = `test`.`t2_16`.`b2`)))) and
(<cache>(concat(`test`.`t1`.`a1`,'x')) = left(`test`.`t1_16`.`a1`,8)))))
+Note 1003 select `test`.`t1`.`a1` AS `a1`,`test`.`t1`.`a2` AS `a2` from `test`.`t1` where
<in_optimizer>(concat(`test`.`t1`.`a1`,'x'),concat(`test`.`t1`.`a1`,'x') in (
<materialize> (select left(`test`.`t1_16`.`a1`,8) AS `left(a1,8)` from
`test`.`t1_16` where
<in_optimizer>((`test`.`t1_16`.`a1`,`test`.`t1_16`.`a2`),(`test`.`t1_16`.`a1`,`test`.`t1_16`.`a2`)
in (select `test`.`t2_16`.`b1` AS `b1`,`test`.`t2_16`.`b2` AS `b2` from `test`.`t2_16`
join `test`.`t2` where ((`test`.`t2`.`b2` = substr(`test`.`t2_16`.`b2`,1,6)) and
<in_optimizer>(`test`.`t2`.`b1`,`test`.`t2`.`b1` in ( <materialize> (select
`test`.`t3`.`c1` AS `c1` from `test`.`t3` where (`test`.`t3`.`c2` > '0') ),
<primary_index_lookup>(`test`.`t2`.`b1` in <temporary table> on distinct_key
where ((`test`.`t2`.`b1` = `materialized subselect`.`c1`))))) and
(<cache>(`test`.`t1_16`.`a1`) = `test`.`t2_16`.`b1`) and
(<cache>(`test`.`t1_16`.`a2`) = `test`.`t2_16`.`b2`)))) ),
<primary_index_lookup>(concat(`test`.`t1`.`a1`,'x'!
) in <temporary table> on distinct_key where ((concat(`test`.`t1`.`a1`,'x') =
`materialized subselect`.`left(a1,8)`)))))
drop table t1_16, t2_16, t3_16;
set @blob_len = 512;
set @suffix_len = @blob_len - @prefix_len;
=== modified file 'mysql-test/r/subselect_systematic.result'
--- a/mysql-test/r/subselect_systematic.result 2008-11-14 09:46:50 +0000
+++ b/mysql-test/r/subselect_systematic.result 2009-01-05 12:09:10 +0000
@@ -2353,6 +2353,402 @@ from t1n
where vi in(select vi
from t2n)));
id u g v vi s
+-- Tests to check decorrelation which triggers subquery materialization
+-- Non-correlated EXISTS predicate
+explain
+select *
+from t1
+where exists(select *
+from t2, t1 as t3, t2 as t4);
+id select_type table type possible_keys key key_len ref rows Extra
+1 PRIMARY t1 ALL NULL NULL NULL NULL 9
+1 PRIMARY t2 index NULL PRIMARY 4 NULL 9 Using index; Start materialize
+1 PRIMARY t3 index NULL PRIMARY 4 NULL 9 Using index; Using join buffer
+1 PRIMARY t4 index NULL PRIMARY 4 NULL 9 Using index; FirstMatch(t1); End materialize;
Using join buffer
+-- No where clause - use materialization
+explain
+select *
+from t1
+where v in(select t2.v
+from t2, t1 as t3, t2 as t4);
+id select_type table type possible_keys key key_len ref rows Extra
+1 PRIMARY t1 ALL NULL NULL NULL NULL 9
+1 PRIMARY t2 ALL NULL NULL NULL NULL 9 Start materialize
+1 PRIMARY t3 index NULL PRIMARY 4 NULL 9 Using index; Using join buffer
+1 PRIMARY t4 index NULL PRIMARY 4 NULL 9 Using index; End materialize; Using join buffer
+-- EXISTS equivalent to above query - use materialization
+explain
+select *
+from t1
+where exists(select *
+from t2, t1 as t3, t2 as t4
+where t1.v=t2.v);
+id select_type table type possible_keys key key_len ref rows Extra
+1 PRIMARY t1 ALL NULL NULL NULL NULL 9
+1 PRIMARY t2 ALL NULL NULL NULL NULL 9 Start materialize
+1 PRIMARY t3 index NULL PRIMARY 4 NULL 9 Using index; Using join buffer
+1 PRIMARY t4 index NULL PRIMARY 4 NULL 9 Using index; End materialize; Using join buffer
+-- simple equals predicate that augments IN clause - use materialization
+explain
+select *
+from t1
+where v in(select t2.v
+from t2, t1 as t3, t2 as t4
+where t1.vi=t2.vi);
+id select_type table type possible_keys key key_len ref rows Extra
+1 PRIMARY t1 ALL vi NULL NULL NULL 9
+1 PRIMARY t2 ALL vi NULL NULL NULL 9 Start materialize
+1 PRIMARY t3 index NULL PRIMARY 4 NULL 9 Using index; Using join buffer
+1 PRIMARY t4 index NULL PRIMARY 4 NULL 9 Using index; End materialize; Using join buffer
+-- IN predicate on inner tables only - use materialization
+explain
+select *
+from t1
+where v in(select t2.v
+from t2, t1 as t3, t2 as t4
+where t2.vi=t3.vi);
+id select_type table type possible_keys key key_len ref rows Extra
+1 PRIMARY t1 ALL NULL NULL NULL NULL 9
+1 PRIMARY t2 ALL vi NULL NULL NULL 9 Start materialize
+1 PRIMARY t3 ref vi vi 4 test.t2.vi 2 Using index
+1 PRIMARY t4 index NULL PRIMARY 4 NULL 9 Using index; End materialize; Using join buffer
+-- EXISTS predicate on inner tables only - use materialization
+explain
+select *
+from t1
+where exists(select *
+from t2, t1 as t3, t2 as t4
+where t2.vi=t3.vi);
+id select_type table type possible_keys key key_len ref rows Extra
+1 PRIMARY t1 ALL NULL NULL NULL NULL 9
+1 PRIMARY t2 index vi vi 4 NULL 9 Using index; Start materialize
+1 PRIMARY t3 ref vi vi 4 test.t2.vi 2 Using index
+1 PRIMARY t4 index NULL PRIMARY 4 NULL 9 Using index; FirstMatch(t1); End materialize;
Using join buffer
+-- IN predicate on outer tables only - no materialization
+explain
+select *
+from t1
+where v in(select t2.v
+from t2, t1 as t3, t2 as t4
+where t1.vi<>10);
+id select_type table type possible_keys key key_len ref rows Extra
+1 PRIMARY t1 ALL vi NULL NULL NULL 9 Using where
+1 PRIMARY t2 ALL NULL NULL NULL NULL 9 Using where
+1 PRIMARY t3 index NULL PRIMARY 4 NULL 9 Using index; Using join buffer
+1 PRIMARY t4 index NULL PRIMARY 4 NULL 9 Using index; FirstMatch(t1); Using join buffer
+-- EXISTS predicate on outer tables only - no materialization
+explain
+select *
+from t1
+where exists(select *
+from t2, t1 as t3, t2 as t4
+where t1.vi<>10);
+id select_type table type possible_keys key key_len ref rows Extra
+1 PRIMARY t1 ALL vi NULL NULL NULL 9 Using where
+1 PRIMARY t2 index NULL PRIMARY 4 NULL 9 Using index
+1 PRIMARY t3 index NULL PRIMARY 4 NULL 9 Using index; Using join buffer
+1 PRIMARY t4 index NULL PRIMARY 4 NULL 9 Using index; FirstMatch(t1); Using join buffer
+-- AND clause that augments IN clause - use materialization
+explain
+select *
+from t1
+where v in(select t2.v
+from t2, t1 as t3, t2 as t4
+where t1.vi=t2.vi and t1.vi+1=t2.vi+1);
+id select_type table type possible_keys key key_len ref rows Extra
+1 PRIMARY t1 ALL vi NULL NULL NULL 9 Using where
+1 PRIMARY t2 ALL vi NULL NULL NULL 9 Start materialize
+1 PRIMARY t3 index NULL PRIMARY 4 NULL 9 Using index; Using join buffer
+1 PRIMARY t4 index NULL PRIMARY 4 NULL 9 Using index; End materialize; Using join buffer
+-- AND clause that augments IN clause - use materialization
+explain
+select *
+from t1
+where v in(select t2.v
+from t2, t1 as t3, t2 as t4
+where t1.vi=t2.vi and t1.vi+1=t2.vi+1 and t1.vi+t1.v=t2.vi+t2.v);
+id select_type table type possible_keys key key_len ref rows Extra
+1 PRIMARY t1 ALL vi NULL NULL NULL 9 Using where
+1 PRIMARY t2 ALL vi NULL NULL NULL 9 Start materialize
+1 PRIMARY t3 index NULL PRIMARY 4 NULL 9 Using index; Using join buffer
+1 PRIMARY t4 index NULL PRIMARY 4 NULL 9 Using index; End materialize; Using join buffer
+-- EXISTS predicate with AND clause - use materialization
+explain
+select *
+from t1
+where exists(select *
+from t2, t1 as t3, t2 as t4
+where t1.vi=t2.vi and t1.vi+1=t2.vi+1);
+id select_type table type possible_keys key key_len ref rows Extra
+1 PRIMARY t1 ALL vi NULL NULL NULL 9 Using where
+1 PRIMARY t2 index vi vi 4 NULL 9 Using index; Start materialize
+1 PRIMARY t3 index NULL PRIMARY 4 NULL 9 Using index; Using join buffer
+1 PRIMARY t4 index NULL PRIMARY 4 NULL 9 Using index; End materialize; Using join buffer
+-- EXISTS predicate with AND clause - use materialization
+explain
+select *
+from t1
+where exists(select *
+from t2, t1 as t3, t2 as t4
+where t1.vi=t2.vi and t1.vi+1=t2.vi+1 and t1.vi+t1.v=t2.vi+t2.v);
+id select_type table type possible_keys key key_len ref rows Extra
+1 PRIMARY t1 ALL vi NULL NULL NULL 9 Using where
+1 PRIMARY t2 ALL vi NULL NULL NULL 9 Start materialize
+1 PRIMARY t3 index NULL PRIMARY 4 NULL 9 Using index; Using join buffer
+1 PRIMARY t4 index NULL PRIMARY 4 NULL 9 Using index; End materialize; Using join buffer
+-- EXISTS predicate with AND clause - use materialization
+explain
+select *
+from t1
+where exists(select *
+from t2, t1 as t3, t2 as t4
+where t1.vi=t2.vi and t2.v=t3.vi and t3.v=t4.v);
+id select_type table type possible_keys key key_len ref rows Extra
+1 PRIMARY t1 ALL vi NULL NULL NULL 9
+1 PRIMARY t2 ALL vi NULL NULL NULL 9 Start materialize
+1 PRIMARY t3 ALL vi NULL NULL NULL 9 Using where; Using join buffer
+1 PRIMARY t4 ALL NULL NULL NULL NULL 9 Using where; End materialize; Using join buffer
+-- IN predicate with AND clause - use materialization
+explain
+select *
+from t1
+where vi in (select t2.vi
+from t2, t1 as t3, t2 as t4
+where t2.v=t3.vi and t3.v=t4.v);
+id select_type table type possible_keys key key_len ref rows Extra
+1 PRIMARY t1 ALL vi NULL NULL NULL 9
+1 PRIMARY t2 ALL vi NULL NULL NULL 9 Start materialize
+1 PRIMARY t3 ALL vi NULL NULL NULL 9 Using where; Using join buffer
+1 PRIMARY t4 ALL NULL NULL NULL NULL 9 Using where; End materialize; Using join buffer
+-- EXISTS predicate with AND clause - use materialization
+explain
+select *
+from t1
+where exists(select *
+from t2, t1 as t3, t2 as t4
+where t1.vi=t3.vi and t2.v=t3.vi and t3.v=t4.v);
+id select_type table type possible_keys key key_len ref rows Extra
+1 PRIMARY t1 ALL vi NULL NULL NULL 9
+1 PRIMARY t2 ALL NULL NULL NULL NULL 9 Start materialize
+1 PRIMARY t3 ALL vi NULL NULL NULL 9 Using where; Using join buffer
+1 PRIMARY t4 ALL NULL NULL NULL NULL 9 Using where; End materialize; Using join buffer
+-- IN predicate with AND clause - use materialization
+explain
+select *
+from t1
+where vi in (select t3.vi
+from t2, t1 as t3, t2 as t4
+where t2.v=t3.vi and t3.v=t4.v);
+id select_type table type possible_keys key key_len ref rows Extra
+1 PRIMARY t1 ALL vi NULL NULL NULL 9
+1 PRIMARY t2 ALL NULL NULL NULL NULL 9 Start materialize
+1 PRIMARY t3 ALL vi NULL NULL NULL 9 Using where; Using join buffer
+1 PRIMARY t4 ALL NULL NULL NULL NULL 9 Using where; End materialize; Using join buffer
+-- EXISTS predicate with AND clause - use materialization
+explain
+select *
+from t1
+where exists(select *
+from t2, t1 as t3, t2 as t4
+where t1.vi=t4.vi and t2.v=t3.vi and t3.v=t4.v);
+id select_type table type possible_keys key key_len ref rows Extra
+1 PRIMARY t1 ALL vi NULL NULL NULL 9
+1 PRIMARY t2 ALL NULL NULL NULL NULL 9 Start materialize
+1 PRIMARY t3 ALL vi NULL NULL NULL 9 Using where; Using join buffer
+1 PRIMARY t4 ALL vi NULL NULL NULL 9 Using where; End materialize; Using join buffer
+-- IN predicate with AND clause - use materialization
+explain
+select *
+from t1
+where vi in (select t4.vi
+from t2, t1 as t3, t2 as t4
+where t2.v=t3.vi and t3.v=t4.v);
+id select_type table type possible_keys key key_len ref rows Extra
+1 PRIMARY t1 ALL vi NULL NULL NULL 9
+1 PRIMARY t2 ALL NULL NULL NULL NULL 9 Start materialize
+1 PRIMARY t3 ALL vi NULL NULL NULL 9 Using where; Using join buffer
+1 PRIMARY t4 ALL vi NULL NULL NULL 9 Using where; End materialize; Using join buffer
+-- EXISTS predicate with AND clause - use materialization
+explain
+select *
+from t1, t2
+where t1.vi=t2.vi
+and exists(select *
+from t1 as t3, t2 as t4
+where t2.v=t3.v and t3.v=t4.v);
+id select_type table type possible_keys key key_len ref rows Extra
+1 PRIMARY t3 ALL NULL NULL NULL NULL 9 Start materialize; Scan
+1 PRIMARY t4 ALL NULL NULL NULL NULL 9 Using where; End materialize; Using join buffer
+1 PRIMARY t2 ALL vi NULL NULL NULL 9 Using where; Using join buffer
+1 PRIMARY t1 ALL vi NULL NULL NULL 9 Using where; Using join buffer
+-- IN predicate with AND clause - use materialization
+explain
+select *
+from t1, t2
+where t1.vi=t2.vi
+and t2.v in (select t3.v
+from t1 as t3, t2 as t4
+where t3.v=t4.v);
+id select_type table type possible_keys key key_len ref rows Extra
+1 PRIMARY t2 ALL vi NULL NULL NULL 9
+1 PRIMARY t3 ALL NULL NULL NULL NULL 9 Start materialize
+1 PRIMARY t4 ALL NULL NULL NULL NULL 9 Using where; End materialize; Using join buffer
+1 PRIMARY t1 ALL vi NULL NULL NULL 9 Using where; Using join buffer
+-- IN predicate with AND clause - use materialization
+explain
+select *
+from t1
+where (v,v,v) in (select t2.v, t3.v, t4.v
+from t2, t1 as t3, t2 as t4);
+id select_type table type possible_keys key key_len ref rows Extra
+1 PRIMARY t1 ALL NULL NULL NULL NULL 9
+1 PRIMARY t2 ALL NULL NULL NULL NULL 9 Start materialize
+1 PRIMARY t3 ALL NULL NULL NULL NULL 9 Using where; Using join buffer
+1 PRIMARY t4 ALL NULL NULL NULL NULL 9 Using where; End materialize; Using join buffer
+-- IN and OR clause involving outer tables - no materialization
+explain
+select *
+from t1
+where v in(select t2.v
+from t2, t1 as t3, t2 as t4
+where t1.vi=t2.vi or t1.vi+1=t2.vi+1);
+id select_type table type possible_keys key key_len ref rows Extra
+1 PRIMARY t3 index NULL PRIMARY 4 NULL 9 Using index
+1 PRIMARY t1 ALL vi NULL NULL NULL 9 Using join buffer
+1 PRIMARY t2 ALL vi NULL NULL NULL 9 Using where
+1 PRIMARY t4 index NULL PRIMARY 4 NULL 9 Using index; FirstMatch(t1); Using join buffer
+-- EXISTS and OR clause involving outer tables - no materialization
+explain
+select *
+from t1
+where exists(select *
+from t2, t1 as t3, t2 as t4
+where t1.vi=t2.vi or t1.vi+1=t2.vi+1);
+id select_type table type possible_keys key key_len ref rows Extra
+1 PRIMARY t3 index NULL PRIMARY 4 NULL 9 Using index
+1 PRIMARY t1 ALL vi NULL NULL NULL 9 Using join buffer
+1 PRIMARY t2 index vi vi 4 NULL 9 Using where; Using index
+1 PRIMARY t4 index NULL PRIMARY 4 NULL 9 Using index; FirstMatch(t1); Using join buffer
+-- IN and OR clause involving inner tables - use materialization
+explain
+select *
+from t1
+where v in(select t2.v
+from t2, t1 as t3, t2 as t4
+where t2.vi=t3.vi or t3.vi=t4.vi);
+id select_type table type possible_keys key key_len ref rows Extra
+1 PRIMARY t1 ALL NULL NULL NULL NULL 9
+1 PRIMARY t2 ALL vi NULL NULL NULL 9 Start materialize
+1 PRIMARY t3 index vi vi 4 NULL 9 Using index; Using join buffer
+1 PRIMARY t4 index vi vi 4 NULL 9 Using where; Using index; End materialize; Using join
buffer
+-- EXISTS and OR clause involving inner tables - use materialization
+explain
+select *
+from t1
+where exists(select *
+from t2, t1 as t3, t2 as t4
+where t2.vi=t3.vi or t3.vi=t4.vi);
+id select_type table type possible_keys key key_len ref rows Extra
+1 PRIMARY t1 ALL NULL NULL NULL NULL 9
+1 PRIMARY t2 index vi vi 4 NULL 9 Using index; Start materialize
+1 PRIMARY t3 index vi vi 4 NULL 9 Using index; Using join buffer
+1 PRIMARY t4 index vi vi 4 NULL 9 Using where; Using index; FirstMatch(t1); End
materialize; Using join buffer
+-- IN and OR clause on 2. level - inner tables only - use materialization
+explain
+select *
+from t1
+where v in(select t2.v
+from t2, t1 as t3, t2 as t4
+where t1.vi=t2.vi and (t2.vi=t3.vi or t3.v=t4.v));
+id select_type table type possible_keys key key_len ref rows Extra
+1 PRIMARY t1 ALL vi NULL NULL NULL 9
+1 PRIMARY t2 ALL vi NULL NULL NULL 9 Start materialize
+1 PRIMARY t3 ALL vi NULL NULL NULL 9 Using join buffer
+1 PRIMARY t4 ALL NULL NULL NULL NULL 9 Using where; End materialize; Using join buffer
+-- EXISTS and OR clause on 2. level - inner t. only - use materialization
+explain
+select *
+from t1
+where exists(select *
+from t2, t1 as t3, t2 as t4
+where t1.vi=t2.vi and (t2.vi=t3.vi or t3.v=t4.v));
+id select_type table type possible_keys key key_len ref rows Extra
+1 PRIMARY t1 ALL vi NULL NULL NULL 9
+1 PRIMARY t2 index vi vi 4 NULL 9 Using index; Start materialize
+1 PRIMARY t3 ALL vi NULL NULL NULL 9 Using join buffer
+1 PRIMARY t4 ALL NULL NULL NULL NULL 9 Using where; End materialize; Using join buffer
+-- IN and OR clause on 2. level - outer tables - no materialization
+explain
+select *
+from t1
+where v in(select t2.v
+from t2, t1 as t3, t2 as t4
+where t1.vi=t2.vi and (t1.vi=t3.vi or t3.v=t4.v));
+id select_type table type possible_keys key key_len ref rows Extra
+1 PRIMARY t1 ALL vi NULL NULL NULL 9
+1 PRIMARY t2 ref vi vi 4 test.t1.vi 2 Using where
+1 PRIMARY t3 ALL vi NULL NULL NULL 9 Using join buffer
+1 PRIMARY t4 ALL NULL NULL NULL NULL 9 Using where; FirstMatch(t1); Using join buffer
+-- EXISTS and OR clause on 2. level - outer tables - no materialization
+explain
+select *
+from t1
+where exists(select *
+from t2, t1 as t3, t2 as t4
+where t1.vi=t2.vi and (t1.vi=t3.vi or t3.v=t4.v));
+id select_type table type possible_keys key key_len ref rows Extra
+1 PRIMARY t1 ALL vi NULL NULL NULL 9
+1 PRIMARY t2 ref vi vi 4 test.t1.vi 2 Using index
+1 PRIMARY t3 ALL vi NULL NULL NULL 9 Using join buffer
+1 PRIMARY t4 ALL NULL NULL NULL NULL 9 Using where; FirstMatch(t1); Using join buffer
+-- IN and NOT equals clause - no materialization
+explain
+select *
+from t1
+where v in(select t2.v
+from t2, t1 as t3, t2 as t4
+where t1.vi=t2.vi and not t1.vi=t3.vi);
+id select_type table type possible_keys key key_len ref rows Extra
+1 PRIMARY t1 ALL vi NULL NULL NULL 9
+1 PRIMARY t2 ref vi vi 4 test.t1.vi 2 Using where
+1 PRIMARY t3 index NULL vi 4 NULL 9 Using where; Using index; Using join buffer
+1 PRIMARY t4 index NULL PRIMARY 4 NULL 9 Using index; FirstMatch(t1); Using join buffer
+-- EXISTS and NOT equals clause - no materialization
+explain
+select *
+from t1
+where exists(select *
+from t2, t1 as t3, t2 as t4
+where t1.vi=t2.vi and not t1.vi=t3.vi);
+id select_type table type possible_keys key key_len ref rows Extra
+1 PRIMARY t1 ALL vi NULL NULL NULL 9
+1 PRIMARY t2 ref vi vi 4 test.t1.vi 2 Using index
+1 PRIMARY t3 index NULL vi 4 NULL 9 Using where; Using index; Using join buffer
+1 PRIMARY t4 index NULL PRIMARY 4 NULL 9 Using index; FirstMatch(t1); Using join buffer
+-- IN and NOT not-equals clause - use materialization
+explain
+select *
+from t1
+where v in(select t2.v
+from t2, t1 as t3, t2 as t4
+where t1.vi=t2.vi and not t1.vi<>t3.vi);
+id select_type table type possible_keys key key_len ref rows Extra
+1 PRIMARY t1 ALL vi NULL NULL NULL 9
+1 PRIMARY t2 ALL vi NULL NULL NULL 9 Start materialize
+1 PRIMARY t3 ref vi vi 4 test.t1.vi 2 Using where; Using index
+1 PRIMARY t4 index NULL PRIMARY 4 NULL 9 Using index; End materialize; Using join buffer
+-- EXISTS and NOT not-equals clause - use materialization
+explain
+select *
+from t1
+where exists(select *
+from t2, t1 as t3, t2 as t4
+where t1.vi=t2.vi and not t1.vi<>t3.vi);
+id select_type table type possible_keys key key_len ref rows Extra
+1 PRIMARY t1 ALL vi NULL NULL NULL 9
+1 PRIMARY t2 index vi vi 4 NULL 9 Using index; Start materialize
+1 PRIMARY t3 ref vi vi 4 test.t1.vi 2 Using where; Using index
+1 PRIMARY t4 index NULL PRIMARY 4 NULL 9 Using index; End materialize; Using join buffer
-- Drop all created tables
drop table empty;
drop table nulls;
=== modified file 'mysql-test/t/subselect_systematic.test'
--- a/mysql-test/t/subselect_systematic.test 2008-11-14 09:46:50 +0000
+++ b/mysql-test/t/subselect_systematic.test 2009-01-05 12:09:10 +0000
@@ -1534,6 +1534,271 @@ where u in(select u
where vi in(select vi
from t2n)));
+--echo -- Tests to check decorrelation which triggers subquery materialization
+
+--echo -- Non-correlated EXISTS predicate
+explain
+select *
+from t1
+where exists(select *
+ from t2, t1 as t3, t2 as t4);
+
+--echo -- No where clause - use materialization
+explain
+select *
+from t1
+where v in(select t2.v
+ from t2, t1 as t3, t2 as t4);
+
+--echo -- EXISTS equivalent to above query - use materialization
+explain
+select *
+from t1
+where exists(select *
+ from t2, t1 as t3, t2 as t4
+ where t1.v=t2.v);
+
+--echo -- simple equals predicate that augments IN clause - use materialization
+explain
+select *
+from t1
+where v in(select t2.v
+ from t2, t1 as t3, t2 as t4
+ where t1.vi=t2.vi);
+
+--echo -- IN predicate on inner tables only - use materialization
+explain
+select *
+from t1
+where v in(select t2.v
+ from t2, t1 as t3, t2 as t4
+ where t2.vi=t3.vi);
+
+--echo -- EXISTS predicate on inner tables only - use materialization
+explain
+select *
+from t1
+where exists(select *
+ from t2, t1 as t3, t2 as t4
+ where t2.vi=t3.vi);
+
+--echo -- IN predicate on outer tables only - no materialization
+explain
+select *
+from t1
+where v in(select t2.v
+ from t2, t1 as t3, t2 as t4
+ where t1.vi<>10);
+
+--echo -- EXISTS predicate on outer tables only - no materialization
+explain
+select *
+from t1
+where exists(select *
+ from t2, t1 as t3, t2 as t4
+ where t1.vi<>10);
+
+--echo -- AND clause that augments IN clause - use materialization
+explain
+select *
+from t1
+where v in(select t2.v
+ from t2, t1 as t3, t2 as t4
+ where t1.vi=t2.vi and t1.vi+1=t2.vi+1);
+
+--echo -- AND clause that augments IN clause - use materialization
+explain
+select *
+from t1
+where v in(select t2.v
+ from t2, t1 as t3, t2 as t4
+ where t1.vi=t2.vi and t1.vi+1=t2.vi+1 and t1.vi+t1.v=t2.vi+t2.v);
+
+--echo -- EXISTS predicate with AND clause - use materialization
+explain
+select *
+from t1
+where exists(select *
+ from t2, t1 as t3, t2 as t4
+ where t1.vi=t2.vi and t1.vi+1=t2.vi+1);
+
+--echo -- EXISTS predicate with AND clause - use materialization
+explain
+select *
+from t1
+where exists(select *
+ from t2, t1 as t3, t2 as t4
+ where t1.vi=t2.vi and t1.vi+1=t2.vi+1 and t1.vi+t1.v=t2.vi+t2.v);
+
+--echo -- EXISTS predicate with AND clause - use materialization
+explain
+select *
+from t1
+where exists(select *
+ from t2, t1 as t3, t2 as t4
+ where t1.vi=t2.vi and t2.v=t3.vi and t3.v=t4.v);
+
+--echo -- IN predicate with AND clause - use materialization
+explain
+select *
+from t1
+where vi in (select t2.vi
+ from t2, t1 as t3, t2 as t4
+ where t2.v=t3.vi and t3.v=t4.v);
+
+--echo -- EXISTS predicate with AND clause - use materialization
+explain
+select *
+from t1
+where exists(select *
+ from t2, t1 as t3, t2 as t4
+ where t1.vi=t3.vi and t2.v=t3.vi and t3.v=t4.v);
+
+--echo -- IN predicate with AND clause - use materialization
+explain
+select *
+from t1
+where vi in (select t3.vi
+ from t2, t1 as t3, t2 as t4
+ where t2.v=t3.vi and t3.v=t4.v);
+
+--echo -- EXISTS predicate with AND clause - use materialization
+explain
+select *
+from t1
+where exists(select *
+ from t2, t1 as t3, t2 as t4
+ where t1.vi=t4.vi and t2.v=t3.vi and t3.v=t4.v);
+
+--echo -- IN predicate with AND clause - use materialization
+explain
+select *
+from t1
+where vi in (select t4.vi
+ from t2, t1 as t3, t2 as t4
+ where t2.v=t3.vi and t3.v=t4.v);
+
+--echo -- EXISTS predicate with AND clause - use materialization
+explain
+select *
+from t1, t2
+where t1.vi=t2.vi
+ and exists(select *
+ from t1 as t3, t2 as t4
+ where t2.v=t3.v and t3.v=t4.v);
+
+--echo -- IN predicate with AND clause - use materialization
+explain
+select *
+from t1, t2
+where t1.vi=t2.vi
+ and t2.v in (select t3.v
+ from t1 as t3, t2 as t4
+ where t3.v=t4.v);
+
+--echo -- IN predicate with AND clause - use materialization
+explain
+select *
+from t1
+where (v,v,v) in (select t2.v, t3.v, t4.v
+ from t2, t1 as t3, t2 as t4);
+
+--echo -- IN and OR clause involving outer tables - no materialization
+explain
+select *
+from t1
+where v in(select t2.v
+ from t2, t1 as t3, t2 as t4
+ where t1.vi=t2.vi or t1.vi+1=t2.vi+1);
+
+--echo -- EXISTS and OR clause involving outer tables - no materialization
+explain
+select *
+from t1
+where exists(select *
+ from t2, t1 as t3, t2 as t4
+ where t1.vi=t2.vi or t1.vi+1=t2.vi+1);
+
+--echo -- IN and OR clause involving inner tables - use materialization
+explain
+select *
+from t1
+where v in(select t2.v
+ from t2, t1 as t3, t2 as t4
+ where t2.vi=t3.vi or t3.vi=t4.vi);
+
+--echo -- EXISTS and OR clause involving inner tables - use materialization
+explain
+select *
+from t1
+where exists(select *
+ from t2, t1 as t3, t2 as t4
+ where t2.vi=t3.vi or t3.vi=t4.vi);
+
+--echo -- IN and OR clause on 2. level - inner tables only - use materialization
+explain
+select *
+from t1
+where v in(select t2.v
+ from t2, t1 as t3, t2 as t4
+ where t1.vi=t2.vi and (t2.vi=t3.vi or t3.v=t4.v));
+
+--echo -- EXISTS and OR clause on 2. level - inner t. only - use materialization
+explain
+select *
+from t1
+where exists(select *
+ from t2, t1 as t3, t2 as t4
+ where t1.vi=t2.vi and (t2.vi=t3.vi or t3.v=t4.v));
+
+--echo -- IN and OR clause on 2. level - outer tables - no materialization
+explain
+select *
+from t1
+where v in(select t2.v
+ from t2, t1 as t3, t2 as t4
+ where t1.vi=t2.vi and (t1.vi=t3.vi or t3.v=t4.v));
+
+--echo -- EXISTS and OR clause on 2. level - outer tables - no materialization
+explain
+select *
+from t1
+where exists(select *
+ from t2, t1 as t3, t2 as t4
+ where t1.vi=t2.vi and (t1.vi=t3.vi or t3.v=t4.v));
+
+--echo -- IN and NOT equals clause - no materialization
+explain
+select *
+from t1
+where v in(select t2.v
+ from t2, t1 as t3, t2 as t4
+ where t1.vi=t2.vi and not t1.vi=t3.vi);
+
+--echo -- EXISTS and NOT equals clause - no materialization
+explain
+select *
+from t1
+where exists(select *
+ from t2, t1 as t3, t2 as t4
+ where t1.vi=t2.vi and not t1.vi=t3.vi);
+
+--echo -- IN and NOT not-equals clause - use materialization
+explain
+select *
+from t1
+where v in(select t2.v
+ from t2, t1 as t3, t2 as t4
+ where t1.vi=t2.vi and not t1.vi<>t3.vi);
+
+--echo -- EXISTS and NOT not-equals clause - use materialization
+explain
+select *
+from t1
+where exists(select *
+ from t2, t1 as t3, t2 as t4
+ where t1.vi=t2.vi and not t1.vi<>t3.vi);
+
--echo -- Drop all created tables
drop table empty;
=== modified file 'sql/sql_select.cc'
--- a/sql/sql_select.cc 2008-12-30 01:06:02 +0000
+++ b/sql/sql_select.cc 2009-01-05 12:09:10 +0000
@@ -592,14 +592,52 @@ JOIN::prepare(Item ***rref_pointer_array
subselect->substype() == Item_subselect::EXISTS_SUBS) ?
(Item_exists_subselect*)subselect :
NULL;
+ Item_in_subselect *in_subs=
+ (subselect->substype() == Item_subselect::IN_SUBS) ?
+ (Item_in_subselect *)item_subs :
+ NULL;
/* Small trick to avoid several if tests below. exec_method is
not defined for EXISTS queries. */
- Item_in_subselect::enum_exec_method exec_method=
- (subselect->substype() == Item_subselect::IN_SUBS) ?
- ((Item_in_subselect *)item_subs)->exec_method :
- Item_in_subselect::NOT_TRANSFORMED;
+ Item_in_subselect::enum_exec_method exec_method= (in_subs != NULL) ?
+ in_subs->exec_method :
+ Item_in_subselect::NOT_TRANSFORMED;
+
+ /* Resolve expressions and perform semantic analysis for IN query */
+ if (in_subs != NULL &&
+ thd->stmt_arena->state != Query_arena::PREPARED)
+ {
+ SELECT_LEX *current= thd->lex->current_select;
+ thd->lex->current_select= current->return_after_parsing();
+ char const *save_where= thd->where;
+ thd->where= "IN/ALL/ANY subquery";
+
+ bool failure= !in_subs->left_expr->fixed &&
+ in_subs->left_expr->fix_fields(thd,
&in_subs->left_expr);
+ thd->lex->current_select= current;
+ thd->where= save_where;
+ if (failure)
+ DBUG_RETURN(-1); /* purecov: deadcode */
+ /*
+ Check if the left and right expressions have the same # of
+ columns, i.e. we don't have a case like
+ (oe1, oe2) IN (SELECT ie1, ie2, ie3 ...)
+ TODO why do we have this duplicated in IN->EXISTS transformers?
+ psergey-todo: fix these: grep for duplicated_subselect_card_check
+ */
+ if (select_lex->item_list.elements != in_subs->left_expr->cols())
+ {
+ my_error(ER_OPERAND_COLUMNS, MYF(0), in_subs->left_expr->cols());
+ DBUG_RETURN(-1);
+ }
+ }
+ if (item_subs != NULL &&
+ thd->stmt_arena->state != Query_arena::PREPARED)
+ { item_subs->types_allow_materialization=
+ subquery_types_allow_materialization(thd, item_subs,
+ &item_subs->sjm_scan_allowed);
+ }
/* Try the following sequence of query transformations:
1. Convert the query into a semi-join
2. Materialize the subquery
@@ -638,42 +676,6 @@ JOIN::prepare(Item ***rref_pointer_array
& SELECT_STRAIGHT_JOIN)) // 10
{
DBUG_PRINT("info", ("Subquery is semi-join conversion candidate"));
- item_subs->types_allow_materialization=
- subquery_types_allow_materialization(thd, item_subs,
- &item_subs->sjm_scan_allowed);
-
- /* This step is only applicable to IN/=ANY queries (no EXISTS) */
- if (subselect->substype() == Item_subselect::IN_SUBS &&
- thd->stmt_arena->state != Query_arena::PREPARED)
- {
- Item_in_subselect *in_subs= (Item_in_subselect *)item_subs;
- SELECT_LEX *current= thd->lex->current_select;
- thd->lex->current_select= current->return_after_parsing();
- char const *save_where= thd->where;
- thd->where= "IN/ALL/ANY subquery";
-
- bool failure= !in_subs->left_expr->fixed &&
- in_subs->left_expr->fix_fields(thd,
- &in_subs->left_expr);
- thd->lex->current_select= current;
- thd->where= save_where;
- in_subs->emb_on_expr_nest= thd->thd_marker.emb_on_expr_nest;
- if (failure)
- DBUG_RETURN(-1); /* purecov: deadcode */
- /*
- Check if the left and right expressions have the same # of
- columns, i.e. we don't have a case like
- (oe1, oe2) IN (SELECT ie1, ie2, ie3 ...)
-
- TODO why do we have this duplicated in IN->EXISTS transformers?
- psergey-todo: fix these: grep for duplicated_subselect_card_check
- */
- if (select_lex->item_list.elements != in_subs->left_expr->cols())
- {
- my_error(ER_OPERAND_COLUMNS, MYF(0), in_subs->left_expr->cols());
- DBUG_RETURN(-1);
- }
- }
item_subs->emb_on_expr_nest= thd->thd_marker.emb_on_expr_nest;
@@ -723,8 +725,7 @@ JOIN::prepare(Item ***rref_pointer_array
!select_lex->is_part_of_union() && // 2
select_lex->master_unit()->first_select()->leaf_tables &&
// 3
thd->lex->sql_command == SQLCOM_SELECT && //
*
- select_lex->outer_select()->leaf_tables && //
3A
- subquery_types_allow_materialization(thd, item_subs, NULL))
+ select_lex->outer_select()->leaf_tables) // 3A
{
// psergey-todo: duplicated_subselect_card_check: where it's done?
Item_in_subselect *in_subs= (Item_in_subselect *)item_subs;
@@ -942,30 +943,16 @@ bool subquery_types_allow_materializatio
if (subs->substype() == Item_subselect::EXISTS_SUBS)
{
- *scan_allowed= true;
+ *scan_allowed= true; /* FIXME before WL#4389 is complete */
DBUG_RETURN(true);
}
Item_in_subselect *in_subs= (Item_in_subselect *)subs;
- /* Fix the left expression if it is not yet fixed */
- if (!in_subs->left_expr->fixed)
- {
- SELECT_LEX *save_lex= thd->lex->current_select;
- thd->lex->current_select= save_lex->outer_select();
- char const *save_where= thd->where;
- thd->where= "IN/ALL/ANY subquery";
- bool res= in_subs->left_expr->fix_fields(thd, &in_subs->left_expr);
- thd->where= save_where;
- thd->lex->current_select=save_lex;
- if (res)
- DBUG_RETURN(FALSE);
- }
+ /* Left expression should be fixed when we reach here */
+ DBUG_ASSERT(in_subs->left_expr->fixed);
List_iterator<Item> it(in_subs->unit->first_select()->item_list);
uint elements= in_subs->unit->first_select()->item_list.elements;
- // psergey: duplicated_subselect_card_check
- if (in_subs->left_expr->cols() != elements)
- DBUG_RETURN(FALSE);
bool all_are_fields= TRUE;
for (uint i= 0; i < elements; i++)
@@ -3197,7 +3184,78 @@ void fix_list_after_tbl_changes(SELECT_L
}
}
+/*
+ Decorrelate the search condition of a subquery.
+
+ SYNOPSIS
+ decorrelate_subquery_search_cond()
+ sj_nest Semi join nest that we are decorrelating
+ cond search condition we are decorrelating, handled recursively
+ correlated set to "true" if we locate a predicate that refers to an
+ outer table and cannot be decorrelated
+
+ DESCRIPTION
+ Analyze each predicate of a subquery search condition.
+ For each trivially-correlated predicate, populate the lists of "left" and
+ "right" expressions of the semi-join nest, similar to the left and right
+ expressions of an IN query.
+
+ Note that the table map of an outer table must be equal to
+ OUTER_REF_TABLE_BIT for this routine to work.
+*/
+void decorrelate_subquery_search_cond(TABLE_LIST *sj_nest, Item *cond,
+ bool *correlated)
+{
+ if (cond == NULL)
+ { return;
+ }
+ if (cond->type() == Item::FUNC_ITEM &&
+ ((Item_func *)cond)->functype() == Item_func::EQ_FUNC)
+ {
+ Item_func_eq *eq_cond = (Item_func_eq *)cond;
+ Item *left = eq_cond->arguments()[0];
+ Item *right = eq_cond->arguments()[1];
+
+ /* De-correlate an equality comparison if the left hand side is from
+ the outer tables and the right hand side is from the inner tables,
+ or vice versa. */
+ if ((left->used_tables() == OUTER_REF_TABLE_BIT) &&
+ right->used_tables() &&
+ !(right->used_tables()&OUTER_REF_TABLE_BIT))
+ {
+ sj_nest->nested_join->sj_outer_expr_list.push_back(left);
+ sj_nest->nested_join->sj_inner_exprs.push_back(right);
+ eq_cond->in_equality_no= 0; // Mark it as a subquery equality predicate
+ }
+ else if ((right->used_tables() == OUTER_REF_TABLE_BIT) &&
+ left->used_tables() &&
+ !(left->used_tables()&OUTER_REF_TABLE_BIT))
+ {
+ sj_nest->nested_join->sj_outer_expr_list.push_back(right);
+ sj_nest->nested_join->sj_inner_exprs.push_back(left);
+ eq_cond->in_equality_no= 0; // Mark it as a subquery equality predicate
+ }
+ else if (cond->used_tables()&OUTER_REF_TABLE_BIT)
+ {
+ *correlated = TRUE;
+ }
+ }
+ else if (cond->type() == Item::COND_ITEM &&
+ ((Item_cond*)cond)->functype() == Item_func::COND_AND_FUNC)
+ {
+ List_iterator_fast<Item> li(*((Item_cond*)cond)->argument_list());
+ Item *item;
+ while ((item=li++))
+ {
+ decorrelate_subquery_search_cond(sj_nest, item, correlated);
+ }
+ }
+ else if (cond->used_tables()&OUTER_REF_TABLE_BIT)
+ {
+ *correlated = TRUE;
+ }
+}
/*
Convert a subquery predicate into a TABLE_LIST semi-join nest
@@ -3419,7 +3477,6 @@ bool convert_subq_to_sj(JOIN *parent_joi
tl->join_list= &nested_join->join_list;
nested_join->join_list.push_back(tl);
}
-
/*
Reconnect the next_leaf chain.
TODO: Do we have to put subquery's tables at the end of the chain?
@@ -3464,6 +3521,20 @@ bool convert_subq_to_sj(JOIN *parent_joi
}
parent_join->tables += subq_lex->join->tables;
+ sj_nest->nested_join->sj_outer_expr_list.empty();
+ sj_nest->nested_join->sj_inner_exprs.empty();
+
+ /* A semijoin nest is considered to be correlated with the outer query if
+ 1) subquery contains any expression that involves an outer table, and
+ 2) that expression is not trivially-correlated.
+ A correlated semijoin cannot be executed using materialization strategy. */
+
+ bool correlated = FALSE;
+
+ decorrelate_subquery_search_cond(sj_nest, subq_lex->where, &correlated);
+
+ sj_nest->sj_subq_pred->is_correlated = correlated;
+
if (subq_pred->substype() == Item_subselect::IN_SUBS)
{
/*
@@ -3497,16 +3568,14 @@ bool convert_subq_to_sj(JOIN *parent_joi
Item_direct_view_refs doesn't substitute itself with anything in
Item_direct_view_ref::fix_fields.
*/
- sj_nest->sj_in_exprs= in_subq_pred->left_expr->cols();
- sj_nest->nested_join->sj_outer_expr_list.empty();
-
if (in_subq_pred->left_expr->cols() == 1)
{
nested_join->sj_outer_expr_list.push_back(in_subq_pred->left_expr);
+ nested_join->sj_inner_exprs.push_back(subq_lex->ref_pointer_array[0]);
Item_func_eq *item_eq= new Item_func_eq(in_subq_pred->left_expr,
subq_lex->ref_pointer_array[0]);
- item_eq->in_equality_no= 0;
+ item_eq->in_equality_no= 0; // Mark it as a subquery equality predicate
sj_nest->sj_on_expr= and_items(sj_nest->sj_on_expr, item_eq);
}
else
@@ -3515,10 +3584,11 @@ bool convert_subq_to_sj(JOIN *parent_joi
{
nested_join->sj_outer_expr_list.push_back(in_subq_pred->left_expr->
element_index(i));
+ nested_join->sj_inner_exprs.push_back(subq_lex->ref_pointer_array[i]);
Item_func_eq *item_eq=
new Item_func_eq(in_subq_pred->left_expr->element_index(i),
subq_lex->ref_pointer_array[i]);
- item_eq->in_equality_no= i;
+ item_eq->in_equality_no= 0; // Mark it as a subquery equality predicate
sj_nest->sj_on_expr= and_items(sj_nest->sj_on_expr, item_eq);
}
}
@@ -3558,17 +3628,29 @@ bool convert_subq_to_sj(JOIN *parent_joi
else if (subq_pred->substype() == Item_subselect::EXISTS_SUBS)
{
/* Add information about correlated tables to semi-join nest */
+ Item *synthetic_cond = NULL;
sj_nest->nested_join->sj_corr_tables= subq_pred->used_tables();
sj_nest->nested_join->sj_depends_on= subq_pred->used_tables();
+
+ if (sj_nest->nested_join->sj_outer_expr_list.elements == 0)
+ {
+ // Add "1=1" predicate, which is always true
+ // Push the expressions into the expression lists
+ synthetic_cond= new Item_func_eq(new Item_int(1), new Item_int(1));
+ sj_nest->nested_join->sj_outer_expr_list.push_back(
+ ((Item_func *)synthetic_cond)->arguments()[0]);
+
+ sj_nest->nested_join->sj_inner_exprs.push_back(
+ ((Item_func *)synthetic_cond)->arguments()[1]);
+ }
if (subq_lex->where)
{
sj_nest->sj_on_expr= subq_lex->where; // Non-empty EXISTS predicate
}
else
- {
- sj_nest->sj_on_expr= new Item_int(1); // Add a "true" predicate, NULL
- // pointer not supported
+ { // sj_on_expr equals NULL is not supported, so add the synthetic cond
+ sj_nest->sj_on_expr= synthetic_cond;
}
/*
Walk through sj nest's WHERE and ON expressions and call
@@ -4914,12 +4996,14 @@ merge_key_fields(KEY_FIELD *start,KEY_FI
}
/*
- Given a field, return its index in semi-join's select list, or UINT_MAX
+ Given a field, return its index in semi-join's expression list, or UINT_MAX
DESCRIPTION
Given a field, we find its table; then see if the table is within a
- semi-join nest and if the field was in select list of the subselect.
- If it was, we return field's index in the select list. The value is used
+ semi-join nest and if the field was in select list of the subselect
+ (if subselect was part of a quantified comparison predicate), or
+ the field was a result of subquery decorrelation.
+ If it was, we return field's index in the expression list. The value is used
by LooseScan strategy.
*/
@@ -4927,38 +5011,19 @@ static uint get_semi_join_select_list_in
{
uint res= UINT_MAX;
TABLE_LIST *emb_sj_nest;
- /*
- NOTE: at the moment semi-join nests do not have a list of IN-equalites
- and hence there is no way to use LooseScan to resolve such queries.
- TODO: When WL#4389's trivial correlation detection is implemented, make
- the code below handle semi-join nests that were made from EXISTS.
- */
if ((emb_sj_nest= field->table->pos_in_table_list->embedding) &&
- emb_sj_nest->sj_on_expr &&
- emb_sj_nest->sj_subq_pred->substype() == Item_subselect::IN_SUBS)
+ emb_sj_nest->sj_on_expr)
{
- Item_in_subselect *subq_pred= (Item_in_subselect*)emb_sj_nest->sj_subq_pred;
- st_select_lex *subq_lex= subq_pred->unit->first_select();
- if (subq_pred->left_expr->cols() == 1)
+ List<Item> &items= emb_sj_nest->nested_join->sj_inner_exprs;
+ List_iterator<Item> it(items);
+ for (uint i= 0; i < items.elements; i++)
{
- Item *sel_item= subq_lex->ref_pointer_array[0];
+ Item *sel_item= it++;
if (sel_item->type() == Item::FIELD_ITEM &&
((Item_field*)sel_item)->field->eq(field))
{
- res= 0;
- }
- }
- else
- {
- for (uint i= 0; i < subq_pred->left_expr->cols(); i++)
- {
- Item *sel_item= subq_lex->ref_pointer_array[i];
- if (sel_item->type() == Item::FIELD_ITEM &&
- ((Item_field*)sel_item)->field->eq(field))
- {
- res= i;
- break;
- }
+ res= i;
+ break;
}
}
}
@@ -6035,10 +6100,10 @@ public:
*/
best_loose_scan_cost= DBL_MAX;
if (!join->emb_sjm_nest && s->emb_sj_nest &&
// (1)
- s->emb_sj_nest->sj_in_exprs < 64 &&
+ s->emb_sj_nest->nested_join->sj_inner_exprs.elements < 64 &&
((remaining_tables & s->emb_sj_nest->sj_inner_tables) == // (2)
s->emb_sj_nest->sj_inner_tables) && //
(2)
- join->cur_sj_inner_tables == 0 && //
(3)
+ join->cur_sj_inner_tables == 0 && // (3)
!(remaining_tables &
s->emb_sj_nest->nested_join->sj_corr_tables) &&
// (4)
remaining_tables & s->emb_sj_nest->nested_join->sj_depends_on
&&// (5)
@@ -6100,12 +6165,13 @@ public:
(handled_col|bound_col)* (other_col|bound_col)
*/
- if (try_loosescan && // (1)
- (handled_sj_equalities | bound_sj_equalities) == // (2)
- PREV_BITS(ulonglong, s->emb_sj_nest->sj_in_exprs) && // (2)
- (PREV_BITS(key_part_map, max_loose_keypart+1) & // (3)
- (found_part | loose_scan_keyparts)) == // (3)
- (found_part | loose_scan_keyparts) && // (3)
+ if (try_loosescan && // (1)
+ (handled_sj_equalities | bound_sj_equalities) == // (2)
+ PREV_BITS(ulonglong,
+
s->emb_sj_nest->nested_join->sj_inner_exprs.elements)&& // (2)
+ (PREV_BITS(key_part_map, max_loose_keypart+1) & // (3)
+ (found_part | loose_scan_keyparts)) == // (3)
+ (found_part | loose_scan_keyparts) && // (3)
!key_uses_partial_cols(s->table, key))
{
/* Ok, can use the strategy */
@@ -7943,7 +8009,6 @@ static void fix_semijoin_strategies_for_
remaining_tables |= s->table->map;
continue;
}
-
if (pos->sj_strategy == SJ_OPT_MATERIALIZE)
{
SJ_MATERIALIZATION_INFO *sjm= s->emb_sj_nest->sj_mat_info;
@@ -9118,10 +9183,9 @@ static bool make_join_select(JOIN *join,
}
first_inner_tab= first_inner_tab->first_upper;
}
-
- if (save_used_tables && !(used_tables &
- ~(tab->emb_sj_nest->sj_inner_tables |
- join->const_table_map | PSEUDO_TABLE_BITS)))
+ if (save_used_tables && // Inside an SJM nest, and
+ !(tab->emb_sj_nest->sj_inner_tables &
+ ~used_tables)) // All inner tables in prefix
{
/*
We have reached the end of semi join nest. That is, the join order
@@ -9130,12 +9194,8 @@ static bool make_join_select(JOIN *join,
outer_tbl1 SJ-Materialize(inner_tbl1 ... inner_tblN) outer_tbl ...
^
\-we're here
- At this point, we need to produce two conditions
- - A condition that can be checked when we have all of the sj-inner
- tables (inner_tbl1 ... inner_tblN). This will be used while doing
- materialization.
- - A condition that can be checked when we have all of the tables
- in the prefix (both inner and outer).
+ At this point, we need to produce a condition that can be checked
+ when we have all of the tables in the prefix (both inner and outer).
*/
tab->emb_sj_nest->sj_mat_info->join_cond=
cond ?
@@ -9695,43 +9755,49 @@ void remove_sj_conds(Item **tree)
/*
- Create subquery IN-equalities assuming use of materialization strategy
+ Create subquery equalities assuming use of materialization strategy
SYNOPSIS
- create_subq_in_equalities()
+ create_subq_equalities()
thd Thread handle
sjm Semi-join materialization structure
- subq_pred The subquery predicate
+ sj_nest Semi-join nest
DESCRIPTION
- Create subquery IN-equality predicates. That is, for a subquery
+ Create subquery equality predicates. That is, for a subquery
(oe1, oe2, ...) IN (SELECT ie1, ie2, ... FROM ...)
- create "oe1=ie1 AND ie1=ie2 AND ..." expression, such that ie1, ie2, ..
+ create "oe1=ie1 AND oe2=ie2 AND ..." expression, such that ie1, ie2, ..
refer to the columns of the table that's used to materialize the
subquery.
+ This function will also generate proper equality predicates for
+ trivially-correlated subqueries corresponding to the above IN query.
RETURN
Created condition
*/
-Item *create_subq_in_equalities(THD *thd, SJ_MATERIALIZATION_INFO *sjm,
- Item_in_subselect *subq_pred)
+Item *create_subq_equalities(THD *thd, SJ_MATERIALIZATION_INFO *sjm,
+ TABLE_LIST *sj_nest)
{
Item *res= NULL;
- if (subq_pred->left_expr->cols() == 1)
+ List_iterator<Item> outer_expr(sj_nest->nested_join->sj_outer_expr_list);
+ Item *outer;
+
+ if (sj_nest->nested_join->sj_outer_expr_list.elements == 1)
{
- if (!(res= new Item_func_eq(subq_pred->left_expr,
- new Item_field(sjm->table->field[0]))))
+ outer = outer_expr++;
+ if (!(res= new Item_func_eq(outer, new Item_field(sjm->table->field[0]))))
return NULL; /* purecov: inspected */
}
else
{
Item *conj;
- for (uint i= 0; i < subq_pred->left_expr->cols(); i++)
+ for (uint i= 0; i < sj_nest->nested_join->sj_outer_expr_list.elements; i++)
{
- if (!(conj= new Item_func_eq(subq_pred->left_expr->element_index(i),
+ outer = outer_expr++;
+ if (!(conj= new Item_func_eq(outer,
new Item_field(sjm->table->field[i]))) ||
!(res= and_items(res, conj)))
return NULL; /* purecov: inspected */
@@ -9772,7 +9838,7 @@ bool setup_sj_materialization(JOIN_TAB *
SJ_MATERIALIZATION_INFO *sjm= emb_sj_nest->sj_mat_info;
THD *thd= tab->join->thd;
/* First the calls come to the materialization function */
- List<Item> &item_list=
emb_sj_nest->sj_subq_pred->unit->first_select()->item_list;
+ List<Item> &item_list= emb_sj_nest->nested_join->sj_inner_exprs;
/*
Set up the table to write to, do as select_union::create_result_table does
@@ -9832,11 +9898,12 @@ bool setup_sj_materialization(JOIN_TAB *
KEY_PART_INFO *cur_key_part= tmp_key->key_part;
store_key **ref_key= tab_ref->key_copy;
uchar *cur_ref_buff= tab_ref->key_buff;
-
+ List_iterator<Item>
+ outer_expr(emb_sj_nest->nested_join->sj_outer_expr_list);
+
for (i= 0; i < tmp_key_parts; i++, cur_key_part++, ref_key++)
{
- tab_ref->items[i]= ((Item_in_subselect *)emb_sj_nest->sj_subq_pred)->
- left_expr->element_index(i);
+ tab_ref->items[i] = outer_expr++;
int null_count= test(cur_key_part->field->real_maybe_null());
*ref_key= new store_key_item(thd, cur_key_part->field,
/* TODO:
@@ -9867,8 +9934,7 @@ bool setup_sj_materialization(JOIN_TAB *
if (tab[i].select)
remove_sj_conds(&tab[i].select->cond);
}
- if (!(sjm->in_equality= create_subq_in_equalities(thd, sjm,
- (Item_in_subselect*)emb_sj_nest->sj_subq_pred)))
+ if (!(sjm->in_equality= create_subq_equalities(thd, sjm, emb_sj_nest)))
DBUG_RETURN(TRUE); /* purecov: inspected */
}
else
@@ -18059,6 +18125,27 @@ make_cond_for_table_from_pred(COND *root
return cond;
}
+
+/*
+ Generate a condition that can be checked after materializing a semi-join nest
+
+ SYNOPSIS
+ make_cond_after_sjm()
+ cond Condition to analyze
+ tables Tables in the outer part of the join nest
+ sjm_tables Tables within the semi-join nest (the inner part)
+
+ DESCRIPTION
+ A regular semi-join materialization is always non-correlated, ie
+ the subquery is always resolved by performing a lookup generated in
+ create_subq_equalities, hence this routine should never produce
+ any condition for regular semi-join materialization.
+ For a scan semi-join materialization, this function may return a condition
+ to be checked.
+
+ RETURN
+ Generated condition
+*/
static COND *
make_cond_after_sjm(Item *root_cond, Item *cond, table_map tables,
=== modified file 'sql/table.h'
--- a/sql/table.h 2008-12-30 01:06:02 +0000
+++ b/sql/table.h 2009-01-05 12:09:10 +0000
@@ -1087,8 +1087,6 @@ struct TABLE_LIST
nest's children).
*/
table_map sj_inner_tables;
- /* Number of IN-compared expressions */
- uint sj_in_exprs;
Item_exists_subselect *sj_subq_pred;
SJ_MATERIALIZATION_INFO *sj_mat_info;
@@ -1659,6 +1657,7 @@ typedef struct st_nested_join
/* Outer non-trivially correlated tables */
table_map sj_corr_tables;
List<Item> sj_outer_expr_list;
+ List<Item> sj_inner_exprs;
} NESTED_JOIN;
| Thread | ||
|---|---|---|
| • bzr commit into mysql-6.0-exists2in branch (roy.lyseng:2726) WL#4389 | Roy Lyseng | 5 Jan 2009 |
© 1995-2008 MySQL AB, 2008-2009 Sun Microsystems, Inc.
Page generated in 0.920 sec. using MySQL 5.1.14-beta-log