SQLite

  WhereClause *pWC;         /* WHERE clause terms */
  ExprList *pOrderBy;       /* ORDER BY clause */
  WhereLoop *pNew;          /* Template WhereLoop */
  WhereOrSet *pOrSet;       /* Record best loops here, if not NULL */
#ifdef SQLITE_ENABLE_STAT4
  UnpackedRecord *pRec;     /* Probe for stat4 (if required) */
  int nRecValid;            /* Number of valid fields currently in pRec */

#endif
};

/*
** The WHERE clause processing routine has two halves.  The
** first part does the start of the WHERE loop and the second
** half does the tail of the WHERE loop.  An instance of

**                    |_____|   |_____|
**                       |         |
**                     pLower    pUpper
**
** If either of the upper or lower bound is not present, then NULL is passed in
** place of the corresponding WhereTerm.
**
** The value in (pBuilder->pNew->u.btree.nEq) is the index of the index
** column subject to the range constraint. Or, equivalently, the number of
** equality constraints optimized by the proposed index scan. For example,
** assuming index p is on t1(a, b), and the SQL query is:
**
**   ... FROM t1 WHERE a = ? AND b > ? AND b < ? ...
**
** then nEq is set to 1 (as the range restricted column, b, is the second 
** left-most column of the index). Or, if the query is:
**
**   ... FROM t1 WHERE a > ? AND a < ? ...
**
** then nEq is set to 0.
**
** When this function is called, *pnOut is set to the whereCost() of the
** number of rows that the index scan is expected to visit without 
** considering the range constraints. If nEq is 0, this is the number of 
** rows in the index. Assuming no error occurs, *pnOut is adjusted (reduced)
** to account for the range contraints pLower and pUpper.
** 
** In the absence of sqlite_stat4 ANALYZE data, or if such data cannot be
** used, each range inequality reduces the search space by a factor of 4. 
** Hence a pair of constraints (x>? AND x<?) reduces the expected number of
** rows visited by a factor of 16.
*/
static int whereRangeScanEst(
  Parse *pParse,       /* Parsing & code generating context */
  WhereLoopBuilder *pBuilder,
  WhereTerm *pLower,   /* Lower bound on the range. ex: "x>123" Might be NULL */
  WhereTerm *pUpper,   /* Upper bound on the range. ex: "x<455" Might be NULL */
  WhereCost *pnOut     /* IN/OUT: Number of rows visited */
){
  int rc = SQLITE_OK;
  int nOut = (int)*pnOut;

#ifdef SQLITE_ENABLE_STAT4
  Index *p = pBuilder->pNew->u.btree.pIndex;
  int nEq = pBuilder->pNew->u.btree.nEq;

  if( nEq==pBuilder->nRecValid 
   && p->nSample 

      ){
        iUpper = a[0];
        if( (pUpper->eOperator & WO_LE)!=0 ) iUpper += a[1];
      }
    }
    pBuilder->pRec = pRec;
    if( rc==SQLITE_OK ){
      WhereCost nNew;
      if( iUpper>iLower ){
        nNew = whereCost(iUpper - iLower);
      }else{
        nNew = whereCost(2);      /* Small number */
      }
      if( nNew<nOut ){


        nOut = nNew;
      }
      *pnOut = (WhereCost)nOut;
      WHERETRACE(0x100, ("range scan regions: %u..%u  est=%d\n",
                         (u32)iLower, (u32)iUpper, nOut));
      return SQLITE_OK;
    }
  }
#else
  UNUSED_PARAMETER(pParse);
  UNUSED_PARAMETER(pBuilder);
#endif
  assert( pLower || pUpper );

  /* TUNING:  Each inequality constraint reduces the search space 4-fold.
  ** A BETWEEN operator, therefore, reduces the search space 16-fold */
  if( pLower && (pLower->wtFlags & TERM_VNULL)==0 ){
    nOut -= 20;        assert( 20==whereCost(4) );
  }
  if( pUpper ){
    nOut -= 20;        assert( 20==whereCost(4) );
  }
  if( nOut<10 ) nOut = 10;
  *pnOut = (WhereCost)nOut;
  return rc;
}

#ifdef SQLITE_ENABLE_STAT4
/*
** Estimate the number of rows that will be returned based on
** an equality constraint x=VALUE and where that VALUE occurs in

  if( bOk==0 ) return SQLITE_NOTFOUND;
  pBuilder->nRecValid = nEq;

  rc = whereKeyStats(pParse, p, pRec, 0, a);
  if( rc==SQLITE_OK ){
    WHERETRACE(0x100,("equality scan regions: %d\n", (int)a[1]));
    *pnRow = a[1];



  }
  
  return rc;
}
#endif /* defined(SQLITE_ENABLE_STAT4) */

#ifdef SQLITE_ENABLE_STAT4

    rc = whereEqualScanEst(pParse, pBuilder, pList->a[i].pExpr, &nEst);
    nRowEst += nEst;
    pBuilder->nRecValid = nRecValid;
  }

  if( rc==SQLITE_OK ){
    if( nRowEst > p->aiRowEst[0] ) nRowEst = p->aiRowEst[0];



    *pnRow = nRowEst;

    WHERETRACE(0x100,("IN row estimate: est=%g\n", nRowEst));
  }
  assert( pBuilder->nRecValid==nRecValid );
  return rc;
}
#endif /* defined(SQLITE_ENABLE_STAT4) */

  saved_nOut = pNew->nOut;
  pNew->rSetup = 0;
  rLogSize = estLog(whereCost(pProbe->aiRowEst[0]));
  for(; rc==SQLITE_OK && pTerm!=0; pTerm = whereScanNext(&scan)){
    int nIn = 0;
#ifdef SQLITE_ENABLE_STAT4
    int nRecValid = pBuilder->nRecValid;

    if( (pTerm->wtFlags & TERM_VNULL)!=0 && pSrc->pTab->aCol[iCol].notNull ){
      continue; /* skip IS NOT NULL constraints on a NOT NULL column */
    }
#endif
    if( pTerm->prereqRight & pNew->maskSelf ) continue;

    pNew->wsFlags = saved_wsFlags;

      pNew->wsFlags |= WHERE_COLUMN_RANGE|WHERE_TOP_LIMIT;
      pTop = pTerm;
      pBtm = (pNew->wsFlags & WHERE_BTM_LIMIT)!=0 ?
                     pNew->aLTerm[pNew->nLTerm-2] : 0;
    }
    if( pNew->wsFlags & WHERE_COLUMN_RANGE ){
      /* Adjust nOut and rRun for STAT3 range values */
      assert( pNew->nOut==saved_nOut );
      whereRangeScanEst(pParse, pBuilder, pBtm, pTop, &pNew->nOut);

    }
#ifdef SQLITE_ENABLE_STAT4
    if( nInMul==0 && pProbe->nSample && OptimizationEnabled(db, SQLITE_Stat3) ){
      Expr *pExpr = pTerm->pExpr;
      tRowcnt nOut = 0;
      if( (pTerm->eOperator & (WO_EQ|WO_ISNULL))!=0 ){
        testcase( pTerm->eOperator & WO_EQ );
        testcase( pTerm->eOperator & WO_ISNULL );
        rc = whereEqualScanEst(pParse, pBuilder, pExpr->pRight, &nOut);


      }else if( (pTerm->eOperator & WO_IN)
             &&  !ExprHasProperty(pExpr, EP_xIsSelect)  ){
        rc = whereInScanEst(pParse, pBuilder, pExpr->x.pList, &nOut);
      }
      assert( nOut==0 || rc==SQLITE_OK );
      if( nOut ){
        nOut = whereCost(nOut);
        pNew->nOut = MIN(nOut, saved_nOut);
      }
    }
#endif
    if( (pNew->wsFlags & (WHERE_IDX_ONLY|WHERE_IPK))==0 ){
      /* Each row involves a step of the index, then a binary search of
      ** the main table */
      pNew->rRun =  whereCostAdd(pNew->rRun, rLogSize>27 ? rLogSize-17 : 10);
    }
    /* Step cost for each output row */
    pNew->rRun = whereCostAdd(pNew->rRun, pNew->nOut);
    /* TBD: Adjust nOut for additional constraints */
    rc = whereLoopInsert(pBuilder, pNew);
    if( (pNew->wsFlags & WHERE_TOP_LIMIT)==0
     && pNew->u.btree.nEq<(pProbe->nColumn + (pProbe->zName!=0))
    ){
      whereLoopAddBtreeIndex(pBuilder, pSrc, pProbe, nInMul+nIn);
    }
#ifdef SQLITE_ENABLE_STAT4
    pBuilder->nRecValid = nRecValid;
    pNew->nOut = saved_nOut;
#endif
  }
  pNew->prereq = saved_prereq;
  pNew->u.btree.nEq = saved_nEq;
  pNew->wsFlags = saved_wsFlags;
  pNew->nOut = saved_nOut;
  pNew->nLTerm = saved_nLTerm;

do_test 2.1 {
  eqp {SELECT * FROM t1 WHERE a=100 AND b BETWEEN 50 AND 54}
} {0 0 0 {SEARCH TABLE t1 USING INDEX t1b (b>? AND b<?)}}

# There are many more values of c between 0 and 100000 than there are
# between 800000 and 900000.  So t1c is more selective for the latter
# range.
# 
# Test 3.2 is a little unstable. It depends on the planner estimating
# that (b BETWEEN 40 AND 44) will match more rows than (c BETWEEN
# 800000 AND 900000). Which is a pretty close call (50 vs. 32), so
# the planner could get it wrong with an unlucky set of samples. This
# case happens to work, but others ("b BETWEEN 50 AND 54" for example) 
# will fail.
#
do_execsql_test 3.0 {
  SELECT count(*) FROM t1 WHERE b BETWEEN 40 AND 44;
  SELECT count(*) FROM t1 WHERE c BETWEEN 0 AND 100000;
  SELECT count(*) FROM t1 WHERE c BETWEEN 800000 AND 900000;
} {50 376 32}
do_test 3.1 {
  eqp {SELECT * FROM t1 WHERE b BETWEEN 40 AND 44 AND c BETWEEN 0 AND 100000}
} {0 0 0 {SEARCH TABLE t1 USING INDEX t1b (b>? AND b<?)}}
do_test 3.2 {
  eqp {SELECT * FROM t1
       WHERE b BETWEEN 40 AND 44 AND c BETWEEN 800000 AND 900000}
} {0 0 0 {SEARCH TABLE t1 USING INDEX t1c (c>? AND c<?)}}

do_test 3.3 {
  eqp {SELECT * FROM t1 WHERE a=100 AND c BETWEEN 0 AND 100000}
} {0 0 0 {SEARCH TABLE t1 USING INDEX t1a (a=?)}}
do_test 3.4 {
  eqp {SELECT * FROM t1
       WHERE a=100 AND c BETWEEN 800000 AND 900000}
} {0 0 0 {SEARCH TABLE t1 USING INDEX t1c (c>? AND c<?)}}