diff options
Diffstat (limited to 'ext/pdo_sqlite/sqlite/src/where.c')
| -rw-r--r-- | ext/pdo_sqlite/sqlite/src/where.c | 209 |
1 files changed, 133 insertions, 76 deletions
diff --git a/ext/pdo_sqlite/sqlite/src/where.c b/ext/pdo_sqlite/sqlite/src/where.c index bdbac8112c..d783a11552 100644 --- a/ext/pdo_sqlite/sqlite/src/where.c +++ b/ext/pdo_sqlite/sqlite/src/where.c @@ -157,22 +157,31 @@ 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. @@ -354,7 +363,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 +397,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 +434,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; @@ -590,13 +602,17 @@ static void exprAnalyze( 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 +624,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 +638,10 @@ static void exprAnalyze( if( pTerm->leftCursor>=0 ){ int idxNew; pDup = sqlite3ExprDup(pExpr); + if( sqlite3MallocFailed() ){ + sqliteFree(pDup); + return; + } idxNew = whereClauseInsert(pWC, pDup, TERM_VIRTUAL|TERM_DYNAMIC); if( idxNew==0 ) return; pNew = &pWC->a[idxNew]; @@ -715,16 +735,15 @@ static void exprAnalyze( 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; @@ -857,11 +876,19 @@ 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 ){ @@ -870,9 +897,22 @@ static int isSortingIndex( return 0; } 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 +928,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 +941,25 @@ static int isSortingIndex( } j++; pTerm++; + if( iColumn<0 ){ + /* If the indexed column is the primary key and everything matches + ** so far, 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( j==pIdx->nColumn && pIdx->onError!=OE_None ){ + /* All terms of this index match some prefix of the ORDER BY clause + ** and this index is UNIQUE, so this index can be used for sorting. */ return 1; } return 0; @@ -928,8 +980,7 @@ 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 ){ *pbRev = pOrderBy->a[0].sortOrder; return 1; } @@ -1232,6 +1283,7 @@ 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)); @@ -1323,6 +1375,17 @@ 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){ @@ -1337,7 +1400,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 ){ @@ -1431,7 +1494,7 @@ static double bestIndex( *ppIndex = bestIdx; TRACE(("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 +1539,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); } @@ -1523,15 +1574,17 @@ static void codeEqualityTerm( 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; + assert( pX->op==TK_IN ); sqlite3CodeSubselect(pParse, pX); iTab = pX->iTable; sqlite3VdbeAddOp(v, OP_Rewind, iTab, 0); @@ -1603,17 +1656,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); + if( (pTerm->eOperator & WO_ISNULL)==0 ){ + sqlite3VdbeAddOp(v, OP_IsNull, termsInMem ? -1 : -(j+1), 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 */ @@ -1850,8 +1906,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 ){ @@ -1986,7 +2041,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); @@ -2025,7 +2082,7 @@ WhereInfo *sqlite3WhereBegin( ** 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); @@ -2159,7 +2216,6 @@ 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; @@ -2181,7 +2237,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; @@ -2206,6 +2261,7 @@ WhereInfo *sqlite3WhereBegin( pX = pTerm->pExpr; assert( (pTerm->flags & TERM_CODED)==0 ); sqlite3ExprCode(pParse, pX->pRight); + sqlite3VdbeAddOp(v, OP_IsNull, -(nEq+1), brk); topEq = pTerm->eOperator & (WO_LE|WO_GE); disableTerm(pLevel, pTerm); testOp = OP_IdxGE; @@ -2216,7 +2272,7 @@ 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); @@ -2244,6 +2300,7 @@ WhereInfo *sqlite3WhereBegin( pX = pTerm->pExpr; assert( (pTerm->flags & TERM_CODED)==0 ); sqlite3ExprCode(pParse, pX->pRight); + sqlite3VdbeAddOp(v, OP_IsNull, -(nEq+1), brk); btmEq = pTerm->eOperator & (WO_LE|WO_GE); disableTerm(pLevel, pTerm); }else{ @@ -2251,7 +2308,7 @@ 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); @@ -2278,8 +2335,10 @@ WhereInfo *sqlite3WhereBegin( 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); @@ -2305,7 +2364,7 @@ WhereInfo *sqlite3WhereBegin( /* 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. @@ -2326,8 +2385,6 @@ WhereInfo *sqlite3WhereBegin( sqlite3VdbeOp3(v, OP_IdxGE, iIdxCur, brk, "+", 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); |