maria-developers team mailing list archive

[worklog-noreply@xxxxxxxxxxxx]

-----------------------------------------------------------------------
                              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.........: Assigned
PRIORITY.......: 60
WORKED HOURS...: 0
ESTIMATE.......: 0 (hours remain)
ORIG. ESTIMATE.: 0

PROGRESS NOTES:

-=-=(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

-=-=(Timour - Fri, 04 Dec 2009, 11:26)=-=-
High-Level Specification modified.
--- /tmp/wklog.68.old.5182      2009-12-04 11:26:25.000000000 +0200
+++ /tmp/wklog.68.new.5182      2009-12-04 11:26:25.000000000 +0200
@@ -50,23 +50,39 @@
 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
+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).
+
+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 1 then a intersection  with
-rowid{a_i=v_i} would not reduce the number of remaining rowids
+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.
- 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.
+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>.
+

-=-=(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:
  <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:



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,
     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.

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).

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>.

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)