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