Index: src/sqliteInt.h ================================================================== --- src/sqliteInt.h +++ src/sqliteInt.h @@ -1963,10 +1963,11 @@ struct { int nIn; /* Number of entries in aInLoop[] */ struct InLoop { int iCur; /* The VDBE cursor used by this IN operator */ int addrInTop; /* Top of the IN loop */ + u8 eEndLoopOp; /* IN Loop terminator. OP_Next or OP_Prev */ } *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; double rOptCost; /* "Optimal" cost for this level */ Index: src/where.c ================================================================== --- src/where.c +++ src/where.c @@ -138,11 +138,10 @@ ** 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[] */ @@ -315,11 +314,10 @@ 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*); @@ -915,11 +913,11 @@ ** (D) x=expr1 OR (y>11 AND y<22 AND z LIKE '*hello*') ** (E) (p.a=1 AND q.b=2 AND r.c=3) OR (p.x=4 AND q.y=5 AND r.z=6) ** ** CASE 1: ** -** If all subterms are of the form T.C=expr for some single column of C +** If all subterms are of the form T.C=expr for some single column of C and ** a single table T (as shown in example B above) then create a new virtual ** term that is an equivalent IN expression. In other words, if the term ** being analyzed is: ** ** x = expr1 OR expr2 = x OR x = expr3 @@ -1003,11 +1001,11 @@ /* ** Compute the set of tables that might satisfy cases 1 or 2. */ indexable = ~(Bitmask)0; - chngToIN = ~(pWC->vmask); + chngToIN = ~(Bitmask)0; for(i=pOrWc->nTerm-1, pOrTerm=pOrWc->a; i>=0 && indexable; i--, pOrTerm++){ if( (pOrTerm->eOperator & WO_SINGLE)==0 ){ WhereAndInfo *pAndInfo; assert( (pOrTerm->wtFlags & (TERM_ANDINFO|TERM_ORINFO))==0 ); chngToIN = 0; @@ -2270,12 +2268,13 @@ Table *pTab = pSrc->pTab; sqlite3_index_info *pIdxInfo; struct sqlite3_index_constraint *pIdxCons; struct sqlite3_index_constraint_usage *pUsage; WhereTerm *pTerm; - int i, j; + int i, j, k; int nOrderBy; + int sortOrder; /* Sort order for IN clauses */ int bAllowIN; /* Allow IN optimizations */ double rCost; /* Make sure wsFlags is initialized to some sane value. Otherwise, if the ** malloc in allocateIndexInfo() fails and this function returns leaving @@ -2370,22 +2369,31 @@ if( vtabBestIndex(pParse, pTab, pIdxInfo) ){ return; } + sortOrder = SQLITE_SO_ASC; pIdxCons = *(struct sqlite3_index_constraint**)&pIdxInfo->aConstraint; for(i=0; inConstraint; i++, pIdxCons++){ if( pUsage[i].argvIndex>0 ){ j = pIdxCons->iTermOffset; pTerm = &pWC->a[j]; p->cost.used |= pTerm->prereqRight; - if( (pTerm->eOperator & WO_IN)!=0 && pUsage[i].omit==0 ){ - /* Do not attempt to use an IN constraint if the virtual table - ** says that the equivalent EQ constraint cannot be safely omitted. - ** If we do attempt to use such a constraint, some rows might be - ** repeated in the output. */ - break; + if( (pTerm->eOperator & WO_IN)!=0 ){ + if( pUsage[i].omit==0 ){ + /* Do not attempt to use an IN constraint if the virtual table + ** says that the equivalent EQ constraint cannot be safely omitted. + ** If we do attempt to use such a constraint, some rows might be + ** repeated in the output. */ + break; + } + for(k=0; knOrderBy; k++){ + if( pIdxInfo->aOrderBy[k].iColumn==pIdxCons->iColumn ){ + sortOrder = pIdxInfo->aOrderBy[k].desc; + break; + } + } } } } if( i>=pIdxInfo->nConstraint ) break; } @@ -2411,11 +2419,12 @@ }else{ p->cost.rCost = rCost; } p->cost.plan.u.pVtabIdx = pIdxInfo; if( pIdxInfo->orderByConsumed ){ - p->cost.plan.wsFlags |= WHERE_ORDERED; + assert( sortOrder==0 || sortOrder==1 ); + p->cost.plan.wsFlags |= WHERE_ORDERED + sortOrder*WHERE_REVERSE; p->cost.plan.nOBSat = nOrderBy; }else{ p->cost.plan.nOBSat = p->i ? p->aLevel[p->i-1].plan.nOBSat : 0; } p->cost.plan.nEq = 0; @@ -3008,14 +3017,11 @@ pConstraint = findTerm(p->pWC, base, iColumn, p->notReady, WO_EQ|WO_ISNULL|WO_IN, pIdx); if( pConstraint==0 ){ isEq = 0; }else if( (pConstraint->eOperator & WO_IN)!=0 ){ - /* Constraints of the form: "X IN ..." cannot be used with an ORDER BY - ** because we do not know in what order the values on the RHS of the IN - ** operator will occur. */ - break; + isEq = 0; }else if( (pConstraint->eOperator & WO_ISNULL)!=0 ){ uniqueNotNull = 0; isEq = 1; /* "X IS NULL" means X has only a single value */ }else if( pConstraint->prereqRight==0 ){ isEq = 1; /* Constraint "X=constant" means X has only a single value */ @@ -3315,12 +3321,12 @@ ** constraint for all columns in the index, then this search will find ** at most a single row. In this case set the WHERE_UNIQUE flag to ** indicate this to the caller. ** ** Otherwise, if the search may find more than one row, test to see if - ** there is a range constraint on indexed column (pc.plan.nEq+1) that can be - ** optimized using the index. + ** there is a range constraint on indexed column (pc.plan.nEq+1) that + ** can be optimized using the index. */ if( pc.plan.nEq==pProbe->nColumn && pProbe->onError!=OE_None ){ testcase( pc.plan.wsFlags & WHERE_COLUMN_IN ); testcase( pc.plan.wsFlags & WHERE_COLUMN_NULL ); if( (pc.plan.wsFlags & (WHERE_COLUMN_IN|WHERE_COLUMN_NULL))==0 ){ @@ -3657,11 +3663,12 @@ #ifndef SQLITE_OMIT_VIRTUALTABLE if( IsVirtual(p->pSrc->pTab) ){ sqlite3_index_info *pIdxInfo = 0; p->ppIdxInfo = &pIdxInfo; bestVirtualIndex(p); - if( pIdxInfo->needToFreeIdxStr ){ + assert( pIdxInfo!=0 || p->pParse->db->mallocFailed ); + if( pIdxInfo && pIdxInfo->needToFreeIdxStr ){ sqlite3_free(pIdxInfo->idxStr); } sqlite3DbFree(p->pParse->db, pIdxInfo); }else #endif @@ -3781,16 +3788,17 @@ #ifndef SQLITE_OMIT_SUBQUERY }else{ int eType; int iTab; struct InLoop *pIn; + u8 bRev = (pLevel->plan.wsFlags & WHERE_REVERSE)!=0; assert( pX->op==TK_IN ); iReg = iTarget; eType = sqlite3FindInIndex(pParse, pX, 0); iTab = pX->iTable; - sqlite3VdbeAddOp2(v, OP_Rewind, iTab, 0); + sqlite3VdbeAddOp2(v, bRev ? OP_Last : OP_Rewind, iTab, 0); assert( pLevel->plan.wsFlags & WHERE_IN_ABLE ); if( pLevel->u.in.nIn==0 ){ pLevel->addrNxt = sqlite3VdbeMakeLabel(v); } pLevel->u.in.nIn++; @@ -3804,10 +3812,11 @@ if( eType==IN_INDEX_ROWID ){ pIn->addrInTop = sqlite3VdbeAddOp2(v, OP_Rowid, iTab, iReg); }else{ pIn->addrInTop = sqlite3VdbeAddOp3(v, OP_Column, iTab, 0, iReg); } + pIn->eEndLoopOp = bRev ? OP_Prev : OP_Next; sqlite3VdbeAddOp1(v, OP_IsNull, iReg); }else{ pLevel->u.in.nIn = 0; } #endif @@ -5055,28 +5064,17 @@ ** its Expr.iRightJoinTable value to find the bitmask of the right table ** of the join. Subtracting one from the right table bitmask gives a ** bitmask for all tables to the left of the join. Knowing the bitmask ** for all tables to the left of a left join is important. Ticket #3015. ** - ** Configure the WhereClause.vmask variable so that bits that correspond - ** to virtual table cursors are set. This is used to selectively disable - ** the OR-to-IN transformation in exprAnalyzeOrTerm(). It is not helpful - ** with virtual tables. - ** ** Note that bitmasks are created for all pTabList->nSrc tables in ** pTabList, not just the first nTabList tables. nTabList is normally ** equal to pTabList->nSrc but might be shortened to 1 if the ** WHERE_ONETABLE_ONLY flag is set. */ - assert( sWBI.pWC->vmask==0 && pMaskSet->n==0 ); for(ii=0; iinSrc; ii++){ createMask(pMaskSet, pTabList->a[ii].iCursor); -#ifndef SQLITE_OMIT_VIRTUALTABLE - if( ALWAYS(pTabList->a[ii].pTab) && IsVirtual(pTabList->a[ii].pTab) ){ - sWBI.pWC->vmask |= ((Bitmask)1 << ii); - } -#endif } #ifndef NDEBUG { Bitmask toTheLeft = 0; for(ii=0; iinSrc; ii++){ @@ -5556,11 +5554,11 @@ struct InLoop *pIn; int j; sqlite3VdbeResolveLabel(v, pLevel->addrNxt); for(j=pLevel->u.in.nIn, pIn=&pLevel->u.in.aInLoop[j-1]; j>0; j--, pIn--){ sqlite3VdbeJumpHere(v, pIn->addrInTop+1); - sqlite3VdbeAddOp2(v, OP_Next, pIn->iCur, pIn->addrInTop); + sqlite3VdbeAddOp2(v, pIn->eEndLoopOp, pIn->iCur, pIn->addrInTop); sqlite3VdbeJumpHere(v, pIn->addrInTop-1); } sqlite3DbFree(db, pLevel->u.in.aInLoop); } sqlite3VdbeResolveLabel(v, pLevel->addrBrk); Index: test/where.test ================================================================== --- test/where.test +++ test/where.test @@ -377,15 +377,30 @@ do_test where-5.2 { count { SELECT * FROM t1 WHERE rowid+0 IN (1,2,3,1234) order by 1; } } {1 0 4 2 1 9 3 1 16 102} - do_test where-5.3 { + do_test where-5.3a { count { SELECT * FROM t1 WHERE w IN (-1,1,2,3) order by 1; } - } {1 0 4 2 1 9 3 1 16 14} + } {1 0 4 2 1 9 3 1 16 13} + do_test where-5.3b { + count { + SELECT * FROM t1 WHERE w IN (3,-1,1,2) order by 1; + } + } {1 0 4 2 1 9 3 1 16 13} + do_test where-5.3c { + count { + SELECT * FROM t1 WHERE w IN (3,2,-1,1,2) order by 1; + } + } {1 0 4 2 1 9 3 1 16 13} + do_test where-5.3d { + count { + SELECT * FROM t1 WHERE w IN (-1,1,2,3) order by 1 DESC; + } + } {3 1 16 2 1 9 1 0 4 12} do_test where-5.4 { count { SELECT * FROM t1 WHERE w+0 IN (-1,1,2,3) order by 1; } } {1 0 4 2 1 9 3 1 16 102} @@ -450,10 +465,34 @@ do_test where-5.15 { count { SELECT * FROM t1 WHERE x IN (1,7) AND y IN (9,16) ORDER BY 1; } } {2 1 9 3 1 16 11} + do_test where-5.100 { + db eval { + SELECT w, x, y FROM t1 WHERE x IN (1,5) AND y IN (9,8,3025,1000,3969) + ORDER BY x, y + } + } {2 1 9 54 5 3025 62 5 3969} + do_test where-5.101 { + db eval { + SELECT w, x, y FROM t1 WHERE x IN (1,5) AND y IN (9,8,3025,1000,3969) + ORDER BY x DESC, y DESC + } + } {62 5 3969 54 5 3025 2 1 9} + do_test where-5.102 { + db eval { + SELECT w, x, y FROM t1 WHERE x IN (1,5) AND y IN (9,8,3025,1000,3969) + ORDER BY x DESC, y + } + } {54 5 3025 62 5 3969 2 1 9} + do_test where-5.103 { + db eval { + SELECT w, x, y FROM t1 WHERE x IN (1,5) AND y IN (9,8,3025,1000,3969) + ORDER BY x, y DESC + } + } {2 1 9 62 5 3969 54 5 3025} } # This procedure executes the SQL. Then it checks to see if the OP_Sort # opcode was executed. If an OP_Sort did occur, then "sort" is appended # to the result. If no OP_Sort happened, then "nosort" is appended. @@ -509,15 +548,20 @@ cksort { SELECT * FROM t3 WHERE b>0 ORDER BY a LIMIT 3 } } {1 100 4 2 99 9 3 98 16 nosort} ifcapable subquery { - do_test where-6.8 { + do_test where-6.8a { 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 sort} + } {1 100 4 2 99 9 3 98 16 nosort} + do_test where-6.8b { + cksort { + SELECT * FROM t3 WHERE a IN (3,5,7,1,9,4,2) ORDER BY a DESC LIMIT 3 + } + } {9 92 100 7 94 64 5 96 36 nosort} } do_test where-6.9.1 { cksort { SELECT * FROM t3 WHERE a=1 AND c>0 ORDER BY a LIMIT 3 } Index: test/where2.test ================================================================== --- test/where2.test +++ test/where2.test @@ -165,28 +165,58 @@ AND x>0 AND x<10 ORDER BY w } } {99 6 10000 10006 100 6 10201 10207 sort t1 i1zyx} } - do_test where2-4.6 { + do_test where2-4.6a { + queryplan { + SELECT * FROM t1 + WHERE x IN (1,2,3,4,5,6,7,8) + AND y IN (10000,10001,10002,10003,10004,10005) + ORDER BY x + } + } {99 6 10000 10006 nosort t1 i1xy} + do_test where2-4.6b { + queryplan { + SELECT * FROM t1 + WHERE x IN (1,2,3,4,5,6,7,8) + AND y IN (10000,10001,10002,10003,10004,10005) + ORDER BY x DESC + } + } {99 6 10000 10006 nosort t1 i1xy} + do_test where2-4.6c { + queryplan { + SELECT * FROM t1 + WHERE x IN (1,2,3,4,5,6,7,8) + AND y IN (10000,10001,10002,10003,10004,10005) + ORDER BY x, y + } + } {99 6 10000 10006 nosort t1 i1xy} + do_test where2-4.6d { queryplan { SELECT * FROM t1 WHERE x IN (1,2,3,4,5,6,7,8) AND y IN (10000,10001,10002,10003,10004,10005) - ORDER BY 2 + ORDER BY x, y DESC } } {99 6 10000 10006 sort t1 i1xy} # Duplicate entires on the RHS of an IN operator do not cause duplicate # output rows. # - do_test where2-4.6 { + do_test where2-4.6x { queryplan { SELECT * FROM t1 WHERE z IN (10207,10006,10006,10207) ORDER BY w } } {99 6 10000 10006 100 6 10201 10207 sort t1 i1zyx} + do_test where2-4.6y { + queryplan { + SELECT * FROM t1 WHERE z IN (10207,10006,10006,10207) + ORDER BY w DESC + } + } {100 6 10201 10207 99 6 10000 10006 sort t1 i1zyx} ifcapable compound { do_test where2-4.7 { queryplan { SELECT * FROM t1 WHERE z IN ( SELECT 10207 UNION ALL SELECT 10006 @@ -205,15 +235,20 @@ SELECT * FROM t1 WHERE w=99 ORDER BY w } } {99 6 10000 10006 nosort t1 i1w} ifcapable subquery { - do_test where2-5.2 { + do_test where2-5.2a { queryplan { SELECT * FROM t1 WHERE w IN (99) ORDER BY w } - } {99 6 10000 10006 sort t1 i1w} + } {99 6 10000 10006 nosort t1 i1w} + do_test where2-5.2b { + queryplan { + SELECT * FROM t1 WHERE w IN (99) ORDER BY w DESC + } + } {99 6 10000 10006 nosort t1 i1w} } # Verify that OR clauses get translated into IN operators. # set ::idx {}