Index: src/delete.c ================================================================== --- src/delete.c +++ src/delete.c @@ -369,11 +369,11 @@ /* Collect rowids of every row to be deleted. */ sqlite3VdbeAddOp2(v, OP_Null, 0, iRowSet); pWInfo = sqlite3WhereBegin( - pParse, pTabList, pWhere, 0, 0, WHERE_DUPLICATES_OK + pParse, pTabList, pWhere, 0, 0, WHERE_DUPLICATES_OK, 0 ); if( pWInfo==0 ) goto delete_from_cleanup; regRowid = sqlite3ExprCodeGetColumn(pParse, pTab, -1, iCur, iRowid, 0); sqlite3VdbeAddOp2(v, OP_RowSetAdd, iRowSet, regRowid); if( db->flags & SQLITE_CountRows ){ Index: src/fkey.c ================================================================== --- src/fkey.c +++ src/fkey.c @@ -558,11 +558,11 @@ /* Create VDBE to loop through the entries in pSrc that match the WHERE ** clause. If the constraint is not deferred, throw an exception for ** each row found. Otherwise, for deferred constraints, increment the ** deferred constraint counter by nIncr for each row selected. */ - pWInfo = sqlite3WhereBegin(pParse, pSrc, pWhere, 0, 0, 0); + pWInfo = sqlite3WhereBegin(pParse, pSrc, pWhere, 0, 0, 0, 0); if( nIncr>0 && pFKey->isDeferred==0 ){ sqlite3ParseToplevel(pParse)->mayAbort = 1; } sqlite3VdbeAddOp2(v, OP_FkCounter, pFKey->isDeferred, nIncr); if( pWInfo ){ Index: src/select.c ================================================================== --- src/select.c +++ src/select.c @@ -4022,11 +4022,11 @@ /* Aggregate and non-aggregate queries are handled differently */ if( !isAgg && pGroupBy==0 ){ ExprList *pDist = (isDistinct ? p->pEList : 0); /* Begin the database scan. */ - pWInfo = sqlite3WhereBegin(pParse, pTabList, pWhere, &pOrderBy, pDist, 0); + pWInfo = sqlite3WhereBegin(pParse, pTabList, pWhere, &pOrderBy, pDist, 0,0); if( pWInfo==0 ) goto select_end; if( pWInfo->nRowOut < p->nSelectRow ) p->nSelectRow = pWInfo->nRowOut; /* If sorting index that was created by a prior OP_OpenEphemeral ** instruction ended up not being needed, then change the OP_OpenEphemeral @@ -4195,11 +4195,11 @@ ** This might involve two separate loops with an OP_Sort in between, or ** it might be a single loop that uses an index to extract information ** in the right order to begin with. */ sqlite3VdbeAddOp2(v, OP_Gosub, regReset, addrReset); - pWInfo = sqlite3WhereBegin(pParse, pTabList, pWhere, &pGroupBy, 0, 0); + pWInfo = sqlite3WhereBegin(pParse, pTabList, pWhere, &pGroupBy, 0, 0, 0); if( pWInfo==0 ) goto select_end; if( pGroupBy==0 ){ /* The optimizer is able to deliver rows in group by order so ** we do not have to sort. The OP_OpenEphemeral table will be ** cancelled later because we still need to use the pKeyInfo @@ -4464,11 +4464,11 @@ /* This case runs if the aggregate has no GROUP BY clause. The ** processing is much simpler since there is only a single row ** of output. */ resetAccumulator(pParse, &sAggInfo); - pWInfo = sqlite3WhereBegin(pParse, pTabList, pWhere, &pMinMax, 0, flag); + pWInfo = sqlite3WhereBegin(pParse, pTabList, pWhere, &pMinMax,0,flag,0); if( pWInfo==0 ){ sqlite3ExprListDelete(db, pDel); goto select_end; } updateAccumulator(pParse, &sAggInfo); Index: src/sqliteInt.h ================================================================== --- src/sqliteInt.h +++ src/sqliteInt.h @@ -1945,10 +1945,11 @@ struct InLoop { int iCur; /* The VDBE cursor used by this IN operator */ int addrInTop; /* Top of the IN loop */ } *aInLoop; /* Information about each nested IN operator */ } in; /* Used when plan.wsFlags&WHERE_IN_ABLE */ + Index *pCovidx; /* Possible covering index for WHERE_MULTI_OR */ } u; /* The following field is really not part of the current level. But ** we need a place to cache virtual table index information for each ** virtual table in the FROM clause and the WhereLevel structure is @@ -2804,11 +2805,12 @@ #if defined(SQLITE_ENABLE_UPDATE_DELETE_LIMIT) && !defined(SQLITE_OMIT_SUBQUERY) Expr *sqlite3LimitWhere(Parse *, SrcList *, Expr *, ExprList *, Expr *, Expr *, char *); #endif void sqlite3DeleteFrom(Parse*, SrcList*, Expr*); void sqlite3Update(Parse*, SrcList*, ExprList*, Expr*, int); -WhereInfo *sqlite3WhereBegin(Parse*, SrcList*, Expr*, ExprList**,ExprList*,u16); +WhereInfo *sqlite3WhereBegin( + Parse*,SrcList*,Expr*,ExprList**,ExprList*,u16,int); void sqlite3WhereEnd(WhereInfo*); int sqlite3ExprCodeGetColumn(Parse*, Table*, int, int, int, u8); void sqlite3ExprCodeGetColumnOfTable(Vdbe*, Table*, int, int, int); void sqlite3ExprCodeMove(Parse*, int, int, int); void sqlite3ExprCodeCopy(Parse*, int, int, int); Index: src/update.c ================================================================== --- src/update.c +++ src/update.c @@ -311,11 +311,11 @@ /* Begin the database scan */ sqlite3VdbeAddOp3(v, OP_Null, 0, regRowSet, regOldRowid); pWInfo = sqlite3WhereBegin( - pParse, pTabList, pWhere, 0, 0, WHERE_ONEPASS_DESIRED + pParse, pTabList, pWhere, 0, 0, WHERE_ONEPASS_DESIRED, 0 ); if( pWInfo==0 ) goto update_cleanup; okOnePass = pWInfo->okOnePass; /* Remember the rowid of every item to be updated. Index: src/where.c ================================================================== --- src/where.c +++ src/where.c @@ -3620,11 +3620,11 @@ assert( pIdx->nColumn>=nEq ); for(j=0; jaiColumn[j]; pTerm = findTerm(pWC, iCur, k, notReady, pLevel->plan.wsFlags, pIdx); - if( NEVER(pTerm==0) ) break; + if( pTerm==0 ) break; /* The following true for indices with redundant columns. ** Ex: CREATE INDEX i1 ON t1(a,b,a); SELECT * FROM t1 WHERE a=0 AND b=0; */ testcase( (pTerm->wtFlags & TERM_CODED)!=0 ); testcase( pTerm->wtFlags & TERM_VIRTUAL ); /* EV: R-30575-11662 */ r1 = codeEqualityTerm(pParse, pTerm, pLevel, regBase+j); @@ -4295,10 +4295,12 @@ ** B: ** */ WhereClause *pOrWc; /* The OR-clause broken out into subterms */ SrcList *pOrTab; /* Shortened table list or OR-clause generation */ + Index *pCov = 0; /* Potential covering index (or NULL) */ + int iCovCur = pParse->nTab++; /* Cursor used for index scans (if any) */ int regReturn = ++pParse->nMem; /* Register used with OP_Gosub */ int regRowset = 0; /* Register for RowSet object */ int regRowid = 0; /* Register holding rowid */ int iLoopBody = sqlite3VdbeMakeLabel(v); /* Start of loop body */ @@ -4313,11 +4315,11 @@ assert( (pTerm->wtFlags & TERM_ORINFO)!=0 ); pOrWc = &pTerm->u.pOrInfo->wc; pLevel->op = OP_Return; pLevel->p1 = regReturn; - /* Set up a new SrcList ni pOrTab containing the table being scanned + /* Set up a new SrcList in pOrTab containing the table being scanned ** by this loop in the a[0] slot and all notReady tables in a[1..] slots. ** This becomes the SrcList in the recursive call to sqlite3WhereBegin(). */ if( pWInfo->nLevel>1 ){ int nNotReady; /* The number of notReady tables */ @@ -4390,12 +4392,14 @@ pOrExpr = pAndExpr; } /* Loop through table entries that match term pOrTerm. */ pSubWInfo = sqlite3WhereBegin(pParse, pOrTab, pOrExpr, 0, 0, WHERE_OMIT_OPEN_CLOSE | WHERE_AND_ONLY | - WHERE_FORCE_TABLE | WHERE_ONETABLE_ONLY); + WHERE_FORCE_TABLE | WHERE_ONETABLE_ONLY, iCovCur); + assert( pSubWInfo || pParse->nErr || pParse->db->mallocFailed ); if( pSubWInfo ){ + WhereLevel *pLvl; explainOneScan( pParse, pOrTab, &pSubWInfo->a[0], iLevel, pLevel->iFrom, 0 ); if( (wctrlFlags & WHERE_DUPLICATES_OK)==0 ){ int iSet = ((ii==pOrWc->nTerm-1)?-1:ii); @@ -4411,16 +4415,41 @@ ** contained one or more AND term from a notReady table. The ** terms from the notReady table could not be tested and will ** need to be tested later. */ if( pSubWInfo->untestedTerms ) untestedTerms = 1; + + /* If all of the OR-connected terms are optimized using the same + ** index, and the index is opened using the same cursor number + ** by each call to sqlite3WhereBegin() made by this loop, it may + ** be possible to use that index as a covering index. + ** + ** If the call to sqlite3WhereBegin() above resulted in a scan that + ** uses an index, and this is either the first OR-connected term + ** processed or the index is the same as that used by all previous + ** terms, set pCov to the candidate covering index. Otherwise, set + ** pCov to NULL to indicate that no candidate covering index will + ** be available. + */ + pLvl = &pSubWInfo->a[0]; + if( (pLvl->plan.wsFlags & WHERE_INDEXED)!=0 + && (pLvl->plan.wsFlags & WHERE_TEMP_INDEX)==0 + && (ii==0 || pLvl->plan.u.pIdx==pCov) + ){ + assert( pLvl->iIdxCur==iCovCur ); + pCov = pLvl->plan.u.pIdx; + }else{ + pCov = 0; + } /* Finish the loop through table entries that match term pOrTerm. */ sqlite3WhereEnd(pSubWInfo); } } } + pLevel->u.pCovidx = pCov; + pLevel->iIdxCur = iCovCur; if( pAndExpr ){ pAndExpr->pLeft = 0; sqlite3ExprDelete(pParse->db, pAndExpr); } sqlite3VdbeChangeP1(v, iRetInit, sqlite3VdbeCurrentAddr(v)); @@ -4634,11 +4663,12 @@ Parse *pParse, /* The parser context */ SrcList *pTabList, /* A list of all tables to be scanned */ Expr *pWhere, /* The WHERE clause */ ExprList **ppOrderBy, /* An ORDER BY clause, or NULL */ ExprList *pDistinct, /* The select-list for DISTINCT queries - or NULL */ - u16 wctrlFlags /* One of the WHERE_* flags defined in sqliteInt.h */ + u16 wctrlFlags, /* One of the WHERE_* flags defined in sqliteInt.h */ + int iIdxCur /* If WHERE_ONETABLE_ONLY is set, index cursor number */ ){ int i; /* Loop counter */ int nByteWInfo; /* Num. bytes allocated for WhereInfo struct */ int nTabList; /* Number of elements in pTabList */ WhereInfo *pWInfo; /* Will become the return value of this function */ @@ -4954,11 +4984,17 @@ andFlags &= bestPlan.plan.wsFlags; pLevel->plan = bestPlan.plan; testcase( bestPlan.plan.wsFlags & WHERE_INDEXED ); testcase( bestPlan.plan.wsFlags & WHERE_TEMP_INDEX ); if( bestPlan.plan.wsFlags & (WHERE_INDEXED|WHERE_TEMP_INDEX) ){ - pLevel->iIdxCur = pParse->nTab++; + if( (wctrlFlags & WHERE_ONETABLE_ONLY) + && (bestPlan.plan.wsFlags & WHERE_TEMP_INDEX)==0 + ){ + pLevel->iIdxCur = iIdxCur; + }else{ + pLevel->iIdxCur = pParse->nTab++; + } }else{ pLevel->iIdxCur = -1; } notReady &= ~getMask(pMaskSet, pTabList->a[bestJ].iCursor); pLevel->iFrom = (u8)bestJ; @@ -5206,10 +5242,11 @@ /* Close all of the cursors that were opened by sqlite3WhereBegin. */ assert( pWInfo->nLevel==1 || pWInfo->nLevel==pTabList->nSrc ); for(i=0, pLevel=pWInfo->a; inLevel; i++, pLevel++){ + Index *pIdx = 0; struct SrcList_item *pTabItem = &pTabList->a[pLevel->iFrom]; Table *pTab = pTabItem->pTab; assert( pTab!=0 ); if( (pTab->tabFlags & TF_Ephemeral)==0 && pTab->pSelect==0 @@ -5235,16 +5272,19 @@ ** 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->plan.wsFlags & WHERE_INDEXED)!=0 && !db->mallocFailed){ + if( pLevel->plan.wsFlags & WHERE_INDEXED ){ + pIdx = pLevel->plan.u.pIdx; + }else if( pLevel->plan.wsFlags & WHERE_MULTI_OR ){ + pIdx = pLevel->u.pCovidx; + } + if( pIdx && !db->mallocFailed){ int k, j, last; VdbeOp *pOp; - Index *pIdx = pLevel->plan.u.pIdx; - assert( pIdx!=0 ); pOp = sqlite3VdbeGetOp(v, pWInfo->iTop); last = sqlite3VdbeCurrentAddr(v); for(k=pWInfo->iTop; kp1!=pLevel->iTabCur ) continue; if( pOp->opcode==OP_Column ){ ADDED test/whereD.test Index: test/whereD.test ================================================================== --- /dev/null +++ test/whereD.test @@ -0,0 +1,164 @@ +# 2012 August 24 +# +# The author disclaims copyright to this source code. In place of +# a legal notice, here is a blessing: +# +# May you do good and not evil. +# May you find forgiveness for yourself and forgive others. +# May you share freely, never taking more than you give. +# +#*********************************************************************** +# This file implements regression tests for SQLite library. The +# focus of this file is testing that an index may be used as a covering +# index when there are OR expressions in the WHERE clause. +# + + +set testdir [file dirname $argv0] +source $testdir/tester.tcl +set ::testprefix whereD + +do_execsql_test 1.1 { + CREATE TABLE t(i,j,k,m,n); + CREATE INDEX ijk ON t(i,j,k); + CREATE INDEX jmn ON t(j,m,n); + + INSERT INTO t VALUES(3, 3, 'three', 3, 'tres'); + INSERT INTO t VALUES(2, 2, 'two', 2, 'dos'); + INSERT INTO t VALUES(1, 1, 'one', 1, 'uno'); + INSERT INTO t VALUES(4, 4, 'four', 4, 'cuatro'); +} + +do_execsql_test 1.2 { + SELECT k FROM t WHERE (i=1 AND j=1) OR (i=2 AND j=2); +} {one two} +do_execsql_test 1.3 { + SELECT k FROM t WHERE (i=1 AND j=1) OR (+i=2 AND j=2); +} {one two} +do_execsql_test 1.4 { + SELECT n FROM t WHERE (i=1 AND j=1) OR (i=2 AND j=2); +} {uno dos} +do_execsql_test 1.5 { + SELECT k, n FROM t WHERE (i=1 AND j=1) OR (i=2 AND j=2); +} {one uno two dos} +do_execsql_test 1.6 { + SELECT k FROM t WHERE (i=1 AND j=1) OR (i=2 AND j=2) OR (i=3 AND j=3); +} {one two three} +do_execsql_test 1.7 { + SELECT n FROM t WHERE (i=1 AND j=1) OR (i=2 AND j=2) OR (i=3 AND j=3); +} {uno dos tres} +do_execsql_test 1.8 { + SELECT k FROM t WHERE (i=1 AND j=1) OR (j=2 AND m=2); +} {one two} +do_execsql_test 1.9 { + SELECT k FROM t WHERE (i=1 AND j=1) OR (i=2 AND j=2) OR (j=3 AND m=3); +} {one two three} +do_execsql_test 1.10 { + SELECT n FROM t WHERE (i=1 AND j=1) OR (i=2 AND j=2) OR (j=3 AND m=3); +} {uno dos tres} +do_execsql_test 1.11 { + SELECT k FROM t WHERE (i=1 AND j=1) OR (j=2 AND m=2) OR (i=3 AND j=3); +} {one two three} +do_execsql_test 1.12 { + SELECT n FROM t WHERE (i=1 AND j=1) OR (j=2 AND m=2) OR (i=3 AND j=3); +} {uno dos tres} +do_execsql_test 1.13 { + SELECT k FROM t WHERE (j=1 AND m=1) OR (i=2 AND j=2) OR (i=3 AND j=3); +} {one two three} +do_execsql_test 1.14 { + SELECT k FROM t WHERE (i=1 AND j=1) OR (j=2 AND i=2) OR (i=3 AND j=3); +} {one two three} +do_execsql_test 1.15 { + SELECT k FROM t WHERE (i=1 AND j=2) OR (i=2 AND j=1) OR (i=3 AND j=4); +} {} +do_execsql_test 1.16 { + SELECT k FROM t WHERE (i=1 AND (j=1 or j=2)) OR (i=3 AND j=3); +} {one three} + +do_execsql_test 2.0 { + CREATE TABLE t1(a,b,c,d); + CREATE INDEX t1b ON t1(b); + CREATE INDEX t1c ON t1(c); + CREATE INDEX t1d ON t1(d); + CREATE TABLE t2(x,y); + CREATE INDEX t2y ON t2(y); + + INSERT INTO t1 VALUES(1,2,3,4); + INSERT INTO t1 VALUES(5,6,7,8); + INSERT INTO t2 VALUES(1,2); + INSERT INTO t2 VALUES(2,7); + INSERT INTO t2 VALUES(3,4); +} {} +do_execsql_test 2.1 { + SELECT a, x FROM t1 JOIN t2 ON +y=d OR x=7 ORDER BY a, x; +} {1 3} +do_execsql_test 2.2 { + SELECT a, x FROM t1 JOIN t2 ON y=d OR x=7 ORDER BY a, x; +} {1 3} + + +# Similar to [do_execsql_test], except that two elements are appended +# to the result - the string "search" and the number of times test variable +# sqlite3_search_count is incremented by running the supplied SQL. e.g. +# +# do_searchcount_test 1.0 { SELECT * FROM t1 } {x y search 2} +# +proc do_searchcount_test {tn sql res} { + uplevel [subst -nocommands { + do_test $tn { + set ::sqlite_search_count 0 + concat [db eval {$sql}] search [set ::sqlite_search_count] + } [list $res] + }] +} + +do_execsql_test 3.0 { + CREATE TABLE t3(a, b, c); + CREATE UNIQUE INDEX i3 ON t3(a, b); + INSERT INTO t3 VALUES(1, 'one', 'i'); + INSERT INTO t3 VALUES(3, 'three', 'iii'); + INSERT INTO t3 VALUES(6, 'six', 'vi'); + INSERT INTO t3 VALUES(2, 'two', 'ii'); + INSERT INTO t3 VALUES(4, 'four', 'iv'); + INSERT INTO t3 VALUES(5, 'five', 'v'); + + CREATE TABLE t4(x PRIMARY KEY, y); + INSERT INTO t4 VALUES('a', 'one'); + INSERT INTO t4 VALUES('b', 'two'); +} + +do_searchcount_test 3.1 { + SELECT a, b FROM t3 WHERE (a=1 AND b='one') OR (a=2 AND b='two') +} {1 one 2 two search 2} + +do_searchcount_test 3.2 { + SELECT a, c FROM t3 WHERE (a=1 AND b='one') OR (a=2 AND b='two') +} {1 i 2 ii search 4} + +do_searchcount_test 3.4.1 { + SELECT y FROM t4 WHERE x='a' +} {one search 2} +do_searchcount_test 3.4.2 { + SELECT a, b FROM t3 WHERE + (a=1 AND b=(SELECT y FROM t4 WHERE x='a')) + OR (a=2 AND b='two') +} {1 one 2 two search 4} +do_searchcount_test 3.4.3 { + SELECT a, b FROM t3 WHERE + (a=2 AND b='two') + OR (a=1 AND b=(SELECT y FROM t4 WHERE x='a')) +} {2 two 1 one search 4} +do_searchcount_test 3.4.4 { + SELECT a, b FROM t3 WHERE + (a=2 AND b=(SELECT y FROM t4 WHERE x='b')) + OR (a=1 AND b=(SELECT y FROM t4 WHERE x='a')) +} {2 two 1 one search 6} + +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 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 2} + +finish_test