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