SQLite

**
** @(#) $Id: analyze.c,v 1.52 2009/04/16 17:45:48 drh Exp $
*/
#ifndef SQLITE_OMIT_ANALYZE
#include "sqliteInt.h"

/*
** This routine generates code that opens the sqlite_stat1 table for
** writing with cursor iStatCur. The sqlite_stat2 table is opened
** for writing using cursor (iStatCur+1).
**
** If the sqlite_stat1 tables does not previously exist, it is created.
** If it does previously exist, all entires associated with table zWhere
** are removed.  If zWhere==0 then all entries are removed.
*/
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 };
  int aRoot[] = {0, 0};
  int aCreateTbl[] = {0, 0};

  int i;
  sqlite3 *db = pParse->db;
  Db *pDb;



  Vdbe *v = sqlite3GetVdbe(pParse);

  if( v==0 ) return;
  assert( sqlite3BtreeHoldsAllMutexes(db) );
  assert( sqlite3VdbeDb(v)==db );
  pDb = &db->aDb[iDb];

  for(i=0; i<ArraySize(aName); i++){
    Table *pStat;
    if( (pStat = sqlite3FindTable(db, aName[i], pDb->zName))==0 ){
      /* The sqlite_stat[12] table does not exist. Create it. Note that a 
      ** side-effect of the CREATE TABLE statement is to leave the rootpage 
      ** of the new table in register pParse->regRoot. This is important 
      ** because the OpenWrite opcode below will be needing it. */
      sqlite3NestedParse(pParse,
          "CREATE TABLE %Q.%s(%s)", pDb->zName, aName[i], aCols[i]

      );
      aRoot[i] = pParse->regRoot;








      aCreateTbl[i] = 1;
    }else{
      /* The table already exists. If zWhere is not NULL, delete all entries 
      ** associated with the table zWhere. If zWhere is NULL, delete the
      ** entire contents of the table. */
      aRoot[i] = pStat->tnum;









      sqlite3TableLock(pParse, iDb, aRoot[i], 1, aName[i]);
      if( zWhere ){
        sqlite3NestedParse(pParse,
           "DELETE FROM %Q.%s WHERE tbl=%Q", pDb->zName, aName[i], zWhere
        );
      }else{
        /* The sqlite_stat[12] table already exists.  Delete all rows. */
        sqlite3VdbeAddOp2(v, OP_Clear, aRoot[i], iDb);
      }
    }
  }

  /* Open the sqlite_stat[12] tables for writing. */
  for(i=0; i<ArraySize(aName); i++){
    sqlite3VdbeAddOp3(v, OP_OpenWrite, iStatCur+i, aRoot[i], iDb);
    sqlite3VdbeChangeP4(v, -1, (char *)3, P4_INT32);
    sqlite3VdbeChangeP5(v, aCreateTbl[i]);
  }
}

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

    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){
    KeyInfo *pKey = sqlite3IndexKeyinfo(pParse, pIdx);
    int regFields;    /* Register block for building records */
    int regRec;       /* Register holding completed record */
    int regTemp;      /* Temporary use register */
    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
    */
    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;
    }

    /* Fill in the register with the total number of rows. */
    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);

    /* 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
    ** 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 ){
        sqlite3VdbeAddOp3(v, OP_Sample, iMem-3, regCol, regStat2+2);
      }
      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));
      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);
    sqlite3VdbeAddOp1(v, OP_Close, iIdxCur);

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

      sqlite3VdbeAddOp1(v, OP_ToInt, regTemp);
      sqlite3VdbeAddOp3(v, OP_Concat, regTemp, regF2, regF2);
    }
    sqlite3VdbeAddOp4(v, OP_MakeRecord, regFields, 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.

  sqlite3 *db = pParse->db;
  Schema *pSchema = db->aDb[iDb].pSchema;    /* Schema of database iDb */
  HashElem *k;
  int iStatCur;
  int iMem;

  sqlite3BeginWriteOperation(pParse, 0, iDb);
  iStatCur = pParse->nTab;
  pParse->nTab += 2;
  openStatTable(pParse, iDb, iStatCur, 0);
  iMem = pParse->nMem+1;
  for(k=sqliteHashFirst(&pSchema->tblHash); k; k=sqliteHashNext(k)){
    Table *pTab = (Table*)sqliteHashData(k);
    analyzeOneTable(pParse, pTab, iStatCur, iMem);
  }
  loadAnalysis(pParse, iDb);

  int iDb;
  int iStatCur;

  assert( pTab!=0 );
  assert( sqlite3BtreeHoldsAllMutexes(pParse->db) );
  iDb = sqlite3SchemaToIndex(pParse->db, pTab->pSchema);
  sqlite3BeginWriteOperation(pParse, 0, iDb);
  iStatCur = pParse->nTab;
  pParse->nTab += 2;
  openStatTable(pParse, iDb, iStatCur, pTab->zName);
  analyzeOneTable(pParse, pTab, iStatCur, pParse->nMem+1);
  loadAnalysis(pParse, iDb);
}

/*
** Generate code for the ANALYZE command.  The parser calls this routine

    pIndex->aiRowEst[i] = v;
    if( *z==' ' ) z++;
  }
  return 0;
}

/*
** Load the content of the sqlite_stat1 and sqlite_stat2 tables into the 
** index hash tables.
*/
int sqlite3AnalysisLoad(sqlite3 *db, int iDb){
  analysisInfo sInfo;
  HashElem *i;
  char *zSql;
  int rc;

  /* Check to make sure the sqlite_stat1 table existss */
  sInfo.db = db;
  sInfo.zDatabase = db->aDb[iDb].zName;
  if( sqlite3FindTable(db, "sqlite_stat1", sInfo.zDatabase)==0 ){
     return SQLITE_ERROR;
  }


  /* Load new statistics out of the sqlite_stat1 table */
  zSql = sqlite3MPrintf(db, "SELECT idx, stat FROM %Q.sqlite_stat1",
                        sInfo.zDatabase);
  if( zSql==0 ){
    rc = SQLITE_NOMEM;
  }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 */
  if( rc==SQLITE_OK ){
    zSql = sqlite3MPrintf(db, 
	"SELECT idx," SQLITE_INDEX_SAMPLE_COLS " 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);
	  Index *pIdx;
          pIdx = sqlite3FindIndex(db, zIndex, sInfo.zDatabase);
	  if( pIdx ){
	    char *pSpace;
	    IndexSample *pSample;
	    int iCol;
	    int nAlloc = SQLITE_INDEX_SAMPLES * sizeof(IndexSample);
	    for(iCol=1; iCol<=SQLITE_INDEX_SAMPLES; iCol++){
	      int eType = sqlite3_column_type(pStmt, iCol);
	      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:
                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);
		  pSpace += n;
		  break;
                }
                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);
    }else{
      rc = SQLITE_NOMEM;
    }
  }

  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 ); */
  sqlite3DbFree(db, p->aSample);
  sqlite3DbFree(db, p->zColAff);
  sqlite3DbFree(db, p);
}

/*
** Remove the given index from the index hash table, and free
** its memory structures.

    }
  }
  if( isAppropriateForFactoring(pExpr) ){
    int r1 = ++pParse->nMem;
    int r2;
    r2 = sqlite3ExprCodeTarget(pParse, pExpr, r1);
    if( NEVER(r1!=r2) ) sqlite3ReleaseTempReg(pParse, r1);
    pExpr->iColumn = pExpr->op;
    pExpr->op = TK_REGISTER;
    pExpr->iTable = r2;
    return WRC_Prune;
  }
  return WRC_Continue;
}

#ifdef HAVE_STDINT_H
#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.  
**
** A simple compiler pragma or casting sequence could not be found

typedef struct ExprList ExprList;
typedef struct ExprSpan ExprSpan;
typedef struct FKey FKey;
typedef struct FuncDef FuncDef;
typedef struct FuncDefHash FuncDefHash;
typedef struct IdList IdList;
typedef struct Index Index;
typedef struct IndexSample IndexSample;
typedef struct KeyClass KeyClass;
typedef struct KeyInfo KeyInfo;
typedef struct Lookaside Lookaside;
typedef struct LookasideSlot LookasideSlot;
typedef struct Module Module;
typedef struct NameContext NameContext;
typedef struct Parse Parse;

  u8 onError;      /* OE_Abort, OE_Ignore, OE_Replace, or OE_None */
  u8 autoIndex;    /* True if is automatically created (ex: by UNIQUE) */
  char *zColAff;   /* String defining the affinity of each column */
  Index *pNext;    /* The next index associated with the same table */
  Schema *pSchema; /* Schema containing this index */
  u8 *aSortOrder;  /* Array of size Index.nColumn. True==DESC, False==ASC */
  char **azColl;   /* Array of collation sequence names for index */
  IndexSample *aSample;    /* Array of SQLITE_INDEX_SAMPLES samples */
};

/*
** Each sample stored in the sqlite_stat2 table is represented in memory 
** using a structure of this type.
*/
struct IndexSample {
  union {
    char *z;        /* Value if eType is SQLITE_TEXT or SQLITE_BLOB */
    double r;       /* Value if eType is SQLITE_FLOAT or SQLITE_INTEGER */
  } u;
  u8 eType;         /* SQLITE_NULL, SQLITE_INTEGER ... etc. */
  u8 nByte;         /* Size in byte of text or blob. */
};

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

const void *sqlite3ValueText(sqlite3_value*, u8);
int sqlite3ValueBytes(sqlite3_value*, u8);
void sqlite3ValueSetStr(sqlite3_value*, int, const void *,u8, 
                        void(*)(void*));
void sqlite3ValueFree(sqlite3_value*);
sqlite3_value *sqlite3ValueNew(sqlite3 *);
char *sqlite3Utf16to8(sqlite3 *, const void*, int);
char *sqlite3Utf8to16(sqlite3 *, int, char *, int, int *);
int sqlite3ValueFromExpr(sqlite3 *, Expr *, u8, u8, sqlite3_value **);
void sqlite3ValueApplyAffinity(sqlite3_value *, u8, u8);
#ifndef SQLITE_AMALGAMATION
extern const unsigned char sqlite3UpperToLower[];
extern const unsigned char sqlite3CtypeMap[];
extern SQLITE_WSD struct Sqlite3Config sqlite3Config;
extern SQLITE_WSD FuncDefHash sqlite3GlobalFunctions;

    case SQLITE_UTF16BE:
      Tcl_ListObjAppendElement(i,pX,Tcl_NewStringObj("UTF-16BE",-1));
      break;
    default:
      assert(0);
  }

  sqlite3BeginBenignMalloc();
  pVal = sqlite3ValueNew(0);
  if( pVal ){
    sqlite3ValueSetStr(pVal, nA, zA, encin, SQLITE_STATIC);
    n = sqlite3_value_bytes(pVal);
    Tcl_ListObjAppendElement(i,pX,
        Tcl_NewStringObj((char*)sqlite3_value_text(pVal),n));
    sqlite3ValueSetStr(pVal, nB, zB, encin, SQLITE_STATIC);
    n = sqlite3_value_bytes(pVal);
    Tcl_ListObjAppendElement(i,pX,
        Tcl_NewStringObj((char*)sqlite3_value_text(pVal),n));
    sqlite3ValueFree(pVal);
  }
  sqlite3EndBenignMalloc();

  Tcl_EvalObjEx(i, pX, 0);
  Tcl_DecrRefCount(pX);
  Tcl_GetIntFromObj(i, Tcl_GetObjResult(i), &res);
  return res;
}
static int test_collate(

    sqlite3VdbeMemRelease(&m);
    m.z = 0;
  }
  assert( (m.flags & MEM_Term)!=0 || db->mallocFailed );
  assert( (m.flags & MEM_Str)!=0 || db->mallocFailed );
  return (m.flags & MEM_Dyn)!=0 ? m.z : sqlite3DbStrDup(db, m.z);
}

/*
** Convert a UTF-8 string to the UTF-16 encoding specified by parameter
** enc. A pointer to the new string is returned, and the value of *pnOut
** 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.
*/
char *sqlite3Utf8to16(sqlite3 *db, int 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 );
    return 0;
  }
  assert( m.z==m.zMalloc );
  *pnOut = m.n;
  return m.z;
}

/*
** pZ is a UTF-16 encoded unicode string at least nChar characters long.
** Return the number of bytes in the first nChar unicode characters
** in pZ.  nChar must be non-negative.
*/
int sqlite3Utf16ByteLen(const void *zIn, int nChar){

** then only the currently executing statement is affected. 
*/
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 *
**

  sqlite3_value *pVal = 0;

  if( !pExpr ){
    *ppVal = 0;
    return SQLITE_OK;
  }
  op = pExpr->op;
  if( op==TK_REGISTER ){
    op = pExpr->iColumn;
  }

  if( op==TK_STRING || op==TK_FLOAT || op==TK_INTEGER ){
    pVal = sqlite3ValueNew(db);
    if( pVal==0 ) goto no_mem;
    if( ExprHasProperty(pExpr, EP_IntValue) ){
      sqlite3VdbeMemSetInt64(pVal, (i64)pExpr->u.iValue);
    }else{

  /* Try to find a more efficient access pattern by using multiple indexes
  ** to optimize an OR expression within the WHERE clause. 
  */
  bestOrClauseIndex(pParse, pWC, pSrc, notReady, pOrderBy, pCost);
}
#endif /* SQLITE_OMIT_VIRTUALTABLE */

/*
** Argument pIdx is a pointer to an index structure that has an array of
** SQLITE_INDEX_SAMPLES evenly spaced samples of the first indexed column
** stored in Index.aSample. The domain of values stored in said column
** may be thought of as divided into (SQLITE_INDEX_SAMPLES+1) regions.
** Region 0 contains all values smaller than the first sample value. Region
** 1 contains values larger than or equal to the value of the first sample,
** but smaller than the value of the second. And so on.
**
** If successful, this function determines which of the regions value 
** pVal lies in, sets *piRegion to the region index and returns SQLITE_OK.
** Or, if an OOM occurs while converting text values between encodings,
** SQLITE_NOMEM is returned.
*/
static int whereRangeRegion(
  Parse *pParse,              /* Database connection */
  Index *pIdx,                /* Index to consider domain of */
  sqlite3_value *pVal,        /* Value to consider */
  int *piRegion               /* OUT: Region of domain in which value lies */
){
  if( pVal ){
    IndexSample *aSample = pIdx->aSample;
    int i = 0;
    int eType = sqlite3_value_type(pVal);

    if( eType==SQLITE_INTEGER || eType==SQLITE_FLOAT ){
      double r = sqlite3_value_double(pVal);
      for(i=0; i<SQLITE_INDEX_SAMPLES; i++){
        if( aSample[i].eType==SQLITE_NULL ) continue;
        if( aSample[i].eType>=SQLITE_TEXT || aSample[i].u.r>r ) break;
      }
    }else if( eType==SQLITE_TEXT || eType==SQLITE_BLOB ){
      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 );
      }else{
	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;
	}
        assert( z && pColl && pColl->xCmp );
      }
      n = sqlite3ValueBytes(pVal, pColl->enc);

      for(i=0; i<SQLITE_INDEX_SAMPLES; i++){
	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);
        }else{
	  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( r>0 ) break;
      }
    }

    *piRegion = i;
  }
  return SQLITE_OK;
}

/*
** This function is used to estimate the number of rows that will be visited
** by scanning an index for a range of values. The range may have an upper
** bound, a lower bound, or both. The WHERE clause terms that set the upper
** and lower bounds are represented by pLower and pUpper respectively. For
** example, assuming that index p is on t1(a):
**
**   ... FROM t1 WHERE a > ? AND a < ? ...
**                    |_____|   |_____|
**                       |         |
**                     pLower    pUpper
**
** If the upper or lower bound is not present, then NULL should be passed in
** place of a WhereTerm.
**
** The nEq parameter is passed the index of the index column subject to the
** range constraint. Or, equivalently, the number of equality constraints
** optimized by the proposed index scan. For example, assuming index p is
** on t1(a, b), and the SQL query is:
**
**   ... FROM t1 WHERE a = ? AND b > ? AND b < ? ...
**
** then nEq should be passed the value 1 (as the range restricted column,
** b, is the second left-most column of the index). Or, if the query is:
**
**   ... FROM t1 WHERE a > ? AND a < ? ...
**
** then nEq should be passed 0.
**
** The returned value is an integer between 1 and 9, inclusive. A return
** value of 1 indicates that the proposed range scan is expected to visit
** approximately 1/9 (11%) of the rows selected by the nEq equality constraints
** (if any). A return value of 9 indicates that it is expected that the
** range scan will visit 9/9 (100%) of the rows selected by the equality
** constraints.
*/
static int whereRangeScanEst(
  Parse *pParse,
  Index *p, 
  int nEq, 
  WhereTerm *pLower, 
  WhereTerm *pUpper,
  int *piEst                      /* OUT: Return value */
){
  sqlite3 *db = pParse->db;
  sqlite3_value *pLowerVal = 0;
  sqlite3_value *pUpperVal = 0;
  int rc = SQLITE_OK;

  if( nEq==0 && p->aSample ){
    int iEst;
    int iUpper = SQLITE_INDEX_SAMPLES;
    int iLower = 0;
    u8 aff = p->pTable->aCol[0].affinity;
    if( pLower ){
      Expr *pExpr = pLower->pExpr->pRight;
      rc = sqlite3ValueFromExpr(db, pExpr, SQLITE_UTF8, aff, &pLowerVal);
      if( !pLowerVal ) goto fallback;
    }
    if( pUpper ){
      Expr *pExpr = pUpper->pExpr->pRight;
      rc = sqlite3ValueFromExpr(db, pExpr, SQLITE_UTF8, aff, &pUpperVal);
      if( !pUpperVal ){
        sqlite3ValueFree(pLowerVal);
        goto fallback;
      }
    }

    rc = whereRangeRegion(pParse, p, pUpperVal, &iUpper);
    if( rc==SQLITE_OK ){
      rc = whereRangeRegion(pParse, p, pLowerVal, &iLower);
    }

    iEst = iUpper - iLower;
    if( iEst>=SQLITE_INDEX_SAMPLES ) iEst = SQLITE_INDEX_SAMPLES-1;
    else if( iEst<1 ) iEst = 1;

    sqlite3ValueFree(pLowerVal);
    sqlite3ValueFree(pUpperVal);
    *piEst = iEst;
    return rc;
  }

fallback:
  assert( pLower || pUpper );
  *piEst = (SQLITE_INDEX_SAMPLES-1) / ((pLower&&pUpper)?9:3);
  return rc;
}


/*
** Find the query plan for accessing a particular table.  Write the
** best query plan and its cost into the WhereCost object supplied as the
** last parameter.
**
** The lowest cost plan wins.  The cost is an estimate of the amount of

    **
    **             SELECT a, b    FROM tbl WHERE a = 1;
    **             SELECT a, b, c FROM tbl WHERE a = 1;
    */
    int nEq;
    int bInEst = 0;
    int nInMul = 1;
    int nBound = 9;
    int bSort = 0;
    int bLookup = 0;

    /* Determine the values of nEq and nInMul */
    for(nEq=0; nEq<pProbe->nColumn; nEq++){
      WhereTerm *pTerm;           /* A single term of the WHERE clause */
      int j = pProbe->aiColumn[nEq];

    /* 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);
        if( pTop ){
          wsFlags |= WHERE_TOP_LIMIT;

          used |= pTop->prereqRight;
        }
        if( pBtm ){
          wsFlags |= WHERE_BTM_LIMIT;

          used |= pBtm->prereqRight;
        }
        wsFlags |= (WHERE_COLUMN_RANGE|WHERE_ROWID_RANGE);
      }
    }else if( pProbe->onError!=OE_None ){
      testcase( wsFlags & WHERE_COLUMN_IN );
      testcase( wsFlags & WHERE_COLUMN_NULL );

    ** works well in practice and causes the test suite to pass.  */
    nRow = (double)(aiRowEst[nEq] * nInMul);
    if( bInEst && nRow*2>aiRowEst[0] ){
      nRow = aiRowEst[0]/2;
      nInMul = nRow / aiRowEst[nEq];
    }
    cost = nRow + nInMul*estLog(aiRowEst[0]);
    nRow = nRow * (double)nBound / 9.0;
    cost = cost * (double)nBound / 9.0;
    if( bSort ){
      cost += cost*estLog(cost);
    }
    if( pIdx && bLookup==0 ){
      cost /= 2;
    }
#endif

  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 sqlite_stat2 t1 t2 t3 t4}
}

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