monotone

monotone Mtn Source Tree

Root/sqlite/analyze.c

1/*
2** 2005 July 8
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** @(#) $Id: analyze.c,v 1.18 2007/05/12 12:08:51 drh Exp $
15*/
16#ifndef SQLITE_OMIT_ANALYZE
17#include "sqliteInt.h"
18
19/*
20** This routine generates code that opens the sqlite_stat1 table on cursor
21** iStatCur.
22**
23** If the sqlite_stat1 tables does not previously exist, it is created.
24** If it does previously exist, all entires associated with table zWhere
25** are removed. If zWhere==0 then all entries are removed.
26*/
27static void openStatTable(
28 Parse *pParse, /* Parsing context */
29 int iDb, /* The database we are looking in */
30 int iStatCur, /* Open the sqlite_stat1 table on this cursor */
31 const char *zWhere /* Delete entries associated with this table */
32){
33 sqlite3 *db = pParse->db;
34 Db *pDb;
35 int iRootPage;
36 Table *pStat;
37 Vdbe *v = sqlite3GetVdbe(pParse);
38
39 if( v==0 ) return;
40 pDb = &db->aDb[iDb];
41 if( (pStat = sqlite3FindTable(db, "sqlite_stat1", pDb->zName))==0 ){
42 /* The sqlite_stat1 tables does not exist. Create it.
43 ** Note that a side-effect of the CREATE TABLE statement is to leave
44 ** the rootpage of the new table on the top of the stack. This is
45 ** important because the OpenWrite opcode below will be needing it. */
46 sqlite3NestedParse(pParse,
47 "CREATE TABLE %Q.sqlite_stat1(tbl,idx,stat)",
48 pDb->zName
49 );
50 iRootPage = 0; /* Cause rootpage to be taken from top of stack */
51 }else if( zWhere ){
52 /* The sqlite_stat1 table exists. Delete all entries associated with
53 ** the table zWhere. */
54 sqlite3NestedParse(pParse,
55 "DELETE FROM %Q.sqlite_stat1 WHERE tbl=%Q",
56 pDb->zName, zWhere
57 );
58 iRootPage = pStat->tnum;
59 }else{
60 /* The sqlite_stat1 table already exists. Delete all rows. */
61 iRootPage = pStat->tnum;
62 sqlite3VdbeAddOp(v, OP_Clear, pStat->tnum, iDb);
63 }
64
65 /* Open the sqlite_stat1 table for writing. Unless it was created
66 ** by this vdbe program, lock it for writing at the shared-cache level.
67 ** If this vdbe did create the sqlite_stat1 table, then it must have
68 ** already obtained a schema-lock, making the write-lock redundant.
69 */
70 if( iRootPage>0 ){
71 sqlite3TableLock(pParse, iDb, iRootPage, 1, "sqlite_stat1");
72 }
73 sqlite3VdbeAddOp(v, OP_Integer, iDb, 0);
74 sqlite3VdbeAddOp(v, OP_OpenWrite, iStatCur, iRootPage);
75 sqlite3VdbeAddOp(v, OP_SetNumColumns, iStatCur, 3);
76}
77
78/*
79** Generate code to do an analysis of all indices associated with
80** a single table.
81*/
82static void analyzeOneTable(
83 Parse *pParse, /* Parser context */
84 Table *pTab, /* Table whose indices are to be analyzed */
85 int iStatCur, /* Cursor that writes to the sqlite_stat1 table */
86 int iMem /* Available memory locations begin here */
87){
88 Index *pIdx; /* An index to being analyzed */
89 int iIdxCur; /* Cursor number for index being analyzed */
90 int nCol; /* Number of columns in the index */
91 Vdbe *v; /* The virtual machine being built up */
92 int i; /* Loop counter */
93 int topOfLoop; /* The top of the loop */
94 int endOfLoop; /* The end of the loop */
95 int addr; /* The address of an instruction */
96 int iDb; /* Index of database containing pTab */
97
98 v = sqlite3GetVdbe(pParse);
99 if( v==0 || pTab==0 || pTab->pIndex==0 ){
100 /* Do no analysis for tables that have no indices */
101 return;
102 }
103
104 iDb = sqlite3SchemaToIndex(pParse->db, pTab->pSchema);
105 assert( iDb>=0 );
106#ifndef SQLITE_OMIT_AUTHORIZATION
107 if( sqlite3AuthCheck(pParse, SQLITE_ANALYZE, pTab->zName, 0,
108 pParse->db->aDb[iDb].zName ) ){
109 return;
110 }
111#endif
112
113 /* Establish a read-lock on the table at the shared-cache level. */
114 sqlite3TableLock(pParse, iDb, pTab->tnum, 0, pTab->zName);
115
116 iIdxCur = pParse->nTab;
117 for(pIdx=pTab->pIndex; pIdx; pIdx=pIdx->pNext){
118 KeyInfo *pKey = sqlite3IndexKeyinfo(pParse, pIdx);
119
120 /* Open a cursor to the index to be analyzed
121 */
122 assert( iDb==sqlite3SchemaToIndex(pParse->db, pIdx->pSchema) );
123 sqlite3VdbeAddOp(v, OP_Integer, iDb, 0);
124 VdbeComment((v, "# %s", pIdx->zName));
125 sqlite3VdbeOp3(v, OP_OpenRead, iIdxCur, pIdx->tnum,
126 (char *)pKey, P3_KEYINFO_HANDOFF);
127 nCol = pIdx->nColumn;
128 if( iMem+nCol*2>=pParse->nMem ){
129 pParse->nMem = iMem+nCol*2+1;
130 }
131 sqlite3VdbeAddOp(v, OP_SetNumColumns, iIdxCur, nCol+1);
132
133 /* Memory cells are used as follows:
134 **
135 ** mem[iMem]: The total number of rows in the table.
136 ** mem[iMem+1]: Number of distinct values in column 1
137 ** ...
138 ** mem[iMem+nCol]: Number of distinct values in column N
139 ** mem[iMem+nCol+1] Last observed value of column 1
140 ** ...
141 ** mem[iMem+nCol+nCol]: Last observed value of column N
142 **
143 ** Cells iMem through iMem+nCol are initialized to 0. The others
144 ** are initialized to NULL.
145 */
146 for(i=0; i<=nCol; i++){
147 sqlite3VdbeAddOp(v, OP_MemInt, 0, iMem+i);
148 }
149 for(i=0; i<nCol; i++){
150 sqlite3VdbeAddOp(v, OP_MemNull, iMem+nCol+i+1, 0);
151 }
152
153 /* Do the analysis.
154 */
155 endOfLoop = sqlite3VdbeMakeLabel(v);
156 sqlite3VdbeAddOp(v, OP_Rewind, iIdxCur, endOfLoop);
157 topOfLoop = sqlite3VdbeCurrentAddr(v);
158 sqlite3VdbeAddOp(v, OP_MemIncr, 1, iMem);
159 for(i=0; i<nCol; i++){
160 sqlite3VdbeAddOp(v, OP_Column, iIdxCur, i);
161 sqlite3VdbeAddOp(v, OP_MemLoad, iMem+nCol+i+1, 0);
162 sqlite3VdbeAddOp(v, OP_Ne, 0x100, 0);
163 }
164 sqlite3VdbeAddOp(v, OP_Goto, 0, endOfLoop);
165 for(i=0; i<nCol; i++){
166 addr = sqlite3VdbeAddOp(v, OP_MemIncr, 1, iMem+i+1);
167 sqlite3VdbeChangeP2(v, topOfLoop + 3*i + 3, addr);
168 sqlite3VdbeAddOp(v, OP_Column, iIdxCur, i);
169 sqlite3VdbeAddOp(v, OP_MemStore, iMem+nCol+i+1, 1);
170 }
171 sqlite3VdbeResolveLabel(v, endOfLoop);
172 sqlite3VdbeAddOp(v, OP_Next, iIdxCur, topOfLoop);
173 sqlite3VdbeAddOp(v, OP_Close, iIdxCur, 0);
174
175 /* Store the results.
176 **
177 ** The result is a single row of the sqlite_stmt1 table. The first
178 ** two columns are the names of the table and index. The third column
179 ** is a string composed of a list of integer statistics about the
180 ** index. The first integer in the list is the total number of entires
181 ** in the index. There is one additional integer in the list for each
182 ** column of the table. This additional integer is a guess of how many
183 ** rows of the table the index will select. If D is the count of distinct
184 ** values and K is the total number of rows, then the integer is computed
185 ** as:
186 **
187 ** I = (K+D-1)/D
188 **
189 ** If K==0 then no entry is made into the sqlite_stat1 table.
190 ** If K>0 then it is always the case the D>0 so division by zero
191 ** is never possible.
192 */
193 sqlite3VdbeAddOp(v, OP_MemLoad, iMem, 0);
194 addr = sqlite3VdbeAddOp(v, OP_IfNot, 0, 0);
195 sqlite3VdbeAddOp(v, OP_NewRowid, iStatCur, 0);
196 sqlite3VdbeOp3(v, OP_String8, 0, 0, pTab->zName, 0);
197 sqlite3VdbeOp3(v, OP_String8, 0, 0, pIdx->zName, 0);
198 sqlite3VdbeAddOp(v, OP_MemLoad, iMem, 0);
199 sqlite3VdbeOp3(v, OP_String8, 0, 0, " ", 0);
200 for(i=0; i<nCol; i++){
201 sqlite3VdbeAddOp(v, OP_MemLoad, iMem, 0);
202 sqlite3VdbeAddOp(v, OP_MemLoad, iMem+i+1, 0);
203 sqlite3VdbeAddOp(v, OP_Add, 0, 0);
204 sqlite3VdbeAddOp(v, OP_AddImm, -1, 0);
205 sqlite3VdbeAddOp(v, OP_MemLoad, iMem+i+1, 0);
206 sqlite3VdbeAddOp(v, OP_Divide, 0, 0);
207 sqlite3VdbeAddOp(v, OP_ToInt, 0, 0);
208 if( i==nCol-1 ){
209 sqlite3VdbeAddOp(v, OP_Concat, nCol*2-1, 0);
210 }else{
211 sqlite3VdbeAddOp(v, OP_Dup, 1, 0);
212 }
213 }
214 sqlite3VdbeOp3(v, OP_MakeRecord, 3, 0, "aaa", 0);
215 sqlite3VdbeAddOp(v, OP_Insert, iStatCur, OPFLAG_APPEND);
216 sqlite3VdbeJumpHere(v, addr);
217 }
218}
219
220/*
221** Generate code that will cause the most recent index analysis to
222** be laoded into internal hash tables where is can be used.
223*/
224static void loadAnalysis(Parse *pParse, int iDb){
225 Vdbe *v = sqlite3GetVdbe(pParse);
226 if( v ){
227 sqlite3VdbeAddOp(v, OP_LoadAnalysis, iDb, 0);
228 }
229}
230
231/*
232** Generate code that will do an analysis of an entire database
233*/
234static void analyzeDatabase(Parse *pParse, int iDb){
235 sqlite3 *db = pParse->db;
236 Schema *pSchema = db->aDb[iDb].pSchema; /* Schema of database iDb */
237 HashElem *k;
238 int iStatCur;
239 int iMem;
240
241 sqlite3BeginWriteOperation(pParse, 0, iDb);
242 iStatCur = pParse->nTab++;
243 openStatTable(pParse, iDb, iStatCur, 0);
244 iMem = pParse->nMem;
245 for(k=sqliteHashFirst(&pSchema->tblHash); k; k=sqliteHashNext(k)){
246 Table *pTab = (Table*)sqliteHashData(k);
247 analyzeOneTable(pParse, pTab, iStatCur, iMem);
248 }
249 loadAnalysis(pParse, iDb);
250}
251
252/*
253** Generate code that will do an analysis of a single table in
254** a database.
255*/
256static void analyzeTable(Parse *pParse, Table *pTab){
257 int iDb;
258 int iStatCur;
259
260 assert( pTab!=0 );
261 iDb = sqlite3SchemaToIndex(pParse->db, pTab->pSchema);
262 sqlite3BeginWriteOperation(pParse, 0, iDb);
263 iStatCur = pParse->nTab++;
264 openStatTable(pParse, iDb, iStatCur, pTab->zName);
265 analyzeOneTable(pParse, pTab, iStatCur, pParse->nMem);
266 loadAnalysis(pParse, iDb);
267}
268
269/*
270** Generate code for the ANALYZE command. The parser calls this routine
271** when it recognizes an ANALYZE command.
272**
273** ANALYZE -- 1
274** ANALYZE <database> -- 2
275** ANALYZE ?<database>.?<tablename> -- 3
276**
277** Form 1 causes all indices in all attached databases to be analyzed.
278** Form 2 analyzes all indices the single database named.
279** Form 3 analyzes all indices associated with the named table.
280*/
281void sqlite3Analyze(Parse *pParse, Token *pName1, Token *pName2){
282 sqlite3 *db = pParse->db;
283 int iDb;
284 int i;
285 char *z, *zDb;
286 Table *pTab;
287 Token *pTableName;
288
289 /* Read the database schema. If an error occurs, leave an error message
290 ** and code in pParse and return NULL. */
291 if( SQLITE_OK!=sqlite3ReadSchema(pParse) ){
292 return;
293 }
294
295 if( pName1==0 ){
296 /* Form 1: Analyze everything */
297 for(i=0; i<db->nDb; i++){
298 if( i==1 ) continue; /* Do not analyze the TEMP database */
299 analyzeDatabase(pParse, i);
300 }
301 }else if( pName2==0 || pName2->n==0 ){
302 /* Form 2: Analyze the database or table named */
303 iDb = sqlite3FindDb(db, pName1);
304 if( iDb>=0 ){
305 analyzeDatabase(pParse, iDb);
306 }else{
307 z = sqlite3NameFromToken(pName1);
308 pTab = sqlite3LocateTable(pParse, z, 0);
309 sqliteFree(z);
310 if( pTab ){
311 analyzeTable(pParse, pTab);
312 }
313 }
314 }else{
315 /* Form 3: Analyze the fully qualified table name */
316 iDb = sqlite3TwoPartName(pParse, pName1, pName2, &pTableName);
317 if( iDb>=0 ){
318 zDb = db->aDb[iDb].zName;
319 z = sqlite3NameFromToken(pTableName);
320 if( z ){
321 pTab = sqlite3LocateTable(pParse, z, zDb);
322 sqliteFree(z);
323 if( pTab ){
324 analyzeTable(pParse, pTab);
325 }
326 }
327 }
328 }
329}
330
331/*
332** Used to pass information from the analyzer reader through to the
333** callback routine.
334*/
335typedef struct analysisInfo analysisInfo;
336struct analysisInfo {
337 sqlite3 *db;
338 const char *zDatabase;
339};
340
341/*
342** This callback is invoked once for each index when reading the
343** sqlite_stat1 table.
344**
345** argv[0] = name of the index
346** argv[1] = results of analysis - on integer for each column
347*/
348static int analysisLoader(void *pData, int argc, char **argv, char **azNotUsed){
349 analysisInfo *pInfo = (analysisInfo*)pData;
350 Index *pIndex;
351 int i, c;
352 unsigned int v;
353 const char *z;
354
355 assert( argc==2 );
356 if( argv==0 || argv[0]==0 || argv[1]==0 ){
357 return 0;
358 }
359 pIndex = sqlite3FindIndex(pInfo->db, argv[0], pInfo->zDatabase);
360 if( pIndex==0 ){
361 return 0;
362 }
363 z = argv[1];
364 for(i=0; *z && i<=pIndex->nColumn; i++){
365 v = 0;
366 while( (c=z[0])>='0' && c<='9' ){
367 v = v*10 + c - '0';
368 z++;
369 }
370 pIndex->aiRowEst[i] = v;
371 if( *z==' ' ) z++;
372 }
373 return 0;
374}
375
376/*
377** Load the content of the sqlite_stat1 table into the index hash tables.
378*/
379int sqlite3AnalysisLoad(sqlite3 *db, int iDb){
380 analysisInfo sInfo;
381 HashElem *i;
382 char *zSql;
383 int rc;
384
385 /* Clear any prior statistics */
386 for(i=sqliteHashFirst(&db->aDb[iDb].pSchema->idxHash);i;i=sqliteHashNext(i)){
387 Index *pIdx = sqliteHashData(i);
388 sqlite3DefaultRowEst(pIdx);
389 }
390
391 /* Check to make sure the sqlite_stat1 table existss */
392 sInfo.db = db;
393 sInfo.zDatabase = db->aDb[iDb].zName;
394 if( sqlite3FindTable(db, "sqlite_stat1", sInfo.zDatabase)==0 ){
395 return SQLITE_ERROR;
396 }
397
398
399 /* Load new statistics out of the sqlite_stat1 table */
400 zSql = sqlite3MPrintf("SELECT idx, stat FROM %Q.sqlite_stat1",
401 sInfo.zDatabase);
402 sqlite3SafetyOff(db);
403 rc = sqlite3_exec(db, zSql, analysisLoader, &sInfo, 0);
404 sqlite3SafetyOn(db);
405 sqliteFree(zSql);
406 return rc;
407}
408
409
410#endif /* SQLITE_OMIT_ANALYZE */

Archive Download this file

Branches

Tags

Quick Links:     www.monotone.ca    -     Downloads    -     Documentation    -     Wiki    -     Code Forge    -     Build Status