SQLite

Check-in [7713996aa9]
Login

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

Overview
Comment:Streamline the processing of the AND operator. Slightly smaller and faster.
Downloads: Tarball | ZIP archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA3-256: 7713996aa99ce6dd35b5a2db74dd26658fb8d9817169b2a7531cdef6edb41403
User & Date: drh 2019-04-19 13:38:34.610
Context
2019-04-19
16:21
Use macros to determine if an expression is always true or always false. (check-in: 6de980a09c user: drh tags: trunk)
13:38
Streamline the processing of the AND operator. Slightly smaller and faster. (check-in: 7713996aa9 user: drh tags: trunk)
2019-04-17
21:12
Small performance and size optimization in sqlite3WalFindFrame(). (check-in: 03f2e78899 user: drh tags: trunk)
Changes
Side-by-Side Diff Show Whitespace Changes Patch
Changes to src/expr.c.
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866



867
868
869
870
871
872
873
846
847
848
849
850
851
852




853
854
855
856
857

858


859
860
861
862
863
864
865
866
867
868
869







-
-
-
-





-

-
-

+
+
+







Expr *sqlite3PExpr(
  Parse *pParse,          /* Parsing context */
  int op,                 /* Expression opcode */
  Expr *pLeft,            /* Left operand */
  Expr *pRight            /* Right operand */
){
  Expr *p;
  if( op==TK_AND && pParse->nErr==0 && !IN_RENAME_OBJECT ){
    /* Take advantage of short-circuit false optimization for AND */
    p = sqlite3ExprAnd(pParse->db, pLeft, pRight);
  }else{
    p = sqlite3DbMallocRawNN(pParse->db, sizeof(Expr));
    if( p ){
      memset(p, 0, sizeof(Expr));
      p->op = op & 0xff;
      p->iAgg = -1;
    }
    sqlite3ExprAttachSubtrees(pParse->db, p, pLeft, pRight);
  }
  if( p ) {
    sqlite3ExprCheckHeight(pParse, p->nHeight);
  }else{
    sqlite3ExprDelete(pParse->db, pLeft);
    sqlite3ExprDelete(pParse->db, pRight);
  }
  return p;
}

/*
** Add pSelect to the Expr.x.pSelect field.  Or, if pExpr is NULL (due
** do a memory allocation failure) then delete the pSelect object.
915
916
917
918
919
920
921
922


923
924
925
926


927
928
929
930
931
932
933
934

935
936
937
938
939
940
941
911
912
913
914
915
916
917

918
919
920
921
922
923
924
925
926
927
928
929
930



931
932
933
934
935
936
937
938







-
+
+




+
+





-
-
-
+







** Join two expressions using an AND operator.  If either expression is
** NULL, then just return the other expression.
**
** If one side or the other of the AND is known to be false, then instead
** of returning an AND expression, just return a constant expression with
** a value of false.
*/
Expr *sqlite3ExprAnd(sqlite3 *db, Expr *pLeft, Expr *pRight){
Expr *sqlite3ExprAnd(Parse *pParse, Expr *pLeft, Expr *pRight){
  sqlite3 *db = pParse->db;
  if( pLeft==0 ){
    return pRight;
  }else if( pRight==0 ){
    return pLeft;
  }else if( pParse->nErr || IN_RENAME_OBJECT ){
    return sqlite3PExpr(pParse, TK_AND, pLeft, pRight);
  }else if( exprAlwaysFalse(pLeft) || exprAlwaysFalse(pRight) ){
    sqlite3ExprDelete(db, pLeft);
    sqlite3ExprDelete(db, pRight);
    return sqlite3ExprAlloc(db, TK_INTEGER, &sqlite3IntTokens[0], 0);
  }else{
    Expr *pNew = sqlite3ExprAlloc(db, TK_AND, 0, 0);
    sqlite3ExprAttachSubtrees(db, pNew, pLeft, pRight);
    return pNew;
    return sqlite3PExpr(pParse, TK_AND, pLeft, pRight);
  }
}

/*
** Construct a new expression node for a function with multiple
** arguments.
*/
Changes to src/fkey.c.
587
588
589
590
591
592
593
594

595
596
597
598
599
600
601
587
588
589
590
591
592
593

594
595
596
597
598
599
600
601







-
+







    iCol = pIdx ? pIdx->aiColumn[i] : -1;
    pLeft = exprTableRegister(pParse, pTab, regData, iCol);
    iCol = aiCol ? aiCol[i] : pFKey->aCol[0].iFrom;
    assert( iCol>=0 );
    zCol = pFKey->pFrom->aCol[iCol].zName;
    pRight = sqlite3Expr(db, TK_ID, zCol);
    pEq = sqlite3PExpr(pParse, TK_EQ, pLeft, pRight);
    pWhere = sqlite3ExprAnd(db, pWhere, pEq);
    pWhere = sqlite3ExprAnd(pParse, pWhere, pEq);
  }

  /* If the child table is the same as the parent table, then add terms
  ** to the WHERE clause that prevent this entry from being scanned.
  ** The added WHERE clause terms are like this:
  **
  **     $current_rowid!=rowid
621
622
623
624
625
626
627
628

629
630
631
632

633
634
635
636
637
638
639
621
622
623
624
625
626
627

628
629
630
631

632
633
634
635
636
637
638
639







-
+



-
+







      assert( pIdx!=0 );
      for(i=0; i<pIdx->nKeyCol; i++){
        i16 iCol = pIdx->aiColumn[i];
        assert( iCol>=0 );
        pLeft = exprTableRegister(pParse, pTab, regData, iCol);
        pRight = sqlite3Expr(db, TK_ID, pTab->aCol[iCol].zName);
        pEq = sqlite3PExpr(pParse, TK_IS, pLeft, pRight);
        pAll = sqlite3ExprAnd(db, pAll, pEq);
        pAll = sqlite3ExprAnd(pParse, pAll, pEq);
      }
      pNe = sqlite3PExpr(pParse, TK_NOT, pAll, 0);
    }
    pWhere = sqlite3ExprAnd(db, pWhere, pNe);
    pWhere = sqlite3ExprAnd(pParse, pWhere, pNe);
  }

  /* Resolve the references in the WHERE clause. */
  memset(&sNameContext, 0, sizeof(NameContext));
  sNameContext.pSrcList = pSrc;
  sNameContext.pParse = pParse;
  sqlite3ResolveExprNames(&sNameContext, pWhere);
1231
1232
1233
1234
1235
1236
1237
1238

1239
1240
1241
1242
1243
1244
1245
1246
1247
1248
1249
1250
1251
1252
1253
1254

1255
1256
1257
1258
1259
1260
1261
1231
1232
1233
1234
1235
1236
1237

1238
1239
1240
1241
1242
1243
1244
1245
1246
1247
1248
1249
1250
1251
1252
1253

1254
1255
1256
1257
1258
1259
1260
1261







-
+















-
+







      ** parent table are used for the comparison. */
      pEq = sqlite3PExpr(pParse, TK_EQ,
          sqlite3PExpr(pParse, TK_DOT, 
            sqlite3ExprAlloc(db, TK_ID, &tOld, 0),
            sqlite3ExprAlloc(db, TK_ID, &tToCol, 0)),
          sqlite3ExprAlloc(db, TK_ID, &tFromCol, 0)
      );
      pWhere = sqlite3ExprAnd(db, pWhere, pEq);
      pWhere = sqlite3ExprAnd(pParse, pWhere, pEq);

      /* For ON UPDATE, construct the next term of the WHEN clause.
      ** The final WHEN clause will be like this:
      **
      **    WHEN NOT(old.col1 IS new.col1 AND ... AND old.colN IS new.colN)
      */
      if( pChanges ){
        pEq = sqlite3PExpr(pParse, TK_IS,
            sqlite3PExpr(pParse, TK_DOT, 
              sqlite3ExprAlloc(db, TK_ID, &tOld, 0),
              sqlite3ExprAlloc(db, TK_ID, &tToCol, 0)),
            sqlite3PExpr(pParse, TK_DOT, 
              sqlite3ExprAlloc(db, TK_ID, &tNew, 0),
              sqlite3ExprAlloc(db, TK_ID, &tToCol, 0))
            );
        pWhen = sqlite3ExprAnd(db, pWhen, pEq);
        pWhen = sqlite3ExprAnd(pParse, pWhen, pEq);
      }
  
      if( action!=OE_Restrict && (action!=OE_Cascade || pChanges) ){
        Expr *pNew;
        if( action==OE_Cascade ){
          pNew = sqlite3PExpr(pParse, TK_DOT, 
            sqlite3ExprAlloc(db, TK_ID, &tNew, 0),
Changes to src/parse.y.
1060
1061
1062
1063
1064
1065
1066
1067

1068
1069
1070
1071
1072
1073
1074
1060
1061
1062
1063
1064
1065
1066

1067
1068
1069
1070
1071
1072
1073
1074







-
+







  if( A ){
    A->x.pList = pList;
  }else{
    sqlite3ExprListDelete(pParse->db, pList);
  }
}

expr(A) ::= expr(A) AND(OP) expr(Y).    {A=sqlite3PExpr(pParse,@OP,A,Y);}
expr(A) ::= expr(A) AND expr(Y).        {A=sqlite3ExprAnd(pParse,A,Y);}
expr(A) ::= expr(A) OR(OP) expr(Y).     {A=sqlite3PExpr(pParse,@OP,A,Y);}
expr(A) ::= expr(A) LT|GT|GE|LE(OP) expr(Y).
                                        {A=sqlite3PExpr(pParse,@OP,A,Y);}
expr(A) ::= expr(A) EQ|NE(OP) expr(Y).  {A=sqlite3PExpr(pParse,@OP,A,Y);}
expr(A) ::= expr(A) BITAND|BITOR|LSHIFT|RSHIFT(OP) expr(Y).
                                        {A=sqlite3PExpr(pParse,@OP,A,Y);}
expr(A) ::= expr(A) PLUS|MINUS(OP) expr(Y).
Changes to src/select.c.
351
352
353
354
355
356
357
358

359
360
361
362
363
364
365
351
352
353
354
355
356
357

358
359
360
361
362
363
364
365







-
+







  pEq = sqlite3PExpr(pParse, TK_EQ, pE1, pE2);
  if( pEq && isOuterJoin ){
    ExprSetProperty(pEq, EP_FromJoin);
    assert( !ExprHasProperty(pEq, EP_TokenOnly|EP_Reduced) );
    ExprSetVVAProperty(pEq, EP_NoReduce);
    pEq->iRightJoinTable = (i16)pE2->iTable;
  }
  *ppWhere = sqlite3ExprAnd(db, *ppWhere, pEq);
  *ppWhere = sqlite3ExprAnd(pParse, *ppWhere, pEq);
}

/*
** Set the EP_FromJoin property on all terms of the given expression.
** And set the Expr.iRightJoinTable to iTable for every term in the
** expression.
**
485
486
487
488
489
490
491
492

493
494
495
496
497
498
499
485
486
487
488
489
490
491

492
493
494
495
496
497
498
499







-
+







    }

    /* Add the ON clause to the end of the WHERE clause, connected by
    ** an AND operator.
    */
    if( pRight->pOn ){
      if( isOuter ) setJoinExpr(pRight->pOn, pRight->iCursor);
      p->pWhere = sqlite3ExprAnd(pParse->db, p->pWhere, pRight->pOn);
      p->pWhere = sqlite3ExprAnd(pParse, p->pWhere, pRight->pOn);
      pRight->pOn = 0;
    }

    /* Create extra terms on the WHERE clause for each column named
    ** in the USING clause.  Example: If the two tables to be joined are 
    ** A and B and the USING clause names X, Y, and Z, then add this
    ** to the WHERE clause:    A.X=B.X AND A.Y=B.Y AND A.Z=B.Z
4030
4031
4032
4033
4034
4035
4036
4037

4038
4039
4040
4041
4042
4043
4044
4030
4031
4032
4033
4034
4035
4036

4037
4038
4039
4040
4041
4042
4043
4044







-
+







      pSub->pOrderBy = 0;
    }
    pWhere = pSub->pWhere;
    pSub->pWhere = 0;
    if( isLeftJoin>0 ){
      setJoinExpr(pWhere, iNewParent);
    }
    pParent->pWhere = sqlite3ExprAnd(db, pWhere, pParent->pWhere);
    pParent->pWhere = sqlite3ExprAnd(pParse, pWhere, pParent->pWhere);
    if( db->mallocFailed==0 ){
      SubstContext x;
      x.pParse = pParse;
      x.iTable = iParent;
      x.iNewTable = iNewParent;
      x.isLeftJoin = isLeftJoin;
      x.pEList = pSub->pEList;
4365
4366
4367
4368
4369
4370
4371
4372

4373
4374

4375
4376
4377
4378
4379
4380
4381
4365
4366
4367
4368
4369
4370
4371

4372
4373

4374
4375
4376
4377
4378
4379
4380
4381







-
+

-
+







      x.pParse = pParse;
      x.iTable = iCursor;
      x.iNewTable = iCursor;
      x.isLeftJoin = 0;
      x.pEList = pSubq->pEList;
      pNew = substExpr(&x, pNew);
      if( pSubq->selFlags & SF_Aggregate ){
        pSubq->pHaving = sqlite3ExprAnd(pParse->db, pSubq->pHaving, pNew);
        pSubq->pHaving = sqlite3ExprAnd(pParse, pSubq->pHaving, pNew);
      }else{
        pSubq->pWhere = sqlite3ExprAnd(pParse->db, pSubq->pWhere, pNew);
        pSubq->pWhere = sqlite3ExprAnd(pParse, pSubq->pWhere, pNew);
      }
      pSubq = pSubq->pPrior;
    }
  }
  return nChng;
}
#endif /* !defined(SQLITE_OMIT_SUBQUERY) || !defined(SQLITE_OMIT_VIEW) */
5414
5415
5416
5417
5418
5419
5420
5421

5422
5423
5424
5425
5426
5427
5428
5414
5415
5416
5417
5418
5419
5420

5421
5422
5423
5424
5425
5426
5427
5428







-
+







    Select *pS = pWalker->u.pSelect;
    if( sqlite3ExprIsConstantOrGroupBy(pWalker->pParse, pExpr, pS->pGroupBy) ){
      sqlite3 *db = pWalker->pParse->db;
      Expr *pNew = sqlite3ExprAlloc(db, TK_INTEGER, &sqlite3IntTokens[1], 0);
      if( pNew ){
        Expr *pWhere = pS->pWhere;
        SWAP(Expr, *pNew, *pExpr);
        pNew = sqlite3ExprAnd(db, pWhere, pNew);
        pNew = sqlite3ExprAnd(pWalker->pParse, pWhere, pNew);
        pS->pWhere = pNew;
        pWalker->eCode = 1;
      }
    }
    return WRC_Prune;
  }
  return WRC_Continue;
Changes to src/sqliteInt.h.
3850
3851
3852
3853
3854
3855
3856
3857

3858
3859
3860
3861
3862
3863
3864
3850
3851
3852
3853
3854
3855
3856

3857
3858
3859
3860
3861
3862
3863
3864







-
+







int sqlite3NoTempsInRange(Parse*,int,int);
#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(sqlite3*,Expr*, Expr*);
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);
Changes to src/where.c.
733
734
735
736
737
738
739
740

741
742
743
744
745
746
747
733
734
735
736
737
738
739

740
741
742
743
744
745
746
747







-
+







    assert( !ExprHasProperty(pExpr, EP_FromJoin)    /* prereq always non-zero */
         || pExpr->iRightJoinTable!=pSrc->iCursor   /*   for the right-hand   */
         || pLoop->prereq!=0 );                     /*   table of a LEFT JOIN */
    if( pLoop->prereq==0
     && (pTerm->wtFlags & TERM_VIRTUAL)==0
     && !ExprHasProperty(pExpr, EP_FromJoin)
     && sqlite3ExprIsTableConstant(pExpr, pSrc->iCursor) ){
      pPartial = sqlite3ExprAnd(pParse->db, pPartial,
      pPartial = sqlite3ExprAnd(pParse, pPartial,
                                sqlite3ExprDup(pParse->db, pExpr, 0));
    }
    if( termCanDriveIndex(pTerm, pSrc, notReady) ){
      int iCol = pTerm->u.leftColumn;
      Bitmask cMask = iCol>=BMS ? MASKBIT(BMS-1) : MASKBIT(iCol);
      testcase( iCol==BMS );
      testcase( iCol==BMS-1 );
Changes to src/wherecode.c.
995
996
997
998
999
1000
1001
1002

1003
1004
1005
1006
1007
1008
1009
995
996
997
998
999
1000
1001

1002
1003
1004
1005
1006
1007
1008
1009







-
+







      sWalker.eCode = 0;
      sWalker.xExprCallback = codeCursorHintCheckExpr;
      sqlite3WalkExpr(&sWalker, pTerm->pExpr);
      if( sWalker.eCode ) continue;
    }

    /* If we survive all prior tests, that means this term is worth hinting */
    pExpr = sqlite3ExprAnd(db, pExpr, sqlite3ExprDup(db, pTerm->pExpr, 0));
    pExpr = sqlite3ExprAnd(pParse, pExpr, sqlite3ExprDup(db, pTerm->pExpr, 0));
  }
  if( pExpr!=0 ){
    sWalker.xExprCallback = codeCursorHintFixExpr;
    sqlite3WalkExpr(&sWalker, pExpr);
    sqlite3VdbeAddOp4(v, OP_CursorHint, 
                      (sHint.pIdx ? sHint.iIdxCur : sHint.iTabCur), 0, 0,
                      (const char*)pExpr, P4_EXPR);
1960
1961
1962
1963
1964
1965
1966
1967

1968
1969
1970
1971
1972
1973
1974
1960
1961
1962
1963
1964
1965
1966

1967
1968
1969
1970
1971
1972
1973
1974







-
+







        if( &pWC->a[iTerm] == pTerm ) continue;
        testcase( pWC->a[iTerm].wtFlags & TERM_VIRTUAL );
        testcase( pWC->a[iTerm].wtFlags & TERM_CODED );
        if( (pWC->a[iTerm].wtFlags & (TERM_VIRTUAL|TERM_CODED))!=0 ) continue;
        if( (pWC->a[iTerm].eOperator & WO_ALL)==0 ) continue;
        testcase( pWC->a[iTerm].wtFlags & TERM_ORINFO );
        pExpr = sqlite3ExprDup(db, pExpr, 0);
        pAndExpr = sqlite3ExprAnd(db, pAndExpr, pExpr);
        pAndExpr = sqlite3ExprAnd(pParse, pAndExpr, pExpr);
      }
      if( pAndExpr ){
        /* The extra 0x10000 bit on the opcode is masked off and does not
        ** become part of the new Expr.op.  However, it does make the
        ** op==TK_AND comparison inside of sqlite3PExpr() false, and this
        ** prevents sqlite3PExpr() from implementing AND short-circuit 
        ** optimization, which we do not want here. */