- developers - lists.mariadb.org

[Maria-developers] Rev 2820: Apply Evgen's fix: in file:///home/psergey/dev/mysql-next-fix-subq-r2/
by Sergey Petrunya 29 Jul '09

29 Jul '09

At file:///home/psergey/dev/mysql-next-fix-subq-r2/ ------------------------------------------------------------ revno: 2820 revision-id: psergey(a)askmonty.org-20090729161849-ynumr03ety244ueu parent: psergey(a)askmonty.org-20090708174703-dz9uf5b0m6pcvtl6 committer: Sergey Petrunya <psergey(a)askmonty.org> branch nick: mysql-next-fix-subq-r2 timestamp: Wed 2009-07-29 20:18:49 +0400 message: Apply Evgen's fix: Bug#45174: Incorrectly applied equality propagation caused wrong result on a query with a materialized semi-join. 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. Materialized semi-joins are exception to this rule. For field which belongs to a table within a materialized semi-join, we can only pick fields from the same semi-join. 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 is_sj_materialization_strategy method is added to the JOIN_TAB class to check whether JOIN_TAB belongs to a materialized semi-join. === modified file 'mysql-test/r/subselect3.result' --- a/mysql-test/r/subselect3.result 2009-04-30 19:37:21 +0000 +++ b/mysql-test/r/subselect3.result 2009-07-29 16:18:49 +0000 @@ -1081,8 +1081,8 @@ insert into t3 select A.a + 10*B.a, 'filler' from t0 A, t0 B; explain select * from t3 where a in (select a from t2) and (a > 5 or a < 10); id select_type table type possible_keys key key_len ref rows Extra -1 PRIMARY t2 ALL NULL NULL NULL NULL 2 Using where; Materialize; Scan -1 PRIMARY t3 ref a a 5 test.t2.a 1 +1 PRIMARY t2 ALL NULL NULL NULL NULL 2 Materialize; Scan +1 PRIMARY t3 ref a a 5 test.t2.a 1 Using index condition select * from t3 where a in (select a from t2); a filler 1 filler @@ -1129,8 +1129,8 @@ explain select * from t1, t3 where t3.a in (select a from t2) and (t3.a < 10 or t3.a >30) and t1.a =3; id select_type table type possible_keys key key_len ref rows Extra 1 PRIMARY t1 ALL NULL NULL NULL NULL 10 Using where -1 PRIMARY t2 ALL NULL NULL NULL NULL 10 Using where; Materialize; Scan -1 PRIMARY t3 ref a a 5 test.t2.a 10 +1 PRIMARY t2 ALL NULL NULL NULL NULL 10 Materialize; Scan +1 PRIMARY t3 ref a a 5 test.t2.a 10 Using index condition explain select straight_join * from t1 A, t1 B where A.a in (select a from t2); id select_type table type possible_keys key key_len ref rows Extra 1 PRIMARY A ALL NULL NULL NULL NULL 10 Using where @@ -1158,14 +1158,14 @@ explain select * from t0, t3 where t3.a in (select a from t2) and (t3.a < 10 or t3.a >30); id select_type table type possible_keys key key_len ref rows Extra 1 PRIMARY t0 system NULL NULL NULL NULL 1 -1 PRIMARY t2 ALL NULL NULL NULL NULL 10 Using where; Materialize; Scan -1 PRIMARY t3 ref a a 5 test.t2.a 10 +1 PRIMARY t2 ALL NULL NULL NULL NULL 10 Materialize; Scan +1 PRIMARY t3 ref a a 5 test.t2.a 10 Using index condition create table t4 as select a as x, a as y from t1; explain select * from t0, t3 where (t3.a, t3.b) in (select x,y from t4) and (t3.a < 10 or t3.a >30); id select_type table type possible_keys key key_len ref rows Extra 1 PRIMARY t0 system NULL NULL NULL NULL 1 -1 PRIMARY t4 ALL NULL NULL NULL NULL 10 Using where; Materialize; Scan -1 PRIMARY t3 ref a a 5 test.t4.x 10 Using where +1 PRIMARY t4 ALL NULL NULL NULL NULL 10 Materialize; Scan +1 PRIMARY t3 ref a a 5 test.t4.x 10 Using index condition; Using where drop table t0,t1,t2,t3,t4; create table t0 (a int); insert into t0 values (0),(1),(2),(3),(4),(5),(6),(7),(8),(9); === modified file 'mysql-test/r/subselect3_jcl6.result' --- a/mysql-test/r/subselect3_jcl6.result 2009-04-30 19:37:21 +0000 +++ b/mysql-test/r/subselect3_jcl6.result 2009-07-29 16:18:49 +0000 @@ -1086,8 +1086,8 @@ insert into t3 select A.a + 10*B.a, 'filler' from t0 A, t0 B; explain select * from t3 where a in (select a from t2) and (a > 5 or a < 10); id select_type table type possible_keys key key_len ref rows Extra -1 PRIMARY t2 ALL NULL NULL NULL NULL 2 Using where; Materialize; Scan -1 PRIMARY t3 ref a a 5 test.t2.a 1 Using join buffer +1 PRIMARY t2 ALL NULL NULL NULL NULL 2 Materialize; Scan +1 PRIMARY t3 ref a a 5 test.t2.a 1 Using index condition; Using join buffer select * from t3 where a in (select a from t2); a filler 1 filler @@ -1134,8 +1134,8 @@ explain select * from t1, t3 where t3.a in (select a from t2) and (t3.a < 10 or t3.a >30) and t1.a =3; id select_type table type possible_keys key key_len ref rows Extra 1 PRIMARY t1 ALL NULL NULL NULL NULL 10 Using where -1 PRIMARY t2 ALL NULL NULL NULL NULL 10 Using where; Materialize; Scan -1 PRIMARY t3 ref a a 5 test.t2.a 10 Using join buffer +1 PRIMARY t2 ALL NULL NULL NULL NULL 10 Materialize; Scan +1 PRIMARY t3 ref a a 5 test.t2.a 10 Using index condition; Using join buffer explain select straight_join * from t1 A, t1 B where A.a in (select a from t2); id select_type table type possible_keys key key_len ref rows Extra 1 PRIMARY A ALL NULL NULL NULL NULL 10 Using where @@ -1163,14 +1163,14 @@ explain select * from t0, t3 where t3.a in (select a from t2) and (t3.a < 10 or t3.a >30); id select_type table type possible_keys key key_len ref rows Extra 1 PRIMARY t0 system NULL NULL NULL NULL 1 -1 PRIMARY t2 ALL NULL NULL NULL NULL 10 Using where; Materialize; Scan -1 PRIMARY t3 ref a a 5 test.t2.a 10 Using join buffer +1 PRIMARY t2 ALL NULL NULL NULL NULL 10 Materialize; Scan +1 PRIMARY t3 ref a a 5 test.t2.a 10 Using index condition; Using join buffer create table t4 as select a as x, a as y from t1; explain select * from t0, t3 where (t3.a, t3.b) in (select x,y from t4) and (t3.a < 10 or t3.a >30); id select_type table type possible_keys key key_len ref rows Extra 1 PRIMARY t0 system NULL NULL NULL NULL 1 -1 PRIMARY t4 ALL NULL NULL NULL NULL 10 Using where; Materialize; Scan -1 PRIMARY t3 ref a a 5 test.t4.x 10 Using where; Using join buffer +1 PRIMARY t4 ALL NULL NULL NULL NULL 10 Materialize; Scan +1 PRIMARY t3 ref a a 5 test.t4.x 10 Using index condition; Using where; Using join buffer drop table t0,t1,t2,t3,t4; create table t0 (a int); insert into t0 values (0),(1),(2),(3),(4),(5),(6),(7),(8),(9); === modified file 'mysql-test/r/subselect_sj.result' --- a/mysql-test/r/subselect_sj.result 2009-07-06 07:57:39 +0000 +++ b/mysql-test/r/subselect_sj.result 2009-07-29 16:18:49 +0000 @@ -372,3 +372,39 @@ 3 2 drop table t1, t2, t3; +# +# 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-07-06 07:57:39 +0000 +++ b/mysql-test/r/subselect_sj_jcl6.result 2009-07-29 16:18:49 +0000 @@ -376,6 +376,42 @@ 3 2 drop table t1, t2, t3; +# +# 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-07-06 07:57:39 +0000 +++ b/mysql-test/t/subselect_sj.test 2009-07-29 16:18:49 +0000 @@ -22,7 +22,6 @@ create table t12 like t10; insert into t12 select * from t10; - --echo Flattened because of dependency, t10=func(t1) explain select * from t1 where a in (select pk from t10); select * from t1 where a in (select pk from t10); @@ -252,3 +251,43 @@ where a in (select c from t2 where d >= some(select e from t3 where b=e)); drop table t1, t2, t3; + +--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-07-06 07:57:39 +0000 +++ b/sql/item.cc 2009-07-29 16:18:49 +0000 @@ -4895,7 +4895,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 2009-07-06 07:57:39 +0000 +++ b/sql/item_cmpfunc.cc 2009-07-29 16:18:49 +0000 @@ -5377,7 +5377,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); } @@ -5440,3 +5440,107 @@ str->append(')'); } + +/* + @brief Get the first 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 the 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 no field is given or the field doesn't belong to a semi-join then + the first field in the multiple equality is returned. + + @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->is_sj_materialization_strategy()) + { + /* + 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->is_sj_materialization_strategy()) + return item; + } + } + // Shouldn't get here. + DBUG_ASSERT(0); + return NULL; +} === modified file 'sql/item_cmpfunc.h' --- a/sql/item_cmpfunc.h 2009-07-06 07:57:39 +0000 +++ b/sql/item_cmpfunc.h 2009-07-29 16:18:49 +0000 @@ -1593,7 +1593,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); 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-07-06 14:33:29 +0000 +++ b/sql/sql_select.cc 2009-07-29 16:18:49 +0000 @@ -10379,6 +10379,21 @@ /** + Check whether the JOIN_TAB belongs to a materialized semi-join. +*/ + +bool JOIN_TAB::is_sj_materialization_strategy() +{ + uint tab_idx= this - join->join_tab; + + return (emb_sj_nest && + ((join->best_positions[tab_idx].sj_strategy == SJ_OPT_MATERIALIZE || + join->best_positions[tab_idx].sj_strategy == SJ_OPT_MATERIALIZE_SCAN))); + +} + + +/** Partially cleanup JOIN after it has executed: close index or rnd read (table cursors), free quick selects. @@ -11720,7 +11735,7 @@ 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-07-29 16:18:49 +0000 @@ -332,6 +332,7 @@ return first_inner; return first_sj_inner_tab; } + bool is_sj_materialization_strategy(); } JOIN_TAB; /*

1 0

[Maria-developers] new buildbot report at askmonty
by Bryan Alsdorf 28 Jul '09

28 Jul '09

Hi all, Last week I pushed a new report for buildbot live and after a few tweaks wanted to send out an email on it. The report is located here: http://askmonty.org/buildbot/reports/ At the moment we only have the "cross reference" report, more reports will be added in the future. The cross reference report lists all test failures matching your search (to view all data just click "search" with no parameters"). You can click on a row to display the full test failure text. Currently there are only a few test failures listed but all future failures will appear on this report. If you have any questions or comments feel free to email the list, me directly or hop on #maria Best Regards, -- Bryan Alsdorf, Lead Web Developer Monty Program, AB. http://askmonty.org

3 3

[Maria-developers] Rev 2717: WL#4800: Optimizer trace in file:///home/psergey/dev/maria-5.1-opt-trace/
by Sergey Petrunya 23 Jul '09

23 Jul '09

At file:///home/psergey/dev/maria-5.1-opt-trace/ ------------------------------------------------------------ revno: 2717 revision-id: psergey(a)askmonty.org-20090723174522-99j6if4ay9r341qg parent: knielsen(a)knielsen-hq.org-20090707111924-e44ycwmckomk13qz committer: Sergey Petrunya <psergey(a)askmonty.org> branch nick: maria-5.1-opt-trace timestamp: Thu 2009-07-23 21:45:22 +0400 message: WL#4800: Optimizer trace - Port current state to MariaDB Diff too large for email (1909 lines, the limit is 1000).

1 0

[Maria-developers] Rev 2717: WL#4800: Optimizer trace in file:///home/psergey/dev/maria-5.1-opt-trace/
by Sergey Petrunya 23 Jul '09

23 Jul '09

At file:///home/psergey/dev/maria-5.1-opt-trace/ ------------------------------------------------------------ revno: 2717 revision-id: psergey(a)askmonty.org-20090723174047-982pmyty704c5bgu parent: knielsen(a)knielsen-hq.org-20090707111924-e44ycwmckomk13qz committer: Sergey Petrunya <psergey(a)askmonty.org> branch nick: maria-5.1-opt-trace timestamp: Thu 2009-07-23 21:40:47 +0400 message: WL#4800: Optimizer trace - Port of current state to mariadb-5.1 Diff too large for email (1354 lines, the limit is 1000).

1 0

[Maria-developers] Updated (by Guest): Table elimination: all tasks (29)
by worklog-noreply＠askmonty.org 23 Jul '09

23 Jul '09

----------------------------------------------------------------------- WORKLOG TASK -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- TASK...........: Table elimination: all tasks CREATION DATE..: Wed, 03 Jun 2009, 12:07 SUPERVISOR.....: Monty IMPLEMENTOR....: COPIES TO......: Psergey CATEGORY.......: Server-Sprint TASK ID........: 29 (http://askmonty.org/worklog/?tid=29) VERSION........: Server-5.1 STATUS.........: In-Progress PRIORITY.......: 60 WORKED HOURS...: 0 ESTIMATE.......: 0 (hours remain) ORIG. ESTIMATE.: 0 PROGRESS NOTES: -=-=(Guest - Thu, 23 Jul 2009, 20:13)=-=- Version updated. --- /tmp/wklog.29.old.17550 2009-07-23 20:13:44.000000000 +0300 +++ /tmp/wklog.29.new.17550 2009-07-23 20:13:44.000000000 +0300 @@ -1 +1 @@ -Server-4.0 +Server-5.1 -=-=(Guest - Thu, 23 Jul 2009, 20:09)=-=- Version updated. --- /tmp/wklog.29.old.17326 2009-07-23 20:09:38.000000000 +0300 +++ /tmp/wklog.29.new.17326 2009-07-23 20:09:38.000000000 +0300 @@ -1 +1 @@ -Server-9.x +Server-4.0 -=-=(Guest - Thu, 23 Jul 2009, 20:07)=-=- Dependency created: 29 now depends on 17 -=-=(Guest - Tue, 16 Jun 2009, 17:03)=-=- Dependency deleted: 29 no longer depends on 20 -=-=(Guest - Tue, 16 Jun 2009, 17:01)=-=- Dependency deleted: 29 no longer depends on 17 -=-=(Psergey - Wed, 03 Jun 2009, 12:07)=-=- Dependency created: 29 now depends on 20 -=-=(Psergey - Wed, 03 Jun 2009, 12:07)=-=- Dependency created: 29 now depends on 17 DESCRIPTION: This WL entry groups all table elimination tasks. ESTIMATED WORK TIME ESTIMATED COMPLETION DATE ----------------------------------------------------------------------- WorkLog (v3.5.9)

1 0

[Maria-developers] Updated (by Guest): Table elimination: all tasks (29)
by worklog-noreply＠askmonty.org 23 Jul '09

23 Jul '09

----------------------------------------------------------------------- WORKLOG TASK -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- TASK...........: Table elimination: all tasks CREATION DATE..: Wed, 03 Jun 2009, 12:07 SUPERVISOR.....: Monty IMPLEMENTOR....: COPIES TO......: Psergey CATEGORY.......: Server-Sprint TASK ID........: 29 (http://askmonty.org/worklog/?tid=29) VERSION........: Server-5.1 STATUS.........: In-Progress PRIORITY.......: 60 WORKED HOURS...: 0 ESTIMATE.......: 0 (hours remain) ORIG. ESTIMATE.: 0 PROGRESS NOTES: -=-=(Guest - Thu, 23 Jul 2009, 20:13)=-=- Version updated. --- /tmp/wklog.29.old.17550 2009-07-23 20:13:44.000000000 +0300 +++ /tmp/wklog.29.new.17550 2009-07-23 20:13:44.000000000 +0300 @@ -1 +1 @@ -Server-4.0 +Server-5.1 -=-=(Guest - Thu, 23 Jul 2009, 20:09)=-=- Version updated. --- /tmp/wklog.29.old.17326 2009-07-23 20:09:38.000000000 +0300 +++ /tmp/wklog.29.new.17326 2009-07-23 20:09:38.000000000 +0300 @@ -1 +1 @@ -Server-9.x +Server-4.0 -=-=(Guest - Thu, 23 Jul 2009, 20:07)=-=- Dependency created: 29 now depends on 17 -=-=(Guest - Tue, 16 Jun 2009, 17:03)=-=- Dependency deleted: 29 no longer depends on 20 -=-=(Guest - Tue, 16 Jun 2009, 17:01)=-=- Dependency deleted: 29 no longer depends on 17 -=-=(Psergey - Wed, 03 Jun 2009, 12:07)=-=- Dependency created: 29 now depends on 20 -=-=(Psergey - Wed, 03 Jun 2009, 12:07)=-=- Dependency created: 29 now depends on 17 DESCRIPTION: This WL entry groups all table elimination tasks. ESTIMATED WORK TIME ESTIMATED COMPLETION DATE ----------------------------------------------------------------------- WorkLog (v3.5.9)

1 0

[Maria-developers] Updated (by Guest): Table elimination: all tasks (29)
by worklog-noreply＠askmonty.org 23 Jul '09

23 Jul '09

----------------------------------------------------------------------- WORKLOG TASK -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- TASK...........: Table elimination: all tasks CREATION DATE..: Wed, 03 Jun 2009, 12:07 SUPERVISOR.....: Monty IMPLEMENTOR....: COPIES TO......: Psergey CATEGORY.......: Server-Sprint TASK ID........: 29 (https://askmonty.org/worklog/?tid=29) VERSION........: Server-4.0 STATUS.........: In-Progress PRIORITY.......: 60 WORKED HOURS...: 0 ESTIMATE.......: 0 (hours remain) ORIG. ESTIMATE.: 0 PROGRESS NOTES: -=-=(Guest - Thu, 23 Jul 2009, 20:09)=-=- Version updated. --- /tmp/wklog.29.old.17326 2009-07-23 20:09:38.000000000 +0300 +++ /tmp/wklog.29.new.17326 2009-07-23 20:09:38.000000000 +0300 @@ -1 +1 @@ -Server-9.x +Server-4.0 -=-=(Guest - Thu, 23 Jul 2009, 20:07)=-=- Dependency created: 29 now depends on 17 -=-=(Guest - Tue, 16 Jun 2009, 17:03)=-=- Dependency deleted: 29 no longer depends on 20 -=-=(Guest - Tue, 16 Jun 2009, 17:01)=-=- Dependency deleted: 29 no longer depends on 17 -=-=(Psergey - Wed, 03 Jun 2009, 12:07)=-=- Dependency created: 29 now depends on 20 -=-=(Psergey - Wed, 03 Jun 2009, 12:07)=-=- Dependency created: 29 now depends on 17 DESCRIPTION: This WL entry groups all table elimination tasks. ESTIMATED WORK TIME ESTIMATED COMPLETION DATE ----------------------------------------------------------------------- WorkLog (v3.5.9)

1 0

[Maria-developers] Updated (by Guest): Table elimination: all tasks (29)
by worklog-noreply＠askmonty.org 23 Jul '09

23 Jul '09

----------------------------------------------------------------------- WORKLOG TASK -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- TASK...........: Table elimination: all tasks CREATION DATE..: Wed, 03 Jun 2009, 12:07 SUPERVISOR.....: Monty IMPLEMENTOR....: COPIES TO......: Psergey CATEGORY.......: Server-Sprint TASK ID........: 29 (https://askmonty.org/worklog/?tid=29) VERSION........: Server-4.0 STATUS.........: In-Progress PRIORITY.......: 60 WORKED HOURS...: 0 ESTIMATE.......: 0 (hours remain) ORIG. ESTIMATE.: 0 PROGRESS NOTES: -=-=(Guest - Thu, 23 Jul 2009, 20:09)=-=- Version updated. --- /tmp/wklog.29.old.17326 2009-07-23 20:09:38.000000000 +0300 +++ /tmp/wklog.29.new.17326 2009-07-23 20:09:38.000000000 +0300 @@ -1 +1 @@ -Server-9.x +Server-4.0 -=-=(Guest - Thu, 23 Jul 2009, 20:07)=-=- Dependency created: 29 now depends on 17 -=-=(Guest - Tue, 16 Jun 2009, 17:03)=-=- Dependency deleted: 29 no longer depends on 20 -=-=(Guest - Tue, 16 Jun 2009, 17:01)=-=- Dependency deleted: 29 no longer depends on 17 -=-=(Psergey - Wed, 03 Jun 2009, 12:07)=-=- Dependency created: 29 now depends on 20 -=-=(Psergey - Wed, 03 Jun 2009, 12:07)=-=- Dependency created: 29 now depends on 17 DESCRIPTION: This WL entry groups all table elimination tasks. ESTIMATED WORK TIME ESTIMATED COMPLETION DATE ----------------------------------------------------------------------- WorkLog (v3.5.9)

1 0

[Maria-developers] Updated (by Monty): Table elimination (17)
by worklog-noreply＠askmonty.org 23 Jul '09

23 Jul '09

----------------------------------------------------------------------- WORKLOG TASK -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- TASK...........: Table elimination CREATION DATE..: Sun, 10 May 2009, 19:57 SUPERVISOR.....: Monty IMPLEMENTOR....: Psergey COPIES TO......: CATEGORY.......: Client-BackLog TASK ID........: 17 (http://askmonty.org/worklog/?tid=17) VERSION........: Server-5.1 STATUS.........: In-Progress PRIORITY.......: 60 WORKED HOURS...: 1 ESTIMATE.......: 3 (hours remain) ORIG. ESTIMATE.: 3 PROGRESS NOTES: -=-=(Monty - Thu, 23 Jul 2009, 09:19)=-=- Version updated. --- /tmp/wklog.17.old.24090 2009-07-23 09:19:32.000000000 +0300 +++ /tmp/wklog.17.new.24090 2009-07-23 09:19:32.000000000 +0300 @@ -1 +1 @@ -Server-9.x +Server-5.1 -=-=(Guest - Mon, 20 Jul 2009, 14:28)=-=- deukje weg Worked 1 hour and estimate 3 hours remain (original estimate increased by 4 hours). -=-=(Guest - Fri, 17 Jul 2009, 02:44)=-=- Version updated. --- /tmp/wklog.17.old.24138 2009-07-17 02:44:49.000000000 +0300 +++ /tmp/wklog.17.new.24138 2009-07-17 02:44:49.000000000 +0300 @@ -1 +1 @@ -9.x +Server-9.x -=-=(Guest - Fri, 17 Jul 2009, 02:44)=-=- Version updated. --- /tmp/wklog.17.old.24114 2009-07-17 02:44:36.000000000 +0300 +++ /tmp/wklog.17.new.24114 2009-07-17 02:44:36.000000000 +0300 @@ -1 +1 @@ -Server-5.1 +9.x -=-=(Guest - Fri, 17 Jul 2009, 02:44)=-=- Category updated. --- /tmp/wklog.17.old.24114 2009-07-17 02:44:36.000000000 +0300 +++ /tmp/wklog.17.new.24114 2009-07-17 02:44:36.000000000 +0300 @@ -1 +1 @@ -Server-Sprint +Client-BackLog -=-=(Guest - Thu, 18 Jun 2009, 04:15)=-=- Low Level Design modified. --- /tmp/wklog.17.old.29969 2009-06-18 04:15:23.000000000 +0300 +++ /tmp/wklog.17.new.29969 2009-06-18 04:15:23.000000000 +0300 @@ -158,3 +158,43 @@ from user/EXPLAIN point of view: no. constant table is the one that we read one record from. eliminated table is the one that we don't acccess at all. +* What is described above will not be able to eliminate this outer join + create unique index idx on tableB (id, fromDate); + ... + left outer join + tableB B + on + B.id = A.id + and + B.fromDate = (select max(sub.fromDate) + from tableB sub where sub.id = A.id); + + This is because condition "B.fromDate= func(tableB)" cannot be used. + Reason#1: update_ref_and_keys() does not consider such conditions to + be of any use (and indeed they are not usable for ref access) + so they are not put into KEYUSE array. + Reason#2: even if they were put there, we would need to be able to tell + between predicates like + B.fromDate= func(B.id) // guarantees only one matching row as + // B.id is already bound by B.id=A.id + // hence B.fromDate becomes bound too. + and + "B.fromDate= func(B.*)" // Can potentially have many matching + // records. + We need to + - Have update_ref_and_keys() create KEYUSE elements for such equalities + - Have eliminate_tables() and friends make a more accurate check. + The right check is to check whether all parts of a unique key are bound. + If we have keypartX to be bound, then t.keypartY=func(keypartX) makes + keypartY to be bound. + The difficulty here is that correlated subquery predicate cannot tell what + columns it depends on (it only remembers tables). + Traversing the predicate is expensive and complicated. + We're leaning towards making each subquery predicate have a List<Item> with + items that + - are in the current select + - and it depends on. + This list will be useful in certain other subquery optimizations as well, + it is cheap to collect it in fix_fields() phase, so it will be collected + for every subquery predicate. + -=-=(Guest - Thu, 18 Jun 2009, 02:48)=-=- Low Level Design modified. --- /tmp/wklog.17.old.27792 2009-06-18 02:48:45.000000000 +0300 +++ /tmp/wklog.17.new.27792 2009-06-18 02:48:45.000000000 +0300 @@ -89,14 +89,14 @@ - queries that would use elimination - queries that are very similar to one above (so that they would have same QEP, execution cost, etc) but cannot use table elimination. +then compare run times and make a conclusion about whether dbms supports table +elimination. 6. Todo, issues to resolve -------------------------- 6.1 To resolve ~~~~~~~~~~~~~~ -- Re-check how this works with equality propagation. - - Relationship with prepared statements. On one hand, it's natural to desire to make table elimination a once-per-statement operation, like outer->inner join conversion. We'll have @@ -141,8 +141,13 @@ 7. Additional issues -------------------- -* We remove ON clauses within semi-join nests. If these clauses contain +* We remove ON clauses within outer join nests. If these clauses contain subqueries, they probably should be gone from EXPLAIN output also? + Yes. Current approach: when removing an outer join nest, walk the ON clause + and mark subselects as eliminated. Then let EXPLAIN code check if the + SELECT was eliminated before the printing (EXPLAIN is generated by doing + a recursive descent, so the check will also cause children of eliminated + selects not to be printed) * Table elimination is performed after constant table detection (but before the range analysis). Constant tables are technically different from -=-=(Guest - Thu, 18 Jun 2009, 02:24)=-=- Low Level Design modified. --- /tmp/wklog.17.old.27162 2009-06-18 02:24:14.000000000 +0300 +++ /tmp/wklog.17.new.27162 2009-06-18 02:24:14.000000000 +0300 @@ -83,9 +83,12 @@ 5. Tests and benchmarks ----------------------- -Should create a benchmark in sql-bench which checks if the dbms has table +Create a benchmark in sql-bench which checks if the DBMS has table elimination. -TODO elaborate +[According to Monty] Run + - queries that would use elimination + - queries that are very similar to one above (so that they would have same + QEP, execution cost, etc) but cannot use table elimination. 6. Todo, issues to resolve -------------------------- @@ -109,33 +112,37 @@ 6.2 Resolved ~~~~~~~~~~~~ -- outer->inner join conversion is not a problem for table elimination. +* outer->inner join conversion is not a problem for table elimination. We make outer->inner conversions based on predicates in WHERE. If the WHERE referred to an inner table (requirement for OJ->IJ conversion) then table elimination would not be applicable anyway. -7. Additional issues --------------------- -* We remove ON clauses within semi-join nests. If these clauses contain - subqueries, they probably should be gone from EXPLAIN output also? +* For Multi-table UPDATEs/DELETEs, need to also analyze the SET clause: + - affected tables must not be eliminated + - tables that are used on the right side of the SET x=y assignments must + not be eliminated either. -* Aggregate functions report they depend on all tables, that is, +* Aggregate functions used to report that they depend on all tables, that is, item_agg_func->used_tables() == (1ULL << join->tables) - 1 - always. If we want table elimination to work in presence of grouping, need - to devise some other way of analyzing aggregate functions. + always. Fixed it, now aggregate function reports it depends on + tables that its arguments depend on. In particular, COUNT(*) reports + that it depends on no tables (item_count_star->used_tables()==0). + One consequence of that is that "item->used_tables()==0" is not + equivalent to "item->const_item()==true" anymore (not sure if it's + "anymore" or this has been already happening). + +* EXPLAIN EXTENDED warning text was generated after the JOIN object has + been discarded. This didn't allow to use information about join plan + when printing the warning. Fixed this by keeping the JOIN objects until + we've printed the warning (have also an intent to remove the const + tables from the join output). -* Should eliminated tables be shown in EXPLAIN EXTENDED? - - If we just ignore the question, they will be shown - - this is what happens for constant tables, too. - - I don't see how showing them could be of any use. They only make it - harder to read the rewritten query. - It turns out that - - it is easy to have EXPLAIN EXTENDED show permanent (once-per-statement - lifetime) changes. - - it is hard to have it show per-execution data. This is because the warning - text is generated after the execution structures have been destroyed. +7. Additional issues +-------------------- +* We remove ON clauses within semi-join nests. If these clauses contain + subqueries, they probably should be gone from EXPLAIN output also? * Table elimination is performed after constant table detection (but before the range analysis). Constant tables are technically different from @@ -143,8 +150,6 @@ Considering we've already done the join_read_const_table() call, is there any real difference between constant table and eliminated one? If there is, should we mark const tables also as eliminated? + from user/EXPLAIN point of view: no. constant table is the one that we read + one record from. eliminated table is the one that we don't acccess at all. -* For Multi-table UPDATEs/DELETEs, need to also analyze the SET clause: - - affected tables must not be eliminated - - tables that are used on the right side of the SET x=y assignments must - not be eliminated either. -=-=(Guest - Tue, 16 Jun 2009, 17:01)=-=- Dependency deleted: 29 no longer depends on 17 -=-=(Guest - Wed, 10 Jun 2009, 01:23)=-=- Low Level Design modified. --- /tmp/wklog.17.old.1842 2009-06-10 01:23:42.000000000 +0300 +++ /tmp/wklog.17.new.1842 2009-06-10 01:23:42.000000000 +0300 @@ -131,6 +131,11 @@ - this is what happens for constant tables, too. - I don't see how showing them could be of any use. They only make it harder to read the rewritten query. + It turns out that + - it is easy to have EXPLAIN EXTENDED show permanent (once-per-statement + lifetime) changes. + - it is hard to have it show per-execution data. This is because the warning + text is generated after the execution structures have been destroyed. * Table elimination is performed after constant table detection (but before the range analysis). Constant tables are technically different from ------------------------------------------------------------ -=-=(View All Progress Notes, 24 total)=-=- http://askmonty.org/worklog/index.pl?tid=17&nolimit=1 DESCRIPTION: Eliminate not needed tables from SELECT queries.. This will speed up some views and automatically generated queries. Example: CREATE TABLE B (id int primary key); select A.colA from tableA A left outer join tableB B on B.id = A.id; In this case we can remove table B and the join from the query. HIGH-LEVEL SPECIFICATION: Here is an extended explanation of table elimination. Table elimination is a feature found in some modern query optimizers, of which Microsoft SQL Server 2005/2008 seems to have the most advanced implementation. Oracle 11g has also been confirmed to use table elimination but not to the same extent. Basically, what table elimination does, is to remove tables from the execution plan when it is unnecessary to include them. This can, of course, only happen if the right circumstances arise. Let us for example look at the following query: select A.colA from tableA A left outer join tableB B on B.id = A.id; When using A as the left table we ensure that the query will return at least as many rows as there are in that table. For rows where the join condition (B.id = A.id) is not met the selected column (A.colA) will still contain it's original value. The not seen B.* row would contain all NULL:s. However, the result set could actually contain more rows than what is found in tableA if there are duplicates of the column B.id in tableB. If A contains a row [1, "val1"] and B the rows [1, "other1a"],[1, "other1b"] then two rows will match in the join condition. The only way to know what the result will look like is to actually touch both tables during execution. Instead, let's say that tableB contains rows that make it possible to place a unique constraint on the column B.id, for example and often the case a primary key. In this situation we know that we will get exactly as many rows as there are in tableA, since joining with tableB cannot introduce any duplicates. If further, as in the example query, we do not select any columns from tableB, touching that table during execution is unnecessary. We can remove the whole join operation from the execution plan. Both SQL Server 2005/2008 and Oracle 11g will deploy table elimination in the case described above. Let us look at a more advanced query, where Oracle fails. select A.colA from tableA A left outer join tableB B on B.id = A.id and B.fromDate = ( select max(sub.fromDate) from tableB sub where sub.id = A.id ); In this example we have added another join condition, which ensures that we only pick the matching row from tableB having the latest fromDate. In this case tableB will contain duplicates of the column B.id, so in order to ensure uniqueness the primary key has to contain the fromDate column as well. In other words the primary key of tableB is (B.id, B.fromDate). Furthermore, since the subselect ensures that we only pick the latest B.fromDate for a given B.id we know that at most one row will match the join condition. We will again have the situation where joining with tableB cannot affect the number of rows in the result set. Since we do not select any columns from tableB, the whole join operation can be eliminated from the execution plan. SQL Server 2005/2008 will deploy table elimination in this situation as well. We have not found a way to make Oracle 11g use it for this type of query. Queries like these arise in two situations. Either when you have denormalized model consisting of a fact table with several related dimension tables, or when you have a highly normalized model where each attribute is stored in its own table. The example with the subselect is common whenever you store historized/versioned data. LOW-LEVEL DESIGN: The code (currently in development) is at lp: ~maria-captains/maria/maria-5.1-table-elimination tree. <contents> 1. Conditions for removal 1.1 Quick check if there are candidates 2. Removal operation properties 3. Removal operation 4. User interface 5. Tests and benchmarks 6. Todo, issues to resolve 6.1 To resolve 6.2 Resolved 7. Additional issues </contents> It's not really about elimination of tables, it's about elimination of inner sides of outer joins. 1. Conditions for removal ------------------------- We can eliminate an inner side of outer join if: 1. For each record combination of outer tables, it will always produce exactly one record. 2. There are no references to columns of the inner tables anywhere else in the query. #1 means that every table inside the outer join nest is: - is a constant table: = because it can be accessed via eq_ref(const) access, or = it is a zero-rows or one-row MyISAM-like table [MARK1] - has an eq_ref access method candidate. #2 means that WHERE clause, ON clauses of embedding outer joins, ORDER BY, GROUP BY and HAVING do not refer to the inner tables of the outer join nest. 1.1 Quick check if there are candidates ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Before we start to enumerate join nests, here is a quick way to check if there *can be* something to be removed: if ((tables used in select_list | tables used in group/order by UNION | tables used in where) != bitmap_of_all_tables) { attempt table elimination; } 2. Removal operation properties ------------------------------- * There is always one way to remove (no choice to remove either this or that) * It is always better to remove as much tables as possible (at least within our cost model). Thus, no need for any cost calculations/etc. It's an unconditional rewrite. 3. Removal operation -------------------- * Remove the outer join nest's nested join structure (i.e. get the outer join's TABLE_LIST object $OJ and remove it from $OJ->embedding, $OJ->embedding->nested_join. Update table_map's of all ancestor nested joins). [MARK2] * Move the tables and their JOIN_TABs to front like it is done with const tables, with exception that if eliminated outer join nest was within another outer join nest, that shouldn't prevent us from moving away the eliminated tables. * Update join->table_count and all-join-tables bitmap. * That's it. Nothing else? 4. User interface ----------------- * We'll add an @@optimizer switch flag for table elimination. Tentative name: 'table_elimination'. (Note ^^ utility of the above questioned ^, as table elimination can never be worse than no elimination. We're leaning towards not adding the flag) * EXPLAIN will not show the removed tables at all. This will allow to check if tables were removed, and also will behave nicely with anchor model and VIEWs: stuff that user doesn't care about just won't be there. 5. Tests and benchmarks ----------------------- Create a benchmark in sql-bench which checks if the DBMS has table elimination. [According to Monty] Run - queries that would use elimination - queries that are very similar to one above (so that they would have same QEP, execution cost, etc) but cannot use table elimination. then compare run times and make a conclusion about whether dbms supports table elimination. 6. Todo, issues to resolve -------------------------- 6.1 To resolve ~~~~~~~~~~~~~~ - Relationship with prepared statements. On one hand, it's natural to desire to make table elimination a once-per-statement operation, like outer->inner join conversion. We'll have to limit the applicability by removing [MARK1] as that can change during lifetime of the statement. The other option is to do table elimination every time. This will require to rework operation [MARK2] to be undoable. I'm leaning towards doing the former. With anchor modeling, it is unlikely that we'll meet outer joins which have N inner tables of which some are 1-row MyISAM tables that do not have primary key. 6.2 Resolved ~~~~~~~~~~~~ * outer->inner join conversion is not a problem for table elimination. We make outer->inner conversions based on predicates in WHERE. If the WHERE referred to an inner table (requirement for OJ->IJ conversion) then table elimination would not be applicable anyway. * For Multi-table UPDATEs/DELETEs, need to also analyze the SET clause: - affected tables must not be eliminated - tables that are used on the right side of the SET x=y assignments must not be eliminated either. * Aggregate functions used to report that they depend on all tables, that is, item_agg_func->used_tables() == (1ULL << join->tables) - 1 always. Fixed it, now aggregate function reports it depends on tables that its arguments depend on. In particular, COUNT(*) reports that it depends on no tables (item_count_star->used_tables()==0). One consequence of that is that "item->used_tables()==0" is not equivalent to "item->const_item()==true" anymore (not sure if it's "anymore" or this has been already happening). * EXPLAIN EXTENDED warning text was generated after the JOIN object has been discarded. This didn't allow to use information about join plan when printing the warning. Fixed this by keeping the JOIN objects until we've printed the warning (have also an intent to remove the const tables from the join output). 7. Additional issues -------------------- * We remove ON clauses within outer join nests. If these clauses contain subqueries, they probably should be gone from EXPLAIN output also? Yes. Current approach: when removing an outer join nest, walk the ON clause and mark subselects as eliminated. Then let EXPLAIN code check if the SELECT was eliminated before the printing (EXPLAIN is generated by doing a recursive descent, so the check will also cause children of eliminated selects not to be printed) * Table elimination is performed after constant table detection (but before the range analysis). Constant tables are technically different from eliminated ones (e.g. the former are shown in EXPLAIN and the latter aren't). Considering we've already done the join_read_const_table() call, is there any real difference between constant table and eliminated one? If there is, should we mark const tables also as eliminated? from user/EXPLAIN point of view: no. constant table is the one that we read one record from. eliminated table is the one that we don't acccess at all. * What is described above will not be able to eliminate this outer join create unique index idx on tableB (id, fromDate); ... left outer join tableB B on B.id = A.id and B.fromDate = (select max(sub.fromDate) from tableB sub where sub.id = A.id); This is because condition "B.fromDate= func(tableB)" cannot be used. Reason#1: update_ref_and_keys() does not consider such conditions to be of any use (and indeed they are not usable for ref access) so they are not put into KEYUSE array. Reason#2: even if they were put there, we would need to be able to tell between predicates like B.fromDate= func(B.id) // guarantees only one matching row as // B.id is already bound by B.id=A.id // hence B.fromDate becomes bound too. and "B.fromDate= func(B.*)" // Can potentially have many matching // records. We need to - Have update_ref_and_keys() create KEYUSE elements for such equalities - Have eliminate_tables() and friends make a more accurate check. The right check is to check whether all parts of a unique key are bound. If we have keypartX to be bound, then t.keypartY=func(keypartX) makes keypartY to be bound. The difficulty here is that correlated subquery predicate cannot tell what columns it depends on (it only remembers tables). Traversing the predicate is expensive and complicated. We're leaning towards making each subquery predicate have a List<Item> with items that - are in the current select - and it depends on. This list will be useful in certain other subquery optimizations as well, it is cheap to collect it in fix_fields() phase, so it will be collected for every subquery predicate. ESTIMATED WORK TIME ESTIMATED COMPLETION DATE ----------------------------------------------------------------------- WorkLog (v3.5.9)

1 0

[Maria-developers] Updated (by Monty): Table elimination (17)
by worklog-noreply＠askmonty.org 23 Jul '09

23 Jul '09

----------------------------------------------------------------------- WORKLOG TASK -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- TASK...........: Table elimination CREATION DATE..: Sun, 10 May 2009, 19:57 SUPERVISOR.....: Monty IMPLEMENTOR....: Psergey COPIES TO......: CATEGORY.......: Client-BackLog TASK ID........: 17 (http://askmonty.org/worklog/?tid=17) VERSION........: Server-5.1 STATUS.........: In-Progress PRIORITY.......: 60 WORKED HOURS...: 1 ESTIMATE.......: 3 (hours remain) ORIG. ESTIMATE.: 3 PROGRESS NOTES: -=-=(Monty - Thu, 23 Jul 2009, 09:19)=-=- Version updated. --- /tmp/wklog.17.old.24090 2009-07-23 09:19:32.000000000 +0300 +++ /tmp/wklog.17.new.24090 2009-07-23 09:19:32.000000000 +0300 @@ -1 +1 @@ -Server-9.x +Server-5.1 -=-=(Guest - Mon, 20 Jul 2009, 14:28)=-=- deukje weg Worked 1 hour and estimate 3 hours remain (original estimate increased by 4 hours). -=-=(Guest - Fri, 17 Jul 2009, 02:44)=-=- Version updated. --- /tmp/wklog.17.old.24138 2009-07-17 02:44:49.000000000 +0300 +++ /tmp/wklog.17.new.24138 2009-07-17 02:44:49.000000000 +0300 @@ -1 +1 @@ -9.x +Server-9.x -=-=(Guest - Fri, 17 Jul 2009, 02:44)=-=- Version updated. --- /tmp/wklog.17.old.24114 2009-07-17 02:44:36.000000000 +0300 +++ /tmp/wklog.17.new.24114 2009-07-17 02:44:36.000000000 +0300 @@ -1 +1 @@ -Server-5.1 +9.x -=-=(Guest - Fri, 17 Jul 2009, 02:44)=-=- Category updated. --- /tmp/wklog.17.old.24114 2009-07-17 02:44:36.000000000 +0300 +++ /tmp/wklog.17.new.24114 2009-07-17 02:44:36.000000000 +0300 @@ -1 +1 @@ -Server-Sprint +Client-BackLog -=-=(Guest - Thu, 18 Jun 2009, 04:15)=-=- Low Level Design modified. --- /tmp/wklog.17.old.29969 2009-06-18 04:15:23.000000000 +0300 +++ /tmp/wklog.17.new.29969 2009-06-18 04:15:23.000000000 +0300 @@ -158,3 +158,43 @@ from user/EXPLAIN point of view: no. constant table is the one that we read one record from. eliminated table is the one that we don't acccess at all. +* What is described above will not be able to eliminate this outer join + create unique index idx on tableB (id, fromDate); + ... + left outer join + tableB B + on + B.id = A.id + and + B.fromDate = (select max(sub.fromDate) + from tableB sub where sub.id = A.id); + + This is because condition "B.fromDate= func(tableB)" cannot be used. + Reason#1: update_ref_and_keys() does not consider such conditions to + be of any use (and indeed they are not usable for ref access) + so they are not put into KEYUSE array. + Reason#2: even if they were put there, we would need to be able to tell + between predicates like + B.fromDate= func(B.id) // guarantees only one matching row as + // B.id is already bound by B.id=A.id + // hence B.fromDate becomes bound too. + and + "B.fromDate= func(B.*)" // Can potentially have many matching + // records. + We need to + - Have update_ref_and_keys() create KEYUSE elements for such equalities + - Have eliminate_tables() and friends make a more accurate check. + The right check is to check whether all parts of a unique key are bound. + If we have keypartX to be bound, then t.keypartY=func(keypartX) makes + keypartY to be bound. + The difficulty here is that correlated subquery predicate cannot tell what + columns it depends on (it only remembers tables). + Traversing the predicate is expensive and complicated. + We're leaning towards making each subquery predicate have a List<Item> with + items that + - are in the current select + - and it depends on. + This list will be useful in certain other subquery optimizations as well, + it is cheap to collect it in fix_fields() phase, so it will be collected + for every subquery predicate. + -=-=(Guest - Thu, 18 Jun 2009, 02:48)=-=- Low Level Design modified. --- /tmp/wklog.17.old.27792 2009-06-18 02:48:45.000000000 +0300 +++ /tmp/wklog.17.new.27792 2009-06-18 02:48:45.000000000 +0300 @@ -89,14 +89,14 @@ - queries that would use elimination - queries that are very similar to one above (so that they would have same QEP, execution cost, etc) but cannot use table elimination. +then compare run times and make a conclusion about whether dbms supports table +elimination. 6. Todo, issues to resolve -------------------------- 6.1 To resolve ~~~~~~~~~~~~~~ -- Re-check how this works with equality propagation. - - Relationship with prepared statements. On one hand, it's natural to desire to make table elimination a once-per-statement operation, like outer->inner join conversion. We'll have @@ -141,8 +141,13 @@ 7. Additional issues -------------------- -* We remove ON clauses within semi-join nests. If these clauses contain +* We remove ON clauses within outer join nests. If these clauses contain subqueries, they probably should be gone from EXPLAIN output also? + Yes. Current approach: when removing an outer join nest, walk the ON clause + and mark subselects as eliminated. Then let EXPLAIN code check if the + SELECT was eliminated before the printing (EXPLAIN is generated by doing + a recursive descent, so the check will also cause children of eliminated + selects not to be printed) * Table elimination is performed after constant table detection (but before the range analysis). Constant tables are technically different from -=-=(Guest - Thu, 18 Jun 2009, 02:24)=-=- Low Level Design modified. --- /tmp/wklog.17.old.27162 2009-06-18 02:24:14.000000000 +0300 +++ /tmp/wklog.17.new.27162 2009-06-18 02:24:14.000000000 +0300 @@ -83,9 +83,12 @@ 5. Tests and benchmarks ----------------------- -Should create a benchmark in sql-bench which checks if the dbms has table +Create a benchmark in sql-bench which checks if the DBMS has table elimination. -TODO elaborate +[According to Monty] Run + - queries that would use elimination + - queries that are very similar to one above (so that they would have same + QEP, execution cost, etc) but cannot use table elimination. 6. Todo, issues to resolve -------------------------- @@ -109,33 +112,37 @@ 6.2 Resolved ~~~~~~~~~~~~ -- outer->inner join conversion is not a problem for table elimination. +* outer->inner join conversion is not a problem for table elimination. We make outer->inner conversions based on predicates in WHERE. If the WHERE referred to an inner table (requirement for OJ->IJ conversion) then table elimination would not be applicable anyway. -7. Additional issues --------------------- -* We remove ON clauses within semi-join nests. If these clauses contain - subqueries, they probably should be gone from EXPLAIN output also? +* For Multi-table UPDATEs/DELETEs, need to also analyze the SET clause: + - affected tables must not be eliminated + - tables that are used on the right side of the SET x=y assignments must + not be eliminated either. -* Aggregate functions report they depend on all tables, that is, +* Aggregate functions used to report that they depend on all tables, that is, item_agg_func->used_tables() == (1ULL << join->tables) - 1 - always. If we want table elimination to work in presence of grouping, need - to devise some other way of analyzing aggregate functions. + always. Fixed it, now aggregate function reports it depends on + tables that its arguments depend on. In particular, COUNT(*) reports + that it depends on no tables (item_count_star->used_tables()==0). + One consequence of that is that "item->used_tables()==0" is not + equivalent to "item->const_item()==true" anymore (not sure if it's + "anymore" or this has been already happening). + +* EXPLAIN EXTENDED warning text was generated after the JOIN object has + been discarded. This didn't allow to use information about join plan + when printing the warning. Fixed this by keeping the JOIN objects until + we've printed the warning (have also an intent to remove the const + tables from the join output). -* Should eliminated tables be shown in EXPLAIN EXTENDED? - - If we just ignore the question, they will be shown - - this is what happens for constant tables, too. - - I don't see how showing them could be of any use. They only make it - harder to read the rewritten query. - It turns out that - - it is easy to have EXPLAIN EXTENDED show permanent (once-per-statement - lifetime) changes. - - it is hard to have it show per-execution data. This is because the warning - text is generated after the execution structures have been destroyed. +7. Additional issues +-------------------- +* We remove ON clauses within semi-join nests. If these clauses contain + subqueries, they probably should be gone from EXPLAIN output also? * Table elimination is performed after constant table detection (but before the range analysis). Constant tables are technically different from @@ -143,8 +150,6 @@ Considering we've already done the join_read_const_table() call, is there any real difference between constant table and eliminated one? If there is, should we mark const tables also as eliminated? + from user/EXPLAIN point of view: no. constant table is the one that we read + one record from. eliminated table is the one that we don't acccess at all. -* For Multi-table UPDATEs/DELETEs, need to also analyze the SET clause: - - affected tables must not be eliminated - - tables that are used on the right side of the SET x=y assignments must - not be eliminated either. -=-=(Guest - Tue, 16 Jun 2009, 17:01)=-=- Dependency deleted: 29 no longer depends on 17 -=-=(Guest - Wed, 10 Jun 2009, 01:23)=-=- Low Level Design modified. --- /tmp/wklog.17.old.1842 2009-06-10 01:23:42.000000000 +0300 +++ /tmp/wklog.17.new.1842 2009-06-10 01:23:42.000000000 +0300 @@ -131,6 +131,11 @@ - this is what happens for constant tables, too. - I don't see how showing them could be of any use. They only make it harder to read the rewritten query. + It turns out that + - it is easy to have EXPLAIN EXTENDED show permanent (once-per-statement + lifetime) changes. + - it is hard to have it show per-execution data. This is because the warning + text is generated after the execution structures have been destroyed. * Table elimination is performed after constant table detection (but before the range analysis). Constant tables are technically different from ------------------------------------------------------------ -=-=(View All Progress Notes, 24 total)=-=- http://askmonty.org/worklog/index.pl?tid=17&nolimit=1 DESCRIPTION: Eliminate not needed tables from SELECT queries.. This will speed up some views and automatically generated queries. Example: CREATE TABLE B (id int primary key); select A.colA from tableA A left outer join tableB B on B.id = A.id; In this case we can remove table B and the join from the query. HIGH-LEVEL SPECIFICATION: Here is an extended explanation of table elimination. Table elimination is a feature found in some modern query optimizers, of which Microsoft SQL Server 2005/2008 seems to have the most advanced implementation. Oracle 11g has also been confirmed to use table elimination but not to the same extent. Basically, what table elimination does, is to remove tables from the execution plan when it is unnecessary to include them. This can, of course, only happen if the right circumstances arise. Let us for example look at the following query: select A.colA from tableA A left outer join tableB B on B.id = A.id; When using A as the left table we ensure that the query will return at least as many rows as there are in that table. For rows where the join condition (B.id = A.id) is not met the selected column (A.colA) will still contain it's original value. The not seen B.* row would contain all NULL:s. However, the result set could actually contain more rows than what is found in tableA if there are duplicates of the column B.id in tableB. If A contains a row [1, "val1"] and B the rows [1, "other1a"],[1, "other1b"] then two rows will match in the join condition. The only way to know what the result will look like is to actually touch both tables during execution. Instead, let's say that tableB contains rows that make it possible to place a unique constraint on the column B.id, for example and often the case a primary key. In this situation we know that we will get exactly as many rows as there are in tableA, since joining with tableB cannot introduce any duplicates. If further, as in the example query, we do not select any columns from tableB, touching that table during execution is unnecessary. We can remove the whole join operation from the execution plan. Both SQL Server 2005/2008 and Oracle 11g will deploy table elimination in the case described above. Let us look at a more advanced query, where Oracle fails. select A.colA from tableA A left outer join tableB B on B.id = A.id and B.fromDate = ( select max(sub.fromDate) from tableB sub where sub.id = A.id ); In this example we have added another join condition, which ensures that we only pick the matching row from tableB having the latest fromDate. In this case tableB will contain duplicates of the column B.id, so in order to ensure uniqueness the primary key has to contain the fromDate column as well. In other words the primary key of tableB is (B.id, B.fromDate). Furthermore, since the subselect ensures that we only pick the latest B.fromDate for a given B.id we know that at most one row will match the join condition. We will again have the situation where joining with tableB cannot affect the number of rows in the result set. Since we do not select any columns from tableB, the whole join operation can be eliminated from the execution plan. SQL Server 2005/2008 will deploy table elimination in this situation as well. We have not found a way to make Oracle 11g use it for this type of query. Queries like these arise in two situations. Either when you have denormalized model consisting of a fact table with several related dimension tables, or when you have a highly normalized model where each attribute is stored in its own table. The example with the subselect is common whenever you store historized/versioned data. LOW-LEVEL DESIGN: The code (currently in development) is at lp: ~maria-captains/maria/maria-5.1-table-elimination tree. <contents> 1. Conditions for removal 1.1 Quick check if there are candidates 2. Removal operation properties 3. Removal operation 4. User interface 5. Tests and benchmarks 6. Todo, issues to resolve 6.1 To resolve 6.2 Resolved 7. Additional issues </contents> It's not really about elimination of tables, it's about elimination of inner sides of outer joins. 1. Conditions for removal ------------------------- We can eliminate an inner side of outer join if: 1. For each record combination of outer tables, it will always produce exactly one record. 2. There are no references to columns of the inner tables anywhere else in the query. #1 means that every table inside the outer join nest is: - is a constant table: = because it can be accessed via eq_ref(const) access, or = it is a zero-rows or one-row MyISAM-like table [MARK1] - has an eq_ref access method candidate. #2 means that WHERE clause, ON clauses of embedding outer joins, ORDER BY, GROUP BY and HAVING do not refer to the inner tables of the outer join nest. 1.1 Quick check if there are candidates ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Before we start to enumerate join nests, here is a quick way to check if there *can be* something to be removed: if ((tables used in select_list | tables used in group/order by UNION | tables used in where) != bitmap_of_all_tables) { attempt table elimination; } 2. Removal operation properties ------------------------------- * There is always one way to remove (no choice to remove either this or that) * It is always better to remove as much tables as possible (at least within our cost model). Thus, no need for any cost calculations/etc. It's an unconditional rewrite. 3. Removal operation -------------------- * Remove the outer join nest's nested join structure (i.e. get the outer join's TABLE_LIST object $OJ and remove it from $OJ->embedding, $OJ->embedding->nested_join. Update table_map's of all ancestor nested joins). [MARK2] * Move the tables and their JOIN_TABs to front like it is done with const tables, with exception that if eliminated outer join nest was within another outer join nest, that shouldn't prevent us from moving away the eliminated tables. * Update join->table_count and all-join-tables bitmap. * That's it. Nothing else? 4. User interface ----------------- * We'll add an @@optimizer switch flag for table elimination. Tentative name: 'table_elimination'. (Note ^^ utility of the above questioned ^, as table elimination can never be worse than no elimination. We're leaning towards not adding the flag) * EXPLAIN will not show the removed tables at all. This will allow to check if tables were removed, and also will behave nicely with anchor model and VIEWs: stuff that user doesn't care about just won't be there. 5. Tests and benchmarks ----------------------- Create a benchmark in sql-bench which checks if the DBMS has table elimination. [According to Monty] Run - queries that would use elimination - queries that are very similar to one above (so that they would have same QEP, execution cost, etc) but cannot use table elimination. then compare run times and make a conclusion about whether dbms supports table elimination. 6. Todo, issues to resolve -------------------------- 6.1 To resolve ~~~~~~~~~~~~~~ - Relationship with prepared statements. On one hand, it's natural to desire to make table elimination a once-per-statement operation, like outer->inner join conversion. We'll have to limit the applicability by removing [MARK1] as that can change during lifetime of the statement. The other option is to do table elimination every time. This will require to rework operation [MARK2] to be undoable. I'm leaning towards doing the former. With anchor modeling, it is unlikely that we'll meet outer joins which have N inner tables of which some are 1-row MyISAM tables that do not have primary key. 6.2 Resolved ~~~~~~~~~~~~ * outer->inner join conversion is not a problem for table elimination. We make outer->inner conversions based on predicates in WHERE. If the WHERE referred to an inner table (requirement for OJ->IJ conversion) then table elimination would not be applicable anyway. * For Multi-table UPDATEs/DELETEs, need to also analyze the SET clause: - affected tables must not be eliminated - tables that are used on the right side of the SET x=y assignments must not be eliminated either. * Aggregate functions used to report that they depend on all tables, that is, item_agg_func->used_tables() == (1ULL << join->tables) - 1 always. Fixed it, now aggregate function reports it depends on tables that its arguments depend on. In particular, COUNT(*) reports that it depends on no tables (item_count_star->used_tables()==0). One consequence of that is that "item->used_tables()==0" is not equivalent to "item->const_item()==true" anymore (not sure if it's "anymore" or this has been already happening). * EXPLAIN EXTENDED warning text was generated after the JOIN object has been discarded. This didn't allow to use information about join plan when printing the warning. Fixed this by keeping the JOIN objects until we've printed the warning (have also an intent to remove the const tables from the join output). 7. Additional issues -------------------- * We remove ON clauses within outer join nests. If these clauses contain subqueries, they probably should be gone from EXPLAIN output also? Yes. Current approach: when removing an outer join nest, walk the ON clause and mark subselects as eliminated. Then let EXPLAIN code check if the SELECT was eliminated before the printing (EXPLAIN is generated by doing a recursive descent, so the check will also cause children of eliminated selects not to be printed) * Table elimination is performed after constant table detection (but before the range analysis). Constant tables are technically different from eliminated ones (e.g. the former are shown in EXPLAIN and the latter aren't). Considering we've already done the join_read_const_table() call, is there any real difference between constant table and eliminated one? If there is, should we mark const tables also as eliminated? from user/EXPLAIN point of view: no. constant table is the one that we read one record from. eliminated table is the one that we don't acccess at all. * What is described above will not be able to eliminate this outer join create unique index idx on tableB (id, fromDate); ... left outer join tableB B on B.id = A.id and B.fromDate = (select max(sub.fromDate) from tableB sub where sub.id = A.id); This is because condition "B.fromDate= func(tableB)" cannot be used. Reason#1: update_ref_and_keys() does not consider such conditions to be of any use (and indeed they are not usable for ref access) so they are not put into KEYUSE array. Reason#2: even if they were put there, we would need to be able to tell between predicates like B.fromDate= func(B.id) // guarantees only one matching row as // B.id is already bound by B.id=A.id // hence B.fromDate becomes bound too. and "B.fromDate= func(B.*)" // Can potentially have many matching // records. We need to - Have update_ref_and_keys() create KEYUSE elements for such equalities - Have eliminate_tables() and friends make a more accurate check. The right check is to check whether all parts of a unique key are bound. If we have keypartX to be bound, then t.keypartY=func(keypartX) makes keypartY to be bound. The difficulty here is that correlated subquery predicate cannot tell what columns it depends on (it only remembers tables). Traversing the predicate is expensive and complicated. We're leaning towards making each subquery predicate have a List<Item> with items that - are in the current select - and it depends on. This list will be useful in certain other subquery optimizations as well, it is cheap to collect it in fix_fields() phase, so it will be collected for every subquery predicate. ESTIMATED WORK TIME ESTIMATED COMPLETION DATE ----------------------------------------------------------------------- WorkLog (v3.5.9)

1 0