/ Check-in [8a6ea455]
Login

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

Overview
Comment:Add the EP_Leaf flag bit to the Expr.flags field to indicate Expr nodes that do not have substructure. Use that bit to avoid unnecessary recursion.
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1:8a6ea455cd1bf42ae0a7f1f1789baf88d782db13
User & Date: drh 2016-09-23 21:36:24
Context
2016-09-24
01:41
Add -DSQLITE_MAX_EXPR_DEPTH=0 to the --lean option on speed-check.sh. check-in: a8cb1390 user: drh tags: trunk
2016-09-23
21:36
Add the EP_Leaf flag bit to the Expr.flags field to indicate Expr nodes that do not have substructure. Use that bit to avoid unnecessary recursion. check-in: 8a6ea455 user: drh tags: trunk
20:59
Use sqlite3ExprAlloc() instead of sqlite3PExpr() for leaf nodes in the expression tree, where appropriate. This is both smaller and faster. check-in: afac0709 user: drh tags: trunk
Changes
Hide Diffs Side-by-Side Diffs Ignore Whitespace Patch

Changes to src/attach.c.

   526    526         if( pFix->pParse->db->init.busy ){
   527    527           pExpr->op = TK_NULL;
   528    528         }else{
   529    529           sqlite3ErrorMsg(pFix->pParse, "%s cannot use variables", pFix->zType);
   530    530           return 1;
   531    531         }
   532    532       }
   533         -    if( ExprHasProperty(pExpr, EP_TokenOnly) ) break;
          533  +    if( ExprHasProperty(pExpr, EP_TokenOnly|EP_Leaf) ) break;
   534    534       if( ExprHasProperty(pExpr, EP_xIsSelect) ){
   535    535         if( sqlite3FixSelect(pFix, pExpr->x.pSelect) ) return 1;
   536    536       }else{
   537    537         if( sqlite3FixExprList(pFix, pExpr->x.pList) ) return 1;
   538    538       }
   539    539       if( sqlite3FixExpr(pFix, pExpr->pRight) ){
   540    540         return 1;

Changes to src/expr.c.

  1012   1012   /*
  1013   1013   ** Recursively delete an expression tree.
  1014   1014   */
  1015   1015   static SQLITE_NOINLINE void sqlite3ExprDeleteNN(sqlite3 *db, Expr *p){
  1016   1016     assert( p!=0 );
  1017   1017     /* Sanity check: Assert that the IntValue is non-negative if it exists */
  1018   1018     assert( !ExprHasProperty(p, EP_IntValue) || p->u.iValue>=0 );
  1019         -  if( !ExprHasProperty(p, EP_TokenOnly) ){
         1019  +#ifdef SQLITE_DEBUG
         1020  +  if( ExprHasProperty(p, EP_Leaf) && !ExprHasProperty(p, EP_TokenOnly) ){
         1021  +    assert( p->pLeft==0 );
         1022  +    assert( p->pRight==0 );
         1023  +    assert( p->x.pSelect==0 );
         1024  +  }
         1025  +#endif
         1026  +  if( !ExprHasProperty(p, (EP_TokenOnly|EP_Leaf)) ){
  1020   1027       /* The Expr.x union is never used at the same time as Expr.pRight */
  1021   1028       assert( p->x.pList==0 || p->pRight==0 );
  1022   1029       if( p->pLeft && p->op!=TK_SELECT_COLUMN ) sqlite3ExprDeleteNN(db, p->pLeft);
  1023   1030       sqlite3ExprDelete(db, p->pRight);
  1024         -    if( ExprHasProperty(p, EP_MemToken) ) sqlite3DbFree(db, p->u.zToken);
  1025   1031       if( ExprHasProperty(p, EP_xIsSelect) ){
  1026   1032         sqlite3SelectDelete(db, p->x.pSelect);
  1027   1033       }else{
  1028   1034         sqlite3ExprListDelete(db, p->x.pList);
  1029   1035       }
  1030   1036     }
         1037  +  if( ExprHasProperty(p, EP_MemToken) ) sqlite3DbFree(db, p->u.zToken);
  1031   1038     if( !ExprHasProperty(p, EP_Static) ){
  1032   1039       sqlite3DbFree(db, p);
  1033   1040     }
  1034   1041   }
  1035   1042   void sqlite3ExprDelete(sqlite3 *db, Expr *p){
  1036   1043     if( p ) sqlite3ExprDeleteNN(db, p);
  1037   1044   }
................................................................................
  1200   1207   
  1201   1208       /* Copy the p->u.zToken string, if any. */
  1202   1209       if( nToken ){
  1203   1210         char *zToken = pNew->u.zToken = (char*)&zAlloc[nNewSize];
  1204   1211         memcpy(zToken, p->u.zToken, nToken);
  1205   1212       }
  1206   1213   
  1207         -    if( 0==((p->flags|pNew->flags) & EP_TokenOnly) ){
         1214  +    if( 0==((p->flags|pNew->flags) & (EP_TokenOnly|EP_Leaf)) ){
  1208   1215         /* Fill in the pNew->x.pSelect or pNew->x.pList member. */
  1209   1216         if( ExprHasProperty(p, EP_xIsSelect) ){
  1210   1217           pNew->x.pSelect = sqlite3SelectDup(db, p->x.pSelect, dupFlags);
  1211   1218         }else{
  1212   1219           pNew->x.pList = sqlite3ExprListDup(db, p->x.pList, dupFlags);
  1213   1220         }
  1214   1221       }
  1215   1222   
  1216   1223       /* Fill in pNew->pLeft and pNew->pRight. */
  1217   1224       if( ExprHasProperty(pNew, EP_Reduced|EP_TokenOnly) ){
  1218   1225         zAlloc += dupedExprNodeSize(p, dupFlags);
  1219         -      if( ExprHasProperty(pNew, EP_Reduced) ){
         1226  +      if( !ExprHasProperty(pNew, EP_TokenOnly|EP_Leaf) ){
  1220   1227           pNew->pLeft = p->pLeft ?
  1221   1228                         exprDup(db, p->pLeft, EXPRDUP_REDUCE, &zAlloc) : 0;
  1222   1229           pNew->pRight = p->pRight ?
  1223   1230                          exprDup(db, p->pRight, EXPRDUP_REDUCE, &zAlloc) : 0;
  1224   1231         }
  1225   1232         if( pzBuffer ){
  1226   1233           *pzBuffer = zAlloc;
  1227   1234         }
  1228   1235       }else{
  1229         -      if( !ExprHasProperty(p, EP_TokenOnly) ){
         1236  +      if( !ExprHasProperty(p, EP_TokenOnly|EP_Leaf) ){
  1230   1237           if( pNew->op==TK_SELECT_COLUMN ){
  1231   1238             pNew->pLeft = p->pLeft;
  1232   1239           }else{
  1233   1240             pNew->pLeft = sqlite3ExprDup(db, p->pLeft, 0);
  1234   1241           }
  1235   1242           pNew->pRight = sqlite3ExprDup(db, p->pRight, 0);
  1236   1243         }

Changes to src/parse.y.

   850    850     ** new Expr to populate pOut.  Set the span of pOut to be the identifier
   851    851     ** that created the expression.
   852    852     */
   853    853     static void spanExpr(ExprSpan *pOut, Parse *pParse, int op, Token t){
   854    854       pOut->pExpr = sqlite3ExprAlloc(pParse->db, op, &t, 1);
   855    855       pOut->zStart = t.z;
   856    856       pOut->zEnd = &t.z[t.n];
          857  +    if( pOut->pExpr ) pOut->pExpr->flags |= EP_Leaf;
   857    858     }
   858    859   }
   859    860   
   860    861   expr(A) ::= term(A).
   861    862   expr(A) ::= LP(B) expr(X) RP(E).
   862    863               {spanSet(&A,&B,&E); /*A-overwrites-B*/  A.pExpr = X.pExpr;}
   863    864   term(A) ::= NULL(X).        {spanExpr(&A,pParse,@X,X);/*A-overwrites-X*/}

Changes to src/sqliteInt.h.

  2334   2334   #define EP_MemToken  0x010000 /* Need to sqlite3DbFree() Expr.zToken */
  2335   2335   #define EP_NoReduce  0x020000 /* Cannot EXPRDUP_REDUCE this Expr */
  2336   2336   #define EP_Unlikely  0x040000 /* unlikely() or likelihood() function */
  2337   2337   #define EP_ConstFunc 0x080000 /* A SQLITE_FUNC_CONSTANT or _SLOCHNG function */
  2338   2338   #define EP_CanBeNull 0x100000 /* Can be null despite NOT NULL constraint */
  2339   2339   #define EP_Subquery  0x200000 /* Tree contains a TK_SELECT operator */
  2340   2340   #define EP_Alias     0x400000 /* Is an alias for a result set column */
         2341  +#define EP_Leaf      0x800000 /* Expr.pLeft, .pRight, .u.pSelect all NULL */
  2341   2342   
  2342   2343   /*
  2343   2344   ** Combinations of two or more EP_* flags
  2344   2345   */
  2345   2346   #define EP_Propagate (EP_Collate|EP_Subquery) /* Propagate these bits up tree */
  2346   2347   
  2347   2348   /*

Changes to src/walker.c.

    37     37   ** and WRC_Continue to continue.
    38     38   */
    39     39   static SQLITE_NOINLINE int walkExpr(Walker *pWalker, Expr *pExpr){
    40     40     int rc;
    41     41     testcase( ExprHasProperty(pExpr, EP_TokenOnly) );
    42     42     testcase( ExprHasProperty(pExpr, EP_Reduced) );
    43     43     rc = pWalker->xExprCallback(pWalker, pExpr);
    44         -  if( rc || ExprHasProperty(pExpr,EP_TokenOnly) ) return rc & WRC_Abort;
           44  +  if( rc || ExprHasProperty(pExpr,(EP_TokenOnly|EP_Leaf)) ){
           45  +    return rc & WRC_Abort;
           46  +  }
    45     47     if( pExpr->pLeft && walkExpr(pWalker, pExpr->pLeft) ) return WRC_Abort;
    46     48     if( pExpr->pRight && walkExpr(pWalker, pExpr->pRight) ) return WRC_Abort;
    47     49     if( ExprHasProperty(pExpr, EP_xIsSelect) ){
    48     50       if( sqlite3WalkSelect(pWalker, pExpr->x.pSelect) ) return WRC_Abort;
    49     51     }else if( pExpr->x.pList ){
    50     52       if( sqlite3WalkExprList(pWalker, pExpr->x.pList) ) return WRC_Abort;
    51     53     }