SQLite

          pSample = allocIndexSample(db, &pIdx->comkey, pIdx->comkey.n);
        }else{
          pSample = allocIndexSample(db, &pIdx->sample, iSample);
        }
        if( pSample==0 ) break;
        eType = sqlite3_column_type(pStmt, 2);
        pSample->eType = (u8)eType;
        pSample->nCopy = sqlite3_column_int(pStmt, 3);
        if( eType==SQLITE_INTEGER ){
          pSample->u.i = sqlite3_column_int64(pStmt, 2);
        }else if( eType==SQLITE_FLOAT ){
          pSample->u.r = sqlite3_column_double(pStmt, 2);
        }else if( eType==SQLITE_TEXT || eType==SQLITE_BLOB ){
          const char *z = (const char *)(
             (eType==SQLITE_BLOB) ?
              sqlite3_column_blob(pStmt, 2):
              sqlite3_column_text(pStmt, 2)
          );

/*
** Each sample stored in the sqlite_stat2 table is represented in memory 
** using a structure of this type.
*/
struct IndexSample {
  union {
    char *z;        /* Value if eType is SQLITE_TEXT or SQLITE_BLOB */
    double r;       /* Value if eType is SQLITE_FLOAT */
    i64 i;          /* Value if eType is SQLITE_INTEGER */
  } u;
  u8 eType;         /* SQLITE_NULL, SQLITE_INTEGER ... etc. */
  u8 nByte;         /* Size in byte of text or blob. */
  u32 nCopy;        /* How many copies of this sample are in the database */
};

/*

  */
  bestOrClauseIndex(pParse, pWC, pSrc, notReady, notValid, pOrderBy, pCost);
}
#endif /* SQLITE_OMIT_VIRTUALTABLE */

/*
** Argument pIdx is a pointer to an index structure that has an array of
** pIdx->sample.n (hereafter "S") evenly spaced samples of the first indexed
** column stored in Index.sample. These samples divide the domain of values

** stored the index into S+1 regions.  Region 0 contains all values less than
** the first sample value. Region 1 contains values between the first and
** second samples.  Region 2 contains values between samples 2 and 3.  And so
** on.  Region S contains values larger than the last sample.
**
** Note that samples are computed as being centered on S buckets where each
** bucket contains the nearly same number of rows.  This routine takes samples
** to be dividers between regions, though.  Hence, region 0 and region S
** contain half as many rows as the interior regions.
**
** If the index contains many duplicates of a single value, then it is
** possible that two or more adjacent samples can hold the same value.
** When that is the case, the smallest possible region code is returned
** when roundUp is false and the largest possible region code is returned
** when roundUp is true.
**
** If successful, this function determines which of the regions value 
** pVal lies in, sets *piRegion to the region index (a value between 0
** and S, inclusive) and returns SQLITE_OK.
** Or, if an OOM occurs while converting text values between encodings,
** SQLITE_NOMEM is returned and *piRegion is undefined.
*/
#ifdef SQLITE_ENABLE_STAT2
static int whereRangeRegion(
  Parse *pParse,              /* Database connection */
  Index *pIdx,                /* Index to consider domain of */
  sqlite3_value *pVal,        /* Value to consider */
  int roundUp,                /* Return largest valid region if true */
  int *piRegion,              /* OUT: Region of domain in which value lies */
  u32 *pnCopy                 /* OUT: Number of rows with pVal, or -1 if unk */
){
  assert( roundUp==0 || roundUp==1 );
  if( ALWAYS(pVal) ){
    IndexSample *aSample = pIdx->sample.a;
    int nSample = pIdx->sample.n;
    int i = 0;
    int eType = sqlite3_value_type(pVal);

    assert( nSample>0 );
    if( eType==SQLITE_INTEGER ){
      i64 x = sqlite3_value_int64(pVal);
      for(i=0; i<nSample; i++){
        if( aSample[i].eType==SQLITE_NULL ) continue;
        if( aSample[i].eType>=SQLITE_TEXT ) break;
        if( aSample[i].u.i==x ) *pnCopy = aSample[i].nCopy;
        if( roundUp ){
          if( aSample[i].u.i>x ) break;
        }else{
          if( aSample[i].u.i>=x ) break;
        }
      }
    }else if( eType==SQLITE_FLOAT ){
      double r = sqlite3_value_double(pVal);
      for(i=0; i<nSample; i++){
        if( aSample[i].eType==SQLITE_NULL ) continue;
        if( aSample[i].eType>=SQLITE_TEXT ) break;
        if( aSample[i].u.r==r ) *pnCopy = aSample[i].nCopy;
        if( roundUp ){
          if( aSample[i].u.r>r ) break;
        }else{
          if( aSample[i].u.r>=r ) break;
        }
      }
    }else if( eType==SQLITE_NULL ){
      i = 0;
      if( aSample[0].eType==SQLITE_NULL ) *pnCopy = aSample[0].nCopy;
      if( roundUp ){
        while( i<nSample && aSample[i].eType==SQLITE_NULL ) i++;
      }
    }else{ 
      sqlite3 *db = pParse->db;
      CollSeq *pColl;
      const u8 *z;
      int n;


      assert( eType==SQLITE_TEXT || eType==SQLITE_BLOB );

      if( eType==SQLITE_BLOB ){
        z = (const u8 *)sqlite3_value_blob(pVal);
        pColl = db->pDfltColl;
        assert( pColl->enc==SQLITE_UTF8 );
      }else{
        pColl = sqlite3GetCollSeq(db, SQLITE_UTF8, 0, *pIdx->azColl);
        if( pColl==0 ){

          c = pColl->xCmp(pColl->pUser, nSample, zSample, n, z);
          sqlite3DbFree(db, zSample);
        }else
#endif
        {
          c = pColl->xCmp(pColl->pUser, aSample[i].nByte, aSample[i].u.z, n, z);
        }
        if( c==0 ) *pnCopy = aSample[i].nCopy;
        if( c-roundUp>=0 ) break;
      }
    }

    assert( i>=0 && i<=pIdx->sample.n );
    *piRegion = i;
  }

    sqlite3_value *pUpperVal = 0;
    int iEst;
    int iLower = 0;
    int nSample = p->sample.n;
    int iUpper = p->sample.n;
    int roundUpUpper = 0;
    int roundUpLower = 0;
    u32 nC = 0;
    u8 aff = p->pTable->aCol[p->aiColumn[0]].affinity;

    if( pLower ){
      Expr *pExpr = pLower->pExpr->pRight;
      rc = valueFromExpr(pParse, pExpr, aff, &pLowerVal);
      assert( pLower->eOperator==WO_GT || pLower->eOperator==WO_GE );
      roundUpLower = (pLower->eOperator==WO_GT) ?1:0;
    }
    if( rc==SQLITE_OK && pUpper ){
      Expr *pExpr = pUpper->pExpr->pRight;
      rc = valueFromExpr(pParse, pExpr, aff, &pUpperVal);
      assert( pUpper->eOperator==WO_LT || pUpper->eOperator==WO_LE );
      roundUpUpper = (pUpper->eOperator==WO_LE) ?1:0;
    }

    if( rc!=SQLITE_OK || (pLowerVal==0 && pUpperVal==0) ){
      sqlite3ValueFree(pLowerVal);
      sqlite3ValueFree(pUpperVal);
      goto range_est_fallback;
    }else if( pLowerVal==0 ){
      rc = whereRangeRegion(pParse, p, pUpperVal, roundUpUpper, &iUpper, &nC);
      if( pLower ) iLower = iUpper/2;
    }else if( pUpperVal==0 ){
      rc = whereRangeRegion(pParse, p, pLowerVal, roundUpLower, &iLower, &nC);
      if( pUpper ) iUpper = (iLower + p->sample.n + 1)/2;
    }else{
      rc = whereRangeRegion(pParse, p, pUpperVal, roundUpUpper, &iUpper, &nC);
      if( rc==SQLITE_OK ){
        rc = whereRangeRegion(pParse, p, pLowerVal, roundUpLower, &iLower, &nC);
      }
    }
    WHERETRACE(("range scan regions: %d..%d\n", iLower, iUpper));

    iEst = iUpper - iLower;
    testcase( iEst==nSample );
    assert( iEst<=nSample );
    assert( nSample>0 );
    if( iEst<1 ){
      *piEst = 50/nSample;
    }else{

  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 */
  u32 nC = 0;               /* Key copy count */

  assert( p->sample.a!=0 );
  assert( p->sample.n>0 );
  aff = p->pTable->aCol[p->aiColumn[0]].affinity;
  if( pExpr ){
    rc = valueFromExpr(pParse, pExpr, aff, &pRhs);
    if( rc ) goto whereEqualScanEst_cancel;
  }else{
    pRhs = sqlite3ValueNew(pParse->db);
  }
  if( pRhs==0 ) return SQLITE_NOTFOUND;
  rc = whereRangeRegion(pParse, p, pRhs, 0, &iLower, &nC);
  if( rc ) goto whereEqualScanEst_cancel;
  if( nC==0 ){
    rc = whereRangeRegion(pParse, p, pRhs, 1, &iUpper, &nC);
    if( rc ) goto whereEqualScanEst_cancel;
  }
  if( nC ){
    WHERETRACE(("equality scan count: %u\n", nC));
    *pnRow = nC;
  }else{
    WHERETRACE(("equality scan regions: %d..%d\n", iLower, iUpper));
    if( iLower>=iUpper ){
      nRowEst = p->aiRowEst[0]/(p->sample.n*3);
      if( nRowEst<*pnRow ) *pnRow = nRowEst;
    }else{
      nRowEst = (iUpper-iLower)*p->aiRowEst[0]/p->sample.n;
      *pnRow = nRowEst;
    }
  }

whereEqualScanEst_cancel:
  sqlite3ValueFree(pRhs);
  return rc;
}
#endif /* defined(SQLITE_ENABLE_STAT2) */

  u8 aff;                   /* Column affinity */
  int rc = SQLITE_OK;       /* Subfunction return code */
  double nRowEst;           /* New estimate of the number of rows */
  int nSpan = 0;            /* Number of histogram regions spanned */
  int nSingle = 0;          /* Histogram regions hit by a single value */
  int nNotFound = 0;        /* Count of values that are not constants */
  int i;                             /* Loop counter */
  u32 nC;                            /* Exact count of rows for a key */
  int nSample = p->sample.n;         /* Number of samples */
  u8 aSpan[SQLITE_MAX_SAMPLES+1];    /* Histogram regions that are spanned */
  u8 aSingle[SQLITE_MAX_SAMPLES+1];  /* Histogram regions hit once */

  assert( p->sample.a!=0 );
  assert( nSample>0 );
  aff = p->pTable->aCol[p->aiColumn[0]].affinity;
  memset(aSpan, 0, nSample+1);
  memset(aSingle, 0, nSample+1);
  for(i=0; i<pList->nExpr; i++){
    sqlite3ValueFree(pVal);
    rc = valueFromExpr(pParse, pList->a[i].pExpr, aff, &pVal);
    if( rc ) break;
    if( pVal==0 || sqlite3_value_type(pVal)==SQLITE_NULL ){
      nNotFound++;
      continue;
    }
    rc = whereRangeRegion(pParse, p, pVal, 0, &iLower, &nC);
    if( rc ) break;
    rc = whereRangeRegion(pParse, p, pVal, 1, &iUpper, &nC);
    if( rc ) break;
    if( iLower>=iUpper ){
      aSingle[iLower] = 1;
    }else{
      assert( iLower>=0 && iUpper<=nSample );
      while( iLower<iUpper ) aSpan[iLower++] = 1;
    }