SQLite

Changes On Branch query-planner-tweaks
Login

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

Changes In Branch query-planner-tweaks Excluding Merge-Ins

This is equivalent to a diff from b90c28be to d1248165

2011-08-08
17:18
Add code to actually use the sqlite_stat2.cnt field in the query planner. This changes some plans resulting in a few failures in analyze5.test. (Closed-Leaf check-in: d1248165 user: drh tags: query-planner-tweaks)
2011-08-07
01:31
Remove relevant elements from the sqlite_stat2 table when doing a DROP INDEX or DROP TABLE. (check-in: 3c8f97ae user: drh tags: trunk)
00:21
The ANALYZE command adds the sqlite_stat2.cnt column if it does not already exist. (check-in: 794fde6f user: drh tags: query-planner-tweaks)
2011-08-05
21:13
Add a column to the sqlite_stat2 table that contains the number of entries with exactly the same key as the sample. We do not yet do anything with this extra value. Some tests in analyze2.test are failing. (check-in: eb434228 user: drh tags: query-planner-tweaks)
2011-08-03
22:06
Merge the winopen-retry-logic branch into trunk. The biggest change here is to test scripts, which should now use such as copy_file and delete_file from tester.tcl rather than the raw file commands of TCL. (check-in: b90c28be user: drh tags: trunk)
16:40
Update the OP_Move opcode to shift the pScopyFrom pointer of aliases when compiled with SQLITE_DEBUG. Ticket [d63523637517386191]. (check-in: a2135ad1 user: drh tags: trunk)
2011-08-02
23:45
Add explanatory comment to the win32lock-2.2 test case. (Closed-Leaf check-in: 4cb17881 user: mistachkin tags: winopen-retry-logic)

Changes to src/analyze.c.

1
2
3
4
5
6
7
8
9
10
11
12





























































































13
14
15
16
17
18
19
/*
** 2005 July 8
**
** The author disclaims copyright to this source code.  In place of
** a legal notice, here is a blessing:
**
**    May you do good and not evil.
**    May you find forgiveness for yourself and forgive others.
**    May you share freely, never taking more than you give.
**
*************************************************************************
** This file contains code associated with the ANALYZE command.





























































































*/
#ifndef SQLITE_OMIT_ANALYZE
#include "sqliteInt.h"

/*
** This routine generates code that opens the sqlite_stat1 table for
** writing with cursor iStatCur. If the library was built with the












>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>







1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
/*
** 2005 July 8
**
** The author disclaims copyright to this source code.  In place of
** a legal notice, here is a blessing:
**
**    May you do good and not evil.
**    May you find forgiveness for yourself and forgive others.
**    May you share freely, never taking more than you give.
**
*************************************************************************
** This file contains code associated with the ANALYZE command.
**
** The ANALYZE command gather statistics about the content of tables
** and indices.  These statistics are made available to the query planner
** to help it make better decisions about the best way to implement a
** query.
**
** Two system tables are created as follows:
**
**    CREATE TABLE sqlite_stat1(tbl, idx, stat);
**    CREATE TABLE sqlite_stat2(tbl, idx, sampleno, sample, cnt);
**
** Additional tables might be added in future releases of SQLite.
** The sqlite_stat2 table is only created and used if SQLite is
** compiled with SQLITE_ENABLE_STAT2.  Older versions of SQLite
** omit the sqlite_stat2.cnt column.  Newer versions of SQLite are
** able to use older versions of the stat2 table that lack the cnt
** column.
**
** Format of sqlite_stat1:
**
** There is normally one row per index, with the index identified by the
** name in the idx column.  The tbl column is the name of the table to
** which the index belongs.  In each such row, the stat column will be
** a string consisting of a list of integers.  The first integer in this
** list is the number of rows in the index and in the table.  The second
** integer is the average number of rows in the index that have the same
** value in the first column of the index.  The third integer is the average
** number of rows in the index that have the same value for the first two
** columns.  The N-th integer (for N>1) is the average number of rows in 
** the index which have the same value for the first N-1 columns.  For
** a K-column index, there will be K+1 integers in the stat column.  If
** the index is unique, then the last integer will be 1.
**
** The list of integers in the stat column can optionally be followed
** by the keyword "unordered".  The "unordered" keyword, if it is present,
** must be separated from the last integer by a single space.  If the
** "unordered" keyword is present, then the query planner assumes that
** the index is unordered and will not use the index for a range query.
** 
** If the sqlite_stat1.idx column is NULL, then the sqlite_stat1.stat
** column contains a single integer which is the (estimated) number of
** rows in the table identified by sqlite_stat1.tbl.
**
** Format of sqlite_stat2:
**
** The sqlite_stat2 is only created and is only used if SQLite is compiled
** with SQLITE_ENABLE_STAT2.  The "stat2" table contains additional information
** about the key distribution within an index.  The index is identified by
** the "idx" column and the "tbl" column is the name of the table to which
** the index belongs.  There are usually multiple rows in the sqlite_stat2
** table for each index.
**
** The sqlite_stat2 entires for an index that have sampleno>=0 are
** sampled key values for the first column of the index taken at
** intervals along the index.  The sqlite_stat2.sample column holds
** the value of the key in the left-most column of the index.
**
** The samples are numbered from 0 to S-1
** where S is 10 by default.  The number of samples created by the
** ANALYZE command can be adjusted at compile-time using the
** SQLITE_INDEX_SAMPLES macro.  The maximum number of samples is
** SQLITE_MAX_SAMPLES, currently set to 100.  There are places in the
** code that use an unsigned character to count samples, so an upper
** bound on SQLITE_MAX_SAMPLES is 255.
**
** Suppose the index contains C rows.  And let the number
** of samples be S.  SQLite assumes that the samples are taken from the
** following rows for i between 0 and S-1:
**
**     rownumber = (i*C*2 + C)/(S*2)
**
** Conceptually, the index is divided into S bins and the sample is
** taken from the middle of each bin.  The ANALYZE will not attempt
** to populate sqlite_stat2 for an index that holds fewer than S*2
** entries.
**
** If the key value for a sample (the sqlite_stat2.sample column) is a 
** large string or blob, SQLite will only use the first 255 bytes of 
** that string or blob.
** 
** The sqlite_stat2.cnt column contains the number of entries in the
** index for which sqlite_stat2.sample matches the left-most column
** of the index.  In other words, sqlite_stat2.cnt holds the number of
** times the sqlite_stat2.sample value appears in the index..  Many 
** older versions of SQLite omit the sqlite_stat2.cnt column.
**
** If the sqlite_stat2.sampleno value is -1, then that row holds a first-
** column key that is a frequently used key in the index.  The
** sqlite_stat2.cnt column will hold the number of occurrances of that key.
** This information is useful to the query planner in cases where a
** large percentage of the rows in indexed field have one of a small
** handful of value but the balance of the rows in the index have
** distinct or nearly distinct keys.
*/
#ifndef SQLITE_OMIT_ANALYZE
#include "sqliteInt.h"

/*
** This routine generates code that opens the sqlite_stat1 table for
** writing with cursor iStatCur. If the library was built with the
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
){
  static const struct {
    const char *zName;
    const char *zCols;
  } aTable[] = {
    { "sqlite_stat1", "tbl,idx,stat" },
#ifdef SQLITE_ENABLE_STAT2
    { "sqlite_stat2", "tbl,idx,sampleno,sample" },
#endif
  };

  int aRoot[] = {0, 0};
  u8 aCreateTbl[] = {0, 0};

  int i;







|







132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
){
  static const struct {
    const char *zName;
    const char *zCols;
  } aTable[] = {
    { "sqlite_stat1", "tbl,idx,stat" },
#ifdef SQLITE_ENABLE_STAT2
    { "sqlite_stat2", "tbl,idx,sampleno,sample,cnt" },
#endif
  };

  int aRoot[] = {0, 0};
  u8 aCreateTbl[] = {0, 0};

  int i;
82
83
84
85
86
87
88









89
90
91
92
93
94
95
96

97
98
99
100
101
102
103
        sqlite3NestedParse(pParse,
           "DELETE FROM %Q.%s WHERE %s=%Q", pDb->zName, zTab, zWhereType, zWhere
        );
      }else{
        /* The sqlite_stat[12] table already exists.  Delete all rows. */
        sqlite3VdbeAddOp2(v, OP_Clear, aRoot[i], iDb);
      }









    }
  }

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

  }
}

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







>
>
>
>
>
>
>
>
>








>







175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
        sqlite3NestedParse(pParse,
           "DELETE FROM %Q.%s WHERE %s=%Q", pDb->zName, zTab, zWhereType, zWhere
        );
      }else{
        /* The sqlite_stat[12] table already exists.  Delete all rows. */
        sqlite3VdbeAddOp2(v, OP_Clear, aRoot[i], iDb);
      }
#ifdef SQLITE_ENABLE_STAT2
      if( i==1 && iDb!=1 && pStat->nCol==4 ){
        sqlite3NestedParse(pParse,
           "UPDATE %Q.sqlite_master SET sql='CREATE TABLE sqlite_stat2(%s)'"
           " WHERE name='sqlite_stat2'", pDb->zName, aTable[i].zCols
        );
        sqlite3ChangeCookie(pParse, iDb);
      }
#endif
    }
  }

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

/*
** Generate code to do an analysis of all indices associated with
** a single table.
*/
115
116
117
118
119
120
121
122














123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
  int i;                       /* Loop counter */
  int topOfLoop;               /* The top of the loop */
  int endOfLoop;               /* The end of the loop */
  int jZeroRows = -1;          /* Jump from here if number of rows is zero */
  int iDb;                     /* Index of database containing pTab */
  int regTabname = iMem++;     /* Register containing table name */
  int regIdxname = iMem++;     /* Register containing index name */
  int regSampleno = iMem++;    /* Register containing next sample number */














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

#ifdef SQLITE_ENABLE_STAT2
  int addr = 0;                /* Instruction address */
  int regTemp2 = iMem++;       /* Temporary use register */
  int regSamplerecno = iMem++; /* Index of next sample to record */
  int regRecno = iMem++;       /* Current sample index */
  int regLast = iMem++;        /* Index of last sample to record */
  int regFirst = iMem++;       /* Index of first sample to record */
#endif

  v = sqlite3GetVdbe(pParse);
  if( v==0 || NEVER(pTab==0) ){
    return;
  }
  if( pTab->tnum==0 ){
    /* Do not gather statistics on views or virtual tables */







|
>
>
>
>
>
>
>
>
>
>
>
>
>
>
|




<
<
<
<
<
<
<
<







218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244








245
246
247
248
249
250
251
  int i;                       /* Loop counter */
  int topOfLoop;               /* The top of the loop */
  int endOfLoop;               /* The end of the loop */
  int jZeroRows = -1;          /* Jump from here if number of rows is zero */
  int iDb;                     /* Index of database containing pTab */
  int regTabname = iMem++;     /* Register containing table name */
  int regIdxname = iMem++;     /* Register containing index name */
  int regSampleno = iMem++;    /* Sampleno (stat2) or stat (stat1) */
#ifdef SQLITE_ENABLE_STAT2
  int regSample = iMem++;      /* The next sample value */
  int regSampleCnt = iMem++;   /* Number of occurrances of regSample value */
  int shortJump = 0;           /* Instruction address */
  int addrStoreStat2 = 0;      /* Address of subroutine to wrote to stat2 */
  int regNext = iMem++;        /* Index of next sample to record */
  int regSampleIdx = iMem++;   /* Index of next sample */
  int regReady = iMem++;       /* True if ready to store a stat2 entry */
  int regGosub = iMem++;       /* Register holding subroutine return addr */
  int regSample2 = iMem++;     /* Number of samples to acquire times 2 */
  int regCount = iMem++;       /* Number of rows in the table */
  int regCount2 = iMem++;      /* regCount*2 */
  int once = 1;                /* One-time initialization */
#endif
  int regCol = iMem++;         /* Content of a column in analyzed table */
  int regRec = iMem++;         /* Register holding completed record */
  int regTemp = iMem++;        /* Temporary use register */
  int regRowid = iMem++;       /* Rowid for the inserted record */










  v = sqlite3GetVdbe(pParse);
  if( v==0 || NEVER(pTab==0) ){
    return;
  }
  if( pTab->tnum==0 ){
    /* Do not gather statistics on views or virtual tables */
161
162
163
164
165
166
167


168
169

170
171
172
173
174


175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190

191
192
193

194




195


196
197
198
199
200

201

202
203
204

205


206
207
208

209
210
211
212
213
214
215
216
  sqlite3TableLock(pParse, iDb, pTab->tnum, 0, pTab->zName);

  iIdxCur = pParse->nTab++;
  sqlite3VdbeAddOp4(v, OP_String8, 0, regTabname, 0, pTab->zName, 0);
  for(pIdx=pTab->pIndex; pIdx; pIdx=pIdx->pNext){
    int nCol;
    KeyInfo *pKey;



    if( pOnlyIdx && pOnlyIdx!=pIdx ) continue;

    nCol = pIdx->nColumn;
    pKey = sqlite3IndexKeyinfo(pParse, pIdx);
    if( iMem+1+(nCol*2)>pParse->nMem ){
      pParse->nMem = iMem+1+(nCol*2);
    }



    /* Open a cursor to the index to be analyzed. */
    assert( iDb==sqlite3SchemaToIndex(db, pIdx->pSchema) );
    sqlite3VdbeAddOp4(v, OP_OpenRead, iIdxCur, pIdx->tnum, iDb,
        (char *)pKey, P4_KEYINFO_HANDOFF);
    VdbeComment((v, "%s", pIdx->zName));

    /* Populate the register containing the index name. */
    sqlite3VdbeAddOp4(v, OP_String8, 0, regIdxname, 0, pIdx->zName, 0);

#ifdef SQLITE_ENABLE_STAT2

    /* If this iteration of the loop is generating code to analyze the
    ** first index in the pTab->pIndex list, then register regLast has
    ** not been populated. In this case populate it now.  */
    if( pTab->pIndex==pIdx ){

      sqlite3VdbeAddOp2(v, OP_Integer, SQLITE_INDEX_SAMPLES, regSamplerecno);
      sqlite3VdbeAddOp2(v, OP_Integer, SQLITE_INDEX_SAMPLES*2-1, regTemp);
      sqlite3VdbeAddOp2(v, OP_Integer, SQLITE_INDEX_SAMPLES*2, regTemp2);






      sqlite3VdbeAddOp2(v, OP_Count, iIdxCur, regLast);


      sqlite3VdbeAddOp2(v, OP_Null, 0, regFirst);
      addr = sqlite3VdbeAddOp3(v, OP_Lt, regSamplerecno, 0, regLast);
      sqlite3VdbeAddOp3(v, OP_Divide, regTemp2, regLast, regFirst);
      sqlite3VdbeAddOp3(v, OP_Multiply, regLast, regTemp, regLast);
      sqlite3VdbeAddOp2(v, OP_AddImm, regLast, SQLITE_INDEX_SAMPLES*2-2);

      sqlite3VdbeAddOp3(v, OP_Divide,  regTemp2, regLast, regLast);

      sqlite3VdbeJumpHere(v, addr);
    }


    /* Zero the regSampleno and regRecno registers. */


    sqlite3VdbeAddOp2(v, OP_Integer, 0, regSampleno);
    sqlite3VdbeAddOp2(v, OP_Integer, 0, regRecno);
    sqlite3VdbeAddOp2(v, OP_Copy, regFirst, regSamplerecno);

#endif

    /* The block of memory cells initialized here is used as follows.
    **
    **    iMem:                
    **        The total number of rows in the table.
    **
    **    iMem+1 .. iMem+nCol: 







>
>


>





>
>















|
>
|
|
|
>

>
>
>
>
|
>
>
|
<
|
|
|
>
|
>
|

|
>
|
>
>

|
|
>
|







270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318

319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
  sqlite3TableLock(pParse, iDb, pTab->tnum, 0, pTab->zName);

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

    if( pOnlyIdx && pOnlyIdx!=pIdx ) continue;
    VdbeNoopComment((v, "Begin analysis of %s", pIdx->zName));
    nCol = pIdx->nColumn;
    pKey = sqlite3IndexKeyinfo(pParse, pIdx);
    if( iMem+1+(nCol*2)>pParse->nMem ){
      pParse->nMem = iMem+1+(nCol*2);
    }
    aChngAddr = sqlite3DbMallocRaw(db, sizeof(int)*pIdx->nColumn);
    if( aChngAddr==0 ) continue;

    /* Open a cursor to the index to be analyzed. */
    assert( iDb==sqlite3SchemaToIndex(db, pIdx->pSchema) );
    sqlite3VdbeAddOp4(v, OP_OpenRead, iIdxCur, pIdx->tnum, iDb,
        (char *)pKey, P4_KEYINFO_HANDOFF);
    VdbeComment((v, "%s", pIdx->zName));

    /* Populate the register containing the index name. */
    sqlite3VdbeAddOp4(v, OP_String8, 0, regIdxname, 0, pIdx->zName, 0);

#ifdef SQLITE_ENABLE_STAT2

    /* If this iteration of the loop is generating code to analyze the
    ** first index in the pTab->pIndex list, then register regLast has
    ** not been populated. In this case populate it now.  */
    if( once ){
      once = 0;
      sqlite3VdbeAddOp2(v, OP_Integer, SQLITE_INDEX_SAMPLES*2, regSample2);

      sqlite3VdbeAddOp2(v, OP_Count, iIdxCur, regCount);
      sqlite3VdbeAddOp3(v, OP_Add, regCount, regCount, regCount2);


      /* Generate code for a subroutine that store the most recent sample
      ** in the sqlite_stat2 table
      */
      shortJump = sqlite3VdbeAddOp0(v, OP_Goto);
      sqlite3VdbeAddOp4(v, OP_MakeRecord, regTabname, 5, regRec, "aaaba", 0);
      VdbeComment((v, "begin stat2 write subroutine"));
      sqlite3VdbeAddOp2(v, OP_NewRowid, iStatCur+1, regRowid);

      sqlite3VdbeAddOp3(v, OP_Insert, iStatCur+1, regRec, regRowid);
      sqlite3VdbeAddOp2(v, OP_AddImm, regSampleno, 1);
      sqlite3VdbeAddOp2(v, OP_AddImm, regReady, -1);
      addrStoreStat2 = sqlite3VdbeAddOp2(v, OP_IfPos, regReady, shortJump+1);
      sqlite3VdbeAddOp1(v, OP_Return, regGosub);
      VdbeComment((v, "end stat2 write subroutine"));
      sqlite3VdbeJumpHere(v, shortJump);
    }
    /* Reset state registers */
    sqlite3VdbeAddOp2(v, OP_Copy, regCount2, regNext);
    shortJump = sqlite3VdbeAddOp3(v, OP_Lt, regSample2, 0, regCount);
    sqlite3VdbeAddOp3(v, OP_Divide, regSample2, regCount, regNext);
    sqlite3VdbeJumpHere(v, shortJump);
    sqlite3VdbeAddOp2(v, OP_Integer, 0, regSampleno);
    sqlite3VdbeAddOp2(v, OP_Integer, 0, regSampleIdx);
    sqlite3VdbeAddOp2(v, OP_Integer, 0, regReady);

#endif /* SQLITE_ENABLE_STAT2 */

    /* The block of memory cells initialized here is used as follows.
    **
    **    iMem:                
    **        The total number of rows in the table.
    **
    **    iMem+1 .. iMem+nCol: 
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284





285
286
287
288
289
290
291
292
293
294
295
296
297




298
299
300
301
302

303
304

305

























306
307



308
309
310
311
312
313
314
    }

    /* Start the analysis loop. This loop runs through all the entries in
    ** the index b-tree.  */
    endOfLoop = sqlite3VdbeMakeLabel(v);
    sqlite3VdbeAddOp2(v, OP_Rewind, iIdxCur, endOfLoop);
    topOfLoop = sqlite3VdbeCurrentAddr(v);
    sqlite3VdbeAddOp2(v, OP_AddImm, iMem, 1);

    for(i=0; i<nCol; i++){
      CollSeq *pColl;
      sqlite3VdbeAddOp3(v, OP_Column, iIdxCur, i, regCol);
      if( i==0 ){
#ifdef SQLITE_ENABLE_STAT2
        /* Check if the record that cursor iIdxCur points to contains a
        ** value that should be stored in the sqlite_stat2 table. If so,
        ** store it.  */
        int ne = sqlite3VdbeAddOp3(v, OP_Ne, regRecno, 0, regSamplerecno);
        assert( regTabname+1==regIdxname 
             && regTabname+2==regSampleno
             && regTabname+3==regCol
        );
        sqlite3VdbeChangeP5(v, SQLITE_JUMPIFNULL);
        sqlite3VdbeAddOp4(v, OP_MakeRecord, regTabname, 4, regRec, "aaab", 0);
        sqlite3VdbeAddOp2(v, OP_NewRowid, iStatCur+1, regRowid);
        sqlite3VdbeAddOp3(v, OP_Insert, iStatCur+1, regRec, regRowid);

        /* Calculate new values for regSamplerecno and regSampleno.
        **
        **   sampleno = sampleno + 1
        **   samplerecno = samplerecno+(remaining records)/(remaining samples)
        */
        sqlite3VdbeAddOp2(v, OP_AddImm, regSampleno, 1);
        sqlite3VdbeAddOp3(v, OP_Subtract, regRecno, regLast, regTemp);
        sqlite3VdbeAddOp2(v, OP_AddImm, regTemp, -1);
        sqlite3VdbeAddOp2(v, OP_Integer, SQLITE_INDEX_SAMPLES, regTemp2);
        sqlite3VdbeAddOp3(v, OP_Subtract, regSampleno, regTemp2, regTemp2);
        sqlite3VdbeAddOp3(v, OP_Divide, regTemp2, regTemp, regTemp);
        sqlite3VdbeAddOp3(v, OP_Add, regSamplerecno, regTemp, regSamplerecno);

        sqlite3VdbeJumpHere(v, ne);
        sqlite3VdbeAddOp2(v, OP_AddImm, regRecno, 1);
#endif

        /* Always record the very first row */
        sqlite3VdbeAddOp1(v, OP_IfNot, iMem+1);
      }
      assert( pIdx->azColl!=0 );
      assert( pIdx->azColl[i]!=0 );
      pColl = sqlite3LocateCollSeq(pParse, pIdx->azColl[i]);
      sqlite3VdbeAddOp4(v, OP_Ne, regCol, 0, iMem+nCol+i+1,
                       (char*)pColl, P4_COLLSEQ);
      sqlite3VdbeChangeP5(v, SQLITE_NULLEQ);





    }
    if( db->mallocFailed ){
      /* If a malloc failure has occurred, then the result of the expression 
      ** passed as the second argument to the call to sqlite3VdbeJumpHere() 
      ** below may be negative. Which causes an assert() to fail (or an
      ** out-of-bounds write if SQLITE_DEBUG is not defined).  */
      return;
    }
    sqlite3VdbeAddOp2(v, OP_Goto, 0, endOfLoop);
    for(i=0; i<nCol; i++){
      int addr2 = sqlite3VdbeCurrentAddr(v) - (nCol*2);
      if( i==0 ){
        sqlite3VdbeJumpHere(v, addr2-1);  /* Set jump dest for the OP_IfNot */




      }
      sqlite3VdbeJumpHere(v, addr2);      /* Set jump dest for the OP_Ne */
      sqlite3VdbeAddOp2(v, OP_AddImm, iMem+i+1, 1);
      sqlite3VdbeAddOp3(v, OP_Column, iIdxCur, i, iMem+nCol+i+1);
    }


    /* End of the analysis loop. */

    sqlite3VdbeResolveLabel(v, endOfLoop);

























    sqlite3VdbeAddOp2(v, OP_Next, iIdxCur, topOfLoop);
    sqlite3VdbeAddOp1(v, OP_Close, iIdxCur);




    /* Store the results in sqlite_stat1.
    **
    ** The result is a single row of the sqlite_stat1 table.  The first
    ** two columns are the names of the table and index.  The third column
    ** is a string composed of a list of integer statistics about the
    ** index.  The first integer in the list is the total number of entries







|





<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<

|




|
|

>
>
>
>
>
|
<
<
<
<
<
|



|

|
>
>
>
>

<



>

<
>

>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>


>
>
>







359
360
361
362
363
364
365
366
367
368
369
370
371































372
373
374
375
376
377
378
379
380
381
382
383
384
385
386





387
388
389
390
391
392
393
394
395
396
397
398

399
400
401
402
403

404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
    }

    /* Start the analysis loop. This loop runs through all the entries in
    ** the index b-tree.  */
    endOfLoop = sqlite3VdbeMakeLabel(v);
    sqlite3VdbeAddOp2(v, OP_Rewind, iIdxCur, endOfLoop);
    topOfLoop = sqlite3VdbeCurrentAddr(v);
    sqlite3VdbeAddOp2(v, OP_AddImm, iMem, 1);  /* Increment row counter */

    for(i=0; i<nCol; i++){
      CollSeq *pColl;
      sqlite3VdbeAddOp3(v, OP_Column, iIdxCur, i, regCol);
      if( i==0 ){































        /* Always record the very first row */
        addrIfNot = sqlite3VdbeAddOp1(v, OP_IfNot, iMem+1);
      }
      assert( pIdx->azColl!=0 );
      assert( pIdx->azColl[i]!=0 );
      pColl = sqlite3LocateCollSeq(pParse, pIdx->azColl[i]);
      aChngAddr[i] = sqlite3VdbeAddOp4(v, OP_Ne, regCol, 0, iMem+nCol+i+1,
                                      (char*)pColl, P4_COLLSEQ);
      sqlite3VdbeChangeP5(v, SQLITE_NULLEQ);
      VdbeComment((v, "jump if column %d changed", i));
#ifdef SQLITE_ENABLE_STAT2
      if( i==0 && addrStoreStat2 ){
        sqlite3VdbeAddOp2(v, OP_AddImm, regSampleCnt, 1);
        VdbeComment((v, "incr repeat count"));
      }





#endif
    }
    sqlite3VdbeAddOp2(v, OP_Goto, 0, endOfLoop);
    for(i=0; i<nCol; i++){
      sqlite3VdbeJumpHere(v, aChngAddr[i]);  /* Set jump dest for the OP_Ne */
      if( i==0 ){
        sqlite3VdbeJumpHere(v, addrIfNot);   /* Jump dest for OP_IfNot */
#ifdef SQLITE_ENABLE_STAT2
        sqlite3VdbeAddOp2(v, OP_Gosub, regGosub, addrStoreStat2);
        sqlite3VdbeAddOp2(v, OP_Integer, 1, regSampleCnt);
#endif        
      }

      sqlite3VdbeAddOp2(v, OP_AddImm, iMem+i+1, 1);
      sqlite3VdbeAddOp3(v, OP_Column, iIdxCur, i, iMem+nCol+i+1);
    }
    sqlite3DbFree(db, aChngAddr);


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

#ifdef SQLITE_ENABLE_STAT2
    /* Check if the record that cursor iIdxCur points to contains a
    ** value that should be stored in the sqlite_stat2 table. If so,
    ** store it. 
    */
    int ne = sqlite3VdbeAddOp3(v, OP_Le, regNext, 0, iMem);
    VdbeComment((v, "jump if not a sample"));
    shortJump = sqlite3VdbeAddOp1(v, OP_If, regReady);
    sqlite3VdbeAddOp2(v, OP_Copy, iMem+nCol+1, regSample);
    sqlite3VdbeJumpHere(v, shortJump);
    sqlite3VdbeAddOp2(v, OP_AddImm, regReady, 1);

    /* Calculate new values for regNextSample.  Where N is the number
    ** of rows in the table and S is the number of samples to take:
    **
    **   nextSample = (sampleNumber*N*2 + N)/(2*S)
    */
    sqlite3VdbeAddOp2(v, OP_AddImm, regSampleIdx, 1);
    sqlite3VdbeAddOp3(v, OP_Multiply, regSampleIdx, regCount2, regNext);
    sqlite3VdbeAddOp3(v, OP_Add, regNext, regCount, regNext);
    sqlite3VdbeAddOp3(v, OP_Divide, regSample2, regNext, regNext);
    sqlite3VdbeJumpHere(v, ne);
#endif

    sqlite3VdbeAddOp2(v, OP_Next, iIdxCur, topOfLoop);
    sqlite3VdbeAddOp1(v, OP_Close, iIdxCur);
#ifdef SQLITE_ENABLE_STAT2
    sqlite3VdbeAddOp2(v, OP_Gosub, regGosub, addrStoreStat2);
#endif        

    /* Store the results in sqlite_stat1.
    **
    ** The result is a single row of the sqlite_stat1 table.  The first
    ** two columns are the names of the table and index.  The third column
    ** is a string composed of a list of integer statistics about the
    ** index.  The first integer in the list is the total number of entries
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
        if( (pIdx = sqlite3FindIndex(db, z, zDb))!=0 ){
          analyzeTable(pParse, pIdx->pTable, pIdx);
        }else if( (pTab = sqlite3LocateTable(pParse, 0, z, zDb))!=0 ){
          analyzeTable(pParse, pTab, 0);
        }
        sqlite3DbFree(db, z);
      }
    }   
  }
}

/*
** Used to pass information from the analyzer reader through to the
** callback routine.
*/







|







612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
        if( (pIdx = sqlite3FindIndex(db, z, zDb))!=0 ){
          analyzeTable(pParse, pIdx->pTable, pIdx);
        }else if( (pTab = sqlite3LocateTable(pParse, 0, z, zDb))!=0 ){
          analyzeTable(pParse, pTab, 0);
        }
        sqlite3DbFree(db, z);
      }
    }
  }
}

/*
** Used to pass information from the analyzer reader through to the
** callback routine.
*/
552
553
554
555
556
557
558

559









560








561


562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580























581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605

606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638

639
640
641
642
643
644
645
646


647
648
649
650
651
652
653
654
655
656
657



658
659

660
661
662

663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678

679

680


681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
      pIndex->bUnordered = 1;
      break;
    }
  }
  return 0;
}


/*









** If the Index.aSample variable is not NULL, delete the aSample[] array








** and its contents.


*/
void sqlite3DeleteIndexSamples(sqlite3 *db, Index *pIdx){
#ifdef SQLITE_ENABLE_STAT2
  if( pIdx->aSample ){
    int j;
    for(j=0; j<SQLITE_INDEX_SAMPLES; j++){
      IndexSample *p = &pIdx->aSample[j];
      if( p->eType==SQLITE_TEXT || p->eType==SQLITE_BLOB ){
        sqlite3DbFree(db, p->u.z);
      }
    }
    sqlite3DbFree(db, pIdx->aSample);
  }
#else
  UNUSED_PARAMETER(db);
  UNUSED_PARAMETER(pIdx);
#endif
}
























/*
** Load the content of the sqlite_stat1 and sqlite_stat2 tables. The
** contents of sqlite_stat1 are used to populate the Index.aiRowEst[]
** arrays. The contents of sqlite_stat2 are used to populate the
** Index.aSample[] arrays.
**
** If the sqlite_stat1 table is not present in the database, SQLITE_ERROR
** is returned. In this case, even if SQLITE_ENABLE_STAT2 was defined 
** during compilation and the sqlite_stat2 table is present, no data is 
** read from it.
**
** If SQLITE_ENABLE_STAT2 was defined during compilation and the 
** sqlite_stat2 table is not present in the database, SQLITE_ERROR is
** returned. However, in this case, data is read from the sqlite_stat1
** table (if it is present) before returning.
**
** If an OOM error occurs, this function always sets db->mallocFailed.
** This means if the caller does not care about other errors, the return
** code may be ignored.
*/
int sqlite3AnalysisLoad(sqlite3 *db, int iDb){
  analysisInfo sInfo;
  HashElem *i;
  char *zSql;
  int rc;


  assert( iDb>=0 && iDb<db->nDb );
  assert( db->aDb[iDb].pBt!=0 );

  /* Clear any prior statistics */
  assert( sqlite3SchemaMutexHeld(db, iDb, 0) );
  for(i=sqliteHashFirst(&db->aDb[iDb].pSchema->idxHash);i;i=sqliteHashNext(i)){
    Index *pIdx = sqliteHashData(i);
    sqlite3DefaultRowEst(pIdx);
    sqlite3DeleteIndexSamples(db, pIdx);
    pIdx->aSample = 0;
  }

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

  /* Load new statistics out of the sqlite_stat1 table */
  zSql = sqlite3MPrintf(db, 
      "SELECT tbl, idx, stat FROM %Q.sqlite_stat1", sInfo.zDatabase);
  if( zSql==0 ){
    rc = SQLITE_NOMEM;
  }else{
    rc = sqlite3_exec(db, zSql, analysisLoader, &sInfo, 0);
    sqlite3DbFree(db, zSql);
  }


  /* Load the statistics from the sqlite_stat2 table. */
#ifdef SQLITE_ENABLE_STAT2

  if( rc==SQLITE_OK && !sqlite3FindTable(db, "sqlite_stat2", sInfo.zDatabase) ){
    rc = SQLITE_ERROR;
  }
  if( rc==SQLITE_OK ){
    sqlite3_stmt *pStmt = 0;

    zSql = sqlite3MPrintf(db, 
        "SELECT idx,sampleno,sample FROM %Q.sqlite_stat2", sInfo.zDatabase);


    if( !zSql ){
      rc = SQLITE_NOMEM;
    }else{
      rc = sqlite3_prepare(db, zSql, -1, &pStmt, 0);
      sqlite3DbFree(db, zSql);
    }

    if( rc==SQLITE_OK ){
      while( sqlite3_step(pStmt)==SQLITE_ROW ){
        char *zIndex;   /* Index name */
        Index *pIdx;    /* Pointer to the index object */




        zIndex = (char *)sqlite3_column_text(pStmt, 0);

        pIdx = zIndex ? sqlite3FindIndex(db, zIndex, sInfo.zDatabase) : 0;
        if( pIdx ){
          int iSample = sqlite3_column_int(pStmt, 1);

          if( iSample<SQLITE_INDEX_SAMPLES && iSample>=0 ){
            int eType = sqlite3_column_type(pStmt, 2);

            if( pIdx->aSample==0 ){
              static const int sz = sizeof(IndexSample)*SQLITE_INDEX_SAMPLES;
              pIdx->aSample = (IndexSample *)sqlite3DbMallocRaw(0, sz);
              if( pIdx->aSample==0 ){
                db->mallocFailed = 1;
                break;
              }
	      memset(pIdx->aSample, 0, sz);
            }

            assert( pIdx->aSample );
            {
              IndexSample *pSample = &pIdx->aSample[iSample];

              pSample->eType = (u8)eType;

              if( eType==SQLITE_INTEGER || eType==SQLITE_FLOAT ){


                pSample->u.r = sqlite3_column_double(pStmt, 2);
              }else if( eType==SQLITE_TEXT || eType==SQLITE_BLOB ){
                const char *z = (const char *)(
                    (eType==SQLITE_BLOB) ?
                    sqlite3_column_blob(pStmt, 2):
                    sqlite3_column_text(pStmt, 2)
                );
                int n = sqlite3_column_bytes(pStmt, 2);
                if( n>24 ){
                  n = 24;
                }
                pSample->nByte = (u8)n;
                if( n < 1){
                  pSample->u.z = 0;
                }else{
                  pSample->u.z = sqlite3DbStrNDup(0, z, n);
                  if( pSample->u.z==0 ){
                    db->mallocFailed = 1;
                    break;
                  }
                }
              }
            }
          }
        }
      }
      rc = sqlite3_finalize(pStmt);
    }
  }







>

>
>
>
>
>
>
>
>
>
|
>
>
>
>
>
>
>
>
|
>
>



|
<
<
|
<
<
<
<
<
<






>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>




|




















>










<





|
















>
|






|
>
>











>
>
>


>
|
|
|
>
|
<
|
<
<
<
<
<
<
|
|
|
|
<
<
<
>
|
>
|
>
>
|
|
|
|
|
|
|
|
|
<
<
|
|
|
|
|
|
|
|
<
<
<







680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713


714






715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779

780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834

835






836
837
838
839



840
841
842
843
844
845
846
847
848
849
850
851
852
853
854


855
856
857
858
859
860
861
862



863
864
865
866
867
868
869
      pIndex->bUnordered = 1;
      break;
    }
  }
  return 0;
}

#if SQLITE_ENABLE_STAT2
/*
** Delete an array of IndexSample objects
*/
static void deleteIndexSampleArray(
  sqlite3 *db,                 /* The database connection */
  IndexSampleArray *pArray     /* Array of IndexSample objects */
){
  int j;
  if( pArray->a==0 ) return;
  for(j=0; j<pArray->n; j++){
    IndexSample *p = &pArray->a[j];
    if( p->eType==SQLITE_TEXT || p->eType==SQLITE_BLOB ){
      sqlite3_free(p->u.z);
    }
  }
  sqlite3_free(pArray->a);
  memset(pArray, 0, sizeof(*pArray));
}
#endif

/*
** Delete the sample and common-key arrays from the index.
*/
void sqlite3DeleteIndexSamples(sqlite3 *db, Index *pIdx){
#ifdef SQLITE_ENABLE_STAT2
  deleteIndexSampleArray(db, &pIdx->sample);


  deleteIndexSampleArray(db, &pIdx->comkey);






#else
  UNUSED_PARAMETER(db);
  UNUSED_PARAMETER(pIdx);
#endif
}

#ifdef SQLITE_ENABLE_STAT2
/*
** Enlarge an array of IndexSample objects.
*/
static IndexSample *allocIndexSample(
  sqlite3 *db,              /* Database connection to malloc against */
  IndexSampleArray *pArray, /* The array to enlarge */
  int i                     /* Return this element */
){
  IndexSample *p;
  if( i>=pArray->nAlloc ){
    int szNew = i+1;
    p = (IndexSample*)sqlite3_realloc(pArray->a, szNew*sizeof(IndexSample));
    if( p==0 ) return 0;
    pArray->a = p;
    memset(&pArray->a[pArray->n], 0, (szNew-(pArray->n))*sizeof(IndexSample));
    pArray->nAlloc = szNew;
  }
  if( i>=pArray->n ) pArray->n = i+1;
  return &pArray->a[i];
}
#endif

/*
** Load the content of the sqlite_stat1 and sqlite_stat2 tables. The
** contents of sqlite_stat1 are used to populate the Index.aiRowEst[]
** arrays. The contents of sqlite_stat2 are used to populate the
** Index.sample and Index.comkey arrays.
**
** If the sqlite_stat1 table is not present in the database, SQLITE_ERROR
** is returned. In this case, even if SQLITE_ENABLE_STAT2 was defined 
** during compilation and the sqlite_stat2 table is present, no data is 
** read from it.
**
** If SQLITE_ENABLE_STAT2 was defined during compilation and the 
** sqlite_stat2 table is not present in the database, SQLITE_ERROR is
** returned. However, in this case, data is read from the sqlite_stat1
** table (if it is present) before returning.
**
** If an OOM error occurs, this function always sets db->mallocFailed.
** This means if the caller does not care about other errors, the return
** code may be ignored.
*/
int sqlite3AnalysisLoad(sqlite3 *db, int iDb){
  analysisInfo sInfo;
  HashElem *i;
  char *zSql;
  int rc;
  Table *pTab;    /* Stat1 or Stat2 table */

  assert( iDb>=0 && iDb<db->nDb );
  assert( db->aDb[iDb].pBt!=0 );

  /* Clear any prior statistics */
  assert( sqlite3SchemaMutexHeld(db, iDb, 0) );
  for(i=sqliteHashFirst(&db->aDb[iDb].pSchema->idxHash);i;i=sqliteHashNext(i)){
    Index *pIdx = sqliteHashData(i);
    sqlite3DefaultRowEst(pIdx);
    sqlite3DeleteIndexSamples(db, pIdx);

  }

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

  /* Load new statistics out of the sqlite_stat1 table */
  zSql = sqlite3MPrintf(db, 
      "SELECT tbl, idx, stat FROM %Q.sqlite_stat1", sInfo.zDatabase);
  if( zSql==0 ){
    rc = SQLITE_NOMEM;
  }else{
    rc = sqlite3_exec(db, zSql, analysisLoader, &sInfo, 0);
    sqlite3DbFree(db, zSql);
  }


  /* Load the statistics from the sqlite_stat2 table. */
#ifdef SQLITE_ENABLE_STAT2
  if( rc==SQLITE_OK 
    && (pTab=sqlite3FindTable(db, "sqlite_stat2", sInfo.zDatabase))==0 ){
    rc = SQLITE_ERROR;
  }
  if( rc==SQLITE_OK ){
    sqlite3_stmt *pStmt = 0;

    zSql = sqlite3MPrintf(db, 
        "SELECT idx, sampleno, sample, %s FROM %Q.sqlite_stat2"
        " ORDER BY rowid DESC",
        pTab->nCol>=5 ? "cnt" : "0", sInfo.zDatabase);
    if( !zSql ){
      rc = SQLITE_NOMEM;
    }else{
      rc = sqlite3_prepare(db, zSql, -1, &pStmt, 0);
      sqlite3DbFree(db, zSql);
    }

    if( rc==SQLITE_OK ){
      while( sqlite3_step(pStmt)==SQLITE_ROW ){
        char *zIndex;   /* Index name */
        Index *pIdx;    /* Pointer to the index object */
        int iSample;
        int eType;
        IndexSample *pSample;

        zIndex = (char *)sqlite3_column_text(pStmt, 0);
        if( zIndex==0 ) continue;
        pIdx = sqlite3FindIndex(db, zIndex, sInfo.zDatabase);
        if( pIdx==0 ) continue;
        iSample = sqlite3_column_int(pStmt, 1);
        if( iSample>=SQLITE_MAX_SAMPLES ) continue;
        if( iSample<0 ){

          pSample = allocIndexSample(db, &pIdx->comkey, pIdx->comkey.n);






        }else{
          pSample = allocIndexSample(db, &pIdx->sample, iSample);
        }
        if( pSample==0 ) break;



        eType = sqlite3_column_type(pStmt, 2);
        pSample->eType = (u8)eType;
        pSample->nCopy = sqlite3_column_int(pStmt, 3);
        if( eType==SQLITE_INTEGER ){
          pSample->u.i = sqlite3_column_int64(pStmt, 2);
        }else if( eType==SQLITE_FLOAT ){
          pSample->u.r = sqlite3_column_double(pStmt, 2);
        }else if( eType==SQLITE_TEXT || eType==SQLITE_BLOB ){
          const char *z = (const char *)(
             (eType==SQLITE_BLOB) ?
              sqlite3_column_blob(pStmt, 2):
              sqlite3_column_text(pStmt, 2)
          );
          int n = sqlite3_column_bytes(pStmt, 2);
          if( n>255 ) n = 255;


          pSample->nByte = (u8)n;
          if( n < 1){
            pSample->u.z = 0;
          }else{
            pSample->u.z = sqlite3DbStrNDup(0, z, n);
            if( pSample->u.z==0 ){
              db->mallocFailed = 1;
              break;



            }
          }
        }
      }
      rc = sqlite3_finalize(pStmt);
    }
  }

Changes to src/sqliteInt.h.

77
78
79
80
81
82
83

84


85
86
87
88
89
90
91
#endif

/*
** The number of samples of an index that SQLite takes in order to 
** construct a histogram of the table content when running ANALYZE
** and with SQLITE_ENABLE_STAT2
*/

#define SQLITE_INDEX_SAMPLES 10



/*
** The following macros are used to cast pointers to integers and
** integers to pointers.  The way you do this varies from one compiler
** to the next, so we have developed the following set of #if statements
** to generate appropriate macros for a wide range of compilers.
**







>
|
>
>







77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
#endif

/*
** The number of samples of an index that SQLite takes in order to 
** construct a histogram of the table content when running ANALYZE
** and with SQLITE_ENABLE_STAT2
*/
#ifndef SQLITE_INDEX_SAMPLES
# define SQLITE_INDEX_SAMPLES 10
#endif
#define SQLITE_MAX_SAMPLES 100

/*
** The following macros are used to cast pointers to integers and
** integers to pointers.  The way you do this varies from one compiler
** to the next, so we have developed the following set of #if statements
** to generate appropriate macros for a wide range of compilers.
**
608
609
610
611
612
613
614

615
616
617
618
619
620
621
typedef struct FKey FKey;
typedef struct FuncDestructor FuncDestructor;
typedef struct FuncDef FuncDef;
typedef struct FuncDefHash FuncDefHash;
typedef struct IdList IdList;
typedef struct Index Index;
typedef struct IndexSample IndexSample;

typedef struct KeyClass KeyClass;
typedef struct KeyInfo KeyInfo;
typedef struct Lookaside Lookaside;
typedef struct LookasideSlot LookasideSlot;
typedef struct Module Module;
typedef struct NameContext NameContext;
typedef struct Parse Parse;







>







611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
typedef struct FKey FKey;
typedef struct FuncDestructor FuncDestructor;
typedef struct FuncDef FuncDef;
typedef struct FuncDefHash FuncDefHash;
typedef struct IdList IdList;
typedef struct Index Index;
typedef struct IndexSample IndexSample;
typedef struct IndexSampleArray IndexSampleArray;
typedef struct KeyClass KeyClass;
typedef struct KeyInfo KeyInfo;
typedef struct Lookaside Lookaside;
typedef struct LookasideSlot LookasideSlot;
typedef struct Module Module;
typedef struct NameContext NameContext;
typedef struct Parse Parse;
1443
1444
1445
1446
1447
1448
1449
























1450
1451
1452
1453
1454
1455
1456
#define UNPACKED_NEED_FREE     0x0001  /* Memory is from sqlite3Malloc() */
#define UNPACKED_NEED_DESTROY  0x0002  /* apMem[]s should all be destroyed */
#define UNPACKED_IGNORE_ROWID  0x0004  /* Ignore trailing rowid on key1 */
#define UNPACKED_INCRKEY       0x0008  /* Make this key an epsilon larger */
#define UNPACKED_PREFIX_MATCH  0x0010  /* A prefix match is considered OK */
#define UNPACKED_PREFIX_SEARCH 0x0020  /* A prefix match is considered OK */

























/*
** Each SQL index is represented in memory by an
** instance of the following structure.
**
** The columns of the table that are to be indexed are described
** by the aiColumn[] field of this structure.  For example, suppose
** we have the following table and index:







>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>







1447
1448
1449
1450
1451
1452
1453
1454
1455
1456
1457
1458
1459
1460
1461
1462
1463
1464
1465
1466
1467
1468
1469
1470
1471
1472
1473
1474
1475
1476
1477
1478
1479
1480
1481
1482
1483
1484
#define UNPACKED_NEED_FREE     0x0001  /* Memory is from sqlite3Malloc() */
#define UNPACKED_NEED_DESTROY  0x0002  /* apMem[]s should all be destroyed */
#define UNPACKED_IGNORE_ROWID  0x0004  /* Ignore trailing rowid on key1 */
#define UNPACKED_INCRKEY       0x0008  /* Make this key an epsilon larger */
#define UNPACKED_PREFIX_MATCH  0x0010  /* A prefix match is considered OK */
#define UNPACKED_PREFIX_SEARCH 0x0020  /* A prefix match is considered OK */

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

/*
** An array of IndexSample elements is as follows:
*/
struct IndexSampleArray {
  u16 n;            /* Number of elements in the array */
  u16 nAlloc;       /* Space allocated to a[] */
  IndexSample *a;   /* The samples */
};

/*
** Each SQL index is represented in memory by an
** instance of the following structure.
**
** The columns of the table that are to be indexed are described
** by the aiColumn[] field of this structure.  For example, suppose
** we have the following table and index:
1484
1485
1486
1487
1488
1489
1490
1491
1492
1493
1494
1495
1496
1497
1498
1499
1500
1501
1502
1503
1504
1505
1506
1507
1508
1509
1510
1511
  u8 autoIndex;    /* True if is automatically created (ex: by UNIQUE) */
  u8 bUnordered;   /* Use this index for == or IN queries only */
  char *zColAff;   /* String defining the affinity of each column */
  Index *pNext;    /* The next index associated with the same table */
  Schema *pSchema; /* Schema containing this index */
  u8 *aSortOrder;  /* Array of size Index.nColumn. True==DESC, False==ASC */
  char **azColl;   /* Array of collation sequence names for index */
  IndexSample *aSample;    /* Array of SQLITE_INDEX_SAMPLES samples */
};

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

/*
** Each token coming out of the lexer is an instance of
** this structure.  Tokens are also used as part of an expression.
**
** Note if Token.z==0 then Token.dyn and Token.n are undefined and







|
<
|
<
<
<
<
|
|
<
<
<
<
<







1512
1513
1514
1515
1516
1517
1518
1519

1520




1521
1522





1523
1524
1525
1526
1527
1528
1529
  u8 autoIndex;    /* True if is automatically created (ex: by UNIQUE) */
  u8 bUnordered;   /* Use this index for == or IN queries only */
  char *zColAff;   /* String defining the affinity of each column */
  Index *pNext;    /* The next index associated with the same table */
  Schema *pSchema; /* Schema containing this index */
  u8 *aSortOrder;  /* Array of size Index.nColumn. True==DESC, False==ASC */
  char **azColl;   /* Array of collation sequence names for index */
#ifdef SQLITE_ENABLE_STAT2

  IndexSampleArray sample;  /* Sampled histogram for the first column */




  IndexSampleArray comkey;  /* The most common keys */
#endif





};

/*
** Each token coming out of the lexer is an instance of
** this structure.  Tokens are also used as part of an expression.
**
** Note if Token.z==0 then Token.dyn and Token.n are undefined and

Changes to src/vdbe.c.

1049
1050
1051
1052
1053
1054
1055
1056
1057
1058
1059
1060
1061
1062
1063
*/
case OP_Copy: {             /* in1, out2 */
  pIn1 = &aMem[pOp->p1];
  pOut = &aMem[pOp->p2];
  assert( pOut!=pIn1 );
  sqlite3VdbeMemShallowCopy(pOut, pIn1, MEM_Ephem);
  Deephemeralize(pOut);
  REGISTER_TRACE(pOp->p2, pOut);
  break;
}

/* Opcode: SCopy P1 P2 * * *
**
** Make a shallow copy of register P1 into register P2.
**







<







1049
1050
1051
1052
1053
1054
1055

1056
1057
1058
1059
1060
1061
1062
*/
case OP_Copy: {             /* in1, out2 */
  pIn1 = &aMem[pOp->p1];
  pOut = &aMem[pOp->p2];
  assert( pOut!=pIn1 );
  sqlite3VdbeMemShallowCopy(pOut, pIn1, MEM_Ephem);
  Deephemeralize(pOut);

  break;
}

/* Opcode: SCopy P1 P2 * * *
**
** Make a shallow copy of register P1 into register P2.
**
1536
1537
1538
1539
1540
1541
1542

1543
1544
1545
1546
1547
1548
1549
** To force any register to be an integer, just add 0.
*/
case OP_AddImm: {            /* in1 */
  pIn1 = &aMem[pOp->p1];
  memAboutToChange(p, pIn1);
  sqlite3VdbeMemIntegerify(pIn1);
  pIn1->u.i += pOp->p2;

  break;
}

/* Opcode: MustBeInt P1 P2 * * *
** 
** Force the value in register P1 to be an integer.  If the value
** in P1 is not an integer and cannot be converted into an integer







>







1535
1536
1537
1538
1539
1540
1541
1542
1543
1544
1545
1546
1547
1548
1549
** To force any register to be an integer, just add 0.
*/
case OP_AddImm: {            /* in1 */
  pIn1 = &aMem[pOp->p1];
  memAboutToChange(p, pIn1);
  sqlite3VdbeMemIntegerify(pIn1);
  pIn1->u.i += pOp->p2;
  REGISTER_TRACE(pOp->p1, pIn1);
  break;
}

/* Opcode: MustBeInt P1 P2 * * *
** 
** Force the value in register P1 to be an integer.  If the value
** in P1 is not an integer and cannot be converted into an integer
2464
2465
2466
2467
2468
2469
2470

2471
2472
2473
2474
2475
2476
2477
  memAboutToChange(p, pOut);

  /* Loop through the elements that will make up the record to figure
  ** out how much space is required for the new record.
  */
  for(pRec=pData0; pRec<=pLast; pRec++){
    assert( memIsValid(pRec) );

    if( zAffinity ){
      applyAffinity(pRec, zAffinity[pRec-pData0], encoding);
    }
    if( pRec->flags&MEM_Zero && pRec->n>0 ){
      sqlite3VdbeMemExpandBlob(pRec);
    }
    serial_type = sqlite3VdbeSerialType(pRec, file_format);







>







2464
2465
2466
2467
2468
2469
2470
2471
2472
2473
2474
2475
2476
2477
2478
  memAboutToChange(p, pOut);

  /* Loop through the elements that will make up the record to figure
  ** out how much space is required for the new record.
  */
  for(pRec=pData0; pRec<=pLast; pRec++){
    assert( memIsValid(pRec) );
    REGISTER_TRACE((pRec-pData0)+pOp->p1, pRec);
    if( zAffinity ){
      applyAffinity(pRec, zAffinity[pRec-pData0], encoding);
    }
    if( pRec->flags&MEM_Zero && pRec->n>0 ){
      sqlite3VdbeMemExpandBlob(pRec);
    }
    serial_type = sqlite3VdbeSerialType(pRec, file_format);

Changes to src/where.c.

2418
2419
2420
2421
2422
2423
2424
2425
2426
2427
2428
2429
2430
2431





2432
2433
2434
2435
2436
2437
2438
2439
2440
2441
2442
2443
2444
2445
2446
2447
2448
2449
2450
2451

2452
2453
2454
2455

2456
2457
2458

2459












2460
2461
2462
2463

2464
2465
2466
2467
2468
2469
2470
2471

2472
2473
2474
2475
2476
2477
2478
2479
2480
2481
2482
2483
2484
2485
2486
2487
2488
2489
2490
2491
2492
2493
2494
2495
2496
2497
2498
2499
2500
2501
2502
2503
2504
2505
2506
2507
2508
2509
2510
  */
  bestOrClauseIndex(pParse, pWC, pSrc, notReady, notValid, pOrderBy, pCost);
}
#endif /* SQLITE_OMIT_VIRTUALTABLE */

/*
** Argument pIdx is a pointer to an index structure that has an array of
** SQLITE_INDEX_SAMPLES evenly spaced samples of the first indexed column
** stored in Index.aSample. These samples divide the domain of values stored
** the index into (SQLITE_INDEX_SAMPLES+1) regions.
** Region 0 contains all values less than the first sample value. Region
** 1 contains values between the first and second samples.  Region 2 contains
** values between samples 2 and 3.  And so on.  Region SQLITE_INDEX_SAMPLES
** contains values larger than the last sample.





**
** If the index contains many duplicates of a single value, then it is
** possible that two or more adjacent samples can hold the same value.
** When that is the case, the smallest possible region code is returned
** when roundUp is false and the largest possible region code is returned
** when roundUp is true.
**
** If successful, this function determines which of the regions value 
** pVal lies in, sets *piRegion to the region index (a value between 0
** and SQLITE_INDEX_SAMPLES+1, inclusive) and returns SQLITE_OK.
** Or, if an OOM occurs while converting text values between encodings,
** SQLITE_NOMEM is returned and *piRegion is undefined.
*/
#ifdef SQLITE_ENABLE_STAT2
static int whereRangeRegion(
  Parse *pParse,              /* Database connection */
  Index *pIdx,                /* Index to consider domain of */
  sqlite3_value *pVal,        /* Value to consider */
  int roundUp,                /* Return largest valid region if true */
  int *piRegion               /* OUT: Region of domain in which value lies */

){
  assert( roundUp==0 || roundUp==1 );
  if( ALWAYS(pVal) ){
    IndexSample *aSample = pIdx->aSample;

    int i = 0;
    int eType = sqlite3_value_type(pVal);


    if( eType==SQLITE_INTEGER || eType==SQLITE_FLOAT ){












      double r = sqlite3_value_double(pVal);
      for(i=0; i<SQLITE_INDEX_SAMPLES; i++){
        if( aSample[i].eType==SQLITE_NULL ) continue;
        if( aSample[i].eType>=SQLITE_TEXT ) break;

        if( roundUp ){
          if( aSample[i].u.r>r ) break;
        }else{
          if( aSample[i].u.r>=r ) break;
        }
      }
    }else if( eType==SQLITE_NULL ){
      i = 0;

      if( roundUp ){
        while( i<SQLITE_INDEX_SAMPLES && aSample[i].eType==SQLITE_NULL ) i++;
      }
    }else{ 
      sqlite3 *db = pParse->db;
      CollSeq *pColl;
      const u8 *z;
      int n;

      /* pVal comes from sqlite3ValueFromExpr() so the type cannot be NULL */
      assert( eType==SQLITE_TEXT || eType==SQLITE_BLOB );

      if( eType==SQLITE_BLOB ){
        z = (const u8 *)sqlite3_value_blob(pVal);
        pColl = db->pDfltColl;
        assert( pColl->enc==SQLITE_UTF8 );
      }else{
        pColl = sqlite3GetCollSeq(db, SQLITE_UTF8, 0, *pIdx->azColl);
        if( pColl==0 ){
          sqlite3ErrorMsg(pParse, "no such collation sequence: %s",
                          *pIdx->azColl);
          return SQLITE_ERROR;
        }
        z = (const u8 *)sqlite3ValueText(pVal, pColl->enc);
        if( !z ){
          return SQLITE_NOMEM;
        }
        assert( z && pColl && pColl->xCmp );
      }
      n = sqlite3ValueBytes(pVal, pColl->enc);

      for(i=0; i<SQLITE_INDEX_SAMPLES; i++){
        int c;
        int eSampletype = aSample[i].eType;
        if( eSampletype==SQLITE_NULL || eSampletype<eType ) continue;
        if( (eSampletype!=eType) ) break;
#ifndef SQLITE_OMIT_UTF16
        if( pColl->enc!=SQLITE_UTF8 ){
          int nSample;







|
|
<
|
|
|
|
>
>
>
>
>









|









|
>



|
>



>
|
>
>
>
>
>
>
>
>
>
>
>
>

|


>








>

|







<

<



















|







2418
2419
2420
2421
2422
2423
2424
2425
2426

2427
2428
2429
2430
2431
2432
2433
2434
2435
2436
2437
2438
2439
2440
2441
2442
2443
2444
2445
2446
2447
2448
2449
2450
2451
2452
2453
2454
2455
2456
2457
2458
2459
2460
2461
2462
2463
2464
2465
2466
2467
2468
2469
2470
2471
2472
2473
2474
2475
2476
2477
2478
2479
2480
2481
2482
2483
2484
2485
2486
2487
2488
2489
2490
2491
2492
2493
2494
2495
2496
2497
2498
2499
2500
2501

2502

2503
2504
2505
2506
2507
2508
2509
2510
2511
2512
2513
2514
2515
2516
2517
2518
2519
2520
2521
2522
2523
2524
2525
2526
2527
2528
2529
  */
  bestOrClauseIndex(pParse, pWC, pSrc, notReady, notValid, pOrderBy, pCost);
}
#endif /* SQLITE_OMIT_VIRTUALTABLE */

/*
** Argument pIdx is a pointer to an index structure that has an array of
** pIdx->sample.n (hereafter "S") evenly spaced samples of the first indexed
** column stored in Index.sample. These samples divide the domain of values

** stored the index into S+1 regions.  Region 0 contains all values less than
** the first sample value. Region 1 contains values between the first and
** second samples.  Region 2 contains values between samples 2 and 3.  And so
** on.  Region S contains values larger than the last sample.
**
** Note that samples are computed as being centered on S buckets where each
** bucket contains the nearly same number of rows.  This routine takes samples
** to be dividers between regions, though.  Hence, region 0 and region S
** contain half as many rows as the interior regions.
**
** If the index contains many duplicates of a single value, then it is
** possible that two or more adjacent samples can hold the same value.
** When that is the case, the smallest possible region code is returned
** when roundUp is false and the largest possible region code is returned
** when roundUp is true.
**
** If successful, this function determines which of the regions value 
** pVal lies in, sets *piRegion to the region index (a value between 0
** and S, inclusive) and returns SQLITE_OK.
** Or, if an OOM occurs while converting text values between encodings,
** SQLITE_NOMEM is returned and *piRegion is undefined.
*/
#ifdef SQLITE_ENABLE_STAT2
static int whereRangeRegion(
  Parse *pParse,              /* Database connection */
  Index *pIdx,                /* Index to consider domain of */
  sqlite3_value *pVal,        /* Value to consider */
  int roundUp,                /* Return largest valid region if true */
  int *piRegion,              /* OUT: Region of domain in which value lies */
  u32 *pnCopy                 /* OUT: Number of rows with pVal, or -1 if unk */
){
  assert( roundUp==0 || roundUp==1 );
  if( ALWAYS(pVal) ){
    IndexSample *aSample = pIdx->sample.a;
    int nSample = pIdx->sample.n;
    int i = 0;
    int eType = sqlite3_value_type(pVal);

    assert( nSample>0 );
    if( eType==SQLITE_INTEGER ){
      i64 x = sqlite3_value_int64(pVal);
      for(i=0; i<nSample; i++){
        if( aSample[i].eType==SQLITE_NULL ) continue;
        if( aSample[i].eType>=SQLITE_TEXT ) break;
        if( aSample[i].u.i==x ) *pnCopy = aSample[i].nCopy;
        if( roundUp ){
          if( aSample[i].u.i>x ) break;
        }else{
          if( aSample[i].u.i>=x ) break;
        }
      }
    }else if( eType==SQLITE_FLOAT ){
      double r = sqlite3_value_double(pVal);
      for(i=0; i<nSample; i++){
        if( aSample[i].eType==SQLITE_NULL ) continue;
        if( aSample[i].eType>=SQLITE_TEXT ) break;
        if( aSample[i].u.r==r ) *pnCopy = aSample[i].nCopy;
        if( roundUp ){
          if( aSample[i].u.r>r ) break;
        }else{
          if( aSample[i].u.r>=r ) break;
        }
      }
    }else if( eType==SQLITE_NULL ){
      i = 0;
      if( aSample[0].eType==SQLITE_NULL ) *pnCopy = aSample[0].nCopy;
      if( roundUp ){
        while( i<nSample && aSample[i].eType==SQLITE_NULL ) i++;
      }
    }else{ 
      sqlite3 *db = pParse->db;
      CollSeq *pColl;
      const u8 *z;
      int n;


      assert( eType==SQLITE_TEXT || eType==SQLITE_BLOB );

      if( eType==SQLITE_BLOB ){
        z = (const u8 *)sqlite3_value_blob(pVal);
        pColl = db->pDfltColl;
        assert( pColl->enc==SQLITE_UTF8 );
      }else{
        pColl = sqlite3GetCollSeq(db, SQLITE_UTF8, 0, *pIdx->azColl);
        if( pColl==0 ){
          sqlite3ErrorMsg(pParse, "no such collation sequence: %s",
                          *pIdx->azColl);
          return SQLITE_ERROR;
        }
        z = (const u8 *)sqlite3ValueText(pVal, pColl->enc);
        if( !z ){
          return SQLITE_NOMEM;
        }
        assert( z && pColl && pColl->xCmp );
      }
      n = sqlite3ValueBytes(pVal, pColl->enc);

      for(i=0; i<nSample; i++){
        int c;
        int eSampletype = aSample[i].eType;
        if( eSampletype==SQLITE_NULL || eSampletype<eType ) continue;
        if( (eSampletype!=eType) ) break;
#ifndef SQLITE_OMIT_UTF16
        if( pColl->enc!=SQLITE_UTF8 ){
          int nSample;
2518
2519
2520
2521
2522
2523
2524

2525
2526
2527
2528
2529
2530
2531
2532
2533
2534
2535
2536
          c = pColl->xCmp(pColl->pUser, nSample, zSample, n, z);
          sqlite3DbFree(db, zSample);
        }else
#endif
        {
          c = pColl->xCmp(pColl->pUser, aSample[i].nByte, aSample[i].u.z, n, z);
        }

        if( c-roundUp>=0 ) break;
      }
    }

    assert( i>=0 && i<=SQLITE_INDEX_SAMPLES );
    *piRegion = i;
  }
  return SQLITE_OK;
}
#endif   /* #ifdef SQLITE_ENABLE_STAT2 */

/*







>




|







2537
2538
2539
2540
2541
2542
2543
2544
2545
2546
2547
2548
2549
2550
2551
2552
2553
2554
2555
2556
          c = pColl->xCmp(pColl->pUser, nSample, zSample, n, z);
          sqlite3DbFree(db, zSample);
        }else
#endif
        {
          c = pColl->xCmp(pColl->pUser, aSample[i].nByte, aSample[i].u.z, n, z);
        }
        if( c==0 ) *pnCopy = aSample[i].nCopy;
        if( c-roundUp>=0 ) break;
      }
    }

    assert( i>=0 && i<=pIdx->sample.n );
    *piRegion = i;
  }
  return SQLITE_OK;
}
#endif   /* #ifdef SQLITE_ENABLE_STAT2 */

/*
2617
2618
2619
2620
2621
2622
2623
2624
2625
2626
2627
2628

2629
2630
2631

2632
2633
2634
2635
2636
2637
2638
2639
2640
2641
2642
2643
2644
2645
2646
2647
2648
2649
2650
2651
2652
2653
2654
2655
2656
2657
2658
2659
2660
2661
2662
2663
2664
2665
2666
2667

2668
2669
2670
2671
2672
2673
2674
2675
2676
2677
2678
  WhereTerm *pUpper,   /* Upper bound on the range. ex: "x<455" Might be NULL */
  int *piEst           /* OUT: Return value */
){
  int rc = SQLITE_OK;

#ifdef SQLITE_ENABLE_STAT2

  if( nEq==0 && p->aSample ){
    sqlite3_value *pLowerVal = 0;
    sqlite3_value *pUpperVal = 0;
    int iEst;
    int iLower = 0;

    int iUpper = SQLITE_INDEX_SAMPLES;
    int roundUpUpper = 0;
    int roundUpLower = 0;

    u8 aff = p->pTable->aCol[p->aiColumn[0]].affinity;

    if( pLower ){
      Expr *pExpr = pLower->pExpr->pRight;
      rc = valueFromExpr(pParse, pExpr, aff, &pLowerVal);
      assert( pLower->eOperator==WO_GT || pLower->eOperator==WO_GE );
      roundUpLower = (pLower->eOperator==WO_GT) ?1:0;
    }
    if( rc==SQLITE_OK && pUpper ){
      Expr *pExpr = pUpper->pExpr->pRight;
      rc = valueFromExpr(pParse, pExpr, aff, &pUpperVal);
      assert( pUpper->eOperator==WO_LT || pUpper->eOperator==WO_LE );
      roundUpUpper = (pUpper->eOperator==WO_LE) ?1:0;
    }

    if( rc!=SQLITE_OK || (pLowerVal==0 && pUpperVal==0) ){
      sqlite3ValueFree(pLowerVal);
      sqlite3ValueFree(pUpperVal);
      goto range_est_fallback;
    }else if( pLowerVal==0 ){
      rc = whereRangeRegion(pParse, p, pUpperVal, roundUpUpper, &iUpper);
      if( pLower ) iLower = iUpper/2;
    }else if( pUpperVal==0 ){
      rc = whereRangeRegion(pParse, p, pLowerVal, roundUpLower, &iLower);
      if( pUpper ) iUpper = (iLower + SQLITE_INDEX_SAMPLES + 1)/2;
    }else{
      rc = whereRangeRegion(pParse, p, pUpperVal, roundUpUpper, &iUpper);
      if( rc==SQLITE_OK ){
        rc = whereRangeRegion(pParse, p, pLowerVal, roundUpLower, &iLower);
      }
    }
    WHERETRACE(("range scan regions: %d..%d\n", iLower, iUpper));

    iEst = iUpper - iLower;
    testcase( iEst==SQLITE_INDEX_SAMPLES );
    assert( iEst<=SQLITE_INDEX_SAMPLES );

    if( iEst<1 ){
      *piEst = 50/SQLITE_INDEX_SAMPLES;
    }else{
      *piEst = (iEst*100)/SQLITE_INDEX_SAMPLES;
    }
    sqlite3ValueFree(pLowerVal);
    sqlite3ValueFree(pUpperVal);
    return rc;
  }
range_est_fallback:
#else







|




>
|


>




















|


|
|

|

|



<

|
|
>

|

|







2637
2638
2639
2640
2641
2642
2643
2644
2645
2646
2647
2648
2649
2650
2651
2652
2653
2654
2655
2656
2657
2658
2659
2660
2661
2662
2663
2664
2665
2666
2667
2668
2669
2670
2671
2672
2673
2674
2675
2676
2677
2678
2679
2680
2681
2682
2683
2684
2685

2686
2687
2688
2689
2690
2691
2692
2693
2694
2695
2696
2697
2698
2699
2700
  WhereTerm *pUpper,   /* Upper bound on the range. ex: "x<455" Might be NULL */
  int *piEst           /* OUT: Return value */
){
  int rc = SQLITE_OK;

#ifdef SQLITE_ENABLE_STAT2

  if( nEq==0 && p->sample.a ){
    sqlite3_value *pLowerVal = 0;
    sqlite3_value *pUpperVal = 0;
    int iEst;
    int iLower = 0;
    int nSample = p->sample.n;
    int iUpper = p->sample.n;
    int roundUpUpper = 0;
    int roundUpLower = 0;
    u32 nC = 0;
    u8 aff = p->pTable->aCol[p->aiColumn[0]].affinity;

    if( pLower ){
      Expr *pExpr = pLower->pExpr->pRight;
      rc = valueFromExpr(pParse, pExpr, aff, &pLowerVal);
      assert( pLower->eOperator==WO_GT || pLower->eOperator==WO_GE );
      roundUpLower = (pLower->eOperator==WO_GT) ?1:0;
    }
    if( rc==SQLITE_OK && pUpper ){
      Expr *pExpr = pUpper->pExpr->pRight;
      rc = valueFromExpr(pParse, pExpr, aff, &pUpperVal);
      assert( pUpper->eOperator==WO_LT || pUpper->eOperator==WO_LE );
      roundUpUpper = (pUpper->eOperator==WO_LE) ?1:0;
    }

    if( rc!=SQLITE_OK || (pLowerVal==0 && pUpperVal==0) ){
      sqlite3ValueFree(pLowerVal);
      sqlite3ValueFree(pUpperVal);
      goto range_est_fallback;
    }else if( pLowerVal==0 ){
      rc = whereRangeRegion(pParse, p, pUpperVal, roundUpUpper, &iUpper, &nC);
      if( pLower ) iLower = iUpper/2;
    }else if( pUpperVal==0 ){
      rc = whereRangeRegion(pParse, p, pLowerVal, roundUpLower, &iLower, &nC);
      if( pUpper ) iUpper = (iLower + p->sample.n + 1)/2;
    }else{
      rc = whereRangeRegion(pParse, p, pUpperVal, roundUpUpper, &iUpper, &nC);
      if( rc==SQLITE_OK ){
        rc = whereRangeRegion(pParse, p, pLowerVal, roundUpLower, &iLower, &nC);
      }
    }
    WHERETRACE(("range scan regions: %d..%d\n", iLower, iUpper));

    iEst = iUpper - iLower;
    testcase( iEst==nSample );
    assert( iEst<=nSample );
    assert( nSample>0 );
    if( iEst<1 ){
      *piEst = 50/nSample;
    }else{
      *piEst = (iEst*100)/nSample;
    }
    sqlite3ValueFree(pLowerVal);
    sqlite3ValueFree(pUpperVal);
    return rc;
  }
range_est_fallback:
#else
2712
2713
2714
2715
2716
2717
2718

2719
2720

2721
2722
2723
2724
2725
2726
2727
2728
2729
2730

2731
2732





2733
2734
2735
2736
2737
2738
2739

2740
2741
2742
2743
2744
2745
2746
  double *pnRow        /* Write the revised row estimate here */
){
  sqlite3_value *pRhs = 0;  /* VALUE on right-hand side of pTerm */
  int iLower, iUpper;       /* Range of histogram regions containing pRhs */
  u8 aff;                   /* Column affinity */
  int rc;                   /* Subfunction return code */
  double nRowEst;           /* New estimate of the number of rows */


  assert( p->aSample!=0 );

  aff = p->pTable->aCol[p->aiColumn[0]].affinity;
  if( pExpr ){
    rc = valueFromExpr(pParse, pExpr, aff, &pRhs);
    if( rc ) goto whereEqualScanEst_cancel;
  }else{
    pRhs = sqlite3ValueNew(pParse->db);
  }
  if( pRhs==0 ) return SQLITE_NOTFOUND;
  rc = whereRangeRegion(pParse, p, pRhs, 0, &iLower);
  if( rc ) goto whereEqualScanEst_cancel;

  rc = whereRangeRegion(pParse, p, pRhs, 1, &iUpper);
  if( rc ) goto whereEqualScanEst_cancel;





  WHERETRACE(("equality scan regions: %d..%d\n", iLower, iUpper));
  if( iLower>=iUpper ){
    nRowEst = p->aiRowEst[0]/(SQLITE_INDEX_SAMPLES*2);
    if( nRowEst<*pnRow ) *pnRow = nRowEst;
  }else{
    nRowEst = (iUpper-iLower)*p->aiRowEst[0]/SQLITE_INDEX_SAMPLES;
    *pnRow = nRowEst;

  }

whereEqualScanEst_cancel:
  sqlite3ValueFree(pRhs);
  return rc;
}
#endif /* defined(SQLITE_ENABLE_STAT2) */







>

|
>








|

>
|
|
>
>
>
>
>
|
|
|
|
|
|
|
>







2734
2735
2736
2737
2738
2739
2740
2741
2742
2743
2744
2745
2746
2747
2748
2749
2750
2751
2752
2753
2754
2755
2756
2757
2758
2759
2760
2761
2762
2763
2764
2765
2766
2767
2768
2769
2770
2771
2772
2773
2774
2775
2776
2777
  double *pnRow        /* Write the revised row estimate here */
){
  sqlite3_value *pRhs = 0;  /* VALUE on right-hand side of pTerm */
  int iLower, iUpper;       /* Range of histogram regions containing pRhs */
  u8 aff;                   /* Column affinity */
  int rc;                   /* Subfunction return code */
  double nRowEst;           /* New estimate of the number of rows */
  u32 nC = 0;               /* Key copy count */

  assert( p->sample.a!=0 );
  assert( p->sample.n>0 );
  aff = p->pTable->aCol[p->aiColumn[0]].affinity;
  if( pExpr ){
    rc = valueFromExpr(pParse, pExpr, aff, &pRhs);
    if( rc ) goto whereEqualScanEst_cancel;
  }else{
    pRhs = sqlite3ValueNew(pParse->db);
  }
  if( pRhs==0 ) return SQLITE_NOTFOUND;
  rc = whereRangeRegion(pParse, p, pRhs, 0, &iLower, &nC);
  if( rc ) goto whereEqualScanEst_cancel;
  if( nC==0 ){
    rc = whereRangeRegion(pParse, p, pRhs, 1, &iUpper, &nC);
    if( rc ) goto whereEqualScanEst_cancel;
  }
  if( nC ){
    WHERETRACE(("equality scan count: %u\n", nC));
    *pnRow = nC;
  }else{
    WHERETRACE(("equality scan regions: %d..%d\n", iLower, iUpper));
    if( iLower>=iUpper ){
      nRowEst = p->aiRowEst[0]/(p->sample.n*3);
      if( nRowEst<*pnRow ) *pnRow = nRowEst;
    }else{
      nRowEst = (iUpper-iLower)*p->aiRowEst[0]/p->sample.n;
      *pnRow = nRowEst;
    }
  }

whereEqualScanEst_cancel:
  sqlite3ValueFree(pRhs);
  return rc;
}
#endif /* defined(SQLITE_ENABLE_STAT2) */
2772
2773
2774
2775
2776
2777
2778
2779


2780
2781
2782
2783

2784
2785
2786
2787
2788
2789
2790
2791
2792
2793
2794
2795
2796
2797
2798
2799
2800
2801
2802
2803
2804
2805
2806
2807
2808
2809
2810
2811
2812
2813
2814
2815
2816
2817
2818
2819
2820
2821
  int iLower, iUpper;       /* Range of histogram regions containing pRhs */
  u8 aff;                   /* Column affinity */
  int rc = SQLITE_OK;       /* Subfunction return code */
  double nRowEst;           /* New estimate of the number of rows */
  int nSpan = 0;            /* Number of histogram regions spanned */
  int nSingle = 0;          /* Histogram regions hit by a single value */
  int nNotFound = 0;        /* Count of values that are not constants */
  int i;                               /* Loop counter */


  u8 aSpan[SQLITE_INDEX_SAMPLES+1];    /* Histogram regions that are spanned */
  u8 aSingle[SQLITE_INDEX_SAMPLES+1];  /* Histogram regions hit once */

  assert( p->aSample!=0 );

  aff = p->pTable->aCol[p->aiColumn[0]].affinity;
  memset(aSpan, 0, sizeof(aSpan));
  memset(aSingle, 0, sizeof(aSingle));
  for(i=0; i<pList->nExpr; i++){
    sqlite3ValueFree(pVal);
    rc = valueFromExpr(pParse, pList->a[i].pExpr, aff, &pVal);
    if( rc ) break;
    if( pVal==0 || sqlite3_value_type(pVal)==SQLITE_NULL ){
      nNotFound++;
      continue;
    }
    rc = whereRangeRegion(pParse, p, pVal, 0, &iLower);
    if( rc ) break;
    rc = whereRangeRegion(pParse, p, pVal, 1, &iUpper);
    if( rc ) break;
    if( iLower>=iUpper ){
      aSingle[iLower] = 1;
    }else{
      assert( iLower>=0 && iUpper<=SQLITE_INDEX_SAMPLES );
      while( iLower<iUpper ) aSpan[iLower++] = 1;
    }
  }
  if( rc==SQLITE_OK ){
    for(i=nSpan=0; i<=SQLITE_INDEX_SAMPLES; i++){
      if( aSpan[i] ){
        nSpan++;
      }else if( aSingle[i] ){
        nSingle++;
      }
    }
    nRowEst = (nSpan*2+nSingle)*p->aiRowEst[0]/(2*SQLITE_INDEX_SAMPLES)
               + nNotFound*p->aiRowEst[1];
    if( nRowEst > p->aiRowEst[0] ) nRowEst = p->aiRowEst[0];
    *pnRow = nRowEst;
    WHERETRACE(("IN row estimate: nSpan=%d, nSingle=%d, nNotFound=%d, est=%g\n",
                 nSpan, nSingle, nNotFound, nRowEst));
  }
  sqlite3ValueFree(pVal);







|
>
>
|
|

|
>

|
|








|

|




|




|






|







2803
2804
2805
2806
2807
2808
2809
2810
2811
2812
2813
2814
2815
2816
2817
2818
2819
2820
2821
2822
2823
2824
2825
2826
2827
2828
2829
2830
2831
2832
2833
2834
2835
2836
2837
2838
2839
2840
2841
2842
2843
2844
2845
2846
2847
2848
2849
2850
2851
2852
2853
2854
2855
  int iLower, iUpper;       /* Range of histogram regions containing pRhs */
  u8 aff;                   /* Column affinity */
  int rc = SQLITE_OK;       /* Subfunction return code */
  double nRowEst;           /* New estimate of the number of rows */
  int nSpan = 0;            /* Number of histogram regions spanned */
  int nSingle = 0;          /* Histogram regions hit by a single value */
  int nNotFound = 0;        /* Count of values that are not constants */
  int i;                             /* Loop counter */
  u32 nC;                            /* Exact count of rows for a key */
  int nSample = p->sample.n;         /* Number of samples */
  u8 aSpan[SQLITE_MAX_SAMPLES+1];    /* Histogram regions that are spanned */
  u8 aSingle[SQLITE_MAX_SAMPLES+1];  /* Histogram regions hit once */

  assert( p->sample.a!=0 );
  assert( nSample>0 );
  aff = p->pTable->aCol[p->aiColumn[0]].affinity;
  memset(aSpan, 0, nSample+1);
  memset(aSingle, 0, nSample+1);
  for(i=0; i<pList->nExpr; i++){
    sqlite3ValueFree(pVal);
    rc = valueFromExpr(pParse, pList->a[i].pExpr, aff, &pVal);
    if( rc ) break;
    if( pVal==0 || sqlite3_value_type(pVal)==SQLITE_NULL ){
      nNotFound++;
      continue;
    }
    rc = whereRangeRegion(pParse, p, pVal, 0, &iLower, &nC);
    if( rc ) break;
    rc = whereRangeRegion(pParse, p, pVal, 1, &iUpper, &nC);
    if( rc ) break;
    if( iLower>=iUpper ){
      aSingle[iLower] = 1;
    }else{
      assert( iLower>=0 && iUpper<=nSample );
      while( iLower<iUpper ) aSpan[iLower++] = 1;
    }
  }
  if( rc==SQLITE_OK ){
    for(i=nSpan=0; i<=nSample; i++){
      if( aSpan[i] ){
        nSpan++;
      }else if( aSingle[i] ){
        nSingle++;
      }
    }
    nRowEst = (nSpan*3+nSingle)*p->aiRowEst[0]/(3*nSample)
               + nNotFound*p->aiRowEst[1];
    if( nRowEst > p->aiRowEst[0] ) nRowEst = p->aiRowEst[0];
    *pnRow = nRowEst;
    WHERETRACE(("IN row estimate: nSpan=%d, nSingle=%d, nNotFound=%d, est=%g\n",
                 nSpan, nSingle, nNotFound, nRowEst));
  }
  sqlite3ValueFree(pVal);
3025
3026
3027
3028
3029
3030
3031
3032
3033
3034
3035
3036
3037
3038
3039
          /* "x IN (value, value, ...)" */
          nInMul *= pExpr->x.pList->nExpr;
        }
      }else if( pTerm->eOperator & WO_ISNULL ){
        wsFlags |= WHERE_COLUMN_NULL;
      }
#ifdef SQLITE_ENABLE_STAT2
      if( nEq==0 && pProbe->aSample ) pFirstTerm = pTerm;
#endif
      used |= pTerm->prereqRight;
    }

    /* Determine the value of estBound. */
    if( nEq<pProbe->nColumn && pProbe->bUnordered==0 ){
      int j = pProbe->aiColumn[nEq];







|







3059
3060
3061
3062
3063
3064
3065
3066
3067
3068
3069
3070
3071
3072
3073
          /* "x IN (value, value, ...)" */
          nInMul *= pExpr->x.pList->nExpr;
        }
      }else if( pTerm->eOperator & WO_ISNULL ){
        wsFlags |= WHERE_COLUMN_NULL;
      }
#ifdef SQLITE_ENABLE_STAT2
      if( nEq==0 && pProbe->sample.a ) pFirstTerm = pTerm;
#endif
      used |= pTerm->prereqRight;
    }

    /* Determine the value of estBound. */
    if( nEq<pProbe->nColumn && pProbe->bUnordered==0 ){
      int j = pProbe->aiColumn[nEq];

Changes to test/analyze2.test.

67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
do_test analyze2-1.1 {
  execsql { CREATE TABLE t1(x PRIMARY KEY) }
  for {set i 0} {$i < 1000} {incr i} {
    execsql { INSERT INTO t1 VALUES($i) }
  }
  execsql { 
    ANALYZE;
    SELECT * FROM sqlite_stat2;
  }
} [list t1 sqlite_autoindex_t1_1 0 50  \
        t1 sqlite_autoindex_t1_1 1 149 \
        t1 sqlite_autoindex_t1_1 2 249 \
        t1 sqlite_autoindex_t1_1 3 349 \
        t1 sqlite_autoindex_t1_1 4 449 \
        t1 sqlite_autoindex_t1_1 5 549 \
        t1 sqlite_autoindex_t1_1 6 649 \
        t1 sqlite_autoindex_t1_1 7 749 \
        t1 sqlite_autoindex_t1_1 8 849 \
        t1 sqlite_autoindex_t1_1 9 949 \
]

do_test analyze2-1.2 {
  execsql {
    DELETE FROM t1 WHERe x>9;
    ANALYZE;
    SELECT tbl, idx, group_concat(sample, ' ') FROM sqlite_stat2;
  }
} {t1 sqlite_autoindex_t1_1 {0 1 2 3 4 5 6 7 8 9}}
do_test analyze2-1.3 {
  execsql {
    DELETE FROM t1 WHERE x>8;
    ANALYZE;
    SELECT * FROM sqlite_stat2;
  }
} {}







|


|
|
|
|
|
|
|
|
|




|



|







67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
do_test analyze2-1.1 {
  execsql { CREATE TABLE t1(x PRIMARY KEY) }
  for {set i 0} {$i < 1000} {incr i} {
    execsql { INSERT INTO t1 VALUES($i) }
  }
  execsql { 
    ANALYZE;
    SELECT tbl, idx, sampleno, sample FROM sqlite_stat2;
  }
} [list t1 sqlite_autoindex_t1_1 0 50  \
        t1 sqlite_autoindex_t1_1 1 150 \
        t1 sqlite_autoindex_t1_1 2 250 \
        t1 sqlite_autoindex_t1_1 3 350 \
        t1 sqlite_autoindex_t1_1 4 450 \
        t1 sqlite_autoindex_t1_1 5 550 \
        t1 sqlite_autoindex_t1_1 6 650 \
        t1 sqlite_autoindex_t1_1 7 750 \
        t1 sqlite_autoindex_t1_1 8 850 \
        t1 sqlite_autoindex_t1_1 9 950 \
]

do_test analyze2-1.2 {
  execsql {
    DELETE FROM t1 WHERE x>20;
    ANALYZE;
    SELECT tbl, idx, group_concat(sample, ' ') FROM sqlite_stat2;
  }
} {t1 sqlite_autoindex_t1_1 {1 3 5 7 9 11 13 15 17 19}}
do_test analyze2-1.3 {
  execsql {
    DELETE FROM t1 WHERE x>8;
    ANALYZE;
    SELECT * FROM sqlite_stat2;
  }
} {}
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
  execsql ANALYZE
  execsql { 
    SELECT tbl,idx,group_concat(sample,' ') 
    FROM sqlite_stat2 
    WHERE idx = 't1_x' 
    GROUP BY tbl,idx
  }
} {t1 t1_x {100 299 499 699 899 ajj cjj ejj gjj ijj}}
do_test analyze2-3.2 {
  execsql { 
    SELECT tbl,idx,group_concat(sample,' ') 
    FROM sqlite_stat2 
    WHERE idx = 't1_y' 
    GROUP BY tbl,idx
  }
} {t1 t1_y {100 299 499 699 899 ajj cjj ejj gjj ijj}}

do_eqp_test 3.3 {
  SELECT * FROM t1 WHERE x BETWEEN 100 AND 500 AND y BETWEEN 'a' AND 'b'
} {
  0 0 0 {SEARCH TABLE t1 USING INDEX t1_y (y>? AND y<?) (~50 rows)}
}
do_eqp_test 3.4 {
  SELECT * FROM t1 WHERE x BETWEEN 100 AND 400 AND y BETWEEN 'a' AND 'h'
} {
  0 0 0 {SEARCH TABLE t1 USING INDEX t1_x (x>? AND x<?) (~100 rows)}
}
do_eqp_test 3.5 {
  SELECT * FROM t1 WHERE x<'a' AND y>'h'
} {
  0 0 0 {SEARCH TABLE t1 USING INDEX t1_y (y>?) (~66 rows)}
}
do_eqp_test 3.6 {
  SELECT * FROM t1 WHERE x<444 AND y>'h'
} {
  0 0 0 {SEARCH TABLE t1 USING INDEX t1_y (y>?) (~66 rows)}
}
do_eqp_test 3.7 {
  SELECT * FROM t1 WHERE x<221 AND y>'g'
} {
  0 0 0 {SEARCH TABLE t1 USING INDEX t1_x (x<?) (~66 rows)}
}








|







|




|









|




|







185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
  execsql ANALYZE
  execsql { 
    SELECT tbl,idx,group_concat(sample,' ') 
    FROM sqlite_stat2 
    WHERE idx = 't1_x' 
    GROUP BY tbl,idx
  }
} {t1 t1_x {100 300 500 700 900 baa daa faa haa jaa}}
do_test analyze2-3.2 {
  execsql { 
    SELECT tbl,idx,group_concat(sample,' ') 
    FROM sqlite_stat2 
    WHERE idx = 't1_y' 
    GROUP BY tbl,idx
  }
} {t1 t1_y {100 300 500 700 900 baa daa faa haa jaa}}

do_eqp_test 3.3 {
  SELECT * FROM t1 WHERE x BETWEEN 100 AND 500 AND y BETWEEN 'a' AND 'b'
} {
  0 0 0 {SEARCH TABLE t1 USING INDEX t1_y (y>? AND y<?) (~25 rows)}
}
do_eqp_test 3.4 {
  SELECT * FROM t1 WHERE x BETWEEN 100 AND 400 AND y BETWEEN 'a' AND 'h'
} {
  0 0 0 {SEARCH TABLE t1 USING INDEX t1_x (x>? AND x<?) (~100 rows)}
}
do_eqp_test 3.5 {
  SELECT * FROM t1 WHERE x<'a' AND y>'h'
} {
  0 0 0 {SEARCH TABLE t1 USING INDEX t1_y (y>?) (~133 rows)}
}
do_eqp_test 3.6 {
  SELECT * FROM t1 WHERE x<444 AND y>'h'
} {
  0 0 0 {SEARCH TABLE t1 USING INDEX t1_y (y>?) (~133 rows)}
}
do_eqp_test 3.7 {
  SELECT * FROM t1 WHERE x<221 AND y>'g'
} {
  0 0 0 {SEARCH TABLE t1 USING INDEX t1_x (x<?) (~66 rows)}
}

245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
    PRAGMA automatic_index=OFF;
    SELECT tbl,idx,group_concat(sample,' ') 
    FROM sqlite_stat2 
    WHERE idx = 't3a' 
    GROUP BY tbl,idx;
    PRAGMA automatic_index=ON;
  }
} {t3 t3a {AfA bEj CEj dEj EEj fEj GEj hEj IEj jEj}}
do_test analyze2-4.3 {
  execsql { 
    SELECT tbl,idx,group_concat(sample,' ') 
    FROM sqlite_stat2 
    WHERE idx = 't3b' 
    GROUP BY tbl,idx
  }
} {t3 t3b {AbA CIj EIj GIj IIj bIj dIj fIj hIj jIj}}

do_eqp_test 4.4 {
  SELECT * FROM t3 WHERE a > 'A' AND a < 'C' AND b > 'A' AND b < 'C'
} {
  0 0 0 {SEARCH TABLE t3 USING INDEX t3b (b>? AND b<?) (~11 rows)}
}
do_eqp_test 4.5 {







|







|







245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
    PRAGMA automatic_index=OFF;
    SELECT tbl,idx,group_concat(sample,' ') 
    FROM sqlite_stat2 
    WHERE idx = 't3a' 
    GROUP BY tbl,idx;
    PRAGMA automatic_index=ON;
  }
} {t3 t3a {AfA bfA CfA dfA EfA ffA GfA hfA IfA jfA}}
do_test analyze2-4.3 {
  execsql { 
    SELECT tbl,idx,group_concat(sample,' ') 
    FROM sqlite_stat2 
    WHERE idx = 't3b' 
    GROUP BY tbl,idx
  }
} {t3 t3b {AbA CbA EbA GbA IbA bbA dbA fbA hbA jbA}}

do_eqp_test 4.4 {
  SELECT * FROM t3 WHERE a > 'A' AND a < 'C' AND b > 'A' AND b < 'C'
} {
  0 0 0 {SEARCH TABLE t3 USING INDEX t3b (b>? AND b<?) (~11 rows)}
}
do_eqp_test 4.5 {
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
  do_test analyze2-5.2 {
    execsql { 
      SELECT tbl,idx,group_concat(sample,' ') 
      FROM sqlite_stat2 
      WHERE tbl = 't4' 
      GROUP BY tbl,idx
    }
  } {t4 t4x {afa bej cej dej eej fej gej hej iej jej}}
  do_eqp_test 5.3 {
    SELECT * FROM t4 WHERE x>'ccc'
  } {0 0 0 {SEARCH TABLE t4 USING COVERING INDEX t4x (x>?) (~800 rows)}}
  do_eqp_test 5.4 {
    SELECT * FROM t4 AS t41, t4 AS t42 WHERE t41.x>'ccc' AND t42.x>'ggg'
  } {
    0 0 1 {SEARCH TABLE t4 AS t42 USING COVERING INDEX t4x (x>?) (~300 rows)} 







|







293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
  do_test analyze2-5.2 {
    execsql { 
      SELECT tbl,idx,group_concat(sample,' ') 
      FROM sqlite_stat2 
      WHERE tbl = 't4' 
      GROUP BY tbl,idx
    }
  } {t4 t4x {afa bfa cfa dfa efa ffa gfa hfa ifa jfa}}
  do_eqp_test 5.3 {
    SELECT * FROM t4 WHERE x>'ccc'
  } {0 0 0 {SEARCH TABLE t4 USING COVERING INDEX t4x (x>?) (~800 rows)}}
  do_eqp_test 5.4 {
    SELECT * FROM t4 AS t41, t4 AS t42 WHERE t41.x>'ccc' AND t42.x>'ggg'
  } {
    0 0 1 {SEARCH TABLE t4 AS t42 USING COVERING INDEX t4x (x>?) (~300 rows)} 

Changes to test/analyze5.test.

124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
   47  {z>=-100 AND z<=0.0}  t1z  400
   48  {z>=-100 AND z<0.0}   t1z   50
   49  {z>=-100 AND z<=1.0}  t1z  700
   50  {z>=-100 AND z<2.0}   t1z  700
   51  {z>=-100 AND z<=2.0}  t1z  900
   52  {z>=-100 AND z<3.0}   t1z  900
  
  101  {z=-1}                t1z   50
  102  {z=0}                 t1z  400
  103  {z=1}                 t1z  300
  104  {z=2}                 t1z  200
  105  {z=3}                 t1z  100
  106  {z=4}                 t1z   50
  107  {z=-10.0}             t1z   50
  108  {z=0.0}               t1z  400
  109  {z=1.0}               t1z  300
  110  {z=2.0}               t1z  200
  111  {z=3.0}               t1z  100
  112  {z=4.0}               t1z   50
  113  {z=1.5}               t1z   50
  114  {z=2.5}               t1z   50
  
  201  {z IN (-1)}           t1z   50
  202  {z IN (0)}            t1z  400
  203  {z IN (1)}            t1z  300
  204  {z IN (2)}            t1z  200
  205  {z IN (3)}            t1z  100
  206  {z IN (4)}            t1z   50
  207  {z IN (0.5)}          t1z   50
  208  {z IN (0,1)}          t1z  700
  209  {z IN (0,1,2)}        t1z  900
  210  {z IN (0,1,2,3)}      {}   100
  211  {z IN (0,1,2,3,4,5)}  {}   100
  212  {z IN (1,2)}          t1z  500
  213  {z IN (2,3)}          t1z  300
  214  {z=3 OR z=2}          t1z  300
  215  {z IN (-1,3)}         t1z  150
  216  {z=-1 OR z=3}         t1z  150

  300  {y=0}                 {}   100
  301  {y=1}                 t1y   50
  302  {y=0.1}               t1y   50

  400  {x IS NULL}           t1x  400

} {
  # Verify that the expected index is used with the expected row count
  do_test analyze5-1.${testid}a {
    set x [lindex [eqp "SELECT * FROM t1 WHERE $where"] 3]







|




|
|




|
|
|

|




|
|







|
|


|
|







124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
   47  {z>=-100 AND z<=0.0}  t1z  400
   48  {z>=-100 AND z<0.0}   t1z   50
   49  {z>=-100 AND z<=1.0}  t1z  700
   50  {z>=-100 AND z<2.0}   t1z  700
   51  {z>=-100 AND z<=2.0}  t1z  900
   52  {z>=-100 AND z<3.0}   t1z  900
  
  101  {z=-1}                t1z   33
  102  {z=0}                 t1z  400
  103  {z=1}                 t1z  300
  104  {z=2}                 t1z  200
  105  {z=3}                 t1z  100
  106  {z=4}                 t1z   33
  107  {z=-10.0}             t1z   33
  108  {z=0.0}               t1z  400
  109  {z=1.0}               t1z  300
  110  {z=2.0}               t1z  200
  111  {z=3.0}               t1z  100
  112  {z=4.0}               t1z   33
  113  {z=1.5}               t1z   33
  114  {z=2.5}               t1z   33
  
  201  {z IN (-1)}           t1z   33
  202  {z IN (0)}            t1z  400
  203  {z IN (1)}            t1z  300
  204  {z IN (2)}            t1z  200
  205  {z IN (3)}            t1z  100
  206  {z IN (4)}            t1z   33
  207  {z IN (0.5)}          t1z   33
  208  {z IN (0,1)}          t1z  700
  209  {z IN (0,1,2)}        t1z  900
  210  {z IN (0,1,2,3)}      {}   100
  211  {z IN (0,1,2,3,4,5)}  {}   100
  212  {z IN (1,2)}          t1z  500
  213  {z IN (2,3)}          t1z  300
  214  {z=3 OR z=2}          t1z  300
  215  {z IN (-1,3)}         t1z  133
  216  {z=-1 OR z=3}         t1z  133

  300  {y=0}                 {}   100
  301  {y=1}                 t1y   33
  302  {y=0.1}               t1y   33

  400  {x IS NULL}           t1x  400

} {
  # Verify that the expected index is used with the expected row count
  do_test analyze5-1.${testid}a {
    set x [lindex [eqp "SELECT * FROM t1 WHERE $where"] 3]
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
   ANALYZE;
}

# Verify that range queries generate the correct row count estimates
#
foreach {testid where index rows} {
  500  {x IS NULL AND u='charlie'}         t1u  20
  501  {x=1 AND u='charlie'}               t1x   5
  502  {x IS NULL}                          {} 100
  503  {x=1}                               t1x  50
  504  {x IS NOT NULL}                     t1x  25
  505  {+x IS NOT NULL}                     {} 500
  506  {upper(x) IS NOT NULL}               {} 500

} {
  # Verify that the expected index is used with the expected row count
  do_test analyze5-1.${testid}a {







|

|







201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
   ANALYZE;
}

# Verify that range queries generate the correct row count estimates
#
foreach {testid where index rows} {
  500  {x IS NULL AND u='charlie'}         t1u  20
  501  {x=1 AND u='charlie'}               t1x   3
  502  {x IS NULL}                          {} 100
  503  {x=1}                               t1x  33
  504  {x IS NOT NULL}                     t1x  25
  505  {+x IS NOT NULL}                     {} 500
  506  {upper(x) IS NOT NULL}               {} 500

} {
  # Verify that the expected index is used with the expected row count
  do_test analyze5-1.${testid}a {

Changes to test/analyze7.test.

95
96
97
98
99
100
101
102


103
104
105
106
107
108
109
110
    execsql {EXPLAIN QUERY PLAN SELECT * FROM t1 WHERE c=2;}
  } {0 0 0 {SEARCH TABLE t1 USING INDEX t1cd (c=?) (~86 rows)}}
}
do_test analyze7-3.3 {
  execsql {EXPLAIN QUERY PLAN SELECT * FROM t1 WHERE a=123 AND b=123}
} {0 0 0 {SEARCH TABLE t1 USING INDEX t1a (a=?) (~1 rows)}}
do_test analyze7-3.4 {
  execsql {EXPLAIN QUERY PLAN SELECT * FROM t1 WHERE c=123 AND b=123}


} {0 0 0 {SEARCH TABLE t1 USING INDEX t1b (b=?) (~2 rows)}}
do_test analyze7-3.5 {
  execsql {EXPLAIN QUERY PLAN SELECT * FROM t1 WHERE a=123 AND c=123}
} {0 0 0 {SEARCH TABLE t1 USING INDEX t1a (a=?) (~1 rows)}}
do_test analyze7-3.6 {
  execsql {EXPLAIN QUERY PLAN SELECT * FROM t1 WHERE c=123 AND d=123 AND b=123}
} {0 0 0 {SEARCH TABLE t1 USING INDEX t1cd (c=? AND d=?) (~1 rows)}}








|
>
>
|







95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
    execsql {EXPLAIN QUERY PLAN SELECT * FROM t1 WHERE c=2;}
  } {0 0 0 {SEARCH TABLE t1 USING INDEX t1cd (c=?) (~86 rows)}}
}
do_test analyze7-3.3 {
  execsql {EXPLAIN QUERY PLAN SELECT * FROM t1 WHERE a=123 AND b=123}
} {0 0 0 {SEARCH TABLE t1 USING INDEX t1a (a=?) (~1 rows)}}
do_test analyze7-3.4 {
  set x [execsql {EXPLAIN QUERY PLAN SELECT * FROM t1 WHERE c=123 AND b=123}]
  regsub -all {[bcd]+} $x {x} x
  set x
} {0 0 0 {SEARCH TABLE t1 USING INDEX t1x (x=?) (~2 rows)}}
do_test analyze7-3.5 {
  execsql {EXPLAIN QUERY PLAN SELECT * FROM t1 WHERE a=123 AND c=123}
} {0 0 0 {SEARCH TABLE t1 USING INDEX t1a (a=?) (~1 rows)}}
do_test analyze7-3.6 {
  execsql {EXPLAIN QUERY PLAN SELECT * FROM t1 WHERE c=123 AND d=123 AND b=123}
} {0 0 0 {SEARCH TABLE t1 USING INDEX t1cd (c=? AND d=?) (~1 rows)}}

Added test/analyze8.test.



















































































































































































































































































































































































































>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
# 2011 August 5
#
# The author disclaims copyright to this source code.  In place of
# a legal notice, here is a blessing:
#
#    May you do good and not evil.
#    May you find forgiveness for yourself and forgive others.
#    May you share freely, never taking more than you give.
#
#***********************************************************************
# This file implements regression tests for SQLite library.
# This file implements tests for the ANALYZE command under STAT2.
# Testing the logic that computes the number of copies of each sample.
#

set testdir [file dirname $argv0]
source $testdir/tester.tcl

# There is nothing to test if ANALYZE is disable for this build.
#
ifcapable {!analyze||!vtab||!stat2} {
  finish_test
  return
}

# Generate some test data
#
do_test analyze8-1.0 {
  set x 100
  set y 1
  set ycnt 0
  set yinc 10
  execsql {
    CREATE TABLE t1(x,y);
    ANALYZE;
    BEGIN;
    CREATE INDEX t1x ON t1(x);
    CREATE INDEX t1y ON t1(y);
  }
  for {set i 0} {$i<20} {incr i} {
    for {set j 0} {$j<300} {incr j} {
      execsql {INSERT INTO t1 VALUES($x,$y)}
      incr ycnt
      if {$ycnt>=$yinc} {set ycnt 0; incr y}
    }
    for {set j 0} {$j<100} {incr j} {
      incr x
      execsql {INSERT INTO t1 VALUES($x,$y)}
      incr ycnt
      if {$ycnt>=$yinc} {set ycnt 0; incr y}
    }
  }
  execsql {
    COMMIT;
    ANALYZE;
    SELECT sample, cnt FROM sqlite_stat2 WHERE idx='t1x' ORDER BY sampleno;
  }
} {200 301 400 301 600 301 800 301 1000 301 1200 301 1400 301 1600 301 1800 301 2000 301}
do_test analyze8-1.1 {
  execsql {
    SELECT count(*) FROM t1 WHERE x=200;
  }
} {301}

do_test analyze8-2.0 {
  execsql {
    BEGIN;
    DELETE FROM t1;
  }
  for {set x 1} {$x<200} {incr x} {
    execsql {INSERT INTO t1 VALUES($x,$x)}
  }
  for {set i 0} {$i<200} {incr i} {
    execsql {INSERT INTO t1 VALUES(999,999)}
  }
  execsql {
    COMMIT;
    ANALYZE;
    SELECT sample, cnt FROM sqlite_stat2 WHERE idx='t1x' ORDER BY sampleno;
  }
} {20 1 60 1 100 1 140 1 180 1 999 200 999 200 999 200 999 200 999 200}
do_test analyze8-2.1 {
  for {set i 0} {$i<200} {incr i} {
    execsql {INSERT INTO t1 VALUES(0,999)}
  }
  execsql {
    ANALYZE;
    SELECT sample, cnt FROM sqlite_stat2 WHERE idx='t1x' ORDER BY sampleno;
  }
} {0 200 0 200 0 200 10 1 70 1 130 1 190 1 999 200 999 200 999 200}

do_test analyze8-3.0 {
  execsql {
    BEGIN;
    DROP TABLE t1;
    CREATE TABLE t1(a,b);
    CREATE INDEX t1all ON t1(a,b);
    INSERT INTO t1 VALUES(0,1);
    INSERT INTO t1 VALUES(0,2);
    INSERT INTO t1 VALUES(0,3);
    INSERT INTO t1 VALUES(1,4);
    INSERT INTO t1 SELECT a+2, b+4 FROM t1;
    INSERT INTO t1 SELECT a+4, b+8 FROM t1;
    INSERT INTO t1 SELECT a+8, b+16 FROM t1;
    COMMIT;
    ANALYZE;
    SELECT sample, cnt FROM sqlite_stat2 WHERE idx='t1all' ORDER BY sampleno;
  }
} {0 3 2 3 4 3 5 1 6 3 8 3 10 3 12 3 13 1 14 3}
do_test analyze8-3.1 {
  execsql {
    DELETE FROM t1;
    INSERT INTO t1 VALUES(1,1);
    INSERT INTO t1 VALUES(2,2);
    INSERT INTO t1 SELECT a+2, b+2 FROM t1;
    INSERT INTO t1 SELECT a+4, b+4 FROM t1;
    INSERT INTO t1 SELECT a+8, b+8 FROM t1;
    INSERT INTO t1 SELECT a+16, b+16 FROM t1;
    DELETE FROM t1 WHERE a>21;
    ANALYZE;
    SELECT sample, cnt FROM sqlite_stat2 WHERE idx='t1all' ORDER BY sampleno;
  }
} {2 1 4 1 6 1 8 1 10 1 12 1 14 1 16 1 18 1 20 1}
do_test analyze8-3.2 {
  execsql {
    UPDATE t1 SET a=123;
    ANALYZE;
    SELECT sample, cnt FROM sqlite_stat2 WHERE idx='t1all' ORDER BY sampleno;
  }
} {123 21 123 21 123 21 123 21 123 21 123 21 123 21 123 21 123 21 123 21}
do_test analyze8-3.3 {
  execsql {
    DELETE FROM t1 WHERE b=1 OR b=2;
    ANALYZE;
    SELECT count(*) FROM t1;
    SELECT sample, cnt FROM sqlite_stat2 WHERE idx='t1all' ORDER BY sampleno;
  }
} {19}
do_test analyze8-3.4 {
  execsql {
    UPDATE t1 SET a=b;
    INSERT INTO t1 VALUES(1,1);
    INSERT INTO t1 VALUES(2,2);
    INSERT INTO t1 SELECT a, b FROM t1;
    ANALYZE;
    SELECT sample, cnt FROM sqlite_stat2 WHERE idx='t1all' ORDER BY sampleno;
  }
} {2 2 4 2 6 2 8 2 10 2 12 2 14 2 16 2 18 2 20 2}
do_test analyze8-3.5 {
  execsql {
    UPDATE t1 SET a=1 WHERE b<20;
    ANALYZE;
    SELECT sample, cnt FROM sqlite_stat2 WHERE idx='t1all' ORDER BY sampleno;
  }
} {1 38 1 38 1 38 1 38 1 38 1 38 1 38 1 38 1 38 20 2}
do_test analyze8-3.6 {
  execsql {
    UPDATE t1 SET a=b;
    UPDATE t1 SET a=20 WHERE b>2;
    ANALYZE;
    SELECT sample, cnt FROM sqlite_stat2 WHERE idx='t1all' ORDER BY sampleno;
  }
} {2 2 20 38 20 38 20 38 20 38 20 38 20 38 20 38 20 38 20 38}



# Verify that the 5th "cnt" column is added to the sqlite_stat2 table
# on a full ANALYZE if the column is not already present.
#
do_test analyze8-4.0 {
  execsql {
    UPDATE t1 SET a=b;
    ANALYZE;
    PRAGMA writable_schema=ON;
    UPDATE sqlite_master 
       SET sql='CREATE TABLE sqlite_stat2(tbl,idx,sampleno,sample)'
     WHERE name='sqlite_stat2';
  }
  db close
  sqlite3 db test.db
  execsql {
    SELECT sample FROM sqlite_stat2 WHERE idx='t1all' ORDER BY sampleno
  }
} {2 4 6 8 10 12 14 16 18 20}
do_test analyze8-4.1 {
  catchsql {SELECT sample, cnt FROM sqlite_stat2}
} {1 {no such column: cnt}}
do_test analyze8-4.2 {
  execsql {
    ANALYZE;
  }
  db close;
  sqlite3 db test.db
  execsql {
    SELECT sample, +cnt FROM sqlite_stat2 WHERE idx='t1all' ORDER BY sampleno;
  }
} {2 2 4 2 6 2 8 2 10 2 12 2 14 2 16 2 18 2 20 2}



finish_test

Changes to test/tkt-cbd054fa6b.test.

31
32
33
34
35
36
37










38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69










70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
    INSERT INTO t1 VALUES (NULL, 'C');
    INSERT INTO t1 VALUES (NULL, 'D');
    INSERT INTO t1 VALUES (NULL, 'E');
    INSERT INTO t1 VALUES (NULL, 'F');
    INSERT INTO t1 VALUES (NULL, 'G');
    INSERT INTO t1 VALUES (NULL, 'H');
    INSERT INTO t1 VALUES (NULL, 'I');










    SELECT count(*) FROM t1;
  }
} {10}
do_test tkt-cbd05-1.2 {
  db eval {
    ANALYZE;
  }
} {}
do_test tkt-cbd05-1.3 {
  execsql { 
    SELECT tbl,idx,group_concat(sample,' ') 
    FROM sqlite_stat2 
    WHERE idx = 't1_x' 
    GROUP BY tbl,idx
  }
} {t1 t1_x { A B C D E F G H I}}

do_test tkt-cbd05-2.1 {
  db eval {
    DROP TABLE t1;
    CREATE TABLE t1(a INTEGER PRIMARY KEY, b BLOB UNIQUE NOT NULL);
    CREATE INDEX t1_x ON t1(b);
    INSERT INTO t1 VALUES(NULL, X'');
    INSERT INTO t1 VALUES(NULL, X'41');
    INSERT INTO t1 VALUES(NULL, X'42');
    INSERT INTO t1 VALUES(NULL, X'43');
    INSERT INTO t1 VALUES(NULL, X'44');
    INSERT INTO t1 VALUES(NULL, X'45');
    INSERT INTO t1 VALUES(NULL, X'46');
    INSERT INTO t1 VALUES(NULL, X'47');
    INSERT INTO t1 VALUES(NULL, X'48');
    INSERT INTO t1 VALUES(NULL, X'49');










    SELECT count(*) FROM t1;
  }
} {10}
do_test tkt-cbd05-2.2 {
  db eval {
    ANALYZE;
  }
} {}
do_test tkt-cbd05-2.3 {
  execsql { 
    SELECT tbl,idx,group_concat(sample,' ') 
    FROM sqlite_stat2 
    WHERE idx = 't1_x' 
    GROUP BY tbl,idx
  }
} {t1 t1_x { A B C D E F G H I}}

finish_test







>
>
>
>
>
>
>
>
>
>


|












|
















>
>
>
>
>
>
>
>
>
>


|












|


31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
    INSERT INTO t1 VALUES (NULL, 'C');
    INSERT INTO t1 VALUES (NULL, 'D');
    INSERT INTO t1 VALUES (NULL, 'E');
    INSERT INTO t1 VALUES (NULL, 'F');
    INSERT INTO t1 VALUES (NULL, 'G');
    INSERT INTO t1 VALUES (NULL, 'H');
    INSERT INTO t1 VALUES (NULL, 'I');
    INSERT INTO t1 VALUES (NULL, 'J');
    INSERT INTO t1 VALUES (NULL, 'K');
    INSERT INTO t1 VALUES (NULL, 'L');
    INSERT INTO t1 VALUES (NULL, 'M');
    INSERT INTO t1 VALUES (NULL, 'N');
    INSERT INTO t1 VALUES (NULL, 'O');
    INSERT INTO t1 VALUES (NULL, 'P');
    INSERT INTO t1 VALUES (NULL, 'Q');
    INSERT INTO t1 VALUES (NULL, 'R');
    INSERT INTO t1 VALUES (NULL, 'S');
    SELECT count(*) FROM t1;
  }
} {20}
do_test tkt-cbd05-1.2 {
  db eval {
    ANALYZE;
  }
} {}
do_test tkt-cbd05-1.3 {
  execsql { 
    SELECT tbl,idx,group_concat(sample,' ') 
    FROM sqlite_stat2 
    WHERE idx = 't1_x' 
    GROUP BY tbl,idx
  }
} {t1 t1_x {A C E G I K M O Q S}}

do_test tkt-cbd05-2.1 {
  db eval {
    DROP TABLE t1;
    CREATE TABLE t1(a INTEGER PRIMARY KEY, b BLOB UNIQUE NOT NULL);
    CREATE INDEX t1_x ON t1(b);
    INSERT INTO t1 VALUES(NULL, X'');
    INSERT INTO t1 VALUES(NULL, X'41');
    INSERT INTO t1 VALUES(NULL, X'42');
    INSERT INTO t1 VALUES(NULL, X'43');
    INSERT INTO t1 VALUES(NULL, X'44');
    INSERT INTO t1 VALUES(NULL, X'45');
    INSERT INTO t1 VALUES(NULL, X'46');
    INSERT INTO t1 VALUES(NULL, X'47');
    INSERT INTO t1 VALUES(NULL, X'48');
    INSERT INTO t1 VALUES(NULL, X'49');
    INSERT INTO t1 VALUES(NULL, X'4A');
    INSERT INTO t1 VALUES(NULL, X'4B');
    INSERT INTO t1 VALUES(NULL, X'4C');
    INSERT INTO t1 VALUES(NULL, X'4D');
    INSERT INTO t1 VALUES(NULL, X'4E');
    INSERT INTO t1 VALUES(NULL, X'4F');
    INSERT INTO t1 VALUES(NULL, X'50');
    INSERT INTO t1 VALUES(NULL, X'51');
    INSERT INTO t1 VALUES(NULL, X'52');
    INSERT INTO t1 VALUES(NULL, X'53');
    SELECT count(*) FROM t1;
  }
} {20}
do_test tkt-cbd05-2.2 {
  db eval {
    ANALYZE;
  }
} {}
do_test tkt-cbd05-2.3 {
  execsql { 
    SELECT tbl,idx,group_concat(sample,' ') 
    FROM sqlite_stat2 
    WHERE idx = 't1_x' 
    GROUP BY tbl,idx
  }
} {t1 t1_x {A C E G I K M O Q S}}

finish_test