1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/os/persistentdata/persistentstorage/sql/SQLite/analyze.c Fri Jun 15 03:10:57 2012 +0200
1.3 @@ -0,0 +1,425 @@
1.4 +/*
1.5 +** 2005 July 8
1.6 +**
1.7 +** The author disclaims copyright to this source code. In place of
1.8 +** a legal notice, here is a blessing:
1.9 +**
1.10 +** May you do good and not evil.
1.11 +** May you find forgiveness for yourself and forgive others.
1.12 +** May you share freely, never taking more than you give.
1.13 +**
1.14 +*************************************************************************
1.15 +** This file contains code associated with the ANALYZE command.
1.16 +**
1.17 +** @(#) $Id: analyze.c,v 1.43 2008/07/28 19:34:53 drh Exp $
1.18 +*/
1.19 +#ifndef SQLITE_OMIT_ANALYZE
1.20 +#include "sqliteInt.h"
1.21 +
1.22 +/*
1.23 +** This routine generates code that opens the sqlite_stat1 table on cursor
1.24 +** iStatCur.
1.25 +**
1.26 +** If the sqlite_stat1 tables does not previously exist, it is created.
1.27 +** If it does previously exist, all entires associated with table zWhere
1.28 +** are removed. If zWhere==0 then all entries are removed.
1.29 +*/
1.30 +static void openStatTable(
1.31 + Parse *pParse, /* Parsing context */
1.32 + int iDb, /* The database we are looking in */
1.33 + int iStatCur, /* Open the sqlite_stat1 table on this cursor */
1.34 + const char *zWhere /* Delete entries associated with this table */
1.35 +){
1.36 + sqlite3 *db = pParse->db;
1.37 + Db *pDb;
1.38 + int iRootPage;
1.39 + int createStat1 = 0;
1.40 + Table *pStat;
1.41 + Vdbe *v = sqlite3GetVdbe(pParse);
1.42 +
1.43 + if( v==0 ) return;
1.44 + assert( sqlite3BtreeHoldsAllMutexes(db) );
1.45 + assert( sqlite3VdbeDb(v)==db );
1.46 + pDb = &db->aDb[iDb];
1.47 + if( (pStat = sqlite3FindTable(db, "sqlite_stat1", pDb->zName))==0 ){
1.48 + /* The sqlite_stat1 tables does not exist. Create it.
1.49 + ** Note that a side-effect of the CREATE TABLE statement is to leave
1.50 + ** the rootpage of the new table in register pParse->regRoot. This is
1.51 + ** important because the OpenWrite opcode below will be needing it. */
1.52 + sqlite3NestedParse(pParse,
1.53 + "CREATE TABLE %Q.sqlite_stat1(tbl,idx,stat)",
1.54 + pDb->zName
1.55 + );
1.56 + iRootPage = pParse->regRoot;
1.57 + createStat1 = 1; /* Cause rootpage to be taken from top of stack */
1.58 + }else if( zWhere ){
1.59 + /* The sqlite_stat1 table exists. Delete all entries associated with
1.60 + ** the table zWhere. */
1.61 + sqlite3NestedParse(pParse,
1.62 + "DELETE FROM %Q.sqlite_stat1 WHERE tbl=%Q",
1.63 + pDb->zName, zWhere
1.64 + );
1.65 + iRootPage = pStat->tnum;
1.66 + }else{
1.67 + /* The sqlite_stat1 table already exists. Delete all rows. */
1.68 + iRootPage = pStat->tnum;
1.69 + sqlite3VdbeAddOp2(v, OP_Clear, pStat->tnum, iDb);
1.70 + }
1.71 +
1.72 + /* Open the sqlite_stat1 table for writing. Unless it was created
1.73 + ** by this vdbe program, lock it for writing at the shared-cache level.
1.74 + ** If this vdbe did create the sqlite_stat1 table, then it must have
1.75 + ** already obtained a schema-lock, making the write-lock redundant.
1.76 + */
1.77 + if( !createStat1 ){
1.78 + sqlite3TableLock(pParse, iDb, iRootPage, 1, "sqlite_stat1");
1.79 + }
1.80 + sqlite3VdbeAddOp2(v, OP_SetNumColumns, 0, 3);
1.81 + sqlite3VdbeAddOp3(v, OP_OpenWrite, iStatCur, iRootPage, iDb);
1.82 + sqlite3VdbeChangeP5(v, createStat1);
1.83 +}
1.84 +
1.85 +/*
1.86 +** Generate code to do an analysis of all indices associated with
1.87 +** a single table.
1.88 +*/
1.89 +static void analyzeOneTable(
1.90 + Parse *pParse, /* Parser context */
1.91 + Table *pTab, /* Table whose indices are to be analyzed */
1.92 + int iStatCur, /* Cursor that writes to the sqlite_stat1 table */
1.93 + int iMem /* Available memory locations begin here */
1.94 +){
1.95 + Index *pIdx; /* An index to being analyzed */
1.96 + int iIdxCur; /* Cursor number for index being analyzed */
1.97 + int nCol; /* Number of columns in the index */
1.98 + Vdbe *v; /* The virtual machine being built up */
1.99 + int i; /* Loop counter */
1.100 + int topOfLoop; /* The top of the loop */
1.101 + int endOfLoop; /* The end of the loop */
1.102 + int addr; /* The address of an instruction */
1.103 + int iDb; /* Index of database containing pTab */
1.104 +
1.105 + v = sqlite3GetVdbe(pParse);
1.106 + if( v==0 || pTab==0 || pTab->pIndex==0 ){
1.107 + /* Do no analysis for tables that have no indices */
1.108 + return;
1.109 + }
1.110 + assert( sqlite3BtreeHoldsAllMutexes(pParse->db) );
1.111 + iDb = sqlite3SchemaToIndex(pParse->db, pTab->pSchema);
1.112 + assert( iDb>=0 );
1.113 +#ifndef SQLITE_OMIT_AUTHORIZATION
1.114 + if( sqlite3AuthCheck(pParse, SQLITE_ANALYZE, pTab->zName, 0,
1.115 + pParse->db->aDb[iDb].zName ) ){
1.116 + return;
1.117 + }
1.118 +#endif
1.119 +
1.120 + /* Establish a read-lock on the table at the shared-cache level. */
1.121 + sqlite3TableLock(pParse, iDb, pTab->tnum, 0, pTab->zName);
1.122 +
1.123 + iIdxCur = pParse->nTab;
1.124 + for(pIdx=pTab->pIndex; pIdx; pIdx=pIdx->pNext){
1.125 + KeyInfo *pKey = sqlite3IndexKeyinfo(pParse, pIdx);
1.126 + int regFields; /* Register block for building records */
1.127 + int regRec; /* Register holding completed record */
1.128 + int regTemp; /* Temporary use register */
1.129 + int regCol; /* Content of a column from the table being analyzed */
1.130 + int regRowid; /* Rowid for the inserted record */
1.131 + int regF2;
1.132 +
1.133 + /* Open a cursor to the index to be analyzed
1.134 + */
1.135 + assert( iDb==sqlite3SchemaToIndex(pParse->db, pIdx->pSchema) );
1.136 + nCol = pIdx->nColumn;
1.137 + sqlite3VdbeAddOp2(v, OP_SetNumColumns, 0, nCol+1);
1.138 + sqlite3VdbeAddOp4(v, OP_OpenRead, iIdxCur, pIdx->tnum, iDb,
1.139 + (char *)pKey, P4_KEYINFO_HANDOFF);
1.140 + VdbeComment((v, "%s", pIdx->zName));
1.141 + regFields = iMem+nCol*2;
1.142 + regTemp = regRowid = regCol = regFields+3;
1.143 + regRec = regCol+1;
1.144 + if( regRec>pParse->nMem ){
1.145 + pParse->nMem = regRec;
1.146 + }
1.147 +
1.148 + /* Memory cells are used as follows:
1.149 + **
1.150 + ** mem[iMem]: The total number of rows in the table.
1.151 + ** mem[iMem+1]: Number of distinct values in column 1
1.152 + ** ...
1.153 + ** mem[iMem+nCol]: Number of distinct values in column N
1.154 + ** mem[iMem+nCol+1] Last observed value of column 1
1.155 + ** ...
1.156 + ** mem[iMem+nCol+nCol]: Last observed value of column N
1.157 + **
1.158 + ** Cells iMem through iMem+nCol are initialized to 0. The others
1.159 + ** are initialized to NULL.
1.160 + */
1.161 + for(i=0; i<=nCol; i++){
1.162 + sqlite3VdbeAddOp2(v, OP_Integer, 0, iMem+i);
1.163 + }
1.164 + for(i=0; i<nCol; i++){
1.165 + sqlite3VdbeAddOp2(v, OP_Null, 0, iMem+nCol+i+1);
1.166 + }
1.167 +
1.168 + /* Do the analysis.
1.169 + */
1.170 + endOfLoop = sqlite3VdbeMakeLabel(v);
1.171 + sqlite3VdbeAddOp2(v, OP_Rewind, iIdxCur, endOfLoop);
1.172 + topOfLoop = sqlite3VdbeCurrentAddr(v);
1.173 + sqlite3VdbeAddOp2(v, OP_AddImm, iMem, 1);
1.174 + for(i=0; i<nCol; i++){
1.175 + sqlite3VdbeAddOp3(v, OP_Column, iIdxCur, i, regCol);
1.176 + sqlite3VdbeAddOp3(v, OP_Ne, regCol, 0, iMem+nCol+i+1);
1.177 + /**** TODO: add collating sequence *****/
1.178 + sqlite3VdbeChangeP5(v, SQLITE_JUMPIFNULL);
1.179 + }
1.180 + sqlite3VdbeAddOp2(v, OP_Goto, 0, endOfLoop);
1.181 + for(i=0; i<nCol; i++){
1.182 + sqlite3VdbeJumpHere(v, topOfLoop + 2*(i + 1));
1.183 + sqlite3VdbeAddOp2(v, OP_AddImm, iMem+i+1, 1);
1.184 + sqlite3VdbeAddOp3(v, OP_Column, iIdxCur, i, iMem+nCol+i+1);
1.185 + }
1.186 + sqlite3VdbeResolveLabel(v, endOfLoop);
1.187 + sqlite3VdbeAddOp2(v, OP_Next, iIdxCur, topOfLoop);
1.188 + sqlite3VdbeAddOp1(v, OP_Close, iIdxCur);
1.189 +
1.190 + /* Store the results.
1.191 + **
1.192 + ** The result is a single row of the sqlite_stat1 table. The first
1.193 + ** two columns are the names of the table and index. The third column
1.194 + ** is a string composed of a list of integer statistics about the
1.195 + ** index. The first integer in the list is the total number of entires
1.196 + ** in the index. There is one additional integer in the list for each
1.197 + ** column of the table. This additional integer is a guess of how many
1.198 + ** rows of the table the index will select. If D is the count of distinct
1.199 + ** values and K is the total number of rows, then the integer is computed
1.200 + ** as:
1.201 + **
1.202 + ** I = (K+D-1)/D
1.203 + **
1.204 + ** If K==0 then no entry is made into the sqlite_stat1 table.
1.205 + ** If K>0 then it is always the case the D>0 so division by zero
1.206 + ** is never possible.
1.207 + */
1.208 + addr = sqlite3VdbeAddOp1(v, OP_IfNot, iMem);
1.209 + sqlite3VdbeAddOp4(v, OP_String8, 0, regFields, 0, pTab->zName, 0);
1.210 + sqlite3VdbeAddOp4(v, OP_String8, 0, regFields+1, 0, pIdx->zName, 0);
1.211 + regF2 = regFields+2;
1.212 + sqlite3VdbeAddOp2(v, OP_SCopy, iMem, regF2);
1.213 + for(i=0; i<nCol; i++){
1.214 + sqlite3VdbeAddOp4(v, OP_String8, 0, regTemp, 0, " ", 0);
1.215 + sqlite3VdbeAddOp3(v, OP_Concat, regTemp, regF2, regF2);
1.216 + sqlite3VdbeAddOp3(v, OP_Add, iMem, iMem+i+1, regTemp);
1.217 + sqlite3VdbeAddOp2(v, OP_AddImm, regTemp, -1);
1.218 + sqlite3VdbeAddOp3(v, OP_Divide, iMem+i+1, regTemp, regTemp);
1.219 + sqlite3VdbeAddOp1(v, OP_ToInt, regTemp);
1.220 + sqlite3VdbeAddOp3(v, OP_Concat, regTemp, regF2, regF2);
1.221 + }
1.222 + sqlite3VdbeAddOp4(v, OP_MakeRecord, regFields, 3, regRec, "aaa", 0);
1.223 + sqlite3VdbeAddOp2(v, OP_NewRowid, iStatCur, regRowid);
1.224 + sqlite3VdbeAddOp3(v, OP_Insert, iStatCur, regRec, regRowid);
1.225 + sqlite3VdbeChangeP5(v, OPFLAG_APPEND);
1.226 + sqlite3VdbeJumpHere(v, addr);
1.227 + }
1.228 +}
1.229 +
1.230 +/*
1.231 +** Generate code that will cause the most recent index analysis to
1.232 +** be laoded into internal hash tables where is can be used.
1.233 +*/
1.234 +static void loadAnalysis(Parse *pParse, int iDb){
1.235 + Vdbe *v = sqlite3GetVdbe(pParse);
1.236 + if( v ){
1.237 + sqlite3VdbeAddOp1(v, OP_LoadAnalysis, iDb);
1.238 + }
1.239 +}
1.240 +
1.241 +/*
1.242 +** Generate code that will do an analysis of an entire database
1.243 +*/
1.244 +static void analyzeDatabase(Parse *pParse, int iDb){
1.245 + sqlite3 *db = pParse->db;
1.246 + Schema *pSchema = db->aDb[iDb].pSchema; /* Schema of database iDb */
1.247 + HashElem *k;
1.248 + int iStatCur;
1.249 + int iMem;
1.250 +
1.251 + sqlite3BeginWriteOperation(pParse, 0, iDb);
1.252 + iStatCur = pParse->nTab++;
1.253 + openStatTable(pParse, iDb, iStatCur, 0);
1.254 + iMem = pParse->nMem+1;
1.255 + for(k=sqliteHashFirst(&pSchema->tblHash); k; k=sqliteHashNext(k)){
1.256 + Table *pTab = (Table*)sqliteHashData(k);
1.257 + analyzeOneTable(pParse, pTab, iStatCur, iMem);
1.258 + }
1.259 + loadAnalysis(pParse, iDb);
1.260 +}
1.261 +
1.262 +/*
1.263 +** Generate code that will do an analysis of a single table in
1.264 +** a database.
1.265 +*/
1.266 +static void analyzeTable(Parse *pParse, Table *pTab){
1.267 + int iDb;
1.268 + int iStatCur;
1.269 +
1.270 + assert( pTab!=0 );
1.271 + assert( sqlite3BtreeHoldsAllMutexes(pParse->db) );
1.272 + iDb = sqlite3SchemaToIndex(pParse->db, pTab->pSchema);
1.273 + sqlite3BeginWriteOperation(pParse, 0, iDb);
1.274 + iStatCur = pParse->nTab++;
1.275 + openStatTable(pParse, iDb, iStatCur, pTab->zName);
1.276 + analyzeOneTable(pParse, pTab, iStatCur, pParse->nMem+1);
1.277 + loadAnalysis(pParse, iDb);
1.278 +}
1.279 +
1.280 +/*
1.281 +** Generate code for the ANALYZE command. The parser calls this routine
1.282 +** when it recognizes an ANALYZE command.
1.283 +**
1.284 +** ANALYZE -- 1
1.285 +** ANALYZE <database> -- 2
1.286 +** ANALYZE ?<database>.?<tablename> -- 3
1.287 +**
1.288 +** Form 1 causes all indices in all attached databases to be analyzed.
1.289 +** Form 2 analyzes all indices the single database named.
1.290 +** Form 3 analyzes all indices associated with the named table.
1.291 +*/
1.292 +void sqlite3Analyze(Parse *pParse, Token *pName1, Token *pName2){
1.293 + sqlite3 *db = pParse->db;
1.294 + int iDb;
1.295 + int i;
1.296 + char *z, *zDb;
1.297 + Table *pTab;
1.298 + Token *pTableName;
1.299 +
1.300 + /* Read the database schema. If an error occurs, leave an error message
1.301 + ** and code in pParse and return NULL. */
1.302 + assert( sqlite3BtreeHoldsAllMutexes(pParse->db) );
1.303 + if( SQLITE_OK!=sqlite3ReadSchema(pParse) ){
1.304 + return;
1.305 + }
1.306 +
1.307 + if( pName1==0 ){
1.308 + /* Form 1: Analyze everything */
1.309 + for(i=0; i<db->nDb; i++){
1.310 + if( i==1 ) continue; /* Do not analyze the TEMP database */
1.311 + analyzeDatabase(pParse, i);
1.312 + }
1.313 + }else if( pName2==0 || pName2->n==0 ){
1.314 + /* Form 2: Analyze the database or table named */
1.315 + iDb = sqlite3FindDb(db, pName1);
1.316 + if( iDb>=0 ){
1.317 + analyzeDatabase(pParse, iDb);
1.318 + }else{
1.319 + z = sqlite3NameFromToken(db, pName1);
1.320 + if( z ){
1.321 + pTab = sqlite3LocateTable(pParse, 0, z, 0);
1.322 + sqlite3DbFree(db, z);
1.323 + if( pTab ){
1.324 + analyzeTable(pParse, pTab);
1.325 + }
1.326 + }
1.327 + }
1.328 + }else{
1.329 + /* Form 3: Analyze the fully qualified table name */
1.330 + iDb = sqlite3TwoPartName(pParse, pName1, pName2, &pTableName);
1.331 + if( iDb>=0 ){
1.332 + zDb = db->aDb[iDb].zName;
1.333 + z = sqlite3NameFromToken(db, pTableName);
1.334 + if( z ){
1.335 + pTab = sqlite3LocateTable(pParse, 0, z, zDb);
1.336 + sqlite3DbFree(db, z);
1.337 + if( pTab ){
1.338 + analyzeTable(pParse, pTab);
1.339 + }
1.340 + }
1.341 + }
1.342 + }
1.343 +}
1.344 +
1.345 +/*
1.346 +** Used to pass information from the analyzer reader through to the
1.347 +** callback routine.
1.348 +*/
1.349 +typedef struct analysisInfo analysisInfo;
1.350 +struct analysisInfo {
1.351 + sqlite3 *db;
1.352 + const char *zDatabase;
1.353 +};
1.354 +
1.355 +/*
1.356 +** This callback is invoked once for each index when reading the
1.357 +** sqlite_stat1 table.
1.358 +**
1.359 +** argv[0] = name of the index
1.360 +** argv[1] = results of analysis - on integer for each column
1.361 +*/
1.362 +static int analysisLoader(void *pData, int argc, char **argv, char **azNotUsed){
1.363 + analysisInfo *pInfo = (analysisInfo*)pData;
1.364 + Index *pIndex;
1.365 + int i, c;
1.366 + unsigned int v;
1.367 + const char *z;
1.368 +
1.369 + assert( argc==2 );
1.370 + if( argv==0 || argv[0]==0 || argv[1]==0 ){
1.371 + return 0;
1.372 + }
1.373 + pIndex = sqlite3FindIndex(pInfo->db, argv[0], pInfo->zDatabase);
1.374 + if( pIndex==0 ){
1.375 + return 0;
1.376 + }
1.377 + z = argv[1];
1.378 + for(i=0; *z && i<=pIndex->nColumn; i++){
1.379 + v = 0;
1.380 + while( (c=z[0])>='0' && c<='9' ){
1.381 + v = v*10 + c - '0';
1.382 + z++;
1.383 + }
1.384 + pIndex->aiRowEst[i] = v;
1.385 + if( *z==' ' ) z++;
1.386 + }
1.387 + return 0;
1.388 +}
1.389 +
1.390 +/*
1.391 +** Load the content of the sqlite_stat1 table into the index hash tables.
1.392 +*/
1.393 +int sqlite3AnalysisLoad(sqlite3 *db, int iDb){
1.394 + analysisInfo sInfo;
1.395 + HashElem *i;
1.396 + char *zSql;
1.397 + int rc;
1.398 +
1.399 + assert( iDb>=0 && iDb<db->nDb );
1.400 + assert( db->aDb[iDb].pBt!=0 );
1.401 + assert( sqlite3BtreeHoldsMutex(db->aDb[iDb].pBt) );
1.402 +
1.403 + /* Clear any prior statistics */
1.404 + for(i=sqliteHashFirst(&db->aDb[iDb].pSchema->idxHash);i;i=sqliteHashNext(i)){
1.405 + Index *pIdx = sqliteHashData(i);
1.406 + sqlite3DefaultRowEst(pIdx);
1.407 + }
1.408 +
1.409 + /* Check to make sure the sqlite_stat1 table existss */
1.410 + sInfo.db = db;
1.411 + sInfo.zDatabase = db->aDb[iDb].zName;
1.412 + if( sqlite3FindTable(db, "sqlite_stat1", sInfo.zDatabase)==0 ){
1.413 + return SQLITE_ERROR;
1.414 + }
1.415 +
1.416 +
1.417 + /* Load new statistics out of the sqlite_stat1 table */
1.418 + zSql = sqlite3MPrintf(db, "SELECT idx, stat FROM %Q.sqlite_stat1",
1.419 + sInfo.zDatabase);
1.420 + (void)sqlite3SafetyOff(db);
1.421 + rc = sqlite3_exec(db, zSql, analysisLoader, &sInfo, 0);
1.422 + (void)sqlite3SafetyOn(db);
1.423 + sqlite3DbFree(db, zSql);
1.424 + return rc;
1.425 +}
1.426 +
1.427 +
1.428 +#endif /* SQLITE_OMIT_ANALYZE */