Index: src/expr.c
==================================================================
--- src/expr.c
+++ src/expr.c
@@ -1507,11 +1507,12 @@
 */
 #ifndef SQLITE_OMIT_SUBQUERY
 static void sqlite3CreateInOperatorRhsTable(
   Parse *pParse,          /* Parsing context */
   Expr *pExpr,            /* The IN, SELECT, or EXISTS operator */
-  int isRowid             /* If true, LHS of IN operator is a rowid */
+  int isRowid,            /* If true, LHS of IN operator is a rowid */
+  int bOrdered            /* If true, must use btree, not a hash */
 ){
   int testAddr = -1;                      /* One-time test address */
   Vdbe *v = sqlite3GetVdbe(pParse);       /* prepared stmt under construction */
   char affinity;                          /* Affinity of the LHS of the IN */
   int addr;                               /* Address of OP_Open.. instruction */
@@ -1559,11 +1560,12 @@
   ** if either column has NUMERIC or INTEGER affinity. If neither
   ** 'x' nor the SELECT... statement are columns, then numeric affinity
   ** is used.
   */
   pExpr->iTable = pParse->nTab++;
-  addr = sqlite3VdbeAddOp2(v, OP_OpenEphemeral, pExpr->iTable, !isRowid);
+  addr = sqlite3VdbeAddOp2(v, bOrdered ? OP_OpenEphemeral : OP_OpenHash,
+                           pExpr->iTable, !isRowid);
   pKeyInfo = isRowid ? 0 : sqlite3KeyInfoAlloc(pParse->db, 1, 1);
 
   if( ExprHasProperty(pExpr, EP_xIsSelect) ){
     /* Case 1:     expr IN (SELECT ...)
     **
@@ -1720,13 +1722,16 @@
 **     register = 1
 **   }
 **
 ** in order to avoid running the <test if data structure contains null>
 ** test more often than is necessary.
+**
+** IN_INDEX_EPH ephemeral tables must be in key order if the bOrdered flag
+** is true.  If bOrdered is false, the generated table can be a hash.
 */
 #ifndef SQLITE_OMIT_SUBQUERY
-int sqlite3FindInIndex(Parse *pParse, Expr *pX, int *prNotFound){
+int sqlite3FindInIndex(Parse *pParse, Expr *pX, int *prNotFound, int bOrdered){
   Select *p;                            /* SELECT to the right of IN operator */
   int eType = 0;                        /* Type of RHS table. IN_INDEX_* */
   int iTab = pParse->nTab++;            /* Cursor of the RHS table */
   int mustBeUnique = (prNotFound==0);   /* True if RHS must be unique */
   Vdbe *v = sqlite3GetVdbe(pParse);     /* Virtual machine being coded */
@@ -1815,11 +1820,11 @@
       pParse->nQueryLoop = 0;
       if( pX->pLeft->iColumn<0 && !ExprHasProperty(pX, EP_xIsSelect) ){
         eType = IN_INDEX_ROWID;
       }
     }
-    sqlite3CreateInOperatorRhsTable(pParse, pX, eType==IN_INDEX_ROWID);
+    sqlite3CreateInOperatorRhsTable(pParse, pX, eType==IN_INDEX_ROWID,bOrdered);
     pParse->nQueryLoop = savedNQueryLoop;
   }else{
     pX->iTable = iTab;
   }
   return eType;
@@ -1941,11 +1946,11 @@
   ** pExpr->iTable will contains the values that make up the RHS.
   */
   v = pParse->pVdbe;
   assert( v!=0 );       /* OOM detected prior to this routine */
   VdbeNoopComment((v, "begin IN expr"));
-  eType = sqlite3FindInIndex(pParse, pExpr, &rRhsHasNull);
+  eType = sqlite3FindInIndex(pParse, pExpr, &rRhsHasNull, 0);
 
   /* Figure out the affinity to use to create a key from the results
   ** of the expression. affinityStr stores a static string suitable for
   ** P4 of OP_MakeRecord.
   */

Index: src/sqliteInt.h
==================================================================
--- src/sqliteInt.h
+++ src/sqliteInt.h
@@ -3476,11 +3476,11 @@
 
 #define IN_INDEX_ROWID           1
 #define IN_INDEX_EPH             2
 #define IN_INDEX_INDEX_ASC       3
 #define IN_INDEX_INDEX_DESC      4
-int sqlite3FindInIndex(Parse *, Expr *, int*);
+int sqlite3FindInIndex(Parse *, Expr *, int*, int);
 
 #ifdef SQLITE_ENABLE_ATOMIC_WRITE
   int sqlite3JournalOpen(sqlite3_vfs *, const char *, sqlite3_file *, int, int);
   int sqlite3JournalSize(sqlite3_vfs *);
   int sqlite3JournalCreate(sqlite3_file *);

Index: src/where.c
==================================================================
--- src/where.c
+++ src/where.c
@@ -2346,20 +2346,21 @@
 ** For a constraint of the form X=expr, the expression is evaluated and its
 ** result is left on the stack.  For constraints of the form X IN (...)
 ** this routine sets up a loop that will iterate over all values of X.
 */
 static int codeEqualityTerm(
-  Parse *pParse,      /* The parsing context */
+  WhereInfo *pWInfo,  /* WHERE clause */
   WhereTerm *pTerm,   /* The term of the WHERE clause to be coded */
   WhereLevel *pLevel, /* The level of the FROM clause we are working on */
   int iEq,            /* Index of the equality term within this level */
   int bRev,           /* True for reverse-order IN operations */
   int iTarget         /* Attempt to leave results in this register */
 ){
-  Expr *pX = pTerm->pExpr;
-  Vdbe *v = pParse->pVdbe;
-  int iReg;                  /* Register holding results */
+  Expr *pX = pTerm->pExpr;            /* Expression to be coded */
+  Parse *pParse = pWInfo->pParse;     /* Parsing context */
+  Vdbe *v = pParse->pVdbe;            /* Prepared stmt under construction */
+  int iReg;                           /* Register holding results */
 
   assert( iTarget>0 );
   if( pX->op==TK_EQ ){
     iReg = sqlite3ExprCodeTarget(pParse, pX->pRight, iTarget);
   }else if( pX->op==TK_ISNULL ){
@@ -2380,11 +2381,11 @@
       testcase( bRev );
       bRev = !bRev;
     }
     assert( pX->op==TK_IN );
     iReg = iTarget;
-    eType = sqlite3FindInIndex(pParse, pX, 0);
+    eType = sqlite3FindInIndex(pParse, pX, 0, pWInfo->bOBSat);
     if( eType==IN_INDEX_INDEX_DESC ){
       testcase( bRev );
       bRev = !bRev;
     }
     iTab = pX->iTable;
@@ -2462,18 +2463,19 @@
 ** no conversion should be attempted before using a t2.b value as part of
 ** a key to search the index. Hence the first byte in the returned affinity
 ** string in this example would be set to SQLITE_AFF_NONE.
 */
 static int codeAllEqualityTerms(
-  Parse *pParse,        /* Parsing context */
+  WhereInfo *pWInfo,    /* WHERE clause */
   WhereLevel *pLevel,   /* Which nested loop of the FROM we are coding */
   int bRev,             /* Reverse the order of IN operators */
   int nExtraReg,        /* Number of extra registers to allocate */
   char **pzAff          /* OUT: Set to point to affinity string */
 ){
   u16 nEq;                      /* The number of == or IN constraints to code */
   u16 nSkip;                    /* Number of left-most columns to skip */
+  Parse *pParse = pWInfo->pParse; /* Parsing context */
   Vdbe *v = pParse->pVdbe;      /* The vm under construction */
   Index *pIdx;                  /* The index being used for this loop */
   WhereTerm *pTerm;             /* A single constraint term */
   WhereLoop *pLoop;             /* The WhereLoop object */
   int j;                        /* Loop counter */
@@ -2524,11 +2526,11 @@
     assert( pTerm!=0 );
     /* The following testcase is 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 );
-    r1 = codeEqualityTerm(pParse, pTerm, pLevel, j, bRev, regBase+j);
+    r1 = codeEqualityTerm(pWInfo, pTerm, pLevel, j, bRev, regBase+j);
     if( r1!=regBase+j ){
       if( nReg==1 ){
         sqlite3ReleaseTempReg(pParse, regBase);
         regBase = r1;
       }else{
@@ -2807,11 +2809,11 @@
     for(j=0; j<nConstraint; j++){
       int iTarget = iReg+j+2;
       pTerm = pLoop->aLTerm[j];
       if( pTerm==0 ) continue;
       if( pTerm->eOperator & WO_IN ){
-        codeEqualityTerm(pParse, pTerm, pLevel, j, bRev, iTarget);
+        codeEqualityTerm(pWInfo, pTerm, pLevel, j, bRev, iTarget);
         addrNotFound = pLevel->addrNxt;
       }else{
         sqlite3ExprCode(pParse, pTerm->pExpr->pRight, iTarget);
       }
     }
@@ -2847,11 +2849,11 @@
     pTerm = pLoop->aLTerm[0];
     assert( pTerm!=0 );
     assert( pTerm->pExpr!=0 );
     assert( omitTable==0 );
     testcase( pTerm->wtFlags & TERM_VIRTUAL );
-    iRowidReg = codeEqualityTerm(pParse, pTerm, pLevel, 0, bRev, iReleaseReg);
+    iRowidReg = codeEqualityTerm(pWInfo, pTerm, pLevel, 0, bRev, iReleaseReg);
     addrNxt = pLevel->addrNxt;
     sqlite3VdbeAddOp2(v, OP_MustBeInt, iRowidReg, addrNxt);
     sqlite3VdbeAddOp3(v, OP_NotExists, iCur, addrNxt, iRowidReg);
     sqlite3ExprCacheAffinityChange(pParse, iRowidReg, 1);
     sqlite3ExprCacheStore(pParse, iCur, -1, iRowidReg);
@@ -3037,11 +3039,11 @@
 
     /* Generate code to evaluate all constraint terms using == or IN
     ** and store the values of those terms in an array of registers
     ** starting at regBase.
     */
-    regBase = codeAllEqualityTerms(pParse,pLevel,bRev,nExtraReg,&zStartAff);
+    regBase = codeAllEqualityTerms(pWInfo,pLevel,bRev,nExtraReg,&zStartAff);
     assert( zStartAff==0 || sqlite3Strlen30(zStartAff)>=nEq );
     if( zStartAff ) cEndAff = zStartAff[nEq];
     addrNxt = pLevel->addrNxt;
 
     /* If we are doing a reverse order scan on an ascending index, or

Index: test/in3.test
==================================================================
--- test/in3.test
+++ test/in3.test
@@ -27,11 +27,11 @@
 # implementation of the sql statement passed as a an argument.
 #
 proc nEphemeral {sql} {
   set nEph 0
   foreach op [execsql "EXPLAIN $sql"] {
-    if {$op eq "OpenEphemeral"} {incr nEph}
+    if {$op eq "OpenEphemeral" || $op eq "OpenHash"} {incr nEph}
   }
   set nEph
 }
 
 # This proc works the same way as execsql, except that the number

Index: test/in5.test
==================================================================
--- test/in5.test
+++ test/in5.test
@@ -63,21 +63,21 @@
   execsql {
     SELECT d FROM t2 WHERE a IN t3x AND b IN t3y AND c IN t3z ORDER BY d;
   }
 } {12a 56e}
 do_test in5-2.5.1 {
-  regexp {OpenEphemeral} [db eval {
+  regexp {Open(Ephemeral|Hash)} [db eval {
     EXPLAIN SELECT d FROM t2 WHERE a IN t3x AND b IN t1y AND c IN t1z
   }]
 } {1}
 do_test in5-2.5.2 {
-  regexp {OpenEphemeral} [db eval {
+  regexp {Open(Ephemeral|Hash)} [db eval {
     EXPLAIN SELECT d FROM t2 WHERE a IN t1x AND b IN t3y AND c IN t1z
   }]
 } {1}
 do_test in5-2.5.3 {
-  regexp {OpenEphemeral} [db eval {
+  regexp {Open(Ephemeral|Hash)} [db eval {
     EXPLAIN SELECT d FROM t2 WHERE a IN t1x AND b IN t1y AND c IN t3z
   }]
 } {1}
 
 do_test in5-3.1 {