Index: src/expr.c ================================================================== --- src/expr.c +++ src/expr.c @@ -139,18 +139,10 @@ CollSeq *pColl = 0; Expr *p = pExpr; while( p ){ int op = p->op; if( p->flags & EP_Generic ) break; - if( op==TK_CAST || op==TK_UPLUS ){ - p = p->pLeft; - continue; - } - if( op==TK_COLLATE || (op==TK_REGISTER && p->op2==TK_COLLATE) ){ - pColl = sqlite3GetCollSeq(pParse, ENC(db), 0, p->u.zToken); - break; - } if( (op==TK_AGG_COLUMN || op==TK_COLUMN || op==TK_REGISTER || op==TK_TRIGGER) && p->pTab!=0 ){ /* op==TK_REGISTER && p->pTab!=0 happens when pExpr was originally @@ -159,10 +151,18 @@ if( j>=0 ){ const char *zColl = p->pTab->aCol[j].zColl; pColl = sqlite3FindCollSeq(db, ENC(db), zColl, 0); } break; + } + if( op==TK_CAST || op==TK_UPLUS ){ + p = p->pLeft; + continue; + } + if( op==TK_COLLATE || (op==TK_REGISTER && p->op2==TK_COLLATE) ){ + pColl = sqlite3GetCollSeq(pParse, ENC(db), 0, p->u.zToken); + break; } if( p->flags & EP_Collate ){ if( p->pLeft && (p->pLeft->flags & EP_Collate)!=0 ){ p = p->pLeft; }else{ @@ -1837,10 +1837,13 @@ case TK_AGG_COLUMN: testcase( pExpr->op==TK_ID ); 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; } /* Fall through */ case TK_IF_NULL_ROW: @@ -1925,11 +1928,11 @@ ** it constant. */ for(i=0; inExpr; i++){ 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; } } } @@ -3579,10 +3582,13 @@ } /* Otherwise, fall thru into the TK_COLUMN case */ } case TK_COLUMN: { int iTab = pExpr->iTable; + if( ExprHasProperty(pExpr, EP_FixedCol) ){ + return sqlite3ExprCodeTarget(pParse, pExpr->pLeft,target); + } if( iTab<0 ){ if( pParse->iSelfTab<0 ){ /* Generating CHECK constraints or inserting into partial index */ return pExpr->iColumn - pParse->iSelfTab; }else{ @@ -4940,11 +4946,12 @@ } } 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 ); if( pA->op!=TK_STRING && pA->op!=TK_TRUEFALSE ){ if( pA->iColumn!=pB->iColumn ) return 2; Index: src/main.c ================================================================== --- src/main.c +++ src/main.c @@ -907,10 +907,19 @@ rc = nKey1 - nKey2; } } return rc; } + +/* +** Return true if CollSeq is the default built-in BINARY. +*/ +int sqlite3IsBinary(const CollSeq *p){ + assert( p==0 || p->xCmp!=binCollFunc || p->pUser!=0 + || strcmp(p->zName,"BINARY")==0 ); + return p==0 || (p->xCmp==binCollFunc && p->pUser==0); +} /* ** Another built-in collating sequence: NOCASE. ** ** This collating sequence is intended to be used for "case independent Index: src/select.c ================================================================== --- src/select.c +++ src/select.c @@ -4072,11 +4072,172 @@ return 1; } #endif /* !defined(SQLITE_OMIT_SUBQUERY) || !defined(SQLITE_OMIT_VIEW) */ +/* +** 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 { + 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 VALUE */ +}; +/* +** Add a new entry to the pConst object +*/ +static void constInsert( + WhereConst *pConst, + Expr *pColumn, + Expr *pValue +){ + + pConst->nConst++; + pConst->apExpr = sqlite3DbReallocOrFree(pConst->pParse->db, pConst->apExpr, + pConst->nConst*2*sizeof(Expr*)); + if( pConst->apExpr==0 ){ + pConst->nConst = 0; + }else{ + if( ExprHasProperty(pValue, EP_FixedCol) ) pValue = pValue->pLeft; + pConst->apExpr[pConst->nConst*2-2] = pColumn; + pConst->apExpr[pConst->nConst*2-1] = pValue; + } +} + +/* +** 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; + if( pExpr==0 ) return; + if( ExprHasProperty(pExpr, EP_FromJoin) ) return; + if( pExpr->op==TK_AND ){ + findConstInWhere(pConst, pExpr->pRight); + findConstInWhere(pConst, pExpr->pLeft); + return; + } + if( pExpr->op!=TK_EQ ) return; + pRight = pExpr->pRight; + pLeft = pExpr->pLeft; + assert( pRight!=0 ); + assert( pLeft!=0 ); + if( pRight->op==TK_COLUMN + && !ExprHasProperty(pRight, EP_FixedCol) + && sqlite3ExprIsConstant(pLeft) + && sqlite3IsBinary(sqlite3BinaryCompareCollSeq(pConst->pParse,pLeft,pRight)) + ){ + constInsert(pConst, pRight, pLeft); + }else + if( pLeft->op==TK_COLUMN + && !ExprHasProperty(pLeft, EP_FixedCol) + && sqlite3ExprIsConstant(pRight) + && sqlite3IsBinary(sqlite3BinaryCompareCollSeq(pConst->pParse,pLeft,pRight)) + ){ + constInsert(pConst, pLeft, pRight); + } +} + +/* +** This is a Walker expression callback. pExpr is a candidate expression +** to be replaced by a value. If pExpr is equivalent to one of the +** columns named in pWalker->u.pConst, then overwrite it with its +** corresponding value. +*/ +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. Add the EP_FixedCol property */ + pConst->nChng++; + ExprClearProperty(pExpr, EP_Leaf); + ExprSetProperty(pExpr, EP_FixedCol); + assert( pExpr->pLeft==0 ); + pExpr->pLeft = sqlite3ExprDup(pConst->pParse->db, pConst->apExpr[i*2+1], 0); + break; + } + return WRC_Prune; +} + +/* +** The WHERE-clause constant propagation optimization. +** +** If the WHERE clause contains terms of the form COLUMN=CONSTANT or +** 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 within the WHERE clause. +** +** For example, the query: +** +** SELECT * FROM t1, t2, t3 WHERE t1.a=39 AND t2.b=t1.a AND t3.c=t2.b +** +** Is transformed into +** +** 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 */ + Select *p /* The query in which to propagate constants */ +){ + WhereConst x; + Walker w; + int nChng = 0; + x.pParse = pParse; + do{ + x.nConst = 0; + x.nChng = 0; + x.apExpr = 0; + findConstInWhere(&x, p->pWhere); + if( x.nConst ){ + memset(&w, 0, sizeof(w)); + w.pParse = pParse; + w.xExprCallback = propagateConstantExprRewrite; + w.xSelectCallback = sqlite3SelectWalkNoop; + w.xSelectCallback2 = 0; + w.walkerDepth = 0; + w.u.pConst = &x; + sqlite3WalkExpr(&w, p->pWhere); + sqlite3DbFree(x.pParse->db, x.apExpr); + nChng += x.nChng; + } + }while( x.nChng ); + return nChng; +} #if !defined(SQLITE_OMIT_SUBQUERY) || !defined(SQLITE_OMIT_VIEW) /* ** Make copies of relevant WHERE clause terms of the outer query into ** the WHERE clause of subquery. Example: @@ -5596,10 +5757,29 @@ #endif if( p->pNext==0 ) ExplainQueryPlanPop(pParse); return rc; } #endif + + /* Do the WHERE-clause constant propagation optimization if this is + ** a join. No need to speed time on this operation for non-join queries + ** as the equivalent optimization will be handled by query planner in + ** sqlite3WhereBegin(). + */ + if( pTabList->nSrc>1 + && OptimizationEnabled(db, SQLITE_PropagateConst) + && propagateConstants(pParse, p) + ){ +#if SELECTTRACE_ENABLED + if( sqlite3SelectTrace & 0x100 ){ + SELECTTRACE(0x100,pParse,p,("After constant propagation:\n")); + sqlite3TreeViewSelect(0, p, 0); + } +#endif + }else{ + SELECTTRACE(0x100,pParse,p,("Constant propagation not helpful\n")); + } /* For each term in the FROM clause, do two things: ** (1) Authorized unreferenced tables ** (2) Generate code for all sub-queries */ Index: src/sqliteInt.h ================================================================== --- src/sqliteInt.h +++ src/sqliteInt.h @@ -1582,10 +1582,11 @@ #define SQLITE_Stat34 0x0800 /* Use STAT3 or STAT4 data */ /* TH3 expects the Stat34 ^^^^^^ value to be 0x0800. Don't change it */ #define SQLITE_PushDown 0x1000 /* The push-down optimization */ #define SQLITE_SimplifyJoin 0x2000 /* Convert LEFT JOIN to JOIN */ #define SQLITE_SkipScan 0x4000 /* Skip-scans */ +#define SQLITE_PropagateConst 0x8000 /* The constant propagation opt */ #define SQLITE_AllOpts 0xffff /* All optimizations */ /* ** Macros for testing whether or not optimizations are enabled or disabled. */ @@ -2476,11 +2477,11 @@ ** The following are the meanings of bits in the Expr.flags field. */ #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 "..." */ #define EP_InfixFunc 0x000080 /* True for an infix function: LIKE, GLOB, etc */ #define EP_Collate 0x000100 /* Tree contains a TK_COLLATE operator */ @@ -3434,10 +3435,11 @@ struct IdxCover *pIdxCover; /* Check for index coverage */ struct IdxExprTrans *pIdxTrans; /* Convert idxed expr to column */ ExprList *pGroupBy; /* GROUP BY clause */ Select *pSelect; /* HAVING to WHERE clause ctx */ struct WindowRewrite *pRewrite; /* Window rewrite context */ + struct WhereConst *pConst; /* WHERE clause constants */ } u; }; /* Forward declarations */ int sqlite3WalkExpr(Walker*, Expr*); @@ -4167,10 +4169,11 @@ #endif 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); int sqlite3ExprCollSeqMatch(Parse*,Expr*,Expr*); Expr *sqlite3ExprAddCollateToken(Parse *pParse, Expr*, const Token*, int); Index: src/treeview.c ================================================================== --- src/treeview.c +++ src/treeview.c @@ -372,10 +372,13 @@ sqlite3TreeViewLine(pView, "COLUMN(%d)%s", pExpr->iColumn, zFlgs); }else{ sqlite3TreeViewLine(pView, "{%d:%d}%s", pExpr->iTable, pExpr->iColumn, zFlgs); } + if( ExprHasProperty(pExpr, EP_FixedCol) ){ + sqlite3TreeViewExpr(pView, pExpr->pLeft, 0); + } break; } case TK_INTEGER: { if( pExpr->flags & EP_IntValue ){ sqlite3TreeViewLine(pView, "%d", pExpr->u.iValue); Index: src/where.c ================================================================== --- src/where.c +++ src/where.c @@ -3203,11 +3203,11 @@ int iTerm = pIdxInfo->aConstraint[iCons].iTermOffset; Expr *pX = pHidden->pWC->a[iTerm].pExpr; if( pX->pLeft ){ pC = sqlite3BinaryCompareCollSeq(pHidden->pParse, pX->pLeft, pX->pRight); } - zRet = (pC ? pC->zName : "BINARY"); + zRet = (pC ? pC->zName : sqlite3StrBINARY); } return zRet; } /* Index: src/wherecode.c ================================================================== --- src/wherecode.c +++ src/wherecode.c @@ -881,11 +881,11 @@ ** an access of the index rather than the original table. */ 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 */ sqlite3ExprCodeGetColumnOfTable( v, pExpr->pTab, pExpr->iTable, pExpr->iColumn, reg Index: src/whereexpr.c ================================================================== --- src/whereexpr.c +++ src/whereexpr.c @@ -857,11 +857,11 @@ && (!sqlite3IsNumericAffinity(aff1) || !sqlite3IsNumericAffinity(aff2)) ){ 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); } /* ** Recursively walk the expressions of a SELECT statement and generate @@ -1198,11 +1198,11 @@ if( c=='A'-1 ) isComplete = 0; c = sqlite3UpperToLower[c]; } *pC = c + 1; } - zCollSeqName = noCase ? "NOCASE" : "BINARY"; + zCollSeqName = noCase ? "NOCASE" : sqlite3StrBINARY; pNewExpr1 = sqlite3ExprDup(db, pLeft, 0); pNewExpr1 = sqlite3PExpr(pParse, TK_GE, sqlite3ExprAddCollateString(pParse,pNewExpr1,zCollSeqName), pStr1); transferJoinMarkings(pNewExpr1, pExpr); @@ -1448,11 +1448,11 @@ ** a bitmask indicating which tables are used in that expression ** tree. */ 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 ); return 0; } ADDED test/whereL.test Index: test/whereL.test ================================================================== --- /dev/null +++ test/whereL.test @@ -0,0 +1,70 @@ +# 2018-07-26 +# +# The author disclaims copyright to this source code. In place of +# a legal notice, here is a blessing: +# +# May you do good and not evil. +# May you find forgiveness for yourself and forgive others. +# May you share freely, never taking more than you give. +# +#*********************************************************************** +# This file implements regression tests for SQLite library. The +# focus of this file is testing the WHERE-clause constant propagation +# optimization. +# +set testdir [file dirname $argv0] +source $testdir/tester.tcl +set ::testprefix whereL + +do_execsql_test 100 { + CREATE TABLE t1(a INT PRIMARY KEY, b, c, d, e); + CREATE TABLE t2(a INT PRIMARY KEY, f, g, h, i); + CREATE TABLE t3(a INT PRIMARY KEY, j, k, l, m); + CREATE VIEW v4 AS SELECT * FROM t2 UNION ALL SELECT * FROM t3; +} +do_eqp_test 110 { + SELECT * FROM t1, v4 WHERE t1.a=?1 AND v4.a=t1.a; +} { + QUERY PLAN + |--MATERIALIZE xxxxxx + | `--COMPOUND QUERY + | |--LEFT-MOST SUBQUERY + | | `--SEARCH TABLE t2 USING INDEX sqlite_autoindex_t2_1 (a=?) + | `--UNION ALL + | `--SEARCH TABLE t3 USING INDEX sqlite_autoindex_t3_1 (a=?) + |--SCAN SUBQUERY xxxxxx + `--SEARCH TABLE t1 USING INDEX sqlite_autoindex_t1_1 (a=?) +} + +# The scan of the t1 table goes first since that enables the ORDER BY +# sort to be omitted. This would not be possible without constant +# propagation because without it the t1 table would depend on t3. +# +do_eqp_test 120 { + SELECT * FROM t1, t2, t3 + WHERE t1.a=t2.a AND t2.a=t3.j AND t3.j=5 + ORDER BY t1.a; +} { + QUERY PLAN + |--SEARCH TABLE t1 USING INDEX sqlite_autoindex_t1_1 (a=?) + |--SEARCH TABLE t2 USING INDEX sqlite_autoindex_t2_1 (a=?) + `--SCAN TABLE t3 +} + +# Constant propagation in the face of collating sequences: +# +do_execsql_test 200 { + CREATE TABLE c3(x COLLATE binary, y COLLATE nocase, z COLLATE binary); + CREATE INDEX c3x ON c3(x); + INSERT INTO c3 VALUES('ABC', 'ABC', 'abc'); + SELECT * FROM c3 WHERE x=y AND y=z AND z='abc'; +} {ABC ABC abc} + +# If the constants are blindly propagated, as shown in the following +# query, the wrong answer results: +# +do_execsql_test 201 { + SELECT * FROM c3 WHERE x='abc' AND y='abc' AND z='abc'; +} {} + +finish_test