/ Check-in [78401b33]
Login

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

Overview
Comment:Update the WHERE clause processing infrastructure in preparation for adding multi-index OR evaluation. (CVS 6037)
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1: 78401b33febf678cfeec2a35514eb4172de420ab
User & Date: drh 2008-12-17 19:22:16
Context
2008-12-18
05:30
Fix a bug in icuOpen() in fts2. (CVS 6038) check-in: b9c722bd user: danielk1977 tags: trunk
2008-12-17
19:22
Update the WHERE clause processing infrastructure in preparation for adding multi-index OR evaluation. (CVS 6037) check-in: 78401b33 user: drh tags: trunk
17:30
Add the savepoint feature. This feature is largely untested at this point. (CVS 6036) check-in: 34b56600 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.810 2008/12/17 17:30:26 danielk1977 Exp $
           14  +** @(#) $Id: sqliteInt.h,v 1.811 2008/12/17 19:22: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
................................................................................
  1535   1535   ** for WhereInfo.pTabList.a[i].  WhereInfo.a[i].pBestInfo is the
  1536   1536   ** index information for the i-th loop of the join.  pBestInfo is always
  1537   1537   ** either NULL or a copy of some pIdxInfo.  So for cleanup it is 
  1538   1538   ** sufficient to free all of the pIdxInfo pointers.
  1539   1539   ** 
  1540   1540   */
  1541   1541   struct WhereLevel {
  1542         -  int iFrom;            /* Which entry in the FROM clause */
  1543         -  int wsFlags;          /* "Where-Scan" flags show the choosen scan strategy */
  1544         -  int iMem;             /* First memory cell used by this level */
         1542  +  u32 wsFlags;          /* "Where-Scan" flags show the choosen scan strategy */
  1545   1543     int iLeftJoin;        /* Memory cell used to implement LEFT OUTER JOIN */
  1546   1544     Index *pIdx;          /* Index used.  NULL if no index */
         1545  +  struct WhereTerm *pTerm; /* Where term containing OR clause */
  1547   1546     int iTabCur;          /* The VDBE cursor used to access the table */
  1548   1547     int iIdxCur;          /* The VDBE cursor used to access pIdx */
  1549   1548     int addrBrk;          /* Jump here to break out of the loop */
  1550   1549     int addrNxt;          /* Jump here to start the next IN combination */
  1551   1550     int addrCont;         /* Jump here to continue with the next loop cycle */
  1552   1551     int addrFirst;        /* First instruction of interior of the loop */
  1553   1552     int op, p1, p2;       /* Opcode used to terminate the loop */
  1554   1553     u8 p5;                /* P5 operand of the opcode that terminates the loop */
  1555         -  int nEq;              /* Number of == or IN constraints on this loop */
  1556         -  int nIn;              /* Number of IN operators constraining this loop */
         1554  +  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   1557     struct InLoop {
  1558   1558       int iCur;              /* The VDBE cursor used by this IN operator */
  1559   1559       int addrInTop;         /* Top of the IN loop */
  1560   1560     } *aInLoop;           /* Information about each nested IN operator */
  1561   1561     sqlite3_index_info *pBestIdx;  /* Index information for this level */
  1562   1562   
  1563   1563     /* The following field is really not part of the current level.  But

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.337 2008/12/12 17:56:16 drh Exp $
           19  +** $Id: where.c,v 1.338 2008/12/17 19:22: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)
................................................................................
    32     32   # define WHERETRACE(X)
    33     33   #endif
    34     34   
    35     35   /* Forward reference
    36     36   */
    37     37   typedef struct WhereClause WhereClause;
    38     38   typedef struct ExprMaskSet ExprMaskSet;
           39  +typedef struct WhereOrInfo WhereOrInfo;
           40  +typedef struct WhereAndInfo WhereAndInfo;
    39     41   
    40     42   /*
    41     43   ** The query generator uses an array of instances of this structure to
    42     44   ** help it analyze the subexpressions of the WHERE clause.  Each WHERE
    43     45   ** clause subexpression is separated from the others by AND operators.
    44     46   ** (Note: the same data structure is also reused to hold a group of terms
    45     47   ** separated by OR operators.  But at the top-level, everything is AND
................................................................................
    51     53   **        WhereTerm.pWC->a[WhereTerm.idx] == WhereTerm
    52     54   **
    53     55   ** When a term is of the form:
    54     56   **
    55     57   **              X <op> <expr>
    56     58   **
    57     59   ** where X is a column name and <op> is one of certain operators,
    58         -** then WhereTerm.leftCursor and WhereTerm.leftColumn record the
    59         -** cursor number and column number for X.  WhereTerm.operator records
           60  +** then WhereTerm.leftCursor and WhereTerm.u.leftColumn record the
           61  +** cursor number and column number for X.  WhereTerm.eOperator records
    60     62   ** the <op> using a bitmask encoding defined by WO_xxx below.  The
    61     63   ** use of a bitmask encoding for the operator allows us to search
    62     64   ** quickly for terms that match any of several different operators.
    63     65   **
    64         -** prereqRight and prereqAll record sets of cursor numbers,
           66  +** A WhereTerm might also be two or more subterms connected by OR:
           67  +**
           68  +**         (t1.X <op> <expr>) OR (t1.Y <op> <expr>) OR ....
           69  +**
           70  +** In this second case, wtFlag as the TERM_ORINFO set and eOperator==WO_OR
           71  +** and the WhereTerm.u.pOrInfo field points to auxiliary information that
           72  +** is collected about the
           73  +**
           74  +** If a term in the WHERE clause does not match either of the two previous
           75  +** categories, then eOperator==0.  The WhereTerm.pExpr field is still set
           76  +** to the original subexpression content and wtFlags is set up appropriately
           77  +** but no other fields in the WhereTerm object are meaningful.
           78  +**
           79  +** When eOperator!=0, prereqRight and prereqAll record sets of cursor numbers,
    65     80   ** but they do so indirectly.  A single ExprMaskSet structure translates
    66     81   ** cursor number into bits and the translated bit is stored in the prereq
    67     82   ** fields.  The translation is used in order to maximize the number of
    68     83   ** bits that will fit in a Bitmask.  The VDBE cursor numbers might be
    69     84   ** spread out over the non-negative integers.  For example, the cursor
    70     85   ** numbers might be 3, 8, 9, 10, 20, 23, 41, and 45.  The ExprMaskSet
    71     86   ** translates these sparse cursor numbers into consecutive integers
................................................................................
    78     93   ** is only able to process joins with 64 or fewer tables.
    79     94   */
    80     95   typedef struct WhereTerm WhereTerm;
    81     96   struct WhereTerm {
    82     97     Expr *pExpr;            /* Pointer to the subexpression that is this term */
    83     98     int iParent;            /* Disable pWC->a[iParent] when this term disabled */
    84     99     int leftCursor;         /* Cursor number of X in "X <op> <expr>" */
    85         -  int leftColumn;         /* Column number of X in "X <op> <expr>" */
          100  +  union {
          101  +    int leftColumn;         /* Column number of X in "X <op> <expr>" */
          102  +    WhereOrInfo *pOrInfo;   /* Extra information if eOperator==WO_OR */
          103  +    WhereAndInfo *pAndInfo; /* Extra information if eOperator==WO_AND */
          104  +  } u;
    86    105     u16 eOperator;          /* A WO_xx value describing <op> */
    87    106     u8 wtFlags;             /* TERM_xxx bit flags.  See below */
    88    107     u8 nChild;              /* Number of children that must disable us */
    89    108     WhereClause *pWC;       /* The clause this term is part of */
    90    109     Bitmask prereqRight;    /* Bitmask of tables used by pExpr->pRight */
    91    110     Bitmask prereqAll;      /* Bitmask of tables referenced by pExpr */
    92    111   };
................................................................................
    94    113   /*
    95    114   ** Allowed values of WhereTerm.wtFlags
    96    115   */
    97    116   #define TERM_DYNAMIC    0x01   /* Need to call sqlite3ExprDelete(db, pExpr) */
    98    117   #define TERM_VIRTUAL    0x02   /* Added by the optimizer.  Do not code */
    99    118   #define TERM_CODED      0x04   /* This term is already coded */
   100    119   #define TERM_COPIED     0x08   /* Has a child */
   101         -#define TERM_OR_OK      0x10   /* Used during OR-clause processing */
          120  +#define TERM_ORINFO     0x10   /* Need to free the WhereTerm.u.pOrInfo object */
          121  +#define TERM_ANDINFO    0x20   /* Need to free the WhereTerm.u.pAndInfo obj */
          122  +#define TERM_OR_OK      0x40   /* Used during OR-clause processing */
   102    123   
   103    124   /*
   104    125   ** An instance of the following structure holds all information about a
   105    126   ** WHERE clause.  Mostly this is a container for one or more WhereTerms.
   106    127   */
   107    128   struct WhereClause {
   108    129     Parse *pParse;           /* The parser context */
   109    130     ExprMaskSet *pMaskSet;   /* Mapping of table indices to bitmasks */
   110    131     int nTerm;               /* Number of terms */
   111    132     int nSlot;               /* Number of entries in a[] */
   112    133     WhereTerm *a;            /* Each a[] describes a term of the WHERE cluase */
   113    134     WhereTerm aStatic[4];    /* Initial static space for a[] */
   114    135   };
          136  +
          137  +/*
          138  +** A WhereTerm with eOperator==WO_OR has its u.pOrInfo pointer set to
          139  +** a dynamically allocated instance of the following structure.
          140  +*/
          141  +struct WhereOrInfo {
          142  +  WhereClause wc;          /* The OR subexpression broken out */
          143  +  double cost;             /* Cost of evaluating this OR subexpression */
          144  +};
          145  +
          146  +/*
          147  +** A WhereTerm with eOperator==WO_AND has its u.pAndInfo pointer set to
          148  +** a dynamically allocated instance of the following structure.
          149  +*/
          150  +struct WhereAndInfo {
          151  +  WhereClause wc;          /* The OR subexpression broken out */
          152  +  Index *pIdx;             /* Index to use */
          153  +  double cost;             /* Cost of evaluating this OR subexpression */
          154  +};
   115    155   
   116    156   /*
   117    157   ** An instance of the following structure keeps track of a mapping
   118    158   ** between VDBE cursor numbers and bits of the bitmasks in WhereTerm.
   119    159   **
   120    160   ** The VDBE cursor numbers are small integers contained in 
   121    161   ** SrcList_item.iCursor and Expr.iTable fields.  For any given WHERE 
................................................................................
   154    194   #define WO_EQ     0x002
   155    195   #define WO_LT     (WO_EQ<<(TK_LT-TK_EQ))
   156    196   #define WO_LE     (WO_EQ<<(TK_LE-TK_EQ))
   157    197   #define WO_GT     (WO_EQ<<(TK_GT-TK_EQ))
   158    198   #define WO_GE     (WO_EQ<<(TK_GE-TK_EQ))
   159    199   #define WO_MATCH  0x040
   160    200   #define WO_ISNULL 0x080
   161         -#define WO_OR     0x100
          201  +#define WO_OR     0x100       /* Two or more OR-connected terms */
          202  +#define WO_AND    0x200       /* Two or more AND-connected terms */
   162    203   
   163    204   #define WO_ALL    0xfff       /* Mask of all possible WO_* values */
   164    205   
   165    206   /*
   166         -** Value for wsFlags returned by bestIndex().  These flags determine which
   167         -** search strategies are appropriate.
          207  +** Value for wsFlags returned by bestIndex() and stored in
          208  +** WhereLevel.wsFlags.  These flags determine which search
          209  +** strategies are appropriate.
   168    210   **
   169    211   ** The least significant 12 bits is reserved as a mask for WO_ values above.
   170         -** The WhereLevel.wtFlags field is usually set to WO_IN|WO_EQ|WO_ISNULL.
   171         -** But if the table is the right table of a left join, WhereLevel.wtFlags
   172         -** is set to WO_IN|WO_EQ.  The WhereLevel.wtFlags field can then be used as
          212  +** The WhereLevel.wsFlags field is usually set to WO_IN|WO_EQ|WO_ISNULL.
          213  +** But if the table is the right table of a left join, WhereLevel.wsFlags
          214  +** is set to WO_IN|WO_EQ.  The WhereLevel.wsFlags field can then be used as
   173    215   ** the "op" parameter to findTerm when we are resolving equality constraints.
   174    216   ** ISNULL constraints will then not be used on the right table of a left
   175    217   ** join.  Tickets #2177 and #2189.
   176    218   */
   177    219   #define WHERE_ROWID_EQ     0x00001000  /* rowid=EXPR or rowid IN (...) */
   178    220   #define WHERE_ROWID_RANGE  0x00002000  /* rowid<EXPR and/or rowid>EXPR */
   179    221   #define WHERE_COLUMN_EQ    0x00010000  /* x=EXPR or x IN (...) */
................................................................................
   198    240   ){
   199    241     pWC->pParse = pParse;
   200    242     pWC->pMaskSet = pMaskSet;
   201    243     pWC->nTerm = 0;
   202    244     pWC->nSlot = ArraySize(pWC->aStatic);
   203    245     pWC->a = pWC->aStatic;
   204    246   }
          247  +
          248  +/* Forward reference */
          249  +static void whereClauseClear(WhereClause*);
          250  +
          251  +/*
          252  +** Deallocate all memory associated with a WhereOrInfo object.
          253  +*/
          254  +static void whereOrInfoDelete(sqlite3 *db, WhereOrInfo *p){
          255  +  if( p ){
          256  +    whereClauseClear(&p->wc);
          257  +  }
          258  +}
          259  +
          260  +/*
          261  +** Deallocate all memory associated with a WhereAndInfo object.
          262  +*/
          263  +static void whereAndInfoDelete(sqlite3 *db, WhereAndInfo *p){
          264  +  if( p ){
          265  +    whereClauseClear(&p->wc);
          266  +  }
          267  +}
   205    268   
   206    269   /*
   207    270   ** Deallocate a WhereClause structure.  The WhereClause structure
   208    271   ** itself is not freed.  This routine is the inverse of whereClauseInit().
   209    272   */
   210    273   static void whereClauseClear(WhereClause *pWC){
   211    274     int i;
   212    275     WhereTerm *a;
   213    276     sqlite3 *db = pWC->pParse->db;
   214    277     for(i=pWC->nTerm-1, a=pWC->a; i>=0; i--, a++){
   215    278       if( a->wtFlags & TERM_DYNAMIC ){
   216    279         sqlite3ExprDelete(db, a->pExpr);
   217    280       }
          281  +    if( a->wtFlags & TERM_ORINFO ){
          282  +      whereOrInfoDelete(db, a->u.pOrInfo);
          283  +    }else if( a->wtFlags & TERM_ANDINFO ){
          284  +      whereAndInfoDelete(db, a->u.pAndInfo);
          285  +    }
   218    286     }
   219    287     if( pWC->a!=pWC->aStatic ){
   220    288       sqlite3DbFree(db, pWC->a);
   221    289     }
   222    290   }
   223    291   
   224    292   /*
................................................................................
   473    541     WhereTerm *pTerm;
   474    542     int k;
   475    543     assert( iCur>=0 );
   476    544     op &= WO_ALL;
   477    545     for(pTerm=pWC->a, k=pWC->nTerm; k; k--, pTerm++){
   478    546       if( pTerm->leftCursor==iCur
   479    547          && (pTerm->prereqRight & notReady)==0
   480         -       && pTerm->leftColumn==iColumn
          548  +       && pTerm->u.leftColumn==iColumn
   481    549          && (pTerm->eOperator & op)!=0
   482    550       ){
   483    551         if( pIdx && pTerm->eOperator!=WO_ISNULL ){
   484    552           Expr *pX = pTerm->pExpr;
   485    553           CollSeq *pColl;
   486    554           char idxaff;
   487    555           int j;
................................................................................
   662    730   */
   663    731   static int orTermIsOptCandidate(WhereTerm *pOrTerm, int iCursor, int iColumn){
   664    732     int affLeft, affRight;
   665    733     assert( pOrTerm->eOperator==WO_EQ );
   666    734     if( pOrTerm->leftCursor!=iCursor ){
   667    735       return 0;
   668    736     }
   669         -  if( pOrTerm->leftColumn!=iColumn ){
          737  +  if( pOrTerm->u.leftColumn!=iColumn ){
   670    738       return 0;
   671    739     }
   672    740     affRight = sqlite3ExprAffinity(pOrTerm->pExpr->pRight);
   673    741     if( affRight==0 ){
   674    742       return 1;
   675    743     }
   676    744     affLeft = sqlite3ExprAffinity(pOrTerm->pExpr->pLeft);
................................................................................
   781    849     pTerm->iParent = -1;
   782    850     pTerm->eOperator = 0;
   783    851     if( allowedOp(op) && (pTerm->prereqRight & prereqLeft)==0 ){
   784    852       Expr *pLeft = pExpr->pLeft;
   785    853       Expr *pRight = pExpr->pRight;
   786    854       if( pLeft->op==TK_COLUMN ){
   787    855         pTerm->leftCursor = pLeft->iTable;
   788         -      pTerm->leftColumn = pLeft->iColumn;
          856  +      pTerm->u.leftColumn = pLeft->iColumn;
   789    857         pTerm->eOperator = operatorMask(op);
   790    858       }
   791    859       if( pRight && pRight->op==TK_COLUMN ){
   792    860         WhereTerm *pNew;
   793    861         Expr *pDup;
   794    862         if( pTerm->leftCursor>=0 ){
   795    863           int idxNew;
................................................................................
   808    876         }else{
   809    877           pDup = pExpr;
   810    878           pNew = pTerm;
   811    879         }
   812    880         exprCommute(pParse, pDup);
   813    881         pLeft = pDup->pLeft;
   814    882         pNew->leftCursor = pLeft->iTable;
   815         -      pNew->leftColumn = pLeft->iColumn;
          883  +      pNew->u.leftColumn = pLeft->iColumn;
   816    884         pNew->prereqRight = prereqLeft;
   817    885         pNew->prereqAll = prereqAll;
   818    886         pNew->eOperator = operatorMask(pDup->op);
   819    887       }
   820    888     }
   821    889   
   822    890   #ifndef SQLITE_OMIT_BETWEEN_OPTIMIZATION
................................................................................
   869    937       whereSplit(&sOr, pExpr, TK_OR);
   870    938       exprAnalyzeAll(pSrc, &sOr);
   871    939       assert( sOr.nTerm>=2 );
   872    940       j = 0;
   873    941       if( db->mallocFailed ) goto or_not_possible;
   874    942       do{
   875    943         assert( j<sOr.nTerm );
   876         -      iColumn = sOr.a[j].leftColumn;
          944  +      iColumn = sOr.a[j].u.leftColumn;
   877    945         iCursor = sOr.a[j].leftCursor;
   878    946         ok = iCursor>=0;
   879    947         for(i=sOr.nTerm-1, pOrTerm=sOr.a; i>=0 && ok; i--, pOrTerm++){
   880    948           if( pOrTerm->eOperator!=WO_EQ ){
   881    949             goto or_not_possible;
   882    950           }
   883    951           if( orTermIsOptCandidate(pOrTerm, iCursor, iColumn) ){
................................................................................
   996   1064         Expr *pNewExpr;
   997   1065         pNewExpr = sqlite3Expr(db, TK_MATCH, 0, sqlite3ExprDup(db, pRight), 0);
   998   1066         idxNew = whereClauseInsert(pWC, pNewExpr, TERM_VIRTUAL|TERM_DYNAMIC);
   999   1067         testcase( idxNew==0 );
  1000   1068         pNewTerm = &pWC->a[idxNew];
  1001   1069         pNewTerm->prereqRight = prereqExpr;
  1002   1070         pNewTerm->leftCursor = pLeft->iTable;
  1003         -      pNewTerm->leftColumn = pLeft->iColumn;
         1071  +      pNewTerm->u.leftColumn = pLeft->iColumn;
  1004   1072         pNewTerm->eOperator = WO_MATCH;
  1005   1073         pNewTerm->iParent = idxTerm;
  1006   1074         pTerm = &pWC->a[idxTerm];
  1007   1075         pTerm->nChild = 1;
  1008   1076         pTerm->wtFlags |= TERM_COPIED;
  1009   1077         pNewTerm->prereqAll = pTerm->prereqAll;
  1010   1078       }
................................................................................
  1358   1426   
  1359   1427       for(i=j=0, pTerm=pWC->a; i<pWC->nTerm; i++, pTerm++){
  1360   1428         if( pTerm->leftCursor != pSrc->iCursor ) continue;
  1361   1429         assert( (pTerm->eOperator&(pTerm->eOperator-1))==0 );
  1362   1430         testcase( pTerm->eOperator==WO_IN );
  1363   1431         testcase( pTerm->eOperator==WO_ISNULL );
  1364   1432         if( pTerm->eOperator & (WO_IN|WO_ISNULL) ) continue;
  1365         -      pIdxCons[j].iColumn = pTerm->leftColumn;
         1433  +      pIdxCons[j].iColumn = pTerm->u.leftColumn;
  1366   1434         pIdxCons[j].iTermOffset = i;
  1367   1435         pIdxCons[j].op = (u8)pTerm->eOperator;
  1368   1436         /* The direct assignment in the previous line is possible only because
  1369   1437         ** the WO_ and SQLITE_INDEX_CONSTRAINT_ codes are identical.  The
  1370   1438         ** following asserts verify this fact. */
  1371   1439         assert( WO_EQ==SQLITE_INDEX_CONSTRAINT_EQ );
  1372   1440         assert( WO_LT==SQLITE_INDEX_CONSTRAINT_LT );
................................................................................
  1590   1658     
  1591   1659       /* Check for constraints on a range of rowids in a table scan.
  1592   1660       */
  1593   1661       pTerm = findTerm(pWC, iCur, -1, notReady, WO_LT|WO_LE|WO_GT|WO_GE, 0);
  1594   1662       if( pTerm ){
  1595   1663         if( findTerm(pWC, iCur, -1, notReady, WO_LT|WO_LE, 0) ){
  1596   1664           wsFlags |= WHERE_TOP_LIMIT;
  1597         -        cost /= 3;  /* Guess that rowid<EXPR eliminates two-thirds or rows */
         1665  +        cost /= 3;  /* Guess that rowid<EXPR eliminates two-thirds of rows */
  1598   1666         }
  1599   1667         if( findTerm(pWC, iCur, -1, notReady, WO_GT|WO_GE, 0) ){
  1600   1668           wsFlags |= WHERE_BTM_LIMIT;
  1601   1669           cost /= 3;  /* Guess that rowid>EXPR eliminates two-thirds of rows */
  1602   1670         }
  1603   1671         WHERETRACE(("... rowid range reduces cost to %.9g\n", cost));
  1604   1672       }else{
................................................................................
  1880   1948   ** a==5 and b IN (1,2,3).  The current values for a and b will be left
  1881   1949   ** on the stack - a is the deepest and b the shallowest.
  1882   1950   **
  1883   1951   ** In the example above nEq==2.  But this subroutine works for any value
  1884   1952   ** of nEq including 0.  If nEq==0, this routine is nearly a no-op.
  1885   1953   ** The only thing it does is allocate the pLevel->iMem memory cell.
  1886   1954   **
  1887         -** This routine always allocates at least one memory cell and puts
  1888         -** the address of that memory cell in pLevel->iMem.  The code that
  1889         -** calls this routine will use pLevel->iMem to store the termination
         1955  +** This routine always allocates at least one memory cell and returns
         1956  +** the index of that memory cell. The code that
         1957  +** calls this routine will use that memory cell to store the termination
  1890   1958   ** key value of the loop.  If one or more IN operators appear, then
  1891   1959   ** this routine allocates an additional nEq memory cells for internal
  1892   1960   ** use.
  1893   1961   */
  1894   1962   static int codeAllEqualityTerms(
  1895   1963     Parse *pParse,        /* Parsing context */
  1896   1964     WhereLevel *pLevel,   /* Which nested loop of the FROM we are coding */
................................................................................
  1907   1975     int regBase;                  /* Base register */
  1908   1976   
  1909   1977     /* Figure out how many memory cells we will need then allocate them.
  1910   1978     ** We always need at least one used to store the loop terminator
  1911   1979     ** value.  If there are IN operators we'll need one for each == or
  1912   1980     ** IN constraint.
  1913   1981     */
  1914         -  pLevel->iMem = pParse->nMem + 1;
  1915         -  regBase = pParse->nMem + 2;
  1916         -  pParse->nMem += pLevel->nEq + 2 + nExtraReg;
         1982  +  regBase = pParse->nMem + 1;
         1983  +  pParse->nMem += pLevel->nEq + 1 + nExtraReg;
  1917   1984   
  1918   1985     /* Evaluate the equality constraints
  1919   1986     */
  1920   1987     assert( pIdx->nColumn>=nEq );
  1921   1988     for(j=0; j<nEq; j++){
  1922   1989       int r1;
  1923   1990       int k = pIdx->aiColumn[j];
................................................................................
  2476   2543         VdbeComment((v, "pk"));
  2477   2544         pLevel->op = OP_Noop;
  2478   2545       }else if( pLevel->wsFlags & WHERE_ROWID_RANGE ){
  2479   2546         /* Case 2:  We have an inequality comparison against the ROWID field.
  2480   2547         */
  2481   2548         int testOp = OP_Noop;
  2482   2549         int start;
         2550  +      int memEndValue = 0;
  2483   2551         WhereTerm *pStart, *pEnd;
  2484   2552   
  2485   2553         assert( omitTable==0 );
  2486   2554         pStart = findTerm(&wc, iCur, -1, notReady, WO_GT|WO_GE, 0);
  2487   2555         pEnd = findTerm(&wc, iCur, -1, notReady, WO_LT|WO_LE, 0);
  2488   2556         if( bRev ){
  2489   2557           pTerm = pStart;
................................................................................
  2520   2588           sqlite3VdbeAddOp2(v, bRev ? OP_Last : OP_Rewind, iCur, addrBrk);
  2521   2589         }
  2522   2590         if( pEnd ){
  2523   2591           Expr *pX;
  2524   2592           pX = pEnd->pExpr;
  2525   2593           assert( pX!=0 );
  2526   2594           assert( pEnd->leftCursor==iCur );
  2527         -        pLevel->iMem = ++pParse->nMem;
  2528         -        sqlite3ExprCode(pParse, pX->pRight, pLevel->iMem);
         2595  +        memEndValue = ++pParse->nMem;
         2596  +        sqlite3ExprCode(pParse, pX->pRight, memEndValue);
  2529   2597           if( pX->op==TK_LT || pX->op==TK_GT ){
  2530   2598             testOp = bRev ? OP_Le : OP_Ge;
  2531   2599           }else{
  2532   2600             testOp = bRev ? OP_Lt : OP_Gt;
  2533   2601           }
  2534   2602           disableTerm(pLevel, pEnd);
  2535   2603         }
................................................................................
  2536   2604         start = sqlite3VdbeCurrentAddr(v);
  2537   2605         pLevel->op = bRev ? OP_Prev : OP_Next;
  2538   2606         pLevel->p1 = iCur;
  2539   2607         pLevel->p2 = start;
  2540   2608         if( testOp!=OP_Noop ){
  2541   2609           int r1 = sqlite3GetTempReg(pParse);
  2542   2610           sqlite3VdbeAddOp2(v, OP_Rowid, iCur, r1);
  2543         -        /* sqlite3VdbeAddOp2(v, OP_SCopy, pLevel->iMem, 0); */
  2544         -        sqlite3VdbeAddOp3(v, testOp, pLevel->iMem, addrBrk, r1);
         2611  +        sqlite3VdbeAddOp3(v, testOp, memEndValue, addrBrk, r1);
  2545   2612           sqlite3VdbeChangeP5(v, SQLITE_AFF_NUMERIC | SQLITE_JUMPIFNULL);
  2546   2613           sqlite3ReleaseTempReg(pParse, r1);
  2547   2614         }
  2548   2615       }else if( pLevel->wsFlags & (WHERE_COLUMN_RANGE|WHERE_COLUMN_EQ) ){
  2549   2616         /* Case 3: A scan using an index.
  2550   2617         **
  2551   2618         **         The WHERE clause may contain zero or more equality 
................................................................................
  2730   2797         /* Record the instruction used to terminate the loop. Disable 
  2731   2798         ** WHERE clause terms made redundant by the index range scan.
  2732   2799         */
  2733   2800         pLevel->op = bRev ? OP_Prev : OP_Next;
  2734   2801         pLevel->p1 = iIdxCur;
  2735   2802         disableTerm(pLevel, pRangeStart);
  2736   2803         disableTerm(pLevel, pRangeEnd);
         2804  +    }else if( pLevel->wsFlags & WHERE_MULTI_OR ){
         2805  +      /* Case 4:  Two or more separately indexed terms connected by OR
         2806  +      **
         2807  +      ** Example:
         2808  +      **
         2809  +      **   CREATE TABLE t1(a,b,c,d);
         2810  +      **   CREATE INDEX i1 ON t1(a);
         2811  +      **   CREATE INDEX i2 ON t1(b);
         2812  +      **   CREATE INDEX i3 ON t1(c);
         2813  +      **
         2814  +      **   SELECT * FROM t1 WHERE a=5 OR b=7 OR (c=11 AND d=13)
         2815  +      **
         2816  +      ** In the example, there are three indexed terms connected by OR.
         2817  +      ** The top of the loop is constructed by creating a RowSet object
         2818  +      ** and populating it.  Then looping over elements of the rowset.
         2819  +      **
         2820  +      **        Null 1
         2821  +      **        # fill RowSet 1 with entries where a=5 using i1
         2822  +      **        # fill Rowset 1 with entries where b=7 using i2
         2823  +      **        # fill Rowset 1 with entries where c=11 and d=13 i3 and t1
         2824  +      **     A: RowSetRead 1, B, 2
         2825  +      **        Seek       i, 2
         2826  +      **
         2827  +      ** The bottom of the loop looks like this:
         2828  +      **
         2829  +      **     C: Goto       0, A
         2830  +      **     B:
         2831  +      */
  2737   2832       }else{
  2738         -      /* Case 4:  There is no usable index.  We must do a complete
         2833  +      /* Case 5:  There is no usable index.  We must do a complete
  2739   2834         **          scan of the entire table.
  2740   2835         */
  2741   2836         assert( omitTable==0 );
  2742   2837         assert( bRev==0 );
  2743   2838         pLevel->op = OP_Next;
  2744   2839         pLevel->p1 = iCur;
  2745   2840         pLevel->p2 = 1 + sqlite3VdbeAddOp2(v, OP_Rewind, iCur, addrBrk);