/ Check-in [f61e4cd9]
Login
SQLite training in Houston TX on 2019-11-05 (details)
Part of the 2019 Tcl Conference

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

Overview
Comment:Attempt to optimize virtual table queries with 'OR' expressions in the WHERE clause. (CVS 6527)
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1: f61e4cd93682fd98bea2a71d346f9eaa68454390
User & Date: danielk1977 2009-04-21 09:02:46
Context
2009-04-21
12:02
Remove a redundant test from sqlite3_shutdown(). (CVS 6528) check-in: 6f481ceb user: drh tags: trunk
09:02
Attempt to optimize virtual table queries with 'OR' expressions in the WHERE clause. (CVS 6527) check-in: f61e4cd9 user: danielk1977 tags: trunk
2009-04-20
17:43
Change the journal_mode pragma so that it always returns the current journal mode, even on a failed attempt to change the journal mode. Allow the journal mode to be changed as long as there is not a pending transaction. Ticket #3811. (CVS 6526) check-in: 419e320a user: drh tags: trunk
Changes
Hide Diffs Unified Diffs Ignore Whitespace Patch

Changes to Makefile.in.

168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
...
245
246
247
248
249
250
251

252
253
254
255
256
257
258
...
667
668
669
670
671
672
673



674
675
676
677
678
679
680
        delete.lo expr.lo fault.lo func.lo global.lo \
        hash.lo journal.lo insert.lo legacy.lo loadext.lo \
        main.lo malloc.lo mem0.lo mem1.lo mem2.lo mem3.lo mem5.lo \
        memjournal.lo \
        mutex.lo mutex_noop.lo mutex_os2.lo mutex_unix.lo mutex_w32.lo \
        notify.lo opcodes.lo os.lo os_unix.lo os_win.lo os_os2.lo \
        pager.lo parse.lo pcache.lo pcache1.lo pragma.lo prepare.lo printf.lo \
        random.lo resolve.lo rowset.lo select.lo status.lo \
        table.lo tokenize.lo trigger.lo update.lo \
        util.lo vacuum.lo \
        vdbe.lo vdbeapi.lo vdbeaux.lo vdbeblob.lo vdbemem.lo \
        walker.lo where.lo utf.lo vtab.lo

# Object files for the amalgamation.
#
................................................................................
  $(TOP)/src/pcache.h \
  $(TOP)/src/pcache1.c \
  $(TOP)/src/pragma.c \
  $(TOP)/src/prepare.c \
  $(TOP)/src/printf.c \
  $(TOP)/src/random.c \
  $(TOP)/src/resolve.c \

  $(TOP)/src/rowset.c \
  $(TOP)/src/select.c \
  $(TOP)/src/status.c \
  $(TOP)/src/shell.c \
  $(TOP)/src/sqlite.h.in \
  $(TOP)/src/sqlite3ext.h \
  $(TOP)/src/sqliteInt.h \
................................................................................

random.lo:	$(TOP)/src/random.c $(HDR)
	$(LTCOMPILE) $(TEMP_STORE) -c $(TOP)/src/random.c

resolve.lo:	$(TOP)/src/resolve.c $(HDR)
	$(LTCOMPILE) $(TEMP_STORE) -c $(TOP)/src/resolve.c




rowset.lo:	$(TOP)/src/rowset.c $(HDR)
	$(LTCOMPILE) $(TEMP_STORE) -c $(TOP)/src/rowset.c

select.lo:	$(TOP)/src/select.c $(HDR)
	$(LTCOMPILE) $(TEMP_STORE) -c $(TOP)/src/select.c

status.lo:	$(TOP)/src/status.c $(HDR)







|







 







>







 







>
>
>







168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
...
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
...
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
        delete.lo expr.lo fault.lo func.lo global.lo \
        hash.lo journal.lo insert.lo legacy.lo loadext.lo \
        main.lo malloc.lo mem0.lo mem1.lo mem2.lo mem3.lo mem5.lo \
        memjournal.lo \
        mutex.lo mutex_noop.lo mutex_os2.lo mutex_unix.lo mutex_w32.lo \
        notify.lo opcodes.lo os.lo os_unix.lo os_win.lo os_os2.lo \
        pager.lo parse.lo pcache.lo pcache1.lo pragma.lo prepare.lo printf.lo \
        random.lo resolve.lo rowhash.lo rowset.lo select.lo status.lo \
        table.lo tokenize.lo trigger.lo update.lo \
        util.lo vacuum.lo \
        vdbe.lo vdbeapi.lo vdbeaux.lo vdbeblob.lo vdbemem.lo \
        walker.lo where.lo utf.lo vtab.lo

# Object files for the amalgamation.
#
................................................................................
  $(TOP)/src/pcache.h \
  $(TOP)/src/pcache1.c \
  $(TOP)/src/pragma.c \
  $(TOP)/src/prepare.c \
  $(TOP)/src/printf.c \
  $(TOP)/src/random.c \
  $(TOP)/src/resolve.c \
  $(TOP)/src/rowhash.c \
  $(TOP)/src/rowset.c \
  $(TOP)/src/select.c \
  $(TOP)/src/status.c \
  $(TOP)/src/shell.c \
  $(TOP)/src/sqlite.h.in \
  $(TOP)/src/sqlite3ext.h \
  $(TOP)/src/sqliteInt.h \
................................................................................

random.lo:	$(TOP)/src/random.c $(HDR)
	$(LTCOMPILE) $(TEMP_STORE) -c $(TOP)/src/random.c

resolve.lo:	$(TOP)/src/resolve.c $(HDR)
	$(LTCOMPILE) $(TEMP_STORE) -c $(TOP)/src/resolve.c

rowhash.lo:	$(TOP)/src/rowhash.c $(HDR)
	$(LTCOMPILE) $(TEMP_STORE) -c $(TOP)/src/rowhash.c

rowset.lo:	$(TOP)/src/rowset.c $(HDR)
	$(LTCOMPILE) $(TEMP_STORE) -c $(TOP)/src/rowset.c

select.lo:	$(TOP)/src/select.c $(HDR)
	$(LTCOMPILE) $(TEMP_STORE) -c $(TOP)/src/select.c

status.lo:	$(TOP)/src/status.c $(HDR)

Changes to main.mk.

57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
...
126
127
128
129
130
131
132

133
134
135
136
137
138
139
         func.o global.o hash.o \
         icu.o insert.o journal.o legacy.o loadext.o \
         main.o malloc.o mem0.o mem1.o mem2.o mem3.o mem5.o \
         memjournal.o \
         mutex.o mutex_noop.o mutex_os2.o mutex_unix.o mutex_w32.o \
         notify.o opcodes.o os.o os_os2.o os_unix.o os_win.o \
         pager.o parse.o pcache.o pcache1.o pragma.o prepare.o printf.o \
         random.o resolve.o rowset.o rtree.o select.o status.o \
         table.o tokenize.o trigger.o \
         update.o util.o vacuum.o \
         vdbe.o vdbeapi.o vdbeaux.o vdbeblob.o vdbemem.o \
         walker.o where.o utf.o vtab.o



................................................................................
  $(TOP)/src/pcache.h \
  $(TOP)/src/pcache1.c \
  $(TOP)/src/pragma.c \
  $(TOP)/src/prepare.c \
  $(TOP)/src/printf.c \
  $(TOP)/src/random.c \
  $(TOP)/src/resolve.c \

  $(TOP)/src/rowset.c \
  $(TOP)/src/select.c \
  $(TOP)/src/status.c \
  $(TOP)/src/shell.c \
  $(TOP)/src/sqlite.h.in \
  $(TOP)/src/sqlite3ext.h \
  $(TOP)/src/sqliteInt.h \







|







 







>







57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
...
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
         func.o global.o hash.o \
         icu.o insert.o journal.o legacy.o loadext.o \
         main.o malloc.o mem0.o mem1.o mem2.o mem3.o mem5.o \
         memjournal.o \
         mutex.o mutex_noop.o mutex_os2.o mutex_unix.o mutex_w32.o \
         notify.o opcodes.o os.o os_os2.o os_unix.o os_win.o \
         pager.o parse.o pcache.o pcache1.o pragma.o prepare.o printf.o \
         random.o resolve.o rowhash.o rowset.o rtree.o select.o status.o \
         table.o tokenize.o trigger.o \
         update.o util.o vacuum.o \
         vdbe.o vdbeapi.o vdbeaux.o vdbeblob.o vdbemem.o \
         walker.o where.o utf.o vtab.o



................................................................................
  $(TOP)/src/pcache.h \
  $(TOP)/src/pcache1.c \
  $(TOP)/src/pragma.c \
  $(TOP)/src/prepare.c \
  $(TOP)/src/printf.c \
  $(TOP)/src/random.c \
  $(TOP)/src/resolve.c \
  $(TOP)/src/rowhash.c \
  $(TOP)/src/rowset.c \
  $(TOP)/src/select.c \
  $(TOP)/src/status.c \
  $(TOP)/src/shell.c \
  $(TOP)/src/sqlite.h.in \
  $(TOP)/src/sqlite3ext.h \
  $(TOP)/src/sqliteInt.h \

Added src/rowhash.c.



































































































































































































































































































































































































































































































































































































































































>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
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
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
/*
** 2009 April 15
**
** The author disclaims copyright to this source code.  In place of
** a legal notice, here is a blessing:
**
**    May you do good and not evil.
**    May you find forgiveness for yourself and forgive others.
**    May you share freely, never taking more than you give.
**
*************************************************************************
**
** This file contains the implementation of the "row-hash" data structure.
**
** $Id: rowhash.c,v 1.1 2009/04/21 09:02:47 danielk1977 Exp $
*/
#include "sqliteInt.h"

typedef struct RowHashElem RowHashElem;
typedef struct RowHashBlock RowHashBlock;

/*
** Size of heap allocations made by this module. This limit is 
** never exceeded.
*/
#define ROWHASH_ALLOCATION 1024

/*
** Number of elements in the RowHashBlock.aElem[] array. This array is
** sized to make RowHashBlock very close to (without exceeding)
** ROWHASH_ALLOCATION bytes in size.
*/
#define ROWHASH_ELEM_PER_BLOCK (                                            \
    (ROWHASH_ALLOCATION - ROUND8(sizeof(struct RowHashBlockData))) /        \
    sizeof(RowHashElem)                                                     \
)

/*
** Number of pointers that fit into a single allocation of 
** ROWHASH_ALLOCATION bytes.
*/
#define ROWHASH_POINTER_PER_PAGE (ROWHASH_ALLOCATION/sizeof(void *))

/*
** If there are less than this number of elements in the block-list, do not
** bother building a hash-table. Just do a linear search of the list when
** querying.
*/
#define ROWHASH_LINEAR_SEARCH_LIMIT 10

/*
** Element stored in the hash-table.
*/
struct RowHashElem {
  i64 iVal;
  RowHashElem *pNext;
};

/*
** The following structure is either exactly ROWHASH_ALLOCATION bytes in
** size or just slightly less. It stores up to ROWHASH_ELEM_PER_BLOCK 
** RowHashElem structures.
*/
struct RowHashBlock {
  struct RowHashBlockData {
    int nElem;
    RowHashBlock *pNext;
  } data;
  RowHashElem aElem[ROWHASH_ELEM_PER_BLOCK];
};

/*
** RowHash structure. References to a structure of this type are passed
** around and used as opaque handles by code in other modules.
*/
struct RowHash {
  /* Variables populated by sqlite3RowhashInsert() */
  int nEntry;               /* Total number of entries in block-list */
  RowHashBlock *pBlock;     /* Linked list of entries */

  /* Variables populated by makeHashTable() */
  int iSet;                 /* Most recent iSet parameter passed to Test() */
  int iMod;                 /* Number of buckets in hash table */
  int nLeaf;                /* Number of leaf pages in hash table */
  int nHeight;              /* Height of tree containing leaf pages */
  void *pHash;              /* Pointer to root of tree */
  int nLinearLimit;         /* Linear search limit (used if pHash==0) */
};


/*
** Allocate a tree of height nHeight with *pnLeaf leaf pages. Set *pp to
** point to the root of the tree. If the maximum number of leaf pages in a
** tree of height nHeight is less than *pnLeaf, allocate a tree with the 
** maximum possible number of leaves for height nHeight. 
**
** Before returning, subtract the number of leaves in the tree allocated
** from *pnLeaf.
**
** This routine returns SQLITE_NOMEM if a malloc() fails, or SQLITE_OK
** otherwise.
*/
static int allocTable(void **pp, int nHeight, int *pnLeaf){
  void **ap = (void **)sqlite3MallocZero(ROWHASH_ALLOCATION);
  if( !ap ){
    return SQLITE_NOMEM;
  }
  *pp = (void *)ap;
  if( nHeight==0 ){
    (*pnLeaf)--;
  }else{
    int ii;
    for(ii=0; ii<ROWHASH_POINTER_PER_PAGE && *pnLeaf>0; ii++){
      if( allocTable(&ap[ii], nHeight-1, pnLeaf) ){
        return SQLITE_NOMEM;
      }
    }
  }
  return SQLITE_OK;
}

/*
** Delete the tree of height nHeight passed as the first argument.
*/
static void deleteTable(void **ap, int nHeight){
  if( ap ){
    if( nHeight>0 ){
      int ii;
      for(ii=0; ii<ROWHASH_POINTER_PER_PAGE; ii++){
        deleteTable((void **)ap[ii], nHeight-1);
      }
    }
    sqlite3_free(ap);
  }
}

/*
** Delete the hash-table stored in p->pHash. The p->pHash pointer is
** set to zero before returning. This function is the inverse of 
** allocHashTable()
*/
static void deleteHashTable(RowHash *p){
  deleteTable(p->pHash, p->nHeight);
  p->pHash = 0;
}

/*
** Allocate the hash table structure based on the current values of
** p->nLeaf and p->nHeight.
*/
static int allocHashTable(RowHash *p){
  int nLeaf = p->nLeaf;
  assert( p->pHash==0 );
  assert( p->nLeaf>0 );
  return allocTable(&p->pHash, p->nHeight, &nLeaf);
}

/*
** Find the hash-bucket associated with value iVal. Return a pointer to it.
*/
static void **findHashBucket(RowHash *p, i64 iVal){
  int aOffset[16];
  int n = p->nHeight;
  void **ap = p->pHash;
  int h = (((u64)iVal) % p->iMod);
  for(n=0; n<p->nHeight; n++){
    int h1 = h / ROWHASH_POINTER_PER_PAGE;
    aOffset[n] = h - (h1 * ROWHASH_POINTER_PER_PAGE);
    h = h1;
  }
  aOffset[n] = h;
  for(n=p->nHeight; n>0; n--){
    ap = (void **)ap[aOffset[n]];
  }
  return &ap[aOffset[0]];
}

/*
** Build a hash table to query with sqlite3RowhashTest() based on the
** set of values stored in the linked list of RowHashBlock structures.
*/
static int makeHashTable(RowHash *p, int iSet){
  RowHashBlock *pBlock;
  int iMod;
  int nLeaf;
  
  /* Delete the old hash table. */
  deleteHashTable(p);
  assert( p->iSet!=iSet );
  p->iSet = iSet;

  if( p->nEntry<ROWHASH_LINEAR_SEARCH_LIMIT ){
    p->nLinearLimit = p->nEntry;
    return SQLITE_OK;
  }

  /* Determine how many leaves the hash-table will comprise. */
  nLeaf = 1 + (p->nEntry / ROWHASH_POINTER_PER_PAGE);
  iMod = nLeaf*ROWHASH_POINTER_PER_PAGE;
  p->nLeaf = nLeaf;
  p->iMod = iMod;

  /* Set nHeight to the height of the tree that contains the leaf pages. If
  ** RowHash.nHeight is zero, then the whole hash-table fits on a single
  ** leaf. If RowHash.nHeight is 1, then RowHash.pHash points to an array
  ** of pointers to leaf pages. If 2, pHash points to an array of pointers
  ** to arrays of pointers to leaf pages. And so on.
  */
  p->nHeight = 0;
  while( nLeaf>1 ){
    nLeaf = (nLeaf+ROWHASH_POINTER_PER_PAGE-1) / ROWHASH_POINTER_PER_PAGE;
    p->nHeight++;
  }

  /* Allocate the hash-table. */
  if( allocHashTable(p) ){
    return SQLITE_NOMEM;
  }

  /* Insert all values into the hash-table. */
  for(pBlock=p->pBlock; pBlock; pBlock=pBlock->data.pNext){
    RowHashElem * const pEnd = &pBlock->aElem[pBlock->data.nElem];
    RowHashElem *pIter;
    for(pIter=pBlock->aElem; pIter<pEnd; pIter++){
      RowHashElem **ppElem = (RowHashElem **)findHashBucket(p, pIter->iVal);
      pIter->pNext = *ppElem;
      *ppElem = pIter;
    }
  }

  return SQLITE_OK;
}

/*
** Test if value iVal is in the hash table. If so, set *pExists to 1
** before returning. If iVal is not in the hash table, set *pExists to 0.
**
** Return SQLITE_OK if all goes as planned. If a malloc() fails, return
** SQLITE_NOMEM.
*/
int sqlite3RowhashTest(RowHash *p, int iSet, i64 iVal, int *pExists){
  *pExists = 0;
  if( p ){
    assert( p->pBlock );
    if( iSet!=p->iSet && makeHashTable(p, iSet) ){
      return SQLITE_NOMEM;
    }
    if( p->pHash ){
      RowHashElem *pElem = *(RowHashElem **)findHashBucket(p, iVal);
      for(; pElem; pElem=pElem->pNext){
        if( pElem->iVal==iVal ){
          *pExists = 1;
          break;
        }
      }
    }else{
      int ii;
      RowHashElem *aElem = p->pBlock->aElem;
      for(ii=0; ii<p->nLinearLimit; ii++){
        if( aElem[ii].iVal==iVal ){
          *pExists = 1;
          break;
        }
      }
    }
  }
  return SQLITE_OK;
}

/*
** Insert value iVal into the RowHash object.
**
** Return SQLITE_OK if all goes as planned. If a malloc() fails, return
** SQLITE_NOMEM.
*/
int sqlite3RowhashInsert(RowHash **pp, i64 iVal){
  RowHash *p = *pp;
  
  /* If the RowHash structure has not been allocated, allocate it now. */
  if( !p ){
    p = (RowHash*)sqlite3MallocZero(sizeof(RowHash));
    if( !p ){
      return SQLITE_NOMEM;
    }
    *pp = p;
  }

  /* If the current RowHashBlock is full, or if the first RowHashBlock has
  ** not yet been allocated, allocate one now. */ 
  if( !p->pBlock || p->pBlock->data.nElem==ROWHASH_ELEM_PER_BLOCK ){
    RowHashBlock *pBlock = (RowHashBlock*)sqlite3Malloc(sizeof(RowHashBlock));
    if( !pBlock ){
      return SQLITE_NOMEM;
    }
    pBlock->data.nElem = 0;
    pBlock->data.pNext = p->pBlock;
    p->pBlock = pBlock;
  }

  /* Add iVal to the current RowHashBlock. */
  p->pBlock->aElem[p->pBlock->data.nElem].iVal = iVal;
  p->pBlock->data.nElem++;
  p->nEntry++;
  return SQLITE_OK;
}

/*
** Destroy the RowHash object passed as the first argument.
*/
void sqlite3RowhashDestroy(RowHash *p){
  if( p ){
    RowHashBlock *pBlock, *pNext;
    deleteHashTable(p);
    for(pBlock=p->pBlock; pBlock; pBlock=pNext){
      pNext = pBlock->data.pNext;
      sqlite3_free(pBlock);
    }
    sqlite3_free(p);
  }
}

Changes to src/sqliteInt.h.

7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
...
553
554
555
556
557
558
559

560
561
562
563
564
565
566
....
1747
1748
1749
1750
1751
1752
1753

1754
1755
1756
1757
1758
1759
1760
1761
1762
1763
1764
1765
1766

1767
1768
1769
1770
1771
1772
1773
....
2394
2395
2396
2397
2398
2399
2400




2401
2402
2403
2404
2405
2406
2407
**    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.854 2009/04/08 13:51:51 drh Exp $
*/
#ifndef _SQLITEINT_H_
#define _SQLITEINT_H_

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

/*
** Forward references to structures
*/
typedef struct AggInfo AggInfo;
typedef struct AuthContext AuthContext;
typedef struct Bitvec Bitvec;

typedef struct RowSet RowSet;
typedef struct CollSeq CollSeq;
typedef struct Column Column;
typedef struct Db Db;
typedef struct Schema Schema;
typedef struct Expr Expr;
typedef struct ExprList ExprList;
................................................................................
#define WHERE_ORDERBY_NORMAL   0x0000 /* No-op */
#define WHERE_ORDERBY_MIN      0x0001 /* ORDER BY processing for min() func */
#define WHERE_ORDERBY_MAX      0x0002 /* ORDER BY processing for max() func */
#define WHERE_ONEPASS_DESIRED  0x0004 /* Want to do one-pass UPDATE/DELETE */
#define WHERE_FILL_ROWSET      0x0008  /* Save results in a RowSet object */
#define WHERE_OMIT_OPEN        0x0010  /* Table cursor are already open */
#define WHERE_OMIT_CLOSE       0x0020  /* Omit close of table & index cursors */


/*
** 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
** into the second half to give some continuity.
*/
struct WhereInfo {
  Parse *pParse;       /* Parsing and code generating context */
  u16 wctrlFlags;      /* Flags originally passed to sqlite3WhereBegin() */
  u8 okOnePass;        /* Ok to use one-pass algorithm for UPDATE or DELETE */
  int regRowSet;                 /* Store rowids in this rowset if >=0 */

  SrcList *pTabList;             /* List of tables in the join */
  int iTop;                      /* The very beginning of the WHERE loop */
  int iContinue;                 /* Jump here to continue with next record */
  int iBreak;                    /* Jump here to break out of the loop */
  int nLevel;                    /* Number of nested loop */
  struct WhereClause *pWC;       /* Decomposition of the WHERE clause */
  WhereLevel a[1];               /* Information about each nest loop in WHERE */
................................................................................
u32 sqlite3BitvecSize(Bitvec*);
int sqlite3BitvecBuiltinTest(int,int*);

RowSet *sqlite3RowSetInit(sqlite3*, void*, unsigned int);
void sqlite3RowSetClear(RowSet*);
void sqlite3RowSetInsert(RowSet*, i64);
int sqlite3RowSetNext(RowSet*, i64*);





void sqlite3CreateView(Parse*,Token*,Token*,Token*,Select*,int,int);

#if !defined(SQLITE_OMIT_VIEW) || !defined(SQLITE_OMIT_VIRTUALTABLE)
  int sqlite3ViewGetColumnNames(Parse*,Table*);
#else
# define sqlite3ViewGetColumnNames(A,B) 0







|







 







>







 







>












|
>







 







>
>
>
>







7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
...
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
....
1748
1749
1750
1751
1752
1753
1754
1755
1756
1757
1758
1759
1760
1761
1762
1763
1764
1765
1766
1767
1768
1769
1770
1771
1772
1773
1774
1775
1776
....
2397
2398
2399
2400
2401
2402
2403
2404
2405
2406
2407
2408
2409
2410
2411
2412
2413
2414
**    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.855 2009/04/21 09:02:47 danielk1977 Exp $
*/
#ifndef _SQLITEINT_H_
#define _SQLITEINT_H_

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

/*
** Forward references to structures
*/
typedef struct AggInfo AggInfo;
typedef struct AuthContext AuthContext;
typedef struct Bitvec Bitvec;
typedef struct RowHash RowHash;
typedef struct RowSet RowSet;
typedef struct CollSeq CollSeq;
typedef struct Column Column;
typedef struct Db Db;
typedef struct Schema Schema;
typedef struct Expr Expr;
typedef struct ExprList ExprList;
................................................................................
#define WHERE_ORDERBY_NORMAL   0x0000 /* No-op */
#define WHERE_ORDERBY_MIN      0x0001 /* ORDER BY processing for min() func */
#define WHERE_ORDERBY_MAX      0x0002 /* ORDER BY processing for max() func */
#define WHERE_ONEPASS_DESIRED  0x0004 /* Want to do one-pass UPDATE/DELETE */
#define WHERE_FILL_ROWSET      0x0008  /* Save results in a RowSet object */
#define WHERE_OMIT_OPEN        0x0010  /* Table cursor are already open */
#define WHERE_OMIT_CLOSE       0x0020  /* Omit close of table & index cursors */
#define WHERE_FILL_ROWHASH     0x0040  /* Save results in a RowHash object */

/*
** 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
** into the second half to give some continuity.
*/
struct WhereInfo {
  Parse *pParse;       /* Parsing and code generating context */
  u16 wctrlFlags;      /* Flags originally passed to sqlite3WhereBegin() */
  u8 okOnePass;        /* Ok to use one-pass algorithm for UPDATE or DELETE */
  int regRowSet;                 /* Store rowids in this rowset/rowhash */
  int iRowidHandler;             /* Address of OP_RowSet or OP_RowHash */
  SrcList *pTabList;             /* List of tables in the join */
  int iTop;                      /* The very beginning of the WHERE loop */
  int iContinue;                 /* Jump here to continue with next record */
  int iBreak;                    /* Jump here to break out of the loop */
  int nLevel;                    /* Number of nested loop */
  struct WhereClause *pWC;       /* Decomposition of the WHERE clause */
  WhereLevel a[1];               /* Information about each nest loop in WHERE */
................................................................................
u32 sqlite3BitvecSize(Bitvec*);
int sqlite3BitvecBuiltinTest(int,int*);

RowSet *sqlite3RowSetInit(sqlite3*, void*, unsigned int);
void sqlite3RowSetClear(RowSet*);
void sqlite3RowSetInsert(RowSet*, i64);
int sqlite3RowSetNext(RowSet*, i64*);

int sqlite3RowhashInsert(RowHash **pp, i64 iVal);
int sqlite3RowhashTest(RowHash *p, int iSet, i64 iVal, int *pExists);
void sqlite3RowhashDestroy(RowHash *p);

void sqlite3CreateView(Parse*,Token*,Token*,Token*,Select*,int,int);

#if !defined(SQLITE_OMIT_VIEW) || !defined(SQLITE_OMIT_VIRTUALTABLE)
  int sqlite3ViewGetColumnNames(Parse*,Table*);
#else
# define sqlite3ViewGetColumnNames(A,B) 0

Changes to src/test8.c.

9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
...
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
**    May you share freely, never taking more than you give.
**
*************************************************************************
** Code for testing the virtual table interfaces.  This code
** is not included in the SQLite library.  It is used for automated
** testing of the SQLite library.
**
** $Id: test8.c,v 1.76 2009/04/08 15:45:32 drh Exp $
*/
#include "sqliteInt.h"
#include "tcl.h"
#include <stdlib.h>
#include <string.h>

#ifndef SQLITE_OMIT_VIRTUALTABLE
................................................................................

  if( !zQuery ){
    return rc;
  }
  pIdxInfo->idxNum = hashString(zQuery);
  pIdxInfo->idxStr = zQuery;
  pIdxInfo->needToFreeIdxStr = 1;
  if (useCost) {
    pIdxInfo->estimatedCost = cost;
  } else if( useIdx ){
    /* Approximation of log2(nRow). */
    for( ii=0; ii<(sizeof(int)*8); ii++ ){
      if( nRow & (1<<ii) ){
        pIdxInfo->estimatedCost = (double)ii;
      }
    }
  } else {
    pIdxInfo->estimatedCost = (double)nRow;
  }
  return rc;
}

/*
** The xUpdate method for echo module virtual tables.







|







 







|

|






|







9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
...
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
**    May you share freely, never taking more than you give.
**
*************************************************************************
** Code for testing the virtual table interfaces.  This code
** is not included in the SQLite library.  It is used for automated
** testing of the SQLite library.
**
** $Id: test8.c,v 1.77 2009/04/21 09:02:47 danielk1977 Exp $
*/
#include "sqliteInt.h"
#include "tcl.h"
#include <stdlib.h>
#include <string.h>

#ifndef SQLITE_OMIT_VIRTUALTABLE
................................................................................

  if( !zQuery ){
    return rc;
  }
  pIdxInfo->idxNum = hashString(zQuery);
  pIdxInfo->idxStr = zQuery;
  pIdxInfo->needToFreeIdxStr = 1;
  if( useCost ){
    pIdxInfo->estimatedCost = cost;
  }else if( useIdx ){
    /* Approximation of log2(nRow). */
    for( ii=0; ii<(sizeof(int)*8); ii++ ){
      if( nRow & (1<<ii) ){
        pIdxInfo->estimatedCost = (double)ii;
      }
    }
  }else{
    pIdxInfo->estimatedCost = (double)nRow;
  }
  return rc;
}

/*
** The xUpdate method for echo module virtual tables.

Changes to src/vdbe.c.

39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
....
3464
3465
3466
3467
3468
3469
3470

3471
3472
3473
3474
3475
3476
3477
....
4596
4597
4598
4599
4600
4601
4602

















































4603
4604
4605
4606
4607
4608
4609
**
** Various scripts scan this source file in order to generate HTML
** documentation, headers files, or other derived files.  The formatting
** of the code in this file is, therefore, important.  See other comments
** in this file for details.  If in doubt, do not deviate from existing
** commenting and indentation practices when changing or adding code.
**
** $Id: vdbe.c,v 1.832 2009/04/10 12:55:17 danielk1977 Exp $
*/
#include "sqliteInt.h"
#include "vdbeInt.h"

/*
** The following global variable is incremented every time a cursor
** moves, either by the OP_SeekXX, OP_Next, or OP_Prev opcodes.  The test
................................................................................
    assert( p->apCsr[i]->isTable );
    iKey = intToKey(pIn3->u.i);
    rc = sqlite3BtreeMovetoUnpacked(pCrsr, 0, iKey, 0,&res);
    pC->lastRowid = pIn3->u.i;
    pC->rowidIsValid = res==0 ?1:0;
    pC->nullRow = 0;
    pC->cacheStatus = CACHE_STALE;

    if( res!=0 ){
      pc = pOp->p2 - 1;
      assert( pC->rowidIsValid==0 );
    }
  }else if( !pC->pseudoTable ){
    /* This happens when an attempt to open a read cursor on the 
    ** sqlite_master table returns SQLITE_EMPTY.
................................................................................
  }else{
    /* A value was pulled from the index */
    assert( pOp->p3>0 && pOp->p3<=p->nMem );
    sqlite3VdbeMemSetInt64(pOut, val);
  }
  break;
}



















































#ifndef SQLITE_OMIT_TRIGGER
/* Opcode: ContextPush * * * 
**
** Save the current Vdbe context such that it can be restored by a ContextPop
** opcode. The context stores the last insert row id, the last statement change







|







 







>







 







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







39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
....
3464
3465
3466
3467
3468
3469
3470
3471
3472
3473
3474
3475
3476
3477
3478
....
4597
4598
4599
4600
4601
4602
4603
4604
4605
4606
4607
4608
4609
4610
4611
4612
4613
4614
4615
4616
4617
4618
4619
4620
4621
4622
4623
4624
4625
4626
4627
4628
4629
4630
4631
4632
4633
4634
4635
4636
4637
4638
4639
4640
4641
4642
4643
4644
4645
4646
4647
4648
4649
4650
4651
4652
4653
4654
4655
4656
4657
4658
4659
**
** Various scripts scan this source file in order to generate HTML
** documentation, headers files, or other derived files.  The formatting
** of the code in this file is, therefore, important.  See other comments
** in this file for details.  If in doubt, do not deviate from existing
** commenting and indentation practices when changing or adding code.
**
** $Id: vdbe.c,v 1.833 2009/04/21 09:02:47 danielk1977 Exp $
*/
#include "sqliteInt.h"
#include "vdbeInt.h"

/*
** The following global variable is incremented every time a cursor
** moves, either by the OP_SeekXX, OP_Next, or OP_Prev opcodes.  The test
................................................................................
    assert( p->apCsr[i]->isTable );
    iKey = intToKey(pIn3->u.i);
    rc = sqlite3BtreeMovetoUnpacked(pCrsr, 0, iKey, 0,&res);
    pC->lastRowid = pIn3->u.i;
    pC->rowidIsValid = res==0 ?1:0;
    pC->nullRow = 0;
    pC->cacheStatus = CACHE_STALE;
    pC->deferredMoveto = 0;
    if( res!=0 ){
      pc = pOp->p2 - 1;
      assert( pC->rowidIsValid==0 );
    }
  }else if( !pC->pseudoTable ){
    /* This happens when an attempt to open a read cursor on the 
    ** sqlite_master table returns SQLITE_EMPTY.
................................................................................
  }else{
    /* A value was pulled from the index */
    assert( pOp->p3>0 && pOp->p3<=p->nMem );
    sqlite3VdbeMemSetInt64(pOut, val);
  }
  break;
}

/* Opcode: RowHash P1 P2 P3 P4
**
** Register P3 is assumed to hold an integer value. If register P1
** contains a rowid-hash object and the rowid-hash object contains
** the value held in P3, jump to register P2. Otherwise, insert the
** integer in P3 into the rowid-hash container.
**
** The rowid-hash is optimized for the case where successive sets
** of integers, where each set contains no duplicates. Each set
** of values is identified by a unique P4 value. The first set
** must have P4==0, the final set P4=-1.
**
** This allows optimizations: (a) when P4==0 there is no need to test
** the row-hash object for P3, as it is guaranteed not to contain it,
** (b) when P4==-1 there is no need to insert the value, as it will
** never be tested for, and (c) when a value that is part of set X is
** inserted, there is no need to search to see if the same value was
** previously inserted as part of set X (only if it was previously
** inserted as part of some other set).
*/
case OP_RowHash: {                     /* jump, in1, in3 */
  int iSet = pOp->p4.i;
  assert( pIn3->flags&MEM_Int );

  /* If there is anything other than a row-hash object in memory cell P1,
  ** delete it now and initialize P1 with an empty row-hash (a null pointer
  ** is an acceptable representation of an empty row-hash).
  */
  if( (pIn1->flags & MEM_RowHash)==0 ){
    sqlite3VdbeMemReleaseExternal(pIn1);
    pIn1->u.pRowHash = 0;
    pIn1->flags = MEM_RowHash;
  }

  assert( pOp->p4type==P4_INT32 );
  if( iSet ){
    int exists;
    rc = sqlite3RowhashTest(pIn1->u.pRowHash, pOp->p4.i, pIn3->u.i, &exists);
    if( exists ){
      pc = pOp->p2 - 1;
      break;
    }
  }
  if( iSet>=0 ){
    rc = sqlite3RowhashInsert(&pIn1->u.pRowHash, pIn3->u.i);
  }
  break;
}


#ifndef SQLITE_OMIT_TRIGGER
/* Opcode: ContextPush * * * 
**
** Save the current Vdbe context such that it can be restored by a ContextPop
** opcode. The context stores the last insert row id, the last statement change

Changes to src/vdbeInt.h.

11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
...
111
112
113
114
115
116
117

118
119
120
121
122
123
124
...
144
145
146
147
148
149
150

151
152
153
154
155
156
157
*************************************************************************
** This is the header file for information that is private to the
** VDBE.  This information used to all be at the top of the single
** source code file "vdbe.c".  When that file became too big (over
** 6000 lines long) it was split up into several smaller files and
** this header information was factored out.
**
** $Id: vdbeInt.h,v 1.167 2009/04/10 12:55:17 danielk1977 Exp $
*/
#ifndef _VDBEINT_H_
#define _VDBEINT_H_

/*
** intToKey() and keyToInt() used to transform the rowid.  But with
** the latest versions of the design they are no-ops.
................................................................................
*/
struct Mem {
  union {
    i64 i;              /* Integer value. */
    int nZero;          /* Used when bit MEM_Zero is set in flags */
    FuncDef *pDef;      /* Used only when flags==MEM_Agg */
    RowSet *pRowSet;    /* Used only when flags==MEM_RowSet */

  } u;
  double r;           /* Real value */
  sqlite3 *db;        /* The associated database connection */
  char *z;            /* String or BLOB value */
  int n;              /* Number of characters in string value, excluding '\0' */
  u16 flags;          /* Some combination of MEM_Null, MEM_Str, MEM_Dyn, etc. */
  u8  type;           /* One of SQLITE_NULL, SQLITE_TEXT, SQLITE_INTEGER, etc */
................................................................................
*/
#define MEM_Null      0x0001   /* Value is NULL */
#define MEM_Str       0x0002   /* Value is a string */
#define MEM_Int       0x0004   /* Value is an integer */
#define MEM_Real      0x0008   /* Value is a real number */
#define MEM_Blob      0x0010   /* Value is a BLOB */
#define MEM_RowSet    0x0020   /* Value is a RowSet object */

#define MEM_TypeMask  0x00ff   /* Mask of type bits */

/* Whenever Mem contains a valid string or blob representation, one of
** the following flags must be set to determine the memory management
** policy for Mem.z.  The MEM_Term flag tells us whether or not the
** string is \000 or \u0000 terminated
*/







|







 







>







 







>







11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
...
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
...
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
*************************************************************************
** This is the header file for information that is private to the
** VDBE.  This information used to all be at the top of the single
** source code file "vdbe.c".  When that file became too big (over
** 6000 lines long) it was split up into several smaller files and
** this header information was factored out.
**
** $Id: vdbeInt.h,v 1.168 2009/04/21 09:02:47 danielk1977 Exp $
*/
#ifndef _VDBEINT_H_
#define _VDBEINT_H_

/*
** intToKey() and keyToInt() used to transform the rowid.  But with
** the latest versions of the design they are no-ops.
................................................................................
*/
struct Mem {
  union {
    i64 i;              /* Integer value. */
    int nZero;          /* Used when bit MEM_Zero is set in flags */
    FuncDef *pDef;      /* Used only when flags==MEM_Agg */
    RowSet *pRowSet;    /* Used only when flags==MEM_RowSet */
    RowHash *pRowHash;  /* Used only when flags==MEM_RowHash */
  } u;
  double r;           /* Real value */
  sqlite3 *db;        /* The associated database connection */
  char *z;            /* String or BLOB value */
  int n;              /* Number of characters in string value, excluding '\0' */
  u16 flags;          /* Some combination of MEM_Null, MEM_Str, MEM_Dyn, etc. */
  u8  type;           /* One of SQLITE_NULL, SQLITE_TEXT, SQLITE_INTEGER, etc */
................................................................................
*/
#define MEM_Null      0x0001   /* Value is NULL */
#define MEM_Str       0x0002   /* Value is a string */
#define MEM_Int       0x0004   /* Value is an integer */
#define MEM_Real      0x0008   /* Value is a real number */
#define MEM_Blob      0x0010   /* Value is a BLOB */
#define MEM_RowSet    0x0020   /* Value is a RowSet object */
#define MEM_RowHash   0x0040   /* Value is a RowHash object */
#define MEM_TypeMask  0x00ff   /* Mask of type bits */

/* Whenever Mem contains a valid string or blob representation, one of
** the following flags must be set to determine the memory management
** policy for Mem.z.  The MEM_Term flag tells us whether or not the
** string is \000 or \u0000 terminated
*/

Changes to src/vdbeaux.c.

10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
....
1220
1221
1222
1223
1224
1225
1226



1227
1228
1229
1230
1231
1232
1233
**
*************************************************************************
** This file contains code used for creating, destroying, and populating
** a VDBE (or an "sqlite3_stmt" as it is known to the outside world.)  Prior
** to version 2.8.7, all this code was combined into the vdbe.c source file.
** But that file was getting too big so this subroutines were split out.
**
** $Id: vdbeaux.c,v 1.451 2009/04/10 15:42:36 shane Exp $
*/
#include "sqliteInt.h"
#include "vdbeInt.h"



/*
................................................................................
  sqlite3 *db = p->db;
  Mem *pMem;
  closeAllCursorsExceptActiveVtabs(p);
  for(pMem=&p->aMem[1], i=1; i<=p->nMem; i++, pMem++){
    if( pMem->flags & MEM_RowSet ){
      sqlite3RowSetClear(pMem->u.pRowSet);
    }



    MemSetTypeFlag(pMem, MEM_Null);
  }
  releaseMemArray(&p->aMem[1], p->nMem);
  if( p->contextStack ){
    sqlite3DbFree(db, p->contextStack);
  }
  p->contextStack = 0;







|







 







>
>
>







10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
....
1220
1221
1222
1223
1224
1225
1226
1227
1228
1229
1230
1231
1232
1233
1234
1235
1236
**
*************************************************************************
** This file contains code used for creating, destroying, and populating
** a VDBE (or an "sqlite3_stmt" as it is known to the outside world.)  Prior
** to version 2.8.7, all this code was combined into the vdbe.c source file.
** But that file was getting too big so this subroutines were split out.
**
** $Id: vdbeaux.c,v 1.452 2009/04/21 09:02:47 danielk1977 Exp $
*/
#include "sqliteInt.h"
#include "vdbeInt.h"



/*
................................................................................
  sqlite3 *db = p->db;
  Mem *pMem;
  closeAllCursorsExceptActiveVtabs(p);
  for(pMem=&p->aMem[1], i=1; i<=p->nMem; i++, pMem++){
    if( pMem->flags & MEM_RowSet ){
      sqlite3RowSetClear(pMem->u.pRowSet);
    }
    if( pMem->flags & MEM_RowHash ){
      sqlite3RowhashDestroy(pMem->u.pRowHash);
    }
    MemSetTypeFlag(pMem, MEM_Null);
  }
  releaseMemArray(&p->aMem[1], p->nMem);
  if( p->contextStack ){
    sqlite3DbFree(db, p->contextStack);
  }
  p->contextStack = 0;

Changes to src/vdbemem.c.

11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
...
266
267
268
269
270
271
272

273
274
275
276
277
278
279
280
281
282




283
284
285
286
287
288
289
*************************************************************************
**
** This file contains code use to manipulate "Mem" structure.  A "Mem"
** stores a single value in the VDBE.  Mem is an opaque structure visible
** only within the VDBE.  Interface routines refer to a Mem using the
** name sqlite_value
**
** $Id: vdbemem.c,v 1.140 2009/04/05 12:22:09 drh Exp $
*/
#include "sqliteInt.h"
#include "vdbeInt.h"

/*
** Call sqlite3VdbeMemExpandBlob() on the supplied value (type Mem*)
** P if required.
................................................................................
/*
** If the memory cell contains a string value that must be freed by
** invoking an external callback, free it now. Calling this function
** does not free any Mem.zMalloc buffer.
*/
void sqlite3VdbeMemReleaseExternal(Mem *p){
  assert( p->db==0 || sqlite3_mutex_held(p->db->mutex) );

  if( p->flags&MEM_Agg ){
    sqlite3VdbeMemFinalize(p, p->u.pDef);
    assert( (p->flags & MEM_Agg)==0 );
    sqlite3VdbeMemRelease(p);
  }else if( p->flags&MEM_Dyn && p->xDel ){
    assert( (p->flags&MEM_RowSet)==0 );
    p->xDel((void *)p->z);
    p->xDel = 0;
  }else if( p->flags&MEM_RowSet ){
    sqlite3RowSetClear(p->u.pRowSet);




  }
}

/*
** Release any memory held by the Mem. This may leave the Mem in an
** inconsistent state, for example with (Mem.z==0) and
** (Mem.type==SQLITE_TEXT).







|







 







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







11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
...
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
*************************************************************************
**
** This file contains code use to manipulate "Mem" structure.  A "Mem"
** stores a single value in the VDBE.  Mem is an opaque structure visible
** only within the VDBE.  Interface routines refer to a Mem using the
** name sqlite_value
**
** $Id: vdbemem.c,v 1.141 2009/04/21 09:02:47 danielk1977 Exp $
*/
#include "sqliteInt.h"
#include "vdbeInt.h"

/*
** Call sqlite3VdbeMemExpandBlob() on the supplied value (type Mem*)
** P if required.
................................................................................
/*
** If the memory cell contains a string value that must be freed by
** invoking an external callback, free it now. Calling this function
** does not free any Mem.zMalloc buffer.
*/
void sqlite3VdbeMemReleaseExternal(Mem *p){
  assert( p->db==0 || sqlite3_mutex_held(p->db->mutex) );
  if( p->flags&(MEM_Agg|MEM_Dyn|MEM_RowSet|MEM_RowHash) ){
    if( p->flags&MEM_Agg ){
      sqlite3VdbeMemFinalize(p, p->u.pDef);
      assert( (p->flags & MEM_Agg)==0 );
      sqlite3VdbeMemRelease(p);
    }else if( p->flags&MEM_Dyn && p->xDel ){
      assert( (p->flags&MEM_RowSet)==0 );
      p->xDel((void *)p->z);
      p->xDel = 0;
    }else if( p->flags&MEM_RowSet ){
      sqlite3RowSetClear(p->u.pRowSet);
    }else if( p->flags&MEM_RowHash ){
      sqlite3RowhashDestroy(p->u.pRowHash);
      p->u.pRowHash = 0;
    }
  }
}

/*
** Release any memory held by the Mem. This may leave the Mem in an
** inconsistent state, for example with (Mem.z==0) and
** (Mem.type==SQLITE_TEXT).

Changes to src/where.c.

12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
....
1470
1471
1472
1473
1474
1475
1476
1477






















































































1478

























































































































































1479
1480
1481
1482
1483
1484
1485
....
1488
1489
1490
1491
1492
1493
1494
1495
1496
1497
1498
1499
1500
1501
1502
1503
1504
1505
1506
1507
1508
1509
1510
1511
1512
1513
1514
1515
1516
1517
1518
1519
1520
1521
1522
1523
1524
1525
1526
1527
1528
1529
1530
1531
1532
1533
1534
1535
1536
1537
1538
1539
1540
1541
1542
1543
1544
1545
1546
1547
1548
1549
1550
1551
1552
1553
1554
1555
1556
1557
1558
1559
1560
1561
1562
1563
1564
1565
1566
1567
1568
1569
1570
1571
1572
1573
1574
1575
1576
1577
1578
1579
1580
1581
1582
1583
1584
1585
1586
1587
1588
1589
1590
1591
1592
1593
1594
1595
1596
1597
1598
1599
1600
1601
1602
1603
1604
1605
1606
1607
1608
1609
....
1610
1611
1612
1613
1614
1615
1616
1617
1618
1619
1620
1621
1622
1623
1624
1625
1626
1627
1628
1629
1630
1631
....
1657
1658
1659
1660
1661
1662
1663
1664
1665
1666
1667
1668
1669
1670
1671
1672
1673
1674
1675





1676
1677
1678

1679

1680
1681

1682
1683
1684
1685


1686
1687
1688
1689
1690
1691
1692
1693
1694
1695
1696
1697




1698
1699
1700
1701
1702
1703
1704
....
1722
1723
1724
1725
1726
1727
1728
1729
1730
1731
1732
1733
1734
1735
1736
....
1740
1741
1742
1743
1744
1745
1746
1747
1748
1749
1750
1751
1752
1753
1754
....
1856
1857
1858
1859
1860
1861
1862
1863
1864
1865
1866
1867
1868
1869
1870
1871
1872
1873
1874
1875
1876
1877
1878
1879
1880
1881
1882
1883
1884
1885
1886
1887
1888
1889
1890
1891
1892
1893
1894
1895
1896
1897
1898
1899
1900
1901
1902
1903
1904
1905
1906
1907
1908
1909
1910
1911
1912
1913
1914
1915
1916
1917
1918
1919
1920
1921
1922
1923
1924
....
2064
2065
2066
2067
2068
2069
2070

























2071
2072
2073
2074
2075
2076
2077
....
2260
2261
2262
2263
2264
2265
2266
2267
2268
2269
2270
2271
2272
2273
2274
2275
2276
2277
2278
2279
2280
2281
2282
2283
2284
2285
2286
2287
2288
2289
2290
2291
2292
....
2304
2305
2306
2307
2308
2309
2310
2311




















2312
2313
2314
2315
2316
2317
2318
2319
2320

2321
2322
2323
2324
2325
2326
2327
....
2382
2383
2384
2385
2386
2387
2388
2389
2390
2391
2392
2393
2394
2395
2396
2397
2398
2399
2400
2401
2402
2403
2404
2405
2406
2407
2408
2409
2410
2411
2412
2413
2414
2415
2416
2417
2418
2419
2420
2421
2422
2423
2424
2425
2426
....
2479
2480
2481
2482
2483
2484
2485
2486
2487
2488
2489
2490
2491
2492
2493
2494
2495
2496
2497
2498
2499
2500
2501
2502
2503
2504
....
2677
2678
2679
2680
2681
2682
2683

2684
2685
2686
2687
2688
2689

2690
2691
2692
2693
2694
2695
2696
2697
2698
2699
2700
2701
2702
2703
2704
....
2713
2714
2715
2716
2717
2718
2719
2720
2721

2722







2723
2724
2725
2726
2727
2728
2729
2730


2731
2732


2733






2734
2735
2736


2737
2738
2739






2740
2741
2742
2743
2744
2745
2746
2747
2748
2749
2750
2751
2752
2753
2754
2755
2756
2757
2758
2759
2760
2761
2762
2763
2764
2765
2766
2767
2768
2769
2770
2771
2772
2773
2774
2775
2776
2777
2778
2779





















2780
2781
2782
2783
2784
2785
2786
....
2789
2790
2791
2792
2793
2794
2795
2796
2797
2798
2799
2800
2801
2802
2803
....
2835
2836
2837
2838
2839
2840
2841
2842
2843
2844



2845
2846

2847
2848
2849
2850
2851
2852
2853
2854
2855




2856
2857



2858


2859
2860
2861
2862
2863
2864
2865
....
2878
2879
2880
2881
2882
2883
2884
2885
2886
2887
2888
2889
2890
2891
2892
....
3034
3035
3036
3037
3038
3039
3040
3041
3042
3043
3044

3045
3046
3047
3048
3049
3050
3051
....
3121
3122
3123
3124
3125
3126
3127
3128
3129

3130
3131
3132
3133
3134
3135
3136
3137


3138
3139
3140
3141
3142
3143
3144
3145
3146
3147
3148
3149
3150
3151
3152
3153
3154
3155
3156
3157
3158
3159
3160
3161
3162
3163
3164
3165
3166
3167
3168
3169
3170
3171
3172
....
3203
3204
3205
3206
3207
3208
3209
3210
3211
3212
3213
3214
3215
3216
3217
** This module contains C code that generates VDBE code used to process
** the WHERE clause of SQL statements.  This module is responsible for
** generating the code that loops through a table looking for applicable
** rows.  Indices are selected and used to speed the search when doing
** so is applicable.  Because this module is responsible for selecting
** indices, you might also think of this module as the "query optimizer".
**
** $Id: where.c,v 1.382 2009/04/07 13:48:12 drh Exp $
*/
#include "sqliteInt.h"

/*
** Trace output macros
*/
#if defined(SQLITE_TEST) || defined(SQLITE_DEBUG)
................................................................................
  sqlite3DebugPrintf("  orderByConsumed=%d\n", p->orderByConsumed);
  sqlite3DebugPrintf("  estimatedCost=%g\n", p->estimatedCost);
}
#else
#define TRACE_IDX_INPUTS(A)
#define TRACE_IDX_OUTPUTS(A)
#endif























































































#ifndef SQLITE_OMIT_VIRTUALTABLE

























































































































































/*
** Compute the best index for a virtual table.
**
** The best index is computed by the xBestIndex method of the virtual
** table module.  This routine is really just a wrapper that sets up
** the sqlite3_index_info structure that is used to communicate with
** xBestIndex.
................................................................................
** same virtual table.  The sqlite3_index_info structure is created
** and initialized on the first invocation and reused on all subsequent
** invocations.  The sqlite3_index_info structure is also used when
** code is generated to access the virtual table.  The whereInfoDelete() 
** routine takes care of freeing the sqlite3_index_info structure after
** everybody has finished with it.
*/
static double bestVirtualIndex(
  Parse *pParse,                 /* The parsing context */
  WhereClause *pWC,              /* The WHERE clause */
  struct SrcList_item *pSrc,     /* The FROM clause term to search */
  Bitmask notReady,              /* Mask of cursors that are not available */
  ExprList *pOrderBy,            /* The order by clause */
  int orderByUsable,             /* True if we can potential sort */
  sqlite3_index_info **ppIdxInfo /* Index information passed to xBestIndex */
){
  Table *pTab = pSrc->pTab;
  sqlite3_vtab *pVtab = pTab->pVtab;
  sqlite3_index_info *pIdxInfo;
  struct sqlite3_index_constraint *pIdxCons;
  struct sqlite3_index_orderby *pIdxOrderBy;
  struct sqlite3_index_constraint_usage *pUsage;
  WhereTerm *pTerm;
  int i, j;
  int nOrderBy;
  int rc;

  /* If the sqlite3_index_info structure has not been previously
  ** allocated and initialized for this virtual table, then allocate
  ** and initialize it now
  */
  pIdxInfo = *ppIdxInfo;
  if( pIdxInfo==0 ){
    int nTerm;
    WHERETRACE(("Recomputing index info for %s...\n", pTab->zName));

    /* Count the number of possible WHERE clause constraints referring
    ** to this virtual table */
    for(i=nTerm=0, pTerm=pWC->a; i<pWC->nTerm; i++, pTerm++){
      if( pTerm->leftCursor != pSrc->iCursor ) continue;
      assert( (pTerm->eOperator&(pTerm->eOperator-1))==0 );
      testcase( pTerm->eOperator==WO_IN );
      testcase( pTerm->eOperator==WO_ISNULL );
      if( pTerm->eOperator & (WO_IN|WO_ISNULL) ) continue;
      nTerm++;
    }

    /* If the ORDER BY clause contains only columns in the current 
    ** virtual table then allocate space for the aOrderBy part of
    ** the sqlite3_index_info structure.
    */
    nOrderBy = 0;
    if( pOrderBy ){
      for(i=0; i<pOrderBy->nExpr; i++){
        Expr *pExpr = pOrderBy->a[i].pExpr;
        if( pExpr->op!=TK_COLUMN || pExpr->iTable!=pSrc->iCursor ) break;
      }
      if( i==pOrderBy->nExpr ){
        nOrderBy = pOrderBy->nExpr;
      }
    }

    /* Allocate the sqlite3_index_info structure
    */
    pIdxInfo = sqlite3DbMallocZero(pParse->db, sizeof(*pIdxInfo)
                             + (sizeof(*pIdxCons) + sizeof(*pUsage))*nTerm
                             + sizeof(*pIdxOrderBy)*nOrderBy );
    if( pIdxInfo==0 ){
      sqlite3ErrorMsg(pParse, "out of memory");
      /* (double)0 In case of SQLITE_OMIT_FLOATING_POINT... */
      return (double)0;
    }
    *ppIdxInfo = pIdxInfo;

    /* Initialize the structure.  The sqlite3_index_info structure contains
    ** many fields that are declared "const" to prevent xBestIndex from
    ** changing them.  We have to do some funky casting in order to
    ** initialize those fields.
    */
    pIdxCons = (struct sqlite3_index_constraint*)&pIdxInfo[1];
    pIdxOrderBy = (struct sqlite3_index_orderby*)&pIdxCons[nTerm];
    pUsage = (struct sqlite3_index_constraint_usage*)&pIdxOrderBy[nOrderBy];
    *(int*)&pIdxInfo->nConstraint = nTerm;
    *(int*)&pIdxInfo->nOrderBy = nOrderBy;
    *(struct sqlite3_index_constraint**)&pIdxInfo->aConstraint = pIdxCons;
    *(struct sqlite3_index_orderby**)&pIdxInfo->aOrderBy = pIdxOrderBy;
    *(struct sqlite3_index_constraint_usage**)&pIdxInfo->aConstraintUsage =
                                                                     pUsage;

    for(i=j=0, pTerm=pWC->a; i<pWC->nTerm; i++, pTerm++){
      if( pTerm->leftCursor != pSrc->iCursor ) continue;
      assert( (pTerm->eOperator&(pTerm->eOperator-1))==0 );
      testcase( pTerm->eOperator==WO_IN );
      testcase( pTerm->eOperator==WO_ISNULL );
      if( pTerm->eOperator & (WO_IN|WO_ISNULL) ) continue;
      pIdxCons[j].iColumn = pTerm->u.leftColumn;
      pIdxCons[j].iTermOffset = i;
      pIdxCons[j].op = (u8)pTerm->eOperator;
      /* The direct assignment in the previous line is possible only because
      ** the WO_ and SQLITE_INDEX_CONSTRAINT_ codes are identical.  The
      ** following asserts verify this fact. */
      assert( WO_EQ==SQLITE_INDEX_CONSTRAINT_EQ );
      assert( WO_LT==SQLITE_INDEX_CONSTRAINT_LT );
      assert( WO_LE==SQLITE_INDEX_CONSTRAINT_LE );
      assert( WO_GT==SQLITE_INDEX_CONSTRAINT_GT );
      assert( WO_GE==SQLITE_INDEX_CONSTRAINT_GE );
      assert( WO_MATCH==SQLITE_INDEX_CONSTRAINT_MATCH );
      assert( pTerm->eOperator & (WO_EQ|WO_LT|WO_LE|WO_GT|WO_GE|WO_MATCH) );
      j++;
    }
    for(i=0; i<nOrderBy; i++){
      Expr *pExpr = pOrderBy->a[i].pExpr;
      pIdxOrderBy[i].iColumn = pExpr->iColumn;
      pIdxOrderBy[i].desc = pOrderBy->a[i].sortOrder;
    }
  }

  /* At this point, the sqlite3_index_info structure that pIdxInfo points
  ** to will have been initialized, either during the current invocation or
  ** during some prior invocation.  Now we just have to customize the
  ** details of pIdxInfo for the current invocation and pass it to
  ** xBestIndex.
................................................................................
  */

  /* The module name must be defined. Also, by this point there must
  ** be a pointer to an sqlite3_vtab structure. Otherwise
  ** sqlite3ViewGetColumnNames() would have picked up the error. 
  */
  assert( pTab->azModuleArg && pTab->azModuleArg[0] );
  assert( pVtab );
#if 0
  if( pTab->pVtab==0 ){
    sqlite3ErrorMsg(pParse, "undefined module %s for table %s",
        pTab->azModuleArg[0], pTab->zName);
    return 0.0;
  }
#endif

  /* Set the aConstraint[].usable fields and initialize all 
  ** output variables to zero.
  **
  ** aConstraint[].usable is true for constraints where the right-hand
  ** side contains only references to tables to the left of the current
  ** table.  In other words, if the constraint is of the form:
................................................................................
  pIdxInfo->idxStr = 0;
  pIdxInfo->idxNum = 0;
  pIdxInfo->needToFreeIdxStr = 0;
  pIdxInfo->orderByConsumed = 0;
  /* ((double)2) In case of SQLITE_OMIT_FLOATING_POINT... */
  pIdxInfo->estimatedCost = SQLITE_BIG_DBL / ((double)2);
  nOrderBy = pIdxInfo->nOrderBy;
  if( pIdxInfo->nOrderBy && !orderByUsable ){
    *(int*)&pIdxInfo->nOrderBy = 0;
  }

  (void)sqlite3SafetyOff(pParse->db);
  WHERETRACE(("xBestIndex for %s\n", pTab->zName));
  TRACE_IDX_INPUTS(pIdxInfo);
  rc = pVtab->pModule->xBestIndex(pVtab, pIdxInfo);
  TRACE_IDX_OUTPUTS(pIdxInfo);
  (void)sqlite3SafetyOn(pParse->db);

  if( rc!=SQLITE_OK ){





    if( rc==SQLITE_NOMEM ){
      pParse->db->mallocFailed = 1;
    }else if( !pVtab->zErrMsg ){

      sqlite3ErrorMsg(pParse, "%s", sqlite3ErrStr(rc));

    }else{
      sqlite3ErrorMsg(pParse, "%s", pVtab->zErrMsg);

    }
  }
  sqlite3DbFree(pParse->db, pVtab->zErrMsg);
  pVtab->zErrMsg = 0;



  for(i=0; i<pIdxInfo->nConstraint; i++){
    if( !pIdxInfo->aConstraint[i].usable && pUsage[i].argvIndex>0 ){
      sqlite3ErrorMsg(pParse, 
          "table %s: xBestIndex returned an invalid plan", pTab->zName);
      /* (double)0 In case of SQLITE_OMIT_FLOATING_POINT... */
      return (double)0;
    }
  }

  *(int*)&pIdxInfo->nOrderBy = nOrderBy;
  return pIdxInfo->estimatedCost;




}
#endif /* SQLITE_OMIT_VIRTUALTABLE */

/*
** Find the query plan for accessing a particular table.  Write the
** best query plan and its cost into the WhereCost object supplied as the
** last parameter.
................................................................................
** then the cost is calculated in the usual way.
**
** If a NOT INDEXED clause (pSrc->notIndexed!=0) was attached to the table 
** in the SELECT statement, then no indexes are considered. However, the 
** selected plan may still take advantage of the tables built-in rowid
** index.
*/
static void bestIndex(
  Parse *pParse,              /* The parsing context */
  WhereClause *pWC,           /* The WHERE clause */
  struct SrcList_item *pSrc,  /* The FROM clause term to search */
  Bitmask notReady,           /* Mask of cursors that are not available */
  ExprList *pOrderBy,         /* The ORDER BY clause */
  WhereCost *pCost            /* Lowest cost query plan */
){
................................................................................
  int rev;                    /* True to scan in reverse order */
  int wsFlags;                /* Flags associated with pProbe */
  int nEq;                    /* Number of == or IN constraints */
  int eqTermMask;             /* Mask of valid equality operators */
  double cost;                /* Cost of using pProbe */
  double nRow;                /* Estimated number of rows in result set */
  int i;                      /* Loop counter */
  Bitmask maskSrc;            /* Bitmask for the pSrc table */

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

................................................................................
    if( cost<pCost->rCost ){
      pCost->rCost = cost;
      pCost->nRow = nRow;
      pCost->plan.wsFlags = wsFlags;
    }
  }

#ifndef SQLITE_OMIT_OR_OPTIMIZATION
  /* Search for an OR-clause that can be used to look up the table.
  */
  maskSrc = getMask(pWC->pMaskSet, iCur);
  for(i=0, pTerm=pWC->a; i<pWC->nTerm; i++, pTerm++){
    WhereClause tempWC;
    tempWC = *pWC;
    if( pTerm->eOperator==WO_OR 
        && ((pTerm->prereqAll & ~maskSrc) & notReady)==0
        && (pTerm->u.pOrInfo->indexable & maskSrc)!=0 ){
      WhereClause *pOrWC = &pTerm->u.pOrInfo->wc;
      WhereTerm *pOrTerm;
      int j;
      int sortable = 0;
      double rTotal = 0;
      nRow = 0;
      for(j=0, pOrTerm=pOrWC->a; j<pOrWC->nTerm; j++, pOrTerm++){
        WhereCost sTermCost;
        WHERETRACE(("... Multi-index OR testing for term %d of %d....\n", j,i));
        if( pOrTerm->eOperator==WO_AND ){
          WhereClause *pAndWC = &pOrTerm->u.pAndInfo->wc;
          bestIndex(pParse, pAndWC, pSrc, notReady, 0, &sTermCost);
        }else if( pOrTerm->leftCursor==iCur ){
          tempWC.a = pOrTerm;
          tempWC.nTerm = 1;
          bestIndex(pParse, &tempWC, pSrc, notReady, 0, &sTermCost);
        }else{
          continue;
        }
        rTotal += sTermCost.rCost;
        nRow += sTermCost.nRow;
        if( rTotal>=pCost->rCost ) break;
      }
      if( pOrderBy!=0 ){
        if( sortableByRowid(iCur, pOrderBy, pWC->pMaskSet, &rev) && !rev ){
          sortable = 1;
        }else{
          rTotal += nRow*estLog(nRow);
          WHERETRACE(("... sorting increases OR cost to %.9g\n", rTotal));
        }
      }
      WHERETRACE(("... multi-index OR cost=%.9g nrow=%.9g\n",
                  rTotal, nRow));
      if( rTotal<pCost->rCost ){
        pCost->rCost = rTotal;
        pCost->nRow = nRow;
        pCost->plan.wsFlags = WHERE_MULTI_OR;
        pCost->plan.u.pTerm = pTerm;
        if( sortable ){
          pCost->plan.wsFlags = WHERE_ORDERBY|WHERE_MULTI_OR;
        }
      }
    }
  }
#endif /* SQLITE_OMIT_OR_OPTIMIZATION */

  /* If the pSrc table is the right table of a LEFT JOIN then we may not
  ** use an index to satisfy IS NULL constraints on that table.  This is
  ** because columns might end up being NULL if the table does not match -
  ** a circumstance which the index cannot help us discover.  Ticket #2177.
  */
  if( (pSrc->jointype & JT_LEFT)!=0 ){
................................................................................
  pCost->plan.wsFlags |= eqTermMask;
  WHERETRACE(("best index is %s, cost=%.9g, nrow=%.9g, wsFlags=%x, nEq=%d\n",
        (pCost->plan.wsFlags & WHERE_INDEXED)!=0 ?
             pCost->plan.u.pIdx->zName : "(none)", pCost->nRow,
        pCost->rCost, pCost->plan.wsFlags, pCost->plan.nEq));
}



























/*
** Disable a term in the WHERE clause.  Except, do not disable the term
** if it controls a LEFT OUTER JOIN and it did not originate in the ON
** or USING clause of that join.
**
** Consider the term t2.z='ok' in the following queries:
................................................................................
    if( (pTerm->eOperator & (WO_ISNULL|WO_IN))==0 ){
      sqlite3VdbeAddOp2(v, OP_IsNull, regBase+j, pLevel->addrBrk);
    }
  }
  return regBase;
}

/*
** Return TRUE if the WhereClause pWC contains no terms that
** are not virtual and which have not been coded.
**
** To put it another way, return TRUE if no additional WHERE clauses
** tests are required in order to establish that the current row
** should go to output and return FALSE if there are some terms of
** the WHERE clause that need to be validated before outputing the row.
*/
static int whereRowReadyForOutput(WhereClause *pWC){
  WhereTerm *pTerm;
  int j;
 
  for(pTerm=pWC->a, j=pWC->nTerm; j>0; j--, pTerm++){
    if( (pTerm->wtFlags & (TERM_VIRTUAL|TERM_CODED))==0 ) return 0;
  }
  return 1;
}

/*
** Generate code for the start of the iLevel-th loop in the WHERE clause
** implementation described by pWInfo.
*/
static Bitmask codeOneLoopStart(
  WhereInfo *pWInfo,   /* Complete information about the WHERE clause */
  int iLevel,          /* Which level of pWInfo->a[] should be coded */
................................................................................
  Parse *pParse;                  /* Parsing context */
  Vdbe *v;                        /* The prepared stmt under constructions */
  struct SrcList_item *pTabItem;  /* FROM clause term being coded */
  int addrBrk;                    /* Jump here to break out of the loop */
  int addrCont;                   /* Jump here to continue with next cycle */
  int regRowSet;       /* Write rowids to this RowSet if non-negative */
  int codeRowSetEarly; /* True if index fully constrains the search */
  





















  pParse = pWInfo->pParse;
  v = pParse->pVdbe;
  pWC = pWInfo->pWC;
  pLevel = &pWInfo->a[iLevel];
  pTabItem = &pWInfo->pTabList->a[pLevel->iFrom];
  iCur = pTabItem->iCursor;
  bRev = (pLevel->plan.wsFlags & WHERE_REVERSE)!=0;
  omitTable = (pLevel->plan.wsFlags & WHERE_IDX_ONLY)!=0;

  regRowSet = pWInfo->regRowSet;
  codeRowSetEarly = 0;

  /* Create labels for the "break" and "continue" instructions
  ** for the current loop.  Jump to addrBrk to break out of a loop.
  ** Jump to cont to go immediately to the next iteration of the
  ** loop.
................................................................................
        int iTerm = aConstraint[j].iTermOffset;
        disableTerm(pLevel, &pWC->a[iTerm]);
      }
    }
    pLevel->op = OP_VNext;
    pLevel->p1 = iCur;
    pLevel->p2 = sqlite3VdbeCurrentAddr(v);
    codeRowSetEarly = regRowSet>=0 ? whereRowReadyForOutput(pWC) : 0;
    if( codeRowSetEarly ){
      sqlite3VdbeAddOp2(v, OP_VRowid, iCur, iReg);
      sqlite3VdbeAddOp2(v, OP_RowSetAdd, regRowSet, iReg);
    }
    sqlite3ReleaseTempRange(pParse, iReg, nConstraint+2);
  }else
#endif /* SQLITE_OMIT_VIRTUALTABLE */

  if( pLevel->plan.wsFlags & WHERE_ROWID_EQ ){
    /* Case 1:  We can directly reference a single row using an
    **          equality comparison against the ROWID field.  Or
    **          we reference multiple rows using a "rowid IN (...)"
    **          construct.
    */
    int r1;
    int rtmp = sqlite3GetTempReg(pParse);
    pTerm = findTerm(pWC, iCur, -1, notReady, WO_EQ|WO_IN, 0);
    assert( pTerm!=0 );
    assert( pTerm->pExpr!=0 );
    assert( pTerm->leftCursor==iCur );
    assert( omitTable==0 );
    r1 = codeEqualityTerm(pParse, pTerm, pLevel, rtmp);
    addrNxt = pLevel->addrNxt;
    sqlite3VdbeAddOp2(v, OP_MustBeInt, r1, addrNxt);
    sqlite3VdbeAddOp3(v, OP_NotExists, iCur, addrNxt, r1);
    codeRowSetEarly = (pWC->nTerm==1 && regRowSet>=0) ?1:0;
    if( codeRowSetEarly ){
      sqlite3VdbeAddOp2(v, OP_RowSetAdd, regRowSet, r1);
    }
    sqlite3ReleaseTempReg(pParse, rtmp);
    VdbeComment((v, "pk"));
    pLevel->op = OP_Noop;
  }else if( pLevel->plan.wsFlags & WHERE_ROWID_RANGE ){
    /* Case 2:  We have an inequality comparison against the ROWID field.
    */
    int testOp = OP_Noop;
    int start;
................................................................................
      disableTerm(pLevel, pEnd);
    }
    start = sqlite3VdbeCurrentAddr(v);
    pLevel->op = bRev ? OP_Prev : OP_Next;
    pLevel->p1 = iCur;
    pLevel->p2 = start;
    pLevel->p5 = (pStart==0 && pEnd==0) ?1:0;
    codeRowSetEarly = regRowSet>=0 ? whereRowReadyForOutput(pWC) : 0;
    if( codeRowSetEarly || testOp!=OP_Noop ){
      int r1 = sqlite3GetTempReg(pParse);
      sqlite3VdbeAddOp2(v, OP_Rowid, iCur, r1);
      if( testOp!=OP_Noop ){
        sqlite3VdbeAddOp3(v, testOp, memEndValue, addrBrk, r1);
        sqlite3VdbeChangeP5(v, SQLITE_AFF_NUMERIC | SQLITE_JUMPIFNULL);
      }
      if( codeRowSetEarly ){
        sqlite3VdbeAddOp2(v, OP_RowSetAdd, regRowSet, r1);
      }
      sqlite3ReleaseTempReg(pParse, r1);
    }
  }else if( pLevel->plan.wsFlags & (WHERE_COLUMN_RANGE|WHERE_COLUMN_EQ) ){
    /* Case 3: A scan using an index.
    **
    **         The WHERE clause may contain zero or more equality 
    **         terms ("==" or "IN" operators) that refer to the N
    **         left-most columns of the index. It may also contain
................................................................................
    r1 = sqlite3GetTempReg(pParse);
    testcase( pLevel->plan.wsFlags & WHERE_BTM_LIMIT );
    testcase( pLevel->plan.wsFlags & WHERE_TOP_LIMIT );
    if( pLevel->plan.wsFlags & (WHERE_BTM_LIMIT|WHERE_TOP_LIMIT) ){
      sqlite3VdbeAddOp3(v, OP_Column, iIdxCur, nEq, r1);
      sqlite3VdbeAddOp2(v, OP_IsNull, r1, addrCont);
    }


    /* Seek the table cursor, if required */
    disableTerm(pLevel, pRangeStart);
    disableTerm(pLevel, pRangeEnd);
    codeRowSetEarly = regRowSet>=0 ? whereRowReadyForOutput(pWC) : 0;
    if( !omitTable || codeRowSetEarly ){

      sqlite3VdbeAddOp2(v, OP_IdxRowid, iIdxCur, r1);
      if( codeRowSetEarly ){
        sqlite3VdbeAddOp2(v, OP_RowSetAdd, regRowSet, r1);
      }else{
        sqlite3VdbeAddOp2(v, OP_Seek, iCur, r1);  /* Deferred seek */
      }
    }
    sqlite3ReleaseTempReg(pParse, r1);

    /* Record the instruction used to terminate the loop. Disable 
    ** WHERE clause terms made redundant by the index range scan.
    */
    pLevel->op = bRev ? OP_Prev : OP_Next;
    pLevel->p1 = iIdxCur;
  }else
................................................................................
    **   CREATE INDEX i1 ON t1(a);
    **   CREATE INDEX i2 ON t1(b);
    **   CREATE INDEX i3 ON t1(c);
    **
    **   SELECT * FROM t1 WHERE a=5 OR b=7 OR (c=11 AND d=13)
    **
    ** In the example, there are three indexed terms connected by OR.
    ** The top of the loop is constructed by creating a RowSet object
    ** and populating it.  Then looping over elements of the rowset.

    **







    **        Null 1
    **        # fill RowSet 1 with entries where a=5 using i1
    **        # fill Rowset 1 with entries where b=7 using i2
    **        # fill Rowset 1 with entries where c=11 and d=13 i3 and t1
    **     A: RowSetRead 1, B, 2
    **        Seek       i, 2
    **
    ** The bottom of the loop looks like this:


    **
    **        Goto       0, A


    **     B:






    */
    int regOrRowset;       /* Register holding the RowSet object */
    int regNextRowid;      /* Register holding next rowid */


    WhereClause *pOrWc;    /* The OR-clause broken out into subterms */
    WhereTerm *pOrTerm;    /* A single subterm within the OR-clause */
    SrcList oneTab;        /* Shortened table list */






   
    pTerm = pLevel->plan.u.pTerm;
    assert( pTerm!=0 );
    assert( pTerm->eOperator==WO_OR );
    assert( (pTerm->wtFlags & TERM_ORINFO)!=0 );
    pOrWc = &pTerm->u.pOrInfo->wc;
    codeRowSetEarly = (regRowSet>=0 && pWC->nTerm==1) ?1:0;

    if( codeRowSetEarly ){
      regOrRowset = regRowSet;
    }else{
      regOrRowset = sqlite3GetTempReg(pParse);
      sqlite3VdbeAddOp2(v, OP_Null, 0, regOrRowset);
    }
    oneTab.nSrc = 1;
    oneTab.nAlloc = 1;
    oneTab.a[0] = *pTabItem;
    for(j=0, pOrTerm=pOrWc->a; j<pOrWc->nTerm; j++, pOrTerm++){
      WhereInfo *pSubWInfo;
      if( pOrTerm->leftCursor!=iCur && pOrTerm->eOperator!=WO_AND ) continue;
      pSubWInfo = sqlite3WhereBegin(pParse, &oneTab, pOrTerm->pExpr, 0,
                        WHERE_FILL_ROWSET | WHERE_OMIT_OPEN | WHERE_OMIT_CLOSE,
                        regOrRowset);
      if( pSubWInfo ){
        sqlite3WhereEnd(pSubWInfo);
      }
    }
    sqlite3VdbeResolveLabel(v, addrCont);
    if( !codeRowSetEarly ){
      regNextRowid = sqlite3GetTempReg(pParse);
      addrCont = 
         sqlite3VdbeAddOp3(v, OP_RowSetRead, regOrRowset,addrBrk,regNextRowid);
      sqlite3VdbeAddOp2(v, OP_Seek, iCur, regNextRowid);
      sqlite3ReleaseTempReg(pParse, regNextRowid);
      /* sqlite3ReleaseTempReg(pParse, regOrRowset); // Preserve the RowSet */
      pLevel->op = OP_Goto;
      pLevel->p2 = addrCont;
    }else{
      pLevel->op = OP_Noop;
    }





















    disableTerm(pLevel, pTerm);
  }else
#endif /* SQLITE_OMIT_OR_OPTIMIZATION */

  {
    /* Case 5:  There is no usable index.  We must do a complete
    **          scan of the entire table.
................................................................................
    static const u8 aStart[] = { OP_Rewind, OP_Last };
    assert( bRev==0 || bRev==1 );
    assert( omitTable==0 );
    pLevel->op = aStep[bRev];
    pLevel->p1 = iCur;
    pLevel->p2 = 1 + sqlite3VdbeAddOp2(v, aStart[bRev], iCur, addrBrk);
    pLevel->p5 = SQLITE_STMTSTATUS_FULLSCAN_STEP;
    codeRowSetEarly = 0;
  }
  notReady &= ~getMask(pWC->pMaskSet, iCur);

  /* Insert code to test every subexpression that can be completely
  ** computed using the current set of tables.
  */
  k = 0;
................................................................................
      if( (pTerm->prereqAll & notReady)!=0 ) continue;
      assert( pTerm->pExpr );
      sqlite3ExprIfFalse(pParse, pTerm->pExpr, addrCont, SQLITE_JUMPIFNULL);
      pTerm->wtFlags |= TERM_CODED;
    }
  }

  /*
  ** If it was requested to store the results in a rowset and that has
  ** not already been do, then do so now.



  */
  if( regRowSet>=0 && !codeRowSetEarly ){

    int r1 = sqlite3GetTempReg(pParse);
#ifndef SQLITE_OMIT_VIRTUALTABLE
    if(  (pLevel->plan.wsFlags & WHERE_VIRTUALTABLE)!=0 ){
      sqlite3VdbeAddOp2(v, OP_VRowid, iCur, r1);
    }else
#endif
    {
      sqlite3VdbeAddOp2(v, OP_Rowid, iCur, r1);
    }




    sqlite3VdbeAddOp2(v, OP_RowSetAdd, regRowSet, r1);
    sqlite3ReleaseTempReg(pParse, r1);



  }



  return notReady;
}

#if defined(SQLITE_TEST)
/*
** The following variable holds a text description of query plan generated
................................................................................
*/
static void whereInfoFree(sqlite3 *db, WhereInfo *pWInfo){
  if( pWInfo ){
    int i;
    for(i=0; i<pWInfo->nLevel; i++){
      sqlite3_index_info *pInfo = pWInfo->a[i].pIdxInfo;
      if( pInfo ){
        assert( pInfo->needToFreeIdxStr==0 || db->mallocFailed );
        if( pInfo->needToFreeIdxStr ){
          sqlite3_free(pInfo->idxStr);
        }
        sqlite3DbFree(db, pInfo);
      }
    }
    whereClauseClear(pWInfo->pWC);
................................................................................
  if( db->mallocFailed ){
    goto whereBeginError;
  }
  pWInfo->nLevel = pTabList->nSrc;
  pWInfo->pParse = pParse;
  pWInfo->pTabList = pTabList;
  pWInfo->iBreak = sqlite3VdbeMakeLabel(v);
  pWInfo->regRowSet = (wctrlFlags & WHERE_FILL_ROWSET) ? regRowSet : -1;
  pWInfo->pWC = pWC = (WhereClause *)&((u8 *)pWInfo)[nByteWInfo];
  pWInfo->wctrlFlags = wctrlFlags;
  pMaskSet = (WhereMaskSet*)&pWC[1];


  /* Split the WHERE clause into separate subexpressions where each
  ** subexpression is separated by an AND operator.
  */
  initMaskSet(pMaskSet);
  whereClauseInit(pWC, pParse, pMaskSet);
  sqlite3ExprCodeConstants(pParse, pWhere);
................................................................................
    int bestJ = 0;              /* The value of j */
    Bitmask m;                  /* Bitmask value for j or bestJ */
    int once = 0;               /* True when first table is seen */

    memset(&bestPlan, 0, sizeof(bestPlan));
    bestPlan.rCost = SQLITE_BIG_DBL;
    for(j=iFrom, pTabItem=&pTabList->a[j]; j<pTabList->nSrc; j++, pTabItem++){
      int doNotReorder;  /* True if this table should not be reordered */
      WhereCost sCost;   /* Cost information from bestIndex() */


      doNotReorder =  (pTabItem->jointype & (JT_LEFT|JT_CROSS))!=0;
      if( once && doNotReorder ) break;
      m = getMask(pMaskSet, pTabItem->iCursor);
      if( (m & notReady)==0 ){
        if( j==iFrom ) iFrom++;
        continue;
      }


      assert( pTabItem->pTab );
#ifndef SQLITE_OMIT_VIRTUALTABLE
      if( IsVirtual(pTabItem->pTab) ){
        sqlite3_index_info *pVtabIdx; /* Current virtual index */
        sqlite3_index_info **ppIdxInfo = &pWInfo->a[j].pIdxInfo;
        sCost.rCost = bestVirtualIndex(pParse, pWC, pTabItem, notReady,
                                       ppOrderBy ? *ppOrderBy : 0, i==0,
                                       ppIdxInfo);
        sCost.plan.wsFlags = WHERE_VIRTUALTABLE;
        sCost.plan.u.pVtabIdx = pVtabIdx = *ppIdxInfo;
        if( pVtabIdx && pVtabIdx->orderByConsumed ){
          sCost.plan.wsFlags = WHERE_VIRTUALTABLE | WHERE_ORDERBY;
        }
        sCost.plan.nEq = 0;
        /* (double)2 In case of SQLITE_OMIT_FLOATING_POINT... */
        if( (SQLITE_BIG_DBL/((double)2))<sCost.rCost ){
          /* The cost is not allowed to be larger than SQLITE_BIG_DBL (the
          ** inital value of lowestCost in this loop. If it is, then
          ** the (cost<lowestCost) test below will never be true.
          */ 
          /* (double)2 In case of SQLITE_OMIT_FLOATING_POINT... */
          sCost.rCost = (SQLITE_BIG_DBL/((double)2));
        }
      }else 
#endif
      {
        bestIndex(pParse, pWC, pTabItem, notReady,
                  (i==0 && ppOrderBy) ? *ppOrderBy : 0, &sCost);
      }
      if( once==0 || sCost.rCost<bestPlan.rCost ){
        once = 1;
        bestPlan = sCost;
        bestJ = j;
      }
      if( doNotReorder ) break;
................................................................................
        ** guaranteed to find the index specified in the INDEXED BY clause
        ** if it find an index at all. */
        assert( bestPlan.plan.u.pIdx==pIdx );
      }
    }
  }
  WHERETRACE(("*** Optimizer Finished ***\n"));
  if( db->mallocFailed ){
    goto whereBeginError;
  }

  /* If the total query only selects a single row, then the ORDER BY
  ** clause is irrelevant.
  */
  if( (andFlags & WHERE_UNIQUE)!=0 && ppOrderBy ){







|







 








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

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







 







|
|
|
|
|
|
|
|


<


<




<


|
<



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







 







<
<
|
<
<
<
<
<







 







|
|


|
|
<
<
<
<
|
<
>
>
>
>
>
|
|
<
>
|
>
|
<
>
|
<
|
|
>
>
|
<
<
|
|
<
<
|
<
<
<
<
>
>
>
>







 







|







 







<







 







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







 







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







 







<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<







 







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








|
>







 







<
<
<
<
<










<
|





|

|
|
<
<
<
<
<







 







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







 







>




<
|
>
|
<
<
<
|
|
<
<







 







|
|
>

>
>
>
>
>
>
>
|
<
<
<
<
|

<
>
>

<
>
>
|
>
>
>
>
>
>

<
<
>
>

|

>
>
>
>
>
>






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







 







<







 







|
|
|
>
>
>
|
<
>
|

|
|
|

|
|
|
>
>
>
>
|
<
>
>
>
|
>
>







 







|







 







|



>







 







|
|
>








>
>



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



|
<







 







|







12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
....
1470
1471
1472
1473
1474
1475
1476
1477
1478
1479
1480
1481
1482
1483
1484
1485
1486
1487
1488
1489
1490
1491
1492
1493
1494
1495
1496
1497
1498
1499
1500
1501
1502
1503
1504
1505
1506
1507
1508
1509
1510
1511
1512
1513
1514
1515
1516
1517
1518
1519
1520
1521
1522
1523
1524
1525
1526
1527
1528
1529
1530
1531
1532
1533
1534
1535
1536
1537
1538
1539
1540
1541
1542
1543
1544
1545
1546
1547
1548
1549
1550
1551
1552
1553
1554
1555
1556
1557
1558
1559
1560
1561
1562
1563
1564
1565
1566
1567
1568
1569
1570
1571
1572
1573
1574
1575
1576
1577
1578
1579
1580
1581
1582
1583
1584
1585
1586
1587
1588
1589
1590
1591
1592
1593
1594
1595
1596
1597
1598
1599
1600
1601
1602
1603
1604
1605
1606
1607
1608
1609
1610
1611
1612
1613
1614
1615
1616
1617
1618
1619
1620
1621
1622
1623
1624
1625
1626
1627
1628
1629
1630
1631
1632
1633
1634
1635
1636
1637
1638
1639
1640
1641
1642
1643
1644
1645
1646
1647
1648
1649
1650
1651
1652
1653
1654
1655
1656
1657
1658
1659
1660
1661
1662
1663
1664
1665
1666
1667
1668
1669
1670
1671
1672
1673
1674
1675
1676
1677
1678
1679
1680
1681
1682
1683
1684
1685
1686
1687
1688
1689
1690
1691
1692
1693
1694
1695
1696
1697
1698
1699
1700
1701
1702
1703
1704
1705
1706
1707
1708
1709
1710
1711
1712
1713
1714
1715
1716
1717
1718
1719
1720
1721
1722
1723
1724
....
1727
1728
1729
1730
1731
1732
1733
1734
1735
1736
1737
1738
1739
1740
1741
1742
1743

1744
1745

1746
1747
1748
1749

1750
1751
1752

1753
1754
1755







































1756










































1757
1758
1759
1760
1761
1762
1763
....
1764
1765
1766
1767
1768
1769
1770


1771





1772
1773
1774
1775
1776
1777
1778
....
1804
1805
1806
1807
1808
1809
1810
1811
1812
1813
1814
1815
1816




1817

1818
1819
1820
1821
1822
1823
1824

1825
1826
1827
1828

1829
1830

1831
1832
1833
1834
1835


1836
1837


1838




1839
1840
1841
1842
1843
1844
1845
1846
1847
1848
1849
....
1867
1868
1869
1870
1871
1872
1873
1874
1875
1876
1877
1878
1879
1880
1881
....
1885
1886
1887
1888
1889
1890
1891

1892
1893
1894
1895
1896
1897
1898
....
2000
2001
2002
2003
2004
2005
2006
2007






















































2008
2009
2010
2011
2012
2013
2014
....
2154
2155
2156
2157
2158
2159
2160
2161
2162
2163
2164
2165
2166
2167
2168
2169
2170
2171
2172
2173
2174
2175
2176
2177
2178
2179
2180
2181
2182
2183
2184
2185
2186
2187
2188
2189
2190
2191
2192
....
2375
2376
2377
2378
2379
2380
2381



















2382
2383
2384
2385
2386
2387
2388
....
2400
2401
2402
2403
2404
2405
2406
2407
2408
2409
2410
2411
2412
2413
2414
2415
2416
2417
2418
2419
2420
2421
2422
2423
2424
2425
2426
2427
2428
2429
2430
2431
2432
2433
2434
2435
2436
2437
2438
2439
2440
2441
2442
2443
2444
....
2499
2500
2501
2502
2503
2504
2505





2506
2507
2508
2509
2510
2511
2512
2513
2514
2515

2516
2517
2518
2519
2520
2521
2522
2523
2524
2525





2526
2527
2528
2529
2530
2531
2532
....
2585
2586
2587
2588
2589
2590
2591

2592
2593
2594

2595
2596





2597
2598
2599
2600
2601
2602
2603
....
2776
2777
2778
2779
2780
2781
2782
2783
2784
2785
2786
2787

2788
2789
2790



2791
2792


2793
2794
2795
2796
2797
2798
2799
....
2808
2809
2810
2811
2812
2813
2814
2815
2816
2817
2818
2819
2820
2821
2822
2823
2824
2825
2826




2827
2828

2829
2830
2831

2832
2833
2834
2835
2836
2837
2838
2839
2840
2841


2842
2843
2844
2845
2846
2847
2848
2849
2850
2851
2852
2853
2854
2855
2856
2857
2858
2859
2860
2861
2862
2863
2864
2865
2866
2867
2868
2869
2870
2871
2872
2873
2874
2875
2876
2877
2878
2879
2880
2881
2882
2883
2884
2885
2886
2887
2888
2889
2890
2891
2892
2893
2894
2895
2896
2897
2898
2899
2900
2901
2902
2903
2904
2905
2906
2907
2908
2909
2910
2911
2912
2913
2914
2915
2916
2917
2918
2919
2920
....
2923
2924
2925
2926
2927
2928
2929

2930
2931
2932
2933
2934
2935
2936
....
2968
2969
2970
2971
2972
2973
2974
2975
2976
2977
2978
2979
2980
2981

2982
2983
2984
2985
2986
2987
2988
2989
2990
2991
2992
2993
2994
2995
2996

2997
2998
2999
3000
3001
3002
3003
3004
3005
3006
3007
3008
3009
....
3022
3023
3024
3025
3026
3027
3028
3029
3030
3031
3032
3033
3034
3035
3036
....
3178
3179
3180
3181
3182
3183
3184
3185
3186
3187
3188
3189
3190
3191
3192
3193
3194
3195
3196
....
3266
3267
3268
3269
3270
3271
3272
3273
3274
3275
3276
3277
3278
3279
3280
3281
3282
3283
3284
3285
3286
3287
3288

3289
3290

















3291
3292
3293
3294

3295
3296
3297
3298
3299
3300
3301
....
3332
3333
3334
3335
3336
3337
3338
3339
3340
3341
3342
3343
3344
3345
3346
** This module contains C code that generates VDBE code used to process
** the WHERE clause of SQL statements.  This module is responsible for
** generating the code that loops through a table looking for applicable
** rows.  Indices are selected and used to speed the search when doing
** so is applicable.  Because this module is responsible for selecting
** indices, you might also think of this module as the "query optimizer".
**
** $Id: where.c,v 1.383 2009/04/21 09:02:47 danielk1977 Exp $
*/
#include "sqliteInt.h"

/*
** Trace output macros
*/
#if defined(SQLITE_TEST) || defined(SQLITE_DEBUG)
................................................................................
  sqlite3DebugPrintf("  orderByConsumed=%d\n", p->orderByConsumed);
  sqlite3DebugPrintf("  estimatedCost=%g\n", p->estimatedCost);
}
#else
#define TRACE_IDX_INPUTS(A)
#define TRACE_IDX_OUTPUTS(A)
#endif

/* 
** Required because bestIndex() is called by bestOrClauseIndex() 
*/
static void bestIndex(
    Parse*, WhereClause*, struct SrcList_item*, Bitmask, ExprList*, WhereCost*);

/*
** This routine attempts to find an scanning strategy that can be used 
** to optimize an 'OR' expression that is part of a WHERE clause. 
**
** The table associated with FROM clause term pSrc may be either a
** regular B-Tree table or a virtual table.
*/
static void bestOrClauseIndex(
  Parse *pParse,              /* The parsing context */
  WhereClause *pWC,           /* The WHERE clause */
  struct SrcList_item *pSrc,  /* The FROM clause term to search */
  Bitmask notReady,           /* Mask of cursors that are not available */
  ExprList *pOrderBy,         /* The ORDER BY clause */
  WhereCost *pCost            /* Lowest cost query plan */
){
#ifndef SQLITE_OMIT_OR_OPTIMIZATION
  const int iCur = pSrc->iCursor;   /* The cursor of the table to be accessed */
  const Bitmask maskSrc = getMask(pWC->pMaskSet, iCur);  /* Bitmask for pSrc */
  WhereTerm * const pWCEnd = &pWC->a[pWC->nTerm];        /* End of pWC->a[] */
  WhereTerm *pTerm;                 /* A single term of the WHERE clause */

  /* Search the WHERE clause terms for a usable WO_OR term. */
  for(pTerm=pWC->a; pTerm<pWCEnd; pTerm++){
    if( pTerm->eOperator==WO_OR 
     && ((pTerm->prereqAll & ~maskSrc) & notReady)==0
     && (pTerm->u.pOrInfo->indexable & maskSrc)!=0 
    ){
      WhereClause * const pOrWC = &pTerm->u.pOrInfo->wc;
      WhereTerm * const pOrWCEnd = &pOrWC->a[pOrWC->nTerm];
      WhereTerm *pOrTerm;
      int flags = WHERE_MULTI_OR;
      double rTotal = 0;
      double nRow = 0;

      for(pOrTerm=pOrWC->a; pOrTerm<pOrWCEnd; pOrTerm++){
        WhereCost sTermCost;
        WHERETRACE(("... Multi-index OR testing for term %d of %d....\n", 
          (pOrTerm - pOrWC->a), (pTerm - pWC->a)
        ));
        if( pOrTerm->eOperator==WO_AND ){
          WhereClause *pAndWC = &pOrTerm->u.pAndInfo->wc;
          bestIndex(pParse, pAndWC, pSrc, notReady, 0, &sTermCost);
        }else if( pOrTerm->leftCursor==iCur ){
          WhereClause tempWC;
          tempWC.pParse = pWC->pParse;
          tempWC.pMaskSet = pWC->pMaskSet;
          tempWC.op = TK_AND;
          tempWC.a = pOrTerm;
          tempWC.nTerm = 1;
          bestIndex(pParse, &tempWC, pSrc, notReady, 0, &sTermCost);
        }else{
          continue;
        }
        rTotal += sTermCost.rCost;
        nRow += sTermCost.nRow;
        if( rTotal>=pCost->rCost ) break;
      }

      /* If there is an ORDER BY clause, increase the scan cost to account 
      ** for the cost of the sort. */
      if( pOrderBy!=0 ){
        rTotal += nRow*estLog(nRow);
        WHERETRACE(("... sorting increases OR cost to %.9g\n", rTotal));
      }

      /* If the cost of scanning using this OR term for optimization is
      ** less than the current cost stored in pCost, replace the contents
      ** of pCost. */
      WHERETRACE(("... multi-index OR cost=%.9g nrow=%.9g\n", rTotal, nRow));
      if( rTotal<pCost->rCost ){
        pCost->rCost = rTotal;
        pCost->nRow = nRow;
        pCost->plan.wsFlags = flags;
        pCost->plan.u.pTerm = pTerm;
      }
    }
  }
#endif /* SQLITE_OMIT_OR_OPTIMIZATION */
}

#ifndef SQLITE_OMIT_VIRTUALTABLE
/*
** Allocate and populate an sqlite3_index_info structure. It is the 
** responsibility of the caller to eventually release the structure
** by passing the pointer returned by this function to sqlite3_free().
*/
static sqlite3_index_info *allocateIndexInfo(
  Parse *pParse, 
  WhereClause *pWC,
  struct SrcList_item *pSrc,
  ExprList *pOrderBy
){
  int i, j;
  int nTerm;
  struct sqlite3_index_constraint *pIdxCons;
  struct sqlite3_index_orderby *pIdxOrderBy;
  struct sqlite3_index_constraint_usage *pUsage;
  WhereTerm *pTerm;
  int nOrderBy;
  sqlite3_index_info *pIdxInfo;

  WHERETRACE(("Recomputing index info for %s...\n", pSrc->pTab->zName));

  /* Count the number of possible WHERE clause constraints referring
  ** to this virtual table */
  for(i=nTerm=0, pTerm=pWC->a; i<pWC->nTerm; i++, pTerm++){
    if( pTerm->leftCursor != pSrc->iCursor ) continue;
    assert( (pTerm->eOperator&(pTerm->eOperator-1))==0 );
    testcase( pTerm->eOperator==WO_IN );
    testcase( pTerm->eOperator==WO_ISNULL );
    if( pTerm->eOperator & (WO_IN|WO_ISNULL) ) continue;
    nTerm++;
  }

  /* If the ORDER BY clause contains only columns in the current 
  ** virtual table then allocate space for the aOrderBy part of
  ** the sqlite3_index_info structure.
  */
  nOrderBy = 0;
  if( pOrderBy ){
    for(i=0; i<pOrderBy->nExpr; i++){
      Expr *pExpr = pOrderBy->a[i].pExpr;
      if( pExpr->op!=TK_COLUMN || pExpr->iTable!=pSrc->iCursor ) break;
    }
    if( i==pOrderBy->nExpr ){
      nOrderBy = pOrderBy->nExpr;
    }
  }

  /* Allocate the sqlite3_index_info structure
  */
  pIdxInfo = sqlite3DbMallocZero(pParse->db, sizeof(*pIdxInfo)
                           + (sizeof(*pIdxCons) + sizeof(*pUsage))*nTerm
                           + sizeof(*pIdxOrderBy)*nOrderBy );
  if( pIdxInfo==0 ){
    sqlite3ErrorMsg(pParse, "out of memory");
    /* (double)0 In case of SQLITE_OMIT_FLOATING_POINT... */
    return 0;
  }

  /* Initialize the structure.  The sqlite3_index_info structure contains
  ** many fields that are declared "const" to prevent xBestIndex from
  ** changing them.  We have to do some funky casting in order to
  ** initialize those fields.
  */
  pIdxCons = (struct sqlite3_index_constraint*)&pIdxInfo[1];
  pIdxOrderBy = (struct sqlite3_index_orderby*)&pIdxCons[nTerm];
  pUsage = (struct sqlite3_index_constraint_usage*)&pIdxOrderBy[nOrderBy];
  *(int*)&pIdxInfo->nConstraint = nTerm;
  *(int*)&pIdxInfo->nOrderBy = nOrderBy;
  *(struct sqlite3_index_constraint**)&pIdxInfo->aConstraint = pIdxCons;
  *(struct sqlite3_index_orderby**)&pIdxInfo->aOrderBy = pIdxOrderBy;
  *(struct sqlite3_index_constraint_usage**)&pIdxInfo->aConstraintUsage =
                                                                   pUsage;

  for(i=j=0, pTerm=pWC->a; i<pWC->nTerm; i++, pTerm++){
    if( pTerm->leftCursor != pSrc->iCursor ) continue;
    assert( (pTerm->eOperator&(pTerm->eOperator-1))==0 );
    testcase( pTerm->eOperator==WO_IN );
    testcase( pTerm->eOperator==WO_ISNULL );
    if( pTerm->eOperator & (WO_IN|WO_ISNULL) ) continue;
    pIdxCons[j].iColumn = pTerm->u.leftColumn;
    pIdxCons[j].iTermOffset = i;
    pIdxCons[j].op = (u8)pTerm->eOperator;
    /* The direct assignment in the previous line is possible only because
    ** the WO_ and SQLITE_INDEX_CONSTRAINT_ codes are identical.  The
    ** following asserts verify this fact. */
    assert( WO_EQ==SQLITE_INDEX_CONSTRAINT_EQ );
    assert( WO_LT==SQLITE_INDEX_CONSTRAINT_LT );
    assert( WO_LE==SQLITE_INDEX_CONSTRAINT_LE );
    assert( WO_GT==SQLITE_INDEX_CONSTRAINT_GT );
    assert( WO_GE==SQLITE_INDEX_CONSTRAINT_GE );
    assert( WO_MATCH==SQLITE_INDEX_CONSTRAINT_MATCH );
    assert( pTerm->eOperator & (WO_EQ|WO_LT|WO_LE|WO_GT|WO_GE|WO_MATCH) );
    j++;
  }
  for(i=0; i<nOrderBy; i++){
    Expr *pExpr = pOrderBy->a[i].pExpr;
    pIdxOrderBy[i].iColumn = pExpr->iColumn;
    pIdxOrderBy[i].desc = pOrderBy->a[i].sortOrder;
  }

  return pIdxInfo;
}

/*
** The table object reference passed as the second argument to this function
** must represent a virtual table. This function invokes the xBestIndex()
** method of the virtual table with the sqlite3_index_info pointer passed
** as the argument.
**
** If an error occurs, pParse is populated with an error message and a
** non-zero value is returned. Otherwise, 0 is returned and the output
** part of the sqlite3_index_info structure is left populated.
**
** Whether or not an error is returned, it is the responsibility of the
** caller to eventually free p->idxStr if p->needToFreeIdxStr indicates
** that this is required.
*/
static int vtabBestIndex(Parse *pParse, Table *pTab, sqlite3_index_info *p){
  sqlite3_vtab *pVtab = pTab->pVtab;
  int i;
  int rc;

  (void)sqlite3SafetyOff(pParse->db);
  WHERETRACE(("xBestIndex for %s\n", pTab->zName));
  TRACE_IDX_INPUTS(p);
  rc = pVtab->pModule->xBestIndex(pVtab, p);
  TRACE_IDX_OUTPUTS(p);
  (void)sqlite3SafetyOn(pParse->db);

  if( rc!=SQLITE_OK ){
    if( rc==SQLITE_NOMEM ){
      pParse->db->mallocFailed = 1;
    }else if( !pVtab->zErrMsg ){
      sqlite3ErrorMsg(pParse, "%s", sqlite3ErrStr(rc));
    }else{
      sqlite3ErrorMsg(pParse, "%s", pVtab->zErrMsg);
    }
  }
  sqlite3DbFree(pParse->db, pVtab->zErrMsg);
  pVtab->zErrMsg = 0;

  for(i=0; i<p->nConstraint; i++){
    if( !p->aConstraint[i].usable && p->aConstraintUsage[i].argvIndex>0 ){
      sqlite3ErrorMsg(pParse, 
          "table %s: xBestIndex returned an invalid plan", pTab->zName);
    }
  }

  return pParse->nErr;
}


/*
** Compute the best index for a virtual table.
**
** The best index is computed by the xBestIndex method of the virtual
** table module.  This routine is really just a wrapper that sets up
** the sqlite3_index_info structure that is used to communicate with
** xBestIndex.
................................................................................
** same virtual table.  The sqlite3_index_info structure is created
** and initialized on the first invocation and reused on all subsequent
** invocations.  The sqlite3_index_info structure is also used when
** code is generated to access the virtual table.  The whereInfoDelete() 
** routine takes care of freeing the sqlite3_index_info structure after
** everybody has finished with it.
*/
static void bestVirtualIndex(
  Parse *pParse,                  /* The parsing context */
  WhereClause *pWC,               /* The WHERE clause */
  struct SrcList_item *pSrc,      /* The FROM clause term to search */
  Bitmask notReady,               /* Mask of cursors that are not available */
  ExprList *pOrderBy,             /* The order by clause */
  WhereCost *pCost,               /* Lowest cost query plan */
  sqlite3_index_info **ppIdxInfo  /* Index information passed to xBestIndex */
){
  Table *pTab = pSrc->pTab;

  sqlite3_index_info *pIdxInfo;
  struct sqlite3_index_constraint *pIdxCons;

  struct sqlite3_index_constraint_usage *pUsage;
  WhereTerm *pTerm;
  int i, j;
  int nOrderBy;


  /* If the sqlite3_index_info structure has not been previously
  ** allocated and initialized, then allocate and initialize it now.

  */
  pIdxInfo = *ppIdxInfo;
  if( pIdxInfo==0 ){







































    *ppIdxInfo = pIdxInfo = allocateIndexInfo(pParse, pWC, pSrc, pOrderBy);










































  }

  /* At this point, the sqlite3_index_info structure that pIdxInfo points
  ** to will have been initialized, either during the current invocation or
  ** during some prior invocation.  Now we just have to customize the
  ** details of pIdxInfo for the current invocation and pass it to
  ** xBestIndex.
................................................................................
  */

  /* The module name must be defined. Also, by this point there must
  ** be a pointer to an sqlite3_vtab structure. Otherwise
  ** sqlite3ViewGetColumnNames() would have picked up the error. 
  */
  assert( pTab->azModuleArg && pTab->azModuleArg[0] );


  assert( pTab->pVtab );






  /* Set the aConstraint[].usable fields and initialize all 
  ** output variables to zero.
  **
  ** aConstraint[].usable is true for constraints where the right-hand
  ** side contains only references to tables to the left of the current
  ** table.  In other words, if the constraint is of the form:
................................................................................
  pIdxInfo->idxStr = 0;
  pIdxInfo->idxNum = 0;
  pIdxInfo->needToFreeIdxStr = 0;
  pIdxInfo->orderByConsumed = 0;
  /* ((double)2) In case of SQLITE_OMIT_FLOATING_POINT... */
  pIdxInfo->estimatedCost = SQLITE_BIG_DBL / ((double)2);
  nOrderBy = pIdxInfo->nOrderBy;
  if( !pOrderBy ){
    pIdxInfo->nOrderBy = 0;
  }

  if( vtabBestIndex(pParse, pTab, pIdxInfo) ){
    return;




  }


  /* The cost is not allowed to be larger than SQLITE_BIG_DBL (the
  ** inital value of lowestCost in this loop. If it is, then the
  ** (cost<lowestCost) test below will never be true.
  ** 
  ** Use "(double)2" instead of "2.0" in case OMIT_FLOATING_POINT 
  ** is defined.

  */
  if( (SQLITE_BIG_DBL/((double)2))<pIdxInfo->estimatedCost ){
    pCost->rCost = (SQLITE_BIG_DBL/((double)2));
  }else{

    pCost->rCost = pIdxInfo->estimatedCost;
  }

  pCost->plan.wsFlags = WHERE_VIRTUALTABLE;
  pCost->plan.u.pVtabIdx = pIdxInfo;
  if( pIdxInfo && pIdxInfo->orderByConsumed ){
    pCost->plan.wsFlags |= WHERE_ORDERBY;
  }


  pCost->plan.nEq = 0;
  pIdxInfo->nOrderBy = nOrderBy;







  /* Try to find a more efficient access pattern by using multiple indexes
  ** to optimize an OR expression within the WHERE clause. 
  */
  bestOrClauseIndex(pParse, pWC, pSrc, notReady, pOrderBy, pCost);
}
#endif /* SQLITE_OMIT_VIRTUALTABLE */

/*
** Find the query plan for accessing a particular table.  Write the
** best query plan and its cost into the WhereCost object supplied as the
** last parameter.
................................................................................
** then the cost is calculated in the usual way.
**
** If a NOT INDEXED clause (pSrc->notIndexed!=0) was attached to the table 
** in the SELECT statement, then no indexes are considered. However, the 
** selected plan may still take advantage of the tables built-in rowid
** index.
*/
static void bestBtreeIndex(
  Parse *pParse,              /* The parsing context */
  WhereClause *pWC,           /* The WHERE clause */
  struct SrcList_item *pSrc,  /* The FROM clause term to search */
  Bitmask notReady,           /* Mask of cursors that are not available */
  ExprList *pOrderBy,         /* The ORDER BY clause */
  WhereCost *pCost            /* Lowest cost query plan */
){
................................................................................
  int rev;                    /* True to scan in reverse order */
  int wsFlags;                /* Flags associated with pProbe */
  int nEq;                    /* Number of == or IN constraints */
  int eqTermMask;             /* Mask of valid equality operators */
  double cost;                /* Cost of using pProbe */
  double nRow;                /* Estimated number of rows in result set */
  int i;                      /* Loop counter */


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

................................................................................
    if( cost<pCost->rCost ){
      pCost->rCost = cost;
      pCost->nRow = nRow;
      pCost->plan.wsFlags = wsFlags;
    }
  }

  bestOrClauseIndex(pParse, pWC, pSrc, notReady, pOrderBy, pCost);























































  /* If the pSrc table is the right table of a LEFT JOIN then we may not
  ** use an index to satisfy IS NULL constraints on that table.  This is
  ** because columns might end up being NULL if the table does not match -
  ** a circumstance which the index cannot help us discover.  Ticket #2177.
  */
  if( (pSrc->jointype & JT_LEFT)!=0 ){
................................................................................
  pCost->plan.wsFlags |= eqTermMask;
  WHERETRACE(("best index is %s, cost=%.9g, nrow=%.9g, wsFlags=%x, nEq=%d\n",
        (pCost->plan.wsFlags & WHERE_INDEXED)!=0 ?
             pCost->plan.u.pIdx->zName : "(none)", pCost->nRow,
        pCost->rCost, pCost->plan.wsFlags, pCost->plan.nEq));
}

/*
** Find the query plan for accessing table pSrc->pTab. Write the
** best query plan and its cost into the WhereCost object supplied 
** as the last parameter. This function may calculate the cost of
** both real and virtual table scans.
*/
static void bestIndex(
  Parse *pParse,              /* The parsing context */
  WhereClause *pWC,           /* The WHERE clause */
  struct SrcList_item *pSrc,  /* The FROM clause term to search */
  Bitmask notReady,           /* Mask of cursors that are not available */
  ExprList *pOrderBy,         /* The ORDER BY clause */
  WhereCost *pCost            /* Lowest cost query plan */
){
  if( IsVirtual(pSrc->pTab) ){
    sqlite3_index_info *p = 0;
    bestVirtualIndex(pParse, pWC, pSrc, notReady, pOrderBy, pCost, &p);
    if( p->needToFreeIdxStr ){
      sqlite3_free(p->idxStr);
    }
    sqlite3DbFree(pParse->db, p);
  }else{
    bestBtreeIndex(pParse, pWC, pSrc, notReady, pOrderBy, pCost);
  }
}

/*
** Disable a term in the WHERE clause.  Except, do not disable the term
** if it controls a LEFT OUTER JOIN and it did not originate in the ON
** or USING clause of that join.
**
** Consider the term t2.z='ok' in the following queries:
................................................................................
    if( (pTerm->eOperator & (WO_ISNULL|WO_IN))==0 ){
      sqlite3VdbeAddOp2(v, OP_IsNull, regBase+j, pLevel->addrBrk);
    }
  }
  return regBase;
}




















/*
** Generate code for the start of the iLevel-th loop in the WHERE clause
** implementation described by pWInfo.
*/
static Bitmask codeOneLoopStart(
  WhereInfo *pWInfo,   /* Complete information about the WHERE clause */
  int iLevel,          /* Which level of pWInfo->a[] should be coded */
................................................................................
  Parse *pParse;                  /* Parsing context */
  Vdbe *v;                        /* The prepared stmt under constructions */
  struct SrcList_item *pTabItem;  /* FROM clause term being coded */
  int addrBrk;                    /* Jump here to break out of the loop */
  int addrCont;                   /* Jump here to continue with next cycle */
  int regRowSet;       /* Write rowids to this RowSet if non-negative */
  int codeRowSetEarly; /* True if index fully constrains the search */

  /* Sometimes, this function is required to generate code to do 
  ** something with the rowid of each row scanned. Specifically:
  **
  **   1) If pWInfo->regRowSet is non-zero, then the rowid must be inserted
  **      into the RowSet object stored in register pWInfo->regRowSet.
  **
  **   2) If pWInfo->regRowHash is non-zero, then the rowid must be inserted
  **      into the RowHash object stored in register pWInfo->regRowHash.
  **
  ** Extracting a rowid value from a VDBE cursor is not always a cheap
  ** operation, especially if the rowid is being extracted from an index
  ** cursor. If the rowid value is available as a by-product of the code
  ** generated to create the top of the scan loop, then it can be reused
  ** for either of the two purposes enumerated above without extracting
  ** it from a cursor. The following two variables are used to communicate
  ** the availability of the rowid value to the C-code at the end of this
  ** function that generates the rowid-handling VDBE code.
  */
  int iRowidReg = 0;              /* Rowid is stored in this register */
  int iReleaseReg = 0;            /* Temp register to free before returning */

  pParse = pWInfo->pParse;
  v = pParse->pVdbe;
  pWC = pWInfo->pWC;
  pLevel = &pWInfo->a[iLevel];
  pTabItem = &pWInfo->pTabList->a[pLevel->iFrom];
  iCur = pTabItem->iCursor;
  bRev = (pLevel->plan.wsFlags & WHERE_REVERSE)!=0;
  omitTable = (pLevel->plan.wsFlags & WHERE_IDX_ONLY)!=0 
           && (wctrlFlags & WHERE_FILL_ROWHASH)==0;
  regRowSet = pWInfo->regRowSet;
  codeRowSetEarly = 0;

  /* Create labels for the "break" and "continue" instructions
  ** for the current loop.  Jump to addrBrk to break out of a loop.
  ** Jump to cont to go immediately to the next iteration of the
  ** loop.
................................................................................
        int iTerm = aConstraint[j].iTermOffset;
        disableTerm(pLevel, &pWC->a[iTerm]);
      }
    }
    pLevel->op = OP_VNext;
    pLevel->p1 = iCur;
    pLevel->p2 = sqlite3VdbeCurrentAddr(v);





    sqlite3ReleaseTempRange(pParse, iReg, nConstraint+2);
  }else
#endif /* SQLITE_OMIT_VIRTUALTABLE */

  if( pLevel->plan.wsFlags & WHERE_ROWID_EQ ){
    /* Case 1:  We can directly reference a single row using an
    **          equality comparison against the ROWID field.  Or
    **          we reference multiple rows using a "rowid IN (...)"
    **          construct.
    */

    iReleaseReg = sqlite3GetTempReg(pParse);
    pTerm = findTerm(pWC, iCur, -1, notReady, WO_EQ|WO_IN, 0);
    assert( pTerm!=0 );
    assert( pTerm->pExpr!=0 );
    assert( pTerm->leftCursor==iCur );
    assert( omitTable==0 );
    iRowidReg = codeEqualityTerm(pParse, pTerm, pLevel, iReleaseReg);
    addrNxt = pLevel->addrNxt;
    sqlite3VdbeAddOp2(v, OP_MustBeInt, iRowidReg, addrNxt);
    sqlite3VdbeAddOp3(v, OP_NotExists, iCur, addrNxt, iRowidReg);





    VdbeComment((v, "pk"));
    pLevel->op = OP_Noop;
  }else if( pLevel->plan.wsFlags & WHERE_ROWID_RANGE ){
    /* Case 2:  We have an inequality comparison against the ROWID field.
    */
    int testOp = OP_Noop;
    int start;
................................................................................
      disableTerm(pLevel, pEnd);
    }
    start = sqlite3VdbeCurrentAddr(v);
    pLevel->op = bRev ? OP_Prev : OP_Next;
    pLevel->p1 = iCur;
    pLevel->p2 = start;
    pLevel->p5 = (pStart==0 && pEnd==0) ?1:0;

    if( testOp!=OP_Noop ){
      iRowidReg = iReleaseReg = sqlite3GetTempReg(pParse);
      sqlite3VdbeAddOp2(v, OP_Rowid, iCur, iRowidReg);

      sqlite3VdbeAddOp3(v, testOp, memEndValue, addrBrk, iRowidReg);
      sqlite3VdbeChangeP5(v, SQLITE_AFF_NUMERIC | SQLITE_JUMPIFNULL);





    }
  }else if( pLevel->plan.wsFlags & (WHERE_COLUMN_RANGE|WHERE_COLUMN_EQ) ){
    /* Case 3: A scan using an index.
    **
    **         The WHERE clause may contain zero or more equality 
    **         terms ("==" or "IN" operators) that refer to the N
    **         left-most columns of the index. It may also contain
................................................................................
    r1 = sqlite3GetTempReg(pParse);
    testcase( pLevel->plan.wsFlags & WHERE_BTM_LIMIT );
    testcase( pLevel->plan.wsFlags & WHERE_TOP_LIMIT );
    if( pLevel->plan.wsFlags & (WHERE_BTM_LIMIT|WHERE_TOP_LIMIT) ){
      sqlite3VdbeAddOp3(v, OP_Column, iIdxCur, nEq, r1);
      sqlite3VdbeAddOp2(v, OP_IsNull, r1, addrCont);
    }
    sqlite3ReleaseTempReg(pParse, r1);

    /* Seek the table cursor, if required */
    disableTerm(pLevel, pRangeStart);
    disableTerm(pLevel, pRangeEnd);

    if( !omitTable ){
      iRowidReg = iReleaseReg = sqlite3GetTempReg(pParse);
      sqlite3VdbeAddOp2(v, OP_IdxRowid, iIdxCur, iRowidReg);



      sqlite3VdbeAddOp2(v, OP_Seek, iCur, iRowidReg);  /* Deferred seek */
    }



    /* Record the instruction used to terminate the loop. Disable 
    ** WHERE clause terms made redundant by the index range scan.
    */
    pLevel->op = bRev ? OP_Prev : OP_Next;
    pLevel->p1 = iIdxCur;
  }else
................................................................................
    **   CREATE INDEX i1 ON t1(a);
    **   CREATE INDEX i2 ON t1(b);
    **   CREATE INDEX i3 ON t1(c);
    **
    **   SELECT * FROM t1 WHERE a=5 OR b=7 OR (c=11 AND d=13)
    **
    ** In the example, there are three indexed terms connected by OR.
    ** The top of the loop looks like this:
    **
    **          Null       1                # Zero the row-hash in reg 1
    **
    ** Then, for each indexed term, the following. The arguments to
    ** RowHash are such that the rowid of the current row is inserted
    ** into the row-hash. If it is already present, control skips the
    ** Gosub opcode and jumps straight to the code generated by WhereEnd().
    **
    **        sqlite3WhereBegin(<term>)
    **          RowHash                     # Insert rowid into rowhash
    **          Gosub      2 A




    **        sqlite3WhereEnd()
    **

    ** Following the above, code to terminate the loop. Label A, the target
    ** of the Gosub above, jumps to the instruction right after the Goto.
    **

    **          Null       1                # Zero the row-hash in reg 1
    **          Goto       B                # The loop is finished.
    **
    **       A: <loop body>                 # Return data, whatever.
    **
    **          Return     2                # Jump back to the Gosub
    **
    **       B: <after the loop>
    **
    */


    const int f = WHERE_OMIT_OPEN | WHERE_OMIT_CLOSE | WHERE_FILL_ROWHASH;

    WhereClause *pOrWc;    /* The OR-clause broken out into subterms */
    WhereTerm *pFinal;     /* Final subterm within the OR-clause. */
    SrcList oneTab;        /* Shortened table list */

    int regReturn = ++pParse->nMem;           /* Register used with OP_Gosub */
    int regRowhash = ++pParse->nMem;          /* Register for RowHash object */
    int iLoopBody = sqlite3VdbeMakeLabel(v);  /* Start of loop body */
    int iRetInit;                             /* Address of regReturn init */
    int ii;
   
    pTerm = pLevel->plan.u.pTerm;
    assert( pTerm!=0 );
    assert( pTerm->eOperator==WO_OR );
    assert( (pTerm->wtFlags & TERM_ORINFO)!=0 );
    pOrWc = &pTerm->u.pOrInfo->wc;
    pFinal = &pOrWc->a[pOrWc->nTerm-1];

    /* Set up a SrcList containing just the table being scanned by this loop. */
    oneTab.nSrc = 1;
    oneTab.nAlloc = 1;
    oneTab.a[0] = *pTabItem;

    /* Initialize the row-hash register to contain NULL. An SQL NULL is 
    ** equivalent to an empty row-hash. 
    **
    ** Also initialize regReturn to contain the address of the instruction 
    ** immediately following the OP_Return at the bottom of the loop. This
    ** is required in a few obscure LEFT JOIN cases where control jumps
    ** over the top of the loop into the body of it. In this case the 
    ** correct response for the end-of-loop code (the OP_Return) is to 
    ** fall through to the next instruction, just as an OP_Next does if
    ** called on an uninitialized cursor.
    */
    sqlite3VdbeAddOp2(v, OP_Null, 0, regRowhash);
    iRetInit = sqlite3VdbeAddOp2(v, OP_Integer, 0, regReturn);

    /* iReleaseReg = iRowidReg = sqlite3GetTempReg(pParse); */
    for(ii=0; ii<pOrWc->nTerm; ii++){
      WhereTerm *pOrTerm = &pOrWc->a[ii];
      if( pOrTerm->leftCursor==iCur || pOrTerm->eOperator==WO_AND ){
        WhereInfo *pSubWInfo;          /* Info for single OR-term scan */

        /* Loop through table entries that match term pOrTerm. */
        pSubWInfo = sqlite3WhereBegin(
            pParse, &oneTab, pOrTerm->pExpr, 0, f, regRowhash);
        if( pSubWInfo ){
          int iSet = ((ii==pOrWc->nTerm-1)?-1:ii);
          /* The call to sqlite3WhereBegin has coded an OP_RowHash 
          ** at instruction iRowHash. Set P2 (the jump target) of this
          ** instruction to jump past the OP_Gosub coded below. This way,
          ** if the rowid is already in the hash-table, the body of the
          ** loop is not executed.
          */
          int iRowHash = pSubWInfo->iRowidHandler;
          sqlite3VdbeChangeP2(v, iRowHash, sqlite3VdbeCurrentAddr(v) + 1);
          sqlite3VdbeChangeP4(v, iRowHash, (char *)iSet, P4_INT32);
          sqlite3VdbeAddOp2(v, OP_Gosub, regReturn, iLoopBody);

          /* Finish the loop through table entries that match term pOrTerm. */
          sqlite3WhereEnd(pSubWInfo);
        }
      }
    }
    sqlite3VdbeChangeP1(v, iRetInit, sqlite3VdbeCurrentAddr(v));
    sqlite3VdbeAddOp2(v, OP_Null, 0, regRowhash);
    sqlite3VdbeAddOp2(v, OP_Goto, 0, pLevel->addrBrk);
    sqlite3VdbeResolveLabel(v, iLoopBody);

    pLevel->op = OP_Return;
    pLevel->p1 = regReturn;
    disableTerm(pLevel, pTerm);
  }else
#endif /* SQLITE_OMIT_OR_OPTIMIZATION */

  {
    /* Case 5:  There is no usable index.  We must do a complete
    **          scan of the entire table.
................................................................................
    static const u8 aStart[] = { OP_Rewind, OP_Last };
    assert( bRev==0 || bRev==1 );
    assert( omitTable==0 );
    pLevel->op = aStep[bRev];
    pLevel->p1 = iCur;
    pLevel->p2 = 1 + sqlite3VdbeAddOp2(v, aStart[bRev], iCur, addrBrk);
    pLevel->p5 = SQLITE_STMTSTATUS_FULLSCAN_STEP;

  }
  notReady &= ~getMask(pWC->pMaskSet, iCur);

  /* Insert code to test every subexpression that can be completely
  ** computed using the current set of tables.
  */
  k = 0;
................................................................................
      if( (pTerm->prereqAll & notReady)!=0 ) continue;
      assert( pTerm->pExpr );
      sqlite3ExprIfFalse(pParse, pTerm->pExpr, addrCont, SQLITE_JUMPIFNULL);
      pTerm->wtFlags |= TERM_CODED;
    }
  }

  /* Do the special rowid handling now. */
  if( regRowSet ){
    assert( regRowSet>0 );
    if( iRowidReg==0 ){
      /* The rowid was not available as a side-effect of the code 
      ** genenerated above. So extract it from the cursor now.
      */

      assert( iReleaseReg==0 );
      iReleaseReg = iRowidReg = sqlite3GetTempReg(pParse);
#ifndef SQLITE_OMIT_VIRTUALTABLE
      if( (pLevel->plan.wsFlags & WHERE_VIRTUALTABLE)!=0 ){
        sqlite3VdbeAddOp2(v, OP_VRowid, iCur, iRowidReg);
      }else
#endif
      {
        sqlite3VdbeAddOp2(v, OP_Rowid, iCur, iRowidReg);
      }
    }
    
    pWInfo->iRowidHandler = sqlite3VdbeCurrentAddr(v);
    if( pWInfo->wctrlFlags&WHERE_FILL_ROWSET ){
      sqlite3VdbeAddOp2(v, OP_RowSetAdd, regRowSet, iRowidReg);

    }else{
      assert( pWInfo->wctrlFlags&WHERE_FILL_ROWHASH );
      sqlite3VdbeAddOp3(v, OP_RowHash, regRowSet, 0, iRowidReg);
    }
  }
  sqlite3ReleaseTempReg(pParse, iReleaseReg);

  return notReady;
}

#if defined(SQLITE_TEST)
/*
** The following variable holds a text description of query plan generated
................................................................................
*/
static void whereInfoFree(sqlite3 *db, WhereInfo *pWInfo){
  if( pWInfo ){
    int i;
    for(i=0; i<pWInfo->nLevel; i++){
      sqlite3_index_info *pInfo = pWInfo->a[i].pIdxInfo;
      if( pInfo ){
        /* assert( pInfo->needToFreeIdxStr==0 || db->mallocFailed ); */
        if( pInfo->needToFreeIdxStr ){
          sqlite3_free(pInfo->idxStr);
        }
        sqlite3DbFree(db, pInfo);
      }
    }
    whereClauseClear(pWInfo->pWC);
................................................................................
  if( db->mallocFailed ){
    goto whereBeginError;
  }
  pWInfo->nLevel = pTabList->nSrc;
  pWInfo->pParse = pParse;
  pWInfo->pTabList = pTabList;
  pWInfo->iBreak = sqlite3VdbeMakeLabel(v);
  pWInfo->regRowSet = regRowSet;
  pWInfo->pWC = pWC = (WhereClause *)&((u8 *)pWInfo)[nByteWInfo];
  pWInfo->wctrlFlags = wctrlFlags;
  pMaskSet = (WhereMaskSet*)&pWC[1];
  assert( regRowSet==0 || (wctrlFlags&(WHERE_FILL_ROWSET|WHERE_FILL_ROWHASH)) );

  /* Split the WHERE clause into separate subexpressions where each
  ** subexpression is separated by an AND operator.
  */
  initMaskSet(pMaskSet);
  whereClauseInit(pWC, pParse, pMaskSet);
  sqlite3ExprCodeConstants(pParse, pWhere);
................................................................................
    int bestJ = 0;              /* The value of j */
    Bitmask m;                  /* Bitmask value for j or bestJ */
    int once = 0;               /* True when first table is seen */

    memset(&bestPlan, 0, sizeof(bestPlan));
    bestPlan.rCost = SQLITE_BIG_DBL;
    for(j=iFrom, pTabItem=&pTabList->a[j]; j<pTabList->nSrc; j++, pTabItem++){
      int doNotReorder;    /* True if this table should not be reordered */
      WhereCost sCost;     /* Cost information from best[Virtual]Index() */
      ExprList *pOrderBy;  /* ORDER BY clause for index to optimize */

      doNotReorder =  (pTabItem->jointype & (JT_LEFT|JT_CROSS))!=0;
      if( once && doNotReorder ) break;
      m = getMask(pMaskSet, pTabItem->iCursor);
      if( (m & notReady)==0 ){
        if( j==iFrom ) iFrom++;
        continue;
      }
      pOrderBy = ((i==0 && ppOrderBy )?*ppOrderBy:0);

      assert( pTabItem->pTab );
#ifndef SQLITE_OMIT_VIRTUALTABLE
      if( IsVirtual(pTabItem->pTab) ){

        sqlite3_index_info **pp = &pWInfo->a[j].pIdxInfo;
        bestVirtualIndex(pParse, pWC, pTabItem, notReady, pOrderBy, &sCost, pp);

















      }else 
#endif
      {
        bestBtreeIndex(pParse, pWC, pTabItem, notReady, pOrderBy, &sCost);

      }
      if( once==0 || sCost.rCost<bestPlan.rCost ){
        once = 1;
        bestPlan = sCost;
        bestJ = j;
      }
      if( doNotReorder ) break;
................................................................................
        ** guaranteed to find the index specified in the INDEXED BY clause
        ** if it find an index at all. */
        assert( bestPlan.plan.u.pIdx==pIdx );
      }
    }
  }
  WHERETRACE(("*** Optimizer Finished ***\n"));
  if( pParse->nErr || db->mallocFailed ){
    goto whereBeginError;
  }

  /* If the total query only selects a single row, then the ORDER BY
  ** clause is irrelevant.
  */
  if( (andFlags & WHERE_UNIQUE)!=0 && ppOrderBy ){

Changes to test/make-where7.tcl.

99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
  if {[info exists seen($w)]} {
    incr i -1
    continue
  }
  set seen($w) 1
  set result [lsort -int [array names r]]
  puts "do_test where7-2.$i.1 \173"
  puts "  count_steps \173"
  puts "     SELECT a FROM t2"
  set wc [join $w "\n         OR "]
  puts "      WHERE $wc"
  puts "      ORDER BY a"
  puts "  \175"
  puts "\175 {$result scan 0 sort 0}"
  puts "do_test where7-2.$i.2 \173"
  puts "  count_steps \173"
  puts "     SELECT a FROM t3"
  set wc [join $w "\n         OR "]
  puts "      WHERE $wc"
  puts "      ORDER BY a"
  puts "  \175"
  puts "\175 {$result scan 0 sort 0}"
}
puts "finish_test"







|



<



|



<




99
100
101
102
103
104
105
106
107
108
109

110
111
112
113
114
115
116

117
118
119
120
  if {[info exists seen($w)]} {
    incr i -1
    continue
  }
  set seen($w) 1
  set result [lsort -int [array names r]]
  puts "do_test where7-2.$i.1 \173"
  puts "  count_steps_sort \173"
  puts "     SELECT a FROM t2"
  set wc [join $w "\n         OR "]
  puts "      WHERE $wc"

  puts "  \175"
  puts "\175 {$result scan 0 sort 0}"
  puts "do_test where7-2.$i.2 \173"
  puts "  count_steps_sort \173"
  puts "     SELECT a FROM t3"
  set wc [join $w "\n         OR "]
  puts "      WHERE $wc"

  puts "  \175"
  puts "\175 {$result scan 0 sort 0}"
}
puts "finish_test"

Added test/rowhash.test.











































































































>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
# 2009 April 17
#
# The author disclaims copyright to this source code.  In place of
# a legal notice, here is a blessing:
#
#    May you do good and not evil.
#    May you find forgiveness for yourself and forgive others.
#    May you share freely, never taking more than you give.
#
#***********************************************************************
#
# This file implements regression tests for SQLite library.  The
# focus of this file is the code in rowhash.c.
#
# $Id: rowhash.test,v 1.1 2009/04/21 09:02:47 danielk1977 Exp $

set testdir [file dirname $argv0]
source $testdir/tester.tcl

do_test rowhash-1.1 {
  execsql {
    CREATE TABLE t1(id INTEGER PRIMARY KEY, a, b, c);
    CREATE INDEX i1 ON t1(a);
    CREATE INDEX i2 ON t1(b);
    CREATE INDEX i3 ON t1(c);
  }
} {}

proc do_keyset_test {name lKey} {
  db transaction {
    execsql { DELETE FROM t1 }
    foreach key $lKey {
      execsql { INSERT INTO t1 VALUES($key, 'a', 'b', 'c') }
    }
  }
  do_test $name {
    lsort -integer [execsql {
      SELECT id FROM t1 WHERE a = 'a' OR b = 'b' OR c = 'c';
    }]
  } [lsort -integer $lKey]
}

do_keyset_test rowhash-2.1 {1 2 3}
do_keyset_test rowhash-2.2 {0 1 2 3}
do_keyset_test rowhash-2.3 {62 125 188}
for {set i 4} {$i < 10} {incr i} {
  for {set j 0} {$j < 5000} {incr j} {
    lappend L [expr int(rand()*10000000000)]
  }
  do_keyset_test rowhash-2.$i $L
}

finish_test

Added test/vtabD.test.













































































































































>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
# 2009 April 14
#
# The author disclaims copyright to this source code.  In place of
# a legal notice, here is a blessing:
#
#    May you do good and not evil.
#    May you find forgiveness for yourself and forgive others.
#    May you share freely, never taking more than you give.
#
#***********************************************************************
# This file implements regression tests for SQLite library.  The
# focus of this file is creating and dropping virtual tables.
#
# $Id: vtabD.test,v 1.1 2009/04/21 09:02:47 danielk1977 Exp $

set testdir [file dirname $argv0]
source $testdir/tester.tcl

ifcapable !vtab||!schema_pragmas { finish_test ; return }

# Register the echo module
register_echo_module [sqlite3_connection_pointer db]

do_test vtabD-1.1 {
  execsql {
    CREATE TABLE t1(a, b);
    CREATE INDEX i1 ON t1(a);
    CREATE INDEX i2 ON t1(b);
    CREATE VIRTUAL TABLE tv1 USING echo(t1);
  }
} {}
do_test vtabD-1.2 {
  execsql BEGIN
  for {set i 0} {$i < 100000} {incr i} {
    execsql { INSERT INTO t1 VALUES($i, $i*$i) }
  }
  execsql COMMIT
} {}
do_test vtabD-1.3 {
  execsql { SELECT * FROM tv1 WHERE a = 1 OR b = 4 }
} {1 1 2 4}
do_test vtabD-1.4 {
  execsql { SELECT * FROM tv1 WHERE a = 1 OR b = 1 }
} {1 1}
do_test vtabD-1.5 {
  execsql { SELECT * FROM tv1 WHERE (a > 0 AND a < 5) OR (b > 15 AND b < 65) }
} {1 1 2 4 3 9 4 16 5 25 6 36 7 49 8 64}

do_test vtabD-1.6 {
  execsql { SELECT * FROM tv1 WHERE a < 500 OR b = 810000 }
} [execsql {
  SELECT * FROM t1 WHERE a < 500
    UNION ALL
  SELECT * FROM t1 WHERE b = 810000 AND NOT (a < 500)
}]

do_test vtabD-1.7 {
  execsql { SELECT * FROM tv1 WHERE a < 90000 OR b = 8100000000 }
} [execsql {
  SELECT * FROM t1 WHERE a < 90000
    UNION ALL
  SELECT * FROM t1 WHERE b = 8100000000 AND NOT (a < 90000)
}]

do_test vtabD-1.8 {
  execsql { SELECT * FROM tv1 WHERE a = 90001 OR b = 810000 }
} {90001 8100180001 900 810000}

finish_test

Changes to test/where7.test.

more than 10,000 changes

Changes to test/where8.test.

8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
..
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
...
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
...
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
#    May you share freely, never taking more than you give.
#
#***********************************************************************
# This file implements regression tests for SQLite library. The focus
# is testing of where.c. More specifically, the focus is the optimization
# of WHERE clauses that feature the OR operator.
#
# $Id: where8.test,v 1.5 2008/12/30 16:13:05 danielk1977 Exp $

set testdir [file dirname $argv0]
source $testdir/tester.tcl

# Test organization:
#
#   where8-1.*: Tests to demonstrate simple cases work with a single table
................................................................................

do_test where8-1.2 { 
  execsql_status2 { SELECT c FROM t1 WHERE a = 1 OR b = 'nine' }
} {I IX 0 0 6}

do_test where8-1.3 { 
  execsql_status2 { SELECT c FROM t1 WHERE a > 8 OR b = 'two' }
} {II IX X 0 0 6}

do_test where8-1.4 { 
  execsql_status2 { SELECT c FROM t1 WHERE a > 8 OR b GLOB 't*' }
} {II III IX X 0 0 9}

do_test where8-1.5 { 
  execsql_status2 { SELECT c FROM t1 WHERE a > 8 OR b GLOB 'f*' }
} {IV V IX X 0 0 9}

do_test where8-1.6 { 
  execsql_status { SELECT c FROM t1 WHERE a = 1 OR b = 'three' ORDER BY rowid }
} {I III 0 0}

do_test where8-1.7 { 
  execsql_status { SELECT c FROM t1 WHERE a = 1 OR b = 'three' ORDER BY a }
} {I III 0 1}

do_test where8-1.8 {
  # 18 searches. 9 on the index cursor and 9 on the table cursor.
  execsql_status2 { SELECT c FROM t1 WHERE a > 1 AND c LIKE 'I%' }
} {II III IV IX 0 0 18}

do_test where8-1.9 {
  execsql_status2 { SELECT c FROM t1 WHERE a >= 9 OR b <= 'eight' }
} {VIII IX X 0 0 6}

do_test where8-1.10 {
  execsql_status2 { 
    SELECT c FROM t1 WHERE (a >= 9 AND c != 'X') OR b <= 'eight' 
  }
} {VIII IX 0 0 7}

do_test where8-1.11 {
  execsql_status2 { 
    SELECT c FROM t1 WHERE (a >= 4 AND a <= 6) OR b = 'nine' 
  }
} {IV V VI IX 0 0 10}

................................................................................

do_test where8-1.13 {
  execsql_status2 {
    SELECT c FROM t1
    WHERE a = 2 OR b = 'three' OR a = 4 OR b = 'five' OR a = 6
    ORDER BY rowid
  }
} {II III IV V VI 0 0 15}
do_test where8-1.14 {
  execsql_status2 {
    SELECT c FROM t1
    WHERE 
      a = 2 OR b = 'three' OR a = 4 OR b = 'five' OR a = 6 OR
      b = 'seven' OR a = 8 OR b = 'nine' OR a = 10
    ORDER BY rowid
  }
} {II III IV V VI VII VIII IX X 0 0 26}

do_test where8-1.15 {
  execsql_status2 {
    SELECT c FROM t1 WHERE 
      a BETWEEN 2 AND 4 OR b = 'nine'
    ORDER BY rowid
  }
} {II III IV IX 0 0 10}



#--------------------------------------------------------------------------
# Tests where8-2.*: Virtual tables
# 

if 0 {
................................................................................
do_test where8-3.8 {
  execsql_status {
    SELECT a, d 
    FROM t1, t2 
    WHERE (a = 2 OR b = 'three') AND (d = a OR e = 'sixteen')
    ORDER BY t1.rowid
  }
} {2 2 2 4 3 3 3 4 0 0}

do_test where8-3.9 {
  # The "OR c = 'IX'" term forces a linear scan.
  execsql_status {
    SELECT a, d 
    FROM t1, t2 
    WHERE (a = 2 OR b = 'three' OR c = 'IX') AND (d = a OR e = 'sixteen')
    ORDER BY t1.rowid
  }
} {2 2 2 4 3 3 3 4 9 4 9 9 9 0}

do_test where8-3.10 {
  execsql_status {
    SELECT d FROM t2 WHERE e IS NULL OR e = 'four'
  }
} {1 2 3 5 10 0 0}

do_test where8-3.11 {
  execsql_status {
    SELECT a, d FROM t1, t2 WHERE (a=d OR b=e) AND a<5 ORDER BY a
  }
} {1 1 2 2 3 3 4 2 4 4 0 0}
do_test where8-3.12 {







|







 







|



|



|



|












|





|







 







|








|







|
<







 







|









|





|







8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
..
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
...
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140

141
142
143
144
145
146
147
...
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
#    May you share freely, never taking more than you give.
#
#***********************************************************************
# This file implements regression tests for SQLite library. The focus
# is testing of where.c. More specifically, the focus is the optimization
# of WHERE clauses that feature the OR operator.
#
# $Id: where8.test,v 1.6 2009/04/21 09:02:47 danielk1977 Exp $

set testdir [file dirname $argv0]
source $testdir/tester.tcl

# Test organization:
#
#   where8-1.*: Tests to demonstrate simple cases work with a single table
................................................................................

do_test where8-1.2 { 
  execsql_status2 { SELECT c FROM t1 WHERE a = 1 OR b = 'nine' }
} {I IX 0 0 6}

do_test where8-1.3 { 
  execsql_status2 { SELECT c FROM t1 WHERE a > 8 OR b = 'two' }
} {IX X II 0 0 6}

do_test where8-1.4 { 
  execsql_status2 { SELECT c FROM t1 WHERE a > 8 OR b GLOB 't*' }
} {IX X III II 0 0 9}

do_test where8-1.5 { 
  execsql_status2 { SELECT c FROM t1 WHERE a > 8 OR b GLOB 'f*' }
} {IX X V IV 0 0 9}

do_test where8-1.6 { 
  execsql_status { SELECT c FROM t1 WHERE a = 1 OR b = 'three' ORDER BY rowid }
} {I III 0 1}

do_test where8-1.7 { 
  execsql_status { SELECT c FROM t1 WHERE a = 1 OR b = 'three' ORDER BY a }
} {I III 0 1}

do_test where8-1.8 {
  # 18 searches. 9 on the index cursor and 9 on the table cursor.
  execsql_status2 { SELECT c FROM t1 WHERE a > 1 AND c LIKE 'I%' }
} {II III IV IX 0 0 18}

do_test where8-1.9 {
  execsql_status2 { SELECT c FROM t1 WHERE a >= 9 OR b <= 'eight' }
} {IX X VIII 0 0 6}

do_test where8-1.10 {
  execsql_status2 { 
    SELECT c FROM t1 WHERE (a >= 9 AND c != 'X') OR b <= 'eight' 
  }
} {IX VIII 0 0 6}

do_test where8-1.11 {
  execsql_status2 { 
    SELECT c FROM t1 WHERE (a >= 4 AND a <= 6) OR b = 'nine' 
  }
} {IV V VI IX 0 0 10}

................................................................................

do_test where8-1.13 {
  execsql_status2 {
    SELECT c FROM t1
    WHERE a = 2 OR b = 'three' OR a = 4 OR b = 'five' OR a = 6
    ORDER BY rowid
  }
} {II III IV V VI 0 1 18}
do_test where8-1.14 {
  execsql_status2 {
    SELECT c FROM t1
    WHERE 
      a = 2 OR b = 'three' OR a = 4 OR b = 'five' OR a = 6 OR
      b = 'seven' OR a = 8 OR b = 'nine' OR a = 10
    ORDER BY rowid
  }
} {II III IV V VI VII VIII IX X 0 1 33}

do_test where8-1.15 {
  execsql_status2 {
    SELECT c FROM t1 WHERE 
      a BETWEEN 2 AND 4 OR b = 'nine'
    ORDER BY rowid
  }
} {II III IV IX 0 1 12}



#--------------------------------------------------------------------------
# Tests where8-2.*: Virtual tables
# 

if 0 {
................................................................................
do_test where8-3.8 {
  execsql_status {
    SELECT a, d 
    FROM t1, t2 
    WHERE (a = 2 OR b = 'three') AND (d = a OR e = 'sixteen')
    ORDER BY t1.rowid
  }
} {2 2 2 4 3 3 3 4 0 1}

do_test where8-3.9 {
  # The "OR c = 'IX'" term forces a linear scan.
  execsql_status {
    SELECT a, d 
    FROM t1, t2 
    WHERE (a = 2 OR b = 'three' OR c = 'IX') AND (d = a OR e = 'sixteen')
    ORDER BY t1.rowid
  }
} {2 2 2 4 3 3 3 4 9 9 9 4 9 0}

do_test where8-3.10 {
  execsql_status {
    SELECT d FROM t2 WHERE e IS NULL OR e = 'four'
  }
} {1 3 5 10 2 0 0}

do_test where8-3.11 {
  execsql_status {
    SELECT a, d FROM t1, t2 WHERE (a=d OR b=e) AND a<5 ORDER BY a
  }
} {1 1 2 2 3 3 4 2 4 4 0 0}
do_test where8-3.12 {

Changes to test/where8m.test.

8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
..
32
33
34
35
36
37
38

















39
40
41
#    May you share freely, never taking more than you give.
#
#***********************************************************************
# This file implements regression tests for SQLite library. The focus
# is testing of where.c. More specifically, the focus is the optimization
# of WHERE clauses that feature the OR operator.
#
# $Id: where8m.test,v 1.1 2008/12/30 12:00:12 danielk1977 Exp $

set testdir [file dirname $argv0]
source $testdir/tester.tcl

source $testdir/malloc_common.tcl

do_malloc_test where8m-1 -sqlprep {
................................................................................

  SELECT c FROM t1 WHERE
    a = 1 OR a = 2 OR a = 3 OR a = 4 OR a = 5 OR a = 6;

  SELECT c FROM t1 WHERE
    a BETWEEN 1 AND 3  AND b < 5 AND b > 2 AND c = 4;
}


















finish_test








|







 







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



8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
..
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#    May you share freely, never taking more than you give.
#
#***********************************************************************
# This file implements regression tests for SQLite library. The focus
# is testing of where.c. More specifically, the focus is the optimization
# of WHERE clauses that feature the OR operator.
#
# $Id: where8m.test,v 1.2 2009/04/21 09:02:47 danielk1977 Exp $

set testdir [file dirname $argv0]
source $testdir/tester.tcl

source $testdir/malloc_common.tcl

do_malloc_test where8m-1 -sqlprep {
................................................................................

  SELECT c FROM t1 WHERE
    a = 1 OR a = 2 OR a = 3 OR a = 4 OR a = 5 OR a = 6;

  SELECT c FROM t1 WHERE
    a BETWEEN 1 AND 3  AND b < 5 AND b > 2 AND c = 4;
}

do_malloc_test where8m-2 -tclprep {
  db eval {
    BEGIN;
    CREATE TABLE t1(a, b, c);
    CREATE INDEX i1 ON t1(a);
    CREATE INDEX i2 ON t1(b);
  }
  for {set i 0} {$i < 1000} {incr i} {
    set ii [expr $i*$i]
    set iii [expr $i*$i]
    db eval { INSERT INTO t1 VALUES($i, $ii, $iii) }
  }
  db eval COMMIT
} -sqlbody {
  SELECT count(*) FROM t1 WHERE a BETWEEN 5 AND 995 OR b BETWEEN 5 AND 900000;
}

finish_test

Changes to test/where9.test.

7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
...
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
...
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
...
244
245
246
247
248
249
250
251
252






253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
...
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
...
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
#    May you find forgiveness for yourself and forgive others.
#    May you share freely, never taking more than you give.
#
#***********************************************************************
# This file implements regression tests for SQLite library.  The
# focus of this file is testing the multi-index OR clause optimizer.
#
# $Id: where9.test,v 1.7 2009/02/24 10:01:52 danielk1977 Exp $

set testdir [file dirname $argv0]
source $testdir/tester.tcl

ifcapable !or_opt {
  finish_test
  return
................................................................................
  count_steps {
    SELECT a FROM t1
     WHERE b IS NULL
        OR c IS NULL
        OR d IS NULL
    ORDER BY a
  }
} {90 91 92 96 97 99 scan 0 sort 0}
do_test where9-1.2.2 {
  count_steps {
    SELECT a FROM t1
     WHERE +b IS NULL
        OR c IS NULL
        OR d IS NULL
    ORDER BY a
................................................................................
  count_steps {
    SELECT a FROM t1
     WHERE (b IS NULL AND c NOT NULL AND d NOT NULL)
        OR (b NOT NULL AND c IS NULL AND d NOT NULL)
        OR (b NOT NULL AND c NOT NULL AND d IS NULL)
    ORDER BY a
  }
} {90 91 92 97 scan 0 sort 0}
do_test where9-1.3.2 {
  count_steps {
    SELECT a FROM t4
     WHERE (b IS NULL AND c NOT NULL AND d NOT NULL)
        OR (b NOT NULL AND c IS NULL AND d NOT NULL)
        OR (b NOT NULL AND c NOT NULL AND d IS NULL)
    ORDER BY a
................................................................................

do_test where9-1.4 {
  count_steps {
    SELECT a FROM t1
     WHERE (b>=950 AND b<=1010) OR (b IS NULL AND c NOT NULL)
    ORDER BY a
  }
} {87 88 89 90 91 scan 0 sort 0}
do_test where9-1.5 {






  count_steps {
    SELECT a FROM t1
     WHERE a=83
        OR b=913
        OR c=28028
        OR (d>=82 AND d<83)
        OR (e>2802 AND e<2803) 
        OR f='fghijklmn'
        OR g='hgfedcb'
    ORDER BY a
  }
} {5 31 57 82 83 84 85 86 87 scan 0 sort 0}
do_test where9-1.6 {
  count_steps {
    SELECT a FROM t1
     WHERE b=1012
        OR (d IS NULL AND e IS NOT NULL)
  }
} {92 scan 0 sort 0}
................................................................................
do_test where9-2.5 {
  count_steps {
    SELECT t1.a, coalesce(t2.a,9999)
      FROM t1 LEFT JOIN t2 ON (t1.c=t2.c AND t1.d=t2.d) OR (t1.f)=t2.f
     WHERE t1.a=80 OR t1.b=880 OR (t1.c=27027 AND round(t1.d)==80)
    ORDER BY 1
  }
} {80 2 80 28 80 54 80 80 scan 0 sort 0}
do_test where9-2.6 {
  count_steps {
    SELECT t1.a, coalesce(t2.a,9999)
      FROM t1 LEFT JOIN t2 ON (t1.c+1=t2.c AND t1.d=t2.d) OR (t1.f||'x')=t2.f
     WHERE t1.a=80 OR t1.b=880 OR (t1.c=27027 AND round(t1.d)==80)
    ORDER BY 1
  }
} {80 9999 scan 0 sort 0}
do_test where9-2.7 {
  count_steps {
    SELECT t3.x, t1.a, coalesce(t2.a,9999)
      FROM t3 JOIN
           t1 LEFT JOIN t2 ON (t1.c+1=t2.c AND t1.d=t2.d) OR (t1.f||'x')=t2.f
     WHERE t1.a=t3.y OR t1.b=t3.y*11 OR (t1.c=27027 AND round(t1.d)==80)
    ORDER BY 1, 2
................................................................................
} {1 80 9999 2 80 9999 scan 1 sort 1}
do_test where9-2.8 {
  count_steps {
    SELECT t3.x, t1.a, coalesce(t2.a,9999)
      FROM t3 JOIN
           t1 LEFT JOIN t2 ON (t1.c=t2.c AND t1.d=t2.d) OR (t1.f)=t2.f
     WHERE t1.a=t3.y OR t1.b=t3.y*11 OR (t1.c=27027 AND round(t1.d)==80)
    ORDER BY 1, 2
  }
} {1 80 2 1 80 28 1 80 54 1 80 80 2 80 2 2 80 28 2 80 54 2 80 80 scan 1 sort 1}


ifcapable explain {
  do_test where9-3.1 {
    set r [db eval {







|







 







|







 







|







 







|

>
>
>
>
>
>






|




|







 







|







|







 







|







7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
...
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
...
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
...
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
...
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
...
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
#    May you find forgiveness for yourself and forgive others.
#    May you share freely, never taking more than you give.
#
#***********************************************************************
# This file implements regression tests for SQLite library.  The
# focus of this file is testing the multi-index OR clause optimizer.
#
# $Id: where9.test,v 1.8 2009/04/21 09:02:47 danielk1977 Exp $

set testdir [file dirname $argv0]
source $testdir/tester.tcl

ifcapable !or_opt {
  finish_test
  return
................................................................................
  count_steps {
    SELECT a FROM t1
     WHERE b IS NULL
        OR c IS NULL
        OR d IS NULL
    ORDER BY a
  }
} {90 91 92 96 97 99 scan 0 sort 1}
do_test where9-1.2.2 {
  count_steps {
    SELECT a FROM t1
     WHERE +b IS NULL
        OR c IS NULL
        OR d IS NULL
    ORDER BY a
................................................................................
  count_steps {
    SELECT a FROM t1
     WHERE (b IS NULL AND c NOT NULL AND d NOT NULL)
        OR (b NOT NULL AND c IS NULL AND d NOT NULL)
        OR (b NOT NULL AND c NOT NULL AND d IS NULL)
    ORDER BY a
  }
} {90 91 92 97 scan 0 sort 1}
do_test where9-1.3.2 {
  count_steps {
    SELECT a FROM t4
     WHERE (b IS NULL AND c NOT NULL AND d NOT NULL)
        OR (b NOT NULL AND c IS NULL AND d NOT NULL)
        OR (b NOT NULL AND c NOT NULL AND d IS NULL)
    ORDER BY a
................................................................................

do_test where9-1.4 {
  count_steps {
    SELECT a FROM t1
     WHERE (b>=950 AND b<=1010) OR (b IS NULL AND c NOT NULL)
    ORDER BY a
  }
} {87 88 89 90 91 scan 0 sort 1}
do_test where9-1.5 {
  # When this test was originally written, SQLite used a rowset object 
  # to optimize the "ORDER BY a" clause. Now that it is using a rowhash,
  # this is not possible. So we have to comment out one term of the OR
  # expression in order to prevent SQLite from deeming a full-table
  # scan to be a better strategy than using multiple indexes, which would
  # defeat the point of the test.
  count_steps {
    SELECT a FROM t1
     WHERE a=83
        OR b=913
        OR c=28028
        OR (d>=82 AND d<83)
/*      OR (e>2802 AND e<2803)  */
        OR f='fghijklmn'
        OR g='hgfedcb'
    ORDER BY a
  }
} {5 31 57 82 83 84 85 86 87 scan 0 sort 1}
do_test where9-1.6 {
  count_steps {
    SELECT a FROM t1
     WHERE b=1012
        OR (d IS NULL AND e IS NOT NULL)
  }
} {92 scan 0 sort 0}
................................................................................
do_test where9-2.5 {
  count_steps {
    SELECT t1.a, coalesce(t2.a,9999)
      FROM t1 LEFT JOIN t2 ON (t1.c=t2.c AND t1.d=t2.d) OR (t1.f)=t2.f
     WHERE t1.a=80 OR t1.b=880 OR (t1.c=27027 AND round(t1.d)==80)
    ORDER BY 1
  }
} {80 80 80 2 80 28 80 54 scan 0 sort 1}
do_test where9-2.6 {
  count_steps {
    SELECT t1.a, coalesce(t2.a,9999)
      FROM t1 LEFT JOIN t2 ON (t1.c+1=t2.c AND t1.d=t2.d) OR (t1.f||'x')=t2.f
     WHERE t1.a=80 OR t1.b=880 OR (t1.c=27027 AND round(t1.d)==80)
    ORDER BY 1
  }
} {80 9999 scan 0 sort 1}
do_test where9-2.7 {
  count_steps {
    SELECT t3.x, t1.a, coalesce(t2.a,9999)
      FROM t3 JOIN
           t1 LEFT JOIN t2 ON (t1.c+1=t2.c AND t1.d=t2.d) OR (t1.f||'x')=t2.f
     WHERE t1.a=t3.y OR t1.b=t3.y*11 OR (t1.c=27027 AND round(t1.d)==80)
    ORDER BY 1, 2
................................................................................
} {1 80 9999 2 80 9999 scan 1 sort 1}
do_test where9-2.8 {
  count_steps {
    SELECT t3.x, t1.a, coalesce(t2.a,9999)
      FROM t3 JOIN
           t1 LEFT JOIN t2 ON (t1.c=t2.c AND t1.d=t2.d) OR (t1.f)=t2.f
     WHERE t1.a=t3.y OR t1.b=t3.y*11 OR (t1.c=27027 AND round(t1.d)==80)
    ORDER BY 1, 2, 3
  }
} {1 80 2 1 80 28 1 80 54 1 80 80 2 80 2 2 80 28 2 80 54 2 80 80 scan 1 sort 1}


ifcapable explain {
  do_test where9-3.1 {
    set r [db eval {

Changes to tool/mksqlite3c.tcl.

235
236
237
238
239
240
241

242
243
244
245
246
247
248
   hash.c
   opcodes.c

   os_os2.c
   os_unix.c
   os_win.c


   bitvec.c
   pcache.c
   pcache1.c
   rowset.c
   pager.c

   btmutex.c







>







235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
   hash.c
   opcodes.c

   os_os2.c
   os_unix.c
   os_win.c

   rowhash.c
   bitvec.c
   pcache.c
   pcache1.c
   rowset.c
   pager.c

   btmutex.c