/ Check-in [8481e841]
Login

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

Overview
Comment:Add optimizations for the IN operator in WHERE clauses. This is a partial implementation of enhancement #63. Still need to add test cases. (CVS 610)
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1:8481e841ebdeabe07bf780246bda1aa053eb60b7
User & Date: drh 2002-06-08 23:25:09
Context
2002-06-09
01:16
Fix for ticket #65: If an integer value is too big to be represented as a 32-bit integer, then treat it as a string. (CVS 611) check-in: ad962479 user: drh tags: trunk
2002-06-08
23:25
Add optimizations for the IN operator in WHERE clauses. This is a partial implementation of enhancement #63. Still need to add test cases. (CVS 610) check-in: 8481e841 user: drh tags: trunk
2002-06-06
23:42
Bug fix: do not segfault if a SELECT without a FROM clause includes the * wildcard in the result column list. (CVS 609) check-in: d9392949 user: drh tags: trunk
Changes
Hide Diffs Side-by-Side Diffs Ignore Whitespace Patch

Changes to src/hash.h.

     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   ** This is the header file for the generic hash-table implemenation
    13     13   ** used in SQLite.
    14     14   **
    15         -** $Id: hash.h,v 1.4 2002/02/23 23:45:45 drh Exp $
           15  +** $Id: hash.h,v 1.5 2002/06/08 23:25:09 drh Exp $
    16     16   */
    17     17   #ifndef _SQLITE_HASH_H_
    18     18   #define _SQLITE_HASH_H_
    19     19   
    20     20   /* Forward declarations of structures. */
    21     21   typedef struct Hash Hash;
    22     22   typedef struct HashElem HashElem;
................................................................................
    95     95   **     // do something with pData
    96     96   **   }
    97     97   */
    98     98   #define sqliteHashFirst(H)  ((H)->first)
    99     99   #define sqliteHashNext(E)   ((E)->next)
   100    100   #define sqliteHashData(E)   ((E)->data)
   101    101   #define sqliteHashKey(E)    ((E)->pKey)
          102  +#define sqliteHashKeysize(E) ((E)->nKey)
   102    103   
   103    104   /*
   104    105   ** Number of entries in a hash table
   105    106   */
   106    107   #define sqliteHashCount(H)  ((H)->count)
   107    108   
   108    109   #endif /* _SQLITE_HASH_H_ */

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.120 2002/06/06 18:54:41 drh Exp $
           14  +** @(#) $Id: sqliteInt.h,v 1.121 2002/06/08 23:25:09 drh Exp $
    15     15   */
    16     16   #include "sqlite.h"
    17     17   #include "hash.h"
    18     18   #include "vdbe.h"
    19     19   #include "parse.h"
    20     20   #include "btree.h"
    21     21   #include <stdio.h>
................................................................................
   407    407   ** be the right operand of an IN operator.  Or, if a scalar SELECT appears
   408    408   ** in an expression the opcode is TK_SELECT and Expr.pSelect is the only
   409    409   ** operand.
   410    410   */
   411    411   struct Expr {
   412    412     int op;                /* Operation performed by this node */
   413    413     Expr *pLeft, *pRight;  /* Left and right subnodes */
   414         -  ExprList *pList;       /* A list of expressions used as a function argument */
          414  +  ExprList *pList;       /* A list of expressions used as function arguments
          415  +                         ** or in "<expr> IN (<expr-list)" */
   415    416     Token token;           /* An operand token */
   416    417     Token span;            /* Complete text of the expression */
   417    418     int iTable, iColumn;   /* When op==TK_COLUMN, then this expr node means the
   418    419                            ** iColumn-th field of the iTable-th table.  When
   419    420                            ** op==TK_FUNCTION, iColumn holds the function id */
   420    421     int iAgg;              /* When op==TK_COLUMN and pParse->useAgg==TRUE, pull
   421    422                            ** result from the iAgg-th element of the aggregator */
   422         -  Select *pSelect;       /* When the expression is a sub-select */
          423  +  Select *pSelect;       /* When the expression is a sub-select.  Also the
          424  +                         ** right side of "<expr> IN (<select>)" */
   423    425   };
   424    426   
   425    427   /*
   426    428   ** A list of expressions.  Each expression may optionally have a
   427    429   ** name.  An expr/name combination can be used in several ways, such
   428    430   ** as the list of "expr AS ID" fields following a "SELECT" or in the
   429    431   ** list of "ID = expr" items in an UPDATE.  A list of expressions can
................................................................................
   504    506     int iCur;            /* Cursor number used for this index */
   505    507     int score;           /* How well this indexed scored */
   506    508     int brk;             /* Jump here to break out of the loop */
   507    509     int cont;            /* Jump here to continue with the next loop cycle */
   508    510     int op, p1, p2;      /* Opcode used to terminate the loop */
   509    511     int iLeftJoin;       /* Memory cell used to implement LEFT OUTER JOIN */
   510    512     int top;             /* First instruction of interior of the loop */
          513  +  int inOp, inP1, inP2;/* Opcode used to implement an IN operator */
   511    514   };
   512    515   
   513    516   /*
   514    517   ** The WHERE clause processing routine has two halves.  The
   515    518   ** first part does the start of the WHERE loop and the second
   516    519   ** half does the tail of the WHERE loop.  An instance of
   517    520   ** this structure is returned by the first half and passed

Changes to src/vdbe.c.

    26     26   ** type to the other occurs as necessary.
    27     27   ** 
    28     28   ** Most of the code in this file is taken up by the sqliteVdbeExec()
    29     29   ** function which does the work of interpreting a VDBE program.
    30     30   ** But other routines are also provided to help in building up
    31     31   ** a program instruction by instruction.
    32     32   **
    33         -** $Id: vdbe.c,v 1.153 2002/06/06 23:16:06 drh Exp $
           33  +** $Id: vdbe.c,v 1.154 2002/06/08 23:25:09 drh Exp $
    34     34   */
    35     35   #include "sqliteInt.h"
    36     36   #include <ctype.h>
    37     37   
    38     38   /*
    39     39   ** The following global variable is incremented every time a cursor
    40     40   ** moves, either by the OP_MoveTo or the OP_Next opcode.  The test
................................................................................
   194    194   ** is part of a small set.  Sets are used to implement code like
   195    195   ** this:
   196    196   **            x.y IN ('hi','hoo','hum')
   197    197   */
   198    198   typedef struct Set Set;
   199    199   struct Set {
   200    200     Hash hash;             /* A set is just a hash table */
          201  +  HashElem *prev;        /* Previously accessed hash elemen */
   201    202   };
   202    203   
   203    204   /*
   204    205   ** A Keylist is a bunch of keys into a table.  The keylist can
   205    206   ** grow without bound.  The keylist stores the ROWIDs of database
   206    207   ** records that need to be deleted or updated.
   207    208   */
................................................................................
  1062   1063     "IdxGE",             "MemLoad",           "MemStore",          "ListWrite",
  1063   1064     "ListRewind",        "ListRead",          "ListReset",         "ListPush",
  1064   1065     "ListPop",           "SortPut",           "SortMakeRec",       "SortMakeKey",
  1065   1066     "Sort",              "SortNext",          "SortCallback",      "SortReset",
  1066   1067     "FileOpen",          "FileRead",          "FileColumn",        "AggReset",
  1067   1068     "AggFocus",          "AggNext",           "AggSet",            "AggGet",
  1068   1069     "AggFunc",           "AggInit",           "AggPush",           "AggPop",
  1069         -  "SetInsert",         "SetFound",          "SetNotFound",       "MakeRecord",
  1070         -  "MakeKey",           "MakeIdxKey",        "IncrKey",           "Goto",
  1071         -  "If",                "IfNot",             "Halt",              "ColumnCount",
  1072         -  "ColumnName",        "Callback",          "NullCallback",      "Integer",
  1073         -  "String",            "Pop",               "Dup",               "Pull",
  1074         -  "Push",              "MustBeInt",         "Add",               "AddImm",
  1075         -  "Subtract",          "Multiply",          "Divide",            "Remainder",
  1076         -  "BitAnd",            "BitOr",             "BitNot",            "ShiftLeft",
  1077         -  "ShiftRight",        "AbsValue",          "Eq",                "Ne",
  1078         -  "Lt",                "Le",                "Gt",                "Ge",
  1079         -  "IsNull",            "NotNull",           "Negative",          "And",
  1080         -  "Or",                "Not",               "Concat",            "Noop",
  1081         -  "Function",          "Limit",           
         1070  +  "SetInsert",         "SetFound",          "SetNotFound",       "SetFirst",
         1071  +  "SetNext",           "MakeRecord",        "MakeKey",           "MakeIdxKey",
         1072  +  "IncrKey",           "Goto",              "If",                "IfNot",
         1073  +  "Halt",              "ColumnCount",       "ColumnName",        "Callback",
         1074  +  "NullCallback",      "Integer",           "String",            "Pop",
         1075  +  "Dup",               "Pull",              "Push",              "MustBeInt",
         1076  +  "Add",               "AddImm",            "Subtract",          "Multiply",
         1077  +  "Divide",            "Remainder",         "BitAnd",            "BitOr",
         1078  +  "BitNot",            "ShiftLeft",         "ShiftRight",        "AbsValue",
         1079  +  "Eq",                "Ne",                "Lt",                "Le",
         1080  +  "Gt",                "Ge",                "IsNull",            "NotNull",
         1081  +  "Negative",          "And",               "Or",                "Not",
         1082  +  "Concat",            "Noop",              "Function",          "Limit",
  1082   1083   };
  1083   1084   
  1084   1085   /*
  1085   1086   ** Given the name of an opcode, return its number.  Return 0 if
  1086   1087   ** there is no match.
  1087   1088   **
  1088   1089   ** This routine is used for testing and debugging.
................................................................................
  1953   1954     aStack[tos].i += pOp->p1;
  1954   1955     break;
  1955   1956   }
  1956   1957   
  1957   1958   /* Opcode: MustBeInt  * P2 *
  1958   1959   ** 
  1959   1960   ** Force the top of the stack to be an integer.  If the top of the
  1960         -** stack is not an integer and cannot be comverted into an integer
         1961  +** stack is not an integer and cannot be converted into an integer
  1961   1962   ** with out data loss, then jump immediately to P2, or if P2==0
  1962   1963   ** raise an SQLITE_MISMATCH exception.
  1963   1964   */
  1964   1965   case OP_MustBeInt: {
  1965   1966     int tos = p->tos;
  1966   1967     VERIFY( if( tos<0 ) goto not_enough_stack; )
  1967   1968     if( aStack[tos].flags & STK_Int ){
................................................................................
  3014   3015   ** not exist in the table of cursor P1, then jump to P2.  If the record
  3015   3016   ** does already exist, then fall thru.  The cursor is left pointing
  3016   3017   ** at the record if it exists. The key is not popped from the stack.
  3017   3018   **
  3018   3019   ** This operation is similar to NotFound except that this operation
  3019   3020   ** does not pop the key from the stack.
  3020   3021   **
  3021         -** See also: Found, NotFound, MoveTo
         3022  +** See also: Found, NotFound, MoveTo, IsUnique, NotExists
  3022   3023   */
  3023   3024   /* Opcode: Found P1 P2 *
  3024   3025   **
  3025   3026   ** Use the top of the stack as a string key.  If a record with that key
  3026   3027   ** does exist in table of P1, then jump to P2.  If the record
  3027   3028   ** does not exist, then fall thru.  The cursor is left pointing
  3028   3029   ** to the record if it exists.  The key is popped from the stack.
  3029   3030   **
  3030         -** See also: Distinct, NotFound, MoveTo
         3031  +** See also: Distinct, NotFound, MoveTo, IsUnique, NotExists
  3031   3032   */
  3032   3033   /* Opcode: NotFound P1 P2 *
  3033   3034   **
  3034   3035   ** Use the top of the stack as a string key.  If a record with that key
  3035   3036   ** does not exist in table of P1, then jump to P2.  If the record
  3036   3037   ** does exist, then fall thru.  The cursor is left pointing to the
  3037   3038   ** record if it exists.  The key is popped from the stack.
................................................................................
  3080   3081   ** index string matches K but the record number is different
  3081   3082   ** from R.  If there is no such entry, then there is an immediate
  3082   3083   ** jump to P2.  If any entry does exist where the index string
  3083   3084   ** matches K but the record number is not R, then the record
  3084   3085   ** number for that entry is pushed onto the stack and control
  3085   3086   ** falls through to the next instruction.
  3086   3087   **
  3087         -** See also: Distinct, NotFound, NotExists
         3088  +** See also: Distinct, NotFound, NotExists, Found
  3088   3089   */
  3089   3090   case OP_IsUnique: {
  3090   3091     int i = pOp->p1;
  3091   3092     int tos = p->tos;
  3092   3093     int nos = tos-1;
  3093   3094     BtCursor *pCrsr;
  3094   3095     int R;
................................................................................
  3163   3164   ** does exist, then fall thru.  The cursor is left pointing to the
  3164   3165   ** record if it exists.  The integer key is popped from the stack.
  3165   3166   **
  3166   3167   ** The difference between this operation and NotFound is that this
  3167   3168   ** operation assumes the key is an integer and NotFound assumes it
  3168   3169   ** is a string.
  3169   3170   **
  3170         -** See also: Distinct, Found, MoveTo, NotExists
         3171  +** See also: Distinct, Found, MoveTo, NotFound, IsUnique
  3171   3172   */
  3172   3173   case OP_NotExists: {
  3173   3174     int i = pOp->p1;
  3174   3175     int tos = p->tos;
  3175   3176     BtCursor *pCrsr;
  3176   3177     VERIFY( if( tos<0 ) goto not_enough_stack; )
  3177   3178     if( VERIFY( i>=0 && i<p->nCursor && ) (pCrsr = p->aCsr[i].pCursor)!=0 ){
................................................................................
  4771   4772          sqliteHashFind(&p->aSet[i].hash, zStack[tos], aStack[tos].n)==0 ){
  4772   4773       pc = pOp->p2 - 1;
  4773   4774     }
  4774   4775     POPSTACK;
  4775   4776     break;
  4776   4777   }
  4777   4778   
         4779  +/* Opcode: SetFirst P1 P2 *
         4780  +**
         4781  +** Read the first element from set P1 and push it onto the stack.  If the
         4782  +** set is empty, push nothing and jump immediately to P2.  This opcode is
         4783  +** used in combination with OP_SetNext to loop over all elements of a set.
         4784  +*/
         4785  +/* Opcode: SetNext P1 P2 *
         4786  +**
         4787  +** Read the next element from set P1 and push it onto the stack.  If there
         4788  +** are no more elements in the set, do not do the push and fall through.
         4789  +** Otherwise, jump to P2 after pushing the next set element.
         4790  +*/
         4791  +case OP_SetFirst: 
         4792  +case OP_SetNext: {
         4793  +  Set *pSet;
         4794  +  int tos;
         4795  +  VERIFY( if( pOp->p1<0 || pOp->p1>=p->nSet ) goto bad_instruction; )
         4796  +  pSet = &p->aSet[pOp->p1];
         4797  +  if( pOp->opcode==OP_SetFirst ){
         4798  +    pSet->prev = sqliteHashFirst(&pSet->hash);
         4799  +    if( pSet->prev==0 ){
         4800  +      pc = pOp->p2 - 1;
         4801  +      break;
         4802  +    }
         4803  +  }else{
         4804  +    VERIFY( if( pSet->prev==0 ) goto bad_instruction; )
         4805  +    pSet->prev = sqliteHashNext(pSet->prev);
         4806  +    if( pSet->prev==0 ){
         4807  +      break;
         4808  +    }else{
         4809  +      pc = pOp->p2 - 1;
         4810  +    }
         4811  +  }
         4812  +  tos = ++p->tos;
         4813  +  VERIFY( if( NeedStack(p, p->tos) ) goto no_mem; )
         4814  +  zStack[tos] = sqliteHashKey(pSet->prev);
         4815  +  aStack[tos].n = sqliteHashKeysize(pSet->prev);
         4816  +  aStack[tos].flags = STK_Str | STK_Static;
         4817  +  break;
         4818  +}
  4778   4819   
  4779   4820   /* An other opcode is illegal...
  4780   4821   */
  4781   4822   default: {
  4782   4823     sprintf(zBuf,"%d",pOp->opcode);
  4783   4824     sqliteSetString(pzErrMsg, "unknown opcode ", zBuf, 0);
  4784   4825     rc = SQLITE_INTERNAL;

Changes to src/vdbe.h.

    11     11   *************************************************************************
    12     12   ** Header file for the Virtual DataBase Engine (VDBE)
    13     13   **
    14     14   ** This header defines the interface to the virtual database engine
    15     15   ** or VDBE.  The VDBE implements an abstract machine that runs a
    16     16   ** simple program to access and modify the underlying database.
    17     17   **
    18         -** $Id: vdbe.h,v 1.53 2002/05/26 20:54:34 drh Exp $
           18  +** $Id: vdbe.h,v 1.54 2002/06/08 23:25:09 drh Exp $
    19     19   */
    20     20   #ifndef _SQLITE_VDBE_H_
    21     21   #define _SQLITE_VDBE_H_
    22     22   #include <stdio.h>
    23     23   
    24     24   /*
    25     25   ** A single VDBE is an opaque structure named "Vdbe".  Only routines
................................................................................
   145    145   #define OP_AggInit            66
   146    146   #define OP_AggPush            67
   147    147   #define OP_AggPop             68
   148    148   
   149    149   #define OP_SetInsert          69
   150    150   #define OP_SetFound           70
   151    151   #define OP_SetNotFound        71
          152  +#define OP_SetFirst           72
          153  +#define OP_SetNext            73
   152    154   
   153         -#define OP_MakeRecord         72
   154         -#define OP_MakeKey            73
   155         -#define OP_MakeIdxKey         74
   156         -#define OP_IncrKey            75
          155  +#define OP_MakeRecord         74
          156  +#define OP_MakeKey            75
          157  +#define OP_MakeIdxKey         76
          158  +#define OP_IncrKey            77
   157    159   
   158         -#define OP_Goto               76
   159         -#define OP_If                 77
   160         -#define OP_IfNot              78
   161         -#define OP_Halt               79
          160  +#define OP_Goto               78
          161  +#define OP_If                 79
          162  +#define OP_IfNot              80
          163  +#define OP_Halt               81
   162    164   
   163         -#define OP_ColumnCount        80
   164         -#define OP_ColumnName         81
   165         -#define OP_Callback           82
   166         -#define OP_NullCallback       83
          165  +#define OP_ColumnCount        82
          166  +#define OP_ColumnName         83
          167  +#define OP_Callback           84
          168  +#define OP_NullCallback       85
   167    169   
   168         -#define OP_Integer            84
   169         -#define OP_String             85
   170         -#define OP_Pop                86
   171         -#define OP_Dup                87
   172         -#define OP_Pull               88
   173         -#define OP_Push               89
   174         -#define OP_MustBeInt          90
          170  +#define OP_Integer            86
          171  +#define OP_String             87
          172  +#define OP_Pop                88
          173  +#define OP_Dup                89
          174  +#define OP_Pull               90
          175  +#define OP_Push               91
          176  +#define OP_MustBeInt          92
   175    177   
   176         -#define OP_Add                91
   177         -#define OP_AddImm             92
   178         -#define OP_Subtract           93
   179         -#define OP_Multiply           94
   180         -#define OP_Divide             95
   181         -#define OP_Remainder          96
   182         -#define OP_BitAnd             97
   183         -#define OP_BitOr              98
   184         -#define OP_BitNot             99
   185         -#define OP_ShiftLeft         100
   186         -#define OP_ShiftRight        101
   187         -#define OP_AbsValue          102
   188         -#define OP_Eq                103
   189         -#define OP_Ne                104
   190         -#define OP_Lt                105
   191         -#define OP_Le                106
   192         -#define OP_Gt                107
   193         -#define OP_Ge                108
   194         -#define OP_IsNull            109
   195         -#define OP_NotNull           110
   196         -#define OP_Negative          111
   197         -#define OP_And               112
   198         -#define OP_Or                113
   199         -#define OP_Not               114
   200         -#define OP_Concat            115
   201         -#define OP_Noop              116
   202         -#define OP_Function          117
          178  +#define OP_Add                93
          179  +#define OP_AddImm             94
          180  +#define OP_Subtract           95
          181  +#define OP_Multiply           96
          182  +#define OP_Divide             97
          183  +#define OP_Remainder          98
          184  +#define OP_BitAnd             99
          185  +#define OP_BitOr             100
          186  +#define OP_BitNot            101
          187  +#define OP_ShiftLeft         102
          188  +#define OP_ShiftRight        103
          189  +#define OP_AbsValue          104
          190  +#define OP_Eq                105
          191  +#define OP_Ne                106
          192  +#define OP_Lt                107
          193  +#define OP_Le                108
          194  +#define OP_Gt                109
          195  +#define OP_Ge                110
          196  +#define OP_IsNull            111
          197  +#define OP_NotNull           112
          198  +#define OP_Negative          113
          199  +#define OP_And               114
          200  +#define OP_Or                115
          201  +#define OP_Not               116
          202  +#define OP_Concat            117
          203  +#define OP_Noop              118
          204  +#define OP_Function          119
   203    205   
   204         -#define OP_Limit             118
          206  +#define OP_Limit             120
   205    207   
   206    208   
   207         -#define OP_MAX               118
          209  +#define OP_MAX               120
   208    210   
   209    211   /*
   210    212   ** Prototypes for the VDBE interface.  See comments on the implementation
   211    213   ** for a description of what each of these routines does.
   212    214   */
   213    215   Vdbe *sqliteVdbeCreate(sqlite*);
   214    216   void sqliteVdbeCreateCallback(Vdbe*, int*);

Changes to src/where.c.

     9      9   **    May you share freely, never taking more than you give.
    10     10   **
    11     11   *************************************************************************
    12     12   ** This module contains C code that generates VDBE code used to process
    13     13   ** the WHERE clause of SQL statements.  Also found here are subroutines
    14     14   ** to generate VDBE code to evaluate expressions.
    15     15   **
    16         -** $Id: where.c,v 1.48 2002/05/26 20:54:34 drh Exp $
           16  +** $Id: where.c,v 1.49 2002/06/08 23:25:10 drh Exp $
    17     17   */
    18     18   #include "sqliteInt.h"
    19     19   
    20     20   /*
    21     21   ** The query generator uses an array of instances of this structure to
    22     22   ** help it analyze the subexpressions of the WHERE clause.  Each WHERE
    23     23   ** clause subexpression is separated from the others by an AND operator.
................................................................................
   108    108   static int allowedOp(int op){
   109    109     switch( op ){
   110    110       case TK_LT:
   111    111       case TK_LE:
   112    112       case TK_GT:
   113    113       case TK_GE:
   114    114       case TK_EQ:
          115  +    case TK_IN:
   115    116         return 1;
   116    117       default:
   117    118         return 0;
   118    119     }
   119    120   }
   120    121   
   121    122   /*
................................................................................
   132    133     pInfo->prereqLeft = exprTableUsage(base, pExpr->pLeft);
   133    134     pInfo->prereqRight = exprTableUsage(base, pExpr->pRight);
   134    135     pInfo->prereqAll = exprTableUsage(base, pExpr);
   135    136     pInfo->indexable = 0;
   136    137     pInfo->idxLeft = -1;
   137    138     pInfo->idxRight = -1;
   138    139     if( allowedOp(pExpr->op) && (pInfo->prereqRight & pInfo->prereqLeft)==0 ){
   139         -    if( pExpr->pRight->op==TK_COLUMN ){
          140  +    if( pExpr->pRight && pExpr->pRight->op==TK_COLUMN ){
   140    141         pInfo->idxRight = pExpr->pRight->iTable - base;
   141    142         pInfo->indexable = 1;
   142    143       }
   143    144       if( pExpr->pLeft->op==TK_COLUMN ){
   144    145         pInfo->idxLeft = pExpr->pLeft->iTable - base;
   145    146         pInfo->indexable = 1;
   146    147       }
................................................................................
   284    285       iDirectEq[i] = -1;
   285    286       iDirectLt[i] = -1;
   286    287       iDirectGt[i] = -1;
   287    288       for(j=0; j<nExpr; j++){
   288    289         if( aExpr[j].idxLeft==idx && aExpr[j].p->pLeft->iColumn<0
   289    290               && (aExpr[j].prereqRight & loopMask)==aExpr[j].prereqRight ){
   290    291           switch( aExpr[j].p->op ){
          292  +          case TK_IN:
   291    293             case TK_EQ: iDirectEq[i] = j; break;
   292    294             case TK_LE:
   293    295             case TK_LT: iDirectLt[i] = j; break;
   294    296             case TK_GE:
   295    297             case TK_GT: iDirectGt[i] = j;  break;
   296    298           }
   297    299         }
................................................................................
   325    327       **
   326    328       ** This scoring system is designed so that the score can later be
   327    329       ** used to determine how the index is used.  If the score&3 is 0
   328    330       ** then all constraints are equalities.  If score&1 is not 0 then
   329    331       ** there is an inequality used as a termination key.  (ex: "x<...")
   330    332       ** If score&2 is not 0 then there is an inequality used as the
   331    333       ** start key.  (ex: "x>...");
          334  +    **
          335  +    ** The IN operator as in "<expr> IN (...)" is treated the same as
          336  +    ** an equality comparison.
   332    337       */
   333    338       for(pIdx=pTab->pIndex; pIdx; pIdx=pIdx->pNext){
   334    339         int eqMask = 0;  /* Index columns covered by an x=... constraint */
   335    340         int ltMask = 0;  /* Index columns covered by an x<... constraint */
   336    341         int gtMask = 0;  /* Index columns covered by an x>... constraing */
   337    342         int nEq, m, score;
   338    343   
................................................................................
   342    347           if( aExpr[j].idxLeft==idx 
   343    348                && (aExpr[j].prereqRight & loopMask)==aExpr[j].prereqRight ){
   344    349             int iColumn = aExpr[j].p->pLeft->iColumn;
   345    350             int k;
   346    351             for(k=0; k<pIdx->nColumn; k++){
   347    352               if( pIdx->aiColumn[k]==iColumn ){
   348    353                 switch( aExpr[j].p->op ){
          354  +                case TK_IN:
   349    355                   case TK_EQ: {
   350    356                     eqMask |= 1<<k;
   351    357                     break;
   352    358                   }
   353    359                   case TK_LE:
   354    360                   case TK_LT: {
   355    361                     ltMask |= 1<<k;
................................................................................
   463    469         if( !pParse->nMem ) pParse->nMem++;
   464    470         pLevel->iLeftJoin = pParse->nMem++;
   465    471         sqliteVdbeAddOp(v, OP_String, 0, 0);
   466    472         sqliteVdbeAddOp(v, OP_MemStore, pLevel->iLeftJoin, 1);
   467    473       }
   468    474   
   469    475       pIdx = pLevel->pIdx;
          476  +    pLevel->inOp = OP_Noop;
   470    477       if( i<ARRAYSIZE(iDirectEq) && iDirectEq[i]>=0 ){
   471    478         /* Case 1:  We can directly reference a single row using an
   472    479         **          equality comparison against the ROWID field.
   473    480         */
   474    481         k = iDirectEq[i];
   475    482         assert( k<nExpr );
   476    483         assert( aExpr[k].p!=0 );
   477    484         assert( aExpr[k].idxLeft==idx || aExpr[k].idxRight==idx );
          485  +      brk = pLevel->brk = sqliteVdbeMakeLabel(v);
   478    486         if( aExpr[k].idxLeft==idx ){
   479         -        sqliteExprCode(pParse, aExpr[k].p->pRight);
          487  +        Expr *pX = aExpr[k].p;
          488  +        if( pX->op!=TK_IN ){
          489  +          sqliteExprCode(pParse, aExpr[k].p->pRight);
          490  +        }else if( pX->pList ){
          491  +          sqliteVdbeAddOp(v, OP_SetFirst, pX->iTable, brk);
          492  +          pLevel->inOp = OP_SetNext;
          493  +          pLevel->inP1 = pX->iTable;
          494  +          pLevel->inP2 = sqliteVdbeCurrentAddr(v);
          495  +        }else{
          496  +          assert( pX->pSelect );
          497  +          sqliteVdbeAddOp(v, OP_Rewind, pX->iTable, brk);
          498  +          sqliteVdbeAddOp(v, OP_KeyAsData, pX->iTable, 1);
          499  +          pLevel->inP2 = sqliteVdbeAddOp(v, OP_FullKey, pX->iTable, 0);
          500  +          pLevel->inOp = OP_Next;
          501  +          pLevel->inP1 = pX->iTable;
          502  +        }
   480    503         }else{
   481    504           sqliteExprCode(pParse, aExpr[k].p->pLeft);
   482    505         }
   483    506         aExpr[k].p = 0;
   484         -      brk = pLevel->brk = sqliteVdbeMakeLabel(v);
   485         -      cont = pLevel->cont = brk;
          507  +      cont = pLevel->cont = sqliteVdbeMakeLabel(v);
   486    508         sqliteVdbeAddOp(v, OP_MustBeInt, 0, brk);
   487         -      if( i==pTabList->nSrc-1 && pushKey ){
   488         -        /* Note: The OP_Dup below will cause the recno to be left on the
   489         -        ** stack if the record does not exists and the OP_NotExists jump is
   490         -        ** taken.  This violates a general rule of the VDBE that you should
   491         -        ** never leave values on the stack in order to avoid a stack overflow.
   492         -        ** But in this case, the OP_Dup will never happen inside of a loop,
   493         -        ** because the pushKey flag is only true for UPDATE and DELETE, not
   494         -        ** for SELECT, and nested loops only occur on a SELECT.
   495         -        ** So it is safe to leave the recno on the stack.
   496         -        */
   497         -        haveKey = 1;
   498         -        sqliteVdbeAddOp(v, OP_Dup, 0, 0);
   499         -      }else{
   500         -        haveKey = 0;
   501         -      }
          509  +      haveKey = 0;
   502    510         sqliteVdbeAddOp(v, OP_NotExists, base+idx, brk);
   503    511         pLevel->op = OP_Noop;
   504    512       }else if( pIdx!=0 && pLevel->score%4==0 ){
   505    513         /* Case 2:  All index constraints are equality operators.
   506    514         */
   507    515         int start;
   508    516         int testOp;
   509    517         int nColumn = pLevel->score/4;
          518  +      brk = pLevel->brk = sqliteVdbeMakeLabel(v);
   510    519         for(j=0; j<nColumn; j++){
   511    520           for(k=0; k<nExpr; k++){
   512         -          if( aExpr[k].p==0 ) continue;
          521  +          Expr *pX = aExpr[k].p;
          522  +          if( pX==0 ) continue;
   513    523             if( aExpr[k].idxLeft==idx 
   514         -             && aExpr[k].p->op==TK_EQ
   515    524                && (aExpr[k].prereqRight & loopMask)==aExpr[k].prereqRight 
   516         -             && aExpr[k].p->pLeft->iColumn==pIdx->aiColumn[j]
          525  +             && pX->pLeft->iColumn==pIdx->aiColumn[j]
   517    526             ){
   518         -            sqliteExprCode(pParse, aExpr[k].p->pRight);
   519         -            aExpr[k].p = 0;
   520         -            break;
          527  +            if( pX->op==TK_EQ ){
          528  +              sqliteExprCode(pParse, pX->pRight);
          529  +              aExpr[k].p = 0;
          530  +              break;
          531  +            }
          532  +            if( pX->op==TK_IN && nColumn==1 ){
          533  +              if( pX->pList ){
          534  +                sqliteVdbeAddOp(v, OP_SetFirst, pX->iTable, brk);
          535  +                pLevel->inOp = OP_SetNext;
          536  +                pLevel->inP1 = pX->iTable;
          537  +                pLevel->inP2 = sqliteVdbeCurrentAddr(v);
          538  +              }else{
          539  +                assert( pX->pSelect );
          540  +                sqliteVdbeAddOp(v, OP_Rewind, pX->iTable, brk);
          541  +                sqliteVdbeAddOp(v, OP_KeyAsData, pX->iTable, 1);
          542  +                pLevel->inP2 = sqliteVdbeAddOp(v, OP_FullKey, pX->iTable, 0);
          543  +                pLevel->inOp = OP_Next;
          544  +                pLevel->inP1 = pX->iTable;
          545  +              }
          546  +              aExpr[k].p = 0;
          547  +              break;
          548  +            }
   521    549             }
   522    550             if( aExpr[k].idxRight==idx 
   523    551                && aExpr[k].p->op==TK_EQ
   524    552                && (aExpr[k].prereqLeft & loopMask)==aExpr[k].prereqLeft
   525    553                && aExpr[k].p->pRight->iColumn==pIdx->aiColumn[j]
   526    554             ){
   527    555               sqliteExprCode(pParse, aExpr[k].p->pLeft);
   528    556               aExpr[k].p = 0;
   529    557               break;
   530    558             }
   531    559           }
   532    560         }
   533    561         pLevel->iMem = pParse->nMem++;
   534         -      brk = pLevel->brk = sqliteVdbeMakeLabel(v);
   535    562         cont = pLevel->cont = sqliteVdbeMakeLabel(v);
   536    563         sqliteVdbeAddOp(v, OP_MakeKey, nColumn, 0);
   537    564         if( nColumn==pIdx->nColumn ){
   538    565           sqliteVdbeAddOp(v, OP_MemStore, pLevel->iMem, 0);
   539    566           testOp = OP_IdxGT;
   540    567         }else{
   541    568           sqliteVdbeAddOp(v, OP_Dup, 0, 0);
................................................................................
   830    857     for(i=pTabList->nSrc-1; i>=0; i--){
   831    858       pLevel = &pWInfo->a[i];
   832    859       sqliteVdbeResolveLabel(v, pLevel->cont);
   833    860       if( pLevel->op!=OP_Noop ){
   834    861         sqliteVdbeAddOp(v, pLevel->op, pLevel->p1, pLevel->p2);
   835    862       }
   836    863       sqliteVdbeResolveLabel(v, pLevel->brk);
          864  +    if( pLevel->inOp!=OP_Noop ){
          865  +      sqliteVdbeAddOp(v, pLevel->inOp, pLevel->inP1, pLevel->inP2);
          866  +    }
   837    867       if( pLevel->iLeftJoin ){
   838    868         int addr;
   839    869         addr = sqliteVdbeAddOp(v, OP_MemLoad, pLevel->iLeftJoin, 0);
   840    870         sqliteVdbeAddOp(v, OP_NotNull, 0, addr+4);
   841    871         sqliteVdbeAddOp(v, OP_NullRow, base+i, 0);
   842    872         sqliteVdbeAddOp(v, OP_Goto, 0, pLevel->top);
   843    873       }