- developers - lists.mariadb.org

[Maria-developers] Updated (by Timour): Subquery optimization: Efficient NOT IN execution with NULLs (68)
by worklog-noreply＠askmonty.org 04 Dec '09

04 Dec '09

----------------------------------------------------------------------- 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 - 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 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>. ESTIMATED WORK TIME ESTIMATED COMPLETION DATE ----------------------------------------------------------------------- WorkLog (v3.5.9)

1 0

[Maria-developers] Updated (by Timour): Subquery optimization: Efficient NOT IN execution with NULLs (68)
by worklog-noreply＠askmonty.org 04 Dec '09

04 Dec '09

----------------------------------------------------------------------- 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 - 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 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>. ESTIMATED WORK TIME ESTIMATED COMPLETION DATE ----------------------------------------------------------------------- WorkLog (v3.5.9)

1 0

[Maria-developers] Updated (by Timour): Subquery optimization: Efficient NOT IN execution with NULLs (68)
by worklog-noreply＠askmonty.org 04 Dec '09

04 Dec '09

----------------------------------------------------------------------- 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........: Benchmarks-3.0 STATUS.........: Assigned PRIORITY.......: 60 WORKED HOURS...: 0 ESTIMATE.......: 0 (hours remain) ORIG. ESTIMATE.: 0 PROGRESS NOTES: -=-=(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 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>. ESTIMATED WORK TIME ESTIMATED COMPLETION DATE ----------------------------------------------------------------------- WorkLog (v3.5.9)

1 0

[Maria-developers] Updated (by Timour): Subquery optimization: Efficient NOT IN execution with NULLs (68)
by worklog-noreply＠askmonty.org 04 Dec '09

04 Dec '09

----------------------------------------------------------------------- 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........: Benchmarks-3.0 STATUS.........: Assigned PRIORITY.......: 60 WORKED HOURS...: 0 ESTIMATE.......: 0 (hours remain) ORIG. ESTIMATE.: 0 PROGRESS NOTES: -=-=(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 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>. ESTIMATED WORK TIME ESTIMATED COMPLETION DATE ----------------------------------------------------------------------- WorkLog (v3.5.9)

1 0

[Maria-developers] Updated (by Timour): Subquery optimization: Efficient NOT IN execution with NULLs (68)
by worklog-noreply＠askmonty.org 04 Dec '09

04 Dec '09

----------------------------------------------------------------------- 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, 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 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>. ESTIMATED WORK TIME ESTIMATED COMPLETION DATE ----------------------------------------------------------------------- WorkLog (v3.5.9)

1 0

[Maria-developers] Updated (by Timour): Subquery optimization: Efficient NOT IN execution with NULLs (68)
by worklog-noreply＠askmonty.org 04 Dec '09

04 Dec '09

----------------------------------------------------------------------- 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, 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 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>. ESTIMATED WORK TIME ESTIMATED COMPLETION DATE ----------------------------------------------------------------------- WorkLog (v3.5.9)

1 0

[Maria-developers] Rev 2775: Fix for maria BUG#491097. in file:///home/bell/maria/bzr/work-maria-5.1-test/
by sanja＠askmonty.org 03 Dec '09

03 Dec '09

At file:///home/bell/maria/bzr/work-maria-5.1-test/ ------------------------------------------------------------ revno: 2775 revision-id: sanja(a)askmonty.org-20091203210748-x0t8m9pim0x20s7g parent: monty(a)askmonty.org-20091201160902-a3iq6lw82xbto9yp committer: sanja(a)askmonty.org branch nick: work-maria-5.1-test timestamp: Thu 2009-12-03 23:07:48 +0200 message: Fix for maria BUG#491097. Unlock tables before sending OK to client. === modified file 'sql/mysql_priv.h' --- a/sql/mysql_priv.h 2009-11-16 20:49:51 +0000 +++ b/sql/mysql_priv.h 2009-12-03 21:07:48 +0000 @@ -796,6 +796,7 @@ void cleanup_items(Item *item); class THD; void close_thread_tables(THD *thd); +void unlock_thread_tables(THD *thd); #ifndef NO_EMBEDDED_ACCESS_CHECKS bool check_one_table_access(THD *thd, ulong privilege, TABLE_LIST *tables); === modified file 'sql/sql_base.cc' --- a/sql/sql_base.cc 2009-11-30 21:37:27 +0000 +++ b/sql/sql_base.cc 2009-12-03 21:07:48 +0000 @@ -1213,6 +1213,33 @@ } +/** + Unlocks tables in thd->lock() + + + @param thd Thread handler +*/ + +void unlock_thread_tables(THD *thd) +{ + if (thd->lock) + { + /* + For RBR we flush the pending event just before we unlock all the + tables. This means that we are at the end of a topmost + statement, so we ensure that the STMT_END_F flag is set on the + pending event. For statements that are *inside* stored + functions, the pending event will not be flushed: that will be + handled either before writing a query log event (inside + binlog_query()) or when preparing a pending event. + */ + thd->binlog_flush_pending_rows_event(TRUE); + mysql_unlock_tables(thd, thd->lock); + thd->lock=0; + } +} + + /* Close all tables used by the current substatement, or all tables used by this thread if we are on the upper level. @@ -1325,21 +1352,8 @@ /* Fallthrough */ } - if (thd->lock) - { - /* - For RBR we flush the pending event just before we unlock all the - tables. This means that we are at the end of a topmost - statement, so we ensure that the STMT_END_F flag is set on the - pending event. For statements that are *inside* stored - functions, the pending event will not be flushed: that will be - handled either before writing a query log event (inside - binlog_query()) or when preparing a pending event. - */ - thd->binlog_flush_pending_rows_event(TRUE); - mysql_unlock_tables(thd, thd->lock); - thd->lock=0; - } + unlock_thread_tables(thd); + /* Note that we need to hold LOCK_open while changing the open_tables list. Another thread may work on it. === modified file 'sql/sql_parse.cc' --- a/sql/sql_parse.cc 2009-11-30 21:37:27 +0000 +++ b/sql/sql_parse.cc 2009-12-03 21:07:48 +0000 @@ -1252,6 +1252,12 @@ ha_maria::implicit_commit(thd, FALSE); #endif + /* + We should unlock tables before sending OK to client, because + unlocking makes results of insert (for example) visible for other + threads (for some engines like MyISAM). + */ + unlock_thread_tables(thd); net_end_statement(thd); query_cache_end_of_result(thd); /* @@ -1645,6 +1651,12 @@ ha_maria::implicit_commit(thd, FALSE); #endif + /* + We should unlock tables before sending OK to client, because unlocking + makes results of insert (for example) visible for other threads (for + some engines like MyISAM). + */ + unlock_thread_tables(thd); net_end_statement(thd); query_cache_end_of_result(thd);

1 0

[Maria-developers] [Branch ~maria-captains/maria/5.1] Rev 2776: Applied patch from to fix some problems with Croatian character set and LIKE queries
by noreply＠launchpad.net 03 Dec '09

03 Dec '09

------------------------------------------------------------ revno: 2776 committer: Michael Widenius <monty(a)askmonty.org> branch nick: maria-5.1 timestamp: Thu 2009-12-03 14:02:37 +0200 message: Applied patch from to fix some problems with Croatian character set and LIKE queries Author: Alexander Barkov License: GPL modified: mysql-test/r/ctype_ucs.result mysql-test/t/ctype_ucs.test strings/ctype-ucs2.c -- lp:maria https://code.launchpad.net/~maria-captains/maria/5.1 Your team Maria developers is subscribed to branch lp:maria. To unsubscribe from this branch go to https://code.launchpad.net/~maria-captains/maria/5.1/+edit-subscription.

1 0

[Maria-developers] [Branch ~maria-captains/maria/5.1] Rev 2775: Merge
by noreply＠launchpad.net 03 Dec '09

03 Dec '09

Merge authors: Antony T Curtis (atcurtis) hery.ramilison(a)sun.com Igor Babaev (igorb-seattle) Michael Widenius (monty) Michael Widenius (monty) Related merge proposals: https://code.launchpad.net/~atcurtis/maria/maria-5.1-federatedx/+merge/14409 proposed by: Antony T Curtis (atcurtis) review: Needs Fixing - Michael Widenius (monty) ------------------------------------------------------------ revno: 2775 [merge] committer: Michael Widenius <monty(a)askmonty.org> branch nick: maria-5.1 timestamp: Thu 2009-12-03 13:34:11 +0200 message: Merge modified: client/mysql.cc client/mysqlcheck.c client/mysqlslap.c client/mysqltest.cc mysql-test/lib/mtr_report.pm mysql-test/mysql-test-run.pl mysql-test/suite/federated/disabled.def mysql-test/suite/federated/federated_server.result mysql-test/suite/federated/federated_server.test storage/federatedx/ha_federatedx.cc unittest/mysys/Makefile.am -- lp:maria https://code.launchpad.net/~maria-captains/maria/5.1 Your team Maria developers is subscribed to branch lp:maria. To unsubscribe from this branch go to https://code.launchpad.net/~maria-captains/maria/5.1/+edit-subscription.

1 0

[Maria-developers] bzr commit into MariaDB 5.1, with Maria 1.5:maria branch (monty:2776)
by Michael Widenius 03 Dec '09

03 Dec '09

#At lp:maria based on revid:monty@askmonty.org-20091203113411-cmr8g2lcp45n0prv 2776 Michael Widenius 2009-12-03 Applied patch from to fix some problems with Croatian character set and LIKE queries Author: Alexander Barkov License: GPL modified: mysql-test/r/ctype_ucs.result mysql-test/t/ctype_ucs.test strings/ctype-ucs2.c per-file messages: mysql-test/t/ctype_ucs.test Added test case for Croatina character set === modified file 'mysql-test/r/ctype_ucs.result' --- a/mysql-test/r/ctype_ucs.result 2008-12-23 14:21:01 +0000 +++ b/mysql-test/r/ctype_ucs.result 2009-12-03 12:02:37 +0000 @@ -1211,3 +1211,47 @@ HEX(DAYNAME(19700101)) 0427043504420432043504400433 SET character_set_connection=latin1; End of 5.0 tests +Start of 5.1 tests +SET NAMES utf8; +CREATE TABLE t1 ( +a varchar(10) CHARACTER SET ucs2 COLLATE ucs2_czech_ci, +key(a) +); +INSERT INTO t1 VALUES +('aa'),('bb'),('cc'),('dd'),('ee'),('ff'),('gg'),('hh'),('ii'), +('jj'),('kk'),('ll'),('mm'),('nn'),('oo'),('pp'),('rr'),('ss'), +('tt'),('uu'),('vv'),('ww'),('xx'),('yy'),('zz'); +INSERT INTO t1 VALUES ('ca'),('cz'),('ch'); +INSERT INTO t1 VALUES ('da'),('dz'), (X'0064017E'); +EXPLAIN SELECT * FROM t1 WHERE a LIKE 'b%'; +id select_type table type possible_keys key key_len ref rows Extra +1 SIMPLE t1 range a a 23 NULL 1 Using where; Using index +EXPLAIN SELECT * FROM t1 WHERE a LIKE 'c%'; +id select_type table type possible_keys key key_len ref rows Extra +1 SIMPLE t1 range a a 23 NULL 30 Using where; Using index +SELECT * FROM t1 WHERE a LIKE 'c%'; +a +ca +cc +cz +ch +EXPLAIN SELECT * FROM t1 WHERE a LIKE 'ch%'; +id select_type table type possible_keys key key_len ref rows Extra +1 SIMPLE t1 range a a 23 NULL 1 Using where; Using index +SELECT * FROM t1 WHERE a LIKE 'ch%'; +a +ch +ALTER TABLE t1 MODIFY a VARCHAR(10) CHARACTER SET ucs2 COLLATE ucs2_croatian_ci; +EXPLAIN SELECT * FROM t1 WHERE a LIKE 'd%'; +id select_type table type possible_keys key key_len ref rows Extra +1 SIMPLE t1 range a a 23 NULL 1 Using where; Using index +SELECT hex(concat('d',_ucs2 0x017E,'%')); +hex(concat('d',_ucs2 0x017E,'%')) +0064017E0025 +EXPLAIN SELECT * FROM t1 WHERE a LIKE concat('d',_ucs2 0x017E,'%'); +id select_type table type possible_keys key key_len ref rows Extra +1 SIMPLE t1 range a a 23 NULL 1 Using where; Using index +SELECT hex(a) FROM t1 WHERE a LIKE concat('D',_ucs2 0x017E,'%'); +hex(a) +0064017E +DROP TABLE t1; === modified file 'mysql-test/t/ctype_ucs.test' --- a/mysql-test/t/ctype_ucs.test 2008-12-23 14:21:01 +0000 +++ b/mysql-test/t/ctype_ucs.test 2009-12-03 12:02:37 +0000 @@ -723,3 +723,34 @@ SELECT HEX(DAYNAME(19700101)); SET character_set_connection=latin1; --echo End of 5.0 tests + + +--echo Start of 5.1 tests +# +# Checking my_like_range_ucs2 +# +SET NAMES utf8; +CREATE TABLE t1 ( + a varchar(10) CHARACTER SET ucs2 COLLATE ucs2_czech_ci, + key(a) +); +INSERT INTO t1 VALUES +('aa'),('bb'),('cc'),('dd'),('ee'),('ff'),('gg'),('hh'),('ii'), +('jj'),('kk'),('ll'),('mm'),('nn'),('oo'),('pp'),('rr'),('ss'), +('tt'),('uu'),('vv'),('ww'),('xx'),('yy'),('zz'); +INSERT INTO t1 VALUES ('ca'),('cz'),('ch'); +INSERT INTO t1 VALUES ('da'),('dz'), (X'0064017E'); +# This one should scan only one row +EXPLAIN SELECT * FROM t1 WHERE a LIKE 'b%'; +# This one should scan many rows: 'c' is a contraction head +EXPLAIN SELECT * FROM t1 WHERE a LIKE 'c%'; +SELECT * FROM t1 WHERE a LIKE 'c%'; +EXPLAIN SELECT * FROM t1 WHERE a LIKE 'ch%'; +SELECT * FROM t1 WHERE a LIKE 'ch%'; +ALTER TABLE t1 MODIFY a VARCHAR(10) CHARACTER SET ucs2 COLLATE ucs2_croatian_ci; +EXPLAIN SELECT * FROM t1 WHERE a LIKE 'd%'; +SELECT hex(concat('d',_ucs2 0x017E,'%')); +EXPLAIN SELECT * FROM t1 WHERE a LIKE concat('d',_ucs2 0x017E,'%'); +SELECT hex(a) FROM t1 WHERE a LIKE concat('D',_ucs2 0x017E,'%'); + +DROP TABLE t1; === modified file 'strings/ctype-ucs2.c' --- a/strings/ctype-ucs2.c 2009-11-30 12:42:24 +0000 +++ b/strings/ctype-ucs2.c 2009-12-03 12:02:37 +0000 @@ -1498,6 +1498,14 @@ void my_hash_sort_ucs2_bin(CHARSET_INFO } } + +static inline my_wc_t +ucs2_to_wc(const uchar *ptr) +{ + return (((uint) ptr[0]) << 8) + ptr[1]; +} + + /* ** Calculate min_str and max_str that ranges a LIKE string. ** Arguments: @@ -1531,6 +1539,7 @@ my_bool my_like_range_ucs2(CHARSET_INFO for ( ; ptr + 1 < end && min_str + 1 < min_end && charlen > 0 ; ptr+=2, charlen--) { + my_wc_t wc; if (ptr[0] == '\0' && ptr[1] == escape && ptr + 1 < end) { ptr+=2; /* Skip escape */ @@ -1567,9 +1576,9 @@ fill_max_and_min: } if (have_contractions && ptr + 3 < end && - ptr[0] == '\0' && - my_uca_can_be_contraction_head(cs, (uchar) ptr[1])) + my_uca_can_be_contraction_head(cs, (wc= ucs2_to_wc((uchar*) ptr)))) { + my_wc_t wc2; /* Contraction head found */ if (ptr[2] == '\0' && (ptr[3] == w_one || ptr[3] == w_many)) { @@ -1581,9 +1590,8 @@ fill_max_and_min: Check if the second letter can be contraction part, and if two letters really produce a contraction. */ - if (ptr[2] == '\0' && - my_uca_can_be_contraction_tail(cs, (uchar) ptr[3]) && - my_uca_contraction2_weight(cs,(uchar) ptr[1], (uchar) ptr[3])) + if (my_uca_can_be_contraction_tail(cs, (wc2= ucs2_to_wc((uchar*) ptr + 2))) && + my_uca_contraction2_weight(cs, wc , wc2)) { /* Contraction found */ if (charlen == 1 || min_str + 2 >= min_end)

1 0