SQLite

        int addrInTop;         /* Top of the IN loop */
        u8 eEndLoopOp;         /* IN Loop terminator. OP_Next or OP_Prev */
      } *aInLoop;           /* Information about each nested IN operator */
    } in;                 /* Used when plan.wsFlags&WHERE_IN_ABLE */
    Index *pCovidx;       /* Possible covering index for WHERE_MULTI_OR */
  } u;
  double rOptCost;      /* "Optimal" cost for this level */
  struct WhereLoop *pWLoop;  /* The selected WhereLoop object */

  /* The following field is really not part of the current level.  But
  ** we need a place to cache virtual table index information for each
  ** virtual table in the FROM clause and the WhereLevel structure is
  ** a convenient place since there is one WhereLevel for each FROM clause
  ** element.
  */

** Each instance of this object represents a way of evaluating one
** term of a join.  The WhereClause object holds a table of these
** objects using (iTab,prereq,iOb,nOb) as the primary key.  Note that the
** same join term might have multiple associated WhereLoop objects.
*/
struct WhereLoop {
  Bitmask prereq;       /* Bitmask of other loops that must run first */
  Bitmask maskSelf;     /* Bitmask identifying table iTab */
  int iTab;             /* Index of the table coded by this loop */
  u16 iOb, nOb;         /* ORDER BY terms satisfied by this strategy */
  double rSetup;        /* One-time setup cost (ex: create transient index) */
  double rRun;          /* Cost of running each loop */
  double nOut;          /* Estimated number of output rows */
  u32 wsFlags;          /* WHERE_* flags describing the plan */
  u16 nEq;              /* Number of equality constraints */

** Each instance of this object holds a sequence of WhereLoop objects
** that implement some or all of the entire query plan.  
*/
struct WherePath {
  Bitmask maskLoop;     /* Bitmask of all WhereLoop objects in this path */
  double nRow;          /* Estimated number of rows generated by this path */
  double rCost;         /* Total cost of this path */
  WhereLoop **aLoop;    /* Array of WhereLoop objects implementing this path */


};

/*
** The query generator uses an array of instances of this structure to
** help it analyze the subexpressions of the WHERE clause.  Each WHERE
** clause subexpression is separated from the others by AND operators,
** usually, or sometimes subexpressions separated by OR.

** analysis only.
*/
char sqlite3_query_plan[BMS*2*40];  /* Text of the join */
static int nQPlan = 0;              /* Next free slow in _query_plan[] */

#endif /* SQLITE_TEST */

#if defined(SQLITE_DEBUG) \
    && (defined(SQLITE_TEST) || defined(SQLITE_ENABLE_WHERETRACE))
/*
** Print a WhereLoop object for debugging purposes
*/
static void whereLoopPrint(WhereLoop *p, SrcList *pTabList){
  int nb = 2*((pTabList->nSrc+15)/16);
  struct SrcList_item *pItem = pTabList->a + p->iTab;
  Table *pTab = pItem->pTab;
  sqlite3DebugPrintf("%02d.%0*llx", p->iTab, nb, p->prereq);
  sqlite3DebugPrintf(" %6s",
                     pItem->zAlias ? pItem->zAlias : pTab->zName);
  if( p->pIndex ){
    sqlite3DebugPrintf(".%-8s %2d", p->pIndex->zName, p->nEq);
  }else{
    sqlite3DebugPrintf("%12s","");
  }
  sqlite3DebugPrintf(" fg %08x OB %d,%d N %2d",
                     p->wsFlags, p->iOb, p->nOb, p->nTerm);
  sqlite3DebugPrintf(" cost %.4g,%.4g,%.4g\n",
                     p->prereq, p->rSetup, p->rRun, p->nOut);
}
#endif

/*
** Delete a WhereLoop object
*/
static void whereLoopDelete(sqlite3 *db, WhereLoop *p){
  sqlite3DbFree(db, p->aTerm);
  sqlite3DbFree(db, p);
}

** is better and has fewer dependencies.  Or the template will be ignored
** and no insert will occur if an existing WhereLoop is faster and has
** fewer dependencies than the template.  Otherwise a new WhereLoop is
** added based no the template.
*/
static int whereLoopInsert(WhereInfo *pWInfo, WhereLoop *pTemplate){
  WhereLoop **ppPrev, *p, *pNext = 0, *pToFree = 0;
  WhereTerm **paTerm = 0;
  sqlite3 *db = pWInfo->pParse->db;

  /* Search for an existing WhereLoop to overwrite, or which takes
  ** priority over pTemplate.
  */
  for(ppPrev=&pWInfo->pLoops, p=*ppPrev; p; ppPrev=&p->pNextLoop, p=*ppPrev){
    if( p->iTab!=pTemplate->iTab ) continue;

     && p->nOb<=pTemplate->nOb
     && p->iOb==pTemplate->iOb
     && p->rSetup>=pTemplate->rSetup
     && p->rRun>=pTemplate->rRun
    ){
      /* Overwrite an existing WhereLoop with a better one */
      sqlite3DbFree(db, p->aTerm);
      p->aTerm = 0;
      p->nTerm = 0;
      pNext = p->pNextLoop;
      break;
    }
  }

  /* If we reach this point it means that either p[] should be overwritten
  ** with pTemplate[] if p[] exists, or if p==NULL then allocate a new
  ** WhereLoop and insert it.
  */
  if( p==0 ){
    p = pToFree = sqlite3DbMallocRaw(db, sizeof(WhereLoop));
    if( p==0 ) return SQLITE_NOMEM;
  }
  if( pTemplate->nTerm ){
    paTerm = sqlite3DbMallocRaw(db, pTemplate->nTerm*sizeof(p->aTerm[0]));
    if( paTerm==0 ){
      sqlite3DbFree(db, pToFree);
      return SQLITE_NOMEM;
    }
  }
  *p = *pTemplate;
  p->pNextLoop = pNext;
  *ppPrev = p;
  p->aTerm = paTerm;
  if( p->pIndex && p->pIndex->tnum==0 ) p->pIndex = 0;
  if( pTemplate->nTerm ){
    memcpy(p->aTerm, pTemplate->aTerm, pTemplate->nTerm*sizeof(p->aTerm[0]));




  }

  return SQLITE_OK;
}

/*
** We have so far matched pBuilder->pNew->nEq terms of the index pIndex.
** Try to match one more.
**
** If pProbe->tnum==0, that means pIndex is a fake index used for the
** INTEGER PRIMARY KEY.
*/
static void whereLoopAddBtreeIndex(
  WhereLoopBuilder *pBuilder,     /* The WhereLoop factory */

  struct SrcList_item *pSrc,      /* FROM clause term being analyzed */
  Index *pProbe,                  /* An index on pSrc */
  int nInMul                      /* Number of iterations due to IN */
){
  sqlite3 *db;                    /* Database connection malloc context */
  WhereLoop *pNew;                /* Template WhereLoop under construction */
  WhereTerm *pTerm;               /* A WhereTerm under consideration */
  int opMask;                     /* Valid operators for constraints */
  WhereScan scan;                 /* Iterator for WHERE terms */
  WhereLoop savedLoop;            /* Saved original content of pNew[] */
  int iCol;                       /* Index of the column in the table */

  db = pBuilder->db;
  pNew = pBuilder->pNew;
  if( db->mallocFailed ) return;

  assert( pNew->nEq<pProbe->nColumn );
  assert( (pNew->wsFlags & WHERE_TOP_LIMIT)==0 );
  if( pNew->wsFlags & WHERE_BTM_LIMIT ){
    opMask = WO_LT|WO_LE;
  }else if( pProbe->tnum<=0 || (pSrc->jointype & JT_LEFT)!=0 ){
    opMask = WO_EQ|WO_IN|WO_GT|WO_GE|WO_LT|WO_LE;
  }else{
    opMask = WO_EQ|WO_IN|WO_ISNULL|WO_GT|WO_GE|WO_LT|WO_LE;
  }






  iCol = pProbe->aiColumn[pNew->nEq];
  pTerm = whereScanInit(&scan, pBuilder->pWC, pSrc->iCursor, iCol,
                        opMask, iCol>=0 ? pProbe : 0);
  savedLoop = *pNew;
  pNew->rSetup = (double)0;
  for(; pTerm!=0; pTerm = whereScanNext(&scan)){
    int nIn = 1;
    pNew->nEq = savedLoop.nEq;
    pNew->nTerm = savedLoop.nTerm;
    pNew->aTerm[pNew->nTerm++] = pTerm;
    pNew->prereq = (savedLoop.prereq | pTerm->prereqRight) & ~pNew->maskSelf;
    if( pTerm->eOperator & WO_IN ){
      Expr *pExpr = pTerm->pExpr;
      pNew->wsFlags |= WHERE_COLUMN_IN;
      if( ExprHasProperty(pExpr, EP_xIsSelect) ){
        /* "x IN (SELECT ...)":  Assume the SELECT returns 25 rows */
        nIn = 25;
      }else if( ALWAYS(pExpr->x.pList && pExpr->x.pList->nExpr) ){
        /* "x IN (value, value, ...)" */
        nIn = pExpr->x.pList->nExpr;
      }
      pNew->nEq++;
      pNew->nOut = (double)pProbe->aiRowEst[pNew->nEq] * nInMul * nIn;
    }else if( pTerm->eOperator & (WO_EQ|WO_ISNULL) ){
      pNew->wsFlags |= WHERE_COLUMN_EQ;
      pNew->nEq++;
      pNew->nOut = (double)pProbe->aiRowEst[pNew->nEq] * nInMul;
    }else if( pTerm->eOperator & (WO_GT|WO_GE) ){
      pNew->wsFlags |= WHERE_COLUMN_RANGE|WHERE_BTM_LIMIT;
      pNew->nOut = savedLoop.nOut/3;
    }else if( pTerm->eOperator & (WO_LT|WO_LE) ){
      pNew->wsFlags |= WHERE_COLUMN_RANGE|WHERE_TOP_LIMIT;
      pNew->nOut = savedLoop.nOut/3;
    }
    pNew->rRun = pNew->nOut + estLog(pProbe->aiRowEst[0])*nIn;
    whereLoopInsert(pBuilder->pWInfo, pNew);
    if( (pNew->wsFlags & WHERE_TOP_LIMIT)==0 && pNew->nEq<pProbe->nColumn ){
      whereLoopAddBtreeIndex(pBuilder, pSrc, pProbe, nInMul*nIn);
    }
  }
  *pNew = savedLoop;

}

/*
** Add all WhereLoop objects for the iTab-th table of the join.  That
** table is guaranteed to be a b-tree table, not a virtual table.
*/
static void whereLoopAddBtree(
  WhereLoopBuilder *pBuilder, /* WHERE clause information */
  int iTab,                   /* The table to process */
  Bitmask mExtra              /* Extra prerequesites for using this table */
){
  Index *pProbe;              /* An index we are evaluating */
  Index sPk;                  /* A fake index object for the primary key */
  tRowcnt aiRowEstPk[2];      /* The aiRowEst[] value for the sPk index */
  int aiColumnPk = -1;        /* The aColumn[] value for the sPk index */
  struct SrcList_item *pSrc;  /* The FROM clause btree term to add */
  sqlite3 *db;                /* The database connection */
  WhereLoop *pNew;            /* Template WhereLoop object */


  pNew = pBuilder->pNew;
  db = pBuilder->db;
  pSrc = pBuilder->pTabList->a + iTab;
  pNew->maskSelf = getMask(pBuilder->pWC->pMaskSet, iTab);

  if( pSrc->pIndex ){
    /* An INDEXED BY clause specifies a particular index to use */
    pProbe = pSrc->pIndex;
  }else{
    /* There is no INDEXED BY clause.  Create a fake Index object in local
    ** variable sPk to represent the rowid primary key index.  Make this

    }
    paTerm = sqlite3DbRealloc(db, pNew->aTerm,
                              (pProbe->nColumn+1)*sizeof(pNew->aTerm[0]));
    if( paTerm==0 ) break;
    pNew->aTerm = paTerm;
    pNew->pIndex = pProbe;

    whereLoopAddBtreeIndex(pBuilder, pSrc, pProbe, 1);

    /* If there was an INDEXED BY clause, then only that one index is
    ** considered. */
    if( pSrc->pIndex ) break;
  }
}

  Bitmask mExtra = 0;
  Bitmask mPrior = 0;
  int iTab;
  SrcList *pTabList = pBuilder->pTabList;
  struct SrcList_item *pItem;
  WhereClause *pWC = pBuilder->pWC;
  sqlite3 *db = pBuilder->db;
  int nTabList = pBuilder->pWInfo->nLevel;

  /* Loop over the tables in the join, from left to right */
  pBuilder->pNew = sqlite3DbMallocZero(db, sizeof(WhereLoop));
  if( pBuilder->pNew==0 ) return;
  for(iTab=0, pItem=pTabList->a; iTab<nTabList; iTab++, pItem++){
    if( IsVirtual(pItem->pTab) ){
      whereLoopAddVirtual(pBuilder, iTab, mExtra);
    }else{
      whereLoopAddBtree(pBuilder, iTab, mExtra);
    }
    mPrior |= getMask(pWC->pMaskSet, pItem->iCursor);
    if( (pItem->jointype & (JT_LEFT|JT_CROSS))!=0 ){
      mExtra = mPrior;
    }
    if( db->mallocFailed ) break;
  }
  whereLoopDelete(db, pBuilder->pNew);
  pBuilder->pNew = 0;
}

/*
** Given the list of WhereLoop objects on pWInfo->pLoops, this routine
** attempts to find the lowest cost path that visits each WhereLoop
** once.  This path is then loaded into the pWInfo->a[].pWLoop fields.
**
** Return SQLITE_OK on success or SQLITE_NOMEM of a memory allocation
** error occurs.
*/
static int wherePathSolver(WhereInfo *pWInfo){
  const int mxChoice = 10;  /* Maximum number of simultaneous paths tracked */
  int nLoop;                /* Number of terms in the join */
  sqlite3 *db;              /* The database connection */
  int iLoop;                /* Loop counter over the terms of the join */
  int ii, jj;               /* Loop counters */
  double rCost;             /* Cost of a path */
  double mxCost;            /* Maximum cost of a set of paths */
  int nTo, nFrom;           /* Number of valid entries in aTo[] and aFrom[] */
  WherePath *aFrom;         /* All nFrom paths at the previous level */
  WherePath *aTo;           /* The nTo best paths at the current level */
  WherePath *pFrom;         /* An element of aFrom[] that we are working on */
  WherePath *pTo;           /* An element of aTo[] that we are working on */
  WhereLoop *pWLoop;        /* One of the WhereLoop objects */
  WhereLoop **pX;           /* Used to divy up the pSpace memory */
  char *pSpace;             /* Temporary memory used by this routine */

  db = pWInfo->pParse->db;
  nLoop = pWInfo->nLevel;
  assert( nLoop<=pWInfo->pTabList->nSrc );

  /* Allocate and initialize space for aTo and aFrom */
  ii = (sizeof(WherePath)+sizeof(WhereLoop*)*nLoop)*mxChoice*2;
  pSpace = sqlite3DbMallocRaw(db, ii);
  if( pSpace==0 ) return SQLITE_NOMEM;
  aTo = (WherePath*)pSpace;
  aFrom = aTo+mxChoice;
  memset(aFrom, 0, sizeof(aFrom[0]));
  pX = (WhereLoop**)(aFrom+mxChoice);
  for(ii=0, pFrom=aTo; ii<mxChoice*2; ii++, pFrom++, pX += nLoop){
    pFrom->aLoop = pX;
  }

  nFrom = 1;
  for(iLoop=0; iLoop<nLoop; iLoop++){
    nTo = 0;
    for(ii=0, pFrom=aFrom; ii<nFrom; ii++, pFrom++){
      for(pWLoop=pWInfo->pLoops; pWLoop; pWLoop=pWLoop->pNextLoop){
        Bitmask maskNew;
        if( (pWLoop->prereq & ~pFrom->maskLoop)!=0 ) continue;
        if( (pWLoop->maskSelf & pFrom->maskLoop)!=0 ) continue;
        rCost = pWLoop->rSetup + pWLoop->rRun*pFrom->nRow + pFrom->rCost;
        maskNew = pFrom->maskLoop | pWLoop->maskSelf;
        for(jj=0, pTo=aTo; jj<nTo && pTo->maskLoop!=maskNew; jj++){}
        if( jj>=nTo ){
          if( nTo>=mxChoice && rCost>=mxCost ) continue;
          if( nTo<mxChoice ){
            jj = nTo++;
          }else{
            for(jj=nTo-1; aTo[jj].rCost>=mxCost; jj++){ assert(jj>0); }
          }
          pTo = &aTo[jj];
        }
        pTo->maskLoop = pFrom->maskLoop | pWLoop->maskSelf;
        pTo->nRow = pFrom->nRow * pWLoop->nOut;
        pTo->rCost = rCost;
        memcpy(pTo->aLoop, pFrom->aLoop, sizeof(WhereLoop*)*iLoop);
        pTo->aLoop[iLoop] = pWLoop;
        if( nTo>=mxChoice ){
          mxCost = aTo[0].rCost;
          for(jj=1, pTo=&aTo[1]; jj<mxChoice; jj++, pTo++){
            if( pTo->rCost>mxCost ) mxCost = pTo->rCost;
          }
        }
      }
    }

    /* Swap the roles of aFrom and aTo in preparation for the next
    ** cycle. */
    pFrom = aTo;
    aTo = aFrom;
    aFrom = pFrom;
    nFrom = nTo;
  }

  /* TEMPORARY */
  if( nFrom==0 ){ sqlite3DbFree(db, pSpace); return SQLITE_ERROR; }
  assert( nFrom>0 );
  
  /* Find the lowest cost path and load it into pWInfo->a[].pWLoop */
  pFrom = aFrom;
  for(ii=1; ii<nFrom; ii++){
    if( pFrom->rCost>aFrom[ii].rCost ) pFrom = &aFrom[ii];
  }
  assert( pWInfo->nLevel==nLoop );
  for(iLoop=0; iLoop<nLoop; iLoop++){
    pWInfo->a[iLoop].pWLoop = pFrom->aLoop[iLoop];
  }

  /* Free temporary memory and return success */
  sqlite3DbFree(db, pSpace);
  return SQLITE_OK;
}

/*
** Generate the beginning of the loop used for WHERE clause processing.
** The return value is a pointer to an opaque structure that contains
** information needed to terminate the loop.  Later, the calling routine
** should invoke sqlite3WhereEnd() with the return value of this function
** in order to complete the WHERE clause processing.

    pDistinct = 0;
    pWInfo->eDistinct = WHERE_DISTINCT_UNIQUE;
  }

  /* Construct the WhereLoop objects */
  WHERETRACE(("*** Optimizer Start ***\n"));
  whereLoopAddAll(&sWLB);
  if( db->mallocFailed ) goto whereBeginError;

  /* Display all of the WhereLoop objects if wheretrace is enabled */
#if defined(SQLITE_DEBUG) \
    && (defined(SQLITE_TEST) || defined(SQLITE_ENABLE_WHERETRACE))
  if( sqlite3WhereTrace ){
    WhereLoop *p;

    for(p=pWInfo->pLoops; p; p=p->pNextLoop){
      whereLoopPrint(p, pTabList);




    }
  }
#endif




  wherePathSolver(pWInfo);
  if( db->mallocFailed ) goto whereBeginError;
#if defined(SQLITE_DEBUG) \
    && (defined(SQLITE_TEST) || defined(SQLITE_ENABLE_WHERETRACE))
  if( sqlite3WhereTrace ){

    int ii;
    sqlite3DebugPrintf("------------ Solution ----------------\n");

    for(ii=0; ii<nTabList; ii++){
      whereLoopPrint(pWInfo->a[ii].pWLoop, pTabList);
    }
  }
#endif

  /* Chose the best index to use for each table in the FROM clause.
  **
  ** This loop fills in the following fields: