SQLite

** list of space separated integers. Read the first nOut of these into
** the array aOut[].
*/
static void decodeIntArray(
  char *zIntArray,       /* String containing int array to decode */
  int nOut,              /* Number of slots in aOut[] */
  tRowcnt *aOut,         /* Store integers here */
  LogEst *aLog,          /* Or, if aOut==0, here */
  Index *pIndex          /* Handle extra flags for this index, if not NULL */
){
  char *z = zIntArray;
  int c;
  int i;
  tRowcnt v;

#ifdef SQLITE_ENABLE_STAT3_OR_STAT4
  if( z==0 ) z = "";
#else
  if( NEVER(z==0) ) z = "";
#endif
  for(i=0; *z && i<nOut; i++){
    v = 0;
    while( (c=z[0])>='0' && c<='9' ){
      v = v*10 + c - '0';
      z++;
    }
    if( aOut ){
      aOut[i] = v;
    }else{
      aLog[i] = sqlite3LogEst(v);
    }
    if( *z==' ' ) z++;
  }
#ifndef SQLITE_ENABLE_STAT3_OR_STAT4
  assert( pIndex!=0 );
#else
  if( pIndex )
#endif

    pIndex = sqlite3PrimaryKeyIndex(pTable);
  }else{
    pIndex = sqlite3FindIndex(pInfo->db, argv[1], pInfo->zDatabase);
  }
  z = argv[2];

  if( pIndex ){
    decodeIntArray((char*)z, pIndex->nKeyCol+1, 0, pIndex->aiRowLogEst, pIndex);
    if( pIndex->pPartIdxWhere==0 ) pTable->nRowLogEst = pIndex->aiRowLogEst[0];
  }else{
    Index fakeIdx;
    fakeIdx.szIdxRow = pTable->szTabRow;
    decodeIntArray((char*)z, 1, 0, &pTable->nRowLogEst, &fakeIdx);
    pTable->szTabRow = fakeIdx.szIdxRow;
  }

  return 0;
}

/*

    nCol = pIdx->nSampleCol;
    if( bStat3 && nCol>1 ) continue;
    if( pIdx!=pPrevIdx ){
      initAvgEq(pPrevIdx);
      pPrevIdx = pIdx;
    }
    pSample = &pIdx->aSample[pIdx->nSample];
    decodeIntArray((char*)sqlite3_column_text(pStmt,1),nCol,pSample->anEq,0,0);
    decodeIntArray((char*)sqlite3_column_text(pStmt,2),nCol,pSample->anLt,0,0);
    decodeIntArray((char*)sqlite3_column_text(pStmt,3),nCol,pSample->anDLt,0,0);

    /* Take a copy of the sample. Add two 0x00 bytes the end of the buffer.
    ** This is in case the sample record is corrupted. In that case, the
    ** sqlite3VdbeRecordCompare() may read up to two varints past the
    ** end of the allocated buffer before it realizes it is dealing with
    ** a corrupt record. Adding the two 0x00 bytes prevents this from causing
    ** a buffer overread.  */

    pParse->nErr++;
    goto begin_table_error;
  }
  pTable->zName = zName;
  pTable->iPKey = -1;
  pTable->pSchema = db->aDb[iDb].pSchema;
  pTable->nRef = 1;
  pTable->nRowLogEst = 200; assert( 200==sqlite3LogEst(1048576) );
  assert( pParse->pNewTable==0 );
  pParse->pNewTable = pTable;

  /* If this is the magic sqlite_sequence table used by autoincrement,
  ** then record a pointer to this table in the main database structure
  ** so that INSERT can find the table easily.
  */

  char **ppExtra       /* Pointer to the "extra" space */
){
  Index *p;            /* Allocated index object */
  int nByte;           /* Bytes of space for Index object + arrays */

  nByte = ROUND8(sizeof(Index)) +              /* Index structure  */
          ROUND8(sizeof(char*)*nCol) +         /* Index.azColl     */
          ROUND8(sizeof(LogEst)*(nCol+1) +     /* Index.aiRowLogEst   */
                 sizeof(i16)*nCol +            /* Index.aiColumn   */
                 sizeof(u8)*nCol);             /* Index.aSortOrder */
  p = sqlite3DbMallocZero(db, nByte + nExtra);
  if( p ){
    char *pExtra = ((char*)p)+ROUND8(sizeof(Index));
    p->azColl = (char**)pExtra;       pExtra += ROUND8(sizeof(char*)*nCol);
    p->aiRowLogEst = (LogEst*)pExtra; pExtra += sizeof(LogEst)*(nCol+1);
    p->aiColumn = (i16*)pExtra;       pExtra += sizeof(i16)*nCol;
    p->aSortOrder = (u8*)pExtra;
    p->nColumn = nCol;
    p->nKeyCol = nCol - 1;
    *ppExtra = ((char*)p) + nByte;
  }
  return p;
}

  nName = sqlite3Strlen30(zName);
  nExtraCol = pPk ? pPk->nKeyCol : 1;
  pIndex = sqlite3AllocateIndexObject(db, pList->nExpr + nExtraCol,
                                      nName + nExtra + 1, &zExtra);
  if( db->mallocFailed ){
    goto exit_create_index;
  }
  assert( EIGHT_BYTE_ALIGNMENT(pIndex->aiRowLogEst) );
  assert( EIGHT_BYTE_ALIGNMENT(pIndex->azColl) );
  pIndex->zName = zExtra;
  zExtra += nName + 1;
  memcpy(pIndex->zName, zName, nName+1);
  pIndex->pTable = pTab;
  pIndex->onError = (u8)onError;
  pIndex->uniqNotNull = onError!=OE_None;

** Fill the Index.aiRowEst[] array with default information - information
** to be used when we have not run the ANALYZE command.
**
** aiRowEst[0] is suppose to contain the number of elements in the index.
** Since we do not know, guess 1 million.  aiRowEst[1] is an estimate of the
** number of rows in the table that match any particular value of the
** first column of the index.  aiRowEst[2] is an estimate of the number
** of rows that match any particular combination of the first 2 columns
** of the index.  And so forth.  It must always be the case that
*
**           aiRowEst[N]<=aiRowEst[N-1]
**           aiRowEst[N]>=1
**
** Apart from that, we have little to go on besides intuition as to
** how aiRowEst[] should be initialized.  The numbers generated here
** are based on typical values found in actual indices.
*/
void sqlite3DefaultRowEst(Index *pIdx){
  /*                10,  9,  8,  7,  6 */
  LogEst aVal[] = { 33, 32, 30, 28, 26 };
  LogEst *a = pIdx->aiRowLogEst;
  int nCopy = MIN(ArraySize(aVal), pIdx->nKeyCol);
  int i;


  /* Set the first entry (number of rows in the index) to the estimated 
  ** number of rows in the table. Or 10, if the estimated number of rows 
  ** in the table is less than that.  */
  a[0] = pIdx->pTable->nRowLogEst;
  if( a[0]<33 ) a[0] = 33;        assert( 33==sqlite3LogEst(10) );

  /* Estimate that a[1] is 10, a[2] is 9, a[3] is 8, a[4] is 7, a[5] is
  ** 6 and each subsequent value (if any) is 5.  */
  memcpy(&a[1], aVal, nCopy*sizeof(LogEst));
  for(i=nCopy+1; i<=pIdx->nKeyCol; i++){
    a[i] = 23;                    assert( 23==sqlite3LogEst(5) );

  }



  assert( 0==sqlite3LogEst(1) );
  if( pIdx->onError!=OE_None ) a[pIdx->nKeyCol] = 0;
}

/*
** This routine will drop an existing named index.  This routine
** implements the DROP INDEX statement.
*/
void sqlite3DropIndex(Parse *pParse, SrcList *pName, int ifExists){

    sqlite3VdbeSetColName(v, 3, COLNAME_NAME, "height", SQLITE_STATIC);
    for(i=sqliteHashFirst(&pDb->pSchema->tblHash); i; i=sqliteHashNext(i)){
      Table *pTab = sqliteHashData(i);
      sqlite3VdbeAddOp4(v, OP_String8, 0, 1, 0, pTab->zName, 0);
      sqlite3VdbeAddOp2(v, OP_Null, 0, 2);
      sqlite3VdbeAddOp2(v, OP_Integer,
                           (int)sqlite3LogEstToInt(pTab->szTabRow), 3);
      sqlite3VdbeAddOp2(v, OP_Integer, 
          (int)sqlite3LogEstToInt(pTab->nRowLogEst), 4);
      sqlite3VdbeAddOp2(v, OP_ResultRow, 1, 4);
      for(pIdx=pTab->pIndex; pIdx; pIdx=pIdx->pNext){
        sqlite3VdbeAddOp4(v, OP_String8, 0, 2, 0, pIdx->zName, 0);
        sqlite3VdbeAddOp2(v, OP_Integer,
                             (int)sqlite3LogEstToInt(pIdx->szIdxRow), 3);
        sqlite3VdbeAddOp2(v, OP_Integer, 
            (int)sqlite3LogEstToInt(pIdx->aiRowLogEst[0]), 4);
        sqlite3VdbeAddOp2(v, OP_ResultRow, 1, 4);
      }
    }
  }
  break;

  case PragTyp_INDEX_INFO: if( zRight ){

    return 0;
  }
  /* The sqlite3ResultSetOfSelect() is only used n contexts where lookaside
  ** is disabled */
  assert( db->lookaside.bEnabled==0 );
  pTab->nRef = 1;
  pTab->zName = 0;
  pTab->nRowLogEst = 200; assert( 200==sqlite3LogEst(1048576) );
  selectColumnsFromExprList(pParse, pSelect->pEList, &pTab->nCol, &pTab->aCol);
  selectAddColumnTypeAndCollation(pParse, pTab, pSelect);
  pTab->iPKey = -1;
  if( db->mallocFailed ){
    sqlite3DeleteTable(db, pTab);
    return 0;
  }

    assert( pFrom->pTab==0 );
    pFrom->pTab = pTab = sqlite3DbMallocZero(db, sizeof(Table));
    if( pTab==0 ) return WRC_Abort;
    pTab->nRef = 1;
    pTab->zName = sqlite3DbStrDup(db, pCte->zName);
    pTab->iPKey = -1;
    pTab->nRowLogEst = 200; assert( 200==sqlite3LogEst(1048576) );
    pTab->tabFlags |= TF_Ephemeral;
    pFrom->pSelect = sqlite3SelectDup(db, pCte->pSelect, 0);
    if( db->mallocFailed ) return SQLITE_NOMEM;
    assert( pFrom->pSelect );

    /* Check if this is a recursive CTE. */
    pSel = pFrom->pSelect;

      pFrom->pTab = pTab = sqlite3DbMallocZero(db, sizeof(Table));
      if( pTab==0 ) return WRC_Abort;
      pTab->nRef = 1;
      pTab->zName = sqlite3MPrintf(db, "sqlite_sq_%p", (void*)pTab);
      while( pSel->pPrior ){ pSel = pSel->pPrior; }
      selectColumnsFromExprList(pParse, pSel->pEList, &pTab->nCol, &pTab->aCol);
      pTab->iPKey = -1;
      pTab->nRowLogEst = 200; assert( 200==sqlite3LogEst(1048576) );
      pTab->tabFlags |= TF_Ephemeral;
#endif
    }else{
      /* An ordinary table or view name in the FROM clause */
      assert( pFrom->pTab==0 );
      pFrom->pTab = pTab = sqlite3LocateTableItem(pParse, 0, pFrom);
      if( pTab==0 ) return WRC_Abort;

      pItem->regReturn = ++pParse->nMem;
      sqlite3VdbeAddOp3(v, OP_InitCoroutine, pItem->regReturn, 0, addrTop);
      VdbeComment((v, "%s", pItem->pTab->zName));
      pItem->addrFillSub = addrTop;
      sqlite3SelectDestInit(&dest, SRT_Coroutine, pItem->regReturn);
      explainSetInteger(pItem->iSelectId, (u8)pParse->iNextSelectId);
      sqlite3Select(pParse, pSub, &dest);
      pItem->pTab->nRowLogEst = sqlite3LogEst(pSub->nSelectRow);
      pItem->viaCoroutine = 1;
      pItem->regResult = dest.iSdst;
      sqlite3VdbeAddOp1(v, OP_EndCoroutine, pItem->regReturn);
      sqlite3VdbeJumpHere(v, addrTop-1);
      sqlite3ClearTempRegCache(pParse);
    }else{
      /* Generate a subroutine that will fill an ephemeral table with

        VdbeComment((v, "materialize \"%s\"", pItem->pTab->zName));
      }else{
        VdbeNoopComment((v, "materialize \"%s\"", pItem->pTab->zName));
      }
      sqlite3SelectDestInit(&dest, SRT_EphemTab, pItem->iCursor);
      explainSetInteger(pItem->iSelectId, (u8)pParse->iNextSelectId);
      sqlite3Select(pParse, pSub, &dest);
      pItem->pTab->nRowLogEst = sqlite3LogEst(pSub->nSelectRow);
      if( onceAddr ) sqlite3VdbeJumpHere(v, onceAddr);
      retAddr = sqlite3VdbeAddOp1(v, OP_Return, pItem->regReturn);
      VdbeComment((v, "end %s", pItem->pTab->zName));
      sqlite3VdbeChangeP1(v, topAddr, retAddr);
      sqlite3ClearTempRegCache(pParse);
    }
    if( /*pParse->nErr ||*/ db->mallocFailed ){

/*
** Estimated quantities used for query planning are stored as 16-bit
** logarithms.  For quantity X, the value stored is 10*log2(X).  This
** gives a possible range of values of approximately 1.0e986 to 1e-986.
** But the allowed values are "grainy".  Not every value is representable.
** For example, quantities 16 and 17 are both represented by a LogEst
** of 40.  However, since LogEst quantaties are suppose to be estimates,
** not exact values, this imprecision is not a problem.
**
** "LogEst" is short for "Logarithmic Estimate".
**
** Examples:
**      1 -> 0              20 -> 43          10000 -> 132
**      2 -> 10             25 -> 46          25000 -> 146
**      3 -> 16            100 -> 66        1000000 -> 199
**      4 -> 20           1000 -> 99        1048576 -> 200
**     10 -> 33           1024 -> 100    4294967296 -> 320

  Index *pIndex;       /* List of SQL indexes on this table. */
  Select *pSelect;     /* NULL for tables.  Points to definition if a view. */
  FKey *pFKey;         /* Linked list of all foreign keys in this table */
  char *zColAff;       /* String defining the affinity of each column */
#ifndef SQLITE_OMIT_CHECK
  ExprList *pCheck;    /* All CHECK constraints */
#endif
  LogEst nRowLogEst;   /* Estimated rows in table - from sqlite_stat1 table */
  int tnum;            /* Root BTree node for this table (see note above) */
  i16 iPKey;           /* If not negative, use aCol[iPKey] as the primary key */
  i16 nCol;            /* Number of columns in this table */
  u16 nRef;            /* Number of pointers to this Table */
  LogEst szTabRow;     /* Estimated size of each table row in bytes */
  u8 tabFlags;         /* Mask of TF_* values */
  u8 keyConf;          /* What to do in case of uniqueness conflict on iPKey */

** and the value of Index.onError indicate the which conflict resolution 
** algorithm to employ whenever an attempt is made to insert a non-unique
** element.
*/
struct Index {
  char *zName;             /* Name of this index */
  i16 *aiColumn;           /* Which columns are used by this index.  1st is 0 */
  LogEst *aiRowLogEst;     /* From ANALYZE: Est. rows selected by each column */
  Table *pTable;           /* The SQL table being indexed */
  char *zColAff;           /* String defining the affinity of each column */
  Index *pNext;            /* The next index associated with the same table */
  Schema *pSchema;         /* Schema containing this index */
  u8 *aSortOrder;          /* for each column: True==DESC, False==ASC */
  char **azColl;           /* Array of collation sequence names for index */
  Expr *pPartIdxWhere;     /* WHERE clause for partial indices */

    if( b>a+49 ) return b;
    if( b>a+31 ) return b+1;
    return b+x[b-a];
  }
}

/*
** Convert an integer into a LogEst.  In other words, compute an
** approximation for 10*log2(x).
*/
LogEst sqlite3LogEst(u64 x){
  static LogEst a[] = { 0, 2, 3, 5, 6, 7, 8, 9 };
  LogEst y = 40;
  if( x<8 ){
    if( x<2 ) return 0;
    while( x<8 ){  y -= 10; x <<= 1; }

    }
    pWC->nSlot = sqlite3DbMallocSize(db, pWC->a)/sizeof(pWC->a[0]);
  }
  pTerm = &pWC->a[idx = pWC->nTerm++];
  if( p && ExprHasProperty(p, EP_Unlikely) ){
    pTerm->truthProb = sqlite3LogEst(p->iTable) - 99;
  }else{
    pTerm->truthProb = 1;
  }
  pTerm->pExpr = sqlite3ExprSkipCollate(p);
  pTerm->wtFlags = wtFlags;
  pTerm->pWC = pWC;
  pTerm->iParent = -1;
  return idx;
}

    aStat[1] = aSample[i].anEq[iCol];
  }else{
    tRowcnt iLower, iUpper, iGap;
    if( i==0 ){
      iLower = 0;
      iUpper = aSample[0].anLt[iCol];
    }else{
      i64 nRow0 = sqlite3LogEstToInt(pIdx->aiRowLogEst[0]);
      iUpper = i>=pIdx->nSample ? nRow0 : aSample[i].anLt[iCol];
      iLower = aSample[i-1].anEq[iCol] + aSample[i-1].anLt[iCol];
    }
    aStat[1] = (pIdx->nKeyCol>iCol ? pIdx->aAvgEq[iCol] : 1);
    if( iLower>=iUpper ){
      iGap = 0;
    }else{
      iGap = iUpper - iLower;
    }
    if( roundUp ){
      iGap = (iGap*2)/3;
    }else{
      iGap = iGap/3;
    }
    aStat[0] = iLower + iGap;
  }
}
#endif /* SQLITE_ENABLE_STAT3_OR_STAT4 */

/*
** If it is not NULL, pTerm is a term that provides an upper or lower
** bound on a range scan. Without considering pTerm, it is estimated 
** that the scan will visit nNew rows. This function returns the number
** estimated to be visited after taking pTerm into account.
**
** If the user explicitly specified a likelihood() value for this term,
** then the return value is the likelihood multiplied by the number of
** input rows. Otherwise, this function assumes that an "IS NOT NULL" term
** has a likelihood of 0.50, and any other term a likelihood of 0.25.
*/
static LogEst whereRangeAdjust(WhereTerm *pTerm, LogEst nNew){
  LogEst nRet = nNew;
  if( pTerm ){
    if( pTerm->truthProb<=0 ){
      nRet += pTerm->truthProb;
    }else if( (pTerm->wtFlags & TERM_VNULL)==0 ){
      nRet -= 20;        assert( 20==sqlite3LogEst(4) );
    }
  }
  return nRet;
}

/*
** This function is used to estimate the number of rows that will be visited
** by scanning an index for a range of values. The range may have an upper
** bound, a lower bound, or both. The WHERE clause terms that set the upper
** and lower bounds are represented by pLower and pUpper respectively. For
** example, assuming that index p is on t1(a):

      aff = SQLITE_AFF_INTEGER;
    }else{
      aff = p->pTable->aCol[p->aiColumn[nEq]].affinity;
    }
    /* Determine iLower and iUpper using ($P) only. */
    if( nEq==0 ){
      iLower = 0;
      iUpper = sqlite3LogEstToInt(p->aiRowLogEst[0]);
    }else{
      /* Note: this call could be optimized away - since the same values must 
      ** have been requested when testing key $P in whereEqualScanEst().  */
      whereKeyStats(pParse, p, pRec, 0, a);
      iLower = a[0];
      iUpper = a[0] + a[1];
    }

    }
  }
#else
  UNUSED_PARAMETER(pParse);
  UNUSED_PARAMETER(pBuilder);
#endif
  assert( pLower || pUpper );



  assert( pUpper==0 || (pUpper->wtFlags & TERM_VNULL)==0 );

  nNew = whereRangeAdjust(pLower, nOut);
  nNew = whereRangeAdjust(pUpper, nNew);

  /* TUNING: If there is both an upper and lower limit, assume the range is
  ** reduced by an additional 75%. This means that, by default, an open-ended
  ** range query (e.g. col > ?) is assumed to match 1/4 of the rows in the
  ** index. While a closed range (e.g. col BETWEEN ? AND ?) is estimated to
  ** match 1/64 of the index. */ 
  if( pLower && pUpper ) nNew -= 20;


  nOut -= (pLower!=0) + (pUpper!=0);
  if( nNew<10 ) nNew = 10;
  if( nNew<nOut ) nOut = nNew;
  pLoop->nOut = (LogEst)nOut;
  return rc;
}

#ifdef SQLITE_ENABLE_STAT3_OR_STAT4

static int whereInScanEst(
  Parse *pParse,       /* Parsing & code generating context */
  WhereLoopBuilder *pBuilder,
  ExprList *pList,     /* The value list on the RHS of "x IN (v1,v2,v3,...)" */
  tRowcnt *pnRow       /* Write the revised row estimate here */
){
  Index *p = pBuilder->pNew->u.btree.pIndex;
  i64 nRow0 = sqlite3LogEstToInt(p->aiRowLogEst[0]);
  int nRecValid = pBuilder->nRecValid;
  int rc = SQLITE_OK;     /* Subfunction return code */
  tRowcnt nEst;           /* Number of rows for a single term */
  tRowcnt nRowEst = 0;    /* New estimate of the number of rows */
  int i;                  /* Loop counter */

  assert( p->aSample!=0 );
  for(i=0; rc==SQLITE_OK && i<pList->nExpr; i++){
    nEst = nRow0;
    rc = whereEqualScanEst(pParse, pBuilder, pList->a[i].pExpr, &nEst);
    nRowEst += nEst;
    pBuilder->nRecValid = nRecValid;
  }

  if( rc==SQLITE_OK ){
    if( nRowEst > nRow0 ) nRowEst = nRow0;
    *pnRow = nRowEst;
    WHERETRACE(0x10,("IN row estimate: est=%g\n", nRowEst));
  }
  assert( pBuilder->nRecValid==nRecValid );
  return rc;
}
#endif /* SQLITE_ENABLE_STAT3_OR_STAT4 */

**
** To say "WhereLoop X is a proper subset of Y" means that X uses fewer
** WHERE clause terms than Y and that every WHERE clause term used by X is
** also used by Y.
*/
static void whereLoopAdjustCost(const WhereLoop *p, WhereLoop *pTemplate){
  if( (pTemplate->wsFlags & WHERE_INDEXED)==0 ) return;
  if( (pTemplate->wsFlags & WHERE_SKIPSCAN)!=0 ) return;
  for(; p; p=p->pNextLoop){
    if( p->iTab!=pTemplate->iTab ) continue;
    if( (p->wsFlags & WHERE_INDEXED)==0 ) continue;
    if( (p->wsFlags & WHERE_SKIPSCAN)!=0 ) continue;
    if( whereLoopCheaperProperSubset(p, pTemplate) ){
      /* Adjust pTemplate cost downward so that it is cheaper than its 
      ** subset p */
      pTemplate->rRun = p->rRun;
      pTemplate->nOut = p->nOut - 1;
    }else if( whereLoopCheaperProperSubset(pTemplate, p) ){
      /* Adjust pTemplate cost upward so that it is costlier than p since

    if( (pTerm->prereqAll & notAllowed)!=0 ) continue;
    for(j=pLoop->nLTerm-1; j>=0; j--){
      pX = pLoop->aLTerm[j];
      if( pX==0 ) continue;
      if( pX==pTerm ) break;
      if( pX->iParent>=0 && (&pWC->a[pX->iParent])==pTerm ) break;
    }
    if( j<0 ){
      pLoop->nOut += (pTerm->truthProb<=0 ? pTerm->truthProb : -1);
    }
  }
}

/*
** We have so far matched pBuilder->pNew->u.btree.nEq terms of the 
** index pIndex. Try to match one more.
**
** When this function is called, pBuilder->pNew->nOut contains the 
** number of rows expected to be visited by filtering using the nEq 
** terms only. If it is modified, this value is restored before this 
** function returns.
**
** If pProbe->tnum==0, that means pIndex is a fake index used for the
** INTEGER PRIMARY KEY.
*/
static int whereLoopAddBtreeIndex(
  WhereLoopBuilder *pBuilder,     /* The WhereLoop factory */
  struct SrcList_item *pSrc,      /* FROM clause term being analyzed */

  u16 saved_nLTerm;               /* Original value of pNew->nLTerm */
  u16 saved_nEq;                  /* Original value of pNew->u.btree.nEq */
  u16 saved_nSkip;                /* Original value of pNew->u.btree.nSkip */
  u32 saved_wsFlags;              /* Original value of pNew->wsFlags */
  LogEst saved_nOut;              /* Original value of pNew->nOut */
  int iCol;                       /* Index of the column in the table */
  int rc = SQLITE_OK;             /* Return code */

  LogEst rLogSize;                /* Logarithm of table size */
  WhereTerm *pTop = 0, *pBtm = 0; /* Top and bottom range constraints */

  pNew = pBuilder->pNew;
  if( db->mallocFailed ) return SQLITE_NOMEM;

  assert( (pNew->wsFlags & WHERE_VIRTUALTABLE)==0 );
  assert( (pNew->wsFlags & WHERE_TOP_LIMIT)==0 );
  if( pNew->wsFlags & WHERE_BTM_LIMIT ){
    opMask = WO_LT|WO_LE;
  }else if( pProbe->tnum<=0 || (pSrc->jointype & JT_LEFT)!=0 ){
    opMask = WO_EQ|WO_IN|WO_GT|WO_GE|WO_LT|WO_LE;
  }else{
    opMask = WO_EQ|WO_IN|WO_ISNULL|WO_GT|WO_GE|WO_LT|WO_LE;
  }
  if( pProbe->bUnordered ) opMask &= ~(WO_GT|WO_GE|WO_LT|WO_LE);

  assert( pNew->u.btree.nEq<=pProbe->nKeyCol );
  if( pNew->u.btree.nEq < pProbe->nKeyCol ){
    iCol = pProbe->aiColumn[pNew->u.btree.nEq];


  }else{
    iCol = -1;

  }
  pTerm = whereScanInit(&scan, pBuilder->pWC, pSrc->iCursor, iCol,
                        opMask, pProbe);
  saved_nEq = pNew->u.btree.nEq;
  saved_nSkip = pNew->u.btree.nSkip;
  saved_nLTerm = pNew->nLTerm;
  saved_wsFlags = pNew->wsFlags;
  saved_prereq = pNew->prereq;
  saved_nOut = pNew->nOut;
  pNew->rSetup = 0;
  rLogSize = estLog(pProbe->aiRowLogEst[0]);

  /* Consider using a skip-scan if there are no WHERE clause constraints
  ** available for the left-most terms of the index, and if the average
  ** number of repeats in the left-most terms is at least 18. 


  **
  ** The magic number 18 is selected on the basis that scanning 17 rows
  ** is almost always quicker than an index seek (even though if the index
  ** contains fewer than 2^17 rows we assume otherwise in other parts of
  ** the code). And, even if it is not, it should not be too much slower. 
  ** On the other hand, the extra seeks could end up being significantly
  ** more expensive.  */
  assert( 42==sqlite3LogEst(18) );
  if( pTerm==0
   && saved_nEq==saved_nSkip
   && saved_nEq+1<pProbe->nKeyCol
   && pProbe->aiRowLogEst[saved_nEq+1]>=42  /* TUNING: Minimum for skip-scan */
   && (rc = whereLoopResize(db, pNew, pNew->nLTerm+1))==SQLITE_OK
  ){
    LogEst nIter;
    pNew->u.btree.nEq++;
    pNew->u.btree.nSkip++;
    pNew->aLTerm[pNew->nLTerm++] = 0;
    pNew->wsFlags |= WHERE_SKIPSCAN;
    nIter = pProbe->aiRowLogEst[saved_nEq] - pProbe->aiRowLogEst[saved_nEq+1];

    pNew->nOut -= nIter;
    whereLoopAddBtreeIndex(pBuilder, pSrc, pProbe, nIter + nInMul);
    pNew->nOut = saved_nOut;
  }
  for(; rc==SQLITE_OK && pTerm!=0; pTerm = whereScanNext(&scan)){
    u16 eOp = pTerm->eOperator;   /* Shorthand for pTerm->eOperator */
    LogEst rCostIdx;
    LogEst nOutUnadjusted;        /* nOut before IN() and WHERE adjustments */
    int nIn = 0;
#ifdef SQLITE_ENABLE_STAT3_OR_STAT4
    int nRecValid = pBuilder->nRecValid;
#endif
    if( (eOp==WO_ISNULL || (pTerm->wtFlags&TERM_VNULL)!=0)
     && (iCol<0 || pSrc->pTab->aCol[iCol].notNull)
    ){
      continue; /* ignore IS [NOT] NULL constraints on NOT NULL columns */
    }
    if( pTerm->prereqRight & pNew->maskSelf ) continue;



    pNew->wsFlags = saved_wsFlags;
    pNew->u.btree.nEq = saved_nEq;
    pNew->nLTerm = saved_nLTerm;
    if( whereLoopResize(db, pNew, pNew->nLTerm+1) ) break; /* OOM */
    pNew->aLTerm[pNew->nLTerm++] = pTerm;
    pNew->prereq = (saved_prereq | pTerm->prereqRight) & ~pNew->maskSelf;

    assert( nInMul==0
        || (pNew->wsFlags & WHERE_COLUMN_NULL)!=0 
        || (pNew->wsFlags & WHERE_COLUMN_IN)!=0 
        || (pNew->wsFlags & WHERE_SKIPSCAN)!=0 
    );

    if( eOp & WO_IN ){
      Expr *pExpr = pTerm->pExpr;
      pNew->wsFlags |= WHERE_COLUMN_IN;
      if( ExprHasProperty(pExpr, EP_xIsSelect) ){
        /* "x IN (SELECT ...)":  TUNING: the SELECT returns 25 rows */
        nIn = 46;  assert( 46==sqlite3LogEst(25) );
      }else if( ALWAYS(pExpr->x.pList && pExpr->x.pList->nExpr) ){
        /* "x IN (value, value, ...)" */
        nIn = sqlite3LogEst(pExpr->x.pList->nExpr);
      }
      assert( nIn>0 );  /* RHS always has 2 or more terms...  The parser
                        ** changes "x IN (?)" into "x=?". */



    }else if( eOp & (WO_EQ) ){




      pNew->wsFlags |= WHERE_COLUMN_EQ;
      if( iCol<0 || (nInMul==0 && pNew->u.btree.nEq==pProbe->nKeyCol-1) ){

        if( iCol>=0 && pProbe->onError==OE_None ){
          pNew->wsFlags |= WHERE_UNQ_WANTED;
        }else{
          pNew->wsFlags |= WHERE_ONEROW;
        }
      }


    }else if( eOp & WO_ISNULL ){
      pNew->wsFlags |= WHERE_COLUMN_NULL;




    }else if( eOp & (WO_GT|WO_GE) ){
      testcase( eOp & WO_GT );
      testcase( eOp & WO_GE );
      pNew->wsFlags |= WHERE_COLUMN_RANGE|WHERE_BTM_LIMIT;
      pBtm = pTerm;
      pTop = 0;
    }else{
      assert( eOp & (WO_LT|WO_LE) );
      testcase( eOp & WO_LT );
      testcase( eOp & WO_LE );
      pNew->wsFlags |= WHERE_COLUMN_RANGE|WHERE_TOP_LIMIT;
      pTop = pTerm;
      pBtm = (pNew->wsFlags & WHERE_BTM_LIMIT)!=0 ?
                     pNew->aLTerm[pNew->nLTerm-2] : 0;
    }

    /* At this point pNew->nOut is set to the number of rows expected to
    ** be visited by the index scan before considering term pTerm, or the
    ** values of nIn and nInMul. In other words, assuming that all 
    ** "x IN(...)" terms are replaced with "x = ?". This block updates
    ** the value of pNew->nOut to account for pTerm (but not nIn/nInMul).  */
    assert( pNew->nOut==saved_nOut );
    if( pNew->wsFlags & WHERE_COLUMN_RANGE ){
      /* Adjust nOut using stat3/stat4 data. Or, if there is no stat3/stat4
      ** data, using some other estimate.  */
      whereRangeScanEst(pParse, pBuilder, pBtm, pTop, pNew);
    }else{
      int nEq = ++pNew->u.btree.nEq;
      assert( eOp & (WO_ISNULL|WO_EQ|WO_IN) );

      assert( pNew->nOut==saved_nOut );
      if( pTerm->truthProb<=0 && iCol>=0 ){
        assert( (eOp & WO_IN) || nIn==0 );
        pNew->nOut += pTerm->truthProb;
        pNew->nOut -= nIn;
        pNew->wsFlags |= WHERE_LIKELIHOOD;
      }else{
#ifdef SQLITE_ENABLE_STAT3_OR_STAT4
        tRowcnt nOut = 0;
        if( nInMul==0 
         && pProbe->nSample 
         && pNew->u.btree.nEq<=pProbe->nSampleCol
         && OptimizationEnabled(db, SQLITE_Stat3) 
         && ((eOp & WO_IN)==0 || !ExprHasProperty(pTerm->pExpr, EP_xIsSelect))
         && (pNew->wsFlags & WHERE_LIKELIHOOD)==0
        ){
          Expr *pExpr = pTerm->pExpr;

          if( (eOp & (WO_EQ|WO_ISNULL))!=0 ){
            testcase( eOp & WO_EQ );
            testcase( eOp & WO_ISNULL );
            rc = whereEqualScanEst(pParse, pBuilder, pExpr->pRight, &nOut);
          }else{

            rc = whereInScanEst(pParse, pBuilder, pExpr->x.pList, &nOut);
          }
          assert( rc!=SQLITE_OK || nOut>0 );
          if( rc==SQLITE_NOTFOUND ) rc = SQLITE_OK;
          if( rc!=SQLITE_OK ) break;          /* Jump out of the pTerm loop */
          if( nOut ){
            pNew->nOut = sqlite3LogEst(nOut);
            if( pNew->nOut>saved_nOut ) pNew->nOut = saved_nOut;
            pNew->nOut -= nIn;
          }
        }
        if( nOut==0 )
#endif
        {
          pNew->nOut += (pProbe->aiRowLogEst[nEq] - pProbe->aiRowLogEst[nEq-1]);
          if( eOp & WO_ISNULL ){
            /* TUNING: If there is no likelihood() value, assume that a 
            ** "col IS NULL" expression matches twice as many rows 
            ** as (col=?). */
            pNew->nOut += 10;
          }
        }
      }
    }

    /* Set rCostIdx to the cost of visiting selected rows in index. Add
    ** it to pNew->rRun, which is currently set to the cost of the index
    ** seek only. Then, if this is a non-covering index, add the cost of
    ** visiting the rows in the main table.  */
    rCostIdx = pNew->nOut + 1 + (15*pProbe->szIdxRow)/pSrc->pTab->szTabRow;
    pNew->rRun = sqlite3LogEstAdd(rLogSize, rCostIdx);
    if( (pNew->wsFlags & (WHERE_IDX_ONLY|WHERE_IPK))==0 ){


      pNew->rRun = sqlite3LogEstAdd(pNew->rRun, pNew->nOut + 16);
    }

    nOutUnadjusted = pNew->nOut;
    pNew->rRun += nInMul + nIn;
    pNew->nOut += nInMul + nIn;
    whereLoopOutputAdjust(pBuilder->pWC, pNew);
    rc = whereLoopInsert(pBuilder, pNew);

    if( pNew->wsFlags & WHERE_COLUMN_RANGE ){
      pNew->nOut = saved_nOut;
    }else{
      pNew->nOut = nOutUnadjusted;
    }

    if( (pNew->wsFlags & WHERE_TOP_LIMIT)==0
     && pNew->u.btree.nEq<(pProbe->nKeyCol + (pProbe->zName!=0))
    ){
      whereLoopAddBtreeIndex(pBuilder, pSrc, pProbe, nInMul+nIn);
    }
    pNew->nOut = saved_nOut;
#ifdef SQLITE_ENABLE_STAT3_OR_STAT4

  return 0;
}

/*
** Add all WhereLoop objects for a single table of the join where the table
** is idenfied by pBuilder->pNew->iTab.  That table is guaranteed to be
** a b-tree table, not a virtual table.
**
** The costs (WhereLoop.rRun) of the b-tree loops added by this function
** are calculated as follows:
**
** For a full scan, assuming the table (or index) contains nRow rows:
**
**     cost = nRow * 3.0                    // full-table scan
**     cost = nRow * K                      // scan of covering index
**     cost = nRow * (K+3.0)                // scan of non-covering index
**
** where K is a value between 1.1 and 3.0 set based on the relative 
** estimated average size of the index and table records.
**
** For an index scan, where nVisit is the number of index rows visited
** by the scan, and nSeek is the number of seek operations required on 
** the index b-tree:
**
**     cost = nSeek * (log(nRow) + K * nVisit)          // covering index
**     cost = nSeek * (log(nRow) + (K+3.0) * nVisit)    // non-covering index
**
** Normally, nSeek is 1. nSeek values greater than 1 come about if the 
** WHERE clause includes "x IN (....)" terms used in place of "x=?". Or when 
** implicit "x IN (SELECT x FROM tbl)" terms are added for skip-scans.
*/
static int whereLoopAddBtree(
  WhereLoopBuilder *pBuilder, /* WHERE clause information */
  Bitmask mExtra              /* Extra prerequesites for using this table */
){
  WhereInfo *pWInfo;          /* WHERE analysis context */
  Index *pProbe;              /* An index we are evaluating */
  Index sPk;                  /* A fake index object for the primary key */
  LogEst aiRowEstPk[2];       /* The aiRowLogEst[] value for the sPk index */
  i16 aiColumnPk = -1;        /* The aColumn[] value for the sPk index */
  SrcList *pTabList;          /* The FROM clause */
  struct SrcList_item *pSrc;  /* The FROM clause btree term to add */
  WhereLoop *pNew;            /* Template WhereLoop object */
  int rc = SQLITE_OK;         /* Return code */
  int iSortIdx = 1;           /* Index number */
  int b;                      /* A boolean value */

    ** variable sPk to represent the rowid primary key index.  Make this
    ** fake index the first in a chain of Index objects with all of the real
    ** indices to follow */
    Index *pFirst;                  /* First of real indices on the table */
    memset(&sPk, 0, sizeof(Index));
    sPk.nKeyCol = 1;
    sPk.aiColumn = &aiColumnPk;
    sPk.aiRowLogEst = aiRowEstPk;
    sPk.onError = OE_Replace;
    sPk.pTable = pTab;
    sPk.szIdxRow = pTab->szTabRow;
    aiRowEstPk[0] = pTab->nRowLogEst;
    aiRowEstPk[1] = 0;
    pFirst = pSrc->pTab->pIndex;
    if( pSrc->notIndexed==0 ){
      /* The real indices of the table are only considered if the
      ** NOT INDEXED qualifier is omitted from the FROM clause */
      sPk.pNext = pFirst;
    }
    pProbe = &sPk;
  }
  rSize = pTab->nRowLogEst;
  rLogSize = estLog(rSize);

#ifndef SQLITE_OMIT_AUTOMATIC_INDEX
  /* Automatic indexes */
  if( !pBuilder->pOrSet
   && (pWInfo->pParse->db->flags & SQLITE_AutoIndex)!=0
   && pSrc->pIndex==0

  /* Loop over all indices
  */
  for(; rc==SQLITE_OK && pProbe; pProbe=pProbe->pNext, iSortIdx++){
    if( pProbe->pPartIdxWhere!=0
     && !whereUsablePartialIndex(pNew->iTab, pWC, pProbe->pPartIdxWhere) ){
      continue;  /* Partial index inappropriate for this query */
    }
    rSize = pProbe->aiRowLogEst[0];
    pNew->u.btree.nEq = 0;
    pNew->u.btree.nSkip = 0;
    pNew->nLTerm = 0;
    pNew->iSortIdx = 0;
    pNew->rSetup = 0;
    pNew->prereq = mExtra;
    pNew->nOut = rSize;
    pNew->u.btree.pIndex = pProbe;
    b = indexMightHelpWithOrderBy(pBuilder, pProbe, pSrc->iCursor);
    /* The ONEPASS_DESIRED flags never occurs together with ORDER BY */
    assert( (pWInfo->wctrlFlags & WHERE_ONEPASS_DESIRED)==0 || b==0 );
    if( pProbe->tnum<=0 ){
      /* Integer primary key index */
      pNew->wsFlags = WHERE_IPK;

      /* Full table scan */
      pNew->iSortIdx = b ? iSortIdx : 0;
      /* TUNING: Cost of full table scan is (N*3.0). */


      pNew->rRun = rSize + 16;
      whereLoopOutputAdjust(pWC, pNew);
      rc = whereLoopInsert(pBuilder, pNew);
      pNew->nOut = rSize;
      if( rc ) break;
    }else{
      Bitmask m;
      if( pProbe->isCovering ){

         && (pProbe->szIdxRow<pTab->szTabRow)
         && (pWInfo->wctrlFlags & WHERE_ONEPASS_DESIRED)==0
         && sqlite3GlobalConfig.bUseCis
         && OptimizationEnabled(pWInfo->pParse->db, SQLITE_CoverIdxScan)
          )
      ){
        pNew->iSortIdx = b ? iSortIdx : 0;





        /* The cost of visiting the index rows is N*K, where K is

        ** between 1.1 and 3.0, depending on the relative sizes of the



        ** index and table rows. If this is a non-covering index scan,

        ** also add the cost of visiting table rows (N*3.0).  */
        pNew->rRun = rSize + 1 + (15*pProbe->szIdxRow)/pTab->szTabRow;











        if( m!=0 ){

          pNew->rRun = sqlite3LogEstAdd(pNew->rRun, rSize+16);
        }

        whereLoopOutputAdjust(pWC, pNew);
        rc = whereLoopInsert(pBuilder, pNew);
        pNew->nOut = rSize;
        if( rc ) break;
      }
    }

      pNew->nLTerm = 1;
      pNew->aLTerm[0] = pTerm;
      pNew->wsFlags = WHERE_MULTI_OR;
      pNew->rSetup = 0;
      pNew->iSortIdx = 0;
      memset(&pNew->u, 0, sizeof(pNew->u));
      for(i=0; rc==SQLITE_OK && i<sSum.n; i++){

        pNew->rRun = sSum.a[i].rRun;
        pNew->nOut = sSum.a[i].nOut;
        pNew->prereq = sSum.a[i].prereq;
        rc = whereLoopInsert(pBuilder, pNew);
      }
    }
  }
  return rc;

        nOut = pFrom->nRow + pWLoop->nOut;
        maskNew = pFrom->maskLoop | pWLoop->maskSelf;
        if( isOrdered<0 ){
          isOrdered = wherePathSatisfiesOrderBy(pWInfo,
                       pWInfo->pOrderBy, pFrom, pWInfo->wctrlFlags,
                       iLoop, pWLoop, &revMask);
          if( isOrdered>=0 && isOrdered<nOrderBy ){
            /* TUNING: Estimated cost of a full external sort, where N is 
            ** the number of rows to sort is:
            **
            **   cost = (3.0 * N * log(N)).
            ** 
            ** Or, if the order-by clause has X terms but only the last Y 
            ** terms are out of order, then block-sorting will reduce the 
            ** sorting cost to:
            **


            **   cost = (3.0 * N * log(N)) * (Y/X)
            **
            ** The (Y/X) term is implemented using stack variable rScale
            ** below.  */
            LogEst rScale, rSortCost;
            assert( nOrderBy>0 && 66==sqlite3LogEst(100) );
            rScale = sqlite3LogEst((nOrderBy-isOrdered)*100/nOrderBy) - 66;
            rSortCost = nRowEst + estLog(nRowEst) + rScale + 16;

            /* TUNING: The cost of implementing DISTINCT using a B-TREE is
            ** similar but with a larger constant of proportionality. 
            ** Multiply by an additional factor of 3.0.  */
            if( pWInfo->wctrlFlags & WHERE_WANT_DISTINCT ){
              rSortCost += 16;
            }
            WHERETRACE(0x002,
               ("---- sort cost=%-3d (%d/%d) increases cost %3d to %-3d\n",
                rSortCost, (nOrderBy-isOrdered), nOrderBy, rCost,
                sqlite3LogEstAdd(rCost,rSortCost)));

#define WHERE_VIRTUALTABLE 0x00000400  /* WhereLoop.u.vtab is valid */
#define WHERE_IN_ABLE      0x00000800  /* Able to support an IN operator */
#define WHERE_ONEROW       0x00001000  /* Selects no more than one row */
#define WHERE_MULTI_OR     0x00002000  /* OR using multiple indices */
#define WHERE_AUTO_INDEX   0x00004000  /* Uses an ephemeral index */
#define WHERE_SKIPSCAN     0x00008000  /* Uses the skip-scan algorithm */
#define WHERE_UNQ_WANTED   0x00010000  /* WHERE_ONEROW would have been helpful*/
#define WHERE_LIKELIHOOD   0x00020000  /* A likelihood() is affecting nOut */

  ifcapable stat4 {
    execsql { SELECT count(*)>0 FROM sqlite_stat4; }
  } else {
    execsql { SELECT count(*)>0 FROM sqlite_stat3; }
  }
} {1}

do_execsql_test analyze3-1.1.x {
  SELECT count(*) FROM t1 WHERE x>200 AND x<300;
  SELECT count(*) FROM t1 WHERE x>0 AND x<1100;
} {99 1000}

# The first of the following two SELECT statements visits 99 rows. So
# it is better to use the index. But the second visits every row in 
# the table (1000 in total) so it is better to do a full-table scan.
#
do_eqp_test analyze3-1.1.2 {
  SELECT sum(y) FROM t1 WHERE x>200 AND x<300
} {0 0 0 {SEARCH TABLE t1 USING INDEX i1 (x>? AND x<?)}}
do_eqp_test analyze3-1.1.3 {
  SELECT sum(y) FROM t1 WHERE x>0 AND x<1100 
} {0 0 0 {SCAN TABLE t1}}

do_test analyze3-1.1.4 {
  sf_execsql { SELECT sum(y) FROM t1 WHERE x>200 AND x<300 }
} {199 0 14850}
do_test analyze3-1.1.5 {
  set l [string range "200" 0 end]
  set u [string range "300" 0 end]
  sf_execsql { SELECT sum(y) FROM t1 WHERE x>$l AND x<$u }
} {199 0 14850}
do_test analyze3-1.1.6 {
  set l [expr int(200)]
  set u [expr int(300)]
  sf_execsql { SELECT sum(y) FROM t1 WHERE x>$l AND x<$u }
} {199 0 14850}
do_test analyze3-1.1.7 {
  sf_execsql { SELECT sum(y) FROM t1 WHERE x>0 AND x<1100 }
} {999 999 499500}
do_test analyze3-1.1.8 {
  set l [string range "0" 0 end]
  set u [string range "1100" 0 end]
  sf_execsql { SELECT sum(y) FROM t1 WHERE x>$l AND x<$u }
} {999 999 499500}
do_test analyze3-1.1.9 {
  set l [expr int(0)]
  set u [expr int(1100)]
  sf_execsql { SELECT sum(y) FROM t1 WHERE x>$l AND x<$u }
} {999 999 499500}


# The following tests are similar to the block above. The difference is
# that the indexed column has TEXT affinity in this case. In the tests
# above the affinity is INTEGER.
#
do_test analyze3-1.2.1 {
  execsql {
    BEGIN;
      CREATE TABLE t2(x TEXT, y);
      INSERT INTO t2 SELECT * FROM t1;
      CREATE INDEX i2 ON t2(x);
    COMMIT;
    ANALYZE;
  }
} {}
do_execsql_test analyze3-2.1.x {
  SELECT count(*) FROM t2 WHERE x>1 AND x<2;
  SELECT count(*) FROM t2 WHERE x>0 AND x<99;
} {200 990}
do_eqp_test analyze3-1.2.2 {
  SELECT sum(y) FROM t2 WHERE x>1 AND x<2
} {0 0 0 {SEARCH TABLE t2 USING INDEX i2 (x>? AND x<?)}}
do_eqp_test analyze3-1.2.3 {
  SELECT sum(y) FROM t2 WHERE x>0 AND x<99
} {0 0 0 {SCAN TABLE t2}}

do_test analyze3-1.2.4 {
  sf_execsql { SELECT sum(y) FROM t2 WHERE x>12 AND x<20 }
} {161 0 4760}
do_test analyze3-1.2.5 {
  set l [string range "12" 0 end]
  set u [string range "20" 0 end]
  sf_execsql {SELECT typeof($l), typeof($u), sum(y) FROM t2 WHERE x>$l AND x<$u}
} {161 0 text text 4760}
do_test analyze3-1.2.6 {
  set l [expr int(12)]
  set u [expr int(20)]
  sf_execsql {SELECT typeof($l), typeof($u), sum(y) FROM t2 WHERE x>$l AND x<$u}
} {161 0 integer integer 4760}
do_test analyze3-1.2.7 {
  sf_execsql { SELECT sum(y) FROM t2 WHERE x>0 AND x<99 }
} {999 999 490555}
do_test analyze3-1.2.8 {
  set l [string range "0" 0 end]
  set u [string range "99" 0 end]
  sf_execsql {SELECT typeof($l), typeof($u), sum(y) FROM t2 WHERE x>$l AND x<$u}
} {999 999 text text 490555}
do_test analyze3-1.2.9 {
  set l [expr int(0)]
  set u [expr int(99)]
  sf_execsql {SELECT typeof($l), typeof($u), sum(y) FROM t2 WHERE x>$l AND x<$u}
} {999 999 integer integer 490555}

# Same tests a third time. This time, column x has INTEGER affinity and
# is not the leftmost column of the table. This triggered a bug causing
# SQLite to use sub-optimal query plans in 3.6.18 and earlier.
#
do_test analyze3-1.3.1 {
  execsql {
    BEGIN;
      CREATE TABLE t3(y TEXT, x INTEGER);
      INSERT INTO t3 SELECT y, x FROM t1;
      CREATE INDEX i3 ON t3(x);
    COMMIT;
    ANALYZE;
  }
} {}
do_execsql_test analyze3-1.3.x {
  SELECT count(*) FROM t3 WHERE x>200 AND x<300;
  SELECT count(*) FROM t3 WHERE x>0 AND x<1100
} {99 1000}
do_eqp_test analyze3-1.3.2 {
  SELECT sum(y) FROM t3 WHERE x>200 AND x<300
} {0 0 0 {SEARCH TABLE t3 USING INDEX i3 (x>? AND x<?)}}
do_eqp_test analyze3-1.3.3 {
  SELECT sum(y) FROM t3 WHERE x>0 AND x<1100
} {0 0 0 {SCAN TABLE t3}}

do_test analyze3-1.3.4 {
  sf_execsql { SELECT sum(y) FROM t3 WHERE x>200 AND x<300 }
} {199 0 14850}
do_test analyze3-1.3.5 {
  set l [string range "200" 0 end]
  set u [string range "300" 0 end]
  sf_execsql { SELECT sum(y) FROM t3 WHERE x>$l AND x<$u }
} {199 0 14850}
do_test analyze3-1.3.6 {
  set l [expr int(200)]
  set u [expr int(300)]
  sf_execsql { SELECT sum(y) FROM t3 WHERE x>$l AND x<$u }
} {199 0 14850}
do_test analyze3-1.3.7 {
  sf_execsql { SELECT sum(y) FROM t3 WHERE x>0 AND x<1100 }
} {999 999 499500}
do_test analyze3-1.3.8 {
  set l [string range "0" 0 end]
  set u [string range "1100" 0 end]
  sf_execsql { SELECT sum(y) FROM t3 WHERE x>$l AND x<$u }
} {999 999 499500}
do_test analyze3-1.3.9 {
  set l [expr int(0)]
  set u [expr int(1100)]
  sf_execsql { SELECT sum(y) FROM t3 WHERE x>$l AND x<$u }
} {999 999 499500}

#-------------------------------------------------------------------------
# Test that the values of bound SQL variables may be used for the LIKE
# optimization.
#
drop_all_tables
do_test analyze3-2.1 {

#-------------------------------------------------------------------------
# Check that affinities are taken into account when using stat4 data to
# estimate the number of rows scanned by a rowid constraint.
#
drop_all_tables
do_test 13.1 {
  execsql {
    CREATE TABLE t1(a, b, c, d);
    CREATE INDEX i1 ON t1(a);
    CREATE INDEX i2 ON t1(b, c);
  }
  for {set i 0} {$i<100} {incr i} {
    if {$i %2} {set a abc} else {set a def}
    execsql { INSERT INTO t1(rowid, a, b, c) VALUES($i, $a, $i, $i) }
  }
  execsql ANALYZE
} {}
do_eqp_test 13.2.1 {
  SELECT * FROM t1 WHERE a='abc' AND rowid<15 AND b<12
} {/SEARCH TABLE t1 USING INDEX i1/}
do_eqp_test 13.2.2 {
  SELECT * FROM t1 WHERE a='abc' AND rowid<'15' AND b<12
} {/SEARCH TABLE t1 USING INDEX i1/}
do_eqp_test 13.3.1 {
  SELECT * FROM t1 WHERE a='abc' AND rowid<100 AND b<12
} {/SEARCH TABLE t1 USING INDEX i2/}
do_eqp_test 13.3.2 {
  SELECT * FROM t1 WHERE a='abc' AND rowid<'100' AND b<12
} {/SEARCH TABLE t1 USING INDEX i2/}

#-------------------------------------------------------------------------
# Check also that affinities are taken into account when using stat4 data 
# to estimate the number of rows scanned by any other constraint on a 
# column other than the leftmost.
#

  db status autoindex
} {0}
do_test autoindex1-210 {
  db eval {
    PRAGMA automatic_index=ON;
    ANALYZE;
    UPDATE sqlite_stat1 SET stat='10000' WHERE tbl='t1';
    -- Table t2 actually contains 8 rows.
    UPDATE sqlite_stat1 SET stat='16' WHERE tbl='t2';
    ANALYZE sqlite_master;
    SELECT b, (SELECT d FROM t2 WHERE c=a) FROM t1;
  }
} {11 911 22 922 33 933 44 944 55 955 66 966 77 977 88 988}
do_test autoindex1-211 {
  db status step
} {7}

# 2014-04-26
#
# 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.
#
#***********************************************************************
# 

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


do_execsql_test 1.1 {
  CREATE TABLE t3(id INTEGER PRIMARY KEY, b NOT NULL);
  CREATE TABLE t4(c, d, e);
  CREATE UNIQUE INDEX i3 ON t3(b);
  CREATE UNIQUE INDEX i4 ON t4(c, d);
}
do_eqp_test 1.2 {
  SELECT e FROM t3, t4 WHERE b=c ORDER BY b, d;
} {
  0 0 0 {SCAN TABLE t3 USING COVERING INDEX i3} 
  0 1 1 {SEARCH TABLE t4 USING INDEX i4 (c=?)}
}


do_execsql_test 2.1 {
  CREATE TABLE t1(a, b);
  CREATE INDEX i1 ON t1(a);
}

# It is better to use an index for ORDER BY than sort externally, even 
# if the index is a non-covering index.
do_eqp_test 2.2 {
  SELECT * FROM t1 ORDER BY a;
} {
  0 0 0 {SCAN TABLE t1 USING INDEX i1}
}

do_execsql_test 3.1 {
  CREATE TABLE t5(a INTEGER PRIMARY KEY,b,c,d,e,f,g);
  CREATE INDEX t5b ON t5(b);
  CREATE INDEX t5c ON t5(c);
  CREATE INDEX t5d ON t5(d);
  CREATE INDEX t5e ON t5(e);
  CREATE INDEX t5f ON t5(f);
  CREATE INDEX t5g ON t5(g);
}

do_eqp_test 3.2 {
  SELECT a FROM t5 
  WHERE b IS NULL OR c IS NULL OR d IS NULL 
  ORDER BY a;
} {
  0 0 0 {SEARCH TABLE t5 USING INDEX t5b (b=?)} 
  0 0 0 {SEARCH TABLE t5 USING INDEX t5c (c=?)} 
  0 0 0 {SEARCH TABLE t5 USING INDEX t5d (d=?)} 
  0 0 0 {USE TEMP B-TREE FOR ORDER BY}
}

#-------------------------------------------------------------------------
# If there is no likelihood() or stat3 data, SQLite assumes that a closed
# range scan (e.g. one constrained by "col BETWEEN ? AND ?" constraint)
# visits 1/64 of the rows in a table.
#
# Note: 1/63 =~ 0.016
# Note: 1/65 =~ 0.015
#
reset_db
do_execsql_test 4.1 {
  CREATE TABLE t1(a, b);
  CREATE INDEX i1 ON t1(a);
  CREATE INDEX i2 ON t1(b);
}
do_eqp_test 4.2 {
  SELECT * FROM t1 WHERE likelihood(a=?, 0.014) AND b BETWEEN ? AND ?;
} {
  0 0 0 {SEARCH TABLE t1 USING INDEX i1 (a=?)}
}
do_eqp_test 4.3 {
  SELECT * FROM t1 WHERE likelihood(a=?, 0.016) AND b BETWEEN ? AND ?;
} {
  0 0 0 {SEARCH TABLE t1 USING INDEX i2 (b>? AND b<?)}
}


#-------------------------------------------------------------------------
#
reset_db
do_execsql_test 5.1 {
  CREATE TABLE t2(x, y);
  CREATE INDEX t2i1 ON t2(x);
}

do_eqp_test 5.2 {
  SELECT * FROM t2 ORDER BY x, y;
} {
  0 0 0 {SCAN TABLE t2 USING INDEX t2i1} 
  0 0 0 {USE TEMP B-TREE FOR RIGHT PART OF ORDER BY}
}

do_eqp_test 5.3 {
  SELECT * FROM t2 WHERE x BETWEEN ? AND ? ORDER BY rowid;
} {
  0 0 0 {SEARCH TABLE t2 USING INDEX t2i1 (x>? AND x<?)} 
  0 0 0 {USE TEMP B-TREE FOR ORDER BY}
}

# where7.test, where8.test:
#
do_execsql_test 6.1 {
  CREATE TABLE t3(a INTEGER PRIMARY KEY, b, c);
  CREATE INDEX t3i1 ON t3(b);
  CREATE INDEX t3i2 ON t3(c);
}

do_eqp_test 6.2 {
  SELECT a FROM t3 WHERE (b BETWEEN 2 AND 4) OR c=100 ORDER BY a
} {
  0 0 0 {SEARCH TABLE t3 USING INDEX t3i1 (b>? AND b<?)} 
  0 0 0 {SEARCH TABLE t3 USING INDEX t3i2 (c=?)}
  0 0 0 {USE TEMP B-TREE FOR ORDER BY}
}

#-------------------------------------------------------------------------
#
reset_db
do_execsql_test 7.1 {
  CREATE TABLE t1(a INTEGER PRIMARY KEY,b,c,d,e,f,g);
  CREATE INDEX t1b ON t1(b);
  CREATE INDEX t1c ON t1(c);
  CREATE INDEX t1d ON t1(d);
  CREATE INDEX t1e ON t1(e);
  CREATE INDEX t1f ON t1(f);
  CREATE INDEX t1g ON t1(g);
}

do_eqp_test 7.2 {
  SELECT a FROM t1
     WHERE (b>=950 AND b<=1010) OR (b IS NULL AND c NOT NULL)
  ORDER BY a
} {
  0 0 0 {SEARCH TABLE t1 USING INDEX t1b (b>? AND b<?)} 
  0 0 0 {SEARCH TABLE t1 USING INDEX t1b (b=?)} 
  0 0 0 {USE TEMP B-TREE FOR ORDER BY}
}

#set sqlite_where_trace 0xfff
do_eqp_test 7.3 {
  SELECT rowid FROM t1
  WHERE (+b IS NULL AND c NOT NULL AND d NOT NULL)
        OR (b NOT NULL AND c IS NULL AND d NOT NULL)
        OR (b NOT NULL AND c NOT NULL AND d IS NULL)
} {
  0 0 0 {SCAN TABLE t1}
}

#-------------------------------------------------------------------------
#
reset_db
do_execsql_test 8.1 {
  CREATE TABLE composer(
    cid INTEGER PRIMARY KEY,
    cname TEXT
  );
  CREATE TABLE album(
    aid INTEGER PRIMARY KEY,
    aname TEXT
  );
  CREATE TABLE track(
    tid INTEGER PRIMARY KEY,
    cid INTEGER REFERENCES composer,
    aid INTEGER REFERENCES album,
    title TEXT
  );
  CREATE INDEX track_i1 ON track(cid);
  CREATE INDEX track_i2 ON track(aid);
}

do_eqp_test 8.2 {
  SELECT DISTINCT aname
    FROM album, composer, track
   WHERE cname LIKE '%bach%'
     AND unlikely(composer.cid=track.cid)
     AND unlikely(album.aid=track.aid);
} {
  0 0 2 {SCAN TABLE track} 
  0 1 0 {SEARCH TABLE album USING INTEGER PRIMARY KEY (rowid=?)}
  0 2 1 {SEARCH TABLE composer USING INTEGER PRIMARY KEY (rowid=?)}
  0 0 0 {USE TEMP B-TREE FOR DISTINCT}
}

#-------------------------------------------------------------------------
#
do_execsql_test 9.1 {
  CREATE TABLE t1(
    a,b,c,d,e, f,g,h,i,j,
    k,l,m,n,o, p,q,r,s,t
  );
  CREATE INDEX i1 ON t1(k,l,m,n,o,p,q,r,s,t);
}
do_test 9.2 {
  for {set i 0} {$i < 100} {incr i} {
    execsql { INSERT INTO t1 DEFAULT VALUES }
  }
  execsql {
    ANALYZE;
    CREATE INDEX i2 ON t1(a,b,c,d,e,f,g,h,i,j);
  }
} {}

set L [list a=? b=? c=? d=? e=? f=? g=? h=? i=? j=?]
foreach {tn nTerm nRow} {
  1   1 10
  2   2  9
  3   3  8
  4   4  7
  5   5  6
  6   6  5
  7   7  5
  8   8  5
  9   9  5
  10 10  5
} {
  set w [join [lrange $L 0 [expr $nTerm-1]] " AND "]
  set p1 [expr ($nRow-1) / 100.0]
  set p2 [expr ($nRow+1) / 100.0]

  set sql1 "SELECT * FROM t1 WHERE likelihood(k=?, $p1) AND $w"
  set sql2 "SELECT * FROM t1 WHERE likelihood(k=?, $p2) AND $w"

  do_eqp_test 9.3.$tn.1 $sql1 {/INDEX i1/}
  do_eqp_test 9.3.$tn.2 $sql2 {/INDEX i2/}
}



finish_test

  0 0 0 {COMPOUND SUBQUERIES 1 AND 2 (UNION ALL)} 
}
do_eqp_test 4.2.3 {
  SELECT * FROM t1 UNION SELECT * FROM t2 ORDER BY 1
} {
  1 0 0 {SCAN TABLE t1} 
  1 0 0 {USE TEMP B-TREE FOR ORDER BY}
  2 0 0 {SCAN TABLE t2 USING INDEX t2i1} 
  2 0 0 {USE TEMP B-TREE FOR RIGHT PART OF ORDER BY}
  0 0 0 {COMPOUND SUBQUERIES 1 AND 2 (UNION)} 
}
do_eqp_test 4.2.4 {
  SELECT * FROM t1 INTERSECT SELECT * FROM t2 ORDER BY 1
} {
  1 0 0 {SCAN TABLE t1} 
  1 0 0 {USE TEMP B-TREE FOR ORDER BY}
  2 0 0 {SCAN TABLE t2 USING INDEX t2i1} 
  2 0 0 {USE TEMP B-TREE FOR RIGHT PART OF ORDER BY}
  0 0 0 {COMPOUND SUBQUERIES 1 AND 2 (INTERSECT)} 
}
do_eqp_test 4.2.5 {
  SELECT * FROM t1 EXCEPT SELECT * FROM t2 ORDER BY 1
} {
  1 0 0 {SCAN TABLE t1} 
  1 0 0 {USE TEMP B-TREE FOR ORDER BY}
  2 0 0 {SCAN TABLE t2 USING INDEX t2i1} 
  2 0 0 {USE TEMP B-TREE FOR RIGHT PART OF ORDER BY}
  0 0 0 {COMPOUND SUBQUERIES 1 AND 2 (EXCEPT)} 
}

do_eqp_test 4.3.1 {
  SELECT x FROM t1 UNION SELECT x FROM t2
} {
  1 0 0 {SCAN TABLE t1} 

# Queries use partial indices as appropriate times.
#
do_test index6-2.1 {
  execsql {
    CREATE TABLE t2(a,b);
    INSERT INTO t2(a,b) SELECT value, value FROM nums WHERE value<1000;
    UPDATE t2 SET a=NULL WHERE b%2==0;
    CREATE INDEX t2a1 ON t2(a) WHERE a IS NOT NULL;
    SELECT count(*) FROM t2 WHERE a IS NOT NULL;
  }
} {500}
do_test index6-2.2 {
  execsql {
    EXPLAIN QUERY PLAN
    SELECT * FROM t2 WHERE a=5;
  }
} {/.* TABLE t2 USING INDEX t2a1 .*/}
ifcapable stat4||stat3 {
  execsql ANALYZE
  do_test index6-2.3stat4 {
    execsql {
      EXPLAIN QUERY PLAN
      SELECT * FROM t2 WHERE a IS NOT NULL;
    }
  } {/.* TABLE t2 USING INDEX t2a1 .*/}
} else {

  INSERT INTO sqlite_stat1 VALUES('t1','t1bc','1000000 10 9');
  INSERT INTO sqlite_stat1 VALUES('t2','t2bc','100 10 5');
  ANALYZE sqlite_master;

  EXPLAIN QUERY PLAN
  SELECT * FROM t2 WHERE a=0 ORDER BY a, b, c;
} {~/B-TREE/}

do_execsql_test 2.1b {
  EXPLAIN QUERY PLAN
  SELECT * FROM t1 WHERE likelihood(a=0, 0.05) ORDER BY a, b, c;
} {/B-TREE/}


do_execsql_test 2.2 {
  EXPLAIN QUERY PLAN
  SELECT * FROM t1 WHERE +a=0 ORDER BY a, b, c;
} {/B-TREE/}
do_execsql_test 2.3 {
  EXPLAIN QUERY PLAN

#
do_execsql_test skipscan2-1.4 {
  ANALYZE;
  -- We do not have enough people above to actually force the use
  -- of a skip-scan.  So make a manual adjustment to the stat1 table
  -- to make it seem like there are many more.
  UPDATE sqlite_stat1 SET stat='10000 5000 20' WHERE idx='people_idx1';
  UPDATE sqlite_stat1 SET stat='10000 1' WHERE idx='sqlite_autoindex_people_1';
  ANALYZE sqlite_master;
}
db cache flush
do_execsql_test skipscan2-1.5 {
  SELECT name FROM people WHERE height>=180 ORDER BY +name;
} {David Jack Patrick Quiana Xavier}
do_execsql_test skipscan2-1.5eqp {

  }
  db close
  sqlite3 db test.db
  foreach {tn sql r(ordered) r(unordered)} {
    1   "SELECT * FROM t1 ORDER BY a"
        {0 0 0 {SCAN TABLE t1 USING INDEX i1}}
        {0 0 0 {SCAN TABLE t1} 0 0 0 {USE TEMP B-TREE FOR ORDER BY}}
    2   "SELECT * FROM t1 WHERE a > 100"
        {0 0 0 {SEARCH TABLE t1 USING INDEX i1 (a>?)}}
        {0 0 0 {SCAN TABLE t1}}
    3   "SELECT * FROM t1 WHERE a = ? ORDER BY rowid"
        {0 0 0 {SEARCH TABLE t1 USING INDEX i1 (a=?)}}
        {0 0 0 {SEARCH TABLE t1 USING INDEX i1 (a=?)} 
         0 0 0 {USE TEMP B-TREE FOR ORDER BY}}
    4   "SELECT max(a) FROM t1"

# the planner into use a table for the outer loop that might be indexable
# if held until an inner loop.
# 
do_execsql_test where3-3.0 {
  CREATE TABLE t301(a INTEGER PRIMARY KEY,b,c);
  CREATE INDEX t301c ON t301(c);
  INSERT INTO t301 VALUES(1,2,3);
  INSERT INTO t301 VALUES(2,2,3);
  CREATE TABLE t302(x, y);
  INSERT INTO t302 VALUES(4,5);
  ANALYZE;
  explain query plan SELECT * FROM t302, t301 WHERE t302.x=5 AND t301.a=t302.y;
} {
  0 0 0 {SCAN TABLE t302} 
  0 1 1 {SEARCH TABLE t301 USING INTEGER PRIMARY KEY (rowid=?)}
}
do_execsql_test where3-3.1 {
  explain query plan
  SELECT * FROM t301, t302 WHERE t302.x=5 AND t301.a=t302.y;
} {
  0 0 1 {SCAN TABLE t302} 
  0 1 0 {SEARCH TABLE t301 USING INTEGER PRIMARY KEY (rowid=?)}
}
do_execsql_test where3-3.2 {
  SELECT * FROM t301 WHERE c=3 AND a IS NULL;
} {}
do_execsql_test where3-3.3 {
  SELECT * FROM t301 WHERE c=3 AND a IS NOT NULL;
} {1 2 3 2 2 3}

if 0 {  # Query planner no longer does this
# Verify that when there are multiple tables in a join which must be
# full table scans that the query planner attempts put the table with
# the fewest number of output rows as the outer loop.
#
do_execsql_test where3-4.0 {

#***********************************************************************
# 
# Test cases for query planning decisions and the unlikely() and
# likelihood() functions.

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

do_execsql_test whereG-1.0 {
  CREATE TABLE composer(
    cid INTEGER PRIMARY KEY,
    cname TEXT
  );
  CREATE TABLE album(

  INSERT INTO t4 VALUES('right'),('wrong');
  SELECT DISTINCT x
   FROM (SELECT x FROM t4 GROUP BY x)
   WHERE x='right'
   ORDER BY x;
} {right}

#-------------------------------------------------------------------------
# Test that likelihood() specifications on indexed terms are taken into 
# account by various forms of loops.
#
#   5.1.*: open ended range scans
#   5.2.*: skip-scans
#
reset_db

do_execsql_test 5.1 {
  CREATE TABLE t1(a, b, c);
  CREATE INDEX i1 ON t1(a, b);
}
do_eqp_test 5.1.2 {
  SELECT * FROM t1 WHERE a>?
} {0 0 0 {SEARCH TABLE t1 USING INDEX i1 (a>?)}}
do_eqp_test 5.1.3 {
  SELECT * FROM t1 WHERE likelihood(a>?, 0.9)
} {0 0 0 {SCAN TABLE t1}}

do_test 5.2 {
  for {set i 0} {$i < 100} {incr i} {
    execsql { INSERT INTO t1 VALUES('abc', $i, $i); }
  }
  execsql { INSERT INTO t1 SELECT 'def', b, c FROM t1; }
  execsql { ANALYZE }
} {}
do_eqp_test 5.2.2 {
  SELECT * FROM t1 WHERE likelihood(b>?, 0.01)
} {0 0 0 {SEARCH TABLE t1 USING INDEX i1 (ANY(a) AND b>?)}}
do_eqp_test 5.2.3 {
  SELECT * FROM t1 WHERE likelihood(b>?, 0.9)
} {0 0 0 {SCAN TABLE t1}}

do_eqp_test 5.3.1 {
  SELECT * FROM t1 WHERE a=?
} {0 0 0 {SEARCH TABLE t1 USING INDEX i1 (a=?)}}
do_eqp_test 5.3.2 {
  SELECT * FROM t1 WHERE likelihood(a=?, 0.9)
} {0 0 0 {SCAN TABLE t1}}

finish_test

  return (n+8)>>(3-x);
}
static LogEst logEstFromDouble(double x){
  sqlite3_uint64 a;
  LogEst e;
  assert( sizeof(x)==8 && sizeof(a)==8 );
  if( x<=0.0 ) return -32768;
  if( x<0.01 ) return -logEstFromDouble(1.0/x);
  if( x<1.0 ) return logEstFromDouble(100.0*x) - 66;
  if( x<1024.0 ) return logEstFromInteger((sqlite3_uint64)(1024.0*x)) - 100;
  if( x<=2000000000.0 ) return logEstFromInteger((sqlite3_uint64)x);
  memcpy(&a, &x, 8);
  e = (a>>52) - 1022;
  return e*10;
}

    }else if( isFloat(z) && z[0]!='-' ){
      a[n++] = logEstFromDouble(atof(z));
    }else{
      showHelp(argv[0]);
    }
  }
  for(i=n-1; i>=0; i--){
    if( a[i]<-40 ){
      printf("%5d (%f)\n", a[i], 1.0/(double)logEstToInt(-a[i]));
    }else if( a[i]<10 ){
      printf("%5d (%f)\n", a[i], logEstToInt(a[i]+100)/1024.0);
    }else{
      sqlite3_uint64 x = logEstToInt(a[i]+100)*100/1024;
      printf("%5d (%lld.%02lld)\n", a[i], x/100, x%100);
    }
  }
  return 0;
}