Index: src/select.c ================================================================== --- src/select.c +++ src/select.c @@ -2868,14 +2868,15 @@ ** row of results comes from selectA or selectB. Also add explicit ** collations to the ORDER BY clause terms so that when the subqueries ** to the right and the left are evaluated, they use the correct ** collation. */ - aPermute = sqlite3DbMallocRaw(db, sizeof(int)*nOrderBy); + aPermute = sqlite3DbMallocRaw(db, sizeof(int)*(nOrderBy + 1)); if( aPermute ){ struct ExprList_item *pItem; - for(i=0, pItem=pOrderBy->a; ia; i<=nOrderBy; i++, pItem++){ assert( pItem->u.x.iOrderByCol>0 ); assert( pItem->u.x.iOrderByCol<=p->pEList->nExpr ); aPermute[i] = pItem->u.x.iOrderByCol - 1; } pKeyMerge = multiSelectOrderByKeyInfo(pParse, p, 1); Index: src/vdbe.c ================================================================== --- src/vdbe.c +++ src/vdbe.c @@ -2065,15 +2065,18 @@ ** of integers in P4. ** ** The permutation is only valid until the next OP_Compare that has ** the OPFLAG_PERMUTE bit set in P5. Typically the OP_Permutation should ** occur immediately prior to the OP_Compare. +** +** The first integer in the P4 integer array is the length of the array +** and does not become part of the permutation. */ case OP_Permutation: { assert( pOp->p4type==P4_INTARRAY ); assert( pOp->p4.ai ); - aPermute = pOp->p4.ai; + aPermute = pOp->p4.ai + 1; break; } /* Opcode: Compare P1 P2 P3 P4 P5 ** Synopsis: r[P1@P3] <-> r[P2@P3] @@ -2374,26 +2377,28 @@ u64 offset64; /* 64-bit offset */ u32 avail; /* Number of bytes of available data */ u32 t; /* A type code from the record header */ Mem *pReg; /* PseudoTable input register */ + pC = p->apCsr[pOp->p1]; p2 = pOp->p2; + + /* If the cursor cache is stale, bring it up-to-date */ + rc = sqlite3VdbeCursorMoveto(&pC, &p2); + assert( pOp->p3>0 && pOp->p3<=(p->nMem-p->nCursor) ); pDest = &aMem[pOp->p3]; memAboutToChange(p, pDest); assert( pOp->p1>=0 && pOp->p1nCursor ); - pC = p->apCsr[pOp->p1]; assert( pC!=0 ); assert( p2nField ); aOffset = pC->aOffset; assert( pC->eCurType!=CURTYPE_VTAB ); assert( pC->eCurType!=CURTYPE_PSEUDO || pC->nullRow ); assert( pC->eCurType!=CURTYPE_SORTER ); pCrsr = pC->uc.pCursor; - /* If the cursor cache is stale, bring it up-to-date */ - rc = sqlite3VdbeCursorMoveto(pC); if( rc ) goto abort_due_to_error; if( pC->cacheStatus!=p->cacheCtr ){ if( pC->nullRow ){ if( pC->eCurType==CURTYPE_PSEUDO ){ assert( pC->uc.pseudoTableReg>0 ); @@ -3844,19 +3849,26 @@ pOp++; /* Skip the OP_IdxLt or OP_IdxGT that follows */ } break; } -/* Opcode: Seek P1 P2 * * * +/* Opcode: Seek P1 P2 P3 P4 * ** Synopsis: intkey=r[P2] ** ** P1 is an open table cursor and P2 is a rowid integer. Arrange ** for P1 to move so that it points to the rowid given by P2. ** ** This is actually a deferred seek. Nothing actually happens until ** the cursor is used to read a record. That way, if no reads ** occur, no unnecessary I/O happens. +** +** P4 may contain an array of integers (type P4_INTARRAY) containing +** one entry for each column in the table P1 is open on. If so, then +** parameter P3 is a cursor open on a database index. If array entry +** a[i] is non-zero, then reading column (a[i]-1) from cursor P3 is +** equivalent to performing the deferred seek and then reading column i +** from P1. */ case OP_Seek: { /* in2 */ VdbeCursor *pC; assert( pOp->p1>=0 && pOp->p1nCursor ); @@ -3867,10 +3879,13 @@ assert( pC->isTable ); pC->nullRow = 0; pIn2 = &aMem[pOp->p2]; pC->movetoTarget = sqlite3VdbeIntValue(pIn2); pC->deferredMoveto = 1; + assert( pOp->p4type==P4_INTARRAY || pOp->p4.ai==0 ); + pC->aAltMap = pOp->p4.ai; + pC->pAltCursor = p->apCsr[pOp->p3]; break; } /* Opcode: Found P1 P2 P3 P4 * Index: src/vdbeInt.h ================================================================== --- src/vdbeInt.h +++ src/vdbeInt.h @@ -72,10 +72,11 @@ ** - On either an index or a table ** * A sorter ** * A virtual table ** * A one-row "pseudotable" stored in a single register */ +typedef struct VdbeCursor VdbeCursor; struct VdbeCursor { u8 eCurType; /* One of the CURTYPE_* values above */ i8 iDb; /* Index of cursor database in db->aDb[] (or -1) */ u8 nullRow; /* True if pointing to a row with no data */ u8 deferredMoveto; /* A call to sqlite3BtreeMoveto() is needed */ @@ -98,10 +99,12 @@ Btree *pBt; /* Separate file holding temporary table */ KeyInfo *pKeyInfo; /* Info about index keys needed by index cursors */ int seekResult; /* Result of previous sqlite3BtreeMoveto() */ i64 seqCount; /* Sequence counter */ i64 movetoTarget; /* Argument to the deferred sqlite3BtreeMoveto() */ + VdbeCursor *pAltCursor; /* Associated index cursor from which to read */ + int *aAltMap; /* Mapping from table to index column numbers */ #ifdef SQLITE_ENABLE_COLUMN_USED_MASK u64 maskUsed; /* Mask of columns used by this cursor */ #endif /* Cached information about the header for the data record that the @@ -122,11 +125,10 @@ u32 aType[1]; /* Type values for all entries in the record */ /* 2*nField extra array elements allocated for aType[], beyond the one ** static element declared in the structure. nField total array slots for ** aType[] and nField+1 array slots for aOffset[] */ }; -typedef struct VdbeCursor VdbeCursor; /* ** When a sub-program is executed (OP_Program), a structure of this type ** is allocated to store the current value of the program counter, as ** well as the current memory cell array and various other frame specific @@ -421,11 +423,11 @@ ** Function prototypes */ void sqlite3VdbeError(Vdbe*, const char *, ...); void sqlite3VdbeFreeCursor(Vdbe *, VdbeCursor*); void sqliteVdbePopStack(Vdbe*,int); -int sqlite3VdbeCursorMoveto(VdbeCursor*); +int sqlite3VdbeCursorMoveto(VdbeCursor**, int*); int sqlite3VdbeCursorRestore(VdbeCursor*); #if defined(SQLITE_DEBUG) || defined(VDBE_PROFILE) void sqlite3VdbePrintOp(FILE*, int, Op*); #endif u32 sqlite3VdbeSerialTypeLen(u32); Index: src/vdbeaux.c ================================================================== --- src/vdbeaux.c +++ src/vdbeaux.c @@ -1286,11 +1286,25 @@ sqlite3_snprintf(nTemp, zTemp, "vtab:%p", pVtab); break; } #endif case P4_INTARRAY: { - sqlite3_snprintf(nTemp, zTemp, "intarray"); + int i, j; + int *ai = pOp->p4.ai; + int n = ai[0]; /* The first element of an INTARRAY is always the + ** count of the number of elements to follow */ + zTemp[0] = '['; + for(i=j=1; i1 ) zTemp[j++] = ','; + sqlite3_snprintf(nTemp-j, zTemp+j, "%d", ai[i]); + j += sqlite3Strlen30(zTemp+j); + } + if( ieCurType==CURTYPE_BTREE ){ if( p->deferredMoveto ){ + int iMap; + if( p->aAltMap && (iMap = p->aAltMap[1+*piCol])>0 ){ + *pp = p->pAltCursor; + *piCol = iMap - 1; + return SQLITE_OK; + } return handleDeferredMoveto(p); } if( sqlite3BtreeCursorHasMoved(p->uc.pCursor) ){ return handleMovedCursor(p); } Index: src/wherecode.c ================================================================== --- src/wherecode.c +++ src/wherecode.c @@ -743,10 +743,59 @@ } } #else # define codeCursorHint(A,B,C) /* No-op */ #endif /* SQLITE_ENABLE_CURSOR_HINTS */ + +/* +** Cursor iCur is open on an intkey b-tree (a table). Register iRowid contains +** a rowid value just read from cursor iIdxCur, open on index pIdx. This +** function generates code to do a deferred seek of cursor iCur to the +** rowid stored in register iRowid. +** +** Normally, this is just: +** +** OP_Seek $iCur $iRowid +** +** However, if the scan currently being coded is a branch of an OR-loop and +** the statement currently being coded is a SELECT, then P3 of the OP_Seek +** is set to iIdxCur and P4 is set to point to an array of integers +** containing one entry for each column of the table cursor iCur is open +** on. For each table column, if the column is the i'th column of the +** index, then the corresponding array entry is set to (i+1). If the column +** does not appear in the index at all, the array entry is set to 0. +*/ +static void codeDeferredSeek( + WhereInfo *pWInfo, /* Where clause context */ + Index *pIdx, /* Index scan is using */ + int iCur, /* Cursor for IPK b-tree */ + int iRowid, /* Register containing rowid to seek to */ + int iIdxCur /* Index cursor */ +){ + Parse *pParse = pWInfo->pParse; /* Parse context */ + Vdbe *v = pParse->pVdbe; /* Vdbe to generate code within */ + + assert( iIdxCur>0 ); + assert( pIdx->aiColumn[pIdx->nColumn-1]==-1 ); + + sqlite3VdbeAddOp3(v, OP_Seek, iCur, iRowid, iIdxCur); + if( (pWInfo->wctrlFlags & WHERE_FORCE_TABLE) + && sqlite3ParseToplevel(pParse)->writeMask==0 + ){ + int i; + Table *pTab = pIdx->pTable; + int *ai = (int*)sqlite3DbMallocZero(pParse->db, sizeof(int)*(pTab->nCol+1)); + if( ai ){ + ai[0] = pTab->nCol; + for(i=0; inColumn-1; i++){ + assert( pIdx->aiColumn[i]nCol ); + if( pIdx->aiColumn[i]>=0 ) ai[pIdx->aiColumn[i]+1] = i+1; + } + sqlite3VdbeChangeP4(v, -1, (char*)ai, P4_INTARRAY); + } + } +} /* ** Generate code for the start of the iLevel-th loop in the WHERE clause ** implementation described by pWInfo. */ @@ -1230,11 +1279,11 @@ sqlite3ExprCacheStore(pParse, iCur, -1, iRowidReg); if( pWInfo->eOnePass!=ONEPASS_OFF ){ sqlite3VdbeAddOp3(v, OP_NotExists, iCur, 0, iRowidReg); VdbeCoverage(v); }else{ - sqlite3VdbeAddOp2(v, OP_Seek, iCur, iRowidReg); /* Deferred seek */ + codeDeferredSeek(pWInfo, pIdx, iCur, iRowidReg, iIdxCur); } }else if( iCur!=iIdxCur ){ Index *pPk = sqlite3PrimaryKeyIndex(pIdx->pTable); iRowidReg = sqlite3GetTempRange(pParse, pPk->nKeyCol); for(j=0; jnKeyCol; j++){ Index: test/whereD.test ================================================================== --- test/whereD.test +++ test/whereD.test @@ -154,11 +154,11 @@ OR (a=1 AND b=(SELECT y FROM t4 WHERE x='a')) } {2 two 1 one search 8} do_searchcount_test 3.5.1 { SELECT a, b FROM t3 WHERE (a=1 AND b='one') OR rowid=4 -} {1 one 2 two search 3} +} {1 one 2 two search 2} do_searchcount_test 3.5.2 { SELECT a, c FROM t3 WHERE (a=1 AND b='one') OR rowid=4 } {1 i 2 ii search 3} # Ticket [d02e1406a58ea02d] (2012-10-04) @@ -269,7 +269,72 @@ c8=1 or c9=1 or c10=1 or c11=1 or c12=1 or c13=1 or c14=1 or c15=1 or c16=1 or c17=1; } {1 {} {} {} {} {} {} {} {} {} {} {} {} {} {} 1 {} {}} +#------------------------------------------------------------------------- +do_execsql_test 6.1 { + CREATE TABLE x1(a, b, c, d, e); + CREATE INDEX x1a ON x1(a); + CREATE INDEX x1bc ON x1(b, c); + CREATE INDEX x1cd ON x1(c, d); + + INSERT INTO x1 VALUES(1, 2, 3, 4, 'A'); + INSERT INTO x1 VALUES(5, 6, 7, 8, 'B'); + INSERT INTO x1 VALUES(9, 10, 11, 12, 'C'); + INSERT INTO x1 VALUES(13, 14, 15, 16, 'D'); +} + +do_searchcount_test 6.2.1 { + SELECT e FROM x1 WHERE b=2 OR c=7; +} {A B search 6} +do_searchcount_test 6.2.2 { + SELECT c FROM x1 WHERE b=2 OR c=7; +} {3 7 search 4} + +do_searchcount_test 6.3.1 { + SELECT e FROM x1 WHERE a=1 OR b=10; +} {A C search 6} +do_searchcount_test 6.3.2 { + SELECT c FROM x1 WHERE a=1 OR b=10; +} {3 11 search 5} +do_searchcount_test 6.3.3 { + SELECT rowid FROM x1 WHERE a=1 OR b=10; +} {1 3 search 4} + +do_searchcount_test 6.4.1 { + SELECT a FROM x1 WHERE b BETWEEN 1 AND 4 OR c BETWEEN 8 AND 12 +} {1 9 search 6} +do_searchcount_test 6.4.2 { + SELECT b, c FROM x1 WHERE b BETWEEN 1 AND 4 OR c BETWEEN 8 AND 12 +} {2 3 10 11 search 5} +do_searchcount_test 6.4.3 { + SELECT rowid, c FROM x1 WHERE b BETWEEN 1 AND 4 OR c BETWEEN 8 AND 12 +} {1 3 3 11 search 4} + +do_searchcount_test 6.5.1 { + SELECT a FROM x1 WHERE rowid = 2 OR c=11 +} {5 9 search 3} +do_searchcount_test 6.5.2 { + SELECT d FROM x1 WHERE rowid = 2 OR c=11 +} {8 12 search 2} +do_searchcount_test 6.5.3 { + SELECT d FROM x1 WHERE c=11 OR rowid = 2 +} {12 8 search 2} +do_searchcount_test 6.5.4 { + SELECT a FROM x1 WHERE c=11 OR rowid = 2 +} {9 5 search 3} + +do_searchcount_test 6.6.1 { + SELECT rowid FROM x1 WHERE a=1 OR b=6 OR c=11 +} {1 2 3 search 6} +do_searchcount_test 6.6.2 { + SELECT c FROM x1 WHERE a=1 OR b=6 OR c=11 +} {3 7 11 search 7} +do_searchcount_test 6.6.3 { + SELECT c FROM x1 WHERE c=11 OR a=1 OR b=6 +} {11 3 7 search 7} +do_searchcount_test 6.6.4 { + SELECT c FROM x1 WHERE b=6 OR c=11 OR a=1 +} {7 11 3 search 7} finish_test