- developers - lists.mariadb.org

[Maria-developers] Updated (by Sergei): options for CREATE TABLE (43)
by worklog-noreply＠askmonty.org 18 Jan '10

18 Jan '10

----------------------------------------------------------------------- WORKLOG TASK -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- TASK...........: options for CREATE TABLE CREATION DATE..: Tue, 11 Aug 2009, 17:02 SUPERVISOR.....: Bothorsen IMPLEMENTOR....: Sanja COPIES TO......: Sergei, Monty CATEGORY.......: Server-BackLog TASK ID........: 43 (http://askmonty.org/worklog/?tid=43) VERSION........: Server-5.2 STATUS.........: Assigned PRIORITY.......: 60 WORKED HOURS...: 0 ESTIMATE.......: 32 (hours remain) ORIG. ESTIMATE.: 32 PROGRESS NOTES: -=-=(Sergei - Mon, 18 Jan 2010, 22:12)=-=- Observers changed: Monty,Sergei -=-=(Monty - Tue, 12 Jan 2010, 17:04)=-=- Version updated. --- /tmp/wklog.43.old.21802 2010-01-12 17:04:31.000000000 +0200 +++ /tmp/wklog.43.new.21802 2010-01-12 17:04:31.000000000 +0200 @@ -1 +1 @@ -Server-5.1 +Server-5.2 -=-=(Guest - Fri, 18 Sep 2009, 14:24)=-=- Low Level Design modified. --- /tmp/wklog.43.old.31654 2009-09-18 14:24:41.000000000 +0300 +++ /tmp/wklog.43.new.31654 2009-09-18 14:24:41.000000000 +0300 @@ -2,4 +2,6 @@ Handler have access to the options during creation and after opening frm. +It should has C interface. + -=-=(Sanja - Fri, 18 Sep 2009, 13:32)=-=- Low Level Design modified. --- /tmp/wklog.43.old.29567 2009-09-18 13:32:41.000000000 +0300 +++ /tmp/wklog.43.new.29567 2009-09-18 13:32:41.000000000 +0300 @@ -1 +1,5 @@ +Options stored in a list as pairs key, value which are LEX_STRING. + +Handler have access to the options during creation and after opening frm. + -=-=(Sanja - Fri, 18 Sep 2009, 13:21)=-=- High-Level Specification modified. --- /tmp/wklog.43.old.29107 2009-09-18 13:21:19.000000000 +0300 +++ /tmp/wklog.43.new.29107 2009-09-18 13:21:19.000000000 +0300 @@ -6,7 +6,8 @@ table_option1=tval1, table_option2=tval2; Exclusion should be made for old table and key options where -'=' was not obligatory. +'=' was not obligatory. Behaviour and way of storage for existing options will +be left as is. Old key options: KEY_BLOCK_SIZE <num> -> KEY_BLOCK_SIZE=num @@ -42,6 +43,6 @@ For fields options can go with field attributes (NOT NULL, UNIQUE and so on) can be separated from them by '=' sign. - - +Incorrect option during creation/altering table lead only to worning. During +opening unrecognised options should be ignored. -=-=(Guest - Tue, 11 Aug 2009, 19:57)=-=- High-Level Specification modified. --- /tmp/wklog.43.old.31856 2009-08-11 19:57:38.000000000 +0300 +++ /tmp/wklog.43.new.31856 2009-08-11 19:57:38.000000000 +0300 @@ -5,8 +5,43 @@ key key1(field) key_opt1=kval1 key_opt2=kval2) table_option1=tval1, table_option2=tval2; -Exclusion should be made for old table and key (KEY_BLOCK_SIZE) options where +Exclusion should be made for old table and key options where '=' was not obligatory. +Old key options: +KEY_BLOCK_SIZE <num> -> KEY_BLOCK_SIZE=num +WITH PARSER <name> -> PARSER=name + +Old table options: +ENGINE name -> ENGINE=name +TYPE name -> TYPE=name +MAX_ROWS num -> MAX_ROWS=num +MIX_ROWS num -> MIX_ROWS=num +AVG_ROW_LENGTH num -> AVG_ROW_LENGTH=num +PASSWORD string -> PASSWORD=string +COMMENT string -> COMMENT=string +AUTO_INCREMENT num -> AUTO_INCREMENT=num +PACK_KEYS num/default -> PACK_KEYS=num/default +CHECKSUM num -> CHECKSUM=num +TABLE_CHECKSUM num -> TABLE_CHECKSUM=num +PAGE_CHECKSUM num -> PAGE_CHECKSUM=num +DELAY_KEY_WRITE num -> DELAY_KEY_WRITE=num +ROW_FORMAT name -> ROW_FORMAT=name +INSERT_METHOD name -> INSERT_METHOD=name +KEY_BLOCK_SIZE num -> KEY_BLOCK_SIZE=num +TRANSACTIONAL num -> TRANSACTIONAL=num + +Table options which will be left hardcoded +UNION +default charset +default collation +DATA DIRECTORY +TABLESPACE +STORAGE + For fields options can go with field attributes (NOT NULL, UNIQUE and so on) can be separated from them by '=' sign. + + + + -=-=(Guest - Tue, 11 Aug 2009, 19:36)=-=- High-Level Specification modified. --- /tmp/wklog.43.old.30883 2009-08-11 19:36:45.000000000 +0300 +++ /tmp/wklog.43.new.30883 2009-08-11 19:36:45.000000000 +0300 @@ -1 +1,12 @@ +Table definition ca looks like following +CREATE TABLE table + (field int ... field_opt1=fval1 field_opt2=fval2, + key key1(field) key_opt1=kval1 key_opt2=kval2) + table_option1=tval1, table_option2=tval2; + +Exclusion should be made for old table and key (KEY_BLOCK_SIZE) options where +'=' was not obligatory. + +For fields options can go with field attributes (NOT NULL, UNIQUE and so on) can +be separated from them by '=' sign. DESCRIPTION: Add ability to create table with additional option which can be passed to engine. Also make current options such as TRANSACTIONAL working via this mechanism. HIGH-LEVEL SPECIFICATION: Table definition ca looks like following CREATE TABLE table (field int ... field_opt1=fval1 field_opt2=fval2, key key1(field) key_opt1=kval1 key_opt2=kval2) table_option1=tval1, table_option2=tval2; Exclusion should be made for old table and key options where '=' was not obligatory. Behaviour and way of storage for existing options will be left as is. Old key options: KEY_BLOCK_SIZE <num> -> KEY_BLOCK_SIZE=num WITH PARSER <name> -> PARSER=name Old table options: ENGINE name -> ENGINE=name TYPE name -> TYPE=name MAX_ROWS num -> MAX_ROWS=num MIX_ROWS num -> MIX_ROWS=num AVG_ROW_LENGTH num -> AVG_ROW_LENGTH=num PASSWORD string -> PASSWORD=string COMMENT string -> COMMENT=string AUTO_INCREMENT num -> AUTO_INCREMENT=num PACK_KEYS num/default -> PACK_KEYS=num/default CHECKSUM num -> CHECKSUM=num TABLE_CHECKSUM num -> TABLE_CHECKSUM=num PAGE_CHECKSUM num -> PAGE_CHECKSUM=num DELAY_KEY_WRITE num -> DELAY_KEY_WRITE=num ROW_FORMAT name -> ROW_FORMAT=name INSERT_METHOD name -> INSERT_METHOD=name KEY_BLOCK_SIZE num -> KEY_BLOCK_SIZE=num TRANSACTIONAL num -> TRANSACTIONAL=num Table options which will be left hardcoded UNION default charset default collation DATA DIRECTORY TABLESPACE STORAGE For fields options can go with field attributes (NOT NULL, UNIQUE and so on) can be separated from them by '=' sign. Incorrect option during creation/altering table lead only to worning. During opening unrecognised options should be ignored. LOW-LEVEL DESIGN: Options stored in a list as pairs key, value which are LEX_STRING. Handler have access to the options during creation and after opening frm. It should has C interface. ESTIMATED WORK TIME ESTIMATED COMPLETION DATE ----------------------------------------------------------------------- WorkLog (v3.5.9)

1 0

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

18 Jan '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.......: Server-BackLog TASK ID........: 66 (http://askmonty.org/worklog/?tid=66) VERSION........: Server-5.2 STATUS.........: Assigned PRIORITY.......: 60 WORKED HOURS...: 0 ESTIMATE.......: 0 (hours remain) ORIG. ESTIMATE.: 0 PROGRESS NOTES: -=-=(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. -=-=(Psergey - Mon, 18 Jan 2010, 16:23)=-=- Low Level Design modified. --- /tmp/wklog.66.old.23203 2010-01-18 16:23:18.000000000 +0200 +++ /tmp/wklog.66.new.23203 2010-01-18 16:23:18.000000000 +0200 @@ -31,3 +31,15 @@ Question: or perhaps that is not necessarry? </questionable> + +Execution process +~~~~~~~~~~~~~~~~~ +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); + + -=-=(Psergey - Mon, 18 Jan 2010, 16:22)=-=- Low Level Design modified. --- /tmp/wklog.66.old.23076 2010-01-18 16:22:07.000000000 +0200 +++ /tmp/wklog.66.new.23076 2010-01-18 16:22:07.000000000 +0200 @@ -4,3 +4,30 @@ Temporary table index should be created by all fields except result field (TMP_TABLE_PARAM::keyinfo). +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> -=-=(Psergey - Tue, 12 Jan 2010, 18:39)=-=- High-Level Specification modified. --- /tmp/wklog.66.old.31666 2010-01-12 18:39:43.000000000 +0200 +++ /tmp/wklog.66.new.31666 2010-01-12 18:39:43.000000000 +0200 @@ -4,3 +4,99 @@ To check/discuss: To put subquery cache on all levels of subqueries or on highest level only. + + +<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 dont support cases when outer_expr or correlation_references are blobs. + +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. + -=-=(Psergey - Mon, 11 Jan 2010, 13:25)=-=- As of today, there is code that - collects outside references - creates a temporary table with index that would allow for fast lookups. there is no code to - fill the temporary table - make lookups into it Reported zero hours worked. Estimate unchanged. -=-=(Sanja - Fri, 11 Dec 2009, 15:09)=-=- High-Level Specification modified. --- /tmp/wklog.66.old.28164 2009-12-11 15:09:15.000000000 +0200 +++ /tmp/wklog.66.new.28164 2009-12-11 15:09:15.000000000 +0200 @@ -3,4 +3,4 @@ To check/discuss: -Are there sens to put subquery cache on all levels of subqueries of on highest. + To put subquery cache on all levels of subqueries or on highest level only. -=-=(Sanja - Fri, 11 Dec 2009, 15:08)=-=- Low Level Design modified. --- /tmp/wklog.66.old.28072 2009-12-11 15:08:16.000000000 +0200 +++ /tmp/wklog.66.new.28072 2009-12-11 15:08:16.000000000 +0200 @@ -1 +1,6 @@ +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). -=-=(Sanja - Fri, 11 Dec 2009, 15:05)=-=- High-Level Specification modified. --- /tmp/wklog.66.old.27795 2009-12-11 15:05:04.000000000 +0200 +++ /tmp/wklog.66.new.27795 2009-12-11 15:05:04.000000000 +0200 @@ -1 +1,6 @@ +Attach subquery cache to each Item_subquery. Interface should allow to use hash +or temporary table inside. + +To check/discuss: +Are there sens to put subquery cache on all levels of subqueries of on highest. DESCRIPTION: 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: To put subquery cache on all levels of subqueries or on highest level only. <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 dont support cases when outer_expr or correlation_references are blobs. 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

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

18 Jan '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.......: Server-BackLog TASK ID........: 66 (http://askmonty.org/worklog/?tid=66) VERSION........: Server-5.2 STATUS.........: Assigned PRIORITY.......: 60 WORKED HOURS...: 0 ESTIMATE.......: 0 (hours remain) ORIG. ESTIMATE.: 0 PROGRESS NOTES: -=-=(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. -=-=(Psergey - Mon, 18 Jan 2010, 16:23)=-=- Low Level Design modified. --- /tmp/wklog.66.old.23203 2010-01-18 16:23:18.000000000 +0200 +++ /tmp/wklog.66.new.23203 2010-01-18 16:23:18.000000000 +0200 @@ -31,3 +31,15 @@ Question: or perhaps that is not necessarry? </questionable> + +Execution process +~~~~~~~~~~~~~~~~~ +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); + + -=-=(Psergey - Mon, 18 Jan 2010, 16:22)=-=- Low Level Design modified. --- /tmp/wklog.66.old.23076 2010-01-18 16:22:07.000000000 +0200 +++ /tmp/wklog.66.new.23076 2010-01-18 16:22:07.000000000 +0200 @@ -4,3 +4,30 @@ Temporary table index should be created by all fields except result field (TMP_TABLE_PARAM::keyinfo). +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> -=-=(Psergey - Tue, 12 Jan 2010, 18:39)=-=- High-Level Specification modified. --- /tmp/wklog.66.old.31666 2010-01-12 18:39:43.000000000 +0200 +++ /tmp/wklog.66.new.31666 2010-01-12 18:39:43.000000000 +0200 @@ -4,3 +4,99 @@ To check/discuss: To put subquery cache on all levels of subqueries or on highest level only. + + +<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 dont support cases when outer_expr or correlation_references are blobs. + +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. + -=-=(Psergey - Mon, 11 Jan 2010, 13:25)=-=- As of today, there is code that - collects outside references - creates a temporary table with index that would allow for fast lookups. there is no code to - fill the temporary table - make lookups into it Reported zero hours worked. Estimate unchanged. -=-=(Sanja - Fri, 11 Dec 2009, 15:09)=-=- High-Level Specification modified. --- /tmp/wklog.66.old.28164 2009-12-11 15:09:15.000000000 +0200 +++ /tmp/wklog.66.new.28164 2009-12-11 15:09:15.000000000 +0200 @@ -3,4 +3,4 @@ To check/discuss: -Are there sens to put subquery cache on all levels of subqueries of on highest. + To put subquery cache on all levels of subqueries or on highest level only. -=-=(Sanja - Fri, 11 Dec 2009, 15:08)=-=- Low Level Design modified. --- /tmp/wklog.66.old.28072 2009-12-11 15:08:16.000000000 +0200 +++ /tmp/wklog.66.new.28072 2009-12-11 15:08:16.000000000 +0200 @@ -1 +1,6 @@ +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). -=-=(Sanja - Fri, 11 Dec 2009, 15:05)=-=- High-Level Specification modified. --- /tmp/wklog.66.old.27795 2009-12-11 15:05:04.000000000 +0200 +++ /tmp/wklog.66.new.27795 2009-12-11 15:05:04.000000000 +0200 @@ -1 +1,6 @@ +Attach subquery cache to each Item_subquery. Interface should allow to use hash +or temporary table inside. + +To check/discuss: +Are there sens to put subquery cache on all levels of subqueries of on highest. DESCRIPTION: 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: To put subquery cache on all levels of subqueries or on highest level only. <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 dont support cases when outer_expr or correlation_references are blobs. 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

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

18 Jan '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.......: Server-BackLog TASK ID........: 66 (http://askmonty.org/worklog/?tid=66) VERSION........: Server-5.2 STATUS.........: Assigned PRIORITY.......: 60 WORKED HOURS...: 0 ESTIMATE.......: 0 (hours remain) ORIG. ESTIMATE.: 0 PROGRESS NOTES: -=-=(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. -=-=(Psergey - Mon, 18 Jan 2010, 16:23)=-=- Low Level Design modified. --- /tmp/wklog.66.old.23203 2010-01-18 16:23:18.000000000 +0200 +++ /tmp/wklog.66.new.23203 2010-01-18 16:23:18.000000000 +0200 @@ -31,3 +31,15 @@ Question: or perhaps that is not necessarry? </questionable> + +Execution process +~~~~~~~~~~~~~~~~~ +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); + + -=-=(Psergey - Mon, 18 Jan 2010, 16:22)=-=- Low Level Design modified. --- /tmp/wklog.66.old.23076 2010-01-18 16:22:07.000000000 +0200 +++ /tmp/wklog.66.new.23076 2010-01-18 16:22:07.000000000 +0200 @@ -4,3 +4,30 @@ Temporary table index should be created by all fields except result field (TMP_TABLE_PARAM::keyinfo). +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> -=-=(Psergey - Tue, 12 Jan 2010, 18:39)=-=- High-Level Specification modified. --- /tmp/wklog.66.old.31666 2010-01-12 18:39:43.000000000 +0200 +++ /tmp/wklog.66.new.31666 2010-01-12 18:39:43.000000000 +0200 @@ -4,3 +4,99 @@ To check/discuss: To put subquery cache on all levels of subqueries or on highest level only. + + +<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 dont support cases when outer_expr or correlation_references are blobs. + +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. + -=-=(Psergey - Mon, 11 Jan 2010, 13:25)=-=- As of today, there is code that - collects outside references - creates a temporary table with index that would allow for fast lookups. there is no code to - fill the temporary table - make lookups into it Reported zero hours worked. Estimate unchanged. -=-=(Sanja - Fri, 11 Dec 2009, 15:09)=-=- High-Level Specification modified. --- /tmp/wklog.66.old.28164 2009-12-11 15:09:15.000000000 +0200 +++ /tmp/wklog.66.new.28164 2009-12-11 15:09:15.000000000 +0200 @@ -3,4 +3,4 @@ To check/discuss: -Are there sens to put subquery cache on all levels of subqueries of on highest. + To put subquery cache on all levels of subqueries or on highest level only. -=-=(Sanja - Fri, 11 Dec 2009, 15:08)=-=- Low Level Design modified. --- /tmp/wklog.66.old.28072 2009-12-11 15:08:16.000000000 +0200 +++ /tmp/wklog.66.new.28072 2009-12-11 15:08:16.000000000 +0200 @@ -1 +1,6 @@ +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). -=-=(Sanja - Fri, 11 Dec 2009, 15:05)=-=- High-Level Specification modified. --- /tmp/wklog.66.old.27795 2009-12-11 15:05:04.000000000 +0200 +++ /tmp/wklog.66.new.27795 2009-12-11 15:05:04.000000000 +0200 @@ -1 +1,6 @@ +Attach subquery cache to each Item_subquery. Interface should allow to use hash +or temporary table inside. + +To check/discuss: +Are there sens to put subquery cache on all levels of subqueries of on highest. DESCRIPTION: 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: To put subquery cache on all levels of subqueries or on highest level only. <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 dont support cases when outer_expr or correlation_references are blobs. 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: 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

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

18 Jan '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.......: Server-BackLog TASK ID........: 66 (http://askmonty.org/worklog/?tid=66) VERSION........: Server-5.2 STATUS.........: Assigned PRIORITY.......: 60 WORKED HOURS...: 0 ESTIMATE.......: 0 (hours remain) ORIG. ESTIMATE.: 0 PROGRESS NOTES: -=-=(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. -=-=(Psergey - Mon, 18 Jan 2010, 16:23)=-=- Low Level Design modified. --- /tmp/wklog.66.old.23203 2010-01-18 16:23:18.000000000 +0200 +++ /tmp/wklog.66.new.23203 2010-01-18 16:23:18.000000000 +0200 @@ -31,3 +31,15 @@ Question: or perhaps that is not necessarry? </questionable> + +Execution process +~~~~~~~~~~~~~~~~~ +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); + + -=-=(Psergey - Mon, 18 Jan 2010, 16:22)=-=- Low Level Design modified. --- /tmp/wklog.66.old.23076 2010-01-18 16:22:07.000000000 +0200 +++ /tmp/wklog.66.new.23076 2010-01-18 16:22:07.000000000 +0200 @@ -4,3 +4,30 @@ Temporary table index should be created by all fields except result field (TMP_TABLE_PARAM::keyinfo). +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> -=-=(Psergey - Tue, 12 Jan 2010, 18:39)=-=- High-Level Specification modified. --- /tmp/wklog.66.old.31666 2010-01-12 18:39:43.000000000 +0200 +++ /tmp/wklog.66.new.31666 2010-01-12 18:39:43.000000000 +0200 @@ -4,3 +4,99 @@ To check/discuss: To put subquery cache on all levels of subqueries or on highest level only. + + +<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 dont support cases when outer_expr or correlation_references are blobs. + +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. + -=-=(Psergey - Mon, 11 Jan 2010, 13:25)=-=- As of today, there is code that - collects outside references - creates a temporary table with index that would allow for fast lookups. there is no code to - fill the temporary table - make lookups into it Reported zero hours worked. Estimate unchanged. -=-=(Sanja - Fri, 11 Dec 2009, 15:09)=-=- High-Level Specification modified. --- /tmp/wklog.66.old.28164 2009-12-11 15:09:15.000000000 +0200 +++ /tmp/wklog.66.new.28164 2009-12-11 15:09:15.000000000 +0200 @@ -3,4 +3,4 @@ To check/discuss: -Are there sens to put subquery cache on all levels of subqueries of on highest. + To put subquery cache on all levels of subqueries or on highest level only. -=-=(Sanja - Fri, 11 Dec 2009, 15:08)=-=- Low Level Design modified. --- /tmp/wklog.66.old.28072 2009-12-11 15:08:16.000000000 +0200 +++ /tmp/wklog.66.new.28072 2009-12-11 15:08:16.000000000 +0200 @@ -1 +1,6 @@ +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). -=-=(Sanja - Fri, 11 Dec 2009, 15:05)=-=- High-Level Specification modified. --- /tmp/wklog.66.old.27795 2009-12-11 15:05:04.000000000 +0200 +++ /tmp/wklog.66.new.27795 2009-12-11 15:05:04.000000000 +0200 @@ -1 +1,6 @@ +Attach subquery cache to each Item_subquery. Interface should allow to use hash +or temporary table inside. + +To check/discuss: +Are there sens to put subquery cache on all levels of subqueries of on highest. DESCRIPTION: 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: To put subquery cache on all levels of subqueries or on highest level only. <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 dont support cases when outer_expr or correlation_references are blobs. 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: 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

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

18 Jan '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.......: Server-BackLog TASK ID........: 66 (http://askmonty.org/worklog/?tid=66) VERSION........: Server-5.2 STATUS.........: Assigned PRIORITY.......: 60 WORKED HOURS...: 0 ESTIMATE.......: 0 (hours remain) ORIG. ESTIMATE.: 0 PROGRESS NOTES: -=-=(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. -=-=(Psergey - Mon, 18 Jan 2010, 16:23)=-=- Low Level Design modified. --- /tmp/wklog.66.old.23203 2010-01-18 16:23:18.000000000 +0200 +++ /tmp/wklog.66.new.23203 2010-01-18 16:23:18.000000000 +0200 @@ -31,3 +31,15 @@ Question: or perhaps that is not necessarry? </questionable> + +Execution process +~~~~~~~~~~~~~~~~~ +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); + + -=-=(Psergey - Mon, 18 Jan 2010, 16:22)=-=- Low Level Design modified. --- /tmp/wklog.66.old.23076 2010-01-18 16:22:07.000000000 +0200 +++ /tmp/wklog.66.new.23076 2010-01-18 16:22:07.000000000 +0200 @@ -4,3 +4,30 @@ Temporary table index should be created by all fields except result field (TMP_TABLE_PARAM::keyinfo). +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> -=-=(Psergey - Tue, 12 Jan 2010, 18:39)=-=- High-Level Specification modified. --- /tmp/wklog.66.old.31666 2010-01-12 18:39:43.000000000 +0200 +++ /tmp/wklog.66.new.31666 2010-01-12 18:39:43.000000000 +0200 @@ -4,3 +4,99 @@ To check/discuss: To put subquery cache on all levels of subqueries or on highest level only. + + +<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 dont support cases when outer_expr or correlation_references are blobs. + +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. + -=-=(Psergey - Mon, 11 Jan 2010, 13:25)=-=- As of today, there is code that - collects outside references - creates a temporary table with index that would allow for fast lookups. there is no code to - fill the temporary table - make lookups into it Reported zero hours worked. Estimate unchanged. -=-=(Sanja - Fri, 11 Dec 2009, 15:09)=-=- High-Level Specification modified. --- /tmp/wklog.66.old.28164 2009-12-11 15:09:15.000000000 +0200 +++ /tmp/wklog.66.new.28164 2009-12-11 15:09:15.000000000 +0200 @@ -3,4 +3,4 @@ To check/discuss: -Are there sens to put subquery cache on all levels of subqueries of on highest. + To put subquery cache on all levels of subqueries or on highest level only. -=-=(Sanja - Fri, 11 Dec 2009, 15:08)=-=- Low Level Design modified. --- /tmp/wklog.66.old.28072 2009-12-11 15:08:16.000000000 +0200 +++ /tmp/wklog.66.new.28072 2009-12-11 15:08:16.000000000 +0200 @@ -1 +1,6 @@ +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). -=-=(Sanja - Fri, 11 Dec 2009, 15:05)=-=- High-Level Specification modified. --- /tmp/wklog.66.old.27795 2009-12-11 15:05:04.000000000 +0200 +++ /tmp/wklog.66.new.27795 2009-12-11 15:05:04.000000000 +0200 @@ -1 +1,6 @@ +Attach subquery cache to each Item_subquery. Interface should allow to use hash +or temporary table inside. + +To check/discuss: +Are there sens to put subquery cache on all levels of subqueries of on highest. DESCRIPTION: 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: To put subquery cache on all levels of subqueries or on highest level only. <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 dont support cases when outer_expr or correlation_references are blobs. 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: 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 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

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

18 Jan '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.......: Server-BackLog TASK ID........: 66 (http://askmonty.org/worklog/?tid=66) VERSION........: Server-5.2 STATUS.........: Assigned PRIORITY.......: 60 WORKED HOURS...: 0 ESTIMATE.......: 0 (hours remain) ORIG. ESTIMATE.: 0 PROGRESS NOTES: -=-=(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. -=-=(Psergey - Mon, 18 Jan 2010, 16:23)=-=- Low Level Design modified. --- /tmp/wklog.66.old.23203 2010-01-18 16:23:18.000000000 +0200 +++ /tmp/wklog.66.new.23203 2010-01-18 16:23:18.000000000 +0200 @@ -31,3 +31,15 @@ Question: or perhaps that is not necessarry? </questionable> + +Execution process +~~~~~~~~~~~~~~~~~ +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); + + -=-=(Psergey - Mon, 18 Jan 2010, 16:22)=-=- Low Level Design modified. --- /tmp/wklog.66.old.23076 2010-01-18 16:22:07.000000000 +0200 +++ /tmp/wklog.66.new.23076 2010-01-18 16:22:07.000000000 +0200 @@ -4,3 +4,30 @@ Temporary table index should be created by all fields except result field (TMP_TABLE_PARAM::keyinfo). +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> -=-=(Psergey - Tue, 12 Jan 2010, 18:39)=-=- High-Level Specification modified. --- /tmp/wklog.66.old.31666 2010-01-12 18:39:43.000000000 +0200 +++ /tmp/wklog.66.new.31666 2010-01-12 18:39:43.000000000 +0200 @@ -4,3 +4,99 @@ To check/discuss: To put subquery cache on all levels of subqueries or on highest level only. + + +<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 dont support cases when outer_expr or correlation_references are blobs. + +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. + -=-=(Psergey - Mon, 11 Jan 2010, 13:25)=-=- As of today, there is code that - collects outside references - creates a temporary table with index that would allow for fast lookups. there is no code to - fill the temporary table - make lookups into it Reported zero hours worked. Estimate unchanged. -=-=(Sanja - Fri, 11 Dec 2009, 15:09)=-=- High-Level Specification modified. --- /tmp/wklog.66.old.28164 2009-12-11 15:09:15.000000000 +0200 +++ /tmp/wklog.66.new.28164 2009-12-11 15:09:15.000000000 +0200 @@ -3,4 +3,4 @@ To check/discuss: -Are there sens to put subquery cache on all levels of subqueries of on highest. + To put subquery cache on all levels of subqueries or on highest level only. -=-=(Sanja - Fri, 11 Dec 2009, 15:08)=-=- Low Level Design modified. --- /tmp/wklog.66.old.28072 2009-12-11 15:08:16.000000000 +0200 +++ /tmp/wklog.66.new.28072 2009-12-11 15:08:16.000000000 +0200 @@ -1 +1,6 @@ +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). -=-=(Sanja - Fri, 11 Dec 2009, 15:05)=-=- High-Level Specification modified. --- /tmp/wklog.66.old.27795 2009-12-11 15:05:04.000000000 +0200 +++ /tmp/wklog.66.new.27795 2009-12-11 15:05:04.000000000 +0200 @@ -1 +1,6 @@ +Attach subquery cache to each Item_subquery. Interface should allow to use hash +or temporary table inside. + +To check/discuss: +Are there sens to put subquery cache on all levels of subqueries of on highest. DESCRIPTION: 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: To put subquery cache on all levels of subqueries or on highest level only. <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 dont support cases when outer_expr or correlation_references are blobs. 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: 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 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

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

18 Jan '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.......: Server-BackLog TASK ID........: 66 (http://askmonty.org/worklog/?tid=66) VERSION........: Server-5.2 STATUS.........: Assigned PRIORITY.......: 60 WORKED HOURS...: 0 ESTIMATE.......: 0 (hours remain) ORIG. ESTIMATE.: 0 PROGRESS NOTES: -=-=(Psergey - Mon, 18 Jan 2010, 16:23)=-=- Low Level Design modified. --- /tmp/wklog.66.old.23203 2010-01-18 16:23:18.000000000 +0200 +++ /tmp/wklog.66.new.23203 2010-01-18 16:23:18.000000000 +0200 @@ -31,3 +31,15 @@ Question: or perhaps that is not necessarry? </questionable> + +Execution process +~~~~~~~~~~~~~~~~~ +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); + + -=-=(Psergey - Mon, 18 Jan 2010, 16:22)=-=- Low Level Design modified. --- /tmp/wklog.66.old.23076 2010-01-18 16:22:07.000000000 +0200 +++ /tmp/wklog.66.new.23076 2010-01-18 16:22:07.000000000 +0200 @@ -4,3 +4,30 @@ Temporary table index should be created by all fields except result field (TMP_TABLE_PARAM::keyinfo). +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> -=-=(Psergey - Tue, 12 Jan 2010, 18:39)=-=- High-Level Specification modified. --- /tmp/wklog.66.old.31666 2010-01-12 18:39:43.000000000 +0200 +++ /tmp/wklog.66.new.31666 2010-01-12 18:39:43.000000000 +0200 @@ -4,3 +4,99 @@ To check/discuss: To put subquery cache on all levels of subqueries or on highest level only. + + +<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 dont support cases when outer_expr or correlation_references are blobs. + +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. + -=-=(Psergey - Mon, 11 Jan 2010, 13:25)=-=- As of today, there is code that - collects outside references - creates a temporary table with index that would allow for fast lookups. there is no code to - fill the temporary table - make lookups into it Reported zero hours worked. Estimate unchanged. -=-=(Sanja - Fri, 11 Dec 2009, 15:09)=-=- High-Level Specification modified. --- /tmp/wklog.66.old.28164 2009-12-11 15:09:15.000000000 +0200 +++ /tmp/wklog.66.new.28164 2009-12-11 15:09:15.000000000 +0200 @@ -3,4 +3,4 @@ To check/discuss: -Are there sens to put subquery cache on all levels of subqueries of on highest. + To put subquery cache on all levels of subqueries or on highest level only. -=-=(Sanja - Fri, 11 Dec 2009, 15:08)=-=- Low Level Design modified. --- /tmp/wklog.66.old.28072 2009-12-11 15:08:16.000000000 +0200 +++ /tmp/wklog.66.new.28072 2009-12-11 15:08:16.000000000 +0200 @@ -1 +1,6 @@ +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). -=-=(Sanja - Fri, 11 Dec 2009, 15:05)=-=- High-Level Specification modified. --- /tmp/wklog.66.old.27795 2009-12-11 15:05:04.000000000 +0200 +++ /tmp/wklog.66.new.27795 2009-12-11 15:05:04.000000000 +0200 @@ -1 +1,6 @@ +Attach subquery cache to each Item_subquery. Interface should allow to use hash +or temporary table inside. + +To check/discuss: +Are there sens to put subquery cache on all levels of subqueries of on highest. DESCRIPTION: 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: To put subquery cache on all levels of subqueries or on highest level only. <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 dont support cases when outer_expr or correlation_references are blobs. 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: 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 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> Execution process ~~~~~~~~~~~~~~~~~ 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); ESTIMATED WORK TIME ESTIMATED COMPLETION DATE ----------------------------------------------------------------------- WorkLog (v3.5.9)

1 0

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

18 Jan '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.......: Server-BackLog TASK ID........: 66 (http://askmonty.org/worklog/?tid=66) VERSION........: Server-5.2 STATUS.........: Assigned PRIORITY.......: 60 WORKED HOURS...: 0 ESTIMATE.......: 0 (hours remain) ORIG. ESTIMATE.: 0 PROGRESS NOTES: -=-=(Psergey - Mon, 18 Jan 2010, 16:23)=-=- Low Level Design modified. --- /tmp/wklog.66.old.23203 2010-01-18 16:23:18.000000000 +0200 +++ /tmp/wklog.66.new.23203 2010-01-18 16:23:18.000000000 +0200 @@ -31,3 +31,15 @@ Question: or perhaps that is not necessarry? </questionable> + +Execution process +~~~~~~~~~~~~~~~~~ +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); + + -=-=(Psergey - Mon, 18 Jan 2010, 16:22)=-=- Low Level Design modified. --- /tmp/wklog.66.old.23076 2010-01-18 16:22:07.000000000 +0200 +++ /tmp/wklog.66.new.23076 2010-01-18 16:22:07.000000000 +0200 @@ -4,3 +4,30 @@ Temporary table index should be created by all fields except result field (TMP_TABLE_PARAM::keyinfo). +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> -=-=(Psergey - Tue, 12 Jan 2010, 18:39)=-=- High-Level Specification modified. --- /tmp/wklog.66.old.31666 2010-01-12 18:39:43.000000000 +0200 +++ /tmp/wklog.66.new.31666 2010-01-12 18:39:43.000000000 +0200 @@ -4,3 +4,99 @@ To check/discuss: To put subquery cache on all levels of subqueries or on highest level only. + + +<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 dont support cases when outer_expr or correlation_references are blobs. + +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. + -=-=(Psergey - Mon, 11 Jan 2010, 13:25)=-=- As of today, there is code that - collects outside references - creates a temporary table with index that would allow for fast lookups. there is no code to - fill the temporary table - make lookups into it Reported zero hours worked. Estimate unchanged. -=-=(Sanja - Fri, 11 Dec 2009, 15:09)=-=- High-Level Specification modified. --- /tmp/wklog.66.old.28164 2009-12-11 15:09:15.000000000 +0200 +++ /tmp/wklog.66.new.28164 2009-12-11 15:09:15.000000000 +0200 @@ -3,4 +3,4 @@ To check/discuss: -Are there sens to put subquery cache on all levels of subqueries of on highest. + To put subquery cache on all levels of subqueries or on highest level only. -=-=(Sanja - Fri, 11 Dec 2009, 15:08)=-=- Low Level Design modified. --- /tmp/wklog.66.old.28072 2009-12-11 15:08:16.000000000 +0200 +++ /tmp/wklog.66.new.28072 2009-12-11 15:08:16.000000000 +0200 @@ -1 +1,6 @@ +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). -=-=(Sanja - Fri, 11 Dec 2009, 15:05)=-=- High-Level Specification modified. --- /tmp/wklog.66.old.27795 2009-12-11 15:05:04.000000000 +0200 +++ /tmp/wklog.66.new.27795 2009-12-11 15:05:04.000000000 +0200 @@ -1 +1,6 @@ +Attach subquery cache to each Item_subquery. Interface should allow to use hash +or temporary table inside. + +To check/discuss: +Are there sens to put subquery cache on all levels of subqueries of on highest. DESCRIPTION: 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: To put subquery cache on all levels of subqueries or on highest level only. <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 dont support cases when outer_expr or correlation_references are blobs. 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: 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 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> Execution process ~~~~~~~~~~~~~~~~~ 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); ESTIMATED WORK TIME ESTIMATED COMPLETION DATE ----------------------------------------------------------------------- WorkLog (v3.5.9)

1 0

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

18 Jan '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.......: Server-BackLog TASK ID........: 66 (http://askmonty.org/worklog/?tid=66) VERSION........: Server-5.2 STATUS.........: Assigned PRIORITY.......: 60 WORKED HOURS...: 0 ESTIMATE.......: 0 (hours remain) ORIG. ESTIMATE.: 0 PROGRESS NOTES: -=-=(Psergey - Mon, 18 Jan 2010, 16:22)=-=- Low Level Design modified. --- /tmp/wklog.66.old.23076 2010-01-18 16:22:07.000000000 +0200 +++ /tmp/wklog.66.new.23076 2010-01-18 16:22:07.000000000 +0200 @@ -4,3 +4,30 @@ Temporary table index should be created by all fields except result field (TMP_TABLE_PARAM::keyinfo). +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> -=-=(Psergey - Tue, 12 Jan 2010, 18:39)=-=- High-Level Specification modified. --- /tmp/wklog.66.old.31666 2010-01-12 18:39:43.000000000 +0200 +++ /tmp/wklog.66.new.31666 2010-01-12 18:39:43.000000000 +0200 @@ -4,3 +4,99 @@ To check/discuss: To put subquery cache on all levels of subqueries or on highest level only. + + +<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 dont support cases when outer_expr or correlation_references are blobs. + +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. + -=-=(Psergey - Mon, 11 Jan 2010, 13:25)=-=- As of today, there is code that - collects outside references - creates a temporary table with index that would allow for fast lookups. there is no code to - fill the temporary table - make lookups into it Reported zero hours worked. Estimate unchanged. -=-=(Sanja - Fri, 11 Dec 2009, 15:09)=-=- High-Level Specification modified. --- /tmp/wklog.66.old.28164 2009-12-11 15:09:15.000000000 +0200 +++ /tmp/wklog.66.new.28164 2009-12-11 15:09:15.000000000 +0200 @@ -3,4 +3,4 @@ To check/discuss: -Are there sens to put subquery cache on all levels of subqueries of on highest. + To put subquery cache on all levels of subqueries or on highest level only. -=-=(Sanja - Fri, 11 Dec 2009, 15:08)=-=- Low Level Design modified. --- /tmp/wklog.66.old.28072 2009-12-11 15:08:16.000000000 +0200 +++ /tmp/wklog.66.new.28072 2009-12-11 15:08:16.000000000 +0200 @@ -1 +1,6 @@ +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). -=-=(Sanja - Fri, 11 Dec 2009, 15:05)=-=- High-Level Specification modified. --- /tmp/wklog.66.old.27795 2009-12-11 15:05:04.000000000 +0200 +++ /tmp/wklog.66.new.27795 2009-12-11 15:05:04.000000000 +0200 @@ -1 +1,6 @@ +Attach subquery cache to each Item_subquery. Interface should allow to use hash +or temporary table inside. + +To check/discuss: +Are there sens to put subquery cache on all levels of subqueries of on highest. DESCRIPTION: 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: To put subquery cache on all levels of subqueries or on highest level only. <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 dont support cases when outer_expr or correlation_references are blobs. 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: 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 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> ESTIMATED WORK TIME ESTIMATED COMPLETION DATE ----------------------------------------------------------------------- WorkLog (v3.5.9)

1 0