Back to index

lightning-sunbird  0.9+nobinonly
analyze.c
Go to the documentation of this file.
00001 /*
00002 ** 2005 July 8
00003 **
00004 ** The author disclaims copyright to this source code.  In place of
00005 ** a legal notice, here is a blessing:
00006 **
00007 **    May you do good and not evil.
00008 **    May you find forgiveness for yourself and forgive others.
00009 **    May you share freely, never taking more than you give.
00010 **
00011 *************************************************************************
00012 ** This file contains code associated with the ANALYZE command.
00013 **
00014 ** @(#) $Id: analyze.c,v 1.1.2.4 2006/05/22 19:12:32 brettw%gmail.com Exp $
00015 */
00016 #ifndef SQLITE_OMIT_ANALYZE
00017 #include "sqliteInt.h"
00018 
00019 /*
00020 ** This routine generates code that opens the sqlite_stat1 table on cursor
00021 ** iStatCur.
00022 **
00023 ** If the sqlite_stat1 tables does not previously exist, it is created.
00024 ** If it does previously exist, all entires associated with table zWhere
00025 ** are removed.  If zWhere==0 then all entries are removed.
00026 */
00027 static void openStatTable(
00028   Parse *pParse,          /* Parsing context */
00029   int iDb,                /* The database we are looking in */
00030   int iStatCur,           /* Open the sqlite_stat1 table on this cursor */
00031   const char *zWhere      /* Delete entries associated with this table */
00032 ){
00033   sqlite3 *db = pParse->db;
00034   Db *pDb;
00035   int iRootPage;
00036   Table *pStat;
00037   Vdbe *v = sqlite3GetVdbe(pParse);
00038 
00039   pDb = &db->aDb[iDb];
00040   if( (pStat = sqlite3FindTable(db, "sqlite_stat1", pDb->zName))==0 ){
00041     /* The sqlite_stat1 tables does not exist.  Create it.  
00042     ** Note that a side-effect of the CREATE TABLE statement is to leave
00043     ** the rootpage of the new table on the top of the stack.  This is
00044     ** important because the OpenWrite opcode below will be needing it. */
00045     sqlite3NestedParse(pParse,
00046       "CREATE TABLE %Q.sqlite_stat1(tbl,idx,stat)",
00047       pDb->zName
00048     );
00049     iRootPage = 0;  /* Cause rootpage to be taken from top of stack */
00050   }else if( zWhere ){
00051     /* The sqlite_stat1 table exists.  Delete all entries associated with
00052     ** the table zWhere. */
00053     sqlite3NestedParse(pParse,
00054        "DELETE FROM %Q.sqlite_stat1 WHERE tbl=%Q",
00055        pDb->zName, zWhere
00056     );
00057     iRootPage = pStat->tnum;
00058   }else{
00059     /* The sqlite_stat1 table already exists.  Delete all rows. */
00060     iRootPage = pStat->tnum;
00061     sqlite3VdbeAddOp(v, OP_Clear, pStat->tnum, iDb);
00062   }
00063 
00064   /* Open the sqlite_stat1 table for writing. Unless it was created
00065   ** by this vdbe program, lock it for writing at the shared-cache level. 
00066   ** If this vdbe did create the sqlite_stat1 table, then it must have 
00067   ** already obtained a schema-lock, making the write-lock redundant.
00068   */
00069   if( iRootPage>0 ){
00070     sqlite3TableLock(pParse, iDb, iRootPage, 1, "sqlite_stat1");
00071   }
00072   sqlite3VdbeAddOp(v, OP_Integer, iDb, 0);
00073   sqlite3VdbeAddOp(v, OP_OpenWrite, iStatCur, iRootPage);
00074   sqlite3VdbeAddOp(v, OP_SetNumColumns, iStatCur, 3);
00075 }
00076 
00077 /*
00078 ** Generate code to do an analysis of all indices associated with
00079 ** a single table.
00080 */
00081 static void analyzeOneTable(
00082   Parse *pParse,   /* Parser context */
00083   Table *pTab,     /* Table whose indices are to be analyzed */
00084   int iStatCur,    /* Cursor that writes to the sqlite_stat1 table */
00085   int iMem         /* Available memory locations begin here */
00086 ){
00087   Index *pIdx;     /* An index to being analyzed */
00088   int iIdxCur;     /* Cursor number for index being analyzed */
00089   int nCol;        /* Number of columns in the index */
00090   Vdbe *v;         /* The virtual machine being built up */
00091   int i;           /* Loop counter */
00092   int topOfLoop;   /* The top of the loop */
00093   int endOfLoop;   /* The end of the loop */
00094   int addr;        /* The address of an instruction */
00095   int iDb;         /* Index of database containing pTab */
00096 
00097   v = sqlite3GetVdbe(pParse);
00098   if( pTab==0 || pTab->pIndex==0 ){
00099     /* Do no analysis for tables that have no indices */
00100     return;
00101   }
00102 
00103   iDb = sqlite3SchemaToIndex(pParse->db, pTab->pSchema);
00104   assert( iDb>=0 );
00105 #ifndef SQLITE_OMIT_AUTHORIZATION
00106   if( sqlite3AuthCheck(pParse, SQLITE_ANALYZE, pTab->zName, 0,
00107       pParse->db->aDb[iDb].zName ) ){
00108     return;
00109   }
00110 #endif
00111 
00112   /* Establish a read-lock on the table at the shared-cache level. */
00113   sqlite3TableLock(pParse, iDb, pTab->tnum, 0, pTab->zName);
00114 
00115   iIdxCur = pParse->nTab;
00116   for(pIdx=pTab->pIndex; pIdx; pIdx=pIdx->pNext){
00117     KeyInfo *pKey = sqlite3IndexKeyinfo(pParse, pIdx);
00118 
00119     /* Open a cursor to the index to be analyzed
00120     */
00121     assert( iDb==sqlite3SchemaToIndex(pParse->db, pIdx->pSchema) );
00122     sqlite3VdbeAddOp(v, OP_Integer, iDb, 0);
00123     VdbeComment((v, "# %s", pIdx->zName));
00124     sqlite3VdbeOp3(v, OP_OpenRead, iIdxCur, pIdx->tnum,
00125         (char *)pKey, P3_KEYINFO_HANDOFF);
00126     nCol = pIdx->nColumn;
00127     if( iMem+nCol*2>=pParse->nMem ){
00128       pParse->nMem = iMem+nCol*2+1;
00129     }
00130     sqlite3VdbeAddOp(v, OP_SetNumColumns, iIdxCur, nCol+1);
00131 
00132     /* Memory cells are used as follows:
00133     **
00134     **    mem[iMem]:             The total number of rows in the table.
00135     **    mem[iMem+1]:           Number of distinct values in column 1
00136     **    ...
00137     **    mem[iMem+nCol]:        Number of distinct values in column N
00138     **    mem[iMem+nCol+1]       Last observed value of column 1
00139     **    ...
00140     **    mem[iMem+nCol+nCol]:   Last observed value of column N
00141     **
00142     ** Cells iMem through iMem+nCol are initialized to 0.  The others
00143     ** are initialized to NULL.
00144     */
00145     for(i=0; i<=nCol; i++){
00146       sqlite3VdbeAddOp(v, OP_MemInt, 0, iMem+i);
00147     }
00148     for(i=0; i<nCol; i++){
00149       sqlite3VdbeAddOp(v, OP_MemNull, iMem+nCol+i+1, 0);
00150     }
00151 
00152     /* Do the analysis.
00153     */
00154     endOfLoop = sqlite3VdbeMakeLabel(v);
00155     sqlite3VdbeAddOp(v, OP_Rewind, iIdxCur, endOfLoop);
00156     topOfLoop = sqlite3VdbeCurrentAddr(v);
00157     sqlite3VdbeAddOp(v, OP_MemIncr, 1, iMem);
00158     for(i=0; i<nCol; i++){
00159       sqlite3VdbeAddOp(v, OP_Column, iIdxCur, i);
00160       sqlite3VdbeAddOp(v, OP_MemLoad, iMem+nCol+i+1, 0);
00161       sqlite3VdbeAddOp(v, OP_Ne, 0x100, 0);
00162     }
00163     sqlite3VdbeAddOp(v, OP_Goto, 0, endOfLoop);
00164     for(i=0; i<nCol; i++){
00165       addr = sqlite3VdbeAddOp(v, OP_MemIncr, 1, iMem+i+1);
00166       sqlite3VdbeChangeP2(v, topOfLoop + 3*i + 3, addr);
00167       sqlite3VdbeAddOp(v, OP_Column, iIdxCur, i);
00168       sqlite3VdbeAddOp(v, OP_MemStore, iMem+nCol+i+1, 1);
00169     }
00170     sqlite3VdbeResolveLabel(v, endOfLoop);
00171     sqlite3VdbeAddOp(v, OP_Next, iIdxCur, topOfLoop);
00172     sqlite3VdbeAddOp(v, OP_Close, iIdxCur, 0);
00173 
00174     /* Store the results.  
00175     **
00176     ** The result is a single row of the sqlite_stmt1 table.  The first
00177     ** two columns are the names of the table and index.  The third column
00178     ** is a string composed of a list of integer statistics about the
00179     ** index.  The first integer in the list is the total number of entires
00180     ** in the index.  There is one additional integer in the list for each
00181     ** column of the table.  This additional integer is a guess of how many
00182     ** rows of the table the index will select.  If D is the count of distinct
00183     ** values and K is the total number of rows, then the integer is computed
00184     ** as:
00185     **
00186     **        I = (K+D-1)/D
00187     **
00188     ** If K==0 then no entry is made into the sqlite_stat1 table.  
00189     ** If K>0 then it is always the case the D>0 so division by zero
00190     ** is never possible.
00191     */
00192     sqlite3VdbeAddOp(v, OP_MemLoad, iMem, 0);
00193     addr = sqlite3VdbeAddOp(v, OP_IfNot, 0, 0);
00194     sqlite3VdbeAddOp(v, OP_NewRowid, iStatCur, 0);
00195     sqlite3VdbeOp3(v, OP_String8, 0, 0, pTab->zName, 0);
00196     sqlite3VdbeOp3(v, OP_String8, 0, 0, pIdx->zName, 0);
00197     sqlite3VdbeAddOp(v, OP_MemLoad, iMem, 0);
00198     sqlite3VdbeOp3(v, OP_String8, 0, 0, " ", 0);
00199     for(i=0; i<nCol; i++){
00200       sqlite3VdbeAddOp(v, OP_MemLoad, iMem, 0);
00201       sqlite3VdbeAddOp(v, OP_MemLoad, iMem+i+1, 0);
00202       sqlite3VdbeAddOp(v, OP_Add, 0, 0);
00203       sqlite3VdbeAddOp(v, OP_AddImm, -1, 0);
00204       sqlite3VdbeAddOp(v, OP_MemLoad, iMem+i+1, 0);
00205       sqlite3VdbeAddOp(v, OP_Divide, 0, 0);
00206       sqlite3VdbeAddOp(v, OP_ToInt, 0, 0);
00207       if( i==nCol-1 ){
00208         sqlite3VdbeAddOp(v, OP_Concat, nCol*2-1, 0);
00209       }else{
00210         sqlite3VdbeAddOp(v, OP_Dup, 1, 0);
00211       }
00212     }
00213     sqlite3VdbeOp3(v, OP_MakeRecord, 3, 0, "aaa", 0);
00214     sqlite3VdbeAddOp(v, OP_Insert, iStatCur, 0);
00215     sqlite3VdbeJumpHere(v, addr);
00216   }
00217 }
00218 
00219 /*
00220 ** Generate code that will cause the most recent index analysis to
00221 ** be laoded into internal hash tables where is can be used.
00222 */
00223 static void loadAnalysis(Parse *pParse, int iDb){
00224   Vdbe *v = sqlite3GetVdbe(pParse);
00225   sqlite3VdbeAddOp(v, OP_LoadAnalysis, iDb, 0);
00226 }
00227 
00228 /*
00229 ** Generate code that will do an analysis of an entire database
00230 */
00231 static void analyzeDatabase(Parse *pParse, int iDb){
00232   sqlite3 *db = pParse->db;
00233   Schema *pSchema = db->aDb[iDb].pSchema;    /* Schema of database iDb */
00234   HashElem *k;
00235   int iStatCur;
00236   int iMem;
00237 
00238   sqlite3BeginWriteOperation(pParse, 0, iDb);
00239   iStatCur = pParse->nTab++;
00240   openStatTable(pParse, iDb, iStatCur, 0);
00241   iMem = pParse->nMem;
00242   for(k=sqliteHashFirst(&pSchema->tblHash); k; k=sqliteHashNext(k)){
00243     Table *pTab = (Table*)sqliteHashData(k);
00244     analyzeOneTable(pParse, pTab, iStatCur, iMem);
00245   }
00246   loadAnalysis(pParse, iDb);
00247 }
00248 
00249 /*
00250 ** Generate code that will do an analysis of a single table in
00251 ** a database.
00252 */
00253 static void analyzeTable(Parse *pParse, Table *pTab){
00254   int iDb;
00255   int iStatCur;
00256 
00257   assert( pTab!=0 );
00258   iDb = sqlite3SchemaToIndex(pParse->db, pTab->pSchema);
00259   sqlite3BeginWriteOperation(pParse, 0, iDb);
00260   iStatCur = pParse->nTab++;
00261   openStatTable(pParse, iDb, iStatCur, pTab->zName);
00262   analyzeOneTable(pParse, pTab, iStatCur, pParse->nMem);
00263   loadAnalysis(pParse, iDb);
00264 }
00265 
00266 /*
00267 ** Generate code for the ANALYZE command.  The parser calls this routine
00268 ** when it recognizes an ANALYZE command.
00269 **
00270 **        ANALYZE                            -- 1
00271 **        ANALYZE  <database>                -- 2
00272 **        ANALYZE  ?<database>.?<tablename>  -- 3
00273 **
00274 ** Form 1 causes all indices in all attached databases to be analyzed.
00275 ** Form 2 analyzes all indices the single database named.
00276 ** Form 3 analyzes all indices associated with the named table.
00277 */
00278 void sqlite3Analyze(Parse *pParse, Token *pName1, Token *pName2){
00279   sqlite3 *db = pParse->db;
00280   int iDb;
00281   int i;
00282   char *z, *zDb;
00283   Table *pTab;
00284   Token *pTableName;
00285 
00286   /* Read the database schema. If an error occurs, leave an error message
00287   ** and code in pParse and return NULL. */
00288   if( SQLITE_OK!=sqlite3ReadSchema(pParse) ){
00289     return;
00290   }
00291 
00292   if( pName1==0 ){
00293     /* Form 1:  Analyze everything */
00294     for(i=0; i<db->nDb; i++){
00295       if( i==1 ) continue;  /* Do not analyze the TEMP database */
00296       analyzeDatabase(pParse, i);
00297     }
00298   }else if( pName2==0 || pName2->n==0 ){
00299     /* Form 2:  Analyze the database or table named */
00300     iDb = sqlite3FindDb(db, pName1);
00301     if( iDb>=0 ){
00302       analyzeDatabase(pParse, iDb);
00303     }else{
00304       z = sqlite3NameFromToken(pName1);
00305       pTab = sqlite3LocateTable(pParse, z, 0);
00306       sqliteFree(z);
00307       if( pTab ){
00308         analyzeTable(pParse, pTab);
00309       }
00310     }
00311   }else{
00312     /* Form 3: Analyze the fully qualified table name */
00313     iDb = sqlite3TwoPartName(pParse, pName1, pName2, &pTableName);
00314     if( iDb>=0 ){
00315       zDb = db->aDb[iDb].zName;
00316       z = sqlite3NameFromToken(pTableName);
00317       pTab = sqlite3LocateTable(pParse, z, zDb);
00318       sqliteFree(z);
00319       if( pTab ){
00320         analyzeTable(pParse, pTab);
00321       }
00322     }   
00323   }
00324 }
00325 
00326 /*
00327 ** Used to pass information from the analyzer reader through to the
00328 ** callback routine.
00329 */
00330 typedef struct analysisInfo analysisInfo;
00331 struct analysisInfo {
00332   sqlite3 *db;
00333   const char *zDatabase;
00334 };
00335 
00336 /*
00337 ** This callback is invoked once for each index when reading the
00338 ** sqlite_stat1 table.  
00339 **
00340 **     argv[0] = name of the index
00341 **     argv[1] = results of analysis - on integer for each column
00342 */
00343 static int analysisLoader(void *pData, int argc, char **argv, char **azNotUsed){
00344   analysisInfo *pInfo = (analysisInfo*)pData;
00345   Index *pIndex;
00346   int i, c;
00347   unsigned int v;
00348   const char *z;
00349 
00350   assert( argc==2 );
00351   if( argv==0 || argv[0]==0 || argv[1]==0 ){
00352     return 0;
00353   }
00354   pIndex = sqlite3FindIndex(pInfo->db, argv[0], pInfo->zDatabase);
00355   if( pIndex==0 ){
00356     return 0;
00357   }
00358   z = argv[1];
00359   for(i=0; *z && i<=pIndex->nColumn; i++){
00360     v = 0;
00361     while( (c=z[0])>='0' && c<='9' ){
00362       v = v*10 + c - '0';
00363       z++;
00364     }
00365     pIndex->aiRowEst[i] = v;
00366     if( *z==' ' ) z++;
00367   }
00368   return 0;
00369 }
00370 
00371 /*
00372 ** Load the content of the sqlite_stat1 table into the index hash tables.
00373 */
00374 void sqlite3AnalysisLoad(sqlite3 *db, int iDb){
00375   analysisInfo sInfo;
00376   HashElem *i;
00377   char *zSql;
00378 
00379   /* Clear any prior statistics */
00380   for(i=sqliteHashFirst(&db->aDb[iDb].pSchema->idxHash);i;i=sqliteHashNext(i)){
00381     Index *pIdx = sqliteHashData(i);
00382     sqlite3DefaultRowEst(pIdx);
00383   }
00384 
00385   /* Check to make sure the sqlite_stat1 table existss */
00386   sInfo.db = db;
00387   sInfo.zDatabase = db->aDb[iDb].zName;
00388   if( sqlite3FindTable(db, "sqlite_stat1", sInfo.zDatabase)==0 ){
00389      return;
00390   }
00391 
00392 
00393   /* Load new statistics out of the sqlite_stat1 table */
00394   zSql = sqlite3MPrintf("SELECT idx, stat FROM %Q.sqlite_stat1",
00395                         sInfo.zDatabase);
00396   sqlite3SafetyOff(db);
00397   sqlite3_exec(db, zSql, analysisLoader, &sInfo, 0);
00398   sqlite3SafetyOn(db);
00399   sqliteFree(zSql);
00400 }
00401 
00402 
00403 #endif /* SQLITE_OMIT_ANALYZE */