SQLite

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

/*
** Context object passed to idxWhereInfo()
*/
struct IdxContext {
  char **pzErrmsg;
  IdxWhere *pCurrent;             /* Current where clause */
  int rc;                         /* Error code (if error has occurred) */
  IdxScan *pScan;                 /* List of scan objects */
  sqlite3 *dbm;                   /* In-memory db for this analysis */
  sqlite3 *db;                    /* User database under analysis */
  sqlite3_stmt *pInsertMask;      /* To write to aux.depmask */
  i64 iIdxRowid;                  /* Rowid of first index created */
};

/*
** Data regarding a database table. Extracted from "PRAGMA table_info"
*/
struct IdxColumn {
  char *zName;

  if( rc==SQLITE_OK ) rc = rc2;

  *pRc = rc;
  return 0;
}

static int idxCreateFromCons(
  sqlite3 *dbm,
  IdxContext *pCtx,
  IdxScan *pScan,
  IdxConstraint *pEq, 
  IdxConstraint *pTail
){
  sqlite3 *dbm = pCtx->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){
      zCols = idxAppendColDefn(&rc, zCols, pTab, pCons);
    }
    for(pCons=pTail; pCons; pCons=pCons->pLink){
      zCols = idxAppendColDefn(&rc, zCols, pTab, pCons);
    }

    /* Hash the list of columns to come up with a name for the index */
    if( rc==SQLITE_OK ){
      /* Hash the list of columns to come up with a name for the index */
      int i;
      for(i=0; zCols[i]; i++){
        h += ((h<<3) + zCols[i]);
      }

      if( idxIdentifierRequiresQuotes(pScan->zTable) ){
        zFmt = "CREATE INDEX '%q_idx_%08x' ON %Q(%s)";
      }else{
        zFmt = "CREATE INDEX %s_idx_%08x ON %s(%s)";
      }
      zIdx = sqlite3_mprintf(zFmt, pScan->zTable, h, pScan->zTable, zCols);
      if( !zIdx ){
        rc = SQLITE_NOMEM;
      }else{
        rc = sqlite3_exec(dbm, zIdx, 0, 0, 0);
#if 0
        printf("/* %s */\n", zIdx);
#endif
      }
    }
    if( rc==SQLITE_OK && pCtx->iIdxRowid==0 ){
      int rc2;
      sqlite3_stmt *pLast = 0;
      rc = idxPrepareStmt(dbm, &pLast, pCtx->pzErrmsg, 
          "SELECT max(rowid) FROM sqlite_master"
      );
      if( rc==SQLITE_OK && SQLITE_ROW==sqlite3_step(pLast) ){
        pCtx->iIdxRowid = sqlite3_column_int64(pLast, 0);
      }
      rc2 = sqlite3_finalize(pLast);
      if( rc==SQLITE_OK ) rc = rc2;
    }

    sqlite3_free(zIdx);
    sqlite3_free(zCols);
  }
  return rc;
}

static int idxCreateFromWhere(
    sqlite3*, i64, IdxScan*, IdxWhere*, IdxConstraint*, IdxConstraint*
    IdxContext*, i64, IdxScan*, IdxWhere*, IdxConstraint*, IdxConstraint*
);

static int idxCreateForeachOr(
  sqlite3 *dbm, 
  IdxContext *pCtx, 
  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 */
){
  int rc = SQLITE_OK;
  IdxWhere *p1;
  IdxWhere *p2;
  for(p1=pWhere->pOr; p1 && rc==SQLITE_OK; p1=p1->pNextOr){
    rc = idxCreateFromWhere(dbm, mask, pScan, p1, pEq, pTail);
    rc = idxCreateFromWhere(pCtx, mask, pScan, p1, pEq, pTail);
    for(p2=p1->pSibling; p2 && rc==SQLITE_OK; p2=p2->pSibling){
      rc = idxCreateFromWhere(dbm, mask, pScan, p2, pEq, pTail);
      rc = idxCreateFromWhere(pCtx, mask, pScan, p2, pEq, pTail);
    }
  }
  return rc;
}

static int idxCreateFromWhere(
  sqlite3 *dbm, 
  IdxContext *pCtx, 
  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 */
){
  sqlite3 *dbm = pCtx->dbm;
  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 ){
      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(dbm, pScan, p1, pTail);
  rc = idxCreateFromCons(pCtx, pScan, p1, pTail);
  if( rc==SQLITE_OK ){
    rc = idxCreateForeachOr(dbm, mask, pScan, pWhere, p1, pTail);
    rc = idxCreateForeachOr(pCtx, mask, pScan, pWhere, 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 ){
        rc = idxCreateFromCons(dbm, pScan, p1, pCon);
        rc = idxCreateFromCons(pCtx, pScan, p1, pCon);
        if( rc==SQLITE_OK ){
          rc = idxCreateForeachOr(dbm, mask, pScan, pWhere, p1, pCon);
          rc = idxCreateForeachOr(pCtx, mask, pScan, pWhere, p1, pCon);
        }
      }
    }
  }

  return rc;
}

/*
** Create candidate indexes in database [dbm] based on the data in 
** linked-list pScan.
*/
static int idxCreateCandidates(
  sqlite3 *dbm,
static int idxCreateCandidates(IdxContext *pCtx){
  sqlite3 *dbm = pCtx->dbm;
  IdxScan *pScan,
  char **pzErrmsg
){
  int rc2;
  int rc = SQLITE_OK;
  sqlite3_stmt *pDepmask;         /* Foreach depmask */
  IdxScan *pIter;

  rc = idxPrepareStmt(pCtx->dbm, &pDepmask, pCtx->pzErrmsg, 
  rc = idxPrepareStmt(dbm, &pDepmask, pzErrmsg, "SELECT mask FROM depmask");
      "SELECT mask FROM depmask"
  );

  for(pIter=pScan; pIter && rc==SQLITE_OK; pIter=pIter->pNextScan){
  for(pIter=pCtx->pScan; pIter && rc==SQLITE_OK; pIter=pIter->pNextScan){
    IdxWhere *pWhere = &pIter->where;
    while( SQLITE_ROW==sqlite3_step(pDepmask) && rc==SQLITE_OK ){
      i64 mask = sqlite3_column_int64(pDepmask, 0);
      rc = idxCreateFromWhere(dbm, mask, pIter, pWhere, 0, 0);
      rc = idxCreateFromWhere(pCtx, mask, pIter, pWhere, 0, 0);
      if( rc==SQLITE_OK && pIter->pOrder ){
        rc = idxCreateFromWhere(dbm, mask, pIter, pWhere, 0, pIter->pOrder);
        rc = idxCreateFromWhere(pCtx, mask, pIter, pWhere, 0, pIter->pOrder);
      }
    }
  }

  rc2 = sqlite3_finalize(pDepmask);
  if( rc==SQLITE_OK ) rc = rc2;
  return rc;
}

static void idxScanFree(IdxScan *pScan){
  IdxScan *pIter;
  IdxScan *pNext;
  for(pIter=pScan; pIter; pIter=pNext){
    pNext = pIter->pNextScan;

  }
}

int idxFindIndexes(
  sqlite3 *dbm,                        /* Database handle */
  IdxContext *pCtx,
  const char *zSql,                    /* SQL to find indexes for */
  void (*xOut)(void*, const char*),    /* Output callback */
  void *pOutCtx,                       /* Context for xOut() */
  char **pzErr                         /* OUT: Error message (sqlite3_malloc) */
){
  sqlite3 *dbm = pCtx->dbm;
  sqlite3_stmt *pExplain = 0;
  sqlite3_stmt *pSelect = 0;
  int rc, rc2;
  int bFound = 0;

  rc = idxPrintfPrepareStmt(dbm, &pExplain, pzErr,"EXPLAIN QUERY PLAN %s",zSql);
  if( rc==SQLITE_OK ){
    rc = idxPrepareStmt(dbm, &pSelect, pzErr, 
        "SELECT sql FROM sqlite_master WHERE name = ?"
        "SELECT rowid, sql FROM sqlite_master WHERE name = ?"
    );
  }

  while( rc==SQLITE_OK && sqlite3_step(pExplain)==SQLITE_ROW ){
    int i;
    const char *zDetail = (const char*)sqlite3_column_text(pExplain, 3);
    int nDetail = strlen(zDetail);

    for(i=0; i<nDetail; i++){
      if( memcmp(&zDetail[i], " USING INDEX ", 13)==0 ){
        int nIdx = 0;
        const char *zIdx = &zDetail[i+13];
        while( zIdx[nIdx]!='\0' && zIdx[nIdx]!=' ' ) nIdx++;
        sqlite3_bind_text(pSelect, 1, zIdx, nIdx, SQLITE_STATIC);
        if( SQLITE_ROW==sqlite3_step(pSelect) ){
          i64 iRowid = sqlite3_column_int64(pSelect, 0);
          const char *zSql = (const char*)sqlite3_column_text(pSelect, 1);
          if( iRowid>=pCtx->iIdxRowid ){
          xOut(pOutCtx, sqlite3_column_text(pSelect, 0));
            xOut(pOutCtx, zSql);
            bFound = 1;
          }
        }
        rc = sqlite3_reset(pSelect);
        break;
      }
    }
  }
  rc2 = sqlite3_reset(pExplain);
  if( rc==SQLITE_OK ) rc = rc2;
  if( rc==SQLITE_OK ) xOut(pOutCtx, "");
  if( rc==SQLITE_OK ){
    if( bFound==0 ) xOut(pOutCtx, "(no new indexes)");
    xOut(pOutCtx, "");
  }

  while( rc==SQLITE_OK && sqlite3_step(pExplain)==SQLITE_ROW ){
    int iSelectid = sqlite3_column_int(pExplain, 0);
    int iOrder = sqlite3_column_int(pExplain, 1);
    int iFrom = sqlite3_column_int(pExplain, 2);
    const char *zDetail = (const char*)sqlite3_column_text(pExplain, 3);
    char *zOut;

  ** database (handle db). The attached in-memory db (aux) contains
  ** application tables used by the code in this file.  */
  rc = sqlite3_open(":memory:", &dbm);
  if( rc==SQLITE_OK ){
    rc = sqlite3_exec(dbm, 
        "ATTACH ':memory:' AS aux;"
        "CREATE TABLE aux.depmask(mask PRIMARY KEY) WITHOUT ROWID;"
        "CREATE TABLE aux.indexes(name PRIMARY KEY) WITHOUT ROWID;"
        "INSERT INTO aux.depmask VALUES(0);"
        , 0, 0, pzErrmsg
    );
  }

  /* Prepare an INSERT statement for writing to aux.depmask */
  if( rc==SQLITE_OK ){

  ** removed. */
  if( rc==SQLITE_OK ){
    rc = idxCreateTables(db, dbm, ctx.pScan, pzErrmsg);
  }

  /* Create candidate indexes within the in-memory database file */
  if( rc==SQLITE_OK ){
    rc = idxCreateCandidates(dbm, ctx.pScan, pzErrmsg);
    rc = idxCreateCandidates(&ctx);
  }

  /* 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(dbm, zSql, xOut, pOutCtx, pzErrmsg);
    rc = idxFindIndexes(&ctx, zSql, xOut, pOutCtx, pzErrmsg);
  }

  idxScanFree(ctx.pScan);
  sqlite3_finalize(ctx.pInsertMask);
  sqlite3_close(dbm);
  return rc;
}