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