February 2010 - developers - lists.mariadb.org

[Maria-developers] Updated (by Psergey): Subqueries: cost-based choice between Materialization and IN->EXISTS transformation (89)
by worklog-noreply＠askmonty.org 28 Feb '10

28 Feb '10

----------------------------------------------------------------------- WORKLOG TASK -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- TASK...........: Subqueries: cost-based choice between Materialization and IN->EXISTS transformation CREATION DATE..: Sun, 28 Feb 2010, 13:39 SUPERVISOR.....: Monty IMPLEMENTOR....: COPIES TO......: Igor, Psergey, Timour CATEGORY.......: Server-RawIdeaBin TASK ID........: 89 (http://askmonty.org/worklog/?tid=89) VERSION........: Server-5.3 STATUS.........: Un-Assigned PRIORITY.......: 60 WORKED HOURS...: 0 ESTIMATE.......: (hours remain) ORIG. ESTIMATE.: 0 PROGRESS NOTES: -=-=(Psergey - Sun, 28 Feb 2010, 15:57)=-=- High-Level Specification modified. --- /tmp/wklog.89.old.24045 2010-02-28 15:57:49.000000000 +0000 +++ /tmp/wklog.89.new.24045 2010-02-28 15:57:49.000000000 +0000 @@ -1 +1,38 @@ +Why need two optimizations +-------------------------- +Consider a query with subquery: + + SELECT + oe IN (SELECT ie FROM inner_tbl WHERE inner_cond) + FROM outer_tbl + WHERE outer_cond + +If we use Materialization strategy, the costs will be + + cost of accessing outer_tbl + + materialization_cost + + #records(outer_tbl w/o outer_cond) * lookup_cost + +where + + materialization_cost= + cost of executing the (SELECT ie FROM inner_tbl WHERE inner_cond) + +On the other hand, for IN->EXISTS strategy, the subquery will be rewritten into + + SELECT + EXISTS (SELECT 1 FROM inner_tbl WHERE inner_cond AND oe=ie) + FROM outer_tbl + WHERE outer_cond + +and the costs will be + + cost of accessing outer_tbl + + #records(outer_tbl w/o outer_cond) * exists_select_cost + +where + exists_select_cost= + cost of executing the (SELECT 1 FROM inner_tbl WHERE inner_cond AND oe=ie) + +So, we'll need to compute both exists_select_cost and materialization_cost. -=-=(Psergey - Sun, 28 Feb 2010, 15:07)=-=- Dependency created: 91 now depends on 89 DESCRIPTION: For uncorrelated IN subqueries that can't be converted to semi-joins it is necessary to make a cost-based choice between IN->EXISTS and Materialization strategies. Both strategies handle two cases: 1. A simple case w/o NULLs handling 2. Handling NULLs. This WL is about making cost-based decision for #1. HIGH-LEVEL SPECIFICATION: Why need two optimizations -------------------------- Consider a query with subquery: SELECT oe IN (SELECT ie FROM inner_tbl WHERE inner_cond) FROM outer_tbl WHERE outer_cond If we use Materialization strategy, the costs will be cost of accessing outer_tbl + materialization_cost + #records(outer_tbl w/o outer_cond) * lookup_cost where materialization_cost= cost of executing the (SELECT ie FROM inner_tbl WHERE inner_cond) On the other hand, for IN->EXISTS strategy, the subquery will be rewritten into SELECT EXISTS (SELECT 1 FROM inner_tbl WHERE inner_cond AND oe=ie) FROM outer_tbl WHERE outer_cond and the costs will be cost of accessing outer_tbl + #records(outer_tbl w/o outer_cond) * exists_select_cost where exists_select_cost= cost of executing the (SELECT 1 FROM inner_tbl WHERE inner_cond AND oe=ie) So, we'll need to compute both exists_select_cost and materialization_cost. ESTIMATED WORK TIME ESTIMATED COMPLETION DATE ----------------------------------------------------------------------- WorkLog (v3.5.9)

1 0

[Maria-developers] Updated (by Psergey): Subqueries: cost-based choice between Materialization and IN->EXISTS transformation (89)
by worklog-noreply＠askmonty.org 28 Feb '10

28 Feb '10

----------------------------------------------------------------------- WORKLOG TASK -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- TASK...........: Subqueries: cost-based choice between Materialization and IN->EXISTS transformation CREATION DATE..: Sun, 28 Feb 2010, 13:39 SUPERVISOR.....: Monty IMPLEMENTOR....: COPIES TO......: Igor, Psergey, Timour CATEGORY.......: Server-RawIdeaBin TASK ID........: 89 (http://askmonty.org/worklog/?tid=89) VERSION........: Server-5.3 STATUS.........: Un-Assigned PRIORITY.......: 60 WORKED HOURS...: 0 ESTIMATE.......: (hours remain) ORIG. ESTIMATE.: 0 PROGRESS NOTES: -=-=(Psergey - Sun, 28 Feb 2010, 15:57)=-=- High-Level Specification modified. --- /tmp/wklog.89.old.24045 2010-02-28 15:57:49.000000000 +0000 +++ /tmp/wklog.89.new.24045 2010-02-28 15:57:49.000000000 +0000 @@ -1 +1,38 @@ +Why need two optimizations +-------------------------- +Consider a query with subquery: + + SELECT + oe IN (SELECT ie FROM inner_tbl WHERE inner_cond) + FROM outer_tbl + WHERE outer_cond + +If we use Materialization strategy, the costs will be + + cost of accessing outer_tbl + + materialization_cost + + #records(outer_tbl w/o outer_cond) * lookup_cost + +where + + materialization_cost= + cost of executing the (SELECT ie FROM inner_tbl WHERE inner_cond) + +On the other hand, for IN->EXISTS strategy, the subquery will be rewritten into + + SELECT + EXISTS (SELECT 1 FROM inner_tbl WHERE inner_cond AND oe=ie) + FROM outer_tbl + WHERE outer_cond + +and the costs will be + + cost of accessing outer_tbl + + #records(outer_tbl w/o outer_cond) * exists_select_cost + +where + exists_select_cost= + cost of executing the (SELECT 1 FROM inner_tbl WHERE inner_cond AND oe=ie) + +So, we'll need to compute both exists_select_cost and materialization_cost. -=-=(Psergey - Sun, 28 Feb 2010, 15:07)=-=- Dependency created: 91 now depends on 89 DESCRIPTION: For uncorrelated IN subqueries that can't be converted to semi-joins it is necessary to make a cost-based choice between IN->EXISTS and Materialization strategies. Both strategies handle two cases: 1. A simple case w/o NULLs handling 2. Handling NULLs. This WL is about making cost-based decision for #1. HIGH-LEVEL SPECIFICATION: Why need two optimizations -------------------------- Consider a query with subquery: SELECT oe IN (SELECT ie FROM inner_tbl WHERE inner_cond) FROM outer_tbl WHERE outer_cond If we use Materialization strategy, the costs will be cost of accessing outer_tbl + materialization_cost + #records(outer_tbl w/o outer_cond) * lookup_cost where materialization_cost= cost of executing the (SELECT ie FROM inner_tbl WHERE inner_cond) On the other hand, for IN->EXISTS strategy, the subquery will be rewritten into SELECT EXISTS (SELECT 1 FROM inner_tbl WHERE inner_cond AND oe=ie) FROM outer_tbl WHERE outer_cond and the costs will be cost of accessing outer_tbl + #records(outer_tbl w/o outer_cond) * exists_select_cost where exists_select_cost= cost of executing the (SELECT 1 FROM inner_tbl WHERE inner_cond AND oe=ie) So, we'll need to compute both exists_select_cost and materialization_cost. ESTIMATED WORK TIME ESTIMATED COMPLETION DATE ----------------------------------------------------------------------- WorkLog (v3.5.9)

1 0

[Maria-developers] Updated (by Psergey): Subqueries: Inside-out execution for non-semijoin materialized subqueries that are AND-parts of the WHERE (90)
by worklog-noreply＠askmonty.org 28 Feb '10

28 Feb '10

----------------------------------------------------------------------- WORKLOG TASK -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- TASK...........: Subqueries: Inside-out execution for non-semijoin materialized subqueries that are AND-parts of the WHERE CREATION DATE..: Sun, 28 Feb 2010, 13:45 SUPERVISOR.....: Monty IMPLEMENTOR....: COPIES TO......: Igor, Psergey, Timour CATEGORY.......: Server-RawIdeaBin TASK ID........: 90 (http://askmonty.org/worklog/?tid=90) VERSION........: Server-5.3 STATUS.........: Un-Assigned PRIORITY.......: 60 WORKED HOURS...: 0 ESTIMATE.......: -1 (hours remain) ORIG. ESTIMATE.: 0 PROGRESS NOTES: -=-=(Psergey - Sun, 28 Feb 2010, 15:37)=-=- High Level Description modified. --- /tmp/wklog.90.old.23524 2010-02-28 15:37:47.000000000 +0000 +++ /tmp/wklog.90.new.23524 2010-02-28 15:37:47.000000000 +0000 @@ -15,3 +15,7 @@ Semi-join materialization supports such strategy with SJM-Scan strategy. This WL entry is about adding support for such strategies for non-semijoin subqueries. + + +Once WL#89 is done, there will be a cost-based choice between +Materialization+lookup, Materialization+scan, and IN->EXISTS+lookup strategies. -=-=(Psergey - Sun, 28 Feb 2010, 15:22)=-=- High-Level Specification modified. --- /tmp/wklog.90.old.23033 2010-02-28 15:22:09.000000000 +0000 +++ /tmp/wklog.90.new.23033 2010-02-28 15:22:09.000000000 +0000 @@ -1 +1,33 @@ +Basic idea on how this could be achieved: + +Pre-optimization phase +---------------------- + +The rewrite +~~~~~~~~~~~ +If we find a subquery predicate that is +- not processed by current semi-join optimizations +- is an AND-part of the WHERE/ON clause +- can be executed with Materialization + +then +- Remove the predicate from WHERE/ON clause +- Add a special JOIN_TAB object instead. + +Plan options +~~~~~~~~~~~~ +- Use the IN-equality to create KEYUSE elements. + +Optimization +------------ +- Pre-optimize the subquery so we know materialization cost +- Whenever best_access_path() encounters the "special JOIN_TAB" it should + consider two strategies: + A. Materialization and making lookups in the materialized table (if applicable) + B. Materialization and then scanning the materialized table. + + +EXPLAIN +------- +TODO how this will look in EXPLAIN output? -=-=(Psergey - Sun, 28 Feb 2010, 14:56)=-=- Dependency created: 91 now depends on 90 -=-=(Psergey - Sun, 28 Feb 2010, 14:54)=-=- Dependency deleted: 94 no longer depends on 90 -=-=(Psergey - Sun, 28 Feb 2010, 14:47)=-=- Title modified. --- /tmp/wklog.90.old.21903 2010-02-28 14:47:54.000000000 +0000 +++ /tmp/wklog.90.new.21903 2010-02-28 14:47:54.000000000 +0000 @@ -1 +1 @@ - Subqueries: Inside-out execution for non-semijoin materialized subqueries that are AND-parts of the WHERE +Subqueries: Inside-out execution for non-semijoin materialized subqueries that are AND-parts of the WHERE -=-=(Psergey - Sun, 28 Feb 2010, 14:47)=-=- High Level Description modified. --- /tmp/wklog.90.old.21880 2010-02-28 14:47:28.000000000 +0000 +++ /tmp/wklog.90.new.21880 2010-02-28 14:47:28.000000000 +0000 @@ -1,10 +1,17 @@ -For uncorrelated IN subqueries that can't be converted to semi-joins it is -necessary to make a cost-based choice between IN->EXISTS and Materialization -strategies. +Consider the following case: -Both strategies handle two cases: -1. A simple case w/o NULLs handling -2. Handling NULLs. +SELECT * FROM big_table +WHERE oe IN (SELECT ie FROM table_with_few_groups + WHERE ... + GROUP BY group_col) AND ... -This WL is about making cost-based decision for #1. +Here the best way to execute the query is: + Materialize the subquery; + # now run the join: + for each record R1 in materialized table + for each record R2 in big_table such that oe=R1 + pass R2 to output + +Semi-join materialization supports such strategy with SJM-Scan strategy. This WL +entry is about adding support for such strategies for non-semijoin subqueries. -=-=(Psergey - Sun, 28 Feb 2010, 14:47)=-=- Title modified. --- /tmp/wklog.90.old.21859 2010-02-28 14:47:02.000000000 +0000 +++ /tmp/wklog.90.new.21859 2010-02-28 14:47:02.000000000 +0000 @@ -1 +1 @@ -Subqueries: cost-based choice between Materialization and IN->EXISTS transformation + Subqueries: Inside-out execution for non-semijoin materialized subqueries that are AND-parts of the WHERE -=-=(Psergey - Sun, 28 Feb 2010, 14:08)=-=- Dependency created: 94 now depends on 90 DESCRIPTION: Consider the following case: SELECT * FROM big_table WHERE oe IN (SELECT ie FROM table_with_few_groups WHERE ... GROUP BY group_col) AND ... Here the best way to execute the query is: Materialize the subquery; # now run the join: for each record R1 in materialized table for each record R2 in big_table such that oe=R1 pass R2 to output Semi-join materialization supports such strategy with SJM-Scan strategy. This WL entry is about adding support for such strategies for non-semijoin subqueries. Once WL#89 is done, there will be a cost-based choice between Materialization+lookup, Materialization+scan, and IN->EXISTS+lookup strategies. HIGH-LEVEL SPECIFICATION: Basic idea on how this could be achieved: Pre-optimization phase ---------------------- The rewrite ~~~~~~~~~~~ If we find a subquery predicate that is - not processed by current semi-join optimizations - is an AND-part of the WHERE/ON clause - can be executed with Materialization then - Remove the predicate from WHERE/ON clause - Add a special JOIN_TAB object instead. Plan options ~~~~~~~~~~~~ - Use the IN-equality to create KEYUSE elements. Optimization ------------ - Pre-optimize the subquery so we know materialization cost - Whenever best_access_path() encounters the "special JOIN_TAB" it should consider two strategies: A. Materialization and making lookups in the materialized table (if applicable) B. Materialization and then scanning the materialized table. EXPLAIN ------- TODO how this will look in EXPLAIN output? ESTIMATED WORK TIME ESTIMATED COMPLETION DATE ----------------------------------------------------------------------- WorkLog (v3.5.9)

1 0

[Maria-developers] Updated (by Psergey): Subqueries: Inside-out execution for non-semijoin materialized subqueries that are AND-parts of the WHERE (90)
by worklog-noreply＠askmonty.org 28 Feb '10

28 Feb '10

----------------------------------------------------------------------- WORKLOG TASK -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- TASK...........: Subqueries: Inside-out execution for non-semijoin materialized subqueries that are AND-parts of the WHERE CREATION DATE..: Sun, 28 Feb 2010, 13:45 SUPERVISOR.....: Monty IMPLEMENTOR....: COPIES TO......: Igor, Psergey, Timour CATEGORY.......: Server-RawIdeaBin TASK ID........: 90 (http://askmonty.org/worklog/?tid=90) VERSION........: Server-5.3 STATUS.........: Un-Assigned PRIORITY.......: 60 WORKED HOURS...: 0 ESTIMATE.......: -1 (hours remain) ORIG. ESTIMATE.: 0 PROGRESS NOTES: -=-=(Psergey - Sun, 28 Feb 2010, 15:37)=-=- High Level Description modified. --- /tmp/wklog.90.old.23524 2010-02-28 15:37:47.000000000 +0000 +++ /tmp/wklog.90.new.23524 2010-02-28 15:37:47.000000000 +0000 @@ -15,3 +15,7 @@ Semi-join materialization supports such strategy with SJM-Scan strategy. This WL entry is about adding support for such strategies for non-semijoin subqueries. + + +Once WL#89 is done, there will be a cost-based choice between +Materialization+lookup, Materialization+scan, and IN->EXISTS+lookup strategies. -=-=(Psergey - Sun, 28 Feb 2010, 15:22)=-=- High-Level Specification modified. --- /tmp/wklog.90.old.23033 2010-02-28 15:22:09.000000000 +0000 +++ /tmp/wklog.90.new.23033 2010-02-28 15:22:09.000000000 +0000 @@ -1 +1,33 @@ +Basic idea on how this could be achieved: + +Pre-optimization phase +---------------------- + +The rewrite +~~~~~~~~~~~ +If we find a subquery predicate that is +- not processed by current semi-join optimizations +- is an AND-part of the WHERE/ON clause +- can be executed with Materialization + +then +- Remove the predicate from WHERE/ON clause +- Add a special JOIN_TAB object instead. + +Plan options +~~~~~~~~~~~~ +- Use the IN-equality to create KEYUSE elements. + +Optimization +------------ +- Pre-optimize the subquery so we know materialization cost +- Whenever best_access_path() encounters the "special JOIN_TAB" it should + consider two strategies: + A. Materialization and making lookups in the materialized table (if applicable) + B. Materialization and then scanning the materialized table. + + +EXPLAIN +------- +TODO how this will look in EXPLAIN output? -=-=(Psergey - Sun, 28 Feb 2010, 14:56)=-=- Dependency created: 91 now depends on 90 -=-=(Psergey - Sun, 28 Feb 2010, 14:54)=-=- Dependency deleted: 94 no longer depends on 90 -=-=(Psergey - Sun, 28 Feb 2010, 14:47)=-=- Title modified. --- /tmp/wklog.90.old.21903 2010-02-28 14:47:54.000000000 +0000 +++ /tmp/wklog.90.new.21903 2010-02-28 14:47:54.000000000 +0000 @@ -1 +1 @@ - Subqueries: Inside-out execution for non-semijoin materialized subqueries that are AND-parts of the WHERE +Subqueries: Inside-out execution for non-semijoin materialized subqueries that are AND-parts of the WHERE -=-=(Psergey - Sun, 28 Feb 2010, 14:47)=-=- High Level Description modified. --- /tmp/wklog.90.old.21880 2010-02-28 14:47:28.000000000 +0000 +++ /tmp/wklog.90.new.21880 2010-02-28 14:47:28.000000000 +0000 @@ -1,10 +1,17 @@ -For uncorrelated IN subqueries that can't be converted to semi-joins it is -necessary to make a cost-based choice between IN->EXISTS and Materialization -strategies. +Consider the following case: -Both strategies handle two cases: -1. A simple case w/o NULLs handling -2. Handling NULLs. +SELECT * FROM big_table +WHERE oe IN (SELECT ie FROM table_with_few_groups + WHERE ... + GROUP BY group_col) AND ... -This WL is about making cost-based decision for #1. +Here the best way to execute the query is: + Materialize the subquery; + # now run the join: + for each record R1 in materialized table + for each record R2 in big_table such that oe=R1 + pass R2 to output + +Semi-join materialization supports such strategy with SJM-Scan strategy. This WL +entry is about adding support for such strategies for non-semijoin subqueries. -=-=(Psergey - Sun, 28 Feb 2010, 14:47)=-=- Title modified. --- /tmp/wklog.90.old.21859 2010-02-28 14:47:02.000000000 +0000 +++ /tmp/wklog.90.new.21859 2010-02-28 14:47:02.000000000 +0000 @@ -1 +1 @@ -Subqueries: cost-based choice between Materialization and IN->EXISTS transformation + Subqueries: Inside-out execution for non-semijoin materialized subqueries that are AND-parts of the WHERE -=-=(Psergey - Sun, 28 Feb 2010, 14:08)=-=- Dependency created: 94 now depends on 90 DESCRIPTION: Consider the following case: SELECT * FROM big_table WHERE oe IN (SELECT ie FROM table_with_few_groups WHERE ... GROUP BY group_col) AND ... Here the best way to execute the query is: Materialize the subquery; # now run the join: for each record R1 in materialized table for each record R2 in big_table such that oe=R1 pass R2 to output Semi-join materialization supports such strategy with SJM-Scan strategy. This WL entry is about adding support for such strategies for non-semijoin subqueries. Once WL#89 is done, there will be a cost-based choice between Materialization+lookup, Materialization+scan, and IN->EXISTS+lookup strategies. HIGH-LEVEL SPECIFICATION: Basic idea on how this could be achieved: Pre-optimization phase ---------------------- The rewrite ~~~~~~~~~~~ If we find a subquery predicate that is - not processed by current semi-join optimizations - is an AND-part of the WHERE/ON clause - can be executed with Materialization then - Remove the predicate from WHERE/ON clause - Add a special JOIN_TAB object instead. Plan options ~~~~~~~~~~~~ - Use the IN-equality to create KEYUSE elements. Optimization ------------ - Pre-optimize the subquery so we know materialization cost - Whenever best_access_path() encounters the "special JOIN_TAB" it should consider two strategies: A. Materialization and making lookups in the materialized table (if applicable) B. Materialization and then scanning the materialized table. EXPLAIN ------- TODO how this will look in EXPLAIN output? ESTIMATED WORK TIME ESTIMATED COMPLETION DATE ----------------------------------------------------------------------- WorkLog (v3.5.9)

1 0

[Maria-developers] Updated (by Psergey): Subqueries: Inside-out execution for non-semijoin materialized subqueries that are AND-parts of the WHERE (90)
by worklog-noreply＠askmonty.org 28 Feb '10

28 Feb '10

----------------------------------------------------------------------- WORKLOG TASK -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- TASK...........: Subqueries: Inside-out execution for non-semijoin materialized subqueries that are AND-parts of the WHERE CREATION DATE..: Sun, 28 Feb 2010, 13:45 SUPERVISOR.....: Monty IMPLEMENTOR....: COPIES TO......: Igor, Psergey, Timour CATEGORY.......: Server-RawIdeaBin TASK ID........: 90 (http://askmonty.org/worklog/?tid=90) VERSION........: Server-5.3 STATUS.........: Un-Assigned PRIORITY.......: 60 WORKED HOURS...: 0 ESTIMATE.......: -1 (hours remain) ORIG. ESTIMATE.: 0 PROGRESS NOTES: -=-=(Psergey - Sun, 28 Feb 2010, 15:37)=-=- High Level Description modified. --- /tmp/wklog.90.old.23524 2010-02-28 15:37:47.000000000 +0000 +++ /tmp/wklog.90.new.23524 2010-02-28 15:37:47.000000000 +0000 @@ -15,3 +15,7 @@ Semi-join materialization supports such strategy with SJM-Scan strategy. This WL entry is about adding support for such strategies for non-semijoin subqueries. + + +Once WL#89 is done, there will be a cost-based choice between +Materialization+lookup, Materialization+scan, and IN->EXISTS+lookup strategies. -=-=(Psergey - Sun, 28 Feb 2010, 15:22)=-=- High-Level Specification modified. --- /tmp/wklog.90.old.23033 2010-02-28 15:22:09.000000000 +0000 +++ /tmp/wklog.90.new.23033 2010-02-28 15:22:09.000000000 +0000 @@ -1 +1,33 @@ +Basic idea on how this could be achieved: + +Pre-optimization phase +---------------------- + +The rewrite +~~~~~~~~~~~ +If we find a subquery predicate that is +- not processed by current semi-join optimizations +- is an AND-part of the WHERE/ON clause +- can be executed with Materialization + +then +- Remove the predicate from WHERE/ON clause +- Add a special JOIN_TAB object instead. + +Plan options +~~~~~~~~~~~~ +- Use the IN-equality to create KEYUSE elements. + +Optimization +------------ +- Pre-optimize the subquery so we know materialization cost +- Whenever best_access_path() encounters the "special JOIN_TAB" it should + consider two strategies: + A. Materialization and making lookups in the materialized table (if applicable) + B. Materialization and then scanning the materialized table. + + +EXPLAIN +------- +TODO how this will look in EXPLAIN output? -=-=(Psergey - Sun, 28 Feb 2010, 14:56)=-=- Dependency created: 91 now depends on 90 -=-=(Psergey - Sun, 28 Feb 2010, 14:54)=-=- Dependency deleted: 94 no longer depends on 90 -=-=(Psergey - Sun, 28 Feb 2010, 14:47)=-=- Title modified. --- /tmp/wklog.90.old.21903 2010-02-28 14:47:54.000000000 +0000 +++ /tmp/wklog.90.new.21903 2010-02-28 14:47:54.000000000 +0000 @@ -1 +1 @@ - Subqueries: Inside-out execution for non-semijoin materialized subqueries that are AND-parts of the WHERE +Subqueries: Inside-out execution for non-semijoin materialized subqueries that are AND-parts of the WHERE -=-=(Psergey - Sun, 28 Feb 2010, 14:47)=-=- High Level Description modified. --- /tmp/wklog.90.old.21880 2010-02-28 14:47:28.000000000 +0000 +++ /tmp/wklog.90.new.21880 2010-02-28 14:47:28.000000000 +0000 @@ -1,10 +1,17 @@ -For uncorrelated IN subqueries that can't be converted to semi-joins it is -necessary to make a cost-based choice between IN->EXISTS and Materialization -strategies. +Consider the following case: -Both strategies handle two cases: -1. A simple case w/o NULLs handling -2. Handling NULLs. +SELECT * FROM big_table +WHERE oe IN (SELECT ie FROM table_with_few_groups + WHERE ... + GROUP BY group_col) AND ... -This WL is about making cost-based decision for #1. +Here the best way to execute the query is: + Materialize the subquery; + # now run the join: + for each record R1 in materialized table + for each record R2 in big_table such that oe=R1 + pass R2 to output + +Semi-join materialization supports such strategy with SJM-Scan strategy. This WL +entry is about adding support for such strategies for non-semijoin subqueries. -=-=(Psergey - Sun, 28 Feb 2010, 14:47)=-=- Title modified. --- /tmp/wklog.90.old.21859 2010-02-28 14:47:02.000000000 +0000 +++ /tmp/wklog.90.new.21859 2010-02-28 14:47:02.000000000 +0000 @@ -1 +1 @@ -Subqueries: cost-based choice between Materialization and IN->EXISTS transformation + Subqueries: Inside-out execution for non-semijoin materialized subqueries that are AND-parts of the WHERE -=-=(Psergey - Sun, 28 Feb 2010, 14:08)=-=- Dependency created: 94 now depends on 90 DESCRIPTION: Consider the following case: SELECT * FROM big_table WHERE oe IN (SELECT ie FROM table_with_few_groups WHERE ... GROUP BY group_col) AND ... Here the best way to execute the query is: Materialize the subquery; # now run the join: for each record R1 in materialized table for each record R2 in big_table such that oe=R1 pass R2 to output Semi-join materialization supports such strategy with SJM-Scan strategy. This WL entry is about adding support for such strategies for non-semijoin subqueries. Once WL#89 is done, there will be a cost-based choice between Materialization+lookup, Materialization+scan, and IN->EXISTS+lookup strategies. HIGH-LEVEL SPECIFICATION: Basic idea on how this could be achieved: Pre-optimization phase ---------------------- The rewrite ~~~~~~~~~~~ If we find a subquery predicate that is - not processed by current semi-join optimizations - is an AND-part of the WHERE/ON clause - can be executed with Materialization then - Remove the predicate from WHERE/ON clause - Add a special JOIN_TAB object instead. Plan options ~~~~~~~~~~~~ - Use the IN-equality to create KEYUSE elements. Optimization ------------ - Pre-optimize the subquery so we know materialization cost - Whenever best_access_path() encounters the "special JOIN_TAB" it should consider two strategies: A. Materialization and making lookups in the materialized table (if applicable) B. Materialization and then scanning the materialized table. EXPLAIN ------- TODO how this will look in EXPLAIN output? ESTIMATED WORK TIME ESTIMATED COMPLETION DATE ----------------------------------------------------------------------- WorkLog (v3.5.9)

1 0

[Maria-developers] Updated (by Psergey): Subqueries: Inside-out execution for non-semijoin materialized subqueries that are AND-parts of the WHERE (90)
by worklog-noreply＠askmonty.org 28 Feb '10

28 Feb '10

----------------------------------------------------------------------- WORKLOG TASK -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- TASK...........: Subqueries: Inside-out execution for non-semijoin materialized subqueries that are AND-parts of the WHERE CREATION DATE..: Sun, 28 Feb 2010, 13:45 SUPERVISOR.....: Monty IMPLEMENTOR....: COPIES TO......: Igor, Psergey, Timour CATEGORY.......: Server-RawIdeaBin TASK ID........: 90 (http://askmonty.org/worklog/?tid=90) VERSION........: Server-5.3 STATUS.........: Un-Assigned PRIORITY.......: 60 WORKED HOURS...: 0 ESTIMATE.......: -1 (hours remain) ORIG. ESTIMATE.: 0 PROGRESS NOTES: -=-=(Psergey - Sun, 28 Feb 2010, 15:37)=-=- High Level Description modified. --- /tmp/wklog.90.old.23524 2010-02-28 15:37:47.000000000 +0000 +++ /tmp/wklog.90.new.23524 2010-02-28 15:37:47.000000000 +0000 @@ -15,3 +15,7 @@ Semi-join materialization supports such strategy with SJM-Scan strategy. This WL entry is about adding support for such strategies for non-semijoin subqueries. + + +Once WL#89 is done, there will be a cost-based choice between +Materialization+lookup, Materialization+scan, and IN->EXISTS+lookup strategies. -=-=(Psergey - Sun, 28 Feb 2010, 15:22)=-=- High-Level Specification modified. --- /tmp/wklog.90.old.23033 2010-02-28 15:22:09.000000000 +0000 +++ /tmp/wklog.90.new.23033 2010-02-28 15:22:09.000000000 +0000 @@ -1 +1,33 @@ +Basic idea on how this could be achieved: + +Pre-optimization phase +---------------------- + +The rewrite +~~~~~~~~~~~ +If we find a subquery predicate that is +- not processed by current semi-join optimizations +- is an AND-part of the WHERE/ON clause +- can be executed with Materialization + +then +- Remove the predicate from WHERE/ON clause +- Add a special JOIN_TAB object instead. + +Plan options +~~~~~~~~~~~~ +- Use the IN-equality to create KEYUSE elements. + +Optimization +------------ +- Pre-optimize the subquery so we know materialization cost +- Whenever best_access_path() encounters the "special JOIN_TAB" it should + consider two strategies: + A. Materialization and making lookups in the materialized table (if applicable) + B. Materialization and then scanning the materialized table. + + +EXPLAIN +------- +TODO how this will look in EXPLAIN output? -=-=(Psergey - Sun, 28 Feb 2010, 14:56)=-=- Dependency created: 91 now depends on 90 -=-=(Psergey - Sun, 28 Feb 2010, 14:54)=-=- Dependency deleted: 94 no longer depends on 90 -=-=(Psergey - Sun, 28 Feb 2010, 14:47)=-=- Title modified. --- /tmp/wklog.90.old.21903 2010-02-28 14:47:54.000000000 +0000 +++ /tmp/wklog.90.new.21903 2010-02-28 14:47:54.000000000 +0000 @@ -1 +1 @@ - Subqueries: Inside-out execution for non-semijoin materialized subqueries that are AND-parts of the WHERE +Subqueries: Inside-out execution for non-semijoin materialized subqueries that are AND-parts of the WHERE -=-=(Psergey - Sun, 28 Feb 2010, 14:47)=-=- High Level Description modified. --- /tmp/wklog.90.old.21880 2010-02-28 14:47:28.000000000 +0000 +++ /tmp/wklog.90.new.21880 2010-02-28 14:47:28.000000000 +0000 @@ -1,10 +1,17 @@ -For uncorrelated IN subqueries that can't be converted to semi-joins it is -necessary to make a cost-based choice between IN->EXISTS and Materialization -strategies. +Consider the following case: -Both strategies handle two cases: -1. A simple case w/o NULLs handling -2. Handling NULLs. +SELECT * FROM big_table +WHERE oe IN (SELECT ie FROM table_with_few_groups + WHERE ... + GROUP BY group_col) AND ... -This WL is about making cost-based decision for #1. +Here the best way to execute the query is: + Materialize the subquery; + # now run the join: + for each record R1 in materialized table + for each record R2 in big_table such that oe=R1 + pass R2 to output + +Semi-join materialization supports such strategy with SJM-Scan strategy. This WL +entry is about adding support for such strategies for non-semijoin subqueries. -=-=(Psergey - Sun, 28 Feb 2010, 14:47)=-=- Title modified. --- /tmp/wklog.90.old.21859 2010-02-28 14:47:02.000000000 +0000 +++ /tmp/wklog.90.new.21859 2010-02-28 14:47:02.000000000 +0000 @@ -1 +1 @@ -Subqueries: cost-based choice between Materialization and IN->EXISTS transformation + Subqueries: Inside-out execution for non-semijoin materialized subqueries that are AND-parts of the WHERE -=-=(Psergey - Sun, 28 Feb 2010, 14:08)=-=- Dependency created: 94 now depends on 90 DESCRIPTION: Consider the following case: SELECT * FROM big_table WHERE oe IN (SELECT ie FROM table_with_few_groups WHERE ... GROUP BY group_col) AND ... Here the best way to execute the query is: Materialize the subquery; # now run the join: for each record R1 in materialized table for each record R2 in big_table such that oe=R1 pass R2 to output Semi-join materialization supports such strategy with SJM-Scan strategy. This WL entry is about adding support for such strategies for non-semijoin subqueries. Once WL#89 is done, there will be a cost-based choice between Materialization+lookup, Materialization+scan, and IN->EXISTS+lookup strategies. HIGH-LEVEL SPECIFICATION: Basic idea on how this could be achieved: Pre-optimization phase ---------------------- The rewrite ~~~~~~~~~~~ If we find a subquery predicate that is - not processed by current semi-join optimizations - is an AND-part of the WHERE/ON clause - can be executed with Materialization then - Remove the predicate from WHERE/ON clause - Add a special JOIN_TAB object instead. Plan options ~~~~~~~~~~~~ - Use the IN-equality to create KEYUSE elements. Optimization ------------ - Pre-optimize the subquery so we know materialization cost - Whenever best_access_path() encounters the "special JOIN_TAB" it should consider two strategies: A. Materialization and making lookups in the materialized table (if applicable) B. Materialization and then scanning the materialized table. EXPLAIN ------- TODO how this will look in EXPLAIN output? ESTIMATED WORK TIME ESTIMATED COMPLETION DATE ----------------------------------------------------------------------- WorkLog (v3.5.9)

1 0

[Maria-developers] New (by Serg): backport libservices (98)
by worklog-noreply＠askmonty.org 28 Feb '10

28 Feb '10

----------------------------------------------------------------------- WORKLOG TASK -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- TASK...........: backport libservices CREATION DATE..: Sun, 28 Feb 2010, 15:27 SUPERVISOR.....: Sergei IMPLEMENTOR....: Sergei COPIES TO......: CATEGORY.......: Server-Sprint TASK ID........: 98 (http://askmonty.org/worklog/?tid=98) VERSION........: Server-5.2 STATUS.........: In-Progress PRIORITY.......: 60 WORKED HOURS...: 0 ESTIMATE.......: 1 (hours remain) ORIG. ESTIMATE.: 1 PROGRESS NOTES: DESCRIPTION: backport the libservices from MySQL 6.0 http://forge.mysql.com/worklog/task.php?id=4903 ESTIMATED WORK TIME ESTIMATED COMPLETION DATE ----------------------------------------------------------------------- WorkLog (v3.5.9)

1 0

[Maria-developers] New (by Serg): backport libservices (98)
by worklog-noreply＠askmonty.org 28 Feb '10

28 Feb '10

----------------------------------------------------------------------- WORKLOG TASK -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- TASK...........: backport libservices CREATION DATE..: Sun, 28 Feb 2010, 15:27 SUPERVISOR.....: Sergei IMPLEMENTOR....: Sergei COPIES TO......: CATEGORY.......: Server-Sprint TASK ID........: 98 (http://askmonty.org/worklog/?tid=98) VERSION........: Server-5.2 STATUS.........: In-Progress PRIORITY.......: 60 WORKED HOURS...: 0 ESTIMATE.......: 1 (hours remain) ORIG. ESTIMATE.: 1 PROGRESS NOTES: DESCRIPTION: backport the libservices from MySQL 6.0 http://forge.mysql.com/worklog/task.php?id=4903 ESTIMATED WORK TIME ESTIMATED COMPLETION DATE ----------------------------------------------------------------------- WorkLog (v3.5.9)

1 0

[Maria-developers] Updated (by Serg): backport MySQL-6.0 dbug extensions (97)
by worklog-noreply＠askmonty.org 28 Feb '10

28 Feb '10

----------------------------------------------------------------------- WORKLOG TASK -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- TASK...........: backport MySQL-6.0 dbug extensions CREATION DATE..: Sun, 28 Feb 2010, 15:10 SUPERVISOR.....: Sergei IMPLEMENTOR....: Sergei COPIES TO......: CATEGORY.......: Server-Sprint TASK ID........: 97 (http://askmonty.org/worklog/?tid=97) VERSION........: Server-5.2 STATUS.........: Cancelled PRIORITY.......: 60 WORKED HOURS...: 0 ESTIMATE.......: 1 (hours remain) ORIG. ESTIMATE.: 1 PROGRESS NOTES: -=-=(Serg - Sun, 28 Feb 2010, 15:22)=-=- High Level Description modified. --- /tmp/wklog.97.old.23137 2010-02-28 15:22:35.000000000 +0000 +++ /tmp/wklog.97.new.23137 2010-02-28 15:22:35.000000000 +0000 @@ -5,3 +5,6 @@ http://bazaar.launchpad.net/~mysql/mysql-server/mysql-6.0-codebase/revision… http://bazaar.launchpad.net/~mysql/mysql-server/mysql-6.0-codebase/revision… + +--- +already done -=-=(Serg - Sun, 28 Feb 2010, 15:21)=-=- Status updated. --- /tmp/wklog.97.old.23018 2010-02-28 15:21:30.000000000 +0000 +++ /tmp/wklog.97.new.23018 2010-02-28 15:21:30.000000000 +0000 @@ -1 +1 @@ -In-Progress +Cancelled -=-=(Serg - Sun, 28 Feb 2010, 15:19)=-=- High Level Description modified. --- /tmp/wklog.97.old.23005 2010-02-28 15:19:29.000000000 +0000 +++ /tmp/wklog.97.new.23005 2010-02-28 15:19:29.000000000 +0000 @@ -2,3 +2,6 @@ function/ syntax glob(7) wildcards unit tests + +http://bazaar.launchpad.net/~mysql/mysql-server/mysql-6.0-codebase/revision/2497.1183.1 +http://bazaar.launchpad.net/~mysql/mysql-server/mysql-6.0-codebase/revision/2497.1183.2 -=-=(Serg - Sun, 28 Feb 2010, 15:19)=-=- Title modified. --- /tmp/wklog.97.old.22992 2010-02-28 15:19:21.000000000 +0000 +++ /tmp/wklog.97.new.22992 2010-02-28 15:19:21.000000000 +0000 @@ -1 +1 @@ -backport MySQL-6.0 backup extensions +backport MySQL-6.0 dbug extensions DESCRIPTION: backport dbug features: function/ syntax glob(7) wildcards unit tests http://bazaar.launchpad.net/~mysql/mysql-server/mysql-6.0-codebase/revision… http://bazaar.launchpad.net/~mysql/mysql-server/mysql-6.0-codebase/revision… --- already done ESTIMATED WORK TIME ESTIMATED COMPLETION DATE ----------------------------------------------------------------------- WorkLog (v3.5.9)

1 0

[Maria-developers] Updated (by Serg): backport MySQL-6.0 dbug extensions (97)
by worklog-noreply＠askmonty.org 28 Feb '10

28 Feb '10

----------------------------------------------------------------------- WORKLOG TASK -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- TASK...........: backport MySQL-6.0 dbug extensions CREATION DATE..: Sun, 28 Feb 2010, 15:10 SUPERVISOR.....: Sergei IMPLEMENTOR....: Sergei COPIES TO......: CATEGORY.......: Server-Sprint TASK ID........: 97 (http://askmonty.org/worklog/?tid=97) VERSION........: Server-5.2 STATUS.........: Cancelled PRIORITY.......: 60 WORKED HOURS...: 0 ESTIMATE.......: 1 (hours remain) ORIG. ESTIMATE.: 1 PROGRESS NOTES: -=-=(Serg - Sun, 28 Feb 2010, 15:22)=-=- High Level Description modified. --- /tmp/wklog.97.old.23137 2010-02-28 15:22:35.000000000 +0000 +++ /tmp/wklog.97.new.23137 2010-02-28 15:22:35.000000000 +0000 @@ -5,3 +5,6 @@ http://bazaar.launchpad.net/~mysql/mysql-server/mysql-6.0-codebase/revision… http://bazaar.launchpad.net/~mysql/mysql-server/mysql-6.0-codebase/revision… + +--- +already done -=-=(Serg - Sun, 28 Feb 2010, 15:21)=-=- Status updated. --- /tmp/wklog.97.old.23018 2010-02-28 15:21:30.000000000 +0000 +++ /tmp/wklog.97.new.23018 2010-02-28 15:21:30.000000000 +0000 @@ -1 +1 @@ -In-Progress +Cancelled -=-=(Serg - Sun, 28 Feb 2010, 15:19)=-=- High Level Description modified. --- /tmp/wklog.97.old.23005 2010-02-28 15:19:29.000000000 +0000 +++ /tmp/wklog.97.new.23005 2010-02-28 15:19:29.000000000 +0000 @@ -2,3 +2,6 @@ function/ syntax glob(7) wildcards unit tests + +http://bazaar.launchpad.net/~mysql/mysql-server/mysql-6.0-codebase/revision/2497.1183.1 +http://bazaar.launchpad.net/~mysql/mysql-server/mysql-6.0-codebase/revision/2497.1183.2 -=-=(Serg - Sun, 28 Feb 2010, 15:19)=-=- Title modified. --- /tmp/wklog.97.old.22992 2010-02-28 15:19:21.000000000 +0000 +++ /tmp/wklog.97.new.22992 2010-02-28 15:19:21.000000000 +0000 @@ -1 +1 @@ -backport MySQL-6.0 backup extensions +backport MySQL-6.0 dbug extensions DESCRIPTION: backport dbug features: function/ syntax glob(7) wildcards unit tests http://bazaar.launchpad.net/~mysql/mysql-server/mysql-6.0-codebase/revision… http://bazaar.launchpad.net/~mysql/mysql-server/mysql-6.0-codebase/revision… --- already done ESTIMATED WORK TIME ESTIMATED COMPLETION DATE ----------------------------------------------------------------------- WorkLog (v3.5.9)

1 0