SQLite

/*
** 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.
**
*************************************************************************
** Internal interface definitions for SQLite.
**
** @(#) $Id: sqliteInt.h,v 1.801 2008/12/05 02:36:34 drh Exp $
*/
#ifndef _SQLITEINT_H_
#define _SQLITEINT_H_

/*
** Include the configuration header output by 'configure' if we're using the
** autoconf-based build

** index information for the i-th loop of the join.  pBestInfo is always
** either NULL or a copy of some pIdxInfo.  So for cleanup it is 
** sufficient to free all of the pIdxInfo pointers.
** 
*/
struct WhereLevel {
  int iFrom;            /* Which entry in the FROM clause */
  int wsFlags;          /* "Where-Scan Flags" associated with this level */
  int iMem;             /* First memory cell used by this level */
  int iLeftJoin;        /* Memory cell used to implement LEFT OUTER JOIN */
  Index *pIdx;          /* Index used.  NULL if no index */
  int iTabCur;          /* The VDBE cursor used to access the table */
  int iIdxCur;          /* The VDBE cursor used to access pIdx */
  int brk;              /* Jump here to break out of the loop */
  int nxt;              /* Jump here to start the next IN combination */

  ** we need a place to cache index information for each table in the
  ** FROM clause and the WhereLevel structure is a convenient place.
  */
  sqlite3_index_info *pIdxInfo;  /* Index info for n-th source table */
};

/*
** Flags appropriate for the wctrlFlags parameter of sqlite3WhereBegin().
*/
#define WHERE_ORDERBY_NORMAL     0   /* No-op */
#define WHERE_ORDERBY_MIN        1   /* ORDER BY processing for min() func */
#define WHERE_ORDERBY_MAX        2   /* ORDER BY processing for max() func */
#define WHERE_ONEPASS_DESIRED    4   /* Want to do one-pass UPDATE/DELETE */

/*

** 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".
**
** $Id: where.c,v 1.331 2008/12/05 02:36:34 drh Exp $
*/
#include "sqliteInt.h"

/*
** Trace output macros
*/
#if defined(SQLITE_TEST) || defined(SQLITE_DEBUG)

** translates these sparse cursor numbers into consecutive integers
** beginning with 0 in order to make the best possible use of the available
** bits in the Bitmask.  So, in the example above, the cursor numbers
** would be mapped into integers 0 through 7.
*/
typedef struct WhereTerm WhereTerm;
struct WhereTerm {
  Expr *pExpr;            /* Pointer to the subexpression that is this term */
  i16 iParent;            /* Disable pWC->a[iParent] when this term disabled */
  i16 leftCursor;         /* Cursor number of X in "X <op> <expr>" */
  i16 leftColumn;         /* Column number of X in "X <op> <expr>" */
  u16 eOperator;          /* A WO_xx value describing <op> */
  u8 wtFlags;             /* TERM_xxx bit flags.  See below */
  u8 nChild;              /* Number of children that must disable us */
  WhereClause *pWC;       /* The clause this term is part of */
  Bitmask prereqRight;    /* Bitmask of tables used by pExpr->pRight */
  Bitmask prereqAll;      /* Bitmask of tables referenced by pExpr */
};

/*
** Allowed values of WhereTerm.wtFlags
*/
#define TERM_DYNAMIC    0x01   /* Need to call sqlite3ExprDelete(db, pExpr) */
#define TERM_VIRTUAL    0x02   /* Added by the optimizer.  Do not code */
#define TERM_CODED      0x04   /* This term is already coded */
#define TERM_COPIED     0x08   /* Has a child */
#define TERM_OR_OK      0x10   /* Used during OR-clause processing */

/*
** 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 WO_IN     0x001
#define WO_EQ     0x002
#define WO_LT     (WO_EQ<<(TK_LT-TK_EQ))
#define WO_LE     (WO_EQ<<(TK_LE-TK_EQ))
#define WO_GT     (WO_EQ<<(TK_GT-TK_EQ))
#define WO_GE     (WO_EQ<<(TK_GE-TK_EQ))
#define WO_MATCH  0x040
#define WO_ISNULL 0x080
#define WO_OR     0x100

/*
** Value for wsFlags returned by bestIndex().  These flags determine which
** search strategies are appropriate.
**
** The least significant 12 bits is reserved as a mask for WO_ values above.
** The WhereLevel.wtFlags field is usually set to WO_IN|WO_EQ|WO_ISNULL.
** But if the table is the right table of a left join, WhereLevel.wtFlags
** is set to WO_IN|WO_EQ.  The WhereLevel.wtFlags field can then be used as
** the "op" parameter to findTerm when we are resolving equality constraints.
** ISNULL constraints will then not be used on the right table of a left
** join.  Tickets #2177 and #2189.
*/
#define WHERE_ROWID_EQ     0x00001000  /* rowid=EXPR or rowid IN (...) */
#define WHERE_ROWID_RANGE  0x00002000  /* rowid<EXPR and/or rowid>EXPR */
#define WHERE_COLUMN_EQ    0x00010000  /* x=EXPR or x IN (...) */
#define WHERE_COLUMN_RANGE 0x00020000  /* x<EXPR and/or x>EXPR */
#define WHERE_COLUMN_IN    0x00040000  /* x IN (...) */
#define WHERE_TOP_LIMIT    0x00100000  /* x<EXPR or x<=EXPR constraint */
#define WHERE_BTM_LIMIT    0x00200000  /* x>EXPR or x>=EXPR constraint */
#define WHERE_IDX_ONLY     0x00800000  /* Use index only - omit table */
#define WHERE_ORDERBY      0x01000000  /* Output will appear in correct order */
#define WHERE_REVERSE      0x02000000  /* Scan in reverse order */
#define WHERE_UNIQUE       0x04000000  /* Selects no more than one row */
#define WHERE_VIRTUALTABLE 0x08000000  /* Use virtual-table processing */
#define WHERE_MULTI_OR     0x10000000  /* OR using multiple indices */

/*
** Initialize a preallocated WhereClause structure.
*/
static void whereClauseInit(
  WhereClause *pWC,        /* The WhereClause to be initialized */
  Parse *pParse,           /* The parsing context */

** itself is not freed.  This routine is the inverse of whereClauseInit().
*/
static void whereClauseClear(WhereClause *pWC){
  int i;
  WhereTerm *a;
  sqlite3 *db = pWC->pParse->db;
  for(i=pWC->nTerm-1, a=pWC->a; i>=0; i--, a++){
    if( a->wtFlags & TERM_DYNAMIC ){
      sqlite3ExprDelete(db, a->pExpr);
    }
  }
  if( pWC->a!=pWC->aStatic ){
    sqlite3DbFree(db, pWC->a);
  }
}

/*
** Add a new entries to the WhereClause structure.  Increase the allocated
** space as necessary.
**
** If the wtFlags argument includes TERM_DYNAMIC, then responsibility
** for freeing the expression p is assumed by the WhereClause object.
**
** WARNING:  This routine might reallocate the space used to store
** WhereTerms.  All pointers to WhereTerms should be invalidated after
** calling this routine.  Such pointers may be reinitialized by referencing
** the pWC->a[] array.
*/
static int whereClauseInsert(WhereClause *pWC, Expr *p, int wtFlags){
  WhereTerm *pTerm;
  int idx;
  if( pWC->nTerm>=pWC->nSlot ){
    WhereTerm *pOld = pWC->a;
    sqlite3 *db = pWC->pParse->db;
    pWC->a = sqlite3DbMallocRaw(db, sizeof(pWC->a[0])*pWC->nSlot*2 );
    if( pWC->a==0 ){
      if( wtFlags & TERM_DYNAMIC ){
        sqlite3ExprDelete(db, p);
      }
      pWC->a = pOld;
      return 0;
    }
    memcpy(pWC->a, pOld, sizeof(pWC->a[0])*pWC->nTerm);
    if( pOld!=pWC->aStatic ){
      sqlite3DbFree(db, pOld);
    }
    pWC->nSlot *= 2;
  }
  pTerm = &pWC->a[idx = pWC->nTerm];
  pWC->nTerm++;
  pTerm->pExpr = p;
  pTerm->wtFlags = wtFlags;
  pTerm->pWC = pWC;
  pTerm->iParent = -1;
  return idx;
}

/*
** This routine identifies subexpressions in the WHERE clause where

static int operatorMask(int op){
  int c;
  assert( allowedOp(op) );
  if( op==TK_IN ){
    c = WO_IN;
  }else if( op==TK_ISNULL ){
    c = WO_ISNULL;
  }else if( op==TK_OR ){
    c = WO_OR;
  }else{
    c = WO_EQ<<(op-TK_EQ);
  }
  assert( op!=TK_ISNULL || c==WO_ISNULL );
  assert( op!=TK_OR || c==WO_OR );
  assert( op!=TK_IN || c==WO_IN );
  assert( op!=TK_EQ || c==WO_EQ );
  assert( op!=TK_LT || c==WO_LT );
  assert( op!=TK_LE || c==WO_LE );
  assert( op!=TK_GT || c==WO_GT );
  assert( op!=TK_GE || c==WO_GE );
  return c;

** this routine is called, we know that pOrTerm did not qualify.
** This routine merely checks to see if pOrTerm has a duplicate that
** might qualify.  If there is a duplicate that has not yet been
** disqualified, then return true.  If there are no duplicates, or
** the duplicate has also been disqualified, return false.
*/
static int orTermHasOkDuplicate(WhereClause *pOr, WhereTerm *pOrTerm){
  if( pOrTerm->wtFlags & TERM_COPIED ){
    /* This is the original term.  The duplicate is to the left had
    ** has not yet been analyzed and thus has not yet been disqualified. */
    return 1;
  }
  if( (pOrTerm->wtFlags & TERM_VIRTUAL)!=0
     && (pOr->a[pOrTerm->iParent].wtFlags & TERM_OR_OK)!=0 ){
    /* This is a duplicate term.  The original qualified so this one
    ** does not have to. */
    return 1;
  }
  /* This is either a singleton term or else it is a duplicate for
  ** which the original did not qualify.  Either way we are done for. */
  return 0;

        }
        idxNew = whereClauseInsert(pWC, pDup, TERM_VIRTUAL|TERM_DYNAMIC);
        if( idxNew==0 ) return;
        pNew = &pWC->a[idxNew];
        pNew->iParent = idxTerm;
        pTerm = &pWC->a[idxTerm];
        pTerm->nChild = 1;
        pTerm->wtFlags |= TERM_COPIED;
      }else{
        pDup = pExpr;
        pNew = pTerm;
      }
      exprCommute(pParse, pDup);
      pLeft = pDup->pLeft;
      pNew->leftCursor = pLeft->iTable;

  else if( pExpr->op==TK_OR ){
    int ok;
    int i, j;
    int iColumn, iCursor;
    WhereClause sOr;
    WhereTerm *pOrTerm;

    assert( (pTerm->wtFlags & TERM_DYNAMIC)==0 );
    whereClauseInit(&sOr, pWC->pParse, pMaskSet);
    whereSplit(&sOr, pExpr, TK_OR);
    exprAnalyzeAll(pSrc, &sOr);
    assert( sOr.nTerm>=2 );
    j = 0;
    if( db->mallocFailed ) goto or_not_possible;
    do{
      assert( j<sOr.nTerm );
      iColumn = sOr.a[j].leftColumn;
      iCursor = sOr.a[j].leftCursor;
      ok = iCursor>=0;
      for(i=sOr.nTerm-1, pOrTerm=sOr.a; i>=0 && ok; i--, pOrTerm++){
        if( pOrTerm->eOperator!=WO_EQ ){
          goto or_not_possible;
        }
        if( orTermIsOptCandidate(pOrTerm, iCursor, iColumn) ){
          pOrTerm->wtFlags |= TERM_OR_OK;
        }else if( orTermHasOkDuplicate(&sOr, pOrTerm) ){
          pOrTerm->wtFlags &= ~TERM_OR_OK;
        }else{
          ok = 0;
        }
      }
    }while( !ok && (sOr.a[j++].wtFlags & TERM_COPIED)!=0 && j<2 );
    if( ok ){
      ExprList *pList = 0;
      Expr *pNew, *pDup;
      Expr *pLeft = 0;
      for(i=sOr.nTerm-1, pOrTerm=sOr.a; i>=0; i--, pOrTerm++){
        if( (pOrTerm->wtFlags & TERM_OR_OK)==0 ) continue;
        pDup = sqlite3ExprDup(db, pOrTerm->pExpr->pRight);
        pList = sqlite3ExprListAppend(pWC->pParse, pList, pDup, 0);
        pLeft = pOrTerm->pExpr->pLeft;
      }
      assert( pLeft!=0 );
      pDup = sqlite3ExprDup(db, pLeft);
      pNew = sqlite3Expr(db, TK_IN, pDup, 0, 0);

      pNewTerm->prereqRight = prereqExpr;
      pNewTerm->leftCursor = pLeft->iTable;
      pNewTerm->leftColumn = pLeft->iColumn;
      pNewTerm->eOperator = WO_MATCH;
      pNewTerm->iParent = idxTerm;
      pTerm = &pWC->a[idxTerm];
      pTerm->nChild = 1;
      pTerm->wtFlags |= TERM_COPIED;
      pNewTerm->prereqAll = pTerm->prereqAll;
    }
  }
#endif /* SQLITE_OMIT_VIRTUALTABLE */

  /* Prevent ON clause terms of a LEFT JOIN from being used to drive
  ** an index for tables to the left of the join.

static double bestIndex(
  Parse *pParse,              /* The parsing context */
  WhereClause *pWC,           /* The WHERE clause */
  struct SrcList_item *pSrc,  /* The FROM clause term to search */
  Bitmask notReady,           /* Mask of cursors that are not available */
  ExprList *pOrderBy,         /* The order by clause */
  Index **ppIndex,            /* Make *ppIndex point to the best index */
  int *pWsFlags,              /* Put wsFlags describing scan strategy here */
  int *pnEq                   /* Put the number of == or IN constraints here */
){
  WhereTerm *pTerm;
  Index *bestIdx = 0;         /* Index that gives the lowest cost */
  double lowestCost;          /* The cost of using bestIdx */
  int bestWsFlags = 0;        /* Flags associated with bestIdx */
  int bestNEq = 0;            /* Best value for nEq */
  int iCur = pSrc->iCursor;   /* The cursor of the table to be accessed */
  Index *pProbe;              /* An index we are evaluating */
  int rev;                    /* True to scan in reverse order */
  int wsFlags;                /* Flags associated with pProbe */
  int nEq;                    /* Number of == or IN constraints */
  int eqTermMask;             /* Mask of valid equality operators */
  double cost;                /* Cost of using pProbe */

  WHERETRACE(("bestIndex: tbl=%s notReady=%llx\n", pSrc->pTab->zName,notReady));
  lowestCost = SQLITE_BIG_DBL;
  pProbe = pSrc->pTab->pIndex;
  if( pSrc->notIndexed ){
    pProbe = 0;
  }

  /* If the table has no indices and there are no terms in the where
  ** clause that refer to the ROWID, then we will never be able to do
  ** anything other than a full table scan on this table.  We might as
  ** well put it first in the join order.  That way, perhaps it can be
  ** referenced by other tables in the join.
  */
  if( pProbe==0 &&
     findTerm(pWC, iCur, -1, 0, WO_EQ|WO_IN|WO_LT|WO_LE|WO_GT|WO_GE,0)==0 &&
     (pOrderBy==0 || !sortableByRowid(iCur, pOrderBy, pWC->pMaskSet, &rev)) ){
    *pWsFlags = 0;
    *ppIndex = 0;
    *pnEq = 0;
    return 0.0;
  }

  /* Check for a rowid=EXPR or rowid IN (...) constraints. If there was
  ** an INDEXED BY clause attached to this table, skip this step.
  */
  if( !pSrc->pIndex ){
    pTerm = findTerm(pWC, iCur, -1, notReady, WO_EQ|WO_IN, 0);
    if( pTerm ){
      Expr *pExpr;
      *ppIndex = 0;
      bestWsFlags = WHERE_ROWID_EQ;
      if( pTerm->eOperator & WO_EQ ){
        /* Rowid== is always the best pick.  Look no further.  Because only
        ** a single row is generated, output is always in sorted order */
        *pWsFlags = WHERE_ROWID_EQ | WHERE_UNIQUE;
        *pnEq = 1;
        WHERETRACE(("... best is rowid\n"));
        return 0.0;
      }else if( (pExpr = pTerm->pExpr)->pList!=0 ){
        /* Rowid IN (LIST): cost is NlogN where N is the number of list
        ** elements.  */
        lowestCost = pExpr->pList->nExpr;

    }
  
    /* Estimate the cost of a table scan.  If we do not know how many
    ** entries are in the table, use 1 million as a guess.
    */
    cost = pProbe ? pProbe->aiRowEst[0] : 1000000;
    WHERETRACE(("... table scan base cost: %.9g\n", cost));
    wsFlags = WHERE_ROWID_RANGE;
  
    /* Check for constraints on a range of rowids in a table scan.
    */
    pTerm = findTerm(pWC, iCur, -1, notReady, WO_LT|WO_LE|WO_GT|WO_GE, 0);
    if( pTerm ){
      if( findTerm(pWC, iCur, -1, notReady, WO_LT|WO_LE, 0) ){
        wsFlags |= WHERE_TOP_LIMIT;
        cost /= 3;  /* Guess that rowid<EXPR eliminates two-thirds or rows */
      }
      if( findTerm(pWC, iCur, -1, notReady, WO_GT|WO_GE, 0) ){
        wsFlags |= WHERE_BTM_LIMIT;
        cost /= 3;  /* Guess that rowid>EXPR eliminates two-thirds of rows */
      }
      WHERETRACE(("... rowid range reduces cost to %.9g\n", cost));
    }else{
      wsFlags = 0;
    }
  
    /* If the table scan does not satisfy the ORDER BY clause, increase
    ** the cost by NlogN to cover the expense of sorting. */
    if( pOrderBy ){
      if( sortableByRowid(iCur, pOrderBy, pWC->pMaskSet, &rev) ){
        wsFlags |= WHERE_ORDERBY|WHERE_ROWID_RANGE;
        if( rev ){
          wsFlags |= WHERE_REVERSE;
        }
      }else{
        cost += cost*estLog(cost);
        WHERETRACE(("... sorting increases cost to %.9g\n", cost));
      }
    }
    if( cost<lowestCost ){
      lowestCost = cost;
      bestWsFlags = wsFlags;
    }
  }

  /* If the pSrc table is the right table of a LEFT JOIN then we may not
  ** use an index to satisfy IS NULL constraints on that table.  This is
  ** because columns might end up being NULL if the table does not match -
  ** a circumstance which the index cannot help us discover.  Ticket #2177.

    double inMultiplier = 1;

    WHERETRACE(("... index %s:\n", pProbe->zName));

    /* Count the number of columns in the index that are satisfied
    ** by x=EXPR constraints or x IN (...) constraints.
    */
    wsFlags = 0;
    for(i=0; i<pProbe->nColumn; i++){
      int j = pProbe->aiColumn[i];
      pTerm = findTerm(pWC, iCur, j, notReady, eqTermMask, pProbe);
      if( pTerm==0 ) break;
      wsFlags |= WHERE_COLUMN_EQ;
      if( pTerm->eOperator & WO_IN ){
        Expr *pExpr = pTerm->pExpr;
        wsFlags |= WHERE_COLUMN_IN;
        if( pExpr->pSelect!=0 ){
          inMultiplier *= 25;
        }else if( ALWAYS(pExpr->pList) ){
          inMultiplier *= pExpr->pList->nExpr + 1;
        }
      }
    }
    cost = pProbe->aiRowEst[i] * inMultiplier * estLog(inMultiplier);
    nEq = i;
    if( pProbe->onError!=OE_None && (wsFlags & WHERE_COLUMN_IN)==0
         && nEq==pProbe->nColumn ){
      wsFlags |= WHERE_UNIQUE;
    }
    WHERETRACE(("...... nEq=%d inMult=%.9g cost=%.9g\n",nEq,inMultiplier,cost));

    /* Look for range constraints
    */
    if( nEq<pProbe->nColumn ){
      int j = pProbe->aiColumn[nEq];
      pTerm = findTerm(pWC, iCur, j, notReady, WO_LT|WO_LE|WO_GT|WO_GE, pProbe);
      if( pTerm ){
        wsFlags |= WHERE_COLUMN_RANGE;
        if( findTerm(pWC, iCur, j, notReady, WO_LT|WO_LE, pProbe) ){
          wsFlags |= WHERE_TOP_LIMIT;
          cost /= 3;
        }
        if( findTerm(pWC, iCur, j, notReady, WO_GT|WO_GE, pProbe) ){
          wsFlags |= WHERE_BTM_LIMIT;
          cost /= 3;
        }
        WHERETRACE(("...... range reduces cost to %.9g\n", cost));
      }
    }

    /* Add the additional cost of sorting if that is a factor.
    */
    if( pOrderBy ){
      if( (wsFlags & WHERE_COLUMN_IN)==0 &&
           isSortingIndex(pParse,pWC->pMaskSet,pProbe,iCur,pOrderBy,nEq,&rev) ){
        if( wsFlags==0 ){
          wsFlags = WHERE_COLUMN_RANGE;
        }
        wsFlags |= WHERE_ORDERBY;
        if( rev ){
          wsFlags |= WHERE_REVERSE;
        }
      }else{
        cost += cost*estLog(cost);
        WHERETRACE(("...... orderby increases cost to %.9g\n", cost));
      }
    }

    /* Check to see if we can get away with using just the index without
    ** ever reading the table.  If that is the case, then halve the
    ** cost of this index.
    */
    if( wsFlags && pSrc->colUsed < (((Bitmask)1)<<(BMS-1)) ){
      Bitmask m = pSrc->colUsed;
      int j;
      for(j=0; j<pProbe->nColumn; j++){
        int x = pProbe->aiColumn[j];
        if( x<BMS-1 ){
          m &= ~(((Bitmask)1)<<x);
        }
      }
      if( m==0 ){
        wsFlags |= WHERE_IDX_ONLY;
        cost /= 2;
        WHERETRACE(("...... idx-only reduces cost to %.9g\n", cost));
      }
    }

    /* If this index has achieved the lowest cost so far, then use it.
    */
    if( wsFlags && cost < lowestCost ){
      bestIdx = pProbe;
      lowestCost = cost;
      bestWsFlags = wsFlags;
      bestNEq = nEq;
    }
  }

  /* Report the best result
  */
  *ppIndex = bestIdx;
  WHERETRACE(("best index is %s, cost=%.9g, wsFlags=%x, nEq=%d\n",
        bestIdx ? bestIdx->zName : "(none)", lowestCost, bestWsFlags, bestNEq));
  *pWsFlags = bestWsFlags | eqTermMask;
  *pnEq = bestNEq;
  return lowestCost;
}


/*
** Disable a term in the WHERE clause.  Except, do not disable the term

** loop.  We would get the correct results if nothing were ever disabled,
** but joins might run a little slower.  The trick is to disable as much
** as we can without disabling too much.  If we disabled in (1), we'd get
** the wrong answer.  See ticket #813.
*/
static void disableTerm(WhereLevel *pLevel, WhereTerm *pTerm){
  if( pTerm
      && ALWAYS((pTerm->wtFlags & TERM_CODED)==0)
      && (pLevel->iLeftJoin==0 || ExprHasProperty(pTerm->pExpr, EP_FromJoin))
  ){
    pTerm->wtFlags |= TERM_CODED;
    if( pTerm->iParent>=0 ){
      WhereTerm *pOther = &pTerm->pWC->a[pTerm->iParent];
      if( (--pOther->nChild)==0 ){
        disableTerm(pLevel, pOther);
      }
    }
  }

  /* Evaluate the equality constraints
  */
  assert( pIdx->nColumn>=nEq );
  for(j=0; j<nEq; j++){
    int r1;
    int k = pIdx->aiColumn[j];
    pTerm = findTerm(pWC, iCur, k, notReady, pLevel->wsFlags, pIdx);
    if( NEVER(pTerm==0) ) break;
    assert( (pTerm->wtFlags & TERM_CODED)==0 );
    r1 = codeEqualityTerm(pParse, pTerm, pLevel, regBase+j);
    if( r1!=regBase+j ){
      sqlite3VdbeAddOp2(v, OP_SCopy, r1, regBase+j);
    }
    testcase( pTerm->eOperator & WO_ISNULL );
    testcase( pTerm->eOperator & WO_IN );
    if( (pTerm->eOperator & (WO_ISNULL|WO_IN))==0 ){

** output order, then the *ppOrderBy is unchanged.
*/
WhereInfo *sqlite3WhereBegin(
  Parse *pParse,        /* The parser context */
  SrcList *pTabList,    /* A list of all tables to be scanned */
  Expr *pWhere,         /* The WHERE clause */
  ExprList **ppOrderBy, /* An ORDER BY clause, or NULL */
  u8 wctrlFlags         /* One of the WHERE_* flags defined in sqliteInt.h */
){
  int i;                     /* Loop counter */
  WhereInfo *pWInfo;         /* Will become the return value of this function */
  Vdbe *v = pParse->pVdbe;   /* The virtual database engine */
  int brk, cont = 0;         /* Addresses used during code generation */
  Bitmask notReady;          /* Cursors that are not yet positioned */
  WhereTerm *pTerm;          /* A single term in the WHERE clause */
  ExprMaskSet maskSet;       /* The expression mask set */
  WhereClause wc;            /* The WHERE clause is divided into these terms */
  struct SrcList_item *pTabItem;  /* A single entry from pTabList */
  WhereLevel *pLevel;             /* A single level in the pWInfo list */
  int iFrom;                      /* First unused FROM clause element */
  int andFlags;              /* AND-ed combination of all wc.a[].wtFlags */
  sqlite3 *db;               /* Database connection */
  ExprList *pOrderBy = 0;

  /* The number of tables in the FROM clause is limited by the number of
  ** bits in a Bitmask 
  */
  if( pTabList->nSrc>BMS ){

  }

  /* 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
  **   pWInfo->a[].nEq       The number of == and IN constraints
  **   pWInfo->a[].iFrom     Which term of the FROM clause is being coded
  **   pWInfo->a[].iTabCur   The VDBE cursor for the database table
  **   pWInfo->a[].iIdxCur   The VDBE cursor for the index
  **
  ** This loop also figures out the nesting order of tables in the FROM
  ** clause.
  */
  notReady = ~(Bitmask)0;
  pTabItem = pTabList->a;
  pLevel = pWInfo->a;
  andFlags = ~0;
  WHERETRACE(("*** Optimizer Start ***\n"));
  for(i=iFrom=0, pLevel=pWInfo->a; i<pTabList->nSrc; i++, pLevel++){
    Index *pIdx;                /* Index for FROM table at pTabItem */
    int wsFlags;                /* Flags describing scan strategy */
    int nEq;                    /* Number of == or IN constraints */
    double cost;                /* The cost for pIdx */
    int j;                      /* For looping over FROM tables */
    Index *pBest = 0;           /* The best index seen so far */
    int bestWsFlags = 0;        /* Flags associated with pBest */
    int bestNEq = 0;            /* nEq associated with pBest */
    double lowestCost;          /* Cost of the pBest */
    int bestJ = 0;              /* The value of j */
    Bitmask m;                  /* Bitmask value for j or bestJ */
    int once = 0;               /* True when first table is seen */
    sqlite3_index_info *pIndex; /* Current virtual index */

      assert( pTabItem->pTab );
#ifndef SQLITE_OMIT_VIRTUALTABLE
      if( IsVirtual(pTabItem->pTab) ){
        sqlite3_index_info **ppIdxInfo = &pWInfo->a[j].pIdxInfo;
        cost = bestVirtualIndex(pParse, &wc, pTabItem, notReady,
                                ppOrderBy ? *ppOrderBy : 0, i==0,
                                ppIdxInfo);
        wsFlags = WHERE_VIRTUALTABLE;
        pIndex = *ppIdxInfo;
        if( pIndex && pIndex->orderByConsumed ){
          wsFlags = WHERE_VIRTUALTABLE | WHERE_ORDERBY;
        }
        pIdx = 0;
        nEq = 0;
        if( (SQLITE_BIG_DBL/2.0)<cost ){
          /* The cost is not allowed to be larger than SQLITE_BIG_DBL (the
          ** inital value of lowestCost in this loop. If it is, then
          ** the (cost<lowestCost) test below will never be true and
          ** pLevel->pBestIdx never set.
          */ 
          cost = (SQLITE_BIG_DBL/2.0);
        }
      }else 
#endif
      {
        cost = bestIndex(pParse, &wc, pTabItem, notReady,
                         (i==0 && ppOrderBy) ? *ppOrderBy : 0,
                         &pIdx, &wsFlags, &nEq);
        pIndex = 0;
      }
      if( cost<lowestCost ){
        once = 1;
        lowestCost = cost;
        pBest = pIdx;
        bestWsFlags = wsFlags;
        bestNEq = nEq;
        bestJ = j;
        pLevel->pBestIdx = pIndex;
      }
      if( doNotReorder ) break;
    }
    WHERETRACE(("*** Optimizer selects table %d for loop %d\n", bestJ,
           pLevel-pWInfo->a));
    if( (bestWsFlags & WHERE_ORDERBY)!=0 ){
      *ppOrderBy = 0;
    }
    andFlags &= bestWsFlags;
    pLevel->wsFlags = bestWsFlags;
    pLevel->pIdx = pBest;
    pLevel->nEq = bestNEq;
    pLevel->aInLoop = 0;
    pLevel->nIn = 0;
    if( pBest ){
      pLevel->iIdxCur = pParse->nTab++;
    }else{

  }

  /* If the caller is an UPDATE or DELETE statement that is requesting
  ** to use a one-pass algorithm, determine if this is appropriate.
  ** The one-pass algorithm only works if the WHERE clause constraints
  ** the statement to update a single row.
  */
  assert( (wctrlFlags & WHERE_ONEPASS_DESIRED)==0 || pWInfo->nLevel==1 );
  if( (wctrlFlags & WHERE_ONEPASS_DESIRED)!=0 && (andFlags & WHERE_UNIQUE)!=0 ){
    pWInfo->okOnePass = 1;
    pWInfo->a[0].wsFlags &= ~WHERE_IDX_ONLY;
  }

  /* Open all tables in the pTabList and any indices selected for
  ** searching those tables.
  */
  sqlite3CodeVerifySchema(pParse, -1); /* Insert the cookie verifier Goto */
  for(i=0, pLevel=pWInfo->a; i<pTabList->nSrc; i++, pLevel++){

      struct SrcList_item *pItem = &pTabList->a[pLevel->iFrom];
      zMsg = sqlite3MPrintf(db, "TABLE %s", pItem->zName);
      if( pItem->zAlias ){
        zMsg = sqlite3MAppendf(db, zMsg, "%s AS %s", zMsg, pItem->zAlias);
      }
      if( (pIx = pLevel->pIdx)!=0 ){
        zMsg = sqlite3MAppendf(db, zMsg, "%s WITH INDEX %s", zMsg, pIx->zName);
      }else if( pLevel->wsFlags & (WHERE_ROWID_EQ|WHERE_ROWID_RANGE) ){
        zMsg = sqlite3MAppendf(db, zMsg, "%s USING PRIMARY KEY", zMsg);
      }
#ifndef SQLITE_OMIT_VIRTUALTABLE
      else if( pLevel->pBestIdx ){
        sqlite3_index_info *pBestIdx = pLevel->pBestIdx;
        zMsg = sqlite3MAppendf(db, zMsg, "%s VIRTUAL TABLE INDEX %d:%s", zMsg,
                    pBestIdx->idxNum, pBestIdx->idxStr);
      }
#endif
      if( pLevel->wsFlags & WHERE_ORDERBY ){
        zMsg = sqlite3MAppendf(db, zMsg, "%s ORDER BY", zMsg);
      }
      sqlite3VdbeAddOp4(v, OP_Explain, i, pLevel->iFrom, 0, zMsg, P4_DYNAMIC);
    }
#endif /* SQLITE_OMIT_EXPLAIN */
    pTabItem = &pTabList->a[pLevel->iFrom];
    pTab = pTabItem->pTab;
    iDb = sqlite3SchemaToIndex(pParse->db, pTab->pSchema);
    if( (pTab->tabFlags & TF_Ephemeral)!=0 || pTab->pSelect ) continue;
#ifndef SQLITE_OMIT_VIRTUALTABLE
    if( pLevel->pBestIdx ){
      int iCur = pTabItem->iCursor;
      sqlite3VdbeAddOp4(v, OP_VOpen, iCur, 0, 0,
                        (const char*)pTab->pVtab, P4_VTAB);
    }else
#endif
    if( (pLevel->wsFlags & WHERE_IDX_ONLY)==0 ){
      int op = pWInfo->okOnePass ? OP_OpenWrite : OP_OpenRead;
      sqlite3OpenTable(pParse, pTabItem->iCursor, iDb, pTab, op);
      if( !pWInfo->okOnePass && pTab->nCol<BMS ){
        Bitmask b = pTabItem->colUsed;
        int n = 0;
        for(; b; b=b>>1, n++){}
        sqlite3VdbeChangeP2(v, sqlite3VdbeCurrentAddr(v)-2, n);

    int omitTable;     /* True if we use the index only */
    int bRev;          /* True if we need to scan in reverse order */

    pTabItem = &pTabList->a[pLevel->iFrom];
    iCur = pTabItem->iCursor;
    pIdx = pLevel->pIdx;
    iIdxCur = pLevel->iIdxCur;
    bRev = (pLevel->wsFlags & WHERE_REVERSE)!=0;
    omitTable = (pLevel->wsFlags & WHERE_IDX_ONLY)!=0;

    /* Create labels for the "break" and "continue" instructions
    ** for the current loop.  Jump to brk to break out of a loop.
    ** Jump to cont to go immediately to the next iteration of the
    ** loop.
    **
    ** When there is an IN operator, we also have a "nxt" label that

      }
      pLevel->op = OP_VNext;
      pLevel->p1 = iCur;
      pLevel->p2 = sqlite3VdbeCurrentAddr(v);
    }else
#endif /* SQLITE_OMIT_VIRTUALTABLE */

    if( pLevel->wsFlags & WHERE_ROWID_EQ ){
      /* Case 1:  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.
      */
      int r1;
      int rtmp = sqlite3GetTempReg(pParse);
      pTerm = findTerm(&wc, iCur, -1, notReady, WO_EQ|WO_IN, 0);
      assert( pTerm!=0 );
      assert( pTerm->pExpr!=0 );
      assert( pTerm->leftCursor==iCur );
      assert( omitTable==0 );
      r1 = codeEqualityTerm(pParse, pTerm, pLevel, rtmp);
      nxt = pLevel->nxt;
      sqlite3VdbeAddOp2(v, OP_MustBeInt, r1, nxt);
      sqlite3VdbeAddOp3(v, OP_NotExists, iCur, nxt, r1);
      sqlite3ReleaseTempReg(pParse, rtmp);
      VdbeComment((v, "pk"));
      pLevel->op = OP_Noop;
    }else if( pLevel->wsFlags & WHERE_ROWID_RANGE ){
      /* Case 2:  We have an inequality comparison against the ROWID field.
      */
      int testOp = OP_Noop;
      int start;
      WhereTerm *pStart, *pEnd;

      assert( omitTable==0 );

        int r1 = sqlite3GetTempReg(pParse);
        sqlite3VdbeAddOp2(v, OP_Rowid, iCur, r1);
        /* sqlite3VdbeAddOp2(v, OP_SCopy, pLevel->iMem, 0); */
        sqlite3VdbeAddOp3(v, testOp, pLevel->iMem, brk, r1);
        sqlite3VdbeChangeP5(v, SQLITE_AFF_NUMERIC | SQLITE_JUMPIFNULL);
        sqlite3ReleaseTempReg(pParse, r1);
      }
    }else if( pLevel->wsFlags & (WHERE_COLUMN_RANGE|WHERE_COLUMN_EQ) ){
      /* Case 3: A scan using an index.
      **
      **         The WHERE clause may contain zero or more equality 
      **         terms ("==" or "IN" operators) that refer to the N
      **         left-most columns of the index. It may also contain
      **         inequality constraints (>, <, >= or <=) on the indexed
      **         column that immediately follows the N equalities. Only 

      ** was passed to this function to implement a "SELECT min(x) ..." 
      ** query, then the caller will only allow the loop to run for
      ** a single iteration. This means that the first row returned
      ** should not have a NULL value stored in 'x'. If column 'x' is
      ** the first one after the nEq equality constraints in the index,
      ** this requires some special handling.
      */
      if( (wctrlFlags&WHERE_ORDERBY_MIN)!=0
       && (pLevel->wsFlags&WHERE_ORDERBY)
       && (pIdx->nColumn>nEq)
      ){
        assert( pOrderBy->nExpr==1 );
        assert( pOrderBy->a[0].pExpr->iColumn==pIdx->aiColumn[nEq] );
        isMinQuery = 1;
      }

      /* Find any inequality constraint terms for the start and end 
      ** of the range. 
      */
      if( pLevel->wsFlags & WHERE_TOP_LIMIT ){
        pRangeEnd = findTerm(&wc, iCur, k, notReady, (WO_LT|WO_LE), pIdx);
      }
      if( pLevel->wsFlags & WHERE_BTM_LIMIT ){
        pRangeStart = findTerm(&wc, iCur, k, notReady, (WO_GT|WO_GE), pIdx);
      }

      /* If we are doing a reverse order scan on an ascending index, or
      ** a forward order scan on a descending index, interchange the 
      ** start and end terms (pRangeStart and pRangeEnd).
      */

      sqlite3VdbeChangeP5(v, endEq!=bRev);

      /* If there are inequality constraints, check that the value
      ** of the table column that the inequality contrains is not NULL.
      ** If it is, jump to the next iteration of the loop.
      */
      r1 = sqlite3GetTempReg(pParse);
      testcase( pLevel->wsFlags & WHERE_BTM_LIMIT );
      testcase( pLevel->wsFlags & WHERE_TOP_LIMIT );
      if( pLevel->wsFlags & (WHERE_BTM_LIMIT|WHERE_TOP_LIMIT) ){
        sqlite3VdbeAddOp3(v, OP_Column, iIdxCur, nEq, r1);
        sqlite3VdbeAddOp2(v, OP_IsNull, r1, cont);
      }

      /* Seek the table cursor, if required */
      if( !omitTable ){
        sqlite3VdbeAddOp2(v, OP_IdxRowid, iIdxCur, r1);

    /* Insert code to test every subexpression that can be completely
    ** computed using the current set of tables.
    */
    k = 0;
    for(pTerm=wc.a, j=wc.nTerm; j>0; j--, pTerm++){
      Expr *pE;
      testcase( pTerm->wtFlags & TERM_VIRTUAL );
      testcase( pTerm->wtFlags & TERM_CODED );
      if( pTerm->wtFlags & (TERM_VIRTUAL|TERM_CODED) ) continue;
      if( (pTerm->prereqAll & notReady)!=0 ) continue;
      pE = pTerm->pExpr;
      assert( pE!=0 );
      if( pLevel->iLeftJoin && !ExprHasProperty(pE, EP_FromJoin) ){
        continue;
      }
      pParse->disableColCache += k;
      sqlite3ExprIfFalse(pParse, pE, cont, SQLITE_JUMPIFNULL);
      pParse->disableColCache -= k;
      k = 1;
      pTerm->wtFlags |= TERM_CODED;
    }

    /* For a LEFT OUTER JOIN, generate code that will record the fact that
    ** at least one row of the right table has matched the left table.  
    */
    if( pLevel->iLeftJoin ){
      pLevel->top = sqlite3VdbeCurrentAddr(v);
      sqlite3VdbeAddOp2(v, OP_Integer, 1, pLevel->iLeftJoin);
      VdbeComment((v, "record LEFT JOIN hit"));
      sqlite3ExprClearColumnCache(pParse, pLevel->iTabCur);
      sqlite3ExprClearColumnCache(pParse, pLevel->iIdxCur);
      for(pTerm=wc.a, j=0; j<wc.nTerm; j++, pTerm++){
        testcase( pTerm->wtFlags & TERM_VIRTUAL );
        testcase( pTerm->wtFlags & TERM_CODED );
        if( pTerm->wtFlags & (TERM_VIRTUAL|TERM_CODED) ) continue;
        if( (pTerm->prereqAll & notReady)!=0 ) continue;
        assert( pTerm->pExpr );
        sqlite3ExprIfFalse(pParse, pTerm->pExpr, cont, SQLITE_JUMPIFNULL);
        pTerm->wtFlags |= TERM_CODED;
      }
    }
  }

#ifdef SQLITE_TEST  /* For testing and debugging use only */
  /* Record in the query plan information about the current table
  ** and the index used to access it (if any).  If the table itself
  ** is not used, its name is just '{}'.  If no index is used
  ** the index is listed as "{}".  If the primary key is used the
  ** index name is '*'.
  */
  for(i=0; i<pTabList->nSrc; i++){
    char *z;
    int n;
    pLevel = &pWInfo->a[i];
    pTabItem = &pTabList->a[pLevel->iFrom];
    z = pTabItem->zAlias;
    if( z==0 ) z = pTabItem->pTab->zName;
    n = strlen(z);
    if( n+nQPlan < sizeof(sqlite3_query_plan)-10 ){
      if( pLevel->wsFlags & WHERE_IDX_ONLY ){
        memcpy(&sqlite3_query_plan[nQPlan], "{}", 2);
        nQPlan += 2;
      }else{
        memcpy(&sqlite3_query_plan[nQPlan], z, n);
        nQPlan += n;
      }
      sqlite3_query_plan[nQPlan++] = ' ';
    }
    testcase( pLevel->wsFlags & WHERE_ROWID_EQ );
    testcase( pLevel->wsFlags & WHERE_ROWID_RANGE );
    if( pLevel->wsFlags & (WHERE_ROWID_EQ|WHERE_ROWID_RANGE) ){
      memcpy(&sqlite3_query_plan[nQPlan], "* ", 2);
      nQPlan += 2;
    }else if( pLevel->pIdx==0 ){
      memcpy(&sqlite3_query_plan[nQPlan], "{} ", 3);
      nQPlan += 3;
    }else{
      n = strlen(pLevel->pIdx->zName);

  /* Close all of the cursors that were opened by sqlite3WhereBegin.
  */
  for(i=0, pLevel=pWInfo->a; i<pTabList->nSrc; i++, pLevel++){
    struct SrcList_item *pTabItem = &pTabList->a[pLevel->iFrom];
    Table *pTab = pTabItem->pTab;
    assert( pTab!=0 );
    if( (pTab->tabFlags & TF_Ephemeral)!=0 || pTab->pSelect ) continue;
    if( !pWInfo->okOnePass && (pLevel->wsFlags & WHERE_IDX_ONLY)==0 ){
      sqlite3VdbeAddOp1(v, OP_Close, pTabItem->iCursor);
    }
    if( pLevel->pIdx!=0 ){
      sqlite3VdbeAddOp1(v, OP_Close, pLevel->iIdxCur);
    }

    /* If this scan uses an index, make code substitutions to read data

    ** that reference the table and converts them into opcodes that
    ** reference the index.
    */
    if( pLevel->pIdx ){
      int k, j, last;
      VdbeOp *pOp;
      Index *pIdx = pLevel->pIdx;
      int useIndexOnly = pLevel->wsFlags & WHERE_IDX_ONLY;

      assert( pIdx!=0 );
      pOp = sqlite3VdbeGetOp(v, pWInfo->iTop);
      last = sqlite3VdbeCurrentAddr(v);
      for(k=pWInfo->iTop; k<last; k++, pOp++){
        if( pOp->p1!=pLevel->iTabCur ) continue;
        if( pOp->opcode==OP_Column ){