## SQLite Expert Extension

This folder contains code for a simple system to propose useful indexes
given a database and a set of SQL queries. It works as follows:

  1. The user database schema is copied to a temporary database.

  1. All SQL queries are prepared against the temporary database. The
     **sqlite3\_whereinfo\_hook()** API is used to record information regarding
     the WHERE and ORDER BY clauses attached to each query.

  1. The information gathered in step 2 is used to create (possibly a large
     number of) candidate indexes.

  1. The SQL queries are prepared a second time. If the planner uses any
     of the indexes created in step 3, they are recommended to the user.

No ANALYZE data is available to the planner in step 4 above. This can lead to sub-optimal results.

This extension requires that SQLite be built with the 
SQLITE\_ENABLE\_WHEREINFO\_HOOK pre-processor symbol defined.

# C API

The SQLite expert C API is defined in sqlite3expert.h. Most uses will proceed
as follows:

  1. An sqlite3expert object is created by calling **sqlite3\_expert\_new()**.
     A database handle opened by the user is passed as an argument.

  1. The sqlite3expert object is configured with one or more SQL statements
     by making one or more calls to **sqlite3\_expert\_sql()**. Each call may
     specify a single SQL statement, or multiple statements separated by
     semi-colons.

  1. **sqlite3\_expert\_analyze()** is called to run the analysis.

  1. One or more calls are made to **sqlite3\_expert\_report()** to extract
     components of the results of the analysis.

  1. **sqlite3\_expert\_destroy()** is called to free all resources.

Refer to comments in sqlite3expert.h for further details.

# sqlite3_expert application

The file "expert.c" contains the code for a command line application that
uses the API described above. It can be compiled with (for example):

<pre>
  gcc -O2 -DSQLITE_ENABLE_WHEREINFO_HOOK sqlite3.c expert.c sqlite3expert.c -o sqlite3_expert
</pre>

Assuming the database is "test.db", it can then be run to analyze a single query:

<pre>
  ./sqlite3_expert -sql &lt;sql-query&gt; test.db
</pre>

Or an entire text file worth of queries with:

<pre>
  ./sqlite3_expert -file &lt;text-file&gt; test.db
</pre>

# the ".recommend" command.
#
#

# Test plan:
#
#

set testdir [file dirname $argv0]

source $testdir/tester.tcl
set testprefix expert1

if {$tcl_platform(platform)=="windows"} {
  set CMD "sqlite3_expert.exe"
} else {
  set CMD ".././sqlite3_expert"

# the ".recommend" command.
#
#

# Test plan:
#
#
if {![info exists testdir]} {
  set testdir [file join [file dirname [info script]] .. .. test]
}
source $testdir/tester.tcl
set testprefix expert1

if {$tcl_platform(platform)=="windows"} {
  set CMD "sqlite3_expert.exe"
} else {
  set CMD ".././sqlite3_expert"

/*
** 2016 February 10
**
** The author disclaims copyright to this source code.  In place of
** a legal notice, here is a blessing:
**
**    May you do good and not evil.
**    May you find forgiveness for yourself and forgive others.
**    May you share freely, never taking more than you give.
................................................................................
#include <assert.h>
#include <string.h>
#include <stdio.h>

typedef sqlite3_int64 i64;
typedef sqlite3_uint64 u64;


typedef struct IdxConstraint IdxConstraint;
typedef struct IdxScan IdxScan;
typedef struct IdxStatement IdxStatement;
typedef struct IdxWhere IdxWhere;

typedef struct IdxColumn IdxColumn;
typedef struct IdxTable IdxTable;

/*
** A single constraint. Equivalent to either "col = ?" or "col < ?".

**
** pLink:
**   Used to temporarily link IdxConstraint objects into lists while
**   creating candidate indexes.
*/
struct IdxConstraint {
  char *zColl;                    /* Collation sequence */
................................................................................
  i64 depmask;                    /* Dependency mask */
  int bFlag;                      /* Used by idxFindCompatible() */
  int bDesc;                      /* True if ORDER BY <expr> DESC */
  IdxConstraint *pNext;           /* Next constraint in pEq or pRange list */
  IdxConstraint *pLink;           /* See above */
};

/*
** A WHERE clause. Made up of IdxConstraint objects. Example WHERE clause:
**
**   a=? AND b=? AND c=? AND d=? AND e>? AND f<?
**
** The above is decomposed into 6 AND connected clauses. The first four are
** added to the IdxWhere.pEq linked list, the following two into 
** IdxWhere.pRange.
**
** IdxWhere.pEq and IdxWhere.pRange are simple linked lists of IdxConstraint
** objects linked by the IdxConstraint.pNext field.
*/
struct IdxWhere {
  IdxConstraint *pEq;             /* List of == constraints */
  IdxConstraint *pRange;          /* List of < constraints */
};

/*
** A single scan of a single table.
*/
struct IdxScan {
  IdxTable *pTable;               /* Table-info */
  char *zTable;                   /* Name of table to scan */
  int iDb;                        /* Database containing table zTable */
  i64 covering;                   /* Mask of columns required for cov. index */
  IdxConstraint *pOrder;          /* ORDER BY columns */
  IdxWhere where;                 /* WHERE Constraints */

  IdxScan *pNextScan;             /* Next IdxScan object for same query */
};

/*
** Data regarding a database table. Extracted from "PRAGMA table_info"

*/
struct IdxColumn {
  char *zName;
  char *zColl;
  int iPk;
};
struct IdxTable {
  int nCol;
  IdxColumn *aCol;
};





struct IdxStatement {
  int iId;                        /* Statement number */
  char *zSql;                     /* SQL statement */
  char *zIdx;                     /* Indexes */
  char *zEQP;                     /* Plan */
  IdxStatement *pNext;
};











#define IDX_HASH_SIZE 1023
typedef struct IdxHashEntry IdxHashEntry;
typedef struct IdxHash IdxHash;
struct IdxHashEntry {
  char *zKey;                     /* nul-terminated key */
  char *zVal;                     /* nul-terminated value string */
  IdxHashEntry *pHashNext;        /* Next entry in same hash bucket */
................................................................................
  IdxHashEntry *pNext;            /* Next entry in hash */
};
struct IdxHash {
  IdxHashEntry *pFirst;
  IdxHashEntry *aHash[IDX_HASH_SIZE];
};




















/*
** sqlite3expert object.
*/
struct sqlite3expert {
  sqlite3 *db;                    /* Users database */
  sqlite3 *dbm;                   /* In-memory db for this analysis */

  int bRun;                       /* True once analysis has run */
  char **pzErrmsg;

  IdxScan *pScan;                 /* List of scan objects */
  IdxStatement *pStatement;       /* List of IdxStatement objects */
  int rc;                         /* Error code from whereinfo hook */

  IdxHash hIdx;                   /* Hash containing all candidate indexes */
};


/*
** Allocate and return nByte bytes of zeroed memory using sqlite3_malloc(). 
** If the allocation fails, set *pRc to SQLITE_NOMEM and return NULL.
................................................................................
    memset(pRet, 0, nByte);
  }else{
    *pRc = SQLITE_NOMEM;
  }
  return pRet;
}

/*************************************************************************
** Start of hash table implementations.
*/
typedef struct IdxHash64Entry IdxHash64Entry;
typedef struct IdxHash64 IdxHash64;
struct IdxHash64Entry {
  u64 iVal;
  IdxHash64Entry *pNext;          /* Next entry in hash table */
  IdxHash64Entry *pHashNext;      /* Next entry in same hash bucket */
};
struct IdxHash64 {
  IdxHash64Entry *pFirst;         /* Most recently added entry in hash table */
  IdxHash64Entry *aHash[IDX_HASH_SIZE];
};

static void idxHash64Init(IdxHash64 *pHash){
  memset(pHash, 0, sizeof(IdxHash64));
}




static void idxHash64Clear(IdxHash64 *pHash){
  IdxHash64Entry *pEntry;
  IdxHash64Entry *pNext;
  for(pEntry=pHash->pFirst; pEntry; pEntry=pNext){
    pNext = pEntry->pNext;
    sqlite3_free(pEntry);
  }
  memset(pHash, 0, sizeof(IdxHash64));
}





static void idxHash64Add(int *pRc, IdxHash64 *pHash, u64 iVal){
  int iHash = (int)((iVal*7) % IDX_HASH_SIZE);
  IdxHash64Entry *pEntry;
  assert( iHash>=0 );

  for(pEntry=pHash->aHash[iHash]; pEntry; pEntry=pEntry->pHashNext){
    if( pEntry->iVal==iVal ) return;
................................................................................
    pEntry->pHashNext = pHash->aHash[iHash];
    pHash->aHash[iHash] = pEntry;
    pEntry->pNext = pHash->pFirst;
    pHash->pFirst = pEntry;
  }
}




static void idxHashInit(IdxHash *pHash){
  memset(pHash, 0, sizeof(IdxHash));
}




static void idxHashClear(IdxHash *pHash){
  int i;
  for(i=0; i<IDX_HASH_SIZE; i++){
    IdxHashEntry *pEntry;
    IdxHashEntry *pNext;
    for(pEntry=pHash->aHash[i]; pEntry; pEntry=pNext){
      pNext = pEntry->pHashNext;
      sqlite3_free(pEntry);
    }
  }
  memset(pHash, 0, sizeof(IdxHash));
}





static int idxHashString(const char *z, int n){
  unsigned int ret = 0;
  int i;
  for(i=0; i<n; i++){
    ret += (ret<<3) + (unsigned char)(z[i]);
  }
  return (int)(ret % IDX_HASH_SIZE);
}






static int idxHashAdd(
  int *pRc, 
  IdxHash *pHash, 
  const char *zKey,
  const char *zVal
){
  int nKey = strlen(zKey);
................................................................................

    pEntry->pNext = pHash->pFirst;
    pHash->pFirst = pEntry;
  }
  return 0;
}







static const char *idxHashSearch(IdxHash *pHash, const char *zKey, int nKey){
  int iHash;
  IdxHashEntry *pEntry;
  if( nKey<0 ) nKey = strlen(zKey);
  iHash = idxHashString(zKey, nKey);
  assert( iHash>=0 );
  for(pEntry=pHash->aHash[iHash]; pEntry; pEntry=pEntry->pHashNext){
................................................................................
    if( strlen(pEntry->zKey)==nKey && 0==memcmp(pEntry->zKey, zKey, nKey) ){
      return pEntry->zVal;
    }
  }
  return 0;
}

/*
** End of hash table implementations.
**************************************************************************/

/*
** Allocate and return a new IdxConstraint object. Set the IdxConstraint.zColl
** variable to point to a copy of nul-terminated string zColl.
*/
static IdxConstraint *idxNewConstraint(int *pRc, const char *zColl){
  IdxConstraint *pNew;
  int nColl = strlen(zColl);
................................................................................
      case SQLITE_WHEREINFO_RANGE: {
        IdxConstraint *pNew = idxNewConstraint(&p->rc, zVal);
        if( pNew==0 ) return;
        pNew->iCol = iVal;
        pNew->depmask = mask;

        if( eOp==SQLITE_WHEREINFO_RANGE ){
          pNew->pNext = p->pScan->where.pRange;
          p->pScan->where.pRange = pNew;
        }else{
          pNew->pNext = p->pScan->where.pEq;
          p->pScan->where.pEq = pNew;
        }
        break;
      }
    }
  }
}

................................................................................
static void idxDatabaseError(
  sqlite3 *db,                    /* Database handle */
  char **pzErrmsg                 /* Write error here */
){
  *pzErrmsg = sqlite3_mprintf("%s", sqlite3_errmsg(db));
}




static int idxPrepareStmt(
  sqlite3 *db,                    /* Database handle to compile against */
  sqlite3_stmt **ppStmt,          /* OUT: Compiled SQL statement */
  char **pzErrmsg,                /* OUT: sqlite3_malloc()ed error message */
  const char *zSql                /* SQL statement to compile */
){
  int rc = sqlite3_prepare_v2(db, zSql, -1, ppStmt, 0);
................................................................................
  if( rc!=SQLITE_OK ){
    *ppStmt = 0;
    idxDatabaseError(db, pzErrmsg);
  }
  return rc;
}




static int idxPrintfPrepareStmt(
  sqlite3 *db,                    /* Database handle to compile against */
  sqlite3_stmt **ppStmt,          /* OUT: Compiled SQL statement */
  char **pzErrmsg,                /* OUT: sqlite3_malloc()ed error message */
  const char *zFmt,               /* printf() format of SQL statement */
  ...                             /* Trailing printf() arguments */
){
................................................................................
    rc = idxPrepareStmt(db, ppStmt, pzErrmsg, zSql);
    sqlite3_free(zSql);
  }
  va_end(ap);
  return rc;
}






static void idxFinalize(int *pRc, sqlite3_stmt *pStmt){
  int rc = sqlite3_finalize(pStmt);
  if( *pRc==SQLITE_OK ) *pRc = rc;
}











static int idxGetTableInfo(
  sqlite3 *db,
  IdxScan *pScan,



  char **pzErrmsg
){
  const char *zTbl = pScan->zTable;
  sqlite3_stmt *p1 = 0;
  int nCol = 0;
  int nByte = sizeof(IdxTable);
  IdxTable *pNew = 0;
  int rc, rc2;
  char *pCsr;

  rc = idxPrintfPrepareStmt(db, &p1, pzErrmsg, "PRAGMA table_info=%Q", zTbl);
  while( rc==SQLITE_OK && SQLITE_ROW==sqlite3_step(p1) ){
    const char *zCol = (const char*)sqlite3_column_text(p1, 1);
    nByte += 1 + strlen(zCol);
    rc = sqlite3_table_column_metadata(
        db, "main", zTbl, zCol, 0, &zCol, 0, 0, 0
    );
    nByte += 1 + strlen(zCol);
    nCol++;
  }
  rc2 = sqlite3_reset(p1);
  if( rc==SQLITE_OK ) rc = rc2;

................................................................................
    int nCopy = strlen(zCol) + 1;
    pNew->aCol[nCol].zName = pCsr;
    pNew->aCol[nCol].iPk = sqlite3_column_int(p1, 5);
    memcpy(pCsr, zCol, nCopy);
    pCsr += nCopy;

    rc = sqlite3_table_column_metadata(
        db, "main", zTbl, zCol, 0, &zCol, 0, 0, 0
    );
    if( rc==SQLITE_OK ){
      nCopy = strlen(zCol) + 1;
      pNew->aCol[nCol].zColl = pCsr;
      memcpy(pCsr, zCol, nCopy);
      pCsr += nCopy;
    }

    nCol++;
  }
  idxFinalize(&rc, p1);

  if( rc==SQLITE_OK ){
    pScan->pTable = pNew;
  }else{
    sqlite3_free(pNew);

  }


  return rc;
}

/*
** This function is a no-op if *pRc is set to anything other than 
** SQLITE_OK when it is called.
**
................................................................................
    sqlite3_free(zAppend);
    sqlite3_free(zIn);
  }
  va_end(ap);
  return zRet;
}





static int idxIdentifierRequiresQuotes(const char *zId){
  int i;
  for(i=0; zId[i]; i++){
    if( !(zId[i]=='_')
     && !(zId[i]>='0' && zId[i]<='9')
     && !(zId[i]>='a' && zId[i]<='z')
     && !(zId[i]>='A' && zId[i]<='Z')
................................................................................
    ){
      return 1;
    }
  }
  return 0;
}





static char *idxAppendColDefn(
  int *pRc, 
  char *zIn, 


  IdxTable *pTab, 
  IdxConstraint *pCons
){
  char *zRet = zIn;
  IdxColumn *p = &pTab->aCol[pCons->iCol];
  if( zRet ) zRet = idxAppendText(pRc, zRet, ", ");

  if( idxIdentifierRequiresQuotes(p->zName) ){
................................................................................

  *pRc = rc;
  return 0;
}

static int idxCreateFromCons(
  sqlite3expert *p,

  IdxScan *pScan,
  IdxConstraint *pEq, 
  IdxConstraint *pTail
){
  sqlite3 *dbm = p->dbm;
  int rc = SQLITE_OK;
  if( (pEq || pTail) && 0==idxFindCompatible(&rc, dbm, pScan, pEq, pTail) ){
    IdxTable *pTab = pScan->pTable;
    char *zCols = 0;
    char *zIdx = 0;
    IdxConstraint *pCons;
    int h = 0;
    const char *zFmt;

    for(pCons=pEq; pCons; pCons=pCons->pLink){
................................................................................
    if( p->iCol==pCmp->iCol ) return 1;
  }
  return 0;
}

static int idxCreateFromWhere(
  sqlite3expert *p, 

  i64 mask,                       /* Consider only these constraints */
  IdxScan *pScan,                 /* Create indexes for this scan */
  IdxWhere *pWhere,               /* Read constraints from here */
  IdxConstraint *pEq,             /* == constraints for inclusion */
  IdxConstraint *pTail            /* range/ORDER BY constraints for inclusion */
){
  IdxConstraint *p1 = pEq;
  IdxConstraint *pCon;
  int rc;

  /* Gather up all the == constraints that match the mask. */
  for(pCon=pWhere->pEq; pCon; pCon=pCon->pNext){
    if( (mask & pCon->depmask)==pCon->depmask 
     && idxFindConstraint(p1, pCon)==0
     && idxFindConstraint(pTail, pCon)==0
    ){
      pCon->pLink = p1;
      p1 = pCon;
    }
  }

  /* Create an index using the == constraints collected above. And the
  ** range constraint/ORDER BY terms passed in by the caller, if any. */
  rc = idxCreateFromCons(p, pScan, p1, pTail);

  /* If no range/ORDER BY passed by the caller, create a version of the
  ** index for each range constraint that matches the mask. */
  if( pTail==0 ){
    for(pCon=pWhere->pRange; rc==SQLITE_OK && pCon; pCon=pCon->pNext){
      assert( pCon->pLink==0 );
      if( (mask & pCon->depmask)==pCon->depmask
        && idxFindConstraint(pEq, pCon)==0
        && idxFindConstraint(pTail, pCon)==0
      ){
        rc = idxCreateFromCons(p, pScan, p1, pCon);
      }
    }
  }

  return rc;
}

................................................................................
  int rc = SQLITE_OK;
  IdxScan *pIter;
  IdxHash64 hMask;
  idxHash64Init(&hMask);

  for(pIter=p->pScan; pIter && rc==SQLITE_OK; pIter=pIter->pNextScan){
    IdxHash64Entry *pEntry;
    IdxWhere *pWhere = &pIter->where;
    IdxConstraint *pCons;




    idxHash64Add(&rc, &hMask, 0);
    for(pCons=pIter->where.pEq; pCons; pCons=pCons->pNext){
      for(pEntry=hMask.pFirst; pEntry; pEntry=pEntry->pNext){
        idxHash64Add(&rc, &hMask, pEntry->iVal | (u64)pCons->depmask);
      }
    }

    for(pEntry=hMask.pFirst; pEntry; pEntry=pEntry->pNext){
      i64 mask = (i64)pEntry->iVal;
      rc = idxCreateFromWhere(p, mask, pIter, pWhere, 0, 0);
      if( rc==SQLITE_OK && pIter->pOrder ){
        rc = idxCreateFromWhere(p, mask, pIter, pWhere, 0, pIter->pOrder);
      }
    }


    idxHash64Clear(&hMask);
  }

  return rc;
}




static void idxConstraintFree(IdxConstraint *pConstraint){
  IdxConstraint *pNext;
  IdxConstraint *p;

  for(p=pConstraint; p; p=pNext){
    pNext = p->pNext;
    sqlite3_free(p);
................................................................................
*/
static void idxScanFree(IdxScan *pScan, IdxScan *pLast){
  IdxScan *p;
  IdxScan *pNext;
  for(p=pScan; p!=pLast; p=pNext){
    pNext = p->pNextScan;
    idxConstraintFree(p->pOrder);
    idxConstraintFree(p->where.pEq);
    idxConstraintFree(p->where.pRange);
    sqlite3_free(p->pTable);
    sqlite3_free(p);
  }
}

/*
** Free all elements of the linked list starting from pStatement up 
** until pLast (pLast is not freed).
................................................................................
    sqlite3_free(p->zEQP);
    sqlite3_free(p->zIdx);
    sqlite3_free(p);
  }
}







int idxFindIndexes(
  sqlite3expert *p,
  char **pzErr                         /* OUT: Error message (sqlite3_malloc) */
){
  IdxStatement *pStmt;
  sqlite3 *dbm = p->dbm;
  int rc = SQLITE_OK;
................................................................................
    p->pStatement = pStmtOrig;
  }

  return rc;
}

int sqlite3_expert_analyze(sqlite3expert *p, char **pzErr){
  int rc = SQLITE_OK;
  IdxScan *pIter;

  /* Load IdxTable objects */
  for(pIter=p->pScan; pIter && rc==SQLITE_OK; pIter=pIter->pNextScan){
    rc = idxGetTableInfo(p->dbm, pIter, pzErr);
  }

  /* Create candidate indexes within the in-memory database file */
  if( rc==SQLITE_OK ){
    rc = idxCreateCandidates(p, pzErr);
  }

  /* Figure out which of the candidate indexes are preferred by the query
  ** planner and report the results to the user.  */
  if( rc==SQLITE_OK ){
    rc = idxFindIndexes(p, pzErr);
  }

/*
** 2017 April 09
**
** The author disclaims copyright to this source code.  In place of
** a legal notice, here is a blessing:
**
**    May you do good and not evil.
**    May you find forgiveness for yourself and forgive others.
**    May you share freely, never taking more than you give.
................................................................................
#include <assert.h>
#include <string.h>
#include <stdio.h>

typedef sqlite3_int64 i64;
typedef sqlite3_uint64 u64;

typedef struct IdxColumn IdxColumn;
typedef struct IdxConstraint IdxConstraint;
typedef struct IdxScan IdxScan;
typedef struct IdxStatement IdxStatement;



typedef struct IdxTable IdxTable;

/*
** A single constraint. Equivalent to either "col = ?" or "col < ?" (or
** any other type of single-ended range constraint on a column).
**
** pLink:
**   Used to temporarily link IdxConstraint objects into lists while
**   creating candidate indexes.
*/
struct IdxConstraint {
  char *zColl;                    /* Collation sequence */
................................................................................
  i64 depmask;                    /* Dependency mask */
  int bFlag;                      /* Used by idxFindCompatible() */
  int bDesc;                      /* True if ORDER BY <expr> DESC */
  IdxConstraint *pNext;           /* Next constraint in pEq or pRange list */
  IdxConstraint *pLink;           /* See above */
};


















/*
** A single scan of a single table.
*/
struct IdxScan {

  char *zTable;                   /* Name of table to scan */
  int iDb;                        /* Database containing table zTable */
  i64 covering;                   /* Mask of columns required for cov. index */
  IdxConstraint *pOrder;          /* ORDER BY columns */
  IdxConstraint *pEq;             /* List of == constraints */
  IdxConstraint *pRange;          /* List of < constraints */
  IdxScan *pNextScan;             /* Next IdxScan object for same analysis */
};

/*
** Information regarding a single database table. Extracted from 
** "PRAGMA table_info" by function idxGetTableInfo().
*/
struct IdxColumn {
  char *zName;
  char *zColl;
  int iPk;
};
struct IdxTable {
  int nCol;
  IdxColumn *aCol;
};

/*
** Each statement being analyzed is represented by an instance of this
** structure.
*/
struct IdxStatement {
  int iId;                        /* Statement number */
  char *zSql;                     /* SQL statement */
  char *zIdx;                     /* Indexes */
  char *zEQP;                     /* Plan */
  IdxStatement *pNext;
};


/*
** A hash table for storing strings. With space for a payload string
** with each entry. Methods are:
**
**   idxHashInit()
**   idxHashClear()
**   idxHashAdd()
**   idxHashSearch()
*/
#define IDX_HASH_SIZE 1023
typedef struct IdxHashEntry IdxHashEntry;
typedef struct IdxHash IdxHash;
struct IdxHashEntry {
  char *zKey;                     /* nul-terminated key */
  char *zVal;                     /* nul-terminated value string */
  IdxHashEntry *pHashNext;        /* Next entry in same hash bucket */
................................................................................
  IdxHashEntry *pNext;            /* Next entry in hash */
};
struct IdxHash {
  IdxHashEntry *pFirst;
  IdxHashEntry *aHash[IDX_HASH_SIZE];
};

/*
** A hash table for storing a set of 64-bit values. Methods are:
**
**   idxHash64Init()
**   idxHash64Clear()
**   idxHash64Add()
*/
typedef struct IdxHash64Entry IdxHash64Entry;
typedef struct IdxHash64 IdxHash64;
struct IdxHash64Entry {
  u64 iVal;
  IdxHash64Entry *pNext;          /* Next entry in hash table */
  IdxHash64Entry *pHashNext;      /* Next entry in same hash bucket */
};
struct IdxHash64 {
  IdxHash64Entry *pFirst;         /* Most recently added entry in hash table */
  IdxHash64Entry *aHash[IDX_HASH_SIZE];
};

/*
** sqlite3expert object.
*/
struct sqlite3expert {
  sqlite3 *db;                    /* User database */
  sqlite3 *dbm;                   /* In-memory db for this analysis */

  int bRun;                       /* True once analysis has run */
  char **pzErrmsg;

  IdxScan *pScan;                 /* List of scan objects */
  IdxStatement *pStatement;       /* List of IdxStatement objects */
  int rc;                         /* Error code from whereinfo hook */

  IdxHash hIdx;                   /* Hash containing all candidate indexes */
};


/*
** Allocate and return nByte bytes of zeroed memory using sqlite3_malloc(). 
** If the allocation fails, set *pRc to SQLITE_NOMEM and return NULL.
................................................................................
    memset(pRet, 0, nByte);
  }else{
    *pRc = SQLITE_NOMEM;
  }
  return pRet;
}

/*
** Initialize an IdxHash64 hash table.
*/












static void idxHash64Init(IdxHash64 *pHash){
  memset(pHash, 0, sizeof(IdxHash64));
}

/*
** Reset an IdxHash64 hash table.
*/
static void idxHash64Clear(IdxHash64 *pHash){
  IdxHash64Entry *pEntry;
  IdxHash64Entry *pNext;
  for(pEntry=pHash->pFirst; pEntry; pEntry=pNext){
    pNext = pEntry->pNext;
    sqlite3_free(pEntry);
  }
  memset(pHash, 0, sizeof(IdxHash64));
}

/*
** Add iVal to the IdxHash64 hash table passed as the second argument. This
** function is a no-op if iVal is already present in the hash table.
*/
static void idxHash64Add(int *pRc, IdxHash64 *pHash, u64 iVal){
  int iHash = (int)((iVal*7) % IDX_HASH_SIZE);
  IdxHash64Entry *pEntry;
  assert( iHash>=0 );

  for(pEntry=pHash->aHash[iHash]; pEntry; pEntry=pEntry->pHashNext){
    if( pEntry->iVal==iVal ) return;
................................................................................
    pEntry->pHashNext = pHash->aHash[iHash];
    pHash->aHash[iHash] = pEntry;
    pEntry->pNext = pHash->pFirst;
    pHash->pFirst = pEntry;
  }
}

/*
** Initialize an IdxHash hash table.
*/
static void idxHashInit(IdxHash *pHash){
  memset(pHash, 0, sizeof(IdxHash));
}

/*
** Reset an IdxHash hash table.
*/
static void idxHashClear(IdxHash *pHash){
  int i;
  for(i=0; i<IDX_HASH_SIZE; i++){
    IdxHashEntry *pEntry;
    IdxHashEntry *pNext;
    for(pEntry=pHash->aHash[i]; pEntry; pEntry=pNext){
      pNext = pEntry->pHashNext;
      sqlite3_free(pEntry);
    }
  }
  memset(pHash, 0, sizeof(IdxHash));
}

/*
** Return the index of the hash bucket that the string specified by the
** arguments to this function belongs.
*/
static int idxHashString(const char *z, int n){
  unsigned int ret = 0;
  int i;
  for(i=0; i<n; i++){
    ret += (ret<<3) + (unsigned char)(z[i]);
  }
  return (int)(ret % IDX_HASH_SIZE);
}

/*
** If zKey is already present in the hash table, return non-zero and do
** nothing. Otherwise, add an entry with key zKey and payload string zVal to
** the hash table passed as the second argument. 
*/
static int idxHashAdd(
  int *pRc, 
  IdxHash *pHash, 
  const char *zKey,
  const char *zVal
){
  int nKey = strlen(zKey);
................................................................................

    pEntry->pNext = pHash->pFirst;
    pHash->pFirst = pEntry;
  }
  return 0;
}

/*
** If the hash table contains an entry with a key equal to the string
** passed as the final two arguments to this function, return a pointer
** to the payload string. Otherwise, if zKey/nKey is not present in the
** hash table, return NULL.
*/
static const char *idxHashSearch(IdxHash *pHash, const char *zKey, int nKey){
  int iHash;
  IdxHashEntry *pEntry;
  if( nKey<0 ) nKey = strlen(zKey);
  iHash = idxHashString(zKey, nKey);
  assert( iHash>=0 );
  for(pEntry=pHash->aHash[iHash]; pEntry; pEntry=pEntry->pHashNext){
................................................................................
    if( strlen(pEntry->zKey)==nKey && 0==memcmp(pEntry->zKey, zKey, nKey) ){
      return pEntry->zVal;
    }
  }
  return 0;
}





/*
** Allocate and return a new IdxConstraint object. Set the IdxConstraint.zColl
** variable to point to a copy of nul-terminated string zColl.
*/
static IdxConstraint *idxNewConstraint(int *pRc, const char *zColl){
  IdxConstraint *pNew;
  int nColl = strlen(zColl);
................................................................................
      case SQLITE_WHEREINFO_RANGE: {
        IdxConstraint *pNew = idxNewConstraint(&p->rc, zVal);
        if( pNew==0 ) return;
        pNew->iCol = iVal;
        pNew->depmask = mask;

        if( eOp==SQLITE_WHEREINFO_RANGE ){
          pNew->pNext = p->pScan->pRange;
          p->pScan->pRange = pNew;
        }else{
          pNew->pNext = p->pScan->pEq;
          p->pScan->pEq = pNew;
        }
        break;
      }
    }
  }
}

................................................................................
static void idxDatabaseError(
  sqlite3 *db,                    /* Database handle */
  char **pzErrmsg                 /* Write error here */
){
  *pzErrmsg = sqlite3_mprintf("%s", sqlite3_errmsg(db));
}

/*
** Prepare an SQL statement.
*/
static int idxPrepareStmt(
  sqlite3 *db,                    /* Database handle to compile against */
  sqlite3_stmt **ppStmt,          /* OUT: Compiled SQL statement */
  char **pzErrmsg,                /* OUT: sqlite3_malloc()ed error message */
  const char *zSql                /* SQL statement to compile */
){
  int rc = sqlite3_prepare_v2(db, zSql, -1, ppStmt, 0);
................................................................................
  if( rc!=SQLITE_OK ){
    *ppStmt = 0;
    idxDatabaseError(db, pzErrmsg);
  }
  return rc;
}

/*
** Prepare an SQL statement using the results of a printf() formatting.
*/
static int idxPrintfPrepareStmt(
  sqlite3 *db,                    /* Database handle to compile against */
  sqlite3_stmt **ppStmt,          /* OUT: Compiled SQL statement */
  char **pzErrmsg,                /* OUT: sqlite3_malloc()ed error message */
  const char *zFmt,               /* printf() format of SQL statement */
  ...                             /* Trailing printf() arguments */
){
................................................................................
    rc = idxPrepareStmt(db, ppStmt, pzErrmsg, zSql);
    sqlite3_free(zSql);
  }
  va_end(ap);
  return rc;
}

/*
** Finalize SQL statement pStmt. If (*pRc) is SQLITE_OK when this function
** is called, set it to the return value of sqlite3_finalize() before
** returning. Otherwise, discard the sqlite3_finalize() return value.
*/
static void idxFinalize(int *pRc, sqlite3_stmt *pStmt){
  int rc = sqlite3_finalize(pStmt);
  if( *pRc==SQLITE_OK ) *pRc = rc;
}

/*
** Attempt to allocate an IdxTable structure corresponding to table zTab
** in the main database of connection db. If successful, set (*ppOut) to
** point to the new object and return SQLITE_OK. Otherwise, return an
** SQLite error code and set (*ppOut) to NULL. In this case *pzErrmsg may be
** set to point to an error string.
**
** It is the responsibility of the caller to eventually free either the
** IdxTable object or error message using sqlite3_free().
*/
static int idxGetTableInfo(


  sqlite3 *db,                    /* Database connection to read details from */
  const char *zTab,               /* Table name */
  IdxTable **ppOut,               /* OUT: New object (if successful) */
  char **pzErrmsg                 /* OUT: Error message (if not) */
){

  sqlite3_stmt *p1 = 0;
  int nCol = 0;
  int nByte = sizeof(IdxTable);
  IdxTable *pNew = 0;
  int rc, rc2;
  char *pCsr;

  rc = idxPrintfPrepareStmt(db, &p1, pzErrmsg, "PRAGMA table_info=%Q", zTab);
  while( rc==SQLITE_OK && SQLITE_ROW==sqlite3_step(p1) ){
    const char *zCol = (const char*)sqlite3_column_text(p1, 1);
    nByte += 1 + strlen(zCol);
    rc = sqlite3_table_column_metadata(
        db, "main", zTab, zCol, 0, &zCol, 0, 0, 0
    );
    nByte += 1 + strlen(zCol);
    nCol++;
  }
  rc2 = sqlite3_reset(p1);
  if( rc==SQLITE_OK ) rc = rc2;

................................................................................
    int nCopy = strlen(zCol) + 1;
    pNew->aCol[nCol].zName = pCsr;
    pNew->aCol[nCol].iPk = sqlite3_column_int(p1, 5);
    memcpy(pCsr, zCol, nCopy);
    pCsr += nCopy;

    rc = sqlite3_table_column_metadata(
        db, "main", zTab, zCol, 0, &zCol, 0, 0, 0
    );
    if( rc==SQLITE_OK ){
      nCopy = strlen(zCol) + 1;
      pNew->aCol[nCol].zColl = pCsr;
      memcpy(pCsr, zCol, nCopy);
      pCsr += nCopy;
    }

    nCol++;
  }
  idxFinalize(&rc, p1);

  if( rc!=SQLITE_OK ){


    sqlite3_free(pNew);
    pNew = 0;
  }

  *ppOut = pNew;
  return rc;
}

/*
** This function is a no-op if *pRc is set to anything other than 
** SQLITE_OK when it is called.
**
................................................................................
    sqlite3_free(zAppend);
    sqlite3_free(zIn);
  }
  va_end(ap);
  return zRet;
}

/*
** Return true if zId must be quoted in order to use it as an SQL
** identifier, or false otherwise.
*/
static int idxIdentifierRequiresQuotes(const char *zId){
  int i;
  for(i=0; zId[i]; i++){
    if( !(zId[i]=='_')
     && !(zId[i]>='0' && zId[i]<='9')
     && !(zId[i]>='a' && zId[i]<='z')
     && !(zId[i]>='A' && zId[i]<='Z')
................................................................................
    ){
      return 1;
    }
  }
  return 0;
}

/*
** This function appends an index column definition suitable for constraint
** pCons to the string passed as zIn and returns the result.
*/
static char *idxAppendColDefn(


  int *pRc,                       /* IN/OUT: Error code */
  char *zIn,                      /* Column defn accumulated so far */
  IdxTable *pTab,                 /* Table index will be created on */
  IdxConstraint *pCons
){
  char *zRet = zIn;
  IdxColumn *p = &pTab->aCol[pCons->iCol];
  if( zRet ) zRet = idxAppendText(pRc, zRet, ", ");

  if( idxIdentifierRequiresQuotes(p->zName) ){
................................................................................

  *pRc = rc;
  return 0;
}

static int idxCreateFromCons(
  sqlite3expert *p,
  IdxTable *pTab,
  IdxScan *pScan,
  IdxConstraint *pEq, 
  IdxConstraint *pTail
){
  sqlite3 *dbm = p->dbm;
  int rc = SQLITE_OK;
  if( (pEq || pTail) && 0==idxFindCompatible(&rc, dbm, pScan, pEq, pTail) ){

    char *zCols = 0;
    char *zIdx = 0;
    IdxConstraint *pCons;
    int h = 0;
    const char *zFmt;

    for(pCons=pEq; pCons; pCons=pCons->pLink){
................................................................................
    if( p->iCol==pCmp->iCol ) return 1;
  }
  return 0;
}

static int idxCreateFromWhere(
  sqlite3expert *p, 
  IdxTable *pTab,
  i64 mask,                       /* Consider only these constraints */
  IdxScan *pScan,                 /* Create indexes for this scan */

  IdxConstraint *pEq,             /* == constraints for inclusion */
  IdxConstraint *pTail            /* range/ORDER BY constraints for inclusion */
){
  IdxConstraint *p1 = pEq;
  IdxConstraint *pCon;
  int rc;

  /* Gather up all the == constraints that match the mask. */
  for(pCon=pScan->pEq; pCon; pCon=pCon->pNext){
    if( (mask & pCon->depmask)==pCon->depmask 
     && idxFindConstraint(p1, pCon)==0
     && idxFindConstraint(pTail, pCon)==0
    ){
      pCon->pLink = p1;
      p1 = pCon;
    }
  }

  /* Create an index using the == constraints collected above. And the
  ** range constraint/ORDER BY terms passed in by the caller, if any. */
  rc = idxCreateFromCons(p, pTab, pScan, p1, pTail);

  /* If no range/ORDER BY passed by the caller, create a version of the
  ** index for each range constraint that matches the mask. */
  if( pTail==0 ){
    for(pCon=pScan->pRange; rc==SQLITE_OK && pCon; pCon=pCon->pNext){
      assert( pCon->pLink==0 );
      if( (mask & pCon->depmask)==pCon->depmask
        && idxFindConstraint(pEq, pCon)==0
        && idxFindConstraint(pTail, pCon)==0
      ){
        rc = idxCreateFromCons(p, pTab, pScan, p1, pCon);
      }
    }
  }

  return rc;
}

................................................................................
  int rc = SQLITE_OK;
  IdxScan *pIter;
  IdxHash64 hMask;
  idxHash64Init(&hMask);

  for(pIter=p->pScan; pIter && rc==SQLITE_OK; pIter=pIter->pNextScan){
    IdxHash64Entry *pEntry;

    IdxConstraint *pCons;
    IdxTable *pTab = 0;

    rc = idxGetTableInfo(p->dbm, pIter->zTable, &pTab, pzErr);

    idxHash64Add(&rc, &hMask, 0);
    for(pCons=pIter->pEq; pCons; pCons=pCons->pNext){
      for(pEntry=hMask.pFirst; pEntry; pEntry=pEntry->pNext){
        idxHash64Add(&rc, &hMask, pEntry->iVal | (u64)pCons->depmask);
      }
    }

    for(pEntry=hMask.pFirst; rc==SQLITE_OK && pEntry; pEntry=pEntry->pNext){
      i64 mask = (i64)pEntry->iVal;
      rc = idxCreateFromWhere(p, pTab, mask, pIter, 0, 0);
      if( rc==SQLITE_OK && pIter->pOrder ){
        rc = idxCreateFromWhere(p, pTab, mask, pIter, 0, pIter->pOrder);
      }
    }

    sqlite3_free(pTab);
    idxHash64Clear(&hMask);
  }

  return rc;
}

/*
** Free all elements of the linked list starting at pConstraint.
*/
static void idxConstraintFree(IdxConstraint *pConstraint){
  IdxConstraint *pNext;
  IdxConstraint *p;

  for(p=pConstraint; p; p=pNext){
    pNext = p->pNext;
    sqlite3_free(p);
................................................................................
*/
static void idxScanFree(IdxScan *pScan, IdxScan *pLast){
  IdxScan *p;
  IdxScan *pNext;
  for(p=pScan; p!=pLast; p=pNext){
    pNext = p->pNextScan;
    idxConstraintFree(p->pOrder);
    idxConstraintFree(p->pEq);
    idxConstraintFree(p->pRange);

    sqlite3_free(p);
  }
}

/*
** Free all elements of the linked list starting from pStatement up 
** until pLast (pLast is not freed).
................................................................................
    sqlite3_free(p->zEQP);
    sqlite3_free(p->zIdx);
    sqlite3_free(p);
  }
}


/*
** This function is called after candidate indexes have been created. It
** runs all the queries to see which indexes they prefer, and populates
** IdxStatement.zIdx and IdxStatement.zEQP with the results.
*/
int idxFindIndexes(
  sqlite3expert *p,
  char **pzErr                         /* OUT: Error message (sqlite3_malloc) */
){
  IdxStatement *pStmt;
  sqlite3 *dbm = p->dbm;
  int rc = SQLITE_OK;
................................................................................
    p->pStatement = pStmtOrig;
  }

  return rc;
}

int sqlite3_expert_analyze(sqlite3expert *p, char **pzErr){
  int rc;







  /* Create candidate indexes within the in-memory database file */

  rc = idxCreateCandidates(p, pzErr);


  /* Figure out which of the candidate indexes are preferred by the query
  ** planner and report the results to the user.  */
  if( rc==SQLITE_OK ){
    rc = idxFindIndexes(p, pzErr);
  }