sqlite3/where.c

   1 /*
   2 ** 2001 September 15
   3 **
   4 ** The author disclaims copyright to this source code.  In place of
   5 ** a legal notice, here is a blessing:
   6 **
   7 **    May you do good and not evil.
   8 **    May you find forgiveness for yourself and forgive others.
   9 **    May you share freely, never taking more than you give.
  10 **
  11 *************************************************************************
  12 ** This module contains C code that generates VDBE code used to process
  13 ** the WHERE clause of SQL statements.  This module is reponsible for
  14 ** generating the code that loops through a table looking for applicable
  15 ** rows.  Indices are selected and used to speed the search when doing
  16 ** so is applicable.  Because this module is responsible for selecting
  17 ** indices, you might also think of this module as the "query optimizer".
  18 **
  19 ** $Id$
  20 */
  21 #include "sqliteInt.h"
  22
  23 /*
  24 ** The query generator uses an array of instances of this structure to
  25 ** help it analyze the subexpressions of the WHERE clause.  Each WHERE
  26 ** clause subexpression is separated from the others by an AND operator.
  27 **
  28 ** The idxLeft and idxRight fields are the VDBE cursor numbers for the
  29 ** table that contains the column that appears on the left-hand and
  30 ** right-hand side of ExprInfo.p.  If either side of ExprInfo.p is
  31 ** something other than a simple column reference, then idxLeft or
  32 ** idxRight are -1.
  33 **
  34 ** It is the VDBE cursor number is the value stored in Expr.iTable
  35 ** when Expr.op==TK_COLUMN and the value stored in SrcList.a[].iCursor.
  36 **
  37 ** prereqLeft, prereqRight, and prereqAll record sets of cursor numbers,
  38 ** but they do so indirectly.  A single ExprMaskSet structure translates
  39 ** cursor number into bits and the translated bit is stored in the prereq
  40 ** fields.  The translation is used in order to maximize the number of
  41 ** bits that will fit in a Bitmask.  The VDBE cursor numbers might be
  42 ** spread out over the non-negative integers.  For example, the cursor
  43 ** numbers might be 3, 8, 9, 10, 20, 23, 41, and 45.  The ExprMaskSet
  44 ** translates these sparse cursor numbers into consecutive integers
  45 ** beginning with 0 in order to make the best possible use of the available
  46 ** bits in the Bitmask.  So, in the example above, the cursor numbers
  47 ** would be mapped into integers 0 through 7.
  48 **
  49 ** prereqLeft tells us every VDBE cursor that is referenced on the
  50 ** left-hand side of ExprInfo.p.  prereqRight does the same for the
  51 ** right-hand side of the expression.  The following identity always
  52 ** holds:
  53 **
  54 **       prereqAll = prereqLeft | prereqRight
  55 **
  56 ** The ExprInfo.indexable field is true if the ExprInfo.p expression
  57 ** is of a form that might control an index.  Indexable expressions
  58 ** look like this:
  59 **
  60 **              <column> <op> <expr>
  61 **
  62 ** Where <column> is a simple column name and <op> is on of the operators
  63 ** that allowedOp() recognizes.
  64 */
  65 typedef struct ExprInfo ExprInfo;
  66 struct ExprInfo {
  67   Expr *p;                /* Pointer to the subexpression */
  68   u8 indexable;           /* True if this subexprssion is usable by an index */
  69   short int idxLeft;      /* p->pLeft is a column in this table number. -1 if
  70                           ** p->pLeft is not the column of any table */
  71   short int idxRight;     /* p->pRight is a column in this table number. -1 if
  72                           ** p->pRight is not the column of any table */
  73   Bitmask prereqLeft;     /* Bitmask of tables referenced by p->pLeft */
  74   Bitmask prereqRight;    /* Bitmask of tables referenced by p->pRight */
  75   Bitmask prereqAll;      /* Bitmask of tables referenced by p */
  76 };
  77
  78 /*
  79 ** An instance of the following structure keeps track of a mapping
  80 ** between VDBE cursor numbers and bits of the bitmasks in ExprInfo.
  81 **
  82 ** The VDBE cursor numbers are small integers contained in
  83 ** SrcList_item.iCursor and Expr.iTable fields.  For any given WHERE
  84 ** clause, the cursor numbers might not begin with 0 and they might
  85 ** contain gaps in the numbering sequence.  But we want to make maximum
  86 ** use of the bits in our bitmasks.  This structure provides a mapping
  87 ** from the sparse cursor numbers into consecutive integers beginning
  88 ** with 0.
  89 **
  90 ** If ExprMaskSet.ix[A]==B it means that The A-th bit of a Bitmask
  91 ** corresponds VDBE cursor number B.  The A-th bit of a bitmask is 1<<A.
  92 **
  93 ** For example, if the WHERE clause expression used these VDBE
  94 ** cursors:  4, 5, 8, 29, 57, 73.  Then the  ExprMaskSet structure
  95 ** would map those cursor numbers into bits 0 through 5.
  96 **
  97 ** Note that the mapping is not necessarily ordered.  In the example
  98 ** above, the mapping might go like this:  4->3, 5->1, 8->2, 29->0,
  99 ** 57->5, 73->4.  Or one of 719 other combinations might be used. It
 100 ** does not really matter.  What is important is that sparse cursor
 101 ** numbers all get mapped into bit numbers that begin with 0 and contain
 102 ** no gaps.
 103 */
 104 typedef struct ExprMaskSet ExprMaskSet;
 105 struct ExprMaskSet {
 106   int n;                        /* Number of assigned cursor values */
 107   int ix[sizeof(Bitmask)*8];    /* Cursor assigned to each bit */
 108 };
 109
 110 /*
 111 ** Determine the number of elements in an array.
 112 */
 113 #define ARRAYSIZE(X)  (sizeof(X)/sizeof(X[0]))
 114
 115 /*
 116 ** This routine identifies subexpressions in the WHERE clause where
 117 ** each subexpression is separate by the AND operator.  aSlot is
 118 ** filled with pointers to the subexpressions.  For example:
 119 **
 120 **    WHERE  a=='hello' AND coalesce(b,11)<10 AND (c+12!=d OR c==22)
 121 **           \________/     \_______________/     \________________/
 122 **            slot[0]            slot[1]               slot[2]
 123 **
 124 ** The original WHERE clause in pExpr is unaltered.  All this routine
 125 ** does is make aSlot[] entries point to substructure within pExpr.
 126 **
 127 ** aSlot[] is an array of subexpressions structures.  There are nSlot
 128 ** spaces left in this array.  This routine finds as many AND-separated
 129 ** subexpressions as it can and puts pointers to those subexpressions
 130 ** into aSlot[] entries.  The return value is the number of slots filled.
 131 */
 132 static int exprSplit(int nSlot, ExprInfo *aSlot, Expr *pExpr){
 133   int cnt = 0;
 134   if( pExpr==0 || nSlot<1 ) return 0;
 135   if( nSlot==1 || pExpr->op!=TK_AND ){
 136     aSlot[0].p = pExpr;
 137     return 1;
 138   }
 139   if( pExpr->pLeft->op!=TK_AND ){
 140     aSlot[0].p = pExpr->pLeft;
 141     cnt = 1 + exprSplit(nSlot-1, &aSlot[1], pExpr->pRight);
 142   }else{
 143     cnt = exprSplit(nSlot, aSlot, pExpr->pLeft);
 144     cnt += exprSplit(nSlot-cnt, &aSlot[cnt], pExpr->pRight);
 145   }
 146   return cnt;
 147 }
 148
 149 /*
 150 ** Initialize an expression mask set
 151 */
 152 #define initMaskSet(P)  memset(P, 0, sizeof(*P))
 153
 154 /*
 155 ** Return the bitmask for the given cursor number.  Return 0 if
 156 ** iCursor is not in the set.
 157 */
 158 static Bitmask getMask(ExprMaskSet *pMaskSet, int iCursor){
 159   int i;
 160   for(i=0; i<pMaskSet->n; i++){
 161     if( pMaskSet->ix[i]==iCursor ){
 162       return ((Bitmask)1)<<i;
 163     }
 164   }
 165   return 0;
 166 }
 167
 168 /*
 169 ** Create a new mask for cursor iCursor.
 170 */
 171 static void createMask(ExprMaskSet *pMaskSet, int iCursor){
 172   if( pMaskSet->n<ARRAYSIZE(pMaskSet->ix) ){
 173     pMaskSet->ix[pMaskSet->n++] = iCursor;
 174   }
 175 }
 176
 177 /*
 178 ** Destroy an expression mask set
 179 */
 180 #define freeMaskSet(P)   /* NO-OP */
 181
 182 /*
 183 ** This routine walks (recursively) an expression tree and generates
 184 ** a bitmask indicating which tables are used in that expression
 185 ** tree.
 186 **
 187 ** In order for this routine to work, the calling function must have
 188 ** previously invoked sqlite3ExprResolveNames() on the expression.  See
 189 ** the header comment on that routine for additional information.
 190 ** The sqlite3ExprResolveNames() routines looks for column names and
 191 ** sets their opcodes to TK_COLUMN and their Expr.iTable fields to
 192 ** the VDBE cursor number of the table.
 193 */
 194 static Bitmask exprListTableUsage(ExprMaskSet *, ExprList *);
 195 static Bitmask exprTableUsage(ExprMaskSet *pMaskSet, Expr *p){
 196   Bitmask mask = 0;
 197   if( p==0 ) return 0;
 198   if( p->op==TK_COLUMN ){
 199     mask = getMask(pMaskSet, p->iTable);
 200     return mask;
 201   }
 202   mask = exprTableUsage(pMaskSet, p->pRight);
 203   mask |= exprTableUsage(pMaskSet, p->pLeft);
 204   mask |= exprListTableUsage(pMaskSet, p->pList);
 205   if( p->pSelect ){
 206     Select *pS = p->pSelect;
 207     mask |= exprListTableUsage(pMaskSet, pS->pEList);
 208     mask |= exprListTableUsage(pMaskSet, pS->pGroupBy);
 209     mask |= exprListTableUsage(pMaskSet, pS->pOrderBy);
 210     mask |= exprTableUsage(pMaskSet, pS->pWhere);
 211     mask |= exprTableUsage(pMaskSet, pS->pHaving);
 212   }
 213   return mask;
 214 }
 215 static Bitmask exprListTableUsage(ExprMaskSet *pMaskSet, ExprList *pList){
 216   int i;
 217   Bitmask mask = 0;
 218   if( pList ){
 219     for(i=0; i<pList->nExpr; i++){
 220       mask |= exprTableUsage(pMaskSet, pList->a[i].pExpr);
 221     }
 222   }
 223   return mask;
 224 }
 225
 226 /*
 227 ** Return TRUE if the given operator is one of the operators that is
 228 ** allowed for an indexable WHERE clause term.  The allowed operators are
 229 ** "=", "<", ">", "<=", ">=", and "IN".
 230 */
 231 static int allowedOp(int op){
 232   assert( TK_GT==TK_LE-1 && TK_LE==TK_LT-1 && TK_LT==TK_GE-1 && TK_EQ==TK_GT-1);
 233   return op==TK_IN || (op>=TK_EQ && op<=TK_GE);
 234 }
 235
 236 /*
 237 ** Swap two objects of type T.
 238 */
 239 #define SWAP(TYPE,A,B) {TYPE t=A; A=B; B=t;}
 240
 241 /*
 242 ** Return the index in the SrcList that uses cursor iCur.  If iCur is
 243 ** used by the first entry in SrcList return 0.  If iCur is used by
 244 ** the second entry return 1.  And so forth.
 245 **
 246 ** SrcList is the set of tables in the FROM clause in the order that
 247 ** they will be processed.  The value returned here gives us an index
 248 ** of which tables will be processed first.
 249 */
 250 static int tableOrder(SrcList *pList, int iCur){
 251   int i;
 252   struct SrcList_item *pItem;
 253   for(i=0, pItem=pList->a; i<pList->nSrc; i++, pItem++){
 254     if( pItem->iCursor==iCur ) return i;
 255   }
 256   return -1;
 257 }
 258
 259 /*
 260 ** The input to this routine is an ExprInfo structure with only the
 261 ** "p" field filled in.  The job of this routine is to analyze the
 262 ** subexpression and populate all the other fields of the ExprInfo
 263 ** structure.
 264 */
 265 static void exprAnalyze(SrcList *pSrc, ExprMaskSet *pMaskSet, ExprInfo *pInfo){
 266   Expr *pExpr = pInfo->p;
 267   pInfo->prereqLeft = exprTableUsage(pMaskSet, pExpr->pLeft);
 268   pInfo->prereqRight = exprTableUsage(pMaskSet, pExpr->pRight);
 269   pInfo->prereqAll = exprTableUsage(pMaskSet, pExpr);
 270   pInfo->indexable = 0;
 271   pInfo->idxLeft = -1;
 272   pInfo->idxRight = -1;
 273   if( allowedOp(pExpr->op) && (pInfo->prereqRight & pInfo->prereqLeft)==0 ){
 274     if( pExpr->pRight && pExpr->pRight->op==TK_COLUMN ){
 275       pInfo->idxRight = pExpr->pRight->iTable;
 276       pInfo->indexable = 1;
 277     }
 278     if( pExpr->pLeft->op==TK_COLUMN ){
 279       pInfo->idxLeft = pExpr->pLeft->iTable;
 280       pInfo->indexable = 1;
 281     }
 282   }
 283   if( pInfo->indexable ){
 284     assert( pInfo->idxLeft!=pInfo->idxRight );
 285
 286     /* We want the expression to be of the form "X = expr", not "expr = X".
 287     ** So flip it over if necessary.  If the expression is "X = Y", then
 288     ** we want Y to come from an earlier table than X.
 289     **
 290     ** The collating sequence rule is to always choose the left expression.
 291     ** So if we do a flip, we also have to move the collating sequence.
 292     */
 293     if( tableOrder(pSrc,pInfo->idxLeft)<tableOrder(pSrc,pInfo->idxRight) ){
 294       assert( pExpr->op!=TK_IN );
 295       SWAP(CollSeq*,pExpr->pRight->pColl,pExpr->pLeft->pColl);
 296       SWAP(Expr*,pExpr->pRight,pExpr->pLeft);
 297       if( pExpr->op>=TK_GT ){
 298         assert( TK_LT==TK_GT+2 );
 299         assert( TK_GE==TK_LE+2 );
 300         assert( TK_GT>TK_EQ );
 301         assert( TK_GT<TK_LE );
 302         assert( pExpr->op>=TK_GT && pExpr->op<=TK_GE );
 303         pExpr->op = ((pExpr->op-TK_GT)^2)+TK_GT;
 304       }
 305       SWAP(unsigned, pInfo->prereqLeft, pInfo->prereqRight);
 306       SWAP(short int, pInfo->idxLeft, pInfo->idxRight);
 307     }
 308   }
 309
 310 }
 311
 312 /*
 313 ** This routine decides if pIdx can be used to satisfy the ORDER BY
 314 ** clause.  If it can, it returns 1.  If pIdx cannot satisfy the
 315 ** ORDER BY clause, this routine returns 0.
 316 **
 317 ** pOrderBy is an ORDER BY clause from a SELECT statement.  pTab is the
 318 ** left-most table in the FROM clause of that same SELECT statement and
 319 ** the table has a cursor number of "base".  pIdx is an index on pTab.
 320 **
 321 ** nEqCol is the number of columns of pIdx that are used as equality
 322 ** constraints.  Any of these columns may be missing from the ORDER BY
 323 ** clause and the match can still be a success.
 324 **
 325 ** If the index is UNIQUE, then the ORDER BY clause is allowed to have
 326 ** additional terms past the end of the index and the match will still
 327 ** be a success.
 328 **
 329 ** All terms of the ORDER BY that match against the index must be either
 330 ** ASC or DESC.  (Terms of the ORDER BY clause past the end of a UNIQUE
 331 ** index do not need to satisfy this constraint.)  The *pbRev value is
 332 ** set to 1 if the ORDER BY clause is all DESC and it is set to 0 if
 333 ** the ORDER BY clause is all ASC.
 334 */
 335 static int isSortingIndex(
 336   Parse *pParse,          /* Parsing context */
 337   Index *pIdx,            /* The index we are testing */
 338   Table *pTab,            /* The table to be sorted */
 339   int base,               /* Cursor number for pTab */
 340   ExprList *pOrderBy,     /* The ORDER BY clause */
 341   int nEqCol,             /* Number of index columns with == constraints */
 342   int *pbRev              /* Set to 1 if ORDER BY is DESC */
 343 ){
 344   int i, j;                    /* Loop counters */
 345   int sortOrder;               /* Which direction we are sorting */
 346   int nTerm;                   /* Number of ORDER BY terms */
 347   struct ExprList_item *pTerm; /* A term of the ORDER BY clause */
 348   sqlite3 *db = pParse->db;
 349
 350   assert( pOrderBy!=0 );
 351   nTerm = pOrderBy->nExpr;
 352   assert( nTerm>0 );
 353
 354   /* Match terms of the ORDER BY clause against columns of
 355   ** the index.
 356   */
 357   for(i=j=0, pTerm=pOrderBy->a; j<nTerm && i<pIdx->nColumn; i++){
 358     Expr *pExpr;       /* The expression of the ORDER BY pTerm */
 359     CollSeq *pColl;    /* The collating sequence of pExpr */
 360
 361     pExpr = pTerm->pExpr;
 362     if( pExpr->op!=TK_COLUMN || pExpr->iTable!=base ){
 363       /* Can not use an index sort on anything that is not a column in the
 364       ** left-most table of the FROM clause */
 365       return 0;
 366     }
 367     pColl = sqlite3ExprCollSeq(pParse, pExpr);
 368     if( !pColl ) pColl = db->pDfltColl;
 369     if( pExpr->iColumn!=pIdx->aiColumn[i] || pColl!=pIdx->keyInfo.aColl[i] ){
 370       /* Term j of the ORDER BY clause does not match column i of the index */
 371       if( i<nEqCol ){
 372         /* If an index column that is constrained by == fails to match an
 373         ** ORDER BY term, that is OK.  Just ignore that column of the index
 374         */
 375         continue;
 376       }else{
 377         /* If an index column fails to match and is not constrained by ==
 378         ** then the index cannot satisfy the ORDER BY constraint.
 379         */
 380         return 0;
 381       }
 382     }
 383     if( i>nEqCol ){
 384       if( pTerm->sortOrder!=sortOrder ){
 385         /* Indices can only be used if all ORDER BY terms past the
 386         ** equality constraints are all either DESC or ASC. */
 387         return 0;
 388       }
 389     }else{
 390       sortOrder = pTerm->sortOrder;
 391     }
 392     j++;
 393     pTerm++;
 394   }
 395
 396   /* The index can be used for sorting if all terms of the ORDER BY clause
 397   ** or covered or if we ran out of index columns and the it is a UNIQUE
 398   ** index.
 399   */
 400   if( j>=nTerm || (i>=pIdx->nColumn && pIdx->onError!=OE_None) ){
 401     *pbRev = sortOrder==SQLITE_SO_DESC;
 402     return 1;
 403   }
 404   return 0;
 405 }
 406
 407 /*
 408 ** Check table to see if the ORDER BY clause in pOrderBy can be satisfied
 409 ** by sorting in order of ROWID.  Return true if so and set *pbRev to be
 410 ** true for reverse ROWID and false for forward ROWID order.
 411 */
 412 static int sortableByRowid(
 413   int base,               /* Cursor number for table to be sorted */
 414   ExprList *pOrderBy,     /* The ORDER BY clause */
 415   int *pbRev              /* Set to 1 if ORDER BY is DESC */
 416 ){
 417   Expr *p;
 418
 419   assert( pOrderBy!=0 );
 420   assert( pOrderBy->nExpr>0 );
 421   p = pOrderBy->a[0].pExpr;
 422   if( p->op==TK_COLUMN && p->iTable==base && p->iColumn==-1 ){
 423     *pbRev = pOrderBy->a[0].sortOrder;
 424     return 1;
 425   }
 426   return 0;
 427 }
 428
 429
 430 /*
 431 ** Disable a term in the WHERE clause.  Except, do not disable the term
 432 ** if it controls a LEFT OUTER JOIN and it did not originate in the ON
 433 ** or USING clause of that join.
 434 **
 435 ** Consider the term t2.z='ok' in the following queries:
 436 **
 437 **   (1)  SELECT * FROM t1 LEFT JOIN t2 ON t1.a=t2.x WHERE t2.z='ok'
 438 **   (2)  SELECT * FROM t1 LEFT JOIN t2 ON t1.a=t2.x AND t2.z='ok'
 439 **   (3)  SELECT * FROM t1, t2 WHERE t1.a=t2.x AND t2.z='ok'
 440 **
 441 ** The t2.z='ok' is disabled in the in (2) because it originates
 442 ** in the ON clause.  The term is disabled in (3) because it is not part
 443 ** of a LEFT OUTER JOIN.  In (1), the term is not disabled.
 444 **
 445 ** Disabling a term causes that term to not be tested in the inner loop
 446 ** of the join.  Disabling is an optimization.  We would get the correct
 447 ** results if nothing were ever disabled, but joins might run a little
 448 ** slower.  The trick is to disable as much as we can without disabling
 449 ** too much.  If we disabled in (1), we'd get the wrong answer.
 450 ** See ticket #813.
 451 */
 452 static void disableTerm(WhereLevel *pLevel, Expr **ppExpr){
 453   Expr *pExpr = *ppExpr;
 454   if( pLevel->iLeftJoin==0 || ExprHasProperty(pExpr, EP_FromJoin) ){
 455     *ppExpr = 0;
 456   }
 457 }
 458
 459 /*
 460 ** Generate code that builds a probe for an index.  Details:
 461 **
 462 **    *  Check the top nColumn entries on the stack.  If any
 463 **       of those entries are NULL, jump immediately to brk,
 464 **       which is the loop exit, since no index entry will match
 465 **       if any part of the key is NULL.
 466 **
 467 **    *  Construct a probe entry from the top nColumn entries in
 468 **       the stack with affinities appropriate for index pIdx.
 469 */
 470 static void buildIndexProbe(Vdbe *v, int nColumn, int brk, Index *pIdx){
 471   sqlite3VdbeAddOp(v, OP_NotNull, -nColumn, sqlite3VdbeCurrentAddr(v)+3);
 472   sqlite3VdbeAddOp(v, OP_Pop, nColumn, 0);
 473   sqlite3VdbeAddOp(v, OP_Goto, 0, brk);
 474   sqlite3VdbeAddOp(v, OP_MakeRecord, nColumn, 0);
 475   sqlite3IndexAffinityStr(v, pIdx);
 476 }
 477
 478 /*
 479 ** Generate code for an equality term of the WHERE clause.  An equality
 480 ** term can be either X=expr  or X IN (...).   pTerm is the X.
 481 */
 482 static void codeEqualityTerm(
 483   Parse *pParse,      /* The parsing context */
 484   ExprInfo *pTerm,    /* The term of the WHERE clause to be coded */
 485   int brk,            /* Jump here to abandon the loop */
 486   WhereLevel *pLevel  /* When level of the FROM clause we are working on */
 487 ){
 488   Expr *pX = pTerm->p;
 489   if( pX->op!=TK_IN ){
 490     assert( pX->op==TK_EQ );
 491     sqlite3ExprCode(pParse, pX->pRight);
 492 #ifndef SQLITE_OMIT_SUBQUERY
 493   }else{
 494     int iTab;
 495     Vdbe *v = pParse->pVdbe;
 496
 497     sqlite3CodeSubselect(pParse, pX);
 498     iTab = pX->iTable;
 499     sqlite3VdbeAddOp(v, OP_Rewind, iTab, brk);
 500     VdbeComment((v, "# %.*s", pX->span.n, pX->span.z));
 501     pLevel->inP2 = sqlite3VdbeAddOp(v, OP_Column, iTab, 0);
 502     pLevel->inOp = OP_Next;
 503     pLevel->inP1 = iTab;
 504 #endif
 505   }
 506   disableTerm(pLevel, &pTerm->p);
 507 }
 508
 509 /*
 510 ** The number of bits in a Bitmask
 511 */
 512 #define BMS  (sizeof(Bitmask)*8-1)
 513
 514
 515 /*
 516 ** Generate the beginning of the loop used for WHERE clause processing.
 517 ** The return value is a pointer to an opaque structure that contains
 518 ** information needed to terminate the loop.  Later, the calling routine
 519 ** should invoke sqlite3WhereEnd() with the return value of this function
 520 ** in order to complete the WHERE clause processing.
 521 **
 522 ** If an error occurs, this routine returns NULL.
 523 **
 524 ** The basic idea is to do a nested loop, one loop for each table in
 525 ** the FROM clause of a select.  (INSERT and UPDATE statements are the
 526 ** same as a SELECT with only a single table in the FROM clause.)  For
 527 ** example, if the SQL is this:
 528 **
 529 **       SELECT * FROM t1, t2, t3 WHERE ...;
 530 **
 531 ** Then the code generated is conceptually like the following:
 532 **
 533 **      foreach row1 in t1 do       \    Code generated
 534 **        foreach row2 in t2 do      |-- by sqlite3WhereBegin()
 535 **          foreach row3 in t3 do   /
 536 **            ...
 537 **          end                     \    Code generated
 538 **        end                        |-- by sqlite3WhereEnd()
 539 **      end                         /
 540 **
 541 ** There are Btree cursors associated with each table.  t1 uses cursor
 542 ** number pTabList->a[0].iCursor.  t2 uses the cursor pTabList->a[1].iCursor.
 543 ** And so forth.  This routine generates code to open those VDBE cursors
 544 ** and sqlite3WhereEnd() generates the code to close them.
 545 **
 546 ** The code that sqlite3WhereBegin() generates leaves the cursors named
 547 ** in pTabList pointing at their appropriate entries.  The [...] code
 548 ** can use OP_Column and OP_Rowid opcodes on these cursors to extract
 549 ** data from the various tables of the loop.
 550 **
 551 ** If the WHERE clause is empty, the foreach loops must each scan their
 552 ** entire tables.  Thus a three-way join is an O(N^3) operation.  But if
 553 ** the tables have indices and there are terms in the WHERE clause that
 554 ** refer to those indices, a complete table scan can be avoided and the
 555 ** code will run much faster.  Most of the work of this routine is checking
 556 ** to see if there are indices that can be used to speed up the loop.
 557 **
 558 ** Terms of the WHERE clause are also used to limit which rows actually
 559 ** make it to the "..." in the middle of the loop.  After each "foreach",
 560 ** terms of the WHERE clause that use only terms in that loop and outer
 561 ** loops are evaluated and if false a jump is made around all subsequent
 562 ** inner loops (or around the "..." if the test occurs within the inner-
 563 ** most loop)
 564 **
 565 ** OUTER JOINS
 566 **
 567 ** An outer join of tables t1 and t2 is conceptally coded as follows:
 568 **
 569 **    foreach row1 in t1 do
 570 **      flag = 0
 571 **      foreach row2 in t2 do
 572 **        start:
 573 **          ...
 574 **          flag = 1
 575 **      end
 576 **      if flag==0 then
 577 **        move the row2 cursor to a null row
 578 **        goto start
 579 **      fi
 580 **    end
 581 **
 582 ** ORDER BY CLAUSE PROCESSING
 583 **
 584 ** *ppOrderBy is a pointer to the ORDER BY clause of a SELECT statement,
 585 ** if there is one.  If there is no ORDER BY clause or if this routine
 586 ** is called from an UPDATE or DELETE statement, then ppOrderBy is NULL.
 587 **
 588 ** If an index can be used so that the natural output order of the table
 589 ** scan is correct for the ORDER BY clause, then that index is used and
 590 ** *ppOrderBy is set to NULL.  This is an optimization that prevents an
 591 ** unnecessary sort of the result set if an index appropriate for the
 592 ** ORDER BY clause already exists.
 593 **
 594 ** If the where clause loops cannot be arranged to provide the correct
 595 ** output order, then the *ppOrderBy is unchanged.
 596 */
 597 WhereInfo *sqlite3WhereBegin(
 598   Parse *pParse,        /* The parser context */
 599   SrcList *pTabList,    /* A list of all tables to be scanned */
 600   Expr *pWhere,         /* The WHERE clause */
 601   ExprList **ppOrderBy  /* An ORDER BY clause, or NULL */
 602 ){
 603   int i;                     /* Loop counter */
 604   WhereInfo *pWInfo;         /* Will become the return value of this function */
 605   Vdbe *v = pParse->pVdbe;   /* The virtual database engine */
 606   int brk, cont = 0;         /* Addresses used during code generation */
 607   int nExpr;           /* Number of subexpressions in the WHERE clause */
 608   Bitmask loopMask;    /* One bit set for each outer loop */
 609   ExprInfo *pTerm;     /* A single term in the WHERE clause; ptr to aExpr[] */
 610   ExprMaskSet maskSet; /* The expression mask set */
 611   int iDirectEq[BMS];  /* Term of the form ROWID==X for the N-th table */
 612   int iDirectLt[BMS];  /* Term of the form ROWID<X or ROWID<=X */
 613   int iDirectGt[BMS];  /* Term of the form ROWID>X or ROWID>=X */
 614   ExprInfo aExpr[101]; /* The WHERE clause is divided into these terms */
 615   struct SrcList_item *pTabItem;  /* A single entry from pTabList */
 616   WhereLevel *pLevel;             /* A single level in the pWInfo list */
 617
 618   /* The number of terms in the FROM clause is limited by the number of
 619   ** bits in a Bitmask
 620   */
 621   if( pTabList->nSrc>sizeof(Bitmask)*8 ){
 622     sqlite3ErrorMsg(pParse, "at most %d tables in a join",
 623        sizeof(Bitmask)*8);
 624     return 0;
 625   }
 626
 627   /* Split the WHERE clause into separate subexpressions where each
 628   ** subexpression is separated by an AND operator.  If the aExpr[]
 629   ** array fills up, the last entry might point to an expression which
 630   ** contains additional unfactored AND operators.
 631   */
 632   initMaskSet(&maskSet);
 633   memset(aExpr, 0, sizeof(aExpr));
 634   nExpr = exprSplit(ARRAYSIZE(aExpr), aExpr, pWhere);
 635   if( nExpr==ARRAYSIZE(aExpr) ){
 636     sqlite3ErrorMsg(pParse, "WHERE clause too complex - no more "
 637        "than %d terms allowed", (int)ARRAYSIZE(aExpr)-1);
 638     return 0;
 639   }
 640
 641   /* Allocate and initialize the WhereInfo structure that will become the
 642   ** return value.
 643   */
 644   pWInfo = sqliteMalloc( sizeof(WhereInfo) + pTabList->nSrc*sizeof(WhereLevel));
 645   if( sqlite3_malloc_failed ){
 646     sqliteFree(pWInfo); /* Avoid leaking memory when malloc fails */
 647     return 0;
 648   }
 649   pWInfo->pParse = pParse;
 650   pWInfo->pTabList = pTabList;
 651   pWInfo->iBreak = sqlite3VdbeMakeLabel(v);
 652
 653   /* Special case: a WHERE clause that is constant.  Evaluate the
 654   ** expression and either jump over all of the code or fall thru.
 655   */
 656   if( pWhere && (pTabList->nSrc==0 || sqlite3ExprIsConstant(pWhere)) ){
 657     sqlite3ExprIfFalse(pParse, pWhere, pWInfo->iBreak, 1);
 658     pWhere = 0;
 659   }
 660
 661   /* Analyze all of the subexpressions.
 662   */
 663   for(i=0; i<pTabList->nSrc; i++){
 664     createMask(&maskSet, pTabList->a[i].iCursor);
 665   }
 666   for(pTerm=aExpr, i=0; i<nExpr; i++, pTerm++){
 667     exprAnalyze(pTabList, &maskSet, pTerm);
 668   }
 669
 670   /* Figure out what index to use (if any) for each nested loop.
 671   ** Make pWInfo->a[i].pIdx point to the index to use for the i-th nested
 672   ** loop where i==0 is the outer loop and i==pTabList->nSrc-1 is the inner
 673   ** loop.
 674   **
 675   ** If terms exist that use the ROWID of any table, then set the
 676   ** iDirectEq[], iDirectLt[], or iDirectGt[] elements for that table
 677   ** to the index of the term containing the ROWID.  We always prefer
 678   ** to use a ROWID which can directly access a table rather than an
 679   ** index which requires reading an index first to get the rowid then
 680   ** doing a second read of the actual database table.
 681   **
 682   ** Actually, if there are more than 32 tables in the join, only the
 683   ** first 32 tables are candidates for indices.  This is (again) due
 684   ** to the limit of 32 bits in an integer bitmask.
 685   */
 686   loopMask = 0;
 687   pTabItem = pTabList->a;
 688   pLevel = pWInfo->a;
 689   for(i=0; i<pTabList->nSrc && i<ARRAYSIZE(iDirectEq); i++,pTabItem++,pLevel++){
 690     int j;
 691     int iCur = pTabItem->iCursor;            /* The cursor for this table */
 692     Bitmask mask = getMask(&maskSet, iCur);  /* Cursor mask for this table */
 693     Table *pTab = pTabItem->pTab;
 694     Index *pIdx;
 695     Index *pBestIdx = 0;
 696     int bestScore = 0;
 697     int bestRev = 0;
 698
 699     /* Check to see if there is an expression that uses only the
 700     ** ROWID field of this table.  For terms of the form ROWID==expr
 701     ** set iDirectEq[i] to the index of the term.  For terms of the
 702     ** form ROWID<expr or ROWID<=expr set iDirectLt[i] to the term index.
 703     ** For terms like ROWID>expr or ROWID>=expr set iDirectGt[i].
 704     **
 705     ** (Added:) Treat ROWID IN expr like ROWID=expr.
 706     */
 707     pLevel->iIdxCur = -1;
 708     iDirectEq[i] = -1;
 709     iDirectLt[i] = -1;
 710     iDirectGt[i] = -1;
 711     for(pTerm=aExpr, j=0; j<nExpr; j++, pTerm++){
 712       Expr *pX = pTerm->p;
 713       if( pTerm->idxLeft==iCur && pX->pLeft->iColumn<0
 714             && (pTerm->prereqRight & loopMask)==pTerm->prereqRight ){
 715         switch( pX->op ){
 716           case TK_IN:
 717           case TK_EQ: iDirectEq[i] = j; break;
 718           case TK_LE:
 719           case TK_LT: iDirectLt[i] = j; break;
 720           case TK_GE:
 721           case TK_GT: iDirectGt[i] = j;  break;
 722         }
 723       }
 724     }
 725
 726     /* If we found a term that tests ROWID with == or IN, that term
 727     ** will be used to locate the rows in the database table.  There
 728     ** is not need to continue into the code below that looks for
 729     ** an index.  We will always use the ROWID over an index.
 730     */
 731     if( iDirectEq[i]>=0 ){
 732       loopMask |= mask;
 733       pLevel->pIdx = 0;
 734       continue;
 735     }
 736
 737     /* Do a search for usable indices.  Leave pBestIdx pointing to
 738     ** the "best" index.  pBestIdx is left set to NULL if no indices
 739     ** are usable.
 740     **
 741     ** The best index is the one with the highest score.  The score
 742     ** for the index is determined as follows.  For each of the
 743     ** left-most terms that is fixed by an equality operator, add
 744     ** 32 to the score.  The right-most term of the index may be
 745     ** constrained by an inequality.  Add 4 if for an "x<..." constraint
 746     ** and add 8 for an "x>..." constraint.  If both constraints
 747     ** are present, add 12.
 748     **
 749     ** If the left-most term of the index uses an IN operator
 750     ** (ex:  "x IN (...)")  then add 16 to the score.
 751     **
 752     ** If an index can be used for sorting, add 2 to the score.
 753     ** If an index contains all the terms of a table that are ever
 754     ** used by any expression in the SQL statement, then add 1 to
 755     ** the score.
 756     **
 757     ** This scoring system is designed so that the score can later be
 758     ** used to determine how the index is used.  If the score&0x1c is 0
 759     ** then all constraints are equalities.  If score&0x4 is not 0 then
 760     ** there is an inequality used as a termination key.  (ex: "x<...")
 761     ** If score&0x8 is not 0 then there is an inequality used as the
 762     ** start key.  (ex: "x>...").  A score or 0x10 is the special case
 763     ** of an IN operator constraint.  (ex:  "x IN ...").
 764     **
 765     ** The IN operator (as in "<expr> IN (...)") is treated the same as
 766     ** an equality comparison except that it can only be used on the
 767     ** left-most column of an index and other terms of the WHERE clause
 768     ** cannot be used in conjunction with the IN operator to help satisfy
 769     ** other columns of the index.
 770     */
 771     for(pIdx=pTab->pIndex; pIdx; pIdx=pIdx->pNext){
 772       Bitmask eqMask = 0;  /* Index columns covered by an x=... term */
 773       Bitmask ltMask = 0;  /* Index columns covered by an x<... term */
 774       Bitmask gtMask = 0;  /* Index columns covered by an x>... term */
 775       Bitmask inMask = 0;  /* Index columns covered by an x IN .. term */
 776       Bitmask m;
 777       int nEq, score, bRev = 0;
 778
 779       if( pIdx->nColumn>sizeof(eqMask)*8 ){
 780         continue;  /* Ignore indices with too many columns to analyze */
 781       }
 782       for(pTerm=aExpr, j=0; j<nExpr; j++, pTerm++){
 783         Expr *pX = pTerm->p;
 784         CollSeq *pColl = sqlite3ExprCollSeq(pParse, pX->pLeft);
 785         if( !pColl && pX->pRight ){
 786           pColl = sqlite3ExprCollSeq(pParse, pX->pRight);
 787         }
 788         if( !pColl ){
 789           pColl = pParse->db->pDfltColl;
 790         }
 791         if( pTerm->idxLeft==iCur
 792              && (pTerm->prereqRight & loopMask)==pTerm->prereqRight ){
 793           int iColumn = pX->pLeft->iColumn;
 794           int k;
 795           char idxaff = iColumn>=0 ? pIdx->pTable->aCol[iColumn].affinity : 0;
 796           for(k=0; k<pIdx->nColumn; k++){
 797             /* If the collating sequences or affinities don't match,
 798             ** ignore this index.  */
 799             if( pColl!=pIdx->keyInfo.aColl[k] ) continue;
 800             if( !sqlite3IndexAffinityOk(pX, idxaff) ) continue;
 801             if( pIdx->aiColumn[k]==iColumn ){
 802               switch( pX->op ){
 803                 case TK_IN: {
 804                   if( k==0 ) inMask |= 1;
 805                   break;
 806                 }
 807                 case TK_EQ: {
 808                   eqMask |= ((Bitmask)1)<<k;
 809                   break;
 810                 }
 811                 case TK_LE:
 812                 case TK_LT: {
 813                   ltMask |= ((Bitmask)1)<<k;
 814                   break;
 815                 }
 816                 case TK_GE:
 817                 case TK_GT: {
 818                   gtMask |= ((Bitmask)1)<<k;
 819                   break;
 820                 }
 821                 default: {
 822                   /* CANT_HAPPEN */
 823                   assert( 0 );
 824                   break;
 825                 }
 826               }
 827               break;
 828             }
 829           }
 830         }
 831       }
 832
 833       /* The following loop ends with nEq set to the number of columns
 834       ** on the left of the index with == constraints.
 835       */
 836       for(nEq=0; nEq<pIdx->nColumn; nEq++){
 837         m = (((Bitmask)1)<<(nEq+1))-1;
 838         if( (m & eqMask)!=m ) break;
 839       }
 840
 841       /* Begin assemblying the score
 842       */
 843       score = nEq*32;   /* Base score is 32 times number of == constraints */
 844       m = ((Bitmask)1)<<nEq;
 845       if( m & ltMask ) score+=4;    /* Increase score for a < constraint */
 846       if( m & gtMask ) score+=8;    /* Increase score for a > constraint */
 847       if( score==0 && inMask ) score = 16; /* Default score for IN constraint */
 848
 849       /* Give bonus points if this index can be used for sorting
 850       */
 851       if( i==0 && score!=16 && ppOrderBy && *ppOrderBy ){
 852         int base = pTabList->a[0].iCursor;
 853         if( isSortingIndex(pParse, pIdx, pTab, base, *ppOrderBy, nEq, &bRev) ){
 854           score += 2;
 855         }
 856       }
 857
 858       /* Check to see if we can get away with using just the index without
 859       ** ever reading the table.  If that is the case, then add one bonus
 860       ** point to the score.
 861       */
 862       if( score && pTabItem->colUsed < (((Bitmask)1)<<(BMS-1)) ){
 863         for(m=0, j=0; j<pIdx->nColumn; j++){
 864           int x = pIdx->aiColumn[j];
 865           if( x<BMS-1 ){
 866             m |= ((Bitmask)1)<<x;
 867           }
 868         }
 869         if( (pTabItem->colUsed & m)==pTabItem->colUsed ){
 870           score++;
 871         }
 872       }
 873
 874       /* If the score for this index is the best we have seen so far, then
 875       ** save it
 876       */
 877       if( score>bestScore ){
 878         pBestIdx = pIdx;
 879         bestScore = score;
 880         bestRev = bRev;
 881       }
 882     }
 883     pLevel->pIdx = pBestIdx;
 884     pLevel->score = bestScore;
 885     pLevel->bRev = bestRev;
 886     loopMask |= mask;
 887     if( pBestIdx ){
 888       pLevel->iIdxCur = pParse->nTab++;
 889     }
 890   }
 891
 892   /* Check to see if the ORDER BY clause is or can be satisfied by the
 893   ** use of an index on the first table.
 894   */
 895   if( ppOrderBy && *ppOrderBy && pTabList->nSrc>0 ){
 896     Index *pIdx;             /* Index derived from the WHERE clause */
 897     Table *pTab;             /* Left-most table in the FROM clause */
 898     int bRev = 0;            /* True to reverse the output order */
 899     int iCur;                /* Btree-cursor that will be used by pTab */
 900     WhereLevel *pLevel0 = &pWInfo->a[0];
 901
 902     pTab = pTabList->a[0].pTab;
 903     pIdx = pLevel0->pIdx;
 904     iCur = pTabList->a[0].iCursor;
 905     if( pIdx==0 && sortableByRowid(iCur, *ppOrderBy, &bRev) ){
 906       /* The ORDER BY clause specifies ROWID order, which is what we
 907       ** were going to be doing anyway...
 908       */
 909       *ppOrderBy = 0;
 910       pLevel0->bRev = bRev;
 911     }else if( pLevel0->score==16 ){
 912       /* If there is already an IN index on the left-most table,
 913       ** it will not give the correct sort order.
 914       ** So, pretend that no suitable index is found.
 915       */
 916     }else if( iDirectEq[0]>=0 || iDirectLt[0]>=0 || iDirectGt[0]>=0 ){
 917       /* If the left-most column is accessed using its ROWID, then do
 918       ** not try to sort by index.  But do delete the ORDER BY clause
 919       ** if it is redundant.
 920       */
 921     }else if( (pLevel0->score&2)!=0 ){
 922       /* The index that was selected for searching will cause rows to
 923       ** appear in sorted order.
 924       */
 925       *ppOrderBy = 0;
 926     }
 927   }
 928
 929   /* Open all tables in the pTabList and any indices selected for
 930   ** searching those tables.
 931   */
 932   sqlite3CodeVerifySchema(pParse, -1); /* Insert the cookie verifier Goto */
 933   pLevel = pWInfo->a;
 934   for(i=0, pTabItem=pTabList->a; i<pTabList->nSrc; i++, pTabItem++, pLevel++){
 935     Table *pTab;
 936     Index *pIx;
 937     int iIdxCur = pLevel->iIdxCur;
 938
 939     pTab = pTabItem->pTab;
 940     if( pTab->isTransient || pTab->pSelect ) continue;
 941     if( (pLevel->score & 1)==0 ){
 942       sqlite3OpenTableForReading(v, pTabItem->iCursor, pTab);
 943     }
 944     pLevel->iTabCur = pTabItem->iCursor;
 945     if( (pIx = pLevel->pIdx)!=0 ){
 946       sqlite3VdbeAddOp(v, OP_Integer, pIx->iDb, 0);
 947       sqlite3VdbeOp3(v, OP_OpenRead, iIdxCur, pIx->tnum,
 948                      (char*)&pIx->keyInfo, P3_KEYINFO);
 949     }
 950     if( (pLevel->score & 1)!=0 ){
 951       sqlite3VdbeAddOp(v, OP_SetNumColumns, iIdxCur, pIx->nColumn+1);
 952     }
 953     sqlite3CodeVerifySchema(pParse, pTab->iDb);
 954   }
 955   pWInfo->iTop = sqlite3VdbeCurrentAddr(v);
 956
 957   /* Generate the code to do the search
 958   */
 959   loopMask = 0;
 960   pLevel = pWInfo->a;
 961   pTabItem = pTabList->a;
 962   for(i=0; i<pTabList->nSrc; i++, pTabItem++, pLevel++){
 963     int j, k;
 964     int iCur = pTabItem->iCursor;  /* The VDBE cursor for the table */
 965     Index *pIdx;       /* The index we will be using */
 966     int iIdxCur;       /* The VDBE cursor for the index */
 967     int omitTable;     /* True if we use the index only */
 968
 969     pIdx = pLevel->pIdx;
 970     iIdxCur = pLevel->iIdxCur;
 971     pLevel->inOp = OP_Noop;
 972
 973     /* Check to see if it is appropriate to omit the use of the table
 974     ** here and use its index instead.
 975     */
 976     omitTable = (pLevel->score&1)!=0;
 977
 978     /* If this is the right table of a LEFT OUTER JOIN, allocate and
 979     ** initialize a memory cell that records if this table matches any
 980     ** row of the left table of the join.
 981     */
 982     if( i>0 && (pTabList->a[i-1].jointype & JT_LEFT)!=0 ){
 983       if( !pParse->nMem ) pParse->nMem++;
 984       pLevel->iLeftJoin = pParse->nMem++;
 985       sqlite3VdbeAddOp(v, OP_Null, 0, 0);
 986       sqlite3VdbeAddOp(v, OP_MemStore, pLevel->iLeftJoin, 1);
 987       VdbeComment((v, "# init LEFT JOIN no-match flag"));
 988     }
 989
 990     if( i<ARRAYSIZE(iDirectEq) && (k = iDirectEq[i])>=0 ){
 991       /* Case 1:  We can directly reference a single row using an
 992       **          equality comparison against the ROWID field.  Or
 993       **          we reference multiple rows using a "rowid IN (...)"
 994       **          construct.
 995       */
 996       assert( k<nExpr );
 997       pTerm = &aExpr[k];
 998       assert( pTerm->p!=0 );
 999       assert( pTerm->idxLeft==iCur );
1000       assert( omitTable==0 );
1001       brk = pLevel->brk = sqlite3VdbeMakeLabel(v);
1002       codeEqualityTerm(pParse, pTerm, brk, pLevel);
1003       cont = pLevel->cont = sqlite3VdbeMakeLabel(v);
1004       sqlite3VdbeAddOp(v, OP_MustBeInt, 1, brk);
1005       sqlite3VdbeAddOp(v, OP_NotExists, iCur, brk);
1006       VdbeComment((v, "pk"));
1007       pLevel->op = OP_Noop;
1008     }else if( pIdx!=0 && pLevel->score>3 && (pLevel->score&0x0c)==0 ){
1009       /* Case 2:  There is an index and all terms of the WHERE clause that
1010       **          refer to the index using the "==" or "IN" operators.
1011       */
1012       int start;
1013       int nColumn = (pLevel->score+16)/32;
1014       brk = pLevel->brk = sqlite3VdbeMakeLabel(v);
1015
1016       /* For each column of the index, find the term of the WHERE clause that
1017       ** constraints that column.  If the WHERE clause term is X=expr, then
1018       ** evaluation expr and leave the result on the stack */
1019       for(j=0; j<nColumn; j++){
1020         for(pTerm=aExpr, k=0; k<nExpr; k++, pTerm++){
1021           Expr *pX = pTerm->p;
1022           if( pX==0 ) continue;
1023           if( pTerm->idxLeft==iCur
1024              && (pTerm->prereqRight & loopMask)==pTerm->prereqRight
1025              && pX->pLeft->iColumn==pIdx->aiColumn[j]
1026              && (pX->op==TK_EQ || pX->op==TK_IN)
1027           ){
1028             char idxaff = pIdx->pTable->aCol[pX->pLeft->iColumn].affinity;
1029             if( sqlite3IndexAffinityOk(pX, idxaff) ){
1030               codeEqualityTerm(pParse, pTerm, brk, pLevel);
1031               break;
1032             }
1033           }
1034         }
1035       }
1036       pLevel->iMem = pParse->nMem++;
1037       cont = pLevel->cont = sqlite3VdbeMakeLabel(v);
1038       buildIndexProbe(v, nColumn, brk, pIdx);
1039       sqlite3VdbeAddOp(v, OP_MemStore, pLevel->iMem, 0);
1040
1041       /* Generate code (1) to move to the first matching element of the table.
1042       ** Then generate code (2) that jumps to "brk" after the cursor is past
1043       ** the last matching element of the table.  The code (1) is executed
1044       ** once to initialize the search, the code (2) is executed before each
1045       ** iteration of the scan to see if the scan has finished. */
1046       if( pLevel->bRev ){
1047         /* Scan in reverse order */
1048         sqlite3VdbeAddOp(v, OP_MoveLe, iIdxCur, brk);
1049         start = sqlite3VdbeAddOp(v, OP_MemLoad, pLevel->iMem, 0);
1050         sqlite3VdbeAddOp(v, OP_IdxLT, iIdxCur, brk);
1051         pLevel->op = OP_Prev;
1052       }else{
1053         /* Scan in the forward order */
1054         sqlite3VdbeAddOp(v, OP_MoveGe, iIdxCur, brk);
1055         start = sqlite3VdbeAddOp(v, OP_MemLoad, pLevel->iMem, 0);
1056         sqlite3VdbeOp3(v, OP_IdxGE, iIdxCur, brk, "+", P3_STATIC);
1057         pLevel->op = OP_Next;
1058       }
1059       sqlite3VdbeAddOp(v, OP_RowKey, iIdxCur, 0);
1060       sqlite3VdbeAddOp(v, OP_IdxIsNull, nColumn, cont);
1061       if( !omitTable ){
1062         sqlite3VdbeAddOp(v, OP_IdxRowid, iIdxCur, 0);
1063         sqlite3VdbeAddOp(v, OP_MoveGe, iCur, 0);
1064       }
1065       pLevel->p1 = iIdxCur;
1066       pLevel->p2 = start;
1067     }else if( i<ARRAYSIZE(iDirectLt) && (iDirectLt[i]>=0 || iDirectGt[i]>=0) ){
1068       /* Case 3:  We have an inequality comparison against the ROWID field.
1069       */
1070       int testOp = OP_Noop;
1071       int start;
1072       int bRev = pLevel->bRev;
1073
1074       assert( omitTable==0 );
1075       brk = pLevel->brk = sqlite3VdbeMakeLabel(v);
1076       cont = pLevel->cont = sqlite3VdbeMakeLabel(v);
1077       if( bRev ){
1078         int t = iDirectGt[i];
1079         iDirectGt[i] = iDirectLt[i];
1080         iDirectLt[i] = t;
1081       }
1082       if( iDirectGt[i]>=0 ){
1083         Expr *pX;
1084         k = iDirectGt[i];
1085         assert( k<nExpr );
1086         pTerm = &aExpr[k];
1087         pX = pTerm->p;
1088         assert( pX!=0 );
1089         assert( pTerm->idxLeft==iCur );
1090         sqlite3ExprCode(pParse, pX->pRight);
1091         sqlite3VdbeAddOp(v, OP_ForceInt, pX->op==TK_LE || pX->op==TK_GT, brk);
1092         sqlite3VdbeAddOp(v, bRev ? OP_MoveLt : OP_MoveGe, iCur, brk);
1093         VdbeComment((v, "pk"));
1094         disableTerm(pLevel, &pTerm->p);
1095       }else{
1096         sqlite3VdbeAddOp(v, bRev ? OP_Last : OP_Rewind, iCur, brk);
1097       }
1098       if( iDirectLt[i]>=0 ){
1099         Expr *pX;
1100         k = iDirectLt[i];
1101         assert( k<nExpr );
1102         pTerm = &aExpr[k];
1103         pX = pTerm->p;
1104         assert( pX!=0 );
1105         assert( pTerm->idxLeft==iCur );
1106         sqlite3ExprCode(pParse, pX->pRight);
1107         pLevel->iMem = pParse->nMem++;
1108         sqlite3VdbeAddOp(v, OP_MemStore, pLevel->iMem, 1);
1109         if( pX->op==TK_LT || pX->op==TK_GT ){
1110           testOp = bRev ? OP_Le : OP_Ge;
1111         }else{
1112           testOp = bRev ? OP_Lt : OP_Gt;
1113         }
1114         disableTerm(pLevel, &pTerm->p);
1115       }
1116       start = sqlite3VdbeCurrentAddr(v);
1117       pLevel->op = bRev ? OP_Prev : OP_Next;
1118       pLevel->p1 = iCur;
1119       pLevel->p2 = start;
1120       if( testOp!=OP_Noop ){
1121         sqlite3VdbeAddOp(v, OP_Rowid, iCur, 0);
1122         sqlite3VdbeAddOp(v, OP_MemLoad, pLevel->iMem, 0);
1123         sqlite3VdbeAddOp(v, testOp, 'n', brk);
1124       }
1125     }else if( pIdx==0 ){
1126       /* Case 4:  There is no usable index.  We must do a complete
1127       **          scan of the entire database table.
1128       */
1129       int start;
1130       int opRewind;
1131
1132       assert( omitTable==0 );
1133       brk = pLevel->brk = sqlite3VdbeMakeLabel(v);
1134       cont = pLevel->cont = sqlite3VdbeMakeLabel(v);
1135       if( pLevel->bRev ){
1136         opRewind = OP_Last;
1137         pLevel->op = OP_Prev;
1138       }else{
1139         opRewind = OP_Rewind;
1140         pLevel->op = OP_Next;
1141       }
1142       sqlite3VdbeAddOp(v, opRewind, iCur, brk);
1143       start = sqlite3VdbeCurrentAddr(v);
1144       pLevel->p1 = iCur;
1145       pLevel->p2 = start;
1146     }else{
1147       /* Case 5: The WHERE clause term that refers to the right-most
1148       **         column of the index is an inequality.  For example, if
1149       **         the index is on (x,y,z) and the WHERE clause is of the
1150       **         form "x=5 AND y<10" then this case is used.  Only the
1151       **         right-most column can be an inequality - the rest must
1152       **         use the "==" operator.
1153       **
1154       **         This case is also used when there are no WHERE clause
1155       **         constraints but an index is selected anyway, in order
1156       **         to force the output order to conform to an ORDER BY.
1157       */
1158       int score = pLevel->score;
1159       int nEqColumn = score/32;
1160       int start;
1161       int leFlag=0, geFlag=0;
1162       int testOp;
1163
1164       /* Evaluate the equality constraints
1165       */
1166       for(j=0; j<nEqColumn; j++){
1167         int iIdxCol = pIdx->aiColumn[j];
1168         for(pTerm=aExpr, k=0; k<nExpr; k++, pTerm++){
1169           Expr *pX = pTerm->p;
1170           if( pX==0 ) continue;
1171           if( pTerm->idxLeft==iCur
1172              && pX->op==TK_EQ
1173              && (pTerm->prereqRight & loopMask)==pTerm->prereqRight
1174              && pX->pLeft->iColumn==iIdxCol
1175           ){
1176             sqlite3ExprCode(pParse, pX->pRight);
1177             disableTerm(pLevel, &pTerm->p);
1178             break;
1179           }
1180         }
1181       }
1182
1183       /* Duplicate the equality term values because they will all be
1184       ** used twice: once to make the termination key and once to make the
1185       ** start key.
1186       */
1187       for(j=0; j<nEqColumn; j++){
1188         sqlite3VdbeAddOp(v, OP_Dup, nEqColumn-1, 0);
1189       }
1190
1191       /* Labels for the beginning and end of the loop
1192       */
1193       cont = pLevel->cont = sqlite3VdbeMakeLabel(v);
1194       brk = pLevel->brk = sqlite3VdbeMakeLabel(v);
1195
1196       /* Generate the termination key.  This is the key value that
1197       ** will end the search.  There is no termination key if there
1198       ** are no equality terms and no "X<..." term.
1199       **
1200       ** 2002-Dec-04: On a reverse-order scan, the so-called "termination"
1201       ** key computed here really ends up being the start key.
1202       */
1203       if( (score & 4)!=0 ){
1204         for(pTerm=aExpr, k=0; k<nExpr; k++, pTerm++){
1205           Expr *pX = pTerm->p;
1206           if( pX==0 ) continue;
1207           if( pTerm->idxLeft==iCur
1208              && (pX->op==TK_LT || pX->op==TK_LE)
1209              && (pTerm->prereqRight & loopMask)==pTerm->prereqRight
1210              && pX->pLeft->iColumn==pIdx->aiColumn[j]
1211           ){
1212             sqlite3ExprCode(pParse, pX->pRight);
1213             leFlag = pX->op==TK_LE;
1214             disableTerm(pLevel, &pTerm->p);
1215             break;
1216           }
1217         }
1218         testOp = OP_IdxGE;
1219       }else{
1220         testOp = nEqColumn>0 ? OP_IdxGE : OP_Noop;
1221         leFlag = 1;
1222       }
1223       if( testOp!=OP_Noop ){
1224         int nCol = nEqColumn + ((score & 4)!=0);
1225         pLevel->iMem = pParse->nMem++;
1226         buildIndexProbe(v, nCol, brk, pIdx);
1227         if( pLevel->bRev ){
1228           int op = leFlag ? OP_MoveLe : OP_MoveLt;
1229           sqlite3VdbeAddOp(v, op, iIdxCur, brk);
1230         }else{
1231           sqlite3VdbeAddOp(v, OP_MemStore, pLevel->iMem, 1);
1232         }
1233       }else if( pLevel->bRev ){
1234         sqlite3VdbeAddOp(v, OP_Last, iIdxCur, brk);
1235       }
1236
1237       /* Generate the start key.  This is the key that defines the lower
1238       ** bound on the search.  There is no start key if there are no
1239       ** equality terms and if there is no "X>..." term.  In
1240       ** that case, generate a "Rewind" instruction in place of the
1241       ** start key search.
1242       **
1243       ** 2002-Dec-04: In the case of a reverse-order search, the so-called
1244       ** "start" key really ends up being used as the termination key.
1245       */
1246       if( (score & 8)!=0 ){
1247         for(pTerm=aExpr, k=0; k<nExpr; k++, pTerm++){
1248           Expr *pX = pTerm->p;
1249           if( pX==0 ) continue;
1250           if( pTerm->idxLeft==iCur
1251              && (pX->op==TK_GT || pX->op==TK_GE)
1252              && (pTerm->prereqRight & loopMask)==pTerm->prereqRight
1253              && pX->pLeft->iColumn==pIdx->aiColumn[j]
1254           ){
1255             sqlite3ExprCode(pParse, pX->pRight);
1256             geFlag = pX->op==TK_GE;
1257             disableTerm(pLevel, &pTerm->p);
1258             break;
1259           }
1260         }
1261       }else{
1262         geFlag = 1;
1263       }
1264       if( nEqColumn>0 || (score&8)!=0 ){
1265         int nCol = nEqColumn + ((score&8)!=0);
1266         buildIndexProbe(v, nCol, brk, pIdx);
1267         if( pLevel->bRev ){
1268           pLevel->iMem = pParse->nMem++;
1269           sqlite3VdbeAddOp(v, OP_MemStore, pLevel->iMem, 1);
1270           testOp = OP_IdxLT;
1271         }else{
1272           int op = geFlag ? OP_MoveGe : OP_MoveGt;
1273           sqlite3VdbeAddOp(v, op, iIdxCur, brk);
1274         }
1275       }else if( pLevel->bRev ){
1276         testOp = OP_Noop;
1277       }else{
1278         sqlite3VdbeAddOp(v, OP_Rewind, iIdxCur, brk);
1279       }
1280
1281       /* Generate the the top of the loop.  If there is a termination
1282       ** key we have to test for that key and abort at the top of the
1283       ** loop.
1284       */
1285       start = sqlite3VdbeCurrentAddr(v);
1286       if( testOp!=OP_Noop ){
1287         sqlite3VdbeAddOp(v, OP_MemLoad, pLevel->iMem, 0);
1288         sqlite3VdbeAddOp(v, testOp, iIdxCur, brk);
1289         if( (leFlag && !pLevel->bRev) || (!geFlag && pLevel->bRev) ){
1290           sqlite3VdbeChangeP3(v, -1, "+", P3_STATIC);
1291         }
1292       }
1293       sqlite3VdbeAddOp(v, OP_RowKey, iIdxCur, 0);
1294       sqlite3VdbeAddOp(v, OP_IdxIsNull, nEqColumn + ((score&4)!=0), cont);
1295       if( !omitTable ){
1296         sqlite3VdbeAddOp(v, OP_IdxRowid, iIdxCur, 0);
1297         sqlite3VdbeAddOp(v, OP_MoveGe, iCur, 0);
1298       }
1299
1300       /* Record the instruction used to terminate the loop.
1301       */
1302       pLevel->op = pLevel->bRev ? OP_Prev : OP_Next;
1303       pLevel->p1 = iIdxCur;
1304       pLevel->p2 = start;
1305     }
1306     loopMask |= getMask(&maskSet, iCur);
1307
1308     /* Insert code to test every subexpression that can be completely
1309     ** computed using the current set of tables.
1310     */
1311     for(pTerm=aExpr, j=0; j<nExpr; j++, pTerm++){
1312       if( pTerm->p==0 ) continue;
1313       if( (pTerm->prereqAll & loopMask)!=pTerm->prereqAll ) continue;
1314       if( pLevel->iLeftJoin && !ExprHasProperty(pTerm->p,EP_FromJoin) ){
1315         continue;
1316       }
1317       sqlite3ExprIfFalse(pParse, pTerm->p, cont, 1);
1318       pTerm->p = 0;
1319     }
1320     brk = cont;
1321
1322     /* For a LEFT OUTER JOIN, generate code that will record the fact that
1323     ** at least one row of the right table has matched the left table.
1324     */
1325     if( pLevel->iLeftJoin ){
1326       pLevel->top = sqlite3VdbeCurrentAddr(v);
1327       sqlite3VdbeAddOp(v, OP_Integer, 1, 0);
1328       sqlite3VdbeAddOp(v, OP_MemStore, pLevel->iLeftJoin, 1);
1329       VdbeComment((v, "# record LEFT JOIN hit"));
1330       for(pTerm=aExpr, j=0; j<nExpr; j++, pTerm++){
1331         if( pTerm->p==0 ) continue;
1332         if( (pTerm->prereqAll & loopMask)!=pTerm->prereqAll ) continue;
1333         sqlite3ExprIfFalse(pParse, pTerm->p, cont, 1);
1334         pTerm->p = 0;
1335       }
1336     }
1337   }
1338   pWInfo->iContinue = cont;
1339   freeMaskSet(&maskSet);
1340   return pWInfo;
1341 }
1342
1343 /*
1344 ** Generate the end of the WHERE loop.  See comments on
1345 ** sqlite3WhereBegin() for additional information.
1346 */
1347 void sqlite3WhereEnd(WhereInfo *pWInfo){
1348   Vdbe *v = pWInfo->pParse->pVdbe;
1349   int i;
1350   WhereLevel *pLevel;
1351   SrcList *pTabList = pWInfo->pTabList;
1352   struct SrcList_item *pTabItem;
1353
1354   /* Generate loop termination code.
1355   */
1356   for(i=pTabList->nSrc-1; i>=0; i--){
1357     pLevel = &pWInfo->a[i];
1358     sqlite3VdbeResolveLabel(v, pLevel->cont);
1359     if( pLevel->op!=OP_Noop ){
1360       sqlite3VdbeAddOp(v, pLevel->op, pLevel->p1, pLevel->p2);
1361     }
1362     sqlite3VdbeResolveLabel(v, pLevel->brk);
1363     if( pLevel->inOp!=OP_Noop ){
1364       sqlite3VdbeAddOp(v, pLevel->inOp, pLevel->inP1, pLevel->inP2);
1365     }
1366     if( pLevel->iLeftJoin ){
1367       int addr;
1368       addr = sqlite3VdbeAddOp(v, OP_MemLoad, pLevel->iLeftJoin, 0);
1369       sqlite3VdbeAddOp(v, OP_NotNull, 1, addr+4 + (pLevel->iIdxCur>=0));
1370       sqlite3VdbeAddOp(v, OP_NullRow, pTabList->a[i].iCursor, 0);
1371       if( pLevel->iIdxCur>=0 ){
1372         sqlite3VdbeAddOp(v, OP_NullRow, pLevel->iIdxCur, 0);
1373       }
1374       sqlite3VdbeAddOp(v, OP_Goto, 0, pLevel->top);
1375     }
1376   }
1377
1378   /* The "break" point is here, just past the end of the outer loop.
1379   ** Set it.
1380   */
1381   sqlite3VdbeResolveLabel(v, pWInfo->iBreak);
1382
1383   /* Close all of the cursors that were opend by sqlite3WhereBegin.
1384   */
1385   pLevel = pWInfo->a;
1386   pTabItem = pTabList->a;
1387   for(i=0; i<pTabList->nSrc; i++, pTabItem++, pLevel++){
1388     Table *pTab = pTabItem->pTab;
1389     assert( pTab!=0 );
1390     if( pTab->isTransient || pTab->pSelect ) continue;
1391     if( (pLevel->score & 1)==0 ){
1392       sqlite3VdbeAddOp(v, OP_Close, pTabItem->iCursor, 0);
1393     }
1394     if( pLevel->pIdx!=0 ){
1395       sqlite3VdbeAddOp(v, OP_Close, pLevel->iIdxCur, 0);
1396     }
1397
1398     /* Make cursor substitutions for cases where we want to use
1399     ** just the index and never reference the table.
1400     **
1401     ** Calls to the code generator in between sqlite3WhereBegin and
1402     ** sqlite3WhereEnd will have created code that references the table
1403     ** directly.  This loop scans all that code looking for opcodes
1404     ** that reference the table and converts them into opcodes that
1405     ** reference the index.
1406     */
1407     if( pLevel->score & 1 ){
1408       int i, j, last;
1409       VdbeOp *pOp;
1410       Index *pIdx = pLevel->pIdx;
1411
1412       assert( pIdx!=0 );
1413       pOp = sqlite3VdbeGetOp(v, pWInfo->iTop);
1414       last = sqlite3VdbeCurrentAddr(v);
1415       for(i=pWInfo->iTop; i<last; i++, pOp++){
1416         if( pOp->p1!=pLevel->iTabCur ) continue;
1417         if( pOp->opcode==OP_Column ){
1418           pOp->p1 = pLevel->iIdxCur;
1419           for(j=0; j<pIdx->nColumn; j++){
1420             if( pOp->p2==pIdx->aiColumn[j] ){
1421               pOp->p2 = j;
1422               break;
1423             }
1424           }
1425         }else if( pOp->opcode==OP_Rowid ){
1426           pOp->p1 = pLevel->iIdxCur;
1427           pOp->opcode = OP_IdxRowid;
1428         }else if( pOp->opcode==OP_NullRow ){
1429           pOp->opcode = OP_Noop;
1430         }
1431       }
1432     }
1433   }
1434
1435   /* Final cleanup
1436   */
1437   sqliteFree(pWInfo);
1438   return;
1439 }