SQLite

/*
** 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 int 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 */
  int rc = SQLITE_OK;         /* Return code */

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

  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

      ** NOT INDEXED qualifier is omitted from the FROM clause */
      sPk.pNext = pFirst;
    }
    pProbe = &sPk;
  }

  /* Insert a full table scan */
  pNew->iTab = iTab;
  pNew->u.btree.nEq = 0;
  pNew->nTerm = 0;
  pNew->rSetup = (double)0;
  pNew->prereq = 0;
  pNew->u.btree.pIndex = 0;
  pNew->wsFlags = 0;
  pNew->rRun = (double)pSrc->pTab->nRowEst;
  pNew->nOut = (double)pSrc->pTab->nRowEst;
  rc = whereLoopInsert(pBuilder->pWInfo, pNew);



  /* Loop over all indices
  */
  for(; rc==SQLITE_OK && pProbe; pProbe=pProbe->pNext){
    WhereTerm **paTerm;
    pNew->prereq = mExtra;
    pNew->iTab = iTab;
    pNew->u.btree.nEq = 0;
    pNew->nTerm = 0;
    if( pProbe->tnum<=0 ){
      /* Integer primary key index */
      pNew->wsFlags = WHERE_IPK;
    }else{
      Bitmask m = pSrc->colUsed;
      int j;
      for(j=pProbe->nColumn-1; j>=0; j--){
        int x = pProbe->aiColumn[j];
        if( x<BMS-1 ){
          m &= ~(((Bitmask)1)<<x);
        }
      }
      pNew->wsFlags = m==0 ? WHERE_IDX_ONLY : 0;
    }
    paTerm = sqlite3DbRealloc(db, pNew->aTerm,
                              (pProbe->nColumn+2)*sizeof(pNew->aTerm[0]));
    if( paTerm==0 ){ rc = SQLITE_NOMEM; break; }
    pNew->aTerm = paTerm;
    pNew->u.btree.pIndex = pProbe;

    rc = whereLoopAddBtreeIndex(pBuilder, pSrc, pProbe, 1);

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

/*
** Add all WhereLoop objects for the iTab-th table of the join.  That
** table is guaranteed to be a virtual table.
*/
static int whereLoopAddVirtual(
  WhereLoopBuilder *pBuilder,  /* WHERE clause information */
  int iTab,                    /* The table to process */
  Bitmask mExtra               /* Extra prerequesites for using this table */
){
  Parse *pParse;               /* The parsing context */
  WhereClause *pWC;            /* The WHERE clause */
  struct SrcList_item *pSrc;   /* The FROM clause term to search */
  Table *pTab;
  sqlite3 *db;
  sqlite3_index_info *pIdxInfo;
  struct sqlite3_index_constraint *pIdxCons;
  struct sqlite3_index_constraint_usage *pUsage;
  WhereTerm *pTerm;
  int i, j;
  int iTerm, mxTerm;
  int seenIn = 0;              /* True if an IN operator is seen */
  int seenVar = 0;             /* True if a non-constant constraint is seen */
  int iPhase;                  /* 0: const w/o IN, 1: const, 2: no IN,  2: IN */
  WhereLoop *pNew;
  WhereTerm **paTerm;
  int rc = SQLITE_OK;

  pParse = pBuilder->pParse;
  db = pParse->db;
  pWC = pBuilder->pWC;

  pSrc = &pBuilder->pTabList->a[iTab];
  pTab = pSrc->pTab;
  pNew = pBuilder->pNew;
  pIdxInfo = allocateIndexInfo(pParse,pWC,pSrc,pBuilder->pOrderBy);
  if( pIdxInfo==0 ) return SQLITE_NOMEM;
  paTerm = sqlite3DbRealloc(db, pNew->aTerm,
                            (pIdxInfo->nConstraint+1)*sizeof(pNew->aTerm[0]));
  if( paTerm==0 ){
    sqlite3DbFree(db, pIdxInfo);
    return SQLITE_NOMEM;
  }
  pNew->aTerm = paTerm;
  pNew->prereq = 0;
  pNew->iTab = iTab;
  pNew->maskSelf = getMask(pBuilder->pWC->pMaskSet, pSrc->iCursor);
  pNew->rSetup = 0;
  pNew->wsFlags = WHERE_VIRTUALTABLE;
  pNew->nTerm = 0;
  pNew->u.vtab.needFree = 0;
  pUsage = pIdxInfo->aConstraintUsage;

  for(iPhase=0; iPhase<=2; iPhase++){

  int iTab;
  SrcList *pTabList = pBuilder->pTabList;
  struct SrcList_item *pItem;
  WhereClause *pWC = pBuilder->pWC;
  sqlite3 *db = pBuilder->db;
  int nTabList = pBuilder->pWInfo->nLevel;
  int rc = SQLITE_OK;


  /* Loop over the tables in the join, from left to right */
  pBuilder->pNew = sqlite3DbMallocZero(db, sizeof(WhereLoop));
  if( pBuilder->pNew==0 ) return SQLITE_NOMEM;
  for(iTab=0, pItem=pTabList->a; iTab<nTabList; iTab++, pItem++){

    if( IsVirtual(pItem->pTab) ){
      rc = whereLoopAddVirtual(pBuilder, iTab, mExtra);
    }else{
      rc = whereLoopAddBtree(pBuilder, iTab, mExtra);
    }


    mPrior |= getMask(pWC->pMaskSet, pItem->iCursor);
    if( (pItem->jointype & (JT_LEFT|JT_CROSS))!=0 ){
      mExtra = mPrior;
    }











    if( rc || db->mallocFailed ) break;
  }

  whereLoopDelete(db, pBuilder->pNew);
  pBuilder->pNew = 0;
  return rc;
}

/*
** Examine a WherePath to see if it outputs rows in the requested ORDER BY