ext/expert/sqlite3expert.c

   1 /*
   2 ** 2017 April 09
   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 #include "sqlite3expert.h"
  14 #include <assert.h>
  15 #include <string.h>
  16 #include <stdio.h>
  17
  18 #if !defined(SQLITE_AMALGAMATION)
  19 #if defined(SQLITE_COVERAGE_TEST) || defined(SQLITE_MUTATION_TEST)
  20 # define SQLITE_OMIT_AUXILIARY_SAFETY_CHECKS 1
  21 #endif
  22 #if defined(SQLITE_OMIT_AUXILIARY_SAFETY_CHECKS)
  23 # define ALWAYS(X)      (1)
  24 # define NEVER(X)       (0)
  25 #elif !defined(NDEBUG)
  26 # define ALWAYS(X)      ((X)?1:(assert(0),0))
  27 # define NEVER(X)       ((X)?(assert(0),1):0)
  28 #else
  29 # define ALWAYS(X)      (X)
  30 # define NEVER(X)       (X)
  31 #endif
  32 #endif /* !defined(SQLITE_AMALGAMATION) */
  33
  34
  35 #ifndef SQLITE_OMIT_VIRTUALTABLE
  36
  37 typedef sqlite3_int64 i64;
  38 typedef sqlite3_uint64 u64;
  39
  40 typedef struct IdxColumn IdxColumn;
  41 typedef struct IdxConstraint IdxConstraint;
  42 typedef struct IdxScan IdxScan;
  43 typedef struct IdxStatement IdxStatement;
  44 typedef struct IdxTable IdxTable;
  45 typedef struct IdxWrite IdxWrite;
  46
  47 #define STRLEN  (int)strlen
  48
  49 /*
  50 ** A temp table name that we assume no user database will actually use.
  51 ** If this assumption proves incorrect triggers on the table with the
  52 ** conflicting name will be ignored.
  53 */
  54 #define UNIQUE_TABLE_NAME "t592690916721053953805701627921227776"
  55
  56 /*
  57 ** A single constraint. Equivalent to either "col = ?" or "col < ?" (or
  58 ** any other type of single-ended range constraint on a column).
  59 **
  60 ** pLink:
  61 **   Used to temporarily link IdxConstraint objects into lists while
  62 **   creating candidate indexes.
  63 */
  64 struct IdxConstraint {
  65   char *zColl;                    /* Collation sequence */
  66   int bRange;                     /* True for range, false for eq */
  67   int iCol;                       /* Constrained table column */
  68   int bFlag;                      /* Used by idxFindCompatible() */
  69   int bDesc;                      /* True if ORDER BY <expr> DESC */
  70   IdxConstraint *pNext;           /* Next constraint in pEq or pRange list */
  71   IdxConstraint *pLink;           /* See above */
  72 };
  73
  74 /*
  75 ** A single scan of a single table.
  76 */
  77 struct IdxScan {
  78   IdxTable *pTab;                 /* Associated table object */
  79   int iDb;                        /* Database containing table zTable */
  80   i64 covering;                   /* Mask of columns required for cov. index */
  81   IdxConstraint *pOrder;          /* ORDER BY columns */
  82   IdxConstraint *pEq;             /* List of == constraints */
  83   IdxConstraint *pRange;          /* List of < constraints */
  84   IdxScan *pNextScan;             /* Next IdxScan object for same analysis */
  85 };
  86
  87 /*
  88 ** Information regarding a single database table. Extracted from
  89 ** "PRAGMA table_info" by function idxGetTableInfo().
  90 */
  91 struct IdxColumn {
  92   char *zName;
  93   char *zColl;
  94   int iPk;
  95 };
  96 struct IdxTable {
  97   int nCol;
  98   char *zName;                    /* Table name */
  99   IdxColumn *aCol;
 100   IdxTable *pNext;                /* Next table in linked list of all tables */
 101 };
 102
 103 /*
 104 ** An object of the following type is created for each unique table/write-op
 105 ** seen. The objects are stored in a singly-linked list beginning at
 106 ** sqlite3expert.pWrite.
 107 */
 108 struct IdxWrite {
 109   IdxTable *pTab;
 110   int eOp;                        /* SQLITE_UPDATE, DELETE or INSERT */
 111   IdxWrite *pNext;
 112 };
 113
 114 /*
 115 ** Each statement being analyzed is represented by an instance of this
 116 ** structure.
 117 */
 118 struct IdxStatement {
 119   int iId;                        /* Statement number */
 120   char *zSql;                     /* SQL statement */
 121   char *zIdx;                     /* Indexes */
 122   char *zEQP;                     /* Plan */
 123   IdxStatement *pNext;
 124 };
 125
 126
 127 /*
 128 ** A hash table for storing strings. With space for a payload string
 129 ** with each entry. Methods are:
 130 **
 131 **   idxHashInit()
 132 **   idxHashClear()
 133 **   idxHashAdd()
 134 **   idxHashSearch()
 135 */
 136 #define IDX_HASH_SIZE 1023
 137 typedef struct IdxHashEntry IdxHashEntry;
 138 typedef struct IdxHash IdxHash;
 139 struct IdxHashEntry {
 140   char *zKey;                     /* nul-terminated key */
 141   char *zVal;                     /* nul-terminated value string */
 142   char *zVal2;                    /* nul-terminated value string 2 */
 143   IdxHashEntry *pHashNext;        /* Next entry in same hash bucket */
 144   IdxHashEntry *pNext;            /* Next entry in hash */
 145 };
 146 struct IdxHash {
 147   IdxHashEntry *pFirst;
 148   IdxHashEntry *aHash[IDX_HASH_SIZE];
 149 };
 150
 151 /*
 152 ** sqlite3expert object.
 153 */
 154 struct sqlite3expert {
 155   int iSample;                    /* Percentage of tables to sample for stat1 */
 156   sqlite3 *db;                    /* User database */
 157   sqlite3 *dbm;                   /* In-memory db for this analysis */
 158   sqlite3 *dbv;                   /* Vtab schema for this analysis */
 159   IdxTable *pTable;               /* List of all IdxTable objects */
 160   IdxScan *pScan;                 /* List of scan objects */
 161   IdxWrite *pWrite;               /* List of write objects */
 162   IdxStatement *pStatement;       /* List of IdxStatement objects */
 163   int bRun;                       /* True once analysis has run */
 164   char **pzErrmsg;
 165   int rc;                         /* Error code from whereinfo hook */
 166   IdxHash hIdx;                   /* Hash containing all candidate indexes */
 167   char *zCandidates;              /* For EXPERT_REPORT_CANDIDATES */
 168 };
 169
 170
 171 /*
 172 ** Allocate and return nByte bytes of zeroed memory using sqlite3_malloc().
 173 ** If the allocation fails, set *pRc to SQLITE_NOMEM and return NULL.
 174 */
 175 static void *idxMalloc(int *pRc, int nByte){
 176   void *pRet;
 177   assert( *pRc==SQLITE_OK );
 178   assert( nByte>0 );
 179   pRet = sqlite3_malloc(nByte);
 180   if( pRet ){
 181     memset(pRet, 0, nByte);
 182   }else{
 183     *pRc = SQLITE_NOMEM;
 184   }
 185   return pRet;
 186 }
 187
 188 /*
 189 ** Initialize an IdxHash hash table.
 190 */
 191 static void idxHashInit(IdxHash *pHash){
 192   memset(pHash, 0, sizeof(IdxHash));
 193 }
 194
 195 /*
 196 ** Reset an IdxHash hash table.
 197 */
 198 static void idxHashClear(IdxHash *pHash){
 199   int i;
 200   for(i=0; i<IDX_HASH_SIZE; i++){
 201     IdxHashEntry *pEntry;
 202     IdxHashEntry *pNext;
 203     for(pEntry=pHash->aHash[i]; pEntry; pEntry=pNext){
 204       pNext = pEntry->pHashNext;
 205       sqlite3_free(pEntry->zVal2);
 206       sqlite3_free(pEntry);
 207     }
 208   }
 209   memset(pHash, 0, sizeof(IdxHash));
 210 }
 211
 212 /*
 213 ** Return the index of the hash bucket that the string specified by the
 214 ** arguments to this function belongs.
 215 */
 216 static int idxHashString(const char *z, int n){
 217   unsigned int ret = 0;
 218   int i;
 219   for(i=0; i<n; i++){
 220     ret += (ret<<3) + (unsigned char)(z[i]);
 221   }
 222   return (int)(ret % IDX_HASH_SIZE);
 223 }
 224
 225 /*
 226 ** If zKey is already present in the hash table, return non-zero and do
 227 ** nothing. Otherwise, add an entry with key zKey and payload string zVal to
 228 ** the hash table passed as the second argument.
 229 */
 230 static int idxHashAdd(
 231   int *pRc,
 232   IdxHash *pHash,
 233   const char *zKey,
 234   const char *zVal
 235 ){
 236   int nKey = STRLEN(zKey);
 237   int iHash = idxHashString(zKey, nKey);
 238   int nVal = (zVal ? STRLEN(zVal) : 0);
 239   IdxHashEntry *pEntry;
 240   assert( iHash>=0 );
 241   for(pEntry=pHash->aHash[iHash]; pEntry; pEntry=pEntry->pHashNext){
 242     if( STRLEN(pEntry->zKey)==nKey && 0==memcmp(pEntry->zKey, zKey, nKey) ){
 243       return 1;
 244     }
 245   }
 246   pEntry = idxMalloc(pRc, sizeof(IdxHashEntry) + nKey+1 + nVal+1);
 247   if( pEntry ){
 248     pEntry->zKey = (char*)&pEntry[1];
 249     memcpy(pEntry->zKey, zKey, nKey);
 250     if( zVal ){
 251       pEntry->zVal = &pEntry->zKey[nKey+1];
 252       memcpy(pEntry->zVal, zVal, nVal);
 253     }
 254     pEntry->pHashNext = pHash->aHash[iHash];
 255     pHash->aHash[iHash] = pEntry;
 256
 257     pEntry->pNext = pHash->pFirst;
 258     pHash->pFirst = pEntry;
 259   }
 260   return 0;
 261 }
 262
 263 /*
 264 ** If zKey/nKey is present in the hash table, return a pointer to the
 265 ** hash-entry object.
 266 */
 267 static IdxHashEntry *idxHashFind(IdxHash *pHash, const char *zKey, int nKey){
 268   int iHash;
 269   IdxHashEntry *pEntry;
 270   if( nKey<0 ) nKey = STRLEN(zKey);
 271   iHash = idxHashString(zKey, nKey);
 272   assert( iHash>=0 );
 273   for(pEntry=pHash->aHash[iHash]; pEntry; pEntry=pEntry->pHashNext){
 274     if( STRLEN(pEntry->zKey)==nKey && 0==memcmp(pEntry->zKey, zKey, nKey) ){
 275       return pEntry;
 276     }
 277   }
 278   return 0;
 279 }
 280
 281 /*
 282 ** If the hash table contains an entry with a key equal to the string
 283 ** passed as the final two arguments to this function, return a pointer
 284 ** to the payload string. Otherwise, if zKey/nKey is not present in the
 285 ** hash table, return NULL.
 286 */
 287 static const char *idxHashSearch(IdxHash *pHash, const char *zKey, int nKey){
 288   IdxHashEntry *pEntry = idxHashFind(pHash, zKey, nKey);
 289   if( pEntry ) return pEntry->zVal;
 290   return 0;
 291 }
 292
 293 /*
 294 ** Allocate and return a new IdxConstraint object. Set the IdxConstraint.zColl
 295 ** variable to point to a copy of nul-terminated string zColl.
 296 */
 297 static IdxConstraint *idxNewConstraint(int *pRc, const char *zColl){
 298   IdxConstraint *pNew;
 299   int nColl = STRLEN(zColl);
 300
 301   assert( *pRc==SQLITE_OK );
 302   pNew = (IdxConstraint*)idxMalloc(pRc, sizeof(IdxConstraint) * nColl + 1);
 303   if( pNew ){
 304     pNew->zColl = (char*)&pNew[1];
 305     memcpy(pNew->zColl, zColl, nColl+1);
 306   }
 307   return pNew;
 308 }
 309
 310 /*
 311 ** An error associated with database handle db has just occurred. Pass
 312 ** the error message to callback function xOut.
 313 */
 314 static void idxDatabaseError(
 315   sqlite3 *db,                    /* Database handle */
 316   char **pzErrmsg                 /* Write error here */
 317 ){
 318   *pzErrmsg = sqlite3_mprintf("%s", sqlite3_errmsg(db));
 319 }
 320
 321 /*
 322 ** Prepare an SQL statement.
 323 */
 324 static int idxPrepareStmt(
 325   sqlite3 *db,                    /* Database handle to compile against */
 326   sqlite3_stmt **ppStmt,          /* OUT: Compiled SQL statement */
 327   char **pzErrmsg,                /* OUT: sqlite3_malloc()ed error message */
 328   const char *zSql                /* SQL statement to compile */
 329 ){
 330   int rc = sqlite3_prepare_v2(db, zSql, -1, ppStmt, 0);
 331   if( rc!=SQLITE_OK ){
 332     *ppStmt = 0;
 333     idxDatabaseError(db, pzErrmsg);
 334   }
 335   return rc;
 336 }
 337
 338 /*
 339 ** Prepare an SQL statement using the results of a printf() formatting.
 340 */
 341 static int idxPrintfPrepareStmt(
 342   sqlite3 *db,                    /* Database handle to compile against */
 343   sqlite3_stmt **ppStmt,          /* OUT: Compiled SQL statement */
 344   char **pzErrmsg,                /* OUT: sqlite3_malloc()ed error message */
 345   const char *zFmt,               /* printf() format of SQL statement */
 346   ...                             /* Trailing printf() arguments */
 347 ){
 348   va_list ap;
 349   int rc;
 350   char *zSql;
 351   va_start(ap, zFmt);
 352   zSql = sqlite3_vmprintf(zFmt, ap);
 353   if( zSql==0 ){
 354     rc = SQLITE_NOMEM;
 355   }else{
 356     rc = idxPrepareStmt(db, ppStmt, pzErrmsg, zSql);
 357     sqlite3_free(zSql);
 358   }
 359   va_end(ap);
 360   return rc;
 361 }
 362
 363
 364 /*************************************************************************
 365 ** Beginning of virtual table implementation.
 366 */
 367 typedef struct ExpertVtab ExpertVtab;
 368 struct ExpertVtab {
 369   sqlite3_vtab base;
 370   IdxTable *pTab;
 371   sqlite3expert *pExpert;
 372 };
 373
 374 typedef struct ExpertCsr ExpertCsr;
 375 struct ExpertCsr {
 376   sqlite3_vtab_cursor base;
 377   sqlite3_stmt *pData;
 378 };
 379
 380 static char *expertDequote(const char *zIn){
 381   int n = STRLEN(zIn);
 382   char *zRet = sqlite3_malloc(n);
 383
 384   assert( zIn[0]=='\'' );
 385   assert( zIn[n-1]=='\'' );
 386
 387   if( zRet ){
 388     int iOut = 0;
 389     int iIn = 0;
 390     for(iIn=1; iIn<(n-1); iIn++){
 391       if( zIn[iIn]=='\'' ){
 392         assert( zIn[iIn+1]=='\'' );
 393         iIn++;
 394       }
 395       zRet[iOut++] = zIn[iIn];
 396     }
 397     zRet[iOut] = '\0';
 398   }
 399
 400   return zRet;
 401 }
 402
 403 /*
 404 ** This function is the implementation of both the xConnect and xCreate
 405 ** methods of the r-tree virtual table.
 406 **
 407 **   argv[0]   -> module name
 408 **   argv[1]   -> database name
 409 **   argv[2]   -> table name
 410 **   argv[...] -> column names...
 411 */
 412 static int expertConnect(
 413   sqlite3 *db,
 414   void *pAux,
 415   int argc, const char *const*argv,
 416   sqlite3_vtab **ppVtab,
 417   char **pzErr
 418 ){
 419   sqlite3expert *pExpert = (sqlite3expert*)pAux;
 420   ExpertVtab *p = 0;
 421   int rc;
 422
 423   if( argc!=4 ){
 424     *pzErr = sqlite3_mprintf("internal error!");
 425     rc = SQLITE_ERROR;
 426   }else{
 427     char *zCreateTable = expertDequote(argv[3]);
 428     if( zCreateTable ){
 429       rc = sqlite3_declare_vtab(db, zCreateTable);
 430       if( rc==SQLITE_OK ){
 431         p = idxMalloc(&rc, sizeof(ExpertVtab));
 432       }
 433       if( rc==SQLITE_OK ){
 434         p->pExpert = pExpert;
 435         p->pTab = pExpert->pTable;
 436         assert( sqlite3_stricmp(p->pTab->zName, argv[2])==0 );
 437       }
 438       sqlite3_free(zCreateTable);
 439     }else{
 440       rc = SQLITE_NOMEM;
 441     }
 442   }
 443
 444   *ppVtab = (sqlite3_vtab*)p;
 445   return rc;
 446 }
 447
 448 static int expertDisconnect(sqlite3_vtab *pVtab){
 449   ExpertVtab *p = (ExpertVtab*)pVtab;
 450   sqlite3_free(p);
 451   return SQLITE_OK;
 452 }
 453
 454 static int expertBestIndex(sqlite3_vtab *pVtab, sqlite3_index_info *pIdxInfo){
 455   ExpertVtab *p = (ExpertVtab*)pVtab;
 456   int rc = SQLITE_OK;
 457   int n = 0;
 458   IdxScan *pScan;
 459   const int opmask =
 460     SQLITE_INDEX_CONSTRAINT_EQ | SQLITE_INDEX_CONSTRAINT_GT |
 461     SQLITE_INDEX_CONSTRAINT_LT | SQLITE_INDEX_CONSTRAINT_GE |
 462     SQLITE_INDEX_CONSTRAINT_LE;
 463
 464   pScan = idxMalloc(&rc, sizeof(IdxScan));
 465   if( pScan ){
 466     int i;
 467
 468     /* Link the new scan object into the list */
 469     pScan->pTab = p->pTab;
 470     pScan->pNextScan = p->pExpert->pScan;
 471     p->pExpert->pScan = pScan;
 472
 473     /* Add the constraints to the IdxScan object */
 474     for(i=0; i<pIdxInfo->nConstraint; i++){
 475       struct sqlite3_index_constraint *pCons = &pIdxInfo->aConstraint[i];
 476       if( pCons->usable
 477        && pCons->iColumn>=0
 478        && p->pTab->aCol[pCons->iColumn].iPk==0
 479        && (pCons->op & opmask)
 480       ){
 481         IdxConstraint *pNew;
 482         const char *zColl = sqlite3_vtab_collation(pIdxInfo, i);
 483         pNew = idxNewConstraint(&rc, zColl);
 484         if( pNew ){
 485           pNew->iCol = pCons->iColumn;
 486           if( pCons->op==SQLITE_INDEX_CONSTRAINT_EQ ){
 487             pNew->pNext = pScan->pEq;
 488             pScan->pEq = pNew;
 489           }else{
 490             pNew->bRange = 1;
 491             pNew->pNext = pScan->pRange;
 492             pScan->pRange = pNew;
 493           }
 494         }
 495         n++;
 496         pIdxInfo->aConstraintUsage[i].argvIndex = n;
 497       }
 498     }
 499
 500     /* Add the ORDER BY to the IdxScan object */
 501     for(i=pIdxInfo->nOrderBy-1; i>=0; i--){
 502       int iCol = pIdxInfo->aOrderBy[i].iColumn;
 503       if( iCol>=0 ){
 504         IdxConstraint *pNew = idxNewConstraint(&rc, p->pTab->aCol[iCol].zColl);
 505         if( pNew ){
 506           pNew->iCol = iCol;
 507           pNew->bDesc = pIdxInfo->aOrderBy[i].desc;
 508           pNew->pNext = pScan->pOrder;
 509           pNew->pLink = pScan->pOrder;
 510           pScan->pOrder = pNew;
 511           n++;
 512         }
 513       }
 514     }
 515   }
 516
 517   pIdxInfo->estimatedCost = 1000000.0 / (n+1);
 518   return rc;
 519 }
 520
 521 static int expertUpdate(
 522   sqlite3_vtab *pVtab,
 523   int nData,
 524   sqlite3_value **azData,
 525   sqlite_int64 *pRowid
 526 ){
 527   (void)pVtab;
 528   (void)nData;
 529   (void)azData;
 530   (void)pRowid;
 531   return SQLITE_OK;
 532 }
 533
 534 /*
 535 ** Virtual table module xOpen method.
 536 */
 537 static int expertOpen(sqlite3_vtab *pVTab, sqlite3_vtab_cursor **ppCursor){
 538   int rc = SQLITE_OK;
 539   ExpertCsr *pCsr;
 540   (void)pVTab;
 541   pCsr = idxMalloc(&rc, sizeof(ExpertCsr));
 542   *ppCursor = (sqlite3_vtab_cursor*)pCsr;
 543   return rc;
 544 }
 545
 546 /*
 547 ** Virtual table module xClose method.
 548 */
 549 static int expertClose(sqlite3_vtab_cursor *cur){
 550   ExpertCsr *pCsr = (ExpertCsr*)cur;
 551   sqlite3_finalize(pCsr->pData);
 552   sqlite3_free(pCsr);
 553   return SQLITE_OK;
 554 }
 555
 556 /*
 557 ** Virtual table module xEof method.
 558 **
 559 ** Return non-zero if the cursor does not currently point to a valid
 560 ** record (i.e if the scan has finished), or zero otherwise.
 561 */
 562 static int expertEof(sqlite3_vtab_cursor *cur){
 563   ExpertCsr *pCsr = (ExpertCsr*)cur;
 564   return pCsr->pData==0;
 565 }
 566
 567 /*
 568 ** Virtual table module xNext method.
 569 */
 570 static int expertNext(sqlite3_vtab_cursor *cur){
 571   ExpertCsr *pCsr = (ExpertCsr*)cur;
 572   int rc = SQLITE_OK;
 573
 574   assert( pCsr->pData );
 575   rc = sqlite3_step(pCsr->pData);
 576   if( rc!=SQLITE_ROW ){
 577     rc = sqlite3_finalize(pCsr->pData);
 578     pCsr->pData = 0;
 579   }else{
 580     rc = SQLITE_OK;
 581   }
 582
 583   return rc;
 584 }
 585
 586 /*
 587 ** Virtual table module xRowid method.
 588 */
 589 static int expertRowid(sqlite3_vtab_cursor *cur, sqlite_int64 *pRowid){
 590   (void)cur;
 591   *pRowid = 0;
 592   return SQLITE_OK;
 593 }
 594
 595 /*
 596 ** Virtual table module xColumn method.
 597 */
 598 static int expertColumn(sqlite3_vtab_cursor *cur, sqlite3_context *ctx, int i){
 599   ExpertCsr *pCsr = (ExpertCsr*)cur;
 600   sqlite3_value *pVal;
 601   pVal = sqlite3_column_value(pCsr->pData, i);
 602   if( pVal ){
 603     sqlite3_result_value(ctx, pVal);
 604   }
 605   return SQLITE_OK;
 606 }
 607
 608 /*
 609 ** Virtual table module xFilter method.
 610 */
 611 static int expertFilter(
 612   sqlite3_vtab_cursor *cur,
 613   int idxNum, const char *idxStr,
 614   int argc, sqlite3_value **argv
 615 ){
 616   ExpertCsr *pCsr = (ExpertCsr*)cur;
 617   ExpertVtab *pVtab = (ExpertVtab*)(cur->pVtab);
 618   sqlite3expert *pExpert = pVtab->pExpert;
 619   int rc;
 620
 621   (void)idxNum;
 622   (void)idxStr;
 623   (void)argc;
 624   (void)argv;
 625   rc = sqlite3_finalize(pCsr->pData);
 626   pCsr->pData = 0;
 627   if( rc==SQLITE_OK ){
 628     rc = idxPrintfPrepareStmt(pExpert->db, &pCsr->pData, &pVtab->base.zErrMsg,
 629         "SELECT * FROM main.%Q WHERE sample()", pVtab->pTab->zName
 630     );
 631   }
 632
 633   if( rc==SQLITE_OK ){
 634     rc = expertNext(cur);
 635   }
 636   return rc;
 637 }
 638
 639 static int idxRegisterVtab(sqlite3expert *p){
 640   static sqlite3_module expertModule = {
 641     2,                            /* iVersion */
 642     expertConnect,                /* xCreate - create a table */
 643     expertConnect,                /* xConnect - connect to an existing table */
 644     expertBestIndex,              /* xBestIndex - Determine search strategy */
 645     expertDisconnect,             /* xDisconnect - Disconnect from a table */
 646     expertDisconnect,             /* xDestroy - Drop a table */
 647     expertOpen,                   /* xOpen - open a cursor */
 648     expertClose,                  /* xClose - close a cursor */
 649     expertFilter,                 /* xFilter - configure scan constraints */
 650     expertNext,                   /* xNext - advance a cursor */
 651     expertEof,                    /* xEof */
 652     expertColumn,                 /* xColumn - read data */
 653     expertRowid,                  /* xRowid - read data */
 654     expertUpdate,                 /* xUpdate - write data */
 655     0,                            /* xBegin - begin transaction */
 656     0,                            /* xSync - sync transaction */
 657     0,                            /* xCommit - commit transaction */
 658     0,                            /* xRollback - rollback transaction */
 659     0,                            /* xFindFunction - function overloading */
 660     0,                            /* xRename - rename the table */
 661     0,                            /* xSavepoint */
 662     0,                            /* xRelease */
 663     0,                            /* xRollbackTo */
 664     0,                            /* xShadowName */
 665   };
 666
 667   return sqlite3_create_module(p->dbv, "expert", &expertModule, (void*)p);
 668 }
 669 /*
 670 ** End of virtual table implementation.
 671 *************************************************************************/
 672 /*
 673 ** Finalize SQL statement pStmt. If (*pRc) is SQLITE_OK when this function
 674 ** is called, set it to the return value of sqlite3_finalize() before
 675 ** returning. Otherwise, discard the sqlite3_finalize() return value.
 676 */
 677 static void idxFinalize(int *pRc, sqlite3_stmt *pStmt){
 678   int rc = sqlite3_finalize(pStmt);
 679   if( *pRc==SQLITE_OK ) *pRc = rc;
 680 }
 681
 682 /*
 683 ** Attempt to allocate an IdxTable structure corresponding to table zTab
 684 ** in the main database of connection db. If successful, set (*ppOut) to
 685 ** point to the new object and return SQLITE_OK. Otherwise, return an
 686 ** SQLite error code and set (*ppOut) to NULL. In this case *pzErrmsg may be
 687 ** set to point to an error string.
 688 **
 689 ** It is the responsibility of the caller to eventually free either the
 690 ** IdxTable object or error message using sqlite3_free().
 691 */
 692 static int idxGetTableInfo(
 693   sqlite3 *db,                    /* Database connection to read details from */
 694   const char *zTab,               /* Table name */
 695   IdxTable **ppOut,               /* OUT: New object (if successful) */
 696   char **pzErrmsg                 /* OUT: Error message (if not) */
 697 ){
 698   sqlite3_stmt *p1 = 0;
 699   int nCol = 0;
 700   int nTab;
 701   int nByte;
 702   IdxTable *pNew = 0;
 703   int rc, rc2;
 704   char *pCsr = 0;
 705   int nPk = 0;
 706
 707   *ppOut = 0;
 708   if( zTab==0 ) return SQLITE_ERROR;
 709   nTab = STRLEN(zTab);
 710   nByte = sizeof(IdxTable) + nTab + 1;
 711   rc = idxPrintfPrepareStmt(db, &p1, pzErrmsg, "PRAGMA table_xinfo=%Q", zTab);
 712   while( rc==SQLITE_OK && SQLITE_ROW==sqlite3_step(p1) ){
 713     const char *zCol = (const char*)sqlite3_column_text(p1, 1);
 714     const char *zColSeq = 0;
 715     if( zCol==0 ){
 716       rc = SQLITE_ERROR;
 717       break;
 718     }
 719     nByte += 1 + STRLEN(zCol);
 720     rc = sqlite3_table_column_metadata(
 721         db, "main", zTab, zCol, 0, &zColSeq, 0, 0, 0
 722     );
 723     if( zColSeq==0 ) zColSeq = "binary";
 724     nByte += 1 + STRLEN(zColSeq);
 725     nCol++;
 726     nPk += (sqlite3_column_int(p1, 5)>0);
 727   }
 728   rc2 = sqlite3_reset(p1);
 729   if( rc==SQLITE_OK ) rc = rc2;
 730
 731   nByte += sizeof(IdxColumn) * nCol;
 732   if( rc==SQLITE_OK ){
 733     pNew = idxMalloc(&rc, nByte);
 734   }
 735   if( rc==SQLITE_OK ){
 736     pNew->aCol = (IdxColumn*)&pNew[1];
 737     pNew->nCol = nCol;
 738     pCsr = (char*)&pNew->aCol[nCol];
 739   }
 740
 741   nCol = 0;
 742   while( rc==SQLITE_OK && SQLITE_ROW==sqlite3_step(p1) ){
 743     const char *zCol = (const char*)sqlite3_column_text(p1, 1);
 744     const char *zColSeq = 0;
 745     int nCopy;
 746     if( zCol==0 ) continue;
 747     nCopy = STRLEN(zCol) + 1;
 748     pNew->aCol[nCol].zName = pCsr;
 749     pNew->aCol[nCol].iPk = (sqlite3_column_int(p1, 5)==1 && nPk==1);
 750     memcpy(pCsr, zCol, nCopy);
 751     pCsr += nCopy;
 752
 753     rc = sqlite3_table_column_metadata(
 754         db, "main", zTab, zCol, 0, &zColSeq, 0, 0, 0
 755     );
 756     if( rc==SQLITE_OK ){
 757       if( zColSeq==0 ) zColSeq = "binary";
 758       nCopy = STRLEN(zColSeq) + 1;
 759       pNew->aCol[nCol].zColl = pCsr;
 760       memcpy(pCsr, zColSeq, nCopy);
 761       pCsr += nCopy;
 762     }
 763
 764     nCol++;
 765   }
 766   idxFinalize(&rc, p1);
 767
 768   if( rc!=SQLITE_OK ){
 769     sqlite3_free(pNew);
 770     pNew = 0;
 771   }else if( ALWAYS(pNew!=0) ){
 772     pNew->zName = pCsr;
 773     if( ALWAYS(pNew->zName!=0) ) memcpy(pNew->zName, zTab, nTab+1);
 774   }
 775
 776   *ppOut = pNew;
 777   return rc;
 778 }
 779
 780 /*
 781 ** This function is a no-op if *pRc is set to anything other than
 782 ** SQLITE_OK when it is called.
 783 **
 784 ** If *pRc is initially set to SQLITE_OK, then the text specified by
 785 ** the printf() style arguments is appended to zIn and the result returned
 786 ** in a buffer allocated by sqlite3_malloc(). sqlite3_free() is called on
 787 ** zIn before returning.
 788 */
 789 static char *idxAppendText(int *pRc, char *zIn, const char *zFmt, ...){
 790   va_list ap;
 791   char *zAppend = 0;
 792   char *zRet = 0;
 793   int nIn = zIn ? STRLEN(zIn) : 0;
 794   int nAppend = 0;
 795   va_start(ap, zFmt);
 796   if( *pRc==SQLITE_OK ){
 797     zAppend = sqlite3_vmprintf(zFmt, ap);
 798     if( zAppend ){
 799       nAppend = STRLEN(zAppend);
 800       zRet = (char*)sqlite3_malloc(nIn + nAppend + 1);
 801     }
 802     if( zAppend && zRet ){
 803       if( nIn ) memcpy(zRet, zIn, nIn);
 804       memcpy(&zRet[nIn], zAppend, nAppend+1);
 805     }else{
 806       sqlite3_free(zRet);
 807       zRet = 0;
 808       *pRc = SQLITE_NOMEM;
 809     }
 810     sqlite3_free(zAppend);
 811     sqlite3_free(zIn);
 812   }
 813   va_end(ap);
 814   return zRet;
 815 }
 816
 817 /*
 818 ** Return true if zId must be quoted in order to use it as an SQL
 819 ** identifier, or false otherwise.
 820 */
 821 static int idxIdentifierRequiresQuotes(const char *zId){
 822   int i;
 823   int nId = STRLEN(zId);
 824
 825   if( sqlite3_keyword_check(zId, nId) ) return 1;
 826
 827   for(i=0; zId[i]; i++){
 828     if( !(zId[i]=='_')
 829      && !(zId[i]>='0' && zId[i]<='9')
 830      && !(zId[i]>='a' && zId[i]<='z')
 831      && !(zId[i]>='A' && zId[i]<='Z')
 832     ){
 833       return 1;
 834     }
 835   }
 836   return 0;
 837 }
 838
 839 /*
 840 ** This function appends an index column definition suitable for constraint
 841 ** pCons to the string passed as zIn and returns the result.
 842 */
 843 static char *idxAppendColDefn(
 844   int *pRc,                       /* IN/OUT: Error code */
 845   char *zIn,                      /* Column defn accumulated so far */
 846   IdxTable *pTab,                 /* Table index will be created on */
 847   IdxConstraint *pCons
 848 ){
 849   char *zRet = zIn;
 850   IdxColumn *p = &pTab->aCol[pCons->iCol];
 851   if( zRet ) zRet = idxAppendText(pRc, zRet, ", ");
 852
 853   if( idxIdentifierRequiresQuotes(p->zName) ){
 854     zRet = idxAppendText(pRc, zRet, "%Q", p->zName);
 855   }else{
 856     zRet = idxAppendText(pRc, zRet, "%s", p->zName);
 857   }
 858
 859   if( sqlite3_stricmp(p->zColl, pCons->zColl) ){
 860     if( idxIdentifierRequiresQuotes(pCons->zColl) ){
 861       zRet = idxAppendText(pRc, zRet, " COLLATE %Q", pCons->zColl);
 862     }else{
 863       zRet = idxAppendText(pRc, zRet, " COLLATE %s", pCons->zColl);
 864     }
 865   }
 866
 867   if( pCons->bDesc ){
 868     zRet = idxAppendText(pRc, zRet, " DESC");
 869   }
 870   return zRet;
 871 }
 872
 873 /*
 874 ** Search database dbm for an index compatible with the one idxCreateFromCons()
 875 ** would create from arguments pScan, pEq and pTail. If no error occurs and
 876 ** such an index is found, return non-zero. Or, if no such index is found,
 877 ** return zero.
 878 **
 879 ** If an error occurs, set *pRc to an SQLite error code and return zero.
 880 */
 881 static int idxFindCompatible(
 882   int *pRc,                       /* OUT: Error code */
 883   sqlite3* dbm,                   /* Database to search */
 884   IdxScan *pScan,                 /* Scan for table to search for index on */
 885   IdxConstraint *pEq,             /* List of == constraints */
 886   IdxConstraint *pTail            /* List of range constraints */
 887 ){
 888   const char *zTbl = pScan->pTab->zName;
 889   sqlite3_stmt *pIdxList = 0;
 890   IdxConstraint *pIter;
 891   int nEq = 0;                    /* Number of elements in pEq */
 892   int rc;
 893
 894   /* Count the elements in list pEq */
 895   for(pIter=pEq; pIter; pIter=pIter->pLink) nEq++;
 896
 897   rc = idxPrintfPrepareStmt(dbm, &pIdxList, 0, "PRAGMA index_list=%Q", zTbl);
 898   while( rc==SQLITE_OK && sqlite3_step(pIdxList)==SQLITE_ROW ){
 899     int bMatch = 1;
 900     IdxConstraint *pT = pTail;
 901     sqlite3_stmt *pInfo = 0;
 902     const char *zIdx = (const char*)sqlite3_column_text(pIdxList, 1);
 903     if( zIdx==0 ) continue;
 904
 905     /* Zero the IdxConstraint.bFlag values in the pEq list */
 906     for(pIter=pEq; pIter; pIter=pIter->pLink) pIter->bFlag = 0;
 907
 908     rc = idxPrintfPrepareStmt(dbm, &pInfo, 0, "PRAGMA index_xInfo=%Q", zIdx);
 909     while( rc==SQLITE_OK && sqlite3_step(pInfo)==SQLITE_ROW ){
 910       int iIdx = sqlite3_column_int(pInfo, 0);
 911       int iCol = sqlite3_column_int(pInfo, 1);
 912       const char *zColl = (const char*)sqlite3_column_text(pInfo, 4);
 913
 914       if( iIdx<nEq ){
 915         for(pIter=pEq; pIter; pIter=pIter->pLink){
 916           if( pIter->bFlag ) continue;
 917           if( pIter->iCol!=iCol ) continue;
 918           if( sqlite3_stricmp(pIter->zColl, zColl) ) continue;
 919           pIter->bFlag = 1;
 920           break;
 921         }
 922         if( pIter==0 ){
 923           bMatch = 0;
 924           break;
 925         }
 926       }else{
 927         if( pT ){
 928           if( pT->iCol!=iCol || sqlite3_stricmp(pT->zColl, zColl) ){
 929             bMatch = 0;
 930             break;
 931           }
 932           pT = pT->pLink;
 933         }
 934       }
 935     }
 936     idxFinalize(&rc, pInfo);
 937
 938     if( rc==SQLITE_OK && bMatch ){
 939       sqlite3_finalize(pIdxList);
 940       return 1;
 941     }
 942   }
 943   idxFinalize(&rc, pIdxList);
 944
 945   *pRc = rc;
 946   return 0;
 947 }
 948
 949 /* Callback for sqlite3_exec() with query with leading count(*) column.
 950  * The first argument is expected to be an int*, referent to be incremented
 951  * if that leading column is not exactly '0'.
 952  */
 953 static int countNonzeros(void* pCount, int nc,
 954                          char* azResults[], char* azColumns[]){
 955   (void)azColumns;  /* Suppress unused parameter warning */
 956   if( nc>0 && (azResults[0][0]!='0' || azResults[0][1]!=0) ){
 957     *((int *)pCount) += 1;
 958   }
 959   return 0;
 960 }
 961
 962 static int idxCreateFromCons(
 963   sqlite3expert *p,
 964   IdxScan *pScan,
 965   IdxConstraint *pEq,
 966   IdxConstraint *pTail
 967 ){
 968   sqlite3 *dbm = p->dbm;
 969   int rc = SQLITE_OK;
 970   if( (pEq || pTail) && 0==idxFindCompatible(&rc, dbm, pScan, pEq, pTail) ){
 971     IdxTable *pTab = pScan->pTab;
 972     char *zCols = 0;
 973     char *zIdx = 0;
 974     IdxConstraint *pCons;
 975     unsigned int h = 0;
 976     const char *zFmt;
 977
 978     for(pCons=pEq; pCons; pCons=pCons->pLink){
 979       zCols = idxAppendColDefn(&rc, zCols, pTab, pCons);
 980     }
 981     for(pCons=pTail; pCons; pCons=pCons->pLink){
 982       zCols = idxAppendColDefn(&rc, zCols, pTab, pCons);
 983     }
 984
 985     if( rc==SQLITE_OK ){
 986       /* Hash the list of columns to come up with a name for the index */
 987       const char *zTable = pScan->pTab->zName;
 988       int quoteTable = idxIdentifierRequiresQuotes(zTable);
 989       char *zName = 0;          /* Index name */
 990       int collisions = 0;
 991       do{
 992         int i;
 993         char *zFind;
 994         for(i=0; zCols[i]; i++){
 995           h += ((h<<3) + zCols[i]);
 996         }
 997         sqlite3_free(zName);
 998         zName = sqlite3_mprintf("%s_idx_%08x", zTable, h);
 999         if( zName==0 ) break;
1000         /* Is is unique among table, view and index names? */
1001         zFmt = "SELECT count(*) FROM sqlite_schema WHERE name=%Q"
1002           " AND type in ('index','table','view')";
1003         zFind = sqlite3_mprintf(zFmt, zName);
1004         i = 0;
1005         rc = sqlite3_exec(dbm, zFind, countNonzeros, &i, 0);
1006         assert(rc==SQLITE_OK);
1007         sqlite3_free(zFind);
1008         if( i==0 ){
1009           collisions = 0;
1010           break;
1011         }
1012         ++collisions;
1013       }while( collisions<50 && zName!=0 );
1014       if( collisions ){
1015         /* This return means "Gave up trying to find a unique index name." */
1016         rc = SQLITE_BUSY_TIMEOUT;
1017       }else if( zName==0 ){
1018         rc = SQLITE_NOMEM;
1019       }else{
1020         if( quoteTable ){
1021           zFmt = "CREATE INDEX \"%w\" ON \"%w\"(%s)";
1022         }else{
1023           zFmt = "CREATE INDEX %s ON %s(%s)";
1024         }
1025         zIdx = sqlite3_mprintf(zFmt, zName, zTable, zCols);
1026         if( !zIdx ){
1027           rc = SQLITE_NOMEM;
1028         }else{
1029           rc = sqlite3_exec(dbm, zIdx, 0, 0, p->pzErrmsg);
1030           if( rc!=SQLITE_OK ){
1031             rc = SQLITE_BUSY_TIMEOUT;
1032           }else{
1033             idxHashAdd(&rc, &p->hIdx, zName, zIdx);
1034           }
1035         }
1036         sqlite3_free(zName);
1037         sqlite3_free(zIdx);
1038       }
1039     }
1040
1041     sqlite3_free(zCols);
1042   }
1043   return rc;
1044 }
1045
1046 /*
1047 ** Return true if list pList (linked by IdxConstraint.pLink) contains
1048 ** a constraint compatible with *p. Otherwise return false.
1049 */
1050 static int idxFindConstraint(IdxConstraint *pList, IdxConstraint *p){
1051   IdxConstraint *pCmp;
1052   for(pCmp=pList; pCmp; pCmp=pCmp->pLink){
1053     if( p->iCol==pCmp->iCol ) return 1;
1054   }
1055   return 0;
1056 }
1057
1058 static int idxCreateFromWhere(
1059   sqlite3expert *p,
1060   IdxScan *pScan,                 /* Create indexes for this scan */
1061   IdxConstraint *pTail            /* range/ORDER BY constraints for inclusion */
1062 ){
1063   IdxConstraint *p1 = 0;
1064   IdxConstraint *pCon;
1065   int rc;
1066
1067   /* Gather up all the == constraints. */
1068   for(pCon=pScan->pEq; pCon; pCon=pCon->pNext){
1069     if( !idxFindConstraint(p1, pCon) && !idxFindConstraint(pTail, pCon) ){
1070       pCon->pLink = p1;
1071       p1 = pCon;
1072     }
1073   }
1074
1075   /* Create an index using the == constraints collected above. And the
1076   ** range constraint/ORDER BY terms passed in by the caller, if any. */
1077   rc = idxCreateFromCons(p, pScan, p1, pTail);
1078
1079   /* If no range/ORDER BY passed by the caller, create a version of the
1080   ** index for each range constraint.  */
1081   if( pTail==0 ){
1082     for(pCon=pScan->pRange; rc==SQLITE_OK && pCon; pCon=pCon->pNext){
1083       assert( pCon->pLink==0 );
1084       if( !idxFindConstraint(p1, pCon) && !idxFindConstraint(pTail, pCon) ){
1085         rc = idxCreateFromCons(p, pScan, p1, pCon);
1086       }
1087     }
1088   }
1089
1090   return rc;
1091 }
1092
1093 /*
1094 ** Create candidate indexes in database [dbm] based on the data in
1095 ** linked-list pScan.
1096 */
1097 static int idxCreateCandidates(sqlite3expert *p){
1098   int rc = SQLITE_OK;
1099   IdxScan *pIter;
1100
1101   for(pIter=p->pScan; pIter && rc==SQLITE_OK; pIter=pIter->pNextScan){
1102     rc = idxCreateFromWhere(p, pIter, 0);
1103     if( rc==SQLITE_OK && pIter->pOrder ){
1104       rc = idxCreateFromWhere(p, pIter, pIter->pOrder);
1105     }
1106   }
1107
1108   return rc;
1109 }
1110
1111 /*
1112 ** Free all elements of the linked list starting at pConstraint.
1113 */
1114 static void idxConstraintFree(IdxConstraint *pConstraint){
1115   IdxConstraint *pNext;
1116   IdxConstraint *p;
1117
1118   for(p=pConstraint; p; p=pNext){
1119     pNext = p->pNext;
1120     sqlite3_free(p);
1121   }
1122 }
1123
1124 /*
1125 ** Free all elements of the linked list starting from pScan up until pLast
1126 ** (pLast is not freed).
1127 */
1128 static void idxScanFree(IdxScan *pScan, IdxScan *pLast){
1129   IdxScan *p;
1130   IdxScan *pNext;
1131   for(p=pScan; p!=pLast; p=pNext){
1132     pNext = p->pNextScan;
1133     idxConstraintFree(p->pOrder);
1134     idxConstraintFree(p->pEq);
1135     idxConstraintFree(p->pRange);
1136     sqlite3_free(p);
1137   }
1138 }
1139
1140 /*
1141 ** Free all elements of the linked list starting from pStatement up
1142 ** until pLast (pLast is not freed).
1143 */
1144 static void idxStatementFree(IdxStatement *pStatement, IdxStatement *pLast){
1145   IdxStatement *p;
1146   IdxStatement *pNext;
1147   for(p=pStatement; p!=pLast; p=pNext){
1148     pNext = p->pNext;
1149     sqlite3_free(p->zEQP);
1150     sqlite3_free(p->zIdx);
1151     sqlite3_free(p);
1152   }
1153 }
1154
1155 /*
1156 ** Free the linked list of IdxTable objects starting at pTab.
1157 */
1158 static void idxTableFree(IdxTable *pTab){
1159   IdxTable *pIter;
1160   IdxTable *pNext;
1161   for(pIter=pTab; pIter; pIter=pNext){
1162     pNext = pIter->pNext;
1163     sqlite3_free(pIter);
1164   }
1165 }
1166
1167 /*
1168 ** Free the linked list of IdxWrite objects starting at pTab.
1169 */
1170 static void idxWriteFree(IdxWrite *pTab){
1171   IdxWrite *pIter;
1172   IdxWrite *pNext;
1173   for(pIter=pTab; pIter; pIter=pNext){
1174     pNext = pIter->pNext;
1175     sqlite3_free(pIter);
1176   }
1177 }
1178
1179
1180
1181 /*
1182 ** This function is called after candidate indexes have been created. It
1183 ** runs all the queries to see which indexes they prefer, and populates
1184 ** IdxStatement.zIdx and IdxStatement.zEQP with the results.
1185 */
1186 static int idxFindIndexes(
1187   sqlite3expert *p,
1188   char **pzErr                         /* OUT: Error message (sqlite3_malloc) */
1189 ){
1190   IdxStatement *pStmt;
1191   sqlite3 *dbm = p->dbm;
1192   int rc = SQLITE_OK;
1193
1194   IdxHash hIdx;
1195   idxHashInit(&hIdx);
1196
1197   for(pStmt=p->pStatement; rc==SQLITE_OK && pStmt; pStmt=pStmt->pNext){
1198     IdxHashEntry *pEntry;
1199     sqlite3_stmt *pExplain = 0;
1200     idxHashClear(&hIdx);
1201     rc = idxPrintfPrepareStmt(dbm, &pExplain, pzErr,
1202         "EXPLAIN QUERY PLAN %s", pStmt->zSql
1203     );
1204     while( rc==SQLITE_OK && sqlite3_step(pExplain)==SQLITE_ROW ){
1205       /* int iId = sqlite3_column_int(pExplain, 0); */
1206       /* int iParent = sqlite3_column_int(pExplain, 1); */
1207       /* int iNotUsed = sqlite3_column_int(pExplain, 2); */
1208       const char *zDetail = (const char*)sqlite3_column_text(pExplain, 3);
1209       int nDetail;
1210       int i;
1211
1212       if( !zDetail ) continue;
1213       nDetail = STRLEN(zDetail);
1214
1215       for(i=0; i<nDetail; i++){
1216         const char *zIdx = 0;
1217         if( i+13<nDetail && memcmp(&zDetail[i], " USING INDEX ", 13)==0 ){
1218           zIdx = &zDetail[i+13];
1219         }else if( i+22<nDetail
1220             && memcmp(&zDetail[i], " USING COVERING INDEX ", 22)==0
1221         ){
1222           zIdx = &zDetail[i+22];
1223         }
1224         if( zIdx ){
1225           const char *zSql;
1226           int nIdx = 0;
1227           while( zIdx[nIdx]!='\0' && (zIdx[nIdx]!=' ' || zIdx[nIdx+1]!='(') ){
1228             nIdx++;
1229           }
1230           zSql = idxHashSearch(&p->hIdx, zIdx, nIdx);
1231           if( zSql ){
1232             idxHashAdd(&rc, &hIdx, zSql, 0);
1233             if( rc ) goto find_indexes_out;
1234           }
1235           break;
1236         }
1237       }
1238
1239       if( zDetail[0]!='-' ){
1240         pStmt->zEQP = idxAppendText(&rc, pStmt->zEQP, "%s\n", zDetail);
1241       }
1242     }
1243
1244     for(pEntry=hIdx.pFirst; pEntry; pEntry=pEntry->pNext){
1245       pStmt->zIdx = idxAppendText(&rc, pStmt->zIdx, "%s;\n", pEntry->zKey);
1246     }
1247
1248     idxFinalize(&rc, pExplain);
1249   }
1250
1251  find_indexes_out:
1252   idxHashClear(&hIdx);
1253   return rc;
1254 }
1255
1256 static int idxAuthCallback(
1257   void *pCtx,
1258   int eOp,
1259   const char *z3,
1260   const char *z4,
1261   const char *zDb,
1262   const char *zTrigger
1263 ){
1264   int rc = SQLITE_OK;
1265   (void)z4;
1266   (void)zTrigger;
1267   if( eOp==SQLITE_INSERT || eOp==SQLITE_UPDATE || eOp==SQLITE_DELETE ){
1268     if( sqlite3_stricmp(zDb, "main")==0 ){
1269       sqlite3expert *p = (sqlite3expert*)pCtx;
1270       IdxTable *pTab;
1271       for(pTab=p->pTable; pTab; pTab=pTab->pNext){
1272         if( 0==sqlite3_stricmp(z3, pTab->zName) ) break;
1273       }
1274       if( pTab ){
1275         IdxWrite *pWrite;
1276         for(pWrite=p->pWrite; pWrite; pWrite=pWrite->pNext){
1277           if( pWrite->pTab==pTab && pWrite->eOp==eOp ) break;
1278         }
1279         if( pWrite==0 ){
1280           pWrite = idxMalloc(&rc, sizeof(IdxWrite));
1281           if( rc==SQLITE_OK ){
1282             pWrite->pTab = pTab;
1283             pWrite->eOp = eOp;
1284             pWrite->pNext = p->pWrite;
1285             p->pWrite = pWrite;
1286           }
1287         }
1288       }
1289     }
1290   }
1291   return rc;
1292 }
1293
1294 static int idxProcessOneTrigger(
1295   sqlite3expert *p,
1296   IdxWrite *pWrite,
1297   char **pzErr
1298 ){
1299   static const char *zInt = UNIQUE_TABLE_NAME;
1300   static const char *zDrop = "DROP TABLE " UNIQUE_TABLE_NAME;
1301   IdxTable *pTab = pWrite->pTab;
1302   const char *zTab = pTab->zName;
1303   const char *zSql =
1304     "SELECT 'CREATE TEMP' || substr(sql, 7) FROM sqlite_schema "
1305     "WHERE tbl_name = %Q AND type IN ('table', 'trigger') "
1306     "ORDER BY type;";
1307   sqlite3_stmt *pSelect = 0;
1308   int rc = SQLITE_OK;
1309   char *zWrite = 0;
1310
1311   /* Create the table and its triggers in the temp schema */
1312   rc = idxPrintfPrepareStmt(p->db, &pSelect, pzErr, zSql, zTab, zTab);
1313   while( rc==SQLITE_OK && SQLITE_ROW==sqlite3_step(pSelect) ){
1314     const char *zCreate = (const char*)sqlite3_column_text(pSelect, 0);
1315     if( zCreate==0 ) continue;
1316     rc = sqlite3_exec(p->dbv, zCreate, 0, 0, pzErr);
1317   }
1318   idxFinalize(&rc, pSelect);
1319
1320   /* Rename the table in the temp schema to zInt */
1321   if( rc==SQLITE_OK ){
1322     char *z = sqlite3_mprintf("ALTER TABLE temp.%Q RENAME TO %Q", zTab, zInt);
1323     if( z==0 ){
1324       rc = SQLITE_NOMEM;
1325     }else{
1326       rc = sqlite3_exec(p->dbv, z, 0, 0, pzErr);
1327       sqlite3_free(z);
1328     }
1329   }
1330
1331   switch( pWrite->eOp ){
1332     case SQLITE_INSERT: {
1333       int i;
1334       zWrite = idxAppendText(&rc, zWrite, "INSERT INTO %Q VALUES(", zInt);
1335       for(i=0; i<pTab->nCol; i++){
1336         zWrite = idxAppendText(&rc, zWrite, "%s?", i==0 ? "" : ", ");
1337       }
1338       zWrite = idxAppendText(&rc, zWrite, ")");
1339       break;
1340     }
1341     case SQLITE_UPDATE: {
1342       int i;
1343       zWrite = idxAppendText(&rc, zWrite, "UPDATE %Q SET ", zInt);
1344       for(i=0; i<pTab->nCol; i++){
1345         zWrite = idxAppendText(&rc, zWrite, "%s%Q=?", i==0 ? "" : ", ",
1346             pTab->aCol[i].zName
1347         );
1348       }
1349       break;
1350     }
1351     default: {
1352       assert( pWrite->eOp==SQLITE_DELETE );
1353       if( rc==SQLITE_OK ){
1354         zWrite = sqlite3_mprintf("DELETE FROM %Q", zInt);
1355         if( zWrite==0 ) rc = SQLITE_NOMEM;
1356       }
1357     }
1358   }
1359
1360   if( rc==SQLITE_OK ){
1361     sqlite3_stmt *pX = 0;
1362     rc = sqlite3_prepare_v2(p->dbv, zWrite, -1, &pX, 0);
1363     idxFinalize(&rc, pX);
1364     if( rc!=SQLITE_OK ){
1365       idxDatabaseError(p->dbv, pzErr);
1366     }
1367   }
1368   sqlite3_free(zWrite);
1369
1370   if( rc==SQLITE_OK ){
1371     rc = sqlite3_exec(p->dbv, zDrop, 0, 0, pzErr);
1372   }
1373
1374   return rc;
1375 }
1376
1377 static int idxProcessTriggers(sqlite3expert *p, char **pzErr){
1378   int rc = SQLITE_OK;
1379   IdxWrite *pEnd = 0;
1380   IdxWrite *pFirst = p->pWrite;
1381
1382   while( rc==SQLITE_OK && pFirst!=pEnd ){
1383     IdxWrite *pIter;
1384     for(pIter=pFirst; rc==SQLITE_OK && pIter!=pEnd; pIter=pIter->pNext){
1385       rc = idxProcessOneTrigger(p, pIter, pzErr);
1386     }
1387     pEnd = pFirst;
1388     pFirst = p->pWrite;
1389   }
1390
1391   return rc;
1392 }
1393
1394
1395 static int idxCreateVtabSchema(sqlite3expert *p, char **pzErrmsg){
1396   int rc = idxRegisterVtab(p);
1397   sqlite3_stmt *pSchema = 0;
1398
1399   /* For each table in the main db schema:
1400   **
1401   **   1) Add an entry to the p->pTable list, and
1402   **   2) Create the equivalent virtual table in dbv.
1403   */
1404   rc = idxPrepareStmt(p->db, &pSchema, pzErrmsg,
1405       "SELECT type, name, sql, 1 FROM sqlite_schema "
1406       "WHERE type IN ('table','view') AND name NOT LIKE 'sqlite_%%' "
1407       " UNION ALL "
1408       "SELECT type, name, sql, 2 FROM sqlite_schema "
1409       "WHERE type = 'trigger'"
1410       "  AND tbl_name IN(SELECT name FROM sqlite_schema WHERE type = 'view') "
1411       "ORDER BY 4, 1"
1412   );
1413   while( rc==SQLITE_OK && SQLITE_ROW==sqlite3_step(pSchema) ){
1414     const char *zType = (const char*)sqlite3_column_text(pSchema, 0);
1415     const char *zName = (const char*)sqlite3_column_text(pSchema, 1);
1416     const char *zSql = (const char*)sqlite3_column_text(pSchema, 2);
1417
1418     if( zType==0 || zName==0 ) continue;
1419     if( zType[0]=='v' || zType[1]=='r' ){
1420       if( zSql ) rc = sqlite3_exec(p->dbv, zSql, 0, 0, pzErrmsg);
1421     }else{
1422       IdxTable *pTab;
1423       rc = idxGetTableInfo(p->db, zName, &pTab, pzErrmsg);
1424       if( rc==SQLITE_OK ){
1425         int i;
1426         char *zInner = 0;
1427         char *zOuter = 0;
1428         pTab->pNext = p->pTable;
1429         p->pTable = pTab;
1430
1431         /* The statement the vtab will pass to sqlite3_declare_vtab() */
1432         zInner = idxAppendText(&rc, 0, "CREATE TABLE x(");
1433         for(i=0; i<pTab->nCol; i++){
1434           zInner = idxAppendText(&rc, zInner, "%s%Q COLLATE %s",
1435               (i==0 ? "" : ", "), pTab->aCol[i].zName, pTab->aCol[i].zColl
1436           );
1437         }
1438         zInner = idxAppendText(&rc, zInner, ")");
1439
1440         /* The CVT statement to create the vtab */
1441         zOuter = idxAppendText(&rc, 0,
1442             "CREATE VIRTUAL TABLE %Q USING expert(%Q)", zName, zInner
1443         );
1444         if( rc==SQLITE_OK ){
1445           rc = sqlite3_exec(p->dbv, zOuter, 0, 0, pzErrmsg);
1446         }
1447         sqlite3_free(zInner);
1448         sqlite3_free(zOuter);
1449       }
1450     }
1451   }
1452   idxFinalize(&rc, pSchema);
1453   return rc;
1454 }
1455
1456 struct IdxSampleCtx {
1457   int iTarget;
1458   double target;                  /* Target nRet/nRow value */
1459   double nRow;                    /* Number of rows seen */
1460   double nRet;                    /* Number of rows returned */
1461 };
1462
1463 static void idxSampleFunc(
1464   sqlite3_context *pCtx,
1465   int argc,
1466   sqlite3_value **argv
1467 ){
1468   struct IdxSampleCtx *p = (struct IdxSampleCtx*)sqlite3_user_data(pCtx);
1469   int bRet;
1470
1471   (void)argv;
1472   assert( argc==0 );
1473   if( p->nRow==0.0 ){
1474     bRet = 1;
1475   }else{
1476     bRet = (p->nRet / p->nRow) <= p->target;
1477     if( bRet==0 ){
1478       unsigned short rnd;
1479       sqlite3_randomness(2, (void*)&rnd);
1480       bRet = ((int)rnd % 100) <= p->iTarget;
1481     }
1482   }
1483
1484   sqlite3_result_int(pCtx, bRet);
1485   p->nRow += 1.0;
1486   p->nRet += (double)bRet;
1487 }
1488
1489 struct IdxRemCtx {
1490   int nSlot;
1491   struct IdxRemSlot {
1492     int eType;                    /* SQLITE_NULL, INTEGER, REAL, TEXT, BLOB */
1493     i64 iVal;                     /* SQLITE_INTEGER value */
1494     double rVal;                  /* SQLITE_FLOAT value */
1495     int nByte;                    /* Bytes of space allocated at z */
1496     int n;                        /* Size of buffer z */
1497     char *z;                      /* SQLITE_TEXT/BLOB value */
1498   } aSlot[1];
1499 };
1500
1501 /*
1502 ** Implementation of scalar function rem().
1503 */
1504 static void idxRemFunc(
1505   sqlite3_context *pCtx,
1506   int argc,
1507   sqlite3_value **argv
1508 ){
1509   struct IdxRemCtx *p = (struct IdxRemCtx*)sqlite3_user_data(pCtx);
1510   struct IdxRemSlot *pSlot;
1511   int iSlot;
1512   assert( argc==2 );
1513
1514   iSlot = sqlite3_value_int(argv[0]);
1515   assert( iSlot<=p->nSlot );
1516   pSlot = &p->aSlot[iSlot];
1517
1518   switch( pSlot->eType ){
1519     case SQLITE_NULL:
1520       /* no-op */
1521       break;
1522
1523     case SQLITE_INTEGER:
1524       sqlite3_result_int64(pCtx, pSlot->iVal);
1525       break;
1526
1527     case SQLITE_FLOAT:
1528       sqlite3_result_double(pCtx, pSlot->rVal);
1529       break;
1530
1531     case SQLITE_BLOB:
1532       sqlite3_result_blob(pCtx, pSlot->z, pSlot->n, SQLITE_TRANSIENT);
1533       break;
1534
1535     case SQLITE_TEXT:
1536       sqlite3_result_text(pCtx, pSlot->z, pSlot->n, SQLITE_TRANSIENT);
1537       break;
1538   }
1539
1540   pSlot->eType = sqlite3_value_type(argv[1]);
1541   switch( pSlot->eType ){
1542     case SQLITE_NULL:
1543       /* no-op */
1544       break;
1545
1546     case SQLITE_INTEGER:
1547       pSlot->iVal = sqlite3_value_int64(argv[1]);
1548       break;
1549
1550     case SQLITE_FLOAT:
1551       pSlot->rVal = sqlite3_value_double(argv[1]);
1552       break;
1553
1554     case SQLITE_BLOB:
1555     case SQLITE_TEXT: {
1556       int nByte = sqlite3_value_bytes(argv[1]);
1557       const void *pData = 0;
1558       if( nByte>pSlot->nByte ){
1559         char *zNew = (char*)sqlite3_realloc(pSlot->z, nByte*2);
1560         if( zNew==0 ){
1561           sqlite3_result_error_nomem(pCtx);
1562           return;
1563         }
1564         pSlot->nByte = nByte*2;
1565         pSlot->z = zNew;
1566       }
1567       pSlot->n = nByte;
1568       if( pSlot->eType==SQLITE_BLOB ){
1569         pData = sqlite3_value_blob(argv[1]);
1570         if( pData ) memcpy(pSlot->z, pData, nByte);
1571       }else{
1572         pData = sqlite3_value_text(argv[1]);
1573         memcpy(pSlot->z, pData, nByte);
1574       }
1575       break;
1576     }
1577   }
1578 }
1579
1580 static int idxLargestIndex(sqlite3 *db, int *pnMax, char **pzErr){
1581   int rc = SQLITE_OK;
1582   const char *zMax =
1583     "SELECT max(i.seqno) FROM "
1584     "  sqlite_schema AS s, "
1585     "  pragma_index_list(s.name) AS l, "
1586     "  pragma_index_info(l.name) AS i "
1587     "WHERE s.type = 'table'";
1588   sqlite3_stmt *pMax = 0;
1589
1590   *pnMax = 0;
1591   rc = idxPrepareStmt(db, &pMax, pzErr, zMax);
1592   if( rc==SQLITE_OK && SQLITE_ROW==sqlite3_step(pMax) ){
1593     *pnMax = sqlite3_column_int(pMax, 0) + 1;
1594   }
1595   idxFinalize(&rc, pMax);
1596
1597   return rc;
1598 }
1599
1600 static int idxPopulateOneStat1(
1601   sqlite3expert *p,
1602   sqlite3_stmt *pIndexXInfo,
1603   sqlite3_stmt *pWriteStat,
1604   const char *zTab,
1605   const char *zIdx,
1606   char **pzErr
1607 ){
1608   char *zCols = 0;
1609   char *zOrder = 0;
1610   char *zQuery = 0;
1611   int nCol = 0;
1612   int i;
1613   sqlite3_stmt *pQuery = 0;
1614   int *aStat = 0;
1615   int rc = SQLITE_OK;
1616
1617   assert( p->iSample>0 );
1618
1619   /* Formulate the query text */
1620   sqlite3_bind_text(pIndexXInfo, 1, zIdx, -1, SQLITE_STATIC);
1621   while( SQLITE_OK==rc && SQLITE_ROW==sqlite3_step(pIndexXInfo) ){
1622     const char *zComma = zCols==0 ? "" : ", ";
1623     const char *zName = (const char*)sqlite3_column_text(pIndexXInfo, 0);
1624     const char *zColl = (const char*)sqlite3_column_text(pIndexXInfo, 1);
1625     zCols = idxAppendText(&rc, zCols,
1626         "%sx.%Q IS rem(%d, x.%Q) COLLATE %s", zComma, zName, nCol, zName, zColl
1627     );
1628     zOrder = idxAppendText(&rc, zOrder, "%s%d", zComma, ++nCol);
1629   }
1630   sqlite3_reset(pIndexXInfo);
1631   if( rc==SQLITE_OK ){
1632     if( p->iSample==100 ){
1633       zQuery = sqlite3_mprintf(
1634           "SELECT %s FROM %Q x ORDER BY %s", zCols, zTab, zOrder
1635       );
1636     }else{
1637       zQuery = sqlite3_mprintf(
1638           "SELECT %s FROM temp."UNIQUE_TABLE_NAME" x ORDER BY %s", zCols, zOrder
1639       );
1640     }
1641   }
1642   sqlite3_free(zCols);
1643   sqlite3_free(zOrder);
1644
1645   /* Formulate the query text */
1646   if( rc==SQLITE_OK ){
1647     sqlite3 *dbrem = (p->iSample==100 ? p->db : p->dbv);
1648     rc = idxPrepareStmt(dbrem, &pQuery, pzErr, zQuery);
1649   }
1650   sqlite3_free(zQuery);
1651
1652   if( rc==SQLITE_OK ){
1653     aStat = (int*)idxMalloc(&rc, sizeof(int)*(nCol+1));
1654   }
1655   if( rc==SQLITE_OK && SQLITE_ROW==sqlite3_step(pQuery) ){
1656     IdxHashEntry *pEntry;
1657     char *zStat = 0;
1658     for(i=0; i<=nCol; i++) aStat[i] = 1;
1659     while( rc==SQLITE_OK && SQLITE_ROW==sqlite3_step(pQuery) ){
1660       aStat[0]++;
1661       for(i=0; i<nCol; i++){
1662         if( sqlite3_column_int(pQuery, i)==0 ) break;
1663       }
1664       for(/*no-op*/; i<nCol; i++){
1665         aStat[i+1]++;
1666       }
1667     }
1668
1669     if( rc==SQLITE_OK ){
1670       int s0 = aStat[0];
1671       zStat = sqlite3_mprintf("%d", s0);
1672       if( zStat==0 ) rc = SQLITE_NOMEM;
1673       for(i=1; rc==SQLITE_OK && i<=nCol; i++){
1674         zStat = idxAppendText(&rc, zStat, " %d", (s0+aStat[i]/2) / aStat[i]);
1675       }
1676     }
1677
1678     if( rc==SQLITE_OK ){
1679       sqlite3_bind_text(pWriteStat, 1, zTab, -1, SQLITE_STATIC);
1680       sqlite3_bind_text(pWriteStat, 2, zIdx, -1, SQLITE_STATIC);
1681       sqlite3_bind_text(pWriteStat, 3, zStat, -1, SQLITE_STATIC);
1682       sqlite3_step(pWriteStat);
1683       rc = sqlite3_reset(pWriteStat);
1684     }
1685
1686     pEntry = idxHashFind(&p->hIdx, zIdx, STRLEN(zIdx));
1687     if( pEntry ){
1688       assert( pEntry->zVal2==0 );
1689       pEntry->zVal2 = zStat;
1690     }else{
1691       sqlite3_free(zStat);
1692     }
1693   }
1694   sqlite3_free(aStat);
1695   idxFinalize(&rc, pQuery);
1696
1697   return rc;
1698 }
1699
1700 static int idxBuildSampleTable(sqlite3expert *p, const char *zTab){
1701   int rc;
1702   char *zSql;
1703
1704   rc = sqlite3_exec(p->dbv,"DROP TABLE IF EXISTS temp."UNIQUE_TABLE_NAME,0,0,0);
1705   if( rc!=SQLITE_OK ) return rc;
1706
1707   zSql = sqlite3_mprintf(
1708       "CREATE TABLE temp." UNIQUE_TABLE_NAME " AS SELECT * FROM %Q", zTab
1709   );
1710   if( zSql==0 ) return SQLITE_NOMEM;
1711   rc = sqlite3_exec(p->dbv, zSql, 0, 0, 0);
1712   sqlite3_free(zSql);
1713
1714   return rc;
1715 }
1716
1717 /*
1718 ** This function is called as part of sqlite3_expert_analyze(). Candidate
1719 ** indexes have already been created in database sqlite3expert.dbm, this
1720 ** function populates sqlite_stat1 table in the same database.
1721 **
1722 ** The stat1 data is generated by querying the
1723 */
1724 static int idxPopulateStat1(sqlite3expert *p, char **pzErr){
1725   int rc = SQLITE_OK;
1726   int nMax =0;
1727   struct IdxRemCtx *pCtx = 0;
1728   struct IdxSampleCtx samplectx;
1729   int i;
1730   i64 iPrev = -100000;
1731   sqlite3_stmt *pAllIndex = 0;
1732   sqlite3_stmt *pIndexXInfo = 0;
1733   sqlite3_stmt *pWrite = 0;
1734
1735   const char *zAllIndex =
1736     "SELECT s.rowid, s.name, l.name FROM "
1737     "  sqlite_schema AS s, "
1738     "  pragma_index_list(s.name) AS l "
1739     "WHERE s.type = 'table'";
1740   const char *zIndexXInfo =
1741     "SELECT name, coll FROM pragma_index_xinfo(?) WHERE key";
1742   const char *zWrite = "INSERT INTO sqlite_stat1 VALUES(?, ?, ?)";
1743
1744   /* If iSample==0, no sqlite_stat1 data is required. */
1745   if( p->iSample==0 ) return SQLITE_OK;
1746
1747   rc = idxLargestIndex(p->dbm, &nMax, pzErr);
1748   if( nMax<=0 || rc!=SQLITE_OK ) return rc;
1749
1750   rc = sqlite3_exec(p->dbm, "ANALYZE; PRAGMA writable_schema=1", 0, 0, 0);
1751
1752   if( rc==SQLITE_OK ){
1753     int nByte = sizeof(struct IdxRemCtx) + (sizeof(struct IdxRemSlot) * nMax);
1754     pCtx = (struct IdxRemCtx*)idxMalloc(&rc, nByte);
1755   }
1756
1757   if( rc==SQLITE_OK ){
1758     sqlite3 *dbrem = (p->iSample==100 ? p->db : p->dbv);
1759     rc = sqlite3_create_function(
1760         dbrem, "rem", 2, SQLITE_UTF8, (void*)pCtx, idxRemFunc, 0, 0
1761     );
1762   }
1763   if( rc==SQLITE_OK ){
1764     rc = sqlite3_create_function(
1765         p->db, "sample", 0, SQLITE_UTF8, (void*)&samplectx, idxSampleFunc, 0, 0
1766     );
1767   }
1768
1769   if( rc==SQLITE_OK ){
1770     pCtx->nSlot = nMax+1;
1771     rc = idxPrepareStmt(p->dbm, &pAllIndex, pzErr, zAllIndex);
1772   }
1773   if( rc==SQLITE_OK ){
1774     rc = idxPrepareStmt(p->dbm, &pIndexXInfo, pzErr, zIndexXInfo);
1775   }
1776   if( rc==SQLITE_OK ){
1777     rc = idxPrepareStmt(p->dbm, &pWrite, pzErr, zWrite);
1778   }
1779
1780   while( rc==SQLITE_OK && SQLITE_ROW==sqlite3_step(pAllIndex) ){
1781     i64 iRowid = sqlite3_column_int64(pAllIndex, 0);
1782     const char *zTab = (const char*)sqlite3_column_text(pAllIndex, 1);
1783     const char *zIdx = (const char*)sqlite3_column_text(pAllIndex, 2);
1784     if( zTab==0 || zIdx==0 ) continue;
1785     if( p->iSample<100 && iPrev!=iRowid ){
1786       samplectx.target = (double)p->iSample / 100.0;
1787       samplectx.iTarget = p->iSample;
1788       samplectx.nRow = 0.0;
1789       samplectx.nRet = 0.0;
1790       rc = idxBuildSampleTable(p, zTab);
1791       if( rc!=SQLITE_OK ) break;
1792     }
1793     rc = idxPopulateOneStat1(p, pIndexXInfo, pWrite, zTab, zIdx, pzErr);
1794     iPrev = iRowid;
1795   }
1796   if( rc==SQLITE_OK && p->iSample<100 ){
1797     rc = sqlite3_exec(p->dbv,
1798         "DROP TABLE IF EXISTS temp." UNIQUE_TABLE_NAME, 0,0,0
1799     );
1800   }
1801
1802   idxFinalize(&rc, pAllIndex);
1803   idxFinalize(&rc, pIndexXInfo);
1804   idxFinalize(&rc, pWrite);
1805
1806   if( pCtx ){
1807     for(i=0; i<pCtx->nSlot; i++){
1808       sqlite3_free(pCtx->aSlot[i].z);
1809     }
1810     sqlite3_free(pCtx);
1811   }
1812
1813   if( rc==SQLITE_OK ){
1814     rc = sqlite3_exec(p->dbm, "ANALYZE sqlite_schema", 0, 0, 0);
1815   }
1816
1817   sqlite3_exec(p->db, "DROP TABLE IF EXISTS temp."UNIQUE_TABLE_NAME,0,0,0);
1818   return rc;
1819 }
1820
1821 /*
1822 ** Allocate a new sqlite3expert object.
1823 */
1824 sqlite3expert *sqlite3_expert_new(sqlite3 *db, char **pzErrmsg){
1825   int rc = SQLITE_OK;
1826   sqlite3expert *pNew;
1827
1828   pNew = (sqlite3expert*)idxMalloc(&rc, sizeof(sqlite3expert));
1829
1830   /* Open two in-memory databases to work with. The "vtab database" (dbv)
1831   ** will contain a virtual table corresponding to each real table in
1832   ** the user database schema, and a copy of each view. It is used to
1833   ** collect information regarding the WHERE, ORDER BY and other clauses
1834   ** of the user's query.
1835   */
1836   if( rc==SQLITE_OK ){
1837     pNew->db = db;
1838     pNew->iSample = 100;
1839     rc = sqlite3_open(":memory:", &pNew->dbv);
1840   }
1841   if( rc==SQLITE_OK ){
1842     rc = sqlite3_open(":memory:", &pNew->dbm);
1843     if( rc==SQLITE_OK ){
1844       sqlite3_db_config(pNew->dbm, SQLITE_DBCONFIG_TRIGGER_EQP, 1, (int*)0);
1845     }
1846   }
1847
1848
1849   /* Copy the entire schema of database [db] into [dbm]. */
1850   if( rc==SQLITE_OK ){
1851     sqlite3_stmt *pSql = 0;
1852     rc = idxPrintfPrepareStmt(pNew->db, &pSql, pzErrmsg,
1853         "SELECT sql FROM sqlite_schema WHERE name NOT LIKE 'sqlite_%%'"
1854         " AND sql NOT LIKE 'CREATE VIRTUAL %%'"
1855     );
1856     while( rc==SQLITE_OK && SQLITE_ROW==sqlite3_step(pSql) ){
1857       const char *zSql = (const char*)sqlite3_column_text(pSql, 0);
1858       if( zSql ) rc = sqlite3_exec(pNew->dbm, zSql, 0, 0, pzErrmsg);
1859     }
1860     idxFinalize(&rc, pSql);
1861   }
1862
1863   /* Create the vtab schema */
1864   if( rc==SQLITE_OK ){
1865     rc = idxCreateVtabSchema(pNew, pzErrmsg);
1866   }
1867
1868   /* Register the auth callback with dbv */
1869   if( rc==SQLITE_OK ){
1870     sqlite3_set_authorizer(pNew->dbv, idxAuthCallback, (void*)pNew);
1871   }
1872
1873   /* If an error has occurred, free the new object and reutrn NULL. Otherwise,
1874   ** return the new sqlite3expert handle.  */
1875   if( rc!=SQLITE_OK ){
1876     sqlite3_expert_destroy(pNew);
1877     pNew = 0;
1878   }
1879   return pNew;
1880 }
1881
1882 /*
1883 ** Configure an sqlite3expert object.
1884 */
1885 int sqlite3_expert_config(sqlite3expert *p, int op, ...){
1886   int rc = SQLITE_OK;
1887   va_list ap;
1888   va_start(ap, op);
1889   switch( op ){
1890     case EXPERT_CONFIG_SAMPLE: {
1891       int iVal = va_arg(ap, int);
1892       if( iVal<0 ) iVal = 0;
1893       if( iVal>100 ) iVal = 100;
1894       p->iSample = iVal;
1895       break;
1896     }
1897     default:
1898       rc = SQLITE_NOTFOUND;
1899       break;
1900   }
1901
1902   va_end(ap);
1903   return rc;
1904 }
1905
1906 /*
1907 ** Add an SQL statement to the analysis.
1908 */
1909 int sqlite3_expert_sql(
1910   sqlite3expert *p,               /* From sqlite3_expert_new() */
1911   const char *zSql,               /* SQL statement to add */
1912   char **pzErr                    /* OUT: Error message (if any) */
1913 ){
1914   IdxScan *pScanOrig = p->pScan;
1915   IdxStatement *pStmtOrig = p->pStatement;
1916   int rc = SQLITE_OK;
1917   const char *zStmt = zSql;
1918
1919   if( p->bRun ) return SQLITE_MISUSE;
1920
1921   while( rc==SQLITE_OK && zStmt && zStmt[0] ){
1922     sqlite3_stmt *pStmt = 0;
1923     rc = sqlite3_prepare_v2(p->dbv, zStmt, -1, &pStmt, &zStmt);
1924     if( rc==SQLITE_OK ){
1925       if( pStmt ){
1926         IdxStatement *pNew;
1927         const char *z = sqlite3_sql(pStmt);
1928         int n = STRLEN(z);
1929         pNew = (IdxStatement*)idxMalloc(&rc, sizeof(IdxStatement) + n+1);
1930         if( rc==SQLITE_OK ){
1931           pNew->zSql = (char*)&pNew[1];
1932           memcpy(pNew->zSql, z, n+1);
1933           pNew->pNext = p->pStatement;
1934           if( p->pStatement ) pNew->iId = p->pStatement->iId+1;
1935           p->pStatement = pNew;
1936         }
1937         sqlite3_finalize(pStmt);
1938       }
1939     }else{
1940       idxDatabaseError(p->dbv, pzErr);
1941     }
1942   }
1943
1944   if( rc!=SQLITE_OK ){
1945     idxScanFree(p->pScan, pScanOrig);
1946     idxStatementFree(p->pStatement, pStmtOrig);
1947     p->pScan = pScanOrig;
1948     p->pStatement = pStmtOrig;
1949   }
1950
1951   return rc;
1952 }
1953
1954 int sqlite3_expert_analyze(sqlite3expert *p, char **pzErr){
1955   int rc;
1956   IdxHashEntry *pEntry;
1957
1958   /* Do trigger processing to collect any extra IdxScan structures */
1959   rc = idxProcessTriggers(p, pzErr);
1960
1961   /* Create candidate indexes within the in-memory database file */
1962   if( rc==SQLITE_OK ){
1963     rc = idxCreateCandidates(p);
1964   }else if ( rc==SQLITE_BUSY_TIMEOUT ){
1965     if( pzErr )
1966       *pzErr = sqlite3_mprintf("Cannot find a unique index name to propose.");
1967     return rc;
1968   }
1969
1970   /* Generate the stat1 data */
1971   if( rc==SQLITE_OK ){
1972     rc = idxPopulateStat1(p, pzErr);
1973   }
1974
1975   /* Formulate the EXPERT_REPORT_CANDIDATES text */
1976   for(pEntry=p->hIdx.pFirst; pEntry; pEntry=pEntry->pNext){
1977     p->zCandidates = idxAppendText(&rc, p->zCandidates,
1978         "%s;%s%s\n", pEntry->zVal,
1979         pEntry->zVal2 ? " -- stat1: " : "", pEntry->zVal2
1980     );
1981   }
1982
1983   /* Figure out which of the candidate indexes are preferred by the query
1984   ** planner and report the results to the user.  */
1985   if( rc==SQLITE_OK ){
1986     rc = idxFindIndexes(p, pzErr);
1987   }
1988
1989   if( rc==SQLITE_OK ){
1990     p->bRun = 1;
1991   }
1992   return rc;
1993 }
1994
1995 /*
1996 ** Return the total number of statements that have been added to this
1997 ** sqlite3expert using sqlite3_expert_sql().
1998 */
1999 int sqlite3_expert_count(sqlite3expert *p){
2000   int nRet = 0;
2001   if( p->pStatement ) nRet = p->pStatement->iId+1;
2002   return nRet;
2003 }
2004
2005 /*
2006 ** Return a component of the report.
2007 */
2008 const char *sqlite3_expert_report(sqlite3expert *p, int iStmt, int eReport){
2009   const char *zRet = 0;
2010   IdxStatement *pStmt;
2011
2012   if( p->bRun==0 ) return 0;
2013   for(pStmt=p->pStatement; pStmt && pStmt->iId!=iStmt; pStmt=pStmt->pNext);
2014   switch( eReport ){
2015     case EXPERT_REPORT_SQL:
2016       if( pStmt ) zRet = pStmt->zSql;
2017       break;
2018     case EXPERT_REPORT_INDEXES:
2019       if( pStmt ) zRet = pStmt->zIdx;
2020       break;
2021     case EXPERT_REPORT_PLAN:
2022       if( pStmt ) zRet = pStmt->zEQP;
2023       break;
2024     case EXPERT_REPORT_CANDIDATES:
2025       zRet = p->zCandidates;
2026       break;
2027   }
2028   return zRet;
2029 }
2030
2031 /*
2032 ** Free an sqlite3expert object.
2033 */
2034 void sqlite3_expert_destroy(sqlite3expert *p){
2035   if( p ){
2036     sqlite3_close(p->dbm);
2037     sqlite3_close(p->dbv);
2038     idxScanFree(p->pScan, 0);
2039     idxStatementFree(p->pStatement, 0);
2040     idxTableFree(p->pTable);
2041     idxWriteFree(p->pWrite);
2042     idxHashClear(&p->hIdx);
2043     sqlite3_free(p->zCandidates);
2044     sqlite3_free(p);
2045   }
2046 }
2047
2048 #endif /* ifndef SQLITE_OMIT_VIRTUALTABLE */