← Back to branch summary

~ubuntu-branches/ubuntu/hardy/php5/hardy-updates

« back to all changes in this revision

Viewing changes to ext/sqlite/libsqlite/src/where.c

  • Committer: Bazaar Package Importer
  • Author(s): Adam Conrad
  • Date: 2005-10-09 03:14:32 UTC
  • Revision ID: james.westby@ubuntu.com-20051009031432-kspik3lobxstafv9
Tags: upstream-5.0.5
Import upstream version 5.0.5

Show diffs side-by-side

added added

removed removed

Lines of Context:
ext/sqlite/libsqlite/src/where.c
 
1
/*
 
2
** 2001 September 15
 
3
**
 
4
** The author disclaims copyright to this source code.  In place of
 
5
** a legal notice, here is a blessing:
 
6
**
 
7
**    May you do good and not evil.
 
8
**    May you find forgiveness for yourself and forgive others.
 
9
**    May you share freely, never taking more than you give.
 
10
**
 
11
*************************************************************************
 
12
** This module contains C code that generates VDBE code used to process
 
13
** the WHERE clause of SQL statements.
 
14
**
 
15
** $Id: where.c,v 1.6 2004/07/10 12:27:51 wez Exp $
 
16
*/
 
17
#include "sqliteInt.h"
 
18
 
 
19
/*
 
20
** The query generator uses an array of instances of this structure to
 
21
** help it analyze the subexpressions of the WHERE clause.  Each WHERE
 
22
** clause subexpression is separated from the others by an AND operator.
 
23
*/
 
24
typedef struct ExprInfo ExprInfo;
 
25
struct ExprInfo {
 
26
  Expr *p;                /* Pointer to the subexpression */
 
27
  u8 indexable;           /* True if this subexprssion is usable by an index */
 
28
  short int idxLeft;      /* p->pLeft is a column in this table number. -1 if
 
29
                          ** p->pLeft is not the column of any table */
 
30
  short int idxRight;     /* p->pRight is a column in this table number. -1 if
 
31
                          ** p->pRight is not the column of any table */
 
32
  unsigned prereqLeft;    /* Bitmask of tables referenced by p->pLeft */
 
33
  unsigned prereqRight;   /* Bitmask of tables referenced by p->pRight */
 
34
  unsigned prereqAll;     /* Bitmask of tables referenced by p */
 
35
};
 
36
 
 
37
/*
 
38
** An instance of the following structure keeps track of a mapping
 
39
** between VDBE cursor numbers and bitmasks.  The VDBE cursor numbers
 
40
** are small integers contained in SrcList_item.iCursor and Expr.iTable
 
41
** fields.  For any given WHERE clause, we want to track which cursors
 
42
** are being used, so we assign a single bit in a 32-bit word to track
 
43
** that cursor.  Then a 32-bit integer is able to show the set of all
 
44
** cursors being used.
 
45
*/
 
46
typedef struct ExprMaskSet ExprMaskSet;
 
47
struct ExprMaskSet {
 
48
  int n;          /* Number of assigned cursor values */
 
49
  int ix[32];     /* Cursor assigned to each bit */
 
50
};
 
51
 
 
52
/*
 
53
** Determine the number of elements in an array.
 
54
*/
 
55
#define ARRAYSIZE(X)  (sizeof(X)/sizeof(X[0]))
 
56
 
 
57
/*
 
58
** This routine is used to divide the WHERE expression into subexpressions
 
59
** separated by the AND operator.
 
60
**
 
61
** aSlot[] is an array of subexpressions structures.
 
62
** There are nSlot spaces left in this array.  This routine attempts to
 
63
** split pExpr into subexpressions and fills aSlot[] with those subexpressions.
 
64
** The return value is the number of slots filled.
 
65
*/
 
66
static int exprSplit(int nSlot, ExprInfo *aSlot, Expr *pExpr){
 
67
  int cnt = 0;
 
68
  if( pExpr==0 || nSlot<1 ) return 0;
 
69
  if( nSlot==1 || pExpr->op!=TK_AND ){
 
70
    aSlot[0].p = pExpr;
 
71
    return 1;
 
72
  }
 
73
  if( pExpr->pLeft->op!=TK_AND ){
 
74
    aSlot[0].p = pExpr->pLeft;
 
75
    cnt = 1 + exprSplit(nSlot-1, &aSlot[1], pExpr->pRight);
 
76
  }else{
 
77
    cnt = exprSplit(nSlot, aSlot, pExpr->pLeft);
 
78
    cnt += exprSplit(nSlot-cnt, &aSlot[cnt], pExpr->pRight);
 
79
  }
 
80
  return cnt;
 
81
}
 
82
 
 
83
/*
 
84
** Initialize an expression mask set
 
85
*/
 
86
#define initMaskSet(P)  memset(P, 0, sizeof(*P))
 
87
 
 
88
/*
 
89
** Return the bitmask for the given cursor.  Assign a new bitmask
 
90
** if this is the first time the cursor has been seen.
 
91
*/
 
92
static int getMask(ExprMaskSet *pMaskSet, int iCursor){
 
93
  int i;
 
94
  for(i=0; i<pMaskSet->n; i++){
 
95
    if( pMaskSet->ix[i]==iCursor ) return 1<<i;
 
96
  }
 
97
  if( i==pMaskSet->n && i<ARRAYSIZE(pMaskSet->ix) ){
 
98
    pMaskSet->n++;
 
99
    pMaskSet->ix[i] = iCursor;
 
100
    return 1<<i;
 
101
  }
 
102
  return 0;
 
103
}
 
104
 
 
105
/*
 
106
** Destroy an expression mask set
 
107
*/
 
108
#define freeMaskSet(P)   /* NO-OP */
 
109
 
 
110
/*
 
111
** This routine walks (recursively) an expression tree and generates
 
112
** a bitmask indicating which tables are used in that expression
 
113
** tree.
 
114
**
 
115
** In order for this routine to work, the calling function must have
 
116
** previously invoked sqliteExprResolveIds() on the expression.  See
 
117
** the header comment on that routine for additional information.
 
118
** The sqliteExprResolveIds() routines looks for column names and
 
119
** sets their opcodes to TK_COLUMN and their Expr.iTable fields to
 
120
** the VDBE cursor number of the table.
 
121
*/
 
122
static int exprTableUsage(ExprMaskSet *pMaskSet, Expr *p){
 
123
  unsigned int mask = 0;
 
124
  if( p==0 ) return 0;
 
125
  if( p->op==TK_COLUMN ){
 
126
    return getMask(pMaskSet, p->iTable);
 
127
  }
 
128
  if( p->pRight ){
 
129
    mask = exprTableUsage(pMaskSet, p->pRight);
 
130
  }
 
131
  if( p->pLeft ){
 
132
    mask |= exprTableUsage(pMaskSet, p->pLeft);
 
133
  }
 
134
  if( p->pList ){
 
135
    int i;
 
136
    for(i=0; i<p->pList->nExpr; i++){
 
137
      mask |= exprTableUsage(pMaskSet, p->pList->a[i].pExpr);
 
138
    }
 
139
  }
 
140
  return mask;
 
141
}
 
142
 
 
143
/*
 
144
** Return TRUE if the given operator is one of the operators that is
 
145
** allowed for an indexable WHERE clause.  The allowed operators are
 
146
** "=", "<", ">", "<=", ">=", and "IN".
 
147
*/
 
148
static int allowedOp(int op){
 
149
  switch( op ){
 
150
    case TK_LT:
 
151
    case TK_LE:
 
152
    case TK_GT:
 
153
    case TK_GE:
 
154
    case TK_EQ:
 
155
    case TK_IN:
 
156
      return 1;
 
157
    default:
 
158
      return 0;
 
159
  }
 
160
}
 
161
 
 
162
/*
 
163
** The input to this routine is an ExprInfo structure with only the
 
164
** "p" field filled in.  The job of this routine is to analyze the
 
165
** subexpression and populate all the other fields of the ExprInfo
 
166
** structure.
 
167
*/
 
168
static void exprAnalyze(ExprMaskSet *pMaskSet, ExprInfo *pInfo){
 
169
  Expr *pExpr = pInfo->p;
 
170
  pInfo->prereqLeft = exprTableUsage(pMaskSet, pExpr->pLeft);
 
171
  pInfo->prereqRight = exprTableUsage(pMaskSet, pExpr->pRight);
 
172
  pInfo->prereqAll = exprTableUsage(pMaskSet, pExpr);
 
173
  pInfo->indexable = 0;
 
174
  pInfo->idxLeft = -1;
 
175
  pInfo->idxRight = -1;
 
176
  if( allowedOp(pExpr->op) && (pInfo->prereqRight & pInfo->prereqLeft)==0 ){
 
177
    if( pExpr->pRight && pExpr->pRight->op==TK_COLUMN ){
 
178
      pInfo->idxRight = pExpr->pRight->iTable;
 
179
      pInfo->indexable = 1;
 
180
    }
 
181
    if( pExpr->pLeft->op==TK_COLUMN ){
 
182
      pInfo->idxLeft = pExpr->pLeft->iTable;
 
183
      pInfo->indexable = 1;
 
184
    }
 
185
  }
 
186
}
 
187
 
 
188
/*
 
189
** pOrderBy is an ORDER BY clause from a SELECT statement.  pTab is the
 
190
** left-most table in the FROM clause of that same SELECT statement and
 
191
** the table has a cursor number of "base".
 
192
**
 
193
** This routine attempts to find an index for pTab that generates the
 
194
** correct record sequence for the given ORDER BY clause.  The return value
 
195
** is a pointer to an index that does the job.  NULL is returned if the
 
196
** table has no index that will generate the correct sort order.
 
197
**
 
198
** If there are two or more indices that generate the correct sort order
 
199
** and pPreferredIdx is one of those indices, then return pPreferredIdx.
 
200
**
 
201
** nEqCol is the number of columns of pPreferredIdx that are used as
 
202
** equality constraints.  Any index returned must have exactly this same
 
203
** set of columns.  The ORDER BY clause only matches index columns beyond the
 
204
** the first nEqCol columns.
 
205
**
 
206
** All terms of the ORDER BY clause must be either ASC or DESC.  The
 
207
** *pbRev value is set to 1 if the ORDER BY clause is all DESC and it is
 
208
** set to 0 if the ORDER BY clause is all ASC.
 
209
*/
 
210
static Index *findSortingIndex(
 
211
  Table *pTab,            /* The table to be sorted */
 
212
  int base,               /* Cursor number for pTab */
 
213
  ExprList *pOrderBy,     /* The ORDER BY clause */
 
214
  Index *pPreferredIdx,   /* Use this index, if possible and not NULL */
 
215
  int nEqCol,             /* Number of index columns used with == constraints */
 
216
  int *pbRev              /* Set to 1 if ORDER BY is DESC */
 
217
){
 
218
  int i, j;
 
219
  Index *pMatch;
 
220
  Index *pIdx;
 
221
  int sortOrder;
 
222
 
 
223
  assert( pOrderBy!=0 );
 
224
  assert( pOrderBy->nExpr>0 );
 
225
  sortOrder = pOrderBy->a[0].sortOrder & SQLITE_SO_DIRMASK;
 
226
  for(i=0; i<pOrderBy->nExpr; i++){
 
227
    Expr *p;
 
228
    if( (pOrderBy->a[i].sortOrder & SQLITE_SO_DIRMASK)!=sortOrder ){
 
229
      /* Indices can only be used if all ORDER BY terms are either
 
230
      ** DESC or ASC.  Indices cannot be used on a mixture. */
 
231
      return 0;
 
232
    }
 
233
    if( (pOrderBy->a[i].sortOrder & SQLITE_SO_TYPEMASK)!=SQLITE_SO_UNK ){
 
234
      /* Do not sort by index if there is a COLLATE clause */
 
235
      return 0;
 
236
    }
 
237
    p = pOrderBy->a[i].pExpr;
 
238
    if( p->op!=TK_COLUMN || p->iTable!=base ){
 
239
      /* Can not use an index sort on anything that is not a column in the
 
240
      ** left-most table of the FROM clause */
 
241
      return 0;
 
242
    }
 
243
  }
 
244
  
 
245
  /* If we get this far, it means the ORDER BY clause consists only of
 
246
  ** ascending columns in the left-most table of the FROM clause.  Now
 
247
  ** check for a matching index.
 
248
  */
 
249
  pMatch = 0;
 
250
  for(pIdx=pTab->pIndex; pIdx; pIdx=pIdx->pNext){
 
251
    int nExpr = pOrderBy->nExpr;
 
252
    if( pIdx->nColumn < nEqCol || pIdx->nColumn < nExpr ) continue;
 
253
    for(i=j=0; i<nEqCol; i++){
 
254
      if( pPreferredIdx->aiColumn[i]!=pIdx->aiColumn[i] ) break;
 
255
      if( j<nExpr && pOrderBy->a[j].pExpr->iColumn==pIdx->aiColumn[i] ){ j++; }
 
256
    }
 
257
    if( i<nEqCol ) continue;
 
258
    for(i=0; i+j<nExpr; i++){
 
259
      if( pOrderBy->a[i+j].pExpr->iColumn!=pIdx->aiColumn[i+nEqCol] ) break;
 
260
    }
 
261
    if( i+j>=nExpr ){
 
262
      pMatch = pIdx;
 
263
      if( pIdx==pPreferredIdx ) break;
 
264
    }
 
265
  }
 
266
  if( pMatch && pbRev ){
 
267
    *pbRev = sortOrder==SQLITE_SO_DESC;
 
268
  }
 
269
  return pMatch;
 
270
}
 
271
 
 
272
/*
 
273
** Generate the beginning of the loop used for WHERE clause processing.
 
274
** The return value is a pointer to an (opaque) structure that contains
 
275
** information needed to terminate the loop.  Later, the calling routine
 
276
** should invoke sqliteWhereEnd() with the return value of this function
 
277
** in order to complete the WHERE clause processing.
 
278
**
 
279
** If an error occurs, this routine returns NULL.
 
280
**
 
281
** The basic idea is to do a nested loop, one loop for each table in
 
282
** the FROM clause of a select.  (INSERT and UPDATE statements are the
 
283
** same as a SELECT with only a single table in the FROM clause.)  For
 
284
** example, if the SQL is this:
 
285
**
 
286
**       SELECT * FROM t1, t2, t3 WHERE ...;
 
287
**
 
288
** Then the code generated is conceptually like the following:
 
289
**
 
290
**      foreach row1 in t1 do       \    Code generated
 
291
**        foreach row2 in t2 do      |-- by sqliteWhereBegin()
 
292
**          foreach row3 in t3 do   /
 
293
**            ...
 
294
**          end                     \    Code generated
 
295
**        end                        |-- by sqliteWhereEnd()
 
296
**      end                         /
 
297
**
 
298
** There are Btree cursors associated with each table.  t1 uses cursor
 
299
** number pTabList->a[0].iCursor.  t2 uses the cursor pTabList->a[1].iCursor.
 
300
** And so forth.  This routine generates code to open those VDBE cursors
 
301
** and sqliteWhereEnd() generates the code to close them.
 
302
**
 
303
** If the WHERE clause is empty, the foreach loops must each scan their
 
304
** entire tables.  Thus a three-way join is an O(N^3) operation.  But if
 
305
** the tables have indices and there are terms in the WHERE clause that
 
306
** refer to those indices, a complete table scan can be avoided and the
 
307
** code will run much faster.  Most of the work of this routine is checking
 
308
** to see if there are indices that can be used to speed up the loop.
 
309
**
 
310
** Terms of the WHERE clause are also used to limit which rows actually
 
311
** make it to the "..." in the middle of the loop.  After each "foreach",
 
312
** terms of the WHERE clause that use only terms in that loop and outer
 
313
** loops are evaluated and if false a jump is made around all subsequent
 
314
** inner loops (or around the "..." if the test occurs within the inner-
 
315
** most loop)
 
316
**
 
317
** OUTER JOINS
 
318
**
 
319
** An outer join of tables t1 and t2 is conceptally coded as follows:
 
320
**
 
321
**    foreach row1 in t1 do
 
322
**      flag = 0
 
323
**      foreach row2 in t2 do
 
324
**        start:
 
325
**          ...
 
326
**          flag = 1
 
327
**      end
 
328
**      if flag==0 then
 
329
**        move the row2 cursor to a null row
 
330
**        goto start
 
331
**      fi
 
332
**    end
 
333
**
 
334
** ORDER BY CLAUSE PROCESSING
 
335
**
 
336
** *ppOrderBy is a pointer to the ORDER BY clause of a SELECT statement,
 
337
** if there is one.  If there is no ORDER BY clause or if this routine
 
338
** is called from an UPDATE or DELETE statement, then ppOrderBy is NULL.
 
339
**
 
340
** If an index can be used so that the natural output order of the table
 
341
** scan is correct for the ORDER BY clause, then that index is used and
 
342
** *ppOrderBy is set to NULL.  This is an optimization that prevents an
 
343
** unnecessary sort of the result set if an index appropriate for the
 
344
** ORDER BY clause already exists.
 
345
**
 
346
** If the where clause loops cannot be arranged to provide the correct
 
347
** output order, then the *ppOrderBy is unchanged.
 
348
*/
 
349
WhereInfo *sqliteWhereBegin(
 
350
  Parse *pParse,       /* The parser context */
 
351
  SrcList *pTabList,   /* A list of all tables to be scanned */
 
352
  Expr *pWhere,        /* The WHERE clause */
 
353
  int pushKey,         /* If TRUE, leave the table key on the stack */
 
354
  ExprList **ppOrderBy /* An ORDER BY clause, or NULL */
 
355
){
 
356
  int i;                     /* Loop counter */
 
357
  WhereInfo *pWInfo;         /* Will become the return value of this function */
 
358
  Vdbe *v = pParse->pVdbe;   /* The virtual database engine */
 
359
  int brk, cont = 0;         /* Addresses used during code generation */
 
360
  int nExpr;           /* Number of subexpressions in the WHERE clause */
 
361
  int loopMask;        /* One bit set for each outer loop */
 
362
  int haveKey;         /* True if KEY is on the stack */
 
363
  ExprMaskSet maskSet; /* The expression mask set */
 
364
  int iDirectEq[32];   /* Term of the form ROWID==X for the N-th table */
 
365
  int iDirectLt[32];   /* Term of the form ROWID<X or ROWID<=X */
 
366
  int iDirectGt[32];   /* Term of the form ROWID>X or ROWID>=X */
 
367
  ExprInfo aExpr[101]; /* The WHERE clause is divided into these expressions */
 
368
 
 
369
  /* pushKey is only allowed if there is a single table (as in an INSERT or
 
370
  ** UPDATE statement)
 
371
  */
 
372
  assert( pushKey==0 || pTabList->nSrc==1 );
 
373
 
 
374
  /* Split the WHERE clause into separate subexpressions where each
 
375
  ** subexpression is separated by an AND operator.  If the aExpr[]
 
376
  ** array fills up, the last entry might point to an expression which
 
377
  ** contains additional unfactored AND operators.
 
378
  */
 
379
  initMaskSet(&maskSet);
 
380
  memset(aExpr, 0, sizeof(aExpr));
 
381
  nExpr = exprSplit(ARRAYSIZE(aExpr), aExpr, pWhere);
 
382
  if( nExpr==ARRAYSIZE(aExpr) ){
 
383
    sqliteErrorMsg(pParse, "WHERE clause too complex - no more "
 
384
       "than %d terms allowed", (int)ARRAYSIZE(aExpr)-1);
 
385
    return 0;
 
386
  }
 
387
  
 
388
  /* Allocate and initialize the WhereInfo structure that will become the
 
389
  ** return value.
 
390
  */
 
391
  pWInfo = sqliteMalloc( sizeof(WhereInfo) + pTabList->nSrc*sizeof(WhereLevel));
 
392
  if( sqlite_malloc_failed ){
 
393
    sqliteFree(pWInfo);
 
394
    return 0;
 
395
  }
 
396
  pWInfo->pParse = pParse;
 
397
  pWInfo->pTabList = pTabList;
 
398
  pWInfo->peakNTab = pWInfo->savedNTab = pParse->nTab;
 
399
  pWInfo->iBreak = sqliteVdbeMakeLabel(v);
 
400
 
 
401
  /* Special case: a WHERE clause that is constant.  Evaluate the
 
402
  ** expression and either jump over all of the code or fall thru.
 
403
  */
 
404
  if( pWhere && (pTabList->nSrc==0 || sqliteExprIsConstant(pWhere)) ){
 
405
    sqliteExprIfFalse(pParse, pWhere, pWInfo->iBreak, 1);
 
406
    pWhere = 0;
 
407
  }
 
408
 
 
409
  /* Analyze all of the subexpressions.
 
410
  */
 
411
  for(i=0; i<nExpr; i++){
 
412
    exprAnalyze(&maskSet, &aExpr[i]);
 
413
 
 
414
    /* If we are executing a trigger body, remove all references to
 
415
    ** new.* and old.* tables from the prerequisite masks.
 
416
    */
 
417
    if( pParse->trigStack ){
 
418
      int x;
 
419
      if( (x = pParse->trigStack->newIdx) >= 0 ){
 
420
        int mask = ~getMask(&maskSet, x);
 
421
        aExpr[i].prereqRight &= mask;
 
422
        aExpr[i].prereqLeft &= mask;
 
423
        aExpr[i].prereqAll &= mask;
 
424
      }
 
425
      if( (x = pParse->trigStack->oldIdx) >= 0 ){
 
426
        int mask = ~getMask(&maskSet, x);
 
427
        aExpr[i].prereqRight &= mask;
 
428
        aExpr[i].prereqLeft &= mask;
 
429
        aExpr[i].prereqAll &= mask;
 
430
      }
 
431
    }
 
432
  }
 
433
 
 
434
  /* Figure out what index to use (if any) for each nested loop.
 
435
  ** Make pWInfo->a[i].pIdx point to the index to use for the i-th nested
 
436
  ** loop where i==0 is the outer loop and i==pTabList->nSrc-1 is the inner
 
437
  ** loop. 
 
438
  **
 
439
  ** If terms exist that use the ROWID of any table, then set the
 
440
  ** iDirectEq[], iDirectLt[], or iDirectGt[] elements for that table
 
441
  ** to the index of the term containing the ROWID.  We always prefer
 
442
  ** to use a ROWID which can directly access a table rather than an
 
443
  ** index which requires reading an index first to get the rowid then
 
444
  ** doing a second read of the actual database table.
 
445
  **
 
446
  ** Actually, if there are more than 32 tables in the join, only the
 
447
  ** first 32 tables are candidates for indices.  This is (again) due
 
448
  ** to the limit of 32 bits in an integer bitmask.
 
449
  */
 
450
  loopMask = 0;
 
451
  for(i=0; i<pTabList->nSrc && i<ARRAYSIZE(iDirectEq); i++){
 
452
    int j;
 
453
    int iCur = pTabList->a[i].iCursor;    /* The cursor for this table */
 
454
    int mask = getMask(&maskSet, iCur);   /* Cursor mask for this table */
 
455
    Table *pTab = pTabList->a[i].pTab;
 
456
    Index *pIdx;
 
457
    Index *pBestIdx = 0;
 
458
    int bestScore = 0;
 
459
 
 
460
    /* Check to see if there is an expression that uses only the
 
461
    ** ROWID field of this table.  For terms of the form ROWID==expr
 
462
    ** set iDirectEq[i] to the index of the term.  For terms of the
 
463
    ** form ROWID<expr or ROWID<=expr set iDirectLt[i] to the term index.
 
464
    ** For terms like ROWID>expr or ROWID>=expr set iDirectGt[i].
 
465
    **
 
466
    ** (Added:) Treat ROWID IN expr like ROWID=expr.
 
467
    */
 
468
    pWInfo->a[i].iCur = -1;
 
469
    iDirectEq[i] = -1;
 
470
    iDirectLt[i] = -1;
 
471
    iDirectGt[i] = -1;
 
472
    for(j=0; j<nExpr; j++){
 
473
      if( aExpr[j].idxLeft==iCur && aExpr[j].p->pLeft->iColumn<0
 
474
            && (aExpr[j].prereqRight & loopMask)==aExpr[j].prereqRight ){
 
475
        switch( aExpr[j].p->op ){
 
476
          case TK_IN:
 
477
          case TK_EQ: iDirectEq[i] = j; break;
 
478
          case TK_LE:
 
479
          case TK_LT: iDirectLt[i] = j; break;
 
480
          case TK_GE:
 
481
          case TK_GT: iDirectGt[i] = j;  break;
 
482
        }
 
483
      }
 
484
      if( aExpr[j].idxRight==iCur && aExpr[j].p->pRight->iColumn<0
 
485
            && (aExpr[j].prereqLeft & loopMask)==aExpr[j].prereqLeft ){
 
486
        switch( aExpr[j].p->op ){
 
487
          case TK_EQ: iDirectEq[i] = j;  break;
 
488
          case TK_LE:
 
489
          case TK_LT: iDirectGt[i] = j;  break;
 
490
          case TK_GE:
 
491
          case TK_GT: iDirectLt[i] = j;  break;
 
492
        }
 
493
      }
 
494
    }
 
495
    if( iDirectEq[i]>=0 ){
 
496
      loopMask |= mask;
 
497
      pWInfo->a[i].pIdx = 0;
 
498
      continue;
 
499
    }
 
500
 
 
501
    /* Do a search for usable indices.  Leave pBestIdx pointing to
 
502
    ** the "best" index.  pBestIdx is left set to NULL if no indices
 
503
    ** are usable.
 
504
    **
 
505
    ** The best index is determined as follows.  For each of the
 
506
    ** left-most terms that is fixed by an equality operator, add
 
507
    ** 8 to the score.  The right-most term of the index may be
 
508
    ** constrained by an inequality.  Add 1 if for an "x<..." constraint
 
509
    ** and add 2 for an "x>..." constraint.  Chose the index that
 
510
    ** gives the best score.
 
511
    **
 
512
    ** This scoring system is designed so that the score can later be
 
513
    ** used to determine how the index is used.  If the score&7 is 0
 
514
    ** then all constraints are equalities.  If score&1 is not 0 then
 
515
    ** there is an inequality used as a termination key.  (ex: "x<...")
 
516
    ** If score&2 is not 0 then there is an inequality used as the
 
517
    ** start key.  (ex: "x>...").  A score or 4 is the special case
 
518
    ** of an IN operator constraint.  (ex:  "x IN ...").
 
519
    **
 
520
    ** The IN operator (as in "<expr> IN (...)") is treated the same as
 
521
    ** an equality comparison except that it can only be used on the
 
522
    ** left-most column of an index and other terms of the WHERE clause
 
523
    ** cannot be used in conjunction with the IN operator to help satisfy
 
524
    ** other columns of the index.
 
525
    */
 
526
    for(pIdx=pTab->pIndex; pIdx; pIdx=pIdx->pNext){
 
527
      int eqMask = 0;  /* Index columns covered by an x=... term */
 
528
      int ltMask = 0;  /* Index columns covered by an x<... term */
 
529
      int gtMask = 0;  /* Index columns covered by an x>... term */
 
530
      int inMask = 0;  /* Index columns covered by an x IN .. term */
 
531
      int nEq, m, score;
 
532
 
 
533
      if( pIdx->nColumn>32 ) continue;  /* Ignore indices too many columns */
 
534
      for(j=0; j<nExpr; j++){
 
535
        if( aExpr[j].idxLeft==iCur 
 
536
             && (aExpr[j].prereqRight & loopMask)==aExpr[j].prereqRight ){
 
537
          int iColumn = aExpr[j].p->pLeft->iColumn;
 
538
          int k;
 
539
          for(k=0; k<pIdx->nColumn; k++){
 
540
            if( pIdx->aiColumn[k]==iColumn ){
 
541
              switch( aExpr[j].p->op ){
 
542
                case TK_IN: {
 
543
                  if( k==0 ) inMask |= 1;
 
544
                  break;
 
545
                }
 
546
                case TK_EQ: {
 
547
                  eqMask |= 1<<k;
 
548
                  break;
 
549
                }
 
550
                case TK_LE:
 
551
                case TK_LT: {
 
552
                  ltMask |= 1<<k;
 
553
                  break;
 
554
                }
 
555
                case TK_GE:
 
556
                case TK_GT: {
 
557
                  gtMask |= 1<<k;
 
558
                  break;
 
559
                }
 
560
                default: {
 
561
                  /* CANT_HAPPEN */
 
562
                  assert( 0 );
 
563
                  break;
 
564
                }
 
565
              }
 
566
              break;
 
567
            }
 
568
          }
 
569
        }
 
570
        if( aExpr[j].idxRight==iCur 
 
571
             && (aExpr[j].prereqLeft & loopMask)==aExpr[j].prereqLeft ){
 
572
          int iColumn = aExpr[j].p->pRight->iColumn;
 
573
          int k;
 
574
          for(k=0; k<pIdx->nColumn; k++){
 
575
            if( pIdx->aiColumn[k]==iColumn ){
 
576
              switch( aExpr[j].p->op ){
 
577
                case TK_EQ: {
 
578
                  eqMask |= 1<<k;
 
579
                  break;
 
580
                }
 
581
                case TK_LE:
 
582
                case TK_LT: {
 
583
                  gtMask |= 1<<k;
 
584
                  break;
 
585
                }
 
586
                case TK_GE:
 
587
                case TK_GT: {
 
588
                  ltMask |= 1<<k;
 
589
                  break;
 
590
                }
 
591
                default: {
 
592
                  /* CANT_HAPPEN */
 
593
                  assert( 0 );
 
594
                  break;
 
595
                }
 
596
              }
 
597
              break;
 
598
            }
 
599
          }
 
600
        }
 
601
      }
 
602
 
 
603
      /* The following loop ends with nEq set to the number of columns
 
604
      ** on the left of the index with == constraints.
 
605
      */
 
606
      for(nEq=0; nEq<pIdx->nColumn; nEq++){
 
607
        m = (1<<(nEq+1))-1;
 
608
        if( (m & eqMask)!=m ) break;
 
609
      }
 
610
      score = nEq*8;   /* Base score is 8 times number of == constraints */
 
611
      m = 1<<nEq;
 
612
      if( m & ltMask ) score++;    /* Increase score for a < constraint */
 
613
      if( m & gtMask ) score+=2;   /* Increase score for a > constraint */
 
614
      if( score==0 && inMask ) score = 4;  /* Default score for IN constraint */
 
615
      if( score>bestScore ){
 
616
        pBestIdx = pIdx;
 
617
        bestScore = score;
 
618
      }
 
619
    }
 
620
    pWInfo->a[i].pIdx = pBestIdx;
 
621
    pWInfo->a[i].score = bestScore;
 
622
    pWInfo->a[i].bRev = 0;
 
623
    loopMask |= mask;
 
624
    if( pBestIdx ){
 
625
      pWInfo->a[i].iCur = pParse->nTab++;
 
626
      pWInfo->peakNTab = pParse->nTab;
 
627
    }
 
628
  }
 
629
 
 
630
  /* Check to see if the ORDER BY clause is or can be satisfied by the
 
631
  ** use of an index on the first table.
 
632
  */
 
633
  if( ppOrderBy && *ppOrderBy && pTabList->nSrc>0 ){
 
634
     Index *pSortIdx;
 
635
     Index *pIdx;
 
636
     Table *pTab;
 
637
     int bRev = 0;
 
638
 
 
639
     pTab = pTabList->a[0].pTab;
 
640
     pIdx = pWInfo->a[0].pIdx;
 
641
     if( pIdx && pWInfo->a[0].score==4 ){
 
642
       /* If there is already an IN index on the left-most table,
 
643
       ** it will not give the correct sort order.
 
644
       ** So, pretend that no suitable index is found.
 
645
       */
 
646
       pSortIdx = 0;
 
647
     }else if( iDirectEq[0]>=0 || iDirectLt[0]>=0 || iDirectGt[0]>=0 ){
 
648
       /* If the left-most column is accessed using its ROWID, then do
 
649
       ** not try to sort by index.
 
650
       */
 
651
       pSortIdx = 0;
 
652
     }else{
 
653
       int nEqCol = (pWInfo->a[0].score+4)/8;
 
654
       pSortIdx = findSortingIndex(pTab, pTabList->a[0].iCursor, 
 
655
                                   *ppOrderBy, pIdx, nEqCol, &bRev);
 
656
     }
 
657
     if( pSortIdx && (pIdx==0 || pIdx==pSortIdx) ){
 
658
       if( pIdx==0 ){
 
659
         pWInfo->a[0].pIdx = pSortIdx;
 
660
         pWInfo->a[0].iCur = pParse->nTab++;
 
661
         pWInfo->peakNTab = pParse->nTab;
 
662
       }
 
663
       pWInfo->a[0].bRev = bRev;
 
664
       *ppOrderBy = 0;
 
665
     }
 
666
  }
 
667
 
 
668
  /* Open all tables in the pTabList and all indices used by those tables.
 
669
  */
 
670
  for(i=0; i<pTabList->nSrc; i++){
 
671
    Table *pTab;
 
672
    Index *pIx;
 
673
 
 
674
    pTab = pTabList->a[i].pTab;
 
675
    if( pTab->isTransient || pTab->pSelect ) continue;
 
676
    sqliteVdbeAddOp(v, OP_Integer, pTab->iDb, 0);
 
677
    sqliteVdbeOp3(v, OP_OpenRead, pTabList->a[i].iCursor, pTab->tnum,
 
678
                     pTab->zName, P3_STATIC);
 
679
    sqliteCodeVerifySchema(pParse, pTab->iDb);
 
680
    if( (pIx = pWInfo->a[i].pIdx)!=0 ){
 
681
      sqliteVdbeAddOp(v, OP_Integer, pIx->iDb, 0);
 
682
      sqliteVdbeOp3(v, OP_OpenRead, pWInfo->a[i].iCur, pIx->tnum, pIx->zName,0);
 
683
    }
 
684
  }
 
685
 
 
686
  /* Generate the code to do the search
 
687
  */
 
688
  loopMask = 0;
 
689
  for(i=0; i<pTabList->nSrc; i++){
 
690
    int j, k;
 
691
    int iCur = pTabList->a[i].iCursor;
 
692
    Index *pIdx;
 
693
    WhereLevel *pLevel = &pWInfo->a[i];
 
694
 
 
695
    /* If this is the right table of a LEFT OUTER JOIN, allocate and
 
696
    ** initialize a memory cell that records if this table matches any
 
697
    ** row of the left table of the join.
 
698
    */
 
699
    if( i>0 && (pTabList->a[i-1].jointype & JT_LEFT)!=0 ){
 
700
      if( !pParse->nMem ) pParse->nMem++;
 
701
      pLevel->iLeftJoin = pParse->nMem++;
 
702
      sqliteVdbeAddOp(v, OP_String, 0, 0);
 
703
      sqliteVdbeAddOp(v, OP_MemStore, pLevel->iLeftJoin, 1);
 
704
    }
 
705
 
 
706
    pIdx = pLevel->pIdx;
 
707
    pLevel->inOp = OP_Noop;
 
708
    if( i<ARRAYSIZE(iDirectEq) && iDirectEq[i]>=0 ){
 
709
      /* Case 1:  We can directly reference a single row using an
 
710
      **          equality comparison against the ROWID field.  Or
 
711
      **          we reference multiple rows using a "rowid IN (...)"
 
712
      **          construct.
 
713
      */
 
714
      k = iDirectEq[i];
 
715
      assert( k<nExpr );
 
716
      assert( aExpr[k].p!=0 );
 
717
      assert( aExpr[k].idxLeft==iCur || aExpr[k].idxRight==iCur );
 
718
      brk = pLevel->brk = sqliteVdbeMakeLabel(v);
 
719
      if( aExpr[k].idxLeft==iCur ){
 
720
        Expr *pX = aExpr[k].p;
 
721
        if( pX->op!=TK_IN ){
 
722
          sqliteExprCode(pParse, aExpr[k].p->pRight);
 
723
        }else if( pX->pList ){
 
724
          sqliteVdbeAddOp(v, OP_SetFirst, pX->iTable, brk);
 
725
          pLevel->inOp = OP_SetNext;
 
726
          pLevel->inP1 = pX->iTable;
 
727
          pLevel->inP2 = sqliteVdbeCurrentAddr(v);
 
728
        }else{
 
729
          assert( pX->pSelect );
 
730
          sqliteVdbeAddOp(v, OP_Rewind, pX->iTable, brk);
 
731
          sqliteVdbeAddOp(v, OP_KeyAsData, pX->iTable, 1);
 
732
          pLevel->inP2 = sqliteVdbeAddOp(v, OP_FullKey, pX->iTable, 0);
 
733
          pLevel->inOp = OP_Next;
 
734
          pLevel->inP1 = pX->iTable;
 
735
        }
 
736
      }else{
 
737
        sqliteExprCode(pParse, aExpr[k].p->pLeft);
 
738
      }
 
739
      aExpr[k].p = 0;
 
740
      cont = pLevel->cont = sqliteVdbeMakeLabel(v);
 
741
      sqliteVdbeAddOp(v, OP_MustBeInt, 1, brk);
 
742
      haveKey = 0;
 
743
      sqliteVdbeAddOp(v, OP_NotExists, iCur, brk);
 
744
      pLevel->op = OP_Noop;
 
745
    }else if( pIdx!=0 && pLevel->score>0 && pLevel->score%4==0 ){
 
746
      /* Case 2:  There is an index and all terms of the WHERE clause that
 
747
      **          refer to the index use the "==" or "IN" operators.
 
748
      */
 
749
      int start;
 
750
      int testOp;
 
751
      int nColumn = (pLevel->score+4)/8;
 
752
      brk = pLevel->brk = sqliteVdbeMakeLabel(v);
 
753
      for(j=0; j<nColumn; j++){
 
754
        for(k=0; k<nExpr; k++){
 
755
          Expr *pX = aExpr[k].p;
 
756
          if( pX==0 ) continue;
 
757
          if( aExpr[k].idxLeft==iCur
 
758
             && (aExpr[k].prereqRight & loopMask)==aExpr[k].prereqRight 
 
759
             && pX->pLeft->iColumn==pIdx->aiColumn[j]
 
760
          ){
 
761
            if( pX->op==TK_EQ ){
 
762
              sqliteExprCode(pParse, pX->pRight);
 
763
              aExpr[k].p = 0;
 
764
              break;
 
765
            }
 
766
            if( pX->op==TK_IN && nColumn==1 ){
 
767
              if( pX->pList ){
 
768
                sqliteVdbeAddOp(v, OP_SetFirst, pX->iTable, brk);
 
769
                pLevel->inOp = OP_SetNext;
 
770
                pLevel->inP1 = pX->iTable;
 
771
                pLevel->inP2 = sqliteVdbeCurrentAddr(v);
 
772
              }else{
 
773
                assert( pX->pSelect );
 
774
                sqliteVdbeAddOp(v, OP_Rewind, pX->iTable, brk);
 
775
                sqliteVdbeAddOp(v, OP_KeyAsData, pX->iTable, 1);
 
776
                pLevel->inP2 = sqliteVdbeAddOp(v, OP_FullKey, pX->iTable, 0);
 
777
                pLevel->inOp = OP_Next;
 
778
                pLevel->inP1 = pX->iTable;
 
779
              }
 
780
              aExpr[k].p = 0;
 
781
              break;
 
782
            }
 
783
          }
 
784
          if( aExpr[k].idxRight==iCur
 
785
             && aExpr[k].p->op==TK_EQ
 
786
             && (aExpr[k].prereqLeft & loopMask)==aExpr[k].prereqLeft
 
787
             && aExpr[k].p->pRight->iColumn==pIdx->aiColumn[j]
 
788
          ){
 
789
            sqliteExprCode(pParse, aExpr[k].p->pLeft);
 
790
            aExpr[k].p = 0;
 
791
            break;
 
792
          }
 
793
        }
 
794
      }
 
795
      pLevel->iMem = pParse->nMem++;
 
796
      cont = pLevel->cont = sqliteVdbeMakeLabel(v);
 
797
      sqliteVdbeAddOp(v, OP_NotNull, -nColumn, sqliteVdbeCurrentAddr(v)+3);
 
798
      sqliteVdbeAddOp(v, OP_Pop, nColumn, 0);
 
799
      sqliteVdbeAddOp(v, OP_Goto, 0, brk);
 
800
      sqliteVdbeAddOp(v, OP_MakeKey, nColumn, 0);
 
801
      sqliteAddIdxKeyType(v, pIdx);
 
802
      if( nColumn==pIdx->nColumn || pLevel->bRev ){
 
803
        sqliteVdbeAddOp(v, OP_MemStore, pLevel->iMem, 0);
 
804
        testOp = OP_IdxGT;
 
805
      }else{
 
806
        sqliteVdbeAddOp(v, OP_Dup, 0, 0);
 
807
        sqliteVdbeAddOp(v, OP_IncrKey, 0, 0);
 
808
        sqliteVdbeAddOp(v, OP_MemStore, pLevel->iMem, 1);
 
809
        testOp = OP_IdxGE;
 
810
      }
 
811
      if( pLevel->bRev ){
 
812
        /* Scan in reverse order */
 
813
        sqliteVdbeAddOp(v, OP_IncrKey, 0, 0);
 
814
        sqliteVdbeAddOp(v, OP_MoveLt, pLevel->iCur, brk);
 
815
        start = sqliteVdbeAddOp(v, OP_MemLoad, pLevel->iMem, 0);
 
816
        sqliteVdbeAddOp(v, OP_IdxLT, pLevel->iCur, brk);
 
817
        pLevel->op = OP_Prev;
 
818
      }else{
 
819
        /* Scan in the forward order */
 
820
        sqliteVdbeAddOp(v, OP_MoveTo, pLevel->iCur, brk);
 
821
        start = sqliteVdbeAddOp(v, OP_MemLoad, pLevel->iMem, 0);
 
822
        sqliteVdbeAddOp(v, testOp, pLevel->iCur, brk);
 
823
        pLevel->op = OP_Next;
 
824
      }
 
825
      sqliteVdbeAddOp(v, OP_RowKey, pLevel->iCur, 0);
 
826
      sqliteVdbeAddOp(v, OP_IdxIsNull, nColumn, cont);
 
827
      sqliteVdbeAddOp(v, OP_IdxRecno, pLevel->iCur, 0);
 
828
      if( i==pTabList->nSrc-1 && pushKey ){
 
829
        haveKey = 1;
 
830
      }else{
 
831
        sqliteVdbeAddOp(v, OP_MoveTo, iCur, 0);
 
832
        haveKey = 0;
 
833
      }
 
834
      pLevel->p1 = pLevel->iCur;
 
835
      pLevel->p2 = start;
 
836
    }else if( i<ARRAYSIZE(iDirectLt) && (iDirectLt[i]>=0 || iDirectGt[i]>=0) ){
 
837
      /* Case 3:  We have an inequality comparison against the ROWID field.
 
838
      */
 
839
      int testOp = OP_Noop;
 
840
      int start;
 
841
 
 
842
      brk = pLevel->brk = sqliteVdbeMakeLabel(v);
 
843
      cont = pLevel->cont = sqliteVdbeMakeLabel(v);
 
844
      if( iDirectGt[i]>=0 ){
 
845
        k = iDirectGt[i];
 
846
        assert( k<nExpr );
 
847
        assert( aExpr[k].p!=0 );
 
848
        assert( aExpr[k].idxLeft==iCur || aExpr[k].idxRight==iCur );
 
849
        if( aExpr[k].idxLeft==iCur ){
 
850
          sqliteExprCode(pParse, aExpr[k].p->pRight);
 
851
        }else{
 
852
          sqliteExprCode(pParse, aExpr[k].p->pLeft);
 
853
        }
 
854
        sqliteVdbeAddOp(v, OP_ForceInt,
 
855
          aExpr[k].p->op==TK_LT || aExpr[k].p->op==TK_GT, brk);
 
856
        sqliteVdbeAddOp(v, OP_MoveTo, iCur, brk);
 
857
        aExpr[k].p = 0;
 
858
      }else{
 
859
        sqliteVdbeAddOp(v, OP_Rewind, iCur, brk);
 
860
      }
 
861
      if( iDirectLt[i]>=0 ){
 
862
        k = iDirectLt[i];
 
863
        assert( k<nExpr );
 
864
        assert( aExpr[k].p!=0 );
 
865
        assert( aExpr[k].idxLeft==iCur || aExpr[k].idxRight==iCur );
 
866
        if( aExpr[k].idxLeft==iCur ){
 
867
          sqliteExprCode(pParse, aExpr[k].p->pRight);
 
868
        }else{
 
869
          sqliteExprCode(pParse, aExpr[k].p->pLeft);
 
870
        }
 
871
        /* sqliteVdbeAddOp(v, OP_MustBeInt, 0, sqliteVdbeCurrentAddr(v)+1); */
 
872
        pLevel->iMem = pParse->nMem++;
 
873
        sqliteVdbeAddOp(v, OP_MemStore, pLevel->iMem, 1);
 
874
        if( aExpr[k].p->op==TK_LT || aExpr[k].p->op==TK_GT ){
 
875
          testOp = OP_Ge;
 
876
        }else{
 
877
          testOp = OP_Gt;
 
878
        }
 
879
        aExpr[k].p = 0;
 
880
      }
 
881
      start = sqliteVdbeCurrentAddr(v);
 
882
      pLevel->op = OP_Next;
 
883
      pLevel->p1 = iCur;
 
884
      pLevel->p2 = start;
 
885
      if( testOp!=OP_Noop ){
 
886
        sqliteVdbeAddOp(v, OP_Recno, iCur, 0);
 
887
        sqliteVdbeAddOp(v, OP_MemLoad, pLevel->iMem, 0);
 
888
        sqliteVdbeAddOp(v, testOp, 0, brk);
 
889
      }
 
890
      haveKey = 0;
 
891
    }else if( pIdx==0 ){
 
892
      /* Case 4:  There is no usable index.  We must do a complete
 
893
      **          scan of the entire database table.
 
894
      */
 
895
      int start;
 
896
 
 
897
      brk = pLevel->brk = sqliteVdbeMakeLabel(v);
 
898
      cont = pLevel->cont = sqliteVdbeMakeLabel(v);
 
899
      sqliteVdbeAddOp(v, OP_Rewind, iCur, brk);
 
900
      start = sqliteVdbeCurrentAddr(v);
 
901
      pLevel->op = OP_Next;
 
902
      pLevel->p1 = iCur;
 
903
      pLevel->p2 = start;
 
904
      haveKey = 0;
 
905
    }else{
 
906
      /* Case 5: The WHERE clause term that refers to the right-most
 
907
      **         column of the index is an inequality.  For example, if
 
908
      **         the index is on (x,y,z) and the WHERE clause is of the
 
909
      **         form "x=5 AND y<10" then this case is used.  Only the
 
910
      **         right-most column can be an inequality - the rest must
 
911
      **         use the "==" operator.
 
912
      **
 
913
      **         This case is also used when there are no WHERE clause
 
914
      **         constraints but an index is selected anyway, in order
 
915
      **         to force the output order to conform to an ORDER BY.
 
916
      */
 
917
      int score = pLevel->score;
 
918
      int nEqColumn = score/8;
 
919
      int start;
 
920
      int leFlag, geFlag;
 
921
      int testOp;
 
922
 
 
923
      /* Evaluate the equality constraints
 
924
      */
 
925
      for(j=0; j<nEqColumn; j++){
 
926
        for(k=0; k<nExpr; k++){
 
927
          if( aExpr[k].p==0 ) continue;
 
928
          if( aExpr[k].idxLeft==iCur
 
929
             && aExpr[k].p->op==TK_EQ
 
930
             && (aExpr[k].prereqRight & loopMask)==aExpr[k].prereqRight 
 
931
             && aExpr[k].p->pLeft->iColumn==pIdx->aiColumn[j]
 
932
          ){
 
933
            sqliteExprCode(pParse, aExpr[k].p->pRight);
 
934
            aExpr[k].p = 0;
 
935
            break;
 
936
          }
 
937
          if( aExpr[k].idxRight==iCur
 
938
             && aExpr[k].p->op==TK_EQ
 
939
             && (aExpr[k].prereqLeft & loopMask)==aExpr[k].prereqLeft
 
940
             && aExpr[k].p->pRight->iColumn==pIdx->aiColumn[j]
 
941
          ){
 
942
            sqliteExprCode(pParse, aExpr[k].p->pLeft);
 
943
            aExpr[k].p = 0;
 
944
            break;
 
945
          }
 
946
        }
 
947
      }
 
948
 
 
949
      /* Duplicate the equality term values because they will all be
 
950
      ** used twice: once to make the termination key and once to make the
 
951
      ** start key.
 
952
      */
 
953
      for(j=0; j<nEqColumn; j++){
 
954
        sqliteVdbeAddOp(v, OP_Dup, nEqColumn-1, 0);
 
955
      }
 
956
 
 
957
      /* Labels for the beginning and end of the loop
 
958
      */
 
959
      cont = pLevel->cont = sqliteVdbeMakeLabel(v);
 
960
      brk = pLevel->brk = sqliteVdbeMakeLabel(v);
 
961
 
 
962
      /* Generate the termination key.  This is the key value that
 
963
      ** will end the search.  There is no termination key if there
 
964
      ** are no equality terms and no "X<..." term.
 
965
      **
 
966
      ** 2002-Dec-04: On a reverse-order scan, the so-called "termination"
 
967
      ** key computed here really ends up being the start key.
 
968
      */
 
969
      if( (score & 1)!=0 ){
 
970
        for(k=0; k<nExpr; k++){
 
971
          Expr *pExpr = aExpr[k].p;
 
972
          if( pExpr==0 ) continue;
 
973
          if( aExpr[k].idxLeft==iCur
 
974
             && (pExpr->op==TK_LT || pExpr->op==TK_LE)
 
975
             && (aExpr[k].prereqRight & loopMask)==aExpr[k].prereqRight 
 
976
             && pExpr->pLeft->iColumn==pIdx->aiColumn[j]
 
977
          ){
 
978
            sqliteExprCode(pParse, pExpr->pRight);
 
979
            leFlag = pExpr->op==TK_LE;
 
980
            aExpr[k].p = 0;
 
981
            break;
 
982
          }
 
983
          if( aExpr[k].idxRight==iCur
 
984
             && (pExpr->op==TK_GT || pExpr->op==TK_GE)
 
985
             && (aExpr[k].prereqLeft & loopMask)==aExpr[k].prereqLeft
 
986
             && pExpr->pRight->iColumn==pIdx->aiColumn[j]
 
987
          ){
 
988
            sqliteExprCode(pParse, pExpr->pLeft);
 
989
            leFlag = pExpr->op==TK_GE;
 
990
            aExpr[k].p = 0;
 
991
            break;
 
992
          }
 
993
        }
 
994
        testOp = OP_IdxGE;
 
995
      }else{
 
996
        testOp = nEqColumn>0 ? OP_IdxGE : OP_Noop;
 
997
        leFlag = 1;
 
998
      }
 
999
      if( testOp!=OP_Noop ){
 
1000
        int nCol = nEqColumn + (score & 1);
 
1001
        pLevel->iMem = pParse->nMem++;
 
1002
        sqliteVdbeAddOp(v, OP_NotNull, -nCol, sqliteVdbeCurrentAddr(v)+3);
 
1003
        sqliteVdbeAddOp(v, OP_Pop, nCol, 0);
 
1004
        sqliteVdbeAddOp(v, OP_Goto, 0, brk);
 
1005
        sqliteVdbeAddOp(v, OP_MakeKey, nCol, 0);
 
1006
        sqliteAddIdxKeyType(v, pIdx);
 
1007
        if( leFlag ){
 
1008
          sqliteVdbeAddOp(v, OP_IncrKey, 0, 0);
 
1009
        }
 
1010
        if( pLevel->bRev ){
 
1011
          sqliteVdbeAddOp(v, OP_MoveLt, pLevel->iCur, brk);
 
1012
        }else{
 
1013
          sqliteVdbeAddOp(v, OP_MemStore, pLevel->iMem, 1);
 
1014
        }
 
1015
      }else if( pLevel->bRev ){
 
1016
        sqliteVdbeAddOp(v, OP_Last, pLevel->iCur, brk);
 
1017
      }
 
1018
 
 
1019
      /* Generate the start key.  This is the key that defines the lower
 
1020
      ** bound on the search.  There is no start key if there are no
 
1021
      ** equality terms and if there is no "X>..." term.  In
 
1022
      ** that case, generate a "Rewind" instruction in place of the
 
1023
      ** start key search.
 
1024
      **
 
1025
      ** 2002-Dec-04: In the case of a reverse-order search, the so-called
 
1026
      ** "start" key really ends up being used as the termination key.
 
1027
      */
 
1028
      if( (score & 2)!=0 ){
 
1029
        for(k=0; k<nExpr; k++){
 
1030
          Expr *pExpr = aExpr[k].p;
 
1031
          if( pExpr==0 ) continue;
 
1032
          if( aExpr[k].idxLeft==iCur
 
1033
             && (pExpr->op==TK_GT || pExpr->op==TK_GE)
 
1034
             && (aExpr[k].prereqRight & loopMask)==aExpr[k].prereqRight 
 
1035
             && pExpr->pLeft->iColumn==pIdx->aiColumn[j]
 
1036
          ){
 
1037
            sqliteExprCode(pParse, pExpr->pRight);
 
1038
            geFlag = pExpr->op==TK_GE;
 
1039
            aExpr[k].p = 0;
 
1040
            break;
 
1041
          }
 
1042
          if( aExpr[k].idxRight==iCur
 
1043
             && (pExpr->op==TK_LT || pExpr->op==TK_LE)
 
1044
             && (aExpr[k].prereqLeft & loopMask)==aExpr[k].prereqLeft
 
1045
             && pExpr->pRight->iColumn==pIdx->aiColumn[j]
 
1046
          ){
 
1047
            sqliteExprCode(pParse, pExpr->pLeft);
 
1048
            geFlag = pExpr->op==TK_LE;
 
1049
            aExpr[k].p = 0;
 
1050
            break;
 
1051
          }
 
1052
        }
 
1053
      }else{
 
1054
        geFlag = 1;
 
1055
      }
 
1056
      if( nEqColumn>0 || (score&2)!=0 ){
 
1057
        int nCol = nEqColumn + ((score&2)!=0);
 
1058
        sqliteVdbeAddOp(v, OP_NotNull, -nCol, sqliteVdbeCurrentAddr(v)+3);
 
1059
        sqliteVdbeAddOp(v, OP_Pop, nCol, 0);
 
1060
        sqliteVdbeAddOp(v, OP_Goto, 0, brk);
 
1061
        sqliteVdbeAddOp(v, OP_MakeKey, nCol, 0);
 
1062
        sqliteAddIdxKeyType(v, pIdx);
 
1063
        if( !geFlag ){
 
1064
          sqliteVdbeAddOp(v, OP_IncrKey, 0, 0);
 
1065
        }
 
1066
        if( pLevel->bRev ){
 
1067
          pLevel->iMem = pParse->nMem++;
 
1068
          sqliteVdbeAddOp(v, OP_MemStore, pLevel->iMem, 1);
 
1069
          testOp = OP_IdxLT;
 
1070
        }else{
 
1071
          sqliteVdbeAddOp(v, OP_MoveTo, pLevel->iCur, brk);
 
1072
        }
 
1073
      }else if( pLevel->bRev ){
 
1074
        testOp = OP_Noop;
 
1075
      }else{
 
1076
        sqliteVdbeAddOp(v, OP_Rewind, pLevel->iCur, brk);
 
1077
      }
 
1078
 
 
1079
      /* Generate the the top of the loop.  If there is a termination
 
1080
      ** key we have to test for that key and abort at the top of the
 
1081
      ** loop.
 
1082
      */
 
1083
      start = sqliteVdbeCurrentAddr(v);
 
1084
      if( testOp!=OP_Noop ){
 
1085
        sqliteVdbeAddOp(v, OP_MemLoad, pLevel->iMem, 0);
 
1086
        sqliteVdbeAddOp(v, testOp, pLevel->iCur, brk);
 
1087
      }
 
1088
      sqliteVdbeAddOp(v, OP_RowKey, pLevel->iCur, 0);
 
1089
      sqliteVdbeAddOp(v, OP_IdxIsNull, nEqColumn + (score & 1), cont);
 
1090
      sqliteVdbeAddOp(v, OP_IdxRecno, pLevel->iCur, 0);
 
1091
      if( i==pTabList->nSrc-1 && pushKey ){
 
1092
        haveKey = 1;
 
1093
      }else{
 
1094
        sqliteVdbeAddOp(v, OP_MoveTo, iCur, 0);
 
1095
        haveKey = 0;
 
1096
      }
 
1097
 
 
1098
      /* Record the instruction used to terminate the loop.
 
1099
      */
 
1100
      pLevel->op = pLevel->bRev ? OP_Prev : OP_Next;
 
1101
      pLevel->p1 = pLevel->iCur;
 
1102
      pLevel->p2 = start;
 
1103
    }
 
1104
    loopMask |= getMask(&maskSet, iCur);
 
1105
 
 
1106
    /* Insert code to test every subexpression that can be completely
 
1107
    ** computed using the current set of tables.
 
1108
    */
 
1109
    for(j=0; j<nExpr; j++){
 
1110
      if( aExpr[j].p==0 ) continue;
 
1111
      if( (aExpr[j].prereqAll & loopMask)!=aExpr[j].prereqAll ) continue;
 
1112
      if( pLevel->iLeftJoin && !ExprHasProperty(aExpr[j].p,EP_FromJoin) ){
 
1113
        continue;
 
1114
      }
 
1115
      if( haveKey ){
 
1116
        haveKey = 0;
 
1117
        sqliteVdbeAddOp(v, OP_MoveTo, iCur, 0);
 
1118
      }
 
1119
      sqliteExprIfFalse(pParse, aExpr[j].p, cont, 1);
 
1120
      aExpr[j].p = 0;
 
1121
    }
 
1122
    brk = cont;
 
1123
 
 
1124
    /* For a LEFT OUTER JOIN, generate code that will record the fact that
 
1125
    ** at least one row of the right table has matched the left table.  
 
1126
    */
 
1127
    if( pLevel->iLeftJoin ){
 
1128
      pLevel->top = sqliteVdbeCurrentAddr(v);
 
1129
      sqliteVdbeAddOp(v, OP_Integer, 1, 0);
 
1130
      sqliteVdbeAddOp(v, OP_MemStore, pLevel->iLeftJoin, 1);
 
1131
      for(j=0; j<nExpr; j++){
 
1132
        if( aExpr[j].p==0 ) continue;
 
1133
        if( (aExpr[j].prereqAll & loopMask)!=aExpr[j].prereqAll ) continue;
 
1134
        if( haveKey ){
 
1135
          /* Cannot happen.  "haveKey" can only be true if pushKey is true
 
1136
          ** an pushKey can only be true for DELETE and UPDATE and there are
 
1137
          ** no outer joins with DELETE and UPDATE.
 
1138
          */
 
1139
          haveKey = 0;
 
1140
          sqliteVdbeAddOp(v, OP_MoveTo, iCur, 0);
 
1141
        }
 
1142
        sqliteExprIfFalse(pParse, aExpr[j].p, cont, 1);
 
1143
        aExpr[j].p = 0;
 
1144
      }
 
1145
    }
 
1146
  }
 
1147
  pWInfo->iContinue = cont;
 
1148
  if( pushKey && !haveKey ){
 
1149
    sqliteVdbeAddOp(v, OP_Recno, pTabList->a[0].iCursor, 0);
 
1150
  }
 
1151
  freeMaskSet(&maskSet);
 
1152
  return pWInfo;
 
1153
}
 
1154
 
 
1155
/*
 
1156
** Generate the end of the WHERE loop.  See comments on 
 
1157
** sqliteWhereBegin() for additional information.
 
1158
*/
 
1159
void sqliteWhereEnd(WhereInfo *pWInfo){
 
1160
  Vdbe *v = pWInfo->pParse->pVdbe;
 
1161
  int i;
 
1162
  WhereLevel *pLevel;
 
1163
  SrcList *pTabList = pWInfo->pTabList;
 
1164
 
 
1165
  for(i=pTabList->nSrc-1; i>=0; i--){
 
1166
    pLevel = &pWInfo->a[i];
 
1167
    sqliteVdbeResolveLabel(v, pLevel->cont);
 
1168
    if( pLevel->op!=OP_Noop ){
 
1169
      sqliteVdbeAddOp(v, pLevel->op, pLevel->p1, pLevel->p2);
 
1170
    }
 
1171
    sqliteVdbeResolveLabel(v, pLevel->brk);
 
1172
    if( pLevel->inOp!=OP_Noop ){
 
1173
      sqliteVdbeAddOp(v, pLevel->inOp, pLevel->inP1, pLevel->inP2);
 
1174
    }
 
1175
    if( pLevel->iLeftJoin ){
 
1176
      int addr;
 
1177
      addr = sqliteVdbeAddOp(v, OP_MemLoad, pLevel->iLeftJoin, 0);
 
1178
      sqliteVdbeAddOp(v, OP_NotNull, 1, addr+4 + (pLevel->iCur>=0));
 
1179
      sqliteVdbeAddOp(v, OP_NullRow, pTabList->a[i].iCursor, 0);
 
1180
      if( pLevel->iCur>=0 ){
 
1181
        sqliteVdbeAddOp(v, OP_NullRow, pLevel->iCur, 0);
 
1182
      }
 
1183
      sqliteVdbeAddOp(v, OP_Goto, 0, pLevel->top);
 
1184
    }
 
1185
  }
 
1186
  sqliteVdbeResolveLabel(v, pWInfo->iBreak);
 
1187
  for(i=0; i<pTabList->nSrc; i++){
 
1188
    Table *pTab = pTabList->a[i].pTab;
 
1189
    assert( pTab!=0 );
 
1190
    if( pTab->isTransient || pTab->pSelect ) continue;
 
1191
    pLevel = &pWInfo->a[i];
 
1192
    sqliteVdbeAddOp(v, OP_Close, pTabList->a[i].iCursor, 0);
 
1193
    if( pLevel->pIdx!=0 ){
 
1194
      sqliteVdbeAddOp(v, OP_Close, pLevel->iCur, 0);
 
1195
    }
 
1196
  }
 
1197
#if 0  /* Never reuse a cursor */
 
1198
  if( pWInfo->pParse->nTab==pWInfo->peakNTab ){
 
1199
    pWInfo->pParse->nTab = pWInfo->savedNTab;
 
1200
  }
 
1201
#endif
 
1202
  sqliteFree(pWInfo);
 
1203
  return;
 
1204
}