From efad2e23668ea5cbd744b6abde43058de45fb53a Mon Sep 17 00:00:00 2001 From: drh Date: Fri, 27 Jul 2018 16:57:11 +0000 Subject: [PATCH] Constant propagation is now restricted to just the WHERE clause. The mechanism is changed to take affinity and collation into account. This seems to give correct answers. But the search for constant propagation costs 4 million cycles in the speed test. FossilOrigin-Name: 82c67efb723dba387964f690cd459b420e59e3367d9589016597a76531596391 --- manifest | 22 +++++++------- manifest.uuid | 2 +- src/expr.c | 23 +++++++++++++-- src/select.c | 76 +++++++++++++++++++++++++++++++++++-------------- src/sqliteInt.h | 3 +- src/treeview.c | 3 ++ src/wherecode.c | 2 +- src/whereexpr.c | 4 +-- 8 files changed, 94 insertions(+), 41 deletions(-) diff --git a/manifest b/manifest index 73c3e5b372..79cc142c4a 100644 --- a/manifest +++ b/manifest @@ -1,5 +1,5 @@ -C Add\sa\stest\scase\sdemonstrating\sthe\scollation\sproblem\swith\sconstant\spropagation. -D 2018-07-26T23:54:19.662 +C Constant\spropagation\sis\snow\srestricted\sto\sjust\sthe\sWHERE\sclause.\sThe\nmechanism\sis\schanged\sto\stake\saffinity\sand\scollation\sinto\saccount.\s\sThis\nseems\sto\sgive\scorrect\sanswers.\s\sBut\sthe\ssearch\sfor\sconstant\spropagation\ncosts\s4\smillion\scycles\sin\sthe\sspeed\stest. +D 2018-07-27T16:57:11.322 F .fossil-settings/empty-dirs dbb81e8fc0401ac46a1491ab34a7f2c7c0452f2f06b54ebb845d024ca8283ef1 F .fossil-settings/ignore-glob 35175cdfcf539b2318cb04a9901442804be81cd677d8b889fcc9149c21f239ea F Makefile.in 0a3a6c81e6fcb969ff9106e882f0a08547014ba463cb6beca4c4efaecc924ee6 @@ -450,7 +450,7 @@ F src/date.c ebe1dc7c8a347117bb02570f1a931c62dd78f4a2b1b516f4837d45b7d6426957 F src/dbpage.c 4aa7f26198934dbd002e69418220eae3dbc71b010bbac32bd78faf86b52ce6c3 F src/dbstat.c edabb82611143727511a45ca0859b8cd037851ebe756ae3db289859dd18b6f91 F src/delete.c 4c8c7604277a2041647f96b78f4b9a47858e9217e4fb333d35e7b5ab32c5b57f -F src/expr.c 8187c1be1003230f027bfc5f5a9830aa43d55beb67d87f4a2589d125749fbcfd +F src/expr.c af489eb4dac501d06c1f05b9f27f7fc37a05582b9f9b7724e0e1ccc78ae8a530 F src/fault.c 460f3e55994363812d9d60844b2a6de88826e007 F src/fkey.c b1da9ef8dc834603bb0d28972378a7ce65897847f9a1e89ab800bbdf24c788ee F src/func.c 7c288b4ce309b5a8b8473514b88e1f8e69a80134509a8c0db8e39c858e367e7f @@ -498,12 +498,12 @@ F src/printf.c 7f6f3cba8e0c49c19e30a1ff4e9aeda6e06814dcbad4b664a69e1b6cb6e7e365 F src/random.c 80f5d666f23feb3e6665a6ce04c7197212a88384 F src/resolve.c 797088662ed61102485e3070ba3b3f7828bd5ef6a588223ba6865d77d52f6cea F src/rowset.c 7b7e7e479212e65b723bf40128c7b36dc5afdfac -F src/select.c 81c6517a8d7b6aae805aaa4171187390f72988d1ceec343ad2f51be09513b289 +F src/select.c 7d2a980be754def09d3458c9eba5ac781ec2962c3415e6ce6d3e00ca100468f8 F src/shell.c.in f6ebd05c461805a7c708333cd645e74e0a93560d2118f5adb73a75d8c9cf6b01 F src/sqlite.h.in c6451bb876adced3aba5b1682c6317d215c5eceaba21a6ce979e71a0b8d0bf95 F src/sqlite3.rc 5121c9e10c3964d5755191c80dd1180c122fc3a8 F src/sqlite3ext.h 9887b27e69c01e79c2cbe74ef73bf01af5b5703d6a7f0a4371e386d7249cb1c7 -F src/sqliteInt.h 0da0d929642cacf99963e406d34e2e3be891a30168f99aefc1cb81c2c545a09b +F src/sqliteInt.h fafe020e6fa39964ffff8ff1b48e2a7f0b394e03c722a746629751d2d31721ae F src/sqliteLimit.h 1513bfb7b20378aa0041e7022d04acb73525de35b80b252f1b83fedb4de6a76b F src/status.c 46e7aec11f79dad50965a5ca5fa9de009f7d6bde08be2156f1538a0a296d4d0e F src/table.c b46ad567748f24a326d9de40e5b9659f96ffff34 @@ -562,7 +562,7 @@ F src/test_window.c cdae419fdcea5bad6dcd9368c685abdad6deb59e9fc8b84b153de513d394 F src/test_wsd.c 41cadfd9d97fe8e3e4e44f61a4a8ccd6f7ca8fe9 F src/threads.c 4ae07fa022a3dc7c5beb373cf744a85d3c5c6c3c F src/tokenize.c 01e96d1b639c3eb0b9ef90616e766d453935c554f1f7aa86b6db937b79554b97 -F src/treeview.c 26c5674083674377b0f41737647802e93ac31f1da89c9b9648501d8a34a44698 +F src/treeview.c e7a7f90552bb418533cdd0309b5eb71d4effa50165b880fc8c2001e613577e5f F src/trigger.c 4ace6d1d5ba9a89822deb287317f33c810440526eafe185c2d8a48c31df1e995 F src/update.c 7b7c768dc415a8d2eb9fd2cea8b524cb29cf354f319700e22f94f262d3f507cb F src/upsert.c 47edd408cc73f8d3c00a140550d1ad180b407c146285947969dd09874802bf88 @@ -585,8 +585,8 @@ F src/wal.h 8de5d2d3de0956d6f6cb48c83a4012d5f227b8fe940f3a349a4b7e85ebcb492a F src/walker.c ba7225773931760cf60bf22f34d0cce2588df7ce5ce0f215a52eb88234b55ac4 F src/where.c 2d313b446758317b60626763d0e1285e04b04c061ce94945dcfffad9525badc1 F src/whereInt.h b90ef9b9707ef750eab2a7a080c48fb4900315033274689def32d0cf5a81ebe4 -F src/wherecode.c fe23a55294b4c94bf658d2a6eb7996170dd563bf33af4c3e5d71aff3483e4b08 -F src/whereexpr.c 571618c67a3eb5ce0f1158c2792c1aee9b4a4a264392fc4fb1b35467f80abf9a +F src/wherecode.c 2c552dfe50d06e0916dbd49a180e4bf0accfce6d17d46a2dfeea8f75d2b5861b +F src/whereexpr.c 7d30c744f37e8bd53811f88fd1d949f6145d24ce77a6f51b252e2b903dc4434e F src/window.c c61434ce7e35b7d76b3321dec39e10e79061c10eed1e3d7976c87dbdd77aefb5 F test/8_3_names.test ebbb5cd36741350040fd28b432ceadf495be25b2 F test/affinity2.test a6d901b436328bd67a79b41bb0ac2663918fe3bd @@ -1753,7 +1753,7 @@ F vsixtest/vsixtest.tcl 6a9a6ab600c25a91a7acc6293828957a386a8a93 F vsixtest/vsixtest.vcxproj.data 2ed517e100c66dc455b492e1a33350c1b20fbcdc F vsixtest/vsixtest.vcxproj.filters 37e51ffedcdb064aad6ff33b6148725226cd608e F vsixtest/vsixtest_TemporaryKey.pfx e5b1b036facdb453873e7084e1cae9102ccc67a0 -P 57eb2abd5b270d65be5e0f138f0d46899fa6091df3ba20b0ea7ef04244a15d48 -R 4901cf7d6c93780d74bf2f77c4b5611e +P 50add839fd95665bd67a6ae5de8346fd09e83904bbcbad26fad280dff86d9e93 +R 50f5324ffb4955a3d4663001ed61326d U drh -Z e93689647fb1d0f73e5b2a94dfb414a1 +Z f7259f5866467f9069a6566db546a485 diff --git a/manifest.uuid b/manifest.uuid index bcb4361963..f10ad29d73 100644 --- a/manifest.uuid +++ b/manifest.uuid @@ -1 +1 @@ -50add839fd95665bd67a6ae5de8346fd09e83904bbcbad26fad280dff86d9e93 \ No newline at end of file +82c67efb723dba387964f690cd459b420e59e3367d9589016597a76531596391 \ No newline at end of file diff --git a/src/expr.c b/src/expr.c index 6e5100a224..69270959fb 100644 --- a/src/expr.c +++ b/src/expr.c @@ -328,6 +328,15 @@ CollSeq *sqlite3BinaryCompareCollSeq( return pColl; } +/* +** Return true if CollSeq is the default built-in BINARY. +*/ +int sqlite3IsBinary(const CollSeq *p){ + if( p==0 ) return 1; + if( sqlite3_stricmp(p->zName,"BINARY")==0 ) return 1; + return 0; +} + /* ** Generate code for a comparison operator. */ @@ -1839,6 +1848,9 @@ static int exprNodeIsConstant(Walker *pWalker, Expr *pExpr){ testcase( pExpr->op==TK_COLUMN ); testcase( pExpr->op==TK_AGG_FUNCTION ); testcase( pExpr->op==TK_AGG_COLUMN ); + if( ExprHasProperty(pExpr, EP_FixedCol) ){ + return WRC_Continue; + } if( pWalker->eCode==3 && pExpr->iTable==pWalker->u.iCur ){ return WRC_Continue; } @@ -1927,7 +1939,7 @@ static int exprNodeIsConstantOrGroupBy(Walker *pWalker, Expr *pExpr){ Expr *p = pGroupBy->a[i].pExpr; if( sqlite3ExprCompare(0, pExpr, p, -1)<2 ){ CollSeq *pColl = sqlite3ExprNNCollSeq(pWalker->pParse, p); - if( sqlite3_stricmp("BINARY", pColl->zName)==0 ){ + if( sqlite3IsBinary(pColl) ){ return WRC_Prune; } } @@ -3581,6 +3593,10 @@ expr_code_doover: } case TK_COLUMN: { int iTab = pExpr->iTable; + if( ExprHasProperty(pExpr, EP_FixedCol) ){ + pExpr = pExpr->pLeft; + goto expr_code_doover; + } if( iTab<0 ){ if( pParse->iSelfTab<0 ){ /* Generating CHECK constraints or inserting into partial index */ @@ -4935,14 +4951,15 @@ int sqlite3ExprCompare(Parse *pParse, Expr *pA, Expr *pB, int iTab){ if( sqlite3StrICmp(pA->u.zToken,pB->u.zToken)!=0 ) return 2; }else if( pA->op==TK_COLLATE ){ if( sqlite3_stricmp(pA->u.zToken,pB->u.zToken)!=0 ) return 2; - }else if( pA->op!=TK_UPLUS && strcmp(pA->u.zToken,pB->u.zToken)!=0 ){ + }else if( strcmp(pA->u.zToken,pB->u.zToken)!=0 ){ return 2; } } if( (pA->flags & EP_Distinct)!=(pB->flags & EP_Distinct) ) return 2; if( ALWAYS((combinedFlags & EP_TokenOnly)==0) ){ if( combinedFlags & EP_xIsSelect ) return 2; - if( sqlite3ExprCompare(pParse, pA->pLeft, pB->pLeft, iTab) ) return 2; + if( (combinedFlags & EP_FixedCol)==0 + && sqlite3ExprCompare(pParse, pA->pLeft, pB->pLeft, iTab) ) return 2; if( sqlite3ExprCompare(pParse, pA->pRight, pB->pRight, iTab) ) return 2; if( sqlite3ExprListCompare(pA->x.pList, pB->x.pList, iTab) ) return 2; assert( (combinedFlags & EP_Reduced)==0 ); diff --git a/src/select.c b/src/select.c index 2060524c49..d74af40989 100644 --- a/src/select.c +++ b/src/select.c @@ -4075,15 +4075,15 @@ static int flattenSubquery( #endif /* !defined(SQLITE_OMIT_SUBQUERY) || !defined(SQLITE_OMIT_VIEW) */ /* -** A structure to keep track of all of the column values that must be -** constant in a WHERE clause. +** A structure to keep track of all of the column values that fixed to +** a known value due to WHERE clause constraints of the form COLUMN=VALUE. */ typedef struct WhereConst WhereConst; struct WhereConst { - sqlite3 *db; /* Database pointer, used by sqlite3DbRealloc() */ + Parse *pParse; /* Parsing context */ int nConst; /* Number for COLUMN=CONSTANT terms */ int nChng; /* Number of times a constant is propagated */ - Expr **apExpr; /* [i*2] is COLUMN and [i*2+1] is CONSTANT */ + Expr **apExpr; /* [i*2] is COLUMN and [i*2+1] is VALUE */ }; /* @@ -4095,23 +4095,26 @@ static void constInsert( Expr *pValue ){ pConst->nConst++; - pConst->apExpr = sqlite3DbReallocOrFree(pConst->db, pConst->apExpr, + pConst->apExpr = sqlite3DbReallocOrFree(pConst->pParse->db, pConst->apExpr, pConst->nConst*2*sizeof(Expr*)); if( pConst->apExpr==0 ){ pConst->nConst = 0; }else{ - while( pValue->op==TK_UPLUS ) pValue = pValue->pLeft; + if( ExprHasProperty(pValue, EP_FixedCol) ) pValue = pValue->pLeft; pConst->apExpr[pConst->nConst*2-2] = pColumn; pConst->apExpr[pConst->nConst*2-1] = pValue; } } /* -** Find all instances of COLUMN=CONSTANT or CONSTANT=COLUMN in pExpr that -** must be true (that are part of the AND-connected terms) and add each -** to pConst. +** Find all terms of COLUMN=VALUE or VALUE=COLUMN in pExpr where VALUE +** is a constant expression and where the term must be true because it +** is part of the AND-connected terms of the expression. For each term +** found, add it to the pConst structure. */ static void findConstInWhere(WhereConst *pConst, Expr *pExpr){ + Expr *pRight, *pLeft; + CollSeq *pColl; if( pExpr==0 ) return; if( ExprHasProperty(pExpr, EP_FromJoin) ) return; if( pExpr->op==TK_AND ){ @@ -4120,13 +4123,22 @@ static void findConstInWhere(WhereConst *pConst, Expr *pExpr){ return; } if( pExpr->op!=TK_EQ ) return; - assert( pExpr->pRight!=0 ); - assert( pExpr->pLeft!=0 ); - if( pExpr->pRight->op==TK_COLUMN && sqlite3ExprIsConstant(pExpr->pLeft) ){ - constInsert(pConst, pExpr->pRight, pExpr->pLeft); + pRight = pExpr->pRight; + pLeft = pExpr->pLeft; + assert( pRight!=0 ); + assert( pLeft!=0 ); + pColl = sqlite3BinaryCompareCollSeq(pConst->pParse, pLeft, pRight); + if( !sqlite3IsBinary(pColl) ) return; + if( pRight->op==TK_COLUMN + && !ExprHasProperty(pRight, EP_FixedCol) + && sqlite3ExprIsConstant(pLeft) + ){ + constInsert(pConst, pRight, pLeft); }else - if( pExpr->pLeft->op==TK_COLUMN && sqlite3ExprIsConstant(pExpr->pRight) ){ - constInsert(pConst, pExpr->pLeft, pExpr->pRight); + if( pLeft->op==TK_COLUMN + && !ExprHasProperty(pLeft, EP_FixedCol) + && sqlite3ExprIsConstant(pRight) ){ + constInsert(pConst, pLeft, pRight); } } @@ -4140,17 +4152,19 @@ static int propagateConstantExprRewrite(Walker *pWalker, Expr *pExpr){ int i; WhereConst *pConst; if( pExpr->op!=TK_COLUMN ) return WRC_Continue; + if( ExprHasProperty(pExpr, EP_FixedCol) ) return WRC_Continue; pConst = pWalker->u.pConst; for(i=0; inConst; i++){ Expr *pColumn = pConst->apExpr[i*2]; if( pColumn==pExpr ) continue; if( pColumn->iTable!=pExpr->iTable ) continue; if( pColumn->iColumn!=pExpr->iColumn ) continue; - /* A match is found. Transform the COLUMN into a CONSTANT */ + /* A match is found. Add the EP_FixedCol property */ pConst->nChng++; ExprClearProperty(pExpr, EP_Leaf); - pExpr->op = TK_UPLUS; - pExpr->pLeft = sqlite3ExprDup(pConst->db, pConst->apExpr[i*2+1], 0); + ExprSetProperty(pExpr, EP_FixedCol); + assert( pExpr->pLeft==0 ); + pExpr->pLeft = sqlite3ExprDup(pConst->pParse->db, pConst->apExpr[i*2+1], 0); break; } return WRC_Prune; @@ -4163,7 +4177,7 @@ static int propagateConstantExprRewrite(Walker *pWalker, Expr *pExpr){ ** CONSTANT=COLUMN that must be tree (in other words, if the terms top-level ** AND-connected terms that are not part of a ON clause from a LEFT JOIN) ** then throughout the query replace all other occurrences of COLUMN -** with CONSTANT. +** with CONSTANT within the WHERE clause. ** ** For example, the query: ** @@ -4174,6 +4188,24 @@ static int propagateConstantExprRewrite(Walker *pWalker, Expr *pExpr){ ** SELECT * FROM t1, t2, t3 WHERE t1.a=39 AND t2.b=39 AND t3.c=39 ** ** Return true if any transformations where made and false if not. +** +** Implementation note: Constant propagation is tricky due to affinity +** and collating sequence interactions. Consider this example: +** +** CREATE TABLE t1(a INT,b TEXT); +** INSERT INTO t1 VALUES(123,'0123'); +** SELECT * FROM t1 WHERE a=123 AND b=a; +** SELECT * FROM t1 WHERE a=123 AND b=123; +** +** The two SELECT statements above should return different answers. b=a +** is alway true because the comparison uses numeric affinity, but b=123 +** is false because it uses text affinity and '0123' is not the same as '123'. +** To work around this, the expression tree is not actually changed from +** "b=a" to "b=123" but rather the "a" in "b=a" is tagged with EP_FixedCol +** and the "123" value is hung off of the pLeft pointer. Code generator +** routines know to generate the constant "123" instead of looking up the +** column value. Also, to avoid collation problems, this optimization is +** only attempted if the "a=123" term uses the default BINARY collation. */ static int propagateConstants( Parse *pParse, /* The parsing context */ @@ -4182,7 +4214,7 @@ static int propagateConstants( WhereConst x; Walker w; int nChng = 0; - x.db = pParse->db; + x.pParse = pParse; do{ x.nConst = 0; x.nChng = 0; @@ -4196,8 +4228,8 @@ static int propagateConstants( w.xSelectCallback2 = 0; w.walkerDepth = 0; w.u.pConst = &x; - sqlite3WalkSelect(&w, p); - sqlite3DbFree(x.db, x.apExpr); + sqlite3WalkExpr(&w, p->pWhere); + sqlite3DbFree(x.pParse->db, x.apExpr); nChng += x.nChng; } }while( x.nChng ); diff --git a/src/sqliteInt.h b/src/sqliteInt.h index 9dbe683398..7c4d46a40a 100644 --- a/src/sqliteInt.h +++ b/src/sqliteInt.h @@ -2479,7 +2479,7 @@ struct Expr { #define EP_FromJoin 0x000001 /* Originates in ON/USING clause of outer join */ #define EP_Agg 0x000002 /* Contains one or more aggregate functions */ #define EP_HasFunc 0x000004 /* Contains one or more functions of any kind */ - /* 0x000008 // available for use */ +#define EP_FixedCol 0x000008 /* TK_Column with a known fixed value */ #define EP_Distinct 0x000010 /* Aggregate function with DISTINCT keyword */ #define EP_VarSelect 0x000020 /* pSelect is correlated, not constant */ #define EP_DblQuoted 0x000040 /* token.z was originally in "..." */ @@ -4171,6 +4171,7 @@ int sqlite3MemdbInit(void); const char *sqlite3ErrStr(int); int sqlite3ReadSchema(Parse *pParse); CollSeq *sqlite3FindCollSeq(sqlite3*,u8 enc, const char*,int); +int sqlite3IsBinary(const CollSeq*); CollSeq *sqlite3LocateCollSeq(Parse *pParse, const char*zName); CollSeq *sqlite3ExprCollSeq(Parse *pParse, Expr *pExpr); CollSeq *sqlite3ExprNNCollSeq(Parse *pParse, Expr *pExpr); diff --git a/src/treeview.c b/src/treeview.c index 7605fa2cb3..cde776d0fa 100644 --- a/src/treeview.c +++ b/src/treeview.c @@ -374,6 +374,9 @@ void sqlite3TreeViewExpr(TreeView *pView, const Expr *pExpr, u8 moreToFollow){ sqlite3TreeViewLine(pView, "{%d:%d}%s", pExpr->iTable, pExpr->iColumn, zFlgs); } + if( ExprHasProperty(pExpr, EP_FixedCol) ){ + sqlite3TreeViewExpr(pView, pExpr->pLeft, 0); + } break; } case TK_INTEGER: { diff --git a/src/wherecode.c b/src/wherecode.c index 3bb220d2ed..1f24c578b3 100644 --- a/src/wherecode.c +++ b/src/wherecode.c @@ -883,7 +883,7 @@ static int codeCursorHintIsOrFunction(Walker *pWalker, Expr *pExpr){ static int codeCursorHintFixExpr(Walker *pWalker, Expr *pExpr){ int rc = WRC_Continue; struct CCurHint *pHint = pWalker->u.pCCurHint; - if( pExpr->op==TK_COLUMN ){ + if( pExpr->op==TK_COLUMN && !ExprHasProperty(pExpr, EP_FixedCol) ){ if( pExpr->iTable!=pHint->iTabCur ){ Vdbe *v = pWalker->pParse->pVdbe; int reg = ++pWalker->pParse->nMem; /* Register for column value */ diff --git a/src/whereexpr.c b/src/whereexpr.c index 6f6e660ad2..4abadb1878 100644 --- a/src/whereexpr.c +++ b/src/whereexpr.c @@ -859,7 +859,7 @@ static int termIsEquivalence(Parse *pParse, Expr *pExpr){ return 0; } pColl = sqlite3BinaryCompareCollSeq(pParse, pExpr->pLeft, pExpr->pRight); - if( pColl==0 || sqlite3StrICmp(pColl->zName, "BINARY")==0 ) return 1; + if( sqlite3IsBinary(pColl) ) return 1; return sqlite3ExprCollSeqMatch(pParse, pExpr->pLeft, pExpr->pRight); } @@ -1450,7 +1450,7 @@ void sqlite3WhereClauseClear(WhereClause *pWC){ */ Bitmask sqlite3WhereExprUsageNN(WhereMaskSet *pMaskSet, Expr *p){ Bitmask mask; - if( p->op==TK_COLUMN ){ + if( p->op==TK_COLUMN && !ExprHasProperty(p, EP_FixedCol) ){ return sqlite3WhereGetMask(pMaskSet, p->iTable); }else if( ExprHasProperty(p, EP_TokenOnly|EP_Leaf) ){ assert( p->op!=TK_IF_NULL_ROW ); -- 2.47.2