Index: src/sqliteInt.h ================================================================== --- src/sqliteInt.h +++ src/sqliteInt.h @@ -9,11 +9,11 @@ ** May you share freely, never taking more than you give. ** ************************************************************************* ** Internal interface definitions for SQLite. ** -** @(#) $Id: sqliteInt.h,v 1.347 2004/12/18 18:40:27 drh Exp $ +** @(#) $Id: sqliteInt.h,v 1.348 2004/12/19 00:11:35 drh Exp $ */ #ifndef _SQLITEINT_H_ #define _SQLITEINT_H_ /* @@ -307,10 +307,11 @@ typedef struct KeyClass KeyClass; typedef struct CollSeq CollSeq; typedef struct KeyInfo KeyInfo; typedef struct SqlCursor SqlCursor; typedef struct Fetch Fetch; +typedef struct CursorSubst CursorSubst; /* ** Each database file to be accessed by the system is an instance ** of the following structure. There are normally two of these structures ** in the sqlite.aDb[] array. aDb[0] is the main database file and @@ -908,12 +909,13 @@ ** is intended to be private the the where.c module and should not be ** access or modified by other modules. */ struct WhereLevel { int iMem; /* Memory cell used by this level */ - Index *pIdx; /* Index used */ - int iCur; /* Cursor number used for this index */ + Index *pIdx; /* Index used. NULL if no index */ + int iTabCur; /* The VDBE cursor used to access the table */ + int iIdxCur; /* The VDBE cursor used to acesss pIdx */ int score; /* How well this indexed scored */ int brk; /* Jump here to break out of the loop */ int cont; /* Jump here to continue with the next loop cycle */ int op, p1, p2; /* Opcode used to terminate the loop */ int iLeftJoin; /* Memory cell used to implement LEFT OUTER JOIN */ @@ -930,10 +932,11 @@ ** into the second half to give some continuity. */ struct WhereInfo { Parse *pParse; SrcList *pTabList; /* List of tables in the join */ + 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 */ WhereLevel a[1]; /* Information about each nest loop in the WHERE */ }; @@ -1065,11 +1068,10 @@ const char *zTail; /* All SQL text past the last semicolon parsed */ Table *pNewTable; /* A table being constructed by CREATE TABLE */ Trigger *pNewTrigger; /* Trigger under construct by a CREATE TRIGGER */ TriggerStack *trigStack; /* Trigger actions being coded */ const char *zAuthContext; /* The 6th parameter to db->xAuth callbacks */ - }; /* ** An instance of the following structure can be declared on a stack and used ** to save the Parse.zAuthContext value so that it can be restored later. Index: src/vdbe.c ================================================================== --- src/vdbe.c +++ src/vdbe.c @@ -41,11 +41,11 @@ ** documentation, headers files, or other derived files. The formatting ** of the code in this file is, therefore, important. See other comments ** in this file for details. If in doubt, do not deviate from existing ** commenting and indentation practices when changing or adding code. ** -** $Id: vdbe.c,v 1.433 2004/12/07 14:06:13 drh Exp $ +** $Id: vdbe.c,v 1.434 2004/12/19 00:11:35 drh Exp $ */ #include "sqliteInt.h" #include "os.h" #include #include "vdbeInt.h" @@ -1664,15 +1664,10 @@ assert( p->apCsr[pOp->p1]!=0 ); p->apCsr[pOp->p1]->nField = pOp->p2; break; } -/* Opcode: IdxColumn P1 * * -** -** P1 is a cursor opened on an index. Push the first field from the -** current index key onto the stack. -*/ /* Opcode: Column P1 P2 * ** ** Interpret the data that cursor P1 points to as a structure built using ** the MakeRecord instruction. (See the MakeRecord opcode for additional ** information about the format of the data.) Push onto the stack the value @@ -1686,11 +1681,10 @@ ** next on the stack is used. And so forth. The value pushed is always ** just a pointer into the record which is stored further down on the ** stack. The column value is not copied. The number of columns in the ** record is stored on the stack just above the record itself. */ -case OP_IdxColumn: case OP_Column: { u32 payloadSize; /* Number of bytes in the record */ int p1 = pOp->p1; /* P1 value of the opcode */ int p2 = pOp->p2; /* column number to retrieve */ Cursor *pC = 0; /* The VDBE cursor */ @@ -3480,11 +3474,11 @@ } /* Opcode: IdxRecno P1 * * ** ** Push onto the stack an integer which is the varint located at the -** end of the index key pointed to by cursor P1. These integer should be +** end of the index key pointed to by cursor P1. This integer should be ** the record number of the table entry to which this index entry points. ** ** See also: Recno, MakeIdxKey. */ case OP_IdxRecno: { Index: src/where.c ================================================================== --- src/where.c +++ src/where.c @@ -14,11 +14,11 @@ ** generating the code that loops through a table looking for applicable ** rows. Indices are selected and used to speed the search when doing ** so is applicable. Because this module is responsible for selecting ** indices, you might also think of this module as the "query optimizer". ** -** $Id: where.c,v 1.122 2004/12/18 18:40:27 drh Exp $ +** $Id: where.c,v 1.123 2004/12/19 00:11:35 drh Exp $ */ #include "sqliteInt.h" /* ** The query generator uses an array of instances of this structure to @@ -294,107 +294,10 @@ } } } -/* -** pOrderBy is an ORDER BY clause from a SELECT statement. pTab is the -** left-most table in the FROM clause of that same SELECT statement and -** the table has a cursor number of "base". -** -** This routine attempts to find an index for pTab that generates the -** correct record sequence for the given ORDER BY clause. The return value -** is a pointer to an index that does the job. NULL is returned if the -** table has no index that will generate the correct sort order. -** -** If there are two or more indices that generate the correct sort order -** and pPreferredIdx is one of those indices, then return pPreferredIdx. -** -** nEqCol is the number of columns of pPreferredIdx that are used as -** equality constraints. Any index returned must have exactly this same -** set of columns. The ORDER BY clause only matches index columns beyond the -** the first nEqCol columns. -** -** All terms of the ORDER BY clause must be either ASC or DESC. The -** *pbRev value is set to 1 if the ORDER BY clause is all DESC and it is -** set to 0 if the ORDER BY clause is all ASC. -** -** TODO: If earlier terms of an ORDER BY clause match all terms of a -** UNIQUE index, then subsequent terms of the ORDER BY can be ignored. -** This optimization needs to be implemented. -*/ -static Index *findSortingIndex( - Parse *pParse, /* Parsing context */ - Table *pTab, /* The table to be sorted */ - int base, /* Cursor number for pTab */ - ExprList *pOrderBy, /* The ORDER BY clause */ - Index *pPreferredIdx, /* Use this index, if possible and not NULL */ - int nEqCol, /* Number of index columns used with == constraints */ - int *pbRev /* Set to 1 if ORDER BY is DESC */ -){ - int i, j; /* Loop counters */ - Index *pMatch; /* Best matching index so far */ - Index *pIdx; /* Current index */ - int sortOrder; /* Which direction we are sorting */ - sqlite3 *db = pParse->db; - - assert( pOrderBy!=0 ); - assert( pOrderBy->nExpr>0 ); - assert( pPreferredIdx!=0 || nEqCol==0 ); - sortOrder = pOrderBy->a[0].sortOrder; - for(i=0; inExpr; i++){ - Expr *p; - if( pOrderBy->a[i].sortOrder!=sortOrder ){ - /* Indices can only be used if all ORDER BY terms are either - ** DESC or ASC. Indices cannot be used on a mixture. */ - return 0; - } - p = pOrderBy->a[i].pExpr; - if( p->op!=TK_COLUMN || p->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; - } - } - - /* If we get this far, it means the ORDER BY clause consists of columns - ** that are all either ascending or descending and which refer only to - ** the left-most table of the FROM clause. Find the index that is best - ** used for sorting. - */ - pMatch = 0; - for(pIdx=pTab->pIndex; pIdx; pIdx=pIdx->pNext){ - int nExpr = pOrderBy->nExpr; - if( pIdx->nColumn < nEqCol || pIdx->nColumn < nExpr ) continue; - for(i=j=0; ia[j].pExpr); - if( !pColl ) pColl = db->pDfltColl; - if( pPreferredIdx->aiColumn[i]!=pIdx->aiColumn[i] ) break; - if( pPreferredIdx->keyInfo.aColl[i]!=pIdx->keyInfo.aColl[i] ) break; - if( ja[j].pExpr->iColumn==pIdx->aiColumn[i] && - pColl==pIdx->keyInfo.aColl[i] - ){ - j++; - } - } - if( ia[i+j].pExpr); - if( !pColl ) pColl = db->pDfltColl; - if( pOrderBy->a[i+j].pExpr->iColumn!=pIdx->aiColumn[i+nEqCol] || - pColl!=pIdx->keyInfo.aColl[i+nEqCol] ) break; - } - if( i+j>=nExpr ){ - pMatch = pIdx; - if( pIdx==pPreferredIdx ) break; - } - } - *pbRev = sortOrder==SQLITE_SO_DESC; - return pMatch; -} - /* ** This routine decides if pIdx can be used to satisfy the ORDER BY ** clause. If it can, it returns 1. If pIdx cannot satisfy the ** ORDER BY clause, this routine returns 0. ** @@ -448,12 +351,13 @@ ** left-most table of the FROM clause */ return 0; } pColl = sqlite3ExprCollSeq(pParse, pExpr); if( !pColl ) pColl = db->pDfltColl; - if( pExpr->iColumn!=pIdx->aiColumn[i] && pColl!=pIdx->keyInfo.aColl[i] ){ - if( i<=nEqCol ){ + if( pExpr->iColumn!=pIdx->aiColumn[i] || pColl!=pIdx->keyInfo.aColl[i] ){ + /* Term j of the ORDER BY clause does not match column i of the index */ + if( iiTable; Vdbe *v = pParse->pVdbe; sqlite3VdbeAddOp(v, OP_Rewind, iTab, brk); sqlite3VdbeAddOp(v, OP_KeyAsData, iTab, 1); - pLevel->inP2 = sqlite3VdbeAddOp(v, OP_IdxColumn, iTab, 0); + pLevel->inP2 = sqlite3VdbeAddOp(v, OP_Column, iTab, 0); pLevel->inOp = OP_Next; pLevel->inP1 = iTab; } disableTerm(pLevel, &pTerm->p); } @@ -679,17 +583,19 @@ WhereInfo *pWInfo; /* Will become the return value of this function */ Vdbe *v = pParse->pVdbe; /* The virtual database engine */ int brk, cont = 0; /* Addresses used during code generation */ int nExpr; /* Number of subexpressions in the WHERE clause */ Bitmask loopMask; /* One bit set for each outer loop */ - int haveKey = 0; /* True if KEY is on the stack */ + int haveRowid = 0; /* True if the ROWID is on the stack */ ExprInfo *pTerm; /* A single term in the WHERE clause; ptr to aExpr[] */ ExprMaskSet maskSet; /* The expression mask set */ int iDirectEq[BMS]; /* Term of the form ROWID==X for the N-th table */ int iDirectLt[BMS]; /* Term of the form ROWIDX or ROWID>=X */ ExprInfo aExpr[101]; /* The WHERE clause is divided into these terms */ + struct SrcList_item *pTabItem; /* A single entry from pTabList */ + WhereLevel *pLevel; /* A single level in the pWInfo list */ /* pushKey is only allowed if there is a single table (as in an INSERT or ** UPDATE statement) */ assert( pushKey==0 || pTabList->nSrc==1 ); @@ -769,16 +675,17 @@ ** Actually, if there are more than 32 tables in the join, only the ** first 32 tables are candidates for indices. This is (again) due ** to the limit of 32 bits in an integer bitmask. */ loopMask = 0; - for(i=0; inSrc && ia; + pLevel = pWInfo->a; + for(i=0; inSrc && ia[i]; - int iCur = pTabList->a[i].iCursor; /* The cursor for this table */ + int iCur = pTabItem->iCursor; /* The cursor for this table */ Bitmask mask = getMask(&maskSet, iCur); /* Cursor mask for this table */ - Table *pTab = pTabList->a[i].pTab; + Table *pTab = pTabItem->pTab; Index *pIdx; Index *pBestIdx = 0; int bestScore = 0; int bestRev = 0; @@ -788,11 +695,11 @@ ** form ROWIDexpr or ROWID>=expr set iDirectGt[i]. ** ** (Added:) Treat ROWID IN expr like ROWID=expr. */ - pLevel->iCur = -1; + pLevel->iIdxCur = -1; iDirectEq[i] = -1; iDirectLt[i] = -1; iDirectGt[i] = -1; for(pTerm=aExpr, j=0; jp; @@ -931,16 +838,32 @@ if( m & gtMask ) score+=8; /* Increase score for a > constraint */ if( score==0 && inMask ) score = 16; /* Default score for IN constraint */ /* Give bonus points if this index can be used for sorting */ - if( i==0 && score>0 && ppOrderBy && *ppOrderBy ){ + if( i==0 && score!=16 && ppOrderBy && *ppOrderBy ){ int base = pTabList->a[0].iCursor; if( isSortingIndex(pParse, pIdx, pTab, base, *ppOrderBy, nEq, &bRev) ){ score += 2; } } + + /* Check to see if we can get away with using just the index without + ** ever reading the table. If that is the case, then add one bonus + ** point to the score. + */ + if( score && pTabItem->colUsed < (((Bitmask)1)<<(BMS-1)) ){ + for(m=0, j=0; jnColumn; j++){ + int x = pIdx->aiColumn[j]; + if( xcolUsed & m)==pTabItem->colUsed ){ + score++; + } + } /* If the score for this index is the best we have seen so far, then ** save it */ if( score>bestScore ){ @@ -952,85 +875,100 @@ pLevel->pIdx = pBestIdx; pLevel->score = bestScore; pLevel->bRev = bestRev; loopMask |= mask; if( pBestIdx ){ - pLevel->iCur = pParse->nTab++; + pLevel->iIdxCur = pParse->nTab++; } } /* Check to see if the ORDER BY clause is or can be satisfied by the ** use of an index on the first table. */ if( ppOrderBy && *ppOrderBy && pTabList->nSrc>0 ){ - Index *pSortIdx = 0; /* Index that satisfies the ORDER BY clause */ - Index *pIdx; /* Index derived from the WHERE clause */ - Table *pTab; /* Left-most table in the FROM clause */ - int bRev = 0; /* True to reverse the output order */ - int iCur; /* Btree-cursor that will be used by pTab */ - WhereLevel *pLevel0 = &pWInfo->a[0]; - - pTab = pTabList->a[0].pTab; - pIdx = pLevel0->pIdx; - iCur = pTabList->a[0].iCursor; - if( pIdx==0 && sortableByRowid(iCur, *ppOrderBy, &bRev) ){ - /* The ORDER BY clause specifies ROWID order, which is what we - ** were going to be doing anyway... - */ - *ppOrderBy = 0; - pLevel0->bRev = bRev; - }else if( pLevel0->score==16 ){ - /* If there is already an IN index on the left-most table, - ** it will not give the correct sort order. - ** So, pretend that no suitable index is found. - */ - }else if( iDirectEq[0]>=0 || iDirectLt[0]>=0 || iDirectGt[0]>=0 ){ - /* If the left-most column is accessed using its ROWID, then do - ** not try to sort by index. But do delete the ORDER BY clause - ** if it is redundant. - */ - }else{ - int nEqCol = (pLevel0->score+16)/32; - pSortIdx = findSortingIndex(pParse, pTab, iCur, - *ppOrderBy, pIdx, nEqCol, &bRev); - } - if( pSortIdx && (pIdx==0 || pIdx==pSortIdx) ){ - if( pIdx==0 ){ - pLevel0->pIdx = pSortIdx; - pLevel0->iCur = pParse->nTab++; - } - pLevel0->bRev = bRev; - *ppOrderBy = 0; - } + Index *pIdx; /* Index derived from the WHERE clause */ + Table *pTab; /* Left-most table in the FROM clause */ + int bRev = 0; /* True to reverse the output order */ + int iCur; /* Btree-cursor that will be used by pTab */ + WhereLevel *pLevel0 = &pWInfo->a[0]; + + pTab = pTabList->a[0].pTab; + pIdx = pLevel0->pIdx; + iCur = pTabList->a[0].iCursor; + if( pIdx==0 && sortableByRowid(iCur, *ppOrderBy, &bRev) ){ + /* The ORDER BY clause specifies ROWID order, which is what we + ** were going to be doing anyway... + */ + *ppOrderBy = 0; + pLevel0->bRev = bRev; + }else if( pLevel0->score==16 ){ + /* If there is already an IN index on the left-most table, + ** it will not give the correct sort order. + ** So, pretend that no suitable index is found. + */ + }else if( iDirectEq[0]>=0 || iDirectLt[0]>=0 || iDirectGt[0]>=0 ){ + /* If the left-most column is accessed using its ROWID, then do + ** not try to sort by index. But do delete the ORDER BY clause + ** if it is redundant. + */ + }else if( (pLevel0->score&2)!=0 ){ + /* The index that was selected for searching will cause rows to + ** appear in sorted order. + */ + *ppOrderBy = 0; + } } - /* Open all tables in the pTabList and all indices used by those tables. + /* Open all tables in the pTabList and any indices selected for + ** searching those tables. */ sqlite3CodeVerifySchema(pParse, -1); /* Insert the cookie verifier Goto */ - for(i=0; inSrc; i++){ + pLevel = pWInfo->a; + for(i=0, pTabItem=pTabList->a; inSrc; i++, pTabItem++, pLevel++){ Table *pTab; Index *pIx; + int iIdxCur = pLevel->iIdxCur; - pTab = pTabList->a[i].pTab; + pTab = pTabItem->pTab; if( pTab->isTransient || pTab->pSelect ) continue; - sqlite3OpenTableForReading(v, pTabList->a[i].iCursor, pTab); - sqlite3CodeVerifySchema(pParse, pTab->iDb); - if( (pIx = pWInfo->a[i].pIdx)!=0 ){ + if( (pLevel->score & 1)==0 ){ + sqlite3OpenTableForReading(v, pTabItem->iCursor, pTab); + } + pLevel->iTabCur = pTabItem->iCursor; + if( (pIx = pLevel->pIdx)!=0 ){ sqlite3VdbeAddOp(v, OP_Integer, pIx->iDb, 0); - sqlite3VdbeOp3(v, OP_OpenRead, pWInfo->a[i].iCur, pIx->tnum, + sqlite3VdbeOp3(v, OP_OpenRead, iIdxCur, pIx->tnum, (char*)&pIx->keyInfo, P3_KEYINFO); } + if( (pLevel->score & 1)!=0 ){ + sqlite3VdbeAddOp(v, OP_KeyAsData, iIdxCur, 1); + sqlite3VdbeAddOp(v, OP_SetNumColumns, iIdxCur, pIx->nColumn+1); + } + sqlite3CodeVerifySchema(pParse, pTab->iDb); } + pWInfo->iTop = sqlite3VdbeCurrentAddr(v); /* Generate the code to do the search */ loopMask = 0; - for(i=0; inSrc; i++){ + pLevel = pWInfo->a; + pTabItem = pTabList->a; + for(i=0; inSrc; i++, pTabItem++, pLevel++){ int j, k; - int iCur = pTabList->a[i].iCursor; - Index *pIdx; - WhereLevel *pLevel = &pWInfo->a[i]; + int iCur = pTabItem->iCursor; /* The VDBE cursor for the table */ + Index *pIdx; /* The index we will be using */ + int iIdxCur; /* The VDBE cursor for the index */ + int omitTable; /* True if we use the index only */ + + pIdx = pLevel->pIdx; + iIdxCur = pLevel->iIdxCur; + pLevel->inOp = OP_Noop; + + /* Check to see if it is appropriate to omit the use of the table + ** here and use its index instead. + */ + omitTable = (pLevel->score&1)!=0; /* 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. */ @@ -1040,12 +978,10 @@ sqlite3VdbeAddOp(v, OP_String8, 0, 0); sqlite3VdbeAddOp(v, OP_MemStore, pLevel->iLeftJoin, 1); VdbeComment((v, "# init LEFT JOIN no-match flag")); } - pIdx = pLevel->pIdx; - pLevel->inOp = OP_Noop; if( i=0 ){ /* Case 1: We can directly reference a single row using an ** equality comparison against the ROWID field. Or ** we reference multiple rows using a "rowid IN (...)" ** construct. @@ -1052,18 +988,19 @@ */ assert( kp!=0 ); assert( pTerm->idxLeft==iCur ); + assert( omitTable==0 ); brk = pLevel->brk = sqlite3VdbeMakeLabel(v); codeEqualityTerm(pParse, pTerm, brk, pLevel); cont = pLevel->cont = sqlite3VdbeMakeLabel(v); sqlite3VdbeAddOp(v, OP_MustBeInt, 1, brk); - haveKey = 0; sqlite3VdbeAddOp(v, OP_NotExists, iCur, brk); + haveRowid = 0; pLevel->op = OP_Noop; - }else if( pIdx!=0 && pLevel->score>0 && (pLevel->score&0x0c)==0 ){ + }else if( pIdx!=0 && pLevel->score>3 && (pLevel->score&0x0c)==0 ){ /* Case 2: There is an index and all terms of the WHERE clause that ** refer to the index using the "==" or "IN" operators. */ int start; int nColumn = (pLevel->score+16)/32; @@ -1098,39 +1035,39 @@ ** 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( pLevel->bRev ){ /* Scan in reverse order */ - sqlite3VdbeAddOp(v, OP_MoveLe, pLevel->iCur, brk); + sqlite3VdbeAddOp(v, OP_MoveLe, iIdxCur, brk); start = sqlite3VdbeAddOp(v, OP_MemLoad, pLevel->iMem, 0); - sqlite3VdbeAddOp(v, OP_IdxLT, pLevel->iCur, brk); + sqlite3VdbeAddOp(v, OP_IdxLT, iIdxCur, brk); pLevel->op = OP_Prev; }else{ /* Scan in the forward order */ - sqlite3VdbeAddOp(v, OP_MoveGe, pLevel->iCur, brk); + sqlite3VdbeAddOp(v, OP_MoveGe, iIdxCur, brk); start = sqlite3VdbeAddOp(v, OP_MemLoad, pLevel->iMem, 0); - sqlite3VdbeOp3(v, OP_IdxGE, pLevel->iCur, brk, "+", P3_STATIC); + sqlite3VdbeOp3(v, OP_IdxGE, iIdxCur, brk, "+", P3_STATIC); pLevel->op = OP_Next; } - sqlite3VdbeAddOp(v, OP_RowKey, pLevel->iCur, 0); + sqlite3VdbeAddOp(v, OP_RowKey, iIdxCur, 0); sqlite3VdbeAddOp(v, OP_IdxIsNull, nColumn, cont); - sqlite3VdbeAddOp(v, OP_IdxRecno, pLevel->iCur, 0); - if( i==pTabList->nSrc-1 && pushKey ){ - haveKey = 1; + if( omitTable ){ + haveRowid = 0; }else{ - sqlite3VdbeAddOp(v, OP_MoveGe, iCur, 0); - haveKey = 0; + sqlite3VdbeAddOp(v, OP_IdxRecno, iIdxCur, 0); + haveRowid = 1; } - pLevel->p1 = pLevel->iCur; + pLevel->p1 = iIdxCur; pLevel->p2 = start; }else if( i=0 || iDirectGt[i]>=0) ){ /* Case 3: We have an inequality comparison against the ROWID field. */ int testOp = OP_Noop; int start; int bRev = pLevel->bRev; + assert( omitTable==0 ); brk = pLevel->brk = sqlite3VdbeMakeLabel(v); cont = pLevel->cont = sqlite3VdbeMakeLabel(v); if( bRev ){ int t = iDirectGt[i]; iDirectGt[i] = iDirectLt[i]; @@ -1176,18 +1113,19 @@ if( testOp!=OP_Noop ){ sqlite3VdbeAddOp(v, OP_Recno, iCur, 0); sqlite3VdbeAddOp(v, OP_MemLoad, pLevel->iMem, 0); sqlite3VdbeAddOp(v, testOp, 0, brk); } - haveKey = 0; + haveRowid = 0; }else if( pIdx==0 ){ /* Case 4: There is no usable index. We must do a complete ** scan of the entire database table. */ int start; int opRewind; + assert( omitTable==0 ); brk = pLevel->brk = sqlite3VdbeMakeLabel(v); cont = pLevel->cont = sqlite3VdbeMakeLabel(v); if( pLevel->bRev ){ opRewind = OP_Last; pLevel->op = OP_Prev; @@ -1197,11 +1135,11 @@ } sqlite3VdbeAddOp(v, opRewind, iCur, brk); start = sqlite3VdbeCurrentAddr(v); pLevel->p1 = iCur; pLevel->p2 = start; - haveKey = 0; + haveRowid = 0; }else{ /* Case 5: The WHERE clause term that refers to the right-most ** column of the index is an inequality. For example, if ** the index is on (x,y,z) and the WHERE clause is of the ** form "x=5 AND y<10" then this case is used. Only the @@ -1281,16 +1219,16 @@ int nCol = nEqColumn + ((score & 4)!=0); pLevel->iMem = pParse->nMem++; buildIndexProbe(v, nCol, brk, pIdx); if( pLevel->bRev ){ int op = leFlag ? OP_MoveLe : OP_MoveLt; - sqlite3VdbeAddOp(v, op, pLevel->iCur, brk); + sqlite3VdbeAddOp(v, op, iIdxCur, brk); }else{ sqlite3VdbeAddOp(v, OP_MemStore, pLevel->iMem, 1); } }else if( pLevel->bRev ){ - sqlite3VdbeAddOp(v, OP_Last, pLevel->iCur, brk); + sqlite3VdbeAddOp(v, OP_Last, iIdxCur, brk); } /* Generate the start key. This is the key that defines the lower ** bound on the search. There is no start key if there are no ** equality terms and if there is no "X>..." term. In @@ -1325,44 +1263,43 @@ pLevel->iMem = pParse->nMem++; sqlite3VdbeAddOp(v, OP_MemStore, pLevel->iMem, 1); testOp = OP_IdxLT; }else{ int op = geFlag ? OP_MoveGe : OP_MoveGt; - sqlite3VdbeAddOp(v, op, pLevel->iCur, brk); + sqlite3VdbeAddOp(v, op, iIdxCur, brk); } }else if( pLevel->bRev ){ testOp = OP_Noop; }else{ - sqlite3VdbeAddOp(v, OP_Rewind, pLevel->iCur, brk); + sqlite3VdbeAddOp(v, OP_Rewind, iIdxCur, brk); } /* Generate the the top of the loop. If there is a termination ** key we have to test for that key and abort at the top of the ** loop. */ start = sqlite3VdbeCurrentAddr(v); if( testOp!=OP_Noop ){ sqlite3VdbeAddOp(v, OP_MemLoad, pLevel->iMem, 0); - sqlite3VdbeAddOp(v, testOp, pLevel->iCur, brk); + sqlite3VdbeAddOp(v, testOp, iIdxCur, brk); if( (leFlag && !pLevel->bRev) || (!geFlag && pLevel->bRev) ){ sqlite3VdbeChangeP3(v, -1, "+", P3_STATIC); } } - sqlite3VdbeAddOp(v, OP_RowKey, pLevel->iCur, 0); + sqlite3VdbeAddOp(v, OP_RowKey, iIdxCur, 0); sqlite3VdbeAddOp(v, OP_IdxIsNull, nEqColumn + ((score&4)!=0), cont); - sqlite3VdbeAddOp(v, OP_IdxRecno, pLevel->iCur, 0); - if( i==pTabList->nSrc-1 && pushKey ){ - haveKey = 1; + if( omitTable ){ + haveRowid = 0; }else{ - sqlite3VdbeAddOp(v, OP_MoveGe, iCur, 0); - haveKey = 0; + sqlite3VdbeAddOp(v, OP_IdxRecno, iIdxCur, 0); + haveRowid = 1; } /* Record the instruction used to terminate the loop. */ pLevel->op = pLevel->bRev ? OP_Prev : OP_Next; - pLevel->p1 = pLevel->iCur; + pLevel->p1 = iIdxCur; pLevel->p2 = start; } loopMask |= getMask(&maskSet, iCur); /* Insert code to test every subexpression that can be completely @@ -1372,13 +1309,17 @@ if( pTerm->p==0 ) continue; if( (pTerm->prereqAll & loopMask)!=pTerm->prereqAll ) continue; if( pLevel->iLeftJoin && !ExprHasProperty(pTerm->p,EP_FromJoin) ){ continue; } - if( haveKey ){ - haveKey = 0; - sqlite3VdbeAddOp(v, OP_MoveGe, iCur, 0); + if( haveRowid ){ + haveRowid = 0; + if( omitTable ){ + sqlite3VdbeAddOp(v, OP_Pop, 1, 0); + }else{ + sqlite3VdbeAddOp(v, OP_MoveGe, iCur, 0); + } } sqlite3ExprIfFalse(pParse, pTerm->p, cont, 1); pTerm->p = 0; } brk = cont; @@ -1392,25 +1333,35 @@ sqlite3VdbeAddOp(v, OP_MemStore, pLevel->iLeftJoin, 1); VdbeComment((v, "# record LEFT JOIN hit")); for(pTerm=aExpr, j=0; jp==0 ) continue; if( (pTerm->prereqAll & loopMask)!=pTerm->prereqAll ) continue; - if( haveKey ){ - /* Cannot happen. "haveKey" can only be true if pushKey is true + if( haveRowid ){ + /* Cannot happen. "haveRowid" can only be true if pushKey is true ** an pushKey can only be true for DELETE and UPDATE and there are ** no outer joins with DELETE and UPDATE. */ - haveKey = 0; + assert( 0 ); + haveRowid = 0; sqlite3VdbeAddOp(v, OP_MoveGe, iCur, 0); } sqlite3ExprIfFalse(pParse, pTerm->p, cont, 1); pTerm->p = 0; } } + + if( haveRowid && (inSrc-1 || !pushKey) ){ + haveRowid = 0; + if( omitTable ){ + sqlite3VdbeAddOp(v, OP_Pop, 1, 0); + }else{ + sqlite3VdbeAddOp(v, OP_MoveGe, iCur, 0); + } + } } pWInfo->iContinue = cont; - if( pushKey && !haveKey ){ + if( pushKey && !haveRowid ){ sqlite3VdbeAddOp(v, OP_Recno, pTabList->a[0].iCursor, 0); } freeMaskSet(&maskSet); return pWInfo; } @@ -1422,11 +1373,14 @@ void sqlite3WhereEnd(WhereInfo *pWInfo){ Vdbe *v = pWInfo->pParse->pVdbe; int i; WhereLevel *pLevel; SrcList *pTabList = pWInfo->pTabList; + struct SrcList_item *pTabItem; + /* Generate loop termination code. + */ for(i=pTabList->nSrc-1; i>=0; i--){ pLevel = &pWInfo->a[i]; sqlite3VdbeResolveLabel(v, pLevel->cont); if( pLevel->op!=OP_Noop ){ sqlite3VdbeAddOp(v, pLevel->op, pLevel->p1, pLevel->p2); @@ -1436,27 +1390,74 @@ sqlite3VdbeAddOp(v, pLevel->inOp, pLevel->inP1, pLevel->inP2); } if( pLevel->iLeftJoin ){ int addr; addr = sqlite3VdbeAddOp(v, OP_MemLoad, pLevel->iLeftJoin, 0); - sqlite3VdbeAddOp(v, OP_NotNull, 1, addr+4 + (pLevel->iCur>=0)); + sqlite3VdbeAddOp(v, OP_NotNull, 1, addr+4 + (pLevel->iIdxCur>=0)); sqlite3VdbeAddOp(v, OP_NullRow, pTabList->a[i].iCursor, 0); - if( pLevel->iCur>=0 ){ - sqlite3VdbeAddOp(v, OP_NullRow, pLevel->iCur, 0); + if( pLevel->iIdxCur>=0 ){ + sqlite3VdbeAddOp(v, OP_NullRow, pLevel->iIdxCur, 0); } sqlite3VdbeAddOp(v, OP_Goto, 0, pLevel->top); } } + + /* The "break" point is here, just past the end of the outer loop. + ** Set it. + */ sqlite3VdbeResolveLabel(v, pWInfo->iBreak); - for(i=0; inSrc; i++){ - Table *pTab = pTabList->a[i].pTab; + + /* Close all of the cursors + */ + pLevel = pWInfo->a; + pTabItem = pTabList->a; + for(i=0; inSrc; i++, pTabItem++, pLevel++){ + Table *pTab = pTabItem->pTab; assert( pTab!=0 ); if( pTab->isTransient || pTab->pSelect ) continue; - pLevel = &pWInfo->a[i]; - sqlite3VdbeAddOp(v, OP_Close, pTabList->a[i].iCursor, 0); + if( (pLevel->score & 1)==0 ){ + sqlite3VdbeAddOp(v, OP_Close, pTabItem->iCursor, 0); + } if( pLevel->pIdx!=0 ){ - sqlite3VdbeAddOp(v, OP_Close, pLevel->iCur, 0); + sqlite3VdbeAddOp(v, OP_Close, pLevel->iIdxCur, 0); + } + + /* Make all cursor substitutions for cases where we want to use + ** just the index and never reference the table. + ** + ** Calls to the code generator in between sqlite3WhereBegin and + ** sqlite3WhereEnd will have created code that references the table + ** directly. This loop scans all that code looking for opcodes + ** that reference the table and converts them into opcodes that + ** reference the index. + */ + if( pLevel->score & 1 ){ + int i, j, last; + VdbeOp *pOp; + Index *pIdx = pLevel->pIdx; + + assert( pIdx!=0 ); + pOp = sqlite3VdbeGetOp(v, pWInfo->iTop); + last = sqlite3VdbeCurrentAddr(v); + for(i=pWInfo->iTop; ip1!=pLevel->iTabCur ) continue; + if( pOp->opcode==OP_Column ){ + pOp->p1 = pLevel->iIdxCur; + for(j=0; jnColumn; j++){ + if( pOp->p2==pIdx->aiColumn[j] ){ + pOp->p2 = j; + break; + } + } + }else if( pOp->opcode==OP_Recno ){ + pOp->p1 = pLevel->iIdxCur; + pOp->opcode = OP_IdxRecno; + } + } } } + + /* Final cleanup + */ sqliteFree(pWInfo); return; } Index: test/collate4.test ================================================================== --- test/collate4.test +++ test/collate4.test @@ -10,11 +10,11 @@ # #*********************************************************************** # This file implements regression tests for SQLite library. The # focus of this script is page cache subsystem. # -# $Id: collate4.test,v 1.5 2004/11/22 19:12:21 drh Exp $ +# $Id: collate4.test,v 1.6 2004/12/19 00:11:36 drh Exp $ set testdir [file dirname $argv0] source $testdir/tester.tcl db collate TEXT text_collate @@ -349,11 +349,11 @@ CREATE INDEX collate4i1 ON collate4t1(a); } count { SELECT * FROM collate4t2, collate4t1 WHERE a = b; } -} {A a A A 7} +} {A a A A 5} do_test collate4-2.1.3 { count { SELECT * FROM collate4t2, collate4t1 WHERE b = a; } } {A A 19} @@ -368,11 +368,11 @@ } {A a A A 19} do_test collate4-2.1.5 { count { SELECT * FROM collate4t2, collate4t1 WHERE b = a; } -} {A A 5} +} {A A 4} do_test collate4-2.1.6 { count { SELECT a FROM collate4t1 WHERE a IN (SELECT * FROM collate4t2); } } {a A 10} @@ -382,16 +382,16 @@ CREATE INDEX collate4i1 ON collate4t1(a); } count { SELECT a FROM collate4t1 WHERE a IN (SELECT * FROM collate4t2); } -} {a A 8} +} {a A 6} do_test collate4-2.1.8 { count { SELECT a FROM collate4t1 WHERE a IN ('z', 'a'); } -} {a A 7} +} {a A 5} do_test collate4-2.1.9 { execsql { DROP INDEX collate4i1; CREATE INDEX collate4i1 ON collate4t1(a COLLATE TEXT); } @@ -425,18 +425,18 @@ do_test collate4-2.2.1 { count { SELECT * FROM collate4t2 NATURAL JOIN collate4t1; } } {0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 63} -do_test collate4-2.2.1 { +do_test collate4-2.2.1b { execsql { CREATE INDEX collate4i1 ON collate4t1(a, b, c); } count { SELECT * FROM collate4t2 NATURAL JOIN collate4t1; } -} {0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 45} +} {0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 29} do_test collate4-2.2.2 { execsql { DROP INDEX collate4i1; CREATE INDEX collate4i1 ON collate4t1(a, b, c COLLATE text); } Index: test/where.test ================================================================== --- test/where.test +++ test/where.test @@ -9,11 +9,11 @@ # #*********************************************************************** # This file implements regression tests for SQLite library. The # focus of this file is testing the use of indices in WHERE clases. # -# $Id: where.test,v 1.25 2004/12/18 18:40:28 drh Exp $ +# $Id: where.test,v 1.26 2004/12/19 00:11:36 drh Exp $ set testdir [file dirname $argv0] source $testdir/tester.tcl # Build some test data @@ -149,39 +149,39 @@ } {10 99} do_test where-1.30 { count {SELECT w FROM t1 WHERE w>97} -} {98 99 100 6} +} {98 99 100 3} do_test where-1.31 { count {SELECT w FROM t1 WHERE w>=97} -} {97 98 99 100 8} +} {97 98 99 100 4} do_test where-1.33 { count {SELECT w FROM t1 WHERE w==97} -} {97 3} +} {97 2} do_test where-1.34 { count {SELECT w FROM t1 WHERE w+1==98} } {97 99} do_test where-1.35 { count {SELECT w FROM t1 WHERE w<3} -} {1 2 4} +} {1 2 2} do_test where-1.36 { count {SELECT w FROM t1 WHERE w<=3} -} {1 2 3 6} +} {1 2 3 3} do_test where-1.37 { count {SELECT w FROM t1 WHERE w+1<=4 ORDER BY w} -} {1 2 3 199} +} {1 2 3 99} do_test where-1.38 { count {SELECT (w) FROM t1 WHERE (w)>(97)} -} {98 99 100 6} +} {98 99 100 3} do_test where-1.39 { count {SELECT (w) FROM t1 WHERE (w)>=(97)} -} {97 98 99 100 8} +} {97 98 99 100 4} do_test where-1.40 { count {SELECT (w) FROM t1 WHERE (w)==(97)} -} {97 3} +} {97 2} do_test where-1.41 { count {SELECT (w) FROM t1 WHERE ((w)+(1))==(98)} } {97 99} @@ -235,23 +235,23 @@ do_test where-3.1 { count { SELECT A.w, B.p, C.w FROM t1 as A, t2 as B, t1 as C WHERE C.w=101-B.p AND B.r=10202-A.y AND A.w=11 } -} {11 90 11 9} +} {11 90 11 8} do_test where-3.2 { count { SELECT A.w, B.p, C.w FROM t1 as A, t2 as B, t1 as C WHERE C.w=101-B.p AND B.r=10202-A.y AND A.w=12 } -} {12 89 12 9} +} {12 89 12 8} do_test where-3.3 { count { SELECT A.w, B.p, C.w FROM t1 as A, t2 as B, t1 as C WHERE A.w=15 AND B.p=C.w AND B.r=10202-A.y } -} {15 86 86 9} +} {15 86 86 8} # Test to see that the special case of a constant WHERE clause is # handled. # do_test where-4.1 { @@ -415,11 +415,11 @@ } {1 100 4 2 99 9 3 98 16 sort} do_test where-6.8 { cksort { SELECT * FROM t3 WHERE a IN (3,5,7,1,9,4,2) ORDER BY a LIMIT 3 } -} {1 100 4 2 99 9 3 98 16 nosort} +} {1 100 4 2 99 9 3 98 16 sort} do_test where-6.9.1 { cksort { SELECT * FROM t3 WHERE a=1 AND c>0 ORDER BY a LIMIT 3 } } {1 100 4 nosort} @@ -455,16 +455,16 @@ } {1 100 4 sort} do_test where-6.9.8 { cksort { SELECT * FROM t3 WHERE a=1 AND c>0 ORDER BY a DESC, c ASC LIMIT 3 } -} {1 100 4 sort} +} {1 100 4 nosort} do_test where-6.9.9 { cksort { SELECT * FROM t3 WHERE a=1 AND c>0 ORDER BY a ASC, c DESC LIMIT 3 } -} {1 100 4 sort} +} {1 100 4 nosort} do_test where-6.10 { cksort { SELECT * FROM t3 WHERE a=1 AND c>0 ORDER BY a LIMIT 3 } } {1 100 4 nosort}