engine/sqlite/src/where.cpp
changeset 97 3903521a36da
parent 96 87e863f6f840
child 98 5f9e7e14eb11
equal deleted inserted replaced
96:87e863f6f840 97:3903521a36da
     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: where.cpp 1282 2008-11-13 09:31:33Z LarsPson $
       
    20 */
       
    21 #include "sqliteInt.h"
       
    22 
       
    23 /*
       
    24 ** The number of bits in a Bitmask.  "BMS" means "BitMask Size".
       
    25 */
       
    26 #define BMS  (sizeof(Bitmask)*8)
       
    27 
       
    28 /*
       
    29 ** Trace output macros
       
    30 */
       
    31 #if defined(SQLITE_TEST) || defined(SQLITE_DEBUG)
       
    32 int sqlite3_where_trace = 0;
       
    33 # define WHERETRACE(X)  if(sqlite3_where_trace) sqlite3DebugPrintf X
       
    34 #else
       
    35 # define WHERETRACE(X)
       
    36 #endif
       
    37 
       
    38 /* Forward reference
       
    39 */
       
    40 typedef struct WhereClause WhereClause;
       
    41 typedef struct ExprMaskSet ExprMaskSet;
       
    42 
       
    43 /*
       
    44 ** The query generator uses an array of instances of this structure to
       
    45 ** help it analyze the subexpressions of the WHERE clause.  Each WHERE
       
    46 ** clause subexpression is separated from the others by an AND operator.
       
    47 **
       
    48 ** All WhereTerms are collected into a single WhereClause structure.  
       
    49 ** The following identity holds:
       
    50 **
       
    51 **        WhereTerm.pWC->a[WhereTerm.idx] == WhereTerm
       
    52 **
       
    53 ** When a term is of the form:
       
    54 **
       
    55 **              X <op> <expr>
       
    56 **
       
    57 ** where X is a column name and <op> is one of certain operators,
       
    58 ** then WhereTerm.leftCursor and WhereTerm.leftColumn record the
       
    59 ** cursor number and column number for X.  WhereTerm.operator records
       
    60 ** the <op> using a bitmask encoding defined by WO_xxx below.  The
       
    61 ** use of a bitmask encoding for the operator allows us to search
       
    62 ** quickly for terms that match any of several different operators.
       
    63 **
       
    64 ** prereqRight and prereqAll record sets of cursor numbers,
       
    65 ** but they do so indirectly.  A single ExprMaskSet structure translates
       
    66 ** cursor number into bits and the translated bit is stored in the prereq
       
    67 ** fields.  The translation is used in order to maximize the number of
       
    68 ** bits that will fit in a Bitmask.  The VDBE cursor numbers might be
       
    69 ** spread out over the non-negative integers.  For example, the cursor
       
    70 ** numbers might be 3, 8, 9, 10, 20, 23, 41, and 45.  The ExprMaskSet
       
    71 ** translates these sparse cursor numbers into consecutive integers
       
    72 ** beginning with 0 in order to make the best possible use of the available
       
    73 ** bits in the Bitmask.  So, in the example above, the cursor numbers
       
    74 ** would be mapped into integers 0 through 7.
       
    75 */
       
    76 typedef struct WhereTerm WhereTerm;
       
    77 struct WhereTerm {
       
    78   Expr *pExpr;            /* Pointer to the subexpression */
       
    79   i16 iParent;            /* Disable pWC->a[iParent] when this term disabled */
       
    80   i16 leftCursor;         /* Cursor number of X in "X <op> <expr>" */
       
    81   i16 leftColumn;         /* Column number of X in "X <op> <expr>" */
       
    82   u16 eOperator;          /* A WO_xx value describing <op> */
       
    83   u8 flags;               /* Bit flags.  See below */
       
    84   u8 nChild;              /* Number of children that must disable us */
       
    85   WhereClause *pWC;       /* The clause this term is part of */
       
    86   Bitmask prereqRight;    /* Bitmask of tables used by pRight */
       
    87   Bitmask prereqAll;      /* Bitmask of tables referenced by p */
       
    88 };
       
    89 
       
    90 /*
       
    91 ** Allowed values of WhereTerm.flags
       
    92 */
       
    93 #define TERM_DYNAMIC    0x01   /* Need to call sqlite3ExprDelete(pExpr) */
       
    94 #define TERM_VIRTUAL    0x02   /* Added by the optimizer.  Do not code */
       
    95 #define TERM_CODED      0x04   /* This term is already coded */
       
    96 #define TERM_COPIED     0x08   /* Has a child */
       
    97 #define TERM_OR_OK      0x10   /* Used during OR-clause processing */
       
    98 
       
    99 /*
       
   100 ** An instance of the following structure holds all information about a
       
   101 ** WHERE clause.  Mostly this is a container for one or more WhereTerms.
       
   102 */
       
   103 struct WhereClause {
       
   104   Parse *pParse;           /* The parser context */
       
   105   ExprMaskSet *pMaskSet;   /* Mapping of table indices to bitmasks */
       
   106   int nTerm;               /* Number of terms */
       
   107   int nSlot;               /* Number of entries in a[] */
       
   108   WhereTerm *a;            /* Each a[] describes a term of the WHERE cluase */
       
   109   WhereTerm aStatic[10];   /* Initial static space for a[] */
       
   110 };
       
   111 
       
   112 /*
       
   113 ** An instance of the following structure keeps track of a mapping
       
   114 ** between VDBE cursor numbers and bits of the bitmasks in WhereTerm.
       
   115 **
       
   116 ** The VDBE cursor numbers are small integers contained in 
       
   117 ** SrcList_item.iCursor and Expr.iTable fields.  For any given WHERE 
       
   118 ** clause, the cursor numbers might not begin with 0 and they might
       
   119 ** contain gaps in the numbering sequence.  But we want to make maximum
       
   120 ** use of the bits in our bitmasks.  This structure provides a mapping
       
   121 ** from the sparse cursor numbers into consecutive integers beginning
       
   122 ** with 0.
       
   123 **
       
   124 ** If ExprMaskSet.ix[A]==B it means that The A-th bit of a Bitmask
       
   125 ** corresponds VDBE cursor number B.  The A-th bit of a bitmask is 1<<A.
       
   126 **
       
   127 ** For example, if the WHERE clause expression used these VDBE
       
   128 ** cursors:  4, 5, 8, 29, 57, 73.  Then the  ExprMaskSet structure
       
   129 ** would map those cursor numbers into bits 0 through 5.
       
   130 **
       
   131 ** Note that the mapping is not necessarily ordered.  In the example
       
   132 ** above, the mapping might go like this:  4->3, 5->1, 8->2, 29->0,
       
   133 ** 57->5, 73->4.  Or one of 719 other combinations might be used. It
       
   134 ** does not really matter.  What is important is that sparse cursor
       
   135 ** numbers all get mapped into bit numbers that begin with 0 and contain
       
   136 ** no gaps.
       
   137 */
       
   138 struct ExprMaskSet {
       
   139   int n;                        /* Number of assigned cursor values */
       
   140   int ix[sizeof(Bitmask)*8];    /* Cursor assigned to each bit */
       
   141 };
       
   142 
       
   143 
       
   144 /*
       
   145 ** Bitmasks for the operators that indices are able to exploit.  An
       
   146 ** OR-ed combination of these values can be used when searching for
       
   147 ** terms in the where clause.
       
   148 */
       
   149 #define WO_IN     1
       
   150 #define WO_EQ     2
       
   151 #define WO_LT     (WO_EQ<<(TK_LT-TK_EQ))
       
   152 #define WO_LE     (WO_EQ<<(TK_LE-TK_EQ))
       
   153 #define WO_GT     (WO_EQ<<(TK_GT-TK_EQ))
       
   154 #define WO_GE     (WO_EQ<<(TK_GE-TK_EQ))
       
   155 #define WO_MATCH  64
       
   156 #define WO_ISNULL 128
       
   157 
       
   158 /*
       
   159 ** Value for flags returned by bestIndex().  
       
   160 **
       
   161 ** The least significant byte is reserved as a mask for WO_ values above.
       
   162 ** The WhereLevel.flags field is usually set to WO_IN|WO_EQ|WO_ISNULL.
       
   163 ** But if the table is the right table of a left join, WhereLevel.flags
       
   164 ** is set to WO_IN|WO_EQ.  The WhereLevel.flags field can then be used as
       
   165 ** the "op" parameter to findTerm when we are resolving equality constraints.
       
   166 ** ISNULL constraints will then not be used on the right table of a left
       
   167 ** join.  Tickets #2177 and #2189.
       
   168 */
       
   169 #define WHERE_ROWID_EQ     0x000100   /* rowid=EXPR or rowid IN (...) */
       
   170 #define WHERE_ROWID_RANGE  0x000200   /* rowid<EXPR and/or rowid>EXPR */
       
   171 #define WHERE_COLUMN_EQ    0x001000   /* x=EXPR or x IN (...) */
       
   172 #define WHERE_COLUMN_RANGE 0x002000   /* x<EXPR and/or x>EXPR */
       
   173 #define WHERE_COLUMN_IN    0x004000   /* x IN (...) */
       
   174 #define WHERE_TOP_LIMIT    0x010000   /* x<EXPR or x<=EXPR constraint */
       
   175 #define WHERE_BTM_LIMIT    0x020000   /* x>EXPR or x>=EXPR constraint */
       
   176 #define WHERE_IDX_ONLY     0x080000   /* Use index only - omit table */
       
   177 #define WHERE_ORDERBY      0x100000   /* Output will appear in correct order */
       
   178 #define WHERE_REVERSE      0x200000   /* Scan in reverse order */
       
   179 #define WHERE_UNIQUE       0x400000   /* Selects no more than one row */
       
   180 #define WHERE_VIRTUALTABLE 0x800000   /* Use virtual-table processing */
       
   181 
       
   182 /*
       
   183 ** Initialize a preallocated WhereClause structure.
       
   184 */
       
   185 static void whereClauseInit(
       
   186   WhereClause *pWC,        /* The WhereClause to be initialized */
       
   187   Parse *pParse,           /* The parsing context */
       
   188   ExprMaskSet *pMaskSet    /* Mapping from table indices to bitmasks */
       
   189 ){
       
   190   pWC->pParse = pParse;
       
   191   pWC->pMaskSet = pMaskSet;
       
   192   pWC->nTerm = 0;
       
   193   pWC->nSlot = ArraySize(pWC->aStatic);
       
   194   pWC->a = pWC->aStatic;
       
   195 }
       
   196 
       
   197 /*
       
   198 ** Deallocate a WhereClause structure.  The WhereClause structure
       
   199 ** itself is not freed.  This routine is the inverse of whereClauseInit().
       
   200 */
       
   201 static void whereClauseClear(WhereClause *pWC){
       
   202   int i;
       
   203   WhereTerm *a;
       
   204   for(i=pWC->nTerm-1, a=pWC->a; i>=0; i--, a++){
       
   205     if( a->flags & TERM_DYNAMIC ){
       
   206       sqlite3ExprDelete(a->pExpr);
       
   207     }
       
   208   }
       
   209   if( pWC->a!=pWC->aStatic ){
       
   210     sqlite3_free(pWC->a);
       
   211   }
       
   212 }
       
   213 
       
   214 /*
       
   215 ** Add a new entries to the WhereClause structure.  Increase the allocated
       
   216 ** space as necessary.
       
   217 **
       
   218 ** If the flags argument includes TERM_DYNAMIC, then responsibility
       
   219 ** for freeing the expression p is assumed by the WhereClause object.
       
   220 **
       
   221 ** WARNING:  This routine might reallocate the space used to store
       
   222 ** WhereTerms.  All pointers to WhereTerms should be invalided after
       
   223 ** calling this routine.  Such pointers may be reinitialized by referencing
       
   224 ** the pWC->a[] array.
       
   225 */
       
   226 static int whereClauseInsert(WhereClause *pWC, Expr *p, int flags){
       
   227   WhereTerm *pTerm;
       
   228   int idx;
       
   229   if( pWC->nTerm>=pWC->nSlot ){
       
   230     WhereTerm *pOld = pWC->a;
       
   231     pWC->a = (WhereTerm*)sqlite3_malloc( sizeof(pWC->a[0])*pWC->nSlot*2 );
       
   232     if( pWC->a==0 ){
       
   233       pWC->pParse->db->mallocFailed = 1;
       
   234       if( flags & TERM_DYNAMIC ){
       
   235         sqlite3ExprDelete(p);
       
   236       }
       
   237       pWC->a = pOld;
       
   238       return 0;
       
   239     }
       
   240     memcpy(pWC->a, pOld, sizeof(pWC->a[0])*pWC->nTerm);
       
   241     if( pOld!=pWC->aStatic ){
       
   242       sqlite3_free(pOld);
       
   243     }
       
   244     pWC->nSlot *= 2;
       
   245   }
       
   246   pTerm = &pWC->a[idx = pWC->nTerm];
       
   247   pWC->nTerm++;
       
   248   pTerm->pExpr = p;
       
   249   pTerm->flags = flags;
       
   250   pTerm->pWC = pWC;
       
   251   pTerm->iParent = -1;
       
   252   return idx;
       
   253 }
       
   254 
       
   255 /*
       
   256 ** This routine identifies subexpressions in the WHERE clause where
       
   257 ** each subexpression is separated by the AND operator or some other
       
   258 ** operator specified in the op parameter.  The WhereClause structure
       
   259 ** is filled with pointers to subexpressions.  For example:
       
   260 **
       
   261 **    WHERE  a=='hello' AND coalesce(b,11)<10 AND (c+12!=d OR c==22)
       
   262 **           \________/     \_______________/     \________________/
       
   263 **            slot[0]            slot[1]               slot[2]
       
   264 **
       
   265 ** The original WHERE clause in pExpr is unaltered.  All this routine
       
   266 ** does is make slot[] entries point to substructure within pExpr.
       
   267 **
       
   268 ** In the previous sentence and in the diagram, "slot[]" refers to
       
   269 ** the WhereClause.a[] array.  This array grows as needed to contain
       
   270 ** all terms of the WHERE clause.
       
   271 */
       
   272 static void whereSplit(WhereClause *pWC, Expr *pExpr, int op){
       
   273   if( pExpr==0 ) return;
       
   274   if( pExpr->op!=op ){
       
   275     whereClauseInsert(pWC, pExpr, 0);
       
   276   }else{
       
   277     whereSplit(pWC, pExpr->pLeft, op);
       
   278     whereSplit(pWC, pExpr->pRight, op);
       
   279   }
       
   280 }
       
   281 
       
   282 /*
       
   283 ** Initialize an expression mask set
       
   284 */
       
   285 #define initMaskSet(P)  memset(P, 0, sizeof(*P))
       
   286 
       
   287 /*
       
   288 ** Return the bitmask for the given cursor number.  Return 0 if
       
   289 ** iCursor is not in the set.
       
   290 */
       
   291 static Bitmask getMask(ExprMaskSet *pMaskSet, int iCursor){
       
   292   int i;
       
   293   for(i=0; i<pMaskSet->n; i++){
       
   294     if( pMaskSet->ix[i]==iCursor ){
       
   295       return ((Bitmask)1)<<i;
       
   296     }
       
   297   }
       
   298   return 0;
       
   299 }
       
   300 
       
   301 /*
       
   302 ** Create a new mask for cursor iCursor.
       
   303 **
       
   304 ** There is one cursor per table in the FROM clause.  The number of
       
   305 ** tables in the FROM clause is limited by a test early in the
       
   306 ** sqlite3WhereBegin() routine.  So we know that the pMaskSet->ix[]
       
   307 ** array will never overflow.
       
   308 */
       
   309 static void createMask(ExprMaskSet *pMaskSet, int iCursor){
       
   310   assert( pMaskSet->n < ArraySize(pMaskSet->ix) );
       
   311   pMaskSet->ix[pMaskSet->n++] = iCursor;
       
   312 }
       
   313 
       
   314 /*
       
   315 ** This routine walks (recursively) an expression tree and generates
       
   316 ** a bitmask indicating which tables are used in that expression
       
   317 ** tree.
       
   318 **
       
   319 ** In order for this routine to work, the calling function must have
       
   320 ** previously invoked sqlite3ExprResolveNames() on the expression.  See
       
   321 ** the header comment on that routine for additional information.
       
   322 ** The sqlite3ExprResolveNames() routines looks for column names and
       
   323 ** sets their opcodes to TK_COLUMN and their Expr.iTable fields to
       
   324 ** the VDBE cursor number of the table.  This routine just has to
       
   325 ** translate the cursor numbers into bitmask values and OR all
       
   326 ** the bitmasks together.
       
   327 */
       
   328 static Bitmask exprListTableUsage(ExprMaskSet*, ExprList*);
       
   329 static Bitmask exprSelectTableUsage(ExprMaskSet*, Select*);
       
   330 static Bitmask exprTableUsage(ExprMaskSet *pMaskSet, Expr *p){
       
   331   Bitmask mask = 0;
       
   332   if( p==0 ) return 0;
       
   333   if( p->op==TK_COLUMN ){
       
   334     mask = getMask(pMaskSet, p->iTable);
       
   335     return mask;
       
   336   }
       
   337   mask = exprTableUsage(pMaskSet, p->pRight);
       
   338   mask |= exprTableUsage(pMaskSet, p->pLeft);
       
   339   mask |= exprListTableUsage(pMaskSet, p->pList);
       
   340   mask |= exprSelectTableUsage(pMaskSet, p->pSelect);
       
   341   return mask;
       
   342 }
       
   343 static Bitmask exprListTableUsage(ExprMaskSet *pMaskSet, ExprList *pList){
       
   344   int i;
       
   345   Bitmask mask = 0;
       
   346   if( pList ){
       
   347     for(i=0; i<pList->nExpr; i++){
       
   348       mask |= exprTableUsage(pMaskSet, pList->a[i].pExpr);
       
   349     }
       
   350   }
       
   351   return mask;
       
   352 }
       
   353 static Bitmask exprSelectTableUsage(ExprMaskSet *pMaskSet, Select *pS){
       
   354   Bitmask mask = 0;
       
   355   while( pS ){
       
   356     mask |= exprListTableUsage(pMaskSet, pS->pEList);
       
   357     mask |= exprListTableUsage(pMaskSet, pS->pGroupBy);
       
   358     mask |= exprListTableUsage(pMaskSet, pS->pOrderBy);
       
   359     mask |= exprTableUsage(pMaskSet, pS->pWhere);
       
   360     mask |= exprTableUsage(pMaskSet, pS->pHaving);
       
   361     pS = pS->pPrior;
       
   362   }
       
   363   return mask;
       
   364 }
       
   365 
       
   366 /*
       
   367 ** Return TRUE if the given operator is one of the operators that is
       
   368 ** allowed for an indexable WHERE clause term.  The allowed operators are
       
   369 ** "=", "<", ">", "<=", ">=", and "IN".
       
   370 */
       
   371 static int allowedOp(int op){
       
   372   assert( TK_GT>TK_EQ && TK_GT<TK_GE );
       
   373   assert( TK_LT>TK_EQ && TK_LT<TK_GE );
       
   374   assert( TK_LE>TK_EQ && TK_LE<TK_GE );
       
   375   assert( TK_GE==TK_EQ+4 );
       
   376   return op==TK_IN || (op>=TK_EQ && op<=TK_GE) || op==TK_ISNULL;
       
   377 }
       
   378 
       
   379 /*
       
   380 ** Swap two objects of type T.
       
   381 */
       
   382 #define SWAP(TYPE,A,B) {TYPE t=A; A=B; B=t;}
       
   383 
       
   384 /*
       
   385 ** Commute a comparision operator.  Expressions of the form "X op Y"
       
   386 ** are converted into "Y op X".
       
   387 **
       
   388 ** If a collation sequence is associated with either the left or right
       
   389 ** side of the comparison, it remains associated with the same side after
       
   390 ** the commutation. So "Y collate NOCASE op X" becomes 
       
   391 ** "X collate NOCASE op Y". This is because any collation sequence on
       
   392 ** the left hand side of a comparison overrides any collation sequence 
       
   393 ** attached to the right. For the same reason the EP_ExpCollate flag
       
   394 ** is not commuted.
       
   395 */
       
   396 static void exprCommute(Expr *pExpr){
       
   397   u16 expRight = (pExpr->pRight->flags & EP_ExpCollate);
       
   398   u16 expLeft = (pExpr->pLeft->flags & EP_ExpCollate);
       
   399   assert( allowedOp(pExpr->op) && pExpr->op!=TK_IN );
       
   400   SWAP(CollSeq*,pExpr->pRight->pColl,pExpr->pLeft->pColl);
       
   401   pExpr->pRight->flags = (pExpr->pRight->flags & ~EP_ExpCollate) | expLeft;
       
   402   pExpr->pLeft->flags = (pExpr->pLeft->flags & ~EP_ExpCollate) | expRight;
       
   403   SWAP(Expr*,pExpr->pRight,pExpr->pLeft);
       
   404   if( pExpr->op>=TK_GT ){
       
   405     assert( TK_LT==TK_GT+2 );
       
   406     assert( TK_GE==TK_LE+2 );
       
   407     assert( TK_GT>TK_EQ );
       
   408     assert( TK_GT<TK_LE );
       
   409     assert( pExpr->op>=TK_GT && pExpr->op<=TK_GE );
       
   410     pExpr->op = ((pExpr->op-TK_GT)^2)+TK_GT;
       
   411   }
       
   412 }
       
   413 
       
   414 /*
       
   415 ** Translate from TK_xx operator to WO_xx bitmask.
       
   416 */
       
   417 static int operatorMask(int op){
       
   418   int c;
       
   419   assert( allowedOp(op) );
       
   420   if( op==TK_IN ){
       
   421     c = WO_IN;
       
   422   }else if( op==TK_ISNULL ){
       
   423     c = WO_ISNULL;
       
   424   }else{
       
   425     c = WO_EQ<<(op-TK_EQ);
       
   426   }
       
   427   assert( op!=TK_ISNULL || c==WO_ISNULL );
       
   428   assert( op!=TK_IN || c==WO_IN );
       
   429   assert( op!=TK_EQ || c==WO_EQ );
       
   430   assert( op!=TK_LT || c==WO_LT );
       
   431   assert( op!=TK_LE || c==WO_LE );
       
   432   assert( op!=TK_GT || c==WO_GT );
       
   433   assert( op!=TK_GE || c==WO_GE );
       
   434   return c;
       
   435 }
       
   436 
       
   437 /*
       
   438 ** Search for a term in the WHERE clause that is of the form "X <op> <expr>"
       
   439 ** where X is a reference to the iColumn of table iCur and <op> is one of
       
   440 ** the WO_xx operator codes specified by the op parameter.
       
   441 ** Return a pointer to the term.  Return 0 if not found.
       
   442 */
       
   443 static WhereTerm *findTerm(
       
   444   WhereClause *pWC,     /* The WHERE clause to be searched */
       
   445   int iCur,             /* Cursor number of LHS */
       
   446   int iColumn,          /* Column number of LHS */
       
   447   Bitmask notReady,     /* RHS must not overlap with this mask */
       
   448   u16 op,               /* Mask of WO_xx values describing operator */
       
   449   Index *pIdx           /* Must be compatible with this index, if not NULL */
       
   450 ){
       
   451   WhereTerm *pTerm;
       
   452   int k;
       
   453   for(pTerm=pWC->a, k=pWC->nTerm; k; k--, pTerm++){
       
   454     if( pTerm->leftCursor==iCur
       
   455        && (pTerm->prereqRight & notReady)==0
       
   456        && pTerm->leftColumn==iColumn
       
   457        && (pTerm->eOperator & op)!=0
       
   458     ){
       
   459       if( iCur>=0 && pIdx && pTerm->eOperator!=WO_ISNULL ){
       
   460         Expr *pX = pTerm->pExpr;
       
   461         CollSeq *pColl;
       
   462         char idxaff;
       
   463         int j;
       
   464         Parse *pParse = pWC->pParse;
       
   465 
       
   466         idxaff = pIdx->pTable->aCol[iColumn].affinity;
       
   467         if( !sqlite3IndexAffinityOk(pX, idxaff) ) continue;
       
   468 
       
   469         /* Figure out the collation sequence required from an index for
       
   470         ** it to be useful for optimising expression pX. Store this
       
   471         ** value in variable pColl.
       
   472         */
       
   473         assert(pX->pLeft);
       
   474         pColl = sqlite3BinaryCompareCollSeq(pParse, pX->pLeft, pX->pRight);
       
   475         if( !pColl ){
       
   476           pColl = pParse->db->pDfltColl;
       
   477         }
       
   478 
       
   479         for(j=0; j<pIdx->nColumn && pIdx->aiColumn[j]!=iColumn; j++){}
       
   480         assert( j<pIdx->nColumn );
       
   481         if( sqlite3StrICmp(pColl->zName, pIdx->azColl[j]) ) continue;
       
   482       }
       
   483       return pTerm;
       
   484     }
       
   485   }
       
   486   return 0;
       
   487 }
       
   488 
       
   489 /* Forward reference */
       
   490 static void exprAnalyze(SrcList*, WhereClause*, int);
       
   491 
       
   492 /*
       
   493 ** Call exprAnalyze on all terms in a WHERE clause.  
       
   494 **
       
   495 **
       
   496 */
       
   497 static void exprAnalyzeAll(
       
   498   SrcList *pTabList,       /* the FROM clause */
       
   499   WhereClause *pWC         /* the WHERE clause to be analyzed */
       
   500 ){
       
   501   int i;
       
   502   for(i=pWC->nTerm-1; i>=0; i--){
       
   503     exprAnalyze(pTabList, pWC, i);
       
   504   }
       
   505 }
       
   506 
       
   507 #ifndef SQLITE_OMIT_LIKE_OPTIMIZATION
       
   508 /*
       
   509 ** Check to see if the given expression is a LIKE or GLOB operator that
       
   510 ** can be optimized using inequality constraints.  Return TRUE if it is
       
   511 ** so and false if not.
       
   512 **
       
   513 ** In order for the operator to be optimizible, the RHS must be a string
       
   514 ** literal that does not begin with a wildcard.  
       
   515 */
       
   516 static int isLikeOrGlob(
       
   517   sqlite3 *db,      /* The database */
       
   518   Expr *pExpr,      /* Test this expression */
       
   519   int *pnPattern,   /* Number of non-wildcard prefix characters */
       
   520   int *pisComplete  /* True if the only wildcard is % in the last character */
       
   521 ){
       
   522   const char *z;
       
   523   Expr *pRight, *pLeft;
       
   524   ExprList *pList;
       
   525   int c, cnt;
       
   526   int noCase;
       
   527   char wc[3];
       
   528   CollSeq *pColl;
       
   529 
       
   530   if( !sqlite3IsLikeFunction(db, pExpr, &noCase, wc) ){
       
   531     return 0;
       
   532   }
       
   533   pList = pExpr->pList;
       
   534   pRight = pList->a[0].pExpr;
       
   535   if( pRight->op!=TK_STRING ){
       
   536     return 0;
       
   537   }
       
   538   pLeft = pList->a[1].pExpr;
       
   539   if( pLeft->op!=TK_COLUMN ){
       
   540     return 0;
       
   541   }
       
   542   pColl = pLeft->pColl;
       
   543   if( pColl==0 ){
       
   544     /* TODO: Coverage testing doesn't get this case. Is it actually possible
       
   545     ** for an expression of type TK_COLUMN to not have an assigned collation 
       
   546     ** sequence at this point?
       
   547     */
       
   548     pColl = db->pDfltColl;
       
   549   }
       
   550   if( (pColl->type!=SQLITE_COLL_BINARY || noCase) &&
       
   551       (pColl->type!=SQLITE_COLL_NOCASE || !noCase) ){
       
   552     return 0;
       
   553   }
       
   554   sqlite3DequoteExpr(db, pRight);
       
   555   z = (char *)pRight->token.z;
       
   556   cnt = 0;
       
   557   if( z ){
       
   558     while( (c=z[cnt])!=0 && c!=wc[0] && c!=wc[1] && c!=wc[2] ){ cnt++; }
       
   559   }
       
   560   if( cnt==0 || 255==(u8)z[cnt] ){
       
   561     return 0;
       
   562   }
       
   563   *pisComplete = z[cnt]==wc[0] && z[cnt+1]==0;
       
   564   *pnPattern = cnt;
       
   565   return 1;
       
   566 }
       
   567 #endif /* SQLITE_OMIT_LIKE_OPTIMIZATION */
       
   568 
       
   569 
       
   570 #ifndef SQLITE_OMIT_VIRTUALTABLE
       
   571 /*
       
   572 ** Check to see if the given expression is of the form
       
   573 **
       
   574 **         column MATCH expr
       
   575 **
       
   576 ** If it is then return TRUE.  If not, return FALSE.
       
   577 */
       
   578 static int isMatchOfColumn(
       
   579   Expr *pExpr      /* Test this expression */
       
   580 ){
       
   581   ExprList *pList;
       
   582 
       
   583   if( pExpr->op!=TK_FUNCTION ){
       
   584     return 0;
       
   585   }
       
   586   if( pExpr->token.n!=5 ||
       
   587        sqlite3StrNICmp((const char*)pExpr->token.z,"match",5)!=0 ){
       
   588     return 0;
       
   589   }
       
   590   pList = pExpr->pList;
       
   591   if( pList->nExpr!=2 ){
       
   592     return 0;
       
   593   }
       
   594   if( pList->a[1].pExpr->op != TK_COLUMN ){
       
   595     return 0;
       
   596   }
       
   597   return 1;
       
   598 }
       
   599 #endif /* SQLITE_OMIT_VIRTUALTABLE */
       
   600 
       
   601 /*
       
   602 ** If the pBase expression originated in the ON or USING clause of
       
   603 ** a join, then transfer the appropriate markings over to derived.
       
   604 */
       
   605 static void transferJoinMarkings(Expr *pDerived, Expr *pBase){
       
   606   pDerived->flags |= pBase->flags & EP_FromJoin;
       
   607   pDerived->iRightJoinTable = pBase->iRightJoinTable;
       
   608 }
       
   609 
       
   610 #if !defined(SQLITE_OMIT_OR_OPTIMIZATION) && !defined(SQLITE_OMIT_SUBQUERY)
       
   611 /*
       
   612 ** Return TRUE if the given term of an OR clause can be converted
       
   613 ** into an IN clause.  The iCursor and iColumn define the left-hand
       
   614 ** side of the IN clause.
       
   615 **
       
   616 ** The context is that we have multiple OR-connected equality terms
       
   617 ** like this:
       
   618 **
       
   619 **           a=<expr1> OR  a=<expr2> OR b=<expr3>  OR ...
       
   620 **
       
   621 ** The pOrTerm input to this routine corresponds to a single term of
       
   622 ** this OR clause.  In order for the term to be a condidate for
       
   623 ** conversion to an IN operator, the following must be true:
       
   624 **
       
   625 **     *  The left-hand side of the term must be the column which
       
   626 **        is identified by iCursor and iColumn.
       
   627 **
       
   628 **     *  If the right-hand side is also a column, then the affinities
       
   629 **        of both right and left sides must be such that no type
       
   630 **        conversions are required on the right.  (Ticket #2249)
       
   631 **
       
   632 ** If both of these conditions are true, then return true.  Otherwise
       
   633 ** return false.
       
   634 */
       
   635 static int orTermIsOptCandidate(WhereTerm *pOrTerm, int iCursor, int iColumn){
       
   636   int affLeft, affRight;
       
   637   assert( pOrTerm->eOperator==WO_EQ );
       
   638   if( pOrTerm->leftCursor!=iCursor ){
       
   639     return 0;
       
   640   }
       
   641   if( pOrTerm->leftColumn!=iColumn ){
       
   642     return 0;
       
   643   }
       
   644   affRight = sqlite3ExprAffinity(pOrTerm->pExpr->pRight);
       
   645   if( affRight==0 ){
       
   646     return 1;
       
   647   }
       
   648   affLeft = sqlite3ExprAffinity(pOrTerm->pExpr->pLeft);
       
   649   if( affRight!=affLeft ){
       
   650     return 0;
       
   651   }
       
   652   return 1;
       
   653 }
       
   654 
       
   655 /*
       
   656 ** Return true if the given term of an OR clause can be ignored during
       
   657 ** a check to make sure all OR terms are candidates for optimization.
       
   658 ** In other words, return true if a call to the orTermIsOptCandidate()
       
   659 ** above returned false but it is not necessary to disqualify the
       
   660 ** optimization.
       
   661 **
       
   662 ** Suppose the original OR phrase was this:
       
   663 **
       
   664 **           a=4  OR  a=11  OR  a=b
       
   665 **
       
   666 ** During analysis, the third term gets flipped around and duplicate
       
   667 ** so that we are left with this:
       
   668 **
       
   669 **           a=4  OR  a=11  OR  a=b  OR  b=a
       
   670 **
       
   671 ** Since the last two terms are duplicates, only one of them
       
   672 ** has to qualify in order for the whole phrase to qualify.  When
       
   673 ** this routine is called, we know that pOrTerm did not qualify.
       
   674 ** This routine merely checks to see if pOrTerm has a duplicate that
       
   675 ** might qualify.  If there is a duplicate that has not yet been
       
   676 ** disqualified, then return true.  If there are no duplicates, or
       
   677 ** the duplicate has also been disqualifed, return false.
       
   678 */
       
   679 static int orTermHasOkDuplicate(WhereClause *pOr, WhereTerm *pOrTerm){
       
   680   if( pOrTerm->flags & TERM_COPIED ){
       
   681     /* This is the original term.  The duplicate is to the left had
       
   682     ** has not yet been analyzed and thus has not yet been disqualified. */
       
   683     return 1;
       
   684   }
       
   685   if( (pOrTerm->flags & TERM_VIRTUAL)!=0
       
   686      && (pOr->a[pOrTerm->iParent].flags & TERM_OR_OK)!=0 ){
       
   687     /* This is a duplicate term.  The original qualified so this one
       
   688     ** does not have to. */
       
   689     return 1;
       
   690   }
       
   691   /* This is either a singleton term or else it is a duplicate for
       
   692   ** which the original did not qualify.  Either way we are done for. */
       
   693   return 0;
       
   694 }
       
   695 #endif /* !SQLITE_OMIT_OR_OPTIMIZATION && !SQLITE_OMIT_SUBQUERY */
       
   696 
       
   697 /*
       
   698 ** The input to this routine is an WhereTerm structure with only the
       
   699 ** "pExpr" field filled in.  The job of this routine is to analyze the
       
   700 ** subexpression and populate all the other fields of the WhereTerm
       
   701 ** structure.
       
   702 **
       
   703 ** If the expression is of the form "<expr> <op> X" it gets commuted
       
   704 ** to the standard form of "X <op> <expr>".  If the expression is of
       
   705 ** the form "X <op> Y" where both X and Y are columns, then the original
       
   706 ** expression is unchanged and a new virtual expression of the form
       
   707 ** "Y <op> X" is added to the WHERE clause and analyzed separately.
       
   708 */
       
   709 static void exprAnalyze(
       
   710   SrcList *pSrc,            /* the FROM clause */
       
   711   WhereClause *pWC,         /* the WHERE clause */
       
   712   int idxTerm               /* Index of the term to be analyzed */
       
   713 ){
       
   714   WhereTerm *pTerm;
       
   715   ExprMaskSet *pMaskSet;
       
   716   Expr *pExpr;
       
   717   Bitmask prereqLeft;
       
   718   Bitmask prereqAll;
       
   719   int nPattern;
       
   720   int isComplete;
       
   721   int op;
       
   722   Parse *pParse = pWC->pParse;
       
   723   sqlite3 *db = pParse->db;
       
   724 
       
   725   if( db->mallocFailed ){
       
   726     return;
       
   727   }
       
   728   pTerm = &pWC->a[idxTerm];
       
   729   pMaskSet = pWC->pMaskSet;
       
   730   pExpr = pTerm->pExpr;
       
   731   prereqLeft = exprTableUsage(pMaskSet, pExpr->pLeft);
       
   732   op = pExpr->op;
       
   733   if( op==TK_IN ){
       
   734     assert( pExpr->pRight==0 );
       
   735     pTerm->prereqRight = exprListTableUsage(pMaskSet, pExpr->pList)
       
   736                           | exprSelectTableUsage(pMaskSet, pExpr->pSelect);
       
   737   }else if( op==TK_ISNULL ){
       
   738     pTerm->prereqRight = 0;
       
   739   }else{
       
   740     pTerm->prereqRight = exprTableUsage(pMaskSet, pExpr->pRight);
       
   741   }
       
   742   prereqAll = exprTableUsage(pMaskSet, pExpr);
       
   743   if( ExprHasProperty(pExpr, EP_FromJoin) ){
       
   744     prereqAll |= getMask(pMaskSet, pExpr->iRightJoinTable);
       
   745   }
       
   746   pTerm->prereqAll = prereqAll;
       
   747   pTerm->leftCursor = -1;
       
   748   pTerm->iParent = -1;
       
   749   pTerm->eOperator = 0;
       
   750   if( allowedOp(op) && (pTerm->prereqRight & prereqLeft)==0 ){
       
   751     Expr *pLeft = pExpr->pLeft;
       
   752     Expr *pRight = pExpr->pRight;
       
   753     if( pLeft->op==TK_COLUMN ){
       
   754       pTerm->leftCursor = pLeft->iTable;
       
   755       pTerm->leftColumn = pLeft->iColumn;
       
   756       pTerm->eOperator = operatorMask(op);
       
   757     }
       
   758     if( pRight && pRight->op==TK_COLUMN ){
       
   759       WhereTerm *pNew;
       
   760       Expr *pDup;
       
   761       if( pTerm->leftCursor>=0 ){
       
   762         int idxNew;
       
   763         pDup = sqlite3ExprDup(db, pExpr);
       
   764         if( db->mallocFailed ){
       
   765           sqlite3ExprDelete(pDup);
       
   766           return;
       
   767         }
       
   768         idxNew = whereClauseInsert(pWC, pDup, TERM_VIRTUAL|TERM_DYNAMIC);
       
   769         if( idxNew==0 ) return;
       
   770         pNew = &pWC->a[idxNew];
       
   771         pNew->iParent = idxTerm;
       
   772         pTerm = &pWC->a[idxTerm];
       
   773         pTerm->nChild = 1;
       
   774         pTerm->flags |= TERM_COPIED;
       
   775       }else{
       
   776         pDup = pExpr;
       
   777         pNew = pTerm;
       
   778       }
       
   779       exprCommute(pDup);
       
   780       pLeft = pDup->pLeft;
       
   781       pNew->leftCursor = pLeft->iTable;
       
   782       pNew->leftColumn = pLeft->iColumn;
       
   783       pNew->prereqRight = prereqLeft;
       
   784       pNew->prereqAll = prereqAll;
       
   785       pNew->eOperator = operatorMask(pDup->op);
       
   786     }
       
   787   }
       
   788 
       
   789 #ifndef SQLITE_OMIT_BETWEEN_OPTIMIZATION
       
   790   /* If a term is the BETWEEN operator, create two new virtual terms
       
   791   ** that define the range that the BETWEEN implements.
       
   792   */
       
   793   else if( pExpr->op==TK_BETWEEN ){
       
   794     ExprList *pList = pExpr->pList;
       
   795     int i;
       
   796     static const u8 ops[] = {TK_GE, TK_LE};
       
   797     assert( pList!=0 );
       
   798     assert( pList->nExpr==2 );
       
   799     for(i=0; i<2; i++){
       
   800       Expr *pNewExpr;
       
   801       int idxNew;
       
   802       pNewExpr = sqlite3Expr(db, ops[i], sqlite3ExprDup(db, pExpr->pLeft),
       
   803                              sqlite3ExprDup(db, pList->a[i].pExpr), 0);
       
   804       idxNew = whereClauseInsert(pWC, pNewExpr, TERM_VIRTUAL|TERM_DYNAMIC);
       
   805       exprAnalyze(pSrc, pWC, idxNew);
       
   806       pTerm = &pWC->a[idxTerm];
       
   807       pWC->a[idxNew].iParent = idxTerm;
       
   808     }
       
   809     pTerm->nChild = 2;
       
   810   }
       
   811 #endif /* SQLITE_OMIT_BETWEEN_OPTIMIZATION */
       
   812 
       
   813 #if !defined(SQLITE_OMIT_OR_OPTIMIZATION) && !defined(SQLITE_OMIT_SUBQUERY)
       
   814   /* Attempt to convert OR-connected terms into an IN operator so that
       
   815   ** they can make use of indices.  Example:
       
   816   **
       
   817   **      x = expr1  OR  expr2 = x  OR  x = expr3
       
   818   **
       
   819   ** is converted into
       
   820   **
       
   821   **      x IN (expr1,expr2,expr3)
       
   822   **
       
   823   ** This optimization must be omitted if OMIT_SUBQUERY is defined because
       
   824   ** the compiler for the the IN operator is part of sub-queries.
       
   825   */
       
   826   else if( pExpr->op==TK_OR ){
       
   827     int ok;
       
   828     int i, j;
       
   829     int iColumn, iCursor;
       
   830     WhereClause sOr;
       
   831     WhereTerm *pOrTerm;
       
   832 
       
   833     assert( (pTerm->flags & TERM_DYNAMIC)==0 );
       
   834     whereClauseInit(&sOr, pWC->pParse, pMaskSet);
       
   835     whereSplit(&sOr, pExpr, TK_OR);
       
   836     exprAnalyzeAll(pSrc, &sOr);
       
   837     assert( sOr.nTerm>=2 );
       
   838     j = 0;
       
   839     do{
       
   840       assert( j<sOr.nTerm );
       
   841       iColumn = sOr.a[j].leftColumn;
       
   842       iCursor = sOr.a[j].leftCursor;
       
   843       ok = iCursor>=0;
       
   844       for(i=sOr.nTerm-1, pOrTerm=sOr.a; i>=0 && ok; i--, pOrTerm++){
       
   845         if( pOrTerm->eOperator!=WO_EQ ){
       
   846           goto or_not_possible;
       
   847         }
       
   848         if( orTermIsOptCandidate(pOrTerm, iCursor, iColumn) ){
       
   849           pOrTerm->flags |= TERM_OR_OK;
       
   850         }else if( orTermHasOkDuplicate(&sOr, pOrTerm) ){
       
   851           pOrTerm->flags &= ~TERM_OR_OK;
       
   852         }else{
       
   853           ok = 0;
       
   854         }
       
   855       }
       
   856     }while( !ok && (sOr.a[j++].flags & TERM_COPIED)!=0 && j<2 );
       
   857     if( ok ){
       
   858       ExprList *pList = 0;
       
   859       Expr *pNew, *pDup;
       
   860       Expr *pLeft = 0;
       
   861       for(i=sOr.nTerm-1, pOrTerm=sOr.a; i>=0 && ok; i--, pOrTerm++){
       
   862         if( (pOrTerm->flags & TERM_OR_OK)==0 ) continue;
       
   863         pDup = sqlite3ExprDup(db, pOrTerm->pExpr->pRight);
       
   864         pList = sqlite3ExprListAppend(pWC->pParse, pList, pDup, 0);
       
   865         pLeft = pOrTerm->pExpr->pLeft;
       
   866       }
       
   867       assert( pLeft!=0 );
       
   868       pDup = sqlite3ExprDup(db, pLeft);
       
   869       pNew = sqlite3Expr(db, TK_IN, pDup, 0, 0);
       
   870       if( pNew ){
       
   871         int idxNew;
       
   872         transferJoinMarkings(pNew, pExpr);
       
   873         pNew->pList = pList;
       
   874         idxNew = whereClauseInsert(pWC, pNew, TERM_VIRTUAL|TERM_DYNAMIC);
       
   875         exprAnalyze(pSrc, pWC, idxNew);
       
   876         pTerm = &pWC->a[idxTerm];
       
   877         pWC->a[idxNew].iParent = idxTerm;
       
   878         pTerm->nChild = 1;
       
   879       }else{
       
   880         sqlite3ExprListDelete(pList);
       
   881       }
       
   882     }
       
   883 or_not_possible:
       
   884     whereClauseClear(&sOr);
       
   885   }
       
   886 #endif /* SQLITE_OMIT_OR_OPTIMIZATION */
       
   887 
       
   888 #ifndef SQLITE_OMIT_LIKE_OPTIMIZATION
       
   889   /* Add constraints to reduce the search space on a LIKE or GLOB
       
   890   ** operator.
       
   891   */
       
   892   if( isLikeOrGlob(db, pExpr, &nPattern, &isComplete) ){
       
   893     Expr *pLeft, *pRight;
       
   894     Expr *pStr1, *pStr2;
       
   895     Expr *pNewExpr1, *pNewExpr2;
       
   896     int idxNew1, idxNew2;
       
   897 
       
   898     pLeft = pExpr->pList->a[1].pExpr;
       
   899     pRight = pExpr->pList->a[0].pExpr;
       
   900     pStr1 = sqlite3PExpr(pParse, TK_STRING, 0, 0, 0);
       
   901     if( pStr1 ){
       
   902       sqlite3TokenCopy(db, &pStr1->token, &pRight->token);
       
   903       pStr1->token.n = nPattern;
       
   904       pStr1->flags = EP_Dequoted;
       
   905     }
       
   906     pStr2 = sqlite3ExprDup(db, pStr1);
       
   907     if( !db->mallocFailed ){
       
   908       assert( pStr2->token.dyn );
       
   909       ++*(u8*)&pStr2->token.z[nPattern-1];
       
   910     }
       
   911     pNewExpr1 = sqlite3PExpr(pParse, TK_GE, sqlite3ExprDup(db,pLeft), pStr1, 0);
       
   912     idxNew1 = whereClauseInsert(pWC, pNewExpr1, TERM_VIRTUAL|TERM_DYNAMIC);
       
   913     exprAnalyze(pSrc, pWC, idxNew1);
       
   914     pNewExpr2 = sqlite3PExpr(pParse, TK_LT, sqlite3ExprDup(db,pLeft), pStr2, 0);
       
   915     idxNew2 = whereClauseInsert(pWC, pNewExpr2, TERM_VIRTUAL|TERM_DYNAMIC);
       
   916     exprAnalyze(pSrc, pWC, idxNew2);
       
   917     pTerm = &pWC->a[idxTerm];
       
   918     if( isComplete ){
       
   919       pWC->a[idxNew1].iParent = idxTerm;
       
   920       pWC->a[idxNew2].iParent = idxTerm;
       
   921       pTerm->nChild = 2;
       
   922     }
       
   923   }
       
   924 #endif /* SQLITE_OMIT_LIKE_OPTIMIZATION */
       
   925 
       
   926 #ifndef SQLITE_OMIT_VIRTUALTABLE
       
   927   /* Add a WO_MATCH auxiliary term to the constraint set if the
       
   928   ** current expression is of the form:  column MATCH expr.
       
   929   ** This information is used by the xBestIndex methods of
       
   930   ** virtual tables.  The native query optimizer does not attempt
       
   931   ** to do anything with MATCH functions.
       
   932   */
       
   933   if( isMatchOfColumn(pExpr) ){
       
   934     int idxNew;
       
   935     Expr *pRight, *pLeft;
       
   936     WhereTerm *pNewTerm;
       
   937     Bitmask prereqColumn, prereqExpr;
       
   938 
       
   939     pRight = pExpr->pList->a[0].pExpr;
       
   940     pLeft = pExpr->pList->a[1].pExpr;
       
   941     prereqExpr = exprTableUsage(pMaskSet, pRight);
       
   942     prereqColumn = exprTableUsage(pMaskSet, pLeft);
       
   943     if( (prereqExpr & prereqColumn)==0 ){
       
   944       Expr *pNewExpr;
       
   945       pNewExpr = sqlite3Expr(db, TK_MATCH, 0, sqlite3ExprDup(db, pRight), 0);
       
   946       idxNew = whereClauseInsert(pWC, pNewExpr, TERM_VIRTUAL|TERM_DYNAMIC);
       
   947       pNewTerm = &pWC->a[idxNew];
       
   948       pNewTerm->prereqRight = prereqExpr;
       
   949       pNewTerm->leftCursor = pLeft->iTable;
       
   950       pNewTerm->leftColumn = pLeft->iColumn;
       
   951       pNewTerm->eOperator = WO_MATCH;
       
   952       pNewTerm->iParent = idxTerm;
       
   953       pTerm = &pWC->a[idxTerm];
       
   954       pTerm->nChild = 1;
       
   955       pTerm->flags |= TERM_COPIED;
       
   956       pNewTerm->prereqAll = pTerm->prereqAll;
       
   957     }
       
   958   }
       
   959 #endif /* SQLITE_OMIT_VIRTUALTABLE */
       
   960 }
       
   961 
       
   962 /*
       
   963 ** Return TRUE if any of the expressions in pList->a[iFirst...] contain
       
   964 ** a reference to any table other than the iBase table.
       
   965 */
       
   966 static int referencesOtherTables(
       
   967   ExprList *pList,          /* Search expressions in ths list */
       
   968   ExprMaskSet *pMaskSet,    /* Mapping from tables to bitmaps */
       
   969   int iFirst,               /* Be searching with the iFirst-th expression */
       
   970   int iBase                 /* Ignore references to this table */
       
   971 ){
       
   972   Bitmask allowed = ~getMask(pMaskSet, iBase);
       
   973   while( iFirst<pList->nExpr ){
       
   974     if( (exprTableUsage(pMaskSet, pList->a[iFirst++].pExpr)&allowed)!=0 ){
       
   975       return 1;
       
   976     }
       
   977   }
       
   978   return 0;
       
   979 }
       
   980 
       
   981 
       
   982 /*
       
   983 ** This routine decides if pIdx can be used to satisfy the ORDER BY
       
   984 ** clause.  If it can, it returns 1.  If pIdx cannot satisfy the
       
   985 ** ORDER BY clause, this routine returns 0.
       
   986 **
       
   987 ** pOrderBy is an ORDER BY clause from a SELECT statement.  pTab is the
       
   988 ** left-most table in the FROM clause of that same SELECT statement and
       
   989 ** the table has a cursor number of "base".  pIdx is an index on pTab.
       
   990 **
       
   991 ** nEqCol is the number of columns of pIdx that are used as equality
       
   992 ** constraints.  Any of these columns may be missing from the ORDER BY
       
   993 ** clause and the match can still be a success.
       
   994 **
       
   995 ** All terms of the ORDER BY that match against the index must be either
       
   996 ** ASC or DESC.  (Terms of the ORDER BY clause past the end of a UNIQUE
       
   997 ** index do not need to satisfy this constraint.)  The *pbRev value is
       
   998 ** set to 1 if the ORDER BY clause is all DESC and it is set to 0 if
       
   999 ** the ORDER BY clause is all ASC.
       
  1000 */
       
  1001 static int isSortingIndex(
       
  1002   Parse *pParse,          /* Parsing context */
       
  1003   ExprMaskSet *pMaskSet,  /* Mapping from table indices to bitmaps */
       
  1004   Index *pIdx,            /* The index we are testing */
       
  1005   int base,               /* Cursor number for the table to be sorted */
       
  1006   ExprList *pOrderBy,     /* The ORDER BY clause */
       
  1007   int nEqCol,             /* Number of index columns with == constraints */
       
  1008   int *pbRev              /* Set to 1 if ORDER BY is DESC */
       
  1009 ){
       
  1010   int i, j;                       /* Loop counters */
       
  1011   int sortOrder = 0;              /* XOR of index and ORDER BY sort direction */
       
  1012   int nTerm;                      /* Number of ORDER BY terms */
       
  1013   ExprList::ExprList_item *pTerm;    /* A term of the ORDER BY clause */
       
  1014   sqlite3 *db = pParse->db;
       
  1015 
       
  1016   assert( pOrderBy!=0 );
       
  1017   nTerm = pOrderBy->nExpr;
       
  1018   assert( nTerm>0 );
       
  1019 
       
  1020   /* Match terms of the ORDER BY clause against columns of
       
  1021   ** the index.
       
  1022   **
       
  1023   ** Note that indices have pIdx->nColumn regular columns plus
       
  1024   ** one additional column containing the rowid.  The rowid column
       
  1025   ** of the index is also allowed to match against the ORDER BY
       
  1026   ** clause.
       
  1027   */
       
  1028   for(i=j=0, pTerm=pOrderBy->a; j<nTerm && i<=pIdx->nColumn; i++){
       
  1029     Expr *pExpr;       /* The expression of the ORDER BY pTerm */
       
  1030     CollSeq *pColl;    /* The collating sequence of pExpr */
       
  1031     int termSortOrder; /* Sort order for this term */
       
  1032     int iColumn;       /* The i-th column of the index.  -1 for rowid */
       
  1033     int iSortOrder;    /* 1 for DESC, 0 for ASC on the i-th index term */
       
  1034     const char *zColl; /* Name of the collating sequence for i-th index term */
       
  1035 
       
  1036     pExpr = pTerm->pExpr;
       
  1037     if( pExpr->op!=TK_COLUMN || pExpr->iTable!=base ){
       
  1038       /* Can not use an index sort on anything that is not a column in the
       
  1039       ** left-most table of the FROM clause */
       
  1040       break;
       
  1041     }
       
  1042     pColl = sqlite3ExprCollSeq(pParse, pExpr);
       
  1043     if( !pColl ){
       
  1044       pColl = db->pDfltColl;
       
  1045     }
       
  1046     if( i<pIdx->nColumn ){
       
  1047       iColumn = pIdx->aiColumn[i];
       
  1048       if( iColumn==pIdx->pTable->iPKey ){
       
  1049         iColumn = -1;
       
  1050       }
       
  1051       iSortOrder = pIdx->aSortOrder[i];
       
  1052       zColl = pIdx->azColl[i];
       
  1053     }else{
       
  1054       iColumn = -1;
       
  1055       iSortOrder = 0;
       
  1056       zColl = pColl->zName;
       
  1057     }
       
  1058     if( pExpr->iColumn!=iColumn || sqlite3StrICmp(pColl->zName, zColl) ){
       
  1059       /* Term j of the ORDER BY clause does not match column i of the index */
       
  1060       if( i<nEqCol ){
       
  1061         /* If an index column that is constrained by == fails to match an
       
  1062         ** ORDER BY term, that is OK.  Just ignore that column of the index
       
  1063         */
       
  1064         continue;
       
  1065       }else{
       
  1066         /* If an index column fails to match and is not constrained by ==
       
  1067         ** then the index cannot satisfy the ORDER BY constraint.
       
  1068         */
       
  1069         return 0;
       
  1070       }
       
  1071     }
       
  1072     assert( pIdx->aSortOrder!=0 );
       
  1073     assert( pTerm->sortOrder==0 || pTerm->sortOrder==1 );
       
  1074     assert( iSortOrder==0 || iSortOrder==1 );
       
  1075     termSortOrder = iSortOrder ^ pTerm->sortOrder;
       
  1076     if( i>nEqCol ){
       
  1077       if( termSortOrder!=sortOrder ){
       
  1078         /* Indices can only be used if all ORDER BY terms past the
       
  1079         ** equality constraints are all either DESC or ASC. */
       
  1080         return 0;
       
  1081       }
       
  1082     }else{
       
  1083       sortOrder = termSortOrder;
       
  1084     }
       
  1085     j++;
       
  1086     pTerm++;
       
  1087     if( iColumn<0 && !referencesOtherTables(pOrderBy, pMaskSet, j, base) ){
       
  1088       /* If the indexed column is the primary key and everything matches
       
  1089       ** so far and none of the ORDER BY terms to the right reference other
       
  1090       ** tables in the join, then we are assured that the index can be used 
       
  1091       ** to sort because the primary key is unique and so none of the other
       
  1092       ** columns will make any difference
       
  1093       */
       
  1094       j = nTerm;
       
  1095     }
       
  1096   }
       
  1097 
       
  1098   *pbRev = sortOrder!=0;
       
  1099   if( j>=nTerm ){
       
  1100     /* All terms of the ORDER BY clause are covered by this index so
       
  1101     ** this index can be used for sorting. */
       
  1102     return 1;
       
  1103   }
       
  1104   if( pIdx->onError!=OE_None && i==pIdx->nColumn
       
  1105       && !referencesOtherTables(pOrderBy, pMaskSet, j, base) ){
       
  1106     /* All terms of this index match some prefix of the ORDER BY clause
       
  1107     ** and the index is UNIQUE and no terms on the tail of the ORDER BY
       
  1108     ** clause reference other tables in a join.  If this is all true then
       
  1109     ** the order by clause is superfluous. */
       
  1110     return 1;
       
  1111   }
       
  1112   return 0;
       
  1113 }
       
  1114 
       
  1115 /*
       
  1116 ** Check table to see if the ORDER BY clause in pOrderBy can be satisfied
       
  1117 ** by sorting in order of ROWID.  Return true if so and set *pbRev to be
       
  1118 ** true for reverse ROWID and false for forward ROWID order.
       
  1119 */
       
  1120 static int sortableByRowid(
       
  1121   int base,               /* Cursor number for table to be sorted */
       
  1122   ExprList *pOrderBy,     /* The ORDER BY clause */
       
  1123   ExprMaskSet *pMaskSet,  /* Mapping from tables to bitmaps */
       
  1124   int *pbRev              /* Set to 1 if ORDER BY is DESC */
       
  1125 ){
       
  1126   Expr *p;
       
  1127 
       
  1128   assert( pOrderBy!=0 );
       
  1129   assert( pOrderBy->nExpr>0 );
       
  1130   p = pOrderBy->a[0].pExpr;
       
  1131   if( p->op==TK_COLUMN && p->iTable==base && p->iColumn==-1
       
  1132     && !referencesOtherTables(pOrderBy, pMaskSet, 1, base) ){
       
  1133     *pbRev = pOrderBy->a[0].sortOrder;
       
  1134     return 1;
       
  1135   }
       
  1136   return 0;
       
  1137 }
       
  1138 
       
  1139 /*
       
  1140 ** Prepare a crude estimate of the logarithm of the input value.
       
  1141 ** The results need not be exact.  This is only used for estimating
       
  1142 ** the total cost of performing operatings with O(logN) or O(NlogN)
       
  1143 ** complexity.  Because N is just a guess, it is no great tragedy if
       
  1144 ** logN is a little off.
       
  1145 */
       
  1146 static double estLog(double N){
       
  1147   double logN = 1;
       
  1148   double x = 10;
       
  1149   while( N>x ){
       
  1150     logN += 1;
       
  1151     x *= 10;
       
  1152   }
       
  1153   return logN;
       
  1154 }
       
  1155 
       
  1156 /*
       
  1157 ** Two routines for printing the content of an sqlite3_index_info
       
  1158 ** structure.  Used for testing and debugging only.  If neither
       
  1159 ** SQLITE_TEST or SQLITE_DEBUG are defined, then these routines
       
  1160 ** are no-ops.
       
  1161 */
       
  1162 #if !defined(SQLITE_OMIT_VIRTUALTABLE) && defined(SQLITE_DEBUG)
       
  1163 static void TRACE_IDX_INPUTS(sqlite3_index_info *p){
       
  1164   int i;
       
  1165   if( !sqlite3_where_trace ) return;
       
  1166   for(i=0; i<p->nConstraint; i++){
       
  1167     sqlite3DebugPrintf("  constraint[%d]: col=%d termid=%d op=%d usabled=%d\n",
       
  1168        i,
       
  1169        p->aConstraint[i].iColumn,
       
  1170        p->aConstraint[i].iTermOffset,
       
  1171        p->aConstraint[i].op,
       
  1172        p->aConstraint[i].usable);
       
  1173   }
       
  1174   for(i=0; i<p->nOrderBy; i++){
       
  1175     sqlite3DebugPrintf("  orderby[%d]: col=%d desc=%d\n",
       
  1176        i,
       
  1177        p->aOrderBy[i].iColumn,
       
  1178        p->aOrderBy[i].desc);
       
  1179   }
       
  1180 }
       
  1181 static void TRACE_IDX_OUTPUTS(sqlite3_index_info *p){
       
  1182   int i;
       
  1183   if( !sqlite3_where_trace ) return;
       
  1184   for(i=0; i<p->nConstraint; i++){
       
  1185     sqlite3DebugPrintf("  usage[%d]: argvIdx=%d omit=%d\n",
       
  1186        i,
       
  1187        p->aConstraintUsage[i].argvIndex,
       
  1188        p->aConstraintUsage[i].omit);
       
  1189   }
       
  1190   sqlite3DebugPrintf("  idxNum=%d\n", p->idxNum);
       
  1191   sqlite3DebugPrintf("  idxStr=%s\n", p->idxStr);
       
  1192   sqlite3DebugPrintf("  orderByConsumed=%d\n", p->orderByConsumed);
       
  1193   sqlite3DebugPrintf("  estimatedCost=%g\n", p->estimatedCost);
       
  1194 }
       
  1195 #else
       
  1196 #define TRACE_IDX_INPUTS(A)
       
  1197 #define TRACE_IDX_OUTPUTS(A)
       
  1198 #endif
       
  1199 
       
  1200 #ifndef SQLITE_OMIT_VIRTUALTABLE
       
  1201 /*
       
  1202 ** Compute the best index for a virtual table.
       
  1203 **
       
  1204 ** The best index is computed by the xBestIndex method of the virtual
       
  1205 ** table module.  This routine is really just a wrapper that sets up
       
  1206 ** the sqlite3_index_info structure that is used to communicate with
       
  1207 ** xBestIndex.
       
  1208 **
       
  1209 ** In a join, this routine might be called multiple times for the
       
  1210 ** same virtual table.  The sqlite3_index_info structure is created
       
  1211 ** and initialized on the first invocation and reused on all subsequent
       
  1212 ** invocations.  The sqlite3_index_info structure is also used when
       
  1213 ** code is generated to access the virtual table.  The whereInfoDelete() 
       
  1214 ** routine takes care of freeing the sqlite3_index_info structure after
       
  1215 ** everybody has finished with it.
       
  1216 */
       
  1217 static double bestVirtualIndex(
       
  1218   Parse *pParse,                 /* The parsing context */
       
  1219   WhereClause *pWC,              /* The WHERE clause */
       
  1220   SrcList::SrcList_item *pSrc,     /* The FROM clause term to search */
       
  1221   Bitmask notReady,              /* Mask of cursors that are not available */
       
  1222   ExprList *pOrderBy,            /* The order by clause */
       
  1223   int orderByUsable,             /* True if we can potential sort */
       
  1224   sqlite3_index_info **ppIdxInfo /* Index information passed to xBestIndex */
       
  1225 ){
       
  1226   Table *pTab = pSrc->pTab;
       
  1227   sqlite3_index_info *pIdxInfo;
       
  1228   sqlite3_index_info::sqlite3_index_constraint *pIdxCons;
       
  1229   sqlite3_index_info::sqlite3_index_orderby *pIdxOrderBy;
       
  1230   sqlite3_index_info::sqlite3_index_constraint_usage *pUsage;
       
  1231   WhereTerm *pTerm;
       
  1232   int i, j;
       
  1233   int nOrderBy;
       
  1234   int rc;
       
  1235 
       
  1236   /* If the sqlite3_index_info structure has not been previously
       
  1237   ** allocated and initialized for this virtual table, then allocate
       
  1238   ** and initialize it now
       
  1239   */
       
  1240   pIdxInfo = *ppIdxInfo;
       
  1241   if( pIdxInfo==0 ){
       
  1242     WhereTerm *pTerm;
       
  1243     int nTerm;
       
  1244     WHERETRACE(("Recomputing index info for %s...\n", pTab->zName));
       
  1245 
       
  1246     /* Count the number of possible WHERE clause constraints referring
       
  1247     ** to this virtual table */
       
  1248     for(i=nTerm=0, pTerm=pWC->a; i<pWC->nTerm; i++, pTerm++){
       
  1249       if( pTerm->leftCursor != pSrc->iCursor ) continue;
       
  1250       if( pTerm->eOperator==WO_IN ) continue;
       
  1251       if( pTerm->eOperator==WO_ISNULL ) continue;
       
  1252       nTerm++;
       
  1253     }
       
  1254 
       
  1255     /* If the ORDER BY clause contains only columns in the current 
       
  1256     ** virtual table then allocate space for the aOrderBy part of
       
  1257     ** the sqlite3_index_info structure.
       
  1258     */
       
  1259     nOrderBy = 0;
       
  1260     if( pOrderBy ){
       
  1261       for(i=0; i<pOrderBy->nExpr; i++){
       
  1262         Expr *pExpr = pOrderBy->a[i].pExpr;
       
  1263         if( pExpr->op!=TK_COLUMN || pExpr->iTable!=pSrc->iCursor ) break;
       
  1264       }
       
  1265       if( i==pOrderBy->nExpr ){
       
  1266         nOrderBy = pOrderBy->nExpr;
       
  1267       }
       
  1268     }
       
  1269 
       
  1270     /* Allocate the sqlite3_index_info structure
       
  1271     */
       
  1272     pIdxInfo = (sqlite3_index_info*)sqlite3DbMallocZero(pParse->db, sizeof(*pIdxInfo)
       
  1273                              + (sizeof(*pIdxCons) + sizeof(*pUsage))*nTerm
       
  1274                              + sizeof(*pIdxOrderBy)*nOrderBy );
       
  1275     if( pIdxInfo==0 ){
       
  1276       sqlite3ErrorMsg(pParse, "out of memory");
       
  1277       return 0.0;
       
  1278     }
       
  1279     *ppIdxInfo = pIdxInfo;
       
  1280 
       
  1281     /* Initialize the structure.  The sqlite3_index_info structure contains
       
  1282     ** many fields that are declared "const" to prevent xBestIndex from
       
  1283     ** changing them.  We have to do some funky casting in order to
       
  1284     ** initialize those fields.
       
  1285     */
       
  1286 	pIdxCons = (sqlite3_index_info::sqlite3_index_constraint*)&pIdxInfo[1];
       
  1287 	pIdxOrderBy = (sqlite3_index_info::sqlite3_index_orderby*)&pIdxCons[nTerm];
       
  1288 	pUsage = (sqlite3_index_info::sqlite3_index_constraint_usage*)&pIdxOrderBy[nOrderBy];
       
  1289     *(int*)&pIdxInfo->nConstraint = nTerm;
       
  1290     *(int*)&pIdxInfo->nOrderBy = nOrderBy;
       
  1291 	*(sqlite3_index_info::sqlite3_index_constraint**)&pIdxInfo->aConstraint = pIdxCons;
       
  1292 	*(sqlite3_index_info::sqlite3_index_orderby**)&pIdxInfo->aOrderBy = pIdxOrderBy;
       
  1293 	*(sqlite3_index_info::sqlite3_index_constraint_usage**)&pIdxInfo->aConstraintUsage =
       
  1294                                                                      pUsage;
       
  1295 
       
  1296     for(i=j=0, pTerm=pWC->a; i<pWC->nTerm; i++, pTerm++){
       
  1297       if( pTerm->leftCursor != pSrc->iCursor ) continue;
       
  1298       if( pTerm->eOperator==WO_IN ) continue;
       
  1299       if( pTerm->eOperator==WO_ISNULL ) continue;
       
  1300       pIdxCons[j].iColumn = pTerm->leftColumn;
       
  1301       pIdxCons[j].iTermOffset = i;
       
  1302       pIdxCons[j].op = pTerm->eOperator;
       
  1303       /* The direct assignment in the previous line is possible only because
       
  1304       ** the WO_ and SQLITE_INDEX_CONSTRAINT_ codes are identical.  The
       
  1305       ** following asserts verify this fact. */
       
  1306       assert( WO_EQ==SQLITE_INDEX_CONSTRAINT_EQ );
       
  1307       assert( WO_LT==SQLITE_INDEX_CONSTRAINT_LT );
       
  1308       assert( WO_LE==SQLITE_INDEX_CONSTRAINT_LE );
       
  1309       assert( WO_GT==SQLITE_INDEX_CONSTRAINT_GT );
       
  1310       assert( WO_GE==SQLITE_INDEX_CONSTRAINT_GE );
       
  1311       assert( WO_MATCH==SQLITE_INDEX_CONSTRAINT_MATCH );
       
  1312       assert( pTerm->eOperator & (WO_EQ|WO_LT|WO_LE|WO_GT|WO_GE|WO_MATCH) );
       
  1313       j++;
       
  1314     }
       
  1315     for(i=0; i<nOrderBy; i++){
       
  1316       Expr *pExpr = pOrderBy->a[i].pExpr;
       
  1317       pIdxOrderBy[i].iColumn = pExpr->iColumn;
       
  1318       pIdxOrderBy[i].desc = pOrderBy->a[i].sortOrder;
       
  1319     }
       
  1320   }
       
  1321 
       
  1322   /* At this point, the sqlite3_index_info structure that pIdxInfo points
       
  1323   ** to will have been initialized, either during the current invocation or
       
  1324   ** during some prior invocation.  Now we just have to customize the
       
  1325   ** details of pIdxInfo for the current invocation and pass it to
       
  1326   ** xBestIndex.
       
  1327   */
       
  1328 
       
  1329   /* The module name must be defined. Also, by this point there must
       
  1330   ** be a pointer to an sqlite3_vtab structure. Otherwise
       
  1331   ** sqlite3ViewGetColumnNames() would have picked up the error. 
       
  1332   */
       
  1333   assert( pTab->azModuleArg && pTab->azModuleArg[0] );
       
  1334   assert( pTab->pVtab );
       
  1335 #if 0
       
  1336   if( pTab->pVtab==0 ){
       
  1337     sqlite3ErrorMsg(pParse, "undefined module %s for table %s",
       
  1338         pTab->azModuleArg[0], pTab->zName);
       
  1339     return 0.0;
       
  1340   }
       
  1341 #endif
       
  1342 
       
  1343   /* Set the aConstraint[].usable fields and initialize all 
       
  1344   ** output variables to zero.
       
  1345   **
       
  1346   ** aConstraint[].usable is true for constraints where the right-hand
       
  1347   ** side contains only references to tables to the left of the current
       
  1348   ** table.  In other words, if the constraint is of the form:
       
  1349   **
       
  1350   **           column = expr
       
  1351   **
       
  1352   ** and we are evaluating a join, then the constraint on column is 
       
  1353   ** only valid if all tables referenced in expr occur to the left
       
  1354   ** of the table containing column.
       
  1355   **
       
  1356   ** The aConstraints[] array contains entries for all constraints
       
  1357   ** on the current table.  That way we only have to compute it once
       
  1358   ** even though we might try to pick the best index multiple times.
       
  1359   ** For each attempt at picking an index, the order of tables in the
       
  1360   ** join might be different so we have to recompute the usable flag
       
  1361   ** each time.
       
  1362   */
       
  1363   pIdxCons = *(sqlite3_index_info::sqlite3_index_constraint**)&pIdxInfo->aConstraint;
       
  1364   pUsage = pIdxInfo->aConstraintUsage;
       
  1365   for(i=0; i<pIdxInfo->nConstraint; i++, pIdxCons++){
       
  1366     j = pIdxCons->iTermOffset;
       
  1367     pTerm = &pWC->a[j];
       
  1368     pIdxCons->usable =  (pTerm->prereqRight & notReady)==0;
       
  1369   }
       
  1370   memset(pUsage, 0, sizeof(pUsage[0])*pIdxInfo->nConstraint);
       
  1371   if( pIdxInfo->needToFreeIdxStr ){
       
  1372     sqlite3_free(pIdxInfo->idxStr);
       
  1373   }
       
  1374   pIdxInfo->idxStr = 0;
       
  1375   pIdxInfo->idxNum = 0;
       
  1376   pIdxInfo->needToFreeIdxStr = 0;
       
  1377   pIdxInfo->orderByConsumed = 0;
       
  1378   pIdxInfo->estimatedCost = SQLITE_BIG_DBL / 2.0;
       
  1379   nOrderBy = pIdxInfo->nOrderBy;
       
  1380   if( pIdxInfo->nOrderBy && !orderByUsable ){
       
  1381     *(int*)&pIdxInfo->nOrderBy = 0;
       
  1382   }
       
  1383 
       
  1384   sqlite3SafetyOff(pParse->db);
       
  1385   WHERETRACE(("xBestIndex for %s\n", pTab->zName));
       
  1386   TRACE_IDX_INPUTS(pIdxInfo);
       
  1387   rc = pTab->pVtab->pModule->xBestIndex(pTab->pVtab, pIdxInfo);
       
  1388   TRACE_IDX_OUTPUTS(pIdxInfo);
       
  1389   if( rc!=SQLITE_OK ){
       
  1390     if( rc==SQLITE_NOMEM ){
       
  1391       pParse->db->mallocFailed = 1;
       
  1392     }else {
       
  1393       sqlite3ErrorMsg(pParse, "%s", sqlite3ErrStr(rc));
       
  1394     }
       
  1395     sqlite3SafetyOn(pParse->db);
       
  1396   }else{
       
  1397     rc = sqlite3SafetyOn(pParse->db);
       
  1398   }
       
  1399   *(int*)&pIdxInfo->nOrderBy = nOrderBy;
       
  1400 
       
  1401   return pIdxInfo->estimatedCost;
       
  1402 }
       
  1403 #endif /* SQLITE_OMIT_VIRTUALTABLE */
       
  1404 
       
  1405 /*
       
  1406 ** Find the best index for accessing a particular table.  Return a pointer
       
  1407 ** to the index, flags that describe how the index should be used, the
       
  1408 ** number of equality constraints, and the "cost" for this index.
       
  1409 **
       
  1410 ** The lowest cost index wins.  The cost is an estimate of the amount of
       
  1411 ** CPU and disk I/O need to process the request using the selected index.
       
  1412 ** Factors that influence cost include:
       
  1413 **
       
  1414 **    *  The estimated number of rows that will be retrieved.  (The
       
  1415 **       fewer the better.)
       
  1416 **
       
  1417 **    *  Whether or not sorting must occur.
       
  1418 **
       
  1419 **    *  Whether or not there must be separate lookups in the
       
  1420 **       index and in the main table.
       
  1421 **
       
  1422 */
       
  1423 static double bestIndex(
       
  1424   Parse *pParse,              /* The parsing context */
       
  1425   WhereClause *pWC,           /* The WHERE clause */
       
  1426   SrcList::SrcList_item *pSrc,  /* The FROM clause term to search */
       
  1427   Bitmask notReady,           /* Mask of cursors that are not available */
       
  1428   ExprList *pOrderBy,         /* The order by clause */
       
  1429   Index **ppIndex,            /* Make *ppIndex point to the best index */
       
  1430   int *pFlags,                /* Put flags describing this choice in *pFlags */
       
  1431   int *pnEq                   /* Put the number of == or IN constraints here */
       
  1432 ){
       
  1433   WhereTerm *pTerm;
       
  1434   Index *bestIdx = 0;         /* Index that gives the lowest cost */
       
  1435   double lowestCost;          /* The cost of using bestIdx */
       
  1436   int bestFlags = 0;          /* Flags associated with bestIdx */
       
  1437   int bestNEq = 0;            /* Best value for nEq */
       
  1438   int iCur = pSrc->iCursor;   /* The cursor of the table to be accessed */
       
  1439   Index *pProbe;              /* An index we are evaluating */
       
  1440   int rev;                    /* True to scan in reverse order */
       
  1441   int flags;                  /* Flags associated with pProbe */
       
  1442   int nEq;                    /* Number of == or IN constraints */
       
  1443   int eqTermMask;             /* Mask of valid equality operators */
       
  1444   double cost;                /* Cost of using pProbe */
       
  1445 
       
  1446   WHERETRACE(("bestIndex: tbl=%s notReady=%x\n", pSrc->pTab->zName, notReady));
       
  1447   lowestCost = SQLITE_BIG_DBL;
       
  1448   pProbe = pSrc->pTab->pIndex;
       
  1449 
       
  1450   /* If the table has no indices and there are no terms in the where
       
  1451   ** clause that refer to the ROWID, then we will never be able to do
       
  1452   ** anything other than a full table scan on this table.  We might as
       
  1453   ** well put it first in the join order.  That way, perhaps it can be
       
  1454   ** referenced by other tables in the join.
       
  1455   */
       
  1456   if( pProbe==0 &&
       
  1457      findTerm(pWC, iCur, -1, 0, WO_EQ|WO_IN|WO_LT|WO_LE|WO_GT|WO_GE,0)==0 &&
       
  1458      (pOrderBy==0 || !sortableByRowid(iCur, pOrderBy, pWC->pMaskSet, &rev)) ){
       
  1459     *pFlags = 0;
       
  1460     *ppIndex = 0;
       
  1461     *pnEq = 0;
       
  1462     return 0.0;
       
  1463   }
       
  1464 
       
  1465   /* Check for a rowid=EXPR or rowid IN (...) constraints
       
  1466   */
       
  1467   pTerm = findTerm(pWC, iCur, -1, notReady, WO_EQ|WO_IN, 0);
       
  1468   if( pTerm ){
       
  1469     Expr *pExpr;
       
  1470     *ppIndex = 0;
       
  1471     bestFlags = WHERE_ROWID_EQ;
       
  1472     if( pTerm->eOperator & WO_EQ ){
       
  1473       /* Rowid== is always the best pick.  Look no further.  Because only
       
  1474       ** a single row is generated, output is always in sorted order */
       
  1475       *pFlags = WHERE_ROWID_EQ | WHERE_UNIQUE;
       
  1476       *pnEq = 1;
       
  1477       WHERETRACE(("... best is rowid\n"));
       
  1478       return 0.0;
       
  1479     }else if( (pExpr = pTerm->pExpr)->pList!=0 ){
       
  1480       /* Rowid IN (LIST): cost is NlogN where N is the number of list
       
  1481       ** elements.  */
       
  1482       lowestCost = pExpr->pList->nExpr;
       
  1483       lowestCost *= estLog(lowestCost);
       
  1484     }else{
       
  1485       /* Rowid IN (SELECT): cost is NlogN where N is the number of rows
       
  1486       ** in the result of the inner select.  We have no way to estimate
       
  1487       ** that value so make a wild guess. */
       
  1488       lowestCost = 200;
       
  1489     }
       
  1490     WHERETRACE(("... rowid IN cost: %.9g\n", lowestCost));
       
  1491   }
       
  1492 
       
  1493   /* Estimate the cost of a table scan.  If we do not know how many
       
  1494   ** entries are in the table, use 1 million as a guess.
       
  1495   */
       
  1496   cost = pProbe ? pProbe->aiRowEst[0] : 1000000;
       
  1497   WHERETRACE(("... table scan base cost: %.9g\n", cost));
       
  1498   flags = WHERE_ROWID_RANGE;
       
  1499 
       
  1500   /* Check for constraints on a range of rowids in a table scan.
       
  1501   */
       
  1502   pTerm = findTerm(pWC, iCur, -1, notReady, WO_LT|WO_LE|WO_GT|WO_GE, 0);
       
  1503   if( pTerm ){
       
  1504     if( findTerm(pWC, iCur, -1, notReady, WO_LT|WO_LE, 0) ){
       
  1505       flags |= WHERE_TOP_LIMIT;
       
  1506       cost /= 3;  /* Guess that rowid<EXPR eliminates two-thirds or rows */
       
  1507     }
       
  1508     if( findTerm(pWC, iCur, -1, notReady, WO_GT|WO_GE, 0) ){
       
  1509       flags |= WHERE_BTM_LIMIT;
       
  1510       cost /= 3;  /* Guess that rowid>EXPR eliminates two-thirds of rows */
       
  1511     }
       
  1512     WHERETRACE(("... rowid range reduces cost to %.9g\n", cost));
       
  1513   }else{
       
  1514     flags = 0;
       
  1515   }
       
  1516 
       
  1517   /* If the table scan does not satisfy the ORDER BY clause, increase
       
  1518   ** the cost by NlogN to cover the expense of sorting. */
       
  1519   if( pOrderBy ){
       
  1520     if( sortableByRowid(iCur, pOrderBy, pWC->pMaskSet, &rev) ){
       
  1521       flags |= WHERE_ORDERBY|WHERE_ROWID_RANGE;
       
  1522       if( rev ){
       
  1523         flags |= WHERE_REVERSE;
       
  1524       }
       
  1525     }else{
       
  1526       cost += cost*estLog(cost);
       
  1527       WHERETRACE(("... sorting increases cost to %.9g\n", cost));
       
  1528     }
       
  1529   }
       
  1530   if( cost<lowestCost ){
       
  1531     lowestCost = cost;
       
  1532     bestFlags = flags;
       
  1533   }
       
  1534 
       
  1535   /* If the pSrc table is the right table of a LEFT JOIN then we may not
       
  1536   ** use an index to satisfy IS NULL constraints on that table.  This is
       
  1537   ** because columns might end up being NULL if the table does not match -
       
  1538   ** a circumstance which the index cannot help us discover.  Ticket #2177.
       
  1539   */
       
  1540   if( (pSrc->jointype & JT_LEFT)!=0 ){
       
  1541     eqTermMask = WO_EQ|WO_IN;
       
  1542   }else{
       
  1543     eqTermMask = WO_EQ|WO_IN|WO_ISNULL;
       
  1544   }
       
  1545 
       
  1546   /* Look at each index.
       
  1547   */
       
  1548   for(; pProbe; pProbe=pProbe->pNext){
       
  1549     int i;                       /* Loop counter */
       
  1550     double inMultiplier = 1;
       
  1551 
       
  1552     WHERETRACE(("... index %s:\n", pProbe->zName));
       
  1553 
       
  1554     /* Count the number of columns in the index that are satisfied
       
  1555     ** by x=EXPR constraints or x IN (...) constraints.
       
  1556     */
       
  1557     flags = 0;
       
  1558     for(i=0; i<pProbe->nColumn; i++){
       
  1559       int j = pProbe->aiColumn[i];
       
  1560       pTerm = findTerm(pWC, iCur, j, notReady, eqTermMask, pProbe);
       
  1561       if( pTerm==0 ) break;
       
  1562       flags |= WHERE_COLUMN_EQ;
       
  1563       if( pTerm->eOperator & WO_IN ){
       
  1564         Expr *pExpr = pTerm->pExpr;
       
  1565         flags |= WHERE_COLUMN_IN;
       
  1566         if( pExpr->pSelect!=0 ){
       
  1567           inMultiplier *= 25;
       
  1568         }else if( pExpr->pList!=0 ){
       
  1569           inMultiplier *= pExpr->pList->nExpr + 1;
       
  1570         }
       
  1571       }
       
  1572     }
       
  1573     cost = pProbe->aiRowEst[i] * inMultiplier * estLog(inMultiplier);
       
  1574     nEq = i;
       
  1575     if( pProbe->onError!=OE_None && (flags & WHERE_COLUMN_IN)==0
       
  1576          && nEq==pProbe->nColumn ){
       
  1577       flags |= WHERE_UNIQUE;
       
  1578     }
       
  1579     WHERETRACE(("...... nEq=%d inMult=%.9g cost=%.9g\n",nEq,inMultiplier,cost));
       
  1580 
       
  1581     /* Look for range constraints
       
  1582     */
       
  1583     if( nEq<pProbe->nColumn ){
       
  1584       int j = pProbe->aiColumn[nEq];
       
  1585       pTerm = findTerm(pWC, iCur, j, notReady, WO_LT|WO_LE|WO_GT|WO_GE, pProbe);
       
  1586       if( pTerm ){
       
  1587         flags |= WHERE_COLUMN_RANGE;
       
  1588         if( findTerm(pWC, iCur, j, notReady, WO_LT|WO_LE, pProbe) ){
       
  1589           flags |= WHERE_TOP_LIMIT;
       
  1590           cost /= 3;
       
  1591         }
       
  1592         if( findTerm(pWC, iCur, j, notReady, WO_GT|WO_GE, pProbe) ){
       
  1593           flags |= WHERE_BTM_LIMIT;
       
  1594           cost /= 3;
       
  1595         }
       
  1596         WHERETRACE(("...... range reduces cost to %.9g\n", cost));
       
  1597       }
       
  1598     }
       
  1599 
       
  1600     /* Add the additional cost of sorting if that is a factor.
       
  1601     */
       
  1602     if( pOrderBy ){
       
  1603       if( (flags & WHERE_COLUMN_IN)==0 &&
       
  1604            isSortingIndex(pParse,pWC->pMaskSet,pProbe,iCur,pOrderBy,nEq,&rev) ){
       
  1605         if( flags==0 ){
       
  1606           flags = WHERE_COLUMN_RANGE;
       
  1607         }
       
  1608         flags |= WHERE_ORDERBY;
       
  1609         if( rev ){
       
  1610           flags |= WHERE_REVERSE;
       
  1611         }
       
  1612       }else{
       
  1613         cost += cost*estLog(cost);
       
  1614         WHERETRACE(("...... orderby increases cost to %.9g\n", cost));
       
  1615       }
       
  1616     }
       
  1617 
       
  1618     /* Check to see if we can get away with using just the index without
       
  1619     ** ever reading the table.  If that is the case, then halve the
       
  1620     ** cost of this index.
       
  1621     */
       
  1622     if( flags && pSrc->colUsed < (((Bitmask)1)<<(BMS-1)) ){
       
  1623       Bitmask m = pSrc->colUsed;
       
  1624       int j;
       
  1625       for(j=0; j<pProbe->nColumn; j++){
       
  1626         int x = pProbe->aiColumn[j];
       
  1627         if( x<BMS-1 ){
       
  1628           m &= ~(((Bitmask)1)<<x);
       
  1629         }
       
  1630       }
       
  1631       if( m==0 ){
       
  1632         flags |= WHERE_IDX_ONLY;
       
  1633         cost /= 2;
       
  1634         WHERETRACE(("...... idx-only reduces cost to %.9g\n", cost));
       
  1635       }
       
  1636     }
       
  1637 
       
  1638     /* If this index has achieved the lowest cost so far, then use it.
       
  1639     */
       
  1640     if( flags && cost < lowestCost ){
       
  1641       bestIdx = pProbe;
       
  1642       lowestCost = cost;
       
  1643       bestFlags = flags;
       
  1644       bestNEq = nEq;
       
  1645     }
       
  1646   }
       
  1647 
       
  1648   /* Report the best result
       
  1649   */
       
  1650   *ppIndex = bestIdx;
       
  1651   WHERETRACE(("best index is %s, cost=%.9g, flags=%x, nEq=%d\n",
       
  1652         bestIdx ? bestIdx->zName : "(none)", lowestCost, bestFlags, bestNEq));
       
  1653   *pFlags = bestFlags | eqTermMask;
       
  1654   *pnEq = bestNEq;
       
  1655   return lowestCost;
       
  1656 }
       
  1657 
       
  1658 
       
  1659 /*
       
  1660 ** Disable a term in the WHERE clause.  Except, do not disable the term
       
  1661 ** if it controls a LEFT OUTER JOIN and it did not originate in the ON
       
  1662 ** or USING clause of that join.
       
  1663 **
       
  1664 ** Consider the term t2.z='ok' in the following queries:
       
  1665 **
       
  1666 **   (1)  SELECT * FROM t1 LEFT JOIN t2 ON t1.a=t2.x WHERE t2.z='ok'
       
  1667 **   (2)  SELECT * FROM t1 LEFT JOIN t2 ON t1.a=t2.x AND t2.z='ok'
       
  1668 **   (3)  SELECT * FROM t1, t2 WHERE t1.a=t2.x AND t2.z='ok'
       
  1669 **
       
  1670 ** The t2.z='ok' is disabled in the in (2) because it originates
       
  1671 ** in the ON clause.  The term is disabled in (3) because it is not part
       
  1672 ** of a LEFT OUTER JOIN.  In (1), the term is not disabled.
       
  1673 **
       
  1674 ** Disabling a term causes that term to not be tested in the inner loop
       
  1675 ** of the join.  Disabling is an optimization.  When terms are satisfied
       
  1676 ** by indices, we disable them to prevent redundant tests in the inner
       
  1677 ** loop.  We would get the correct results if nothing were ever disabled,
       
  1678 ** but joins might run a little slower.  The trick is to disable as much
       
  1679 ** as we can without disabling too much.  If we disabled in (1), we'd get
       
  1680 ** the wrong answer.  See ticket #813.
       
  1681 */
       
  1682 static void disableTerm(WhereLevel *pLevel, WhereTerm *pTerm){
       
  1683   if( pTerm
       
  1684       && (pTerm->flags & TERM_CODED)==0
       
  1685       && (pLevel->iLeftJoin==0 || ExprHasProperty(pTerm->pExpr, EP_FromJoin))
       
  1686   ){
       
  1687     pTerm->flags |= TERM_CODED;
       
  1688     if( pTerm->iParent>=0 ){
       
  1689       WhereTerm *pOther = &pTerm->pWC->a[pTerm->iParent];
       
  1690       if( (--pOther->nChild)==0 ){
       
  1691         disableTerm(pLevel, pOther);
       
  1692       }
       
  1693     }
       
  1694   }
       
  1695 }
       
  1696 
       
  1697 /*
       
  1698 ** Generate code that builds a probe for an index.
       
  1699 **
       
  1700 ** There should be nColumn values on the stack.  The index
       
  1701 ** to be probed is pIdx.  Pop the values from the stack and
       
  1702 ** replace them all with a single record that is the index
       
  1703 ** problem.
       
  1704 */
       
  1705 static void buildIndexProbe(
       
  1706   Vdbe *v,        /* Generate code into this VM */
       
  1707   int nColumn,    /* The number of columns to check for NULL */
       
  1708   Index *pIdx     /* Index that we will be searching */
       
  1709 ){
       
  1710   sqlite3VdbeAddOp(v, OP_MakeRecord, nColumn, 0);
       
  1711   sqlite3IndexAffinityStr(v, pIdx);
       
  1712 }
       
  1713 
       
  1714 
       
  1715 /*
       
  1716 ** Generate code for a single equality term of the WHERE clause.  An equality
       
  1717 ** term can be either X=expr or X IN (...).   pTerm is the term to be 
       
  1718 ** coded.
       
  1719 **
       
  1720 ** The current value for the constraint is left on the top of the stack.
       
  1721 **
       
  1722 ** For a constraint of the form X=expr, the expression is evaluated and its
       
  1723 ** result is left on the stack.  For constraints of the form X IN (...)
       
  1724 ** this routine sets up a loop that will iterate over all values of X.
       
  1725 */
       
  1726 static void codeEqualityTerm(
       
  1727   Parse *pParse,      /* The parsing context */
       
  1728   WhereTerm *pTerm,   /* The term of the WHERE clause to be coded */
       
  1729   WhereLevel *pLevel  /* When level of the FROM clause we are working on */
       
  1730 ){
       
  1731   Expr *pX = pTerm->pExpr;
       
  1732   Vdbe *v = pParse->pVdbe;
       
  1733   if( pX->op==TK_EQ ){
       
  1734     sqlite3ExprCode(pParse, pX->pRight);
       
  1735   }else if( pX->op==TK_ISNULL ){
       
  1736     sqlite3VdbeAddOp(v, OP_Null, 0, 0);
       
  1737 #ifndef SQLITE_OMIT_SUBQUERY
       
  1738   }else{
       
  1739     int eType;
       
  1740     int iTab;
       
  1741 	WhereLevel::InLoop *pIn;
       
  1742 
       
  1743     assert( pX->op==TK_IN );
       
  1744     eType = sqlite3FindInIndex(pParse, pX, 1);
       
  1745     iTab = pX->iTable;
       
  1746     sqlite3VdbeAddOp(v, OP_Rewind, iTab, 0);
       
  1747     VdbeComment((v, "# %.*s", pX->span.n, pX->span.z));
       
  1748     if( pLevel->nIn==0 ){
       
  1749       pLevel->nxt = sqlite3VdbeMakeLabel(v);
       
  1750     }
       
  1751     pLevel->nIn++;
       
  1752 	pLevel->aInLoop = (WhereLevel::InLoop*)sqlite3DbReallocOrFree(pParse->db, pLevel->aInLoop,
       
  1753                                     sizeof(pLevel->aInLoop[0])*pLevel->nIn);
       
  1754 	pIn = (WhereLevel::InLoop*)pLevel->aInLoop;
       
  1755     if( pIn ){
       
  1756       int op = ((eType==IN_INDEX_ROWID)?OP_Rowid:OP_Column);
       
  1757       pIn += pLevel->nIn - 1;
       
  1758       pIn->iCur = iTab;
       
  1759       pIn->topAddr = sqlite3VdbeAddOp(v, op, iTab, 0);
       
  1760       sqlite3VdbeAddOp(v, OP_IsNull, -1, 0);
       
  1761     }else{
       
  1762       pLevel->nIn = 0;
       
  1763     }
       
  1764 #endif
       
  1765   }
       
  1766   disableTerm(pLevel, pTerm);
       
  1767 }
       
  1768 
       
  1769 /*
       
  1770 ** Generate code that will evaluate all == and IN constraints for an
       
  1771 ** index.  The values for all constraints are left on the stack.
       
  1772 **
       
  1773 ** For example, consider table t1(a,b,c,d,e,f) with index i1(a,b,c).
       
  1774 ** Suppose the WHERE clause is this:  a==5 AND b IN (1,2,3) AND c>5 AND c<10
       
  1775 ** The index has as many as three equality constraints, but in this
       
  1776 ** example, the third "c" value is an inequality.  So only two 
       
  1777 ** constraints are coded.  This routine will generate code to evaluate
       
  1778 ** a==5 and b IN (1,2,3).  The current values for a and b will be left
       
  1779 ** on the stack - a is the deepest and b the shallowest.
       
  1780 **
       
  1781 ** In the example above nEq==2.  But this subroutine works for any value
       
  1782 ** of nEq including 0.  If nEq==0, this routine is nearly a no-op.
       
  1783 ** The only thing it does is allocate the pLevel->iMem memory cell.
       
  1784 **
       
  1785 ** This routine always allocates at least one memory cell and puts
       
  1786 ** the address of that memory cell in pLevel->iMem.  The code that
       
  1787 ** calls this routine will use pLevel->iMem to store the termination
       
  1788 ** key value of the loop.  If one or more IN operators appear, then
       
  1789 ** this routine allocates an additional nEq memory cells for internal
       
  1790 ** use.
       
  1791 */
       
  1792 static void codeAllEqualityTerms(
       
  1793   Parse *pParse,        /* Parsing context */
       
  1794   WhereLevel *pLevel,   /* Which nested loop of the FROM we are coding */
       
  1795   WhereClause *pWC,     /* The WHERE clause */
       
  1796   Bitmask notReady      /* Which parts of FROM have not yet been coded */
       
  1797 ){
       
  1798   int nEq = pLevel->nEq;        /* The number of == or IN constraints to code */
       
  1799   int termsInMem = 0;           /* If true, store value in mem[] cells */
       
  1800   Vdbe *v = pParse->pVdbe;      /* The virtual machine under construction */
       
  1801   Index *pIdx = pLevel->pIdx;   /* The index being used for this loop */
       
  1802   int iCur = pLevel->iTabCur;   /* The cursor of the table */
       
  1803   WhereTerm *pTerm;             /* A single constraint term */
       
  1804   int j;                        /* Loop counter */
       
  1805 
       
  1806   /* Figure out how many memory cells we will need then allocate them.
       
  1807   ** We always need at least one used to store the loop terminator
       
  1808   ** value.  If there are IN operators we'll need one for each == or
       
  1809   ** IN constraint.
       
  1810   */
       
  1811   pLevel->iMem = pParse->nMem++;
       
  1812   if( pLevel->flags & WHERE_COLUMN_IN ){
       
  1813     pParse->nMem += pLevel->nEq;
       
  1814     termsInMem = 1;
       
  1815   }
       
  1816 
       
  1817   /* Evaluate the equality constraints
       
  1818   */
       
  1819   assert( pIdx->nColumn>=nEq );
       
  1820   for(j=0; j<nEq; j++){
       
  1821     int k = pIdx->aiColumn[j];
       
  1822     pTerm = findTerm(pWC, iCur, k, notReady, pLevel->flags, pIdx);
       
  1823     if( pTerm==0 ) break;
       
  1824     assert( (pTerm->flags & TERM_CODED)==0 );
       
  1825     codeEqualityTerm(pParse, pTerm, pLevel);
       
  1826     if( (pTerm->eOperator & (WO_ISNULL|WO_IN))==0 ){
       
  1827       sqlite3VdbeAddOp(v, OP_IsNull, termsInMem ? -1 : -(j+1), pLevel->brk);
       
  1828     }
       
  1829     if( termsInMem ){
       
  1830       sqlite3VdbeAddOp(v, OP_MemStore, pLevel->iMem+j+1, 1);
       
  1831     }
       
  1832   }
       
  1833 
       
  1834   /* Make sure all the constraint values are on the top of the stack
       
  1835   */
       
  1836   if( termsInMem ){
       
  1837     for(j=0; j<nEq; j++){
       
  1838       sqlite3VdbeAddOp(v, OP_MemLoad, pLevel->iMem+j+1, 0);
       
  1839     }
       
  1840   }
       
  1841 }
       
  1842 
       
  1843 #if defined(SQLITE_TEST)
       
  1844 /*
       
  1845 ** The following variable holds a text description of query plan generated
       
  1846 ** by the most recent call to sqlite3WhereBegin().  Each call to WhereBegin
       
  1847 ** overwrites the previous.  This information is used for testing and
       
  1848 ** analysis only.
       
  1849 */
       
  1850 char sqlite3_query_plan[BMS*2*40];  /* Text of the join */
       
  1851 static int nQPlan = 0;              /* Next free slow in _query_plan[] */
       
  1852 
       
  1853 #endif /* SQLITE_TEST */
       
  1854 
       
  1855 
       
  1856 /*
       
  1857 ** Free a WhereInfo structure
       
  1858 */
       
  1859 static void whereInfoFree(WhereInfo *pWInfo){
       
  1860   if( pWInfo ){
       
  1861     int i;
       
  1862     for(i=0; i<pWInfo->nLevel; i++){
       
  1863       sqlite3_index_info *pInfo = pWInfo->a[i].pIdxInfo;
       
  1864       if( pInfo ){
       
  1865         if( pInfo->needToFreeIdxStr ){
       
  1866           /* Coverage: Don't think this can be reached. By the time this
       
  1867           ** function is called, the index-strings have been passed
       
  1868           ** to the vdbe layer for deletion.
       
  1869           */
       
  1870           sqlite3_free(pInfo->idxStr);
       
  1871         }
       
  1872         sqlite3_free(pInfo);
       
  1873       }
       
  1874     }
       
  1875     sqlite3_free(pWInfo);
       
  1876   }
       
  1877 }
       
  1878 
       
  1879 
       
  1880 /*
       
  1881 ** Generate the beginning of the loop used for WHERE clause processing.
       
  1882 ** The return value is a pointer to an opaque structure that contains
       
  1883 ** information needed to terminate the loop.  Later, the calling routine
       
  1884 ** should invoke sqlite3WhereEnd() with the return value of this function
       
  1885 ** in order to complete the WHERE clause processing.
       
  1886 **
       
  1887 ** If an error occurs, this routine returns NULL.
       
  1888 **
       
  1889 ** The basic idea is to do a nested loop, one loop for each table in
       
  1890 ** the FROM clause of a select.  (INSERT and UPDATE statements are the
       
  1891 ** same as a SELECT with only a single table in the FROM clause.)  For
       
  1892 ** example, if the SQL is this:
       
  1893 **
       
  1894 **       SELECT * FROM t1, t2, t3 WHERE ...;
       
  1895 **
       
  1896 ** Then the code generated is conceptually like the following:
       
  1897 **
       
  1898 **      foreach row1 in t1 do       \    Code generated
       
  1899 **        foreach row2 in t2 do      |-- by sqlite3WhereBegin()
       
  1900 **          foreach row3 in t3 do   /
       
  1901 **            ...
       
  1902 **          end                     \    Code generated
       
  1903 **        end                        |-- by sqlite3WhereEnd()
       
  1904 **      end                         /
       
  1905 **
       
  1906 ** Note that the loops might not be nested in the order in which they
       
  1907 ** appear in the FROM clause if a different order is better able to make
       
  1908 ** use of indices.  Note also that when the IN operator appears in
       
  1909 ** the WHERE clause, it might result in additional nested loops for
       
  1910 ** scanning through all values on the right-hand side of the IN.
       
  1911 **
       
  1912 ** There are Btree cursors associated with each table.  t1 uses cursor
       
  1913 ** number pTabList->a[0].iCursor.  t2 uses the cursor pTabList->a[1].iCursor.
       
  1914 ** And so forth.  This routine generates code to open those VDBE cursors
       
  1915 ** and sqlite3WhereEnd() generates the code to close them.
       
  1916 **
       
  1917 ** The code that sqlite3WhereBegin() generates leaves the cursors named
       
  1918 ** in pTabList pointing at their appropriate entries.  The [...] code
       
  1919 ** can use OP_Column and OP_Rowid opcodes on these cursors to extract
       
  1920 ** data from the various tables of the loop.
       
  1921 **
       
  1922 ** If the WHERE clause is empty, the foreach loops must each scan their
       
  1923 ** entire tables.  Thus a three-way join is an O(N^3) operation.  But if
       
  1924 ** the tables have indices and there are terms in the WHERE clause that
       
  1925 ** refer to those indices, a complete table scan can be avoided and the
       
  1926 ** code will run much faster.  Most of the work of this routine is checking
       
  1927 ** to see if there are indices that can be used to speed up the loop.
       
  1928 **
       
  1929 ** Terms of the WHERE clause are also used to limit which rows actually
       
  1930 ** make it to the "..." in the middle of the loop.  After each "foreach",
       
  1931 ** terms of the WHERE clause that use only terms in that loop and outer
       
  1932 ** loops are evaluated and if false a jump is made around all subsequent
       
  1933 ** inner loops (or around the "..." if the test occurs within the inner-
       
  1934 ** most loop)
       
  1935 **
       
  1936 ** OUTER JOINS
       
  1937 **
       
  1938 ** An outer join of tables t1 and t2 is conceptally coded as follows:
       
  1939 **
       
  1940 **    foreach row1 in t1 do
       
  1941 **      flag = 0
       
  1942 **      foreach row2 in t2 do
       
  1943 **        start:
       
  1944 **          ...
       
  1945 **          flag = 1
       
  1946 **      end
       
  1947 **      if flag==0 then
       
  1948 **        move the row2 cursor to a null row
       
  1949 **        goto start
       
  1950 **      fi
       
  1951 **    end
       
  1952 **
       
  1953 ** ORDER BY CLAUSE PROCESSING
       
  1954 **
       
  1955 ** *ppOrderBy is a pointer to the ORDER BY clause of a SELECT statement,
       
  1956 ** if there is one.  If there is no ORDER BY clause or if this routine
       
  1957 ** is called from an UPDATE or DELETE statement, then ppOrderBy is NULL.
       
  1958 **
       
  1959 ** If an index can be used so that the natural output order of the table
       
  1960 ** scan is correct for the ORDER BY clause, then that index is used and
       
  1961 ** *ppOrderBy is set to NULL.  This is an optimization that prevents an
       
  1962 ** unnecessary sort of the result set if an index appropriate for the
       
  1963 ** ORDER BY clause already exists.
       
  1964 **
       
  1965 ** If the where clause loops cannot be arranged to provide the correct
       
  1966 ** output order, then the *ppOrderBy is unchanged.
       
  1967 */
       
  1968 WhereInfo *sqlite3WhereBegin(
       
  1969   Parse *pParse,        /* The parser context */
       
  1970   SrcList *pTabList,    /* A list of all tables to be scanned */
       
  1971   Expr *pWhere,         /* The WHERE clause */
       
  1972   ExprList **ppOrderBy  /* An ORDER BY clause, or NULL */
       
  1973 ){
       
  1974   int i;                     /* Loop counter */
       
  1975   WhereInfo *pWInfo;         /* Will become the return value of this function */
       
  1976   Vdbe *v = pParse->pVdbe;   /* The virtual database engine */
       
  1977   int brk, cont = 0;         /* Addresses used during code generation */
       
  1978   Bitmask notReady;          /* Cursors that are not yet positioned */
       
  1979   WhereTerm *pTerm;          /* A single term in the WHERE clause */
       
  1980   ExprMaskSet maskSet;       /* The expression mask set */
       
  1981   WhereClause wc;            /* The WHERE clause is divided into these terms */
       
  1982   SrcList::SrcList_item *pTabItem;  /* A single entry from pTabList */
       
  1983   WhereLevel *pLevel;             /* A single level in the pWInfo list */
       
  1984   int iFrom;                      /* First unused FROM clause element */
       
  1985   int andFlags;              /* AND-ed combination of all wc.a[].flags */
       
  1986   sqlite3 *db;               /* Database connection */
       
  1987 
       
  1988   /* The number of tables in the FROM clause is limited by the number of
       
  1989   ** bits in a Bitmask 
       
  1990   */
       
  1991   if( pTabList->nSrc>BMS ){
       
  1992     sqlite3ErrorMsg(pParse, "at most %d tables in a join", BMS);
       
  1993     return 0;
       
  1994   }
       
  1995 
       
  1996   /* Split the WHERE clause into separate subexpressions where each
       
  1997   ** subexpression is separated by an AND operator.
       
  1998   */
       
  1999   initMaskSet(&maskSet);
       
  2000   whereClauseInit(&wc, pParse, &maskSet);
       
  2001   whereSplit(&wc, pWhere, TK_AND);
       
  2002     
       
  2003   /* Allocate and initialize the WhereInfo structure that will become the
       
  2004   ** return value.
       
  2005   */
       
  2006   db = pParse->db;
       
  2007   pWInfo = (WhereInfo*)sqlite3DbMallocZero(db,  
       
  2008                       sizeof(WhereInfo) + pTabList->nSrc*sizeof(WhereLevel));
       
  2009   if( db->mallocFailed ){
       
  2010     goto whereBeginNoMem;
       
  2011   }
       
  2012   pWInfo->nLevel = pTabList->nSrc;
       
  2013   pWInfo->pParse = pParse;
       
  2014   pWInfo->pTabList = pTabList;
       
  2015   pWInfo->iBreak = sqlite3VdbeMakeLabel(v);
       
  2016 
       
  2017   /* Special case: a WHERE clause that is constant.  Evaluate the
       
  2018   ** expression and either jump over all of the code or fall thru.
       
  2019   */
       
  2020   if( pWhere && (pTabList->nSrc==0 || sqlite3ExprIsConstantNotJoin(pWhere)) ){
       
  2021     sqlite3ExprIfFalse(pParse, pWhere, pWInfo->iBreak, 1);
       
  2022     pWhere = 0;
       
  2023   }
       
  2024 
       
  2025   /* Analyze all of the subexpressions.  Note that exprAnalyze() might
       
  2026   ** add new virtual terms onto the end of the WHERE clause.  We do not
       
  2027   ** want to analyze these virtual terms, so start analyzing at the end
       
  2028   ** and work forward so that the added virtual terms are never processed.
       
  2029   */
       
  2030   for(i=0; i<pTabList->nSrc; i++){
       
  2031     createMask(&maskSet, pTabList->a[i].iCursor);
       
  2032   }
       
  2033   exprAnalyzeAll(pTabList, &wc);
       
  2034   if( db->mallocFailed ){
       
  2035     goto whereBeginNoMem;
       
  2036   }
       
  2037 
       
  2038   /* Chose the best index to use for each table in the FROM clause.
       
  2039   **
       
  2040   ** This loop fills in the following fields:
       
  2041   **
       
  2042   **   pWInfo->a[].pIdx      The index to use for this level of the loop.
       
  2043   **   pWInfo->a[].flags     WHERE_xxx flags associated with pIdx
       
  2044   **   pWInfo->a[].nEq       The number of == and IN constraints
       
  2045   **   pWInfo->a[].iFrom     When term of the FROM clause is being coded
       
  2046   **   pWInfo->a[].iTabCur   The VDBE cursor for the database table
       
  2047   **   pWInfo->a[].iIdxCur   The VDBE cursor for the index
       
  2048   **
       
  2049   ** This loop also figures out the nesting order of tables in the FROM
       
  2050   ** clause.
       
  2051   */
       
  2052   notReady = ~(Bitmask)0;
       
  2053   pTabItem = pTabList->a;
       
  2054   pLevel = pWInfo->a;
       
  2055   andFlags = ~0;
       
  2056   WHERETRACE(("*** Optimizer Start ***\n"));
       
  2057   for(i=iFrom=0, pLevel=pWInfo->a; i<pTabList->nSrc; i++, pLevel++){
       
  2058     Index *pIdx;                /* Index for FROM table at pTabItem */
       
  2059     int flags;                  /* Flags asssociated with pIdx */
       
  2060     int nEq;                    /* Number of == or IN constraints */
       
  2061     double cost;                /* The cost for pIdx */
       
  2062     int j;                      /* For looping over FROM tables */
       
  2063     Index *pBest = 0;           /* The best index seen so far */
       
  2064     int bestFlags = 0;          /* Flags associated with pBest */
       
  2065     int bestNEq = 0;            /* nEq associated with pBest */
       
  2066     double lowestCost;          /* Cost of the pBest */
       
  2067     int bestJ = 0;              /* The value of j */
       
  2068     Bitmask m;                  /* Bitmask value for j or bestJ */
       
  2069     int once = 0;               /* True when first table is seen */
       
  2070     sqlite3_index_info *pIndex; /* Current virtual index */
       
  2071 
       
  2072     lowestCost = SQLITE_BIG_DBL;
       
  2073     for(j=iFrom, pTabItem=&pTabList->a[j]; j<pTabList->nSrc; j++, pTabItem++){
       
  2074       int doNotReorder;  /* True if this table should not be reordered */
       
  2075 
       
  2076       doNotReorder =  (pTabItem->jointype & (JT_LEFT|JT_CROSS))!=0;
       
  2077       if( once && doNotReorder ) break;
       
  2078       m = getMask(&maskSet, pTabItem->iCursor);
       
  2079       if( (m & notReady)==0 ){
       
  2080         if( j==iFrom ) iFrom++;
       
  2081         continue;
       
  2082       }
       
  2083       assert( pTabItem->pTab );
       
  2084 #ifndef SQLITE_OMIT_VIRTUALTABLE
       
  2085       if( IsVirtual(pTabItem->pTab) ){
       
  2086         sqlite3_index_info **ppIdxInfo = &pWInfo->a[j].pIdxInfo;
       
  2087         cost = bestVirtualIndex(pParse, &wc, pTabItem, notReady,
       
  2088                                 ppOrderBy ? *ppOrderBy : 0, i==0,
       
  2089                                 ppIdxInfo);
       
  2090         flags = WHERE_VIRTUALTABLE;
       
  2091         pIndex = *ppIdxInfo;
       
  2092         if( pIndex && pIndex->orderByConsumed ){
       
  2093           flags = WHERE_VIRTUALTABLE | WHERE_ORDERBY;
       
  2094         }
       
  2095         pIdx = 0;
       
  2096         nEq = 0;
       
  2097         if( (SQLITE_BIG_DBL/2.0)<cost ){
       
  2098           /* The cost is not allowed to be larger than SQLITE_BIG_DBL (the
       
  2099           ** inital value of lowestCost in this loop. If it is, then
       
  2100           ** the (cost<lowestCost) test below will never be true and
       
  2101           ** pLevel->pBestIdx never set.
       
  2102           */ 
       
  2103           cost = (SQLITE_BIG_DBL/2.0);
       
  2104         }
       
  2105       }else 
       
  2106 #endif
       
  2107       {
       
  2108         cost = bestIndex(pParse, &wc, pTabItem, notReady,
       
  2109                          (i==0 && ppOrderBy) ? *ppOrderBy : 0,
       
  2110                          &pIdx, &flags, &nEq);
       
  2111         pIndex = 0;
       
  2112       }
       
  2113       if( cost<lowestCost ){
       
  2114         once = 1;
       
  2115         lowestCost = cost;
       
  2116         pBest = pIdx;
       
  2117         bestFlags = flags;
       
  2118         bestNEq = nEq;
       
  2119         bestJ = j;
       
  2120         pLevel->pBestIdx = pIndex;
       
  2121       }
       
  2122       if( doNotReorder ) break;
       
  2123     }
       
  2124     WHERETRACE(("*** Optimizer choose table %d for loop %d\n", bestJ,
       
  2125            pLevel-pWInfo->a));
       
  2126     if( (bestFlags & WHERE_ORDERBY)!=0 ){
       
  2127       *ppOrderBy = 0;
       
  2128     }
       
  2129     andFlags &= bestFlags;
       
  2130     pLevel->flags = bestFlags;
       
  2131     pLevel->pIdx = pBest;
       
  2132     pLevel->nEq = bestNEq;
       
  2133     pLevel->aInLoop = 0;
       
  2134     pLevel->nIn = 0;
       
  2135     if( pBest ){
       
  2136       pLevel->iIdxCur = pParse->nTab++;
       
  2137     }else{
       
  2138       pLevel->iIdxCur = -1;
       
  2139     }
       
  2140     notReady &= ~getMask(&maskSet, pTabList->a[bestJ].iCursor);
       
  2141     pLevel->iFrom = bestJ;
       
  2142   }
       
  2143   WHERETRACE(("*** Optimizer Finished ***\n"));
       
  2144 
       
  2145   /* If the total query only selects a single row, then the ORDER BY
       
  2146   ** clause is irrelevant.
       
  2147   */
       
  2148   if( (andFlags & WHERE_UNIQUE)!=0 && ppOrderBy ){
       
  2149     *ppOrderBy = 0;
       
  2150   }
       
  2151 
       
  2152   /* Open all tables in the pTabList and any indices selected for
       
  2153   ** searching those tables.
       
  2154   */
       
  2155   sqlite3CodeVerifySchema(pParse, -1); /* Insert the cookie verifier Goto */
       
  2156   for(i=0, pLevel=pWInfo->a; i<pTabList->nSrc; i++, pLevel++){
       
  2157     Table *pTab;     /* Table to open */
       
  2158     Index *pIx;      /* Index used to access pTab (if any) */
       
  2159     int iDb;         /* Index of database containing table/index */
       
  2160     int iIdxCur = pLevel->iIdxCur;
       
  2161 
       
  2162 #ifndef SQLITE_OMIT_EXPLAIN
       
  2163     if( pParse->explain==2 ){
       
  2164       char *zMsg;
       
  2165 	  SrcList::SrcList_item *pItem = &pTabList->a[pLevel->iFrom];
       
  2166       zMsg = sqlite3MPrintf(db, "TABLE %s", pItem->zName);
       
  2167       if( pItem->zAlias ){
       
  2168         zMsg = sqlite3MPrintf(db, "%z AS %s", zMsg, pItem->zAlias);
       
  2169       }
       
  2170       if( (pIx = pLevel->pIdx)!=0 ){
       
  2171         zMsg = sqlite3MPrintf(db, "%z WITH INDEX %s", zMsg, pIx->zName);
       
  2172       }else if( pLevel->flags & (WHERE_ROWID_EQ|WHERE_ROWID_RANGE) ){
       
  2173         zMsg = sqlite3MPrintf(db, "%z USING PRIMARY KEY", zMsg);
       
  2174       }
       
  2175 #ifndef SQLITE_OMIT_VIRTUALTABLE
       
  2176       else if( pLevel->pBestIdx ){
       
  2177         sqlite3_index_info *pBestIdx = pLevel->pBestIdx;
       
  2178         zMsg = sqlite3MPrintf(db, "%z VIRTUAL TABLE INDEX %d:%s", zMsg,
       
  2179                     pBestIdx->idxNum, pBestIdx->idxStr);
       
  2180       }
       
  2181 #endif
       
  2182       if( pLevel->flags & WHERE_ORDERBY ){
       
  2183         zMsg = sqlite3MPrintf(db, "%z ORDER BY", zMsg);
       
  2184       }
       
  2185       sqlite3VdbeOp3(v, OP_Explain, i, pLevel->iFrom, zMsg, P3_DYNAMIC);
       
  2186     }
       
  2187 #endif /* SQLITE_OMIT_EXPLAIN */
       
  2188     pTabItem = &pTabList->a[pLevel->iFrom];
       
  2189     pTab = pTabItem->pTab;
       
  2190     iDb = sqlite3SchemaToIndex(pParse->db, pTab->pSchema);
       
  2191     if( pTab->isEphem || pTab->pSelect ) continue;
       
  2192 #ifndef SQLITE_OMIT_VIRTUALTABLE
       
  2193     if( pLevel->pBestIdx ){
       
  2194       int iCur = pTabItem->iCursor;
       
  2195       sqlite3VdbeOp3(v, OP_VOpen, iCur, 0, (const char*)pTab->pVtab, P3_VTAB);
       
  2196     }else
       
  2197 #endif
       
  2198     if( (pLevel->flags & WHERE_IDX_ONLY)==0 ){
       
  2199       sqlite3OpenTable(pParse, pTabItem->iCursor, iDb, pTab, OP_OpenRead);
       
  2200       if( pTab->nCol<(sizeof(Bitmask)*8) ){
       
  2201         Bitmask b = pTabItem->colUsed;
       
  2202         int n = 0;
       
  2203         for(; b; b=b>>1, n++){}
       
  2204         sqlite3VdbeChangeP2(v, sqlite3VdbeCurrentAddr(v)-1, n);
       
  2205         assert( n<=pTab->nCol );
       
  2206       }
       
  2207     }else{
       
  2208       sqlite3TableLock(pParse, iDb, pTab->tnum, 0, pTab->zName);
       
  2209     }
       
  2210     pLevel->iTabCur = pTabItem->iCursor;
       
  2211     if( (pIx = pLevel->pIdx)!=0 ){
       
  2212       KeyInfo *pKey = sqlite3IndexKeyinfo(pParse, pIx);
       
  2213       assert( pIx->pSchema==pTab->pSchema );
       
  2214       sqlite3VdbeAddOp(v, OP_Integer, iDb, 0);
       
  2215       VdbeComment((v, "# %s", pIx->zName));
       
  2216       sqlite3VdbeOp3(v, OP_OpenRead, iIdxCur, pIx->tnum,
       
  2217                      (char*)pKey, P3_KEYINFO_HANDOFF);
       
  2218       sqlite3VdbeAddOp(v, OP_SetNumColumns, iIdxCur, pIx->nColumn+1);
       
  2219     }
       
  2220     sqlite3CodeVerifySchema(pParse, iDb);
       
  2221   }
       
  2222   pWInfo->iTop = sqlite3VdbeCurrentAddr(v);
       
  2223 
       
  2224   /* Generate the code to do the search.  Each iteration of the for
       
  2225   ** loop below generates code for a single nested loop of the VM
       
  2226   ** program.
       
  2227   */
       
  2228   notReady = ~(Bitmask)0;
       
  2229   for(i=0, pLevel=pWInfo->a; i<pTabList->nSrc; i++, pLevel++){
       
  2230     int j;
       
  2231     int iCur = pTabItem->iCursor;  /* The VDBE cursor for the table */
       
  2232     Index *pIdx;       /* The index we will be using */
       
  2233     int nxt;           /* Where to jump to continue with the next IN case */
       
  2234     int iIdxCur;       /* The VDBE cursor for the index */
       
  2235     int omitTable;     /* True if we use the index only */
       
  2236     int bRev;          /* True if we need to scan in reverse order */
       
  2237 
       
  2238     pTabItem = &pTabList->a[pLevel->iFrom];
       
  2239     iCur = pTabItem->iCursor;
       
  2240     pIdx = pLevel->pIdx;
       
  2241     iIdxCur = pLevel->iIdxCur;
       
  2242     bRev = (pLevel->flags & WHERE_REVERSE)!=0;
       
  2243     omitTable = (pLevel->flags & WHERE_IDX_ONLY)!=0;
       
  2244 
       
  2245     /* Create labels for the "break" and "continue" instructions
       
  2246     ** for the current loop.  Jump to brk to break out of a loop.
       
  2247     ** Jump to cont to go immediately to the next iteration of the
       
  2248     ** loop.
       
  2249     **
       
  2250     ** When there is an IN operator, we also have a "nxt" label that
       
  2251     ** means to continue with the next IN value combination.  When
       
  2252     ** there are no IN operators in the constraints, the "nxt" label
       
  2253     ** is the same as "brk".
       
  2254     */
       
  2255     brk = pLevel->brk = pLevel->nxt = sqlite3VdbeMakeLabel(v);
       
  2256     cont = pLevel->cont = sqlite3VdbeMakeLabel(v);
       
  2257 
       
  2258     /* If this is the right table of a LEFT OUTER JOIN, allocate and
       
  2259     ** initialize a memory cell that records if this table matches any
       
  2260     ** row of the left table of the join.
       
  2261     */
       
  2262     if( pLevel->iFrom>0 && (pTabItem[0].jointype & JT_LEFT)!=0 ){
       
  2263       if( !pParse->nMem ) pParse->nMem++;
       
  2264       pLevel->iLeftJoin = pParse->nMem++;
       
  2265       sqlite3VdbeAddOp(v, OP_MemInt, 0, pLevel->iLeftJoin);
       
  2266       VdbeComment((v, "# init LEFT JOIN no-match flag"));
       
  2267     }
       
  2268 
       
  2269 #ifndef SQLITE_OMIT_VIRTUALTABLE
       
  2270     if( pLevel->pBestIdx ){
       
  2271       /* Case 0:  The table is a virtual-table.  Use the VFilter and VNext
       
  2272       **          to access the data.
       
  2273       */
       
  2274       int j;
       
  2275       sqlite3_index_info *pBestIdx = pLevel->pBestIdx;
       
  2276       int nConstraint = pBestIdx->nConstraint;
       
  2277 	  sqlite3_index_info::sqlite3_index_constraint_usage *aUsage =
       
  2278                                                   pBestIdx->aConstraintUsage;
       
  2279 	  const sqlite3_index_info::sqlite3_index_constraint *aConstraint =
       
  2280                                                   pBestIdx->aConstraint;
       
  2281 
       
  2282       for(j=1; j<=nConstraint; j++){
       
  2283         int k;
       
  2284         for(k=0; k<nConstraint; k++){
       
  2285           if( aUsage[k].argvIndex==j ){
       
  2286             int iTerm = aConstraint[k].iTermOffset;
       
  2287             sqlite3ExprCode(pParse, wc.a[iTerm].pExpr->pRight);
       
  2288             break;
       
  2289           }
       
  2290         }
       
  2291         if( k==nConstraint ) break;
       
  2292       }
       
  2293       sqlite3VdbeAddOp(v, OP_Integer, j-1, 0);
       
  2294       sqlite3VdbeAddOp(v, OP_Integer, pBestIdx->idxNum, 0);
       
  2295       sqlite3VdbeOp3(v, OP_VFilter, iCur, brk, pBestIdx->idxStr,
       
  2296                       pBestIdx->needToFreeIdxStr ? P3_MPRINTF : P3_STATIC);
       
  2297       pBestIdx->needToFreeIdxStr = 0;
       
  2298       for(j=0; j<pBestIdx->nConstraint; j++){
       
  2299         if( aUsage[j].omit ){
       
  2300           int iTerm = aConstraint[j].iTermOffset;
       
  2301           disableTerm(pLevel, &wc.a[iTerm]);
       
  2302         }
       
  2303       }
       
  2304       pLevel->op = OP_VNext;
       
  2305       pLevel->p1 = iCur;
       
  2306       pLevel->p2 = sqlite3VdbeCurrentAddr(v);
       
  2307     }else
       
  2308 #endif /* SQLITE_OMIT_VIRTUALTABLE */
       
  2309 
       
  2310     if( pLevel->flags & WHERE_ROWID_EQ ){
       
  2311       /* Case 1:  We can directly reference a single row using an
       
  2312       **          equality comparison against the ROWID field.  Or
       
  2313       **          we reference multiple rows using a "rowid IN (...)"
       
  2314       **          construct.
       
  2315       */
       
  2316       pTerm = findTerm(&wc, iCur, -1, notReady, WO_EQ|WO_IN, 0);
       
  2317       assert( pTerm!=0 );
       
  2318       assert( pTerm->pExpr!=0 );
       
  2319       assert( pTerm->leftCursor==iCur );
       
  2320       assert( omitTable==0 );
       
  2321       codeEqualityTerm(pParse, pTerm, pLevel);
       
  2322       nxt = pLevel->nxt;
       
  2323       sqlite3VdbeAddOp(v, OP_MustBeInt, 1, nxt);
       
  2324       sqlite3VdbeAddOp(v, OP_NotExists, iCur, nxt);
       
  2325       VdbeComment((v, "pk"));
       
  2326       pLevel->op = OP_Noop;
       
  2327     }else if( pLevel->flags & WHERE_ROWID_RANGE ){
       
  2328       /* Case 2:  We have an inequality comparison against the ROWID field.
       
  2329       */
       
  2330       int testOp = OP_Noop;
       
  2331       int start;
       
  2332       WhereTerm *pStart, *pEnd;
       
  2333 
       
  2334       assert( omitTable==0 );
       
  2335       pStart = findTerm(&wc, iCur, -1, notReady, WO_GT|WO_GE, 0);
       
  2336       pEnd = findTerm(&wc, iCur, -1, notReady, WO_LT|WO_LE, 0);
       
  2337       if( bRev ){
       
  2338         pTerm = pStart;
       
  2339         pStart = pEnd;
       
  2340         pEnd = pTerm;
       
  2341       }
       
  2342       if( pStart ){
       
  2343         Expr *pX;
       
  2344         pX = pStart->pExpr;
       
  2345         assert( pX!=0 );
       
  2346         assert( pStart->leftCursor==iCur );
       
  2347         sqlite3ExprCode(pParse, pX->pRight);
       
  2348         sqlite3VdbeAddOp(v, OP_ForceInt, pX->op==TK_LE || pX->op==TK_GT, brk);
       
  2349         sqlite3VdbeAddOp(v, bRev ? OP_MoveLt : OP_MoveGe, iCur, brk);
       
  2350         VdbeComment((v, "pk"));
       
  2351         disableTerm(pLevel, pStart);
       
  2352       }else{
       
  2353         sqlite3VdbeAddOp(v, bRev ? OP_Last : OP_Rewind, iCur, brk);
       
  2354       }
       
  2355       if( pEnd ){
       
  2356         Expr *pX;
       
  2357         pX = pEnd->pExpr;
       
  2358         assert( pX!=0 );
       
  2359         assert( pEnd->leftCursor==iCur );
       
  2360         sqlite3ExprCode(pParse, pX->pRight);
       
  2361         pLevel->iMem = pParse->nMem++;
       
  2362         sqlite3VdbeAddOp(v, OP_MemStore, pLevel->iMem, 1);
       
  2363         if( pX->op==TK_LT || pX->op==TK_GT ){
       
  2364           testOp = bRev ? OP_Le : OP_Ge;
       
  2365         }else{
       
  2366           testOp = bRev ? OP_Lt : OP_Gt;
       
  2367         }
       
  2368         disableTerm(pLevel, pEnd);
       
  2369       }
       
  2370       start = sqlite3VdbeCurrentAddr(v);
       
  2371       pLevel->op = bRev ? OP_Prev : OP_Next;
       
  2372       pLevel->p1 = iCur;
       
  2373       pLevel->p2 = start;
       
  2374       if( testOp!=OP_Noop ){
       
  2375         sqlite3VdbeAddOp(v, OP_Rowid, iCur, 0);
       
  2376         sqlite3VdbeAddOp(v, OP_MemLoad, pLevel->iMem, 0);
       
  2377         sqlite3VdbeAddOp(v, testOp, SQLITE_AFF_NUMERIC|0x100, brk);
       
  2378       }
       
  2379     }else if( pLevel->flags & WHERE_COLUMN_RANGE ){
       
  2380       /* Case 3: The WHERE clause term that refers to the right-most
       
  2381       **         column of the index is an inequality.  For example, if
       
  2382       **         the index is on (x,y,z) and the WHERE clause is of the
       
  2383       **         form "x=5 AND y<10" then this case is used.  Only the
       
  2384       **         right-most column can be an inequality - the rest must
       
  2385       **         use the "==" and "IN" operators.
       
  2386       **
       
  2387       **         This case is also used when there are no WHERE clause
       
  2388       **         constraints but an index is selected anyway, in order
       
  2389       **         to force the output order to conform to an ORDER BY.
       
  2390       */
       
  2391       int start;
       
  2392       int nEq = pLevel->nEq;
       
  2393       int topEq=0;        /* True if top limit uses ==. False is strictly < */
       
  2394       int btmEq=0;        /* True if btm limit uses ==. False if strictly > */
       
  2395       int topOp, btmOp;   /* Operators for the top and bottom search bounds */
       
  2396       int testOp;
       
  2397       int topLimit = (pLevel->flags & WHERE_TOP_LIMIT)!=0;
       
  2398       int btmLimit = (pLevel->flags & WHERE_BTM_LIMIT)!=0;
       
  2399 
       
  2400       /* Generate code to evaluate all constraint terms using == or IN
       
  2401       ** and level the values of those terms on the stack.
       
  2402       */
       
  2403       codeAllEqualityTerms(pParse, pLevel, &wc, notReady);
       
  2404 
       
  2405       /* Duplicate the equality term values because they will all be
       
  2406       ** used twice: once to make the termination key and once to make the
       
  2407       ** start key.
       
  2408       */
       
  2409       for(j=0; j<nEq; j++){
       
  2410         sqlite3VdbeAddOp(v, OP_Dup, nEq-1, 0);
       
  2411       }
       
  2412 
       
  2413       /* Figure out what comparison operators to use for top and bottom 
       
  2414       ** search bounds. For an ascending index, the bottom bound is a > or >=
       
  2415       ** operator and the top bound is a < or <= operator.  For a descending
       
  2416       ** index the operators are reversed.
       
  2417       */
       
  2418       if( pIdx->aSortOrder[nEq]==SQLITE_SO_ASC ){
       
  2419         topOp = WO_LT|WO_LE;
       
  2420         btmOp = WO_GT|WO_GE;
       
  2421       }else{
       
  2422         topOp = WO_GT|WO_GE;
       
  2423         btmOp = WO_LT|WO_LE;
       
  2424         SWAP(int, topLimit, btmLimit);
       
  2425       }
       
  2426 
       
  2427       /* Generate the termination key.  This is the key value that
       
  2428       ** will end the search.  There is no termination key if there
       
  2429       ** are no equality terms and no "X<..." term.
       
  2430       **
       
  2431       ** 2002-Dec-04: On a reverse-order scan, the so-called "termination"
       
  2432       ** key computed here really ends up being the start key.
       
  2433       */
       
  2434       nxt = pLevel->nxt;
       
  2435       if( topLimit ){
       
  2436         Expr *pX;
       
  2437         int k = pIdx->aiColumn[j];
       
  2438         pTerm = findTerm(&wc, iCur, k, notReady, topOp, pIdx);
       
  2439         assert( pTerm!=0 );
       
  2440         pX = pTerm->pExpr;
       
  2441         assert( (pTerm->flags & TERM_CODED)==0 );
       
  2442         sqlite3ExprCode(pParse, pX->pRight);
       
  2443         sqlite3VdbeAddOp(v, OP_IsNull, -(nEq*2+1), nxt);
       
  2444         topEq = pTerm->eOperator & (WO_LE|WO_GE);
       
  2445         disableTerm(pLevel, pTerm);
       
  2446         testOp = OP_IdxGE;
       
  2447       }else{
       
  2448         testOp = nEq>0 ? OP_IdxGE : OP_Noop;
       
  2449         topEq = 1;
       
  2450       }
       
  2451       if( testOp!=OP_Noop ){
       
  2452         int nCol = nEq + topLimit;
       
  2453         pLevel->iMem = pParse->nMem++;
       
  2454         buildIndexProbe(v, nCol, pIdx);
       
  2455         if( bRev ){
       
  2456           int op = topEq ? OP_MoveLe : OP_MoveLt;
       
  2457           sqlite3VdbeAddOp(v, op, iIdxCur, nxt);
       
  2458         }else{
       
  2459           sqlite3VdbeAddOp(v, OP_MemStore, pLevel->iMem, 1);
       
  2460         }
       
  2461       }else if( bRev ){
       
  2462         sqlite3VdbeAddOp(v, OP_Last, iIdxCur, brk);
       
  2463       }
       
  2464 
       
  2465       /* Generate the start key.  This is the key that defines the lower
       
  2466       ** bound on the search.  There is no start key if there are no
       
  2467       ** equality terms and if there is no "X>..." term.  In
       
  2468       ** that case, generate a "Rewind" instruction in place of the
       
  2469       ** start key search.
       
  2470       **
       
  2471       ** 2002-Dec-04: In the case of a reverse-order search, the so-called
       
  2472       ** "start" key really ends up being used as the termination key.
       
  2473       */
       
  2474       if( btmLimit ){
       
  2475         Expr *pX;
       
  2476         int k = pIdx->aiColumn[j];
       
  2477         pTerm = findTerm(&wc, iCur, k, notReady, btmOp, pIdx);
       
  2478         assert( pTerm!=0 );
       
  2479         pX = pTerm->pExpr;
       
  2480         assert( (pTerm->flags & TERM_CODED)==0 );
       
  2481         sqlite3ExprCode(pParse, pX->pRight);
       
  2482         sqlite3VdbeAddOp(v, OP_IsNull, -(nEq+1), nxt);
       
  2483         btmEq = pTerm->eOperator & (WO_LE|WO_GE);
       
  2484         disableTerm(pLevel, pTerm);
       
  2485       }else{
       
  2486         btmEq = 1;
       
  2487       }
       
  2488       if( nEq>0 || btmLimit ){
       
  2489         int nCol = nEq + btmLimit;
       
  2490         buildIndexProbe(v, nCol, pIdx);
       
  2491         if( bRev ){
       
  2492           pLevel->iMem = pParse->nMem++;
       
  2493           sqlite3VdbeAddOp(v, OP_MemStore, pLevel->iMem, 1);
       
  2494           testOp = OP_IdxLT;
       
  2495         }else{
       
  2496           int op = btmEq ? OP_MoveGe : OP_MoveGt;
       
  2497           sqlite3VdbeAddOp(v, op, iIdxCur, nxt);
       
  2498         }
       
  2499       }else if( bRev ){
       
  2500         testOp = OP_Noop;
       
  2501       }else{
       
  2502         sqlite3VdbeAddOp(v, OP_Rewind, iIdxCur, brk);
       
  2503       }
       
  2504 
       
  2505       /* Generate the the top of the loop.  If there is a termination
       
  2506       ** key we have to test for that key and abort at the top of the
       
  2507       ** loop.
       
  2508       */
       
  2509       start = sqlite3VdbeCurrentAddr(v);
       
  2510       if( testOp!=OP_Noop ){
       
  2511         sqlite3VdbeAddOp(v, OP_MemLoad, pLevel->iMem, 0);
       
  2512         sqlite3VdbeAddOp(v, testOp, iIdxCur, nxt);
       
  2513         if( (topEq && !bRev) || (!btmEq && bRev) ){
       
  2514           sqlite3VdbeChangeP3(v, -1, "+", P3_STATIC);
       
  2515         }
       
  2516       }
       
  2517       if( topLimit | btmLimit ){
       
  2518         sqlite3VdbeAddOp(v, OP_Column, iIdxCur, nEq);
       
  2519         sqlite3VdbeAddOp(v, OP_IsNull, 1, cont);
       
  2520       }
       
  2521       if( !omitTable ){
       
  2522         sqlite3VdbeAddOp(v, OP_IdxRowid, iIdxCur, 0);
       
  2523         sqlite3VdbeAddOp(v, OP_MoveGe, iCur, 0);
       
  2524       }
       
  2525 
       
  2526       /* Record the instruction used to terminate the loop.
       
  2527       */
       
  2528       pLevel->op = bRev ? OP_Prev : OP_Next;
       
  2529       pLevel->p1 = iIdxCur;
       
  2530       pLevel->p2 = start;
       
  2531     }else if( pLevel->flags & WHERE_COLUMN_EQ ){
       
  2532       /* Case 4:  There is an index and all terms of the WHERE clause that
       
  2533       **          refer to the index using the "==" or "IN" operators.
       
  2534       */
       
  2535       int start;
       
  2536       int nEq = pLevel->nEq;
       
  2537 
       
  2538       /* Generate code to evaluate all constraint terms using == or IN
       
  2539       ** and leave the values of those terms on the stack.
       
  2540       */
       
  2541       codeAllEqualityTerms(pParse, pLevel, &wc, notReady);
       
  2542       nxt = pLevel->nxt;
       
  2543 
       
  2544       /* Generate a single key that will be used to both start and terminate
       
  2545       ** the search
       
  2546       */
       
  2547       buildIndexProbe(v, nEq, pIdx);
       
  2548       sqlite3VdbeAddOp(v, OP_MemStore, pLevel->iMem, 0);
       
  2549 
       
  2550       /* Generate code (1) to move to the first matching element of the table.
       
  2551       ** Then generate code (2) that jumps to "nxt" after the cursor is past
       
  2552       ** the last matching element of the table.  The code (1) is executed
       
  2553       ** once to initialize the search, the code (2) is executed before each
       
  2554       ** iteration of the scan to see if the scan has finished. */
       
  2555       if( bRev ){
       
  2556         /* Scan in reverse order */
       
  2557         sqlite3VdbeAddOp(v, OP_MoveLe, iIdxCur, nxt);
       
  2558         start = sqlite3VdbeAddOp(v, OP_MemLoad, pLevel->iMem, 0);
       
  2559         sqlite3VdbeAddOp(v, OP_IdxLT, iIdxCur, nxt);
       
  2560         pLevel->op = OP_Prev;
       
  2561       }else{
       
  2562         /* Scan in the forward order */
       
  2563         sqlite3VdbeAddOp(v, OP_MoveGe, iIdxCur, nxt);
       
  2564         start = sqlite3VdbeAddOp(v, OP_MemLoad, pLevel->iMem, 0);
       
  2565         sqlite3VdbeOp3(v, OP_IdxGE, iIdxCur, nxt, "+", P3_STATIC);
       
  2566         pLevel->op = OP_Next;
       
  2567       }
       
  2568       if( !omitTable ){
       
  2569         sqlite3VdbeAddOp(v, OP_IdxRowid, iIdxCur, 0);
       
  2570         sqlite3VdbeAddOp(v, OP_MoveGe, iCur, 0);
       
  2571       }
       
  2572       pLevel->p1 = iIdxCur;
       
  2573       pLevel->p2 = start;
       
  2574     }else{
       
  2575       /* Case 5:  There is no usable index.  We must do a complete
       
  2576       **          scan of the entire table.
       
  2577       */
       
  2578       assert( omitTable==0 );
       
  2579       assert( bRev==0 );
       
  2580       pLevel->op = OP_Next;
       
  2581       pLevel->p1 = iCur;
       
  2582       pLevel->p2 = 1 + sqlite3VdbeAddOp(v, OP_Rewind, iCur, brk);
       
  2583     }
       
  2584     notReady &= ~getMask(&maskSet, iCur);
       
  2585     sqlite3VdbeAddOp(v, OP_StackDepth, -1, 0);
       
  2586 
       
  2587     /* Insert code to test every subexpression that can be completely
       
  2588     ** computed using the current set of tables.
       
  2589     */
       
  2590     for(pTerm=wc.a, j=wc.nTerm; j>0; j--, pTerm++){
       
  2591       Expr *pE;
       
  2592       if( pTerm->flags & (TERM_VIRTUAL|TERM_CODED) ) continue;
       
  2593       if( (pTerm->prereqAll & notReady)!=0 ) continue;
       
  2594       pE = pTerm->pExpr;
       
  2595       assert( pE!=0 );
       
  2596       if( pLevel->iLeftJoin && !ExprHasProperty(pE, EP_FromJoin) ){
       
  2597         continue;
       
  2598       }
       
  2599       sqlite3ExprIfFalse(pParse, pE, cont, 1);
       
  2600       pTerm->flags |= TERM_CODED;
       
  2601     }
       
  2602 
       
  2603     /* For a LEFT OUTER JOIN, generate code that will record the fact that
       
  2604     ** at least one row of the right table has matched the left table.  
       
  2605     */
       
  2606     if( pLevel->iLeftJoin ){
       
  2607       pLevel->top = sqlite3VdbeCurrentAddr(v);
       
  2608       sqlite3VdbeAddOp(v, OP_MemInt, 1, pLevel->iLeftJoin);
       
  2609       VdbeComment((v, "# record LEFT JOIN hit"));
       
  2610       for(pTerm=wc.a, j=0; j<wc.nTerm; j++, pTerm++){
       
  2611         if( pTerm->flags & (TERM_VIRTUAL|TERM_CODED) ) continue;
       
  2612         if( (pTerm->prereqAll & notReady)!=0 ) continue;
       
  2613         assert( pTerm->pExpr );
       
  2614         sqlite3ExprIfFalse(pParse, pTerm->pExpr, cont, 1);
       
  2615         pTerm->flags |= TERM_CODED;
       
  2616       }
       
  2617     }
       
  2618   }
       
  2619 
       
  2620 #ifdef SQLITE_TEST  /* For testing and debugging use only */
       
  2621   /* Record in the query plan information about the current table
       
  2622   ** and the index used to access it (if any).  If the table itself
       
  2623   ** is not used, its name is just '{}'.  If no index is used
       
  2624   ** the index is listed as "{}".  If the primary key is used the
       
  2625   ** index name is '*'.
       
  2626   */
       
  2627   for(i=0; i<pTabList->nSrc; i++){
       
  2628     char *z;
       
  2629     int n;
       
  2630     pLevel = &pWInfo->a[i];
       
  2631     pTabItem = &pTabList->a[pLevel->iFrom];
       
  2632     z = pTabItem->zAlias;
       
  2633     if( z==0 ) z = pTabItem->pTab->zName;
       
  2634     n = strlen(z);
       
  2635     if( n+nQPlan < sizeof(sqlite3_query_plan)-10 ){
       
  2636       if( pLevel->flags & WHERE_IDX_ONLY ){
       
  2637         memcpy(&sqlite3_query_plan[nQPlan], "{}", 2);
       
  2638         nQPlan += 2;
       
  2639       }else{
       
  2640         memcpy(&sqlite3_query_plan[nQPlan], z, n);
       
  2641         nQPlan += n;
       
  2642       }
       
  2643       sqlite3_query_plan[nQPlan++] = ' ';
       
  2644     }
       
  2645     if( pLevel->flags & (WHERE_ROWID_EQ|WHERE_ROWID_RANGE) ){
       
  2646       memcpy(&sqlite3_query_plan[nQPlan], "* ", 2);
       
  2647       nQPlan += 2;
       
  2648     }else if( pLevel->pIdx==0 ){
       
  2649       memcpy(&sqlite3_query_plan[nQPlan], "{} ", 3);
       
  2650       nQPlan += 3;
       
  2651     }else{
       
  2652       n = strlen(pLevel->pIdx->zName);
       
  2653       if( n+nQPlan < sizeof(sqlite3_query_plan)-2 ){
       
  2654         memcpy(&sqlite3_query_plan[nQPlan], pLevel->pIdx->zName, n);
       
  2655         nQPlan += n;
       
  2656         sqlite3_query_plan[nQPlan++] = ' ';
       
  2657       }
       
  2658     }
       
  2659   }
       
  2660   while( nQPlan>0 && sqlite3_query_plan[nQPlan-1]==' ' ){
       
  2661     sqlite3_query_plan[--nQPlan] = 0;
       
  2662   }
       
  2663   sqlite3_query_plan[nQPlan] = 0;
       
  2664   nQPlan = 0;
       
  2665 #endif /* SQLITE_TEST // Testing and debugging use only */
       
  2666 
       
  2667   /* Record the continuation address in the WhereInfo structure.  Then
       
  2668   ** clean up and return.
       
  2669   */
       
  2670   pWInfo->iContinue = cont;
       
  2671   whereClauseClear(&wc);
       
  2672   return pWInfo;
       
  2673 
       
  2674   /* Jump here if malloc fails */
       
  2675 whereBeginNoMem:
       
  2676   whereClauseClear(&wc);
       
  2677   whereInfoFree(pWInfo);
       
  2678   return 0;
       
  2679 }
       
  2680 
       
  2681 /*
       
  2682 ** Generate the end of the WHERE loop.  See comments on 
       
  2683 ** sqlite3WhereBegin() for additional information.
       
  2684 */
       
  2685 void sqlite3WhereEnd(WhereInfo *pWInfo){
       
  2686   Vdbe *v = pWInfo->pParse->pVdbe;
       
  2687   int i;
       
  2688   WhereLevel *pLevel;
       
  2689   SrcList *pTabList = pWInfo->pTabList;
       
  2690 
       
  2691   /* Generate loop termination code.
       
  2692   */
       
  2693   for(i=pTabList->nSrc-1; i>=0; i--){
       
  2694     pLevel = &pWInfo->a[i];
       
  2695     sqlite3VdbeResolveLabel(v, pLevel->cont);
       
  2696     if( pLevel->op!=OP_Noop ){
       
  2697       sqlite3VdbeAddOp(v, pLevel->op, pLevel->p1, pLevel->p2);
       
  2698     }
       
  2699     if( pLevel->nIn ){
       
  2700 		WhereLevel::InLoop *pIn;
       
  2701       int j;
       
  2702       sqlite3VdbeResolveLabel(v, pLevel->nxt);
       
  2703       for(j=pLevel->nIn, pIn=&pLevel->aInLoop[j-1]; j>0; j--, pIn--){
       
  2704         sqlite3VdbeJumpHere(v, pIn->topAddr+1);
       
  2705         sqlite3VdbeAddOp(v, OP_Next, pIn->iCur, pIn->topAddr);
       
  2706         sqlite3VdbeJumpHere(v, pIn->topAddr-1);
       
  2707       }
       
  2708       sqlite3_free(pLevel->aInLoop);
       
  2709     }
       
  2710     sqlite3VdbeResolveLabel(v, pLevel->brk);
       
  2711     if( pLevel->iLeftJoin ){
       
  2712       int addr;
       
  2713       addr = sqlite3VdbeAddOp(v, OP_IfMemPos, pLevel->iLeftJoin, 0);
       
  2714       sqlite3VdbeAddOp(v, OP_NullRow, pTabList->a[i].iCursor, 0);
       
  2715       if( pLevel->iIdxCur>=0 ){
       
  2716         sqlite3VdbeAddOp(v, OP_NullRow, pLevel->iIdxCur, 0);
       
  2717       }
       
  2718       sqlite3VdbeAddOp(v, OP_Goto, 0, pLevel->top);
       
  2719       sqlite3VdbeJumpHere(v, addr);
       
  2720     }
       
  2721   }
       
  2722 
       
  2723   /* The "break" point is here, just past the end of the outer loop.
       
  2724   ** Set it.
       
  2725   */
       
  2726   sqlite3VdbeResolveLabel(v, pWInfo->iBreak);
       
  2727 
       
  2728   /* Close all of the cursors that were opened by sqlite3WhereBegin.
       
  2729   */
       
  2730   for(i=0, pLevel=pWInfo->a; i<pTabList->nSrc; i++, pLevel++){
       
  2731 	  SrcList::SrcList_item *pTabItem = &pTabList->a[pLevel->iFrom];
       
  2732     Table *pTab = pTabItem->pTab;
       
  2733     assert( pTab!=0 );
       
  2734     if( pTab->isEphem || pTab->pSelect ) continue;
       
  2735     if( (pLevel->flags & WHERE_IDX_ONLY)==0 ){
       
  2736       sqlite3VdbeAddOp(v, OP_Close, pTabItem->iCursor, 0);
       
  2737     }
       
  2738     if( pLevel->pIdx!=0 ){
       
  2739       sqlite3VdbeAddOp(v, OP_Close, pLevel->iIdxCur, 0);
       
  2740     }
       
  2741 
       
  2742     /* If this scan uses an index, make code substitutions to read data
       
  2743     ** from the index in preference to the table. Sometimes, this means
       
  2744     ** the table need never be read from. This is a performance boost,
       
  2745     ** as the vdbe level waits until the table is read before actually
       
  2746     ** seeking the table cursor to the record corresponding to the current
       
  2747     ** position in the index.
       
  2748     ** 
       
  2749     ** Calls to the code generator in between sqlite3WhereBegin and
       
  2750     ** sqlite3WhereEnd will have created code that references the table
       
  2751     ** directly.  This loop scans all that code looking for opcodes
       
  2752     ** that reference the table and converts them into opcodes that
       
  2753     ** reference the index.
       
  2754     */
       
  2755     if( pLevel->pIdx ){
       
  2756       int k, j, last;
       
  2757       VdbeOp *pOp;
       
  2758       Index *pIdx = pLevel->pIdx;
       
  2759       int useIndexOnly = pLevel->flags & WHERE_IDX_ONLY;
       
  2760 
       
  2761       assert( pIdx!=0 );
       
  2762       pOp = sqlite3VdbeGetOp(v, pWInfo->iTop);
       
  2763       last = sqlite3VdbeCurrentAddr(v);
       
  2764       for(k=pWInfo->iTop; k<last; k++, pOp++){
       
  2765         if( pOp->p1!=pLevel->iTabCur ) continue;
       
  2766         if( pOp->opcode==OP_Column ){
       
  2767           for(j=0; j<pIdx->nColumn; j++){
       
  2768             if( pOp->p2==pIdx->aiColumn[j] ){
       
  2769               pOp->p2 = j;
       
  2770               pOp->p1 = pLevel->iIdxCur;
       
  2771               break;
       
  2772             }
       
  2773           }
       
  2774           assert(!useIndexOnly || j<pIdx->nColumn);
       
  2775         }else if( pOp->opcode==OP_Rowid ){
       
  2776           pOp->p1 = pLevel->iIdxCur;
       
  2777           pOp->opcode = OP_IdxRowid;
       
  2778         }else if( pOp->opcode==OP_NullRow && useIndexOnly ){
       
  2779           pOp->opcode = OP_Noop;
       
  2780         }
       
  2781       }
       
  2782     }
       
  2783   }
       
  2784 
       
  2785   /* Final cleanup
       
  2786   */
       
  2787   whereInfoFree(pWInfo);
       
  2788   return;
       
  2789 }