/ Check-in [0fbd154e]
Login

Many hyperlinks are disabled.
Use anonymous login to enable hyperlinks.

Overview
Comment:Improved optimization of the AND and OR operators.
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA3-256: 0fbd154eb419b57b9c064c1f47346835d6324388b966b73f8a0122de065f08b1
User & Date: drh 2019-04-19 17:26:19
Context
2019-04-19
22:01
Increase the version number to 3.29 for the next development cycle. check-in: 6cf16703 user: drh tags: trunk
18:10
Mark two branches as unreachable. Oops - one of those branches was reachable via fuzzcheck tests. Closed-Leaf check-in: 9b888fcc user: drh tags: mistake
17:26
Improved optimization of the AND and OR operators. check-in: 0fbd154e user: drh tags: trunk
16:34
Fix a problem with renaming a table that starts with "sqlite". Fix for ticket [f00d7b65]. check-in: a2ead8aa user: dan tags: trunk
Changes
Hide Diffs Side-by-Side Diffs Ignore Whitespace Patch

Changes to src/expr.c.

  1804   1804   int sqlite3ExprTruthValue(const Expr *pExpr){
  1805   1805     assert( pExpr->op==TK_TRUEFALSE );
  1806   1806     assert( sqlite3StrICmp(pExpr->u.zToken,"true")==0
  1807   1807          || sqlite3StrICmp(pExpr->u.zToken,"false")==0 );
  1808   1808     return pExpr->u.zToken[4]==0;
  1809   1809   }
  1810   1810   
         1811  +/*
         1812  +** If pExpr is an AND or OR expression, try to simplify it by eliminating
         1813  +** terms that are always true or false.  Return the simplified expression.
         1814  +** Or return the original expression if no simplification is possible.
         1815  +**
         1816  +** Examples:
         1817  +**
         1818  +**     (x<10) AND true                =>   (x<10)
         1819  +**     (x<10) AND false               =>   false
         1820  +**     (x<10) AND (y=22 OR false)     =>   (x<10) AND (y=22)
         1821  +**     (x<10) AND (y=22 OR true)      =>   (x<10)
         1822  +**     (y=22) OR true                 =>   true
         1823  +*/
         1824  +Expr *sqlite3ExprSimplifiedAndOr(Expr *pExpr){
         1825  +  assert( pExpr!=0 );
         1826  +  if( pExpr->op==TK_AND || pExpr->op==TK_OR ){
         1827  +    Expr *pRight = sqlite3ExprSimplifiedAndOr(pExpr->pRight);
         1828  +    Expr *pLeft = sqlite3ExprSimplifiedAndOr(pExpr->pLeft);
         1829  +    if( ExprAlwaysTrue(pLeft) || ExprAlwaysFalse(pRight) ){
         1830  +      pExpr = pExpr->op==TK_AND ? pRight : pLeft;
         1831  +    }else if( ExprAlwaysTrue(pRight) || ExprAlwaysFalse(pLeft) ){
         1832  +      pExpr = pExpr->op==TK_AND ? pLeft : pRight;
         1833  +    }
         1834  +  }
         1835  +  return pExpr;
         1836  +}
         1837  +
  1811   1838   
  1812   1839   /*
  1813   1840   ** These routines are Walker callbacks used to check expressions to
  1814   1841   ** see if they are "constant" for some definition of constant.  The
  1815   1842   ** Walker.eCode value determines the type of "constant" we are looking
  1816   1843   ** for.
  1817   1844   **
................................................................................
  4395   4422     int r1, r2;
  4396   4423   
  4397   4424     assert( jumpIfNull==SQLITE_JUMPIFNULL || jumpIfNull==0 );
  4398   4425     if( NEVER(v==0) )     return;  /* Existence of VDBE checked by caller */
  4399   4426     if( NEVER(pExpr==0) ) return;  /* No way this can happen */
  4400   4427     op = pExpr->op;
  4401   4428     switch( op ){
  4402         -    case TK_AND: {
  4403         -      int d2 = sqlite3VdbeMakeLabel(pParse);
  4404         -      testcase( jumpIfNull==0 );
  4405         -      sqlite3ExprIfFalse(pParse, pExpr->pLeft, d2,jumpIfNull^SQLITE_JUMPIFNULL);
  4406         -      sqlite3ExprIfTrue(pParse, pExpr->pRight, dest, jumpIfNull);
  4407         -      sqlite3VdbeResolveLabel(v, d2);
  4408         -      break;
  4409         -    }
         4429  +    case TK_AND:
  4410   4430       case TK_OR: {
  4411         -      testcase( jumpIfNull==0 );
  4412         -      sqlite3ExprIfTrue(pParse, pExpr->pLeft, dest, jumpIfNull);
  4413         -      sqlite3ExprIfTrue(pParse, pExpr->pRight, dest, jumpIfNull);
         4431  +      Expr *pAlt = sqlite3ExprSimplifiedAndOr(pExpr);
         4432  +      if( pAlt!=pExpr ){
         4433  +        sqlite3ExprIfTrue(pParse, pAlt, dest, jumpIfNull);
         4434  +      }else if( op==TK_AND ){
         4435  +        int d2 = sqlite3VdbeMakeLabel(pParse);
         4436  +        testcase( jumpIfNull==0 );
         4437  +        sqlite3ExprIfFalse(pParse, pExpr->pLeft, d2,
         4438  +                           jumpIfNull^SQLITE_JUMPIFNULL);
         4439  +        sqlite3ExprIfTrue(pParse, pExpr->pRight, dest, jumpIfNull);
         4440  +        sqlite3VdbeResolveLabel(v, d2);
         4441  +      }else{
         4442  +        testcase( jumpIfNull==0 );
         4443  +        sqlite3ExprIfTrue(pParse, pExpr->pLeft, dest, jumpIfNull);
         4444  +        sqlite3ExprIfTrue(pParse, pExpr->pRight, dest, jumpIfNull);
         4445  +      }
  4414   4446         break;
  4415   4447       }
  4416   4448       case TK_NOT: {
  4417   4449         testcase( jumpIfNull==0 );
  4418   4450         sqlite3ExprIfFalse(pParse, pExpr->pLeft, dest, jumpIfNull);
  4419   4451         break;
  4420   4452       }
................................................................................
  4562   4594     assert( pExpr->op!=TK_EQ || op==OP_Ne );
  4563   4595     assert( pExpr->op!=TK_LT || op==OP_Ge );
  4564   4596     assert( pExpr->op!=TK_LE || op==OP_Gt );
  4565   4597     assert( pExpr->op!=TK_GT || op==OP_Le );
  4566   4598     assert( pExpr->op!=TK_GE || op==OP_Lt );
  4567   4599   
  4568   4600     switch( pExpr->op ){
  4569         -    case TK_AND: {
  4570         -      testcase( jumpIfNull==0 );
  4571         -      sqlite3ExprIfFalse(pParse, pExpr->pLeft, dest, jumpIfNull);
  4572         -      sqlite3ExprIfFalse(pParse, pExpr->pRight, dest, jumpIfNull);
  4573         -      break;
  4574         -    }
         4601  +    case TK_AND:
  4575   4602       case TK_OR: {
  4576         -      int d2 = sqlite3VdbeMakeLabel(pParse);
  4577         -      testcase( jumpIfNull==0 );
  4578         -      sqlite3ExprIfTrue(pParse, pExpr->pLeft, d2, jumpIfNull^SQLITE_JUMPIFNULL);
  4579         -      sqlite3ExprIfFalse(pParse, pExpr->pRight, dest, jumpIfNull);
  4580         -      sqlite3VdbeResolveLabel(v, d2);
         4603  +      Expr *pAlt = sqlite3ExprSimplifiedAndOr(pExpr);
         4604  +      if( pAlt!=pExpr ){
         4605  +        sqlite3ExprIfFalse(pParse, pAlt, dest, jumpIfNull);
         4606  +      }else if( pExpr->op==TK_AND ){
         4607  +        testcase( jumpIfNull==0 );
         4608  +        sqlite3ExprIfFalse(pParse, pExpr->pLeft, dest, jumpIfNull);
         4609  +        sqlite3ExprIfFalse(pParse, pExpr->pRight, dest, jumpIfNull);
         4610  +      }else{
         4611  +        int d2 = sqlite3VdbeMakeLabel(pParse);
         4612  +        testcase( jumpIfNull==0 );
         4613  +        sqlite3ExprIfTrue(pParse, pExpr->pLeft, d2,
         4614  +                          jumpIfNull^SQLITE_JUMPIFNULL);
         4615  +        sqlite3ExprIfFalse(pParse, pExpr->pRight, dest, jumpIfNull);
         4616  +        sqlite3VdbeResolveLabel(v, d2);
         4617  +      }
  4581   4618         break;
  4582   4619       }
  4583   4620       case TK_NOT: {
  4584   4621         testcase( jumpIfNull==0 );
  4585   4622         sqlite3ExprIfTrue(pParse, pExpr->pLeft, dest, jumpIfNull);
  4586   4623         break;
  4587   4624       }

Changes to src/sqliteInt.h.

  3855   3855   #endif
  3856   3856   Expr *sqlite3ExprAlloc(sqlite3*,int,const Token*,int);
  3857   3857   Expr *sqlite3Expr(sqlite3*,int,const char*);
  3858   3858   void sqlite3ExprAttachSubtrees(sqlite3*,Expr*,Expr*,Expr*);
  3859   3859   Expr *sqlite3PExpr(Parse*, int, Expr*, Expr*);
  3860   3860   void sqlite3PExprAddSelect(Parse*, Expr*, Select*);
  3861   3861   Expr *sqlite3ExprAnd(Parse*,Expr*, Expr*);
         3862  +Expr *sqlite3ExprSimplifiedAndOr(Expr*);
  3862   3863   Expr *sqlite3ExprFunction(Parse*,ExprList*, Token*, int);
  3863   3864   void sqlite3ExprAssignVarNumber(Parse*, Expr*, u32);
  3864   3865   void sqlite3ExprDelete(sqlite3*, Expr*);
  3865   3866   ExprList *sqlite3ExprListAppend(Parse*,ExprList*,Expr*);
  3866   3867   ExprList *sqlite3ExprListAppendVector(Parse*,ExprList*,IdList*,Expr*);
  3867   3868   void sqlite3ExprListSetSortOrder(ExprList*,int);
  3868   3869   void sqlite3ExprListSetName(Parse*,ExprList*,Token*,int);