SQLite

*/
#ifndef SQLITE_OMIT_ANALYZE
#include "sqliteInt.h"

#if defined(SQLITE_ENABLE_STAT4)
# define IsStat4     1
# define IsStat3     0

#elif defined(SQLITE_ENABLE_STAT3)
# define IsStat4     0
# define IsStat3     1

#else
# define IsStat4     0
# define IsStat3     0

# undef SQLITE_STAT4_SAMPLES
# define SQLITE_STAT4_SAMPLES 1
#endif
#define IsStat34    (IsStat3+IsStat4)  /* 1 for STAT3 or STAT4. 0 otherwise */

/*
** This routine generates code that opens the sqlite_statN tables.

      ** associated with the table zWhere. If zWhere is NULL, delete the
      ** entire contents of the table. */
      aRoot[i] = pStat->tnum;
      aCreateTbl[i] = 0;
      sqlite3TableLock(pParse, iDb, aRoot[i], 1, zTab);
      if( zWhere ){
        sqlite3NestedParse(pParse,
           "DELETE FROM %Q.%s WHERE %s=%Q",
           pDb->zName, zTab, zWhereType, zWhere
        );
      }else{
        /* The sqlite_stat[134] table already exists.  Delete all rows. */
        sqlite3VdbeAddOp2(v, OP_Clear, aRoot[i], iDb);
      }
    }
  }

  /* Open the sqlite_stat[134] tables for writing. */
  for(i=0; aTable[i].zCols; i++){
    assert( i<ArraySize(aTable) );

    sqlite3VdbeAddOp3(v, OP_OpenWrite, iStatCur+i, aRoot[i], iDb);
    sqlite3VdbeChangeP4(v, -1, (char *)3, P4_INT32);
    sqlite3VdbeChangeP5(v, aCreateTbl[i]);



  }
}

/*
** Recommended number of samples for sqlite_stat4
*/
#ifndef SQLITE_STAT4_SAMPLES
# define SQLITE_STAT4_SAMPLES 24
#endif

/*
** Three SQL functions - stat_init(), stat_push(), and stat_get() -
** share an instance of the following structure to hold their state
** information.
*/
typedef struct Stat4Accum Stat4Accum;
typedef struct Stat4Sample Stat4Sample;
struct Stat4Sample {
  tRowcnt *anEq;                  /* sqlite_stat4.nEq */
  tRowcnt *anDLt;                 /* sqlite_stat4.nDLt */
#ifdef SQLITE_ENABLE_STAT3_OR_STAT4
  tRowcnt *anLt;                  /* sqlite_stat4.nLt */
  i64 iRowid;                     /* Rowid in main table of the key */
  u8 isPSample;                   /* True if a periodic sample */
  int iCol;                       /* If !isPSample, the reason for inclusion */
  u32 iHash;                      /* Tiebreaker hash */
#endif
};                                                    

  int argc,
  sqlite3_value **argv
){
  Stat4Accum *p;
  int nCol;                       /* Number of columns in index being sampled */
  int nColUp;                     /* nCol rounded up for alignment */
  int n;                          /* Bytes of space to allocate */
#ifdef SQLITE_ENABLE_STAT3_OR_STAT4
  int mxSample = SQLITE_STAT4_SAMPLES;
#endif

  /* Decode the three function arguments */
  UNUSED_PARAMETER(argc);
  nCol = sqlite3_value_int(argv[0]);
  assert( nCol>1 );               /* >1 because it includes the rowid column */
  nColUp = sizeof(tRowcnt)<8 ? (nCol+1)&~1 : nCol;

  /* Allocate the space required for the Stat4Accum object */
  n = sizeof(*p) 
    + sizeof(tRowcnt)*nColUp                  /* Stat4Accum.anEq */
    + sizeof(tRowcnt)*nColUp                  /* Stat4Accum.anDLt */
#ifdef SQLITE_ENABLE_STAT3_OR_STAT4
    + sizeof(tRowcnt)*nColUp                  /* Stat4Accum.anLt */
    + sizeof(Stat4Sample)*(nCol+mxSample)   /* Stat4Accum.aBest[], a[] */
    + sizeof(tRowcnt)*3*nColUp*(nCol+mxSample)
#endif
  ;
  p = sqlite3MallocZero(n);
  if( p==0 ){
    sqlite3_result_error_nomem(context);
    return;
  }

  p->nRow = 0;
  p->nCol = nCol;
  p->current.anDLt = (tRowcnt*)&p[1];
  p->current.anEq = &p->current.anDLt[nColUp];

#ifdef SQLITE_ENABLE_STAT3_OR_STAT4
  {
    u8 *pSpace;                     /* Allocated space not yet assigned */
    int i;                          /* Used to iterate through p->aSample[] */

    p->iGet = -1;
    p->mxSample = mxSample;
    p->nPSample = sqlite3_value_int64(argv[1])/(mxSample/3+1) + 1;

  0,               /* xStep */
  0,               /* xFinalize */
  "stat_init",     /* zName */
  0,               /* pHash */
  0                /* pDestructor */
};

#ifdef SQLITE_ENABLE_STAT3_OR_STAT4
/*
** Return true if pNew is to be preferred over pOld.
*/
static int sampleIsBetter(Stat4Sample *pNew, Stat4Sample *pOld){
  tRowcnt nEqNew = pNew->anEq[pNew->iCol];
  tRowcnt nEqOld = pOld->anEq[pOld->iCol];

        iMin = i;
      }
    }
    assert( iMin>=0 );
    p->iMin = iMin;
  }
}
#endif /* SQLITE_ENABLE_STAT3_OR_STAT4 */

/*
** Field iChng of the index being scanned has changed. So at this point
** p->current contains a sample that reflects the previous row of the
** index. The value of anEq[iChng] and subsequent anEq[] elements are
** correct at this point.
*/

    /* Update anDLt[], anLt[] and anEq[] to reflect the values that apply
    ** to the current row of the index. */
    for(i=0; i<iChng; i++){
      p->current.anEq[i]++;
    }
    for(i=iChng; i<p->nCol; i++){
      p->current.anDLt[i]++;
#ifdef SQLITE_ENABLE_STAT3_OR_STAT4
      p->current.anLt[i] += p->current.anEq[i];
#endif
      p->current.anEq[i] = 1;
    }
  }
  p->nRow++;
#ifdef SQLITE_ENABLE_STAT3_OR_STAT4
  p->current.iRowid = sqlite3_value_int64(argv[2]);
  p->current.iHash = p->iPrn = p->iPrn*1103515245 + 12345;
#endif

#ifdef SQLITE_ENABLE_STAT4
  {
    tRowcnt nLt = p->current.anLt[p->nCol-1];

*/
static void statGet(
  sqlite3_context *context,
  int argc,
  sqlite3_value **argv
){
  Stat4Accum *p = (Stat4Accum*)sqlite3_value_blob(argv[0]);
#ifdef SQLITE_ENABLE_STAT3_OR_STAT4
  /* STAT3 and STAT4 have a parameter on this routine. */
  int eCall = sqlite3_value_int(argv[1]);
  assert( argc==2 );
  assert( eCall==STAT_GET_STAT1 || eCall==STAT_GET_NEQ 
       || eCall==STAT_GET_ROWID || eCall==STAT_GET_NLT
       || eCall==STAT_GET_NDLT 
  );

      z += sqlite3Strlen30(z);
      assert( p->current.anEq[i] );
    }
    assert( z[0]=='\0' && z>zRet );

    sqlite3_result_text(context, zRet, -1, sqlite3_free);
  }
#ifdef SQLITE_ENABLE_STAT3_OR_STAT4
  else if( eCall==STAT_GET_ROWID ){
    if( p->iGet<0 ){
      samplePushPrevious(p, 0);
      p->iGet = 0;
    }
    if( p->iGet<p->nSample ){
      sqlite3_result_int64(context, p->a[p->iGet].iRowid);

        }
        assert( z[0]=='\0' && z>zRet );
        z[-1] = '\0';
        sqlite3_result_text(context, zRet, -1, sqlite3_free);
      }
    }
  }
#endif /* SQLITE_ENABLE_STAT3_OR_STAT4 */
}
static const FuncDef statGetFuncdef = {
  1+IsStat34,      /* nArg */
  SQLITE_UTF8,     /* iPrefEnc */
  0,               /* flags */
  0,               /* pUserData */
  0,               /* pNext */
  statGet,         /* xFunc */
  0,               /* xStep */
  0,               /* xFinalize */
  "stat_get",      /* zName */
  0,               /* pHash */
  0                /* pDestructor */
};

static void callStatGet(Vdbe *v, int regStat4, int iParam, int regOut){
  assert( regOut!=regStat4 && regOut!=regStat4+1 );
#ifdef SQLITE_ENABLE_STAT3_OR_STAT4
  sqlite3VdbeAddOp2(v, OP_Integer, iParam, regStat4+1);
#else
  assert( iParam==STAT_GET_STAT1 );
#endif
  sqlite3VdbeAddOp3(v, OP_Function, 0, regStat4, regOut);
  sqlite3VdbeChangeP4(v, -1, (char*)&statGetFuncdef, P4_FUNCDEF);
  sqlite3VdbeChangeP5(v, 1 + IsStat34);

  int i;                       /* Loop counter */
  int jZeroRows = -1;          /* Jump from here if number of rows is zero */
  int iDb;                     /* Index of database containing pTab */
  u8 needTableCnt = 1;         /* True to count the table */
  int regNewRowid = iMem++;    /* Rowid for the inserted record */
  int regStat4 = iMem++;       /* Register to hold Stat4Accum object */
  int regChng = iMem++;        /* Index of changed index field */
#ifdef SQLITE_ENABLE_STAT3_OR_STAT4
  int regRowid = iMem++;       /* Rowid argument passed to stat_push() */
#endif
  int regTemp = iMem++;        /* Temporary use register */
  int regTabname = iMem++;     /* Register containing table name */
  int regIdxname = iMem++;     /* Register containing index name */
  int regStat1 = iMem++;       /* Value for the stat column of sqlite_stat1 */
  int regPrev = iMem;          /* MUST BE LAST (see below) */

    /* Invoke the stat_init() function. The arguments are:
    ** 
    **    (1) the number of columns in the index including the rowid,
    **    (2) the number of rows in the index,
    **
    ** The second argument is only used for STAT3 and STAT4
    */
#ifdef SQLITE_ENABLE_STAT3_OR_STAT4
    sqlite3VdbeAddOp2(v, OP_Count, iIdxCur, regStat4+2);
#endif
    sqlite3VdbeAddOp2(v, OP_Integer, nCol+1, regStat4+1);
    sqlite3VdbeAddOp3(v, OP_Function, 0, regStat4+1, regStat4);
    sqlite3VdbeChangeP4(v, -1, (char*)&statInitFuncdef, P4_FUNCDEF);
    sqlite3VdbeChangeP5(v, 1+IsStat34);

    **  chng_addr_N:
    **   regRowid = idx(rowid)            // STAT34 only
    **   stat_push(P, regChng, regRowid)  // 3rd parameter STAT34 only
    **   Next csr
    **   if !eof(csr) goto next_row;
    */
    sqlite3VdbeJumpHere(v, aGotoChng[nCol]);
#ifdef SQLITE_ENABLE_STAT3_OR_STAT4
    sqlite3VdbeAddOp2(v, OP_IdxRowid, iIdxCur, regRowid);
    assert( regRowid==(regStat4+2) );
#endif
    assert( regChng==(regStat4+1) );
    sqlite3VdbeAddOp3(v, OP_Function, 1, regStat4, regTemp);
    sqlite3VdbeChangeP4(v, -1, (char*)&statPushFuncdef, P4_FUNCDEF);
    sqlite3VdbeChangeP5(v, 2+IsStat34);
    sqlite3VdbeAddOp2(v, OP_Next, iIdxCur, addrNextRow);

    /* Add the entry to the stat1 table. */
    callStatGet(v, regStat4, STAT_GET_STAT1, regStat1);
    sqlite3VdbeAddOp4(v, OP_MakeRecord, regTabname, 3, regTemp, "aaa", 0);
    sqlite3VdbeAddOp2(v, OP_NewRowid, iStatCur, regNewRowid);
    sqlite3VdbeAddOp3(v, OP_Insert, iStatCur, regTemp, regNewRowid);
    sqlite3VdbeChangeP5(v, OPFLAG_APPEND);

    /* Add the entries to the stat3 or stat4 table. */
#ifdef SQLITE_ENABLE_STAT3_OR_STAT4
    {
      int regEq = regStat1;
      int regLt = regStat1+1;
      int regDLt = regStat1+2;
      int regSample = regStat1+3;
      int regCol = regStat1+4;
      int regSampleRowid = regCol + nCol;

#endif
      sqlite3VdbeAddOp4(v, OP_MakeRecord, regTabname, 6, regTemp, "bbbbbb", 0);
      sqlite3VdbeAddOp2(v, OP_NewRowid, iStatCur+1, regNewRowid);
      sqlite3VdbeAddOp3(v, OP_Insert, iStatCur+1, regTemp, regNewRowid);
      sqlite3VdbeAddOp2(v, OP_Goto, 0, addrNext);
      sqlite3VdbeJumpHere(v, addrIsNull);
    }
#endif /* SQLITE_ENABLE_STAT3_OR_STAT4 */

    /* End of analysis */
    sqlite3VdbeJumpHere(v, addrRewind);
    sqlite3DbFree(db, aGotoChng);
  }

){
  char *z = zIntArray;
  int c;
  int i;
  tRowcnt v;

  assert( pbUnordered==0 || *pbUnordered==0 );

  if( NEVER(z==0) ) z = "";
  for(i=0; *z && i<nOut; i++){
    v = 0;
    while( (c=z[0])>='0' && c<='9' ){
      v = v*10 + c - '0';
      z++;
    }
    aOut[i] = v;

  }else{
    pIndex = 0;
  }
  z = argv[2];

  if( pIndex ){
    int bUnordered = 0;
    decodeIntArray((char*)z, pIndex->nColumn+1, pIndex->aiRowEst,&bUnordered);
    if( pIndex->pPartIdxWhere==0 ) pTable->nRowEst = pIndex->aiRowEst[0];
    pIndex->bUnordered = bUnordered;
  }else{
    decodeIntArray((char*)z, 1, &pTable->nRowEst, 0);
  }

  return 0;
}

/*
** If the Index.aSample variable is not NULL, delete the aSample[] array
** and its contents.
*/
void sqlite3DeleteIndexSamples(sqlite3 *db, Index *pIdx){
#ifdef SQLITE_ENABLE_STAT3_OR_STAT4
  if( pIdx->aSample ){
    int j;
    for(j=0; j<pIdx->nSample; j++){
      IndexSample *p = &pIdx->aSample[j];
      sqlite3DbFree(db, p->p);
    }
    sqlite3DbFree(db, pIdx->aSample);
  }
  if( db && db->pnBytesFreed==0 ){
    pIdx->nSample = 0;
    pIdx->aSample = 0;
  }
#else
  UNUSED_PARAMETER(db);
  UNUSED_PARAMETER(pIdx);
#endif /* SQLITE_ENABLE_STAT3_OR_STAT4 */
}

#ifdef SQLITE_ENABLE_STAT3_OR_STAT4
/*
** Populate the pIdx->aAvgEq[] array based on the samples currently
** stored in pIdx->aSample[]. 
*/
static void initAvgEq(Index *pIdx){
  if( pIdx ){
    IndexSample *aSample = pIdx->aSample;

      "SELECT idx,neq,nlt,ndlt,sqlite_record(sample) FROM %Q.sqlite_stat3",
      zDb
    );
  }

  return rc;
}
#endif /* SQLITE_ENABLE_STAT3_OR_STAT4 */

/*
** Load the content of the sqlite_stat1 and sqlite_stat3/4 tables. The
** contents of sqlite_stat1 are used to populate the Index.aiRowEst[]
** arrays. The contents of sqlite_stat3/4 are used to populate the
** Index.aSample[] arrays.
**

  assert( db->aDb[iDb].pBt!=0 );

  /* Clear any prior statistics */
  assert( sqlite3SchemaMutexHeld(db, iDb, 0) );
  for(i=sqliteHashFirst(&db->aDb[iDb].pSchema->idxHash);i;i=sqliteHashNext(i)){
    Index *pIdx = sqliteHashData(i);
    sqlite3DefaultRowEst(pIdx);
#ifdef SQLITE_ENABLE_STAT3_OR_STAT4
    sqlite3DeleteIndexSamples(db, pIdx);
    pIdx->aSample = 0;
#endif
  }

  /* Check to make sure the sqlite_stat1 table exists */
  sInfo.db = db;

  }else{
    rc = sqlite3_exec(db, zSql, analysisLoader, &sInfo, 0);
    sqlite3DbFree(db, zSql);
  }


  /* Load the statistics from the sqlite_stat4 table. */
#ifdef SQLITE_ENABLE_STAT3_OR_STAT4
  if( rc==SQLITE_OK ){
    int lookasideEnabled = db->lookaside.bEnabled;
    db->lookaside.bEnabled = 0;
    rc = loadStat4(db, sInfo.zDatabase);
    db->lookaside.bEnabled = lookasideEnabled;
  }
#endif

# define SQLITE_DEFAULT_MMAP_SIZE_xc 1  /* Exclude from ctime.c */
#endif
#if SQLITE_DEFAULT_MMAP_SIZE>SQLITE_MAX_MMAP_SIZE
# undef SQLITE_DEFAULT_MMAP_SIZE
# define SQLITE_DEFAULT_MMAP_SIZE SQLITE_MAX_MMAP_SIZE
#endif

/*
** Only one of SQLITE_ENABLE_STAT3 or SQLITE_ENABLE_STAT4 can be defined.
** Priority is given to SQLITE_ENABLE_STAT4.  If either are defined, also
** define SQLITE_ENABLE_STAT3_OR_STAT4
*/
#ifdef SQLITE_ENABLE_STAT4
# undef SQLITE_ENABLE_STAT3
# define SQLITE_ENABLE_STAT3_OR_STAT4 1
#elif SQLITE_ENABLE_STAT3
# define SQLITE_ENABLE_STAT3_OR_STAT4 1
#elif SQLITE_ENABLE_STAT3_OR_STAT4
# undef SQLITE_ENABLE_STAT3_OR_STAT4
#endif

/*
** An instance of the following structure is used to store the busy-handler
** callback for a given sqlite handle. 
**
** The sqlite.busyHandler member of the sqlite struct contains the busy
** callback for the database handle. Each pager opened via the sqlite
** handle is passed a pointer to sqlite.busyHandler. The busy-handler

  Expr *pPartIdxWhere;     /* WHERE clause for partial indices */
  int tnum;                /* DB Page containing root of this index */
  u16 nColumn;             /* Number of columns in table used by this index */
  u8 onError;              /* OE_Abort, OE_Ignore, OE_Replace, or OE_None */
  unsigned autoIndex:2;    /* 1==UNIQUE, 2==PRIMARY KEY, 0==CREATE INDEX */
  unsigned bUnordered:1;   /* Use this index for == or IN queries only */
  unsigned uniqNotNull:1;  /* True if UNIQUE and NOT NULL for all columns */
#ifdef SQLITE_ENABLE_STAT3_OR_STAT4
  int nSample;             /* Number of elements in aSample[] */
  int nSampleCol;          /* Size of IndexSample.anEq[] and so on */
  tRowcnt *aAvgEq;         /* Average nEq values for keys not in aSample */
  IndexSample *aSample;    /* Samples of the left-most key */
#endif
};

void sqlite3StrAccumReset(StrAccum*);
void sqlite3SelectDestInit(SelectDest*,int,int);
Expr *sqlite3CreateColumnExpr(sqlite3 *, SrcList *, int, int);

void sqlite3BackupRestart(sqlite3_backup *);
void sqlite3BackupUpdate(sqlite3_backup *, Pgno, const u8 *);

#ifdef SQLITE_ENABLE_STAT3_OR_STAT4
void sqlite3AnalyzeFunctions(void);
int sqlite3Stat4ProbeSetValue(Parse*,Index*,UnpackedRecord**,Expr*,u8,int,int*);
void sqlite3Stat4ProbeFree(UnpackedRecord*);
#endif

/*
** The interface to the LEMON-generated parser

** Otherwise, if the second argument is non-zero, then this function is 
** being called indirectly by sqlite3Stat4ProbeSetValue(). If it has not
** already been allocated, allocate the UnpackedRecord structure that 
** that function will return to its caller here. Then return a pointer 
** an sqlite3_value within the UnpackedRecord.a[] array.
*/
static sqlite3_value *valueNew(sqlite3 *db, struct ValueNewStat4Ctx *p){
#ifdef SQLITE_ENABLE_STAT3_OR_STAT4
  if( p ){
    UnpackedRecord *pRec = p->ppRec[0];

    if( pRec==0 ){
      Index *pIdx = p->pIdx;      /* Index being probed */
      int nByte;                  /* Bytes of space to allocate */
      int i;                      /* Counter variable */

  }
  op = pExpr->op;

  /* op can only be TK_REGISTER if we have compiled with SQLITE_ENABLE_STAT4.
  ** The ifdef here is to enable us to achieve 100% branch test coverage even
  ** when SQLITE_ENABLE_STAT4 is omitted.
  */
#ifdef SQLITE_ENABLE_STAT3_OR_STAT4
  if( op==TK_REGISTER ) op = pExpr->op2;
#else
  if( NEVER(op==TK_REGISTER) ) op = pExpr->op2;
#endif

  /* Handle negative integers in a single step.  This is needed in the
  ** case when the value is -9223372036854775808.

  *ppVal = pVal;
  return rc;

no_mem:
  db->mallocFailed = 1;
  sqlite3DbFree(db, zVal);
  assert( *ppVal==0 );
#ifdef SQLITE_ENABLE_STAT3_OR_STAT4
  if( pCtx==0 ) sqlite3ValueFree(pVal);
#else
  assert( pCtx==0 ); sqlite3ValueFree(pVal);
#endif
  return SQLITE_NOMEM;
}

/*
** Create a new sqlite3_value object, containing the value of pExpr.
**
** This only works for very simple expressions that consist of one constant

  u8 enc,                   /* Encoding to use */
  u8 affinity,              /* Affinity to use */
  sqlite3_value **ppVal     /* Write the new value here */
){
  return valueFromExpr(db, pExpr, enc, affinity, ppVal, 0);
}

#ifdef SQLITE_ENABLE_STAT3_OR_STAT4
/*
** The implementation of the sqlite_record() function. This function accepts
** a single argument of any type. The return value is a formatted database 
** record (a blob) containing the argument value.
**
** This is used to convert the value stored in the 'sample' column of the
** sqlite_stat3 table to the record format SQLite uses internally.

#define TERM_DYNAMIC    0x01   /* Need to call sqlite3ExprDelete(db, pExpr) */
#define TERM_VIRTUAL    0x02   /* Added by the optimizer.  Do not code */
#define TERM_CODED      0x04   /* This term is already coded */
#define TERM_COPIED     0x08   /* Has a child */
#define TERM_ORINFO     0x10   /* Need to free the WhereTerm.u.pOrInfo object */
#define TERM_ANDINFO    0x20   /* Need to free the WhereTerm.u.pAndInfo obj */
#define TERM_OR_OK      0x40   /* Used during OR-clause processing */
#ifdef SQLITE_ENABLE_STAT3_OR_STAT4
#  define TERM_VNULL    0x80   /* Manufactured x>NULL or x<=NULL term */
#else
#  define TERM_VNULL    0x00   /* Disabled if not using stat3 */
#endif

/*
** An instance of the WhereScan object is used as an iterator for locating

*/
struct WhereLoopBuilder {
  WhereInfo *pWInfo;        /* Information about this WHERE */
  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_STAT3_OR_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

      pTerm->nChild = 1;
      pTerm->wtFlags |= TERM_COPIED;
      pNewTerm->prereqAll = pTerm->prereqAll;
    }
  }
#endif /* SQLITE_OMIT_VIRTUALTABLE */

#ifdef SQLITE_ENABLE_STAT3_OR_STAT4
  /* When sqlite_stat3 histogram data is available an operator of the
  ** form "x IS NOT NULL" can sometimes be evaluated more efficiently
  ** as "x>NULL" if x is not an INTEGER PRIMARY KEY.  So construct a
  ** virtual term of that form.
  **
  ** Note that the virtual term must be tagged with TERM_VNULL.  This
  ** TERM_VNULL tag will suppress the not-null check at the beginning

      pNewTerm->iParent = idxTerm;
      pTerm = &pWC->a[idxTerm];
      pTerm->nChild = 1;
      pTerm->wtFlags |= TERM_COPIED;
      pNewTerm->prereqAll = pTerm->prereqAll;
    }
  }
#endif /* SQLITE_ENABLE_STAT3_OR_STAT4 */

  /* Prevent ON clause terms of a LEFT JOIN from being used to drive
  ** an index for tables to the left of the join.
  */
  pTerm->prereqRight |= extraRight;
}

  }

  return pParse->nErr;
}
#endif /* !defined(SQLITE_OMIT_VIRTUALTABLE) */


#ifdef SQLITE_ENABLE_STAT3_OR_STAT4
/*
** Estimate the location of a particular key among all keys in an
** index.  Store the results in aStat as follows:
**
**    aStat[0]      Est. number of rows less than pVal
**    aStat[1]      Est. number of rows equal to pVal
**

      iGap = (iGap*2)/3;
    }else{
      iGap = iGap/3;
    }
    aStat[0] = iLower + iGap;
  }
}
#endif /* SQLITE_ENABLE_STAT3_OR_STAT4 */

/*
** 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):

  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_STAT3_OR_STAT4
  Index *p = pBuilder->pNew->u.btree.pIndex;
  int nEq = pBuilder->pNew->u.btree.nEq;

  if( nEq==pBuilder->nRecValid
   && nEq<p->nSampleCol
   && p->nSample 
   && OptimizationEnabled(pParse->db, SQLITE_Stat3) 

    nOut -= 20;        assert( 20==whereCost(4) );
  }
  if( nOut<10 ) nOut = 10;
  *pnOut = (WhereCost)nOut;
  return rc;
}

#ifdef SQLITE_ENABLE_STAT3_OR_STAT4
/*
** 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_stat3 histogram data is available
** for that index.  When pExpr==NULL that means the constraint is
** "x IS NULL" instead of "x=VALUE".

  whereKeyStats(pParse, p, pRec, 0, a);
  WHERETRACE(0x100,("equality scan regions: %d\n", (int)a[1]));
  *pnRow = a[1];
  
  return rc;
}
#endif /* SQLITE_ENABLE_STAT3_OR_STAT4 */

#ifdef SQLITE_ENABLE_STAT3_OR_STAT4
/*
** Estimate the number of rows that will be returned based on
** an IN constraint where the right-hand side of the IN operator
** is a list of values.  Example:
**
**        WHERE x IN (1,2,3,4)
**

    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 /* SQLITE_ENABLE_STAT3_OR_STAT4 */

/*
** Disable a term in the WHERE clause.  Except, do not disable the term
** if it controls a LEFT OUTER JOIN and it did not originate in the ON
** or USING clause of that join.
**
** Consider the term t2.z='ok' in the following queries:

  saved_wsFlags = pNew->wsFlags;
  saved_prereq = pNew->prereq;
  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_STAT3_OR_STAT4
    int nRecValid = pBuilder->nRecValid;
    assert( pNew->nOut==saved_nOut );
    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->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_STAT3_OR_STAT4
    if( nInMul==0 
     && pProbe->nSample 
     && pNew->u.btree.nEq<=pProbe->nSampleCol
     && OptimizationEnabled(db, SQLITE_Stat3) 
    ){
      Expr *pExpr = pTerm->pExpr;
      tRowcnt nOut = 0;

    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);
    }
    pNew->nOut = saved_nOut;
#ifdef SQLITE_ENABLE_STAT3_OR_STAT4
    pBuilder->nRecValid = nRecValid;
#endif
  }
  pNew->prereq = saved_prereq;
  pNew->u.btree.nEq = saved_nEq;
  pNew->wsFlags = saved_wsFlags;
  pNew->nOut = saved_nOut;

        }
        rc = whereLoopInsert(pBuilder, pNew);
        if( rc ) break;
      }
    }

    rc = whereLoopAddBtreeIndex(pBuilder, pSrc, pProbe, 0);
#ifdef SQLITE_ENABLE_STAT3_OR_STAT4
    sqlite3Stat4ProbeFree(pBuilder->pRec);
    pBuilder->nRecValid = 0;
    pBuilder->pRec = 0;
#endif

    /* If there was an INDEXED BY clause, then only that one index is
    ** considered. */