SQLite4  Check-in [d5d0e93a57]

** Recommended number of samples for sqlite_stat3
*/
#ifndef SQLITE4_STAT3_SAMPLES
# define SQLITE4_STAT3_SAMPLES 24
#endif

/*
** Three SQL functions - stat3_init(), stat3_push(), and stat3_pop() -
** share an instance of the following structure to hold their state
** information.
*/
typedef struct Stat3Accum Stat3Accum;
struct Stat3Accum {
  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 */
  u32 iPrn;                 /* Pseudo-random number used for sampling */
  struct Stat3Sample {
    i64 iRowid;                /* Rowid in main table of the key */



    tRowcnt nEq;               /* sqlite_stat3.nEq */
    tRowcnt nLt;               /* sqlite_stat3.nLt */
    tRowcnt nDLt;              /* sqlite_stat3.nDLt */
    u8 isPSample;              /* True if a periodic sample */
    u32 iHash;                 /* Tiebreaker hash */
  } *a;                     /* An array of samples */
};

#ifdef SQLITE4_ENABLE_STAT3






/*
** Implementation of the stat3_init(C,S) SQL function.  The two parameters
** are the number of rows in the table or index (C) and the number of samples
** to accumulate (S).
**
** This routine allocates the Stat3Accum object.
**
** The return value is the Stat3Accum object (P).
*/
static void stat3Init(
  sqlite4_context *context,
  int argc,
  sqlite4_value **argv
){

  Stat3Accum *p;
  tRowcnt nRow;
  int mxSample;
  int n;

  UNUSED_PARAMETER(argc);
  nRow = (tRowcnt)sqlite4_value_int64(argv[0]);
  mxSample = sqlite4_value_int(argv[1]);
  n = sizeof(*p) + sizeof(p->a[0])*mxSample;
  p = sqlite4MallocZero( n );
  if( p==0 ){
    sqlite4_result_error_nomem(context);
    return;
  }
  p->a = (struct Stat3Sample*)&p[1];
  p->nRow = nRow;
  p->mxSample = mxSample;
  p->nPSample = p->nRow/(mxSample/3+1) + 1;
  sqlite4_randomness(sizeof(p->iPrn), &p->iPrn);
  sqlite4_result_blob(context, p, sizeof(p), sqlite4_free);
}
static const FuncDef stat3InitFuncdef = {
  2,                /* nArg */
  SQLITE4_UTF8,      /* iPrefEnc */
  0,                /* flags */
  0,                /* pUserData */
  0,                /* pNext */
  stat3Init,        /* xFunc */
  0,                /* xStep */
  0,                /* xFinalize */
  "stat3_init",     /* zName */
  0,                /* pHash */
  0                 /* pDestructor */
};


/*
** Implementation of the stat3_push(nEq,nLt,nDLt,rowid,P) 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_stat3
** table.
**
** The return value is NULL.
*/
static void stat3Push(
  sqlite4_context *context,
  int argc,
  sqlite4_value **argv
){
  Stat3Accum *p = (Stat3Accum*)sqlite4_value_blob(argv[4]);
  tRowcnt nEq = sqlite4_value_int64(argv[0]);
  tRowcnt nLt = sqlite4_value_int64(argv[1]);
  tRowcnt nDLt = sqlite4_value_int64(argv[2]);

  i64 rowid = sqlite4_value_int64(argv[3]);
  u8 isPSample = 0;
  u8 doInsert = 0;
  int iMin = p->iMin;
  struct Stat3Sample *pSample;
  int i;
  u32 h;

  if( p->nSample==p->mxSample ){
    assert( p->nSample - iMin - 1 >= 0 );
    memmove(&p->a[iMin], &p->a[iMin+1], sizeof(p->a[0])*(p->nSample-iMin-1));
    pSample = &p->a[p->nSample-1];
  }else{
    pSample = &p->a[p->nSample++];
  }










  pSample->iRowid = rowid;
  pSample->nEq = nEq;
  pSample->nLt = nLt;
  pSample->nDLt = nDLt;
  pSample->iHash = h;
  pSample->isPSample = isPSample;

  /* Find the new minimum */

      }
    }
    p->iMin = iMin;
  }
}
static const FuncDef stat3PushFuncdef = {
  5,                /* nArg */
  SQLITE4_UTF8,      /* iPrefEnc */
  0,                /* flags */
  0,                /* pUserData */
  0,                /* pNext */
  stat3Push,        /* xFunc */
  0,                /* xStep */
  0,                /* xFinalize */
  "stat3_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 stat3Get(
  sqlite4_context *context,
  int argc,
  sqlite4_value **argv
){
  int n = sqlite4_value_int(argv[1]);
  Stat3Accum *p = (Stat3Accum*)sqlite4_value_blob(argv[0]);

  assert( p!=0 );
  if( p->nSample<=n ) return;
  switch( argc ){
    case 2:  sqlite4_result_int64(context, p->a[n].iRowid); break;
    case 3:  sqlite4_result_int64(context, p->a[n].nEq);    break;
    case 4:  sqlite4_result_int64(context, p->a[n].nLt);    break;
    default: sqlite4_result_int64(context, p->a[n].nDLt);   break;







  }
}
static const FuncDef stat3GetFuncdef = {
  -1,               /* nArg */
  SQLITE4_UTF8,      /* iPrefEnc */
  0,                /* flags */
  0,                /* pUserData */
  0,                /* pNext */
  stat3Get,         /* xFunc */
  0,                /* xStep */
  0,                /* xFinalize */
  "stat3_get",     /* zName */
  0,                /* pHash */
  0                 /* pDestructor */
};
#endif /* SQLITE4_ENABLE_STAT3 */

  int regIdxname = iMem++;     /* Register containing index name */
  int regStat1 = iMem++;       /* The stat column of sqlite_stat1 */
#ifdef SQLITE4_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 regRowid = regSample;    /* Rowid of a sample */
  int regAccum = iMem++;       /* Register to hold Stat3Accum object */
  int regLoop = iMem++;        /* Loop counter */
  int regCount = iMem++;       /* Number of rows in the table or index */
  int regTemp1 = iMem++;       /* Intermediate register */
  int regTemp2 = iMem++;       /* Intermediate register */
  int once = 1;                /* One-time initialization */
  int shortJump = 0;           /* Instruction address */
  int iTabCur = pParse->nTab++; /* Table cursor */

#endif
  int regCol = iMem++;         /* Content of a column in analyzed table */
  int regRec = iMem++;         /* Register holding completed record */
  int regTemp = iMem++;        /* Temporary use register */
  int regNewRowid = iMem++;    /* Rowid for the inserted record */

  v = sqlite4GetVdbe(pParse);
  if( v==0 || NEVER(pTab==0) ){
    return;

#endif

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

    int regCnt;                  /* Total number of rows in table. */
    int regPrev;                 /* Previous index key read from database */
    int aregCard;                /* Cardinality array registers */





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

    sqlite4VdbeAddOp4(v, OP_String8, 0, regIdxname, 0, pIdx->zName, 0);

#ifdef SQLITE4_ENABLE_STAT3
    if( once ){
      once = 0;
      sqlite4OpenTable(pParse, iTabCur, iDb, pTab, OP_OpenRead);
    }
    sqlite4VdbeAddOp2(v, OP_Count, iIdxCur, regCount);
    sqlite4VdbeAddOp2(v, OP_Integer, SQLITE4_STAT3_SAMPLES, regTemp1);
    sqlite4VdbeAddOp2(v, OP_Integer, 0, regNumEq);
    sqlite4VdbeAddOp2(v, OP_Integer, 0, regNumLt);
    sqlite4VdbeAddOp2(v, OP_Integer, -1, regNumDLt);

    sqlite4VdbeAddOp3(v, OP_Null, 0, regSample, regAccum);



    sqlite4VdbeAddOp4(v, OP_Function, 1, regCount, regAccum,
                      (char*)&stat3InitFuncdef, P4_FUNCDEF);
    sqlite4VdbeChangeP5(v, 2);
#endif /* SQLITE4_ENABLE_STAT3 */

    /* The block of memory cells initialized here is used as follows.
    **

    regCnt = iMem;
    regPrev = iMem+1;
    aregCard = iMem+2;

    sqlite4VdbeAddOp2(v, OP_Integer, 0, regCnt);
    sqlite4VdbeAddOp2(v, OP_Null, 0, regPrev);
    for(i=0; i<nCol; i++){
      sqlite4VdbeAddOp2(v, OP_Integer, 1, aregCard+i);
    }

    /* Start the analysis loop. This loop runs through all the entries in
    ** the index b-tree.  */
    endOfLoop = sqlite4VdbeMakeLabel(v);
    sqlite4VdbeAddOp2(v, OP_Rewind, iIdxCur, endOfLoop);
    topOfLoop = sqlite4VdbeCurrentAddr(v);
    sqlite4VdbeAddOp2(v, OP_AddImm, regCnt, 1);  /* Increment row counter */
    sqlite4VdbeAddOp4Int(v, OP_AnalyzeKey, iIdxCur, regPrev, aregCard, nCol);

#if 0
    for(i=0; i<nCol; i++){
      CollSeq *pColl;
      sqlite4VdbeAddOp3(v, OP_Column, iIdxCur, i, regCol);
      if( i==0 ){
        /* Always record the very first row */
        addrIfNot = sqlite4VdbeAddOp1(v, OP_IfNot, iMem+1);
      }
      assert( pIdx->azColl!=0 );
      assert( pIdx->azColl[i]!=0 );
      pColl = sqlite4LocateCollSeq(pParse, pIdx->azColl[i]);
      aChngAddr[i] = sqlite4VdbeAddOp4(v, OP_Ne, regCol, 0, iMem+nCol+i+1,
                                      (char*)pColl, P4_COLLSEQ);
      sqlite4VdbeChangeP5(v, SQLITE4_NULLEQ);
      VdbeComment((v, "jump if column %d changed", i));
#ifdef SQLITE4_ENABLE_STAT3
      if( i==0 ){
        sqlite4VdbeAddOp2(v, OP_AddImm, regNumEq, 1);
        VdbeComment((v, "incr repeat count"));
      }
#endif

    }

    sqlite4VdbeAddOp2(v, OP_Goto, 0, endOfLoop);
    for(i=0; i<nCol; i++){
      sqlite4VdbeJumpHere(v, aChngAddr[i]);  /* Set jump dest for the OP_Ne */


      if( i==0 ){

        sqlite4VdbeJumpHere(v, addrIfNot);   /* Jump dest for OP_IfNot */
#ifdef SQLITE4_ENABLE_STAT3
        sqlite4VdbeAddOp4(v, OP_Function, 1, regNumEq, regTemp2,
                          (char*)&stat3PushFuncdef, P4_FUNCDEF);

        sqlite4VdbeChangeP5(v, 5);
        sqlite4VdbeAddOp3(v, OP_Column, iIdxCur, pIdx->nColumn, regRowid);
        sqlite4VdbeAddOp3(v, OP_Add, regNumEq, regNumLt, regNumLt);
        sqlite4VdbeAddOp2(v, OP_AddImm, regNumDLt, 1);
        sqlite4VdbeAddOp2(v, OP_Integer, 1, regNumEq);
#endif        
      }
      sqlite4VdbeAddOp2(v, OP_AddImm, iMem+i+1, 1);
      sqlite4VdbeAddOp3(v, OP_Column, iIdxCur, i, iMem+nCol+i+1);
    }
    sqlite4DbFree(db, aChngAddr);
#endif

    /* Always jump here after updating the iMem+1...iMem+1+nCol counters */
    sqlite4VdbeResolveLabel(v, endOfLoop);

    sqlite4VdbeAddOp2(v, OP_Next, iIdxCur, topOfLoop);
    sqlite4VdbeAddOp1(v, OP_Close, iIdxCur);
#ifdef SQLITE4_ENABLE_STAT3


    sqlite4VdbeAddOp4(v, OP_Function, 1, regNumEq, regTemp2,
                      (char*)&stat3PushFuncdef, P4_FUNCDEF);
    sqlite4VdbeChangeP5(v, 5);




    sqlite4VdbeAddOp2(v, OP_Integer, -1, regLoop);
    shortJump = 
    sqlite4VdbeAddOp2(v, OP_AddImm, regLoop, 1);

    sqlite4VdbeAddOp4(v, OP_Function, 1, regAccum, regTemp1,
                      (char*)&stat3GetFuncdef, P4_FUNCDEF);
    sqlite4VdbeChangeP5(v, 2);

    sqlite4VdbeAddOp1(v, OP_IsNull, regTemp1);
    sqlite4VdbeAddOp3(v, OP_NotExists, iTabCur, shortJump, regTemp1);
    sqlite4VdbeAddOp3(v, OP_Column, iTabCur, pIdx->aiColumn[0], regSample);
    sqlite4ColumnDefault(v, pTab, pIdx->aiColumn[0], regSample);
    sqlite4VdbeAddOp4(v, OP_Function, 1, regAccum, regNumEq,
                      (char*)&stat3GetFuncdef, P4_FUNCDEF);
    sqlite4VdbeChangeP5(v, 3);
    sqlite4VdbeAddOp4(v, OP_Function, 1, regAccum, regNumLt,
                      (char*)&stat3GetFuncdef, P4_FUNCDEF);
    sqlite4VdbeChangeP5(v, 4);
    sqlite4VdbeAddOp4(v, OP_Function, 1, regAccum, regNumDLt,
                      (char*)&stat3GetFuncdef, P4_FUNCDEF);
    sqlite4VdbeChangeP5(v, 5);
    sqlite4VdbeAddOp4(v, OP_MakeRecord, regTabname, 6, regRec, "bbbbbb", 0);
    sqlite4VdbeAddOp2(v, OP_NewRowid, iStatCur+1, regNewRowid);
    sqlite4VdbeAddOp3(v, OP_Insert, iStatCur+1, regRec, regNewRowid);
    sqlite4VdbeAddOp2(v, OP_Goto, 0, shortJump);
    sqlite4VdbeJumpHere(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

/*
** If the Index.aSample variable is not NULL, delete the aSample[] array
** and its contents.
*/
void sqlite4DeleteIndexSamples(sqlite4 *db, Index *pIdx){
#ifdef SQLITE4_ENABLE_STAT3
  if( pIdx->aSample ){
    int j;
    for(j=0; j<pIdx->nSample; j++){
      IndexSample *p = &pIdx->aSample[j];
      if( p->eType==SQLITE4_TEXT || p->eType==SQLITE_BLOB ){
        sqlite4DbFree(db, p->u.z);
      }
    }
    sqlite4DbFree(db, pIdx->aSample);
  }
  if( db && db->pnBytesFreed==0 ){
    pIdx->nSample = 0;
    pIdx->aSample = 0;
  }
#else
  UNUSED_PARAMETER(db);
  UNUSED_PARAMETER(pIdx);

*/
static int loadStat3(sqlite4 *db, const char *zDb){
  int rc;                       /* Result codes from subroutines */
  sqlite4_stmt *pStmt = 0;      /* An SQL statement being run */
  char *zSql;                   /* Text of the SQL statement */
  Index *pPrevIdx = 0;          /* Previous index in the loop */
  int idx = 0;                  /* slot in pIdx->aSample[] for next sample */
  int eType;                    /* Datatype of a sample */
  IndexSample *pSample;         /* A slot in pIdx->aSample[] */


  assert( db->lookaside.bEnabled==0 );
  if( !sqlite4FindTable(db, "sqlite_stat3", zDb) ){
    return SQLITE4_OK;
  }

  zSql = sqlite4MPrintf(db, 
      "SELECT idx,count(*) FROM %Q.sqlite_stat3"
      " GROUP BY idx", zDb);
  if( !zSql ){
    return SQLITE4_NOMEM;
  }
  rc = sqlite4_prepare(db, zSql, -1, &pStmt, 0);
  sqlite4DbFree(db, zSql);
  if( rc ) return rc;

  while( sqlite4_step(pStmt)==SQLITE4_ROW ){
    char *zIndex;   /* Index name */
    Index *pIdx;    /* Pointer to the index object */
    int nSample;    /* Number of samples */



    zIndex = (char *)sqlite4_column_text(pStmt, 0);
    if( zIndex==0 ) continue;
    nSample = sqlite4_column_int(pStmt, 1);

    pIdx = sqlite4FindIndex(db, zIndex, zDb);
    if( pIdx==0 ) continue;
    assert( pIdx->nSample==0 );

    pIdx->nSample = nSample;
    pIdx->aSample = sqlite4DbMallocZero(db, nSample*sizeof(IndexSample));
    pIdx->avgEq = pIdx->aiRowEst[1];
    if( pIdx->aSample==0 ){
      db->mallocFailed = 1;
      sqlite4_finalize(pStmt);
      return SQLITE4_NOMEM;
    }
  }
  rc = sqlite4_finalize(pStmt);
  if( rc ) return rc;

  zSql = sqlite4MPrintf(db, 
      "SELECT idx,neq,nlt,ndlt,sample FROM %Q.sqlite_stat3", zDb);
  if( !zSql ){
    return SQLITE4_NOMEM;
  }
  rc = sqlite4_prepare(db, zSql, -1, &pStmt, 0);
  sqlite4DbFree(db, zSql);
  if( rc ) return rc;

  while( sqlite4_step(pStmt)==SQLITE4_ROW ){
    char *zIndex;   /* Index name */
    Index *pIdx;    /* Pointer to the index object */
    int i;          /* Loop counter */
    tRowcnt sumEq;  /* Sum of the nEq values */



    zIndex = (char *)sqlite4_column_text(pStmt, 0);
    if( zIndex==0 ) continue;
    pIdx = sqlite4FindIndex(db, zIndex, zDb);
    if( pIdx==0 ) continue;
    if( pIdx==pPrevIdx ){
      idx++;
    }else{
      pPrevIdx = pIdx;
      idx = 0;

    }
    assert( idx<pIdx->nSample );
    pSample = &pIdx->aSample[idx];
    pSample->nEq = (tRowcnt)sqlite4_column_int64(pStmt, 1);
    pSample->nLt = (tRowcnt)sqlite4_column_int64(pStmt, 2);
    pSample->nDLt = (tRowcnt)sqlite4_column_int64(pStmt, 3);
    if( idx==pIdx->nSample-1 ){
      if( pSample->nDLt>0 ){
        for(i=0, sumEq=0; i<=idx-1; i++) sumEq += pIdx->aSample[i].nEq;
        pIdx->avgEq = (pSample->nLt - sumEq)/pSample->nDLt;
      }
      if( pIdx->avgEq<=0 ) pIdx->avgEq = 1;
    }
    eType = sqlite4_column_type(pStmt, 4);
    pSample->eType = (u8)eType;
    switch( eType ){
      case SQLITE4_INTEGER: {
        pSample->u.i = sqlite4_column_int64(pStmt, 4);
        break;
      }
      case SQLITE4_FLOAT: {
        pSample->u.r = sqlite4_column_double(pStmt, 4);
        break;
      }
      case SQLITE4_NULL: {
        break;
      }
      default: assert( eType==SQLITE4_TEXT || eType==SQLITE_BLOB ); {
        const char *z = (const char *)(
              (eType==SQLITE4_BLOB) ?
              sqlite4_column_blob(pStmt, 4):
              sqlite4_column_text(pStmt, 4)
           );
        int n = z ? sqlite4_column_bytes(pStmt, 4) : 0;
        pSample->nByte = n;
        if( n < 1){
          pSample->u.z = 0;
        }else{
          pSample->u.z = sqlite4DbMallocRaw(db, n);
          if( pSample->u.z==0 ){
            db->mallocFailed = 1;
            sqlite4_finalize(pStmt);
            return SQLITE4_NOMEM;
          }
          memcpy(pSample->u.z, z, n);
        }
      }
    }

  }
  return sqlite4_finalize(pStmt);
}
#endif /* SQLITE4_ENABLE_STAT3 */

/*
** Load the content of the sqlite_stat1 and sqlite_stat3 tables. The

  rc = sqlite4_buffer_resize(pBuf, nOrig+n);
  if( rc==SQLITE4_OK ){
    memcpy(&((u8 *)pBuf->p)[nOrig], p, n);
  }
  return rc;
}










void sqlite4_buffer_clear(sqlite4_buffer *pBuf){
  sqlite4_mm_free(pBuf->pMM, pBuf->p);
  sqlite4_buffer_init(pBuf, pBuf->pMM);
}

  sqlite4_size_t n;
};

void sqlite4_buffer_init(sqlite4_buffer *, sqlite4_mm *);
void sqlite4_buffer_clear(sqlite4_buffer *);
int sqlite4_buffer_resize(sqlite4_buffer *, sqlite4_size_t);
int sqlite4_buffer_append(sqlite4_buffer *, const void *, sqlite4_size_t);


/*
** CAPIREF: Translate Text Encodings
**
** This API function is used to translate between utf-8 and utf-16 text
** encodings. 
**

/*
** Each sample stored in the sqlite_stat3 table is represented in memory 
** using a structure of this type.  See documentation at the top of the
** analyze.c source file for additional information.
*/
struct IndexSample {
  union {
    char *z;        /* Value if eType is SQLITE4_TEXT or SQLITE4_BLOB */
    double r;       /* Value if eType is SQLITE4_FLOAT */
    i64 i;          /* Value if eType is SQLITE4_INTEGER */
  } u;
  u8 eType;         /* SQLITE4_NULL, SQLITE4_INTEGER ... etc. */
  int nByte;        /* Size in byte of text or blob. */
  tRowcnt nEq;      /* Est. number of rows where the key equals this sample */
  tRowcnt nLt;      /* Est. number of rows where key is less than this sample */
  tRowcnt nDLt;     /* Est. number of distinct keys less than this sample */
};

/*
** Each token coming out of the lexer is an instance of

  rc = sqlite4VdbeSeekEnd(pC, +1);
  nEntry = 0;
  while( rc!=SQLITE4_NOTFOUND ){
    nEntry++;
    rc = sqlite4VdbeNext(pC);
  }
  sqlite4VdbeMemSetInt64(pOut, nEntry);

  break;
}

/* Opcode: Savepoint P1 * * P4 *
**
** This opcode is used to implement the SQL BEGIN, COMMIT, ROLLBACK,
** SAVEPOINT, RELEASE and ROLLBACK TO commands. As follows:

    if( rc==SQLITE4_OK ){
      n = sqlite4GetVarint64((u8 *)aKey, nKey, (u64 *)&v);
      if( n==0 ) rc = SQLITE4_CORRUPT_BKPT;
      if( v!=pC->iRoot ) rc = SQLITE4_CORRUPT_BKPT;
    }
    if( rc==SQLITE4_OK ){
      n = sqlite4VdbeDecodeIntKey(&aKey[n], nKey-n, &v);
      if( n==0 || v==LARGEST_INT64 ) rc = SQLITE4_FULL;



    }
  }else{
    break;
  }
#ifndef SQLITE_OMIT_AUTOINCREMENT
  if( pOp->p3 && rc==SQLITE4_OK ){
    pIn3 = sqlite4RegisterInRootFrame(p, pOp->p3);
    assert( memIsValid(pIn3) );
    REGISTER_TRACE(pOp->p3, pIn3);
    sqlite4VdbeMemIntegerify(pIn3);
    assert( (pIn3->flags & MEM_Int)!=0 );  /* mem(P3) holds an integer */
    i3 = sqlite4_num_to_int64(pIn3->u.num, 0);
    if( i3==MAX_ROWID ){
      rc = SQLITE4_FULL;

    }
    if( v<i3 ) v = i3;
  }
#endif
  pOut->flags = MEM_Int;
  pOut->u.num = sqlite4_num_from_int64(v+1);
  break;

** There is no interpretation of the data.  
** It is just copied onto the P2 register exactly as 
** it is found in the database file.
**
** If the P1 cursor must be pointing to a valid row (not a NULL row)
** of a real table, not a pseudo-table.
*/
/* Opcode: RowKey P1 P2 * * *
**
** Write into register P2 the complete row key for cursor P1.
** There is no interpretation of the data.  
** The key is copied onto the P3 register exactly as 
** it is found in the database file.
**
** If the P1 cursor must be pointing to a valid row (not a NULL row)
** of a real table, not a pseudo-table.







*/
case OP_SorterData:
case OP_RowKey:
case OP_RowData: {
  VdbeCursor *pC;
  KVCursor *pCrsr;
  const KVByteArray *pData;
  KVSize nData;



  pOut = &aMem[pOp->p2];
  memAboutToChange(p, pOut);

  /* Note that RowKey and RowData are really exactly the same instruction */
  assert( pOp->p1>=0 && pOp->p1<p->nCursor );
  pC = p->apCsr[pOp->p1];
  assert( pC!=0 );
  assert( pC->nullRow==0 );
  assert( pC->pseudoTableReg==0 );
  assert( pC->pKVCur!=0 );
  pCrsr = pC->pKVCur;

  if( pOp->opcode==OP_RowKey ){
    rc = sqlite4KVCursorKey(pCrsr, &pData, &nData);






  }else{
    rc = sqlite4KVCursorData(pCrsr, 0, -1, &pData, &nData);
  }
  if( rc==SQLITE4_OK && nData>db->aLimit[SQLITE4_LIMIT_LENGTH] ){
    goto too_big;
  }
  sqlite4VdbeMemSetStr(pOut, (const char*)pData, nData, 0, SQLITE4_TRANSIENT,0);
  pOut->enc = SQLITE4_UTF8;  /* In case the blob is ever cast to text */
  UPDATE_MAX_BLOBSIZE(pOut);
  break;
}

/* Opcode: AnalyzeKey P1 P2 P3 P4
**
** P1 is an open cursor that currently points to a valid row. P2 is a 
** register that contains either a NULL value, or an index key. If it is 
** not NULL, this opcode compares the key in register P2 with the key of 
** the row P1 currently points to and determines the number of fields in
** the prefix that the two keys share in common (which may be zero).
** Call this value N. It then increments the integer values stored in
** N consecutive register starting at P3.



**
** Finally, the key belonging to the current row of cursor P1 is copied
** into register P2.
*/
case OP_AnalyzeKey: {
  VdbeCursor *pC;
  const KVByteArray *pNew;
  KVSize nNew;
  Mem *pKey;
  Mem *aIncr;
  int nEq;
  int nTotal;
  int i;
  int nSz;

  pKey = &aMem[pOp->p2];
  aIncr = &aMem[pOp->p3];
  nTotal = pOp->p4.i;
  pC = p->apCsr[pOp->p1];
  assert( pC!=0 );
  assert( pC->nullRow==0 );
  assert( pC->pseudoTableReg==0 );
  assert( pC->pKVCur!=0 );
  assert( pOp->p4type==P4_INT32 );

  rc = sqlite4KVCursorKey(pC->pKVCur, &pNew, &nNew);
  if( rc==SQLITE4_OK ){
    assert( pKey->flags & (MEM_Blob|MEM_Null) );
    if( pKey->flags & MEM_Blob ){
      for(i=0; i<nNew && i<pKey->n && pNew[i]==(KVByteArray)pKey->z[i]; i++);

      /* The two keys share i bytes in common. Figure out how many fields
      ** this corresponds to. Store said value in variable nEq. */
      sqlite4VdbeShortKey(pNew, i, LARGEST_INT32, &nEq);




      /* Increment nTotal-nEq registers */
      for(i=nEq; i<nTotal; i++){
        memAboutToChange(p, &aIncr[i]);
        sqlite4VdbeMemIntegerify(&aIncr[i]);
        aIncr[i].u.num = sqlite4_num_add(
            aIncr[i].u.num, sqlite4_num_from_int64(1)
        );
        REGISTER_TRACE(pOp->p1, &aIncr[i]);
      }
    }

    /* Copy the new key into register P2 */
    memAboutToChange(p, pKey);
    sqlite4VdbeMemSetStr(pKey, (const char*)pNew, nNew, 0, SQLITE4_TRANSIENT,0);
    pKey->enc = SQLITE4_UTF8;
    UPDATE_MAX_BLOBSIZE(pKey);
  }


  break;
}

/* Opcode: Rowid P1 P2 * * *
**
** Store in register P2 an integer which is the key of the table entry that

** be freed by the caller using sqlite4DbFree() to avoid a memory leak.
*/
int sqlite4VdbeEncodeKey(
  sqlite4 *db,                 /* The database connection */
  Mem *aIn,                    /* Values to be encoded */
  int nIn,                     /* Number of entries in aIn[] */
  int nInTotal,                /* Number of values in a complete key */
  int iTabno,                  /* The table this key applies to */
  KeyInfo *pKeyInfo,           /* Collating sequence and sort-order info */
  u8 **paOut,                  /* Write the resulting key here */
  int *pnOut,                  /* Number of bytes in the key */
  int nExtra                   /* extra bytes of space appended to the key */
){
  int i;
  int rc = SQLITE4_OK;

  x.aOut = 0;
  x.nOut = 0;
  x.nAlloc = 0;
  *paOut = 0;
  *pnOut = 0;

  if( enlargeEncoderAllocation(&x, (nIn+1)*10) ) return SQLITE4_NOMEM;

  x.nOut = sqlite4PutVarint64(x.aOut, iTabno);

  aColl = pKeyInfo->aColl;
  so = pKeyInfo->aSortOrder;
  for(i=0; i<nIn && rc==SQLITE4_OK; i++){
    rc = encodeOneKeyValue(&x, aIn+i, so ? so[i] : SQLITE4_SO_ASC,
                           i==nInTotal-1, aColl[i]);
  }

** generating the code that loops through a table looking for applicable
** rows.  Indices are selected and used to speed the search when doing
** so is applicable.  Because this module is responsible for selecting
** indices, you might also think of this module as the "query optimizer".
*/
#include "sqliteInt.h"





/*
** Trace output macros
*/
#if defined(SQLITE4_TEST) || defined(SQLITE4_DEBUG)
int sqlite4WhereTrace = 0;
#endif

**    aStat[1]      Est. number of rows equal to pVal
**
** Return SQLITE4_OK on success.
*/
static int whereKeyStats(
  Parse *pParse,              /* Database connection */
  Index *pIdx,                /* Index to consider domain of */
  sqlite4_value *pVal,        /* Value to consider */
  int roundUp,                /* Round up if true.  Round down if false */
  tRowcnt *aStat              /* OUT: stats written here */
){
  tRowcnt n;
  IndexSample *aSample;
  int i, eType;
  int isEq = 0;
  i64 v;
  double r, rS;

  assert( roundUp==0 || roundUp==1 );
  assert( pIdx->nSample>0 );

  if( pVal==0 ) return SQLITE4_ERROR;
  n = pIdx->aiRowEst[0];
  aSample = pIdx->aSample;
  eType = sqlite4_value_type(pVal);

  if( eType==SQLITE4_INTEGER ){
    v = sqlite4_value_int64(pVal);
    r = (i64)v;
    for(i=0; i<pIdx->nSample; i++){
      if( aSample[i].eType==SQLITE4_NULL ) continue;
      if( aSample[i].eType>=SQLITE4_TEXT ) break;
      if( aSample[i].eType==SQLITE4_INTEGER ){
        if( aSample[i].u.i>=v ){
          isEq = aSample[i].u.i==v;
          break;
        }
      }else{
        assert( aSample[i].eType==SQLITE4_FLOAT );
        if( aSample[i].u.r>=r ){
          isEq = aSample[i].u.r==r;
          break;
        }
      }
    }
  }else if( eType==SQLITE4_FLOAT ){
    r = sqlite4_value_double(pVal);
    for(i=0; i<pIdx->nSample; i++){
      if( aSample[i].eType==SQLITE4_NULL ) continue;
      if( aSample[i].eType>=SQLITE4_TEXT ) break;
      if( aSample[i].eType==SQLITE4_FLOAT ){
        rS = aSample[i].u.r;
      }else{
        rS = aSample[i].u.i;
      }
      if( rS>=r ){
        isEq = rS==r;
        break;
      }
    }
  }else if( eType==SQLITE4_NULL ){
    i = 0;
    if( aSample[0].eType==SQLITE4_NULL ) isEq = 1;
  }else{
    assert( eType==SQLITE4_TEXT || eType==SQLITE4_BLOB );
    for(i=0; i<pIdx->nSample; i++){
      if( aSample[i].eType==SQLITE4_TEXT || aSample[i].eType==SQLITE4_BLOB ){
        break;
      }
    }
    if( i<pIdx->nSample ){      
      sqlite4 *db = pParse->db;
      CollSeq *pColl;
      const u8 *z;
      if( eType==SQLITE4_BLOB ){
        z = (const u8 *)sqlite4_value_blob(pVal);
        pColl = db->pDfltColl;
        assert( pColl->enc==SQLITE4_UTF8 );
      }else{
        pColl = sqlite4GetCollSeq(db, SQLITE4_UTF8, 0, *pIdx->azColl);
        if( pColl==0 ){
          sqlite4ErrorMsg(pParse, "no such collation sequence: %s",
                          *pIdx->azColl);
          return SQLITE4_ERROR;
        }
        z = (const u8 *)sqlite4ValueText(pVal, pColl->enc);
        if( !z ){
          return SQLITE4_NOMEM;
        }
        assert( z && pColl && pColl->xCmp );
      }
      n = sqlite4ValueBytes(pVal, pColl->enc);
  
      for(; i<pIdx->nSample; i++){
        int c;
        int eSampletype = aSample[i].eType;
        if( eSampletype<eType ) continue;
        if( eSampletype!=eType ) break;
#ifndef SQLITE4_OMIT_UTF16
        if( pColl->enc!=SQLITE4_UTF8 ){
          int nSample;
          char *zSample = sqlite4Utf8to16(
              db, pColl->enc, aSample[i].u.z, aSample[i].nByte, &nSample
          );
          if( !zSample ){
            assert( db->mallocFailed );
            return SQLITE4_NOMEM;
          }
          c = pColl->xCmp(pColl->pUser, nSample, zSample, n, z);
          sqlite4DbFree(db, zSample);
        }else
#endif
        {
          c = pColl->xCmp(pColl->pUser, aSample[i].nByte, aSample[i].u.z, n, z);
        }
        if( c>=0 ){
          if( c==0 ) isEq = 1;
          break;
        }
      }
    }
  }

  /* At this point, aSample[i] is the first sample that is greater than
  ** or equal to pVal.  Or if i==pIdx->nSample, then all samples are less
  ** than pVal.  If aSample[i]==pVal, then isEq==1.
  */

    aStat[0] = iLower + iGap;
  }
  return SQLITE4_OK;
}
#endif /* SQLITE4_ENABLE_STAT3 */

/*
** If expression pExpr represents a literal value, set *pp to point to
** an sqlite4_value structure containing the same value, with affinity
** aff applied to it, before returning. It is the responsibility of the 
** caller to eventually release this structure by passing it to 
** sqlite4ValueFree().
**
** If the current parse is a recompile (sqlite4Reprepare()) and pExpr
** is an SQL variable that currently has a non-NULL value bound to it,
** create an sqlite4_value structure containing this value, again with
** affinity aff applied to it, instead.
**
** If neither of the above apply, set *pp to NULL.
**
** If an error occurs, return an error code. Otherwise, SQLITE4_OK.
*/
#ifdef SQLITE4_ENABLE_STAT3
static int valueFromExpr(
  Parse *pParse, 

  Expr *pExpr, 
  u8 aff, 
  sqlite4_value **pp
){






  if( pExpr->op==TK_VARIABLE
   || (pExpr->op==TK_REGISTER && pExpr->op2==TK_VARIABLE)
  ){
    int iVar = pExpr->iColumn;
    sqlite4VdbeSetVarmask(pParse->pVdbe, iVar);
    *pp = sqlite4VdbeGetValue(pParse->pReprepare, iVar, aff);








    return SQLITE4_OK;

  }


  return sqlite4ValueFromExpr(pParse->db, pExpr, SQLITE4_UTF8, aff, pp);


}
#endif















/*
** This function is used to estimate the number of rows that will be visited
** by scanning an index for a range of values. The range may have an upper
** bound, a lower bound, or both. The WHERE clause terms that set the upper
** and lower bounds are represented by pLower and pUpper respectively. For
** example, assuming that index p is on t1(a):

  double *pRangeDiv   /* OUT: Reduce search space by this divisor */
){
  int rc = SQLITE4_OK;

#ifdef SQLITE4_ENABLE_STAT3

  if( nEq==0 && p->nSample ){
    sqlite4_value *pRangeVal;


    tRowcnt iLower = 0;
    tRowcnt iUpper = p->aiRowEst[0];
    tRowcnt a[2];
    u8 aff = p->pTable->aCol[p->aiColumn[0]].affinity;




    if( pLower ){
      Expr *pExpr = pLower->pExpr->pRight;
      rc = valueFromExpr(pParse, pExpr, aff, &pRangeVal);
      assert( pLower->eOperator==WO_GT || pLower->eOperator==WO_GE );
      if( rc==SQLITE4_OK
       && whereKeyStats(pParse, p, pRangeVal, 0, a)==SQLITE4_OK
      ){
        iLower = a[0];
        if( pLower->eOperator==WO_GT ) iLower += a[1];
      }
      sqlite4ValueFree(pRangeVal);
    }
    if( rc==SQLITE4_OK && pUpper ){
      Expr *pExpr = pUpper->pExpr->pRight;
      rc = valueFromExpr(pParse, pExpr, aff, &pRangeVal);
      assert( pUpper->eOperator==WO_LT || pUpper->eOperator==WO_LE );
      if( rc==SQLITE4_OK
       && whereKeyStats(pParse, p, pRangeVal, 1, a)==SQLITE4_OK
      ){
        iUpper = a[0];
        if( pUpper->eOperator==WO_LE ) iUpper += a[1];
      }
      sqlite4ValueFree(pRangeVal);
    }

    if( rc==SQLITE4_OK ){
      if( iUpper<=iLower ){
        *pRangeDiv = (double)p->aiRowEst[0];
      }else{
        *pRangeDiv = (double)p->aiRowEst[0]/(double)(iUpper - iLower);
      }
      WHERETRACE(("range scan regions: %u..%u  div=%g\n",

*/
static int whereEqualScanEst(
  Parse *pParse,       /* Parsing & code generating context */
  Index *p,            /* The index whose left-most column is pTerm */
  Expr *pExpr,         /* Expression for VALUE in the x=VALUE constraint */
  double *pnRow        /* Write the revised row estimate here */
){
  sqlite4_value *pRhs = 0;  /* VALUE on right-hand side of pTerm */
  u8 aff;                   /* Column affinity */
  int rc;                   /* Subfunction return code */
  tRowcnt a[2];             /* Statistics */

  assert( p->aSample!=0 );
  assert( p->nSample>0 );


  aff = p->pTable->aCol[p->aiColumn[0]].affinity;
  if( pExpr ){



    rc = valueFromExpr(pParse, pExpr, aff, &pRhs);
    if( rc ) goto whereEqualScanEst_cancel;

  }else{


    pRhs = sqlite4ValueNew(pParse->db);
  }

  if( pRhs==0 ) return SQLITE4_NOTFOUND;
  rc = whereKeyStats(pParse, p, pRhs, 0, a);
  if( rc==SQLITE4_OK ){
    WHERETRACE(("equality scan regions: %d\n", (int)a[1]));
    *pnRow = a[1];
  }
whereEqualScanEst_cancel:
  sqlite4ValueFree(pRhs);
  return rc;
}
#endif /* defined(SQLITE4_ENABLE_STAT3) */

#ifdef SQLITE4_ENABLE_STAT3
/*
** Estimate the number of rows that will be returned based on

} {t3 t3i1 t3i3 t4 t4i1 t4i2 t3 t4}
ifcapable stat3 {
  do_test analyze-5.3 {
    execsql {
      SELECT DISTINCT idx FROM sqlite_stat3 ORDER BY 1;
      SELECT DISTINCT tbl FROM sqlite_stat3 ORDER BY 1;
    }
  } {t3i1 t3i3 t4 t4i1 t4i2 t3 t4}
}
do_test analyze-5.4 {
  execsql {
    DROP TABLE t3;
    SELECT DISTINCT idx FROM sqlite_stat1 ORDER BY 1;
    SELECT DISTINCT tbl FROM sqlite_stat1 ORDER BY 1;
  }
} {t4 t4i1 t4i2 t4}
ifcapable stat3 {
  do_test analyze-5.5 {
    execsql {
      SELECT DISTINCT idx FROM sqlite_stat3 ORDER BY 1;
      SELECT DISTINCT tbl FROM sqlite_stat3 ORDER BY 1;
    }
  } {t4i1 t4i2 t4}
}

# This test corrupts the database file so it must be the last test
# in the series.
#
do_test analyze-99.1 {
  execsql {

  tkt-02a8e81d44.test tkt-26ff0c2d1e.test tkt-2d1a5c67d.test
  tkt-2ea2425d34.test tkt-31338dca7e.test
  tkt-38cb5df375.test tkt-3998683a16.test tkt-3a77c9714e.test
  tkt-3fe897352e.test tkt-4a03edc4c8.test tkt-54844eea3f.test
  tkt-5e10420e8d.test tkt-752e1646fc.test tkt-80ba201079.test
  tkt-80e031a00f.test tkt-91e2e8ba6f.test tkt-9d68c883.test
  tkt-b1d3a2e531.test tkt-b351d95f9.test  tkt-b72787b1.test
  tkt-bd484a090c.test tkt-cbd054fa6b.test tkt-d11f09d36e.test
  tkt-d635236375.test tkt-f973c7ac31.test tkt-fa7bf5ec.test
  tkt1443.test tkt1444.test tkt1449.test tkt1473.test tkt1501.test
  tkt1514.test tkt1537.test tkt1873.test
  tkt2141.test tkt2192.test tkt2213.test tkt2285.test tkt2339.test
  tkt2391.test tkt2450.test tkt2640.test tkt2767.test tkt2817.test
  tkt2822.test tkt2832.test tkt2927.test tkt2942.test tkt3121.test
  tkt3201.test tkt3292.test tkt3298.test tkt3334.test tkt3346.test

do_test 79.1 {
  set r1 [expr 0.684377705997032]
  execsql "CREATE TABLE t1(x UNIQUE)"
  execsql "INSERT INTO t1 VALUES($r1)"
  execsql "PRAGMA integrity_check"
} {ok}


















finish_test