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 = STRLEN(zTab);
 701   int nByte = sizeof(IdxTable) + nTab + 1;
 702   IdxTable *pNew = 0;
 703   int rc, rc2;
 704   char *pCsr = 0;
 705   int nPk = 0;
 706
 707   rc = idxPrintfPrepareStmt(db, &p1, pzErrmsg, "PRAGMA table_xinfo=%Q", zTab);
 708   while( rc==SQLITE_OK && SQLITE_ROW==sqlite3_step(p1) ){
 709     const char *zCol = (const char*)sqlite3_column_text(p1, 1);
 710     const char *zColSeq = 0;
 711     nByte += 1 + STRLEN(zCol);
 712     rc = sqlite3_table_column_metadata(
 713         db, "main", zTab, zCol, 0, &zColSeq, 0, 0, 0
 714     );
 715     if( zColSeq==0 ) zColSeq = "binary";
 716     nByte += 1 + STRLEN(zColSeq);
 717     nCol++;
 718     nPk += (sqlite3_column_int(p1, 5)>0);
 719   }
 720   rc2 = sqlite3_reset(p1);
 721   if( rc==SQLITE_OK ) rc = rc2;
 722
 723   nByte += sizeof(IdxColumn) * nCol;
 724   if( rc==SQLITE_OK ){
 725     pNew = idxMalloc(&rc, nByte);
 726   }
 727   if( rc==SQLITE_OK ){
 728     pNew->aCol = (IdxColumn*)&pNew[1];
 729     pNew->nCol = nCol;
 730     pCsr = (char*)&pNew->aCol[nCol];
 731   }
 732
 733   nCol = 0;
 734   while( rc==SQLITE_OK && SQLITE_ROW==sqlite3_step(p1) ){
 735     const char *zCol = (const char*)sqlite3_column_text(p1, 1);
 736     const char *zColSeq = 0;
 737     int nCopy = STRLEN(zCol) + 1;
 738     pNew->aCol[nCol].zName = pCsr;
 739     pNew->aCol[nCol].iPk = (sqlite3_column_int(p1, 5)==1 && nPk==1);
 740     memcpy(pCsr, zCol, nCopy);
 741     pCsr += nCopy;
 742
 743     rc = sqlite3_table_column_metadata(
 744         db, "main", zTab, zCol, 0, &zColSeq, 0, 0, 0
 745     );
 746     if( rc==SQLITE_OK ){
 747       if( zColSeq==0 ) zColSeq = "binary";
 748       nCopy = STRLEN(zColSeq) + 1;
 749       pNew->aCol[nCol].zColl = pCsr;
 750       memcpy(pCsr, zColSeq, nCopy);
 751       pCsr += nCopy;
 752     }
 753
 754     nCol++;
 755   }
 756   idxFinalize(&rc, p1);
 757
 758   if( rc!=SQLITE_OK ){
 759     sqlite3_free(pNew);
 760     pNew = 0;
 761   }else if( ALWAYS(pNew!=0) ){
 762     pNew->zName = pCsr;
 763     if( ALWAYS(pNew->zName!=0) ) memcpy(pNew->zName, zTab, nTab+1);
 764   }
 765
 766   *ppOut = pNew;
 767   return rc;
 768 }
 769
 770 /*
 771 ** This function is a no-op if *pRc is set to anything other than
 772 ** SQLITE_OK when it is called.
 773 **
 774 ** If *pRc is initially set to SQLITE_OK, then the text specified by
 775 ** the printf() style arguments is appended to zIn and the result returned
 776 ** in a buffer allocated by sqlite3_malloc(). sqlite3_free() is called on
 777 ** zIn before returning.
 778 */
 779 static char *idxAppendText(int *pRc, char *zIn, const char *zFmt, ...){
 780   va_list ap;
 781   char *zAppend = 0;
 782   char *zRet = 0;
 783   int nIn = zIn ? STRLEN(zIn) : 0;
 784   int nAppend = 0;
 785   va_start(ap, zFmt);
 786   if( *pRc==SQLITE_OK ){
 787     zAppend = sqlite3_vmprintf(zFmt, ap);
 788     if( zAppend ){
 789       nAppend = STRLEN(zAppend);
 790       zRet = (char*)sqlite3_malloc(nIn + nAppend + 1);
 791     }
 792     if( zAppend && zRet ){
 793       if( nIn ) memcpy(zRet, zIn, nIn);
 794       memcpy(&zRet[nIn], zAppend, nAppend+1);
 795     }else{
 796       sqlite3_free(zRet);
 797       zRet = 0;
 798       *pRc = SQLITE_NOMEM;
 799     }
 800     sqlite3_free(zAppend);
 801     sqlite3_free(zIn);
 802   }
 803   va_end(ap);
 804   return zRet;
 805 }
 806
 807 /*
 808 ** Return true if zId must be quoted in order to use it as an SQL
 809 ** identifier, or false otherwise.
 810 */
 811 static int idxIdentifierRequiresQuotes(const char *zId){
 812   int i;
 813   for(i=0; zId[i]; i++){
 814     if( !(zId[i]=='_')
 815      && !(zId[i]>='0' && zId[i]<='9')
 816      && !(zId[i]>='a' && zId[i]<='z')
 817      && !(zId[i]>='A' && zId[i]<='Z')
 818     ){
 819       return 1;
 820     }
 821   }
 822   return 0;
 823 }
 824
 825 /*
 826 ** This function appends an index column definition suitable for constraint
 827 ** pCons to the string passed as zIn and returns the result.
 828 */
 829 static char *idxAppendColDefn(
 830   int *pRc,                       /* IN/OUT: Error code */
 831   char *zIn,                      /* Column defn accumulated so far */
 832   IdxTable *pTab,                 /* Table index will be created on */
 833   IdxConstraint *pCons
 834 ){
 835   char *zRet = zIn;
 836   IdxColumn *p = &pTab->aCol[pCons->iCol];
 837   if( zRet ) zRet = idxAppendText(pRc, zRet, ", ");
 838
 839   if( idxIdentifierRequiresQuotes(p->zName) ){
 840     zRet = idxAppendText(pRc, zRet, "%Q", p->zName);
 841   }else{
 842     zRet = idxAppendText(pRc, zRet, "%s", p->zName);
 843   }
 844
 845   if( sqlite3_stricmp(p->zColl, pCons->zColl) ){
 846     if( idxIdentifierRequiresQuotes(pCons->zColl) ){
 847       zRet = idxAppendText(pRc, zRet, " COLLATE %Q", pCons->zColl);
 848     }else{
 849       zRet = idxAppendText(pRc, zRet, " COLLATE %s", pCons->zColl);
 850     }
 851   }
 852
 853   if( pCons->bDesc ){
 854     zRet = idxAppendText(pRc, zRet, " DESC");
 855   }
 856   return zRet;
 857 }
 858
 859 /*
 860 ** Search database dbm for an index compatible with the one idxCreateFromCons()
 861 ** would create from arguments pScan, pEq and pTail. If no error occurs and
 862 ** such an index is found, return non-zero. Or, if no such index is found,
 863 ** return zero.
 864 **
 865 ** If an error occurs, set *pRc to an SQLite error code and return zero.
 866 */
 867 static int idxFindCompatible(
 868   int *pRc,                       /* OUT: Error code */
 869   sqlite3* dbm,                   /* Database to search */
 870   IdxScan *pScan,                 /* Scan for table to search for index on */
 871   IdxConstraint *pEq,             /* List of == constraints */
 872   IdxConstraint *pTail            /* List of range constraints */
 873 ){
 874   const char *zTbl = pScan->pTab->zName;
 875   sqlite3_stmt *pIdxList = 0;
 876   IdxConstraint *pIter;
 877   int nEq = 0;                    /* Number of elements in pEq */
 878   int rc;
 879
 880   /* Count the elements in list pEq */
 881   for(pIter=pEq; pIter; pIter=pIter->pLink) nEq++;
 882
 883   rc = idxPrintfPrepareStmt(dbm, &pIdxList, 0, "PRAGMA index_list=%Q", zTbl);
 884   while( rc==SQLITE_OK && sqlite3_step(pIdxList)==SQLITE_ROW ){
 885     int bMatch = 1;
 886     IdxConstraint *pT = pTail;
 887     sqlite3_stmt *pInfo = 0;
 888     const char *zIdx = (const char*)sqlite3_column_text(pIdxList, 1);
 889
 890     /* Zero the IdxConstraint.bFlag values in the pEq list */
 891     for(pIter=pEq; pIter; pIter=pIter->pLink) pIter->bFlag = 0;
 892
 893     rc = idxPrintfPrepareStmt(dbm, &pInfo, 0, "PRAGMA index_xInfo=%Q", zIdx);
 894     while( rc==SQLITE_OK && sqlite3_step(pInfo)==SQLITE_ROW ){
 895       int iIdx = sqlite3_column_int(pInfo, 0);
 896       int iCol = sqlite3_column_int(pInfo, 1);
 897       const char *zColl = (const char*)sqlite3_column_text(pInfo, 4);
 898
 899       if( iIdx<nEq ){
 900         for(pIter=pEq; pIter; pIter=pIter->pLink){
 901           if( pIter->bFlag ) continue;
 902           if( pIter->iCol!=iCol ) continue;
 903           if( sqlite3_stricmp(pIter->zColl, zColl) ) continue;
 904           pIter->bFlag = 1;
 905           break;
 906         }
 907         if( pIter==0 ){
 908           bMatch = 0;
 909           break;
 910         }
 911       }else{
 912         if( pT ){
 913           if( pT->iCol!=iCol || sqlite3_stricmp(pT->zColl, zColl) ){
 914             bMatch = 0;
 915             break;
 916           }
 917           pT = pT->pLink;
 918         }
 919       }
 920     }
 921     idxFinalize(&rc, pInfo);
 922
 923     if( rc==SQLITE_OK && bMatch ){
 924       sqlite3_finalize(pIdxList);
 925       return 1;
 926     }
 927   }
 928   idxFinalize(&rc, pIdxList);
 929
 930   *pRc = rc;
 931   return 0;
 932 }
 933
 934 /* Callback for sqlite3_exec() with query with leading count(*) column.
 935  * The first argument is expected to be an int*, referent to be incremented
 936  * if that leading column is not exactly '0'.
 937  */
 938 static int countNonzeros(void* pCount, int nc,
 939                          char* azResults[], char* azColumns[]){
 940   (void)azColumns;  /* Suppress unused parameter warning */
 941   if( nc>0 && (azResults[0][0]!='0' || azResults[0][1]!=0) ){
 942     *((int *)pCount) += 1;
 943   }
 944   return 0;
 945 }
 946
 947 static int idxCreateFromCons(
 948   sqlite3expert *p,
 949   IdxScan *pScan,
 950   IdxConstraint *pEq,
 951   IdxConstraint *pTail
 952 ){
 953   sqlite3 *dbm = p->dbm;
 954   int rc = SQLITE_OK;
 955   if( (pEq || pTail) && 0==idxFindCompatible(&rc, dbm, pScan, pEq, pTail) ){
 956     IdxTable *pTab = pScan->pTab;
 957     char *zCols = 0;
 958     char *zIdx = 0;
 959     IdxConstraint *pCons;
 960     unsigned int h = 0;
 961     const char *zFmt;
 962
 963     for(pCons=pEq; pCons; pCons=pCons->pLink){
 964       zCols = idxAppendColDefn(&rc, zCols, pTab, pCons);
 965     }
 966     for(pCons=pTail; pCons; pCons=pCons->pLink){
 967       zCols = idxAppendColDefn(&rc, zCols, pTab, pCons);
 968     }
 969
 970     if( rc==SQLITE_OK ){
 971       /* Hash the list of columns to come up with a name for the index */
 972       const char *zTable = pScan->pTab->zName;
 973       int quoteTable = idxIdentifierRequiresQuotes(zTable);
 974       char *zName = 0;          /* Index name */
 975       int collisions = 0;
 976       do{
 977         int i;
 978         char *zFind;
 979         for(i=0; zCols[i]; i++){
 980           h += ((h<<3) + zCols[i]);
 981         }
 982         sqlite3_free(zName);
 983         zName = sqlite3_mprintf("%s_idx_%08x", zTable, h);
 984         if( zName==0 ) break;
 985         /* Is is unique among table, view and index names? */
 986         zFmt = "SELECT count(*) FROM sqlite_schema WHERE name=%Q"
 987           " AND type in ('index','table','view')";
 988         zFind = sqlite3_mprintf(zFmt, zName);
 989         i = 0;
 990         rc = sqlite3_exec(dbm, zFind, countNonzeros, &i, 0);
 991         assert(rc==SQLITE_OK);
 992         sqlite3_free(zFind);
 993         if( i==0 ){
 994           collisions = 0;
 995           break;
 996         }
 997         ++collisions;
 998       }while( collisions<50 && zName!=0 );
 999       if( collisions ){
1000         /* This return means "Gave up trying to find a unique index name." */
1001         rc = SQLITE_BUSY_TIMEOUT;
1002       }else if( zName==0 ){
1003         rc = SQLITE_NOMEM;
1004       }else{
1005         if( quoteTable ){
1006           zFmt = "CREATE INDEX \"%w\" ON \"%w\"(%s)";
1007         }else{
1008           zFmt = "CREATE INDEX %s ON %s(%s)";
1009         }
1010         zIdx = sqlite3_mprintf(zFmt, zName, zTable, zCols);
1011         if( !zIdx ){
1012           rc = SQLITE_NOMEM;
1013         }else{
1014           rc = sqlite3_exec(dbm, zIdx, 0, 0, p->pzErrmsg);
1015           if( rc!=SQLITE_OK ){
1016             rc = SQLITE_BUSY_TIMEOUT;
1017           }else{
1018             idxHashAdd(&rc, &p->hIdx, zName, zIdx);
1019           }
1020         }
1021         sqlite3_free(zName);
1022         sqlite3_free(zIdx);
1023       }
1024     }
1025
1026     sqlite3_free(zCols);
1027   }
1028   return rc;
1029 }
1030
1031 /*
1032 ** Return true if list pList (linked by IdxConstraint.pLink) contains
1033 ** a constraint compatible with *p. Otherwise return false.
1034 */
1035 static int idxFindConstraint(IdxConstraint *pList, IdxConstraint *p){
1036   IdxConstraint *pCmp;
1037   for(pCmp=pList; pCmp; pCmp=pCmp->pLink){
1038     if( p->iCol==pCmp->iCol ) return 1;
1039   }
1040   return 0;
1041 }
1042
1043 static int idxCreateFromWhere(
1044   sqlite3expert *p,
1045   IdxScan *pScan,                 /* Create indexes for this scan */
1046   IdxConstraint *pTail            /* range/ORDER BY constraints for inclusion */
1047 ){
1048   IdxConstraint *p1 = 0;
1049   IdxConstraint *pCon;
1050   int rc;
1051
1052   /* Gather up all the == constraints. */
1053   for(pCon=pScan->pEq; pCon; pCon=pCon->pNext){
1054     if( !idxFindConstraint(p1, pCon) && !idxFindConstraint(pTail, pCon) ){
1055       pCon->pLink = p1;
1056       p1 = pCon;
1057     }
1058   }
1059
1060   /* Create an index using the == constraints collected above. And the
1061   ** range constraint/ORDER BY terms passed in by the caller, if any. */
1062   rc = idxCreateFromCons(p, pScan, p1, pTail);
1063
1064   /* If no range/ORDER BY passed by the caller, create a version of the
1065   ** index for each range constraint.  */
1066   if( pTail==0 ){
1067     for(pCon=pScan->pRange; rc==SQLITE_OK && pCon; pCon=pCon->pNext){
1068       assert( pCon->pLink==0 );
1069       if( !idxFindConstraint(p1, pCon) && !idxFindConstraint(pTail, pCon) ){
1070         rc = idxCreateFromCons(p, pScan, p1, pCon);
1071       }
1072     }
1073   }
1074
1075   return rc;
1076 }
1077
1078 /*
1079 ** Create candidate indexes in database [dbm] based on the data in
1080 ** linked-list pScan.
1081 */
1082 static int idxCreateCandidates(sqlite3expert *p){
1083   int rc = SQLITE_OK;
1084   IdxScan *pIter;
1085
1086   for(pIter=p->pScan; pIter && rc==SQLITE_OK; pIter=pIter->pNextScan){
1087     rc = idxCreateFromWhere(p, pIter, 0);
1088     if( rc==SQLITE_OK && pIter->pOrder ){
1089       rc = idxCreateFromWhere(p, pIter, pIter->pOrder);
1090     }
1091   }
1092
1093   return rc;
1094 }
1095
1096 /*
1097 ** Free all elements of the linked list starting at pConstraint.
1098 */
1099 static void idxConstraintFree(IdxConstraint *pConstraint){
1100   IdxConstraint *pNext;
1101   IdxConstraint *p;
1102
1103   for(p=pConstraint; p; p=pNext){
1104     pNext = p->pNext;
1105     sqlite3_free(p);
1106   }
1107 }
1108
1109 /*
1110 ** Free all elements of the linked list starting from pScan up until pLast
1111 ** (pLast is not freed).
1112 */
1113 static void idxScanFree(IdxScan *pScan, IdxScan *pLast){
1114   IdxScan *p;
1115   IdxScan *pNext;
1116   for(p=pScan; p!=pLast; p=pNext){
1117     pNext = p->pNextScan;
1118     idxConstraintFree(p->pOrder);
1119     idxConstraintFree(p->pEq);
1120     idxConstraintFree(p->pRange);
1121     sqlite3_free(p);
1122   }
1123 }
1124
1125 /*
1126 ** Free all elements of the linked list starting from pStatement up
1127 ** until pLast (pLast is not freed).
1128 */
1129 static void idxStatementFree(IdxStatement *pStatement, IdxStatement *pLast){
1130   IdxStatement *p;
1131   IdxStatement *pNext;
1132   for(p=pStatement; p!=pLast; p=pNext){
1133     pNext = p->pNext;
1134     sqlite3_free(p->zEQP);
1135     sqlite3_free(p->zIdx);
1136     sqlite3_free(p);
1137   }
1138 }
1139
1140 /*
1141 ** Free the linked list of IdxTable objects starting at pTab.
1142 */
1143 static void idxTableFree(IdxTable *pTab){
1144   IdxTable *pIter;
1145   IdxTable *pNext;
1146   for(pIter=pTab; pIter; pIter=pNext){
1147     pNext = pIter->pNext;
1148     sqlite3_free(pIter);
1149   }
1150 }
1151
1152 /*
1153 ** Free the linked list of IdxWrite objects starting at pTab.
1154 */
1155 static void idxWriteFree(IdxWrite *pTab){
1156   IdxWrite *pIter;
1157   IdxWrite *pNext;
1158   for(pIter=pTab; pIter; pIter=pNext){
1159     pNext = pIter->pNext;
1160     sqlite3_free(pIter);
1161   }
1162 }
1163
1164
1165
1166 /*
1167 ** This function is called after candidate indexes have been created. It
1168 ** runs all the queries to see which indexes they prefer, and populates
1169 ** IdxStatement.zIdx and IdxStatement.zEQP with the results.
1170 */
1171 int idxFindIndexes(
1172   sqlite3expert *p,
1173   char **pzErr                         /* OUT: Error message (sqlite3_malloc) */
1174 ){
1175   IdxStatement *pStmt;
1176   sqlite3 *dbm = p->dbm;
1177   int rc = SQLITE_OK;
1178
1179   IdxHash hIdx;
1180   idxHashInit(&hIdx);
1181
1182   for(pStmt=p->pStatement; rc==SQLITE_OK && pStmt; pStmt=pStmt->pNext){
1183     IdxHashEntry *pEntry;
1184     sqlite3_stmt *pExplain = 0;
1185     idxHashClear(&hIdx);
1186     rc = idxPrintfPrepareStmt(dbm, &pExplain, pzErr,
1187         "EXPLAIN QUERY PLAN %s", pStmt->zSql
1188     );
1189     while( rc==SQLITE_OK && sqlite3_step(pExplain)==SQLITE_ROW ){
1190       /* int iId = sqlite3_column_int(pExplain, 0); */
1191       /* int iParent = sqlite3_column_int(pExplain, 1); */
1192       /* int iNotUsed = sqlite3_column_int(pExplain, 2); */
1193       const char *zDetail = (const char*)sqlite3_column_text(pExplain, 3);
1194       int nDetail;
1195       int i;
1196
1197       if( !zDetail ) continue;
1198       nDetail = STRLEN(zDetail);
1199
1200       for(i=0; i<nDetail; i++){
1201         const char *zIdx = 0;
1202         if( i+13<nDetail && memcmp(&zDetail[i], " USING INDEX ", 13)==0 ){
1203           zIdx = &zDetail[i+13];
1204         }else if( i+22<nDetail
1205             && memcmp(&zDetail[i], " USING COVERING INDEX ", 22)==0
1206         ){
1207           zIdx = &zDetail[i+22];
1208         }
1209         if( zIdx ){
1210           const char *zSql;
1211           int nIdx = 0;
1212           while( zIdx[nIdx]!='\0' && (zIdx[nIdx]!=' ' || zIdx[nIdx+1]!='(') ){
1213             nIdx++;
1214           }
1215           zSql = idxHashSearch(&p->hIdx, zIdx, nIdx);
1216           if( zSql ){
1217             idxHashAdd(&rc, &hIdx, zSql, 0);
1218             if( rc ) goto find_indexes_out;
1219           }
1220           break;
1221         }
1222       }
1223
1224       if( zDetail[0]!='-' ){
1225         pStmt->zEQP = idxAppendText(&rc, pStmt->zEQP, "%s\n", zDetail);
1226       }
1227     }
1228
1229     for(pEntry=hIdx.pFirst; pEntry; pEntry=pEntry->pNext){
1230       pStmt->zIdx = idxAppendText(&rc, pStmt->zIdx, "%s;\n", pEntry->zKey);
1231     }
1232
1233     idxFinalize(&rc, pExplain);
1234   }
1235
1236  find_indexes_out:
1237   idxHashClear(&hIdx);
1238   return rc;
1239 }
1240
1241 static int idxAuthCallback(
1242   void *pCtx,
1243   int eOp,
1244   const char *z3,
1245   const char *z4,
1246   const char *zDb,
1247   const char *zTrigger
1248 ){
1249   int rc = SQLITE_OK;
1250   (void)z4;
1251   (void)zTrigger;
1252   if( eOp==SQLITE_INSERT || eOp==SQLITE_UPDATE || eOp==SQLITE_DELETE ){
1253     if( sqlite3_stricmp(zDb, "main")==0 ){
1254       sqlite3expert *p = (sqlite3expert*)pCtx;
1255       IdxTable *pTab;
1256       for(pTab=p->pTable; pTab; pTab=pTab->pNext){
1257         if( 0==sqlite3_stricmp(z3, pTab->zName) ) break;
1258       }
1259       if( pTab ){
1260         IdxWrite *pWrite;
1261         for(pWrite=p->pWrite; pWrite; pWrite=pWrite->pNext){
1262           if( pWrite->pTab==pTab && pWrite->eOp==eOp ) break;
1263         }
1264         if( pWrite==0 ){
1265           pWrite = idxMalloc(&rc, sizeof(IdxWrite));
1266           if( rc==SQLITE_OK ){
1267             pWrite->pTab = pTab;
1268             pWrite->eOp = eOp;
1269             pWrite->pNext = p->pWrite;
1270             p->pWrite = pWrite;
1271           }
1272         }
1273       }
1274     }
1275   }
1276   return rc;
1277 }
1278
1279 static int idxProcessOneTrigger(
1280   sqlite3expert *p,
1281   IdxWrite *pWrite,
1282   char **pzErr
1283 ){
1284   static const char *zInt = UNIQUE_TABLE_NAME;
1285   static const char *zDrop = "DROP TABLE " UNIQUE_TABLE_NAME;
1286   IdxTable *pTab = pWrite->pTab;
1287   const char *zTab = pTab->zName;
1288   const char *zSql =
1289     "SELECT 'CREATE TEMP' || substr(sql, 7) FROM sqlite_schema "
1290     "WHERE tbl_name = %Q AND type IN ('table', 'trigger') "
1291     "ORDER BY type;";
1292   sqlite3_stmt *pSelect = 0;
1293   int rc = SQLITE_OK;
1294   char *zWrite = 0;
1295
1296   /* Create the table and its triggers in the temp schema */
1297   rc = idxPrintfPrepareStmt(p->db, &pSelect, pzErr, zSql, zTab, zTab);
1298   while( rc==SQLITE_OK && SQLITE_ROW==sqlite3_step(pSelect) ){
1299     const char *zCreate = (const char*)sqlite3_column_text(pSelect, 0);
1300     rc = sqlite3_exec(p->dbv, zCreate, 0, 0, pzErr);
1301   }
1302   idxFinalize(&rc, pSelect);
1303
1304   /* Rename the table in the temp schema to zInt */
1305   if( rc==SQLITE_OK ){
1306     char *z = sqlite3_mprintf("ALTER TABLE temp.%Q RENAME TO %Q", zTab, zInt);
1307     if( z==0 ){
1308       rc = SQLITE_NOMEM;
1309     }else{
1310       rc = sqlite3_exec(p->dbv, z, 0, 0, pzErr);
1311       sqlite3_free(z);
1312     }
1313   }
1314
1315   switch( pWrite->eOp ){
1316     case SQLITE_INSERT: {
1317       int i;
1318       zWrite = idxAppendText(&rc, zWrite, "INSERT INTO %Q VALUES(", zInt);
1319       for(i=0; i<pTab->nCol; i++){
1320         zWrite = idxAppendText(&rc, zWrite, "%s?", i==0 ? "" : ", ");
1321       }
1322       zWrite = idxAppendText(&rc, zWrite, ")");
1323       break;
1324     }
1325     case SQLITE_UPDATE: {
1326       int i;
1327       zWrite = idxAppendText(&rc, zWrite, "UPDATE %Q SET ", zInt);
1328       for(i=0; i<pTab->nCol; i++){
1329         zWrite = idxAppendText(&rc, zWrite, "%s%Q=?", i==0 ? "" : ", ",
1330             pTab->aCol[i].zName
1331         );
1332       }
1333       break;
1334     }
1335     default: {
1336       assert( pWrite->eOp==SQLITE_DELETE );
1337       if( rc==SQLITE_OK ){
1338         zWrite = sqlite3_mprintf("DELETE FROM %Q", zInt);
1339         if( zWrite==0 ) rc = SQLITE_NOMEM;
1340       }
1341     }
1342   }
1343
1344   if( rc==SQLITE_OK ){
1345     sqlite3_stmt *pX = 0;
1346     rc = sqlite3_prepare_v2(p->dbv, zWrite, -1, &pX, 0);
1347     idxFinalize(&rc, pX);
1348     if( rc!=SQLITE_OK ){
1349       idxDatabaseError(p->dbv, pzErr);
1350     }
1351   }
1352   sqlite3_free(zWrite);
1353
1354   if( rc==SQLITE_OK ){
1355     rc = sqlite3_exec(p->dbv, zDrop, 0, 0, pzErr);
1356   }
1357
1358   return rc;
1359 }
1360
1361 static int idxProcessTriggers(sqlite3expert *p, char **pzErr){
1362   int rc = SQLITE_OK;
1363   IdxWrite *pEnd = 0;
1364   IdxWrite *pFirst = p->pWrite;
1365
1366   while( rc==SQLITE_OK && pFirst!=pEnd ){
1367     IdxWrite *pIter;
1368     for(pIter=pFirst; rc==SQLITE_OK && pIter!=pEnd; pIter=pIter->pNext){
1369       rc = idxProcessOneTrigger(p, pIter, pzErr);
1370     }
1371     pEnd = pFirst;
1372     pFirst = p->pWrite;
1373   }
1374
1375   return rc;
1376 }
1377
1378
1379 static int idxCreateVtabSchema(sqlite3expert *p, char **pzErrmsg){
1380   int rc = idxRegisterVtab(p);
1381   sqlite3_stmt *pSchema = 0;
1382
1383   /* For each table in the main db schema:
1384   **
1385   **   1) Add an entry to the p->pTable list, and
1386   **   2) Create the equivalent virtual table in dbv.
1387   */
1388   rc = idxPrepareStmt(p->db, &pSchema, pzErrmsg,
1389       "SELECT type, name, sql, 1 FROM sqlite_schema "
1390       "WHERE type IN ('table','view') AND name NOT LIKE 'sqlite_%%' "
1391       " UNION ALL "
1392       "SELECT type, name, sql, 2 FROM sqlite_schema "
1393       "WHERE type = 'trigger'"
1394       "  AND tbl_name IN(SELECT name FROM sqlite_schema WHERE type = 'view') "
1395       "ORDER BY 4, 1"
1396   );
1397   while( rc==SQLITE_OK && SQLITE_ROW==sqlite3_step(pSchema) ){
1398     const char *zType = (const char*)sqlite3_column_text(pSchema, 0);
1399     const char *zName = (const char*)sqlite3_column_text(pSchema, 1);
1400     const char *zSql = (const char*)sqlite3_column_text(pSchema, 2);
1401
1402     if( zType[0]=='v' || zType[1]=='r' ){
1403       rc = sqlite3_exec(p->dbv, zSql, 0, 0, pzErrmsg);
1404     }else{
1405       IdxTable *pTab;
1406       rc = idxGetTableInfo(p->db, zName, &pTab, pzErrmsg);
1407       if( rc==SQLITE_OK ){
1408         int i;
1409         char *zInner = 0;
1410         char *zOuter = 0;
1411         pTab->pNext = p->pTable;
1412         p->pTable = pTab;
1413
1414         /* The statement the vtab will pass to sqlite3_declare_vtab() */
1415         zInner = idxAppendText(&rc, 0, "CREATE TABLE x(");
1416         for(i=0; i<pTab->nCol; i++){
1417           zInner = idxAppendText(&rc, zInner, "%s%Q COLLATE %s",
1418               (i==0 ? "" : ", "), pTab->aCol[i].zName, pTab->aCol[i].zColl
1419           );
1420         }
1421         zInner = idxAppendText(&rc, zInner, ")");
1422
1423         /* The CVT statement to create the vtab */
1424         zOuter = idxAppendText(&rc, 0,
1425             "CREATE VIRTUAL TABLE %Q USING expert(%Q)", zName, zInner
1426         );
1427         if( rc==SQLITE_OK ){
1428           rc = sqlite3_exec(p->dbv, zOuter, 0, 0, pzErrmsg);
1429         }
1430         sqlite3_free(zInner);
1431         sqlite3_free(zOuter);
1432       }
1433     }
1434   }
1435   idxFinalize(&rc, pSchema);
1436   return rc;
1437 }
1438
1439 struct IdxSampleCtx {
1440   int iTarget;
1441   double target;                  /* Target nRet/nRow value */
1442   double nRow;                    /* Number of rows seen */
1443   double nRet;                    /* Number of rows returned */
1444 };
1445
1446 static void idxSampleFunc(
1447   sqlite3_context *pCtx,
1448   int argc,
1449   sqlite3_value **argv
1450 ){
1451   struct IdxSampleCtx *p = (struct IdxSampleCtx*)sqlite3_user_data(pCtx);
1452   int bRet;
1453
1454   (void)argv;
1455   assert( argc==0 );
1456   if( p->nRow==0.0 ){
1457     bRet = 1;
1458   }else{
1459     bRet = (p->nRet / p->nRow) <= p->target;
1460     if( bRet==0 ){
1461       unsigned short rnd;
1462       sqlite3_randomness(2, (void*)&rnd);
1463       bRet = ((int)rnd % 100) <= p->iTarget;
1464     }
1465   }
1466
1467   sqlite3_result_int(pCtx, bRet);
1468   p->nRow += 1.0;
1469   p->nRet += (double)bRet;
1470 }
1471
1472 struct IdxRemCtx {
1473   int nSlot;
1474   struct IdxRemSlot {
1475     int eType;                    /* SQLITE_NULL, INTEGER, REAL, TEXT, BLOB */
1476     i64 iVal;                     /* SQLITE_INTEGER value */
1477     double rVal;                  /* SQLITE_FLOAT value */
1478     int nByte;                    /* Bytes of space allocated at z */
1479     int n;                        /* Size of buffer z */
1480     char *z;                      /* SQLITE_TEXT/BLOB value */
1481   } aSlot[1];
1482 };
1483
1484 /*
1485 ** Implementation of scalar function rem().
1486 */
1487 static void idxRemFunc(
1488   sqlite3_context *pCtx,
1489   int argc,
1490   sqlite3_value **argv
1491 ){
1492   struct IdxRemCtx *p = (struct IdxRemCtx*)sqlite3_user_data(pCtx);
1493   struct IdxRemSlot *pSlot;
1494   int iSlot;
1495   assert( argc==2 );
1496
1497   iSlot = sqlite3_value_int(argv[0]);
1498   assert( iSlot<=p->nSlot );
1499   pSlot = &p->aSlot[iSlot];
1500
1501   switch( pSlot->eType ){
1502     case SQLITE_NULL:
1503       /* no-op */
1504       break;
1505
1506     case SQLITE_INTEGER:
1507       sqlite3_result_int64(pCtx, pSlot->iVal);
1508       break;
1509
1510     case SQLITE_FLOAT:
1511       sqlite3_result_double(pCtx, pSlot->rVal);
1512       break;
1513
1514     case SQLITE_BLOB:
1515       sqlite3_result_blob(pCtx, pSlot->z, pSlot->n, SQLITE_TRANSIENT);
1516       break;
1517
1518     case SQLITE_TEXT:
1519       sqlite3_result_text(pCtx, pSlot->z, pSlot->n, SQLITE_TRANSIENT);
1520       break;
1521   }
1522
1523   pSlot->eType = sqlite3_value_type(argv[1]);
1524   switch( pSlot->eType ){
1525     case SQLITE_NULL:
1526       /* no-op */
1527       break;
1528
1529     case SQLITE_INTEGER:
1530       pSlot->iVal = sqlite3_value_int64(argv[1]);
1531       break;
1532
1533     case SQLITE_FLOAT:
1534       pSlot->rVal = sqlite3_value_double(argv[1]);
1535       break;
1536
1537     case SQLITE_BLOB:
1538     case SQLITE_TEXT: {
1539       int nByte = sqlite3_value_bytes(argv[1]);
1540       if( nByte>pSlot->nByte ){
1541         char *zNew = (char*)sqlite3_realloc(pSlot->z, nByte*2);
1542         if( zNew==0 ){
1543           sqlite3_result_error_nomem(pCtx);
1544           return;
1545         }
1546         pSlot->nByte = nByte*2;
1547         pSlot->z = zNew;
1548       }
1549       pSlot->n = nByte;
1550       if( pSlot->eType==SQLITE_BLOB ){
1551         memcpy(pSlot->z, sqlite3_value_blob(argv[1]), nByte);
1552       }else{
1553         memcpy(pSlot->z, sqlite3_value_text(argv[1]), nByte);
1554       }
1555       break;
1556     }
1557   }
1558 }
1559
1560 static int idxLargestIndex(sqlite3 *db, int *pnMax, char **pzErr){
1561   int rc = SQLITE_OK;
1562   const char *zMax =
1563     "SELECT max(i.seqno) FROM "
1564     "  sqlite_schema AS s, "
1565     "  pragma_index_list(s.name) AS l, "
1566     "  pragma_index_info(l.name) AS i "
1567     "WHERE s.type = 'table'";
1568   sqlite3_stmt *pMax = 0;
1569
1570   *pnMax = 0;
1571   rc = idxPrepareStmt(db, &pMax, pzErr, zMax);
1572   if( rc==SQLITE_OK && SQLITE_ROW==sqlite3_step(pMax) ){
1573     *pnMax = sqlite3_column_int(pMax, 0) + 1;
1574   }
1575   idxFinalize(&rc, pMax);
1576
1577   return rc;
1578 }
1579
1580 static int idxPopulateOneStat1(
1581   sqlite3expert *p,
1582   sqlite3_stmt *pIndexXInfo,
1583   sqlite3_stmt *pWriteStat,
1584   const char *zTab,
1585   const char *zIdx,
1586   char **pzErr
1587 ){
1588   char *zCols = 0;
1589   char *zOrder = 0;
1590   char *zQuery = 0;
1591   int nCol = 0;
1592   int i;
1593   sqlite3_stmt *pQuery = 0;
1594   int *aStat = 0;
1595   int rc = SQLITE_OK;
1596
1597   assert( p->iSample>0 );
1598
1599   /* Formulate the query text */
1600   sqlite3_bind_text(pIndexXInfo, 1, zIdx, -1, SQLITE_STATIC);
1601   while( SQLITE_OK==rc && SQLITE_ROW==sqlite3_step(pIndexXInfo) ){
1602     const char *zComma = zCols==0 ? "" : ", ";
1603     const char *zName = (const char*)sqlite3_column_text(pIndexXInfo, 0);
1604     const char *zColl = (const char*)sqlite3_column_text(pIndexXInfo, 1);
1605     zCols = idxAppendText(&rc, zCols,
1606         "%sx.%Q IS rem(%d, x.%Q) COLLATE %s", zComma, zName, nCol, zName, zColl
1607     );
1608     zOrder = idxAppendText(&rc, zOrder, "%s%d", zComma, ++nCol);
1609   }
1610   sqlite3_reset(pIndexXInfo);
1611   if( rc==SQLITE_OK ){
1612     if( p->iSample==100 ){
1613       zQuery = sqlite3_mprintf(
1614           "SELECT %s FROM %Q x ORDER BY %s", zCols, zTab, zOrder
1615       );
1616     }else{
1617       zQuery = sqlite3_mprintf(
1618           "SELECT %s FROM temp."UNIQUE_TABLE_NAME" x ORDER BY %s", zCols, zOrder
1619       );
1620     }
1621   }
1622   sqlite3_free(zCols);
1623   sqlite3_free(zOrder);
1624
1625   /* Formulate the query text */
1626   if( rc==SQLITE_OK ){
1627     sqlite3 *dbrem = (p->iSample==100 ? p->db : p->dbv);
1628     rc = idxPrepareStmt(dbrem, &pQuery, pzErr, zQuery);
1629   }
1630   sqlite3_free(zQuery);
1631
1632   if( rc==SQLITE_OK ){
1633     aStat = (int*)idxMalloc(&rc, sizeof(int)*(nCol+1));
1634   }
1635   if( rc==SQLITE_OK && SQLITE_ROW==sqlite3_step(pQuery) ){
1636     IdxHashEntry *pEntry;
1637     char *zStat = 0;
1638     for(i=0; i<=nCol; i++) aStat[i] = 1;
1639     while( rc==SQLITE_OK && SQLITE_ROW==sqlite3_step(pQuery) ){
1640       aStat[0]++;
1641       for(i=0; i<nCol; i++){
1642         if( sqlite3_column_int(pQuery, i)==0 ) break;
1643       }
1644       for(/*no-op*/; i<nCol; i++){
1645         aStat[i+1]++;
1646       }
1647     }
1648
1649     if( rc==SQLITE_OK ){
1650       int s0 = aStat[0];
1651       zStat = sqlite3_mprintf("%d", s0);
1652       if( zStat==0 ) rc = SQLITE_NOMEM;
1653       for(i=1; rc==SQLITE_OK && i<=nCol; i++){
1654         zStat = idxAppendText(&rc, zStat, " %d", (s0+aStat[i]/2) / aStat[i]);
1655       }
1656     }
1657
1658     if( rc==SQLITE_OK ){
1659       sqlite3_bind_text(pWriteStat, 1, zTab, -1, SQLITE_STATIC);
1660       sqlite3_bind_text(pWriteStat, 2, zIdx, -1, SQLITE_STATIC);
1661       sqlite3_bind_text(pWriteStat, 3, zStat, -1, SQLITE_STATIC);
1662       sqlite3_step(pWriteStat);
1663       rc = sqlite3_reset(pWriteStat);
1664     }
1665
1666     pEntry = idxHashFind(&p->hIdx, zIdx, STRLEN(zIdx));
1667     if( pEntry ){
1668       assert( pEntry->zVal2==0 );
1669       pEntry->zVal2 = zStat;
1670     }else{
1671       sqlite3_free(zStat);
1672     }
1673   }
1674   sqlite3_free(aStat);
1675   idxFinalize(&rc, pQuery);
1676
1677   return rc;
1678 }
1679
1680 static int idxBuildSampleTable(sqlite3expert *p, const char *zTab){
1681   int rc;
1682   char *zSql;
1683
1684   rc = sqlite3_exec(p->dbv,"DROP TABLE IF EXISTS temp."UNIQUE_TABLE_NAME,0,0,0);
1685   if( rc!=SQLITE_OK ) return rc;
1686
1687   zSql = sqlite3_mprintf(
1688       "CREATE TABLE temp." UNIQUE_TABLE_NAME " AS SELECT * FROM %Q", zTab
1689   );
1690   if( zSql==0 ) return SQLITE_NOMEM;
1691   rc = sqlite3_exec(p->dbv, zSql, 0, 0, 0);
1692   sqlite3_free(zSql);
1693
1694   return rc;
1695 }
1696
1697 /*
1698 ** This function is called as part of sqlite3_expert_analyze(). Candidate
1699 ** indexes have already been created in database sqlite3expert.dbm, this
1700 ** function populates sqlite_stat1 table in the same database.
1701 **
1702 ** The stat1 data is generated by querying the
1703 */
1704 static int idxPopulateStat1(sqlite3expert *p, char **pzErr){
1705   int rc = SQLITE_OK;
1706   int nMax =0;
1707   struct IdxRemCtx *pCtx = 0;
1708   struct IdxSampleCtx samplectx;
1709   int i;
1710   i64 iPrev = -100000;
1711   sqlite3_stmt *pAllIndex = 0;
1712   sqlite3_stmt *pIndexXInfo = 0;
1713   sqlite3_stmt *pWrite = 0;
1714
1715   const char *zAllIndex =
1716     "SELECT s.rowid, s.name, l.name FROM "
1717     "  sqlite_schema AS s, "
1718     "  pragma_index_list(s.name) AS l "
1719     "WHERE s.type = 'table'";
1720   const char *zIndexXInfo =
1721     "SELECT name, coll FROM pragma_index_xinfo(?) WHERE key";
1722   const char *zWrite = "INSERT INTO sqlite_stat1 VALUES(?, ?, ?)";
1723
1724   /* If iSample==0, no sqlite_stat1 data is required. */
1725   if( p->iSample==0 ) return SQLITE_OK;
1726
1727   rc = idxLargestIndex(p->dbm, &nMax, pzErr);
1728   if( nMax<=0 || rc!=SQLITE_OK ) return rc;
1729
1730   rc = sqlite3_exec(p->dbm, "ANALYZE; PRAGMA writable_schema=1", 0, 0, 0);
1731
1732   if( rc==SQLITE_OK ){
1733     int nByte = sizeof(struct IdxRemCtx) + (sizeof(struct IdxRemSlot) * nMax);
1734     pCtx = (struct IdxRemCtx*)idxMalloc(&rc, nByte);
1735   }
1736
1737   if( rc==SQLITE_OK ){
1738     sqlite3 *dbrem = (p->iSample==100 ? p->db : p->dbv);
1739     rc = sqlite3_create_function(
1740         dbrem, "rem", 2, SQLITE_UTF8, (void*)pCtx, idxRemFunc, 0, 0
1741     );
1742   }
1743   if( rc==SQLITE_OK ){
1744     rc = sqlite3_create_function(
1745         p->db, "sample", 0, SQLITE_UTF8, (void*)&samplectx, idxSampleFunc, 0, 0
1746     );
1747   }
1748
1749   if( rc==SQLITE_OK ){
1750     pCtx->nSlot = nMax+1;
1751     rc = idxPrepareStmt(p->dbm, &pAllIndex, pzErr, zAllIndex);
1752   }
1753   if( rc==SQLITE_OK ){
1754     rc = idxPrepareStmt(p->dbm, &pIndexXInfo, pzErr, zIndexXInfo);
1755   }
1756   if( rc==SQLITE_OK ){
1757     rc = idxPrepareStmt(p->dbm, &pWrite, pzErr, zWrite);
1758   }
1759
1760   while( rc==SQLITE_OK && SQLITE_ROW==sqlite3_step(pAllIndex) ){
1761     i64 iRowid = sqlite3_column_int64(pAllIndex, 0);
1762     const char *zTab = (const char*)sqlite3_column_text(pAllIndex, 1);
1763     const char *zIdx = (const char*)sqlite3_column_text(pAllIndex, 2);
1764     if( p->iSample<100 && iPrev!=iRowid ){
1765       samplectx.target = (double)p->iSample / 100.0;
1766       samplectx.iTarget = p->iSample;
1767       samplectx.nRow = 0.0;
1768       samplectx.nRet = 0.0;
1769       rc = idxBuildSampleTable(p, zTab);
1770       if( rc!=SQLITE_OK ) break;
1771     }
1772     rc = idxPopulateOneStat1(p, pIndexXInfo, pWrite, zTab, zIdx, pzErr);
1773     iPrev = iRowid;
1774   }
1775   if( rc==SQLITE_OK && p->iSample<100 ){
1776     rc = sqlite3_exec(p->dbv,
1777         "DROP TABLE IF EXISTS temp." UNIQUE_TABLE_NAME, 0,0,0
1778     );
1779   }
1780
1781   idxFinalize(&rc, pAllIndex);
1782   idxFinalize(&rc, pIndexXInfo);
1783   idxFinalize(&rc, pWrite);
1784
1785   if( pCtx ){
1786     for(i=0; i<pCtx->nSlot; i++){
1787       sqlite3_free(pCtx->aSlot[i].z);
1788     }
1789     sqlite3_free(pCtx);
1790   }
1791
1792   if( rc==SQLITE_OK ){
1793     rc = sqlite3_exec(p->dbm, "ANALYZE sqlite_schema", 0, 0, 0);
1794   }
1795
1796   sqlite3_exec(p->db, "DROP TABLE IF EXISTS temp."UNIQUE_TABLE_NAME,0,0,0);
1797   return rc;
1798 }
1799
1800 /*
1801 ** Allocate a new sqlite3expert object.
1802 */
1803 sqlite3expert *sqlite3_expert_new(sqlite3 *db, char **pzErrmsg){
1804   int rc = SQLITE_OK;
1805   sqlite3expert *pNew;
1806
1807   pNew = (sqlite3expert*)idxMalloc(&rc, sizeof(sqlite3expert));
1808
1809   /* Open two in-memory databases to work with. The "vtab database" (dbv)
1810   ** will contain a virtual table corresponding to each real table in
1811   ** the user database schema, and a copy of each view. It is used to
1812   ** collect information regarding the WHERE, ORDER BY and other clauses
1813   ** of the user's query.
1814   */
1815   if( rc==SQLITE_OK ){
1816     pNew->db = db;
1817     pNew->iSample = 100;
1818     rc = sqlite3_open(":memory:", &pNew->dbv);
1819   }
1820   if( rc==SQLITE_OK ){
1821     rc = sqlite3_open(":memory:", &pNew->dbm);
1822     if( rc==SQLITE_OK ){
1823       sqlite3_db_config(pNew->dbm, SQLITE_DBCONFIG_TRIGGER_EQP, 1, (int*)0);
1824     }
1825   }
1826
1827
1828   /* Copy the entire schema of database [db] into [dbm]. */
1829   if( rc==SQLITE_OK ){
1830     sqlite3_stmt *pSql;
1831     rc = idxPrintfPrepareStmt(pNew->db, &pSql, pzErrmsg,
1832         "SELECT sql FROM sqlite_schema WHERE name NOT LIKE 'sqlite_%%'"
1833         " AND sql NOT LIKE 'CREATE VIRTUAL %%'"
1834     );
1835     while( rc==SQLITE_OK && SQLITE_ROW==sqlite3_step(pSql) ){
1836       const char *zSql = (const char*)sqlite3_column_text(pSql, 0);
1837       rc = sqlite3_exec(pNew->dbm, zSql, 0, 0, pzErrmsg);
1838     }
1839     idxFinalize(&rc, pSql);
1840   }
1841
1842   /* Create the vtab schema */
1843   if( rc==SQLITE_OK ){
1844     rc = idxCreateVtabSchema(pNew, pzErrmsg);
1845   }
1846
1847   /* Register the auth callback with dbv */
1848   if( rc==SQLITE_OK ){
1849     sqlite3_set_authorizer(pNew->dbv, idxAuthCallback, (void*)pNew);
1850   }
1851
1852   /* If an error has occurred, free the new object and reutrn NULL. Otherwise,
1853   ** return the new sqlite3expert handle.  */
1854   if( rc!=SQLITE_OK ){
1855     sqlite3_expert_destroy(pNew);
1856     pNew = 0;
1857   }
1858   return pNew;
1859 }
1860
1861 /*
1862 ** Configure an sqlite3expert object.
1863 */
1864 int sqlite3_expert_config(sqlite3expert *p, int op, ...){
1865   int rc = SQLITE_OK;
1866   va_list ap;
1867   va_start(ap, op);
1868   switch( op ){
1869     case EXPERT_CONFIG_SAMPLE: {
1870       int iVal = va_arg(ap, int);
1871       if( iVal<0 ) iVal = 0;
1872       if( iVal>100 ) iVal = 100;
1873       p->iSample = iVal;
1874       break;
1875     }
1876     default:
1877       rc = SQLITE_NOTFOUND;
1878       break;
1879   }
1880
1881   va_end(ap);
1882   return rc;
1883 }
1884
1885 /*
1886 ** Add an SQL statement to the analysis.
1887 */
1888 int sqlite3_expert_sql(
1889   sqlite3expert *p,               /* From sqlite3_expert_new() */
1890   const char *zSql,               /* SQL statement to add */
1891   char **pzErr                    /* OUT: Error message (if any) */
1892 ){
1893   IdxScan *pScanOrig = p->pScan;
1894   IdxStatement *pStmtOrig = p->pStatement;
1895   int rc = SQLITE_OK;
1896   const char *zStmt = zSql;
1897
1898   if( p->bRun ) return SQLITE_MISUSE;
1899
1900   while( rc==SQLITE_OK && zStmt && zStmt[0] ){
1901     sqlite3_stmt *pStmt = 0;
1902     rc = sqlite3_prepare_v2(p->dbv, zStmt, -1, &pStmt, &zStmt);
1903     if( rc==SQLITE_OK ){
1904       if( pStmt ){
1905         IdxStatement *pNew;
1906         const char *z = sqlite3_sql(pStmt);
1907         int n = STRLEN(z);
1908         pNew = (IdxStatement*)idxMalloc(&rc, sizeof(IdxStatement) + n+1);
1909         if( rc==SQLITE_OK ){
1910           pNew->zSql = (char*)&pNew[1];
1911           memcpy(pNew->zSql, z, n+1);
1912           pNew->pNext = p->pStatement;
1913           if( p->pStatement ) pNew->iId = p->pStatement->iId+1;
1914           p->pStatement = pNew;
1915         }
1916         sqlite3_finalize(pStmt);
1917       }
1918     }else{
1919       idxDatabaseError(p->dbv, pzErr);
1920     }
1921   }
1922
1923   if( rc!=SQLITE_OK ){
1924     idxScanFree(p->pScan, pScanOrig);
1925     idxStatementFree(p->pStatement, pStmtOrig);
1926     p->pScan = pScanOrig;
1927     p->pStatement = pStmtOrig;
1928   }
1929
1930   return rc;
1931 }
1932
1933 int sqlite3_expert_analyze(sqlite3expert *p, char **pzErr){
1934   int rc;
1935   IdxHashEntry *pEntry;
1936
1937   /* Do trigger processing to collect any extra IdxScan structures */
1938   rc = idxProcessTriggers(p, pzErr);
1939
1940   /* Create candidate indexes within the in-memory database file */
1941   if( rc==SQLITE_OK ){
1942     rc = idxCreateCandidates(p);
1943   }else if ( rc==SQLITE_BUSY_TIMEOUT ){
1944     if( pzErr )
1945       *pzErr = sqlite3_mprintf("Cannot find a unique index name to propose.");
1946     return rc;
1947   }
1948
1949   /* Generate the stat1 data */
1950   if( rc==SQLITE_OK ){
1951     rc = idxPopulateStat1(p, pzErr);
1952   }
1953
1954   /* Formulate the EXPERT_REPORT_CANDIDATES text */
1955   for(pEntry=p->hIdx.pFirst; pEntry; pEntry=pEntry->pNext){
1956     p->zCandidates = idxAppendText(&rc, p->zCandidates,
1957         "%s;%s%s\n", pEntry->zVal,
1958         pEntry->zVal2 ? " -- stat1: " : "", pEntry->zVal2
1959     );
1960   }
1961
1962   /* Figure out which of the candidate indexes are preferred by the query
1963   ** planner and report the results to the user.  */
1964   if( rc==SQLITE_OK ){
1965     rc = idxFindIndexes(p, pzErr);
1966   }
1967
1968   if( rc==SQLITE_OK ){
1969     p->bRun = 1;
1970   }
1971   return rc;
1972 }
1973
1974 /*
1975 ** Return the total number of statements that have been added to this
1976 ** sqlite3expert using sqlite3_expert_sql().
1977 */
1978 int sqlite3_expert_count(sqlite3expert *p){
1979   int nRet = 0;
1980   if( p->pStatement ) nRet = p->pStatement->iId+1;
1981   return nRet;
1982 }
1983
1984 /*
1985 ** Return a component of the report.
1986 */
1987 const char *sqlite3_expert_report(sqlite3expert *p, int iStmt, int eReport){
1988   const char *zRet = 0;
1989   IdxStatement *pStmt;
1990
1991   if( p->bRun==0 ) return 0;
1992   for(pStmt=p->pStatement; pStmt && pStmt->iId!=iStmt; pStmt=pStmt->pNext);
1993   switch( eReport ){
1994     case EXPERT_REPORT_SQL:
1995       if( pStmt ) zRet = pStmt->zSql;
1996       break;
1997     case EXPERT_REPORT_INDEXES:
1998       if( pStmt ) zRet = pStmt->zIdx;
1999       break;
2000     case EXPERT_REPORT_PLAN:
2001       if( pStmt ) zRet = pStmt->zEQP;
2002       break;
2003     case EXPERT_REPORT_CANDIDATES:
2004       zRet = p->zCandidates;
2005       break;
2006   }
2007   return zRet;
2008 }
2009
2010 /*
2011 ** Free an sqlite3expert object.
2012 */
2013 void sqlite3_expert_destroy(sqlite3expert *p){
2014   if( p ){
2015     sqlite3_close(p->dbm);
2016     sqlite3_close(p->dbv);
2017     idxScanFree(p->pScan, 0);
2018     idxStatementFree(p->pStatement, 0);
2019     idxTableFree(p->pTable);
2020     idxWriteFree(p->pWrite);
2021     idxHashClear(&p->hIdx);
2022     sqlite3_free(p->zCandidates);
2023     sqlite3_free(p);
2024   }
2025 }
2026
2027 #endif /* ifndef SQLITE_OMIT_VIRTUALTABLE */