From 1c8148fffb49cb540e0c97f0700a0f3c0c0db52d Mon Sep 17 00:00:00 2001 From: drh Date: Sat, 4 May 2013 20:25:23 +0000 Subject: [PATCH] In where.c, make findTerm() a wrapper around methods to a new WhereScan object which is capable of finding all suitable matching terms, not just the first. This check-in includes some prototype functions for building WhereLoop objects. FossilOrigin-Name: dd92b8fa929badaf2f79e8a00c83667a9d589096 --- manifest | 15 +- manifest.uuid | 2 +- src/where.c | 383 +++++++++++++++++++++++++++++++++++++------------- 3 files changed, 293 insertions(+), 107 deletions(-) diff --git a/manifest b/manifest index 75d4e526f5..a36fbf25aa 100644 --- a/manifest +++ b/manifest @@ -1,5 +1,5 @@ -C Begin\sinserting\ssome\sexperimental\scode\sfor\sthe\snext\sgeneration\squery\splanner. -D 2013-05-02T00:15:01.231 +C In\swhere.c,\smake\sfindTerm()\sa\swrapper\saround\smethods\sto\sa\snew\sWhereScan\sobject\nwhich\sis\scapable\sof\sfinding\sall\ssuitable\smatching\sterms,\snot\sjust\sthe\sfirst.\nThis\scheck-in\sincludes\ssome\sprototype\sfunctions\sfor\sbuilding\sWhereLoop\sobjects. +D 2013-05-04T20:25:23.612 F Makefile.arm-wince-mingw32ce-gcc d6df77f1f48d690bd73162294bbba7f59507c72f F Makefile.in ce81671efd6223d19d4c8c6b88ac2c4134427111 F Makefile.linux-gcc 91d710bdc4998cb015f39edf3cb314ec4f4d7e23 @@ -263,7 +263,7 @@ F src/vtab.c b05e5f1f4902461ba9f5fc49bb7eb7c3a0741a83 F src/wal.c 436bfceb141b9423c45119e68e444358ee0ed35d F src/wal.h a4d3da523d55a226a0b28e9058ef88d0a8051887 F src/walker.c 4fa43583d0a84b48f93b1e88f11adf2065be4e73 -F src/where.c fc62bea654f27d5787bc428cd8f3f176d764f785 +F src/where.c 173347e4598207467401e1952bdee983cf0bf087 F test/8_3_names.test ebbb5cd36741350040fd28b432ceadf495be25b2 F test/aggerror.test a867e273ef9e3d7919f03ef4f0e8c0d2767944f2 F test/aggnested.test 45c0201e28045ad38a530b5a144b73cd4aa2cfd6 @@ -1060,10 +1060,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 faedaeace9c7ed9a8aaf96700caee09db0c0c061 -R 84f8c9b09f28282800936ed72686b19f -T *branch * nextgen-query-plan-exp -T *sym-nextgen-query-plan-exp * -T -sym-trunk * +P ccaf4c3f7e1ec45e058d594d9b5c26818a37722a +R d516c3475d503fb543da6770e30ae39a U drh -Z 18faca4b1f68b4b3514e189f395d77ff +Z 4a8c637fc587086861ee6817f8b965a6 diff --git a/manifest.uuid b/manifest.uuid index 016ae611b1..36eaec293a 100644 --- a/manifest.uuid +++ b/manifest.uuid @@ -1 +1 @@ -ccaf4c3f7e1ec45e058d594d9b5c26818a37722a \ No newline at end of file +dd92b8fa929badaf2f79e8a00c83667a9d589096 \ No newline at end of file diff --git a/src/where.c b/src/where.c index f44ab496c0..14120339d2 100644 --- a/src/where.c +++ b/src/where.c @@ -42,6 +42,8 @@ typedef struct WhereCost WhereCost; typedef struct WhereLoop WhereLoop; typedef struct WherePath WherePath; typedef struct WhereTerm WhereTerm; +typedef struct WhereLoopBuilder WhereLoopBuilder; +typedef struct WhereScan WhereScan; /* ** Each instance of this object represents a way of evaluating one @@ -60,7 +62,7 @@ struct WhereLoop { u16 nEq; /* Number of equality constraints */ u16 nTerm; /* Number of entries in aTerm[] */ Index *pIndex; /* Index used */ - WhereTerm *aTerm; /* WhereTerms used */ + WhereTerm **aTerm; /* WhereTerms used */ WhereLoop *pNextLoop; /* Next WhereLoop object in the WhereClause */ }; @@ -161,6 +163,23 @@ struct WhereTerm { # define TERM_VNULL 0x00 /* Disabled if not using stat3 */ #endif +/* +** An instance of the WhereScan object is used as an iterator for locating +** terms in the WHERE clause that are useful to the query planner. +*/ +struct WhereScan { + WhereTerm *pCurrent; /* Most recent match */ + WhereClause *pOrigWC; /* Original, innermost WhereClause */ + WhereClause *pWC; /* WhereClause currently being scanned */ + char *zCollName; /* Must have this collating sequence, if not NULL */ + char idxaff; /* Must match this affinity, if zCollName!=NULL */ + unsigned char nEquiv; /* Number of entries in aEquiv[] */ + unsigned char iEquiv; /* Next unused slot in aEquiv[] */ + u32 opMask; /* Acceptable operators */ + int k; /* Resume scanning at this->pWC->a[this->k] */ + int aEquiv[22]; /* Cursor,Column pairs for equivalence classes */ +}; + /* ** An instance of the following structure holds all information about a ** WHERE clause. Mostly this is a container for one or more WhereTerms. @@ -247,6 +266,19 @@ struct WhereCost { Bitmask used; /* Bitmask of cursors used by this plan */ }; +/* +** This object is a factory for WhereLoop objects for a particular query. +*/ +struct WhereLoopBuilder { + WhereInfo *pWInfo; /* Information about this WHERE */ + sqlite3 *db; /* Database connection */ + Parse *pParse; /* Parsing context */ + WhereClause *pWC; /* WHERE clause terms */ + SrcList *pTabList; /* FROM clause */ + ExprList *pOrderBy; /* ORDER BY clause */ + WhereLoop *pNew; /* Template WhereLoop */ +}; + /* ** Bitmasks for the operators that indices are able to exploit. An ** OR-ed combination of these values can be used when searching for @@ -661,6 +693,114 @@ static u16 operatorMask(int op){ return c; } +/* +** Advance to the next WhereTerm that matches according to the criteria +** established when the pScan object was initialized by whereScanInit(). +** Return NULL if there are no more matching WhereTerms. +*/ +WhereTerm *whereScanNext(WhereScan *pScan){ + int iCur; /* The cursor on the LHS of the term */ + int iColumn; /* The column on the LHS of the term. -1 for IPK */ + Expr *pX; /* An expression being tested */ + WhereClause *pWC; /* Shorthand for pScan->pWC */ + WhereTerm *pTerm; /* The term being tested */ + + while( pScan->iEquiv<=pScan->nEquiv ){ + iCur = pScan->aEquiv[pScan->iEquiv-2]; + iColumn = pScan->aEquiv[pScan->iEquiv-1]; + while( (pWC = pScan->pWC)!=0 ){ + for(pTerm=pWC->a+pScan->k; pScan->knTerm; pScan->k++, pTerm++){ + if( pTerm->leftCursor==iCur && pTerm->u.leftColumn==iColumn ){ + if( (pTerm->eOperator & WO_EQUIV)!=0 + && pScan->nEquivaEquiv) + ){ + int j; + pX = sqlite3ExprSkipCollate(pTerm->pExpr->pRight); + assert( pX->op==TK_COLUMN ); + for(j=0; jnEquiv; j+=2){ + if( pScan->aEquiv[j]==pX->iTable + && pScan->aEquiv[j+1]==pX->iColumn ){ + break; + } + } + if( j==pScan->nEquiv ){ + pScan->aEquiv[j] = pX->iTable; + pScan->aEquiv[j+1] = pX->iColumn; + pScan->nEquiv += 2; + } + } + if( (pTerm->eOperator & pScan->opMask)!=0 ){ + /* Verify the affinity and collating sequence match */ + if( pScan->zCollName && (pTerm->eOperator & WO_ISNULL)==0 ){ + CollSeq *pColl; + pX = pTerm->pExpr; + if( !sqlite3IndexAffinityOk(pX, pScan->idxaff) ){ + continue; + } + assert(pX->pLeft); + pColl = sqlite3BinaryCompareCollSeq(pWC->pParse, + pX->pLeft, pX->pRight); + if( pColl==0 ) pColl = pWC->pParse->db->pDfltColl; + if( sqlite3StrICmp(pColl->zName, pScan->zCollName) ){ + continue; + } + } + pScan->pCurrent = pTerm; + pScan->k++; + return pTerm; + } + } + } + pWC = pScan->pWC = pScan->pWC->pOuter; + pScan->k = 0; + } + pScan->pWC = pScan->pOrigWC; + pScan->k = 0; + pScan->iEquiv += 2; + } + pScan->pCurrent = 0; + return 0; +} + +/* +** Initialize a WHERE clause scanner object. Return a pointer to the +** first match. Return NULL if there are no matches. +** +** The scanner will be searching the WHERE clause pWC. It will look +** for terms of the form "X " where X is column iColumn of table +** iCur. The must be one of the operators described by opMask. +** +** If X is not the INTEGER PRIMARY KEY then X must be compatible with +** index pIdx. +*/ +WhereTerm *whereScanInit( + WhereScan *pScan, /* The WhereScan object being initialized */ + WhereClause *pWC, /* The WHERE clause to be scanned */ + int iCur, /* Cursor to scan for */ + int iColumn, /* Column to scan for */ + u32 opMask, /* Operator(s) to scan for */ + Index *pIdx /* Must be compatible with this index */ +){ + int j; + + memset(pScan, 0, sizeof(*pScan)); + pScan->pOrigWC = pWC; + pScan->pWC = pWC; + if( pIdx && iColumn>=0 ){ + pScan->idxaff = pIdx->pTable->aCol[iColumn].affinity; + for(j=0; pIdx->aiColumn[j]!=iColumn; j++){ + if( NEVER(j>=pIdx->nColumn) ) return 0; + } + pScan->zCollName = pIdx->azColl[j]; + } + pScan->opMask = opMask; + pScan->aEquiv[0] = iCur; + pScan->aEquiv[1] = iColumn; + pScan->nEquiv = 2; + pScan->iEquiv = 2; + return whereScanNext(pScan); +} + /* ** Search for a term in the WHERE clause that is of the form "X " ** where X is a reference to the iColumn of table iCur and is one of @@ -692,84 +832,20 @@ static WhereTerm *findTerm( u32 op, /* Mask of WO_xx values describing operator */ Index *pIdx /* Must be compatible with this index, if not NULL */ ){ - WhereTerm *pTerm; /* Term being examined as possible result */ - WhereTerm *pResult = 0; /* The answer to return */ - WhereClause *pWCOrig = pWC; /* Original pWC value */ - int j, k; /* Loop counters */ - Expr *pX; /* Pointer to an expression */ - Parse *pParse; /* Parsing context */ - int iOrigCol = iColumn; /* Original value of iColumn */ - int nEquiv = 2; /* Number of entires in aEquiv[] */ - int iEquiv = 2; /* Number of entries of aEquiv[] processed so far */ - int aEquiv[22]; /* iCur,iColumn and up to 10 other equivalents */ - - assert( iCur>=0 ); - aEquiv[0] = iCur; - aEquiv[1] = iColumn; - for(;;){ - for(pWC=pWCOrig; pWC; pWC=pWC->pOuter){ - for(pTerm=pWC->a, k=pWC->nTerm; k; k--, pTerm++){ - if( pTerm->leftCursor==iCur - && pTerm->u.leftColumn==iColumn - ){ - if( (pTerm->prereqRight & notReady)==0 - && (pTerm->eOperator & op & WO_ALL)!=0 - ){ - if( iOrigCol>=0 && pIdx && (pTerm->eOperator & WO_ISNULL)==0 ){ - CollSeq *pColl; - char idxaff; - - pX = pTerm->pExpr; - pParse = pWC->pParse; - idxaff = pIdx->pTable->aCol[iOrigCol].affinity; - if( !sqlite3IndexAffinityOk(pX, idxaff) ){ - continue; - } - - /* Figure out the collation sequence required from an index for - ** it to be useful for optimising expression pX. Store this - ** value in variable pColl. - */ - assert(pX->pLeft); - pColl = sqlite3BinaryCompareCollSeq(pParse,pX->pLeft,pX->pRight); - if( pColl==0 ) pColl = pParse->db->pDfltColl; - - for(j=0; pIdx->aiColumn[j]!=iOrigCol; j++){ - if( NEVER(j>=pIdx->nColumn) ) return 0; - } - if( sqlite3StrICmp(pColl->zName, pIdx->azColl[j]) ){ - continue; - } - } - if( pTerm->prereqRight==0 && (pTerm->eOperator&WO_EQ)!=0 ){ - pResult = pTerm; - goto findTerm_success; - }else if( pResult==0 ){ - pResult = pTerm; - } - } - if( (pTerm->eOperator & WO_EQUIV)!=0 - && nEquivpExpr->pRight); - assert( pX->op==TK_COLUMN ); - for(j=0; jiTable && aEquiv[j+1]==pX->iColumn ) break; - } - if( j==nEquiv ){ - aEquiv[j] = pX->iTable; - aEquiv[j+1] = pX->iColumn; - nEquiv += 2; - } - } - } + WhereTerm *pResult = 0; + WhereTerm *p; + WhereScan scan; + + p = whereScanInit(&scan, pWC, iCur, iColumn, op, pIdx); + while( p ){ + if( (p->prereqRight & notReady)==0 ){ + if( p->prereqRight==0 && (p->eOperator&WO_EQ)!=0 ){ + return p; } + if( pResult==0 ) pResult = p; } - if( iEquiv>=nEquiv ) break; - iCur = aEquiv[iEquiv++]; - iColumn = aEquiv[iEquiv++]; + p = whereScanNext(&scan); } -findTerm_success: return pResult; } @@ -5058,38 +5134,139 @@ static int whereLoopInsert(WhereInfo *pWInfo, WhereLoop *pTemplate){ p->pNextLoop = pWInfo->pLoops; pWInfo->pLoops = p; if( pTemplate->nTerm<=0 ) return SQLITE_OK; + if( p->pIndex && p->pIndex->tnum==0 ) p->pIndex = 0; p->aTerm = sqlite3DbMallocRaw(db, pTemplate->nTerm*sizeof(p->aTerm[0])); if( p->aTerm==0 ){ p->nTerm = 0; + sqlite3DbFree(db, p); return SQLITE_NOMEM; } memcpy(p->aTerm, pTemplate->aTerm, pTemplate->nTerm*sizeof(p->aTerm[0])); return SQLITE_OK; } +/* +** We have so far matched pBuilder->pNew->nEq terms of the index pIndex. +** Try to match one more. +** +** If pProbe->tnum==0, that means pIndex is a fake index used for the +** INTEGER PRIMARY KEY. +*/ +static void whereLoopAddBtreeIndex( + WhereLoopBuilder *pBuilder, /* The WhereLoop factory */ + struct SrcList_item *pSrc, /* FROM clause term being analyzed */ + Index *pProbe, /* An index on pSrc */ + int nInMul /* Number of iterations due to IN */ +){ + sqlite3 *db; /* Database connection malloc context */ + WhereLoop *pNew; /* Template WhereLoop under construction */ + WhereTerm *pTerm; /* A WhereTerm under consideration */ + int eqTermMask; /* Valid equality operators */ + WhereScan scan; /* Iterator for WHERE terms */ + + db = pBuilder->db; + pNew = pBuilder->pNew; + if( db->mallocFailed ) return; + + if( pProbe->tnum<=0 || (pSrc->jointype & JT_LEFT)!=0 ){ + eqTermMask = WO_EQ|WO_IN; + }else{ + eqTermMask = WO_EQ|WO_IN|WO_ISNULL; + } + + + if( pNew->nEqnColumn ){ + int iCol; /* Index of the column in the table */ + + + iCol = pProbe->aiColumn[pNew->nEq]; + pTerm = whereScanInit(&scan, pBuilder->pWC, pSrc->iCursor, iCol, + eqTermMask, iCol>=0 ? pProbe : 0); + pNew->nEq++; + for(; pTerm!=0; pTerm = whereScanNext(&scan)){ + pNew->aTerm[pNew->nEq-1] = pTerm; + + } + pNew->nEq--; + + } +} + /* ** Add all WhereLoop objects for the iTab-th table of the join. That ** table is guaranteed to be a b-tree table, not a virtual table. */ static void whereLoopAddBtree( - WhereInfo *pWInfo, /* WHERE clause information */ - int iTab, /* The table to process */ - Bitmask mExtra /* Extra prerequesites for using this table */ + WhereLoopBuilder *pBuilder, /* WHERE clause information */ + int iTab, /* The table to process */ + Bitmask mExtra /* Extra prerequesites for using this table */ ){ - WhereLoop *pNew; /* Template WhereLoop object */ - sqlite3 *db = pWInfo->pParse->db; + Index *pProbe; /* An index we are evaluating */ + int eqTermMask; /* Current mask of valid equality operators */ + Index sPk; /* A fake index object for the primary key */ + tRowcnt aiRowEstPk[2]; /* The aiRowEst[] value for the sPk index */ + int aiColumnPk = -1; /* The aColumn[] value for the sPk index */ + struct SrcList_item *pSrc; /* The FROM clause btree term to add */ + sqlite3 *db; /* The database connection */ + WhereLoop *pNew; /* Template WhereLoop object */ - pNew = sqlite3DbMallocZero(db, sizeof(*pNew)); - if( pNew==0 ) return; - + pNew = pBuilder->pNew; + db = pBuilder->db; + pSrc = pBuilder->pTabList->a + iTab; + + if( pSrc->pIndex ){ + /* An INDEXED BY clause specifies a particular index to use */ + pProbe = pSrc->pIndex; + }else{ + /* There is no INDEXED BY clause. Create a fake Index object in local + ** variable sPk to represent the rowid primary key index. Make this + ** fake index the first in a chain of Index objects with all of the real + ** indices to follow */ + Index *pFirst; /* First of real indices on the table */ + memset(&sPk, 0, sizeof(Index)); + sPk.nColumn = 1; + sPk.aiColumn = &aiColumnPk; + sPk.aiRowEst = aiRowEstPk; + sPk.onError = OE_Replace; + sPk.pTable = pSrc->pTab; + aiRowEstPk[0] = pSrc->pTab->nRowEst; + aiRowEstPk[1] = 1; + pFirst = pSrc->pTab->pIndex; + if( pSrc->notIndexed==0 ){ + /* The real indices of the table are only considered if the + ** NOT INDEXED qualifier is omitted from the FROM clause */ + sPk.pNext = pFirst; + } + pProbe = &sPk; + } + + /* Loop over all indices + */ + for(; pProbe; pProbe=pProbe->pNext){ + pNew->prereq = mExtra; + pNew->iTab = iTab; + pNew->nEq = 0; + pNew->nTerm = 0; + pNew->aTerm = sqlite3DbRealloc(db, pNew->aTerm, + (pProbe->nColumn+1)*sizeof(pNew->aTerm[0])); + if( pNew->aTerm==0 ) break; + pNew->pIndex = pProbe; + + whereLoopAddBtreeIndex(pBuilder, pSrc, pProbe, 1); + + /* If there was an INDEXED BY clause, then only that one index is + ** considered. */ + if( pSrc->pIndex ) break; + } + +#if 0 /* Insert a full table scan */ pNew->iTab = iTab; pNew->rSetup = (double)0; pNew->rRun = (double)1000000; pNew->nOut = (double)1000000; - whereLoopInsert(pWInfo, pNew); - - whereLoopDelete(db, pNew); + whereLoopInsert(pBuilder->pWInfo, pNew); +#endif } /* @@ -5097,30 +5274,32 @@ static void whereLoopAddBtree( ** table is guaranteed to be a virtual table. */ static void whereLoopAddVirtual( - WhereInfo *pWInfo, /* WHERE clause information */ - int iTab, /* The table to process */ - Bitmask mExtra /* Extra prerequesites for using this table */ + WhereLoopBuilder *pBuilder, /* WHERE clause information */ + int iTab, /* The table to process */ + Bitmask mExtra /* Extra prerequesites for using this table */ ){ } /* ** Add all WhereLoop objects for all tables */ -static void whereLoopAddAll(WhereInfo *pWInfo){ +static void whereLoopAddAll(WhereLoopBuilder *pBuilder){ Bitmask mExtra = 0; Bitmask mPrior = 0; int iTab; - SrcList *pTabList = pWInfo->pTabList; + SrcList *pTabList = pBuilder->pTabList; struct SrcList_item *pItem; - WhereClause *pWC = pWInfo->pWC; - sqlite3 *db = pWInfo->pParse->db; + WhereClause *pWC = pBuilder->pWC; + sqlite3 *db = pBuilder->db; /* Loop over the tables in the join, from left to right */ + pBuilder->pNew = sqlite3DbMallocZero(db, sizeof(WhereLoop)); + if( pBuilder->pNew==0 ) return; for(iTab=0, pItem=pTabList->a; iTabnSrc; iTab++, pItem++){ if( IsVirtual(pItem->pTab) ){ - whereLoopAddVirtual(pWInfo, iTab, mExtra); + whereLoopAddVirtual(pBuilder, iTab, mExtra); }else{ - whereLoopAddBtree(pWInfo, iTab, mExtra); + whereLoopAddBtree(pBuilder, iTab, mExtra); } mPrior |= getMask(pWC->pMaskSet, pItem->iCursor); if( (pItem->jointype & (JT_LEFT|JT_CROSS))!=0 ){ @@ -5128,6 +5307,8 @@ static void whereLoopAddAll(WhereInfo *pWInfo){ } if( db->mallocFailed ) break; } + whereLoopDelete(db, pBuilder->pNew); + pBuilder->pNew = 0; } @@ -5234,6 +5415,7 @@ WhereInfo *sqlite3WhereBegin( Vdbe *v = pParse->pVdbe; /* The virtual database engine */ Bitmask notReady; /* Cursors that are not yet positioned */ WhereBestIdx sWBI; /* Best index search context */ + WhereLoopBuilder sWLB; /* The WhereLoop builder */ WhereMaskSet *pMaskSet; /* The expression mask set */ WhereLevel *pLevel; /* A single level in pWInfo->a[] */ int iFrom; /* First unused FROM clause element */ @@ -5245,6 +5427,11 @@ WhereInfo *sqlite3WhereBegin( /* Variable initialization */ memset(&sWBI, 0, sizeof(sWBI)); sWBI.pParse = pParse; + memset(&sWLB, 0, sizeof(sWLB)); + sWLB.pParse = pParse; + sWLB.db = pParse->db; + sWLB.pTabList = pTabList; + sWLB.pOrderBy = pOrderBy; /* The number of tables in the FROM clause is limited by the number of ** bits in a Bitmask @@ -5290,6 +5477,8 @@ WhereInfo *sqlite3WhereBegin( pWInfo->savedNQueryLoop = pParse->nQueryLoop; pMaskSet = (WhereMaskSet*)&sWBI.pWC[1]; sWBI.aLevel = pWInfo->a; + sWLB.pWInfo = pWInfo; + sWLB.pWC = pWInfo->pWC; /* Disable the DISTINCT optimization if SQLITE_DistinctOpt is set via ** sqlite3_test_ctrl(SQLITE_TESTCTRL_OPTIMIZATIONS,...) */ @@ -5362,7 +5551,7 @@ WhereInfo *sqlite3WhereBegin( /* Construct the WhereLoop objects */ WHERETRACE(("*** Optimizer Start ***\n")); - whereLoopAddAll(pWInfo); + /*whereLoopAddAll(&sWLB);*/ /* Display all of the WhereLoop objects if wheretrace is enabled */ #if defined(SQLITE_DEBUG) \ -- 2.47.2