From 6f32848d619dbcd0ca213b2c815bc39bb6587986 Mon Sep 17 00:00:00 2001 From: drh Date: Wed, 5 Jun 2013 23:39:34 +0000 Subject: [PATCH] Move the definitions of the WhereLevel and WhereInfo objects out of sqliteInt.h and into where.c. This will facilitate future refactoring of the internal query planner data structures. FossilOrigin-Name: 1574653b9b4522b489d4c62d9cf70166bb3bddfd --- manifest | 18 ++++---- manifest.uuid | 2 +- src/select.c | 19 +++++--- src/sqliteInt.h | 74 +++--------------------------- src/update.c | 2 +- src/where.c | 117 ++++++++++++++++++++++++++++++++++++++++++++++++ 6 files changed, 146 insertions(+), 86 deletions(-) diff --git a/manifest b/manifest index 68794b6938..3602c781f7 100644 --- a/manifest +++ b/manifest @@ -1,5 +1,5 @@ -C Performance\simprovement\sfor\sthe\sOR-clause\sanalysis\sin\sthe\sNGQP. -D 2013-06-05T17:53:43.355 +C Move\sthe\sdefinitions\sof\sthe\sWhereLevel\sand\sWhereInfo\sobjects\sout\sof\nsqliteInt.h\sand\sinto\swhere.c.\s\sThis\swill\sfacilitate\sfuture\srefactoring\nof\sthe\sinternal\squery\splanner\sdata\sstructures. +D 2013-06-05T23:39:34.316 F Makefile.arm-wince-mingw32ce-gcc d6df77f1f48d690bd73162294bbba7f59507c72f F Makefile.in 5e41da95d92656a5004b03d3576e8b226858a28e F Makefile.linux-gcc 91d710bdc4998cb015f39edf3cb314ec4f4d7e23 @@ -215,12 +215,12 @@ F src/printf.c bff529ed47657098c55c9910b9c69b1b3b1a1353 F src/random.c cd4a67b3953b88019f8cd4ccd81394a8ddfaba50 F src/resolve.c 89f9003e8316ee3a172795459efc2a0274e1d5a8 F src/rowset.c 64655f1a627c9c212d9ab497899e7424a34222e0 -F src/select.c 22ee971346a736ddefdc4497d07c92f2e9978afc +F src/select.c 5e8fe15b1c5b2cc592880d3f039c6a6da55bf253 F src/shell.c ab6eea968c8745be3aa74e45fedb37d057b4cd0d F src/sqlite.h.in 5b390ca5d94e09e56e7fee6a51ddde4721b89f8e F src/sqlite3.rc fea433eb0a59f4c9393c8e6d76a6e2596b1fe0c0 F src/sqlite3ext.h d936f797812c28b81b26ed18345baf8db28a21a5 -F src/sqliteInt.h 259d999abebf4498615e9237a18c0815257a1f2f +F src/sqliteInt.h 7b85b09d746cde295c7a0f60711421a28f5c4905 F src/sqliteLimit.h 164b0e6749d31e0daa1a4589a169d31c0dec7b3d F src/status.c bedc37ec1a6bb9399944024d63f4c769971955a9 F src/table.c 2cd62736f845d82200acfa1287e33feb3c15d62e @@ -272,7 +272,7 @@ F src/test_vfstrace.c 34b544e80ba7fb77be15395a609c669df2e660a2 F src/test_wsd.c 41cadfd9d97fe8e3e4e44f61a4a8ccd6f7ca8fe9 F src/tokenize.c 1e86210d3976717a19238ea7b047fac481fe8c12 F src/trigger.c 5c0ea9b8755e7c5e1a700f3e27ac4f8d92dd221e -F src/update.c 4c0c6864c4349ba292042e984a56d15985b57f4e +F src/update.c 8e76c3d03e4b7b21cb250bd2df0c05e12993e577 F src/utf.c 8d819e2e5104a430fc2005f018db14347c95a38f F src/util.c f566b5138099a2df8533b190d0dcc74b7dfbe0c9 F src/vacuum.c ddf21cc9577c4cb459d08bee9863a78ec000c5bb @@ -289,7 +289,7 @@ F src/vtab.c b05e5f1f4902461ba9f5fc49bb7eb7c3a0741a83 F src/wal.c 436bfceb141b9423c45119e68e444358ee0ed35d F src/wal.h df01efe09c5cb8c8e391ff1715cca294f89668a4 F src/walker.c 4fa43583d0a84b48f93b1e88f11adf2065be4e73 -F src/where.c 35e510bf0de4925316934e0ae989db9d062069d5 +F src/where.c 83c6fce38c5c22a1573bc3acbc0d1241a140331a F test/8_3_names.test ebbb5cd36741350040fd28b432ceadf495be25b2 F test/aggerror.test a867e273ef9e3d7919f03ef4f0e8c0d2767944f2 F test/aggnested.test 45c0201e28045ad38a530b5a144b73cd4aa2cfd6 @@ -1094,7 +1094,7 @@ F tool/vdbe-compress.tcl f12c884766bd14277f4fcedcae07078011717381 F tool/warnings-clang.sh f6aa929dc20ef1f856af04a730772f59283631d4 F tool/warnings.sh fbc018d67fd7395f440c28f33ef0f94420226381 F tool/win/sqlite.vsix 97894c2790eda7b5bce3cc79cb2a8ec2fde9b3ac -P cbef38c2d123e7d5a02c2a2450e8b329e3e96ee9 -R 0e9737367b7d6db3cdf59c7691a34aed +P 9b1c4954e468d0acfb5787e6bff56d50a3e7bc1a +R 2a5a6c03912e176e1d2592bfb6917650 U drh -Z 4606f36521508d3eb4fac531dd74f101 +Z 58f6e83bb7528a16d0e3d3a98418299b diff --git a/manifest.uuid b/manifest.uuid index 0a8e044566..abc266545e 100644 --- a/manifest.uuid +++ b/manifest.uuid @@ -1 +1 @@ -9b1c4954e468d0acfb5787e6bff56d50a3e7bc1a \ No newline at end of file +1574653b9b4522b489d4c62d9cf70166bb3bddfd \ No newline at end of file diff --git a/src/select.c b/src/select.c index 9705c19058..d160513bd3 100644 --- a/src/select.c +++ b/src/select.c @@ -4267,9 +4267,13 @@ int sqlite3Select( /* Begin the database scan. */ pWInfo = sqlite3WhereBegin(pParse, pTabList, pWhere, pOrderBy, pDist, 0,0); if( pWInfo==0 ) goto select_end; - if( pWInfo->nRowOut < p->nSelectRow ) p->nSelectRow = pWInfo->nRowOut; - if( pWInfo->eDistinct ) sDistinct.eTnctType = pWInfo->eDistinct; - if( pOrderBy && pWInfo->nOBSat==pOrderBy->nExpr ) pOrderBy = 0; + if( sqlite3WhereOutputRowCount(pWInfo) < p->nSelectRow ){ + p->nSelectRow = sqlite3WhereOutputRowCount(pWInfo); + } + if( sqlite3WhereIsDistinct(pWInfo) ){ + sDistinct.eTnctType = sqlite3WhereIsDistinct(pWInfo); + } + if( pOrderBy && sqlite3WhereIsOrdered(pWInfo) ) pOrderBy = 0; /* If sorting index that was created by a prior OP_OpenEphemeral ** instruction ended up not being needed, then change the OP_OpenEphemeral @@ -4282,7 +4286,8 @@ int sqlite3Select( /* Use the standard inner loop. */ selectInnerLoop(pParse, p, pEList, 0, 0, pOrderBy, &sDistinct, pDest, - pWInfo->iContinue, pWInfo->iBreak); + sqlite3WhereContinueLabel(pWInfo), + sqlite3WhereBreakLabel(pWInfo)); /* End the database scan loop. */ @@ -4399,7 +4404,7 @@ int sqlite3Select( sqlite3VdbeAddOp2(v, OP_Gosub, regReset, addrReset); pWInfo = sqlite3WhereBegin(pParse, pTabList, pWhere, pGroupBy, 0, 0, 0); if( pWInfo==0 ) goto select_end; - if( pWInfo->nOBSat==pGroupBy->nExpr ){ + if( sqlite3WhereIsOrdered(pWInfo) ){ /* The optimizer is able to deliver rows in group by order so ** we do not have to sort. The OP_OpenEphemeral table will be ** cancelled later because we still need to use the pKeyInfo @@ -4680,8 +4685,8 @@ int sqlite3Select( } updateAccumulator(pParse, &sAggInfo); assert( pMinMax==0 || pMinMax->nExpr==1 ); - if( pWInfo->nOBSat>0 ){ - sqlite3VdbeAddOp2(v, OP_Goto, 0, pWInfo->iBreak); + if( sqlite3WhereIsOrdered(pWInfo) ){ + sqlite3VdbeAddOp2(v, OP_Goto, 0, sqlite3WhereBreakLabel(pWInfo)); VdbeComment((v, "%s() by index", (flag==WHERE_ORDERBY_MIN?"min":"max"))); } diff --git a/src/sqliteInt.h b/src/sqliteInt.h index 2b07d2ef02..76835385fb 100644 --- a/src/sqliteInt.h +++ b/src/sqliteInt.h @@ -721,7 +721,6 @@ typedef struct VTable VTable; typedef struct VtabCtx VtabCtx; typedef struct Walker Walker; typedef struct WhereInfo WhereInfo; -typedef struct WhereLevel WhereLevel; /* ** Defer sourcing vdbe.h and btree.h until after the "u8" and @@ -1954,44 +1953,6 @@ struct SrcList { #define JT_ERROR 0x0040 /* unknown or unsupported join type */ -/* -** For each nested loop in a WHERE clause implementation, the WhereInfo -** structure contains a single instance of this structure. This structure -** is intended to be private to the where.c module and should not be -** access or modified by other modules. -** -** The pIdxInfo field is used to help pick the best index on a -** virtual table. The pIdxInfo pointer contains indexing -** information for the i-th table in the FROM clause before reordering. -** All the pIdxInfo pointers are freed by whereInfoFree() in where.c. -** All other information in the i-th WhereLevel object for the i-th table -** after FROM clause ordering. -*/ -struct WhereLevel { - int iLeftJoin; /* Memory cell used to implement LEFT OUTER JOIN */ - int iTabCur; /* The VDBE cursor used to access the table */ - int iIdxCur; /* The VDBE cursor used to access pIdx */ - int addrBrk; /* Jump here to break out of the loop */ - int addrNxt; /* Jump here to start the next IN combination */ - int addrCont; /* Jump here to continue with the next loop cycle */ - int addrFirst; /* First instruction of interior of the loop */ - u8 iFrom; /* FIXME: Which entry in the FROM clause */ - u8 op, p5; /* Opcode and P5 of the opcode that ends the loop */ - int p1, p2; /* Operands of the opcode used to ends the loop */ - union { /* Information that depends on plan.wsFlags */ - struct { - int nIn; /* Number of entries in aInLoop[] */ - struct InLoop { - int iCur; /* The VDBE cursor used by this IN operator */ - int addrInTop; /* Top of the IN loop */ - u8 eEndLoopOp; /* IN Loop terminator. OP_Next or OP_Prev */ - } *aInLoop; /* Information about each nested IN operator */ - } in; /* Used when plan.wsFlags&WHERE_IN_ABLE */ - Index *pCovidx; /* Possible covering index for WHERE_MULTI_OR */ - } u; - struct WhereLoop *pWLoop; /* The selected WhereLoop object */ -}; - /* ** Flags appropriate for the wctrlFlags parameter of sqlite3WhereBegin() ** and the WhereInfo.wctrlFlags member. @@ -2007,35 +1968,6 @@ struct WhereLevel { #define WHERE_AND_ONLY 0x0080 /* Don't use indices for OR terms */ #define WHERE_GROUPBY 0x0100 /* pOrderBy is really a GROUP BY */ -/* -** The WHERE clause processing routine has two halves. The -** first part does the start of the WHERE loop and the second -** half does the tail of the WHERE loop. An instance of -** this structure is returned by the first half and passed -** into the second half to give some continuity. -*/ -struct WhereInfo { - Parse *pParse; /* Parsing and code generating context */ - SrcList *pTabList; /* List of tables in the join */ - ExprList *pOrderBy; /* The ORDER BY clause or NULL */ - ExprList *pDistinct; /* DISTINCT ON values, or NULL */ - Bitmask revMask; /* Mask of ORDER BY terms that need reversing */ - u16 nOBSat; /* Number of ORDER BY terms satisfied by indices */ - u16 wctrlFlags; /* Flags originally passed to sqlite3WhereBegin() */ - u8 okOnePass; /* Ok to use one-pass algorithm for UPDATE/DELETE */ - u8 untestedTerms; /* Not all WHERE terms resolved by outer loop */ - u8 eDistinct; /* One of the WHERE_DISTINCT_* values below */ - int iTop; /* The very beginning of the WHERE loop */ - int iContinue; /* Jump here to continue with next record */ - int iBreak; /* Jump here to break out of the loop */ - int nLevel; /* Number of nested loop */ - struct WhereClause *pWC; /* Decomposition of the WHERE clause */ - struct WhereLoop *pLoops; /* List of all WhereLoop objects */ - double savedNQueryLoop; /* pParse->nQueryLoop outside the WHERE loop */ - double nRowOut; /* Estimated number of output rows */ - WhereLevel a[1]; /* Information about each nest loop in WHERE */ -}; - /* Allowed values for WhereInfo.eDistinct and DistinctCtx.eTnctType */ #define WHERE_DISTINCT_NOOP 0 /* DISTINCT keyword not used */ #define WHERE_DISTINCT_UNIQUE 1 /* No duplicates */ @@ -2864,6 +2796,12 @@ void sqlite3DeleteFrom(Parse*, SrcList*, Expr*); void sqlite3Update(Parse*, SrcList*, ExprList*, Expr*, int); WhereInfo *sqlite3WhereBegin(Parse*,SrcList*,Expr*,ExprList*,ExprList*,u16,int); void sqlite3WhereEnd(WhereInfo*); +double sqlite3WhereOutputRowCount(WhereInfo*); +int sqlite3WhereIsDistinct(WhereInfo*); +int sqlite3WhereIsOrdered(WhereInfo*); +int sqlite3WhereContinueLabel(WhereInfo*); +int sqlite3WhereBreakLabel(WhereInfo*); +int sqlite3WhereOkOnePass(WhereInfo*); int sqlite3ExprCodeGetColumn(Parse*, Table*, int, int, int, u8); void sqlite3ExprCodeGetColumnOfTable(Vdbe*, Table*, int, int, int); void sqlite3ExprCodeMove(Parse*, int, int, int); diff --git a/src/update.c b/src/update.c index 3ab1ab2a4b..5b18ebd6bf 100644 --- a/src/update.c +++ b/src/update.c @@ -318,7 +318,7 @@ void sqlite3Update( pParse, pTabList, pWhere, 0, 0, WHERE_ONEPASS_DESIRED, 0 ); if( pWInfo==0 ) goto update_cleanup; - okOnePass = pWInfo->okOnePass; + okOnePass = sqlite3WhereOkOnePass(pWInfo); /* Remember the rowid of every item to be updated. */ diff --git a/src/where.c b/src/where.c index 342c9ac721..4d03776bf2 100644 --- a/src/where.c +++ b/src/where.c @@ -39,6 +39,7 @@ typedef struct WhereClause WhereClause; typedef struct WhereMaskSet WhereMaskSet; typedef struct WhereOrInfo WhereOrInfo; typedef struct WhereAndInfo WhereAndInfo; +typedef struct WhereLevel WhereLevel; typedef struct WhereLoop WhereLoop; typedef struct WherePath WherePath; typedef struct WhereTerm WhereTerm; @@ -47,6 +48,73 @@ typedef struct WhereScan WhereScan; typedef struct WhereVtabPlan WhereVtabPlan; +/* +** For each nested loop in a WHERE clause implementation, the WhereInfo +** structure contains a single instance of this structure. This structure +** is intended to be private to the where.c module and should not be +** access or modified by other modules. +** +** The pIdxInfo field is used to help pick the best index on a +** virtual table. The pIdxInfo pointer contains indexing +** information for the i-th table in the FROM clause before reordering. +** All the pIdxInfo pointers are freed by whereInfoFree() in where.c. +** All other information in the i-th WhereLevel object for the i-th table +** after FROM clause ordering. +*/ +struct WhereLevel { + int iLeftJoin; /* Memory cell used to implement LEFT OUTER JOIN */ + int iTabCur; /* The VDBE cursor used to access the table */ + int iIdxCur; /* The VDBE cursor used to access pIdx */ + int addrBrk; /* Jump here to break out of the loop */ + int addrNxt; /* Jump here to start the next IN combination */ + int addrCont; /* Jump here to continue with the next loop cycle */ + int addrFirst; /* First instruction of interior of the loop */ + u8 iFrom; /* FIXME: Which entry in the FROM clause */ + u8 op, p5; /* Opcode and P5 of the opcode that ends the loop */ + int p1, p2; /* Operands of the opcode used to ends the loop */ + union { /* Information that depends on plan.wsFlags */ + struct { + int nIn; /* Number of entries in aInLoop[] */ + struct InLoop { + int iCur; /* The VDBE cursor used by this IN operator */ + int addrInTop; /* Top of the IN loop */ + u8 eEndLoopOp; /* IN Loop terminator. OP_Next or OP_Prev */ + } *aInLoop; /* Information about each nested IN operator */ + } in; /* Used when plan.wsFlags&WHERE_IN_ABLE */ + Index *pCovidx; /* Possible covering index for WHERE_MULTI_OR */ + } u; + struct WhereLoop *pWLoop; /* The selected WhereLoop object */ +}; + +/* +** The WHERE clause processing routine has two halves. The +** first part does the start of the WHERE loop and the second +** half does the tail of the WHERE loop. An instance of +** this structure is returned by the first half and passed +** into the second half to give some continuity. +*/ +struct WhereInfo { + Parse *pParse; /* Parsing and code generating context */ + SrcList *pTabList; /* List of tables in the join */ + ExprList *pOrderBy; /* The ORDER BY clause or NULL */ + ExprList *pDistinct; /* DISTINCT ON values, or NULL */ + Bitmask revMask; /* Mask of ORDER BY terms that need reversing */ + u16 nOBSat; /* Number of ORDER BY terms satisfied by indices */ + u16 wctrlFlags; /* Flags originally passed to sqlite3WhereBegin() */ + u8 okOnePass; /* Ok to use one-pass algorithm for UPDATE/DELETE */ + u8 untestedTerms; /* Not all WHERE terms resolved by outer loop */ + u8 eDistinct; /* One of the WHERE_DISTINCT_* values below */ + int iTop; /* The very beginning of the WHERE loop */ + int iContinue; /* Jump here to continue with next record */ + int iBreak; /* Jump here to break out of the loop */ + int nLevel; /* Number of nested loop */ + struct WhereClause *pWC; /* Decomposition of the WHERE clause */ + struct WhereLoop *pLoops; /* List of all WhereLoop objects */ + double savedNQueryLoop; /* pParse->nQueryLoop outside the WHERE loop */ + double nRowOut; /* Estimated number of output rows */ + WhereLevel a[1]; /* Information about each nest loop in WHERE */ +}; + /* ** Each instance of this object represents a way of evaluating one ** term of a join. The WhereClause object holds a table of these @@ -333,6 +401,54 @@ struct WhereLoopBuilder { #define WHERE_TEMP_INDEX 0x00004000 /* Uses an ephemeral index */ #define WHERE_COVER_SCAN 0x00008000 /* Full scan of a covering index */ +/* +** Return the estimated number of output rows from a WHERE clause +*/ +double sqlite3WhereOutputRowCount(WhereInfo *pWInfo){ + return pWInfo->nRowOut; +} + +/* +** Return one of the WHERE_DISTINCT_xxxxx values to indicate how this +** WHERE clause returns outputs for DISTINCT processing. +*/ +int sqlite3WhereIsDistinct(WhereInfo *pWInfo){ + return pWInfo->eDistinct; +} + +/* +** Return TRUE if the WHERE clause returns rows in ORDER BY order. +** Return FALSE if the output needs to be sorted. +*/ +int sqlite3WhereIsOrdered(WhereInfo *pWInfo){ + return pWInfo->nOBSat>0; +} + +/* +** Return the VDBE address or label to jump to in order to continue +** immediately with the next row of a WHERE clause. +*/ +int sqlite3WhereContinueLabel(WhereInfo *pWInfo){ + return pWInfo->iContinue; +} + +/* +** Return the VDBE address or label to jump to in order to break +** out of a WHERE loop. +*/ +int sqlite3WhereBreakLabel(WhereInfo *pWInfo){ + return pWInfo->iBreak; +} + +/* +** Return TRUE if an UPDATE or DELETE statement can operate directly on +** the rowids returned by a WHERE clause. Return FALSE if doing an +** UPDATE or DELETE might change subsequent WHERE clause results. +*/ +int sqlite3WhereOkOnePass(WhereInfo *pWInfo){ + return pWInfo->okOnePass; +} + /* ** Initialize a preallocated WhereClause structure. */ @@ -4179,6 +4295,7 @@ static int whereLoopAddBtree( /* Automatic indexes */ if( !pBuilder->pBest + && pBuilder->pTabList->nSrc>1 && (pBuilder->pParse->db->flags & SQLITE_AutoIndex)!=0 && !pSrc->viaCoroutine && !pSrc->notIndexed -- 2.47.2