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