u8 untestedTerms;         /* Not all WHERE terms resolved by outer loop */
  u8 eDistinct;             /* One of the WHERE_DISTINCT_* values below */
  int iTop;                 /* The very beginning of the WHERE loop */
  int iContinue;            /* Jump here to continue with next record */
  int iBreak;               /* Jump here to break out of the loop */
  int nLevel;               /* Number of nested loop */
  struct WhereClause *pWC;  /* Decomposition of the WHERE clause */

  double savedNQueryLoop;   /* pParse->nQueryLoop outside the WHERE loop */
  double nRowOut;           /* Estimated number of output rows */
  WhereLevel a[1];          /* Information about each nest loop in WHERE */
};

/* Allowed values for WhereInfo.eDistinct and DistinctCtx.eTnctType */
#define WHERE_DISTINCT_NOOP      0  /* DISTINCT keyword not used */

  u8 untestedTerms;         /* Not all WHERE terms resolved by outer loop */
  u8 eDistinct;             /* One of the WHERE_DISTINCT_* values below */
  int iTop;                 /* The very beginning of the WHERE loop */
  int iContinue;            /* Jump here to continue with next record */
  int iBreak;               /* Jump here to break out of the loop */
  int nLevel;               /* Number of nested loop */
  struct WhereClause *pWC;  /* Decomposition of the WHERE clause */
  struct WhereLoop *pLoops; /* List of all WhereLoop objects */
  double savedNQueryLoop;   /* pParse->nQueryLoop outside the WHERE loop */
  double nRowOut;           /* Estimated number of output rows */
  WhereLevel a[1];          /* Information about each nest loop in WHERE */
};

/* Allowed values for WhereInfo.eDistinct and DistinctCtx.eTnctType */
#define WHERE_DISTINCT_NOOP      0  /* DISTINCT keyword not used */

/* Forward reference
*/
typedef struct WhereClause WhereClause;
typedef struct WhereMaskSet WhereMaskSet;
typedef struct WhereOrInfo WhereOrInfo;
typedef struct WhereAndInfo WhereAndInfo;
typedef struct WhereCost WhereCost;






































/*
** The query generator uses an array of instances of this structure to
** help it analyze the subexpressions of the WHERE clause.  Each WHERE
** clause subexpression is separated from the others by AND operators,
** usually, or sometimes subexpressions separated by OR.
**
................................................................................
** bits in the Bitmask.  So, in the example above, the cursor numbers
** would be mapped into integers 0 through 7.
**
** The number of terms in a join is limited by the number of bits
** in prereqRight and prereqAll.  The default is 64 bits, hence SQLite
** is only able to process joins with 64 or fewer tables.
*/
typedef struct WhereTerm WhereTerm;
struct WhereTerm {
  Expr *pExpr;            /* Pointer to the subexpression that is this term */
  int iParent;            /* Disable pWC->a[iParent] when this term disabled */
  int leftCursor;         /* Cursor number of X in "X <op> <expr>" */
  union {
    int leftColumn;         /* Column number of X in "X <op> <expr>" */
    WhereOrInfo *pOrInfo;   /* Extra information if (eOperator & WO_OR)!=0 */
................................................................................
      WhereBestIdx sBOI;

      sBOI = *p;
      sBOI.pOrderBy = 0;
      sBOI.pDistinct = 0;
      sBOI.ppIdxInfo = 0;
      for(pOrTerm=pOrWC->a; pOrTerm<pOrWCEnd; pOrTerm++){
        WHERETRACE(("... Multi-index OR testing for term %d of %d....\n", 
          (pOrTerm - pOrWC->a), (pTerm - pWC->a)
        ));
        if( (pOrTerm->eOperator& WO_AND)!=0 ){
          sBOI.pWC = &pOrTerm->u.pAndInfo->wc;
          bestIndex(&sBOI);
        }else if( pOrTerm->leftCursor==iCur ){
          WhereClause tempWC;
          tempWC.pParse = pWC->pParse;
          tempWC.pMaskSet = pWC->pMaskSet;
................................................................................
        used |= sBOI.cost.used;
        if( rTotal>=p->cost.rCost ) break;
      }

      /* If there is an ORDER BY clause, increase the scan cost to account 
      ** for the cost of the sort. */
      if( p->pOrderBy!=0 ){
        WHERETRACE(("... sorting increases OR cost %.9g to %.9g\n",
                    rTotal, rTotal+nRow*estLog(nRow)));
        rTotal += nRow*estLog(nRow);
      }

      /* If the cost of scanning using this OR term for optimization is
      ** less than the current cost stored in pCost, replace the contents
      ** of pCost. */
      WHERETRACE(("... multi-index OR cost=%.9g nrow=%.9g\n", rTotal, nRow));
      if( rTotal<p->cost.rCost ){
        p->cost.rCost = rTotal;
        p->cost.used = used;
        p->cost.plan.nRow = nRow;
        p->cost.plan.nOBSat = p->i ? p->aLevel[p->i-1].plan.nOBSat : 0;
        p->cost.plan.wsFlags = flags;
        p->cost.plan.u.pTerm = pTerm;
................................................................................
    return;
  }

  /* Search for any equality comparison term */
  pWCEnd = &pWC->a[pWC->nTerm];
  for(pTerm=pWC->a; pTerm<pWCEnd; pTerm++){
    if( termCanDriveIndex(pTerm, pSrc, p->notReady) ){
      WHERETRACE(("auto-index reduces cost from %.1f to %.1f\n",
                    p->cost.rCost, costTempIdx));
      p->cost.rCost = costTempIdx;
      p->cost.plan.nRow = logN + 1;
      p->cost.plan.wsFlags = WHERE_TEMP_INDEX;
      p->cost.used = pTerm->prereqRight;
      break;
    }
  }
................................................................................
  struct sqlite3_index_constraint *pIdxCons;
  struct sqlite3_index_orderby *pIdxOrderBy;
  struct sqlite3_index_constraint_usage *pUsage;
  WhereTerm *pTerm;
  int nOrderBy;
  sqlite3_index_info *pIdxInfo;

  WHERETRACE(("Recomputing index info for %s...\n", pSrc->pTab->zName));

  /* 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;
    assert( IsPowerOfTwo(pTerm->eOperator & ~WO_EQUIV) );
    testcase( pTerm->eOperator & WO_IN );
................................................................................
** that this is required.
*/
static int vtabBestIndex(Parse *pParse, Table *pTab, sqlite3_index_info *p){
  sqlite3_vtab *pVtab = sqlite3GetVTable(pParse->db, pTab)->pVtab;
  int i;
  int rc;

  WHERETRACE(("xBestIndex for %s\n", pTab->zName));
  TRACE_IDX_INPUTS(p);
  rc = pVtab->pModule->xBestIndex(pVtab, p);
  TRACE_IDX_OUTPUTS(p);

  if( rc!=SQLITE_OK ){
    if( rc==SQLITE_NOMEM ){
      pParse->db->mallocFailed = 1;
................................................................................
    }
    if( rc==SQLITE_OK ){
      if( iUpper<=iLower ){
        *pRangeDiv = (double)p->aiRowEst[0];
      }else{
        *pRangeDiv = (double)p->aiRowEst[0]/(double)(iUpper - iLower);
      }
      WHERETRACE(("range scan regions: %u..%u  div=%g\n",
                  (u32)iLower, (u32)iUpper, *pRangeDiv));
      return SQLITE_OK;
    }
  }
#else
  UNUSED_PARAMETER(pParse);
  UNUSED_PARAMETER(p);
  UNUSED_PARAMETER(nEq);
................................................................................
    if( rc ) goto whereEqualScanEst_cancel;
  }else{
    pRhs = sqlite3ValueNew(pParse->db);
  }
  if( pRhs==0 ) return SQLITE_NOTFOUND;
  rc = whereKeyStats(pParse, p, pRhs, 0, a);
  if( rc==SQLITE_OK ){
    WHERETRACE(("equality scan regions: %d\n", (int)a[1]));
    *pnRow = a[1];
  }
whereEqualScanEst_cancel:
  sqlite3ValueFree(pRhs);
  return rc;
}
#endif /* defined(SQLITE_ENABLE_STAT3) */
................................................................................
    nEst = p->aiRowEst[0];
    rc = whereEqualScanEst(pParse, p, pList->a[i].pExpr, &nEst);
    nRowEst += nEst;
  }
  if( rc==SQLITE_OK ){
    if( nRowEst > p->aiRowEst[0] ) nRowEst = p->aiRowEst[0];
    *pnRow = nRowEst;
    WHERETRACE(("IN row estimate: est=%g\n", nRowEst));
  }
  return rc;
}
#endif /* defined(SQLITE_ENABLE_STAT3) */

/*
** Check to see if column iCol of the table with cursor iTab will appear
................................................................................
      uniqueNotNull = 0;
      isEq = 1;  /* "X IS NULL" means X has only a single value */
    }else if( pConstraint->prereqRight==0 ){
      isEq = 1;  /* Constraint "X=constant" means X has only a single value */
    }else{
      Expr *pRight = pConstraint->pExpr->pRight;
      if( pRight->op==TK_COLUMN ){
        WHERETRACE(("       .. isOrderedColumn(tab=%d,col=%d)",
                    pRight->iTable, pRight->iColumn));
        isEq = isOrderedColumn(p, pRight->iTable, pRight->iColumn);
        WHERETRACE((" -> isEq=%d\n", isEq));

        /* If the constraint is of the form X=Y where Y is an ordered value
        ** in an outer loop, then make sure the sort order of Y matches the
        ** sort order required for X. */
        if( isMatch && isEq>=2 && isEq!=pOBItem->sortOrder+2 ){
          testcase( isEq==2 );
          testcase( isEq==3 );
................................................................................
    char bDist = bDistInit;       /* True if index cannot help with DISTINCT */
    char bLookup = 0;             /* True if not a covering index */
    WhereTerm *pTerm;             /* A single term of the WHERE clause */
#ifdef SQLITE_ENABLE_STAT3
    WhereTerm *pFirstTerm = 0;    /* First term matching the index */
#endif

    WHERETRACE((
      "   %s(%s):\n",
      pSrc->pTab->zName, (pIdx ? pIdx->zName : "ipk")
    ));
    memset(&pc, 0, sizeof(pc));
    pc.plan.nOBSat = nPriorSat;

    /* Determine the values of pc.plan.nEq and nInMul */
    for(pc.plan.nEq=0; pc.plan.nEq<pProbe->nColumn; pc.plan.nEq++){
      int j = pProbe->aiColumn[pc.plan.nEq];
      pTerm = findTerm(pWC, iCur, j, p->notReady, eqTermMask, pIdx);
................................................................................
    ** naturally scan rows in the required order, set the appropriate flags
    ** in pc.plan.wsFlags. Otherwise, if there is an ORDER BY clause but
    ** the index will scan rows in a different order, set the bSort
    ** variable.  */
    if( bSort && (pSrc->jointype & JT_LEFT)==0 ){
      int bRev = 2;
      int bObUnique = 0;
      WHERETRACE(("      --> before isSortIndex: nPriorSat=%d\n",nPriorSat));
      pc.plan.nOBSat = isSortingIndex(p, pProbe, iCur, &bRev, &bObUnique);
      WHERETRACE(("      --> after  isSortIndex: bRev=%d bObU=%d nOBSat=%d\n",
                  bRev, bObUnique, pc.plan.nOBSat));
      if( nPriorSat<pc.plan.nOBSat || (pc.plan.wsFlags & WHERE_ALL_UNIQUE)!=0 ){
        pc.plan.wsFlags |= WHERE_ORDERED;
        if( bObUnique ) pc.plan.wsFlags |= WHERE_OB_UNIQUE;
      }
      if( nOrderBy==pc.plan.nOBSat ){
        bSort = 0;
        pc.plan.wsFlags |= WHERE_ROWID_RANGE|WHERE_COLUMN_RANGE;
................................................................................
          pc.plan.nRow /= 2;
        }
      }
      if( pc.plan.nRow<2 ) pc.plan.nRow = 2;
    }


    WHERETRACE((
      "      nEq=%d nInMul=%d rangeDiv=%d bSort=%d bLookup=%d wsFlags=0x%08x\n"
      "      notReady=0x%llx log10N=%.1f nRow=%.1f cost=%.1f\n"
      "      used=0x%llx nOBSat=%d\n",
      pc.plan.nEq, nInMul, (int)rangeDiv, bSort, bLookup, pc.plan.wsFlags,
      p->notReady, log10N, pc.plan.nRow, pc.rCost, pc.used,
      pc.plan.nOBSat
    ));

    /* If this index is the best we have seen so far, then record this
    ** index and its cost in the p->cost structure.
    */
    if( (!pIdx || pc.plan.wsFlags) && compareCost(&pc, &p->cost) ){
      p->cost = pc;
      p->cost.plan.wsFlags &= wsFlagMask;
................................................................................
  assert( p->pOrderBy || (p->cost.plan.wsFlags&WHERE_ORDERED)==0 );
  assert( p->cost.plan.u.pIdx==0 || (p->cost.plan.wsFlags&WHERE_ROWID_EQ)==0 );
  assert( pSrc->pIndex==0 
       || p->cost.plan.u.pIdx==0 
       || p->cost.plan.u.pIdx==pSrc->pIndex 
  );

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

/*
................................................................................
** analysis only.
*/
char sqlite3_query_plan[BMS*2*40];  /* Text of the join */
static int nQPlan = 0;              /* Next free slow in _query_plan[] */

#endif /* SQLITE_TEST */









/*
** Free a WhereInfo structure
*/
static void whereInfoFree(sqlite3 *db, WhereInfo *pWInfo){
  if( ALWAYS(pWInfo) ){
    int i;
................................................................................
        if( pIdx ){
          sqlite3DbFree(db, pIdx->zColAff);
          sqlite3DbFree(db, pIdx);
        }
      }
    }
    whereClauseClear(pWInfo->pWC);





    sqlite3DbFree(db, pWInfo);
  }
}































































































































/*
** 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
................................................................................
  ** If it is, then set pDistinct to NULL and WhereInfo.eDistinct to
  ** WHERE_DISTINCT_UNIQUE to tell the caller to ignore the DISTINCT.
  */
  if( pDistinct && isDistinctRedundant(pParse, pTabList, sWBI.pWC, pDistinct) ){
    pDistinct = 0;
    pWInfo->eDistinct = WHERE_DISTINCT_UNIQUE;
  }






























  /* Chose the best index to use for each table in the FROM clause.
  **
  ** This loop fills in the following fields:
  **
  **   pWInfo->a[].pIdx      The index to use for this level of the loop.
  **   pWInfo->a[].wsFlags   WHERE_xxx flags associated with pIdx
................................................................................
  ** clause.
  */
  sWBI.notValid = ~(Bitmask)0;
  sWBI.pOrderBy = pOrderBy;
  sWBI.n = nTabList;
  sWBI.pDistinct = pDistinct;
  andFlags = ~0;
  WHERETRACE(("*** Optimizer Start ***\n"));
  for(sWBI.i=iFrom=0, pLevel=pWInfo->a; sWBI.i<nTabList; sWBI.i++, pLevel++){
    WhereCost bestPlan;         /* Most efficient plan seen so far */
    Index *pIdx;                /* Index for FROM table at pTabItem */
    int j;                      /* For looping over FROM tables */
    int bestJ = -1;             /* The value of j */
    Bitmask m;                  /* Bitmask value for j or bestJ */
    int isOptimal;              /* Iterator for optimal/non-optimal search */
    int ckOptimal;              /* Do the optimal scan check */
    int nUnconstrained;         /* Number tables without INDEXED BY */
    Bitmask notIndexed;         /* Mask of tables that cannot use an index */

    memset(&bestPlan, 0, sizeof(bestPlan));
    bestPlan.rCost = SQLITE_BIG_DBL;
    WHERETRACE(("*** Begin search for loop %d ***\n", sWBI.i));

    /* Loop through the remaining entries in the FROM clause to find the
    ** next nested loop. The loop tests all FROM clause entries
    ** either once or twice. 
    **
    ** The first test is always performed if there are two or more entries
    ** remaining and never performed if there is only one FROM clause entry
................................................................................
        if( (m & sWBI.notValid)==0 ){
          assert( j>iFrom );
          continue;
        }
        sWBI.notReady = (isOptimal ? m : sWBI.notValid);
        if( sWBI.pSrc->pIndex==0 ) nUnconstrained++;
  
        WHERETRACE(("   === trying table %d (%s) with isOptimal=%d ===\n",
                    j, sWBI.pSrc->pTab->zName, isOptimal));
        assert( sWBI.pSrc->pTab );
#ifndef SQLITE_OMIT_VIRTUALTABLE
        if( IsVirtual(sWBI.pSrc->pTab) ){
          sWBI.ppIdxInfo = &pWInfo->a[j].pIdxInfo;
          bestVirtualIndex(&sWBI);
        }else 
#endif
................................................................................
          pWInfo->a[j].rOptCost = sWBI.cost.rCost;
        }else if( ckOptimal ){
          /* If two or more tables have nearly the same outer loop cost, but
          ** very different inner loop (optimal) cost, we want to choose
          ** for the outer loop that table which benefits the least from
          ** being in the inner loop.  The following code scales the 
          ** outer loop cost estimate to accomplish that. */
          WHERETRACE(("   scaling cost from %.1f to %.1f\n",
                      sWBI.cost.rCost,
                      sWBI.cost.rCost/pWInfo->a[j].rOptCost));
          sWBI.cost.rCost /= pWInfo->a[j].rOptCost;
        }

        /* Conditions under which this table becomes the best so far:
        **
        **   (1) The table must not depend on other tables that have not
        **       yet run.  (In other words, it must not depend on tables
................................................................................
        **       is defined by the compareCost() function above. 
        */
        if( (sWBI.cost.used&sWBI.notValid)==0                    /* (1) */
            && (nUnconstrained==0 || sWBI.pSrc->pIndex==0        /* (3) */
                || NEVER((sWBI.cost.plan.wsFlags & WHERE_NOT_FULLSCAN)!=0))
            && (bestJ<0 || compareCost(&sWBI.cost, &bestPlan))   /* (4) */
        ){
          WHERETRACE(("   === table %d (%s) is best so far\n"
                      "       cost=%.1f, nRow=%.1f, nOBSat=%d, wsFlags=%08x\n",
                      j, sWBI.pSrc->pTab->zName,
                      sWBI.cost.rCost, sWBI.cost.plan.nRow,
                      sWBI.cost.plan.nOBSat, sWBI.cost.plan.wsFlags));
          bestPlan = sWBI.cost;
          bestJ = j;
        }

        /* In a join like "w JOIN x LEFT JOIN y JOIN z"  make sure that
        ** table y (and not table z) is always the next inner loop inside
        ** of table x. */
................................................................................
    }
    assert( bestJ>=0 );
    assert( sWBI.notValid & getMask(pMaskSet, pTabList->a[bestJ].iCursor) );
    assert( bestJ==iFrom || (pTabList->a[iFrom].jointype & JT_LEFT)==0 );
    testcase( bestJ>iFrom && (pTabList->a[iFrom].jointype & JT_CROSS)!=0 );
    testcase( bestJ>iFrom && bestJ<nTabList-1
                          && (pTabList->a[bestJ+1].jointype & JT_LEFT)!=0 );
    WHERETRACE(("*** Optimizer selects table %d (%s) for loop %d with:\n"
                "    cost=%.1f, nRow=%.1f, nOBSat=%d, wsFlags=0x%08x\n",
                bestJ, pTabList->a[bestJ].pTab->zName,
                pLevel-pWInfo->a, bestPlan.rCost, bestPlan.plan.nRow,
                bestPlan.plan.nOBSat, bestPlan.plan.wsFlags));
    if( (bestPlan.plan.wsFlags & WHERE_DISTINCT)!=0 ){
      assert( pWInfo->eDistinct==0 );
      pWInfo->eDistinct = WHERE_DISTINCT_ORDERED;
    }
    andFlags &= bestPlan.plan.wsFlags;
    pLevel->plan = bestPlan.plan;
    pLevel->iTabCur = pTabList->a[bestJ].iCursor;

/* Forward reference
*/
typedef struct WhereClause WhereClause;
typedef struct WhereMaskSet WhereMaskSet;
typedef struct WhereOrInfo WhereOrInfo;
typedef struct WhereAndInfo WhereAndInfo;
typedef struct WhereCost WhereCost;
typedef struct WhereLoop WhereLoop;
typedef struct WherePath WherePath;
typedef struct WhereTerm WhereTerm;

/*
** Each instance of this object represents a way of evaluating one
** term of a join.  The WhereClause object holds a table of these
** objects using (iTab,prereq,iOb,nOb) as the primary key.  Note that the
** same join term might have multiple associated WhereLoop objects.
*/
struct WhereLoop {
  Bitmask prereq;       /* Bitmask of other loops that must run first */
  int iTab;             /* Index of the table coded by this loop */
  u16 iOb, nOb;         /* ORDER BY terms satisfied by this strategy */
  double rSetup;        /* One-time setup cost (ex: create transient index) */
  double rRun;          /* Cost of running each loop */
  double nOut;          /* Estimated number of output rows */
  u32 wsFlags;          /* WHERE_* flags describing the plan */
  u16 nEq;              /* Number of equality constraints */
  u16 nTerm;            /* Number of entries in aTerm[] */
  Index *pIndex;        /* Index used */
  WhereTerm *aTerm;     /* WhereTerms used */
  WhereLoop *pNextLoop; /* Next WhereLoop object in the WhereClause */
};

/*
** Each instance of this object holds a sequence of WhereLoop objects
** that implement some or all of the entire query plan.  
*/
struct WherePath {
  Bitmask maskLoop;     /* Bitmask of all WhereLoop objects in this path */
  double nRow;          /* Estimated number of rows generated by this path */
  double rCost;         /* Total cost of this path */
  WhereLoop *aLoop[1];  /* Array of WhereLoop objects implementing this path */
  WherePath *pNextPath; /* Next path in order of increasing cost */
  WherePath *pPrevPath; /* Previous path in cost order */
};

/*
** The query generator uses an array of instances of this structure to
** help it analyze the subexpressions of the WHERE clause.  Each WHERE
** clause subexpression is separated from the others by AND operators,
** usually, or sometimes subexpressions separated by OR.
**
................................................................................
** bits in the Bitmask.  So, in the example above, the cursor numbers
** would be mapped into integers 0 through 7.
**
** The number of terms in a join is limited by the number of bits
** in prereqRight and prereqAll.  The default is 64 bits, hence SQLite
** is only able to process joins with 64 or fewer tables.
*/

struct WhereTerm {
  Expr *pExpr;            /* Pointer to the subexpression that is this term */
  int iParent;            /* Disable pWC->a[iParent] when this term disabled */
  int leftCursor;         /* Cursor number of X in "X <op> <expr>" */
  union {
    int leftColumn;         /* Column number of X in "X <op> <expr>" */
    WhereOrInfo *pOrInfo;   /* Extra information if (eOperator & WO_OR)!=0 */
................................................................................
      WhereBestIdx sBOI;

      sBOI = *p;
      sBOI.pOrderBy = 0;
      sBOI.pDistinct = 0;
      sBOI.ppIdxInfo = 0;
      for(pOrTerm=pOrWC->a; pOrTerm<pOrWCEnd; pOrTerm++){
        /*WHERETRACE(("... Multi-index OR testing for term %d of %d....\n", 
          (pOrTerm - pOrWC->a), (pTerm - pWC->a)
        ));*/
        if( (pOrTerm->eOperator& WO_AND)!=0 ){
          sBOI.pWC = &pOrTerm->u.pAndInfo->wc;
          bestIndex(&sBOI);
        }else if( pOrTerm->leftCursor==iCur ){
          WhereClause tempWC;
          tempWC.pParse = pWC->pParse;
          tempWC.pMaskSet = pWC->pMaskSet;
................................................................................
        used |= sBOI.cost.used;
        if( rTotal>=p->cost.rCost ) break;
      }

      /* If there is an ORDER BY clause, increase the scan cost to account 
      ** for the cost of the sort. */
      if( p->pOrderBy!=0 ){
        /*WHERETRACE(("... sorting increases OR cost %.9g to %.9g\n",
                    rTotal, rTotal+nRow*estLog(nRow)));*/
        rTotal += nRow*estLog(nRow);
      }

      /* If the cost of scanning using this OR term for optimization is
      ** less than the current cost stored in pCost, replace the contents
      ** of pCost. */
      /*WHERETRACE(("... multi-index OR cost=%.9g nrow=%.9g\n", rTotal, nRow));*/
      if( rTotal<p->cost.rCost ){
        p->cost.rCost = rTotal;
        p->cost.used = used;
        p->cost.plan.nRow = nRow;
        p->cost.plan.nOBSat = p->i ? p->aLevel[p->i-1].plan.nOBSat : 0;
        p->cost.plan.wsFlags = flags;
        p->cost.plan.u.pTerm = pTerm;
................................................................................
    return;
  }

  /* Search for any equality comparison term */
  pWCEnd = &pWC->a[pWC->nTerm];
  for(pTerm=pWC->a; pTerm<pWCEnd; pTerm++){
    if( termCanDriveIndex(pTerm, pSrc, p->notReady) ){
      /*WHERETRACE(("auto-index reduces cost from %.1f to %.1f\n",
                    p->cost.rCost, costTempIdx));*/
      p->cost.rCost = costTempIdx;
      p->cost.plan.nRow = logN + 1;
      p->cost.plan.wsFlags = WHERE_TEMP_INDEX;
      p->cost.used = pTerm->prereqRight;
      break;
    }
  }
................................................................................
  struct sqlite3_index_constraint *pIdxCons;
  struct sqlite3_index_orderby *pIdxOrderBy;
  struct sqlite3_index_constraint_usage *pUsage;
  WhereTerm *pTerm;
  int nOrderBy;
  sqlite3_index_info *pIdxInfo;

  /*WHERETRACE(("Recomputing index info for %s...\n", pSrc->pTab->zName));*/

  /* 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;
    assert( IsPowerOfTwo(pTerm->eOperator & ~WO_EQUIV) );
    testcase( pTerm->eOperator & WO_IN );
................................................................................
** that this is required.
*/
static int vtabBestIndex(Parse *pParse, Table *pTab, sqlite3_index_info *p){
  sqlite3_vtab *pVtab = sqlite3GetVTable(pParse->db, pTab)->pVtab;
  int i;
  int rc;

  /*WHERETRACE(("xBestIndex for %s\n", pTab->zName));*/
  TRACE_IDX_INPUTS(p);
  rc = pVtab->pModule->xBestIndex(pVtab, p);
  TRACE_IDX_OUTPUTS(p);

  if( rc!=SQLITE_OK ){
    if( rc==SQLITE_NOMEM ){
      pParse->db->mallocFailed = 1;
................................................................................
    }
    if( rc==SQLITE_OK ){
      if( iUpper<=iLower ){
        *pRangeDiv = (double)p->aiRowEst[0];
      }else{
        *pRangeDiv = (double)p->aiRowEst[0]/(double)(iUpper - iLower);
      }
      /*WHERETRACE(("range scan regions: %u..%u  div=%g\n",
                  (u32)iLower, (u32)iUpper, *pRangeDiv));*/
      return SQLITE_OK;
    }
  }
#else
  UNUSED_PARAMETER(pParse);
  UNUSED_PARAMETER(p);
  UNUSED_PARAMETER(nEq);
................................................................................
    if( rc ) goto whereEqualScanEst_cancel;
  }else{
    pRhs = sqlite3ValueNew(pParse->db);
  }
  if( pRhs==0 ) return SQLITE_NOTFOUND;
  rc = whereKeyStats(pParse, p, pRhs, 0, a);
  if( rc==SQLITE_OK ){
    /*WHERETRACE(("equality scan regions: %d\n", (int)a[1]));*/
    *pnRow = a[1];
  }
whereEqualScanEst_cancel:
  sqlite3ValueFree(pRhs);
  return rc;
}
#endif /* defined(SQLITE_ENABLE_STAT3) */
................................................................................
    nEst = p->aiRowEst[0];
    rc = whereEqualScanEst(pParse, p, pList->a[i].pExpr, &nEst);
    nRowEst += nEst;
  }
  if( rc==SQLITE_OK ){
    if( nRowEst > p->aiRowEst[0] ) nRowEst = p->aiRowEst[0];
    *pnRow = nRowEst;
    /*WHERETRACE(("IN row estimate: est=%g\n", nRowEst));*/
  }
  return rc;
}
#endif /* defined(SQLITE_ENABLE_STAT3) */

/*
** Check to see if column iCol of the table with cursor iTab will appear
................................................................................
      uniqueNotNull = 0;
      isEq = 1;  /* "X IS NULL" means X has only a single value */
    }else if( pConstraint->prereqRight==0 ){
      isEq = 1;  /* Constraint "X=constant" means X has only a single value */
    }else{
      Expr *pRight = pConstraint->pExpr->pRight;
      if( pRight->op==TK_COLUMN ){
        /*WHERETRACE(("       .. isOrderedColumn(tab=%d,col=%d)",
                    pRight->iTable, pRight->iColumn));*/
        isEq = isOrderedColumn(p, pRight->iTable, pRight->iColumn);
        /*WHERETRACE((" -> isEq=%d\n", isEq));*/

        /* If the constraint is of the form X=Y where Y is an ordered value
        ** in an outer loop, then make sure the sort order of Y matches the
        ** sort order required for X. */
        if( isMatch && isEq>=2 && isEq!=pOBItem->sortOrder+2 ){
          testcase( isEq==2 );
          testcase( isEq==3 );
................................................................................
    char bDist = bDistInit;       /* True if index cannot help with DISTINCT */
    char bLookup = 0;             /* True if not a covering index */
    WhereTerm *pTerm;             /* A single term of the WHERE clause */
#ifdef SQLITE_ENABLE_STAT3
    WhereTerm *pFirstTerm = 0;    /* First term matching the index */
#endif

    /*WHERETRACE((
      "   %s(%s):\n",
      pSrc->pTab->zName, (pIdx ? pIdx->zName : "ipk")
    ));*/
    memset(&pc, 0, sizeof(pc));
    pc.plan.nOBSat = nPriorSat;

    /* Determine the values of pc.plan.nEq and nInMul */
    for(pc.plan.nEq=0; pc.plan.nEq<pProbe->nColumn; pc.plan.nEq++){
      int j = pProbe->aiColumn[pc.plan.nEq];
      pTerm = findTerm(pWC, iCur, j, p->notReady, eqTermMask, pIdx);
................................................................................
    ** naturally scan rows in the required order, set the appropriate flags
    ** in pc.plan.wsFlags. Otherwise, if there is an ORDER BY clause but
    ** the index will scan rows in a different order, set the bSort
    ** variable.  */
    if( bSort && (pSrc->jointype & JT_LEFT)==0 ){
      int bRev = 2;
      int bObUnique = 0;
      /*WHERETRACE(("      --> before isSortIndex: nPriorSat=%d\n",nPriorSat));*/
      pc.plan.nOBSat = isSortingIndex(p, pProbe, iCur, &bRev, &bObUnique);
      /*WHERETRACE(("      --> after  isSortIndex: bRev=%d bObU=%d nOBSat=%d\n",
                  bRev, bObUnique, pc.plan.nOBSat));*/
      if( nPriorSat<pc.plan.nOBSat || (pc.plan.wsFlags & WHERE_ALL_UNIQUE)!=0 ){
        pc.plan.wsFlags |= WHERE_ORDERED;
        if( bObUnique ) pc.plan.wsFlags |= WHERE_OB_UNIQUE;
      }
      if( nOrderBy==pc.plan.nOBSat ){
        bSort = 0;
        pc.plan.wsFlags |= WHERE_ROWID_RANGE|WHERE_COLUMN_RANGE;
................................................................................
          pc.plan.nRow /= 2;
        }
      }
      if( pc.plan.nRow<2 ) pc.plan.nRow = 2;
    }


    /*WHERETRACE((
      "      nEq=%d nInMul=%d rangeDiv=%d bSort=%d bLookup=%d wsFlags=0x%08x\n"
      "      notReady=0x%llx log10N=%.1f nRow=%.1f cost=%.1f\n"
      "      used=0x%llx nOBSat=%d\n",
      pc.plan.nEq, nInMul, (int)rangeDiv, bSort, bLookup, pc.plan.wsFlags,
      p->notReady, log10N, pc.plan.nRow, pc.rCost, pc.used,
      pc.plan.nOBSat
    ));*/

    /* If this index is the best we have seen so far, then record this
    ** index and its cost in the p->cost structure.
    */
    if( (!pIdx || pc.plan.wsFlags) && compareCost(&pc, &p->cost) ){
      p->cost = pc;
      p->cost.plan.wsFlags &= wsFlagMask;
................................................................................
  assert( p->pOrderBy || (p->cost.plan.wsFlags&WHERE_ORDERED)==0 );
  assert( p->cost.plan.u.pIdx==0 || (p->cost.plan.wsFlags&WHERE_ROWID_EQ)==0 );
  assert( pSrc->pIndex==0 
       || p->cost.plan.u.pIdx==0 
       || p->cost.plan.u.pIdx==pSrc->pIndex 
  );

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

/*
................................................................................
** analysis only.
*/
char sqlite3_query_plan[BMS*2*40];  /* Text of the join */
static int nQPlan = 0;              /* Next free slow in _query_plan[] */

#endif /* SQLITE_TEST */

/*
** Delete a WhereLoop object
*/
static void whereLoopDelete(sqlite3 *db, WhereLoop *p){
  sqlite3DbFree(db, p->aTerm);
  sqlite3DbFree(db, p);
}

/*
** Free a WhereInfo structure
*/
static void whereInfoFree(sqlite3 *db, WhereInfo *pWInfo){
  if( ALWAYS(pWInfo) ){
    int i;
................................................................................
        if( pIdx ){
          sqlite3DbFree(db, pIdx->zColAff);
          sqlite3DbFree(db, pIdx);
        }
      }
    }
    whereClauseClear(pWInfo->pWC);
    while( pWInfo->pLoops ){
      WhereLoop *p = pWInfo->pLoops;
      pWInfo->pLoops = p->pNextLoop;
      whereLoopDelete(db, p);
    }
    sqlite3DbFree(db, pWInfo);
  }
}

/*
** 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 no the template.
*/
static int whereLoopInsert(WhereInfo *pWInfo, WhereLoop *pTemplate){
  WhereLoop **ppPrev, *p;
  sqlite3 *db = pWInfo->pParse->db;

  /* Search for an existing WhereLoop to overwrite, or which takes
  ** priority over pTemplate.
  */
  for(ppPrev=&pWInfo->pLoops, p=*ppPrev; p; ppPrev=&p->pNextLoop, p=*ppPrev){
    if( p->iTab!=pTemplate->iTab ) continue;
    if( (p->prereq & pTemplate->prereq)==p->prereq
     && p->nOb>=pTemplate->nOb
     && p->iOb==pTemplate->iOb
     && p->rSetup<=pTemplate->rSetup
     && p->rRun<=pTemplate->rRun
    ){
      /* Already holding an equal or better WhereLoop.
      ** Return without changing or adding anything */
      return SQLITE_OK;
    }
    if( (p->prereq & pTemplate->prereq)==pTemplate->prereq
     && p->nOb<=pTemplate->nOb
     && p->iOb==pTemplate->iOb
     && p->rSetup>=pTemplate->rSetup
     && p->rRun>=pTemplate->rRun
    ){
      /* Overwrite an existing WhereLoop with a better one */
      sqlite3DbFree(db, p->aTerm);
      *ppPrev = p->pNextLoop;
      break;
    }
  }

  /* 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( p==0 ){
    p = sqlite3DbMallocRaw(db, sizeof(WhereLoop));
    if( p==0 ) return SQLITE_NOMEM;
  }
  *p = *pTemplate;
  p->pNextLoop = pWInfo->pLoops;
  pWInfo->pLoops = p;
  if( pTemplate->nTerm<=0 ) return SQLITE_OK;
  p->aTerm = sqlite3DbMallocRaw(db, pTemplate->nTerm*sizeof(p->aTerm[0]));
  if( p->aTerm==0 ){
    p->nTerm = 0;
    return SQLITE_NOMEM;
  }
  memcpy(p->aTerm, pTemplate->aTerm, pTemplate->nTerm*sizeof(p->aTerm[0]));
  return SQLITE_OK;
}

/*
** Add all WhereLoop objects for the iTab-th table of the join.  That
** table is guaranteed to be a b-tree table, not a virtual table.
*/
static void whereLoopAddBtree(
  WhereInfo *pWInfo,        /* WHERE clause information */
  int iTab,                 /* The table to process */
  Bitmask mExtra            /* Extra prerequesites for using this table */
){
  WhereLoop *pNew;          /* Template WhereLoop object */
  sqlite3 *db = pWInfo->pParse->db;

  pNew = sqlite3DbMallocZero(db, sizeof(*pNew));
  if( pNew==0 ) return;
  
  /* Insert a full table scan */
  pNew->iTab = iTab;
  pNew->rSetup = (double)0;
  pNew->rRun = (double)1000000;
  pNew->nOut = (double)1000000;
  whereLoopInsert(pWInfo, pNew);

  whereLoopDelete(db, pNew);
}

/*
** Add all WhereLoop objects for the iTab-th table of the join.  That
** table is guaranteed to be a virtual table.
*/
static void whereLoopAddVirtual(
  WhereInfo *pWInfo,        /* WHERE clause information */
  int iTab,                 /* The table to process */
  Bitmask mExtra            /* Extra prerequesites for using this table */
){
}

/*
** Add all WhereLoop objects for all tables 
*/
static void whereLoopAddAll(WhereInfo *pWInfo){
  Bitmask mExtra = 0;
  Bitmask mPrior = 0;
  int iTab;
  SrcList *pTabList = pWInfo->pTabList;
  struct SrcList_item *pItem;
  WhereClause *pWC = pWInfo->pWC;
  sqlite3 *db = pWInfo->pParse->db;

  /* Loop over the tables in the join, from left to right */
  for(iTab=0, pItem=pTabList->a; iTab<pTabList->nSrc; iTab++, pItem++){
    if( IsVirtual(pItem->pTab) ){
      whereLoopAddVirtual(pWInfo, iTab, mExtra);
    }else{
      whereLoopAddBtree(pWInfo, iTab, mExtra);
    }
    mPrior |= getMask(pWC->pMaskSet, pItem->iCursor);
    if( (pItem->jointype & (JT_LEFT|JT_CROSS))!=0 ){
      mExtra = mPrior;
    }
    if( db->mallocFailed ) break;
  }
}


/*
** 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
................................................................................
  ** If it is, then set pDistinct to NULL and WhereInfo.eDistinct to
  ** WHERE_DISTINCT_UNIQUE to tell the caller to ignore the DISTINCT.
  */
  if( pDistinct && isDistinctRedundant(pParse, pTabList, sWBI.pWC, pDistinct) ){
    pDistinct = 0;
    pWInfo->eDistinct = WHERE_DISTINCT_UNIQUE;
  }

  /* Construct the WhereLoop objects */
  WHERETRACE(("*** Optimizer Start ***\n"));
  whereLoopAddAll(pWInfo);

  /* Display all of the WhereLoop objects if wheretrace is enabled */
#if defined(SQLITE_DEBUG) \
    && (defined(SQLITE_TEST) || defined(SQLITE_ENABLE_WHERETRACE))
  if( sqlite3WhereTrace ){
    WhereLoop *p;
    int nb = 2*((nTabList+15)/16);
    for(p=pWInfo->pLoops; p; p=p->pNextLoop){
      struct SrcList_item *pItem = pTabList->a + p->iTab;
       Table *pTab = pItem->pTab;
      sqlite3DebugPrintf("%02d.%0*llx", p->iTab, nb, p->prereq);
      sqlite3DebugPrintf("     %s",
                         pItem->zAlias ? pItem->zAlias : pTab->zName);
      if( p->pIndex ){
        sqlite3DebugPrintf(" index %s nEq %d", p->pIndex->zName, p->nEq);
      }else{
        sqlite3DebugPrintf("\n");
      }
      sqlite3DebugPrintf("     wsFlags %08x OB %d,%d nTerm %d\n",
                         p->wsFlags, p->iOb, p->nOb, p->nTerm);
      sqlite3DebugPrintf("     cost %.2e + %.2e nOut %.2e\n",
                         p->prereq, p->rSetup, p->rRun, p->nOut);
    }
  }
#endif

  /* Chose the best index to use for each table in the FROM clause.
  **
  ** This loop fills in the following fields:
  **
  **   pWInfo->a[].pIdx      The index to use for this level of the loop.
  **   pWInfo->a[].wsFlags   WHERE_xxx flags associated with pIdx
................................................................................
  ** clause.
  */
  sWBI.notValid = ~(Bitmask)0;
  sWBI.pOrderBy = pOrderBy;
  sWBI.n = nTabList;
  sWBI.pDistinct = pDistinct;
  andFlags = ~0;

  for(sWBI.i=iFrom=0, pLevel=pWInfo->a; sWBI.i<nTabList; sWBI.i++, pLevel++){
    WhereCost bestPlan;         /* Most efficient plan seen so far */
    Index *pIdx;                /* Index for FROM table at pTabItem */
    int j;                      /* For looping over FROM tables */
    int bestJ = -1;             /* The value of j */
    Bitmask m;                  /* Bitmask value for j or bestJ */
    int isOptimal;              /* Iterator for optimal/non-optimal search */
    int ckOptimal;              /* Do the optimal scan check */
    int nUnconstrained;         /* Number tables without INDEXED BY */
    Bitmask notIndexed;         /* Mask of tables that cannot use an index */

    memset(&bestPlan, 0, sizeof(bestPlan));
    bestPlan.rCost = SQLITE_BIG_DBL;
    /*WHERETRACE(("*** Begin search for loop %d ***\n", sWBI.i));*/

    /* Loop through the remaining entries in the FROM clause to find the
    ** next nested loop. The loop tests all FROM clause entries
    ** either once or twice. 
    **
    ** The first test is always performed if there are two or more entries
    ** remaining and never performed if there is only one FROM clause entry
................................................................................
        if( (m & sWBI.notValid)==0 ){
          assert( j>iFrom );
          continue;
        }
        sWBI.notReady = (isOptimal ? m : sWBI.notValid);
        if( sWBI.pSrc->pIndex==0 ) nUnconstrained++;
  
        /*WHERETRACE(("   === trying table %d (%s) with isOptimal=%d ===\n",
                    j, sWBI.pSrc->pTab->zName, isOptimal));*/
        assert( sWBI.pSrc->pTab );
#ifndef SQLITE_OMIT_VIRTUALTABLE
        if( IsVirtual(sWBI.pSrc->pTab) ){
          sWBI.ppIdxInfo = &pWInfo->a[j].pIdxInfo;
          bestVirtualIndex(&sWBI);
        }else 
#endif
................................................................................
          pWInfo->a[j].rOptCost = sWBI.cost.rCost;
        }else if( ckOptimal ){
          /* If two or more tables have nearly the same outer loop cost, but
          ** very different inner loop (optimal) cost, we want to choose
          ** for the outer loop that table which benefits the least from
          ** being in the inner loop.  The following code scales the 
          ** outer loop cost estimate to accomplish that. */
          /*WHERETRACE(("   scaling cost from %.1f to %.1f\n",
                      sWBI.cost.rCost,
                      sWBI.cost.rCost/pWInfo->a[j].rOptCost));*/
          sWBI.cost.rCost /= pWInfo->a[j].rOptCost;
        }

        /* Conditions under which this table becomes the best so far:
        **
        **   (1) The table must not depend on other tables that have not
        **       yet run.  (In other words, it must not depend on tables
................................................................................
        **       is defined by the compareCost() function above. 
        */
        if( (sWBI.cost.used&sWBI.notValid)==0                    /* (1) */
            && (nUnconstrained==0 || sWBI.pSrc->pIndex==0        /* (3) */
                || NEVER((sWBI.cost.plan.wsFlags & WHERE_NOT_FULLSCAN)!=0))
            && (bestJ<0 || compareCost(&sWBI.cost, &bestPlan))   /* (4) */
        ){
          /*WHERETRACE(("   === table %d (%s) is best so far\n"
                      "       cost=%.1f, nRow=%.1f, nOBSat=%d, wsFlags=%08x\n",
                      j, sWBI.pSrc->pTab->zName,
                      sWBI.cost.rCost, sWBI.cost.plan.nRow,
                      sWBI.cost.plan.nOBSat, sWBI.cost.plan.wsFlags));*/
          bestPlan = sWBI.cost;
          bestJ = j;
        }

        /* In a join like "w JOIN x LEFT JOIN y JOIN z"  make sure that
        ** table y (and not table z) is always the next inner loop inside
        ** of table x. */
................................................................................
    }
    assert( bestJ>=0 );
    assert( sWBI.notValid & getMask(pMaskSet, pTabList->a[bestJ].iCursor) );
    assert( bestJ==iFrom || (pTabList->a[iFrom].jointype & JT_LEFT)==0 );
    testcase( bestJ>iFrom && (pTabList->a[iFrom].jointype & JT_CROSS)!=0 );
    testcase( bestJ>iFrom && bestJ<nTabList-1
                          && (pTabList->a[bestJ+1].jointype & JT_LEFT)!=0 );
    /*WHERETRACE(("*** Optimizer selects table %d (%s) for loop %d with:\n"
                "    cost=%.1f, nRow=%.1f, nOBSat=%d, wsFlags=0x%08x\n",
                bestJ, pTabList->a[bestJ].pTab->zName,
                pLevel-pWInfo->a, bestPlan.rCost, bestPlan.plan.nRow,
                bestPlan.plan.nOBSat, bestPlan.plan.wsFlags));*/
    if( (bestPlan.plan.wsFlags & WHERE_DISTINCT)!=0 ){
      assert( pWInfo->eDistinct==0 );
      pWInfo->eDistinct = WHERE_DISTINCT_ORDERED;
    }
    andFlags &= bestPlan.plan.wsFlags;
    pLevel->plan = bestPlan.plan;
    pLevel->iTabCur = pTabList->a[bestJ].iCursor;