Merge Chromium + Blink git repositories
[chromium-blink-merge.git] / third_party / sqlite / sqlite-src-3080704 / src / analyze.c
blobe655aaa50c7136cfb712f3799bcd3c65f3d050f6
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.
11 *************************************************************************
12 ** This file contains code associated with the ANALYZE command.
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.
18 ** The following system tables are or have been supported:
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);
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 and later and with
31 ** SQLITE_ENABLE_STAT3 defined. The functionality of sqlite_stat3
32 ** is a superset of sqlite_stat2. The sqlite_stat4 is an enhanced
33 ** version of sqlite_stat3 and is only available when compiled with
34 ** SQLITE_ENABLE_STAT4 and in SQLite versions 3.8.1 and later. It is
35 ** not possible to enable both STAT3 and STAT4 at the same time. If they
36 ** are both enabled, then STAT4 takes precedence.
38 ** For most applications, sqlite_stat1 provides all the statistics required
39 ** for the query planner to make good choices.
41 ** Format of sqlite_stat1:
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.
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.
67 ** Format of sqlite_stat2:
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.
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:
83 ** rownumber = (i*C*2 + C)/(S*2)
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.
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.
93 ** Format for sqlite_stat3:
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.
99 ** Format for sqlite_stat4:
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.
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.
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.
132 ** Format for sqlite_stat3 redux:
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.
142 #ifndef SQLITE_OMIT_ANALYZE
143 #include "sqliteInt.h"
145 #if defined(SQLITE_ENABLE_STAT4)
146 # define IsStat4 1
147 # define IsStat3 0
148 #elif defined(SQLITE_ENABLE_STAT3)
149 # define IsStat4 0
150 # define IsStat3 1
151 #else
152 # define IsStat4 0
153 # define IsStat3 0
154 # undef SQLITE_STAT4_SAMPLES
155 # define SQLITE_STAT4_SAMPLES 1
156 #endif
157 #define IsStat34 (IsStat3+IsStat4) /* 1 for STAT3 or STAT4. 0 otherwise */
160 ** This routine generates code that opens the sqlite_statN tables.
161 ** The sqlite_stat1 table is always relevant. sqlite_stat2 is now
162 ** obsolete. sqlite_stat3 and sqlite_stat4 are only opened when
163 ** appropriate compile-time options are provided.
165 ** If the sqlite_statN tables do not previously exist, it is created.
167 ** Argument zWhere may be a pointer to a buffer containing a table name,
168 ** or it may be a NULL pointer. If it is not NULL, then all entries in
169 ** the sqlite_statN tables associated with the named table are deleted.
170 ** If zWhere==0, then code is generated to delete all stat table entries.
172 static void openStatTable(
173 Parse *pParse, /* Parsing context */
174 int iDb, /* The database we are looking in */
175 int iStatCur, /* Open the sqlite_stat1 table on this cursor */
176 const char *zWhere, /* Delete entries for this table or index */
177 const char *zWhereType /* Either "tbl" or "idx" */
179 static const struct {
180 const char *zName;
181 const char *zCols;
182 } aTable[] = {
183 { "sqlite_stat1", "tbl,idx,stat" },
184 #if defined(SQLITE_ENABLE_STAT4)
185 { "sqlite_stat4", "tbl,idx,neq,nlt,ndlt,sample" },
186 { "sqlite_stat3", 0 },
187 #elif defined(SQLITE_ENABLE_STAT3)
188 { "sqlite_stat3", "tbl,idx,neq,nlt,ndlt,sample" },
189 { "sqlite_stat4", 0 },
190 #else
191 { "sqlite_stat3", 0 },
192 { "sqlite_stat4", 0 },
193 #endif
195 int i;
196 sqlite3 *db = pParse->db;
197 Db *pDb;
198 Vdbe *v = sqlite3GetVdbe(pParse);
199 int aRoot[ArraySize(aTable)];
200 u8 aCreateTbl[ArraySize(aTable)];
202 if( v==0 ) return;
203 assert( sqlite3BtreeHoldsAllMutexes(db) );
204 assert( sqlite3VdbeDb(v)==db );
205 pDb = &db->aDb[iDb];
207 /* Create new statistic tables if they do not exist, or clear them
208 ** if they do already exist.
210 for(i=0; i<ArraySize(aTable); i++){
211 const char *zTab = aTable[i].zName;
212 Table *pStat;
213 if( (pStat = sqlite3FindTable(db, zTab, pDb->zName))==0 ){
214 if( aTable[i].zCols ){
215 /* The sqlite_statN table does not exist. Create it. Note that a
216 ** side-effect of the CREATE TABLE statement is to leave the rootpage
217 ** of the new table in register pParse->regRoot. This is important
218 ** because the OpenWrite opcode below will be needing it. */
219 sqlite3NestedParse(pParse,
220 "CREATE TABLE %Q.%s(%s)", pDb->zName, zTab, aTable[i].zCols
222 aRoot[i] = pParse->regRoot;
223 aCreateTbl[i] = OPFLAG_P2ISREG;
225 }else{
226 /* The table already exists. If zWhere is not NULL, delete all entries
227 ** associated with the table zWhere. If zWhere is NULL, delete the
228 ** entire contents of the table. */
229 aRoot[i] = pStat->tnum;
230 aCreateTbl[i] = 0;
231 sqlite3TableLock(pParse, iDb, aRoot[i], 1, zTab);
232 if( zWhere ){
233 sqlite3NestedParse(pParse,
234 "DELETE FROM %Q.%s WHERE %s=%Q",
235 pDb->zName, zTab, zWhereType, zWhere
237 }else{
238 /* The sqlite_stat[134] table already exists. Delete all rows. */
239 sqlite3VdbeAddOp2(v, OP_Clear, aRoot[i], iDb);
244 /* Open the sqlite_stat[134] tables for writing. */
245 for(i=0; aTable[i].zCols; i++){
246 assert( i<ArraySize(aTable) );
247 sqlite3VdbeAddOp4Int(v, OP_OpenWrite, iStatCur+i, aRoot[i], iDb, 3);
248 sqlite3VdbeChangeP5(v, aCreateTbl[i]);
249 VdbeComment((v, aTable[i].zName));
254 ** Recommended number of samples for sqlite_stat4
256 #ifndef SQLITE_STAT4_SAMPLES
257 # define SQLITE_STAT4_SAMPLES 24
258 #endif
261 ** Three SQL functions - stat_init(), stat_push(), and stat_get() -
262 ** share an instance of the following structure to hold their state
263 ** information.
265 typedef struct Stat4Accum Stat4Accum;
266 typedef struct Stat4Sample Stat4Sample;
267 struct Stat4Sample {
268 tRowcnt *anEq; /* sqlite_stat4.nEq */
269 tRowcnt *anDLt; /* sqlite_stat4.nDLt */
270 #ifdef SQLITE_ENABLE_STAT3_OR_STAT4
271 tRowcnt *anLt; /* sqlite_stat4.nLt */
272 union {
273 i64 iRowid; /* Rowid in main table of the key */
274 u8 *aRowid; /* Key for WITHOUT ROWID tables */
275 } u;
276 u32 nRowid; /* Sizeof aRowid[] */
277 u8 isPSample; /* True if a periodic sample */
278 int iCol; /* If !isPSample, the reason for inclusion */
279 u32 iHash; /* Tiebreaker hash */
280 #endif
282 struct Stat4Accum {
283 tRowcnt nRow; /* Number of rows in the entire table */
284 tRowcnt nPSample; /* How often to do a periodic sample */
285 int nCol; /* Number of columns in index + pk/rowid */
286 int nKeyCol; /* Number of index columns w/o the pk/rowid */
287 int mxSample; /* Maximum number of samples to accumulate */
288 Stat4Sample current; /* Current row as a Stat4Sample */
289 u32 iPrn; /* Pseudo-random number used for sampling */
290 Stat4Sample *aBest; /* Array of nCol best samples */
291 int iMin; /* Index in a[] of entry with minimum score */
292 int nSample; /* Current number of samples */
293 int iGet; /* Index of current sample accessed by stat_get() */
294 Stat4Sample *a; /* Array of mxSample Stat4Sample objects */
295 sqlite3 *db; /* Database connection, for malloc() */
298 /* Reclaim memory used by a Stat4Sample
300 #ifdef SQLITE_ENABLE_STAT3_OR_STAT4
301 static void sampleClear(sqlite3 *db, Stat4Sample *p){
302 assert( db!=0 );
303 if( p->nRowid ){
304 sqlite3DbFree(db, p->u.aRowid);
305 p->nRowid = 0;
308 #endif
310 /* Initialize the BLOB value of a ROWID
312 #ifdef SQLITE_ENABLE_STAT3_OR_STAT4
313 static void sampleSetRowid(sqlite3 *db, Stat4Sample *p, int n, const u8 *pData){
314 assert( db!=0 );
315 if( p->nRowid ) sqlite3DbFree(db, p->u.aRowid);
316 p->u.aRowid = sqlite3DbMallocRaw(db, n);
317 if( p->u.aRowid ){
318 p->nRowid = n;
319 memcpy(p->u.aRowid, pData, n);
320 }else{
321 p->nRowid = 0;
324 #endif
326 /* Initialize the INTEGER value of a ROWID.
328 #ifdef SQLITE_ENABLE_STAT3_OR_STAT4
329 static void sampleSetRowidInt64(sqlite3 *db, Stat4Sample *p, i64 iRowid){
330 assert( db!=0 );
331 if( p->nRowid ) sqlite3DbFree(db, p->u.aRowid);
332 p->nRowid = 0;
333 p->u.iRowid = iRowid;
335 #endif
339 ** Copy the contents of object (*pFrom) into (*pTo).
341 #ifdef SQLITE_ENABLE_STAT3_OR_STAT4
342 static void sampleCopy(Stat4Accum *p, Stat4Sample *pTo, Stat4Sample *pFrom){
343 pTo->isPSample = pFrom->isPSample;
344 pTo->iCol = pFrom->iCol;
345 pTo->iHash = pFrom->iHash;
346 memcpy(pTo->anEq, pFrom->anEq, sizeof(tRowcnt)*p->nCol);
347 memcpy(pTo->anLt, pFrom->anLt, sizeof(tRowcnt)*p->nCol);
348 memcpy(pTo->anDLt, pFrom->anDLt, sizeof(tRowcnt)*p->nCol);
349 if( pFrom->nRowid ){
350 sampleSetRowid(p->db, pTo, pFrom->nRowid, pFrom->u.aRowid);
351 }else{
352 sampleSetRowidInt64(p->db, pTo, pFrom->u.iRowid);
355 #endif
358 ** Reclaim all memory of a Stat4Accum structure.
360 static void stat4Destructor(void *pOld){
361 Stat4Accum *p = (Stat4Accum*)pOld;
362 #ifdef SQLITE_ENABLE_STAT3_OR_STAT4
363 int i;
364 for(i=0; i<p->nCol; i++) sampleClear(p->db, p->aBest+i);
365 for(i=0; i<p->mxSample; i++) sampleClear(p->db, p->a+i);
366 sampleClear(p->db, &p->current);
367 #endif
368 sqlite3DbFree(p->db, p);
372 ** Implementation of the stat_init(N,K,C) SQL function. The three parameters
373 ** are:
374 ** N: The number of columns in the index including the rowid/pk (note 1)
375 ** K: The number of columns in the index excluding the rowid/pk.
376 ** C: The number of rows in the index (note 2)
378 ** Note 1: In the special case of the covering index that implements a
379 ** WITHOUT ROWID table, N is the number of PRIMARY KEY columns, not the
380 ** total number of columns in the table.
382 ** Note 2: C is only used for STAT3 and STAT4.
384 ** For indexes on ordinary rowid tables, N==K+1. But for indexes on
385 ** WITHOUT ROWID tables, N=K+P where P is the number of columns in the
386 ** PRIMARY KEY of the table. The covering index that implements the
387 ** original WITHOUT ROWID table as N==K as a special case.
389 ** This routine allocates the Stat4Accum object in heap memory. The return
390 ** value is a pointer to the Stat4Accum object. The datatype of the
391 ** return value is BLOB, but it is really just a pointer to the Stat4Accum
392 ** object.
394 static void statInit(
395 sqlite3_context *context,
396 int argc,
397 sqlite3_value **argv
399 Stat4Accum *p;
400 int nCol; /* Number of columns in index being sampled */
401 int nKeyCol; /* Number of key columns */
402 int nColUp; /* nCol rounded up for alignment */
403 int n; /* Bytes of space to allocate */
404 sqlite3 *db; /* Database connection */
405 #ifdef SQLITE_ENABLE_STAT3_OR_STAT4
406 int mxSample = SQLITE_STAT4_SAMPLES;
407 #endif
409 /* Decode the three function arguments */
410 UNUSED_PARAMETER(argc);
411 nCol = sqlite3_value_int(argv[0]);
412 assert( nCol>0 );
413 nColUp = sizeof(tRowcnt)<8 ? (nCol+1)&~1 : nCol;
414 nKeyCol = sqlite3_value_int(argv[1]);
415 assert( nKeyCol<=nCol );
416 assert( nKeyCol>0 );
418 /* Allocate the space required for the Stat4Accum object */
419 n = sizeof(*p)
420 + sizeof(tRowcnt)*nColUp /* Stat4Accum.anEq */
421 + sizeof(tRowcnt)*nColUp /* Stat4Accum.anDLt */
422 #ifdef SQLITE_ENABLE_STAT3_OR_STAT4
423 + sizeof(tRowcnt)*nColUp /* Stat4Accum.anLt */
424 + sizeof(Stat4Sample)*(nCol+mxSample) /* Stat4Accum.aBest[], a[] */
425 + sizeof(tRowcnt)*3*nColUp*(nCol+mxSample)
426 #endif
428 db = sqlite3_context_db_handle(context);
429 p = sqlite3DbMallocZero(db, n);
430 if( p==0 ){
431 sqlite3_result_error_nomem(context);
432 return;
435 p->db = db;
436 p->nRow = 0;
437 p->nCol = nCol;
438 p->nKeyCol = nKeyCol;
439 p->current.anDLt = (tRowcnt*)&p[1];
440 p->current.anEq = &p->current.anDLt[nColUp];
442 #ifdef SQLITE_ENABLE_STAT3_OR_STAT4
444 u8 *pSpace; /* Allocated space not yet assigned */
445 int i; /* Used to iterate through p->aSample[] */
447 p->iGet = -1;
448 p->mxSample = mxSample;
449 p->nPSample = (tRowcnt)(sqlite3_value_int64(argv[2])/(mxSample/3+1) + 1);
450 p->current.anLt = &p->current.anEq[nColUp];
451 p->iPrn = nCol*0x689e962d ^ sqlite3_value_int(argv[2])*0xd0944565;
453 /* Set up the Stat4Accum.a[] and aBest[] arrays */
454 p->a = (struct Stat4Sample*)&p->current.anLt[nColUp];
455 p->aBest = &p->a[mxSample];
456 pSpace = (u8*)(&p->a[mxSample+nCol]);
457 for(i=0; i<(mxSample+nCol); i++){
458 p->a[i].anEq = (tRowcnt *)pSpace; pSpace += (sizeof(tRowcnt) * nColUp);
459 p->a[i].anLt = (tRowcnt *)pSpace; pSpace += (sizeof(tRowcnt) * nColUp);
460 p->a[i].anDLt = (tRowcnt *)pSpace; pSpace += (sizeof(tRowcnt) * nColUp);
462 assert( (pSpace - (u8*)p)==n );
464 for(i=0; i<nCol; i++){
465 p->aBest[i].iCol = i;
468 #endif
470 /* Return a pointer to the allocated object to the caller. Note that
471 ** only the pointer (the 2nd parameter) matters. The size of the object
472 ** (given by the 3rd parameter) is never used and can be any positive
473 ** value. */
474 sqlite3_result_blob(context, p, sizeof(*p), stat4Destructor);
476 static const FuncDef statInitFuncdef = {
477 2+IsStat34, /* nArg */
478 SQLITE_UTF8, /* funcFlags */
479 0, /* pUserData */
480 0, /* pNext */
481 statInit, /* xFunc */
482 0, /* xStep */
483 0, /* xFinalize */
484 "stat_init", /* zName */
485 0, /* pHash */
486 0 /* pDestructor */
489 #ifdef SQLITE_ENABLE_STAT4
491 ** pNew and pOld are both candidate non-periodic samples selected for
492 ** the same column (pNew->iCol==pOld->iCol). Ignoring this column and
493 ** considering only any trailing columns and the sample hash value, this
494 ** function returns true if sample pNew is to be preferred over pOld.
495 ** In other words, if we assume that the cardinalities of the selected
496 ** column for pNew and pOld are equal, is pNew to be preferred over pOld.
498 ** This function assumes that for each argument sample, the contents of
499 ** the anEq[] array from pSample->anEq[pSample->iCol+1] onwards are valid.
501 static int sampleIsBetterPost(
502 Stat4Accum *pAccum,
503 Stat4Sample *pNew,
504 Stat4Sample *pOld
506 int nCol = pAccum->nCol;
507 int i;
508 assert( pNew->iCol==pOld->iCol );
509 for(i=pNew->iCol+1; i<nCol; i++){
510 if( pNew->anEq[i]>pOld->anEq[i] ) return 1;
511 if( pNew->anEq[i]<pOld->anEq[i] ) return 0;
513 if( pNew->iHash>pOld->iHash ) return 1;
514 return 0;
516 #endif
518 #ifdef SQLITE_ENABLE_STAT3_OR_STAT4
520 ** Return true if pNew is to be preferred over pOld.
522 ** This function assumes that for each argument sample, the contents of
523 ** the anEq[] array from pSample->anEq[pSample->iCol] onwards are valid.
525 static int sampleIsBetter(
526 Stat4Accum *pAccum,
527 Stat4Sample *pNew,
528 Stat4Sample *pOld
530 tRowcnt nEqNew = pNew->anEq[pNew->iCol];
531 tRowcnt nEqOld = pOld->anEq[pOld->iCol];
533 assert( pOld->isPSample==0 && pNew->isPSample==0 );
534 assert( IsStat4 || (pNew->iCol==0 && pOld->iCol==0) );
536 if( (nEqNew>nEqOld) ) return 1;
537 #ifdef SQLITE_ENABLE_STAT4
538 if( nEqNew==nEqOld ){
539 if( pNew->iCol<pOld->iCol ) return 1;
540 return (pNew->iCol==pOld->iCol && sampleIsBetterPost(pAccum, pNew, pOld));
542 return 0;
543 #else
544 return (nEqNew==nEqOld && pNew->iHash>pOld->iHash);
545 #endif
549 ** Copy the contents of sample *pNew into the p->a[] array. If necessary,
550 ** remove the least desirable sample from p->a[] to make room.
552 static void sampleInsert(Stat4Accum *p, Stat4Sample *pNew, int nEqZero){
553 Stat4Sample *pSample = 0;
554 int i;
556 assert( IsStat4 || nEqZero==0 );
558 #ifdef SQLITE_ENABLE_STAT4
559 if( pNew->isPSample==0 ){
560 Stat4Sample *pUpgrade = 0;
561 assert( pNew->anEq[pNew->iCol]>0 );
563 /* This sample is being added because the prefix that ends in column
564 ** iCol occurs many times in the table. However, if we have already
565 ** added a sample that shares this prefix, there is no need to add
566 ** this one. Instead, upgrade the priority of the highest priority
567 ** existing sample that shares this prefix. */
568 for(i=p->nSample-1; i>=0; i--){
569 Stat4Sample *pOld = &p->a[i];
570 if( pOld->anEq[pNew->iCol]==0 ){
571 if( pOld->isPSample ) return;
572 assert( pOld->iCol>pNew->iCol );
573 assert( sampleIsBetter(p, pNew, pOld) );
574 if( pUpgrade==0 || sampleIsBetter(p, pOld, pUpgrade) ){
575 pUpgrade = pOld;
579 if( pUpgrade ){
580 pUpgrade->iCol = pNew->iCol;
581 pUpgrade->anEq[pUpgrade->iCol] = pNew->anEq[pUpgrade->iCol];
582 goto find_new_min;
585 #endif
587 /* If necessary, remove sample iMin to make room for the new sample. */
588 if( p->nSample>=p->mxSample ){
589 Stat4Sample *pMin = &p->a[p->iMin];
590 tRowcnt *anEq = pMin->anEq;
591 tRowcnt *anLt = pMin->anLt;
592 tRowcnt *anDLt = pMin->anDLt;
593 sampleClear(p->db, pMin);
594 memmove(pMin, &pMin[1], sizeof(p->a[0])*(p->nSample-p->iMin-1));
595 pSample = &p->a[p->nSample-1];
596 pSample->nRowid = 0;
597 pSample->anEq = anEq;
598 pSample->anDLt = anDLt;
599 pSample->anLt = anLt;
600 p->nSample = p->mxSample-1;
603 /* The "rows less-than" for the rowid column must be greater than that
604 ** for the last sample in the p->a[] array. Otherwise, the samples would
605 ** be out of order. */
606 #ifdef SQLITE_ENABLE_STAT4
607 assert( p->nSample==0
608 || pNew->anLt[p->nCol-1] > p->a[p->nSample-1].anLt[p->nCol-1] );
609 #endif
611 /* Insert the new sample */
612 pSample = &p->a[p->nSample];
613 sampleCopy(p, pSample, pNew);
614 p->nSample++;
616 /* Zero the first nEqZero entries in the anEq[] array. */
617 memset(pSample->anEq, 0, sizeof(tRowcnt)*nEqZero);
619 #ifdef SQLITE_ENABLE_STAT4
620 find_new_min:
621 #endif
622 if( p->nSample>=p->mxSample ){
623 int iMin = -1;
624 for(i=0; i<p->mxSample; i++){
625 if( p->a[i].isPSample ) continue;
626 if( iMin<0 || sampleIsBetter(p, &p->a[iMin], &p->a[i]) ){
627 iMin = i;
630 assert( iMin>=0 );
631 p->iMin = iMin;
634 #endif /* SQLITE_ENABLE_STAT3_OR_STAT4 */
637 ** Field iChng of the index being scanned has changed. So at this point
638 ** p->current contains a sample that reflects the previous row of the
639 ** index. The value of anEq[iChng] and subsequent anEq[] elements are
640 ** correct at this point.
642 static void samplePushPrevious(Stat4Accum *p, int iChng){
643 #ifdef SQLITE_ENABLE_STAT4
644 int i;
646 /* Check if any samples from the aBest[] array should be pushed
647 ** into IndexSample.a[] at this point. */
648 for(i=(p->nCol-2); i>=iChng; i--){
649 Stat4Sample *pBest = &p->aBest[i];
650 pBest->anEq[i] = p->current.anEq[i];
651 if( p->nSample<p->mxSample || sampleIsBetter(p, pBest, &p->a[p->iMin]) ){
652 sampleInsert(p, pBest, i);
656 /* Update the anEq[] fields of any samples already collected. */
657 for(i=p->nSample-1; i>=0; i--){
658 int j;
659 for(j=iChng; j<p->nCol; j++){
660 if( p->a[i].anEq[j]==0 ) p->a[i].anEq[j] = p->current.anEq[j];
663 #endif
665 #if defined(SQLITE_ENABLE_STAT3) && !defined(SQLITE_ENABLE_STAT4)
666 if( iChng==0 ){
667 tRowcnt nLt = p->current.anLt[0];
668 tRowcnt nEq = p->current.anEq[0];
670 /* Check if this is to be a periodic sample. If so, add it. */
671 if( (nLt/p->nPSample)!=(nLt+nEq)/p->nPSample ){
672 p->current.isPSample = 1;
673 sampleInsert(p, &p->current, 0);
674 p->current.isPSample = 0;
675 }else
677 /* Or if it is a non-periodic sample. Add it in this case too. */
678 if( p->nSample<p->mxSample
679 || sampleIsBetter(p, &p->current, &p->a[p->iMin])
681 sampleInsert(p, &p->current, 0);
684 #endif
686 #ifndef SQLITE_ENABLE_STAT3_OR_STAT4
687 UNUSED_PARAMETER( p );
688 UNUSED_PARAMETER( iChng );
689 #endif
693 ** Implementation of the stat_push SQL function: stat_push(P,C,R)
694 ** Arguments:
696 ** P Pointer to the Stat4Accum object created by stat_init()
697 ** C Index of left-most column to differ from previous row
698 ** R Rowid for the current row. Might be a key record for
699 ** WITHOUT ROWID tables.
701 ** This SQL function always returns NULL. It's purpose it to accumulate
702 ** statistical data and/or samples in the Stat4Accum object about the
703 ** index being analyzed. The stat_get() SQL function will later be used to
704 ** extract relevant information for constructing the sqlite_statN tables.
706 ** The R parameter is only used for STAT3 and STAT4
708 static void statPush(
709 sqlite3_context *context,
710 int argc,
711 sqlite3_value **argv
713 int i;
715 /* The three function arguments */
716 Stat4Accum *p = (Stat4Accum*)sqlite3_value_blob(argv[0]);
717 int iChng = sqlite3_value_int(argv[1]);
719 UNUSED_PARAMETER( argc );
720 UNUSED_PARAMETER( context );
721 assert( p->nCol>0 );
722 assert( iChng<p->nCol );
724 if( p->nRow==0 ){
725 /* This is the first call to this function. Do initialization. */
726 for(i=0; i<p->nCol; i++) p->current.anEq[i] = 1;
727 }else{
728 /* Second and subsequent calls get processed here */
729 samplePushPrevious(p, iChng);
731 /* Update anDLt[], anLt[] and anEq[] to reflect the values that apply
732 ** to the current row of the index. */
733 for(i=0; i<iChng; i++){
734 p->current.anEq[i]++;
736 for(i=iChng; i<p->nCol; i++){
737 p->current.anDLt[i]++;
738 #ifdef SQLITE_ENABLE_STAT3_OR_STAT4
739 p->current.anLt[i] += p->current.anEq[i];
740 #endif
741 p->current.anEq[i] = 1;
744 p->nRow++;
745 #ifdef SQLITE_ENABLE_STAT3_OR_STAT4
746 if( sqlite3_value_type(argv[2])==SQLITE_INTEGER ){
747 sampleSetRowidInt64(p->db, &p->current, sqlite3_value_int64(argv[2]));
748 }else{
749 sampleSetRowid(p->db, &p->current, sqlite3_value_bytes(argv[2]),
750 sqlite3_value_blob(argv[2]));
752 p->current.iHash = p->iPrn = p->iPrn*1103515245 + 12345;
753 #endif
755 #ifdef SQLITE_ENABLE_STAT4
757 tRowcnt nLt = p->current.anLt[p->nCol-1];
759 /* Check if this is to be a periodic sample. If so, add it. */
760 if( (nLt/p->nPSample)!=(nLt+1)/p->nPSample ){
761 p->current.isPSample = 1;
762 p->current.iCol = 0;
763 sampleInsert(p, &p->current, p->nCol-1);
764 p->current.isPSample = 0;
767 /* Update the aBest[] array. */
768 for(i=0; i<(p->nCol-1); i++){
769 p->current.iCol = i;
770 if( i>=iChng || sampleIsBetterPost(p, &p->current, &p->aBest[i]) ){
771 sampleCopy(p, &p->aBest[i], &p->current);
775 #endif
777 static const FuncDef statPushFuncdef = {
778 2+IsStat34, /* nArg */
779 SQLITE_UTF8, /* funcFlags */
780 0, /* pUserData */
781 0, /* pNext */
782 statPush, /* xFunc */
783 0, /* xStep */
784 0, /* xFinalize */
785 "stat_push", /* zName */
786 0, /* pHash */
787 0 /* pDestructor */
790 #define STAT_GET_STAT1 0 /* "stat" column of stat1 table */
791 #define STAT_GET_ROWID 1 /* "rowid" column of stat[34] entry */
792 #define STAT_GET_NEQ 2 /* "neq" column of stat[34] entry */
793 #define STAT_GET_NLT 3 /* "nlt" column of stat[34] entry */
794 #define STAT_GET_NDLT 4 /* "ndlt" column of stat[34] entry */
797 ** Implementation of the stat_get(P,J) SQL function. This routine is
798 ** used to query statistical information that has been gathered into
799 ** the Stat4Accum object by prior calls to stat_push(). The P parameter
800 ** has type BLOB but it is really just a pointer to the Stat4Accum object.
801 ** The content to returned is determined by the parameter J
802 ** which is one of the STAT_GET_xxxx values defined above.
804 ** If neither STAT3 nor STAT4 are enabled, then J is always
805 ** STAT_GET_STAT1 and is hence omitted and this routine becomes
806 ** a one-parameter function, stat_get(P), that always returns the
807 ** stat1 table entry information.
809 static void statGet(
810 sqlite3_context *context,
811 int argc,
812 sqlite3_value **argv
814 Stat4Accum *p = (Stat4Accum*)sqlite3_value_blob(argv[0]);
815 #ifdef SQLITE_ENABLE_STAT3_OR_STAT4
816 /* STAT3 and STAT4 have a parameter on this routine. */
817 int eCall = sqlite3_value_int(argv[1]);
818 assert( argc==2 );
819 assert( eCall==STAT_GET_STAT1 || eCall==STAT_GET_NEQ
820 || eCall==STAT_GET_ROWID || eCall==STAT_GET_NLT
821 || eCall==STAT_GET_NDLT
823 if( eCall==STAT_GET_STAT1 )
824 #else
825 assert( argc==1 );
826 #endif
828 /* Return the value to store in the "stat" column of the sqlite_stat1
829 ** table for this index.
831 ** The value is a string composed of a list of integers describing
832 ** the index. The first integer in the list is the total number of
833 ** entries in the index. There is one additional integer in the list
834 ** for each indexed column. This additional integer is an estimate of
835 ** the number of rows matched by a stabbing query on the index using
836 ** a key with the corresponding number of fields. In other words,
837 ** if the index is on columns (a,b) and the sqlite_stat1 value is
838 ** "100 10 2", then SQLite estimates that:
840 ** * the index contains 100 rows,
841 ** * "WHERE a=?" matches 10 rows, and
842 ** * "WHERE a=? AND b=?" matches 2 rows.
844 ** If D is the count of distinct values and K is the total number of
845 ** rows, then each estimate is computed as:
847 ** I = (K+D-1)/D
849 char *z;
850 int i;
852 char *zRet = sqlite3MallocZero( (p->nKeyCol+1)*25 );
853 if( zRet==0 ){
854 sqlite3_result_error_nomem(context);
855 return;
858 sqlite3_snprintf(24, zRet, "%llu", (u64)p->nRow);
859 z = zRet + sqlite3Strlen30(zRet);
860 for(i=0; i<p->nKeyCol; i++){
861 u64 nDistinct = p->current.anDLt[i] + 1;
862 u64 iVal = (p->nRow + nDistinct - 1) / nDistinct;
863 sqlite3_snprintf(24, z, " %llu", iVal);
864 z += sqlite3Strlen30(z);
865 assert( p->current.anEq[i] );
867 assert( z[0]=='\0' && z>zRet );
869 sqlite3_result_text(context, zRet, -1, sqlite3_free);
871 #ifdef SQLITE_ENABLE_STAT3_OR_STAT4
872 else if( eCall==STAT_GET_ROWID ){
873 if( p->iGet<0 ){
874 samplePushPrevious(p, 0);
875 p->iGet = 0;
877 if( p->iGet<p->nSample ){
878 Stat4Sample *pS = p->a + p->iGet;
879 if( pS->nRowid==0 ){
880 sqlite3_result_int64(context, pS->u.iRowid);
881 }else{
882 sqlite3_result_blob(context, pS->u.aRowid, pS->nRowid,
883 SQLITE_TRANSIENT);
886 }else{
887 tRowcnt *aCnt = 0;
889 assert( p->iGet<p->nSample );
890 switch( eCall ){
891 case STAT_GET_NEQ: aCnt = p->a[p->iGet].anEq; break;
892 case STAT_GET_NLT: aCnt = p->a[p->iGet].anLt; break;
893 default: {
894 aCnt = p->a[p->iGet].anDLt;
895 p->iGet++;
896 break;
900 if( IsStat3 ){
901 sqlite3_result_int64(context, (i64)aCnt[0]);
902 }else{
903 char *zRet = sqlite3MallocZero(p->nCol * 25);
904 if( zRet==0 ){
905 sqlite3_result_error_nomem(context);
906 }else{
907 int i;
908 char *z = zRet;
909 for(i=0; i<p->nCol; i++){
910 sqlite3_snprintf(24, z, "%llu ", (u64)aCnt[i]);
911 z += sqlite3Strlen30(z);
913 assert( z[0]=='\0' && z>zRet );
914 z[-1] = '\0';
915 sqlite3_result_text(context, zRet, -1, sqlite3_free);
919 #endif /* SQLITE_ENABLE_STAT3_OR_STAT4 */
920 #ifndef SQLITE_DEBUG
921 UNUSED_PARAMETER( argc );
922 #endif
924 static const FuncDef statGetFuncdef = {
925 1+IsStat34, /* nArg */
926 SQLITE_UTF8, /* funcFlags */
927 0, /* pUserData */
928 0, /* pNext */
929 statGet, /* xFunc */
930 0, /* xStep */
931 0, /* xFinalize */
932 "stat_get", /* zName */
933 0, /* pHash */
934 0 /* pDestructor */
937 static void callStatGet(Vdbe *v, int regStat4, int iParam, int regOut){
938 assert( regOut!=regStat4 && regOut!=regStat4+1 );
939 #ifdef SQLITE_ENABLE_STAT3_OR_STAT4
940 sqlite3VdbeAddOp2(v, OP_Integer, iParam, regStat4+1);
941 #elif SQLITE_DEBUG
942 assert( iParam==STAT_GET_STAT1 );
943 #else
944 UNUSED_PARAMETER( iParam );
945 #endif
946 sqlite3VdbeAddOp3(v, OP_Function, 0, regStat4, regOut);
947 sqlite3VdbeChangeP4(v, -1, (char*)&statGetFuncdef, P4_FUNCDEF);
948 sqlite3VdbeChangeP5(v, 1 + IsStat34);
952 ** Generate code to do an analysis of all indices associated with
953 ** a single table.
955 static void analyzeOneTable(
956 Parse *pParse, /* Parser context */
957 Table *pTab, /* Table whose indices are to be analyzed */
958 Index *pOnlyIdx, /* If not NULL, only analyze this one index */
959 int iStatCur, /* Index of VdbeCursor that writes the sqlite_stat1 table */
960 int iMem, /* Available memory locations begin here */
961 int iTab /* Next available cursor */
963 sqlite3 *db = pParse->db; /* Database handle */
964 Index *pIdx; /* An index to being analyzed */
965 int iIdxCur; /* Cursor open on index being analyzed */
966 int iTabCur; /* Table cursor */
967 Vdbe *v; /* The virtual machine being built up */
968 int i; /* Loop counter */
969 int jZeroRows = -1; /* Jump from here if number of rows is zero */
970 int iDb; /* Index of database containing pTab */
971 u8 needTableCnt = 1; /* True to count the table */
972 int regNewRowid = iMem++; /* Rowid for the inserted record */
973 int regStat4 = iMem++; /* Register to hold Stat4Accum object */
974 int regChng = iMem++; /* Index of changed index field */
975 #ifdef SQLITE_ENABLE_STAT3_OR_STAT4
976 int regRowid = iMem++; /* Rowid argument passed to stat_push() */
977 #endif
978 int regTemp = iMem++; /* Temporary use register */
979 int regTabname = iMem++; /* Register containing table name */
980 int regIdxname = iMem++; /* Register containing index name */
981 int regStat1 = iMem++; /* Value for the stat column of sqlite_stat1 */
982 int regPrev = iMem; /* MUST BE LAST (see below) */
984 pParse->nMem = MAX(pParse->nMem, iMem);
985 v = sqlite3GetVdbe(pParse);
986 if( v==0 || NEVER(pTab==0) ){
987 return;
989 if( pTab->tnum==0 ){
990 /* Do not gather statistics on views or virtual tables */
991 return;
993 if( sqlite3_strnicmp(pTab->zName, "sqlite_", 7)==0 ){
994 /* Do not gather statistics on system tables */
995 return;
997 assert( sqlite3BtreeHoldsAllMutexes(db) );
998 iDb = sqlite3SchemaToIndex(db, pTab->pSchema);
999 assert( iDb>=0 );
1000 assert( sqlite3SchemaMutexHeld(db, iDb, 0) );
1001 #ifndef SQLITE_OMIT_AUTHORIZATION
1002 if( sqlite3AuthCheck(pParse, SQLITE_ANALYZE, pTab->zName, 0,
1003 db->aDb[iDb].zName ) ){
1004 return;
1006 #endif
1008 /* Establish a read-lock on the table at the shared-cache level.
1009 ** Open a read-only cursor on the table. Also allocate a cursor number
1010 ** to use for scanning indexes (iIdxCur). No index cursor is opened at
1011 ** this time though. */
1012 sqlite3TableLock(pParse, iDb, pTab->tnum, 0, pTab->zName);
1013 iTabCur = iTab++;
1014 iIdxCur = iTab++;
1015 pParse->nTab = MAX(pParse->nTab, iTab);
1016 sqlite3OpenTable(pParse, iTabCur, iDb, pTab, OP_OpenRead);
1017 sqlite3VdbeAddOp4(v, OP_String8, 0, regTabname, 0, pTab->zName, 0);
1019 for(pIdx=pTab->pIndex; pIdx; pIdx=pIdx->pNext){
1020 int nCol; /* Number of columns in pIdx. "N" */
1021 int addrRewind; /* Address of "OP_Rewind iIdxCur" */
1022 int addrNextRow; /* Address of "next_row:" */
1023 const char *zIdxName; /* Name of the index */
1024 int nColTest; /* Number of columns to test for changes */
1026 if( pOnlyIdx && pOnlyIdx!=pIdx ) continue;
1027 if( pIdx->pPartIdxWhere==0 ) needTableCnt = 0;
1028 if( !HasRowid(pTab) && IsPrimaryKeyIndex(pIdx) ){
1029 nCol = pIdx->nKeyCol;
1030 zIdxName = pTab->zName;
1031 nColTest = nCol - 1;
1032 }else{
1033 nCol = pIdx->nColumn;
1034 zIdxName = pIdx->zName;
1035 nColTest = pIdx->uniqNotNull ? pIdx->nKeyCol-1 : nCol-1;
1038 /* Populate the register containing the index name. */
1039 sqlite3VdbeAddOp4(v, OP_String8, 0, regIdxname, 0, zIdxName, 0);
1040 VdbeComment((v, "Analysis for %s.%s", pTab->zName, zIdxName));
1043 ** Pseudo-code for loop that calls stat_push():
1045 ** Rewind csr
1046 ** if eof(csr) goto end_of_scan;
1047 ** regChng = 0
1048 ** goto chng_addr_0;
1050 ** next_row:
1051 ** regChng = 0
1052 ** if( idx(0) != regPrev(0) ) goto chng_addr_0
1053 ** regChng = 1
1054 ** if( idx(1) != regPrev(1) ) goto chng_addr_1
1055 ** ...
1056 ** regChng = N
1057 ** goto chng_addr_N
1059 ** chng_addr_0:
1060 ** regPrev(0) = idx(0)
1061 ** chng_addr_1:
1062 ** regPrev(1) = idx(1)
1063 ** ...
1065 ** endDistinctTest:
1066 ** regRowid = idx(rowid)
1067 ** stat_push(P, regChng, regRowid)
1068 ** Next csr
1069 ** if !eof(csr) goto next_row;
1071 ** end_of_scan:
1074 /* Make sure there are enough memory cells allocated to accommodate
1075 ** the regPrev array and a trailing rowid (the rowid slot is required
1076 ** when building a record to insert into the sample column of
1077 ** the sqlite_stat4 table. */
1078 pParse->nMem = MAX(pParse->nMem, regPrev+nColTest);
1080 /* Open a read-only cursor on the index being analyzed. */
1081 assert( iDb==sqlite3SchemaToIndex(db, pIdx->pSchema) );
1082 sqlite3VdbeAddOp3(v, OP_OpenRead, iIdxCur, pIdx->tnum, iDb);
1083 sqlite3VdbeSetP4KeyInfo(pParse, pIdx);
1084 VdbeComment((v, "%s", pIdx->zName));
1086 /* Invoke the stat_init() function. The arguments are:
1088 ** (1) the number of columns in the index including the rowid
1089 ** (or for a WITHOUT ROWID table, the number of PK columns),
1090 ** (2) the number of columns in the key without the rowid/pk
1091 ** (3) the number of rows in the index,
1094 ** The third argument is only used for STAT3 and STAT4
1096 #ifdef SQLITE_ENABLE_STAT3_OR_STAT4
1097 sqlite3VdbeAddOp2(v, OP_Count, iIdxCur, regStat4+3);
1098 #endif
1099 sqlite3VdbeAddOp2(v, OP_Integer, nCol, regStat4+1);
1100 sqlite3VdbeAddOp2(v, OP_Integer, pIdx->nKeyCol, regStat4+2);
1101 sqlite3VdbeAddOp3(v, OP_Function, 0, regStat4+1, regStat4);
1102 sqlite3VdbeChangeP4(v, -1, (char*)&statInitFuncdef, P4_FUNCDEF);
1103 sqlite3VdbeChangeP5(v, 2+IsStat34);
1105 /* Implementation of the following:
1107 ** Rewind csr
1108 ** if eof(csr) goto end_of_scan;
1109 ** regChng = 0
1110 ** goto next_push_0;
1113 addrRewind = sqlite3VdbeAddOp1(v, OP_Rewind, iIdxCur);
1114 VdbeCoverage(v);
1115 sqlite3VdbeAddOp2(v, OP_Integer, 0, regChng);
1116 addrNextRow = sqlite3VdbeCurrentAddr(v);
1118 if( nColTest>0 ){
1119 int endDistinctTest = sqlite3VdbeMakeLabel(v);
1120 int *aGotoChng; /* Array of jump instruction addresses */
1121 aGotoChng = sqlite3DbMallocRaw(db, sizeof(int)*nColTest);
1122 if( aGotoChng==0 ) continue;
1125 ** next_row:
1126 ** regChng = 0
1127 ** if( idx(0) != regPrev(0) ) goto chng_addr_0
1128 ** regChng = 1
1129 ** if( idx(1) != regPrev(1) ) goto chng_addr_1
1130 ** ...
1131 ** regChng = N
1132 ** goto endDistinctTest
1134 sqlite3VdbeAddOp0(v, OP_Goto);
1135 addrNextRow = sqlite3VdbeCurrentAddr(v);
1136 if( nColTest==1 && pIdx->nKeyCol==1 && IsUniqueIndex(pIdx) ){
1137 /* For a single-column UNIQUE index, once we have found a non-NULL
1138 ** row, we know that all the rest will be distinct, so skip
1139 ** subsequent distinctness tests. */
1140 sqlite3VdbeAddOp2(v, OP_NotNull, regPrev, endDistinctTest);
1141 VdbeCoverage(v);
1143 for(i=0; i<nColTest; i++){
1144 char *pColl = (char*)sqlite3LocateCollSeq(pParse, pIdx->azColl[i]);
1145 sqlite3VdbeAddOp2(v, OP_Integer, i, regChng);
1146 sqlite3VdbeAddOp3(v, OP_Column, iIdxCur, i, regTemp);
1147 aGotoChng[i] =
1148 sqlite3VdbeAddOp4(v, OP_Ne, regTemp, 0, regPrev+i, pColl, P4_COLLSEQ);
1149 sqlite3VdbeChangeP5(v, SQLITE_NULLEQ);
1150 VdbeCoverage(v);
1152 sqlite3VdbeAddOp2(v, OP_Integer, nColTest, regChng);
1153 sqlite3VdbeAddOp2(v, OP_Goto, 0, endDistinctTest);
1157 ** chng_addr_0:
1158 ** regPrev(0) = idx(0)
1159 ** chng_addr_1:
1160 ** regPrev(1) = idx(1)
1161 ** ...
1163 sqlite3VdbeJumpHere(v, addrNextRow-1);
1164 for(i=0; i<nColTest; i++){
1165 sqlite3VdbeJumpHere(v, aGotoChng[i]);
1166 sqlite3VdbeAddOp3(v, OP_Column, iIdxCur, i, regPrev+i);
1168 sqlite3VdbeResolveLabel(v, endDistinctTest);
1169 sqlite3DbFree(db, aGotoChng);
1173 ** chng_addr_N:
1174 ** regRowid = idx(rowid) // STAT34 only
1175 ** stat_push(P, regChng, regRowid) // 3rd parameter STAT34 only
1176 ** Next csr
1177 ** if !eof(csr) goto next_row;
1179 #ifdef SQLITE_ENABLE_STAT3_OR_STAT4
1180 assert( regRowid==(regStat4+2) );
1181 if( HasRowid(pTab) ){
1182 sqlite3VdbeAddOp2(v, OP_IdxRowid, iIdxCur, regRowid);
1183 }else{
1184 Index *pPk = sqlite3PrimaryKeyIndex(pIdx->pTable);
1185 int j, k, regKey;
1186 regKey = sqlite3GetTempRange(pParse, pPk->nKeyCol);
1187 for(j=0; j<pPk->nKeyCol; j++){
1188 k = sqlite3ColumnOfIndex(pIdx, pPk->aiColumn[j]);
1189 sqlite3VdbeAddOp3(v, OP_Column, iIdxCur, k, regKey+j);
1190 VdbeComment((v, "%s", pTab->aCol[pPk->aiColumn[j]].zName));
1192 sqlite3VdbeAddOp3(v, OP_MakeRecord, regKey, pPk->nKeyCol, regRowid);
1193 sqlite3ReleaseTempRange(pParse, regKey, pPk->nKeyCol);
1195 #endif
1196 assert( regChng==(regStat4+1) );
1197 sqlite3VdbeAddOp3(v, OP_Function, 1, regStat4, regTemp);
1198 sqlite3VdbeChangeP4(v, -1, (char*)&statPushFuncdef, P4_FUNCDEF);
1199 sqlite3VdbeChangeP5(v, 2+IsStat34);
1200 sqlite3VdbeAddOp2(v, OP_Next, iIdxCur, addrNextRow); VdbeCoverage(v);
1202 /* Add the entry to the stat1 table. */
1203 callStatGet(v, regStat4, STAT_GET_STAT1, regStat1);
1204 assert( "BBB"[0]==SQLITE_AFF_TEXT );
1205 sqlite3VdbeAddOp4(v, OP_MakeRecord, regTabname, 3, regTemp, "BBB", 0);
1206 sqlite3VdbeAddOp2(v, OP_NewRowid, iStatCur, regNewRowid);
1207 sqlite3VdbeAddOp3(v, OP_Insert, iStatCur, regTemp, regNewRowid);
1208 sqlite3VdbeChangeP5(v, OPFLAG_APPEND);
1210 /* Add the entries to the stat3 or stat4 table. */
1211 #ifdef SQLITE_ENABLE_STAT3_OR_STAT4
1213 int regEq = regStat1;
1214 int regLt = regStat1+1;
1215 int regDLt = regStat1+2;
1216 int regSample = regStat1+3;
1217 int regCol = regStat1+4;
1218 int regSampleRowid = regCol + nCol;
1219 int addrNext;
1220 int addrIsNull;
1221 u8 seekOp = HasRowid(pTab) ? OP_NotExists : OP_NotFound;
1223 pParse->nMem = MAX(pParse->nMem, regCol+nCol);
1225 addrNext = sqlite3VdbeCurrentAddr(v);
1226 callStatGet(v, regStat4, STAT_GET_ROWID, regSampleRowid);
1227 addrIsNull = sqlite3VdbeAddOp1(v, OP_IsNull, regSampleRowid);
1228 VdbeCoverage(v);
1229 callStatGet(v, regStat4, STAT_GET_NEQ, regEq);
1230 callStatGet(v, regStat4, STAT_GET_NLT, regLt);
1231 callStatGet(v, regStat4, STAT_GET_NDLT, regDLt);
1232 sqlite3VdbeAddOp4Int(v, seekOp, iTabCur, addrNext, regSampleRowid, 0);
1233 /* We know that the regSampleRowid row exists because it was read by
1234 ** the previous loop. Thus the not-found jump of seekOp will never
1235 ** be taken */
1236 VdbeCoverageNeverTaken(v);
1237 #ifdef SQLITE_ENABLE_STAT3
1238 sqlite3ExprCodeGetColumnOfTable(v, pTab, iTabCur,
1239 pIdx->aiColumn[0], regSample);
1240 #else
1241 for(i=0; i<nCol; i++){
1242 i16 iCol = pIdx->aiColumn[i];
1243 sqlite3ExprCodeGetColumnOfTable(v, pTab, iTabCur, iCol, regCol+i);
1245 sqlite3VdbeAddOp3(v, OP_MakeRecord, regCol, nCol, regSample);
1246 #endif
1247 sqlite3VdbeAddOp3(v, OP_MakeRecord, regTabname, 6, regTemp);
1248 sqlite3VdbeAddOp2(v, OP_NewRowid, iStatCur+1, regNewRowid);
1249 sqlite3VdbeAddOp3(v, OP_Insert, iStatCur+1, regTemp, regNewRowid);
1250 sqlite3VdbeAddOp2(v, OP_Goto, 1, addrNext); /* P1==1 for end-of-loop */
1251 sqlite3VdbeJumpHere(v, addrIsNull);
1253 #endif /* SQLITE_ENABLE_STAT3_OR_STAT4 */
1255 /* End of analysis */
1256 sqlite3VdbeJumpHere(v, addrRewind);
1260 /* Create a single sqlite_stat1 entry containing NULL as the index
1261 ** name and the row count as the content.
1263 if( pOnlyIdx==0 && needTableCnt ){
1264 VdbeComment((v, "%s", pTab->zName));
1265 sqlite3VdbeAddOp2(v, OP_Count, iTabCur, regStat1);
1266 jZeroRows = sqlite3VdbeAddOp1(v, OP_IfNot, regStat1); VdbeCoverage(v);
1267 sqlite3VdbeAddOp2(v, OP_Null, 0, regIdxname);
1268 assert( "BBB"[0]==SQLITE_AFF_TEXT );
1269 sqlite3VdbeAddOp4(v, OP_MakeRecord, regTabname, 3, regTemp, "BBB", 0);
1270 sqlite3VdbeAddOp2(v, OP_NewRowid, iStatCur, regNewRowid);
1271 sqlite3VdbeAddOp3(v, OP_Insert, iStatCur, regTemp, regNewRowid);
1272 sqlite3VdbeChangeP5(v, OPFLAG_APPEND);
1273 sqlite3VdbeJumpHere(v, jZeroRows);
1279 ** Generate code that will cause the most recent index analysis to
1280 ** be loaded into internal hash tables where is can be used.
1282 static void loadAnalysis(Parse *pParse, int iDb){
1283 Vdbe *v = sqlite3GetVdbe(pParse);
1284 if( v ){
1285 sqlite3VdbeAddOp1(v, OP_LoadAnalysis, iDb);
1290 ** Generate code that will do an analysis of an entire database
1292 static void analyzeDatabase(Parse *pParse, int iDb){
1293 sqlite3 *db = pParse->db;
1294 Schema *pSchema = db->aDb[iDb].pSchema; /* Schema of database iDb */
1295 HashElem *k;
1296 int iStatCur;
1297 int iMem;
1298 int iTab;
1300 sqlite3BeginWriteOperation(pParse, 0, iDb);
1301 iStatCur = pParse->nTab;
1302 pParse->nTab += 3;
1303 openStatTable(pParse, iDb, iStatCur, 0, 0);
1304 iMem = pParse->nMem+1;
1305 iTab = pParse->nTab;
1306 assert( sqlite3SchemaMutexHeld(db, iDb, 0) );
1307 for(k=sqliteHashFirst(&pSchema->tblHash); k; k=sqliteHashNext(k)){
1308 Table *pTab = (Table*)sqliteHashData(k);
1309 analyzeOneTable(pParse, pTab, 0, iStatCur, iMem, iTab);
1311 loadAnalysis(pParse, iDb);
1315 ** Generate code that will do an analysis of a single table in
1316 ** a database. If pOnlyIdx is not NULL then it is a single index
1317 ** in pTab that should be analyzed.
1319 static void analyzeTable(Parse *pParse, Table *pTab, Index *pOnlyIdx){
1320 int iDb;
1321 int iStatCur;
1323 assert( pTab!=0 );
1324 assert( sqlite3BtreeHoldsAllMutexes(pParse->db) );
1325 iDb = sqlite3SchemaToIndex(pParse->db, pTab->pSchema);
1326 sqlite3BeginWriteOperation(pParse, 0, iDb);
1327 iStatCur = pParse->nTab;
1328 pParse->nTab += 3;
1329 if( pOnlyIdx ){
1330 openStatTable(pParse, iDb, iStatCur, pOnlyIdx->zName, "idx");
1331 }else{
1332 openStatTable(pParse, iDb, iStatCur, pTab->zName, "tbl");
1334 analyzeOneTable(pParse, pTab, pOnlyIdx, iStatCur,pParse->nMem+1,pParse->nTab);
1335 loadAnalysis(pParse, iDb);
1339 ** Generate code for the ANALYZE command. The parser calls this routine
1340 ** when it recognizes an ANALYZE command.
1342 ** ANALYZE -- 1
1343 ** ANALYZE <database> -- 2
1344 ** ANALYZE ?<database>.?<tablename> -- 3
1346 ** Form 1 causes all indices in all attached databases to be analyzed.
1347 ** Form 2 analyzes all indices the single database named.
1348 ** Form 3 analyzes all indices associated with the named table.
1350 void sqlite3Analyze(Parse *pParse, Token *pName1, Token *pName2){
1351 sqlite3 *db = pParse->db;
1352 int iDb;
1353 int i;
1354 char *z, *zDb;
1355 Table *pTab;
1356 Index *pIdx;
1357 Token *pTableName;
1358 Vdbe *v;
1360 /* Read the database schema. If an error occurs, leave an error message
1361 ** and code in pParse and return NULL. */
1362 assert( sqlite3BtreeHoldsAllMutexes(pParse->db) );
1363 if( SQLITE_OK!=sqlite3ReadSchema(pParse) ){
1364 return;
1367 assert( pName2!=0 || pName1==0 );
1368 if( pName1==0 ){
1369 /* Form 1: Analyze everything */
1370 for(i=0; i<db->nDb; i++){
1371 if( i==1 ) continue; /* Do not analyze the TEMP database */
1372 analyzeDatabase(pParse, i);
1374 }else if( pName2->n==0 ){
1375 /* Form 2: Analyze the database or table named */
1376 iDb = sqlite3FindDb(db, pName1);
1377 if( iDb>=0 ){
1378 analyzeDatabase(pParse, iDb);
1379 }else{
1380 z = sqlite3NameFromToken(db, pName1);
1381 if( z ){
1382 if( (pIdx = sqlite3FindIndex(db, z, 0))!=0 ){
1383 analyzeTable(pParse, pIdx->pTable, pIdx);
1384 }else if( (pTab = sqlite3LocateTable(pParse, 0, z, 0))!=0 ){
1385 analyzeTable(pParse, pTab, 0);
1387 sqlite3DbFree(db, z);
1390 }else{
1391 /* Form 3: Analyze the fully qualified table name */
1392 iDb = sqlite3TwoPartName(pParse, pName1, pName2, &pTableName);
1393 if( iDb>=0 ){
1394 zDb = db->aDb[iDb].zName;
1395 z = sqlite3NameFromToken(db, pTableName);
1396 if( z ){
1397 if( (pIdx = sqlite3FindIndex(db, z, zDb))!=0 ){
1398 analyzeTable(pParse, pIdx->pTable, pIdx);
1399 }else if( (pTab = sqlite3LocateTable(pParse, 0, z, zDb))!=0 ){
1400 analyzeTable(pParse, pTab, 0);
1402 sqlite3DbFree(db, z);
1406 v = sqlite3GetVdbe(pParse);
1407 if( v ) sqlite3VdbeAddOp0(v, OP_Expire);
1411 ** Used to pass information from the analyzer reader through to the
1412 ** callback routine.
1414 typedef struct analysisInfo analysisInfo;
1415 struct analysisInfo {
1416 sqlite3 *db;
1417 const char *zDatabase;
1421 ** The first argument points to a nul-terminated string containing a
1422 ** list of space separated integers. Read the first nOut of these into
1423 ** the array aOut[].
1425 static void decodeIntArray(
1426 char *zIntArray, /* String containing int array to decode */
1427 int nOut, /* Number of slots in aOut[] */
1428 tRowcnt *aOut, /* Store integers here */
1429 LogEst *aLog, /* Or, if aOut==0, here */
1430 Index *pIndex /* Handle extra flags for this index, if not NULL */
1432 char *z = zIntArray;
1433 int c;
1434 int i;
1435 tRowcnt v;
1437 #ifdef SQLITE_ENABLE_STAT3_OR_STAT4
1438 if( z==0 ) z = "";
1439 #else
1440 assert( z!=0 );
1441 #endif
1442 for(i=0; *z && i<nOut; i++){
1443 v = 0;
1444 while( (c=z[0])>='0' && c<='9' ){
1445 v = v*10 + c - '0';
1446 z++;
1448 #ifdef SQLITE_ENABLE_STAT3_OR_STAT4
1449 if( aOut ) aOut[i] = v;
1450 if( aLog ) aLog[i] = sqlite3LogEst(v);
1451 #else
1452 assert( aOut==0 );
1453 UNUSED_PARAMETER(aOut);
1454 assert( aLog!=0 );
1455 aLog[i] = sqlite3LogEst(v);
1456 #endif
1457 if( *z==' ' ) z++;
1459 #ifndef SQLITE_ENABLE_STAT3_OR_STAT4
1460 assert( pIndex!=0 );
1461 #else
1462 if( pIndex )
1463 #endif
1464 while( z[0] ){
1465 if( sqlite3_strglob("unordered*", z)==0 ){
1466 pIndex->bUnordered = 1;
1467 }else if( sqlite3_strglob("sz=[0-9]*", z)==0 ){
1468 pIndex->szIdxRow = sqlite3LogEst(sqlite3Atoi(z+3));
1470 #ifdef SQLITE_ENABLE_COSTMULT
1471 else if( sqlite3_strglob("costmult=[0-9]*",z)==0 ){
1472 pIndex->pTable->costMult = sqlite3LogEst(sqlite3Atoi(z+9));
1474 #endif
1475 while( z[0]!=0 && z[0]!=' ' ) z++;
1476 while( z[0]==' ' ) z++;
1481 ** This callback is invoked once for each index when reading the
1482 ** sqlite_stat1 table.
1484 ** argv[0] = name of the table
1485 ** argv[1] = name of the index (might be NULL)
1486 ** argv[2] = results of analysis - on integer for each column
1488 ** Entries for which argv[1]==NULL simply record the number of rows in
1489 ** the table.
1491 static int analysisLoader(void *pData, int argc, char **argv, char **NotUsed){
1492 analysisInfo *pInfo = (analysisInfo*)pData;
1493 Index *pIndex;
1494 Table *pTable;
1495 const char *z;
1497 assert( argc==3 );
1498 UNUSED_PARAMETER2(NotUsed, argc);
1500 if( argv==0 || argv[0]==0 || argv[2]==0 ){
1501 return 0;
1503 pTable = sqlite3FindTable(pInfo->db, argv[0], pInfo->zDatabase);
1504 if( pTable==0 ){
1505 return 0;
1507 if( argv[1]==0 ){
1508 pIndex = 0;
1509 }else if( sqlite3_stricmp(argv[0],argv[1])==0 ){
1510 pIndex = sqlite3PrimaryKeyIndex(pTable);
1511 }else{
1512 pIndex = sqlite3FindIndex(pInfo->db, argv[1], pInfo->zDatabase);
1514 z = argv[2];
1516 if( pIndex ){
1517 int nCol = pIndex->nKeyCol+1;
1518 #ifdef SQLITE_ENABLE_STAT3_OR_STAT4
1519 tRowcnt * const aiRowEst = pIndex->aiRowEst = (tRowcnt*)sqlite3MallocZero(
1520 sizeof(tRowcnt) * nCol
1522 if( aiRowEst==0 ) pInfo->db->mallocFailed = 1;
1523 #else
1524 tRowcnt * const aiRowEst = 0;
1525 #endif
1526 pIndex->bUnordered = 0;
1527 decodeIntArray((char*)z, nCol, aiRowEst, pIndex->aiRowLogEst, pIndex);
1528 if( pIndex->pPartIdxWhere==0 ) pTable->nRowLogEst = pIndex->aiRowLogEst[0];
1529 }else{
1530 Index fakeIdx;
1531 fakeIdx.szIdxRow = pTable->szTabRow;
1532 #ifdef SQLITE_ENABLE_COSTMULT
1533 fakeIdx.pTable = pTable;
1534 #endif
1535 decodeIntArray((char*)z, 1, 0, &pTable->nRowLogEst, &fakeIdx);
1536 pTable->szTabRow = fakeIdx.szIdxRow;
1539 return 0;
1543 ** If the Index.aSample variable is not NULL, delete the aSample[] array
1544 ** and its contents.
1546 void sqlite3DeleteIndexSamples(sqlite3 *db, Index *pIdx){
1547 #ifdef SQLITE_ENABLE_STAT3_OR_STAT4
1548 if( pIdx->aSample ){
1549 int j;
1550 for(j=0; j<pIdx->nSample; j++){
1551 IndexSample *p = &pIdx->aSample[j];
1552 sqlite3DbFree(db, p->p);
1554 sqlite3DbFree(db, pIdx->aSample);
1556 if( db && db->pnBytesFreed==0 ){
1557 pIdx->nSample = 0;
1558 pIdx->aSample = 0;
1560 #else
1561 UNUSED_PARAMETER(db);
1562 UNUSED_PARAMETER(pIdx);
1563 #endif /* SQLITE_ENABLE_STAT3_OR_STAT4 */
1566 #ifdef SQLITE_ENABLE_STAT3_OR_STAT4
1568 ** Populate the pIdx->aAvgEq[] array based on the samples currently
1569 ** stored in pIdx->aSample[].
1571 static void initAvgEq(Index *pIdx){
1572 if( pIdx ){
1573 IndexSample *aSample = pIdx->aSample;
1574 IndexSample *pFinal = &aSample[pIdx->nSample-1];
1575 int iCol;
1576 int nCol = 1;
1577 if( pIdx->nSampleCol>1 ){
1578 /* If this is stat4 data, then calculate aAvgEq[] values for all
1579 ** sample columns except the last. The last is always set to 1, as
1580 ** once the trailing PK fields are considered all index keys are
1581 ** unique. */
1582 nCol = pIdx->nSampleCol-1;
1583 pIdx->aAvgEq[nCol] = 1;
1585 for(iCol=0; iCol<nCol; iCol++){
1586 int nSample = pIdx->nSample;
1587 int i; /* Used to iterate through samples */
1588 tRowcnt sumEq = 0; /* Sum of the nEq values */
1589 tRowcnt avgEq = 0;
1590 tRowcnt nRow; /* Number of rows in index */
1591 i64 nSum100 = 0; /* Number of terms contributing to sumEq */
1592 i64 nDist100; /* Number of distinct values in index */
1594 if( !pIdx->aiRowEst || iCol>=pIdx->nKeyCol || pIdx->aiRowEst[iCol+1]==0 ){
1595 nRow = pFinal->anLt[iCol];
1596 nDist100 = (i64)100 * pFinal->anDLt[iCol];
1597 nSample--;
1598 }else{
1599 nRow = pIdx->aiRowEst[0];
1600 nDist100 = ((i64)100 * pIdx->aiRowEst[0]) / pIdx->aiRowEst[iCol+1];
1603 /* Set nSum to the number of distinct (iCol+1) field prefixes that
1604 ** occur in the stat4 table for this index. Set sumEq to the sum of
1605 ** the nEq values for column iCol for the same set (adding the value
1606 ** only once where there exist duplicate prefixes). */
1607 for(i=0; i<nSample; i++){
1608 if( i==(pIdx->nSample-1)
1609 || aSample[i].anDLt[iCol]!=aSample[i+1].anDLt[iCol]
1611 sumEq += aSample[i].anEq[iCol];
1612 nSum100 += 100;
1616 if( nDist100>nSum100 ){
1617 avgEq = ((i64)100 * (nRow - sumEq))/(nDist100 - nSum100);
1619 if( avgEq==0 ) avgEq = 1;
1620 pIdx->aAvgEq[iCol] = avgEq;
1626 ** Look up an index by name. Or, if the name of a WITHOUT ROWID table
1627 ** is supplied instead, find the PRIMARY KEY index for that table.
1629 static Index *findIndexOrPrimaryKey(
1630 sqlite3 *db,
1631 const char *zName,
1632 const char *zDb
1634 Index *pIdx = sqlite3FindIndex(db, zName, zDb);
1635 if( pIdx==0 ){
1636 Table *pTab = sqlite3FindTable(db, zName, zDb);
1637 if( pTab && !HasRowid(pTab) ) pIdx = sqlite3PrimaryKeyIndex(pTab);
1639 return pIdx;
1643 ** Load the content from either the sqlite_stat4 or sqlite_stat3 table
1644 ** into the relevant Index.aSample[] arrays.
1646 ** Arguments zSql1 and zSql2 must point to SQL statements that return
1647 ** data equivalent to the following (statements are different for stat3,
1648 ** see the caller of this function for details):
1650 ** zSql1: SELECT idx,count(*) FROM %Q.sqlite_stat4 GROUP BY idx
1651 ** zSql2: SELECT idx,neq,nlt,ndlt,sample FROM %Q.sqlite_stat4
1653 ** where %Q is replaced with the database name before the SQL is executed.
1655 static int loadStatTbl(
1656 sqlite3 *db, /* Database handle */
1657 int bStat3, /* Assume single column records only */
1658 const char *zSql1, /* SQL statement 1 (see above) */
1659 const char *zSql2, /* SQL statement 2 (see above) */
1660 const char *zDb /* Database name (e.g. "main") */
1662 int rc; /* Result codes from subroutines */
1663 sqlite3_stmt *pStmt = 0; /* An SQL statement being run */
1664 char *zSql; /* Text of the SQL statement */
1665 Index *pPrevIdx = 0; /* Previous index in the loop */
1666 IndexSample *pSample; /* A slot in pIdx->aSample[] */
1668 assert( db->lookaside.bEnabled==0 );
1669 zSql = sqlite3MPrintf(db, zSql1, zDb);
1670 if( !zSql ){
1671 return SQLITE_NOMEM;
1673 rc = sqlite3_prepare(db, zSql, -1, &pStmt, 0);
1674 sqlite3DbFree(db, zSql);
1675 if( rc ) return rc;
1677 while( sqlite3_step(pStmt)==SQLITE_ROW ){
1678 int nIdxCol = 1; /* Number of columns in stat4 records */
1680 char *zIndex; /* Index name */
1681 Index *pIdx; /* Pointer to the index object */
1682 int nSample; /* Number of samples */
1683 int nByte; /* Bytes of space required */
1684 int i; /* Bytes of space required */
1685 tRowcnt *pSpace;
1687 zIndex = (char *)sqlite3_column_text(pStmt, 0);
1688 if( zIndex==0 ) continue;
1689 nSample = sqlite3_column_int(pStmt, 1);
1690 pIdx = findIndexOrPrimaryKey(db, zIndex, zDb);
1691 assert( pIdx==0 || bStat3 || pIdx->nSample==0 );
1692 /* Index.nSample is non-zero at this point if data has already been
1693 ** loaded from the stat4 table. In this case ignore stat3 data. */
1694 if( pIdx==0 || pIdx->nSample ) continue;
1695 if( bStat3==0 ){
1696 assert( !HasRowid(pIdx->pTable) || pIdx->nColumn==pIdx->nKeyCol+1 );
1697 if( !HasRowid(pIdx->pTable) && IsPrimaryKeyIndex(pIdx) ){
1698 nIdxCol = pIdx->nKeyCol;
1699 }else{
1700 nIdxCol = pIdx->nColumn;
1703 pIdx->nSampleCol = nIdxCol;
1704 nByte = sizeof(IndexSample) * nSample;
1705 nByte += sizeof(tRowcnt) * nIdxCol * 3 * nSample;
1706 nByte += nIdxCol * sizeof(tRowcnt); /* Space for Index.aAvgEq[] */
1708 pIdx->aSample = sqlite3DbMallocZero(db, nByte);
1709 if( pIdx->aSample==0 ){
1710 sqlite3_finalize(pStmt);
1711 return SQLITE_NOMEM;
1713 pSpace = (tRowcnt*)&pIdx->aSample[nSample];
1714 pIdx->aAvgEq = pSpace; pSpace += nIdxCol;
1715 for(i=0; i<nSample; i++){
1716 pIdx->aSample[i].anEq = pSpace; pSpace += nIdxCol;
1717 pIdx->aSample[i].anLt = pSpace; pSpace += nIdxCol;
1718 pIdx->aSample[i].anDLt = pSpace; pSpace += nIdxCol;
1720 assert( ((u8*)pSpace)-nByte==(u8*)(pIdx->aSample) );
1722 rc = sqlite3_finalize(pStmt);
1723 if( rc ) return rc;
1725 zSql = sqlite3MPrintf(db, zSql2, zDb);
1726 if( !zSql ){
1727 return SQLITE_NOMEM;
1729 rc = sqlite3_prepare(db, zSql, -1, &pStmt, 0);
1730 sqlite3DbFree(db, zSql);
1731 if( rc ) return rc;
1733 while( sqlite3_step(pStmt)==SQLITE_ROW ){
1734 char *zIndex; /* Index name */
1735 Index *pIdx; /* Pointer to the index object */
1736 int nCol = 1; /* Number of columns in index */
1738 zIndex = (char *)sqlite3_column_text(pStmt, 0);
1739 if( zIndex==0 ) continue;
1740 pIdx = findIndexOrPrimaryKey(db, zIndex, zDb);
1741 if( pIdx==0 ) continue;
1742 /* This next condition is true if data has already been loaded from
1743 ** the sqlite_stat4 table. In this case ignore stat3 data. */
1744 nCol = pIdx->nSampleCol;
1745 if( bStat3 && nCol>1 ) continue;
1746 if( pIdx!=pPrevIdx ){
1747 initAvgEq(pPrevIdx);
1748 pPrevIdx = pIdx;
1750 pSample = &pIdx->aSample[pIdx->nSample];
1751 decodeIntArray((char*)sqlite3_column_text(pStmt,1),nCol,pSample->anEq,0,0);
1752 decodeIntArray((char*)sqlite3_column_text(pStmt,2),nCol,pSample->anLt,0,0);
1753 decodeIntArray((char*)sqlite3_column_text(pStmt,3),nCol,pSample->anDLt,0,0);
1755 /* Take a copy of the sample. Add two 0x00 bytes the end of the buffer.
1756 ** This is in case the sample record is corrupted. In that case, the
1757 ** sqlite3VdbeRecordCompare() may read up to two varints past the
1758 ** end of the allocated buffer before it realizes it is dealing with
1759 ** a corrupt record. Adding the two 0x00 bytes prevents this from causing
1760 ** a buffer overread. */
1761 pSample->n = sqlite3_column_bytes(pStmt, 4);
1762 pSample->p = sqlite3DbMallocZero(db, pSample->n + 2);
1763 if( pSample->p==0 ){
1764 sqlite3_finalize(pStmt);
1765 return SQLITE_NOMEM;
1767 memcpy(pSample->p, sqlite3_column_blob(pStmt, 4), pSample->n);
1768 pIdx->nSample++;
1770 rc = sqlite3_finalize(pStmt);
1771 if( rc==SQLITE_OK ) initAvgEq(pPrevIdx);
1772 return rc;
1776 ** Load content from the sqlite_stat4 and sqlite_stat3 tables into
1777 ** the Index.aSample[] arrays of all indices.
1779 static int loadStat4(sqlite3 *db, const char *zDb){
1780 int rc = SQLITE_OK; /* Result codes from subroutines */
1782 assert( db->lookaside.bEnabled==0 );
1783 if( sqlite3FindTable(db, "sqlite_stat4", zDb) ){
1784 rc = loadStatTbl(db, 0,
1785 "SELECT idx,count(*) FROM %Q.sqlite_stat4 GROUP BY idx",
1786 "SELECT idx,neq,nlt,ndlt,sample FROM %Q.sqlite_stat4",
1791 if( rc==SQLITE_OK && sqlite3FindTable(db, "sqlite_stat3", zDb) ){
1792 rc = loadStatTbl(db, 1,
1793 "SELECT idx,count(*) FROM %Q.sqlite_stat3 GROUP BY idx",
1794 "SELECT idx,neq,nlt,ndlt,sqlite_record(sample) FROM %Q.sqlite_stat3",
1799 return rc;
1801 #endif /* SQLITE_ENABLE_STAT3_OR_STAT4 */
1804 ** Load the content of the sqlite_stat1 and sqlite_stat3/4 tables. The
1805 ** contents of sqlite_stat1 are used to populate the Index.aiRowEst[]
1806 ** arrays. The contents of sqlite_stat3/4 are used to populate the
1807 ** Index.aSample[] arrays.
1809 ** If the sqlite_stat1 table is not present in the database, SQLITE_ERROR
1810 ** is returned. In this case, even if SQLITE_ENABLE_STAT3/4 was defined
1811 ** during compilation and the sqlite_stat3/4 table is present, no data is
1812 ** read from it.
1814 ** If SQLITE_ENABLE_STAT3/4 was defined during compilation and the
1815 ** sqlite_stat4 table is not present in the database, SQLITE_ERROR is
1816 ** returned. However, in this case, data is read from the sqlite_stat1
1817 ** table (if it is present) before returning.
1819 ** If an OOM error occurs, this function always sets db->mallocFailed.
1820 ** This means if the caller does not care about other errors, the return
1821 ** code may be ignored.
1823 int sqlite3AnalysisLoad(sqlite3 *db, int iDb){
1824 analysisInfo sInfo;
1825 HashElem *i;
1826 char *zSql;
1827 int rc;
1829 assert( iDb>=0 && iDb<db->nDb );
1830 assert( db->aDb[iDb].pBt!=0 );
1832 /* Clear any prior statistics */
1833 assert( sqlite3SchemaMutexHeld(db, iDb, 0) );
1834 for(i=sqliteHashFirst(&db->aDb[iDb].pSchema->idxHash);i;i=sqliteHashNext(i)){
1835 Index *pIdx = sqliteHashData(i);
1836 sqlite3DefaultRowEst(pIdx);
1837 #ifdef SQLITE_ENABLE_STAT3_OR_STAT4
1838 sqlite3DeleteIndexSamples(db, pIdx);
1839 pIdx->aSample = 0;
1840 #endif
1843 /* Check to make sure the sqlite_stat1 table exists */
1844 sInfo.db = db;
1845 sInfo.zDatabase = db->aDb[iDb].zName;
1846 if( sqlite3FindTable(db, "sqlite_stat1", sInfo.zDatabase)==0 ){
1847 return SQLITE_ERROR;
1850 /* Load new statistics out of the sqlite_stat1 table */
1851 zSql = sqlite3MPrintf(db,
1852 "SELECT tbl,idx,stat FROM %Q.sqlite_stat1", sInfo.zDatabase);
1853 if( zSql==0 ){
1854 rc = SQLITE_NOMEM;
1855 }else{
1856 rc = sqlite3_exec(db, zSql, analysisLoader, &sInfo, 0);
1857 sqlite3DbFree(db, zSql);
1861 /* Load the statistics from the sqlite_stat4 table. */
1862 #ifdef SQLITE_ENABLE_STAT3_OR_STAT4
1863 if( rc==SQLITE_OK ){
1864 int lookasideEnabled = db->lookaside.bEnabled;
1865 db->lookaside.bEnabled = 0;
1866 rc = loadStat4(db, sInfo.zDatabase);
1867 db->lookaside.bEnabled = lookasideEnabled;
1869 for(i=sqliteHashFirst(&db->aDb[iDb].pSchema->idxHash);i;i=sqliteHashNext(i)){
1870 Index *pIdx = sqliteHashData(i);
1871 sqlite3_free(pIdx->aiRowEst);
1872 pIdx->aiRowEst = 0;
1874 #endif
1876 if( rc==SQLITE_NOMEM ){
1877 db->mallocFailed = 1;
1879 return rc;
1883 #endif /* SQLITE_OMIT_ANALYZE */