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 |
Timelines: | family | ancestors | descendants | both | trunk |
Files: | files | file ages | folders |
SHA1: |
8a6ea455cd1bf42ae0a7f1f1789baf88 |
User & Date: | drh 2016-09-23 21:36:24.016 |
Context
2016-09-24
| ||
01:41 | Add -DSQLITE_MAX_EXPR_DEPTH=0 to the --lean option on speed-check.sh. (check-in: a8cb1390fc 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: 8a6ea455cd 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: afac0709ce user: drh tags: trunk) | |
Changes
Changes to src/attach.c.
︙ | ︙ | |||
526 527 528 529 530 531 532 | if( pFix->pParse->db->init.busy ){ pExpr->op = TK_NULL; }else{ sqlite3ErrorMsg(pFix->pParse, "%s cannot use variables", pFix->zType); return 1; } } | | | 526 527 528 529 530 531 532 533 534 535 536 537 538 539 540 | if( pFix->pParse->db->init.busy ){ pExpr->op = TK_NULL; }else{ sqlite3ErrorMsg(pFix->pParse, "%s cannot use variables", pFix->zType); return 1; } } if( ExprHasProperty(pExpr, EP_TokenOnly|EP_Leaf) ) break; if( ExprHasProperty(pExpr, EP_xIsSelect) ){ if( sqlite3FixSelect(pFix, pExpr->x.pSelect) ) return 1; }else{ if( sqlite3FixExprList(pFix, pExpr->x.pList) ) return 1; } if( sqlite3FixExpr(pFix, pExpr->pRight) ){ return 1; |
︙ | ︙ |
Changes to src/expr.c.
︙ | ︙ | |||
1012 1013 1014 1015 1016 1017 1018 | /* ** Recursively delete an expression tree. */ static SQLITE_NOINLINE void sqlite3ExprDeleteNN(sqlite3 *db, Expr *p){ assert( p!=0 ); /* Sanity check: Assert that the IntValue is non-negative if it exists */ assert( !ExprHasProperty(p, EP_IntValue) || p->u.iValue>=0 ); | > > > > > > > | < > | 1012 1013 1014 1015 1016 1017 1018 1019 1020 1021 1022 1023 1024 1025 1026 1027 1028 1029 1030 1031 1032 1033 1034 1035 1036 1037 1038 1039 1040 1041 1042 1043 1044 | /* ** Recursively delete an expression tree. */ static SQLITE_NOINLINE void sqlite3ExprDeleteNN(sqlite3 *db, Expr *p){ assert( p!=0 ); /* Sanity check: Assert that the IntValue is non-negative if it exists */ assert( !ExprHasProperty(p, EP_IntValue) || p->u.iValue>=0 ); #ifdef SQLITE_DEBUG if( ExprHasProperty(p, EP_Leaf) && !ExprHasProperty(p, EP_TokenOnly) ){ assert( p->pLeft==0 ); assert( p->pRight==0 ); assert( p->x.pSelect==0 ); } #endif if( !ExprHasProperty(p, (EP_TokenOnly|EP_Leaf)) ){ /* The Expr.x union is never used at the same time as Expr.pRight */ assert( p->x.pList==0 || p->pRight==0 ); if( p->pLeft && p->op!=TK_SELECT_COLUMN ) sqlite3ExprDeleteNN(db, p->pLeft); sqlite3ExprDelete(db, p->pRight); if( ExprHasProperty(p, EP_xIsSelect) ){ sqlite3SelectDelete(db, p->x.pSelect); }else{ sqlite3ExprListDelete(db, p->x.pList); } } if( ExprHasProperty(p, EP_MemToken) ) sqlite3DbFree(db, p->u.zToken); if( !ExprHasProperty(p, EP_Static) ){ sqlite3DbFree(db, p); } } void sqlite3ExprDelete(sqlite3 *db, Expr *p){ if( p ) sqlite3ExprDeleteNN(db, p); } |
︙ | ︙ | |||
1200 1201 1202 1203 1204 1205 1206 | /* Copy the p->u.zToken string, if any. */ if( nToken ){ char *zToken = pNew->u.zToken = (char*)&zAlloc[nNewSize]; memcpy(zToken, p->u.zToken, nToken); } | | | | | 1207 1208 1209 1210 1211 1212 1213 1214 1215 1216 1217 1218 1219 1220 1221 1222 1223 1224 1225 1226 1227 1228 1229 1230 1231 1232 1233 1234 1235 1236 1237 1238 1239 1240 1241 1242 1243 | /* Copy the p->u.zToken string, if any. */ if( nToken ){ char *zToken = pNew->u.zToken = (char*)&zAlloc[nNewSize]; memcpy(zToken, p->u.zToken, nToken); } if( 0==((p->flags|pNew->flags) & (EP_TokenOnly|EP_Leaf)) ){ /* Fill in the pNew->x.pSelect or pNew->x.pList member. */ if( ExprHasProperty(p, EP_xIsSelect) ){ pNew->x.pSelect = sqlite3SelectDup(db, p->x.pSelect, dupFlags); }else{ pNew->x.pList = sqlite3ExprListDup(db, p->x.pList, dupFlags); } } /* Fill in pNew->pLeft and pNew->pRight. */ if( ExprHasProperty(pNew, EP_Reduced|EP_TokenOnly) ){ zAlloc += dupedExprNodeSize(p, dupFlags); if( !ExprHasProperty(pNew, EP_TokenOnly|EP_Leaf) ){ pNew->pLeft = p->pLeft ? exprDup(db, p->pLeft, EXPRDUP_REDUCE, &zAlloc) : 0; pNew->pRight = p->pRight ? exprDup(db, p->pRight, EXPRDUP_REDUCE, &zAlloc) : 0; } if( pzBuffer ){ *pzBuffer = zAlloc; } }else{ if( !ExprHasProperty(p, EP_TokenOnly|EP_Leaf) ){ if( pNew->op==TK_SELECT_COLUMN ){ pNew->pLeft = p->pLeft; }else{ pNew->pLeft = sqlite3ExprDup(db, p->pLeft, 0); } pNew->pRight = sqlite3ExprDup(db, p->pRight, 0); } |
︙ | ︙ |
Changes to src/parse.y.
︙ | ︙ | |||
850 851 852 853 854 855 856 857 858 859 860 861 862 863 | ** new Expr to populate pOut. Set the span of pOut to be the identifier ** that created the expression. */ static void spanExpr(ExprSpan *pOut, Parse *pParse, int op, Token t){ pOut->pExpr = sqlite3ExprAlloc(pParse->db, op, &t, 1); pOut->zStart = t.z; pOut->zEnd = &t.z[t.n]; } } expr(A) ::= term(A). expr(A) ::= LP(B) expr(X) RP(E). {spanSet(&A,&B,&E); /*A-overwrites-B*/ A.pExpr = X.pExpr;} term(A) ::= NULL(X). {spanExpr(&A,pParse,@X,X);/*A-overwrites-X*/} | > | 850 851 852 853 854 855 856 857 858 859 860 861 862 863 864 | ** new Expr to populate pOut. Set the span of pOut to be the identifier ** that created the expression. */ static void spanExpr(ExprSpan *pOut, Parse *pParse, int op, Token t){ pOut->pExpr = sqlite3ExprAlloc(pParse->db, op, &t, 1); pOut->zStart = t.z; pOut->zEnd = &t.z[t.n]; if( pOut->pExpr ) pOut->pExpr->flags |= EP_Leaf; } } expr(A) ::= term(A). expr(A) ::= LP(B) expr(X) RP(E). {spanSet(&A,&B,&E); /*A-overwrites-B*/ A.pExpr = X.pExpr;} term(A) ::= NULL(X). {spanExpr(&A,pParse,@X,X);/*A-overwrites-X*/} |
︙ | ︙ |
Changes to src/sqliteInt.h.
︙ | ︙ | |||
2334 2335 2336 2337 2338 2339 2340 2341 2342 2343 2344 2345 2346 2347 | #define EP_MemToken 0x010000 /* Need to sqlite3DbFree() Expr.zToken */ #define EP_NoReduce 0x020000 /* Cannot EXPRDUP_REDUCE this Expr */ #define EP_Unlikely 0x040000 /* unlikely() or likelihood() function */ #define EP_ConstFunc 0x080000 /* A SQLITE_FUNC_CONSTANT or _SLOCHNG function */ #define EP_CanBeNull 0x100000 /* Can be null despite NOT NULL constraint */ #define EP_Subquery 0x200000 /* Tree contains a TK_SELECT operator */ #define EP_Alias 0x400000 /* Is an alias for a result set column */ /* ** Combinations of two or more EP_* flags */ #define EP_Propagate (EP_Collate|EP_Subquery) /* Propagate these bits up tree */ /* | > | 2334 2335 2336 2337 2338 2339 2340 2341 2342 2343 2344 2345 2346 2347 2348 | #define EP_MemToken 0x010000 /* Need to sqlite3DbFree() Expr.zToken */ #define EP_NoReduce 0x020000 /* Cannot EXPRDUP_REDUCE this Expr */ #define EP_Unlikely 0x040000 /* unlikely() or likelihood() function */ #define EP_ConstFunc 0x080000 /* A SQLITE_FUNC_CONSTANT or _SLOCHNG function */ #define EP_CanBeNull 0x100000 /* Can be null despite NOT NULL constraint */ #define EP_Subquery 0x200000 /* Tree contains a TK_SELECT operator */ #define EP_Alias 0x400000 /* Is an alias for a result set column */ #define EP_Leaf 0x800000 /* Expr.pLeft, .pRight, .u.pSelect all NULL */ /* ** Combinations of two or more EP_* flags */ #define EP_Propagate (EP_Collate|EP_Subquery) /* Propagate these bits up tree */ /* |
︙ | ︙ |
Changes to src/walker.c.
︙ | ︙ | |||
37 38 39 40 41 42 43 | ** and WRC_Continue to continue. */ static SQLITE_NOINLINE int walkExpr(Walker *pWalker, Expr *pExpr){ int rc; testcase( ExprHasProperty(pExpr, EP_TokenOnly) ); testcase( ExprHasProperty(pExpr, EP_Reduced) ); rc = pWalker->xExprCallback(pWalker, pExpr); | | > > | 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 | ** and WRC_Continue to continue. */ static SQLITE_NOINLINE int walkExpr(Walker *pWalker, Expr *pExpr){ int rc; testcase( ExprHasProperty(pExpr, EP_TokenOnly) ); testcase( ExprHasProperty(pExpr, EP_Reduced) ); rc = pWalker->xExprCallback(pWalker, pExpr); if( rc || ExprHasProperty(pExpr,(EP_TokenOnly|EP_Leaf)) ){ return rc & WRC_Abort; } if( pExpr->pLeft && walkExpr(pWalker, pExpr->pLeft) ) return WRC_Abort; if( pExpr->pRight && walkExpr(pWalker, pExpr->pRight) ) return WRC_Abort; if( ExprHasProperty(pExpr, EP_xIsSelect) ){ if( sqlite3WalkSelect(pWalker, pExpr->x.pSelect) ) return WRC_Abort; }else if( pExpr->x.pList ){ if( sqlite3WalkExprList(pWalker, pExpr->x.pList) ) return WRC_Abort; } |
︙ | ︙ |