aboutsummaryrefslogtreecommitdiff
path: root/src
diff options
context:
space:
mode:
Diffstat (limited to 'src')
-rw-r--r--src/analyze.c503
-rw-r--r--src/build.c152
-rw-r--r--src/ctime.c3
-rw-r--r--src/sqlite.h.in2
-rw-r--r--src/sqliteInt.h31
-rw-r--r--src/test_config.c6
-rw-r--r--src/utf.c2
-rw-r--r--src/vdbemem.c6
-rw-r--r--src/where.c374
9 files changed, 637 insertions, 442 deletions
diff --git a/src/analyze.c b/src/analyze.c
index 17c1de83a..7ccddfb11 100644
--- a/src/analyze.c
+++ b/src/analyze.c
@@ -10,6 +10,95 @@
**
*************************************************************************
** 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, nLt, nEq, 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.7, inclusive, and unless SQLite is compiled
+** with SQLITE_ENABLE_STAT2. The sqlite_stat2 table is deprecated.
+** The sqlite_stat2 table is superceded by sqlite_stat3, which is only
+** created and used by SQLite versions after 2011-08-09 with
+** SQLITE_ENABLE_STAT3 defined. The fucntionality of sqlite_stat3
+** is a superset of sqlite_stat2.
+**
+** 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 and in the table. 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.7. 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 entires 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 is an enhancement to sqlite_stat2. A new name is
+** used to avoid compatibility problems.
+**
+** The format of the sqlite_stat3 table is similar to the format for
+** the sqlite_stat2 table, with the following changes: (1)
+** The sampleno column is removed. (2) Every sample has nEq and nLt
+** columns which hold the approximate number of keys in the table that
+** exactly match the sample, and which are less than the sample,
+** respectively. (3) The number of samples can very from one table
+** to the next; the sample count does not have to be exactly 10 as
+** it is with sqlite_stat2. (4) The samples do not have to be evenly spaced.
+**
+** The ANALYZE command will typically generate sqlite_stat3 tables
+** that contain between 10 and 40 samples which are distributed across
+** the key space, though not uniformly, and which include samples with
+** largest possible nEq values.
*/
#ifndef SQLITE_OMIT_ANALYZE
#include "sqliteInt.h"
@@ -42,8 +131,14 @@ static void openStatTable(
const char *zCols;
} aTable[] = {
{ "sqlite_stat1", "tbl,idx,stat" },
-#ifdef SQLITE_ENABLE_STAT2
- { "sqlite_stat2", "tbl,idx,sampleno,sample" },
+#ifdef SQLITE_ENABLE_STAT3
+ { "sqlite_stat3", "tbl,idx,neq,nlt,sample" },
+#endif
+ };
+ static const char *azToDrop[] = {
+ "sqlite_stat2",
+#ifndef SQLITE_ENABLE_STAT3
+ "sqlite_stat3",
#endif
};
@@ -59,6 +154,17 @@ static void openStatTable(
assert( sqlite3VdbeDb(v)==db );
pDb = &db->aDb[iDb];
+ /* Drop all statistics tables that this version of SQLite does not
+ ** understand.
+ */
+ for(i=0; i<ArraySize(azToDrop); i++){
+ Table *pTab = sqlite3FindTable(db, azToDrop[i], pDb->zName);
+ if( pTab ) sqlite3CodeDropTable(pParse, pTab, iDb, 0);
+ }
+
+ /* 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;
@@ -89,7 +195,7 @@ static void openStatTable(
}
}
- /* Open the sqlite_stat[12] tables for writing. */
+ /* Open the sqlite_stat[13] tables for writing. */
for(i=0; i<ArraySize(aTable); i++){
sqlite3VdbeAddOp3(v, OP_OpenWrite, iStatCur+i, aRoot[i], iDb);
sqlite3VdbeChangeP4(v, -1, (char *)3, P4_INT32);
@@ -98,6 +204,13 @@ static void openStatTable(
}
/*
+** Recommended number of samples for sqlite_stat3
+*/
+#ifndef SQLITE_STAT3_SAMPLES
+# define SQLITE_STAT3_SAMPLES 16
+#endif
+
+/*
** Generate code to do an analysis of all indices associated with
** a single table.
*/
@@ -119,20 +232,26 @@ static void analyzeOneTable(
int iDb; /* Index of database containing pTab */
int regTabname = iMem++; /* Register containing table name */
int regIdxname = iMem++; /* Register containing index name */
- int regSampleno = iMem++; /* Register containing next sample number */
- int regCol = iMem++; /* Content of a column analyzed table */
+ int regStat1 = iMem++; /* The stat column of sqlite_stat1 */
+#ifdef SQLITE_ENABLE_STAT3
+ int regNumEq = iMem-1; /* Number of instances. Same as regStat1 */
+ int regNumLt = iMem++; /* Number of keys less than regSample */
+ int regSample = iMem++; /* The next sample value */
+ int regNext = iMem++; /* Index of next sample to record */
+ int regSpacing = iMem++; /* Spacing between samples */
+ int regBigSize = iMem++; /* Always save entries with nEq >= this */
+ int regTemp1 = iMem++; /* Intermediate register */
+ int regCount = iMem++; /* Number of rows in the table or index */
+ int regGosub = iMem++; /* Register holding subroutine return addr */
+ int once = 1; /* One-time initialization */
+ int shortJump = 0; /* Instruction address */
+ int addrStoreStat3 = 0; /* Address of subroutine to wrote to stat3 */
+#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 regRowid = iMem++; /* Rowid for the inserted record */
-#ifdef SQLITE_ENABLE_STAT2
- int addr = 0; /* Instruction address */
- int regTemp2 = iMem++; /* Temporary use register */
- int regSamplerecno = iMem++; /* Index of next sample to record */
- int regRecno = iMem++; /* Current sample index */
- int regLast = iMem++; /* Index of last sample to record */
- int regFirst = iMem++; /* Index of first sample to record */
-#endif
v = sqlite3GetVdbe(pParse);
if( v==0 || NEVER(pTab==0) ){
@@ -165,13 +284,18 @@ static void analyzeOneTable(
for(pIdx=pTab->pIndex; pIdx; pIdx=pIdx->pNext){
int nCol;
KeyInfo *pKey;
+ int addrIfNot; /* address of OP_IfNot */
+ int *aChngAddr; /* Array of jump instruction addresses */
if( pOnlyIdx && pOnlyIdx!=pIdx ) continue;
+ VdbeNoopComment((v, "Begin analysis of %s", pIdx->zName));
nCol = pIdx->nColumn;
pKey = sqlite3IndexKeyinfo(pParse, pIdx);
if( iMem+1+(nCol*2)>pParse->nMem ){
pParse->nMem = iMem+1+(nCol*2);
}
+ aChngAddr = sqlite3DbMallocRaw(db, sizeof(int)*pIdx->nColumn);
+ if( aChngAddr==0 ) continue;
/* Open a cursor to the index to be analyzed. */
assert( iDb==sqlite3SchemaToIndex(db, pIdx->pSchema) );
@@ -182,31 +306,43 @@ static void analyzeOneTable(
/* Populate the register containing the index name. */
sqlite3VdbeAddOp4(v, OP_String8, 0, regIdxname, 0, pIdx->zName, 0);
-#ifdef SQLITE_ENABLE_STAT2
+#ifdef SQLITE_ENABLE_STAT3
/* If this iteration of the loop is generating code to analyze the
** first index in the pTab->pIndex list, then register regLast has
** not been populated. In this case populate it now. */
- if( pTab->pIndex==pIdx ){
- sqlite3VdbeAddOp2(v, OP_Integer, SQLITE_INDEX_SAMPLES, regSamplerecno);
- sqlite3VdbeAddOp2(v, OP_Integer, SQLITE_INDEX_SAMPLES*2-1, regTemp);
- sqlite3VdbeAddOp2(v, OP_Integer, SQLITE_INDEX_SAMPLES*2, regTemp2);
-
- sqlite3VdbeAddOp2(v, OP_Count, iIdxCur, regLast);
- sqlite3VdbeAddOp2(v, OP_Null, 0, regFirst);
- addr = sqlite3VdbeAddOp3(v, OP_Lt, regSamplerecno, 0, regLast);
- sqlite3VdbeAddOp3(v, OP_Divide, regTemp2, regLast, regFirst);
- sqlite3VdbeAddOp3(v, OP_Multiply, regLast, regTemp, regLast);
- sqlite3VdbeAddOp2(v, OP_AddImm, regLast, SQLITE_INDEX_SAMPLES*2-2);
- sqlite3VdbeAddOp3(v, OP_Divide, regTemp2, regLast, regLast);
- sqlite3VdbeJumpHere(v, addr);
+ if( once ){
+ once = 0;
+ sqlite3VdbeAddOp2(v, OP_Count, iIdxCur, regCount);
+ sqlite3VdbeAddOp2(v, OP_Integer, SQLITE_STAT3_SAMPLES, regTemp1);
+ sqlite3VdbeAddOp3(v, OP_Divide, regTemp1, regCount, regSpacing);
+ sqlite3VdbeAddOp2(v, OP_Integer, SQLITE_STAT3_SAMPLES/2, regTemp1);
+ sqlite3VdbeAddOp3(v, OP_Divide, regTemp1, regCount, regBigSize);
+
+ /* Generate code for a subroutine that store the most recent sample
+ ** in the sqlite_stat3 table
+ */
+ shortJump = sqlite3VdbeAddOp0(v, OP_Goto);
+ sqlite3VdbeAddOp4(v, OP_MakeRecord, regTabname, 5, regRec, "bbbbb", 0);
+ VdbeComment((v, "begin stat3 write subroutine"));
+ sqlite3VdbeAddOp2(v, OP_NewRowid, iStatCur+1, regRowid);
+ sqlite3VdbeAddOp3(v, OP_Insert, iStatCur+1, regRec, regRowid);
+ sqlite3VdbeAddOp3(v, OP_Add, regNext, regSpacing, regNext);
+ sqlite3VdbeAddOp1(v, OP_Return, regGosub);
+ addrStoreStat3 =
+ sqlite3VdbeAddOp3(v, OP_Ge, regBigSize, shortJump+1, regNumEq);
+ sqlite3VdbeAddOp3(v, OP_Add, regNumEq, regNumLt, regTemp1);
+ sqlite3VdbeAddOp3(v, OP_Ge, regNext, shortJump+1, regTemp1);
+ sqlite3VdbeAddOp1(v, OP_Return, regGosub);
+ VdbeComment((v, "end stat3 write subroutine"));
+ sqlite3VdbeJumpHere(v, shortJump);
}
+ /* Reset state registers */
+ sqlite3VdbeAddOp2(v, OP_Copy, regSpacing, regNext);
+ sqlite3VdbeAddOp2(v, OP_Integer, 0, regNumEq);
+ sqlite3VdbeAddOp2(v, OP_Integer, 0, regNumLt);
- /* Zero the regSampleno and regRecno registers. */
- sqlite3VdbeAddOp2(v, OP_Integer, 0, regSampleno);
- sqlite3VdbeAddOp2(v, OP_Integer, 0, regRecno);
- sqlite3VdbeAddOp2(v, OP_Copy, regFirst, regSamplerecno);
-#endif
+#endif /* SQLITE_ENABLE_STAT3 */
/* The block of memory cells initialized here is used as follows.
**
@@ -236,75 +372,54 @@ static void analyzeOneTable(
endOfLoop = sqlite3VdbeMakeLabel(v);
sqlite3VdbeAddOp2(v, OP_Rewind, iIdxCur, endOfLoop);
topOfLoop = sqlite3VdbeCurrentAddr(v);
- sqlite3VdbeAddOp2(v, OP_AddImm, iMem, 1);
+ sqlite3VdbeAddOp2(v, OP_AddImm, iMem, 1); /* Increment row counter */
for(i=0; i<nCol; i++){
CollSeq *pColl;
sqlite3VdbeAddOp3(v, OP_Column, iIdxCur, i, regCol);
if( i==0 ){
-#ifdef SQLITE_ENABLE_STAT2
- /* Check if the record that cursor iIdxCur points to contains a
- ** value that should be stored in the sqlite_stat2 table. If so,
- ** store it. */
- int ne = sqlite3VdbeAddOp3(v, OP_Ne, regRecno, 0, regSamplerecno);
- assert( regTabname+1==regIdxname
- && regTabname+2==regSampleno
- && regTabname+3==regCol
- );
- sqlite3VdbeChangeP5(v, SQLITE_JUMPIFNULL);
- sqlite3VdbeAddOp4(v, OP_MakeRecord, regTabname, 4, regRec, "aaab", 0);
- sqlite3VdbeAddOp2(v, OP_NewRowid, iStatCur+1, regRowid);
- sqlite3VdbeAddOp3(v, OP_Insert, iStatCur+1, regRec, regRowid);
-
- /* Calculate new values for regSamplerecno and regSampleno.
- **
- ** sampleno = sampleno + 1
- ** samplerecno = samplerecno+(remaining records)/(remaining samples)
- */
- sqlite3VdbeAddOp2(v, OP_AddImm, regSampleno, 1);
- sqlite3VdbeAddOp3(v, OP_Subtract, regRecno, regLast, regTemp);
- sqlite3VdbeAddOp2(v, OP_AddImm, regTemp, -1);
- sqlite3VdbeAddOp2(v, OP_Integer, SQLITE_INDEX_SAMPLES, regTemp2);
- sqlite3VdbeAddOp3(v, OP_Subtract, regSampleno, regTemp2, regTemp2);
- sqlite3VdbeAddOp3(v, OP_Divide, regTemp2, regTemp, regTemp);
- sqlite3VdbeAddOp3(v, OP_Add, regSamplerecno, regTemp, regSamplerecno);
-
- sqlite3VdbeJumpHere(v, ne);
- sqlite3VdbeAddOp2(v, OP_AddImm, regRecno, 1);
-#endif
-
/* Always record the very first row */
- sqlite3VdbeAddOp1(v, OP_IfNot, iMem+1);
+ addrIfNot = sqlite3VdbeAddOp1(v, OP_IfNot, iMem+1);
}
assert( pIdx->azColl!=0 );
assert( pIdx->azColl[i]!=0 );
pColl = sqlite3LocateCollSeq(pParse, pIdx->azColl[i]);
- sqlite3VdbeAddOp4(v, OP_Ne, regCol, 0, iMem+nCol+i+1,
- (char*)pColl, P4_COLLSEQ);
+ aChngAddr[i] = sqlite3VdbeAddOp4(v, OP_Ne, regCol, 0, iMem+nCol+i+1,
+ (char*)pColl, P4_COLLSEQ);
sqlite3VdbeChangeP5(v, SQLITE_NULLEQ);
- }
- if( db->mallocFailed ){
- /* If a malloc failure has occurred, then the result of the expression
- ** passed as the second argument to the call to sqlite3VdbeJumpHere()
- ** below may be negative. Which causes an assert() to fail (or an
- ** out-of-bounds write if SQLITE_DEBUG is not defined). */
- return;
+ VdbeComment((v, "jump if column %d changed", i));
+#ifdef SQLITE_ENABLE_STAT3
+ if( i==0 && addrStoreStat3 ){
+ sqlite3VdbeAddOp2(v, OP_AddImm, regNumEq, 1);
+ VdbeComment((v, "incr repeat count"));
+ }
+#endif
}
sqlite3VdbeAddOp2(v, OP_Goto, 0, endOfLoop);
for(i=0; i<nCol; i++){
- int addr2 = sqlite3VdbeCurrentAddr(v) - (nCol*2);
+ sqlite3VdbeJumpHere(v, aChngAddr[i]); /* Set jump dest for the OP_Ne */
if( i==0 ){
- sqlite3VdbeJumpHere(v, addr2-1); /* Set jump dest for the OP_IfNot */
+ sqlite3VdbeJumpHere(v, addrIfNot); /* Jump dest for OP_IfNot */
+#ifdef SQLITE_ENABLE_STAT3
+ sqlite3VdbeAddOp2(v, OP_Gosub, regGosub, addrStoreStat3);
+ sqlite3VdbeAddOp2(v, OP_Copy, regCol, regSample);
+ sqlite3VdbeAddOp3(v, OP_Add, regNumEq, regNumLt, regNumLt);
+ sqlite3VdbeAddOp2(v, OP_Integer, 1, regNumEq);
+#endif
}
- sqlite3VdbeJumpHere(v, addr2); /* Set jump dest for the OP_Ne */
sqlite3VdbeAddOp2(v, OP_AddImm, iMem+i+1, 1);
sqlite3VdbeAddOp3(v, OP_Column, iIdxCur, i, iMem+nCol+i+1);
}
+ sqlite3DbFree(db, aChngAddr);
- /* End of the analysis loop. */
+ /* Always jump here after updating the iMem+1...iMem+1+nCol counters */
sqlite3VdbeResolveLabel(v, endOfLoop);
+
sqlite3VdbeAddOp2(v, OP_Next, iIdxCur, topOfLoop);
sqlite3VdbeAddOp1(v, OP_Close, iIdxCur);
+#ifdef SQLITE_ENABLE_STAT3
+ sqlite3VdbeAddOp2(v, OP_Gosub, regGosub, addrStoreStat3);
+#endif
/* Store the results in sqlite_stat1.
**
@@ -324,18 +439,18 @@ static void analyzeOneTable(
** If K>0 then it is always the case the D>0 so division by zero
** is never possible.
*/
- sqlite3VdbeAddOp2(v, OP_SCopy, iMem, regSampleno);
+ sqlite3VdbeAddOp2(v, OP_SCopy, iMem, regStat1);
if( jZeroRows<0 ){
jZeroRows = sqlite3VdbeAddOp1(v, OP_IfNot, iMem);
}
for(i=0; i<nCol; i++){
sqlite3VdbeAddOp4(v, OP_String8, 0, regTemp, 0, " ", 0);
- sqlite3VdbeAddOp3(v, OP_Concat, regTemp, regSampleno, regSampleno);
+ sqlite3VdbeAddOp3(v, OP_Concat, regTemp, regStat1, regStat1);
sqlite3VdbeAddOp3(v, OP_Add, iMem, iMem+i+1, regTemp);
sqlite3VdbeAddOp2(v, OP_AddImm, regTemp, -1);
sqlite3VdbeAddOp3(v, OP_Divide, iMem+i+1, regTemp, regTemp);
sqlite3VdbeAddOp1(v, OP_ToInt, regTemp);
- sqlite3VdbeAddOp3(v, OP_Concat, regTemp, regSampleno, regSampleno);
+ sqlite3VdbeAddOp3(v, OP_Concat, regTemp, regStat1, regStat1);
}
sqlite3VdbeAddOp4(v, OP_MakeRecord, regTabname, 3, regRec, "aaa", 0);
sqlite3VdbeAddOp2(v, OP_NewRowid, iStatCur, regRowid);
@@ -349,9 +464,9 @@ static void analyzeOneTable(
if( pTab->pIndex==0 ){
sqlite3VdbeAddOp3(v, OP_OpenRead, iIdxCur, pTab->tnum, iDb);
VdbeComment((v, "%s", pTab->zName));
- sqlite3VdbeAddOp2(v, OP_Count, iIdxCur, regSampleno);
+ sqlite3VdbeAddOp2(v, OP_Count, iIdxCur, regStat1);
sqlite3VdbeAddOp1(v, OP_Close, iIdxCur);
- jZeroRows = sqlite3VdbeAddOp1(v, OP_IfNot, regSampleno);
+ jZeroRows = sqlite3VdbeAddOp1(v, OP_IfNot, regStat1);
}else{
sqlite3VdbeJumpHere(v, jZeroRows);
jZeroRows = sqlite3VdbeAddOp0(v, OP_Goto);
@@ -365,6 +480,7 @@ static void analyzeOneTable(
sqlite3VdbeJumpHere(v, jZeroRows);
}
+
/*
** Generate code that will cause the most recent index analysis to
** be loaded into internal hash tables where is can be used.
@@ -518,7 +634,7 @@ static int analysisLoader(void *pData, int argc, char **argv, char **NotUsed){
Index *pIndex;
Table *pTable;
int i, c, n;
- unsigned int v;
+ tRowcnt v;
const char *z;
assert( argc==3 );
@@ -561,36 +677,157 @@ static int analysisLoader(void *pData, int argc, char **argv, char **NotUsed){
** and its contents.
*/
void sqlite3DeleteIndexSamples(sqlite3 *db, Index *pIdx){
-#ifdef SQLITE_ENABLE_STAT2
+#ifdef SQLITE_ENABLE_STAT3
if( pIdx->aSample ){
int j;
- for(j=0; j<SQLITE_INDEX_SAMPLES; j++){
+ for(j=0; j<pIdx->nSample; j++){
IndexSample *p = &pIdx->aSample[j];
if( p->eType==SQLITE_TEXT || p->eType==SQLITE_BLOB ){
- sqlite3DbFree(db, p->u.z);
+ sqlite3_free(p->u.z);
}
}
- sqlite3DbFree(db, pIdx->aSample);
+ sqlite3_free(pIdx->aSample);
}
+ pIdx->nSample = 0;
+ pIdx->aSample = 0;
#else
UNUSED_PARAMETER(db);
UNUSED_PARAMETER(pIdx);
#endif
}
+#ifdef SQLITE_ENABLE_STAT3
/*
-** Load the content of the sqlite_stat1 and sqlite_stat2 tables. The
+** Load content from the sqlite_stat3 table into the Index.aSample[]
+** arrays of all indices.
+*/
+static int loadStat3(sqlite3 *db, const char *zDb){
+ int rc; /* Result codes from subroutines */
+ sqlite3_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; /* slot in pIdx->aSample[] for next sample */
+ int eType; /* Datatype of a sample */
+ IndexSample *pSample; /* A slot in pIdx->aSample[] */
+
+ if( !sqlite3FindTable(db, "sqlite_stat3", zDb) ){
+ return SQLITE_OK;
+ }
+
+ zSql = sqlite3MPrintf(db,
+ "SELECT idx,count(*) FROM %Q.sqlite_stat3"
+ " GROUP BY idx", zDb);
+ if( !zSql ){
+ return SQLITE_NOMEM;
+ }
+ rc = sqlite3_prepare(db, zSql, -1, &pStmt, 0);
+ sqlite3DbFree(db, zSql);
+ if( rc ) return rc;
+
+ while( sqlite3_step(pStmt)==SQLITE_ROW ){
+ char *zIndex; /* Index name */
+ Index *pIdx; /* Pointer to the index object */
+ int nSample; /* Number of samples */
+
+ zIndex = (char *)sqlite3_column_text(pStmt, 0);
+ if( zIndex==0 ) continue;
+ nSample = sqlite3_column_int(pStmt, 1);
+ if( nSample>255 ) continue;
+ pIdx = sqlite3FindIndex(db, zIndex, zDb);
+ if( pIdx==0 ) continue;
+ assert( pIdx->nSample==0 );
+ pIdx->nSample = (u8)nSample;
+ pIdx->aSample = sqlite3MallocZero( nSample*sizeof(IndexSample) );
+ if( pIdx->aSample==0 ){
+ db->mallocFailed = 1;
+ sqlite3_finalize(pStmt);
+ return SQLITE_NOMEM;
+ }
+ }
+ sqlite3_finalize(pStmt);
+
+ zSql = sqlite3MPrintf(db,
+ "SELECT idx,nlt,neq,sample FROM %Q.sqlite_stat3"
+ " ORDER BY idx, nlt", zDb);
+ if( !zSql ){
+ return SQLITE_NOMEM;
+ }
+ rc = sqlite3_prepare(db, zSql, -1, &pStmt, 0);
+ sqlite3DbFree(db, zSql);
+ if( rc ) return rc;
+
+ while( sqlite3_step(pStmt)==SQLITE_ROW ){
+ char *zIndex; /* Index name */
+ Index *pIdx; /* Pointer to the index object */
+
+ zIndex = (char *)sqlite3_column_text(pStmt, 0);
+ if( zIndex==0 ) continue;
+ pIdx = sqlite3FindIndex(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->nLt = (tRowcnt)sqlite3_column_int64(pStmt, 1);
+ pSample->nEq = (tRowcnt)sqlite3_column_int64(pStmt, 2);
+ eType = sqlite3_column_type(pStmt, 3);
+ pSample->eType = (u8)eType;
+ switch( eType ){
+ case SQLITE_INTEGER: {
+ pSample->u.i = sqlite3_column_int64(pStmt, 3);
+ break;
+ }
+ case SQLITE_FLOAT: {
+ pSample->u.r = sqlite3_column_double(pStmt, 3);
+ break;
+ }
+ case SQLITE_NULL: {
+ break;
+ }
+ default: assert( eType==SQLITE_TEXT || eType==SQLITE_BLOB ); {
+ const char *z = (const char *)(
+ (eType==SQLITE_BLOB) ?
+ sqlite3_column_blob(pStmt, 3):
+ sqlite3_column_text(pStmt, 3)
+ );
+ int n = sqlite3_column_bytes(pStmt, 2);
+ if( n>0xffff ) n = 0xffff;
+ pSample->nByte = (u16)n;
+ if( n < 1){
+ pSample->u.z = 0;
+ }else{
+ pSample->u.z = sqlite3Malloc(n);
+ if( pSample->u.z==0 ){
+ db->mallocFailed = 1;
+ sqlite3_finalize(pStmt);
+ return SQLITE_NOMEM;
+ }
+ memcpy(pSample->u.z, z, n);
+ }
+ }
+ }
+ }
+ return sqlite3_finalize(pStmt);
+}
+#endif /* SQLITE_ENABLE_STAT3 */
+
+/*
+** Load the content of the sqlite_stat1 and sqlite_stat3 tables. The
** contents of sqlite_stat1 are used to populate the Index.aiRowEst[]
-** arrays. The contents of sqlite_stat2 are used to populate the
+** arrays. The contents of sqlite_stat3 are used to populate the
** Index.aSample[] arrays.
**
** If the sqlite_stat1 table is not present in the database, SQLITE_ERROR
-** is returned. In this case, even if SQLITE_ENABLE_STAT2 was defined
-** during compilation and the sqlite_stat2 table is present, no data is
+** is returned. In this case, even if SQLITE_ENABLE_STAT3 was defined
+** during compilation and the sqlite_stat3 table is present, no data is
** read from it.
**
-** If SQLITE_ENABLE_STAT2 was defined during compilation and the
-** sqlite_stat2 table is not present in the database, SQLITE_ERROR is
+** If SQLITE_ENABLE_STAT3 was defined during compilation and the
+** sqlite_stat3 table is not present in the database, SQLITE_ERROR is
** returned. However, in this case, data is read from the sqlite_stat1
** table (if it is present) before returning.
**
@@ -612,8 +849,10 @@ int sqlite3AnalysisLoad(sqlite3 *db, int iDb){
for(i=sqliteHashFirst(&db->aDb[iDb].pSchema->idxHash);i;i=sqliteHashNext(i)){
Index *pIdx = sqliteHashData(i);
sqlite3DefaultRowEst(pIdx);
+#ifdef SQLITE_ENABLE_STAT3
sqlite3DeleteIndexSamples(db, pIdx);
pIdx->aSample = 0;
+#endif
}
/* Check to make sure the sqlite_stat1 table exists */
@@ -625,7 +864,7 @@ int sqlite3AnalysisLoad(sqlite3 *db, int iDb){
/* Load new statistics out of the sqlite_stat1 table */
zSql = sqlite3MPrintf(db,
- "SELECT tbl, idx, stat FROM %Q.sqlite_stat1", sInfo.zDatabase);
+ "SELECT tbl,idx,stat FROM %Q.sqlite_stat1", sInfo.zDatabase);
if( zSql==0 ){
rc = SQLITE_NOMEM;
}else{
@@ -634,78 +873,10 @@ int sqlite3AnalysisLoad(sqlite3 *db, int iDb){
}
- /* Load the statistics from the sqlite_stat2 table. */
-#ifdef SQLITE_ENABLE_STAT2
- if( rc==SQLITE_OK && !sqlite3FindTable(db, "sqlite_stat2", sInfo.zDatabase) ){
- rc = SQLITE_ERROR;
- }
+ /* Load the statistics from the sqlite_stat3 table. */
+#ifdef SQLITE_ENABLE_STAT3
if( rc==SQLITE_OK ){
- sqlite3_stmt *pStmt = 0;
-
- zSql = sqlite3MPrintf(db,
- "SELECT idx,sampleno,sample FROM %Q.sqlite_stat2", sInfo.zDatabase);
- if( !zSql ){
- rc = SQLITE_NOMEM;
- }else{
- rc = sqlite3_prepare(db, zSql, -1, &pStmt, 0);
- sqlite3DbFree(db, zSql);
- }
-
- if( rc==SQLITE_OK ){
- while( sqlite3_step(pStmt)==SQLITE_ROW ){
- char *zIndex; /* Index name */
- Index *pIdx; /* Pointer to the index object */
-
- zIndex = (char *)sqlite3_column_text(pStmt, 0);
- pIdx = zIndex ? sqlite3FindIndex(db, zIndex, sInfo.zDatabase) : 0;
- if( pIdx ){
- int iSample = sqlite3_column_int(pStmt, 1);
- if( iSample<SQLITE_INDEX_SAMPLES && iSample>=0 ){
- int eType = sqlite3_column_type(pStmt, 2);
-
- if( pIdx->aSample==0 ){
- static const int sz = sizeof(IndexSample)*SQLITE_INDEX_SAMPLES;
- pIdx->aSample = (IndexSample *)sqlite3DbMallocRaw(0, sz);
- if( pIdx->aSample==0 ){
- db->mallocFailed = 1;
- break;
- }
- memset(pIdx->aSample, 0, sz);
- }
-
- assert( pIdx->aSample );
- {
- IndexSample *pSample = &pIdx->aSample[iSample];
- pSample->eType = (u8)eType;
- if( eType==SQLITE_INTEGER || eType==SQLITE_FLOAT ){
- pSample->u.r = sqlite3_column_double(pStmt, 2);
- }else if( eType==SQLITE_TEXT || eType==SQLITE_BLOB ){
- const char *z = (const char *)(
- (eType==SQLITE_BLOB) ?
- sqlite3_column_blob(pStmt, 2):
- sqlite3_column_text(pStmt, 2)
- );
- int n = sqlite3_column_bytes(pStmt, 2);
- if( n>24 ){
- n = 24;
- }
- pSample->nByte = (u8)n;
- if( n < 1){
- pSample->u.z = 0;
- }else{
- pSample->u.z = sqlite3DbStrNDup(0, z, n);
- if( pSample->u.z==0 ){
- db->mallocFailed = 1;
- break;
- }
- }
- }
- }
- }
- }
- }
- rc = sqlite3_finalize(pStmt);
- }
+ rc = loadStat3(db, sInfo.zDatabase);
}
#endif
diff --git a/src/build.c b/src/build.c
index f609ed837..73c51c855 100644
--- a/src/build.c
+++ b/src/build.c
@@ -1990,7 +1990,11 @@ static void sqlite3ClearStatTables(
const char *zType, /* "idx" or "tbl" */
const char *zName /* Name of index or table */
){
- static const char *azStatTab[] = { "sqlite_stat1", "sqlite_stat2" };
+ static const char *azStatTab[] = {
+ "sqlite_stat1",
+ "sqlite_stat2",
+ "sqlite_stat3",
+ };
int i;
const char *zDbName = pParse->db->aDb[iDb].zName;
for(i=0; i<ArraySize(azStatTab); i++){
@@ -2004,6 +2008,78 @@ static void sqlite3ClearStatTables(
}
/*
+** Generate code to drop a table.
+*/
+void sqlite3CodeDropTable(Parse *pParse, Table *pTab, int iDb, int isView){
+ Vdbe *v;
+ sqlite3 *db = pParse->db;
+ Trigger *pTrigger;
+ Db *pDb = &db->aDb[iDb];
+
+ v = sqlite3GetVdbe(pParse);
+ assert( v!=0 );
+ sqlite3BeginWriteOperation(pParse, 1, iDb);
+
+#ifndef SQLITE_OMIT_VIRTUALTABLE
+ if( IsVirtual(pTab) ){
+ sqlite3VdbeAddOp0(v, OP_VBegin);
+ }
+#endif
+
+ /* Drop all triggers associated with the table being dropped. Code
+ ** is generated to remove entries from sqlite_master and/or
+ ** sqlite_temp_master if required.
+ */
+ pTrigger = sqlite3TriggerList(pParse, pTab);
+ while( pTrigger ){
+ assert( pTrigger->pSchema==pTab->pSchema ||
+ pTrigger->pSchema==db->aDb[1].pSchema );
+ sqlite3DropTriggerPtr(pParse, pTrigger);
+ pTrigger = pTrigger->pNext;
+ }
+
+#ifndef SQLITE_OMIT_AUTOINCREMENT
+ /* Remove any entries of the sqlite_sequence table associated with
+ ** the table being dropped. This is done before the table is dropped
+ ** at the btree level, in case the sqlite_sequence table needs to
+ ** move as a result of the drop (can happen in auto-vacuum mode).
+ */
+ if( pTab->tabFlags & TF_Autoincrement ){
+ sqlite3NestedParse(pParse,
+ "DELETE FROM %Q.sqlite_sequence WHERE name=%Q",
+ pDb->zName, pTab->zName
+ );
+ }
+#endif
+
+ /* Drop all SQLITE_MASTER table and index entries that refer to the
+ ** table. The program name loops through the master table and deletes
+ ** every row that refers to a table of the same name as the one being
+ ** dropped. Triggers are handled seperately because a trigger can be
+ ** created in the temp database that refers to a table in another
+ ** database.
+ */
+ sqlite3NestedParse(pParse,
+ "DELETE FROM %Q.%s WHERE tbl_name=%Q and type!='trigger'",
+ pDb->zName, SCHEMA_TABLE(iDb), pTab->zName);
+ sqlite3ClearStatTables(pParse, iDb, "tbl", pTab->zName);
+ if( !isView && !IsVirtual(pTab) ){
+ destroyTable(pParse, pTab);
+ }
+
+ /* Remove the table entry from SQLite's internal schema and modify
+ ** the schema cookie.
+ */
+ if( IsVirtual(pTab) ){
+ sqlite3VdbeAddOp4(v, OP_VDestroy, iDb, 0, 0, pTab->zName, 0);
+ }
+ sqlite3VdbeAddOp4(v, OP_DropTable, iDb, 0, 0, pTab->zName, 0);
+ sqlite3ChangeCookie(pParse, iDb);
+ sqliteViewResetAll(db, iDb);
+
+}
+
+/*
** This routine is called to do the work of a DROP TABLE statement.
** pName is the name of the table to be dropped.
*/
@@ -2071,7 +2147,7 @@ void sqlite3DropTable(Parse *pParse, SrcList *pName, int isView, int noErr){
}
}
#endif
- if( sqlite3StrNICmp(pTab->zName, "sqlite_", 7)==0 ){
+ if( !pParse->nested && sqlite3StrNICmp(pTab->zName, "sqlite_", 7)==0 ){
sqlite3ErrorMsg(pParse, "table %s may not be dropped", pTab->zName);
goto exit_drop_table;
}
@@ -2095,68 +2171,10 @@ void sqlite3DropTable(Parse *pParse, SrcList *pName, int isView, int noErr){
*/
v = sqlite3GetVdbe(pParse);
if( v ){
- Trigger *pTrigger;
- Db *pDb = &db->aDb[iDb];
sqlite3BeginWriteOperation(pParse, 1, iDb);
-
-#ifndef SQLITE_OMIT_VIRTUALTABLE
- if( IsVirtual(pTab) ){
- sqlite3VdbeAddOp0(v, OP_VBegin);
- }
-#endif
sqlite3FkDropTable(pParse, pName, pTab);
-
- /* Drop all triggers associated with the table being dropped. Code
- ** is generated to remove entries from sqlite_master and/or
- ** sqlite_temp_master if required.
- */
- pTrigger = sqlite3TriggerList(pParse, pTab);
- while( pTrigger ){
- assert( pTrigger->pSchema==pTab->pSchema ||
- pTrigger->pSchema==db->aDb[1].pSchema );
- sqlite3DropTriggerPtr(pParse, pTrigger);
- pTrigger = pTrigger->pNext;
- }
-
-#ifndef SQLITE_OMIT_AUTOINCREMENT
- /* Remove any entries of the sqlite_sequence table associated with
- ** the table being dropped. This is done before the table is dropped
- ** at the btree level, in case the sqlite_sequence table needs to
- ** move as a result of the drop (can happen in auto-vacuum mode).
- */
- if( pTab->tabFlags & TF_Autoincrement ){
- sqlite3NestedParse(pParse,
- "DELETE FROM %s.sqlite_sequence WHERE name=%Q",
- pDb->zName, pTab->zName
- );
- }
-#endif
-
- /* Drop all SQLITE_MASTER table and index entries that refer to the
- ** table. The program name loops through the master table and deletes
- ** every row that refers to a table of the same name as the one being
- ** dropped. Triggers are handled seperately because a trigger can be
- ** created in the temp database that refers to a table in another
- ** database.
- */
- sqlite3NestedParse(pParse,
- "DELETE FROM %Q.%s WHERE tbl_name=%Q and type!='trigger'",
- pDb->zName, SCHEMA_TABLE(iDb), pTab->zName);
- sqlite3ClearStatTables(pParse, iDb, "tbl", pTab->zName);
- if( !isView && !IsVirtual(pTab) ){
- destroyTable(pParse, pTab);
- }
-
- /* Remove the table entry from SQLite's internal schema and modify
- ** the schema cookie.
- */
- if( IsVirtual(pTab) ){
- sqlite3VdbeAddOp4(v, OP_VDestroy, iDb, 0, 0, pTab->zName, 0);
- }
- sqlite3VdbeAddOp4(v, OP_DropTable, iDb, 0, 0, pTab->zName, 0);
- sqlite3ChangeCookie(pParse, iDb);
+ sqlite3CodeDropTable(pParse, pTab, iDb, isView);
}
- sqliteViewResetAll(db, iDb);
exit_drop_table:
sqlite3SrcListDelete(db, pName);
@@ -2603,8 +2621,8 @@ Index *sqlite3CreateIndex(
nCol = pList->nExpr;
pIndex = sqlite3DbMallocZero(db,
sizeof(Index) + /* Index structure */
+ sizeof(tRowcnt)*(nCol+1) + /* Index.aiRowEst */
sizeof(int)*nCol + /* Index.aiColumn */
- sizeof(int)*(nCol+1) + /* Index.aiRowEst */
sizeof(char *)*nCol + /* Index.azColl */
sizeof(u8)*nCol + /* Index.aSortOrder */
nName + 1 + /* Index.zName */
@@ -2613,10 +2631,10 @@ Index *sqlite3CreateIndex(
if( db->mallocFailed ){
goto exit_create_index;
}
- pIndex->azColl = (char**)(&pIndex[1]);
+ pIndex->aiRowEst = (tRowcnt*)(&pIndex[1]);
+ pIndex->azColl = (char**)(&pIndex->aiRowEst[nCol+1]);
pIndex->aiColumn = (int *)(&pIndex->azColl[nCol]);
- pIndex->aiRowEst = (unsigned *)(&pIndex->aiColumn[nCol]);
- pIndex->aSortOrder = (u8 *)(&pIndex->aiRowEst[nCol+1]);
+ pIndex->aSortOrder = (u8 *)(&pIndex->aiColumn[nCol]);
pIndex->zName = (char *)(&pIndex->aSortOrder[nCol]);
zExtra = (char *)(&pIndex->zName[nName+1]);
memcpy(pIndex->zName, zName, nName+1);
@@ -2893,9 +2911,9 @@ exit_create_index:
** are based on typical values found in actual indices.
*/
void sqlite3DefaultRowEst(Index *pIdx){
- unsigned *a = pIdx->aiRowEst;
+ tRowcnt *a = pIdx->aiRowEst;
int i;
- unsigned n;
+ tRowcnt n;
assert( a!=0 );
a[0] = pIdx->pTable->nRowEst;
if( a[0]<10 ) a[0] = 10;
diff --git a/src/ctime.c b/src/ctime.c
index a128f61a6..ad028ed2a 100644
--- a/src/ctime.c
+++ b/src/ctime.c
@@ -117,6 +117,9 @@ static const char * const azCompileOpt[] = {
#ifdef SQLITE_ENABLE_STAT2
"ENABLE_STAT2",
#endif
+#ifdef SQLITE_ENABLE_STAT3
+ "ENABLE_STAT3",
+#endif
#ifdef SQLITE_ENABLE_UNLOCK_NOTIFY
"ENABLE_UNLOCK_NOTIFY",
#endif
diff --git a/src/sqlite.h.in b/src/sqlite.h.in
index eb5f7a02a..4471c5d36 100644
--- a/src/sqlite.h.in
+++ b/src/sqlite.h.in
@@ -2851,7 +2851,7 @@ int sqlite3_limit(sqlite3*, int id, int newVal);
** ^The specific value of WHERE-clause [parameter] might influence the
** choice of query plan if the parameter is the left-hand side of a [LIKE]
** or [GLOB] operator or if the parameter is compared to an indexed column
-** and the [SQLITE_ENABLE_STAT2] compile-time option is enabled.
+** and the [SQLITE_ENABLE_STAT3] compile-time option is enabled.
** the
** </li>
** </ol>
diff --git a/src/sqliteInt.h b/src/sqliteInt.h
index bcf6a591a..6bb14b60b 100644
--- a/src/sqliteInt.h
+++ b/src/sqliteInt.h
@@ -446,6 +446,18 @@ typedef INT8_TYPE i8; /* 1-byte signed integer */
#define SQLITE_MAX_U32 ((((u64)1)<<32)-1)
/*
+** The datatype used to store estimates of the number of rows in a
+** table or index. This is an unsigned integer type. For 99.9% of
+** the world, a 32-bit integer is sufficient. But a 64-bit integer
+** can be used at compile-time if desired.
+*/
+#ifdef SQLITE_64BIT_STATS
+ typedef u64 tRowcnt; /* 64-bit only if requested at compile-time */
+#else
+ typedef u32 tRowcnt; /* 32-bit is the default */
+#endif
+
+/*
** Macros to determine whether the machine is big or little endian,
** evaluated at runtime.
*/
@@ -1278,7 +1290,7 @@ struct Table {
Column *aCol; /* Information about each column */
Index *pIndex; /* List of SQL indexes on this table. */
int tnum; /* Root BTree node for this table (see note above) */
- unsigned nRowEst; /* Estimated rows in table - from sqlite_stat1 table */
+ tRowcnt nRowEst; /* Estimated rows in table - from sqlite_stat1 table */
Select *pSelect; /* NULL for tables. Points to definition if a view. */
u16 nRef; /* Number of pointers to this Table */
u8 tabFlags; /* Mask of TF_* values */
@@ -1477,18 +1489,21 @@ struct Index {
char *zName; /* Name of this index */
int nColumn; /* Number of columns in the table used by this index */
int *aiColumn; /* Which columns are used by this index. 1st is 0 */
- unsigned *aiRowEst; /* Result of ANALYZE: Est. rows selected by each column */
+ tRowcnt *aiRowEst; /* Result of ANALYZE: Est. rows selected by each column */
Table *pTable; /* The SQL table being indexed */
int tnum; /* Page containing root of this index in database file */
u8 onError; /* OE_Abort, OE_Ignore, OE_Replace, or OE_None */
u8 autoIndex; /* True if is automatically created (ex: by UNIQUE) */
u8 bUnordered; /* Use this index for == or IN queries only */
+ u8 nSample; /* Number of elements in aSample[] */
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 */
+#ifdef SQLITE_ENABLE_STAT3
+ IndexSample *aSample; /* Samples of the left-most key */
+#endif
};
/*
@@ -1498,10 +1513,13 @@ struct Index {
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 */
+ double r; /* Value if eType is SQLITE_FLOAT */
+ i64 i; /* Value if eType is SQLITE_INTEGER */
} u;
u8 eType; /* SQLITE_NULL, SQLITE_INTEGER ... etc. */
- u8 nByte; /* Size in byte of text or blob. */
+ u16 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 */
};
/*
@@ -2707,6 +2725,7 @@ void sqlite3CreateView(Parse*,Token*,Token*,Token*,Select*,int,int);
#endif
void sqlite3DropTable(Parse*, SrcList*, int, int);
+void sqlite3CodeDropTable(Parse*, Table*, int, int);
void sqlite3DeleteTable(sqlite3*, Table*);
#ifndef SQLITE_OMIT_AUTOINCREMENT
void sqlite3AutoincrementBegin(Parse *pParse);
@@ -2963,7 +2982,7 @@ void sqlite3ValueSetStr(sqlite3_value*, int, const void *,u8,
void sqlite3ValueFree(sqlite3_value*);
sqlite3_value *sqlite3ValueNew(sqlite3 *);
char *sqlite3Utf16to8(sqlite3 *, const void*, int, u8);
-#ifdef SQLITE_ENABLE_STAT2
+#ifdef SQLITE_ENABLE_STAT3
char *sqlite3Utf8to16(sqlite3 *, u8, char *, int, int *);
#endif
int sqlite3ValueFromExpr(sqlite3 *, Expr *, u8, u8, sqlite3_value **);
diff --git a/src/test_config.c b/src/test_config.c
index e8d6f88f6..9a3f3da73 100644
--- a/src/test_config.c
+++ b/src/test_config.c
@@ -418,6 +418,12 @@ Tcl_SetVar2(interp, "sqlite_options", "long_double",
Tcl_SetVar2(interp, "sqlite_options", "stat2", "0", TCL_GLOBAL_ONLY);
#endif
+#ifdef SQLITE_ENABLE_STAT3
+ Tcl_SetVar2(interp, "sqlite_options", "stat3", "1", TCL_GLOBAL_ONLY);
+#else
+ Tcl_SetVar2(interp, "sqlite_options", "stat3", "0", TCL_GLOBAL_ONLY);
+#endif
+
#if !defined(SQLITE_ENABLE_LOCKING_STYLE)
# if defined(__APPLE__)
# define SQLITE_ENABLE_LOCKING_STYLE 1
diff --git a/src/utf.c b/src/utf.c
index 17f3a09a4..e94815b5a 100644
--- a/src/utf.c
+++ b/src/utf.c
@@ -464,7 +464,7 @@ char *sqlite3Utf16to8(sqlite3 *db, const void *z, int nByte, u8 enc){
** If a malloc failure occurs, NULL is returned and the db.mallocFailed
** flag set.
*/
-#ifdef SQLITE_ENABLE_STAT2
+#ifdef SQLITE_ENABLE_STAT3
char *sqlite3Utf8to16(sqlite3 *db, u8 enc, char *z, int n, int *pnOut){
Mem m;
memset(&m, 0, sizeof(m));
diff --git a/src/vdbemem.c b/src/vdbemem.c
index 882c68633..9c964a258 100644
--- a/src/vdbemem.c
+++ b/src/vdbemem.c
@@ -1032,11 +1032,11 @@ int sqlite3ValueFromExpr(
}
op = pExpr->op;
- /* op can only be TK_REGISTER if we have compiled with SQLITE_ENABLE_STAT2.
+ /* op can only be TK_REGISTER if we have compiled with SQLITE_ENABLE_STAT3.
** The ifdef here is to enable us to achieve 100% branch test coverage even
- ** when SQLITE_ENABLE_STAT2 is omitted.
+ ** when SQLITE_ENABLE_STAT3 is omitted.
*/
-#ifdef SQLITE_ENABLE_STAT2
+#ifdef SQLITE_ENABLE_STAT3
if( op==TK_REGISTER ) op = pExpr->op2;
#else
if( NEVER(op==TK_REGISTER) ) op = pExpr->op2;
diff --git a/src/where.c b/src/where.c
index 21fb7f45f..3118a0a0e 100644
--- a/src/where.c
+++ b/src/where.c
@@ -118,7 +118,7 @@ struct WhereTerm {
#define TERM_ORINFO 0x10 /* Need to free the WhereTerm.u.pOrInfo object */
#define TERM_ANDINFO 0x20 /* Need to free the WhereTerm.u.pAndInfo obj */
#define TERM_OR_OK 0x40 /* Used during OR-clause processing */
-#ifdef SQLITE_ENABLE_STAT2
+#ifdef SQLITE_ENABLE_STAT3
# define TERM_VNULL 0x80 /* Manufactured x>NULL or x<=NULL term */
#else
# define TERM_VNULL 0x00 /* Disabled if not using stat2 */
@@ -1332,7 +1332,7 @@ static void exprAnalyze(
}
#endif /* SQLITE_OMIT_VIRTUALTABLE */
-#ifdef SQLITE_ENABLE_STAT2
+#ifdef SQLITE_ENABLE_STAT3
/* When sqlite_stat2 histogram data is available an operator of the
** form "x IS NOT NULL" can sometimes be evaluated more efficiently
** as "x>NULL" if x is not an INTEGER PRIMARY KEY. So construct a
@@ -1371,7 +1371,7 @@ static void exprAnalyze(
pNewTerm->prereqAll = pTerm->prereqAll;
}
}
-#endif /* SQLITE_ENABLE_STAT2 */
+#endif /* SQLITE_ENABLE_STAT */
/* Prevent ON clause terms of a LEFT JOIN from being used to drive
** an index for tables to the left of the join.
@@ -2420,67 +2420,70 @@ static void bestVirtualIndex(
}
#endif /* SQLITE_OMIT_VIRTUALTABLE */
+#ifdef SQLITE_ENABLE_STAT3
/*
-** 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. These samples divide the domain of values stored
-** the index into (SQLITE_INDEX_SAMPLES+1) regions.
-** Region 0 contains all values less than the first sample value. Region
-** 1 contains values between the first and second samples. Region 2 contains
-** values between samples 2 and 3. And so on. Region SQLITE_INDEX_SAMPLES
-** contains values larger than the last sample.
-**
-** If the index contains many duplicates of a single value, then it is
-** possible that two or more adjacent samples can hold the same value.
-** When that is the case, the smallest possible region code is returned
-** when roundUp is false and the largest possible region code is returned
-** when roundUp is true.
-**
-** If successful, this function determines which of the regions value
-** pVal lies in, sets *piRegion to the region index (a value between 0
-** and SQLITE_INDEX_SAMPLES+1, inclusive) and returns SQLITE_OK.
-** Or, if an OOM occurs while converting text values between encodings,
-** SQLITE_NOMEM is returned and *piRegion is undefined.
+** Estimate the location of a particular key among all keys in an
+** index. Store the results in aStat as follows:
+**
+** aStat[0] Est. number of rows less than pVal
+** aStat[1] Est. number of rows equal to pVal
+**
+** Return SQLITE_OK on success.
*/
-#ifdef SQLITE_ENABLE_STAT2
-static int whereRangeRegion(
+static int whereKeyStats(
Parse *pParse, /* Database connection */
Index *pIdx, /* Index to consider domain of */
sqlite3_value *pVal, /* Value to consider */
- int roundUp, /* Return largest valid region if true */
- int *piRegion /* OUT: Region of domain in which value lies */
+ 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;
+
assert( roundUp==0 || roundUp==1 );
- if( ALWAYS(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 ) break;
- if( roundUp ){
- if( aSample[i].u.r>r ) break;
- }else{
- if( aSample[i].u.r>=r ) break;
- }
+ if( pVal==0 ) return SQLITE_ERROR;
+ n = pIdx->aiRowEst[0];
+ aSample = pIdx->aSample;
+ i = 0;
+ eType = sqlite3_value_type(pVal);
+
+ if( eType==SQLITE_INTEGER ){
+ i64 v = sqlite3_value_int64(pVal);
+ for(i=0; i<pIdx->nSample; i++){
+ if( aSample[i].eType==SQLITE_NULL ) continue;
+ if( aSample[i].eType>=SQLITE_TEXT ) break;
+ if( aSample[i].u.i>=v ){
+ isEq = aSample[i].u.i==v;
+ break;
+ }
+ }
+ }else if( eType==SQLITE_FLOAT ){
+ double r = sqlite3_value_double(pVal);
+ for(i=0; i<pIdx->nSample; i++){
+ if( aSample[i].eType==SQLITE_NULL ) continue;
+ if( aSample[i].eType>=SQLITE_TEXT ) break;
+ if( aSample[i].u.r>=r ){
+ isEq = aSample[i].u.r==r;
+ break;
}
- }else if( eType==SQLITE_NULL ){
- i = 0;
- if( roundUp ){
- while( i<SQLITE_INDEX_SAMPLES && aSample[i].eType==SQLITE_NULL ) i++;
+ }
+ }else if( eType==SQLITE_NULL ){
+ i = 0;
+ if( pIdx->nSample>=1 && aSample[0].eType==SQLITE_NULL ) isEq = 1;
+ }else{
+ assert( eType==SQLITE_TEXT || eType==SQLITE_BLOB );
+ for(i=0; i<pIdx->nSample; i++){
+ if( aSample[i].eType==SQLITE_TEXT || aSample[i].eType==SQLITE_BLOB ){
+ break;
}
- }else{
+ }
+ if( i<pIdx->nSample ){
sqlite3 *db = pParse->db;
CollSeq *pColl;
const u8 *z;
int n;
-
- /* pVal comes from sqlite3ValueFromExpr() so the type cannot be NULL */
- assert( eType==SQLITE_TEXT || eType==SQLITE_BLOB );
-
if( eType==SQLITE_BLOB ){
z = (const u8 *)sqlite3_value_blob(pVal);
pColl = db->pDfltColl;
@@ -2499,12 +2502,12 @@ static int whereRangeRegion(
assert( z && pColl && pColl->xCmp );
}
n = sqlite3ValueBytes(pVal, pColl->enc);
-
- for(i=0; i<SQLITE_INDEX_SAMPLES; i++){
+
+ for(; i<pIdx->nSample; i++){
int c;
int eSampletype = aSample[i].eType;
- if( eSampletype==SQLITE_NULL || eSampletype<eType ) continue;
- if( (eSampletype!=eType) ) break;
+ if( eSampletype<eType ) continue;
+ if( eSampletype!=eType ) break;
#ifndef SQLITE_OMIT_UTF16
if( pColl->enc!=SQLITE_UTF8 ){
int nSample;
@@ -2522,16 +2525,51 @@ static int whereRangeRegion(
{
c = pColl->xCmp(pColl->pUser, aSample[i].nByte, aSample[i].u.z, n, z);
}
- if( c-roundUp>=0 ) break;
+ if( c>=0 ){
+ if( c==0 ) isEq = 1;
+ break;
+ }
}
}
+ }
- assert( i>=0 && i<=SQLITE_INDEX_SAMPLES );
- *piRegion = i;
+ /* 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.
+ */
+ if( isEq ){
+ assert( i<pIdx->nSample );
+ aStat[0] = aSample[i].nLt;
+ aStat[1] = aSample[i].nEq;
+ }else{
+ tRowcnt iLower, iUpper, iGap;
+ if( i==0 ){
+ iLower = 0;
+ iUpper = aSample[0].nLt;
+ }else if( i>=pIdx->nSample ){
+ iUpper = n;
+ iLower = aSample[i].nEq + aSample[i].nLt;
+ }else{
+ iLower = aSample[i-1].nEq + aSample[i-1].nLt;
+ iUpper = aSample[i].nLt;
+ }
+ aStat[1] = pIdx->aiRowEst[1];
+ if( iLower>=iUpper ){
+ iGap = 0;
+ }else{
+ iGap = iUpper - iLower;
+ if( iGap>=aStat[1]/2 ) iGap -= aStat[1]/2;
+ }
+ if( roundUp ){
+ iGap = (iGap*2)/3;
+ }else{
+ iGap = iGap/3;
+ }
+ aStat[0] = iLower + iGap;
}
return SQLITE_OK;
}
-#endif /* #ifdef SQLITE_ENABLE_STAT2 */
+#endif /* SQLITE_ENABLE_STAT3 */
/*
** If expression pExpr represents a literal value, set *pp to point to
@@ -2549,7 +2587,7 @@ static int whereRangeRegion(
**
** If an error occurs, return an error code. Otherwise, SQLITE_OK.
*/
-#ifdef SQLITE_ENABLE_STAT2
+#ifdef SQLITE_ENABLE_STAT3
static int valueFromExpr(
Parse *pParse,
Expr *pExpr,
@@ -2597,17 +2635,15 @@ static int valueFromExpr(
**
** then nEq should be passed 0.
**
-** The returned value is an integer between 1 and 100, inclusive. A return
-** value of 1 indicates that the proposed range scan is expected to visit
-** approximately 1/100th (1%) of the rows selected by the nEq equality
-** constraints (if any). A return value of 100 indicates that it is expected
-** that the range scan will visit every row (100%) selected by the equality
-** constraints.
-**
-** In the absence of sqlite_stat2 ANALYZE data, each range inequality
-** reduces the search space by 3/4ths. Hence a single constraint (x>?)
-** results in a return of 25 and a range constraint (x>? AND x<?) results
-** in a return of 6.
+** The returned value is an integer divisor to reduce the estimated
+** search space. A return value of 1 means that range constraints are
+** no help at all. A return value of 2 means range constraints are
+** expected to reduce the search space by half. And so forth...
+**
+** In the absence of sqlite_stat3 ANALYZE data, each range inequality
+** reduces the search space by a factor of 4. Hence a single constraint (x>?)
+** results in a return of 4 and a range constraint (x>? AND x<?) results
+** in a return of 16.
*/
static int whereRangeScanEst(
Parse *pParse, /* Parsing & code generating context */
@@ -2615,84 +2651,72 @@ static int whereRangeScanEst(
int nEq, /* index into p->aCol[] of the range-compared column */
WhereTerm *pLower, /* Lower bound on the range. ex: "x>123" Might be NULL */
WhereTerm *pUpper, /* Upper bound on the range. ex: "x<455" Might be NULL */
- int *piEst /* OUT: Return value */
+ tRowcnt *pRangeDiv /* OUT: Reduce search space by this divisor */
){
int rc = SQLITE_OK;
-#ifdef SQLITE_ENABLE_STAT2
+#ifdef SQLITE_ENABLE_STAT3
- if( nEq==0 && p->aSample ){
- sqlite3_value *pLowerVal = 0;
- sqlite3_value *pUpperVal = 0;
- int iEst;
- int iLower = 0;
- int iUpper = SQLITE_INDEX_SAMPLES;
- int roundUpUpper = 0;
- int roundUpLower = 0;
+ if( nEq==0 && p->nSample ){
+ sqlite3_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, &pLowerVal);
+ rc = valueFromExpr(pParse, pExpr, aff, &pRangeVal);
assert( pLower->eOperator==WO_GT || pLower->eOperator==WO_GE );
- roundUpLower = (pLower->eOperator==WO_GT) ?1:0;
+ if( rc==SQLITE_OK
+ && whereKeyStats(pParse, p, pRangeVal, 0, a)==SQLITE_OK
+ ){
+ iLower = a[0];
+ if( pLower->eOperator==WO_GT ) iLower += a[1];
+ }
+ sqlite3ValueFree(pRangeVal);
}
if( rc==SQLITE_OK && pUpper ){
Expr *pExpr = pUpper->pExpr->pRight;
- rc = valueFromExpr(pParse, pExpr, aff, &pUpperVal);
+ rc = valueFromExpr(pParse, pExpr, aff, &pRangeVal);
assert( pUpper->eOperator==WO_LT || pUpper->eOperator==WO_LE );
- roundUpUpper = (pUpper->eOperator==WO_LE) ?1:0;
- }
-
- if( rc!=SQLITE_OK || (pLowerVal==0 && pUpperVal==0) ){
- sqlite3ValueFree(pLowerVal);
- sqlite3ValueFree(pUpperVal);
- goto range_est_fallback;
- }else if( pLowerVal==0 ){
- rc = whereRangeRegion(pParse, p, pUpperVal, roundUpUpper, &iUpper);
- if( pLower ) iLower = iUpper/2;
- }else if( pUpperVal==0 ){
- rc = whereRangeRegion(pParse, p, pLowerVal, roundUpLower, &iLower);
- if( pUpper ) iUpper = (iLower + SQLITE_INDEX_SAMPLES + 1)/2;
- }else{
- rc = whereRangeRegion(pParse, p, pUpperVal, roundUpUpper, &iUpper);
- if( rc==SQLITE_OK ){
- rc = whereRangeRegion(pParse, p, pLowerVal, roundUpLower, &iLower);
+ if( rc==SQLITE_OK
+ && whereKeyStats(pParse, p, pRangeVal, 1, a)==SQLITE_OK
+ ){
+ iUpper = a[0];
+ if( pLower->eOperator==WO_LE ) iUpper += a[1];
}
+ sqlite3ValueFree(pRangeVal);
}
- WHERETRACE(("range scan regions: %d..%d\n", iLower, iUpper));
-
- iEst = iUpper - iLower;
- testcase( iEst==SQLITE_INDEX_SAMPLES );
- assert( iEst<=SQLITE_INDEX_SAMPLES );
- if( iEst<1 ){
- *piEst = 50/SQLITE_INDEX_SAMPLES;
- }else{
- *piEst = (iEst*100)/SQLITE_INDEX_SAMPLES;
+ if( rc==SQLITE_OK ){
+ if( iUpper<=iLower ){
+ *pRangeDiv = p->aiRowEst[0];
+ }else{
+ *pRangeDiv = p->aiRowEst[0]/(iUpper - iLower);
+ }
+ WHERETRACE(("range scan regions: %u..%u div=%u\n",
+ (u32)iLower, (u32)iUpper, (u32)*pRangeDiv));
+ return SQLITE_OK;
}
- sqlite3ValueFree(pLowerVal);
- sqlite3ValueFree(pUpperVal);
- return rc;
}
-range_est_fallback:
#else
UNUSED_PARAMETER(pParse);
UNUSED_PARAMETER(p);
UNUSED_PARAMETER(nEq);
#endif
assert( pLower || pUpper );
- *piEst = 100;
- if( pLower && (pLower->wtFlags & TERM_VNULL)==0 ) *piEst /= 4;
- if( pUpper ) *piEst /= 4;
+ *pRangeDiv = 1;
+ if( pLower && (pLower->wtFlags & TERM_VNULL)==0 ) *pRangeDiv *= 4;
+ if( pUpper ) *pRangeDiv *= 4;
return rc;
}
-#ifdef SQLITE_ENABLE_STAT2
+#ifdef SQLITE_ENABLE_STAT3
/*
** Estimate the number of rows that will be returned based on
** an equality constraint x=VALUE and where that VALUE occurs in
** the histogram data. This only works when x is the left-most
-** column of an index and sqlite_stat2 histogram data is available
+** column of an index and sqlite_stat3 histogram data is available
** for that index. When pExpr==NULL that means the constraint is
** "x IS NULL" instead of "x=VALUE".
**
@@ -2712,10 +2736,9 @@ static int whereEqualScanEst(
double *pnRow /* Write the revised row estimate here */
){
sqlite3_value *pRhs = 0; /* VALUE on right-hand side of pTerm */
- int iLower, iUpper; /* Range of histogram regions containing pRhs */
u8 aff; /* Column affinity */
int rc; /* Subfunction return code */
- double nRowEst; /* New estimate of the number of rows */
+ tRowcnt a[2]; /* Statistics */
assert( p->aSample!=0 );
aff = p->pTable->aCol[p->aiColumn[0]].affinity;
@@ -2726,26 +2749,18 @@ static int whereEqualScanEst(
pRhs = sqlite3ValueNew(pParse->db);
}
if( pRhs==0 ) return SQLITE_NOTFOUND;
- rc = whereRangeRegion(pParse, p, pRhs, 0, &iLower);
- if( rc ) goto whereEqualScanEst_cancel;
- rc = whereRangeRegion(pParse, p, pRhs, 1, &iUpper);
- if( rc ) goto whereEqualScanEst_cancel;
- WHERETRACE(("equality scan regions: %d..%d\n", iLower, iUpper));
- if( iLower>=iUpper ){
- nRowEst = p->aiRowEst[0]/(SQLITE_INDEX_SAMPLES*2);
- if( nRowEst<*pnRow ) *pnRow = nRowEst;
- }else{
- nRowEst = (iUpper-iLower)*p->aiRowEst[0]/SQLITE_INDEX_SAMPLES;
- *pnRow = nRowEst;
+ rc = whereKeyStats(pParse, p, pRhs, 0, a);
+ if( rc==SQLITE_OK ){
+ WHERETRACE(("equality scan regions: %d\n", (int)a[1]));
+ *pnRow = a[1];
}
-
whereEqualScanEst_cancel:
sqlite3ValueFree(pRhs);
return rc;
}
-#endif /* defined(SQLITE_ENABLE_STAT2) */
+#endif /* defined(SQLITE_ENABLE_STAT3) */
-#ifdef SQLITE_ENABLE_STAT2
+#ifdef SQLITE_ENABLE_STAT3
/*
** Estimate the number of rows that will be returned based on
** an IN constraint where the right-hand side of the IN operator
@@ -2768,60 +2783,25 @@ static int whereInScanEst(
ExprList *pList, /* The value list on the RHS of "x IN (v1,v2,v3,...)" */
double *pnRow /* Write the revised row estimate here */
){
- sqlite3_value *pVal = 0; /* One value from list */
- int iLower, iUpper; /* Range of histogram regions containing pRhs */
- u8 aff; /* Column affinity */
int rc = SQLITE_OK; /* Subfunction return code */
+ double nEst; /* Number of rows for a single term */
double nRowEst; /* New estimate of the number of rows */
- int nSpan = 0; /* Number of histogram regions spanned */
- int nSingle = 0; /* Histogram regions hit by a single value */
- int nNotFound = 0; /* Count of values that are not constants */
- int i; /* Loop counter */
- u8 aSpan[SQLITE_INDEX_SAMPLES+1]; /* Histogram regions that are spanned */
- u8 aSingle[SQLITE_INDEX_SAMPLES+1]; /* Histogram regions hit once */
+ int i; /* Loop counter */
assert( p->aSample!=0 );
- aff = p->pTable->aCol[p->aiColumn[0]].affinity;
- memset(aSpan, 0, sizeof(aSpan));
- memset(aSingle, 0, sizeof(aSingle));
- for(i=0; i<pList->nExpr; i++){
- sqlite3ValueFree(pVal);
- rc = valueFromExpr(pParse, pList->a[i].pExpr, aff, &pVal);
- if( rc ) break;
- if( pVal==0 || sqlite3_value_type(pVal)==SQLITE_NULL ){
- nNotFound++;
- continue;
- }
- rc = whereRangeRegion(pParse, p, pVal, 0, &iLower);
- if( rc ) break;
- rc = whereRangeRegion(pParse, p, pVal, 1, &iUpper);
- if( rc ) break;
- if( iLower>=iUpper ){
- aSingle[iLower] = 1;
- }else{
- assert( iLower>=0 && iUpper<=SQLITE_INDEX_SAMPLES );
- while( iLower<iUpper ) aSpan[iLower++] = 1;
- }
+ for(i=0; rc==SQLITE_OK && i<pList->nExpr; i++){
+ nEst = p->aiRowEst[0];
+ rc = whereEqualScanEst(pParse, p, pList->a[i].pExpr, &nEst);
+ nRowEst += nEst;
}
if( rc==SQLITE_OK ){
- for(i=nSpan=0; i<=SQLITE_INDEX_SAMPLES; i++){
- if( aSpan[i] ){
- nSpan++;
- }else if( aSingle[i] ){
- nSingle++;
- }
- }
- nRowEst = (nSpan*2+nSingle)*p->aiRowEst[0]/(2*SQLITE_INDEX_SAMPLES)
- + nNotFound*p->aiRowEst[1];
if( nRowEst > p->aiRowEst[0] ) nRowEst = p->aiRowEst[0];
*pnRow = nRowEst;
- WHERETRACE(("IN row estimate: nSpan=%d, nSingle=%d, nNotFound=%d, est=%g\n",
- nSpan, nSingle, nNotFound, nRowEst));
+ WHERETRACE(("IN row estimate: est=%g\n", nRowEst));
}
- sqlite3ValueFree(pVal);
return rc;
}
-#endif /* defined(SQLITE_ENABLE_STAT2) */
+#endif /* defined(SQLITE_ENABLE_STAT3) */
/*
@@ -2868,7 +2848,7 @@ static void bestBtreeIndex(
int eqTermMask; /* Current mask of valid equality operators */
int idxEqTermMask; /* Index mask of valid equality operators */
Index sPk; /* A fake index object for the primary key */
- unsigned int aiRowEstPk[2]; /* The aiRowEst[] value for the sPk index */
+ tRowcnt aiRowEstPk[2]; /* The aiRowEst[] value for the sPk index */
int aiColumnPk = -1; /* The aColumn[] value for the sPk index */
int wsFlagMask; /* Allowed flags in pCost->plan.wsFlag */
@@ -2923,7 +2903,7 @@ static void bestBtreeIndex(
/* Loop over all indices looking for the best one to use
*/
for(; pProbe; pIdx=pProbe=pProbe->pNext){
- const unsigned int * const aiRowEst = pProbe->aiRowEst;
+ const tRowcnt * const aiRowEst = pProbe->aiRowEst;
double cost; /* Cost of using pProbe */
double nRow; /* Estimated number of rows in result set */
double log10N; /* base-10 logarithm of nRow (inexact) */
@@ -2966,14 +2946,12 @@ static void bestBtreeIndex(
** IN operator must be a SELECT, not a value list, for this variable
** to be true.
**
- ** estBound:
- ** An estimate on the amount of the table that must be searched. A
- ** value of 100 means the entire table is searched. Range constraints
- ** might reduce this to a value less than 100 to indicate that only
- ** a fraction of the table needs searching. In the absence of
- ** sqlite_stat2 ANALYZE data, a single inequality reduces the search
- ** space to 1/4rd its original size. So an x>? constraint reduces
- ** estBound to 25. Two constraints (x>? AND x<?) reduce estBound to 6.
+ ** rangeDiv:
+ ** An estimate of a divisor by which to reduce the search space due
+ ** to inequality constraints. In the absence of sqlite_stat3 ANALYZE
+ ** data, a single inequality reduces the search space to 1/4rd its
+ ** original size (rangeDiv==4). Two inequalities reduce the search
+ ** space to 1/16th of its original size (rangeDiv==16).
**
** bSort:
** Boolean. True if there is an ORDER BY clause that will require an
@@ -2998,13 +2976,13 @@ static void bestBtreeIndex(
int nEq; /* Number of == or IN terms matching index */
int bInEst = 0; /* True if "x IN (SELECT...)" seen */
int nInMul = 1; /* Number of distinct equalities to lookup */
- int estBound = 100; /* Estimated reduction in search space */
+ tRowcnt rangeDiv = 1; /* Estimated reduction in search space */
int nBound = 0; /* Number of range constraints seen */
int bSort = !!pOrderBy; /* True if external sort required */
int bDist = !!pDistinct; /* True if index cannot help with DISTINCT */
int bLookup = 0; /* True if not a covering index */
WhereTerm *pTerm; /* A single term of the WHERE clause */
-#ifdef SQLITE_ENABLE_STAT2
+#ifdef SQLITE_ENABLE_STAT3
WhereTerm *pFirstTerm = 0; /* First term matching the index */
#endif
@@ -3028,19 +3006,19 @@ static void bestBtreeIndex(
}else if( pTerm->eOperator & WO_ISNULL ){
wsFlags |= WHERE_COLUMN_NULL;
}
-#ifdef SQLITE_ENABLE_STAT2
+#ifdef SQLITE_ENABLE_STAT3
if( nEq==0 && pProbe->aSample ) pFirstTerm = pTerm;
#endif
used |= pTerm->prereqRight;
}
- /* Determine the value of estBound. */
+ /* Determine the value of rangeDiv */
if( nEq<pProbe->nColumn && pProbe->bUnordered==0 ){
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, &estBound);
+ whereRangeScanEst(pParse, pProbe, nEq, pBtm, pTop, &rangeDiv);
if( pTop ){
nBound = 1;
wsFlags |= WHERE_TOP_LIMIT;
@@ -3112,7 +3090,7 @@ static void bestBtreeIndex(
nInMul = (int)(nRow / aiRowEst[nEq]);
}
-#ifdef SQLITE_ENABLE_STAT2
+#ifdef SQLITE_ENABLE_STAT3
/* If the constraint is of the form x=VALUE or x IN (E1,E2,...)
** and we do not think that values of x are unique and if histogram
** data is available for column x, then it might be possible
@@ -3128,12 +3106,12 @@ static void bestBtreeIndex(
whereInScanEst(pParse, pProbe, pFirstTerm->pExpr->x.pList, &nRow);
}
}
-#endif /* SQLITE_ENABLE_STAT2 */
+#endif /* SQLITE_ENABLE_STAT3 */
/* Adjust the number of output rows and downward to reflect rows
** that are excluded by range constraints.
*/
- nRow = (nRow * (double)estBound) / (double)100;
+ nRow = nRow/(double)rangeDiv;
if( nRow<1 ) nRow = 1;
/* Experiments run on real SQLite databases show that the time needed
@@ -3262,10 +3240,10 @@ static void bestBtreeIndex(
WHERETRACE((
- "%s(%s): nEq=%d nInMul=%d estBound=%d bSort=%d bLookup=%d wsFlags=0x%x\n"
+ "%s(%s): nEq=%d nInMul=%d rangeDiv=%d bSort=%d bLookup=%d wsFlags=0x%x\n"
" notReady=0x%llx log10N=%.1f nRow=%.1f cost=%.1f used=0x%llx\n",
pSrc->pTab->zName, (pIdx ? pIdx->zName : "ipk"),
- nEq, nInMul, estBound, bSort, bLookup, wsFlags,
+ nEq, nInMul, (int)rangeDiv, bSort, bLookup, wsFlags,
notReady, log10N, nRow, cost, used
));
generated by cgit v1.2.3 (git 2.25.1) at 2025-07-19 22:58:08 +0000