/ Check-in [2cef8b68]
Login

Many hyperlinks are disabled.
Use anonymous login to enable hyperlinks.

Overview
Comment:Allow an index to be used for sorting even if prior terms of the index are constrained by IN operators.
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1: 2cef8b68f0e1216cf68bb7dd45a5a9a330748070
User & Date: drh 2013-02-13 01:00:35
References
2013-03-12
17:34 New ticket [4dd95f69] Inverted result order with ORDER BY DESC and a DESC index.. artifact: 8f409867 user: drh
Context
2013-02-13
14:04
Add recent API additions to the extension mechanism. check-in: 7e10a62d user: drh tags: trunk
13:42
Enhancements to the query planner to make use of indices for ORDER BY even when IN constraints are in the WHERE clause. Add extended error codes for all SQLITE_CONSTRAINT errors. check-in: 7e14dc73 user: drh tags: sessions
01:00
Allow an index to be used for sorting even if prior terms of the index are constrained by IN operators. check-in: 2cef8b68 user: drh tags: trunk
2013-02-12
22:20
Improve memory allocation error handling on WinCE. check-in: cdbca259 user: drh tags: trunk
2013-02-08
23:18
Fix a potential NULL-pointer dereference following an OOM error in the query planner logic for virtual tables with OR-connected terms. Closed-Leaf check-in: 71b6c260 user: drh tags: IN-with-ORDERBY
Changes
Hide Diffs Side-by-Side Diffs Ignore Whitespace Patch

Changes to src/sqliteInt.h.

  1961   1961     int p1, p2;           /* Operands of the opcode used to ends the loop */
  1962   1962     union {               /* Information that depends on plan.wsFlags */
  1963   1963       struct {
  1964   1964         int nIn;              /* Number of entries in aInLoop[] */
  1965   1965         struct InLoop {
  1966   1966           int iCur;              /* The VDBE cursor used by this IN operator */
  1967   1967           int addrInTop;         /* Top of the IN loop */
         1968  +        u8 eEndLoopOp;         /* IN Loop terminator. OP_Next or OP_Prev */
  1968   1969         } *aInLoop;           /* Information about each nested IN operator */
  1969   1970       } in;                 /* Used when plan.wsFlags&WHERE_IN_ABLE */
  1970   1971       Index *pCovidx;       /* Possible covering index for WHERE_MULTI_OR */
  1971   1972     } u;
  1972   1973     double rOptCost;      /* "Optimal" cost for this level */
  1973   1974   
  1974   1975     /* The following field is really not part of the current level.  But

Changes to src/where.c.

   136    136   ** There are separate WhereClause objects for the whole clause and for
   137    137   ** the subclauses "(b AND c)" and "(d AND e)".  The pOuter field of the
   138    138   ** subclauses points to the WhereClause object for the whole clause.
   139    139   */
   140    140   struct WhereClause {
   141    141     Parse *pParse;           /* The parser context */
   142    142     WhereMaskSet *pMaskSet;  /* Mapping of table cursor numbers to bitmasks */
   143         -  Bitmask vmask;           /* Bitmask identifying virtual table cursors */
   144    143     WhereClause *pOuter;     /* Outer conjunction */
   145    144     u8 op;                   /* Split operator.  TK_AND or TK_OR */
   146    145     u16 wctrlFlags;          /* Might include WHERE_AND_ONLY */
   147    146     int nTerm;               /* Number of terms */
   148    147     int nSlot;               /* Number of entries in a[] */
   149    148     WhereTerm *a;            /* Each a[] describes a term of the WHERE cluase */
   150    149   #if defined(SQLITE_SMALL_STACK)
................................................................................
   313    312   ){
   314    313     pWC->pParse = pParse;
   315    314     pWC->pMaskSet = pMaskSet;
   316    315     pWC->pOuter = 0;
   317    316     pWC->nTerm = 0;
   318    317     pWC->nSlot = ArraySize(pWC->aStatic);
   319    318     pWC->a = pWC->aStatic;
   320         -  pWC->vmask = 0;
   321    319     pWC->wctrlFlags = wctrlFlags;
   322    320   }
   323    321   
   324    322   /* Forward reference */
   325    323   static void whereClauseClear(WhereClause*);
   326    324   
   327    325   /*
................................................................................
   913    911   **     (B)     x=expr1 OR expr2=x OR x=expr3
   914    912   **     (C)     t1.x=t2.y OR (t1.x=t2.z AND t1.y=15)
   915    913   **     (D)     x=expr1 OR (y>11 AND y<22 AND z LIKE '*hello*')
   916    914   **     (E)     (p.a=1 AND q.b=2 AND r.c=3) OR (p.x=4 AND q.y=5 AND r.z=6)
   917    915   **
   918    916   ** CASE 1:
   919    917   **
   920         -** If all subterms are of the form T.C=expr for some single column of C
          918  +** If all subterms are of the form T.C=expr for some single column of C and
   921    919   ** a single table T (as shown in example B above) then create a new virtual
   922    920   ** term that is an equivalent IN expression.  In other words, if the term
   923    921   ** being analyzed is:
   924    922   **
   925    923   **      x = expr1  OR  expr2 = x  OR  x = expr3
   926    924   **
   927    925   ** then create a new virtual term like this:
................................................................................
  1001    999     if( db->mallocFailed ) return;
  1002   1000     assert( pOrWc->nTerm>=2 );
  1003   1001   
  1004   1002     /*
  1005   1003     ** Compute the set of tables that might satisfy cases 1 or 2.
  1006   1004     */
  1007   1005     indexable = ~(Bitmask)0;
  1008         -  chngToIN = ~(pWC->vmask);
         1006  +  chngToIN = ~(Bitmask)0;
  1009   1007     for(i=pOrWc->nTerm-1, pOrTerm=pOrWc->a; i>=0 && indexable; i--, pOrTerm++){
  1010   1008       if( (pOrTerm->eOperator & WO_SINGLE)==0 ){
  1011   1009         WhereAndInfo *pAndInfo;
  1012   1010         assert( (pOrTerm->wtFlags & (TERM_ANDINFO|TERM_ORINFO))==0 );
  1013   1011         chngToIN = 0;
  1014   1012         pAndInfo = sqlite3DbMallocRaw(db, sizeof(*pAndInfo));
  1015   1013         if( pAndInfo ){
................................................................................
  2268   2266     WhereClause *pWC = p->pWC;      /* The WHERE clause */
  2269   2267     struct SrcList_item *pSrc = p->pSrc; /* The FROM clause term to search */
  2270   2268     Table *pTab = pSrc->pTab;
  2271   2269     sqlite3_index_info *pIdxInfo;
  2272   2270     struct sqlite3_index_constraint *pIdxCons;
  2273   2271     struct sqlite3_index_constraint_usage *pUsage;
  2274   2272     WhereTerm *pTerm;
  2275         -  int i, j;
         2273  +  int i, j, k;
  2276   2274     int nOrderBy;
         2275  +  int sortOrder;                  /* Sort order for IN clauses */
  2277   2276     int bAllowIN;                   /* Allow IN optimizations */
  2278   2277     double rCost;
  2279   2278   
  2280   2279     /* Make sure wsFlags is initialized to some sane value. Otherwise, if the 
  2281   2280     ** malloc in allocateIndexInfo() fails and this function returns leaving
  2282   2281     ** wsFlags in an uninitialized state, the caller may behave unpredictably.
  2283   2282     */
................................................................................
  2368   2367         pIdxInfo->nOrderBy = 0;
  2369   2368       }
  2370   2369     
  2371   2370       if( vtabBestIndex(pParse, pTab, pIdxInfo) ){
  2372   2371         return;
  2373   2372       }
  2374   2373     
         2374  +    sortOrder = SQLITE_SO_ASC;
  2375   2375       pIdxCons = *(struct sqlite3_index_constraint**)&pIdxInfo->aConstraint;
  2376   2376       for(i=0; i<pIdxInfo->nConstraint; i++, pIdxCons++){
  2377   2377         if( pUsage[i].argvIndex>0 ){
  2378   2378           j = pIdxCons->iTermOffset;
  2379   2379           pTerm = &pWC->a[j];
  2380   2380           p->cost.used |= pTerm->prereqRight;
  2381         -        if( (pTerm->eOperator & WO_IN)!=0 && pUsage[i].omit==0 ){
  2382         -          /* Do not attempt to use an IN constraint if the virtual table
  2383         -          ** says that the equivalent EQ constraint cannot be safely omitted.
  2384         -          ** If we do attempt to use such a constraint, some rows might be
  2385         -          ** repeated in the output. */
  2386         -          break;
         2381  +        if( (pTerm->eOperator & WO_IN)!=0 ){
         2382  +          if( pUsage[i].omit==0 ){
         2383  +            /* Do not attempt to use an IN constraint if the virtual table
         2384  +            ** says that the equivalent EQ constraint cannot be safely omitted.
         2385  +            ** If we do attempt to use such a constraint, some rows might be
         2386  +            ** repeated in the output. */
         2387  +            break;
         2388  +          }
         2389  +          for(k=0; k<pIdxInfo->nOrderBy; k++){
         2390  +            if( pIdxInfo->aOrderBy[k].iColumn==pIdxCons->iColumn ){
         2391  +              sortOrder = pIdxInfo->aOrderBy[k].desc;
         2392  +              break;
         2393  +            }
         2394  +          }
  2387   2395           }
  2388   2396         }
  2389   2397       }
  2390   2398       if( i>=pIdxInfo->nConstraint ) break;
  2391   2399     }
  2392   2400     
  2393   2401     /* If there is an ORDER BY clause, and the selected virtual table index
................................................................................
  2409   2417     if( (SQLITE_BIG_DBL/((double)2))<rCost ){
  2410   2418       p->cost.rCost = (SQLITE_BIG_DBL/((double)2));
  2411   2419     }else{
  2412   2420       p->cost.rCost = rCost;
  2413   2421     }
  2414   2422     p->cost.plan.u.pVtabIdx = pIdxInfo;
  2415   2423     if( pIdxInfo->orderByConsumed ){
  2416         -    p->cost.plan.wsFlags |= WHERE_ORDERED;
         2424  +    assert( sortOrder==0 || sortOrder==1 );
         2425  +    p->cost.plan.wsFlags |= WHERE_ORDERED + sortOrder*WHERE_REVERSE;
  2417   2426       p->cost.plan.nOBSat = nOrderBy;
  2418   2427     }else{
  2419   2428       p->cost.plan.nOBSat = p->i ? p->aLevel[p->i-1].plan.nOBSat : 0;
  2420   2429     }
  2421   2430     p->cost.plan.nEq = 0;
  2422   2431     pIdxInfo->nOrderBy = nOrderBy;
  2423   2432   
................................................................................
  3006   3015       /* If X is the column in the index and ORDER BY clause, check to see
  3007   3016       ** if there are any X= or X IS NULL constraints in the WHERE clause. */
  3008   3017       pConstraint = findTerm(p->pWC, base, iColumn, p->notReady,
  3009   3018                              WO_EQ|WO_ISNULL|WO_IN, pIdx);
  3010   3019       if( pConstraint==0 ){
  3011   3020         isEq = 0;
  3012   3021       }else if( (pConstraint->eOperator & WO_IN)!=0 ){
  3013         -      /* Constraints of the form: "X IN ..." cannot be used with an ORDER BY
  3014         -      ** because we do not know in what order the values on the RHS of the IN
  3015         -      ** operator will occur. */
  3016         -      break;
         3022  +      isEq = 0;
  3017   3023       }else if( (pConstraint->eOperator & WO_ISNULL)!=0 ){
  3018   3024         uniqueNotNull = 0;
  3019   3025         isEq = 1;  /* "X IS NULL" means X has only a single value */
  3020   3026       }else if( pConstraint->prereqRight==0 ){
  3021   3027         isEq = 1;  /* Constraint "X=constant" means X has only a single value */
  3022   3028       }else{
  3023   3029         Expr *pRight = pConstraint->pExpr->pRight;
................................................................................
  3313   3319    
  3314   3320       /* If the index being considered is UNIQUE, and there is an equality 
  3315   3321       ** constraint for all columns in the index, then this search will find
  3316   3322       ** at most a single row. In this case set the WHERE_UNIQUE flag to 
  3317   3323       ** indicate this to the caller.
  3318   3324       **
  3319   3325       ** Otherwise, if the search may find more than one row, test to see if
  3320         -    ** there is a range constraint on indexed column (pc.plan.nEq+1) that can be 
  3321         -    ** optimized using the index. 
         3326  +    ** there is a range constraint on indexed column (pc.plan.nEq+1) that
         3327  +    ** can be optimized using the index. 
  3322   3328       */
  3323   3329       if( pc.plan.nEq==pProbe->nColumn && pProbe->onError!=OE_None ){
  3324   3330         testcase( pc.plan.wsFlags & WHERE_COLUMN_IN );
  3325   3331         testcase( pc.plan.wsFlags & WHERE_COLUMN_NULL );
  3326   3332         if( (pc.plan.wsFlags & (WHERE_COLUMN_IN|WHERE_COLUMN_NULL))==0 ){
  3327   3333           pc.plan.wsFlags |= WHERE_UNIQUE;
  3328   3334           if( p->i==0 || (p->aLevel[p->i-1].plan.wsFlags & WHERE_ALL_UNIQUE)!=0 ){
................................................................................
  3655   3661   */
  3656   3662   static void bestIndex(WhereBestIdx *p){
  3657   3663   #ifndef SQLITE_OMIT_VIRTUALTABLE
  3658   3664     if( IsVirtual(p->pSrc->pTab) ){
  3659   3665       sqlite3_index_info *pIdxInfo = 0;
  3660   3666       p->ppIdxInfo = &pIdxInfo;
  3661   3667       bestVirtualIndex(p);
  3662         -    if( pIdxInfo->needToFreeIdxStr ){
         3668  +    assert( pIdxInfo!=0 || p->pParse->db->mallocFailed );
         3669  +    if( pIdxInfo && pIdxInfo->needToFreeIdxStr ){
  3663   3670         sqlite3_free(pIdxInfo->idxStr);
  3664   3671       }
  3665   3672       sqlite3DbFree(p->pParse->db, pIdxInfo);
  3666   3673     }else
  3667   3674   #endif
  3668   3675     {
  3669   3676       bestBtreeIndex(p);
................................................................................
  3779   3786       iReg = iTarget;
  3780   3787       sqlite3VdbeAddOp2(v, OP_Null, 0, iReg);
  3781   3788   #ifndef SQLITE_OMIT_SUBQUERY
  3782   3789     }else{
  3783   3790       int eType;
  3784   3791       int iTab;
  3785   3792       struct InLoop *pIn;
         3793  +    u8 bRev = (pLevel->plan.wsFlags & WHERE_REVERSE)!=0;
  3786   3794   
  3787   3795       assert( pX->op==TK_IN );
  3788   3796       iReg = iTarget;
  3789   3797       eType = sqlite3FindInIndex(pParse, pX, 0);
  3790   3798       iTab = pX->iTable;
  3791         -    sqlite3VdbeAddOp2(v, OP_Rewind, iTab, 0);
         3799  +    sqlite3VdbeAddOp2(v, bRev ? OP_Last : OP_Rewind, iTab, 0);
  3792   3800       assert( pLevel->plan.wsFlags & WHERE_IN_ABLE );
  3793   3801       if( pLevel->u.in.nIn==0 ){
  3794   3802         pLevel->addrNxt = sqlite3VdbeMakeLabel(v);
  3795   3803       }
  3796   3804       pLevel->u.in.nIn++;
  3797   3805       pLevel->u.in.aInLoop =
  3798   3806          sqlite3DbReallocOrFree(pParse->db, pLevel->u.in.aInLoop,
................................................................................
  3802   3810         pIn += pLevel->u.in.nIn - 1;
  3803   3811         pIn->iCur = iTab;
  3804   3812         if( eType==IN_INDEX_ROWID ){
  3805   3813           pIn->addrInTop = sqlite3VdbeAddOp2(v, OP_Rowid, iTab, iReg);
  3806   3814         }else{
  3807   3815           pIn->addrInTop = sqlite3VdbeAddOp3(v, OP_Column, iTab, 0, iReg);
  3808   3816         }
         3817  +      pIn->eEndLoopOp = bRev ? OP_Prev : OP_Next;
  3809   3818         sqlite3VdbeAddOp1(v, OP_IsNull, iReg);
  3810   3819       }else{
  3811   3820         pLevel->u.in.nIn = 0;
  3812   3821       }
  3813   3822   #endif
  3814   3823     }
  3815   3824     disableTerm(pLevel, pTerm);
................................................................................
  5053   5062     ** the bitmask for all FROM clause terms to the left of the N-th term
  5054   5063     ** is (X-1).   An expression from the ON clause of a LEFT JOIN can use
  5055   5064     ** its Expr.iRightJoinTable value to find the bitmask of the right table
  5056   5065     ** of the join.  Subtracting one from the right table bitmask gives a
  5057   5066     ** bitmask for all tables to the left of the join.  Knowing the bitmask
  5058   5067     ** for all tables to the left of a left join is important.  Ticket #3015.
  5059   5068     **
  5060         -  ** Configure the WhereClause.vmask variable so that bits that correspond
  5061         -  ** to virtual table cursors are set. This is used to selectively disable 
  5062         -  ** the OR-to-IN transformation in exprAnalyzeOrTerm(). It is not helpful 
  5063         -  ** with virtual tables.
  5064         -  **
  5065   5069     ** Note that bitmasks are created for all pTabList->nSrc tables in
  5066   5070     ** pTabList, not just the first nTabList tables.  nTabList is normally
  5067   5071     ** equal to pTabList->nSrc but might be shortened to 1 if the
  5068   5072     ** WHERE_ONETABLE_ONLY flag is set.
  5069   5073     */
  5070         -  assert( sWBI.pWC->vmask==0 && pMaskSet->n==0 );
  5071   5074     for(ii=0; ii<pTabList->nSrc; ii++){
  5072   5075       createMask(pMaskSet, pTabList->a[ii].iCursor);
  5073         -#ifndef SQLITE_OMIT_VIRTUALTABLE
  5074         -    if( ALWAYS(pTabList->a[ii].pTab) && IsVirtual(pTabList->a[ii].pTab) ){
  5075         -      sWBI.pWC->vmask |= ((Bitmask)1 << ii);
  5076         -    }
  5077         -#endif
  5078   5076     }
  5079   5077   #ifndef NDEBUG
  5080   5078     {
  5081   5079       Bitmask toTheLeft = 0;
  5082   5080       for(ii=0; ii<pTabList->nSrc; ii++){
  5083   5081         Bitmask m = getMask(pMaskSet, pTabList->a[ii].iCursor);
  5084   5082         assert( (m-1)==toTheLeft );
................................................................................
  5554   5552       }
  5555   5553       if( pLevel->plan.wsFlags & WHERE_IN_ABLE && pLevel->u.in.nIn>0 ){
  5556   5554         struct InLoop *pIn;
  5557   5555         int j;
  5558   5556         sqlite3VdbeResolveLabel(v, pLevel->addrNxt);
  5559   5557         for(j=pLevel->u.in.nIn, pIn=&pLevel->u.in.aInLoop[j-1]; j>0; j--, pIn--){
  5560   5558           sqlite3VdbeJumpHere(v, pIn->addrInTop+1);
  5561         -        sqlite3VdbeAddOp2(v, OP_Next, pIn->iCur, pIn->addrInTop);
         5559  +        sqlite3VdbeAddOp2(v, pIn->eEndLoopOp, pIn->iCur, pIn->addrInTop);
  5562   5560           sqlite3VdbeJumpHere(v, pIn->addrInTop-1);
  5563   5561         }
  5564   5562         sqlite3DbFree(db, pLevel->u.in.aInLoop);
  5565   5563       }
  5566   5564       sqlite3VdbeResolveLabel(v, pLevel->addrBrk);
  5567   5565       if( pLevel->iLeftJoin ){
  5568   5566         int addr;

Changes to test/where.test.

   375    375       }
   376    376     } {1 0 4 2 1 9 3 1 16 4}
   377    377     do_test where-5.2 {
   378    378       count {
   379    379         SELECT * FROM t1 WHERE rowid+0 IN (1,2,3,1234) order by 1;
   380    380       }
   381    381     } {1 0 4 2 1 9 3 1 16 102}
   382         -  do_test where-5.3 {
          382  +  do_test where-5.3a {
   383    383       count {
   384    384         SELECT * FROM t1 WHERE w IN (-1,1,2,3) order by 1;
   385    385       }
   386         -  } {1 0 4 2 1 9 3 1 16 14}
          386  +  } {1 0 4 2 1 9 3 1 16 13}
          387  +  do_test where-5.3b {
          388  +    count {
          389  +      SELECT * FROM t1 WHERE w IN (3,-1,1,2) order by 1;
          390  +    }
          391  +  } {1 0 4 2 1 9 3 1 16 13}
          392  +  do_test where-5.3c {
          393  +    count {
          394  +      SELECT * FROM t1 WHERE w IN (3,2,-1,1,2) order by 1;
          395  +    }
          396  +  } {1 0 4 2 1 9 3 1 16 13}
          397  +  do_test where-5.3d {
          398  +    count {
          399  +      SELECT * FROM t1 WHERE w IN (-1,1,2,3) order by 1 DESC;
          400  +    }
          401  +  } {3 1 16 2 1 9 1 0 4 12}
   387    402     do_test where-5.4 {
   388    403       count {
   389    404         SELECT * FROM t1 WHERE w+0 IN (-1,1,2,3) order by 1;
   390    405       }
   391    406     } {1 0 4 2 1 9 3 1 16 102}
   392    407     do_test where-5.5 {
   393    408       count {
................................................................................
   448    463       }
   449    464     } {2 1 9 8}
   450    465     do_test where-5.15 {
   451    466       count {
   452    467         SELECT * FROM t1 WHERE x IN (1,7) AND y IN (9,16) ORDER BY 1;
   453    468       }
   454    469     } {2 1 9 3 1 16 11}
          470  +  do_test where-5.100 {
          471  +    db eval {
          472  +      SELECT w, x, y FROM t1 WHERE x IN (1,5) AND y IN (9,8,3025,1000,3969)
          473  +       ORDER BY x, y
          474  +    }
          475  +  } {2 1 9 54 5 3025 62 5 3969}
          476  +  do_test where-5.101 {
          477  +    db eval {
          478  +      SELECT w, x, y FROM t1 WHERE x IN (1,5) AND y IN (9,8,3025,1000,3969)
          479  +       ORDER BY x DESC, y DESC
          480  +    }
          481  +  } {62 5 3969 54 5 3025 2 1 9}
          482  +  do_test where-5.102 {
          483  +    db eval {
          484  +      SELECT w, x, y FROM t1 WHERE x IN (1,5) AND y IN (9,8,3025,1000,3969)
          485  +       ORDER BY x DESC, y
          486  +    }
          487  +  } {54 5 3025 62 5 3969 2 1 9}
          488  +  do_test where-5.103 {
          489  +    db eval {
          490  +      SELECT w, x, y FROM t1 WHERE x IN (1,5) AND y IN (9,8,3025,1000,3969)
          491  +       ORDER BY x, y DESC
          492  +    }
          493  +  } {2 1 9 62 5 3969 54 5 3025}
   455    494   }
   456    495   
   457    496   # This procedure executes the SQL.  Then it checks to see if the OP_Sort
   458    497   # opcode was executed.  If an OP_Sort did occur, then "sort" is appended
   459    498   # to the result.  If no OP_Sort happened, then "nosort" is appended.
   460    499   #
   461    500   # This procedure is used to check to make sure sorting is or is not
................................................................................
   507    546   } {1 100 4 2 99 9 3 98 16 nosort}
   508    547   do_test where-6.7 {
   509    548     cksort {
   510    549       SELECT * FROM t3 WHERE b>0 ORDER BY a LIMIT 3
   511    550     }
   512    551   } {1 100 4 2 99 9 3 98 16 nosort}
   513    552   ifcapable subquery {
   514         -  do_test where-6.8 {
          553  +  do_test where-6.8a {
   515    554       cksort {
   516    555         SELECT * FROM t3 WHERE a IN (3,5,7,1,9,4,2) ORDER BY a LIMIT 3
   517    556       }
   518         -  } {1 100 4 2 99 9 3 98 16 sort}
          557  +  } {1 100 4 2 99 9 3 98 16 nosort}
          558  +  do_test where-6.8b {
          559  +    cksort {
          560  +      SELECT * FROM t3 WHERE a IN (3,5,7,1,9,4,2) ORDER BY a DESC LIMIT 3
          561  +    }
          562  +  } {9 92 100 7 94 64 5 96 36 nosort}
   519    563   }
   520    564   do_test where-6.9.1 {
   521    565     cksort {
   522    566       SELECT * FROM t3 WHERE a=1 AND c>0 ORDER BY a LIMIT 3
   523    567     }
   524    568   } {1 100 4 nosort}
   525    569   do_test where-6.9.1.1 {

Changes to test/where2.test.

   163    163           SELECT * FROM t1 WHERE z IN (SELECT 10207 UNION SELECT 10006)
   164    164                            AND y IN (SELECT 10000 UNION SELECT 10201)
   165    165                            AND x>0 AND x<10
   166    166           ORDER BY w
   167    167         }
   168    168       } {99 6 10000 10006 100 6 10201 10207 sort t1 i1zyx}
   169    169     }
   170         -  do_test where2-4.6 {
          170  +  do_test where2-4.6a {
          171  +    queryplan {
          172  +      SELECT * FROM t1
          173  +       WHERE x IN (1,2,3,4,5,6,7,8)
          174  +         AND y IN (10000,10001,10002,10003,10004,10005)
          175  +       ORDER BY x
          176  +    }
          177  +  } {99 6 10000 10006 nosort t1 i1xy}
          178  +  do_test where2-4.6b {
          179  +    queryplan {
          180  +      SELECT * FROM t1
          181  +       WHERE x IN (1,2,3,4,5,6,7,8)
          182  +         AND y IN (10000,10001,10002,10003,10004,10005)
          183  +       ORDER BY x DESC
          184  +    }
          185  +  } {99 6 10000 10006 nosort t1 i1xy}
          186  +  do_test where2-4.6c {
          187  +    queryplan {
          188  +      SELECT * FROM t1
          189  +       WHERE x IN (1,2,3,4,5,6,7,8)
          190  +         AND y IN (10000,10001,10002,10003,10004,10005)
          191  +       ORDER BY x, y
          192  +    }
          193  +  } {99 6 10000 10006 nosort t1 i1xy}
          194  +  do_test where2-4.6d {
   171    195       queryplan {
   172    196         SELECT * FROM t1
   173    197          WHERE x IN (1,2,3,4,5,6,7,8)
   174    198            AND y IN (10000,10001,10002,10003,10004,10005)
   175         -       ORDER BY 2
          199  +       ORDER BY x, y DESC
   176    200       }
   177    201     } {99 6 10000 10006 sort t1 i1xy}
   178    202   
   179    203     # Duplicate entires on the RHS of an IN operator do not cause duplicate
   180    204     # output rows.
   181    205     #
   182         -  do_test where2-4.6 {
          206  +  do_test where2-4.6x {
   183    207       queryplan {
   184    208         SELECT * FROM t1 WHERE z IN (10207,10006,10006,10207)
   185    209         ORDER BY w
   186    210       }
   187    211     } {99 6 10000 10006 100 6 10201 10207 sort t1 i1zyx}
          212  +  do_test where2-4.6y {
          213  +    queryplan {
          214  +      SELECT * FROM t1 WHERE z IN (10207,10006,10006,10207)
          215  +      ORDER BY w DESC
          216  +    }
          217  +  } {100 6 10201 10207 99 6 10000 10006 sort t1 i1zyx}
   188    218     ifcapable compound {
   189    219       do_test where2-4.7 {
   190    220         queryplan {
   191    221           SELECT * FROM t1 WHERE z IN (
   192    222              SELECT 10207 UNION ALL SELECT 10006
   193    223              UNION ALL SELECT 10006 UNION ALL SELECT 10207)
   194    224           ORDER BY w
................................................................................
   203    233   do_test where2-5.1 {
   204    234     queryplan {
   205    235       SELECT * FROM t1 WHERE w=99 ORDER BY w
   206    236     }
   207    237   } {99 6 10000 10006 nosort t1 i1w}
   208    238   
   209    239   ifcapable subquery {
   210         -  do_test where2-5.2 {
          240  +  do_test where2-5.2a {
   211    241       queryplan {
   212    242         SELECT * FROM t1 WHERE w IN (99) ORDER BY w
   213    243       }
   214         -  } {99 6 10000 10006 sort t1 i1w}
          244  +  } {99 6 10000 10006 nosort t1 i1w}
          245  +  do_test where2-5.2b {
          246  +    queryplan {
          247  +      SELECT * FROM t1 WHERE w IN (99) ORDER BY w DESC
          248  +    }
          249  +  } {99 6 10000 10006 nosort t1 i1w}
   215    250   }
   216    251   
   217    252   # Verify that OR clauses get translated into IN operators.
   218    253   #
   219    254   set ::idx {}
   220    255   ifcapable subquery {set ::idx i1w}
   221    256   do_test where2-6.1.1 {