1/*
2** 2005-07-08
3**
4** The author disclaims copyright to this source code. In place of
5** a legal notice, here is a blessing:
6**
7** May you do good and not evil.
8** May you find forgiveness for yourself and forgive others.
9** May you share freely, never taking more than you give.
10**
11*************************************************************************
12** This file contains code associated with the ANALYZE command.
13**
14** The ANALYZE command gather statistics about the content of tables
15** and indices. These statistics are made available to the query planner
16** to help it make better decisions about how to perform queries.
17**
18** The following system tables are or have been supported:
19**
20** CREATE TABLE sqlite_stat1(tbl, idx, stat);
21** CREATE TABLE sqlite_stat2(tbl, idx, sampleno, sample);
22** CREATE TABLE sqlite_stat3(tbl, idx, nEq, nLt, nDLt, sample);
23** CREATE TABLE sqlite_stat4(tbl, idx, nEq, nLt, nDLt, sample);
24**
25** Additional tables might be added in future releases of SQLite.
26** The sqlite_stat2 table is not created or used unless the SQLite version
27** is between 3.6.18 and 3.7.8, inclusive, and unless SQLite is compiled
28** with SQLITE_ENABLE_STAT2. The sqlite_stat2 table is deprecated.
29** The sqlite_stat2 table is superseded by sqlite_stat3, which is only
30** created and used by SQLite versions 3.7.9 through 3.29.0 when
31** SQLITE_ENABLE_STAT3 defined. The functionality of sqlite_stat3
32** is a superset of sqlite_stat2 and is also now deprecated. The
33** sqlite_stat4 is an enhanced version of sqlite_stat3 and is only
34** available when compiled with SQLITE_ENABLE_STAT4 and in SQLite
35** versions 3.8.1 and later. STAT4 is the only variant that is still
36** supported.
37**
38** For most applications, sqlite_stat1 provides all the statistics required
39** for the query planner to make good choices.
40**
41** Format of sqlite_stat1:
42**
43** There is normally one row per index, with the index identified by the
44** name in the idx column. The tbl column is the name of the table to
45** which the index belongs. In each such row, the stat column will be
46** a string consisting of a list of integers. The first integer in this
47** list is the number of rows in the index. (This is the same as the
48** number of rows in the table, except for partial indices.) The second
49** integer is the average number of rows in the index that have the same
50** value in the first column of the index. The third integer is the average
51** number of rows in the index that have the same value for the first two
52** columns. The N-th integer (for N>1) is the average number of rows in
53** the index which have the same value for the first N-1 columns. For
54** a K-column index, there will be K+1 integers in the stat column. If
55** the index is unique, then the last integer will be 1.
56**
57** The list of integers in the stat column can optionally be followed
58** by the keyword "unordered". The "unordered" keyword, if it is present,
59** must be separated from the last integer by a single space. If the
60** "unordered" keyword is present, then the query planner assumes that
61** the index is unordered and will not use the index for a range query.
62**
63** If the sqlite_stat1.idx column is NULL, then the sqlite_stat1.stat
64** column contains a single integer which is the (estimated) number of
65** rows in the table identified by sqlite_stat1.tbl.
66**
67** Format of sqlite_stat2:
68**
69** The sqlite_stat2 is only created and is only used if SQLite is compiled
70** with SQLITE_ENABLE_STAT2 and if the SQLite version number is between
71** 3.6.18 and 3.7.8. The "stat2" table contains additional information
72** about the distribution of keys within an index. The index is identified by
73** the "idx" column and the "tbl" column is the name of the table to which
74** the index belongs. There are usually 10 rows in the sqlite_stat2
75** table for each index.
76**
77** The sqlite_stat2 entries for an index that have sampleno between 0 and 9
78** inclusive are samples of the left-most key value in the index taken at
79** evenly spaced points along the index. Let the number of samples be S
80** (10 in the standard build) and let C be the number of rows in the index.
81** Then the sampled rows are given by:
82**
83** rownumber = (i*C*2 + C)/(S*2)
84**
85** For i between 0 and S-1. Conceptually, the index space is divided into
86** S uniform buckets and the samples are the middle row from each bucket.
87**
88** The format for sqlite_stat2 is recorded here for legacy reference. This
89** version of SQLite does not support sqlite_stat2. It neither reads nor
90** writes the sqlite_stat2 table. This version of SQLite only supports
91** sqlite_stat3.
92**
93** Format for sqlite_stat3:
94**
95** The sqlite_stat3 format is a subset of sqlite_stat4. Hence, the
96** sqlite_stat4 format will be described first. Further information
97** about sqlite_stat3 follows the sqlite_stat4 description.
98**
99** Format for sqlite_stat4:
100**
101** As with sqlite_stat2, the sqlite_stat4 table contains histogram data
102** to aid the query planner in choosing good indices based on the values
103** that indexed columns are compared against in the WHERE clauses of
104** queries.
105**
106** The sqlite_stat4 table contains multiple entries for each index.
107** The idx column names the index and the tbl column is the table of the
108** index. If the idx and tbl columns are the same, then the sample is
109** of the INTEGER PRIMARY KEY. The sample column is a blob which is the
110** binary encoding of a key from the index. The nEq column is a
111** list of integers. The first integer is the approximate number
112** of entries in the index whose left-most column exactly matches
113** the left-most column of the sample. The second integer in nEq
114** is the approximate number of entries in the index where the
115** first two columns match the first two columns of the sample.
116** And so forth. nLt is another list of integers that show the approximate
117** number of entries that are strictly less than the sample. The first
118** integer in nLt contains the number of entries in the index where the
119** left-most column is less than the left-most column of the sample.
120** The K-th integer in the nLt entry is the number of index entries
121** where the first K columns are less than the first K columns of the
122** sample. The nDLt column is like nLt except that it contains the
123** number of distinct entries in the index that are less than the
124** sample.
125**
126** There can be an arbitrary number of sqlite_stat4 entries per index.
127** The ANALYZE command will typically generate sqlite_stat4 tables
128** that contain between 10 and 40 samples which are distributed across
129** the key space, though not uniformly, and which include samples with
130** large nEq values.
131**
132** Format for sqlite_stat3 redux:
133**
134** The sqlite_stat3 table is like sqlite_stat4 except that it only
135** looks at the left-most column of the index. The sqlite_stat3.sample
136** column contains the actual value of the left-most column instead
137** of a blob encoding of the complete index key as is found in
138** sqlite_stat4.sample. The nEq, nLt, and nDLt entries of sqlite_stat3
139** all contain just a single integer which is the same as the first
140** integer in the equivalent columns in sqlite_stat4.
141*/
142#ifndef SQLITE_OMIT_ANALYZE
143#include "sqliteInt.h"
144
145#if defined(SQLITE_ENABLE_STAT4)
146# define IsStat4 1
147#else
148# define IsStat4 0
149# undef SQLITE_STAT4_SAMPLES
150# define SQLITE_STAT4_SAMPLES 1
151#endif
152
153/*
154** This routine generates code that opens the sqlite_statN tables.
155** The sqlite_stat1 table is always relevant. sqlite_stat2 is now
156** obsolete. sqlite_stat3 and sqlite_stat4 are only opened when
157** appropriate compile-time options are provided.
158**
159** If the sqlite_statN tables do not previously exist, it is created.
160**
161** Argument zWhere may be a pointer to a buffer containing a table name,
162** or it may be a NULL pointer. If it is not NULL, then all entries in
163** the sqlite_statN tables associated with the named table are deleted.
164** If zWhere==0, then code is generated to delete all stat table entries.
165*/
166static void openStatTable(
167 Parse *pParse, /* Parsing context */
168 int iDb, /* The database we are looking in */
169 int iStatCur, /* Open the sqlite_stat1 table on this cursor */
170 const char *zWhere, /* Delete entries for this table or index */
171 const char *zWhereType /* Either "tbl" or "idx" */
172){
173 static const struct {
174 const char *zName;
175 const char *zCols;
176 } aTable[] = {
177 { "sqlite_stat1", "tbl,idx,stat" },
178#if defined(SQLITE_ENABLE_STAT4)
179 { "sqlite_stat4", "tbl,idx,neq,nlt,ndlt,sample" },
180#else
181 { "sqlite_stat4", 0 },
182#endif
183 { "sqlite_stat3", 0 },
184 };
185 int i;
186 sqlite3 *db = pParse->db;
187 Db *pDb;
188 Vdbe *v = sqlite3GetVdbe(pParse);
189 u32 aRoot[ArraySize(aTable)];
190 u8 aCreateTbl[ArraySize(aTable)];
191#ifdef SQLITE_ENABLE_STAT4
192 const int nToOpen = OptimizationEnabled(db,SQLITE_Stat4) ? 2 : 1;
193#else
194 const int nToOpen = 1;
195#endif
196
197 if( v==0 ) return;
198 assert( sqlite3BtreeHoldsAllMutexes(db) );
199 assert( sqlite3VdbeDb(v)==db );
200 pDb = &db->aDb[iDb];
201
202 /* Create new statistic tables if they do not exist, or clear them
203 ** if they do already exist.
204 */
205 for(i=0; i<ArraySize(aTable); i++){
206 const char *zTab = aTable[i].zName;
207 Table *pStat;
208 aCreateTbl[i] = 0;
209 if( (pStat = sqlite3FindTable(db, zTab, pDb->zDbSName))==0 ){
210 if( i<nToOpen ){
211 /* The sqlite_statN table does not exist. Create it. Note that a
212 ** side-effect of the CREATE TABLE statement is to leave the rootpage
213 ** of the new table in register pParse->regRoot. This is important
214 ** because the OpenWrite opcode below will be needing it. */
215 sqlite3NestedParse(pParse,
216 "CREATE TABLE %Q.%s(%s)", pDb->zDbSName, zTab, aTable[i].zCols
217 );
218 aRoot[i] = (u32)pParse->regRoot;
219 aCreateTbl[i] = OPFLAG_P2ISREG;
220 }
221 }else{
222 /* The table already exists. If zWhere is not NULL, delete all entries
223 ** associated with the table zWhere. If zWhere is NULL, delete the
224 ** entire contents of the table. */
225 aRoot[i] = pStat->tnum;
226 sqlite3TableLock(pParse, iDb, aRoot[i], 1, zTab);
227 if( zWhere ){
228 sqlite3NestedParse(pParse,
229 "DELETE FROM %Q.%s WHERE %s=%Q",
230 pDb->zDbSName, zTab, zWhereType, zWhere
231 );
232#ifdef SQLITE_ENABLE_PREUPDATE_HOOK
233 }else if( db->xPreUpdateCallback ){
234 sqlite3NestedParse(pParse, "DELETE FROM %Q.%s", pDb->zDbSName, zTab);
235#endif
236 }else{
237 /* The sqlite_stat[134] table already exists. Delete all rows. */
238 sqlite3VdbeAddOp2(v, OP_Clear, (int)aRoot[i], iDb);
239 }
240 }
241 }
242
243 /* Open the sqlite_stat[134] tables for writing. */
244 for(i=0; i<nToOpen; i++){
245 assert( i<ArraySize(aTable) );
246 sqlite3VdbeAddOp4Int(v, OP_OpenWrite, iStatCur+i, (int)aRoot[i], iDb, 3);
247 sqlite3VdbeChangeP5(v, aCreateTbl[i]);
248 VdbeComment((v, aTable[i].zName));
249 }
250}
251
252/*
253** Recommended number of samples for sqlite_stat4
254*/
255#ifndef SQLITE_STAT4_SAMPLES
256# define SQLITE_STAT4_SAMPLES 24
257#endif
258
259/*
260** Three SQL functions - stat_init(), stat_push(), and stat_get() -
261** share an instance of the following structure to hold their state
262** information.
263*/
264typedef struct StatAccum StatAccum;
265typedef struct StatSample StatSample;
266struct StatSample {
267 tRowcnt *anEq; /* sqlite_stat4.nEq */
268 tRowcnt *anDLt; /* sqlite_stat4.nDLt */
269#ifdef SQLITE_ENABLE_STAT4
270 tRowcnt *anLt; /* sqlite_stat4.nLt */
271 union {
272 i64 iRowid; /* Rowid in main table of the key */
273 u8 *aRowid; /* Key for WITHOUT ROWID tables */
274 } u;
275 u32 nRowid; /* Sizeof aRowid[] */
276 u8 isPSample; /* True if a periodic sample */
277 int iCol; /* If !isPSample, the reason for inclusion */
278 u32 iHash; /* Tiebreaker hash */
279#endif
280};
281struct StatAccum {
282 sqlite3 *db; /* Database connection, for malloc() */
283 tRowcnt nEst; /* Estimated number of rows */
284 tRowcnt nRow; /* Number of rows visited so far */
285 int nLimit; /* Analysis row-scan limit */
286 int nCol; /* Number of columns in index + pk/rowid */
287 int nKeyCol; /* Number of index columns w/o the pk/rowid */
288 u8 nSkipAhead; /* Number of times of skip-ahead */
289 StatSample current; /* Current row as a StatSample */
290#ifdef SQLITE_ENABLE_STAT4
291 tRowcnt nPSample; /* How often to do a periodic sample */
292 int mxSample; /* Maximum number of samples to accumulate */
293 u32 iPrn; /* Pseudo-random number used for sampling */
294 StatSample *aBest; /* Array of nCol best samples */
295 int iMin; /* Index in a[] of entry with minimum score */
296 int nSample; /* Current number of samples */
297 int nMaxEqZero; /* Max leading 0 in anEq[] for any a[] entry */
298 int iGet; /* Index of current sample accessed by stat_get() */
299 StatSample *a; /* Array of mxSample StatSample objects */
300#endif
301};
302
303/* Reclaim memory used by a StatSample
304*/
305#ifdef SQLITE_ENABLE_STAT4
306static void sampleClear(sqlite3 *db, StatSample *p){
307 assert( db!=0 );
308 if( p->nRowid ){
309 sqlite3DbFree(db, p->u.aRowid);
310 p->nRowid = 0;
311 }
312}
313#endif
314
315/* Initialize the BLOB value of a ROWID
316*/
317#ifdef SQLITE_ENABLE_STAT4
318static void sampleSetRowid(sqlite3 *db, StatSample *p, int n, const u8 *pData){
319 assert( db!=0 );
320 if( p->nRowid ) sqlite3DbFree(db, p->u.aRowid);
321 p->u.aRowid = sqlite3DbMallocRawNN(db, n);
322 if( p->u.aRowid ){
323 p->nRowid = n;
324 memcpy(p->u.aRowid, pData, n);
325 }else{
326 p->nRowid = 0;
327 }
328}
329#endif
330
331/* Initialize the INTEGER value of a ROWID.
332*/
333#ifdef SQLITE_ENABLE_STAT4
334static void sampleSetRowidInt64(sqlite3 *db, StatSample *p, i64 iRowid){
335 assert( db!=0 );
336 if( p->nRowid ) sqlite3DbFree(db, p->u.aRowid);
337 p->nRowid = 0;
338 p->u.iRowid = iRowid;
339}
340#endif
341
342
343/*
344** Copy the contents of object (*pFrom) into (*pTo).
345*/
346#ifdef SQLITE_ENABLE_STAT4
347static void sampleCopy(StatAccum *p, StatSample *pTo, StatSample *pFrom){
348 pTo->isPSample = pFrom->isPSample;
349 pTo->iCol = pFrom->iCol;
350 pTo->iHash = pFrom->iHash;
351 memcpy(pTo->anEq, pFrom->anEq, sizeof(tRowcnt)*p->nCol);
352 memcpy(pTo->anLt, pFrom->anLt, sizeof(tRowcnt)*p->nCol);
353 memcpy(pTo->anDLt, pFrom->anDLt, sizeof(tRowcnt)*p->nCol);
354 if( pFrom->nRowid ){
355 sampleSetRowid(p->db, pTo, pFrom->nRowid, pFrom->u.aRowid);
356 }else{
357 sampleSetRowidInt64(p->db, pTo, pFrom->u.iRowid);
358 }
359}
360#endif
361
362/*
363** Reclaim all memory of a StatAccum structure.
364*/
365static void statAccumDestructor(void *pOld){
366 StatAccum *p = (StatAccum*)pOld;
367#ifdef SQLITE_ENABLE_STAT4
368 if( p->mxSample ){
369 int i;
370 for(i=0; i<p->nCol; i++) sampleClear(p->db, p->aBest+i);
371 for(i=0; i<p->mxSample; i++) sampleClear(p->db, p->a+i);
372 sampleClear(p->db, &p->current);
373 }
374#endif
375 sqlite3DbFree(p->db, p);
376}
377
378/*
379** Implementation of the stat_init(N,K,C,L) SQL function. The four parameters
380** are:
381** N: The number of columns in the index including the rowid/pk (note 1)
382** K: The number of columns in the index excluding the rowid/pk.
383** C: Estimated number of rows in the index
384** L: A limit on the number of rows to scan, or 0 for no-limit
385**
386** Note 1: In the special case of the covering index that implements a
387** WITHOUT ROWID table, N is the number of PRIMARY KEY columns, not the
388** total number of columns in the table.
389**
390** For indexes on ordinary rowid tables, N==K+1. But for indexes on
391** WITHOUT ROWID tables, N=K+P where P is the number of columns in the
392** PRIMARY KEY of the table. The covering index that implements the
393** original WITHOUT ROWID table as N==K as a special case.
394**
395** This routine allocates the StatAccum object in heap memory. The return
396** value is a pointer to the StatAccum object. The datatype of the
397** return value is BLOB, but it is really just a pointer to the StatAccum
398** object.
399*/
400static void statInit(
401 sqlite3_context *context,
402 int argc,
403 sqlite3_value **argv
404){
405 StatAccum *p;
406 int nCol; /* Number of columns in index being sampled */
407 int nKeyCol; /* Number of key columns */
408 int nColUp; /* nCol rounded up for alignment */
409 int n; /* Bytes of space to allocate */
410 sqlite3 *db = sqlite3_context_db_handle(context); /* Database connection */
411#ifdef SQLITE_ENABLE_STAT4
412 /* Maximum number of samples. 0 if STAT4 data is not collected */
413 int mxSample = OptimizationEnabled(db,SQLITE_Stat4) ?SQLITE_STAT4_SAMPLES :0;
414#endif
415
416 /* Decode the three function arguments */
417 UNUSED_PARAMETER(argc);
418 nCol = sqlite3_value_int(argv[0]);
419 assert( nCol>0 );
420 nColUp = sizeof(tRowcnt)<8 ? (nCol+1)&~1 : nCol;
421 nKeyCol = sqlite3_value_int(argv[1]);
422 assert( nKeyCol<=nCol );
423 assert( nKeyCol>0 );
424
425 /* Allocate the space required for the StatAccum object */
426 n = sizeof(*p)
427 + sizeof(tRowcnt)*nColUp /* StatAccum.anEq */
428 + sizeof(tRowcnt)*nColUp; /* StatAccum.anDLt */
429#ifdef SQLITE_ENABLE_STAT4
430 if( mxSample ){
431 n += sizeof(tRowcnt)*nColUp /* StatAccum.anLt */
432 + sizeof(StatSample)*(nCol+mxSample) /* StatAccum.aBest[], a[] */
433 + sizeof(tRowcnt)*3*nColUp*(nCol+mxSample);
434 }
435#endif
436 p = sqlite3DbMallocZero(db, n);
437 if( p==0 ){
438 sqlite3_result_error_nomem(context);
439 return;
440 }
441
442 p->db = db;
443 p->nEst = sqlite3_value_int64(argv[2]);
444 p->nRow = 0;
445 p->nLimit = sqlite3_value_int64(argv[3]);
446 p->nCol = nCol;
447 p->nKeyCol = nKeyCol;
448 p->nSkipAhead = 0;
449 p->current.anDLt = (tRowcnt*)&p[1];
450 p->current.anEq = &p->current.anDLt[nColUp];
451
452#ifdef SQLITE_ENABLE_STAT4
453 p->mxSample = p->nLimit==0 ? mxSample : 0;
454 if( mxSample ){
455 u8 *pSpace; /* Allocated space not yet assigned */
456 int i; /* Used to iterate through p->aSample[] */
457
458 p->iGet = -1;
459 p->nPSample = (tRowcnt)(p->nEst/(mxSample/3+1) + 1);
460 p->current.anLt = &p->current.anEq[nColUp];
461 p->iPrn = 0x689e962d*(u32)nCol ^ 0xd0944565*(u32)sqlite3_value_int(argv[2]);
462
463 /* Set up the StatAccum.a[] and aBest[] arrays */
464 p->a = (struct StatSample*)&p->current.anLt[nColUp];
465 p->aBest = &p->a[mxSample];
466 pSpace = (u8*)(&p->a[mxSample+nCol]);
467 for(i=0; i<(mxSample+nCol); i++){
468 p->a[i].anEq = (tRowcnt *)pSpace; pSpace += (sizeof(tRowcnt) * nColUp);
469 p->a[i].anLt = (tRowcnt *)pSpace; pSpace += (sizeof(tRowcnt) * nColUp);
470 p->a[i].anDLt = (tRowcnt *)pSpace; pSpace += (sizeof(tRowcnt) * nColUp);
471 }
472 assert( (pSpace - (u8*)p)==n );
473
474 for(i=0; i<nCol; i++){
475 p->aBest[i].iCol = i;
476 }
477 }
478#endif
479
480 /* Return a pointer to the allocated object to the caller. Note that
481 ** only the pointer (the 2nd parameter) matters. The size of the object
482 ** (given by the 3rd parameter) is never used and can be any positive
483 ** value. */
484 sqlite3_result_blob(context, p, sizeof(*p), statAccumDestructor);
485}
486static const FuncDef statInitFuncdef = {
487 4, /* nArg */
488 SQLITE_UTF8, /* funcFlags */
489 0, /* pUserData */
490 0, /* pNext */
491 statInit, /* xSFunc */
492 0, /* xFinalize */
493 0, 0, /* xValue, xInverse */
494 "stat_init", /* zName */
495 {0}
496};
497
498#ifdef SQLITE_ENABLE_STAT4
499/*
500** pNew and pOld are both candidate non-periodic samples selected for
501** the same column (pNew->iCol==pOld->iCol). Ignoring this column and
502** considering only any trailing columns and the sample hash value, this
503** function returns true if sample pNew is to be preferred over pOld.
504** In other words, if we assume that the cardinalities of the selected
505** column for pNew and pOld are equal, is pNew to be preferred over pOld.
506**
507** This function assumes that for each argument sample, the contents of
508** the anEq[] array from pSample->anEq[pSample->iCol+1] onwards are valid.
509*/
510static int sampleIsBetterPost(
511 StatAccum *pAccum,
512 StatSample *pNew,
513 StatSample *pOld
514){
515 int nCol = pAccum->nCol;
516 int i;
517 assert( pNew->iCol==pOld->iCol );
518 for(i=pNew->iCol+1; i<nCol; i++){
519 if( pNew->anEq[i]>pOld->anEq[i] ) return 1;
520 if( pNew->anEq[i]<pOld->anEq[i] ) return 0;
521 }
522 if( pNew->iHash>pOld->iHash ) return 1;
523 return 0;
524}
525#endif
526
527#ifdef SQLITE_ENABLE_STAT4
528/*
529** Return true if pNew is to be preferred over pOld.
530**
531** This function assumes that for each argument sample, the contents of
532** the anEq[] array from pSample->anEq[pSample->iCol] onwards are valid.
533*/
534static int sampleIsBetter(
535 StatAccum *pAccum,
536 StatSample *pNew,
537 StatSample *pOld
538){
539 tRowcnt nEqNew = pNew->anEq[pNew->iCol];
540 tRowcnt nEqOld = pOld->anEq[pOld->iCol];
541
542 assert( pOld->isPSample==0 && pNew->isPSample==0 );
543 assert( IsStat4 || (pNew->iCol==0 && pOld->iCol==0) );
544
545 if( (nEqNew>nEqOld) ) return 1;
546 if( nEqNew==nEqOld ){
547 if( pNew->iCol<pOld->iCol ) return 1;
548 return (pNew->iCol==pOld->iCol && sampleIsBetterPost(pAccum, pNew, pOld));
549 }
550 return 0;
551}
552
553/*
554** Copy the contents of sample *pNew into the p->a[] array. If necessary,
555** remove the least desirable sample from p->a[] to make room.
556*/
557static void sampleInsert(StatAccum *p, StatSample *pNew, int nEqZero){
558 StatSample *pSample = 0;
559 int i;
560
561 assert( IsStat4 || nEqZero==0 );
562
563 /* StatAccum.nMaxEqZero is set to the maximum number of leading 0
564 ** values in the anEq[] array of any sample in StatAccum.a[]. In
565 ** other words, if nMaxEqZero is n, then it is guaranteed that there
566 ** are no samples with StatSample.anEq[m]==0 for (m>=n). */
567 if( nEqZero>p->nMaxEqZero ){
568 p->nMaxEqZero = nEqZero;
569 }
570 if( pNew->isPSample==0 ){
571 StatSample *pUpgrade = 0;
572 assert( pNew->anEq[pNew->iCol]>0 );
573
574 /* This sample is being added because the prefix that ends in column
575 ** iCol occurs many times in the table. However, if we have already
576 ** added a sample that shares this prefix, there is no need to add
577 ** this one. Instead, upgrade the priority of the highest priority
578 ** existing sample that shares this prefix. */
579 for(i=p->nSample-1; i>=0; i--){
580 StatSample *pOld = &p->a[i];
581 if( pOld->anEq[pNew->iCol]==0 ){
582 if( pOld->isPSample ) return;
583 assert( pOld->iCol>pNew->iCol );
584 assert( sampleIsBetter(p, pNew, pOld) );
585 if( pUpgrade==0 || sampleIsBetter(p, pOld, pUpgrade) ){
586 pUpgrade = pOld;
587 }
588 }
589 }
590 if( pUpgrade ){
591 pUpgrade->iCol = pNew->iCol;
592 pUpgrade->anEq[pUpgrade->iCol] = pNew->anEq[pUpgrade->iCol];
593 goto find_new_min;
594 }
595 }
596
597 /* If necessary, remove sample iMin to make room for the new sample. */
598 if( p->nSample>=p->mxSample ){
599 StatSample *pMin = &p->a[p->iMin];
600 tRowcnt *anEq = pMin->anEq;
601 tRowcnt *anLt = pMin->anLt;
602 tRowcnt *anDLt = pMin->anDLt;
603 sampleClear(p->db, pMin);
604 memmove(pMin, &pMin[1], sizeof(p->a[0])*(p->nSample-p->iMin-1));
605 pSample = &p->a[p->nSample-1];
606 pSample->nRowid = 0;
607 pSample->anEq = anEq;
608 pSample->anDLt = anDLt;
609 pSample->anLt = anLt;
610 p->nSample = p->mxSample-1;
611 }
612
613 /* The "rows less-than" for the rowid column must be greater than that
614 ** for the last sample in the p->a[] array. Otherwise, the samples would
615 ** be out of order. */
616 assert( p->nSample==0
617 || pNew->anLt[p->nCol-1] > p->a[p->nSample-1].anLt[p->nCol-1] );
618
619 /* Insert the new sample */
620 pSample = &p->a[p->nSample];
621 sampleCopy(p, pSample, pNew);
622 p->nSample++;
623
624 /* Zero the first nEqZero entries in the anEq[] array. */
625 memset(pSample->anEq, 0, sizeof(tRowcnt)*nEqZero);
626
627find_new_min:
628 if( p->nSample>=p->mxSample ){
629 int iMin = -1;
630 for(i=0; i<p->mxSample; i++){
631 if( p->a[i].isPSample ) continue;
632 if( iMin<0 || sampleIsBetter(p, &p->a[iMin], &p->a[i]) ){
633 iMin = i;
634 }
635 }
636 assert( iMin>=0 );
637 p->iMin = iMin;
638 }
639}
640#endif /* SQLITE_ENABLE_STAT4 */
641
642#ifdef SQLITE_ENABLE_STAT4
643/*
644** Field iChng of the index being scanned has changed. So at this point
645** p->current contains a sample that reflects the previous row of the
646** index. The value of anEq[iChng] and subsequent anEq[] elements are
647** correct at this point.
648*/
649static void samplePushPrevious(StatAccum *p, int iChng){
650 int i;
651
652 /* Check if any samples from the aBest[] array should be pushed
653 ** into IndexSample.a[] at this point. */
654 for(i=(p->nCol-2); i>=iChng; i--){
655 StatSample *pBest = &p->aBest[i];
656 pBest->anEq[i] = p->current.anEq[i];
657 if( p->nSample<p->mxSample || sampleIsBetter(p, pBest, &p->a[p->iMin]) ){
658 sampleInsert(p, pBest, i);
659 }
660 }
661
662 /* Check that no sample contains an anEq[] entry with an index of
663 ** p->nMaxEqZero or greater set to zero. */
664 for(i=p->nSample-1; i>=0; i--){
665 int j;
666 for(j=p->nMaxEqZero; j<p->nCol; j++) assert( p->a[i].anEq[j]>0 );
667 }
668
669 /* Update the anEq[] fields of any samples already collected. */
670 if( iChng<p->nMaxEqZero ){
671 for(i=p->nSample-1; i>=0; i--){
672 int j;
673 for(j=iChng; j<p->nCol; j++){
674 if( p->a[i].anEq[j]==0 ) p->a[i].anEq[j] = p->current.anEq[j];
675 }
676 }
677 p->nMaxEqZero = iChng;
678 }
679}
680#endif /* SQLITE_ENABLE_STAT4 */
681
682/*
683** Implementation of the stat_push SQL function: stat_push(P,C,R)
684** Arguments:
685**
686** P Pointer to the StatAccum object created by stat_init()
687** C Index of left-most column to differ from previous row
688** R Rowid for the current row. Might be a key record for
689** WITHOUT ROWID tables.
690**
691** The purpose of this routine is to collect statistical data and/or
692** samples from the index being analyzed into the StatAccum object.
693** The stat_get() SQL function will be used afterwards to
694** retrieve the information gathered.
695**
696** This SQL function usually returns NULL, but might return an integer
697** if it wants the byte-code to do special processing.
698**
699** The R parameter is only used for STAT4
700*/
701static void statPush(
702 sqlite3_context *context,
703 int argc,
704 sqlite3_value **argv
705){
706 int i;
707
708 /* The three function arguments */
709 StatAccum *p = (StatAccum*)sqlite3_value_blob(argv[0]);
710 int iChng = sqlite3_value_int(argv[1]);
711
712 UNUSED_PARAMETER( argc );
713 UNUSED_PARAMETER( context );
714 assert( p->nCol>0 );
715 assert( iChng<p->nCol );
716
717 if( p->nRow==0 ){
718 /* This is the first call to this function. Do initialization. */
719 for(i=0; i<p->nCol; i++) p->current.anEq[i] = 1;
720 }else{
721 /* Second and subsequent calls get processed here */
722#ifdef SQLITE_ENABLE_STAT4
723 if( p->mxSample ) samplePushPrevious(p, iChng);
724#endif
725
726 /* Update anDLt[], anLt[] and anEq[] to reflect the values that apply
727 ** to the current row of the index. */
728 for(i=0; i<iChng; i++){
729 p->current.anEq[i]++;
730 }
731 for(i=iChng; i<p->nCol; i++){
732 p->current.anDLt[i]++;
733#ifdef SQLITE_ENABLE_STAT4
734 if( p->mxSample ) p->current.anLt[i] += p->current.anEq[i];
735#endif
736 p->current.anEq[i] = 1;
737 }
738 }
739
740 p->nRow++;
741#ifdef SQLITE_ENABLE_STAT4
742 if( p->mxSample ){
743 tRowcnt nLt;
744 if( sqlite3_value_type(argv[2])==SQLITE_INTEGER ){
745 sampleSetRowidInt64(p->db, &p->current, sqlite3_value_int64(argv[2]));
746 }else{
747 sampleSetRowid(p->db, &p->current, sqlite3_value_bytes(argv[2]),
748 sqlite3_value_blob(argv[2]));
749 }
750 p->current.iHash = p->iPrn = p->iPrn*1103515245 + 12345;
751
752 nLt = p->current.anLt[p->nCol-1];
753 /* Check if this is to be a periodic sample. If so, add it. */
754 if( (nLt/p->nPSample)!=(nLt+1)/p->nPSample ){
755 p->current.isPSample = 1;
756 p->current.iCol = 0;
757 sampleInsert(p, &p->current, p->nCol-1);
758 p->current.isPSample = 0;
759 }
760
761 /* Update the aBest[] array. */
762 for(i=0; i<(p->nCol-1); i++){
763 p->current.iCol = i;
764 if( i>=iChng || sampleIsBetterPost(p, &p->current, &p->aBest[i]) ){
765 sampleCopy(p, &p->aBest[i], &p->current);
766 }
767 }
768 }else
769#endif
770 if( p->nLimit && p->nRow>(tRowcnt)p->nLimit*(p->nSkipAhead+1) ){
771 p->nSkipAhead++;
772 sqlite3_result_int(context, p->current.anDLt[0]>0);
773 }
774}
775
776static const FuncDef statPushFuncdef = {
777 2+IsStat4, /* nArg */
778 SQLITE_UTF8, /* funcFlags */
779 0, /* pUserData */
780 0, /* pNext */
781 statPush, /* xSFunc */
782 0, /* xFinalize */
783 0, 0, /* xValue, xInverse */
784 "stat_push", /* zName */
785 {0}
786};
787
788#define STAT_GET_STAT1 0 /* "stat" column of stat1 table */
789#define STAT_GET_ROWID 1 /* "rowid" column of stat[34] entry */
790#define STAT_GET_NEQ 2 /* "neq" column of stat[34] entry */
791#define STAT_GET_NLT 3 /* "nlt" column of stat[34] entry */
792#define STAT_GET_NDLT 4 /* "ndlt" column of stat[34] entry */
793
794/*
795** Implementation of the stat_get(P,J) SQL function. This routine is
796** used to query statistical information that has been gathered into
797** the StatAccum object by prior calls to stat_push(). The P parameter
798** has type BLOB but it is really just a pointer to the StatAccum object.
799** The content to returned is determined by the parameter J
800** which is one of the STAT_GET_xxxx values defined above.
801**
802** The stat_get(P,J) function is not available to generic SQL. It is
803** inserted as part of a manually constructed bytecode program. (See
804** the callStatGet() routine below.) It is guaranteed that the P
805** parameter will always be a pointer to a StatAccum object, never a
806** NULL.
807**
808** If STAT4 is not enabled, then J is always
809** STAT_GET_STAT1 and is hence omitted and this routine becomes
810** a one-parameter function, stat_get(P), that always returns the
811** stat1 table entry information.
812*/
813static void statGet(
814 sqlite3_context *context,
815 int argc,
816 sqlite3_value **argv
817){
818 StatAccum *p = (StatAccum*)sqlite3_value_blob(argv[0]);
819#ifdef SQLITE_ENABLE_STAT4
820 /* STAT4 has a parameter on this routine. */
821 int eCall = sqlite3_value_int(argv[1]);
822 assert( argc==2 );
823 assert( eCall==STAT_GET_STAT1 || eCall==STAT_GET_NEQ
824 || eCall==STAT_GET_ROWID || eCall==STAT_GET_NLT
825 || eCall==STAT_GET_NDLT
826 );
827 assert( eCall==STAT_GET_STAT1 || p->mxSample );
828 if( eCall==STAT_GET_STAT1 )
829#else
830 assert( argc==1 );
831#endif
832 {
833 /* Return the value to store in the "stat" column of the sqlite_stat1
834 ** table for this index.
835 **
836 ** The value is a string composed of a list of integers describing
837 ** the index. The first integer in the list is the total number of
838 ** entries in the index. There is one additional integer in the list
839 ** for each indexed column. This additional integer is an estimate of
840 ** the number of rows matched by a equality query on the index using
841 ** a key with the corresponding number of fields. In other words,
842 ** if the index is on columns (a,b) and the sqlite_stat1 value is
843 ** "100 10 2", then SQLite estimates that:
844 **
845 ** * the index contains 100 rows,
846 ** * "WHERE a=?" matches 10 rows, and
847 ** * "WHERE a=? AND b=?" matches 2 rows.
848 **
849 ** If D is the count of distinct values and K is the total number of
850 ** rows, then each estimate is usually computed as:
851 **
852 ** I = (K+D-1)/D
853 **
854 ** In other words, I is K/D rounded up to the next whole integer.
855 ** However, if I is between 1.0 and 1.1 (in other words if I is
856 ** close to 1.0 but just a little larger) then do not round up but
857 ** instead keep the I value at 1.0.
858 */
859 sqlite3_str sStat; /* Text of the constructed "stat" line */
860 int i; /* Loop counter */
861
862 sqlite3StrAccumInit(&sStat, 0, 0, 0, (p->nKeyCol+1)*100);
863 sqlite3_str_appendf(&sStat, "%llu",
864 p->nSkipAhead ? (u64)p->nEst : (u64)p->nRow);
865 for(i=0; i<p->nKeyCol; i++){
866 u64 nDistinct = p->current.anDLt[i] + 1;
867 u64 iVal = (p->nRow + nDistinct - 1) / nDistinct;
868 if( iVal==2 && p->nRow*10 <= nDistinct*11 ) iVal = 1;
869 sqlite3_str_appendf(&sStat, " %llu", iVal);
870 assert( p->current.anEq[i] );
871 }
872 sqlite3ResultStrAccum(context, &sStat);
873 }
874#ifdef SQLITE_ENABLE_STAT4
875 else if( eCall==STAT_GET_ROWID ){
876 if( p->iGet<0 ){
877 samplePushPrevious(p, 0);
878 p->iGet = 0;
879 }
880 if( p->iGet<p->nSample ){
881 StatSample *pS = p->a + p->iGet;
882 if( pS->nRowid==0 ){
883 sqlite3_result_int64(context, pS->u.iRowid);
884 }else{
885 sqlite3_result_blob(context, pS->u.aRowid, pS->nRowid,
886 SQLITE_TRANSIENT);
887 }
888 }
889 }else{
890 tRowcnt *aCnt = 0;
891 sqlite3_str sStat;
892 int i;
893
894 assert( p->iGet<p->nSample );
895 switch( eCall ){
896 case STAT_GET_NEQ: aCnt = p->a[p->iGet].anEq; break;
897 case STAT_GET_NLT: aCnt = p->a[p->iGet].anLt; break;
898 default: {
899 aCnt = p->a[p->iGet].anDLt;
900 p->iGet++;
901 break;
902 }
903 }
904 sqlite3StrAccumInit(&sStat, 0, 0, 0, p->nCol*100);
905 for(i=0; i<p->nCol; i++){
906 sqlite3_str_appendf(&sStat, "%llu ", (u64)aCnt[i]);
907 }
908 if( sStat.nChar ) sStat.nChar--;
909 sqlite3ResultStrAccum(context, &sStat);
910 }
911#endif /* SQLITE_ENABLE_STAT4 */
912#ifndef SQLITE_DEBUG
913 UNUSED_PARAMETER( argc );
914#endif
915}
916static const FuncDef statGetFuncdef = {
917 1+IsStat4, /* nArg */
918 SQLITE_UTF8, /* funcFlags */
919 0, /* pUserData */
920 0, /* pNext */
921 statGet, /* xSFunc */
922 0, /* xFinalize */
923 0, 0, /* xValue, xInverse */
924 "stat_get", /* zName */
925 {0}
926};
927
928static void callStatGet(Parse *pParse, int regStat, int iParam, int regOut){
929#ifdef SQLITE_ENABLE_STAT4
930 sqlite3VdbeAddOp2(pParse->pVdbe, OP_Integer, iParam, regStat+1);
931#elif SQLITE_DEBUG
932 assert( iParam==STAT_GET_STAT1 );
933#else
934 UNUSED_PARAMETER( iParam );
935#endif
936 assert( regOut!=regStat && regOut!=regStat+1 );
937 sqlite3VdbeAddFunctionCall(pParse, 0, regStat, regOut, 1+IsStat4,
938 &statGetFuncdef, 0);
939}
940
941#ifdef SQLITE_ENABLE_EXPLAIN_COMMENTS
942/* Add a comment to the most recent VDBE opcode that is the name
943** of the k-th column of the pIdx index.
944*/
945static void analyzeVdbeCommentIndexWithColumnName(
946 Vdbe *v, /* Prepared statement under construction */
947 Index *pIdx, /* Index whose column is being loaded */
948 int k /* Which column index */
949){
950 int i; /* Index of column in the table */
951 assert( k>=0 && k<pIdx->nColumn );
952 i = pIdx->aiColumn[k];
953 if( NEVER(i==XN_ROWID) ){
954 VdbeComment((v,"%s.rowid",pIdx->zName));
955 }else if( i==XN_EXPR ){
956 assert( pIdx->bHasExpr );
957 VdbeComment((v,"%s.expr(%d)",pIdx->zName, k));
958 }else{
959 VdbeComment((v,"%s.%s", pIdx->zName, pIdx->pTable->aCol[i].zCnName));
960 }
961}
962#else
963# define analyzeVdbeCommentIndexWithColumnName(a,b,c)
964#endif /* SQLITE_DEBUG */
965
966/*
967** Generate code to do an analysis of all indices associated with
968** a single table.
969*/
970static void analyzeOneTable(
971 Parse *pParse, /* Parser context */
972 Table *pTab, /* Table whose indices are to be analyzed */
973 Index *pOnlyIdx, /* If not NULL, only analyze this one index */
974 int iStatCur, /* Index of VdbeCursor that writes the sqlite_stat1 table */
975 int iMem, /* Available memory locations begin here */
976 int iTab /* Next available cursor */
977){
978 sqlite3 *db = pParse->db; /* Database handle */
979 Index *pIdx; /* An index to being analyzed */
980 int iIdxCur; /* Cursor open on index being analyzed */
981 int iTabCur; /* Table cursor */
982 Vdbe *v; /* The virtual machine being built up */
983 int i; /* Loop counter */
984 int jZeroRows = -1; /* Jump from here if number of rows is zero */
985 int iDb; /* Index of database containing pTab */
986 u8 needTableCnt = 1; /* True to count the table */
987 int regNewRowid = iMem++; /* Rowid for the inserted record */
988 int regStat = iMem++; /* Register to hold StatAccum object */
989 int regChng = iMem++; /* Index of changed index field */
990 int regRowid = iMem++; /* Rowid argument passed to stat_push() */
991 int regTemp = iMem++; /* Temporary use register */
992 int regTemp2 = iMem++; /* Second temporary use register */
993 int regTabname = iMem++; /* Register containing table name */
994 int regIdxname = iMem++; /* Register containing index name */
995 int regStat1 = iMem++; /* Value for the stat column of sqlite_stat1 */
996 int regPrev = iMem; /* MUST BE LAST (see below) */
997#ifdef SQLITE_ENABLE_PREUPDATE_HOOK
998 Table *pStat1 = 0;
999#endif
1000
1001 pParse->nMem = MAX(pParse->nMem, iMem);
1002 v = sqlite3GetVdbe(pParse);
1003 if( v==0 || NEVER(pTab==0) ){
1004 return;
1005 }
1006 if( !IsOrdinaryTable(pTab) ){
1007 /* Do not gather statistics on views or virtual tables */
1008 return;
1009 }
1010 if( sqlite3_strlike("sqlite\\_%", pTab->zName, '\\')==0 ){
1011 /* Do not gather statistics on system tables */
1012 return;
1013 }
1014 assert( sqlite3BtreeHoldsAllMutexes(db) );
1015 iDb = sqlite3SchemaToIndex(db, pTab->pSchema);
1016 assert( iDb>=0 );
1017 assert( sqlite3SchemaMutexHeld(db, iDb, 0) );
1018#ifndef SQLITE_OMIT_AUTHORIZATION
1019 if( sqlite3AuthCheck(pParse, SQLITE_ANALYZE, pTab->zName, 0,
1020 db->aDb[iDb].zDbSName ) ){
1021 return;
1022 }
1023#endif
1024
1025#ifdef SQLITE_ENABLE_PREUPDATE_HOOK
1026 if( db->xPreUpdateCallback ){
1027 pStat1 = (Table*)sqlite3DbMallocZero(db, sizeof(Table) + 13);
1028 if( pStat1==0 ) return;
1029 pStat1->zName = (char*)&pStat1[1];
1030 memcpy(pStat1->zName, "sqlite_stat1", 13);
1031 pStat1->nCol = 3;
1032 pStat1->iPKey = -1;
1033 sqlite3VdbeAddOp4(pParse->pVdbe, OP_Noop, 0, 0, 0,(char*)pStat1,P4_DYNAMIC);
1034 }
1035#endif
1036
1037 /* Establish a read-lock on the table at the shared-cache level.
1038 ** Open a read-only cursor on the table. Also allocate a cursor number
1039 ** to use for scanning indexes (iIdxCur). No index cursor is opened at
1040 ** this time though. */
1041 sqlite3TableLock(pParse, iDb, pTab->tnum, 0, pTab->zName);
1042 iTabCur = iTab++;
1043 iIdxCur = iTab++;
1044 pParse->nTab = MAX(pParse->nTab, iTab);
1045 sqlite3OpenTable(pParse, iTabCur, iDb, pTab, OP_OpenRead);
1046 sqlite3VdbeLoadString(v, regTabname, pTab->zName);
1047
1048 for(pIdx=pTab->pIndex; pIdx; pIdx=pIdx->pNext){
1049 int nCol; /* Number of columns in pIdx. "N" */
1050 int addrRewind; /* Address of "OP_Rewind iIdxCur" */
1051 int addrNextRow; /* Address of "next_row:" */
1052 const char *zIdxName; /* Name of the index */
1053 int nColTest; /* Number of columns to test for changes */
1054
1055 if( pOnlyIdx && pOnlyIdx!=pIdx ) continue;
1056 if( pIdx->pPartIdxWhere==0 ) needTableCnt = 0;
1057 if( !HasRowid(pTab) && IsPrimaryKeyIndex(pIdx) ){
1058 nCol = pIdx->nKeyCol;
1059 zIdxName = pTab->zName;
1060 nColTest = nCol - 1;
1061 }else{
1062 nCol = pIdx->nColumn;
1063 zIdxName = pIdx->zName;
1064 nColTest = pIdx->uniqNotNull ? pIdx->nKeyCol-1 : nCol-1;
1065 }
1066
1067 /* Populate the register containing the index name. */
1068 sqlite3VdbeLoadString(v, regIdxname, zIdxName);
1069 VdbeComment((v, "Analysis for %s.%s", pTab->zName, zIdxName));
1070
1071 /*
1072 ** Pseudo-code for loop that calls stat_push():
1073 **
1074 ** Rewind csr
1075 ** if eof(csr) goto end_of_scan;
1076 ** regChng = 0
1077 ** goto chng_addr_0;
1078 **
1079 ** next_row:
1080 ** regChng = 0
1081 ** if( idx(0) != regPrev(0) ) goto chng_addr_0
1082 ** regChng = 1
1083 ** if( idx(1) != regPrev(1) ) goto chng_addr_1
1084 ** ...
1085 ** regChng = N
1086 ** goto chng_addr_N
1087 **
1088 ** chng_addr_0:
1089 ** regPrev(0) = idx(0)
1090 ** chng_addr_1:
1091 ** regPrev(1) = idx(1)
1092 ** ...
1093 **
1094 ** endDistinctTest:
1095 ** regRowid = idx(rowid)
1096 ** stat_push(P, regChng, regRowid)
1097 ** Next csr
1098 ** if !eof(csr) goto next_row;
1099 **
1100 ** end_of_scan:
1101 */
1102
1103 /* Make sure there are enough memory cells allocated to accommodate
1104 ** the regPrev array and a trailing rowid (the rowid slot is required
1105 ** when building a record to insert into the sample column of
1106 ** the sqlite_stat4 table. */
1107 pParse->nMem = MAX(pParse->nMem, regPrev+nColTest);
1108
1109 /* Open a read-only cursor on the index being analyzed. */
1110 assert( iDb==sqlite3SchemaToIndex(db, pIdx->pSchema) );
1111 sqlite3VdbeAddOp3(v, OP_OpenRead, iIdxCur, pIdx->tnum, iDb);
1112 sqlite3VdbeSetP4KeyInfo(pParse, pIdx);
1113 VdbeComment((v, "%s", pIdx->zName));
1114
1115 /* Invoke the stat_init() function. The arguments are:
1116 **
1117 ** (1) the number of columns in the index including the rowid
1118 ** (or for a WITHOUT ROWID table, the number of PK columns),
1119 ** (2) the number of columns in the key without the rowid/pk
1120 ** (3) estimated number of rows in the index,
1121 */
1122 sqlite3VdbeAddOp2(v, OP_Integer, nCol, regStat+1);
1123 assert( regRowid==regStat+2 );
1124 sqlite3VdbeAddOp2(v, OP_Integer, pIdx->nKeyCol, regRowid);
1125#ifdef SQLITE_ENABLE_STAT4
1126 if( OptimizationEnabled(db, SQLITE_Stat4) ){
1127 sqlite3VdbeAddOp2(v, OP_Count, iIdxCur, regTemp);
1128 addrRewind = sqlite3VdbeAddOp1(v, OP_Rewind, iIdxCur);
1129 VdbeCoverage(v);
1130 }else
1131#endif
1132 {
1133 addrRewind = sqlite3VdbeAddOp1(v, OP_Rewind, iIdxCur);
1134 VdbeCoverage(v);
1135 sqlite3VdbeAddOp3(v, OP_Count, iIdxCur, regTemp, 1);
1136 }
1137 assert( regTemp2==regStat+4 );
1138 sqlite3VdbeAddOp2(v, OP_Integer, db->nAnalysisLimit, regTemp2);
1139 sqlite3VdbeAddFunctionCall(pParse, 0, regStat+1, regStat, 4,
1140 &statInitFuncdef, 0);
1141
1142 /* Implementation of the following:
1143 **
1144 ** Rewind csr
1145 ** if eof(csr) goto end_of_scan;
1146 ** regChng = 0
1147 ** goto next_push_0;
1148 **
1149 */
1150 sqlite3VdbeAddOp2(v, OP_Integer, 0, regChng);
1151 addrNextRow = sqlite3VdbeCurrentAddr(v);
1152
1153 if( nColTest>0 ){
1154 int endDistinctTest = sqlite3VdbeMakeLabel(pParse);
1155 int *aGotoChng; /* Array of jump instruction addresses */
1156 aGotoChng = sqlite3DbMallocRawNN(db, sizeof(int)*nColTest);
1157 if( aGotoChng==0 ) continue;
1158
1159 /*
1160 ** next_row:
1161 ** regChng = 0
1162 ** if( idx(0) != regPrev(0) ) goto chng_addr_0
1163 ** regChng = 1
1164 ** if( idx(1) != regPrev(1) ) goto chng_addr_1
1165 ** ...
1166 ** regChng = N
1167 ** goto endDistinctTest
1168 */
1169 sqlite3VdbeAddOp0(v, OP_Goto);
1170 addrNextRow = sqlite3VdbeCurrentAddr(v);
1171 if( nColTest==1 && pIdx->nKeyCol==1 && IsUniqueIndex(pIdx) ){
1172 /* For a single-column UNIQUE index, once we have found a non-NULL
1173 ** row, we know that all the rest will be distinct, so skip
1174 ** subsequent distinctness tests. */
1175 sqlite3VdbeAddOp2(v, OP_NotNull, regPrev, endDistinctTest);
1176 VdbeCoverage(v);
1177 }
1178 for(i=0; i<nColTest; i++){
1179 char *pColl = (char*)sqlite3LocateCollSeq(pParse, pIdx->azColl[i]);
1180 sqlite3VdbeAddOp2(v, OP_Integer, i, regChng);
1181 sqlite3VdbeAddOp3(v, OP_Column, iIdxCur, i, regTemp);
1182 analyzeVdbeCommentIndexWithColumnName(v,pIdx,i);
1183 aGotoChng[i] =
1184 sqlite3VdbeAddOp4(v, OP_Ne, regTemp, 0, regPrev+i, pColl, P4_COLLSEQ);
1185 sqlite3VdbeChangeP5(v, SQLITE_NULLEQ);
1186 VdbeCoverage(v);
1187 }
1188 sqlite3VdbeAddOp2(v, OP_Integer, nColTest, regChng);
1189 sqlite3VdbeGoto(v, endDistinctTest);
1190
1191
1192 /*
1193 ** chng_addr_0:
1194 ** regPrev(0) = idx(0)
1195 ** chng_addr_1:
1196 ** regPrev(1) = idx(1)
1197 ** ...
1198 */
1199 sqlite3VdbeJumpHere(v, addrNextRow-1);
1200 for(i=0; i<nColTest; i++){
1201 sqlite3VdbeJumpHere(v, aGotoChng[i]);
1202 sqlite3VdbeAddOp3(v, OP_Column, iIdxCur, i, regPrev+i);
1203 analyzeVdbeCommentIndexWithColumnName(v,pIdx,i);
1204 }
1205 sqlite3VdbeResolveLabel(v, endDistinctTest);
1206 sqlite3DbFree(db, aGotoChng);
1207 }
1208
1209 /*
1210 ** chng_addr_N:
1211 ** regRowid = idx(rowid) // STAT4 only
1212 ** stat_push(P, regChng, regRowid) // 3rd parameter STAT4 only
1213 ** Next csr
1214 ** if !eof(csr) goto next_row;
1215 */
1216#ifdef SQLITE_ENABLE_STAT4
1217 if( OptimizationEnabled(db, SQLITE_Stat4) ){
1218 assert( regRowid==(regStat+2) );
1219 if( HasRowid(pTab) ){
1220 sqlite3VdbeAddOp2(v, OP_IdxRowid, iIdxCur, regRowid);
1221 }else{
1222 Index *pPk = sqlite3PrimaryKeyIndex(pIdx->pTable);
1223 int j, k, regKey;
1224 regKey = sqlite3GetTempRange(pParse, pPk->nKeyCol);
1225 for(j=0; j<pPk->nKeyCol; j++){
1226 k = sqlite3TableColumnToIndex(pIdx, pPk->aiColumn[j]);
1227 assert( k>=0 && k<pIdx->nColumn );
1228 sqlite3VdbeAddOp3(v, OP_Column, iIdxCur, k, regKey+j);
1229 analyzeVdbeCommentIndexWithColumnName(v,pIdx,k);
1230 }
1231 sqlite3VdbeAddOp3(v, OP_MakeRecord, regKey, pPk->nKeyCol, regRowid);
1232 sqlite3ReleaseTempRange(pParse, regKey, pPk->nKeyCol);
1233 }
1234 }
1235#endif
1236 assert( regChng==(regStat+1) );
1237 {
1238 sqlite3VdbeAddFunctionCall(pParse, 1, regStat, regTemp, 2+IsStat4,
1239 &statPushFuncdef, 0);
1240 if( db->nAnalysisLimit ){
1241 int j1, j2, j3;
1242 j1 = sqlite3VdbeAddOp1(v, OP_IsNull, regTemp); VdbeCoverage(v);
1243 j2 = sqlite3VdbeAddOp1(v, OP_If, regTemp); VdbeCoverage(v);
1244 j3 = sqlite3VdbeAddOp4Int(v, OP_SeekGT, iIdxCur, 0, regPrev, 1);
1245 VdbeCoverage(v);
1246 sqlite3VdbeJumpHere(v, j1);
1247 sqlite3VdbeAddOp2(v, OP_Next, iIdxCur, addrNextRow); VdbeCoverage(v);
1248 sqlite3VdbeJumpHere(v, j2);
1249 sqlite3VdbeJumpHere(v, j3);
1250 }else{
1251 sqlite3VdbeAddOp2(v, OP_Next, iIdxCur, addrNextRow); VdbeCoverage(v);
1252 }
1253 }
1254
1255 /* Add the entry to the stat1 table. */
1256 callStatGet(pParse, regStat, STAT_GET_STAT1, regStat1);
1257 assert( "BBB"[0]==SQLITE_AFF_TEXT );
1258 sqlite3VdbeAddOp4(v, OP_MakeRecord, regTabname, 3, regTemp, "BBB", 0);
1259 sqlite3VdbeAddOp2(v, OP_NewRowid, iStatCur, regNewRowid);
1260 sqlite3VdbeAddOp3(v, OP_Insert, iStatCur, regTemp, regNewRowid);
1261#ifdef SQLITE_ENABLE_PREUPDATE_HOOK
1262 sqlite3VdbeChangeP4(v, -1, (char*)pStat1, P4_TABLE);
1263#endif
1264 sqlite3VdbeChangeP5(v, OPFLAG_APPEND);
1265
1266 /* Add the entries to the stat4 table. */
1267#ifdef SQLITE_ENABLE_STAT4
1268 if( OptimizationEnabled(db, SQLITE_Stat4) && db->nAnalysisLimit==0 ){
1269 int regEq = regStat1;
1270 int regLt = regStat1+1;
1271 int regDLt = regStat1+2;
1272 int regSample = regStat1+3;
1273 int regCol = regStat1+4;
1274 int regSampleRowid = regCol + nCol;
1275 int addrNext;
1276 int addrIsNull;
1277 u8 seekOp = HasRowid(pTab) ? OP_NotExists : OP_NotFound;
1278
1279 pParse->nMem = MAX(pParse->nMem, regCol+nCol);
1280
1281 addrNext = sqlite3VdbeCurrentAddr(v);
1282 callStatGet(pParse, regStat, STAT_GET_ROWID, regSampleRowid);
1283 addrIsNull = sqlite3VdbeAddOp1(v, OP_IsNull, regSampleRowid);
1284 VdbeCoverage(v);
1285 callStatGet(pParse, regStat, STAT_GET_NEQ, regEq);
1286 callStatGet(pParse, regStat, STAT_GET_NLT, regLt);
1287 callStatGet(pParse, regStat, STAT_GET_NDLT, regDLt);
1288 sqlite3VdbeAddOp4Int(v, seekOp, iTabCur, addrNext, regSampleRowid, 0);
1289 VdbeCoverage(v);
1290 for(i=0; i<nCol; i++){
1291 sqlite3ExprCodeLoadIndexColumn(pParse, pIdx, iTabCur, i, regCol+i);
1292 }
1293 sqlite3VdbeAddOp3(v, OP_MakeRecord, regCol, nCol, regSample);
1294 sqlite3VdbeAddOp3(v, OP_MakeRecord, regTabname, 6, regTemp);
1295 sqlite3VdbeAddOp2(v, OP_NewRowid, iStatCur+1, regNewRowid);
1296 sqlite3VdbeAddOp3(v, OP_Insert, iStatCur+1, regTemp, regNewRowid);
1297 sqlite3VdbeAddOp2(v, OP_Goto, 1, addrNext); /* P1==1 for end-of-loop */
1298 sqlite3VdbeJumpHere(v, addrIsNull);
1299 }
1300#endif /* SQLITE_ENABLE_STAT4 */
1301
1302 /* End of analysis */
1303 sqlite3VdbeJumpHere(v, addrRewind);
1304 }
1305
1306
1307 /* Create a single sqlite_stat1 entry containing NULL as the index
1308 ** name and the row count as the content.
1309 */
1310 if( pOnlyIdx==0 && needTableCnt ){
1311 VdbeComment((v, "%s", pTab->zName));
1312 sqlite3VdbeAddOp2(v, OP_Count, iTabCur, regStat1);
1313 jZeroRows = sqlite3VdbeAddOp1(v, OP_IfNot, regStat1); VdbeCoverage(v);
1314 sqlite3VdbeAddOp2(v, OP_Null, 0, regIdxname);
1315 assert( "BBB"[0]==SQLITE_AFF_TEXT );
1316 sqlite3VdbeAddOp4(v, OP_MakeRecord, regTabname, 3, regTemp, "BBB", 0);
1317 sqlite3VdbeAddOp2(v, OP_NewRowid, iStatCur, regNewRowid);
1318 sqlite3VdbeAddOp3(v, OP_Insert, iStatCur, regTemp, regNewRowid);
1319 sqlite3VdbeChangeP5(v, OPFLAG_APPEND);
1320#ifdef SQLITE_ENABLE_PREUPDATE_HOOK
1321 sqlite3VdbeChangeP4(v, -1, (char*)pStat1, P4_TABLE);
1322#endif
1323 sqlite3VdbeJumpHere(v, jZeroRows);
1324 }
1325}
1326
1327
1328/*
1329** Generate code that will cause the most recent index analysis to
1330** be loaded into internal hash tables where is can be used.
1331*/
1332static void loadAnalysis(Parse *pParse, int iDb){
1333 Vdbe *v = sqlite3GetVdbe(pParse);
1334 if( v ){
1335 sqlite3VdbeAddOp1(v, OP_LoadAnalysis, iDb);
1336 }
1337}
1338
1339/*
1340** Generate code that will do an analysis of an entire database
1341*/
1342static void analyzeDatabase(Parse *pParse, int iDb){
1343 sqlite3 *db = pParse->db;
1344 Schema *pSchema = db->aDb[iDb].pSchema; /* Schema of database iDb */
1345 HashElem *k;
1346 int iStatCur;
1347 int iMem;
1348 int iTab;
1349
1350 sqlite3BeginWriteOperation(pParse, 0, iDb);
1351 iStatCur = pParse->nTab;
1352 pParse->nTab += 3;
1353 openStatTable(pParse, iDb, iStatCur, 0, 0);
1354 iMem = pParse->nMem+1;
1355 iTab = pParse->nTab;
1356 assert( sqlite3SchemaMutexHeld(db, iDb, 0) );
1357 for(k=sqliteHashFirst(&pSchema->tblHash); k; k=sqliteHashNext(k)){
1358 Table *pTab = (Table*)sqliteHashData(k);
1359 analyzeOneTable(pParse, pTab, 0, iStatCur, iMem, iTab);
1360 }
1361 loadAnalysis(pParse, iDb);
1362}
1363
1364/*
1365** Generate code that will do an analysis of a single table in
1366** a database. If pOnlyIdx is not NULL then it is a single index
1367** in pTab that should be analyzed.
1368*/
1369static void analyzeTable(Parse *pParse, Table *pTab, Index *pOnlyIdx){
1370 int iDb;
1371 int iStatCur;
1372
1373 assert( pTab!=0 );
1374 assert( sqlite3BtreeHoldsAllMutexes(pParse->db) );
1375 iDb = sqlite3SchemaToIndex(pParse->db, pTab->pSchema);
1376 sqlite3BeginWriteOperation(pParse, 0, iDb);
1377 iStatCur = pParse->nTab;
1378 pParse->nTab += 3;
1379 if( pOnlyIdx ){
1380 openStatTable(pParse, iDb, iStatCur, pOnlyIdx->zName, "idx");
1381 }else{
1382 openStatTable(pParse, iDb, iStatCur, pTab->zName, "tbl");
1383 }
1384 analyzeOneTable(pParse, pTab, pOnlyIdx, iStatCur,pParse->nMem+1,pParse->nTab);
1385 loadAnalysis(pParse, iDb);
1386}
1387
1388/*
1389** Generate code for the ANALYZE command. The parser calls this routine
1390** when it recognizes an ANALYZE command.
1391**
1392** ANALYZE -- 1
1393** ANALYZE <database> -- 2
1394** ANALYZE ?<database>.?<tablename> -- 3
1395**
1396** Form 1 causes all indices in all attached databases to be analyzed.
1397** Form 2 analyzes all indices the single database named.
1398** Form 3 analyzes all indices associated with the named table.
1399*/
1400void sqlite3Analyze(Parse *pParse, Token *pName1, Token *pName2){
1401 sqlite3 *db = pParse->db;
1402 int iDb;
1403 int i;
1404 char *z, *zDb;
1405 Table *pTab;
1406 Index *pIdx;
1407 Token *pTableName;
1408 Vdbe *v;
1409
1410 /* Read the database schema. If an error occurs, leave an error message
1411 ** and code in pParse and return NULL. */
1412 assert( sqlite3BtreeHoldsAllMutexes(pParse->db) );
1413 if( SQLITE_OK!=sqlite3ReadSchema(pParse) ){
1414 return;
1415 }
1416
1417 assert( pName2!=0 || pName1==0 );
1418 if( pName1==0 ){
1419 /* Form 1: Analyze everything */
1420 for(i=0; i<db->nDb; i++){
1421 if( i==1 ) continue; /* Do not analyze the TEMP database */
1422 analyzeDatabase(pParse, i);
1423 }
1424 }else if( pName2->n==0 && (iDb = sqlite3FindDb(db, pName1))>=0 ){
1425 /* Analyze the schema named as the argument */
1426 analyzeDatabase(pParse, iDb);
1427 }else{
1428 /* Form 3: Analyze the table or index named as an argument */
1429 iDb = sqlite3TwoPartName(pParse, pName1, pName2, &pTableName);
1430 if( iDb>=0 ){
1431 zDb = pName2->n ? db->aDb[iDb].zDbSName : 0;
1432 z = sqlite3NameFromToken(db, pTableName);
1433 if( z ){
1434 if( (pIdx = sqlite3FindIndex(db, z, zDb))!=0 ){
1435 analyzeTable(pParse, pIdx->pTable, pIdx);
1436 }else if( (pTab = sqlite3LocateTable(pParse, 0, z, zDb))!=0 ){
1437 analyzeTable(pParse, pTab, 0);
1438 }
1439 sqlite3DbFree(db, z);
1440 }
1441 }
1442 }
1443 if( db->nSqlExec==0 && (v = sqlite3GetVdbe(pParse))!=0 ){
1444 sqlite3VdbeAddOp0(v, OP_Expire);
1445 }
1446}
1447
1448/*
1449** Used to pass information from the analyzer reader through to the
1450** callback routine.
1451*/
1452typedef struct analysisInfo analysisInfo;
1453struct analysisInfo {
1454 sqlite3 *db;
1455 const char *zDatabase;
1456};
1457
1458/*
1459** The first argument points to a nul-terminated string containing a
1460** list of space separated integers. Read the first nOut of these into
1461** the array aOut[].
1462*/
1463static void decodeIntArray(
1464 char *zIntArray, /* String containing int array to decode */
1465 int nOut, /* Number of slots in aOut[] */
1466 tRowcnt *aOut, /* Store integers here */
1467 LogEst *aLog, /* Or, if aOut==0, here */
1468 Index *pIndex /* Handle extra flags for this index, if not NULL */
1469){
1470 char *z = zIntArray;
1471 int c;
1472 int i;
1473 tRowcnt v;
1474
1475#ifdef SQLITE_ENABLE_STAT4
1476 if( z==0 ) z = "";
1477#else
1478 assert( z!=0 );
1479#endif
1480 for(i=0; *z && i<nOut; i++){
1481 v = 0;
1482 while( (c=z[0])>='0' && c<='9' ){
1483 v = v*10 + c - '0';
1484 z++;
1485 }
1486#ifdef SQLITE_ENABLE_STAT4
1487 if( aOut ) aOut[i] = v;
1488 if( aLog ) aLog[i] = sqlite3LogEst(v);
1489#else
1490 assert( aOut==0 );
1491 UNUSED_PARAMETER(aOut);
1492 assert( aLog!=0 );
1493 aLog[i] = sqlite3LogEst(v);
1494#endif
1495 if( *z==' ' ) z++;
1496 }
1497#ifndef SQLITE_ENABLE_STAT4
1498 assert( pIndex!=0 ); {
1499#else
1500 if( pIndex ){
1501#endif
1502 pIndex->bUnordered = 0;
1503 pIndex->noSkipScan = 0;
1504 while( z[0] ){
1505 if( sqlite3_strglob("unordered*", z)==0 ){
1506 pIndex->bUnordered = 1;
1507 }else if( sqlite3_strglob("sz=[0-9]*", z)==0 ){
1508 int sz = sqlite3Atoi(z+3);
1509 if( sz<2 ) sz = 2;
1510 pIndex->szIdxRow = sqlite3LogEst(sz);
1511 }else if( sqlite3_strglob("noskipscan*", z)==0 ){
1512 pIndex->noSkipScan = 1;
1513 }
1514#ifdef SQLITE_ENABLE_COSTMULT
1515 else if( sqlite3_strglob("costmult=[0-9]*",z)==0 ){
1516 pIndex->pTable->costMult = sqlite3LogEst(sqlite3Atoi(z+9));
1517 }
1518#endif
1519 while( z[0]!=0 && z[0]!=' ' ) z++;
1520 while( z[0]==' ' ) z++;
1521 }
1522 }
1523}
1524
1525/*
1526** This callback is invoked once for each index when reading the
1527** sqlite_stat1 table.
1528**
1529** argv[0] = name of the table
1530** argv[1] = name of the index (might be NULL)
1531** argv[2] = results of analysis - on integer for each column
1532**
1533** Entries for which argv[1]==NULL simply record the number of rows in
1534** the table.
1535*/
1536static int analysisLoader(void *pData, int argc, char **argv, char **NotUsed){
1537 analysisInfo *pInfo = (analysisInfo*)pData;
1538 Index *pIndex;
1539 Table *pTable;
1540 const char *z;
1541
1542 assert( argc==3 );
1543 UNUSED_PARAMETER2(NotUsed, argc);
1544
1545 if( argv==0 || argv[0]==0 || argv[2]==0 ){
1546 return 0;
1547 }
1548 pTable = sqlite3FindTable(pInfo->db, argv[0], pInfo->zDatabase);
1549 if( pTable==0 ){
1550 return 0;
1551 }
1552 if( argv[1]==0 ){
1553 pIndex = 0;
1554 }else if( sqlite3_stricmp(argv[0],argv[1])==0 ){
1555 pIndex = sqlite3PrimaryKeyIndex(pTable);
1556 }else{
1557 pIndex = sqlite3FindIndex(pInfo->db, argv[1], pInfo->zDatabase);
1558 }
1559 z = argv[2];
1560
1561 if( pIndex ){
1562 tRowcnt *aiRowEst = 0;
1563 int nCol = pIndex->nKeyCol+1;
1564#ifdef SQLITE_ENABLE_STAT4
1565 /* Index.aiRowEst may already be set here if there are duplicate
1566 ** sqlite_stat1 entries for this index. In that case just clobber
1567 ** the old data with the new instead of allocating a new array. */
1568 if( pIndex->aiRowEst==0 ){
1569 pIndex->aiRowEst = (tRowcnt*)sqlite3MallocZero(sizeof(tRowcnt) * nCol);
1570 if( pIndex->aiRowEst==0 ) sqlite3OomFault(pInfo->db);
1571 }
1572 aiRowEst = pIndex->aiRowEst;
1573#endif
1574 pIndex->bUnordered = 0;
1575 decodeIntArray((char*)z, nCol, aiRowEst, pIndex->aiRowLogEst, pIndex);
1576 pIndex->hasStat1 = 1;
1577 if( pIndex->pPartIdxWhere==0 ){
1578 pTable->nRowLogEst = pIndex->aiRowLogEst[0];
1579 pTable->tabFlags |= TF_HasStat1;
1580 }
1581 }else{
1582 Index fakeIdx;
1583 fakeIdx.szIdxRow = pTable->szTabRow;
1584#ifdef SQLITE_ENABLE_COSTMULT
1585 fakeIdx.pTable = pTable;
1586#endif
1587 decodeIntArray((char*)z, 1, 0, &pTable->nRowLogEst, &fakeIdx);
1588 pTable->szTabRow = fakeIdx.szIdxRow;
1589 pTable->tabFlags |= TF_HasStat1;
1590 }
1591
1592 return 0;
1593}
1594
1595/*
1596** If the Index.aSample variable is not NULL, delete the aSample[] array
1597** and its contents.
1598*/
1599void sqlite3DeleteIndexSamples(sqlite3 *db, Index *pIdx){
1600#ifdef SQLITE_ENABLE_STAT4
1601 if( pIdx->aSample ){
1602 int j;
1603 for(j=0; j<pIdx->nSample; j++){
1604 IndexSample *p = &pIdx->aSample[j];
1605 sqlite3DbFree(db, p->p);
1606 }
1607 sqlite3DbFree(db, pIdx->aSample);
1608 }
1609 if( db && db->pnBytesFreed==0 ){
1610 pIdx->nSample = 0;
1611 pIdx->aSample = 0;
1612 }
1613#else
1614 UNUSED_PARAMETER(db);
1615 UNUSED_PARAMETER(pIdx);
1616#endif /* SQLITE_ENABLE_STAT4 */
1617}
1618
1619#ifdef SQLITE_ENABLE_STAT4
1620/*
1621** Populate the pIdx->aAvgEq[] array based on the samples currently
1622** stored in pIdx->aSample[].
1623*/
1624static void initAvgEq(Index *pIdx){
1625 if( pIdx ){
1626 IndexSample *aSample = pIdx->aSample;
1627 IndexSample *pFinal = &aSample[pIdx->nSample-1];
1628 int iCol;
1629 int nCol = 1;
1630 if( pIdx->nSampleCol>1 ){
1631 /* If this is stat4 data, then calculate aAvgEq[] values for all
1632 ** sample columns except the last. The last is always set to 1, as
1633 ** once the trailing PK fields are considered all index keys are
1634 ** unique. */
1635 nCol = pIdx->nSampleCol-1;
1636 pIdx->aAvgEq[nCol] = 1;
1637 }
1638 for(iCol=0; iCol<nCol; iCol++){
1639 int nSample = pIdx->nSample;
1640 int i; /* Used to iterate through samples */
1641 tRowcnt sumEq = 0; /* Sum of the nEq values */
1642 tRowcnt avgEq = 0;
1643 tRowcnt nRow; /* Number of rows in index */
1644 i64 nSum100 = 0; /* Number of terms contributing to sumEq */
1645 i64 nDist100; /* Number of distinct values in index */
1646
1647 if( !pIdx->aiRowEst || iCol>=pIdx->nKeyCol || pIdx->aiRowEst[iCol+1]==0 ){
1648 nRow = pFinal->anLt[iCol];
1649 nDist100 = (i64)100 * pFinal->anDLt[iCol];
1650 nSample--;
1651 }else{
1652 nRow = pIdx->aiRowEst[0];
1653 nDist100 = ((i64)100 * pIdx->aiRowEst[0]) / pIdx->aiRowEst[iCol+1];
1654 }
1655 pIdx->nRowEst0 = nRow;
1656
1657 /* Set nSum to the number of distinct (iCol+1) field prefixes that
1658 ** occur in the stat4 table for this index. Set sumEq to the sum of
1659 ** the nEq values for column iCol for the same set (adding the value
1660 ** only once where there exist duplicate prefixes). */
1661 for(i=0; i<nSample; i++){
1662 if( i==(pIdx->nSample-1)
1663 || aSample[i].anDLt[iCol]!=aSample[i+1].anDLt[iCol]
1664 ){
1665 sumEq += aSample[i].anEq[iCol];
1666 nSum100 += 100;
1667 }
1668 }
1669
1670 if( nDist100>nSum100 && sumEq<nRow ){
1671 avgEq = ((i64)100 * (nRow - sumEq))/(nDist100 - nSum100);
1672 }
1673 if( avgEq==0 ) avgEq = 1;
1674 pIdx->aAvgEq[iCol] = avgEq;
1675 }
1676 }
1677}
1678
1679/*
1680** Look up an index by name. Or, if the name of a WITHOUT ROWID table
1681** is supplied instead, find the PRIMARY KEY index for that table.
1682*/
1683static Index *findIndexOrPrimaryKey(
1684 sqlite3 *db,
1685 const char *zName,
1686 const char *zDb
1687){
1688 Index *pIdx = sqlite3FindIndex(db, zName, zDb);
1689 if( pIdx==0 ){
1690 Table *pTab = sqlite3FindTable(db, zName, zDb);
1691 if( pTab && !HasRowid(pTab) ) pIdx = sqlite3PrimaryKeyIndex(pTab);
1692 }
1693 return pIdx;
1694}
1695
1696/*
1697** Load the content from either the sqlite_stat4
1698** into the relevant Index.aSample[] arrays.
1699**
1700** Arguments zSql1 and zSql2 must point to SQL statements that return
1701** data equivalent to the following:
1702**
1703** zSql1: SELECT idx,count(*) FROM %Q.sqlite_stat4 GROUP BY idx
1704** zSql2: SELECT idx,neq,nlt,ndlt,sample FROM %Q.sqlite_stat4
1705**
1706** where %Q is replaced with the database name before the SQL is executed.
1707*/
1708static int loadStatTbl(
1709 sqlite3 *db, /* Database handle */
1710 const char *zSql1, /* SQL statement 1 (see above) */
1711 const char *zSql2, /* SQL statement 2 (see above) */
1712 const char *zDb /* Database name (e.g. "main") */
1713){
1714 int rc; /* Result codes from subroutines */
1715 sqlite3_stmt *pStmt = 0; /* An SQL statement being run */
1716 char *zSql; /* Text of the SQL statement */
1717 Index *pPrevIdx = 0; /* Previous index in the loop */
1718 IndexSample *pSample; /* A slot in pIdx->aSample[] */
1719
1720 assert( db->lookaside.bDisable );
1721 zSql = sqlite3MPrintf(db, zSql1, zDb);
1722 if( !zSql ){
1723 return SQLITE_NOMEM_BKPT;
1724 }
1725 rc = sqlite3_prepare(db, zSql, -1, &pStmt, 0);
1726 sqlite3DbFree(db, zSql);
1727 if( rc ) return rc;
1728
1729 while( sqlite3_step(pStmt)==SQLITE_ROW ){
1730 int nIdxCol = 1; /* Number of columns in stat4 records */
1731
1732 char *zIndex; /* Index name */
1733 Index *pIdx; /* Pointer to the index object */
1734 int nSample; /* Number of samples */
1735 int nByte; /* Bytes of space required */
1736 int i; /* Bytes of space required */
1737 tRowcnt *pSpace;
1738
1739 zIndex = (char *)sqlite3_column_text(pStmt, 0);
1740 if( zIndex==0 ) continue;
1741 nSample = sqlite3_column_int(pStmt, 1);
1742 pIdx = findIndexOrPrimaryKey(db, zIndex, zDb);
1743 assert( pIdx==0 || pIdx->nSample==0 );
1744 if( pIdx==0 ) continue;
1745 assert( !HasRowid(pIdx->pTable) || pIdx->nColumn==pIdx->nKeyCol+1 );
1746 if( !HasRowid(pIdx->pTable) && IsPrimaryKeyIndex(pIdx) ){
1747 nIdxCol = pIdx->nKeyCol;
1748 }else{
1749 nIdxCol = pIdx->nColumn;
1750 }
1751 pIdx->nSampleCol = nIdxCol;
1752 nByte = sizeof(IndexSample) * nSample;
1753 nByte += sizeof(tRowcnt) * nIdxCol * 3 * nSample;
1754 nByte += nIdxCol * sizeof(tRowcnt); /* Space for Index.aAvgEq[] */
1755
1756 pIdx->aSample = sqlite3DbMallocZero(db, nByte);
1757 if( pIdx->aSample==0 ){
1758 sqlite3_finalize(pStmt);
1759 return SQLITE_NOMEM_BKPT;
1760 }
1761 pSpace = (tRowcnt*)&pIdx->aSample[nSample];
1762 pIdx->aAvgEq = pSpace; pSpace += nIdxCol;
1763 pIdx->pTable->tabFlags |= TF_HasStat4;
1764 for(i=0; i<nSample; i++){
1765 pIdx->aSample[i].anEq = pSpace; pSpace += nIdxCol;
1766 pIdx->aSample[i].anLt = pSpace; pSpace += nIdxCol;
1767 pIdx->aSample[i].anDLt = pSpace; pSpace += nIdxCol;
1768 }
1769 assert( ((u8*)pSpace)-nByte==(u8*)(pIdx->aSample) );
1770 }
1771 rc = sqlite3_finalize(pStmt);
1772 if( rc ) return rc;
1773
1774 zSql = sqlite3MPrintf(db, zSql2, zDb);
1775 if( !zSql ){
1776 return SQLITE_NOMEM_BKPT;
1777 }
1778 rc = sqlite3_prepare(db, zSql, -1, &pStmt, 0);
1779 sqlite3DbFree(db, zSql);
1780 if( rc ) return rc;
1781
1782 while( sqlite3_step(pStmt)==SQLITE_ROW ){
1783 char *zIndex; /* Index name */
1784 Index *pIdx; /* Pointer to the index object */
1785 int nCol = 1; /* Number of columns in index */
1786
1787 zIndex = (char *)sqlite3_column_text(pStmt, 0);
1788 if( zIndex==0 ) continue;
1789 pIdx = findIndexOrPrimaryKey(db, zIndex, zDb);
1790 if( pIdx==0 ) continue;
1791 /* This next condition is true if data has already been loaded from
1792 ** the sqlite_stat4 table. */
1793 nCol = pIdx->nSampleCol;
1794 if( pIdx!=pPrevIdx ){
1795 initAvgEq(pPrevIdx);
1796 pPrevIdx = pIdx;
1797 }
1798 pSample = &pIdx->aSample[pIdx->nSample];
1799 decodeIntArray((char*)sqlite3_column_text(pStmt,1),nCol,pSample->anEq,0,0);
1800 decodeIntArray((char*)sqlite3_column_text(pStmt,2),nCol,pSample->anLt,0,0);
1801 decodeIntArray((char*)sqlite3_column_text(pStmt,3),nCol,pSample->anDLt,0,0);
1802
1803 /* Take a copy of the sample. Add two 0x00 bytes the end of the buffer.
1804 ** This is in case the sample record is corrupted. In that case, the
1805 ** sqlite3VdbeRecordCompare() may read up to two varints past the
1806 ** end of the allocated buffer before it realizes it is dealing with
1807 ** a corrupt record. Adding the two 0x00 bytes prevents this from causing
1808 ** a buffer overread. */
1809 pSample->n = sqlite3_column_bytes(pStmt, 4);
1810 pSample->p = sqlite3DbMallocZero(db, pSample->n + 2);
1811 if( pSample->p==0 ){
1812 sqlite3_finalize(pStmt);
1813 return SQLITE_NOMEM_BKPT;
1814 }
1815 if( pSample->n ){
1816 memcpy(pSample->p, sqlite3_column_blob(pStmt, 4), pSample->n);
1817 }
1818 pIdx->nSample++;
1819 }
1820 rc = sqlite3_finalize(pStmt);
1821 if( rc==SQLITE_OK ) initAvgEq(pPrevIdx);
1822 return rc;
1823}
1824
1825/*
1826** Load content from the sqlite_stat4 table into
1827** the Index.aSample[] arrays of all indices.
1828*/
1829static int loadStat4(sqlite3 *db, const char *zDb){
1830 int rc = SQLITE_OK; /* Result codes from subroutines */
1831 const Table *pStat4;
1832
1833 assert( db->lookaside.bDisable );
1834 if( (pStat4 = sqlite3FindTable(db, "sqlite_stat4", zDb))!=0
1835 && IsOrdinaryTable(pStat4)
1836 ){
1837 rc = loadStatTbl(db,
1838 "SELECT idx,count(*) FROM %Q.sqlite_stat4 GROUP BY idx",
1839 "SELECT idx,neq,nlt,ndlt,sample FROM %Q.sqlite_stat4",
1840 zDb
1841 );
1842 }
1843 return rc;
1844}
1845#endif /* SQLITE_ENABLE_STAT4 */
1846
1847/*
1848** Load the content of the sqlite_stat1 and sqlite_stat4 tables. The
1849** contents of sqlite_stat1 are used to populate the Index.aiRowEst[]
1850** arrays. The contents of sqlite_stat4 are used to populate the
1851** Index.aSample[] arrays.
1852**
1853** If the sqlite_stat1 table is not present in the database, SQLITE_ERROR
1854** is returned. In this case, even if SQLITE_ENABLE_STAT4 was defined
1855** during compilation and the sqlite_stat4 table is present, no data is
1856** read from it.
1857**
1858** If SQLITE_ENABLE_STAT4 was defined during compilation and the
1859** sqlite_stat4 table is not present in the database, SQLITE_ERROR is
1860** returned. However, in this case, data is read from the sqlite_stat1
1861** table (if it is present) before returning.
1862**
1863** If an OOM error occurs, this function always sets db->mallocFailed.
1864** This means if the caller does not care about other errors, the return
1865** code may be ignored.
1866*/
1867int sqlite3AnalysisLoad(sqlite3 *db, int iDb){
1868 analysisInfo sInfo;
1869 HashElem *i;
1870 char *zSql;
1871 int rc = SQLITE_OK;
1872 Schema *pSchema = db->aDb[iDb].pSchema;
1873 const Table *pStat1;
1874
1875 assert( iDb>=0 && iDb<db->nDb );
1876 assert( db->aDb[iDb].pBt!=0 );
1877
1878 /* Clear any prior statistics */
1879 assert( sqlite3SchemaMutexHeld(db, iDb, 0) );
1880 for(i=sqliteHashFirst(&pSchema->tblHash); i; i=sqliteHashNext(i)){
1881 Table *pTab = sqliteHashData(i);
1882 pTab->tabFlags &= ~TF_HasStat1;
1883 }
1884 for(i=sqliteHashFirst(&pSchema->idxHash); i; i=sqliteHashNext(i)){
1885 Index *pIdx = sqliteHashData(i);
1886 pIdx->hasStat1 = 0;
1887#ifdef SQLITE_ENABLE_STAT4
1888 sqlite3DeleteIndexSamples(db, pIdx);
1889 pIdx->aSample = 0;
1890#endif
1891 }
1892
1893 /* Load new statistics out of the sqlite_stat1 table */
1894 sInfo.db = db;
1895 sInfo.zDatabase = db->aDb[iDb].zDbSName;
1896 if( (pStat1 = sqlite3FindTable(db, "sqlite_stat1", sInfo.zDatabase))
1897 && IsOrdinaryTable(pStat1)
1898 ){
1899 zSql = sqlite3MPrintf(db,
1900 "SELECT tbl,idx,stat FROM %Q.sqlite_stat1", sInfo.zDatabase);
1901 if( zSql==0 ){
1902 rc = SQLITE_NOMEM_BKPT;
1903 }else{
1904 rc = sqlite3_exec(db, zSql, analysisLoader, &sInfo, 0);
1905 sqlite3DbFree(db, zSql);
1906 }
1907 }
1908
1909 /* Set appropriate defaults on all indexes not in the sqlite_stat1 table */
1910 assert( sqlite3SchemaMutexHeld(db, iDb, 0) );
1911 for(i=sqliteHashFirst(&pSchema->idxHash); i; i=sqliteHashNext(i)){
1912 Index *pIdx = sqliteHashData(i);
1913 if( !pIdx->hasStat1 ) sqlite3DefaultRowEst(pIdx);
1914 }
1915
1916 /* Load the statistics from the sqlite_stat4 table. */
1917#ifdef SQLITE_ENABLE_STAT4
1918 if( rc==SQLITE_OK ){
1919 DisableLookaside;
1920 rc = loadStat4(db, sInfo.zDatabase);
1921 EnableLookaside;
1922 }
1923 for(i=sqliteHashFirst(&pSchema->idxHash); i; i=sqliteHashNext(i)){
1924 Index *pIdx = sqliteHashData(i);
1925 sqlite3_free(pIdx->aiRowEst);
1926 pIdx->aiRowEst = 0;
1927 }
1928#endif
1929
1930 if( rc==SQLITE_NOMEM ){
1931 sqlite3OomFault(db);
1932 }
1933 return rc;
1934}
1935
1936
1937#endif /* SQLITE_OMIT_ANALYZE */
1938