SQLite

** sqlite_stat4.sample.  The nEq, nLt, and nDLt entries of sqlite_stat3
** all contain just a single integer which is the same as the first
** integer in the equivalent columns in sqlite_stat4.
*/
#ifndef SQLITE_OMIT_ANALYZE
#include "sqliteInt.h"

#ifdef SQLITE_ENABLE_STAT4

# define IsStat3 0



#else

# define IsStat3 1
#endif

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

      }else{
        /* The sqlite_stat[134] 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(aRoot); 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.
**
** bHaveP, bHaveNonP:
**   The stat4_push() user-defined-function may be invoked multiple
**   times with index keys that are identical except for the rowid 
**   field. An argument is passed to stat4_push() to indicate if this
**   is the case or not.
**
**   bHaveP is set to true if a periodic sample corresponding to the
**   current index key has already been added. bHaveNonP is true if a
**   non-periodic sample has been added.
*/
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 nEq and hash */
  int mxSample;             /* Maximum number of samples to accumulate */
  int nSample;              /* Current number of samples */
  int nCol;                 /* Number of columns in the index including rowid */
  u32 iPrn;                 /* Pseudo-random number used for sampling */
  int bHaveP;
  int bHaveNonP;
  struct Stat4Sample {
    i64 iRowid;                /* Rowid in main table of the key */
    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 */
};

#if defined(SQLITE_ENABLE_STAT4) || defined(SQLITE_ENABLE_STAT3)
/*
** 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]);
  mxSample = sqlite3_value_int(argv[2]);
  nCol = sqlite3_value_int(argv[1]);
  assert( nCol>1 );               /* >1 because it includes the rowid column */

  /* 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]);
  int bNewKey = sqlite3_value_int(argv[2]);
  struct Stat4Sample *pSample;
  u32 h;                          /* Hash value for this key */
  int iMin = p->iMin;
  int i;
  int nSampleCol;                 /* Number of fields in samples */
  u8 isPSample = 0;               /* True if this is a periodic sample */
  u8 doInsert = 0;

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

  i64 nLt;
  i64 nEq;

  UNUSED_PARAMETER(context);
  UNUSED_PARAMETER(argc);
  assert( p->nCol>0 );
  assert( argc==(3 + 3*p->nCol) );
  assert( p->bHaveNonP==0 || p->bHaveP==0 );

  if( IsStat3 ){
    /* Stat3 builds ignore any call with bNewKey==0. And consider only
    ** the first column of the index keys. */
    if( bNewKey==0 ) return;
    nEq = sqlite3_value_int64(aEq[0]);
    nSampleCol = 1;
  }else{
    nEq = 1;
    nSampleCol = p->nCol;
  }
  nLt = sqlite3_value_int64(aLt[nSampleCol-1]);

  if( bNewKey ){
    p->bHaveP = 0;
    p->bHaveNonP = 0;
  }
  h = p->iPrn = p->iPrn*1103515245 + 12345;

  /* Check if this should be a periodic sample. If this is a periodic
  ** sample and there is already a non-periodic sample for this key,
  ** replace it.  */
  if( (nLt/p->nPSample) != (nLt+nEq)/p->nPSample ){
    doInsert = isPSample = 1;
    if( p->bHaveNonP ){
      p->nSample--;
      p->bHaveNonP = 0;
      p->bHaveP = 1;
      assert( p->nSample<p->mxSample );
      assert( p->a[p->nSample].isPSample==0 );
    }

  /* Or, if this is not a periodic sample, and there is already at least one
  ** periodic sample, return early. */
  }else if( p->bHaveP ){
    /* no-op */

  /* If there is already a non-periodic sample for the key, but this one
  ** has a higher hash score, replace the existing sample.  */
  }else if( p->bHaveNonP ){
    if( p->a[p->nSample-1].iHash<h ){
      p->nSample--;
      doInsert = 1;
    }

  /* Finally, check if this should be added as a non-periodic sample. */
  }else if( p->nSample<p->mxSample ){
    doInsert = 1;
    p->bHaveNonP = 1;
  }else{
    tRowcnt *aMinEq = p->a[iMin].anEq;
    for(i=(IsStat3 ? 0 : p->nCol-2); i>=0; i--){
      i64 nEq = sqlite3_value_int64(aEq[i]);
      if( nEq<aMinEq[i] ) break;
      if( nEq>aMinEq[i] ){
        doInsert = 1;
        break;
      }

    }
    if( i<0 && h>p->a[iMin].iHash ){
      doInsert = 1;
    }
    p->bHaveNonP = doInsert;
  }
  if( doInsert==0 ) return;

  /* Fill in the new Stat4Sample object. */
  if( p->nSample==p->mxSample ){
    struct Stat4Sample *pMin = &p->a[iMin];
    tRowcnt *anEq = pMin->anEq;
    tRowcnt *anDLt = pMin->anDLt;
    tRowcnt *anLt = pMin->anLt;
    assert( p->nSample - iMin - 1 >= 0 );

    memmove(pMin, &pMin[1], sizeof(p->a[0])*(p->nSample-iMin-1));
    pSample = &p->a[p->nSample-1];
    pSample->anEq = anEq;
    pSample->anDLt = anDLt;
    pSample->anLt = anLt;


  }else{


    pSample = &p->a[p->nSample++];

  }
  pSample->iRowid = rowid;
  pSample->iHash = h;
  pSample->isPSample = isPSample;
  for(i=0; i<nSampleCol; 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])-1;
    assert( sqlite3_value_int64(aDLt[i])>0 );
  }





  /* Find the new minimum */

  if( p->nSample==p->mxSample ){
    iMin = -1;
    for(i=0; i<p->mxSample; i++){
      if( p->a[i].isPSample ) continue;
      if( iMin<0 ){
        iMin = i;
      }else{
        int j;
        for(j=nSampleCol-1; j>=0; j++){
          i64 iCmp = (p->a[iMin].anEq[j] - p->a[i].anEq[j]);
          if( iCmp<0 ){ iMin = i; }
          if( iCmp ) break;
        }
        if( j==0 && p->a[iMin].iHash<p->a[i].iHash ){
          iMin = i;
        }
      }
    }
    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;




    }

    if( IsStat3 ){
      sqlite3_result_int64(context, (i64)aCnt[0]);
    }else{
      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.
*/
static void analyzeOneTable(
  Parse *pParse,   /* Parser context */

  int iIdxCur;                 /* Cursor open on index being analyzed */
  int iTabCur;                 /* Table cursor */
  Vdbe *v;                     /* The virtual machine being built up */
  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 regTabname = iMem++;     /* Register containing table name */
  int regIdxname = iMem++;     /* Register containing index name */
  int regStat1 = iMem++;       /* The stat column of sqlite_stat1 */
#if defined(SQLITE_ENABLE_STAT4) || defined(SQLITE_ENABLE_STAT3)
  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 regLoop = iMem++;        /* Loop counter */
  int shortJump = 0;           /* Instruction address */
#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 regEof = iMem++;         /* True once cursors are all at EOF */
  int regCnt = iMem++;         /* Row counter */

  int regStat4 = iMem++;       /* Register to hold Stat4Accum object */
  int regRowid = iMem++;       /* Rowid argument passed to stat4_push() */
  int regKeychng = iMem++;     /* True if key has changed */






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

  if( sqlite3AuthCheck(pParse, SQLITE_ANALYZE, pTab->zName, 0,
      db->aDb[iDb].zName ) ){
    return;
  }
#endif

  /* Establish a read-lock on the table at the shared-cache level. 
  ** Also open a read-only cursor on the table.  */


  sqlite3TableLock(pParse, iDb, pTab->tnum, 0, pTab->zName);
  iTabCur = iTab++;

  pParse->nTab = MAX(pParse->nTab, iTab);
  sqlite3OpenTable(pParse, iTabCur, iDb, pTab, OP_OpenRead);
  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 *aChngAddr;               /* Array of jump instruction addresses */
    int regPrev;                  /* First in array of previous values */
    int regDLte;                  /* First in array of nDlt registers */
    int regLt;                    /* First in array of nLt registers */
    int regEq;                    /* First in array of nEq registers */
    int endOfScan;                /* Label to jump to once scan is finished */

    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+1));
    if( aChngAddr==0 ) continue;
    pKey = sqlite3IndexKeyinfo(pParse, pIdx);

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

    /*
    ** The following pseudo-code demonstrates the way the VM scans an index 
    ** to call stat4_push() and collect the values for the sqlite_stat1 
    ** entry. The code below is for an index with 2 columns. The actual
    ** VM code generated may be for any number of columns.
    **
    ** One cursor is opened for each column in the index and one for the
    ** rowid column (nCol+1 in total). All cursors scan concurrently the 
    ** index from start to end. All variables used in the pseudo-code are 
    ** initialized to zero.
    **
    **   Rewind csr(0)
    **   Rewind csr(1)
    **   Rewind csr(2)
    ** 
    **  next_0:
    **   regPrev(0) = csr(0)[0]
    **   regDLte(0) += 1
    **   regLt(0) += regEq(0)
    **   regEq(0) = 0
    **   do {
    **     regEq(0) += 1
    **     Next csr(0)
    **   }while ( csr(0)[0] == regPrev(0) )
    **   if( IsStat3 ) regKeychng = 1
    ** 
    **  next_1:
    **   regPrev(1) = csr(1)[1]
    **   regDLte(1) += 1
    **   regLt(1) += regEq(1)
    **   regEq(1) = 0
    **   do {
    **     regEq(1) += 1
    **     Next csr(1)
    **   }while ( csr(1)[0..1] == regPrev(0..1) )
    ** 
    **   if( IsStat3==0 ) regKeychng = 1
    **  next_row:
    **   regRowid = csr(2)[rowid]
    **   regEq(2) = 1
    **   regLt(2) = regCnt
    **   regCnt += 1
    **   regDLte(2) = regCnt
    **   stat4_push(regRowid, regKeychng, regEq, regLt, regDLte);
    **   regKeychng = 0
    **   Next csr(2)
    **   if( eof( csr(2) ) ) goto endOfScan
    ** 
    **   if( csr(2)[0] != regPrev(0) ) goto next_0
    **   if( csr(2)[1] != regPrev(1) ) goto next_1
    **   goto next_row
    **
    **  endOfScan:
    **   // done!
    **
    ** The last two lines above modify the contents of the regDLte 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.
    **
    ** At this point, the last memory cell allocated (that with the largest 
    ** integer identifier) is regKeychng. Immediately following regKeychng
    ** we allocate the following:
    **
    **     regEq -    nCol registers
    **     regLt -    nCol+1 registers

    **     regDLte -  nCol+1 registers
    **     regPrev -  nCol+1 registers
    **
    ** can be passed to the stat4_push() function.
    **
    ** All of the above are initialized to contain integer value 0.
    */
    regEq = regKeychng+1;         /* First in array of nEq value registers */
    regLt = regEq+nCol+1;         /* First in array of nLt value registers */
    regDLte = regLt+nCol+1;       /* First in array of nDLt value registers */

    regPrev = regDLte+nCol+1;     /* First in array of prev. value registers */


    pParse->nMem = MAX(pParse->nMem, regPrev+nCol);

    /* Open a read-only cursor for each column of the index. And one for
    ** the rowid column. A total of (nCol+1) cursors.  */
    assert( iDb==sqlite3SchemaToIndex(db, pIdx->pSchema) );
    iIdxCur = iTab;
    pParse->nTab = MAX(pParse->nTab, iTab+nCol+1);
    for(i=0; i<(nCol+1); i++){
      int iMode = (i==0 ? P4_KEYINFO_HANDOFF : P4_KEYINFO);
      sqlite3VdbeAddOp3(v, OP_OpenRead, iIdxCur+i, pIdx->tnum, iDb);
      sqlite3VdbeChangeP4(v, -1, (char*)pKey, iMode); 
      VdbeComment((v, "%s", pIdx->zName));
    }

#if defined(SQLITE_ENABLE_STAT4) || defined(SQLITE_ENABLE_STAT3)
    /* Invoke the stat4_init() function. The arguments are:
    ** 
    **     * the number of rows in the index,
    **     * the number of columns in the index including the rowid,
    **     * the recommended number of samples for the stat4 table.
    **
    ** If this is a stat3 build, the number of columns in the index is
    ** set to 1 (as this is the number of index fields gathered).
    */
    sqlite3VdbeAddOp2(v, OP_Count, iIdxCur, regStat4+1);
    sqlite3VdbeAddOp2(v, OP_Integer, nCol+1, 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 */

    /* Initialize all the memory registers allocated above to 0. */
    for(i=regEq; i<regDLte+nCol; i++){
      sqlite3VdbeAddOp2(v, OP_Integer, 0, i);
    }
    sqlite3VdbeAddOp2(v, OP_Integer, 0, regCnt);
    sqlite3VdbeAddOp2(v, OP_Integer, 0, regEof);

    /* Rewind all cursors open on the index. If the table is entry, this
    ** will cause control to jump to address endOfScan immediately.  */
    endOfScan = sqlite3VdbeMakeLabel(v);
    for(i=0; i<(nCol+1); i++){
      sqlite3VdbeAddOp2(v, OP_Rewind, iIdxCur+i, endOfScan);
    }

    for(i=0; i<nCol; i++){
      char *pColl = (char*)sqlite3LocateCollSeq(pParse, pIdx->azColl[i]);
      int iCsr = iIdxCur+i;
      int iDo;
      int iNe;                    /* Jump here to exit do{...}while loop */
      int j;

      /* Implementation of the following pseudo-code:
      **
      **   regPrev(i) = csr(i)[i]

      **   regDLte(i) += 1
      **   regLt(i) += regEq(i)
      **   regEq(i) = 0
      **   regRowid = csr(i)[rowid]        // innermost cursor only
      */
      aChngAddr[i] = sqlite3VdbeAddOp3(v, OP_Column, iCsr, i, regPrev+i);
      VdbeComment((v, "regPrev(%d) = csr(%d)(%d)", i, i, i));
      sqlite3VdbeAddOp2(v, OP_AddImm, regDLte+i, 1);
      VdbeComment((v, "regDLte(%d) += 1", i));
      sqlite3VdbeAddOp3(v, OP_Add, regEq+i, regLt+i, regLt+i);
      VdbeComment((v, "regLt(%d) += regEq(%d)", i, i));
      sqlite3VdbeAddOp2(v, OP_Integer, 0, regEq+i);
      VdbeComment((v, "regEq(%d) = 0", i));

      /* This bit:
      **
      **   do {
      **     regEq(i) += 1
      **     Next csr(i)
      **     if( Eof csr(i) ){
      **       break
      **     }
      **   }while ( csr(i)[0..i] == regPrev(0..i) )
      */
      iDo = sqlite3VdbeAddOp2(v, OP_AddImm, regEq+i, 1);
      VdbeComment((v, "regEq(%d) += 1", i));
      sqlite3VdbeAddOp2(v, OP_Next, iCsr, sqlite3VdbeCurrentAddr(v)+2);

      iNe = sqlite3VdbeMakeLabel(v);
      sqlite3VdbeAddOp2(v, OP_Goto, 0, iNe);
      for(j=0; j<=i; j++){
        sqlite3VdbeAddOp3(v, OP_Column, iCsr, j, regCol);

        sqlite3VdbeAddOp4(v, OP_Ne, regCol, iNe, regPrev+j, pColl, P4_COLLSEQ);
        sqlite3VdbeChangeP5(v, SQLITE_NULLEQ);
        VdbeComment((v, "if( regPrev(%d) != csr(%d)(%d) )", j, i, j));
      }
      sqlite3VdbeAddOp2(v, OP_Goto, 0, iDo);
      sqlite3VdbeResolveLabel(v, iNe);

      if( IsStat3 && i==0 ){

        sqlite3VdbeAddOp2(v, OP_Integer, 1, regKeychng);
      }
    }

    /* This stuff:

    ** 






    **   regKeychng = 1

    **  next_row:
    **   regRowid = csr(2)[rowid]
    **   regEq(2) = 1
    **   regLt(2) = regCnt
    **   regCnt += 1
    **   regDLte(2) = regCnt
    **   stat4_push(regRowid, regKeychng, regEq, regLt, regDLte);
    **   regKeychng = 0
    **   Next csr(2)
    **   if( eof( csr(2) ) ) goto endOfScan
    */
#if defined(SQLITE_ENABLE_STAT4) || defined(SQLITE_ENABLE_STAT3)
    if( 0==IsStat3 ){
      sqlite3VdbeAddOp2(v, OP_Integer, 1, regKeychng);
    }
    aChngAddr[nCol] =
    sqlite3VdbeAddOp2(v, OP_IdxRowid, iIdxCur+nCol, regRowid);
    sqlite3VdbeAddOp2(v, OP_Integer, 1, regEq+nCol);
    sqlite3VdbeAddOp2(v, OP_Copy, regCnt, regLt+nCol);
    sqlite3VdbeAddOp2(v, OP_AddImm, regCnt, 1);
    sqlite3VdbeAddOp2(v, OP_Copy, regCnt, regDLte+nCol);
    sqlite3VdbeAddOp3(v, OP_Function, 1, regStat4, regTemp);
    sqlite3VdbeChangeP4(v, -1, (char*)&stat4PushFuncdef, P4_FUNCDEF);
    sqlite3VdbeChangeP5(v, 3 + 3*(nCol+1));
    sqlite3VdbeAddOp2(v, OP_Integer, 0, regKeychng);
    sqlite3VdbeAddOp2(v, OP_Next, iIdxCur+nCol, sqlite3VdbeCurrentAddr(v)+2);
    sqlite3VdbeAddOp2(v, OP_Goto, 0, endOfScan);
#endif

    sqlite3VdbeAddOp2(v, OP_If, regEof, endOfScan);
    for(i=0; i<nCol; i++){
      char *pColl = (char*)sqlite3LocateCollSeq(pParse, pIdx->azColl[i]);
      sqlite3VdbeAddOp3(v, OP_Column, iIdxCur+nCol, i, regCol);
      sqlite3VdbeAddOp3(v, OP_Ne, regCol, aChngAddr[i], regPrev+i);
      sqlite3VdbeChangeP4(v, -1, pColl, P4_COLLSEQ);
      sqlite3VdbeChangeP5(v, SQLITE_NULLEQ);
    }
    sqlite3VdbeAddOp2(v, OP_Goto, 0, aChngAddr[nCol]);
    sqlite3DbFree(db, aChngAddr);

    sqlite3VdbeResolveLabel(v, endOfScan);

#if defined(SQLITE_ENABLE_STAT4) || defined(SQLITE_ENABLE_STAT3)
    /* 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, regEq+nCol);
    sqlite3VdbeChangeP4(v, -1, (char*)&stat4GetFuncdef, P4_FUNCDEF);
    sqlite3VdbeChangeP5(v, 2);
    sqlite3VdbeAddOp1(v, OP_IsNull, regEq+nCol);

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

    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        

    /* Store the results in sqlite_stat1.
    **
    ** The result is a single row of the sqlite_stat1 table.  The first
    ** two columns are the names of the table and index.  The third column
    ** is a string composed of a list of integer statistics about the
    ** index.  The first integer in the list is the total number of entries
    ** in the index.  There is one additional integer in the list for each
    ** column of the table.  This additional integer is a guess of how many
    ** rows of the table the index will select.  If D is the count of distinct
    ** values and K is the total number of rows, then the integer is computed
    ** as:
    **
    **        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, regDLte+i, regTemp);
      sqlite3VdbeAddOp2(v, OP_AddImm, regTemp, -1);
      sqlite3VdbeAddOp3(v, OP_Divide, regDLte+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);



    sqlite3VdbeChangeP5(v, OPFLAG_APPEND);

    if( pIdx->pPartIdxWhere==0 ) sqlite3VdbeJumpHere(v, jZeroRows);

  }


  /* Create a single sqlite_stat1 entry containing NULL as the index
  ** name and the row count as the content.
  */
  if( pOnlyIdx==0 && needTableCnt ){
    VdbeComment((v, "%s", pTab->zName));
    sqlite3VdbeAddOp2(v, OP_Count, iTabCur, regStat1);
    jZeroRows = sqlite3VdbeAddOp1(v, OP_IfNot, regStat1);
    sqlite3VdbeAddOp2(v, OP_Null, 0, regIdxname);
    sqlite3VdbeAddOp4(v, OP_MakeRecord, regTabname, 3, regRec, "aaa", 0);
    sqlite3VdbeAddOp2(v, OP_NewRowid, iStatCur, regNewRowid);
    sqlite3VdbeAddOp3(v, OP_Insert, iStatCur, regRec, regNewRowid);
    sqlite3VdbeChangeP5(v, OPFLAG_APPEND);
    sqlite3VdbeJumpHere(v, jZeroRows);
  }
}


/*

} {0 0 0 {SEARCH TABLE t1 USING INDEX t1b (b>? AND b<?)}}

# There are many more values of c between 0 and 100000 than there are
# between 800000 and 900000.  So t1c is more selective for the latter
# range.
# 
# Test 3.2 is a little unstable. It depends on the planner estimating
# that (b BETWEEN 40 AND 44) will match more rows than (c BETWEEN
# 800000 AND 900000). Which is a pretty close call (50 vs. 32), so
# the planner could get it wrong with an unlucky set of samples. This
# case happens to work, but others ("b BETWEEN 50 AND 54" for example) 
# will fail.
#
do_execsql_test 3.0 {
  SELECT count(*) FROM t1 WHERE b BETWEEN 40 AND 44;
  SELECT count(*) FROM t1 WHERE c BETWEEN 0 AND 100000;
  SELECT count(*) FROM t1 WHERE c BETWEEN 800000 AND 900000;
} {50 376 32}
do_test 3.1 {
  eqp {SELECT * FROM t1 WHERE b BETWEEN 40 AND 44 AND c BETWEEN 0 AND 100000}
} {0 0 0 {SEARCH TABLE t1 USING INDEX t1b (b>? AND b<?)}}
do_test 3.2 {
  eqp {SELECT * FROM t1
       WHERE b BETWEEN 40 AND 44 AND c BETWEEN 800000 AND 900000}
} {0 0 0 {SEARCH TABLE t1 USING INDEX t1c (c>? AND c<?)}}

do_test 3.3 {
  eqp {SELECT * FROM t1 WHERE a=100 AND c BETWEEN 0 AND 100000}
} {0 0 0 {SEARCH TABLE t1 USING INDEX t1a (a=?)}}
do_test 3.4 {
  eqp {SELECT * FROM t1
       WHERE a=100 AND c BETWEEN 800000 AND 900000}
} {0 0 0 {SEARCH TABLE t1 USING INDEX t1c (c>? AND c<?)}}