diff options
Diffstat (limited to 'ext/pdo_sqlite/sqlite/src/where.c')
| -rw-r--r-- | ext/pdo_sqlite/sqlite/src/where.c | 524 |
1 files changed, 370 insertions, 154 deletions
diff --git a/ext/pdo_sqlite/sqlite/src/where.c b/ext/pdo_sqlite/sqlite/src/where.c index bdbac8112..ac3df19d5 100644 --- a/ext/pdo_sqlite/sqlite/src/where.c +++ b/ext/pdo_sqlite/sqlite/src/where.c @@ -35,14 +35,15 @@ */ #if defined(SQLITE_TEST) || defined(SQLITE_DEBUG) int sqlite3_where_trace = 0; -# define TRACE(X) if(sqlite3_where_trace) sqlite3DebugPrintf X +# define WHERETRACE(X) if(sqlite3_where_trace) sqlite3DebugPrintf X #else -# define TRACE(X) +# define WHERETRACE(X) #endif /* Forward reference */ typedef struct WhereClause WhereClause; +typedef struct ExprMaskSet ExprMaskSet; /* ** The query generator uses an array of instances of this structure to @@ -106,6 +107,7 @@ struct WhereTerm { */ struct WhereClause { Parse *pParse; /* The parser context */ + ExprMaskSet *pMaskSet; /* Mapping of table indices to bitmasks */ int nTerm; /* Number of terms */ int nSlot; /* Number of entries in a[] */ WhereTerm *a; /* Each a[] describes a term of the WHERE cluase */ @@ -138,7 +140,6 @@ struct WhereClause { ** numbers all get mapped into bit numbers that begin with 0 and contain ** no gaps. */ -typedef struct ExprMaskSet ExprMaskSet; struct ExprMaskSet { int n; /* Number of assigned cursor values */ int ix[sizeof(Bitmask)*8]; /* Cursor assigned to each bit */ @@ -157,28 +158,42 @@ struct ExprMaskSet { #define WO_GT (WO_EQ<<(TK_GT-TK_EQ)) #define WO_GE (WO_EQ<<(TK_GE-TK_EQ)) #define WO_MATCH 64 +#define WO_ISNULL 128 /* -** Value for flags returned by bestIndex() +** Value for flags returned by bestIndex(). +** +** The least significant byte is reserved as a mask for WO_ values above. +** The WhereLevel.flags field is usually set to WO_IN|WO_EQ|WO_ISNULL. +** But if the table is the right table of a left join, WhereLevel.flags +** is set to WO_IN|WO_EQ. The WhereLevel.flags field can then be used as +** the "op" parameter to findTerm when we are resolving equality constraints. +** ISNULL constraints will then not be used on the right table of a left +** join. Tickets #2177 and #2189. */ -#define WHERE_ROWID_EQ 0x0001 /* rowid=EXPR or rowid IN (...) */ -#define WHERE_ROWID_RANGE 0x0002 /* rowid<EXPR and/or rowid>EXPR */ -#define WHERE_COLUMN_EQ 0x0010 /* x=EXPR or x IN (...) */ -#define WHERE_COLUMN_RANGE 0x0020 /* x<EXPR and/or x>EXPR */ -#define WHERE_COLUMN_IN 0x0040 /* x IN (...) */ -#define WHERE_TOP_LIMIT 0x0100 /* x<EXPR or x<=EXPR constraint */ -#define WHERE_BTM_LIMIT 0x0200 /* x>EXPR or x>=EXPR constraint */ -#define WHERE_IDX_ONLY 0x0800 /* Use index only - omit table */ -#define WHERE_ORDERBY 0x1000 /* Output will appear in correct order */ -#define WHERE_REVERSE 0x2000 /* Scan in reverse order */ -#define WHERE_UNIQUE 0x4000 /* Selects no more than one row */ -#define WHERE_VIRTUALTABLE 0x8000 /* Use virtual-table processing */ +#define WHERE_ROWID_EQ 0x000100 /* rowid=EXPR or rowid IN (...) */ +#define WHERE_ROWID_RANGE 0x000200 /* rowid<EXPR and/or rowid>EXPR */ +#define WHERE_COLUMN_EQ 0x001000 /* x=EXPR or x IN (...) */ +#define WHERE_COLUMN_RANGE 0x002000 /* x<EXPR and/or x>EXPR */ +#define WHERE_COLUMN_IN 0x004000 /* x IN (...) */ +#define WHERE_TOP_LIMIT 0x010000 /* x<EXPR or x<=EXPR constraint */ +#define WHERE_BTM_LIMIT 0x020000 /* x>EXPR or x>=EXPR constraint */ +#define WHERE_IDX_ONLY 0x080000 /* Use index only - omit table */ +#define WHERE_ORDERBY 0x100000 /* Output will appear in correct order */ +#define WHERE_REVERSE 0x200000 /* Scan in reverse order */ +#define WHERE_UNIQUE 0x400000 /* Selects no more than one row */ +#define WHERE_VIRTUALTABLE 0x800000 /* Use virtual-table processing */ /* ** Initialize a preallocated WhereClause structure. */ -static void whereClauseInit(WhereClause *pWC, Parse *pParse){ +static void whereClauseInit( + WhereClause *pWC, /* The WhereClause to be initialized */ + Parse *pParse, /* The parsing context */ + ExprMaskSet *pMaskSet /* Mapping from table indices to bitmasks */ +){ pWC->pParse = pParse; + pWC->pMaskSet = pMaskSet; pWC->nTerm = 0; pWC->nSlot = ARRAYSIZE(pWC->aStatic); pWC->a = pWC->aStatic; @@ -205,6 +220,9 @@ static void whereClauseClear(WhereClause *pWC){ ** Add a new entries to the WhereClause structure. Increase the allocated ** space as necessary. ** +** If the flags argument includes TERM_DYNAMIC, then responsibility +** for freeing the expression p is assumed by the WhereClause object. +** ** WARNING: This routine might reallocate the space used to store ** WhereTerms. All pointers to WhereTerms should be invalided after ** calling this routine. Such pointers may be reinitialized by referencing @@ -216,7 +234,12 @@ static int whereClauseInsert(WhereClause *pWC, Expr *p, int flags){ if( pWC->nTerm>=pWC->nSlot ){ WhereTerm *pOld = pWC->a; pWC->a = sqliteMalloc( sizeof(pWC->a[0])*pWC->nSlot*2 ); - if( pWC->a==0 ) return 0; + if( pWC->a==0 ){ + if( flags & TERM_DYNAMIC ){ + sqlite3ExprDelete(p); + } + return 0; + } memcpy(pWC->a, pOld, sizeof(pWC->a[0])*pWC->nTerm); if( pOld!=pWC->aStatic ){ sqliteFree(pOld); @@ -354,7 +377,7 @@ static int allowedOp(int op){ assert( TK_LT>TK_EQ && TK_LT<TK_GE ); assert( TK_LE>TK_EQ && TK_LE<TK_GE ); assert( TK_GE==TK_EQ+4 ); - return op==TK_IN || (op>=TK_EQ && op<=TK_GE); + return op==TK_IN || (op>=TK_EQ && op<=TK_GE) || op==TK_ISNULL; } /* @@ -388,9 +411,12 @@ static int operatorMask(int op){ assert( allowedOp(op) ); if( op==TK_IN ){ c = WO_IN; + }else if( op==TK_ISNULL ){ + c = WO_ISNULL; }else{ c = WO_EQ<<(op-TK_EQ); } + assert( op!=TK_ISNULL || c==WO_ISNULL ); assert( op!=TK_IN || c==WO_IN ); assert( op!=TK_EQ || c==WO_EQ ); assert( op!=TK_LT || c==WO_LT ); @@ -422,7 +448,7 @@ static WhereTerm *findTerm( && pTerm->leftColumn==iColumn && (pTerm->eOperator & op)!=0 ){ - if( iCur>=0 && pIdx ){ + if( iCur>=0 && pIdx && pTerm->eOperator!=WO_ISNULL ){ Expr *pX = pTerm->pExpr; CollSeq *pColl; char idxaff; @@ -451,7 +477,7 @@ static WhereTerm *findTerm( } /* Forward reference */ -static void exprAnalyze(SrcList*, ExprMaskSet*, WhereClause*, int); +static void exprAnalyze(SrcList*, WhereClause*, int); /* ** Call exprAnalyze on all terms in a WHERE clause. @@ -460,12 +486,11 @@ static void exprAnalyze(SrcList*, ExprMaskSet*, WhereClause*, int); */ static void exprAnalyzeAll( SrcList *pTabList, /* the FROM clause */ - ExprMaskSet *pMaskSet, /* table masks */ WhereClause *pWC /* the WHERE clause to be analyzed */ ){ int i; for(i=pWC->nTerm-1; i>=0; i--){ - exprAnalyze(pTabList, pMaskSet, pWC, i); + exprAnalyze(pTabList, pWC, i); } } @@ -506,6 +531,10 @@ static int isLikeOrGlob( } pColl = pLeft->pColl; if( pColl==0 ){ + /* TODO: Coverage testing doesn't get this case. Is it actually possible + ** for an expression of type TK_COLUMN to not have an assigned collation + ** sequence at this point? + */ pColl = db->pDfltColl; } if( (pColl->type!=SQLITE_COLL_BINARY || noCase) && @@ -565,6 +594,92 @@ static void transferJoinMarkings(Expr *pDerived, Expr *pBase){ pDerived->iRightJoinTable = pBase->iRightJoinTable; } +#if !defined(SQLITE_OMIT_OR_OPTIMIZATION) && !defined(SQLITE_OMIT_SUBQUERY) +/* +** Return TRUE if the given term of an OR clause can be converted +** into an IN clause. The iCursor and iColumn define the left-hand +** side of the IN clause. +** +** The context is that we have multiple OR-connected equality terms +** like this: +** +** a=<expr1> OR a=<expr2> OR b=<expr3> OR ... +** +** The pOrTerm input to this routine corresponds to a single term of +** this OR clause. In order for the term to be a condidate for +** conversion to an IN operator, the following must be true: +** +** * The left-hand side of the term must be the column which +** is identified by iCursor and iColumn. +** +** * If the right-hand side is also a column, then the affinities +** of both right and left sides must be such that no type +** conversions are required on the right. (Ticket #2249) +** +** If both of these conditions are true, then return true. Otherwise +** return false. +*/ +static int orTermIsOptCandidate(WhereTerm *pOrTerm, int iCursor, int iColumn){ + int affLeft, affRight; + assert( pOrTerm->eOperator==WO_EQ ); + if( pOrTerm->leftCursor!=iCursor ){ + return 0; + } + if( pOrTerm->leftColumn!=iColumn ){ + return 0; + } + affRight = sqlite3ExprAffinity(pOrTerm->pExpr->pRight); + if( affRight==0 ){ + return 1; + } + affLeft = sqlite3ExprAffinity(pOrTerm->pExpr->pLeft); + if( affRight!=affLeft ){ + return 0; + } + return 1; +} + +/* +** Return true if the given term of an OR clause can be ignored during +** a check to make sure all OR terms are candidates for optimization. +** In other words, return true if a call to the orTermIsOptCandidate() +** above returned false but it is not necessary to disqualify the +** optimization. +** +** Suppose the original OR phrase was this: +** +** a=4 OR a=11 OR a=b +** +** During analysis, the third term gets flipped around and duplicate +** so that we are left with this: +** +** a=4 OR a=11 OR a=b OR b=a +** +** Since the last two terms are duplicates, only one of them +** has to qualify in order for the whole phrase to qualify. When +** this routine is called, we know that pOrTerm did not qualify. +** This routine merely checks to see if pOrTerm has a duplicate that +** might qualify. If there is a duplicate that has not yet been +** disqualified, then return true. If there are no duplicates, or +** the duplicate has also been disqualifed, return false. +*/ +static int orTermHasOkDuplicate(WhereClause *pOr, WhereTerm *pOrTerm){ + if( pOrTerm->flags & TERM_COPIED ){ + /* This is the original term. The duplicate is to the left had + ** has not yet been analyzed and thus has not yet been disqualified. */ + return 1; + } + if( (pOrTerm->flags & TERM_VIRTUAL)!=0 + && (pOr->a[pOrTerm->iParent].flags & TERM_OR_OK)!=0 ){ + /* This is a duplicate term. The original qualified so this one + ** does not have to. */ + return 1; + } + /* This is either a singleton term or else it is a duplicate for + ** which the original did not qualify. Either way we are done for. */ + return 0; +} +#endif /* !SQLITE_OMIT_OR_OPTIMIZATION && !SQLITE_OMIT_SUBQUERY */ /* ** The input to this routine is an WhereTerm structure with only the @@ -580,23 +695,27 @@ static void transferJoinMarkings(Expr *pDerived, Expr *pBase){ */ static void exprAnalyze( SrcList *pSrc, /* the FROM clause */ - ExprMaskSet *pMaskSet, /* table masks */ WhereClause *pWC, /* the WHERE clause */ int idxTerm /* Index of the term to be analyzed */ ){ WhereTerm *pTerm = &pWC->a[idxTerm]; + ExprMaskSet *pMaskSet = pWC->pMaskSet; Expr *pExpr = pTerm->pExpr; Bitmask prereqLeft; Bitmask prereqAll; int nPattern; int isComplete; + int op; if( sqlite3MallocFailed() ) return; prereqLeft = exprTableUsage(pMaskSet, pExpr->pLeft); - if( pExpr->op==TK_IN ){ + op = pExpr->op; + if( op==TK_IN ){ assert( pExpr->pRight==0 ); pTerm->prereqRight = exprListTableUsage(pMaskSet, pExpr->pList) | exprSelectTableUsage(pMaskSet, pExpr->pSelect); + }else if( op==TK_ISNULL ){ + pTerm->prereqRight = 0; }else{ pTerm->prereqRight = exprTableUsage(pMaskSet, pExpr->pRight); } @@ -608,13 +727,13 @@ static void exprAnalyze( pTerm->leftCursor = -1; pTerm->iParent = -1; pTerm->eOperator = 0; - if( allowedOp(pExpr->op) && (pTerm->prereqRight & prereqLeft)==0 ){ + if( allowedOp(op) && (pTerm->prereqRight & prereqLeft)==0 ){ Expr *pLeft = pExpr->pLeft; Expr *pRight = pExpr->pRight; if( pLeft->op==TK_COLUMN ){ pTerm->leftCursor = pLeft->iTable; pTerm->leftColumn = pLeft->iColumn; - pTerm->eOperator = operatorMask(pExpr->op); + pTerm->eOperator = operatorMask(op); } if( pRight && pRight->op==TK_COLUMN ){ WhereTerm *pNew; @@ -622,6 +741,10 @@ static void exprAnalyze( if( pTerm->leftCursor>=0 ){ int idxNew; pDup = sqlite3ExprDup(pExpr); + if( sqlite3MallocFailed() ){ + sqlite3ExprDelete(pDup); + return; + } idxNew = whereClauseInsert(pWC, pDup, TERM_VIRTUAL|TERM_DYNAMIC); if( idxNew==0 ) return; pNew = &pWC->a[idxNew]; @@ -659,7 +782,7 @@ static void exprAnalyze( pNewExpr = sqlite3Expr(ops[i], sqlite3ExprDup(pExpr->pLeft), sqlite3ExprDup(pList->a[i].pExpr), 0); idxNew = whereClauseInsert(pWC, pNewExpr, TERM_VIRTUAL|TERM_DYNAMIC); - exprAnalyze(pSrc, pMaskSet, pWC, idxNew); + exprAnalyze(pSrc, pWC, idxNew); pTerm = &pWC->a[idxTerm]; pWC->a[idxNew].iParent = idxTerm; } @@ -688,12 +811,13 @@ static void exprAnalyze( WhereTerm *pOrTerm; assert( (pTerm->flags & TERM_DYNAMIC)==0 ); - whereClauseInit(&sOr, pWC->pParse); + whereClauseInit(&sOr, pWC->pParse, pMaskSet); whereSplit(&sOr, pExpr, TK_OR); - exprAnalyzeAll(pSrc, pMaskSet, &sOr); - assert( sOr.nTerm>0 ); + exprAnalyzeAll(pSrc, &sOr); + assert( sOr.nTerm>=2 ); j = 0; do{ + assert( j<sOr.nTerm ); iColumn = sOr.a[j].leftColumn; iCursor = sOr.a[j].leftCursor; ok = iCursor>=0; @@ -701,37 +825,34 @@ static void exprAnalyze( if( pOrTerm->eOperator!=WO_EQ ){ goto or_not_possible; } - if( pOrTerm->leftCursor==iCursor && pOrTerm->leftColumn==iColumn ){ + if( orTermIsOptCandidate(pOrTerm, iCursor, iColumn) ){ pOrTerm->flags |= TERM_OR_OK; - }else if( (pOrTerm->flags & TERM_COPIED)!=0 || - ((pOrTerm->flags & TERM_VIRTUAL)!=0 && - (sOr.a[pOrTerm->iParent].flags & TERM_OR_OK)!=0) ){ + }else if( orTermHasOkDuplicate(&sOr, pOrTerm) ){ pOrTerm->flags &= ~TERM_OR_OK; }else{ ok = 0; } } - }while( !ok && (sOr.a[j++].flags & TERM_COPIED)!=0 && j<sOr.nTerm ); + }while( !ok && (sOr.a[j++].flags & TERM_COPIED)!=0 && j<2 ); if( ok ){ ExprList *pList = 0; Expr *pNew, *pDup; + Expr *pLeft = 0; for(i=sOr.nTerm-1, pOrTerm=sOr.a; i>=0 && ok; i--, pOrTerm++){ if( (pOrTerm->flags & TERM_OR_OK)==0 ) continue; pDup = sqlite3ExprDup(pOrTerm->pExpr->pRight); pList = sqlite3ExprListAppend(pList, pDup, 0); + pLeft = pOrTerm->pExpr->pLeft; } - pDup = sqlite3Expr(TK_COLUMN, 0, 0, 0); - if( pDup ){ - pDup->iTable = iCursor; - pDup->iColumn = iColumn; - } + assert( pLeft!=0 ); + pDup = sqlite3ExprDup(pLeft); pNew = sqlite3Expr(TK_IN, pDup, 0, 0); if( pNew ){ int idxNew; transferJoinMarkings(pNew, pExpr); pNew->pList = pList; idxNew = whereClauseInsert(pWC, pNew, TERM_VIRTUAL|TERM_DYNAMIC); - exprAnalyze(pSrc, pMaskSet, pWC, idxNew); + exprAnalyze(pSrc, pWC, idxNew); pTerm = &pWC->a[idxTerm]; pWC->a[idxNew].iParent = idxTerm; pTerm->nChild = 1; @@ -768,10 +889,10 @@ or_not_possible: } pNewExpr1 = sqlite3Expr(TK_GE, sqlite3ExprDup(pLeft), pStr1, 0); idxNew1 = whereClauseInsert(pWC, pNewExpr1, TERM_VIRTUAL|TERM_DYNAMIC); - exprAnalyze(pSrc, pMaskSet, pWC, idxNew1); + exprAnalyze(pSrc, pWC, idxNew1); pNewExpr2 = sqlite3Expr(TK_LT, sqlite3ExprDup(pLeft), pStr2, 0); idxNew2 = whereClauseInsert(pWC, pNewExpr2, TERM_VIRTUAL|TERM_DYNAMIC); - exprAnalyze(pSrc, pMaskSet, pWC, idxNew2); + exprAnalyze(pSrc, pWC, idxNew2); pTerm = &pWC->a[idxTerm]; if( isComplete ){ pWC->a[idxNew1].iParent = idxTerm; @@ -817,6 +938,25 @@ or_not_possible: #endif /* SQLITE_OMIT_VIRTUALTABLE */ } +/* +** Return TRUE if any of the expressions in pList->a[iFirst...] contain +** a reference to any table other than the iBase table. +*/ +static int referencesOtherTables( + ExprList *pList, /* Search expressions in ths list */ + ExprMaskSet *pMaskSet, /* Mapping from tables to bitmaps */ + int iFirst, /* Be searching with the iFirst-th expression */ + int iBase /* Ignore references to this table */ +){ + Bitmask allowed = ~getMask(pMaskSet, iBase); + while( iFirst<pList->nExpr ){ + if( (exprTableUsage(pMaskSet, pList->a[iFirst++].pExpr)&allowed)!=0 ){ + return 1; + } + } + return 0; +} + /* ** This routine decides if pIdx can be used to satisfy the ORDER BY @@ -839,6 +979,7 @@ or_not_possible: */ static int isSortingIndex( Parse *pParse, /* Parsing context */ + ExprMaskSet *pMaskSet, /* Mapping from table indices to bitmaps */ Index *pIdx, /* The index we are testing */ int base, /* Cursor number for the table to be sorted */ ExprList *pOrderBy, /* The ORDER BY clause */ @@ -857,22 +998,43 @@ static int isSortingIndex( /* Match terms of the ORDER BY clause against columns of ** the index. + ** + ** Note that indices have pIdx->nColumn regular columns plus + ** one additional column containing the rowid. The rowid column + ** of the index is also allowed to match against the ORDER BY + ** clause. */ - for(i=j=0, pTerm=pOrderBy->a; j<nTerm && i<pIdx->nColumn; i++){ + for(i=j=0, pTerm=pOrderBy->a; j<nTerm && i<=pIdx->nColumn; i++){ Expr *pExpr; /* The expression of the ORDER BY pTerm */ CollSeq *pColl; /* The collating sequence of pExpr */ int termSortOrder; /* Sort order for this term */ + int iColumn; /* The i-th column of the index. -1 for rowid */ + int iSortOrder; /* 1 for DESC, 0 for ASC on the i-th index term */ + const char *zColl; /* Name of the collating sequence for i-th index term */ pExpr = pTerm->pExpr; if( pExpr->op!=TK_COLUMN || pExpr->iTable!=base ){ /* Can not use an index sort on anything that is not a column in the ** left-most table of the FROM clause */ - return 0; + break; } pColl = sqlite3ExprCollSeq(pParse, pExpr); - if( !pColl ) pColl = db->pDfltColl; - if( pExpr->iColumn!=pIdx->aiColumn[i] || - sqlite3StrICmp(pColl->zName, pIdx->azColl[i]) ){ + if( !pColl ){ + pColl = db->pDfltColl; + } + if( i<pIdx->nColumn ){ + iColumn = pIdx->aiColumn[i]; + if( iColumn==pIdx->pTable->iPKey ){ + iColumn = -1; + } + iSortOrder = pIdx->aSortOrder[i]; + zColl = pIdx->azColl[i]; + }else{ + iColumn = -1; + iSortOrder = 0; + zColl = pColl->zName; + } + if( pExpr->iColumn!=iColumn || sqlite3StrICmp(pColl->zName, zColl) ){ /* Term j of the ORDER BY clause does not match column i of the index */ if( i<nEqCol ){ /* If an index column that is constrained by == fails to match an @@ -888,8 +1050,8 @@ static int isSortingIndex( } assert( pIdx->aSortOrder!=0 ); assert( pTerm->sortOrder==0 || pTerm->sortOrder==1 ); - assert( pIdx->aSortOrder[i]==0 || pIdx->aSortOrder[i]==1 ); - termSortOrder = pIdx->aSortOrder[i] ^ pTerm->sortOrder; + assert( iSortOrder==0 || iSortOrder==1 ); + termSortOrder = iSortOrder ^ pTerm->sortOrder; if( i>nEqCol ){ if( termSortOrder!=sortOrder ){ /* Indices can only be used if all ORDER BY terms past the @@ -901,13 +1063,29 @@ static int isSortingIndex( } j++; pTerm++; + if( iColumn<0 && !referencesOtherTables(pOrderBy, pMaskSet, j, base) ){ + /* If the indexed column is the primary key and everything matches + ** so far and none of the ORDER BY terms to the right reference other + ** tables in the join, then we are assured that the index can be used + ** to sort because the primary key is unique and so none of the other + ** columns will make any difference + */ + j = nTerm; + } } - /* The index can be used for sorting if all terms of the ORDER BY clause - ** are covered. - */ + *pbRev = sortOrder!=0; if( j>=nTerm ){ - *pbRev = sortOrder!=0; + /* All terms of the ORDER BY clause are covered by this index so + ** this index can be used for sorting. */ + return 1; + } + if( pIdx->onError!=OE_None && i==pIdx->nColumn + && !referencesOtherTables(pOrderBy, pMaskSet, j, base) ){ + /* All terms of this index match some prefix of the ORDER BY clause + ** and the index is UNIQUE and no terms on the tail of the ORDER BY + ** clause reference other tables in a join. If this is all true then + ** the order by clause is superfluous. */ return 1; } return 0; @@ -921,6 +1099,7 @@ static int isSortingIndex( static int sortableByRowid( int base, /* Cursor number for table to be sorted */ ExprList *pOrderBy, /* The ORDER BY clause */ + ExprMaskSet *pMaskSet, /* Mapping from tables to bitmaps */ int *pbRev /* Set to 1 if ORDER BY is DESC */ ){ Expr *p; @@ -928,8 +1107,8 @@ static int sortableByRowid( assert( pOrderBy!=0 ); assert( pOrderBy->nExpr>0 ); p = pOrderBy->a[0].pExpr; - if( pOrderBy->nExpr==1 && p->op==TK_COLUMN && p->iTable==base - && p->iColumn==-1 ){ + if( p->op==TK_COLUMN && p->iTable==base && p->iColumn==-1 + && !referencesOtherTables(pOrderBy, pMaskSet, 1, base) ){ *pbRev = pOrderBy->a[0].sortOrder; return 1; } @@ -959,8 +1138,7 @@ static double estLog(double N){ ** SQLITE_TEST or SQLITE_DEBUG are defined, then these routines ** are no-ops. */ -#if !defined(SQLITE_OMIT_VIRTUALTABLE) && \ - (defined(SQLITE_TEST) || defined(SQLITE_DEBUG)) +#if !defined(SQLITE_OMIT_VIRTUALTABLE) && defined(SQLITE_DEBUG) static void TRACE_IDX_INPUTS(sqlite3_index_info *p){ int i; if( !sqlite3_where_trace ) return; @@ -1042,7 +1220,7 @@ static double bestVirtualIndex( if( pIdxInfo==0 ){ WhereTerm *pTerm; int nTerm; - TRACE(("Recomputing index info for %s...\n", pTab->zName)); + WHERETRACE(("Recomputing index info for %s...\n", pTab->zName)); /* Count the number of possible WHERE clause constraints referring ** to this virtual table */ @@ -1125,13 +1303,19 @@ static double bestVirtualIndex( ** xBestIndex. */ - /* The module name must be defined */ + /* The module name must be defined. Also, by this point there must + ** be a pointer to an sqlite3_vtab structure. Otherwise + ** sqlite3ViewGetColumnNames() would have picked up the error. + */ assert( pTab->azModuleArg && pTab->azModuleArg[0] ); + assert( pTab->pVtab ); +#if 0 if( pTab->pVtab==0 ){ sqlite3ErrorMsg(pParse, "undefined module %s for table %s", pTab->azModuleArg[0], pTab->zName); return 0.0; } +#endif /* Set the aConstraint[].usable fields and initialize all ** output variables to zero. @@ -1175,7 +1359,7 @@ static double bestVirtualIndex( } sqlite3SafetyOff(pParse->db); - TRACE(("xBestIndex for %s\n", pTab->zName)); + WHERETRACE(("xBestIndex for %s\n", pTab->zName)); TRACE_IDX_INPUTS(pIdxInfo); rc = pTab->pVtab->pModule->xBestIndex(pTab->pVtab, pIdxInfo); TRACE_IDX_OUTPUTS(pIdxInfo); @@ -1190,6 +1374,7 @@ static double bestVirtualIndex( rc = sqlite3SafetyOn(pParse->db); } *(int*)&pIdxInfo->nOrderBy = nOrderBy; + return pIdxInfo->estimatedCost; } #endif /* SQLITE_OMIT_VIRTUALTABLE */ @@ -1232,9 +1417,10 @@ static double bestIndex( int rev; /* True to scan in reverse order */ int flags; /* Flags associated with pProbe */ int nEq; /* Number of == or IN constraints */ + int eqTermMask; /* Mask of valid equality operators */ double cost; /* Cost of using pProbe */ - TRACE(("bestIndex: tbl=%s notReady=%x\n", pSrc->pTab->zName, notReady)); + WHERETRACE(("bestIndex: tbl=%s notReady=%x\n", pSrc->pTab->zName, notReady)); lowestCost = SQLITE_BIG_DBL; pProbe = pSrc->pTab->pIndex; @@ -1246,7 +1432,7 @@ static double bestIndex( */ if( pProbe==0 && findTerm(pWC, iCur, -1, 0, WO_EQ|WO_IN|WO_LT|WO_LE|WO_GT|WO_GE,0)==0 && - (pOrderBy==0 || !sortableByRowid(iCur, pOrderBy, &rev)) ){ + (pOrderBy==0 || !sortableByRowid(iCur, pOrderBy, pWC->pMaskSet, &rev)) ){ *pFlags = 0; *ppIndex = 0; *pnEq = 0; @@ -1265,7 +1451,7 @@ static double bestIndex( ** a single row is generated, output is always in sorted order */ *pFlags = WHERE_ROWID_EQ | WHERE_UNIQUE; *pnEq = 1; - TRACE(("... best is rowid\n")); + WHERETRACE(("... best is rowid\n")); return 0.0; }else if( (pExpr = pTerm->pExpr)->pList!=0 ){ /* Rowid IN (LIST): cost is NlogN where N is the number of list @@ -1278,14 +1464,14 @@ static double bestIndex( ** that value so make a wild guess. */ lowestCost = 200; } - TRACE(("... rowid IN cost: %.9g\n", lowestCost)); + WHERETRACE(("... rowid IN cost: %.9g\n", lowestCost)); } /* Estimate the cost of a table scan. If we do not know how many ** entries are in the table, use 1 million as a guess. */ cost = pProbe ? pProbe->aiRowEst[0] : 1000000; - TRACE(("... table scan base cost: %.9g\n", cost)); + WHERETRACE(("... table scan base cost: %.9g\n", cost)); flags = WHERE_ROWID_RANGE; /* Check for constraints on a range of rowids in a table scan. @@ -1300,7 +1486,7 @@ static double bestIndex( flags |= WHERE_BTM_LIMIT; cost /= 3; /* Guess that rowid>EXPR eliminates two-thirds of rows */ } - TRACE(("... rowid range reduces cost to %.9g\n", cost)); + WHERETRACE(("... rowid range reduces cost to %.9g\n", cost)); }else{ flags = 0; } @@ -1308,14 +1494,14 @@ static double bestIndex( /* If the table scan does not satisfy the ORDER BY clause, increase ** the cost by NlogN to cover the expense of sorting. */ if( pOrderBy ){ - if( sortableByRowid(iCur, pOrderBy, &rev) ){ + if( sortableByRowid(iCur, pOrderBy, pWC->pMaskSet, &rev) ){ flags |= WHERE_ORDERBY|WHERE_ROWID_RANGE; if( rev ){ flags |= WHERE_REVERSE; } }else{ cost += cost*estLog(cost); - TRACE(("... sorting increases cost to %.9g\n", cost)); + WHERETRACE(("... sorting increases cost to %.9g\n", cost)); } } if( cost<lowestCost ){ @@ -1323,13 +1509,24 @@ static double bestIndex( bestFlags = flags; } + /* If the pSrc table is the right table of a LEFT JOIN then we may not + ** use an index to satisfy IS NULL constraints on that table. This is + ** because columns might end up being NULL if the table does not match - + ** a circumstance which the index cannot help us discover. Ticket #2177. + */ + if( (pSrc->jointype & JT_LEFT)!=0 ){ + eqTermMask = WO_EQ|WO_IN; + }else{ + eqTermMask = WO_EQ|WO_IN|WO_ISNULL; + } + /* Look at each index. */ for(; pProbe; pProbe=pProbe->pNext){ int i; /* Loop counter */ double inMultiplier = 1; - TRACE(("... index %s:\n", pProbe->zName)); + WHERETRACE(("... index %s:\n", pProbe->zName)); /* Count the number of columns in the index that are satisfied ** by x=EXPR constraints or x IN (...) constraints. @@ -1337,7 +1534,7 @@ static double bestIndex( flags = 0; for(i=0; i<pProbe->nColumn; i++){ int j = pProbe->aiColumn[i]; - pTerm = findTerm(pWC, iCur, j, notReady, WO_EQ|WO_IN, pProbe); + pTerm = findTerm(pWC, iCur, j, notReady, eqTermMask, pProbe); if( pTerm==0 ) break; flags |= WHERE_COLUMN_EQ; if( pTerm->eOperator & WO_IN ){ @@ -1356,7 +1553,7 @@ static double bestIndex( && nEq==pProbe->nColumn ){ flags |= WHERE_UNIQUE; } - TRACE(("...... nEq=%d inMult=%.9g cost=%.9g\n", nEq, inMultiplier, cost)); + WHERETRACE(("...... nEq=%d inMult=%.9g cost=%.9g\n", nEq, inMultiplier, cost)); /* Look for range constraints */ @@ -1373,7 +1570,7 @@ static double bestIndex( flags |= WHERE_BTM_LIMIT; cost /= 3; } - TRACE(("...... range reduces cost to %.9g\n", cost)); + WHERETRACE(("...... range reduces cost to %.9g\n", cost)); } } @@ -1381,7 +1578,7 @@ static double bestIndex( */ if( pOrderBy ){ if( (flags & WHERE_COLUMN_IN)==0 && - isSortingIndex(pParse,pProbe,iCur,pOrderBy,nEq,&rev) ){ + isSortingIndex(pParse,pWC->pMaskSet,pProbe,iCur,pOrderBy,nEq,&rev) ){ if( flags==0 ){ flags = WHERE_COLUMN_RANGE; } @@ -1391,7 +1588,7 @@ static double bestIndex( } }else{ cost += cost*estLog(cost); - TRACE(("...... orderby increases cost to %.9g\n", cost)); + WHERETRACE(("...... orderby increases cost to %.9g\n", cost)); } } @@ -1411,7 +1608,7 @@ static double bestIndex( if( m==0 ){ flags |= WHERE_IDX_ONLY; cost /= 2; - TRACE(("...... idx-only reduces cost to %.9g\n", cost)); + WHERETRACE(("...... idx-only reduces cost to %.9g\n", cost)); } } @@ -1429,9 +1626,9 @@ static double bestIndex( /* Report the best result */ *ppIndex = bestIdx; - TRACE(("best index is %s, cost=%.9g, flags=%x, nEq=%d\n", + WHERETRACE(("best index is %s, cost=%.9g, flags=%x, nEq=%d\n", bestIdx ? bestIdx->zName : "(none)", lowestCost, bestFlags, bestNEq)); - *pFlags = bestFlags; + *pFlags = bestFlags | eqTermMask; *pnEq = bestNEq; return lowestCost; } @@ -1476,30 +1673,18 @@ static void disableTerm(WhereLevel *pLevel, WhereTerm *pTerm){ } /* -** Generate code that builds a probe for an index. Details: -** -** * Check the top nColumn entries on the stack. If any -** of those entries are NULL, jump immediately to brk, -** which is the loop exit, since no index entry will match -** if any part of the key is NULL. Pop (nColumn+nExtra) -** elements from the stack. -** -** * Construct a probe entry from the top nColumn entries in -** the stack with affinities appropriate for index pIdx. -** Only nColumn elements are popped from the stack in this case -** (by OP_MakeRecord). +** Generate code that builds a probe for an index. ** +** There should be nColumn values on the stack. The index +** to be probed is pIdx. Pop the values from the stack and +** replace them all with a single record that is the index +** problem. */ static void buildIndexProbe( - Vdbe *v, - int nColumn, - int nExtra, - int brk, - Index *pIdx + Vdbe *v, /* Generate code into this VM */ + int nColumn, /* The number of columns to check for NULL */ + Index *pIdx /* Index that we will be searching */ ){ - sqlite3VdbeAddOp(v, OP_NotNull, -nColumn, sqlite3VdbeCurrentAddr(v)+3); - sqlite3VdbeAddOp(v, OP_Pop, nColumn+nExtra, 0); - sqlite3VdbeAddOp(v, OP_Goto, 0, brk); sqlite3VdbeAddOp(v, OP_MakeRecord, nColumn, 0); sqlite3IndexAffinityStr(v, pIdx); } @@ -1519,31 +1704,36 @@ static void buildIndexProbe( static void codeEqualityTerm( Parse *pParse, /* The parsing context */ WhereTerm *pTerm, /* The term of the WHERE clause to be coded */ - int brk, /* Jump here to abandon the loop */ WhereLevel *pLevel /* When level of the FROM clause we are working on */ ){ Expr *pX = pTerm->pExpr; - if( pX->op!=TK_IN ){ - assert( pX->op==TK_EQ ); + Vdbe *v = pParse->pVdbe; + if( pX->op==TK_EQ ){ sqlite3ExprCode(pParse, pX->pRight); + }else if( pX->op==TK_ISNULL ){ + sqlite3VdbeAddOp(v, OP_Null, 0, 0); #ifndef SQLITE_OMIT_SUBQUERY }else{ int iTab; - int *aIn; - Vdbe *v = pParse->pVdbe; + struct InLoop *pIn; + assert( pX->op==TK_IN ); sqlite3CodeSubselect(pParse, pX); iTab = pX->iTable; sqlite3VdbeAddOp(v, OP_Rewind, iTab, 0); VdbeComment((v, "# %.*s", pX->span.n, pX->span.z)); + if( pLevel->nIn==0 ){ + pLevel->nxt = sqlite3VdbeMakeLabel(v); + } pLevel->nIn++; - sqliteReallocOrFree((void**)&pLevel->aInLoop, - sizeof(pLevel->aInLoop[0])*2*pLevel->nIn); - aIn = pLevel->aInLoop; - if( aIn ){ - aIn += pLevel->nIn*2 - 2; - aIn[0] = iTab; - aIn[1] = sqlite3VdbeAddOp(v, OP_Column, iTab, 0); + pLevel->aInLoop = sqliteReallocOrFree(pLevel->aInLoop, + sizeof(pLevel->aInLoop[0])*pLevel->nIn); + pIn = pLevel->aInLoop; + if( pIn ){ + pIn += pLevel->nIn - 1; + pIn->iCur = iTab; + pIn->topAddr = sqlite3VdbeAddOp(v, OP_Column, iTab, 0); + sqlite3VdbeAddOp(v, OP_IsNull, -1, 0); }else{ pLevel->nIn = 0; } @@ -1579,8 +1769,7 @@ static void codeAllEqualityTerms( Parse *pParse, /* Parsing context */ WhereLevel *pLevel, /* Which nested loop of the FROM we are coding */ WhereClause *pWC, /* The WHERE clause */ - Bitmask notReady, /* Which parts of FROM have not yet been coded */ - int brk /* Jump here to end the loop */ + Bitmask notReady /* Which parts of FROM have not yet been coded */ ){ int nEq = pLevel->nEq; /* The number of == or IN constraints to code */ int termsInMem = 0; /* If true, store value in mem[] cells */ @@ -1603,17 +1792,20 @@ static void codeAllEqualityTerms( /* Evaluate the equality constraints */ - for(j=0; j<pIdx->nColumn; j++){ + assert( pIdx->nColumn>=nEq ); + for(j=0; j<nEq; j++){ int k = pIdx->aiColumn[j]; - pTerm = findTerm(pWC, iCur, k, notReady, WO_EQ|WO_IN, pIdx); + pTerm = findTerm(pWC, iCur, k, notReady, pLevel->flags, pIdx); if( pTerm==0 ) break; assert( (pTerm->flags & TERM_CODED)==0 ); - codeEqualityTerm(pParse, pTerm, brk, pLevel); + codeEqualityTerm(pParse, pTerm, pLevel); + if( (pTerm->eOperator & (WO_ISNULL|WO_IN))==0 ){ + sqlite3VdbeAddOp(v, OP_IsNull, termsInMem ? -1 : -(j+1), pLevel->brk); + } if( termsInMem ){ sqlite3VdbeAddOp(v, OP_MemStore, pLevel->iMem+j+1, 1); } } - assert( j==nEq ); /* Make sure all the constraint values are on the top of the stack */ @@ -1647,6 +1839,10 @@ static void whereInfoFree(WhereInfo *pWInfo){ sqlite3_index_info *pInfo = pWInfo->a[i].pIdxInfo; if( pInfo ){ if( pInfo->needToFreeIdxStr ){ + /* Coverage: Don't think this can be reached. By the time this + ** function is called, the index-strings have been passed + ** to the vdbe layer for deletion. + */ sqlite3_free(pInfo->idxStr); } sqliteFree(pInfo); @@ -1776,7 +1972,7 @@ WhereInfo *sqlite3WhereBegin( ** subexpression is separated by an AND operator. */ initMaskSet(&maskSet); - whereClauseInit(&wc, pParse); + whereClauseInit(&wc, pParse, &maskSet); whereSplit(&wc, pWhere, TK_AND); /* Allocate and initialize the WhereInfo structure that will become the @@ -1807,7 +2003,7 @@ WhereInfo *sqlite3WhereBegin( for(i=0; i<pTabList->nSrc; i++){ createMask(&maskSet, pTabList->a[i].iCursor); } - exprAnalyzeAll(pTabList, &maskSet, &wc); + exprAnalyzeAll(pTabList, &wc); if( sqlite3MallocFailed() ){ goto whereBeginNoMem; } @@ -1830,7 +2026,7 @@ WhereInfo *sqlite3WhereBegin( pTabItem = pTabList->a; pLevel = pWInfo->a; andFlags = ~0; - TRACE(("*** Optimizer Start ***\n")); + WHERETRACE(("*** Optimizer Start ***\n")); for(i=iFrom=0, pLevel=pWInfo->a; i<pTabList->nSrc; i++, pLevel++){ Index *pIdx; /* Index for FROM table at pTabItem */ int flags; /* Flags asssociated with pIdx */ @@ -1850,8 +2046,7 @@ WhereInfo *sqlite3WhereBegin( for(j=iFrom, pTabItem=&pTabList->a[j]; j<pTabList->nSrc; j++, pTabItem++){ int doNotReorder; /* True if this table should not be reordered */ - doNotReorder = (pTabItem->jointype & (JT_LEFT|JT_CROSS))!=0 - || (j>0 && (pTabItem[-1].jointype & (JT_LEFT|JT_CROSS))!=0); + doNotReorder = (pTabItem->jointype & (JT_LEFT|JT_CROSS))!=0; if( once && doNotReorder ) break; m = getMask(&maskSet, pTabItem->iCursor); if( (m & notReady)==0 ){ @@ -1872,6 +2067,14 @@ WhereInfo *sqlite3WhereBegin( } pIdx = 0; nEq = 0; + if( (SQLITE_BIG_DBL/2.0)<cost ){ + /* The cost is not allowed to be larger than SQLITE_BIG_DBL (the + ** inital value of lowestCost in this loop. If it is, then + ** the (cost<lowestCost) test below will never be true and + ** pLevel->pBestIdx never set. + */ + cost = (SQLITE_BIG_DBL/2.0); + } }else #endif { @@ -1891,7 +2094,7 @@ WhereInfo *sqlite3WhereBegin( } if( doNotReorder ) break; } - TRACE(("*** Optimizer choose table %d for loop %d\n", bestJ, + WHERETRACE(("*** Optimizer choose table %d for loop %d\n", bestJ, pLevel-pWInfo->a)); if( (bestFlags & WHERE_ORDERBY)!=0 ){ *ppOrderBy = 0; @@ -1910,7 +2113,7 @@ WhereInfo *sqlite3WhereBegin( notReady &= ~getMask(&maskSet, pTabList->a[bestJ].iCursor); pLevel->iFrom = bestJ; } - TRACE(("*** Optimizer Finished ***\n")); + WHERETRACE(("*** Optimizer Finished ***\n")); /* If the total query only selects a single row, then the ORDER BY ** clause is irrelevant. @@ -1986,7 +2189,9 @@ WhereInfo *sqlite3WhereBegin( sqlite3VdbeOp3(v, OP_OpenRead, iIdxCur, pIx->tnum, (char*)pKey, P3_KEYINFO_HANDOFF); } - if( (pLevel->flags & WHERE_IDX_ONLY)!=0 ){ + if( (pLevel->flags & (WHERE_IDX_ONLY|WHERE_COLUMN_RANGE))!=0 ){ + /* Only call OP_SetNumColumns on the index if we might later use + ** OP_Column on the index. */ sqlite3VdbeAddOp(v, OP_SetNumColumns, iIdxCur, pIx->nColumn+1); } sqlite3CodeVerifySchema(pParse, iDb); @@ -2002,6 +2207,7 @@ WhereInfo *sqlite3WhereBegin( int j; int iCur = pTabItem->iCursor; /* The VDBE cursor for the table */ Index *pIdx; /* The index we will be using */ + int nxt; /* Where to jump to continue with the next IN case */ int iIdxCur; /* The VDBE cursor for the index */ int omitTable; /* True if we use the index only */ int bRev; /* True if we need to scan in reverse order */ @@ -2017,15 +2223,20 @@ WhereInfo *sqlite3WhereBegin( ** for the current loop. Jump to brk to break out of a loop. ** Jump to cont to go immediately to the next iteration of the ** loop. + ** + ** When there is an IN operator, we also have a "nxt" label that + ** means to continue with the next IN value combination. When + ** there are no IN operators in the constraints, the "nxt" label + ** is the same as "brk". */ - brk = pLevel->brk = sqlite3VdbeMakeLabel(v); + brk = pLevel->brk = pLevel->nxt = sqlite3VdbeMakeLabel(v); cont = pLevel->cont = sqlite3VdbeMakeLabel(v); /* If this is the right table of a LEFT OUTER JOIN, allocate and ** initialize a memory cell that records if this table matches any ** row of the left table of the join. */ - if( pLevel->iFrom>0 && (pTabItem[-1].jointype & JT_LEFT)!=0 ){ + if( pLevel->iFrom>0 && (pTabItem[0].jointype & JT_LEFT)!=0 ){ if( !pParse->nMem ) pParse->nMem++; pLevel->iLeftJoin = pParse->nMem++; sqlite3VdbeAddOp(v, OP_MemInt, 0, pLevel->iLeftJoin); @@ -2084,9 +2295,10 @@ WhereInfo *sqlite3WhereBegin( assert( pTerm->pExpr!=0 ); assert( pTerm->leftCursor==iCur ); assert( omitTable==0 ); - codeEqualityTerm(pParse, pTerm, brk, pLevel); - sqlite3VdbeAddOp(v, OP_MustBeInt, 1, brk); - sqlite3VdbeAddOp(v, OP_NotExists, iCur, brk); + codeEqualityTerm(pParse, pTerm, pLevel); + nxt = pLevel->nxt; + sqlite3VdbeAddOp(v, OP_MustBeInt, 1, nxt); + sqlite3VdbeAddOp(v, OP_NotExists, iCur, nxt); VdbeComment((v, "pk")); pLevel->op = OP_Noop; }else if( pLevel->flags & WHERE_ROWID_RANGE ){ @@ -2159,14 +2371,13 @@ WhereInfo *sqlite3WhereBegin( int btmEq=0; /* True if btm limit uses ==. False if strictly > */ int topOp, btmOp; /* Operators for the top and bottom search bounds */ int testOp; - int nNotNull; /* Number of rows of index that must be non-NULL */ int topLimit = (pLevel->flags & WHERE_TOP_LIMIT)!=0; int btmLimit = (pLevel->flags & WHERE_BTM_LIMIT)!=0; /* Generate code to evaluate all constraint terms using == or IN ** and level the values of those terms on the stack. */ - codeAllEqualityTerms(pParse, pLevel, &wc, notReady, brk); + codeAllEqualityTerms(pParse, pLevel, &wc, notReady); /* Duplicate the equality term values because they will all be ** used twice: once to make the termination key and once to make the @@ -2181,7 +2392,6 @@ WhereInfo *sqlite3WhereBegin( ** operator and the top bound is a < or <= operator. For a descending ** index the operators are reversed. */ - nNotNull = nEq + topLimit; if( pIdx->aSortOrder[nEq]==SQLITE_SO_ASC ){ topOp = WO_LT|WO_LE; btmOp = WO_GT|WO_GE; @@ -2198,6 +2408,7 @@ WhereInfo *sqlite3WhereBegin( ** 2002-Dec-04: On a reverse-order scan, the so-called "termination" ** key computed here really ends up being the start key. */ + nxt = pLevel->nxt; if( topLimit ){ Expr *pX; int k = pIdx->aiColumn[j]; @@ -2206,6 +2417,7 @@ WhereInfo *sqlite3WhereBegin( pX = pTerm->pExpr; assert( (pTerm->flags & TERM_CODED)==0 ); sqlite3ExprCode(pParse, pX->pRight); + sqlite3VdbeAddOp(v, OP_IsNull, -(nEq+1), nxt); topEq = pTerm->eOperator & (WO_LE|WO_GE); disableTerm(pLevel, pTerm); testOp = OP_IdxGE; @@ -2216,10 +2428,10 @@ WhereInfo *sqlite3WhereBegin( if( testOp!=OP_Noop ){ int nCol = nEq + topLimit; pLevel->iMem = pParse->nMem++; - buildIndexProbe(v, nCol, nEq, brk, pIdx); + buildIndexProbe(v, nCol, pIdx); if( bRev ){ int op = topEq ? OP_MoveLe : OP_MoveLt; - sqlite3VdbeAddOp(v, op, iIdxCur, brk); + sqlite3VdbeAddOp(v, op, iIdxCur, nxt); }else{ sqlite3VdbeAddOp(v, OP_MemStore, pLevel->iMem, 1); } @@ -2244,6 +2456,7 @@ WhereInfo *sqlite3WhereBegin( pX = pTerm->pExpr; assert( (pTerm->flags & TERM_CODED)==0 ); sqlite3ExprCode(pParse, pX->pRight); + sqlite3VdbeAddOp(v, OP_IsNull, -(nEq+1), nxt); btmEq = pTerm->eOperator & (WO_LE|WO_GE); disableTerm(pLevel, pTerm); }else{ @@ -2251,14 +2464,14 @@ WhereInfo *sqlite3WhereBegin( } if( nEq>0 || btmLimit ){ int nCol = nEq + btmLimit; - buildIndexProbe(v, nCol, 0, brk, pIdx); + buildIndexProbe(v, nCol, pIdx); if( bRev ){ pLevel->iMem = pParse->nMem++; sqlite3VdbeAddOp(v, OP_MemStore, pLevel->iMem, 1); testOp = OP_IdxLT; }else{ int op = btmEq ? OP_MoveGe : OP_MoveGt; - sqlite3VdbeAddOp(v, op, iIdxCur, brk); + sqlite3VdbeAddOp(v, op, iIdxCur, nxt); } }else if( bRev ){ testOp = OP_Noop; @@ -2273,13 +2486,15 @@ WhereInfo *sqlite3WhereBegin( start = sqlite3VdbeCurrentAddr(v); if( testOp!=OP_Noop ){ sqlite3VdbeAddOp(v, OP_MemLoad, pLevel->iMem, 0); - sqlite3VdbeAddOp(v, testOp, iIdxCur, brk); + sqlite3VdbeAddOp(v, testOp, iIdxCur, nxt); if( (topEq && !bRev) || (!btmEq && bRev) ){ sqlite3VdbeChangeP3(v, -1, "+", P3_STATIC); } } - sqlite3VdbeAddOp(v, OP_RowKey, iIdxCur, 0); - sqlite3VdbeAddOp(v, OP_IdxIsNull, nNotNull, cont); + if( topLimit | btmLimit ){ + sqlite3VdbeAddOp(v, OP_Column, iIdxCur, nEq); + sqlite3VdbeAddOp(v, OP_IsNull, 1, cont); + } if( !omitTable ){ sqlite3VdbeAddOp(v, OP_IdxRowid, iIdxCur, 0); sqlite3VdbeAddOp(v, OP_MoveGe, iCur, 0); @@ -2300,34 +2515,33 @@ WhereInfo *sqlite3WhereBegin( /* Generate code to evaluate all constraint terms using == or IN ** and leave the values of those terms on the stack. */ - codeAllEqualityTerms(pParse, pLevel, &wc, notReady, brk); + codeAllEqualityTerms(pParse, pLevel, &wc, notReady); + nxt = pLevel->nxt; /* Generate a single key that will be used to both start and terminate ** the search */ - buildIndexProbe(v, nEq, 0, brk, pIdx); + buildIndexProbe(v, nEq, pIdx); sqlite3VdbeAddOp(v, OP_MemStore, pLevel->iMem, 0); /* Generate code (1) to move to the first matching element of the table. - ** Then generate code (2) that jumps to "brk" after the cursor is past + ** Then generate code (2) that jumps to "nxt" after the cursor is past ** the last matching element of the table. The code (1) is executed ** once to initialize the search, the code (2) is executed before each ** iteration of the scan to see if the scan has finished. */ if( bRev ){ /* Scan in reverse order */ - sqlite3VdbeAddOp(v, OP_MoveLe, iIdxCur, brk); + sqlite3VdbeAddOp(v, OP_MoveLe, iIdxCur, nxt); start = sqlite3VdbeAddOp(v, OP_MemLoad, pLevel->iMem, 0); - sqlite3VdbeAddOp(v, OP_IdxLT, iIdxCur, brk); + sqlite3VdbeAddOp(v, OP_IdxLT, iIdxCur, nxt); pLevel->op = OP_Prev; }else{ /* Scan in the forward order */ - sqlite3VdbeAddOp(v, OP_MoveGe, iIdxCur, brk); + sqlite3VdbeAddOp(v, OP_MoveGe, iIdxCur, nxt); start = sqlite3VdbeAddOp(v, OP_MemLoad, pLevel->iMem, 0); - sqlite3VdbeOp3(v, OP_IdxGE, iIdxCur, brk, "+", P3_STATIC); + sqlite3VdbeOp3(v, OP_IdxGE, iIdxCur, nxt, "+", P3_STATIC); pLevel->op = OP_Next; } - sqlite3VdbeAddOp(v, OP_RowKey, iIdxCur, 0); - sqlite3VdbeAddOp(v, OP_IdxIsNull, nEq, cont); if( !omitTable ){ sqlite3VdbeAddOp(v, OP_IdxRowid, iIdxCur, 0); sqlite3VdbeAddOp(v, OP_MoveGe, iCur, 0); @@ -2458,16 +2672,18 @@ void sqlite3WhereEnd(WhereInfo *pWInfo){ if( pLevel->op!=OP_Noop ){ sqlite3VdbeAddOp(v, pLevel->op, pLevel->p1, pLevel->p2); } - sqlite3VdbeResolveLabel(v, pLevel->brk); if( pLevel->nIn ){ - int *a; + struct InLoop *pIn; int j; - for(j=pLevel->nIn, a=&pLevel->aInLoop[j*2-2]; j>0; j--, a-=2){ - sqlite3VdbeAddOp(v, OP_Next, a[0], a[1]); - sqlite3VdbeJumpHere(v, a[1]-1); + sqlite3VdbeResolveLabel(v, pLevel->nxt); + for(j=pLevel->nIn, pIn=&pLevel->aInLoop[j-1]; j>0; j--, pIn--){ + sqlite3VdbeJumpHere(v, pIn->topAddr+1); + sqlite3VdbeAddOp(v, OP_Next, pIn->iCur, pIn->topAddr); + sqlite3VdbeJumpHere(v, pIn->topAddr-1); } sqliteFree(pLevel->aInLoop); } + sqlite3VdbeResolveLabel(v, pLevel->brk); if( pLevel->iLeftJoin ){ int addr; addr = sqlite3VdbeAddOp(v, OP_IfMemPos, pLevel->iLeftJoin, 0); |