SQLite

/*
** A convenience macro that returns the number of elements in
** an array.
*/
#define ArraySize(X)    ((int)(sizeof(X)/sizeof(X[0])))

/*
** Determine if the argument is a power of two
*/
#define IsPowerOfTwo(X) (((X)&((X)-1))==0)

/*
** The following value as a destructor means to use sqlite3DbFree().
** The sqlite3DbFree() routine requires two parameters instead of the 
** one parameter that destructors normally want.  So we have to introduce 
** this magic value that the code knows to handle differently.  Any 
** pointer will work here as long as it is distinct from SQLITE_STATIC
** and SQLITE_TRANSIENT.

#define SQLITE_GroupByOrder   0x0004   /* GROUPBY cover of ORDERBY */
#define SQLITE_FactorOutConst 0x0008   /* Constant factoring */
#define SQLITE_IdxRealAsInt   0x0010   /* Store REAL as INT in indices */
#define SQLITE_DistinctOpt    0x0020   /* DISTINCT using indexes */
#define SQLITE_CoverIdxScan   0x0040   /* Covering index scans */
#define SQLITE_OrderByIdxJoin 0x0080   /* ORDER BY of joins via index */
#define SQLITE_SubqCoroutine  0x0100   /* Evaluate subqueries as coroutines */
#define SQLITE_Transitive     0x0200   /* Transitive constraints */
#define SQLITE_AllOpts        0xffff   /* All optimizations */

/*
** Macros for testing whether or not optimizations are enabled or disabled.
*/
#ifndef SQLITE_OMIT_BUILTIN_TEST
#define OptimizationDisabled(db, mask)  (((db)->dbOptFlags&(mask))!=0)

typedef struct WhereTerm WhereTerm;
struct WhereTerm {
  Expr *pExpr;            /* Pointer to the subexpression that is this term */
  int iParent;            /* Disable pWC->a[iParent] when this term disabled */
  int leftCursor;         /* Cursor number of X in "X <op> <expr>" */
  union {
    int leftColumn;         /* Column number of X in "X <op> <expr>" */
    WhereOrInfo *pOrInfo;   /* Extra information if (eOperator & WO_OR)!=0 */
    WhereAndInfo *pAndInfo; /* Extra information if (eOperator& WO_AND)!=0 */
  } u;
  u16 eOperator;          /* A WO_xx value describing <op> */
  u8 wtFlags;             /* TERM_xxx bit flags.  See below */
  u8 nChild;              /* Number of children that must disable us */
  WhereClause *pWC;       /* The clause this term is part of */
  Bitmask prereqRight;    /* Bitmask of tables used by pExpr->pRight */
  Bitmask prereqAll;      /* Bitmask of tables referenced by pExpr */

#define WO_LE     (WO_EQ<<(TK_LE-TK_EQ))
#define WO_GT     (WO_EQ<<(TK_GT-TK_EQ))
#define WO_GE     (WO_EQ<<(TK_GE-TK_EQ))
#define WO_MATCH  0x040
#define WO_ISNULL 0x080
#define WO_OR     0x100       /* Two or more OR-connected terms */
#define WO_AND    0x200       /* Two or more AND-connected terms */
#define WO_EQUIV  0x400       /* Of the form A==B, both columns */
#define WO_NOOP   0x800       /* This term does not restrict search space */

#define WO_ALL    0xfff       /* Mask of all possible WO_* values */
#define WO_SINGLE 0x0ff       /* Mask of all non-compound WO_* values */

/*
** Value for wsFlags returned by bestIndex() and stored in

}

/*
** Search for a term in the WHERE clause that is of the form "X <op> <expr>"
** where X is a reference to the iColumn of table iCur and <op> is one of
** the WO_xx operator codes specified by the op parameter.
** Return a pointer to the term.  Return 0 if not found.
**
** The term returned might by Y=<expr> if there is another constraint in
** the WHERE clause that specifies that X=Y.  Any such constraints will be
** identified by the WO_EQUIV bit in the pTerm->eOperator field.  The
** aEquiv[] array holds X and all its equivalents, with each SQL variable
** taking up two slots in aEquiv[].  The first slot is for the cursor number
** and the second is for the column number.  There are 22 slots in aEquiv[]
** so that means we can look for X plus up to 10 other equivalent values.
** Hence a search for X will return <expr> if X=A1 and A1=A2 and A2=A3
** and ... and A9=A10 and A10=<expr>.
**
** If there are multiple terms in the WHERE clause of the form "X <op> <expr>"
** then try for the one with no dependencies on <expr> - in other words where
** <expr> is a constant expression of some kind.  Only return entries of
** the form "X <op> Y" where Y is a column in another table if no terms of
** the form "X <op> <const-expr>" exist.  Other than this priority, if there
** are two or more terms that match, then the choice of which term to return
** is arbitrary.
*/
static WhereTerm *findTerm(
  WhereClause *pWC,     /* The WHERE clause to be searched */
  int iCur,             /* Cursor number of LHS */
  int iColumn,          /* Column number of LHS */
  Bitmask notReady,     /* RHS must not overlap with this mask */
  u32 op,               /* Mask of WO_xx values describing operator */
  Index *pIdx           /* Must be compatible with this index, if not NULL */
){
  WhereTerm *pTerm;            /* Term being examined as possible result */
  WhereTerm *pResult = 0;      /* The answer to return */
  WhereClause *pWCOrig = pWC;  /* Original pWC value */
  int j, k;                    /* Loop counters */
  Expr *pX;                /* Pointer to an expression */
  Parse *pParse;           /* Parsing context */
  int iOrigCol = iColumn;  /* Original value of iColumn */
  int nEquiv = 2;          /* Number of entires in aEquiv[] */
  int iEquiv = 2;          /* Number of entries of aEquiv[] processed so far */
  int aEquiv[22];          /* iCur,iColumn and up to 10 other equivalents */

  assert( iCur>=0 );
  aEquiv[0] = iCur;
  aEquiv[1] = iColumn;
  for(;;){
    for(pWC=pWCOrig; pWC; pWC=pWC->pOuter){
      for(pTerm=pWC->a, k=pWC->nTerm; k; k--, pTerm++){
        if( pTerm->leftCursor==iCur

          && pTerm->u.leftColumn==iColumn
        ){
          if( (pTerm->prereqRight & notReady)==0
           && (pTerm->eOperator & op & WO_ALL)!=0
          ){
            if( iOrigCol>=0 && pIdx && (pTerm->eOperator & WO_ISNULL)==0 ){

              CollSeq *pColl;
              char idxaff;
      
              pX = pTerm->pExpr;
              pParse = pWC->pParse;

              idxaff = pIdx->pTable->aCol[iOrigCol].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);
              if( pColl==0 ) pColl = pParse->db->pDfltColl;
      
              for(j=0; pIdx->aiColumn[j]!=iOrigCol; j++){
                if( NEVER(j>=pIdx->nColumn) ) return 0;
              }
              if( sqlite3StrICmp(pColl->zName, pIdx->azColl[j]) ){
                continue;
              }
            }
            pResult = pTerm;
            if( pTerm->prereqRight==0 ) goto findTerm_success;
          }
          if( (pTerm->eOperator & WO_EQUIV)!=0
           && nEquiv<ArraySize(aEquiv)
          ){
            pX = sqlite3ExprSkipCollate(pTerm->pExpr->pRight);
            assert( pX->op==TK_COLUMN );
            for(j=0; j<nEquiv; j+=2){
              if( aEquiv[j]==pX->iTable && aEquiv[j+1]==pX->iColumn ) break;
            }
            if( j==nEquiv ){
              aEquiv[j] = pX->iTable;
              aEquiv[j+1] = pX->iColumn;
              nEquiv += 2;
            }
          }
        }
      }
    }
    if( iEquiv>=nEquiv ) break;
    iCur = aEquiv[iEquiv++];
    iColumn = aEquiv[iEquiv++];
  }
findTerm_success:
  return pResult;
}

/* Forward reference */
static void exprAnalyze(SrcList*, WhereClause*, int);

/*
** Call exprAnalyze on all terms in a WHERE clause.  

  ** Compute the set of tables that might satisfy cases 1 or 2.
  */
  indexable = ~(Bitmask)0;
  chngToIN = ~(pWC->vmask);
  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;
      pAndInfo = sqlite3DbMallocRaw(db, sizeof(*pAndInfo));
      if( pAndInfo ){
        WhereClause *pAndWC;
        WhereTerm *pAndTerm;
        int j;

      Bitmask b;
      b = getMask(pMaskSet, pOrTerm->leftCursor);
      if( pOrTerm->wtFlags & TERM_VIRTUAL ){
        WhereTerm *pOther = &pOrWc->a[pOrTerm->iParent];
        b |= getMask(pMaskSet, pOther->leftCursor);
      }
      indexable &= b;
      if( (pOrTerm->eOperator & WO_EQ)==0 ){
        chngToIN = 0;
      }else{
        chngToIN &= b;
      }
    }
  }

    ** will be recorded in iCursor and iColumn.  There might not be any
    ** such table and column.  Set okToChngToIN if an appropriate table
    ** and column is found but leave okToChngToIN false if not found.
    */
    for(j=0; j<2 && !okToChngToIN; j++){
      pOrTerm = pOrWc->a;
      for(i=pOrWc->nTerm-1; i>=0; i--, pOrTerm++){
        assert( pOrTerm->eOperator & WO_EQ );
        pOrTerm->wtFlags &= ~TERM_OR_OK;
        if( pOrTerm->leftCursor==iCursor ){
          /* This is the 2-bit case and we are on the second iteration and
          ** current term is from the first iteration.  So skip this term. */
          assert( j==1 );
          continue;
        }

        iCursor = pOrTerm->leftCursor;
        break;
      }
      if( i<0 ){
        /* No candidate table+column was found.  This can only occur
        ** on the second iteration */
        assert( j==1 );
        assert( IsPowerOfTwo(chngToIN) );
        assert( chngToIN==getMask(pMaskSet, iCursor) );
        break;
      }
      testcase( j==1 );

      /* We have found a candidate table and column.  Check to see if that
      ** table and column is common to every term in the OR clause */
      okToChngToIN = 1;
      for(; i>=0 && okToChngToIN; i--, pOrTerm++){
        assert( pOrTerm->eOperator & WO_EQ );
        if( pOrTerm->leftCursor!=iCursor ){
          pOrTerm->wtFlags &= ~TERM_OR_OK;
        }else if( pOrTerm->u.leftColumn!=iColumn ){
          okToChngToIN = 0;
        }else{
          int affLeft, affRight;
          /* If the right-hand side is also a column, then the affinities

      Expr *pDup;            /* A transient duplicate expression */
      ExprList *pList = 0;   /* The RHS of the IN operator */
      Expr *pLeft = 0;       /* The LHS of the IN operator */
      Expr *pNew;            /* The complete IN operator */

      for(i=pOrWc->nTerm-1, pOrTerm=pOrWc->a; i>=0; i--, pOrTerm++){
        if( (pOrTerm->wtFlags & TERM_OR_OK)==0 ) continue;
        assert( pOrTerm->eOperator & WO_EQ );
        assert( pOrTerm->leftCursor==iCursor );
        assert( pOrTerm->u.leftColumn==iColumn );
        pDup = sqlite3ExprDup(db, pOrTerm->pExpr->pRight, 0);
        pList = sqlite3ExprListAppend(pWC->pParse, pList, pDup);
        pLeft = pOrTerm->pExpr->pLeft;
      }
      assert( pLeft!=0 );

        sqlite3ExprListDelete(db, pList);
      }
      pTerm->eOperator = WO_NOOP;  /* case 1 trumps case 2 */
    }
  }
}
#endif /* !SQLITE_OMIT_OR_OPTIMIZATION && !SQLITE_OMIT_SUBQUERY */


/*
** The input to this routine is an WhereTerm structure with only the
** "pExpr" field filled in.  The job of this routine is to analyze the
** subexpression and populate all the other fields of the WhereTerm
** structure.
**

    extraRight = x-1;  /* ON clause terms may not be used with an index
                       ** on left table of a LEFT JOIN.  Ticket #3015 */
  }
  pTerm->prereqAll = prereqAll;
  pTerm->leftCursor = -1;
  pTerm->iParent = -1;
  pTerm->eOperator = 0;
  if( allowedOp(op) ){
    Expr *pLeft = sqlite3ExprSkipCollate(pExpr->pLeft);
    Expr *pRight = sqlite3ExprSkipCollate(pExpr->pRight);
    u16 opMask = (pTerm->prereqRight & prereqLeft)==0 ? WO_ALL : WO_EQUIV;
    if( pLeft->op==TK_COLUMN ){
      pTerm->leftCursor = pLeft->iTable;
      pTerm->u.leftColumn = pLeft->iColumn;
      pTerm->eOperator = operatorMask(op) & opMask;
    }
    if( pRight && pRight->op==TK_COLUMN ){
      WhereTerm *pNew;
      Expr *pDup;
      u16 eExtraOp = 0;        /* Extra bits for pNew->eOperator */
      if( pTerm->leftCursor>=0 ){
        int idxNew;
        pDup = sqlite3ExprDup(db, pExpr, 0);
        if( db->mallocFailed ){
          sqlite3ExprDelete(db, pDup);
          return;
        }
        idxNew = whereClauseInsert(pWC, pDup, TERM_VIRTUAL|TERM_DYNAMIC);
        if( idxNew==0 ) return;
        pNew = &pWC->a[idxNew];
        pNew->iParent = idxTerm;
        pTerm = &pWC->a[idxTerm];
        pTerm->nChild = 1;
        pTerm->wtFlags |= TERM_COPIED;
        if( pExpr->op==TK_EQ
         && !ExprHasProperty(pExpr, EP_FromJoin)
         && OptimizationEnabled(db, SQLITE_Transitive)
        ){
          pTerm->eOperator |= WO_EQUIV;
          eExtraOp = WO_EQUIV;
        }
      }else{
        pDup = pExpr;
        pNew = pTerm;
      }
      exprCommute(pParse, pDup);
      pLeft = sqlite3ExprSkipCollate(pDup->pLeft);
      pNew->leftCursor = pLeft->iTable;
      pNew->u.leftColumn = pLeft->iColumn;
      testcase( (prereqLeft | extraRight) != prereqLeft );
      pNew->prereqRight = prereqLeft | extraRight;
      pNew->prereqAll = prereqAll;
      pNew->eOperator = (operatorMask(pDup->op) + eExtraOp) & opMask;
    }
  }

#ifndef SQLITE_OMIT_BETWEEN_OPTIMIZATION
  /* If a term is the BETWEEN operator, create two new virtual terms
  ** that define the range that the BETWEEN implements.  For example:
  **

  }
  if( pWC->wctrlFlags & WHERE_AND_ONLY ){
    return;
  }

  /* Search the WHERE clause terms for a usable WO_OR term. */
  for(pTerm=pWC->a; pTerm<pWCEnd; pTerm++){
    if( (pTerm->eOperator & WO_OR)!=0
     && ((pTerm->prereqAll & ~maskSrc) & p->notReady)==0
     && (pTerm->u.pOrInfo->indexable & maskSrc)!=0 
    ){
      WhereClause * const pOrWC = &pTerm->u.pOrInfo->wc;
      WhereTerm * const pOrWCEnd = &pOrWC->a[pOrWC->nTerm];
      WhereTerm *pOrTerm;
      int flags = WHERE_MULTI_OR;
      double rTotal = 0;
      double nRow = 0;
      Bitmask used = 0;
      WhereBestIdx sBOI;

      sBOI = *p;
      sBOI.pOrderBy = 0;
      sBOI.pDistinct = 0;
      sBOI.ppIdxInfo = 0;
      for(pOrTerm=pOrWC->a; pOrTerm<pOrWCEnd; pOrTerm++){
        WHERETRACE(("... Multi-index OR testing for term %d of %d....\n", 
          (pOrTerm - pOrWC->a), (pTerm - pWC->a)
        ));
        if( (pOrTerm->eOperator& WO_AND)!=0 ){
          sBOI.pWC = &pOrTerm->u.pAndInfo->wc;
          bestIndex(&sBOI);
        }else if( pOrTerm->leftCursor==iCur ){
          WhereClause tempWC;
          tempWC.pParse = pWC->pParse;
          tempWC.pMaskSet = pWC->pMaskSet;
          tempWC.pOuter = pWC;

static int termCanDriveIndex(
  WhereTerm *pTerm,              /* WHERE clause term to check */
  struct SrcList_item *pSrc,     /* Table we are trying to access */
  Bitmask notReady               /* Tables in outer loops of the join */
){
  char aff;
  if( pTerm->leftCursor!=pSrc->iCursor ) return 0;
  if( (pTerm->eOperator & WO_EQ)==0 ) return 0;
  if( (pTerm->prereqRight & notReady)!=0 ) return 0;
  aff = pSrc->pTab->aCol[pTerm->u.leftColumn].affinity;
  if( !sqlite3IndexAffinityOk(pTerm->pExpr, aff) ) return 0;
  return 1;
}
#endif

  WHERETRACE(("Recomputing index info for %s...\n", pSrc->pTab->zName));

  /* Count the number of possible WHERE clause constraints referring
  ** to this virtual table */
  for(i=nTerm=0, pTerm=pWC->a; i<pWC->nTerm; i++, pTerm++){
    if( pTerm->leftCursor != pSrc->iCursor ) continue;
    assert( IsPowerOfTwo(pTerm->eOperator & ~WO_EQUIV) );
    testcase( pTerm->eOperator & WO_IN );
    testcase( pTerm->eOperator & WO_ISNULL );
    if( pTerm->eOperator & (WO_ISNULL) ) continue;
    if( pTerm->wtFlags & TERM_VNULL ) continue;
    nTerm++;
  }

  /* If the ORDER BY clause contains only columns in the current 
  ** virtual table then allocate space for the aOrderBy part of

  *(struct sqlite3_index_orderby**)&pIdxInfo->aOrderBy = pIdxOrderBy;
  *(struct sqlite3_index_constraint_usage**)&pIdxInfo->aConstraintUsage =
                                                                   pUsage;

  for(i=j=0, pTerm=pWC->a; i<pWC->nTerm; i++, pTerm++){
    u8 op;
    if( pTerm->leftCursor != pSrc->iCursor ) continue;
    assert( IsPowerOfTwo(pTerm->eOperator & ~WO_EQUIV) );
    testcase( pTerm->eOperator & WO_IN );
    testcase( pTerm->eOperator & WO_ISNULL );
    if( pTerm->eOperator & (WO_ISNULL) ) continue;
    if( pTerm->wtFlags & TERM_VNULL ) continue;
    pIdxCons[j].iColumn = pTerm->u.leftColumn;
    pIdxCons[j].iTermOffset = i;
    op = (u8)pTerm->eOperator & WO_ALL;
    if( op==WO_IN ) op = WO_EQ;
    pIdxCons[j].op = op;
    /* The direct assignment in the previous line is possible only because
    ** the WO_ and SQLITE_INDEX_CONSTRAINT_ codes are identical.  The
    ** following asserts verify this fact. */
    assert( WO_EQ==SQLITE_INDEX_CONSTRAINT_EQ );
    assert( WO_LT==SQLITE_INDEX_CONSTRAINT_LT );

    */
    pIdxCons = *(struct sqlite3_index_constraint**)&pIdxInfo->aConstraint;
    pUsage = pIdxInfo->aConstraintUsage;
    for(i=0; i<pIdxInfo->nConstraint; i++, pIdxCons++){
      j = pIdxCons->iTermOffset;
      pTerm = &pWC->a[j];
      if( (pTerm->prereqRight&p->notReady)==0
       && (bAllowIN || (pTerm->eOperator & WO_IN)==0)
      ){
        pIdxCons->usable = 1;
      }else{
        pIdxCons->usable = 0;
      }
    }
    memset(pUsage, 0, sizeof(pUsage[0])*pIdxInfo->nConstraint);

  
    pIdxCons = *(struct sqlite3_index_constraint**)&pIdxInfo->aConstraint;
    for(i=0; i<pIdxInfo->nConstraint; 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;
        }
      }

    tRowcnt iUpper = p->aiRowEst[0];
    tRowcnt a[2];
    u8 aff = p->pTable->aCol[p->aiColumn[0]].affinity;

    if( pLower ){
      Expr *pExpr = pLower->pExpr->pRight;
      rc = valueFromExpr(pParse, pExpr, aff, &pRangeVal);
      assert( (pLower->eOperator & (WO_GT|WO_GE))!=0 );
      if( rc==SQLITE_OK
       && whereKeyStats(pParse, p, pRangeVal, 0, a)==SQLITE_OK
      ){
        iLower = a[0];
        if( (pLower->eOperator & WO_GT)!=0 ) iLower += a[1];
      }
      sqlite3ValueFree(pRangeVal);
    }
    if( rc==SQLITE_OK && pUpper ){
      Expr *pExpr = pUpper->pExpr->pRight;
      rc = valueFromExpr(pParse, pExpr, aff, &pRangeVal);
      assert( (pUpper->eOperator & (WO_LT|WO_LE))!=0 );
      if( rc==SQLITE_OK
       && whereKeyStats(pParse, p, pRangeVal, 1, a)==SQLITE_OK
      ){
        iUpper = a[0];
        if( (pUpper->eOperator & WO_LE)!=0 ) iUpper += a[1];
      }
      sqlite3ValueFree(pRangeVal);
    }
    if( rc==SQLITE_OK ){
      if( iUpper<=iLower ){
        *pRangeDiv = (double)p->aiRowEst[0];
      }else{

    /* If X is the column in the index and ORDER BY clause, check to see
    ** if there are any X= or X IS NULL constraints in the WHERE clause. */
    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;
    }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 */
    }else{
      Expr *pRight = pConstraint->pExpr->pRight;
      if( pRight->op==TK_COLUMN ){

    ** to get a better estimate on the number of rows based on
    ** VALUE and how common that value is according to the histogram.
    */
    if( pc.plan.nRow>(double)1 && pc.plan.nEq==1
     && pFirstTerm!=0 && aiRowEst[1]>1 ){
      assert( (pFirstTerm->eOperator & (WO_EQ|WO_ISNULL|WO_IN))!=0 );
      if( pFirstTerm->eOperator & (WO_EQ|WO_ISNULL) ){
        testcase( pFirstTerm->eOperator & WO_EQ );
        testcase( pFirstTerm->eOperator & WO_EQUIV );
        testcase( pFirstTerm->eOperator & WO_ISNULL );
        whereEqualScanEst(pParse, pProbe, pFirstTerm->pExpr->pRight,
                          &pc.plan.nRow);
      }else if( bInEst==0 ){
        assert( pFirstTerm->eOperator & WO_IN );
        whereInScanEst(pParse, pProbe, pFirstTerm->pExpr->x.pList,
                       &pc.plan.nRow);
      }
    }
#endif /* SQLITE_ENABLE_STAT3 */

    /* Adjust the number of output rows and downward to reflect rows

            ** set size by a factor of 3.  Indexed range constraints reduce
            ** the search space by a larger factor: 4.  We make indexed range
            ** more selective intentionally because of the subjective 
            ** observation that indexed range constraints really are more
            ** selective in practice, on average. */
            pc.plan.nRow /= 3;
          }
        }else if( (pTerm->eOperator & WO_NOOP)==0 ){
          /* Any other expression lowers the output row count by half */
          pc.plan.nRow /= 2;
        }
      }
      if( pc.plan.nRow<2 ) pc.plan.nRow = 2;
    }

    **          we reference multiple rows using a "rowid IN (...)"
    **          construct.
    */
    iReleaseReg = sqlite3GetTempReg(pParse);
    pTerm = findTerm(pWC, iCur, -1, notReady, WO_EQ|WO_IN, 0);
    assert( pTerm!=0 );
    assert( pTerm->pExpr!=0 );

    assert( omitTable==0 );
    testcase( pTerm->wtFlags & TERM_VIRTUAL ); /* EV: R-30575-11662 */
    iRowidReg = codeEqualityTerm(pParse, pTerm, pLevel, iReleaseReg);
    addrNxt = pLevel->addrNxt;
    sqlite3VdbeAddOp2(v, OP_MustBeInt, iRowidReg, addrNxt);
    sqlite3VdbeAddOp3(v, OP_NotExists, iCur, addrNxt, iRowidReg);
    sqlite3ExprCacheStore(pParse, iCur, -1, iRowidReg);

    int iRetInit;                             /* Address of regReturn init */
    int untestedTerms = 0;             /* Some terms not completely tested */
    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 );
    pOrWc = &pTerm->u.pOrInfo->wc;
    pLevel->op = OP_Return;
    pLevel->p1 = regReturn;

    /* Set up a new SrcList in pOrTab containing the table being scanned
    ** by this loop in the a[0] slot and all notReady tables in a[1..] slots.

      if( pAndExpr ){
        pAndExpr = sqlite3PExpr(pParse, TK_AND, 0, pAndExpr, 0);
      }
    }

    for(ii=0; ii<pOrWc->nTerm; ii++){
      WhereTerm *pOrTerm = &pOrWc->a[ii];
      if( pOrTerm->leftCursor==iCur || (pOrTerm->eOperator & WO_AND)!=0 ){
        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. */

  CREATE TABLE t5(a, b, c);
  EXPLAIN QUERY PLAN SELECT a FROM t5 WHERE b=10 ORDER BY c;
} {
  0 0 0 {SCAN TABLE t5 (~100000 rows)} 
  0 0 0 {USE TEMP B-TREE FOR ORDER BY}
}

# The following checks a performance issue reported on the sqlite-dev
# mailing list on 2013-01-10
#
do_execsql_test autoindex1-800 {
  CREATE TABLE accounts(
    _id INTEGER PRIMARY KEY AUTOINCREMENT,
    account_name TEXT,
    account_type TEXT,
    data_set TEXT
  );
  CREATE TABLE data(
    _id INTEGER PRIMARY KEY AUTOINCREMENT,
    package_id INTEGER REFERENCES package(_id),
    mimetype_id INTEGER REFERENCES mimetype(_id) NOT NULL,
    raw_contact_id INTEGER REFERENCES raw_contacts(_id) NOT NULL,
    is_read_only INTEGER NOT NULL DEFAULT 0,
    is_primary INTEGER NOT NULL DEFAULT 0,
    is_super_primary INTEGER NOT NULL DEFAULT 0,
    data_version INTEGER NOT NULL DEFAULT 0,
    data1 TEXT,
    data2 TEXT,
    data3 TEXT,
    data4 TEXT,
    data5 TEXT,
    data6 TEXT,
    data7 TEXT,
    data8 TEXT,
    data9 TEXT,
    data10 TEXT,
    data11 TEXT,
    data12 TEXT,
    data13 TEXT,
    data14 TEXT,
    data15 TEXT,
    data_sync1 TEXT,
    data_sync2 TEXT,
    data_sync3 TEXT,
    data_sync4 TEXT 
  );
  CREATE TABLE mimetypes(
    _id INTEGER PRIMARY KEY AUTOINCREMENT,
    mimetype TEXT NOT NULL
  );
  CREATE TABLE raw_contacts(
    _id INTEGER PRIMARY KEY AUTOINCREMENT,
    account_id INTEGER REFERENCES accounts(_id),
    sourceid TEXT,
    raw_contact_is_read_only INTEGER NOT NULL DEFAULT 0,
    version INTEGER NOT NULL DEFAULT 1,
    dirty INTEGER NOT NULL DEFAULT 0,
    deleted INTEGER NOT NULL DEFAULT 0,
    contact_id INTEGER REFERENCES contacts(_id),
    aggregation_mode INTEGER NOT NULL DEFAULT 0,
    aggregation_needed INTEGER NOT NULL DEFAULT 1,
    custom_ringtone TEXT,
    send_to_voicemail INTEGER NOT NULL DEFAULT 0,
    times_contacted INTEGER NOT NULL DEFAULT 0,
    last_time_contacted INTEGER,
    starred INTEGER NOT NULL DEFAULT 0,
    display_name TEXT,
    display_name_alt TEXT,
    display_name_source INTEGER NOT NULL DEFAULT 0,
    phonetic_name TEXT,
    phonetic_name_style TEXT,
    sort_key TEXT,
    sort_key_alt TEXT,
    name_verified INTEGER NOT NULL DEFAULT 0,
    sync1 TEXT,
    sync2 TEXT,
    sync3 TEXT,
    sync4 TEXT,
    sync_uid TEXT,
    sync_version INTEGER NOT NULL DEFAULT 1,
    has_calendar_event INTEGER NOT NULL DEFAULT 0,
    modified_time INTEGER,
    is_restricted INTEGER DEFAULT 0,
    yp_source TEXT,
    method_selected INTEGER DEFAULT 0,
    custom_vibration_type INTEGER DEFAULT 0,
    custom_ringtone_path TEXT,
    message_notification TEXT,
    message_notification_path TEXT
  );
  CREATE INDEX data_mimetype_data1_index ON data (mimetype_id,data1);
  CREATE INDEX data_raw_contact_id ON data (raw_contact_id);
  CREATE UNIQUE INDEX mime_type ON mimetypes (mimetype);
  CREATE INDEX raw_contact_sort_key1_index ON raw_contacts (sort_key);
  CREATE INDEX raw_contact_sort_key2_index ON raw_contacts (sort_key_alt);
  CREATE INDEX raw_contacts_contact_id_index ON raw_contacts (contact_id);
  CREATE INDEX raw_contacts_source_id_account_id_index
      ON raw_contacts (sourceid, account_id);
  ANALYZE sqlite_master;
  INSERT INTO sqlite_stat1
     VALUES('raw_contacts','raw_contact_sort_key2_index','1600 4');
  INSERT INTO sqlite_stat1
     VALUES('raw_contacts','raw_contact_sort_key1_index','1600 4');
  INSERT INTO sqlite_stat1
     VALUES('raw_contacts','raw_contacts_source_id_account_id_index',
            '1600 1600 1600');
  INSERT INTO sqlite_stat1
     VALUES('raw_contacts','raw_contacts_contact_id_index','1600 1');
  INSERT INTO sqlite_stat1 VALUES('mimetypes','mime_type','12 1');
  INSERT INTO sqlite_stat1
     VALUES('data','data_mimetype_data1_index','9819 2455 3');
  INSERT INTO sqlite_stat1 VALUES('data','data_raw_contact_id','9819 7');
  INSERT INTO sqlite_stat1 VALUES('accounts',NULL,'1');
  DROP TABLE IF EXISTS sqlite_stat3;
  ANALYZE sqlite_master;
  
  EXPLAIN QUERY PLAN
  SELECT * FROM 
        data JOIN mimetypes ON (data.mimetype_id=mimetypes._id) 
             JOIN raw_contacts ON (data.raw_contact_id=raw_contacts._id) 
             JOIN accounts ON (raw_contacts.account_id=accounts._id)
   WHERE mimetype_id=10 AND data14 IS NOT NULL;
} {/SEARCH TABLE data .*SEARCH TABLE raw_contacts/}
do_execsql_test autoindex1-801 {
  EXPLAIN QUERY PLAN
  SELECT * FROM 
        data JOIN mimetypes ON (data.mimetype_id=mimetypes._id) 
             JOIN raw_contacts ON (data.raw_contact_id=raw_contacts._id) 
             JOIN accounts ON (raw_contacts.account_id=accounts._id)
   WHERE mimetypes._id=10 AND data14 IS NOT NULL;
} {/SEARCH TABLE data .*SEARCH TABLE raw_contacts/}

finish_test

# 2013 April 17
#
# The author disclaims copyright to this source code.  In place of
# a legal notice, here is a blessing:
#
#    May you do good and not evil.
#    May you find forgiveness for yourself and forgive others.
#    May you share freely, never taking more than you give.
#
#*************************************************************************
# This file implements regression tests for SQLite library.  The
# focus of this script is testing of transitive WHERE clause constraints
#

set testdir [file dirname $argv0]
source $testdir/tester.tcl

do_execsql_test transitive1-100 {
  CREATE TABLE t1(a TEXT, b TEXT, c TEXT COLLATE NOCASE);
  INSERT INTO t1 VALUES('abc','abc','Abc');
  INSERT INTO t1 VALUES('def','def','def');
  INSERT INTO t1 VALUES('ghi','ghi','GHI');
  CREATE INDEX t1a1 ON t1(a);
  CREATE INDEX t1a2 ON t1(a COLLATE nocase);

  SELECT * FROM t1 WHERE a=b AND c=b AND c='DEF';
} {def def def}
do_execsql_test transitive1-110 {
  SELECT * FROM t1 WHERE a=b AND c=b AND c>='DEF' ORDER BY +a;
} {def def def ghi ghi GHI}
do_execsql_test transitive1-120 {
  SELECT * FROM t1 WHERE a=b AND c=b AND c<='DEF' ORDER BY +a;
} {abc abc Abc def def def}

do_execsql_test transitive1-200 {
  CREATE TABLE t2(a INTEGER, b INTEGER, c TEXT);
  INSERT INTO t2 VALUES(100,100,100);
  INSERT INTO t2 VALUES(20,20,20);
  INSERT INTO t2 VALUES(3,3,3);

  SELECT * FROM t2 WHERE a=b AND c=b AND c=20;
} {20 20 20}
do_execsql_test transitive1-210 {
  SELECT * FROM t2 WHERE a=b AND c=b AND c>=20 ORDER BY +a;
} {3 3 3 20 20 20}
do_execsql_test transitive1-220 {
  SELECT * FROM t2 WHERE a=b AND c=b AND c<=20 ORDER BY +a;
} {20 20 20 100 100 100}

finish_test