sl@0: /*
sl@0: ** 2005 July 8
sl@0: **
sl@0: ** The author disclaims copyright to this source code.  In place of
sl@0: ** a legal notice, here is a blessing:
sl@0: **
sl@0: **    May you do good and not evil.
sl@0: **    May you find forgiveness for yourself and forgive others.
sl@0: **    May you share freely, never taking more than you give.
sl@0: **
sl@0: *************************************************************************
sl@0: ** This file contains code associated with the ANALYZE command.
sl@0: **
sl@0: ** @(#) $Id: analyze.c,v 1.43 2008/07/28 19:34:53 drh Exp $
sl@0: */
sl@0: #ifndef SQLITE_OMIT_ANALYZE
sl@0: #include "sqliteInt.h"
sl@0: 
sl@0: /*
sl@0: ** This routine generates code that opens the sqlite_stat1 table on cursor
sl@0: ** iStatCur.
sl@0: **
sl@0: ** If the sqlite_stat1 tables does not previously exist, it is created.
sl@0: ** If it does previously exist, all entires associated with table zWhere
sl@0: ** are removed.  If zWhere==0 then all entries are removed.
sl@0: */
sl@0: static void openStatTable(
sl@0:   Parse *pParse,          /* Parsing context */
sl@0:   int iDb,                /* The database we are looking in */
sl@0:   int iStatCur,           /* Open the sqlite_stat1 table on this cursor */
sl@0:   const char *zWhere      /* Delete entries associated with this table */
sl@0: ){
sl@0:   sqlite3 *db = pParse->db;
sl@0:   Db *pDb;
sl@0:   int iRootPage;
sl@0:   int createStat1 = 0;
sl@0:   Table *pStat;
sl@0:   Vdbe *v = sqlite3GetVdbe(pParse);
sl@0: 
sl@0:   if( v==0 ) return;
sl@0:   assert( sqlite3BtreeHoldsAllMutexes(db) );
sl@0:   assert( sqlite3VdbeDb(v)==db );
sl@0:   pDb = &db->aDb[iDb];
sl@0:   if( (pStat = sqlite3FindTable(db, "sqlite_stat1", pDb->zName))==0 ){
sl@0:     /* The sqlite_stat1 tables does not exist.  Create it.  
sl@0:     ** Note that a side-effect of the CREATE TABLE statement is to leave
sl@0:     ** the rootpage of the new table in register pParse->regRoot.  This is
sl@0:     ** important because the OpenWrite opcode below will be needing it. */
sl@0:     sqlite3NestedParse(pParse,
sl@0:       "CREATE TABLE %Q.sqlite_stat1(tbl,idx,stat)",
sl@0:       pDb->zName
sl@0:     );
sl@0:     iRootPage = pParse->regRoot;
sl@0:     createStat1 = 1;  /* Cause rootpage to be taken from top of stack */
sl@0:   }else if( zWhere ){
sl@0:     /* The sqlite_stat1 table exists.  Delete all entries associated with
sl@0:     ** the table zWhere. */
sl@0:     sqlite3NestedParse(pParse,
sl@0:        "DELETE FROM %Q.sqlite_stat1 WHERE tbl=%Q",
sl@0:        pDb->zName, zWhere
sl@0:     );
sl@0:     iRootPage = pStat->tnum;
sl@0:   }else{
sl@0:     /* The sqlite_stat1 table already exists.  Delete all rows. */
sl@0:     iRootPage = pStat->tnum;
sl@0:     sqlite3VdbeAddOp2(v, OP_Clear, pStat->tnum, iDb);
sl@0:   }
sl@0: 
sl@0:   /* Open the sqlite_stat1 table for writing. Unless it was created
sl@0:   ** by this vdbe program, lock it for writing at the shared-cache level. 
sl@0:   ** If this vdbe did create the sqlite_stat1 table, then it must have 
sl@0:   ** already obtained a schema-lock, making the write-lock redundant.
sl@0:   */
sl@0:   if( !createStat1 ){
sl@0:     sqlite3TableLock(pParse, iDb, iRootPage, 1, "sqlite_stat1");
sl@0:   }
sl@0:   sqlite3VdbeAddOp2(v, OP_SetNumColumns, 0, 3);
sl@0:   sqlite3VdbeAddOp3(v, OP_OpenWrite, iStatCur, iRootPage, iDb);
sl@0:   sqlite3VdbeChangeP5(v, createStat1);
sl@0: }
sl@0: 
sl@0: /*
sl@0: ** Generate code to do an analysis of all indices associated with
sl@0: ** a single table.
sl@0: */
sl@0: static void analyzeOneTable(
sl@0:   Parse *pParse,   /* Parser context */
sl@0:   Table *pTab,     /* Table whose indices are to be analyzed */
sl@0:   int iStatCur,    /* Cursor that writes to the sqlite_stat1 table */
sl@0:   int iMem         /* Available memory locations begin here */
sl@0: ){
sl@0:   Index *pIdx;     /* An index to being analyzed */
sl@0:   int iIdxCur;     /* Cursor number for index being analyzed */
sl@0:   int nCol;        /* Number of columns in the index */
sl@0:   Vdbe *v;         /* The virtual machine being built up */
sl@0:   int i;           /* Loop counter */
sl@0:   int topOfLoop;   /* The top of the loop */
sl@0:   int endOfLoop;   /* The end of the loop */
sl@0:   int addr;        /* The address of an instruction */
sl@0:   int iDb;         /* Index of database containing pTab */
sl@0: 
sl@0:   v = sqlite3GetVdbe(pParse);
sl@0:   if( v==0 || pTab==0 || pTab->pIndex==0 ){
sl@0:     /* Do no analysis for tables that have no indices */
sl@0:     return;
sl@0:   }
sl@0:   assert( sqlite3BtreeHoldsAllMutexes(pParse->db) );
sl@0:   iDb = sqlite3SchemaToIndex(pParse->db, pTab->pSchema);
sl@0:   assert( iDb>=0 );
sl@0: #ifndef SQLITE_OMIT_AUTHORIZATION
sl@0:   if( sqlite3AuthCheck(pParse, SQLITE_ANALYZE, pTab->zName, 0,
sl@0:       pParse->db->aDb[iDb].zName ) ){
sl@0:     return;
sl@0:   }
sl@0: #endif
sl@0: 
sl@0:   /* Establish a read-lock on the table at the shared-cache level. */
sl@0:   sqlite3TableLock(pParse, iDb, pTab->tnum, 0, pTab->zName);
sl@0: 
sl@0:   iIdxCur = pParse->nTab;
sl@0:   for(pIdx=pTab->pIndex; pIdx; pIdx=pIdx->pNext){
sl@0:     KeyInfo *pKey = sqlite3IndexKeyinfo(pParse, pIdx);
sl@0:     int regFields;    /* Register block for building records */
sl@0:     int regRec;       /* Register holding completed record */
sl@0:     int regTemp;      /* Temporary use register */
sl@0:     int regCol;       /* Content of a column from the table being analyzed */
sl@0:     int regRowid;     /* Rowid for the inserted record */
sl@0:     int regF2;
sl@0: 
sl@0:     /* Open a cursor to the index to be analyzed
sl@0:     */
sl@0:     assert( iDb==sqlite3SchemaToIndex(pParse->db, pIdx->pSchema) );
sl@0:     nCol = pIdx->nColumn;
sl@0:     sqlite3VdbeAddOp2(v, OP_SetNumColumns, 0, nCol+1);
sl@0:     sqlite3VdbeAddOp4(v, OP_OpenRead, iIdxCur, pIdx->tnum, iDb,
sl@0:         (char *)pKey, P4_KEYINFO_HANDOFF);
sl@0:     VdbeComment((v, "%s", pIdx->zName));
sl@0:     regFields = iMem+nCol*2;
sl@0:     regTemp = regRowid = regCol = regFields+3;
sl@0:     regRec = regCol+1;
sl@0:     if( regRec>pParse->nMem ){
sl@0:       pParse->nMem = regRec;
sl@0:     }
sl@0: 
sl@0:     /* Memory cells are used as follows:
sl@0:     **
sl@0:     **    mem[iMem]:             The total number of rows in the table.
sl@0:     **    mem[iMem+1]:           Number of distinct values in column 1
sl@0:     **    ...
sl@0:     **    mem[iMem+nCol]:        Number of distinct values in column N
sl@0:     **    mem[iMem+nCol+1]       Last observed value of column 1
sl@0:     **    ...
sl@0:     **    mem[iMem+nCol+nCol]:   Last observed value of column N
sl@0:     **
sl@0:     ** Cells iMem through iMem+nCol are initialized to 0.  The others
sl@0:     ** are initialized to NULL.
sl@0:     */
sl@0:     for(i=0; i<=nCol; i++){
sl@0:       sqlite3VdbeAddOp2(v, OP_Integer, 0, iMem+i);
sl@0:     }
sl@0:     for(i=0; i<nCol; i++){
sl@0:       sqlite3VdbeAddOp2(v, OP_Null, 0, iMem+nCol+i+1);
sl@0:     }
sl@0: 
sl@0:     /* Do the analysis.
sl@0:     */
sl@0:     endOfLoop = sqlite3VdbeMakeLabel(v);
sl@0:     sqlite3VdbeAddOp2(v, OP_Rewind, iIdxCur, endOfLoop);
sl@0:     topOfLoop = sqlite3VdbeCurrentAddr(v);
sl@0:     sqlite3VdbeAddOp2(v, OP_AddImm, iMem, 1);
sl@0:     for(i=0; i<nCol; i++){
sl@0:       sqlite3VdbeAddOp3(v, OP_Column, iIdxCur, i, regCol);
sl@0:       sqlite3VdbeAddOp3(v, OP_Ne, regCol, 0, iMem+nCol+i+1);
sl@0:       /**** TODO:  add collating sequence *****/
sl@0:       sqlite3VdbeChangeP5(v, SQLITE_JUMPIFNULL);
sl@0:     }
sl@0:     sqlite3VdbeAddOp2(v, OP_Goto, 0, endOfLoop);
sl@0:     for(i=0; i<nCol; i++){
sl@0:       sqlite3VdbeJumpHere(v, topOfLoop + 2*(i + 1));
sl@0:       sqlite3VdbeAddOp2(v, OP_AddImm, iMem+i+1, 1);
sl@0:       sqlite3VdbeAddOp3(v, OP_Column, iIdxCur, i, iMem+nCol+i+1);
sl@0:     }
sl@0:     sqlite3VdbeResolveLabel(v, endOfLoop);
sl@0:     sqlite3VdbeAddOp2(v, OP_Next, iIdxCur, topOfLoop);
sl@0:     sqlite3VdbeAddOp1(v, OP_Close, iIdxCur);
sl@0: 
sl@0:     /* Store the results.  
sl@0:     **
sl@0:     ** The result is a single row of the sqlite_stat1 table.  The first
sl@0:     ** two columns are the names of the table and index.  The third column
sl@0:     ** is a string composed of a list of integer statistics about the
sl@0:     ** index.  The first integer in the list is the total number of entires
sl@0:     ** in the index.  There is one additional integer in the list for each
sl@0:     ** column of the table.  This additional integer is a guess of how many
sl@0:     ** rows of the table the index will select.  If D is the count of distinct
sl@0:     ** values and K is the total number of rows, then the integer is computed
sl@0:     ** as:
sl@0:     **
sl@0:     **        I = (K+D-1)/D
sl@0:     **
sl@0:     ** If K==0 then no entry is made into the sqlite_stat1 table.  
sl@0:     ** If K>0 then it is always the case the D>0 so division by zero
sl@0:     ** is never possible.
sl@0:     */
sl@0:     addr = sqlite3VdbeAddOp1(v, OP_IfNot, iMem);
sl@0:     sqlite3VdbeAddOp4(v, OP_String8, 0, regFields, 0, pTab->zName, 0);
sl@0:     sqlite3VdbeAddOp4(v, OP_String8, 0, regFields+1, 0, pIdx->zName, 0);
sl@0:     regF2 = regFields+2;
sl@0:     sqlite3VdbeAddOp2(v, OP_SCopy, iMem, regF2);
sl@0:     for(i=0; i<nCol; i++){
sl@0:       sqlite3VdbeAddOp4(v, OP_String8, 0, regTemp, 0, " ", 0);
sl@0:       sqlite3VdbeAddOp3(v, OP_Concat, regTemp, regF2, regF2);
sl@0:       sqlite3VdbeAddOp3(v, OP_Add, iMem, iMem+i+1, regTemp);
sl@0:       sqlite3VdbeAddOp2(v, OP_AddImm, regTemp, -1);
sl@0:       sqlite3VdbeAddOp3(v, OP_Divide, iMem+i+1, regTemp, regTemp);
sl@0:       sqlite3VdbeAddOp1(v, OP_ToInt, regTemp);
sl@0:       sqlite3VdbeAddOp3(v, OP_Concat, regTemp, regF2, regF2);
sl@0:     }
sl@0:     sqlite3VdbeAddOp4(v, OP_MakeRecord, regFields, 3, regRec, "aaa", 0);
sl@0:     sqlite3VdbeAddOp2(v, OP_NewRowid, iStatCur, regRowid);
sl@0:     sqlite3VdbeAddOp3(v, OP_Insert, iStatCur, regRec, regRowid);
sl@0:     sqlite3VdbeChangeP5(v, OPFLAG_APPEND);
sl@0:     sqlite3VdbeJumpHere(v, addr);
sl@0:   }
sl@0: }
sl@0: 
sl@0: /*
sl@0: ** Generate code that will cause the most recent index analysis to
sl@0: ** be laoded into internal hash tables where is can be used.
sl@0: */
sl@0: static void loadAnalysis(Parse *pParse, int iDb){
sl@0:   Vdbe *v = sqlite3GetVdbe(pParse);
sl@0:   if( v ){
sl@0:     sqlite3VdbeAddOp1(v, OP_LoadAnalysis, iDb);
sl@0:   }
sl@0: }
sl@0: 
sl@0: /*
sl@0: ** Generate code that will do an analysis of an entire database
sl@0: */
sl@0: static void analyzeDatabase(Parse *pParse, int iDb){
sl@0:   sqlite3 *db = pParse->db;
sl@0:   Schema *pSchema = db->aDb[iDb].pSchema;    /* Schema of database iDb */
sl@0:   HashElem *k;
sl@0:   int iStatCur;
sl@0:   int iMem;
sl@0: 
sl@0:   sqlite3BeginWriteOperation(pParse, 0, iDb);
sl@0:   iStatCur = pParse->nTab++;
sl@0:   openStatTable(pParse, iDb, iStatCur, 0);
sl@0:   iMem = pParse->nMem+1;
sl@0:   for(k=sqliteHashFirst(&pSchema->tblHash); k; k=sqliteHashNext(k)){
sl@0:     Table *pTab = (Table*)sqliteHashData(k);
sl@0:     analyzeOneTable(pParse, pTab, iStatCur, iMem);
sl@0:   }
sl@0:   loadAnalysis(pParse, iDb);
sl@0: }
sl@0: 
sl@0: /*
sl@0: ** Generate code that will do an analysis of a single table in
sl@0: ** a database.
sl@0: */
sl@0: static void analyzeTable(Parse *pParse, Table *pTab){
sl@0:   int iDb;
sl@0:   int iStatCur;
sl@0: 
sl@0:   assert( pTab!=0 );
sl@0:   assert( sqlite3BtreeHoldsAllMutexes(pParse->db) );
sl@0:   iDb = sqlite3SchemaToIndex(pParse->db, pTab->pSchema);
sl@0:   sqlite3BeginWriteOperation(pParse, 0, iDb);
sl@0:   iStatCur = pParse->nTab++;
sl@0:   openStatTable(pParse, iDb, iStatCur, pTab->zName);
sl@0:   analyzeOneTable(pParse, pTab, iStatCur, pParse->nMem+1);
sl@0:   loadAnalysis(pParse, iDb);
sl@0: }
sl@0: 
sl@0: /*
sl@0: ** Generate code for the ANALYZE command.  The parser calls this routine
sl@0: ** when it recognizes an ANALYZE command.
sl@0: **
sl@0: **        ANALYZE                            -- 1
sl@0: **        ANALYZE  <database>                -- 2
sl@0: **        ANALYZE  ?<database>.?<tablename>  -- 3
sl@0: **
sl@0: ** Form 1 causes all indices in all attached databases to be analyzed.
sl@0: ** Form 2 analyzes all indices the single database named.
sl@0: ** Form 3 analyzes all indices associated with the named table.
sl@0: */
sl@0: void sqlite3Analyze(Parse *pParse, Token *pName1, Token *pName2){
sl@0:   sqlite3 *db = pParse->db;
sl@0:   int iDb;
sl@0:   int i;
sl@0:   char *z, *zDb;
sl@0:   Table *pTab;
sl@0:   Token *pTableName;
sl@0: 
sl@0:   /* Read the database schema. If an error occurs, leave an error message
sl@0:   ** and code in pParse and return NULL. */
sl@0:   assert( sqlite3BtreeHoldsAllMutexes(pParse->db) );
sl@0:   if( SQLITE_OK!=sqlite3ReadSchema(pParse) ){
sl@0:     return;
sl@0:   }
sl@0: 
sl@0:   if( pName1==0 ){
sl@0:     /* Form 1:  Analyze everything */
sl@0:     for(i=0; i<db->nDb; i++){
sl@0:       if( i==1 ) continue;  /* Do not analyze the TEMP database */
sl@0:       analyzeDatabase(pParse, i);
sl@0:     }
sl@0:   }else if( pName2==0 || pName2->n==0 ){
sl@0:     /* Form 2:  Analyze the database or table named */
sl@0:     iDb = sqlite3FindDb(db, pName1);
sl@0:     if( iDb>=0 ){
sl@0:       analyzeDatabase(pParse, iDb);
sl@0:     }else{
sl@0:       z = sqlite3NameFromToken(db, pName1);
sl@0:       if( z ){
sl@0:         pTab = sqlite3LocateTable(pParse, 0, z, 0);
sl@0:         sqlite3DbFree(db, z);
sl@0:         if( pTab ){
sl@0:           analyzeTable(pParse, pTab);
sl@0:         }
sl@0:       }
sl@0:     }
sl@0:   }else{
sl@0:     /* Form 3: Analyze the fully qualified table name */
sl@0:     iDb = sqlite3TwoPartName(pParse, pName1, pName2, &pTableName);
sl@0:     if( iDb>=0 ){
sl@0:       zDb = db->aDb[iDb].zName;
sl@0:       z = sqlite3NameFromToken(db, pTableName);
sl@0:       if( z ){
sl@0:         pTab = sqlite3LocateTable(pParse, 0, z, zDb);
sl@0:         sqlite3DbFree(db, z);
sl@0:         if( pTab ){
sl@0:           analyzeTable(pParse, pTab);
sl@0:         }
sl@0:       }
sl@0:     }   
sl@0:   }
sl@0: }
sl@0: 
sl@0: /*
sl@0: ** Used to pass information from the analyzer reader through to the
sl@0: ** callback routine.
sl@0: */
sl@0: typedef struct analysisInfo analysisInfo;
sl@0: struct analysisInfo {
sl@0:   sqlite3 *db;
sl@0:   const char *zDatabase;
sl@0: };
sl@0: 
sl@0: /*
sl@0: ** This callback is invoked once for each index when reading the
sl@0: ** sqlite_stat1 table.  
sl@0: **
sl@0: **     argv[0] = name of the index
sl@0: **     argv[1] = results of analysis - on integer for each column
sl@0: */
sl@0: static int analysisLoader(void *pData, int argc, char **argv, char **azNotUsed){
sl@0:   analysisInfo *pInfo = (analysisInfo*)pData;
sl@0:   Index *pIndex;
sl@0:   int i, c;
sl@0:   unsigned int v;
sl@0:   const char *z;
sl@0: 
sl@0:   assert( argc==2 );
sl@0:   if( argv==0 || argv[0]==0 || argv[1]==0 ){
sl@0:     return 0;
sl@0:   }
sl@0:   pIndex = sqlite3FindIndex(pInfo->db, argv[0], pInfo->zDatabase);
sl@0:   if( pIndex==0 ){
sl@0:     return 0;
sl@0:   }
sl@0:   z = argv[1];
sl@0:   for(i=0; *z && i<=pIndex->nColumn; i++){
sl@0:     v = 0;
sl@0:     while( (c=z[0])>='0' && c<='9' ){
sl@0:       v = v*10 + c - '0';
sl@0:       z++;
sl@0:     }
sl@0:     pIndex->aiRowEst[i] = v;
sl@0:     if( *z==' ' ) z++;
sl@0:   }
sl@0:   return 0;
sl@0: }
sl@0: 
sl@0: /*
sl@0: ** Load the content of the sqlite_stat1 table into the index hash tables.
sl@0: */
sl@0: int sqlite3AnalysisLoad(sqlite3 *db, int iDb){
sl@0:   analysisInfo sInfo;
sl@0:   HashElem *i;
sl@0:   char *zSql;
sl@0:   int rc;
sl@0: 
sl@0:   assert( iDb>=0 && iDb<db->nDb );
sl@0:   assert( db->aDb[iDb].pBt!=0 );
sl@0:   assert( sqlite3BtreeHoldsMutex(db->aDb[iDb].pBt) );
sl@0: 
sl@0:   /* Clear any prior statistics */
sl@0:   for(i=sqliteHashFirst(&db->aDb[iDb].pSchema->idxHash);i;i=sqliteHashNext(i)){
sl@0:     Index *pIdx = sqliteHashData(i);
sl@0:     sqlite3DefaultRowEst(pIdx);
sl@0:   }
sl@0: 
sl@0:   /* Check to make sure the sqlite_stat1 table existss */
sl@0:   sInfo.db = db;
sl@0:   sInfo.zDatabase = db->aDb[iDb].zName;
sl@0:   if( sqlite3FindTable(db, "sqlite_stat1", sInfo.zDatabase)==0 ){
sl@0:      return SQLITE_ERROR;
sl@0:   }
sl@0: 
sl@0: 
sl@0:   /* Load new statistics out of the sqlite_stat1 table */
sl@0:   zSql = sqlite3MPrintf(db, "SELECT idx, stat FROM %Q.sqlite_stat1",
sl@0:                         sInfo.zDatabase);
sl@0:   (void)sqlite3SafetyOff(db);
sl@0:   rc = sqlite3_exec(db, zSql, analysisLoader, &sInfo, 0);
sl@0:   (void)sqlite3SafetyOn(db);
sl@0:   sqlite3DbFree(db, zSql);
sl@0:   return rc;
sl@0: }
sl@0: 
sl@0: 
sl@0: #endif /* SQLITE_OMIT_ANALYZE */