SQLite

typedef struct WhereAndInfo WhereAndInfo;
typedef struct WhereLevel WhereLevel;
typedef struct WhereLoop WhereLoop;
typedef struct WherePath WherePath;
typedef struct WhereTerm WhereTerm;
typedef struct WhereLoopBuilder WhereLoopBuilder;
typedef struct WhereScan WhereScan;
typedef float WhereCost;

/*
** For each nested loop in a WHERE clause implementation, the WhereInfo
** structure contains a single instance of this structure.  This structure
** is intended to be private to the where.c module and should not be
** access or modified by other modules.
**

  Bitmask prereq;       /* Bitmask of other loops that must run first */
  Bitmask maskSelf;     /* Bitmask identifying table iTab */
#ifdef SQLITE_DEBUG
  char cId;             /* Symbolic ID of this loop for debugging use */
#endif
  u8 iTab;              /* Position in FROM clause of table for this loop */
  u8 iSortIdx;          /* Sorting index number.  0==None */
  u16 nLTerm;           /* Number of entries in aLTerm[] */
  u16 nLSlot;           /* Number of slots allocated for aLTerm[] */
  u32 wsFlags;          /* WHERE_* flags describing the plan */
  WhereCost rSetup;     /* One-time setup cost (ex: create transient index) */
  WhereCost rRun;       /* Cost of running each loop */
  WhereCost nOut;       /* Estimated number of output rows */
  union {
    struct {               /* Information for internal btree tables */
      int nEq;               /* Number of equality constraints */
      Index *pIndex;         /* Index used, or NULL */
    } btree;
    struct {               /* Information for virtual tables */
      int idxNum;            /* Index number */
      u8 needFree;           /* True if sqlite3_free(idxStr) is needed */
      u8 isOrdered;          /* True if satisfies ORDER BY */
      u16 omitMask;          /* Terms that may be omitted */
      char *idxStr;          /* Index identifier string */
    } vtab;
  } u;
  WhereTerm **aLTerm;   /* WhereTerms used */
  WhereLoop *pNextLoop; /* Next WhereLoop object in the WhereClause */
  WhereTerm *aLTermSpace[4];  /* Initial aLTerm[] space */
};

/* Forward declaration of methods */
static int whereLoopResize(sqlite3*, WhereLoop*, int);

/*
** Each instance of this object holds a sequence of WhereLoop objects
** that implement some or all of the entire query plan.  
*/
struct WherePath {
  Bitmask maskLoop;     /* Bitmask of all WhereLoop objects in this path */
  Bitmask revLoop;      /* aLoop[]s that should be reversed for ORDER BY */
  WhereCost nRow;       /* Estimated number of rows generated by this path */
  WhereCost rCost;      /* Total cost of this path */
  u8 isOrdered;         /* True if this path satisfies ORDER BY */
  u8 isOrderedValid;    /* True if the isOrdered field is valid */
  WhereLoop **aLoop;    /* Array of WhereLoop objects implementing this path */
};

/*
** The query generator uses an array of instances of this structure to

*/
struct WhereLoopBuilder {
  WhereInfo *pWInfo;        /* Information about this WHERE */
  WhereClause *pWC;         /* WHERE clause terms */
  ExprList *pOrderBy;       /* ORDER BY clause */
  WhereLoop *pNew;          /* Template WhereLoop */
  WhereLoop *pBest;         /* If non-NULL, store single best loop here */

};

/*
** The WHERE clause processing routine has two halves.  The
** first part does the start of the WHERE loop and the second
** half does the tail of the WHERE loop.  An instance of
** this structure is returned by the first half and passed

  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 */
  WhereMaskSet sMaskSet;    /* Map cursor numbers to bitmasks */
  WhereClause sWC;          /* Decomposition of the WHERE clause */
  WhereLoop *pLoops;        /* List of all WhereLoop objects */
  WhereCost savedNQueryLoop; /* pParse->nQueryLoop outside the WHERE loop */
  WhereCost nRowOut;        /* Estimated number of output rows */
  WhereLevel a[1];          /* Information about each nest loop in WHERE */
};

/*
** Bitmasks for the operators that indices are able to exploit.  An
** OR-ed combination of these values can be used when searching for
** terms in the where clause.

#define WHERE_TEMP_INDEX   0x00004000  /* Uses an ephemeral index */
#define WHERE_COVER_SCAN   0x00008000  /* Full scan of a covering index */

/*
** Return the estimated number of output rows from a WHERE clause
*/
double sqlite3WhereOutputRowCount(WhereInfo *pWInfo){
  return (double)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){

/*
** Prepare a crude estimate of the logarithm of the input value.
** The results need not be exact.  This is only used for estimating
** the total cost of performing operations with O(logN) or O(NlogN)
** complexity.  Because N is just a guess, it is no great tragedy if
** logN is a little off.
*/
static WhereCost estLog(WhereCost N){
  WhereCost logN = 1;
  WhereCost x = 10;
  while( N>x ){
    logN += 1;
    x *= 10;
  }
  return logN;
}

  /* Count the number of columns that will be added to the index
  ** and used to match WHERE clause constraints */
  nColumn = 0;
  pTable = pSrc->pTab;
  pWCEnd = &pWC->a[pWC->nTerm];
  pLoop = pLevel->pWLoop;
  idxCols = 0;



  for(pTerm=pWC->a; pTerm<pWCEnd && pLoop->nLTerm<mxConstraint; pTerm++){
    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( (idxCols & cMask)==0 ){
        if( whereLoopResize(pParse->db, pLoop, nColumn+1) ) return;
        pLoop->aLTerm[nColumn++] = pTerm;
        idxCols |= cMask;
      }
    }
  }
  assert( nColumn>0 );
  pLoop->u.btree.nEq = pLoop->nLTerm = nColumn;
  pLoop->wsFlags = WHERE_COLUMN_EQ | WHERE_IDX_ONLY | WHERE_INDEXED
                     | WHERE_TEMP_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

  /* Allocate the sqlite3_index_info structure
  */
  pIdxInfo = sqlite3DbMallocZero(pParse->db, sizeof(*pIdxInfo)
                           + (sizeof(*pIdxCons) + sizeof(*pUsage))*nTerm
                           + sizeof(*pIdxOrderBy)*nOrderBy );
  if( pIdxInfo==0 ){
    sqlite3ErrorMsg(pParse, "out of memory");

    return 0;
  }

  /* Initialize the structure.  The sqlite3_index_info structure contains
  ** many fields that are declared "const" to prevent xBestIndex from
  ** changing them.  We have to do some funky casting in order to
  ** initialize those fields.

  tRowcnt *aStat              /* OUT: stats written here */
){
  tRowcnt n;
  IndexSample *aSample;
  int i, eType;
  int isEq = 0;
  i64 v;
  WhereCost r, rS;

  assert( roundUp==0 || roundUp==1 );
  assert( pIdx->nSample>0 );
  if( pVal==0 ) return SQLITE_ERROR;
  n = pIdx->aiRowEst[0];
  aSample = pIdx->aSample;
  eType = sqlite3_value_type(pVal);

*/
static int whereRangeScanEst(
  Parse *pParse,       /* Parsing & code generating context */
  Index *p,            /* The index containing the range-compared column; "x" */
  int nEq,             /* index into p->aCol[] of the range-compared column */
  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 */
  WhereCost *pRangeDiv /* OUT: Reduce search space by this divisor */
){
  int rc = SQLITE_OK;

#ifdef SQLITE_ENABLE_STAT3

  if( nEq==0 && p->nSample ){
    sqlite3_value *pRangeVal;

        iUpper = a[0];
        if( (pUpper->eOperator & WO_LE)!=0 ) iUpper += a[1];
      }
      sqlite3ValueFree(pRangeVal);
    }
    if( rc==SQLITE_OK ){
      if( iUpper<=iLower ){
        *pRangeDiv = (WhereCost)p->aiRowEst[0];
      }else{
        *pRangeDiv = (WhereCost)p->aiRowEst[0]/(WhereCost)(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);
#endif
  assert( pLower || pUpper );
  *pRangeDiv = (WhereCost)1;
  if( pLower && (pLower->wtFlags & TERM_VNULL)==0 ) *pRangeDiv *= (WhereCost)4;
  if( pUpper ) *pRangeDiv *= (WhereCost)4;
  return rc;
}

#ifdef SQLITE_ENABLE_STAT3
/*
** Estimate the number of rows that will be returned based on
** an equality constraint x=VALUE and where that VALUE occurs in

** for a UTF conversion required for comparison.  The error is stored
** in the pParse structure.
*/
static int whereEqualScanEst(
  Parse *pParse,       /* Parsing & code generating context */
  Index *p,            /* The index whose left-most column is pTerm */
  Expr *pExpr,         /* Expression for VALUE in the x=VALUE constraint */
  WhereCost *pnRow     /* Write the revised row estimate here */
){
  sqlite3_value *pRhs = 0;  /* VALUE on right-hand side of pTerm */
  u8 aff;                   /* Column affinity */
  int rc;                   /* Subfunction return code */
  tRowcnt a[2];             /* Statistics */

  assert( p->aSample!=0 );

** for a UTF conversion required for comparison.  The error is stored
** in the pParse structure.
*/
static int whereInScanEst(
  Parse *pParse,       /* Parsing & code generating context */
  Index *p,            /* The index whose left-most column is pTerm */
  ExprList *pList,     /* The value list on the RHS of "x IN (v1,v2,v3,...)" */
  WhereCost *pnRow     /* Write the revised row estimate here */
){
  int rc = SQLITE_OK;         /* Subfunction return code */
  WhereCost nEst;                /* Number of rows for a single term */
  WhereCost nRowEst = (WhereCost)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 = p->aiRowEst[0];
    rc = whereEqualScanEst(pParse, p, pList->a[i].pExpr, &nEst);
    nRowEst += nEst;

  }

  /* Evaluate the equality constraints
  */
  assert( pIdx->nColumn>=nEq );
  for(j=0; j<nEq; j++){
    int r1;
    pTerm = pLoop->aLTerm[j];
    assert( pTerm!=0 );
    /* The following true for indices with redundant columns. 
    ** Ex: CREATE INDEX i1 ON t1(a,b,a); SELECT * FROM t1 WHERE a=0 AND b=0; */
    testcase( (pTerm->wtFlags & TERM_CODED)!=0 );
    testcase( pTerm->wtFlags & TERM_VIRTUAL ); /* EV: R-30575-11662 */
    r1 = codeEqualityTerm(pParse, pTerm, pLevel, j, bRev, regBase+j);
    if( r1!=regBase+j ){

#ifndef SQLITE_OMIT_VIRTUALTABLE
  if(  (pLoop->wsFlags & WHERE_VIRTUALTABLE)!=0 ){
    /* Case 1:  The table is a virtual-table.  Use the VFilter and VNext
    **          to access the data.
    */
    int iReg;   /* P3 Value for OP_VFilter */
    int addrNotFound;
    int nConstraint = pLoop->nLTerm;

    sqlite3ExprCachePush(pParse);
    iReg = sqlite3GetTempRange(pParse, nConstraint+2);
    addrNotFound = pLevel->addrBrk;
    for(j=0; j<nConstraint; j++){
      int iTarget = iReg+j+2;
      pTerm = pLoop->aLTerm[j];
      if( pTerm->eOperator & WO_IN ){
        codeEqualityTerm(pParse, pTerm, pLevel, j, bRev, iTarget);
        addrNotFound = pLevel->addrNxt;
      }else{
        sqlite3ExprCode(pParse, pTerm->pExpr->pRight, iTarget);
      }
    }
    sqlite3VdbeAddOp2(v, OP_Integer, pLoop->u.vtab.idxNum, iReg);
    sqlite3VdbeAddOp2(v, OP_Integer, nConstraint, iReg+1);
    sqlite3VdbeAddOp4(v, OP_VFilter, iCur, addrNotFound, iReg,
                      pLoop->u.vtab.idxStr,
                      pLoop->u.vtab.needFree ? P4_MPRINTF : P4_STATIC);
    pLoop->u.vtab.needFree = 0;
    for(j=0; j<nConstraint && j<16; j++){
      if( (pLoop->u.vtab.omitMask>>j)&1 ){
        disableTerm(pLevel, pLoop->aLTerm[j]);
      }
    }
    pLevel->op = OP_VNext;
    pLevel->p1 = iCur;
    pLevel->p2 = sqlite3VdbeCurrentAddr(v);
    sqlite3ReleaseTempRange(pParse, iReg, nConstraint+2);
    sqlite3ExprCachePop(pParse, 1);
  }else
#endif /* SQLITE_OMIT_VIRTUALTABLE */

  if( (pLoop->wsFlags & WHERE_IPK)!=0
   && (pLoop->wsFlags & (WHERE_COLUMN_IN|WHERE_COLUMN_EQ))!=0
  ){
    /* Case 2:  We can directly reference a single row using an
    **          equality comparison against the ROWID field.  Or
    **          we reference multiple rows using a "rowid IN (...)"
    **          construct.
    */
    assert( pLoop->u.btree.nEq==1 );
    iReleaseReg = sqlite3GetTempReg(pParse);
    pTerm = pLoop->aLTerm[0];
    assert( pTerm!=0 );
    assert( pTerm->pExpr!=0 );
    assert( omitTable==0 );
    testcase( pTerm->wtFlags & TERM_VIRTUAL ); /* EV: R-30575-11662 */
    iRowidReg = codeEqualityTerm(pParse, pTerm, pLevel, 0, bRev, iReleaseReg);
    addrNxt = pLevel->addrNxt;
    sqlite3VdbeAddOp2(v, OP_MustBeInt, iRowidReg, addrNxt);

    int start;
    int memEndValue = 0;
    WhereTerm *pStart, *pEnd;

    assert( omitTable==0 );
    j = 0;
    pStart = pEnd = 0;
    if( pLoop->wsFlags & WHERE_BTM_LIMIT ) pStart = pLoop->aLTerm[j++];
    if( pLoop->wsFlags & WHERE_TOP_LIMIT ) pEnd = pLoop->aLTerm[j++];
    if( bRev ){
      pTerm = pStart;
      pStart = pEnd;
      pEnd = pTerm;
    }
    if( pStart ){
      Expr *pX;             /* The expression that defines the start bound */

    }

    /* Find any inequality constraint terms for the start and end 
    ** of the range. 
    */
    j = nEq;
    if( pLoop->wsFlags & WHERE_BTM_LIMIT ){
      pRangeStart = pLoop->aLTerm[j++];
      nExtraReg = 1;
    }
    if( pLoop->wsFlags & WHERE_TOP_LIMIT ){
      pRangeEnd = pLoop->aLTerm[j++];
      nExtraReg = 1;
    }

    /* Generate code to evaluate all constraint terms using == or IN
    ** and store the values of those terms in an array of registers
    ** starting at regBase.
    */

    int regRowid = 0;                         /* Register holding rowid */
    int iLoopBody = sqlite3VdbeMakeLabel(v);  /* Start of loop body */
    int iRetInit;                             /* Address of regReturn init */
    int untestedTerms = 0;             /* Some terms not completely tested */
    int ii;                            /* Loop counter */
    Expr *pAndExpr = 0;                /* An ".. AND (...)" expression */
   
    pTerm = pLoop->aLTerm[0];
    assert( pTerm!=0 );
    assert( pTerm->eOperator & WO_OR );
    assert( (pTerm->wtFlags & TERM_ORINFO)!=0 );
    pOrWc = &pTerm->u.pOrInfo->wc;
    pLevel->op = OP_Return;
    pLevel->p1 = regReturn;

                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(" %-15s", z);
    sqlite3_free(z);
  }
  sqlite3DebugPrintf(" fg %05x N %d", p->wsFlags, p->nLTerm);
  sqlite3DebugPrintf(" cost %.2g,%.2g,%.2g\n",
                     p->prereq, p->rSetup, p->rRun, p->nOut);
}
#endif

/*
** Convert bulk memory into a valid WhereLoop that can be passed
** to whereLoopClear harmlessly.
*/
static 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.
*/
static void whereLoopClearUnion(sqlite3 *db, WhereLoop *p){
  if( (p->wsFlags & WHERE_VIRTUALTABLE)!=0 ){
    if( 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_TEMP_INDEX)!=0 && p->u.btree.pIndex!=0 ){
    sqlite3DbFree(db, p->u.btree.pIndex->zColAff);
    sqlite3DbFree(db, p->u.btree.pIndex);
    p->u.btree.pIndex = 0;
  }
}


/*
** Deallocate internal memory used by a WhereLoop object
*/
static void whereLoopClear(sqlite3 *db, WhereLoop *p){
  if( p->aLTerm!=p->aLTermSpace ) sqlite3DbFree(db, p->aLTerm);
  whereLoopClearUnion(db, p);
  whereLoopInit(p);
}

/*
** Increase the memory allocation for pLoop->aLTerm[] to be at least n.
*/
static int whereLoopResize(sqlite3 *db, WhereLoop *p, int n){
  WhereTerm **paNew;
  if( p->nLSlot>=n ) return SQLITE_OK;
  n = (n+7)&~7;
  paNew = sqlite3DbMallocRaw(db, sizeof(p->aLTerm[0])*n);
  if( paNew==0 ) return SQLITE_NOMEM;
  memcpy(paNew, p->aLTerm, sizeof(p->aLTerm[0])*p->nLSlot);
  if( p->aLTerm!=p->aLTermSpace ) sqlite3DbFree(db, p->aLTerm);
  p->aLTerm = paNew;
  p->nLSlot = n;
  return SQLITE_OK;
}

/*
** Transfer content from the second pLoop into the first.
*/
static int whereLoopXfer(sqlite3 *db, WhereLoop *pTo, WhereLoop *pFrom){
  if( whereLoopResize(db, pTo, pFrom->nLTerm) ) return SQLITE_NOMEM;
  whereLoopClearUnion(db, pTo);
  pTo->prereq = pFrom->prereq;
  pTo->maskSelf = pFrom->maskSelf;
  pTo->iTab = pFrom->iTab;
  pTo->iSortIdx = pFrom->iSortIdx;
  pTo->nLTerm = pFrom->nLTerm;
  pTo->rSetup = pFrom->rSetup;
  pTo->rRun = pFrom->rRun;
  pTo->nOut = pFrom->nOut;
  if( pTo->nLTerm ){
    memcpy(pTo->aLTerm, pFrom->aLTerm, pTo->nLTerm*sizeof(pTo->aLTerm[0]));
  }
  pTo->wsFlags = pFrom->wsFlags;
  pTo->u = pFrom->u;
  if( pFrom->wsFlags & WHERE_VIRTUALTABLE ){
    pFrom->u.vtab.needFree = 0;
  }else if( (pFrom->wsFlags & WHERE_TEMP_INDEX)!=0 && pFrom->u.btree.pIndex!=0 ){
    sqlite3DbFree(db, pFrom->u.btree.pIndex->zColAff);
    sqlite3DbFree(db, pFrom->u.btree.pIndex);
    pFrom->u.btree.pIndex = 0;
  }
  return SQLITE_OK;
}

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

**    (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
**    (5)  The template uses more terms of the same index but has no additional
**         dependencies          
*/
static int whereLoopInsert(WhereLoopBuilder *pBuilder, WhereLoop *pTemplate){
  WhereLoop **ppPrev, *p, *pNext = 0;

  WhereInfo *pWInfo = pBuilder->pWInfo;
  sqlite3 *db = pWInfo->pParse->db;

  /* If pBuilder->pBest is defined, then only keep track of the single
  ** best WhereLoop.  pBuilder->pBest->maskSelf==0 indicates that no
  ** prior WhereLoops have been evaluated and that the current pTemplate
  ** is therefore the first and hence the best and should be retained.
  */
  if( (p = pBuilder->pBest)!=0 ){
    if( p->maskSelf!=0 ){
      WhereCost rCost = p->rRun + p->rSetup;
      WhereCost rTemplate = pTemplate->rRun + pTemplate->rSetup;
      if( rCost < rTemplate ){
        goto whereLoopInsert_noop;
      }

      if( rCost == rTemplate && p->prereq <= pTemplate->prereq ){
        goto whereLoopInsert_noop;
      }
    }
    whereLoopXfer(db, p, pTemplate);


#if WHERETRACE_ENABLED
    if( sqlite3WhereTrace & 0x8 ){
      sqlite3DebugPrintf("ins-best: ");
      whereLoopPrint(pTemplate, pWInfo->pTabList);
    }
#endif
    return SQLITE_OK;
  }

  /* 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 || p->iSortIdx!=pTemplate->iSortIdx ) continue;
    if( (p->prereq & pTemplate->prereq)==p->prereq
     && p->rSetup<=pTemplate->rSetup
     && p->rRun<=pTemplate->rRun
    ){
      /* p is equal or better than pTemplate */
      if( p->nLTerm<pTemplate->nLTerm
       && (p->wsFlags & WHERE_INDEXED)!=0
       && (pTemplate->wsFlags & WHERE_INDEXED)!=0
       && p->u.btree.pIndex==pTemplate->u.btree.pIndex
       && p->prereq==pTemplate->prereq
      ){
        /* Overwrite an existing WhereLoop with an similar one that uses
        ** more terms of the index */

      whereLoopPrint(p, pWInfo->pTabList);
    }
    sqlite3DebugPrintf("ins-new:  ");
    whereLoopPrint(pTemplate, pWInfo->pTabList);
  }
#endif
  if( p==0 ){
    p = sqlite3DbMallocRaw(db, sizeof(WhereLoop));
    if( p==0 ) return SQLITE_NOMEM;



    whereLoopInit(p);


  }

  whereLoopXfer(db, p, pTemplate);
  p->pNextLoop = pNext;
  *ppPrev = p;




  if( (p->wsFlags & WHERE_VIRTUALTABLE)==0 ){
    Index *pIndex = p->u.btree.pIndex;
    if( pIndex && pIndex->tnum==0 ){
      p->u.btree.pIndex = 0;
    }


  }
  return SQLITE_OK;

  /* Jump here if the insert is a no-op */
whereLoopInsert_noop:
#if WHERETRACE_ENABLED
  if( sqlite3WhereTrace & 0x8 ){

  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 */
  int saved_nEq;                  /* Original value of pNew->u.btree.nEq */
  u32 saved_wsFlags;              /* Original value of pNew->wsFlags */
  WhereCost saved_nOut;           /* Original value of pNew->nOut */
  int iCol;                       /* Index of the column in the table */
  int rc = SQLITE_OK;             /* Return code */
  tRowcnt iRowEst;                /* Estimated index selectivity */
  WhereCost rLogSize;             /* Logarithm of table size */
  WhereTerm *pTop, *pBtm;         /* Top and bottom range constraints */

  pNew = pBuilder->pNew;
  if( db->mallocFailed ) return SQLITE_NOMEM;

  assert( (pNew->wsFlags & WHERE_VIRTUALTABLE)==0 );
  assert( pNew->u.btree.nEq<=pProbe->nColumn );

    iRowEst = pProbe->aiRowEst[pNew->u.btree.nEq+1];
  }else{
    iCol = -1;
    iRowEst = 1;
  }
  pTerm = whereScanInit(&scan, pBuilder->pWC, pSrc->iCursor, iCol,
                        opMask, pProbe);
  saved_nEq = pNew->u.btree.nEq;
  saved_nLTerm = pNew->nLTerm;
  saved_wsFlags = pNew->wsFlags;
  saved_prereq = pNew->prereq;
  saved_nOut = pNew->nOut;
  pNew->rSetup = (WhereCost)0;
  rLogSize = estLog(pProbe->aiRowEst[0]);
  for(; rc==SQLITE_OK && pTerm!=0; pTerm = whereScanNext(&scan)){
    int nIn = 1;
    if( pTerm->prereqRight & pNew->maskSelf ) continue;
    pNew->wsFlags = saved_wsFlags;
    pNew->u.btree.nEq = saved_nEq;
    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;
    pNew->rRun = rLogSize;
    if( pTerm->eOperator & WO_IN ){
      Expr *pExpr = pTerm->pExpr;
      pNew->wsFlags |= WHERE_COLUMN_IN;
      if( ExprHasProperty(pExpr, EP_xIsSelect) ){
        /* "x IN (SELECT ...)":  Assume the SELECT returns 25 rows */
        nIn = 25;
      }else if( ALWAYS(pExpr->x.pList && pExpr->x.pList->nExpr) ){
        /* "x IN (value, value, ...)" */
        nIn = pExpr->x.pList->nExpr;
      }
      pNew->rRun *= nIn;
      pNew->u.btree.nEq++;
      pNew->nOut = (WhereCost)iRowEst * nInMul * nIn;
    }else if( pTerm->eOperator & (WO_EQ) ){
      assert( (pNew->wsFlags & (WHERE_COLUMN_NULL|WHERE_COLUMN_IN))!=0
                  || nInMul==1 );
      pNew->wsFlags |= WHERE_COLUMN_EQ;
      if( iCol<0  
       || (pProbe->onError!=OE_None && nInMul==1
           && pNew->u.btree.nEq==pProbe->nColumn-1)
      ){
        testcase( pNew->wsFlags & WHERE_COLUMN_IN );
        pNew->wsFlags |= WHERE_ONEROW;
      }
      pNew->u.btree.nEq++;
      pNew->nOut = (WhereCost)iRowEst * nInMul;
    }else if( pTerm->eOperator & (WO_ISNULL) ){
      pNew->wsFlags |= WHERE_COLUMN_NULL;
      pNew->u.btree.nEq++;
      nIn = 2;  /* Assume IS NULL matches two rows */
      pNew->nOut = (WhereCost)iRowEst * nInMul * nIn;
    }else if( pTerm->eOperator & (WO_GT|WO_GE) ){
      pNew->wsFlags |= WHERE_COLUMN_RANGE|WHERE_BTM_LIMIT;
      pBtm = pTerm;
      pTop = 0;
    }else if( pTerm->eOperator & (WO_LT|WO_LE) ){
      pNew->wsFlags |= WHERE_COLUMN_RANGE|WHERE_TOP_LIMIT;
      pTop = pTerm;
      pBtm = (pNew->wsFlags & WHERE_BTM_LIMIT)!=0 ?
                     pNew->aLTerm[pNew->nLTerm-2] : 0;
    }
    if( pNew->wsFlags & WHERE_COLUMN_RANGE ){
      /* Adjust nOut and rRun for STAT3 range values */
      WhereCost rDiv;
      whereRangeScanEst(pParse, pProbe, pNew->u.btree.nEq,
                        pBtm, pTop, &rDiv);
      pNew->nOut = saved_nOut/rDiv;
    }
#ifdef SQLITE_ENABLE_STAT3
    if( pNew->u.btree.nEq==1 && pProbe->nSample ){
      if( (pTerm->eOperator & (WO_EQ|WO_ISNULL))!=0 ){
        rc = whereEqualScanEst(pParse, pProbe, pTerm->pExpr->pRight,
                               &pNew->nOut);
      }else if( (pTerm->eOperator & WO_IN)

    if( (pNew->wsFlags & WHERE_TOP_LIMIT)==0
     && pNew->u.btree.nEq<=pProbe->nColumn
     && pProbe->zName!=0
    ){
      whereLoopAddBtreeIndex(pBuilder, pSrc, pProbe, nInMul*nIn);
    }
  }
  pNew->prereq = saved_prereq;
  pNew->u.btree.nEq = saved_nEq;
  pNew->wsFlags = saved_wsFlags;
  pNew->nOut = saved_nOut;
  pNew->nLTerm = saved_nLTerm;
  return rc;
}

/*
** Return True if it is possible that pIndex might be useful in
** implementing the ORDER BY clause in pBuilder.
**

  int 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 */
  WhereCost rSize;               /* number of rows in the table */
  WhereCost rLogSize;            /* Logarithm of the number of rows in the table */
  
  pNew = pBuilder->pNew;
  pWInfo = pBuilder->pWInfo;
  pTabList = pWInfo->pTabList;
  pSrc = pTabList->a + pNew->iTab;
  assert( !IsVirtual(pSrc->pTab) );

    if( pSrc->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 = (WhereCost)pSrc->pTab->nRowEst;
  rLogSize = estLog(rSize);

  /* Automatic indexes */
  if( !pBuilder->pBest
   && pTabList->nSrc>1
   && (pWInfo->pParse->db->flags & SQLITE_AutoIndex)!=0 
   && !pSrc->viaCoroutine
   && !pSrc->notIndexed
   && !pSrc->isCorrelated
  ){
    /* Generate auto-index WhereLoops */
    WhereClause *pWC = pBuilder->pWC;
    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->u.btree.pIndex = 0;
        pNew->nLTerm = 1;
        pNew->aLTerm[0] = pTerm;
        pNew->rSetup = 20*rLogSize*pSrc->pTab->nRowEst;
        pNew->nOut = (WhereCost)10;
        pNew->rRun = rLogSize + pNew->nOut;
        pNew->wsFlags = WHERE_TEMP_INDEX;
        pNew->prereq = mExtra | pTerm->prereqRight;
        rc = whereLoopInsert(pBuilder, pNew);
      }
    }
  }

  /* Loop over all indices
  */
  for(; rc==SQLITE_OK && pProbe; pProbe=pProbe->pNext, iSortIdx++){
    pNew->u.btree.nEq = 0;
    pNew->nLTerm = 0;
    pNew->iSortIdx = 0;
    pNew->rSetup = (WhereCost)0;
    pNew->prereq = mExtra;
    pNew->u.btree.pIndex = pProbe;
    b = indexMightHelpWithOrderBy(pBuilder, pProbe, pSrc->iCursor);
    if( pProbe->tnum<=0 ){
      /* Integer primary key index */
      pNew->wsFlags = WHERE_IPK;

  sqlite3 *db;
  sqlite3_index_info *pIdxInfo;
  struct sqlite3_index_constraint *pIdxCons;
  struct sqlite3_index_constraint_usage *pUsage;
  WhereTerm *pTerm;
  int i, j;
  int iTerm, mxTerm;
  int nConstraint;
  int seenIn = 0;              /* True if an IN operator is seen */
  int seenVar = 0;             /* True if a non-constant constraint is seen */
  int iPhase;                  /* 0: const w/o IN, 1: const, 2: no IN,  2: IN */
  WhereLoop *pNew;
  int rc = SQLITE_OK;

  pWInfo = pBuilder->pWInfo;
  pParse = pWInfo->pParse;
  db = pParse->db;
  pWC = pBuilder->pWC;
  pNew = pBuilder->pNew;
  pSrc = &pWInfo->pTabList->a[pNew->iTab];
  pTab = pSrc->pTab;
  assert( IsVirtual(pTab) );
  pIdxInfo = allocateIndexInfo(pParse, pWC, pSrc, pBuilder->pOrderBy);
  if( pIdxInfo==0 ) return SQLITE_NOMEM;
  pNew->prereq = 0;
  pNew->rSetup = 0;
  pNew->wsFlags = WHERE_VIRTUALTABLE;
  pNew->nLTerm = 0;
  pNew->u.vtab.needFree = 0;
  pUsage = pIdxInfo->aConstraintUsage;
  nConstraint = pIdxInfo->nConstraint;
  if( whereLoopResize(db, pNew, nConstraint) ) return SQLITE_NOMEM;

  for(iPhase=0; iPhase<=3; iPhase++){
    if( !seenIn && (iPhase&1)!=0 ){
      iPhase++;
      if( iPhase>3 ) break;
    }
    if( !seenVar && iPhase>1 ) break;

    }
    memset(pUsage, 0, sizeof(pUsage[0])*pIdxInfo->nConstraint);
    if( pIdxInfo->needToFreeIdxStr ) sqlite3_free(pIdxInfo->idxStr);
    pIdxInfo->idxStr = 0;
    pIdxInfo->idxNum = 0;
    pIdxInfo->needToFreeIdxStr = 0;
    pIdxInfo->orderByConsumed = 0;
    /* ((WhereCost)2) In case of SQLITE_OMIT_FLOATING_POINT... */
    pIdxInfo->estimatedCost = SQLITE_BIG_DBL / ((WhereCost)2);
    rc = vtabBestIndex(pParse, pTab, pIdxInfo);
    if( rc ) goto whereLoopAddVtab_exit;
    pIdxCons = *(struct sqlite3_index_constraint**)&pIdxInfo->aConstraint;
    pNew->prereq = 0;
    mxTerm = -1;
    assert( pNew->nLSlot>=nConstraint );
    for(i=0; i<nConstraint; i++) pNew->aLTerm[i] = 0;
    pNew->u.vtab.omitMask = 0;
    for(i=0; i<nConstraint; i++, pIdxCons++){
      if( (iTerm = pUsage[i].argvIndex - 1)>=0 ){

        j = pIdxCons->iTermOffset;
        if( iTerm>=nConstraint
         || j<0
         || j>=pWC->nTerm
         || pNew->aLTerm[iTerm]!=0
        ){
          rc = SQLITE_ERROR;
          sqlite3ErrorMsg(pParse, "%s.xBestIndex() malfunction", pTab->zName);
          goto whereLoopAddVtab_exit;
        }
        pTerm = &pWC->a[j];
        pNew->prereq |= pTerm->prereqRight;
        assert( iTerm<pNew->nLSlot );
        pNew->aLTerm[iTerm] = pTerm;
        if( iTerm>mxTerm ) mxTerm = iTerm;
        if( iTerm<16 && pUsage[i].omit ) pNew->u.vtab.omitMask |= 1<<iTerm;
        if( (pTerm->eOperator & WO_IN)!=0 ){
          if( pUsage[i].omit==0 ){
            /* Do not attempt to use an IN constraint if the virtual table
            ** says that the equivalent EQ constraint cannot be safely omitted.
            ** If we do attempt to use such a constraint, some rows might be
            ** repeated in the output. */
            break;
          }
          /* 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;
        }
      }
    }
    if( i>=nConstraint ){
      pNew->nLTerm = mxTerm+1;
      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 = (u8)((pIdxInfo->nOrderBy!=0)
                                     && pIdxInfo->orderByConsumed);
      pNew->rSetup = (WhereCost)0;
      pNew->rRun = pIdxInfo->estimatedCost;
      pNew->nOut = (WhereCost)25;
      whereLoopInsert(pBuilder, pNew);
      if( pNew->u.vtab.needFree ){
        sqlite3_free(pNew->u.vtab.idxStr);
        pNew->u.vtab.needFree = 0;
      }
    }
  }  

  WhereLoop sBest;
  struct SrcList_item *pItem;
  
  pWC = pBuilder->pWC;
  if( pWInfo->wctrlFlags & WHERE_AND_ONLY ) return SQLITE_OK;
  pWCEnd = pWC->a + pWC->nTerm;
  pNew = pBuilder->pNew;
  whereLoopInit(&sBest);

  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;
      WhereCost rTotal = 0;
      WhereCost nRow = 0;
      Bitmask prereq = mExtra;
    
      pItem = pWInfo->pTabList->a + pNew->iTab;
      iCur = pItem->iCursor;
      sSubBuild = *pBuilder;
      sSubBuild.pOrderBy = 0;
      sSubBuild.pBest = &sBest;

          tempWC.nTerm = 1;
          tempWC.a = pOrTerm;
          sSubBuild.pWC = &tempWC;
        }else{
          continue;
        }
        sBest.maskSelf = 0;
        sBest.rSetup = 0;
        sBest.rRun = 0;
        if( IsVirtual(pItem->pTab) ){
          rc = whereLoopAddVirtual(&sSubBuild, mExtra);
        }else{
          rc = whereLoopAddBtree(&sSubBuild, mExtra);
        }
        if( sBest.maskSelf==0 ) break;
        assert( sBest.rSetup==(WhereCost)0 );
        rTotal += sBest.rRun;
        nRow += sBest.nOut;
        prereq |= sBest.prereq;
      }
      assert( pNew->nLSlot>=1 );
      pNew->nLTerm = 1;
      pNew->aLTerm[0] = pTerm;
      pNew->wsFlags = WHERE_MULTI_OR;
      pNew->rSetup = (WhereCost)0;
      pNew->rRun = rTotal;
      pNew->nOut = nRow;
      pNew->prereq = prereq;
      memset(&pNew->u, 0, sizeof(pNew->u));
      rc = whereLoopInsert(pBuilder, pNew);
    }
  }
  whereLoopClear(pWInfo->pParse->db, &sBest);
  return rc;
}

/*
** Add all WhereLoop objects for all tables 
*/
static int whereLoopAddAll(WhereLoopBuilder *pBuilder){
  WhereInfo *pWInfo = pBuilder->pWInfo;
  Bitmask mExtra = 0;
  Bitmask mPrior = 0;
  int iTab;
  SrcList *pTabList = pWInfo->pTabList;
  struct SrcList_item *pItem;

  sqlite3 *db = pWInfo->pParse->db;
  int nTabList = pWInfo->nLevel;
  int rc = SQLITE_OK;
  WhereLoop *pNew;

  /* Loop over the tables in the join, from left to right */
  pBuilder->pNew = pNew = sqlite3DbMallocZero(db, sizeof(WhereLoop));
  if( pNew==0 ) return SQLITE_NOMEM;
  pNew->aLTerm = pNew->aLTermSpace;






  pNew->nLSlot = ArraySize(pNew->aLTermSpace);



  for(iTab=0, pItem=pTabList->a; iTab<nTabList; iTab++, pItem++){
    pNew->iTab = iTab;
    pNew->maskSelf = getMask(&pWInfo->sMaskSet, pItem->iCursor);
    if( (pItem->jointype & (JT_LEFT|JT_CROSS))!=0 ){
      mExtra = mPrior;
    }
    if( IsVirtual(pItem->pTab) ){
      rc = whereLoopAddVirtual(pBuilder, mExtra);
    }else{
      rc = whereLoopAddBtree(pBuilder, mExtra);
    }
    if( rc==SQLITE_OK ){
      rc = whereLoopAddOr(pBuilder, mExtra);
    }
    mPrior |= pNew->maskSelf;
    if( rc || db->mallocFailed ) break;
  }

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

/*
** Examine a WherePath (with the addition of the extra WhereLoop of the 5th

      }

      /* For every term of the index that is constrained by == or IS NULL,
      ** mark off corresponding ORDER BY terms wherever they occur
      ** in the ORDER BY clause.
      */
      for(i=0; i<pLoop->u.btree.nEq; i++){
        pTerm = pLoop->aLTerm[i];
        if( (pTerm->eOperator & (WO_EQ|WO_ISNULL))==0 ) continue;
        iColumn = pTerm->u.leftColumn;
        for(j=0; j<nOrderBy; j++){
          if( MASKBIT(j) & obSat ) continue;
          pOBExpr = sqlite3ExprSkipCollate(pOrderBy->a[j].pExpr);
          if( pOBExpr->op!=TK_COLUMN ) continue;
          if( pOBExpr->iTable!=iCur ) continue;

      rev = revSet = 0;
      distinctColumns = 0;
      for(j=0; j<=nColumn; j++){
        u8 bOnce;   /* True to run the ORDER BY search loop */

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

        /* Get the column number in the table (iColumn) and sort order
        ** (revIdx) for the j-th column of the index.

** Given the list of WhereLoop objects on pWInfo->pLoops, this routine
** attempts to find the lowest cost path that visits each WhereLoop
** once.  This path is then loaded into the pWInfo->a[].pWLoop fields.
**
** Return SQLITE_OK on success or SQLITE_NOMEM of a memory allocation
** error occurs.
*/
static int wherePathSolver(WhereInfo *pWInfo, WhereCost nRowEst){
  int mxChoice;             /* Maximum number of simultaneous paths tracked */
  int nLoop;                /* Number of terms in the join */
  sqlite3 *db;              /* The database connection */
  int iLoop;                /* Loop counter over the terms of the join */
  int ii, jj;               /* Loop counters */
  WhereCost rCost;             /* Cost of a path */
  WhereCost mxCost;            /* Maximum cost of a set of paths */
  WhereCost rSortCost;         /* Cost to do a sort */
  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 */

  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;
  }

  /* Seed the search with a single WherePath containing zero WhereLoops */
  aFrom[0].nRow = (WhereCost)1;
  nFrom = 1;

  /* Precompute the cost of sorting the final result set, if the caller
  ** to sqlite3WhereBegin() was concerned about sorting */
  rSortCost = (WhereCost)0;
  if( pWInfo->pOrderBy==0 || nRowEst<=0.0 ){
    aFrom[0].isOrderedValid = 1;
  }else{
    /* Compute an estimate on the cost to sort the entire result set */
    rSortCost = nRowEst*estLog(nRowEst);
#ifdef WHERETRACE_ENABLED
    if( sqlite3WhereTrace>=2 ){

#endif

  /* Open all tables in the pTabList and any indices selected for
  ** searching those tables.
  */
  sqlite3CodeVerifySchema(pParse, -1); /* Insert the cookie verifier Goto */
  notReady = ~(Bitmask)0;
  pWInfo->nRowOut = (WhereCost)1;
  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;
    WhereLoop *pLoop;

    pTabItem = &pTabList->a[pLevel->iFrom];