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.43 2008/07/28 19:34:53 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   int createStat1 = 0;

    37   Table *pStat;

    38   Vdbe *v = sqlite3GetVdbe(pParse);

    39 

    40   if( v==0 ) return;

    41   assert( sqlite3BtreeHoldsAllMutexes(db) );

    42   assert( sqlite3VdbeDb(v)==db );

    43   pDb = &db->aDb[iDb];

    44   if( (pStat = sqlite3FindTable(db, "sqlite_stat1", pDb->zName))==0 ){

    45     /* The sqlite_stat1 tables does not exist.  Create it.  

    46     ** Note that a side-effect of the CREATE TABLE statement is to leave

    47     ** the rootpage of the new table in register pParse->regRoot.  This is

    48     ** important because the OpenWrite opcode below will be needing it. */

    49     sqlite3NestedParse(pParse,

    50       "CREATE TABLE %Q.sqlite_stat1(tbl,idx,stat)",

    51       pDb->zName

    52     );

    53     iRootPage = pParse->regRoot;

    54     createStat1 = 1;  /* Cause rootpage to be taken from top of stack */

    55   }else if( zWhere ){

    56     /* The sqlite_stat1 table exists.  Delete all entries associated with

    57     ** the table zWhere. */

    58     sqlite3NestedParse(pParse,

    59        "DELETE FROM %Q.sqlite_stat1 WHERE tbl=%Q",

    60        pDb->zName, zWhere

    61     );

    62     iRootPage = pStat->tnum;

    63   }else{

    64     /* The sqlite_stat1 table already exists.  Delete all rows. */

    65     iRootPage = pStat->tnum;

    66     sqlite3VdbeAddOp2(v, OP_Clear, pStat->tnum, iDb);

    67   }

    68 

    69   /* Open the sqlite_stat1 table for writing. Unless it was created

    70   ** by this vdbe program, lock it for writing at the shared-cache level. 

    71   ** If this vdbe did create the sqlite_stat1 table, then it must have 

    72   ** already obtained a schema-lock, making the write-lock redundant.

    73   */

    74   if( !createStat1 ){

    75     sqlite3TableLock(pParse, iDb, iRootPage, 1, "sqlite_stat1");

    76   }

    77   sqlite3VdbeAddOp2(v, OP_SetNumColumns, 0, 3);

    78   sqlite3VdbeAddOp3(v, OP_OpenWrite, iStatCur, iRootPage, iDb);

    79   sqlite3VdbeChangeP5(v, createStat1);

    80 }

    81 

    82 /*

    83 ** Generate code to do an analysis of all indices associated with

    84 ** a single table.

    85 */

    86 static void analyzeOneTable(

    87   Parse *pParse,   /* Parser context */

    88   Table *pTab,     /* Table whose indices are to be analyzed */

    89   int iStatCur,    /* Cursor that writes to the sqlite_stat1 table */

    90   int iMem         /* Available memory locations begin here */

    91 ){

    92   Index *pIdx;     /* An index to being analyzed */

    93   int iIdxCur;     /* Cursor number for index being analyzed */

    94   int nCol;        /* Number of columns in the index */

    95   Vdbe *v;         /* The virtual machine being built up */

    96   int i;           /* Loop counter */

    97   int topOfLoop;   /* The top of the loop */

    98   int endOfLoop;   /* The end of the loop */

    99   int addr;        /* The address of an instruction */

   100   int iDb;         /* Index of database containing pTab */

   101 

   102   v = sqlite3GetVdbe(pParse);

   103   if( v==0 || pTab==0 || pTab->pIndex==0 ){

   104     /* Do no analysis for tables that have no indices */

   105     return;

   106   }

   107   assert( sqlite3BtreeHoldsAllMutexes(pParse->db) );

   108   iDb = sqlite3SchemaToIndex(pParse->db, pTab->pSchema);

   109   assert( iDb>=0 );

   110 #ifndef SQLITE_OMIT_AUTHORIZATION

   111   if( sqlite3AuthCheck(pParse, SQLITE_ANALYZE, pTab->zName, 0,

   112       pParse->db->aDb[iDb].zName ) ){

   113     return;

   114   }

   115 #endif

   116 

   117   /* Establish a read-lock on the table at the shared-cache level. */

   118   sqlite3TableLock(pParse, iDb, pTab->tnum, 0, pTab->zName);

   119 

   120   iIdxCur = pParse->nTab;

   121   for(pIdx=pTab->pIndex; pIdx; pIdx=pIdx->pNext){

   122     KeyInfo *pKey = sqlite3IndexKeyinfo(pParse, pIdx);

   123     int regFields;    /* Register block for building records */

   124     int regRec;       /* Register holding completed record */

   125     int regTemp;      /* Temporary use register */

   126     int regCol;       /* Content of a column from the table being analyzed */

   127     int regRowid;     /* Rowid for the inserted record */

   128     int regF2;

   129 

   130     /* Open a cursor to the index to be analyzed

   131     */

   132     assert( iDb==sqlite3SchemaToIndex(pParse->db, pIdx->pSchema) );

   133     nCol = pIdx->nColumn;

   134     sqlite3VdbeAddOp2(v, OP_SetNumColumns, 0, nCol+1);

   135     sqlite3VdbeAddOp4(v, OP_OpenRead, iIdxCur, pIdx->tnum, iDb,

   136         (char *)pKey, P4_KEYINFO_HANDOFF);

   137     VdbeComment((v, "%s", pIdx->zName));

   138     regFields = iMem+nCol*2;

   139     regTemp = regRowid = regCol = regFields+3;

   140     regRec = regCol+1;

   141     if( regRec>pParse->nMem ){

   142       pParse->nMem = regRec;

   143     }

   144 

   145     /* Memory cells are used as follows:

   146     **

   147     **    mem[iMem]:             The total number of rows in the table.

   148     **    mem[iMem+1]:           Number of distinct values in column 1

   149     **    ...

   150     **    mem[iMem+nCol]:        Number of distinct values in column N

   151     **    mem[iMem+nCol+1]       Last observed value of column 1

   152     **    ...

   153     **    mem[iMem+nCol+nCol]:   Last observed value of column N

   154     **

   155     ** Cells iMem through iMem+nCol are initialized to 0.  The others

   156     ** are initialized to NULL.

   157     */

   158     for(i=0; i<=nCol; i++){

   159       sqlite3VdbeAddOp2(v, OP_Integer, 0, iMem+i);

   160     }

   161     for(i=0; i<nCol; i++){

   162       sqlite3VdbeAddOp2(v, OP_Null, 0, iMem+nCol+i+1);

   163     }

   164 

   165     /* Do the analysis.

   166     */

   167     endOfLoop = sqlite3VdbeMakeLabel(v);

   168     sqlite3VdbeAddOp2(v, OP_Rewind, iIdxCur, endOfLoop);

   169     topOfLoop = sqlite3VdbeCurrentAddr(v);

   170     sqlite3VdbeAddOp2(v, OP_AddImm, iMem, 1);

   171     for(i=0; i<nCol; i++){

   172       sqlite3VdbeAddOp3(v, OP_Column, iIdxCur, i, regCol);

   173       sqlite3VdbeAddOp3(v, OP_Ne, regCol, 0, iMem+nCol+i+1);

   174       /**** TODO:  add collating sequence *****/

   175       sqlite3VdbeChangeP5(v, SQLITE_JUMPIFNULL);

   176     }

   177     sqlite3VdbeAddOp2(v, OP_Goto, 0, endOfLoop);

   178     for(i=0; i<nCol; i++){

   179       sqlite3VdbeJumpHere(v, topOfLoop + 2*(i + 1));

   180       sqlite3VdbeAddOp2(v, OP_AddImm, iMem+i+1, 1);

   181       sqlite3VdbeAddOp3(v, OP_Column, iIdxCur, i, iMem+nCol+i+1);

   182     }

   183     sqlite3VdbeResolveLabel(v, endOfLoop);

   184     sqlite3VdbeAddOp2(v, OP_Next, iIdxCur, topOfLoop);

   185     sqlite3VdbeAddOp1(v, OP_Close, iIdxCur);

   186 

   187     /* Store the results.  

   188     **

   189     ** The result is a single row of the sqlite_stat1 table.  The first

   190     ** two columns are the names of the table and index.  The third column

   191     ** is a string composed of a list of integer statistics about the

   192     ** index.  The first integer in the list is the total number of entires

   193     ** in the index.  There is one additional integer in the list for each

   194     ** column of the table.  This additional integer is a guess of how many

   195     ** rows of the table the index will select.  If D is the count of distinct

   196     ** values and K is the total number of rows, then the integer is computed

   197     ** as:

   198     **

   199     **        I = (K+D-1)/D

   200     **

   201     ** If K==0 then no entry is made into the sqlite_stat1 table.  

   202     ** If K>0 then it is always the case the D>0 so division by zero

   203     ** is never possible.

   204     */

   205     addr = sqlite3VdbeAddOp1(v, OP_IfNot, iMem);

   206     sqlite3VdbeAddOp4(v, OP_String8, 0, regFields, 0, pTab->zName, 0);

   207     sqlite3VdbeAddOp4(v, OP_String8, 0, regFields+1, 0, pIdx->zName, 0);

   208     regF2 = regFields+2;

   209     sqlite3VdbeAddOp2(v, OP_SCopy, iMem, regF2);

   210     for(i=0; i<nCol; i++){

   211       sqlite3VdbeAddOp4(v, OP_String8, 0, regTemp, 0, " ", 0);

   212       sqlite3VdbeAddOp3(v, OP_Concat, regTemp, regF2, regF2);

   213       sqlite3VdbeAddOp3(v, OP_Add, iMem, iMem+i+1, regTemp);

   214       sqlite3VdbeAddOp2(v, OP_AddImm, regTemp, -1);

   215       sqlite3VdbeAddOp3(v, OP_Divide, iMem+i+1, regTemp, regTemp);

   216       sqlite3VdbeAddOp1(v, OP_ToInt, regTemp);

   217       sqlite3VdbeAddOp3(v, OP_Concat, regTemp, regF2, regF2);

   218     }

   219     sqlite3VdbeAddOp4(v, OP_MakeRecord, regFields, 3, regRec, "aaa", 0);

   220     sqlite3VdbeAddOp2(v, OP_NewRowid, iStatCur, regRowid);

   221     sqlite3VdbeAddOp3(v, OP_Insert, iStatCur, regRec, regRowid);

   222     sqlite3VdbeChangeP5(v, OPFLAG_APPEND);

   223     sqlite3VdbeJumpHere(v, addr);

   224   }

   225 }

   226 

   227 /*

   228 ** Generate code that will cause the most recent index analysis to

   229 ** be laoded into internal hash tables where is can be used.

   230 */

   231 static void loadAnalysis(Parse *pParse, int iDb){

   232   Vdbe *v = sqlite3GetVdbe(pParse);

   233   if( v ){

   234     sqlite3VdbeAddOp1(v, OP_LoadAnalysis, iDb);

   235   }

   236 }

   237 

   238 /*

   239 ** Generate code that will do an analysis of an entire database

   240 */

   241 static void analyzeDatabase(Parse *pParse, int iDb){

   242   sqlite3 *db = pParse->db;

   243   Schema *pSchema = db->aDb[iDb].pSchema;    /* Schema of database iDb */

   244   HashElem *k;

   245   int iStatCur;

   246   int iMem;

   247 

   248   sqlite3BeginWriteOperation(pParse, 0, iDb);

   249   iStatCur = pParse->nTab++;

   250   openStatTable(pParse, iDb, iStatCur, 0);

   251   iMem = pParse->nMem+1;

   252   for(k=sqliteHashFirst(&pSchema->tblHash); k; k=sqliteHashNext(k)){

   253     Table *pTab = (Table*)sqliteHashData(k);

   254     analyzeOneTable(pParse, pTab, iStatCur, iMem);

   255   }

   256   loadAnalysis(pParse, iDb);

   257 }

   258 

   259 /*

   260 ** Generate code that will do an analysis of a single table in

   261 ** a database.

   262 */

   263 static void analyzeTable(Parse *pParse, Table *pTab){

   264   int iDb;

   265   int iStatCur;

   266 

   267   assert( pTab!=0 );

   268   assert( sqlite3BtreeHoldsAllMutexes(pParse->db) );

   269   iDb = sqlite3SchemaToIndex(pParse->db, pTab->pSchema);

   270   sqlite3BeginWriteOperation(pParse, 0, iDb);

   271   iStatCur = pParse->nTab++;

   272   openStatTable(pParse, iDb, iStatCur, pTab->zName);

   273   analyzeOneTable(pParse, pTab, iStatCur, pParse->nMem+1);

   274   loadAnalysis(pParse, iDb);

   275 }

   276 

   277 /*

   278 ** Generate code for the ANALYZE command.  The parser calls this routine

   279 ** when it recognizes an ANALYZE command.

   280 **

   281 **        ANALYZE                            -- 1

   282 **        ANALYZE  <database>                -- 2

   283 **        ANALYZE  ?<database>.?<tablename>  -- 3

   284 **

   285 ** Form 1 causes all indices in all attached databases to be analyzed.

   286 ** Form 2 analyzes all indices the single database named.

   287 ** Form 3 analyzes all indices associated with the named table.

   288 */

   289 void sqlite3Analyze(Parse *pParse, Token *pName1, Token *pName2){

   290   sqlite3 *db = pParse->db;

   291   int iDb;

   292   int i;

   293   char *z, *zDb;

   294   Table *pTab;

   295   Token *pTableName;

   296 

   297   /* Read the database schema. If an error occurs, leave an error message

   298   ** and code in pParse and return NULL. */

   299   assert( sqlite3BtreeHoldsAllMutexes(pParse->db) );

   300   if( SQLITE_OK!=sqlite3ReadSchema(pParse) ){

   301     return;

   302   }

   303 

   304   if( pName1==0 ){

   305     /* Form 1:  Analyze everything */

   306     for(i=0; i<db->nDb; i++){

   307       if( i==1 ) continue;  /* Do not analyze the TEMP database */

   308       analyzeDatabase(pParse, i);

   309     }

   310   }else if( pName2==0 || pName2->n==0 ){

   311     /* Form 2:  Analyze the database or table named */

   312     iDb = sqlite3FindDb(db, pName1);

   313     if( iDb>=0 ){

   314       analyzeDatabase(pParse, iDb);

   315     }else{

   316       z = sqlite3NameFromToken(db, pName1);

   317       if( z ){

   318         pTab = sqlite3LocateTable(pParse, 0, z, 0);

   319         sqlite3DbFree(db, z);

   320         if( pTab ){

   321           analyzeTable(pParse, pTab);

   322         }

   323       }

   324     }

   325   }else{

   326     /* Form 3: Analyze the fully qualified table name */

   327     iDb = sqlite3TwoPartName(pParse, pName1, pName2, &pTableName);

   328     if( iDb>=0 ){

   329       zDb = db->aDb[iDb].zName;

   330       z = sqlite3NameFromToken(db, pTableName);

   331       if( z ){

   332         pTab = sqlite3LocateTable(pParse, 0, z, zDb);

   333         sqlite3DbFree(db, z);

   334         if( pTab ){

   335           analyzeTable(pParse, pTab);

   336         }

   337       }

   338     }   

   339   }

   340 }

   341 

   342 /*

   343 ** Used to pass information from the analyzer reader through to the

   344 ** callback routine.

   345 */

   346 typedef struct analysisInfo analysisInfo;

   347 struct analysisInfo {

   348   sqlite3 *db;

   349   const char *zDatabase;

   350 };

   351 

   352 /*

   353 ** This callback is invoked once for each index when reading the

   354 ** sqlite_stat1 table.  

   355 **

   356 **     argv[0] = name of the index

   357 **     argv[1] = results of analysis - on integer for each column

   358 */

   359 static int analysisLoader(void *pData, int argc, char **argv, char **azNotUsed){

   360   analysisInfo *pInfo = (analysisInfo*)pData;

   361   Index *pIndex;

   362   int i, c;

   363   unsigned int v;

   364   const char *z;

   365 

   366   assert( argc==2 );

   367   if( argv==0 || argv[0]==0 || argv[1]==0 ){

   368     return 0;

   369   }

   370   pIndex = sqlite3FindIndex(pInfo->db, argv[0], pInfo->zDatabase);

   371   if( pIndex==0 ){

   372     return 0;

   373   }

   374   z = argv[1];

   375   for(i=0; *z && i<=pIndex->nColumn; i++){

   376     v = 0;

   377     while( (c=z[0])>='0' && c<='9' ){

   378       v = v*10 + c - '0';

   379       z++;

   380     }

   381     pIndex->aiRowEst[i] = v;

   382     if( *z==' ' ) z++;

   383   }

   384   return 0;

   385 }

   386 

   387 /*

   388 ** Load the content of the sqlite_stat1 table into the index hash tables.

   389 */

   390 int sqlite3AnalysisLoad(sqlite3 *db, int iDb){

   391   analysisInfo sInfo;

   392   HashElem *i;

   393   char *zSql;

   394   int rc;

   395 

   396   assert( iDb>=0 && iDb<db->nDb );

   397   assert( db->aDb[iDb].pBt!=0 );

   398   assert( sqlite3BtreeHoldsMutex(db->aDb[iDb].pBt) );

   399 

   400   /* Clear any prior statistics */

   401   for(i=sqliteHashFirst(&db->aDb[iDb].pSchema->idxHash);i;i=sqliteHashNext(i)){

   402     Index *pIdx = sqliteHashData(i);

   403     sqlite3DefaultRowEst(pIdx);

   404   }

   405 

   406   /* Check to make sure the sqlite_stat1 table existss */

   407   sInfo.db = db;

   408   sInfo.zDatabase = db->aDb[iDb].zName;

   409   if( sqlite3FindTable(db, "sqlite_stat1", sInfo.zDatabase)==0 ){

   410      return SQLITE_ERROR;

   411   }

   412 

   413 

   414   /* Load new statistics out of the sqlite_stat1 table */

   415   zSql = sqlite3MPrintf(db, "SELECT idx, stat FROM %Q.sqlite_stat1",

   416                         sInfo.zDatabase);

   417   (void)sqlite3SafetyOff(db);

   418   rc = sqlite3_exec(db, zSql, analysisLoader, &sInfo, 0);

   419   (void)sqlite3SafetyOn(db);

   420   sqlite3DbFree(db, zSql);

   421   return rc;

   422 }

   423 

   424 

   425 #endif /* SQLITE_OMIT_ANALYZE */