SQLite

    *piEst = 11;
  }else{
    *piEst = 33;
  }
  return rc;
}

#ifdef SQLITE_ENABLE_STAT2
/*
** Estimate the number of rows that will be returned based on
** an equality constraint x=VALUE and where that VALUE occurs in
** the histogram data.  This only works when x is the left-most
** column of an index and sqlite_stat2 histogram data is available
** for that index.
**
** Write the estimated row count into *pnRow.  If unable to make
** an estimate, leave *pnRow unchanged.
*/
void whereEqScanEst(
  Parse *pParse,       /* Parsing & code generating context */
  Index *p,            /* The index whose left-most column is pTerm */
  WhereTerm *pTerm,    /* The x=VALUE constraint */
  double *pnRow        /* Write the revised row estimate here */
){
  sqlite3_value *pRhs = 0;  /* VALUE on right-hand side of pTerm */
  int iLower, iUpper;       /* Range of histogram regions containing pRhs */
  u8 aff;                   /* Column affinity */
  int rc;                   /* Subfunction return code */
  double nRowEst;           /* New estimate of the number of rows */

  assert( p->aSample!=0 );
  assert( pTerm->eOperator==WO_EQ );
  aff = p->pTable->aCol[p->aiColumn[0]].affinity;
  rc = valueFromExpr(pParse, pTerm->pExpr->pRight, aff, &pRhs);
  if( rc ) goto whereEqScanEst_cancel;
  rc = whereRangeRegion(pParse, p, pRhs, 0, &iLower);
  if( rc ) goto whereEqScanEst_cancel;
  rc = whereRangeRegion(pParse, p, pRhs, 1, &iUpper);
  if( rc ) goto whereEqScanEst_cancel;
  if( iLower>=iUpper ){
    nRowEst = p->aiRowEst[0]/(SQLITE_INDEX_SAMPLES*2);
    if( nRowEst<*pnRow ) *pnRow = nRowEst;
  }else{
    nRowEst = (iUpper-iLower)*p->aiRowEst[0]/SQLITE_INDEX_SAMPLES;
    *pnRow = nRowEst;
  }

whereEqScanEst_cancel:
  sqlite3ValueFree(pRhs);
}
#endif /* defined(SQLITE_ENABLE_STAT2) */


/*
** Find the query plan for accessing a particular table.  Write the
** best query plan and its cost into the WhereCost object supplied as the
** last parameter.
**
** The lowest cost plan wins.  The cost is an estimate of the amount of

    **             SELECT a, b    FROM tbl WHERE a = 1;
    **             SELECT a, b, c FROM tbl WHERE a = 1;
    */
    int nEq;
    int bInEst = 0;
    int nInMul = 1;
    int estBound = 100;
    int nBound = 0;               /* Number of range constraints seen */
    int bSort = 0;
    int bLookup = 0;
    WhereTerm *pTerm;             /* A single term of the WHERE clause */
#ifdef SQLITE_ENABLE_STAT2
    WhereTerm *pFirstEqTerm = 0;  /* First WO_EQ term */
#endif

    /* Determine the values of nEq and nInMul */
    for(nEq=0; nEq<pProbe->nColumn; nEq++){
      int j = pProbe->aiColumn[nEq];
      pTerm = findTerm(pWC, iCur, j, notReady, eqTermMask, pIdx);
      if( pTerm==0 ) break;
      wsFlags |= (WHERE_COLUMN_EQ|WHERE_ROWID_EQ);
      if( pTerm->eOperator & WO_IN ){
        Expr *pExpr = pTerm->pExpr;
        wsFlags |= WHERE_COLUMN_IN;
        if( ExprHasProperty(pExpr, EP_xIsSelect) ){
          nInMul *= 25;
          bInEst = 1;
        }else if( ALWAYS(pExpr->x.pList) ){
          nInMul *= pExpr->x.pList->nExpr + 1;
        }
      }else if( pTerm->eOperator & WO_ISNULL ){
        wsFlags |= WHERE_COLUMN_NULL;
      }
#ifdef SQLITE_ENABLE_STAT2
      else if( nEq==0 && pProbe->aSample ){
        pFirstEqTerm = pTerm;
      }
#endif
      used |= pTerm->prereqRight;
    }

    /* Determine the value of estBound. */
    if( nEq<pProbe->nColumn ){
      int j = pProbe->aiColumn[nEq];
      if( findTerm(pWC, iCur, j, notReady, WO_LT|WO_LE|WO_GT|WO_GE, pIdx) ){

    */
    nRow = (double)(aiRowEst[nEq] * nInMul);
    if( bInEst && nRow*2>aiRowEst[0] ){
      nRow = aiRowEst[0]/2;
      nInMul = (int)(nRow / aiRowEst[nEq]);
    }

#ifdef SQLITE_ENABLE_STAT2
    /* If the constraint is of the form x=VALUE and histogram
    ** data is available for column x, then it might be possible
    ** to get a better estimate on the number of rows based on
    ** VALUE and how common that value is according to the histogram.
    */
    if( nRow>(double)1 && nEq==1 && pFirstEqTerm!=0 ){
      whereEqScanEst(pParse, pProbe, pFirstEqTerm, &nRow);
    }
#endif /* SQLITE_ENABLE_STAT2 */

    /* Assume constant cost to access a row and logarithmic cost to
    ** do a binary search.  Hence, the initial cost is the number of output
    ** rows plus log2(table-size) times the number of binary searches.
    */
    cost = nRow + nInMul*estLog(aiRowEst[0]);

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

 16  {y>=0 AND y<=''}                 50
 17  {y>=0 AND y<='alpha'}           400
 18  {y>=0 AND y<'alpha'}             50
 19  {y>=0 AND y<='bravo'}           700
 20  {y>=0 AND y<'charlie'}          700
 21  {y>=0 AND y<='charlie'}         900
 22  {y>=0 AND y<'delta'}            900
 23  {y>'alpha' AND y<x'00'}         600
 24  {y>='bravo' AND y<x'00'}        600
 25  {y>'bravo' AND y<x'00'}         300
 26  {y>='charlie' AND y<x'00'}      300
 27  {y>'charlie' AND y<x'00'}       100
 28  {y>='delta' AND y<x'00'}        100
 29  {y>'delta' AND y<x'00'}          50
 30  {y>='echo' AND y<x'00'}          50
} {
  do_test analyze5-3.$testid {
    eqp "SELECT * FROM t1 WHERE $where"
  } [format {0 0 0 {SEARCH TABLE t1 USING INDEX t1y (y>? AND y<?) (~%d rows)}} \
       $rows]
}