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.cpp 1282 2008-11-13 09:31:33Z LarsPson $

    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 = (Index *)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 */