/*

** 2005-07-08

**

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

**

*************************************************************************

** This file contains code associated with the ANALYZE command.

**

** The ANALYZE command gather statistics about the content of tables

** and indices. These statistics are made available to the query planner

** to help it make better decisions about how to perform queries.

**

** The following system tables are or have been supported:

**

** CREATE TABLE sqlite_stat1(tbl, idx, stat);

** CREATE TABLE sqlite_stat2(tbl, idx, sampleno, sample);

** CREATE TABLE sqlite_stat3(tbl, idx, nEq, nLt, nDLt, sample);

** CREATE TABLE sqlite_stat4(tbl, idx, nEq, nLt, nDLt, sample);

**

** Additional tables might be added in future releases of SQLite.

** The sqlite_stat2 table is not created or used unless the SQLite version

** is between 3.6.18 and 3.7.8, inclusive, and unless SQLite is compiled

** with SQLITE_ENABLE_STAT2. The sqlite_stat2 table is deprecated.

** The sqlite_stat2 table is superseded by sqlite_stat3, which is only

** created and used by SQLite versions 3.7.9 and later and with

** SQLITE_ENABLE_STAT3 defined. The functionality of sqlite_stat3

** is a superset of sqlite_stat2. The sqlite_stat4 is an enhanced

** version of sqlite_stat3 and is only available when compiled with

** SQLITE_ENABLE_STAT4 and in SQLite versions 3.8.1 and later. It is

** not possible to enable both STAT3 and STAT4 at the same time. If they

** are both enabled, then STAT4 takes precedence.

**

** For most applications, sqlite_stat1 provides all the statistics required

** for the query planner to make good choices.

**

** Format of sqlite_stat1:

**

** There is normally one row per index, with the index identified by the

** name in the idx column. The tbl column is the name of the table to

** which the index belongs. In each such row, the stat column will be

** a string consisting of a list of integers. The first integer in this

** list is the number of rows in the index. (This is the same as the

** number of rows in the table, except for partial indices.) The second

** integer is the average number of rows in the index that have the same

** value in the first column of the index. The third integer is the average

** number of rows in the index that have the same value for the first two

** columns. The N-th integer (for N>1) is the average number of rows in

** the index which have the same value for the first N-1 columns. For

** a K-column index, there will be K+1 integers in the stat column. If

** the index is unique, then the last integer will be 1.

**

** The list of integers in the stat column can optionally be followed

** by the keyword "unordered". The "unordered" keyword, if it is present,

** must be separated from the last integer by a single space. If the

** "unordered" keyword is present, then the query planner assumes that

** the index is unordered and will not use the index for a range query.

**

** If the sqlite_stat1.idx column is NULL, then the sqlite_stat1.stat

** column contains a single integer which is the (estimated) number of

** rows in the table identified by sqlite_stat1.tbl.

**

** Format of sqlite_stat2:

**

** The sqlite_stat2 is only created and is only used if SQLite is compiled

** with SQLITE_ENABLE_STAT2 and if the SQLite version number is between

** 3.6.18 and 3.7.8. The "stat2" table contains additional information

** about the distribution of keys within an index. The index is identified by

** the "idx" column and the "tbl" column is the name of the table to which

** the index belongs. There are usually 10 rows in the sqlite_stat2

** table for each index.

**

** The sqlite_stat2 entries for an index that have sampleno between 0 and 9

** inclusive are samples of the left-most key value in the index taken at

** evenly spaced points along the index. Let the number of samples be S

** (10 in the standard build) and let C be the number of rows in the index.

** Then the sampled rows are given by:

**

** rownumber = (i*C*2 + C)/(S*2)

**

** For i between 0 and S-1. Conceptually, the index space is divided into

** S uniform buckets and the samples are the middle row from each bucket.

**

** The format for sqlite_stat2 is recorded here for legacy reference. This

** version of SQLite does not support sqlite_stat2. It neither reads nor

** writes the sqlite_stat2 table. This version of SQLite only supports

** sqlite_stat3.

**

** Format for sqlite_stat3:

**

** The sqlite_stat3 format is a subset of sqlite_stat4. Hence, the

** sqlite_stat4 format will be described first. Further information

** about sqlite_stat3 follows the sqlite_stat4 description.

**

** Format for sqlite_stat4:

**

** As with sqlite_stat2, the sqlite_stat4 table contains histogram data

** to aid the query planner in choosing good indices based on the values

** that indexed columns are compared against in the WHERE clauses of

** queries.

**

** The sqlite_stat4 table contains multiple entries for each index.

** The idx column names the index and the tbl column is the table of the

** index. If the idx and tbl columns are the same, then the sample is

** of the INTEGER PRIMARY KEY. The sample column is a blob which is the

** binary encoding of a key from the index. The nEq column is a

** list of integers. The first integer is the approximate number

** of entries in the index whose left-most column exactly matches

** the left-most column of the sample. The second integer in nEq

** is the approximate number of entries in the index where the

** first two columns match the first two columns of the sample.

** And so forth. nLt is another list of integers that show the approximate

** number of entries that are strictly less than the sample. The first

** integer in nLt contains the number of entries in the index where the

** left-most column is less than the left-most column of the sample.

** The K-th integer in the nLt entry is the number of index entries

** where the first K columns are less than the first K columns of the

** sample. The nDLt column is like nLt except that it contains the

** number of distinct entries in the index that are less than the

** sample.

**

** There can be an arbitrary number of sqlite_stat4 entries per index.

** The ANALYZE command will typically generate sqlite_stat4 tables

** that contain between 10 and 40 samples which are distributed across

** the key space, though not uniformly, and which include samples with

** large nEq values.

**

** Format for sqlite_stat3 redux:

**

** The sqlite_stat3 table is like sqlite_stat4 except that it only

** looks at the left-most column of the index. The sqlite_stat3.sample

** column contains the actual value of the left-most column instead

** of a blob encoding of the complete index key as is found in

** sqlite_stat4.sample. The nEq, nLt, and nDLt entries of sqlite_stat3

** all contain just a single integer which is the same as the first

** integer in the equivalent columns in sqlite_stat4.

*/

#ifndef SQLITE_OMIT_ANALYZE

#include "sqliteInt.h"

#if defined(SQLITE_ENABLE_STAT4)

# define IsStat4 1

# define IsStat3 0

#elif defined(SQLITE_ENABLE_STAT3)

# define IsStat4 0

# define IsStat3 1

#else

# define IsStat4 0

# define IsStat3 0

# undef SQLITE_STAT4_SAMPLES

# define SQLITE_STAT4_SAMPLES 1

#endif

#define IsStat34 (IsStat3+IsStat4) /* 1 for STAT3 or STAT4. 0 otherwise */

/*

** This routine generates code that opens the sqlite_statN tables.

** The sqlite_stat1 table is always relevant. sqlite_stat2 is now

** obsolete. sqlite_stat3 and sqlite_stat4 are only opened when

** appropriate compile-time options are provided.

**

** If the sqlite_statN tables do not previously exist, it is created.

**

** Argument zWhere may be a pointer to a buffer containing a table name,

** or it may be a NULL pointer. If it is not NULL, then all entries in

** the sqlite_statN tables associated with the named table are deleted.

** If zWhere==0, then code is generated to delete all stat table entries.

*/

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 for this table or index */

const char *zWhereType /* Either "tbl" or "idx" */

){

static const struct {

const char *zName;

const char *zCols;

} aTable[] = {

{ "sqlite_stat1", "tbl,idx,stat" },

#if defined(SQLITE_ENABLE_STAT4)

{ "sqlite_stat4", "tbl,idx,neq,nlt,ndlt,sample" },

{ "sqlite_stat3", 0 },

#elif defined(SQLITE_ENABLE_STAT3)

{ "sqlite_stat3", "tbl,idx,neq,nlt,ndlt,sample" },

{ "sqlite_stat4", 0 },

#else

{ "sqlite_stat3", 0 },

{ "sqlite_stat4", 0 },

#endif

};

int i;

sqlite3 *db = pParse->db;

Db *pDb;

Vdbe *v = sqlite3GetVdbe(pParse);

int aRoot[ArraySize(aTable)];

u8 aCreateTbl[ArraySize(aTable)];

if( v==0 ) return;

assert( sqlite3BtreeHoldsAllMutexes(db) );

assert( sqlite3VdbeDb(v)==db );

pDb = &db->aDb[iDb];

/* Create new statistic tables if they do not exist, or clear them

** if they do already exist.

*/

for(i=0; i<ArraySize(aTable); i++){

const char *zTab = aTable[i].zName;

Table *pStat;

if( (pStat = sqlite3FindTable(db, zTab, pDb->zDbSName))==0 ){

if( aTable[i].zCols ){

/* The sqlite_statN 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->zDbSName, zTab, aTable[i].zCols

);

aRoot[i] = pParse->regRoot;

aCreateTbl[i] = OPFLAG_P2ISREG;

}

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

aCreateTbl[i] = 0;

sqlite3TableLock(pParse, iDb, aRoot[i], 1, zTab);

if( zWhere ){

sqlite3NestedParse(pParse,

"DELETE FROM %Q.%s WHERE %s=%Q",

pDb->zDbSName, zTab, zWhereType, zWhere

);

#ifdef SQLITE_ENABLE_PREUPDATE_HOOK

}else if( db->xPreUpdateCallback ){

sqlite3NestedParse(pParse, "DELETE FROM %Q.%s", pDb->zDbSName, zTab);

#endif

}else{

/* The sqlite_stat[134] table already exists. Delete all rows. */

sqlite3VdbeAddOp2(v, OP_Clear, aRoot[i], iDb);

}

}

}

/* Open the sqlite_stat[134] tables for writing. */

for(i=0; aTable[i].zCols; i++){

assert( i<ArraySize(aTable) );

sqlite3VdbeAddOp4Int(v, OP_OpenWrite, iStatCur+i, aRoot[i], iDb, 3);

sqlite3VdbeChangeP5(v, aCreateTbl[i]);

VdbeComment((v, aTable[i].zName));

}

}

/*

** Recommended number of samples for sqlite_stat4

*/

#ifndef SQLITE_STAT4_SAMPLES

# define SQLITE_STAT4_SAMPLES 24

#endif

/*

** Three SQL functions - stat_init(), stat_push(), and stat_get() -

** share an instance of the following structure to hold their state

** information.

*/

typedef struct Stat4Accum Stat4Accum;

typedef struct Stat4Sample Stat4Sample;

struct Stat4Sample {

tRowcnt *anEq; /* sqlite_stat4.nEq */

tRowcnt *anDLt; /* sqlite_stat4.nDLt */

#ifdef SQLITE_ENABLE_STAT3_OR_STAT4

tRowcnt *anLt; /* sqlite_stat4.nLt */

union {

i64 iRowid; /* Rowid in main table of the key */

u8 *aRowid; /* Key for WITHOUT ROWID tables */

} u;

u32 nRowid; /* Sizeof aRowid[] */

u8 isPSample; /* True if a periodic sample */

int iCol; /* If !isPSample, the reason for inclusion */

u32 iHash; /* Tiebreaker hash */

#endif

};

struct Stat4Accum {

tRowcnt nRow; /* Number of rows in the entire table */

tRowcnt nPSample; /* How often to do a periodic sample */

int nCol; /* Number of columns in index + pk/rowid */

int nKeyCol; /* Number of index columns w/o the pk/rowid */

int mxSample; /* Maximum number of samples to accumulate */

Stat4Sample current; /* Current row as a Stat4Sample */

u32 iPrn; /* Pseudo-random number used for sampling */

Stat4Sample *aBest; /* Array of nCol best samples */

int iMin; /* Index in a[] of entry with minimum score */

int nSample; /* Current number of samples */

int nMaxEqZero; /* Max leading 0 in anEq[] for any a[] entry */

int iGet; /* Index of current sample accessed by stat_get() */

Stat4Sample *a; /* Array of mxSample Stat4Sample objects */

sqlite3 *db; /* Database connection, for malloc() */

};

/* Reclaim memory used by a Stat4Sample

*/

#ifdef SQLITE_ENABLE_STAT3_OR_STAT4

static void sampleClear(sqlite3 *db, Stat4Sample *p){

assert( db!=0 );

if( p->nRowid ){

sqlite3DbFree(db, p->u.aRowid);

p->nRowid = 0;

}

}

#endif

/* Initialize the BLOB value of a ROWID

*/

#ifdef SQLITE_ENABLE_STAT3_OR_STAT4

static void sampleSetRowid(sqlite3 *db, Stat4Sample *p, int n, const u8 *pData){

assert( db!=0 );

if( p->nRowid ) sqlite3DbFree(db, p->u.aRowid);

p->u.aRowid = sqlite3DbMallocRawNN(db, n);

if( p->u.aRowid ){

p->nRowid = n;

memcpy(p->u.aRowid, pData, n);

}else{

p->nRowid = 0;

}

}

#endif

/* Initialize the INTEGER value of a ROWID.

*/

#ifdef SQLITE_ENABLE_STAT3_OR_STAT4

static void sampleSetRowidInt64(sqlite3 *db, Stat4Sample *p, i64 iRowid){

assert( db!=0 );

if( p->nRowid ) sqlite3DbFree(db, p->u.aRowid);

p->nRowid = 0;

p->u.iRowid = iRowid;

}

#endif

/*

** Copy the contents of object (*pFrom) into (*pTo).

*/

#ifdef SQLITE_ENABLE_STAT3_OR_STAT4

static void sampleCopy(Stat4Accum *p, Stat4Sample *pTo, Stat4Sample *pFrom){

pTo->isPSample = pFrom->isPSample;

pTo->iCol = pFrom->iCol;

pTo->iHash = pFrom->iHash;

memcpy(pTo->anEq, pFrom->anEq, sizeof(tRowcnt)*p->nCol);

memcpy(pTo->anLt, pFrom->anLt, sizeof(tRowcnt)*p->nCol);

memcpy(pTo->anDLt, pFrom->anDLt, sizeof(tRowcnt)*p->nCol);

if( pFrom->nRowid ){

sampleSetRowid(p->db, pTo, pFrom->nRowid, pFrom->u.aRowid);

}else{

sampleSetRowidInt64(p->db, pTo, pFrom->u.iRowid);

}

}

#endif

/*

** Reclaim all memory of a Stat4Accum structure.

*/

static void stat4Destructor(void *pOld){

Stat4Accum *p = (Stat4Accum*)pOld;

#ifdef SQLITE_ENABLE_STAT3_OR_STAT4

int i;

for(i=0; i<p->nCol; i++) sampleClear(p->db, p->aBest+i);

for(i=0; i<p->mxSample; i++) sampleClear(p->db, p->a+i);

sampleClear(p->db, &p->current);

#endif

sqlite3DbFree(p->db, p);

}

/*

** Implementation of the stat_init(N,K,C) SQL function. The three parameters

** are:

** N: The number of columns in the index including the rowid/pk (note 1)

** K: The number of columns in the index excluding the rowid/pk.

** C: The number of rows in the index (note 2)

**

** Note 1: In the special case of the covering index that implements a

** WITHOUT ROWID table, N is the number of PRIMARY KEY columns, not the

** total number of columns in the table.

**

** Note 2: C is only used for STAT3 and STAT4.

**

** For indexes on ordinary rowid tables, N==K+1. But for indexes on

** WITHOUT ROWID tables, N=K+P where P is the number of columns in the

** PRIMARY KEY of the table. The covering index that implements the

** original WITHOUT ROWID table as N==K as a special case.

**

** This routine allocates the Stat4Accum object in heap memory. The return

** value is a pointer to the Stat4Accum object. The datatype of the

** return value is BLOB, but it is really just a pointer to the Stat4Accum

** object.

*/

static void statInit(

sqlite3_context *context,

int argc,

sqlite3_value **argv

){

Stat4Accum *p;

int nCol; /* Number of columns in index being sampled */

int nKeyCol; /* Number of key columns */

int nColUp; /* nCol rounded up for alignment */

int n; /* Bytes of space to allocate */

sqlite3 *db; /* Database connection */

#ifdef SQLITE_ENABLE_STAT3_OR_STAT4

int mxSample = SQLITE_STAT4_SAMPLES;

#endif

/* Decode the three function arguments */

UNUSED_PARAMETER(argc);

nCol = sqlite3_value_int(argv[0]);

assert( nCol>0 );

nColUp = sizeof(tRowcnt)<8 ? (nCol+1)&~1 : nCol;

nKeyCol = sqlite3_value_int(argv[1]);

assert( nKeyCol<=nCol );

assert( nKeyCol>0 );

/* Allocate the space required for the Stat4Accum object */

n = sizeof(*p)

+ sizeof(tRowcnt)*nColUp /* Stat4Accum.anEq */

+ sizeof(tRowcnt)*nColUp /* Stat4Accum.anDLt */

#ifdef SQLITE_ENABLE_STAT3_OR_STAT4

+ sizeof(tRowcnt)*nColUp /* Stat4Accum.anLt */

+ sizeof(Stat4Sample)*(nCol+mxSample) /* Stat4Accum.aBest[], a[] */

+ sizeof(tRowcnt)*3*nColUp*(nCol+mxSample)

#endif

;

db = sqlite3_context_db_handle(context);

p = sqlite3DbMallocZero(db, n);

if( p==0 ){

sqlite3_result_error_nomem(context);

return;

}

p->db = db;

p->nRow = 0;

p->nCol = nCol;

p->nKeyCol = nKeyCol;

p->current.anDLt = (tRowcnt*)&p[1];

p->current.anEq = &p->current.anDLt[nColUp];

#ifdef SQLITE_ENABLE_STAT3_OR_STAT4

{

u8 *pSpace; /* Allocated space not yet assigned */

int i; /* Used to iterate through p->aSample[] */

p->iGet = -1;

p->mxSample = mxSample;

p->nPSample = (tRowcnt)(sqlite3_value_int64(argv[2])/(mxSample/3+1) + 1);

p->current.anLt = &p->current.anEq[nColUp];

p->iPrn = 0x689e962d*(u32)nCol ^ 0xd0944565*(u32)sqlite3_value_int(argv[2]);

/* Set up the Stat4Accum.a[] and aBest[] arrays */

p->a = (struct Stat4Sample*)&p->current.anLt[nColUp];

p->aBest = &p->a[mxSample];

pSpace = (u8*)(&p->a[mxSample+nCol]);

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

p->a[i].anEq = (tRowcnt *)pSpace; pSpace += (sizeof(tRowcnt) * nColUp);

p->a[i].anLt = (tRowcnt *)pSpace; pSpace += (sizeof(tRowcnt) * nColUp);

p->a[i].anDLt = (tRowcnt *)pSpace; pSpace += (sizeof(tRowcnt) * nColUp);

}

assert( (pSpace - (u8*)p)==n );

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

p->aBest[i].iCol = i;

}

}

#endif

/* Return a pointer to the allocated object to the caller. Note that

** only the pointer (the 2nd parameter) matters. The size of the object

** (given by the 3rd parameter) is never used and can be any positive

** value. */

sqlite3_result_blob(context, p, sizeof(*p), stat4Destructor);

}

static const FuncDef statInitFuncdef = {

2+IsStat34, /* nArg */

SQLITE_UTF8, /* funcFlags */

0, /* pUserData */

0, /* pNext */

statInit, /* xSFunc */

0, /* xFinalize */

0, 0, /* xValue, xInverse */

"stat_init", /* zName */

{0}

};

#ifdef SQLITE_ENABLE_STAT4

/*

** pNew and pOld are both candidate non-periodic samples selected for

** the same column (pNew->iCol==pOld->iCol). Ignoring this column and

** considering only any trailing columns and the sample hash value, this

** function returns true if sample pNew is to be preferred over pOld.

** In other words, if we assume that the cardinalities of the selected

** column for pNew and pOld are equal, is pNew to be preferred over pOld.

**

** This function assumes that for each argument sample, the contents of

** the anEq[] array from pSample->anEq[pSample->iCol+1] onwards are valid.

*/

static int sampleIsBetterPost(

Stat4Accum *pAccum,

Stat4Sample *pNew,

Stat4Sample *pOld

){

int nCol = pAccum->nCol;

int i;

assert( pNew->iCol==pOld->iCol );

for(i=pNew->iCol+1; i<nCol; i++){

if( pNew->anEq[i]>pOld->anEq[i] ) return 1;

if( pNew->anEq[i]<pOld->anEq[i] ) return 0;

}

if( pNew->iHash>pOld->iHash ) return 1;

return 0;

}

#endif

#ifdef SQLITE_ENABLE_STAT3_OR_STAT4

/*

** Return true if pNew is to be preferred over pOld.

**

** This function assumes that for each argument sample, the contents of

** the anEq[] array from pSample->anEq[pSample->iCol] onwards are valid.

*/

static int sampleIsBetter(

Stat4Accum *pAccum,

Stat4Sample *pNew,

Stat4Sample *pOld

){

tRowcnt nEqNew = pNew->anEq[pNew->iCol];

tRowcnt nEqOld = pOld->anEq[pOld->iCol];

assert( pOld->isPSample==0 && pNew->isPSample==0 );

assert( IsStat4 || (pNew->iCol==0 && pOld->iCol==0) );

if( (nEqNew>nEqOld) ) return 1;

#ifdef SQLITE_ENABLE_STAT4

if( nEqNew==nEqOld ){

if( pNew->iCol<pOld->iCol ) return 1;

return (pNew->iCol==pOld->iCol && sampleIsBetterPost(pAccum, pNew, pOld));

}

return 0;

#else

return (nEqNew==nEqOld && pNew->iHash>pOld->iHash);

#endif

}

/*

** Copy the contents of sample *pNew into the p->a[] array. If necessary,

** remove the least desirable sample from p->a[] to make room.

*/

static void sampleInsert(Stat4Accum *p, Stat4Sample *pNew, int nEqZero){

Stat4Sample *pSample = 0;

int i;

assert( IsStat4 || nEqZero==0 );

#ifdef SQLITE_ENABLE_STAT4

/* Stat4Accum.nMaxEqZero is set to the maximum number of leading 0

** values in the anEq[] array of any sample in Stat4Accum.a[]. In

** other words, if nMaxEqZero is n, then it is guaranteed that there

** are no samples with Stat4Sample.anEq[m]==0 for (m>=n). */

if( nEqZero>p->nMaxEqZero ){

p->nMaxEqZero = nEqZero;

}

if( pNew->isPSample==0 ){

Stat4Sample *pUpgrade = 0;

assert( pNew->anEq[pNew->iCol]>0 );

/* This sample is being added because the prefix that ends in column

** iCol occurs many times in the table. However, if we have already

** added a sample that shares this prefix, there is no need to add

** this one. Instead, upgrade the priority of the highest priority

** existing sample that shares this prefix. */

for(i=p->nSample-1; i>=0; i--){

Stat4Sample *pOld = &p->a[i];

if( pOld->anEq[pNew->iCol]==0 ){

if( pOld->isPSample ) return;

assert( pOld->iCol>pNew->iCol );

assert( sampleIsBetter(p, pNew, pOld) );

if( pUpgrade==0 || sampleIsBetter(p, pOld, pUpgrade) ){

pUpgrade = pOld;

}

}

}

if( pUpgrade ){

pUpgrade->iCol = pNew->iCol;

pUpgrade->anEq[pUpgrade->iCol] = pNew->anEq[pUpgrade->iCol];

goto find_new_min;

}

}

#endif

/* If necessary, remove sample iMin to make room for the new sample. */

if( p->nSample>=p->mxSample ){

Stat4Sample *pMin = &p->a[p->iMin];

tRowcnt *anEq = pMin->anEq;

tRowcnt *anLt = pMin->anLt;

tRowcnt *anDLt = pMin->anDLt;

sampleClear(p->db, pMin);

memmove(pMin, &pMin[1], sizeof(p->a[0])*(p->nSample-p->iMin-1));

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

pSample->nRowid = 0;

pSample->anEq = anEq;

pSample->anDLt = anDLt;

pSample->anLt = anLt;

p->nSample = p->mxSample-1;

}

/* The "rows less-than" for the rowid column must be greater than that

** for the last sample in the p->a[] array. Otherwise, the samples would

** be out of order. */

#ifdef SQLITE_ENABLE_STAT4

assert( p->nSample==0

|| pNew->anLt[p->nCol-1] > p->a[p->nSample-1].anLt[p->nCol-1] );

#endif

/* Insert the new sample */

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

sampleCopy(p, pSample, pNew);

p->nSample++;

/* Zero the first nEqZero entries in the anEq[] array. */

memset(pSample->anEq, 0, sizeof(tRowcnt)*nEqZero);

#ifdef SQLITE_ENABLE_STAT4

find_new_min:

#endif

if( p->nSample>=p->mxSample ){

int iMin = -1;

for(i=0; i<p->mxSample; i++){

if( p->a[i].isPSample ) continue;

if( iMin<0 || sampleIsBetter(p, &p->a[iMin], &p->a[i]) ){

iMin = i;

}

}

assert( iMin>=0 );

p->iMin = iMin;

}

}

#endif /* SQLITE_ENABLE_STAT3_OR_STAT4 */

/*

** Field iChng of the index being scanned has changed. So at this point

** p->current contains a sample that reflects the previous row of the

** index. The value of anEq[iChng] and subsequent anEq[] elements are

** correct at this point.

*/

static void samplePushPrevious(Stat4Accum *p, int iChng){

#ifdef SQLITE_ENABLE_STAT4

int i;

/* Check if any samples from the aBest[] array should be pushed

** into IndexSample.a[] at this point. */

for(i=(p->nCol-2); i>=iChng; i--){

Stat4Sample *pBest = &p->aBest[i];

pBest->anEq[i] = p->current.anEq[i];

if( p->nSample<p->mxSample || sampleIsBetter(p, pBest, &p->a[p->iMin]) ){

sampleInsert(p, pBest, i);

}

}

/* Check that no sample contains an anEq[] entry with an index of

** p->nMaxEqZero or greater set to zero. */

for(i=p->nSample-1; i>=0; i--){

int j;

for(j=p->nMaxEqZero; j<p->nCol; j++) assert( p->a[i].anEq[j]>0 );

}

/* Update the anEq[] fields of any samples already collected. */

if( iChng<p->nMaxEqZero ){

for(i=p->nSample-1; i>=0; i--){

int j;

for(j=iChng; j<p->nCol; j++){

if( p->a[i].anEq[j]==0 ) p->a[i].anEq[j] = p->current.anEq[j];

}

}

p->nMaxEqZero = iChng;

}

#endif

#if defined(SQLITE_ENABLE_STAT3) && !defined(SQLITE_ENABLE_STAT4)

if( iChng==0 ){

tRowcnt nLt = p->current.anLt[0];

tRowcnt nEq = p->current.anEq[0];

/* Check if this is to be a periodic sample. If so, add it. */

if( (nLt/p->nPSample)!=(nLt+nEq)/p->nPSample ){

p->current.isPSample = 1;

sampleInsert(p, &p->current, 0);

p->current.isPSample = 0;

}else

/* Or if it is a non-periodic sample. Add it in this case too. */

if( p->nSample<p->mxSample

|| sampleIsBetter(p, &p->current, &p->a[p->iMin])

){

sampleInsert(p, &p->current, 0);

}

}

#endif

#ifndef SQLITE_ENABLE_STAT3_OR_STAT4

UNUSED_PARAMETER( p );

UNUSED_PARAMETER( iChng );

#endif

}

/*

** Implementation of the stat_push SQL function: stat_push(P,C,R)

** Arguments:

**

** P Pointer to the Stat4Accum object created by stat_init()

** C Index of left-most column to differ from previous row

** R Rowid for the current row. Might be a key record for

** WITHOUT ROWID tables.

**

** This SQL function always returns NULL. It's purpose it to accumulate

** statistical data and/or samples in the Stat4Accum object about the

** index being analyzed. The stat_get() SQL function will later be used to

** extract relevant information for constructing the sqlite_statN tables.

**

** The R parameter is only used for STAT3 and STAT4

*/

static void statPush(

sqlite3_context *context,

int argc,

sqlite3_value **argv

){

int i;

/* The three function arguments */

Stat4Accum *p = (Stat4Accum*)sqlite3_value_blob(argv[0]);

int iChng = sqlite3_value_int(argv[1]);

UNUSED_PARAMETER( argc );

UNUSED_PARAMETER( context );

assert( p->nCol>0 );

assert( iChng<p->nCol );

if( p->nRow==0 ){

/* This is the first call to this function. Do initialization. */

for(i=0; i<p->nCol; i++) p->current.anEq[i] = 1;

}else{

/* Second and subsequent calls get processed here */

samplePushPrevious(p, iChng);

/* Update anDLt[], anLt[] and anEq[] to reflect the values that apply

** to the current row of the index. */

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

p->current.anEq[i]++;

}

for(i=iChng; i<p->nCol; i++){

p->current.anDLt[i]++;

#ifdef SQLITE_ENABLE_STAT3_OR_STAT4

p->current.anLt[i] += p->current.anEq[i];

#endif

p->current.anEq[i] = 1;

}

}

p->nRow++;

#ifdef SQLITE_ENABLE_STAT3_OR_STAT4

if( sqlite3_value_type(argv[2])==SQLITE_INTEGER ){

sampleSetRowidInt64(p->db, &p->current, sqlite3_value_int64(argv[2]));

}else{

sampleSetRowid(p->db, &p->current, sqlite3_value_bytes(argv[2]),

sqlite3_value_blob(argv[2]));

}

p->current.iHash = p->iPrn = p->iPrn*1103515245 + 12345;

#endif

#ifdef SQLITE_ENABLE_STAT4

{

tRowcnt nLt = p->current.anLt[p->nCol-1];

/* Check if this is to be a periodic sample. If so, add it. */

if( (nLt/p->nPSample)!=(nLt+1)/p->nPSample ){

p->current.isPSample = 1;

p->current.iCol = 0;

sampleInsert(p, &p->current, p->nCol-1);

p->current.isPSample = 0;

}

/* Update the aBest[] array. */

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

p->current.iCol = i;

if( i>=iChng || sampleIsBetterPost(p, &p->current, &p->aBest[i]) ){

sampleCopy(p, &p->aBest[i], &p->current);

}

}

}

#endif

}

static const FuncDef statPushFuncdef = {

2+IsStat34, /* nArg */

SQLITE_UTF8, /* funcFlags */

0, /* pUserData */

0, /* pNext */

statPush, /* xSFunc */

0, /* xFinalize */

0, 0, /* xValue, xInverse */

"stat_push", /* zName */

{0}

};

#define STAT_GET_STAT1 0 /* "stat" column of stat1 table */

#define STAT_GET_ROWID 1 /* "rowid" column of stat[34] entry */

#define STAT_GET_NEQ 2 /* "neq" column of stat[34] entry */

#define STAT_GET_NLT 3 /* "nlt" column of stat[34] entry */

#define STAT_GET_NDLT 4 /* "ndlt" column of stat[34] entry */

/*

** Implementation of the stat_get(P,J) SQL function. This routine is

** used to query statistical information that has been gathered into

** the Stat4Accum object by prior calls to stat_push(). The P parameter

** has type BLOB but it is really just a pointer to the Stat4Accum object.

** The content to returned is determined by the parameter J

** which is one of the STAT_GET_xxxx values defined above.

**

** The stat_get(P,J) function is not available to generic SQL. It is

** inserted as part of a manually constructed bytecode program. (See

** the callStatGet() routine below.) It is guaranteed that the P

** parameter will always be a poiner to a Stat4Accum object, never a

** NULL.

**

** If neither STAT3 nor STAT4 are enabled, then J is always

** STAT_GET_STAT1 and is hence omitted and this routine becomes

** a one-parameter function, stat_get(P), that always returns the

** stat1 table entry information.

*/

static void statGet(

sqlite3_context *context,

int argc,

sqlite3_value **argv

){

Stat4Accum *p = (Stat4Accum*)sqlite3_value_blob(argv[0]);

#ifdef SQLITE_ENABLE_STAT3_OR_STAT4

/* STAT3 and STAT4 have a parameter on this routine. */

int eCall = sqlite3_value_int(argv[1]);

assert( argc==2 );

assert( eCall==STAT_GET_STAT1 || eCall==STAT_GET_NEQ

|| eCall==STAT_GET_ROWID || eCall==STAT_GET_NLT

|| eCall==STAT_GET_NDLT

);

if( eCall==STAT_GET_STAT1 )

#else

assert( argc==1 );

#endif

{

/* Return the value to store in the "stat" column of the sqlite_stat1

** table for this index.

**

** The value is a string composed of a list of integers describing

** 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 indexed column. This additional integer is an estimate of

** the number of rows matched by a stabbing query on the index using

** a key with the corresponding number of fields. In other words,

** if the index is on columns (a,b) and the sqlite_stat1 value is

** "100 10 2", then SQLite estimates that:

**

** * the index contains 100 rows,

** * "WHERE a=?" matches 10 rows, and

** * "WHERE a=? AND b=?" matches 2 rows.

**

** If D is the count of distinct values and K is the total number of

** rows, then each estimate is computed as:

**

** I = (K+D-1)/D

*/

char *z;

int i;

char *zRet = sqlite3MallocZero( (p->nKeyCol+1)*25 );

if( zRet==0 ){

sqlite3_result_error_nomem(context);

return;

}

sqlite3_snprintf(24, zRet, "%llu", (u64)p->nRow);

z = zRet + sqlite3Strlen30(zRet);

for(i=0; i<p->nKeyCol; i++){

u64 nDistinct = p->current.anDLt[i] + 1;

u64 iVal = (p->nRow + nDistinct - 1) / nDistinct;

sqlite3_snprintf(24, z, " %llu", iVal);

z += sqlite3Strlen30(z);

assert( p->current.anEq[i] );

}

assert( z[0]=='\0' && z>zRet );

sqlite3_result_text(context, zRet, -1, sqlite3_free);

}

#ifdef SQLITE_ENABLE_STAT3_OR_STAT4

else if( eCall==STAT_GET_ROWID ){

if( p->iGet<0 ){

samplePushPrevious(p, 0);

p->iGet = 0;

}

if( p->iGet<p->nSample ){

Stat4Sample *pS = p->a + p->iGet;

if( pS->nRowid==0 ){

sqlite3_result_int64(context, pS->u.iRowid);

}else{

sqlite3_result_blob(context, pS->u.aRowid, pS->nRowid,

SQLITE_TRANSIENT);

}

}

}else{

tRowcnt *aCnt = 0;

assert( p->iGet<p->nSample );

switch( eCall ){

case STAT_GET_NEQ: aCnt = p->a[p->iGet].anEq; break;

case STAT_GET_NLT: aCnt = p->a[p->iGet].anLt; break;

default: {

aCnt = p->a[p->iGet].anDLt;

p->iGet++;

break;

}

}

if( IsStat3 ){

sqlite3_result_int64(context, (i64)aCnt[0]);

}else{

char *zRet = sqlite3MallocZero(p->nCol * 25);

if( zRet==0 ){

sqlite3_result_error_nomem(context);

}else{

int i;

char *z = zRet;

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

sqlite3_snprintf(24, z, "%llu ", (u64)aCnt[i]);

z += sqlite3Strlen30(z);

}

assert( z[0]=='\0' && z>zRet );

z[-1] = '\0';

sqlite3_result_text(context, zRet, -1, sqlite3_free);

}

}

}

#endif /* SQLITE_ENABLE_STAT3_OR_STAT4 */

#ifndef SQLITE_DEBUG

UNUSED_PARAMETER( argc );

#endif

}

static const FuncDef statGetFuncdef = {

1+IsStat34, /* nArg */

SQLITE_UTF8, /* funcFlags */

0, /* pUserData */

0, /* pNext */

statGet, /* xSFunc */

0, /* xFinalize */

0, 0, /* xValue, xInverse */

"stat_get", /* zName */

{0}

};

static void callStatGet(Vdbe *v, int regStat4, int iParam, int regOut){

assert( regOut!=regStat4 && regOut!=regStat4+1 );

#ifdef SQLITE_ENABLE_STAT3_OR_STAT4

sqlite3VdbeAddOp2(v, OP_Integer, iParam, regStat4+1);

#elif SQLITE_DEBUG

assert( iParam==STAT_GET_STAT1 );

#else

UNUSED_PARAMETER( iParam );

#endif

sqlite3VdbeAddOp4(v, OP_Function0, 0, regStat4, regOut,

(char*)&statGetFuncdef, P4_FUNCDEF);

sqlite3VdbeChangeP5(v, 1 + IsStat34);

}

/*

** Generate code to do an analysis of all indices associated with

** a single table.

*/

static void analyzeOneTable(

Parse *pParse, /* Parser context */

Table *pTab, /* Table whose indices are to be analyzed */

Index *pOnlyIdx, /* If not NULL, only analyze this one index */

int iStatCur, /* Index of VdbeCursor that writes the sqlite_stat1 table */

int iMem, /* Available memory locations begin here */

int iTab /* Next available cursor */

){

sqlite3 *db = pParse->db; /* Database handle */

Index *pIdx; /* An index to being analyzed */

int iIdxCur; /* Cursor open on index being analyzed */

int iTabCur; /* Table cursor */

Vdbe *v; /* The virtual machine being built up */

int i; /* Loop counter */

int jZeroRows = -1; /* Jump from here if number of rows is zero */

int iDb; /* Index of database containing pTab */

u8 needTableCnt = 1; /* True to count the table */

int regNewRowid = iMem++; /* Rowid for the inserted record */

int regStat4 = iMem++; /* Register to hold Stat4Accum object */

int regChng = iMem++; /* Index of changed index field */

#ifdef SQLITE_ENABLE_STAT3_OR_STAT4