Initial implementation of the WHERE-clause constant propagation optimization.
FossilOrigin-Name: 2fb82ad8ebb6434438c0d235b1239444fb08c8711cea2c5a9ed955fedd0acdec
diff --git a/src/select.c b/src/select.c
index dd8c89c..a0f140e 100644
--- a/src/select.c
+++ b/src/select.c
@@ -4074,7 +4074,134 @@
}
#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.
+*/
+typedef struct WhereConst WhereConst;
+struct WhereConst {
+ sqlite3 *db; /* Database pointer, used by sqlite3DbRealloc() */
+ 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 */
+};
+/*
+** Add a new entry to the pConst object
+*/
+static void constInsert(
+ WhereConst *pConst,
+ Expr *pColumn,
+ Expr *pValue
+){
+ pConst->nConst++;
+ pConst->apExpr = sqlite3DbReallocOrFree(pConst->db, pConst->apExpr,
+ pConst->nConst*2*sizeof(Expr*));
+ if( pConst->apExpr==0 ){
+ pConst->nConst = 0;
+ }else{
+ 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.
+*/
+static void findConstInWhere(WhereConst *pConst, Expr *pExpr){
+ 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;
+ assert( pExpr->pRight!=0 );
+ assert( pExpr->pLeft!=0 );
+ if( pExpr->pRight->op==TK_COLUMN && sqlite3ExprIsConstant(pExpr->pLeft) ){
+ constInsert(pConst, pExpr->pRight, pExpr->pLeft);
+ }else
+ if( pExpr->pLeft->op==TK_COLUMN && sqlite3ExprIsConstant(pExpr->pRight) ){
+ constInsert(pConst, pExpr->pLeft, pExpr->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;
+ pConst = pWalker->u.pConst;
+ for(i=0; i<pConst->nConst; 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 */
+ pConst->nChng++;
+ ExprClearProperty(pExpr, EP_Leaf);
+ pExpr->op = TK_UPLUS;
+ pExpr->pLeft = sqlite3ExprDup(pConst->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.
+**
+** 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.
+*/
+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.db = pParse->db;
+ 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;
+ sqlite3WalkSelect(&w, p);
+ sqlite3DbFree(x.db, x.apExpr);
+ nChng += x.nChng;
+ }
+ }while( x.nChng );
+ return nChng;
+}
#if !defined(SQLITE_OMIT_SUBQUERY) || !defined(SQLITE_OMIT_VIEW)
/*
@@ -5663,6 +5790,20 @@
*/
pParse->nHeight += sqlite3SelectExprHeight(p);
+ /* Do the constant propagation optimization */
+ if( 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 possible\n"));
+ }
+
/* Make copies of constant WHERE-clause terms in the outer query down
** inside the subquery. This can help the subquery to run more efficiently.
*/
diff --git a/src/sqliteInt.h b/src/sqliteInt.h
index 2c52dfe..9dbe683 100644
--- a/src/sqliteInt.h
+++ b/src/sqliteInt.h
@@ -1584,6 +1584,7 @@
#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 */
/*
@@ -3436,6 +3437,7 @@
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;
};