SQLite

** intkey B-Tree to store the set of IN(...) values instead of the usual
** (slower) variable length keys B-Tree.
*/
#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 */
  Expr *pLeft = pExpr->pLeft;             /* the LHS of the IN operator */
  KeyInfo *pKeyInfo = 0;                  /* Key information */

  ** column is used to build the index keys. If both 'x' and the
  ** SELECT... statement are columns, then numeric affinity is used
  ** 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, bOrdered ? OP_OpenEphemeral : OP_OpenHash,
  addr = sqlite3VdbeAddOp2(v, OP_OpenEphemeral, pExpr->iTable, !isRowid);
                           pExpr->iTable, !isRowid);
  pKeyInfo = isRowid ? 0 : sqlite3KeyInfoAlloc(pParse->db, 1, 1);

  if( ExprHasProperty(pExpr, EP_xIsSelect) ){
    /* Case 1:     expr IN (SELECT ...)
    **
    ** Generate code to write the results of the select into the temporary
    ** table allocated and opened above.

**   if( register==NULL ){
**     has_null = <test if data structure contains null>
**     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 */

  assert( v!=0 );

    }else{
      testcase( pParse->nQueryLoop>0 );
      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;
}
#endif

  /* Compute the RHS.   After this step, the table with cursor
  ** 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.
  */
  affinity = comparisonAffinity(pExpr);

  #define sqlite3EndBenignMalloc()
#endif

#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 *);
  int sqlite3JournalExists(sqlite3_file *p);
#else

** The current value for the constraint is left in register iReg.
**
** 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 ){
    iReg = iTarget;
    sqlite3VdbeAddOp2(v, OP_Null, 0, iReg);

    ){
      testcase( iEq==0 );
      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;
    sqlite3VdbeAddOp2(v, bRev ? OP_Last : OP_Rewind, iTab, 0);
    assert( (pLoop->wsFlags & WHERE_MULTI_OR)==0 );

** In the example above, the index on t1(a) has TEXT affinity. But since
** the right hand side of the equality constraint (t2.b) has NONE affinity,
** 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 */
  int regBase;                  /* Base register */
  int nReg;                     /* Number of registers to allocate */

    int r1;
    pTerm = pLoop->aLTerm[j];
    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{
        sqlite3VdbeAddOp2(v, OP_SCopy, r1, regBase+j);
      }

    iReg = sqlite3GetTempRange(pParse, nConstraint+2);
    addrNotFound = pLevel->addrBrk;
    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);
      }
    }
    sqlite3VdbeAddOp2(v, OP_Integer, pLoop->u.vtab.idxNum, iReg);
    sqlite3VdbeAddOp2(v, OP_Integer, nConstraint, iReg+1);

    assert( pLoop->u.btree.nEq==1 );
    iReleaseReg = sqlite3GetTempReg(pParse);
    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);
    VdbeComment((v, "pk"));
    pLevel->op = OP_Noop;

      nExtraReg = 1;
    }

    /* 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
    ** a forward order scan on a descending index, interchange the 
    ** start and end terms (pRangeStart and pRangeEnd).

# Return the number of OpenEphemeral instructions used in the
# 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
# of OpenEphemeral instructions used in the implementation of the
# statement is inserted into the start of the returned list.

} {0}
do_test in5-2.4 {
  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 {
  execsql {
    DROP INDEX t2abc;