SQLite

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 associated with this table */
){
  const char *aName[] = { "sqlite_stat1", "sqlite_stat2" };
  const char *aCols[] = { "tbl,idx,stat", "tbl,idx," SQLITE_INDEX_SAMPLE_COLS };
  const char *aCols[] = { "tbl,idx,stat", "tbl,idx,sampleno,sample" };
  int aRoot[] = {0, 0};
  int aCreateTbl[] = {0, 0};

  int i;
  sqlite3 *db = pParse->db;
  Db *pDb;
  Vdbe *v = sqlite3GetVdbe(pParse);

  Parse *pParse,   /* Parser context */
  Table *pTab,     /* Table whose indices are to be analyzed */
  int iStatCur,    /* Index of VdbeCursor that writes the sqlite_stat1 table */
  int iMem         /* Available memory locations begin here */
){
  Index *pIdx;     /* An index to being analyzed */
  int iIdxCur;     /* Index of VdbeCursor for index being analyzed */
  int nCol;        /* Number of columns in the index */
  Vdbe *v;         /* The virtual machine being built up */
  int i;           /* Loop counter */
  int topOfLoop;   /* The top of the loop */
  int endOfLoop;   /* The end of the loop */
  int addr;        /* The address of an instruction */
  int iDb;         /* Index of database containing pTab */


  /* Assign the required registers. */
  int regTabname = iMem++;     /* Register containing table name */
  int regIdxname = iMem++;     /* Register containing index name */
  int regSampleno = iMem++;    /* Register containing next sample number */
  int regCol = iMem++;         /* Content of a column analyzed table */

  int regSamplerecno = iMem++; /* Next sample index record number */
  int regRecno = iMem++;       /* Register next index record number */
  int regRec = iMem++;         /* Register holding completed record */
  int regTemp = iMem++;        /* Temporary use register */
  int regTemp2 = iMem++;        /* Temporary use register */
  int regRowid = iMem++;       /* Rowid for the inserted record */
  int regCount = iMem++;       /* Total number of records in table */

  v = sqlite3GetVdbe(pParse);
  if( v==0 || NEVER(pTab==0) || pTab->pIndex==0 ){
    /* Do no analysis for tables that have no indices */
    return;
  }
  assert( sqlite3BtreeHoldsAllMutexes(pParse->db) );
  iDb = sqlite3SchemaToIndex(pParse->db, pTab->pSchema);
  assert( iDb>=0 );
#ifndef SQLITE_OMIT_AUTHORIZATION
  if( sqlite3AuthCheck(pParse, SQLITE_ANALYZE, pTab->zName, 0,
      pParse->db->aDb[iDb].zName ) ){
    return;
  }
#endif

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

  iMem += 3;
  iIdxCur = pParse->nTab++;
  for(pIdx=pTab->pIndex; pIdx; pIdx=pIdx->pNext){
    int nCol = pIdx->nColumn;
    KeyInfo *pKey = sqlite3IndexKeyinfo(pParse, pIdx);
    int regFields;    /* Register block for building records */
    int regRec;       /* Register holding completed record */
    int regTemp;      /* Temporary use register */

    if( iMem+1+(nCol*2)>pParse->nMem ){
      pParse->nMem = iMem+1+(nCol*2);
    int regCol;       /* Content of a column from the table being analyzed */
    int regRowid;     /* Rowid for the inserted record */
    int regF2;
    int regStat2;

    /* Open a cursor to the index to be analyzed
    }

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

    regFields = regStat2+2+SQLITE_INDEX_SAMPLES;
    regTemp = regRowid = regCol = regFields+3;
    regRec = regCol+1;
    if( regRec>pParse->nMem ){
      pParse->nMem = regRec;
    /* If this iteration of the loop is generating code to analyze the
    ** first index in the pTab->pIndex list, then register regCount has
    ** not been populated. In this case populate it now.  */
    if( pTab->pIndex==pIdx ){
      sqlite3VdbeAddOp2(v, OP_Count, iIdxCur, regCount);
      sqlite3VdbeAddOp4(v, OP_String8, 0, regTabname, 0, pTab->zName, 0);
    }
    sqlite3VdbeAddOp4(v, OP_String8, 0, regIdxname, 0, pIdx->zName, 0);

    /* Fill in the register with the total number of rows. */
    /* Zero the regSampleno and regRecno registers. */
    if( pTab->pIndex==pIdx ){
      sqlite3VdbeAddOp2(v, OP_Count, iIdxCur, iMem-3);
    }
    sqlite3VdbeAddOp2(v, OP_Integer, 0, iMem-2);
    sqlite3VdbeAddOp2(v, OP_Integer, 1, iMem-1);
    sqlite3VdbeAddOp2(v, OP_Integer, 0, regSampleno);
    sqlite3VdbeAddOp2(v, OP_Integer, 0, regRecno);

    /* If there are less than INDEX_SAMPLES records in the index, then
    ** set the contents of regSampleRecno to integer value INDEX_SAMPLES.
    ** Otherwise, set it to zero. This is to ensure that if there are 
    ** less than the said number of entries in the index, no samples at
    ** all are collected.  */
    sqlite3VdbeAddOp2(v, OP_Integer, SQLITE_INDEX_SAMPLES, regSamplerecno);
    sqlite3VdbeAddOp3(v, OP_Lt, regSamplerecno, sqlite3VdbeCurrentAddr(v)+2,
        regCount);
    sqlite3VdbeAddOp2(v, OP_Integer, 0, regSamplerecno);

    /* Memory cells are used as follows. All memory cell addresses are
    ** offset by iMem. That is, cell 0 below is actually cell iMem, cell
    ** 1 is cell 1+iMem, etc.
    **
    **    0:               The total number of rows in the table.
    **
    **    1..nCol:         Number of distinct entries in index considering the
    **                     left-most N columns, where N is the same as the 
    **                     memory cell number.
    **
    **    nCol+1..2*nCol:  Previous value of indexed columns, from left to
    **                     right.
    **
    **    2*nCol+1..2*nCol+10: 10 evenly spaced samples.
    **
    ** Cells iMem through iMem+nCol are initialized to 0.  The others
    ** are initialized to NULL.
    */
    for(i=0; i<=nCol; i++){
      sqlite3VdbeAddOp2(v, OP_Integer, 0, iMem+i);
    }
    for(i=0; i<nCol; i++){
      sqlite3VdbeAddOp2(v, OP_Null, 0, iMem+nCol+i+1);
    }

    /* Start the analysis loop. This loop runs through all the entries inof
    /* Start the analysis loop. This loop runs through all the entries in
    ** the index b-tree.  */
    endOfLoop = sqlite3VdbeMakeLabel(v);
    sqlite3VdbeAddOp2(v, OP_Rewind, iIdxCur, endOfLoop);
    topOfLoop = sqlite3VdbeCurrentAddr(v);
    sqlite3VdbeAddOp2(v, OP_AddImm, iMem, 1);

    for(i=0; i<nCol; i++){
      sqlite3VdbeAddOp3(v, OP_Column, iIdxCur, i, regCol);
      if( i==0 ){

        /* Check if the record that cursor iIdxCur points to contains a
        ** value that should be stored in the sqlite_stat2 table. If so,
        ** store it.  */
        int ne = sqlite3VdbeAddOp3(v, OP_Ne, regRecno, 0, regSamplerecno);
        assert( regTabname+1==regIdxname 
             && regTabname+2==regSampleno
             && regTabname+3==regCol
        );
        sqlite3VdbeAddOp4(v, OP_MakeRecord, regTabname, 4, regRec, "aaab", 0);
        sqlite3VdbeAddOp2(v, OP_NewRowid, iStatCur+1, regRowid);
        sqlite3VdbeAddOp3(v, OP_Insert, iStatCur+1, regRec, regRowid);

        /* Calculate new values for regSamplerecno and regSampleno.
        **
        **   sampleno = sampleno + 1
        **   samplerecno = samplerecno+(remaining records)/(remaining samples)
        */
        sqlite3VdbeAddOp2(v, OP_AddImm, regSampleno, 1);
        sqlite3VdbeAddOp3(v, OP_Sample, iMem-3, regCol, regStat2+2);
      }
        sqlite3VdbeAddOp3(v, OP_Subtract, regRecno, regCount, regTemp);
        sqlite3VdbeAddOp2(v, OP_AddImm, regTemp, -1);
        sqlite3VdbeAddOp2(v, OP_Integer, SQLITE_INDEX_SAMPLES, regTemp2);
        sqlite3VdbeAddOp3(v, OP_Subtract, regSampleno, regTemp2, regTemp2);
        sqlite3VdbeAddOp3(v, OP_Divide, regTemp2, regTemp, regTemp);
        sqlite3VdbeAddOp3(v, OP_Add, regSamplerecno, regTemp, regSamplerecno);

        sqlite3VdbeJumpHere(v, ne);
        sqlite3VdbeAddOp2(v, OP_AddImm, regRecno, 1);
      }

      assert( sqlite3VdbeCurrentAddr(v)==(topOfLoop+14+2*i) );
      sqlite3VdbeAddOp3(v, OP_Ne, regCol, 0, iMem+nCol+i+1);

      /**** TODO:  add collating sequence *****/
      sqlite3VdbeChangeP5(v, SQLITE_JUMPIFNULL);
    }
    sqlite3VdbeAddOp2(v, OP_Goto, 0, endOfLoop);
    for(i=0; i<nCol; i++){
      sqlite3VdbeJumpHere(v, topOfLoop + 1 + 2*(i + 1));
      sqlite3VdbeJumpHere(v, topOfLoop+14+2*i);
      sqlite3VdbeAddOp2(v, OP_AddImm, iMem+i+1, 1);
      sqlite3VdbeAddOp3(v, OP_Column, iIdxCur, i, iMem+nCol+i+1);
    }

    /* End of the analysis loop. */
    sqlite3VdbeResolveLabel(v, endOfLoop);
    sqlite3VdbeAddOp2(v, OP_Next, iIdxCur, topOfLoop);

    **        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.
    */
    addr = sqlite3VdbeAddOp1(v, OP_IfNot, iMem);
    sqlite3VdbeAddOp4(v, OP_String8, 0, regFields, 0, pTab->zName, 0);
    sqlite3VdbeAddOp4(v, OP_String8, 0, regFields+1, 0, pIdx->zName, 0);
    regF2 = regFields+2;
    sqlite3VdbeAddOp2(v, OP_SCopy, iMem, regF2);
    sqlite3VdbeAddOp2(v, OP_SCopy, iMem, regSampleno);
    for(i=0; i<nCol; i++){
      sqlite3VdbeAddOp4(v, OP_String8, 0, regTemp, 0, " ", 0);
      sqlite3VdbeAddOp3(v, OP_Concat, regTemp, regF2, regF2);
      sqlite3VdbeAddOp3(v, OP_Concat, regTemp, regSampleno, regSampleno);
      sqlite3VdbeAddOp3(v, OP_Add, iMem, iMem+i+1, regTemp);
      sqlite3VdbeAddOp2(v, OP_AddImm, regTemp, -1);
      sqlite3VdbeAddOp3(v, OP_Divide, iMem+i+1, regTemp, regTemp);
      sqlite3VdbeAddOp1(v, OP_ToInt, regTemp);
      sqlite3VdbeAddOp3(v, OP_Concat, regTemp, regF2, regF2);
      sqlite3VdbeAddOp3(v, OP_Concat, regTemp, regSampleno, regSampleno);
    }
    sqlite3VdbeAddOp4(v, OP_MakeRecord, regFields, 3, regRec, "aaa", 0);
    sqlite3VdbeAddOp4(v, OP_MakeRecord, regTabname, 3, regRec, "aaa", 0);
    sqlite3VdbeAddOp2(v, OP_NewRowid, iStatCur, regRowid);
    sqlite3VdbeAddOp3(v, OP_Insert, iStatCur, regRec, regRowid);
    sqlite3VdbeChangeP5(v, OPFLAG_APPEND);

    /* Store the results in sqlite_stat2. */
    sqlite3VdbeAddOp4(v, OP_String8, 0, regStat2, 0, pTab->zName, 0);
    sqlite3VdbeAddOp4(v, OP_String8, 0, regStat2+1, 0, pIdx->zName, 0);
    sqlite3VdbeAddOp4(v, OP_MakeRecord, regStat2, SQLITE_INDEX_SAMPLES+2,
	regRec, "aabbbbbbbbbb", 0
    );
    sqlite3VdbeAddOp2(v, OP_NewRowid, iStatCur+1, regRowid);
    sqlite3VdbeAddOp3(v, OP_Insert, iStatCur+1, regRec, regRowid);

    sqlite3VdbeJumpHere(v, addr);
  }
}

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

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

  /* Load the statistics from the sqlite_stat2 table */
  /* Load the statistics from the sqlite_stat2 table. */
  if( rc==SQLITE_OK ){
    sqlite3_stmt *pStmt = 0;

    zSql = sqlite3MPrintf(db, 
	"SELECT idx," SQLITE_INDEX_SAMPLE_COLS " FROM %Q.sqlite_stat2",
        sInfo.zDatabase
        "SELECT idx,sampleno,sample FROM %Q.sqlite_stat2", sInfo.zDatabase
    );
    if( zSql ){
      sqlite3_stmt *pStmt = 0;
      (void)sqlite3SafetyOff(db);
      rc = sqlite3_prepare(db, zSql, -1, &pStmt, 0);
      if( rc==SQLITE_OK ){
	while( SQLITE_ROW==sqlite3_step(pStmt) ){
	  char *zIndex = (char *)sqlite3_column_text(pStmt, 0);
    if( !zSql ){
      return SQLITE_NOMEM;
    }

    (void)sqlite3SafetyOff(db);
    rc = sqlite3_prepare(db, zSql, -1, &pStmt, 0);
    assert( rc!=SQLITE_MISUSE );
    (void)sqlite3SafetyOn(db);
    sqlite3DbFree(db, zSql);
    (void)sqlite3SafetyOff(db);

    if( rc==SQLITE_OK ){
      while( sqlite3_step(pStmt)==SQLITE_ROW ){
        char *zIndex = (char *)sqlite3_column_text(pStmt, 0);
	  Index *pIdx;
          pIdx = sqlite3FindIndex(db, zIndex, sInfo.zDatabase);
	  if( pIdx ){
        Index *pIdx = sqlite3FindIndex(db, zIndex, sInfo.zDatabase);
        if( pIdx ){
	    char *pSpace;
	    IndexSample *pSample;
          int iSample = sqlite3_column_int(pStmt, 1);
	    int iCol;
	    int nAlloc = SQLITE_INDEX_SAMPLES * sizeof(IndexSample);
          if( iSample<SQLITE_INDEX_SAMPLES && iSample>=0 ){
	    for(iCol=1; iCol<=SQLITE_INDEX_SAMPLES; iCol++){
	      int eType = sqlite3_column_type(pStmt, iCol);
            int eType = sqlite3_column_type(pStmt, 2);
	      if( eType==SQLITE_TEXT || eType==SQLITE_BLOB ){
	        nAlloc += sqlite3_column_bytes(pStmt, iCol);
	      }
	    }
	    pSample = sqlite3DbMallocRaw(db, nAlloc);
	    if( !pSample ){
	      rc = SQLITE_NOMEM;
	      break;
	    }
	    sqlite3DbFree(db, pIdx->aSample);
	    pIdx->aSample = pSample;
	    pSpace = (char *)&pSample[SQLITE_INDEX_SAMPLES];
	    for(iCol=1; iCol<=SQLITE_INDEX_SAMPLES; iCol++){
	      int eType = sqlite3_column_type(pStmt, iCol);
	      pSample[iCol-1].eType = eType;
	      switch( eType ){
                case SQLITE_BLOB:

            if( pIdx->aSample==0 ){
              pIdx->aSample = (IndexSample *)sqlite3DbMallocZero(db, 
                  sizeof(IndexSample)*SQLITE_INDEX_SAMPLES
              );
	      if( pIdx->aSample==0 ){
	       	break;
	      }
            }

            if( pIdx->aSample ){
              IndexSample *pSample = &pIdx->aSample[iSample];
              if( pSample->eType==SQLITE_TEXT || pSample->eType==SQLITE_BLOB ){
                sqlite3DbFree(db, pSample->u.z);
              }
	      pSample->eType = eType;
	      if( eType==SQLITE_INTEGER || eType==SQLITE_FLOAT ){
                pSample->u.r = sqlite3_column_double(pStmt, 2);
	      }else if( eType==SQLITE_TEXT || eType==SQLITE_BLOB ){
                case SQLITE_TEXT: {
                  const char *z = (const char *)(
		      (eType==SQLITE_BLOB) ?
                      sqlite3_column_blob(pStmt, iCol):
                      sqlite3_column_text(pStmt, iCol)
		  );
                  int n = sqlite3_column_bytes(pStmt, iCol);
		  if( n>24 ){
		    n = 24;
		  }
		  pSample[iCol-1].nByte = n;
		  pSample[iCol-1].u.z = pSpace;
		  memcpy(pSpace, z, n);
                const char *z = (const char *)(
                    (eType==SQLITE_BLOB) ?
                    sqlite3_column_blob(pStmt, 2):
                    sqlite3_column_text(pStmt, 2)
                );
                int n = sqlite3_column_bytes(pStmt, 2);
                if( n>24 ){
                  n = 24;
                }
                pSample->nByte = n;
                pSample->u.z = sqlite3DbMallocRaw(db, n);
                if( pSample->u.z ){
                  memcpy(pSample->u.z, z, n);
		  pSpace += n;
		  break;
                }
                }else{
                case SQLITE_INTEGER:
                case SQLITE_FLOAT:
		  pSample[iCol-1].u.r = sqlite3_column_double(pStmt, iCol);
		  break;
                case SQLITE_NULL:
		  break;
	      }
	    }
	  }
	}
		}
              }
            }
          }
	if( rc==SQLITE_NOMEM ){
	  sqlite3_finalize(pStmt);
	}else{
	  rc = sqlite3_finalize(pStmt);
	}
        }
      }
      (void)sqlite3SafetyOn(db);
      sqlite3DbFree(db, zSql);
      rc = sqlite3_finalize(pStmt);
    }else{
      rc = SQLITE_NOMEM;
    }
    (void)sqlite3SafetyOn(db);
  }

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


#endif /* SQLITE_OMIT_ANALYZE */

/*
** Reclaim the memory used by an index
*/
static void freeIndex(Index *p){
  sqlite3 *db = p->pTable->dbMem;
  /* testcase( db==0 ); */
  if( p->aSample ){
    int i;
    for(i=0; i<SQLITE_INDEX_SAMPLES; i++){
      int e = p->aSample[i].eType;
      if( e==SQLITE_BLOB || e==SQLITE_TEXT ){
        sqlite3DbFree(db, p->aSample[i].u.z);
      }
    }
  }
  sqlite3DbFree(db, p->aSample);
  sqlite3DbFree(db, p->zColAff);
  sqlite3DbFree(db, p);
}

/*
** Remove the given index from the index hash table, and free

#include <stdint.h>
#endif
#ifdef HAVE_INTTYPES_H
#include <inttypes.h>
#endif

#define SQLITE_INDEX_SAMPLES 10
#define SQLITE_INDEX_SAMPLE_COLS "s1,s2,s3,s4,s5,s6,s7,s8,s9,s10"

/*
** This macro is used to "hide" some ugliness in casting an int
** value to a ptr value under the MSVC 64-bit compiler.   Casting
** non 64-bit values to ptr types results in a "hard" error with 
** the MSVC 64-bit compiler which this attempts to avoid.  
**

** Subtract the value in register P1 from the value in register P2
** and store the result in register P3.
** If either input is NULL, the result is NULL.
*/
/* Opcode: Divide P1 P2 P3 * *
**
** Divide the value in register P1 by the value in register P2
** and store the result in register P3.  If the value in register P2
** is zero, then the result is NULL.
** If either input is NULL, the result is NULL.
** and store the result in register P3 (P3=P2/P1). If the value in 
** register P1 is zero, then the result is NULL. If either input is 
** NULL, the result is NULL.
*/
/* Opcode: Remainder P1 P2 P3 * *
**
** Compute the remainder after integer division of the value in
** register P1 by the value in register P2 and store the result in P3. 
** If the value in register P2 is zero the result is NULL.
** If either operand is NULL, the result is NULL.

*/
case OP_Expire: {
  if( !pOp->p1 ){
    sqlite3ExpirePreparedStatements(db);
  }else{
    p->expired = 1;
  }
  break;
}


/* Opcode: Sample P1 P2 P3 * *
**
** Register P1 contains the total number of rows in the index being 
** analyzed. Register P1+1 contains an integer between 0 and 9, the
** index of the next sample required. Register P1+2 contains an index
** between 1 and *P1, the number of the next sample required. Register
** P1+3 contains the current row index.
**
** If the integer in register P1+3 is the same as the integer in register
** P1+1, then the following takes place:
**
**   (a) the contents of register P1+1 is incremented.
**
**   (b) the contents of the register identified by parameter P2 is 
**       copied to register number (P3 + X), where X is the newly
**       incremented value of register P1+1.
**
**   (c) register P1+2 is set to the index of the next sample required.
*/
case OP_Sample: {
  int p1 = pOp->p1;
  i64 iReq = p->aMem[p1+2].u.i;
  i64 iRow = p->aMem[p1+3].u.i;

  while( iReq==iRow ){
    i64 nRow = p->aMem[p1].u.i;
    int iSample = ++p->aMem[p1+1].u.i;
    Mem *pReg = &p->aMem[pOp->p3 + iSample - 1];

    assert( pReg<&p->aMem[p->nMem] );
    sqlite3VdbeMemShallowCopy(pReg, &p->aMem[pOp->p2], MEM_Ephem);
    Deephemeralize(pReg);
    if( iSample==SQLITE_INDEX_SAMPLES ){
      iReq = 0;
    }else{
      iReq = iRow + (nRow-iRow)/(SQLITE_INDEX_SAMPLES - iSample);
      p->aMem[p1+2].u.i = iReq;
    }
  }
  break;
}

#ifndef SQLITE_OMIT_SHARED_CACHE
/* Opcode: TableLock P1 P2 P3 P4 *
**
** Obtain a lock on a particular table. This instruction is only used when

      sqlite3 *db = pParse->db;
      CollSeq *pColl;
      const u8 *z;
      int n;
      if( eType==SQLITE_BLOB ){
        z = (const u8 *)sqlite3_value_blob(pVal);
        pColl = db->pDfltColl;
	assert( pColl->enc==SQLITE_UTF8 );
        assert( pColl->enc==SQLITE_UTF8 );
      }else{
	pColl = sqlite3FindCollSeq(db, SQLITE_UTF8, *pIdx->azColl, 0);
	if( sqlite3CheckCollSeq(pParse, pColl) ){
	  return SQLITE_ERROR;
	}
        pColl = sqlite3FindCollSeq(db, SQLITE_UTF8, *pIdx->azColl, 0);
        if( sqlite3CheckCollSeq(pParse, pColl) ){
          return SQLITE_ERROR;
        }
        z = (const u8 *)sqlite3ValueText(pVal, pColl->enc);
	if( !z ){
	  return SQLITE_NOMEM;
	}
        if( !z ){
          return SQLITE_NOMEM;
        }
        assert( z && pColl && pColl->xCmp );
      }
      n = sqlite3ValueBytes(pVal, pColl->enc);

      for(i=0; i<SQLITE_INDEX_SAMPLES; i++){
	int r;
        int r;
        int eSampletype = aSample[i].eType;
        if( eSampletype==SQLITE_NULL || eSampletype<eType ) continue;
        if( (eSampletype!=eType) ) break;
        if( pColl->enc==SQLITE_UTF8 ){
	  r = pColl->xCmp(pColl->pUser, aSample[i].nByte, aSample[i].u.z, n, z);
          r = pColl->xCmp(pColl->pUser, aSample[i].nByte, aSample[i].u.z, n, z);
        }else{
	  int nSample;
	  char *zSample = sqlite3Utf8to16(
          int nSample;
          char *zSample = sqlite3Utf8to16(
              db, pColl->enc, aSample[i].u.z, aSample[i].nByte, &nSample
          );
	  if( !zSample ){
	    assert( db->mallocFailed );
	    return SQLITE_NOMEM;
	  }
	  r = pColl->xCmp(pColl->pUser, nSample, zSample, n, z);
	  sqlite3DbFree(db, zSample);
          if( !zSample ){
            assert( db->mallocFailed );
            return SQLITE_NOMEM;
          }
          r = pColl->xCmp(pColl->pUser, nSample, zSample, n, z);
          sqlite3DbFree(db, zSample);
        }
	if( r>0 ) break;
        if( r>0 ) break;
      }
    }

    *piRegion = i;
  }
  return SQLITE_OK;
}

    /* Determine the value of nBound. */
    if( nEq<pProbe->nColumn ){
      int j = pProbe->aiColumn[nEq];
      if( findTerm(pWC, iCur, j, notReady, WO_LT|WO_LE|WO_GT|WO_GE, pIdx) ){
        WhereTerm *pTop = findTerm(pWC, iCur, j, notReady, WO_LT|WO_LE, pIdx);
        WhereTerm *pBtm = findTerm(pWC, iCur, j, notReady, WO_GT|WO_GE, pIdx);
	whereRangeScanEst(pParse, pProbe, nEq, pBtm, pTop, &nBound);
        whereRangeScanEst(pParse, pProbe, nEq, pBtm, pTop, &nBound);
        if( pTop ){
          wsFlags |= WHERE_TOP_LIMIT;
          used |= pTop->prereqRight;
        }
        if( pBtm ){
          wsFlags |= WHERE_BTM_LIMIT;
          used |= pBtm->prereqRight;

# 2009 August 06
#
# 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.
#
#***********************************************************************
#
# $Id: analyze.test,v 1.9 2008/08/11 18:44:58 drh Exp $

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

sqlite3_db_config_lookaside db 0 0 0

do_test analyze2-0.1 {
  execsql { CREATE TABLE t1(x PRIMARY KEY) }
  for {set i 0} {$i < 1000} {incr i} {
    execsql { INSERT INTO t1 VALUES($i) }
  }
  execsql { 
    ANALYZE;
    SELECT * FROM sqlite_stat2;
  }
} [list t1 sqlite_autoindex_t1_1 0 0   \
        t1 sqlite_autoindex_t1_1 1 111 \
        t1 sqlite_autoindex_t1_1 2 222 \
        t1 sqlite_autoindex_t1_1 3 333 \
        t1 sqlite_autoindex_t1_1 4 444 \
        t1 sqlite_autoindex_t1_1 5 555 \
        t1 sqlite_autoindex_t1_1 6 666 \
        t1 sqlite_autoindex_t1_1 7 777 \
        t1 sqlite_autoindex_t1_1 8 888 \
        t1 sqlite_autoindex_t1_1 9 999 \
]

do_test analyze2-0.2 {
  execsql {
    DELETE FROM t1 WHERe x>9;
    ANALYZE;
    SELECT tbl, idx, group_concat(sample, ' ') FROM sqlite_stat2;
  }
} {t1 sqlite_autoindex_t1_1 {0 1 2 3 4 5 6 7 8 9}}

do_test analyze2-0.3 {
  execsql {
    DELETE FROM t1 WHERE x>5;
    ANALYZE;
    SELECT * FROM sqlite_stat2;
  }
} {}

do_test analyze2-0.4 {
  execsql {
    DELETE FROM t1;
    ANALYZE;
    SELECT * FROM sqlite_stat2;
  }
} {}

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

do_test analyze2-1.1 {
  execsql { 
    DROP TABLE t1;
    CREATE TABLE t1(x, y);
    CREATE INDEX t1_x ON t1(x);
    CREATE INDEX t1_y ON t1(y);
  }

  for {set i 0} {$i < 1000} {incr i} {
    execsql { INSERT INTO t1 VALUES($i, $i) }
  }
  execsql ANALYZE
} {}
do_test analyze2-1.2 {
  execsql { EXPLAIN QUERY PLAN SELECT * FROM t1 WHERE x>500 AND y>700 }
} {0 0 {TABLE t1 WITH INDEX t1_y}}

do_test analyze2-1.3 {
  execsql { EXPLAIN QUERY PLAN SELECT * FROM t1 WHERE x>700 AND y>500 }
} {0 0 {TABLE t1 WITH INDEX t1_x}}

do_test analyze2-1.3 {
  execsql { EXPLAIN QUERY PLAN SELECT * FROM t1 WHERE y>700 AND x>500 }
} {0 0 {TABLE t1 WITH INDEX t1_y}}
do_test analyze2-1.4 {
  execsql { EXPLAIN QUERY PLAN SELECT * FROM t1 WHERE y>500 AND x>700 }
} {0 0 {TABLE t1 WITH INDEX t1_x}}

do_test analyze2-2.1 {
  eqp "SELECT * FROM t1 WHERE x BETWEEN 100 AND 200 AND y BETWEEN 400 AND 700"
} {0 0 {TABLE t1 WITH INDEX t1_x}}
do_test analyze2-2.2 {
  eqp "SELECT * FROM t1 WHERE x BETWEEN 100 AND 500 AND y BETWEEN 400 AND 700"
} {0 0 {TABLE t1 WITH INDEX t1_y}}
do_test analyze2-2.3 {
  eqp "SELECT * FROM t1 WHERE x BETWEEN -400 AND -300 AND y BETWEEN 100 AND 300"
} {0 0 {TABLE t1 WITH INDEX t1_x}}
do_test analyze2-2.4 {
  eqp "SELECT * FROM t1 WHERE x BETWEEN 100 AND 300 AND y BETWEEN -400 AND -300"
} {0 0 {TABLE t1 WITH INDEX t1_y}}

do_test analyze2-3.1 {
  eqp "SELECT * FROM t1 WHERE x BETWEEN 500 AND 100 AND y BETWEEN 100 AND 300"
} {0 0 {TABLE t1 WITH INDEX t1_x}}
do_test analyze2-3.2 {
  eqp "SELECT * FROM t1 WHERE x BETWEEN 100 AND 300 AND y BETWEEN 500 AND 100"
} {0 0 {TABLE t1 WITH INDEX t1_y}}

do_test analyze2-4.1 {
  set alphabet [list a b c d e f g h i j]
  for {set i 0} {$i < 1000} {incr i} {
    set str    [lindex $alphabet [expr ($i/100)%10]] 
    append str [lindex $alphabet [expr ($i/ 10)%10]]
    append str [lindex $alphabet [expr ($i/  1)%10]]
    execsql { INSERT INTO t1 VALUES($str, $str) }
  }
  execsql ANALYZE
  execsql { 
    SELECT tbl,idx,group_concat(sample,' ') 
    FROM sqlite_stat2 
    WHERE idx = 't1_x' 
    GROUP BY tbl,idx
  }
} {t1 t1_x {0 222 444 666 888 bba ddc ffe hhg jjj}}
do_test analyze2-4.2 {
  execsql { 
    SELECT tbl,idx,group_concat(sample,' ') 
    FROM sqlite_stat2 
    WHERE idx = 't1_y' 
    GROUP BY tbl,idx
  }
} {t1 t1_y {0 222 444 666 888 bba ddc ffe hhg jjj}}

do_test analyze2-4.3 {
  eqp "SELECT * FROM t1 WHERE x BETWEEN 100 AND 500 AND y BETWEEN 'a' AND 'b'"
} {0 0 {TABLE t1 WITH INDEX t1_y}}
do_test analyze2-4.4 {
  eqp "SELECT * FROM t1 WHERE x BETWEEN 100 AND 400 AND y BETWEEN 'a' AND 'h'"
} {0 0 {TABLE t1 WITH INDEX t1_x}}
do_test analyze2-4.5 {
  eqp "SELECT * FROM t1 WHERE x<'a' AND y>'h'"
} {0 0 {TABLE t1 WITH INDEX t1_y}}
do_test analyze2-4.6 {
  eqp "SELECT * FROM t1 WHERE x<444 AND y>'h'"
} {0 0 {TABLE t1 WITH INDEX t1_y}}
do_test analyze2-4.7 {
  eqp "SELECT * FROM t1 WHERE x<221 AND y>'h'"
} {0 0 {TABLE t1 WITH INDEX t1_x}}

do_test analyze2-5.1 {
  execsql { CREATE TABLE t3(a COLLATE nocase, b) }
  execsql { CREATE INDEX t3a ON t3(a) }
  execsql { CREATE INDEX t3b ON t3(b) }
  set alphabet [list A b C d E f G h I j]
  for {set i 0} {$i < 1000} {incr i} {
    set str    [lindex $alphabet [expr ($i/100)%10]] 
    append str [lindex $alphabet [expr ($i/ 10)%10]]
    append str [lindex $alphabet [expr ($i/  1)%10]]
    execsql { INSERT INTO t3 VALUES($str, $str) }
  }
  execsql ANALYZE
} {}
do_test analyze2-5.2 {
  execsql { 
    SELECT tbl,idx,group_concat(sample,' ') 
    FROM sqlite_stat2 
    WHERE idx = 't3a' 
    GROUP BY tbl,idx
  }
} {t3 t3a {AAA bbb CCC ddd EEE fff GGG hhh III jjj}}
do_test analyze2-5.3 {
  execsql { 
    SELECT tbl,idx,group_concat(sample,' ') 
    FROM sqlite_stat2 
    WHERE idx = 't3b' 
    GROUP BY tbl,idx
  }
} {t3 t3b {AAA CCC EEE GGG III bbb ddd fff hhh jjj}}

do_test analyze2-5.4 {
  eqp "SELECT * FROM t3 WHERE a > 'A' AND a < 'C' AND b > 'A' AND b < 'C'"
} {0 0 {TABLE t3 WITH INDEX t3b}}
do_test analyze2-5.5 {
  eqp "SELECT * FROM t3 WHERE a > 'A' AND a < 'c' AND b > 'A' AND b < 'c'"
} {0 0 {TABLE t3 WITH INDEX t3a}}

proc test_collate {enc lhs rhs} {
  # puts $enc
  return [string compare $lhs $rhs]
}

do_test analyze2-6.1 {
  add_test_collate db 0 0 1
  execsql { CREATE TABLE t4(x COLLATE test_collate) }
  execsql { CREATE INDEX t4x ON t4(x) }
  set alphabet [list a b c d e f g h i j]
  for {set i 0} {$i < 1000} {incr i} {
    set str    [lindex $alphabet [expr ($i/100)%10]] 
    append str [lindex $alphabet [expr ($i/ 10)%10]]
    append str [lindex $alphabet [expr ($i/  1)%10]]
    execsql { INSERT INTO t4 VALUES($str) }
  }
  execsql ANALYZE
} {}
do_test analyze2-6.2 {
  execsql { 
    SELECT tbl,idx,group_concat(sample,' ') 
    FROM sqlite_stat2 
    WHERE tbl = 't4' 
    GROUP BY tbl,idx
  }
} {t4 t4x {aaa bbb ccc ddd eee fff ggg hhh iii jjj}}
do_test analyze2-6.3 {
  eqp "SELECT * FROM t4 WHERE x>'ccc'"
} {0 0 {TABLE t4 WITH INDEX t4x}}
do_test analyze2-6.4 {
  eqp "SELECT * FROM t4 AS t41, t4 AS t42 WHERE t41.x>'ccc' AND t42.x>'ggg'"
} {0 1 {TABLE t4 AS t42 WITH INDEX t4x} 1 0 {TABLE t4 AS t41 WITH INDEX t4x}}
do_test analyze2-6.5 {
  eqp "SELECT * FROM t4 AS t41, t4 AS t42 WHERE t41.x>'ddd' AND t42.x>'ccc'"
} {0 0 {TABLE t4 AS t41 WITH INDEX t4x} 1 1 {TABLE t4 AS t42 WITH INDEX t4x}}

ifcapable memdebug {
  execsql { DELETE FROM t4 }
  db close
  source $testdir/malloc_common.tcl
  file copy -force test.db bak.db

  do_malloc_test analyze2-oom -tclprep {
    db close
    file copy -force bak.db test.db
    sqlite3 db test.db
    sqlite3_db_config_lookaside db 0 0 0
    add_test_collate db 0 0 1
  } -sqlbody {
    SELECT * FROM t4 AS t41, t4 AS t42 WHERE t41.x>'ddd' AND t42.x>'ccc'
  }
}

finish_test