text: /*
  ** 2001 September 15
  **
  ** The author disclaims copyright to this source code.  In place of
  ** a legal notice, here is a blessing:
  **
  **    May you do good and not evil.
  **    May you find forgiveness for yourself and forgive others.
  **    May you share freely, never taking more than you give.
  **
  *************************************************************************
  ** This module contains C code that generates VDBE code used to process
  ** the WHERE clause of SQL statements.  This module is responsible for
  ** generating the code that loops through a table looking for applicable
  ** rows.  Indices are selected and used to speed the search when doing
  ** so is applicable.  Because this module is responsible for selecting
  ** indices, you might also think of this module as the "query optimizer".
  */
  #include "sqliteInt.h"
  #include "whereInt.h"
  
  /*
  ** Extra information appended to the end of sqlite3_index_info but not
  ** visible to the xBestIndex function, at least not directly.  The
  ** sqlite3_vtab_collation() interface knows how to reach it, however.
  **
  ** This object is not an API and can be changed from one release to the
  ** next.  As long as allocateIndexInfo() and sqlite3_vtab_collation()
  ** agree on the structure, all will be well.
  */
  typedef struct HiddenIndexInfo HiddenIndexInfo;
  struct HiddenIndexInfo {
    WhereClause *pWC;   /* The Where clause being analyzed */
    Parse *pParse;      /* The parsing context */
  };
  
  /* Forward declaration of methods */
  int whereLoopResize(sqlite3*, WhereLoop*, int);
  
  /* Test variable that can be set to enable WHERE tracing */
  #if defined(SQLITE_TEST) || defined(SQLITE_DEBUG)
  /***/ int sqlite3WhereTrace = 0;
  #endif
  
  
  /*
  ** Return the estimated number of output rows from a WHERE clause
  */
  LogEst sqlite3WhereOutputRowCount(WhereInfo *pWInfo){
    return pWInfo->nRowOut;
  }
  
  /*
  ** Return one of the WHERE_DISTINCT_xxxxx values to indicate how this
  ** WHERE clause returns outputs for DISTINCT processing.
  */
  int sqlite3WhereIsDistinct(WhereInfo *pWInfo){
    return pWInfo->eDistinct;
  }
  
  /*
  ** Return TRUE if the WHERE clause returns rows in ORDER BY order.
  ** Return FALSE if the output needs to be sorted.
  */
  int sqlite3WhereIsOrdered(WhereInfo *pWInfo){
    return pWInfo->nOBSat;
  }
  
  /*
  ** In the ORDER BY LIMIT optimization, if the inner-most loop is known
  ** to emit rows in increasing order, and if the last row emitted by the
  ** inner-most loop did not fit within the sorter, then we can skip all
  ** subsequent rows for the current iteration of the inner loop (because they
  ** will not fit in the sorter either) and continue with the second inner
  ** loop - the loop immediately outside the inner-most.
  **
  ** When a row does not fit in the sorter (because the sorter already
  ** holds LIMIT+OFFSET rows that are smaller), then a jump is made to the
  ** label returned by this function.
  **
  ** If the ORDER BY LIMIT optimization applies, the jump destination should
  ** be the continuation for the second-inner-most loop.  If the ORDER BY
  ** LIMIT optimization does not apply, then the jump destination should
  ** be the continuation for the inner-most loop.
  **
  ** It is always safe for this routine to return the continuation of the
  ** inner-most loop, in the sense that a correct answer will result.  
  ** Returning the continuation the second inner loop is an optimization
  ** that might make the code run a little faster, but should not change
  ** the final answer.
  */
  int sqlite3WhereOrderByLimitOptLabel(WhereInfo *pWInfo){
    WhereLevel *pInner;
    if( !pWInfo->bOrderedInnerLoop ){
      /* The ORDER BY LIMIT optimization does not apply.  Jump to the 
      ** continuation of the inner-most loop. */
      return pWInfo->iContinue;
    }
    pInner = &pWInfo->a[pWInfo->nLevel-1];
    assert( pInner->addrNxt!=0 );
    return pInner->addrNxt;
  }
  
  /*
  ** Return the VDBE address or label to jump to in order to continue
  ** immediately with the next row of a WHERE clause.
  */
  int sqlite3WhereContinueLabel(WhereInfo *pWInfo){
    assert( pWInfo->iContinue!=0 );
    return pWInfo->iContinue;
  }
  
  /*
  ** Return the VDBE address or label to jump to in order to break
  ** out of a WHERE loop.
  */
  int sqlite3WhereBreakLabel(WhereInfo *pWInfo){
    return pWInfo->iBreak;
  }
  
  /*
  ** Return ONEPASS_OFF (0) if an UPDATE or DELETE statement is unable to
  ** operate directly on the rowids returned by a WHERE clause.  Return
  ** ONEPASS_SINGLE (1) if the statement can operation directly because only
  ** a single row is to be changed.  Return ONEPASS_MULTI (2) if the one-pass
  ** optimization can be used on multiple 
  **
  ** If the ONEPASS optimization is used (if this routine returns true)
  ** then also write the indices of open cursors used by ONEPASS
  ** into aiCur[0] and aiCur[1].  iaCur[0] gets the cursor of the data
  ** table and iaCur[1] gets the cursor used by an auxiliary index.
  ** Either value may be -1, indicating that cursor is not used.
  ** Any cursors returned will have been opened for writing.
  **
  ** aiCur[0] and aiCur[1] both get -1 if the where-clause logic is
  ** unable to use the ONEPASS optimization.
  */
  int sqlite3WhereOkOnePass(WhereInfo *pWInfo, int *aiCur){
    memcpy(aiCur, pWInfo->aiCurOnePass, sizeof(int)*2);
  #ifdef WHERETRACE_ENABLED
    if( sqlite3WhereTrace && pWInfo->eOnePass!=ONEPASS_OFF ){
      sqlite3DebugPrintf("%s cursors: %d %d\n",
           pWInfo->eOnePass==ONEPASS_SINGLE ? "ONEPASS_SINGLE" : "ONEPASS_MULTI",
           aiCur[0], aiCur[1]);
    }
  #endif
    return pWInfo->eOnePass;
  }
  
  /*
  ** Return TRUE if the WHERE loop uses the OP_DeferredSeek opcode to move
  ** the data cursor to the row selected by the index cursor.
  */
  int sqlite3WhereUsesDeferredSeek(WhereInfo *pWInfo){
    return pWInfo->bDeferredSeek;
  }
  
  /*
  ** Move the content of pSrc into pDest
  */
  void whereOrMove(WhereOrSet *pDest, WhereOrSet *pSrc){
    pDest->n = pSrc->n;
    memcpy(pDest->a, pSrc->a, pDest->n*sizeof(pDest->a[0]));
  }
  
  /*
  ** Try to insert a new prerequisite/cost entry into the WhereOrSet pSet.
  **
  ** The new entry might overwrite an existing entry, or it might be
  ** appended, or it might be discarded.  Do whatever is the right thing
  ** so that pSet keeps the N_OR_COST best entries seen so far.
  */
  int whereOrInsert(
    WhereOrSet *pSet,      /* The WhereOrSet to be updated */
    Bitmask prereq,        /* Prerequisites of the new entry */
    LogEst rRun,           /* Run-cost of the new entry */
    LogEst nOut            /* Number of outputs for the new entry */
  ){
    u16 i;
    WhereOrCost *p;
    for(i=pSet->n, p=pSet->a; i>0; i--, p++){
      if( rRun<=p->rRun && (prereq & p->prereq)==prereq ){
        goto whereOrInsert_done;
      }
      if( p->rRun<=rRun && (p->prereq & prereq)==p->prereq ){
        return 0;
      }
    }
    if( pSet->n<N_OR_COST ){
      p = &pSet->a[pSet->n++];
      p->nOut = nOut;
    }else{
      p = pSet->a;
      for(i=1; i<pSet->n; i++){
        if( p->rRun>pSet->a[i].rRun ) p = pSet->a + i;
      }
      if( p->rRun<=rRun ) return 0;
    }
  whereOrInsert_done:
    p->prereq = prereq;
    p->rRun = rRun;
    if( p->nOut>nOut ) p->nOut = nOut;
    return 1;
  }
  
  /*
  ** Return the bitmask for the given cursor number.  Return 0 if
  ** iCursor is not in the set.
  */
  Bitmask sqlite3WhereGetMask(WhereMaskSet *pMaskSet, int iCursor){
    int i;
    assert( pMaskSet->n<=(int)sizeof(Bitmask)*8 );
    for(i=0; i<pMaskSet->n; i++){
      if( pMaskSet->ix[i]==iCursor ){
        return MASKBIT(i);
      }
    }
    return 0;
  }
  
  /*
  ** Create a new mask for cursor iCursor.
  **
  ** There is one cursor per table in the FROM clause.  The number of
  ** tables in the FROM clause is limited by a test early in the
  ** sqlite3WhereBegin() routine.  So we know that the pMaskSet->ix[]
  ** array will never overflow.
  */
  void createMask(WhereMaskSet *pMaskSet, int iCursor){
    assert( pMaskSet->n < ArraySize(pMaskSet->ix) );
    pMaskSet->ix[pMaskSet->n++] = iCursor;
  }
  
  /*
  ** Advance to the next WhereTerm that matches according to the criteria
  ** established when the pScan object was initialized by whereScanInit().
  ** Return NULL if there are no more matching WhereTerms.
  */
  WhereTerm *whereScanNext(WhereScan *pScan){
    int iCur;            /* The cursor on the LHS of the term */
    i16 iColumn;         /* The column on the LHS of the term.  -1 for IPK */
    Expr *pX;            /* An expression being tested */
    WhereClause *pWC;    /* Shorthand for pScan->pWC */
    WhereTerm *pTerm;    /* The term being tested */
    int k = pScan->k;    /* Where to start scanning */
  
    assert( pScan->iEquiv<=pScan->nEquiv );
    pWC = pScan->pWC;
    while(1){
      iColumn = pScan->aiColumn[pScan->iEquiv-1];
      iCur = pScan->aiCur[pScan->iEquiv-1];
      assert( pWC!=0 );
      do{
        for(pTerm=pWC->a+k; k<pWC->nTerm; k++, pTerm++){
          if( pTerm->leftCursor==iCur
           && pTerm->u.leftColumn==iColumn
           && (iColumn!=XN_EXPR
               || sqlite3ExprCompareSkip(pTerm->pExpr->pLeft,
                                         pScan->pIdxExpr,iCur)==0)
           && (pScan->iEquiv<=1 || !ExprHasProperty(pTerm->pExpr, EP_FromJoin))
          ){
            if( (pTerm->eOperator & WO_EQUIV)!=0
             && pScan->nEquiv<ArraySize(pScan->aiCur)
             && (pX = sqlite3ExprSkipCollateAndLikely(pTerm->pExpr->pRight))->op
                 ==TK_COLUMN
            ){
              int j;
              for(j=0; j<pScan->nEquiv; j++){
                if( pScan->aiCur[j]==pX->iTable
                 && pScan->aiColumn[j]==pX->iColumn ){
                    break;
                }
              }
              if( j==pScan->nEquiv ){
                pScan->aiCur[j] = pX->iTable;
                pScan->aiColumn[j] = pX->iColumn;
                pScan->nEquiv++;
              }
            }
            if( (pTerm->eOperator & pScan->opMask)!=0 ){
              /* Verify the affinity and collating sequence match */
              if( pScan->zCollName && (pTerm->eOperator & WO_ISNULL)==0 ){
                CollSeq *pColl;
                Parse *pParse = pWC->pWInfo->pParse;
                pX = pTerm->pExpr;
                if( !sqlite3IndexAffinityOk(pX, pScan->idxaff) ){
                  continue;
                }
                assert(pX->pLeft);
                pColl = sqlite3ExprCompareCollSeq(pParse, pX);
                if( pColl==0 ) pColl = pParse->db->pDfltColl;
                if( sqlite3StrICmp(pColl->zName, pScan->zCollName) ){
                  continue;
                }
              }
              if( (pTerm->eOperator & (WO_EQ|WO_IS))!=0
               && (pX = pTerm->pExpr->pRight)->op==TK_COLUMN
               && pX->iTable==pScan->aiCur[0]
               && pX->iColumn==pScan->aiColumn[0]
              ){
                testcase( pTerm->eOperator & WO_IS );
                continue;
              }
              pScan->pWC = pWC;
              pScan->k = k+1;
              return pTerm;
            }
          }
        }
        pWC = pWC->pOuter;
        k = 0;
      }while( pWC!=0 );
      if( pScan->iEquiv>=pScan->nEquiv ) break;
      pWC = pScan->pOrigWC;
      k = 0;
      pScan->iEquiv++;
    }
    return 0;
  }
  
  /*
  ** This is whereScanInit() for the case of an index on an expression.
  ** It is factored out into a separate tail-recursion subroutine so that
  ** the normal whereScanInit() routine, which is a high-runner, does not
  ** need to push registers onto the stack as part of its prologue.
  */
  SQLITE_NOINLINE WhereTerm *whereScanInitIndexExpr(WhereScan *pScan){
    pScan->idxaff = sqlite3ExprAffinity(pScan->pIdxExpr);
    return whereScanNext(pScan);
  }
  
  /*
  ** Initialize a WHERE clause scanner object.  Return a pointer to the
  ** first match.  Return NULL if there are no matches.
  **
  ** The scanner will be searching the WHERE clause pWC.  It will look
  ** for terms of the form "X <op> <expr>" where X is column iColumn of table
  ** iCur.   Or if pIdx!=0 then X is column iColumn of index pIdx.  pIdx
  ** must be one of the indexes of table iCur.
  **
  ** The <op> must be one of the operators described by opMask.
  **
  ** If the search is for X and the WHERE clause contains terms of the
  ** form X=Y then this routine might also return terms of the form
  ** "Y <op> <expr>".  The number of levels of transitivity is limited,
  ** but is enough to handle most commonly occurring SQL statements.
  **
  ** If X is not the INTEGER PRIMARY KEY then X must be compatible with
  ** index pIdx.
  */
  WhereTerm *whereScanInit(
    WhereScan *pScan,       /* The WhereScan object being initialized */
    WhereClause *pWC,       /* The WHERE clause to be scanned */
    int iCur,               /* Cursor to scan for */
    int iColumn,            /* Column to scan for */
    u32 opMask,             /* Operator(s) to scan for */
    Index *pIdx             /* Must be compatible with this index */
  ){
    pScan->pOrigWC = pWC;
    pScan->pWC = pWC;
    pScan->pIdxExpr = 0;
    pScan->idxaff = 0;
    pScan->zCollName = 0;
    pScan->opMask = opMask;
    pScan->k = 0;
    pScan->aiCur[0] = iCur;
    pScan->nEquiv = 1;
    pScan->iEquiv = 1;
    if( pIdx ){
      int j = iColumn;
      iColumn = pIdx->aiColumn[j];
      if( iColumn==XN_EXPR ){
        pScan->pIdxExpr = pIdx->aColExpr->a[j].pExpr;
        pScan->zCollName = pIdx->azColl[j];
        pScan->aiColumn[0] = XN_EXPR;
        return whereScanInitIndexExpr(pScan);
      }else if( iColumn==pIdx->pTable->iPKey ){
        iColumn = XN_ROWID;
      }else if( iColumn>=0 ){
        pScan->idxaff = pIdx->pTable->aCol[iColumn].affinity;
        pScan->zCollName = pIdx->azColl[j];
      }
    }else if( iColumn==XN_EXPR ){
      return 0;
    }
    pScan->aiColumn[0] = iColumn;
    return whereScanNext(pScan);
  }
  
  /*
  ** Search for a term in the WHERE clause that is of the form "X <op> <expr>"
  ** where X is a reference to the iColumn of table iCur or of index pIdx
  ** if pIdx!=0 and <op> is one of the WO_xx operator codes specified by
  ** the op parameter.  Return a pointer to the term.  Return 0 if not found.
  **
  ** If pIdx!=0 then it must be one of the indexes of table iCur.  
  ** Search for terms matching the iColumn-th column of pIdx
  ** rather than the iColumn-th column of table iCur.
  **
  ** The term returned might by Y=<expr> if there is another constraint in
  ** the WHERE clause that specifies that X=Y.  Any such constraints will be
  ** identified by the WO_EQUIV bit in the pTerm->eOperator field.  The
  ** aiCur[]/iaColumn[] arrays hold X and all its equivalents. There are 11
  ** slots in aiCur[]/aiColumn[] so that means we can look for X plus up to 10
  ** other equivalent values.  Hence a search for X will return <expr> if X=A1
  ** and A1=A2 and A2=A3 and ... and A9=A10 and A10=<expr>.
  **
  ** If there are multiple terms in the WHERE clause of the form "X <op> <expr>"
  ** then try for the one with no dependencies on <expr> - in other words where
  ** <expr> is a constant expression of some kind.  Only return entries of
  ** the form "X <op> Y" where Y is a column in another table if no terms of
  ** the form "X <op> <const-expr>" exist.   If no terms with a constant RHS
  ** exist, try to return a term that does not use WO_EQUIV.
  */
  WhereTerm *sqlite3WhereFindTerm(
    WhereClause *pWC,     /* The WHERE clause to be searched */
    int iCur,             /* Cursor number of LHS */
    int iColumn,          /* Column number of LHS */
    Bitmask notReady,     /* RHS must not overlap with this mask */
    u32 op,               /* Mask of WO_xx values describing operator */
    Index *pIdx           /* Must be compatible with this index, if not NULL */
  ){
    WhereTerm *pResult = 0;
    WhereTerm *p;
    WhereScan scan;
  
    p = whereScanInit(&scan, pWC, iCur, iColumn, op, pIdx);
    op &= WO_EQ|WO_IS;
    while( p ){
      if( (p->prereqRight & notReady)==0 ){
        if( p->prereqRight==0 && (p->eOperator&op)!=0 ){
          testcase( p->eOperator & WO_IS );
          return p;
        }
        if( pResult==0 ) pResult = p;
      }
      p = whereScanNext(&scan);
    }
    return pResult;
  }
  
  /*
  ** This function searches pList for an entry that matches the iCol-th column
  ** of index pIdx.
  **
  ** If such an expression is found, its index in pList->a[] is returned. If
  ** no expression is found, -1 is returned.
  */
  int findIndexCol(
    Parse *pParse,                  /* Parse context */
    ExprList *pList,                /* Expression list to search */
    int iBase,                      /* Cursor for table associated with pIdx */
    Index *pIdx,                    /* Index to match column of */
    int iCol                        /* Column of index to match */
  ){
    int i;
    const char *zColl = pIdx->azColl[iCol];
  
    for(i=0; i<pList->nExpr; i++){
      Expr *p = sqlite3ExprSkipCollateAndLikely(pList->a[i].pExpr);
      if( p->op==TK_COLUMN
       && p->iColumn==pIdx->aiColumn[iCol]
       && p->iTable==iBase
      ){
        CollSeq *pColl = sqlite3ExprNNCollSeq(pParse, pList->a[i].pExpr);
        if( 0==sqlite3StrICmp(pColl->zName, zColl) ){
          return i;
        }
      }
    }
  
    return -1;
  }
  
  /*
  ** Return TRUE if the iCol-th column of index pIdx is NOT NULL
  */
  int indexColumnNotNull(Index *pIdx, int iCol){
    int j;
    assert( pIdx!=0 );
    assert( iCol>=0 && iCol<pIdx->nColumn );
    j = pIdx->aiColumn[iCol];
    if( j>=0 ){
      return pIdx->pTable->aCol[j].notNull;
    }else if( j==(-1) ){
      return 1;
    }else{
      assert( j==(-2) );
      return 0;  /* Assume an indexed expression can always yield a NULL */
  
    }
  }
  
  /*
  ** Return true if the DISTINCT expression-list passed as the third argument
  ** is redundant.
  **
  ** A DISTINCT list is redundant if any subset of the columns in the
  ** DISTINCT list are collectively unique and individually non-null.
  */
  int isDistinctRedundant(
    Parse *pParse,            /* Parsing context */
    SrcList *pTabList,        /* The FROM clause */
    WhereClause *pWC,         /* The WHERE clause */
    ExprList *pDistinct       /* The result set that needs to be DISTINCT */
  ){
    Table *pTab;
    Index *pIdx;
    int i;                          
    int iBase;
  
    /* If there is more than one table or sub-select in the FROM clause of
    ** this query, then it will not be possible to show that the DISTINCT 
    ** clause is redundant. */
    if( pTabList->nSrc!=1 ) return 0;
    iBase = pTabList->a[0].iCursor;
    pTab = pTabList->a[0].pTab;
  
    /* If any of the expressions is an IPK column on table iBase, then return 
    ** true. Note: The (p->iTable==iBase) part of this test may be false if the
    ** current SELECT is a correlated sub-query.
    */
    for(i=0; i<pDistinct->nExpr; i++){
      Expr *p = sqlite3ExprSkipCollateAndLikely(pDistinct->a[i].pExpr);
      if( p->op==TK_COLUMN && p->iTable==iBase && p->iColumn<0 ) return 1;
    }
  
    /* Loop through all indices on the table, checking each to see if it makes
    ** the DISTINCT qualifier redundant. It does so if:
    **
    **   1. The index is itself UNIQUE, and
    **
    **   2. All of the columns in the index are either part of the pDistinct
    **      list, or else the WHERE clause contains a term of the form "col=X",
    **      where X is a constant value. The collation sequences of the
    **      comparison and select-list expressions must match those of the index.
    **
    **   3. All of those index columns for which the WHERE clause does not
    **      contain a "col=X" term are subject to a NOT NULL constraint.
    */
    for(pIdx=pTab->pIndex; pIdx; pIdx=pIdx->pNext){
      if( !IsUniqueIndex(pIdx) ) continue;
      for(i=0; i<pIdx->nKeyCol; i++){
        if( 0==sqlite3WhereFindTerm(pWC, iBase, i, ~(Bitmask)0, WO_EQ, pIdx) ){
          if( findIndexCol(pParse, pDistinct, iBase, pIdx, i)<0 ) break;
          if( indexColumnNotNull(pIdx, i)==0 ) break;
        }
      }
      if( i==pIdx->nKeyCol ){
        /* This index implies that the DISTINCT qualifier is redundant. */
        return 1;
      }
    }
  
    return 0;
  }
  
  
  /*
  ** Estimate the logarithm of the input value to base 2.
  */
  LogEst estLog(LogEst N){
    return N<=10 ? 0 : sqlite3LogEst(N) - 33;
  }
  
  /*
  ** Convert OP_Column opcodes to OP_Copy in previously generated code.
  **
  ** This routine runs over generated VDBE code and translates OP_Column
  ** opcodes into OP_Copy when the table is being accessed via co-routine 
  ** instead of via table lookup.
  **
  ** If the iAutoidxCur is not zero, then any OP_Rowid instructions on
  ** cursor iTabCur are transformed into OP_Sequence opcode for the
  ** iAutoidxCur cursor, in order to generate unique rowids for the
  ** automatic index being generated.
  */
  void translateColumnToCopy(
    Parse *pParse,      /* Parsing context */
    int iStart,         /* Translate from this opcode to the end */
    int iTabCur,        /* OP_Column/OP_Rowid references to this table */
    int iRegister,      /* The first column is in this register */
    int iAutoidxCur     /* If non-zero, cursor of autoindex being generated */
  ){
    Vdbe *v = pParse->pVdbe;
    VdbeOp *pOp = sqlite3VdbeGetOp(v, iStart);
    int iEnd = sqlite3VdbeCurrentAddr(v);
    if( pParse->db->mallocFailed ) return;
    for(; iStart<iEnd; iStart++, pOp++){
      if( pOp->p1!=iTabCur ) continue;
      if( pOp->opcode==OP_Column ){
        pOp->opcode = OP_Copy;
        pOp->p1 = pOp->p2 + iRegister;
        pOp->p2 = pOp->p3;
        pOp->p3 = 0;
      }else if( pOp->opcode==OP_Rowid ){
        if( iAutoidxCur ){
          pOp->opcode = OP_Sequence;
          pOp->p1 = iAutoidxCur;
        }else{
          pOp->opcode = OP_Null;
          pOp->p1 = 0;
          pOp->p3 = 0;
        }
      }
    }
  }
  
  /*
  ** Two routines for printing the content of an sqlite3_index_info
  ** structure.  Used for testing and debugging only.  If neither
  ** SQLITE_TEST or SQLITE_DEBUG are defined, then these routines
  ** are no-ops.
  */
  #if !defined(SQLITE_OMIT_VIRTUALTABLE) && defined(WHERETRACE_ENABLED)
  void whereTraceIndexInfoInputs(sqlite3_index_info *p){
    int i;
    if( !sqlite3WhereTrace ) return;
    for(i=0; i<p->nConstraint; i++){
      sqlite3DebugPrintf("  constraint[%d]: col=%d termid=%d op=%d usabled=%d\n",
         i,
         p->aConstraint[i].iColumn,
         p->aConstraint[i].iTermOffset,
         p->aConstraint[i].op,
         p->aConstraint[i].usable);
    }
    for(i=0; i<p->nOrderBy; i++){
      sqlite3DebugPrintf("  orderby[%d]: col=%d desc=%d\n",
         i,
         p->aOrderBy[i].iColumn,
         p->aOrderBy[i].desc);
    }
  }
  void whereTraceIndexInfoOutputs(sqlite3_index_info *p){
    int i;
    if( !sqlite3WhereTrace ) return;
    for(i=0; i<p->nConstraint; i++){
      sqlite3DebugPrintf("  usage[%d]: argvIdx=%d omit=%d\n",
         i,
         p->aConstraintUsage[i].argvIndex,
         p->aConstraintUsage[i].omit);
    }
    sqlite3DebugPrintf("  idxNum=%d\n", p->idxNum);
    sqlite3DebugPrintf("  idxStr=%s\n", p->idxStr);
    sqlite3DebugPrintf("  orderByConsumed=%d\n", p->orderByConsumed);
    sqlite3DebugPrintf("  estimatedCost=%g\n", p->estimatedCost);
    sqlite3DebugPrintf("  estimatedRows=%lld\n", p->estimatedRows);
  }
  #else
  #define whereTraceIndexInfoInputs(A)
  #define whereTraceIndexInfoOutputs(A)
  #endif
  
  #ifndef SQLITE_OMIT_AUTOMATIC_INDEX
  /*
  ** Return TRUE if the WHERE clause term pTerm is of a form where it
  ** could be used with an index to access pSrc, assuming an appropriate
  ** index existed.
  */
  int termCanDriveIndex(
    WhereTerm *pTerm,              /* WHERE clause term to check */
    struct SrcList_item *pSrc,     /* Table we are trying to access */
    Bitmask notReady               /* Tables in outer loops of the join */
  ){
    char aff;
    if( pTerm->leftCursor!=pSrc->iCursor ) return 0;
    if( (pTerm->eOperator & (WO_EQ|WO_IS))==0 ) return 0;
    if( (pSrc->fg.jointype & JT_LEFT) 
     && !ExprHasProperty(pTerm->pExpr, EP_FromJoin)
     && (pTerm->eOperator & WO_IS)
    ){
      /* Cannot use an IS term from the WHERE clause as an index driver for
      ** the RHS of a LEFT JOIN. Such a term can only be used if it is from
      ** the ON clause.  */
      return 0;
    }
    if( (pTerm->prereqRight & notReady)!=0 ) return 0;
    if( pTerm->u.leftColumn<0 ) return 0;
    aff = pSrc->pTab->aCol[pTerm->u.leftColumn].affinity;
    if( !sqlite3IndexAffinityOk(pTerm->pExpr, aff) ) return 0;
    testcase( pTerm->pExpr->op==TK_IS );
    return 1;
  }
  #endif
  
  
  #ifndef SQLITE_OMIT_AUTOMATIC_INDEX
  /*
  ** Generate code to construct the Index object for an automatic index
  ** and to set up the WhereLevel object pLevel so that the code generator
  ** makes use of the automatic index.
  */
  void constructAutomaticIndex(
    Parse *pParse,              /* The parsing context */
    WhereClause *pWC,           /* The WHERE clause */
    struct SrcList_item *pSrc,  /* The FROM clause term to get the next index */
    Bitmask notReady,           /* Mask of cursors that are not available */
    WhereLevel *pLevel          /* Write new index here */
  ){
    int nKeyCol;                /* Number of columns in the constructed index */
    WhereTerm *pTerm;           /* A single term of the WHERE clause */
    WhereTerm *pWCEnd;          /* End of pWC->a[] */
    Index *pIdx;                /* Object describing the transient index */
    Vdbe *v;                    /* Prepared statement under construction */
    int addrInit;               /* Address of the initialization bypass jump */
    Table *pTable;              /* The table being indexed */
    int addrTop;                /* Top of the index fill loop */
    int regRecord;              /* Register holding an index record */
    int n;                      /* Column counter */
    int i;                      /* Loop counter */
    int mxBitCol;               /* Maximum column in pSrc->colUsed */
    CollSeq *pColl;             /* Collating sequence to on a column */
    WhereLoop *pLoop;           /* The Loop object */
    char *zNotUsed;             /* Extra space on the end of pIdx */
    Bitmask idxCols;            /* Bitmap of columns used for indexing */
    Bitmask extraCols;          /* Bitmap of additional columns */
    u8 sentWarning = 0;         /* True if a warnning has been issued */
    Expr *pPartial = 0;         /* Partial Index Expression */
    int iContinue = 0;          /* Jump here to skip excluded rows */
    struct SrcList_item *pTabItem;  /* FROM clause term being indexed */
    int addrCounter = 0;        /* Address where integer counter is initialized */
    int regBase;                /* Array of registers where record is assembled */
  
    /* Generate code to skip over the creation and initialization of the
    ** transient index on 2nd and subsequent iterations of the loop. */
    v = pParse->pVdbe;
    assert( v!=0 );
    addrInit = sqlite3VdbeAddOp0(v, OP_Once); VdbeCoverage(v);
  
    /* Count the number of columns that will be added to the index
    ** and used to match WHERE clause constraints */
    nKeyCol = 0;
    pTable = pSrc->pTab;
    pWCEnd = &pWC->a[pWC->nTerm];
    pLoop = pLevel->pWLoop;
    idxCols = 0;
    for(pTerm=pWC->a; pTerm<pWCEnd; pTerm++){
      Expr *pExpr = pTerm->pExpr;
      assert( !ExprHasProperty(pExpr, EP_FromJoin)    /* prereq always non-zero */
           || pExpr->iRightJoinTable!=pSrc->iCursor   /*   for the right-hand   */
           || pLoop->prereq!=0 );                     /*   table of a LEFT JOIN */
      if( pLoop->prereq==0
       && (pTerm->wtFlags & TERM_VIRTUAL)==0
       && !ExprHasProperty(pExpr, EP_FromJoin)
       && sqlite3ExprIsTableConstant(pExpr, pSrc->iCursor) ){
        pPartial = sqlite3ExprAnd(pParse, pPartial,
                                  sqlite3ExprDup(pParse->db, pExpr, 0));
      }
      if( termCanDriveIndex(pTerm, pSrc, notReady) ){
        int iCol = pTerm->u.leftColumn;
        Bitmask cMask = iCol>=BMS ? MASKBIT(BMS-1) : MASKBIT(iCol);
        testcase( iCol==BMS );
        testcase( iCol==BMS-1 );
        if( !sentWarning ){
          sqlite3_log(SQLITE_WARNING_AUTOINDEX,
              "automatic index on %s(%s)", pTable->zName,
              pTable->aCol[iCol].zName);
          sentWarning = 1;
        }
        if( (idxCols & cMask)==0 ){
          if( whereLoopResize(pParse->db, pLoop, nKeyCol+1) ){
            goto end_auto_index_create;
          }
          pLoop->aLTerm[nKeyCol++] = pTerm;
          idxCols |= cMask;
        }
      }
    }
    assert( nKeyCol>0 );
    pLoop->u.btree.nEq = pLoop->nLTerm = nKeyCol;
    pLoop->wsFlags = WHERE_COLUMN_EQ | WHERE_IDX_ONLY | WHERE_INDEXED
                       | WHERE_AUTO_INDEX;
  
    /* Count the number of additional columns needed to create a
    ** covering index.  A "covering index" is an index that contains all
    ** columns that are needed by the query.  With a covering index, the
    ** original table never needs to be accessed.  Automatic indices must
    ** be a covering index because the index will not be updated if the
    ** original table changes and the index and table cannot both be used
    ** if they go out of sync.
    */
    extraCols = pSrc->colUsed & (~idxCols | MASKBIT(BMS-1));
    mxBitCol = MIN(BMS-1,pTable->nCol);
    testcase( pTable->nCol==BMS-1 );
    testcase( pTable->nCol==BMS-2 );
    for(i=0; i<mxBitCol; i++){
      if( extraCols & MASKBIT(i) ) nKeyCol++;
    }
    if( pSrc->colUsed & MASKBIT(BMS-1) ){
      nKeyCol += pTable->nCol - BMS + 1;
    }
  
    /* Construct the Index object to describe this index */
    pIdx = sqlite3AllocateIndexObject(pParse->db, nKeyCol+1, 0, &zNotUsed);
    if( pIdx==0 ) goto end_auto_index_create;
    pLoop->u.btree.pIndex = pIdx;
    pIdx->zName = "auto-index";
    pIdx->pTable = pTable;
    n = 0;
    idxCols = 0;
    for(pTerm=pWC->a; pTerm<pWCEnd; pTerm++){
      if( termCanDriveIndex(pTerm, pSrc, notReady) ){
        int iCol = pTerm->u.leftColumn;
        Bitmask cMask = iCol>=BMS ? MASKBIT(BMS-1) : MASKBIT(iCol);
        testcase( iCol==BMS-1 );
        testcase( iCol==BMS );
        if( (idxCols & cMask)==0 ){
          Expr *pX = pTerm->pExpr;
          idxCols |= cMask;
          pIdx->aiColumn[n] = pTerm->u.leftColumn;
          pColl = sqlite3ExprCompareCollSeq(pParse, pX);
          assert( pColl!=0 || pParse->nErr>0 ); /* TH3 collate01.800 */
          pIdx->azColl[n] = pColl ? pColl->zName : sqlite3StrBINARY;
          n++;
        }
      }
    }
    assert( (u32)n==pLoop->u.btree.nEq );
  
    /* Add additional columns needed to make the automatic index into
    ** a covering index */
    for(i=0; i<mxBitCol; i++){
      if( extraCols & MASKBIT(i) ){
        pIdx->aiColumn[n] = i;
        pIdx->azColl[n] = sqlite3StrBINARY;
        n++;
      }
    }
    if( pSrc->colUsed & MASKBIT(BMS-1) ){
      for(i=BMS-1; i<pTable->nCol; i++){
        pIdx->aiColumn[n] = i;
        pIdx->azColl[n] = sqlite3StrBINARY;
        n++;
      }
    }
    assert( n==nKeyCol );
    pIdx->aiColumn[n] = XN_ROWID;
    pIdx->azColl[n] = sqlite3StrBINARY;
  
    /* Create the automatic index */
    assert( pLevel->iIdxCur>=0 );
    pLevel->iIdxCur = pParse->nTab++;
    sqlite3VdbeAddOp2(v, OP_OpenAutoindex, pLevel->iIdxCur, nKeyCol+1);
    sqlite3VdbeSetP4KeyInfo(pParse, pIdx);
    VdbeComment((v, "for %s", pTable->zName));
  
    /* Fill the automatic index with content */
    pTabItem = &pWC->pWInfo->pTabList->a[pLevel->iFrom];
    if( pTabItem->fg.viaCoroutine ){
      int regYield = pTabItem->regReturn;
      addrCounter = sqlite3VdbeAddOp2(v, OP_Integer, 0, 0);
      sqlite3VdbeAddOp3(v, OP_InitCoroutine, regYield, 0, pTabItem->addrFillSub);
      addrTop =  sqlite3VdbeAddOp1(v, OP_Yield, regYield);
      VdbeCoverage(v);
      VdbeComment((v, "next row of %s", pTabItem->pTab->zName));
    }else{
      addrTop = sqlite3VdbeAddOp1(v, OP_Rewind, pLevel->iTabCur); VdbeCoverage(v);
    }
    if( pPartial ){
      iContinue = sqlite3VdbeMakeLabel(pParse);
      sqlite3ExprIfFalse(pParse, pPartial, iContinue, SQLITE_JUMPIFNULL);
      pLoop->wsFlags |= WHERE_PARTIALIDX;
    }
    regRecord = sqlite3GetTempReg(pParse);
    regBase = sqlite3GenerateIndexKey(
        pParse, pIdx, pLevel->iTabCur, regRecord, 0, 0, 0, 0
    );
    sqlite3VdbeAddOp2(v, OP_IdxInsert, pLevel->iIdxCur, regRecord);
    sqlite3VdbeChangeP5(v, OPFLAG_USESEEKRESULT);
    if( pPartial ) sqlite3VdbeResolveLabel(v, iContinue);
    if( pTabItem->fg.viaCoroutine ){
      sqlite3VdbeChangeP2(v, addrCounter, regBase+n);
      testcase( pParse->db->mallocFailed );
      assert( pLevel->iIdxCur>0 );
      translateColumnToCopy(pParse, addrTop, pLevel->iTabCur,
                            pTabItem->regResult, pLevel->iIdxCur);
      sqlite3VdbeGoto(v, addrTop);
      pTabItem->fg.viaCoroutine = 0;
    }else{
      sqlite3VdbeAddOp2(v, OP_Next, pLevel->iTabCur, addrTop+1); VdbeCoverage(v);
      sqlite3VdbeChangeP5(v, SQLITE_STMTSTATUS_AUTOINDEX);
    }
    sqlite3VdbeJumpHere(v, addrTop);
    sqlite3ReleaseTempReg(pParse, regRecord);
    
    /* Jump here when skipping the initialization */
    sqlite3VdbeJumpHere(v, addrInit);
  
  end_auto_index_create:
    sqlite3ExprDelete(pParse->db, pPartial);
  }
  #endif /* SQLITE_OMIT_AUTOMATIC_INDEX */
  
  #ifndef SQLITE_OMIT_VIRTUALTABLE
  /*
  ** Allocate and populate an sqlite3_index_info structure. It is the 
  ** responsibility of the caller to eventually release the structure
  ** by passing the pointer returned by this function to sqlite3_free().
  */
  sqlite3_index_info *allocateIndexInfo(
    Parse *pParse,                  /* The parsing context */
    WhereClause *pWC,               /* The WHERE clause being analyzed */
    Bitmask mUnusable,              /* Ignore terms with these prereqs */
    struct SrcList_item *pSrc,      /* The FROM clause term that is the vtab */
    ExprList *pOrderBy,             /* The ORDER BY clause */
    u16 *pmNoOmit                   /* Mask of terms not to omit */
  ){
    int i, j;
    int nTerm;
    struct sqlite3_index_constraint *pIdxCons;
    struct sqlite3_index_orderby *pIdxOrderBy;
    struct sqlite3_index_constraint_usage *pUsage;
    struct HiddenIndexInfo *pHidden;
    WhereTerm *pTerm;
    int nOrderBy;
    sqlite3_index_info *pIdxInfo;
    u16 mNoOmit = 0;
  
    /* Count the number of possible WHERE clause constraints referring
    ** to this virtual table */
    for(i=nTerm=0, pTerm=pWC->a; i<pWC->nTerm; i++, pTerm++){
      if( pTerm->leftCursor != pSrc->iCursor ) continue;
      if( pTerm->prereqRight & mUnusable ) continue;
      assert( IsPowerOfTwo(pTerm->eOperator & ~WO_EQUIV) );
      testcase( pTerm->eOperator & WO_IN );
      testcase( pTerm->eOperator & WO_ISNULL );
      testcase( pTerm->eOperator & WO_IS );
      testcase( pTerm->eOperator & WO_ALL );
      if( (pTerm->eOperator & ~(WO_EQUIV))==0 ) continue;
      if( pTerm->wtFlags & TERM_VNULL ) continue;
      assert( pTerm->u.leftColumn>=(-1) );
      nTerm++;
    }
  
    /* If the ORDER BY clause contains only columns in the current 
    ** virtual table then allocate space for the aOrderBy part of
    ** the sqlite3_index_info structure.
    */
    nOrderBy = 0;
    if( pOrderBy ){
      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( pOrderBy->a[i].sortFlags & KEYINFO_ORDER_BIGNULL ) break;
      }
      if( i==n){
        nOrderBy = n;
      }
    }
  
    /* Allocate the sqlite3_index_info structure
    */
    pIdxInfo = sqlite3DbMallocZero(pParse->db, sizeof(*pIdxInfo)
                             + (sizeof(*pIdxCons) + sizeof(*pUsage))*nTerm
                             + sizeof(*pIdxOrderBy)*nOrderBy + sizeof(*pHidden) );
    if( pIdxInfo==0 ){
      sqlite3ErrorMsg(pParse, "out of memory");
      return 0;
    }
    pHidden = (struct HiddenIndexInfo*)&pIdxInfo[1];
    pIdxCons = (struct sqlite3_index_constraint*)&pHidden[1];
    pIdxOrderBy = (struct sqlite3_index_orderby*)&pIdxCons[nTerm];
    pUsage = (struct sqlite3_index_constraint_usage*)&pIdxOrderBy[nOrderBy];
    pIdxInfo->nOrderBy = nOrderBy;
    pIdxInfo->aConstraint = pIdxCons;
    pIdxInfo->aOrderBy = pIdxOrderBy;
    pIdxInfo->aConstraintUsage = pUsage;
    pHidden->pWC = pWC;
    pHidden->pParse = pParse;
    for(i=j=0, pTerm=pWC->a; i<pWC->nTerm; i++, pTerm++){
      u16 op;
      if( pTerm->leftCursor != pSrc->iCursor ) continue;
      if( pTerm->prereqRight & mUnusable ) continue;
      assert( IsPowerOfTwo(pTerm->eOperator & ~WO_EQUIV) );
      testcase( pTerm->eOperator & WO_IN );
      testcase( pTerm->eOperator & WO_IS );
      testcase( pTerm->eOperator & WO_ISNULL );
      testcase( pTerm->eOperator & WO_ALL );
      if( (pTerm->eOperator & ~(WO_EQUIV))==0 ) continue;
      if( pTerm->wtFlags & TERM_VNULL ) continue;
  
      /* tag-20191211-002: WHERE-clause constraints are not useful to the
      ** right-hand table of a LEFT JOIN.  See tag-20191211-001 for the
      ** equivalent restriction for ordinary tables. */
      if( (pSrc->fg.jointype & JT_LEFT)!=0
       && !ExprHasProperty(pTerm->pExpr, EP_FromJoin)
      ){
        continue;
      }
      assert( pTerm->u.leftColumn>=(-1) );
      pIdxCons[j].iColumn = pTerm->u.leftColumn;
      pIdxCons[j].iTermOffset = i;
      op = pTerm->eOperator & WO_ALL;
      if( op==WO_IN ) op = WO_EQ;
      if( op==WO_AUX ){
        pIdxCons[j].op = pTerm->eMatchOp;
      }else if( op & (WO_ISNULL|WO_IS) ){
        if( op==WO_ISNULL ){
          pIdxCons[j].op = SQLITE_INDEX_CONSTRAINT_ISNULL;
        }else{
          pIdxCons[j].op = SQLITE_INDEX_CONSTRAINT_IS;
        }
      }else{
        pIdxCons[j].op = (u8)op;
        /* The direct assignment in the previous line is possible only because
        ** the WO_ and SQLITE_INDEX_CONSTRAINT_ codes are identical.  The
        ** following asserts verify this fact. */
        assert( WO_EQ==SQLITE_INDEX_CONSTRAINT_EQ );
        assert( WO_LT==SQLITE_INDEX_CONSTRAINT_LT );
        assert( WO_LE==SQLITE_INDEX_CONSTRAINT_LE );
        assert( WO_GT==SQLITE_INDEX_CONSTRAINT_GT );
        assert( WO_GE==SQLITE_INDEX_CONSTRAINT_GE );
        assert( pTerm->eOperator&(WO_IN|WO_EQ|WO_LT|WO_LE|WO_GT|WO_GE|WO_AUX) );
  
        if( op & (WO_LT|WO_LE|WO_GT|WO_GE)
         && sqlite3ExprIsVector(pTerm->pExpr->pRight) 
        ){
          testcase( j!=i );
          if( j<16 ) mNoOmit |= (1 << j);
          if( op==WO_LT ) pIdxCons[j].op = WO_LE;
          if( op==WO_GT ) pIdxCons[j].op = WO_GE;
        }
      }
  
      j++;
    }
    pIdxInfo->nConstraint = j;
    for(i=0; i<nOrderBy; i++){
      Expr *pExpr = pOrderBy->a[i].pExpr;
      pIdxOrderBy[i].iColumn = pExpr->iColumn;
      pIdxOrderBy[i].desc = pOrderBy->a[i].sortFlags & KEYINFO_ORDER_DESC;
    }
  
    *pmNoOmit = mNoOmit;
    return pIdxInfo;
  }
  
  /*
  ** The table object reference passed as the second argument to this function
  ** must represent a virtual table. This function invokes the xBestIndex()
  ** method of the virtual table with the sqlite3_index_info object that
  ** comes in as the 3rd argument to this function.
  **
  ** If an error occurs, pParse is populated with an error message and an
  ** appropriate error code is returned.  A return of SQLITE_CONSTRAINT from
  ** xBestIndex is not considered an error.  SQLITE_CONSTRAINT indicates that
  ** the current configuration of "unusable" flags in sqlite3_index_info can
  ** not result in a valid plan.
  **
  ** Whether or not an error is returned, it is the responsibility of the
  ** caller to eventually free p->idxStr if p->needToFreeIdxStr indicates
  ** that this is required.
  */
  int vtabBestIndex(Parse *pParse, Table *pTab, sqlite3_index_info *p){
    sqlite3_vtab *pVtab = sqlite3GetVTable(pParse->db, pTab)->pVtab;
    int rc;
  
    whereTraceIndexInfoInputs(p);
    rc = pVtab->pModule->xBestIndex(pVtab, p);
    whereTraceIndexInfoOutputs(p);
  
    if( rc!=SQLITE_OK && rc!=SQLITE_CONSTRAINT ){
      if( rc==SQLITE_NOMEM ){
        sqlite3OomFault(pParse->db);
      }else if( !pVtab->zErrMsg ){
        sqlite3ErrorMsg(pParse, "%s", sqlite3ErrStr(rc));
      }else{
        sqlite3ErrorMsg(pParse, "%s", pVtab->zErrMsg);
      }
    }
    sqlite3_free(pVtab->zErrMsg);
    pVtab->zErrMsg = 0;
    return rc;
  }
  #endif /* !defined(SQLITE_OMIT_VIRTUALTABLE) */
  
  #ifdef SQLITE_ENABLE_STAT4
  /*
  ** Estimate the location of a particular key among all keys in an
  ** index.  Store the results in aStat as follows:
  **
  **    aStat[0]      Est. number of rows less than pRec
  **    aStat[1]      Est. number of rows equal to pRec
  **
  ** Return the index of the sample that is the smallest sample that
  ** is greater than or equal to pRec. Note that this index is not an index
  ** into the aSample[] array - it is an index into a virtual set of samples
  ** based on the contents of aSample[] and the number of fields in record 
  ** pRec. 
  */
  int whereKeyStats(
    Parse *pParse,              /* Database connection */
    Index *pIdx,                /* Index to consider domain of */
    UnpackedRecord *pRec,       /* Vector of values to consider */
    int roundUp,                /* Round up if true.  Round down if false */
    tRowcnt *aStat              /* OUT: stats written here */
  ){
    IndexSample *aSample = pIdx->aSample;
    int iCol;                   /* Index of required stats in anEq[] etc. */
    int i;                      /* Index of first sample >= pRec */
    int iSample;                /* Smallest sample larger than or equal to pRec */
    int iMin = 0;               /* Smallest sample not yet tested */
    int iTest;                  /* Next sample to test */
    int res;                    /* Result of comparison operation */
    int nField;                 /* Number of fields in pRec */
    tRowcnt iLower = 0;         /* anLt[] + anEq[] of largest sample pRec is > */
  
  #ifndef SQLITE_DEBUG
    UNUSED_PARAMETER( pParse );
  #endif
    assert( pRec!=0 );
    assert( pIdx->nSample>0 );
    assert( pRec->nField>0 && pRec->nField<=pIdx->nSampleCol );
  
    /* Do a binary search to find the first sample greater than or equal
    ** to pRec. If pRec contains a single field, the set of samples to search
    ** is simply the aSample[] array. If the samples in aSample[] contain more
    ** than one fields, all fields following the first are ignored.
    **
    ** If pRec contains N fields, where N is more than one, then as well as the
    ** samples in aSample[] (truncated to N fields), the search also has to
    ** consider prefixes of those samples. For example, if the set of samples
    ** in aSample is:
    **
    **     aSample[0] = (a, 5) 
    **     aSample[1] = (a, 10) 
    **     aSample[2] = (b, 5) 
    **     aSample[3] = (c, 100) 
    **     aSample[4] = (c, 105)
    **
    ** Then the search space should ideally be the samples above and the 
    ** unique prefixes [a], [b] and [c]. But since that is hard to organize, 
    ** the code actually searches this set:
    **
    **     0: (a) 
    **     1: (a, 5) 
    **     2: (a, 10) 
    **     3: (a, 10) 
    **     4: (b) 
    **     5: (b, 5) 
    **     6: (c) 
    **     7: (c, 100) 
    **     8: (c, 105)
    **     9: (c, 105)
    **
    ** For each sample in the aSample[] array, N samples are present in the
    ** effective sample array. In the above, samples 0 and 1 are based on 
    ** sample aSample[0]. Samples 2 and 3 on aSample[1] etc.
    **
    ** Often, sample i of each block of N effective samples has (i+1) fields.
    ** Except, each sample may be extended to ensure that it is greater than or
    ** equal to the previous sample in the array. For example, in the above, 
    ** sample 2 is the first sample of a block of N samples, so at first it 
    ** appears that it should be 1 field in size. However, that would make it 
    ** smaller than sample 1, so the binary search would not work. As a result, 
    ** it is extended to two fields. The duplicates that this creates do not 
    ** cause any problems.
    */
    nField = pRec->nField;
    iCol = 0;
    iSample = pIdx->nSample * nField;
    do{
      int iSamp;                    /* Index in aSample[] of test sample */
      int n;                        /* Number of fields in test sample */
  
      iTest = (iMin+iSample)/2;
      iSamp = iTest / nField;
      if( iSamp>0 ){
        /* The proposed effective sample is a prefix of sample aSample[iSamp].
        ** Specifically, the shortest prefix of at least (1 + iTest%nField) 
        ** fields that is greater than the previous effective sample.  */
        for(n=(iTest % nField) + 1; n<nField; n++){
          if( aSample[iSamp-1].anLt[n-1]!=aSample[iSamp].anLt[n-1] ) break;
        }
      }else{
        n = iTest + 1;
      }
  
      pRec->nField = n;
      res = sqlite3VdbeRecordCompare(aSample[iSamp].n, aSample[iSamp].p, pRec);
      if( res<0 ){
        iLower = aSample[iSamp].anLt[n-1] + aSample[iSamp].anEq[n-1];
        iMin = iTest+1;
      }else if( res==0 && n<nField ){
        iLower = aSample[iSamp].anLt[n-1];
        iMin = iTest+1;
        res = -1;
      }else{
        iSample = iTest;
        iCol = n-1;
      }
    }while( res && iMin<iSample );
    i = iSample / nField;
  
  #ifdef SQLITE_DEBUG
    /* The following assert statements check that the binary search code
    ** above found the right answer. This block serves no purpose other
    ** than to invoke the asserts.  */
    if( pParse->db->mallocFailed==0 ){
      if( res==0 ){
        /* If (res==0) is true, then pRec must be equal to sample i. */
        assert( i<pIdx->nSample );
        assert( iCol==nField-1 );
        pRec->nField = nField;
        assert( 0==sqlite3VdbeRecordCompare(aSample[i].n, aSample[i].p, pRec) 
             || pParse->db->mallocFailed 
        );
      }else{
        /* Unless i==pIdx->nSample, indicating that pRec is larger than
        ** all samples in the aSample[] array, pRec must be smaller than the
        ** (iCol+1) field prefix of sample i.  */
        assert( i<=pIdx->nSample && i>=0 );
        pRec->nField = iCol+1;
        assert( i==pIdx->nSample 
             || sqlite3VdbeRecordCompare(aSample[i].n, aSample[i].p, pRec)>0
             || pParse->db->mallocFailed );
  
        /* if i==0 and iCol==0, then record pRec is smaller than all samples
        ** in the aSample[] array. Otherwise, if (iCol>0) then pRec must
        ** be greater than or equal to the (iCol) field prefix of sample i.
        ** If (i>0), then pRec must also be greater than sample (i-1).  */
        if( iCol>0 ){
          pRec->nField = iCol;
          assert( sqlite3VdbeRecordCompare(aSample[i].n, aSample[i].p, pRec)<=0
               || pParse->db->mallocFailed );
        }
        if( i>0 ){
          pRec->nField = nField;
          assert( sqlite3VdbeRecordCompare(aSample[i-1].n, aSample[i-1].p, pRec)<0
               || pParse->db->mallocFailed );
        }
      }
    }
  #endif /* ifdef SQLITE_DEBUG */
  
    if( res==0 ){
      /* Record pRec is equal to sample i */
      assert( iCol==nField-1 );
      aStat[0] = aSample[i].anLt[iCol];
      aStat[1] = aSample[i].anEq[iCol];
    }else{
      /* At this point, the (iCol+1) field prefix of aSample[i] is the first 
      ** sample that is greater than pRec. Or, if i==pIdx->nSample then pRec
      ** is larger than all samples in the array. */
      tRowcnt iUpper, iGap;
      if( i>=pIdx->nSample ){
        iUpper = sqlite3LogEstToInt(pIdx->aiRowLogEst[0]);
      }else{
        iUpper = aSample[i].anLt[iCol];
      }
  
      if( iLower>=iUpper ){
        iGap = 0;
      }else{
        iGap = iUpper - iLower;
      }
      if( roundUp ){
        iGap = (iGap*2)/3;
      }else{
        iGap = iGap/3;
      }
      aStat[0] = iLower + iGap;
      aStat[1] = pIdx->aAvgEq[nField-1];
    }
  
    /* Restore the pRec->nField value before returning.  */
    pRec->nField = nField;
    return i;
  }
  #endif /* SQLITE_ENABLE_STAT4 */
  
  /*
  ** If it is not NULL, pTerm is a term that provides an upper or lower
  ** bound on a range scan. Without considering pTerm, it is estimated 
  ** that the scan will visit nNew rows. This function returns the number
  ** estimated to be visited after taking pTerm into account.
  **
  ** If the user explicitly specified a likelihood() value for this term,
  ** then the return value is the likelihood multiplied by the number of
  ** input rows. Otherwise, this function assumes that an "IS NOT NULL" term
  ** has a likelihood of 0.50, and any other term a likelihood of 0.25.
  */
  LogEst whereRangeAdjust(WhereTerm *pTerm, LogEst nNew){
    LogEst nRet = nNew;
    if( pTerm ){
      if( pTerm->truthProb<=0 ){
        nRet += pTerm->truthProb;
      }else if( (pTerm->wtFlags & TERM_VNULL)==0 ){
        nRet -= 20;        assert( 20==sqlite3LogEst(4) );
      }
    }
    return nRet;
  }
  
  
  #ifdef SQLITE_ENABLE_STAT4
  /*
  ** Return the affinity for a single column of an index.
  */
  char sqlite3IndexColumnAffinity(sqlite3 *db, Index *pIdx, int iCol){
    assert( iCol>=0 && iCol<pIdx->nColumn );
    if( !pIdx->zColAff ){
      if( sqlite3IndexAffinityStr(db, pIdx)==0 ) return SQLITE_AFF_BLOB;
    }
    assert( pIdx->zColAff[iCol]!=0 );
    return pIdx->zColAff[iCol];
  }
  #endif
  
  
  #ifdef SQLITE_ENABLE_STAT4
  /* 
  ** This function is called to estimate the number of rows visited by a
  ** range-scan on a skip-scan index. For example:
  **
  **   CREATE INDEX i1 ON t1(a, b, c);
  **   SELECT * FROM t1 WHERE a=? AND c BETWEEN ? AND ?;
  **
  ** Value pLoop->nOut is currently set to the estimated number of rows 
  ** visited for scanning (a=? AND b=?). This function reduces that estimate 
  ** by some factor to account for the (c BETWEEN ? AND ?) expression based
  ** on the stat4 data for the index. this scan will be peformed multiple 
  ** times (once for each (a,b) combination that matches a=?) is dealt with 
  ** by the caller.
  **
  ** It does this by scanning through all stat4 samples, comparing values
  ** extracted from pLower and pUpper with the corresponding column in each
  ** sample. If L and U are the number of samples found to be less than or
  ** equal to the values extracted from pLower and pUpper respectively, and
  ** N is the total number of samples, the pLoop->nOut value is adjusted
  ** as follows:
  **
  **   nOut = nOut * ( min(U - L, 1) / N )
  **
  ** If pLower is NULL, or a value cannot be extracted from the term, L is
  ** set to zero. If pUpper is NULL, or a value cannot be extracted from it,
  ** U is set to N.
  **
  ** Normally, this function sets *pbDone to 1 before returning. However,
  ** if no value can be extracted from either pLower or pUpper (and so the
  ** estimate of the number of rows delivered remains unchanged), *pbDone
  ** is left as is.
  **
  ** If an error occurs, an SQLite error code is returned. Otherwise, 
  ** SQLITE_OK.
  */
  int whereRangeSkipScanEst(
    Parse *pParse,       /* Parsing & code generating context */
    WhereTerm *pLower,   /* Lower bound on the range. ex: "x>123" Might be NULL */
    WhereTerm *pUpper,   /* Upper bound on the range. ex: "x<455" Might be NULL */
    WhereLoop *pLoop,    /* Update the .nOut value of this loop */
    int *pbDone          /* Set to true if at least one expr. value extracted */
  ){
    Index *p = pLoop->u.btree.pIndex;
    int nEq = pLoop->u.btree.nEq;
    sqlite3 *db = pParse->db;
    int nLower = -1;
    int nUpper = p->nSample+1;
    int rc = SQLITE_OK;
    u8 aff = sqlite3IndexColumnAffinity(db, p, nEq);
    CollSeq *pColl;
    
    sqlite3_value *p1 = 0;          /* Value extracted from pLower */
    sqlite3_value *p2 = 0;          /* Value extracted from pUpper */
    sqlite3_value *pVal = 0;        /* Value extracted from record */
  
    pColl = sqlite3LocateCollSeq(pParse, p->azColl[nEq]);
    if( pLower ){
      rc = sqlite3Stat4ValueFromExpr(pParse, pLower->pExpr->pRight, aff, &p1);
      nLower = 0;
    }
    if( pUpper && rc==SQLITE_OK ){
      rc = sqlite3Stat4ValueFromExpr(pParse, pUpper->pExpr->pRight, aff, &p2);
      nUpper = p2 ? 0 : p->nSample;
    }
  
    if( p1 || p2 ){
      int i;
      int nDiff;
      for(i=0; rc==SQLITE_OK && i<p->nSample; i++){
        rc = sqlite3Stat4Column(db, p->aSample[i].p, p->aSample[i].n, nEq, &pVal);
        if( rc==SQLITE_OK && p1 ){
          int res = sqlite3MemCompare(p1, pVal, pColl);
          if( res>=0 ) nLower++;
        }
        if( rc==SQLITE_OK && p2 ){
          int res = sqlite3MemCompare(p2, pVal, pColl);
          if( res>=0 ) nUpper++;
        }
      }
      nDiff = (nUpper - nLower);
      if( nDiff<=0 ) nDiff = 1;
  
      /* If there is both an upper and lower bound specified, and the 
      ** comparisons indicate that they are close together, use the fallback
      ** method (assume that the scan visits 1/64 of the rows) for estimating
      ** the number of rows visited. Otherwise, estimate the number of rows
      ** using the method described in the header comment for this function. */
      if( nDiff!=1 || pUpper==0 || pLower==0 ){
        int nAdjust = (sqlite3LogEst(p->nSample) - sqlite3LogEst(nDiff));
        pLoop->nOut -= nAdjust;
        *pbDone = 1;
        WHERETRACE(0x10, ("range skip-scan regions: %u..%u  adjust=%d est=%d\n",
                             nLower, nUpper, nAdjust*-1, pLoop->nOut));
      }
  
    }else{
      assert( *pbDone==0 );
    }
  
    sqlite3ValueFree(p1);
    sqlite3ValueFree(p2);
    sqlite3ValueFree(pVal);
  
    return rc;
  }
  #endif /* SQLITE_ENABLE_STAT4 */
  
  /*
  ** This function is used to estimate the number of rows that will be visited
  ** by scanning an index for a range of values. The range may have an upper
  ** bound, a lower bound, or both. The WHERE clause terms that set the upper
  ** and lower bounds are represented by pLower and pUpper respectively. For
  ** example, assuming that index p is on t1(a):
  **
  **   ... FROM t1 WHERE a > ? AND a < ? ...
  **                    |_____|   |_____|
  **                       |         |
  **                     pLower    pUpper
  **
  ** If either of the upper or lower bound is not present, then NULL is passed in
  ** place of the corresponding WhereTerm.
  **
  ** The value in (pBuilder->pNew->u.btree.nEq) is the number of the index
  ** column subject to the range constraint. Or, equivalently, the number of
  ** equality constraints optimized by the proposed index scan. For example,
  ** assuming index p is on t1(a, b), and the SQL query is:
  **
  **   ... FROM t1 WHERE a = ? AND b > ? AND b < ? ...
  **
  ** then nEq is set to 1 (as the range restricted column, b, is the second 
  ** left-most column of the index). Or, if the query is:
  **
  **   ... FROM t1 WHERE a > ? AND a < ? ...
  **
  ** then nEq is set to 0.
  **
  ** When this function is called, *pnOut is set to the sqlite3LogEst() of the
  ** number of rows that the index scan is expected to visit without 
  ** considering the range constraints. If nEq is 0, then *pnOut is the number of 
  ** rows in the index. Assuming no error occurs, *pnOut is adjusted (reduced)
  ** to account for the range constraints pLower and pUpper.
  ** 
  ** In the absence of sqlite_stat4 ANALYZE data, or if such data cannot be
  ** used, a single range inequality reduces the search space by a factor of 4. 
  ** and a pair of constraints (x>? AND x<?) reduces the expected number of
  ** rows visited by a factor of 64.
  */
  int whereRangeScanEst(
    Parse *pParse,       /* Parsing & code generating context */
    WhereLoopBuilder *pBuilder,
    WhereTerm *pLower,   /* Lower bound on the range. ex: "x>123" Might be NULL */
    WhereTerm *pUpper,   /* Upper bound on the range. ex: "x<455" Might be NULL */
    WhereLoop *pLoop     /* Modify the .nOut and maybe .rRun fields */
  ){
    int rc = SQLITE_OK;
    int nOut = pLoop->nOut;
    LogEst nNew;
  
  #ifdef SQLITE_ENABLE_STAT4
    Index *p = pLoop->u.btree.pIndex;
    int nEq = pLoop->u.btree.nEq;
  
    if( p->nSample>0 && ALWAYS(nEq<p->nSampleCol)
     && OptimizationEnabled(pParse->db, SQLITE_Stat4)
    ){
      if( nEq==pBuilder->nRecValid ){
        UnpackedRecord *pRec = pBuilder->pRec;
        tRowcnt a[2];
        int nBtm = pLoop->u.btree.nBtm;
        int nTop = pLoop->u.btree.nTop;
  
        /* Variable iLower will be set to the estimate of the number of rows in 
        ** the index that are less than the lower bound of the range query. The
        ** lower bound being the concatenation of $P and $L, where $P is the
        ** key-prefix formed by the nEq values matched against the nEq left-most
        ** columns of the index, and $L is the value in pLower.
        **
        ** Or, if pLower is NULL or $L cannot be extracted from it (because it
        ** is not a simple variable or literal value), the lower bound of the
        ** range is $P. Due to a quirk in the way whereKeyStats() works, even
        ** if $L is available, whereKeyStats() is called for both ($P) and 
        ** ($P:$L) and the larger of the two returned values is used.
        **
        ** Similarly, iUpper is to be set to the estimate of the number of rows
        ** less than the upper bound of the range query. Where the upper bound
        ** is either ($P) or ($P:$U). Again, even if $U is available, both values
        ** of iUpper are requested of whereKeyStats() and the smaller used.
        **
        ** The number of rows between the two bounds is then just iUpper-iLower.
        */
        tRowcnt iLower;     /* Rows less than the lower bound */
        tRowcnt iUpper;     /* Rows less than the upper bound */
        int iLwrIdx = -2;   /* aSample[] for the lower bound */
        int iUprIdx = -1;   /* aSample[] for the upper bound */
  
        if( pRec ){
          testcase( pRec->nField!=pBuilder->nRecValid );
          pRec->nField = pBuilder->nRecValid;
        }
        /* Determine iLower and iUpper using ($P) only. */
        if( nEq==0 ){
          iLower = 0;
          iUpper = p->nRowEst0;
        }else{
          /* Note: this call could be optimized away - since the same values must 
          ** have been requested when testing key $P in whereEqualScanEst().  */
          whereKeyStats(pParse, p, pRec, 0, a);
          iLower = a[0];
          iUpper = a[0] + a[1];
        }
  
        assert( pLower==0 || (pLower->eOperator & (WO_GT|WO_GE))!=0 );
        assert( pUpper==0 || (pUpper->eOperator & (WO_LT|WO_LE))!=0 );
        assert( p->aSortOrder!=0 );
        if( p->aSortOrder[nEq] ){
          /* The roles of pLower and pUpper are swapped for a DESC index */
          SWAP(WhereTerm*, pLower, pUpper);
          SWAP(int, nBtm, nTop);
        }
  
        /* If possible, improve on the iLower estimate using ($P:$L). */
        if( pLower ){
          int n;                    /* Values extracted from pExpr */
          Expr *pExpr = pLower->pExpr->pRight;
          rc = sqlite3Stat4ProbeSetValue(pParse, p, &pRec, pExpr, nBtm, nEq, &n);
          if( rc==SQLITE_OK && n ){
            tRowcnt iNew;
            u16 mask = WO_GT|WO_LE;
            if( sqlite3ExprVectorSize(pExpr)>n ) mask = (WO_LE|WO_LT);
            iLwrIdx = whereKeyStats(pParse, p, pRec, 0, a);
            iNew = a[0] + ((pLower->eOperator & mask) ? a[1] : 0);
            if( iNew>iLower ) iLower = iNew;
            nOut--;
            pLower = 0;
          }
        }
  
        /* If possible, improve on the iUpper estimate using ($P:$U). */
        if( pUpper ){
          int n;                    /* Values extracted from pExpr */
          Expr *pExpr = pUpper->pExpr->pRight;
          rc = sqlite3Stat4ProbeSetValue(pParse, p, &pRec, pExpr, nTop, nEq, &n);
          if( rc==SQLITE_OK && n ){
            tRowcnt iNew;
            u16 mask = WO_GT|WO_LE;
            if( sqlite3ExprVectorSize(pExpr)>n ) mask = (WO_LE|WO_LT);
            iUprIdx = whereKeyStats(pParse, p, pRec, 1, a);
            iNew = a[0] + ((pUpper->eOperator & mask) ? a[1] : 0);
            if( iNew<iUpper ) iUpper = iNew;
            nOut--;
            pUpper = 0;
          }
        }
  
        pBuilder->pRec = pRec;
        if( rc==SQLITE_OK ){
          if( iUpper>iLower ){
            nNew = sqlite3LogEst(iUpper - iLower);
            /* TUNING:  If both iUpper and iLower are derived from the same
            ** sample, then assume they are 4x more selective.  This brings
            ** the estimated selectivity more in line with what it would be
            ** if estimated without the use of STAT4 tables. */
            if( iLwrIdx==iUprIdx ) nNew -= 20;  assert( 20==sqlite3LogEst(4) );
          }else{
            nNew = 10;        assert( 10==sqlite3LogEst(2) );
          }
          if( nNew<nOut ){
            nOut = nNew;
          }
          WHERETRACE(0x10, ("STAT4 range scan: %u..%u  est=%d\n",
                             (u32)iLower, (u32)iUpper, nOut));
        }
      }else{
        int bDone = 0;
        rc = whereRangeSkipScanEst(pParse, pLower, pUpper, pLoop, &bDone);
        if( bDone ) return rc;
      }
    }
  #else
    UNUSED_PARAMETER(pParse);
    UNUSED_PARAMETER(pBuilder);
    assert( pLower || pUpper );
  #endif
    assert( pUpper==0 || (pUpper->wtFlags & TERM_VNULL)==0 );
    nNew = whereRangeAdjust(pLower, nOut);
    nNew = whereRangeAdjust(pUpper, nNew);
  
    /* TUNING: If there is both an upper and lower limit and neither limit
    ** has an application-defined likelihood(), assume the range is
    ** reduced by an additional 75%. This means that, by default, an open-ended
    ** range query (e.g. col > ?) is assumed to match 1/4 of the rows in the
    ** index. While a closed range (e.g. col BETWEEN ? AND ?) is estimated to
    ** match 1/64 of the index. */ 
    if( pLower && pLower->truthProb>0 && pUpper && pUpper->truthProb>0 ){
      nNew -= 20;
    }
  
    nOut -= (pLower!=0) + (pUpper!=0);
    if( nNew<10 ) nNew = 10;
    if( nNew<nOut ) nOut = nNew;
  #if defined(WHERETRACE_ENABLED)
    if( pLoop->nOut>nOut ){
      WHERETRACE(0x10,("Range scan lowers nOut from %d to %d\n",
                      pLoop->nOut, nOut));
    }
  #endif
    pLoop->nOut = (LogEst)nOut;
    return rc;
  }
  
  #ifdef SQLITE_ENABLE_STAT4
  /*
  ** Estimate the number of rows that will be returned based on
  ** an equality constraint x=VALUE and where that VALUE occurs in
  ** the histogram data.  This only works when x is the left-most
  ** column of an index and sqlite_stat4 histogram data is available
  ** for that index.  When pExpr==NULL that means the constraint is
  ** "x IS NULL" instead of "x=VALUE".
  **
  ** Write the estimated row count into *pnRow and return SQLITE_OK. 
  ** If unable to make an estimate, leave *pnRow unchanged and return
  ** non-zero.
  **
  ** This routine can fail if it is unable to load a collating sequence
  ** required for string comparison, or if unable to allocate memory
  ** for a UTF conversion required for comparison.  The error is stored
  ** in the pParse structure.
  */
  int whereEqualScanEst(
    Parse *pParse,       /* Parsing & code generating context */
    WhereLoopBuilder *pBuilder,
    Expr *pExpr,         /* Expression for VALUE in the x=VALUE constraint */
    tRowcnt *pnRow       /* Write the revised row estimate here */
  ){
    Index *p = pBuilder->pNew->u.btree.pIndex;
    int nEq = pBuilder->pNew->u.btree.nEq;
    UnpackedRecord *pRec = pBuilder->pRec;
    int rc;                   /* Subfunction return code */
    tRowcnt a[2];             /* Statistics */
    int bOk;
  
    assert( nEq>=1 );
    assert( nEq<=p->nColumn );
    assert( p->aSample!=0 );
    assert( p->nSample>0 );
    assert( pBuilder->nRecValid<nEq );
  
    /* If values are not available for all fields of the index to the left
    ** of this one, no estimate can be made. Return SQLITE_NOTFOUND. */
    if( pBuilder->nRecValid<(nEq-1) ){
      return SQLITE_NOTFOUND;
    }
  
    /* This is an optimization only. The call to sqlite3Stat4ProbeSetValue()
    ** below would return the same value.  */
    if( nEq>=p->nColumn ){
      *pnRow = 1;
      return SQLITE_OK;
    }
  
    rc = sqlite3Stat4ProbeSetValue(pParse, p, &pRec, pExpr, 1, nEq-1, &bOk);
    pBuilder->pRec = pRec;
    if( rc!=SQLITE_OK ) return rc;
    if( bOk==0 ) return SQLITE_NOTFOUND;
    pBuilder->nRecValid = nEq;
  
    whereKeyStats(pParse, p, pRec, 0, a);
    WHERETRACE(0x10,("equality scan regions %s(%d): %d\n",
                     p->zName, nEq-1, (int)a[1]));
    *pnRow = a[1];
    
    return rc;
  }
  #endif /* SQLITE_ENABLE_STAT4 */
  
  #ifdef SQLITE_ENABLE_STAT4
  /*
  ** Estimate the number of rows that will be returned based on
  ** an IN constraint where the right-hand side of the IN operator
  ** is a list of values.  Example:
  **
  **        WHERE x IN (1,2,3,4)
  **
  ** Write the estimated row count into *pnRow and return SQLITE_OK. 
  ** If unable to make an estimate, leave *pnRow unchanged and return
  ** non-zero.
  **
  ** This routine can fail if it is unable to load a collating sequence
  ** required for string comparison, or if unable to allocate memory
  ** for a UTF conversion required for comparison.  The error is stored
  ** in the pParse structure.
  */
  int whereInScanEst(
    Parse *pParse,       /* Parsing & code generating context */
    WhereLoopBuilder *pBuilder,
    ExprList *pList,     /* The value list on the RHS of "x IN (v1,v2,v3,...)" */
    tRowcnt *pnRow       /* Write the revised row estimate here */
  ){
    Index *p = pBuilder->pNew->u.btree.pIndex;
    i64 nRow0 = sqlite3LogEstToInt(p->aiRowLogEst[0]);
    int nRecValid = pBuilder->nRecValid;
    int rc = SQLITE_OK;     /* Subfunction return code */
    tRowcnt nEst;           /* Number of rows for a single term */
    tRowcnt nRowEst = 0;    /* New estimate of the number of rows */
    int i;                  /* Loop counter */
  
    assert( p->aSample!=0 );
    for(i=0; rc==SQLITE_OK && i<pList->nExpr; i++){
      nEst = nRow0;
      rc = whereEqualScanEst(pParse, pBuilder, pList->a[i].pExpr, &nEst);
      nRowEst += nEst;
      pBuilder->nRecValid = nRecValid;
    }
  
    if( rc==SQLITE_OK ){
      if( nRowEst > nRow0 ) nRowEst = nRow0;
      *pnRow = nRowEst;
      WHERETRACE(0x10,("IN row estimate: est=%d\n", nRowEst));
    }
    assert( pBuilder->nRecValid==nRecValid );
    return rc;
  }
  #endif /* SQLITE_ENABLE_STAT4 */
  
  
  #ifdef WHERETRACE_ENABLED
  /*
  ** Print the content of a WhereTerm object
  */
  void sqlite3WhereTermPrint(WhereTerm *pTerm, int iTerm){
    if( pTerm==0 ){
      sqlite3DebugPrintf("TERM-%-3d NULL\n", iTerm);
    }else{
      char zType[8];
      char zLeft[50];
      memcpy(zType, "....", 5);
      if( pTerm->wtFlags & TERM_VIRTUAL ) zType[0] = 'V';
      if( pTerm->eOperator & WO_EQUIV  ) zType[1] = 'E';
      if( ExprHasProperty(pTerm->pExpr, EP_FromJoin) ) zType[2] = 'L';
      if( pTerm->wtFlags & TERM_CODED  ) zType[3] = 'C';
      if( pTerm->eOperator & WO_SINGLE ){
        sqlite3_snprintf(sizeof(zLeft),zLeft,"left={%d:%d}",
                         pTerm->leftCursor, pTerm->u.leftColumn);
      }else if( (pTerm->eOperator & WO_OR)!=0 && pTerm->u.pOrInfo!=0 ){
        sqlite3_snprintf(sizeof(zLeft),zLeft,"indexable=0x%lld", 
                         pTerm->u.pOrInfo->indexable);
      }else{
        sqlite3_snprintf(sizeof(zLeft),zLeft,"left=%d", pTerm->leftCursor);
      }
      sqlite3DebugPrintf(
         "TERM-%-3d %p %s %-12s op=%03x wtFlags=%04x",
         iTerm, pTerm, zType, zLeft, pTerm->eOperator, pTerm->wtFlags);
      /* The 0x10000 .wheretrace flag causes extra information to be
      ** shown about each Term */
      if( sqlite3WhereTrace & 0x10000 ){
        sqlite3DebugPrintf(" prob=%-3d prereq=%llx,%llx",
          pTerm->truthProb, (u64)pTerm->prereqAll, (u64)pTerm->prereqRight);
      }
      if( pTerm->iField ){
        sqlite3DebugPrintf(" iField=%d", pTerm->iField);
      }
      if( pTerm->iParent>=0 ){
        sqlite3DebugPrintf(" iParent=%d", pTerm->iParent);
      }
      sqlite3DebugPrintf("\n");
      sqlite3TreeViewExpr(0, pTerm->pExpr, 0);
    }
  }
  #endif
  
  #ifdef WHERETRACE_ENABLED
  /*
  ** Show the complete content of a WhereClause
  */
  void sqlite3WhereClausePrint(WhereClause *pWC){
    int i;
    for(i=0; i<pWC->nTerm; i++){
      sqlite3WhereTermPrint(&pWC->a[i], i);
    }
  }
  #endif
  
  #ifdef WHERETRACE_ENABLED
  /*
  ** Print a WhereLoop object for debugging purposes
  */
  void sqlite3WhereLoopPrint(WhereLoop *p, WhereClause *pWC){
    WhereInfo *pWInfo = pWC->pWInfo;
    int nb = 1+(pWInfo->pTabList->nSrc+3)/4;
    struct SrcList_item *pItem = pWInfo->pTabList->a + p->iTab;
    Table *pTab = pItem->pTab;
    Bitmask mAll = (((Bitmask)1)<<(nb*4)) - 1;
    sqlite3DebugPrintf("%c%2d.%0*llx.%0*llx", p->cId,
                       p->iTab, nb, p->maskSelf, nb, p->prereq & mAll);
    sqlite3DebugPrintf(" %12s",
                       pItem->zAlias ? pItem->zAlias : pTab->zName);
    if( (p->wsFlags & WHERE_VIRTUALTABLE)==0 ){
      const char *zName;
      if( p->u.btree.pIndex && (zName = p->u.btree.pIndex->zName)!=0 ){
        if( strncmp(zName, "sqlite_autoindex_", 17)==0 ){
          int i = sqlite3Strlen30(zName) - 1;
          while( zName[i]!='_' ) i--;
          zName += i;
        }
        sqlite3DebugPrintf(".%-16s %2d", zName, p->u.btree.nEq);
      }else{
        sqlite3DebugPrintf("%20s","");
      }
    }else{
      char *z;
      if( p->u.vtab.idxStr ){
        z = sqlite3_mprintf("(%d,\"%s\",%#x)",
                  p->u.vtab.idxNum, p->u.vtab.idxStr, p->u.vtab.omitMask);
      }else{
        z = sqlite3_mprintf("(%d,%x)", p->u.vtab.idxNum, p->u.vtab.omitMask);
      }
      sqlite3DebugPrintf(" %-19s", z);
      sqlite3_free(z);
    }
    if( p->wsFlags & WHERE_SKIPSCAN ){
      sqlite3DebugPrintf(" f %05x %d-%d", p->wsFlags, p->nLTerm,p->nSkip);
    }else{
      sqlite3DebugPrintf(" f %05x N %d", p->wsFlags, p->nLTerm);
    }
    sqlite3DebugPrintf(" cost %d,%d,%d\n", p->rSetup, p->rRun, p->nOut);
    if( p->nLTerm && (sqlite3WhereTrace & 0x100)!=0 ){
      int i;
      for(i=0; i<p->nLTerm; i++){
        sqlite3WhereTermPrint(p->aLTerm[i], i);
      }
    }
  }
  #endif
  
  /*
  ** Convert bulk memory into a valid WhereLoop that can be passed
  ** to whereLoopClear harmlessly.
  */
  void whereLoopInit(WhereLoop *p){
    p->aLTerm = p->aLTermSpace;
    p->nLTerm = 0;
    p->nLSlot = ArraySize(p->aLTermSpace);
    p->wsFlags = 0;
  }
  
  /*
  ** Clear the WhereLoop.u union.  Leave WhereLoop.pLTerm intact.
  */
  void whereLoopClearUnion(sqlite3 *db, WhereLoop *p){
    if( p->wsFlags & (WHERE_VIRTUALTABLE|WHERE_AUTO_INDEX) ){
      if( (p->wsFlags & WHERE_VIRTUALTABLE)!=0 && p->u.vtab.needFree ){
        sqlite3_free(p->u.vtab.idxStr);
        p->u.vtab.needFree = 0;
        p->u.vtab.idxStr = 0;
      }else if( (p->wsFlags & WHERE_AUTO_INDEX)!=0 && p->u.btree.pIndex!=0 ){
        sqlite3DbFree(db, p->u.btree.pIndex->zColAff);
        sqlite3DbFreeNN(db, p->u.btree.pIndex);
        p->u.btree.pIndex = 0;
      }
    }
  }
  
  /*
  ** Deallocate internal memory used by a WhereLoop object
  */
  void whereLoopClear(sqlite3 *db, WhereLoop *p){
    if( p->aLTerm!=p->aLTermSpace ) sqlite3DbFreeNN(db, p->aLTerm);
    whereLoopClearUnion(db, p);
    whereLoopInit(p);
  }
  
  /*
  ** Increase the memory allocation for pLoop->aLTerm[] to be at least n.
  */
  int whereLoopResize(sqlite3 *db, WhereLoop *p, int n){
    WhereTerm **paNew;
    if( p->nLSlot>=n ) return SQLITE_OK;
    n = (n+7)&~7;
    paNew = sqlite3DbMallocRawNN(db, sizeof(p->aLTerm[0])*n);
    if( paNew==0 ) return SQLITE_NOMEM_BKPT;
    memcpy(paNew, p->aLTerm, sizeof(p->aLTerm[0])*p->nLSlot);
    if( p->aLTerm!=p->aLTermSpace ) sqlite3DbFreeNN(db, p->aLTerm);
    p->aLTerm = paNew;
    p->nLSlot = n;
    return SQLITE_OK;
  }
  
  /*
  ** Transfer content from the second pLoop into the first.
  */
  int whereLoopXfer(sqlite3 *db, WhereLoop *pTo, WhereLoop *pFrom){
    whereLoopClearUnion(db, pTo);
    if( whereLoopResize(db, pTo, pFrom->nLTerm) ){
      memset(&pTo->u, 0, sizeof(pTo->u));
      return SQLITE_NOMEM_BKPT;
    }
    memcpy(pTo, pFrom, WHERE_LOOP_XFER_SZ);
    memcpy(pTo->aLTerm, pFrom->aLTerm, pTo->nLTerm*sizeof(pTo->aLTerm[0]));
    if( pFrom->wsFlags & WHERE_VIRTUALTABLE ){
      pFrom->u.vtab.needFree = 0;
    }else if( (pFrom->wsFlags & WHERE_AUTO_INDEX)!=0 ){
      pFrom->u.btree.pIndex = 0;
    }
    return SQLITE_OK;
  }
  
  /*
  ** Delete a WhereLoop object
  */
  void whereLoopDelete(sqlite3 *db, WhereLoop *p){
    whereLoopClear(db, p);
    sqlite3DbFreeNN(db, p);
  }
  
  /*
  ** Free a WhereInfo structure
  */
  void whereInfoFree(sqlite3 *db, WhereInfo *pWInfo){
    int i;
    assert( pWInfo!=0 );
    for(i=0; i<pWInfo->nLevel; i++){
      WhereLevel *pLevel = &pWInfo->a[i];
      if( pLevel->pWLoop && (pLevel->pWLoop->wsFlags & WHERE_IN_ABLE) ){
        sqlite3DbFree(db, pLevel->u.in.aInLoop);
      }
    }
    sqlite3WhereClauseClear(&pWInfo->sWC);
    while( pWInfo->pLoops ){
      WhereLoop *p = pWInfo->pLoops;
      pWInfo->pLoops = p->pNextLoop;
      whereLoopDelete(db, p);
    }
    assert( pWInfo->pExprMods==0 );
    sqlite3DbFreeNN(db, pWInfo);
  }
  
  /*
  ** Return TRUE if all of the following are true:
  **
  **   (1)  X has the same or lower cost that Y
  **   (2)  X uses fewer WHERE clause terms than Y
  **   (3)  Every WHERE clause term used by X is also used by Y
  **   (4)  X skips at least as many columns as Y
  **   (5)  If X is a covering index, than Y is too
  **
  ** Conditions (2) and (3) mean that X is a "proper subset" of Y.
  ** If X is a proper subset of Y then Y is a better choice and ought
  ** to have a lower cost.  This routine returns TRUE when that cost 
  ** relationship is inverted and needs to be adjusted.  Constraint (4)
  ** was added because if X uses skip-scan less than Y it still might
  ** deserve a lower cost even if it is a proper subset of Y.  Constraint (5)
  ** was added because a covering index probably deserves to have a lower cost
  ** than a non-covering index even if it is a proper subset.
  */
  int whereLoopCheaperProperSubset(
    const WhereLoop *pX,       /* First WhereLoop to compare */
    const WhereLoop *pY        /* Compare against this WhereLoop */
  ){
    int i, j;
    if( pX->nLTerm-pX->nSkip >= pY->nLTerm-pY->nSkip ){
      return 0; /* X is not a subset of Y */
    }
    if( pY->nSkip > pX->nSkip ) return 0;
    if( pX->rRun >= pY->rRun ){
      if( pX->rRun > pY->rRun ) return 0;    /* X costs more than Y */
      if( pX->nOut > pY->nOut ) return 0;    /* X costs more than Y */
    }
    for(i=pX->nLTerm-1; i>=0; i--){
      if( pX->aLTerm[i]==0 ) continue;
      for(j=pY->nLTerm-1; j>=0; j--){
        if( pY->aLTerm[j]==pX->aLTerm[i] ) break;
      }
      if( j<0 ) return 0;  /* X not a subset of Y since term X[i] not used by Y */
    }
    if( (pX->wsFlags&WHERE_IDX_ONLY)!=0 
     && (pY->wsFlags&WHERE_IDX_ONLY)==0 ){
      return 0;  /* Constraint (5) */
    }
    return 1;  /* All conditions meet */
  }
  
  /*
  ** Try to adjust the cost of WhereLoop pTemplate upwards or downwards so
  ** that:
  **
  **   (1) pTemplate costs less than any other WhereLoops that are a proper
  **       subset of pTemplate
  **
  **   (2) pTemplate costs more than any other WhereLoops for which pTemplate
  **       is a proper subset.
  **
  ** To say "WhereLoop X is a proper subset of Y" means that X uses fewer
  ** WHERE clause terms than Y and that every WHERE clause term used by X is
  ** also used by Y.
  */
  void whereLoopAdjustCost(const WhereLoop *p, WhereLoop *pTemplate){
    if( (pTemplate->wsFlags & WHERE_INDEXED)==0 ) return;
    for(; p; p=p->pNextLoop){
      if( p->iTab!=pTemplate->iTab ) continue;
      if( (p->wsFlags & WHERE_INDEXED)==0 ) continue;
      if( whereLoopCheaperProperSubset(p, pTemplate) ){
        /* Adjust pTemplate cost downward so that it is cheaper than its 
        ** subset p. */
        WHERETRACE(0x80,("subset cost adjustment %d,%d to %d,%d\n",
                         pTemplate->rRun, pTemplate->nOut, p->rRun, p->nOut-1));
        pTemplate->rRun = p->rRun;
        pTemplate->nOut = p->nOut - 1;
      }else if( whereLoopCheaperProperSubset(pTemplate, p) ){
        /* Adjust pTemplate cost upward so that it is costlier than p since
        ** pTemplate is a proper subset of p */
        WHERETRACE(0x80,("subset cost adjustment %d,%d to %d,%d\n",
                         pTemplate->rRun, pTemplate->nOut, p->rRun, p->nOut+1));
        pTemplate->rRun = p->rRun;
        pTemplate->nOut = p->nOut + 1;
      }
    }
  }
  
  /*
  ** Search the list of WhereLoops in *ppPrev looking for one that can be
  ** replaced by pTemplate.
  **
  ** Return NULL if pTemplate does not belong on the WhereLoop list.
  ** In other words if pTemplate ought to be dropped from further consideration.
  **
  ** If pX is a WhereLoop that pTemplate can replace, then return the
  ** link that points to pX.
  **
  ** If pTemplate cannot replace any existing element of the list but needs
  ** to be added to the list as a new entry, then return a pointer to the
  ** tail of the list.
  */
  WhereLoop **whereLoopFindLesser(
    WhereLoop **ppPrev,
    const WhereLoop *pTemplate
  ){
    WhereLoop *p;
    for(p=(*ppPrev); p; ppPrev=&p->pNextLoop, p=*ppPrev){
      if( p->iTab!=pTemplate->iTab || p->iSortIdx!=pTemplate->iSortIdx ){
        /* If either the iTab or iSortIdx values for two WhereLoop are different
        ** then those WhereLoops need to be considered separately.  Neither is
        ** a candidate to replace the other. */
        continue;
      }
      /* In the current implementation, the rSetup value is either zero
      ** or the cost of building an automatic index (NlogN) and the NlogN
      ** is the same for compatible WhereLoops. */
      assert( p->rSetup==0 || pTemplate->rSetup==0 
                   || p->rSetup==pTemplate->rSetup );
  
      /* whereLoopAddBtree() always generates and inserts the automatic index
      ** case first.  Hence compatible candidate WhereLoops never have a larger
      ** rSetup. Call this SETUP-INVARIANT */
      assert( p->rSetup>=pTemplate->rSetup );
  
      /* Any loop using an appliation-defined index (or PRIMARY KEY or
      ** UNIQUE constraint) with one or more == constraints is better
      ** than an automatic index. Unless it is a skip-scan. */
      if( (p->wsFlags & WHERE_AUTO_INDEX)!=0
       && (pTemplate->nSkip)==0
       && (pTemplate->wsFlags & WHERE_INDEXED)!=0
       && (pTemplate->wsFlags & WHERE_COLUMN_EQ)!=0
       && (p->prereq & pTemplate->prereq)==pTemplate->prereq
      ){
        break;
      }
  
      /* If existing WhereLoop p is better than pTemplate, pTemplate can be
      ** discarded.  WhereLoop p is better if:
      **   (1)  p has no more dependencies than pTemplate, and
      **   (2)  p has an equal or lower cost than pTemplate
      */
      if( (p->prereq & pTemplate->prereq)==p->prereq    /* (1)  */
       && p->rSetup<=pTemplate->rSetup                  /* (2a) */
       && p->rRun<=pTemplate->rRun                      /* (2b) */
       && p->nOut<=pTemplate->nOut                      /* (2c) */
      ){
        return 0;  /* Discard pTemplate */
      }
  
      /* If pTemplate is always better than p, then cause p to be overwritten
      ** with pTemplate.  pTemplate is better than p if:
      **   (1)  pTemplate has no more dependences than p, and
      **   (2)  pTemplate has an equal or lower cost than p.
      */
      if( (p->prereq & pTemplate->prereq)==pTemplate->prereq   /* (1)  */
       && p->rRun>=pTemplate->rRun                             /* (2a) */
       && p->nOut>=pTemplate->nOut                             /* (2b) */
      ){
        assert( p->rSetup>=pTemplate->rSetup ); /* SETUP-INVARIANT above */
        break;   /* Cause p to be overwritten by pTemplate */
      }
    }
    return ppPrev;
  }
  
  /*
  ** Insert or replace a WhereLoop entry using the template supplied.
  **
  ** An existing WhereLoop entry might be overwritten if the new template
  ** is better and has fewer dependencies.  Or the template will be ignored
  ** and no insert will occur if an existing WhereLoop is faster and has
  ** fewer dependencies than the template.  Otherwise a new WhereLoop is
  ** added based on the template.
  **
  ** If pBuilder->pOrSet is not NULL then we care about only the
  ** prerequisites and rRun and nOut costs of the N best loops.  That
  ** information is gathered in the pBuilder->pOrSet object.  This special
  ** processing mode is used only for OR clause processing.
  **
  ** When accumulating multiple loops (when pBuilder->pOrSet is NULL) we
  ** still might overwrite similar loops with the new template if the
  ** new template is better.  Loops may be overwritten if the following 
  ** conditions are met:
  **
  **    (1)  They have the same iTab.
  **    (2)  They have the same iSortIdx.
  **    (3)  The template has same or fewer dependencies than the current loop
  **    (4)  The template has the same or lower cost than the current loop
  */
  int whereLoopInsert(WhereLoopBuilder *pBuilder, WhereLoop *pTemplate){
    WhereLoop **ppPrev, *p;
    WhereInfo *pWInfo = pBuilder->pWInfo;
    sqlite3 *db = pWInfo->pParse->db;
    int rc;
  
    /* Stop the search once we hit the query planner search limit */
    if( pBuilder->iPlanLimit==0 ){
      WHERETRACE(0xffffffff,("=== query planner search limit reached ===\n"));
      if( pBuilder->pOrSet ) pBuilder->pOrSet->n = 0;
      return SQLITE_DONE;
    }
    pBuilder->iPlanLimit--;
  
    whereLoopAdjustCost(pWInfo->pLoops, pTemplate);
  
    /* If pBuilder->pOrSet is defined, then only keep track of the costs
    ** and prereqs.
    */
    if( pBuilder->pOrSet!=0 ){
      if( pTemplate->nLTerm ){
  #if WHERETRACE_ENABLED
        u16 n = pBuilder->pOrSet->n;
        int x =
  #endif
        whereOrInsert(pBuilder->pOrSet, pTemplate->prereq, pTemplate->rRun,
                                      pTemplate->nOut);
  #if WHERETRACE_ENABLED /* 0x8 */
        if( sqlite3WhereTrace & 0x8 ){
          sqlite3DebugPrintf(x?"   or-%d:  ":"   or-X:  ", n);
          sqlite3WhereLoopPrint(pTemplate, pBuilder->pWC);
        }
  #endif
      }
      return SQLITE_OK;
    }
  
    /* Look for an existing WhereLoop to replace with pTemplate
    */
    ppPrev = whereLoopFindLesser(&pWInfo->pLoops, pTemplate);
  
    if( ppPrev==0 ){
      /* There already exists a WhereLoop on the list that is better
      ** than pTemplate, so just ignore pTemplate */
  #if WHERETRACE_ENABLED /* 0x8 */
      if( sqlite3WhereTrace & 0x8 ){
        sqlite3DebugPrintf("   skip: ");
        sqlite3WhereLoopPrint(pTemplate, pBuilder->pWC);
      }
  #endif
      return SQLITE_OK;  
    }else{
      p = *ppPrev;
    }
  
    /* If we reach this point it means that either p[] should be overwritten
    ** with pTemplate[] if p[] exists, or if p==NULL then allocate a new
    ** WhereLoop and insert it.
    */
  #if WHERETRACE_ENABLED /* 0x8 */
    if( sqlite3WhereTrace & 0x8 ){
      if( p!=0 ){
        sqlite3DebugPrintf("replace: ");
        sqlite3WhereLoopPrint(p, pBuilder->pWC);
        sqlite3DebugPrintf("   with: ");
      }else{
        sqlite3DebugPrintf("    add: ");
      }
      sqlite3WhereLoopPrint(pTemplate, pBuilder->pWC);
    }
  #endif
    if( p==0 ){
      /* Allocate a new WhereLoop to add to the end of the list */
      *ppPrev = p = sqlite3DbMallocRawNN(db, sizeof(WhereLoop));
      if( p==0 ) return SQLITE_NOMEM_BKPT;
      whereLoopInit(p);
      p->pNextLoop = 0;
    }else{
      /* We will be overwriting WhereLoop p[].  But before we do, first
      ** go through the rest of the list and delete any other entries besides
      ** p[] that are also supplated by pTemplate */
      WhereLoop **ppTail = &p->pNextLoop;
      WhereLoop *pToDel;
      while( *ppTail ){
        ppTail = whereLoopFindLesser(ppTail, pTemplate);
        if( ppTail==0 ) break;
        pToDel = *ppTail;
        if( pToDel==0 ) break;
        *ppTail = pToDel->pNextLoop;
  #if WHERETRACE_ENABLED /* 0x8 */
        if( sqlite3WhereTrace & 0x8 ){
          sqlite3DebugPrintf(" delete: ");
          sqlite3WhereLoopPrint(pToDel, pBuilder->pWC);
        }
  #endif
        whereLoopDelete(db, pToDel);
      }
    }
    rc = whereLoopXfer(db, p, pTemplate);
    if( (p->wsFlags & WHERE_VIRTUALTABLE)==0 ){
      Index *pIndex = p->u.btree.pIndex;
      if( pIndex && pIndex->idxType==SQLITE_IDXTYPE_IPK ){
        p->u.btree.pIndex = 0;
      }
    }
    return rc;
  }
  
  /*
  ** Adjust the WhereLoop.nOut value downward to account for terms of the
  ** WHERE clause that reference the loop but which are not used by an
  ** index.
  *
  ** For every WHERE clause term that is not used by the index
  ** and which has a truth probability assigned by one of the likelihood(),
  ** likely(), or unlikely() SQL functions, reduce the estimated number
  ** of output rows by the probability specified.
  **
  ** TUNING:  For every WHERE clause term that is not used by the index
  ** and which does not have an assigned truth probability, heuristics
  ** described below are used to try to estimate the truth probability.
  ** TODO --> Perhaps this is something that could be improved by better
  ** table statistics.
  **
  ** Heuristic 1:  Estimate the truth probability as 93.75%.  The 93.75%
  ** value corresponds to -1 in LogEst notation, so this means decrement
  ** the WhereLoop.nOut field for every such WHERE clause term.
  **
  ** Heuristic 2:  If there exists one or more WHERE clause terms of the
  ** form "x==EXPR" and EXPR is not a constant 0 or 1, then make sure the
  ** final output row estimate is no greater than 1/4 of the total number
  ** of rows in the table.  In other words, assume that x==EXPR will filter
  ** out at least 3 out of 4 rows.  If EXPR is -1 or 0 or 1, then maybe the
  ** "x" column is boolean or else -1 or 0 or 1 is a common default value
  ** on the "x" column and so in that case only cap the output row estimate
  ** at 1/2 instead of 1/4.
  */
  void whereLoopOutputAdjust(
    WhereClause *pWC,      /* The WHERE clause */
    WhereLoop *pLoop,      /* The loop to adjust downward */
    LogEst nRow            /* Number of rows in the entire table */
  ){
    WhereTerm *pTerm, *pX;
    Bitmask notAllowed = ~(pLoop->prereq|pLoop->maskSelf);
    int i, j;
    LogEst iReduce = 0;    /* pLoop->nOut should not exceed nRow-iReduce */
  
    assert( (pLoop->wsFlags & WHERE_AUTO_INDEX)==0 );
    for(i=pWC->nTerm, pTerm=pWC->a; i>0; i--, pTerm++){
      assert( pTerm!=0 );
      if( (pTerm->wtFlags & TERM_VIRTUAL)!=0 ) break;
      if( (pTerm->prereqAll & pLoop->maskSelf)==0 ) continue;
      if( (pTerm->prereqAll & notAllowed)!=0 ) continue;
      for(j=pLoop->nLTerm-1; j>=0; j--){
        pX = pLoop->aLTerm[j];
        if( pX==0 ) continue;
        if( pX==pTerm ) break;
        if( pX->iParent>=0 && (&pWC->a[pX->iParent])==pTerm ) break;
      }
      if( j<0 ){
        if( pTerm->truthProb<=0 ){
          /* If a truth probability is specified using the likelihood() hints,
          ** then use the probability provided by the application. */
          pLoop->nOut += pTerm->truthProb;
        }else{
          /* In the absence of explicit truth probabilities, use heuristics to
          ** guess a reasonable truth probability. */
          pLoop->nOut--;
          if( (pTerm->eOperator&(WO_EQ|WO_IS))!=0
           && (pTerm->wtFlags & TERM_HIGHTRUTH)==0  /* tag-20200224-1 */
          ){
            Expr *pRight = pTerm->pExpr->pRight;
            int k = 0;
            testcase( pTerm->pExpr->op==TK_IS );
            if( sqlite3ExprIsInteger(pRight, &k) && k>=(-1) && k<=1 ){
              k = 10;
            }else{
              k = 20;
            }
            if( iReduce<k ){
              pTerm->wtFlags |= TERM_HEURTRUTH;
              iReduce = k;
            }
          }
        }
      }
    }
    if( pLoop->nOut > nRow-iReduce )  pLoop->nOut = nRow - iReduce;
  }
  
  /* 
  ** Term pTerm is a vector range comparison operation. The first comparison
  ** in the vector can be optimized using column nEq of the index. This
  ** function returns the total number of vector elements that can be used
  ** as part of the range comparison.
  **
  ** For example, if the query is:
  **
  **   WHERE a = ? AND (b, c, d) > (?, ?, ?)
  **
  ** and the index:
  **
  **   CREATE INDEX ... ON (a, b, c, d, e)
  **
  ** then this function would be invoked with nEq=1. The value returned in
  ** this case is 3.
  */
  int whereRangeVectorLen(
    Parse *pParse,       /* Parsing context */
    int iCur,            /* Cursor open on pIdx */
    Index *pIdx,         /* The index to be used for a inequality constraint */
    int nEq,             /* Number of prior equality constraints on same index */
    WhereTerm *pTerm     /* The vector inequality constraint */
  ){
    int nCmp = sqlite3ExprVectorSize(pTerm->pExpr->pLeft);
    int i;
  
    nCmp = MIN(nCmp, (pIdx->nColumn - nEq));
    for(i=1; i<nCmp; i++){
      /* Test if comparison i of pTerm is compatible with column (i+nEq) 
      ** of the index. If not, exit the loop.  */
      char aff;                     /* Comparison affinity */
      char idxaff = 0;              /* Indexed columns affinity */
      CollSeq *pColl;               /* Comparison collation sequence */
      Expr *pLhs = pTerm->pExpr->pLeft->x.pList->a[i].pExpr;
      Expr *pRhs = pTerm->pExpr->pRight;
      if( pRhs->flags & EP_xIsSelect ){
        pRhs = pRhs->x.pSelect->pEList->a[i].pExpr;
      }else{
        pRhs = pRhs->x.pList->a[i].pExpr;
      }
  
      /* Check that the LHS of the comparison is a column reference to
      ** the right column of the right source table. And that the sort
      ** order of the index column is the same as the sort order of the
      ** leftmost index column.  */
      if( pLhs->op!=TK_COLUMN 
       || pLhs->iTable!=iCur 
       || pLhs->iColumn!=pIdx->aiColumn[i+nEq] 
       || pIdx->aSortOrder[i+nEq]!=pIdx->aSortOrder[nEq]
      ){
        break;
      }
  
      testcase( pLhs->iColumn==XN_ROWID );
      aff = sqlite3CompareAffinity(pRhs, sqlite3ExprAffinity(pLhs));
      idxaff = sqlite3TableColumnAffinity(pIdx->pTable, pLhs->iColumn);
      if( aff!=idxaff ) break;
  
      pColl = sqlite3BinaryCompareCollSeq(pParse, pLhs, pRhs);
      if( pColl==0 ) break;
      if( sqlite3StrICmp(pColl->zName, pIdx->azColl[i+nEq]) ) break;
    }
    return i;
  }
  
  /*
  ** Adjust the cost C by the costMult facter T.  This only occurs if
  ** compiled with -DSQLITE_ENABLE_COSTMULT
  */
  #ifdef SQLITE_ENABLE_COSTMULT
  # define ApplyCostMultiplier(C,T)  C += T
  #else
  # define ApplyCostMultiplier(C,T)
  #endif
  
  /*
  ** We have so far matched pBuilder->pNew->u.btree.nEq terms of the 
  ** index pIndex. Try to match one more.
  **
  ** When this function is called, pBuilder->pNew->nOut contains the 
  ** number of rows expected to be visited by filtering using the nEq 
  ** terms only. If it is modified, this value is restored before this 
  ** function returns.
  **
  ** If pProbe->idxType==SQLITE_IDXTYPE_IPK, that means pIndex is 
  ** a fake index used for the INTEGER PRIMARY KEY.
  */
  int whereLoopAddBtreeIndex(
    WhereLoopBuilder *pBuilder,     /* The WhereLoop factory */
    struct SrcList_item *pSrc,      /* FROM clause term being analyzed */
    Index *pProbe,                  /* An index on pSrc */
    LogEst nInMul                   /* log(Number of iterations due to IN) */
  ){
    WhereInfo *pWInfo = pBuilder->pWInfo;  /* WHERE analyse context */
    Parse *pParse = pWInfo->pParse;        /* Parsing context */
    sqlite3 *db = pParse->db;       /* Database connection malloc context */
    WhereLoop *pNew;                /* Template WhereLoop under construction */
    WhereTerm *pTerm;               /* A WhereTerm under consideration */
    int opMask;                     /* Valid operators for constraints */
    WhereScan scan;                 /* Iterator for WHERE terms */
    Bitmask saved_prereq;           /* Original value of pNew->prereq */
    u16 saved_nLTerm;               /* Original value of pNew->nLTerm */
    u16 saved_nEq;                  /* Original value of pNew->u.btree.nEq */
    u16 saved_nBtm;                 /* Original value of pNew->u.btree.nBtm */
    u16 saved_nTop;                 /* Original value of pNew->u.btree.nTop */
    u16 saved_nSkip;                /* Original value of pNew->nSkip */
    u32 saved_wsFlags;              /* Original value of pNew->wsFlags */
    LogEst saved_nOut;              /* Original value of pNew->nOut */
    int rc = SQLITE_OK;             /* Return code */
    LogEst rSize;                   /* Number of rows in the table */
    LogEst rLogSize;                /* Logarithm of table size */
    WhereTerm *pTop = 0, *pBtm = 0; /* Top and bottom range constraints */
  
    pNew = pBuilder->pNew;
    if( db->mallocFailed ) return SQLITE_NOMEM_BKPT;
    WHERETRACE(0x800, ("BEGIN %s.addBtreeIdx(%s), nEq=%d, nSkip=%d\n",
                       pProbe->pTable->zName,pProbe->zName,
                       pNew->u.btree.nEq, pNew->nSkip));
  
    assert( (pNew->wsFlags & WHERE_VIRTUALTABLE)==0 );
    assert( (pNew->wsFlags & WHERE_TOP_LIMIT)==0 );
    if( pNew->wsFlags & WHERE_BTM_LIMIT ){
      opMask = WO_LT|WO_LE;
    }else{
      assert( pNew->u.btree.nBtm==0 );
      opMask = WO_EQ|WO_IN|WO_GT|WO_GE|WO_LT|WO_LE|WO_ISNULL|WO_IS;
    }
    if( pProbe->bUnordered ) opMask &= ~(WO_GT|WO_GE|WO_LT|WO_LE);
  
    assert( pNew->u.btree.nEq<pProbe->nColumn );
  
    saved_nEq = pNew->u.btree.nEq;
    saved_nBtm = pNew->u.btree.nBtm;
    saved_nTop = pNew->u.btree.nTop;
    saved_nSkip = pNew->nSkip;
    saved_nLTerm = pNew->nLTerm;
    saved_wsFlags = pNew->wsFlags;
    saved_prereq = pNew->prereq;
    saved_nOut = pNew->nOut;
    pTerm = whereScanInit(&scan, pBuilder->pWC, pSrc->iCursor, saved_nEq,
                          opMask, pProbe);
    pNew->rSetup = 0;
    rSize = pProbe->aiRowLogEst[0];
    rLogSize = estLog(rSize);
    for(; rc==SQLITE_OK && pTerm!=0; pTerm = whereScanNext(&scan)){
      u16 eOp = pTerm->eOperator;   /* Shorthand for pTerm->eOperator */
      LogEst rCostIdx;
      LogEst nOutUnadjusted;        /* nOut before IN() and WHERE adjustments */
      int nIn = 0;
  #ifdef SQLITE_ENABLE_STAT4
      int nRecValid = pBuilder->nRecValid;
  #endif
      if( (eOp==WO_ISNULL || (pTerm->wtFlags&TERM_VNULL)!=0)
       && indexColumnNotNull(pProbe, saved_nEq)
      ){
        continue; /* ignore IS [NOT] NULL constraints on NOT NULL columns */
      }
      if( pTerm->prereqRight & pNew->maskSelf ) continue;
  
      /* Do not allow the upper bound of a LIKE optimization range constraint
      ** to mix with a lower range bound from some other source */
      if( pTerm->wtFlags & TERM_LIKEOPT && pTerm->eOperator==WO_LT ) continue;
  
      /* tag-20191211-001:  Do not allow constraints from the WHERE clause to
      ** be used by the right table of a LEFT JOIN.  Only constraints in the
      ** ON clause are allowed.  See tag-20191211-002 for the vtab equivalent. */
      if( (pSrc->fg.jointype & JT_LEFT)!=0
       && !ExprHasProperty(pTerm->pExpr, EP_FromJoin)
      ){
        continue;
      }
  
      if( IsUniqueIndex(pProbe) && saved_nEq==pProbe->nKeyCol-1 ){
        pBuilder->bldFlags1 |= SQLITE_BLDF1_UNIQUE;
      }else{
        pBuilder->bldFlags1 |= SQLITE_BLDF1_INDEXED;
      }
      pNew->wsFlags = saved_wsFlags;
      pNew->u.btree.nEq = saved_nEq;
      pNew->u.btree.nBtm = saved_nBtm;
      pNew->u.btree.nTop = saved_nTop;
      pNew->nLTerm = saved_nLTerm;
      if( whereLoopResize(db, pNew, pNew->nLTerm+1) ) break; /* OOM */
      pNew->aLTerm[pNew->nLTerm++] = pTerm;
      pNew->prereq = (saved_prereq | pTerm->prereqRight) & ~pNew->maskSelf;
  
      assert( nInMul==0
          || (pNew->wsFlags & WHERE_COLUMN_NULL)!=0 
          || (pNew->wsFlags & WHERE_COLUMN_IN)!=0 
          || (pNew->wsFlags & WHERE_SKIPSCAN)!=0 
      );
  
      if( eOp & WO_IN ){
        Expr *pExpr = pTerm->pExpr;
        if( ExprHasProperty(pExpr, EP_xIsSelect) ){
          /* "x IN (SELECT ...)":  TUNING: the SELECT returns 25 rows */
          int i;
          nIn = 46;  assert( 46==sqlite3LogEst(25) );
  
          /* The expression may actually be of the form (x, y) IN (SELECT...).
          ** In this case there is a separate term for each of (x) and (y).
          ** However, the nIn multiplier should only be applied once, not once
          ** for each such term. The following loop checks that pTerm is the
          ** first such term in use, and sets nIn back to 0 if it is not. */
          for(i=0; i<pNew->nLTerm-1; i++){
            if( pNew->aLTerm[i] && pNew->aLTerm[i]->pExpr==pExpr ) nIn = 0;
          }
        }else if( ALWAYS(pExpr->x.pList && pExpr->x.pList->nExpr) ){
          /* "x IN (value, value, ...)" */
          nIn = sqlite3LogEst(pExpr->x.pList->nExpr);
        }
        if( pProbe->hasStat1 ){
          LogEst M, logK, safetyMargin;
          /* Let:
          **   N = the total number of rows in the table
          **   K = the number of entries on the RHS of the IN operator
          **   M = the number of rows in the table that match terms to the 
          **       to the left in the same index.  If the IN operator is on
          **       the left-most index column, M==N.
          **
          ** Given the definitions above, it is better to omit the IN operator
          ** from the index lookup and instead do a scan of the M elements,
          ** testing each scanned row against the IN operator separately, if:
          **
          **        M*log(K) < K*log(N)
          **
          ** Our estimates for M, K, and N might be inaccurate, so we build in
          ** a safety margin of 2 (LogEst: 10) that favors using the IN operator
          ** with the index, as using an index has better worst-case behavior.
          ** If we do not have real sqlite_stat1 data, always prefer to use
          ** the index.
          */
          M = pProbe->aiRowLogEst[saved_nEq];
          logK = estLog(nIn);
          safetyMargin = 10;  /* TUNING: extra weight for indexed IN */
          if( M + logK + safetyMargin < nIn + rLogSize ){
            WHERETRACE(0x40,
              ("Scan preferred over IN operator on column %d of \"%s\" (%d<%d)\n",
               saved_nEq, pProbe->zName, M+logK+10, nIn+rLogSize));
            continue;
          }else{
            WHERETRACE(0x40,
              ("IN operator preferred on column %d of \"%s\" (%d>=%d)\n",
               saved_nEq, pProbe->zName, M+logK+10, nIn+rLogSize));
          }
        }
        pNew->wsFlags |= WHERE_COLUMN_IN;
      }else if( eOp & (WO_EQ|WO_IS) ){
        int iCol = pProbe->aiColumn[saved_nEq];
        pNew->wsFlags |= WHERE_COLUMN_EQ;
        assert( saved_nEq==pNew->u.btree.nEq );
        if( iCol==XN_ROWID 
         || (iCol>=0 && nInMul==0 && saved_nEq==pProbe->nKeyCol-1)
        ){
          if( iCol==XN_ROWID || pProbe->uniqNotNull 
           || (pProbe->nKeyCol==1 && pProbe->onError && eOp==WO_EQ) 
          ){
            pNew->wsFlags |= WHERE_ONEROW;
          }else{
            pNew->wsFlags |= WHERE_UNQ_WANTED;
          }
        }
      }else if( eOp & WO_ISNULL ){
        pNew->wsFlags |= WHERE_COLUMN_NULL;
      }else if( eOp & (WO_GT|WO_GE) ){
        testcase( eOp & WO_GT );
        testcase( eOp & WO_GE );
        pNew->wsFlags |= WHERE_COLUMN_RANGE|WHERE_BTM_LIMIT;
        pNew->u.btree.nBtm = whereRangeVectorLen(
            pParse, pSrc->iCursor, pProbe, saved_nEq, pTerm
        );
        pBtm = pTerm;
        pTop = 0;
        if( pTerm->wtFlags & TERM_LIKEOPT ){
          /* Range contraints that come from the LIKE optimization are
          ** always used in pairs. */
          pTop = &pTerm[1];
          assert( (pTop-(pTerm->pWC->a))<pTerm->pWC->nTerm );
          assert( pTop->wtFlags & TERM_LIKEOPT );
          assert( pTop->eOperator==WO_LT );
          if( whereLoopResize(db, pNew, pNew->nLTerm+1) ) break; /* OOM */
          pNew->aLTerm[pNew->nLTerm++] = pTop;
          pNew->wsFlags |= WHERE_TOP_LIMIT;
          pNew->u.btree.nTop = 1;
        }
      }else{
        assert( eOp & (WO_LT|WO_LE) );
        testcase( eOp & WO_LT );
        testcase( eOp & WO_LE );
        pNew->wsFlags |= WHERE_COLUMN_RANGE|WHERE_TOP_LIMIT;
        pNew->u.btree.nTop = whereRangeVectorLen(
            pParse, pSrc->iCursor, pProbe, saved_nEq, pTerm
        );
        pTop = pTerm;
        pBtm = (pNew->wsFlags & WHERE_BTM_LIMIT)!=0 ?
                       pNew->aLTerm[pNew->nLTerm-2] : 0;
      }
  
      /* At this point pNew->nOut is set to the number of rows expected to
      ** be visited by the index scan before considering term pTerm, or the
      ** values of nIn and nInMul. In other words, assuming that all 
      ** "x IN(...)" terms are replaced with "x = ?". This block updates
      ** the value of pNew->nOut to account for pTerm (but not nIn/nInMul).  */
      assert( pNew->nOut==saved_nOut );
      if( pNew->wsFlags & WHERE_COLUMN_RANGE ){
        /* Adjust nOut using stat4 data. Or, if there is no stat4
        ** data, using some other estimate.  */
        whereRangeScanEst(pParse, pBuilder, pBtm, pTop, pNew);
      }else{
        int nEq = ++pNew->u.btree.nEq;
        assert( eOp & (WO_ISNULL|WO_EQ|WO_IN|WO_IS) );
  
        assert( pNew->nOut==saved_nOut );
        if( pTerm->truthProb<=0 && pProbe->aiColumn[saved_nEq]>=0 ){
          assert( (eOp & WO_IN) || nIn==0 );
          testcase( eOp & WO_IN );
          pNew->nOut += pTerm->truthProb;
          pNew->nOut -= nIn;
        }else{
  #ifdef SQLITE_ENABLE_STAT4
          tRowcnt nOut = 0;
          if( nInMul==0 
           && pProbe->nSample 
           && pNew->u.btree.nEq<=pProbe->nSampleCol
           && ((eOp & WO_IN)==0 || !ExprHasProperty(pTerm->pExpr, EP_xIsSelect))
           && OptimizationEnabled(db, SQLITE_Stat4)
          ){
            Expr *pExpr = pTerm->pExpr;
            if( (eOp & (WO_EQ|WO_ISNULL|WO_IS))!=0 ){
              testcase( eOp & WO_EQ );
              testcase( eOp & WO_IS );
              testcase( eOp & WO_ISNULL );
              rc = whereEqualScanEst(pParse, pBuilder, pExpr->pRight, &nOut);
            }else{
              rc = whereInScanEst(pParse, pBuilder, pExpr->x.pList, &nOut);
            }
            if( rc==SQLITE_NOTFOUND ) rc = SQLITE_OK;
            if( rc!=SQLITE_OK ) break;          /* Jump out of the pTerm loop */
            if( nOut ){
              pNew->nOut = sqlite3LogEst(nOut);
              if( nEq==1
               /* TUNING: Mark terms as "low selectivity" if they seem likely
               ** to be true for half or more of the rows in the table.
               ** See tag-202002240-1 */
               && pNew->nOut+10 > pProbe->aiRowLogEst[0]
              ){
  #if WHERETRACE_ENABLED /* 0x01 */
                if( sqlite3WhereTrace & 0x01 ){
                  sqlite3DebugPrintf(
                     "STAT4 determines term has low selectivity:\n");
                  sqlite3WhereTermPrint(pTerm, 999);
                }
  #endif
                pTerm->wtFlags |= TERM_HIGHTRUTH;
                if( pTerm->wtFlags & TERM_HEURTRUTH ){
                  /* If the term has previously been used with an assumption of
                  ** higher selectivity, then set the flag to rerun the
                  ** loop computations. */
                  pBuilder->bldFlags2 |= SQLITE_BLDF2_2NDPASS;
                }
              }
              if( pNew->nOut>saved_nOut ) pNew->nOut = saved_nOut;
              pNew->nOut -= nIn;
            }
          }
          if( nOut==0 )
  #endif
          {
            pNew->nOut += (pProbe->aiRowLogEst[nEq] - pProbe->aiRowLogEst[nEq-1]);
            if( eOp & WO_ISNULL ){
              /* TUNING: If there is no likelihood() value, assume that a 
              ** "col IS NULL" expression matches twice as many rows 
              ** as (col=?). */
              pNew->nOut += 10;
            }
          }
        }
      }
  
      /* Set rCostIdx to the cost of visiting selected rows in index. Add
      ** it to pNew->rRun, which is currently set to the cost of the index
      ** seek only. Then, if this is a non-covering index, add the cost of
      ** visiting the rows in the main table.  */
      assert( pSrc->pTab->szTabRow>0 );
      rCostIdx = pNew->nOut + 1 + (15*pProbe->szIdxRow)/pSrc->pTab->szTabRow;
      pNew->rRun = sqlite3LogEstAdd(rLogSize, rCostIdx);
      if( (pNew->wsFlags & (WHERE_IDX_ONLY|WHERE_IPK))==0 ){
        pNew->rRun = sqlite3LogEstAdd(pNew->rRun, pNew->nOut + 16);
      }
      ApplyCostMultiplier(pNew->rRun, pProbe->pTable->costMult);
  
      nOutUnadjusted = pNew->nOut;
      pNew->rRun += nInMul + nIn;
      pNew->nOut += nInMul + nIn;
      whereLoopOutputAdjust(pBuilder->pWC, pNew, rSize);
      rc = whereLoopInsert(pBuilder, pNew);
  
      if( pNew->wsFlags & WHERE_COLUMN_RANGE ){
        pNew->nOut = saved_nOut;
      }else{
        pNew->nOut = nOutUnadjusted;
      }
  
      if( (pNew->wsFlags & WHERE_TOP_LIMIT)==0
       && pNew->u.btree.nEq<pProbe->nColumn
      ){
        whereLoopAddBtreeIndex(pBuilder, pSrc, pProbe, nInMul+nIn);
      }
      pNew->nOut = saved_nOut;
  #ifdef SQLITE_ENABLE_STAT4
      pBuilder->nRecValid = nRecValid;
  #endif
    }
    pNew->prereq = saved_prereq;
    pNew->u.btree.nEq = saved_nEq;
    pNew->u.btree.nBtm = saved_nBtm;
    pNew->u.btree.nTop = saved_nTop;
    pNew->nSkip = saved_nSkip;
    pNew->wsFlags = saved_wsFlags;
    pNew->nOut = saved_nOut;
    pNew->nLTerm = saved_nLTerm;
  
    /* Consider using a skip-scan if there are no WHERE clause constraints
    ** available for the left-most terms of the index, and if the average
    ** number of repeats in the left-most terms is at least 18. 
    **
    ** The magic number 18 is selected on the basis that scanning 17 rows
    ** is almost always quicker than an index seek (even though if the index
    ** contains fewer than 2^17 rows we assume otherwise in other parts of
    ** the code). And, even if it is not, it should not be too much slower. 
    ** On the other hand, the extra seeks could end up being significantly
    ** more expensive.  */
    assert( 42==sqlite3LogEst(18) );
    if( saved_nEq==saved_nSkip
     && saved_nEq+1<pProbe->nKeyCol
     && saved_nEq==pNew->nLTerm
     && pProbe->noSkipScan==0
     && pProbe->hasStat1!=0
     && OptimizationEnabled(db, SQLITE_SkipScan)
     && pProbe->aiRowLogEst[saved_nEq+1]>=42  /* TUNING: Minimum for skip-scan */
     && (rc = whereLoopResize(db, pNew, pNew->nLTerm+1))==SQLITE_OK
    ){
      LogEst nIter;
      pNew->u.btree.nEq++;
      pNew->nSkip++;
      pNew->aLTerm[pNew->nLTerm++] = 0;
      pNew->wsFlags |= WHERE_SKIPSCAN;
      nIter = pProbe->aiRowLogEst[saved_nEq] - pProbe->aiRowLogEst[saved_nEq+1];
      pNew->nOut -= nIter;
      /* TUNING:  Because uncertainties in the estimates for skip-scan queries,
      ** add a 1.375 fudge factor to make skip-scan slightly less likely. */
      nIter += 5;
      whereLoopAddBtreeIndex(pBuilder, pSrc, pProbe, nIter + nInMul);
      pNew->nOut = saved_nOut;
      pNew->u.btree.nEq = saved_nEq;
      pNew->nSkip = saved_nSkip;
      pNew->wsFlags = saved_wsFlags;
    }
  
    WHERETRACE(0x800, ("END %s.addBtreeIdx(%s), nEq=%d, rc=%d\n",
                        pProbe->pTable->zName, pProbe->zName, saved_nEq, rc));
    return rc;
  }
  
  /*
  ** Return True if it is possible that pIndex might be useful in
  ** implementing the ORDER BY clause in pBuilder.
  **
  ** Return False if pBuilder does not contain an ORDER BY clause or
  ** if there is no way for pIndex to be useful in implementing that
  ** ORDER BY clause.
  */
  int indexMightHelpWithOrderBy(
    WhereLoopBuilder *pBuilder,
    Index *pIndex,
    int iCursor
  ){
    ExprList *pOB;
    ExprList *aColExpr;
    int ii, jj;
  
    if( pIndex->bUnordered ) return 0;
    if( (pOB = pBuilder->pWInfo->pOrderBy)==0 ) return 0;
    for(ii=0; ii<pOB->nExpr; ii++){
      Expr *pExpr = sqlite3ExprSkipCollateAndLikely(pOB->a[ii].pExpr);
      if( pExpr->op==TK_COLUMN && pExpr->iTable==iCursor ){
        if( pExpr->iColumn<0 ) return 1;
        for(jj=0; jj<pIndex->nKeyCol; jj++){
          if( pExpr->iColumn==pIndex->aiColumn[jj] ) return 1;
        }
      }else if( (aColExpr = pIndex->aColExpr)!=0 ){
        for(jj=0; jj<pIndex->nKeyCol; jj++){
          if( pIndex->aiColumn[jj]!=XN_EXPR ) continue;
          if( sqlite3ExprCompareSkip(pExpr,aColExpr->a[jj].pExpr,iCursor)==0 ){
            return 1;
          }
        }
      }
    }
    return 0;
  }
  
  /* Check to see if a partial index with pPartIndexWhere can be used
  ** in the current query.  Return true if it can be and false if not.
  */
  int whereUsablePartialIndex(
    int iTab,             /* The table for which we want an index */
    int isLeft,           /* True if iTab is the right table of a LEFT JOIN */
    WhereClause *pWC,     /* The WHERE clause of the query */
    Expr *pWhere          /* The WHERE clause from the partial index */
  ){
    int i;
    WhereTerm *pTerm;
    Parse *pParse = pWC->pWInfo->pParse;
    while( pWhere->op==TK_AND ){
      if( !whereUsablePartialIndex(iTab,isLeft,pWC,pWhere->pLeft) ) return 0;
      pWhere = pWhere->pRight;
    }
    if( pParse->db->flags & SQLITE_EnableQPSG ) pParse = 0;
    for(i=0, pTerm=pWC->a; i<pWC->nTerm; i++, pTerm++){
      Expr *pExpr;
      pExpr = pTerm->pExpr;
      if( (!ExprHasProperty(pExpr, EP_FromJoin) || pExpr->iRightJoinTable==iTab)
       && (isLeft==0 || ExprHasProperty(pExpr, EP_FromJoin))
       && sqlite3ExprImpliesExpr(pParse, pExpr, pWhere, iTab) 
      ){
        return 1;
      }
    }
    return 0;
  }
  
  /*
  ** Add all WhereLoop objects for a single table of the join where the table
  ** is identified by pBuilder->pNew->iTab.  That table is guaranteed to be
  ** a b-tree table, not a virtual table.
  **
  ** The costs (WhereLoop.rRun) of the b-tree loops added by this function
  ** are calculated as follows:
  **
  ** For a full scan, assuming the table (or index) contains nRow rows:
  **
  **     cost = nRow * 3.0                    // full-table scan
  **     cost = nRow * K                      // scan of covering index
  **     cost = nRow * (K+3.0)                // scan of non-covering index
  **
  ** where K is a value between 1.1 and 3.0 set based on the relative 
  ** estimated average size of the index and table records.
  **
  ** For an index scan, where nVisit is the number of index rows visited
  ** by the scan, and nSeek is the number of seek operations required on 
  ** the index b-tree:
  **
  **     cost = nSeek * (log(nRow) + K * nVisit)          // covering index
  **     cost = nSeek * (log(nRow) + (K+3.0) * nVisit)    // non-covering index
  **
  ** Normally, nSeek is 1. nSeek values greater than 1 come about if the 
  ** WHERE clause includes "x IN (....)" terms used in place of "x=?". Or when 
  ** implicit "x IN (SELECT x FROM tbl)" terms are added for skip-scans.
  **
  ** The estimated values (nRow, nVisit, nSeek) often contain a large amount
  ** of uncertainty.  For this reason, scoring is designed to pick plans that
  ** "do the least harm" if the estimates are inaccurate.  For example, a
  ** log(nRow) factor is omitted from a non-covering index scan in order to
  ** bias the scoring in favor of using an index, since the worst-case
  ** performance of using an index is far better than the worst-case performance
  ** of a full table scan.
  */
  int whereLoopAddBtree(
    WhereLoopBuilder *pBuilder, /* WHERE clause information */
    Bitmask mPrereq             /* Extra prerequesites for using this table */
  ){
    WhereInfo *pWInfo;          /* WHERE analysis context */
    Index *pProbe;              /* An index we are evaluating */
    Index sPk;                  /* A fake index object for the primary key */
    LogEst aiRowEstPk[2];       /* The aiRowLogEst[] value for the sPk index */
    i16 aiColumnPk = -1;        /* The aColumn[] value for the sPk index */
    SrcList *pTabList;          /* The FROM clause */
    struct SrcList_item *pSrc;  /* The FROM clause btree term to add */
    WhereLoop *pNew;            /* Template WhereLoop object */
    int rc = SQLITE_OK;         /* Return code */
    int iSortIdx = 1;           /* Index number */
    int b;                      /* A boolean value */
    LogEst rSize;               /* number of rows in the table */
    LogEst rLogSize;            /* Logarithm of the number of rows in the table */
    WhereClause *pWC;           /* The parsed WHERE clause */
    Table *pTab;                /* Table being queried */
    
    pNew = pBuilder->pNew;
    pWInfo = pBuilder->pWInfo;
    pTabList = pWInfo->pTabList;
    pSrc = pTabList->a + pNew->iTab;
    pTab = pSrc->pTab;
    pWC = pBuilder->pWC;
    assert( !IsVirtual(pSrc->pTab) );
  
    if( pSrc->pIBIndex ){
      /* An INDEXED BY clause specifies a particular index to use */
      pProbe = pSrc->pIBIndex;
    }else if( !HasRowid(pTab) ){
      pProbe = pTab->pIndex;
    }else{
      /* There is no INDEXED BY clause.  Create a fake Index object in local
      ** variable sPk to represent the rowid primary key index.  Make this
      ** fake index the first in a chain of Index objects with all of the real
      ** indices to follow */
      Index *pFirst;                  /* First of real indices on the table */
      memset(&sPk, 0, sizeof(Index));
      sPk.nKeyCol = 1;
      sPk.nColumn = 1;
      sPk.aiColumn = &aiColumnPk;
      sPk.aiRowLogEst = aiRowEstPk;
      sPk.onError = OE_Replace;
      sPk.pTable = pTab;
      sPk.szIdxRow = pTab->szTabRow;
      sPk.idxType = SQLITE_IDXTYPE_IPK;
      aiRowEstPk[0] = pTab->nRowLogEst;
      aiRowEstPk[1] = 0;
      pFirst = pSrc->pTab->pIndex;
      if( pSrc->fg.notIndexed==0 ){
        /* The real indices of the table are only considered if the
        ** NOT INDEXED qualifier is omitted from the FROM clause */
        sPk.pNext = pFirst;
      }
      pProbe = &sPk;
    }
    rSize = pTab->nRowLogEst;
    rLogSize = estLog(rSize);
  
  #ifndef SQLITE_OMIT_AUTOMATIC_INDEX
    /* Automatic indexes */
    if( !pBuilder->pOrSet      /* Not part of an OR optimization */
     && (pWInfo->wctrlFlags & WHERE_OR_SUBCLAUSE)==0
     && (pWInfo->pParse->db->flags & SQLITE_AutoIndex)!=0
     && pSrc->pIBIndex==0      /* Has no INDEXED BY clause */
     && !pSrc->fg.notIndexed   /* Has no NOT INDEXED clause */
     && HasRowid(pTab)         /* Not WITHOUT ROWID table. (FIXME: Why not?) */
     && !pSrc->fg.isCorrelated /* Not a correlated subquery */
     && !pSrc->fg.isRecursive  /* Not a recursive common table expression. */
    ){
      /* Generate auto-index WhereLoops */
      WhereTerm *pTerm;
      WhereTerm *pWCEnd = pWC->a + pWC->nTerm;
      for(pTerm=pWC->a; rc==SQLITE_OK && pTerm<pWCEnd; pTerm++){
        if( pTerm->prereqRight & pNew->maskSelf ) continue;
        if( termCanDriveIndex(pTerm, pSrc, 0) ){
          pNew->u.btree.nEq = 1;
          pNew->nSkip = 0;
          pNew->u.btree.pIndex = 0;
          pNew->nLTerm = 1;
          pNew->aLTerm[0] = pTerm;
          /* TUNING: One-time cost for computing the automatic index is
          ** estimated to be X*N*log2(N) where N is the number of rows in
          ** the table being indexed and where X is 7 (LogEst=28) for normal
          ** tables or 0.5 (LogEst=-10) for views and subqueries.  The value
          ** of X is smaller for views and subqueries so that the query planner
          ** will be more aggressive about generating automatic indexes for
          ** those objects, since there is no opportunity to add schema
          ** indexes on subqueries and views. */
          pNew->rSetup = rLogSize + rSize;
          if( pTab->pSelect==0 && (pTab->tabFlags & TF_Ephemeral)==0 ){
            pNew->rSetup += 28;
          }else{
            pNew->rSetup -= 10;
          }
          ApplyCostMultiplier(pNew->rSetup, pTab->costMult);
          if( pNew->rSetup<0 ) pNew->rSetup = 0;
          /* TUNING: Each index lookup yields 20 rows in the table.  This
          ** is more than the usual guess of 10 rows, since we have no way
          ** of knowing how selective the index will ultimately be.  It would
          ** not be unreasonable to make this value much larger. */
          pNew->nOut = 43;  assert( 43==sqlite3LogEst(20) );
          pNew->rRun = sqlite3LogEstAdd(rLogSize,pNew->nOut);
          pNew->wsFlags = WHERE_AUTO_INDEX;
          pNew->prereq = mPrereq | pTerm->prereqRight;
          rc = whereLoopInsert(pBuilder, pNew);
        }
      }
    }
  #endif /* SQLITE_OMIT_AUTOMATIC_INDEX */
  
    /* Loop over all indices. If there was an INDEXED BY clause, then only 
    ** consider index pProbe.  */
    for(; rc==SQLITE_OK && pProbe; 
        pProbe=(pSrc->pIBIndex ? 0 : pProbe->pNext), iSortIdx++
    ){
      int isLeft = (pSrc->fg.jointype & JT_OUTER)!=0;
      if( pProbe->pPartIdxWhere!=0
       && !whereUsablePartialIndex(pSrc->iCursor, isLeft, pWC,
                                   pProbe->pPartIdxWhere)
      ){
        testcase( pNew->iTab!=pSrc->iCursor );  /* See ticket [98d973b8f5] */
        continue;  /* Partial index inappropriate for this query */
      }
      if( pProbe->bNoQuery ) continue;
      rSize = pProbe->aiRowLogEst[0];
      pNew->u.btree.nEq = 0;
      pNew->u.btree.nBtm = 0;
      pNew->u.btree.nTop = 0;
      pNew->nSkip = 0;
      pNew->nLTerm = 0;
      pNew->iSortIdx = 0;
      pNew->rSetup = 0;
      pNew->prereq = mPrereq;
      pNew->nOut = rSize;
      pNew->u.btree.pIndex = pProbe;
      b = indexMightHelpWithOrderBy(pBuilder, pProbe, pSrc->iCursor);
      /* The ONEPASS_DESIRED flags never occurs together with ORDER BY */
      assert( (pWInfo->wctrlFlags & WHERE_ONEPASS_DESIRED)==0 || b==0 );
      if( pProbe->idxType==SQLITE_IDXTYPE_IPK ){
        /* Integer primary key index */
        pNew->wsFlags = WHERE_IPK;
  
        /* Full table scan */
        pNew->iSortIdx = b ? iSortIdx : 0;
        /* TUNING: Cost of full table scan is (N*3.0). */
        pNew->rRun = rSize + 16;
        ApplyCostMultiplier(pNew->rRun, pTab->costMult);
        whereLoopOutputAdjust(pWC, pNew, rSize);
        rc = whereLoopInsert(pBuilder, pNew);
        pNew->nOut = rSize;
        if( rc ) break;
      }else{
        Bitmask m;
        if( pProbe->isCovering ){
          pNew->wsFlags = WHERE_IDX_ONLY | WHERE_INDEXED;
          m = 0;
        }else{
          m = pSrc->colUsed & pProbe->colNotIdxed;
          pNew->wsFlags = (m==0) ? (WHERE_IDX_ONLY|WHERE_INDEXED) : WHERE_INDEXED;
        }
  
        /* Full scan via index */
        if( b
         || !HasRowid(pTab)
         || pProbe->pPartIdxWhere!=0
         || ( m==0
           && pProbe->bUnordered==0
           && (pProbe->szIdxRow<pTab->szTabRow)
           && (pWInfo->wctrlFlags & WHERE_ONEPASS_DESIRED)==0
           && sqlite3GlobalConfig.bUseCis
           && OptimizationEnabled(pWInfo->pParse->db, SQLITE_CoverIdxScan)
            )
        ){
          pNew->iSortIdx = b ? iSortIdx : 0;
  
          /* The cost of visiting the index rows is N*K, where K is
          ** between 1.1 and 3.0, depending on the relative sizes of the
          ** index and table rows. */
          pNew->rRun = rSize + 1 + (15*pProbe->szIdxRow)/pTab->szTabRow;
          if( m!=0 ){
            /* If this is a non-covering index scan, add in the cost of
            ** doing table lookups.  The cost will be 3x the number of
            ** lookups.  Take into account WHERE clause terms that can be
            ** satisfied using just the index, and that do not require a
            ** table lookup. */
            LogEst nLookup = rSize + 16;  /* Base cost:  N*3 */
            int ii;
            int iCur = pSrc->iCursor;
            WhereClause *pWC2 = &pWInfo->sWC;
            for(ii=0; ii<pWC2->nTerm; ii++){
              WhereTerm *pTerm = &pWC2->a[ii];
              if( !sqlite3ExprCoveredByIndex(pTerm->pExpr, iCur, pProbe) ){
                break;
              }
              /* pTerm can be evaluated using just the index.  So reduce
              ** the expected number of table lookups accordingly */
              if( pTerm->truthProb<=0 ){
                nLookup += pTerm->truthProb;
              }else{
                nLookup--;
                if( pTerm->eOperator & (WO_EQ|WO_IS) ) nLookup -= 19;
              }
            }
            
            pNew->rRun = sqlite3LogEstAdd(pNew->rRun, nLookup);
          }
          ApplyCostMultiplier(pNew->rRun, pTab->costMult);
          whereLoopOutputAdjust(pWC, pNew, rSize);
          rc = whereLoopInsert(pBuilder, pNew);
          pNew->nOut = rSize;
          if( rc ) break;
        }
      }
  
      pBuilder->bldFlags1 = 0;
      rc = whereLoopAddBtreeIndex(pBuilder, pSrc, pProbe, 0);
      if( pBuilder->bldFlags1==SQLITE_BLDF1_INDEXED ){
        /* If a non-unique index is used, or if a prefix of the key for
        ** unique index is used (making the index functionally non-unique)
        ** then the sqlite_stat1 data becomes important for scoring the
        ** plan */
        pTab->tabFlags |= TF_StatsUsed;
      }
  #ifdef SQLITE_ENABLE_STAT4
      sqlite3Stat4ProbeFree(pBuilder->pRec);
      pBuilder->nRecValid = 0;
      pBuilder->pRec = 0;
  #endif
    }
    return rc;
  }
  
  #ifndef SQLITE_OMIT_VIRTUALTABLE
  
  /*
  ** Argument pIdxInfo is already populated with all constraints that may
  ** be used by the virtual table identified by pBuilder->pNew->iTab. This
  ** function marks a subset of those constraints usable, invokes the
  ** xBestIndex method and adds the returned plan to pBuilder.
  **
  ** A constraint is marked usable if:
  **
  **   * Argument mUsable indicates that its prerequisites are available, and
  **
  **   * It is not one of the operators specified in the mExclude mask passed
  **     as the fourth argument (which in practice is either WO_IN or 0).
  **
  ** Argument mPrereq is a mask of tables that must be scanned before the
  ** virtual table in question. These are added to the plans prerequisites
  ** before it is added to pBuilder.
  **
  ** Output parameter *pbIn is set to true if the plan added to pBuilder
  ** uses one or more WO_IN terms, or false otherwise.
  */
  int whereLoopAddVirtualOne(
    WhereLoopBuilder *pBuilder,
    Bitmask mPrereq,                /* Mask of tables that must be used. */
    Bitmask mUsable,                /* Mask of usable tables */
    u16 mExclude,                   /* Exclude terms using these operators */
    sqlite3_index_info *pIdxInfo,   /* Populated object for xBestIndex */
    u16 mNoOmit,                    /* Do not omit these constraints */
    int *pbIn                       /* OUT: True if plan uses an IN(...) op */
  ){
    WhereClause *pWC = pBuilder->pWC;
    struct sqlite3_index_constraint *pIdxCons;
    struct sqlite3_index_constraint_usage *pUsage = pIdxInfo->aConstraintUsage;
    int i;
    int mxTerm;
    int rc = SQLITE_OK;
    WhereLoop *pNew = pBuilder->pNew;
    Parse *pParse = pBuilder->pWInfo->pParse;
    struct SrcList_item *pSrc = &pBuilder->pWInfo->pTabList->a[pNew->iTab];
    int nConstraint = pIdxInfo->nConstraint;
  
    assert( (mUsable & mPrereq)==mPrereq );
    *pbIn = 0;
    pNew->prereq = mPrereq;
  
    /* Set the usable flag on the subset of constraints identified by 
    ** arguments mUsable and mExclude. */
    pIdxCons = *(struct sqlite3_index_constraint**)&pIdxInfo->aConstraint;
    for(i=0; i<nConstraint; i++, pIdxCons++){
      WhereTerm *pTerm = &pWC->a[pIdxCons->iTermOffset];
      pIdxCons->usable = 0;
      if( (pTerm->prereqRight & mUsable)==pTerm->prereqRight 
       && (pTerm->eOperator & mExclude)==0
      ){
        pIdxCons->usable = 1;
      }
    }
  
    /* Initialize the output fields of the sqlite3_index_info structure */
    memset(pUsage, 0, sizeof(pUsage[0])*nConstraint);
    assert( pIdxInfo->needToFreeIdxStr==0 );
    pIdxInfo->idxStr = 0;
    pIdxInfo->idxNum = 0;
    pIdxInfo->orderByConsumed = 0;
    pIdxInfo->estimatedCost = SQLITE_BIG_DBL / (double)2;
    pIdxInfo->estimatedRows = 25;
    pIdxInfo->idxFlags = 0;
    pIdxInfo->colUsed = (sqlite3_int64)pSrc->colUsed;
  
    /* Invoke the virtual table xBestIndex() method */
    rc = vtabBestIndex(pParse, pSrc->pTab, pIdxInfo);
    if( rc ){
      if( rc==SQLITE_CONSTRAINT ){
        /* If the xBestIndex method returns SQLITE_CONSTRAINT, that means
        ** that the particular combination of parameters provided is unusable.
        ** Make no entries in the loop table.
        */
        WHERETRACE(0xffff, ("  ^^^^--- non-viable plan rejected!\n"));
        return SQLITE_OK;
      }
      return rc;
    }
  
    mxTerm = -1;
    assert( pNew->nLSlot>=nConstraint );
    for(i=0; i<nConstraint; i++) pNew->aLTerm[i] = 0;
    pNew->u.vtab.omitMask = 0;
    pIdxCons = *(struct sqlite3_index_constraint**)&pIdxInfo->aConstraint;
    for(i=0; i<nConstraint; i++, pIdxCons++){
      int iTerm;
      if( (iTerm = pUsage[i].argvIndex - 1)>=0 ){
        WhereTerm *pTerm;
        int j = pIdxCons->iTermOffset;
        if( iTerm>=nConstraint
         || j<0
         || j>=pWC->nTerm
         || pNew->aLTerm[iTerm]!=0
         || pIdxCons->usable==0
        ){
          sqlite3ErrorMsg(pParse,"%s.xBestIndex malfunction",pSrc->pTab->zName);
          testcase( pIdxInfo->needToFreeIdxStr );
          return SQLITE_ERROR;
        }
        testcase( iTerm==nConstraint-1 );
        testcase( j==0 );
        testcase( j==pWC->nTerm-1 );
        pTerm = &pWC->a[j];
        pNew->prereq |= pTerm->prereqRight;
        assert( iTerm<pNew->nLSlot );
        pNew->aLTerm[iTerm] = pTerm;
        if( iTerm>mxTerm ) mxTerm = iTerm;
        testcase( iTerm==15 );
        testcase( iTerm==16 );
        if( pUsage[i].omit ){
          if( i<16 && ((1<<i)&mNoOmit)==0 ){
            testcase( i!=iTerm );
            pNew->u.vtab.omitMask |= 1<<iTerm;
          }else{
            testcase( i!=iTerm );
          }
        }
        if( (pTerm->eOperator & WO_IN)!=0 ){
          /* A virtual table that is constrained by an IN clause may not
          ** consume the ORDER BY clause because (1) the order of IN terms
          ** is not necessarily related to the order of output terms and
          ** (2) Multiple outputs from a single IN value will not merge
          ** together.  */
          pIdxInfo->orderByConsumed = 0;
          pIdxInfo->idxFlags &= ~SQLITE_INDEX_SCAN_UNIQUE;
          *pbIn = 1; assert( (mExclude & WO_IN)==0 );
        }
      }
    }
  
    pNew->nLTerm = mxTerm+1;
    for(i=0; i<=mxTerm; i++){
      if( pNew->aLTerm[i]==0 ){
        /* The non-zero argvIdx values must be contiguous.  Raise an
        ** error if they are not */
        sqlite3ErrorMsg(pParse,"%s.xBestIndex malfunction",pSrc->pTab->zName);
        testcase( pIdxInfo->needToFreeIdxStr );
        return SQLITE_ERROR;
      }
    }
    assert( pNew->nLTerm<=pNew->nLSlot );
    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 = (i8)(pIdxInfo->orderByConsumed ?
        pIdxInfo->nOrderBy : 0);
    pNew->rSetup = 0;
    pNew->rRun = sqlite3LogEstFromDouble(pIdxInfo->estimatedCost);
    pNew->nOut = sqlite3LogEst(pIdxInfo->estimatedRows);
  
    /* Set the WHERE_ONEROW flag if the xBestIndex() method indicated
    ** that the scan will visit at most one row. Clear it otherwise. */
    if( pIdxInfo->idxFlags & SQLITE_INDEX_SCAN_UNIQUE ){
      pNew->wsFlags |= WHERE_ONEROW;
    }else{
      pNew->wsFlags &= ~WHERE_ONEROW;
    }
    rc = whereLoopInsert(pBuilder, pNew);
    if( pNew->u.vtab.needFree ){
      sqlite3_free(pNew->u.vtab.idxStr);
      pNew->u.vtab.needFree = 0;
    }
    WHERETRACE(0xffff, ("  bIn=%d prereqIn=%04llx prereqOut=%04llx\n",
                        *pbIn, (sqlite3_uint64)mPrereq,
                        (sqlite3_uint64)(pNew->prereq & ~mPrereq)));
  
    return rc;
  }
  
  /*
  ** If this function is invoked from within an xBestIndex() callback, it
  ** returns a pointer to a buffer containing the name of the collation
  ** sequence associated with element iCons of the sqlite3_index_info.aConstraint
  ** array. Or, if iCons is out of range or there is no active xBestIndex
  ** call, return NULL.
  */
  const char *sqlite3_vtab_collation(sqlite3_index_info *pIdxInfo, int iCons){
    HiddenIndexInfo *pHidden = (HiddenIndexInfo*)&pIdxInfo[1];
    const char *zRet = 0;
    if( iCons>=0 && iCons<pIdxInfo->nConstraint ){
      CollSeq *pC = 0;
      int iTerm = pIdxInfo->aConstraint[iCons].iTermOffset;
      Expr *pX = pHidden->pWC->a[iTerm].pExpr;
      if( pX->pLeft ){
        pC = sqlite3ExprCompareCollSeq(pHidden->pParse, pX);
      }
      zRet = (pC ? pC->zName : sqlite3StrBINARY);
    }
    return zRet;
  }
  
  /*
  ** Add all WhereLoop objects for a table of the join identified by
  ** pBuilder->pNew->iTab.  That table is guaranteed to be a virtual table.
  **
  ** If there are no LEFT or CROSS JOIN joins in the query, both mPrereq and
  ** mUnusable are set to 0. Otherwise, mPrereq is a mask of all FROM clause
  ** entries that occur before the virtual table in the FROM clause and are
  ** separated from it by at least one LEFT or CROSS JOIN. Similarly, the
  ** mUnusable mask contains all FROM clause entries that occur after the
  ** virtual table and are separated from it by at least one LEFT or 
  ** CROSS JOIN. 
  **
  ** For example, if the query were:
  **
  **   ... FROM t1, t2 LEFT JOIN t3, t4, vt CROSS JOIN t5, t6;
  **
  ** then mPrereq corresponds to (t1, t2) and mUnusable to (t5, t6).
  **
  ** All the tables in mPrereq must be scanned before the current virtual 
  ** table. So any terms for which all prerequisites are satisfied by 
  ** mPrereq may be specified as "usable" in all calls to xBestIndex. 
  ** Conversely, all tables in mUnusable must be scanned after the current
  ** virtual table, so any terms for which the prerequisites overlap with
  ** mUnusable should always be configured as "not-usable" for xBestIndex.
  */
  int whereLoopAddVirtual(
    WhereLoopBuilder *pBuilder,  /* WHERE clause information */
    Bitmask mPrereq,             /* Tables that must be scanned before this one */
    Bitmask mUnusable            /* Tables that must be scanned after this one */
  ){
    int rc = SQLITE_OK;          /* Return code */
    WhereInfo *pWInfo;           /* WHERE analysis context */
    Parse *pParse;               /* The parsing context */
    WhereClause *pWC;            /* The WHERE clause */
    struct SrcList_item *pSrc;   /* The FROM clause term to search */
    sqlite3_index_info *p;       /* Object to pass to xBestIndex() */
    int nConstraint;             /* Number of constraints in p */
    int bIn;                     /* True if plan uses IN(...) operator */
    WhereLoop *pNew;
    Bitmask mBest;               /* Tables used by best possible plan */
    u16 mNoOmit;
  
    assert( (mPrereq & mUnusable)==0 );
    pWInfo = pBuilder->pWInfo;
    pParse = pWInfo->pParse;
    pWC = pBuilder->pWC;
    pNew = pBuilder->pNew;
    pSrc = &pWInfo->pTabList->a[pNew->iTab];
    assert( IsVirtual(pSrc->pTab) );
    p = allocateIndexInfo(pParse, pWC, mUnusable, pSrc, pBuilder->pOrderBy, 
        &mNoOmit);
    if( p==0 ) return SQLITE_NOMEM_BKPT;
    pNew->rSetup = 0;
    pNew->wsFlags = WHERE_VIRTUALTABLE;
    pNew->nLTerm = 0;
    pNew->u.vtab.needFree = 0;
    nConstraint = p->nConstraint;
    if( whereLoopResize(pParse->db, pNew, nConstraint) ){
      sqlite3DbFree(pParse->db, p);
      return SQLITE_NOMEM_BKPT;
    }
  
    /* First call xBestIndex() with all constraints usable. */
    WHERETRACE(0x800, ("BEGIN %s.addVirtual()\n", pSrc->pTab->zName));
    WHERETRACE(0x40, ("  VirtualOne: all usable\n"));
    rc = whereLoopAddVirtualOne(pBuilder, mPrereq, ALLBITS, 0, p, mNoOmit, &bIn);
  
    /* If the call to xBestIndex() with all terms enabled produced a plan
    ** that does not require any source tables (IOW: a plan with mBest==0)
    ** and does not use an IN(...) operator, then there is no point in making 
    ** any further calls to xBestIndex() since they will all return the same
    ** result (if the xBestIndex() implementation is sane). */
    if( rc==SQLITE_OK && ((mBest = (pNew->prereq & ~mPrereq))!=0 || bIn) ){
      int seenZero = 0;             /* True if a plan with no prereqs seen */
      int seenZeroNoIN = 0;         /* Plan with no prereqs and no IN(...) seen */
      Bitmask mPrev = 0;
      Bitmask mBestNoIn = 0;
  
      /* If the plan produced by the earlier call uses an IN(...) term, call
      ** xBestIndex again, this time with IN(...) terms disabled. */
      if( bIn ){
        WHERETRACE(0x40, ("  VirtualOne: all usable w/o IN\n"));
        rc = whereLoopAddVirtualOne(
            pBuilder, mPrereq, ALLBITS, WO_IN, p, mNoOmit, &bIn);
        assert( bIn==0 );
        mBestNoIn = pNew->prereq & ~mPrereq;
        if( mBestNoIn==0 ){
          seenZero = 1;
          seenZeroNoIN = 1;
        }
      }
  
      /* Call xBestIndex once for each distinct value of (prereqRight & ~mPrereq) 
      ** in the set of terms that apply to the current virtual table.  */
      while( rc==SQLITE_OK ){
        int i;
        Bitmask mNext = ALLBITS;
        assert( mNext>0 );
        for(i=0; i<nConstraint; i++){
          Bitmask mThis = (
              pWC->a[p->aConstraint[i].iTermOffset].prereqRight & ~mPrereq
          );
          if( mThis>mPrev && mThis<mNext ) mNext = mThis;
        }
        mPrev = mNext;
        if( mNext==ALLBITS ) break;
        if( mNext==mBest || mNext==mBestNoIn ) continue;
        WHERETRACE(0x40, ("  VirtualOne: mPrev=%04llx mNext=%04llx\n",
                         (sqlite3_uint64)mPrev, (sqlite3_uint64)mNext));
        rc = whereLoopAddVirtualOne(
            pBuilder, mPrereq, mNext|mPrereq, 0, p, mNoOmit, &bIn);
        if( pNew->prereq==mPrereq ){
          seenZero = 1;
          if( bIn==0 ) seenZeroNoIN = 1;
        }
      }
  
      /* If the calls to xBestIndex() in the above loop did not find a plan
      ** that requires no source tables at all (i.e. one guaranteed to be
      ** usable), make a call here with all source tables disabled */
      if( rc==SQLITE_OK && seenZero==0 ){
        WHERETRACE(0x40, ("  VirtualOne: all disabled\n"));
        rc = whereLoopAddVirtualOne(
            pBuilder, mPrereq, mPrereq, 0, p, mNoOmit, &bIn);
        if( bIn==0 ) seenZeroNoIN = 1;
      }
  
      /* If the calls to xBestIndex() have so far failed to find a plan
      ** that requires no source tables at all and does not use an IN(...)
      ** operator, make a final call to obtain one here.  */
      if( rc==SQLITE_OK && seenZeroNoIN==0 ){
        WHERETRACE(0x40, ("  VirtualOne: all disabled and w/o IN\n"));
        rc = whereLoopAddVirtualOne(
            pBuilder, mPrereq, mPrereq, WO_IN, p, mNoOmit, &bIn);
      }
    }
  
    if( p->needToFreeIdxStr ) sqlite3_free(p->idxStr);
    sqlite3DbFreeNN(pParse->db, p);
    WHERETRACE(0x800, ("END %s.addVirtual(), rc=%d\n", pSrc->pTab->zName, rc));
    return rc;
  }
  #endif /* SQLITE_OMIT_VIRTUALTABLE */
  
  /*
  ** Add WhereLoop entries to handle OR terms.  This works for either
  ** btrees or virtual tables.
  */
  int whereLoopAddOr(
    WhereLoopBuilder *pBuilder, 
    Bitmask mPrereq, 
    Bitmask mUnusable
  ){
    WhereInfo *pWInfo = pBuilder->pWInfo;
    WhereClause *pWC;
    WhereLoop *pNew;
    WhereTerm *pTerm, *pWCEnd;
    int rc = SQLITE_OK;
    int iCur;
    WhereClause tempWC;
    WhereLoopBuilder sSubBuild;
    WhereOrSet sSum, sCur;
    struct SrcList_item *pItem;
    
    pWC = pBuilder->pWC;
    pWCEnd = pWC->a + pWC->nTerm;
    pNew = pBuilder->pNew;
    memset(&sSum, 0, sizeof(sSum));
    pItem = pWInfo->pTabList->a + pNew->iTab;
    iCur = pItem->iCursor;
  
    for(pTerm=pWC->a; pTerm<pWCEnd && rc==SQLITE_OK; pTerm++){
      if( (pTerm->eOperator & WO_OR)!=0
       && (pTerm->u.pOrInfo->indexable & pNew->maskSelf)!=0 
      ){
        WhereClause * const pOrWC = &pTerm->u.pOrInfo->wc;
        WhereTerm * const pOrWCEnd = &pOrWC->a[pOrWC->nTerm];
        WhereTerm *pOrTerm;
        int once = 1;
        int i, j;
      
        sSubBuild = *pBuilder;
        sSubBuild.pOrderBy = 0;
        sSubBuild.pOrSet = &sCur;
  
        WHERETRACE(0x200, ("Begin processing OR-clause %p\n", pTerm));
        for(pOrTerm=pOrWC->a; pOrTerm<pOrWCEnd; pOrTerm++){
          if( (pOrTerm->eOperator & WO_AND)!=0 ){
            sSubBuild.pWC = &pOrTerm->u.pAndInfo->wc;
          }else if( pOrTerm->leftCursor==iCur ){
            tempWC.pWInfo = pWC->pWInfo;
            tempWC.pOuter = pWC;
            tempWC.op = TK_AND;
            tempWC.nTerm = 1;
            tempWC.a = pOrTerm;
            sSubBuild.pWC = &tempWC;
          }else{
            continue;
          }
          sCur.n = 0;
  #ifdef WHERETRACE_ENABLED
          WHERETRACE(0x200, ("OR-term %d of %p has %d subterms:\n", 
                     (int)(pOrTerm-pOrWC->a), pTerm, sSubBuild.pWC->nTerm));
          if( sqlite3WhereTrace & 0x400 ){
            sqlite3WhereClausePrint(sSubBuild.pWC);
          }
  #endif
  #ifndef SQLITE_OMIT_VIRTUALTABLE
          if( IsVirtual(pItem->pTab) ){
            rc = whereLoopAddVirtual(&sSubBuild, mPrereq, mUnusable);
          }else
  #endif
          {
            rc = whereLoopAddBtree(&sSubBuild, mPrereq);
          }
          if( rc==SQLITE_OK ){
            rc = whereLoopAddOr(&sSubBuild, mPrereq, mUnusable);
          }
          assert( rc==SQLITE_OK || rc==SQLITE_DONE || sCur.n==0 );
          testcase( rc==SQLITE_DONE );
          if( sCur.n==0 ){
            sSum.n = 0;
            break;
          }else if( once ){
            whereOrMove(&sSum, &sCur);
            once = 0;
          }else{
            WhereOrSet sPrev;
            whereOrMove(&sPrev, &sSum);
            sSum.n = 0;
            for(i=0; i<sPrev.n; i++){
              for(j=0; j<sCur.n; j++){
                whereOrInsert(&sSum, sPrev.a[i].prereq | sCur.a[j].prereq,
                              sqlite3LogEstAdd(sPrev.a[i].rRun, sCur.a[j].rRun),
                              sqlite3LogEstAdd(sPrev.a[i].nOut, sCur.a[j].nOut));
              }
            }
          }
        }
        pNew->nLTerm = 1;
        pNew->aLTerm[0] = pTerm;
        pNew->wsFlags = WHERE_MULTI_OR;
        pNew->rSetup = 0;
        pNew->iSortIdx = 0;
        memset(&pNew->u, 0, sizeof(pNew->u));
        for(i=0; rc==SQLITE_OK && i<sSum.n; i++){
          /* TUNING: Currently sSum.a[i].rRun is set to the sum of the costs
          ** of all sub-scans required by the OR-scan. However, due to rounding
          ** errors, it may be that the cost of the OR-scan is equal to its
          ** most expensive sub-scan. Add the smallest possible penalty 
          ** (equivalent to multiplying the cost by 1.07) to ensure that 
          ** this does not happen. Otherwise, for WHERE clauses such as the
          ** following where there is an index on "y":
          **
          **     WHERE likelihood(x=?, 0.99) OR y=?
          **
          ** the planner may elect to "OR" together a full-table scan and an
          ** index lookup. And other similarly odd results.  */
          pNew->rRun = sSum.a[i].rRun + 1;
          pNew->nOut = sSum.a[i].nOut;
          pNew->prereq = sSum.a[i].prereq;
          rc = whereLoopInsert(pBuilder, pNew);
        }
        WHERETRACE(0x200, ("End processing OR-clause %p\n", pTerm));
      }
    }
    return rc;
  }
  
  /*
  ** Add all WhereLoop objects for all tables 
  */
  int whereLoopAddAll(WhereLoopBuilder *pBuilder){
    WhereInfo *pWInfo = pBuilder->pWInfo;
    Bitmask mPrereq = 0;
    Bitmask mPrior = 0;
    int iTab;
    SrcList *pTabList = pWInfo->pTabList;
    struct SrcList_item *pItem;
    struct SrcList_item *pEnd = &pTabList->a[pWInfo->nLevel];
    sqlite3 *db = pWInfo->pParse->db;
    int rc = SQLITE_OK;
    WhereLoop *pNew;
    u8 priorJointype = 0;
  
    /* Loop over the tables in the join, from left to right */
    pNew = pBuilder->pNew;
    whereLoopInit(pNew);
    pBuilder->iPlanLimit = SQLITE_QUERY_PLANNER_LIMIT;
    for(iTab=0, pItem=pTabList->a; pItem<pEnd; iTab++, pItem++){
      Bitmask mUnusable = 0;
      pNew->iTab = iTab;
      pBuilder->iPlanLimit += SQLITE_QUERY_PLANNER_LIMIT_INCR;
      pNew->maskSelf = sqlite3WhereGetMask(&pWInfo->sMaskSet, pItem->iCursor);
      if( ((pItem->fg.jointype|priorJointype) & (JT_LEFT|JT_CROSS))!=0 ){
        /* This condition is true when pItem is the FROM clause term on the
        ** right-hand-side of a LEFT or CROSS JOIN.  */
        mPrereq = mPrior;
      }
      priorJointype = pItem->fg.jointype;
  #ifndef SQLITE_OMIT_VIRTUALTABLE
      if( IsVirtual(pItem->pTab) ){
        struct SrcList_item *p;
        for(p=&pItem[1]; p<pEnd; p++){
          if( mUnusable || (p->fg.jointype & (JT_LEFT|JT_CROSS)) ){
            mUnusable |= sqlite3WhereGetMask(&pWInfo->sMaskSet, p->iCursor);
          }
        }
        rc = whereLoopAddVirtual(pBuilder, mPrereq, mUnusable);
      }else
  #endif /* SQLITE_OMIT_VIRTUALTABLE */
      {
        rc = whereLoopAddBtree(pBuilder, mPrereq);
      }
      if( rc==SQLITE_OK && pBuilder->pWC->hasOr ){
        rc = whereLoopAddOr(pBuilder, mPrereq, mUnusable);
      }
      mPrior |= pNew->maskSelf;
      if( rc || db->mallocFailed ){
        if( rc==SQLITE_DONE ){
          /* We hit the query planner search limit set by iPlanLimit */
          sqlite3_log(SQLITE_WARNING, "abbreviated query algorithm search");
          rc = SQLITE_OK;
        }else{
          break;
        }
      }
    }
  
    whereLoopClear(db, pNew);
    return rc;
  }
  
  /*
  ** Examine a WherePath (with the addition of the extra WhereLoop of the 6th
  ** parameters) to see if it outputs rows in the requested ORDER BY
  ** (or GROUP BY) without requiring a separate sort operation.  Return N:
  ** 
  **   N>0:   N terms of the ORDER BY clause are satisfied
  **   N==0:  No terms of the ORDER BY clause are satisfied
  **   N<0:   Unknown yet how many terms of ORDER BY might be satisfied.   
  **
  ** Note that processing for WHERE_GROUPBY and WHERE_DISTINCTBY is not as
  ** strict.  With GROUP BY and DISTINCT the only requirement is that
  ** equivalent rows appear immediately adjacent to one another.  GROUP BY
  ** and DISTINCT do not require rows to appear in any particular order as long
  ** as equivalent rows are grouped together.  Thus for GROUP BY and DISTINCT
  ** the pOrderBy terms can be matched in any order.  With ORDER BY, the 
  ** pOrderBy terms must be matched in strict left-to-right order.
  */
  i8 wherePathSatisfiesOrderBy(
    WhereInfo *pWInfo,    /* The WHERE clause */
    ExprList *pOrderBy,   /* ORDER BY or GROUP BY or DISTINCT clause to check */
    WherePath *pPath,     /* The WherePath to check */
    u16 wctrlFlags,       /* WHERE_GROUPBY or _DISTINCTBY or _ORDERBY_LIMIT */
    u16 nLoop,            /* Number of entries in pPath->aLoop[] */
    WhereLoop *pLast,     /* Add this WhereLoop to the end of pPath->aLoop[] */
    Bitmask *pRevMask     /* OUT: 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 eqOpMask;         /* Allowed equality operators */
    u16 nKeyCol;          /* Number of key columns in pIndex */
    u16 nColumn;          /* Total number of ordered columns in the index */
    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 = 0; /* Current WhereLoop being processed. */
    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 */
    Bitmask ready;              /* Mask of inner loops */
  
    /*
    ** 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 );
    if( nLoop && OptimizationDisabled(db, SQLITE_OrderByIdxJoin) ) return 0;
  
    nOrderBy = pOrderBy->nExpr;
    testcase( nOrderBy==BMS-1 );
    if( nOrderBy>BMS-1 ) return 0;  /* Cannot optimize overly large ORDER BYs */
    isOrderDistinct = 1;
    obDone = MASKBIT(nOrderBy)-1;
    orderDistinctMask = 0;
    ready = 0;
    eqOpMask = WO_EQ | WO_IS | WO_ISNULL;
    if( wctrlFlags & WHERE_ORDERBY_LIMIT ) eqOpMask |= WO_IN;
    for(iLoop=0; isOrderDistinct && obSat<obDone && iLoop<=nLoop; iLoop++){
      if( iLoop>0 ) ready |= pLoop->maskSelf;
      if( iLoop<nLoop ){
        pLoop = pPath->aLoop[iLoop];
        if( wctrlFlags & WHERE_ORDERBY_LIMIT ) continue;
      }else{
        pLoop = pLast;
      }
      if( pLoop->wsFlags & WHERE_VIRTUALTABLE ){
        if( pLoop->u.vtab.isOrdered && (wctrlFlags & WHERE_DISTINCTBY)==0 ){
          obSat = obDone;
        }
        break;
      }else if( wctrlFlags & WHERE_DISTINCTBY ){
        pLoop->u.btree.nDistinctCol = 0;
      }
      iCur = pWInfo->pTabList->a[pLoop->iTab].iCursor;
  
      /* Mark off any ORDER BY term X that is a column in the table of
      ** the current loop for which there is term in the WHERE
      ** clause of the form X IS NULL or X=? that reference only outer
      ** loops.
      */
      for(i=0; i<nOrderBy; i++){
        if( MASKBIT(i) & obSat ) continue;
        pOBExpr = sqlite3ExprSkipCollateAndLikely(pOrderBy->a[i].pExpr);
        if( pOBExpr->op!=TK_COLUMN ) continue;
        if( pOBExpr->iTable!=iCur ) continue;
        pTerm = sqlite3WhereFindTerm(&pWInfo->sWC, iCur, pOBExpr->iColumn,
                         ~ready, eqOpMask, 0);
        if( pTerm==0 ) continue;
        if( pTerm->eOperator==WO_IN ){
          /* IN terms are only valid for sorting in the ORDER BY LIMIT 
          ** optimization, and then only if they are actually used
          ** by the query plan */
          assert( wctrlFlags & WHERE_ORDERBY_LIMIT );
          for(j=0; j<pLoop->nLTerm && pTerm!=pLoop->aLTerm[j]; j++){}
          if( j>=pLoop->nLTerm ) continue;
        }
        if( (pTerm->eOperator&(WO_EQ|WO_IS))!=0 && pOBExpr->iColumn>=0 ){
          Parse *pParse = pWInfo->pParse;
          CollSeq *pColl1 = sqlite3ExprNNCollSeq(pParse, pOrderBy->a[i].pExpr);
          CollSeq *pColl2 = sqlite3ExprCompareCollSeq(pParse, pTerm->pExpr);
          assert( pColl1 );
          if( pColl2==0 || sqlite3StrICmp(pColl1->zName, pColl2->zName) ){
            continue;
          }
          testcase( pTerm->pExpr->op==TK_IS );
        }
        obSat |= MASKBIT(i);
      }
  
      if( (pLoop->wsFlags & WHERE_ONEROW)==0 ){
        if( pLoop->wsFlags & WHERE_IPK ){
          pIndex = 0;
          nKeyCol = 0;
          nColumn = 1;
        }else if( (pIndex = pLoop->u.btree.pIndex)==0 || pIndex->bUnordered ){
          return 0;
        }else{
          nKeyCol = pIndex->nKeyCol;
          nColumn = pIndex->nColumn;
          assert( nColumn==nKeyCol+1 || !HasRowid(pIndex->pTable) );
          assert( pIndex->aiColumn[nColumn-1]==XN_ROWID
                            || !HasRowid(pIndex->pTable));
          isOrderDistinct = IsUniqueIndex(pIndex)
                            && (pLoop->wsFlags & WHERE_SKIPSCAN)==0;
        }
  
        /* 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 = 1; /* True to run the ORDER BY search loop */
  
          assert( j>=pLoop->u.btree.nEq 
              || (pLoop->aLTerm[j]==0)==(j<pLoop->nSkip)
          );
          if( j<pLoop->u.btree.nEq && j>=pLoop->nSkip ){
            u16 eOp = pLoop->aLTerm[j]->eOperator;
  
            /* Skip over == and IS and ISNULL terms.  (Also skip IN terms when
            ** doing WHERE_ORDERBY_LIMIT processing).  Except, IS and ISNULL
            ** terms imply that the index is not UNIQUE NOT NULL in which case
            ** the loop need to be marked as not order-distinct because it can
            ** have repeated NULL rows.
            **
            ** If the current term is a column of an ((?,?) IN (SELECT...)) 
            ** expression for which the SELECT returns more than one column,
            ** check that it is the only column used by this loop. Otherwise,
            ** if it is one of two or more, none of the columns can be
            ** considered to match an ORDER BY term.
            */
            if( (eOp & eqOpMask)!=0 ){
              if( eOp & (WO_ISNULL|WO_IS) ){
                testcase( eOp & WO_ISNULL );
                testcase( eOp & WO_IS );
                testcase( isOrderDistinct );
                isOrderDistinct = 0;
              }
              continue;  
            }else if( ALWAYS(eOp & WO_IN) ){
              /* ALWAYS() justification: eOp is an equality operator due to the
              ** j<pLoop->u.btree.nEq constraint above.  Any equality other
              ** than WO_IN is captured by the previous "if".  So this one
              ** always has to be WO_IN. */
              Expr *pX = pLoop->aLTerm[j]->pExpr;
              for(i=j+1; i<pLoop->u.btree.nEq; i++){
                if( pLoop->aLTerm[i]->pExpr==pX ){
                  assert( (pLoop->aLTerm[i]->eOperator & WO_IN) );
                  bOnce = 0;
                  break;
                }
              }
            }
          }
  
          /* Get the column number in the table (iColumn) and sort order
          ** (revIdx) for the j-th column of the index.
          */
          if( pIndex ){
            iColumn = pIndex->aiColumn[j];
            revIdx = pIndex->aSortOrder[j] & KEYINFO_ORDER_DESC;
            if( iColumn==pIndex->pTable->iPKey ) iColumn = XN_ROWID;
          }else{
            iColumn = XN_ROWID;
            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 mark that ORDER BY term off 
          */
          isMatch = 0;
          for(i=0; bOnce && i<nOrderBy; i++){
            if( MASKBIT(i) & obSat ) continue;
            pOBExpr = sqlite3ExprSkipCollateAndLikely(pOrderBy->a[i].pExpr);
            testcase( wctrlFlags & WHERE_GROUPBY );
            testcase( wctrlFlags & WHERE_DISTINCTBY );
            if( (wctrlFlags & (WHERE_GROUPBY|WHERE_DISTINCTBY))==0 ) bOnce = 0;
            if( iColumn>=XN_ROWID ){
              if( pOBExpr->op!=TK_COLUMN ) continue;
              if( pOBExpr->iTable!=iCur ) continue;
              if( pOBExpr->iColumn!=iColumn ) continue;
            }else{
              Expr *pIdxExpr = pIndex->aColExpr->a[j].pExpr;
              if( sqlite3ExprCompareSkip(pOBExpr, pIdxExpr, iCur) ){
                continue;
              }
            }
            if( iColumn!=XN_ROWID ){
              pColl = sqlite3ExprNNCollSeq(pWInfo->pParse, pOrderBy->a[i].pExpr);
              if( sqlite3StrICmp(pColl->zName, pIndex->azColl[j])!=0 ) continue;
            }
            if( wctrlFlags & WHERE_DISTINCTBY ){
              pLoop->u.btree.nDistinctCol = j+1;
            }
            isMatch = 1;
            break;
          }
          if( isMatch && (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].sortFlags&KEYINFO_ORDER_DESC) ){
                isMatch = 0;
              }
            }else{
              rev = revIdx ^ (pOrderBy->a[i].sortFlags & KEYINFO_ORDER_DESC);
              if( rev ) *pRevMask |= MASKBIT(iLoop);
              revSet = 1;
            }
          }
          if( isMatch && (pOrderBy->a[i].sortFlags & KEYINFO_ORDER_BIGNULL) ){
            if( j==pLoop->u.btree.nEq ){
              pLoop->wsFlags |= WHERE_BIGNULL_SORT;
            }else{
              isMatch = 0;
            }
          }
          if( isMatch ){
            if( iColumn==XN_ROWID ){
              testcase( distinctColumns==0 );
              distinctColumns = 1;
            }
            obSat |= MASKBIT(i);
          }else{
            /* No match found */
            if( j==0 || j<nKeyCol ){
              testcase( isOrderDistinct!=0 );
              isOrderDistinct = 0;
            }
            break;
          }
        } /* end Loop over all index columns */
        if( distinctColumns ){
          testcase( isOrderDistinct==0 );
          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;
          Bitmask mTerm;
          if( MASKBIT(i) & obSat ) continue;
          p = pOrderBy->a[i].pExpr;
          mTerm = sqlite3WhereExprUsage(&pWInfo->sMaskSet,p);
          if( mTerm==0 && !sqlite3ExprIsConstant(p) ) continue;
          if( (mTerm&~orderDistinctMask)==0 ){
            obSat |= MASKBIT(i);
          }
        }
      }
    } /* End the loop over all WhereLoops from outer-most down to inner-most */
    if( obSat==obDone ) return (i8)nOrderBy;
    if( !isOrderDistinct ){
      for(i=nOrderBy-1; i>0; i--){
        Bitmask m = MASKBIT(i) - 1;
        if( (obSat&m)==m ) return i;
      }
      return 0;
    }
    return -1;
  }
  
  
  /*
  ** If the WHERE_GROUPBY flag is set in the mask passed to sqlite3WhereBegin(),
  ** the planner assumes that the specified pOrderBy list is actually a GROUP
  ** BY clause - and so any order that groups rows as required satisfies the
  ** request.
  **
  ** Normally, in this case it is not possible for the caller to determine
  ** whether or not the rows are really being delivered in sorted order, or
  ** just in some other order that provides the required grouping. However,
  ** if the WHERE_SORTBYGROUP flag is also passed to sqlite3WhereBegin(), then
  ** this function may be called on the returned WhereInfo object. It returns
  ** true if the rows really will be sorted in the specified order, or false
  ** otherwise.
  **
  ** For example, assuming:
  **
  **   CREATE INDEX i1 ON t1(x, Y);
  **
  ** then
  **
  **   SELECT * FROM t1 GROUP BY x,y ORDER BY x,y;   -- IsSorted()==1
  **   SELECT * FROM t1 GROUP BY y,x ORDER BY y,x;   -- IsSorted()==0
  */
  int sqlite3WhereIsSorted(WhereInfo *pWInfo){
    assert( pWInfo->wctrlFlags & WHERE_GROUPBY );
    assert( pWInfo->wctrlFlags & WHERE_SORTBYGROUP );
    return pWInfo->sorted;
  }
  
  #ifdef WHERETRACE_ENABLED
  /* For debugging use only: */
  const char *wherePathName(WherePath *pPath, int nLoop, WhereLoop *pLast){
    static char zName[65];
    int i;
    for(i=0; i<nLoop; i++){ zName[i] = pPath->aLoop[i]->cId; }
    if( pLast ) zName[i++] = pLast->cId;
    zName[i] = 0;
    return zName;
  }
  #endif
  
  /*
  ** Return the cost of sorting nRow rows, assuming that the keys have 
  ** nOrderby columns and that the first nSorted columns are already in
  ** order.
  */
  LogEst whereSortingCost(
    WhereInfo *pWInfo,
    LogEst nRow,
    int nOrderBy,
    int nSorted
  ){
    /* TUNING: Estimated cost of a full external sort, where N is 
    ** the number of rows to sort is:
    **
    **   cost = (3.0 * N * log(N)).
    ** 
    ** Or, if the order-by clause has X terms but only the last Y 
    ** terms are out of order, then block-sorting will reduce the 
    ** sorting cost to:
    **
    **   cost = (3.0 * N * log(N)) * (Y/X)
    **
    ** The (Y/X) term is implemented using stack variable rScale
    ** below.  */
    LogEst rScale, rSortCost;
    assert( nOrderBy>0 && 66==sqlite3LogEst(100) );
    rScale = sqlite3LogEst((nOrderBy-nSorted)*100/nOrderBy) - 66;
    rSortCost = nRow + rScale + 16;
  
    /* Multiple by log(M) where M is the number of output rows.
    ** Use the LIMIT for M if it is smaller */
    if( (pWInfo->wctrlFlags & WHERE_USE_LIMIT)!=0 && pWInfo->iLimit<nRow ){
      nRow = pWInfo->iLimit;
    }
    rSortCost += estLog(nRow);
    return rSortCost;
  }
  
  /*
  ** Given the list of WhereLoop objects at 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.
  **
  ** Assume that the total number of output rows that will need to be sorted
  ** will be nRowEst (in the 10*log2 representation).  Or, ignore sorting
  ** costs if nRowEst==0.
  **
  ** Return SQLITE_OK on success or SQLITE_NOMEM of a memory allocation
  ** error occurs.
  */
  int wherePathSolver(WhereInfo *pWInfo, LogEst nRowEst){
    int mxChoice;             /* Maximum number of simultaneous paths tracked */
    int nLoop;                /* Number of terms in the join */
    Parse *pParse;            /* Parsing context */
    sqlite3 *db;              /* The database connection */
    int iLoop;                /* Loop counter over the terms of the join */
    int ii, jj;               /* Loop counters */
    int mxI = 0;              /* Index of next entry to replace */
    int nOrderBy;             /* Number of ORDER BY clause terms */
    LogEst mxCost = 0;        /* Maximum cost of a set of paths */
    LogEst mxUnsorted = 0;    /* Maximum unsorted cost of a set of path */
    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 **pX;           /* Used to divy up the pSpace memory */
    LogEst *aSortCost = 0;    /* Sorting and partial sorting costs */
    char *pSpace;             /* Temporary memory used by this routine */
    int nSpace;               /* Bytes of space allocated at pSpace */
  
    pParse = pWInfo->pParse;
    db = pParse->db;
    nLoop = pWInfo->nLevel;
    /* TUNING: For simple queries, only the best path is tracked.
    ** For 2-way joins, the 5 best paths are followed.
    ** For joins of 3 or more tables, track the 10 best paths */
    mxChoice = (nLoop<=1) ? 1 : (nLoop==2 ? 5 : 10);
    assert( nLoop<=pWInfo->pTabList->nSrc );
    WHERETRACE(0x002, ("---- begin solver.  (nRowEst=%d)\n", nRowEst));
  
    /* If nRowEst is zero and there is an ORDER BY clause, ignore it. In this
    ** case the purpose of this call is to estimate the number of rows returned
    ** by the overall query. Once this estimate has been obtained, the caller
    ** will invoke this function a second time, passing the estimate as the
    ** nRowEst parameter.  */
    if( pWInfo->pOrderBy==0 || nRowEst==0 ){
      nOrderBy = 0;
    }else{
      nOrderBy = pWInfo->pOrderBy->nExpr;
    }
  
    /* Allocate and initialize space for aTo, aFrom and aSortCost[] */
    nSpace = (sizeof(WherePath)+sizeof(WhereLoop*)*nLoop)*mxChoice*2;
    nSpace += sizeof(LogEst) * nOrderBy;
    pSpace = sqlite3DbMallocRawNN(db, nSpace);
    if( pSpace==0 ) return SQLITE_NOMEM_BKPT;
    aTo = (WherePath*)pSpace;
    aFrom = aTo+mxChoice;
    memset(aFrom, 0, sizeof(aFrom[0]));
    pX = (WhereLoop**)(aFrom+mxChoice);
    for(ii=mxChoice*2, pFrom=aTo; ii>0; ii--, pFrom++, pX += nLoop){
      pFrom->aLoop = pX;
    }
    if( nOrderBy ){
      /* If there is an ORDER BY clause and it is not being ignored, set up
      ** space for the aSortCost[] array. Each element of the aSortCost array
      ** is either zero - meaning it has not yet been initialized - or the
      ** cost of sorting nRowEst rows of data where the first X terms of
      ** the ORDER BY clause are already in order, where X is the array 
      ** index.  */
      aSortCost = (LogEst*)pX;
      memset(aSortCost, 0, sizeof(LogEst) * nOrderBy);
    }
    assert( aSortCost==0 || &pSpace[nSpace]==(char*)&aSortCost[nOrderBy] );
    assert( aSortCost!=0 || &pSpace[nSpace]==(char*)pX );
  
    /* Seed the search with a single WherePath containing zero WhereLoops.
    **
    ** TUNING: Do not let the number of iterations go above 28.  If the cost
    ** of computing an automatic index is not paid back within the first 28
    ** rows, then do not use the automatic index. */
    aFrom[0].nRow = MIN(pParse->nQueryLoop, 48);  assert( 48==sqlite3LogEst(28) );
    nFrom = 1;
    assert( aFrom[0].isOrdered==0 );
    if( nOrderBy ){
      /* If nLoop is zero, then there are no FROM terms in the query. Since
      ** in this case the query may return a maximum of one row, the results
      ** are already in the requested order. Set isOrdered to nOrderBy to
      ** indicate this. Or, if nLoop is greater than zero, set isOrdered to
      ** -1, indicating that the result set may or may not be ordered, 
      ** depending on the loops added to the current plan.  */
      aFrom[0].isOrdered = nLoop>0 ? -1 : nOrderBy;
    }
  
    /* 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){
          LogEst nOut;                      /* Rows visited by (pFrom+pWLoop) */
          LogEst rCost;                     /* Cost of path (pFrom+pWLoop) */
          LogEst rUnsorted;                 /* Unsorted cost of (pFrom+pWLoop) */
          i8 isOrdered = pFrom->isOrdered;  /* isOrdered for (pFrom+pWLoop) */
          Bitmask maskNew;                  /* Mask of src visited by (..) */
          Bitmask revMask = 0;              /* Mask of rev-order loops for (..) */
  
          if( (pWLoop->prereq & ~pFrom->maskLoop)!=0 ) continue;
          if( (pWLoop->maskSelf & pFrom->maskLoop)!=0 ) continue;
          if( (pWLoop->wsFlags & WHERE_AUTO_INDEX)!=0 && pFrom->nRow<3 ){
            /* Do not use an automatic index if the this loop is expected
            ** to run less than 1.25 times.  It is tempting to also exclude
            ** automatic index usage on an outer loop, but sometimes an automatic
            ** index is useful in the outer loop of a correlated subquery. */
            assert( 10==sqlite3LogEst(2) );
            continue;
          }
  
          /* At this point, pWLoop is a candidate to be the next loop. 
          ** Compute its cost */
          rUnsorted = sqlite3LogEstAdd(pWLoop->rSetup,pWLoop->rRun + pFrom->nRow);
          rUnsorted = sqlite3LogEstAdd(rUnsorted, pFrom->rUnsorted);
          nOut = pFrom->nRow + pWLoop->nOut;
          maskNew = pFrom->maskLoop | pWLoop->maskSelf;
          if( isOrdered<0 ){
            isOrdered = wherePathSatisfiesOrderBy(pWInfo,
                         pWInfo->pOrderBy, pFrom, pWInfo->wctrlFlags,
                         iLoop, pWLoop, &revMask);
          }else{
            revMask = pFrom->revLoop;
          }
          if( isOrdered>=0 && isOrdered<nOrderBy ){
            if( aSortCost[isOrdered]==0 ){
              aSortCost[isOrdered] = whereSortingCost(
                  pWInfo, nRowEst, nOrderBy, isOrdered
              );
            }
            /* TUNING:  Add a small extra penalty (5) to sorting as an
            ** extra encouragment to the query planner to select a plan
            ** where the rows emerge in the correct order without any sorting
            ** required. */
            rCost = sqlite3LogEstAdd(rUnsorted, aSortCost[isOrdered]) + 5;
  
            WHERETRACE(0x002,
                ("---- sort cost=%-3d (%d/%d) increases cost %3d to %-3d\n",
                 aSortCost[isOrdered], (nOrderBy-isOrdered), nOrderBy, 
                 rUnsorted, rCost));
          }else{
            rCost = rUnsorted;
            rUnsorted -= 2;  /* TUNING:  Slight bias in favor of no-sort plans */
          }
  
          /* Check to see if pWLoop should be added to the set of
          ** mxChoice best-so-far paths.
          **
          ** First look for an existing path among best-so-far paths
          ** that covers the same set of loops and has the same isOrdered
          ** setting as the current path candidate.
          **
          ** The term "((pTo->isOrdered^isOrdered)&0x80)==0" is equivalent
          ** to (pTo->isOrdered==(-1))==(isOrdered==(-1))" for the range
          ** of legal values for isOrdered, -1..64.
          */
          for(jj=0, pTo=aTo; jj<nTo; jj++, pTo++){
            if( pTo->maskLoop==maskNew
             && ((pTo->isOrdered^isOrdered)&0x80)==0
            ){
              testcase( jj==nTo-1 );
              break;
            }
          }
          if( jj>=nTo ){
            /* None of the existing best-so-far paths match the candidate. */
            if( nTo>=mxChoice
             && (rCost>mxCost || (rCost==mxCost && rUnsorted>=mxUnsorted))
            ){
              /* The current candidate is no better than any of the mxChoice
              ** paths currently in the best-so-far buffer.  So discard
              ** this candidate as not viable. */
  #ifdef WHERETRACE_ENABLED /* 0x4 */
              if( sqlite3WhereTrace&0x4 ){
                sqlite3DebugPrintf("Skip   %s cost=%-3d,%3d,%3d order=%c\n",
                    wherePathName(pFrom, iLoop, pWLoop), rCost, nOut, rUnsorted,
                    isOrdered>=0 ? isOrdered+'0' : '?');
              }
  #endif
              continue;
            }
            /* If we reach this points it means that the new candidate path
            ** needs to be added to the set of best-so-far paths. */
            if( nTo<mxChoice ){
              /* Increase the size of the aTo set by one */
              jj = nTo++;
            }else{
              /* New path replaces the prior worst to keep count below mxChoice */
              jj = mxI;
            }
            pTo = &aTo[jj];
  #ifdef WHERETRACE_ENABLED /* 0x4 */
            if( sqlite3WhereTrace&0x4 ){
              sqlite3DebugPrintf("New    %s cost=%-3d,%3d,%3d order=%c\n",
                  wherePathName(pFrom, iLoop, pWLoop), rCost, nOut, rUnsorted,
                  isOrdered>=0 ? isOrdered+'0' : '?');
            }
  #endif
          }else{
            /* Control reaches here if best-so-far path pTo=aTo[jj] covers the
            ** same set of loops and has the same isOrdered setting as the
            ** candidate path.  Check to see if the candidate should replace
            ** pTo or if the candidate should be skipped.
            ** 
            ** The conditional is an expanded vector comparison equivalent to:
            **   (pTo->rCost,pTo->nRow,pTo->rUnsorted) <= (rCost,nOut,rUnsorted)
            */
            if( pTo->rCost<rCost 
             || (pTo->rCost==rCost
                 && (pTo->nRow<nOut
                     || (pTo->nRow==nOut && pTo->rUnsorted<=rUnsorted)
                    )
                )
            ){
  #ifdef WHERETRACE_ENABLED /* 0x4 */
              if( sqlite3WhereTrace&0x4 ){
                sqlite3DebugPrintf(
                    "Skip   %s cost=%-3d,%3d,%3d order=%c",
                    wherePathName(pFrom, iLoop, pWLoop), rCost, nOut, rUnsorted,
                    isOrdered>=0 ? isOrdered+'0' : '?');
                sqlite3DebugPrintf("   vs %s cost=%-3d,%3d,%3d order=%c\n",
                    wherePathName(pTo, iLoop+1, 0), pTo->rCost, pTo->nRow,
                    pTo->rUnsorted, pTo->isOrdered>=0 ? pTo->isOrdered+'0' : '?');
              }
  #endif
              /* Discard the candidate path from further consideration */
              testcase( pTo->rCost==rCost );
              continue;
            }
            testcase( pTo->rCost==rCost+1 );
            /* Control reaches here if the candidate path is better than the
            ** pTo path.  Replace pTo with the candidate. */
  #ifdef WHERETRACE_ENABLED /* 0x4 */
            if( sqlite3WhereTrace&0x4 ){
              sqlite3DebugPrintf(
                  "Update %s cost=%-3d,%3d,%3d order=%c",
                  wherePathName(pFrom, iLoop, pWLoop), rCost, nOut, rUnsorted,
                  isOrdered>=0 ? isOrdered+'0' : '?');
              sqlite3DebugPrintf("  was %s cost=%-3d,%3d,%3d order=%c\n",
                  wherePathName(pTo, iLoop+1, 0), pTo->rCost, pTo->nRow,
                  pTo->rUnsorted, pTo->isOrdered>=0 ? pTo->isOrdered+'0' : '?');
            }
  #endif
          }
          /* pWLoop is a winner.  Add it to the set of best so far */
          pTo->maskLoop = pFrom->maskLoop | pWLoop->maskSelf;
          pTo->revLoop = revMask;
          pTo->nRow = nOut;
          pTo->rCost = rCost;
          pTo->rUnsorted = rUnsorted;
          pTo->isOrdered = isOrdered;
          memcpy(pTo->aLoop, pFrom->aLoop, sizeof(WhereLoop*)*iLoop);
          pTo->aLoop[iLoop] = pWLoop;
          if( nTo>=mxChoice ){
            mxI = 0;
            mxCost = aTo[0].rCost;
            mxUnsorted = aTo[0].nRow;
            for(jj=1, pTo=&aTo[1]; jj<mxChoice; jj++, pTo++){
              if( pTo->rCost>mxCost 
               || (pTo->rCost==mxCost && pTo->rUnsorted>mxUnsorted) 
              ){
                mxCost = pTo->rCost;
                mxUnsorted = pTo->rUnsorted;
                mxI = jj;
              }
            }
          }
        }
      }
  
  #ifdef WHERETRACE_ENABLED  /* >=2 */
      if( sqlite3WhereTrace & 0x02 ){
        sqlite3DebugPrintf("---- after round %d ----\n", iLoop);
        for(ii=0, pTo=aTo; ii<nTo; ii++, pTo++){
          sqlite3DebugPrintf(" %s cost=%-3d nrow=%-3d order=%c",
             wherePathName(pTo, iLoop+1, 0), pTo->rCost, pTo->nRow,
             pTo->isOrdered>=0 ? (pTo->isOrdered+'0') : '?');
          if( pTo->isOrdered>0 ){
            sqlite3DebugPrintf(" rev=0x%llx\n", pTo->revLoop);
          }else{
            sqlite3DebugPrintf("\n");
          }
        }
      }
  #endif
  
      /* Swap the roles of aFrom and aTo for the next generation */
      pFrom = aTo;
      aTo = aFrom;
      aFrom = pFrom;
      nFrom = nTo;
    }
  
    if( nFrom==0 ){
      sqlite3ErrorMsg(pParse, "no query solution");
      sqlite3DbFreeNN(db, pSpace);
      return SQLITE_ERROR;
    }
    
    /* 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++){
      WhereLevel *pLevel = pWInfo->a + iLoop;
      pLevel->pWLoop = pWLoop = pFrom->aLoop[iLoop];
      pLevel->iFrom = pWLoop->iTab;
      pLevel->iTabCur = pWInfo->pTabList->a[pLevel->iFrom].iCursor;
    }
    if( (pWInfo->wctrlFlags & WHERE_WANT_DISTINCT)!=0
     && (pWInfo->wctrlFlags & WHERE_DISTINCTBY)==0
     && pWInfo->eDistinct==WHERE_DISTINCT_NOOP
     && nRowEst
    ){
      Bitmask notUsed;
      int rc = wherePathSatisfiesOrderBy(pWInfo, pWInfo->pResultSet, pFrom,
                   WHERE_DISTINCTBY, nLoop-1, pFrom->aLoop[nLoop-1], &notUsed);
      if( rc==pWInfo->pResultSet->nExpr ){
        pWInfo->eDistinct = WHERE_DISTINCT_ORDERED;
      }
    }
    pWInfo->bOrderedInnerLoop = 0;
    if( pWInfo->pOrderBy ){
      if( pWInfo->wctrlFlags & WHERE_DISTINCTBY ){
        if( pFrom->isOrdered==pWInfo->pOrderBy->nExpr ){
          pWInfo->eDistinct = WHERE_DISTINCT_ORDERED;
        }
      }else{
        pWInfo->nOBSat = pFrom->isOrdered;
        pWInfo->revMask = pFrom->revLoop;
        if( pWInfo->nOBSat<=0 ){
          pWInfo->nOBSat = 0;
          if( nLoop>0 ){
            u32 wsFlags = pFrom->aLoop[nLoop-1]->wsFlags;
            if( (wsFlags & WHERE_ONEROW)==0 
             && (wsFlags&(WHERE_IPK|WHERE_COLUMN_IN))!=(WHERE_IPK|WHERE_COLUMN_IN)
            ){
              Bitmask m = 0;
              int rc = wherePathSatisfiesOrderBy(pWInfo, pWInfo->pOrderBy, pFrom,
                        WHERE_ORDERBY_LIMIT, nLoop-1, pFrom->aLoop[nLoop-1], &m);
              testcase( wsFlags & WHERE_IPK );
              testcase( wsFlags & WHERE_COLUMN_IN );
              if( rc==pWInfo->pOrderBy->nExpr ){
                pWInfo->bOrderedInnerLoop = 1;
                pWInfo->revMask = m;
              }
            }
          }
        }
      }
      if( (pWInfo->wctrlFlags & WHERE_SORTBYGROUP)
          && pWInfo->nOBSat==pWInfo->pOrderBy->nExpr && nLoop>0
      ){
        Bitmask revMask = 0;
        int nOrder = wherePathSatisfiesOrderBy(pWInfo, pWInfo->pOrderBy, 
            pFrom, 0, nLoop-1, pFrom->aLoop[nLoop-1], &revMask
        );
        assert( pWInfo->sorted==0 );
        if( nOrder==pWInfo->pOrderBy->nExpr ){
          pWInfo->sorted = 1;
          pWInfo->revMask = revMask;
        }
      }
    }
  
  
    pWInfo->nRowOut = pFrom->nRow;
  
    /* Free temporary memory and return success */
    sqlite3DbFreeNN(db, pSpace);
    return SQLITE_OK;
  }
  
  /*
  ** Most queries use only a single table (they are not joins) and have
  ** simple == constraints against indexed fields.  This routine attempts
  ** to plan those simple cases using much less ceremony than the
  ** general-purpose query planner, and thereby yield faster sqlite3_prepare()
  ** times for the common case.
  **
  ** Return non-zero on success, if this query can be handled by this
  ** no-frills query planner.  Return zero if this query needs the 
  ** general-purpose query planner.
  */
  int whereShortCut(WhereLoopBuilder *pBuilder){
    WhereInfo *pWInfo;
    struct SrcList_item *pItem;
    WhereClause *pWC;
    WhereTerm *pTerm;
    WhereLoop *pLoop;
    int iCur;
    int j;
    Table *pTab;
    Index *pIdx;
  
    pWInfo = pBuilder->pWInfo;
    if( pWInfo->wctrlFlags & WHERE_OR_SUBCLAUSE ) return 0;
    assert( pWInfo->pTabList->nSrc>=1 );
    pItem = pWInfo->pTabList->a;
    pTab = pItem->pTab;
    if( IsVirtual(pTab) ) return 0;
    if( pItem->fg.isIndexedBy ) return 0;
    iCur = pItem->iCursor;
    pWC = &pWInfo->sWC;
    pLoop = pBuilder->pNew;
    pLoop->wsFlags = 0;
    pLoop->nSkip = 0;
    pTerm = sqlite3WhereFindTerm(pWC, iCur, -1, 0, WO_EQ|WO_IS, 0);
    if( pTerm ){
      testcase( pTerm->eOperator & WO_IS );
      pLoop->wsFlags = WHERE_COLUMN_EQ|WHERE_IPK|WHERE_ONEROW;
      pLoop->aLTerm[0] = pTerm;
      pLoop->nLTerm = 1;
      pLoop->u.btree.nEq = 1;
      /* TUNING: Cost of a rowid lookup is 10 */
      pLoop->rRun = 33;  /* 33==sqlite3LogEst(10) */
    }else{
      for(pIdx=pTab->pIndex; pIdx; pIdx=pIdx->pNext){
        int opMask;
        assert( pLoop->aLTermSpace==pLoop->aLTerm );
        if( !IsUniqueIndex(pIdx)
         || pIdx->pPartIdxWhere!=0 
         || pIdx->nKeyCol>ArraySize(pLoop->aLTermSpace) 
        ) continue;
        opMask = pIdx->uniqNotNull ? (WO_EQ|WO_IS) : WO_EQ;
        for(j=0; j<pIdx->nKeyCol; j++){
          pTerm = sqlite3WhereFindTerm(pWC, iCur, j, 0, opMask, pIdx);
          if( pTerm==0 ) break;
          testcase( pTerm->eOperator & WO_IS );
          pLoop->aLTerm[j] = pTerm;
        }
        if( j!=pIdx->nKeyCol ) continue;
        pLoop->wsFlags = WHERE_COLUMN_EQ|WHERE_ONEROW|WHERE_INDEXED;
        if( pIdx->isCovering || (pItem->colUsed & pIdx->colNotIdxed)==0 ){
          pLoop->wsFlags |= WHERE_IDX_ONLY;
        }
        pLoop->nLTerm = j;
        pLoop->u.btree.nEq = j;
        pLoop->u.btree.pIndex = pIdx;
        /* TUNING: Cost of a unique index lookup is 15 */
        pLoop->rRun = 39;  /* 39==sqlite3LogEst(15) */
        break;
      }
    }
    if( pLoop->wsFlags ){
      pLoop->nOut = (LogEst)1;
      pWInfo->a[0].pWLoop = pLoop;
      assert( pWInfo->sMaskSet.n==1 && iCur==pWInfo->sMaskSet.ix[0] );
      pLoop->maskSelf = 1; /* sqlite3WhereGetMask(&pWInfo->sMaskSet, iCur); */
      pWInfo->a[0].iTabCur = iCur;
      pWInfo->nRowOut = 1;
      if( pWInfo->pOrderBy ) pWInfo->nOBSat =  pWInfo->pOrderBy->nExpr;
      if( pWInfo->wctrlFlags & WHERE_WANT_DISTINCT ){
        pWInfo->eDistinct = WHERE_DISTINCT_UNIQUE;
      }
  #ifdef SQLITE_DEBUG
      pLoop->cId = '0';
  #endif
      return 1;
    }
    return 0;
  }
  
  /*
  ** Helper function for exprIsDeterministic().
  */
  int exprNodeIsDeterministic(Walker *pWalker, Expr *pExpr){
    if( pExpr->op==TK_FUNCTION && ExprHasProperty(pExpr, EP_ConstFunc)==0 ){
      pWalker->eCode = 0;
      return WRC_Abort;
    }
    return WRC_Continue;
  }
  
  /*
  ** Return true if the expression contains no non-deterministic SQL 
  ** functions. Do not consider non-deterministic SQL functions that are 
  ** part of sub-select statements.
  */
  int exprIsDeterministic(Expr *p){
    Walker w;
    memset(&w, 0, sizeof(w));
    w.eCode = 1;
    w.xExprCallback = exprNodeIsDeterministic;
    w.xSelectCallback = sqlite3SelectWalkFail;
    sqlite3WalkExpr(&w, p);
    return w.eCode;
  }
  
    
  #ifdef WHERETRACE_ENABLED
  /*
  ** Display all WhereLoops in pWInfo
  */
  void showAllWhereLoops(WhereInfo *pWInfo, WhereClause *pWC){
    if( sqlite3WhereTrace ){    /* Display all of the WhereLoop objects */
      WhereLoop *p;
      int i;
      static const char zLabel[] = "0123456789abcdefghijklmnopqrstuvwyxz"
                                             "ABCDEFGHIJKLMNOPQRSTUVWYXZ";
      for(p=pWInfo->pLoops, i=0; p; p=p->pNextLoop, i++){
        p->cId = zLabel[i%(sizeof(zLabel)-1)];
        sqlite3WhereLoopPrint(p, pWC);
      }
    }
  }
  # define WHERETRACE_ALL_LOOPS(W,C) showAllWhereLoops(W,C)
  #else
  # define WHERETRACE_ALL_LOOPS(W,C)
  #endif
  
  /*
  ** Generate the beginning of the loop used for WHERE clause processing.
  ** The return value is a pointer to an opaque structure that contains
  ** information needed to terminate the loop.  Later, the calling routine
  ** should invoke sqlite3WhereEnd() with the return value of this function
  ** in order to complete the WHERE clause processing.
  **
  ** If an error occurs, this routine returns NULL.
  **
  ** The basic idea is to do a nested loop, one loop for each table in
  ** the FROM clause of a select.  (INSERT and UPDATE statements are the
  ** same as a SELECT with only a single table in the FROM clause.)  For
  ** example, if the SQL is this:
  **
  **       SELECT * FROM t1, t2, t3 WHERE ...;
  **
  ** Then the code generated is conceptually like the following:
  **
  **      foreach row1 in t1 do       \    Code generated
  **        foreach row2 in t2 do      |-- by sqlite3WhereBegin()
  **          foreach row3 in t3 do   /
  **            ...
  **          end                     \    Code generated
  **        end                        |-- by sqlite3WhereEnd()
  **      end                         /
  **
  ** Note that the loops might not be nested in the order in which they
  ** appear in the FROM clause if a different order is better able to make
  ** use of indices.  Note also that when the IN operator appears in
  ** the WHERE clause, it might result in additional nested loops for
  ** scanning through all values on the right-hand side of the IN.
  **
  ** There are Btree cursors associated with each table.  t1 uses cursor
  ** number pTabList->a[0].iCursor.  t2 uses the cursor pTabList->a[1].iCursor.
  ** And so forth.  This routine generates code to open those VDBE cursors
  ** and sqlite3WhereEnd() generates the code to close them.
  **
  ** The code that sqlite3WhereBegin() generates leaves the cursors named
  ** in pTabList pointing at their appropriate entries.  The [...] code
  ** can use OP_Column and OP_Rowid opcodes on these cursors to extract
  ** data from the various tables of the loop.
  **
  ** If the WHERE clause is empty, the foreach loops must each scan their
  ** entire tables.  Thus a three-way join is an O(N^3) operation.  But if
  ** the tables have indices and there are terms in the WHERE clause that
  ** refer to those indices, a complete table scan can be avoided and the
  ** code will run much faster.  Most of the work of this routine is checking
  ** to see if there are indices that can be used to speed up the loop.
  **
  ** Terms of the WHERE clause are also used to limit which rows actually
  ** make it to the "..." in the middle of the loop.  After each "foreach",
  ** terms of the WHERE clause that use only terms in that loop and outer
  ** loops are evaluated and if false a jump is made around all subsequent
  ** inner loops (or around the "..." if the test occurs within the inner-
  ** most loop)
  **
  ** OUTER JOINS
  **
  ** An outer join of tables t1 and t2 is conceptally coded as follows:
  **
  **    foreach row1 in t1 do
  **      flag = 0
  **      foreach row2 in t2 do
  **        start:
  **          ...
  **          flag = 1
  **      end
  **      if flag==0 then
  **        move the row2 cursor to a null row
  **        goto start
  **      fi
  **    end
  **
  ** ORDER BY CLAUSE PROCESSING
  **
  ** pOrderBy is a pointer to the ORDER BY clause (or the GROUP BY clause
  ** if the WHERE_GROUPBY flag is set in wctrlFlags) of a SELECT statement
  ** if there is one.  If there is no ORDER BY clause or if this routine
  ** is called from an UPDATE or DELETE statement, then pOrderBy is NULL.
  **
  ** The iIdxCur parameter is the cursor number of an index.  If 
  ** WHERE_OR_SUBCLAUSE is set, iIdxCur is the cursor number of an index
  ** to use for OR clause processing.  The WHERE clause should use this
  ** specific cursor.  If WHERE_ONEPASS_DESIRED is set, then iIdxCur is
  ** the first cursor in an array of cursors for all indices.  iIdxCur should
  ** be used to compute the appropriate cursor depending on which index is
  ** used.
  */
  WhereInfo *sqlite3WhereBegin(
    Parse *pParse,          /* The parser context */
    SrcList *pTabList,      /* FROM clause: A list of all tables to be scanned */
    Expr *pWhere,           /* The WHERE clause */
    ExprList *pOrderBy,     /* An ORDER BY (or GROUP BY) clause, or NULL */
    ExprList *pResultSet,   /* Query result set.  Req'd for DISTINCT */
    u16 wctrlFlags,         /* The WHERE_* flags defined in sqliteInt.h */
    int iAuxArg             /* If WHERE_OR_SUBCLAUSE is set, index cursor number
                            ** If WHERE_USE_LIMIT, then the limit amount */
  ){
    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 */
    WhereLoopBuilder sWLB;     /* The WhereLoop builder */
    WhereMaskSet *pMaskSet;    /* The expression mask set */
    WhereLevel *pLevel;        /* A single level in pWInfo->a[] */
    WhereLoop *pLoop;          /* Pointer to a single WhereLoop object */
    int ii;                    /* Loop counter */
    sqlite3 *db;               /* Database connection */
    int rc;                    /* Return code */
    u8 bFordelete = 0;         /* OPFLAG_FORDELETE or zero, as appropriate */
  
    assert( (wctrlFlags & WHERE_ONEPASS_MULTIROW)==0 || (
          (wctrlFlags & WHERE_ONEPASS_DESIRED)!=0 
       && (wctrlFlags & WHERE_OR_SUBCLAUSE)==0 
    ));
  
    /* Only one of WHERE_OR_SUBCLAUSE or WHERE_USE_LIMIT */
    assert( (wctrlFlags & WHERE_OR_SUBCLAUSE)==0
              || (wctrlFlags & WHERE_USE_LIMIT)==0 );
  
    /* Variable initialization */
    db = pParse->db;
    memset(&sWLB, 0, sizeof(sWLB));
  
    /* An ORDER/GROUP BY clause of more than 63 terms cannot be optimized */
    testcase( pOrderBy && pOrderBy->nExpr==BMS-1 );
    if( pOrderBy && pOrderBy->nExpr>=BMS ) pOrderBy = 0;
    sWLB.pOrderBy = pOrderBy;
  
    /* Disable the DISTINCT optimization if SQLITE_DistinctOpt is set via
    ** sqlite3_test_ctrl(SQLITE_TESTCTRL_OPTIMIZATIONS,...) */
    if( OptimizationDisabled(db, SQLITE_DistinctOpt) ){
      wctrlFlags &= ~WHERE_WANT_DISTINCT;
    }
  
    /* The number of tables in the FROM clause is limited by the number of
    ** bits in a Bitmask 
    */
    testcase( pTabList->nSrc==BMS );
    if( pTabList->nSrc>BMS ){
      sqlite3ErrorMsg(pParse, "at most %d tables in a join", BMS);
      return 0;
    }
  
    /* This function normally generates a nested loop for all tables in 
    ** pTabList.  But if the WHERE_OR_SUBCLAUSE flag is set, then we should
    ** only generate code for the first table in pTabList and assume that
    ** any cursors associated with subsequent tables are uninitialized.
    */
    nTabList = (wctrlFlags & WHERE_OR_SUBCLAUSE) ? 1 : pTabList->nSrc;
  
    /* Allocate and initialize the WhereInfo structure that will become the
    ** return value. A single allocation is used to store the WhereInfo
    ** struct, the contents of WhereInfo.a[], the WhereClause structure
    ** and the WhereMaskSet structure. Since WhereClause contains an 8-byte
    ** field (type Bitmask) it must be aligned on an 8-byte boundary on
    ** some architectures. Hence the ROUND8() below.
    */
    nByteWInfo = ROUND8(sizeof(WhereInfo)+(nTabList-1)*sizeof(WhereLevel));
    pWInfo = sqlite3DbMallocRawNN(db, nByteWInfo + sizeof(WhereLoop));
    if( db->mallocFailed ){
      sqlite3DbFree(db, pWInfo);
      pWInfo = 0;
      goto whereBeginError;
    }
    pWInfo->pParse = pParse;
    pWInfo->pTabList = pTabList;
    pWInfo->pOrderBy = pOrderBy;
    pWInfo->pWhere = pWhere;
    pWInfo->pResultSet = pResultSet;
    pWInfo->aiCurOnePass[0] = pWInfo->aiCurOnePass[1] = -1;
    pWInfo->nLevel = nTabList;
    pWInfo->iBreak = pWInfo->iContinue = sqlite3VdbeMakeLabel(pParse);
    pWInfo->wctrlFlags = wctrlFlags;
    pWInfo->iLimit = iAuxArg;
    pWInfo->savedNQueryLoop = pParse->nQueryLoop;
    memset(&pWInfo->nOBSat, 0, 
           offsetof(WhereInfo,sWC) - offsetof(WhereInfo,nOBSat));
    memset(&pWInfo->a[0], 0, sizeof(WhereLoop)+nTabList*sizeof(WhereLevel));
    assert( pWInfo->eOnePass==ONEPASS_OFF );  /* ONEPASS defaults to OFF */
    pMaskSet = &pWInfo->sMaskSet;
    sWLB.pWInfo = pWInfo;
    sWLB.pWC = &pWInfo->sWC;
    sWLB.pNew = (WhereLoop*)(((char*)pWInfo)+nByteWInfo);
    assert( EIGHT_BYTE_ALIGNMENT(sWLB.pNew) );
    whereLoopInit(sWLB.pNew);
  #ifdef SQLITE_DEBUG
    sWLB.pNew->cId = '*';
  #endif
  
    /* Split the WHERE clause into separate subexpressions where each
    ** subexpression is separated by an AND operator.
    */
    initMaskSet(pMaskSet);
    sqlite3WhereClauseInit(&pWInfo->sWC, pWInfo);
    sqlite3WhereSplit(&pWInfo->sWC, pWhere, TK_AND);
      
    /* Special case: No FROM clause
    */
    if( nTabList==0 ){
      if( pOrderBy ) pWInfo->nOBSat = pOrderBy->nExpr;
      if( wctrlFlags & WHERE_WANT_DISTINCT ){
        pWInfo->eDistinct = WHERE_DISTINCT_UNIQUE;
      }
      ExplainQueryPlan((pParse, 0, "SCAN CONSTANT ROW"));
    }else{
      /* Assign a bit from the bitmask to every term in the FROM clause.
      **
      ** The N-th term of the FROM clause is assigned a bitmask of 1<<N.
      **
      ** The rule of the previous sentence ensures thta if X is the bitmask for
      ** a table T, then X-1 is the bitmask for all other tables to the left of T.
      ** Knowing the bitmask for all tables to the left of a left join is
      ** important.  Ticket #3015.
      **
      ** Note that bitmasks are created for all pTabList->nSrc tables in
      ** pTabList, not just the first nTabList tables.  nTabList is normally
      ** equal to pTabList->nSrc but might be shortened to 1 if the
      ** WHERE_OR_SUBCLAUSE flag is set.
      */
      ii = 0;
      do{
        createMask(pMaskSet, pTabList->a[ii].iCursor);
        sqlite3WhereTabFuncArgs(pParse, &pTabList->a[ii], &pWInfo->sWC);
      }while( (++ii)<pTabList->nSrc );
    #ifdef SQLITE_DEBUG
      {
        Bitmask mx = 0;
        for(ii=0; ii<pTabList->nSrc; ii++){
          Bitmask m = sqlite3WhereGetMask(pMaskSet, pTabList->a[ii].iCursor);
          assert( m>=mx );
          mx = m;
        }
      }
    #endif
    }
    
    /* Analyze all of the subexpressions. */
    sqlite3WhereExprAnalyze(pTabList, &pWInfo->sWC);
    if( db->mallocFailed ) goto whereBeginError;
  
    /* Special case: WHERE terms that do not refer to any tables in the join
    ** (constant expressions). Evaluate each such term, and jump over all the
    ** generated code if the result is not true.  
    **
    ** Do not do this if the expression contains non-deterministic functions
    ** that are not within a sub-select. This is not strictly required, but
    ** preserves SQLite's legacy behaviour in the following two cases:
    **
    **   FROM ... WHERE random()>0;           -- eval random() once per row
    **   FROM ... WHERE (SELECT random())>0;  -- eval random() once overall
    */
    for(ii=0; ii<sWLB.pWC->nTerm; ii++){
      WhereTerm *pT = &sWLB.pWC->a[ii];
      if( pT->wtFlags & TERM_VIRTUAL ) continue;
      if( pT->prereqAll==0 && (nTabList==0 || exprIsDeterministic(pT->pExpr)) ){
        sqlite3ExprIfFalse(pParse, pT->pExpr, pWInfo->iBreak, SQLITE_JUMPIFNULL);
        pT->wtFlags |= TERM_CODED;
      }
    }
  
    if( wctrlFlags & WHERE_WANT_DISTINCT ){
      if( isDistinctRedundant(pParse, pTabList, &pWInfo->sWC, pResultSet) ){
        /* The DISTINCT marking is pointless.  Ignore it. */
        pWInfo->eDistinct = WHERE_DISTINCT_UNIQUE;
      }else if( pOrderBy==0 ){
        /* Try to ORDER BY the result set to make distinct processing easier */
        pWInfo->wctrlFlags |= WHERE_DISTINCTBY;
        pWInfo->pOrderBy = pResultSet;
      }
    }
  
    /* Construct the WhereLoop objects */
  #if defined(WHERETRACE_ENABLED)
    if( sqlite3WhereTrace & 0xffff ){
      sqlite3DebugPrintf("*** Optimizer Start *** (wctrlFlags: 0x%x",wctrlFlags);
      if( wctrlFlags & WHERE_USE_LIMIT ){
        sqlite3DebugPrintf(", limit: %d", iAuxArg);
      }
      sqlite3DebugPrintf(")\n");
      if( sqlite3WhereTrace & 0x100 ){
        Select sSelect;
        memset(&sSelect, 0, sizeof(sSelect));
        sSelect.selFlags = SF_WhereBegin;
        sSelect.pSrc = pTabList;
        sSelect.pWhere = pWhere;
        sSelect.pOrderBy = pOrderBy;
        sSelect.pEList = pResultSet;
        sqlite3TreeViewSelect(0, &sSelect, 0);
      }
    }
    if( sqlite3WhereTrace & 0x100 ){ /* Display all terms of the WHERE clause */
      sqlite3DebugPrintf("---- WHERE clause at start of analysis:\n");
      sqlite3WhereClausePrint(sWLB.pWC);
    }
  #endif
  
    if( nTabList!=1 || whereShortCut(&sWLB)==0 ){
      rc = whereLoopAddAll(&sWLB);
      if( rc ) goto whereBeginError;
  
  #ifdef SQLITE_ENABLE_STAT4
      /* If one or more WhereTerm.truthProb values were used in estimating
      ** loop parameters, but then those truthProb values were subsequently
      ** changed based on STAT4 information while computing subsequent loops,
      ** then we need to rerun the whole loop building process so that all
      ** loops will be built using the revised truthProb values. */
      if( sWLB.bldFlags2 & SQLITE_BLDF2_2NDPASS ){
        WHERETRACE_ALL_LOOPS(pWInfo, sWLB.pWC);
        WHERETRACE(0xffff, 
             ("**** Redo all loop computations due to"
              " TERM_HIGHTRUTH changes ****\n"));
        while( pWInfo->pLoops ){
          WhereLoop *p = pWInfo->pLoops;
          pWInfo->pLoops = p->pNextLoop;
          whereLoopDelete(db, p);
        }
        rc = whereLoopAddAll(&sWLB);
        if( rc ) goto whereBeginError;
      }
  #endif
      WHERETRACE_ALL_LOOPS(pWInfo, sWLB.pWC);
    
      wherePathSolver(pWInfo, 0);
      if( db->mallocFailed ) goto whereBeginError;
      if( pWInfo->pOrderBy ){
         wherePathSolver(pWInfo, pWInfo->nRowOut+1);
         if( db->mallocFailed ) goto whereBeginError;
      }
    }
    if( pWInfo->pOrderBy==0 && (db->flags & SQLITE_ReverseOrder)!=0 ){
       pWInfo->revMask = ALLBITS;
    }
    if( pParse->nErr || NEVER(db->mallocFailed) ){
      goto whereBeginError;
    }
  #ifdef WHERETRACE_ENABLED
    if( sqlite3WhereTrace ){
      sqlite3DebugPrintf("---- Solution nRow=%d", pWInfo->nRowOut);
      if( pWInfo->nOBSat>0 ){
        sqlite3DebugPrintf(" ORDERBY=%d,0x%llx", pWInfo->nOBSat, pWInfo->revMask);
      }
      switch( pWInfo->eDistinct ){
        case WHERE_DISTINCT_UNIQUE: {
          sqlite3DebugPrintf("  DISTINCT=unique");
          break;
        }
        case WHERE_DISTINCT_ORDERED: {
          sqlite3DebugPrintf("  DISTINCT=ordered");
          break;
        }
        case WHERE_DISTINCT_UNORDERED: {
          sqlite3DebugPrintf("  DISTINCT=unordered");
          break;
        }
      }
      sqlite3DebugPrintf("\n");
      for(ii=0; ii<pWInfo->nLevel; ii++){
        sqlite3WhereLoopPrint(pWInfo->a[ii].pWLoop, sWLB.pWC);
      }
    }
  #endif
  
    /* Attempt to omit tables from the join that do not affect the result.
    ** For a table to not affect the result, the following must be true:
    **
    **   1) The query must not be an aggregate.
    **   2) The table must be the RHS of a LEFT JOIN.
    **   3) Either the query must be DISTINCT, or else the ON or USING clause
    **      must contain a constraint that limits the scan of the table to 
    **      at most a single row.
    **   4) The table must not be referenced by any part of the query apart
    **      from its own USING or ON clause.
    **
    ** For example, given:
    **
    **     CREATE TABLE t1(ipk INTEGER PRIMARY KEY, v1);
    **     CREATE TABLE t2(ipk INTEGER PRIMARY KEY, v2);
    **     CREATE TABLE t3(ipk INTEGER PRIMARY KEY, v3);
    **
    ** then table t2 can be omitted from the following:
    **
    **     SELECT v1, v3 FROM t1 
    **       LEFT JOIN t2 ON (t1.ipk=t2.ipk)
    **       LEFT JOIN t3 ON (t1.ipk=t3.ipk)
    **
    ** or from:
    **
    **     SELECT DISTINCT v1, v3 FROM t1 
    **       LEFT JOIN t2
    **       LEFT JOIN t3 ON (t1.ipk=t3.ipk)
    */
    notReady = ~(Bitmask)0;
    if( pWInfo->nLevel>=2
     && pResultSet!=0               /* guarantees condition (1) above */
     && OptimizationEnabled(db, SQLITE_OmitNoopJoin)
    ){
      int i;
      Bitmask tabUsed = sqlite3WhereExprListUsage(pMaskSet, pResultSet);
      if( sWLB.pOrderBy ){
        tabUsed |= sqlite3WhereExprListUsage(pMaskSet, sWLB.pOrderBy);
      }
      for(i=pWInfo->nLevel-1; i>=1; i--){
        WhereTerm *pTerm, *pEnd;
        struct SrcList_item *pItem;
        pLoop = pWInfo->a[i].pWLoop;
        pItem = &pWInfo->pTabList->a[pLoop->iTab];
        if( (pItem->fg.jointype & JT_LEFT)==0 ) continue;
        if( (wctrlFlags & WHERE_WANT_DISTINCT)==0
         && (pLoop->wsFlags & WHERE_ONEROW)==0
        ){
          continue;
        }
        if( (tabUsed & pLoop->maskSelf)!=0 ) continue;
        pEnd = sWLB.pWC->a + sWLB.pWC->nTerm;
        for(pTerm=sWLB.pWC->a; pTerm<pEnd; pTerm++){
          if( (pTerm->prereqAll & pLoop->maskSelf)!=0 ){
            if( !ExprHasProperty(pTerm->pExpr, EP_FromJoin)
             || pTerm->pExpr->iRightJoinTable!=pItem->iCursor
            ){
              break;
            }
          }
        }
        if( pTerm<pEnd ) continue;
        WHERETRACE(0xffff, ("-> drop loop %c not used\n", pLoop->cId));
        notReady &= ~pLoop->maskSelf;
        for(pTerm=sWLB.pWC->a; pTerm<pEnd; pTerm++){
          if( (pTerm->prereqAll & pLoop->maskSelf)!=0 ){
            pTerm->wtFlags |= TERM_CODED;
          }
        }
        if( i!=pWInfo->nLevel-1 ){
          int nByte = (pWInfo->nLevel-1-i) * sizeof(WhereLevel);
          memmove(&pWInfo->a[i], &pWInfo->a[i+1], nByte);
        }
        pWInfo->nLevel--;
        nTabList--;
      }
    }
  #if defined(WHERETRACE_ENABLED)
    if( sqlite3WhereTrace & 0x100 ){ /* Display all terms of the WHERE clause */
      sqlite3DebugPrintf("---- WHERE clause at end of analysis:\n");
      sqlite3WhereClausePrint(sWLB.pWC);
    }
    WHERETRACE(0xffff,("*** Optimizer Finished ***\n"));
  #endif
    pWInfo->pParse->nQueryLoop += pWInfo->nRowOut;
  
    /* If the caller is an UPDATE or DELETE statement that is requesting
    ** to use a one-pass algorithm, determine if this is appropriate.
    **
    ** A one-pass approach can be used if the caller has requested one
    ** and either (a) the scan visits at most one row or (b) each
    ** of the following are true:
    **
    **   * the caller has indicated that a one-pass approach can be used
    **     with multiple rows (by setting WHERE_ONEPASS_MULTIROW), and
    **   * the table is not a virtual table, and
    **   * either the scan does not use the OR optimization or the caller
    **     is a DELETE operation (WHERE_DUPLICATES_OK is only specified
    **     for DELETE).
    **
    ** The last qualification is because an UPDATE statement uses
    ** WhereInfo.aiCurOnePass[1] to determine whether or not it really can
    ** use a one-pass approach, and this is not set accurately for scans
    ** that use the OR optimization.
    */
    assert( (wctrlFlags & WHERE_ONEPASS_DESIRED)==0 || pWInfo->nLevel==1 );
    if( (wctrlFlags & WHERE_ONEPASS_DESIRED)!=0 ){
      int wsFlags = pWInfo->a[0].pWLoop->wsFlags;
      int bOnerow = (wsFlags & WHERE_ONEROW)!=0;
      assert( !(wsFlags & WHERE_VIRTUALTABLE) || IsVirtual(pTabList->a[0].pTab) );
      if( bOnerow || (
          0!=(wctrlFlags & WHERE_ONEPASS_MULTIROW)
       && !IsVirtual(pTabList->a[0].pTab)
       && (0==(wsFlags & WHERE_MULTI_OR) || (wctrlFlags & WHERE_DUPLICATES_OK))
      )){
        pWInfo->eOnePass = bOnerow ? ONEPASS_SINGLE : ONEPASS_MULTI;
        if( HasRowid(pTabList->a[0].pTab) && (wsFlags & WHERE_IDX_ONLY) ){
          if( wctrlFlags & WHERE_ONEPASS_MULTIROW ){
            bFordelete = OPFLAG_FORDELETE;
          }
          pWInfo->a[0].pWLoop->wsFlags = (wsFlags & ~WHERE_IDX_ONLY);
        }
      }
    }
  
    /* Open all tables in the pTabList and any indices selected for
    ** searching those tables.
    */
    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;
      iDb = sqlite3SchemaToIndex(db, pTab->pSchema);
      pLoop = pLevel->pWLoop;
      if( (pTab->tabFlags & TF_Ephemeral)!=0 || pTab->pSelect ){
        /* Do nothing */
      }else
  #ifndef SQLITE_OMIT_VIRTUALTABLE
      if( (pLoop->wsFlags & WHERE_VIRTUALTABLE)!=0 ){
        const char *pVTab = (const char *)sqlite3GetVTable(db, pTab);
        int iCur = pTabItem->iCursor;
        sqlite3VdbeAddOp4(v, OP_VOpen, iCur, 0, 0, pVTab, P4_VTAB);
      }else if( IsVirtual(pTab) ){
        /* noop */
      }else
  #endif
      if( (pLoop->wsFlags & WHERE_IDX_ONLY)==0
           && (wctrlFlags & WHERE_OR_SUBCLAUSE)==0 ){
        int op = OP_OpenRead;
        if( pWInfo->eOnePass!=ONEPASS_OFF ){
          op = OP_OpenWrite;
          pWInfo->aiCurOnePass[0] = pTabItem->iCursor;
        };
        sqlite3OpenTable(pParse, pTabItem->iCursor, iDb, pTab, op);
        assert( pTabItem->iCursor==pLevel->iTabCur );
        testcase( pWInfo->eOnePass==ONEPASS_OFF && pTab->nCol==BMS-1 );
        testcase( pWInfo->eOnePass==ONEPASS_OFF && pTab->nCol==BMS );
        if( pWInfo->eOnePass==ONEPASS_OFF 
         && pTab->nCol<BMS
         && (pTab->tabFlags & (TF_HasGenerated|TF_WithoutRowid))==0
        ){
          /* If we know that only a prefix of the record will be used,
          ** it is advantageous to reduce the "column count" field in
          ** the P4 operand of the OP_OpenRead/Write opcode. */
          Bitmask b = pTabItem->colUsed;
          int n = 0;
          for(; b; b=b>>1, n++){}
          sqlite3VdbeChangeP4(v, -1, SQLITE_INT_TO_PTR(n), P4_INT32);
          assert( n<=pTab->nCol );
        }
  #ifdef SQLITE_ENABLE_CURSOR_HINTS
        if( pLoop->u.btree.pIndex!=0 ){
          sqlite3VdbeChangeP5(v, OPFLAG_SEEKEQ|bFordelete);
        }else
  #endif
        {
          sqlite3VdbeChangeP5(v, bFordelete);
        }
  #ifdef SQLITE_ENABLE_COLUMN_USED_MASK
        sqlite3VdbeAddOp4Dup8(v, OP_ColumnsUsed, pTabItem->iCursor, 0, 0,
                              (const u8*)&pTabItem->colUsed, P4_INT64);
  #endif
      }else{
        sqlite3TableLock(pParse, iDb, pTab->tnum, 0, pTab->zName);
      }
      if( pLoop->wsFlags & WHERE_INDEXED ){
        Index *pIx = pLoop->u.btree.pIndex;
        int iIndexCur;
        int op = OP_OpenRead;
        /* iAuxArg is always set to a positive value if ONEPASS is possible */
        assert( iAuxArg!=0 || (pWInfo->wctrlFlags & WHERE_ONEPASS_DESIRED)==0 );
        if( !HasRowid(pTab) && IsPrimaryKeyIndex(pIx)
         && (wctrlFlags & WHERE_OR_SUBCLAUSE)!=0
        ){
          /* This is one term of an OR-optimization using the PRIMARY KEY of a
          ** WITHOUT ROWID table.  No need for a separate index */
          iIndexCur = pLevel->iTabCur;
          op = 0;
        }else if( pWInfo->eOnePass!=ONEPASS_OFF ){
          Index *pJ = pTabItem->pTab->pIndex;
          iIndexCur = iAuxArg;
          assert( wctrlFlags & WHERE_ONEPASS_DESIRED );
          while( ALWAYS(pJ) && pJ!=pIx ){
            iIndexCur++;
            pJ = pJ->pNext;
          }
          op = OP_OpenWrite;
          pWInfo->aiCurOnePass[1] = iIndexCur;
        }else if( iAuxArg && (wctrlFlags & WHERE_OR_SUBCLAUSE)!=0 ){
          iIndexCur = iAuxArg;
          op = OP_ReopenIdx;
        }else{
          iIndexCur = pParse->nTab++;
        }
        pLevel->iIdxCur = iIndexCur;
        assert( pIx->pSchema==pTab->pSchema );
        assert( iIndexCur>=0 );
        if( op ){
          sqlite3VdbeAddOp3(v, op, iIndexCur, pIx->tnum, iDb);
          sqlite3VdbeSetP4KeyInfo(pParse, pIx);
          if( (pLoop->wsFlags & WHERE_CONSTRAINT)!=0
           && (pLoop->wsFlags & (WHERE_COLUMN_RANGE|WHERE_SKIPSCAN))==0
           && (pLoop->wsFlags & WHERE_BIGNULL_SORT)==0
           && (pWInfo->wctrlFlags&WHERE_ORDERBY_MIN)==0
           && pWInfo->eDistinct!=WHERE_DISTINCT_ORDERED
          ){
            sqlite3VdbeChangeP5(v, OPFLAG_SEEKEQ); /* Hint to COMDB2 */
          }
          VdbeComment((v, "%s", pIx->zName));
  #ifdef SQLITE_ENABLE_COLUMN_USED_MASK
          {
            u64 colUsed = 0;
            int ii, jj;
            for(ii=0; ii<pIx->nColumn; ii++){
              jj = pIx->aiColumn[ii];
              if( jj<0 ) continue;
              if( jj>63 ) jj = 63;
              if( (pTabItem->colUsed & MASKBIT(jj))==0 ) continue;
              colUsed |= ((u64)1)<<(ii<63 ? ii : 63);
            }
            sqlite3VdbeAddOp4Dup8(v, OP_ColumnsUsed, iIndexCur, 0, 0,
                                  (u8*)&colUsed, P4_INT64);
          }
  #endif /* SQLITE_ENABLE_COLUMN_USED_MASK */
        }
      }
      if( iDb>=0 ) sqlite3CodeVerifySchema(pParse, iDb);
    }
    pWInfo->iTop = sqlite3VdbeCurrentAddr(v);
    if( db->mallocFailed ) goto whereBeginError;
  
    /* Generate the code to do the search.  Each iteration of the for
    ** loop below generates code for a single nested loop of the VM
    ** program.
    */
    for(ii=0; ii<nTabList; ii++){
      int addrExplain;
      int wsFlags;
      pLevel = &pWInfo->a[ii];
      wsFlags = pLevel->pWLoop->wsFlags;
  #ifndef SQLITE_OMIT_AUTOMATIC_INDEX
      if( (pLevel->pWLoop->wsFlags & WHERE_AUTO_INDEX)!=0 ){
        constructAutomaticIndex(pParse, &pWInfo->sWC,
                  &pTabList->a[pLevel->iFrom], notReady, pLevel);
        if( db->mallocFailed ) goto whereBeginError;
      }
  #endif
      addrExplain = sqlite3WhereExplainOneScan(
          pParse, pTabList, pLevel, wctrlFlags
      );
      pLevel->addrBody = sqlite3VdbeCurrentAddr(v);
      notReady = sqlite3WhereCodeOneLoopStart(pParse,v,pWInfo,ii,pLevel,notReady);
      pWInfo->iContinue = pLevel->addrCont;
      if( (wsFlags&WHERE_MULTI_OR)==0 && (wctrlFlags&WHERE_OR_SUBCLAUSE)==0 ){
        sqlite3WhereAddScanStatus(v, pTabList, pLevel, addrExplain);
      }
    }
  
    /* Done. */
    VdbeModuleComment((v, "Begin WHERE-core"));
    return pWInfo;
  
    /* Jump here if malloc fails */
  whereBeginError:
    if( pWInfo ){
      pParse->nQueryLoop = pWInfo->savedNQueryLoop;
      whereInfoFree(db, pWInfo);
    }
    return 0;
  }
  
  /*
  ** Part of sqlite3WhereEnd() will rewrite opcodes to reference the
  ** index rather than the main table.  In SQLITE_DEBUG mode, we want
  ** to trace those changes if PRAGMA vdbe_addoptrace=on.  This routine
  ** does that.
  */
  #ifndef SQLITE_DEBUG
  # define OpcodeRewriteTrace(D,K,P) /* no-op */
  #else
  # define OpcodeRewriteTrace(D,K,P) sqlite3WhereOpcodeRewriteTrace(D,K,P)
    static void sqlite3WhereOpcodeRewriteTrace(
      sqlite3 *db,
      int pc,
      VdbeOp *pOp
    ){
      if( (db->flags & SQLITE_VdbeAddopTrace)==0 ) return;
      sqlite3VdbePrintOp(0, pc, pOp);
    }
  #endif
  
  /*
  ** Generate the end of the WHERE loop.  See comments on 
  ** sqlite3WhereBegin() for additional information.
  */
  void sqlite3WhereEnd(WhereInfo *pWInfo){
    Parse *pParse = pWInfo->pParse;
    Vdbe *v = pParse->pVdbe;
    int i;
    WhereLevel *pLevel;
    WhereLoop *pLoop;
    SrcList *pTabList = pWInfo->pTabList;
    sqlite3 *db = pParse->db;
  
    /* Generate loop termination code.
    */
    VdbeModuleComment((v, "End WHERE-core"));
    for(i=pWInfo->nLevel-1; i>=0; i--){
      int addr;
      pLevel = &pWInfo->a[i];
      pLoop = pLevel->pWLoop;
      if( pLevel->op!=OP_Noop ){
  #ifndef SQLITE_DISABLE_SKIPAHEAD_DISTINCT
        int addrSeek = 0;
        Index *pIdx;
        int n;
        if( pWInfo->eDistinct==WHERE_DISTINCT_ORDERED
         && i==pWInfo->nLevel-1  /* Ticket [ef9318757b152e3] 2017-10-21 */
         && (pLoop->wsFlags & WHERE_INDEXED)!=0
         && (pIdx = pLoop->u.btree.pIndex)->hasStat1
         && (n = pLoop->u.btree.nDistinctCol)>0
         && pIdx->aiRowLogEst[n]>=36
        ){
          int r1 = pParse->nMem+1;
          int j, op;
          for(j=0; j<n; j++){
            sqlite3VdbeAddOp3(v, OP_Column, pLevel->iIdxCur, j, r1+j);
          }
          pParse->nMem += n+1;
          op = pLevel->op==OP_Prev ? OP_SeekLT : OP_SeekGT;
          addrSeek = sqlite3VdbeAddOp4Int(v, op, pLevel->iIdxCur, 0, r1, n);
          VdbeCoverageIf(v, op==OP_SeekLT);
          VdbeCoverageIf(v, op==OP_SeekGT);
          sqlite3VdbeAddOp2(v, OP_Goto, 1, pLevel->p2);
        }
  #endif /* SQLITE_DISABLE_SKIPAHEAD_DISTINCT */
        /* The common case: Advance to the next row */
        sqlite3VdbeResolveLabel(v, pLevel->addrCont);
        sqlite3VdbeAddOp3(v, pLevel->op, pLevel->p1, pLevel->p2, pLevel->p3);
        sqlite3VdbeChangeP5(v, pLevel->p5);
        VdbeCoverage(v);
        VdbeCoverageIf(v, pLevel->op==OP_Next);
        VdbeCoverageIf(v, pLevel->op==OP_Prev);
        VdbeCoverageIf(v, pLevel->op==OP_VNext);
        if( pLevel->regBignull ){
          sqlite3VdbeResolveLabel(v, pLevel->addrBignull);
          sqlite3VdbeAddOp2(v, OP_DecrJumpZero, pLevel->regBignull, pLevel->p2-1);
          VdbeCoverage(v);
        }
  #ifndef SQLITE_DISABLE_SKIPAHEAD_DISTINCT
        if( addrSeek ) sqlite3VdbeJumpHere(v, addrSeek);
  #endif
      }else{
        sqlite3VdbeResolveLabel(v, pLevel->addrCont);
      }
      if( pLoop->wsFlags & WHERE_IN_ABLE && pLevel->u.in.nIn>0 ){
        struct InLoop *pIn;
        int j;
        sqlite3VdbeResolveLabel(v, pLevel->addrNxt);
        for(j=pLevel->u.in.nIn, pIn=&pLevel->u.in.aInLoop[j-1]; j>0; j--, pIn--){
          sqlite3VdbeJumpHere(v, pIn->addrInTop+1);
          if( pIn->eEndLoopOp!=OP_Noop ){
            if( pIn->nPrefix ){
              assert( pLoop->wsFlags & WHERE_IN_EARLYOUT );
              if( (pLoop->wsFlags & WHERE_VIRTUALTABLE)==0 ){
                sqlite3VdbeAddOp4Int(v, OP_IfNoHope, pLevel->iIdxCur,
                    sqlite3VdbeCurrentAddr(v)+2+(pLevel->iLeftJoin!=0),
                    pIn->iBase, pIn->nPrefix);
                VdbeCoverage(v);
              }
              if( pLevel->iLeftJoin ){
                /* For LEFT JOIN queries, cursor pIn->iCur may not have been
                ** opened yet. This occurs for WHERE clauses such as
                ** "a = ? AND b IN (...)", where the index is on (a, b). If
                ** the RHS of the (a=?) is NULL, then the "b IN (...)" may
                ** never have been coded, but the body of the loop run to
                ** return the null-row. So, if the cursor is not open yet,
                ** jump over the OP_Next or OP_Prev instruction about to
                ** be coded.  */
                sqlite3VdbeAddOp2(v, OP_IfNotOpen, pIn->iCur, 
                    sqlite3VdbeCurrentAddr(v) + 2
                );
                VdbeCoverage(v);
              }
            }
            sqlite3VdbeAddOp2(v, pIn->eEndLoopOp, pIn->iCur, pIn->addrInTop);
            VdbeCoverage(v);
            VdbeCoverageIf(v, pIn->eEndLoopOp==OP_Prev);
            VdbeCoverageIf(v, pIn->eEndLoopOp==OP_Next);
          }
          sqlite3VdbeJumpHere(v, pIn->addrInTop-1);
        }
      }
      sqlite3VdbeResolveLabel(v, pLevel->addrBrk);
      if( pLevel->addrSkip ){
        sqlite3VdbeGoto(v, pLevel->addrSkip);
        VdbeComment((v, "next skip-scan on %s", pLoop->u.btree.pIndex->zName));
        sqlite3VdbeJumpHere(v, pLevel->addrSkip);
        sqlite3VdbeJumpHere(v, pLevel->addrSkip-2);
      }
  #ifndef SQLITE_LIKE_DOESNT_MATCH_BLOBS
      if( pLevel->addrLikeRep ){
        sqlite3VdbeAddOp2(v, OP_DecrJumpZero, (int)(pLevel->iLikeRepCntr>>1),
                          pLevel->addrLikeRep);
        VdbeCoverage(v);
      }
  #endif
      if( pLevel->iLeftJoin ){
        int ws = pLoop->wsFlags;
        addr = sqlite3VdbeAddOp1(v, OP_IfPos, pLevel->iLeftJoin); VdbeCoverage(v);
        assert( (ws & WHERE_IDX_ONLY)==0 || (ws & WHERE_INDEXED)!=0 );
        if( (ws & WHERE_IDX_ONLY)==0 ){
          assert( pLevel->iTabCur==pTabList->a[pLevel->iFrom].iCursor );
          sqlite3VdbeAddOp1(v, OP_NullRow, pLevel->iTabCur);
        }
        if( (ws & WHERE_INDEXED) 
         || ((ws & WHERE_MULTI_OR) && pLevel->u.pCovidx) 
        ){
          sqlite3VdbeAddOp1(v, OP_NullRow, pLevel->iIdxCur);
        }
        if( pLevel->op==OP_Return ){
          sqlite3VdbeAddOp2(v, OP_Gosub, pLevel->p1, pLevel->addrFirst);
        }else{
          sqlite3VdbeGoto(v, pLevel->addrFirst);
        }
        sqlite3VdbeJumpHere(v, addr);
      }
      VdbeModuleComment((v, "End WHERE-loop%d: %s", i,
                       pWInfo->pTabList->a[pLevel->iFrom].pTab->zName));
    }
  
    /* The "break" point is here, just past the end of the outer loop.
    ** Set it.
    */
    sqlite3VdbeResolveLabel(v, pWInfo->iBreak);
  
    assert( pWInfo->nLevel<=pTabList->nSrc );
    for(i=0, pLevel=pWInfo->a; i<pWInfo->nLevel; i++, pLevel++){
      int k, last;
      VdbeOp *pOp;
      Index *pIdx = 0;
      struct SrcList_item *pTabItem = &pTabList->a[pLevel->iFrom];
      Table *pTab = pTabItem->pTab;
      assert( pTab!=0 );
      pLoop = pLevel->pWLoop;
  
      /* For a co-routine, change all OP_Column references to the table of
      ** the co-routine into OP_Copy of result contained in a register.
      ** OP_Rowid becomes OP_Null.
      */
      if( pTabItem->fg.viaCoroutine ){
        testcase( pParse->db->mallocFailed );
        translateColumnToCopy(pParse, pLevel->addrBody, pLevel->iTabCur,
                              pTabItem->regResult, 0);
        continue;
      }
  
  #ifdef SQLITE_ENABLE_EARLY_CURSOR_CLOSE
      /* Close all of the cursors that were opened by sqlite3WhereBegin.
      ** Except, do not close cursors that will be reused by the OR optimization
      ** (WHERE_OR_SUBCLAUSE).  And do not close the OP_OpenWrite cursors
      ** created for the ONEPASS optimization.
      */
      if( (pTab->tabFlags & TF_Ephemeral)==0
       && pTab->pSelect==0
       && (pWInfo->wctrlFlags & WHERE_OR_SUBCLAUSE)==0
      ){
        int ws = pLoop->wsFlags;
        if( pWInfo->eOnePass==ONEPASS_OFF && (ws & WHERE_IDX_ONLY)==0 ){
          sqlite3VdbeAddOp1(v, OP_Close, pTabItem->iCursor);
        }
        if( (ws & WHERE_INDEXED)!=0
         && (ws & (WHERE_IPK|WHERE_AUTO_INDEX))==0 
         && pLevel->iIdxCur!=pWInfo->aiCurOnePass[1]
        ){
          sqlite3VdbeAddOp1(v, OP_Close, pLevel->iIdxCur);
        }
      }
  #endif
  
      /* If this scan uses an index, make VDBE code substitutions to read data
      ** from the index instead of from the table where possible.  In some cases
      ** this optimization prevents the table from ever being read, which can
      ** yield a significant performance boost.
      ** 
      ** Calls to the code generator in between sqlite3WhereBegin and
      ** sqlite3WhereEnd will have created code that references the table
      ** directly.  This loop scans all that code looking for opcodes
      ** that reference the table and converts them into opcodes that
      ** reference the index.
      */
      if( pLoop->wsFlags & (WHERE_INDEXED|WHERE_IDX_ONLY) ){
        pIdx = pLoop->u.btree.pIndex;
      }else if( pLoop->wsFlags & WHERE_MULTI_OR ){
        pIdx = pLevel->u.pCovidx;
      }
      if( pIdx
       && (pWInfo->eOnePass==ONEPASS_OFF || !HasRowid(pIdx->pTable))
       && !db->mallocFailed
      ){
        last = sqlite3VdbeCurrentAddr(v);
        k = pLevel->addrBody;
  #ifdef SQLITE_DEBUG
        if( db->flags & SQLITE_VdbeAddopTrace ){
          printf("TRANSLATE opcodes in range %d..%d\n", k, last-1);
        }
  #endif
        pOp = sqlite3VdbeGetOp(v, k);
        for(; k<last; k++, pOp++){
          if( pOp->p1!=pLevel->iTabCur ) continue;
          if( pOp->opcode==OP_Column
  #ifdef SQLITE_ENABLE_OFFSET_SQL_FUNC
           || pOp->opcode==OP_Offset
  #endif
          ){
            int x = pOp->p2;
            assert( pIdx->pTable==pTab );
            if( !HasRowid(pTab) ){
              Index *pPk = sqlite3PrimaryKeyIndex(pTab);
              x = pPk->aiColumn[x];
              assert( x>=0 );
            }else{
              testcase( x!=sqlite3StorageColumnToTable(pTab,x) );
              x = sqlite3StorageColumnToTable(pTab,x);
            }
            x = sqlite3TableColumnToIndex(pIdx, x);
            if( x>=0 ){
              pOp->p2 = x;
              pOp->p1 = pLevel->iIdxCur;
              OpcodeRewriteTrace(db, k, pOp);
            }
            assert( (pLoop->wsFlags & WHERE_IDX_ONLY)==0 || x>=0 
                || pWInfo->eOnePass );
          }else if( pOp->opcode==OP_Rowid ){
            pOp->p1 = pLevel->iIdxCur;
            pOp->opcode = OP_IdxRowid;
            OpcodeRewriteTrace(db, k, pOp);
          }else if( pOp->opcode==OP_IfNullRow ){
            pOp->p1 = pLevel->iIdxCur;
            OpcodeRewriteTrace(db, k, pOp);
          }
        }
  #ifdef SQLITE_DEBUG
        if( db->flags & SQLITE_VdbeAddopTrace ) printf("TRANSLATE complete\n");
  #endif
      }
    }
  
    /* Undo all Expr node modifications */
    while( pWInfo->pExprMods ){
      WhereExprMod *p = pWInfo->pExprMods;
      pWInfo->pExprMods = p->pNext;
      memcpy(p->pExpr, &p->orig, sizeof(p->orig));
      sqlite3DbFree(db, p);
    }
  
    /* Final cleanup
    */
    pParse->nQueryLoop = pWInfo->savedNQueryLoop;
    whereInfoFree(db, pWInfo);
    return;
  }
  