[Maria-developers] Updated (by Timour): Subquery optimization: Efficient NOT IN execution with NULLs (68)
-----------------------------------------------------------------------
WORKLOG TASK
-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
TASK...........: Subquery optimization: Efficient NOT IN execution with NULLs
CREATION DATE..: Fri, 27 Nov 2009, 13:22
SUPERVISOR.....: Monty
IMPLEMENTOR....:
COPIES TO......:
CATEGORY.......: Server-RawIdeaBin
TASK ID........: 68 (http://askmonty.org/worklog/?tid=68)
VERSION........: Benchmarks-3.0
STATUS.........: Un-Assigned
PRIORITY.......: 60
WORKED HOURS...: 0
ESTIMATE.......: 0 (hours remain)
ORIG. ESTIMATE.: 0
PROGRESS NOTES:
-=-=(Timour - Fri, 27 Nov 2009, 13:23)=-=-
High-Level Specification modified.
--- /tmp/wklog.68.old.17140 2009-11-27 11:23:17.000000000 +0000
+++ /tmp/wklog.68.new.17140 2009-11-27 11:23:17.000000000 +0000
@@ -1 +1,72 @@
+This a copy of the initial algorithm 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
+
+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.
+
+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, create for them only one index array (and of course do not
+create any bitmaps for them).
+2. Consider the ratio d(a_i)=N'/ V(a_i), where N' 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 1 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 1 then a intersection with
+rowid{a_i=v_i} would not reduce the number of remaining rowids
+significantly.
+ If additionally N-N' 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 1, but N-N' 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.
DESCRIPTION:
The goal of this task is to implement efficient execution of NOT IN
subquery predicates of the form:
participants (1)
-
worklog-noreply@askmonty.org