SQLite

**   Used to temporarily link IdxConstraint objects into lists while
**   creating candidate indexes.
*/
struct IdxConstraint {
  char *zColl;                    /* Collation sequence */
  int bRange;                     /* True for range, false for eq */
  int iCol;                       /* Constrained table column */
  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 */
};

/*

  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 */
  sqlite3 *dbv;                   /* Vtab schema for this analysis */

    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 = idxMalloc(pRc, sizeof(IdxHash64Entry));
  if( pEntry ){
    pEntry->iVal = iVal;
    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));
}

    /* Link the new scan object into the list */
    pScan->pTab = p->pTab;
    pScan->pNextScan = p->pExpert->pScan;
    p->pExpert->pScan = pScan;

    /* Add the constraints to the IdxScan object */
    for(i=0; i<pIdxInfo->nConstraint; i++){
      int op = pIdxInfo->aConstraint[i].op;
      if( op&opmask ){
        IdxConstraint *pNew;
        const char *zColl = sqlite3_vtab_collation(dbv, i);
        pNew = idxNewConstraint(&rc, zColl);
        if( pNew ){
          pNew->iCol = pIdxInfo->aConstraint[i].iColumn;
          if( op==SQLITE_INDEX_CONSTRAINT_EQ ){
            pNew->pNext = pScan->pEq;
            pScan->pEq = pNew;
          }else{
            pNew->bRange = 1;
            pNew->pNext = pScan->pRange;
            pScan->pRange = pNew;
          }
        }
        if( pIdxInfo->aConstraint[i].usable ){
          n++;
          pIdxInfo->aConstraintUsage[i].argvIndex = n;
        }
      }
    }

    /* Add the ORDER BY to the IdxScan object */
    for(i=pIdxInfo->nOrderBy-1; i>=0; i--){
      IdxConstraint *pNew;
      const char *zColl = sqlite3_vtab_collation(dbv, i+pIdxInfo->nConstraint);
      pNew = idxNewConstraint(&rc, zColl);
      if( pNew ){
        pNew->iCol = pIdxInfo->aOrderBy[i].iColumn;
        pNew->bDesc = pIdxInfo->aOrderBy[i].desc;
        pNew->pNext = pScan->pOrder;
        pNew->pLink = pScan->pOrder;
        pScan->pOrder = pNew;
        n++;
      }
    }

  *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;
}

/*
** Create candidate indexes in database [dbm] based on the data in 
** linked-list pScan.
*/
static int idxCreateCandidates(sqlite3expert *p, char **pzErr){
  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 = pIter->pTab;

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

    idxHash64Clear(&hMask);
  }

  return rc;
}

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

  for(p=pStatement; p!=pLast; p=pNext){
    pNext = p->pNext;
    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.
*/

          rc = sqlite3_exec(p->dbv, zOuter, 0, 0, pzErrmsg);
        }
        sqlite3_free(zInner);
        sqlite3_free(zOuter);
      }
    }
  }

  return rc;
}

/*
** Allocate a new sqlite3expert object.
*/
sqlite3expert *sqlite3_expert_new(sqlite3 *db, char **pzErrmsg){

*/
void sqlite3_expert_destroy(sqlite3expert *p){
  if( p ){
    sqlite3_close(p->dbm);
    sqlite3_close(p->dbv);
    idxScanFree(p->pScan, 0);
    idxStatementFree(p->pStatement, 0);

    idxHashClear(&p->hIdx);

    sqlite3_free(p);
  }
}

#endif /* !defined(SQLITE_TEST) || defined(SQLITE_ENABLE_WHEREINFO_HOOK) */

  return rc;
}


struct BestIndexCtx {
  WhereClause *pWC;
  sqlite3_index_info *pIdxInfo;
  ExprList *pOrderBy;
  Parse *pParse;
};

const char *sqlite3_vtab_collation(sqlite3 *db, int iCons){
  struct BestIndexCtx *p = (struct BestIndexCtx*)db->pVtabWC;
  const char *zRet = 0;
  if( p && iCons>=0 ){
    if( iCons<p->pIdxInfo->nConstraint ){
      int iTerm = p->pIdxInfo->aConstraint[iCons].iTermOffset;
      Expr *pX = p->pWC->a[iTerm].pExpr;
      CollSeq *pC = sqlite3BinaryCompareCollSeq(p->pParse,pX->pLeft,pX->pRight);
      zRet = (pC ? pC->zName : "BINARY");
    }else{
      iCons -= p->pIdxInfo->nConstraint;
      if( iCons<p->pIdxInfo->nOrderBy ){
        Expr *pX = p->pOrderBy->a[iCons].pExpr;
        CollSeq *pC = sqlite3ExprCollSeq(p->pParse, pX);
        zRet = (pC ? pC->zName : "BINARY");
      }
    }
  }
  return zRet;
}

/*
** Add all WhereLoop objects for a table of the join identified by
** pBuilder->pNew->iTab.  That table is guaranteed to be a virtual table.

    sqlite3DbFree(pParse->db, p);
    return SQLITE_NOMEM_BKPT;
  }

  bic.pWC = pWC;
  bic.pIdxInfo = p;
  bic.pParse = pParse;
  bic.pOrderBy = pBuilder->pOrderBy;
  pSaved = pParse->db->pVtabWC;
  pParse->db->pVtabWC = (void*)&bic;

  /* First call xBestIndex() with all constraints usable. */
  WHERETRACE(0x40, ("  VirtualOne: all usable\n"));
  rc = whereLoopAddVirtualOne(pBuilder, mPrereq, ALLBITS, 0, p, mNoOmit, &bIn);