From 39a7c34242d00afe13d4db2905f161ce820f5132 Mon Sep 17 00:00:00 2001 From: drh Date: Tue, 4 Dec 2018 01:18:36 +0000 Subject: [PATCH] Attempt to make the parser a little faster by storing the ON and USING clause in a single OnUsing object. FossilOrigin-Name: 6770ed0873a0f152bae5849c0e596d46173fd480bb8f07cb90d07739ba2cafb5 --- manifest | 21 ++++++++++++--------- manifest.uuid | 2 +- src/build.c | 16 ++++++++-------- src/parse.y | 41 ++++++++++++++++++++--------------------- src/select.c | 12 +++++------- src/sqliteInt.h | 18 +++++++++++++++++- 6 files changed, 63 insertions(+), 47 deletions(-) diff --git a/manifest b/manifest index da9de6931b..554b2581ec 100644 --- a/manifest +++ b/manifest @@ -1,5 +1,5 @@ -C Reduce\sthe\ssize\sof\sthe\sparser\stables\sgenerated\sby\sLemon\sby\ssplitting\sthe\nyyRuleInfo\sstructure\sinto\sseparate\syyRuleInfoLhs\sand\syyRuleInfoNRhs\sarrays. -D 2018-12-03T23:57:27.083 +C Attempt\sto\smake\sthe\sparser\sa\slittle\sfaster\sby\sstoring\sthe\sON\sand\sUSING\nclause\sin\sa\ssingle\sOnUsing\sobject. +D 2018-12-04T01:18:36.851 F .fossil-settings/empty-dirs dbb81e8fc0401ac46a1491ab34a7f2c7c0452f2f06b54ebb845d024ca8283ef1 F .fossil-settings/ignore-glob 35175cdfcf539b2318cb04a9901442804be81cd677d8b889fcc9149c21f239ea F Makefile.in a050c8670ea0d7b37b2192306cbb50d392acd9902b84e9b56f3444d006f97a6c @@ -451,7 +451,7 @@ F src/btmutex.c 8acc2f464ee76324bf13310df5692a262b801808984c1b79defb2503bbafadb6 F src/btree.c ba7c7eef4461790f37c309936bfc5d0d6ba9b194b02d3c8ff1fd53b420ea6d3b F src/btree.h febb2e817be499570b7a2e32a9bbb4b607a9234f6b84bb9ae84916d4806e96f2 F src/btreeInt.h 620ab4c7235f43572cf3ac2ac8723cbdf68073be4d29da24897c7b77dda5fd96 -F src/build.c fce47a9789704e65c63299b01be8153745faee7919f5137d3f29b7c3c0b549bd +F src/build.c 0bd866f9ac68f823d8a93e3c6464be687960132ac44c9435fd1a5e3b942086f9 F src/callback.c 789bd33d188146f66c0dd8306472a72d1c05f71924b24a91caf6bd45cf9aba73 F src/complete.c a3634ab1e687055cd002e11b8f43eb75c17da23e F src/ctime.c 109e58d00f62e8e71ee1eb5944ac18b90171c928ab2e082e058056e1137cc20b @@ -496,7 +496,7 @@ F src/os_win.c 85d9e532d0444ab6c16d7431490c2e279e282aa0917b0e988996b1ae0de5c5a0 F src/os_win.h 7b073010f1451abe501be30d12f6bc599824944a F src/pager.c 75e0f3cfa3962c714f519f8a3d1e67ecca1c91de0e010a036b988e40ce9e4c73 F src/pager.h 217921e81eb5fe455caa5cda96061959706bcdd29ddb57166198645ef7822ac3 -F src/parse.y 5cf85c2b9dfac38ac4e2bf2776484705186ce2eda8631e65cc0b04bf566c1173 +F src/parse.y c4da3ae9f0482f5916849b58a93d702625376c452bdd4be4bd42798f83ff7e4a F src/pcache.c 696a01f1a6370c1b50a09c15972bc3bee3333f8fcd1f2da8e9a76b1b062c59ee F src/pcache.h 4f87acd914cef5016fae3030343540d75f5b85a1877eed1a2a19b9f284248586 F src/pcache1.c ad0ffc5b35b0280d045ac569d34d4b842e3e6a4a118f6396b320987a0957afcc @@ -507,12 +507,12 @@ F src/printf.c 0f1177cf1dd4d7827bf64d840768514ec76409abecaca9e8b577dbd065150381 F src/random.c 80f5d666f23feb3e6665a6ce04c7197212a88384 F src/resolve.c 976e7879286a1eecdc71ceff64f6d1b3f58c8f8096537ba668b3dc0887f410c1 F src/rowset.c d977b011993aaea002cab3e0bb2ce50cf346000dff94e944d547b989f4b1fe93 -F src/select.c 61e867a906f140b73baf4ce7a201ad6dcba30820969f5618ee40e9a0d32c6f5f +F src/select.c 8a0fb4fd971c0364006f6a69b56aced36a773956483acfcc260e83b49e8c0da5 F src/shell.c.in 482e23a370cbe5b0d4c73a0f0f5fce34f7caa08a14a8d75e12f0225c4e14915c F src/sqlite.h.in cce9feede1c1c03923c091b4bbbd081dd77aaf92024cc2cdbf65f712c2f668c3 F src/sqlite3.rc 5121c9e10c3964d5755191c80dd1180c122fc3a8 F src/sqlite3ext.h 960f1b86c3610fa23cb6a267572a97dcf286e77aa0dd3b9b23292ffaa1ea8683 -F src/sqliteInt.h 1161f7579cdd6217737a66517ef27f4016426603eff492e9b31f45a7d7d4c61f +F src/sqliteInt.h 1e26dff5cb1b0805ac2f8e775b1ef5bb8d3f082db30b64eeaf2341263036aae7 F src/sqliteLimit.h 1513bfb7b20378aa0041e7022d04acb73525de35b80b252f1b83fedb4de6a76b F src/status.c 46e7aec11f79dad50965a5ca5fa9de009f7d6bde08be2156f1538a0a296d4d0e F src/table.c b46ad567748f24a326d9de40e5b9659f96ffff34 @@ -1781,7 +1781,10 @@ F vsixtest/vsixtest.tcl 6a9a6ab600c25a91a7acc6293828957a386a8a93 F vsixtest/vsixtest.vcxproj.data 2ed517e100c66dc455b492e1a33350c1b20fbcdc F vsixtest/vsixtest.vcxproj.filters 37e51ffedcdb064aad6ff33b6148725226cd608e F vsixtest/vsixtest_TemporaryKey.pfx e5b1b036facdb453873e7084e1cae9102ccc67a0 -P 7149dacf1d440a19f62808b4591c3fa8da202b2ec742d5490a63f2ec005ff9e7 -R 457633af26ab8489c6f274ab3a7ad9fc +P 70fe8ec2ae3099b8773834c7ac2e56768addbecd57956ac523e71a7dc264049c +R ba0d657988bc149b80ac7a1558e95ccf +T *branch * on-using-opt +T *sym-on-using-opt * +T -sym-trunk * U drh -Z 7836770a12b5a3ad0791dca5d89f1095 +Z c13436380c54aa625889c6261f0708c3 diff --git a/manifest.uuid b/manifest.uuid index 30bc9f4cbf..b0f110d79d 100644 --- a/manifest.uuid +++ b/manifest.uuid @@ -1 +1 @@ -70fe8ec2ae3099b8773834c7ac2e56768addbecd57956ac523e71a7dc264049c \ No newline at end of file +6770ed0873a0f152bae5849c0e596d46173fd480bb8f07cb90d07739ba2cafb5 \ No newline at end of file diff --git a/src/build.c b/src/build.c index ad1421d195..806a93ed71 100644 --- a/src/build.c +++ b/src/build.c @@ -4017,14 +4017,14 @@ SrcList *sqlite3SrcListAppendFromTerm( Token *pDatabase, /* Name of the database containing pTable */ Token *pAlias, /* The right-hand side of the AS subexpression */ Select *pSubquery, /* A subquery used in place of a table name */ - Expr *pOn, /* The ON clause of a join */ - IdList *pUsing /* The USING clause of a join */ + const OnUsing *pOnUsing /* The ON or USING clause */ ){ struct SrcList_item *pItem; sqlite3 *db = pParse->db; - if( !p && (pOn || pUsing) ){ + assert( pOnUsing!=0 ); + if( !p && (pOnUsing->pOn || pOnUsing->pUsing) ){ sqlite3ErrorMsg(pParse, "a JOIN clause is required before %s", - (pOn ? "ON" : "USING") + (pOnUsing->pOn ? "ON" : "USING") ); goto append_from_error; } @@ -4045,14 +4045,14 @@ SrcList *sqlite3SrcListAppendFromTerm( pItem->zAlias = sqlite3NameFromToken(db, pAlias); } pItem->pSelect = pSubquery; - pItem->pOn = pOn; - pItem->pUsing = pUsing; + pItem->pOn = pOnUsing->pOn; + pItem->pUsing = pOnUsing->pUsing; return p; append_from_error: assert( p==0 ); - sqlite3ExprDelete(db, pOn); - sqlite3IdListDelete(db, pUsing); + sqlite3ExprDelete(db, pOnUsing->pOn); + sqlite3IdListDelete(db, pOnUsing->pUsing); sqlite3SelectDelete(db, pSubquery); return 0; } diff --git a/src/parse.y b/src/parse.y index 3bb28ab5f5..a58c3ebc2c 100644 --- a/src/parse.y +++ b/src/parse.y @@ -508,11 +508,12 @@ selectnowith(A) ::= selectnowith(A) multiselect_op(Y) oneselect(Z). { Select *pRhs = Z; Select *pLhs = A; if( pRhs && pRhs->pPrior ){ + static const OnUsing nullOnUsing = { 0, 0 }; SrcList *pFrom; Token x; x.n = 0; parserDoubleLinkSelect(pParse, pRhs); - pFrom = sqlite3SrcListAppendFromTerm(pParse,0,0,0,&x,pRhs,0,0); + pFrom = sqlite3SrcListAppendFromTerm(pParse,0,0,0,&x,pRhs,&nullOnUsing); pRhs = sqlite3SelectNew(pParse,0,pFrom,0,0,0,0,0,0); } if( pRhs ){ @@ -638,26 +639,26 @@ stl_prefix(A) ::= seltablist(A) joinop(Y). { } stl_prefix(A) ::= . {A = 0;} seltablist(A) ::= stl_prefix(A) nm(Y) dbnm(D) as(Z) indexed_opt(I) - on_opt(N) using_opt(U). { - A = sqlite3SrcListAppendFromTerm(pParse,A,&Y,&D,&Z,0,N,U); + onusing(U). { + A = sqlite3SrcListAppendFromTerm(pParse,A,&Y,&D,&Z,0,&U); sqlite3SrcListIndexedBy(pParse, A, &I); } seltablist(A) ::= stl_prefix(A) nm(Y) dbnm(D) LP exprlist(E) RP as(Z) - on_opt(N) using_opt(U). { - A = sqlite3SrcListAppendFromTerm(pParse,A,&Y,&D,&Z,0,N,U); + onusing(U). { + A = sqlite3SrcListAppendFromTerm(pParse,A,&Y,&D,&Z,0,&U); sqlite3SrcListFuncArgs(pParse, A, E); } %ifndef SQLITE_OMIT_SUBQUERY seltablist(A) ::= stl_prefix(A) LP select(S) RP - as(Z) on_opt(N) using_opt(U). { - A = sqlite3SrcListAppendFromTerm(pParse,A,0,0,&Z,S,N,U); + as(Z) onusing(U). { + A = sqlite3SrcListAppendFromTerm(pParse,A,0,0,&Z,S,&U); } seltablist(A) ::= stl_prefix(A) LP seltablist(F) RP - as(Z) on_opt(N) using_opt(U). { - if( A==0 && Z.n==0 && N==0 && U==0 ){ + as(Z) onusing(U). { + if( A==0 && Z.n==0 && U.pOn==0 && U.pUsing==0 ){ A = F; }else if( F->nSrc==1 ){ - A = sqlite3SrcListAppendFromTerm(pParse,A,0,0,&Z,0,N,U); + A = sqlite3SrcListAppendFromTerm(pParse,A,0,0,&Z,0,&U); if( A ){ struct SrcList_item *pNew = &A->a[A->nSrc-1]; struct SrcList_item *pOld = F->a; @@ -678,7 +679,7 @@ seltablist(A) ::= stl_prefix(A) nm(Y) dbnm(D) LP exprlist(E) RP as(Z) Select *pSubquery; sqlite3SrcListShiftJoinType(F); pSubquery = sqlite3SelectNew(pParse,0,F,0,0,0,0,SF_NestedFrom,0); - A = sqlite3SrcListAppendFromTerm(pParse,A,0,0,&Z,pSubquery,N,U); + A = sqlite3SrcListAppendFromTerm(pParse,A,0,0,&Z,pSubquery,&U); } } %endif SQLITE_OMIT_SUBQUERY @@ -739,10 +740,14 @@ joinop(X) ::= JOIN_KW(A) nm(B) nm(C) JOIN. // The [AND] and [OR] precedence marks in the rules for on_opt cause the // ON in this context to always be interpreted as belonging to the JOIN. // -%type on_opt {Expr*} -%destructor on_opt {sqlite3ExprDelete(pParse->db, $$);} -on_opt(N) ::= ON expr(E). {N = E;} -on_opt(N) ::= . [OR] {N = 0;} +%type onusing {OnUsing} +%destructor onusing { + sqlite3ExprDelete(pParse->db, $$.pOn); + sqlite3IdListDelete(pParse->db, $$.pUsing); +} +onusing(A) ::= . [OR] {A.pOn = 0; A.pUsing = 0;} +onusing(A) ::= ON expr(E). {A.pOn = E; A.pUsing = 0;} +onusing(A) ::= USING LP idlist(L) RP. {A.pOn = 0; A.pUsing=L;} // Note that this block abuses the Token type just a little. If there is // no "INDEXED BY" clause, the returned token is empty (z==0 && n==0). If @@ -759,12 +764,6 @@ indexed_opt(A) ::= . {A.z=0; A.n=0;} indexed_opt(A) ::= INDEXED BY nm(X). {A = X;} indexed_opt(A) ::= NOT INDEXED. {A.z=0; A.n=1;} -%type using_opt {IdList*} -%destructor using_opt {sqlite3IdListDelete(pParse->db, $$);} -using_opt(U) ::= USING LP idlist(L) RP. {U = L;} -using_opt(U) ::= . {U = 0;} - - %type orderby_opt {ExprList*} %destructor orderby_opt {sqlite3ExprListDelete(pParse->db, $$);} diff --git a/src/select.c b/src/select.c index c60ff27001..d75afacdad 100644 --- a/src/select.c +++ b/src/select.c @@ -476,13 +476,10 @@ static int sqliteProcessJoin(Parse *pParse, Select *p){ } } - /* Disallow both ON and USING clauses in the same join + /* Cannot both ON and USING clauses in the same join. The parser + ** does not allow this. */ - if( pRight->pOn && pRight->pUsing ){ - sqlite3ErrorMsg(pParse, "cannot have both ON and USING " - "clauses in the same join"); - return 1; - } + assert( pRight->pOn==0 || pRight->pUsing==0 ); /* Add the ON clause to the end of the WHERE clause, connected by ** an AND operator. @@ -4507,6 +4504,7 @@ static int convertCompoundSelectToSubquery(Walker *pWalker, Select *p){ SrcList *pNewSrc; Parse *pParse; Token dummy; + static const OnUsing nullOnUsing = { 0, 0 }; if( p->pPrior==0 ) return WRC_Continue; if( p->pOrderBy==0 ) return WRC_Continue; @@ -4525,7 +4523,7 @@ static int convertCompoundSelectToSubquery(Walker *pWalker, Select *p){ pNew = sqlite3DbMallocZero(db, sizeof(*pNew) ); if( pNew==0 ) return WRC_Abort; memset(&dummy, 0, sizeof(dummy)); - pNewSrc = sqlite3SrcListAppendFromTerm(pParse,0,0,0,&dummy,pNew,0,0); + pNewSrc = sqlite3SrcListAppendFromTerm(pParse,0,0,0,&dummy,pNew,&nullOnUsing); if( pNewSrc==0 ) return WRC_Abort; *pNew = *p; p->pSrc = pNewSrc; diff --git a/src/sqliteInt.h b/src/sqliteInt.h index 051aa40382..fcdd268651 100644 --- a/src/sqliteInt.h +++ b/src/sqliteInt.h @@ -1085,6 +1085,7 @@ typedef struct Lookaside Lookaside; typedef struct LookasideSlot LookasideSlot; typedef struct Module Module; typedef struct NameContext NameContext; +typedef struct OnUsing OnUsing; typedef struct Parse Parse; typedef struct PreUpdate PreUpdate; typedef struct PrintfArguments PrintfArguments; @@ -2615,6 +2616,21 @@ struct IdList { int nId; /* Number of identifiers on the list */ }; +/* +** An instance of the following structure records the ON and USING clauses +** as part of a join. +** +** ON expr USING exprlist +** +** The parser uses a single instance of this object to hold both elements +** as a performance optimization - to reduce the number of "reduce" actions +** required in the parser automaton. +*/ +struct OnUsing { + Expr *pOn; + IdList *pUsing; +}; + /* ** The following structure describes the FROM clause of a SELECT statement. ** Each table or subquery in the FROM clause is a separate element of @@ -3918,7 +3934,7 @@ int sqlite3IdListIndex(IdList*,const char*); SrcList *sqlite3SrcListEnlarge(sqlite3*, SrcList*, int, int); SrcList *sqlite3SrcListAppend(sqlite3*, SrcList*, Token*, Token*); SrcList *sqlite3SrcListAppendFromTerm(Parse*, SrcList*, Token*, Token*, - Token*, Select*, Expr*, IdList*); + Token*, Select*, const OnUsing*); void sqlite3SrcListIndexedBy(Parse *, SrcList *, Token *); void sqlite3SrcListFuncArgs(Parse*, SrcList*, ExprList*); int sqlite3IndexedByLookup(Parse *, struct SrcList_item *); -- 2.39.5