/ Check-in [778e91dd]
Login

Many hyperlinks are disabled.
Use anonymous login to enable hyperlinks.

Overview
Comment:Continue refactoring where.c in preparation for installing OR-clause optimizations. (CVS 6050)
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1: 778e91ddb834f6084ecdf3909692b54bb7da8f6d
User & Date: drh 2008-12-21 03:51:16
Context
2008-12-22
03:37
Fix a variable type to prevent a warning in the proxy-locking code. (CVS 6051) check-in: d9595b96 user: danielk1977 tags: trunk
2008-12-21
03:51
Continue refactoring where.c in preparation for installing OR-clause optimizations. (CVS 6050) check-in: 778e91dd user: drh tags: trunk
2008-12-20
18:33
Add a vfs backend that detects problems like the one addressed by (6043) and (6047). (CVS 6049) check-in: 49172e48 user: danielk1977 tags: trunk
Changes
Hide Diffs Side-by-Side Diffs Ignore Whitespace Patch

Changes to src/sqliteInt.h.

     7      7   **    May you do good and not evil.
     8      8   **    May you find forgiveness for yourself and forgive others.
     9      9   **    May you share freely, never taking more than you give.
    10     10   **
    11     11   *************************************************************************
    12     12   ** Internal interface definitions for SQLite.
    13     13   **
    14         -** @(#) $Id: sqliteInt.h,v 1.812 2008/12/20 02:14:40 drh Exp $
           14  +** @(#) $Id: sqliteInt.h,v 1.813 2008/12/21 03:51:16 drh Exp $
    15     15   */
    16     16   #ifndef _SQLITEINT_H_
    17     17   #define _SQLITEINT_H_
    18     18   
    19     19   /*
    20     20   ** Include the configuration header output by 'configure' if we're using the
    21     21   ** autoconf-based build
................................................................................
   530    530   typedef struct TableLock TableLock;
   531    531   typedef struct Token Token;
   532    532   typedef struct TriggerStack TriggerStack;
   533    533   typedef struct TriggerStep TriggerStep;
   534    534   typedef struct Trigger Trigger;
   535    535   typedef struct UnpackedRecord UnpackedRecord;
   536    536   typedef struct Walker Walker;
          537  +typedef struct WherePlan WherePlan;
   537    538   typedef struct WhereInfo WhereInfo;
   538    539   typedef struct WhereLevel WhereLevel;
   539    540   
   540    541   /*
   541    542   ** Defer sourcing vdbe.h and btree.h until after the "u8" and 
   542    543   ** "BusyHandler" typedefs. vdbe.h also requires a few of the opaque
   543    544   ** pointer types (i.e. FuncDef) defined above.
................................................................................
  1515   1516   #define JT_CROSS     0x0002    /* Explicit use of the CROSS keyword */
  1516   1517   #define JT_NATURAL   0x0004    /* True for a "natural" join */
  1517   1518   #define JT_LEFT      0x0008    /* Left outer join */
  1518   1519   #define JT_RIGHT     0x0010    /* Right outer join */
  1519   1520   #define JT_OUTER     0x0020    /* The "OUTER" keyword is present */
  1520   1521   #define JT_ERROR     0x0040    /* unknown or unsupported join type */
  1521   1522   
         1523  +
         1524  +/*
         1525  +** A WherePlan object holds information that describes a lookup
         1526  +** strategy.
         1527  +**
         1528  +** This object is intended to be opaque outside of the where.c module.
         1529  +** It is included here only so that that compiler will know how big it
         1530  +** is.  None of the fields in this object should be used outside of
         1531  +** the where.c module.
         1532  +**
         1533  +** Within the union, pIdx is only used when wsFlags&WHERE_INDEXED is true.
         1534  +** pTerm is only used when wsFlags&WHERE_MULTI_OR is true.  And pVtabIdx
         1535  +** is only used when wsFlags&WHERE_VIRTUALTABLE is true.  It is never the
         1536  +** case that more than one of these conditions is true.
         1537  +*/
         1538  +struct WherePlan {
         1539  +  u32 wsFlags;                   /* WHERE_* flags that describe the strategy */
         1540  +  u32 nEq;                       /* Number of == constraints */
         1541  +  union {
         1542  +    Index *pIdx;                   /* Index when WHERE_INDEXED is true */
         1543  +    struct WhereTerm *pTerm;       /* WHERE clause term for OR-search */
         1544  +    sqlite3_index_info *pVtabIdx;  /* Virtual table index to use */
         1545  +  } u;
         1546  +};
         1547  +
  1522   1548   /*
  1523   1549   ** For each nested loop in a WHERE clause implementation, the WhereInfo
  1524   1550   ** structure contains a single instance of this structure.  This structure
  1525   1551   ** is intended to be private the the where.c module and should not be
  1526   1552   ** access or modified by other modules.
  1527   1553   **
  1528         -** The pIdxInfo and pBestIdx fields are used to help pick the best
  1529         -** index on a virtual table.  The pIdxInfo pointer contains indexing
         1554  +** The pIdxInfo field is used to help pick the best index on a
         1555  +** virtual table.  The pIdxInfo pointer contains indexing
  1530   1556   ** information for the i-th table in the FROM clause before reordering.
  1531   1557   ** All the pIdxInfo pointers are freed by whereInfoFree() in where.c.
  1532         -** The pBestIdx pointer is a copy of pIdxInfo for the i-th table after
  1533         -** FROM clause ordering.  This is a little confusing so I will repeat
  1534         -** it in different words.  WhereInfo.a[i].pIdxInfo is index information 
  1535         -** for WhereInfo.pTabList.a[i].  WhereInfo.a[i].pBestInfo is the
  1536         -** index information for the i-th loop of the join.  pBestInfo is always
  1537         -** either NULL or a copy of some pIdxInfo.  So for cleanup it is 
  1538         -** sufficient to free all of the pIdxInfo pointers.
  1539         -** 
         1558  +** All other information in the i-th WhereLevel object for the i-th table
         1559  +** after FROM clause ordering.
  1540   1560   */
  1541   1561   struct WhereLevel {
  1542         -  u32 wsFlags;          /* "Where-Scan" flags show the choosen scan strategy */
         1562  +  WherePlan plan;       /* query plan for this element of the FROM clause */
  1543   1563     int iLeftJoin;        /* Memory cell used to implement LEFT OUTER JOIN */
  1544         -  Index *pIdx;          /* Index used.  NULL if no index */
  1545         -  struct WhereTerm *pTerm; /* Where term containing OR clause */
  1546   1564     int iTabCur;          /* The VDBE cursor used to access the table */
  1547   1565     int iIdxCur;          /* The VDBE cursor used to access pIdx */
  1548   1566     int addrBrk;          /* Jump here to break out of the loop */
  1549   1567     int addrNxt;          /* Jump here to start the next IN combination */
  1550   1568     int addrCont;         /* Jump here to continue with the next loop cycle */
  1551   1569     int addrFirst;        /* First instruction of interior of the loop */
  1552         -  int op, p1, p2;       /* Opcode used to terminate the loop */
  1553         -  u8 p5;                /* P5 operand of the opcode that terminates the loop */
  1554   1570     u8 iFrom;             /* Which entry in the FROM clause */
  1555         -  u16 nEq;              /* Number of == or IN constraints on this loop */
  1556         -  u16 nIn;              /* Number of IN operators constraining this loop */
  1557         -  struct InLoop {
  1558         -    int iCur;              /* The VDBE cursor used by this IN operator */
  1559         -    int addrInTop;         /* Top of the IN loop */
  1560         -  } *aInLoop;           /* Information about each nested IN operator */
  1561         -  sqlite3_index_info *pBestIdx;  /* Index information for this level */
         1571  +  u8 op, p5;            /* Opcode and P5 of the opcode that ends the loop */
         1572  +  int p1, p2;           /* Operands of the opcode used to ends the loop */
         1573  +  union {               /* Information that depends on plan.wsFlags */
         1574  +    struct {
         1575  +      int nIn;              /* Number of entries in aInLoop[] */
         1576  +      struct InLoop {
         1577  +        int iCur;              /* The VDBE cursor used by this IN operator */
         1578  +        int addrInTop;         /* Top of the IN loop */
         1579  +      } *aInLoop;           /* Information about each nested IN operator */
         1580  +    } in;                 /* Used when plan.wsFlags&WHERE_IN_ABLE */
         1581  +    struct {
         1582  +      WherePlan *aPlan;     /* Plans for each term of the WHERE clause */
         1583  +    } or;                 /* Used when plan.wsFlags&WHERE_MULTI_OR */
         1584  +  } u;
  1562   1585   
  1563   1586     /* The following field is really not part of the current level.  But
  1564         -  ** we need a place to cache index information for each table in the
  1565         -  ** FROM clause and the WhereLevel structure is a convenient place.
         1587  +  ** we need a place to cache virtual table index information for each
         1588  +  ** virtual table in the FROM clause and the WhereLevel structure is
         1589  +  ** a convenient place since there is one WhereLevel for each FROM clause
         1590  +  ** element.
  1566   1591     */
  1567   1592     sqlite3_index_info *pIdxInfo;  /* Index info for n-th source table */
  1568   1593   };
  1569   1594   
  1570   1595   /*
  1571   1596   ** Flags appropriate for the wctrlFlags parameter of sqlite3WhereBegin().
  1572   1597   */
................................................................................
  1581   1606   ** half does the tail of the WHERE loop.  An instance of
  1582   1607   ** this structure is returned by the first half and passed
  1583   1608   ** into the second half to give some continuity.
  1584   1609   */
  1585   1610   struct WhereInfo {
  1586   1611     Parse *pParse;       /* Parsing and code generating context */
  1587   1612     u8 okOnePass;        /* Ok to use one-pass algorithm for UPDATE or DELETE */
  1588         -  SrcList *pTabList;   /* List of tables in the join */
  1589         -  int iTop;            /* The very beginning of the WHERE loop */
  1590         -  int iContinue;       /* Jump here to continue with next record */
  1591         -  int iBreak;          /* Jump here to break out of the loop */
  1592         -  int nLevel;          /* Number of nested loop */
  1593         -  sqlite3_index_info **apInfo;  /* Array of pointers to index info structures */
  1594         -  WhereLevel a[1];     /* Information about each nest loop in the WHERE */
         1613  +  SrcList *pTabList;             /* List of tables in the join */
         1614  +  int iTop;                      /* The very beginning of the WHERE loop */
         1615  +  int iContinue;                 /* Jump here to continue with next record */
         1616  +  int iBreak;                    /* Jump here to break out of the loop */
         1617  +  int nLevel;                    /* Number of nested loop */
         1618  +  struct WhereClause *pWC;       /* Decomposition of the WHERE clause */
         1619  +  sqlite3_index_info **apInfo;   /* Array of pointers to index info objects */
         1620  +  WhereLevel a[1];               /* Information about each nest loop in WHERE */
  1595   1621   };
  1596   1622   
  1597   1623   /*
  1598   1624   ** A NameContext defines a context in which to resolve table and column
  1599   1625   ** names.  The context consists of a list of tables (the pSrcList) field and
  1600   1626   ** a list of named expression (pEList).  The named expression list may
  1601   1627   ** be NULL.  The pSrc corresponds to the FROM clause of a SELECT or

Changes to src/where.c.

    12     12   ** This module contains C code that generates VDBE code used to process
    13     13   ** the WHERE clause of SQL statements.  This module is responsible for
    14     14   ** generating the code that loops through a table looking for applicable
    15     15   ** rows.  Indices are selected and used to speed the search when doing
    16     16   ** so is applicable.  Because this module is responsible for selecting
    17     17   ** indices, you might also think of this module as the "query optimizer".
    18     18   **
    19         -** $Id: where.c,v 1.339 2008/12/20 02:06:14 drh Exp $
           19  +** $Id: where.c,v 1.340 2008/12/21 03:51:16 drh Exp $
    20     20   */
    21     21   #include "sqliteInt.h"
    22     22   
    23     23   /*
    24     24   ** Trace output macros
    25     25   */
    26     26   #if defined(SQLITE_TEST) || defined(SQLITE_DEBUG)
    27     27   int sqlite3WhereTrace = 0;
    28     28   #endif
    29         -#if 0
           29  +#if 1
    30     30   # define WHERETRACE(X)  if(sqlite3WhereTrace) sqlite3DebugPrintf X
    31     31   #else
    32     32   # define WHERETRACE(X)
    33     33   #endif
    34     34   
    35     35   /* Forward reference
    36     36   */
    37     37   typedef struct WhereClause WhereClause;
    38         -typedef struct ExprMaskSet ExprMaskSet;
           38  +typedef struct WhereMaskSet WhereMaskSet;
    39     39   typedef struct WhereOrInfo WhereOrInfo;
    40     40   typedef struct WhereAndInfo WhereAndInfo;
           41  +typedef struct WhereCost WhereCost;
    41     42   
    42     43   /*
    43     44   ** The query generator uses an array of instances of this structure to
    44     45   ** help it analyze the subexpressions of the WHERE clause.  Each WHERE
    45     46   ** clause subexpression is separated from the others by AND operators.
    46     47   ** (Note: the same data structure is also reused to hold a group of terms
    47     48   ** separated by OR operators.  But at the top-level, everything is AND
................................................................................
    73     74   **
    74     75   ** If a term in the WHERE clause does not match either of the two previous
    75     76   ** categories, then eOperator==0.  The WhereTerm.pExpr field is still set
    76     77   ** to the original subexpression content and wtFlags is set up appropriately
    77     78   ** but no other fields in the WhereTerm object are meaningful.
    78     79   **
    79     80   ** When eOperator!=0, prereqRight and prereqAll record sets of cursor numbers,
    80         -** but they do so indirectly.  A single ExprMaskSet structure translates
           81  +** but they do so indirectly.  A single WhereMaskSet structure translates
    81     82   ** cursor number into bits and the translated bit is stored in the prereq
    82     83   ** fields.  The translation is used in order to maximize the number of
    83     84   ** bits that will fit in a Bitmask.  The VDBE cursor numbers might be
    84     85   ** spread out over the non-negative integers.  For example, the cursor
    85         -** numbers might be 3, 8, 9, 10, 20, 23, 41, and 45.  The ExprMaskSet
           86  +** numbers might be 3, 8, 9, 10, 20, 23, 41, and 45.  The WhereMaskSet
    86     87   ** translates these sparse cursor numbers into consecutive integers
    87     88   ** beginning with 0 in order to make the best possible use of the available
    88     89   ** bits in the Bitmask.  So, in the example above, the cursor numbers
    89     90   ** would be mapped into integers 0 through 7.
    90     91   **
    91     92   ** The number of terms in a join is limited by the number of bits
    92     93   ** in prereqRight and prereqAll.  The default is 64 bits, hence SQLite
................................................................................
   123    124   
   124    125   /*
   125    126   ** An instance of the following structure holds all information about a
   126    127   ** WHERE clause.  Mostly this is a container for one or more WhereTerms.
   127    128   */
   128    129   struct WhereClause {
   129    130     Parse *pParse;           /* The parser context */
   130         -  ExprMaskSet *pMaskSet;   /* Mapping of table indices to bitmasks */
          131  +  WhereMaskSet *pMaskSet;  /* Mapping of table cursor numbers to bitmasks */
   131    132     int nTerm;               /* Number of terms */
   132    133     int nSlot;               /* Number of entries in a[] */
   133    134     WhereTerm *a;            /* Each a[] describes a term of the WHERE cluase */
   134    135     WhereTerm aStatic[4];    /* Initial static space for a[] */
   135    136   };
   136    137   
   137    138   /*
   138    139   ** A WhereTerm with eOperator==WO_OR has its u.pOrInfo pointer set to
   139    140   ** a dynamically allocated instance of the following structure.
   140    141   */
   141    142   struct WhereOrInfo {
   142         -  WhereClause wc;          /* The OR subexpression broken out */
          143  +  WhereClause wc;          /* Decomposition into subterms */
   143    144     Bitmask indexable;       /* Bitmask of all indexable tables in the clause */
          145  +  WherePlan *aPlan;        /* Search plan for each subterm */
   144    146   };
   145    147   
   146    148   /*
   147    149   ** A WhereTerm with eOperator==WO_AND has its u.pAndInfo pointer set to
   148    150   ** a dynamically allocated instance of the following structure.
   149    151   */
   150    152   struct WhereAndInfo {
................................................................................
   161    163   ** SrcList_item.iCursor and Expr.iTable fields.  For any given WHERE 
   162    164   ** clause, the cursor numbers might not begin with 0 and they might
   163    165   ** contain gaps in the numbering sequence.  But we want to make maximum
   164    166   ** use of the bits in our bitmasks.  This structure provides a mapping
   165    167   ** from the sparse cursor numbers into consecutive integers beginning
   166    168   ** with 0.
   167    169   **
   168         -** If ExprMaskSet.ix[A]==B it means that The A-th bit of a Bitmask
          170  +** If WhereMaskSet.ix[A]==B it means that The A-th bit of a Bitmask
   169    171   ** corresponds VDBE cursor number B.  The A-th bit of a bitmask is 1<<A.
   170    172   **
   171    173   ** For example, if the WHERE clause expression used these VDBE
   172         -** cursors:  4, 5, 8, 29, 57, 73.  Then the  ExprMaskSet structure
          174  +** cursors:  4, 5, 8, 29, 57, 73.  Then the  WhereMaskSet structure
   173    175   ** would map those cursor numbers into bits 0 through 5.
   174    176   **
   175    177   ** Note that the mapping is not necessarily ordered.  In the example
   176    178   ** above, the mapping might go like this:  4->3, 5->1, 8->2, 29->0,
   177    179   ** 57->5, 73->4.  Or one of 719 other combinations might be used. It
   178    180   ** does not really matter.  What is important is that sparse cursor
   179    181   ** numbers all get mapped into bit numbers that begin with 0 and contain
   180    182   ** no gaps.
   181    183   */
   182         -struct ExprMaskSet {
          184  +struct WhereMaskSet {
   183    185     int n;                        /* Number of assigned cursor values */
   184    186     int ix[BMS];                  /* Cursor assigned to each bit */
   185    187   };
   186    188   
          189  +/*
          190  +** A WhereCost object records a lookup strategy and the estimated
          191  +** cost of pursuing that strategy.
          192  +*/
          193  +struct WhereCost {
          194  +  WherePlan plan;    /* The lookup strategy */
          195  +  double rCost;      /* Overall cost of pursuing this search strategy */
          196  +  double nRow;       /* Estimated number of output rows */
          197  +};
   187    198   
   188    199   /*
   189    200   ** Bitmasks for the operators that indices are able to exploit.  An
   190    201   ** OR-ed combination of these values can be used when searching for
   191    202   ** terms in the where clause.
   192    203   */
   193    204   #define WO_IN     0x001
................................................................................
   218    229   ** join.  Tickets #2177 and #2189.
   219    230   */
   220    231   #define WHERE_ROWID_EQ     0x00001000  /* rowid=EXPR or rowid IN (...) */
   221    232   #define WHERE_ROWID_RANGE  0x00002000  /* rowid<EXPR and/or rowid>EXPR */
   222    233   #define WHERE_COLUMN_EQ    0x00010000  /* x=EXPR or x IN (...) */
   223    234   #define WHERE_COLUMN_RANGE 0x00020000  /* x<EXPR and/or x>EXPR */
   224    235   #define WHERE_COLUMN_IN    0x00040000  /* x IN (...) */
          236  +#define WHERE_INDEXED      0x00070000  /* Anything that uses an index */
          237  +#define WHERE_IN_ABLE      0x00071000  /* Able to support an IN operator */
   225    238   #define WHERE_TOP_LIMIT    0x00100000  /* x<EXPR or x<=EXPR constraint */
   226    239   #define WHERE_BTM_LIMIT    0x00200000  /* x>EXPR or x>=EXPR constraint */
   227    240   #define WHERE_IDX_ONLY     0x00800000  /* Use index only - omit table */
   228    241   #define WHERE_ORDERBY      0x01000000  /* Output will appear in correct order */
   229    242   #define WHERE_REVERSE      0x02000000  /* Scan in reverse order */
   230    243   #define WHERE_UNIQUE       0x04000000  /* Selects no more than one row */
   231    244   #define WHERE_VIRTUALTABLE 0x08000000  /* Use virtual-table processing */
................................................................................
   233    246   
   234    247   /*
   235    248   ** Initialize a preallocated WhereClause structure.
   236    249   */
   237    250   static void whereClauseInit(
   238    251     WhereClause *pWC,        /* The WhereClause to be initialized */
   239    252     Parse *pParse,           /* The parsing context */
   240         -  ExprMaskSet *pMaskSet    /* Mapping from table indices to bitmasks */
          253  +  WhereMaskSet *pMaskSet   /* Mapping from table cursor numbers to bitmasks */
   241    254   ){
   242    255     pWC->pParse = pParse;
   243    256     pWC->pMaskSet = pMaskSet;
   244    257     pWC->nTerm = 0;
   245    258     pWC->nSlot = ArraySize(pWC->aStatic);
   246    259     pWC->a = pWC->aStatic;
   247    260   }
................................................................................
   251    264   
   252    265   /*
   253    266   ** Deallocate all memory associated with a WhereOrInfo object.
   254    267   */
   255    268   static void whereOrInfoDelete(sqlite3 *db, WhereOrInfo *p){
   256    269     if( p ){
   257    270       whereClauseClear(&p->wc);
          271  +    sqlite3DbFree(db, p->aPlan);
   258    272       sqlite3DbFree(db, p);
   259    273     }
   260    274   }
   261    275   
   262    276   /*
   263    277   ** Deallocate all memory associated with a WhereAndInfo object.
   264    278   */
................................................................................
   371    385   */
   372    386   #define initMaskSet(P)  memset(P, 0, sizeof(*P))
   373    387   
   374    388   /*
   375    389   ** Return the bitmask for the given cursor number.  Return 0 if
   376    390   ** iCursor is not in the set.
   377    391   */
   378         -static Bitmask getMask(ExprMaskSet *pMaskSet, int iCursor){
          392  +static Bitmask getMask(WhereMaskSet *pMaskSet, int iCursor){
   379    393     int i;
   380    394     for(i=0; i<pMaskSet->n; i++){
   381    395       if( pMaskSet->ix[i]==iCursor ){
   382    396         return ((Bitmask)1)<<i;
   383    397       }
   384    398     }
   385    399     return 0;
................................................................................
   389    403   ** Create a new mask for cursor iCursor.
   390    404   **
   391    405   ** There is one cursor per table in the FROM clause.  The number of
   392    406   ** tables in the FROM clause is limited by a test early in the
   393    407   ** sqlite3WhereBegin() routine.  So we know that the pMaskSet->ix[]
   394    408   ** array will never overflow.
   395    409   */
   396         -static void createMask(ExprMaskSet *pMaskSet, int iCursor){
          410  +static void createMask(WhereMaskSet *pMaskSet, int iCursor){
   397    411     assert( pMaskSet->n < ArraySize(pMaskSet->ix) );
   398    412     pMaskSet->ix[pMaskSet->n++] = iCursor;
   399    413   }
   400    414   
   401    415   /*
   402    416   ** This routine walks (recursively) an expression tree and generates
   403    417   ** a bitmask indicating which tables are used in that expression
................................................................................
   408    422   ** the header comment on that routine for additional information.
   409    423   ** The sqlite3ResolveExprNames() routines looks for column names and
   410    424   ** sets their opcodes to TK_COLUMN and their Expr.iTable fields to
   411    425   ** the VDBE cursor number of the table.  This routine just has to
   412    426   ** translate the cursor numbers into bitmask values and OR all
   413    427   ** the bitmasks together.
   414    428   */
   415         -static Bitmask exprListTableUsage(ExprMaskSet*, ExprList*);
   416         -static Bitmask exprSelectTableUsage(ExprMaskSet*, Select*);
   417         -static Bitmask exprTableUsage(ExprMaskSet *pMaskSet, Expr *p){
          429  +static Bitmask exprListTableUsage(WhereMaskSet*, ExprList*);
          430  +static Bitmask exprSelectTableUsage(WhereMaskSet*, Select*);
          431  +static Bitmask exprTableUsage(WhereMaskSet *pMaskSet, Expr *p){
   418    432     Bitmask mask = 0;
   419    433     if( p==0 ) return 0;
   420    434     if( p->op==TK_COLUMN ){
   421    435       mask = getMask(pMaskSet, p->iTable);
   422    436       return mask;
   423    437     }
   424    438     mask = exprTableUsage(pMaskSet, p->pRight);
   425    439     mask |= exprTableUsage(pMaskSet, p->pLeft);
   426    440     mask |= exprListTableUsage(pMaskSet, p->pList);
   427    441     mask |= exprSelectTableUsage(pMaskSet, p->pSelect);
   428    442     return mask;
   429    443   }
   430         -static Bitmask exprListTableUsage(ExprMaskSet *pMaskSet, ExprList *pList){
          444  +static Bitmask exprListTableUsage(WhereMaskSet *pMaskSet, ExprList *pList){
   431    445     int i;
   432    446     Bitmask mask = 0;
   433    447     if( pList ){
   434    448       for(i=0; i<pList->nExpr; i++){
   435    449         mask |= exprTableUsage(pMaskSet, pList->a[i].pExpr);
   436    450       }
   437    451     }
   438    452     return mask;
   439    453   }
   440         -static Bitmask exprSelectTableUsage(ExprMaskSet *pMaskSet, Select *pS){
          454  +static Bitmask exprSelectTableUsage(WhereMaskSet *pMaskSet, Select *pS){
   441    455     Bitmask mask = 0;
   442    456     while( pS ){
   443    457       mask |= exprListTableUsage(pMaskSet, pS->pEList);
   444    458       mask |= exprListTableUsage(pMaskSet, pS->pGroupBy);
   445    459       mask |= exprListTableUsage(pMaskSet, pS->pOrderBy);
   446    460       mask |= exprTableUsage(pMaskSet, pS->pWhere);
   447    461       mask |= exprTableUsage(pMaskSet, pS->pHaving);
................................................................................
   788    802     WhereClause *pWC,         /* the complete WHERE clause */
   789    803     int idxTerm               /* Index of the OR-term to be analyzed */
   790    804   ){
   791    805     Parse *pParse = pWC->pParse;            /* Parser context */
   792    806     sqlite3 *db = pParse->db;               /* Database connection */
   793    807     WhereTerm *pTerm = &pWC->a[idxTerm];    /* The term to be analyzed */
   794    808     Expr *pExpr = pTerm->pExpr;             /* The expression of the term */
   795         -  ExprMaskSet *pMaskSet = pWC->pMaskSet;  /* Table use masks */
          809  +  WhereMaskSet *pMaskSet = pWC->pMaskSet; /* Table use masks */
   796    810     int i;                                  /* Loop counters */
   797    811     WhereClause *pOrWc;       /* Breakup of pTerm into subterms */
   798    812     WhereTerm *pOrTerm;       /* A Sub-term within the pOrWc */
   799    813     WhereOrInfo *pOrInfo;     /* Additional information associated with pTerm */
   800    814     Bitmask chngToIN;         /* Tables that might satisfy case 1 */
   801    815     Bitmask indexable;        /* Tables that are indexable, satisfying case 2 */
   802    816   
................................................................................
   808    822     assert( (pTerm->wtFlags & (TERM_DYNAMIC|TERM_ORINFO|TERM_ANDINFO))==0 );
   809    823     assert( pExpr->op==TK_OR );
   810    824     pTerm->u.pOrInfo = pOrInfo = sqlite3DbMallocRaw(db, sizeof(*pOrInfo));
   811    825     if( pOrInfo==0 ) return;
   812    826     pTerm->wtFlags |= TERM_ORINFO;
   813    827     pOrWc = &pOrInfo->wc;
   814    828     whereClauseInit(pOrWc, pWC->pParse, pMaskSet);
          829  +  pOrInfo->aPlan = 0;
   815    830     whereSplit(pOrWc, pExpr, TK_OR);
   816    831     exprAnalyzeAll(pSrc, pOrWc);
   817    832     if( db->mallocFailed ) return;
   818    833     assert( pOrWc->nTerm>=2 );
   819    834   
   820    835     /*
   821    836     ** Compute the set of tables that might satisfy cases 1 or 2.
................................................................................
   842    857           chngToIN &= b;
   843    858         }
   844    859       }
   845    860     }
   846    861   
   847    862     /*
   848    863     ** Record the set of tables that satisfy case 2.  The set might be
   849         -  ** empty, but that is OK.
          864  +  ** empty.
   850    865     */
   851    866     pOrInfo->indexable = indexable;
   852         -  pTerm->eOperator = WO_OR;
          867  +  pTerm->eOperator = indexable==0 ? 0 : WO_OR;
   853    868   
   854    869     /*
   855    870     ** chngToIN holds a set of tables that *might* satisfy case 1.  But
   856    871     ** we have to do some additional checking to see if case 1 really
   857    872     ** is satisfied.
   858    873     */
   859    874     if( chngToIN ){
................................................................................
   943    958           pTerm->nChild = 1;
   944    959         }else{
   945    960           sqlite3ExprListDelete(db, pList);
   946    961         }
   947    962         pTerm->eOperator = 0;  /* case 1 trumps case 2 */
   948    963       }
   949    964     }
          965  +
          966  +  /* If case 2 applies, allocate space for pOrInfo->aPlan
          967  +  */
          968  +  if( pTerm->eOperator==WO_OR ){
          969  +    pOrInfo->aPlan = sqlite3DbMallocRaw(db, pOrWc->nTerm*sizeof(WherePlan));
          970  +  }
   950    971   }
   951    972   #endif /* !SQLITE_OMIT_OR_OPTIMIZATION && !SQLITE_OMIT_SUBQUERY */
   952    973   
   953    974   
   954    975   /*
   955    976   ** The input to this routine is an WhereTerm structure with only the
   956    977   ** "pExpr" field filled in.  The job of this routine is to analyze the
................................................................................
   971    992   */
   972    993   static void exprAnalyze(
   973    994     SrcList *pSrc,            /* the FROM clause */
   974    995     WhereClause *pWC,         /* the WHERE clause */
   975    996     int idxTerm               /* Index of the term to be analyzed */
   976    997   ){
   977    998     WhereTerm *pTerm;                /* The term to be analyzed */
   978         -  ExprMaskSet *pMaskSet;           /* Set of table index masks */
          999  +  WhereMaskSet *pMaskSet;          /* Set of table index masks */
   979   1000     Expr *pExpr;                     /* The expression to be analyzed */
   980   1001     Bitmask prereqLeft;              /* Prerequesites of the pExpr->pLeft */
   981   1002     Bitmask prereqAll;               /* Prerequesites of pExpr */
   982   1003     Bitmask extraRight = 0;
   983   1004     int nPattern;
   984   1005     int isComplete;
   985   1006     int noCase;
................................................................................
  1198   1219   
  1199   1220   /*
  1200   1221   ** Return TRUE if any of the expressions in pList->a[iFirst...] contain
  1201   1222   ** a reference to any table other than the iBase table.
  1202   1223   */
  1203   1224   static int referencesOtherTables(
  1204   1225     ExprList *pList,          /* Search expressions in ths list */
  1205         -  ExprMaskSet *pMaskSet,    /* Mapping from tables to bitmaps */
         1226  +  WhereMaskSet *pMaskSet,   /* Mapping from tables to bitmaps */
  1206   1227     int iFirst,               /* Be searching with the iFirst-th expression */
  1207   1228     int iBase                 /* Ignore references to this table */
  1208   1229   ){
  1209   1230     Bitmask allowed = ~getMask(pMaskSet, iBase);
  1210   1231     while( iFirst<pList->nExpr ){
  1211   1232       if( (exprTableUsage(pMaskSet, pList->a[iFirst++].pExpr)&allowed)!=0 ){
  1212   1233         return 1;
................................................................................
  1233   1254   ** ASC or DESC.  (Terms of the ORDER BY clause past the end of a UNIQUE
  1234   1255   ** index do not need to satisfy this constraint.)  The *pbRev value is
  1235   1256   ** set to 1 if the ORDER BY clause is all DESC and it is set to 0 if
  1236   1257   ** the ORDER BY clause is all ASC.
  1237   1258   */
  1238   1259   static int isSortingIndex(
  1239   1260     Parse *pParse,          /* Parsing context */
  1240         -  ExprMaskSet *pMaskSet,  /* Mapping from table indices to bitmaps */
         1261  +  WhereMaskSet *pMaskSet, /* Mapping from table cursor numbers to bitmaps */
  1241   1262     Index *pIdx,            /* The index we are testing */
  1242   1263     int base,               /* Cursor number for the table to be sorted */
  1243   1264     ExprList *pOrderBy,     /* The ORDER BY clause */
  1244   1265     int nEqCol,             /* Number of index columns with == constraints */
  1245   1266     int *pbRev              /* Set to 1 if ORDER BY is DESC */
  1246   1267   ){
  1247   1268     int i, j;                       /* Loop counters */
................................................................................
  1356   1377   ** Check table to see if the ORDER BY clause in pOrderBy can be satisfied
  1357   1378   ** by sorting in order of ROWID.  Return true if so and set *pbRev to be
  1358   1379   ** true for reverse ROWID and false for forward ROWID order.
  1359   1380   */
  1360   1381   static int sortableByRowid(
  1361   1382     int base,               /* Cursor number for table to be sorted */
  1362   1383     ExprList *pOrderBy,     /* The ORDER BY clause */
  1363         -  ExprMaskSet *pMaskSet,  /* Mapping from tables to bitmaps */
         1384  +  WhereMaskSet *pMaskSet, /* Mapping from table cursors to bitmaps */
  1364   1385     int *pbRev              /* Set to 1 if ORDER BY is DESC */
  1365   1386   ){
  1366   1387     Expr *p;
  1367   1388   
  1368   1389     assert( pOrderBy!=0 );
  1369   1390     assert( pOrderBy->nExpr>0 );
  1370   1391     p = pOrderBy->a[0].pExpr;
................................................................................
  1654   1675   
  1655   1676     *(int*)&pIdxInfo->nOrderBy = nOrderBy;
  1656   1677     return pIdxInfo->estimatedCost;
  1657   1678   }
  1658   1679   #endif /* SQLITE_OMIT_VIRTUALTABLE */
  1659   1680   
  1660   1681   /*
  1661         -** Find the best index for accessing a particular table.  Return a pointer
  1662         -** to the index, flags that describe how the index should be used, the
  1663         -** number of equality constraints, and the "cost" for this index.
         1682  +** Find the query plan for accessing a particular table.  Write the
         1683  +** best query plan and its cost into the WhereCost object supplied as the
         1684  +** last parameter.
  1664   1685   **
  1665         -** The lowest cost index wins.  The cost is an estimate of the amount of
  1666         -** CPU and disk I/O need to process the request using the selected index.
         1686  +** The lowest cost plan wins.  The cost is an estimate of the amount of
         1687  +** CPU and disk I/O need to process the request using the selected plan.
  1667   1688   ** Factors that influence cost include:
  1668   1689   **
  1669   1690   **    *  The estimated number of rows that will be retrieved.  (The
  1670   1691   **       fewer the better.)
  1671   1692   **
  1672   1693   **    *  Whether or not sorting must occur.
  1673   1694   **
  1674   1695   **    *  Whether or not there must be separate lookups in the
  1675   1696   **       index and in the main table.
  1676   1697   **
  1677   1698   ** If there was an INDEXED BY clause attached to the table in the SELECT
  1678         -** statement, then this function only considers strategies using the 
         1699  +** statement, then this function only considers plans using the 
  1679   1700   ** named index. If one cannot be found, then the returned cost is
  1680         -** SQLITE_BIG_DBL. If a strategy can be found that uses the named index, 
         1701  +** SQLITE_BIG_DBL. If a plan can be found that uses the named index, 
  1681   1702   ** then the cost is calculated in the usual way.
  1682   1703   **
  1683   1704   ** If a NOT INDEXED clause was attached to the table in the SELECT 
  1684   1705   ** statement, then no indexes are considered. However, the selected 
  1685         -** stategy may still take advantage of the tables built-in rowid
         1706  +** plan may still take advantage of the tables built-in rowid
  1686   1707   ** index.
  1687   1708   */
  1688         -static double bestIndex(
         1709  +static void bestIndex(
  1689   1710     Parse *pParse,              /* The parsing context */
  1690   1711     WhereClause *pWC,           /* The WHERE clause */
  1691   1712     struct SrcList_item *pSrc,  /* The FROM clause term to search */
  1692   1713     Bitmask notReady,           /* Mask of cursors that are not available */
  1693         -  ExprList *pOrderBy,         /* The order by clause */
  1694         -  Index **ppIndex,            /* Make *ppIndex point to the best index */
  1695         -  int *pWsFlags,              /* Put wsFlags describing scan strategy here */
  1696         -  int *pnEq                   /* Put the number of == or IN constraints here */
         1714  +  ExprList *pOrderBy,         /* The ORDER BY clause */
         1715  +  WhereCost *pCost            /* Lowest cost query plan */
  1697   1716   ){
  1698         -  WhereTerm *pTerm;
  1699         -  Index *bestIdx = 0;         /* Index that gives the lowest cost */
  1700         -  double lowestCost;          /* The cost of using bestIdx */
  1701         -  int bestWsFlags = 0;        /* Flags associated with bestIdx */
  1702         -  int bestNEq = 0;            /* Best value for nEq */
         1717  +  WhereTerm *pTerm;           /* A single term of the WHERE clause */
  1703   1718     int iCur = pSrc->iCursor;   /* The cursor of the table to be accessed */
  1704   1719     Index *pProbe;              /* An index we are evaluating */
  1705   1720     int rev;                    /* True to scan in reverse order */
  1706   1721     int wsFlags;                /* Flags associated with pProbe */
  1707   1722     int nEq;                    /* Number of == or IN constraints */
  1708   1723     int eqTermMask;             /* Mask of valid equality operators */
  1709   1724     double cost;                /* Cost of using pProbe */
         1725  +  double nRow;                /* Estimated number of rows in result set */
  1710   1726   
  1711   1727     WHERETRACE(("bestIndex: tbl=%s notReady=%llx\n", pSrc->pTab->zName,notReady));
  1712         -  lowestCost = SQLITE_BIG_DBL;
  1713   1728     pProbe = pSrc->pTab->pIndex;
  1714   1729     if( pSrc->notIndexed ){
  1715   1730       pProbe = 0;
  1716   1731     }
  1717   1732   
  1718   1733     /* If the table has no indices and there are no terms in the where
  1719   1734     ** clause that refer to the ROWID, then we will never be able to do
  1720   1735     ** anything other than a full table scan on this table.  We might as
  1721   1736     ** well put it first in the join order.  That way, perhaps it can be
  1722   1737     ** referenced by other tables in the join.
  1723   1738     */
         1739  +  memset(pCost, 0, sizeof(*pCost));
  1724   1740     if( pProbe==0 &&
  1725   1741        findTerm(pWC, iCur, -1, 0, WO_EQ|WO_IN|WO_LT|WO_LE|WO_GT|WO_GE,0)==0 &&
  1726   1742        (pOrderBy==0 || !sortableByRowid(iCur, pOrderBy, pWC->pMaskSet, &rev)) ){
  1727         -    *pWsFlags = 0;
  1728         -    *ppIndex = 0;
  1729         -    *pnEq = 0;
  1730         -    return 0.0;
         1743  +    return;
  1731   1744     }
         1745  +  pCost->rCost = SQLITE_BIG_DBL;
  1732   1746   
  1733   1747     /* Check for a rowid=EXPR or rowid IN (...) constraints. If there was
  1734   1748     ** an INDEXED BY clause attached to this table, skip this step.
  1735   1749     */
  1736   1750     if( !pSrc->pIndex ){
  1737   1751       pTerm = findTerm(pWC, iCur, -1, notReady, WO_EQ|WO_IN, 0);
  1738   1752       if( pTerm ){
  1739   1753         Expr *pExpr;
  1740         -      *ppIndex = 0;
  1741         -      bestWsFlags = WHERE_ROWID_EQ;
         1754  +      pCost->plan.wsFlags = WHERE_ROWID_EQ;
  1742   1755         if( pTerm->eOperator & WO_EQ ){
  1743   1756           /* Rowid== is always the best pick.  Look no further.  Because only
  1744   1757           ** a single row is generated, output is always in sorted order */
  1745         -        *pWsFlags = WHERE_ROWID_EQ | WHERE_UNIQUE;
  1746         -        *pnEq = 1;
         1758  +        pCost->plan.wsFlags = WHERE_ROWID_EQ | WHERE_UNIQUE;
         1759  +        pCost->plan.nEq = 1;
  1747   1760           WHERETRACE(("... best is rowid\n"));
  1748         -        return 0.0;
         1761  +        pCost->rCost = 0;
         1762  +        pCost->nRow = 1;
         1763  +        return;
  1749   1764         }else if( (pExpr = pTerm->pExpr)->pList!=0 ){
  1750   1765           /* Rowid IN (LIST): cost is NlogN where N is the number of list
  1751   1766           ** elements.  */
  1752         -        lowestCost = pExpr->pList->nExpr;
  1753         -        lowestCost *= estLog(lowestCost);
         1767  +        pCost->rCost = pCost->nRow = pExpr->pList->nExpr;
         1768  +        pCost->rCost *= estLog(pCost->rCost);
  1754   1769         }else{
  1755   1770           /* Rowid IN (SELECT): cost is NlogN where N is the number of rows
  1756   1771           ** in the result of the inner select.  We have no way to estimate
  1757   1772           ** that value so make a wild guess. */
  1758         -        lowestCost = 200;
         1773  +        pCost->nRow = 100;
         1774  +        pCost->rCost = 200;
  1759   1775         }
  1760         -      WHERETRACE(("... rowid IN cost: %.9g\n", lowestCost));
         1776  +      WHERETRACE(("... rowid IN cost: %.9g\n", pCost->rCost));
  1761   1777       }
  1762   1778     
  1763   1779       /* Estimate the cost of a table scan.  If we do not know how many
  1764   1780       ** entries are in the table, use 1 million as a guess.
  1765   1781       */
  1766   1782       cost = pProbe ? pProbe->aiRowEst[0] : 1000000;
  1767   1783       WHERETRACE(("... table scan base cost: %.9g\n", cost));
................................................................................
  1779   1795           wsFlags |= WHERE_BTM_LIMIT;
  1780   1796           cost /= 3;  /* Guess that rowid>EXPR eliminates two-thirds of rows */
  1781   1797         }
  1782   1798         WHERETRACE(("... rowid range reduces cost to %.9g\n", cost));
  1783   1799       }else{
  1784   1800         wsFlags = 0;
  1785   1801       }
         1802  +    nRow = cost;
  1786   1803     
  1787   1804       /* If the table scan does not satisfy the ORDER BY clause, increase
  1788   1805       ** the cost by NlogN to cover the expense of sorting. */
  1789   1806       if( pOrderBy ){
  1790   1807         if( sortableByRowid(iCur, pOrderBy, pWC->pMaskSet, &rev) ){
  1791   1808           wsFlags |= WHERE_ORDERBY|WHERE_ROWID_RANGE;
  1792   1809           if( rev ){
................................................................................
  1793   1810             wsFlags |= WHERE_REVERSE;
  1794   1811           }
  1795   1812         }else{
  1796   1813           cost += cost*estLog(cost);
  1797   1814           WHERETRACE(("... sorting increases cost to %.9g\n", cost));
  1798   1815         }
  1799   1816       }
  1800         -    if( cost<lowestCost ){
  1801         -      lowestCost = cost;
  1802         -      bestWsFlags = wsFlags;
         1817  +    if( cost<pCost->rCost ){
         1818  +      pCost->rCost = cost;
         1819  +      pCost->nRow = nRow;
         1820  +      pCost->plan.wsFlags = wsFlags;
  1803   1821       }
  1804   1822     }
  1805   1823   
  1806   1824     /* If the pSrc table is the right table of a LEFT JOIN then we may not
  1807   1825     ** use an index to satisfy IS NULL constraints on that table.  This is
  1808   1826     ** because columns might end up being NULL if the table does not match -
  1809   1827     ** a circumstance which the index cannot help us discover.  Ticket #2177.
................................................................................
  1840   1858           if( pExpr->pSelect!=0 ){
  1841   1859             inMultiplier *= 25;
  1842   1860           }else if( ALWAYS(pExpr->pList) ){
  1843   1861             inMultiplier *= pExpr->pList->nExpr + 1;
  1844   1862           }
  1845   1863         }
  1846   1864       }
  1847         -    cost = pProbe->aiRowEst[i] * inMultiplier * estLog(inMultiplier);
         1865  +    nRow = pProbe->aiRowEst[i] * inMultiplier;
         1866  +    cost = nRow * estLog(inMultiplier);
  1848   1867       nEq = i;
  1849   1868       if( pProbe->onError!=OE_None && (wsFlags & WHERE_COLUMN_IN)==0
  1850   1869            && nEq==pProbe->nColumn ){
  1851   1870         wsFlags |= WHERE_UNIQUE;
  1852   1871       }
  1853   1872       WHERETRACE(("...... nEq=%d inMult=%.9g cost=%.9g\n",nEq,inMultiplier,cost));
  1854   1873   
................................................................................
  1858   1877         int j = pProbe->aiColumn[nEq];
  1859   1878         pTerm = findTerm(pWC, iCur, j, notReady, WO_LT|WO_LE|WO_GT|WO_GE, pProbe);
  1860   1879         if( pTerm ){
  1861   1880           wsFlags |= WHERE_COLUMN_RANGE;
  1862   1881           if( findTerm(pWC, iCur, j, notReady, WO_LT|WO_LE, pProbe) ){
  1863   1882             wsFlags |= WHERE_TOP_LIMIT;
  1864   1883             cost /= 3;
         1884  +          nRow /= 3;
  1865   1885           }
  1866   1886           if( findTerm(pWC, iCur, j, notReady, WO_GT|WO_GE, pProbe) ){
  1867   1887             wsFlags |= WHERE_BTM_LIMIT;
  1868   1888             cost /= 3;
         1889  +          nRow /= 3;
  1869   1890           }
  1870   1891           WHERETRACE(("...... range reduces cost to %.9g\n", cost));
  1871   1892         }
  1872   1893       }
  1873   1894   
  1874   1895       /* Add the additional cost of sorting if that is a factor.
  1875   1896       */
................................................................................
  1907   1928           cost /= 2;
  1908   1929           WHERETRACE(("...... idx-only reduces cost to %.9g\n", cost));
  1909   1930         }
  1910   1931       }
  1911   1932   
  1912   1933       /* If this index has achieved the lowest cost so far, then use it.
  1913   1934       */
  1914         -    if( wsFlags && cost < lowestCost ){
  1915         -      bestIdx = pProbe;
  1916         -      lowestCost = cost;
  1917         -      bestWsFlags = wsFlags;
  1918         -      bestNEq = nEq;
         1935  +    if( wsFlags!=0 && cost < pCost->rCost ){
         1936  +      pCost->rCost = cost;
         1937  +      pCost->nRow = nRow;
         1938  +      pCost->plan.wsFlags = wsFlags;
         1939  +      pCost->plan.nEq = nEq;
         1940  +      assert( pCost->plan.wsFlags & WHERE_INDEXED );
         1941  +      pCost->plan.u.pIdx = pProbe;
  1919   1942       }
  1920   1943     }
  1921   1944   
  1922   1945     /* Report the best result
  1923   1946     */
  1924         -  *ppIndex = bestIdx;
  1925         -  WHERETRACE(("best index is %s, cost=%.9g, wsFlags=%x, nEq=%d\n",
  1926         -        bestIdx ? bestIdx->zName : "(none)", lowestCost, bestWsFlags, bestNEq));
  1927         -  *pWsFlags = bestWsFlags | eqTermMask;
  1928         -  *pnEq = bestNEq;
  1929         -  return lowestCost;
         1947  +  pCost->plan.wsFlags |= eqTermMask;
         1948  +  WHERETRACE(("best index is %s, cost=%.9g, nrow=%.9g, wsFlags=%x, nEq=%d\n",
         1949  +        (pCost->plan.wsFlags & WHERE_INDEXED)!=0 ?
         1950  +             pCost->plan.u.pIdx->zName : "(none)", pCost->nRow,
         1951  +        pCost->rCost, pCost->plan.wsFlags, pCost->plan.nEq));
  1930   1952   }
  1931   1953   
  1932   1954   
  1933   1955   /*
  1934   1956   ** Disable a term in the WHERE clause.  Except, do not disable the term
  1935   1957   ** if it controls a LEFT OUTER JOIN and it did not originate in the ON
  1936   1958   ** or USING clause of that join.
................................................................................
  2018   2040   
  2019   2041       assert( pX->op==TK_IN );
  2020   2042       iReg = iTarget;
  2021   2043       eType = sqlite3FindInIndex(pParse, pX, 0);
  2022   2044       iTab = pX->iTable;
  2023   2045       sqlite3VdbeAddOp2(v, OP_Rewind, iTab, 0);
  2024   2046       VdbeComment((v, "%.*s", pX->span.n, pX->span.z));
  2025         -    if( pLevel->nIn==0 ){
         2047  +    assert( pLevel->plan.wsFlags & WHERE_IN_ABLE );
         2048  +    if( pLevel->u.in.nIn==0 ){
  2026   2049         pLevel->addrNxt = sqlite3VdbeMakeLabel(v);
  2027   2050       }
  2028         -    pLevel->nIn++;
  2029         -    pLevel->aInLoop = sqlite3DbReallocOrFree(pParse->db, pLevel->aInLoop,
  2030         -                                    sizeof(pLevel->aInLoop[0])*pLevel->nIn);
  2031         -    pIn = pLevel->aInLoop;
         2051  +    pLevel->u.in.nIn++;
         2052  +    pLevel->u.in.aInLoop =
         2053  +       sqlite3DbReallocOrFree(pParse->db, pLevel->u.in.aInLoop,
         2054  +                              sizeof(pLevel->u.in.aInLoop[0])*pLevel->u.in.nIn);
         2055  +    pIn = pLevel->u.in.aInLoop;
  2032   2056       if( pIn ){
  2033         -      pIn += pLevel->nIn - 1;
         2057  +      pIn += pLevel->u.in.nIn - 1;
  2034   2058         pIn->iCur = iTab;
  2035   2059         if( eType==IN_INDEX_ROWID ){
  2036   2060           pIn->addrInTop = sqlite3VdbeAddOp2(v, OP_Rowid, iTab, iReg);
  2037   2061         }else{
  2038   2062           pIn->addrInTop = sqlite3VdbeAddOp3(v, OP_Column, iTab, 0, iReg);
  2039   2063         }
  2040   2064         sqlite3VdbeAddOp1(v, OP_IsNull, iReg);
  2041   2065       }else{
  2042         -      pLevel->nIn = 0;
         2066  +      pLevel->u.in.nIn = 0;
  2043   2067       }
  2044   2068   #endif
  2045   2069     }
  2046   2070     disableTerm(pLevel, pTerm);
  2047   2071     return iReg;
  2048   2072   }
  2049   2073   
................................................................................
  2073   2097   static int codeAllEqualityTerms(
  2074   2098     Parse *pParse,        /* Parsing context */
  2075   2099     WhereLevel *pLevel,   /* Which nested loop of the FROM we are coding */
  2076   2100     WhereClause *pWC,     /* The WHERE clause */
  2077   2101     Bitmask notReady,     /* Which parts of FROM have not yet been coded */
  2078   2102     int nExtraReg         /* Number of extra registers to allocate */
  2079   2103   ){
  2080         -  int nEq = pLevel->nEq;        /* The number of == or IN constraints to code */
  2081         -  Vdbe *v = pParse->pVdbe;      /* The virtual machine under construction */
  2082         -  Index *pIdx = pLevel->pIdx;   /* The index being used for this loop */
         2104  +  int nEq = pLevel->plan.nEq;   /* The number of == or IN constraints to code */
         2105  +  Vdbe *v = pParse->pVdbe;      /* The vm under construction */
         2106  +  Index *pIdx;                  /* The index being used for this loop */
  2083   2107     int iCur = pLevel->iTabCur;   /* The cursor of the table */
  2084   2108     WhereTerm *pTerm;             /* A single constraint term */
  2085   2109     int j;                        /* Loop counter */
  2086   2110     int regBase;                  /* Base register */
         2111  +
         2112  +  /* This module is only called on query plans that use an index. */
         2113  +  assert( pLevel->plan.wsFlags & WHERE_INDEXED );
         2114  +  pIdx = pLevel->plan.u.pIdx;
  2087   2115   
  2088   2116     /* Figure out how many memory cells we will need then allocate them.
  2089   2117     ** We always need at least one used to store the loop terminator
  2090   2118     ** value.  If there are IN operators we'll need one for each == or
  2091   2119     ** IN constraint.
  2092   2120     */
  2093   2121     regBase = pParse->nMem + 1;
  2094         -  pParse->nMem += pLevel->nEq + 1 + nExtraReg;
         2122  +  pParse->nMem += pLevel->plan.nEq + 1 + nExtraReg;
  2095   2123   
  2096   2124     /* Evaluate the equality constraints
  2097   2125     */
  2098   2126     assert( pIdx->nColumn>=nEq );
  2099   2127     for(j=0; j<nEq; j++){
  2100   2128       int r1;
  2101   2129       int k = pIdx->aiColumn[j];
  2102         -    pTerm = findTerm(pWC, iCur, k, notReady, pLevel->wsFlags, pIdx);
         2130  +    pTerm = findTerm(pWC, iCur, k, notReady, pLevel->plan.wsFlags, pIdx);
  2103   2131       if( NEVER(pTerm==0) ) break;
  2104   2132       assert( (pTerm->wtFlags & TERM_CODED)==0 );
  2105   2133       r1 = codeEqualityTerm(pParse, pTerm, pLevel, regBase+j);
  2106   2134       if( r1!=regBase+j ){
  2107   2135         sqlite3VdbeAddOp2(v, OP_SCopy, r1, regBase+j);
  2108   2136       }
  2109   2137       testcase( pTerm->eOperator & WO_ISNULL );
................................................................................
  2110   2138       testcase( pTerm->eOperator & WO_IN );
  2111   2139       if( (pTerm->eOperator & (WO_ISNULL|WO_IN))==0 ){
  2112   2140         sqlite3VdbeAddOp2(v, OP_IsNull, regBase+j, pLevel->addrBrk);
  2113   2141       }
  2114   2142     }
  2115   2143     return regBase;
  2116   2144   }
         2145  +
         2146  +/*
         2147  +** Generate code for the start of the iLevel-th loop in the WHERE clause
         2148  +** implementation described by pWInfo.
         2149  +*/
         2150  +static Bitmask codeOneLoopStart(
         2151  +  WhereInfo *pWInfo,   /* Complete information about the WHERE clause */
         2152  +  int iLevel,          /* Which level of pWInfo->a[] should be coded */
         2153  +  u8 wctrlFlags,       /* One of the WHERE_* flags defined in sqliteInt.h */
         2154  +  Bitmask notReady     /* Which tables are currently available */
         2155  +){
         2156  +  int j, k;            /* Loop counters */
         2157  +  int iCur;            /* The VDBE cursor for the table */
         2158  +  int addrNxt;         /* Where to jump to continue with the next IN case */
         2159  +  int omitTable;       /* True if we use the index only */
         2160  +  int bRev;            /* True if we need to scan in reverse order */
         2161  +  WhereLevel *pLevel;  /* The where level to be coded */
         2162  +  WhereClause *pWC;    /* Decomposition of the entire WHERE clause */
         2163  +  WhereTerm *pTerm;               /* A WHERE clause term */
         2164  +  Parse *pParse;                  /* Parsing context */
         2165  +  Vdbe *v;                        /* The prepared stmt under constructions */
         2166  +  struct SrcList_item *pTabItem;  /* FROM clause term being coded */
         2167  +  int addrBrk;
         2168  +  int addrCont;
         2169  +  
         2170  +
         2171  +  pParse = pWInfo->pParse;
         2172  +  v = pParse->pVdbe;
         2173  +  pWC = pWInfo->pWC;
         2174  +  pLevel = &pWInfo->a[iLevel];
         2175  +  pTabItem = &pWInfo->pTabList->a[pLevel->iFrom];
         2176  +  iCur = pTabItem->iCursor;
         2177  +  bRev = (pLevel->plan.wsFlags & WHERE_REVERSE)!=0;
         2178  +  omitTable = (pLevel->plan.wsFlags & WHERE_IDX_ONLY)!=0;
         2179  +
         2180  +  /* Create labels for the "break" and "continue" instructions
         2181  +  ** for the current loop.  Jump to addrBrk to break out of a loop.
         2182  +  ** Jump to cont to go immediately to the next iteration of the
         2183  +  ** loop.
         2184  +  **
         2185  +  ** When there is an IN operator, we also have a "addrNxt" label that
         2186  +  ** means to continue with the next IN value combination.  When
         2187  +  ** there are no IN operators in the constraints, the "addrNxt" label
         2188  +  ** is the same as "addrBrk".
         2189  +  */
         2190  +  addrBrk = pLevel->addrBrk = pLevel->addrNxt = sqlite3VdbeMakeLabel(v);
         2191  +  addrCont = pLevel->addrCont = sqlite3VdbeMakeLabel(v);
         2192  +
         2193  +  /* If this is the right table of a LEFT OUTER JOIN, allocate and
         2194  +  ** initialize a memory cell that records if this table matches any
         2195  +  ** row of the left table of the join.
         2196  +  */
         2197  +  if( pLevel->iFrom>0 && (pTabItem[0].jointype & JT_LEFT)!=0 ){
         2198  +    pLevel->iLeftJoin = ++pParse->nMem;
         2199  +    sqlite3VdbeAddOp2(v, OP_Integer, 0, pLevel->iLeftJoin);
         2200  +    VdbeComment((v, "init LEFT JOIN no-match flag"));
         2201  +  }
         2202  +
         2203  +#ifndef SQLITE_OMIT_VIRTUALTABLE
         2204  +  if(  (pLevel->plan.wsFlags & WHERE_VIRTUALTABLE)!=0 ){
         2205  +    /* Case 0:  The table is a virtual-table.  Use the VFilter and VNext
         2206  +    **          to access the data.
         2207  +    */
         2208  +    int iReg;   /* P3 Value for OP_VFilter */
         2209  +    sqlite3_index_info *pVtabIdx = pLevel->plan.u.pVtabIdx;
         2210  +    int nConstraint = pVtabIdx->nConstraint;
         2211  +    struct sqlite3_index_constraint_usage *aUsage =
         2212  +                                                pVtabIdx->aConstraintUsage;
         2213  +    const struct sqlite3_index_constraint *aConstraint =
         2214  +                                                pVtabIdx->aConstraint;
         2215  +
         2216  +    iReg = sqlite3GetTempRange(pParse, nConstraint+2);
         2217  +    pParse->disableColCache++;
         2218  +    for(j=1; j<=nConstraint; j++){
         2219  +      for(k=0; k<nConstraint; k++){
         2220  +        if( aUsage[k].argvIndex==j ){
         2221  +          int iTerm = aConstraint[k].iTermOffset;
         2222  +          assert( pParse->disableColCache );
         2223  +          sqlite3ExprCode(pParse, pWC->a[iTerm].pExpr->pRight, iReg+j+1);
         2224  +          break;
         2225  +        }
         2226  +      }
         2227  +      if( k==nConstraint ) break;
         2228  +    }
         2229  +    assert( pParse->disableColCache );
         2230  +    pParse->disableColCache--;
         2231  +    sqlite3VdbeAddOp2(v, OP_Integer, pVtabIdx->idxNum, iReg);
         2232  +    sqlite3VdbeAddOp2(v, OP_Integer, j-1, iReg+1);
         2233  +    sqlite3VdbeAddOp4(v, OP_VFilter, iCur, addrBrk, iReg, pVtabIdx->idxStr,
         2234  +                      pVtabIdx->needToFreeIdxStr ? P4_MPRINTF : P4_STATIC);
         2235  +    sqlite3ReleaseTempRange(pParse, iReg, nConstraint+2);
         2236  +    pVtabIdx->needToFreeIdxStr = 0;
         2237  +    for(j=0; j<nConstraint; j++){
         2238  +      if( aUsage[j].omit ){
         2239  +        int iTerm = aConstraint[j].iTermOffset;
         2240  +        disableTerm(pLevel, &pWC->a[iTerm]);
         2241  +      }
         2242  +    }
         2243  +    pLevel->op = OP_VNext;
         2244  +    pLevel->p1 = iCur;
         2245  +    pLevel->p2 = sqlite3VdbeCurrentAddr(v);
         2246  +  }else
         2247  +#endif /* SQLITE_OMIT_VIRTUALTABLE */
         2248  +
         2249  +  if( pLevel->plan.wsFlags & WHERE_ROWID_EQ ){
         2250  +    /* Case 1:  We can directly reference a single row using an
         2251  +    **          equality comparison against the ROWID field.  Or
         2252  +    **          we reference multiple rows using a "rowid IN (...)"
         2253  +    **          construct.
         2254  +    */
         2255  +    int r1;
         2256  +    int rtmp = sqlite3GetTempReg(pParse);
         2257  +    pTerm = findTerm(pWC, iCur, -1, notReady, WO_EQ|WO_IN, 0);
         2258  +    assert( pTerm!=0 );
         2259  +    assert( pTerm->pExpr!=0 );
         2260  +    assert( pTerm->leftCursor==iCur );
         2261  +    assert( omitTable==0 );
         2262  +    r1 = codeEqualityTerm(pParse, pTerm, pLevel, rtmp);
         2263  +    addrNxt = pLevel->addrNxt;
         2264  +    sqlite3VdbeAddOp2(v, OP_MustBeInt, r1, addrNxt);
         2265  +    sqlite3VdbeAddOp3(v, OP_NotExists, iCur, addrNxt, r1);
         2266  +    sqlite3ReleaseTempReg(pParse, rtmp);
         2267  +    VdbeComment((v, "pk"));
         2268  +    pLevel->op = OP_Noop;
         2269  +  }else if( pLevel->plan.wsFlags & WHERE_ROWID_RANGE ){
         2270  +    /* Case 2:  We have an inequality comparison against the ROWID field.
         2271  +    */
         2272  +    int testOp = OP_Noop;
         2273  +    int start;
         2274  +    int memEndValue = 0;
         2275  +    WhereTerm *pStart, *pEnd;
         2276  +
         2277  +    assert( omitTable==0 );
         2278  +    pStart = findTerm(pWC, iCur, -1, notReady, WO_GT|WO_GE, 0);
         2279  +    pEnd = findTerm(pWC, iCur, -1, notReady, WO_LT|WO_LE, 0);
         2280  +    if( bRev ){
         2281  +      pTerm = pStart;
         2282  +      pStart = pEnd;
         2283  +      pEnd = pTerm;
         2284  +    }
         2285  +    if( pStart ){
         2286  +      Expr *pX;             /* The expression that defines the start bound */
         2287  +      int r1, rTemp;        /* Registers for holding the start boundary */
         2288  +
         2289  +      /* The following constant maps TK_xx codes into corresponding 
         2290  +      ** seek opcodes.  It depends on a particular ordering of TK_xx
         2291  +      */
         2292  +      const u8 aMoveOp[] = {
         2293  +           /* TK_GT */  OP_SeekGt,
         2294  +           /* TK_LE */  OP_SeekLe,
         2295  +           /* TK_LT */  OP_SeekLt,
         2296  +           /* TK_GE */  OP_SeekGe
         2297  +      };
         2298  +      assert( TK_LE==TK_GT+1 );      /* Make sure the ordering.. */
         2299  +      assert( TK_LT==TK_GT+2 );      /*  ... of the TK_xx values... */
         2300  +      assert( TK_GE==TK_GT+3 );      /*  ... is correcct. */
         2301  +
         2302  +      pX = pStart->pExpr;
         2303  +      assert( pX!=0 );
         2304  +      assert( pStart->leftCursor==iCur );
         2305  +      r1 = sqlite3ExprCodeTemp(pParse, pX->pRight, &rTemp);
         2306  +      sqlite3VdbeAddOp3(v, aMoveOp[pX->op-TK_GT], iCur, addrBrk, r1);
         2307  +      VdbeComment((v, "pk"));
         2308  +      sqlite3ExprCacheAffinityChange(pParse, r1, 1);
         2309  +      sqlite3ReleaseTempReg(pParse, rTemp);
         2310  +      disableTerm(pLevel, pStart);
         2311  +    }else{
         2312  +      sqlite3VdbeAddOp2(v, bRev ? OP_Last : OP_Rewind, iCur, addrBrk);
         2313  +    }
         2314  +    if( pEnd ){
         2315  +      Expr *pX;
         2316  +      pX = pEnd->pExpr;
         2317  +      assert( pX!=0 );
         2318  +      assert( pEnd->leftCursor==iCur );
         2319  +      memEndValue = ++pParse->nMem;
         2320  +      sqlite3ExprCode(pParse, pX->pRight, memEndValue);
         2321  +      if( pX->op==TK_LT || pX->op==TK_GT ){
         2322  +        testOp = bRev ? OP_Le : OP_Ge;
         2323  +      }else{
         2324  +        testOp = bRev ? OP_Lt : OP_Gt;
         2325  +      }
         2326  +      disableTerm(pLevel, pEnd);
         2327  +    }
         2328  +    start = sqlite3VdbeCurrentAddr(v);
         2329  +    pLevel->op = bRev ? OP_Prev : OP_Next;
         2330  +    pLevel->p1 = iCur;
         2331  +    pLevel->p2 = start;
         2332  +    if( testOp!=OP_Noop ){
         2333  +      int r1 = sqlite3GetTempReg(pParse);
         2334  +      sqlite3VdbeAddOp2(v, OP_Rowid, iCur, r1);
         2335  +      sqlite3VdbeAddOp3(v, testOp, memEndValue, addrBrk, r1);
         2336  +      sqlite3VdbeChangeP5(v, SQLITE_AFF_NUMERIC | SQLITE_JUMPIFNULL);
         2337  +      sqlite3ReleaseTempReg(pParse, r1);
         2338  +    }
         2339  +  }else if( pLevel->plan.wsFlags & (WHERE_COLUMN_RANGE|WHERE_COLUMN_EQ) ){
         2340  +    /* Case 3: A scan using an index.
         2341  +    **
         2342  +    **         The WHERE clause may contain zero or more equality 
         2343  +    **         terms ("==" or "IN" operators) that refer to the N
         2344  +    **         left-most columns of the index. It may also contain
         2345  +    **         inequality constraints (>, <, >= or <=) on the indexed
         2346  +    **         column that immediately follows the N equalities. Only 
         2347  +    **         the right-most column can be an inequality - the rest must
         2348  +    **         use the "==" and "IN" operators. For example, if the 
         2349  +    **         index is on (x,y,z), then the following clauses are all 
         2350  +    **         optimized:
         2351  +    **
         2352  +    **            x=5
         2353  +    **            x=5 AND y=10
         2354  +    **            x=5 AND y<10
         2355  +    **            x=5 AND y>5 AND y<10
         2356  +    **            x=5 AND y=5 AND z<=10
         2357  +    **
         2358  +    **         The z<10 term of the following cannot be used, only
         2359  +    **         the x=5 term:
         2360  +    **
         2361  +    **            x=5 AND z<10
         2362  +    **
         2363  +    **         N may be zero if there are inequality constraints.
         2364  +    **         If there are no inequality constraints, then N is at
         2365  +    **         least one.
         2366  +    **
         2367  +    **         This case is also used when there are no WHERE clause
         2368  +    **         constraints but an index is selected anyway, in order
         2369  +    **         to force the output order to conform to an ORDER BY.
         2370  +    */  
         2371  +    int aStartOp[] = {
         2372  +      0,
         2373  +      0,
         2374  +      OP_Rewind,           /* 2: (!start_constraints && startEq &&  !bRev) */
         2375  +      OP_Last,             /* 3: (!start_constraints && startEq &&   bRev) */
         2376  +      OP_SeekGt,           /* 4: (start_constraints  && !startEq && !bRev) */
         2377  +      OP_SeekLt,           /* 5: (start_constraints  && !startEq &&  bRev) */
         2378  +      OP_SeekGe,           /* 6: (start_constraints  &&  startEq && !bRev) */
         2379  +      OP_SeekLe            /* 7: (start_constraints  &&  startEq &&  bRev) */
         2380  +    };
         2381  +    int aEndOp[] = {
         2382  +      OP_Noop,             /* 0: (!end_constraints) */
         2383  +      OP_IdxGE,            /* 1: (end_constraints && !bRev) */
         2384  +      OP_IdxLT             /* 2: (end_constraints && bRev) */
         2385  +    };
         2386  +    int nEq = pLevel->plan.nEq;
         2387  +    int isMinQuery = 0;          /* If this is an optimized SELECT min(x).. */
         2388  +    int regBase;                 /* Base register holding constraint values */
         2389  +    int r1;                      /* Temp register */
         2390  +    WhereTerm *pRangeStart = 0;  /* Inequality constraint at range start */
         2391  +    WhereTerm *pRangeEnd = 0;    /* Inequality constraint at range end */
         2392  +    int startEq;                 /* True if range start uses ==, >= or <= */
         2393  +    int endEq;                   /* True if range end uses ==, >= or <= */
         2394  +    int start_constraints;       /* Start of range is constrained */
         2395  +    int nConstraint;             /* Number of constraint terms */
         2396  +    Index *pIdx;         /* The index we will be using */
         2397  +    int iIdxCur;         /* The VDBE cursor for the index */
         2398  +    int op;
         2399  +
         2400  +    pIdx = pLevel->plan.u.pIdx;
         2401  +    iIdxCur = pLevel->iIdxCur;
         2402  +    k = pIdx->aiColumn[nEq];     /* Column for inequality constraints */
         2403  +
         2404  +    /* Generate code to evaluate all constraint terms using == or IN
         2405  +    ** and store the values of those terms in an array of registers
         2406  +    ** starting at regBase.
         2407  +    */
         2408  +    regBase = codeAllEqualityTerms(pParse, pLevel, pWC, notReady, 2);
         2409  +    addrNxt = pLevel->addrNxt;
         2410  +
         2411  +    /* If this loop satisfies a sort order (pOrderBy) request that 
         2412  +    ** was passed to this function to implement a "SELECT min(x) ..." 
         2413  +    ** query, then the caller will only allow the loop to run for
         2414  +    ** a single iteration. This means that the first row returned
         2415  +    ** should not have a NULL value stored in 'x'. If column 'x' is
         2416  +    ** the first one after the nEq equality constraints in the index,
         2417  +    ** this requires some special handling.
         2418  +    */
         2419  +    if( (wctrlFlags&WHERE_ORDERBY_MIN)!=0
         2420  +     && (pLevel->plan.wsFlags&WHERE_ORDERBY)
         2421  +     && (pIdx->nColumn>nEq)
         2422  +    ){
         2423  +      /* assert( pOrderBy->nExpr==1 ); */
         2424  +      /* assert( pOrderBy->a[0].pExpr->iColumn==pIdx->aiColumn[nEq] ); */
         2425  +      isMinQuery = 1;
         2426  +    }
         2427  +
         2428  +    /* Find any inequality constraint terms for the start and end 
         2429  +    ** of the range. 
         2430  +    */
         2431  +    if( pLevel->plan.wsFlags & WHERE_TOP_LIMIT ){
         2432  +      pRangeEnd = findTerm(pWC, iCur, k, notReady, (WO_LT|WO_LE), pIdx);
         2433  +    }
         2434  +    if( pLevel->plan.wsFlags & WHERE_BTM_LIMIT ){
         2435  +      pRangeStart = findTerm(pWC, iCur, k, notReady, (WO_GT|WO_GE), pIdx);
         2436  +    }
         2437  +
         2438  +    /* If we are doing a reverse order scan on an ascending index, or
         2439  +    ** a forward order scan on a descending index, interchange the 
         2440  +    ** start and end terms (pRangeStart and pRangeEnd).
         2441  +    */
         2442  +    if( bRev==(pIdx->aSortOrder[nEq]==SQLITE_SO_ASC) ){
         2443  +      SWAP(WhereTerm *, pRangeEnd, pRangeStart);
         2444  +    }
         2445  +
         2446  +    testcase( pRangeStart && pRangeStart->eOperator & WO_LE );
         2447  +    testcase( pRangeStart && pRangeStart->eOperator & WO_GE );
         2448  +    testcase( pRangeEnd && pRangeEnd->eOperator & WO_LE );
         2449  +    testcase( pRangeEnd && pRangeEnd->eOperator & WO_GE );
         2450  +    startEq = !pRangeStart || pRangeStart->eOperator & (WO_LE|WO_GE);
         2451  +    endEq =   !pRangeEnd || pRangeEnd->eOperator & (WO_LE|WO_GE);
         2452  +    start_constraints = pRangeStart || nEq>0;
         2453  +
         2454  +    /* Seek the index cursor to the start of the range. */
         2455  +    nConstraint = nEq;
         2456  +    if( pRangeStart ){
         2457  +      int dcc = pParse->disableColCache;
         2458  +      if( pRangeEnd ){
         2459  +        pParse->disableColCache++;
         2460  +      }
         2461  +      sqlite3ExprCode(pParse, pRangeStart->pExpr->pRight, regBase+nEq);
         2462  +      pParse->disableColCache = dcc;
         2463  +      sqlite3VdbeAddOp2(v, OP_IsNull, regBase+nEq, addrNxt);
         2464  +      nConstraint++;
         2465  +    }else if( isMinQuery ){
         2466  +      sqlite3VdbeAddOp2(v, OP_Null, 0, regBase+nEq);
         2467  +      nConstraint++;
         2468  +      startEq = 0;
         2469  +      start_constraints = 1;
         2470  +    }
         2471  +    codeApplyAffinity(pParse, regBase, nConstraint, pIdx);
         2472  +    op = aStartOp[(start_constraints<<2) + (startEq<<1) + bRev];
         2473  +    assert( op!=0 );
         2474  +    testcase( op==OP_Rewind );
         2475  +    testcase( op==OP_Last );
         2476  +    testcase( op==OP_SeekGt );
         2477  +    testcase( op==OP_SeekGe );
         2478  +    testcase( op==OP_SeekLe );
         2479  +    testcase( op==OP_SeekLt );
         2480  +    sqlite3VdbeAddOp4(v, op, iIdxCur, addrNxt, regBase, 
         2481  +                      SQLITE_INT_TO_PTR(nConstraint), P4_INT32);
         2482  +
         2483  +    /* Load the value for the inequality constraint at the end of the
         2484  +    ** range (if any).
         2485  +    */
         2486  +    nConstraint = nEq;
         2487  +    if( pRangeEnd ){
         2488  +      sqlite3ExprCode(pParse, pRangeEnd->pExpr->pRight, regBase+nEq);
         2489  +      sqlite3VdbeAddOp2(v, OP_IsNull, regBase+nEq, addrNxt);
         2490  +      codeApplyAffinity(pParse, regBase, nEq+1, pIdx);
         2491  +      nConstraint++;
         2492  +    }
         2493  +
         2494  +    /* Top of the loop body */
         2495  +    pLevel->p2 = sqlite3VdbeCurrentAddr(v);
         2496  +
         2497  +    /* Check if the index cursor is past the end of the range. */
         2498  +    op = aEndOp[(pRangeEnd || nEq) * (1 + bRev)];
         2499  +    testcase( op==OP_Noop );
         2500  +    testcase( op==OP_IdxGE );
         2501  +    testcase( op==OP_IdxLT );
         2502  +    sqlite3VdbeAddOp4(v, op, iIdxCur, addrNxt, regBase,
         2503  +                      SQLITE_INT_TO_PTR(nConstraint), P4_INT32);
         2504  +    sqlite3VdbeChangeP5(v, endEq!=bRev ?1:0);
         2505  +
         2506  +    /* If there are inequality constraints, check that the value
         2507  +    ** of the table column that the inequality contrains is not NULL.
         2508  +    ** If it is, jump to the next iteration of the loop.
         2509  +    */
         2510  +    r1 = sqlite3GetTempReg(pParse);
         2511  +    testcase( pLevel->plan.wsFlags & WHERE_BTM_LIMIT );
         2512  +    testcase( pLevel->plan.wsFlags & WHERE_TOP_LIMIT );
         2513  +    if( pLevel->plan.wsFlags & (WHERE_BTM_LIMIT|WHERE_TOP_LIMIT) ){
         2514  +      sqlite3VdbeAddOp3(v, OP_Column, iIdxCur, nEq, r1);
         2515  +      sqlite3VdbeAddOp2(v, OP_IsNull, r1, addrCont);
         2516  +    }
         2517  +
         2518  +    /* Seek the table cursor, if required */
         2519  +    if( !omitTable ){
         2520  +      sqlite3VdbeAddOp2(v, OP_IdxRowid, iIdxCur, r1);
         2521  +      sqlite3VdbeAddOp2(v, OP_Seek, iCur, r1);  /* Deferred seek */
         2522  +    }
         2523  +    sqlite3ReleaseTempReg(pParse, r1);
         2524  +
         2525  +    /* Record the instruction used to terminate the loop. Disable 
         2526  +    ** WHERE clause terms made redundant by the index range scan.
         2527  +    */
         2528  +    pLevel->op = bRev ? OP_Prev : OP_Next;
         2529  +    pLevel->p1 = iIdxCur;
         2530  +    disableTerm(pLevel, pRangeStart);
         2531  +    disableTerm(pLevel, pRangeEnd);
         2532  +  }else if( pLevel->plan.wsFlags & WHERE_MULTI_OR ){
         2533  +    /* Case 4:  Two or more separately indexed terms connected by OR
         2534  +    **
         2535  +    ** Example:
         2536  +    **
         2537  +    **   CREATE TABLE t1(a,b,c,d);
         2538  +    **   CREATE INDEX i1 ON t1(a);
         2539  +    **   CREATE INDEX i2 ON t1(b);
         2540  +    **   CREATE INDEX i3 ON t1(c);
         2541  +    **
         2542  +    **   SELECT * FROM t1 WHERE a=5 OR b=7 OR (c=11 AND d=13)
         2543  +    **
         2544  +    ** In the example, there are three indexed terms connected by OR.
         2545  +    ** The top of the loop is constructed by creating a RowSet object
         2546  +    ** and populating it.  Then looping over elements of the rowset.
         2547  +    **
         2548  +    **        Null 1
         2549  +    **        # fill RowSet 1 with entries where a=5 using i1
         2550  +    **        # fill Rowset 1 with entries where b=7 using i2
         2551  +    **        # fill Rowset 1 with entries where c=11 and d=13 i3 and t1
         2552  +    **     A: RowSetRead 1, B, 2
         2553  +    **        Seek       i, 2
         2554  +    **
         2555  +    ** The bottom of the loop looks like this:
         2556  +    **
         2557  +    **        Goto       0, A
         2558  +    **     B:
         2559  +    */
         2560  +    int regRowset;         /* Register holding the RowSet object */
         2561  +    int regNextRowid;      /* Register holding next rowid */
         2562  +    WhereTerm *pTerm;      /* The complete OR-clause */
         2563  +    WhereClause *pOrWc;    /* The OR-clause broken out into subterms */
         2564  +    WhereTerm *pOrTerm;    /* A single subterm within the OR-clause */
         2565  +   
         2566  +    pTerm = pLevel->plan.u.pTerm;
         2567  +    assert( pTerm!=0 );
         2568  +    assert( pTerm->eOperator==WO_OR );
         2569  +    assert( (pTerm->wtFlags & TERM_ORINFO)!=0 );
         2570  +    pOrWc = &pTerm->u.pOrInfo->wc;
         2571  +    
         2572  +    regRowset = sqlite3GetTempReg(pParse);
         2573  +    sqlite3VdbeAddOp1(v, OP_Null, regRowset);
         2574  +    for(j=0, pOrTerm=pOrWc->a; j<pOrWc->nTerm; j++, pOrTerm++){
         2575  +      if( pOrTerm->leftCursor!=iCur ) continue;
         2576  +      /* fillRowSetFromIdx(pParse, regRowset, pTabItem, pOrTerm); */
         2577  +    }
         2578  +    regNextRowid = sqlite3GetTempReg(pParse);
         2579  +    sqlite3VdbeResolveLabel(v, addrCont);
         2580  +    addrCont = 
         2581  +       sqlite3VdbeAddOp3(v, OP_RowSetRead, regRowset, addrBrk, regNextRowid);
         2582  +    sqlite3VdbeAddOp2(v, OP_Seek, iCur, regNextRowid);
         2583  +    sqlite3ReleaseTempReg(pParse, regNextRowid);
         2584  +    pLevel->op = OP_Goto;
         2585  +    pLevel->p2 = addrCont;
         2586  +  }else{
         2587  +    /* Case 5:  There is no usable index.  We must do a complete
         2588  +    **          scan of the entire table.
         2589  +    */
         2590  +    assert( omitTable==0 );
         2591  +    assert( bRev==0 );
         2592  +    pLevel->op = OP_Next;
         2593  +    pLevel->p1 = iCur;
         2594  +    pLevel->p2 = 1 + sqlite3VdbeAddOp2(v, OP_Rewind, iCur, addrBrk);
         2595  +    pLevel->p5 = SQLITE_STMTSTATUS_FULLSCAN_STEP;
         2596  +  }
         2597  +  notReady &= ~getMask(pWC->pMaskSet, iCur);
         2598  +
         2599  +  /* Insert code to test every subexpression that can be completely
         2600  +  ** computed using the current set of tables.
         2601  +  */
         2602  +  k = 0;
         2603  +  for(pTerm=pWC->a, j=pWC->nTerm; j>0; j--, pTerm++){
         2604  +    Expr *pE;
         2605  +    testcase( pTerm->wtFlags & TERM_VIRTUAL );
         2606  +    testcase( pTerm->wtFlags & TERM_CODED );
         2607  +    if( pTerm->wtFlags & (TERM_VIRTUAL|TERM_CODED) ) continue;
         2608  +    if( (pTerm->prereqAll & notReady)!=0 ) continue;
         2609  +    pE = pTerm->pExpr;
         2610  +    assert( pE!=0 );
         2611  +    if( pLevel->iLeftJoin && !ExprHasProperty(pE, EP_FromJoin) ){
         2612  +      continue;
         2613  +    }
         2614  +    pParse->disableColCache += k;
         2615  +    sqlite3ExprIfFalse(pParse, pE, addrCont, SQLITE_JUMPIFNULL);
         2616  +    pParse->disableColCache -= k;
         2617  +    k = 1;
         2618  +    pTerm->wtFlags |= TERM_CODED;
         2619  +  }
         2620  +
         2621  +  /* For a LEFT OUTER JOIN, generate code that will record the fact that
         2622  +  ** at least one row of the right table has matched the left table.  
         2623  +  */
         2624  +  if( pLevel->iLeftJoin ){
         2625  +    pLevel->addrFirst = sqlite3VdbeCurrentAddr(v);
         2626  +    sqlite3VdbeAddOp2(v, OP_Integer, 1, pLevel->iLeftJoin);
         2627  +    VdbeComment((v, "record LEFT JOIN hit"));
         2628  +    sqlite3ExprClearColumnCache(pParse, pLevel->iTabCur);
         2629  +    sqlite3ExprClearColumnCache(pParse, pLevel->iIdxCur);
         2630  +    for(pTerm=pWC->a, j=0; j<pWC->nTerm; j++, pTerm++){
         2631  +      testcase( pTerm->wtFlags & TERM_VIRTUAL );
         2632  +      testcase( pTerm->wtFlags & TERM_CODED );
         2633  +      if( pTerm->wtFlags & (TERM_VIRTUAL|TERM_CODED) ) continue;
         2634  +      if( (pTerm->prereqAll & notReady)!=0 ) continue;
         2635  +      assert( pTerm->pExpr );
         2636  +      sqlite3ExprIfFalse(pParse, pTerm->pExpr, addrCont, SQLITE_JUMPIFNULL);
         2637  +      pTerm->wtFlags |= TERM_CODED;
         2638  +    }
         2639  +  }
         2640  +  return notReady;
         2641  +}
  2117   2642   
  2118   2643   #if defined(SQLITE_TEST)
  2119   2644   /*
  2120   2645   ** The following variable holds a text description of query plan generated
  2121   2646   ** by the most recent call to sqlite3WhereBegin().  Each call to WhereBegin
  2122   2647   ** overwrites the previous.  This information is used for testing and
  2123   2648   ** analysis only.
................................................................................
  2137   2662       for(i=0; i<pWInfo->nLevel; i++){
  2138   2663         sqlite3_index_info *pInfo = pWInfo->a[i].pIdxInfo;
  2139   2664         if( pInfo ){
  2140   2665           assert( pInfo->needToFreeIdxStr==0 );
  2141   2666           sqlite3DbFree(db, pInfo);
  2142   2667         }
  2143   2668       }
         2669  +    whereClauseClear(pWInfo->pWC);
  2144   2670       sqlite3DbFree(db, pWInfo);
  2145   2671     }
  2146   2672   }
  2147   2673   
  2148   2674   
  2149   2675   /*
  2150   2676   ** Generate the beginning of the loop used for WHERE clause processing.
................................................................................
  2240   2766     Expr *pWhere,         /* The WHERE clause */
  2241   2767     ExprList **ppOrderBy, /* An ORDER BY clause, or NULL */
  2242   2768     u8 wctrlFlags         /* One of the WHERE_* flags defined in sqliteInt.h */
  2243   2769   ){
  2244   2770     int i;                     /* Loop counter */
  2245   2771     WhereInfo *pWInfo;         /* Will become the return value of this function */
  2246   2772     Vdbe *v = pParse->pVdbe;   /* The virtual database engine */
  2247         -  int addrBrk, addrCont = 0; /* Addresses used during code generation */
  2248   2773     Bitmask notReady;          /* Cursors that are not yet positioned */
  2249         -  WhereTerm *pTerm;          /* A single term in the WHERE clause */
  2250         -  ExprMaskSet maskSet;       /* The expression mask set */
  2251         -  WhereClause wc;            /* The WHERE clause is divided into these terms */
         2774  +  WhereMaskSet *pMaskSet;    /* The expression mask set */
         2775  +  //WhereClause wc;          /* The WHERE clause is divided into these terms */
         2776  +  WhereClause *pWC;               /* Decomposition of the WHERE clause */
  2252   2777     struct SrcList_item *pTabItem;  /* A single entry from pTabList */
  2253   2778     WhereLevel *pLevel;             /* A single level in the pWInfo list */
  2254   2779     int iFrom;                      /* First unused FROM clause element */
  2255         -  int andFlags;              /* AND-ed combination of all wc.a[].wtFlags */
         2780  +  int andFlags;              /* AND-ed combination of all pWC->a[].wtFlags */
  2256   2781     sqlite3 *db;               /* Database connection */
  2257   2782     ExprList *pOrderBy = 0;
  2258   2783   
  2259   2784     /* The number of tables in the FROM clause is limited by the number of
  2260   2785     ** bits in a Bitmask 
  2261   2786     */
  2262   2787     if( pTabList->nSrc>BMS ){
................................................................................
  2264   2789       return 0;
  2265   2790     }
  2266   2791   
  2267   2792     if( ppOrderBy ){
  2268   2793       pOrderBy = *ppOrderBy;
  2269   2794     }
  2270   2795   
  2271         -  /* Split the WHERE clause into separate subexpressions where each
  2272         -  ** subexpression is separated by an AND operator.
  2273         -  */
  2274         -  initMaskSet(&maskSet);
  2275         -  whereClauseInit(&wc, pParse, &maskSet);
  2276         -  sqlite3ExprCodeConstants(pParse, pWhere);
  2277         -  whereSplit(&wc, pWhere, TK_AND);
  2278         -    
  2279   2796     /* Allocate and initialize the WhereInfo structure that will become the
  2280   2797     ** return value.
  2281   2798     */
  2282   2799     db = pParse->db;
  2283   2800     pWInfo = sqlite3DbMallocZero(db,  
  2284         -                      sizeof(WhereInfo) + pTabList->nSrc*sizeof(WhereLevel));
         2801  +                      sizeof(WhereInfo)
         2802  +                      + (pTabList->nSrc-1)*sizeof(WhereLevel)
         2803  +                      + sizeof(WhereClause)
         2804  +                      + sizeof(WhereMaskSet)
         2805  +           );
  2285   2806     if( db->mallocFailed ){
  2286   2807       goto whereBeginError;
  2287   2808     }
  2288   2809     pWInfo->nLevel = pTabList->nSrc;
  2289   2810     pWInfo->pParse = pParse;
  2290   2811     pWInfo->pTabList = pTabList;
  2291   2812     pWInfo->iBreak = sqlite3VdbeMakeLabel(v);
         2813  +  pWInfo->pWC = pWC = (WhereClause*)&pWInfo->a[pWInfo->nLevel];
         2814  +  pMaskSet = (WhereMaskSet*)&pWC[1];
  2292   2815   
         2816  +  /* Split the WHERE clause into separate subexpressions where each
         2817  +  ** subexpression is separated by an AND operator.
         2818  +  */
         2819  +  initMaskSet(pMaskSet);
         2820  +  whereClauseInit(pWC, pParse, pMaskSet);
         2821  +  sqlite3ExprCodeConstants(pParse, pWhere);
         2822  +  whereSplit(pWC, pWhere, TK_AND);
         2823  +    
  2293   2824     /* Special case: a WHERE clause that is constant.  Evaluate the
  2294   2825     ** expression and either jump over all of the code or fall thru.
  2295   2826     */
  2296   2827     if( pWhere && (pTabList->nSrc==0 || sqlite3ExprIsConstantNotJoin(pWhere)) ){
  2297   2828       sqlite3ExprIfFalse(pParse, pWhere, pWInfo->iBreak, SQLITE_JUMPIFNULL);
  2298   2829       pWhere = 0;
  2299   2830     }
................................................................................
  2306   2837     ** is (X-1).   An expression from the ON clause of a LEFT JOIN can use
  2307   2838     ** its Expr.iRightJoinTable value to find the bitmask of the right table
  2308   2839     ** of the join.  Subtracting one from the right table bitmask gives a
  2309   2840     ** bitmask for all tables to the left of the join.  Knowing the bitmask
  2310   2841     ** for all tables to the left of a left join is important.  Ticket #3015.
  2311   2842     */
  2312   2843     for(i=0; i<pTabList->nSrc; i++){
  2313         -    createMask(&maskSet, pTabList->a[i].iCursor);
         2844  +    createMask(pMaskSet, pTabList->a[i].iCursor);
  2314   2845     }
  2315   2846   #ifndef NDEBUG
  2316   2847     {
  2317   2848       Bitmask toTheLeft = 0;
  2318   2849       for(i=0; i<pTabList->nSrc; i++){
  2319         -      Bitmask m = getMask(&maskSet, pTabList->a[i].iCursor);
         2850  +      Bitmask m = getMask(pMaskSet, pTabList->a[i].iCursor);
  2320   2851         assert( (m-1)==toTheLeft );
  2321   2852         toTheLeft |= m;
  2322   2853       }
  2323   2854     }
  2324   2855   #endif
  2325   2856   
  2326   2857     /* Analyze all of the subexpressions.  Note that exprAnalyze() might
  2327   2858     ** add new virtual terms onto the end of the WHERE clause.  We do not
  2328   2859     ** want to analyze these virtual terms, so start analyzing at the end
  2329   2860     ** and work forward so that the added virtual terms are never processed.
  2330   2861     */
  2331         -  exprAnalyzeAll(pTabList, &wc);
         2862  +  exprAnalyzeAll(pTabList, pWC);
  2332   2863     if( db->mallocFailed ){
  2333   2864       goto whereBeginError;
  2334   2865     }
  2335   2866   
  2336   2867     /* Chose the best index to use for each table in the FROM clause.
  2337   2868     **
  2338   2869     ** This loop fills in the following fields:
................................................................................
  2339   2870     **
  2340   2871     **   pWInfo->a[].pIdx      The index to use for this level of the loop.
  2341   2872     **   pWInfo->a[].wsFlags   WHERE_xxx flags associated with pIdx
  2342   2873     **   pWInfo->a[].nEq       The number of == and IN constraints
  2343   2874     **   pWInfo->a[].iFrom     Which term of the FROM clause is being coded
  2344   2875     **   pWInfo->a[].iTabCur   The VDBE cursor for the database table
  2345   2876     **   pWInfo->a[].iIdxCur   The VDBE cursor for the index
         2877  +  **   pWInfo->a[].pTerm     When wsFlags==WO_OR, the OR-clause term
  2346   2878     **
  2347   2879     ** This loop also figures out the nesting order of tables in the FROM
  2348   2880     ** clause.
  2349   2881     */
  2350   2882     notReady = ~(Bitmask)0;
  2351   2883     pTabItem = pTabList->a;
  2352   2884     pLevel = pWInfo->a;
  2353   2885     andFlags = ~0;
  2354   2886     WHERETRACE(("*** Optimizer Start ***\n"));
  2355   2887     for(i=iFrom=0, pLevel=pWInfo->a; i<pTabList->nSrc; i++, pLevel++){
         2888  +    WhereCost bestPlan;         /* Most efficient plan seen so far */
  2356   2889       Index *pIdx;                /* Index for FROM table at pTabItem */
  2357         -    int wsFlags;                /* Flags describing scan strategy */
  2358         -    int nEq;                    /* Number of == or IN constraints */
  2359         -    double cost;                /* The cost for pIdx */
  2360   2890       int j;                      /* For looping over FROM tables */
  2361         -    Index *pBest = 0;           /* The best index seen so far */
  2362         -    int bestWsFlags = 0;        /* Flags associated with pBest */
  2363         -    int bestNEq = 0;            /* nEq associated with pBest */
  2364         -    double lowestCost;          /* Cost of the pBest */
  2365   2891       int bestJ = 0;              /* The value of j */
  2366   2892       Bitmask m;                  /* Bitmask value for j or bestJ */
  2367   2893       int once = 0;               /* True when first table is seen */
  2368         -    sqlite3_index_info *pIndex; /* Current virtual index */
  2369   2894   
  2370         -    lowestCost = SQLITE_BIG_DBL;
         2895  +    memset(&bestPlan, 0, sizeof(bestPlan));
         2896  +    bestPlan.rCost = SQLITE_BIG_DBL;
  2371   2897       for(j=iFrom, pTabItem=&pTabList->a[j]; j<pTabList->nSrc; j++, pTabItem++){
  2372   2898         int doNotReorder;  /* True if this table should not be reordered */
         2899  +      WhereCost sCost;   /* Cost information from bestIndex() */
  2373   2900   
  2374   2901         doNotReorder =  (pTabItem->jointype & (JT_LEFT|JT_CROSS))!=0;
  2375   2902         if( once && doNotReorder ) break;
  2376         -      m = getMask(&maskSet, pTabItem->iCursor);
         2903  +      m = getMask(pMaskSet, pTabItem->iCursor);
  2377   2904         if( (m & notReady)==0 ){
  2378   2905           if( j==iFrom ) iFrom++;
  2379   2906           continue;
  2380   2907         }
  2381   2908         assert( pTabItem->pTab );
  2382   2909   #ifndef SQLITE_OMIT_VIRTUALTABLE
  2383   2910         if( IsVirtual(pTabItem->pTab) ){
         2911  +        sqlite3_index_info *pVtabIdx; /* Current virtual index */
  2384   2912           sqlite3_index_info **ppIdxInfo = &pWInfo->a[j].pIdxInfo;
  2385         -        cost = bestVirtualIndex(pParse, &wc, pTabItem, notReady,
  2386         -                                ppOrderBy ? *ppOrderBy : 0, i==0,
  2387         -                                ppIdxInfo);
  2388         -        wsFlags = WHERE_VIRTUALTABLE;
  2389         -        pIndex = *ppIdxInfo;
  2390         -        if( pIndex && pIndex->orderByConsumed ){
  2391         -          wsFlags = WHERE_VIRTUALTABLE | WHERE_ORDERBY;
         2913  +        sCost.rCost = bestVirtualIndex(pParse, pWC, pTabItem, notReady,
         2914  +                                       ppOrderBy ? *ppOrderBy : 0, i==0,
         2915  +                                       ppIdxInfo);
         2916  +        sCost.plan.wsFlags = WHERE_VIRTUALTABLE;
         2917  +        sCost.plan.u.pVtabIdx = pVtabIdx = *ppIdxInfo;
         2918  +        if( pVtabIdx && pVtabIdx->orderByConsumed ){
         2919  +          sCost.plan.wsFlags = WHERE_VIRTUALTABLE | WHERE_ORDERBY;
  2392   2920           }
  2393         -        pIdx = 0;
  2394         -        nEq = 0;
  2395         -        if( (SQLITE_BIG_DBL/2.0)<cost ){
         2921  +        sCost.plan.nEq = 0;
         2922  +        if( (SQLITE_BIG_DBL/2.0)<sCost.rCost ){
  2396   2923             /* The cost is not allowed to be larger than SQLITE_BIG_DBL (the
  2397   2924             ** inital value of lowestCost in this loop. If it is, then
  2398         -          ** the (cost<lowestCost) test below will never be true and
  2399         -          ** pLevel->pBestIdx never set.
         2925  +          ** the (cost<lowestCost) test below will never be true.
  2400   2926             */ 
  2401         -          cost = (SQLITE_BIG_DBL/2.0);
         2927  +          sCost.rCost = (SQLITE_BIG_DBL/2.0);
  2402   2928           }
  2403   2929         }else 
  2404   2930   #endif
  2405   2931         {
  2406         -        cost = bestIndex(pParse, &wc, pTabItem, notReady,
  2407         -                         (i==0 && ppOrderBy) ? *ppOrderBy : 0,
  2408         -                         &pIdx, &wsFlags, &nEq);
  2409         -        pIndex = 0;
         2932  +        bestIndex(pParse, pWC, pTabItem, notReady,
         2933  +                  (i==0 && ppOrderBy) ? *ppOrderBy : 0, &sCost);
  2410   2934         }
  2411         -      if( cost<lowestCost ){
         2935  +      if( sCost.rCost<bestPlan.rCost ){
  2412   2936           once = 1;
  2413         -        lowestCost = cost;
  2414         -        pBest = pIdx;
  2415         -        bestWsFlags = wsFlags;
  2416         -        bestNEq = nEq;
         2937  +        bestPlan = sCost;
  2417   2938           bestJ = j;
  2418         -        pLevel->pBestIdx = pIndex;
  2419   2939         }
  2420   2940         if( doNotReorder ) break;
  2421   2941       }
  2422   2942       WHERETRACE(("*** Optimizer selects table %d for loop %d\n", bestJ,
  2423   2943              pLevel-pWInfo->a));
  2424         -    if( (bestWsFlags & WHERE_ORDERBY)!=0 ){
         2944  +    if( (bestPlan.plan.wsFlags & WHERE_ORDERBY)!=0 ){
  2425   2945         *ppOrderBy = 0;
  2426   2946       }
  2427         -    andFlags &= bestWsFlags;
  2428         -    pLevel->wsFlags = bestWsFlags;
  2429         -    pLevel->pIdx = pBest;
  2430         -    pLevel->nEq = bestNEq;
  2431         -    pLevel->aInLoop = 0;
  2432         -    pLevel->nIn = 0;
  2433         -    if( pBest ){
         2947  +    andFlags &= bestPlan.plan.wsFlags;
         2948  +    pLevel->plan = bestPlan.plan;
         2949  +    if( bestPlan.plan.wsFlags & WHERE_INDEXED ){
  2434   2950         pLevel->iIdxCur = pParse->nTab++;
  2435   2951       }else{
  2436   2952         pLevel->iIdxCur = -1;
  2437   2953       }
  2438         -    notReady &= ~getMask(&maskSet, pTabList->a[bestJ].iCursor);
         2954  +    notReady &= ~getMask(pMaskSet, pTabList->a[bestJ].iCursor);
  2439   2955       pLevel->iFrom = bestJ;
  2440   2956   
  2441   2957       /* Check that if the table scanned by this loop iteration had an
  2442   2958       ** INDEXED BY clause attached to it, that the named index is being
  2443   2959       ** used for the scan. If not, then query compilation has failed.
  2444   2960       ** Return an error.
  2445   2961       */
  2446   2962       pIdx = pTabList->a[bestJ].pIndex;
  2447         -    assert( !pIdx || !pBest || pIdx==pBest );
  2448         -    if( pIdx && pBest!=pIdx ){
         2963  +    assert( !pIdx
         2964  +           || (bestPlan.plan.wsFlags&WHERE_INDEXED)==0
         2965  +           || pIdx==bestPlan.plan.u.pIdx );
         2966  +    if( pIdx
         2967  +     && ((bestPlan.plan.wsFlags & WHERE_INDEXED)==0
         2968  +         || bestPlan.plan.u.pIdx!=pIdx)
         2969  +    ){
  2449   2970         sqlite3ErrorMsg(pParse, "cannot use index: %s", pIdx->zName);
  2450   2971         goto whereBeginError;
  2451   2972       }
  2452   2973     }
  2453   2974     WHERETRACE(("*** Optimizer Finished ***\n"));
  2454   2975   
  2455   2976     /* If the total query only selects a single row, then the ORDER BY
................................................................................
  2463   2984     ** to use a one-pass algorithm, determine if this is appropriate.
  2464   2985     ** The one-pass algorithm only works if the WHERE clause constraints
  2465   2986     ** the statement to update a single row.
  2466   2987     */
  2467   2988     assert( (wctrlFlags & WHERE_ONEPASS_DESIRED)==0 || pWInfo->nLevel==1 );
  2468   2989     if( (wctrlFlags & WHERE_ONEPASS_DESIRED)!=0 && (andFlags & WHERE_UNIQUE)!=0 ){
  2469   2990       pWInfo->okOnePass = 1;
  2470         -    pWInfo->a[0].wsFlags &= ~WHERE_IDX_ONLY;
         2991  +    pWInfo->a[0].plan.wsFlags &= ~WHERE_IDX_ONLY;
  2471   2992     }
  2472   2993   
  2473   2994     /* Open all tables in the pTabList and any indices selected for
  2474   2995     ** searching those tables.
  2475   2996     */
  2476   2997     sqlite3CodeVerifySchema(pParse, -1); /* Insert the cookie verifier Goto */
  2477   2998     for(i=0, pLevel=pWInfo->a; i<pTabList->nSrc; i++, pLevel++){
  2478   2999       Table *pTab;     /* Table to open */
  2479         -    Index *pIx;      /* Index used to access pTab (if any) */
  2480   3000       int iDb;         /* Index of database containing table/index */
  2481         -    int iIdxCur = pLevel->iIdxCur;
  2482   3001   
  2483   3002   #ifndef SQLITE_OMIT_EXPLAIN
  2484   3003       if( pParse->explain==2 ){
  2485   3004         char *zMsg;
  2486   3005         struct SrcList_item *pItem = &pTabList->a[pLevel->iFrom];
  2487   3006         zMsg = sqlite3MPrintf(db, "TABLE %s", pItem->zName);
  2488   3007         if( pItem->zAlias ){
  2489   3008           zMsg = sqlite3MAppendf(db, zMsg, "%s AS %s", zMsg, pItem->zAlias);
  2490   3009         }
  2491         -      if( (pIx = pLevel->pIdx)!=0 ){
  2492         -        zMsg = sqlite3MAppendf(db, zMsg, "%s WITH INDEX %s", zMsg, pIx->zName);
  2493         -      }else if( pLevel->wsFlags & (WHERE_ROWID_EQ|WHERE_ROWID_RANGE) ){
         3010  +      if( (pLevel->plan.wsFlags & WHERE_INDEXED)!=0 ){
         3011  +        zMsg = sqlite3MAppendf(db, zMsg, "%s WITH INDEX %s",
         3012  +           zMsg, pLevel->plan.u.pIdx->zName);
         3013  +      }else if( pLevel->plan.wsFlags & (WHERE_ROWID_EQ|WHERE_ROWID_RANGE) ){
  2494   3014           zMsg = sqlite3MAppendf(db, zMsg, "%s USING PRIMARY KEY", zMsg);
  2495   3015         }
  2496   3016   #ifndef SQLITE_OMIT_VIRTUALTABLE
  2497         -      else if( pLevel->pBestIdx ){
  2498         -        sqlite3_index_info *pBestIdx = pLevel->pBestIdx;
         3017  +      else if( (pLevel->plan.wsFlags & WHERE_VIRTUALTABLE)!=0 ){
         3018  +        sqlite3_index_info *pVtabIdx = pLevel->plan.u.pVtabIdx;
  2499   3019           zMsg = sqlite3MAppendf(db, zMsg, "%s VIRTUAL TABLE INDEX %d:%s", zMsg,
  2500         -                    pBestIdx->idxNum, pBestIdx->idxStr);
         3020  +                    pVtabIdx->idxNum, pVtabIdx->idxStr);
  2501   3021         }
  2502   3022   #endif
  2503         -      if( pLevel->wsFlags & WHERE_ORDERBY ){
         3023  +      if( pLevel->plan.wsFlags & WHERE_ORDERBY ){
  2504   3024           zMsg = sqlite3MAppendf(db, zMsg, "%s ORDER BY", zMsg);
  2505   3025         }
  2506   3026         sqlite3VdbeAddOp4(v, OP_Explain, i, pLevel->iFrom, 0, zMsg, P4_DYNAMIC);
  2507   3027       }
  2508   3028   #endif /* SQLITE_OMIT_EXPLAIN */
  2509   3029       pTabItem = &pTabList->a[pLevel->iFrom];
  2510   3030       pTab = pTabItem->pTab;
  2511   3031       iDb = sqlite3SchemaToIndex(pParse->db, pTab->pSchema);
  2512   3032       if( (pTab->tabFlags & TF_Ephemeral)!=0 || pTab->pSelect ) continue;
  2513   3033   #ifndef SQLITE_OMIT_VIRTUALTABLE
  2514         -    if( pLevel->pBestIdx ){
         3034  +    if( (pLevel->plan.wsFlags & WHERE_VIRTUALTABLE)!=0 ){
  2515   3035         int iCur = pTabItem->iCursor;
  2516   3036         sqlite3VdbeAddOp4(v, OP_VOpen, iCur, 0, 0,
  2517   3037                           (const char*)pTab->pVtab, P4_VTAB);
  2518   3038       }else
  2519   3039   #endif
  2520         -    if( (pLevel->wsFlags & WHERE_IDX_ONLY)==0 ){
         3040  +    if( (pLevel->plan.wsFlags & WHERE_IDX_ONLY)==0 ){
  2521   3041         int op = pWInfo->okOnePass ? OP_OpenWrite : OP_OpenRead;
  2522   3042         sqlite3OpenTable(pParse, pTabItem->iCursor, iDb, pTab, op);
  2523   3043         if( !pWInfo->okOnePass && pTab->nCol<BMS ){
  2524   3044           Bitmask b = pTabItem->colUsed;
  2525   3045           int n = 0;
  2526   3046           for(; b; b=b>>1, n++){}
  2527   3047           sqlite3VdbeChangeP2(v, sqlite3VdbeCurrentAddr(v)-2, n);
  2528   3048           assert( n<=pTab->nCol );
  2529   3049         }
  2530   3050       }else{
  2531   3051         sqlite3TableLock(pParse, iDb, pTab->tnum, 0, pTab->zName);
  2532   3052       }
  2533   3053       pLevel->iTabCur = pTabItem->iCursor;
  2534         -    if( (pIx = pLevel->pIdx)!=0 ){
         3054  +    if( (pLevel->plan.wsFlags & WHERE_INDEXED)!=0 ){
         3055  +      Index *pIx = pLevel->plan.u.pIdx;
  2535   3056         KeyInfo *pKey = sqlite3IndexKeyinfo(pParse, pIx);
         3057  +      int iIdxCur = pLevel->iIdxCur;
  2536   3058         assert( pIx->pSchema==pTab->pSchema );
         3059  +      assert( iIdxCur>=0 );
  2537   3060         sqlite3VdbeAddOp2(v, OP_SetNumColumns, 0, pIx->nColumn+1);
  2538   3061         sqlite3VdbeAddOp4(v, OP_OpenRead, iIdxCur, pIx->tnum, iDb,
  2539   3062                           (char*)pKey, P4_KEYINFO_HANDOFF);
  2540   3063         VdbeComment((v, "%s", pIx->zName));
  2541   3064       }
  2542   3065       sqlite3CodeVerifySchema(pParse, iDb);
  2543   3066     }
................................................................................
  2544   3067     pWInfo->iTop = sqlite3VdbeCurrentAddr(v);
  2545   3068   
  2546   3069     /* Generate the code to do the search.  Each iteration of the for
  2547   3070     ** loop below generates code for a single nested loop of the VM
  2548   3071     ** program.
  2549   3072     */
  2550   3073     notReady = ~(Bitmask)0;
  2551         -  for(i=0, pLevel=pWInfo->a; i<pTabList->nSrc; i++, pLevel++){
  2552         -    int j, k;
  2553         -    int iCur = pTabItem->iCursor;  /* The VDBE cursor for the table */
  2554         -    Index *pIdx;       /* The index we will be using */
  2555         -    int addrNxt;           /* Where to jump to continue with the next IN case */
  2556         -    int iIdxCur;       /* The VDBE cursor for the index */
  2557         -    int omitTable;     /* True if we use the index only */
  2558         -    int bRev;          /* True if we need to scan in reverse order */
  2559         -
  2560         -    pTabItem = &pTabList->a[pLevel->iFrom];
  2561         -    iCur = pTabItem->iCursor;
  2562         -    pIdx = pLevel->pIdx;
  2563         -    iIdxCur = pLevel->iIdxCur;
  2564         -    bRev = (pLevel->wsFlags & WHERE_REVERSE)!=0;
  2565         -    omitTable = (pLevel->wsFlags & WHERE_IDX_ONLY)!=0;
  2566         -
  2567         -    /* Create labels for the "break" and "continue" instructions
  2568         -    ** for the current loop.  Jump to addrBrk to break out of a loop.
  2569         -    ** Jump to cont to go immediately to the next iteration of the
  2570         -    ** loop.
  2571         -    **
  2572         -    ** When there is an IN operator, we also have a "addrNxt" label that
  2573         -    ** means to continue with the next IN value combination.  When
  2574         -    ** there are no IN operators in the constraints, the "addrNxt" label
  2575         -    ** is the same as "addrBrk".
  2576         -    */
  2577         -    addrBrk = pLevel->addrBrk = pLevel->addrNxt = sqlite3VdbeMakeLabel(v);
  2578         -    addrCont = pLevel->addrCont = sqlite3VdbeMakeLabel(v);
  2579         -
  2580         -    /* If this is the right table of a LEFT OUTER JOIN, allocate and
  2581         -    ** initialize a memory cell that records if this table matches any
  2582         -    ** row of the left table of the join.
  2583         -    */
  2584         -    if( pLevel->iFrom>0 && (pTabItem[0].jointype & JT_LEFT)!=0 ){
  2585         -      pLevel->iLeftJoin = ++pParse->nMem;
  2586         -      sqlite3VdbeAddOp2(v, OP_Integer, 0, pLevel->iLeftJoin);
  2587         -      VdbeComment((v, "init LEFT JOIN no-match flag"));
  2588         -    }
  2589         -
  2590         -#ifndef SQLITE_OMIT_VIRTUALTABLE
  2591         -    if( pLevel->pBestIdx ){
  2592         -      /* Case 0:  The table is a virtual-table.  Use the VFilter and VNext
  2593         -      **          to access the data.
  2594         -      */
  2595         -      int iReg;   /* P3 Value for OP_VFilter */
  2596         -      sqlite3_index_info *pBestIdx = pLevel->pBestIdx;
  2597         -      int nConstraint = pBestIdx->nConstraint;
  2598         -      struct sqlite3_index_constraint_usage *aUsage =
  2599         -                                                  pBestIdx->aConstraintUsage;
  2600         -      const struct sqlite3_index_constraint *aConstraint =
  2601         -                                                  pBestIdx->aConstraint;
  2602         -
  2603         -      iReg = sqlite3GetTempRange(pParse, nConstraint+2);
  2604         -      pParse->disableColCache++;
  2605         -      for(j=1; j<=nConstraint; j++){
  2606         -        for(k=0; k<nConstraint; k++){
  2607         -          if( aUsage[k].argvIndex==j ){
  2608         -            int iTerm = aConstraint[k].iTermOffset;
  2609         -            assert( pParse->disableColCache );
  2610         -            sqlite3ExprCode(pParse, wc.a[iTerm].pExpr->pRight, iReg+j+1);
  2611         -            break;
  2612         -          }
  2613         -        }
  2614         -        if( k==nConstraint ) break;
  2615         -      }
  2616         -      assert( pParse->disableColCache );
  2617         -      pParse->disableColCache--;
  2618         -      sqlite3VdbeAddOp2(v, OP_Integer, pBestIdx->idxNum, iReg);
  2619         -      sqlite3VdbeAddOp2(v, OP_Integer, j-1, iReg+1);
  2620         -      sqlite3VdbeAddOp4(v, OP_VFilter, iCur, addrBrk, iReg, pBestIdx->idxStr,
  2621         -                        pBestIdx->needToFreeIdxStr ? P4_MPRINTF : P4_STATIC);
  2622         -      sqlite3ReleaseTempRange(pParse, iReg, nConstraint+2);
  2623         -      pBestIdx->needToFreeIdxStr = 0;
  2624         -      for(j=0; j<nConstraint; j++){
  2625         -        if( aUsage[j].omit ){
  2626         -          int iTerm = aConstraint[j].iTermOffset;
  2627         -          disableTerm(pLevel, &wc.a[iTerm]);
  2628         -        }
  2629         -      }
  2630         -      pLevel->op = OP_VNext;
  2631         -      pLevel->p1 = iCur;
  2632         -      pLevel->p2 = sqlite3VdbeCurrentAddr(v);
  2633         -    }else
  2634         -#endif /* SQLITE_OMIT_VIRTUALTABLE */
  2635         -
  2636         -    if( pLevel->wsFlags & WHERE_ROWID_EQ ){
  2637         -      /* Case 1:  We can directly reference a single row using an
  2638         -      **          equality comparison against the ROWID field.  Or
  2639         -      **          we reference multiple rows using a "rowid IN (...)"
  2640         -      **          construct.
  2641         -      */
  2642         -      int r1;
  2643         -      int rtmp = sqlite3GetTempReg(pParse);
  2644         -      pTerm = findTerm(&wc, iCur, -1, notReady, WO_EQ|WO_IN, 0);
  2645         -      assert( pTerm!=0 );
  2646         -      assert( pTerm->pExpr!=0 );
  2647         -      assert( pTerm->leftCursor==iCur );
  2648         -      assert( omitTable==0 );
  2649         -      r1 = codeEqualityTerm(pParse, pTerm, pLevel, rtmp);
  2650         -      addrNxt = pLevel->addrNxt;
  2651         -      sqlite3VdbeAddOp2(v, OP_MustBeInt, r1, addrNxt);
  2652         -      sqlite3VdbeAddOp3(v, OP_NotExists, iCur, addrNxt, r1);
  2653         -      sqlite3ReleaseTempReg(pParse, rtmp);
  2654         -      VdbeComment((v, "pk"));
  2655         -      pLevel->op = OP_Noop;
  2656         -    }else if( pLevel->wsFlags & WHERE_ROWID_RANGE ){
  2657         -      /* Case 2:  We have an inequality comparison against the ROWID field.
  2658         -      */
  2659         -      int testOp = OP_Noop;
  2660         -      int start;
  2661         -      int memEndValue = 0;
  2662         -      WhereTerm *pStart, *pEnd;
  2663         -
  2664         -      assert( omitTable==0 );
  2665         -      pStart = findTerm(&wc, iCur, -1, notReady, WO_GT|WO_GE, 0);
  2666         -      pEnd = findTerm(&wc, iCur, -1, notReady, WO_LT|WO_LE, 0);
  2667         -      if( bRev ){
  2668         -        pTerm = pStart;
  2669         -        pStart = pEnd;
  2670         -        pEnd = pTerm;
  2671         -      }
  2672         -      if( pStart ){
  2673         -        Expr *pX;             /* The expression that defines the start bound */
  2674         -        int r1, rTemp;        /* Registers for holding the start boundary */
  2675         -
  2676         -        /* The following constant maps TK_xx codes into corresponding 
  2677         -        ** seek opcodes.  It depends on a particular ordering of TK_xx
  2678         -        */
  2679         -        const u8 aMoveOp[] = {
  2680         -             /* TK_GT */  OP_SeekGt,
  2681         -             /* TK_LE */  OP_SeekLe,
  2682         -             /* TK_LT */  OP_SeekLt,
  2683         -             /* TK_GE */  OP_SeekGe
  2684         -        };
  2685         -        assert( TK_LE==TK_GT+1 );      /* Make sure the ordering.. */
  2686         -        assert( TK_LT==TK_GT+2 );      /*  ... of the TK_xx values... */
  2687         -        assert( TK_GE==TK_GT+3 );      /*  ... is correcct. */
  2688         -
  2689         -        pX = pStart->pExpr;
  2690         -        assert( pX!=0 );
  2691         -        assert( pStart->leftCursor==iCur );
  2692         -        r1 = sqlite3ExprCodeTemp(pParse, pX->pRight, &rTemp);
  2693         -        sqlite3VdbeAddOp3(v, aMoveOp[pX->op-TK_GT], iCur, addrBrk, r1);
  2694         -        VdbeComment((v, "pk"));
  2695         -        sqlite3ExprCacheAffinityChange(pParse, r1, 1);
  2696         -        sqlite3ReleaseTempReg(pParse, rTemp);
  2697         -        disableTerm(pLevel, pStart);
  2698         -      }else{
  2699         -        sqlite3VdbeAddOp2(v, bRev ? OP_Last : OP_Rewind, iCur, addrBrk);
  2700         -      }
  2701         -      if( pEnd ){
  2702         -        Expr *pX;
  2703         -        pX = pEnd->pExpr;
  2704         -        assert( pX!=0 );
  2705         -        assert( pEnd->leftCursor==iCur );
  2706         -        memEndValue = ++pParse->nMem;
  2707         -        sqlite3ExprCode(pParse, pX->pRight, memEndValue);
  2708         -        if( pX->op==TK_LT || pX->op==TK_GT ){
  2709         -          testOp = bRev ? OP_Le : OP_Ge;
  2710         -        }else{
  2711         -          testOp = bRev ? OP_Lt : OP_Gt;
  2712         -        }
  2713         -        disableTerm(pLevel, pEnd);
  2714         -      }
  2715         -      start = sqlite3VdbeCurrentAddr(v);
  2716         -      pLevel->op = bRev ? OP_Prev : OP_Next;
  2717         -      pLevel->p1 = iCur;
  2718         -      pLevel->p2 = start;
  2719         -      if( testOp!=OP_Noop ){
  2720         -        int r1 = sqlite3GetTempReg(pParse);
  2721         -        sqlite3VdbeAddOp2(v, OP_Rowid, iCur, r1);
  2722         -        sqlite3VdbeAddOp3(v, testOp, memEndValue, addrBrk, r1);
  2723         -        sqlite3VdbeChangeP5(v, SQLITE_AFF_NUMERIC | SQLITE_JUMPIFNULL);
  2724         -        sqlite3ReleaseTempReg(pParse, r1);
  2725         -      }
  2726         -    }else if( pLevel->wsFlags & (WHERE_COLUMN_RANGE|WHERE_COLUMN_EQ) ){
  2727         -      /* Case 3: A scan using an index.
  2728         -      **
  2729         -      **         The WHERE clause may contain zero or more equality 
  2730         -      **         terms ("==" or "IN" operators) that refer to the N
  2731         -      **         left-most columns of the index. It may also contain
  2732         -      **         inequality constraints (>, <, >= or <=) on the indexed
  2733         -      **         column that immediately follows the N equalities. Only 
  2734         -      **         the right-most column can be an inequality - the rest must
  2735         -      **         use the "==" and "IN" operators. For example, if the 
  2736         -      **         index is on (x,y,z), then the following clauses are all 
  2737         -      **         optimized:
  2738         -      **
  2739         -      **            x=5
  2740         -      **            x=5 AND y=10
  2741         -      **            x=5 AND y<10
  2742         -      **            x=5 AND y>5 AND y<10
  2743         -      **            x=5 AND y=5 AND z<=10
  2744         -      **
  2745         -      **         The z<10 term of the following cannot be used, only
  2746         -      **         the x=5 term:
  2747         -      **
  2748         -      **            x=5 AND z<10
  2749         -      **
  2750         -      **         N may be zero if there are inequality constraints.
  2751         -      **         If there are no inequality constraints, then N is at
  2752         -      **         least one.
  2753         -      **
  2754         -      **         This case is also used when there are no WHERE clause
  2755         -      **         constraints but an index is selected anyway, in order
  2756         -      **         to force the output order to conform to an ORDER BY.
  2757         -      */  
  2758         -      int aStartOp[] = {
  2759         -        0,
  2760         -        0,
  2761         -        OP_Rewind,           /* 2: (!start_constraints && startEq &&  !bRev) */
  2762         -        OP_Last,             /* 3: (!start_constraints && startEq &&   bRev) */
  2763         -        OP_SeekGt,           /* 4: (start_constraints  && !startEq && !bRev) */
  2764         -        OP_SeekLt,           /* 5: (start_constraints  && !startEq &&  bRev) */
  2765         -        OP_SeekGe,           /* 6: (start_constraints  &&  startEq && !bRev) */
  2766         -        OP_SeekLe            /* 7: (start_constraints  &&  startEq &&  bRev) */
  2767         -      };
  2768         -      int aEndOp[] = {
  2769         -        OP_Noop,             /* 0: (!end_constraints) */
  2770         -        OP_IdxGE,            /* 1: (end_constraints && !bRev) */
  2771         -        OP_IdxLT             /* 2: (end_constraints && bRev) */
  2772         -      };
  2773         -      int nEq = pLevel->nEq;
  2774         -      int isMinQuery = 0;          /* If this is an optimized SELECT min(x).. */
  2775         -      int regBase;                 /* Base register holding constraint values */
  2776         -      int r1;                      /* Temp register */
  2777         -      WhereTerm *pRangeStart = 0;  /* Inequality constraint at range start */
  2778         -      WhereTerm *pRangeEnd = 0;    /* Inequality constraint at range end */
  2779         -      int startEq;                 /* True if range start uses ==, >= or <= */
  2780         -      int endEq;                   /* True if range end uses ==, >= or <= */
  2781         -      int start_constraints;       /* Start of range is constrained */
  2782         -      int nConstraint;             /* Number of constraint terms */
  2783         -      int op;
  2784         -
  2785         -      k = pIdx->aiColumn[nEq];     /* Column for inequality constraints */
  2786         -
  2787         -      /* Generate code to evaluate all constraint terms using == or IN
  2788         -      ** and store the values of those terms in an array of registers
  2789         -      ** starting at regBase.
  2790         -      */
  2791         -      regBase = codeAllEqualityTerms(pParse, pLevel, &wc, notReady, 2);
  2792         -      addrNxt = pLevel->addrNxt;
  2793         -
  2794         -      /* If this loop satisfies a sort order (pOrderBy) request that 
  2795         -      ** was passed to this function to implement a "SELECT min(x) ..." 
  2796         -      ** query, then the caller will only allow the loop to run for
  2797         -      ** a single iteration. This means that the first row returned
  2798         -      ** should not have a NULL value stored in 'x'. If column 'x' is
  2799         -      ** the first one after the nEq equality constraints in the index,
  2800         -      ** this requires some special handling.
  2801         -      */
  2802         -      if( (wctrlFlags&WHERE_ORDERBY_MIN)!=0
  2803         -       && (pLevel->wsFlags&WHERE_ORDERBY)
  2804         -       && (pIdx->nColumn>nEq)
  2805         -      ){
  2806         -        assert( pOrderBy->nExpr==1 );
  2807         -        assert( pOrderBy->a[0].pExpr->iColumn==pIdx->aiColumn[nEq] );
  2808         -        isMinQuery = 1;
  2809         -      }
  2810         -
  2811         -      /* Find any inequality constraint terms for the start and end 
  2812         -      ** of the range. 
  2813         -      */
  2814         -      if( pLevel->wsFlags & WHERE_TOP_LIMIT ){
  2815         -        pRangeEnd = findTerm(&wc, iCur, k, notReady, (WO_LT|WO_LE), pIdx);
  2816         -      }
  2817         -      if( pLevel->wsFlags & WHERE_BTM_LIMIT ){
  2818         -        pRangeStart = findTerm(&wc, iCur, k, notReady, (WO_GT|WO_GE), pIdx);
  2819         -      }
  2820         -
  2821         -      /* If we are doing a reverse order scan on an ascending index, or
  2822         -      ** a forward order scan on a descending index, interchange the 
  2823         -      ** start and end terms (pRangeStart and pRangeEnd).
  2824         -      */
  2825         -      if( bRev==(pIdx->aSortOrder[nEq]==SQLITE_SO_ASC) ){
  2826         -        SWAP(WhereTerm *, pRangeEnd, pRangeStart);
  2827         -      }
  2828         -
  2829         -      testcase( pRangeStart && pRangeStart->eOperator & WO_LE );
  2830         -      testcase( pRangeStart && pRangeStart->eOperator & WO_GE );
  2831         -      testcase( pRangeEnd && pRangeEnd->eOperator & WO_LE );
  2832         -      testcase( pRangeEnd && pRangeEnd->eOperator & WO_GE );
  2833         -      startEq = !pRangeStart || pRangeStart->eOperator & (WO_LE|WO_GE);
  2834         -      endEq =   !pRangeEnd || pRangeEnd->eOperator & (WO_LE|WO_GE);
  2835         -      start_constraints = pRangeStart || nEq>0;
  2836         -
  2837         -      /* Seek the index cursor to the start of the range. */
  2838         -      nConstraint = nEq;
  2839         -      if( pRangeStart ){
  2840         -        int dcc = pParse->disableColCache;
  2841         -        if( pRangeEnd ){
  2842         -          pParse->disableColCache++;
  2843         -        }
  2844         -        sqlite3ExprCode(pParse, pRangeStart->pExpr->pRight, regBase+nEq);
  2845         -        pParse->disableColCache = dcc;
  2846         -        sqlite3VdbeAddOp2(v, OP_IsNull, regBase+nEq, addrNxt);
  2847         -        nConstraint++;
  2848         -      }else if( isMinQuery ){
  2849         -        sqlite3VdbeAddOp2(v, OP_Null, 0, regBase+nEq);
  2850         -        nConstraint++;
  2851         -        startEq = 0;
  2852         -        start_constraints = 1;
  2853         -      }
  2854         -      codeApplyAffinity(pParse, regBase, nConstraint, pIdx);
  2855         -      op = aStartOp[(start_constraints<<2) + (startEq<<1) + bRev];
  2856         -      assert( op!=0 );
  2857         -      testcase( op==OP_Rewind );
  2858         -      testcase( op==OP_Last );
  2859         -      testcase( op==OP_SeekGt );
  2860         -      testcase( op==OP_SeekGe );
  2861         -      testcase( op==OP_SeekLe );
  2862         -      testcase( op==OP_SeekLt );
  2863         -      sqlite3VdbeAddOp4(v, op, iIdxCur, addrNxt, regBase, 
  2864         -                        SQLITE_INT_TO_PTR(nConstraint), P4_INT32);
  2865         -
  2866         -      /* Load the value for the inequality constraint at the end of the
  2867         -      ** range (if any).
  2868         -      */
  2869         -      nConstraint = nEq;
  2870         -      if( pRangeEnd ){
  2871         -        sqlite3ExprCode(pParse, pRangeEnd->pExpr->pRight, regBase+nEq);
  2872         -        sqlite3VdbeAddOp2(v, OP_IsNull, regBase+nEq, addrNxt);
  2873         -        codeApplyAffinity(pParse, regBase, nEq+1, pIdx);
  2874         -        nConstraint++;
  2875         -      }
  2876         -
  2877         -      /* Top of the loop body */
  2878         -      pLevel->p2 = sqlite3VdbeCurrentAddr(v);
  2879         -
  2880         -      /* Check if the index cursor is past the end of the range. */
  2881         -      op = aEndOp[(pRangeEnd || nEq) * (1 + bRev)];
  2882         -      testcase( op==OP_Noop );
  2883         -      testcase( op==OP_IdxGE );
  2884         -      testcase( op==OP_IdxLT );
  2885         -      sqlite3VdbeAddOp4(v, op, iIdxCur, addrNxt, regBase,
  2886         -                        SQLITE_INT_TO_PTR(nConstraint), P4_INT32);
  2887         -      sqlite3VdbeChangeP5(v, endEq!=bRev ?1:0);
  2888         -
  2889         -      /* If there are inequality constraints, check that the value
  2890         -      ** of the table column that the inequality contrains is not NULL.
  2891         -      ** If it is, jump to the next iteration of the loop.
  2892         -      */
  2893         -      r1 = sqlite3GetTempReg(pParse);
  2894         -      testcase( pLevel->wsFlags & WHERE_BTM_LIMIT );
  2895         -      testcase( pLevel->wsFlags & WHERE_TOP_LIMIT );
  2896         -      if( pLevel->wsFlags & (WHERE_BTM_LIMIT|WHERE_TOP_LIMIT) ){
  2897         -        sqlite3VdbeAddOp3(v, OP_Column, iIdxCur, nEq, r1);
  2898         -        sqlite3VdbeAddOp2(v, OP_IsNull, r1, addrCont);
  2899         -      }
  2900         -
  2901         -      /* Seek the table cursor, if required */
  2902         -      if( !omitTable ){
  2903         -        sqlite3VdbeAddOp2(v, OP_IdxRowid, iIdxCur, r1);
  2904         -        sqlite3VdbeAddOp2(v, OP_Seek, iCur, r1);  /* Deferred seek */
  2905         -      }
  2906         -      sqlite3ReleaseTempReg(pParse, r1);
  2907         -
  2908         -      /* Record the instruction used to terminate the loop. Disable 
  2909         -      ** WHERE clause terms made redundant by the index range scan.
  2910         -      */
  2911         -      pLevel->op = bRev ? OP_Prev : OP_Next;
  2912         -      pLevel->p1 = iIdxCur;
  2913         -      disableTerm(pLevel, pRangeStart);
  2914         -      disableTerm(pLevel, pRangeEnd);
  2915         -    }else if( pLevel->wsFlags & WHERE_MULTI_OR ){
  2916         -      /* Case 4:  Two or more separately indexed terms connected by OR
  2917         -      **
  2918         -      ** Example:
  2919         -      **
  2920         -      **   CREATE TABLE t1(a,b,c,d);
  2921         -      **   CREATE INDEX i1 ON t1(a);
  2922         -      **   CREATE INDEX i2 ON t1(b);
  2923         -      **   CREATE INDEX i3 ON t1(c);
  2924         -      **
  2925         -      **   SELECT * FROM t1 WHERE a=5 OR b=7 OR (c=11 AND d=13)
  2926         -      **
  2927         -      ** In the example, there are three indexed terms connected by OR.
  2928         -      ** The top of the loop is constructed by creating a RowSet object
  2929         -      ** and populating it.  Then looping over elements of the rowset.
  2930         -      **
  2931         -      **        Null 1
  2932         -      **        # fill RowSet 1 with entries where a=5 using i1
  2933         -      **        # fill Rowset 1 with entries where b=7 using i2
  2934         -      **        # fill Rowset 1 with entries where c=11 and d=13 i3 and t1
  2935         -      **     A: RowSetRead 1, B, 2
  2936         -      **        Seek       i, 2
  2937         -      **
  2938         -      ** The bottom of the loop looks like this:
  2939         -      **
  2940         -      **     C: Goto       0, A
  2941         -      **     B:
  2942         -      */
  2943         -    }else{
  2944         -      /* Case 5:  There is no usable index.  We must do a complete
  2945         -      **          scan of the entire table.
  2946         -      */
  2947         -      assert( omitTable==0 );
  2948         -      assert( bRev==0 );
  2949         -      pLevel->op = OP_Next;
  2950         -      pLevel->p1 = iCur;
  2951         -      pLevel->p2 = 1 + sqlite3VdbeAddOp2(v, OP_Rewind, iCur, addrBrk);
  2952         -      pLevel->p5 = SQLITE_STMTSTATUS_FULLSCAN_STEP;
  2953         -    }
  2954         -    notReady &= ~getMask(&maskSet, iCur);
  2955         -
  2956         -    /* Insert code to test every subexpression that can be completely
  2957         -    ** computed using the current set of tables.
  2958         -    */
  2959         -    k = 0;
  2960         -    for(pTerm=wc.a, j=wc.nTerm; j>0; j--, pTerm++){
  2961         -      Expr *pE;
  2962         -      testcase( pTerm->wtFlags & TERM_VIRTUAL );
  2963         -      testcase( pTerm->wtFlags & TERM_CODED );
  2964         -      if( pTerm->wtFlags & (TERM_VIRTUAL|TERM_CODED) ) continue;
  2965         -      if( (pTerm->prereqAll & notReady)!=0 ) continue;
  2966         -      pE = pTerm->pExpr;
  2967         -      assert( pE!=0 );
  2968         -      if( pLevel->iLeftJoin && !ExprHasProperty(pE, EP_FromJoin) ){
  2969         -        continue;
  2970         -      }
  2971         -      pParse->disableColCache += k;
  2972         -      sqlite3ExprIfFalse(pParse, pE, addrCont, SQLITE_JUMPIFNULL);
  2973         -      pParse->disableColCache -= k;
  2974         -      k = 1;
  2975         -      pTerm->wtFlags |= TERM_CODED;
  2976         -    }
  2977         -
  2978         -    /* For a LEFT OUTER JOIN, generate code that will record the fact that
  2979         -    ** at least one row of the right table has matched the left table.  
  2980         -    */
  2981         -    if( pLevel->iLeftJoin ){
  2982         -      pLevel->addrFirst = sqlite3VdbeCurrentAddr(v);
  2983         -      sqlite3VdbeAddOp2(v, OP_Integer, 1, pLevel->iLeftJoin);
  2984         -      VdbeComment((v, "record LEFT JOIN hit"));
  2985         -      sqlite3ExprClearColumnCache(pParse, pLevel->iTabCur);
  2986         -      sqlite3ExprClearColumnCache(pParse, pLevel->iIdxCur);
  2987         -      for(pTerm=wc.a, j=0; j<wc.nTerm; j++, pTerm++){
  2988         -        testcase( pTerm->wtFlags & TERM_VIRTUAL );
  2989         -        testcase( pTerm->wtFlags & TERM_CODED );
  2990         -        if( pTerm->wtFlags & (TERM_VIRTUAL|TERM_CODED) ) continue;
  2991         -        if( (pTerm->prereqAll & notReady)!=0 ) continue;
  2992         -        assert( pTerm->pExpr );
  2993         -        sqlite3ExprIfFalse(pParse, pTerm->pExpr, addrCont, SQLITE_JUMPIFNULL);
  2994         -        pTerm->wtFlags |= TERM_CODED;
  2995         -      }
  2996         -    }
         3074  +  for(i=0; i<pTabList->nSrc; i++){
         3075  +    notReady = codeOneLoopStart(pWInfo, i, wctrlFlags, notReady);
  2997   3076     }
         3077  +  pWInfo->iContinue = pWInfo->a[i-1].addrCont;
  2998   3078   
  2999   3079   #ifdef SQLITE_TEST  /* For testing and debugging use only */
  3000   3080     /* Record in the query plan information about the current table
  3001   3081     ** and the index used to access it (if any).  If the table itself
  3002   3082     ** is not used, its name is just '{}'.  If no index is used
  3003   3083     ** the index is listed as "{}".  If the primary key is used the
  3004   3084     ** index name is '*'.
................................................................................
  3008   3088       int n;
  3009   3089       pLevel = &pWInfo->a[i];
  3010   3090       pTabItem = &pTabList->a[pLevel->iFrom];
  3011   3091       z = pTabItem->zAlias;
  3012   3092       if( z==0 ) z = pTabItem->pTab->zName;
  3013   3093       n = sqlite3Strlen30(z);
  3014   3094       if( n+nQPlan < sizeof(sqlite3_query_plan)-10 ){
  3015         -      if( pLevel->wsFlags & WHERE_IDX_ONLY ){
         3095  +      if( pLevel->plan.wsFlags & WHERE_IDX_ONLY ){
  3016   3096           memcpy(&sqlite3_query_plan[nQPlan], "{}", 2);
  3017   3097           nQPlan += 2;
  3018   3098         }else{
  3019   3099           memcpy(&sqlite3_query_plan[nQPlan], z, n);
  3020   3100           nQPlan += n;
  3021   3101         }
  3022   3102         sqlite3_query_plan[nQPlan++] = ' ';
  3023   3103       }
  3024         -    testcase( pLevel->wsFlags & WHERE_ROWID_EQ );
  3025         -    testcase( pLevel->wsFlags & WHERE_ROWID_RANGE );
  3026         -    if( pLevel->wsFlags & (WHERE_ROWID_EQ|WHERE_ROWID_RANGE) ){
         3104  +    testcase( pLevel->plan.wsFlags & WHERE_ROWID_EQ );
         3105  +    testcase( pLevel->plan.wsFlags & WHERE_ROWID_RANGE );
         3106  +    if( pLevel->plan.wsFlags & (WHERE_ROWID_EQ|WHERE_ROWID_RANGE) ){
  3027   3107         memcpy(&sqlite3_query_plan[nQPlan], "* ", 2);
  3028   3108         nQPlan += 2;
  3029         -    }else if( pLevel->pIdx==0 ){
  3030         -      memcpy(&sqlite3_query_plan[nQPlan], "{} ", 3);
  3031         -      nQPlan += 3;
  3032         -    }else{
  3033         -      n = sqlite3Strlen30(pLevel->pIdx->zName);
         3109  +    }else if( (pLevel->plan.wsFlags & WHERE_INDEXED)!=0 ){
         3110  +      n = sqlite3Strlen30(pLevel->plan.u.pIdx->zName);
  3034   3111         if( n+nQPlan < sizeof(sqlite3_query_plan)-2 ){
  3035         -        memcpy(&sqlite3_query_plan[nQPlan], pLevel->pIdx->zName, n);
         3112  +        memcpy(&sqlite3_query_plan[nQPlan], pLevel->plan.u.pIdx->zName, n);
  3036   3113           nQPlan += n;
  3037   3114           sqlite3_query_plan[nQPlan++] = ' ';
  3038   3115         }
         3116  +    }else{
         3117  +      memcpy(&sqlite3_query_plan[nQPlan], "{} ", 3);
         3118  +      nQPlan += 3;
  3039   3119       }
  3040   3120     }
  3041   3121     while( nQPlan>0 && sqlite3_query_plan[nQPlan-1]==' ' ){
  3042   3122       sqlite3_query_plan[--nQPlan] = 0;
  3043   3123     }
  3044   3124     sqlite3_query_plan[nQPlan] = 0;
  3045   3125     nQPlan = 0;
  3046   3126   #endif /* SQLITE_TEST // Testing and debugging use only */
  3047   3127   
  3048   3128     /* Record the continuation address in the WhereInfo structure.  Then
  3049   3129     ** clean up and return.
  3050   3130     */
  3051         -  pWInfo->iContinue = addrCont;
  3052         -  whereClauseClear(&wc);
  3053   3131     return pWInfo;
  3054   3132   
  3055   3133     /* Jump here if malloc fails */
  3056   3134   whereBeginError:
  3057         -  whereClauseClear(&wc);
  3058   3135     whereInfoFree(db, pWInfo);
  3059   3136     return 0;
  3060   3137   }
  3061   3138   
  3062   3139   /*
  3063   3140   ** Generate the end of the WHERE loop.  See comments on 
  3064   3141   ** sqlite3WhereBegin() for additional information.
................................................................................
  3077   3154     for(i=pTabList->nSrc-1; i>=0; i--){
  3078   3155       pLevel = &pWInfo->a[i];
  3079   3156       sqlite3VdbeResolveLabel(v, pLevel->addrCont);
  3080   3157       if( pLevel->op!=OP_Noop ){
  3081   3158         sqlite3VdbeAddOp2(v, pLevel->op, pLevel->p1, pLevel->p2);
  3082   3159         sqlite3VdbeChangeP5(v, pLevel->p5);
  3083   3160       }
  3084         -    if( pLevel->nIn ){
         3161  +    if( pLevel->plan.wsFlags & WHERE_IN_ABLE && pLevel->u.in.nIn>0 ){
  3085   3162         struct InLoop *pIn;
  3086   3163         int j;
  3087   3164         sqlite3VdbeResolveLabel(v, pLevel->addrNxt);
  3088         -      for(j=pLevel->nIn, pIn=&pLevel->aInLoop[j-1]; j>0; j--, pIn--){
         3165  +      for(j=pLevel->u.in.nIn, pIn=&pLevel->u.in.aInLoop[j-1]; j>0; j--, pIn--){
  3089   3166           sqlite3VdbeJumpHere(v, pIn->addrInTop+1);
  3090   3167           sqlite3VdbeAddOp2(v, OP_Next, pIn->iCur, pIn->addrInTop);
  3091   3168           sqlite3VdbeJumpHere(v, pIn->addrInTop-1);
  3092   3169         }
  3093         -      sqlite3DbFree(db, pLevel->aInLoop);
         3170  +      sqlite3DbFree(db, pLevel->u.in.aInLoop);
  3094   3171       }
  3095   3172       sqlite3VdbeResolveLabel(v, pLevel->addrBrk);
  3096   3173       if( pLevel->iLeftJoin ){
  3097   3174         int addr;
  3098   3175         addr = sqlite3VdbeAddOp1(v, OP_IfPos, pLevel->iLeftJoin);
  3099   3176         sqlite3VdbeAddOp1(v, OP_NullRow, pTabList->a[i].iCursor);
  3100   3177         if( pLevel->iIdxCur>=0 ){
................................................................................
  3113   3190     /* Close all of the cursors that were opened by sqlite3WhereBegin.
  3114   3191     */
  3115   3192     for(i=0, pLevel=pWInfo->a; i<pTabList->nSrc; i++, pLevel++){
  3116   3193       struct SrcList_item *pTabItem = &pTabList->a[pLevel->iFrom];
  3117   3194       Table *pTab = pTabItem->pTab;
  3118   3195       assert( pTab!=0 );
  3119   3196       if( (pTab->tabFlags & TF_Ephemeral)!=0 || pTab->pSelect ) continue;
  3120         -    if( !pWInfo->okOnePass && (pLevel->wsFlags & WHERE_IDX_ONLY)==0 ){
         3197  +    if( !pWInfo->okOnePass && (pLevel->plan.wsFlags & WHERE_IDX_ONLY)==0 ){
  3121   3198         sqlite3VdbeAddOp1(v, OP_Close, pTabItem->iCursor);
  3122   3199       }
  3123         -    if( pLevel->pIdx!=0 ){
         3200  +    if( (pLevel->plan.wsFlags & WHERE_INDEXED)!=0 ){
  3124   3201         sqlite3VdbeAddOp1(v, OP_Close, pLevel->iIdxCur);
  3125   3202       }
  3126   3203   
  3127   3204       /* If this scan uses an index, make code substitutions to read data
  3128   3205       ** from the index in preference to the table. Sometimes, this means
  3129   3206       ** the table need never be read from. This is a performance boost,
  3130   3207       ** as the vdbe level waits until the table is read before actually
................................................................................
  3133   3210       ** 
  3134   3211       ** Calls to the code generator in between sqlite3WhereBegin and
  3135   3212       ** sqlite3WhereEnd will have created code that references the table
  3136   3213       ** directly.  This loop scans all that code looking for opcodes
  3137   3214       ** that reference the table and converts them into opcodes that
  3138   3215       ** reference the index.
  3139   3216       */
  3140         -    if( pLevel->pIdx ){
         3217  +    if( (pLevel->plan.wsFlags & WHERE_INDEXED)!=0 ){
  3141   3218         int k, j, last;
  3142   3219         VdbeOp *pOp;
  3143         -      Index *pIdx = pLevel->pIdx;
  3144         -      int useIndexOnly = pLevel->wsFlags & WHERE_IDX_ONLY;
         3220  +      Index *pIdx = pLevel->plan.u.pIdx;
         3221  +      int useIndexOnly = pLevel->plan.wsFlags & WHERE_IDX_ONLY;
  3145   3222   
  3146   3223         assert( pIdx!=0 );
  3147   3224         pOp = sqlite3VdbeGetOp(v, pWInfo->iTop);
  3148   3225         last = sqlite3VdbeCurrentAddr(v);
  3149   3226         for(k=pWInfo->iTop; k<last; k++, pOp++){
  3150   3227           if( pOp->p1!=pLevel->iTabCur ) continue;
  3151   3228           if( pOp->opcode==OP_Column ){