/ Check-in [0fbd154e]
Login
SQLite training in Houston TX on 2019-11-05 (details)
Part of the 2019 Tcl Conference

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 Unified Diffs Ignore Whitespace Patch

Changes to src/expr.c.

1804
1805
1806
1807
1808
1809
1810



























1811
1812
1813
1814
1815
1816
1817
....
4395
4396
4397
4398
4399
4400
4401
4402





4403
4404
4405

4406
4407
4408
4409
4410

4411
4412
4413

4414
4415
4416
4417
4418
4419
4420
....
4562
4563
4564
4565
4566
4567
4568
4569





4570
4571
4572
4573
4574
4575

4576
4577
4578

4579
4580

4581
4582
4583
4584
4585
4586
4587
int sqlite3ExprTruthValue(const Expr *pExpr){
  assert( pExpr->op==TK_TRUEFALSE );
  assert( sqlite3StrICmp(pExpr->u.zToken,"true")==0
       || sqlite3StrICmp(pExpr->u.zToken,"false")==0 );
  return pExpr->u.zToken[4]==0;
}





























/*
** These routines are Walker callbacks used to check expressions to
** see if they are "constant" for some definition of constant.  The
** Walker.eCode value determines the type of "constant" we are looking
** for.
**
................................................................................
  int r1, r2;

  assert( jumpIfNull==SQLITE_JUMPIFNULL || jumpIfNull==0 );
  if( NEVER(v==0) )     return;  /* Existence of VDBE checked by caller */
  if( NEVER(pExpr==0) ) return;  /* No way this can happen */
  op = pExpr->op;
  switch( op ){
    case TK_AND: {





      int d2 = sqlite3VdbeMakeLabel(pParse);
      testcase( jumpIfNull==0 );
      sqlite3ExprIfFalse(pParse, pExpr->pLeft, d2,jumpIfNull^SQLITE_JUMPIFNULL);

      sqlite3ExprIfTrue(pParse, pExpr->pRight, dest, jumpIfNull);
      sqlite3VdbeResolveLabel(v, d2);
      break;
    }
    case TK_OR: {

      testcase( jumpIfNull==0 );
      sqlite3ExprIfTrue(pParse, pExpr->pLeft, dest, jumpIfNull);
      sqlite3ExprIfTrue(pParse, pExpr->pRight, dest, jumpIfNull);

      break;
    }
    case TK_NOT: {
      testcase( jumpIfNull==0 );
      sqlite3ExprIfFalse(pParse, pExpr->pLeft, dest, jumpIfNull);
      break;
    }
................................................................................
  assert( pExpr->op!=TK_EQ || op==OP_Ne );
  assert( pExpr->op!=TK_LT || op==OP_Ge );
  assert( pExpr->op!=TK_LE || op==OP_Gt );
  assert( pExpr->op!=TK_GT || op==OP_Le );
  assert( pExpr->op!=TK_GE || op==OP_Lt );

  switch( pExpr->op ){
    case TK_AND: {





      testcase( jumpIfNull==0 );
      sqlite3ExprIfFalse(pParse, pExpr->pLeft, dest, jumpIfNull);
      sqlite3ExprIfFalse(pParse, pExpr->pRight, dest, jumpIfNull);
      break;
    }
    case TK_OR: {

      int d2 = sqlite3VdbeMakeLabel(pParse);
      testcase( jumpIfNull==0 );
      sqlite3ExprIfTrue(pParse, pExpr->pLeft, d2, jumpIfNull^SQLITE_JUMPIFNULL);

      sqlite3ExprIfFalse(pParse, pExpr->pRight, dest, jumpIfNull);
      sqlite3VdbeResolveLabel(v, d2);

      break;
    }
    case TK_NOT: {
      testcase( jumpIfNull==0 );
      sqlite3ExprIfTrue(pParse, pExpr->pLeft, dest, jumpIfNull);
      break;
    }







>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>







 







|
>
>
>
>
>
|
|
|
>
|
|
<
<
<
>
|
|
|
>







 







|
>
>
>
>
>
|
|
|
<
<
<
>
|
|
|
>
|
|
>







1804
1805
1806
1807
1808
1809
1810
1811
1812
1813
1814
1815
1816
1817
1818
1819
1820
1821
1822
1823
1824
1825
1826
1827
1828
1829
1830
1831
1832
1833
1834
1835
1836
1837
1838
1839
1840
1841
1842
1843
1844
....
4422
4423
4424
4425
4426
4427
4428
4429
4430
4431
4432
4433
4434
4435
4436
4437
4438
4439
4440



4441
4442
4443
4444
4445
4446
4447
4448
4449
4450
4451
4452
....
4594
4595
4596
4597
4598
4599
4600
4601
4602
4603
4604
4605
4606
4607
4608
4609



4610
4611
4612
4613
4614
4615
4616
4617
4618
4619
4620
4621
4622
4623
4624
int sqlite3ExprTruthValue(const Expr *pExpr){
  assert( pExpr->op==TK_TRUEFALSE );
  assert( sqlite3StrICmp(pExpr->u.zToken,"true")==0
       || sqlite3StrICmp(pExpr->u.zToken,"false")==0 );
  return pExpr->u.zToken[4]==0;
}

/*
** If pExpr is an AND or OR expression, try to simplify it by eliminating
** terms that are always true or false.  Return the simplified expression.
** Or return the original expression if no simplification is possible.
**
** Examples:
**
**     (x<10) AND true                =>   (x<10)
**     (x<10) AND false               =>   false
**     (x<10) AND (y=22 OR false)     =>   (x<10) AND (y=22)
**     (x<10) AND (y=22 OR true)      =>   (x<10)
**     (y=22) OR true                 =>   true
*/
Expr *sqlite3ExprSimplifiedAndOr(Expr *pExpr){
  assert( pExpr!=0 );
  if( pExpr->op==TK_AND || pExpr->op==TK_OR ){
    Expr *pRight = sqlite3ExprSimplifiedAndOr(pExpr->pRight);
    Expr *pLeft = sqlite3ExprSimplifiedAndOr(pExpr->pLeft);
    if( ExprAlwaysTrue(pLeft) || ExprAlwaysFalse(pRight) ){
      pExpr = pExpr->op==TK_AND ? pRight : pLeft;
    }else if( ExprAlwaysTrue(pRight) || ExprAlwaysFalse(pLeft) ){
      pExpr = pExpr->op==TK_AND ? pLeft : pRight;
    }
  }
  return pExpr;
}


/*
** These routines are Walker callbacks used to check expressions to
** see if they are "constant" for some definition of constant.  The
** Walker.eCode value determines the type of "constant" we are looking
** for.
**
................................................................................
  int r1, r2;

  assert( jumpIfNull==SQLITE_JUMPIFNULL || jumpIfNull==0 );
  if( NEVER(v==0) )     return;  /* Existence of VDBE checked by caller */
  if( NEVER(pExpr==0) ) return;  /* No way this can happen */
  op = pExpr->op;
  switch( op ){
    case TK_AND:
    case TK_OR: {
      Expr *pAlt = sqlite3ExprSimplifiedAndOr(pExpr);
      if( pAlt!=pExpr ){
        sqlite3ExprIfTrue(pParse, pAlt, dest, jumpIfNull);
      }else if( op==TK_AND ){
        int d2 = sqlite3VdbeMakeLabel(pParse);
        testcase( jumpIfNull==0 );
        sqlite3ExprIfFalse(pParse, pExpr->pLeft, d2,
                           jumpIfNull^SQLITE_JUMPIFNULL);
        sqlite3ExprIfTrue(pParse, pExpr->pRight, dest, jumpIfNull);
        sqlite3VdbeResolveLabel(v, d2);



      }else{
        testcase( jumpIfNull==0 );
        sqlite3ExprIfTrue(pParse, pExpr->pLeft, dest, jumpIfNull);
        sqlite3ExprIfTrue(pParse, pExpr->pRight, dest, jumpIfNull);
      }
      break;
    }
    case TK_NOT: {
      testcase( jumpIfNull==0 );
      sqlite3ExprIfFalse(pParse, pExpr->pLeft, dest, jumpIfNull);
      break;
    }
................................................................................
  assert( pExpr->op!=TK_EQ || op==OP_Ne );
  assert( pExpr->op!=TK_LT || op==OP_Ge );
  assert( pExpr->op!=TK_LE || op==OP_Gt );
  assert( pExpr->op!=TK_GT || op==OP_Le );
  assert( pExpr->op!=TK_GE || op==OP_Lt );

  switch( pExpr->op ){
    case TK_AND:
    case TK_OR: {
      Expr *pAlt = sqlite3ExprSimplifiedAndOr(pExpr);
      if( pAlt!=pExpr ){
        sqlite3ExprIfFalse(pParse, pAlt, dest, jumpIfNull);
      }else if( pExpr->op==TK_AND ){
        testcase( jumpIfNull==0 );
        sqlite3ExprIfFalse(pParse, pExpr->pLeft, dest, jumpIfNull);
        sqlite3ExprIfFalse(pParse, pExpr->pRight, dest, jumpIfNull);



      }else{
        int d2 = sqlite3VdbeMakeLabel(pParse);
        testcase( jumpIfNull==0 );
        sqlite3ExprIfTrue(pParse, pExpr->pLeft, d2,
                          jumpIfNull^SQLITE_JUMPIFNULL);
        sqlite3ExprIfFalse(pParse, pExpr->pRight, dest, jumpIfNull);
        sqlite3VdbeResolveLabel(v, d2);
      }
      break;
    }
    case TK_NOT: {
      testcase( jumpIfNull==0 );
      sqlite3ExprIfTrue(pParse, pExpr->pLeft, dest, jumpIfNull);
      break;
    }

Changes to src/sqliteInt.h.

3855
3856
3857
3858
3859
3860
3861

3862
3863
3864
3865
3866
3867
3868
#endif
Expr *sqlite3ExprAlloc(sqlite3*,int,const Token*,int);
Expr *sqlite3Expr(sqlite3*,int,const char*);
void sqlite3ExprAttachSubtrees(sqlite3*,Expr*,Expr*,Expr*);
Expr *sqlite3PExpr(Parse*, int, Expr*, Expr*);
void sqlite3PExprAddSelect(Parse*, Expr*, Select*);
Expr *sqlite3ExprAnd(Parse*,Expr*, Expr*);

Expr *sqlite3ExprFunction(Parse*,ExprList*, Token*, int);
void sqlite3ExprAssignVarNumber(Parse*, Expr*, u32);
void sqlite3ExprDelete(sqlite3*, Expr*);
ExprList *sqlite3ExprListAppend(Parse*,ExprList*,Expr*);
ExprList *sqlite3ExprListAppendVector(Parse*,ExprList*,IdList*,Expr*);
void sqlite3ExprListSetSortOrder(ExprList*,int);
void sqlite3ExprListSetName(Parse*,ExprList*,Token*,int);







>







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