Index: src/sqliteInt.h ================================================================== --- src/sqliteInt.h +++ src/sqliteInt.h @@ -1977,14 +1977,14 @@ #define WHERE_ORDERBY_NORMAL 0x0000 /* No-op */ #define WHERE_ORDERBY_MIN 0x0001 /* ORDER BY processing for min() func */ #define WHERE_ORDERBY_MAX 0x0002 /* ORDER BY processing for max() func */ #define WHERE_ONEPASS_DESIRED 0x0004 /* Want to do one-pass UPDATE/DELETE */ #define WHERE_DUPLICATES_OK 0x0008 /* Ok to return a row more than once */ -#define WHERE_OMIT_OPEN 0x0010 /* Table cursors are already open */ -#define WHERE_OMIT_CLOSE 0x0020 /* Omit close of table & index cursors */ -#define WHERE_FORCE_TABLE 0x0040 /* Do not use an index-only search */ -#define WHERE_ONETABLE_ONLY 0x0080 /* Only code the 1st table in pTabList */ +#define WHERE_OMIT_OPEN_CLOSE 0x0010 /* Table cursors are already open */ +#define WHERE_FORCE_TABLE 0x0020 /* Do not use an index-only search */ +#define WHERE_ONETABLE_ONLY 0x0040 /* Only code the 1st table in pTabList */ +#define WHERE_AND_ONLY 0x0080 /* Don't use indices for OR terms */ /* ** The WHERE clause processing routine has two halves. The ** first part does the start of the WHERE loop and the second ** half does the tail of the WHERE loop. An instance of Index: src/where.c ================================================================== --- src/where.c +++ src/where.c @@ -125,16 +125,26 @@ #endif /* ** An instance of the following structure holds all information about a ** WHERE clause. Mostly this is a container for one or more WhereTerms. +** +** Explanation of pOuter: For a WHERE clause of the form +** +** a AND ((b AND c) OR (d AND e)) AND f +** +** There are separate WhereClause objects for the whole clause and for +** the subclauses "(b AND c)" and "(d AND e)". The pOuter field of the +** subclauses points to the WhereClause object for the whole clause. */ struct WhereClause { Parse *pParse; /* The parser context */ WhereMaskSet *pMaskSet; /* Mapping of table cursor numbers to bitmasks */ Bitmask vmask; /* Bitmask identifying virtual table cursors */ + WhereClause *pOuter; /* Outer conjunction */ u8 op; /* Split operator. TK_AND or TK_OR */ + u16 wctrlFlags; /* Might include WHERE_AND_ONLY */ int nTerm; /* Number of terms */ int nSlot; /* Number of entries in a[] */ WhereTerm *a; /* Each a[] describes a term of the WHERE cluase */ #if defined(SQLITE_SMALL_STACK) WhereTerm aStatic[1]; /* Initial static space for a[] */ @@ -259,18 +269,21 @@ ** Initialize a preallocated WhereClause structure. */ static void whereClauseInit( WhereClause *pWC, /* The WhereClause to be initialized */ Parse *pParse, /* The parsing context */ - WhereMaskSet *pMaskSet /* Mapping from table cursor numbers to bitmasks */ + WhereMaskSet *pMaskSet, /* Mapping from table cursor numbers to bitmasks */ + u16 wctrlFlags /* Might include WHERE_AND_ONLY */ ){ pWC->pParse = pParse; pWC->pMaskSet = pMaskSet; + pWC->pOuter = 0; pWC->nTerm = 0; pWC->nSlot = ArraySize(pWC->aStatic); pWC->a = pWC->aStatic; pWC->vmask = 0; + pWC->wctrlFlags = wctrlFlags; } /* Forward reference */ static void whereClauseClear(WhereClause*); @@ -582,40 +595,42 @@ ){ WhereTerm *pTerm; int k; assert( iCur>=0 ); op &= WO_ALL; - for(pTerm=pWC->a, k=pWC->nTerm; k; k--, pTerm++){ - if( pTerm->leftCursor==iCur - && (pTerm->prereqRight & notReady)==0 - && pTerm->u.leftColumn==iColumn - && (pTerm->eOperator & op)!=0 - ){ - if( pIdx && pTerm->eOperator!=WO_ISNULL ){ - Expr *pX = pTerm->pExpr; - CollSeq *pColl; - char idxaff; - int j; - Parse *pParse = pWC->pParse; - - idxaff = pIdx->pTable->aCol[iColumn].affinity; - if( !sqlite3IndexAffinityOk(pX, idxaff) ) continue; - - /* Figure out the collation sequence required from an index for - ** it to be useful for optimising expression pX. Store this - ** value in variable pColl. - */ - assert(pX->pLeft); - pColl = sqlite3BinaryCompareCollSeq(pParse, pX->pLeft, pX->pRight); - assert(pColl || pParse->nErr); - - for(j=0; pIdx->aiColumn[j]!=iColumn; j++){ - if( NEVER(j>=pIdx->nColumn) ) return 0; - } - if( pColl && sqlite3StrICmp(pColl->zName, pIdx->azColl[j]) ) continue; - } - return pTerm; + for(; pWC; pWC=pWC->pOuter){ + for(pTerm=pWC->a, k=pWC->nTerm; k; k--, pTerm++){ + if( pTerm->leftCursor==iCur + && (pTerm->prereqRight & notReady)==0 + && pTerm->u.leftColumn==iColumn + && (pTerm->eOperator & op)!=0 + ){ + if( pIdx && pTerm->eOperator!=WO_ISNULL ){ + Expr *pX = pTerm->pExpr; + CollSeq *pColl; + char idxaff; + int j; + Parse *pParse = pWC->pParse; + + idxaff = pIdx->pTable->aCol[iColumn].affinity; + if( !sqlite3IndexAffinityOk(pX, idxaff) ) continue; + + /* Figure out the collation sequence required from an index for + ** it to be useful for optimising expression pX. Store this + ** value in variable pColl. + */ + assert(pX->pLeft); + pColl = sqlite3BinaryCompareCollSeq(pParse, pX->pLeft, pX->pRight); + assert(pColl || pParse->nErr); + + for(j=0; pIdx->aiColumn[j]!=iColumn; j++){ + if( NEVER(j>=pIdx->nColumn) ) return 0; + } + if( pColl && sqlite3StrICmp(pColl->zName, pIdx->azColl[j]) ) continue; + } + return pTerm; + } } } return 0; } @@ -875,11 +890,11 @@ assert( pExpr->op==TK_OR ); pTerm->u.pOrInfo = pOrInfo = sqlite3DbMallocZero(db, sizeof(*pOrInfo)); if( pOrInfo==0 ) return; pTerm->wtFlags |= TERM_ORINFO; pOrWc = &pOrInfo->wc; - whereClauseInit(pOrWc, pWC->pParse, pMaskSet); + whereClauseInit(pOrWc, pWC->pParse, pMaskSet, pWC->wctrlFlags); whereSplit(pOrWc, pExpr, TK_OR); exprAnalyzeAll(pSrc, pOrWc); if( db->mallocFailed ) return; assert( pOrWc->nTerm>=2 ); @@ -902,13 +917,14 @@ Bitmask b = 0; pOrTerm->u.pAndInfo = pAndInfo; pOrTerm->wtFlags |= TERM_ANDINFO; pOrTerm->eOperator = WO_AND; pAndWC = &pAndInfo->wc; - whereClauseInit(pAndWC, pWC->pParse, pMaskSet); + whereClauseInit(pAndWC, pWC->pParse, pMaskSet, pWC->wctrlFlags); whereSplit(pAndWC, pOrTerm->pExpr, TK_AND); exprAnalyzeAll(pSrc, pAndWC); + pAndWC->pOuter = pWC; testcase( db->mallocFailed ); if( !db->mallocFailed ){ for(j=0, pAndTerm=pAndWC->a; jnTerm; j++, pAndTerm++){ assert( pAndTerm->pExpr ); if( allowedOp(pAndTerm->pExpr->op) ){ @@ -1799,14 +1815,17 @@ const int iCur = pSrc->iCursor; /* The cursor of the table to be accessed */ const Bitmask maskSrc = getMask(pWC->pMaskSet, iCur); /* Bitmask for pSrc */ WhereTerm * const pWCEnd = &pWC->a[pWC->nTerm]; /* End of pWC->a[] */ WhereTerm *pTerm; /* A single term of the WHERE clause */ - /* No OR-clause optimization allowed if the INDEXED BY or NOT INDEXED clauses - ** are used */ + /* The OR-clause optimization is disallowed if the INDEXED BY or + ** NOT INDEXED clauses are used or if the WHERE_AND_ONLY bit is set. */ if( pSrc->notIndexed || pSrc->pIndex!=0 ){ return; + } + if( pWC->wctrlFlags & WHERE_AND_ONLY ){ + return; } /* Search the WHERE clause terms for a usable WO_OR term. */ for(pTerm=pWC->a; pTermeOperator==WO_OR @@ -1831,10 +1850,11 @@ bestIndex(pParse, pAndWC, pSrc, notReady, notValid, 0, &sTermCost); }else if( pOrTerm->leftCursor==iCur ){ WhereClause tempWC; tempWC.pParse = pWC->pParse; tempWC.pMaskSet = pWC->pMaskSet; + tempWC.pOuter = pWC; tempWC.op = TK_AND; tempWC.a = pOrTerm; tempWC.nTerm = 1; bestIndex(pParse, &tempWC, pSrc, notReady, notValid, 0, &sTermCost); }else{ @@ -3010,10 +3030,11 @@ for(nEq=0; nEqnColumn; nEq++){ int j = pProbe->aiColumn[nEq]; pTerm = findTerm(pWC, iCur, j, notReady, eqTermMask, pIdx); if( pTerm==0 ) break; wsFlags |= (WHERE_COLUMN_EQ|WHERE_ROWID_EQ); + testcase( pTerm->pWC!=pWC ); if( pTerm->eOperator & WO_IN ){ Expr *pExpr = pTerm->pExpr; wsFlags |= WHERE_COLUMN_IN; if( ExprHasProperty(pExpr, EP_xIsSelect) ){ /* "x IN (SELECT ...)": Assume the SELECT returns 25 rows */ @@ -3041,15 +3062,17 @@ whereRangeScanEst(pParse, pProbe, nEq, pBtm, pTop, &rangeDiv); if( pTop ){ nBound = 1; wsFlags |= WHERE_TOP_LIMIT; used |= pTop->prereqRight; + testcase( pTop->pWC!=pWC ); } if( pBtm ){ nBound++; wsFlags |= WHERE_BTM_LIMIT; used |= pBtm->prereqRight; + testcase( pBtm->pWC!=pWC ); } wsFlags |= (WHERE_COLUMN_RANGE|WHERE_ROWID_RANGE); } }else if( pProbe->onError!=OE_None ){ testcase( wsFlags & WHERE_COLUMN_IN ); @@ -3767,11 +3790,12 @@ */ static Bitmask codeOneLoopStart( WhereInfo *pWInfo, /* Complete information about the WHERE clause */ int iLevel, /* Which level of pWInfo->a[] should be coded */ u16 wctrlFlags, /* One of the WHERE_* flags defined in sqliteInt.h */ - Bitmask notReady /* Which tables are currently available */ + Bitmask notReady, /* Which tables are currently available */ + Expr *pWhere /* Complete WHERE clause */ ){ int j, k; /* Loop counters */ int iCur; /* The VDBE cursor for the table */ int addrNxt; /* Where to jump to continue with the next IN case */ int omitTable; /* True if we use the index only */ @@ -4249,11 +4273,12 @@ int regRowset = 0; /* Register for RowSet object */ int regRowid = 0; /* Register holding rowid */ int iLoopBody = sqlite3VdbeMakeLabel(v); /* Start of loop body */ int iRetInit; /* Address of regReturn init */ int untestedTerms = 0; /* Some terms not completely tested */ - int ii; + int ii; /* Loop counter */ + Expr *pAndExpr = 0; /* An ".. AND (...)" expression */ pTerm = pLevel->plan.u.pTerm; assert( pTerm!=0 ); assert( pTerm->eOperator==WO_OR ); assert( (pTerm->wtFlags & TERM_ORINFO)!=0 ); @@ -4298,18 +4323,33 @@ regRowset = ++pParse->nMem; 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 + ** That way, terms in y that are factored into the disjunction will + ** be picked up by the recursive calls to sqlite3WhereBegin() below. + */ + if( pWC->nTerm>1 ){ + pAndExpr = sqlite3ExprAlloc(pParse->db, TK_AND, 0, 0); + pAndExpr->pRight = pWhere; + } for(ii=0; iinTerm; ii++){ WhereTerm *pOrTerm = &pOrWc->a[ii]; if( pOrTerm->leftCursor==iCur || pOrTerm->eOperator==WO_AND ){ WhereInfo *pSubWInfo; /* Info for single OR-term scan */ + Expr *pOrExpr = pOrTerm->pExpr; + if( pAndExpr ){ + pAndExpr->pLeft = pOrExpr; + pOrExpr = pAndExpr; + } /* Loop through table entries that match term pOrTerm. */ - pSubWInfo = sqlite3WhereBegin(pParse, pOrTab, pOrTerm->pExpr, 0, 0, - WHERE_OMIT_OPEN | WHERE_OMIT_CLOSE | + pSubWInfo = sqlite3WhereBegin(pParse, pOrTab, pOrExpr, 0, 0, + WHERE_OMIT_OPEN_CLOSE | WHERE_AND_ONLY | WHERE_FORCE_TABLE | WHERE_ONETABLE_ONLY); if( pSubWInfo ){ explainOneScan( pParse, pOrTab, &pSubWInfo->a[0], iLevel, pLevel->iFrom, 0 ); @@ -4333,10 +4373,11 @@ /* Finish the loop through table entries that match term pOrTerm. */ sqlite3WhereEnd(pSubWInfo); } } } + sqlite3DbFree(pParse->db, pAndExpr); sqlite3VdbeChangeP1(v, iRetInit, sqlite3VdbeCurrentAddr(v)); sqlite3VdbeAddOp2(v, OP_Goto, 0, pLevel->addrBrk); sqlite3VdbeResolveLabel(v, iLoopBody); if( pWInfo->nLevel>1 ) sqlite3StackFree(pParse->db, pOrTab); @@ -4614,11 +4655,11 @@ /* Split the WHERE clause into separate subexpressions where each ** subexpression is separated by an AND operator. */ initMaskSet(pMaskSet); - whereClauseInit(pWC, pParse, pMaskSet); + whereClauseInit(pWC, pParse, pMaskSet, wctrlFlags); sqlite3ExprCodeConstants(pParse, pWhere); whereSplit(pWC, pWhere, TK_AND); /* IMP: R-15842-53296 */ /* Special case: a WHERE clause that is constant. Evaluate the ** expression and either jump over all of the code or fall thru. @@ -4942,11 +4983,11 @@ int iCur = pTabItem->iCursor; sqlite3VdbeAddOp4(v, OP_VOpen, iCur, 0, 0, pVTab, P4_VTAB); }else #endif if( (pLevel->plan.wsFlags & WHERE_IDX_ONLY)==0 - && (wctrlFlags & WHERE_OMIT_OPEN)==0 ){ + && (wctrlFlags & WHERE_OMIT_OPEN_CLOSE)==0 ){ int op = pWInfo->okOnePass ? OP_OpenWrite : OP_OpenRead; sqlite3OpenTable(pParse, pTabItem->iCursor, iDb, pTab, op); testcase( pTab->nCol==BMS-1 ); testcase( pTab->nCol==BMS ); if( !pWInfo->okOnePass && pTab->nCola[i]; explainOneScan(pParse, pTabList, pLevel, i, pLevel->iFrom, wctrlFlags); - notReady = codeOneLoopStart(pWInfo, i, wctrlFlags, notReady); + notReady = codeOneLoopStart(pWInfo, i, wctrlFlags, notReady, pWhere); pWInfo->iContinue = pLevel->addrCont; } #ifdef SQLITE_TEST /* For testing and debugging use only */ /* Record in the query plan information about the current table @@ -5122,11 +5163,11 @@ struct SrcList_item *pTabItem = &pTabList->a[pLevel->iFrom]; Table *pTab = pTabItem->pTab; assert( pTab!=0 ); if( (pTab->tabFlags & TF_Ephemeral)==0 && pTab->pSelect==0 - && (pWInfo->wctrlFlags & WHERE_OMIT_CLOSE)==0 + && (pWInfo->wctrlFlags & WHERE_OMIT_OPEN_CLOSE)==0 ){ int ws = pLevel->plan.wsFlags; if( !pWInfo->okOnePass && (ws & WHERE_IDX_ONLY)==0 ){ sqlite3VdbeAddOp1(v, OP_Close, pTabItem->iCursor); } Index: test/where7.test ================================================================== --- test/where7.test +++ test/where7.test @@ -8,12 +8,10 @@ # 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 the multi-index OR clause optimizer. -# -# $Id: where7.test,v 1.9 2009/06/07 23:45:11 drh Exp $ set testdir [file dirname $argv0] source $testdir/tester.tcl ifcapable !or_opt { @@ -23339,12 +23337,12 @@ AND t302.c3 > 1287603136 AND (t301.c4 = 1407449685622784 OR t301.c8 = 1407424651264000) ORDER BY t302.c5 LIMIT 200; } { - 0 0 1 {SEARCH TABLE t301 USING COVERING INDEX t301_c4 (c4=?) (~10 rows)} + 0 0 1 {SEARCH TABLE t301 USING COVERING INDEX t301_c4 (c4=?) (~5 rows)} 0 0 1 {SEARCH TABLE t301 USING INTEGER PRIMARY KEY (rowid=?) (~1 rows)} 0 1 0 {SEARCH TABLE t302 USING INDEX t302_c8_c3 (c8=? AND c3>?) (~2 rows)} 0 0 0 {USE TEMP B-TREE FOR ORDER BY} } finish_test Index: test/where9.test ================================================================== --- test/where9.test +++ test/where9.test @@ -9,11 +9,10 @@ # #*********************************************************************** # This file implements regression tests for SQLite library. The # focus of this file is testing the multi-index OR clause optimizer. # -# $Id: where9.test,v 1.9 2009/06/05 17:09:12 drh Exp $ set testdir [file dirname $argv0] source $testdir/tester.tcl ifcapable !or_opt { @@ -363,21 +362,21 @@ SELECT t2.a FROM t1, t2 WHERE t1.a=80 AND ((t1.c=t2.c AND t1.d=t2.d) OR t1.f=t2.f) } { 0 0 0 {SEARCH TABLE t1 USING INTEGER PRIMARY KEY (rowid=?) (~1 rows)} 0 1 1 {SEARCH TABLE t2 USING INDEX t2d (d=?) (~2 rows)} - 0 1 1 {SEARCH TABLE t2 USING COVERING INDEX t2f (f=?) (~10 rows)} + 0 1 1 {SEARCH TABLE t2 USING COVERING INDEX t2f (f=?) (~5 rows)} } do_execsql_test where9-3.2 { EXPLAIN QUERY PLAN SELECT coalesce(t2.a,9999) FROM t1 LEFT JOIN t2 ON (t1.c+1=t2.c AND t1.d=t2.d) OR (t1.f||'x')=t2.f WHERE t1.a=80 } { 0 0 0 {SEARCH TABLE t1 USING INTEGER PRIMARY KEY (rowid=?) (~1 rows)} 0 1 1 {SEARCH TABLE t2 USING INDEX t2d (d=?) (~2 rows)} - 0 1 1 {SEARCH TABLE t2 USING COVERING INDEX t2f (f=?) (~10 rows)} + 0 1 1 {SEARCH TABLE t2 USING COVERING INDEX t2f (f=?) (~5 rows)} } } # Make sure that INDEXED BY and multi-index OR clauses play well with # one another. @@ -452,12 +451,12 @@ # the former is an equality test which is expected to return fewer rows. # do_execsql_test where9-5.1 { EXPLAIN QUERY PLAN SELECT a FROM t1 WHERE b>1000 AND (c=31031 OR d IS NULL) } { - 0 0 0 {SEARCH TABLE t1 USING INDEX t1c (c=?) (~10 rows)} - 0 0 0 {SEARCH TABLE t1 USING INDEX t1d (d=?) (~10 rows)} + 0 0 0 {SEARCH TABLE t1 USING INDEX t1c (c=?) (~2 rows)} + 0 0 0 {SEARCH TABLE t1 USING INDEX t1d (d=?) (~2 rows)} } # In contrast, b=1000 is preferred over any OR-clause. # do_execsql_test where9-5.2 { @@ -780,7 +779,82 @@ WHERE (b IS NULL AND c NOT NULL AND d NOT NULL) OR (b NOT NULL AND c IS NULL AND d NOT NULL) OR (b NOT NULL AND c NOT NULL AND d IS NULL) } } {1 {cannot use index: t1b}} + +############################################################################ +# Test cases where terms inside an OR series are combined with AND terms +# external to the OR clause. In other words, cases where +# +# x AND (y OR z) +# +# is able to use indices on x,y and x,z, or indices y,x and z,x. +# +do_test where9-7.0 { + execsql { + CREATE TABLE t5(a, b, c, d, e, f, g, x, y); + INSERT INTO t5 + SELECT a, b, c, e, d, f, g, + CASE WHEN (a&1)!=0 THEN 'y' ELSE 'n' END, + CASE WHEN (a&2)!=0 THEN 'y' ELSE 'n' END + FROM t1; + CREATE INDEX t5xb ON t5(x, b); + CREATE INDEX t5xc ON t5(x, c); + CREATE INDEX t5xd ON t5(x, d); + CREATE INDEX t5xe ON t5(x, e); + CREATE INDEX t5xf ON t5(x, f); + CREATE INDEX t5xg ON t5(x, g); + CREATE INDEX t5yb ON t5(y, b); + CREATE INDEX t5yc ON t5(y, c); + CREATE INDEX t5yd ON t5(y, d); + CREATE INDEX t5ye ON t5(y, e); + CREATE INDEX t5yf ON t5(y, f); + CREATE INDEX t5yg ON t5(y, g); + CREATE TABLE t6(a, b, c, e, d, f, g, x, y); + INSERT INTO t6 SELECT * FROM t5; + ANALYZE t5; + } +} {} +do_test where9-7.1.1 { + count_steps { + SELECT a FROM t5 WHERE x='y' AND (b=913 OR c=27027) ORDER BY a; + } +} {79 81 83 scan 0 sort 1} +do_test where9-7.1.2 { + execsql { + SELECT a FROM t6 WHERE x='y' AND (b=913 OR c=27027) ORDER BY a; + } +} {79 81 83} +do_test where9-7.1.3 { + count_steps { + SELECT a FROM t5 WHERE x='n' AND (b=913 OR c=27027) ORDER BY a; + } +} {80 scan 0 sort 1} +do_test where9-7.1.4 { + execsql { + SELECT a FROM t6 WHERE x='n' AND (b=913 OR c=27027) ORDER BY a; + } +} {80} +do_test where9-7.2.1 { + count_steps { + SELECT a FROM t5 WHERE (x='y' OR y='y') AND b=913 ORDER BY a; + } +} {83 scan 0 sort 1} +do_test where9-7.2.2 { + execsql { + SELECT a FROM t6 WHERE (x='y' OR y='y') AND b=913 ORDER BY a; + } +} {83} +do_test where9-7.3.1 { + count_steps { + SELECT a FROM t5 WHERE (x='y' OR y='y') AND c=27027 ORDER BY a; + } +} {79 81 scan 0 sort 1} +do_test where9-7.3.2 { + execsql { + SELECT a FROM t6 WHERE (x='y' OR y='y') AND c=27027 ORDER BY a; + } +} {79 81} + finish_test