- developers - lists.mariadb.org

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

28 Feb '10

----------------------------------------------------------------------- WORKLOG TASK -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- TASK...........: Subqueries: cost-based choice between Materialization and IN->EXISTS transformation CREATION DATE..: Sun, 28 Feb 2010, 13:45 SUPERVISOR.....: Monty IMPLEMENTOR....: COPIES TO......: Igor, Psergey, Timour CATEGORY.......: Server-RawIdeaBin TASK ID........: 90 (http://askmonty.org/worklog/?tid=90) VERSION........: Server-5.3 STATUS.........: Un-Assigned PRIORITY.......: 60 WORKED HOURS...: 0 ESTIMATE.......: -1 (hours remain) ORIG. ESTIMATE.: 0 PROGRESS NOTES: DESCRIPTION: For uncorrelated IN subqueries that can't be converted to semi-joins it is necessary to make a cost-based choice between IN->EXISTS and Materialization strategies. Both strategies handle two cases: 1. A simple case w/o NULLs handling 2. Handling NULLs. This WL is about making cost-based decision for #1. ESTIMATED WORK TIME ESTIMATED COMPLETION DATE ----------------------------------------------------------------------- WorkLog (v3.5.9)

1 0

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

28 Feb '10

----------------------------------------------------------------------- WORKLOG TASK -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- TASK...........: Subqueries: cost-based choice between Materialization and IN->EXISTS transformation CREATION DATE..: Sun, 28 Feb 2010, 13:45 SUPERVISOR.....: Monty IMPLEMENTOR....: COPIES TO......: Igor, Psergey, Timour CATEGORY.......: Server-RawIdeaBin TASK ID........: 90 (http://askmonty.org/worklog/?tid=90) VERSION........: Server-5.3 STATUS.........: Un-Assigned PRIORITY.......: 60 WORKED HOURS...: 0 ESTIMATE.......: -1 (hours remain) ORIG. ESTIMATE.: 0 PROGRESS NOTES: DESCRIPTION: For uncorrelated IN subqueries that can't be converted to semi-joins it is necessary to make a cost-based choice between IN->EXISTS and Materialization strategies. Both strategies handle two cases: 1. A simple case w/o NULLs handling 2. Handling NULLs. This WL is about making cost-based decision for #1. ESTIMATED WORK TIME ESTIMATED COMPLETION DATE ----------------------------------------------------------------------- WorkLog (v3.5.9)

1 0

[Maria-developers] New (by Knielsen): Update packaging scripts for MariaDB 5.2 (88)
by worklog-noreply＠askmonty.org 27 Feb '10

27 Feb '10

----------------------------------------------------------------------- WORKLOG TASK -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- TASK...........: Update packaging scripts for MariaDB 5.2 CREATION DATE..: Sat, 27 Feb 2010, 16:39 SUPERVISOR.....: Knielsen IMPLEMENTOR....: Knielsen COPIES TO......: CATEGORY.......: Server-RawIdeaBin TASK ID........: 88 (http://askmonty.org/worklog/?tid=88) VERSION........: Server-5.2 STATUS.........: Assigned PRIORITY.......: 60 WORKED HOURS...: 0 ESTIMATE.......: 30 (hours remain) ORIG. ESTIMATE.: 30 PROGRESS NOTES: DESCRIPTION: The packaging scripts need to be updated to work for MariaDB 5.2 Currently, 5.2 package builds fail in Buildbot. The .debs are missing a debian-5.2 subdirectory. The .rpm also need to be checked. Buildbot needs to be updated to do the new upgrade tests (mariadb-5.1 -> mariadb 5.2) ESTIMATED WORK TIME ESTIMATED COMPLETION DATE ----------------------------------------------------------------------- WorkLog (v3.5.9)

1 0

[Maria-developers] Updated (by Knielsen): Enable the use of libstdc++ in MariaDB (63)
by worklog-noreply＠askmonty.org 27 Feb '10

27 Feb '10

----------------------------------------------------------------------- WORKLOG TASK -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- TASK...........: Enable the use of libstdc++ in MariaDB CREATION DATE..: Wed, 11 Nov 2009, 13:19 SUPERVISOR.....: Monty IMPLEMENTOR....: Knielsen COPIES TO......: CATEGORY.......: Server-BackLog TASK ID........: 63 (http://askmonty.org/worklog/?tid=63) VERSION........: Server-5.2 STATUS.........: Assigned PRIORITY.......: 60 WORKED HOURS...: 4 ESTIMATE.......: 10 (hours remain) ORIG. ESTIMATE.: 10 PROGRESS NOTES: -=-=(Knielsen - Sat, 27 Feb 2010, 16:02)=-=- Status updated. --- /tmp/wklog.63.old.30948 2010-02-27 16:02:20.000000000 +0000 +++ /tmp/wklog.63.new.30948 2010-02-27 16:02:20.000000000 +0000 @@ -1 +1 @@ -Un-Assigned +Assigned -=-=(Knielsen - Thu, 14 Jan 2010, 13:46)=-=- Research and updated description Worked 4 hours and estimate 10 hours remain (original estimate increased by 14 hours). -=-=(Knielsen - Thu, 14 Jan 2010, 13:45)=-=- High-Level Specification modified. --- /tmp/wklog.63.old.13967 2010-01-14 11:45:49.000000000 +0000 +++ /tmp/wklog.63.new.13967 2010-01-14 11:45:49.000000000 +0000 @@ -1 +1,37 @@ +I did some investigation into this. + +The simple way to do this is to simply use g++ to link C++ objects. So this +issue is really restricted to GCC compilation where we by default prefer to +link with gcc even for C++ code. So this means building with + + CXX=g++ + +The consequences of doing this for the binaries is the addition of two +additional run-time .so dependencies: libstdc++.so and libgcc_s.so. + +It still needs to be investigated if these additional dependencies are a +problem for binary tarball packages, or if the ABI for those libraries are now +as stable as libc.so. + +The libgcc_s.so is needed as a dependency to support exceptions between +different object files, as they need to use the same code for stack unwinding. +libstdc++.so is of course needed for access to C++ runtime. + +I researched into the possibility to instead link only specific plugins with +g++, and continue to link the rest of the server with gcc. Unfortunately, this +seems really hard to do in a proper way due to the way autotools works. At +configure time, a script ./libtool is created with hardcoded compiler commands +derived from $CC and $CXX. This script is then used to do the actual linking +in Makefiles generated by Automake. I thus did not find a way to change the +linker command on a per-makefile basis, as libtool is global to the project. + +One option would be to use separate configure.in for plugins, but this is +quite an intrusive change. + +My conclusion is that the best way is to start using g++ for linking the +entire server. This is no problem for binaries made for a specific +distribution (Ubuntu, Debian, Centos), where the dependencies are handled by +the package manager. If it is a big problem for binary tarball releases, at +worst we can build multiple binary tarball releases for the different library +versions we need to support. -=-=(Guest - Tue, 12 Jan 2010, 16:26)=-=- Version updated. --- /tmp/wklog.63.old.19522 2010-01-12 16:26:23.000000000 +0200 +++ /tmp/wklog.63.new.19522 2010-01-12 16:26:23.000000000 +0200 @@ -1 +1 @@ -Connector/.NET-5.2 +Server-5.2 -=-=(Guest - Tue, 12 Jan 2010, 16:26)=-=- Category updated. --- /tmp/wklog.63.old.19506 2010-01-12 16:26:15.000000000 +0200 +++ /tmp/wklog.63.new.19506 2010-01-12 16:26:15.000000000 +0200 @@ -1 +1 @@ -Server-RawIdeaBin +Server-BackLog DESCRIPTION: Enable the use of libstdc++ in MariaDB. As time goes on, more and more plugins and external code/library will need linking to libstdc++ for stuff it uses. I have already seen this happen several times, with extra work needed to integrate things properly. It would be nice to have a general solution for this so that it is not necessary to spend time on individual solutions in each case. It also needs to be considered what the impact of this will be for the server in terms of binary compatibility, performance etc. I think it should be mostly ok, except that it might introduce a problem for bintar packages with an external dependency on libstdc++. HIGH-LEVEL SPECIFICATION: I did some investigation into this. The simple way to do this is to simply use g++ to link C++ objects. So this issue is really restricted to GCC compilation where we by default prefer to link with gcc even for C++ code. So this means building with CXX=g++ The consequences of doing this for the binaries is the addition of two additional run-time .so dependencies: libstdc++.so and libgcc_s.so. It still needs to be investigated if these additional dependencies are a problem for binary tarball packages, or if the ABI for those libraries are now as stable as libc.so. The libgcc_s.so is needed as a dependency to support exceptions between different object files, as they need to use the same code for stack unwinding. libstdc++.so is of course needed for access to C++ runtime. I researched into the possibility to instead link only specific plugins with g++, and continue to link the rest of the server with gcc. Unfortunately, this seems really hard to do in a proper way due to the way autotools works. At configure time, a script ./libtool is created with hardcoded compiler commands derived from $CC and $CXX. This script is then used to do the actual linking in Makefiles generated by Automake. I thus did not find a way to change the linker command on a per-makefile basis, as libtool is global to the project. One option would be to use separate configure.in for plugins, but this is quite an intrusive change. My conclusion is that the best way is to start using g++ for linking the entire server. This is no problem for binaries made for a specific distribution (Ubuntu, Debian, Centos), where the dependencies are handled by the package manager. If it is a big problem for binary tarball releases, at worst we can build multiple binary tarball releases for the different library versions we need to support. ESTIMATED WORK TIME ESTIMATED COMPLETION DATE ----------------------------------------------------------------------- WorkLog (v3.5.9)

1 0

[Maria-developers] Updated (by Knielsen): Enable the use of libstdc++ in MariaDB (63)
by worklog-noreply＠askmonty.org 27 Feb '10

27 Feb '10

----------------------------------------------------------------------- WORKLOG TASK -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- TASK...........: Enable the use of libstdc++ in MariaDB CREATION DATE..: Wed, 11 Nov 2009, 13:19 SUPERVISOR.....: Monty IMPLEMENTOR....: Knielsen COPIES TO......: CATEGORY.......: Server-BackLog TASK ID........: 63 (http://askmonty.org/worklog/?tid=63) VERSION........: Server-5.2 STATUS.........: Assigned PRIORITY.......: 60 WORKED HOURS...: 4 ESTIMATE.......: 10 (hours remain) ORIG. ESTIMATE.: 10 PROGRESS NOTES: -=-=(Knielsen - Sat, 27 Feb 2010, 16:02)=-=- Status updated. --- /tmp/wklog.63.old.30948 2010-02-27 16:02:20.000000000 +0000 +++ /tmp/wklog.63.new.30948 2010-02-27 16:02:20.000000000 +0000 @@ -1 +1 @@ -Un-Assigned +Assigned -=-=(Knielsen - Thu, 14 Jan 2010, 13:46)=-=- Research and updated description Worked 4 hours and estimate 10 hours remain (original estimate increased by 14 hours). -=-=(Knielsen - Thu, 14 Jan 2010, 13:45)=-=- High-Level Specification modified. --- /tmp/wklog.63.old.13967 2010-01-14 11:45:49.000000000 +0000 +++ /tmp/wklog.63.new.13967 2010-01-14 11:45:49.000000000 +0000 @@ -1 +1,37 @@ +I did some investigation into this. + +The simple way to do this is to simply use g++ to link C++ objects. So this +issue is really restricted to GCC compilation where we by default prefer to +link with gcc even for C++ code. So this means building with + + CXX=g++ + +The consequences of doing this for the binaries is the addition of two +additional run-time .so dependencies: libstdc++.so and libgcc_s.so. + +It still needs to be investigated if these additional dependencies are a +problem for binary tarball packages, or if the ABI for those libraries are now +as stable as libc.so. + +The libgcc_s.so is needed as a dependency to support exceptions between +different object files, as they need to use the same code for stack unwinding. +libstdc++.so is of course needed for access to C++ runtime. + +I researched into the possibility to instead link only specific plugins with +g++, and continue to link the rest of the server with gcc. Unfortunately, this +seems really hard to do in a proper way due to the way autotools works. At +configure time, a script ./libtool is created with hardcoded compiler commands +derived from $CC and $CXX. This script is then used to do the actual linking +in Makefiles generated by Automake. I thus did not find a way to change the +linker command on a per-makefile basis, as libtool is global to the project. + +One option would be to use separate configure.in for plugins, but this is +quite an intrusive change. + +My conclusion is that the best way is to start using g++ for linking the +entire server. This is no problem for binaries made for a specific +distribution (Ubuntu, Debian, Centos), where the dependencies are handled by +the package manager. If it is a big problem for binary tarball releases, at +worst we can build multiple binary tarball releases for the different library +versions we need to support. -=-=(Guest - Tue, 12 Jan 2010, 16:26)=-=- Version updated. --- /tmp/wklog.63.old.19522 2010-01-12 16:26:23.000000000 +0200 +++ /tmp/wklog.63.new.19522 2010-01-12 16:26:23.000000000 +0200 @@ -1 +1 @@ -Connector/.NET-5.2 +Server-5.2 -=-=(Guest - Tue, 12 Jan 2010, 16:26)=-=- Category updated. --- /tmp/wklog.63.old.19506 2010-01-12 16:26:15.000000000 +0200 +++ /tmp/wklog.63.new.19506 2010-01-12 16:26:15.000000000 +0200 @@ -1 +1 @@ -Server-RawIdeaBin +Server-BackLog DESCRIPTION: Enable the use of libstdc++ in MariaDB. As time goes on, more and more plugins and external code/library will need linking to libstdc++ for stuff it uses. I have already seen this happen several times, with extra work needed to integrate things properly. It would be nice to have a general solution for this so that it is not necessary to spend time on individual solutions in each case. It also needs to be considered what the impact of this will be for the server in terms of binary compatibility, performance etc. I think it should be mostly ok, except that it might introduce a problem for bintar packages with an external dependency on libstdc++. HIGH-LEVEL SPECIFICATION: I did some investigation into this. The simple way to do this is to simply use g++ to link C++ objects. So this issue is really restricted to GCC compilation where we by default prefer to link with gcc even for C++ code. So this means building with CXX=g++ The consequences of doing this for the binaries is the addition of two additional run-time .so dependencies: libstdc++.so and libgcc_s.so. It still needs to be investigated if these additional dependencies are a problem for binary tarball packages, or if the ABI for those libraries are now as stable as libc.so. The libgcc_s.so is needed as a dependency to support exceptions between different object files, as they need to use the same code for stack unwinding. libstdc++.so is of course needed for access to C++ runtime. I researched into the possibility to instead link only specific plugins with g++, and continue to link the rest of the server with gcc. Unfortunately, this seems really hard to do in a proper way due to the way autotools works. At configure time, a script ./libtool is created with hardcoded compiler commands derived from $CC and $CXX. This script is then used to do the actual linking in Makefiles generated by Automake. I thus did not find a way to change the linker command on a per-makefile basis, as libtool is global to the project. One option would be to use separate configure.in for plugins, but this is quite an intrusive change. My conclusion is that the best way is to start using g++ for linking the entire server. This is no problem for binaries made for a specific distribution (Ubuntu, Debian, Centos), where the dependencies are handled by the package manager. If it is a big problem for binary tarball releases, at worst we can build multiple binary tarball releases for the different library versions we need to support. ESTIMATED WORK TIME ESTIMATED COMPLETION DATE ----------------------------------------------------------------------- WorkLog (v3.5.9)

1 0

[Maria-developers] Rev 2765: Change Field_enumerator to enumerate Item_field-s not Field-s. in file:///home/psergey/dev/maria-5.3-subqueries-r7/
by Sergey Petrunya 27 Feb '10

27 Feb '10

At file:///home/psergey/dev/maria-5.3-subqueries-r7/ ------------------------------------------------------------ revno: 2765 revision-id: psergey(a)askmonty.org-20100221063223-h0f7u2low7rtjixc parent: psergey(a)askmonty.org-20100221033618-83dgm2h9ingzmhcc committer: Sergey Petrunya <psergey(a)askmonty.org> branch nick: maria-5.3-subqueries-r7 timestamp: Sun 2010-02-21 08:32:23 +0200 message: Change Field_enumerator to enumerate Item_field-s not Field-s. In Item_ref::fix_fields() do invoke mark_as_dependent() for outside references in all cases (see email for more details) === modified file 'sql/item.cc' --- a/sql/item.cc 2010-02-11 23:59:58 +0000 +++ b/sql/item.cc 2010-02-21 06:32:23 +0000 @@ -1959,7 +1959,7 @@ bool Item_field::enumerate_field_refs_processor(uchar *arg) { Field_enumerator *fe= (Field_enumerator*)arg; - fe->visit_field(field); + fe->visit_field(this); return FALSE; } @@ -5779,6 +5779,35 @@ set_properties(); } +/* + A Field_enumerator-compatible class that invokes mark_as_dependent() for + each field that is a reference to some ancestor of current_select. +*/ +class Dependency_marker: public Field_enumerator +{ +public: + THD *thd; + st_select_lex *current_select; + virtual void visit_field(Item_field *item) + { + // Find which select the field is in. This is achieved by walking up + // the select tree and looking for the table of interest. + st_select_lex *sel; + for (sel= current_select; sel; sel= sel->outer_select()) + { + TABLE_LIST *tbl; + for (tbl= sel->leaf_tables; tbl; tbl= tbl->next_leaf) + { + if (tbl->table == item->field->table) + { + if (sel != current_select) + mark_as_dependent(thd, sel, current_select, item, item); + return; + } + } + } + } +}; /** Resolve the name of a reference to a column reference. @@ -6038,6 +6067,20 @@ last_checked_context->select_lex->nest_level); } } + else + { + ; + /* + It could be that we're referring to something that's in ancestor selects. + We must make an appropriate mark_as_dependent() call for each such + outside reference. + */ + Dependency_marker dep_marker; + dep_marker.current_select= current_sel; + dep_marker.thd= thd; + (*ref)->walk(&Item::enumerate_field_refs_processor, FALSE, + (uchar*)&dep_marker); + } DBUG_ASSERT(*ref); /* === modified file 'sql/item.h' --- a/sql/item.h 2010-02-21 03:36:18 +0000 +++ b/sql/item.h 2010-02-21 06:32:23 +0000 @@ -1134,7 +1134,7 @@ class Field_enumerator { public: - virtual void visit_field(Field *field)= 0; + virtual void visit_field(Item_field *field)= 0; virtual ~Field_enumerator() {}; /* purecov: inspected */ }; === modified file 'sql/item_subselect.cc' --- a/sql/item_subselect.cc 2010-02-21 03:36:18 +0000 +++ b/sql/item_subselect.cc 2010-02-21 06:32:23 +0000 @@ -319,13 +319,13 @@ public: table_map used_tables; /* Collect used_tables here */ st_select_lex *new_parent; /* Select we're in */ - virtual void visit_field(Field *field) + virtual void visit_field(Item_field *item) { //for (TABLE_LIST *tbl= new_parent->leaf_tables; tbl; tbl= tbl->next_local) //{ // if (tbl->table == field->table) // { - used_tables|= field->table->map; + used_tables|= item->field->table->map; // return; // } //} === modified file 'sql/opt_table_elimination.cc' --- a/sql/opt_table_elimination.cc 2010-01-17 14:51:10 +0000 +++ b/sql/opt_table_elimination.cc 2010-02-21 06:32:23 +0000 @@ -922,8 +922,9 @@ Field_dependency_recorder(Dep_analysis_context *ctx_arg): ctx(ctx_arg) {} - void visit_field(Field *field) + void visit_field(Item_field *item) { + Field *field= item->field; Dep_value_table *tbl_dep; if ((tbl_dep= ctx->table_deps[field->table->tablenr])) {

1 2

[Maria-developers] Updated (by Guest): Subquery optimization: Efficient NOT IN execution with NULLs (68)
by worklog-noreply＠askmonty.org 27 Feb '10

27 Feb '10

----------------------------------------------------------------------- WORKLOG TASK -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- TASK...........: Subquery optimization: Efficient NOT IN execution with NULLs CREATION DATE..: Fri, 27 Nov 2009, 13:22 SUPERVISOR.....: Monty IMPLEMENTOR....: Timour COPIES TO......: CATEGORY.......: Server-Sprint TASK ID........: 68 (http://askmonty.org/worklog/?tid=68) VERSION........: Server-9.x STATUS.........: In-Progress PRIORITY.......: 60 WORKED HOURS...: 0 ESTIMATE.......: 0 (hours remain) ORIG. ESTIMATE.: 0 PROGRESS NOTES: -=-=(Guest - Sat, 27 Feb 2010, 10:11)=-=- Status updated. No change. -=-=(Guest - Sat, 27 Feb 2010, 10:11)=-=- Status updated. --- /tmp/wklog.68.old.24229 2010-02-27 10:11:57.000000000 +0000 +++ /tmp/wklog.68.new.24229 2010-02-27 10:11:57.000000000 +0000 @@ -1 +1 @@ -Assigned +In-Progress -=-=(Timour - Mon, 22 Feb 2010, 17:39)=-=- High-Level Specification modified. --- /tmp/wklog.68.old.17116 2010-02-22 17:39:48.000000000 +0200 +++ /tmp/wklog.68.new.17116 2010-02-22 17:39:48.000000000 +0200 @@ -233,6 +233,7 @@ 1. If columns a_j1,...,a_jm do not contain null values in the temporary table at all and v_j1,...,v_jm cannot be null, create for these columns only one index array (and of course do not create any bitmaps for them). +[done] 2. Consider the ratio d(a_i)=N'(a_i)/V(a_i), where N'(a_i) is the number of rows, where a_i is not null and V(a_i) is the number of distinct @@ -264,6 +265,10 @@ 7. If you get a row with nulls in all columns stop filling the temporary table and return UNKNOWN for any tuple <v1,...,vn>. +[This is wrong, because if we don't fill the whole temp table, there may + be some tuple(s) that would match some outer tuple. In such cases, if we + stop filling the temp table, we would miss a TRUE result. Having a partial + match doesn't preclude us from having a complete match]. 8. [timour] Consider that due to materialization, we already have a unique index -=-=(Timour - Tue, 19 Jan 2010, 18:44)=-=- High-Level Specification modified. --- /tmp/wklog.68.old.22569 2010-01-19 18:44:01.000000000 +0200 +++ /tmp/wklog.68.new.22569 2010-01-19 18:44:01.000000000 +0200 @@ -132,11 +132,10 @@ if (nonull_key && ! nonull_key->lookup(outer_ref)) return FALSE - if (nonull_key) - pq.insert(nonull_key) for (i = 1; i <= n; i++) { + if (vkey[i] != nonull_key) vkey[i].lookup(outer_ref) if (! vkey[i].is_eof()) pq.insert(i) @@ -167,7 +166,7 @@ /* There cannot be a complete match, as we already checked for one. */ assert(matching_keys.elements < n) } - else if (cur_min_key == nonull_key) + else if (vkey[cur_min_key] == nonull_key) { /* The non-NULL key has no corresponding NULL index, so we know for @@ -183,8 +182,10 @@ /* Check if all null_keys contain a NULL at row 'min_row'. The procedure internally checks all keys in a special precomputed order. A prior - procedure determines an optimal order and a mapping - idx_no -> idx_order (encoded as an array). + procedure determines an optimal order and a mapping idx_no -> idx_order + (encoded as an array). + + This procedure makes sure not to match the non-NULL column. */ if (test_null_row(null_keys, min_row)) return TRUE @@ -198,6 +199,14 @@ vkey[cur_min_key].next() if (! vkey[cur_min_key].is_eof()) pq.insert(cur_min_key) + else if (vkey[cur_min_key] == nonull_key) + { + /* + If there can't be more matches for the nonull_key, we know for sure + there is no match, since there is no possible NULL match. + */ + return FALSE + } if (pq.is_empty()) { @@ -216,7 +225,6 @@ } - 3. Directions for improvement ======================================================================== -=-=(Timour - Tue, 19 Jan 2010, 18:29)=-=- High-Level Specification modified. --- /tmp/wklog.68.old.21045 2010-01-19 18:29:12.000000000 +0200 +++ /tmp/wklog.68.new.21045 2010-01-19 18:29:12.000000000 +0200 @@ -132,6 +132,8 @@ if (nonull_key && ! nonull_key->lookup(outer_ref)) return FALSE + if (nonull_key) + pq.insert(nonull_key) for (i = 1; i <= n; i++) { -=-=(Guest - Tue, 19 Jan 2010, 18:15)=-=- High-Level Specification modified. --- /tmp/wklog.68.old.19825 2010-01-19 18:15:30.000000000 +0200 +++ /tmp/wklog.68.new.19825 2010-01-19 18:15:30.000000000 +0200 @@ -1,8 +1,16 @@ -This a copy of the initial algorithm proposed by Igor: -====================================================== +Contents +======================================================================== -For each left side tuple (v_1,...,v_n) we have to find the following set -of rowids for the temp table containing N rows as the result of +1. Initial idea as proposed by Igor +2. Algorithm for IN execution with partial matching +3. Directions for improvement + + +1. Initial idea as proposed by Igor +======================================================================== + +For each left side tuple (v_1,...,v_n) we have to find the following +set of rowids for the temp table containing N rows as the result of materialization of the subquery: R= INTERSECT (rowid{a_i=v_i} UNION rowid{a_i is null} where i runs @@ -18,38 +26,198 @@ - it requires minimum memory: not more than N*n bits in total - search of an element in a set is extremely cheap -Taken all above into account I could suggest the following algorithm to -build R: +Taken all above into account I could suggest the following algorithm +to build R: - Using indexes (read about them below) for each column participating in the - intersection, - merge ordered sets rowid{a_i=v_i} in the following manner. + Using indexes (read about them below) for each column participating + in the intersection, merge ordered sets rowid{a_i=v_i} in the + following manner. If a rowid r has been encountered maximum in k sets -rowid{a_i1=v_i1},...,rowid(a_ik=v_ik), + rowid{a_i1=v_i1},...,rowid(a_ik=v_ik), then it has to be checked against all rowid{a_i=v_i} such that i is -not in {i1,...,ik}. + not in {i1,...,ik}. As soon as we fail to find r in one of these sets we discard it. If r has been found in all of them then r belongs to the set R. -Here we use the property (1): any r from rowid{a_i=v_i} UNION rowid{a_i -is null} is either +Here we use the property (1): +any r from rowid{a_i=v_i} UNION rowid{a_i is null} is either belongs to rowid{a_i=v_i} or to rowid{a_i is null}. From this we can -infer that for any r from R -indexes a_i can be uniquely divided into two groups: one contains -indexes a_i where r belongs to -the sets rowid{a_i=v_i}, the other contains indexes a_j such that r -belongs to rowid{a_j is null}. - -Now let's talk how to get elements from rowid{a_i=v_i} in a sorted order -needed for the merge procedure. We could use BTREE indexes for temp -table. But they are rather expensive and -take a lot of memory as the are implemented with RB trees. +infer that for any r from R indexes a_i can be uniquely divided into +two groups: +- one contains indexes a_i where r belongs to the sets rowid{a_i=v_i}, +- the other contains indexes a_j such that r belongs to + rowid{a_j is null}. + +Now let's talk how to get elements from rowid{a_i=v_i} in a sorted +order needed for the merge procedure. We could use BTREE indexes for +temp table. But they are rather expensive and take a lot of memory as +the are implemented with RB trees. I would suggest creating for each column from the temporary table just an array of rowids sorted by the value from column a. Index lookup in such an array is cheap. It's also rather cheap to check that the next rowid refers to a row with a different value in column a. The array can be created on demand. +2. Algorithm for IN execution with partial matching +======================================================================== + +2.1 Below is shown the top-level algorithm to execute an IN predicate +with partial matching. This algorithm is essentially the implementation +of Item_subselect:exec(). + +int lookup_with_null_semantics(outer_ref[], mat_subquery) +{ + if (index_lookup(outer_ref, mat_subquery) + return TRUE + else + { + /* + Check if there is a partial match (UNKNOWN) or no match (NULL). + */ + if (this is the first partial match) + { + vkey[] = build array of value keys for each NULL-able column + of mat_subquery. + nkey[] = build a bitmap NULL index for each column of mat_subquery + that contains NULLs + nonull_key = build a key over all non-NULL columns of mat_subquery + } + if (partial_match(outer_ref, vkey[], nkey[], nonull_key) + return UNKNOWN + else + return FALSE + } +} + +2.2 The implementation of partial matching is as follows + +/* + Assumptions: + - It has already been checked if there is a complete match by a + regular index lookup, and the test failed. + - It has already been checked if there is a complete NULL row, + and if there was we wouldn't call this function. Thus we assume + that there is no complete NULL row. + - Not all vidx_i are empty, but some can be empty. If all were empty, + then the only possibility for a match is a complete NULL row, which + we already checked. + + @param outer_ref - the uter (left) IN argument. + @param vidx[] - array of value keys + Ordered sequences of rowids of the corresponding columns a_i, such + that all rowids in idx_i are the ones where column a_i contains some + value or NULL. Each idx_i is derived dynamically, for each different + left argument of an IN predicate. + @param nidx[] - array of NULL keys + Bitmpas, one per each column, where a bit is set if the corresponding + row has a NULL value for the corresponding column. + @nonull_key - the only key over all columns of the materialized subquery + that do not contain NULLs + + @returns + @retval FALSE if there is no match + @retval TRUE if there is a partial match +*/ + +Boolean partial_match(outer_ref, vkey[], nkey[], nonull_key) +{ + /* Set of the keys (columns) that form a partial match. */ + Set matching_keys = {} + /* A subset of all keys that need to be checked for NULL matches. */ + Set null_keys = {} + Int min_key /* Key that contains the current minimum position. */ + Int min_row /* Current row number of min_key. */ + Int cur_min_key, cur_min_row + PriorityQueue pq + + if (nonull_key && ! nonull_key->lookup(outer_ref)) + return FALSE + + for (i = 1; i <= n; i++) + { + vkey[i].lookup(outer_ref) + if (! vkey[i].is_eof()) + pq.insert(i) + } + /* + Not all value keys are empty, thus we don't have only NULL + keys. If we had, the only possible match is a NULL row, and + we cheked there is no such row, therefore the result is known + to be FALSE. + In fact this algorithm makes sense for at least two non-NULL + columns. + */ + assert(pq.elements > 1) + + (min_key, min_row) = pq.pop() + matching_keys.add(min_key) + vkey[min_key].next() + if (! vkey[min_key].is_eof()) + pq.insert(min_key) + + while (TRUE) + { + (cur_min_key, cur_min_row) = pq.pop() + + if (cur_min_row == min_row) + { + matching_keys.add(cur_min_key) + /* There cannot be a complete match, as we already checked for one. */ + assert(matching_keys.elements < n) + } + else if (cur_min_key == nonull_key) + { + /* + The non-NULL key has no corresponding NULL index, so we know for + sure that the row 'min_row' is not a match. + */ + (min_key, min_row) = (cur_min_key, cur_min_row) + matching_keys = {min_key} + } + else + { + assert(cur_min_row > min_row) /* Follows from the use of PQ. */ + null_keys = set_difference(all keys vkey[], matching_keys) + /* + Check if all null_keys contain a NULL at row 'min_row'. The procedure + internally checks all keys in a special precomputed order. A prior + procedure determines an optimal order and a mapping + idx_no -> idx_order (encoded as an array). + */ + if (test_null_row(null_keys, min_row)) + return TRUE + else + { + (min_key, min_row) = (cur_min_key, cur_min_row) + matching_keys = {min_key} + } + } + + vkey[cur_min_key].next() + if (! vkey[cur_min_key].is_eof()) + pq.insert(cur_min_key) + + if (pq.is_empty()) + { + /* Check the last row of the last column in PQ for NULL matches. */ + null_keys = set_difference(all keys vkey[], matching_keys) + if (test_null_row(null_keys, min_row)) + return TRUE + else + return FALSE + } + } + + /* We should never get here. */ + assert(FALSE) + return FALSE +} + + + +3. Directions for improvement +======================================================================== + Other consideration that may be taken into account: 1. If columns a_j1,...,a_jm do not contain null values in the temporary -=-=(Timour - Sun, 06 Dec 2009, 14:36)=-=- High-Level Specification modified. --- /tmp/wklog.68.old.12919 2009-12-06 14:36:18.000000000 +0200 +++ /tmp/wklog.68.new.12919 2009-12-06 14:36:18.000000000 +0200 @@ -87,3 +87,8 @@ 7. If you get a row with nulls in all columns stop filling the temporary table and return UNKNOWN for any tuple <v1,...,vn>. +8. [timour] + Consider that due to materialization, we already have a unique index +on all columns <a_1,..., a_n>. We can use the first key part of this index +over column a_1, instead of the index rowid{a_i=v_i}. Thus we can avoid +creating the index rowid{a_i=v_i}. -=-=(Timour - Fri, 04 Dec 2009, 14:04)=-=- High-Level Specification modified. --- /tmp/wklog.68.old.16724 2009-12-04 14:04:28.000000000 +0200 +++ /tmp/wklog.68.new.16724 2009-12-04 14:04:28.000000000 +0200 @@ -10,7 +10,8 @@ Bear in mind the following specifics of this intersection: (1) For each i: rowid{a_i=v_i} and rowid{a_i is null} are disjoint - (2) For each i: rowid{a_i is null} is the same for each tuple + (2) For each i: rowid{a_i is null} is the same for each tuple, + that is, this set is independent of the left-side tuples. Due to (2) it makes sense to build rowid{a_i is null} only once. A good representation for such sets would be bitmaps: -=-=(Timour - Fri, 04 Dec 2009, 11:27)=-=- Version updated. --- /tmp/wklog.68.old.5257 2009-12-04 11:27:11.000000000 +0200 +++ /tmp/wklog.68.new.5257 2009-12-04 11:27:11.000000000 +0200 @@ -1 +1 @@ -Benchmarks-3.0 +Server-9.x -=-=(Timour - Fri, 04 Dec 2009, 11:27)=-=- Category updated. --- /tmp/wklog.68.old.5242 2009-12-04 11:27:02.000000000 +0200 +++ /tmp/wklog.68.new.5242 2009-12-04 11:27:02.000000000 +0200 @@ -1 +1 @@ -Server-RawIdeaBin +Server-Sprint ------------------------------------------------------------ -=-=(View All Progress Notes, 13 total)=-=- http://askmonty.org/worklog/index.pl?tid=68&nolimit=1 DESCRIPTION: The goal of this task is to implement efficient execution of NOT IN subquery predicates of the form: <oe_1,...,oe_n> NOT IN <non_correlated subquery> when either some oe_i, or some subqury result column contains NULLs. The problem with such predicates is that it is possible to use index lookups only when neither argument of the predicate contains NULLs. If some argument contains a NULL, then due to NULL semantics, it plays the role of a wildcard. If we were to use regular index lookups, then we would get 'no match' for some outer tuple (thus the predicate evaluates to FALSE), while the SQL semantics means 'partial match', and the predicate should evaluate to NULL. This task implements an efficient algorithm to compute such 'parial matches', where a NULL matches any value. HIGH-LEVEL SPECIFICATION: Contents ======================================================================== 1. Initial idea as proposed by Igor 2. Algorithm for IN execution with partial matching 3. Directions for improvement 1. Initial idea as proposed by Igor ======================================================================== For each left side tuple (v_1,...,v_n) we have to find the following set of rowids for the temp table containing N rows as the result of materialization of the subquery: R= INTERSECT (rowid{a_i=v_i} UNION rowid{a_i is null} where i runs trough all indexes from [1..n] such that v_i is not null. Bear in mind the following specifics of this intersection: (1) For each i: rowid{a_i=v_i} and rowid{a_i is null} are disjoint (2) For each i: rowid{a_i is null} is the same for each tuple, that is, this set is independent of the left-side tuples. Due to (2) it makes sense to build rowid{a_i is null} only once. A good representation for such sets would be bitmaps: - it requires minimum memory: not more than N*n bits in total - search of an element in a set is extremely cheap Taken all above into account I could suggest the following algorithm to build R: Using indexes (read about them below) for each column participating in the intersection, merge ordered sets rowid{a_i=v_i} in the following manner. If a rowid r has been encountered maximum in k sets rowid{a_i1=v_i1},...,rowid(a_ik=v_ik), then it has to be checked against all rowid{a_i=v_i} such that i is not in {i1,...,ik}. As soon as we fail to find r in one of these sets we discard it. If r has been found in all of them then r belongs to the set R. Here we use the property (1): any r from rowid{a_i=v_i} UNION rowid{a_i is null} is either belongs to rowid{a_i=v_i} or to rowid{a_i is null}. From this we can infer that for any r from R indexes a_i can be uniquely divided into two groups: - one contains indexes a_i where r belongs to the sets rowid{a_i=v_i}, - the other contains indexes a_j such that r belongs to rowid{a_j is null}. Now let's talk how to get elements from rowid{a_i=v_i} in a sorted order needed for the merge procedure. We could use BTREE indexes for temp table. But they are rather expensive and take a lot of memory as the are implemented with RB trees. I would suggest creating for each column from the temporary table just an array of rowids sorted by the value from column a. Index lookup in such an array is cheap. It's also rather cheap to check that the next rowid refers to a row with a different value in column a. The array can be created on demand. 2. Algorithm for IN execution with partial matching ======================================================================== 2.1 Below is shown the top-level algorithm to execute an IN predicate with partial matching. This algorithm is essentially the implementation of Item_subselect:exec(). int lookup_with_null_semantics(outer_ref[], mat_subquery) { if (index_lookup(outer_ref, mat_subquery) return TRUE else { /* Check if there is a partial match (UNKNOWN) or no match (NULL). */ if (this is the first partial match) { vkey[] = build array of value keys for each NULL-able column of mat_subquery. nkey[] = build a bitmap NULL index for each column of mat_subquery that contains NULLs nonull_key = build a key over all non-NULL columns of mat_subquery } if (partial_match(outer_ref, vkey[], nkey[], nonull_key) return UNKNOWN else return FALSE } } 2.2 The implementation of partial matching is as follows /* Assumptions: - It has already been checked if there is a complete match by a regular index lookup, and the test failed. - It has already been checked if there is a complete NULL row, and if there was we wouldn't call this function. Thus we assume that there is no complete NULL row. - Not all vidx_i are empty, but some can be empty. If all were empty, then the only possibility for a match is a complete NULL row, which we already checked. @param outer_ref - the uter (left) IN argument. @param vidx[] - array of value keys Ordered sequences of rowids of the corresponding columns a_i, such that all rowids in idx_i are the ones where column a_i contains some value or NULL. Each idx_i is derived dynamically, for each different left argument of an IN predicate. @param nidx[] - array of NULL keys Bitmpas, one per each column, where a bit is set if the corresponding row has a NULL value for the corresponding column. @nonull_key - the only key over all columns of the materialized subquery that do not contain NULLs @returns @retval FALSE if there is no match @retval TRUE if there is a partial match */ Boolean partial_match(outer_ref, vkey[], nkey[], nonull_key) { /* Set of the keys (columns) that form a partial match. */ Set matching_keys = {} /* A subset of all keys that need to be checked for NULL matches. */ Set null_keys = {} Int min_key /* Key that contains the current minimum position. */ Int min_row /* Current row number of min_key. */ Int cur_min_key, cur_min_row PriorityQueue pq if (nonull_key && ! nonull_key->lookup(outer_ref)) return FALSE for (i = 1; i <= n; i++) { if (vkey[i] != nonull_key) vkey[i].lookup(outer_ref) if (! vkey[i].is_eof()) pq.insert(i) } /* Not all value keys are empty, thus we don't have only NULL keys. If we had, the only possible match is a NULL row, and we cheked there is no such row, therefore the result is known to be FALSE. In fact this algorithm makes sense for at least two non-NULL columns. */ assert(pq.elements > 1) (min_key, min_row) = pq.pop() matching_keys.add(min_key) vkey[min_key].next() if (! vkey[min_key].is_eof()) pq.insert(min_key) while (TRUE) { (cur_min_key, cur_min_row) = pq.pop() if (cur_min_row == min_row) { matching_keys.add(cur_min_key) /* There cannot be a complete match, as we already checked for one. */ assert(matching_keys.elements < n) } else if (vkey[cur_min_key] == nonull_key) { /* The non-NULL key has no corresponding NULL index, so we know for sure that the row 'min_row' is not a match. */ (min_key, min_row) = (cur_min_key, cur_min_row) matching_keys = {min_key} } else { assert(cur_min_row > min_row) /* Follows from the use of PQ. */ null_keys = set_difference(all keys vkey[], matching_keys) /* Check if all null_keys contain a NULL at row 'min_row'. The procedure internally checks all keys in a special precomputed order. A prior procedure determines an optimal order and a mapping idx_no -> idx_order (encoded as an array). This procedure makes sure not to match the non-NULL column. */ if (test_null_row(null_keys, min_row)) return TRUE else { (min_key, min_row) = (cur_min_key, cur_min_row) matching_keys = {min_key} } } vkey[cur_min_key].next() if (! vkey[cur_min_key].is_eof()) pq.insert(cur_min_key) else if (vkey[cur_min_key] == nonull_key) { /* If there can't be more matches for the nonull_key, we know for sure there is no match, since there is no possible NULL match. */ return FALSE } if (pq.is_empty()) { /* Check the last row of the last column in PQ for NULL matches. */ null_keys = set_difference(all keys vkey[], matching_keys) if (test_null_row(null_keys, min_row)) return TRUE else return FALSE } } /* We should never get here. */ assert(FALSE) return FALSE } 3. Directions for improvement ======================================================================== Other consideration that may be taken into account: 1. If columns a_j1,...,a_jm do not contain null values in the temporary table at all and v_j1,...,v_jm cannot be null, create for these columns only one index array (and of course do not create any bitmaps for them). [done] 2. Consider the ratio d(a_i)=N'(a_i)/V(a_i), where N'(a_i) is the number of rows, where a_i is not null and V(a_i) is the number of distinct values for a_i excluding nulls. If d(a_i) is close to N'(a_i) then do not create any index array: check whether there is a match running through the records that have been filtered in. Anyway if d(a_i) is close to N'(a_i) then the intersection with rowid{a_i=v_i} will not reduce the number of remaining rowids significantly. In other words is V(a_i) exceeds some threshold there is no sense to create an index for a_i. If additionally N-N'(a_i) is small do not create a bitmap for this column either. 3. If for a column a_i d(a_i) is not close to N'(a_i), but N-N'(a_i) is small a sorted array of rowids from the set rowid{a_i is null} can be used instead of a bitmap. 4. We always have a match if R0= INTERSECT rowid{a_i is null} is not empty. Here i runs through all indexes from [1..n] such that v_i is not null. For a given subset of columns this fact has to be checked only once. It can be easily done with bitmap intersection. 5. If v1,...,vn never can be a null, then indexes (sorted arrays) can be created only for rows with nulls. 6. If v1,...,vn never can be a null and number of rows with nulls is small do not create indexes and do not create bitmaps. 7. If you get a row with nulls in all columns stop filling the temporary table and return UNKNOWN for any tuple <v1,...,vn>. [This is wrong, because if we don't fill the whole temp table, there may be some tuple(s) that would match some outer tuple. In such cases, if we stop filling the temp table, we would miss a TRUE result. Having a partial match doesn't preclude us from having a complete match]. 8. [timour] Consider that due to materialization, we already have a unique index on all columns <a_1,..., a_n>. We can use the first key part of this index over column a_1, instead of the index rowid{a_i=v_i}. Thus we can avoid creating the index rowid{a_i=v_i}. ESTIMATED WORK TIME ESTIMATED COMPLETION DATE ----------------------------------------------------------------------- WorkLog (v3.5.9)

1 0

[Maria-developers] Updated (by Guest): Subquery optimization: Efficient NOT IN execution with NULLs (68)
by worklog-noreply＠askmonty.org 27 Feb '10

27 Feb '10

----------------------------------------------------------------------- WORKLOG TASK -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- TASK...........: Subquery optimization: Efficient NOT IN execution with NULLs CREATION DATE..: Fri, 27 Nov 2009, 13:22 SUPERVISOR.....: Monty IMPLEMENTOR....: Timour COPIES TO......: CATEGORY.......: Server-Sprint TASK ID........: 68 (http://askmonty.org/worklog/?tid=68) VERSION........: Server-9.x STATUS.........: In-Progress PRIORITY.......: 60 WORKED HOURS...: 0 ESTIMATE.......: 0 (hours remain) ORIG. ESTIMATE.: 0 PROGRESS NOTES: -=-=(Guest - Sat, 27 Feb 2010, 10:11)=-=- Status updated. No change. -=-=(Guest - Sat, 27 Feb 2010, 10:11)=-=- Status updated. --- /tmp/wklog.68.old.24229 2010-02-27 10:11:57.000000000 +0000 +++ /tmp/wklog.68.new.24229 2010-02-27 10:11:57.000000000 +0000 @@ -1 +1 @@ -Assigned +In-Progress -=-=(Timour - Mon, 22 Feb 2010, 17:39)=-=- High-Level Specification modified. --- /tmp/wklog.68.old.17116 2010-02-22 17:39:48.000000000 +0200 +++ /tmp/wklog.68.new.17116 2010-02-22 17:39:48.000000000 +0200 @@ -233,6 +233,7 @@ 1. If columns a_j1,...,a_jm do not contain null values in the temporary table at all and v_j1,...,v_jm cannot be null, create for these columns only one index array (and of course do not create any bitmaps for them). +[done] 2. Consider the ratio d(a_i)=N'(a_i)/V(a_i), where N'(a_i) is the number of rows, where a_i is not null and V(a_i) is the number of distinct @@ -264,6 +265,10 @@ 7. If you get a row with nulls in all columns stop filling the temporary table and return UNKNOWN for any tuple <v1,...,vn>. +[This is wrong, because if we don't fill the whole temp table, there may + be some tuple(s) that would match some outer tuple. In such cases, if we + stop filling the temp table, we would miss a TRUE result. Having a partial + match doesn't preclude us from having a complete match]. 8. [timour] Consider that due to materialization, we already have a unique index -=-=(Timour - Tue, 19 Jan 2010, 18:44)=-=- High-Level Specification modified. --- /tmp/wklog.68.old.22569 2010-01-19 18:44:01.000000000 +0200 +++ /tmp/wklog.68.new.22569 2010-01-19 18:44:01.000000000 +0200 @@ -132,11 +132,10 @@ if (nonull_key && ! nonull_key->lookup(outer_ref)) return FALSE - if (nonull_key) - pq.insert(nonull_key) for (i = 1; i <= n; i++) { + if (vkey[i] != nonull_key) vkey[i].lookup(outer_ref) if (! vkey[i].is_eof()) pq.insert(i) @@ -167,7 +166,7 @@ /* There cannot be a complete match, as we already checked for one. */ assert(matching_keys.elements < n) } - else if (cur_min_key == nonull_key) + else if (vkey[cur_min_key] == nonull_key) { /* The non-NULL key has no corresponding NULL index, so we know for @@ -183,8 +182,10 @@ /* Check if all null_keys contain a NULL at row 'min_row'. The procedure internally checks all keys in a special precomputed order. A prior - procedure determines an optimal order and a mapping - idx_no -> idx_order (encoded as an array). + procedure determines an optimal order and a mapping idx_no -> idx_order + (encoded as an array). + + This procedure makes sure not to match the non-NULL column. */ if (test_null_row(null_keys, min_row)) return TRUE @@ -198,6 +199,14 @@ vkey[cur_min_key].next() if (! vkey[cur_min_key].is_eof()) pq.insert(cur_min_key) + else if (vkey[cur_min_key] == nonull_key) + { + /* + If there can't be more matches for the nonull_key, we know for sure + there is no match, since there is no possible NULL match. + */ + return FALSE + } if (pq.is_empty()) { @@ -216,7 +225,6 @@ } - 3. Directions for improvement ======================================================================== -=-=(Timour - Tue, 19 Jan 2010, 18:29)=-=- High-Level Specification modified. --- /tmp/wklog.68.old.21045 2010-01-19 18:29:12.000000000 +0200 +++ /tmp/wklog.68.new.21045 2010-01-19 18:29:12.000000000 +0200 @@ -132,6 +132,8 @@ if (nonull_key && ! nonull_key->lookup(outer_ref)) return FALSE + if (nonull_key) + pq.insert(nonull_key) for (i = 1; i <= n; i++) { -=-=(Guest - Tue, 19 Jan 2010, 18:15)=-=- High-Level Specification modified. --- /tmp/wklog.68.old.19825 2010-01-19 18:15:30.000000000 +0200 +++ /tmp/wklog.68.new.19825 2010-01-19 18:15:30.000000000 +0200 @@ -1,8 +1,16 @@ -This a copy of the initial algorithm proposed by Igor: -====================================================== +Contents +======================================================================== -For each left side tuple (v_1,...,v_n) we have to find the following set -of rowids for the temp table containing N rows as the result of +1. Initial idea as proposed by Igor +2. Algorithm for IN execution with partial matching +3. Directions for improvement + + +1. Initial idea as proposed by Igor +======================================================================== + +For each left side tuple (v_1,...,v_n) we have to find the following +set of rowids for the temp table containing N rows as the result of materialization of the subquery: R= INTERSECT (rowid{a_i=v_i} UNION rowid{a_i is null} where i runs @@ -18,38 +26,198 @@ - it requires minimum memory: not more than N*n bits in total - search of an element in a set is extremely cheap -Taken all above into account I could suggest the following algorithm to -build R: +Taken all above into account I could suggest the following algorithm +to build R: - Using indexes (read about them below) for each column participating in the - intersection, - merge ordered sets rowid{a_i=v_i} in the following manner. + Using indexes (read about them below) for each column participating + in the intersection, merge ordered sets rowid{a_i=v_i} in the + following manner. If a rowid r has been encountered maximum in k sets -rowid{a_i1=v_i1},...,rowid(a_ik=v_ik), + rowid{a_i1=v_i1},...,rowid(a_ik=v_ik), then it has to be checked against all rowid{a_i=v_i} such that i is -not in {i1,...,ik}. + not in {i1,...,ik}. As soon as we fail to find r in one of these sets we discard it. If r has been found in all of them then r belongs to the set R. -Here we use the property (1): any r from rowid{a_i=v_i} UNION rowid{a_i -is null} is either +Here we use the property (1): +any r from rowid{a_i=v_i} UNION rowid{a_i is null} is either belongs to rowid{a_i=v_i} or to rowid{a_i is null}. From this we can -infer that for any r from R -indexes a_i can be uniquely divided into two groups: one contains -indexes a_i where r belongs to -the sets rowid{a_i=v_i}, the other contains indexes a_j such that r -belongs to rowid{a_j is null}. - -Now let's talk how to get elements from rowid{a_i=v_i} in a sorted order -needed for the merge procedure. We could use BTREE indexes for temp -table. But they are rather expensive and -take a lot of memory as the are implemented with RB trees. +infer that for any r from R indexes a_i can be uniquely divided into +two groups: +- one contains indexes a_i where r belongs to the sets rowid{a_i=v_i}, +- the other contains indexes a_j such that r belongs to + rowid{a_j is null}. + +Now let's talk how to get elements from rowid{a_i=v_i} in a sorted +order needed for the merge procedure. We could use BTREE indexes for +temp table. But they are rather expensive and take a lot of memory as +the are implemented with RB trees. I would suggest creating for each column from the temporary table just an array of rowids sorted by the value from column a. Index lookup in such an array is cheap. It's also rather cheap to check that the next rowid refers to a row with a different value in column a. The array can be created on demand. +2. Algorithm for IN execution with partial matching +======================================================================== + +2.1 Below is shown the top-level algorithm to execute an IN predicate +with partial matching. This algorithm is essentially the implementation +of Item_subselect:exec(). + +int lookup_with_null_semantics(outer_ref[], mat_subquery) +{ + if (index_lookup(outer_ref, mat_subquery) + return TRUE + else + { + /* + Check if there is a partial match (UNKNOWN) or no match (NULL). + */ + if (this is the first partial match) + { + vkey[] = build array of value keys for each NULL-able column + of mat_subquery. + nkey[] = build a bitmap NULL index for each column of mat_subquery + that contains NULLs + nonull_key = build a key over all non-NULL columns of mat_subquery + } + if (partial_match(outer_ref, vkey[], nkey[], nonull_key) + return UNKNOWN + else + return FALSE + } +} + +2.2 The implementation of partial matching is as follows + +/* + Assumptions: + - It has already been checked if there is a complete match by a + regular index lookup, and the test failed. + - It has already been checked if there is a complete NULL row, + and if there was we wouldn't call this function. Thus we assume + that there is no complete NULL row. + - Not all vidx_i are empty, but some can be empty. If all were empty, + then the only possibility for a match is a complete NULL row, which + we already checked. + + @param outer_ref - the uter (left) IN argument. + @param vidx[] - array of value keys + Ordered sequences of rowids of the corresponding columns a_i, such + that all rowids in idx_i are the ones where column a_i contains some + value or NULL. Each idx_i is derived dynamically, for each different + left argument of an IN predicate. + @param nidx[] - array of NULL keys + Bitmpas, one per each column, where a bit is set if the corresponding + row has a NULL value for the corresponding column. + @nonull_key - the only key over all columns of the materialized subquery + that do not contain NULLs + + @returns + @retval FALSE if there is no match + @retval TRUE if there is a partial match +*/ + +Boolean partial_match(outer_ref, vkey[], nkey[], nonull_key) +{ + /* Set of the keys (columns) that form a partial match. */ + Set matching_keys = {} + /* A subset of all keys that need to be checked for NULL matches. */ + Set null_keys = {} + Int min_key /* Key that contains the current minimum position. */ + Int min_row /* Current row number of min_key. */ + Int cur_min_key, cur_min_row + PriorityQueue pq + + if (nonull_key && ! nonull_key->lookup(outer_ref)) + return FALSE + + for (i = 1; i <= n; i++) + { + vkey[i].lookup(outer_ref) + if (! vkey[i].is_eof()) + pq.insert(i) + } + /* + Not all value keys are empty, thus we don't have only NULL + keys. If we had, the only possible match is a NULL row, and + we cheked there is no such row, therefore the result is known + to be FALSE. + In fact this algorithm makes sense for at least two non-NULL + columns. + */ + assert(pq.elements > 1) + + (min_key, min_row) = pq.pop() + matching_keys.add(min_key) + vkey[min_key].next() + if (! vkey[min_key].is_eof()) + pq.insert(min_key) + + while (TRUE) + { + (cur_min_key, cur_min_row) = pq.pop() + + if (cur_min_row == min_row) + { + matching_keys.add(cur_min_key) + /* There cannot be a complete match, as we already checked for one. */ + assert(matching_keys.elements < n) + } + else if (cur_min_key == nonull_key) + { + /* + The non-NULL key has no corresponding NULL index, so we know for + sure that the row 'min_row' is not a match. + */ + (min_key, min_row) = (cur_min_key, cur_min_row) + matching_keys = {min_key} + } + else + { + assert(cur_min_row > min_row) /* Follows from the use of PQ. */ + null_keys = set_difference(all keys vkey[], matching_keys) + /* + Check if all null_keys contain a NULL at row 'min_row'. The procedure + internally checks all keys in a special precomputed order. A prior + procedure determines an optimal order and a mapping + idx_no -> idx_order (encoded as an array). + */ + if (test_null_row(null_keys, min_row)) + return TRUE + else + { + (min_key, min_row) = (cur_min_key, cur_min_row) + matching_keys = {min_key} + } + } + + vkey[cur_min_key].next() + if (! vkey[cur_min_key].is_eof()) + pq.insert(cur_min_key) + + if (pq.is_empty()) + { + /* Check the last row of the last column in PQ for NULL matches. */ + null_keys = set_difference(all keys vkey[], matching_keys) + if (test_null_row(null_keys, min_row)) + return TRUE + else + return FALSE + } + } + + /* We should never get here. */ + assert(FALSE) + return FALSE +} + + + +3. Directions for improvement +======================================================================== + Other consideration that may be taken into account: 1. If columns a_j1,...,a_jm do not contain null values in the temporary -=-=(Timour - Sun, 06 Dec 2009, 14:36)=-=- High-Level Specification modified. --- /tmp/wklog.68.old.12919 2009-12-06 14:36:18.000000000 +0200 +++ /tmp/wklog.68.new.12919 2009-12-06 14:36:18.000000000 +0200 @@ -87,3 +87,8 @@ 7. If you get a row with nulls in all columns stop filling the temporary table and return UNKNOWN for any tuple <v1,...,vn>. +8. [timour] + Consider that due to materialization, we already have a unique index +on all columns <a_1,..., a_n>. We can use the first key part of this index +over column a_1, instead of the index rowid{a_i=v_i}. Thus we can avoid +creating the index rowid{a_i=v_i}. -=-=(Timour - Fri, 04 Dec 2009, 14:04)=-=- High-Level Specification modified. --- /tmp/wklog.68.old.16724 2009-12-04 14:04:28.000000000 +0200 +++ /tmp/wklog.68.new.16724 2009-12-04 14:04:28.000000000 +0200 @@ -10,7 +10,8 @@ Bear in mind the following specifics of this intersection: (1) For each i: rowid{a_i=v_i} and rowid{a_i is null} are disjoint - (2) For each i: rowid{a_i is null} is the same for each tuple + (2) For each i: rowid{a_i is null} is the same for each tuple, + that is, this set is independent of the left-side tuples. Due to (2) it makes sense to build rowid{a_i is null} only once. A good representation for such sets would be bitmaps: -=-=(Timour - Fri, 04 Dec 2009, 11:27)=-=- Version updated. --- /tmp/wklog.68.old.5257 2009-12-04 11:27:11.000000000 +0200 +++ /tmp/wklog.68.new.5257 2009-12-04 11:27:11.000000000 +0200 @@ -1 +1 @@ -Benchmarks-3.0 +Server-9.x -=-=(Timour - Fri, 04 Dec 2009, 11:27)=-=- Category updated. --- /tmp/wklog.68.old.5242 2009-12-04 11:27:02.000000000 +0200 +++ /tmp/wklog.68.new.5242 2009-12-04 11:27:02.000000000 +0200 @@ -1 +1 @@ -Server-RawIdeaBin +Server-Sprint ------------------------------------------------------------ -=-=(View All Progress Notes, 13 total)=-=- http://askmonty.org/worklog/index.pl?tid=68&nolimit=1 DESCRIPTION: The goal of this task is to implement efficient execution of NOT IN subquery predicates of the form: <oe_1,...,oe_n> NOT IN <non_correlated subquery> when either some oe_i, or some subqury result column contains NULLs. The problem with such predicates is that it is possible to use index lookups only when neither argument of the predicate contains NULLs. If some argument contains a NULL, then due to NULL semantics, it plays the role of a wildcard. If we were to use regular index lookups, then we would get 'no match' for some outer tuple (thus the predicate evaluates to FALSE), while the SQL semantics means 'partial match', and the predicate should evaluate to NULL. This task implements an efficient algorithm to compute such 'parial matches', where a NULL matches any value. HIGH-LEVEL SPECIFICATION: Contents ======================================================================== 1. Initial idea as proposed by Igor 2. Algorithm for IN execution with partial matching 3. Directions for improvement 1. Initial idea as proposed by Igor ======================================================================== For each left side tuple (v_1,...,v_n) we have to find the following set of rowids for the temp table containing N rows as the result of materialization of the subquery: R= INTERSECT (rowid{a_i=v_i} UNION rowid{a_i is null} where i runs trough all indexes from [1..n] such that v_i is not null. Bear in mind the following specifics of this intersection: (1) For each i: rowid{a_i=v_i} and rowid{a_i is null} are disjoint (2) For each i: rowid{a_i is null} is the same for each tuple, that is, this set is independent of the left-side tuples. Due to (2) it makes sense to build rowid{a_i is null} only once. A good representation for such sets would be bitmaps: - it requires minimum memory: not more than N*n bits in total - search of an element in a set is extremely cheap Taken all above into account I could suggest the following algorithm to build R: Using indexes (read about them below) for each column participating in the intersection, merge ordered sets rowid{a_i=v_i} in the following manner. If a rowid r has been encountered maximum in k sets rowid{a_i1=v_i1},...,rowid(a_ik=v_ik), then it has to be checked against all rowid{a_i=v_i} such that i is not in {i1,...,ik}. As soon as we fail to find r in one of these sets we discard it. If r has been found in all of them then r belongs to the set R. Here we use the property (1): any r from rowid{a_i=v_i} UNION rowid{a_i is null} is either belongs to rowid{a_i=v_i} or to rowid{a_i is null}. From this we can infer that for any r from R indexes a_i can be uniquely divided into two groups: - one contains indexes a_i where r belongs to the sets rowid{a_i=v_i}, - the other contains indexes a_j such that r belongs to rowid{a_j is null}. Now let's talk how to get elements from rowid{a_i=v_i} in a sorted order needed for the merge procedure. We could use BTREE indexes for temp table. But they are rather expensive and take a lot of memory as the are implemented with RB trees. I would suggest creating for each column from the temporary table just an array of rowids sorted by the value from column a. Index lookup in such an array is cheap. It's also rather cheap to check that the next rowid refers to a row with a different value in column a. The array can be created on demand. 2. Algorithm for IN execution with partial matching ======================================================================== 2.1 Below is shown the top-level algorithm to execute an IN predicate with partial matching. This algorithm is essentially the implementation of Item_subselect:exec(). int lookup_with_null_semantics(outer_ref[], mat_subquery) { if (index_lookup(outer_ref, mat_subquery) return TRUE else { /* Check if there is a partial match (UNKNOWN) or no match (NULL). */ if (this is the first partial match) { vkey[] = build array of value keys for each NULL-able column of mat_subquery. nkey[] = build a bitmap NULL index for each column of mat_subquery that contains NULLs nonull_key = build a key over all non-NULL columns of mat_subquery } if (partial_match(outer_ref, vkey[], nkey[], nonull_key) return UNKNOWN else return FALSE } } 2.2 The implementation of partial matching is as follows /* Assumptions: - It has already been checked if there is a complete match by a regular index lookup, and the test failed. - It has already been checked if there is a complete NULL row, and if there was we wouldn't call this function. Thus we assume that there is no complete NULL row. - Not all vidx_i are empty, but some can be empty. If all were empty, then the only possibility for a match is a complete NULL row, which we already checked. @param outer_ref - the uter (left) IN argument. @param vidx[] - array of value keys Ordered sequences of rowids of the corresponding columns a_i, such that all rowids in idx_i are the ones where column a_i contains some value or NULL. Each idx_i is derived dynamically, for each different left argument of an IN predicate. @param nidx[] - array of NULL keys Bitmpas, one per each column, where a bit is set if the corresponding row has a NULL value for the corresponding column. @nonull_key - the only key over all columns of the materialized subquery that do not contain NULLs @returns @retval FALSE if there is no match @retval TRUE if there is a partial match */ Boolean partial_match(outer_ref, vkey[], nkey[], nonull_key) { /* Set of the keys (columns) that form a partial match. */ Set matching_keys = {} /* A subset of all keys that need to be checked for NULL matches. */ Set null_keys = {} Int min_key /* Key that contains the current minimum position. */ Int min_row /* Current row number of min_key. */ Int cur_min_key, cur_min_row PriorityQueue pq if (nonull_key && ! nonull_key->lookup(outer_ref)) return FALSE for (i = 1; i <= n; i++) { if (vkey[i] != nonull_key) vkey[i].lookup(outer_ref) if (! vkey[i].is_eof()) pq.insert(i) } /* Not all value keys are empty, thus we don't have only NULL keys. If we had, the only possible match is a NULL row, and we cheked there is no such row, therefore the result is known to be FALSE. In fact this algorithm makes sense for at least two non-NULL columns. */ assert(pq.elements > 1) (min_key, min_row) = pq.pop() matching_keys.add(min_key) vkey[min_key].next() if (! vkey[min_key].is_eof()) pq.insert(min_key) while (TRUE) { (cur_min_key, cur_min_row) = pq.pop() if (cur_min_row == min_row) { matching_keys.add(cur_min_key) /* There cannot be a complete match, as we already checked for one. */ assert(matching_keys.elements < n) } else if (vkey[cur_min_key] == nonull_key) { /* The non-NULL key has no corresponding NULL index, so we know for sure that the row 'min_row' is not a match. */ (min_key, min_row) = (cur_min_key, cur_min_row) matching_keys = {min_key} } else { assert(cur_min_row > min_row) /* Follows from the use of PQ. */ null_keys = set_difference(all keys vkey[], matching_keys) /* Check if all null_keys contain a NULL at row 'min_row'. The procedure internally checks all keys in a special precomputed order. A prior procedure determines an optimal order and a mapping idx_no -> idx_order (encoded as an array). This procedure makes sure not to match the non-NULL column. */ if (test_null_row(null_keys, min_row)) return TRUE else { (min_key, min_row) = (cur_min_key, cur_min_row) matching_keys = {min_key} } } vkey[cur_min_key].next() if (! vkey[cur_min_key].is_eof()) pq.insert(cur_min_key) else if (vkey[cur_min_key] == nonull_key) { /* If there can't be more matches for the nonull_key, we know for sure there is no match, since there is no possible NULL match. */ return FALSE } if (pq.is_empty()) { /* Check the last row of the last column in PQ for NULL matches. */ null_keys = set_difference(all keys vkey[], matching_keys) if (test_null_row(null_keys, min_row)) return TRUE else return FALSE } } /* We should never get here. */ assert(FALSE) return FALSE } 3. Directions for improvement ======================================================================== Other consideration that may be taken into account: 1. If columns a_j1,...,a_jm do not contain null values in the temporary table at all and v_j1,...,v_jm cannot be null, create for these columns only one index array (and of course do not create any bitmaps for them). [done] 2. Consider the ratio d(a_i)=N'(a_i)/V(a_i), where N'(a_i) is the number of rows, where a_i is not null and V(a_i) is the number of distinct values for a_i excluding nulls. If d(a_i) is close to N'(a_i) then do not create any index array: check whether there is a match running through the records that have been filtered in. Anyway if d(a_i) is close to N'(a_i) then the intersection with rowid{a_i=v_i} will not reduce the number of remaining rowids significantly. In other words is V(a_i) exceeds some threshold there is no sense to create an index for a_i. If additionally N-N'(a_i) is small do not create a bitmap for this column either. 3. If for a column a_i d(a_i) is not close to N'(a_i), but N-N'(a_i) is small a sorted array of rowids from the set rowid{a_i is null} can be used instead of a bitmap. 4. We always have a match if R0= INTERSECT rowid{a_i is null} is not empty. Here i runs through all indexes from [1..n] such that v_i is not null. For a given subset of columns this fact has to be checked only once. It can be easily done with bitmap intersection. 5. If v1,...,vn never can be a null, then indexes (sorted arrays) can be created only for rows with nulls. 6. If v1,...,vn never can be a null and number of rows with nulls is small do not create indexes and do not create bitmaps. 7. If you get a row with nulls in all columns stop filling the temporary table and return UNKNOWN for any tuple <v1,...,vn>. [This is wrong, because if we don't fill the whole temp table, there may be some tuple(s) that would match some outer tuple. In such cases, if we stop filling the temp table, we would miss a TRUE result. Having a partial match doesn't preclude us from having a complete match]. 8. [timour] Consider that due to materialization, we already have a unique index on all columns <a_1,..., a_n>. We can use the first key part of this index over column a_1, instead of the index rowid{a_i=v_i}. Thus we can avoid creating the index rowid{a_i=v_i}. ESTIMATED WORK TIME ESTIMATED COMPLETION DATE ----------------------------------------------------------------------- WorkLog (v3.5.9)

1 0

[Maria-developers] Updated (by Guest): Subquery optimization: Efficient NOT IN execution with NULLs (68)
by worklog-noreply＠askmonty.org 27 Feb '10

27 Feb '10

----------------------------------------------------------------------- WORKLOG TASK -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- TASK...........: Subquery optimization: Efficient NOT IN execution with NULLs CREATION DATE..: Fri, 27 Nov 2009, 13:22 SUPERVISOR.....: Monty IMPLEMENTOR....: Timour COPIES TO......: CATEGORY.......: Server-Sprint TASK ID........: 68 (http://askmonty.org/worklog/?tid=68) VERSION........: Server-9.x STATUS.........: In-Progress PRIORITY.......: 60 WORKED HOURS...: 0 ESTIMATE.......: 0 (hours remain) ORIG. ESTIMATE.: 0 PROGRESS NOTES: -=-=(Guest - Sat, 27 Feb 2010, 10:11)=-=- Status updated. --- /tmp/wklog.68.old.24229 2010-02-27 10:11:57.000000000 +0000 +++ /tmp/wklog.68.new.24229 2010-02-27 10:11:57.000000000 +0000 @@ -1 +1 @@ -Assigned +In-Progress -=-=(Timour - Mon, 22 Feb 2010, 17:39)=-=- High-Level Specification modified. --- /tmp/wklog.68.old.17116 2010-02-22 17:39:48.000000000 +0200 +++ /tmp/wklog.68.new.17116 2010-02-22 17:39:48.000000000 +0200 @@ -233,6 +233,7 @@ 1. If columns a_j1,...,a_jm do not contain null values in the temporary table at all and v_j1,...,v_jm cannot be null, create for these columns only one index array (and of course do not create any bitmaps for them). +[done] 2. Consider the ratio d(a_i)=N'(a_i)/V(a_i), where N'(a_i) is the number of rows, where a_i is not null and V(a_i) is the number of distinct @@ -264,6 +265,10 @@ 7. If you get a row with nulls in all columns stop filling the temporary table and return UNKNOWN for any tuple <v1,...,vn>. +[This is wrong, because if we don't fill the whole temp table, there may + be some tuple(s) that would match some outer tuple. In such cases, if we + stop filling the temp table, we would miss a TRUE result. Having a partial + match doesn't preclude us from having a complete match]. 8. [timour] Consider that due to materialization, we already have a unique index -=-=(Timour - Tue, 19 Jan 2010, 18:44)=-=- High-Level Specification modified. --- /tmp/wklog.68.old.22569 2010-01-19 18:44:01.000000000 +0200 +++ /tmp/wklog.68.new.22569 2010-01-19 18:44:01.000000000 +0200 @@ -132,11 +132,10 @@ if (nonull_key && ! nonull_key->lookup(outer_ref)) return FALSE - if (nonull_key) - pq.insert(nonull_key) for (i = 1; i <= n; i++) { + if (vkey[i] != nonull_key) vkey[i].lookup(outer_ref) if (! vkey[i].is_eof()) pq.insert(i) @@ -167,7 +166,7 @@ /* There cannot be a complete match, as we already checked for one. */ assert(matching_keys.elements < n) } - else if (cur_min_key == nonull_key) + else if (vkey[cur_min_key] == nonull_key) { /* The non-NULL key has no corresponding NULL index, so we know for @@ -183,8 +182,10 @@ /* Check if all null_keys contain a NULL at row 'min_row'. The procedure internally checks all keys in a special precomputed order. A prior - procedure determines an optimal order and a mapping - idx_no -> idx_order (encoded as an array). + procedure determines an optimal order and a mapping idx_no -> idx_order + (encoded as an array). + + This procedure makes sure not to match the non-NULL column. */ if (test_null_row(null_keys, min_row)) return TRUE @@ -198,6 +199,14 @@ vkey[cur_min_key].next() if (! vkey[cur_min_key].is_eof()) pq.insert(cur_min_key) + else if (vkey[cur_min_key] == nonull_key) + { + /* + If there can't be more matches for the nonull_key, we know for sure + there is no match, since there is no possible NULL match. + */ + return FALSE + } if (pq.is_empty()) { @@ -216,7 +225,6 @@ } - 3. Directions for improvement ======================================================================== -=-=(Timour - Tue, 19 Jan 2010, 18:29)=-=- High-Level Specification modified. --- /tmp/wklog.68.old.21045 2010-01-19 18:29:12.000000000 +0200 +++ /tmp/wklog.68.new.21045 2010-01-19 18:29:12.000000000 +0200 @@ -132,6 +132,8 @@ if (nonull_key && ! nonull_key->lookup(outer_ref)) return FALSE + if (nonull_key) + pq.insert(nonull_key) for (i = 1; i <= n; i++) { -=-=(Guest - Tue, 19 Jan 2010, 18:15)=-=- High-Level Specification modified. --- /tmp/wklog.68.old.19825 2010-01-19 18:15:30.000000000 +0200 +++ /tmp/wklog.68.new.19825 2010-01-19 18:15:30.000000000 +0200 @@ -1,8 +1,16 @@ -This a copy of the initial algorithm proposed by Igor: -====================================================== +Contents +======================================================================== -For each left side tuple (v_1,...,v_n) we have to find the following set -of rowids for the temp table containing N rows as the result of +1. Initial idea as proposed by Igor +2. Algorithm for IN execution with partial matching +3. Directions for improvement + + +1. Initial idea as proposed by Igor +======================================================================== + +For each left side tuple (v_1,...,v_n) we have to find the following +set of rowids for the temp table containing N rows as the result of materialization of the subquery: R= INTERSECT (rowid{a_i=v_i} UNION rowid{a_i is null} where i runs @@ -18,38 +26,198 @@ - it requires minimum memory: not more than N*n bits in total - search of an element in a set is extremely cheap -Taken all above into account I could suggest the following algorithm to -build R: +Taken all above into account I could suggest the following algorithm +to build R: - Using indexes (read about them below) for each column participating in the - intersection, - merge ordered sets rowid{a_i=v_i} in the following manner. + Using indexes (read about them below) for each column participating + in the intersection, merge ordered sets rowid{a_i=v_i} in the + following manner. If a rowid r has been encountered maximum in k sets -rowid{a_i1=v_i1},...,rowid(a_ik=v_ik), + rowid{a_i1=v_i1},...,rowid(a_ik=v_ik), then it has to be checked against all rowid{a_i=v_i} such that i is -not in {i1,...,ik}. + not in {i1,...,ik}. As soon as we fail to find r in one of these sets we discard it. If r has been found in all of them then r belongs to the set R. -Here we use the property (1): any r from rowid{a_i=v_i} UNION rowid{a_i -is null} is either +Here we use the property (1): +any r from rowid{a_i=v_i} UNION rowid{a_i is null} is either belongs to rowid{a_i=v_i} or to rowid{a_i is null}. From this we can -infer that for any r from R -indexes a_i can be uniquely divided into two groups: one contains -indexes a_i where r belongs to -the sets rowid{a_i=v_i}, the other contains indexes a_j such that r -belongs to rowid{a_j is null}. - -Now let's talk how to get elements from rowid{a_i=v_i} in a sorted order -needed for the merge procedure. We could use BTREE indexes for temp -table. But they are rather expensive and -take a lot of memory as the are implemented with RB trees. +infer that for any r from R indexes a_i can be uniquely divided into +two groups: +- one contains indexes a_i where r belongs to the sets rowid{a_i=v_i}, +- the other contains indexes a_j such that r belongs to + rowid{a_j is null}. + +Now let's talk how to get elements from rowid{a_i=v_i} in a sorted +order needed for the merge procedure. We could use BTREE indexes for +temp table. But they are rather expensive and take a lot of memory as +the are implemented with RB trees. I would suggest creating for each column from the temporary table just an array of rowids sorted by the value from column a. Index lookup in such an array is cheap. It's also rather cheap to check that the next rowid refers to a row with a different value in column a. The array can be created on demand. +2. Algorithm for IN execution with partial matching +======================================================================== + +2.1 Below is shown the top-level algorithm to execute an IN predicate +with partial matching. This algorithm is essentially the implementation +of Item_subselect:exec(). + +int lookup_with_null_semantics(outer_ref[], mat_subquery) +{ + if (index_lookup(outer_ref, mat_subquery) + return TRUE + else + { + /* + Check if there is a partial match (UNKNOWN) or no match (NULL). + */ + if (this is the first partial match) + { + vkey[] = build array of value keys for each NULL-able column + of mat_subquery. + nkey[] = build a bitmap NULL index for each column of mat_subquery + that contains NULLs + nonull_key = build a key over all non-NULL columns of mat_subquery + } + if (partial_match(outer_ref, vkey[], nkey[], nonull_key) + return UNKNOWN + else + return FALSE + } +} + +2.2 The implementation of partial matching is as follows + +/* + Assumptions: + - It has already been checked if there is a complete match by a + regular index lookup, and the test failed. + - It has already been checked if there is a complete NULL row, + and if there was we wouldn't call this function. Thus we assume + that there is no complete NULL row. + - Not all vidx_i are empty, but some can be empty. If all were empty, + then the only possibility for a match is a complete NULL row, which + we already checked. + + @param outer_ref - the uter (left) IN argument. + @param vidx[] - array of value keys + Ordered sequences of rowids of the corresponding columns a_i, such + that all rowids in idx_i are the ones where column a_i contains some + value or NULL. Each idx_i is derived dynamically, for each different + left argument of an IN predicate. + @param nidx[] - array of NULL keys + Bitmpas, one per each column, where a bit is set if the corresponding + row has a NULL value for the corresponding column. + @nonull_key - the only key over all columns of the materialized subquery + that do not contain NULLs + + @returns + @retval FALSE if there is no match + @retval TRUE if there is a partial match +*/ + +Boolean partial_match(outer_ref, vkey[], nkey[], nonull_key) +{ + /* Set of the keys (columns) that form a partial match. */ + Set matching_keys = {} + /* A subset of all keys that need to be checked for NULL matches. */ + Set null_keys = {} + Int min_key /* Key that contains the current minimum position. */ + Int min_row /* Current row number of min_key. */ + Int cur_min_key, cur_min_row + PriorityQueue pq + + if (nonull_key && ! nonull_key->lookup(outer_ref)) + return FALSE + + for (i = 1; i <= n; i++) + { + vkey[i].lookup(outer_ref) + if (! vkey[i].is_eof()) + pq.insert(i) + } + /* + Not all value keys are empty, thus we don't have only NULL + keys. If we had, the only possible match is a NULL row, and + we cheked there is no such row, therefore the result is known + to be FALSE. + In fact this algorithm makes sense for at least two non-NULL + columns. + */ + assert(pq.elements > 1) + + (min_key, min_row) = pq.pop() + matching_keys.add(min_key) + vkey[min_key].next() + if (! vkey[min_key].is_eof()) + pq.insert(min_key) + + while (TRUE) + { + (cur_min_key, cur_min_row) = pq.pop() + + if (cur_min_row == min_row) + { + matching_keys.add(cur_min_key) + /* There cannot be a complete match, as we already checked for one. */ + assert(matching_keys.elements < n) + } + else if (cur_min_key == nonull_key) + { + /* + The non-NULL key has no corresponding NULL index, so we know for + sure that the row 'min_row' is not a match. + */ + (min_key, min_row) = (cur_min_key, cur_min_row) + matching_keys = {min_key} + } + else + { + assert(cur_min_row > min_row) /* Follows from the use of PQ. */ + null_keys = set_difference(all keys vkey[], matching_keys) + /* + Check if all null_keys contain a NULL at row 'min_row'. The procedure + internally checks all keys in a special precomputed order. A prior + procedure determines an optimal order and a mapping + idx_no -> idx_order (encoded as an array). + */ + if (test_null_row(null_keys, min_row)) + return TRUE + else + { + (min_key, min_row) = (cur_min_key, cur_min_row) + matching_keys = {min_key} + } + } + + vkey[cur_min_key].next() + if (! vkey[cur_min_key].is_eof()) + pq.insert(cur_min_key) + + if (pq.is_empty()) + { + /* Check the last row of the last column in PQ for NULL matches. */ + null_keys = set_difference(all keys vkey[], matching_keys) + if (test_null_row(null_keys, min_row)) + return TRUE + else + return FALSE + } + } + + /* We should never get here. */ + assert(FALSE) + return FALSE +} + + + +3. Directions for improvement +======================================================================== + Other consideration that may be taken into account: 1. If columns a_j1,...,a_jm do not contain null values in the temporary -=-=(Timour - Sun, 06 Dec 2009, 14:36)=-=- High-Level Specification modified. --- /tmp/wklog.68.old.12919 2009-12-06 14:36:18.000000000 +0200 +++ /tmp/wklog.68.new.12919 2009-12-06 14:36:18.000000000 +0200 @@ -87,3 +87,8 @@ 7. If you get a row with nulls in all columns stop filling the temporary table and return UNKNOWN for any tuple <v1,...,vn>. +8. [timour] + Consider that due to materialization, we already have a unique index +on all columns <a_1,..., a_n>. We can use the first key part of this index +over column a_1, instead of the index rowid{a_i=v_i}. Thus we can avoid +creating the index rowid{a_i=v_i}. -=-=(Timour - Fri, 04 Dec 2009, 14:04)=-=- High-Level Specification modified. --- /tmp/wklog.68.old.16724 2009-12-04 14:04:28.000000000 +0200 +++ /tmp/wklog.68.new.16724 2009-12-04 14:04:28.000000000 +0200 @@ -10,7 +10,8 @@ Bear in mind the following specifics of this intersection: (1) For each i: rowid{a_i=v_i} and rowid{a_i is null} are disjoint - (2) For each i: rowid{a_i is null} is the same for each tuple + (2) For each i: rowid{a_i is null} is the same for each tuple, + that is, this set is independent of the left-side tuples. Due to (2) it makes sense to build rowid{a_i is null} only once. A good representation for such sets would be bitmaps: -=-=(Timour - Fri, 04 Dec 2009, 11:27)=-=- Version updated. --- /tmp/wklog.68.old.5257 2009-12-04 11:27:11.000000000 +0200 +++ /tmp/wklog.68.new.5257 2009-12-04 11:27:11.000000000 +0200 @@ -1 +1 @@ -Benchmarks-3.0 +Server-9.x -=-=(Timour - Fri, 04 Dec 2009, 11:27)=-=- Category updated. --- /tmp/wklog.68.old.5242 2009-12-04 11:27:02.000000000 +0200 +++ /tmp/wklog.68.new.5242 2009-12-04 11:27:02.000000000 +0200 @@ -1 +1 @@ -Server-RawIdeaBin +Server-Sprint -=-=(Timour - Fri, 04 Dec 2009, 11:27)=-=- Status updated. --- /tmp/wklog.68.old.5242 2009-12-04 11:27:02.000000000 +0200 +++ /tmp/wklog.68.new.5242 2009-12-04 11:27:02.000000000 +0200 @@ -1 +1 @@ -Un-Assigned +Assigned ------------------------------------------------------------ -=-=(View All Progress Notes, 12 total)=-=- http://askmonty.org/worklog/index.pl?tid=68&nolimit=1 DESCRIPTION: The goal of this task is to implement efficient execution of NOT IN subquery predicates of the form: <oe_1,...,oe_n> NOT IN <non_correlated subquery> when either some oe_i, or some subqury result column contains NULLs. The problem with such predicates is that it is possible to use index lookups only when neither argument of the predicate contains NULLs. If some argument contains a NULL, then due to NULL semantics, it plays the role of a wildcard. If we were to use regular index lookups, then we would get 'no match' for some outer tuple (thus the predicate evaluates to FALSE), while the SQL semantics means 'partial match', and the predicate should evaluate to NULL. This task implements an efficient algorithm to compute such 'parial matches', where a NULL matches any value. HIGH-LEVEL SPECIFICATION: Contents ======================================================================== 1. Initial idea as proposed by Igor 2. Algorithm for IN execution with partial matching 3. Directions for improvement 1. Initial idea as proposed by Igor ======================================================================== For each left side tuple (v_1,...,v_n) we have to find the following set of rowids for the temp table containing N rows as the result of materialization of the subquery: R= INTERSECT (rowid{a_i=v_i} UNION rowid{a_i is null} where i runs trough all indexes from [1..n] such that v_i is not null. Bear in mind the following specifics of this intersection: (1) For each i: rowid{a_i=v_i} and rowid{a_i is null} are disjoint (2) For each i: rowid{a_i is null} is the same for each tuple, that is, this set is independent of the left-side tuples. Due to (2) it makes sense to build rowid{a_i is null} only once. A good representation for such sets would be bitmaps: - it requires minimum memory: not more than N*n bits in total - search of an element in a set is extremely cheap Taken all above into account I could suggest the following algorithm to build R: Using indexes (read about them below) for each column participating in the intersection, merge ordered sets rowid{a_i=v_i} in the following manner. If a rowid r has been encountered maximum in k sets rowid{a_i1=v_i1},...,rowid(a_ik=v_ik), then it has to be checked against all rowid{a_i=v_i} such that i is not in {i1,...,ik}. As soon as we fail to find r in one of these sets we discard it. If r has been found in all of them then r belongs to the set R. Here we use the property (1): any r from rowid{a_i=v_i} UNION rowid{a_i is null} is either belongs to rowid{a_i=v_i} or to rowid{a_i is null}. From this we can infer that for any r from R indexes a_i can be uniquely divided into two groups: - one contains indexes a_i where r belongs to the sets rowid{a_i=v_i}, - the other contains indexes a_j such that r belongs to rowid{a_j is null}. Now let's talk how to get elements from rowid{a_i=v_i} in a sorted order needed for the merge procedure. We could use BTREE indexes for temp table. But they are rather expensive and take a lot of memory as the are implemented with RB trees. I would suggest creating for each column from the temporary table just an array of rowids sorted by the value from column a. Index lookup in such an array is cheap. It's also rather cheap to check that the next rowid refers to a row with a different value in column a. The array can be created on demand. 2. Algorithm for IN execution with partial matching ======================================================================== 2.1 Below is shown the top-level algorithm to execute an IN predicate with partial matching. This algorithm is essentially the implementation of Item_subselect:exec(). int lookup_with_null_semantics(outer_ref[], mat_subquery) { if (index_lookup(outer_ref, mat_subquery) return TRUE else { /* Check if there is a partial match (UNKNOWN) or no match (NULL). */ if (this is the first partial match) { vkey[] = build array of value keys for each NULL-able column of mat_subquery. nkey[] = build a bitmap NULL index for each column of mat_subquery that contains NULLs nonull_key = build a key over all non-NULL columns of mat_subquery } if (partial_match(outer_ref, vkey[], nkey[], nonull_key) return UNKNOWN else return FALSE } } 2.2 The implementation of partial matching is as follows /* Assumptions: - It has already been checked if there is a complete match by a regular index lookup, and the test failed. - It has already been checked if there is a complete NULL row, and if there was we wouldn't call this function. Thus we assume that there is no complete NULL row. - Not all vidx_i are empty, but some can be empty. If all were empty, then the only possibility for a match is a complete NULL row, which we already checked. @param outer_ref - the uter (left) IN argument. @param vidx[] - array of value keys Ordered sequences of rowids of the corresponding columns a_i, such that all rowids in idx_i are the ones where column a_i contains some value or NULL. Each idx_i is derived dynamically, for each different left argument of an IN predicate. @param nidx[] - array of NULL keys Bitmpas, one per each column, where a bit is set if the corresponding row has a NULL value for the corresponding column. @nonull_key - the only key over all columns of the materialized subquery that do not contain NULLs @returns @retval FALSE if there is no match @retval TRUE if there is a partial match */ Boolean partial_match(outer_ref, vkey[], nkey[], nonull_key) { /* Set of the keys (columns) that form a partial match. */ Set matching_keys = {} /* A subset of all keys that need to be checked for NULL matches. */ Set null_keys = {} Int min_key /* Key that contains the current minimum position. */ Int min_row /* Current row number of min_key. */ Int cur_min_key, cur_min_row PriorityQueue pq if (nonull_key && ! nonull_key->lookup(outer_ref)) return FALSE for (i = 1; i <= n; i++) { if (vkey[i] != nonull_key) vkey[i].lookup(outer_ref) if (! vkey[i].is_eof()) pq.insert(i) } /* Not all value keys are empty, thus we don't have only NULL keys. If we had, the only possible match is a NULL row, and we cheked there is no such row, therefore the result is known to be FALSE. In fact this algorithm makes sense for at least two non-NULL columns. */ assert(pq.elements > 1) (min_key, min_row) = pq.pop() matching_keys.add(min_key) vkey[min_key].next() if (! vkey[min_key].is_eof()) pq.insert(min_key) while (TRUE) { (cur_min_key, cur_min_row) = pq.pop() if (cur_min_row == min_row) { matching_keys.add(cur_min_key) /* There cannot be a complete match, as we already checked for one. */ assert(matching_keys.elements < n) } else if (vkey[cur_min_key] == nonull_key) { /* The non-NULL key has no corresponding NULL index, so we know for sure that the row 'min_row' is not a match. */ (min_key, min_row) = (cur_min_key, cur_min_row) matching_keys = {min_key} } else { assert(cur_min_row > min_row) /* Follows from the use of PQ. */ null_keys = set_difference(all keys vkey[], matching_keys) /* Check if all null_keys contain a NULL at row 'min_row'. The procedure internally checks all keys in a special precomputed order. A prior procedure determines an optimal order and a mapping idx_no -> idx_order (encoded as an array). This procedure makes sure not to match the non-NULL column. */ if (test_null_row(null_keys, min_row)) return TRUE else { (min_key, min_row) = (cur_min_key, cur_min_row) matching_keys = {min_key} } } vkey[cur_min_key].next() if (! vkey[cur_min_key].is_eof()) pq.insert(cur_min_key) else if (vkey[cur_min_key] == nonull_key) { /* If there can't be more matches for the nonull_key, we know for sure there is no match, since there is no possible NULL match. */ return FALSE } if (pq.is_empty()) { /* Check the last row of the last column in PQ for NULL matches. */ null_keys = set_difference(all keys vkey[], matching_keys) if (test_null_row(null_keys, min_row)) return TRUE else return FALSE } } /* We should never get here. */ assert(FALSE) return FALSE } 3. Directions for improvement ======================================================================== Other consideration that may be taken into account: 1. If columns a_j1,...,a_jm do not contain null values in the temporary table at all and v_j1,...,v_jm cannot be null, create for these columns only one index array (and of course do not create any bitmaps for them). [done] 2. Consider the ratio d(a_i)=N'(a_i)/V(a_i), where N'(a_i) is the number of rows, where a_i is not null and V(a_i) is the number of distinct values for a_i excluding nulls. If d(a_i) is close to N'(a_i) then do not create any index array: check whether there is a match running through the records that have been filtered in. Anyway if d(a_i) is close to N'(a_i) then the intersection with rowid{a_i=v_i} will not reduce the number of remaining rowids significantly. In other words is V(a_i) exceeds some threshold there is no sense to create an index for a_i. If additionally N-N'(a_i) is small do not create a bitmap for this column either. 3. If for a column a_i d(a_i) is not close to N'(a_i), but N-N'(a_i) is small a sorted array of rowids from the set rowid{a_i is null} can be used instead of a bitmap. 4. We always have a match if R0= INTERSECT rowid{a_i is null} is not empty. Here i runs through all indexes from [1..n] such that v_i is not null. For a given subset of columns this fact has to be checked only once. It can be easily done with bitmap intersection. 5. If v1,...,vn never can be a null, then indexes (sorted arrays) can be created only for rows with nulls. 6. If v1,...,vn never can be a null and number of rows with nulls is small do not create indexes and do not create bitmaps. 7. If you get a row with nulls in all columns stop filling the temporary table and return UNKNOWN for any tuple <v1,...,vn>. [This is wrong, because if we don't fill the whole temp table, there may be some tuple(s) that would match some outer tuple. In such cases, if we stop filling the temp table, we would miss a TRUE result. Having a partial match doesn't preclude us from having a complete match]. 8. [timour] Consider that due to materialization, we already have a unique index on all columns <a_1,..., a_n>. We can use the first key part of this index over column a_1, instead of the index rowid{a_i=v_i}. Thus we can avoid creating the index rowid{a_i=v_i}. ESTIMATED WORK TIME ESTIMATED COMPLETION DATE ----------------------------------------------------------------------- WorkLog (v3.5.9)

1 0

[Maria-developers] Updated (by Guest): Subquery optimization: Efficient NOT IN execution with NULLs (68)
by worklog-noreply＠askmonty.org 27 Feb '10

27 Feb '10

----------------------------------------------------------------------- WORKLOG TASK -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- TASK...........: Subquery optimization: Efficient NOT IN execution with NULLs CREATION DATE..: Fri, 27 Nov 2009, 13:22 SUPERVISOR.....: Monty IMPLEMENTOR....: Timour COPIES TO......: CATEGORY.......: Server-Sprint TASK ID........: 68 (http://askmonty.org/worklog/?tid=68) VERSION........: Server-9.x STATUS.........: In-Progress PRIORITY.......: 60 WORKED HOURS...: 0 ESTIMATE.......: 0 (hours remain) ORIG. ESTIMATE.: 0 PROGRESS NOTES: -=-=(Guest - Sat, 27 Feb 2010, 10:11)=-=- Status updated. --- /tmp/wklog.68.old.24229 2010-02-27 10:11:57.000000000 +0000 +++ /tmp/wklog.68.new.24229 2010-02-27 10:11:57.000000000 +0000 @@ -1 +1 @@ -Assigned +In-Progress -=-=(Timour - Mon, 22 Feb 2010, 17:39)=-=- High-Level Specification modified. --- /tmp/wklog.68.old.17116 2010-02-22 17:39:48.000000000 +0200 +++ /tmp/wklog.68.new.17116 2010-02-22 17:39:48.000000000 +0200 @@ -233,6 +233,7 @@ 1. If columns a_j1,...,a_jm do not contain null values in the temporary table at all and v_j1,...,v_jm cannot be null, create for these columns only one index array (and of course do not create any bitmaps for them). +[done] 2. Consider the ratio d(a_i)=N'(a_i)/V(a_i), where N'(a_i) is the number of rows, where a_i is not null and V(a_i) is the number of distinct @@ -264,6 +265,10 @@ 7. If you get a row with nulls in all columns stop filling the temporary table and return UNKNOWN for any tuple <v1,...,vn>. +[This is wrong, because if we don't fill the whole temp table, there may + be some tuple(s) that would match some outer tuple. In such cases, if we + stop filling the temp table, we would miss a TRUE result. Having a partial + match doesn't preclude us from having a complete match]. 8. [timour] Consider that due to materialization, we already have a unique index -=-=(Timour - Tue, 19 Jan 2010, 18:44)=-=- High-Level Specification modified. --- /tmp/wklog.68.old.22569 2010-01-19 18:44:01.000000000 +0200 +++ /tmp/wklog.68.new.22569 2010-01-19 18:44:01.000000000 +0200 @@ -132,11 +132,10 @@ if (nonull_key && ! nonull_key->lookup(outer_ref)) return FALSE - if (nonull_key) - pq.insert(nonull_key) for (i = 1; i <= n; i++) { + if (vkey[i] != nonull_key) vkey[i].lookup(outer_ref) if (! vkey[i].is_eof()) pq.insert(i) @@ -167,7 +166,7 @@ /* There cannot be a complete match, as we already checked for one. */ assert(matching_keys.elements < n) } - else if (cur_min_key == nonull_key) + else if (vkey[cur_min_key] == nonull_key) { /* The non-NULL key has no corresponding NULL index, so we know for @@ -183,8 +182,10 @@ /* Check if all null_keys contain a NULL at row 'min_row'. The procedure internally checks all keys in a special precomputed order. A prior - procedure determines an optimal order and a mapping - idx_no -> idx_order (encoded as an array). + procedure determines an optimal order and a mapping idx_no -> idx_order + (encoded as an array). + + This procedure makes sure not to match the non-NULL column. */ if (test_null_row(null_keys, min_row)) return TRUE @@ -198,6 +199,14 @@ vkey[cur_min_key].next() if (! vkey[cur_min_key].is_eof()) pq.insert(cur_min_key) + else if (vkey[cur_min_key] == nonull_key) + { + /* + If there can't be more matches for the nonull_key, we know for sure + there is no match, since there is no possible NULL match. + */ + return FALSE + } if (pq.is_empty()) { @@ -216,7 +225,6 @@ } - 3. Directions for improvement ======================================================================== -=-=(Timour - Tue, 19 Jan 2010, 18:29)=-=- High-Level Specification modified. --- /tmp/wklog.68.old.21045 2010-01-19 18:29:12.000000000 +0200 +++ /tmp/wklog.68.new.21045 2010-01-19 18:29:12.000000000 +0200 @@ -132,6 +132,8 @@ if (nonull_key && ! nonull_key->lookup(outer_ref)) return FALSE + if (nonull_key) + pq.insert(nonull_key) for (i = 1; i <= n; i++) { -=-=(Guest - Tue, 19 Jan 2010, 18:15)=-=- High-Level Specification modified. --- /tmp/wklog.68.old.19825 2010-01-19 18:15:30.000000000 +0200 +++ /tmp/wklog.68.new.19825 2010-01-19 18:15:30.000000000 +0200 @@ -1,8 +1,16 @@ -This a copy of the initial algorithm proposed by Igor: -====================================================== +Contents +======================================================================== -For each left side tuple (v_1,...,v_n) we have to find the following set -of rowids for the temp table containing N rows as the result of +1. Initial idea as proposed by Igor +2. Algorithm for IN execution with partial matching +3. Directions for improvement + + +1. Initial idea as proposed by Igor +======================================================================== + +For each left side tuple (v_1,...,v_n) we have to find the following +set of rowids for the temp table containing N rows as the result of materialization of the subquery: R= INTERSECT (rowid{a_i=v_i} UNION rowid{a_i is null} where i runs @@ -18,38 +26,198 @@ - it requires minimum memory: not more than N*n bits in total - search of an element in a set is extremely cheap -Taken all above into account I could suggest the following algorithm to -build R: +Taken all above into account I could suggest the following algorithm +to build R: - Using indexes (read about them below) for each column participating in the - intersection, - merge ordered sets rowid{a_i=v_i} in the following manner. + Using indexes (read about them below) for each column participating + in the intersection, merge ordered sets rowid{a_i=v_i} in the + following manner. If a rowid r has been encountered maximum in k sets -rowid{a_i1=v_i1},...,rowid(a_ik=v_ik), + rowid{a_i1=v_i1},...,rowid(a_ik=v_ik), then it has to be checked against all rowid{a_i=v_i} such that i is -not in {i1,...,ik}. + not in {i1,...,ik}. As soon as we fail to find r in one of these sets we discard it. If r has been found in all of them then r belongs to the set R. -Here we use the property (1): any r from rowid{a_i=v_i} UNION rowid{a_i -is null} is either +Here we use the property (1): +any r from rowid{a_i=v_i} UNION rowid{a_i is null} is either belongs to rowid{a_i=v_i} or to rowid{a_i is null}. From this we can -infer that for any r from R -indexes a_i can be uniquely divided into two groups: one contains -indexes a_i where r belongs to -the sets rowid{a_i=v_i}, the other contains indexes a_j such that r -belongs to rowid{a_j is null}. - -Now let's talk how to get elements from rowid{a_i=v_i} in a sorted order -needed for the merge procedure. We could use BTREE indexes for temp -table. But they are rather expensive and -take a lot of memory as the are implemented with RB trees. +infer that for any r from R indexes a_i can be uniquely divided into +two groups: +- one contains indexes a_i where r belongs to the sets rowid{a_i=v_i}, +- the other contains indexes a_j such that r belongs to + rowid{a_j is null}. + +Now let's talk how to get elements from rowid{a_i=v_i} in a sorted +order needed for the merge procedure. We could use BTREE indexes for +temp table. But they are rather expensive and take a lot of memory as +the are implemented with RB trees. I would suggest creating for each column from the temporary table just an array of rowids sorted by the value from column a. Index lookup in such an array is cheap. It's also rather cheap to check that the next rowid refers to a row with a different value in column a. The array can be created on demand. +2. Algorithm for IN execution with partial matching +======================================================================== + +2.1 Below is shown the top-level algorithm to execute an IN predicate +with partial matching. This algorithm is essentially the implementation +of Item_subselect:exec(). + +int lookup_with_null_semantics(outer_ref[], mat_subquery) +{ + if (index_lookup(outer_ref, mat_subquery) + return TRUE + else + { + /* + Check if there is a partial match (UNKNOWN) or no match (NULL). + */ + if (this is the first partial match) + { + vkey[] = build array of value keys for each NULL-able column + of mat_subquery. + nkey[] = build a bitmap NULL index for each column of mat_subquery + that contains NULLs + nonull_key = build a key over all non-NULL columns of mat_subquery + } + if (partial_match(outer_ref, vkey[], nkey[], nonull_key) + return UNKNOWN + else + return FALSE + } +} + +2.2 The implementation of partial matching is as follows + +/* + Assumptions: + - It has already been checked if there is a complete match by a + regular index lookup, and the test failed. + - It has already been checked if there is a complete NULL row, + and if there was we wouldn't call this function. Thus we assume + that there is no complete NULL row. + - Not all vidx_i are empty, but some can be empty. If all were empty, + then the only possibility for a match is a complete NULL row, which + we already checked. + + @param outer_ref - the uter (left) IN argument. + @param vidx[] - array of value keys + Ordered sequences of rowids of the corresponding columns a_i, such + that all rowids in idx_i are the ones where column a_i contains some + value or NULL. Each idx_i is derived dynamically, for each different + left argument of an IN predicate. + @param nidx[] - array of NULL keys + Bitmpas, one per each column, where a bit is set if the corresponding + row has a NULL value for the corresponding column. + @nonull_key - the only key over all columns of the materialized subquery + that do not contain NULLs + + @returns + @retval FALSE if there is no match + @retval TRUE if there is a partial match +*/ + +Boolean partial_match(outer_ref, vkey[], nkey[], nonull_key) +{ + /* Set of the keys (columns) that form a partial match. */ + Set matching_keys = {} + /* A subset of all keys that need to be checked for NULL matches. */ + Set null_keys = {} + Int min_key /* Key that contains the current minimum position. */ + Int min_row /* Current row number of min_key. */ + Int cur_min_key, cur_min_row + PriorityQueue pq + + if (nonull_key && ! nonull_key->lookup(outer_ref)) + return FALSE + + for (i = 1; i <= n; i++) + { + vkey[i].lookup(outer_ref) + if (! vkey[i].is_eof()) + pq.insert(i) + } + /* + Not all value keys are empty, thus we don't have only NULL + keys. If we had, the only possible match is a NULL row, and + we cheked there is no such row, therefore the result is known + to be FALSE. + In fact this algorithm makes sense for at least two non-NULL + columns. + */ + assert(pq.elements > 1) + + (min_key, min_row) = pq.pop() + matching_keys.add(min_key) + vkey[min_key].next() + if (! vkey[min_key].is_eof()) + pq.insert(min_key) + + while (TRUE) + { + (cur_min_key, cur_min_row) = pq.pop() + + if (cur_min_row == min_row) + { + matching_keys.add(cur_min_key) + /* There cannot be a complete match, as we already checked for one. */ + assert(matching_keys.elements < n) + } + else if (cur_min_key == nonull_key) + { + /* + The non-NULL key has no corresponding NULL index, so we know for + sure that the row 'min_row' is not a match. + */ + (min_key, min_row) = (cur_min_key, cur_min_row) + matching_keys = {min_key} + } + else + { + assert(cur_min_row > min_row) /* Follows from the use of PQ. */ + null_keys = set_difference(all keys vkey[], matching_keys) + /* + Check if all null_keys contain a NULL at row 'min_row'. The procedure + internally checks all keys in a special precomputed order. A prior + procedure determines an optimal order and a mapping + idx_no -> idx_order (encoded as an array). + */ + if (test_null_row(null_keys, min_row)) + return TRUE + else + { + (min_key, min_row) = (cur_min_key, cur_min_row) + matching_keys = {min_key} + } + } + + vkey[cur_min_key].next() + if (! vkey[cur_min_key].is_eof()) + pq.insert(cur_min_key) + + if (pq.is_empty()) + { + /* Check the last row of the last column in PQ for NULL matches. */ + null_keys = set_difference(all keys vkey[], matching_keys) + if (test_null_row(null_keys, min_row)) + return TRUE + else + return FALSE + } + } + + /* We should never get here. */ + assert(FALSE) + return FALSE +} + + + +3. Directions for improvement +======================================================================== + Other consideration that may be taken into account: 1. If columns a_j1,...,a_jm do not contain null values in the temporary -=-=(Timour - Sun, 06 Dec 2009, 14:36)=-=- High-Level Specification modified. --- /tmp/wklog.68.old.12919 2009-12-06 14:36:18.000000000 +0200 +++ /tmp/wklog.68.new.12919 2009-12-06 14:36:18.000000000 +0200 @@ -87,3 +87,8 @@ 7. If you get a row with nulls in all columns stop filling the temporary table and return UNKNOWN for any tuple <v1,...,vn>. +8. [timour] + Consider that due to materialization, we already have a unique index +on all columns <a_1,..., a_n>. We can use the first key part of this index +over column a_1, instead of the index rowid{a_i=v_i}. Thus we can avoid +creating the index rowid{a_i=v_i}. -=-=(Timour - Fri, 04 Dec 2009, 14:04)=-=- High-Level Specification modified. --- /tmp/wklog.68.old.16724 2009-12-04 14:04:28.000000000 +0200 +++ /tmp/wklog.68.new.16724 2009-12-04 14:04:28.000000000 +0200 @@ -10,7 +10,8 @@ Bear in mind the following specifics of this intersection: (1) For each i: rowid{a_i=v_i} and rowid{a_i is null} are disjoint - (2) For each i: rowid{a_i is null} is the same for each tuple + (2) For each i: rowid{a_i is null} is the same for each tuple, + that is, this set is independent of the left-side tuples. Due to (2) it makes sense to build rowid{a_i is null} only once. A good representation for such sets would be bitmaps: -=-=(Timour - Fri, 04 Dec 2009, 11:27)=-=- Version updated. --- /tmp/wklog.68.old.5257 2009-12-04 11:27:11.000000000 +0200 +++ /tmp/wklog.68.new.5257 2009-12-04 11:27:11.000000000 +0200 @@ -1 +1 @@ -Benchmarks-3.0 +Server-9.x -=-=(Timour - Fri, 04 Dec 2009, 11:27)=-=- Category updated. --- /tmp/wklog.68.old.5242 2009-12-04 11:27:02.000000000 +0200 +++ /tmp/wklog.68.new.5242 2009-12-04 11:27:02.000000000 +0200 @@ -1 +1 @@ -Server-RawIdeaBin +Server-Sprint -=-=(Timour - Fri, 04 Dec 2009, 11:27)=-=- Status updated. --- /tmp/wklog.68.old.5242 2009-12-04 11:27:02.000000000 +0200 +++ /tmp/wklog.68.new.5242 2009-12-04 11:27:02.000000000 +0200 @@ -1 +1 @@ -Un-Assigned +Assigned ------------------------------------------------------------ -=-=(View All Progress Notes, 12 total)=-=- http://askmonty.org/worklog/index.pl?tid=68&nolimit=1 DESCRIPTION: The goal of this task is to implement efficient execution of NOT IN subquery predicates of the form: <oe_1,...,oe_n> NOT IN <non_correlated subquery> when either some oe_i, or some subqury result column contains NULLs. The problem with such predicates is that it is possible to use index lookups only when neither argument of the predicate contains NULLs. If some argument contains a NULL, then due to NULL semantics, it plays the role of a wildcard. If we were to use regular index lookups, then we would get 'no match' for some outer tuple (thus the predicate evaluates to FALSE), while the SQL semantics means 'partial match', and the predicate should evaluate to NULL. This task implements an efficient algorithm to compute such 'parial matches', where a NULL matches any value. HIGH-LEVEL SPECIFICATION: Contents ======================================================================== 1. Initial idea as proposed by Igor 2. Algorithm for IN execution with partial matching 3. Directions for improvement 1. Initial idea as proposed by Igor ======================================================================== For each left side tuple (v_1,...,v_n) we have to find the following set of rowids for the temp table containing N rows as the result of materialization of the subquery: R= INTERSECT (rowid{a_i=v_i} UNION rowid{a_i is null} where i runs trough all indexes from [1..n] such that v_i is not null. Bear in mind the following specifics of this intersection: (1) For each i: rowid{a_i=v_i} and rowid{a_i is null} are disjoint (2) For each i: rowid{a_i is null} is the same for each tuple, that is, this set is independent of the left-side tuples. Due to (2) it makes sense to build rowid{a_i is null} only once. A good representation for such sets would be bitmaps: - it requires minimum memory: not more than N*n bits in total - search of an element in a set is extremely cheap Taken all above into account I could suggest the following algorithm to build R: Using indexes (read about them below) for each column participating in the intersection, merge ordered sets rowid{a_i=v_i} in the following manner. If a rowid r has been encountered maximum in k sets rowid{a_i1=v_i1},...,rowid(a_ik=v_ik), then it has to be checked against all rowid{a_i=v_i} such that i is not in {i1,...,ik}. As soon as we fail to find r in one of these sets we discard it. If r has been found in all of them then r belongs to the set R. Here we use the property (1): any r from rowid{a_i=v_i} UNION rowid{a_i is null} is either belongs to rowid{a_i=v_i} or to rowid{a_i is null}. From this we can infer that for any r from R indexes a_i can be uniquely divided into two groups: - one contains indexes a_i where r belongs to the sets rowid{a_i=v_i}, - the other contains indexes a_j such that r belongs to rowid{a_j is null}. Now let's talk how to get elements from rowid{a_i=v_i} in a sorted order needed for the merge procedure. We could use BTREE indexes for temp table. But they are rather expensive and take a lot of memory as the are implemented with RB trees. I would suggest creating for each column from the temporary table just an array of rowids sorted by the value from column a. Index lookup in such an array is cheap. It's also rather cheap to check that the next rowid refers to a row with a different value in column a. The array can be created on demand. 2. Algorithm for IN execution with partial matching ======================================================================== 2.1 Below is shown the top-level algorithm to execute an IN predicate with partial matching. This algorithm is essentially the implementation of Item_subselect:exec(). int lookup_with_null_semantics(outer_ref[], mat_subquery) { if (index_lookup(outer_ref, mat_subquery) return TRUE else { /* Check if there is a partial match (UNKNOWN) or no match (NULL). */ if (this is the first partial match) { vkey[] = build array of value keys for each NULL-able column of mat_subquery. nkey[] = build a bitmap NULL index for each column of mat_subquery that contains NULLs nonull_key = build a key over all non-NULL columns of mat_subquery } if (partial_match(outer_ref, vkey[], nkey[], nonull_key) return UNKNOWN else return FALSE } } 2.2 The implementation of partial matching is as follows /* Assumptions: - It has already been checked if there is a complete match by a regular index lookup, and the test failed. - It has already been checked if there is a complete NULL row, and if there was we wouldn't call this function. Thus we assume that there is no complete NULL row. - Not all vidx_i are empty, but some can be empty. If all were empty, then the only possibility for a match is a complete NULL row, which we already checked. @param outer_ref - the uter (left) IN argument. @param vidx[] - array of value keys Ordered sequences of rowids of the corresponding columns a_i, such that all rowids in idx_i are the ones where column a_i contains some value or NULL. Each idx_i is derived dynamically, for each different left argument of an IN predicate. @param nidx[] - array of NULL keys Bitmpas, one per each column, where a bit is set if the corresponding row has a NULL value for the corresponding column. @nonull_key - the only key over all columns of the materialized subquery that do not contain NULLs @returns @retval FALSE if there is no match @retval TRUE if there is a partial match */ Boolean partial_match(outer_ref, vkey[], nkey[], nonull_key) { /* Set of the keys (columns) that form a partial match. */ Set matching_keys = {} /* A subset of all keys that need to be checked for NULL matches. */ Set null_keys = {} Int min_key /* Key that contains the current minimum position. */ Int min_row /* Current row number of min_key. */ Int cur_min_key, cur_min_row PriorityQueue pq if (nonull_key && ! nonull_key->lookup(outer_ref)) return FALSE for (i = 1; i <= n; i++) { if (vkey[i] != nonull_key) vkey[i].lookup(outer_ref) if (! vkey[i].is_eof()) pq.insert(i) } /* Not all value keys are empty, thus we don't have only NULL keys. If we had, the only possible match is a NULL row, and we cheked there is no such row, therefore the result is known to be FALSE. In fact this algorithm makes sense for at least two non-NULL columns. */ assert(pq.elements > 1) (min_key, min_row) = pq.pop() matching_keys.add(min_key) vkey[min_key].next() if (! vkey[min_key].is_eof()) pq.insert(min_key) while (TRUE) { (cur_min_key, cur_min_row) = pq.pop() if (cur_min_row == min_row) { matching_keys.add(cur_min_key) /* There cannot be a complete match, as we already checked for one. */ assert(matching_keys.elements < n) } else if (vkey[cur_min_key] == nonull_key) { /* The non-NULL key has no corresponding NULL index, so we know for sure that the row 'min_row' is not a match. */ (min_key, min_row) = (cur_min_key, cur_min_row) matching_keys = {min_key} } else { assert(cur_min_row > min_row) /* Follows from the use of PQ. */ null_keys = set_difference(all keys vkey[], matching_keys) /* Check if all null_keys contain a NULL at row 'min_row'. The procedure internally checks all keys in a special precomputed order. A prior procedure determines an optimal order and a mapping idx_no -> idx_order (encoded as an array). This procedure makes sure not to match the non-NULL column. */ if (test_null_row(null_keys, min_row)) return TRUE else { (min_key, min_row) = (cur_min_key, cur_min_row) matching_keys = {min_key} } } vkey[cur_min_key].next() if (! vkey[cur_min_key].is_eof()) pq.insert(cur_min_key) else if (vkey[cur_min_key] == nonull_key) { /* If there can't be more matches for the nonull_key, we know for sure there is no match, since there is no possible NULL match. */ return FALSE } if (pq.is_empty()) { /* Check the last row of the last column in PQ for NULL matches. */ null_keys = set_difference(all keys vkey[], matching_keys) if (test_null_row(null_keys, min_row)) return TRUE else return FALSE } } /* We should never get here. */ assert(FALSE) return FALSE } 3. Directions for improvement ======================================================================== Other consideration that may be taken into account: 1. If columns a_j1,...,a_jm do not contain null values in the temporary table at all and v_j1,...,v_jm cannot be null, create for these columns only one index array (and of course do not create any bitmaps for them). [done] 2. Consider the ratio d(a_i)=N'(a_i)/V(a_i), where N'(a_i) is the number of rows, where a_i is not null and V(a_i) is the number of distinct values for a_i excluding nulls. If d(a_i) is close to N'(a_i) then do not create any index array: check whether there is a match running through the records that have been filtered in. Anyway if d(a_i) is close to N'(a_i) then the intersection with rowid{a_i=v_i} will not reduce the number of remaining rowids significantly. In other words is V(a_i) exceeds some threshold there is no sense to create an index for a_i. If additionally N-N'(a_i) is small do not create a bitmap for this column either. 3. If for a column a_i d(a_i) is not close to N'(a_i), but N-N'(a_i) is small a sorted array of rowids from the set rowid{a_i is null} can be used instead of a bitmap. 4. We always have a match if R0= INTERSECT rowid{a_i is null} is not empty. Here i runs through all indexes from [1..n] such that v_i is not null. For a given subset of columns this fact has to be checked only once. It can be easily done with bitmap intersection. 5. If v1,...,vn never can be a null, then indexes (sorted arrays) can be created only for rows with nulls. 6. If v1,...,vn never can be a null and number of rows with nulls is small do not create indexes and do not create bitmaps. 7. If you get a row with nulls in all columns stop filling the temporary table and return UNKNOWN for any tuple <v1,...,vn>. [This is wrong, because if we don't fill the whole temp table, there may be some tuple(s) that would match some outer tuple. In such cases, if we stop filling the temp table, we would miss a TRUE result. Having a partial match doesn't preclude us from having a complete match]. 8. [timour] Consider that due to materialization, we already have a unique index on all columns <a_1,..., a_n>. We can use the first key part of this index over column a_1, instead of the index rowid{a_i=v_i}. Thus we can avoid creating the index rowid{a_i=v_i}. ESTIMATED WORK TIME ESTIMATED COMPLETION DATE ----------------------------------------------------------------------- WorkLog (v3.5.9)

1 0