SQLite

  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=?) OR e=?) AND (f=? OR g=?) AND h>?
**
** The above is decomposed into 5 AND connected clauses. The first two are
** added to the IdxWhere.pEq linked list, the following two into 
** IdxWhere.pOr and the last into IdxWhere.pRange.
**
** IdxWhere.pEq and IdxWhere.pRange are simple linked lists of IdxConstraint
** objects linked by the IdxConstraint.pNext field.
**
** The list headed at IdxWhere.pOr and linked by IdxWhere.pNextOr contains
** all "OR" terms that belong to the current WHERE clause. In the example
** above, there are two OR terms:
**
**   ((c=? AND d=?) OR e=?)
**   (f=? OR g=?)
**
** Within an OR term, the OR connected sub-expressions are termed siblings.
** These are connected into a linked list by the pSibling pointers. Each OR
** term above consists of two siblings.
**
**   pOr -> (c=? AND d=?) -> pNextOr -> (f=?)
**               |                        |
**            pSibling                 pSibling
**               |                        |
**               V                        V
**             (e=?)                    (g=?)
**
** IdxWhere.pParent is only used while constructing a tree of IdxWhere 
** structures. It is NULL for the root IdxWhere. For all others, the parent
** WHERE clause.
*/
struct IdxWhere {
  IdxConstraint *pEq;             /* List of == constraints */
  IdxConstraint *pRange;          /* List of < constraints */
  IdxWhere *pOr;                  /* List of OR constraints */
  IdxWhere *pNextOr;              /* Next in OR constraints of same IdxWhere */
  IdxWhere *pSibling;             /* Next branch in single OR constraint */
  IdxWhere *pParent;              /* Parent object (or NULL) */
};

/*
** A single scan of a single table.
*/
struct IdxScan {
  IdxTable *pTable;               /* Table-info */

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

static char *idxQueryToList(
  sqlite3 *db, 
  const char *zBind,
  int *pRc,
  char **pzErrmsg,
  const char *zSql
){
  char *zRet = 0;
  if( *pRc==SQLITE_OK ){
    sqlite3_stmt *pStmt = 0;
    int rc = sqlite3_prepare_v2(db, zSql, -1, &pStmt, 0);
    if( rc==SQLITE_OK ){
      sqlite3_bind_text(pStmt, 1, zBind, -1, SQLITE_TRANSIENT);
      while( rc==SQLITE_OK && sqlite3_step(pStmt)==SQLITE_ROW ){
        const char *z = (const char*)sqlite3_column_text(pStmt, 0);
        zRet = sqlite3_mprintf("%z%s%Q", zRet, zRet?", ":"", z);
        if( zRet==0 ){
          rc = SQLITE_NOMEM;
        }
      }
      rc = sqlite3_finalize(pStmt);
    }

    if( rc ){
      idxDatabaseError(db, pzErrmsg);
      sqlite3_free(zRet);
      zRet = 0;
    }
    *pRc = rc;
  }

  return zRet;
}

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);

  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 = 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++;
  }

    pNew->aCol = (IdxColumn*)&pNew[1];
    pNew->nCol = nCol;
    pCsr = (char*)&pNew->aCol[nCol];
  }

  nCol = 0;
  while( rc==SQLITE_OK && SQLITE_ROW==sqlite3_step(p1) ){
    const char *zCol = sqlite3_column_text(p1, 1);
    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(

static int idxCreateTables(
  sqlite3 *db,                    /* User database */
  sqlite3 *dbm,                   /* In-memory database to create tables in */
  IdxScan *pScan,                 /* List of scans */
  char **pzErrmsg                 /* OUT: Error message */
){
  int rc = SQLITE_OK;

  IdxScan *pIter;
  for(pIter=pScan; pIter && rc==SQLITE_OK; pIter=pIter->pNextScan){
    rc = idxGetTableInfo(db, pIter, pzErrmsg);

    /* Test if table has already been created. If so, jump to the next
    ** iteration of the loop.  */
    if( rc==SQLITE_OK ){
      sqlite3_stmt *pSql = 0;
      rc = idxPrintfPrepareStmt(dbm, &pSql, pzErrmsg, 
          "SELECT 1 FROM sqlite_master WHERE tbl_name = %Q", pIter->zTable
      );
      if( rc==SQLITE_OK ){
        int bSkip = 0;
        if( sqlite3_step(pSql)==SQLITE_ROW ) bSkip = 1;
        rc = sqlite3_finalize(pSql);
        if( bSkip ) continue;
      }
    }

    if( rc==SQLITE_OK ){
      int rc2;
      sqlite3_stmt *pSql = 0;
      rc = idxPrintfPrepareStmt(db, &pSql, pzErrmsg, 
          "SELECT sql FROM sqlite_master WHERE tbl_name = %Q", pIter->zTable
      );
      while( rc==SQLITE_OK && SQLITE_ROW==sqlite3_step(pSql) ){
        const char *zSql = (const char*)sqlite3_column_text(pSql, 0);
        rc = sqlite3_exec(dbm, zSql, 0, 0, pzErrmsg);
      }
      rc2 = sqlite3_finalize(pSql);
      if( rc==SQLITE_OK ) rc = rc2;
    }



  }
  return rc;
}

/*
** This function is a no-op if *pRc is set to anything other than 
** SQLITE_OK when it is called.

  return rc;
}

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

static int idxCreateForeachOr(
  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(pCtx, mask, pScan, p1, pEq, pTail);
    for(p2=p1->pSibling; p2 && rc==SQLITE_OK; p2=p2->pSibling){
      rc = idxCreateFromWhere(pCtx, mask, pScan, p2, pEq, pTail);
    }
  }
  return rc;
}

/*
** Return true if list pList (linked by IdxConstraint.pLink) contains
** a constraint compatible with *p. Otherwise return false.
*/
static int idxFindConstraint(IdxConstraint *pList, IdxConstraint *p){
  IdxConstraint *pCmp;
  for(pCmp=pList; pCmp; pCmp=pCmp->pLink){
    if( p->iCol==pCmp->iCol ) return 1;
  }
  return 0;
}

static int idxCreateFromWhere(
  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 
     && 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(pCtx, pScan, p1, pTail);
  if( rc==SQLITE_OK ){
    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
        && idxFindConstraint(pEq, pCon)==0
        && idxFindConstraint(pTail, pCon)==0
      ){
        rc = idxCreateFromCons(pCtx, pScan, p1, pCon);
        if( rc==SQLITE_OK ){
          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(IdxContext *pCtx){
  sqlite3 *dbm = pCtx->dbm;
  int rc2;
  int rc = SQLITE_OK;
  sqlite3_stmt *pDepmask;         /* Foreach depmask */
  IdxScan *pIter;

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

  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);

}

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

  }
}

int idxFindIndexes(
  IdxContext *pCtx,
  const char *zSql,                    /* SQL to find indexes for */
  void (*xOut)(void*, const char*),    /* Output callback */

      }
    }
  }
  rc2 = sqlite3_reset(pExplain);
  if( rc==SQLITE_OK ) rc = rc2;
  if( rc==SQLITE_OK ){
    sqlite3_stmt *pLoop = 0;
    rc = idxPrepareStmt(dbm, &pLoop, pzErr, "SELECT name FROM aux.indexes");
    if( rc==SQLITE_OK ){
      while( SQLITE_ROW==sqlite3_step(pLoop) ){
        bFound = 1;
        xOut(pOutCtx, sqlite3_column_text(pLoop, 0));
      }
      rc = sqlite3_finalize(pLoop);
    }
    if( rc==SQLITE_OK ){
      if( bFound==0 ) xOut(pOutCtx, "(no new indexes)");
      xOut(pOutCtx, "");
    }

}

do_setup_rec_test 1.2 {
  CREATE TABLE t1(a, b, c);
} {
  SELECT * FROM t1 WHERE b>?;
} {
  CREATE INDEX t1_idx_00000062 ON t1(b) 
  0|0|0|SEARCH TABLE t1 USING INDEX t1_idx_00000062 (b>?)
}

do_setup_rec_test 1.3 {
  CREATE TABLE t1(a, b, c);
} {
  SELECT * FROM t1 WHERE b COLLATE nocase BETWEEN ? AND ?
} {
  CREATE INDEX t1_idx_3e094c27 ON t1(b COLLATE NOCASE) 
  0|0|0|SEARCH TABLE t1 USING INDEX t1_idx_3e094c27 (b>? AND b<?)
}

do_setup_rec_test 1.4 {
  CREATE TABLE t1(a, b, c);
} {
  SELECT a FROM t1 ORDER BY b;
} {
  CREATE INDEX t1_idx_00000062 ON t1(b) 
  0|0|0|SCAN TABLE t1 USING INDEX t1_idx_00000062
}

do_setup_rec_test 1.5 {
  CREATE TABLE t1(a, b, c);
} {
  SELECT a FROM t1 WHERE a=? ORDER BY b;
} {
  CREATE INDEX t1_idx_000123a7 ON t1(a, b) 
  0|0|0|SEARCH TABLE t1 USING COVERING INDEX t1_idx_000123a7 (a=?)
}

do_setup_rec_test 1.6 {
  CREATE TABLE t1(a, b, c);
} {
  SELECT min(a) FROM t1
} {
  CREATE INDEX t1_idx_00000061 ON t1(a) 
  0|0|0|SEARCH TABLE t1 USING COVERING INDEX t1_idx_00000061
}

do_setup_rec_test 1.7 {
  CREATE TABLE t1(a, b, c);
} {
  SELECT * FROM t1 ORDER BY a, b, c;
} {
  CREATE INDEX t1_idx_033e95fe ON t1(a, b, c) 
  0|0|0|SCAN TABLE t1 USING COVERING INDEX t1_idx_033e95fe
}

do_setup_rec_test 1.8 {
  CREATE TABLE t1(a, b, c);
} {
  SELECT * FROM t1 ORDER BY a ASC, b COLLATE nocase DESC, c ASC;
} {
  CREATE INDEX t1_idx_5be6e222 ON t1(a, b COLLATE NOCASE DESC, c)
  0|0|0|SCAN TABLE t1 USING COVERING INDEX t1_idx_5be6e222
}

do_setup_rec_test 1.9 {
  CREATE TABLE t1(a COLLATE NOCase, b, c);
} {
  SELECT * FROM t1 WHERE a=?
} {
  CREATE INDEX t1_idx_00000061 ON t1(a) 
  0|0|0|SEARCH TABLE t1 USING INDEX t1_idx_00000061 (a=?)
}


# Tables with names that require quotes.
#
do_setup_rec_test 8.1 {
  CREATE TABLE "t t"(a, b, c);
} {
  SELECT * FROM "t t" WHERE a=?
} {
  CREATE INDEX 't t_idx_00000061' ON 't t'(a)
  0|0|0|SEARCH TABLE t t USING INDEX t t_idx_00000061 (a=?) 
}

do_setup_rec_test 8.2 {
  CREATE TABLE "t t"(a, b, c);
} {
  SELECT * FROM "t t" WHERE b BETWEEN ? AND ?
} {
  CREATE INDEX 't t_idx_00000062' ON 't t'(b) 
  0|0|0|SEARCH TABLE t t USING INDEX t t_idx_00000062 (b>? AND b<?)
}

# Columns with names that require quotes.
#
do_setup_rec_test 9.1 {
  CREATE TABLE t3(a, "b b", c);
} {
  SELECT * FROM t3 WHERE "b b" = ?
} {
  CREATE INDEX t3_idx_00050c52 ON t3('b b') 
  0|0|0|SEARCH TABLE t3 USING INDEX t3_idx_00050c52 (b b=?)
}

do_setup_rec_test 9.2 {
  CREATE TABLE t3(a, "b b", c);
} {
  SELECT * FROM t3 ORDER BY "b b"
} {
  CREATE INDEX t3_idx_00050c52 ON t3('b b') 
  0|0|0|SCAN TABLE t3 USING INDEX t3_idx_00050c52
}

# Transitive constraints
#
do_setup_rec_test 10.1 {
  CREATE TABLE t5(a, b);
  CREATE TABLE t6(c, d);
} {
  SELECT * FROM t5, t6 WHERE a=? AND b=c AND c=?
} {
  CREATE INDEX t5_idx_000123a7 ON t5(a, b) 
  CREATE INDEX t6_idx_00000063 ON t6(c) 
  0|0|1|SEARCH TABLE t6 USING INDEX t6_idx_00000063 (c=?) 
  0|1|0|SEARCH TABLE t5 USING COVERING INDEX t5_idx_000123a7 (a=? AND b=?)
}

# OR terms.
#
do_setup_rec_test 11.1 {
  CREATE TABLE t7(a, b);
} {
  SELECT * FROM t7 WHERE a=? OR b=?
} {
  CREATE INDEX t7_idx_00000061 ON t7(a) 
  CREATE INDEX t7_idx_00000062 ON t7(b)
  0|0|0|SEARCH TABLE t7 USING INDEX t7_idx_00000061 (a=?) 
  0|0|0|SEARCH TABLE t7 USING INDEX t7_idx_00000062 (b=?)
}

finish_test