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 WHERE_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.

/*
** 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 */
  Bitmask revLoop;      /* aLoop[]s that should be reversed for ORDER BY */
  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 */
};

  Table *pTab = pItem->pTab;
  sqlite3DebugPrintf("%2d.%0*llx.%0*llx",
                     p->iTab, nb, p->maskSelf, nb, p->prereq);
  sqlite3DebugPrintf(" %8s",
                     pItem->zAlias ? pItem->zAlias : pTab->zName);
  if( (p->wsFlags & WHERE_VIRTUALTABLE)==0 ){
    if( p->u.btree.pIndex ){
      const char *zName = p->u.btree.pIndex->zName;
      if( strncmp(zName, "sqlite_autoindex_", 17)==0 ){
        int i = sqlite3Strlen30(zName) - 1;
        while( zName[i]!='_' ) i--;
        zName += i;
      }
      sqlite3DebugPrintf(".%-12s %2d", zName, p->u.btree.nEq);

    }else{
      sqlite3DebugPrintf("%16s","");
    }
  }else{
    char *z;
    if( p->u.vtab.idxStr ){
      z = sqlite3_mprintf("(%d,\"%s\")", p->u.vtab.idxNum,p->u.vtab.idxStr);

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

/*
** Examine a WherePath (with the addition of the extra WhereLoop of the 4th
** parameters) to see if it outputs rows in the requested ORDER BY
** (or GROUP BY) without requiring a separate source operation.  Return:
** 
**    0:  ORDER BY is not satisfied.  Sorting required
**    1:  ORDER BY is satisfied.      Omit sorting
**   -1:  Unknown at this time
**
*/
static int wherePathSatisfiesOrderBy(
  WhereInfo *pWInfo,    /* The WHERE clause */
  WherePath *pPath,     /* The WherePath to check */
  int nLoop,            /* Number of entries in pPath->aLoop[] */
  WhereLoop *pLast,     /* Add this WhereLoop to the end of pPath->aLoop[] */
  Bitmask *pRevMask     /* Mask of WhereLoops to run in reverse order */
){
  u8 revSet;
  u8 rev;
  u8 isUnique;
  u8 requireUnique = 0;
  u16 nColumn;
  u16 nOrderBy;
  int i, j;
  int nUsed = 0;
  int iCur;
  int iColumn;
  WhereLoop *pLoop;
  ExprList *pOrderBy = pWInfo->pOrderBy;
  Expr *pOBExpr;
  CollSeq *pColl;
  Index *pIndex;
  sqlite3 *db = pWInfo->pParse->db;
  Bitmask revMask = 0;

  /*
  ** We say the WhereLoop is "one-row" if all of the following are true:
  **  (a) All index columns match with WHERE_COLUMN_EQ.
  **  (b) The index is unique
  **
  ** General rules:  (not an algorithm!)
  **
  **  (1) If the current WhereLoop is one-row, then match over any and all
  **      ORDER BY terms for the current WhereLoop and proceed to the next
  **      WhereLoop.
  **
  **  (2) If the current WhereLoop is not one-row, then all subsequent
  **      WhereLoops must be one-row.
  **
  **  (3) Optionally match any ORDER BY terms against the first nEq columns
  **      of the index.
  **
  **  (4) Index columns past nEq must match ORDER BY terms one-for-one.
  */

  assert( pOrderBy!=0 );

  /* Sortability of virtual tables is determined by the xBestIndex method
  ** of the virtual table itself */
  if( pLast->wsFlags & WHERE_VIRTUALTABLE ){
    assert( nLoop==0 );
    return pLast->u.vtab.isOrdered;
  }

  /* Sorting is always required if any term of the ORDER BY is not a 
  ** column reference */
  nOrderBy = pOrderBy->nExpr;
  for(i=0; i<nOrderBy; i++){
    pOBExpr = sqlite3ExprSkipCollate(pOrderBy->a[nUsed].pExpr);
    if( pOBExpr->op!=TK_COLUMN ) return 0;
  }
    
  for(i=0; i<=nLoop && nUsed<nOrderBy; i++){
    pLoop = i<nLoop ? pPath->aLoop[i] : pLast;
    assert( (pLoop->wsFlags & WHERE_VIRTUALTABLE)==0 );
    isUnique = 1;
    if( pLoop->wsFlags & WHERE_IPK ){
      if( (pLoop->wsFlags & WHERE_COLUMN_EQ)!=0 ) isUnique = 0;
      pIndex = 0;
      nColumn = 1;
    }else if( pLoop->u.btree.pIndex==0 ){
      return 0;
    }else{

      pIndex = pLoop->u.btree.pIndex;
      nColumn = pIndex->nColumn;
      if( pIndex->onError==OE_None ){
        isUnique = 0;
      }else if( (pLoop->wsFlags & (WHERE_COLUMN_IN|WHERE_COLUMN_RANGE
                                   |WHERE_COLUMN_NULL))!=0 ){
        isUnique = 0;
      }else if( pLoop->u.btree.nEq < pIndex->nColumn ){
        isUnique = 0;
      }
    }
    if( !isUnique && requireUnique ) return 0;
    requireUnique = !isUnique;
    iCur = pWInfo->pTabList->a[pLoop->iTab].iCursor;
    j = 0;
    revSet = rev = 0;
    for(j=0; j<nColumn && nUsed<nOrderBy; j++, nUsed++){
      pOBExpr = sqlite3ExprSkipCollate(pOrderBy->a[nUsed].pExpr);
      assert( pOBExpr->op==TK_COLUMN );
      if( pOBExpr->iTable!=iCur ) break;
      if( pIndex==0 ){
        if( pOBExpr->iColumn<0 && j==0 ){
          isUnique = 1;
          rev = pOrderBy->a[nUsed].sortOrder;


        }else if( isUnique ){
          continue;
        }else{
          return 0;
        }
      }
      if( isUnique ) continue;
      iColumn = pIndex->aiColumn[j];
      if( iColumn==pIndex->pTable->iPKey ) iColumn = -1;
      if( pOBExpr->iColumn!=iColumn ) return 0;
      pColl = sqlite3ExprCollSeq(pWInfo->pParse, pOrderBy->a[nUsed].pExpr);
      if( !pColl ) pColl = db->pDfltColl;
      if( sqlite3StrICmp(pColl->zName, pIndex->azColl[j])!=0 ) return 0;
      if( revSet ){
        if( pIndex->aSortOrder[j]!=rev ) return 0;
      }else{
        rev = pIndex->aSortOrder[j];
        revSet = 1;
      }
    }
    if( rev ) revMask |= ((Bitmask)1)<<i;
  }
  if( nUsed==nOrderBy ){
    *pRevMask = revMask;
    return 1;
  }
  return -1;
}


/*
** 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.

  ** 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;
        Bitmask revMask = 0;
        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, &revMask) ){
            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;

          }
          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->revLoop = revMask;
        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 ){

  wherePathSolver(pWInfo);
  if( db->mallocFailed ) goto whereBeginError;
#if defined(SQLITE_DEBUG) \
    && (defined(SQLITE_TEST) || defined(SQLITE_ENABLE_WHERETRACE))
  if( sqlite3WhereTrace ){
    int ii;
    sqlite3DebugPrintf("------------ Solution -------------");
    if( pWInfo->nOBSat ){
      sqlite3DebugPrintf(" ORDER BY omitted\n");
    }else{
      sqlite3DebugPrintf("\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.