SQLite

#define WHERE_ORDERBY_MAX      0x0002 /* ORDER BY processing for max() func */
#define WHERE_ONEPASS_DESIRED  0x0004 /* Want to do one-pass UPDATE/DELETE */
#define WHERE_DUPLICATES_OK    0x0008 /* Ok to return a row more than once */
#define WHERE_OMIT_OPEN_CLOSE  0x0010 /* Table cursors are already open */
#define WHERE_FORCE_TABLE      0x0020 /* Do not use an index-only search */
#define WHERE_ONETABLE_ONLY    0x0040 /* Only code the 1st table in pTabList */
#define WHERE_AND_ONLY         0x0080 /* Don't use indices for OR terms */
#define WHREE_GROUPBY          0x0100 /* pOrderBy is really a GROUP BY */

/*
** The WHERE clause processing routine has two halves.  The
** first part does the start of the WHERE loop and the second
** half does the tail of the WHERE loop.  An instance of
** this structure is returned by the first half and passed
** into the second half to give some continuity.
*/
struct WhereInfo {
  Parse *pParse;            /* Parsing and code generating context */
  SrcList *pTabList;        /* List of tables in the join */
  ExprList *pOrderBy;       /* The ORDER BY clause or NULL */
  ExprList *pDistinct;      /* DISTINCT ON values, or NULL */
  u16 nOBSat;               /* Number of ORDER BY terms satisfied by indices */
  u16 wctrlFlags;           /* Flags originally passed to sqlite3WhereBegin() */
  u8 okOnePass;             /* Ok to use one-pass algorithm for UPDATE/DELETE */
  u8 untestedTerms;         /* Not all WHERE terms resolved by outer loop */
  u8 eDistinct;             /* One of the WHERE_DISTINCT_* values below */
  int iTop;                 /* The very beginning of the WHERE loop */
  int iContinue;            /* Jump here to continue with next record */

typedef struct WhereScan WhereScan;
typedef struct WhereVtabPlan WhereVtabPlan;


/*
** 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 (maskSelf,prereq,) 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 */
  u16 iTab;             /* Index of the table coded by this loop */
  u16 nTerm;            /* Number of entries in aTerm[] */
  u32 wsFlags;          /* WHERE_* flags describing the plan */
  double rSetup;        /* One-time setup cost (ex: create transient index) */
  double rRun;          /* Cost of running each loop */
  double nOut;          /* Estimated number of output rows */

  union {
    struct {               /* Information for internal btree tables */
      int nEq;               /* Number of equality constraints */
      Index *pIndex;         /* Index used, or NULL */
    } btree;
    struct {               /* Information for virtual tables */
      int idxNum;            /* Index number */
      u8 needFree;           /* True if sqlite3_free(idxStr) is needed */
      u8 isOrdered;          /* True if satisfies ORDER BY */
      char *idxStr;          /* Index identifier string */
    } vtab;
  } u;
  WhereTerm **aTerm;    /* WhereTerms used */
  WhereLoop *pNextLoop; /* Next WhereLoop object in the WhereClause */
};

/*
** 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 */
  u8 isOrdered;         /* True if this path satisfies ORDER BY */
  u8 isOrderedValid;    /* True if the isOrdered field is valid */
  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,

#define WO_ALL    0xfff       /* Mask of all possible WO_* values */
#define WO_SINGLE 0x0ff       /* Mask of all non-compound WO_* values */

/*
** Value for wsFlags returned by bestIndex() and stored in
** WhereLevel.wsFlags.  These flags determine which search
** strategies are appropriate.








*/
#define WHERE_ROWID_EQ     0x00000001  /* rowid=EXPR or rowid IN (...) */
#define WHERE_ROWID_RANGE  0x00000002  /* rowid<EXPR and/or rowid>EXPR */
#define WHERE_NULL_OK      0x00000004  /* Ok to use WO_ISNULL */
#define WHERE_IPK          0x00000008  /* x is the INTEGER PRIMARY KEY */
#define WHERE_COLUMN_EQ    0x00000010  /* x=EXPR or x IN (...) or x IS NULL */
#define WHERE_COLUMN_RANGE 0x00000020  /* x<EXPR and/or x>EXPR */
#define WHERE_COLUMN_IN    0x00000040  /* x IN (...) */
#define WHERE_COLUMN_NULL  0x00000080  /* x IS NULL */
#define WHERE_INDEXED      0x000000f0  /* Anything that uses an index */
#define WHERE_NOT_FULLSCAN 0x000200f3  /* Does not do a full table scan */
#define WHERE_IN_ABLE      0x000100f1  /* Able to support an IN operator */
#define WHERE_TOP_LIMIT    0x00000100  /* x<EXPR or x<=EXPR constraint */
#define WHERE_BTM_LIMIT    0x00000200  /* x>EXPR or x>=EXPR constraint */
#define WHERE_BOTH_LIMIT   0x00000300  /* Both x>EXPR and x<EXPR */
#define WHERE_IDX_ONLY     0x00000400  /* Use index only - omit table */
#define WHERE_ORDERED      0x00000800  /* Output will appear in correct order */
#define WHERE_REVERSE      0x00001000  /* Scan in reverse order */
#define WHERE_UNIQUE       0x00002000  /* Selects no more than one row */
#define WHERE_ALL_UNIQUE   0x00004000  /* This and all prior have one row */
#define WHERE_OB_UNIQUE    0x00008000  /* Values in ORDER BY columns are 
                                       ** different for every output row */
#define WHERE_VIRTUALTABLE 0x00010000  /* Use virtual-table processing */

#define WHERE_MULTI_OR     0x00020000  /* OR using multiple indices */
#define WHERE_TEMP_INDEX   0x00040000  /* Uses an ephemeral index */
#define WHERE_DISTINCT     0x00080000  /* Correct order for DISTINCT */
#define WHERE_COVER_SCAN   0x00100000  /* Full scan of a covering index */
#define WHERE_SINGLE_ROW   0x00200000  /* No more than one row guaranteed */

/*
** This module contains many separate subroutines that work together to
** find the best indices to use for accessing a particular table in a query.
** An instance of the following structure holds context information about the
** index search so that it can be more easily passed between the various
** routines.

    if( (pTerm->eOperator & WO_OR)!=0
     && ((pTerm->prereqAll & ~maskSrc) & p->notReady)==0
     && (pTerm->u.pOrInfo->indexable & maskSrc)!=0 
    ){
      WhereClause * const pOrWC = &pTerm->u.pOrInfo->wc;
      WhereTerm * const pOrWCEnd = &pOrWC->a[pOrWC->nTerm];
      WhereTerm *pOrTerm;

      double rTotal = 0;
      double nRow = 0;
      Bitmask used = 0;
      WhereBestIdx sBOI;

      sBOI = *p;
      sBOI.pOrderBy = 0;

      ** of pCost. */
      /*WHERETRACE(("... multi-index OR cost=%.9g nrow=%.9g\n", rTotal, nRow));*/
      if( rTotal<p->cost.rCost ){
        p->cost.rCost = rTotal;
        p->cost.used = used;
        p->cost.plan.nRow = nRow;
        p->cost.plan.nOBSat = p->i ? p->aLevel[p->i-1].plan.nOBSat : 0;
        p->cost.plan.wsFlags = WHERE_MULTI_OR;
        p->cost.plan.u.pTerm = pTerm;
      }
    }
  }
#endif /* SQLITE_OMIT_OR_OPTIMIZATION */
}

  testcase( pTable->nCol==BMS-2 );
  for(i=0; i<mxBitCol; i++){
    if( extraCols & (((Bitmask)1)<<i) ) nColumn++;
  }
  if( pSrc->colUsed & (((Bitmask)1)<<(BMS-1)) ){
    nColumn += pTable->nCol - BMS + 1;
  }
  pLevel->plan.wsFlags |= WHERE_COLUMN_EQ | WHERE_IDX_ONLY;

  /* Construct the Index object to describe this index */
  nByte = sizeof(Index);
  nByte += nColumn*sizeof(int);     /* Index.aiColumn */
  nByte += nColumn*sizeof(char*);   /* Index.azColl */
  nByte += nColumn;                 /* Index.aSortOrder */
  pIdx = sqlite3DbMallocZero(pParse->db, nByte);

  /*WHERETRACE(("   best index is %s cost=%.1f\n",
         p->cost.plan.u.pIdx ? p->cost.plan.u.pIdx->zName : "ipk",
         p->cost.rCost));*/
  
  bestOrClauseIndex(p);
  bestAutomaticIndex(p);
  if( eqTermMask & WO_ISNULL ) p->cost.plan.wsFlags |= WHERE_NULL_OK;
}

/*
** Find the query plan for accessing table pSrc->pTab. Write the
** best query plan and its cost into the WhereCost object supplied 
** as the last parameter. This function may calculate the cost of
** both real and virtual table scans.

  Index *pIdx;                  /* The index being used for this loop */
  int iCur = pLevel->iTabCur;   /* The cursor of the table */
  WhereTerm *pTerm;             /* A single constraint term */
  int j;                        /* Loop counter */
  int regBase;                  /* Base register */
  int nReg;                     /* Number of registers to allocate */
  char *zAff;                   /* Affinity string to return */
  int eqFlags;                  /* WO_EQ|WO_IN and maybe also WO_ISNULL */

  /* This module is only called on query plans that use an index. */
  assert( pLevel->plan.wsFlags & WHERE_INDEXED );
  pIdx = pLevel->plan.u.pIdx;

  /* Figure out how many memory cells we will need then allocate them.
  */
  regBase = pParse->nMem + 1;
  nReg = pLevel->plan.nEq + nExtraReg;
  pParse->nMem += nReg;

  zAff = sqlite3DbStrDup(pParse->db, sqlite3IndexAffinityStr(v, pIdx));
  if( !zAff ){
    pParse->db->mallocFailed = 1;
  }

  /* Evaluate the equality constraints
  */
  assert( pIdx->nColumn>=nEq );
  eqFlags = (pLevel->plan.wsFlags&WHERE_NULL_OK) ? (WO_EQ|WO_IN|WO_ISNULL)
                                                 : (WO_EQ|WO_IN);
  for(j=0; j<nEq; j++){
    int r1;
    int k = pIdx->aiColumn[j];
    pTerm = findTerm(pWC, iCur, k, notReady, eqFlags, pIdx);
    if( pTerm==0 ) break;
    /* The following true for indices with redundant columns. 
    ** Ex: CREATE INDEX i1 ON t1(a,b,a); SELECT * FROM t1 WHERE a=0 AND b=0; */
    testcase( (pTerm->wtFlags & TERM_CODED)!=0 );
    testcase( pTerm->wtFlags & TERM_VIRTUAL ); /* EV: R-30575-11662 */
    r1 = codeEqualityTerm(pParse, pTerm, pLevel, j, regBase+j);
    if( r1!=regBase+j ){

      z = sqlite3_mprintf("(%d,\"%s\")", p->u.vtab.idxNum,p->u.vtab.idxStr);
    }else{
      z = sqlite3_mprintf("(%d)", p->u.vtab.idxNum);
    }
    sqlite3DebugPrintf(" %-15s", z);
    sqlite3_free(z);
  }
  sqlite3DebugPrintf(" fg %08x N %2d", p->wsFlags, p->nTerm);

  sqlite3DebugPrintf(" cost %.4g,%.4g,%.4g\n",
                     p->prereq, p->rSetup, p->rRun, p->nOut);
}
#endif

/*
** Deallocate internal memory used by a WhereLoop object

  /* 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;
    if( (p->prereq & pTemplate->prereq)==p->prereq


     && p->rSetup<=pTemplate->rSetup
     && p->rRun<=pTemplate->rRun
    ){
      /* Already holding an equal or better WhereLoop.
      ** Return without changing or adding anything */
      return SQLITE_OK;
    }
    if( (p->prereq & pTemplate->prereq)==pTemplate->prereq


     && p->rSetup>=pTemplate->rSetup
     && p->rRun>=pTemplate->rRun
    ){
      /* Overwrite an existing WhereLoop with a better one */
      pNext = p->pNextLoop;
      whereLoopClear(db, p);
      break;

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

    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++){

    }
    if( i>=pIdxInfo->nConstraint ){
      pNew->nTerm = mxTerm+1;
      pNew->u.vtab.idxNum = pIdxInfo->idxNum;
      pNew->u.vtab.needFree = pIdxInfo->needToFreeIdxStr;
      pIdxInfo->needToFreeIdxStr = 0;
      pNew->u.vtab.idxStr = pIdxInfo->idxStr;


      pNew->u.vtab.isOrdered = (u8)(pIdxInfo->nOrderBy!=0);



      pNew->rSetup = (double)0;
      pNew->rRun = pIdxInfo->estimatedCost;
      pNew->nOut = (double)25;
      whereLoopInsert(pBuilder->pWInfo, pNew);
      if( pNew->u.vtab.needFree ){
        sqlite3_free(pNew->u.vtab.idxStr);
        pNew->u.vtab.needFree = 0;

    }
    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
** (or GROUP BY) without requiring a separate source operation.  Return 1
** if it does and 0 if it does not and -1 if we cannot tell.
*/
static int wherePathSatisfiesOrderBy(
  WhereInfo *pWInfo,    /* The WHERE clause */
  WherePath *pPath,     /* The WherePath to check */
  int nLoop,            /* Number of entries in pPath->aLoop[] */
  WhereLoop *pLoop      /* Add this WhereLoop to the end of pPath->aLoop[] */
){
  if( pLoop->wsFlags & WHERE_VIRTUALTABLE ){
    return nLoop==0 && pLoop->u.vtab.isOrdered;
  }else{
    /* TBD: Check to see if pFrom + pWLoop satisfies the ORDER BY.
    **  (1)  If yes:   set isOrderedValid and isOrdered to 1.
    **  (2)  If no:    set isOrderedValid to 1 and isOrdered to 0.
    **  (3)  unknown:  no-op */
    return 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 */
  double rSortCost;         /* Cost to do a sort */
  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 *pNext;         /* Next loop */
  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;
  }

  /* Seed the search with a single WherePath containing zero WhereLoops */
  aFrom[0].nRow = (double)1;
  nFrom = 1;

  /* Precompute the cost of sorting the final result set, if the caller
  ** to sqlite3WhereBegin() was concerned about sorting */
  rSortCost = (double)0;
  if( pWInfo->pOrderBy==0 ){
    aFrom[0].isOrderedValid = 1;
  }else{
    /* Compute an estimate on the cost to sort the entire result set */
    rSortCost = (double)1;
    for(pWLoop=pWInfo->pLoops; pWLoop; pWLoop=pNext){
      pNext = pWLoop->pNextLoop;
      rCost = pWLoop->nOut;
      while( pNext && pNext->iTab==pWLoop->iTab ){
        if( pNext->nOut<rCost ) rCost = pNext->nOut;
        pNext = pNext->pNextLoop;
      }
      rSortCost *= rCost;
    }
    rSortCost *= estLog(rSortCost);
  }

  /* Compute successively longer WherePaths using the previous generation
  ** of WherePaths as the basis for the next.  Keep track of the mxChoice
  ** best paths at each generation */
  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;
        u8 isOrderedValid = pFrom->isOrderedValid;
        u8 isOrdered = pFrom->isOrdered;
        if( (pWLoop->prereq & ~pFrom->maskLoop)!=0 ) continue;
        if( (pWLoop->maskSelf & pFrom->maskLoop)!=0 ) continue;
        /* At this point, pWLoop is a candidate to be the next loop. 
        ** Compute its cost */
        rCost = pWLoop->rSetup + pWLoop->rRun*pFrom->nRow + pFrom->rCost;
        maskNew = pFrom->maskLoop | pWLoop->maskSelf;
        if( !isOrderedValid ){
          switch( wherePathSatisfiesOrderBy(pWInfo, pFrom, iLoop, pWLoop) ){
            case 1:  /* Yes.  pFrom+pWLoop does satisfy the ORDER BY clause */
              isOrdered = 1;
              isOrderedValid = 1;
              break;
            case 0:  /* No.  pFrom+pWLoop will require a separate sort */
              isOrdered = 0;
              isOrderedValid = 1;
              rCost += rSortCost;
              break;
            default: /* Cannot tell yet.  Try again on the next iteration */
              break;
          }
        }
        /* Check to see if pWLoop should be added to the mxChoice best so far */
        for(jj=0, pTo=aTo; jj<nTo; jj++, pTo++){
          if( pTo->maskLoop==maskNew && pTo->isOrderedValid==isOrderedValid ){
            break;
          }
        }
        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];
        }else{
          if( pTo->rCost<=rCost ) continue;
        }
        /* pWLoop is a winner.  Add it to the set of best so far */
        pTo->maskLoop = pFrom->maskLoop | pWLoop->maskSelf;
        pTo->nRow = pFrom->nRow * pWLoop->nOut;
        pTo->rCost = rCost;
        pTo->isOrderedValid = isOrderedValid;
        pTo->isOrdered = isOrdered;
        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;
          }

        for(jj=0; jj<=iLoop; jj++){
          whereLoopPrint(aTo[ii].aLoop[jj], pWInfo->pTabList);
        }
      }
    }
#endif

    /* Swap the roles of aFrom and aTo for the next generation */

    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.  pFrom will be left pointing to that path */
  pFrom = aFrom;
  for(ii=1; ii<nFrom; ii++){
    if( pFrom->rCost>aFrom[ii].rCost ) pFrom = &aFrom[ii];
  }
  assert( pWInfo->nLevel==nLoop );
  /* Load the lowest cost path into pWInfo */
  for(iLoop=0; iLoop<nLoop; iLoop++){
    pWInfo->a[iLoop].pWLoop = pFrom->aLoop[iLoop];
  }
  if( pFrom->isOrdered ){
    pWInfo->nOBSat = pWInfo->pOrderBy->nExpr;
  }

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

/*

    sqlite3DbFree(db, pWInfo);
    pWInfo = 0;
    goto whereBeginError;
  }
  pWInfo->nLevel = nTabList;
  pWInfo->pParse = pParse;
  pWInfo->pTabList = pTabList;
  pWInfo->pOrderBy = pOrderBy;
  pWInfo->pDistinct = pDistinct;
  pWInfo->iBreak = sqlite3VdbeMakeLabel(v);
  pWInfo->pWC = sWBI.pWC = (WhereClause *)&((u8 *)pWInfo)[nByteWInfo];
  pWInfo->wctrlFlags = wctrlFlags;
  pWInfo->savedNQueryLoop = pParse->nQueryLoop;
  pMaskSet = (WhereMaskSet*)&sWBI.pWC[1];
  sWBI.aLevel = pWInfo->a;
  sWLB.pWInfo = pWInfo;