SQLite

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

/*
** This routine generates code that opens the sqlite_stat1 table for
** writing with cursor iStatCur. If the library was built with the
** SQLITE_ENABLE_STAT4 macro defined, then the sqlite_stat4 table is
** opened for writing using cursor (iStatCur+1)
**
** If the sqlite_stat1 tables does not previously exist, it is created.
** Similarly, if the sqlite_stat4 table does not exist and the library
** is compiled with SQLITE_ENABLE_STAT4 defined, it is created. 
**
** Argument zWhere may be a pointer to a buffer containing a table name,
** or it may be a NULL pointer. If it is not NULL, then all entries in
** the sqlite_stat1 and (if applicable) sqlite_stat4 tables associated
** with the named table are deleted. If zWhere==0, then code is generated
** to delete all stat table entries.
*/
static void openStatTable(
  Parse *pParse,          /* Parsing context */
  int iDb,                /* The database we are looking in */
  int iStatCur,           /* Open the sqlite_stat1 table on this cursor */
  const char *zWhere,     /* Delete entries for this table or index */
  const char *zWhereType  /* Either "tbl" or "idx" */
){
  static const struct {
    const char *zName;
    const char *zCols;
  } aTable[] = {
    { "sqlite_stat1", "tbl,idx,stat" },
#ifdef SQLITE_ENABLE_STAT4
    { "sqlite_stat4", "tbl,idx,neq,nlt,ndlt,sample" },
#endif
  };

  int aRoot[] = {0, 0};
  u8 aCreateTbl[] = {0, 0};

  int i;

      }else{
        /* The sqlite_stat[12] table already exists.  Delete all rows. */
        sqlite3VdbeAddOp2(v, OP_Clear, aRoot[i], iDb);
      }
    }
  }

  /* Open the sqlite_stat[14] tables for writing. */
  for(i=0; i<ArraySize(aTable); i++){
    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 - stat4_init(), stat4_push(), and stat4_pop() -
** share an instance of the following structure to hold their state
** information.
*/
typedef struct Stat4Accum Stat4Accum;
struct Stat4Accum {
  tRowcnt nRow;             /* Number of rows in the entire table */
  tRowcnt nPSample;         /* How often to do a periodic sample */
  int iMin;                 /* Index of entry with minimum nSumEq and hash */
  int mxSample;             /* Maximum number of samples to accumulate */
  int nSample;              /* Current number of samples */
  int nCol;                 /* Number of columns in the index */
  u32 iPrn;                 /* Pseudo-random number used for sampling */
  struct Stat4Sample {
    i64 iRowid;                /* Rowid in main table of the key */
    tRowcnt nSumEq;            /* Sum of anEq[] values */
    tRowcnt *anEq;             /* sqlite_stat4.nEq */
    tRowcnt *anLt;             /* sqlite_stat4.nLt */
    tRowcnt *anDLt;            /* sqlite_stat4.nDLt */
    u8 isPSample;              /* True if a periodic sample */
    u32 iHash;                 /* Tiebreaker hash */
  } *a;                     /* An array of samples */
};

#ifdef SQLITE_ENABLE_STAT4
/*
** Implementation of the stat4_init(C,N,S) SQL function. The three parameters
** are the number of rows in the table or index (C), the number of columns
** in the index (N) and the number of samples to accumulate (S).
**
** This routine allocates the Stat4Accum object in heap memory. The return 

** value is a pointer to the the Stat4Accum object encoded as a blob (i.e. 
** the size of the blob is sizeof(void*) bytes). 
*/
static void stat4Init(
  sqlite3_context *context,
  int argc,
  sqlite3_value **argv
){
  Stat4Accum *p;
  u8 *pSpace;                     /* Allocated space not yet assigned */
  tRowcnt nRow;                   /* Number of rows in table (C) */
  int mxSample;                   /* Maximum number of samples collected */
  int nCol;                       /* Number of columns in index being sampled */
  int n;                          /* Bytes of space to allocate */
  int i;                          /* Used to iterate through p->aSample[] */

  /* Decode the three function arguments */
  UNUSED_PARAMETER(argc);
  nRow = (tRowcnt)sqlite3_value_int64(argv[0]);
  nCol = sqlite3_value_int(argv[1]);
  mxSample = sqlite3_value_int(argv[2]);
  assert( nCol>0 );

  /* Allocate the space required for the Stat4Accum object */
  n = sizeof(*p) + (sizeof(p->a[0]) + 3*sizeof(tRowcnt)*nCol)*mxSample;
  p = sqlite3MallocZero( n );
  if( p==0 ){
    sqlite3_result_error_nomem(context);
    return;
  }

  /* Populate the new Stat4Accum object */
  p->nRow = nRow;
  p->nCol = nCol;
  p->mxSample = mxSample;
  p->nPSample = p->nRow/(mxSample/3+1) + 1;
  sqlite3_randomness(sizeof(p->iPrn), &p->iPrn);
  p->a = (struct Stat4Sample*)&p[1];
  pSpace = (u8*)(&p->a[mxSample]);
  for(i=0; i<mxSample; i++){
    p->a[i].anEq = (tRowcnt *)pSpace; pSpace += (sizeof(tRowcnt) * nCol);
    p->a[i].anLt = (tRowcnt *)pSpace; pSpace += (sizeof(tRowcnt) * nCol);
    p->a[i].anDLt = (tRowcnt *)pSpace; pSpace += (sizeof(tRowcnt) * nCol);
  }
  assert( (pSpace - (u8*)p)==n );

  /* Return a pointer to the allocated object to the caller */
  sqlite3_result_blob(context, p, sizeof(p), sqlite3_free);
}
static const FuncDef stat4InitFuncdef = {
  3,                /* nArg */
  SQLITE_UTF8,      /* iPrefEnc */
  0,                /* flags */
  0,                /* pUserData */
  0,                /* pNext */
  stat4Init,        /* xFunc */
  0,                /* xStep */
  0,                /* xFinalize */
  "stat4_init",     /* zName */
  0,                /* pHash */
  0                 /* pDestructor */
};


/*
** Implementation of the stat4_push SQL function. The arguments describe a
** single key instance. This routine makes the decision about whether or 
** not to retain this key for the sqlite_stat4 table.
** 
** The calling convention is:
**
**     stat4_push(P, rowid, ...nEq args..., ...nLt args..., ...nDLt args...)
**
** where each instance of the "...nXX args..." is replaced by an array of
** nCol arguments, where nCol is the number of columns in the index being
** sampled (if the index being sampled is "CREATE INDEX i ON t(a, b)", a 
** total of 8 arguments are passed when this function is invoked).
**
** The return value is always NULL.
*/
static void stat4Push(
  sqlite3_context *context,
  int argc,
  sqlite3_value **argv
){
  Stat4Accum *p = (Stat4Accum*)sqlite3_value_blob(argv[0]);

  i64 rowid = sqlite3_value_int64(argv[1]);
  i64 nSumEq = 0;                 /* Sum of all nEq parameters */
  struct Stat4Sample *pSample;
  u32 h;
  int iMin = p->iMin;
  int i;
  u8 isPSample = 0;
  u8 doInsert = 0;

  sqlite3_value **aEq = &argv[2];
  sqlite3_value **aLt = &argv[2+p->nCol];
  sqlite3_value **aDLt = &argv[2+p->nCol+p->nCol];

  i64 nEq = sqlite3_value_int64(aEq[p->nCol-1]);

  i64 nLt = sqlite3_value_int64(aLt[p->nCol-1]);

  UNUSED_PARAMETER(context);
  UNUSED_PARAMETER(argc);

  assert( p->nCol>0 );
  assert( argc==(2 + 3*p->nCol) );

  /* Set nSumEq to the sum of all nEq parameters. */
  for(i=0; i<p->nCol; i++){
    nSumEq += sqlite3_value_int64(aEq[i]);
  }
  if( nSumEq==0 ) return;

  /* Figure out if this sample will be used. Set isPSample to true if this
  ** is a periodic sample, or false if it is being captured because of a
  ** large nSumEq value. If the sample will not be used, return early.  */
  h = p->iPrn = p->iPrn*1103515245 + 12345;
  if( (nLt/p->nPSample)!=((nEq+nLt)/p->nPSample) ){
    doInsert = isPSample = 1;
  }else if( (p->nSample<p->mxSample)
         || (nSumEq>p->a[iMin].nSumEq)

         || (nSumEq==p->a[iMin].nSumEq && h>p->a[iMin].iHash) 
  ){
    doInsert = 1;
  }

  if( !doInsert ) return;

  /* Fill in the new Stat4Sample object. */
  if( p->nSample==p->mxSample ){
    assert( p->nSample - iMin - 1 >= 0 );
    memmove(&p->a[iMin], &p->a[iMin+1], sizeof(p->a[0])*(p->nSample-iMin-1));
    pSample = &p->a[p->nSample-1];
  }else{
    pSample = &p->a[p->nSample++];
  }
  pSample->iRowid = rowid;



  pSample->iHash = h;
  pSample->isPSample = isPSample;
  pSample->nSumEq = nSumEq;
  for(i=0; i<p->nCol; i++){
    pSample->anEq[i] = sqlite3_value_int64(aEq[i]);
    pSample->anLt[i] = sqlite3_value_int64(aLt[i]);
    pSample->anDLt[i] = sqlite3_value_int64(aDLt[i]);
  } 

  /* Find the new minimum */
  if( p->nSample==p->mxSample ){

    u32 iHash = 0;                /* Hash corresponding to iMin/nSumEq entry */


    i64 nMinEq = LARGEST_INT64;   /* Smallest nSumEq seen so far */
    assert( iMin = -1 );




    for(i=0; i<p->mxSample; i++){
      if( p->a[i].isPSample ) continue;
      if( (p->a[i].nSumEq<nMinEq)
       || (p->a[i].nSumEq==nMinEq && p->a[i].iHash<iHash)
      ){
        iMin = i;
        nMinEq = p->a[i].nSumEq;
        iHash = p->a[i].iHash;
      }
    }
    assert( iMin>=0 );
    p->iMin = iMin;
  }
}
static const FuncDef stat4PushFuncdef = {
  -1,               /* nArg */
  SQLITE_UTF8,      /* iPrefEnc */
  0,                /* flags */
  0,                /* pUserData */
  0,                /* pNext */
  stat4Push,        /* xFunc */
  0,                /* xStep */
  0,                /* xFinalize */
  "stat4_push",     /* zName */
  0,                /* pHash */
  0                 /* pDestructor */
};

/*
** Implementation of the stat3_get(P,N,...) SQL function.  This routine is
** used to query the results.  Content is returned for the Nth sqlite_stat3
** row where N is between 0 and S-1 and S is the number of samples.  The
** value returned depends on the number of arguments.
**
**   argc==2    result:  rowid
**   argc==3    result:  nEq
**   argc==4    result:  nLt
**   argc==5    result:  nDLt
*/
static void stat4Get(
  sqlite3_context *context,
  int argc,
  sqlite3_value **argv
){
  Stat4Accum *p = (Stat4Accum*)sqlite3_value_blob(argv[0]);
  int n = sqlite3_value_int(argv[1]);


  assert( p!=0 );
  if( n<p->nSample ){
    tRowcnt *aCnt = 0;
    char *zRet;
 
    switch( argc ){
      case 2:  
        sqlite3_result_int64(context, p->a[n].iRowid);
        return;
      case 3:  aCnt = p->a[n].anEq; break;
      case 4:  aCnt = p->a[n].anLt; break;
      default: aCnt = p->a[n].anDLt; break;
    }

    zRet = sqlite3MallocZero(p->nCol * 25);
    if( zRet==0 ){
      sqlite3_result_error_nomem(context);
    }else{
      int i;
      char *z = zRet;
      for(i=0; i<p->nCol; i++){
        sqlite3_snprintf(24, z, "%lld ", aCnt[i]);
        z += sqlite3Strlen30(z);
      }
      assert( z[0]=='\0' && z>zRet );
      z[-1] = '\0';
      sqlite3_result_text(context, zRet, -1, sqlite3_free);
    }
  }
}
static const FuncDef stat4GetFuncdef = {
  -1,               /* nArg */
  SQLITE_UTF8,      /* iPrefEnc */
  0,                /* flags */
  0,                /* pUserData */
  0,                /* pNext */
  stat4Get,         /* xFunc */
  0,                /* xStep */
  0,                /* xFinalize */
  "stat4_get",     /* zName */
  0,                /* pHash */
  0                 /* pDestructor */
};
#endif /* SQLITE_ENABLE_STAT4 */




/*
** Generate code to do an analysis of all indices associated with
** a single table.

  int endOfLoop;               /* The end of the loop */
  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 regTabname = iMem++;     /* Register containing table name */
  int regIdxname = iMem++;     /* Register containing index name */
  int regStat1 = iMem++;       /* The stat column of sqlite_stat1 */
#ifdef SQLITE_ENABLE_STAT4
  int regNumEq = regStat1;     /* Number of instances.  Same as regStat1 */
  int regNumLt = iMem++;       /* Number of keys less than regSample */
  int regNumDLt = iMem++;      /* Number of distinct keys less than regSample */
  int regSample = iMem++;      /* The next sample value */
  int regRowid = regSample;    /* Rowid of a sample */
  int regAccum = iMem++;       /* Register to hold Stat4Accum object */
  int regLoop = iMem++;        /* Loop counter */
  int regCount = iMem++;       /* Number of rows in the table or index */
  int regTemp1 = iMem++;       /* Intermediate register */
  int regTemp2 = iMem++;       /* Intermediate register */
  int once = 1;                /* One-time initialization */
  int shortJump = 0;           /* Instruction address */
  int iTabCur = pParse->nTab++; /* Table cursor */
#endif
  int regCol = iMem++;         /* Content of a column in analyzed table */
  int regRec = iMem++;         /* Register holding completed record */
  int regTemp = iMem++;        /* Temporary use register */
  int regNewRowid = iMem++;    /* Rowid for the inserted record */

  int regStat4 = iMem++;       /* Register to hold Stat4Accum object */

  v = sqlite3GetVdbe(pParse);
  if( v==0 || NEVER(pTab==0) ){
    return;
  }
  if( pTab->tnum==0 ){
    /* Do not gather statistics on views or virtual tables */

  /* Establish a read-lock on the table at the shared-cache level. */
  sqlite3TableLock(pParse, iDb, pTab->tnum, 0, pTab->zName);

  iIdxCur = pParse->nTab++;
  sqlite3VdbeAddOp4(v, OP_String8, 0, regTabname, 0, pTab->zName, 0);
  for(pIdx=pTab->pIndex; pIdx; pIdx=pIdx->pNext){
    int nCol;                     /* Number of columns indexed by pIdx */
    KeyInfo *pKey;                /* KeyInfo structure for pIdx */
    int addrIfNot = 0;            /* address of OP_IfNot */
    int *aChngAddr;               /* Array of jump instruction addresses */

    int regRowid;                 /* Register for rowid of current row */
    int regPrev;                  /* First in array of previous values */
    int regDLt;                   /* First in array of nDlt registers */
    int regLt;                    /* First in array of nLt registers */
    int regEq;                    /* First in array of nEq registers */
    int regCnt;                   /* Number of index entries */

    int addrGoto;

    if( pOnlyIdx && pOnlyIdx!=pIdx ) continue;
    if( pIdx->pPartIdxWhere==0 ) needTableCnt = 0;
    VdbeNoopComment((v, "Begin analysis of %s", pIdx->zName));
    nCol = pIdx->nColumn;
    aChngAddr = sqlite3DbMallocRaw(db, sizeof(int)*nCol);
    if( aChngAddr==0 ) continue;
    pKey = sqlite3IndexKeyinfo(pParse, pIdx);




    /* Open a cursor to the index to be analyzed. */
    assert( iDb==sqlite3SchemaToIndex(db, pIdx->pSchema) );
    sqlite3VdbeAddOp4(v, OP_OpenRead, iIdxCur, pIdx->tnum, iDb,
        (char *)pKey, P4_KEYINFO_HANDOFF);
    VdbeComment((v, "%s", pIdx->zName));

    /* Populate the register containing the index name. */
    sqlite3VdbeAddOp4(v, OP_String8, 0, regIdxname, 0, pIdx->zName, 0);

#ifdef SQLITE_ENABLE_STAT4
    if( once ){
      once = 0;
      sqlite3OpenTable(pParse, iTabCur, iDb, pTab, OP_OpenRead);
    }

    /* Invoke the stat4_init() function. The arguments are:
    ** 
    **     * the number of rows in the index,
    **     * the number of columns in the index,
    **     * the recommended number of samples for the stat4 table.
    */
    sqlite3VdbeAddOp2(v, OP_Count, iIdxCur, regStat4+1);
    sqlite3VdbeAddOp2(v, OP_Integer, nCol, regStat4+2);
    sqlite3VdbeAddOp2(v, OP_Integer, SQLITE_STAT4_SAMPLES, regStat4+3);
    sqlite3VdbeAddOp3(v, OP_Function, 0, regStat4+1, regStat4);

    sqlite3VdbeChangeP4(v, -1, (char*)&stat4InitFuncdef, P4_FUNCDEF);
    sqlite3VdbeChangeP5(v, 3);
#endif /* SQLITE_ENABLE_STAT4 */

    /* The block of (1 + 4*nCol) memory cells initialized here is used 
    ** as follows:
    **
    ** TODO: Update this comment:
    **
    **    iMem:                
    **        Loop counter. The number of rows visited so far, including
    **        the current row (i.e. this register is set to 1 for the
    **        first iteration of the loop).
    **
    **    iMem+1 .. iMem+nCol:
    **        Number of distinct index entries seen so far, considering
    **        the left-most N columns only, where N is between 1 and nCol,
    **        inclusive.
    **
    **    iMem+nCol+1 .. Mem+2*nCol:  
    **        Previous value of indexed columns, from left to right.
    **
    ** Cells iMem through iMem+nCol are initialized to 0. The others are 
    ** initialized to contain an SQL NULL.
    */
    regRowid = regStat4+1;        /* Rowid argument */
    regEq = regRowid+1;           /* First in array of nEq value registers */
    regLt = regEq+nCol;           /* First in array of nLt value registers */
    regDLt = regLt+nCol;          /* First in array of nDLt value registers */
    regCnt = regDLt+nCol;         /* Row counter */
    regPrev = regCnt+1;           /* First in array of prev. value registers */

    if( regPrev+1>pParse->nMem ){
      pParse->nMem = regPrev+1;
    }
    for(i=0; i<2+nCol*4; i++){
      sqlite3VdbeAddOp2(v, OP_Integer, 0, regRowid+i);
    }

    /*
    ** Loop through all entries in the b-tree index. Pseudo-code for the
    ** body of the loop is as follows:
    **
    **    foreach i IN index {
    **      regCnt += 1
    **
    **      if( regEq(0)==0 ) goto ne_0;
    **
    **      if i(0) != regPrev(0) {
    **          stat4_push(regRowid, regEq, regLt, regDLt);
    **          goto ne_0;
    **      }
    **      regEq(0) += 1
    **
    **      if i(1) != regPrev(1){
    **          stat4_push(regRowid, regEq, regLt, regDLt);
    **          goto ne_1;
    **      }
    **      regEq(1) += 1
    **    
    **      goto all_eq;
    **    
    **      ne_0:
    **        regPrev(0) = i(0)
    **        if( regEq(0) != 0 ) regDLt(0) += 1
    **        regLt(0) += regEq(0)
    **        regEq(0) = 1
    **    
    **      ne_1:
    **        regPrev(1) = $i(1)
    **        if( regEq(1) != 0 ) regDLt(1) += 1
    **        regLt(1) += regEq(1)
    **        regEq(1) = 1
    **
    **      all_eq:
    **        regRowid = i(rowid)
    **    }
    **
    **    stat4_push(regRowid, regEq, regLt, regDLt);
    **    
    **    if( regEq(0) != 0 ) regDLt(0) += 1
    **    if( regEq(1) != 0 ) regDLt(1) += 1
    **
    ** The last two lines above modify the contents of the regDLt array
    ** so that each element contains the number of distinct key prefixes
    ** of the corresponding length. As required to calculate the contents
    ** of the sqlite_stat1 entry.
    **
    ** Note: if regEq(0)==0, stat4_push() is a no-op.
    */
    endOfLoop = sqlite3VdbeMakeLabel(v);
    sqlite3VdbeAddOp2(v, OP_Rewind, iIdxCur, endOfLoop);
    topOfLoop = sqlite3VdbeCurrentAddr(v);
    sqlite3VdbeAddOp2(v, OP_AddImm, regCnt, 1);  /* Increment row counter */

    /* This jump is taken for the first iteration of the loop only.
    **
    **     if( regEq(0)==0 ) goto ne_0;
    */
    addrIfNot = sqlite3VdbeAddOp1(v, OP_IfNot, regEq);

    /* Code these bits:
    **
    **      if i(N) != regPrev(N) {
    **          stat4_push(regRowid, regEq, regLt, regDLt);
    **          goto ne_N;
    **      }
    **      regEq(N) += 1
    */
    for(i=0; i<nCol; i++){
      char *pColl;                /* Pointer to CollSeq cast to (char*) */
      assert( pIdx->azColl && pIdx->azColl[i]!=0 );
      pColl = (char*)sqlite3LocateCollSeq(pParse, pIdx->azColl[i]);

      sqlite3VdbeAddOp3(v, OP_Column, iIdxCur, i, regCol);


      sqlite3VdbeAddOp4(v, OP_Eq, regCol, 0, regPrev+i, pColl, P4_COLLSEQ);
      sqlite3VdbeChangeP5(v, SQLITE_NULLEQ);




      sqlite3VdbeAddOp3(v, OP_Function, 1, regStat4, regTemp2);
      sqlite3VdbeChangeP4(v, -1, (char*)&stat4PushFuncdef, P4_FUNCDEF);
      sqlite3VdbeChangeP5(v, 2 + 3*nCol);

      aChngAddr[i] = sqlite3VdbeAddOp0(v, OP_Goto);
      VdbeComment((v, "jump if column %d changed", i));


      sqlite3VdbeJumpHere(v, sqlite3VdbeCurrentAddr(v)-3);
      sqlite3VdbeAddOp2(v, OP_AddImm, regEq+i, 1);
      VdbeComment((v, "incr repeat count"));
    }


    /* Code the "continue" */
    addrGoto = sqlite3VdbeAddOp2(v, OP_Goto, 0, endOfLoop);

    /* And now these:
    **
    **      ne_N:
    **        regPrev(N) = i(N)
    **        if( regEq(N) != N ) regDLt(N) += 1
    **        regLt(N) += regEq(N)
    **        regEq(N) = 1
    */
    for(i=0; i<nCol; i++){
      sqlite3VdbeJumpHere(v, aChngAddr[i]);  /* Set jump dest for the OP_Ne */
      if( i==0 ){
        sqlite3VdbeJumpHere(v, addrIfNot);   /* Jump dest for OP_IfNot */




      }
      sqlite3VdbeAddOp3(v, OP_Column, iIdxCur, i, regPrev+i);
      sqlite3VdbeAddOp2(v, OP_IfNot, regEq+i, sqlite3VdbeCurrentAddr(v)+2);
      sqlite3VdbeAddOp2(v, OP_AddImm, regDLt+i, 1);
      sqlite3VdbeAddOp3(v, OP_Add, regEq+i, regLt+i, regLt+i);
      sqlite3VdbeAddOp2(v, OP_Integer, 1, regEq+i);

    }
    sqlite3DbFree(db, aChngAddr);


    /*
    **      all_eq:
    **        regRowid = i(rowid)
    */
    sqlite3VdbeJumpHere(v, addrGoto);
    sqlite3VdbeAddOp2(v, OP_IdxRowid, iIdxCur, regRowid);

    /* The end of the loop that iterates through all index entries. Always 
    ** jump here after updating the iMem+1...iMem+1+nCol counters. */
    sqlite3VdbeResolveLabel(v, endOfLoop);

    sqlite3VdbeAddOp2(v, OP_Next, iIdxCur, topOfLoop);
    sqlite3VdbeAddOp1(v, OP_Close, iIdxCur);

    /* Final invocation of stat4_push() */
    sqlite3VdbeAddOp3(v, OP_Function, 1, regStat4, regTemp2);
    sqlite3VdbeChangeP4(v, -1, (char*)&stat4PushFuncdef, P4_FUNCDEF);
    sqlite3VdbeChangeP5(v, 2 + 3*nCol);

    /* Finally:
    **
    **    if( regEq(0) != 0 ) regDLt(0) += 1
    */
    for(i=0; i<nCol; i++){
      sqlite3VdbeAddOp2(v, OP_IfNot, regEq+i, sqlite3VdbeCurrentAddr(v)+2);
      sqlite3VdbeAddOp2(v, OP_AddImm, regDLt+i, 1);
    }

#ifdef SQLITE_ENABLE_STAT4
    /* Add rows to the sqlite_stat4 table */
    regLoop = regStat4+1;
    sqlite3VdbeAddOp2(v, OP_Integer, -1, regLoop);

    shortJump = sqlite3VdbeAddOp2(v, OP_AddImm, regLoop, 1);
    sqlite3VdbeAddOp3(v, OP_Function, 0, regStat4, regTemp1);
    sqlite3VdbeChangeP4(v, -1, (char*)&stat4GetFuncdef, P4_FUNCDEF);
    sqlite3VdbeChangeP5(v, 2);
    sqlite3VdbeAddOp1(v, OP_IsNull, regTemp1);

    sqlite3VdbeAddOp3(v, OP_NotExists, iTabCur, shortJump, regTemp1);
    for(i=0; i<nCol; i++){
      int iCol = pIdx->aiColumn[i];
      sqlite3ExprCodeGetColumnOfTable(v, pTab, iTabCur, iCol, regPrev+i);
    }
    sqlite3VdbeAddOp3(v, OP_MakeRecord, regPrev, nCol, regSample);
    sqlite3VdbeChangeP4(v, -1, pIdx->zColAff, 0);

    sqlite3VdbeAddOp3(v, OP_Function, 1, regStat4, regNumEq);
    sqlite3VdbeChangeP4(v, -1, (char*)&stat4GetFuncdef, P4_FUNCDEF);
    sqlite3VdbeChangeP5(v, 3);

    sqlite3VdbeAddOp3(v, OP_Function, 1, regStat4, regNumLt);
    sqlite3VdbeChangeP4(v, -1, (char*)&stat4GetFuncdef, P4_FUNCDEF);
    sqlite3VdbeChangeP5(v, 4);

    sqlite3VdbeAddOp3(v, OP_Function, 1, regStat4, regNumDLt);
    sqlite3VdbeChangeP4(v, -1, (char*)&stat4GetFuncdef, P4_FUNCDEF);
    sqlite3VdbeChangeP5(v, 5);

    sqlite3VdbeAddOp4(v, OP_MakeRecord, regTabname, 6, regRec, "bbbbbb", 0);
    sqlite3VdbeAddOp2(v, OP_NewRowid, iStatCur+1, regNewRowid);
    sqlite3VdbeAddOp3(v, OP_Insert, iStatCur+1, regRec, regNewRowid);
    sqlite3VdbeAddOp2(v, OP_Goto, 0, shortJump);
    sqlite3VdbeJumpHere(v, shortJump+2);
#endif        

    **
    **        I = (K+D-1)/D
    **
    ** If K==0 then no entry is made into the sqlite_stat1 table.  
    ** If K>0 then it is always the case the D>0 so division by zero
    ** is never possible.
    */
    sqlite3VdbeAddOp2(v, OP_SCopy, regCnt, regStat1);
    jZeroRows = sqlite3VdbeAddOp1(v, OP_IfNot, regCnt);
    for(i=0; i<nCol; i++){
      sqlite3VdbeAddOp4(v, OP_String8, 0, regTemp, 0, " ", 0);
      sqlite3VdbeAddOp3(v, OP_Concat, regTemp, regStat1, regStat1);
      sqlite3VdbeAddOp3(v, OP_Add, regCnt, regDLt+i, regTemp);
      sqlite3VdbeAddOp2(v, OP_AddImm, regTemp, -1);
      sqlite3VdbeAddOp3(v, OP_Divide, regDLt+i, regTemp, regTemp);
      sqlite3VdbeAddOp1(v, OP_ToInt, regTemp);
      sqlite3VdbeAddOp3(v, OP_Concat, regTemp, regStat1, regStat1);
    }
    if( pIdx->pPartIdxWhere!=0 ) sqlite3VdbeJumpHere(v, jZeroRows);
    sqlite3VdbeAddOp4(v, OP_MakeRecord, regTabname, 3, regRec, "aaa", 0);
    sqlite3VdbeAddOp2(v, OP_NewRowid, iStatCur, regNewRowid);
    sqlite3VdbeAddOp3(v, OP_Insert, iStatCur, regRec, regNewRowid);

** callback routine.
*/
typedef struct analysisInfo analysisInfo;
struct analysisInfo {
  sqlite3 *db;
  const char *zDatabase;
};

/*
** The first argument points to a nul-terminated string containing a
** list of space separated integers. Read the first nOut of these into
** the array aOut[].
*/
static void decodeIntArray(
  char *zIntArray, 
  int nOut, 
  tRowcnt *aOut, 
  int *pbUnordered
){
  char *z = zIntArray;
  int c;
  int i;
  tRowcnt v;

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

  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;
    if( *z==' ' ) z++;
  }
  if( pbUnordered && strcmp(z, "unordered")==0 ){
    *pbUnordered = 1;
  }
}

/*
** This callback is invoked once for each index when reading the
** sqlite_stat1 table.  
**
**     argv[0] = name of the table
**     argv[1] = name of the index (might be NULL)
**     argv[2] = results of analysis - on integer for each column
**
** Entries for which argv[1]==NULL simply record the number of rows in
** the table.
*/
static int analysisLoader(void *pData, int argc, char **argv, char **NotUsed){
  analysisInfo *pInfo = (analysisInfo*)pData;
  Index *pIndex;
  Table *pTable;


  const char *z;

  assert( argc==3 );
  UNUSED_PARAMETER2(NotUsed, argc);

  if( argv==0 || argv[0]==0 || argv[2]==0 ){
    return 0;
  }
  pTable = sqlite3FindTable(pInfo->db, argv[0], pInfo->zDatabase);
  if( pTable==0 ){
    return 0;
  }
  if( argv[1] ){
    pIndex = sqlite3FindIndex(pInfo->db, argv[1], pInfo->zDatabase);
  }else{
    pIndex = 0;
  }

  z = argv[2];








  if( pIndex ){

    int bUnordered = 0;
    decodeIntArray((char*)z, pIndex->nColumn, 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_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
}

#ifdef SQLITE_ENABLE_STAT4
/*
** Load content from the sqlite_stat4 table into the Index.aSample[]
** arrays of all indices.
*/
static int loadStat4(sqlite3 *db, const char *zDb){
  int rc;                       /* Result codes from subroutines */
  sqlite3_stmt *pStmt = 0;      /* An SQL statement being run */
  char *zSql;                   /* Text of the SQL statement */
  Index *pPrevIdx = 0;          /* Previous index in the loop */
  int idx = 0;                  /* slot in pIdx->aSample[] for next sample */

  IndexSample *pSample;         /* A slot in pIdx->aSample[] */

  assert( db->lookaside.bEnabled==0 );
  if( !sqlite3FindTable(db, "sqlite_stat4", zDb) ){
    return SQLITE_OK;
  }

  zSql = sqlite3MPrintf(db, 
      "SELECT idx,count(*) FROM %Q.sqlite_stat4"
      " GROUP BY idx", zDb);
  if( !zSql ){
    return SQLITE_NOMEM;
  }
  rc = sqlite3_prepare(db, zSql, -1, &pStmt, 0);
  sqlite3DbFree(db, zSql);
  if( rc ) return rc;

  while( sqlite3_step(pStmt)==SQLITE_ROW ){
    char *zIndex;   /* Index name */
    Index *pIdx;    /* Pointer to the index object */
    int nSample;    /* Number of samples */
    int nByte;      /* Bytes of space required */
    int i;          /* Bytes of space required */
    tRowcnt *pSpace;

    zIndex = (char *)sqlite3_column_text(pStmt, 0);
    if( zIndex==0 ) continue;
    nSample = sqlite3_column_int(pStmt, 1);
    pIdx = sqlite3FindIndex(db, zIndex, zDb);
    if( pIdx==0 ) continue;
    assert( pIdx->nSample==0 );
    pIdx->nSample = nSample;
    nByte = sizeof(IndexSample) * nSample;
    nByte += sizeof(tRowcnt) * pIdx->nColumn * 3 * nSample;

    pIdx->aSample = sqlite3DbMallocZero(db, nByte);
    pIdx->avgEq = pIdx->aiRowEst[1];
    if( pIdx->aSample==0 ){

      sqlite3_finalize(pStmt);
      return SQLITE_NOMEM;
    }
    pSpace = (tRowcnt*)&pIdx->aSample[nSample];
    for(i=0; i<pIdx->nSample; i++){
      pIdx->aSample[i].anEq = pSpace; pSpace += pIdx->nColumn;
      pIdx->aSample[i].anLt = pSpace; pSpace += pIdx->nColumn;
      pIdx->aSample[i].anDLt = pSpace; pSpace += pIdx->nColumn;
    }
    assert( ((u8*)pSpace)-nByte==(u8*)(pIdx->aSample) );
  }
  rc = sqlite3_finalize(pStmt);
  if( rc ) return rc;

  zSql = sqlite3MPrintf(db, 
      "SELECT idx,neq,nlt,ndlt,sample FROM %Q.sqlite_stat4", zDb);
  if( !zSql ){
    return SQLITE_NOMEM;
  }
  rc = sqlite3_prepare(db, zSql, -1, &pStmt, 0);
  sqlite3DbFree(db, zSql);
  if( rc ) return rc;

  while( sqlite3_step(pStmt)==SQLITE_ROW ){
    char *zIndex;   /* Index name */
    Index *pIdx;    /* Pointer to the index object */
    int i;          /* Loop counter */
    tRowcnt sumEq;  /* Sum of the nEq values */
    int nCol;       /* Number of columns in index */

    zIndex = (char *)sqlite3_column_text(pStmt, 0);
    if( zIndex==0 ) continue;
    pIdx = sqlite3FindIndex(db, zIndex, zDb);
    if( pIdx==0 ) continue;
    if( pIdx==pPrevIdx ){
      idx++;
    }else{
      pPrevIdx = pIdx;
      idx = 0;
    }
    assert( idx<pIdx->nSample );
    pSample = &pIdx->aSample[idx];

    nCol = pIdx->nColumn;
    decodeIntArray((char*)sqlite3_column_text(pStmt,1), nCol, pSample->anEq, 0);
    decodeIntArray((char*)sqlite3_column_text(pStmt,2), nCol, pSample->anLt, 0);
    decodeIntArray((char*)sqlite3_column_text(pStmt,3), nCol, pSample->anDLt,0);

    if( idx==pIdx->nSample-1 ){
      if( pSample->anDLt[0]>0 ){
        for(i=0, sumEq=0; i<=idx-1; i++) sumEq += pIdx->aSample[i].anEq[0];
        pIdx->avgEq = (pSample->anLt[0] - sumEq)/pSample->anDLt[0];
      }
      if( pIdx->avgEq<=0 ) pIdx->avgEq = 1;
    }




















    pSample->n = sqlite3_column_bytes(pStmt, 4);


    pSample->p = sqlite3DbMallocZero(db, pSample->n);


    if( pSample->p==0 ){

      sqlite3_finalize(pStmt);
      return SQLITE_NOMEM;
    }
    memcpy(pSample->p, sqlite3_column_blob(pStmt, 4), pSample->n);



  }
  return sqlite3_finalize(pStmt);
}
#endif /* SQLITE_ENABLE_STAT4 */

/*
** Load the content of the sqlite_stat1 and sqlite_stat4 tables. The
** contents of sqlite_stat1 are used to populate the Index.aiRowEst[]
** arrays. The contents of sqlite_stat4 are used to populate the
** Index.aSample[] arrays.
**
** If the sqlite_stat1 table is not present in the database, SQLITE_ERROR
** is returned. In this case, even if SQLITE_ENABLE_STAT4 was defined 
** during compilation and the sqlite_stat4 table is present, no data is 
** read from it.
**
** If SQLITE_ENABLE_STAT4 was defined during compilation and the 
** sqlite_stat4 table is not present in the database, SQLITE_ERROR is
** returned. However, in this case, data is read from the sqlite_stat1
** table (if it is present) before returning.
**
** If an OOM error occurs, this function always sets db->mallocFailed.
** This means if the caller does not care about other errors, the return
** code may be ignored.
*/

  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_STAT4
    sqlite3DeleteIndexSamples(db, pIdx);
    pIdx->aSample = 0;
#endif
  }

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

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


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

  if( rc==SQLITE_NOMEM ){
    db->mallocFailed = 1;
  }
  return rc;
}


#endif /* SQLITE_OMIT_ANALYZE */

    pBt->max1bytePayload = 127;
  }else{
    pBt->max1bytePayload = (u8)pBt->maxLocal;
  }
  assert( pBt->maxLeaf + 23 <= MX_CELL_SIZE(pBt) );
  pBt->pPage1 = pPage1;
  pBt->nPage = nPage;
assert( pPage1->leaf==0 || pPage1->leaf==1 );
  return SQLITE_OK;

page1_init_failed:
  releasePage(pPage1);
  pBt->pPage1 = 0;
  return rc;
}

  Parse *pParse,         /* The parsing context */
  int iDb,               /* The database number */
  const char *zType,     /* "idx" or "tbl" */
  const char *zName      /* Name of index or table */
){
  int i;
  const char *zDbName = pParse->db->aDb[iDb].zName;
  for(i=1; i<=4; i++){
    char zTab[24];
    sqlite3_snprintf(sizeof(zTab),zTab,"sqlite_stat%d",i);
    if( sqlite3FindTable(pParse->db, zTab, zDbName) ){
      sqlite3NestedParse(pParse,
        "DELETE FROM %Q.%s WHERE %s=%Q",
        zDbName, zTab, zType, zName
      );

#endif
#ifdef SQLITE_ENABLE_OVERSIZE_CELL_CHECK
  "ENABLE_OVERSIZE_CELL_CHECK",
#endif
#ifdef SQLITE_ENABLE_RTREE
  "ENABLE_RTREE",
#endif
#ifdef SQLITE_ENABLE_STAT4
  "ENABLE_STAT4",
#endif
#ifdef SQLITE_ENABLE_UNLOCK_NOTIFY
  "ENABLE_UNLOCK_NOTIFY",
#endif
#ifdef SQLITE_ENABLE_UPDATE_DELETE_LIMIT
  "ENABLE_UPDATE_DELETE_LIMIT",
#endif

/*
** Each sample stored in the sqlite_stat3 table is represented in memory 
** using a structure of this type.  See documentation at the top of the
** analyze.c source file for additional information.
*/
struct IndexSample {



  void *p;          /* Pointer to sampled record */

  int n;            /* Size of record in bytes */

  tRowcnt *anEq;    /* Est. number of rows where the key equals this sample */
  tRowcnt *anLt;    /* Est. number of rows where key is less than this sample */
  tRowcnt *anDLt;   /* Est. number of distinct keys less than this sample */
};

/*
** Each token coming out of the lexer is an instance of
** this structure.  Tokens are also used as part of an expression.
**
** Note if Token.z==0 then Token.dyn and Token.n are undefined and

#ifdef SQLITE_OMIT_SCHEMA_VERSION_PRAGMAS
  Tcl_SetVar2(interp, "sqlite_options", "schema_version", "0", TCL_GLOBAL_ONLY);
#else
  Tcl_SetVar2(interp, "sqlite_options", "schema_version", "1", TCL_GLOBAL_ONLY);
#endif

#ifdef SQLITE_ENABLE_STAT4
  Tcl_SetVar2(interp, "sqlite_options", "stat4", "1", TCL_GLOBAL_ONLY);
#else
  Tcl_SetVar2(interp, "sqlite_options", "stat4", "0", TCL_GLOBAL_ONLY);
#endif

#if !defined(SQLITE_ENABLE_LOCKING_STYLE)
#  if defined(__APPLE__)
#    define SQLITE_ENABLE_LOCKING_STYLE 1
#  else
#    define SQLITE_ENABLE_LOCKING_STYLE 0

** is set to the length of the returned string in bytes. The call should
** arrange to call sqlite3DbFree() on the returned pointer when it is
** no longer required.
** 
** If a malloc failure occurs, NULL is returned and the db.mallocFailed
** flag set.
*/
#ifdef SQLITE_ENABLE_STAT4
char *sqlite3Utf8to16(sqlite3 *db, u8 enc, char *z, int n, int *pnOut){
  Mem m;
  memset(&m, 0, sizeof(m));
  m.db = db;
  sqlite3VdbeMemSetStr(&m, z, n, SQLITE_UTF8, SQLITE_STATIC);
  if( sqlite3VdbeMemTranslate(&m, enc) ){
    assert( db->mallocFailed );

** See also: Destroy
*/
case OP_Clear: {
  int nChange;
 
  nChange = 0;
  assert( p->readOnly==0 );
  assert( pOp->p1!=1 );
  assert( (p->btreeMask & (((yDbMask)1)<<pOp->p2))!=0 );
  rc = sqlite3BtreeClearTable(
      db->aDb[pOp->p2].pBt, pOp->p1, (pOp->p3 ? &nChange : 0)
  );
  if( pOp->p3 ){
    p->nChange += nChange;
    if( pOp->p3>0 ){

  if( !pExpr ){
    *ppVal = 0;
    return SQLITE_OK;
  }
  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_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.

#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_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

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

#ifdef SQLITE_ENABLE_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

  }

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


#ifdef SQLITE_ENABLE_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
**
** Return SQLITE_OK on success.
*/
static int whereKeyStats(
  Parse *pParse,              /* Database connection */
  Index *pIdx,                /* Index to consider domain of */
  sqlite3_value *pVal,        /* Value to consider */
  int roundUp,                /* Round up if true.  Round down if false */
  tRowcnt *aStat              /* OUT: stats written here */
){

  IndexSample *aSample = pIdx->aSample;
  UnpackedRecord rec;
  int i;
  int isEq = 0;





  if( pVal==0 ) return SQLITE_ERROR;





  memset(&rec, 0, sizeof(UnpackedRecord));
  rec.pKeyInfo = sqlite3IndexKeyinfo(pParse, pIdx);


  if( rec.pKeyInfo==0 ) return SQLITE_NOMEM;




















  rec.pKeyInfo->enc = ENC(pParse->db);
  rec.nField = 1;



  rec.flags = UNPACKED_PREFIX_MATCH;




  rec.aMem = pVal;






























  for(i=0; i<pIdx->nSample; i++){








    int res = sqlite3VdbeRecordCompare(aSample[i].n, aSample[i].p, &rec);












    if( res>=0 ){
      isEq = (res==0);
      break;
    }
  }


  sqlite3DbFree(pParse->db, rec.pKeyInfo);

  /* At this point, aSample[i] is the first sample that is greater than
  ** or equal to pVal.  Or if i==pIdx->nSample, then all samples are less
  ** than pVal.  If aSample[i]==pVal, then isEq==1.
  */
  if( isEq ){
    assert( i<pIdx->nSample );
    aStat[0] = aSample[i].anLt[0];
    aStat[1] = aSample[i].anEq[0];
  }else{
    tRowcnt iLower, iUpper, iGap;
    if( i==0 ){
      iLower = 0;
      iUpper = aSample[0].anLt[0];
    }else{
      iUpper = i>=pIdx->nSample ? pIdx->aiRowEst[0] : aSample[i].anLt[0];
      iLower = aSample[i-1].anEq[0] + aSample[i-1].anLt[0];
    }
    aStat[1] = pIdx->avgEq;
    if( iLower>=iUpper ){
      iGap = 0;
    }else{
      iGap = iUpper - iLower;
    }
    if( roundUp ){
      iGap = (iGap*2)/3;
    }else{
      iGap = iGap/3;
    }
    aStat[0] = iLower + iGap;
  }
  return SQLITE_OK;
}
#endif /* SQLITE_ENABLE_STAT4 */

/*
** If expression pExpr represents a literal value, set *pp to point to
** an sqlite3_value structure containing the same value, with affinity
** aff applied to it, before returning. It is the responsibility of the 
** caller to eventually release this structure by passing it to 
** sqlite3ValueFree().
**
** If the current parse is a recompile (sqlite3Reprepare()) and pExpr
** is an SQL variable that currently has a non-NULL value bound to it,
** create an sqlite3_value structure containing this value, again with
** affinity aff applied to it, instead.
**
** If neither of the above apply, set *pp to NULL.
**
** If an error occurs, return an error code. Otherwise, SQLITE_OK.
*/
#ifdef SQLITE_ENABLE_STAT4
static int valueFromExpr(
  Parse *pParse, 
  Expr *pExpr, 
  u8 aff, 
  sqlite3_value **pp
){
  if( pExpr->op==TK_VARIABLE
   || (pExpr->op==TK_REGISTER && pExpr->op2==TK_VARIABLE)
  ){
    int iVar = pExpr->iColumn;
    sqlite3VdbeSetVarmask(pParse->pVdbe, iVar);
    *pp = sqlite3VdbeGetBoundValue(pParse->pReprepare, iVar, aff);
    return SQLITE_OK;
  }
  return sqlite3ValueFromExpr(pParse->db, pExpr, ENC(pParse->db), aff, pp);
}
#endif

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

  int nEq,             /* index into p->aCol[] of the range-compared column */
  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 *pRangeDiv /* OUT: Reduce search space by this divisor */
){
  int rc = SQLITE_OK;

#ifdef SQLITE_ENABLE_STAT4

  if( nEq==0 && p->nSample && OptimizationEnabled(pParse->db, SQLITE_Stat3) ){
    sqlite3_value *pRangeVal;
    tRowcnt iLower = 0;
    tRowcnt iUpper = p->aiRowEst[0];
    tRowcnt a[2];
    u8 aff = p->pTable->aCol[p->aiColumn[0]].affinity;

  }
  if( pUpper ){
    *pRangeDiv += 20;  assert( 20==whereCost(4) );
  }
  return rc;
}

#ifdef SQLITE_ENABLE_STAT4
/*
** Estimate the number of rows that will be returned based on
** an equality constraint x=VALUE and where that VALUE occurs in
** 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".

    WHERETRACE(0x100,("equality scan regions: %d\n", (int)a[1]));
    *pnRow = a[1];
  }
whereEqualScanEst_cancel:
  sqlite3ValueFree(pRhs);
  return rc;
}
#endif /* defined(SQLITE_ENABLE_STAT4) */

#ifdef SQLITE_ENABLE_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( rc==SQLITE_OK ){
    if( nRowEst > p->aiRowEst[0] ) nRowEst = p->aiRowEst[0];
    *pnRow = nRowEst;
    WHERETRACE(0x100,("IN row estimate: est=%g\n", nRowEst));
  }
  return rc;
}
#endif /* defined(SQLITE_ENABLE_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_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;
    if( pTerm->prereqRight & pNew->maskSelf ) continue;
#ifdef SQLITE_ENABLE_STAT4
    if( (pTerm->wtFlags & TERM_VNULL)!=0 && pSrc->pTab->aCol[iCol].notNull ){
      continue; /* skip IS NOT NULL constraints on a NOT NULL column */
    }
#endif
    pNew->wsFlags = saved_wsFlags;
    pNew->u.btree.nEq = saved_nEq;
    pNew->nLTerm = saved_nLTerm;

    if( pNew->wsFlags & WHERE_COLUMN_RANGE ){
      /* Adjust nOut and rRun for STAT3 range values */
      WhereCost rDiv;
      whereRangeScanEst(pParse, pProbe, pNew->u.btree.nEq,
                        pBtm, pTop, &rDiv);
      pNew->nOut = saved_nOut>rDiv+10 ? saved_nOut - rDiv : 10;
    }
#ifdef SQLITE_ENABLE_STAT4
    if( pNew->u.btree.nEq==1 && pProbe->nSample
     &&  OptimizationEnabled(db, SQLITE_Stat3) ){
      tRowcnt nOut = 0;
      if( (pTerm->eOperator & (WO_EQ|WO_ISNULL))!=0 ){
        testcase( pTerm->eOperator & WO_EQ );
        testcase( pTerm->eOperator & WO_ISNULL );
        rc = whereEqualScanEst(pParse, pProbe, pTerm->pExpr->pRight, &nOut);

#-------------------------------------------------------------------------
# Test that it is not possible to use ALTER TABLE on any system table.
#
set system_table_list {1 sqlite_master}
catchsql ANALYZE
ifcapable analyze { lappend system_table_list 2 sqlite_stat1 }
ifcapable stat4   { lappend system_table_list 4 sqlite_stat4 }

foreach {tn tbl} $system_table_list {
  do_test alter-15.$tn.1 {
    catchsql "ALTER TABLE $tbl RENAME TO xyz"
  } [list 1 "table $tbl may not be altered"]

  do_test alter-15.$tn.2 {

  sqlite3 db test.db
  execsql {
    SELECT * FROM t4 WHERE x=1234;
  }
} {}

# Verify that DROP TABLE and DROP INDEX remove entries from the 
# sqlite_stat1 and sqlite_stat4 tables.
#
do_test analyze-5.0 {
  execsql {
    DELETE FROM t3;
    DELETE FROM t4;
    INSERT INTO t3 VALUES(1,2,3,4);
    INSERT INTO t3 VALUES(5,6,7,8);
    INSERT INTO t3 SELECT a+8, b+8, c+8, d+8 FROM t3;
    INSERT INTO t3 SELECT a+16, b+16, c+16, d+16 FROM t3;
    INSERT INTO t3 SELECT a+32, b+32, c+32, d+32 FROM t3;
    INSERT INTO t3 SELECT a+64, b+64, c+64, d+64 FROM t3;
    INSERT INTO t4 SELECT a, b, c FROM t3;
    ANALYZE;
    SELECT DISTINCT idx FROM sqlite_stat1 ORDER BY 1;
    SELECT DISTINCT tbl FROM sqlite_stat1 ORDER BY 1;
  }
} {t3i1 t3i2 t3i3 t4i1 t4i2 t3 t4}
ifcapable stat4 {
  do_test analyze-5.1 {
    execsql {
      SELECT DISTINCT idx FROM sqlite_stat4 ORDER BY 1;
      SELECT DISTINCT tbl FROM sqlite_stat4 ORDER BY 1;
    }
  } {t3i1 t3i2 t3i3 t4i1 t4i2 t3 t4}
}
do_test analyze-5.2 {
  execsql {
    DROP INDEX t3i2;
    SELECT DISTINCT idx FROM sqlite_stat1 ORDER BY 1;
    SELECT DISTINCT tbl FROM sqlite_stat1 ORDER BY 1;
  }
} {t3i1 t3i3 t4i1 t4i2 t3 t4}
ifcapable stat4 {
  do_test analyze-5.3 {
    execsql {
      SELECT DISTINCT idx FROM sqlite_stat4 ORDER BY 1;
      SELECT DISTINCT tbl FROM sqlite_stat4 ORDER BY 1;
    }
  } {t3i1 t3i3 t4i1 t4i2 t3 t4}
}
do_test analyze-5.4 {
  execsql {
    DROP TABLE t3;
    SELECT DISTINCT idx FROM sqlite_stat1 ORDER BY 1;
    SELECT DISTINCT tbl FROM sqlite_stat1 ORDER BY 1;
  }
} {t4i1 t4i2 t4}
ifcapable stat4 {
  do_test analyze-5.5 {
    execsql {
      SELECT DISTINCT idx FROM sqlite_stat4 ORDER BY 1;
      SELECT DISTINCT tbl FROM sqlite_stat4 ORDER BY 1;
    }
  } {t4i1 t4i2 t4}
}

# This test corrupts the database file so it must be the last test
# in the series.
#
do_test analyze-99.1 {
  execsql {
    PRAGMA writable_schema=on;
    UPDATE sqlite_master SET sql='nonsense' WHERE name='sqlite_stat1';
  }
  db close
  catch { sqlite3 db test.db }
  catchsql {
    ANALYZE
  }
} {1 {malformed database schema (sqlite_stat1) - near "nonsense": syntax error}}


finish_test

# implements tests for range and LIKE constraints that use bound variables
# instead of literal constant arguments.
#

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

ifcapable !stat4 {
  finish_test
  return
}

#----------------------------------------------------------------------
# Test Organization:
#

# 2011 January 19
#
# 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.
#
#***********************************************************************
#
# This file implements tests for SQLite library.  The focus of the tests
# in this file is the use of the sqlite_stat4 histogram data on tables
# with many repeated values and only a few distinct values.
#

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

ifcapable !stat4 {
  finish_test
  return
}

set testprefix analyze5

proc eqp {sql {db db}} {
  uplevel execsql [list "EXPLAIN QUERY PLAN $sql"] $db
}

proc alpha {blob} {
  set ret ""
  foreach c [split $blob {}] {
    if {[string is alpha $c]} {append ret $c}
  }
  return $ret
}
db func alpha alpha

unset -nocomplain i t u v w x y z
do_test analyze5-1.0 {
  db eval {CREATE TABLE t1(t,u,v TEXT COLLATE nocase,w,x,y,z)}
  for {set i 0} {$i < 1000} {incr i} {
    set y [expr {$i>=25 && $i<=50}]
    set z [expr {($i>=400) + ($i>=700) + ($i>=875)}]

    CREATE INDEX t1u ON t1(u);  -- text
    CREATE INDEX t1v ON t1(v);  -- mixed case text
    CREATE INDEX t1w ON t1(w);  -- integers 0, 1, 2 and a few NULLs
    CREATE INDEX t1x ON t1(x);  -- integers 1, 2, 3 and many NULLs
    CREATE INDEX t1y ON t1(y);  -- integers 0 and very few 1s
    CREATE INDEX t1z ON t1(z);  -- integers 0, 1, 2, and 3
    ANALYZE;
    SELECT alpha(sample) FROM sqlite_stat4 WHERE idx='t1u' ORDER BY nlt;
  }
} {alpha bravo charlie delta}

do_test analyze5-1.1 {
  db eval {
    SELECT DISTINCT lower(alpha(sample)) FROM sqlite_stat4 WHERE idx='t1v'
    ORDER BY 1
  }
} {alpha bravo charlie delta}
do_test analyze5-1.2 {
  db eval {SELECT idx, count(*) FROM sqlite_stat4 GROUP BY 1 ORDER BY 1}
} {t1t 4 t1u 4 t1v 4 t1w 4 t1x 4 t1y 2 t1z 4}

# Verify that range queries generate the correct row count estimates
#
foreach {testid where index rows} {
    1  {z>=0 AND z<=0}       t1z  400
    2  {z>=1 AND z<=1}       t1z  300

# in this file a corner-case query planner optimization involving the
# join order of two tables of different sizes.
#

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

ifcapable !stat4 {
  finish_test
  return
}

set testprefix analyze6

proc eqp {sql {db db}} {

} {0 0 0 {SEARCH TABLE t1 USING INDEX t1a (a=?)}}
do_test analyze7-3.1 {
  execsql {EXPLAIN QUERY PLAN SELECT * FROM t1 WHERE b=123;}
} {0 0 0 {SEARCH TABLE t1 USING INDEX t1b (b=?)}}
do_test analyze7-3.2.1 {
  execsql {EXPLAIN QUERY PLAN SELECT * FROM t1 WHERE c=?;}
} {0 0 0 {SEARCH TABLE t1 USING INDEX t1cd (c=?)}}
ifcapable stat4 {
  # If ENABLE_STAT4 is defined, SQLite comes up with a different estimated
  # row count for (c=2) than it does for (c=?).
  do_test analyze7-3.2.2 {
    execsql {EXPLAIN QUERY PLAN SELECT * FROM t1 WHERE c=2;}
  } {0 0 0 {SEARCH TABLE t1 USING INDEX t1cd (c=?)}}
} else {
  # If ENABLE_STAT4 is not defined, the expected row count for (c=2) is the
  # same as that for (c=?).
  do_test analyze7-3.2.3 {
    execsql {EXPLAIN QUERY PLAN SELECT * FROM t1 WHERE c=2;}
  } {0 0 0 {SEARCH TABLE t1 USING INDEX t1cd (c=?)}}
}
do_test analyze7-3.3 {
  execsql {EXPLAIN QUERY PLAN SELECT * FROM t1 WHERE a=123 AND b=123}
} {0 0 0 {SEARCH TABLE t1 USING INDEX t1a (a=?)}}
ifcapable {!stat4} {
  do_test analyze7-3.4 {
    execsql {EXPLAIN QUERY PLAN SELECT * FROM t1 WHERE c=123 AND b=123}
  } {0 0 0 {SEARCH TABLE t1 USING INDEX t1b (b=?)}}
  do_test analyze7-3.5 {
    execsql {EXPLAIN QUERY PLAN SELECT * FROM t1 WHERE a=123 AND c=123}
  } {0 0 0 {SEARCH TABLE t1 USING INDEX t1a (a=?)}}
}

# This file implements tests for SQLite library.  The focus of the tests
# in this file is testing the capabilities of sqlite_stat3.
#

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

ifcapable !stat4 {
  finish_test
  return
}

set testprefix analyze8

proc eqp {sql {db db}} {

# 2013 August 3
#
# 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 analyze9

proc s {blob} {
  set ret ""
  binary scan $blob c* bytes
  foreach b $bytes {
    set t [binary format c $b]
    if {[string is print $t]} {
      append ret $t
    } else {
      append ret .
    }
  }
  return $ret
}
db function s s

do_test 1.0 {
  execsql { CREATE TABLE t1(a TEXT, b TEXT); }
  for {set i 0} {$i < 5} {incr i} {
    execsql {INSERT INTO t1 VALUES ('('||($i%10)||')', '('||($i%7)||')')}
  }
  execsql { CREATE INDEX i1 ON t1(a, b) }
} {}

do_execsql_test 1.1 {
  ANALYZE;
} {}

do_execsql_test 1.2 {
  SELECT tbl,idx,nEq,nLt,nDLt,s(sample) FROM sqlite_stat4;
} {
  t1 i1 {1 1} {1 1} {1 1} ...(1)(1) 
  t1 i1 {1 1} {2 2} {2 2} ...(2)(2) 
  t1 i1 {1 1} {3 3} {3 3} ...(3)(3)
  t1 i1 {1 1} {4 4} {4 4} ...(4)(4)
}


finish_test

    }
    ifcapable view {
      execsql {
        DROP TABLE v1chng;
      }
    }
  }
  ifcapable stat4 {
    set stat4 "sqlite_stat4 "
  } else {
    set stat4 ""
  }
  do_test auth-5.2 {
    execsql {
      SELECT name FROM (
        SELECT * FROM sqlite_master UNION ALL SELECT * FROM sqlite_temp_master)
      WHERE type='table'
      ORDER BY name
    }
  } "sqlite_stat1 ${stat4}t1 t2 t3 t4"
}

# Ticket #3944
#
ifcapable trigger {
  do_test auth-5.3.1 {
    execsql {

proc lookaside {db} {
  expr { $::lookaside_buffer_size *
    [lindex [sqlite3_db_status $db SQLITE_DBSTATUS_LOOKASIDE_USED 0] 1]
  }
}

ifcapable stat4 {
  set STAT3 1
} else {
  set STAT3 0
}

ifcapable malloc_usable_size {
  finish_test

    # for any reason is not counted as "schema memory".
    #
    # Additionally, in auto-vacuum mode, dropping tables and indexes causes
    # the page-cache to shrink. So the amount of memory freed is always
    # much greater than just that reported by DBSTATUS_SCHEMA_USED in this
    # case.
    #
    # Some of the memory used for sqlite_stat4 is unaccounted for by
    # dbstatus.
    #
    # Finally, on osx the estimate of memory used by the schema may be
    # slightly low. 
    #
    if {[string match *x $tn] || $AUTOVACUUM
         || ([string match *y $tn] && $STAT3)

# This file implements tests to verify that ticket [cbd054fa6b] has been
# fixed.  
#

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

ifcapable !stat4 {
  finish_test
  return
}

proc s {blob} {
  set ret ""
  binary scan $blob c* bytes
  foreach b $bytes {
    set t [binary format c $b]
    if {[string is print $t]} {
      append ret $t
    } else {
      append ret .
    }
  }
  return $ret
}
db function s s

do_test tkt-cbd05-1.1 {
  db eval {
    CREATE TABLE t1(a INTEGER PRIMARY KEY, b TEXT UNIQUE NOT NULL);
    CREATE INDEX t1_x ON t1(b);
    INSERT INTO t1 VALUES (NULL, '');
    INSERT INTO t1 VALUES (NULL, 'A');

do_test tkt-cbd05-1.2 {
  db eval {
    ANALYZE;
  }
} {}
do_test tkt-cbd05-1.3 {
  execsql { 
    SELECT tbl,idx,group_concat(s(sample),' ') 
    FROM sqlite_stat4 
    WHERE idx = 't1_x' 
    GROUP BY tbl,idx
  }
} {t1 t1_x {.. ..A ..B ..C ..D ..E ..F ..G ..H ..I}}

do_test tkt-cbd05-2.1 {
  db eval {
    DROP TABLE t1;
    CREATE TABLE t1(a INTEGER PRIMARY KEY, b BLOB UNIQUE NOT NULL);
    CREATE INDEX t1_x ON t1(b);
    INSERT INTO t1 VALUES(NULL, X'');

do_test tkt-cbd05-2.2 {
  db eval {
    ANALYZE;
  }
} {}
do_test tkt-cbd05-2.3 {
  execsql { 
    SELECT tbl,idx,group_concat(s(sample),' ') 
    FROM sqlite_stat4 
    WHERE idx = 't1_x' 
    GROUP BY tbl,idx
  }
} {t1 t1_x {.. ..A ..B ..C ..D ..E ..F ..G ..H ..I}}

finish_test

  catchsql {
    UPDATE t1 INDEXED BY t1b SET a=a+100
     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)
  }
} {1 {no query solution}}
ifcapable stat4 {
  # When STAT3 is enabled, the "b NOT NULL" terms get translated
  # into b>NULL, which can be satified by the index t1b.  It is a very
  # expensive way to do the query, but it works, and so a solution is possible.
  do_test where9-6.8.3-stat4 {
    catchsql {
      UPDATE t1 INDEXED BY t1b SET a=a+100
       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 {}}
  do_test where9-6.8.4-stat4 {
    catchsql {
      DELETE FROM t1 INDEXED BY t1b
       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 {}}

#
# This test should work the same with and without SQLITE_ENABLE_STAT3
#
###############################################################################

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

# TODO: Reenable this test.
  finish_test
  return

ifcapable !stat3 {
  finish_test
  return
}

do_execsql_test wild001.01 {