/ 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 Unified Diffs Ignore Whitespace Patch

Changes to src/hash.h.

8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
..
95
96
97
98
99
100
101

102
103
104
105
106
107
108
**    May you find forgiveness for yourself and forgive others.
**    May you share freely, never taking more than you give.
**
*************************************************************************
** This is the header file for the generic hash-table implemenation
** used in SQLite.
**
** $Id: hash.h,v 1.4 2002/02/23 23:45:45 drh Exp $
*/
#ifndef _SQLITE_HASH_H_
#define _SQLITE_HASH_H_

/* Forward declarations of structures. */
typedef struct Hash Hash;
typedef struct HashElem HashElem;
................................................................................
**     // do something with pData
**   }
*/
#define sqliteHashFirst(H)  ((H)->first)
#define sqliteHashNext(E)   ((E)->next)
#define sqliteHashData(E)   ((E)->data)
#define sqliteHashKey(E)    ((E)->pKey)


/*
** Number of entries in a hash table
*/
#define sqliteHashCount(H)  ((H)->count)

#endif /* _SQLITE_HASH_H_ */







|







 







>







8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
..
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
**    May you find forgiveness for yourself and forgive others.
**    May you share freely, never taking more than you give.
**
*************************************************************************
** This is the header file for the generic hash-table implemenation
** used in SQLite.
**
** $Id: hash.h,v 1.5 2002/06/08 23:25:09 drh Exp $
*/
#ifndef _SQLITE_HASH_H_
#define _SQLITE_HASH_H_

/* Forward declarations of structures. */
typedef struct Hash Hash;
typedef struct HashElem HashElem;
................................................................................
**     // do something with pData
**   }
*/
#define sqliteHashFirst(H)  ((H)->first)
#define sqliteHashNext(E)   ((E)->next)
#define sqliteHashData(E)   ((E)->data)
#define sqliteHashKey(E)    ((E)->pKey)
#define sqliteHashKeysize(E) ((E)->nKey)

/*
** Number of entries in a hash table
*/
#define sqliteHashCount(H)  ((H)->count)

#endif /* _SQLITE_HASH_H_ */

Changes to src/sqliteInt.h.

7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
...
407
408
409
410
411
412
413
414

415
416
417
418
419
420
421
422

423
424
425
426
427
428
429
...
504
505
506
507
508
509
510

511
512
513
514
515
516
517
**    May you do good and not evil.
**    May you find forgiveness for yourself and forgive others.
**    May you share freely, never taking more than you give.
**
*************************************************************************
** Internal interface definitions for SQLite.
**
** @(#) $Id: sqliteInt.h,v 1.120 2002/06/06 18:54:41 drh Exp $
*/
#include "sqlite.h"
#include "hash.h"
#include "vdbe.h"
#include "parse.h"
#include "btree.h"
#include <stdio.h>
................................................................................
** be the right operand of an IN operator.  Or, if a scalar SELECT appears
** in an expression the opcode is TK_SELECT and Expr.pSelect is the only
** operand.
*/
struct Expr {
  int op;                /* Operation performed by this node */
  Expr *pLeft, *pRight;  /* Left and right subnodes */
  ExprList *pList;       /* A list of expressions used as a function argument */

  Token token;           /* An operand token */
  Token span;            /* Complete text of the expression */
  int iTable, iColumn;   /* When op==TK_COLUMN, then this expr node means the
                         ** iColumn-th field of the iTable-th table.  When
                         ** op==TK_FUNCTION, iColumn holds the function id */
  int iAgg;              /* When op==TK_COLUMN and pParse->useAgg==TRUE, pull
                         ** result from the iAgg-th element of the aggregator */
  Select *pSelect;       /* When the expression is a sub-select */

};

/*
** A list of expressions.  Each expression may optionally have a
** name.  An expr/name combination can be used in several ways, such
** as the list of "expr AS ID" fields following a "SELECT" or in the
** list of "ID = expr" items in an UPDATE.  A list of expressions can
................................................................................
  int iCur;            /* Cursor number used for this index */
  int score;           /* How well this indexed scored */
  int brk;             /* Jump here to break out of the loop */
  int cont;            /* Jump here to continue with the next loop cycle */
  int op, p1, p2;      /* Opcode used to terminate the loop */
  int iLeftJoin;       /* Memory cell used to implement LEFT OUTER JOIN */
  int top;             /* First instruction of interior of the loop */

};

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







|







 







|
>







|
>







 







>







7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
...
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
...
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
**    May you do good and not evil.
**    May you find forgiveness for yourself and forgive others.
**    May you share freely, never taking more than you give.
**
*************************************************************************
** Internal interface definitions for SQLite.
**
** @(#) $Id: sqliteInt.h,v 1.121 2002/06/08 23:25:09 drh Exp $
*/
#include "sqlite.h"
#include "hash.h"
#include "vdbe.h"
#include "parse.h"
#include "btree.h"
#include <stdio.h>
................................................................................
** be the right operand of an IN operator.  Or, if a scalar SELECT appears
** in an expression the opcode is TK_SELECT and Expr.pSelect is the only
** operand.
*/
struct Expr {
  int op;                /* Operation performed by this node */
  Expr *pLeft, *pRight;  /* Left and right subnodes */
  ExprList *pList;       /* A list of expressions used as function arguments
                         ** or in "<expr> IN (<expr-list)" */
  Token token;           /* An operand token */
  Token span;            /* Complete text of the expression */
  int iTable, iColumn;   /* When op==TK_COLUMN, then this expr node means the
                         ** iColumn-th field of the iTable-th table.  When
                         ** op==TK_FUNCTION, iColumn holds the function id */
  int iAgg;              /* When op==TK_COLUMN and pParse->useAgg==TRUE, pull
                         ** result from the iAgg-th element of the aggregator */
  Select *pSelect;       /* When the expression is a sub-select.  Also the
                         ** right side of "<expr> IN (<select>)" */
};

/*
** A list of expressions.  Each expression may optionally have a
** name.  An expr/name combination can be used in several ways, such
** as the list of "expr AS ID" fields following a "SELECT" or in the
** list of "ID = expr" items in an UPDATE.  A list of expressions can
................................................................................
  int iCur;            /* Cursor number used for this index */
  int score;           /* How well this indexed scored */
  int brk;             /* Jump here to break out of the loop */
  int cont;            /* Jump here to continue with the next loop cycle */
  int op, p1, p2;      /* Opcode used to terminate the loop */
  int iLeftJoin;       /* Memory cell used to implement LEFT OUTER JOIN */
  int top;             /* First instruction of interior of the loop */
  int inOp, inP1, inP2;/* Opcode used to implement an IN operator */
};

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

Changes to src/vdbe.c.

26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
...
194
195
196
197
198
199
200

201
202
203
204
205
206
207
....
1062
1063
1064
1065
1066
1067
1068
1069
1070
1071
1072
1073
1074
1075
1076
1077
1078
1079
1080
1081
1082
1083
1084
1085
1086
1087
1088
....
1953
1954
1955
1956
1957
1958
1959
1960
1961
1962
1963
1964
1965
1966
1967
....
3014
3015
3016
3017
3018
3019
3020
3021
3022
3023
3024
3025
3026
3027
3028
3029
3030
3031
3032
3033
3034
3035
3036
3037
....
3080
3081
3082
3083
3084
3085
3086
3087
3088
3089
3090
3091
3092
3093
3094
....
3163
3164
3165
3166
3167
3168
3169
3170
3171
3172
3173
3174
3175
3176
3177
....
4771
4772
4773
4774
4775
4776
4777








































4778
4779
4780
4781
4782
4783
4784
** type to the other occurs as necessary.
** 
** Most of the code in this file is taken up by the sqliteVdbeExec()
** function which does the work of interpreting a VDBE program.
** But other routines are also provided to help in building up
** a program instruction by instruction.
**
** $Id: vdbe.c,v 1.153 2002/06/06 23:16:06 drh Exp $
*/
#include "sqliteInt.h"
#include <ctype.h>

/*
** The following global variable is incremented every time a cursor
** moves, either by the OP_MoveTo or the OP_Next opcode.  The test
................................................................................
** is part of a small set.  Sets are used to implement code like
** this:
**            x.y IN ('hi','hoo','hum')
*/
typedef struct Set Set;
struct Set {
  Hash hash;             /* A set is just a hash table */

};

/*
** A Keylist is a bunch of keys into a table.  The keylist can
** grow without bound.  The keylist stores the ROWIDs of database
** records that need to be deleted or updated.
*/
................................................................................
  "IdxGE",             "MemLoad",           "MemStore",          "ListWrite",
  "ListRewind",        "ListRead",          "ListReset",         "ListPush",
  "ListPop",           "SortPut",           "SortMakeRec",       "SortMakeKey",
  "Sort",              "SortNext",          "SortCallback",      "SortReset",
  "FileOpen",          "FileRead",          "FileColumn",        "AggReset",
  "AggFocus",          "AggNext",           "AggSet",            "AggGet",
  "AggFunc",           "AggInit",           "AggPush",           "AggPop",
  "SetInsert",         "SetFound",          "SetNotFound",       "MakeRecord",
  "MakeKey",           "MakeIdxKey",        "IncrKey",           "Goto",
  "If",                "IfNot",             "Halt",              "ColumnCount",
  "ColumnName",        "Callback",          "NullCallback",      "Integer",
  "String",            "Pop",               "Dup",               "Pull",
  "Push",              "MustBeInt",         "Add",               "AddImm",
  "Subtract",          "Multiply",          "Divide",            "Remainder",
  "BitAnd",            "BitOr",             "BitNot",            "ShiftLeft",
  "ShiftRight",        "AbsValue",          "Eq",                "Ne",
  "Lt",                "Le",                "Gt",                "Ge",
  "IsNull",            "NotNull",           "Negative",          "And",
  "Or",                "Not",               "Concat",            "Noop",
  "Function",          "Limit",           
};

/*
** Given the name of an opcode, return its number.  Return 0 if
** there is no match.
**
** This routine is used for testing and debugging.
................................................................................
  aStack[tos].i += pOp->p1;
  break;
}

/* Opcode: MustBeInt  * P2 *
** 
** Force the top of the stack to be an integer.  If the top of the
** stack is not an integer and cannot be comverted into an integer
** with out data loss, then jump immediately to P2, or if P2==0
** raise an SQLITE_MISMATCH exception.
*/
case OP_MustBeInt: {
  int tos = p->tos;
  VERIFY( if( tos<0 ) goto not_enough_stack; )
  if( aStack[tos].flags & STK_Int ){
................................................................................
** not exist in the table of cursor P1, then jump to P2.  If the record
** does already exist, then fall thru.  The cursor is left pointing
** at the record if it exists. The key is not popped from the stack.
**
** This operation is similar to NotFound except that this operation
** does not pop the key from the stack.
**
** See also: Found, NotFound, MoveTo
*/
/* Opcode: Found P1 P2 *
**
** Use the top of the stack as a string key.  If a record with that key
** does exist in table of P1, then jump to P2.  If the record
** does not exist, then fall thru.  The cursor is left pointing
** to the record if it exists.  The key is popped from the stack.
**
** See also: Distinct, NotFound, MoveTo
*/
/* Opcode: NotFound P1 P2 *
**
** Use the top of the stack as a string key.  If a record with that key
** does not exist in table of P1, then jump to P2.  If the record
** does exist, then fall thru.  The cursor is left pointing to the
** record if it exists.  The key is popped from the stack.
................................................................................
** index string matches K but the record number is different
** from R.  If there is no such entry, then there is an immediate
** jump to P2.  If any entry does exist where the index string
** matches K but the record number is not R, then the record
** number for that entry is pushed onto the stack and control
** falls through to the next instruction.
**
** See also: Distinct, NotFound, NotExists
*/
case OP_IsUnique: {
  int i = pOp->p1;
  int tos = p->tos;
  int nos = tos-1;
  BtCursor *pCrsr;
  int R;
................................................................................
** does exist, then fall thru.  The cursor is left pointing to the
** record if it exists.  The integer key is popped from the stack.
**
** The difference between this operation and NotFound is that this
** operation assumes the key is an integer and NotFound assumes it
** is a string.
**
** See also: Distinct, Found, MoveTo, NotExists
*/
case OP_NotExists: {
  int i = pOp->p1;
  int tos = p->tos;
  BtCursor *pCrsr;
  VERIFY( if( tos<0 ) goto not_enough_stack; )
  if( VERIFY( i>=0 && i<p->nCursor && ) (pCrsr = p->aCsr[i].pCursor)!=0 ){
................................................................................
       sqliteHashFind(&p->aSet[i].hash, zStack[tos], aStack[tos].n)==0 ){
    pc = pOp->p2 - 1;
  }
  POPSTACK;
  break;
}










































/* An other opcode is illegal...
*/
default: {
  sprintf(zBuf,"%d",pOp->opcode);
  sqliteSetString(pzErrMsg, "unknown opcode ", zBuf, 0);
  rc = SQLITE_INTERNAL;







|







 







>







 







|
|
|
|
|
|
|
|
|
|
|
|
|







 







|







 







|








|







 







|







 







|







 







>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>







26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
...
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
....
1063
1064
1065
1066
1067
1068
1069
1070
1071
1072
1073
1074
1075
1076
1077
1078
1079
1080
1081
1082
1083
1084
1085
1086
1087
1088
1089
....
1954
1955
1956
1957
1958
1959
1960
1961
1962
1963
1964
1965
1966
1967
1968
....
3015
3016
3017
3018
3019
3020
3021
3022
3023
3024
3025
3026
3027
3028
3029
3030
3031
3032
3033
3034
3035
3036
3037
3038
....
3081
3082
3083
3084
3085
3086
3087
3088
3089
3090
3091
3092
3093
3094
3095
....
3164
3165
3166
3167
3168
3169
3170
3171
3172
3173
3174
3175
3176
3177
3178
....
4772
4773
4774
4775
4776
4777
4778
4779
4780
4781
4782
4783
4784
4785
4786
4787
4788
4789
4790
4791
4792
4793
4794
4795
4796
4797
4798
4799
4800
4801
4802
4803
4804
4805
4806
4807
4808
4809
4810
4811
4812
4813
4814
4815
4816
4817
4818
4819
4820
4821
4822
4823
4824
4825
** type to the other occurs as necessary.
** 
** Most of the code in this file is taken up by the sqliteVdbeExec()
** function which does the work of interpreting a VDBE program.
** But other routines are also provided to help in building up
** a program instruction by instruction.
**
** $Id: vdbe.c,v 1.154 2002/06/08 23:25:09 drh Exp $
*/
#include "sqliteInt.h"
#include <ctype.h>

/*
** The following global variable is incremented every time a cursor
** moves, either by the OP_MoveTo or the OP_Next opcode.  The test
................................................................................
** is part of a small set.  Sets are used to implement code like
** this:
**            x.y IN ('hi','hoo','hum')
*/
typedef struct Set Set;
struct Set {
  Hash hash;             /* A set is just a hash table */
  HashElem *prev;        /* Previously accessed hash elemen */
};

/*
** A Keylist is a bunch of keys into a table.  The keylist can
** grow without bound.  The keylist stores the ROWIDs of database
** records that need to be deleted or updated.
*/
................................................................................
  "IdxGE",             "MemLoad",           "MemStore",          "ListWrite",
  "ListRewind",        "ListRead",          "ListReset",         "ListPush",
  "ListPop",           "SortPut",           "SortMakeRec",       "SortMakeKey",
  "Sort",              "SortNext",          "SortCallback",      "SortReset",
  "FileOpen",          "FileRead",          "FileColumn",        "AggReset",
  "AggFocus",          "AggNext",           "AggSet",            "AggGet",
  "AggFunc",           "AggInit",           "AggPush",           "AggPop",
  "SetInsert",         "SetFound",          "SetNotFound",       "SetFirst",
  "SetNext",           "MakeRecord",        "MakeKey",           "MakeIdxKey",
  "IncrKey",           "Goto",              "If",                "IfNot",
  "Halt",              "ColumnCount",       "ColumnName",        "Callback",
  "NullCallback",      "Integer",           "String",            "Pop",
  "Dup",               "Pull",              "Push",              "MustBeInt",
  "Add",               "AddImm",            "Subtract",          "Multiply",
  "Divide",            "Remainder",         "BitAnd",            "BitOr",
  "BitNot",            "ShiftLeft",         "ShiftRight",        "AbsValue",
  "Eq",                "Ne",                "Lt",                "Le",
  "Gt",                "Ge",                "IsNull",            "NotNull",
  "Negative",          "And",               "Or",                "Not",
  "Concat",            "Noop",              "Function",          "Limit",
};

/*
** Given the name of an opcode, return its number.  Return 0 if
** there is no match.
**
** This routine is used for testing and debugging.
................................................................................
  aStack[tos].i += pOp->p1;
  break;
}

/* Opcode: MustBeInt  * P2 *
** 
** Force the top of the stack to be an integer.  If the top of the
** stack is not an integer and cannot be converted into an integer
** with out data loss, then jump immediately to P2, or if P2==0
** raise an SQLITE_MISMATCH exception.
*/
case OP_MustBeInt: {
  int tos = p->tos;
  VERIFY( if( tos<0 ) goto not_enough_stack; )
  if( aStack[tos].flags & STK_Int ){
................................................................................
** not exist in the table of cursor P1, then jump to P2.  If the record
** does already exist, then fall thru.  The cursor is left pointing
** at the record if it exists. The key is not popped from the stack.
**
** This operation is similar to NotFound except that this operation
** does not pop the key from the stack.
**
** See also: Found, NotFound, MoveTo, IsUnique, NotExists
*/
/* Opcode: Found P1 P2 *
**
** Use the top of the stack as a string key.  If a record with that key
** does exist in table of P1, then jump to P2.  If the record
** does not exist, then fall thru.  The cursor is left pointing
** to the record if it exists.  The key is popped from the stack.
**
** See also: Distinct, NotFound, MoveTo, IsUnique, NotExists
*/
/* Opcode: NotFound P1 P2 *
**
** Use the top of the stack as a string key.  If a record with that key
** does not exist in table of P1, then jump to P2.  If the record
** does exist, then fall thru.  The cursor is left pointing to the
** record if it exists.  The key is popped from the stack.
................................................................................
** index string matches K but the record number is different
** from R.  If there is no such entry, then there is an immediate
** jump to P2.  If any entry does exist where the index string
** matches K but the record number is not R, then the record
** number for that entry is pushed onto the stack and control
** falls through to the next instruction.
**
** See also: Distinct, NotFound, NotExists, Found
*/
case OP_IsUnique: {
  int i = pOp->p1;
  int tos = p->tos;
  int nos = tos-1;
  BtCursor *pCrsr;
  int R;
................................................................................
** does exist, then fall thru.  The cursor is left pointing to the
** record if it exists.  The integer key is popped from the stack.
**
** The difference between this operation and NotFound is that this
** operation assumes the key is an integer and NotFound assumes it
** is a string.
**
** See also: Distinct, Found, MoveTo, NotFound, IsUnique
*/
case OP_NotExists: {
  int i = pOp->p1;
  int tos = p->tos;
  BtCursor *pCrsr;
  VERIFY( if( tos<0 ) goto not_enough_stack; )
  if( VERIFY( i>=0 && i<p->nCursor && ) (pCrsr = p->aCsr[i].pCursor)!=0 ){
................................................................................
       sqliteHashFind(&p->aSet[i].hash, zStack[tos], aStack[tos].n)==0 ){
    pc = pOp->p2 - 1;
  }
  POPSTACK;
  break;
}

/* Opcode: SetFirst P1 P2 *
**
** Read the first element from set P1 and push it onto the stack.  If the
** set is empty, push nothing and jump immediately to P2.  This opcode is
** used in combination with OP_SetNext to loop over all elements of a set.
*/
/* Opcode: SetNext P1 P2 *
**
** Read the next element from set P1 and push it onto the stack.  If there
** are no more elements in the set, do not do the push and fall through.
** Otherwise, jump to P2 after pushing the next set element.
*/
case OP_SetFirst: 
case OP_SetNext: {
  Set *pSet;
  int tos;
  VERIFY( if( pOp->p1<0 || pOp->p1>=p->nSet ) goto bad_instruction; )
  pSet = &p->aSet[pOp->p1];
  if( pOp->opcode==OP_SetFirst ){
    pSet->prev = sqliteHashFirst(&pSet->hash);
    if( pSet->prev==0 ){
      pc = pOp->p2 - 1;
      break;
    }
  }else{
    VERIFY( if( pSet->prev==0 ) goto bad_instruction; )
    pSet->prev = sqliteHashNext(pSet->prev);
    if( pSet->prev==0 ){
      break;
    }else{
      pc = pOp->p2 - 1;
    }
  }
  tos = ++p->tos;
  VERIFY( if( NeedStack(p, p->tos) ) goto no_mem; )
  zStack[tos] = sqliteHashKey(pSet->prev);
  aStack[tos].n = sqliteHashKeysize(pSet->prev);
  aStack[tos].flags = STK_Str | STK_Static;
  break;
}

/* An other opcode is illegal...
*/
default: {
  sprintf(zBuf,"%d",pOp->opcode);
  sqliteSetString(pzErrMsg, "unknown opcode ", zBuf, 0);
  rc = SQLITE_INTERNAL;

Changes to src/vdbe.h.

11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
...
145
146
147
148
149
150
151


152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
*************************************************************************
** Header file for the Virtual DataBase Engine (VDBE)
**
** This header defines the interface to the virtual database engine
** or VDBE.  The VDBE implements an abstract machine that runs a
** simple program to access and modify the underlying database.
**
** $Id: vdbe.h,v 1.53 2002/05/26 20:54:34 drh Exp $
*/
#ifndef _SQLITE_VDBE_H_
#define _SQLITE_VDBE_H_
#include <stdio.h>

/*
** A single VDBE is an opaque structure named "Vdbe".  Only routines
................................................................................
#define OP_AggInit            66
#define OP_AggPush            67
#define OP_AggPop             68

#define OP_SetInsert          69
#define OP_SetFound           70
#define OP_SetNotFound        71



#define OP_MakeRecord         72
#define OP_MakeKey            73
#define OP_MakeIdxKey         74
#define OP_IncrKey            75

#define OP_Goto               76
#define OP_If                 77
#define OP_IfNot              78
#define OP_Halt               79

#define OP_ColumnCount        80
#define OP_ColumnName         81
#define OP_Callback           82
#define OP_NullCallback       83

#define OP_Integer            84
#define OP_String             85
#define OP_Pop                86
#define OP_Dup                87
#define OP_Pull               88
#define OP_Push               89
#define OP_MustBeInt          90

#define OP_Add                91
#define OP_AddImm             92
#define OP_Subtract           93
#define OP_Multiply           94
#define OP_Divide             95
#define OP_Remainder          96
#define OP_BitAnd             97
#define OP_BitOr              98
#define OP_BitNot             99
#define OP_ShiftLeft         100
#define OP_ShiftRight        101
#define OP_AbsValue          102
#define OP_Eq                103
#define OP_Ne                104
#define OP_Lt                105
#define OP_Le                106
#define OP_Gt                107
#define OP_Ge                108
#define OP_IsNull            109
#define OP_NotNull           110
#define OP_Negative          111
#define OP_And               112
#define OP_Or                113
#define OP_Not               114
#define OP_Concat            115
#define OP_Noop              116
#define OP_Function          117

#define OP_Limit             118


#define OP_MAX               118

/*
** Prototypes for the VDBE interface.  See comments on the implementation
** for a description of what each of these routines does.
*/
Vdbe *sqliteVdbeCreate(sqlite*);
void sqliteVdbeCreateCallback(Vdbe*, int*);







|







 







>
>

|
|
|
|

|
|
|
|

|
|
|
|

|
|
|
|
|
|
|

|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|

|


|







11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
...
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
*************************************************************************
** Header file for the Virtual DataBase Engine (VDBE)
**
** This header defines the interface to the virtual database engine
** or VDBE.  The VDBE implements an abstract machine that runs a
** simple program to access and modify the underlying database.
**
** $Id: vdbe.h,v 1.54 2002/06/08 23:25:09 drh Exp $
*/
#ifndef _SQLITE_VDBE_H_
#define _SQLITE_VDBE_H_
#include <stdio.h>

/*
** A single VDBE is an opaque structure named "Vdbe".  Only routines
................................................................................
#define OP_AggInit            66
#define OP_AggPush            67
#define OP_AggPop             68

#define OP_SetInsert          69
#define OP_SetFound           70
#define OP_SetNotFound        71
#define OP_SetFirst           72
#define OP_SetNext            73

#define OP_MakeRecord         74
#define OP_MakeKey            75
#define OP_MakeIdxKey         76
#define OP_IncrKey            77

#define OP_Goto               78
#define OP_If                 79
#define OP_IfNot              80
#define OP_Halt               81

#define OP_ColumnCount        82
#define OP_ColumnName         83
#define OP_Callback           84
#define OP_NullCallback       85

#define OP_Integer            86
#define OP_String             87
#define OP_Pop                88
#define OP_Dup                89
#define OP_Pull               90
#define OP_Push               91
#define OP_MustBeInt          92

#define OP_Add                93
#define OP_AddImm             94
#define OP_Subtract           95
#define OP_Multiply           96
#define OP_Divide             97
#define OP_Remainder          98
#define OP_BitAnd             99
#define OP_BitOr             100
#define OP_BitNot            101
#define OP_ShiftLeft         102
#define OP_ShiftRight        103
#define OP_AbsValue          104
#define OP_Eq                105
#define OP_Ne                106
#define OP_Lt                107
#define OP_Le                108
#define OP_Gt                109
#define OP_Ge                110
#define OP_IsNull            111
#define OP_NotNull           112
#define OP_Negative          113
#define OP_And               114
#define OP_Or                115
#define OP_Not               116
#define OP_Concat            117
#define OP_Noop              118
#define OP_Function          119

#define OP_Limit             120


#define OP_MAX               120

/*
** Prototypes for the VDBE interface.  See comments on the implementation
** for a description of what each of these routines does.
*/
Vdbe *sqliteVdbeCreate(sqlite*);
void sqliteVdbeCreateCallback(Vdbe*, int*);

Changes to src/where.c.

9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
...
108
109
110
111
112
113
114

115
116
117
118
119
120
121
...
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
...
284
285
286
287
288
289
290

291
292
293
294
295
296
297
...
325
326
327
328
329
330
331



332
333
334
335
336
337
338
...
342
343
344
345
346
347
348

349
350
351
352
353
354
355
...
463
464
465
466
467
468
469

470
471
472
473
474
475
476
477

478


479













480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509

510
511

512
513
514
515
516
517

518
519
520


















521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
...
830
831
832
833
834
835
836



837
838
839
840
841
842
843
**    May you share freely, never taking more than you give.
**
*************************************************************************
** This module contains C code that generates VDBE code used to process
** the WHERE clause of SQL statements.  Also found here are subroutines
** to generate VDBE code to evaluate expressions.
**
** $Id: where.c,v 1.48 2002/05/26 20:54:34 drh Exp $
*/
#include "sqliteInt.h"

/*
** The query generator uses an array of instances of this structure to
** help it analyze the subexpressions of the WHERE clause.  Each WHERE
** clause subexpression is separated from the others by an AND operator.
................................................................................
static int allowedOp(int op){
  switch( op ){
    case TK_LT:
    case TK_LE:
    case TK_GT:
    case TK_GE:
    case TK_EQ:

      return 1;
    default:
      return 0;
  }
}

/*
................................................................................
  pInfo->prereqLeft = exprTableUsage(base, pExpr->pLeft);
  pInfo->prereqRight = exprTableUsage(base, pExpr->pRight);
  pInfo->prereqAll = exprTableUsage(base, pExpr);
  pInfo->indexable = 0;
  pInfo->idxLeft = -1;
  pInfo->idxRight = -1;
  if( allowedOp(pExpr->op) && (pInfo->prereqRight & pInfo->prereqLeft)==0 ){
    if( pExpr->pRight->op==TK_COLUMN ){
      pInfo->idxRight = pExpr->pRight->iTable - base;
      pInfo->indexable = 1;
    }
    if( pExpr->pLeft->op==TK_COLUMN ){
      pInfo->idxLeft = pExpr->pLeft->iTable - base;
      pInfo->indexable = 1;
    }
................................................................................
    iDirectEq[i] = -1;
    iDirectLt[i] = -1;
    iDirectGt[i] = -1;
    for(j=0; j<nExpr; j++){
      if( aExpr[j].idxLeft==idx && aExpr[j].p->pLeft->iColumn<0
            && (aExpr[j].prereqRight & loopMask)==aExpr[j].prereqRight ){
        switch( aExpr[j].p->op ){

          case TK_EQ: iDirectEq[i] = j; break;
          case TK_LE:
          case TK_LT: iDirectLt[i] = j; break;
          case TK_GE:
          case TK_GT: iDirectGt[i] = j;  break;
        }
      }
................................................................................
    **
    ** This scoring system is designed so that the score can later be
    ** used to determine how the index is used.  If the score&3 is 0
    ** then all constraints are equalities.  If score&1 is not 0 then
    ** there is an inequality used as a termination key.  (ex: "x<...")
    ** If score&2 is not 0 then there is an inequality used as the
    ** start key.  (ex: "x>...");



    */
    for(pIdx=pTab->pIndex; pIdx; pIdx=pIdx->pNext){
      int eqMask = 0;  /* Index columns covered by an x=... constraint */
      int ltMask = 0;  /* Index columns covered by an x<... constraint */
      int gtMask = 0;  /* Index columns covered by an x>... constraing */
      int nEq, m, score;

................................................................................
        if( aExpr[j].idxLeft==idx 
             && (aExpr[j].prereqRight & loopMask)==aExpr[j].prereqRight ){
          int iColumn = aExpr[j].p->pLeft->iColumn;
          int k;
          for(k=0; k<pIdx->nColumn; k++){
            if( pIdx->aiColumn[k]==iColumn ){
              switch( aExpr[j].p->op ){

                case TK_EQ: {
                  eqMask |= 1<<k;
                  break;
                }
                case TK_LE:
                case TK_LT: {
                  ltMask |= 1<<k;
................................................................................
      if( !pParse->nMem ) pParse->nMem++;
      pLevel->iLeftJoin = pParse->nMem++;
      sqliteVdbeAddOp(v, OP_String, 0, 0);
      sqliteVdbeAddOp(v, OP_MemStore, pLevel->iLeftJoin, 1);
    }

    pIdx = pLevel->pIdx;

    if( i<ARRAYSIZE(iDirectEq) && iDirectEq[i]>=0 ){
      /* Case 1:  We can directly reference a single row using an
      **          equality comparison against the ROWID field.
      */
      k = iDirectEq[i];
      assert( k<nExpr );
      assert( aExpr[k].p!=0 );
      assert( aExpr[k].idxLeft==idx || aExpr[k].idxRight==idx );

      if( aExpr[k].idxLeft==idx ){


        sqliteExprCode(pParse, aExpr[k].p->pRight);













      }else{
        sqliteExprCode(pParse, aExpr[k].p->pLeft);
      }
      aExpr[k].p = 0;
      brk = pLevel->brk = sqliteVdbeMakeLabel(v);
      cont = pLevel->cont = brk;
      sqliteVdbeAddOp(v, OP_MustBeInt, 0, brk);
      if( i==pTabList->nSrc-1 && pushKey ){
        /* Note: The OP_Dup below will cause the recno to be left on the
        ** stack if the record does not exists and the OP_NotExists jump is
        ** taken.  This violates a general rule of the VDBE that you should
        ** never leave values on the stack in order to avoid a stack overflow.
        ** But in this case, the OP_Dup will never happen inside of a loop,
        ** because the pushKey flag is only true for UPDATE and DELETE, not
        ** for SELECT, and nested loops only occur on a SELECT.
        ** So it is safe to leave the recno on the stack.
        */
        haveKey = 1;
        sqliteVdbeAddOp(v, OP_Dup, 0, 0);
      }else{
        haveKey = 0;
      }
      sqliteVdbeAddOp(v, OP_NotExists, base+idx, brk);
      pLevel->op = OP_Noop;
    }else if( pIdx!=0 && pLevel->score%4==0 ){
      /* Case 2:  All index constraints are equality operators.
      */
      int start;
      int testOp;
      int nColumn = pLevel->score/4;

      for(j=0; j<nColumn; j++){
        for(k=0; k<nExpr; k++){

          if( aExpr[k].p==0 ) continue;
          if( aExpr[k].idxLeft==idx 
             && aExpr[k].p->op==TK_EQ
             && (aExpr[k].prereqRight & loopMask)==aExpr[k].prereqRight 
             && aExpr[k].p->pLeft->iColumn==pIdx->aiColumn[j]
          ){

            sqliteExprCode(pParse, aExpr[k].p->pRight);
            aExpr[k].p = 0;
            break;


















          }
          if( aExpr[k].idxRight==idx 
             && aExpr[k].p->op==TK_EQ
             && (aExpr[k].prereqLeft & loopMask)==aExpr[k].prereqLeft
             && aExpr[k].p->pRight->iColumn==pIdx->aiColumn[j]
          ){
            sqliteExprCode(pParse, aExpr[k].p->pLeft);
            aExpr[k].p = 0;
            break;
          }
        }
      }
      pLevel->iMem = pParse->nMem++;
      brk = pLevel->brk = sqliteVdbeMakeLabel(v);
      cont = pLevel->cont = sqliteVdbeMakeLabel(v);
      sqliteVdbeAddOp(v, OP_MakeKey, nColumn, 0);
      if( nColumn==pIdx->nColumn ){
        sqliteVdbeAddOp(v, OP_MemStore, pLevel->iMem, 0);
        testOp = OP_IdxGT;
      }else{
        sqliteVdbeAddOp(v, OP_Dup, 0, 0);
................................................................................
  for(i=pTabList->nSrc-1; i>=0; i--){
    pLevel = &pWInfo->a[i];
    sqliteVdbeResolveLabel(v, pLevel->cont);
    if( pLevel->op!=OP_Noop ){
      sqliteVdbeAddOp(v, pLevel->op, pLevel->p1, pLevel->p2);
    }
    sqliteVdbeResolveLabel(v, pLevel->brk);



    if( pLevel->iLeftJoin ){
      int addr;
      addr = sqliteVdbeAddOp(v, OP_MemLoad, pLevel->iLeftJoin, 0);
      sqliteVdbeAddOp(v, OP_NotNull, 0, addr+4);
      sqliteVdbeAddOp(v, OP_NullRow, base+i, 0);
      sqliteVdbeAddOp(v, OP_Goto, 0, pLevel->top);
    }







|







 







>







 







|







 







>







 







>
>
>







 







>







 







>








>

>
>
|
>
>
>
>
>
>
>
>
>
>
>
>
>




<
|

<
<
<
<
<
<
<
<
<
<
<
<
<
|
<








>


>
|

<

|

>
|
|
|
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>













<







 







>
>
>







9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
...
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
...
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
...
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
...
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
...
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
...
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506

507
508













509

510
511
512
513
514
515
516
517
518
519
520
521
522
523

524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561

562
563
564
565
566
567
568
...
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
**    May you share freely, never taking more than you give.
**
*************************************************************************
** This module contains C code that generates VDBE code used to process
** the WHERE clause of SQL statements.  Also found here are subroutines
** to generate VDBE code to evaluate expressions.
**
** $Id: where.c,v 1.49 2002/06/08 23:25:10 drh Exp $
*/
#include "sqliteInt.h"

/*
** The query generator uses an array of instances of this structure to
** help it analyze the subexpressions of the WHERE clause.  Each WHERE
** clause subexpression is separated from the others by an AND operator.
................................................................................
static int allowedOp(int op){
  switch( op ){
    case TK_LT:
    case TK_LE:
    case TK_GT:
    case TK_GE:
    case TK_EQ:
    case TK_IN:
      return 1;
    default:
      return 0;
  }
}

/*
................................................................................
  pInfo->prereqLeft = exprTableUsage(base, pExpr->pLeft);
  pInfo->prereqRight = exprTableUsage(base, pExpr->pRight);
  pInfo->prereqAll = exprTableUsage(base, pExpr);
  pInfo->indexable = 0;
  pInfo->idxLeft = -1;
  pInfo->idxRight = -1;
  if( allowedOp(pExpr->op) && (pInfo->prereqRight & pInfo->prereqLeft)==0 ){
    if( pExpr->pRight && pExpr->pRight->op==TK_COLUMN ){
      pInfo->idxRight = pExpr->pRight->iTable - base;
      pInfo->indexable = 1;
    }
    if( pExpr->pLeft->op==TK_COLUMN ){
      pInfo->idxLeft = pExpr->pLeft->iTable - base;
      pInfo->indexable = 1;
    }
................................................................................
    iDirectEq[i] = -1;
    iDirectLt[i] = -1;
    iDirectGt[i] = -1;
    for(j=0; j<nExpr; j++){
      if( aExpr[j].idxLeft==idx && aExpr[j].p->pLeft->iColumn<0
            && (aExpr[j].prereqRight & loopMask)==aExpr[j].prereqRight ){
        switch( aExpr[j].p->op ){
          case TK_IN:
          case TK_EQ: iDirectEq[i] = j; break;
          case TK_LE:
          case TK_LT: iDirectLt[i] = j; break;
          case TK_GE:
          case TK_GT: iDirectGt[i] = j;  break;
        }
      }
................................................................................
    **
    ** This scoring system is designed so that the score can later be
    ** used to determine how the index is used.  If the score&3 is 0
    ** then all constraints are equalities.  If score&1 is not 0 then
    ** there is an inequality used as a termination key.  (ex: "x<...")
    ** If score&2 is not 0 then there is an inequality used as the
    ** start key.  (ex: "x>...");
    **
    ** The IN operator as in "<expr> IN (...)" is treated the same as
    ** an equality comparison.
    */
    for(pIdx=pTab->pIndex; pIdx; pIdx=pIdx->pNext){
      int eqMask = 0;  /* Index columns covered by an x=... constraint */
      int ltMask = 0;  /* Index columns covered by an x<... constraint */
      int gtMask = 0;  /* Index columns covered by an x>... constraing */
      int nEq, m, score;

................................................................................
        if( aExpr[j].idxLeft==idx 
             && (aExpr[j].prereqRight & loopMask)==aExpr[j].prereqRight ){
          int iColumn = aExpr[j].p->pLeft->iColumn;
          int k;
          for(k=0; k<pIdx->nColumn; k++){
            if( pIdx->aiColumn[k]==iColumn ){
              switch( aExpr[j].p->op ){
                case TK_IN:
                case TK_EQ: {
                  eqMask |= 1<<k;
                  break;
                }
                case TK_LE:
                case TK_LT: {
                  ltMask |= 1<<k;
................................................................................
      if( !pParse->nMem ) pParse->nMem++;
      pLevel->iLeftJoin = pParse->nMem++;
      sqliteVdbeAddOp(v, OP_String, 0, 0);
      sqliteVdbeAddOp(v, OP_MemStore, pLevel->iLeftJoin, 1);
    }

    pIdx = pLevel->pIdx;
    pLevel->inOp = OP_Noop;
    if( i<ARRAYSIZE(iDirectEq) && iDirectEq[i]>=0 ){
      /* Case 1:  We can directly reference a single row using an
      **          equality comparison against the ROWID field.
      */
      k = iDirectEq[i];
      assert( k<nExpr );
      assert( aExpr[k].p!=0 );
      assert( aExpr[k].idxLeft==idx || aExpr[k].idxRight==idx );
      brk = pLevel->brk = sqliteVdbeMakeLabel(v);
      if( aExpr[k].idxLeft==idx ){
        Expr *pX = aExpr[k].p;
        if( pX->op!=TK_IN ){
          sqliteExprCode(pParse, aExpr[k].p->pRight);
        }else if( pX->pList ){
          sqliteVdbeAddOp(v, OP_SetFirst, pX->iTable, brk);
          pLevel->inOp = OP_SetNext;
          pLevel->inP1 = pX->iTable;
          pLevel->inP2 = sqliteVdbeCurrentAddr(v);
        }else{
          assert( pX->pSelect );
          sqliteVdbeAddOp(v, OP_Rewind, pX->iTable, brk);
          sqliteVdbeAddOp(v, OP_KeyAsData, pX->iTable, 1);
          pLevel->inP2 = sqliteVdbeAddOp(v, OP_FullKey, pX->iTable, 0);
          pLevel->inOp = OP_Next;
          pLevel->inP1 = pX->iTable;
        }
      }else{
        sqliteExprCode(pParse, aExpr[k].p->pLeft);
      }
      aExpr[k].p = 0;

      cont = pLevel->cont = sqliteVdbeMakeLabel(v);
      sqliteVdbeAddOp(v, OP_MustBeInt, 0, brk);













      haveKey = 0;

      sqliteVdbeAddOp(v, OP_NotExists, base+idx, brk);
      pLevel->op = OP_Noop;
    }else if( pIdx!=0 && pLevel->score%4==0 ){
      /* Case 2:  All index constraints are equality operators.
      */
      int start;
      int testOp;
      int nColumn = pLevel->score/4;
      brk = pLevel->brk = sqliteVdbeMakeLabel(v);
      for(j=0; j<nColumn; j++){
        for(k=0; k<nExpr; k++){
          Expr *pX = aExpr[k].p;
          if( pX==0 ) continue;
          if( aExpr[k].idxLeft==idx 

             && (aExpr[k].prereqRight & loopMask)==aExpr[k].prereqRight 
             && pX->pLeft->iColumn==pIdx->aiColumn[j]
          ){
            if( pX->op==TK_EQ ){
              sqliteExprCode(pParse, pX->pRight);
              aExpr[k].p = 0;
              break;
            }
            if( pX->op==TK_IN && nColumn==1 ){
              if( pX->pList ){
                sqliteVdbeAddOp(v, OP_SetFirst, pX->iTable, brk);
                pLevel->inOp = OP_SetNext;
                pLevel->inP1 = pX->iTable;
                pLevel->inP2 = sqliteVdbeCurrentAddr(v);
              }else{
                assert( pX->pSelect );
                sqliteVdbeAddOp(v, OP_Rewind, pX->iTable, brk);
                sqliteVdbeAddOp(v, OP_KeyAsData, pX->iTable, 1);
                pLevel->inP2 = sqliteVdbeAddOp(v, OP_FullKey, pX->iTable, 0);
                pLevel->inOp = OP_Next;
                pLevel->inP1 = pX->iTable;
              }
              aExpr[k].p = 0;
              break;
            }
          }
          if( aExpr[k].idxRight==idx 
             && aExpr[k].p->op==TK_EQ
             && (aExpr[k].prereqLeft & loopMask)==aExpr[k].prereqLeft
             && aExpr[k].p->pRight->iColumn==pIdx->aiColumn[j]
          ){
            sqliteExprCode(pParse, aExpr[k].p->pLeft);
            aExpr[k].p = 0;
            break;
          }
        }
      }
      pLevel->iMem = pParse->nMem++;

      cont = pLevel->cont = sqliteVdbeMakeLabel(v);
      sqliteVdbeAddOp(v, OP_MakeKey, nColumn, 0);
      if( nColumn==pIdx->nColumn ){
        sqliteVdbeAddOp(v, OP_MemStore, pLevel->iMem, 0);
        testOp = OP_IdxGT;
      }else{
        sqliteVdbeAddOp(v, OP_Dup, 0, 0);
................................................................................
  for(i=pTabList->nSrc-1; i>=0; i--){
    pLevel = &pWInfo->a[i];
    sqliteVdbeResolveLabel(v, pLevel->cont);
    if( pLevel->op!=OP_Noop ){
      sqliteVdbeAddOp(v, pLevel->op, pLevel->p1, pLevel->p2);
    }
    sqliteVdbeResolveLabel(v, pLevel->brk);
    if( pLevel->inOp!=OP_Noop ){
      sqliteVdbeAddOp(v, pLevel->inOp, pLevel->inP1, pLevel->inP2);
    }
    if( pLevel->iLeftJoin ){
      int addr;
      addr = sqliteVdbeAddOp(v, OP_MemLoad, pLevel->iLeftJoin, 0);
      sqliteVdbeAddOp(v, OP_NotNull, 0, addr+4);
      sqliteVdbeAddOp(v, OP_NullRow, base+i, 0);
      sqliteVdbeAddOp(v, OP_Goto, 0, pLevel->top);
    }