ext/misc/btreeinfo.c

   1 /*
   2 ** 2017-10-24
   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 **
  13 ** This file contains an implementation of the "sqlite_btreeinfo" virtual table.
  14 **
  15 ** The sqlite_btreeinfo virtual table is a read-only eponymous-only virtual
  16 ** table that shows information about all btrees in an SQLite database file.
  17 ** The schema is like this:
  18 **
  19 ** CREATE TABLE sqlite_btreeinfo(
  20 **    type TEXT,                   -- "table" or "index"
  21 **    name TEXT,                   -- Name of table or index for this btree.
  22 **    tbl_name TEXT,               -- Associated table
  23 **    rootpage INT,                -- The root page of the btree
  24 **    sql TEXT,                    -- SQL for this btree - from sqlite_master
  25 **    hasRowid BOOLEAN,            -- True if the btree has a rowid
  26 **    nEntry INT,                  -- Estimated number of enteries
  27 **    nPage INT,                   -- Estimated number of pages
  28 **    depth INT,                   -- Depth of the btree
  29 **    szPage INT,                  -- Size of each page in bytes
  30 **    zSchema TEXT HIDDEN          -- The schema to which this btree belongs
  31 ** );
  32 **
  33 ** The first 5 fields are taken directly from the sqlite_master table.
  34 ** Considering only the first 5 fields, the only difference between
  35 ** this virtual table and the sqlite_master table is that this virtual
  36 ** table omits all entries that have a 0 or NULL rowid - in other words
  37 ** it omits triggers and views.
  38 **
  39 ** The value added by this table comes in the next 5 fields.
  40 **
  41 ** Note that nEntry and nPage are *estimated*.  They are computed doing
  42 ** a single search from the root to a leaf, counting the number of cells
  43 ** at each level, and assuming that unvisited pages have a similar number
  44 ** of cells.
  45 **
  46 ** The sqlite_dbpage virtual table must be available for this virtual table
  47 ** to operate.
  48 **
  49 ** USAGE EXAMPLES:
  50 **
  51 ** Show the table btrees in a schema order with the tables with the most
  52 ** rows occuring first:
  53 **
  54 **      SELECT name, nEntry
  55 **        FROM sqlite_btreeinfo
  56 **       WHERE type='table'
  57 **       ORDER BY nEntry DESC, name;
  58 **
  59 ** Show the names of all WITHOUT ROWID tables:
  60 **
  61 **      SELECT name FROM sqlite_btreeinfo
  62 **       WHERE type='table' AND NOT hasRowid;
  63 */
  64 #if !defined(SQLITEINT_H)
  65 #include "sqlite3ext.h"
  66 #endif
  67 SQLITE_EXTENSION_INIT1
  68 #include <string.h>
  69 #include <assert.h>
  70
  71 /* Columns available in this virtual table */
  72 #define BINFO_COLUMN_TYPE         0
  73 #define BINFO_COLUMN_NAME         1
  74 #define BINFO_COLUMN_TBL_NAME     2
  75 #define BINFO_COLUMN_ROOTPAGE     3
  76 #define BINFO_COLUMN_SQL          4
  77 #define BINFO_COLUMN_HASROWID     5
  78 #define BINFO_COLUMN_NENTRY       6
  79 #define BINFO_COLUMN_NPAGE        7
  80 #define BINFO_COLUMN_DEPTH        8
  81 #define BINFO_COLUMN_SZPAGE       9
  82 #define BINFO_COLUMN_SCHEMA      10
  83
  84 /* Forward declarations */
  85 typedef struct BinfoTable BinfoTable;
  86 typedef struct BinfoCursor BinfoCursor;
  87
  88 /* A cursor for the sqlite_btreeinfo table */
  89 struct BinfoCursor {
  90   sqlite3_vtab_cursor base;       /* Base class.  Must be first */
  91   sqlite3_stmt *pStmt;            /* Query against sqlite_master */
  92   int rc;                         /* Result of previous sqlite_step() call */
  93   int hasRowid;                   /* hasRowid value.  Negative if unknown. */
  94   sqlite3_int64 nEntry;           /* nEntry value */
  95   int nPage;                      /* nPage value */
  96   int depth;                      /* depth value */
  97   int szPage;                     /* size of a btree page.  0 if unknown */
  98   char *zSchema;                  /* Schema being interrogated */
  99 };
 100
 101 /* The sqlite_btreeinfo table */
 102 struct BinfoTable {
 103   sqlite3_vtab base;              /* Base class.  Must be first */
 104   sqlite3 *db;                    /* The databse connection */
 105 };
 106
 107 /*
 108 ** Connect to the sqlite_btreeinfo virtual table.
 109 */
 110 static int binfoConnect(
 111   sqlite3 *db,
 112   void *pAux,
 113   int argc, const char *const*argv,
 114   sqlite3_vtab **ppVtab,
 115   char **pzErr
 116 ){
 117   BinfoTable *pTab = 0;
 118   int rc = SQLITE_OK;
 119   rc = sqlite3_declare_vtab(db,
 120       "CREATE TABLE x(\n"
 121       " type TEXT,\n"
 122       " name TEXT,\n"
 123       " tbl_name TEXT,\n"
 124       " rootpage INT,\n"
 125       " sql TEXT,\n"
 126       " hasRowid BOOLEAN,\n"
 127       " nEntry INT,\n"
 128       " nPage INT,\n"
 129       " depth INT,\n"
 130       " szPage INT,\n"
 131       " zSchema TEXT HIDDEN\n"
 132       ")");
 133   if( rc==SQLITE_OK ){
 134     pTab = (BinfoTable *)sqlite3_malloc64(sizeof(BinfoTable));
 135     if( pTab==0 ) rc = SQLITE_NOMEM;
 136   }
 137   assert( rc==SQLITE_OK || pTab==0 );
 138   if( pTab ){
 139     pTab->db = db;
 140   }
 141   *ppVtab = (sqlite3_vtab*)pTab;
 142   return rc;
 143 }
 144
 145 /*
 146 ** Disconnect from or destroy a btreeinfo virtual table.
 147 */
 148 static int binfoDisconnect(sqlite3_vtab *pVtab){
 149   sqlite3_free(pVtab);
 150   return SQLITE_OK;
 151 }
 152
 153 /*
 154 ** idxNum:
 155 **
 156 **     0     Use "main" for the schema
 157 **     1     Schema identified by parameter ?1
 158 */
 159 static int binfoBestIndex(sqlite3_vtab *tab, sqlite3_index_info *pIdxInfo){
 160   int i;
 161   pIdxInfo->estimatedCost = 10000.0;  /* Cost estimate */
 162   pIdxInfo->estimatedRows = 100;
 163   for(i=0; i<pIdxInfo->nConstraint; i++){
 164     struct sqlite3_index_constraint *p = &pIdxInfo->aConstraint[i];
 165     if( p->usable
 166      && p->iColumn==BINFO_COLUMN_SCHEMA
 167      && p->op==SQLITE_INDEX_CONSTRAINT_EQ
 168     ){
 169       pIdxInfo->estimatedCost = 1000.0;
 170       pIdxInfo->idxNum = 1;
 171       pIdxInfo->aConstraintUsage[i].argvIndex = 1;
 172       pIdxInfo->aConstraintUsage[i].omit = 1;
 173       break;
 174     }
 175   }
 176   return SQLITE_OK;
 177 }
 178
 179 /*
 180 ** Open a new btreeinfo cursor.
 181 */
 182 static int binfoOpen(sqlite3_vtab *pVTab, sqlite3_vtab_cursor **ppCursor){
 183   BinfoCursor *pCsr;
 184
 185   pCsr = (BinfoCursor *)sqlite3_malloc64(sizeof(BinfoCursor));
 186   if( pCsr==0 ){
 187     return SQLITE_NOMEM;
 188   }else{
 189     memset(pCsr, 0, sizeof(BinfoCursor));
 190     pCsr->base.pVtab = pVTab;
 191   }
 192
 193   *ppCursor = (sqlite3_vtab_cursor *)pCsr;
 194   return SQLITE_OK;
 195 }
 196
 197 /*
 198 ** Close a btreeinfo cursor.
 199 */
 200 static int binfoClose(sqlite3_vtab_cursor *pCursor){
 201   BinfoCursor *pCsr = (BinfoCursor *)pCursor;
 202   sqlite3_finalize(pCsr->pStmt);
 203   sqlite3_free(pCsr->zSchema);
 204   sqlite3_free(pCsr);
 205   return SQLITE_OK;
 206 }
 207
 208 /*
 209 ** Move a btreeinfo cursor to the next entry in the file.
 210 */
 211 static int binfoNext(sqlite3_vtab_cursor *pCursor){
 212   BinfoCursor *pCsr = (BinfoCursor *)pCursor;
 213   pCsr->rc = sqlite3_step(pCsr->pStmt);
 214   pCsr->hasRowid = -1;
 215   return pCsr->rc==SQLITE_ERROR ? SQLITE_ERROR : SQLITE_OK;
 216 }
 217
 218 /* We have reached EOF if previous sqlite3_step() returned
 219 ** anything other than SQLITE_ROW;
 220 */
 221 static int binfoEof(sqlite3_vtab_cursor *pCursor){
 222   BinfoCursor *pCsr = (BinfoCursor *)pCursor;
 223   return pCsr->rc!=SQLITE_ROW;
 224 }
 225
 226 /* Position a cursor back to the beginning.
 227 */
 228 static int binfoFilter(
 229   sqlite3_vtab_cursor *pCursor,
 230   int idxNum, const char *idxStr,
 231   int argc, sqlite3_value **argv
 232 ){
 233   BinfoCursor *pCsr = (BinfoCursor *)pCursor;
 234   BinfoTable *pTab = (BinfoTable *)pCursor->pVtab;
 235   char *zSql;
 236   int rc;
 237
 238   sqlite3_free(pCsr->zSchema);
 239   if( idxNum==1 && sqlite3_value_type(argv[0])!=SQLITE_NULL ){
 240     pCsr->zSchema = sqlite3_mprintf("%s", sqlite3_value_text(argv[0]));
 241   }else{
 242     pCsr->zSchema = sqlite3_mprintf("main");
 243   }
 244   zSql = sqlite3_mprintf(
 245       "SELECT 0, 'table','sqlite_master','sqlite_master',1,NULL "
 246       "UNION ALL "
 247       "SELECT rowid, type, name, tbl_name, rootpage, sql"
 248       " FROM \"%w\".sqlite_master WHERE rootpage>=1",
 249        pCsr->zSchema);
 250   sqlite3_finalize(pCsr->pStmt);
 251   pCsr->pStmt = 0;
 252   pCsr->hasRowid = -1;
 253   rc = sqlite3_prepare_v2(pTab->db, zSql, -1, &pCsr->pStmt, 0);
 254   sqlite3_free(zSql);
 255   if( rc==SQLITE_OK ){
 256     rc = binfoNext(pCursor);
 257   }
 258   return rc;
 259 }
 260
 261 /* Decode big-endian integers */
 262 static unsigned int get_uint16(unsigned char *a){
 263   return (a[0]<<8)|a[1];
 264 }
 265 static unsigned int get_uint32(unsigned char *a){
 266   return (a[0]<<24)|(a[1]<<16)|(a[2]<<8)|a[3];
 267 }
 268
 269 /* Examine the b-tree rooted at pgno and estimate its size.
 270 ** Return non-zero if anything goes wrong.
 271 */
 272 static int binfoCompute(sqlite3 *db, int pgno, BinfoCursor *pCsr){
 273   sqlite3_int64 nEntry = 1;
 274   int nPage = 1;
 275   unsigned char *aData;
 276   sqlite3_stmt *pStmt = 0;
 277   int rc = SQLITE_OK;
 278   int pgsz = 0;
 279   int nCell;
 280   int iCell;
 281
 282   rc = sqlite3_prepare_v2(db,
 283            "SELECT data FROM sqlite_dbpage('main') WHERE pgno=?1", -1,
 284            &pStmt, 0);
 285   if( rc ) return rc;
 286   pCsr->depth = 1;
 287   while(1){
 288     sqlite3_bind_int(pStmt, 1, pgno);
 289     rc = sqlite3_step(pStmt);
 290     if( rc!=SQLITE_ROW ){
 291       rc = SQLITE_ERROR;
 292       break;
 293     }
 294     pCsr->szPage = pgsz = sqlite3_column_bytes(pStmt, 0);
 295     aData = (unsigned char*)sqlite3_column_blob(pStmt, 0);
 296     if( aData==0 ){
 297       rc = SQLITE_NOMEM;
 298       break;
 299     }
 300     if( pgno==1 ){
 301       aData += 100;
 302       pgsz -= 100;
 303     }
 304     pCsr->hasRowid = aData[0]!=2 && aData[0]!=10;
 305     nCell = get_uint16(aData+3);
 306     nEntry *= (nCell+1);
 307     if( aData[0]==10 || aData[0]==13 ) break;
 308     nPage *= (nCell+1);
 309     if( nCell<=1 ){
 310       pgno = get_uint32(aData+8);
 311     }else{
 312       iCell = get_uint16(aData+12+2*(nCell/2));
 313       if( pgno==1 ) iCell -= 100;
 314       if( iCell<=12 || iCell>=pgsz-4 ){
 315         rc = SQLITE_CORRUPT;
 316         break;
 317       }
 318       pgno = get_uint32(aData+iCell);
 319     }
 320     pCsr->depth++;
 321     sqlite3_reset(pStmt);
 322   }
 323   sqlite3_finalize(pStmt);
 324   pCsr->nPage = nPage;
 325   pCsr->nEntry = nEntry;
 326   if( rc==SQLITE_ROW ) rc = SQLITE_OK;
 327   return rc;
 328 }
 329
 330 /* Return a column for the sqlite_btreeinfo table */
 331 static int binfoColumn(
 332   sqlite3_vtab_cursor *pCursor,
 333   sqlite3_context *ctx,
 334   int i
 335 ){
 336   BinfoCursor *pCsr = (BinfoCursor *)pCursor;
 337   if( i>=BINFO_COLUMN_HASROWID && i<=BINFO_COLUMN_SZPAGE && pCsr->hasRowid<0 ){
 338     int pgno = sqlite3_column_int(pCsr->pStmt, BINFO_COLUMN_ROOTPAGE+1);
 339     sqlite3 *db = sqlite3_context_db_handle(ctx);
 340     int rc = binfoCompute(db, pgno, pCsr);
 341     if( rc ){
 342       pCursor->pVtab->zErrMsg = sqlite3_mprintf("%s", sqlite3_errmsg(db));
 343       return SQLITE_ERROR;
 344     }
 345   }
 346   switch( i ){
 347     case BINFO_COLUMN_NAME:
 348     case BINFO_COLUMN_TYPE:
 349     case BINFO_COLUMN_TBL_NAME:
 350     case BINFO_COLUMN_ROOTPAGE:
 351     case BINFO_COLUMN_SQL: {
 352       sqlite3_result_value(ctx, sqlite3_column_value(pCsr->pStmt, i+1));
 353       break;
 354     }
 355     case BINFO_COLUMN_HASROWID: {
 356       sqlite3_result_int(ctx, pCsr->hasRowid);
 357       break;
 358     }
 359     case BINFO_COLUMN_NENTRY: {
 360       sqlite3_result_int64(ctx, pCsr->nEntry);
 361       break;
 362     }
 363     case BINFO_COLUMN_NPAGE: {
 364       sqlite3_result_int(ctx, pCsr->nPage);
 365       break;
 366     }
 367     case BINFO_COLUMN_DEPTH: {
 368       sqlite3_result_int(ctx, pCsr->depth);
 369       break;
 370     }
 371     case BINFO_COLUMN_SCHEMA: {
 372       sqlite3_result_text(ctx, pCsr->zSchema, -1, SQLITE_STATIC);
 373       break;
 374     }
 375   }
 376   return SQLITE_OK;
 377 }
 378
 379 /* Return the ROWID for the sqlite_btreeinfo table */
 380 static int binfoRowid(sqlite3_vtab_cursor *pCursor, sqlite_int64 *pRowid){
 381   BinfoCursor *pCsr = (BinfoCursor *)pCursor;
 382   *pRowid = sqlite3_column_int64(pCsr->pStmt, 0);
 383   return SQLITE_OK;
 384 }
 385
 386 /*
 387 ** Invoke this routine to register the "sqlite_btreeinfo" virtual table module
 388 */
 389 int sqlite3BinfoRegister(sqlite3 *db){
 390   static sqlite3_module binfo_module = {
 391     0,                           /* iVersion */
 392     0,                           /* xCreate */
 393     binfoConnect,                /* xConnect */
 394     binfoBestIndex,              /* xBestIndex */
 395     binfoDisconnect,             /* xDisconnect */
 396     0,                           /* xDestroy */
 397     binfoOpen,                   /* xOpen - open a cursor */
 398     binfoClose,                  /* xClose - close a cursor */
 399     binfoFilter,                 /* xFilter - configure scan constraints */
 400     binfoNext,                   /* xNext - advance a cursor */
 401     binfoEof,                    /* xEof - check for end of scan */
 402     binfoColumn,                 /* xColumn - read data */
 403     binfoRowid,                  /* xRowid - read data */
 404     0,                           /* xUpdate */
 405     0,                           /* xBegin */
 406     0,                           /* xSync */
 407     0,                           /* xCommit */
 408     0,                           /* xRollback */
 409     0,                           /* xFindMethod */
 410     0,                           /* xRename */
 411     0,                           /* xSavepoint */
 412     0,                           /* xRelease */
 413     0,                           /* xRollbackTo */
 414   };
 415   return sqlite3_create_module(db, "sqlite_btreeinfo", &binfo_module, 0);
 416 }
 417
 418 #ifdef _WIN32
 419 __declspec(dllexport)
 420 #endif
 421 int sqlite3_btreeinfo_init(
 422   sqlite3 *db,
 423   char **pzErrMsg,
 424   const sqlite3_api_routines *pApi
 425 ){
 426   SQLITE_EXTENSION_INIT2(pApi);
 427   return sqlite3BinfoRegister(db);
 428 }