/ Check-in [52e1d7e8]
Login
SQLite training in Houston TX on 2019-11-05 (details)
Part of the 2019 Tcl Conference

Many hyperlinks are disabled.
Use anonymous login to enable hyperlinks.

Overview
Comment:Begin a branch that experimentally replaces sqlite_stat2 with a new table called sqlite_stat3 that will hopefully facilitate better query planning decisions.
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | stat3-enhancement
Files: files | file ages | folders
SHA1: 52e1d7e8ddd4bb5ef3a9d00fd2d719a8a784f807
User & Date: drh 2011-08-12 01:51:45
Context
2011-08-13
00:58
The ANALYZE command picks for 15 samples for sqlite_stat3 with the largest nEq fields, plus 5 other evenly spaced samples. check-in: 8225924e user: drh tags: stat3-enhancement
2011-08-12
01:51
Begin a branch that experimentally replaces sqlite_stat2 with a new table called sqlite_stat3 that will hopefully facilitate better query planning decisions. check-in: 52e1d7e8 user: drh tags: stat3-enhancement
2011-08-10
01:52
Make the openDirectory routine in os_unix.c overrideable so that it can be turned into a harmless no-op for the chromium sandbox. check-in: 6b236069 user: drh tags: trunk
Changes
Hide Diffs Side-by-Side Diffs Ignore Whitespace Patch

Changes to src/analyze.c.

     6      6   **
     7      7   **    May you do good and not evil.
     8      8   **    May you find forgiveness for yourself and forgive others.
     9      9   **    May you share freely, never taking more than you give.
    10     10   **
    11     11   *************************************************************************
    12     12   ** This file contains code associated with the ANALYZE command.
           13  +**
           14  +** The ANALYZE command gather statistics about the content of tables
           15  +** and indices.  These statistics are made available to the query planner
           16  +** to help it make better decisions about how to perform queries.
           17  +**
           18  +** The following system tables are or have been supported:
           19  +**
           20  +**    CREATE TABLE sqlite_stat1(tbl, idx, stat);
           21  +**    CREATE TABLE sqlite_stat2(tbl, idx, sampleno, sample);
           22  +**    CREATE TABLE sqlite_stat3(tbl, idx, nLt, nEq, sample);
           23  +**
           24  +** Additional tables might be added in future releases of SQLite.
           25  +** The sqlite_stat2 table is not created or used unless the SQLite version
           26  +** is between 3.6.18 and 3.7.7, inclusive, and unless SQLite is compiled
           27  +** with SQLITE_ENABLE_STAT2.  The sqlite_stat2 table is deprecated.
           28  +** The sqlite_stat2 table is superceded by sqlite_stat3, which is only
           29  +** created and used by SQLite versions after 2011-08-09 with
           30  +** SQLITE_ENABLE_STAT3 defined.  The fucntionality of sqlite_stat3
           31  +** is a superset of sqlite_stat2.  
           32  +**
           33  +** Format of sqlite_stat1:
           34  +**
           35  +** There is normally one row per index, with the index identified by the
           36  +** name in the idx column.  The tbl column is the name of the table to
           37  +** which the index belongs.  In each such row, the stat column will be
           38  +** a string consisting of a list of integers.  The first integer in this
           39  +** list is the number of rows in the index and in the table.  The second
           40  +** integer is the average number of rows in the index that have the same
           41  +** value in the first column of the index.  The third integer is the average
           42  +** number of rows in the index that have the same value for the first two
           43  +** columns.  The N-th integer (for N>1) is the average number of rows in 
           44  +** the index which have the same value for the first N-1 columns.  For
           45  +** a K-column index, there will be K+1 integers in the stat column.  If
           46  +** the index is unique, then the last integer will be 1.
           47  +**
           48  +** The list of integers in the stat column can optionally be followed
           49  +** by the keyword "unordered".  The "unordered" keyword, if it is present,
           50  +** must be separated from the last integer by a single space.  If the
           51  +** "unordered" keyword is present, then the query planner assumes that
           52  +** the index is unordered and will not use the index for a range query.
           53  +** 
           54  +** If the sqlite_stat1.idx column is NULL, then the sqlite_stat1.stat
           55  +** column contains a single integer which is the (estimated) number of
           56  +** rows in the table identified by sqlite_stat1.tbl.
           57  +**
           58  +** Format of sqlite_stat2:
           59  +**
           60  +** The sqlite_stat2 is only created and is only used if SQLite is compiled
           61  +** with SQLITE_ENABLE_STAT2 and if the SQLite version number is between
           62  +** 3.6.18 and 3.7.7.  The "stat2" table contains additional information
           63  +** about the distribution of keys within an index.  The index is identified by
           64  +** the "idx" column and the "tbl" column is the name of the table to which
           65  +** the index belongs.  There are usually 10 rows in the sqlite_stat2
           66  +** table for each index.
           67  +**
           68  +** The sqlite_stat2 entires for an index that have sampleno between 0 and 9
           69  +** inclusive are samples of the left-most key value in the index taken at
           70  +** evenly spaced points along the index.  Let the number of samples be S
           71  +** (10 in the standard build) and let C be the number of rows in the index.
           72  +** Then the sampled rows are given by:
           73  +**
           74  +**     rownumber = (i*C*2 + C)/(S*2)
           75  +**
           76  +** For i between 0 and S-1.  Conceptually, the index space is divided into
           77  +** S uniform buckets and the samples are the middle row from each bucket.
           78  +**
           79  +** The format for sqlite_stat2 is recorded here for legacy reference.  This
           80  +** version of SQLite does not support sqlite_stat2.  It neither reads nor
           81  +** writes the sqlite_stat2 table.  This version of SQLite only supports
           82  +** sqlite_stat3.
           83  +**
           84  +** Format for sqlite_stat3:
           85  +**
           86  +** The sqlite_stat3 is an enhancement to sqlite_stat2.  A new name is
           87  +** used to avoid compatibility problems.  
           88  +**
           89  +** The format of the sqlite_stat3 table is similar to the format for
           90  +** the sqlite_stat2 table, with the following changes:  (1)
           91  +** The sampleno column is removed.  (2) Every sample has nEq and nLt 
           92  +** columns which hold the approximate number of keys in the table that
           93  +** exactly match the sample, and which are less than the sample,
           94  +** respectively.  (3) The number of samples can very from one table
           95  +** to the next; the sample count does not have to be exactly 10 as
           96  +** it is with sqlite_stat2. (4) The samples do not have to be evenly spaced.
           97  +**
           98  +** The ANALYZE command will typically generate sqlite_stat3 tables
           99  +** that contain between 10 and 40 samples which are distributed across
          100  +** the key space, though not uniformly, and which include samples with
          101  +** largest possible nEq values.
    13    102   */
    14    103   #ifndef SQLITE_OMIT_ANALYZE
    15    104   #include "sqliteInt.h"
    16    105   
    17    106   /*
    18    107   ** This routine generates code that opens the sqlite_stat1 table for
    19    108   ** writing with cursor iStatCur. If the library was built with the
................................................................................
    38    127     const char *zWhereType  /* Either "tbl" or "idx" */
    39    128   ){
    40    129     static const struct {
    41    130       const char *zName;
    42    131       const char *zCols;
    43    132     } aTable[] = {
    44    133       { "sqlite_stat1", "tbl,idx,stat" },
    45         -#ifdef SQLITE_ENABLE_STAT2
    46         -    { "sqlite_stat2", "tbl,idx,sampleno,sample" },
          134  +#ifdef SQLITE_ENABLE_STAT3
          135  +    { "sqlite_stat3", "tbl,idx,neq,nlt,sample" },
          136  +#endif
          137  +  };
          138  +  static const char *azToDrop[] = { 
          139  +    "sqlite_stat2",
          140  +#ifndef SQLITE_ENABLE_STAT3
          141  +    "sqlite_stat3",
    47    142   #endif
    48    143     };
    49    144   
    50    145     int aRoot[] = {0, 0};
    51    146     u8 aCreateTbl[] = {0, 0};
    52    147   
    53    148     int i;
................................................................................
    55    150     Db *pDb;
    56    151     Vdbe *v = sqlite3GetVdbe(pParse);
    57    152     if( v==0 ) return;
    58    153     assert( sqlite3BtreeHoldsAllMutexes(db) );
    59    154     assert( sqlite3VdbeDb(v)==db );
    60    155     pDb = &db->aDb[iDb];
    61    156   
          157  +  /* Drop all statistics tables that this version of SQLite does not
          158  +  ** understand.
          159  +  */
          160  +  for(i=0; i<ArraySize(azToDrop); i++){
          161  +    Table *pTab = sqlite3FindTable(db, azToDrop[i], pDb->zName);
          162  +    if( pTab ) sqlite3CodeDropTable(pParse, pTab, iDb, 0);
          163  +  }
          164  +
          165  +  /* Create new statistic tables if they do not exist, or clear them
          166  +  ** if they do already exist.
          167  +  */
    62    168     for(i=0; i<ArraySize(aTable); i++){
    63    169       const char *zTab = aTable[i].zName;
    64    170       Table *pStat;
    65    171       if( (pStat = sqlite3FindTable(db, zTab, pDb->zName))==0 ){
    66    172         /* The sqlite_stat[12] table does not exist. Create it. Note that a 
    67    173         ** side-effect of the CREATE TABLE statement is to leave the rootpage 
    68    174         ** of the new table in register pParse->regRoot. This is important 
................................................................................
    85    191         }else{
    86    192           /* The sqlite_stat[12] table already exists.  Delete all rows. */
    87    193           sqlite3VdbeAddOp2(v, OP_Clear, aRoot[i], iDb);
    88    194         }
    89    195       }
    90    196     }
    91    197   
    92         -  /* Open the sqlite_stat[12] tables for writing. */
          198  +  /* Open the sqlite_stat[13] tables for writing. */
    93    199     for(i=0; i<ArraySize(aTable); i++){
    94    200       sqlite3VdbeAddOp3(v, OP_OpenWrite, iStatCur+i, aRoot[i], iDb);
    95    201       sqlite3VdbeChangeP4(v, -1, (char *)3, P4_INT32);
    96    202       sqlite3VdbeChangeP5(v, aCreateTbl[i]);
    97    203     }
    98    204   }
    99    205   
          206  +/*
          207  +** Recommended number of samples for sqlite_stat3
          208  +*/
          209  +#ifndef SQLITE_STAT3_SAMPLES
          210  +# define SQLITE_STAT3_SAMPLES 16
          211  +#endif
          212  +
   100    213   /*
   101    214   ** Generate code to do an analysis of all indices associated with
   102    215   ** a single table.
   103    216   */
   104    217   static void analyzeOneTable(
   105    218     Parse *pParse,   /* Parser context */
   106    219     Table *pTab,     /* Table whose indices are to be analyzed */
................................................................................
   115    228     int i;                       /* Loop counter */
   116    229     int topOfLoop;               /* The top of the loop */
   117    230     int endOfLoop;               /* The end of the loop */
   118    231     int jZeroRows = -1;          /* Jump from here if number of rows is zero */
   119    232     int iDb;                     /* Index of database containing pTab */
   120    233     int regTabname = iMem++;     /* Register containing table name */
   121    234     int regIdxname = iMem++;     /* Register containing index name */
   122         -  int regSampleno = iMem++;    /* Register containing next sample number */
   123         -  int regCol = iMem++;         /* Content of a column analyzed table */
          235  +  int regStat1 = iMem++;       /* The stat column of sqlite_stat1 */
          236  +#ifdef SQLITE_ENABLE_STAT3
          237  +  int regNumEq = iMem-1;       /* Number of instances.  Same as regStat1 */
          238  +  int regNumLt = iMem++;       /* Number of keys less than regSample */
          239  +  int regSample = iMem++;      /* The next sample value */
          240  +  int regNext = iMem++;        /* Index of next sample to record */
          241  +  int regSpacing = iMem++;     /* Spacing between samples */
          242  +  int regBigSize = iMem++;     /* Always save entries with nEq >= this */
          243  +  int regTemp1 = iMem++;       /* Intermediate register */
          244  +  int regCount = iMem++;       /* Number of rows in the table or index */
          245  +  int regGosub = iMem++;       /* Register holding subroutine return addr */
          246  +  int once = 1;                /* One-time initialization */
          247  +  int shortJump = 0;           /* Instruction address */
          248  +  int addrStoreStat3 = 0;      /* Address of subroutine to wrote to stat3 */
          249  +#endif
          250  +  int regCol = iMem++;         /* Content of a column in analyzed table */
   124    251     int regRec = iMem++;         /* Register holding completed record */
   125    252     int regTemp = iMem++;        /* Temporary use register */
   126    253     int regRowid = iMem++;       /* Rowid for the inserted record */
   127    254   
   128         -#ifdef SQLITE_ENABLE_STAT2
   129         -  int addr = 0;                /* Instruction address */
   130         -  int regTemp2 = iMem++;       /* Temporary use register */
   131         -  int regSamplerecno = iMem++; /* Index of next sample to record */
   132         -  int regRecno = iMem++;       /* Current sample index */
   133         -  int regLast = iMem++;        /* Index of last sample to record */
   134         -  int regFirst = iMem++;       /* Index of first sample to record */
   135         -#endif
   136    255   
   137    256     v = sqlite3GetVdbe(pParse);
   138    257     if( v==0 || NEVER(pTab==0) ){
   139    258       return;
   140    259     }
   141    260     if( pTab->tnum==0 ){
   142    261       /* Do not gather statistics on views or virtual tables */
................................................................................
   161    280     sqlite3TableLock(pParse, iDb, pTab->tnum, 0, pTab->zName);
   162    281   
   163    282     iIdxCur = pParse->nTab++;
   164    283     sqlite3VdbeAddOp4(v, OP_String8, 0, regTabname, 0, pTab->zName, 0);
   165    284     for(pIdx=pTab->pIndex; pIdx; pIdx=pIdx->pNext){
   166    285       int nCol;
   167    286       KeyInfo *pKey;
          287  +    int addrIfNot;               /* address of OP_IfNot */
          288  +    int *aChngAddr;              /* Array of jump instruction addresses */
   168    289   
   169    290       if( pOnlyIdx && pOnlyIdx!=pIdx ) continue;
          291  +    VdbeNoopComment((v, "Begin analysis of %s", pIdx->zName));
   170    292       nCol = pIdx->nColumn;
   171    293       pKey = sqlite3IndexKeyinfo(pParse, pIdx);
   172    294       if( iMem+1+(nCol*2)>pParse->nMem ){
   173    295         pParse->nMem = iMem+1+(nCol*2);
   174    296       }
          297  +    aChngAddr = sqlite3DbMallocRaw(db, sizeof(int)*pIdx->nColumn);
          298  +    if( aChngAddr==0 ) continue;
   175    299   
   176    300       /* Open a cursor to the index to be analyzed. */
   177    301       assert( iDb==sqlite3SchemaToIndex(db, pIdx->pSchema) );
   178    302       sqlite3VdbeAddOp4(v, OP_OpenRead, iIdxCur, pIdx->tnum, iDb,
   179    303           (char *)pKey, P4_KEYINFO_HANDOFF);
   180    304       VdbeComment((v, "%s", pIdx->zName));
   181    305   
   182    306       /* Populate the register containing the index name. */
   183    307       sqlite3VdbeAddOp4(v, OP_String8, 0, regIdxname, 0, pIdx->zName, 0);
   184    308   
   185         -#ifdef SQLITE_ENABLE_STAT2
          309  +#ifdef SQLITE_ENABLE_STAT3
   186    310   
   187    311       /* If this iteration of the loop is generating code to analyze the
   188    312       ** first index in the pTab->pIndex list, then register regLast has
   189    313       ** not been populated. In this case populate it now.  */
   190         -    if( pTab->pIndex==pIdx ){
   191         -      sqlite3VdbeAddOp2(v, OP_Integer, SQLITE_INDEX_SAMPLES, regSamplerecno);
   192         -      sqlite3VdbeAddOp2(v, OP_Integer, SQLITE_INDEX_SAMPLES*2-1, regTemp);
   193         -      sqlite3VdbeAddOp2(v, OP_Integer, SQLITE_INDEX_SAMPLES*2, regTemp2);
   194         -
   195         -      sqlite3VdbeAddOp2(v, OP_Count, iIdxCur, regLast);
   196         -      sqlite3VdbeAddOp2(v, OP_Null, 0, regFirst);
   197         -      addr = sqlite3VdbeAddOp3(v, OP_Lt, regSamplerecno, 0, regLast);
   198         -      sqlite3VdbeAddOp3(v, OP_Divide, regTemp2, regLast, regFirst);
   199         -      sqlite3VdbeAddOp3(v, OP_Multiply, regLast, regTemp, regLast);
   200         -      sqlite3VdbeAddOp2(v, OP_AddImm, regLast, SQLITE_INDEX_SAMPLES*2-2);
   201         -      sqlite3VdbeAddOp3(v, OP_Divide,  regTemp2, regLast, regLast);
   202         -      sqlite3VdbeJumpHere(v, addr);
   203         -    }
   204         -
   205         -    /* Zero the regSampleno and regRecno registers. */
   206         -    sqlite3VdbeAddOp2(v, OP_Integer, 0, regSampleno);
   207         -    sqlite3VdbeAddOp2(v, OP_Integer, 0, regRecno);
   208         -    sqlite3VdbeAddOp2(v, OP_Copy, regFirst, regSamplerecno);
   209         -#endif
          314  +    if( once ){
          315  +      once = 0;
          316  +      sqlite3VdbeAddOp2(v, OP_Count, iIdxCur, regCount);
          317  +      sqlite3VdbeAddOp2(v, OP_Integer, SQLITE_STAT3_SAMPLES, regTemp1);
          318  +      sqlite3VdbeAddOp3(v, OP_Divide, regTemp1, regCount, regSpacing);
          319  +      sqlite3VdbeAddOp2(v, OP_Integer, SQLITE_STAT3_SAMPLES/2, regTemp1);
          320  +      sqlite3VdbeAddOp3(v, OP_Divide, regTemp1, regCount, regBigSize);
          321  +
          322  +      /* Generate code for a subroutine that store the most recent sample
          323  +      ** in the sqlite_stat3 table
          324  +      */
          325  +      shortJump = sqlite3VdbeAddOp0(v, OP_Goto);
          326  +        sqlite3VdbeAddOp4(v, OP_MakeRecord, regTabname, 5, regRec, "bbbbb", 0);
          327  +        VdbeComment((v, "begin stat3 write subroutine"));
          328  +      sqlite3VdbeAddOp2(v, OP_NewRowid, iStatCur+1, regRowid);
          329  +      sqlite3VdbeAddOp3(v, OP_Insert, iStatCur+1, regRec, regRowid);
          330  +      sqlite3VdbeAddOp3(v, OP_Add, regNext, regSpacing, regNext);
          331  +      sqlite3VdbeAddOp1(v, OP_Return, regGosub);
          332  +      addrStoreStat3 = 
          333  +      sqlite3VdbeAddOp3(v, OP_Ge, regBigSize, shortJump+1, regNumEq);
          334  +      sqlite3VdbeAddOp3(v, OP_Add, regNumEq, regNumLt, regTemp1);
          335  +      sqlite3VdbeAddOp3(v, OP_Ge, regNext, shortJump+1, regTemp1);
          336  +      sqlite3VdbeAddOp1(v, OP_Return, regGosub);
          337  +      VdbeComment((v, "end stat3 write subroutine"));
          338  +      sqlite3VdbeJumpHere(v, shortJump);
          339  +    }
          340  +    /* Reset state registers */
          341  +    sqlite3VdbeAddOp2(v, OP_Copy, regSpacing, regNext);
          342  +    sqlite3VdbeAddOp2(v, OP_Integer, 0, regNumEq);
          343  +    sqlite3VdbeAddOp2(v, OP_Integer, 0, regNumLt);
          344  +
          345  +#endif /* SQLITE_ENABLE_STAT3 */
   210    346   
   211    347       /* The block of memory cells initialized here is used as follows.
   212    348       **
   213    349       **    iMem:                
   214    350       **        The total number of rows in the table.
   215    351       **
   216    352       **    iMem+1 .. iMem+nCol: 
................................................................................
   232    368       }
   233    369   
   234    370       /* Start the analysis loop. This loop runs through all the entries in
   235    371       ** the index b-tree.  */
   236    372       endOfLoop = sqlite3VdbeMakeLabel(v);
   237    373       sqlite3VdbeAddOp2(v, OP_Rewind, iIdxCur, endOfLoop);
   238    374       topOfLoop = sqlite3VdbeCurrentAddr(v);
   239         -    sqlite3VdbeAddOp2(v, OP_AddImm, iMem, 1);
          375  +    sqlite3VdbeAddOp2(v, OP_AddImm, iMem, 1);  /* Increment row counter */
   240    376   
   241    377       for(i=0; i<nCol; i++){
   242    378         CollSeq *pColl;
   243    379         sqlite3VdbeAddOp3(v, OP_Column, iIdxCur, i, regCol);
   244    380         if( i==0 ){
   245         -#ifdef SQLITE_ENABLE_STAT2
   246         -        /* Check if the record that cursor iIdxCur points to contains a
   247         -        ** value that should be stored in the sqlite_stat2 table. If so,
   248         -        ** store it.  */
   249         -        int ne = sqlite3VdbeAddOp3(v, OP_Ne, regRecno, 0, regSamplerecno);
   250         -        assert( regTabname+1==regIdxname 
   251         -             && regTabname+2==regSampleno
   252         -             && regTabname+3==regCol
   253         -        );
   254         -        sqlite3VdbeChangeP5(v, SQLITE_JUMPIFNULL);
   255         -        sqlite3VdbeAddOp4(v, OP_MakeRecord, regTabname, 4, regRec, "aaab", 0);
   256         -        sqlite3VdbeAddOp2(v, OP_NewRowid, iStatCur+1, regRowid);
   257         -        sqlite3VdbeAddOp3(v, OP_Insert, iStatCur+1, regRec, regRowid);
   258         -
   259         -        /* Calculate new values for regSamplerecno and regSampleno.
   260         -        **
   261         -        **   sampleno = sampleno + 1
   262         -        **   samplerecno = samplerecno+(remaining records)/(remaining samples)
   263         -        */
   264         -        sqlite3VdbeAddOp2(v, OP_AddImm, regSampleno, 1);
   265         -        sqlite3VdbeAddOp3(v, OP_Subtract, regRecno, regLast, regTemp);
   266         -        sqlite3VdbeAddOp2(v, OP_AddImm, regTemp, -1);
   267         -        sqlite3VdbeAddOp2(v, OP_Integer, SQLITE_INDEX_SAMPLES, regTemp2);
   268         -        sqlite3VdbeAddOp3(v, OP_Subtract, regSampleno, regTemp2, regTemp2);
   269         -        sqlite3VdbeAddOp3(v, OP_Divide, regTemp2, regTemp, regTemp);
   270         -        sqlite3VdbeAddOp3(v, OP_Add, regSamplerecno, regTemp, regSamplerecno);
   271         -
   272         -        sqlite3VdbeJumpHere(v, ne);
   273         -        sqlite3VdbeAddOp2(v, OP_AddImm, regRecno, 1);
   274         -#endif
   275         -
   276    381           /* Always record the very first row */
   277         -        sqlite3VdbeAddOp1(v, OP_IfNot, iMem+1);
          382  +        addrIfNot = sqlite3VdbeAddOp1(v, OP_IfNot, iMem+1);
   278    383         }
   279    384         assert( pIdx->azColl!=0 );
   280    385         assert( pIdx->azColl[i]!=0 );
   281    386         pColl = sqlite3LocateCollSeq(pParse, pIdx->azColl[i]);
   282         -      sqlite3VdbeAddOp4(v, OP_Ne, regCol, 0, iMem+nCol+i+1,
   283         -                       (char*)pColl, P4_COLLSEQ);
          387  +      aChngAddr[i] = sqlite3VdbeAddOp4(v, OP_Ne, regCol, 0, iMem+nCol+i+1,
          388  +                                      (char*)pColl, P4_COLLSEQ);
   284    389         sqlite3VdbeChangeP5(v, SQLITE_NULLEQ);
   285         -    }
   286         -    if( db->mallocFailed ){
   287         -      /* If a malloc failure has occurred, then the result of the expression 
   288         -      ** passed as the second argument to the call to sqlite3VdbeJumpHere() 
   289         -      ** below may be negative. Which causes an assert() to fail (or an
   290         -      ** out-of-bounds write if SQLITE_DEBUG is not defined).  */
   291         -      return;
          390  +      VdbeComment((v, "jump if column %d changed", i));
          391  +#ifdef SQLITE_ENABLE_STAT3
          392  +      if( i==0 && addrStoreStat3 ){
          393  +        sqlite3VdbeAddOp2(v, OP_AddImm, regNumEq, 1);
          394  +        VdbeComment((v, "incr repeat count"));
          395  +      }
          396  +#endif
   292    397       }
   293    398       sqlite3VdbeAddOp2(v, OP_Goto, 0, endOfLoop);
   294    399       for(i=0; i<nCol; i++){
   295         -      int addr2 = sqlite3VdbeCurrentAddr(v) - (nCol*2);
          400  +      sqlite3VdbeJumpHere(v, aChngAddr[i]);  /* Set jump dest for the OP_Ne */
   296    401         if( i==0 ){
   297         -        sqlite3VdbeJumpHere(v, addr2-1);  /* Set jump dest for the OP_IfNot */
          402  +        sqlite3VdbeJumpHere(v, addrIfNot);   /* Jump dest for OP_IfNot */
          403  +#ifdef SQLITE_ENABLE_STAT3
          404  +        sqlite3VdbeAddOp2(v, OP_Gosub, regGosub, addrStoreStat3);
          405  +        sqlite3VdbeAddOp2(v, OP_Copy, regCol, regSample);
          406  +        sqlite3VdbeAddOp3(v, OP_Add, regNumEq, regNumLt, regNumLt);
          407  +        sqlite3VdbeAddOp2(v, OP_Integer, 1, regNumEq);
          408  +#endif        
   298    409         }
   299         -      sqlite3VdbeJumpHere(v, addr2);      /* Set jump dest for the OP_Ne */
   300    410         sqlite3VdbeAddOp2(v, OP_AddImm, iMem+i+1, 1);
   301    411         sqlite3VdbeAddOp3(v, OP_Column, iIdxCur, i, iMem+nCol+i+1);
   302    412       }
          413  +    sqlite3DbFree(db, aChngAddr);
   303    414   
   304         -    /* End of the analysis loop. */
          415  +    /* Always jump here after updating the iMem+1...iMem+1+nCol counters */
   305    416       sqlite3VdbeResolveLabel(v, endOfLoop);
          417  +
   306    418       sqlite3VdbeAddOp2(v, OP_Next, iIdxCur, topOfLoop);
   307    419       sqlite3VdbeAddOp1(v, OP_Close, iIdxCur);
          420  +#ifdef SQLITE_ENABLE_STAT3
          421  +    sqlite3VdbeAddOp2(v, OP_Gosub, regGosub, addrStoreStat3);
          422  +#endif        
   308    423   
   309    424       /* Store the results in sqlite_stat1.
   310    425       **
   311    426       ** The result is a single row of the sqlite_stat1 table.  The first
   312    427       ** two columns are the names of the table and index.  The third column
   313    428       ** is a string composed of a list of integer statistics about the
   314    429       ** index.  The first integer in the list is the total number of entries
................................................................................
   320    435       **
   321    436       **        I = (K+D-1)/D
   322    437       **
   323    438       ** If K==0 then no entry is made into the sqlite_stat1 table.  
   324    439       ** If K>0 then it is always the case the D>0 so division by zero
   325    440       ** is never possible.
   326    441       */
   327         -    sqlite3VdbeAddOp2(v, OP_SCopy, iMem, regSampleno);
          442  +    sqlite3VdbeAddOp2(v, OP_SCopy, iMem, regStat1);
   328    443       if( jZeroRows<0 ){
   329    444         jZeroRows = sqlite3VdbeAddOp1(v, OP_IfNot, iMem);
   330    445       }
   331    446       for(i=0; i<nCol; i++){
   332    447         sqlite3VdbeAddOp4(v, OP_String8, 0, regTemp, 0, " ", 0);
   333         -      sqlite3VdbeAddOp3(v, OP_Concat, regTemp, regSampleno, regSampleno);
          448  +      sqlite3VdbeAddOp3(v, OP_Concat, regTemp, regStat1, regStat1);
   334    449         sqlite3VdbeAddOp3(v, OP_Add, iMem, iMem+i+1, regTemp);
   335    450         sqlite3VdbeAddOp2(v, OP_AddImm, regTemp, -1);
   336    451         sqlite3VdbeAddOp3(v, OP_Divide, iMem+i+1, regTemp, regTemp);
   337    452         sqlite3VdbeAddOp1(v, OP_ToInt, regTemp);
   338         -      sqlite3VdbeAddOp3(v, OP_Concat, regTemp, regSampleno, regSampleno);
          453  +      sqlite3VdbeAddOp3(v, OP_Concat, regTemp, regStat1, regStat1);
   339    454       }
   340    455       sqlite3VdbeAddOp4(v, OP_MakeRecord, regTabname, 3, regRec, "aaa", 0);
   341    456       sqlite3VdbeAddOp2(v, OP_NewRowid, iStatCur, regRowid);
   342    457       sqlite3VdbeAddOp3(v, OP_Insert, iStatCur, regRec, regRowid);
   343    458       sqlite3VdbeChangeP5(v, OPFLAG_APPEND);
   344    459     }
   345    460   
   346    461     /* If the table has no indices, create a single sqlite_stat1 entry
   347    462     ** containing NULL as the index name and the row count as the content.
   348    463     */
   349    464     if( pTab->pIndex==0 ){
   350    465       sqlite3VdbeAddOp3(v, OP_OpenRead, iIdxCur, pTab->tnum, iDb);
   351    466       VdbeComment((v, "%s", pTab->zName));
   352         -    sqlite3VdbeAddOp2(v, OP_Count, iIdxCur, regSampleno);
          467  +    sqlite3VdbeAddOp2(v, OP_Count, iIdxCur, regStat1);
   353    468       sqlite3VdbeAddOp1(v, OP_Close, iIdxCur);
   354         -    jZeroRows = sqlite3VdbeAddOp1(v, OP_IfNot, regSampleno);
          469  +    jZeroRows = sqlite3VdbeAddOp1(v, OP_IfNot, regStat1);
   355    470     }else{
   356    471       sqlite3VdbeJumpHere(v, jZeroRows);
   357    472       jZeroRows = sqlite3VdbeAddOp0(v, OP_Goto);
   358    473     }
   359    474     sqlite3VdbeAddOp2(v, OP_Null, 0, regIdxname);
   360    475     sqlite3VdbeAddOp4(v, OP_MakeRecord, regTabname, 3, regRec, "aaa", 0);
   361    476     sqlite3VdbeAddOp2(v, OP_NewRowid, iStatCur, regRowid);
   362    477     sqlite3VdbeAddOp3(v, OP_Insert, iStatCur, regRec, regRowid);
   363    478     sqlite3VdbeChangeP5(v, OPFLAG_APPEND);
   364    479     if( pParse->nMem<regRec ) pParse->nMem = regRec;
   365    480     sqlite3VdbeJumpHere(v, jZeroRows);
   366    481   }
          482  +
   367    483   
   368    484   /*
   369    485   ** Generate code that will cause the most recent index analysis to
   370    486   ** be loaded into internal hash tables where is can be used.
   371    487   */
   372    488   static void loadAnalysis(Parse *pParse, int iDb){
   373    489     Vdbe *v = sqlite3GetVdbe(pParse);
................................................................................
   514    630   ** the table.
   515    631   */
   516    632   static int analysisLoader(void *pData, int argc, char **argv, char **NotUsed){
   517    633     analysisInfo *pInfo = (analysisInfo*)pData;
   518    634     Index *pIndex;
   519    635     Table *pTable;
   520    636     int i, c, n;
   521         -  unsigned int v;
          637  +  tRowcnt v;
   522    638     const char *z;
   523    639   
   524    640     assert( argc==3 );
   525    641     UNUSED_PARAMETER2(NotUsed, argc);
   526    642   
   527    643     if( argv==0 || argv[0]==0 || argv[2]==0 ){
   528    644       return 0;
................................................................................
   557    673   }
   558    674   
   559    675   /*
   560    676   ** If the Index.aSample variable is not NULL, delete the aSample[] array
   561    677   ** and its contents.
   562    678   */
   563    679   void sqlite3DeleteIndexSamples(sqlite3 *db, Index *pIdx){
   564         -#ifdef SQLITE_ENABLE_STAT2
          680  +#ifdef SQLITE_ENABLE_STAT3
   565    681     if( pIdx->aSample ){
   566    682       int j;
   567         -    for(j=0; j<SQLITE_INDEX_SAMPLES; j++){
          683  +    for(j=0; j<pIdx->nSample; j++){
   568    684         IndexSample *p = &pIdx->aSample[j];
   569    685         if( p->eType==SQLITE_TEXT || p->eType==SQLITE_BLOB ){
   570         -        sqlite3DbFree(db, p->u.z);
          686  +        sqlite3_free(p->u.z);
   571    687         }
   572    688       }
   573         -    sqlite3DbFree(db, pIdx->aSample);
          689  +    sqlite3_free(pIdx->aSample);
   574    690     }
          691  +  pIdx->nSample = 0;
          692  +  pIdx->aSample = 0;
   575    693   #else
   576    694     UNUSED_PARAMETER(db);
   577    695     UNUSED_PARAMETER(pIdx);
   578    696   #endif
   579    697   }
   580    698   
          699  +#ifdef SQLITE_ENABLE_STAT3
          700  +/*
          701  +** Load content from the sqlite_stat3 table into the Index.aSample[]
          702  +** arrays of all indices.
          703  +*/
          704  +static int loadStat3(sqlite3 *db, const char *zDb){
          705  +  int rc;                       /* Result codes from subroutines */
          706  +  sqlite3_stmt *pStmt = 0;      /* An SQL statement being run */
          707  +  char *zSql;                   /* Text of the SQL statement */
          708  +  Index *pPrevIdx = 0;          /* Previous index in the loop */
          709  +  int idx;                      /* slot in pIdx->aSample[] for next sample */
          710  +  int eType;                    /* Datatype of a sample */
          711  +  IndexSample *pSample;         /* A slot in pIdx->aSample[] */
          712  +
          713  +  if( !sqlite3FindTable(db, "sqlite_stat3", zDb) ){
          714  +    return SQLITE_OK;
          715  +  }
          716  +
          717  +  zSql = sqlite3MPrintf(db, 
          718  +      "SELECT idx,count(*) FROM %Q.sqlite_stat3"
          719  +      " GROUP BY idx", zDb);
          720  +  if( !zSql ){
          721  +    return SQLITE_NOMEM;
          722  +  }
          723  +  rc = sqlite3_prepare(db, zSql, -1, &pStmt, 0);
          724  +  sqlite3DbFree(db, zSql);
          725  +  if( rc ) return rc;
          726  +
          727  +  while( sqlite3_step(pStmt)==SQLITE_ROW ){
          728  +    char *zIndex;   /* Index name */
          729  +    Index *pIdx;    /* Pointer to the index object */
          730  +    int nSample;    /* Number of samples */
          731  +
          732  +    zIndex = (char *)sqlite3_column_text(pStmt, 0);
          733  +    if( zIndex==0 ) continue;
          734  +    nSample = sqlite3_column_int(pStmt, 1);
          735  +    if( nSample>255 ) continue;
          736  +    pIdx = sqlite3FindIndex(db, zIndex, zDb);
          737  +    if( pIdx==0 ) continue;
          738  +    assert( pIdx->nSample==0 );
          739  +    pIdx->nSample = (u8)nSample;
          740  +    pIdx->aSample = sqlite3MallocZero( nSample*sizeof(IndexSample) );
          741  +    if( pIdx->aSample==0 ){
          742  +      db->mallocFailed = 1;
          743  +      sqlite3_finalize(pStmt);
          744  +      return SQLITE_NOMEM;
          745  +    }
          746  +  }
          747  +  sqlite3_finalize(pStmt);
          748  +
          749  +  zSql = sqlite3MPrintf(db, 
          750  +      "SELECT idx,nlt,neq,sample FROM %Q.sqlite_stat3"
          751  +      " ORDER BY idx, nlt", zDb);
          752  +  if( !zSql ){
          753  +    return SQLITE_NOMEM;
          754  +  }
          755  +  rc = sqlite3_prepare(db, zSql, -1, &pStmt, 0);
          756  +  sqlite3DbFree(db, zSql);
          757  +  if( rc ) return rc;
          758  +
          759  +  while( sqlite3_step(pStmt)==SQLITE_ROW ){
          760  +    char *zIndex;   /* Index name */
          761  +    Index *pIdx;    /* Pointer to the index object */
          762  +
          763  +    zIndex = (char *)sqlite3_column_text(pStmt, 0);
          764  +    if( zIndex==0 ) continue;
          765  +    pIdx = sqlite3FindIndex(db, zIndex, zDb);
          766  +    if( pIdx==0 ) continue;
          767  +    if( pIdx==pPrevIdx ){
          768  +      idx++;
          769  +    }else{
          770  +      pPrevIdx = pIdx;
          771  +      idx = 0;
          772  +    }
          773  +    assert( idx<pIdx->nSample );
          774  +    pSample = &pIdx->aSample[idx];
          775  +    pSample->nLt = (tRowcnt)sqlite3_column_int64(pStmt, 1);
          776  +    pSample->nEq = (tRowcnt)sqlite3_column_int64(pStmt, 2);
          777  +    eType = sqlite3_column_type(pStmt, 3);
          778  +    pSample->eType = (u8)eType;
          779  +    switch( eType ){
          780  +      case SQLITE_INTEGER: {
          781  +        pSample->u.i = sqlite3_column_int64(pStmt, 3);
          782  +        break;
          783  +      }
          784  +      case SQLITE_FLOAT: {
          785  +        pSample->u.r = sqlite3_column_double(pStmt, 3);
          786  +        break;
          787  +      }
          788  +      case SQLITE_NULL: {
          789  +        break;
          790  +      }
          791  +      default: assert( eType==SQLITE_TEXT || eType==SQLITE_BLOB ); {
          792  +        const char *z = (const char *)(
          793  +              (eType==SQLITE_BLOB) ?
          794  +              sqlite3_column_blob(pStmt, 3):
          795  +              sqlite3_column_text(pStmt, 3)
          796  +           );
          797  +        int n = sqlite3_column_bytes(pStmt, 2);
          798  +        if( n>0xffff ) n = 0xffff;
          799  +        pSample->nByte = (u16)n;
          800  +        if( n < 1){
          801  +          pSample->u.z = 0;
          802  +        }else{
          803  +          pSample->u.z = sqlite3Malloc(n);
          804  +          if( pSample->u.z==0 ){
          805  +            db->mallocFailed = 1;
          806  +            sqlite3_finalize(pStmt);
          807  +            return SQLITE_NOMEM;
          808  +          }
          809  +          memcpy(pSample->u.z, z, n);
          810  +        }
          811  +      }
          812  +    }
          813  +  }
          814  +  return sqlite3_finalize(pStmt);
          815  +}
          816  +#endif /* SQLITE_ENABLE_STAT3 */
          817  +
   581    818   /*
   582         -** Load the content of the sqlite_stat1 and sqlite_stat2 tables. The
          819  +** Load the content of the sqlite_stat1 and sqlite_stat3 tables. The
   583    820   ** contents of sqlite_stat1 are used to populate the Index.aiRowEst[]
   584         -** arrays. The contents of sqlite_stat2 are used to populate the
          821  +** arrays. The contents of sqlite_stat3 are used to populate the
   585    822   ** Index.aSample[] arrays.
   586    823   **
   587    824   ** If the sqlite_stat1 table is not present in the database, SQLITE_ERROR
   588         -** is returned. In this case, even if SQLITE_ENABLE_STAT2 was defined 
   589         -** during compilation and the sqlite_stat2 table is present, no data is 
          825  +** is returned. In this case, even if SQLITE_ENABLE_STAT3 was defined 
          826  +** during compilation and the sqlite_stat3 table is present, no data is 
   590    827   ** read from it.
   591    828   **
   592         -** If SQLITE_ENABLE_STAT2 was defined during compilation and the 
   593         -** sqlite_stat2 table is not present in the database, SQLITE_ERROR is
          829  +** If SQLITE_ENABLE_STAT3 was defined during compilation and the 
          830  +** sqlite_stat3 table is not present in the database, SQLITE_ERROR is
   594    831   ** returned. However, in this case, data is read from the sqlite_stat1
   595    832   ** table (if it is present) before returning.
   596    833   **
   597    834   ** If an OOM error occurs, this function always sets db->mallocFailed.
   598    835   ** This means if the caller does not care about other errors, the return
   599    836   ** code may be ignored.
   600    837   */
................................................................................
   608    845     assert( db->aDb[iDb].pBt!=0 );
   609    846   
   610    847     /* Clear any prior statistics */
   611    848     assert( sqlite3SchemaMutexHeld(db, iDb, 0) );
   612    849     for(i=sqliteHashFirst(&db->aDb[iDb].pSchema->idxHash);i;i=sqliteHashNext(i)){
   613    850       Index *pIdx = sqliteHashData(i);
   614    851       sqlite3DefaultRowEst(pIdx);
          852  +#ifdef SQLITE_ENABLE_STAT3
   615    853       sqlite3DeleteIndexSamples(db, pIdx);
   616    854       pIdx->aSample = 0;
          855  +#endif
   617    856     }
   618    857   
   619    858     /* Check to make sure the sqlite_stat1 table exists */
   620    859     sInfo.db = db;
   621    860     sInfo.zDatabase = db->aDb[iDb].zName;
   622    861     if( sqlite3FindTable(db, "sqlite_stat1", sInfo.zDatabase)==0 ){
   623    862       return SQLITE_ERROR;
   624    863     }
   625    864   
   626    865     /* Load new statistics out of the sqlite_stat1 table */
   627    866     zSql = sqlite3MPrintf(db, 
   628         -      "SELECT tbl, idx, stat FROM %Q.sqlite_stat1", sInfo.zDatabase);
          867  +      "SELECT tbl,idx,stat FROM %Q.sqlite_stat1", sInfo.zDatabase);
   629    868     if( zSql==0 ){
   630    869       rc = SQLITE_NOMEM;
   631    870     }else{
   632    871       rc = sqlite3_exec(db, zSql, analysisLoader, &sInfo, 0);
   633    872       sqlite3DbFree(db, zSql);
   634    873     }
   635    874   
   636    875   
   637         -  /* Load the statistics from the sqlite_stat2 table. */
   638         -#ifdef SQLITE_ENABLE_STAT2
   639         -  if( rc==SQLITE_OK && !sqlite3FindTable(db, "sqlite_stat2", sInfo.zDatabase) ){
   640         -    rc = SQLITE_ERROR;
   641         -  }
          876  +  /* Load the statistics from the sqlite_stat3 table. */
          877  +#ifdef SQLITE_ENABLE_STAT3
   642    878     if( rc==SQLITE_OK ){
   643         -    sqlite3_stmt *pStmt = 0;
   644         -
   645         -    zSql = sqlite3MPrintf(db, 
   646         -        "SELECT idx,sampleno,sample FROM %Q.sqlite_stat2", sInfo.zDatabase);
   647         -    if( !zSql ){
   648         -      rc = SQLITE_NOMEM;
   649         -    }else{
   650         -      rc = sqlite3_prepare(db, zSql, -1, &pStmt, 0);
   651         -      sqlite3DbFree(db, zSql);
   652         -    }
   653         -
   654         -    if( rc==SQLITE_OK ){
   655         -      while( sqlite3_step(pStmt)==SQLITE_ROW ){
   656         -        char *zIndex;   /* Index name */
   657         -        Index *pIdx;    /* Pointer to the index object */
   658         -
   659         -        zIndex = (char *)sqlite3_column_text(pStmt, 0);
   660         -        pIdx = zIndex ? sqlite3FindIndex(db, zIndex, sInfo.zDatabase) : 0;
   661         -        if( pIdx ){
   662         -          int iSample = sqlite3_column_int(pStmt, 1);
   663         -          if( iSample<SQLITE_INDEX_SAMPLES && iSample>=0 ){
   664         -            int eType = sqlite3_column_type(pStmt, 2);
   665         -
   666         -            if( pIdx->aSample==0 ){
   667         -              static const int sz = sizeof(IndexSample)*SQLITE_INDEX_SAMPLES;
   668         -              pIdx->aSample = (IndexSample *)sqlite3DbMallocRaw(0, sz);
   669         -              if( pIdx->aSample==0 ){
   670         -                db->mallocFailed = 1;
   671         -                break;
   672         -              }
   673         -	      memset(pIdx->aSample, 0, sz);
   674         -            }
   675         -
   676         -            assert( pIdx->aSample );
   677         -            {
   678         -              IndexSample *pSample = &pIdx->aSample[iSample];
   679         -              pSample->eType = (u8)eType;
   680         -              if( eType==SQLITE_INTEGER || eType==SQLITE_FLOAT ){
   681         -                pSample->u.r = sqlite3_column_double(pStmt, 2);
   682         -              }else if( eType==SQLITE_TEXT || eType==SQLITE_BLOB ){
   683         -                const char *z = (const char *)(
   684         -                    (eType==SQLITE_BLOB) ?
   685         -                    sqlite3_column_blob(pStmt, 2):
   686         -                    sqlite3_column_text(pStmt, 2)
   687         -                );
   688         -                int n = sqlite3_column_bytes(pStmt, 2);
   689         -                if( n>24 ){
   690         -                  n = 24;
   691         -                }
   692         -                pSample->nByte = (u8)n;
   693         -                if( n < 1){
   694         -                  pSample->u.z = 0;
   695         -                }else{
   696         -                  pSample->u.z = sqlite3DbStrNDup(0, z, n);
   697         -                  if( pSample->u.z==0 ){
   698         -                    db->mallocFailed = 1;
   699         -                    break;
   700         -                  }
   701         -                }
   702         -              }
   703         -            }
   704         -          }
   705         -        }
   706         -      }
   707         -      rc = sqlite3_finalize(pStmt);
   708         -    }
          879  +    rc = loadStat3(db, sInfo.zDatabase);
   709    880     }
   710    881   #endif
   711    882   
   712    883     if( rc==SQLITE_NOMEM ){
   713    884       db->mallocFailed = 1;
   714    885     }
   715    886     return rc;
   716    887   }
   717    888   
   718    889   
   719    890   #endif /* SQLITE_OMIT_ANALYZE */

Changes to src/build.c.

  1986   1986   */
  1987   1987   static void sqlite3ClearStatTables(
  1988   1988     Parse *pParse,         /* The parsing context */
  1989   1989     int iDb,               /* The database number */
  1990   1990     const char *zType,     /* "idx" or "tbl" */
  1991   1991     const char *zName      /* Name of index or table */
  1992   1992   ){
  1993         -  static const char *azStatTab[] = { "sqlite_stat1", "sqlite_stat2" };
         1993  +  static const char *azStatTab[] = { 
         1994  +    "sqlite_stat1",
         1995  +    "sqlite_stat2",
         1996  +    "sqlite_stat3",
         1997  +  };
  1994   1998     int i;
  1995   1999     const char *zDbName = pParse->db->aDb[iDb].zName;
  1996   2000     for(i=0; i<ArraySize(azStatTab); i++){
  1997   2001       if( sqlite3FindTable(pParse->db, azStatTab[i], zDbName) ){
  1998   2002         sqlite3NestedParse(pParse,
  1999   2003           "DELETE FROM %Q.%s WHERE %s=%Q",
  2000   2004           zDbName, azStatTab[i], zType, zName
  2001   2005         );
  2002   2006       }
  2003   2007     }
         2008  +}
         2009  +
         2010  +/*
         2011  +** Generate code to drop a table.
         2012  +*/
         2013  +void sqlite3CodeDropTable(Parse *pParse, Table *pTab, int iDb, int isView){
         2014  +  Vdbe *v;
         2015  +  sqlite3 *db = pParse->db;
         2016  +  Trigger *pTrigger;
         2017  +  Db *pDb = &db->aDb[iDb];
         2018  +
         2019  +  v = sqlite3GetVdbe(pParse);
         2020  +  assert( v!=0 );
         2021  +  sqlite3BeginWriteOperation(pParse, 1, iDb);
         2022  +
         2023  +#ifndef SQLITE_OMIT_VIRTUALTABLE
         2024  +  if( IsVirtual(pTab) ){
         2025  +    sqlite3VdbeAddOp0(v, OP_VBegin);
         2026  +  }
         2027  +#endif
         2028  +
         2029  +  /* Drop all triggers associated with the table being dropped. Code
         2030  +  ** is generated to remove entries from sqlite_master and/or
         2031  +  ** sqlite_temp_master if required.
         2032  +  */
         2033  +  pTrigger = sqlite3TriggerList(pParse, pTab);
         2034  +  while( pTrigger ){
         2035  +    assert( pTrigger->pSchema==pTab->pSchema || 
         2036  +        pTrigger->pSchema==db->aDb[1].pSchema );
         2037  +    sqlite3DropTriggerPtr(pParse, pTrigger);
         2038  +    pTrigger = pTrigger->pNext;
         2039  +  }
         2040  +
         2041  +#ifndef SQLITE_OMIT_AUTOINCREMENT
         2042  +  /* Remove any entries of the sqlite_sequence table associated with
         2043  +  ** the table being dropped. This is done before the table is dropped
         2044  +  ** at the btree level, in case the sqlite_sequence table needs to
         2045  +  ** move as a result of the drop (can happen in auto-vacuum mode).
         2046  +  */
         2047  +  if( pTab->tabFlags & TF_Autoincrement ){
         2048  +    sqlite3NestedParse(pParse,
         2049  +      "DELETE FROM %Q.sqlite_sequence WHERE name=%Q",
         2050  +      pDb->zName, pTab->zName
         2051  +    );
         2052  +  }
         2053  +#endif
         2054  +
         2055  +  /* Drop all SQLITE_MASTER table and index entries that refer to the
         2056  +  ** table. The program name loops through the master table and deletes
         2057  +  ** every row that refers to a table of the same name as the one being
         2058  +  ** dropped. Triggers are handled seperately because a trigger can be
         2059  +  ** created in the temp database that refers to a table in another
         2060  +  ** database.
         2061  +  */
         2062  +  sqlite3NestedParse(pParse, 
         2063  +      "DELETE FROM %Q.%s WHERE tbl_name=%Q and type!='trigger'",
         2064  +      pDb->zName, SCHEMA_TABLE(iDb), pTab->zName);
         2065  +  sqlite3ClearStatTables(pParse, iDb, "tbl", pTab->zName);
         2066  +  if( !isView && !IsVirtual(pTab) ){
         2067  +    destroyTable(pParse, pTab);
         2068  +  }
         2069  +
         2070  +  /* Remove the table entry from SQLite's internal schema and modify
         2071  +  ** the schema cookie.
         2072  +  */
         2073  +  if( IsVirtual(pTab) ){
         2074  +    sqlite3VdbeAddOp4(v, OP_VDestroy, iDb, 0, 0, pTab->zName, 0);
         2075  +  }
         2076  +  sqlite3VdbeAddOp4(v, OP_DropTable, iDb, 0, 0, pTab->zName, 0);
         2077  +  sqlite3ChangeCookie(pParse, iDb);
         2078  +  sqliteViewResetAll(db, iDb);
         2079  +
  2004   2080   }
  2005   2081   
  2006   2082   /*
  2007   2083   ** This routine is called to do the work of a DROP TABLE statement.
  2008   2084   ** pName is the name of the table to be dropped.
  2009   2085   */
  2010   2086   void sqlite3DropTable(Parse *pParse, SrcList *pName, int isView, int noErr){
................................................................................
  2067   2143         goto exit_drop_table;
  2068   2144       }
  2069   2145       if( sqlite3AuthCheck(pParse, SQLITE_DELETE, pTab->zName, 0, zDb) ){
  2070   2146         goto exit_drop_table;
  2071   2147       }
  2072   2148     }
  2073   2149   #endif
  2074         -  if( sqlite3StrNICmp(pTab->zName, "sqlite_", 7)==0 ){
         2150  +  if( !pParse->nested && sqlite3StrNICmp(pTab->zName, "sqlite_", 7)==0 ){
  2075   2151       sqlite3ErrorMsg(pParse, "table %s may not be dropped", pTab->zName);
  2076   2152       goto exit_drop_table;
  2077   2153     }
  2078   2154   
  2079   2155   #ifndef SQLITE_OMIT_VIEW
  2080   2156     /* Ensure DROP TABLE is not used on a view, and DROP VIEW is not used
  2081   2157     ** on a table.
................................................................................
  2091   2167   #endif
  2092   2168   
  2093   2169     /* Generate code to remove the table from the master table
  2094   2170     ** on disk.
  2095   2171     */
  2096   2172     v = sqlite3GetVdbe(pParse);
  2097   2173     if( v ){
  2098         -    Trigger *pTrigger;
  2099         -    Db *pDb = &db->aDb[iDb];
  2100   2174       sqlite3BeginWriteOperation(pParse, 1, iDb);
  2101         -
  2102         -#ifndef SQLITE_OMIT_VIRTUALTABLE
  2103         -    if( IsVirtual(pTab) ){
  2104         -      sqlite3VdbeAddOp0(v, OP_VBegin);
  2105         -    }
  2106         -#endif
  2107   2175       sqlite3FkDropTable(pParse, pName, pTab);
  2108         -
  2109         -    /* Drop all triggers associated with the table being dropped. Code
  2110         -    ** is generated to remove entries from sqlite_master and/or
  2111         -    ** sqlite_temp_master if required.
  2112         -    */
  2113         -    pTrigger = sqlite3TriggerList(pParse, pTab);
  2114         -    while( pTrigger ){
  2115         -      assert( pTrigger->pSchema==pTab->pSchema || 
  2116         -          pTrigger->pSchema==db->aDb[1].pSchema );
  2117         -      sqlite3DropTriggerPtr(pParse, pTrigger);
  2118         -      pTrigger = pTrigger->pNext;
  2119         -    }
  2120         -
  2121         -#ifndef SQLITE_OMIT_AUTOINCREMENT
  2122         -    /* Remove any entries of the sqlite_sequence table associated with
  2123         -    ** the table being dropped. This is done before the table is dropped
  2124         -    ** at the btree level, in case the sqlite_sequence table needs to
  2125         -    ** move as a result of the drop (can happen in auto-vacuum mode).
  2126         -    */
  2127         -    if( pTab->tabFlags & TF_Autoincrement ){
  2128         -      sqlite3NestedParse(pParse,
  2129         -        "DELETE FROM %s.sqlite_sequence WHERE name=%Q",
  2130         -        pDb->zName, pTab->zName
  2131         -      );
  2132         -    }
  2133         -#endif
  2134         -
  2135         -    /* Drop all SQLITE_MASTER table and index entries that refer to the
  2136         -    ** table. The program name loops through the master table and deletes
  2137         -    ** every row that refers to a table of the same name as the one being
  2138         -    ** dropped. Triggers are handled seperately because a trigger can be
  2139         -    ** created in the temp database that refers to a table in another
  2140         -    ** database.
  2141         -    */
  2142         -    sqlite3NestedParse(pParse, 
  2143         -        "DELETE FROM %Q.%s WHERE tbl_name=%Q and type!='trigger'",
  2144         -        pDb->zName, SCHEMA_TABLE(iDb), pTab->zName);
  2145         -    sqlite3ClearStatTables(pParse, iDb, "tbl", pTab->zName);
  2146         -    if( !isView && !IsVirtual(pTab) ){
  2147         -      destroyTable(pParse, pTab);
  2148         -    }
  2149         -
  2150         -    /* Remove the table entry from SQLite's internal schema and modify
  2151         -    ** the schema cookie.
  2152         -    */
  2153         -    if( IsVirtual(pTab) ){
  2154         -      sqlite3VdbeAddOp4(v, OP_VDestroy, iDb, 0, 0, pTab->zName, 0);
  2155         -    }
  2156         -    sqlite3VdbeAddOp4(v, OP_DropTable, iDb, 0, 0, pTab->zName, 0);
  2157         -    sqlite3ChangeCookie(pParse, iDb);
         2176  +    sqlite3CodeDropTable(pParse, pTab, iDb, isView);
  2158   2177     }
  2159         -  sqliteViewResetAll(db, iDb);
  2160   2178   
  2161   2179   exit_drop_table:
  2162   2180     sqlite3SrcListDelete(db, pName);
  2163   2181   }
  2164   2182   
  2165   2183   /*
  2166   2184   ** This routine is called to create a new foreign key on the table
................................................................................
  2599   2617     /* 
  2600   2618     ** Allocate the index structure. 
  2601   2619     */
  2602   2620     nName = sqlite3Strlen30(zName);
  2603   2621     nCol = pList->nExpr;
  2604   2622     pIndex = sqlite3DbMallocZero(db, 
  2605   2623         sizeof(Index) +              /* Index structure  */
         2624  +      sizeof(tRowcnt)*(nCol+1) +   /* Index.aiRowEst   */
  2606   2625         sizeof(int)*nCol +           /* Index.aiColumn   */
  2607         -      sizeof(int)*(nCol+1) +       /* Index.aiRowEst   */
  2608   2626         sizeof(char *)*nCol +        /* Index.azColl     */
  2609   2627         sizeof(u8)*nCol +            /* Index.aSortOrder */
  2610   2628         nName + 1 +                  /* Index.zName      */
  2611   2629         nExtra                       /* Collation sequence names */
  2612   2630     );
  2613   2631     if( db->mallocFailed ){
  2614   2632       goto exit_create_index;
  2615   2633     }
  2616         -  pIndex->azColl = (char**)(&pIndex[1]);
         2634  +  pIndex->aiRowEst = (tRowcnt*)(&pIndex[1]);
         2635  +  pIndex->azColl = (char**)(&pIndex->aiRowEst[nCol+1]);
  2617   2636     pIndex->aiColumn = (int *)(&pIndex->azColl[nCol]);
  2618         -  pIndex->aiRowEst = (unsigned *)(&pIndex->aiColumn[nCol]);
  2619         -  pIndex->aSortOrder = (u8 *)(&pIndex->aiRowEst[nCol+1]);
         2637  +  pIndex->aSortOrder = (u8 *)(&pIndex->aiColumn[nCol]);
  2620   2638     pIndex->zName = (char *)(&pIndex->aSortOrder[nCol]);
  2621   2639     zExtra = (char *)(&pIndex->zName[nName+1]);
  2622   2640     memcpy(pIndex->zName, zName, nName+1);
  2623   2641     pIndex->pTable = pTab;
  2624   2642     pIndex->nColumn = pList->nExpr;
  2625   2643     pIndex->onError = (u8)onError;
  2626   2644     pIndex->autoIndex = (u8)(pName==0);
................................................................................
  2889   2907   **           aiRowEst[N]>=1
  2890   2908   **
  2891   2909   ** Apart from that, we have little to go on besides intuition as to
  2892   2910   ** how aiRowEst[] should be initialized.  The numbers generated here
  2893   2911   ** are based on typical values found in actual indices.
  2894   2912   */
  2895   2913   void sqlite3DefaultRowEst(Index *pIdx){
  2896         -  unsigned *a = pIdx->aiRowEst;
         2914  +  tRowcnt *a = pIdx->aiRowEst;
  2897   2915     int i;
  2898         -  unsigned n;
         2916  +  tRowcnt n;
  2899   2917     assert( a!=0 );
  2900   2918     a[0] = pIdx->pTable->nRowEst;
  2901   2919     if( a[0]<10 ) a[0] = 10;
  2902   2920     n = 10;
  2903   2921     for(i=1; i<=pIdx->nColumn; i++){
  2904   2922       a[i] = n;
  2905   2923       if( n>5 ) n--;

Changes to src/ctime.c.

   112    112     "ENABLE_OVERSIZE_CELL_CHECK",
   113    113   #endif
   114    114   #ifdef SQLITE_ENABLE_RTREE
   115    115     "ENABLE_RTREE",
   116    116   #endif
   117    117   #ifdef SQLITE_ENABLE_STAT2
   118    118     "ENABLE_STAT2",
          119  +#endif
          120  +#ifdef SQLITE_ENABLE_STAT3
          121  +  "ENABLE_STAT3",
   119    122   #endif
   120    123   #ifdef SQLITE_ENABLE_UNLOCK_NOTIFY
   121    124     "ENABLE_UNLOCK_NOTIFY",
   122    125   #endif
   123    126   #ifdef SQLITE_ENABLE_UPDATE_DELETE_LIMIT
   124    127     "ENABLE_UPDATE_DELETE_LIMIT",
   125    128   #endif

Changes to src/sqlite.h.in.

  2847   2847   ** WHERE clause might influence the choice of query plan for a statement,
  2848   2848   ** then the statement will be automatically recompiled, as if there had been 
  2849   2849   ** a schema change, on the first  [sqlite3_step()] call following any change
  2850   2850   ** to the [sqlite3_bind_text | bindings] of that [parameter]. 
  2851   2851   ** ^The specific value of WHERE-clause [parameter] might influence the 
  2852   2852   ** choice of query plan if the parameter is the left-hand side of a [LIKE]
  2853   2853   ** or [GLOB] operator or if the parameter is compared to an indexed column
  2854         -** and the [SQLITE_ENABLE_STAT2] compile-time option is enabled.
         2854  +** and the [SQLITE_ENABLE_STAT3] compile-time option is enabled.
  2855   2855   ** the 
  2856   2856   ** </li>
  2857   2857   ** </ol>
  2858   2858   */
  2859   2859   int sqlite3_prepare(
  2860   2860     sqlite3 *db,            /* Database handle */
  2861   2861     const char *zSql,       /* SQL statement, UTF-8 encoded */

Changes to src/sqliteInt.h.

   441    441   ** SQLITE_MAX_U32 is a u64 constant that is the maximum u64 value
   442    442   ** that can be stored in a u32 without loss of data.  The value
   443    443   ** is 0x00000000ffffffff.  But because of quirks of some compilers, we
   444    444   ** have to specify the value in the less intuitive manner shown:
   445    445   */
   446    446   #define SQLITE_MAX_U32  ((((u64)1)<<32)-1)
   447    447   
          448  +/*
          449  +** The datatype used to store estimates of the number of rows in a
          450  +** table or index.  This is an unsigned integer type.  For 99.9% of
          451  +** the world, a 32-bit integer is sufficient.  But a 64-bit integer
          452  +** can be used at compile-time if desired.
          453  +*/
          454  +#ifdef SQLITE_64BIT_STATS
          455  + typedef u64 tRowcnt;    /* 64-bit only if requested at compile-time */
          456  +#else
          457  + typedef u32 tRowcnt;    /* 32-bit is the default */
          458  +#endif
          459  +
   448    460   /*
   449    461   ** Macros to determine whether the machine is big or little endian,
   450    462   ** evaluated at runtime.
   451    463   */
   452    464   #ifdef SQLITE_AMALGAMATION
   453    465   const int sqlite3one = 1;
   454    466   #else
................................................................................
  1274   1286   struct Table {
  1275   1287     char *zName;         /* Name of the table or view */
  1276   1288     int iPKey;           /* If not negative, use aCol[iPKey] as the primary key */
  1277   1289     int nCol;            /* Number of columns in this table */
  1278   1290     Column *aCol;        /* Information about each column */
  1279   1291     Index *pIndex;       /* List of SQL indexes on this table. */
  1280   1292     int tnum;            /* Root BTree node for this table (see note above) */
  1281         -  unsigned nRowEst;    /* Estimated rows in table - from sqlite_stat1 table */
         1293  +  tRowcnt nRowEst;     /* Estimated rows in table - from sqlite_stat1 table */
  1282   1294     Select *pSelect;     /* NULL for tables.  Points to definition if a view. */
  1283   1295     u16 nRef;            /* Number of pointers to this Table */
  1284   1296     u8 tabFlags;         /* Mask of TF_* values */
  1285   1297     u8 keyConf;          /* What to do in case of uniqueness conflict on iPKey */
  1286   1298     FKey *pFKey;         /* Linked list of all foreign keys in this table */
  1287   1299     char *zColAff;       /* String defining the affinity of each column */
  1288   1300   #ifndef SQLITE_OMIT_CHECK
................................................................................
  1473   1485   ** algorithm to employ whenever an attempt is made to insert a non-unique
  1474   1486   ** element.
  1475   1487   */
  1476   1488   struct Index {
  1477   1489     char *zName;     /* Name of this index */
  1478   1490     int nColumn;     /* Number of columns in the table used by this index */
  1479   1491     int *aiColumn;   /* Which columns are used by this index.  1st is 0 */
  1480         -  unsigned *aiRowEst; /* Result of ANALYZE: Est. rows selected by each column */
         1492  +  tRowcnt *aiRowEst; /* Result of ANALYZE: Est. rows selected by each column */
  1481   1493     Table *pTable;   /* The SQL table being indexed */
  1482   1494     int tnum;        /* Page containing root of this index in database file */
  1483   1495     u8 onError;      /* OE_Abort, OE_Ignore, OE_Replace, or OE_None */
  1484   1496     u8 autoIndex;    /* True if is automatically created (ex: by UNIQUE) */
  1485   1497     u8 bUnordered;   /* Use this index for == or IN queries only */
         1498  +  u8 nSample;      /* Number of elements in aSample[] */
  1486   1499     char *zColAff;   /* String defining the affinity of each column */
  1487   1500     Index *pNext;    /* The next index associated with the same table */
  1488   1501     Schema *pSchema; /* Schema containing this index */
  1489   1502     u8 *aSortOrder;  /* Array of size Index.nColumn. True==DESC, False==ASC */
  1490   1503     char **azColl;   /* Array of collation sequence names for index */
  1491         -  IndexSample *aSample;    /* Array of SQLITE_INDEX_SAMPLES samples */
         1504  +#ifdef SQLITE_ENABLE_STAT3
         1505  +  IndexSample *aSample;    /* Samples of the left-most key */
         1506  +#endif
  1492   1507   };
  1493   1508   
  1494   1509   /*
  1495   1510   ** Each sample stored in the sqlite_stat2 table is represented in memory 
  1496   1511   ** using a structure of this type.
  1497   1512   */
  1498   1513   struct IndexSample {
  1499   1514     union {
  1500   1515       char *z;        /* Value if eType is SQLITE_TEXT or SQLITE_BLOB */
  1501         -    double r;       /* Value if eType is SQLITE_FLOAT or SQLITE_INTEGER */
         1516  +    double r;       /* Value if eType is SQLITE_FLOAT */
         1517  +    i64 i;          /* Value if eType is SQLITE_INTEGER */
  1502   1518     } u;
  1503   1519     u8 eType;         /* SQLITE_NULL, SQLITE_INTEGER ... etc. */
  1504         -  u8 nByte;         /* Size in byte of text or blob. */
         1520  +  u16 nByte;        /* Size in byte of text or blob. */
         1521  +  tRowcnt nEq;      /* Est. number of rows where the key equals this sample */
         1522  +  tRowcnt nLt;      /* Est. number of rows where key is less than this sample */
  1505   1523   };
  1506   1524   
  1507   1525   /*
  1508   1526   ** Each token coming out of the lexer is an instance of
  1509   1527   ** this structure.  Tokens are also used as part of an expression.
  1510   1528   **
  1511   1529   ** Note if Token.z==0 then Token.dyn and Token.n are undefined and
................................................................................
  2703   2721   #if !defined(SQLITE_OMIT_VIEW) || !defined(SQLITE_OMIT_VIRTUALTABLE)
  2704   2722     int sqlite3ViewGetColumnNames(Parse*,Table*);
  2705   2723   #else
  2706   2724   # define sqlite3ViewGetColumnNames(A,B) 0
  2707   2725   #endif
  2708   2726   
  2709   2727   void sqlite3DropTable(Parse*, SrcList*, int, int);
         2728  +void sqlite3CodeDropTable(Parse*, Table*, int, int);
  2710   2729   void sqlite3DeleteTable(sqlite3*, Table*);
  2711   2730   #ifndef SQLITE_OMIT_AUTOINCREMENT
  2712   2731     void sqlite3AutoincrementBegin(Parse *pParse);
  2713   2732     void sqlite3AutoincrementEnd(Parse *pParse);
  2714   2733   #else
  2715   2734   # define sqlite3AutoincrementBegin(X)
  2716   2735   # define sqlite3AutoincrementEnd(X)
................................................................................
  2959   2978   const void *sqlite3ValueText(sqlite3_value*, u8);
  2960   2979   int sqlite3ValueBytes(sqlite3_value*, u8);
  2961   2980   void sqlite3ValueSetStr(sqlite3_value*, int, const void *,u8, 
  2962   2981                           void(*)(void*));
  2963   2982   void sqlite3ValueFree(sqlite3_value*);
  2964   2983   sqlite3_value *sqlite3ValueNew(sqlite3 *);
  2965   2984   char *sqlite3Utf16to8(sqlite3 *, const void*, int, u8);
  2966         -#ifdef SQLITE_ENABLE_STAT2
         2985  +#ifdef SQLITE_ENABLE_STAT3
  2967   2986   char *sqlite3Utf8to16(sqlite3 *, u8, char *, int, int *);
  2968   2987   #endif
  2969   2988   int sqlite3ValueFromExpr(sqlite3 *, Expr *, u8, u8, sqlite3_value **);
  2970   2989   void sqlite3ValueApplyAffinity(sqlite3_value *, u8, u8);
  2971   2990   #ifndef SQLITE_AMALGAMATION
  2972   2991   extern const unsigned char sqlite3OpcodeProperty[];
  2973   2992   extern const unsigned char sqlite3UpperToLower[];

Changes to src/test_config.c.

   413    413   #endif
   414    414   
   415    415   #ifdef SQLITE_ENABLE_STAT2
   416    416     Tcl_SetVar2(interp, "sqlite_options", "stat2", "1", TCL_GLOBAL_ONLY);
   417    417   #else
   418    418     Tcl_SetVar2(interp, "sqlite_options", "stat2", "0", TCL_GLOBAL_ONLY);
   419    419   #endif
          420  +
          421  +#ifdef SQLITE_ENABLE_STAT3
          422  +  Tcl_SetVar2(interp, "sqlite_options", "stat3", "1", TCL_GLOBAL_ONLY);
          423  +#else
          424  +  Tcl_SetVar2(interp, "sqlite_options", "stat3", "0", TCL_GLOBAL_ONLY);
          425  +#endif
   420    426   
   421    427   #if !defined(SQLITE_ENABLE_LOCKING_STYLE)
   422    428   #  if defined(__APPLE__)
   423    429   #    define SQLITE_ENABLE_LOCKING_STYLE 1
   424    430   #  else
   425    431   #    define SQLITE_ENABLE_LOCKING_STYLE 0
   426    432   #  endif

Changes to src/utf.c.

   460    460   ** is set to the length of the returned string in bytes. The call should
   461    461   ** arrange to call sqlite3DbFree() on the returned pointer when it is
   462    462   ** no longer required.
   463    463   ** 
   464    464   ** If a malloc failure occurs, NULL is returned and the db.mallocFailed
   465    465   ** flag set.
   466    466   */
   467         -#ifdef SQLITE_ENABLE_STAT2
          467  +#ifdef SQLITE_ENABLE_STAT3
   468    468   char *sqlite3Utf8to16(sqlite3 *db, u8 enc, char *z, int n, int *pnOut){
   469    469     Mem m;
   470    470     memset(&m, 0, sizeof(m));
   471    471     m.db = db;
   472    472     sqlite3VdbeMemSetStr(&m, z, n, SQLITE_UTF8, SQLITE_STATIC);
   473    473     if( sqlite3VdbeMemTranslate(&m, enc) ){
   474    474       assert( db->mallocFailed );

Changes to src/vdbemem.c.

  1028   1028   
  1029   1029     if( !pExpr ){
  1030   1030       *ppVal = 0;
  1031   1031       return SQLITE_OK;
  1032   1032     }
  1033   1033     op = pExpr->op;
  1034   1034   
  1035         -  /* op can only be TK_REGISTER if we have compiled with SQLITE_ENABLE_STAT2.
         1035  +  /* op can only be TK_REGISTER if we have compiled with SQLITE_ENABLE_STAT3.
  1036   1036     ** The ifdef here is to enable us to achieve 100% branch test coverage even
  1037         -  ** when SQLITE_ENABLE_STAT2 is omitted.
         1037  +  ** when SQLITE_ENABLE_STAT3 is omitted.
  1038   1038     */
  1039         -#ifdef SQLITE_ENABLE_STAT2
         1039  +#ifdef SQLITE_ENABLE_STAT3
  1040   1040     if( op==TK_REGISTER ) op = pExpr->op2;
  1041   1041   #else
  1042   1042     if( NEVER(op==TK_REGISTER) ) op = pExpr->op2;
  1043   1043   #endif
  1044   1044   
  1045   1045     /* Handle negative integers in a single step.  This is needed in the
  1046   1046     ** case when the value is -9223372036854775808.

Changes to src/where.c.

   114    114   #define TERM_DYNAMIC    0x01   /* Need to call sqlite3ExprDelete(db, pExpr) */
   115    115   #define TERM_VIRTUAL    0x02   /* Added by the optimizer.  Do not code */
   116    116   #define TERM_CODED      0x04   /* This term is already coded */
   117    117   #define TERM_COPIED     0x08   /* Has a child */
   118    118   #define TERM_ORINFO     0x10   /* Need to free the WhereTerm.u.pOrInfo object */
   119    119   #define TERM_ANDINFO    0x20   /* Need to free the WhereTerm.u.pAndInfo obj */
   120    120   #define TERM_OR_OK      0x40   /* Used during OR-clause processing */
   121         -#ifdef SQLITE_ENABLE_STAT2
          121  +#ifdef SQLITE_ENABLE_STAT3
   122    122   #  define TERM_VNULL    0x80   /* Manufactured x>NULL or x<=NULL term */
   123    123   #else
   124    124   #  define TERM_VNULL    0x00   /* Disabled if not using stat2 */
   125    125   #endif
   126    126   
   127    127   /*
   128    128   ** An instance of the following structure holds all information about a
................................................................................
  1328   1328         pTerm->nChild = 1;
  1329   1329         pTerm->wtFlags |= TERM_COPIED;
  1330   1330         pNewTerm->prereqAll = pTerm->prereqAll;
  1331   1331       }
  1332   1332     }
  1333   1333   #endif /* SQLITE_OMIT_VIRTUALTABLE */
  1334   1334   
  1335         -#ifdef SQLITE_ENABLE_STAT2
         1335  +#ifdef SQLITE_ENABLE_STAT3
  1336   1336     /* When sqlite_stat2 histogram data is available an operator of the
  1337   1337     ** form "x IS NOT NULL" can sometimes be evaluated more efficiently
  1338   1338     ** as "x>NULL" if x is not an INTEGER PRIMARY KEY.  So construct a
  1339   1339     ** virtual term of that form.
  1340   1340     **
  1341   1341     ** Note that the virtual term must be tagged with TERM_VNULL.  This
  1342   1342     ** TERM_VNULL tag will suppress the not-null check at the beginning
................................................................................
  1367   1367         pNewTerm->iParent = idxTerm;
  1368   1368         pTerm = &pWC->a[idxTerm];
  1369   1369         pTerm->nChild = 1;
  1370   1370         pTerm->wtFlags |= TERM_COPIED;
  1371   1371         pNewTerm->prereqAll = pTerm->prereqAll;
  1372   1372       }
  1373   1373     }
  1374         -#endif /* SQLITE_ENABLE_STAT2 */
         1374  +#endif /* SQLITE_ENABLE_STAT */
  1375   1375   
  1376   1376     /* Prevent ON clause terms of a LEFT JOIN from being used to drive
  1377   1377     ** an index for tables to the left of the join.
  1378   1378     */
  1379   1379     pTerm->prereqRight |= extraRight;
  1380   1380   }
  1381   1381   
................................................................................
  2416   2416     /* Try to find a more efficient access pattern by using multiple indexes
  2417   2417     ** to optimize an OR expression within the WHERE clause. 
  2418   2418     */
  2419   2419     bestOrClauseIndex(pParse, pWC, pSrc, notReady, notValid, pOrderBy, pCost);
  2420   2420   }
  2421   2421   #endif /* SQLITE_OMIT_VIRTUALTABLE */
  2422   2422   
         2423  +#ifdef SQLITE_ENABLE_STAT3
  2423   2424   /*
  2424         -** Argument pIdx is a pointer to an index structure that has an array of
  2425         -** SQLITE_INDEX_SAMPLES evenly spaced samples of the first indexed column
  2426         -** stored in Index.aSample. These samples divide the domain of values stored
  2427         -** the index into (SQLITE_INDEX_SAMPLES+1) regions.
  2428         -** Region 0 contains all values less than the first sample value. Region
  2429         -** 1 contains values between the first and second samples.  Region 2 contains
  2430         -** values between samples 2 and 3.  And so on.  Region SQLITE_INDEX_SAMPLES
  2431         -** contains values larger than the last sample.
         2425  +** Estimate the location of a particular key among all keys in an
         2426  +** index.  Store the results in aStat as follows:
  2432   2427   **
  2433         -** If the index contains many duplicates of a single value, then it is
  2434         -** possible that two or more adjacent samples can hold the same value.
  2435         -** When that is the case, the smallest possible region code is returned
  2436         -** when roundUp is false and the largest possible region code is returned
  2437         -** when roundUp is true.
         2428  +**    aStat[0]      Est. number of rows less than pVal
         2429  +**    aStat[1]      Est. number of rows equal to pVal
  2438   2430   **
  2439         -** If successful, this function determines which of the regions value 
  2440         -** pVal lies in, sets *piRegion to the region index (a value between 0
  2441         -** and SQLITE_INDEX_SAMPLES+1, inclusive) and returns SQLITE_OK.
  2442         -** Or, if an OOM occurs while converting text values between encodings,
  2443         -** SQLITE_NOMEM is returned and *piRegion is undefined.
         2431  +** Return SQLITE_OK on success.
  2444   2432   */
  2445         -#ifdef SQLITE_ENABLE_STAT2
  2446         -static int whereRangeRegion(
         2433  +static int whereKeyStats(
  2447   2434     Parse *pParse,              /* Database connection */
  2448   2435     Index *pIdx,                /* Index to consider domain of */
  2449   2436     sqlite3_value *pVal,        /* Value to consider */
  2450         -  int roundUp,                /* Return largest valid region if true */
  2451         -  int *piRegion               /* OUT: Region of domain in which value lies */
         2437  +  int roundUp,                /* Round up if true.  Round down if false */
         2438  +  tRowcnt *aStat              /* OUT: stats written here */
  2452   2439   ){
         2440  +  tRowcnt n;
         2441  +  IndexSample *aSample;
         2442  +  int i, eType;
         2443  +  int isEq = 0;
         2444  +
  2453   2445     assert( roundUp==0 || roundUp==1 );
  2454         -  if( ALWAYS(pVal) ){
  2455         -    IndexSample *aSample = pIdx->aSample;
  2456         -    int i = 0;
  2457         -    int eType = sqlite3_value_type(pVal);
  2458         -
  2459         -    if( eType==SQLITE_INTEGER || eType==SQLITE_FLOAT ){
  2460         -      double r = sqlite3_value_double(pVal);
  2461         -      for(i=0; i<SQLITE_INDEX_SAMPLES; i++){
  2462         -        if( aSample[i].eType==SQLITE_NULL ) continue;
  2463         -        if( aSample[i].eType>=SQLITE_TEXT ) break;
  2464         -        if( roundUp ){
  2465         -          if( aSample[i].u.r>r ) break;
  2466         -        }else{
  2467         -          if( aSample[i].u.r>=r ) break;
  2468         -        }
  2469         -      }
  2470         -    }else if( eType==SQLITE_NULL ){
  2471         -      i = 0;
  2472         -      if( roundUp ){
  2473         -        while( i<SQLITE_INDEX_SAMPLES && aSample[i].eType==SQLITE_NULL ) i++;
  2474         -      }
  2475         -    }else{ 
         2446  +  if( pVal==0 ) return SQLITE_ERROR;
         2447  +  n = pIdx->aiRowEst[0];
         2448  +  aSample = pIdx->aSample;
         2449  +  i = 0;
         2450  +  eType = sqlite3_value_type(pVal);
         2451  +
         2452  +  if( eType==SQLITE_INTEGER ){
         2453  +    i64 v = sqlite3_value_int64(pVal);
         2454  +    for(i=0; i<pIdx->nSample; i++){
         2455  +      if( aSample[i].eType==SQLITE_NULL ) continue;
         2456  +      if( aSample[i].eType>=SQLITE_TEXT ) break;
         2457  +      if( aSample[i].u.i>=v ){
         2458  +        isEq = aSample[i].u.i==v;
         2459  +        break;
         2460  +      }
         2461  +    }
         2462  +  }else if( eType==SQLITE_FLOAT ){
         2463  +    double r = sqlite3_value_double(pVal);
         2464  +    for(i=0; i<pIdx->nSample; i++){
         2465  +      if( aSample[i].eType==SQLITE_NULL ) continue;
         2466  +      if( aSample[i].eType>=SQLITE_TEXT ) break;
         2467  +      if( aSample[i].u.r>=r ){
         2468  +        isEq = aSample[i].u.r==r;
         2469  +        break;
         2470  +      }
         2471  +    }
         2472  +  }else if( eType==SQLITE_NULL ){
         2473  +    i = 0;
         2474  +    if( pIdx->nSample>=1 && aSample[0].eType==SQLITE_NULL ) isEq = 1;
         2475  +  }else{
         2476  +    assert( eType==SQLITE_TEXT || eType==SQLITE_BLOB );
         2477  +    for(i=0; i<pIdx->nSample; i++){
         2478  +      if( aSample[i].eType==SQLITE_TEXT || aSample[i].eType==SQLITE_BLOB ){
         2479  +        break;
         2480  +      }
         2481  +    }
         2482  +    if( i<pIdx->nSample ){      
  2476   2483         sqlite3 *db = pParse->db;
  2477   2484         CollSeq *pColl;
  2478   2485         const u8 *z;
  2479   2486         int n;
  2480         -
  2481         -      /* pVal comes from sqlite3ValueFromExpr() so the type cannot be NULL */
  2482         -      assert( eType==SQLITE_TEXT || eType==SQLITE_BLOB );
  2483         -
  2484   2487         if( eType==SQLITE_BLOB ){
  2485   2488           z = (const u8 *)sqlite3_value_blob(pVal);
  2486   2489           pColl = db->pDfltColl;
  2487   2490           assert( pColl->enc==SQLITE_UTF8 );
  2488   2491         }else{
  2489   2492           pColl = sqlite3GetCollSeq(db, SQLITE_UTF8, 0, *pIdx->azColl);
  2490   2493           if( pColl==0 ){
................................................................................
  2495   2498           z = (const u8 *)sqlite3ValueText(pVal, pColl->enc);
  2496   2499           if( !z ){
  2497   2500             return SQLITE_NOMEM;
  2498   2501           }
  2499   2502           assert( z && pColl && pColl->xCmp );
  2500   2503         }
  2501   2504         n = sqlite3ValueBytes(pVal, pColl->enc);
  2502         -
  2503         -      for(i=0; i<SQLITE_INDEX_SAMPLES; i++){
         2505  +  
         2506  +      for(; i<pIdx->nSample; i++){
  2504   2507           int c;
  2505   2508           int eSampletype = aSample[i].eType;
  2506         -        if( eSampletype==SQLITE_NULL || eSampletype<eType ) continue;
  2507         -        if( (eSampletype!=eType) ) break;
         2509  +        if( eSampletype<eType ) continue;
         2510  +        if( eSampletype!=eType ) break;
  2508   2511   #ifndef SQLITE_OMIT_UTF16
  2509   2512           if( pColl->enc!=SQLITE_UTF8 ){
  2510   2513             int nSample;
  2511   2514             char *zSample = sqlite3Utf8to16(
  2512   2515                 db, pColl->enc, aSample[i].u.z, aSample[i].nByte, &nSample
  2513   2516             );
  2514   2517             if( !zSample ){
................................................................................
  2518   2521             c = pColl->xCmp(pColl->pUser, nSample, zSample, n, z);
  2519   2522             sqlite3DbFree(db, zSample);
  2520   2523           }else
  2521   2524   #endif
  2522   2525           {
  2523   2526             c = pColl->xCmp(pColl->pUser, aSample[i].nByte, aSample[i].u.z, n, z);
  2524   2527           }
  2525         -        if( c-roundUp>=0 ) break;
         2528  +        if( c>=0 ){
         2529  +          if( c==0 ) isEq = 1;
         2530  +          break;
         2531  +        }
  2526   2532         }
  2527   2533       }
         2534  +  }
  2528   2535   
  2529         -    assert( i>=0 && i<=SQLITE_INDEX_SAMPLES );
  2530         -    *piRegion = i;
         2536  +  /* At this point, aSample[i] is the first sample that is greater than
         2537  +  ** or equal to pVal.  Or if i==pIdx->nSample, then all samples are less
         2538  +  ** than pVal.  If aSample[i]==pVal, then isEq==1.
         2539  +  */
         2540  +  if( isEq ){
         2541  +    assert( i<pIdx->nSample );
         2542  +    aStat[0] = aSample[i].nLt;
         2543  +    aStat[1] = aSample[i].nEq;
         2544  +  }else{
         2545  +    tRowcnt iLower, iUpper, iGap;
         2546  +    if( i==0 ){
         2547  +      iLower = 0;
         2548  +      iUpper = aSample[0].nLt;
         2549  +    }else if( i>=pIdx->nSample ){
         2550  +      iUpper = n;
         2551  +      iLower = aSample[i].nEq + aSample[i].nLt;
         2552  +    }else{
         2553  +      iLower = aSample[i-1].nEq + aSample[i-1].nLt;
         2554  +      iUpper = aSample[i].nLt;
         2555  +    }
         2556  +    aStat[1] = pIdx->aiRowEst[1];
         2557  +    if( iLower>=iUpper ){
         2558  +      iGap = 0;
         2559  +    }else{
         2560  +      iGap = iUpper - iLower;
         2561  +      if( iGap>=aStat[1]/2 ) iGap -= aStat[1]/2;
         2562  +    }
         2563  +    if( roundUp ){
         2564  +      iGap = (iGap*2)/3;
         2565  +    }else{
         2566  +      iGap = iGap/3;
         2567  +    }
         2568  +    aStat[0] = iLower + iGap;
  2531   2569     }
  2532   2570     return SQLITE_OK;
  2533   2571   }
  2534         -#endif   /* #ifdef SQLITE_ENABLE_STAT2 */
         2572  +#endif /* SQLITE_ENABLE_STAT3 */
  2535   2573   
  2536   2574   /*
  2537   2575   ** If expression pExpr represents a literal value, set *pp to point to
  2538   2576   ** an sqlite3_value structure containing the same value, with affinity
  2539   2577   ** aff applied to it, before returning. It is the responsibility of the 
  2540   2578   ** caller to eventually release this structure by passing it to 
  2541   2579   ** sqlite3ValueFree().
................................................................................
  2545   2583   ** create an sqlite3_value structure containing this value, again with
  2546   2584   ** affinity aff applied to it, instead.
  2547   2585   **
  2548   2586   ** If neither of the above apply, set *pp to NULL.
  2549   2587   **
  2550   2588   ** If an error occurs, return an error code. Otherwise, SQLITE_OK.
  2551   2589   */
  2552         -#ifdef SQLITE_ENABLE_STAT2
         2590  +#ifdef SQLITE_ENABLE_STAT3
  2553   2591   static int valueFromExpr(
  2554   2592     Parse *pParse, 
  2555   2593     Expr *pExpr, 
  2556   2594     u8 aff, 
  2557   2595     sqlite3_value **pp
  2558   2596   ){
  2559   2597     if( pExpr->op==TK_VARIABLE
................................................................................
  2593   2631   ** then nEq should be passed the value 1 (as the range restricted column,
  2594   2632   ** b, is the second left-most column of the index). Or, if the query is:
  2595   2633   **
  2596   2634   **   ... FROM t1 WHERE a > ? AND a < ? ...
  2597   2635   **
  2598   2636   ** then nEq should be passed 0.
  2599   2637   **
  2600         -** The returned value is an integer between 1 and 100, inclusive. A return
  2601         -** value of 1 indicates that the proposed range scan is expected to visit
  2602         -** approximately 1/100th (1%) of the rows selected by the nEq equality
  2603         -** constraints (if any). A return value of 100 indicates that it is expected
  2604         -** that the range scan will visit every row (100%) selected by the equality
  2605         -** constraints.
         2638  +** The returned value is an integer divisor to reduce the estimated
         2639  +** search space.  A return value of 1 means that range constraints are
         2640  +** no help at all.  A return value of 2 means range constraints are
         2641  +** expected to reduce the search space by half.  And so forth...
  2606   2642   **
  2607         -** In the absence of sqlite_stat2 ANALYZE data, each range inequality
  2608         -** reduces the search space by 3/4ths.  Hence a single constraint (x>?)
  2609         -** results in a return of 25 and a range constraint (x>? AND x<?) results
  2610         -** in a return of 6.
         2643  +** In the absence of sqlite_stat3 ANALYZE data, each range inequality
         2644  +** reduces the search space by a factor of 4.  Hence a single constraint (x>?)
         2645  +** results in a return of 4 and a range constraint (x>? AND x<?) results
         2646  +** in a return of 16.
  2611   2647   */
  2612   2648   static int whereRangeScanEst(
  2613   2649     Parse *pParse,       /* Parsing & code generating context */
  2614   2650     Index *p,            /* The index containing the range-compared column; "x" */
  2615   2651     int nEq,             /* index into p->aCol[] of the range-compared column */
  2616   2652     WhereTerm *pLower,   /* Lower bound on the range. ex: "x>123" Might be NULL */
  2617   2653     WhereTerm *pUpper,   /* Upper bound on the range. ex: "x<455" Might be NULL */
  2618         -  int *piEst           /* OUT: Return value */
         2654  +  tRowcnt *pRangeDiv   /* OUT: Reduce search space by this divisor */
  2619   2655   ){
  2620   2656     int rc = SQLITE_OK;
  2621   2657   
  2622         -#ifdef SQLITE_ENABLE_STAT2
         2658  +#ifdef SQLITE_ENABLE_STAT3
  2623   2659   
  2624         -  if( nEq==0 && p->aSample ){
  2625         -    sqlite3_value *pLowerVal = 0;
  2626         -    sqlite3_value *pUpperVal = 0;
  2627         -    int iEst;
  2628         -    int iLower = 0;
  2629         -    int iUpper = SQLITE_INDEX_SAMPLES;
  2630         -    int roundUpUpper = 0;
  2631         -    int roundUpLower = 0;
         2660  +  if( nEq==0 && p->nSample ){
         2661  +    sqlite3_value *pRangeVal;
         2662  +    tRowcnt iLower = 0;
         2663  +    tRowcnt iUpper = p->aiRowEst[0];
         2664  +    tRowcnt a[2];
  2632   2665       u8 aff = p->pTable->aCol[p->aiColumn[0]].affinity;
  2633   2666   
  2634   2667       if( pLower ){
  2635   2668         Expr *pExpr = pLower->pExpr->pRight;
  2636         -      rc = valueFromExpr(pParse, pExpr, aff, &pLowerVal);
         2669  +      rc = valueFromExpr(pParse, pExpr, aff, &pRangeVal);
  2637   2670         assert( pLower->eOperator==WO_GT || pLower->eOperator==WO_GE );
  2638         -      roundUpLower = (pLower->eOperator==WO_GT) ?1:0;
         2671  +      if( rc==SQLITE_OK
         2672  +       && whereKeyStats(pParse, p, pRangeVal, 0, a)==SQLITE_OK
         2673  +      ){
         2674  +        iLower = a[0];
         2675  +        if( pLower->eOperator==WO_GT ) iLower += a[1];
         2676  +      }
         2677  +      sqlite3ValueFree(pRangeVal);
  2639   2678       }
  2640   2679       if( rc==SQLITE_OK && pUpper ){
  2641   2680         Expr *pExpr = pUpper->pExpr->pRight;
  2642         -      rc = valueFromExpr(pParse, pExpr, aff, &pUpperVal);
         2681  +      rc = valueFromExpr(pParse, pExpr, aff, &pRangeVal);
  2643   2682         assert( pUpper->eOperator==WO_LT || pUpper->eOperator==WO_LE );
  2644         -      roundUpUpper = (pUpper->eOperator==WO_LE) ?1:0;
  2645         -    }
  2646         -
  2647         -    if( rc!=SQLITE_OK || (pLowerVal==0 && pUpperVal==0) ){
  2648         -      sqlite3ValueFree(pLowerVal);
  2649         -      sqlite3ValueFree(pUpperVal);
  2650         -      goto range_est_fallback;
  2651         -    }else if( pLowerVal==0 ){
  2652         -      rc = whereRangeRegion(pParse, p, pUpperVal, roundUpUpper, &iUpper);
  2653         -      if( pLower ) iLower = iUpper/2;
  2654         -    }else if( pUpperVal==0 ){
  2655         -      rc = whereRangeRegion(pParse, p, pLowerVal, roundUpLower, &iLower);
  2656         -      if( pUpper ) iUpper = (iLower + SQLITE_INDEX_SAMPLES + 1)/2;
  2657         -    }else{
  2658         -      rc = whereRangeRegion(pParse, p, pUpperVal, roundUpUpper, &iUpper);
  2659         -      if( rc==SQLITE_OK ){
  2660         -        rc = whereRangeRegion(pParse, p, pLowerVal, roundUpLower, &iLower);
  2661         -      }
  2662         -    }
  2663         -    WHERETRACE(("range scan regions: %d..%d\n", iLower, iUpper));
  2664         -
  2665         -    iEst = iUpper - iLower;
  2666         -    testcase( iEst==SQLITE_INDEX_SAMPLES );
  2667         -    assert( iEst<=SQLITE_INDEX_SAMPLES );
  2668         -    if( iEst<1 ){
  2669         -      *piEst = 50/SQLITE_INDEX_SAMPLES;
  2670         -    }else{
  2671         -      *piEst = (iEst*100)/SQLITE_INDEX_SAMPLES;
  2672         -    }
  2673         -    sqlite3ValueFree(pLowerVal);
  2674         -    sqlite3ValueFree(pUpperVal);
  2675         -    return rc;
  2676         -  }
  2677         -range_est_fallback:
         2683  +      if( rc==SQLITE_OK
         2684  +       && whereKeyStats(pParse, p, pRangeVal, 1, a)==SQLITE_OK
         2685  +      ){
         2686  +        iUpper = a[0];
         2687  +        if( pLower->eOperator==WO_LE ) iUpper += a[1];
         2688  +      }
         2689  +      sqlite3ValueFree(pRangeVal);
         2690  +    }
         2691  +    if( rc==SQLITE_OK ){
         2692  +      if( iUpper<=iLower ){
         2693  +        *pRangeDiv = p->aiRowEst[0];
         2694  +      }else{
         2695  +        *pRangeDiv = p->aiRowEst[0]/(iUpper - iLower);
         2696  +      }
         2697  +      WHERETRACE(("range scan regions: %u..%u  div=%u\n",
         2698  +                  (u32)iLower, (u32)iUpper, (u32)*pRangeDiv));
         2699  +      return SQLITE_OK;
         2700  +    }
         2701  +  }
  2678   2702   #else
  2679   2703     UNUSED_PARAMETER(pParse);
  2680   2704     UNUSED_PARAMETER(p);
  2681   2705     UNUSED_PARAMETER(nEq);
  2682   2706   #endif
  2683   2707     assert( pLower || pUpper );
  2684         -  *piEst = 100;
  2685         -  if( pLower && (pLower->wtFlags & TERM_VNULL)==0 ) *piEst /= 4;
  2686         -  if( pUpper ) *piEst /= 4;
         2708  +  *pRangeDiv = 1;
         2709  +  if( pLower && (pLower->wtFlags & TERM_VNULL)==0 ) *pRangeDiv *= 4;
         2710  +  if( pUpper ) *pRangeDiv *= 4;
  2687   2711     return rc;
  2688   2712   }
  2689   2713   
  2690         -#ifdef SQLITE_ENABLE_STAT2
         2714  +#ifdef SQLITE_ENABLE_STAT3
  2691   2715   /*
  2692   2716   ** Estimate the number of rows that will be returned based on
  2693   2717   ** an equality constraint x=VALUE and where that VALUE occurs in
  2694   2718   ** the histogram data.  This only works when x is the left-most
  2695         -** column of an index and sqlite_stat2 histogram data is available
         2719  +** column of an index and sqlite_stat3 histogram data is available
  2696   2720   ** for that index.  When pExpr==NULL that means the constraint is
  2697   2721   ** "x IS NULL" instead of "x=VALUE".
  2698   2722   **
  2699   2723   ** Write the estimated row count into *pnRow and return SQLITE_OK. 
  2700   2724   ** If unable to make an estimate, leave *pnRow unchanged and return
  2701   2725   ** non-zero.
  2702   2726   **
................................................................................
  2708   2732   static int whereEqualScanEst(
  2709   2733     Parse *pParse,       /* Parsing & code generating context */
  2710   2734     Index *p,            /* The index whose left-most column is pTerm */
  2711   2735     Expr *pExpr,         /* Expression for VALUE in the x=VALUE constraint */
  2712   2736     double *pnRow        /* Write the revised row estimate here */
  2713   2737   ){
  2714   2738     sqlite3_value *pRhs = 0;  /* VALUE on right-hand side of pTerm */
  2715         -  int iLower, iUpper;       /* Range of histogram regions containing pRhs */
  2716   2739     u8 aff;                   /* Column affinity */
  2717   2740     int rc;                   /* Subfunction return code */
  2718         -  double nRowEst;           /* New estimate of the number of rows */
         2741  +  tRowcnt a[2];             /* Statistics */
  2719   2742   
  2720   2743     assert( p->aSample!=0 );
  2721   2744     aff = p->pTable->aCol[p->aiColumn[0]].affinity;
  2722   2745     if( pExpr ){
  2723   2746       rc = valueFromExpr(pParse, pExpr, aff, &pRhs);
  2724   2747       if( rc ) goto whereEqualScanEst_cancel;
  2725   2748     }else{
  2726   2749       pRhs = sqlite3ValueNew(pParse->db);
  2727   2750     }
  2728   2751     if( pRhs==0 ) return SQLITE_NOTFOUND;
  2729         -  rc = whereRangeRegion(pParse, p, pRhs, 0, &iLower);
  2730         -  if( rc ) goto whereEqualScanEst_cancel;
  2731         -  rc = whereRangeRegion(pParse, p, pRhs, 1, &iUpper);
  2732         -  if( rc ) goto whereEqualScanEst_cancel;
  2733         -  WHERETRACE(("equality scan regions: %d..%d\n", iLower, iUpper));
  2734         -  if( iLower>=iUpper ){
  2735         -    nRowEst = p->aiRowEst[0]/(SQLITE_INDEX_SAMPLES*2);
  2736         -    if( nRowEst<*pnRow ) *pnRow = nRowEst;
  2737         -  }else{
  2738         -    nRowEst = (iUpper-iLower)*p->aiRowEst[0]/SQLITE_INDEX_SAMPLES;
  2739         -    *pnRow = nRowEst;
         2752  +  rc = whereKeyStats(pParse, p, pRhs, 0, a);
         2753  +  if( rc==SQLITE_OK ){
         2754  +    WHERETRACE(("equality scan regions: %d\n", (int)a[1]));
         2755  +    *pnRow = a[1];
  2740   2756     }
  2741         -
  2742   2757   whereEqualScanEst_cancel:
  2743   2758     sqlite3ValueFree(pRhs);
  2744   2759     return rc;
  2745   2760   }
  2746         -#endif /* defined(SQLITE_ENABLE_STAT2) */
         2761  +#endif /* defined(SQLITE_ENABLE_STAT3) */
  2747   2762   
  2748         -#ifdef SQLITE_ENABLE_STAT2
         2763  +#ifdef SQLITE_ENABLE_STAT3
  2749   2764   /*
  2750   2765   ** Estimate the number of rows that will be returned based on
  2751   2766   ** an IN constraint where the right-hand side of the IN operator
  2752   2767   ** is a list of values.  Example:
  2753   2768   **
  2754   2769   **        WHERE x IN (1,2,3,4)
  2755   2770   **
................................................................................
  2764   2779   */
  2765   2780   static int whereInScanEst(
  2766   2781     Parse *pParse,       /* Parsing & code generating context */
  2767   2782     Index *p,            /* The index whose left-most column is pTerm */
  2768   2783     ExprList *pList,     /* The value list on the RHS of "x IN (v1,v2,v3,...)" */
  2769   2784     double *pnRow        /* Write the revised row estimate here */
  2770   2785   ){
  2771         -  sqlite3_value *pVal = 0;  /* One value from list */
  2772         -  int iLower, iUpper;       /* Range of histogram regions containing pRhs */
  2773         -  u8 aff;                   /* Column affinity */
  2774   2786     int rc = SQLITE_OK;       /* Subfunction return code */
         2787  +  double nEst;              /* Number of rows for a single term */
  2775   2788     double nRowEst;           /* New estimate of the number of rows */
  2776         -  int nSpan = 0;            /* Number of histogram regions spanned */
  2777         -  int nSingle = 0;          /* Histogram regions hit by a single value */
  2778         -  int nNotFound = 0;        /* Count of values that are not constants */
  2779         -  int i;                               /* Loop counter */
  2780         -  u8 aSpan[SQLITE_INDEX_SAMPLES+1];    /* Histogram regions that are spanned */
  2781         -  u8 aSingle[SQLITE_INDEX_SAMPLES+1];  /* Histogram regions hit once */
         2789  +  int i;                    /* Loop counter */
  2782   2790   
  2783   2791     assert( p->aSample!=0 );
  2784         -  aff = p->pTable->aCol[p->aiColumn[0]].affinity;
  2785         -  memset(aSpan, 0, sizeof(aSpan));
  2786         -  memset(aSingle, 0, sizeof(aSingle));
  2787         -  for(i=0; i<pList->nExpr; i++){
  2788         -    sqlite3ValueFree(pVal);
  2789         -    rc = valueFromExpr(pParse, pList->a[i].pExpr, aff, &pVal);
  2790         -    if( rc ) break;
  2791         -    if( pVal==0 || sqlite3_value_type(pVal)==SQLITE_NULL ){
  2792         -      nNotFound++;
  2793         -      continue;
  2794         -    }
  2795         -    rc = whereRangeRegion(pParse, p, pVal, 0, &iLower);
  2796         -    if( rc ) break;
  2797         -    rc = whereRangeRegion(pParse, p, pVal, 1, &iUpper);
  2798         -    if( rc ) break;
  2799         -    if( iLower>=iUpper ){
  2800         -      aSingle[iLower] = 1;
  2801         -    }else{
  2802         -      assert( iLower>=0 && iUpper<=SQLITE_INDEX_SAMPLES );
  2803         -      while( iLower<iUpper ) aSpan[iLower++] = 1;
  2804         -    }
         2792  +  for(i=0; rc==SQLITE_OK && i<pList->nExpr; i++){
         2793  +    nEst = p->aiRowEst[0];
         2794  +    rc = whereEqualScanEst(pParse, p, pList->a[i].pExpr, &nEst);
         2795  +    nRowEst += nEst;
  2805   2796     }
  2806   2797     if( rc==SQLITE_OK ){
  2807         -    for(i=nSpan=0; i<=SQLITE_INDEX_SAMPLES; i++){
  2808         -      if( aSpan[i] ){
  2809         -        nSpan++;
  2810         -      }else if( aSingle[i] ){
  2811         -        nSingle++;
  2812         -      }
  2813         -    }
  2814         -    nRowEst = (nSpan*2+nSingle)*p->aiRowEst[0]/(2*SQLITE_INDEX_SAMPLES)
  2815         -               + nNotFound*p->aiRowEst[1];
  2816   2798       if( nRowEst > p->aiRowEst[0] ) nRowEst = p->aiRowEst[0];
  2817   2799       *pnRow = nRowEst;
  2818         -    WHERETRACE(("IN row estimate: nSpan=%d, nSingle=%d, nNotFound=%d, est=%g\n",
  2819         -                 nSpan, nSingle, nNotFound, nRowEst));
         2800  +    WHERETRACE(("IN row estimate: est=%g\n", nRowEst));
  2820   2801     }
  2821         -  sqlite3ValueFree(pVal);
  2822   2802     return rc;
  2823   2803   }
  2824         -#endif /* defined(SQLITE_ENABLE_STAT2) */
         2804  +#endif /* defined(SQLITE_ENABLE_STAT3) */
  2825   2805   
  2826   2806   
  2827   2807   /*
  2828   2808   ** Find the best query plan for accessing a particular table.  Write the
  2829   2809   ** best query plan and its cost into the WhereCost object supplied as the
  2830   2810   ** last parameter.
  2831   2811   **
................................................................................
  2864   2844   ){
  2865   2845     int iCur = pSrc->iCursor;   /* The cursor of the table to be accessed */
  2866   2846     Index *pProbe;              /* An index we are evaluating */
  2867   2847     Index *pIdx;                /* Copy of pProbe, or zero for IPK index */
  2868   2848     int eqTermMask;             /* Current mask of valid equality operators */
  2869   2849     int idxEqTermMask;          /* Index mask of valid equality operators */
  2870   2850     Index sPk;                  /* A fake index object for the primary key */
  2871         -  unsigned int aiRowEstPk[2]; /* The aiRowEst[] value for the sPk index */
         2851  +  tRowcnt aiRowEstPk[2];      /* The aiRowEst[] value for the sPk index */
  2872   2852     int aiColumnPk = -1;        /* The aColumn[] value for the sPk index */
  2873   2853     int wsFlagMask;             /* Allowed flags in pCost->plan.wsFlag */
  2874   2854   
  2875   2855     /* Initialize the cost to a worst-case value */
  2876   2856     memset(pCost, 0, sizeof(*pCost));
  2877   2857     pCost->rCost = SQLITE_BIG_DBL;
  2878   2858   
................................................................................
  2919   2899       eqTermMask = WO_EQ|WO_IN;
  2920   2900       pIdx = 0;
  2921   2901     }
  2922   2902   
  2923   2903     /* Loop over all indices looking for the best one to use
  2924   2904     */
  2925   2905     for(; pProbe; pIdx=pProbe=pProbe->pNext){
  2926         -    const unsigned int * const aiRowEst = pProbe->aiRowEst;
         2906  +    const tRowcnt * const aiRowEst = pProbe->aiRowEst;
  2927   2907       double cost;                /* Cost of using pProbe */
  2928   2908       double nRow;                /* Estimated number of rows in result set */
  2929   2909       double log10N;              /* base-10 logarithm of nRow (inexact) */
  2930   2910       int rev;                    /* True to scan in reverse order */
  2931   2911       int wsFlags = 0;
  2932   2912       Bitmask used = 0;
  2933   2913   
................................................................................
  2962   2942       **
  2963   2943       **  bInEst:  
  2964   2944       **    Set to true if there was at least one "x IN (SELECT ...)" term used 
  2965   2945       **    in determining the value of nInMul.  Note that the RHS of the
  2966   2946       **    IN operator must be a SELECT, not a value list, for this variable
  2967   2947       **    to be true.
  2968   2948       **
  2969         -    **  estBound:
  2970         -    **    An estimate on the amount of the table that must be searched.  A
  2971         -    **    value of 100 means the entire table is searched.  Range constraints
  2972         -    **    might reduce this to a value less than 100 to indicate that only
  2973         -    **    a fraction of the table needs searching.  In the absence of
  2974         -    **    sqlite_stat2 ANALYZE data, a single inequality reduces the search
  2975         -    **    space to 1/4rd its original size.  So an x>? constraint reduces
  2976         -    **    estBound to 25.  Two constraints (x>? AND x<?) reduce estBound to 6.
         2949  +    **  rangeDiv:
         2950  +    **    An estimate of a divisor by which to reduce the search space due
         2951  +    **    to inequality constraints.  In the absence of sqlite_stat3 ANALYZE
         2952  +    **    data, a single inequality reduces the search space to 1/4rd its
         2953  +    **    original size (rangeDiv==4).  Two inequalities reduce the search
         2954  +    **    space to 1/16th of its original size (rangeDiv==16).
  2977   2955       **
  2978   2956       **  bSort:   
  2979   2957       **    Boolean. True if there is an ORDER BY clause that will require an 
  2980   2958       **    external sort (i.e. scanning the index being evaluated will not 
  2981   2959       **    correctly order records).
  2982   2960       **
  2983   2961       **  bLookup: 
................................................................................
  2994   2972       **
  2995   2973       **             SELECT a, b    FROM tbl WHERE a = 1;
  2996   2974       **             SELECT a, b, c FROM tbl WHERE a = 1;
  2997   2975       */
  2998   2976       int nEq;                      /* Number of == or IN terms matching index */
  2999   2977       int bInEst = 0;               /* True if "x IN (SELECT...)" seen */
  3000   2978       int nInMul = 1;               /* Number of distinct equalities to lookup */
  3001         -    int estBound = 100;           /* Estimated reduction in search space */
         2979  +    tRowcnt rangeDiv = 1;         /* Estimated reduction in search space */
  3002   2980       int nBound = 0;               /* Number of range constraints seen */
  3003   2981       int bSort = !!pOrderBy;       /* True if external sort required */
  3004   2982       int bDist = !!pDistinct;      /* True if index cannot help with DISTINCT */
  3005   2983       int bLookup = 0;              /* True if not a covering index */
  3006   2984       WhereTerm *pTerm;             /* A single term of the WHERE clause */
  3007         -#ifdef SQLITE_ENABLE_STAT2
         2985  +#ifdef SQLITE_ENABLE_STAT3
  3008   2986       WhereTerm *pFirstTerm = 0;    /* First term matching the index */
  3009   2987   #endif
  3010   2988   
  3011   2989       /* Determine the values of nEq and nInMul */
  3012   2990       for(nEq=0; nEq<pProbe->nColumn; nEq++){
  3013   2991         int j = pProbe->aiColumn[nEq];
  3014   2992         pTerm = findTerm(pWC, iCur, j, notReady, eqTermMask, pIdx);
................................................................................
  3024   3002           }else if( ALWAYS(pExpr->x.pList && pExpr->x.pList->nExpr) ){
  3025   3003             /* "x IN (value, value, ...)" */
  3026   3004             nInMul *= pExpr->x.pList->nExpr;
  3027   3005           }
  3028   3006         }else if( pTerm->eOperator & WO_ISNULL ){
  3029   3007           wsFlags |= WHERE_COLUMN_NULL;
  3030   3008         }
  3031         -#ifdef SQLITE_ENABLE_STAT2
         3009  +#ifdef SQLITE_ENABLE_STAT3
  3032   3010         if( nEq==0 && pProbe->aSample ) pFirstTerm = pTerm;
  3033   3011   #endif
  3034   3012         used |= pTerm->prereqRight;
  3035   3013       }
  3036   3014   
  3037         -    /* Determine the value of estBound. */
         3015  +    /* Determine the value of rangeDiv */
  3038   3016       if( nEq<pProbe->nColumn && pProbe->bUnordered==0 ){
  3039   3017         int j = pProbe->aiColumn[nEq];
  3040   3018         if( findTerm(pWC, iCur, j, notReady, WO_LT|WO_LE|WO_GT|WO_GE, pIdx) ){
  3041   3019           WhereTerm *pTop = findTerm(pWC, iCur, j, notReady, WO_LT|WO_LE, pIdx);
  3042   3020           WhereTerm *pBtm = findTerm(pWC, iCur, j, notReady, WO_GT|WO_GE, pIdx);
  3043         -        whereRangeScanEst(pParse, pProbe, nEq, pBtm, pTop, &estBound);
         3021  +        whereRangeScanEst(pParse, pProbe, nEq, pBtm, pTop, &rangeDiv);
  3044   3022           if( pTop ){
  3045   3023             nBound = 1;
  3046   3024             wsFlags |= WHERE_TOP_LIMIT;
  3047   3025             used |= pTop->prereqRight;
  3048   3026           }
  3049   3027           if( pBtm ){
  3050   3028             nBound++;
................................................................................
  3108   3086       */
  3109   3087       nRow = (double)(aiRowEst[nEq] * nInMul);
  3110   3088       if( bInEst && nRow*2>aiRowEst[0] ){
  3111   3089         nRow = aiRowEst[0]/2;
  3112   3090         nInMul = (int)(nRow / aiRowEst[nEq]);
  3113   3091       }
  3114   3092   
  3115         -#ifdef SQLITE_ENABLE_STAT2
         3093  +#ifdef SQLITE_ENABLE_STAT3
  3116   3094       /* If the constraint is of the form x=VALUE or x IN (E1,E2,...)
  3117   3095       ** and we do not think that values of x are unique and if histogram
  3118   3096       ** data is available for column x, then it might be possible
  3119   3097       ** to get a better estimate on the number of rows based on
  3120   3098       ** VALUE and how common that value is according to the histogram.
  3121   3099       */
  3122   3100       if( nRow>(double)1 && nEq==1 && pFirstTerm!=0 && aiRowEst[1]>1 ){
................................................................................
  3124   3102           testcase( pFirstTerm->eOperator==WO_EQ );
  3125   3103           testcase( pFirstTerm->eOperator==WO_ISNULL );
  3126   3104           whereEqualScanEst(pParse, pProbe, pFirstTerm->pExpr->pRight, &nRow);
  3127   3105         }else if( pFirstTerm->eOperator==WO_IN && bInEst==0 ){
  3128   3106           whereInScanEst(pParse, pProbe, pFirstTerm->pExpr->x.pList, &nRow);
  3129   3107         }
  3130   3108       }
  3131         -#endif /* SQLITE_ENABLE_STAT2 */
         3109  +#endif /* SQLITE_ENABLE_STAT3 */
  3132   3110   
  3133   3111       /* Adjust the number of output rows and downward to reflect rows
  3134   3112       ** that are excluded by range constraints.
  3135   3113       */
  3136         -    nRow = (nRow * (double)estBound) / (double)100;
         3114  +    nRow = nRow/(double)rangeDiv;
  3137   3115       if( nRow<1 ) nRow = 1;
  3138   3116   
  3139   3117       /* Experiments run on real SQLite databases show that the time needed
  3140   3118       ** to do a binary search to locate a row in a table or index is roughly
  3141   3119       ** log10(N) times the time to move from one row to the next row within
  3142   3120       ** a table or index.  The actual times can vary, with the size of
  3143   3121       ** records being an important factor.  Both moves and searches are
................................................................................
  3258   3236           }
  3259   3237         }
  3260   3238         if( nRow<2 ) nRow = 2;
  3261   3239       }
  3262   3240   
  3263   3241   
  3264   3242       WHERETRACE((
  3265         -      "%s(%s): nEq=%d nInMul=%d estBound=%d bSort=%d bLookup=%d wsFlags=0x%x\n"
         3243  +      "%s(%s): nEq=%d nInMul=%d rangeDiv=%d bSort=%d bLookup=%d wsFlags=0x%x\n"
  3266   3244         "         notReady=0x%llx log10N=%.1f nRow=%.1f cost=%.1f used=0x%llx\n",
  3267   3245         pSrc->pTab->zName, (pIdx ? pIdx->zName : "ipk"), 
  3268         -      nEq, nInMul, estBound, bSort, bLookup, wsFlags,
         3246  +      nEq, nInMul, (int)rangeDiv, bSort, bLookup, wsFlags,
  3269   3247         notReady, log10N, nRow, cost, used
  3270   3248       ));
  3271   3249   
  3272   3250       /* If this index is the best we have seen so far, then record this
  3273   3251       ** index and its cost in the pCost structure.
  3274   3252       */
  3275   3253       if( (!pIdx || wsFlags)

Changes to test/auth.test.

  2320   2320           DROP TABLE v1chng;
  2321   2321         }
  2322   2322       }
  2323   2323     }
  2324   2324     ifcapable stat2 {
  2325   2325       set stat2 "sqlite_stat2 "
  2326   2326     } else {
  2327         -    set stat2 ""
         2327  +    ifcapable stat3 {
         2328  +      set stat2 "sqlite_stat3 "
         2329  +    } else {
         2330  +      set stat2 ""
         2331  +    }
  2328   2332     }
  2329   2333     do_test auth-5.2 {
  2330   2334       execsql {
  2331   2335         SELECT name FROM (
  2332   2336           SELECT * FROM sqlite_master UNION ALL SELECT * FROM sqlite_temp_master)
  2333   2337         WHERE type='table'
  2334   2338         ORDER BY name

Added test/stat3.test.

            1  +# 2011 August 08
            2  +#
            3  +# The author disclaims copyright to this source code.  In place of
            4  +# a legal notice, here is a blessing:
            5  +#
            6  +#    May you do good and not evil.
            7  +#    May you find forgiveness for yourself and forgive others.
            8  +#    May you share freely, never taking more than you give.
            9  +#
           10  +#***********************************************************************
           11  +#
           12  +# This file implements regression tests for SQLite library. This file 
           13  +# implements tests for the extra functionality provided by the ANALYZE 
           14  +# command when the library is compiled with SQLITE_ENABLE_STAT2 defined.
           15  +#
           16  +
           17  +set testdir [file dirname $argv0]
           18  +source $testdir/tester.tcl
           19  +
           20  +set testprefix stat3
           21  +
           22  +
           23  +# Verify that if not compiled with SQLITE_ENABLE_STAT2 that the ANALYZE
           24  +# command will delete the sqlite_stat2 table.  Likewise, if not compiled
           25  +# with SQLITE_ENABLE_STAT3, the sqlite_stat3 table is deleted.
           26  +#
           27  +do_test 1.1 {
           28  +  db eval {
           29  +    PRAGMA writable_schema=ON;
           30  +    CREATE TABLE sqlite_stat2(tbl,idx,sampleno,sample);
           31  +    CREATE TABLE sqlite_stat3(tbl,idx,sampleno,sample,neq,nlt);
           32  +    SELECT name FROM sqlite_master ORDER BY 1;
           33  +  }
           34  +} {sqlite_stat2 sqlite_stat3}
           35  +do_test 1.2 {
           36  +  db close
           37  +  sqlite3 db test.db
           38  +  db eval {SELECT name FROM sqlite_master ORDER BY 1}
           39  +} {sqlite_stat2 sqlite_stat3}
           40  +
           41  +ifcapable {stat3} {
           42  +  do_test 1.3 {
           43  +    db eval {ANALYZE; SELECT name FROM sqlite_master ORDER BY 1}
           44  +  } {sqlite_stat1 sqlite_stat3}
           45  +} else {
           46  +  do_test 1.4 {
           47  +    db eval {ANALYZE; SELECT name FROM sqlite_master ORDER BY 1}
           48  +  } {sqlite_stat1}
           49  +  finish_test
           50  +  return
           51  +}
           52  +
           53  +
           54  +
           55  +
           56  +finish_test