Re: [sqlite] [patch][rebase for 3.8.2] really move "const" check out of loop "WHERE const" (and "WHERE const AND expr" optimization)
Richard Hipp wrote: > On Thu, Jan 2, 2014 at 3:25 PM, Yuriy Kaminskiy wrote: > >> Richard Hipp wrote: >>> Please verify that the alternative optimization checked-in at >>> http://www.sqlite.org/src/info/b7e39851a7 covers all of the cases that >>> you identify below. Tnx. >> Maybe I overlooked something, but from first look it cannot handle >> placeholders and constant functions, and my patch does? > > OK. How about http://www.sqlite.org/src/info/9d05777fe2 - does it work > better for you? Yes, thanks :-) ___ sqlite-users mailing list sqlite-users@sqlite.org http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users
Re: [sqlite] [patch][rebase for 3.8.2] really move "const" check out of loop "WHERE const" (and "WHERE const AND expr" optimization)
On Thu, Jan 2, 2014 at 3:25 PM, Yuriy Kaminskiy wrote: > Richard Hipp wrote: > > Please verify that the alternative optimization checked-in at > > http://www.sqlite.org/src/info/b7e39851a7 covers all of the cases that > you > > identify below. Tnx. > > Maybe I overlooked something, but from first look it cannot handle > placeholders > and constant functions, and my patch does? > OK. How about http://www.sqlite.org/src/info/9d05777fe2 - does it work better for you? -- D. Richard Hipp d...@sqlite.org ___ sqlite-users mailing list sqlite-users@sqlite.org http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users
Re: [sqlite] [patch][rebase for 3.8.2] really move "const" check out of loop "WHERE const" (and "WHERE const AND expr" optimization)
Richard Hipp wrote:
> Please verify that the alternative optimization checked-in at
> http://www.sqlite.org/src/info/b7e39851a7 covers all of the cases that you
> identify below. Tnx.
Maybe I overlooked something, but from first look it cannot handle placeholders
and constant functions, and my patch does?
(Besides, with b7e39851a7 "Special case" code remains expensive no-op.)
(Probably your patch handles some *other* cases my patch does not. Probably,
they can be applied both :-))
===
EXPLAIN SELECT * FROM t WHERE ? AND ? AND i AND ? AND j AND ?;
3.8.2 + My patch series:
sqlite> EXPLAIN SELECT * FROM t WHERE ? AND ? AND i AND ? AND j AND ?;
0|Trace|0|0|0||00|
1|Goto|0|19|0||00|
2|IfNot|1|17|1||00| <<< ?1 check moved out of loop
3|IfNot|2|17|1||00| <<< ?2 check moved out of loop
4|IfNot|3|17|1||00| <<< ?3 check moved out of loop
5|IfNot|4|17|1||00| <<< ?4 check moved out of loop
6|OpenRead|0|2|0|3|00|
7|Rewind|0|17|0||00|
8|Column|0|0|5||00|
9|IfNot|5|16|1||00| <<< only i
10|Column|0|1|6||00|
11|IfNot|6|16|1||00|<<< and j check in the inner loop
12|Column|0|0|7||00|
13|Column|0|1|8||00|
14|Column|0|2|9||00|
15|ResultRow|7|3|0||00|
16|Next|0|8|0||01|
17|Close|0|0|0||00|
18|Halt|0|0|0||00|
19|Transaction|0|0|0||00|
20|VerifyCookie|0|1|0||00|
21|TableLock|0|2|0|t|00|
22|Variable|1|1|0||00|
23|Variable|2|2|0||00|
24|Variable|3|3|0||00|
25|Variable|4|4|0||00|
26|Goto|0|2|0||00|
3.8.2 + b7e39851a7 (but without any other commits from trunk):
sqlite> EXPLAIN SELECT * FROM t WHERE ? AND ? AND i AND ? AND j AND ?;
0|Trace|0|0|0||00|
1|Goto|0|19|0||00|
2|OpenRead|0|2|0|3|00|
3|Rewind|0|17|0||00|
4|IfNot|1|16|1||00| <<< ?1 check in the inner loop
5|IfNot|2|16|1||00| <<< ?2 check in the inner loop
6|Column|0|0|3||00|
7|IfNot|3|16|1||00| <<< ?3 check in the inner loop
8|IfNot|4|16|1||00| <<< ?4 check in the inner loop
9|Column|0|1|5||00|
10|IfNot|5|16|1||00|
11|IfNot|6|16|1||00|
12|Column|0|0|7||00|
13|Column|0|1|8||00|
14|Column|0|2|9||00|
15|ResultRow|7|3|0||00|
16|Next|0|4|0||01|
17|Close|0|0|0||00|
18|Halt|0|0|0||00|
19|Transaction|0|0|0||00|
20|VerifyCookie|0|1|0||00|
21|TableLock|0|2|0|t|00|
22|Variable|1|1|0||00|
23|Variable|2|2|0||00|
24|Variable|3|4|0||00|
25|Variable|4|6|0||00|
26|Goto|0|2|0||00|
EXPLAIN SELECT * FROM t WHERE SUBSTR(DATE('now'),6) = '01-01' AND i;
My patch:
sqlite> EXPLAIN SELECT * FROM t WHERE SUBSTR(DATE('now'),6) = '01-01' AND i;
0|Trace|0|0|0||00|
1|Goto|0|14|0||00|
2|Ne|2|12|1||6a| <<< `= '01-01'` moved out of loop
3|OpenRead|0|2|0|3|00|
4|Rewind|0|12|0||00|
5|Column|0|0|3||00|
6|IfNot|3|11|1||00| <<< only [i] checked in the inner loop
7|Column|0|0|4||00|
8|Column|0|1|5||00|
9|Column|0|2|6||00|
10|ResultRow|4|3|0||00|
11|Next|0|5|0||01|
12|Close|0|0|0||00|
13|Halt|0|0|0||00|
14|Transaction|0|0|0||00|
15|VerifyCookie|0|1|0||00|
16|TableLock|0|2|0|t|00|
17|String8|0|9|0|now|00|
18|Function|1|9|7|date(-1)|01|
19|Integer|6|8|0||00|
20|Function|3|7|1|substr(2)|02|
21|String8|0|2|0|01-01|00|
22|Goto|0|2|0||00|
b7e39851a7:
sqlite> EXPLAIN SELECT * FROM t WHERE SUBSTR(DATE('now'),6) = '01-01' AND i;
0|Trace|0|0|0||00|
1|Goto|0|14|0||00|
2|OpenRead|0|2|0|3|00|
3|Rewind|0|12|0||00|
4|Ne|2|11|1||6a| ` = '01-01'` check in the inner loop
5|Column|0|0|3||00|
6|IfNot|3|11|1||00|
7|Column|0|0|4||00|
8|Column|0|1|5||00|
9|Column|0|2|6||00|
10|ResultRow|4|3|0||00|
11|Next|0|4|0||01|
12|Close|0|0|0||00|
13|Halt|0|0|0||00|
14|Transaction|0|0|0||00|
15|VerifyCookie|0|1|0||00|
16|TableLock|0|2|0|t|00|
17|String8|0|9|0|now|00|
18|Function|1|9|7|date(-1)|01|
19|Integer|6|8|0||00|
20|Function|3|7|1|substr(2)|02|
21|String8|0|2|0|01-01|00|
22|Goto|0|2|0||00|
> On Thu, Jan 2, 2014 at 9:25 AM, Yuriy Kaminskiy wrote:
>
>> On 2013/11/04 Yuriy Kaminskiy wrote:
>>> On 2012/04/08 Yuriy Kaminskiy wrote:
On 2011/12/06 Yuriy Kaminskiy wrote:
> On 2011/11/03 Yuriy Kaminskiy wrote:
>> On 2011/11/23 Yuriy Kaminskiy wrote:
>>> On 2011/10/23 Yuriy Kaminskiy wrote:
When WHERE condition is constant, there are no need to evaluate and
>> check it for
each row. It works, but only partially:
>>> ...
[In fact, you can move out out loop not only *whole* constant
>> WHERE, but also
all constant AND terms of WHERE, like this:
SELECT * FROM t WHERE const1 AND notconst AND const2 ->
SELECT * FROM (SELECT * FROM t WHERE notconst) WHERE const1 AND
>> const2
I'll take a shot on that later.]
>>> Here it goes.
>>>
>>> Prerequisite: previous patch.
>>> Passes quick regression test (make test).
>>> Possible problem: short-circuits evaluation. Should not be a
>> problem, IMO, as only
>>> constants references? Please verify.
>> P
Re: [sqlite] [patch][rebase for 3.8.2] really move "const" check out of loop "WHERE const" (and "WHERE const AND expr" optimization)
Please verify that the alternative optimization checked-in at
http://www.sqlite.org/src/info/b7e39851a7 covers all of the cases that you
identify below. Tnx.
On Thu, Jan 2, 2014 at 9:25 AM, Yuriy Kaminskiy wrote:
> On 2013/11/04 Yuriy Kaminskiy wrote:
> > On 2012/04/08 Yuriy Kaminskiy wrote:
> >> On 2011/12/06 Yuriy Kaminskiy wrote:
> >>> On 2011/11/03 Yuriy Kaminskiy wrote:
> On 2011/11/23 Yuriy Kaminskiy wrote:
> > On 2011/10/23 Yuriy Kaminskiy wrote:
> >> When WHERE condition is constant, there are no need to evaluate and
> check it for
> >> each row. It works, but only partially:
> > ...
> >> [In fact, you can move out out loop not only *whole* constant
> WHERE, but also
> >> all constant AND terms of WHERE, like this:
> >> SELECT * FROM t WHERE const1 AND notconst AND const2 ->
> >> SELECT * FROM (SELECT * FROM t WHERE notconst) WHERE const1 AND
> const2
> >> I'll take a shot on that later.]
> > Here it goes.
> >
> > Prerequisite: previous patch.
> > Passes quick regression test (make test).
> > Possible problem: short-circuits evaluation. Should not be a
> problem, IMO, as only
> > constants references? Please verify.
> Ping.
> >>> Ping.
> >> Ping.
> >> For convenience all 3 patches collected below (needed no change for
> 3.7.11).
> >
> > Ping. Over 2 years passed since this patch series was first posted.
> > Updated patch series for 3.8.1 below.
>
> Ping. Same patch series refreshed for 3.8.2 with minor change.
> --
> The author or authors of this code dedicate any and all copyright interest
> in this code to the public domain. We make this dedication for the benefit
> of the public at large and to the detriment of our heirs and successors.
> We intend this dedication to be an overt act of relinquishment in
> perpetuity
> of all present and future rights to this code under copyright law.
>
> Signed-off-by: Yuriy M. Kaminskiy
>
> Part 1: Move whereSplit() to unbreak constant condition elimination.
>
> (this is very obvious fix: only effect of "Special case" is pWhere
> assignment,
> but pWhere value is only used in whereSplit call *above* of "Special
> case"; this
> whole "Special case" is expensive no-op now)
>
> Test case:
>CREATE TABLE t (i, j, k);
>EXPLAIN SELECT * FROM t WHERE 11;
>
> Index: sqlite3-3.8.2/src/where.c
> ===
> --- sqlite3-3.8.2.orig/src/where.c 2014-01-02 16:18:24.0 +0400
> +++ sqlite3-3.8.2/src/where.c 2014-01-02 17:10:24.0 +0400
> @@ -5423,7 +5423,6 @@ WhereInfo *sqlite3WhereBegin(
>*/
>initMaskSet(pMaskSet);
>whereClauseInit(&pWInfo->sWC, pWInfo);
> - whereSplit(&pWInfo->sWC, pWhere, TK_AND);
>sqlite3CodeVerifySchema(pParse, -1); /* Insert the cookie verifier Goto
> */
>
>/* Special case: a WHERE clause that is constant. Evaluate the
> @@ -5434,6 +5433,8 @@ WhereInfo *sqlite3WhereBegin(
> pWhere = 0;
>}
>
> + whereSplit(&pWInfo->sWC, pWhere, TK_AND);
> +
>/* Special case: No FROM clause
>*/
>if( nTabList==0 ){
> ===
>
> Part 2: optimize "WHERE const AND notconst" too
>
> (trivial generalization of "Special case")
>
> Test case:
>EXPLAIN SELECT * FROM t WHERE 11 AND 12 AND i AND 13 AND j AND 14;
>
> Index: sqlite3-3.8.1/src/where.c
> ===
> --- sqlite3-3.8.1.orig/src/where.c 2013-11-03 23:27:05.0 +0400
> +++ sqlite3-3.8.1/src/where.c 2013-11-03 23:27:59.0 +0400
> @@ -5739,6 +5739,24 @@ WhereInfo *sqlite3WhereBegin(
>
>whereSplit(&pWInfo->sWC, pWhere, TK_AND);
>
> + {
> +/* Move const in "WHERE const AND notconst" out of internal loop */
> +int i, j;
> +WhereClause * const pWC = &pWInfo->sWC;
> +
> +for(j=i=0; inTerm; i++){
> + if( nTabList==0 || sqlite3ExprIsConstantNotJoin(pWC->a[i].pExpr) ){
> +sqlite3ExprIfFalse(pParse, pWC->a[i].pExpr, pWInfo->iBreak,
> SQLITE_JUMPIFNULL);
> +continue;
> + }
> + if( j!=i )
> +pWC->a[j]=pWC->a[i];
> + j++;
> +}
> +/* XXX if (i != j) memset(&(pWC->a[j]), 0, (i-j)*sizeof(pWC->a[0]));
> */
> +pWC->nTerm -= i-j;
> + }
> +
>/* Special case: No FROM clause
>*/
>if( nTabList==0 ){
> ===
> Part 3: Remove now-redundant sqlite3ExprIsConstantNotJoin call.
>
> Index: sqlite3-3.8.2/src/where.c
> ===
> --- sqlite3-3.8.2.orig/src/where.c 2014-01-02 17:10:47.0 +0400
> +++ sqlite3-3.8.2/src/where.c 2014-01-02 17:11:54.0 +0400
> @@ -5423,20 +5423,13 @@ WhereInfo *sqlite3WhereBegin(
>*/
>initMaskSet(pMaskSet);
>whereClauseInit(&pWInfo->sWC, pWInfo);
> - sqlite3CodeVerifySchema(pParse, -1); /* Insert the cookie verifier Goto
> */
> -
> - /* Special c
[sqlite] [patch][rebase for 3.8.2] really move "const" check out of loop "WHERE const" (and "WHERE const AND expr" optimization)
On 2013/11/04 Yuriy Kaminskiy wrote:
> On 2012/04/08 Yuriy Kaminskiy wrote:
>> On 2011/12/06 Yuriy Kaminskiy wrote:
>>> On 2011/11/03 Yuriy Kaminskiy wrote:
On 2011/11/23 Yuriy Kaminskiy wrote:
> On 2011/10/23 Yuriy Kaminskiy wrote:
>> When WHERE condition is constant, there are no need to evaluate and
>> check it for
>> each row. It works, but only partially:
> ...
>> [In fact, you can move out out loop not only *whole* constant WHERE, but
>> also
>> all constant AND terms of WHERE, like this:
>> SELECT * FROM t WHERE const1 AND notconst AND const2 ->
>> SELECT * FROM (SELECT * FROM t WHERE notconst) WHERE const1 AND const2
>> I'll take a shot on that later.]
> Here it goes.
>
> Prerequisite: previous patch.
> Passes quick regression test (make test).
> Possible problem: short-circuits evaluation. Should not be a problem,
> IMO, as only
> constants references? Please verify.
Ping.
>>> Ping.
>> Ping.
>> For convenience all 3 patches collected below (needed no change for 3.7.11).
>
> Ping. Over 2 years passed since this patch series was first posted.
> Updated patch series for 3.8.1 below.
Ping. Same patch series refreshed for 3.8.2 with minor change.
--
The author or authors of this code dedicate any and all copyright interest
in this code to the public domain. We make this dedication for the benefit
of the public at large and to the detriment of our heirs and successors.
We intend this dedication to be an overt act of relinquishment in perpetuity
of all present and future rights to this code under copyright law.
Signed-off-by: Yuriy M. Kaminskiy
Part 1: Move whereSplit() to unbreak constant condition elimination.
(this is very obvious fix: only effect of "Special case" is pWhere assignment,
but pWhere value is only used in whereSplit call *above* of "Special case"; this
whole "Special case" is expensive no-op now)
Test case:
CREATE TABLE t (i, j, k);
EXPLAIN SELECT * FROM t WHERE 11;
Index: sqlite3-3.8.2/src/where.c
===
--- sqlite3-3.8.2.orig/src/where.c 2014-01-02 16:18:24.0 +0400
+++ sqlite3-3.8.2/src/where.c 2014-01-02 17:10:24.0 +0400
@@ -5423,7 +5423,6 @@ WhereInfo *sqlite3WhereBegin(
*/
initMaskSet(pMaskSet);
whereClauseInit(&pWInfo->sWC, pWInfo);
- whereSplit(&pWInfo->sWC, pWhere, TK_AND);
sqlite3CodeVerifySchema(pParse, -1); /* Insert the cookie verifier Goto */
/* Special case: a WHERE clause that is constant. Evaluate the
@@ -5434,6 +5433,8 @@ WhereInfo *sqlite3WhereBegin(
pWhere = 0;
}
+ whereSplit(&pWInfo->sWC, pWhere, TK_AND);
+
/* Special case: No FROM clause
*/
if( nTabList==0 ){
===
Part 2: optimize "WHERE const AND notconst" too
(trivial generalization of "Special case")
Test case:
EXPLAIN SELECT * FROM t WHERE 11 AND 12 AND i AND 13 AND j AND 14;
Index: sqlite3-3.8.1/src/where.c
===
--- sqlite3-3.8.1.orig/src/where.c 2013-11-03 23:27:05.0 +0400
+++ sqlite3-3.8.1/src/where.c 2013-11-03 23:27:59.0 +0400
@@ -5739,6 +5739,24 @@ WhereInfo *sqlite3WhereBegin(
whereSplit(&pWInfo->sWC, pWhere, TK_AND);
+ {
+/* Move const in "WHERE const AND notconst" out of internal loop */
+int i, j;
+WhereClause * const pWC = &pWInfo->sWC;
+
+for(j=i=0; inTerm; i++){
+ if( nTabList==0 || sqlite3ExprIsConstantNotJoin(pWC->a[i].pExpr) ){
+sqlite3ExprIfFalse(pParse, pWC->a[i].pExpr, pWInfo->iBreak,
SQLITE_JUMPIFNULL);
+continue;
+ }
+ if( j!=i )
+pWC->a[j]=pWC->a[i];
+ j++;
+}
+/* XXX if (i != j) memset(&(pWC->a[j]), 0, (i-j)*sizeof(pWC->a[0])); */
+pWC->nTerm -= i-j;
+ }
+
/* Special case: No FROM clause
*/
if( nTabList==0 ){
===
Part 3: Remove now-redundant sqlite3ExprIsConstantNotJoin call.
Index: sqlite3-3.8.2/src/where.c
===
--- sqlite3-3.8.2.orig/src/where.c 2014-01-02 17:10:47.0 +0400
+++ sqlite3-3.8.2/src/where.c 2014-01-02 17:11:54.0 +0400
@@ -5423,20 +5423,13 @@ WhereInfo *sqlite3WhereBegin(
*/
initMaskSet(pMaskSet);
whereClauseInit(&pWInfo->sWC, pWInfo);
- sqlite3CodeVerifySchema(pParse, -1); /* Insert the cookie verifier Goto */
-
- /* Special case: a WHERE clause that is constant. Evaluate the
- ** expression and either jump over all of the code or fall thru.
- */
- if( pWhere && (nTabList==0 || sqlite3ExprIsConstantNotJoin(pWhere)) ){
-sqlite3ExprIfFalse(pParse, pWhere, pWInfo->iBreak, SQLITE_JUMPIFNULL);
-pWhere = 0;
- }
-
whereSplit(&pWInfo->sWC, pWhere, TK_AND);
+ sqlite3CodeVerifySchema(pParse, -1); /* Insert the cookie verifier Goto */
{
-/* Move co
