Index: src/where.c ================================================================== --- src/where.c +++ src/where.c @@ -3291,10 +3291,14 @@ ** ** Return 2 # Jump back to the Gosub ** ** B: ** + ** Added 2014-05-26: If the table is a WITHOUT ROWID table, then + ** use an ephermeral index instead of a RowSet to record the primary + ** keys of the rows we have already seen. + ** */ 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) */ @@ -3305,10 +3309,11 @@ int iLoopBody = sqlite3VdbeMakeLabel(v); /* Start of loop body */ int iRetInit; /* Address of regReturn init */ int untestedTerms = 0; /* Some terms not completely tested */ int ii; /* Loop counter */ Expr *pAndExpr = 0; /* An ".. AND (...)" expression */ + Table *pTab = pTabItem->pTab; pTerm = pLoop->aLTerm[0]; assert( pTerm!=0 ); assert( pTerm->eOperator & WO_OR ); assert( (pTerm->wtFlags & TERM_ORINFO)!=0 ); @@ -3337,11 +3342,12 @@ }else{ pOrTab = pWInfo->pTabList; } /* Initialize the rowset register to contain NULL. An SQL NULL is - ** equivalent to an empty rowset. + ** equivalent to an empty rowset. Or, create an ephermeral index + ** capable of holding primary keys in the case of a WITHOUT ROWID. ** ** Also initialize regReturn to contain the address of the instruction ** immediately following the OP_Return at the bottom of the loop. This ** is required in a few obscure LEFT JOIN cases where control jumps ** over the top of the loop into the body of it. In this case the @@ -3348,13 +3354,20 @@ ** correct response for the end-of-loop code (the OP_Return) is to ** fall through to the next instruction, just as an OP_Next does if ** called on an uninitialized cursor. */ if( (pWInfo->wctrlFlags & WHERE_DUPLICATES_OK)==0 ){ - regRowset = ++pParse->nMem; + if( HasRowid(pTab) ){ + regRowset = ++pParse->nMem; + sqlite3VdbeAddOp2(v, OP_Null, 0, regRowset); + }else{ + Index *pPk = sqlite3PrimaryKeyIndex(pTab); + regRowset = pParse->nTab++; + sqlite3VdbeAddOp2(v, OP_OpenEphemeral, regRowset, pPk->nKeyCol); + sqlite3VdbeSetP4KeyInfo(pParse, pPk); + } regRowid = ++pParse->nMem; - sqlite3VdbeAddOp2(v, OP_Null, 0, regRowset); } iRetInit = sqlite3VdbeAddOp2(v, OP_Integer, 0, regReturn); /* If the original WHERE clause is z of the form: (x1 OR x2 OR ...) AND y ** Then for every term xN, evaluate as the subexpression: xN AND z @@ -3391,10 +3404,11 @@ for(ii=0; iinTerm; ii++){ WhereTerm *pOrTerm = &pOrWc->a[ii]; if( pOrTerm->leftCursor==iCur || (pOrTerm->eOperator & WO_AND)!=0 ){ WhereInfo *pSubWInfo; /* Info for single OR-term scan */ Expr *pOrExpr = pOrTerm->pExpr; + int j1 = 0; /* Address of jump operation */ if( pAndExpr && !ExprHasProperty(pOrExpr, EP_FromJoin) ){ pAndExpr->pLeft = pOrExpr; pOrExpr = pAndExpr; } /* Loop through table entries that match term pOrTerm. */ @@ -3406,19 +3420,55 @@ WhereLoop *pSubLoop; explainOneScan( pParse, pOrTab, &pSubWInfo->a[0], iLevel, pLevel->iFrom, 0 ); if( (pWInfo->wctrlFlags & WHERE_DUPLICATES_OK)==0 ){ - int iSet = ((ii==pOrWc->nTerm-1)?-1:ii); int r; - r = sqlite3ExprCodeGetColumn(pParse, pTabItem->pTab, -1, iCur, - regRowid, 0); - sqlite3VdbeAddOp4Int(v, OP_RowSetTest, regRowset, - sqlite3VdbeCurrentAddr(v)+2, r, iSet); - VdbeCoverage(v); + int iSet = ((ii==pOrWc->nTerm-1)?-1:ii); + if( HasRowid(pTab) ){ + r = sqlite3ExprCodeGetColumn(pParse, pTab, -1, iCur, regRowid, 0); + j1 = sqlite3VdbeAddOp4Int(v, OP_RowSetTest, regRowset, 0, r,iSet); + VdbeCoverage(v); + }else{ + Index *pPk = sqlite3PrimaryKeyIndex(pTab); + int nPk = pPk->nKeyCol; + int iPk; + + /* Read the PK into an array of temp registers. */ + r = sqlite3GetTempRange(pParse, nPk); + for(iPk=0; iPkaiColumn[iPk]; + sqlite3ExprCodeGetColumn(pParse, pTab, iCol, iCur, r+iPk, 0); + } + + /* Check if the temp table already contains this key. If so, + ** the row has already been included in the result set and + ** can be ignored (by jumping past the Gosub below). Otherwise, + ** insert the key into the temp table and proceed with processing + ** the row. + ** + ** Use some of the same optimizations as OP_RowSetTest: If iSet + ** is zero, assume that the key cannot already be present in + ** the temp table. And if iSet is -1, assume that there is no + ** need to insert the key into the temp table, as it will never + ** be tested for. */ + if( iSet ){ + j1 = sqlite3VdbeAddOp4Int(v, OP_Found, regRowset, 0, r, nPk); + VdbeCoverage(v); + } + if( iSet>=0 ){ + sqlite3VdbeAddOp3(v, OP_MakeRecord, r, nPk, regRowid); + sqlite3VdbeAddOp3(v, OP_IdxInsert, regRowset, regRowid, 0); + if( iSet ) sqlite3VdbeChangeP5(v, OPFLAG_USESEEKRESULT); + } + + /* Release the array of temp registers */ + sqlite3ReleaseTempRange(pParse, r, nPk); + } } sqlite3VdbeAddOp2(v, OP_Gosub, regReturn, iLoopBody); + if( j1 ) sqlite3VdbeJumpHere(v, j1); /* The pSubWInfo->untestedTerms flag means that this OR term ** 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. @@ -4764,11 +4814,10 @@ if( pWInfo->wctrlFlags & WHERE_AND_ONLY ) return SQLITE_OK; pWCEnd = pWC->a + pWC->nTerm; pNew = pBuilder->pNew; memset(&sSum, 0, sizeof(sSum)); pItem = pWInfo->pTabList->a + pNew->iTab; - if( !HasRowid(pItem->pTab) ) return SQLITE_OK; iCur = pItem->iCursor; for(pTerm=pWC->a; pTermeOperator & WO_OR)!=0 && (pTerm->u.pOrInfo->indexable & pNew->maskSelf)!=0 ADDED test/whereI.test Index: test/whereI.test ================================================================== --- /dev/null +++ test/whereI.test @@ -0,0 +1,74 @@ +# 2014-03-31 +# +# 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. +# +#*********************************************************************** +# The focus of this file is testing the OR optimization on WITHOUT ROWID +# tables. +# + +set testdir [file dirname $argv0] +source $testdir/tester.tcl +set ::testprefix whereI + +do_execsql_test 1.0 { + CREATE TABLE t1(a, b, c, PRIMARY KEY(a)) WITHOUT ROWID; + INSERT INTO t1 VALUES(1, 'a', 'z'); + INSERT INTO t1 VALUES(2, 'b', 'y'); + INSERT INTO t1 VALUES(3, 'c', 'x'); + INSERT INTO t1 VALUES(4, 'd', 'w'); + CREATE INDEX i1 ON t1(b); + CREATE INDEX i2 ON t1(c); +} + +do_eqp_test 1.1 { + SELECT a FROM t1 WHERE b='b' OR c='x' +} { + 0 0 0 {SEARCH TABLE t1 USING INDEX i1 (b=?)} + 0 0 0 {SEARCH TABLE t1 USING INDEX i2 (c=?)} +} + +do_execsql_test 1.2 { + SELECT a FROM t1 WHERE b='b' OR c='x' +} {2 3} + +do_execsql_test 1.3 { + SELECT a FROM t1 WHERE b='a' OR c='z' +} {1} + +#---------------------------------------------------------------------- +# Try that again, this time with non integer PRIMARY KEY values. +# +do_execsql_test 2.0 { + CREATE TABLE t2(a, b, c, PRIMARY KEY(a)) WITHOUT ROWID; + INSERT INTO t2 VALUES('i', 'a', 'z'); + INSERT INTO t2 VALUES('ii', 'b', 'y'); + INSERT INTO t2 VALUES('iii', 'c', 'x'); + INSERT INTO t2 VALUES('iv', 'd', 'w'); + CREATE INDEX i3 ON t2(b); + CREATE INDEX i4 ON t2(c); +} + +do_eqp_test 2.1 { + SELECT a FROM t2 WHERE b='b' OR c='x' +} { + 0 0 0 {SEARCH TABLE t2 USING INDEX i3 (b=?)} + 0 0 0 {SEARCH TABLE t2 USING INDEX i4 (c=?)} +} + +do_execsql_test 2.2 { + SELECT a FROM t2 WHERE b='b' OR c='x' +} {ii iii} + +do_execsql_test 2.3 { + SELECT a FROM t2 WHERE b='a' OR c='z' +} {i} + +finish_test + +