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