- developers - lists.mariadb.org

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

11 Mar '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....: Psergey COPIES TO......: Igor, Psergey, Timour CATEGORY.......: Server-RawIdeaBin TASK ID........: 90 (http://askmonty.org/worklog/?tid=90) VERSION........: Server-5.3 STATUS.........: Assigned PRIORITY.......: 60 WORKED HOURS...: 0 ESTIMATE.......: -1 (hours remain) ORIG. ESTIMATE.: 0 PROGRESS NOTES: -=-=(Igor - Wed, 10 Mar 2010, 21:52)=-=- Status updated. --- /tmp/wklog.90.old.882 2010-03-10 21:52:02.000000000 +0000 +++ /tmp/wklog.90.new.882 2010-03-10 21:52:02.000000000 +0000 @@ -1 +1 @@ -Un-Assigned +Assigned -=-=(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 Igor): Subqueries: cost-based choice between Materialization and IN->EXISTS transformation (89)
by worklog-noreply＠askmonty.org 11 Mar '10

11 Mar '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....: Timour COPIES TO......: Igor, Psergey, Timour CATEGORY.......: Server-Sprint TASK ID........: 89 (http://askmonty.org/worklog/?tid=89) VERSION........: Server-5.3 STATUS.........: Assigned PRIORITY.......: 60 WORKED HOURS...: 0 ESTIMATE.......: (hours remain) ORIG. ESTIMATE.: 0 PROGRESS NOTES: -=-=(Igor - Wed, 10 Mar 2010, 21:48)=-=- Category updated. --- /tmp/wklog.89.old.778 2010-03-10 21:48:08.000000000 +0000 +++ /tmp/wklog.89.new.778 2010-03-10 21:48:08.000000000 +0000 @@ -1 +1 @@ -Server-RawIdeaBin +Server-Sprint -=-=(Igor - Wed, 10 Mar 2010, 21:48)=-=- Status updated. --- /tmp/wklog.89.old.778 2010-03-10 21:48:08.000000000 +0000 +++ /tmp/wklog.89.new.778 2010-03-10 21:48:08.000000000 +0000 @@ -1 +1 @@ -Un-Assigned +Assigned -=-=(Psergey - Sun, 28 Feb 2010, 16:34)=-=- High-Level Specification modified. --- /tmp/wklog.89.old.24497 2010-02-28 16:34:05.000000000 +0000 +++ /tmp/wklog.89.new.24497 2010-02-28 16:34:05.000000000 +0000 @@ -36,8 +36,8 @@ So, we'll need to compute both exists_select_cost and materialization_cost. -Difficulty with computing the two costs ---------------------------------------- +Difficulty with the need to run select optimization two times +------------------------------------------------------------- The problem is in this scenario: 1. We compute materialization_cost by running optimization for the original subquery select. @@ -46,4 +46,10 @@ 3. Then we find that cost #1 is less and want to execute the materialization strategy. +The problem is that once one injects "oe=ie", it can trigger some optimization +steps that are not possible to undo. +- Example1: outer->inner join conversion +- non-Example: according to Igor, "oe=ie" won't participate in equality propagation. +- ... what else ? + -=-=(Psergey - Sun, 28 Feb 2010, 16:08)=-=- High-Level Specification modified. --- /tmp/wklog.89.old.24098 2010-02-28 16:08:56.000000000 +0000 +++ /tmp/wklog.89.new.24098 2010-02-28 16:08:56.000000000 +0000 @@ -36,3 +36,14 @@ So, we'll need to compute both exists_select_cost and materialization_cost. +Difficulty with computing the two costs +--------------------------------------- +The problem is in this scenario: +1. We compute materialization_cost by running optimization for the original + subquery select. +2. We compute exists_select_cost by running optimization for the subquery's + select with "oe=ie" injected into WHERE +3. Then we find that cost #1 is less and want to execute the materialization + strategy. + + -=-=(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. Difficulty with the need to run select optimization two times ------------------------------------------------------------- The problem is in this scenario: 1. We compute materialization_cost by running optimization for the original subquery select. 2. We compute exists_select_cost by running optimization for the subquery's select with "oe=ie" injected into WHERE 3. Then we find that cost #1 is less and want to execute the materialization strategy. The problem is that once one injects "oe=ie", it can trigger some optimization steps that are not possible to undo. - Example1: outer->inner join conversion - non-Example: according to Igor, "oe=ie" won't participate in equality propagation. - ... what else ? ESTIMATED WORK TIME ESTIMATED COMPLETION DATE ----------------------------------------------------------------------- WorkLog (v3.5.9)

1 0

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

11 Mar '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....: Timour COPIES TO......: Igor, Psergey, Timour CATEGORY.......: Server-Sprint TASK ID........: 89 (http://askmonty.org/worklog/?tid=89) VERSION........: Server-5.3 STATUS.........: Assigned PRIORITY.......: 60 WORKED HOURS...: 0 ESTIMATE.......: (hours remain) ORIG. ESTIMATE.: 0 PROGRESS NOTES: -=-=(Igor - Wed, 10 Mar 2010, 21:48)=-=- Category updated. --- /tmp/wklog.89.old.778 2010-03-10 21:48:08.000000000 +0000 +++ /tmp/wklog.89.new.778 2010-03-10 21:48:08.000000000 +0000 @@ -1 +1 @@ -Server-RawIdeaBin +Server-Sprint -=-=(Igor - Wed, 10 Mar 2010, 21:48)=-=- Status updated. --- /tmp/wklog.89.old.778 2010-03-10 21:48:08.000000000 +0000 +++ /tmp/wklog.89.new.778 2010-03-10 21:48:08.000000000 +0000 @@ -1 +1 @@ -Un-Assigned +Assigned -=-=(Psergey - Sun, 28 Feb 2010, 16:34)=-=- High-Level Specification modified. --- /tmp/wklog.89.old.24497 2010-02-28 16:34:05.000000000 +0000 +++ /tmp/wklog.89.new.24497 2010-02-28 16:34:05.000000000 +0000 @@ -36,8 +36,8 @@ So, we'll need to compute both exists_select_cost and materialization_cost. -Difficulty with computing the two costs ---------------------------------------- +Difficulty with the need to run select optimization two times +------------------------------------------------------------- The problem is in this scenario: 1. We compute materialization_cost by running optimization for the original subquery select. @@ -46,4 +46,10 @@ 3. Then we find that cost #1 is less and want to execute the materialization strategy. +The problem is that once one injects "oe=ie", it can trigger some optimization +steps that are not possible to undo. +- Example1: outer->inner join conversion +- non-Example: according to Igor, "oe=ie" won't participate in equality propagation. +- ... what else ? + -=-=(Psergey - Sun, 28 Feb 2010, 16:08)=-=- High-Level Specification modified. --- /tmp/wklog.89.old.24098 2010-02-28 16:08:56.000000000 +0000 +++ /tmp/wklog.89.new.24098 2010-02-28 16:08:56.000000000 +0000 @@ -36,3 +36,14 @@ So, we'll need to compute both exists_select_cost and materialization_cost. +Difficulty with computing the two costs +--------------------------------------- +The problem is in this scenario: +1. We compute materialization_cost by running optimization for the original + subquery select. +2. We compute exists_select_cost by running optimization for the subquery's + select with "oe=ie" injected into WHERE +3. Then we find that cost #1 is less and want to execute the materialization + strategy. + + -=-=(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. Difficulty with the need to run select optimization two times ------------------------------------------------------------- The problem is in this scenario: 1. We compute materialization_cost by running optimization for the original subquery select. 2. We compute exists_select_cost by running optimization for the subquery's select with "oe=ie" injected into WHERE 3. Then we find that cost #1 is less and want to execute the materialization strategy. The problem is that once one injects "oe=ie", it can trigger some optimization steps that are not possible to undo. - Example1: outer->inner join conversion - non-Example: according to Igor, "oe=ie" won't participate in equality propagation. - ... what else ? ESTIMATED WORK TIME ESTIMATED COMPLETION DATE ----------------------------------------------------------------------- WorkLog (v3.5.9)

1 0

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

11 Mar '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....: Timour COPIES TO......: Igor, Psergey, Timour CATEGORY.......: Server-Sprint TASK ID........: 89 (http://askmonty.org/worklog/?tid=89) VERSION........: Server-5.3 STATUS.........: Assigned PRIORITY.......: 60 WORKED HOURS...: 0 ESTIMATE.......: (hours remain) ORIG. ESTIMATE.: 0 PROGRESS NOTES: -=-=(Igor - Wed, 10 Mar 2010, 21:48)=-=- Category updated. --- /tmp/wklog.89.old.778 2010-03-10 21:48:08.000000000 +0000 +++ /tmp/wklog.89.new.778 2010-03-10 21:48:08.000000000 +0000 @@ -1 +1 @@ -Server-RawIdeaBin +Server-Sprint -=-=(Igor - Wed, 10 Mar 2010, 21:48)=-=- Status updated. --- /tmp/wklog.89.old.778 2010-03-10 21:48:08.000000000 +0000 +++ /tmp/wklog.89.new.778 2010-03-10 21:48:08.000000000 +0000 @@ -1 +1 @@ -Un-Assigned +Assigned -=-=(Psergey - Sun, 28 Feb 2010, 16:34)=-=- High-Level Specification modified. --- /tmp/wklog.89.old.24497 2010-02-28 16:34:05.000000000 +0000 +++ /tmp/wklog.89.new.24497 2010-02-28 16:34:05.000000000 +0000 @@ -36,8 +36,8 @@ So, we'll need to compute both exists_select_cost and materialization_cost. -Difficulty with computing the two costs ---------------------------------------- +Difficulty with the need to run select optimization two times +------------------------------------------------------------- The problem is in this scenario: 1. We compute materialization_cost by running optimization for the original subquery select. @@ -46,4 +46,10 @@ 3. Then we find that cost #1 is less and want to execute the materialization strategy. +The problem is that once one injects "oe=ie", it can trigger some optimization +steps that are not possible to undo. +- Example1: outer->inner join conversion +- non-Example: according to Igor, "oe=ie" won't participate in equality propagation. +- ... what else ? + -=-=(Psergey - Sun, 28 Feb 2010, 16:08)=-=- High-Level Specification modified. --- /tmp/wklog.89.old.24098 2010-02-28 16:08:56.000000000 +0000 +++ /tmp/wklog.89.new.24098 2010-02-28 16:08:56.000000000 +0000 @@ -36,3 +36,14 @@ So, we'll need to compute both exists_select_cost and materialization_cost. +Difficulty with computing the two costs +--------------------------------------- +The problem is in this scenario: +1. We compute materialization_cost by running optimization for the original + subquery select. +2. We compute exists_select_cost by running optimization for the subquery's + select with "oe=ie" injected into WHERE +3. Then we find that cost #1 is less and want to execute the materialization + strategy. + + -=-=(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. Difficulty with the need to run select optimization two times ------------------------------------------------------------- The problem is in this scenario: 1. We compute materialization_cost by running optimization for the original subquery select. 2. We compute exists_select_cost by running optimization for the subquery's select with "oe=ie" injected into WHERE 3. Then we find that cost #1 is less and want to execute the materialization strategy. The problem is that once one injects "oe=ie", it can trigger some optimization steps that are not possible to undo. - Example1: outer->inner join conversion - non-Example: according to Igor, "oe=ie" won't participate in equality propagation. - ... what else ? ESTIMATED WORK TIME ESTIMATED COMPLETION DATE ----------------------------------------------------------------------- WorkLog (v3.5.9)

1 0

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

11 Mar '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....: Timour COPIES TO......: Igor, Psergey, Timour CATEGORY.......: Server-Sprint TASK ID........: 89 (http://askmonty.org/worklog/?tid=89) VERSION........: Server-5.3 STATUS.........: Assigned PRIORITY.......: 60 WORKED HOURS...: 0 ESTIMATE.......: (hours remain) ORIG. ESTIMATE.: 0 PROGRESS NOTES: -=-=(Igor - Wed, 10 Mar 2010, 21:48)=-=- Category updated. --- /tmp/wklog.89.old.778 2010-03-10 21:48:08.000000000 +0000 +++ /tmp/wklog.89.new.778 2010-03-10 21:48:08.000000000 +0000 @@ -1 +1 @@ -Server-RawIdeaBin +Server-Sprint -=-=(Igor - Wed, 10 Mar 2010, 21:48)=-=- Status updated. --- /tmp/wklog.89.old.778 2010-03-10 21:48:08.000000000 +0000 +++ /tmp/wklog.89.new.778 2010-03-10 21:48:08.000000000 +0000 @@ -1 +1 @@ -Un-Assigned +Assigned -=-=(Psergey - Sun, 28 Feb 2010, 16:34)=-=- High-Level Specification modified. --- /tmp/wklog.89.old.24497 2010-02-28 16:34:05.000000000 +0000 +++ /tmp/wklog.89.new.24497 2010-02-28 16:34:05.000000000 +0000 @@ -36,8 +36,8 @@ So, we'll need to compute both exists_select_cost and materialization_cost. -Difficulty with computing the two costs ---------------------------------------- +Difficulty with the need to run select optimization two times +------------------------------------------------------------- The problem is in this scenario: 1. We compute materialization_cost by running optimization for the original subquery select. @@ -46,4 +46,10 @@ 3. Then we find that cost #1 is less and want to execute the materialization strategy. +The problem is that once one injects "oe=ie", it can trigger some optimization +steps that are not possible to undo. +- Example1: outer->inner join conversion +- non-Example: according to Igor, "oe=ie" won't participate in equality propagation. +- ... what else ? + -=-=(Psergey - Sun, 28 Feb 2010, 16:08)=-=- High-Level Specification modified. --- /tmp/wklog.89.old.24098 2010-02-28 16:08:56.000000000 +0000 +++ /tmp/wklog.89.new.24098 2010-02-28 16:08:56.000000000 +0000 @@ -36,3 +36,14 @@ So, we'll need to compute both exists_select_cost and materialization_cost. +Difficulty with computing the two costs +--------------------------------------- +The problem is in this scenario: +1. We compute materialization_cost by running optimization for the original + subquery select. +2. We compute exists_select_cost by running optimization for the subquery's + select with "oe=ie" injected into WHERE +3. Then we find that cost #1 is less and want to execute the materialization + strategy. + + -=-=(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. Difficulty with the need to run select optimization two times ------------------------------------------------------------- The problem is in this scenario: 1. We compute materialization_cost by running optimization for the original subquery select. 2. We compute exists_select_cost by running optimization for the subquery's select with "oe=ie" injected into WHERE 3. Then we find that cost #1 is less and want to execute the materialization strategy. The problem is that once one injects "oe=ie", it can trigger some optimization steps that are not possible to undo. - Example1: outer->inner join conversion - non-Example: according to Igor, "oe=ie" won't participate in equality propagation. - ... what else ? ESTIMATED WORK TIME ESTIMATED COMPLETION DATE ----------------------------------------------------------------------- WorkLog (v3.5.9)

1 0

[Maria-developers] Updated (by Igor): Subqueries backport: fix known semi-join subquery bugs (92)
by worklog-noreply＠askmonty.org 11 Mar '10

11 Mar '10

----------------------------------------------------------------------- WORKLOG TASK -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- TASK...........: Subqueries backport: fix known semi-join subquery bugs CREATION DATE..: Sun, 28 Feb 2010, 14:02 SUPERVISOR.....: Monty IMPLEMENTOR....: COPIES TO......: Igor, Psergey, Timour CATEGORY.......: Server-RawIdeaBin TASK ID........: 92 (http://askmonty.org/worklog/?tid=92) VERSION........: WorkLog-3.4 STATUS.........: Un-Assigned PRIORITY.......: 60 WORKED HOURS...: 0 ESTIMATE.......: 0 (hours remain) ORIG. ESTIMATE.: 0 PROGRESS NOTES: -=-=(Igor - Wed, 10 Mar 2010, 21:33)=-=- High Level Description modified. --- /tmp/wklog.92.old.32291 2010-03-10 21:33:29.000000000 +0000 +++ /tmp/wklog.92.new.32291 2010-03-10 21:33:29.000000000 +0000 @@ -1,3 +1,5 @@ +The goal of this task is to fix all known subquery semi-join bugs. + We must fix known subquery semi-join bugs. * outer join + semi join problem * Duplicate Weedout + join caching problem. -=-=(Psergey - Sun, 28 Feb 2010, 16:41)=-=- High Level Description modified. --- /tmp/wklog.92.old.24539 2010-02-28 16:41:06.000000000 +0000 +++ /tmp/wklog.92.new.24539 2010-02-28 16:41:06.000000000 +0000 @@ -1 +1,4 @@ We must fix known subquery semi-join bugs. +* outer join + semi join problem +* Duplicate Weedout + join caching problem. + -=-=(Psergey - Sun, 28 Feb 2010, 15:06)=-=- Dependency created: 91 now depends on 92 -=-=(Psergey - Sun, 28 Feb 2010, 15:06)=-=- High Level Description modified. --- /tmp/wklog.92.old.22593 2010-02-28 15:06:23.000000000 +0000 +++ /tmp/wklog.92.new.22593 2010-02-28 15:06:23.000000000 +0000 @@ -1 +1 @@ - +We must fix known subquery semi-join bugs. -=-=(Psergey - Sun, 28 Feb 2010, 15:03)=-=- Title modified. --- /tmp/wklog.92.old.22572 2010-02-28 15:03:51.000000000 +0000 +++ /tmp/wklog.92.new.22572 2010-02-28 15:03:51.000000000 +0000 @@ -1 +1 @@ -Unused +Subqueries backport: fix known semi-join subquery bugs -=-=(Psergey - Sun, 28 Feb 2010, 14:58)=-=- Dependency deleted: 91 no longer depends on 92 -=-=(Psergey - Sun, 28 Feb 2010, 14:58)=-=- Dependency created: 91 now depends on 92 -=-=(Psergey - Sun, 28 Feb 2010, 14:57)=-=- High Level Description modified. --- /tmp/wklog.92.old.22267 2010-02-28 14:57:52.000000000 +0000 +++ /tmp/wklog.92.new.22267 2010-02-28 14:57:52.000000000 +0000 @@ -1 +1 @@ -We must fix known semi-join subquery bugs. + -=-=(Psergey - Sun, 28 Feb 2010, 14:57)=-=- Title modified. --- /tmp/wklog.92.old.22249 2010-02-28 14:57:41.000000000 +0000 +++ /tmp/wklog.92.new.22249 2010-02-28 14:57:41.000000000 +0000 @@ -1 +1 @@ -Subqueries: Inside-out execution for non-semijoin materialized subqueries that are AND-parts of the WHERE +Unused -=-=(Psergey - Sun, 28 Feb 2010, 14:51)=-=- High Level Description modified. --- /tmp/wklog.92.old.21961 2010-02-28 14:51:06.000000000 +0000 +++ /tmp/wklog.92.new.21961 2010-02-28 14:51:06.000000000 +0000 @@ -1,18 +1 @@ -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. - +We must fix known semi-join subquery bugs. ------------------------------------------------------------ -=-=(View All Progress Notes, 11 total)=-=- http://askmonty.org/worklog/index.pl?tid=92&nolimit=1 DESCRIPTION: The goal of this task is to fix all known subquery semi-join bugs. We must fix known subquery semi-join bugs. * outer join + semi join problem * Duplicate Weedout + join caching problem. ESTIMATED WORK TIME ESTIMATED COMPLETION DATE ----------------------------------------------------------------------- WorkLog (v3.5.9)

1 0

[Maria-developers] Updated (by Igor): Subqueries backport: fix known semi-join subquery bugs (92)
by worklog-noreply＠askmonty.org 11 Mar '10

11 Mar '10

----------------------------------------------------------------------- WORKLOG TASK -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- TASK...........: Subqueries backport: fix known semi-join subquery bugs CREATION DATE..: Sun, 28 Feb 2010, 14:02 SUPERVISOR.....: Monty IMPLEMENTOR....: COPIES TO......: Igor, Psergey, Timour CATEGORY.......: Server-RawIdeaBin TASK ID........: 92 (http://askmonty.org/worklog/?tid=92) VERSION........: WorkLog-3.4 STATUS.........: Un-Assigned PRIORITY.......: 60 WORKED HOURS...: 0 ESTIMATE.......: 0 (hours remain) ORIG. ESTIMATE.: 0 PROGRESS NOTES: -=-=(Igor - Wed, 10 Mar 2010, 21:33)=-=- High Level Description modified. --- /tmp/wklog.92.old.32291 2010-03-10 21:33:29.000000000 +0000 +++ /tmp/wklog.92.new.32291 2010-03-10 21:33:29.000000000 +0000 @@ -1,3 +1,5 @@ +The goal of this task is to fix all known subquery semi-join bugs. + We must fix known subquery semi-join bugs. * outer join + semi join problem * Duplicate Weedout + join caching problem. -=-=(Psergey - Sun, 28 Feb 2010, 16:41)=-=- High Level Description modified. --- /tmp/wklog.92.old.24539 2010-02-28 16:41:06.000000000 +0000 +++ /tmp/wklog.92.new.24539 2010-02-28 16:41:06.000000000 +0000 @@ -1 +1,4 @@ We must fix known subquery semi-join bugs. +* outer join + semi join problem +* Duplicate Weedout + join caching problem. + -=-=(Psergey - Sun, 28 Feb 2010, 15:06)=-=- Dependency created: 91 now depends on 92 -=-=(Psergey - Sun, 28 Feb 2010, 15:06)=-=- High Level Description modified. --- /tmp/wklog.92.old.22593 2010-02-28 15:06:23.000000000 +0000 +++ /tmp/wklog.92.new.22593 2010-02-28 15:06:23.000000000 +0000 @@ -1 +1 @@ - +We must fix known subquery semi-join bugs. -=-=(Psergey - Sun, 28 Feb 2010, 15:03)=-=- Title modified. --- /tmp/wklog.92.old.22572 2010-02-28 15:03:51.000000000 +0000 +++ /tmp/wklog.92.new.22572 2010-02-28 15:03:51.000000000 +0000 @@ -1 +1 @@ -Unused +Subqueries backport: fix known semi-join subquery bugs -=-=(Psergey - Sun, 28 Feb 2010, 14:58)=-=- Dependency deleted: 91 no longer depends on 92 -=-=(Psergey - Sun, 28 Feb 2010, 14:58)=-=- Dependency created: 91 now depends on 92 -=-=(Psergey - Sun, 28 Feb 2010, 14:57)=-=- High Level Description modified. --- /tmp/wklog.92.old.22267 2010-02-28 14:57:52.000000000 +0000 +++ /tmp/wklog.92.new.22267 2010-02-28 14:57:52.000000000 +0000 @@ -1 +1 @@ -We must fix known semi-join subquery bugs. + -=-=(Psergey - Sun, 28 Feb 2010, 14:57)=-=- Title modified. --- /tmp/wklog.92.old.22249 2010-02-28 14:57:41.000000000 +0000 +++ /tmp/wklog.92.new.22249 2010-02-28 14:57:41.000000000 +0000 @@ -1 +1 @@ -Subqueries: Inside-out execution for non-semijoin materialized subqueries that are AND-parts of the WHERE +Unused -=-=(Psergey - Sun, 28 Feb 2010, 14:51)=-=- High Level Description modified. --- /tmp/wklog.92.old.21961 2010-02-28 14:51:06.000000000 +0000 +++ /tmp/wklog.92.new.21961 2010-02-28 14:51:06.000000000 +0000 @@ -1,18 +1 @@ -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. - +We must fix known semi-join subquery bugs. ------------------------------------------------------------ -=-=(View All Progress Notes, 11 total)=-=- http://askmonty.org/worklog/index.pl?tid=92&nolimit=1 DESCRIPTION: The goal of this task is to fix all known subquery semi-join bugs. We must fix known subquery semi-join bugs. * outer join + semi join problem * Duplicate Weedout + join caching problem. ESTIMATED WORK TIME ESTIMATED COMPLETION DATE ----------------------------------------------------------------------- WorkLog (v3.5.9)

1 0

[Maria-developers] Updated (by Igor): Subqueries backport: fix known semi-join subquery bugs (92)
by worklog-noreply＠askmonty.org 11 Mar '10

11 Mar '10

----------------------------------------------------------------------- WORKLOG TASK -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- TASK...........: Subqueries backport: fix known semi-join subquery bugs CREATION DATE..: Sun, 28 Feb 2010, 14:02 SUPERVISOR.....: Monty IMPLEMENTOR....: COPIES TO......: Igor, Psergey, Timour CATEGORY.......: Server-RawIdeaBin TASK ID........: 92 (http://askmonty.org/worklog/?tid=92) VERSION........: WorkLog-3.4 STATUS.........: Un-Assigned PRIORITY.......: 60 WORKED HOURS...: 0 ESTIMATE.......: 0 (hours remain) ORIG. ESTIMATE.: 0 PROGRESS NOTES: -=-=(Igor - Wed, 10 Mar 2010, 21:33)=-=- High Level Description modified. --- /tmp/wklog.92.old.32291 2010-03-10 21:33:29.000000000 +0000 +++ /tmp/wklog.92.new.32291 2010-03-10 21:33:29.000000000 +0000 @@ -1,3 +1,5 @@ +The goal of this task is to fix all known subquery semi-join bugs. + We must fix known subquery semi-join bugs. * outer join + semi join problem * Duplicate Weedout + join caching problem. -=-=(Psergey - Sun, 28 Feb 2010, 16:41)=-=- High Level Description modified. --- /tmp/wklog.92.old.24539 2010-02-28 16:41:06.000000000 +0000 +++ /tmp/wklog.92.new.24539 2010-02-28 16:41:06.000000000 +0000 @@ -1 +1,4 @@ We must fix known subquery semi-join bugs. +* outer join + semi join problem +* Duplicate Weedout + join caching problem. + -=-=(Psergey - Sun, 28 Feb 2010, 15:06)=-=- Dependency created: 91 now depends on 92 -=-=(Psergey - Sun, 28 Feb 2010, 15:06)=-=- High Level Description modified. --- /tmp/wklog.92.old.22593 2010-02-28 15:06:23.000000000 +0000 +++ /tmp/wklog.92.new.22593 2010-02-28 15:06:23.000000000 +0000 @@ -1 +1 @@ - +We must fix known subquery semi-join bugs. -=-=(Psergey - Sun, 28 Feb 2010, 15:03)=-=- Title modified. --- /tmp/wklog.92.old.22572 2010-02-28 15:03:51.000000000 +0000 +++ /tmp/wklog.92.new.22572 2010-02-28 15:03:51.000000000 +0000 @@ -1 +1 @@ -Unused +Subqueries backport: fix known semi-join subquery bugs -=-=(Psergey - Sun, 28 Feb 2010, 14:58)=-=- Dependency deleted: 91 no longer depends on 92 -=-=(Psergey - Sun, 28 Feb 2010, 14:58)=-=- Dependency created: 91 now depends on 92 -=-=(Psergey - Sun, 28 Feb 2010, 14:57)=-=- High Level Description modified. --- /tmp/wklog.92.old.22267 2010-02-28 14:57:52.000000000 +0000 +++ /tmp/wklog.92.new.22267 2010-02-28 14:57:52.000000000 +0000 @@ -1 +1 @@ -We must fix known semi-join subquery bugs. + -=-=(Psergey - Sun, 28 Feb 2010, 14:57)=-=- Title modified. --- /tmp/wklog.92.old.22249 2010-02-28 14:57:41.000000000 +0000 +++ /tmp/wklog.92.new.22249 2010-02-28 14:57:41.000000000 +0000 @@ -1 +1 @@ -Subqueries: Inside-out execution for non-semijoin materialized subqueries that are AND-parts of the WHERE +Unused -=-=(Psergey - Sun, 28 Feb 2010, 14:51)=-=- High Level Description modified. --- /tmp/wklog.92.old.21961 2010-02-28 14:51:06.000000000 +0000 +++ /tmp/wklog.92.new.21961 2010-02-28 14:51:06.000000000 +0000 @@ -1,18 +1 @@ -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. - +We must fix known semi-join subquery bugs. ------------------------------------------------------------ -=-=(View All Progress Notes, 11 total)=-=- http://askmonty.org/worklog/index.pl?tid=92&nolimit=1 DESCRIPTION: The goal of this task is to fix all known subquery semi-join bugs. We must fix known subquery semi-join bugs. * outer join + semi join problem * Duplicate Weedout + join caching problem. ESTIMATED WORK TIME ESTIMATED COMPLETION DATE ----------------------------------------------------------------------- WorkLog (v3.5.9)

1 0

[Maria-developers] Updated (by Igor): Subqueries backport: fix known semi-join subquery bugs (92)
by worklog-noreply＠askmonty.org 11 Mar '10

11 Mar '10

----------------------------------------------------------------------- WORKLOG TASK -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- TASK...........: Subqueries backport: fix known semi-join subquery bugs CREATION DATE..: Sun, 28 Feb 2010, 14:02 SUPERVISOR.....: Monty IMPLEMENTOR....: COPIES TO......: Igor, Psergey, Timour CATEGORY.......: Server-RawIdeaBin TASK ID........: 92 (http://askmonty.org/worklog/?tid=92) VERSION........: WorkLog-3.4 STATUS.........: Un-Assigned PRIORITY.......: 60 WORKED HOURS...: 0 ESTIMATE.......: 0 (hours remain) ORIG. ESTIMATE.: 0 PROGRESS NOTES: -=-=(Igor - Wed, 10 Mar 2010, 21:33)=-=- High Level Description modified. --- /tmp/wklog.92.old.32291 2010-03-10 21:33:29.000000000 +0000 +++ /tmp/wklog.92.new.32291 2010-03-10 21:33:29.000000000 +0000 @@ -1,3 +1,5 @@ +The goal of this task is to fix all known subquery semi-join bugs. + We must fix known subquery semi-join bugs. * outer join + semi join problem * Duplicate Weedout + join caching problem. -=-=(Psergey - Sun, 28 Feb 2010, 16:41)=-=- High Level Description modified. --- /tmp/wklog.92.old.24539 2010-02-28 16:41:06.000000000 +0000 +++ /tmp/wklog.92.new.24539 2010-02-28 16:41:06.000000000 +0000 @@ -1 +1,4 @@ We must fix known subquery semi-join bugs. +* outer join + semi join problem +* Duplicate Weedout + join caching problem. + -=-=(Psergey - Sun, 28 Feb 2010, 15:06)=-=- Dependency created: 91 now depends on 92 -=-=(Psergey - Sun, 28 Feb 2010, 15:06)=-=- High Level Description modified. --- /tmp/wklog.92.old.22593 2010-02-28 15:06:23.000000000 +0000 +++ /tmp/wklog.92.new.22593 2010-02-28 15:06:23.000000000 +0000 @@ -1 +1 @@ - +We must fix known subquery semi-join bugs. -=-=(Psergey - Sun, 28 Feb 2010, 15:03)=-=- Title modified. --- /tmp/wklog.92.old.22572 2010-02-28 15:03:51.000000000 +0000 +++ /tmp/wklog.92.new.22572 2010-02-28 15:03:51.000000000 +0000 @@ -1 +1 @@ -Unused +Subqueries backport: fix known semi-join subquery bugs -=-=(Psergey - Sun, 28 Feb 2010, 14:58)=-=- Dependency deleted: 91 no longer depends on 92 -=-=(Psergey - Sun, 28 Feb 2010, 14:58)=-=- Dependency created: 91 now depends on 92 -=-=(Psergey - Sun, 28 Feb 2010, 14:57)=-=- High Level Description modified. --- /tmp/wklog.92.old.22267 2010-02-28 14:57:52.000000000 +0000 +++ /tmp/wklog.92.new.22267 2010-02-28 14:57:52.000000000 +0000 @@ -1 +1 @@ -We must fix known semi-join subquery bugs. + -=-=(Psergey - Sun, 28 Feb 2010, 14:57)=-=- Title modified. --- /tmp/wklog.92.old.22249 2010-02-28 14:57:41.000000000 +0000 +++ /tmp/wklog.92.new.22249 2010-02-28 14:57:41.000000000 +0000 @@ -1 +1 @@ -Subqueries: Inside-out execution for non-semijoin materialized subqueries that are AND-parts of the WHERE +Unused -=-=(Psergey - Sun, 28 Feb 2010, 14:51)=-=- High Level Description modified. --- /tmp/wklog.92.old.21961 2010-02-28 14:51:06.000000000 +0000 +++ /tmp/wklog.92.new.21961 2010-02-28 14:51:06.000000000 +0000 @@ -1,18 +1 @@ -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. - +We must fix known semi-join subquery bugs. ------------------------------------------------------------ -=-=(View All Progress Notes, 11 total)=-=- http://askmonty.org/worklog/index.pl?tid=92&nolimit=1 DESCRIPTION: The goal of this task is to fix all known subquery semi-join bugs. We must fix known subquery semi-join bugs. * outer join + semi join problem * Duplicate Weedout + join caching problem. ESTIMATED WORK TIME ESTIMATED COMPLETION DATE ----------------------------------------------------------------------- WorkLog (v3.5.9)

1 0

[Maria-developers] Updated (by Igor): Subquery optimization: Avoid recalculating subquery if external fields values found in subquery cache (66)
by worklog-noreply＠askmonty.org 11 Mar '10

11 Mar '10

----------------------------------------------------------------------- WORKLOG TASK -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- TASK...........: Subquery optimization: Avoid recalculating subquery if external fields values found in subquery cache CREATION DATE..: Wed, 25 Nov 2009, 22:25 SUPERVISOR.....: Monty IMPLEMENTOR....: Sanja COPIES TO......: CATEGORY.......: Client-Sprint TASK ID........: 66 (http://askmonty.org/worklog/?tid=66) VERSION........: 9.x STATUS.........: Assigned PRIORITY.......: 60 WORKED HOURS...: 0 ESTIMATE.......: 0 (hours remain) ORIG. ESTIMATE.: 0 PROGRESS NOTES: -=-=(Igor - Wed, 10 Mar 2010, 21:29)=-=- High Level Description modified. --- /tmp/wklog.66.old.32188 2010-03-10 21:29:16.000000000 +0000 +++ /tmp/wklog.66.new.32188 2010-03-10 21:29:16.000000000 +0000 @@ -1,3 +1,10 @@ +The goal of this task is to optimize evaluation of subqueries and subquery +predicates by storing the results of a correlated subquery together with +correlation parameters in a cache and reusing those results for the same sets of +parameters. + +Here's what is to be done in this task in more details: + Collect all outer items/references (left part of the subquiery and outer references inside the subquery) in key string. Compare the string (which represents certain value set of the references) against values in hash table and -=-=(Igor - Wed, 10 Mar 2010, 21:13)=-=- Dependency created: 91 now depends on 66 -=-=(Igor - Wed, 10 Mar 2010, 21:12)=-=- Category updated. --- /tmp/wklog.66.old.31558 2010-03-10 21:12:50.000000000 +0000 +++ /tmp/wklog.66.new.31558 2010-03-10 21:12:50.000000000 +0000 @@ -1 +1 @@ -Server-BackLog +Client-Sprint -=-=(Igor - Wed, 10 Mar 2010, 21:12)=-=- Version updated. --- /tmp/wklog.66.old.31558 2010-03-10 21:12:50.000000000 +0000 +++ /tmp/wklog.66.new.31558 2010-03-10 21:12:50.000000000 +0000 @@ -1 +1 @@ -Server-5.3 +9.x -=-=(Monty - Fri, 29 Jan 2010, 19:07)=-=- Version updated. --- /tmp/wklog.66.old.5893 2010-01-29 19:07:10.000000000 +0200 +++ /tmp/wklog.66.new.5893 2010-01-29 19:07:10.000000000 +0200 @@ -1 +1 @@ -Server-5.2 +Server-5.3 -=-=(Psergey - Wed, 20 Jan 2010, 14:50)=-=- High-Level Specification modified. --- /tmp/wklog.66.old.26873 2010-01-20 14:50:41.000000000 +0200 +++ /tmp/wklog.66.new.26873 2010-01-20 14:50:41.000000000 +0200 @@ -4,7 +4,6 @@ To check/discuss: ----------------- -* Do we put subquery cache on all levels of subqueries or on highest level only * Will there be any means to measure subquery cache hit rate? * MySQL-6.0 has a one-element predicate result cache. It is called "left expression cache", grep for left_expr_cache in sql/item_subselect.* @@ -41,7 +40,12 @@ - subquery_item_result is 'bool' for subquery predicates, and is of some scalar or ROW(scalar1,...scalarN) type for scalar-context subquery. -We dont support cases when outer_expr or correlation_references are blobs. +We don't support cases when outer_expr or correlation_references are blobs. + +All subquery predicates are cached. That is, if one subquery predicate is +located within another, both of them will have caches (one option to reduce +cache memory usage was to use cache only for the upper-most select. we decided +against it). 2. Data structure used for the cache ------------------------------------ -=-=(Psergey - Wed, 20 Jan 2010, 13:07)=-=- High-Level Specification modified. --- /tmp/wklog.66.old.17649 2010-01-20 13:07:07.000000000 +0200 +++ /tmp/wklog.66.new.17649 2010-01-20 13:07:07.000000000 +0200 @@ -3,7 +3,13 @@ To check/discuss: - To put subquery cache on all levels of subqueries or on highest level only. +----------------- +* Do we put subquery cache on all levels of subqueries or on highest level only +* Will there be any means to measure subquery cache hit rate? +* MySQL-6.0 has a one-element predicate result cache. It is called "left + expression cache", grep for left_expr_cache in sql/item_subselect.* + When this WL is merged with 6.0's optimizations, these two caches will + need to be unified somehow. <contents> -=-=(Psergey - Mon, 18 Jan 2010, 16:40)=-=- Low Level Design modified. --- /tmp/wklog.66.old.24899 2010-01-18 16:40:16.000000000 +0200 +++ /tmp/wklog.66.new.24899 2010-01-18 16:40:16.000000000 +0200 @@ -1,3 +1,5 @@ +* Target version: base on mysql-5.2 code + All items on which subquery depend could be collected in st_select_lex::mark_as_dependent (direct of indirect reference?) -=-=(Psergey - Mon, 18 Jan 2010, 16:37)=-=- Low Level Design modified. --- /tmp/wklog.66.old.24586 2010-01-18 16:37:07.000000000 +0200 +++ /tmp/wklog.66.new.24586 2010-01-18 16:37:07.000000000 +0200 @@ -4,6 +4,11 @@ Temporary table index should be created by all fields except result field (TMP_TABLE_PARAM::keyinfo). +How to fill the temptable +------------------------- +Can reuse approach from SJ-Materialization. Its code is in end_sj_materialize() +and is supposed to be quite trivial. + How to make lookups into temptable ---------------------------------- We'll reuse approach used by SJ-Materialization in 6.0. -=-=(Psergey - Mon, 18 Jan 2010, 16:34)=-=- Low Level Design modified. --- /tmp/wklog.66.old.24328 2010-01-18 16:34:19.000000000 +0200 +++ /tmp/wklog.66.new.24328 2010-01-18 16:34:19.000000000 +0200 @@ -32,8 +32,8 @@ Question: or perhaps that is not necessarry? </questionable> -Execution process -~~~~~~~~~~~~~~~~~ +Doing the lookup +~~~~~~~~~~~~~~~~ SJ-Materialization does lookup in sub_select_sjm(), with this code: /* Do index lookup in the materialized table */ @@ -42,4 +42,12 @@ if (res || !sjm->in_equality->val_int()) DBUG_RETURN(NESTED_LOOP_NO_MORE_ROWS); +The code in this WL will use the same approach +Extracting the value of the subquery predicate +~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ +The goal of making the lookup is to get the value of subquery predicate. +This is done by creating an Item_field $I which refers to appropriate +temporary table's field and then subquery_predicate->val_int() will invoke +$I->val_int(), subquery_predicate->val_str() will invoke $I->val_str() and so +forth. ------------------------------------------------------------ -=-=(View All Progress Notes, 17 total)=-=- http://askmonty.org/worklog/index.pl?tid=66&nolimit=1 DESCRIPTION: The goal of this task is to optimize evaluation of subqueries and subquery predicates by storing the results of a correlated subquery together with correlation parameters in a cache and reusing those results for the same sets of parameters. Here's what is to be done in this task in more details: Collect all outer items/references (left part of the subquiery and outer references inside the subquery) in key string. Compare the string (which represents certain value set of the references) against values in hash table and return cached result of subquery if the reference values combination has already been used. For example in the following subquery: (L1, L2) IN (SELECT A, B FROM T WHERE T.F1>OTER_FIELD) set of references to look into the subquery cache is (L1, L2, OTER_FIELD). The subquery cache should be implemented as simple LRU connected to the subquery. Size of the subquery cache (in number of results (but maybe in used memory amount)) is limited by session variable (query parameter?). HIGH-LEVEL SPECIFICATION: Attach subquery cache to each Item_subquery. Interface should allow to use hash or temporary table inside. To check/discuss: ----------------- * Will there be any means to measure subquery cache hit rate? * MySQL-6.0 has a one-element predicate result cache. It is called "left expression cache", grep for left_expr_cache in sql/item_subselect.* When this WL is merged with 6.0's optimizations, these two caches will need to be unified somehow. <contents> 1. Scope of the task 2. Data structure used for the cache 3. Cache size 4. Interplay with other subquery optimizations 5. User interface </contents> 1. Scope of the task -------------------- This WL should handle all subquery predicates, i.e. it should handle these cases: outer_expr IN (SELECT correlated_select) outer_expr $CMP$ ALL/ANY (SELECT correlated_select) EXISTS (SELECT correlated_select) scalar-context subquery: (SELECT correlated_select) The cache will maintain (outer_expr, correlation_references)-> subquery_item_result mapping, where - correlation_references is a list of tablename.column_name that are referred from the correlated_select but tablename is a table that is ouside the subquery. - subquery_item_result is 'bool' for subquery predicates, and is of some scalar or ROW(scalar1,...scalarN) type for scalar-context subquery. We don't support cases when outer_expr or correlation_references are blobs. All subquery predicates are cached. That is, if one subquery predicate is located within another, both of them will have caches (one option to reduce cache memory usage was to use cache only for the upper-most select. we decided against it). 2. Data structure used for the cache ------------------------------------ There are two data structures available in the codebase that will allow fast equality lookups: 1. HASH (mysys/hash.c) tables 2. Temporary tables (the ones that are used for e.g. GROUP BY) None of them has any support for element eviction on overflow (using LRU or some other policy). Query cache and MyISAM/Maria's key/page cache ought to support some eviction mechanism, but code-wise it is not readily reusable, one will need to factor it out (or copy it). We choose to use #2, and not to have any eviction policy. See subsequent sections for details and reasoning behind the decision. 3. Cache size ------------- Typically, a cache has some maximum size and a policy which is used to select a cache entry for removal when the cache becomes full (e.g. find and remove the least [recently] used entry) For this WL entry we will use a cache of infinite size. The reasoning behind this is that: - is is easy to do: we have temporary tables that can grow to arbitrarily large size while still providing the same insert/lookup interface. - it suits us: unless the subquery is resolved with one index lookup, hitting the cache would be many times cheaper than re-running the subquery, so cache is worth having. 4. Interplay with other subquery optimizations ---------------------------------------------- * This WL entry should not care about IN->EXISTS transformation: caching for IN subquery and result of its conversion to EXISTS would work in the same way. * This optimization is orthogonal to <=>ANY -> MIN/MAX rewrite (it will work/be useful irrespectively of whether the rewrite has been performed or not) * TODO: compare this with materialization for uncorrelated IN-subqueries. Is this basically the same? A: no, it is not: - IN-Materialization has to perform full materialization before it can do the first subquery evaluation. This WL's code has almost no startup costs. - This optimization has temp.table of (corr_reference, predicate_value), while IN-materialization will have (corr_reference) only. 5. User interface ----------------- * There will be an @@optimizer_switch flag to turn this optimization on and off (TODO: name of the flag?) * TODO: how do we show this in EXPLAIN [EXTENDED]? The most easiest is to print something in the warning text of EXPLAIN EXTEDED that would indicate use of cache. * temporary table sizing (max size for heap table, whether to use MyISAM or Maria) will be controlled with common temp.table control variables. LOW-LEVEL DESIGN: * Target version: base on mysql-5.2 code All items on which subquery depend could be collected in st_select_lex::mark_as_dependent (direct of indirect reference?) Temporary table index should be created by all fields except result field (TMP_TABLE_PARAM::keyinfo). How to fill the temptable ------------------------- Can reuse approach from SJ-Materialization. Its code is in end_sj_materialize() and is supposed to be quite trivial. How to make lookups into temptable ---------------------------------- We'll reuse approach used by SJ-Materialization in 6.0. Setup process ~~~~~~~~~~~~~ Setup is performed in the same way as in setup_sj_materialization(), see the code that starts these lines: /* Create/initialize everything we will need to index lookups into the temptable. */ and ends at this line: Remove the injected semi-join IN-equalities from join_tab conds. This <questionable> We'll also need to check equalities, i.e. do an equivalent of this: if (!(sjm->in_equality= create_subq_in_equalities(thd, sjm, emb_sj_nest->sj_subq_pred))) DBUG_RETURN(TRUE); /* purecov: inspected */ Question: or perhaps that is not necessarry? </questionable> Doing the lookup ~~~~~~~~~~~~~~~~ SJ-Materialization does lookup in sub_select_sjm(), with this code: /* Do index lookup in the materialized table */ if ((res= join_read_key2(join_tab, sjm->table, sjm->tab_ref)) == 1) DBUG_RETURN(NESTED_LOOP_ERROR); /* purecov: inspected */ if (res || !sjm->in_equality->val_int()) DBUG_RETURN(NESTED_LOOP_NO_MORE_ROWS); The code in this WL will use the same approach Extracting the value of the subquery predicate ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ The goal of making the lookup is to get the value of subquery predicate. This is done by creating an Item_field $I which refers to appropriate temporary table's field and then subquery_predicate->val_int() will invoke $I->val_int(), subquery_predicate->val_str() will invoke $I->val_str() and so forth. ESTIMATED WORK TIME ESTIMATED COMPLETION DATE ----------------------------------------------------------------------- WorkLog (v3.5.9)

1 0