Query planner enhancements to be more agressive about optimizing out ORDER BY

clauses - in particular the query planner now has the ability to omit ORDER BY
clauses that span multiple tables in a join.

FossilOrigin-Name: 1e874629d7cf568368b912b295bd3001147d0b52

7 files changed, 475 insertions, 357 deletions

diff --git a/src/delete.c b/src/delete.c
index 44e5995a6..f7f52865e 100644
--- a/src/delete.c
+++ b/src/delete.c
@@ -638,7 +638,9 @@ int sqlite3GenerateIndexKey(
   }
   if( doMakeRec ){
     const char *zAff;
-    if( pTab->pSelect || (pParse->db->flags & SQLITE_IdxRealAsInt)!=0 ){
+    if( pTab->pSelect
+     || OptimizationDisabled(pParse->db, SQLITE_IdxRealAsInt)
+    ){
       zAff = 0;
     }else{
       zAff = sqlite3IndexAffinityStr(v, pIdx);
diff --git a/src/expr.c b/src/expr.c
index 3d6373881..2d1fb38ed 100644
--- a/src/expr.c
+++ b/src/expr.c
@@ -2066,7 +2066,7 @@ void sqlite3ExprCacheStore(Parse *pParse, int iTab, int iCol, int iReg){
   ** for testing only - to verify that SQLite always gets the same answer
   ** with and without the column cache.
   */
-  if( pParse->db->flags & SQLITE_ColumnCache ) return;
+  if( OptimizationDisabled(pParse->db, SQLITE_ColumnCache) ) return;
 
   /* First replace any existing entry.
   **
@@ -3382,7 +3382,7 @@ static int evalConstExpr(Walker *pWalker, Expr *pExpr){
 void sqlite3ExprCodeConstants(Parse *pParse, Expr *pExpr){
   Walker w;
   if( pParse->cookieGoto ) return;
-  if( (pParse->db->flags & SQLITE_FactorOutConst)!=0 ) return;
+  if( OptimizationDisabled(pParse->db, SQLITE_FactorOutConst) ) return;
   w.xExprCallback = evalConstExpr;
   w.xSelectCallback = 0;
   w.pParse = pParse;
diff --git a/src/main.c b/src/main.c
index 66ef9fc4f..b2826c0c7 100644
--- a/src/main.c
+++ b/src/main.c
@@ -3019,8 +3019,7 @@ int sqlite3_test_control(int op, ...){
     */
     case SQLITE_TESTCTRL_OPTIMIZATIONS: {
       sqlite3 *db = va_arg(ap, sqlite3*);
-      int x = va_arg(ap,int);
-      db->flags = (x & SQLITE_OptMask) | (db->flags & ~SQLITE_OptMask);
+      db->dbOptFlags = (u16)(va_arg(ap, int) & 0xffff);
       break;
     }
 
diff --git a/src/select.c b/src/select.c
index 01fe27694..2da14d93e 100644
--- a/src/select.c
+++ b/src/select.c
@@ -2809,7 +2809,7 @@ static int flattenSubquery(
   */
   assert( p!=0 );
   assert( p->pPrior==0 );  /* Unable to flatten compound queries */
-  if( db->flags & SQLITE_QueryFlattener ) return 0;
+  if( OptimizationDisabled(db, SQLITE_QueryFlattener) ) return 0;
   pSrc = p->pSrc;
   assert( pSrc && iFrom>=0 && iFrom<pSrc->nSrc );
   pSubitem = &pSrc->a[iFrom];
@@ -4012,7 +4012,7 @@ int sqlite3Select(
   ** to disable this optimization for testing purposes.
   */
   if( sqlite3ExprListCompare(p->pGroupBy, pOrderBy)==0
-         && (db->flags & SQLITE_GroupByOrder)==0 ){
+         && OptimizationEnabled(db, SQLITE_GroupByOrder) ){
     pOrderBy = 0;
   }
 
@@ -4506,6 +4506,7 @@ int sqlite3Select(
           goto select_end;
         }
         updateAccumulator(pParse, &sAggInfo);
+        assert( pMinMax==0 || pMinMax->nExpr==1 );
         if( pWInfo->nOBSat>0 ){
           sqlite3VdbeAddOp2(v, OP_Goto, 0, pWInfo->iBreak);
           VdbeComment((v, "%s() by index",
diff --git a/src/sqliteInt.h b/src/sqliteInt.h
index 7b9894254..a03b7ac1e 100644
--- a/src/sqliteInt.h
+++ b/src/sqliteInt.h
@@ -827,6 +827,7 @@ struct sqlite3 {
   unsigned int openFlags;       /* Flags passed to sqlite3_vfs.xOpen() */
   int errCode;                  /* Most recent error code (SQLITE_*) */
   int errMask;                  /* & result codes with this before returning */
+  u8 dbOptFlags;                /* Flags to enable/disable optimizations */
   u8 autoCommit;                /* The auto-commit flag. */
   u8 temp_store;                /* 1: file 2: memory 0: default */
   u8 mallocFailed;              /* True if we have seen a malloc failure */
@@ -931,46 +932,58 @@ struct sqlite3 {
 /*
 ** Possible values for the sqlite3.flags.
 */
-#define SQLITE_VdbeTrace      0x00000100  /* True to trace VDBE execution */
-#define SQLITE_InternChanges  0x00000200  /* Uncommitted Hash table changes */
-#define SQLITE_FullColNames   0x00000400  /* Show full column names on SELECT */
-#define SQLITE_ShortColNames  0x00000800  /* Show short columns names */
-#define SQLITE_CountRows      0x00001000  /* Count rows changed by INSERT, */
+#define SQLITE_VdbeTrace      0x00000001  /* True to trace VDBE execution */
+#define SQLITE_InternChanges  0x00000002  /* Uncommitted Hash table changes */
+#define SQLITE_FullColNames   0x00000004  /* Show full column names on SELECT */
+#define SQLITE_ShortColNames  0x00000008  /* Show short columns names */
+#define SQLITE_CountRows      0x00000010  /* Count rows changed by INSERT, */
                                           /*   DELETE, or UPDATE and return */
                                           /*   the count using a callback. */
-#define SQLITE_NullCallback   0x00002000  /* Invoke the callback once if the */
+#define SQLITE_NullCallback   0x00000020  /* Invoke the callback once if the */
                                           /*   result set is empty */
-#define SQLITE_SqlTrace       0x00004000  /* Debug print SQL as it executes */
-#define SQLITE_VdbeListing    0x00008000  /* Debug listings of VDBE programs */
-#define SQLITE_WriteSchema    0x00010000  /* OK to update SQLITE_MASTER */
-                         /*   0x00020000  Unused */
-#define SQLITE_IgnoreChecks   0x00040000  /* Do not enforce check constraints */
-#define SQLITE_ReadUncommitted 0x0080000  /* For shared-cache mode */
-#define SQLITE_LegacyFileFmt  0x00100000  /* Create new databases in format 1 */
-#define SQLITE_FullFSync      0x00200000  /* Use full fsync on the backend */
-#define SQLITE_CkptFullFSync  0x00400000  /* Use full fsync for checkpoint */
-#define SQLITE_RecoveryMode   0x00800000  /* Ignore schema errors */
-#define SQLITE_ReverseOrder   0x01000000  /* Reverse unordered SELECTs */
-#define SQLITE_RecTriggers    0x02000000  /* Enable recursive triggers */
-#define SQLITE_ForeignKeys    0x04000000  /* Enforce foreign key constraints  */
-#define SQLITE_AutoIndex      0x08000000  /* Enable automatic indexes */
-#define SQLITE_PreferBuiltin  0x10000000  /* Preference to built-in funcs */
-#define SQLITE_LoadExtension  0x20000000  /* Enable load_extension */
-#define SQLITE_EnableTrigger  0x40000000  /* True to enable triggers */
-
-/*
-** Bits of the sqlite3.flags field that are used by the
-** sqlite3_test_control(SQLITE_TESTCTRL_OPTIMIZATIONS,...) interface.
-** These must be the low-order bits of the flags field.
-*/
-#define SQLITE_QueryFlattener 0x01   /* Disable query flattening */
-#define SQLITE_ColumnCache    0x02   /* Disable the column cache */
-#define SQLITE_GroupByOrder   0x04   /* Disable GROUPBY cover of ORDERBY */
-#define SQLITE_FactorOutConst 0x08   /* Disable factoring out constants */
-#define SQLITE_IdxRealAsInt   0x10   /* Store REAL as INT in indices */
-#define SQLITE_DistinctOpt    0x20   /* DISTINCT using indexes */
-#define SQLITE_CoverIdxScan   0x40   /* Disable covering index scans */
-#define SQLITE_OptMask        0xff   /* Mask of all disablable opts */
+#define SQLITE_SqlTrace       0x00000040  /* Debug print SQL as it executes */
+#define SQLITE_VdbeListing    0x00000080  /* Debug listings of VDBE programs */
+#define SQLITE_WriteSchema    0x00000100  /* OK to update SQLITE_MASTER */
+                         /*   0x00000200  Unused */
+#define SQLITE_IgnoreChecks   0x00000400  /* Do not enforce check constraints */
+#define SQLITE_ReadUncommitted 0x0000800  /* For shared-cache mode */
+#define SQLITE_LegacyFileFmt  0x00001000  /* Create new databases in format 1 */
+#define SQLITE_FullFSync      0x00002000  /* Use full fsync on the backend */
+#define SQLITE_CkptFullFSync  0x00004000  /* Use full fsync for checkpoint */
+#define SQLITE_RecoveryMode   0x00008000  /* Ignore schema errors */
+#define SQLITE_ReverseOrder   0x00010000  /* Reverse unordered SELECTs */
+#define SQLITE_RecTriggers    0x00020000  /* Enable recursive triggers */
+#define SQLITE_ForeignKeys    0x00040000  /* Enforce foreign key constraints  */
+#define SQLITE_AutoIndex      0x00080000  /* Enable automatic indexes */
+#define SQLITE_PreferBuiltin  0x00100000  /* Preference to built-in funcs */
+#define SQLITE_LoadExtension  0x00200000  /* Enable load_extension */
+#define SQLITE_EnableTrigger  0x00400000  /* True to enable triggers */
+
+/*
+** Bits of the sqlite3.dbOptFlags field that are used by the
+** sqlite3_test_control(SQLITE_TESTCTRL_OPTIMIZATIONS,...) interface to
+** selectively disable various optimizations.
+*/
+#define SQLITE_QueryFlattener 0x0001   /* Query flattening */
+#define SQLITE_ColumnCache    0x0002   /* Column cache */
+#define SQLITE_GroupByOrder   0x0004   /* GROUPBY cover of ORDERBY */
+#define SQLITE_FactorOutConst 0x0008   /* Constant factoring */
+#define SQLITE_IdxRealAsInt   0x0010   /* Store REAL as INT in indices */
+#define SQLITE_DistinctOpt    0x0020   /* DISTINCT using indexes */
+#define SQLITE_CoverIdxScan   0x0040   /* Covering index scans */
+#define SQLITE_OrderByIdxJoin 0x0080   /* ORDER BY of joins via index */
+#define SQLITE_AllOpts        0x00ff   /* All optimizations */
+
+/*
+** Macros for testing whether or not optimizations are enabled or disabled.
+*/
+#ifndef SQLITE_OMIT_BUILTIN_TEST
+#define OptimizationDisabled(db, mask)  (((db)->dbOptFlags&(mask))!=0)
+#define OptimizationEnabled(db, mask)   (((db)->dbOptFlags&(mask))==0)
+#else
+#define OptimizationDisabled(db, mask)  0
+#define OptimizationEnabled(db, mask)   1
+#endif
 
 /*
 ** Possible values for the sqlite.magic field.
@@ -1906,7 +1919,8 @@ struct SrcList {
 */
 struct WherePlan {
   u32 wsFlags;                   /* WHERE_* flags that describe the strategy */
-  u32 nEq;                       /* Number of == constraints */
+  u16 nEq;                       /* Number of == constraints */
+  u16 nOBSat;                    /* Number of ORDER BY terms satisfied */
   double nRow;                   /* Estimated number of rows (for EQP) */
   union {
     Index *pIdx;                   /* Index when WHERE_INDEXED is true */
diff --git a/src/test1.c b/src/test1.c
index 0b9b812e8..3d2fb0203 100644
--- a/src/test1.c
+++ b/src/test1.c
@@ -5933,7 +5933,7 @@ static int optimization_control(
     const char *zOptName;
     int mask;
   } aOpt[] = {
-    { "all",              SQLITE_OptMask        },
+    { "all",              SQLITE_AllOpts        },
     { "query-flattener",  SQLITE_QueryFlattener },
     { "column-cache",     SQLITE_ColumnCache    },
     { "groupby-order",    SQLITE_GroupByOrder   },
@@ -5941,6 +5941,7 @@ static int optimization_control(
     { "real-as-int",      SQLITE_IdxRealAsInt   },
     { "distinct-opt",     SQLITE_DistinctOpt    },
     { "cover-idx-scan",   SQLITE_CoverIdxScan   },
+    { "order-by-idx-join",SQLITE_OrderByIdxJoin },
   };
 
   if( objc!=4 ){
diff --git a/src/where.c b/src/where.c
index 85fb1ed4f..7f386289c 100644
--- a/src/where.c
+++ b/src/where.c
@@ -268,6 +268,28 @@ struct WhereCost {
 #define WHERE_COVER_SCAN   0x80000000  /* Full scan of a covering index */
 
 /*
+** 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.
+*/
+typedef struct WhereBestIdx WhereBestIdx;
+struct WhereBestIdx {
+  Parse *pParse;                  /* Parser context */
+  WhereClause *pWC;               /* The WHERE clause */
+  struct SrcList_item *pSrc;      /* The FROM clause term to search */
+  Bitmask notReady;               /* Mask of cursors not available */
+  Bitmask notValid;               /* Cursors not available for any purpose */
+  ExprList *pOrderBy;             /* The ORDER BY clause */
+  ExprList *pDistinct;            /* The select-list if query is DISTINCT */
+  sqlite3_index_info **ppIdxInfo; /* Index information passed to xBestIndex */
+  int i, n;                       /* Which loop is being coded; # of loops */
+  WhereLevel *aLevel;             /* Info about outer loops */
+  WhereCost cost;                 /* Lowest cost query plan */
+};
+
+/*
 ** Initialize a preallocated WhereClause structure.
 */
 static void whereClauseInit(
@@ -1409,22 +1431,18 @@ static void exprAnalyze(
 }
 
 /*
-** Return TRUE if any of the expressions in pList->a[iFirst...] contain
-** a reference to any table other than the iBase table.
+** Return TRUE if the given index is UNIQUE and all columns past the
+** first nSkip columns are NOT NULL.
 */
-static int referencesOtherTables(
-  ExprList *pList,          /* Search expressions in ths list */
-  WhereMaskSet *pMaskSet,   /* Mapping from tables to bitmaps */
-  int iFirst,               /* Be searching with the iFirst-th expression */
-  int iBase                 /* Ignore references to this table */
-){
-  Bitmask allowed = ~getMask(pMaskSet, iBase);
-  while( iFirst<pList->nExpr ){
-    if( (exprTableUsage(pMaskSet, pList->a[iFirst++].pExpr)&allowed)!=0 ){
-      return 1;
-    }
+static int indexIsUniqueNotNull(Index *pIdx, int nSkip){
+  Table *pTab = pIdx->pTable;
+  int i;
+  if( pIdx->onError==OE_None ) return 0;
+  for(i=nSkip; i<pIdx->nColumn; i++){
+    int j = pIdx->aiColumn[i];
+    if( j>=0 && pTab->aCol[j].notNull==0 ) return 0;
   }
-  return 0;
+  return 1;
 }
 
 /*
@@ -1590,43 +1608,59 @@ static int isDistinctRedundant(
 
 /*
 ** This routine decides if pIdx can be used to satisfy the ORDER BY
-** clause.  If it can, it returns 1.  If pIdx cannot satisfy the
-** ORDER BY clause, this routine returns 0.
+** clause, either in whole or in part.  The return value is the 
+** cumulative number of terms in the ORDER BY clause that are satisfied
+** by the index pIdx and other indices in outer loops.
 **
-** pOrderBy is an ORDER BY clause from a SELECT statement.  pTab is the
-** left-most table in the FROM clause of that same SELECT statement and
-** the table has a cursor number of "base".  pIdx is an index on pTab.
+** The table being queried has a cursor number of "base".  pIdx is the
+** index that is postulated for use to access the table.
 **
 ** nEqCol is the number of columns of pIdx that are used as equality
-** constraints.  Any of these columns may be missing from the ORDER BY
-** clause and the match can still be a success.
-**
-** All terms of the ORDER BY that match against the index must be either
-** ASC or DESC.  (Terms of the ORDER BY clause past the end of a UNIQUE
-** index do not need to satisfy this constraint.)  The *pbRev value is
-** set to 1 if the ORDER BY clause is all DESC and it is set to 0 if
-** the ORDER BY clause is all ASC.
+** constraints and where the other side of the == is an ordered column
+** or constant.  An "order column" in the previous sentence means a column
+** in table from an outer loop whose values will always appear in the 
+** correct order due to othre index, or because the outer loop generates
+** a unique result.  Any of the first nEqCol columns of pIdx may be missing
+** from the ORDER BY clause and the match can still be a success.
+**
+** The *pbRev value is set to 0 order 1 depending on whether or not
+** pIdx should be run in the forward order or in reverse order.
 */
 static int isSortingIndex(
-  Parse *pParse,          /* Parsing context */
-  WhereMaskSet *pMaskSet, /* Mapping from table cursor numbers to bitmaps */
-  Index *pIdx,            /* The index we are testing */
-  int base,               /* Cursor number for the table to be sorted */
-  ExprList *pOrderBy,     /* The ORDER BY clause */
-  int nEqCol,             /* Number of index columns with == constraints */
-  int wsFlags,            /* Index usages flags */
-  int *pbRev              /* Set to 1 if ORDER BY is DESC */
+  WhereBestIdx *p,    /* Best index search context */
+  Index *pIdx,        /* The index we are testing */
+  int base,           /* Cursor number for the table to be sorted */
+  int nEqCol,         /* Number of index columns with ordered == constraints */
+  int wsFlags,        /* Index usages flags */
+  int bOuterRev,      /* True if outer loops scan in reverse order */
+  int *pbRev          /* Set to 1 for reverse-order scan of pIdx */
 ){
-  int i, j;                       /* Loop counters */
-  int sortOrder = 0;              /* XOR of index and ORDER BY sort direction */
-  int nTerm;                      /* Number of ORDER BY terms */
-  struct ExprList_item *pTerm;    /* A term of the ORDER BY clause */
-  sqlite3 *db = pParse->db;
-
-  if( !pOrderBy ) return 0;
-  if( wsFlags & WHERE_COLUMN_IN ) return 0;
-  if( pIdx->bUnordered ) return 0;
-
+  int i;                        /* Number of pIdx terms used */
+  int j;                        /* Number of ORDER BY terms satisfied */
+  int sortOrder = 0;            /* XOR of index and ORDER BY sort direction */
+  int nTerm;                    /* Number of ORDER BY terms */
+  struct ExprList_item *pTerm;  /* A term of the ORDER BY clause */
+  ExprList *pOrderBy;           /* The ORDER BY clause */
+  Parse *pParse = p->pParse;    /* Parser context */
+  sqlite3 *db = pParse->db;     /* Database connection */
+  int nPriorSat;                /* ORDER BY terms satisfied by outer loops */
+  int seenRowid = 0;            /* True if an ORDER BY rowid term is seen */
+  int nEqOneRow;                /* Idx columns that ref unique values */
+
+  if( p->i==0 ){
+    nPriorSat = 0;
+    nEqOneRow = nEqCol;
+  }else{
+    if( OptimizationDisabled(db, SQLITE_OrderByIdxJoin) ) return 0;
+    nPriorSat = p->aLevel[p->i-1].plan.nOBSat;
+    sortOrder = bOuterRev;
+    nEqOneRow = 0;
+  }
+  if( p->i>0 && nEqCol==0 /*&& !allOuterLoopsUnique(p)*/ ) return nPriorSat;
+  pOrderBy = p->pOrderBy;
+  if( !pOrderBy ) return nPriorSat;
+  if( wsFlags & WHERE_COLUMN_IN ) return nPriorSat;
+  if( pIdx->bUnordered ) return nPriorSat;
   nTerm = pOrderBy->nExpr;
   assert( nTerm>0 );
 
@@ -1643,7 +1677,7 @@ static int isSortingIndex(
   ** of the index is also allowed to match against the ORDER BY
   ** clause.
   */
-  for(i=j=0, pTerm=pOrderBy->a; j<nTerm && i<=pIdx->nColumn; i++){
+  for(i=0,j=nPriorSat,pTerm=&pOrderBy->a[j]; j<nTerm && i<=pIdx->nColumn; i++){
     Expr *pExpr;       /* The expression of the ORDER BY pTerm */
     CollSeq *pColl;    /* The collating sequence of pExpr */
     int termSortOrder; /* Sort order for this term */
@@ -1687,64 +1721,49 @@ static int isSortingIndex(
         /* If an index column fails to match and is not constrained by ==
         ** then the index cannot satisfy the ORDER BY constraint.
         */
-        return 0;
+        return nPriorSat;
       }
     }
     assert( pIdx->aSortOrder!=0 || iColumn==-1 );
     assert( pTerm->sortOrder==0 || pTerm->sortOrder==1 );
     assert( iSortOrder==0 || iSortOrder==1 );
     termSortOrder = iSortOrder ^ pTerm->sortOrder;
-    if( i>nEqCol ){
+    if( i>nEqOneRow ){
       if( termSortOrder!=sortOrder ){
         /* Indices can only be used if all ORDER BY terms past the
         ** equality constraints are all either DESC or ASC. */
-        return 0;
+        break;
       }
     }else{
       sortOrder = termSortOrder;
     }
     j++;
     pTerm++;
-    if( iColumn<0 && !referencesOtherTables(pOrderBy, pMaskSet, j, base) ){
-      /* If the indexed column is the primary key and everything matches
-      ** so far and none of the ORDER BY terms to the right reference other
-      ** tables in the join, then we are assured that the index can be used 
-      ** to sort because the primary key is unique and so none of the other
-      ** columns will make any difference
-      */
-      j = nTerm;
+    if( iColumn<0 ){
+      seenRowid = 1;
+      break;
     }
   }
+  *pbRev = sortOrder;
 
-  *pbRev = sortOrder!=0;
-  if( j>=nTerm ){
-    /* All terms of the ORDER BY clause are covered by this index so
-    ** this index can be used for sorting. */
-    return 1;
-  }
-  if( pIdx->onError!=OE_None && i==pIdx->nColumn
-      && (wsFlags & WHERE_COLUMN_NULL)==0
-      && !referencesOtherTables(pOrderBy, pMaskSet, j, base) 
+  /* If there was an "ORDER BY rowid" term that matched, or it is only
+  ** possible for a single row from this table to match, then skip over
+  ** any additional ORDER BY terms dealing with this table.
+  */
+  if( seenRowid ||
+     (   (wsFlags & WHERE_COLUMN_NULL)==0
+      && i>=pIdx->nColumn
+      && indexIsUniqueNotNull(pIdx, nEqCol)
+     )
   ){
-    Column *aCol = pIdx->pTable->aCol;
-
-    /* All terms of this index match some prefix of the ORDER BY clause,
-    ** the index is UNIQUE, and no terms on the tail of the ORDER BY
-    ** refer to other tables in a join. So, assuming that the index entries
-    ** visited contain no NULL values, then this index delivers rows in
-    ** the required order.
-    **
-    ** It is not possible for any of the first nEqCol index fields to be
-    ** NULL (since the corresponding "=" operator in the WHERE clause would 
-    ** not be true). So if all remaining index columns have NOT NULL 
-    ** constaints attached to them, we can be confident that the visited
-    ** index entries are free of NULLs.  */
-    for(i=nEqCol; i<pIdx->nColumn; i++){
-      if( aCol[pIdx->aiColumn[i]].notNull==0 ) break;
+    /* Advance j over additional ORDER BY terms associated with base */
+    WhereMaskSet *pMS = p->pWC->pMaskSet;
+    Bitmask m = ~getMask(pMS, base);
+    while( j<nTerm && (exprTableUsage(pMS, pOrderBy->a[j].pExpr)&m)==0 ){
+      j++;
     }
-    return (i==pIdx->nColumn);
   }
-  return 0;
+  return j;
 }
 
 /*
@@ -1811,9 +1830,7 @@ static void TRACE_IDX_OUTPUTS(sqlite3_index_info *p){
 /* 
 ** Required because bestIndex() is called by bestOrClauseIndex() 
 */
-static void bestIndex(
-    Parse*, WhereClause*, struct SrcList_item*,
-    Bitmask, Bitmask, WhereCost*);
+static void bestIndex(WhereBestIdx*);
 
 /*
 ** This routine attempts to find an scanning strategy that can be used 
@@ -1822,20 +1839,14 @@ static void bestIndex(
 ** The table associated with FROM clause term pSrc may be either a
 ** regular B-Tree table or a virtual table.
 */
-static void bestOrClauseIndex(
-  Parse *pParse,              /* The parsing context */
-  WhereClause *pWC,           /* The WHERE clause */
-  struct SrcList_item *pSrc,  /* The FROM clause term to search */
-  Bitmask notReady,           /* Mask of cursors not available for indexing */
-  Bitmask notValid,           /* Cursors not available for any purpose */
-  ExprList *pOrderBy,         /* The ORDER BY clause */
-  WhereCost *pCost            /* Lowest cost query plan */
-){
+static void bestOrClauseIndex(WhereBestIdx *p){
 #ifndef SQLITE_OMIT_OR_OPTIMIZATION
-  const int iCur = pSrc->iCursor;   /* The cursor of the table to be accessed */
+  WhereClause *pWC = p->pWC;           /* The WHERE clause */
+  struct SrcList_item *pSrc = p->pSrc; /* The FROM clause term to search */
+  const int iCur = pSrc->iCursor;      /* The cursor of the table  */
   const Bitmask maskSrc = getMask(pWC->pMaskSet, iCur);  /* Bitmask for pSrc */
   WhereTerm * const pWCEnd = &pWC->a[pWC->nTerm];        /* End of pWC->a[] */
-  WhereTerm *pTerm;                 /* A single term of the WHERE clause */
+  WhereTerm *pTerm;                    /* A single term of the WHERE clause */
 
   /* The OR-clause optimization is disallowed if the INDEXED BY or
   ** NOT INDEXED clauses are used or if the WHERE_AND_ONLY bit is set. */
@@ -1849,7 +1860,7 @@ static void bestOrClauseIndex(
   /* Search the WHERE clause terms for a usable WO_OR term. */
   for(pTerm=pWC->a; pTerm<pWCEnd; pTerm++){
     if( pTerm->eOperator==WO_OR 
-     && ((pTerm->prereqAll & ~maskSrc) & notReady)==0
+     && ((pTerm->prereqAll & ~maskSrc) & p->notReady)==0
      && (pTerm->u.pOrInfo->indexable & maskSrc)!=0 
     ){
       WhereClause * const pOrWC = &pTerm->u.pOrInfo->wc;
@@ -1859,15 +1870,19 @@ static void bestOrClauseIndex(
       double rTotal = 0;
       double nRow = 0;
       Bitmask used = 0;
+      WhereBestIdx sBOI;
 
+      sBOI = *p;
+      sBOI.pOrderBy = 0;
+      sBOI.pDistinct = 0;
+      sBOI.ppIdxInfo = 0;
       for(pOrTerm=pOrWC->a; pOrTerm<pOrWCEnd; pOrTerm++){
-        WhereCost sTermCost;
         WHERETRACE(("... Multi-index OR testing for term %d of %d....\n", 
           (pOrTerm - pOrWC->a), (pTerm - pWC->a)
         ));
         if( pOrTerm->eOperator==WO_AND ){
-          WhereClause *pAndWC = &pOrTerm->u.pAndInfo->wc;
-          bestIndex(pParse, pAndWC, pSrc, notReady, notValid, &sTermCost);
+          sBOI.pWC = &pOrTerm->u.pAndInfo->wc;
+          bestIndex(&sBOI);
         }else if( pOrTerm->leftCursor==iCur ){
           WhereClause tempWC;
           tempWC.pParse = pWC->pParse;
@@ -1877,19 +1892,20 @@ static void bestOrClauseIndex(
           tempWC.a = pOrTerm;
           tempWC.wctrlFlags = 0;
           tempWC.nTerm = 1;
-          bestIndex(pParse, &tempWC, pSrc, notReady, notValid, &sTermCost);
+          sBOI.pWC = &tempWC;
+          bestIndex(&sBOI);
         }else{
           continue;
         }
-        rTotal += sTermCost.rCost;
-        nRow += sTermCost.plan.nRow;
-        used |= sTermCost.used;
-        if( rTotal>=pCost->rCost ) break;
+        rTotal += sBOI.cost.rCost;
+        nRow += sBOI.cost.plan.nRow;
+        used |= sBOI.cost.used;
+        if( rTotal>=p->cost.rCost ) break;
       }
 
       /* If there is an ORDER BY clause, increase the scan cost to account 
       ** for the cost of the sort. */
-      if( pOrderBy!=0 ){
+      if( p->pOrderBy!=0 ){
         WHERETRACE(("... sorting increases OR cost %.9g to %.9g\n",
                     rTotal, rTotal+nRow*estLog(nRow)));
         rTotal += nRow*estLog(nRow);
@@ -1899,12 +1915,12 @@ static void bestOrClauseIndex(
       ** less than the current cost stored in pCost, replace the contents
       ** of pCost. */
       WHERETRACE(("... multi-index OR cost=%.9g nrow=%.9g\n", rTotal, nRow));
-      if( rTotal<pCost->rCost ){
-        pCost->rCost = rTotal;
-        pCost->used = used;
-        pCost->plan.nRow = nRow;
-        pCost->plan.wsFlags = flags;
-        pCost->plan.u.pTerm = pTerm;
+      if( rTotal<p->cost.rCost ){
+        p->cost.rCost = rTotal;
+        p->cost.used = used;
+        p->cost.plan.nRow = nRow;
+        p->cost.plan.wsFlags = flags;
+        p->cost.plan.u.pTerm = pTerm;
       }
     }
   }
@@ -1941,15 +1957,12 @@ static int termCanDriveIndex(
 ** is taken into account, then alter the query plan to use the
 ** transient index.
 */
-static void bestAutomaticIndex(
-  Parse *pParse,              /* The parsing context */
-  WhereClause *pWC,           /* The WHERE clause */
-  struct SrcList_item *pSrc,  /* The FROM clause term to search */
-  Bitmask notReady,           /* Mask of cursors that are not available */
-  WhereCost *pCost            /* Lowest cost query plan */
-){
-  double nTableRow;           /* Rows in the input table */
-  double logN;                /* log(nTableRow) */
+static void bestAutomaticIndex(WhereBestIdx *p){
+  Parse *pParse = p->pParse;            /* The parsing context */
+  WhereClause *pWC = p->pWC;            /* The WHERE clause */
+  struct SrcList_item *pSrc = p->pSrc;  /* The FROM clause term to search */
+  double nTableRow;                     /* Rows in the input table */
+  double logN;                          /* log(nTableRow) */
   double costTempIdx;         /* per-query cost of the transient index */
   WhereTerm *pTerm;           /* A single term of the WHERE clause */
   WhereTerm *pWCEnd;          /* End of pWC->a[] */
@@ -1963,7 +1976,7 @@ static void bestAutomaticIndex(
     /* Automatic indices are disabled at run-time */
     return;
   }
-  if( (pCost->plan.wsFlags & WHERE_NOT_FULLSCAN)!=0 ){
+  if( (p->cost.plan.wsFlags & WHERE_NOT_FULLSCAN)!=0 ){
     /* We already have some kind of index in use for this query. */
     return;
   }
@@ -1981,7 +1994,7 @@ static void bestAutomaticIndex(
   nTableRow = pTable->nRowEst;
   logN = estLog(nTableRow);
   costTempIdx = 2*logN*(nTableRow/pParse->nQueryLoop + 1);
-  if( costTempIdx>=pCost->rCost ){
+  if( costTempIdx>=p->cost.rCost ){
     /* The cost of creating the transient table would be greater than
     ** doing the full table scan */
     return;
@@ -1990,19 +2003,19 @@ static void bestAutomaticIndex(
   /* Search for any equality comparison term */
   pWCEnd = &pWC->a[pWC->nTerm];
   for(pTerm=pWC->a; pTerm<pWCEnd; pTerm++){
-    if( termCanDriveIndex(pTerm, pSrc, notReady) ){
+    if( termCanDriveIndex(pTerm, pSrc, p->notReady) ){
       WHERETRACE(("auto-index reduces cost from %.1f to %.1f\n",
-                    pCost->rCost, costTempIdx));
-      pCost->rCost = costTempIdx;
-      pCost->plan.nRow = logN + 1;
-      pCost->plan.wsFlags = WHERE_TEMP_INDEX;
-      pCost->used = pTerm->prereqRight;
+                    p->cost.rCost, costTempIdx));
+      p->cost.rCost = costTempIdx;
+      p->cost.plan.nRow = logN + 1;
+      p->cost.plan.wsFlags = WHERE_TEMP_INDEX;
+      p->cost.used = pTerm->prereqRight;
       break;
     }
   }
 }
 #else
-# define bestAutomaticIndex(A,B,C,D,E)  /* no-op */
+# define bestAutomaticIndex(A)  /* no-op */
 #endif /* SQLITE_OMIT_AUTOMATIC_INDEX */
 
 
@@ -2163,12 +2176,11 @@ static void constructAutomaticIndex(
 ** responsibility of the caller to eventually release the structure
 ** by passing the pointer returned by this function to sqlite3_free().
 */
-static sqlite3_index_info *allocateIndexInfo(
-  Parse *pParse, 
-  WhereClause *pWC,
-  struct SrcList_item *pSrc,
-  ExprList *pOrderBy
-){
+static sqlite3_index_info *allocateIndexInfo(WhereBestIdx *p){
+  Parse *pParse = p->pParse; 
+  WhereClause *pWC = p->pWC;
+  struct SrcList_item *pSrc = p->pSrc;
+  ExprList *pOrderBy = p->pOrderBy;
   int i, j;
   int nTerm;
   struct sqlite3_index_constraint *pIdxCons;
@@ -2198,12 +2210,13 @@ static sqlite3_index_info *allocateIndexInfo(
   */
   nOrderBy = 0;
   if( pOrderBy ){
-    for(i=0; i<pOrderBy->nExpr; i++){
+    int n = pOrderBy->nExpr;
+    for(i=0; i<n; i++){
       Expr *pExpr = pOrderBy->a[i].pExpr;
       if( pExpr->op!=TK_COLUMN || pExpr->iTable!=pSrc->iCursor ) break;
     }
-    if( i==pOrderBy->nExpr ){
-      nOrderBy = pOrderBy->nExpr;
+    if( i==n){
+      nOrderBy = n;
     }
   }
 
@@ -2327,16 +2340,10 @@ static int vtabBestIndex(Parse *pParse, Table *pTab, sqlite3_index_info *p){
 ** routine takes care of freeing the sqlite3_index_info structure after
 ** everybody has finished with it.
 */
-static void bestVirtualIndex(
-  Parse *pParse,                  /* The parsing context */
-  WhereClause *pWC,               /* The WHERE clause */
-  struct SrcList_item *pSrc,      /* The FROM clause term to search */
-  Bitmask notReady,               /* Mask of cursors not available for index */
-  Bitmask notValid,               /* Cursors not valid for any purpose */
-  ExprList *pOrderBy,             /* The order by clause */
-  WhereCost *pCost,               /* Lowest cost query plan */
-  sqlite3_index_info **ppIdxInfo  /* Index information passed to xBestIndex */
-){
+static void bestVirtualIndex(WhereBestIdx *p){
+  Parse *pParse = p->pParse;      /* The parsing context */
+  WhereClause *pWC = p->pWC;      /* The WHERE clause */
+  struct SrcList_item *pSrc = p->pSrc; /* The FROM clause term to search */
   Table *pTab = pSrc->pTab;
   sqlite3_index_info *pIdxInfo;
   struct sqlite3_index_constraint *pIdxCons;
@@ -2350,15 +2357,15 @@ static void bestVirtualIndex(
   ** malloc in allocateIndexInfo() fails and this function returns leaving
   ** wsFlags in an uninitialized state, the caller may behave unpredictably.
   */
-  memset(pCost, 0, sizeof(*pCost));
-  pCost->plan.wsFlags = WHERE_VIRTUALTABLE;
+  memset(&p->cost, 0, sizeof(p->cost));
+  p->cost.plan.wsFlags = WHERE_VIRTUALTABLE;
 
   /* If the sqlite3_index_info structure has not been previously
   ** allocated and initialized, then allocate and initialize it now.
   */
-  pIdxInfo = *ppIdxInfo;
+  pIdxInfo = *p->ppIdxInfo;
   if( pIdxInfo==0 ){
-    *ppIdxInfo = pIdxInfo = allocateIndexInfo(pParse, pWC, pSrc, pOrderBy);
+    *p->ppIdxInfo = pIdxInfo = allocateIndexInfo(p);
   }
   if( pIdxInfo==0 ){
     return;
@@ -2403,7 +2410,7 @@ static void bestVirtualIndex(
   for(i=0; i<pIdxInfo->nConstraint; i++, pIdxCons++){
     j = pIdxCons->iTermOffset;
     pTerm = &pWC->a[j];
-    pIdxCons->usable = (pTerm->prereqRight&notReady) ? 0 : 1;
+    pIdxCons->usable = (pTerm->prereqRight&p->notReady) ? 0 : 1;
   }
   memset(pUsage, 0, sizeof(pUsage[0])*pIdxInfo->nConstraint);
   if( pIdxInfo->needToFreeIdxStr ){
@@ -2416,7 +2423,7 @@ static void bestVirtualIndex(
   /* ((double)2) In case of SQLITE_OMIT_FLOATING_POINT... */
   pIdxInfo->estimatedCost = SQLITE_BIG_DBL / ((double)2);
   nOrderBy = pIdxInfo->nOrderBy;
-  if( !pOrderBy ){
+  if( !p->pOrderBy ){
     pIdxInfo->nOrderBy = 0;
   }
 
@@ -2427,7 +2434,7 @@ static void bestVirtualIndex(
   pIdxCons = *(struct sqlite3_index_constraint**)&pIdxInfo->aConstraint;
   for(i=0; i<pIdxInfo->nConstraint; i++){
     if( pUsage[i].argvIndex>0 ){
-      pCost->used |= pWC->a[pIdxCons[i].iTermOffset].prereqRight;
+      p->cost.used |= pWC->a[pIdxCons[i].iTermOffset].prereqRight;
     }
   }
 
@@ -2436,7 +2443,7 @@ static void bestVirtualIndex(
   ** matches the processing for non-virtual tables in bestBtreeIndex().
   */
   rCost = pIdxInfo->estimatedCost;
-  if( pOrderBy && pIdxInfo->orderByConsumed==0 ){
+  if( p->pOrderBy && pIdxInfo->orderByConsumed==0 ){
     rCost += estLog(rCost)*rCost;
   }
 
@@ -2448,21 +2455,21 @@ static void bestVirtualIndex(
   ** is defined.
   */
   if( (SQLITE_BIG_DBL/((double)2))<rCost ){
-    pCost->rCost = (SQLITE_BIG_DBL/((double)2));
+    p->cost.rCost = (SQLITE_BIG_DBL/((double)2));
   }else{
-    pCost->rCost = rCost;
+    p->cost.rCost = rCost;
   }
-  pCost->plan.u.pVtabIdx = pIdxInfo;
+  p->cost.plan.u.pVtabIdx = pIdxInfo;
   if( pIdxInfo->orderByConsumed ){
-    pCost->plan.wsFlags |= WHERE_ORDERBY;
+    p->cost.plan.wsFlags |= WHERE_ORDERBY;
   }
-  pCost->plan.nEq = 0;
+  p->cost.plan.nEq = 0;
   pIdxInfo->nOrderBy = nOrderBy;
 
   /* Try to find a more efficient access pattern by using multiple indexes
   ** to optimize an OR expression within the WHERE clause. 
   */
-  bestOrClauseIndex(pParse, pWC, pSrc, notReady, notValid, pOrderBy, pCost);
+  bestOrClauseIndex(p);
 }
 #endif /* SQLITE_OMIT_VIRTUALTABLE */
 
@@ -2861,11 +2868,84 @@ static int whereInScanEst(
 }
 #endif /* defined(SQLITE_ENABLE_STAT3) */
 
+/*
+** Check to see if column iCol of the table with cursor iTab will appear
+** in sorted order according to the current query plan.  Return true if
+** it will and false if not.  
+**
+** If *pbRev is initially 2 (meaning "unknown") then set *pbRev to the
+** sort order of iTab.iCol.  If *pbRev is 0 or 1 but does not match
+** the sort order of iTab.iCol, then consider the column to be unordered.
+*/
+static int isOrderedColumn(WhereBestIdx *p, int iTab, int iCol, int *pbRev){
+  int i, j;
+  WhereLevel *pLevel = &p->aLevel[p->i-1];
+  Index *pIdx;
+  u8 sortOrder;
+  for(i=p->i-1; i>=0; i--, pLevel--){
+    if( pLevel->iTabCur!=iTab ) continue;
+    if( (pLevel->plan.wsFlags & WHERE_INDEXED)!=0 ){
+      pIdx = pLevel->plan.u.pIdx;
+      if( iCol<0 ){
+        sortOrder = 0;
+        testcase( (pLevel->plan.wsFlags & WHERE_REVERSE)!=0 );
+      }else{
+        for(j=0; j<pIdx->nColumn; j++){
+          if( iCol==pIdx->aiColumn[j] ) break;
+        }
+        if( j>=pIdx->nColumn ) return 0;
+        sortOrder = pIdx->aSortOrder[j];
+        testcase( (pLevel->plan.wsFlags & WHERE_REVERSE)!=0 );
+      }
+    }else{
+      if( iCol!=(-1) ) return 0;
+      sortOrder = 0;
+      testcase( (pLevel->plan.wsFlags & WHERE_REVERSE)!=0 );
+    }
+    if( (pLevel->plan.wsFlags & WHERE_REVERSE)!=0 ){
+      assert( sortOrder==0 || sortOrder==1 );
+      testcase( sortOrder==1 );
+      sortOrder = 1 - sortOrder;
+    }
+    if( *pbRev==2 ){
+      *pbRev = sortOrder;
+      return 1;
+    }
+    return (*pbRev==sortOrder);
+  }
+  return 0;
+}
+
+/*
+** pTerm is an == constraint.  Check to see if the other side of
+** the == is a constant or a value that is guaranteed to be ordered
+** by outer loops.  Return 1 if pTerm is ordered, and 0 if not.
+*/
+static int isOrderedTerm(WhereBestIdx *p, WhereTerm *pTerm, int *pbRev){
+  Expr *pExpr = pTerm->pExpr;
+  assert( pExpr->op==TK_EQ );
+  assert( pExpr->pLeft!=0 && pExpr->pLeft->op==TK_COLUMN );
+  assert( pExpr->pRight!=0 );
+  if( p->i==0 ){
+    return 1;  /* All == are ordered in the outer loop */
+  }
+  if( pTerm->prereqRight==0 ){
+    return 1;  /* RHS of the == is a constant */
+  }
+  if( pExpr->pRight->op==TK_COLUMN 
+   && isOrderedColumn(p, pExpr->pRight->iTable, pExpr->pRight->iColumn, pbRev)
+  ){
+    return 1;
+  }
+
+  /* If we cannot prove that the constraint is ordered, assume it is not */
+  return 0;
+}
+
 
 /*
 ** Find the best query plan for accessing a particular table.  Write the
-** best query plan and its cost into the WhereCost object supplied as the
-** last parameter.
+** best query plan and its cost into the p->cost.
 **
 ** The lowest cost plan wins.  The cost is an estimate of the amount of
 ** CPU and disk I/O needed to process the requested result.
@@ -2890,16 +2970,10 @@ static int whereInScanEst(
 ** selected plan may still take advantage of the built-in rowid primary key
 ** index.
 */
-static void bestBtreeIndex(
-  Parse *pParse,              /* The parsing context */
-  WhereClause *pWC,           /* The WHERE clause */
-  struct SrcList_item *pSrc,  /* The FROM clause term to search */
-  Bitmask notReady,           /* Mask of cursors not available for indexing */
-  Bitmask notValid,           /* Cursors not available for any purpose */
-  ExprList *pOrderBy,         /* The ORDER BY clause */
-  ExprList *pDistinct,        /* The select-list if query is DISTINCT */
-  WhereCost *pCost            /* Lowest cost query plan */
-){
+static void bestBtreeIndex(WhereBestIdx *p){
+  Parse *pParse = p->pParse;  /* The parsing context */
+  WhereClause *pWC = p->pWC;  /* The WHERE clause */
+  struct SrcList_item *pSrc = p->pSrc; /* The FROM clause term to search */
   int iCur = pSrc->iCursor;   /* The cursor of the table to be accessed */
   Index *pProbe;              /* An index we are evaluating */
   Index *pIdx;                /* Copy of pProbe, or zero for IPK index */
@@ -2908,11 +2982,11 @@ static void bestBtreeIndex(
   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 */
-  int wsFlagMask;             /* Allowed flags in pCost->plan.wsFlag */
+  int wsFlagMask;             /* Allowed flags in p->cost.plan.wsFlag */
 
   /* Initialize the cost to a worst-case value */
-  memset(pCost, 0, sizeof(*pCost));
-  pCost->rCost = SQLITE_BIG_DBL;
+  memset(&p->cost, 0, sizeof(p->cost));
+  p->cost.rCost = SQLITE_BIG_DBL;
 
   /* If the pSrc table is the right table of a LEFT JOIN then we may not
   ** use an index to satisfy IS NULL constraints on that table.  This is
@@ -2965,7 +3039,7 @@ static void bestBtreeIndex(
     double cost;                /* Cost of using pProbe */
     double nRow;                /* Estimated number of rows in result set */
     double log10N = (double)1;  /* base-10 logarithm of nRow (inexact) */
-    int rev;                    /* True to scan in reverse order */
+    int bRev = 2;               /* 0=forward scan.  1=reverse.  2=undecided */
     int wsFlags = 0;
     Bitmask used = 0;
 
@@ -2998,6 +3072,10 @@ static void bestBtreeIndex(
     **    the sub-select is assumed to return 25 rows for the purposes of 
     **    determining nInMul.
     **
+    **  nOrdered:
+    **    The number of equality terms that are constrainted by outer loop
+    **    variables that are well-ordered.
+    **
     **  bInEst:  
     **    Set to true if there was at least one "x IN (SELECT ...)" term used 
     **    in determining the value of nInMul.  Note that the RHS of the
@@ -3016,6 +3094,10 @@ static void bestBtreeIndex(
     **    external sort (i.e. scanning the index being evaluated will not 
     **    correctly order records).
     **
+    **  bDistinct:
+    **    Boolean. True if there is a DISTINCT clause that will require an 
+    **    external btree.
+    **
     **  bLookup: 
     **    Boolean. True if a table lookup is required for each index entry
     **    visited.  In other words, true if this is not a covering index.
@@ -3032,22 +3114,29 @@ static void bestBtreeIndex(
     **             SELECT a, b, c FROM tbl WHERE a = 1;
     */
     int nEq;                      /* Number of == or IN terms matching index */
+    int nOrdered;                 /* Number of ordered terms matching index */
     int bInEst = 0;               /* True if "x IN (SELECT...)" seen */
     int nInMul = 1;               /* Number of distinct equalities to lookup */
     double rangeDiv = (double)1;  /* Estimated reduction in search space */
     int nBound = 0;               /* Number of range constraints seen */
-    int bSort = !!pOrderBy;       /* True if external sort required */
-    int bDist = !!pDistinct;      /* True if index cannot help with DISTINCT */
+    int bSort;                    /* True if external sort required */
+    int bDist;                    /* True if index cannot help with DISTINCT */
     int bLookup = 0;              /* True if not a covering index */
+    int nOBSat = 0;               /* Number of ORDER BY terms satisfied */
+    int nOrderBy;                 /* Number of ORDER BY terms */
     WhereTerm *pTerm;             /* A single term of the WHERE clause */
 #ifdef SQLITE_ENABLE_STAT3
     WhereTerm *pFirstTerm = 0;    /* First term matching the index */
 #endif
 
+    nOrderBy = p->pOrderBy ? p->pOrderBy->nExpr : 0;
+    bSort = nOrderBy>0 && (p->i==0 || p->aLevel[p->i-1].plan.nOBSat<nOrderBy);
+    bDist = p->i==0 && p->pDistinct!=0;
+
     /* Determine the values of nEq and nInMul */
-    for(nEq=0; nEq<pProbe->nColumn; nEq++){
+    for(nEq=nOrdered=0; nEq<pProbe->nColumn; nEq++){
       int j = pProbe->aiColumn[nEq];
-      pTerm = findTerm(pWC, iCur, j, notReady, eqTermMask, pIdx);
+      pTerm = findTerm(pWC, iCur, j, p->notReady, eqTermMask, pIdx);
       if( pTerm==0 ) break;
       wsFlags |= (WHERE_COLUMN_EQ|WHERE_ROWID_EQ);
       testcase( pTerm->pWC!=pWC );
@@ -3064,6 +3153,9 @@ static void bestBtreeIndex(
         }
       }else if( pTerm->eOperator & WO_ISNULL ){
         wsFlags |= WHERE_COLUMN_NULL;
+        if( nEq==nOrdered ) nOrdered++;
+      }else if( bSort && nEq==nOrdered && isOrderedTerm(p, pTerm, &bRev) ){
+        nOrdered++;
       }
 #ifdef SQLITE_ENABLE_STAT3
       if( nEq==0 && pProbe->aSample ) pFirstTerm = pTerm;
@@ -3088,9 +3180,10 @@ static void bestBtreeIndex(
       }
     }else if( pProbe->bUnordered==0 ){
       int j = (nEq==pProbe->nColumn ? -1 : pProbe->aiColumn[nEq]);
-      if( findTerm(pWC, iCur, j, notReady, WO_LT|WO_LE|WO_GT|WO_GE, pIdx) ){
-        WhereTerm *pTop = findTerm(pWC, iCur, j, notReady, WO_LT|WO_LE, pIdx);
-        WhereTerm *pBtm = findTerm(pWC, iCur, j, notReady, WO_GT|WO_GE, pIdx);
+      if( findTerm(pWC, iCur, j, p->notReady, WO_LT|WO_LE|WO_GT|WO_GE, pIdx) ){
+        WhereTerm *pTop, *pBtm;
+        pTop = findTerm(pWC, iCur, j, p->notReady, WO_LT|WO_LE, pIdx);
+        pBtm = findTerm(pWC, iCur, j, p->notReady, WO_GT|WO_GE, pIdx);
         whereRangeScanEst(pParse, pProbe, nEq, pBtm, pTop, &rangeDiv);
         if( pTop ){
           nBound = 1;
@@ -3112,18 +3205,25 @@ static void bestBtreeIndex(
     ** naturally scan rows in the required order, set the appropriate flags
     ** in wsFlags. Otherwise, if there is an ORDER BY clause but the index
     ** will scan rows in a different order, set the bSort variable.  */
-    if( isSortingIndex(
-          pParse, pWC->pMaskSet, pProbe, iCur, pOrderBy, nEq, wsFlags, &rev)
-    ){
-      bSort = 0;
-      wsFlags |= WHERE_ROWID_RANGE|WHERE_COLUMN_RANGE|WHERE_ORDERBY;
-      wsFlags |= (rev ? WHERE_REVERSE : 0);
+    assert( bRev>=0 && bRev<=2 );
+    if( bSort ){
+      testcase( bRev==0 );
+      testcase( bRev==1 );
+      testcase( bRev==2 );
+      nOBSat = isSortingIndex(p, pProbe, iCur, nOrdered,
+                              wsFlags, bRev&1, &bRev);
+      if( nOrderBy==nOBSat ){
+        bSort = 0;
+        wsFlags |= WHERE_ROWID_RANGE|WHERE_COLUMN_RANGE|WHERE_ORDERBY;
+      }
+      if( bRev & 1 ) wsFlags |= WHERE_REVERSE;
     }
 
     /* If there is a DISTINCT qualifier and this index will scan rows in
     ** order of the DISTINCT expressions, clear bDist and set the appropriate
     ** flags in wsFlags. */
-    if( isDistinctIndex(pParse, pWC, pProbe, iCur, pDistinct, nEq)
+    if( bDist
+     && isDistinctIndex(pParse, pWC, pProbe, iCur, p->pDistinct, nEq)
      && (wsFlags & WHERE_COLUMN_IN)==0
     ){
       bDist = 0;
@@ -3200,12 +3300,10 @@ static void bestBtreeIndex(
     ** So this computation assumes table records are about twice as big
     ** as index records
     */
-    if( wsFlags==WHERE_IDX_ONLY
+    if( (wsFlags&~WHERE_REVERSE)==WHERE_IDX_ONLY
      && (pWC->wctrlFlags & WHERE_ONEPASS_DESIRED)==0
      && sqlite3GlobalConfig.bUseCis
-#ifndef SQLITE_OMIT_BUILTIN_TEST
-     && (pParse->db->flags & SQLITE_CoverIdxScan)==0
-#endif
+     && OptimizationEnabled(pParse->db, SQLITE_CoverIdxScan)
     ){
       /* This index is not useful for indexing, but it is a covering index.
       ** A full-scan of the index might be a little faster than a full-scan
@@ -3259,7 +3357,7 @@ static void bestBtreeIndex(
     ** difference and select C of 3.0.
     */
     if( bSort ){
-      cost += nRow*estLog(nRow)*3;
+      cost += nRow*estLog(nRow*(nOrderBy - nOBSat)/nOrderBy)*3;
     }
     if( bDist ){
       cost += nRow*estLog(nRow)*3;
@@ -3283,7 +3381,7 @@ static void bestBtreeIndex(
     ** might be selected even when there exists an optimal index that has
     ** no such dependency.
     */
-    if( nRow>2 && cost<=pCost->rCost ){
+    if( nRow>2 && cost<=p->cost.rCost ){
       int k;                       /* Loop counter */
       int nSkipEq = nEq;           /* Number of == constraints to skip */
       int nSkipRange = nBound;     /* Number of < constraints to skip */
@@ -3292,7 +3390,7 @@ static void bestBtreeIndex(
       thisTab = getMask(pWC->pMaskSet, iCur);
       for(pTerm=pWC->a, k=pWC->nTerm; nRow>2 && k; k--, pTerm++){
         if( pTerm->wtFlags & TERM_VIRTUAL ) continue;
-        if( (pTerm->prereqAll & notValid)!=thisTab ) continue;
+        if( (pTerm->prereqAll & p->notValid)!=thisTab ) continue;
         if( pTerm->eOperator & (WO_EQ|WO_IN|WO_ISNULL) ){
           if( nSkipEq ){
             /* Ignore the first nEq equality matches since the index
@@ -3327,25 +3425,28 @@ static void bestBtreeIndex(
 
 
     WHERETRACE((
-      "%s(%s): nEq=%d nInMul=%d rangeDiv=%d bSort=%d bLookup=%d wsFlags=0x%x\n"
-      "         notReady=0x%llx log10N=%.1f nRow=%.1f cost=%.1f used=0x%llx\n",
+      "%s(%s):\n"
+      "    nEq=%d nInMul=%d rangeDiv=%d bSort=%d bLookup=%d wsFlags=0x%08x\n"
+      "    notReady=0x%llx log10N=%.1f nRow=%.1f cost=%.1f\n"
+      "    used=0x%llx nOrdered=%d nOBSat=%d\n",
       pSrc->pTab->zName, (pIdx ? pIdx->zName : "ipk"), 
       nEq, nInMul, (int)rangeDiv, bSort, bLookup, wsFlags,
-      notReady, log10N, nRow, cost, used
+      p->notReady, log10N, nRow, cost, used, nOrdered, nOBSat
     ));
 
     /* If this index is the best we have seen so far, then record this
     ** index and its cost in the pCost structure.
     */
     if( (!pIdx || wsFlags)
-     && (cost<pCost->rCost || (cost<=pCost->rCost && nRow<pCost->plan.nRow))
+     && (cost<p->cost.rCost || (cost<=p->cost.rCost && nRow<p->cost.plan.nRow))
     ){
-      pCost->rCost = cost;
-      pCost->used = used;
-      pCost->plan.nRow = nRow;
-      pCost->plan.wsFlags = (wsFlags&wsFlagMask);
-      pCost->plan.nEq = nEq;
-      pCost->plan.u.pIdx = pIdx;
+      p->cost.rCost = cost;
+      p->cost.used = used;
+      p->cost.plan.nRow = nRow;
+      p->cost.plan.wsFlags = (wsFlags&wsFlagMask);
+      p->cost.plan.nEq = nEq;
+      p->cost.plan.nOBSat = nOBSat;
+      p->cost.plan.u.pIdx = pIdx;
     }
 
     /* If there was an INDEXED BY clause, then only that one index is
@@ -3362,25 +3463,25 @@ static void bestBtreeIndex(
   ** in. This is used for application testing, to help find cases
   ** where application behaviour depends on the (undefined) order that
   ** SQLite outputs rows in in the absence of an ORDER BY clause.  */
-  if( !pOrderBy && pParse->db->flags & SQLITE_ReverseOrder ){
-    pCost->plan.wsFlags |= WHERE_REVERSE;
+  if( !p->pOrderBy && pParse->db->flags & SQLITE_ReverseOrder ){
+    p->cost.plan.wsFlags |= WHERE_REVERSE;
   }
 
-  assert( pOrderBy || (pCost->plan.wsFlags&WHERE_ORDERBY)==0 );
-  assert( pCost->plan.u.pIdx==0 || (pCost->plan.wsFlags&WHERE_ROWID_EQ)==0 );
+  assert( p->pOrderBy || (p->cost.plan.wsFlags&WHERE_ORDERBY)==0 );
+  assert( p->cost.plan.u.pIdx==0 || (p->cost.plan.wsFlags&WHERE_ROWID_EQ)==0 );
   assert( pSrc->pIndex==0 
-       || pCost->plan.u.pIdx==0 
-       || pCost->plan.u.pIdx==pSrc->pIndex 
+       || p->cost.plan.u.pIdx==0 
+       || p->cost.plan.u.pIdx==pSrc->pIndex 
   );
 
   WHERETRACE(("best index is: %s\n", 
-    ((pCost->plan.wsFlags & WHERE_NOT_FULLSCAN)==0 ? "none" : 
-         pCost->plan.u.pIdx ? pCost->plan.u.pIdx->zName : "ipk")
+    ((p->cost.plan.wsFlags & WHERE_NOT_FULLSCAN)==0 ? "none" : 
+         p->cost.plan.u.pIdx ? p->cost.plan.u.pIdx->zName : "ipk")
   ));
   
-  bestOrClauseIndex(pParse, pWC, pSrc, notReady, notValid, pOrderBy, pCost);
-  bestAutomaticIndex(pParse, pWC, pSrc, notReady, pCost);
-  pCost->plan.wsFlags |= eqTermMask;
+  bestOrClauseIndex(p);
+  bestAutomaticIndex(p);
+  p->cost.plan.wsFlags |= eqTermMask;
 }
 
 /*
@@ -3395,26 +3496,20 @@ static void bestBtreeIndex(
 ** details will be reconsidered later if the optimization is found to be
 ** applicable.
 */
-static void bestIndex(
-  Parse *pParse,              /* The parsing context */
-  WhereClause *pWC,           /* The WHERE clause */
-  struct SrcList_item *pSrc,  /* The FROM clause term to search */
-  Bitmask notReady,           /* Mask of cursors not available for indexing */
-  Bitmask notValid,           /* Cursors not available for any purpose */
-  WhereCost *pCost            /* Lowest cost query plan */
-){
+static void bestIndex(WhereBestIdx *p){
 #ifndef SQLITE_OMIT_VIRTUALTABLE
-  if( IsVirtual(pSrc->pTab) ){
-    sqlite3_index_info *p = 0;
-    bestVirtualIndex(pParse, pWC, pSrc, notReady, notValid, 0, pCost, &p);
-    if( p->needToFreeIdxStr ){
-      sqlite3_free(p->idxStr);
+  if( IsVirtual(p->pSrc->pTab) ){
+    sqlite3_index_info *pIdxInfo = 0;
+    p->ppIdxInfo = &pIdxInfo;
+    bestVirtualIndex(p);
+    if( pIdxInfo->needToFreeIdxStr ){
+      sqlite3_free(pIdxInfo->idxStr);
     }
-    sqlite3DbFree(pParse->db, p);
+    sqlite3DbFree(p->pParse->db, pIdxInfo);
   }else
 #endif
   {
-    bestBtreeIndex(pParse, pWC, pSrc, notReady, notValid, 0, 0, pCost);
+    bestBtreeIndex(p);
   }
 }
 
@@ -4694,20 +4789,24 @@ WhereInfo *sqlite3WhereBegin(
   u16 wctrlFlags,       /* One of the WHERE_* flags defined in sqliteInt.h */
   int iIdxCur           /* If WHERE_ONETABLE_ONLY is set, index cursor number */
 ){
-  int i;                     /* Loop counter */
   int nByteWInfo;            /* Num. bytes allocated for WhereInfo struct */
   int nTabList;              /* Number of elements in pTabList */
   WhereInfo *pWInfo;         /* Will become the return value of this function */
   Vdbe *v = pParse->pVdbe;   /* The virtual database engine */
   Bitmask notReady;          /* Cursors that are not yet positioned */
+  WhereBestIdx sWBI;         /* Best index search context */
   WhereMaskSet *pMaskSet;    /* The expression mask set */
-  WhereClause *pWC;               /* Decomposition of the WHERE clause */
-  struct SrcList_item *pTabItem;  /* A single entry from pTabList */
-  WhereLevel *pLevel;             /* A single level in pWInfo->a[] */
-  int iFrom;                      /* First unused FROM clause element */
+  WhereLevel *pLevel;        /* A single level in pWInfo->a[] */
+  int iFrom;                 /* First unused FROM clause element */
   int andFlags;              /* AND-ed combination of all pWC->a[].wtFlags */
+  int ii;                    /* Loop counter */
   sqlite3 *db;               /* Database connection */
 
+
+  /* Variable initialization */
+  memset(&sWBI, 0, sizeof(sWBI));
+  sWBI.pParse = pParse;
+
   /* The number of tables in the FROM clause is limited by the number of
   ** bits in a Bitmask 
   */
@@ -4747,22 +4846,23 @@ WhereInfo *sqlite3WhereBegin(
   pWInfo->pParse = pParse;
   pWInfo->pTabList = pTabList;
   pWInfo->iBreak = sqlite3VdbeMakeLabel(v);
-  pWInfo->pWC = pWC = (WhereClause *)&((u8 *)pWInfo)[nByteWInfo];
+  pWInfo->pWC = sWBI.pWC = (WhereClause *)&((u8 *)pWInfo)[nByteWInfo];
   pWInfo->wctrlFlags = wctrlFlags;
   pWInfo->savedNQueryLoop = pParse->nQueryLoop;
-  pMaskSet = (WhereMaskSet*)&pWC[1];
+  pMaskSet = (WhereMaskSet*)&sWBI.pWC[1];
+  sWBI.aLevel = pWInfo->a;
 
   /* Disable the DISTINCT optimization if SQLITE_DistinctOpt is set via
   ** sqlite3_test_ctrl(SQLITE_TESTCTRL_OPTIMIZATIONS,...) */
-  if( db->flags & SQLITE_DistinctOpt ) pDistinct = 0;
+  if( OptimizationDisabled(db, SQLITE_DistinctOpt) ) pDistinct = 0;
 
   /* Split the WHERE clause into separate subexpressions where each
   ** subexpression is separated by an AND operator.
   */
   initMaskSet(pMaskSet);
-  whereClauseInit(pWC, pParse, pMaskSet, wctrlFlags);
+  whereClauseInit(sWBI.pWC, pParse, pMaskSet, wctrlFlags);
   sqlite3ExprCodeConstants(pParse, pWhere);
-  whereSplit(pWC, pWhere, TK_AND);   /* IMP: R-15842-53296 */
+  whereSplit(sWBI.pWC, pWhere, TK_AND);   /* IMP: R-15842-53296 */
     
   /* Special case: a WHERE clause that is constant.  Evaluate the
   ** expression and either jump over all of the code or fall thru.
@@ -4793,20 +4893,20 @@ WhereInfo *sqlite3WhereBegin(
   ** equal to pTabList->nSrc but might be shortened to 1 if the
   ** WHERE_ONETABLE_ONLY flag is set.
   */
-  assert( pWC->vmask==0 && pMaskSet->n==0 );
-  for(i=0; i<pTabList->nSrc; i++){
-    createMask(pMaskSet, pTabList->a[i].iCursor);
+  assert( sWBI.pWC->vmask==0 && pMaskSet->n==0 );
+  for(ii=0; ii<pTabList->nSrc; ii++){
+    createMask(pMaskSet, pTabList->a[ii].iCursor);
 #ifndef SQLITE_OMIT_VIRTUALTABLE
-    if( ALWAYS(pTabList->a[i].pTab) && IsVirtual(pTabList->a[i].pTab) ){
-      pWC->vmask |= ((Bitmask)1 << i);
+    if( ALWAYS(pTabList->a[ii].pTab) && IsVirtual(pTabList->a[ii].pTab) ){
+      sWBI.pWC->vmask |= ((Bitmask)1 << ii);
     }
 #endif
   }
 #ifndef NDEBUG
   {
     Bitmask toTheLeft = 0;
-    for(i=0; i<pTabList->nSrc; i++){
-      Bitmask m = getMask(pMaskSet, pTabList->a[i].iCursor);
+    for(ii=0; ii<pTabList->nSrc; ii++){
+      Bitmask m = getMask(pMaskSet, pTabList->a[ii].iCursor);
       assert( (m-1)==toTheLeft );
       toTheLeft |= m;
     }
@@ -4818,7 +4918,7 @@ WhereInfo *sqlite3WhereBegin(
   ** want to analyze these virtual terms, so start analyzing at the end
   ** and work forward so that the added virtual terms are never processed.
   */
-  exprAnalyzeAll(pTabList, pWC);
+  exprAnalyzeAll(pTabList, sWBI.pWC);
   if( db->mallocFailed ){
     goto whereBeginError;
   }
@@ -4827,7 +4927,7 @@ WhereInfo *sqlite3WhereBegin(
   ** If it is, then set pDistinct to NULL and WhereInfo.eDistinct to
   ** WHERE_DISTINCT_UNIQUE to tell the caller to ignore the DISTINCT.
   */
-  if( pDistinct && isDistinctRedundant(pParse, pTabList, pWC, pDistinct) ){
+  if( pDistinct && isDistinctRedundant(pParse, pTabList, sWBI.pWC, pDistinct) ){
     pDistinct = 0;
     pWInfo->eDistinct = WHERE_DISTINCT_UNIQUE;
   }
@@ -4847,10 +4947,13 @@ WhereInfo *sqlite3WhereBegin(
   ** This loop also figures out the nesting order of tables in the FROM
   ** clause.
   */
-  notReady = ~(Bitmask)0;
+  sWBI.notValid = ~(Bitmask)0;
+  sWBI.pOrderBy = pOrderBy;
+  sWBI.n = nTabList;
+  sWBI.pDistinct = pDistinct;
   andFlags = ~0;
   WHERETRACE(("*** Optimizer Start ***\n"));
-  for(i=iFrom=0, pLevel=pWInfo->a; i<nTabList; i++, pLevel++){
+  for(sWBI.i=iFrom=0, pLevel=pWInfo->a; sWBI.i<nTabList; sWBI.i++, pLevel++){
     WhereCost bestPlan;         /* Most efficient plan seen so far */
     Index *pIdx;                /* Index for FROM table at pTabItem */
     int j;                      /* For looping over FROM tables */
@@ -4862,7 +4965,7 @@ WhereInfo *sqlite3WhereBegin(
 
     memset(&bestPlan, 0, sizeof(bestPlan));
     bestPlan.rCost = SQLITE_BIG_DBL;
-    WHERETRACE(("*** Begin search for loop %d ***\n", i));
+    WHERETRACE(("*** Begin search for loop %d ***\n", sWBI.i));
 
     /* Loop through the remaining entries in the FROM clause to find the
     ** next nested loop. The loop tests all FROM clause entries
@@ -4878,8 +4981,8 @@ WhereInfo *sqlite3WhereBegin(
     ** by waiting for other tables to run first.  This "optimal" test works
     ** by first assuming that the FROM clause is on the inner loop and finding
     ** its query plan, then checking to see if that query plan uses any
-    ** other FROM clause terms that are notReady.  If no notReady terms are
-    ** used then the "optimal" query plan works.
+    ** other FROM clause terms that are sWBI.notValid.  If no notValid terms
+    ** are used then the "optimal" query plan works.
     **
     ** Note that the WhereCost.nRow parameter for an optimal scan might
     ** not be as small as it would be if the table really were the innermost
@@ -4910,55 +5013,48 @@ WhereInfo *sqlite3WhereBegin(
     nUnconstrained = 0;
     notIndexed = 0;
     for(isOptimal=(iFrom<nTabList-1); isOptimal>=0 && bestJ<0; isOptimal--){
-      Bitmask mask;             /* Mask of tables not yet ready */
-      for(j=iFrom, pTabItem=&pTabList->a[j]; j<nTabList; j++, pTabItem++){
+      for(j=iFrom, sWBI.pSrc=&pTabList->a[j]; j<nTabList; j++, sWBI.pSrc++){
         int doNotReorder;    /* True if this table should not be reordered */
-        WhereCost sCost;     /* Cost information from best[Virtual]Index() */
-        ExprList *pOB;       /* ORDER BY clause for index to optimize */
-        ExprList *pDist;     /* DISTINCT clause for index to optimize */
   
-        doNotReorder =  (pTabItem->jointype & (JT_LEFT|JT_CROSS))!=0;
+        doNotReorder =  (sWBI.pSrc->jointype & (JT_LEFT|JT_CROSS))!=0;
         if( j!=iFrom && doNotReorder ) break;
-        m = getMask(pMaskSet, pTabItem->iCursor);
-        if( (m & notReady)==0 ){
+        m = getMask(pMaskSet, sWBI.pSrc->iCursor);
+        if( (m & sWBI.notValid)==0 ){
           if( j==iFrom ) iFrom++;
           continue;
         }
-        mask = (isOptimal ? m : notReady);
-        pOB = (i==0) ? pOrderBy : 0;
-        pDist = (i==0 ? pDistinct : 0);
-        if( pTabItem->pIndex==0 ) nUnconstrained++;
+        sWBI.notReady = (isOptimal ? m : sWBI.notValid);
+        if( sWBI.pSrc->pIndex==0 ) nUnconstrained++;
   
         WHERETRACE(("=== trying table %d with isOptimal=%d ===\n",
                     j, isOptimal));
-        assert( pTabItem->pTab );
+        assert( sWBI.pSrc->pTab );
 #ifndef SQLITE_OMIT_VIRTUALTABLE
-        if( IsVirtual(pTabItem->pTab) ){
-          sqlite3_index_info **pp = &pWInfo->a[j].pIdxInfo;
-          bestVirtualIndex(pParse, pWC, pTabItem, mask, notReady, pOB,
-                           &sCost, pp);
+        if( IsVirtual(sWBI.pSrc->pTab) ){
+          sWBI.ppIdxInfo = &pWInfo->a[j].pIdxInfo;
+          bestVirtualIndex(&sWBI);
         }else 
 #endif
         {
-          bestBtreeIndex(pParse, pWC, pTabItem, mask, notReady, pOB,
-              pDist, &sCost);
+          bestBtreeIndex(&sWBI);
         }
-        assert( isOptimal || (sCost.used&notReady)==0 );
+        assert( isOptimal || (sWBI.cost.used&sWBI.notValid)==0 );
 
         /* If an INDEXED BY clause is present, then the plan must use that
         ** index if it uses any index at all */
-        assert( pTabItem->pIndex==0 
-                  || (sCost.plan.wsFlags & WHERE_NOT_FULLSCAN)==0
-                  || sCost.plan.u.pIdx==pTabItem->pIndex );
+        assert( sWBI.pSrc->pIndex==0 
+                  || (sWBI.cost.plan.wsFlags & WHERE_NOT_FULLSCAN)==0
+                  || sWBI.cost.plan.u.pIdx==sWBI.pSrc->pIndex );
 
-        if( isOptimal && (sCost.plan.wsFlags & WHERE_NOT_FULLSCAN)==0 ){
+        if( isOptimal && (sWBI.cost.plan.wsFlags & WHERE_NOT_FULLSCAN)==0 ){
           notIndexed |= m;
         }
 
         /* Conditions under which this table becomes the best so far:
         **
         **   (1) The table must not depend on other tables that have not
-        **       yet run.
+        **       yet run.  (In other words, it must not depend on tables
+        **       in inner loops.)
         **
         **   (2) A full-table-scan plan cannot supercede indexed plan unless
         **       the full-table-scan is an "optimal" plan as defined above.
@@ -4975,30 +5071,32 @@ WhereInfo *sqlite3WhereBegin(
         **   (4) The plan cost must be lower than prior plans or else the
         **       cost must be the same and the number of rows must be lower.
         */
-        if( (sCost.used&notReady)==0                       /* (1) */
-            && (bestJ<0 || (notIndexed&m)!=0               /* (2) */
+        if( (sWBI.cost.used&sWBI.notValid)==0                    /* (1) */
+            && (bestJ<0 || (notIndexed&m)!=0                     /* (2) */
                 || (bestPlan.plan.wsFlags & WHERE_NOT_FULLSCAN)==0
-                || (sCost.plan.wsFlags & WHERE_NOT_FULLSCAN)!=0)
-            && (nUnconstrained==0 || pTabItem->pIndex==0   /* (3) */
-                || NEVER((sCost.plan.wsFlags & WHERE_NOT_FULLSCAN)!=0))
-            && (bestJ<0 || sCost.rCost<bestPlan.rCost      /* (4) */
-                || (sCost.rCost<=bestPlan.rCost 
-                 && sCost.plan.nRow<bestPlan.plan.nRow))
+                || (sWBI.cost.plan.wsFlags & WHERE_NOT_FULLSCAN)!=0)
+            && (nUnconstrained==0 || sWBI.pSrc->pIndex==0        /* (3) */
+                || NEVER((sWBI.cost.plan.wsFlags & WHERE_NOT_FULLSCAN)!=0))
+            && (bestJ<0 || sWBI.cost.rCost<bestPlan.rCost        /* (4) */
+                || (sWBI.cost.rCost<=bestPlan.rCost 
+                 && sWBI.cost.plan.nRow<bestPlan.plan.nRow))
         ){
           WHERETRACE(("=== table %d is best so far"
-                      " with cost=%g and nRow=%g\n",
-                      j, sCost.rCost, sCost.plan.nRow));
-          bestPlan = sCost;
+                      " with cost=%.1f, nRow=%.1f, nOBSat=%d\n",
+                      j, sWBI.cost.rCost, sWBI.cost.plan.nRow,
+                      sWBI.cost.plan.nOBSat));
+          bestPlan = sWBI.cost;
           bestJ = j;
         }
         if( doNotReorder ) break;
       }
     }
     assert( bestJ>=0 );
-    assert( notReady & getMask(pMaskSet, pTabList->a[bestJ].iCursor) );
-    WHERETRACE(("*** Optimizer selects table %d for loop %d"
-                " with cost=%g and nRow=%g\n",
-                bestJ, pLevel-pWInfo->a, bestPlan.rCost, bestPlan.plan.nRow));
+    assert( sWBI.notValid & getMask(pMaskSet, pTabList->a[bestJ].iCursor) );
+    WHERETRACE(("*** Optimizer selects table %d for loop %d with:\n"
+                "    cost=%.1f, nRow=%.1f, nOBSat=%d wsFlags=0x%08x\n",
+                bestJ, pLevel-pWInfo->a, bestPlan.rCost, bestPlan.plan.nRow,
+                bestPlan.plan.nOBSat, bestPlan.plan.wsFlags));
     if( (bestPlan.plan.wsFlags & WHERE_ORDERBY)!=0 ){
       pWInfo->nOBSat = pOrderBy->nExpr;
     }
@@ -5021,7 +5119,7 @@ WhereInfo *sqlite3WhereBegin(
     }else{
       pLevel->iIdxCur = -1;
     }
-    notReady &= ~getMask(pMaskSet, pTabList->a[bestJ].iCursor);
+    sWBI.notValid &= ~getMask(pMaskSet, pTabList->a[bestJ].iCursor);
     pLevel->iFrom = (u8)bestJ;
     if( bestPlan.plan.nRow>=(double)1 ){
       pParse->nQueryLoop *= bestPlan.plan.nRow;
@@ -5074,9 +5172,10 @@ WhereInfo *sqlite3WhereBegin(
   sqlite3CodeVerifySchema(pParse, -1); /* Insert the cookie verifier Goto */
   notReady = ~(Bitmask)0;
   pWInfo->nRowOut = (double)1;
-  for(i=0, pLevel=pWInfo->a; i<nTabList; i++, pLevel++){
+  for(ii=0, pLevel=pWInfo->a; ii<nTabList; ii++, pLevel++){
     Table *pTab;     /* Table to open */
     int iDb;         /* Index of database containing table/index */
+    struct SrcList_item *pTabItem;
 
     pTabItem = &pTabList->a[pLevel->iFrom];
     pTab = pTabItem->pTab;
@@ -5112,7 +5211,7 @@ WhereInfo *sqlite3WhereBegin(
     }
 #ifndef SQLITE_OMIT_AUTOMATIC_INDEX
     if( (pLevel->plan.wsFlags & WHERE_TEMP_INDEX)!=0 ){
-      constructAutomaticIndex(pParse, pWC, pTabItem, notReady, pLevel);
+      constructAutomaticIndex(pParse, sWBI.pWC, pTabItem, notReady, pLevel);
     }else
 #endif
     if( (pLevel->plan.wsFlags & WHERE_INDEXED)!=0 ){
@@ -5126,7 +5225,7 @@ WhereInfo *sqlite3WhereBegin(
       VdbeComment((v, "%s", pIx->zName));
     }
     sqlite3CodeVerifySchema(pParse, iDb);
-    notReady &= ~getMask(pWC->pMaskSet, pTabItem->iCursor);
+    notReady &= ~getMask(sWBI.pWC->pMaskSet, pTabItem->iCursor);
   }
   pWInfo->iTop = sqlite3VdbeCurrentAddr(v);
   if( db->mallocFailed ) goto whereBeginError;
@@ -5136,10 +5235,10 @@ WhereInfo *sqlite3WhereBegin(
   ** program.
   */
   notReady = ~(Bitmask)0;
-  for(i=0; i<nTabList; i++){
-    pLevel = &pWInfo->a[i];
-    explainOneScan(pParse, pTabList, pLevel, i, pLevel->iFrom, wctrlFlags);
-    notReady = codeOneLoopStart(pWInfo, i, wctrlFlags, notReady);
+  for(ii=0; ii<nTabList; ii++){
+    pLevel = &pWInfo->a[ii];
+    explainOneScan(pParse, pTabList, pLevel, ii, pLevel->iFrom, wctrlFlags);
+    notReady = codeOneLoopStart(pWInfo, ii, wctrlFlags, notReady);
     pWInfo->iContinue = pLevel->addrCont;
   }
 
@@ -5150,11 +5249,13 @@ WhereInfo *sqlite3WhereBegin(
   ** the index is listed as "{}".  If the primary key is used the
   ** index name is '*'.
   */
-  for(i=0; i<nTabList; i++){
+  for(ii=0; ii<nTabList; ii++){
     char *z;
     int n;
     int w;
-    pLevel = &pWInfo->a[i];
+    struct SrcList_item *pTabItem;
+
+    pLevel = &pWInfo->a[ii];
     w = pLevel->plan.wsFlags;
     pTabItem = &pTabList->a[pLevel->iFrom];
     z = pTabItem->zAlias;