SQLite

  int isLastLoop,       /* True if pLast is the inner-most loop */
  WhereLoop *pLast,     /* Add this WhereLoop to the end of pPath->aLoop[] */
  Bitmask *pRevMask     /* Mask of WhereLoops to run in reverse order */
){
  u8 revSet;            /* True if rev is known */
  u8 rev;               /* Composite sort order */
  u8 revIdx;            /* Index sort order */
  u8 isOrderDistinct;   /* All prior WhereLoops are order-distinct */
  u8 distinctColumns;   /* True if the loop has UNIQUE NOT NULL columns */
  u8 isMatch;           /* iColumn matches a term of the ORDER BY clause */
  u16 nColumn;          /* Number of columns in pIndex */
  u16 nOrderBy;         /* Number terms in the ORDER BY clause */
  int iLoop;            /* Index of WhereLoop in pPath being processed */
  int i, j;             /* Loop counters */
  int iCur;             /* Cursor number for current WhereLoop */
  int iColumn;          /* A column number within table iCur */
  WhereLoop *pLoop;     /* Current WhereLoop being processed. */
  ExprList *pOrderBy = pWInfo->pOrderBy;  /* the ORDER BY clause */
  WhereTerm *pTerm;     /* A single term of the WHERE clause */
  Expr *pOBExpr;        /* An expression from the ORDER BY clause */
  CollSeq *pColl;       /* COLLATE function from an ORDER BY clause term */
  Index *pIndex;        /* The index associated with pLoop */
  sqlite3 *db = pWInfo->pParse->db;  /* Database connection */
  Bitmask obSat = 0;    /* Mask of ORDER BY terms satisfied so far */
  Bitmask obDone;       /* Mask of all ORDER BY terms */
  Bitmask orderDistinctMask;  /* Mask of all well-ordered loops */
  WhereMaskSet *pMaskSet;     /* WhereMaskSet object for this where clause */
  

  /*
  ** We say the WhereLoop is "one-row" if it generates no more than one
  ** row of output.  A 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
  ** Any WhereLoop with an WHERE_COLUMN_EQ constraint on the rowid is one-row.
  ** Every one-row WhereLoop will have the WHERE_ONEROW bit set in wsFlags.
  **
  ** We say the WhereLoop is "order-distinct" if the set of columns from


  ** that WhereLoop that are in the ORDER BY clause are different for every
  ** row of the WhereLoop.  Every one-row WhereLoop is automatically
  ** order-distinct.   A WhereLoop that has no columns in the ORDER BY clause
  ** is not order-distinct. To be order-distinct is not quite the same as being
  ** UNIQUE since a UNIQUE column or index can have multiple rows that 
  ** are NULL and NULL values are equivalent for the purpose of order-distinct.
  ** To be order-distinct, the columns must be UNIQUE and NOT NULL.
  **
  ** The rowid for a table is always UNIQUE and NOT NULL so whenever the
  ** rowid appears in the ORDER BY clause, the corresponding WhereLoop is
  ** automatically order-distinct.
  */

  assert( pOrderBy!=0 );

  /* Sortability of virtual tables is determined by the xBestIndex method
  ** of the virtual table itself */
  if( pLast->wsFlags & WHERE_VIRTUALTABLE ){
    testcase( nLoop>0 );  /* True when outer loops are one-row and match 
                          ** no ORDER BY terms */
    return pLast->u.vtab.isOrdered;
  }
  if( nLoop && OptimizationDisabled(db, SQLITE_OrderByIdxJoin) ) return 0;

  nOrderBy = pOrderBy->nExpr;
  if( nOrderBy>BMS-1 ) return 0;  /* Cannot optimize overly large ORDER BYs */
  isOrderDistinct = 1;
  obDone = MASKBIT(nOrderBy)-1;
  orderDistinctMask = 0;
  pMaskSet = pWInfo->pWC->pMaskSet;
  for(iLoop=0; isOrderDistinct && obSat<obDone && iLoop<=nLoop; iLoop++){
    pLoop = iLoop<nLoop ? pPath->aLoop[iLoop] : pLast;
    assert( (pLoop->wsFlags & WHERE_VIRTUALTABLE)==0 );
    iCur = pWInfo->pTabList->a[pLoop->iTab].iCursor;
    if( (pLoop->wsFlags & WHERE_ONEROW)==0 ){
      if( pLoop->wsFlags & WHERE_IPK ){
        pIndex = 0;
        nColumn = 0;
      }else if( (pIndex = pLoop->u.btree.pIndex)==0 || pIndex->bUnordered ){
        return 0;
      }else{
        nColumn = pIndex->nColumn;
        isOrderDistinct = pIndex->onError!=OE_None;
      }

      /* For every term of the index that is constrained by == or IS NULL,
      ** mark off corresponding ORDER BY terms wherever they occur
      ** in the ORDER BY clause.
      */
      for(i=0; i<pLoop->u.btree.nEq; i++){
        pTerm = pLoop->aTerm[i];
        if( (pTerm->eOperator & (WO_EQ|WO_ISNULL))==0 ) continue;
        iColumn = pTerm->u.leftColumn;

        if( obSat==obDone ) return 1;
      }

      /* Loop through all columns of the index and deal with the ones
      ** that are not constrained by == or IN.
      */
      rev = revSet = 0;
      distinctColumns = 0;
      for(j=0; j<=nColumn; j++){
        u8 bOnce;   /* True to run the ORDER BY search loop */

        /* Skip over == and IS NULL terms */
        if( j<pLoop->u.btree.nEq
         && ((i = pLoop->aTerm[j]->eOperator) & (WO_EQ|WO_ISNULL))!=0
        ){
          if( i & WO_ISNULL ) isOrderDistinct = 0;
          continue;  
        }

        /* Get the column number in the table (iColumn) and sort order
        ** (revIdx) for the j-th column of the index.
        */
        if( j<nColumn ){
          /* Normal index columns */
          iColumn = pIndex->aiColumn[j];
          revIdx = pIndex->aSortOrder[j];
          if( iColumn==pIndex->pTable->iPKey ) iColumn = -1;
        }else{
          /* The ROWID column at the end */
          iColumn = -1;
          revIdx = 0;
        }

        /* An unconstrained column that might be NULL means that this
        ** WhereLoop is not well-ordered 
        */
        if( isOrderDistinct
         && iColumn>=0
         && j>=pLoop->u.btree.nEq
         && pIndex->pTable->aCol[iColumn].notNull==0
        ){
          isOrderDistinct = 0;
        }

        /* Find the ORDER BY term that corresponds to the j-th column
        ** of the index and and mark that ORDER BY term off 
        */
        bOnce = 1;
        isMatch = 0;
        for(i=0; bOnce && i<nOrderBy; i++){
          if( MASKBIT(i) & obSat ) continue;
          pOBExpr = sqlite3ExprSkipCollate(pOrderBy->a[i].pExpr);

          if( (pWInfo->wctrlFlags & WHERE_GROUPBY)==0 ) bOnce = 0;
          if( pOBExpr->op!=TK_COLUMN ) continue;
          if( pOBExpr->iTable!=iCur ) continue;
          if( pOBExpr->iColumn!=iColumn ) continue;
          if( iColumn>=0 ){
            pColl = sqlite3ExprCollSeq(pWInfo->pParse, pOrderBy->a[i].pExpr);
            if( !pColl ) pColl = db->pDfltColl;
            if( sqlite3StrICmp(pColl->zName, pIndex->azColl[j])!=0 ) continue;
          }
          isMatch = 1;
          break;
        }
        if( isMatch ){
          if( iColumn<0 ) distinctColumns = 1;
          obSat |= MASKBIT(i);
          if( (pWInfo->wctrlFlags & WHERE_GROUPBY)==0 ){
            /* Make sure the sort order is compatible in an ORDER BY clause.
            ** Sort order is irrelevant for a GROUP BY clause. */
            if( revSet ){
              if( (rev ^ revIdx)!=pOrderBy->a[i].sortOrder ) return 0;
            }else{
              rev = revIdx ^ pOrderBy->a[i].sortOrder;
              if( rev ) *pRevMask |= MASKBIT(iLoop);
              revSet = 1;
            }
          }
        }else{
          /* No match found */
          if( j==0 || j<nColumn ) isOrderDistinct = 0;


          break;
        }
      } /* end Loop over all index columns */
      if( distinctColumns ) isOrderDistinct = 1;
    } /* end-if not one-row */

    /* Mark off any other ORDER BY terms that reference pLoop */
    if( isOrderDistinct ){
      orderDistinctMask |= pLoop->maskSelf;
      for(i=0; i<nOrderBy; i++){
        Expr *p;
        if( MASKBIT(i) & obSat ) continue;
        p = pOrderBy->a[i].pExpr;
        if( (exprTableUsage(pMaskSet, p)&~orderDistinctMask)==0 ){
          obSat |= MASKBIT(i);
        }
      }
    }
  }
  if( obSat==obDone ) return 1;
  if( !isOrderDistinct ) return 0;
  if( isLastLoop ) return 1;
  return -1;
}

#ifdef WHERETRACE_ENABLED
/* For debugging use only: */
static const char *wherePathName(WherePath *pPath, int nLoop, WhereLoop *pLast){

  }
} {tA * tB * tC * tD *}
do_test where3-2.2 {
  queryplan {
    SELECT * FROM tA, tB, tC LEFT JOIN tD ON dpk=cx
     WHERE cpk=bx AND apk=bx
  }
} {tB * tA * tC * tD *}
do_test where3-2.3 {
  queryplan {
    SELECT * FROM tA, tB, tC LEFT JOIN tD ON dpk=cx
     WHERE cpk=bx AND apk=bx
  }
} {tB * tA * tC * tD *}
do_test where3-2.4 {
  queryplan {
    SELECT * FROM tA, tB, tC LEFT JOIN tD ON dpk=cx
     WHERE apk=cx AND bpk=ax
  }
} {tC * tA * tB * tD *}
do_test where3-2.5 {
  queryplan {
    SELECT * FROM tA, tB, tC LEFT JOIN tD ON dpk=cx
     WHERE cpk=ax AND bpk=cx
  }
} {tA * tC * tB * tD *}
do_test where3-2.6 {
  queryplan {
    SELECT * FROM tA, tB, tC LEFT JOIN tD ON dpk=cx
     WHERE bpk=cx AND apk=bx
  }
} {tC * tB * tA * tD *}
do_test where3-2.7 {
  queryplan {
    SELECT * FROM tA, tB, tC LEFT JOIN tD ON dpk=cx
     WHERE cpk=bx AND apk=cx
  }
} {tB * tC * tA * tD *}

# Ticket [13f033c865f878953]
# If the outer loop must be a full table scan, do not let ANALYZE trick
# the planner into use a table for the outer loop that might be indexable
# if held until an inner loop.
# 
do_execsql_test where3-3.0 {