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