Annotation of embedaddon/php/ext/sqlite/libsqlite/src/where.c, revision 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