SQLite

  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])-1;
    assert( sqlite3_value_int64(aDLt[i])>0 );
  } 

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

#ifndef SQLITE_OMIT_AUTHORIZATION
  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 = pParse->nTab++;
  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 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 regDLte;                  /* 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 regEof;                   /* True once cursors are all at EOF */
    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);
    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 (nCol). 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)
    ** 
    **  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) )
    ** 
    **  next_1:
    **   regPrev(1) = csr(1)[1]
    **   regDLte(1) += 1
    **   regLt(1) += regEq(1)
    **   regEq(1) = 0
    **   regRowid = csr(1)[rowid]        // innermost cursor only
    **   do {
    **     regEq(1) += 1
    **     regCnt += 1                   // innermost cursor only
    **     Next csr(1)
    **   }while ( csr(1)[0..1] == regPrev(0..1) )
    ** 
    **   stat4_push(regRowid, regEq, regLt, regDLte);
    ** 
    **   if( eof( csr(1) ) ) goto endOfScan
    **   if( csr(1)[0] != regPrev(0) ) goto next_0
    **   goto next_1
    **
    **  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.
    **
    ** Currently, the last memory cell allocated (that with the largest 
    ** integer identifier) is regStat4. Immediately following regStat4
    ** we allocate the following:
    **
    **     regRowid -    1 register
    **     regEq -    nCol registers
    **     regLt -    nCol registers
    **     regDLte -  nCol registers
    **     regCnt -      1 register
    **     regPrev -  nCol registers
    **     regEof -      1 register
    **
    ** The regRowid, regEq, regLt and regDLte registers must be positioned in 
    ** that order immediately following regStat4 so that they can be passed
    ** to the stat4_push() function.
    **
    ** All of the above are initialized to contain integer value 0.
    */
    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 */
    regDLte = regLt+nCol;         /* First in array of nDLt value registers */
    regCnt = regDLte+nCol;        /* Row counter */
    regPrev = regCnt+1;           /* First in array of prev. value registers */
    regEof = regPrev+nCol;        /* True once last row read from index */
    if( regEof+1>pParse->nMem ){
      pParse->nMem = regPrev+nCol;
    }

    /* Open a read-only cursor for each column of the index. */
    assert( iDb==sqlite3SchemaToIndex(db, pIdx->pSchema) );
    iIdxCur = pParse->nTab++;
    pParse->nTab += (nCol-1);
    for(i=0; i<nCol; 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));
    }

#ifdef SQLITE_ENABLE_STAT4
    /* 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 */




















    /* Initialize all the memory registers allocated above to 0. */

    for(i=regRowid; i<=regEof; i++){





      sqlite3VdbeAddOp2(v, OP_Integer, 0, i);
    }



    /* 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; 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;
      int bInner = (i==(nCol-1)); /* True for innermost cursor */


      /* 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));
      if( bInner ) sqlite3VdbeAddOp2(v, OP_IdxRowid, iCsr, regRowid);

      /* This bit:

      **

      **   do {
      **     regEq(i) += 1
      **     regCnt += 1                   // innermost cursor only

      **     Next csr(i)
      **     if( Eof csr(i) ){

      **       regEof = 1                  // innermost cursor only





      **       break

      **     }



      **   }while ( csr(i)[0..i] == regPrev(0..i) )








      */
      iDo = sqlite3VdbeAddOp2(v, OP_AddImm, regEq+i, 1);
      VdbeComment((v, "regEq(%d) += 1", i));
      if( bInner ){


        sqlite3VdbeAddOp2(v, OP_AddImm, regCnt, 1);
        VdbeComment((v, "regCnt += 1"));
      }




      sqlite3VdbeAddOp2(v, OP_Next, iCsr, sqlite3VdbeCurrentAddr(v)+2+bInner);
      if( bInner ) sqlite3VdbeAddOp2(v, OP_Integer, 1, regEof);
      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);
    }

    /* Invoke stat4_push() */
    sqlite3VdbeAddOp3(v, OP_Function, 1, regStat4, regTemp2);
    sqlite3VdbeChangeP4(v, -1, (char*)&stat4PushFuncdef, P4_FUNCDEF);


    sqlite3VdbeChangeP5(v, 2 + 3*nCol);




    sqlite3VdbeAddOp2(v, OP_If, regEof, endOfScan);

    for(i=0; i<nCol-1; i++){


      char *pColl = (char*)sqlite3LocateCollSeq(pParse, pIdx->azColl[i]);

      sqlite3VdbeAddOp3(v, OP_Column, iIdxCur+nCol-1, 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-1]);
    sqlite3DbFree(db, aChngAddr);










    sqlite3VdbeResolveLabel(v, endOfScan);







    /* Close all the cursors */




    for(i=0; i<nCol; i++){

      sqlite3VdbeAddOp1(v, OP_Close, iIdxCur+i);
      VdbeComment((v, "close index cursor %d", i));
    }

#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);

    ** 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);
  }

  sqlite3VdbeAddOp1(v, OP_Close, iTabCur);

  /* TODO: Not sure about this... */
  if( pParse->nMem<regRec ) pParse->nMem = regRec;
}


/*
** Generate code that will cause the most recent index analysis to
** be loaded into internal hash tables where is can be used.

*/
#include "sqlite3.h"
#include "tcl.h"
#include <stdlib.h>
#include <string.h>
#include <assert.h>

#include "sqliteInt.h"
#include "vdbeInt.h"


/*
** Allocate nByte bytes of space using sqlite3_malloc(). If the
** allocation fails, call sqlite3_result_error_nomem() to notify
** the database handle that malloc() has failed.
*/
static void *testContextMalloc(sqlite3_context *context, int nByte){

      zOut[14-i*2+1] = "0123456789abcdef"[v.x[i]&0xf];
    }
  }
  zOut[16] = 0;
  sqlite3_result_text(context, zOut, -1, SQLITE_TRANSIENT);
}

/*
** tclcmd: test_decode(record)
**
** This function implements an SQL user-function that accepts a blob
** containing a formatted database record as its only argument. It returns
** a tcl list (type SQLITE_TEXT) containing each of the values stored
** in the record.
*/
static void test_decode(
  sqlite3_context *context,
  int argc,
  sqlite3_value **argv
){
  sqlite3 *db = sqlite3_context_db_handle(context);
  u8 *pRec;
  u8 *pEndHdr;                    /* Points to one byte past record header */
  u8 *pHdr;                       /* Current point in record header */
  u8 *pBody;                      /* Current point in record data */
  u64 nHdr;                       /* Bytes in record header */
  Tcl_Obj *pRet;                  /* Return value */

  pRet = Tcl_NewObj();
  Tcl_IncrRefCount(pRet);

  assert( argc==1 );
  pRec = (u8*)sqlite3_value_blob(argv[0]);

  pHdr = pRec + sqlite3GetVarint(pRec, &nHdr);
  pBody = pEndHdr = &pRec[nHdr];
  while( pHdr<pEndHdr ){
    Tcl_Obj *pVal = 0;
    u64 iSerialType;
    Mem mem;

    memset(&mem, 0, sizeof(mem));
    mem.db = db;
    mem.enc = SQLITE_UTF8;
    pHdr += sqlite3GetVarint(pHdr, &iSerialType);
    pBody += sqlite3VdbeSerialGet(pBody, (u32)iSerialType, &mem);

    sqlite3VdbeMemStoreType(&mem);
    switch( sqlite3_value_type(&mem) ){
      case SQLITE_TEXT:
        pVal = Tcl_NewStringObj((const char*)sqlite3_value_text(&mem), -1);
        break;

      case SQLITE_BLOB: {
        char hexdigit[] = {
          '0', '1', '2', '3', '4', '5', '6', '7',
          '8', '9', 'a', 'b', 'c', 'd', 'e', 'f'
        };
        int n = sqlite3_value_bytes(&mem);
        u8 *z = (u8*)sqlite3_value_blob(&mem);
        int i;
        pVal = Tcl_NewStringObj("x'", -1);
        for(i=0; i<n; i++){
          char hex[3];
          hex[0] = hexdigit[((z[i] >> 4) & 0x0F)];
          hex[1] = hexdigit[(z[i] & 0x0F)];
          hex[2] = '\0';
          Tcl_AppendStringsToObj(pVal, hex, 0);
        }
        Tcl_AppendStringsToObj(pVal, "'", 0);
        break;
      }

      case SQLITE_FLOAT:
        pVal = Tcl_NewDoubleObj(sqlite3_value_double(&mem));
        break;

      case SQLITE_INTEGER:
        pVal = Tcl_NewWideIntObj(sqlite3_value_int64(&mem));
        break;

      case SQLITE_NULL:
        pVal = Tcl_NewStringObj("NULL", -1);
        break;

      default:
        assert( 0 );
    }

    Tcl_ListObjAppendElement(0, pRet, pVal);

    if( mem.zMalloc ){
      sqlite3DbFree(db, mem.zMalloc);
    }
  }

  sqlite3_result_text(context, Tcl_GetString(pRet), -1, SQLITE_TRANSIENT);
  Tcl_DecrRefCount(pRet);
}


static int registerTestFunctions(sqlite3 *db){
  static const struct {
     char *zName;
     signed char nArg;
     unsigned char eTextRep; /* 1: UTF-16.  0: UTF-8 */
     void (*xFunc)(sqlite3_context*,int,sqlite3_value **);

    { "test_auxdata",         -1, SQLITE_UTF8, test_auxdata},
    { "test_error",            1, SQLITE_UTF8, test_error},
    { "test_error",            2, SQLITE_UTF8, test_error},
    { "test_eval",             1, SQLITE_UTF8, test_eval},
    { "test_isolation",        2, SQLITE_UTF8, test_isolation},
    { "test_counter",          1, SQLITE_UTF8, counterFunc},
    { "real2hex",              1, SQLITE_UTF8, real2hex},
    { "test_decode",           1, SQLITE_UTF8, test_decode},
  };
  int i;

  for(i=0; i<sizeof(aFuncs)/sizeof(aFuncs[0]); i++){
    sqlite3_create_function(db, aFuncs[i].zName, aFuncs[i].nArg,
        aFuncs[i].eTextRep, 0, aFuncs[i].xFunc, 0, 0);
  }

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.3 {
  SELECT tbl,idx,nEq,nLt,nDLt,test_decode(sample) FROM sqlite_stat4;
} {
  t1 i1 {1 1} {0 0} {0 0} {(0) (0)}
  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)}
}

do_execsql_test 1.2 {
  SELECT tbl,idx,nEq,nLt,nDLt,s(sample) FROM sqlite_stat4;
} {
  t1 i1 {1 1} {0 0} {0 0} ...(0)(0) 
  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)
}


#-------------------------------------------------------------------------
# This is really just to test SQL user function "test_decode".
#
reset_db
do_execsql_test 2.1 {
  CREATE TABLE t1(a, b, c);
  INSERT INTO t1 VALUES('some text', 14, NULL);
  INSERT INTO t1 VALUES(22.0, NULL, x'656667');
  CREATE INDEX i1 ON t1(a, b, c);
  ANALYZE;
  SELECT test_decode(sample) FROM sqlite_stat4;
} {
  {22.0 NULL x'656667'} 
  {{some text} 14 NULL}
}

#-------------------------------------------------------------------------
# 
reset_db
do_execsql_test 3.1 {
  CREATE TABLE t2(a, b);
  CREATE INDEX i2 ON t2(a, b);
  BEGIN;
}

do_test 3.2 {
  for {set i 0} {$i < 1000} {incr i} {
    set a [expr $i / 10]
    set b [expr int(rand() * 15.0)]
    execsql { INSERT INTO t2 VALUES($a, $b) }
  }
  execsql COMMIT
} {}

db func lindex lindex

# Each value of "a" occurs exactly 10 times in the table.
#
do_execsql_test 3.3.1 {
  SELECT count(*) FROM t2 GROUP BY a;
} [lrange [string repeat "10 " 100] 0 99]

# The first element in the "nEq" list of all samples should therefore be 10.
#
do_execsql_test 3.3.2 {
  ANALYZE;
  SELECT lindex(nEq, 0) FROM sqlite_stat4;
} [lrange [string repeat "10 " 100] 0 23]


finish_test