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 <[email protected]> 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 <[email protected]>
>>
>> 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.000000000 +0400
>> +++ sqlite3-3.8.2/src/where.c 2014-01-02 17:10:24.000000000 +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.000000000 +0400
>> +++ sqlite3-3.8.1/src/where.c 2013-11-03 23:27:59.000000000 +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; i<pWC->nTerm; 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.000000000 +0400
>> +++ sqlite3-3.8.2/src/where.c 2014-01-02 17:11:54.000000000 +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 const in "WHERE const AND notconst" out of internal loop */
>> + /* Special case: AND subterm of WHERE clause that is constant.
>> Evaluate the
>> + ** expression and either jump over all of the code or fall thru.
>> + */
>> int i, j;
>> WhereClause * const pWC = &pWInfo->sWC;
>>
>> _______________________________________________
>> sqlite-users mailing list
>> [email protected]
>> http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users
>>
>
>
>
_______________________________________________
sqlite-users mailing list
[email protected]
http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users
