Home | History | Annotate | Download | only in src
      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 responsible 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 #include "sqliteInt.h"
     20 
     21 
     22 /*
     23 ** Trace output macros
     24 */
     25 #if defined(SQLITE_TEST) || defined(SQLITE_DEBUG)
     26 int sqlite3WhereTrace = 0;
     27 #endif
     28 #if defined(SQLITE_TEST) && defined(SQLITE_DEBUG)
     29 # define WHERETRACE(X)  if(sqlite3WhereTrace) sqlite3DebugPrintf X
     30 #else
     31 # define WHERETRACE(X)
     32 #endif
     33 
     34 /* Forward reference
     35 */
     36 typedef struct WhereClause WhereClause;
     37 typedef struct WhereMaskSet WhereMaskSet;
     38 typedef struct WhereOrInfo WhereOrInfo;
     39 typedef struct WhereAndInfo WhereAndInfo;
     40 typedef struct WhereCost WhereCost;
     41 
     42 /*
     43 ** The query generator uses an array of instances of this structure to
     44 ** help it analyze the subexpressions of the WHERE clause.  Each WHERE
     45 ** clause subexpression is separated from the others by AND operators,
     46 ** usually, or sometimes subexpressions separated by OR.
     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.u.leftColumn record the
     59 ** cursor number and column number for X.  WhereTerm.eOperator 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 ** A WhereTerm might also be two or more subterms connected by OR:
     65 **
     66 **         (t1.X <op> <expr>) OR (t1.Y <op> <expr>) OR ....
     67 **
     68 ** In this second case, wtFlag as the TERM_ORINFO set and eOperator==WO_OR
     69 ** and the WhereTerm.u.pOrInfo field points to auxiliary information that
     70 ** is collected about the
     71 **
     72 ** If a term in the WHERE clause does not match either of the two previous
     73 ** categories, then eOperator==0.  The WhereTerm.pExpr field is still set
     74 ** to the original subexpression content and wtFlags is set up appropriately
     75 ** but no other fields in the WhereTerm object are meaningful.
     76 **
     77 ** When eOperator!=0, prereqRight and prereqAll record sets of cursor numbers,
     78 ** but they do so indirectly.  A single WhereMaskSet structure translates
     79 ** cursor number into bits and the translated bit is stored in the prereq
     80 ** fields.  The translation is used in order to maximize the number of
     81 ** bits that will fit in a Bitmask.  The VDBE cursor numbers might be
     82 ** spread out over the non-negative integers.  For example, the cursor
     83 ** numbers might be 3, 8, 9, 10, 20, 23, 41, and 45.  The WhereMaskSet
     84 ** translates these sparse cursor numbers into consecutive integers
     85 ** beginning with 0 in order to make the best possible use of the available
     86 ** bits in the Bitmask.  So, in the example above, the cursor numbers
     87 ** would be mapped into integers 0 through 7.
     88 **
     89 ** The number of terms in a join is limited by the number of bits
     90 ** in prereqRight and prereqAll.  The default is 64 bits, hence SQLite
     91 ** is only able to process joins with 64 or fewer tables.
     92 */
     93 typedef struct WhereTerm WhereTerm;
     94 struct WhereTerm {
     95   Expr *pExpr;            /* Pointer to the subexpression that is this term */
     96   int iParent;            /* Disable pWC->a[iParent] when this term disabled */
     97   int leftCursor;         /* Cursor number of X in "X <op> <expr>" */
     98   union {
     99     int leftColumn;         /* Column number of X in "X <op> <expr>" */
    100     WhereOrInfo *pOrInfo;   /* Extra information if eOperator==WO_OR */
    101     WhereAndInfo *pAndInfo; /* Extra information if eOperator==WO_AND */
    102   } u;
    103   u16 eOperator;          /* A WO_xx value describing <op> */
    104   u8 wtFlags;             /* TERM_xxx bit flags.  See below */
    105   u8 nChild;              /* Number of children that must disable us */
    106   WhereClause *pWC;       /* The clause this term is part of */
    107   Bitmask prereqRight;    /* Bitmask of tables used by pExpr->pRight */
    108   Bitmask prereqAll;      /* Bitmask of tables referenced by pExpr */
    109 };
    110 
    111 /*
    112 ** Allowed values of WhereTerm.wtFlags
    113 */
    114 #define TERM_DYNAMIC    0x01   /* Need to call sqlite3ExprDelete(db, pExpr) */
    115 #define TERM_VIRTUAL    0x02   /* Added by the optimizer.  Do not code */
    116 #define TERM_CODED      0x04   /* This term is already coded */
    117 #define TERM_COPIED     0x08   /* Has a child */
    118 #define TERM_ORINFO     0x10   /* Need to free the WhereTerm.u.pOrInfo object */
    119 #define TERM_ANDINFO    0x20   /* Need to free the WhereTerm.u.pAndInfo obj */
    120 #define TERM_OR_OK      0x40   /* Used during OR-clause processing */
    121 #ifdef SQLITE_ENABLE_STAT2
    122 #  define TERM_VNULL    0x80   /* Manufactured x>NULL or x<=NULL term */
    123 #else
    124 #  define TERM_VNULL    0x00   /* Disabled if not using stat2 */
    125 #endif
    126 
    127 /*
    128 ** An instance of the following structure holds all information about a
    129 ** WHERE clause.  Mostly this is a container for one or more WhereTerms.
    130 */
    131 struct WhereClause {
    132   Parse *pParse;           /* The parser context */
    133   WhereMaskSet *pMaskSet;  /* Mapping of table cursor numbers to bitmasks */
    134   Bitmask vmask;           /* Bitmask identifying virtual table cursors */
    135   u8 op;                   /* Split operator.  TK_AND or TK_OR */
    136   int nTerm;               /* Number of terms */
    137   int nSlot;               /* Number of entries in a[] */
    138   WhereTerm *a;            /* Each a[] describes a term of the WHERE cluase */
    139 #if defined(SQLITE_SMALL_STACK)
    140   WhereTerm aStatic[1];    /* Initial static space for a[] */
    141 #else
    142   WhereTerm aStatic[8];    /* Initial static space for a[] */
    143 #endif
    144 };
    145 
    146 /*
    147 ** A WhereTerm with eOperator==WO_OR has its u.pOrInfo pointer set to
    148 ** a dynamically allocated instance of the following structure.
    149 */
    150 struct WhereOrInfo {
    151   WhereClause wc;          /* Decomposition into subterms */
    152   Bitmask indexable;       /* Bitmask of all indexable tables in the clause */
    153 };
    154 
    155 /*
    156 ** A WhereTerm with eOperator==WO_AND has its u.pAndInfo pointer set to
    157 ** a dynamically allocated instance of the following structure.
    158 */
    159 struct WhereAndInfo {
    160   WhereClause wc;          /* The subexpression broken out */
    161 };
    162 
    163 /*
    164 ** An instance of the following structure keeps track of a mapping
    165 ** between VDBE cursor numbers and bits of the bitmasks in WhereTerm.
    166 **
    167 ** The VDBE cursor numbers are small integers contained in
    168 ** SrcList_item.iCursor and Expr.iTable fields.  For any given WHERE
    169 ** clause, the cursor numbers might not begin with 0 and they might
    170 ** contain gaps in the numbering sequence.  But we want to make maximum
    171 ** use of the bits in our bitmasks.  This structure provides a mapping
    172 ** from the sparse cursor numbers into consecutive integers beginning
    173 ** with 0.
    174 **
    175 ** If WhereMaskSet.ix[A]==B it means that The A-th bit of a Bitmask
    176 ** corresponds VDBE cursor number B.  The A-th bit of a bitmask is 1<<A.
    177 **
    178 ** For example, if the WHERE clause expression used these VDBE
    179 ** cursors:  4, 5, 8, 29, 57, 73.  Then the  WhereMaskSet structure
    180 ** would map those cursor numbers into bits 0 through 5.
    181 **
    182 ** Note that the mapping is not necessarily ordered.  In the example
    183 ** above, the mapping might go like this:  4->3, 5->1, 8->2, 29->0,
    184 ** 57->5, 73->4.  Or one of 719 other combinations might be used. It
    185 ** does not really matter.  What is important is that sparse cursor
    186 ** numbers all get mapped into bit numbers that begin with 0 and contain
    187 ** no gaps.
    188 */
    189 struct WhereMaskSet {
    190   int n;                        /* Number of assigned cursor values */
    191   int ix[BMS];                  /* Cursor assigned to each bit */
    192 };
    193 
    194 /*
    195 ** A WhereCost object records a lookup strategy and the estimated
    196 ** cost of pursuing that strategy.
    197 */
    198 struct WhereCost {
    199   WherePlan plan;    /* The lookup strategy */
    200   double rCost;      /* Overall cost of pursuing this search strategy */
    201   Bitmask used;      /* Bitmask of cursors used by this plan */
    202 };
    203 
    204 /*
    205 ** Bitmasks for the operators that indices are able to exploit.  An
    206 ** OR-ed combination of these values can be used when searching for
    207 ** terms in the where clause.
    208 */
    209 #define WO_IN     0x001
    210 #define WO_EQ     0x002
    211 #define WO_LT     (WO_EQ<<(TK_LT-TK_EQ))
    212 #define WO_LE     (WO_EQ<<(TK_LE-TK_EQ))
    213 #define WO_GT     (WO_EQ<<(TK_GT-TK_EQ))
    214 #define WO_GE     (WO_EQ<<(TK_GE-TK_EQ))
    215 #define WO_MATCH  0x040
    216 #define WO_ISNULL 0x080
    217 #define WO_OR     0x100       /* Two or more OR-connected terms */
    218 #define WO_AND    0x200       /* Two or more AND-connected terms */
    219 #define WO_NOOP   0x800       /* This term does not restrict search space */
    220 
    221 #define WO_ALL    0xfff       /* Mask of all possible WO_* values */
    222 #define WO_SINGLE 0x0ff       /* Mask of all non-compound WO_* values */
    223 
    224 /*
    225 ** Value for wsFlags returned by bestIndex() and stored in
    226 ** WhereLevel.wsFlags.  These flags determine which search
    227 ** strategies are appropriate.
    228 **
    229 ** The least significant 12 bits is reserved as a mask for WO_ values above.
    230 ** The WhereLevel.wsFlags field is usually set to WO_IN|WO_EQ|WO_ISNULL.
    231 ** But if the table is the right table of a left join, WhereLevel.wsFlags
    232 ** is set to WO_IN|WO_EQ.  The WhereLevel.wsFlags field can then be used as
    233 ** the "op" parameter to findTerm when we are resolving equality constraints.
    234 ** ISNULL constraints will then not be used on the right table of a left
    235 ** join.  Tickets #2177 and #2189.
    236 */
    237 #define WHERE_ROWID_EQ     0x00001000  /* rowid=EXPR or rowid IN (...) */
    238 #define WHERE_ROWID_RANGE  0x00002000  /* rowid<EXPR and/or rowid>EXPR */
    239 #define WHERE_COLUMN_EQ    0x00010000  /* x=EXPR or x IN (...) or x IS NULL */
    240 #define WHERE_COLUMN_RANGE 0x00020000  /* x<EXPR and/or x>EXPR */
    241 #define WHERE_COLUMN_IN    0x00040000  /* x IN (...) */
    242 #define WHERE_COLUMN_NULL  0x00080000  /* x IS NULL */
    243 #define WHERE_INDEXED      0x000f0000  /* Anything that uses an index */
    244 #define WHERE_NOT_FULLSCAN 0x100f3000  /* Does not do a full table scan */
    245 #define WHERE_IN_ABLE      0x000f1000  /* Able to support an IN operator */
    246 #define WHERE_TOP_LIMIT    0x00100000  /* x<EXPR or x<=EXPR constraint */
    247 #define WHERE_BTM_LIMIT    0x00200000  /* x>EXPR or x>=EXPR constraint */
    248 #define WHERE_BOTH_LIMIT   0x00300000  /* Both x>EXPR and x<EXPR */
    249 #define WHERE_IDX_ONLY     0x00800000  /* Use index only - omit table */
    250 #define WHERE_ORDERBY      0x01000000  /* Output will appear in correct order */
    251 #define WHERE_REVERSE      0x02000000  /* Scan in reverse order */
    252 #define WHERE_UNIQUE       0x04000000  /* Selects no more than one row */
    253 #define WHERE_VIRTUALTABLE 0x08000000  /* Use virtual-table processing */
    254 #define WHERE_MULTI_OR     0x10000000  /* OR using multiple indices */
    255 #define WHERE_TEMP_INDEX   0x20000000  /* Uses an ephemeral index */
    256 
    257 /*
    258 ** Initialize a preallocated WhereClause structure.
    259 */
    260 static void whereClauseInit(
    261   WhereClause *pWC,        /* The WhereClause to be initialized */
    262   Parse *pParse,           /* The parsing context */
    263   WhereMaskSet *pMaskSet   /* Mapping from table cursor numbers to bitmasks */
    264 ){
    265   pWC->pParse = pParse;
    266   pWC->pMaskSet = pMaskSet;
    267   pWC->nTerm = 0;
    268   pWC->nSlot = ArraySize(pWC->aStatic);
    269   pWC->a = pWC->aStatic;
    270   pWC->vmask = 0;
    271 }
    272 
    273 /* Forward reference */
    274 static void whereClauseClear(WhereClause*);
    275 
    276 /*
    277 ** Deallocate all memory associated with a WhereOrInfo object.
    278 */
    279 static void whereOrInfoDelete(sqlite3 *db, WhereOrInfo *p){
    280   whereClauseClear(&p->wc);
    281   sqlite3DbFree(db, p);
    282 }
    283 
    284 /*
    285 ** Deallocate all memory associated with a WhereAndInfo object.
    286 */
    287 static void whereAndInfoDelete(sqlite3 *db, WhereAndInfo *p){
    288   whereClauseClear(&p->wc);
    289   sqlite3DbFree(db, p);
    290 }
    291 
    292 /*
    293 ** Deallocate a WhereClause structure.  The WhereClause structure
    294 ** itself is not freed.  This routine is the inverse of whereClauseInit().
    295 */
    296 static void whereClauseClear(WhereClause *pWC){
    297   int i;
    298   WhereTerm *a;
    299   sqlite3 *db = pWC->pParse->db;
    300   for(i=pWC->nTerm-1, a=pWC->a; i>=0; i--, a++){
    301     if( a->wtFlags & TERM_DYNAMIC ){
    302       sqlite3ExprDelete(db, a->pExpr);
    303     }
    304     if( a->wtFlags & TERM_ORINFO ){
    305       whereOrInfoDelete(db, a->u.pOrInfo);
    306     }else if( a->wtFlags & TERM_ANDINFO ){
    307       whereAndInfoDelete(db, a->u.pAndInfo);
    308     }
    309   }
    310   if( pWC->a!=pWC->aStatic ){
    311     sqlite3DbFree(db, pWC->a);
    312   }
    313 }
    314 
    315 /*
    316 ** Add a single new WhereTerm entry to the WhereClause object pWC.
    317 ** The new WhereTerm object is constructed from Expr p and with wtFlags.
    318 ** The index in pWC->a[] of the new WhereTerm is returned on success.
    319 ** 0 is returned if the new WhereTerm could not be added due to a memory
    320 ** allocation error.  The memory allocation failure will be recorded in
    321 ** the db->mallocFailed flag so that higher-level functions can detect it.
    322 **
    323 ** This routine will increase the size of the pWC->a[] array as necessary.
    324 **
    325 ** If the wtFlags argument includes TERM_DYNAMIC, then responsibility
    326 ** for freeing the expression p is assumed by the WhereClause object pWC.
    327 ** This is true even if this routine fails to allocate a new WhereTerm.
    328 **
    329 ** WARNING:  This routine might reallocate the space used to store
    330 ** WhereTerms.  All pointers to WhereTerms should be invalidated after
    331 ** calling this routine.  Such pointers may be reinitialized by referencing
    332 ** the pWC->a[] array.
    333 */
    334 static int whereClauseInsert(WhereClause *pWC, Expr *p, u8 wtFlags){
    335   WhereTerm *pTerm;
    336   int idx;
    337   testcase( wtFlags & TERM_VIRTUAL );  /* EV: R-00211-15100 */
    338   if( pWC->nTerm>=pWC->nSlot ){
    339     WhereTerm *pOld = pWC->a;
    340     sqlite3 *db = pWC->pParse->db;
    341     pWC->a = sqlite3DbMallocRaw(db, sizeof(pWC->a[0])*pWC->nSlot*2 );
    342     if( pWC->a==0 ){
    343       if( wtFlags & TERM_DYNAMIC ){
    344         sqlite3ExprDelete(db, p);
    345       }
    346       pWC->a = pOld;
    347       return 0;
    348     }
    349     memcpy(pWC->a, pOld, sizeof(pWC->a[0])*pWC->nTerm);
    350     if( pOld!=pWC->aStatic ){
    351       sqlite3DbFree(db, pOld);
    352     }
    353     pWC->nSlot = sqlite3DbMallocSize(db, pWC->a)/sizeof(pWC->a[0]);
    354   }
    355   pTerm = &pWC->a[idx = pWC->nTerm++];
    356   pTerm->pExpr = p;
    357   pTerm->wtFlags = wtFlags;
    358   pTerm->pWC = pWC;
    359   pTerm->iParent = -1;
    360   return idx;
    361 }
    362 
    363 /*
    364 ** This routine identifies subexpressions in the WHERE clause where
    365 ** each subexpression is separated by the AND operator or some other
    366 ** operator specified in the op parameter.  The WhereClause structure
    367 ** is filled with pointers to subexpressions.  For example:
    368 **
    369 **    WHERE  a=='hello' AND coalesce(b,11)<10 AND (c+12!=d OR c==22)
    370 **           \________/     \_______________/     \________________/
    371 **            slot[0]            slot[1]               slot[2]
    372 **
    373 ** The original WHERE clause in pExpr is unaltered.  All this routine
    374 ** does is make slot[] entries point to substructure within pExpr.
    375 **
    376 ** In the previous sentence and in the diagram, "slot[]" refers to
    377 ** the WhereClause.a[] array.  The slot[] array grows as needed to contain
    378 ** all terms of the WHERE clause.
    379 */
    380 static void whereSplit(WhereClause *pWC, Expr *pExpr, int op){
    381   pWC->op = (u8)op;
    382   if( pExpr==0 ) return;
    383   if( pExpr->op!=op ){
    384     whereClauseInsert(pWC, pExpr, 0);
    385   }else{
    386     whereSplit(pWC, pExpr->pLeft, op);
    387     whereSplit(pWC, pExpr->pRight, op);
    388   }
    389 }
    390 
    391 /*
    392 ** Initialize an expression mask set (a WhereMaskSet object)
    393 */
    394 #define initMaskSet(P)  memset(P, 0, sizeof(*P))
    395 
    396 /*
    397 ** Return the bitmask for the given cursor number.  Return 0 if
    398 ** iCursor is not in the set.
    399 */
    400 static Bitmask getMask(WhereMaskSet *pMaskSet, int iCursor){
    401   int i;
    402   assert( pMaskSet->n<=(int)sizeof(Bitmask)*8 );
    403   for(i=0; i<pMaskSet->n; i++){
    404     if( pMaskSet->ix[i]==iCursor ){
    405       return ((Bitmask)1)<<i;
    406     }
    407   }
    408   return 0;
    409 }
    410 
    411 /*
    412 ** Create a new mask for cursor iCursor.
    413 **
    414 ** There is one cursor per table in the FROM clause.  The number of
    415 ** tables in the FROM clause is limited by a test early in the
    416 ** sqlite3WhereBegin() routine.  So we know that the pMaskSet->ix[]
    417 ** array will never overflow.
    418 */
    419 static void createMask(WhereMaskSet *pMaskSet, int iCursor){
    420   assert( pMaskSet->n < ArraySize(pMaskSet->ix) );
    421   pMaskSet->ix[pMaskSet->n++] = iCursor;
    422 }
    423 
    424 /*
    425 ** This routine walks (recursively) an expression tree and generates
    426 ** a bitmask indicating which tables are used in that expression
    427 ** tree.
    428 **
    429 ** In order for this routine to work, the calling function must have
    430 ** previously invoked sqlite3ResolveExprNames() on the expression.  See
    431 ** the header comment on that routine for additional information.
    432 ** The sqlite3ResolveExprNames() routines looks for column names and
    433 ** sets their opcodes to TK_COLUMN and their Expr.iTable fields to
    434 ** the VDBE cursor number of the table.  This routine just has to
    435 ** translate the cursor numbers into bitmask values and OR all
    436 ** the bitmasks together.
    437 */
    438 static Bitmask exprListTableUsage(WhereMaskSet*, ExprList*);
    439 static Bitmask exprSelectTableUsage(WhereMaskSet*, Select*);
    440 static Bitmask exprTableUsage(WhereMaskSet *pMaskSet, Expr *p){
    441   Bitmask mask = 0;
    442   if( p==0 ) return 0;
    443   if( p->op==TK_COLUMN ){
    444     mask = getMask(pMaskSet, p->iTable);
    445     return mask;
    446   }
    447   mask = exprTableUsage(pMaskSet, p->pRight);
    448   mask |= exprTableUsage(pMaskSet, p->pLeft);
    449   if( ExprHasProperty(p, EP_xIsSelect) ){
    450     mask |= exprSelectTableUsage(pMaskSet, p->x.pSelect);
    451   }else{
    452     mask |= exprListTableUsage(pMaskSet, p->x.pList);
    453   }
    454   return mask;
    455 }
    456 static Bitmask exprListTableUsage(WhereMaskSet *pMaskSet, ExprList *pList){
    457   int i;
    458   Bitmask mask = 0;
    459   if( pList ){
    460     for(i=0; i<pList->nExpr; i++){
    461       mask |= exprTableUsage(pMaskSet, pList->a[i].pExpr);
    462     }
    463   }
    464   return mask;
    465 }
    466 static Bitmask exprSelectTableUsage(WhereMaskSet *pMaskSet, Select *pS){
    467   Bitmask mask = 0;
    468   while( pS ){
    469     mask |= exprListTableUsage(pMaskSet, pS->pEList);
    470     mask |= exprListTableUsage(pMaskSet, pS->pGroupBy);
    471     mask |= exprListTableUsage(pMaskSet, pS->pOrderBy);
    472     mask |= exprTableUsage(pMaskSet, pS->pWhere);
    473     mask |= exprTableUsage(pMaskSet, pS->pHaving);
    474     pS = pS->pPrior;
    475   }
    476   return mask;
    477 }
    478 
    479 /*
    480 ** Return TRUE if the given operator is one of the operators that is
    481 ** allowed for an indexable WHERE clause term.  The allowed operators are
    482 ** "=", "<", ">", "<=", ">=", and "IN".
    483 **
    484 ** IMPLEMENTATION-OF: R-59926-26393 To be usable by an index a term must be
    485 ** of one of the following forms: column = expression column > expression
    486 ** column >= expression column < expression column <= expression
    487 ** expression = column expression > column expression >= column
    488 ** expression < column expression <= column column IN
    489 ** (expression-list) column IN (subquery) column IS NULL
    490 */
    491 static int allowedOp(int op){
    492   assert( TK_GT>TK_EQ && TK_GT<TK_GE );
    493   assert( TK_LT>TK_EQ && TK_LT<TK_GE );
    494   assert( TK_LE>TK_EQ && TK_LE<TK_GE );
    495   assert( TK_GE==TK_EQ+4 );
    496   return op==TK_IN || (op>=TK_EQ && op<=TK_GE) || op==TK_ISNULL;
    497 }
    498 
    499 /*
    500 ** Swap two objects of type TYPE.
    501 */
    502 #define SWAP(TYPE,A,B) {TYPE t=A; A=B; B=t;}
    503 
    504 /*
    505 ** Commute a comparison operator.  Expressions of the form "X op Y"
    506 ** are converted into "Y op X".
    507 **
    508 ** If a collation sequence is associated with either the left or right
    509 ** side of the comparison, it remains associated with the same side after
    510 ** the commutation. So "Y collate NOCASE op X" becomes
    511 ** "X collate NOCASE op Y". This is because any collation sequence on
    512 ** the left hand side of a comparison overrides any collation sequence
    513 ** attached to the right. For the same reason the EP_ExpCollate flag
    514 ** is not commuted.
    515 */
    516 static void exprCommute(Parse *pParse, Expr *pExpr){
    517   u16 expRight = (pExpr->pRight->flags & EP_ExpCollate);
    518   u16 expLeft = (pExpr->pLeft->flags & EP_ExpCollate);
    519   assert( allowedOp(pExpr->op) && pExpr->op!=TK_IN );
    520   pExpr->pRight->pColl = sqlite3ExprCollSeq(pParse, pExpr->pRight);
    521   pExpr->pLeft->pColl = sqlite3ExprCollSeq(pParse, pExpr->pLeft);
    522   SWAP(CollSeq*,pExpr->pRight->pColl,pExpr->pLeft->pColl);
    523   pExpr->pRight->flags = (pExpr->pRight->flags & ~EP_ExpCollate) | expLeft;
    524   pExpr->pLeft->flags = (pExpr->pLeft->flags & ~EP_ExpCollate) | expRight;
    525   SWAP(Expr*,pExpr->pRight,pExpr->pLeft);
    526   if( pExpr->op>=TK_GT ){
    527     assert( TK_LT==TK_GT+2 );
    528     assert( TK_GE==TK_LE+2 );
    529     assert( TK_GT>TK_EQ );
    530     assert( TK_GT<TK_LE );
    531     assert( pExpr->op>=TK_GT && pExpr->op<=TK_GE );
    532     pExpr->op = ((pExpr->op-TK_GT)^2)+TK_GT;
    533   }
    534 }
    535 
    536 /*
    537 ** Translate from TK_xx operator to WO_xx bitmask.
    538 */
    539 static u16 operatorMask(int op){
    540   u16 c;
    541   assert( allowedOp(op) );
    542   if( op==TK_IN ){
    543     c = WO_IN;
    544   }else if( op==TK_ISNULL ){
    545     c = WO_ISNULL;
    546   }else{
    547     assert( (WO_EQ<<(op-TK_EQ)) < 0x7fff );
    548     c = (u16)(WO_EQ<<(op-TK_EQ));
    549   }
    550   assert( op!=TK_ISNULL || c==WO_ISNULL );
    551   assert( op!=TK_IN || c==WO_IN );
    552   assert( op!=TK_EQ || c==WO_EQ );
    553   assert( op!=TK_LT || c==WO_LT );
    554   assert( op!=TK_LE || c==WO_LE );
    555   assert( op!=TK_GT || c==WO_GT );
    556   assert( op!=TK_GE || c==WO_GE );
    557   return c;
    558 }
    559 
    560 /*
    561 ** Search for a term in the WHERE clause that is of the form "X <op> <expr>"
    562 ** where X is a reference to the iColumn of table iCur and <op> is one of
    563 ** the WO_xx operator codes specified by the op parameter.
    564 ** Return a pointer to the term.  Return 0 if not found.
    565 */
    566 static WhereTerm *findTerm(
    567   WhereClause *pWC,     /* The WHERE clause to be searched */
    568   int iCur,             /* Cursor number of LHS */
    569   int iColumn,          /* Column number of LHS */
    570   Bitmask notReady,     /* RHS must not overlap with this mask */
    571   u32 op,               /* Mask of WO_xx values describing operator */
    572   Index *pIdx           /* Must be compatible with this index, if not NULL */
    573 ){
    574   WhereTerm *pTerm;
    575   int k;
    576   assert( iCur>=0 );
    577   op &= WO_ALL;
    578   for(pTerm=pWC->a, k=pWC->nTerm; k; k--, pTerm++){
    579     if( pTerm->leftCursor==iCur
    580        && (pTerm->prereqRight & notReady)==0
    581        && pTerm->u.leftColumn==iColumn
    582        && (pTerm->eOperator & op)!=0
    583     ){
    584       if( pIdx && pTerm->eOperator!=WO_ISNULL ){
    585         Expr *pX = pTerm->pExpr;
    586         CollSeq *pColl;
    587         char idxaff;
    588         int j;
    589         Parse *pParse = pWC->pParse;
    590 
    591         idxaff = pIdx->pTable->aCol[iColumn].affinity;
    592         if( !sqlite3IndexAffinityOk(pX, idxaff) ) continue;
    593 
    594         /* Figure out the collation sequence required from an index for
    595         ** it to be useful for optimising expression pX. Store this
    596         ** value in variable pColl.
    597         */
    598         assert(pX->pLeft);
    599         pColl = sqlite3BinaryCompareCollSeq(pParse, pX->pLeft, pX->pRight);
    600         assert(pColl || pParse->nErr);
    601 
    602         for(j=0; pIdx->aiColumn[j]!=iColumn; j++){
    603           if( NEVER(j>=pIdx->nColumn) ) return 0;
    604         }
    605         if( pColl && sqlite3StrICmp(pColl->zName, pIdx->azColl[j]) ) continue;
    606       }
    607       return pTerm;
    608     }
    609   }
    610   return 0;
    611 }
    612 
    613 /* Forward reference */
    614 static void exprAnalyze(SrcList*, WhereClause*, int);
    615 
    616 /*
    617 ** Call exprAnalyze on all terms in a WHERE clause.
    618 **
    619 **
    620 */
    621 static void exprAnalyzeAll(
    622   SrcList *pTabList,       /* the FROM clause */
    623   WhereClause *pWC         /* the WHERE clause to be analyzed */
    624 ){
    625   int i;
    626   for(i=pWC->nTerm-1; i>=0; i--){
    627     exprAnalyze(pTabList, pWC, i);
    628   }
    629 }
    630 
    631 #ifndef SQLITE_OMIT_LIKE_OPTIMIZATION
    632 /*
    633 ** Check to see if the given expression is a LIKE or GLOB operator that
    634 ** can be optimized using inequality constraints.  Return TRUE if it is
    635 ** so and false if not.
    636 **
    637 ** In order for the operator to be optimizible, the RHS must be a string
    638 ** literal that does not begin with a wildcard.
    639 */
    640 static int isLikeOrGlob(
    641   Parse *pParse,    /* Parsing and code generating context */
    642   Expr *pExpr,      /* Test this expression */
    643   Expr **ppPrefix,  /* Pointer to TK_STRING expression with pattern prefix */
    644   int *pisComplete, /* True if the only wildcard is % in the last character */
    645   int *pnoCase      /* True if uppercase is equivalent to lowercase */
    646 ){
    647   const char *z = 0;         /* String on RHS of LIKE operator */
    648   Expr *pRight, *pLeft;      /* Right and left size of LIKE operator */
    649   ExprList *pList;           /* List of operands to the LIKE operator */
    650   int c;                     /* One character in z[] */
    651   int cnt;                   /* Number of non-wildcard prefix characters */
    652   char wc[3];                /* Wildcard characters */
    653   sqlite3 *db = pParse->db;  /* Database connection */
    654   sqlite3_value *pVal = 0;
    655   int op;                    /* Opcode of pRight */
    656 
    657   if( !sqlite3IsLikeFunction(db, pExpr, pnoCase, wc) ){
    658     return 0;
    659   }
    660 #ifdef SQLITE_EBCDIC
    661   if( *pnoCase ) return 0;
    662 #endif
    663   pList = pExpr->x.pList;
    664   pLeft = pList->a[1].pExpr;
    665   if( pLeft->op!=TK_COLUMN || sqlite3ExprAffinity(pLeft)!=SQLITE_AFF_TEXT ){
    666     /* IMP: R-02065-49465 The left-hand side of the LIKE or GLOB operator must
    667     ** be the name of an indexed column with TEXT affinity. */
    668     return 0;
    669   }
    670   assert( pLeft->iColumn!=(-1) ); /* Because IPK never has AFF_TEXT */
    671 
    672   pRight = pList->a[0].pExpr;
    673   op = pRight->op;
    674   if( op==TK_REGISTER ){
    675     op = pRight->op2;
    676   }
    677   if( op==TK_VARIABLE ){
    678     Vdbe *pReprepare = pParse->pReprepare;
    679     int iCol = pRight->iColumn;
    680     pVal = sqlite3VdbeGetValue(pReprepare, iCol, SQLITE_AFF_NONE);
    681     if( pVal && sqlite3_value_type(pVal)==SQLITE_TEXT ){
    682       z = (char *)sqlite3_value_text(pVal);
    683     }
    684     sqlite3VdbeSetVarmask(pParse->pVdbe, iCol); /* IMP: R-23257-02778 */
    685     assert( pRight->op==TK_VARIABLE || pRight->op==TK_REGISTER );
    686   }else if( op==TK_STRING ){
    687     z = pRight->u.zToken;
    688   }
    689   if( z ){
    690     cnt = 0;
    691     while( (c=z[cnt])!=0 && c!=wc[0] && c!=wc[1] && c!=wc[2] ){
    692       cnt++;
    693     }
    694     if( cnt!=0 && 255!=(u8)z[cnt-1] ){
    695       Expr *pPrefix;
    696       *pisComplete = c==wc[0] && z[cnt+1]==0;
    697       pPrefix = sqlite3Expr(db, TK_STRING, z);
    698       if( pPrefix ) pPrefix->u.zToken[cnt] = 0;
    699       *ppPrefix = pPrefix;
    700       if( op==TK_VARIABLE ){
    701         Vdbe *v = pParse->pVdbe;
    702         sqlite3VdbeSetVarmask(v, pRight->iColumn); /* IMP: R-23257-02778 */
    703         if( *pisComplete && pRight->u.zToken[1] ){
    704           /* If the rhs of the LIKE expression is a variable, and the current
    705           ** value of the variable means there is no need to invoke the LIKE
    706           ** function, then no OP_Variable will be added to the program.
    707           ** This causes problems for the sqlite3_bind_parameter_name()
    708           ** API. To workaround them, add a dummy OP_Variable here.
    709           */
    710           int r1 = sqlite3GetTempReg(pParse);
    711           sqlite3ExprCodeTarget(pParse, pRight, r1);
    712           sqlite3VdbeChangeP3(v, sqlite3VdbeCurrentAddr(v)-1, 0);
    713           sqlite3ReleaseTempReg(pParse, r1);
    714         }
    715       }
    716     }else{
    717       z = 0;
    718     }
    719   }
    720 
    721   sqlite3ValueFree(pVal);
    722   return (z!=0);
    723 }
    724 #endif /* SQLITE_OMIT_LIKE_OPTIMIZATION */
    725 
    726 
    727 #ifndef SQLITE_OMIT_VIRTUALTABLE
    728 /*
    729 ** Check to see if the given expression is of the form
    730 **
    731 **         column MATCH expr
    732 **
    733 ** If it is then return TRUE.  If not, return FALSE.
    734 */
    735 static int isMatchOfColumn(
    736   Expr *pExpr      /* Test this expression */
    737 ){
    738   ExprList *pList;
    739 
    740   if( pExpr->op!=TK_FUNCTION ){
    741     return 0;
    742   }
    743   if( sqlite3StrICmp(pExpr->u.zToken,"match")!=0 ){
    744     return 0;
    745   }
    746   pList = pExpr->x.pList;
    747   if( pList->nExpr!=2 ){
    748     return 0;
    749   }
    750   if( pList->a[1].pExpr->op != TK_COLUMN ){
    751     return 0;
    752   }
    753   return 1;
    754 }
    755 #endif /* SQLITE_OMIT_VIRTUALTABLE */
    756 
    757 /*
    758 ** If the pBase expression originated in the ON or USING clause of
    759 ** a join, then transfer the appropriate markings over to derived.
    760 */
    761 static void transferJoinMarkings(Expr *pDerived, Expr *pBase){
    762   pDerived->flags |= pBase->flags & EP_FromJoin;
    763   pDerived->iRightJoinTable = pBase->iRightJoinTable;
    764 }
    765 
    766 #if !defined(SQLITE_OMIT_OR_OPTIMIZATION) && !defined(SQLITE_OMIT_SUBQUERY)
    767 /*
    768 ** Analyze a term that consists of two or more OR-connected
    769 ** subterms.  So in:
    770 **
    771 **     ... WHERE  (a=5) AND (b=7 OR c=9 OR d=13) AND (d=13)
    772 **                          ^^^^^^^^^^^^^^^^^^^^
    773 **
    774 ** This routine analyzes terms such as the middle term in the above example.
    775 ** A WhereOrTerm object is computed and attached to the term under
    776 ** analysis, regardless of the outcome of the analysis.  Hence:
    777 **
    778 **     WhereTerm.wtFlags   |=  TERM_ORINFO
    779 **     WhereTerm.u.pOrInfo  =  a dynamically allocated WhereOrTerm object
    780 **
    781 ** The term being analyzed must have two or more of OR-connected subterms.
    782 ** A single subterm might be a set of AND-connected sub-subterms.
    783 ** Examples of terms under analysis:
    784 **
    785 **     (A)     t1.x=t2.y OR t1.x=t2.z OR t1.y=15 OR t1.z=t3.a+5
    786 **     (B)     x=expr1 OR expr2=x OR x=expr3
    787 **     (C)     t1.x=t2.y OR (t1.x=t2.z AND t1.y=15)
    788 **     (D)     x=expr1 OR (y>11 AND y<22 AND z LIKE '*hello*')
    789 **     (E)     (p.a=1 AND q.b=2 AND r.c=3) OR (p.x=4 AND q.y=5 AND r.z=6)
    790 **
    791 ** CASE 1:
    792 **
    793 ** If all subterms are of the form T.C=expr for some single column of C
    794 ** a single table T (as shown in example B above) then create a new virtual
    795 ** term that is an equivalent IN expression.  In other words, if the term
    796 ** being analyzed is:
    797 **
    798 **      x = expr1  OR  expr2 = x  OR  x = expr3
    799 **
    800 ** then create a new virtual term like this:
    801 **
    802 **      x IN (expr1,expr2,expr3)
    803 **
    804 ** CASE 2:
    805 **
    806 ** If all subterms are indexable by a single table T, then set
    807 **
    808 **     WhereTerm.eOperator              =  WO_OR
    809 **     WhereTerm.u.pOrInfo->indexable  |=  the cursor number for table T
    810 **
    811 ** A subterm is "indexable" if it is of the form
    812 ** "T.C <op> <expr>" where C is any column of table T and
    813 ** <op> is one of "=", "<", "<=", ">", ">=", "IS NULL", or "IN".
    814 ** A subterm is also indexable if it is an AND of two or more
    815 ** subsubterms at least one of which is indexable.  Indexable AND
    816 ** subterms have their eOperator set to WO_AND and they have
    817 ** u.pAndInfo set to a dynamically allocated WhereAndTerm object.
    818 **
    819 ** From another point of view, "indexable" means that the subterm could
    820 ** potentially be used with an index if an appropriate index exists.
    821 ** This analysis does not consider whether or not the index exists; that
    822 ** is something the bestIndex() routine will determine.  This analysis
    823 ** only looks at whether subterms appropriate for indexing exist.
    824 **
    825 ** All examples A through E above all satisfy case 2.  But if a term
    826 ** also statisfies case 1 (such as B) we know that the optimizer will
    827 ** always prefer case 1, so in that case we pretend that case 2 is not
    828 ** satisfied.
    829 **
    830 ** It might be the case that multiple tables are indexable.  For example,
    831 ** (E) above is indexable on tables P, Q, and R.
    832 **
    833 ** Terms that satisfy case 2 are candidates for lookup by using
    834 ** separate indices to find rowids for each subterm and composing
    835 ** the union of all rowids using a RowSet object.  This is similar
    836 ** to "bitmap indices" in other database engines.
    837 **
    838 ** OTHERWISE:
    839 **
    840 ** If neither case 1 nor case 2 apply, then leave the eOperator set to
    841 ** zero.  This term is not useful for search.
    842 */
    843 static void exprAnalyzeOrTerm(
    844   SrcList *pSrc,            /* the FROM clause */
    845   WhereClause *pWC,         /* the complete WHERE clause */
    846   int idxTerm               /* Index of the OR-term to be analyzed */
    847 ){
    848   Parse *pParse = pWC->pParse;            /* Parser context */
    849   sqlite3 *db = pParse->db;               /* Database connection */
    850   WhereTerm *pTerm = &pWC->a[idxTerm];    /* The term to be analyzed */
    851   Expr *pExpr = pTerm->pExpr;             /* The expression of the term */
    852   WhereMaskSet *pMaskSet = pWC->pMaskSet; /* Table use masks */
    853   int i;                                  /* Loop counters */
    854   WhereClause *pOrWc;       /* Breakup of pTerm into subterms */
    855   WhereTerm *pOrTerm;       /* A Sub-term within the pOrWc */
    856   WhereOrInfo *pOrInfo;     /* Additional information associated with pTerm */
    857   Bitmask chngToIN;         /* Tables that might satisfy case 1 */
    858   Bitmask indexable;        /* Tables that are indexable, satisfying case 2 */
    859 
    860   /*
    861   ** Break the OR clause into its separate subterms.  The subterms are
    862   ** stored in a WhereClause structure containing within the WhereOrInfo
    863   ** object that is attached to the original OR clause term.
    864   */
    865   assert( (pTerm->wtFlags & (TERM_DYNAMIC|TERM_ORINFO|TERM_ANDINFO))==0 );
    866   assert( pExpr->op==TK_OR );
    867   pTerm->u.pOrInfo = pOrInfo = sqlite3DbMallocZero(db, sizeof(*pOrInfo));
    868   if( pOrInfo==0 ) return;
    869   pTerm->wtFlags |= TERM_ORINFO;
    870   pOrWc = &pOrInfo->wc;
    871   whereClauseInit(pOrWc, pWC->pParse, pMaskSet);
    872   whereSplit(pOrWc, pExpr, TK_OR);
    873   exprAnalyzeAll(pSrc, pOrWc);
    874   if( db->mallocFailed ) return;
    875   assert( pOrWc->nTerm>=2 );
    876 
    877   /*
    878   ** Compute the set of tables that might satisfy cases 1 or 2.
    879   */
    880   indexable = ~(Bitmask)0;
    881   chngToIN = ~(pWC->vmask);
    882   for(i=pOrWc->nTerm-1, pOrTerm=pOrWc->a; i>=0 && indexable; i--, pOrTerm++){
    883     if( (pOrTerm->eOperator & WO_SINGLE)==0 ){
    884       WhereAndInfo *pAndInfo;
    885       assert( pOrTerm->eOperator==0 );
    886       assert( (pOrTerm->wtFlags & (TERM_ANDINFO|TERM_ORINFO))==0 );
    887       chngToIN = 0;
    888       pAndInfo = sqlite3DbMallocRaw(db, sizeof(*pAndInfo));
    889       if( pAndInfo ){
    890         WhereClause *pAndWC;
    891         WhereTerm *pAndTerm;
    892         int j;
    893         Bitmask b = 0;
    894         pOrTerm->u.pAndInfo = pAndInfo;
    895         pOrTerm->wtFlags |= TERM_ANDINFO;
    896         pOrTerm->eOperator = WO_AND;
    897         pAndWC = &pAndInfo->wc;
    898         whereClauseInit(pAndWC, pWC->pParse, pMaskSet);
    899         whereSplit(pAndWC, pOrTerm->pExpr, TK_AND);
    900         exprAnalyzeAll(pSrc, pAndWC);
    901         testcase( db->mallocFailed );
    902         if( !db->mallocFailed ){
    903           for(j=0, pAndTerm=pAndWC->a; j<pAndWC->nTerm; j++, pAndTerm++){
    904             assert( pAndTerm->pExpr );
    905             if( allowedOp(pAndTerm->pExpr->op) ){
    906               b |= getMask(pMaskSet, pAndTerm->leftCursor);
    907             }
    908           }
    909         }
    910         indexable &= b;
    911       }
    912     }else if( pOrTerm->wtFlags & TERM_COPIED ){
    913       /* Skip this term for now.  We revisit it when we process the
    914       ** corresponding TERM_VIRTUAL term */
    915     }else{
    916       Bitmask b;
    917       b = getMask(pMaskSet, pOrTerm->leftCursor);
    918       if( pOrTerm->wtFlags & TERM_VIRTUAL ){
    919         WhereTerm *pOther = &pOrWc->a[pOrTerm->iParent];
    920         b |= getMask(pMaskSet, pOther->leftCursor);
    921       }
    922       indexable &= b;
    923       if( pOrTerm->eOperator!=WO_EQ ){
    924         chngToIN = 0;
    925       }else{
    926         chngToIN &= b;
    927       }
    928     }
    929   }
    930 
    931   /*
    932   ** Record the set of tables that satisfy case 2.  The set might be
    933   ** empty.
    934   */
    935   pOrInfo->indexable = indexable;
    936   pTerm->eOperator = indexable==0 ? 0 : WO_OR;
    937 
    938   /*
    939   ** chngToIN holds a set of tables that *might* satisfy case 1.  But
    940   ** we have to do some additional checking to see if case 1 really
    941   ** is satisfied.
    942   **
    943   ** chngToIN will hold either 0, 1, or 2 bits.  The 0-bit case means
    944   ** that there is no possibility of transforming the OR clause into an
    945   ** IN operator because one or more terms in the OR clause contain
    946   ** something other than == on a column in the single table.  The 1-bit
    947   ** case means that every term of the OR clause is of the form
    948   ** "table.column=expr" for some single table.  The one bit that is set
    949   ** will correspond to the common table.  We still need to check to make
    950   ** sure the same column is used on all terms.  The 2-bit case is when
    951   ** the all terms are of the form "table1.column=table2.column".  It
    952   ** might be possible to form an IN operator with either table1.column
    953   ** or table2.column as the LHS if either is common to every term of
    954   ** the OR clause.
    955   **
    956   ** Note that terms of the form "table.column1=table.column2" (the
    957   ** same table on both sizes of the ==) cannot be optimized.
    958   */
    959   if( chngToIN ){
    960     int okToChngToIN = 0;     /* True if the conversion to IN is valid */
    961     int iColumn = -1;         /* Column index on lhs of IN operator */
    962     int iCursor = -1;         /* Table cursor common to all terms */
    963     int j = 0;                /* Loop counter */
    964 
    965     /* Search for a table and column that appears on one side or the
    966     ** other of the == operator in every subterm.  That table and column
    967     ** will be recorded in iCursor and iColumn.  There might not be any
    968     ** such table and column.  Set okToChngToIN if an appropriate table
    969     ** and column is found but leave okToChngToIN false if not found.
    970     */
    971     for(j=0; j<2 && !okToChngToIN; j++){
    972       pOrTerm = pOrWc->a;
    973       for(i=pOrWc->nTerm-1; i>=0; i--, pOrTerm++){
    974         assert( pOrTerm->eOperator==WO_EQ );
    975         pOrTerm->wtFlags &= ~TERM_OR_OK;
    976         if( pOrTerm->leftCursor==iCursor ){
    977           /* This is the 2-bit case and we are on the second iteration and
    978           ** current term is from the first iteration.  So skip this term. */
    979           assert( j==1 );
    980           continue;
    981         }
    982         if( (chngToIN & getMask(pMaskSet, pOrTerm->leftCursor))==0 ){
    983           /* This term must be of the form t1.a==t2.b where t2 is in the
    984           ** chngToIN set but t1 is not.  This term will be either preceeded
    985           ** or follwed by an inverted copy (t2.b==t1.a).  Skip this term
    986           ** and use its inversion. */
    987           testcase( pOrTerm->wtFlags & TERM_COPIED );
    988           testcase( pOrTerm->wtFlags & TERM_VIRTUAL );
    989           assert( pOrTerm->wtFlags & (TERM_COPIED|TERM_VIRTUAL) );
    990           continue;
    991         }
    992         iColumn = pOrTerm->u.leftColumn;
    993         iCursor = pOrTerm->leftCursor;
    994         break;
    995       }
    996       if( i<0 ){
    997         /* No candidate table+column was found.  This can only occur
    998         ** on the second iteration */
    999         assert( j==1 );
   1000         assert( (chngToIN&(chngToIN-1))==0 );
   1001         assert( chngToIN==getMask(pMaskSet, iCursor) );
   1002         break;
   1003       }
   1004       testcase( j==1 );
   1005 
   1006       /* We have found a candidate table and column.  Check to see if that
   1007       ** table and column is common to every term in the OR clause */
   1008       okToChngToIN = 1;
   1009       for(; i>=0 && okToChngToIN; i--, pOrTerm++){
   1010         assert( pOrTerm->eOperator==WO_EQ );
   1011         if( pOrTerm->leftCursor!=iCursor ){
   1012           pOrTerm->wtFlags &= ~TERM_OR_OK;
   1013         }else if( pOrTerm->u.leftColumn!=iColumn ){
   1014           okToChngToIN = 0;
   1015         }else{
   1016           int affLeft, affRight;
   1017           /* If the right-hand side is also a column, then the affinities
   1018           ** of both right and left sides must be such that no type
   1019           ** conversions are required on the right.  (Ticket #2249)
   1020           */
   1021           affRight = sqlite3ExprAffinity(pOrTerm->pExpr->pRight);
   1022           affLeft = sqlite3ExprAffinity(pOrTerm->pExpr->pLeft);
   1023           if( affRight!=0 && affRight!=affLeft ){
   1024             okToChngToIN = 0;
   1025           }else{
   1026             pOrTerm->wtFlags |= TERM_OR_OK;
   1027           }
   1028         }
   1029       }
   1030     }
   1031 
   1032     /* At this point, okToChngToIN is true if original pTerm satisfies
   1033     ** case 1.  In that case, construct a new virtual term that is
   1034     ** pTerm converted into an IN operator.
   1035     **
   1036     ** EV: R-00211-15100
   1037     */
   1038     if( okToChngToIN ){
   1039       Expr *pDup;            /* A transient duplicate expression */
   1040       ExprList *pList = 0;   /* The RHS of the IN operator */
   1041       Expr *pLeft = 0;       /* The LHS of the IN operator */
   1042       Expr *pNew;            /* The complete IN operator */
   1043 
   1044       for(i=pOrWc->nTerm-1, pOrTerm=pOrWc->a; i>=0; i--, pOrTerm++){
   1045         if( (pOrTerm->wtFlags & TERM_OR_OK)==0 ) continue;
   1046         assert( pOrTerm->eOperator==WO_EQ );
   1047         assert( pOrTerm->leftCursor==iCursor );
   1048         assert( pOrTerm->u.leftColumn==iColumn );
   1049         pDup = sqlite3ExprDup(db, pOrTerm->pExpr->pRight, 0);
   1050         pList = sqlite3ExprListAppend(pWC->pParse, pList, pDup);
   1051         pLeft = pOrTerm->pExpr->pLeft;
   1052       }
   1053       assert( pLeft!=0 );
   1054       pDup = sqlite3ExprDup(db, pLeft, 0);
   1055       pNew = sqlite3PExpr(pParse, TK_IN, pDup, 0, 0);
   1056       if( pNew ){
   1057         int idxNew;
   1058         transferJoinMarkings(pNew, pExpr);
   1059         assert( !ExprHasProperty(pNew, EP_xIsSelect) );
   1060         pNew->x.pList = pList;
   1061         idxNew = whereClauseInsert(pWC, pNew, TERM_VIRTUAL|TERM_DYNAMIC);
   1062         testcase( idxNew==0 );
   1063         exprAnalyze(pSrc, pWC, idxNew);
   1064         pTerm = &pWC->a[idxTerm];
   1065         pWC->a[idxNew].iParent = idxTerm;
   1066         pTerm->nChild = 1;
   1067       }else{
   1068         sqlite3ExprListDelete(db, pList);
   1069       }
   1070       pTerm->eOperator = WO_NOOP;  /* case 1 trumps case 2 */
   1071     }
   1072   }
   1073 }
   1074 #endif /* !SQLITE_OMIT_OR_OPTIMIZATION && !SQLITE_OMIT_SUBQUERY */
   1075 
   1076 
   1077 /*
   1078 ** The input to this routine is an WhereTerm structure with only the
   1079 ** "pExpr" field filled in.  The job of this routine is to analyze the
   1080 ** subexpression and populate all the other fields of the WhereTerm
   1081 ** structure.
   1082 **
   1083 ** If the expression is of the form "<expr> <op> X" it gets commuted
   1084 ** to the standard form of "X <op> <expr>".
   1085 **
   1086 ** If the expression is of the form "X <op> Y" where both X and Y are
   1087 ** columns, then the original expression is unchanged and a new virtual
   1088 ** term of the form "Y <op> X" is added to the WHERE clause and
   1089 ** analyzed separately.  The original term is marked with TERM_COPIED
   1090 ** and the new term is marked with TERM_DYNAMIC (because it's pExpr
   1091 ** needs to be freed with the WhereClause) and TERM_VIRTUAL (because it
   1092 ** is a commuted copy of a prior term.)  The original term has nChild=1
   1093 ** and the copy has idxParent set to the index of the original term.
   1094 */
   1095 static void exprAnalyze(
   1096   SrcList *pSrc,            /* the FROM clause */
   1097   WhereClause *pWC,         /* the WHERE clause */
   1098   int idxTerm               /* Index of the term to be analyzed */
   1099 ){
   1100   WhereTerm *pTerm;                /* The term to be analyzed */
   1101   WhereMaskSet *pMaskSet;          /* Set of table index masks */
   1102   Expr *pExpr;                     /* The expression to be analyzed */
   1103   Bitmask prereqLeft;              /* Prerequesites of the pExpr->pLeft */
   1104   Bitmask prereqAll;               /* Prerequesites of pExpr */
   1105   Bitmask extraRight = 0;          /* Extra dependencies on LEFT JOIN */
   1106   Expr *pStr1 = 0;                 /* RHS of LIKE/GLOB operator */
   1107   int isComplete = 0;              /* RHS of LIKE/GLOB ends with wildcard */
   1108   int noCase = 0;                  /* LIKE/GLOB distinguishes case */
   1109   int op;                          /* Top-level operator.  pExpr->op */
   1110   Parse *pParse = pWC->pParse;     /* Parsing context */
   1111   sqlite3 *db = pParse->db;        /* Database connection */
   1112 
   1113   if( db->mallocFailed ){
   1114     return;
   1115   }
   1116   pTerm = &pWC->a[idxTerm];
   1117   pMaskSet = pWC->pMaskSet;
   1118   pExpr = pTerm->pExpr;
   1119   prereqLeft = exprTableUsage(pMaskSet, pExpr->pLeft);
   1120   op = pExpr->op;
   1121   if( op==TK_IN ){
   1122     assert( pExpr->pRight==0 );
   1123     if( ExprHasProperty(pExpr, EP_xIsSelect) ){
   1124       pTerm->prereqRight = exprSelectTableUsage(pMaskSet, pExpr->x.pSelect);
   1125     }else{
   1126       pTerm->prereqRight = exprListTableUsage(pMaskSet, pExpr->x.pList);
   1127     }
   1128   }else if( op==TK_ISNULL ){
   1129     pTerm->prereqRight = 0;
   1130   }else{
   1131     pTerm->prereqRight = exprTableUsage(pMaskSet, pExpr->pRight);
   1132   }
   1133   prereqAll = exprTableUsage(pMaskSet, pExpr);
   1134   if( ExprHasProperty(pExpr, EP_FromJoin) ){
   1135     Bitmask x = getMask(pMaskSet, pExpr->iRightJoinTable);
   1136     prereqAll |= x;
   1137     extraRight = x-1;  /* ON clause terms may not be used with an index
   1138                        ** on left table of a LEFT JOIN.  Ticket #3015 */
   1139   }
   1140   pTerm->prereqAll = prereqAll;
   1141   pTerm->leftCursor = -1;
   1142   pTerm->iParent = -1;
   1143   pTerm->eOperator = 0;
   1144   if( allowedOp(op) && (pTerm->prereqRight & prereqLeft)==0 ){
   1145     Expr *pLeft = pExpr->pLeft;
   1146     Expr *pRight = pExpr->pRight;
   1147     if( pLeft->op==TK_COLUMN ){
   1148       pTerm->leftCursor = pLeft->iTable;
   1149       pTerm->u.leftColumn = pLeft->iColumn;
   1150       pTerm->eOperator = operatorMask(op);
   1151     }
   1152     if( pRight && pRight->op==TK_COLUMN ){
   1153       WhereTerm *pNew;
   1154       Expr *pDup;
   1155       if( pTerm->leftCursor>=0 ){
   1156         int idxNew;
   1157         pDup = sqlite3ExprDup(db, pExpr, 0);
   1158         if( db->mallocFailed ){
   1159           sqlite3ExprDelete(db, pDup);
   1160           return;
   1161         }
   1162         idxNew = whereClauseInsert(pWC, pDup, TERM_VIRTUAL|TERM_DYNAMIC);
   1163         if( idxNew==0 ) return;
   1164         pNew = &pWC->a[idxNew];
   1165         pNew->iParent = idxTerm;
   1166         pTerm = &pWC->a[idxTerm];
   1167         pTerm->nChild = 1;
   1168         pTerm->wtFlags |= TERM_COPIED;
   1169       }else{
   1170         pDup = pExpr;
   1171         pNew = pTerm;
   1172       }
   1173       exprCommute(pParse, pDup);
   1174       pLeft = pDup->pLeft;
   1175       pNew->leftCursor = pLeft->iTable;
   1176       pNew->u.leftColumn = pLeft->iColumn;
   1177       testcase( (prereqLeft | extraRight) != prereqLeft );
   1178       pNew->prereqRight = prereqLeft | extraRight;
   1179       pNew->prereqAll = prereqAll;
   1180       pNew->eOperator = operatorMask(pDup->op);
   1181     }
   1182   }
   1183 
   1184 #ifndef SQLITE_OMIT_BETWEEN_OPTIMIZATION
   1185   /* If a term is the BETWEEN operator, create two new virtual terms
   1186   ** that define the range that the BETWEEN implements.  For example:
   1187   **
   1188   **      a BETWEEN b AND c
   1189   **
   1190   ** is converted into:
   1191   **
   1192   **      (a BETWEEN b AND c) AND (a>=b) AND (a<=c)
   1193   **
   1194   ** The two new terms are added onto the end of the WhereClause object.
   1195   ** The new terms are "dynamic" and are children of the original BETWEEN
   1196   ** term.  That means that if the BETWEEN term is coded, the children are
   1197   ** skipped.  Or, if the children are satisfied by an index, the original
   1198   ** BETWEEN term is skipped.
   1199   */
   1200   else if( pExpr->op==TK_BETWEEN && pWC->op==TK_AND ){
   1201     ExprList *pList = pExpr->x.pList;
   1202     int i;
   1203     static const u8 ops[] = {TK_GE, TK_LE};
   1204     assert( pList!=0 );
   1205     assert( pList->nExpr==2 );
   1206     for(i=0; i<2; i++){
   1207       Expr *pNewExpr;
   1208       int idxNew;
   1209       pNewExpr = sqlite3PExpr(pParse, ops[i],
   1210                              sqlite3ExprDup(db, pExpr->pLeft, 0),
   1211                              sqlite3ExprDup(db, pList->a[i].pExpr, 0), 0);
   1212       idxNew = whereClauseInsert(pWC, pNewExpr, TERM_VIRTUAL|TERM_DYNAMIC);
   1213       testcase( idxNew==0 );
   1214       exprAnalyze(pSrc, pWC, idxNew);
   1215       pTerm = &pWC->a[idxTerm];
   1216       pWC->a[idxNew].iParent = idxTerm;
   1217     }
   1218     pTerm->nChild = 2;
   1219   }
   1220 #endif /* SQLITE_OMIT_BETWEEN_OPTIMIZATION */
   1221 
   1222 #if !defined(SQLITE_OMIT_OR_OPTIMIZATION) && !defined(SQLITE_OMIT_SUBQUERY)
   1223   /* Analyze a term that is composed of two or more subterms connected by
   1224   ** an OR operator.
   1225   */
   1226   else if( pExpr->op==TK_OR ){
   1227     assert( pWC->op==TK_AND );
   1228     exprAnalyzeOrTerm(pSrc, pWC, idxTerm);
   1229     pTerm = &pWC->a[idxTerm];
   1230   }
   1231 #endif /* SQLITE_OMIT_OR_OPTIMIZATION */
   1232 
   1233 #ifndef SQLITE_OMIT_LIKE_OPTIMIZATION
   1234   /* Add constraints to reduce the search space on a LIKE or GLOB
   1235   ** operator.
   1236   **
   1237   ** A like pattern of the form "x LIKE 'abc%'" is changed into constraints
   1238   **
   1239   **          x>='abc' AND x<'abd' AND x LIKE 'abc%'
   1240   **
   1241   ** The last character of the prefix "abc" is incremented to form the
   1242   ** termination condition "abd".
   1243   */
   1244   if( pWC->op==TK_AND
   1245    && isLikeOrGlob(pParse, pExpr, &pStr1, &isComplete, &noCase)
   1246   ){
   1247     Expr *pLeft;       /* LHS of LIKE/GLOB operator */
   1248     Expr *pStr2;       /* Copy of pStr1 - RHS of LIKE/GLOB operator */
   1249     Expr *pNewExpr1;
   1250     Expr *pNewExpr2;
   1251     int idxNew1;
   1252     int idxNew2;
   1253     CollSeq *pColl;    /* Collating sequence to use */
   1254 
   1255     pLeft = pExpr->x.pList->a[1].pExpr;
   1256     pStr2 = sqlite3ExprDup(db, pStr1, 0);
   1257     if( !db->mallocFailed ){
   1258       u8 c, *pC;       /* Last character before the first wildcard */
   1259       pC = (u8*)&pStr2->u.zToken[sqlite3Strlen30(pStr2->u.zToken)-1];
   1260       c = *pC;
   1261       if( noCase ){
   1262         /* The point is to increment the last character before the first
   1263         ** wildcard.  But if we increment '@', that will push it into the
   1264         ** alphabetic range where case conversions will mess up the
   1265         ** inequality.  To avoid this, make sure to also run the full
   1266         ** LIKE on all candidate expressions by clearing the isComplete flag
   1267         */
   1268         if( c=='A'-1 ) isComplete = 0;   /* EV: R-64339-08207 */
   1269 
   1270 
   1271         c = sqlite3UpperToLower[c];
   1272       }
   1273       *pC = c + 1;
   1274     }
   1275     pColl = sqlite3FindCollSeq(db, SQLITE_UTF8, noCase ? "NOCASE" : "BINARY",0);
   1276     pNewExpr1 = sqlite3PExpr(pParse, TK_GE,
   1277                      sqlite3ExprSetColl(sqlite3ExprDup(db,pLeft,0), pColl),
   1278                      pStr1, 0);
   1279     idxNew1 = whereClauseInsert(pWC, pNewExpr1, TERM_VIRTUAL|TERM_DYNAMIC);
   1280     testcase( idxNew1==0 );
   1281     exprAnalyze(pSrc, pWC, idxNew1);
   1282     pNewExpr2 = sqlite3PExpr(pParse, TK_LT,
   1283                      sqlite3ExprSetColl(sqlite3ExprDup(db,pLeft,0), pColl),
   1284                      pStr2, 0);
   1285     idxNew2 = whereClauseInsert(pWC, pNewExpr2, TERM_VIRTUAL|TERM_DYNAMIC);
   1286     testcase( idxNew2==0 );
   1287     exprAnalyze(pSrc, pWC, idxNew2);
   1288     pTerm = &pWC->a[idxTerm];
   1289     if( isComplete ){
   1290       pWC->a[idxNew1].iParent = idxTerm;
   1291       pWC->a[idxNew2].iParent = idxTerm;
   1292       pTerm->nChild = 2;
   1293     }
   1294   }
   1295 #endif /* SQLITE_OMIT_LIKE_OPTIMIZATION */
   1296 
   1297 #ifndef SQLITE_OMIT_VIRTUALTABLE
   1298   /* Add a WO_MATCH auxiliary term to the constraint set if the
   1299   ** current expression is of the form:  column MATCH expr.
   1300   ** This information is used by the xBestIndex methods of
   1301   ** virtual tables.  The native query optimizer does not attempt
   1302   ** to do anything with MATCH functions.
   1303   */
   1304   if( isMatchOfColumn(pExpr) ){
   1305     int idxNew;
   1306     Expr *pRight, *pLeft;
   1307     WhereTerm *pNewTerm;
   1308     Bitmask prereqColumn, prereqExpr;
   1309 
   1310     pRight = pExpr->x.pList->a[0].pExpr;
   1311     pLeft = pExpr->x.pList->a[1].pExpr;
   1312     prereqExpr = exprTableUsage(pMaskSet, pRight);
   1313     prereqColumn = exprTableUsage(pMaskSet, pLeft);
   1314     if( (prereqExpr & prereqColumn)==0 ){
   1315       Expr *pNewExpr;
   1316       pNewExpr = sqlite3PExpr(pParse, TK_MATCH,
   1317                               0, sqlite3ExprDup(db, pRight, 0), 0);
   1318       idxNew = whereClauseInsert(pWC, pNewExpr, TERM_VIRTUAL|TERM_DYNAMIC);
   1319       testcase( idxNew==0 );
   1320       pNewTerm = &pWC->a[idxNew];
   1321       pNewTerm->prereqRight = prereqExpr;
   1322       pNewTerm->leftCursor = pLeft->iTable;
   1323       pNewTerm->u.leftColumn = pLeft->iColumn;
   1324       pNewTerm->eOperator = WO_MATCH;
   1325       pNewTerm->iParent = idxTerm;
   1326       pTerm = &pWC->a[idxTerm];
   1327       pTerm->nChild = 1;
   1328       pTerm->wtFlags |= TERM_COPIED;
   1329       pNewTerm->prereqAll = pTerm->prereqAll;
   1330     }
   1331   }
   1332 #endif /* SQLITE_OMIT_VIRTUALTABLE */
   1333 
   1334 #ifdef SQLITE_ENABLE_STAT2
   1335   /* When sqlite_stat2 histogram data is available an operator of the
   1336   ** form "x IS NOT NULL" can sometimes be evaluated more efficiently
   1337   ** as "x>NULL" if x is not an INTEGER PRIMARY KEY.  So construct a
   1338   ** virtual term of that form.
   1339   **
   1340   ** Note that the virtual term must be tagged with TERM_VNULL.  This
   1341   ** TERM_VNULL tag will suppress the not-null check at the beginning
   1342   ** of the loop.  Without the TERM_VNULL flag, the not-null check at
   1343   ** the start of the loop will prevent any results from being returned.
   1344   */
   1345   if( pExpr->op==TK_NOTNULL
   1346    && pExpr->pLeft->op==TK_COLUMN
   1347    && pExpr->pLeft->iColumn>=0
   1348   ){
   1349     Expr *pNewExpr;
   1350     Expr *pLeft = pExpr->pLeft;
   1351     int idxNew;
   1352     WhereTerm *pNewTerm;
   1353 
   1354     pNewExpr = sqlite3PExpr(pParse, TK_GT,
   1355                             sqlite3ExprDup(db, pLeft, 0),
   1356                             sqlite3PExpr(pParse, TK_NULL, 0, 0, 0), 0);
   1357 
   1358     idxNew = whereClauseInsert(pWC, pNewExpr,
   1359                               TERM_VIRTUAL|TERM_DYNAMIC|TERM_VNULL);
   1360     if( idxNew ){
   1361       pNewTerm = &pWC->a[idxNew];
   1362       pNewTerm->prereqRight = 0;
   1363       pNewTerm->leftCursor = pLeft->iTable;
   1364       pNewTerm->u.leftColumn = pLeft->iColumn;
   1365       pNewTerm->eOperator = WO_GT;
   1366       pNewTerm->iParent = idxTerm;
   1367       pTerm = &pWC->a[idxTerm];
   1368       pTerm->nChild = 1;
   1369       pTerm->wtFlags |= TERM_COPIED;
   1370       pNewTerm->prereqAll = pTerm->prereqAll;
   1371     }
   1372   }
   1373 #endif /* SQLITE_ENABLE_STAT2 */
   1374 
   1375   /* Prevent ON clause terms of a LEFT JOIN from being used to drive
   1376   ** an index for tables to the left of the join.
   1377   */
   1378   pTerm->prereqRight |= extraRight;
   1379 }
   1380 
   1381 /*
   1382 ** Return TRUE if any of the expressions in pList->a[iFirst...] contain
   1383 ** a reference to any table other than the iBase table.
   1384 */
   1385 static int referencesOtherTables(
   1386   ExprList *pList,          /* Search expressions in ths list */
   1387   WhereMaskSet *pMaskSet,   /* Mapping from tables to bitmaps */
   1388   int iFirst,               /* Be searching with the iFirst-th expression */
   1389   int iBase                 /* Ignore references to this table */
   1390 ){
   1391   Bitmask allowed = ~getMask(pMaskSet, iBase);
   1392   while( iFirst<pList->nExpr ){
   1393     if( (exprTableUsage(pMaskSet, pList->a[iFirst++].pExpr)&allowed)!=0 ){
   1394       return 1;
   1395     }
   1396   }
   1397   return 0;
   1398 }
   1399 
   1400 
   1401 /*
   1402 ** This routine decides if pIdx can be used to satisfy the ORDER BY
   1403 ** clause.  If it can, it returns 1.  If pIdx cannot satisfy the
   1404 ** ORDER BY clause, this routine returns 0.
   1405 **
   1406 ** pOrderBy is an ORDER BY clause from a SELECT statement.  pTab is the
   1407 ** left-most table in the FROM clause of that same SELECT statement and
   1408 ** the table has a cursor number of "base".  pIdx is an index on pTab.
   1409 **
   1410 ** nEqCol is the number of columns of pIdx that are used as equality
   1411 ** constraints.  Any of these columns may be missing from the ORDER BY
   1412 ** clause and the match can still be a success.
   1413 **
   1414 ** All terms of the ORDER BY that match against the index must be either
   1415 ** ASC or DESC.  (Terms of the ORDER BY clause past the end of a UNIQUE
   1416 ** index do not need to satisfy this constraint.)  The *pbRev value is
   1417 ** set to 1 if the ORDER BY clause is all DESC and it is set to 0 if
   1418 ** the ORDER BY clause is all ASC.
   1419 */
   1420 static int isSortingIndex(
   1421   Parse *pParse,          /* Parsing context */
   1422   WhereMaskSet *pMaskSet, /* Mapping from table cursor numbers to bitmaps */
   1423   Index *pIdx,            /* The index we are testing */
   1424   int base,               /* Cursor number for the table to be sorted */
   1425   ExprList *pOrderBy,     /* The ORDER BY clause */
   1426   int nEqCol,             /* Number of index columns with == constraints */
   1427   int wsFlags,            /* Index usages flags */
   1428   int *pbRev              /* Set to 1 if ORDER BY is DESC */
   1429 ){
   1430   int i, j;                       /* Loop counters */
   1431   int sortOrder = 0;              /* XOR of index and ORDER BY sort direction */
   1432   int nTerm;                      /* Number of ORDER BY terms */
   1433   struct ExprList_item *pTerm;    /* A term of the ORDER BY clause */
   1434   sqlite3 *db = pParse->db;
   1435 
   1436   assert( pOrderBy!=0 );
   1437   nTerm = pOrderBy->nExpr;
   1438   assert( nTerm>0 );
   1439 
   1440   /* Argument pIdx must either point to a 'real' named index structure,
   1441   ** or an index structure allocated on the stack by bestBtreeIndex() to
   1442   ** represent the rowid index that is part of every table.  */
   1443   assert( pIdx->zName || (pIdx->nColumn==1 && pIdx->aiColumn[0]==-1) );
   1444 
   1445   /* Match terms of the ORDER BY clause against columns of
   1446   ** the index.
   1447   **
   1448   ** Note that indices have pIdx->nColumn regular columns plus
   1449   ** one additional column containing the rowid.  The rowid column
   1450   ** of the index is also allowed to match against the ORDER BY
   1451   ** clause.
   1452   */
   1453   for(i=j=0, pTerm=pOrderBy->a; j<nTerm && i<=pIdx->nColumn; i++){
   1454     Expr *pExpr;       /* The expression of the ORDER BY pTerm */
   1455     CollSeq *pColl;    /* The collating sequence of pExpr */
   1456     int termSortOrder; /* Sort order for this term */
   1457     int iColumn;       /* The i-th column of the index.  -1 for rowid */
   1458     int iSortOrder;    /* 1 for DESC, 0 for ASC on the i-th index term */
   1459     const char *zColl; /* Name of the collating sequence for i-th index term */
   1460 
   1461     pExpr = pTerm->pExpr;
   1462     if( pExpr->op!=TK_COLUMN || pExpr->iTable!=base ){
   1463       /* Can not use an index sort on anything that is not a column in the
   1464       ** left-most table of the FROM clause */
   1465       break;
   1466     }
   1467     pColl = sqlite3ExprCollSeq(pParse, pExpr);
   1468     if( !pColl ){
   1469       pColl = db->pDfltColl;
   1470     }
   1471     if( pIdx->zName && i<pIdx->nColumn ){
   1472       iColumn = pIdx->aiColumn[i];
   1473       if( iColumn==pIdx->pTable->iPKey ){
   1474         iColumn = -1;
   1475       }
   1476       iSortOrder = pIdx->aSortOrder[i];
   1477       zColl = pIdx->azColl[i];
   1478     }else{
   1479       iColumn = -1;
   1480       iSortOrder = 0;
   1481       zColl = pColl->zName;
   1482     }
   1483     if( pExpr->iColumn!=iColumn || sqlite3StrICmp(pColl->zName, zColl) ){
   1484       /* Term j of the ORDER BY clause does not match column i of the index */
   1485       if( i<nEqCol ){
   1486         /* If an index column that is constrained by == fails to match an
   1487         ** ORDER BY term, that is OK.  Just ignore that column of the index
   1488         */
   1489         continue;
   1490       }else if( i==pIdx->nColumn ){
   1491         /* Index column i is the rowid.  All other terms match. */
   1492         break;
   1493       }else{
   1494         /* If an index column fails to match and is not constrained by ==
   1495         ** then the index cannot satisfy the ORDER BY constraint.
   1496         */
   1497         return 0;
   1498       }
   1499     }
   1500     assert( pIdx->aSortOrder!=0 || iColumn==-1 );
   1501     assert( pTerm->sortOrder==0 || pTerm->sortOrder==1 );
   1502     assert( iSortOrder==0 || iSortOrder==1 );
   1503     termSortOrder = iSortOrder ^ pTerm->sortOrder;
   1504     if( i>nEqCol ){
   1505       if( termSortOrder!=sortOrder ){
   1506         /* Indices can only be used if all ORDER BY terms past the
   1507         ** equality constraints are all either DESC or ASC. */
   1508         return 0;
   1509       }
   1510     }else{
   1511       sortOrder = termSortOrder;
   1512     }
   1513     j++;
   1514     pTerm++;
   1515     if( iColumn<0 && !referencesOtherTables(pOrderBy, pMaskSet, j, base) ){
   1516       /* If the indexed column is the primary key and everything matches
   1517       ** so far and none of the ORDER BY terms to the right reference other
   1518       ** tables in the join, then we are assured that the index can be used
   1519       ** to sort because the primary key is unique and so none of the other
   1520       ** columns will make any difference
   1521       */
   1522       j = nTerm;
   1523     }
   1524   }
   1525 
   1526   *pbRev = sortOrder!=0;
   1527   if( j>=nTerm ){
   1528     /* All terms of the ORDER BY clause are covered by this index so
   1529     ** this index can be used for sorting. */
   1530     return 1;
   1531   }
   1532   if( pIdx->onError!=OE_None && i==pIdx->nColumn
   1533       && (wsFlags & WHERE_COLUMN_NULL)==0
   1534       && !referencesOtherTables(pOrderBy, pMaskSet, j, base) ){
   1535     /* All terms of this index match some prefix of the ORDER BY clause
   1536     ** and the index is UNIQUE and no terms on the tail of the ORDER BY
   1537     ** clause reference other tables in a join.  If this is all true then
   1538     ** the order by clause is superfluous.  Not that if the matching
   1539     ** condition is IS NULL then the result is not necessarily unique
   1540     ** even on a UNIQUE index, so disallow those cases. */
   1541     return 1;
   1542   }
   1543   return 0;
   1544 }
   1545 
   1546 /*
   1547 ** Prepare a crude estimate of the logarithm of the input value.
   1548 ** The results need not be exact.  This is only used for estimating
   1549 ** the total cost of performing operations with O(logN) or O(NlogN)
   1550 ** complexity.  Because N is just a guess, it is no great tragedy if
   1551 ** logN is a little off.
   1552 */
   1553 static double estLog(double N){
   1554   double logN = 1;
   1555   double x = 10;
   1556   while( N>x ){
   1557     logN += 1;
   1558     x *= 10;
   1559   }
   1560   return logN;
   1561 }
   1562 
   1563 /*
   1564 ** Two routines for printing the content of an sqlite3_index_info
   1565 ** structure.  Used for testing and debugging only.  If neither
   1566 ** SQLITE_TEST or SQLITE_DEBUG are defined, then these routines
   1567 ** are no-ops.
   1568 */
   1569 #if !defined(SQLITE_OMIT_VIRTUALTABLE) && defined(SQLITE_DEBUG)
   1570 static void TRACE_IDX_INPUTS(sqlite3_index_info *p){
   1571   int i;
   1572   if( !sqlite3WhereTrace ) return;
   1573   for(i=0; i<p->nConstraint; i++){
   1574     sqlite3DebugPrintf("  constraint[%d]: col=%d termid=%d op=%d usabled=%d\n",
   1575        i,
   1576        p->aConstraint[i].iColumn,
   1577        p->aConstraint[i].iTermOffset,
   1578        p->aConstraint[i].op,
   1579        p->aConstraint[i].usable);
   1580   }
   1581   for(i=0; i<p->nOrderBy; i++){
   1582     sqlite3DebugPrintf("  orderby[%d]: col=%d desc=%d\n",
   1583        i,
   1584        p->aOrderBy[i].iColumn,
   1585        p->aOrderBy[i].desc);
   1586   }
   1587 }
   1588 static void TRACE_IDX_OUTPUTS(sqlite3_index_info *p){
   1589   int i;
   1590   if( !sqlite3WhereTrace ) return;
   1591   for(i=0; i<p->nConstraint; i++){
   1592     sqlite3DebugPrintf("  usage[%d]: argvIdx=%d omit=%d\n",
   1593        i,
   1594        p->aConstraintUsage[i].argvIndex,
   1595        p->aConstraintUsage[i].omit);
   1596   }
   1597   sqlite3DebugPrintf("  idxNum=%d\n", p->idxNum);
   1598   sqlite3DebugPrintf("  idxStr=%s\n", p->idxStr);
   1599   sqlite3DebugPrintf("  orderByConsumed=%d\n", p->orderByConsumed);
   1600   sqlite3DebugPrintf("  estimatedCost=%g\n", p->estimatedCost);
   1601 }
   1602 #else
   1603 #define TRACE_IDX_INPUTS(A)
   1604 #define TRACE_IDX_OUTPUTS(A)
   1605 #endif
   1606 
   1607 /*
   1608 ** Required because bestIndex() is called by bestOrClauseIndex()
   1609 */
   1610 static void bestIndex(
   1611     Parse*, WhereClause*, struct SrcList_item*,
   1612     Bitmask, Bitmask, ExprList*, WhereCost*);
   1613 
   1614 /*
   1615 ** This routine attempts to find an scanning strategy that can be used
   1616 ** to optimize an 'OR' expression that is part of a WHERE clause.
   1617 **
   1618 ** The table associated with FROM clause term pSrc may be either a
   1619 ** regular B-Tree table or a virtual table.
   1620 */
   1621 static void bestOrClauseIndex(
   1622   Parse *pParse,              /* The parsing context */
   1623   WhereClause *pWC,           /* The WHERE clause */
   1624   struct SrcList_item *pSrc,  /* The FROM clause term to search */
   1625   Bitmask notReady,           /* Mask of cursors not available for indexing */
   1626   Bitmask notValid,           /* Cursors not available for any purpose */
   1627   ExprList *pOrderBy,         /* The ORDER BY clause */
   1628   WhereCost *pCost            /* Lowest cost query plan */
   1629 ){
   1630 #ifndef SQLITE_OMIT_OR_OPTIMIZATION
   1631   const int iCur = pSrc->iCursor;   /* The cursor of the table to be accessed */
   1632   const Bitmask maskSrc = getMask(pWC->pMaskSet, iCur);  /* Bitmask for pSrc */
   1633   WhereTerm * const pWCEnd = &pWC->a[pWC->nTerm];        /* End of pWC->a[] */
   1634   WhereTerm *pTerm;                 /* A single term of the WHERE clause */
   1635 
   1636   /* No OR-clause optimization allowed if the INDEXED BY or NOT INDEXED clauses
   1637   ** are used */
   1638   if( pSrc->notIndexed || pSrc->pIndex!=0 ){
   1639     return;
   1640   }
   1641 
   1642   /* Search the WHERE clause terms for a usable WO_OR term. */
   1643   for(pTerm=pWC->a; pTerm<pWCEnd; pTerm++){
   1644     if( pTerm->eOperator==WO_OR
   1645      && ((pTerm->prereqAll & ~maskSrc) & notReady)==0
   1646      && (pTerm->u.pOrInfo->indexable & maskSrc)!=0
   1647     ){
   1648       WhereClause * const pOrWC = &pTerm->u.pOrInfo->wc;
   1649       WhereTerm * const pOrWCEnd = &pOrWC->a[pOrWC->nTerm];
   1650       WhereTerm *pOrTerm;
   1651       int flags = WHERE_MULTI_OR;
   1652       double rTotal = 0;
   1653       double nRow = 0;
   1654       Bitmask used = 0;
   1655 
   1656       for(pOrTerm=pOrWC->a; pOrTerm<pOrWCEnd; pOrTerm++){
   1657         WhereCost sTermCost;
   1658         WHERETRACE(("... Multi-index OR testing for term %d of %d....\n",
   1659           (pOrTerm - pOrWC->a), (pTerm - pWC->a)
   1660         ));
   1661         if( pOrTerm->eOperator==WO_AND ){
   1662           WhereClause *pAndWC = &pOrTerm->u.pAndInfo->wc;
   1663           bestIndex(pParse, pAndWC, pSrc, notReady, notValid, 0, &sTermCost);
   1664         }else if( pOrTerm->leftCursor==iCur ){
   1665           WhereClause tempWC;
   1666           tempWC.pParse = pWC->pParse;
   1667           tempWC.pMaskSet = pWC->pMaskSet;
   1668           tempWC.op = TK_AND;
   1669           tempWC.a = pOrTerm;
   1670           tempWC.nTerm = 1;
   1671           bestIndex(pParse, &tempWC, pSrc, notReady, notValid, 0, &sTermCost);
   1672         }else{
   1673           continue;
   1674         }
   1675         rTotal += sTermCost.rCost;
   1676         nRow += sTermCost.plan.nRow;
   1677         used |= sTermCost.used;
   1678         if( rTotal>=pCost->rCost ) break;
   1679       }
   1680 
   1681       /* If there is an ORDER BY clause, increase the scan cost to account
   1682       ** for the cost of the sort. */
   1683       if( pOrderBy!=0 ){
   1684         WHERETRACE(("... sorting increases OR cost %.9g to %.9g\n",
   1685                     rTotal, rTotal+nRow*estLog(nRow)));
   1686         rTotal += nRow*estLog(nRow);
   1687       }
   1688 
   1689       /* If the cost of scanning using this OR term for optimization is
   1690       ** less than the current cost stored in pCost, replace the contents
   1691       ** of pCost. */
   1692       WHERETRACE(("... multi-index OR cost=%.9g nrow=%.9g\n", rTotal, nRow));
   1693       if( rTotal<pCost->rCost ){
   1694         pCost->rCost = rTotal;
   1695         pCost->used = used;
   1696         pCost->plan.nRow = nRow;
   1697         pCost->plan.wsFlags = flags;
   1698         pCost->plan.u.pTerm = pTerm;
   1699       }
   1700     }
   1701   }
   1702 #endif /* SQLITE_OMIT_OR_OPTIMIZATION */
   1703 }
   1704 
   1705 #ifndef SQLITE_OMIT_AUTOMATIC_INDEX
   1706 /*
   1707 ** Return TRUE if the WHERE clause term pTerm is of a form where it
   1708 ** could be used with an index to access pSrc, assuming an appropriate
   1709 ** index existed.
   1710 */
   1711 static int termCanDriveIndex(
   1712   WhereTerm *pTerm,              /* WHERE clause term to check */
   1713   struct SrcList_item *pSrc,     /* Table we are trying to access */
   1714   Bitmask notReady               /* Tables in outer loops of the join */
   1715 ){
   1716   char aff;
   1717   if( pTerm->leftCursor!=pSrc->iCursor ) return 0;
   1718   if( pTerm->eOperator!=WO_EQ ) return 0;
   1719   if( (pTerm->prereqRight & notReady)!=0 ) return 0;
   1720   aff = pSrc->pTab->aCol[pTerm->u.leftColumn].affinity;
   1721   if( !sqlite3IndexAffinityOk(pTerm->pExpr, aff) ) return 0;
   1722   return 1;
   1723 }
   1724 #endif
   1725 
   1726 #ifndef SQLITE_OMIT_AUTOMATIC_INDEX
   1727 /*
   1728 ** If the query plan for pSrc specified in pCost is a full table scan
   1729 ** and indexing is allows (if there is no NOT INDEXED clause) and it
   1730 ** possible to construct a transient index that would perform better
   1731 ** than a full table scan even when the cost of constructing the index
   1732 ** is taken into account, then alter the query plan to use the
   1733 ** transient index.
   1734 */
   1735 static void bestAutomaticIndex(
   1736   Parse *pParse,              /* The parsing context */
   1737   WhereClause *pWC,           /* The WHERE clause */
   1738   struct SrcList_item *pSrc,  /* The FROM clause term to search */
   1739   Bitmask notReady,           /* Mask of cursors that are not available */
   1740   WhereCost *pCost            /* Lowest cost query plan */
   1741 ){
   1742   double nTableRow;           /* Rows in the input table */
   1743   double logN;                /* log(nTableRow) */
   1744   double costTempIdx;         /* per-query cost of the transient index */
   1745   WhereTerm *pTerm;           /* A single term of the WHERE clause */
   1746   WhereTerm *pWCEnd;          /* End of pWC->a[] */
   1747   Table *pTable;              /* Table tht might be indexed */
   1748 
   1749   if( (pParse->db->flags & SQLITE_AutoIndex)==0 ){
   1750     /* Automatic indices are disabled at run-time */
   1751     return;
   1752   }
   1753   if( (pCost->plan.wsFlags & WHERE_NOT_FULLSCAN)!=0 ){
   1754     /* We already have some kind of index in use for this query. */
   1755     return;
   1756   }
   1757   if( pSrc->notIndexed ){
   1758     /* The NOT INDEXED clause appears in the SQL. */
   1759     return;
   1760   }
   1761 
   1762   assert( pParse->nQueryLoop >= (double)1 );
   1763   pTable = pSrc->pTab;
   1764   nTableRow = pTable->nRowEst;
   1765   logN = estLog(nTableRow);
   1766   costTempIdx = 2*logN*(nTableRow/pParse->nQueryLoop + 1);
   1767   if( costTempIdx>=pCost->rCost ){
   1768     /* The cost of creating the transient table would be greater than
   1769     ** doing the full table scan */
   1770     return;
   1771   }
   1772 
   1773   /* Search for any equality comparison term */
   1774   pWCEnd = &pWC->a[pWC->nTerm];
   1775   for(pTerm=pWC->a; pTerm<pWCEnd; pTerm++){
   1776     if( termCanDriveIndex(pTerm, pSrc, notReady) ){
   1777       WHERETRACE(("auto-index reduces cost from %.1f to %.1f\n",
   1778                     pCost->rCost, costTempIdx));
   1779       pCost->rCost = costTempIdx;
   1780       pCost->plan.nRow = logN + 1;
   1781       pCost->plan.wsFlags = WHERE_TEMP_INDEX;
   1782       pCost->used = pTerm->prereqRight;
   1783       break;
   1784     }
   1785   }
   1786 }
   1787 #else
   1788 # define bestAutomaticIndex(A,B,C,D,E)  /* no-op */
   1789 #endif /* SQLITE_OMIT_AUTOMATIC_INDEX */
   1790 
   1791 
   1792 #ifndef SQLITE_OMIT_AUTOMATIC_INDEX
   1793 /*
   1794 ** Generate code to construct the Index object for an automatic index
   1795 ** and to set up the WhereLevel object pLevel so that the code generator
   1796 ** makes use of the automatic index.
   1797 */
   1798 static void constructAutomaticIndex(
   1799   Parse *pParse,              /* The parsing context */
   1800   WhereClause *pWC,           /* The WHERE clause */
   1801   struct SrcList_item *pSrc,  /* The FROM clause term to get the next index */
   1802   Bitmask notReady,           /* Mask of cursors that are not available */
   1803   WhereLevel *pLevel          /* Write new index here */
   1804 ){
   1805   int nColumn;                /* Number of columns in the constructed index */
   1806   WhereTerm *pTerm;           /* A single term of the WHERE clause */
   1807   WhereTerm *pWCEnd;          /* End of pWC->a[] */
   1808   int nByte;                  /* Byte of memory needed for pIdx */
   1809   Index *pIdx;                /* Object describing the transient index */
   1810   Vdbe *v;                    /* Prepared statement under construction */
   1811   int regIsInit;              /* Register set by initialization */
   1812   int addrInit;               /* Address of the initialization bypass jump */
   1813   Table *pTable;              /* The table being indexed */
   1814   KeyInfo *pKeyinfo;          /* Key information for the index */
   1815   int addrTop;                /* Top of the index fill loop */
   1816   int regRecord;              /* Register holding an index record */
   1817   int n;                      /* Column counter */
   1818   int i;                      /* Loop counter */
   1819   int mxBitCol;               /* Maximum column in pSrc->colUsed */
   1820   CollSeq *pColl;             /* Collating sequence to on a column */
   1821   Bitmask idxCols;            /* Bitmap of columns used for indexing */
   1822   Bitmask extraCols;          /* Bitmap of additional columns */
   1823 
   1824   /* Generate code to skip over the creation and initialization of the
   1825   ** transient index on 2nd and subsequent iterations of the loop. */
   1826   v = pParse->pVdbe;
   1827   assert( v!=0 );
   1828   regIsInit = ++pParse->nMem;
   1829   addrInit = sqlite3VdbeAddOp1(v, OP_If, regIsInit);
   1830   sqlite3VdbeAddOp2(v, OP_Integer, 1, regIsInit);
   1831 
   1832   /* Count the number of columns that will be added to the index
   1833   ** and used to match WHERE clause constraints */
   1834   nColumn = 0;
   1835   pTable = pSrc->pTab;
   1836   pWCEnd = &pWC->a[pWC->nTerm];
   1837   idxCols = 0;
   1838   for(pTerm=pWC->a; pTerm<pWCEnd; pTerm++){
   1839     if( termCanDriveIndex(pTerm, pSrc, notReady) ){
   1840       int iCol = pTerm->u.leftColumn;
   1841       Bitmask cMask = iCol>=BMS ? ((Bitmask)1)<<(BMS-1) : ((Bitmask)1)<<iCol;
   1842       testcase( iCol==BMS );
   1843       testcase( iCol==BMS-1 );
   1844       if( (idxCols & cMask)==0 ){
   1845         nColumn++;
   1846         idxCols |= cMask;
   1847       }
   1848     }
   1849   }
   1850   assert( nColumn>0 );
   1851   pLevel->plan.nEq = nColumn;
   1852 
   1853   /* Count the number of additional columns needed to create a
   1854   ** covering index.  A "covering index" is an index that contains all
   1855   ** columns that are needed by the query.  With a covering index, the
   1856   ** original table never needs to be accessed.  Automatic indices must
   1857   ** be a covering index because the index will not be updated if the
   1858   ** original table changes and the index and table cannot both be used
   1859   ** if they go out of sync.
   1860   */
   1861   extraCols = pSrc->colUsed & (~idxCols | (((Bitmask)1)<<(BMS-1)));
   1862   mxBitCol = (pTable->nCol >= BMS-1) ? BMS-1 : pTable->nCol;
   1863   testcase( pTable->nCol==BMS-1 );
   1864   testcase( pTable->nCol==BMS-2 );
   1865   for(i=0; i<mxBitCol; i++){
   1866     if( extraCols & (((Bitmask)1)<<i) ) nColumn++;
   1867   }
   1868   if( pSrc->colUsed & (((Bitmask)1)<<(BMS-1)) ){
   1869     nColumn += pTable->nCol - BMS + 1;
   1870   }
   1871   pLevel->plan.wsFlags |= WHERE_COLUMN_EQ | WHERE_IDX_ONLY | WO_EQ;
   1872 
   1873   /* Construct the Index object to describe this index */
   1874   nByte = sizeof(Index);
   1875   nByte += nColumn*sizeof(int);     /* Index.aiColumn */
   1876   nByte += nColumn*sizeof(char*);   /* Index.azColl */
   1877   nByte += nColumn;                 /* Index.aSortOrder */
   1878   pIdx = sqlite3DbMallocZero(pParse->db, nByte);
   1879   if( pIdx==0 ) return;
   1880   pLevel->plan.u.pIdx = pIdx;
   1881   pIdx->azColl = (char**)&pIdx[1];
   1882   pIdx->aiColumn = (int*)&pIdx->azColl[nColumn];
   1883   pIdx->aSortOrder = (u8*)&pIdx->aiColumn[nColumn];
   1884   pIdx->zName = "auto-index";
   1885   pIdx->nColumn = nColumn;
   1886   pIdx->pTable = pTable;
   1887   n = 0;
   1888   idxCols = 0;
   1889   for(pTerm=pWC->a; pTerm<pWCEnd; pTerm++){
   1890     if( termCanDriveIndex(pTerm, pSrc, notReady) ){
   1891       int iCol = pTerm->u.leftColumn;
   1892       Bitmask cMask = iCol>=BMS ? ((Bitmask)1)<<(BMS-1) : ((Bitmask)1)<<iCol;
   1893       if( (idxCols & cMask)==0 ){
   1894         Expr *pX = pTerm->pExpr;
   1895         idxCols |= cMask;
   1896         pIdx->aiColumn[n] = pTerm->u.leftColumn;
   1897         pColl = sqlite3BinaryCompareCollSeq(pParse, pX->pLeft, pX->pRight);
   1898         pIdx->azColl[n] = ALWAYS(pColl) ? pColl->zName : "BINARY";
   1899         n++;
   1900       }
   1901     }
   1902   }
   1903   assert( (u32)n==pLevel->plan.nEq );
   1904 
   1905   /* Add additional columns needed to make the automatic index into
   1906   ** a covering index */
   1907   for(i=0; i<mxBitCol; i++){
   1908     if( extraCols & (((Bitmask)1)<<i) ){
   1909       pIdx->aiColumn[n] = i;
   1910       pIdx->azColl[n] = "BINARY";
   1911       n++;
   1912     }
   1913   }
   1914   if( pSrc->colUsed & (((Bitmask)1)<<(BMS-1)) ){
   1915     for(i=BMS-1; i<pTable->nCol; i++){
   1916       pIdx->aiColumn[n] = i;
   1917       pIdx->azColl[n] = "BINARY";
   1918       n++;
   1919     }
   1920   }
   1921   assert( n==nColumn );
   1922 
   1923   /* Create the automatic index */
   1924   pKeyinfo = sqlite3IndexKeyinfo(pParse, pIdx);
   1925   assert( pLevel->iIdxCur>=0 );
   1926   sqlite3VdbeAddOp4(v, OP_OpenAutoindex, pLevel->iIdxCur, nColumn+1, 0,
   1927                     (char*)pKeyinfo, P4_KEYINFO_HANDOFF);
   1928   VdbeComment((v, "for %s", pTable->zName));
   1929 
   1930   /* Fill the automatic index with content */
   1931   addrTop = sqlite3VdbeAddOp1(v, OP_Rewind, pLevel->iTabCur);
   1932   regRecord = sqlite3GetTempReg(pParse);
   1933   sqlite3GenerateIndexKey(pParse, pIdx, pLevel->iTabCur, regRecord, 1);
   1934   sqlite3VdbeAddOp2(v, OP_IdxInsert, pLevel->iIdxCur, regRecord);
   1935   sqlite3VdbeChangeP5(v, OPFLAG_USESEEKRESULT);
   1936   sqlite3VdbeAddOp2(v, OP_Next, pLevel->iTabCur, addrTop+1);
   1937   sqlite3VdbeChangeP5(v, SQLITE_STMTSTATUS_AUTOINDEX);
   1938   sqlite3VdbeJumpHere(v, addrTop);
   1939   sqlite3ReleaseTempReg(pParse, regRecord);
   1940 
   1941   /* Jump here when skipping the initialization */
   1942   sqlite3VdbeJumpHere(v, addrInit);
   1943 }
   1944 #endif /* SQLITE_OMIT_AUTOMATIC_INDEX */
   1945 
   1946 #ifndef SQLITE_OMIT_VIRTUALTABLE
   1947 /*
   1948 ** Allocate and populate an sqlite3_index_info structure. It is the
   1949 ** responsibility of the caller to eventually release the structure
   1950 ** by passing the pointer returned by this function to sqlite3_free().
   1951 */
   1952 static sqlite3_index_info *allocateIndexInfo(
   1953   Parse *pParse,
   1954   WhereClause *pWC,
   1955   struct SrcList_item *pSrc,
   1956   ExprList *pOrderBy
   1957 ){
   1958   int i, j;
   1959   int nTerm;
   1960   struct sqlite3_index_constraint *pIdxCons;
   1961   struct sqlite3_index_orderby *pIdxOrderBy;
   1962   struct sqlite3_index_constraint_usage *pUsage;
   1963   WhereTerm *pTerm;
   1964   int nOrderBy;
   1965   sqlite3_index_info *pIdxInfo;
   1966 
   1967   WHERETRACE(("Recomputing index info for %s...\n", pSrc->pTab->zName));
   1968 
   1969   /* Count the number of possible WHERE clause constraints referring
   1970   ** to this virtual table */
   1971   for(i=nTerm=0, pTerm=pWC->a; i<pWC->nTerm; i++, pTerm++){
   1972     if( pTerm->leftCursor != pSrc->iCursor ) continue;
   1973     assert( (pTerm->eOperator&(pTerm->eOperator-1))==0 );
   1974     testcase( pTerm->eOperator==WO_IN );
   1975     testcase( pTerm->eOperator==WO_ISNULL );
   1976     if( pTerm->eOperator & (WO_IN|WO_ISNULL) ) continue;
   1977     nTerm++;
   1978   }
   1979 
   1980   /* If the ORDER BY clause contains only columns in the current
   1981   ** virtual table then allocate space for the aOrderBy part of
   1982   ** the sqlite3_index_info structure.
   1983   */
   1984   nOrderBy = 0;
   1985   if( pOrderBy ){
   1986     for(i=0; i<pOrderBy->nExpr; i++){
   1987       Expr *pExpr = pOrderBy->a[i].pExpr;
   1988       if( pExpr->op!=TK_COLUMN || pExpr->iTable!=pSrc->iCursor ) break;
   1989     }
   1990     if( i==pOrderBy->nExpr ){
   1991       nOrderBy = pOrderBy->nExpr;
   1992     }
   1993   }
   1994 
   1995   /* Allocate the sqlite3_index_info structure
   1996   */
   1997   pIdxInfo = sqlite3DbMallocZero(pParse->db, sizeof(*pIdxInfo)
   1998                            + (sizeof(*pIdxCons) + sizeof(*pUsage))*nTerm
   1999                            + sizeof(*pIdxOrderBy)*nOrderBy );
   2000   if( pIdxInfo==0 ){
   2001     sqlite3ErrorMsg(pParse, "out of memory");
   2002     /* (double)0 In case of SQLITE_OMIT_FLOATING_POINT... */
   2003     return 0;
   2004   }
   2005 
   2006   /* Initialize the structure.  The sqlite3_index_info structure contains
   2007   ** many fields that are declared "const" to prevent xBestIndex from
   2008   ** changing them.  We have to do some funky casting in order to
   2009   ** initialize those fields.
   2010   */
   2011   pIdxCons = (struct sqlite3_index_constraint*)&pIdxInfo[1];
   2012   pIdxOrderBy = (struct sqlite3_index_orderby*)&pIdxCons[nTerm];
   2013   pUsage = (struct sqlite3_index_constraint_usage*)&pIdxOrderBy[nOrderBy];
   2014   *(int*)&pIdxInfo->nConstraint = nTerm;
   2015   *(int*)&pIdxInfo->nOrderBy = nOrderBy;
   2016   *(struct sqlite3_index_constraint**)&pIdxInfo->aConstraint = pIdxCons;
   2017   *(struct sqlite3_index_orderby**)&pIdxInfo->aOrderBy = pIdxOrderBy;
   2018   *(struct sqlite3_index_constraint_usage**)&pIdxInfo->aConstraintUsage =
   2019                                                                    pUsage;
   2020 
   2021   for(i=j=0, pTerm=pWC->a; i<pWC->nTerm; i++, pTerm++){
   2022     if( pTerm->leftCursor != pSrc->iCursor ) continue;
   2023     assert( (pTerm->eOperator&(pTerm->eOperator-1))==0 );
   2024     testcase( pTerm->eOperator==WO_IN );
   2025     testcase( pTerm->eOperator==WO_ISNULL );
   2026     if( pTerm->eOperator & (WO_IN|WO_ISNULL) ) continue;
   2027     pIdxCons[j].iColumn = pTerm->u.leftColumn;
   2028     pIdxCons[j].iTermOffset = i;
   2029     pIdxCons[j].op = (u8)pTerm->eOperator;
   2030     /* The direct assignment in the previous line is possible only because
   2031     ** the WO_ and SQLITE_INDEX_CONSTRAINT_ codes are identical.  The
   2032     ** following asserts verify this fact. */
   2033     assert( WO_EQ==SQLITE_INDEX_CONSTRAINT_EQ );
   2034     assert( WO_LT==SQLITE_INDEX_CONSTRAINT_LT );
   2035     assert( WO_LE==SQLITE_INDEX_CONSTRAINT_LE );
   2036     assert( WO_GT==SQLITE_INDEX_CONSTRAINT_GT );
   2037     assert( WO_GE==SQLITE_INDEX_CONSTRAINT_GE );
   2038     assert( WO_MATCH==SQLITE_INDEX_CONSTRAINT_MATCH );
   2039     assert( pTerm->eOperator & (WO_EQ|WO_LT|WO_LE|WO_GT|WO_GE|WO_MATCH) );
   2040     j++;
   2041   }
   2042   for(i=0; i<nOrderBy; i++){
   2043     Expr *pExpr = pOrderBy->a[i].pExpr;
   2044     pIdxOrderBy[i].iColumn = pExpr->iColumn;
   2045     pIdxOrderBy[i].desc = pOrderBy->a[i].sortOrder;
   2046   }
   2047 
   2048   return pIdxInfo;
   2049 }
   2050 
   2051 /*
   2052 ** The table object reference passed as the second argument to this function
   2053 ** must represent a virtual table. This function invokes the xBestIndex()
   2054 ** method of the virtual table with the sqlite3_index_info pointer passed
   2055 ** as the argument.
   2056 **
   2057 ** If an error occurs, pParse is populated with an error message and a
   2058 ** non-zero value is returned. Otherwise, 0 is returned and the output
   2059 ** part of the sqlite3_index_info structure is left populated.
   2060 **
   2061 ** Whether or not an error is returned, it is the responsibility of the
   2062 ** caller to eventually free p->idxStr if p->needToFreeIdxStr indicates
   2063 ** that this is required.
   2064 */
   2065 static int vtabBestIndex(Parse *pParse, Table *pTab, sqlite3_index_info *p){
   2066   sqlite3_vtab *pVtab = sqlite3GetVTable(pParse->db, pTab)->pVtab;
   2067   int i;
   2068   int rc;
   2069 
   2070   WHERETRACE(("xBestIndex for %s\n", pTab->zName));
   2071   TRACE_IDX_INPUTS(p);
   2072   rc = pVtab->pModule->xBestIndex(pVtab, p);
   2073   TRACE_IDX_OUTPUTS(p);
   2074 
   2075   if( rc!=SQLITE_OK ){
   2076     if( rc==SQLITE_NOMEM ){
   2077       pParse->db->mallocFailed = 1;
   2078     }else if( !pVtab->zErrMsg ){
   2079       sqlite3ErrorMsg(pParse, "%s", sqlite3ErrStr(rc));
   2080     }else{
   2081       sqlite3ErrorMsg(pParse, "%s", pVtab->zErrMsg);
   2082     }
   2083   }
   2084   sqlite3_free(pVtab->zErrMsg);
   2085   pVtab->zErrMsg = 0;
   2086 
   2087   for(i=0; i<p->nConstraint; i++){
   2088     if( !p->aConstraint[i].usable && p->aConstraintUsage[i].argvIndex>0 ){
   2089       sqlite3ErrorMsg(pParse,
   2090           "table %s: xBestIndex returned an invalid plan", pTab->zName);
   2091     }
   2092   }
   2093 
   2094   return pParse->nErr;
   2095 }
   2096 
   2097 
   2098 /*
   2099 ** Compute the best index for a virtual table.
   2100 **
   2101 ** The best index is computed by the xBestIndex method of the virtual
   2102 ** table module.  This routine is really just a wrapper that sets up
   2103 ** the sqlite3_index_info structure that is used to communicate with
   2104 ** xBestIndex.
   2105 **
   2106 ** In a join, this routine might be called multiple times for the
   2107 ** same virtual table.  The sqlite3_index_info structure is created
   2108 ** and initialized on the first invocation and reused on all subsequent
   2109 ** invocations.  The sqlite3_index_info structure is also used when
   2110 ** code is generated to access the virtual table.  The whereInfoDelete()
   2111 ** routine takes care of freeing the sqlite3_index_info structure after
   2112 ** everybody has finished with it.
   2113 */
   2114 static void bestVirtualIndex(
   2115   Parse *pParse,                  /* The parsing context */
   2116   WhereClause *pWC,               /* The WHERE clause */
   2117   struct SrcList_item *pSrc,      /* The FROM clause term to search */
   2118   Bitmask notReady,               /* Mask of cursors not available for index */
   2119   Bitmask notValid,               /* Cursors not valid for any purpose */
   2120   ExprList *pOrderBy,             /* The order by clause */
   2121   WhereCost *pCost,               /* Lowest cost query plan */
   2122   sqlite3_index_info **ppIdxInfo  /* Index information passed to xBestIndex */
   2123 ){
   2124   Table *pTab = pSrc->pTab;
   2125   sqlite3_index_info *pIdxInfo;
   2126   struct sqlite3_index_constraint *pIdxCons;
   2127   struct sqlite3_index_constraint_usage *pUsage;
   2128   WhereTerm *pTerm;
   2129   int i, j;
   2130   int nOrderBy;
   2131   double rCost;
   2132 
   2133   /* Make sure wsFlags is initialized to some sane value. Otherwise, if the
   2134   ** malloc in allocateIndexInfo() fails and this function returns leaving
   2135   ** wsFlags in an uninitialized state, the caller may behave unpredictably.
   2136   */
   2137   memset(pCost, 0, sizeof(*pCost));
   2138   pCost->plan.wsFlags = WHERE_VIRTUALTABLE;
   2139 
   2140   /* If the sqlite3_index_info structure has not been previously
   2141   ** allocated and initialized, then allocate and initialize it now.
   2142   */
   2143   pIdxInfo = *ppIdxInfo;
   2144   if( pIdxInfo==0 ){
   2145     *ppIdxInfo = pIdxInfo = allocateIndexInfo(pParse, pWC, pSrc, pOrderBy);
   2146   }
   2147   if( pIdxInfo==0 ){
   2148     return;
   2149   }
   2150 
   2151   /* At this point, the sqlite3_index_info structure that pIdxInfo points
   2152   ** to will have been initialized, either during the current invocation or
   2153   ** during some prior invocation.  Now we just have to customize the
   2154   ** details of pIdxInfo for the current invocation and pass it to
   2155   ** xBestIndex.
   2156   */
   2157 
   2158   /* The module name must be defined. Also, by this point there must
   2159   ** be a pointer to an sqlite3_vtab structure. Otherwise
   2160   ** sqlite3ViewGetColumnNames() would have picked up the error.
   2161   */
   2162   assert( pTab->azModuleArg && pTab->azModuleArg[0] );
   2163   assert( sqlite3GetVTable(pParse->db, pTab) );
   2164 
   2165   /* Set the aConstraint[].usable fields and initialize all
   2166   ** output variables to zero.
   2167   **
   2168   ** aConstraint[].usable is true for constraints where the right-hand
   2169   ** side contains only references to tables to the left of the current
   2170   ** table.  In other words, if the constraint is of the form:
   2171   **
   2172   **           column = expr
   2173   **
   2174   ** and we are evaluating a join, then the constraint on column is
   2175   ** only valid if all tables referenced in expr occur to the left
   2176   ** of the table containing column.
   2177   **
   2178   ** The aConstraints[] array contains entries for all constraints
   2179   ** on the current table.  That way we only have to compute it once
   2180   ** even though we might try to pick the best index multiple times.
   2181   ** For each attempt at picking an index, the order of tables in the
   2182   ** join might be different so we have to recompute the usable flag
   2183   ** each time.
   2184   */
   2185   pIdxCons = *(struct sqlite3_index_constraint**)&pIdxInfo->aConstraint;
   2186   pUsage = pIdxInfo->aConstraintUsage;
   2187   for(i=0; i<pIdxInfo->nConstraint; i++, pIdxCons++){
   2188     j = pIdxCons->iTermOffset;
   2189     pTerm = &pWC->a[j];
   2190     pIdxCons->usable = (pTerm->prereqRight&notReady) ? 0 : 1;
   2191   }
   2192   memset(pUsage, 0, sizeof(pUsage[0])*pIdxInfo->nConstraint);
   2193   if( pIdxInfo->needToFreeIdxStr ){
   2194     sqlite3_free(pIdxInfo->idxStr);
   2195   }
   2196   pIdxInfo->idxStr = 0;
   2197   pIdxInfo->idxNum = 0;
   2198   pIdxInfo->needToFreeIdxStr = 0;
   2199   pIdxInfo->orderByConsumed = 0;
   2200   /* ((double)2) In case of SQLITE_OMIT_FLOATING_POINT... */
   2201   pIdxInfo->estimatedCost = SQLITE_BIG_DBL / ((double)2);
   2202   nOrderBy = pIdxInfo->nOrderBy;
   2203   if( !pOrderBy ){
   2204     pIdxInfo->nOrderBy = 0;
   2205   }
   2206 
   2207   if( vtabBestIndex(pParse, pTab, pIdxInfo) ){
   2208     return;
   2209   }
   2210 
   2211   pIdxCons = *(struct sqlite3_index_constraint**)&pIdxInfo->aConstraint;
   2212   for(i=0; i<pIdxInfo->nConstraint; i++){
   2213     if( pUsage[i].argvIndex>0 ){
   2214       pCost->used |= pWC->a[pIdxCons[i].iTermOffset].prereqRight;
   2215     }
   2216   }
   2217 
   2218   /* If there is an ORDER BY clause, and the selected virtual table index
   2219   ** does not satisfy it, increase the cost of the scan accordingly. This
   2220   ** matches the processing for non-virtual tables in bestBtreeIndex().
   2221   */
   2222   rCost = pIdxInfo->estimatedCost;
   2223   if( pOrderBy && pIdxInfo->orderByConsumed==0 ){
   2224     rCost += estLog(rCost)*rCost;
   2225   }
   2226 
   2227   /* The cost is not allowed to be larger than SQLITE_BIG_DBL (the
   2228   ** inital value of lowestCost in this loop. If it is, then the
   2229   ** (cost<lowestCost) test below will never be true.
   2230   **
   2231   ** Use "(double)2" instead of "2.0" in case OMIT_FLOATING_POINT
   2232   ** is defined.
   2233   */
   2234   if( (SQLITE_BIG_DBL/((double)2))<rCost ){
   2235     pCost->rCost = (SQLITE_BIG_DBL/((double)2));
   2236   }else{
   2237     pCost->rCost = rCost;
   2238   }
   2239   pCost->plan.u.pVtabIdx = pIdxInfo;
   2240   if( pIdxInfo->orderByConsumed ){
   2241     pCost->plan.wsFlags |= WHERE_ORDERBY;
   2242   }
   2243   pCost->plan.nEq = 0;
   2244   pIdxInfo->nOrderBy = nOrderBy;
   2245 
   2246   /* Try to find a more efficient access pattern by using multiple indexes
   2247   ** to optimize an OR expression within the WHERE clause.
   2248   */
   2249   bestOrClauseIndex(pParse, pWC, pSrc, notReady, notValid, pOrderBy, pCost);
   2250 }
   2251 #endif /* SQLITE_OMIT_VIRTUALTABLE */
   2252 
   2253 /*
   2254 ** Argument pIdx is a pointer to an index structure that has an array of
   2255 ** SQLITE_INDEX_SAMPLES evenly spaced samples of the first indexed column
   2256 ** stored in Index.aSample. These samples divide the domain of values stored
   2257 ** the index into (SQLITE_INDEX_SAMPLES+1) regions.
   2258 ** Region 0 contains all values less than the first sample value. Region
   2259 ** 1 contains values between the first and second samples.  Region 2 contains
   2260 ** values between samples 2 and 3.  And so on.  Region SQLITE_INDEX_SAMPLES
   2261 ** contains values larger than the last sample.
   2262 **
   2263 ** If the index contains many duplicates of a single value, then it is
   2264 ** possible that two or more adjacent samples can hold the same value.
   2265 ** When that is the case, the smallest possible region code is returned
   2266 ** when roundUp is false and the largest possible region code is returned
   2267 ** when roundUp is true.
   2268 **
   2269 ** If successful, this function determines which of the regions value
   2270 ** pVal lies in, sets *piRegion to the region index (a value between 0
   2271 ** and SQLITE_INDEX_SAMPLES+1, inclusive) and returns SQLITE_OK.
   2272 ** Or, if an OOM occurs while converting text values between encodings,
   2273 ** SQLITE_NOMEM is returned and *piRegion is undefined.
   2274 */
   2275 #ifdef SQLITE_ENABLE_STAT2
   2276 static int whereRangeRegion(
   2277   Parse *pParse,              /* Database connection */
   2278   Index *pIdx,                /* Index to consider domain of */
   2279   sqlite3_value *pVal,        /* Value to consider */
   2280   int roundUp,                /* Return largest valid region if true */
   2281   int *piRegion               /* OUT: Region of domain in which value lies */
   2282 ){
   2283   assert( roundUp==0 || roundUp==1 );
   2284   if( ALWAYS(pVal) ){
   2285     IndexSample *aSample = pIdx->aSample;
   2286     int i = 0;
   2287     int eType = sqlite3_value_type(pVal);
   2288 
   2289     if( eType==SQLITE_INTEGER || eType==SQLITE_FLOAT ){
   2290       double r = sqlite3_value_double(pVal);
   2291       for(i=0; i<SQLITE_INDEX_SAMPLES; i++){
   2292         if( aSample[i].eType==SQLITE_NULL ) continue;
   2293         if( aSample[i].eType>=SQLITE_TEXT ) break;
   2294         if( roundUp ){
   2295           if( aSample[i].u.r>r ) break;
   2296         }else{
   2297           if( aSample[i].u.r>=r ) break;
   2298         }
   2299       }
   2300     }else if( eType==SQLITE_NULL ){
   2301       i = 0;
   2302       if( roundUp ){
   2303         while( i<SQLITE_INDEX_SAMPLES && aSample[i].eType==SQLITE_NULL ) i++;
   2304       }
   2305     }else{
   2306       sqlite3 *db = pParse->db;
   2307       CollSeq *pColl;
   2308       const u8 *z;
   2309       int n;
   2310 
   2311       /* pVal comes from sqlite3ValueFromExpr() so the type cannot be NULL */
   2312       assert( eType==SQLITE_TEXT || eType==SQLITE_BLOB );
   2313 
   2314       if( eType==SQLITE_BLOB ){
   2315         z = (const u8 *)sqlite3_value_blob(pVal);
   2316         pColl = db->pDfltColl;
   2317         assert( pColl->enc==SQLITE_UTF8 );
   2318       }else{
   2319         pColl = sqlite3GetCollSeq(db, SQLITE_UTF8, 0, *pIdx->azColl);
   2320         if( pColl==0 ){
   2321           sqlite3ErrorMsg(pParse, "no such collation sequence: %s",
   2322                           *pIdx->azColl);
   2323           return SQLITE_ERROR;
   2324         }
   2325         z = (const u8 *)sqlite3ValueText(pVal, pColl->enc);
   2326         if( !z ){
   2327           return SQLITE_NOMEM;
   2328         }
   2329         assert( z && pColl && pColl->xCmp );
   2330       }
   2331       n = sqlite3ValueBytes(pVal, pColl->enc);
   2332 
   2333       for(i=0; i<SQLITE_INDEX_SAMPLES; i++){
   2334         int c;
   2335         int eSampletype = aSample[i].eType;
   2336         if( eSampletype==SQLITE_NULL || eSampletype<eType ) continue;
   2337         if( (eSampletype!=eType) ) break;
   2338 #ifndef SQLITE_OMIT_UTF16
   2339         if( pColl->enc!=SQLITE_UTF8 ){
   2340           int nSample;
   2341           char *zSample = sqlite3Utf8to16(
   2342               db, pColl->enc, aSample[i].u.z, aSample[i].nByte, &nSample
   2343           );
   2344           if( !zSample ){
   2345             assert( db->mallocFailed );
   2346             return SQLITE_NOMEM;
   2347           }
   2348           c = pColl->xCmp(pColl->pUser, nSample, zSample, n, z);
   2349           sqlite3DbFree(db, zSample);
   2350         }else
   2351 #endif
   2352         {
   2353           c = pColl->xCmp(pColl->pUser, aSample[i].nByte, aSample[i].u.z, n, z);
   2354         }
   2355         if( c-roundUp>=0 ) break;
   2356       }
   2357     }
   2358 
   2359     assert( i>=0 && i<=SQLITE_INDEX_SAMPLES );
   2360     *piRegion = i;
   2361   }
   2362   return SQLITE_OK;
   2363 }
   2364 #endif   /* #ifdef SQLITE_ENABLE_STAT2 */
   2365 
   2366 /*
   2367 ** If expression pExpr represents a literal value, set *pp to point to
   2368 ** an sqlite3_value structure containing the same value, with affinity
   2369 ** aff applied to it, before returning. It is the responsibility of the
   2370 ** caller to eventually release this structure by passing it to
   2371 ** sqlite3ValueFree().
   2372 **
   2373 ** If the current parse is a recompile (sqlite3Reprepare()) and pExpr
   2374 ** is an SQL variable that currently has a non-NULL value bound to it,
   2375 ** create an sqlite3_value structure containing this value, again with
   2376 ** affinity aff applied to it, instead.
   2377 **
   2378 ** If neither of the above apply, set *pp to NULL.
   2379 **
   2380 ** If an error occurs, return an error code. Otherwise, SQLITE_OK.
   2381 */
   2382 #ifdef SQLITE_ENABLE_STAT2
   2383 static int valueFromExpr(
   2384   Parse *pParse,
   2385   Expr *pExpr,
   2386   u8 aff,
   2387   sqlite3_value **pp
   2388 ){
   2389   if( pExpr->op==TK_VARIABLE
   2390    || (pExpr->op==TK_REGISTER && pExpr->op2==TK_VARIABLE)
   2391   ){
   2392     int iVar = pExpr->iColumn;
   2393     sqlite3VdbeSetVarmask(pParse->pVdbe, iVar); /* IMP: R-23257-02778 */
   2394     *pp = sqlite3VdbeGetValue(pParse->pReprepare, iVar, aff);
   2395     return SQLITE_OK;
   2396   }
   2397   return sqlite3ValueFromExpr(pParse->db, pExpr, SQLITE_UTF8, aff, pp);
   2398 }
   2399 #endif
   2400 
   2401 /*
   2402 ** This function is used to estimate the number of rows that will be visited
   2403 ** by scanning an index for a range of values. The range may have an upper
   2404 ** bound, a lower bound, or both. The WHERE clause terms that set the upper
   2405 ** and lower bounds are represented by pLower and pUpper respectively. For
   2406 ** example, assuming that index p is on t1(a):
   2407 **
   2408 **   ... FROM t1 WHERE a > ? AND a < ? ...
   2409 **                    |_____|   |_____|
   2410 **                       |         |
   2411 **                     pLower    pUpper
   2412 **
   2413 ** If either of the upper or lower bound is not present, then NULL is passed in
   2414 ** place of the corresponding WhereTerm.
   2415 **
   2416 ** The nEq parameter is passed the index of the index column subject to the
   2417 ** range constraint. Or, equivalently, the number of equality constraints
   2418 ** optimized by the proposed index scan. For example, assuming index p is
   2419 ** on t1(a, b), and the SQL query is:
   2420 **
   2421 **   ... FROM t1 WHERE a = ? AND b > ? AND b < ? ...
   2422 **
   2423 ** then nEq should be passed the value 1 (as the range restricted column,
   2424 ** b, is the second left-most column of the index). Or, if the query is:
   2425 **
   2426 **   ... FROM t1 WHERE a > ? AND a < ? ...
   2427 **
   2428 ** then nEq should be passed 0.
   2429 **
   2430 ** The returned value is an integer between 1 and 100, inclusive. A return
   2431 ** value of 1 indicates that the proposed range scan is expected to visit
   2432 ** approximately 1/100th (1%) of the rows selected by the nEq equality
   2433 ** constraints (if any). A return value of 100 indicates that it is expected
   2434 ** that the range scan will visit every row (100%) selected by the equality
   2435 ** constraints.
   2436 **
   2437 ** In the absence of sqlite_stat2 ANALYZE data, each range inequality
   2438 ** reduces the search space by 3/4ths.  Hence a single constraint (x>?)
   2439 ** results in a return of 25 and a range constraint (x>? AND x<?) results
   2440 ** in a return of 6.
   2441 */
   2442 static int whereRangeScanEst(
   2443   Parse *pParse,       /* Parsing & code generating context */
   2444   Index *p,            /* The index containing the range-compared column; "x" */
   2445   int nEq,             /* index into p->aCol[] of the range-compared column */
   2446   WhereTerm *pLower,   /* Lower bound on the range. ex: "x>123" Might be NULL */
   2447   WhereTerm *pUpper,   /* Upper bound on the range. ex: "x<455" Might be NULL */
   2448   int *piEst           /* OUT: Return value */
   2449 ){
   2450   int rc = SQLITE_OK;
   2451 
   2452 #ifdef SQLITE_ENABLE_STAT2
   2453 
   2454   if( nEq==0 && p->aSample ){
   2455     sqlite3_value *pLowerVal = 0;
   2456     sqlite3_value *pUpperVal = 0;
   2457     int iEst;
   2458     int iLower = 0;
   2459     int iUpper = SQLITE_INDEX_SAMPLES;
   2460     int roundUpUpper = 0;
   2461     int roundUpLower = 0;
   2462     u8 aff = p->pTable->aCol[p->aiColumn[0]].affinity;
   2463 
   2464     if( pLower ){
   2465       Expr *pExpr = pLower->pExpr->pRight;
   2466       rc = valueFromExpr(pParse, pExpr, aff, &pLowerVal);
   2467       assert( pLower->eOperator==WO_GT || pLower->eOperator==WO_GE );
   2468       roundUpLower = (pLower->eOperator==WO_GT) ?1:0;
   2469     }
   2470     if( rc==SQLITE_OK && pUpper ){
   2471       Expr *pExpr = pUpper->pExpr->pRight;
   2472       rc = valueFromExpr(pParse, pExpr, aff, &pUpperVal);
   2473       assert( pUpper->eOperator==WO_LT || pUpper->eOperator==WO_LE );
   2474       roundUpUpper = (pUpper->eOperator==WO_LE) ?1:0;
   2475     }
   2476 
   2477     if( rc!=SQLITE_OK || (pLowerVal==0 && pUpperVal==0) ){
   2478       sqlite3ValueFree(pLowerVal);
   2479       sqlite3ValueFree(pUpperVal);
   2480       goto range_est_fallback;
   2481     }else if( pLowerVal==0 ){
   2482       rc = whereRangeRegion(pParse, p, pUpperVal, roundUpUpper, &iUpper);
   2483       if( pLower ) iLower = iUpper/2;
   2484     }else if( pUpperVal==0 ){
   2485       rc = whereRangeRegion(pParse, p, pLowerVal, roundUpLower, &iLower);
   2486       if( pUpper ) iUpper = (iLower + SQLITE_INDEX_SAMPLES + 1)/2;
   2487     }else{
   2488       rc = whereRangeRegion(pParse, p, pUpperVal, roundUpUpper, &iUpper);
   2489       if( rc==SQLITE_OK ){
   2490         rc = whereRangeRegion(pParse, p, pLowerVal, roundUpLower, &iLower);
   2491       }
   2492     }
   2493     WHERETRACE(("range scan regions: %d..%d\n", iLower, iUpper));
   2494 
   2495     iEst = iUpper - iLower;
   2496     testcase( iEst==SQLITE_INDEX_SAMPLES );
   2497     assert( iEst<=SQLITE_INDEX_SAMPLES );
   2498     if( iEst<1 ){
   2499       *piEst = 50/SQLITE_INDEX_SAMPLES;
   2500     }else{
   2501       *piEst = (iEst*100)/SQLITE_INDEX_SAMPLES;
   2502     }
   2503     sqlite3ValueFree(pLowerVal);
   2504     sqlite3ValueFree(pUpperVal);
   2505     return rc;
   2506   }
   2507 range_est_fallback:
   2508 #else
   2509   UNUSED_PARAMETER(pParse);
   2510   UNUSED_PARAMETER(p);
   2511   UNUSED_PARAMETER(nEq);
   2512 #endif
   2513   assert( pLower || pUpper );
   2514   *piEst = 100;
   2515   if( pLower && (pLower->wtFlags & TERM_VNULL)==0 ) *piEst /= 4;
   2516   if( pUpper ) *piEst /= 4;
   2517   return rc;
   2518 }
   2519 
   2520 #ifdef SQLITE_ENABLE_STAT2
   2521 /*
   2522 ** Estimate the number of rows that will be returned based on
   2523 ** an equality constraint x=VALUE and where that VALUE occurs in
   2524 ** the histogram data.  This only works when x is the left-most
   2525 ** column of an index and sqlite_stat2 histogram data is available
   2526 ** for that index.  When pExpr==NULL that means the constraint is
   2527 ** "x IS NULL" instead of "x=VALUE".
   2528 **
   2529 ** Write the estimated row count into *pnRow and return SQLITE_OK.
   2530 ** If unable to make an estimate, leave *pnRow unchanged and return
   2531 ** non-zero.
   2532 **
   2533 ** This routine can fail if it is unable to load a collating sequence
   2534 ** required for string comparison, or if unable to allocate memory
   2535 ** for a UTF conversion required for comparison.  The error is stored
   2536 ** in the pParse structure.
   2537 */
   2538 static int whereEqualScanEst(
   2539   Parse *pParse,       /* Parsing & code generating context */
   2540   Index *p,            /* The index whose left-most column is pTerm */
   2541   Expr *pExpr,         /* Expression for VALUE in the x=VALUE constraint */
   2542   double *pnRow        /* Write the revised row estimate here */
   2543 ){
   2544   sqlite3_value *pRhs = 0;  /* VALUE on right-hand side of pTerm */
   2545   int iLower, iUpper;       /* Range of histogram regions containing pRhs */
   2546   u8 aff;                   /* Column affinity */
   2547   int rc;                   /* Subfunction return code */
   2548   double nRowEst;           /* New estimate of the number of rows */
   2549 
   2550   assert( p->aSample!=0 );
   2551   aff = p->pTable->aCol[p->aiColumn[0]].affinity;
   2552   if( pExpr ){
   2553     rc = valueFromExpr(pParse, pExpr, aff, &pRhs);
   2554     if( rc ) goto whereEqualScanEst_cancel;
   2555   }else{
   2556     pRhs = sqlite3ValueNew(pParse->db);
   2557   }
   2558   if( pRhs==0 ) return SQLITE_NOTFOUND;
   2559   rc = whereRangeRegion(pParse, p, pRhs, 0, &iLower);
   2560   if( rc ) goto whereEqualScanEst_cancel;
   2561   rc = whereRangeRegion(pParse, p, pRhs, 1, &iUpper);
   2562   if( rc ) goto whereEqualScanEst_cancel;
   2563   WHERETRACE(("equality scan regions: %d..%d\n", iLower, iUpper));
   2564   if( iLower>=iUpper ){
   2565     nRowEst = p->aiRowEst[0]/(SQLITE_INDEX_SAMPLES*2);
   2566     if( nRowEst<*pnRow ) *pnRow = nRowEst;
   2567   }else{
   2568     nRowEst = (iUpper-iLower)*p->aiRowEst[0]/SQLITE_INDEX_SAMPLES;
   2569     *pnRow = nRowEst;
   2570   }
   2571 
   2572 whereEqualScanEst_cancel:
   2573   sqlite3ValueFree(pRhs);
   2574   return rc;
   2575 }
   2576 #endif /* defined(SQLITE_ENABLE_STAT2) */
   2577 
   2578 #ifdef SQLITE_ENABLE_STAT2
   2579 /*
   2580 ** Estimate the number of rows that will be returned based on
   2581 ** an IN constraint where the right-hand side of the IN operator
   2582 ** is a list of values.  Example:
   2583 **
   2584 **        WHERE x IN (1,2,3,4)
   2585 **
   2586 ** Write the estimated row count into *pnRow and return SQLITE_OK.
   2587 ** If unable to make an estimate, leave *pnRow unchanged and return
   2588 ** non-zero.
   2589 **
   2590 ** This routine can fail if it is unable to load a collating sequence
   2591 ** required for string comparison, or if unable to allocate memory
   2592 ** for a UTF conversion required for comparison.  The error is stored
   2593 ** in the pParse structure.
   2594 */
   2595 static int whereInScanEst(
   2596   Parse *pParse,       /* Parsing & code generating context */
   2597   Index *p,            /* The index whose left-most column is pTerm */
   2598   ExprList *pList,     /* The value list on the RHS of "x IN (v1,v2,v3,...)" */
   2599   double *pnRow        /* Write the revised row estimate here */
   2600 ){
   2601   sqlite3_value *pVal = 0;  /* One value from list */
   2602   int iLower, iUpper;       /* Range of histogram regions containing pRhs */
   2603   u8 aff;                   /* Column affinity */
   2604   int rc = SQLITE_OK;       /* Subfunction return code */
   2605   double nRowEst;           /* New estimate of the number of rows */
   2606   int nSpan = 0;            /* Number of histogram regions spanned */
   2607   int nSingle = 0;          /* Histogram regions hit by a single value */
   2608   int nNotFound = 0;        /* Count of values that are not constants */
   2609   int i;                               /* Loop counter */
   2610   u8 aSpan[SQLITE_INDEX_SAMPLES+1];    /* Histogram regions that are spanned */
   2611   u8 aSingle[SQLITE_INDEX_SAMPLES+1];  /* Histogram regions hit once */
   2612 
   2613   assert( p->aSample!=0 );
   2614   aff = p->pTable->aCol[p->aiColumn[0]].affinity;
   2615   memset(aSpan, 0, sizeof(aSpan));
   2616   memset(aSingle, 0, sizeof(aSingle));
   2617   for(i=0; i<pList->nExpr; i++){
   2618     sqlite3ValueFree(pVal);
   2619     rc = valueFromExpr(pParse, pList->a[i].pExpr, aff, &pVal);
   2620     if( rc ) break;
   2621     if( pVal==0 || sqlite3_value_type(pVal)==SQLITE_NULL ){
   2622       nNotFound++;
   2623       continue;
   2624     }
   2625     rc = whereRangeRegion(pParse, p, pVal, 0, &iLower);
   2626     if( rc ) break;
   2627     rc = whereRangeRegion(pParse, p, pVal, 1, &iUpper);
   2628     if( rc ) break;
   2629     if( iLower>=iUpper ){
   2630       aSingle[iLower] = 1;
   2631     }else{
   2632       assert( iLower>=0 && iUpper<=SQLITE_INDEX_SAMPLES );
   2633       while( iLower<iUpper ) aSpan[iLower++] = 1;
   2634     }
   2635   }
   2636   if( rc==SQLITE_OK ){
   2637     for(i=nSpan=0; i<=SQLITE_INDEX_SAMPLES; i++){
   2638       if( aSpan[i] ){
   2639         nSpan++;
   2640       }else if( aSingle[i] ){
   2641         nSingle++;
   2642       }
   2643     }
   2644     nRowEst = (nSpan*2+nSingle)*p->aiRowEst[0]/(2*SQLITE_INDEX_SAMPLES)
   2645                + nNotFound*p->aiRowEst[1];
   2646     if( nRowEst > p->aiRowEst[0] ) nRowEst = p->aiRowEst[0];
   2647     *pnRow = nRowEst;
   2648     WHERETRACE(("IN row estimate: nSpan=%d, nSingle=%d, nNotFound=%d, est=%g\n",
   2649                  nSpan, nSingle, nNotFound, nRowEst));
   2650   }
   2651   sqlite3ValueFree(pVal);
   2652   return rc;
   2653 }
   2654 #endif /* defined(SQLITE_ENABLE_STAT2) */
   2655 
   2656 
   2657 /*
   2658 ** Find the best query plan for accessing a particular table.  Write the
   2659 ** best query plan and its cost into the WhereCost object supplied as the
   2660 ** last parameter.
   2661 **
   2662 ** The lowest cost plan wins.  The cost is an estimate of the amount of
   2663 ** CPU and disk I/O needed to process the requested result.
   2664 ** Factors that influence cost include:
   2665 **
   2666 **    *  The estimated number of rows that will be retrieved.  (The
   2667 **       fewer the better.)
   2668 **
   2669 **    *  Whether or not sorting must occur.
   2670 **
   2671 **    *  Whether or not there must be separate lookups in the
   2672 **       index and in the main table.
   2673 **
   2674 ** If there was an INDEXED BY clause (pSrc->pIndex) attached to the table in
   2675 ** the SQL statement, then this function only considers plans using the
   2676 ** named index. If no such plan is found, then the returned cost is
   2677 ** SQLITE_BIG_DBL. If a plan is found that uses the named index,
   2678 ** then the cost is calculated in the usual way.
   2679 **
   2680 ** If a NOT INDEXED clause (pSrc->notIndexed!=0) was attached to the table
   2681 ** in the SELECT statement, then no indexes are considered. However, the
   2682 ** selected plan may still take advantage of the built-in rowid primary key
   2683 ** index.
   2684 */
   2685 static void bestBtreeIndex(
   2686   Parse *pParse,              /* The parsing context */
   2687   WhereClause *pWC,           /* The WHERE clause */
   2688   struct SrcList_item *pSrc,  /* The FROM clause term to search */
   2689   Bitmask notReady,           /* Mask of cursors not available for indexing */
   2690   Bitmask notValid,           /* Cursors not available for any purpose */
   2691   ExprList *pOrderBy,         /* The ORDER BY clause */
   2692   WhereCost *pCost            /* Lowest cost query plan */
   2693 ){
   2694   int iCur = pSrc->iCursor;   /* The cursor of the table to be accessed */
   2695   Index *pProbe;              /* An index we are evaluating */
   2696   Index *pIdx;                /* Copy of pProbe, or zero for IPK index */
   2697   int eqTermMask;             /* Current mask of valid equality operators */
   2698   int idxEqTermMask;          /* Index mask of valid equality operators */
   2699   Index sPk;                  /* A fake index object for the primary key */
   2700   unsigned int aiRowEstPk[2]; /* The aiRowEst[] value for the sPk index */
   2701   int aiColumnPk = -1;        /* The aColumn[] value for the sPk index */
   2702   int wsFlagMask;             /* Allowed flags in pCost->plan.wsFlag */
   2703 
   2704   /* Initialize the cost to a worst-case value */
   2705   memset(pCost, 0, sizeof(*pCost));
   2706   pCost->rCost = SQLITE_BIG_DBL;
   2707 
   2708   /* If the pSrc table is the right table of a LEFT JOIN then we may not
   2709   ** use an index to satisfy IS NULL constraints on that table.  This is
   2710   ** because columns might end up being NULL if the table does not match -
   2711   ** a circumstance which the index cannot help us discover.  Ticket #2177.
   2712   */
   2713   if( pSrc->jointype & JT_LEFT ){
   2714     idxEqTermMask = WO_EQ|WO_IN;
   2715   }else{
   2716     idxEqTermMask = WO_EQ|WO_IN|WO_ISNULL;
   2717   }
   2718 
   2719   if( pSrc->pIndex ){
   2720     /* An INDEXED BY clause specifies a particular index to use */
   2721     pIdx = pProbe = pSrc->pIndex;
   2722     wsFlagMask = ~(WHERE_ROWID_EQ|WHERE_ROWID_RANGE);
   2723     eqTermMask = idxEqTermMask;
   2724   }else{
   2725     /* There is no INDEXED BY clause.  Create a fake Index object in local
   2726     ** variable sPk to represent the rowid primary key index.  Make this
   2727     ** fake index the first in a chain of Index objects with all of the real
   2728     ** indices to follow */
   2729     Index *pFirst;                  /* First of real indices on the table */
   2730     memset(&sPk, 0, sizeof(Index));
   2731     sPk.nColumn = 1;
   2732     sPk.aiColumn = &aiColumnPk;
   2733     sPk.aiRowEst = aiRowEstPk;
   2734     sPk.onError = OE_Replace;
   2735     sPk.pTable = pSrc->pTab;
   2736     aiRowEstPk[0] = pSrc->pTab->nRowEst;
   2737     aiRowEstPk[1] = 1;
   2738     pFirst = pSrc->pTab->pIndex;
   2739     if( pSrc->notIndexed==0 ){
   2740       /* The real indices of the table are only considered if the
   2741       ** NOT INDEXED qualifier is omitted from the FROM clause */
   2742       sPk.pNext = pFirst;
   2743     }
   2744     pProbe = &sPk;
   2745     wsFlagMask = ~(
   2746         WHERE_COLUMN_IN|WHERE_COLUMN_EQ|WHERE_COLUMN_NULL|WHERE_COLUMN_RANGE
   2747     );
   2748     eqTermMask = WO_EQ|WO_IN;
   2749     pIdx = 0;
   2750   }
   2751 
   2752   /* Loop over all indices looking for the best one to use
   2753   */
   2754   for(; pProbe; pIdx=pProbe=pProbe->pNext){
   2755     const unsigned int * const aiRowEst = pProbe->aiRowEst;
   2756     double cost;                /* Cost of using pProbe */
   2757     double nRow;                /* Estimated number of rows in result set */
   2758     double log10N;              /* base-10 logarithm of nRow (inexact) */
   2759     int rev;                    /* True to scan in reverse order */
   2760     int wsFlags = 0;
   2761     Bitmask used = 0;
   2762 
   2763     /* The following variables are populated based on the properties of
   2764     ** index being evaluated. They are then used to determine the expected
   2765     ** cost and number of rows returned.
   2766     **
   2767     **  nEq:
   2768     **    Number of equality terms that can be implemented using the index.
   2769     **    In other words, the number of initial fields in the index that
   2770     **    are used in == or IN or NOT NULL constraints of the WHERE clause.
   2771     **
   2772     **  nInMul:
   2773     **    The "in-multiplier". This is an estimate of how many seek operations
   2774     **    SQLite must perform on the index in question. For example, if the
   2775     **    WHERE clause is:
   2776     **
   2777     **      WHERE a IN (1, 2, 3) AND b IN (4, 5, 6)
   2778     **
   2779     **    SQLite must perform 9 lookups on an index on (a, b), so nInMul is
   2780     **    set to 9. Given the same schema and either of the following WHERE
   2781     **    clauses:
   2782     **
   2783     **      WHERE a =  1
   2784     **      WHERE a >= 2
   2785     **
   2786     **    nInMul is set to 1.
   2787     **
   2788     **    If there exists a WHERE term of the form "x IN (SELECT ...)", then
   2789     **    the sub-select is assumed to return 25 rows for the purposes of
   2790     **    determining nInMul.
   2791     **
   2792     **  bInEst:
   2793     **    Set to true if there was at least one "x IN (SELECT ...)" term used
   2794     **    in determining the value of nInMul.  Note that the RHS of the
   2795     **    IN operator must be a SELECT, not a value list, for this variable
   2796     **    to be true.
   2797     **
   2798     **  estBound:
   2799     **    An estimate on the amount of the table that must be searched.  A
   2800     **    value of 100 means the entire table is searched.  Range constraints
   2801     **    might reduce this to a value less than 100 to indicate that only
   2802     **    a fraction of the table needs searching.  In the absence of
   2803     **    sqlite_stat2 ANALYZE data, a single inequality reduces the search
   2804     **    space to 1/4rd its original size.  So an x>? constraint reduces
   2805     **    estBound to 25.  Two constraints (x>? AND x<?) reduce estBound to 6.
   2806     **
   2807     **  bSort:
   2808     **    Boolean. True if there is an ORDER BY clause that will require an
   2809     **    external sort (i.e. scanning the index being evaluated will not
   2810     **    correctly order records).
   2811     **
   2812     **  bLookup:
   2813     **    Boolean. True if a table lookup is required for each index entry
   2814     **    visited.  In other words, true if this is not a covering index.
   2815     **    This is always false for the rowid primary key index of a table.
   2816     **    For other indexes, it is true unless all the columns of the table
   2817     **    used by the SELECT statement are present in the index (such an
   2818     **    index is sometimes described as a covering index).
   2819     **    For example, given the index on (a, b), the second of the following
   2820     **    two queries requires table b-tree lookups in order to find the value
   2821     **    of column c, but the first does not because columns a and b are
   2822     **    both available in the index.
   2823     **
   2824     **             SELECT a, b    FROM tbl WHERE a = 1;
   2825     **             SELECT a, b, c FROM tbl WHERE a = 1;
   2826     */
   2827     int nEq;                      /* Number of == or IN terms matching index */
   2828     int bInEst = 0;               /* True if "x IN (SELECT...)" seen */
   2829     int nInMul = 1;               /* Number of distinct equalities to lookup */
   2830     int estBound = 100;           /* Estimated reduction in search space */
   2831     int nBound = 0;               /* Number of range constraints seen */
   2832     int bSort = 0;                /* True if external sort required */
   2833     int bLookup = 0;              /* True if not a covering index */
   2834     WhereTerm *pTerm;             /* A single term of the WHERE clause */
   2835 #ifdef SQLITE_ENABLE_STAT2
   2836     WhereTerm *pFirstTerm = 0;    /* First term matching the index */
   2837 #endif
   2838 
   2839     /* Determine the values of nEq and nInMul */
   2840     for(nEq=0; nEq<pProbe->nColumn; nEq++){
   2841       int j = pProbe->aiColumn[nEq];
   2842       pTerm = findTerm(pWC, iCur, j, notReady, eqTermMask, pIdx);
   2843       if( pTerm==0 ) break;
   2844       wsFlags |= (WHERE_COLUMN_EQ|WHERE_ROWID_EQ);
   2845       if( pTerm->eOperator & WO_IN ){
   2846         Expr *pExpr = pTerm->pExpr;
   2847         wsFlags |= WHERE_COLUMN_IN;
   2848         if( ExprHasProperty(pExpr, EP_xIsSelect) ){
   2849           /* "x IN (SELECT ...)":  Assume the SELECT returns 25 rows */
   2850           nInMul *= 25;
   2851           bInEst = 1;
   2852         }else if( ALWAYS(pExpr->x.pList && pExpr->x.pList->nExpr) ){
   2853           /* "x IN (value, value, ...)" */
   2854           nInMul *= pExpr->x.pList->nExpr;
   2855         }
   2856       }else if( pTerm->eOperator & WO_ISNULL ){
   2857         wsFlags |= WHERE_COLUMN_NULL;
   2858       }
   2859 #ifdef SQLITE_ENABLE_STAT2
   2860       if( nEq==0 && pProbe->aSample ) pFirstTerm = pTerm;
   2861 #endif
   2862       used |= pTerm->prereqRight;
   2863     }
   2864 
   2865     /* Determine the value of estBound. */
   2866     if( nEq<pProbe->nColumn && pProbe->bUnordered==0 ){
   2867       int j = pProbe->aiColumn[nEq];
   2868       if( findTerm(pWC, iCur, j, notReady, WO_LT|WO_LE|WO_GT|WO_GE, pIdx) ){
   2869         WhereTerm *pTop = findTerm(pWC, iCur, j, notReady, WO_LT|WO_LE, pIdx);
   2870         WhereTerm *pBtm = findTerm(pWC, iCur, j, notReady, WO_GT|WO_GE, pIdx);
   2871         whereRangeScanEst(pParse, pProbe, nEq, pBtm, pTop, &estBound);
   2872         if( pTop ){
   2873           nBound = 1;
   2874           wsFlags |= WHERE_TOP_LIMIT;
   2875           used |= pTop->prereqRight;
   2876         }
   2877         if( pBtm ){
   2878           nBound++;
   2879           wsFlags |= WHERE_BTM_LIMIT;
   2880           used |= pBtm->prereqRight;
   2881         }
   2882         wsFlags |= (WHERE_COLUMN_RANGE|WHERE_ROWID_RANGE);
   2883       }
   2884     }else if( pProbe->onError!=OE_None ){
   2885       testcase( wsFlags & WHERE_COLUMN_IN );
   2886       testcase( wsFlags & WHERE_COLUMN_NULL );
   2887       if( (wsFlags & (WHERE_COLUMN_IN|WHERE_COLUMN_NULL))==0 ){
   2888         wsFlags |= WHERE_UNIQUE;
   2889       }
   2890     }
   2891 
   2892     /* If there is an ORDER BY clause and the index being considered will
   2893     ** naturally scan rows in the required order, set the appropriate flags
   2894     ** in wsFlags. Otherwise, if there is an ORDER BY clause but the index
   2895     ** will scan rows in a different order, set the bSort variable.  */
   2896     if( pOrderBy ){
   2897       if( (wsFlags & WHERE_COLUMN_IN)==0
   2898         && pProbe->bUnordered==0
   2899         && isSortingIndex(pParse, pWC->pMaskSet, pProbe, iCur, pOrderBy,
   2900                           nEq, wsFlags, &rev)
   2901       ){
   2902         wsFlags |= WHERE_ROWID_RANGE|WHERE_COLUMN_RANGE|WHERE_ORDERBY;
   2903         wsFlags |= (rev ? WHERE_REVERSE : 0);
   2904       }else{
   2905         bSort = 1;
   2906       }
   2907     }
   2908 
   2909     /* If currently calculating the cost of using an index (not the IPK
   2910     ** index), determine if all required column data may be obtained without
   2911     ** using the main table (i.e. if the index is a covering
   2912     ** index for this query). If it is, set the WHERE_IDX_ONLY flag in
   2913     ** wsFlags. Otherwise, set the bLookup variable to true.  */
   2914     if( pIdx && wsFlags ){
   2915       Bitmask m = pSrc->colUsed;
   2916       int j;
   2917       for(j=0; j<pIdx->nColumn; j++){
   2918         int x = pIdx->aiColumn[j];
   2919         if( x<BMS-1 ){
   2920           m &= ~(((Bitmask)1)<<x);
   2921         }
   2922       }
   2923       if( m==0 ){
   2924         wsFlags |= WHERE_IDX_ONLY;
   2925       }else{
   2926         bLookup = 1;
   2927       }
   2928     }
   2929 
   2930     /*
   2931     ** Estimate the number of rows of output.  For an "x IN (SELECT...)"
   2932     ** constraint, do not let the estimate exceed half the rows in the table.
   2933     */
   2934     nRow = (double)(aiRowEst[nEq] * nInMul);
   2935     if( bInEst && nRow*2>aiRowEst[0] ){
   2936       nRow = aiRowEst[0]/2;
   2937       nInMul = (int)(nRow / aiRowEst[nEq]);
   2938     }
   2939 
   2940 #ifdef SQLITE_ENABLE_STAT2
   2941     /* If the constraint is of the form x=VALUE and histogram
   2942     ** data is available for column x, then it might be possible
   2943     ** to get a better estimate on the number of rows based on
   2944     ** VALUE and how common that value is according to the histogram.
   2945     */
   2946     if( nRow>(double)1 && nEq==1 && pFirstTerm!=0 ){
   2947       if( pFirstTerm->eOperator & (WO_EQ|WO_ISNULL) ){
   2948         testcase( pFirstTerm->eOperator==WO_EQ );
   2949         testcase( pFirstTerm->eOperator==WO_ISNULL );
   2950         whereEqualScanEst(pParse, pProbe, pFirstTerm->pExpr->pRight, &nRow);
   2951       }else if( pFirstTerm->eOperator==WO_IN && bInEst==0 ){
   2952         whereInScanEst(pParse, pProbe, pFirstTerm->pExpr->x.pList, &nRow);
   2953       }
   2954     }
   2955 #endif /* SQLITE_ENABLE_STAT2 */
   2956 
   2957     /* Adjust the number of output rows and downward to reflect rows
   2958     ** that are excluded by range constraints.
   2959     */
   2960     nRow = (nRow * (double)estBound) / (double)100;
   2961     if( nRow<1 ) nRow = 1;
   2962 
   2963     /* Experiments run on real SQLite databases show that the time needed
   2964     ** to do a binary search to locate a row in a table or index is roughly
   2965     ** log10(N) times the time to move from one row to the next row within
   2966     ** a table or index.  The actual times can vary, with the size of
   2967     ** records being an important factor.  Both moves and searches are
   2968     ** slower with larger records, presumably because fewer records fit
   2969     ** on one page and hence more pages have to be fetched.
   2970     **
   2971     ** The ANALYZE command and the sqlite_stat1 and sqlite_stat2 tables do
   2972     ** not give us data on the relative sizes of table and index records.
   2973     ** So this computation assumes table records are about twice as big
   2974     ** as index records
   2975     */
   2976     if( (wsFlags & WHERE_NOT_FULLSCAN)==0 ){
   2977       /* The cost of a full table scan is a number of move operations equal
   2978       ** to the number of rows in the table.
   2979       **
   2980       ** We add an additional 4x penalty to full table scans.  This causes
   2981       ** the cost function to err on the side of choosing an index over
   2982       ** choosing a full scan.  This 4x full-scan penalty is an arguable
   2983       ** decision and one which we expect to revisit in the future.  But
   2984       ** it seems to be working well enough at the moment.
   2985       */
   2986       cost = aiRowEst[0]*4;
   2987     }else{
   2988       log10N = estLog(aiRowEst[0]);
   2989       cost = nRow;
   2990       if( pIdx ){
   2991         if( bLookup ){
   2992           /* For an index lookup followed by a table lookup:
   2993           **    nInMul index searches to find the start of each index range
   2994           **  + nRow steps through the index
   2995           **  + nRow table searches to lookup the table entry using the rowid
   2996           */
   2997           cost += (nInMul + nRow)*log10N;
   2998         }else{
   2999           /* For a covering index:
   3000           **     nInMul index searches to find the initial entry
   3001           **   + nRow steps through the index
   3002           */
   3003           cost += nInMul*log10N;
   3004         }
   3005       }else{
   3006         /* For a rowid primary key lookup:
   3007         **    nInMult table searches to find the initial entry for each range
   3008         **  + nRow steps through the table
   3009         */
   3010         cost += nInMul*log10N;
   3011       }
   3012     }
   3013 
   3014     /* Add in the estimated cost of sorting the result.  Actual experimental
   3015     ** measurements of sorting performance in SQLite show that sorting time
   3016     ** adds C*N*log10(N) to the cost, where N is the number of rows to be
   3017     ** sorted and C is a factor between 1.95 and 4.3.  We will split the
   3018     ** difference and select C of 3.0.
   3019     */
   3020     if( bSort ){
   3021       cost += nRow*estLog(nRow)*3;
   3022     }
   3023 
   3024     /**** Cost of using this index has now been computed ****/
   3025 
   3026     /* If there are additional constraints on this table that cannot
   3027     ** be used with the current index, but which might lower the number
   3028     ** of output rows, adjust the nRow value accordingly.  This only
   3029     ** matters if the current index is the least costly, so do not bother
   3030     ** with this step if we already know this index will not be chosen.
   3031     ** Also, never reduce the output row count below 2 using this step.
   3032     **
   3033     ** It is critical that the notValid mask be used here instead of
   3034     ** the notReady mask.  When computing an "optimal" index, the notReady
   3035     ** mask will only have one bit set - the bit for the current table.
   3036     ** The notValid mask, on the other hand, always has all bits set for
   3037     ** tables that are not in outer loops.  If notReady is used here instead
   3038     ** of notValid, then a optimal index that depends on inner joins loops
   3039     ** might be selected even when there exists an optimal index that has
   3040     ** no such dependency.
   3041     */
   3042     if( nRow>2 && cost<=pCost->rCost ){
   3043       int k;                       /* Loop counter */
   3044       int nSkipEq = nEq;           /* Number of == constraints to skip */
   3045       int nSkipRange = nBound;     /* Number of < constraints to skip */
   3046       Bitmask thisTab;             /* Bitmap for pSrc */
   3047 
   3048       thisTab = getMask(pWC->pMaskSet, iCur);
   3049       for(pTerm=pWC->a, k=pWC->nTerm; nRow>2 && k; k--, pTerm++){
   3050         if( pTerm->wtFlags & TERM_VIRTUAL ) continue;
   3051         if( (pTerm->prereqAll & notValid)!=thisTab ) continue;
   3052         if( pTerm->eOperator & (WO_EQ|WO_IN|WO_ISNULL) ){
   3053           if( nSkipEq ){
   3054             /* Ignore the first nEq equality matches since the index
   3055             ** has already accounted for these */
   3056             nSkipEq--;
   3057           }else{
   3058             /* Assume each additional equality match reduces the result
   3059             ** set size by a factor of 10 */
   3060             nRow /= 10;
   3061           }
   3062         }else if( pTerm->eOperator & (WO_LT|WO_LE|WO_GT|WO_GE) ){
   3063           if( nSkipRange ){
   3064             /* Ignore the first nSkipRange range constraints since the index
   3065             ** has already accounted for these */
   3066             nSkipRange--;
   3067           }else{
   3068             /* Assume each additional range constraint reduces the result
   3069             ** set size by a factor of 3.  Indexed range constraints reduce
   3070             ** the search space by a larger factor: 4.  We make indexed range
   3071             ** more selective intentionally because of the subjective
   3072             ** observation that indexed range constraints really are more
   3073             ** selective in practice, on average. */
   3074             nRow /= 3;
   3075           }
   3076         }else if( pTerm->eOperator!=WO_NOOP ){
   3077           /* Any other expression lowers the output row count by half */
   3078           nRow /= 2;
   3079         }
   3080       }
   3081       if( nRow<2 ) nRow = 2;
   3082     }
   3083 
   3084 
   3085     WHERETRACE((
   3086       "%s(%s): nEq=%d nInMul=%d estBound=%d bSort=%d bLookup=%d wsFlags=0x%x\n"
   3087       "         notReady=0x%llx log10N=%.1f nRow=%.1f cost=%.1f used=0x%llx\n",
   3088       pSrc->pTab->zName, (pIdx ? pIdx->zName : "ipk"),
   3089       nEq, nInMul, estBound, bSort, bLookup, wsFlags,
   3090       notReady, log10N, nRow, cost, used
   3091     ));
   3092 
   3093     /* If this index is the best we have seen so far, then record this
   3094     ** index and its cost in the pCost structure.
   3095     */
   3096     if( (!pIdx || wsFlags)
   3097      && (cost<pCost->rCost || (cost<=pCost->rCost && nRow<pCost->plan.nRow))
   3098     ){
   3099       pCost->rCost = cost;
   3100       pCost->used = used;
   3101       pCost->plan.nRow = nRow;
   3102       pCost->plan.wsFlags = (wsFlags&wsFlagMask);
   3103       pCost->plan.nEq = nEq;
   3104       pCost->plan.u.pIdx = pIdx;
   3105     }
   3106 
   3107     /* If there was an INDEXED BY clause, then only that one index is
   3108     ** considered. */
   3109     if( pSrc->pIndex ) break;
   3110 
   3111     /* Reset masks for the next index in the loop */
   3112     wsFlagMask = ~(WHERE_ROWID_EQ|WHERE_ROWID_RANGE);
   3113     eqTermMask = idxEqTermMask;
   3114   }
   3115 
   3116   /* If there is no ORDER BY clause and the SQLITE_ReverseOrder flag
   3117   ** is set, then reverse the order that the index will be scanned
   3118   ** in. This is used for application testing, to help find cases
   3119   ** where application behaviour depends on the (undefined) order that
   3120   ** SQLite outputs rows in in the absence of an ORDER BY clause.  */
   3121   if( !pOrderBy && pParse->db->flags & SQLITE_ReverseOrder ){
   3122     pCost->plan.wsFlags |= WHERE_REVERSE;
   3123   }
   3124 
   3125   assert( pOrderBy || (pCost->plan.wsFlags&WHERE_ORDERBY)==0 );
   3126   assert( pCost->plan.u.pIdx==0 || (pCost->plan.wsFlags&WHERE_ROWID_EQ)==0 );
   3127   assert( pSrc->pIndex==0
   3128        || pCost->plan.u.pIdx==0
   3129        || pCost->plan.u.pIdx==pSrc->pIndex
   3130   );
   3131 
   3132   WHERETRACE(("best index is: %s\n",
   3133     ((pCost->plan.wsFlags & WHERE_NOT_FULLSCAN)==0 ? "none" :
   3134          pCost->plan.u.pIdx ? pCost->plan.u.pIdx->zName : "ipk")
   3135   ));
   3136 
   3137   bestOrClauseIndex(pParse, pWC, pSrc, notReady, notValid, pOrderBy, pCost);
   3138   bestAutomaticIndex(pParse, pWC, pSrc, notReady, pCost);
   3139   pCost->plan.wsFlags |= eqTermMask;
   3140 }
   3141 
   3142 /*
   3143 ** Find the query plan for accessing table pSrc->pTab. Write the
   3144 ** best query plan and its cost into the WhereCost object supplied
   3145 ** as the last parameter. This function may calculate the cost of
   3146 ** both real and virtual table scans.
   3147 */
   3148 static void bestIndex(
   3149   Parse *pParse,              /* The parsing context */
   3150   WhereClause *pWC,           /* The WHERE clause */
   3151   struct SrcList_item *pSrc,  /* The FROM clause term to search */
   3152   Bitmask notReady,           /* Mask of cursors not available for indexing */
   3153   Bitmask notValid,           /* Cursors not available for any purpose */
   3154   ExprList *pOrderBy,         /* The ORDER BY clause */
   3155   WhereCost *pCost            /* Lowest cost query plan */
   3156 ){
   3157 #ifndef SQLITE_OMIT_VIRTUALTABLE
   3158   if( IsVirtual(pSrc->pTab) ){
   3159     sqlite3_index_info *p = 0;
   3160     bestVirtualIndex(pParse, pWC, pSrc, notReady, notValid, pOrderBy, pCost,&p);
   3161     if( p->needToFreeIdxStr ){
   3162       sqlite3_free(p->idxStr);
   3163     }
   3164     sqlite3DbFree(pParse->db, p);
   3165   }else
   3166 #endif
   3167   {
   3168     bestBtreeIndex(pParse, pWC, pSrc, notReady, notValid, pOrderBy, pCost);
   3169   }
   3170 }
   3171 
   3172 /*
   3173 ** Disable a term in the WHERE clause.  Except, do not disable the term
   3174 ** if it controls a LEFT OUTER JOIN and it did not originate in the ON
   3175 ** or USING clause of that join.
   3176 **
   3177 ** Consider the term t2.z='ok' in the following queries:
   3178 **
   3179 **   (1)  SELECT * FROM t1 LEFT JOIN t2 ON t1.a=t2.x WHERE t2.z='ok'
   3180 **   (2)  SELECT * FROM t1 LEFT JOIN t2 ON t1.a=t2.x AND t2.z='ok'
   3181 **   (3)  SELECT * FROM t1, t2 WHERE t1.a=t2.x AND t2.z='ok'
   3182 **
   3183 ** The t2.z='ok' is disabled in the in (2) because it originates
   3184 ** in the ON clause.  The term is disabled in (3) because it is not part
   3185 ** of a LEFT OUTER JOIN.  In (1), the term is not disabled.
   3186 **
   3187 ** IMPLEMENTATION-OF: R-24597-58655 No tests are done for terms that are
   3188 ** completely satisfied by indices.
   3189 **
   3190 ** Disabling a term causes that term to not be tested in the inner loop
   3191 ** of the join.  Disabling is an optimization.  When terms are satisfied
   3192 ** by indices, we disable them to prevent redundant tests in the inner
   3193 ** loop.  We would get the correct results if nothing were ever disabled,
   3194 ** but joins might run a little slower.  The trick is to disable as much
   3195 ** as we can without disabling too much.  If we disabled in (1), we'd get
   3196 ** the wrong answer.  See ticket #813.
   3197 */
   3198 static void disableTerm(WhereLevel *pLevel, WhereTerm *pTerm){
   3199   if( pTerm
   3200       && (pTerm->wtFlags & TERM_CODED)==0
   3201       && (pLevel->iLeftJoin==0 || ExprHasProperty(pTerm->pExpr, EP_FromJoin))
   3202   ){
   3203     pTerm->wtFlags |= TERM_CODED;
   3204     if( pTerm->iParent>=0 ){
   3205       WhereTerm *pOther = &pTerm->pWC->a[pTerm->iParent];
   3206       if( (--pOther->nChild)==0 ){
   3207         disableTerm(pLevel, pOther);
   3208       }
   3209     }
   3210   }
   3211 }
   3212 
   3213 /*
   3214 ** Code an OP_Affinity opcode to apply the column affinity string zAff
   3215 ** to the n registers starting at base.
   3216 **
   3217 ** As an optimization, SQLITE_AFF_NONE entries (which are no-ops) at the
   3218 ** beginning and end of zAff are ignored.  If all entries in zAff are
   3219 ** SQLITE_AFF_NONE, then no code gets generated.
   3220 **
   3221 ** This routine makes its own copy of zAff so that the caller is free
   3222 ** to modify zAff after this routine returns.
   3223 */
   3224 static void codeApplyAffinity(Parse *pParse, int base, int n, char *zAff){
   3225   Vdbe *v = pParse->pVdbe;
   3226   if( zAff==0 ){
   3227     assert( pParse->db->mallocFailed );
   3228     return;
   3229   }
   3230   assert( v!=0 );
   3231 
   3232   /* Adjust base and n to skip over SQLITE_AFF_NONE entries at the beginning
   3233   ** and end of the affinity string.
   3234   */
   3235   while( n>0 && zAff[0]==SQLITE_AFF_NONE ){
   3236     n--;
   3237     base++;
   3238     zAff++;
   3239   }
   3240   while( n>1 && zAff[n-1]==SQLITE_AFF_NONE ){
   3241     n--;
   3242   }
   3243 
   3244   /* Code the OP_Affinity opcode if there is anything left to do. */
   3245   if( n>0 ){
   3246     sqlite3VdbeAddOp2(v, OP_Affinity, base, n);
   3247     sqlite3VdbeChangeP4(v, -1, zAff, n);
   3248     sqlite3ExprCacheAffinityChange(pParse, base, n);
   3249   }
   3250 }
   3251 
   3252 
   3253 /*
   3254 ** Generate code for a single equality term of the WHERE clause.  An equality
   3255 ** term can be either X=expr or X IN (...).   pTerm is the term to be
   3256 ** coded.
   3257 **
   3258 ** The current value for the constraint is left in register iReg.
   3259 **
   3260 ** For a constraint of the form X=expr, the expression is evaluated and its
   3261 ** result is left on the stack.  For constraints of the form X IN (...)
   3262 ** this routine sets up a loop that will iterate over all values of X.
   3263 */
   3264 static int codeEqualityTerm(
   3265   Parse *pParse,      /* The parsing context */
   3266   WhereTerm *pTerm,   /* The term of the WHERE clause to be coded */
   3267   WhereLevel *pLevel, /* When level of the FROM clause we are working on */
   3268   int iTarget         /* Attempt to leave results in this register */
   3269 ){
   3270   Expr *pX = pTerm->pExpr;
   3271   Vdbe *v = pParse->pVdbe;
   3272   int iReg;                  /* Register holding results */
   3273 
   3274   assert( iTarget>0 );
   3275   if( pX->op==TK_EQ ){
   3276     iReg = sqlite3ExprCodeTarget(pParse, pX->pRight, iTarget);
   3277   }else if( pX->op==TK_ISNULL ){
   3278     iReg = iTarget;
   3279     sqlite3VdbeAddOp2(v, OP_Null, 0, iReg);
   3280 #ifndef SQLITE_OMIT_SUBQUERY
   3281   }else{
   3282     int eType;
   3283     int iTab;
   3284     struct InLoop *pIn;
   3285 
   3286     assert( pX->op==TK_IN );
   3287     iReg = iTarget;
   3288     eType = sqlite3FindInIndex(pParse, pX, 0);
   3289     iTab = pX->iTable;
   3290     sqlite3VdbeAddOp2(v, OP_Rewind, iTab, 0);
   3291     assert( pLevel->plan.wsFlags & WHERE_IN_ABLE );
   3292     if( pLevel->u.in.nIn==0 ){
   3293       pLevel->addrNxt = sqlite3VdbeMakeLabel(v);
   3294     }
   3295     pLevel->u.in.nIn++;
   3296     pLevel->u.in.aInLoop =
   3297        sqlite3DbReallocOrFree(pParse->db, pLevel->u.in.aInLoop,
   3298                               sizeof(pLevel->u.in.aInLoop[0])*pLevel->u.in.nIn);
   3299     pIn = pLevel->u.in.aInLoop;
   3300     if( pIn ){
   3301       pIn += pLevel->u.in.nIn - 1;
   3302       pIn->iCur = iTab;
   3303       if( eType==IN_INDEX_ROWID ){
   3304         pIn->addrInTop = sqlite3VdbeAddOp2(v, OP_Rowid, iTab, iReg);
   3305       }else{
   3306         pIn->addrInTop = sqlite3VdbeAddOp3(v, OP_Column, iTab, 0, iReg);
   3307       }
   3308       sqlite3VdbeAddOp1(v, OP_IsNull, iReg);
   3309     }else{
   3310       pLevel->u.in.nIn = 0;
   3311     }
   3312 #endif
   3313   }
   3314   disableTerm(pLevel, pTerm);
   3315   return iReg;
   3316 }
   3317 
   3318 /*
   3319 ** Generate code that will evaluate all == and IN constraints for an
   3320 ** index.
   3321 **
   3322 ** For example, consider table t1(a,b,c,d,e,f) with index i1(a,b,c).
   3323 ** Suppose the WHERE clause is this:  a==5 AND b IN (1,2,3) AND c>5 AND c<10
   3324 ** The index has as many as three equality constraints, but in this
   3325 ** example, the third "c" value is an inequality.  So only two
   3326 ** constraints are coded.  This routine will generate code to evaluate
   3327 ** a==5 and b IN (1,2,3).  The current values for a and b will be stored
   3328 ** in consecutive registers and the index of the first register is returned.
   3329 **
   3330 ** In the example above nEq==2.  But this subroutine works for any value
   3331 ** of nEq including 0.  If nEq==0, this routine is nearly a no-op.
   3332 ** The only thing it does is allocate the pLevel->iMem memory cell and
   3333 ** compute the affinity string.
   3334 **
   3335 ** This routine always allocates at least one memory cell and returns
   3336 ** the index of that memory cell. The code that
   3337 ** calls this routine will use that memory cell to store the termination
   3338 ** key value of the loop.  If one or more IN operators appear, then
   3339 ** this routine allocates an additional nEq memory cells for internal
   3340 ** use.
   3341 **
   3342 ** Before returning, *pzAff is set to point to a buffer containing a
   3343 ** copy of the column affinity string of the index allocated using
   3344 ** sqlite3DbMalloc(). Except, entries in the copy of the string associated
   3345 ** with equality constraints that use NONE affinity are set to
   3346 ** SQLITE_AFF_NONE. This is to deal with SQL such as the following:
   3347 **
   3348 **   CREATE TABLE t1(a TEXT PRIMARY KEY, b);
   3349 **   SELECT ... FROM t1 AS t2, t1 WHERE t1.a = t2.b;
   3350 **
   3351 ** In the example above, the index on t1(a) has TEXT affinity. But since
   3352 ** the right hand side of the equality constraint (t2.b) has NONE affinity,
   3353 ** no conversion should be attempted before using a t2.b value as part of
   3354 ** a key to search the index. Hence the first byte in the returned affinity
   3355 ** string in this example would be set to SQLITE_AFF_NONE.
   3356 */
   3357 static int codeAllEqualityTerms(
   3358   Parse *pParse,        /* Parsing context */
   3359   WhereLevel *pLevel,   /* Which nested loop of the FROM we are coding */
   3360   WhereClause *pWC,     /* The WHERE clause */
   3361   Bitmask notReady,     /* Which parts of FROM have not yet been coded */
   3362   int nExtraReg,        /* Number of extra registers to allocate */
   3363   char **pzAff          /* OUT: Set to point to affinity string */
   3364 ){
   3365   int nEq = pLevel->plan.nEq;   /* The number of == or IN constraints to code */
   3366   Vdbe *v = pParse->pVdbe;      /* The vm under construction */
   3367   Index *pIdx;                  /* The index being used for this loop */
   3368   int iCur = pLevel->iTabCur;   /* The cursor of the table */
   3369   WhereTerm *pTerm;             /* A single constraint term */
   3370   int j;                        /* Loop counter */
   3371   int regBase;                  /* Base register */
   3372   int nReg;                     /* Number of registers to allocate */
   3373   char *zAff;                   /* Affinity string to return */
   3374 
   3375   /* This module is only called on query plans that use an index. */
   3376   assert( pLevel->plan.wsFlags & WHERE_INDEXED );
   3377   pIdx = pLevel->plan.u.pIdx;
   3378 
   3379   /* Figure out how many memory cells we will need then allocate them.
   3380   */
   3381   regBase = pParse->nMem + 1;
   3382   nReg = pLevel->plan.nEq + nExtraReg;
   3383   pParse->nMem += nReg;
   3384 
   3385   zAff = sqlite3DbStrDup(pParse->db, sqlite3IndexAffinityStr(v, pIdx));
   3386   if( !zAff ){
   3387     pParse->db->mallocFailed = 1;
   3388   }
   3389 
   3390   /* Evaluate the equality constraints
   3391   */
   3392   assert( pIdx->nColumn>=nEq );
   3393   for(j=0; j<nEq; j++){
   3394     int r1;
   3395     int k = pIdx->aiColumn[j];
   3396     pTerm = findTerm(pWC, iCur, k, notReady, pLevel->plan.wsFlags, pIdx);
   3397     if( NEVER(pTerm==0) ) break;
   3398     /* The following true for indices with redundant columns.
   3399     ** Ex: CREATE INDEX i1 ON t1(a,b,a); SELECT * FROM t1 WHERE a=0 AND b=0; */
   3400     testcase( (pTerm->wtFlags & TERM_CODED)!=0 );
   3401     testcase( pTerm->wtFlags & TERM_VIRTUAL ); /* EV: R-30575-11662 */
   3402     r1 = codeEqualityTerm(pParse, pTerm, pLevel, regBase+j);
   3403     if( r1!=regBase+j ){
   3404       if( nReg==1 ){
   3405         sqlite3ReleaseTempReg(pParse, regBase);
   3406         regBase = r1;
   3407       }else{
   3408         sqlite3VdbeAddOp2(v, OP_SCopy, r1, regBase+j);
   3409       }
   3410     }
   3411     testcase( pTerm->eOperator & WO_ISNULL );
   3412     testcase( pTerm->eOperator & WO_IN );
   3413     if( (pTerm->eOperator & (WO_ISNULL|WO_IN))==0 ){
   3414       Expr *pRight = pTerm->pExpr->pRight;
   3415       sqlite3ExprCodeIsNullJump(v, pRight, regBase+j, pLevel->addrBrk);
   3416       if( zAff ){
   3417         if( sqlite3CompareAffinity(pRight, zAff[j])==SQLITE_AFF_NONE ){
   3418           zAff[j] = SQLITE_AFF_NONE;
   3419         }
   3420         if( sqlite3ExprNeedsNoAffinityChange(pRight, zAff[j]) ){
   3421           zAff[j] = SQLITE_AFF_NONE;
   3422         }
   3423       }
   3424     }
   3425   }
   3426   *pzAff = zAff;
   3427   return regBase;
   3428 }
   3429 
   3430 #ifndef SQLITE_OMIT_EXPLAIN
   3431 /*
   3432 ** This routine is a helper for explainIndexRange() below
   3433 **
   3434 ** pStr holds the text of an expression that we are building up one term
   3435 ** at a time.  This routine adds a new term to the end of the expression.
   3436 ** Terms are separated by AND so add the "AND" text for second and subsequent
   3437 ** terms only.
   3438 */
   3439 static void explainAppendTerm(
   3440   StrAccum *pStr,             /* The text expression being built */
   3441   int iTerm,                  /* Index of this term.  First is zero */
   3442   const char *zColumn,        /* Name of the column */
   3443   const char *zOp             /* Name of the operator */
   3444 ){
   3445   if( iTerm ) sqlite3StrAccumAppend(pStr, " AND ", 5);
   3446   sqlite3StrAccumAppend(pStr, zColumn, -1);
   3447   sqlite3StrAccumAppend(pStr, zOp, 1);
   3448   sqlite3StrAccumAppend(pStr, "?", 1);
   3449 }
   3450 
   3451 /*
   3452 ** Argument pLevel describes a strategy for scanning table pTab. This
   3453 ** function returns a pointer to a string buffer containing a description
   3454 ** of the subset of table rows scanned by the strategy in the form of an
   3455 ** SQL expression. Or, if all rows are scanned, NULL is returned.
   3456 **
   3457 ** For example, if the query:
   3458 **
   3459 **   SELECT * FROM t1 WHERE a=1 AND b>2;
   3460 **
   3461 ** is run and there is an index on (a, b), then this function returns a
   3462 ** string similar to:
   3463 **
   3464 **   "a=? AND b>?"
   3465 **
   3466 ** The returned pointer points to memory obtained from sqlite3DbMalloc().
   3467 ** It is the responsibility of the caller to free the buffer when it is
   3468 ** no longer required.
   3469 */
   3470 static char *explainIndexRange(sqlite3 *db, WhereLevel *pLevel, Table *pTab){
   3471   WherePlan *pPlan = &pLevel->plan;
   3472   Index *pIndex = pPlan->u.pIdx;
   3473   int nEq = pPlan->nEq;
   3474   int i, j;
   3475   Column *aCol = pTab->aCol;
   3476   int *aiColumn = pIndex->aiColumn;
   3477   StrAccum txt;
   3478 
   3479   if( nEq==0 && (pPlan->wsFlags & (WHERE_BTM_LIMIT|WHERE_TOP_LIMIT))==0 ){
   3480     return 0;
   3481   }
   3482   sqlite3StrAccumInit(&txt, 0, 0, SQLITE_MAX_LENGTH);
   3483   txt.db = db;
   3484   sqlite3StrAccumAppend(&txt, " (", 2);
   3485   for(i=0; i<nEq; i++){
   3486     explainAppendTerm(&txt, i, aCol[aiColumn[i]].zName, "=");
   3487   }
   3488 
   3489   j = i;
   3490   if( pPlan->wsFlags&WHERE_BTM_LIMIT ){
   3491     explainAppendTerm(&txt, i++, aCol[aiColumn[j]].zName, ">");
   3492   }
   3493   if( pPlan->wsFlags&WHERE_TOP_LIMIT ){
   3494     explainAppendTerm(&txt, i, aCol[aiColumn[j]].zName, "<");
   3495   }
   3496   sqlite3StrAccumAppend(&txt, ")", 1);
   3497   return sqlite3StrAccumFinish(&txt);
   3498 }
   3499 
   3500 /*
   3501 ** This function is a no-op unless currently processing an EXPLAIN QUERY PLAN
   3502 ** command. If the query being compiled is an EXPLAIN QUERY PLAN, a single
   3503 ** record is added to the output to describe the table scan strategy in
   3504 ** pLevel.
   3505 */
   3506 static void explainOneScan(
   3507   Parse *pParse,                  /* Parse context */
   3508   SrcList *pTabList,              /* Table list this loop refers to */
   3509   WhereLevel *pLevel,             /* Scan to write OP_Explain opcode for */
   3510   int iLevel,                     /* Value for "level" column of output */
   3511   int iFrom,                      /* Value for "from" column of output */
   3512   u16 wctrlFlags                  /* Flags passed to sqlite3WhereBegin() */
   3513 ){
   3514   if( pParse->explain==2 ){
   3515     u32 flags = pLevel->plan.wsFlags;
   3516     struct SrcList_item *pItem = &pTabList->a[pLevel->iFrom];
   3517     Vdbe *v = pParse->pVdbe;      /* VM being constructed */
   3518     sqlite3 *db = pParse->db;     /* Database handle */
   3519     char *zMsg;                   /* Text to add to EQP output */
   3520     sqlite3_int64 nRow;           /* Expected number of rows visited by scan */
   3521     int iId = pParse->iSelectId;  /* Select id (left-most output column) */
   3522     int isSearch;                 /* True for a SEARCH. False for SCAN. */
   3523 
   3524     if( (flags&WHERE_MULTI_OR) || (wctrlFlags&WHERE_ONETABLE_ONLY) ) return;
   3525 
   3526     isSearch = (pLevel->plan.nEq>0)
   3527              || (flags&(WHERE_BTM_LIMIT|WHERE_TOP_LIMIT))!=0
   3528              || (wctrlFlags&(WHERE_ORDERBY_MIN|WHERE_ORDERBY_MAX));
   3529 
   3530     zMsg = sqlite3MPrintf(db, "%s", isSearch?"SEARCH":"SCAN");
   3531     if( pItem->pSelect ){
   3532       zMsg = sqlite3MAppendf(db, zMsg, "%s SUBQUERY %d", zMsg,pItem->iSelectId);
   3533     }else{
   3534       zMsg = sqlite3MAppendf(db, zMsg, "%s TABLE %s", zMsg, pItem->zName);
   3535     }
   3536 
   3537     if( pItem->zAlias ){
   3538       zMsg = sqlite3MAppendf(db, zMsg, "%s AS %s", zMsg, pItem->zAlias);
   3539     }
   3540     if( (flags & WHERE_INDEXED)!=0 ){
   3541       char *zWhere = explainIndexRange(db, pLevel, pItem->pTab);
   3542       zMsg = sqlite3MAppendf(db, zMsg, "%s USING %s%sINDEX%s%s%s", zMsg,
   3543           ((flags & WHERE_TEMP_INDEX)?"AUTOMATIC ":""),
   3544           ((flags & WHERE_IDX_ONLY)?"COVERING ":""),
   3545           ((flags & WHERE_TEMP_INDEX)?"":" "),
   3546           ((flags & WHERE_TEMP_INDEX)?"": pLevel->plan.u.pIdx->zName),
   3547           zWhere
   3548       );
   3549       sqlite3DbFree(db, zWhere);
   3550     }else if( flags & (WHERE_ROWID_EQ|WHERE_ROWID_RANGE) ){
   3551       zMsg = sqlite3MAppendf(db, zMsg, "%s USING INTEGER PRIMARY KEY", zMsg);
   3552 
   3553       if( flags&WHERE_ROWID_EQ ){
   3554         zMsg = sqlite3MAppendf(db, zMsg, "%s (rowid=?)", zMsg);
   3555       }else if( (flags&WHERE_BOTH_LIMIT)==WHERE_BOTH_LIMIT ){
   3556         zMsg = sqlite3MAppendf(db, zMsg, "%s (rowid>? AND rowid<?)", zMsg);
   3557       }else if( flags&WHERE_BTM_LIMIT ){
   3558         zMsg = sqlite3MAppendf(db, zMsg, "%s (rowid>?)", zMsg);
   3559       }else if( flags&WHERE_TOP_LIMIT ){
   3560         zMsg = sqlite3MAppendf(db, zMsg, "%s (rowid<?)", zMsg);
   3561       }
   3562     }
   3563 #ifndef SQLITE_OMIT_VIRTUALTABLE
   3564     else if( (flags & WHERE_VIRTUALTABLE)!=0 ){
   3565       sqlite3_index_info *pVtabIdx = pLevel->plan.u.pVtabIdx;
   3566       zMsg = sqlite3MAppendf(db, zMsg, "%s VIRTUAL TABLE INDEX %d:%s", zMsg,
   3567                   pVtabIdx->idxNum, pVtabIdx->idxStr);
   3568     }
   3569 #endif
   3570     if( wctrlFlags&(WHERE_ORDERBY_MIN|WHERE_ORDERBY_MAX) ){
   3571       testcase( wctrlFlags & WHERE_ORDERBY_MIN );
   3572       nRow = 1;
   3573     }else{
   3574       nRow = (sqlite3_int64)pLevel->plan.nRow;
   3575     }
   3576     zMsg = sqlite3MAppendf(db, zMsg, "%s (~%lld rows)", zMsg, nRow);
   3577     sqlite3VdbeAddOp4(v, OP_Explain, iId, iLevel, iFrom, zMsg, P4_DYNAMIC);
   3578   }
   3579 }
   3580 #else
   3581 # define explainOneScan(u,v,w,x,y,z)
   3582 #endif /* SQLITE_OMIT_EXPLAIN */
   3583 
   3584 
   3585 /*
   3586 ** Generate code for the start of the iLevel-th loop in the WHERE clause
   3587 ** implementation described by pWInfo.
   3588 */
   3589 static Bitmask codeOneLoopStart(
   3590   WhereInfo *pWInfo,   /* Complete information about the WHERE clause */
   3591   int iLevel,          /* Which level of pWInfo->a[] should be coded */
   3592   u16 wctrlFlags,      /* One of the WHERE_* flags defined in sqliteInt.h */
   3593   Bitmask notReady     /* Which tables are currently available */
   3594 ){
   3595   int j, k;            /* Loop counters */
   3596   int iCur;            /* The VDBE cursor for the table */
   3597   int addrNxt;         /* Where to jump to continue with the next IN case */
   3598   int omitTable;       /* True if we use the index only */
   3599   int bRev;            /* True if we need to scan in reverse order */
   3600   WhereLevel *pLevel;  /* The where level to be coded */
   3601   WhereClause *pWC;    /* Decomposition of the entire WHERE clause */
   3602   WhereTerm *pTerm;               /* A WHERE clause term */
   3603   Parse *pParse;                  /* Parsing context */
   3604   Vdbe *v;                        /* The prepared stmt under constructions */
   3605   struct SrcList_item *pTabItem;  /* FROM clause term being coded */
   3606   int addrBrk;                    /* Jump here to break out of the loop */
   3607   int addrCont;                   /* Jump here to continue with next cycle */
   3608   int iRowidReg = 0;        /* Rowid is stored in this register, if not zero */
   3609   int iReleaseReg = 0;      /* Temp register to free before returning */
   3610 
   3611   pParse = pWInfo->pParse;
   3612   v = pParse->pVdbe;
   3613   pWC = pWInfo->pWC;
   3614   pLevel = &pWInfo->a[iLevel];
   3615   pTabItem = &pWInfo->pTabList->a[pLevel->iFrom];
   3616   iCur = pTabItem->iCursor;
   3617   bRev = (pLevel->plan.wsFlags & WHERE_REVERSE)!=0;
   3618   omitTable = (pLevel->plan.wsFlags & WHERE_IDX_ONLY)!=0
   3619            && (wctrlFlags & WHERE_FORCE_TABLE)==0;
   3620 
   3621   /* Create labels for the "break" and "continue" instructions
   3622   ** for the current loop.  Jump to addrBrk to break out of a loop.
   3623   ** Jump to cont to go immediately to the next iteration of the
   3624   ** loop.
   3625   **
   3626   ** When there is an IN operator, we also have a "addrNxt" label that
   3627   ** means to continue with the next IN value combination.  When
   3628   ** there are no IN operators in the constraints, the "addrNxt" label
   3629   ** is the same as "addrBrk".
   3630   */
   3631   addrBrk = pLevel->addrBrk = pLevel->addrNxt = sqlite3VdbeMakeLabel(v);
   3632   addrCont = pLevel->addrCont = sqlite3VdbeMakeLabel(v);
   3633 
   3634   /* If this is the right table of a LEFT OUTER JOIN, allocate and
   3635   ** initialize a memory cell that records if this table matches any
   3636   ** row of the left table of the join.
   3637   */
   3638   if( pLevel->iFrom>0 && (pTabItem[0].jointype & JT_LEFT)!=0 ){
   3639     pLevel->iLeftJoin = ++pParse->nMem;
   3640     sqlite3VdbeAddOp2(v, OP_Integer, 0, pLevel->iLeftJoin);
   3641     VdbeComment((v, "init LEFT JOIN no-match flag"));
   3642   }
   3643 
   3644 #ifndef SQLITE_OMIT_VIRTUALTABLE
   3645   if(  (pLevel->plan.wsFlags & WHERE_VIRTUALTABLE)!=0 ){
   3646     /* Case 0:  The table is a virtual-table.  Use the VFilter and VNext
   3647     **          to access the data.
   3648     */
   3649     int iReg;   /* P3 Value for OP_VFilter */
   3650     sqlite3_index_info *pVtabIdx = pLevel->plan.u.pVtabIdx;
   3651     int nConstraint = pVtabIdx->nConstraint;
   3652     struct sqlite3_index_constraint_usage *aUsage =
   3653                                                 pVtabIdx->aConstraintUsage;
   3654     const struct sqlite3_index_constraint *aConstraint =
   3655                                                 pVtabIdx->aConstraint;
   3656 
   3657     sqlite3ExprCachePush(pParse);
   3658     iReg = sqlite3GetTempRange(pParse, nConstraint+2);
   3659     for(j=1; j<=nConstraint; j++){
   3660       for(k=0; k<nConstraint; k++){
   3661         if( aUsage[k].argvIndex==j ){
   3662           int iTerm = aConstraint[k].iTermOffset;
   3663           sqlite3ExprCode(pParse, pWC->a[iTerm].pExpr->pRight, iReg+j+1);
   3664           break;
   3665         }
   3666       }
   3667       if( k==nConstraint ) break;
   3668     }
   3669     sqlite3VdbeAddOp2(v, OP_Integer, pVtabIdx->idxNum, iReg);
   3670     sqlite3VdbeAddOp2(v, OP_Integer, j-1, iReg+1);
   3671     sqlite3VdbeAddOp4(v, OP_VFilter, iCur, addrBrk, iReg, pVtabIdx->idxStr,
   3672                       pVtabIdx->needToFreeIdxStr ? P4_MPRINTF : P4_STATIC);
   3673     pVtabIdx->needToFreeIdxStr = 0;
   3674     for(j=0; j<nConstraint; j++){
   3675       if( aUsage[j].omit ){
   3676         int iTerm = aConstraint[j].iTermOffset;
   3677         disableTerm(pLevel, &pWC->a[iTerm]);
   3678       }
   3679     }
   3680     pLevel->op = OP_VNext;
   3681     pLevel->p1 = iCur;
   3682     pLevel->p2 = sqlite3VdbeCurrentAddr(v);
   3683     sqlite3ReleaseTempRange(pParse, iReg, nConstraint+2);
   3684     sqlite3ExprCachePop(pParse, 1);
   3685   }else
   3686 #endif /* SQLITE_OMIT_VIRTUALTABLE */
   3687 
   3688   if( pLevel->plan.wsFlags & WHERE_ROWID_EQ ){
   3689     /* Case 1:  We can directly reference a single row using an
   3690     **          equality comparison against the ROWID field.  Or
   3691     **          we reference multiple rows using a "rowid IN (...)"
   3692     **          construct.
   3693     */
   3694     iReleaseReg = sqlite3GetTempReg(pParse);
   3695     pTerm = findTerm(pWC, iCur, -1, notReady, WO_EQ|WO_IN, 0);
   3696     assert( pTerm!=0 );
   3697     assert( pTerm->pExpr!=0 );
   3698     assert( pTerm->leftCursor==iCur );
   3699     assert( omitTable==0 );
   3700     testcase( pTerm->wtFlags & TERM_VIRTUAL ); /* EV: R-30575-11662 */
   3701     iRowidReg = codeEqualityTerm(pParse, pTerm, pLevel, iReleaseReg);
   3702     addrNxt = pLevel->addrNxt;
   3703     sqlite3VdbeAddOp2(v, OP_MustBeInt, iRowidReg, addrNxt);
   3704     sqlite3VdbeAddOp3(v, OP_NotExists, iCur, addrNxt, iRowidReg);
   3705     sqlite3ExprCacheStore(pParse, iCur, -1, iRowidReg);
   3706     VdbeComment((v, "pk"));
   3707     pLevel->op = OP_Noop;
   3708   }else if( pLevel->plan.wsFlags & WHERE_ROWID_RANGE ){
   3709     /* Case 2:  We have an inequality comparison against the ROWID field.
   3710     */
   3711     int testOp = OP_Noop;
   3712     int start;
   3713     int memEndValue = 0;
   3714     WhereTerm *pStart, *pEnd;
   3715 
   3716     assert( omitTable==0 );
   3717     pStart = findTerm(pWC, iCur, -1, notReady, WO_GT|WO_GE, 0);
   3718     pEnd = findTerm(pWC, iCur, -1, notReady, WO_LT|WO_LE, 0);
   3719     if( bRev ){
   3720       pTerm = pStart;
   3721       pStart = pEnd;
   3722       pEnd = pTerm;
   3723     }
   3724     if( pStart ){
   3725       Expr *pX;             /* The expression that defines the start bound */
   3726       int r1, rTemp;        /* Registers for holding the start boundary */
   3727 
   3728       /* The following constant maps TK_xx codes into corresponding
   3729       ** seek opcodes.  It depends on a particular ordering of TK_xx
   3730       */
   3731       const u8 aMoveOp[] = {
   3732            /* TK_GT */  OP_SeekGt,
   3733            /* TK_LE */  OP_SeekLe,
   3734            /* TK_LT */  OP_SeekLt,
   3735            /* TK_GE */  OP_SeekGe
   3736       };
   3737       assert( TK_LE==TK_GT+1 );      /* Make sure the ordering.. */
   3738       assert( TK_LT==TK_GT+2 );      /*  ... of the TK_xx values... */
   3739       assert( TK_GE==TK_GT+3 );      /*  ... is correcct. */
   3740 
   3741       testcase( pStart->wtFlags & TERM_VIRTUAL ); /* EV: R-30575-11662 */
   3742       pX = pStart->pExpr;
   3743       assert( pX!=0 );
   3744       assert( pStart->leftCursor==iCur );
   3745       r1 = sqlite3ExprCodeTemp(pParse, pX->pRight, &rTemp);
   3746       sqlite3VdbeAddOp3(v, aMoveOp[pX->op-TK_GT], iCur, addrBrk, r1);
   3747       VdbeComment((v, "pk"));
   3748       sqlite3ExprCacheAffinityChange(pParse, r1, 1);
   3749       sqlite3ReleaseTempReg(pParse, rTemp);
   3750       disableTerm(pLevel, pStart);
   3751     }else{
   3752       sqlite3VdbeAddOp2(v, bRev ? OP_Last : OP_Rewind, iCur, addrBrk);
   3753     }
   3754     if( pEnd ){
   3755       Expr *pX;
   3756       pX = pEnd->pExpr;
   3757       assert( pX!=0 );
   3758       assert( pEnd->leftCursor==iCur );
   3759       testcase( pEnd->wtFlags & TERM_VIRTUAL ); /* EV: R-30575-11662 */
   3760       memEndValue = ++pParse->nMem;
   3761       sqlite3ExprCode(pParse, pX->pRight, memEndValue);
   3762       if( pX->op==TK_LT || pX->op==TK_GT ){
   3763         testOp = bRev ? OP_Le : OP_Ge;
   3764       }else{
   3765         testOp = bRev ? OP_Lt : OP_Gt;
   3766       }
   3767       disableTerm(pLevel, pEnd);
   3768     }
   3769     start = sqlite3VdbeCurrentAddr(v);
   3770     pLevel->op = bRev ? OP_Prev : OP_Next;
   3771     pLevel->p1 = iCur;
   3772     pLevel->p2 = start;
   3773     if( pStart==0 && pEnd==0 ){
   3774       pLevel->p5 = SQLITE_STMTSTATUS_FULLSCAN_STEP;
   3775     }else{
   3776       assert( pLevel->p5==0 );
   3777     }
   3778     if( testOp!=OP_Noop ){
   3779       iRowidReg = iReleaseReg = sqlite3GetTempReg(pParse);
   3780       sqlite3VdbeAddOp2(v, OP_Rowid, iCur, iRowidReg);
   3781       sqlite3ExprCacheStore(pParse, iCur, -1, iRowidReg);
   3782       sqlite3VdbeAddOp3(v, testOp, memEndValue, addrBrk, iRowidReg);
   3783       sqlite3VdbeChangeP5(v, SQLITE_AFF_NUMERIC | SQLITE_JUMPIFNULL);
   3784     }
   3785   }else if( pLevel->plan.wsFlags & (WHERE_COLUMN_RANGE|WHERE_COLUMN_EQ) ){
   3786     /* Case 3: A scan using an index.
   3787     **
   3788     **         The WHERE clause may contain zero or more equality
   3789     **         terms ("==" or "IN" operators) that refer to the N
   3790     **         left-most columns of the index. It may also contain
   3791     **         inequality constraints (>, <, >= or <=) on the indexed
   3792     **         column that immediately follows the N equalities. Only
   3793     **         the right-most column can be an inequality - the rest must
   3794     **         use the "==" and "IN" operators. For example, if the
   3795     **         index is on (x,y,z), then the following clauses are all
   3796     **         optimized:
   3797     **
   3798     **            x=5
   3799     **            x=5 AND y=10
   3800     **            x=5 AND y<10
   3801     **            x=5 AND y>5 AND y<10
   3802     **            x=5 AND y=5 AND z<=10
   3803     **
   3804     **         The z<10 term of the following cannot be used, only
   3805     **         the x=5 term:
   3806     **
   3807     **            x=5 AND z<10
   3808     **
   3809     **         N may be zero if there are inequality constraints.
   3810     **         If there are no inequality constraints, then N is at
   3811     **         least one.
   3812     **
   3813     **         This case is also used when there are no WHERE clause
   3814     **         constraints but an index is selected anyway, in order
   3815     **         to force the output order to conform to an ORDER BY.
   3816     */
   3817     static const u8 aStartOp[] = {
   3818       0,
   3819       0,
   3820       OP_Rewind,           /* 2: (!start_constraints && startEq &&  !bRev) */
   3821       OP_Last,             /* 3: (!start_constraints && startEq &&   bRev) */
   3822       OP_SeekGt,           /* 4: (start_constraints  && !startEq && !bRev) */
   3823       OP_SeekLt,           /* 5: (start_constraints  && !startEq &&  bRev) */
   3824       OP_SeekGe,           /* 6: (start_constraints  &&  startEq && !bRev) */
   3825       OP_SeekLe            /* 7: (start_constraints  &&  startEq &&  bRev) */
   3826     };
   3827     static const u8 aEndOp[] = {
   3828       OP_Noop,             /* 0: (!end_constraints) */
   3829       OP_IdxGE,            /* 1: (end_constraints && !bRev) */
   3830       OP_IdxLT             /* 2: (end_constraints && bRev) */
   3831     };
   3832     int nEq = pLevel->plan.nEq;  /* Number of == or IN terms */
   3833     int isMinQuery = 0;          /* If this is an optimized SELECT min(x).. */
   3834     int regBase;                 /* Base register holding constraint values */
   3835     int r1;                      /* Temp register */
   3836     WhereTerm *pRangeStart = 0;  /* Inequality constraint at range start */
   3837     WhereTerm *pRangeEnd = 0;    /* Inequality constraint at range end */
   3838     int startEq;                 /* True if range start uses ==, >= or <= */
   3839     int endEq;                   /* True if range end uses ==, >= or <= */
   3840     int start_constraints;       /* Start of range is constrained */
   3841     int nConstraint;             /* Number of constraint terms */
   3842     Index *pIdx;                 /* The index we will be using */
   3843     int iIdxCur;                 /* The VDBE cursor for the index */
   3844     int nExtraReg = 0;           /* Number of extra registers needed */
   3845     int op;                      /* Instruction opcode */
   3846     char *zStartAff;             /* Affinity for start of range constraint */
   3847     char *zEndAff;               /* Affinity for end of range constraint */
   3848 
   3849     pIdx = pLevel->plan.u.pIdx;
   3850     iIdxCur = pLevel->iIdxCur;
   3851     k = pIdx->aiColumn[nEq];     /* Column for inequality constraints */
   3852 
   3853     /* If this loop satisfies a sort order (pOrderBy) request that
   3854     ** was passed to this function to implement a "SELECT min(x) ..."
   3855     ** query, then the caller will only allow the loop to run for
   3856     ** a single iteration. This means that the first row returned
   3857     ** should not have a NULL value stored in 'x'. If column 'x' is
   3858     ** the first one after the nEq equality constraints in the index,
   3859     ** this requires some special handling.
   3860     */
   3861     if( (wctrlFlags&WHERE_ORDERBY_MIN)!=0
   3862      && (pLevel->plan.wsFlags&WHERE_ORDERBY)
   3863      && (pIdx->nColumn>nEq)
   3864     ){
   3865       /* assert( pOrderBy->nExpr==1 ); */
   3866       /* assert( pOrderBy->a[0].pExpr->iColumn==pIdx->aiColumn[nEq] ); */
   3867       isMinQuery = 1;
   3868       nExtraReg = 1;
   3869     }
   3870 
   3871     /* Find any inequality constraint terms for the start and end
   3872     ** of the range.
   3873     */
   3874     if( pLevel->plan.wsFlags & WHERE_TOP_LIMIT ){
   3875       pRangeEnd = findTerm(pWC, iCur, k, notReady, (WO_LT|WO_LE), pIdx);
   3876       nExtraReg = 1;
   3877     }
   3878     if( pLevel->plan.wsFlags & WHERE_BTM_LIMIT ){
   3879       pRangeStart = findTerm(pWC, iCur, k, notReady, (WO_GT|WO_GE), pIdx);
   3880       nExtraReg = 1;
   3881     }
   3882 
   3883     /* Generate code to evaluate all constraint terms using == or IN
   3884     ** and store the values of those terms in an array of registers
   3885     ** starting at regBase.
   3886     */
   3887     regBase = codeAllEqualityTerms(
   3888         pParse, pLevel, pWC, notReady, nExtraReg, &zStartAff
   3889     );
   3890     zEndAff = sqlite3DbStrDup(pParse->db, zStartAff);
   3891     addrNxt = pLevel->addrNxt;
   3892 
   3893     /* If we are doing a reverse order scan on an ascending index, or
   3894     ** a forward order scan on a descending index, interchange the
   3895     ** start and end terms (pRangeStart and pRangeEnd).
   3896     */
   3897     if( nEq<pIdx->nColumn && bRev==(pIdx->aSortOrder[nEq]==SQLITE_SO_ASC) ){
   3898       SWAP(WhereTerm *, pRangeEnd, pRangeStart);
   3899     }
   3900 
   3901     testcase( pRangeStart && pRangeStart->eOperator & WO_LE );
   3902     testcase( pRangeStart && pRangeStart->eOperator & WO_GE );
   3903     testcase( pRangeEnd && pRangeEnd->eOperator & WO_LE );
   3904     testcase( pRangeEnd && pRangeEnd->eOperator & WO_GE );
   3905     startEq = !pRangeStart || pRangeStart->eOperator & (WO_LE|WO_GE);
   3906     endEq =   !pRangeEnd || pRangeEnd->eOperator & (WO_LE|WO_GE);
   3907     start_constraints = pRangeStart || nEq>0;
   3908 
   3909     /* Seek the index cursor to the start of the range. */
   3910     nConstraint = nEq;
   3911     if( pRangeStart ){
   3912       Expr *pRight = pRangeStart->pExpr->pRight;
   3913       sqlite3ExprCode(pParse, pRight, regBase+nEq);
   3914       if( (pRangeStart->wtFlags & TERM_VNULL)==0 ){
   3915         sqlite3ExprCodeIsNullJump(v, pRight, regBase+nEq, addrNxt);
   3916       }
   3917       if( zStartAff ){
   3918         if( sqlite3CompareAffinity(pRight, zStartAff[nEq])==SQLITE_AFF_NONE){
   3919           /* Since the comparison is to be performed with no conversions
   3920           ** applied to the operands, set the affinity to apply to pRight to
   3921           ** SQLITE_AFF_NONE.  */
   3922           zStartAff[nEq] = SQLITE_AFF_NONE;
   3923         }
   3924         if( sqlite3ExprNeedsNoAffinityChange(pRight, zStartAff[nEq]) ){
   3925           zStartAff[nEq] = SQLITE_AFF_NONE;
   3926         }
   3927       }
   3928       nConstraint++;
   3929       testcase( pRangeStart->wtFlags & TERM_VIRTUAL ); /* EV: R-30575-11662 */
   3930     }else if( isMinQuery ){
   3931       sqlite3VdbeAddOp2(v, OP_Null, 0, regBase+nEq);
   3932       nConstraint++;
   3933       startEq = 0;
   3934       start_constraints = 1;
   3935     }
   3936     codeApplyAffinity(pParse, regBase, nConstraint, zStartAff);
   3937     op = aStartOp[(start_constraints<<2) + (startEq<<1) + bRev];
   3938     assert( op!=0 );
   3939     testcase( op==OP_Rewind );
   3940     testcase( op==OP_Last );
   3941     testcase( op==OP_SeekGt );
   3942     testcase( op==OP_SeekGe );
   3943     testcase( op==OP_SeekLe );
   3944     testcase( op==OP_SeekLt );
   3945     sqlite3VdbeAddOp4Int(v, op, iIdxCur, addrNxt, regBase, nConstraint);
   3946 
   3947     /* Load the value for the inequality constraint at the end of the
   3948     ** range (if any).
   3949     */
   3950     nConstraint = nEq;
   3951     if( pRangeEnd ){
   3952       Expr *pRight = pRangeEnd->pExpr->pRight;
   3953       sqlite3ExprCacheRemove(pParse, regBase+nEq, 1);
   3954       sqlite3ExprCode(pParse, pRight, regBase+nEq);
   3955       if( (pRangeEnd->wtFlags & TERM_VNULL)==0 ){
   3956         sqlite3ExprCodeIsNullJump(v, pRight, regBase+nEq, addrNxt);
   3957       }
   3958       if( zEndAff ){
   3959         if( sqlite3CompareAffinity(pRight, zEndAff[nEq])==SQLITE_AFF_NONE){
   3960           /* Since the comparison is to be performed with no conversions
   3961           ** applied to the operands, set the affinity to apply to pRight to
   3962           ** SQLITE_AFF_NONE.  */
   3963           zEndAff[nEq] = SQLITE_AFF_NONE;
   3964         }
   3965         if( sqlite3ExprNeedsNoAffinityChange(pRight, zEndAff[nEq]) ){
   3966           zEndAff[nEq] = SQLITE_AFF_NONE;
   3967         }
   3968       }
   3969       codeApplyAffinity(pParse, regBase, nEq+1, zEndAff);
   3970       nConstraint++;
   3971       testcase( pRangeEnd->wtFlags & TERM_VIRTUAL ); /* EV: R-30575-11662 */
   3972     }
   3973     sqlite3DbFree(pParse->db, zStartAff);
   3974     sqlite3DbFree(pParse->db, zEndAff);
   3975 
   3976     /* Top of the loop body */
   3977     pLevel->p2 = sqlite3VdbeCurrentAddr(v);
   3978 
   3979     /* Check if the index cursor is past the end of the range. */
   3980     op = aEndOp[(pRangeEnd || nEq) * (1 + bRev)];
   3981     testcase( op==OP_Noop );
   3982     testcase( op==OP_IdxGE );
   3983     testcase( op==OP_IdxLT );
   3984     if( op!=OP_Noop ){
   3985       sqlite3VdbeAddOp4Int(v, op, iIdxCur, addrNxt, regBase, nConstraint);
   3986       sqlite3VdbeChangeP5(v, endEq!=bRev ?1:0);
   3987     }
   3988 
   3989     /* If there are inequality constraints, check that the value
   3990     ** of the table column that the inequality contrains is not NULL.
   3991     ** If it is, jump to the next iteration of the loop.
   3992     */
   3993     r1 = sqlite3GetTempReg(pParse);
   3994     testcase( pLevel->plan.wsFlags & WHERE_BTM_LIMIT );
   3995     testcase( pLevel->plan.wsFlags & WHERE_TOP_LIMIT );
   3996     if( (pLevel->plan.wsFlags & (WHERE_BTM_LIMIT|WHERE_TOP_LIMIT))!=0 ){
   3997       sqlite3VdbeAddOp3(v, OP_Column, iIdxCur, nEq, r1);
   3998       sqlite3VdbeAddOp2(v, OP_IsNull, r1, addrCont);
   3999     }
   4000     sqlite3ReleaseTempReg(pParse, r1);
   4001 
   4002     /* Seek the table cursor, if required */
   4003     disableTerm(pLevel, pRangeStart);
   4004     disableTerm(pLevel, pRangeEnd);
   4005     if( !omitTable ){
   4006       iRowidReg = iReleaseReg = sqlite3GetTempReg(pParse);
   4007       sqlite3VdbeAddOp2(v, OP_IdxRowid, iIdxCur, iRowidReg);
   4008       sqlite3ExprCacheStore(pParse, iCur, -1, iRowidReg);
   4009       sqlite3VdbeAddOp2(v, OP_Seek, iCur, iRowidReg);  /* Deferred seek */
   4010     }
   4011 
   4012     /* Record the instruction used to terminate the loop. Disable
   4013     ** WHERE clause terms made redundant by the index range scan.
   4014     */
   4015     if( pLevel->plan.wsFlags & WHERE_UNIQUE ){
   4016       pLevel->op = OP_Noop;
   4017     }else if( bRev ){
   4018       pLevel->op = OP_Prev;
   4019     }else{
   4020       pLevel->op = OP_Next;
   4021     }
   4022     pLevel->p1 = iIdxCur;
   4023   }else
   4024 
   4025 #ifndef SQLITE_OMIT_OR_OPTIMIZATION
   4026   if( pLevel->plan.wsFlags & WHERE_MULTI_OR ){
   4027     /* Case 4:  Two or more separately indexed terms connected by OR
   4028     **
   4029     ** Example:
   4030     **
   4031     **   CREATE TABLE t1(a,b,c,d);
   4032     **   CREATE INDEX i1 ON t1(a);
   4033     **   CREATE INDEX i2 ON t1(b);
   4034     **   CREATE INDEX i3 ON t1(c);
   4035     **
   4036     **   SELECT * FROM t1 WHERE a=5 OR b=7 OR (c=11 AND d=13)
   4037     **
   4038     ** In the example, there are three indexed terms connected by OR.
   4039     ** The top of the loop looks like this:
   4040     **
   4041     **          Null       1                # Zero the rowset in reg 1
   4042     **
   4043     ** Then, for each indexed term, the following. The arguments to
   4044     ** RowSetTest are such that the rowid of the current row is inserted
   4045     ** into the RowSet. If it is already present, control skips the
   4046     ** Gosub opcode and jumps straight to the code generated by WhereEnd().
   4047     **
   4048     **        sqlite3WhereBegin(<term>)
   4049     **          RowSetTest                  # Insert rowid into rowset
   4050     **          Gosub      2 A
   4051     **        sqlite3WhereEnd()
   4052     **
   4053     ** Following the above, code to terminate the loop. Label A, the target
   4054     ** of the Gosub above, jumps to the instruction right after the Goto.
   4055     **
   4056     **          Null       1                # Zero the rowset in reg 1
   4057     **          Goto       B                # The loop is finished.
   4058     **
   4059     **       A: <loop body>                 # Return data, whatever.
   4060     **
   4061     **          Return     2                # Jump back to the Gosub
   4062     **
   4063     **       B: <after the loop>
   4064     **
   4065     */
   4066     WhereClause *pOrWc;    /* The OR-clause broken out into subterms */
   4067     SrcList *pOrTab;       /* Shortened table list or OR-clause generation */
   4068 
   4069     int regReturn = ++pParse->nMem;           /* Register used with OP_Gosub */
   4070     int regRowset = 0;                        /* Register for RowSet object */
   4071     int regRowid = 0;                         /* Register holding rowid */
   4072     int iLoopBody = sqlite3VdbeMakeLabel(v);  /* Start of loop body */
   4073     int iRetInit;                             /* Address of regReturn init */
   4074     int untestedTerms = 0;             /* Some terms not completely tested */
   4075     int ii;
   4076 
   4077     pTerm = pLevel->plan.u.pTerm;
   4078     assert( pTerm!=0 );
   4079     assert( pTerm->eOperator==WO_OR );
   4080     assert( (pTerm->wtFlags & TERM_ORINFO)!=0 );
   4081     pOrWc = &pTerm->u.pOrInfo->wc;
   4082     pLevel->op = OP_Return;
   4083     pLevel->p1 = regReturn;
   4084 
   4085     /* Set up a new SrcList ni pOrTab containing the table being scanned
   4086     ** by this loop in the a[0] slot and all notReady tables in a[1..] slots.
   4087     ** This becomes the SrcList in the recursive call to sqlite3WhereBegin().
   4088     */
   4089     if( pWInfo->nLevel>1 ){
   4090       int nNotReady;                 /* The number of notReady tables */
   4091       struct SrcList_item *origSrc;     /* Original list of tables */
   4092       nNotReady = pWInfo->nLevel - iLevel - 1;
   4093       pOrTab = sqlite3StackAllocRaw(pParse->db,
   4094                             sizeof(*pOrTab)+ nNotReady*sizeof(pOrTab->a[0]));
   4095       if( pOrTab==0 ) return notReady;
   4096       pOrTab->nAlloc = (i16)(nNotReady + 1);
   4097       pOrTab->nSrc = pOrTab->nAlloc;
   4098       memcpy(pOrTab->a, pTabItem, sizeof(*pTabItem));
   4099       origSrc = pWInfo->pTabList->a;
   4100       for(k=1; k<=nNotReady; k++){
   4101         memcpy(&pOrTab->a[k], &origSrc[pLevel[k].iFrom], sizeof(pOrTab->a[k]));
   4102       }
   4103     }else{
   4104       pOrTab = pWInfo->pTabList;
   4105     }
   4106 
   4107     /* Initialize the rowset register to contain NULL. An SQL NULL is
   4108     ** equivalent to an empty rowset.
   4109     **
   4110     ** Also initialize regReturn to contain the address of the instruction
   4111     ** immediately following the OP_Return at the bottom of the loop. This
   4112     ** is required in a few obscure LEFT JOIN cases where control jumps
   4113     ** over the top of the loop into the body of it. In this case the
   4114     ** correct response for the end-of-loop code (the OP_Return) is to
   4115     ** fall through to the next instruction, just as an OP_Next does if
   4116     ** called on an uninitialized cursor.
   4117     */
   4118     if( (wctrlFlags & WHERE_DUPLICATES_OK)==0 ){
   4119       regRowset = ++pParse->nMem;
   4120       regRowid = ++pParse->nMem;
   4121       sqlite3VdbeAddOp2(v, OP_Null, 0, regRowset);
   4122     }
   4123     iRetInit = sqlite3VdbeAddOp2(v, OP_Integer, 0, regReturn);
   4124 
   4125     for(ii=0; ii<pOrWc->nTerm; ii++){
   4126       WhereTerm *pOrTerm = &pOrWc->a[ii];
   4127       if( pOrTerm->leftCursor==iCur || pOrTerm->eOperator==WO_AND ){
   4128         WhereInfo *pSubWInfo;          /* Info for single OR-term scan */
   4129         /* Loop through table entries that match term pOrTerm. */
   4130         pSubWInfo = sqlite3WhereBegin(pParse, pOrTab, pOrTerm->pExpr, 0,
   4131                         WHERE_OMIT_OPEN | WHERE_OMIT_CLOSE |
   4132                         WHERE_FORCE_TABLE | WHERE_ONETABLE_ONLY);
   4133         if( pSubWInfo ){
   4134           explainOneScan(
   4135               pParse, pOrTab, &pSubWInfo->a[0], iLevel, pLevel->iFrom, 0
   4136           );
   4137           if( (wctrlFlags & WHERE_DUPLICATES_OK)==0 ){
   4138             int iSet = ((ii==pOrWc->nTerm-1)?-1:ii);
   4139             int r;
   4140             r = sqlite3ExprCodeGetColumn(pParse, pTabItem->pTab, -1, iCur,
   4141                                          regRowid);
   4142             sqlite3VdbeAddOp4Int(v, OP_RowSetTest, regRowset,
   4143                                  sqlite3VdbeCurrentAddr(v)+2, r, iSet);
   4144           }
   4145           sqlite3VdbeAddOp2(v, OP_Gosub, regReturn, iLoopBody);
   4146 
   4147           /* The pSubWInfo->untestedTerms flag means that this OR term
   4148           ** contained one or more AND term from a notReady table.  The
   4149           ** terms from the notReady table could not be tested and will
   4150           ** need to be tested later.
   4151           */
   4152           if( pSubWInfo->untestedTerms ) untestedTerms = 1;
   4153 
   4154           /* Finish the loop through table entries that match term pOrTerm. */
   4155           sqlite3WhereEnd(pSubWInfo);
   4156         }
   4157       }
   4158     }
   4159     sqlite3VdbeChangeP1(v, iRetInit, sqlite3VdbeCurrentAddr(v));
   4160     sqlite3VdbeAddOp2(v, OP_Goto, 0, pLevel->addrBrk);
   4161     sqlite3VdbeResolveLabel(v, iLoopBody);
   4162 
   4163     if( pWInfo->nLevel>1 ) sqlite3StackFree(pParse->db, pOrTab);
   4164     if( !untestedTerms ) disableTerm(pLevel, pTerm);
   4165   }else
   4166 #endif /* SQLITE_OMIT_OR_OPTIMIZATION */
   4167 
   4168   {
   4169     /* Case 5:  There is no usable index.  We must do a complete
   4170     **          scan of the entire table.
   4171     */
   4172     static const u8 aStep[] = { OP_Next, OP_Prev };
   4173     static const u8 aStart[] = { OP_Rewind, OP_Last };
   4174     assert( bRev==0 || bRev==1 );
   4175     assert( omitTable==0 );
   4176     pLevel->op = aStep[bRev];
   4177     pLevel->p1 = iCur;
   4178     pLevel->p2 = 1 + sqlite3VdbeAddOp2(v, aStart[bRev], iCur, addrBrk);
   4179     pLevel->p5 = SQLITE_STMTSTATUS_FULLSCAN_STEP;
   4180   }
   4181   notReady &= ~getMask(pWC->pMaskSet, iCur);
   4182 
   4183   /* Insert code to test every subexpression that can be completely
   4184   ** computed using the current set of tables.
   4185   **
   4186   ** IMPLEMENTATION-OF: R-49525-50935 Terms that cannot be satisfied through
   4187   ** the use of indices become tests that are evaluated against each row of
   4188   ** the relevant input tables.
   4189   */
   4190   for(pTerm=pWC->a, j=pWC->nTerm; j>0; j--, pTerm++){
   4191     Expr *pE;
   4192     testcase( pTerm->wtFlags & TERM_VIRTUAL ); /* IMP: R-30575-11662 */
   4193     testcase( pTerm->wtFlags & TERM_CODED );
   4194     if( pTerm->wtFlags & (TERM_VIRTUAL|TERM_CODED) ) continue;
   4195     if( (pTerm->prereqAll & notReady)!=0 ){
   4196       testcase( pWInfo->untestedTerms==0
   4197                && (pWInfo->wctrlFlags & WHERE_ONETABLE_ONLY)!=0 );
   4198       pWInfo->untestedTerms = 1;
   4199       continue;
   4200     }
   4201     pE = pTerm->pExpr;
   4202     assert( pE!=0 );
   4203     if( pLevel->iLeftJoin && !ExprHasProperty(pE, EP_FromJoin) ){
   4204       continue;
   4205     }
   4206     sqlite3ExprIfFalse(pParse, pE, addrCont, SQLITE_JUMPIFNULL);
   4207     pTerm->wtFlags |= TERM_CODED;
   4208   }
   4209 
   4210   /* For a LEFT OUTER JOIN, generate code that will record the fact that
   4211   ** at least one row of the right table has matched the left table.
   4212   */
   4213   if( pLevel->iLeftJoin ){
   4214     pLevel->addrFirst = sqlite3VdbeCurrentAddr(v);
   4215     sqlite3VdbeAddOp2(v, OP_Integer, 1, pLevel->iLeftJoin);
   4216     VdbeComment((v, "record LEFT JOIN hit"));
   4217     sqlite3ExprCacheClear(pParse);
   4218     for(pTerm=pWC->a, j=0; j<pWC->nTerm; j++, pTerm++){
   4219       testcase( pTerm->wtFlags & TERM_VIRTUAL );  /* IMP: R-30575-11662 */
   4220       testcase( pTerm->wtFlags & TERM_CODED );
   4221       if( pTerm->wtFlags & (TERM_VIRTUAL|TERM_CODED) ) continue;
   4222       if( (pTerm->prereqAll & notReady)!=0 ){
   4223         assert( pWInfo->untestedTerms );
   4224         continue;
   4225       }
   4226       assert( pTerm->pExpr );
   4227       sqlite3ExprIfFalse(pParse, pTerm->pExpr, addrCont, SQLITE_JUMPIFNULL);
   4228       pTerm->wtFlags |= TERM_CODED;
   4229     }
   4230   }
   4231   sqlite3ReleaseTempReg(pParse, iReleaseReg);
   4232 
   4233   return notReady;
   4234 }
   4235 
   4236 #if defined(SQLITE_TEST)
   4237 /*
   4238 ** The following variable holds a text description of query plan generated
   4239 ** by the most recent call to sqlite3WhereBegin().  Each call to WhereBegin
   4240 ** overwrites the previous.  This information is used for testing and
   4241 ** analysis only.
   4242 */
   4243 char sqlite3_query_plan[BMS*2*40];  /* Text of the join */
   4244 static int nQPlan = 0;              /* Next free slow in _query_plan[] */
   4245 
   4246 #endif /* SQLITE_TEST */
   4247 
   4248 
   4249 /*
   4250 ** Free a WhereInfo structure
   4251 */
   4252 static void whereInfoFree(sqlite3 *db, WhereInfo *pWInfo){
   4253   if( ALWAYS(pWInfo) ){
   4254     int i;
   4255     for(i=0; i<pWInfo->nLevel; i++){
   4256       sqlite3_index_info *pInfo = pWInfo->a[i].pIdxInfo;
   4257       if( pInfo ){
   4258         /* assert( pInfo->needToFreeIdxStr==0 || db->mallocFailed ); */
   4259         if( pInfo->needToFreeIdxStr ){
   4260           sqlite3_free(pInfo->idxStr);
   4261         }
   4262         sqlite3DbFree(db, pInfo);
   4263       }
   4264       if( pWInfo->a[i].plan.wsFlags & WHERE_TEMP_INDEX ){
   4265         Index *pIdx = pWInfo->a[i].plan.u.pIdx;
   4266         if( pIdx ){
   4267           sqlite3DbFree(db, pIdx->zColAff);
   4268           sqlite3DbFree(db, pIdx);
   4269         }
   4270       }
   4271     }
   4272     whereClauseClear(pWInfo->pWC);
   4273     sqlite3DbFree(db, pWInfo);
   4274   }
   4275 }
   4276 
   4277 
   4278 /*
   4279 ** Generate the beginning of the loop used for WHERE clause processing.
   4280 ** The return value is a pointer to an opaque structure that contains
   4281 ** information needed to terminate the loop.  Later, the calling routine
   4282 ** should invoke sqlite3WhereEnd() with the return value of this function
   4283 ** in order to complete the WHERE clause processing.
   4284 **
   4285 ** If an error occurs, this routine returns NULL.
   4286 **
   4287 ** The basic idea is to do a nested loop, one loop for each table in
   4288 ** the FROM clause of a select.  (INSERT and UPDATE statements are the
   4289 ** same as a SELECT with only a single table in the FROM clause.)  For
   4290 ** example, if the SQL is this:
   4291 **
   4292 **       SELECT * FROM t1, t2, t3 WHERE ...;
   4293 **
   4294 ** Then the code generated is conceptually like the following:
   4295 **
   4296 **      foreach row1 in t1 do       \    Code generated
   4297 **        foreach row2 in t2 do      |-- by sqlite3WhereBegin()
   4298 **          foreach row3 in t3 do   /
   4299 **            ...
   4300 **          end                     \    Code generated
   4301 **        end                        |-- by sqlite3WhereEnd()
   4302 **      end                         /
   4303 **
   4304 ** Note that the loops might not be nested in the order in which they
   4305 ** appear in the FROM clause if a different order is better able to make
   4306 ** use of indices.  Note also that when the IN operator appears in
   4307 ** the WHERE clause, it might result in additional nested loops for
   4308 ** scanning through all values on the right-hand side of the IN.
   4309 **
   4310 ** There are Btree cursors associated with each table.  t1 uses cursor
   4311 ** number pTabList->a[0].iCursor.  t2 uses the cursor pTabList->a[1].iCursor.
   4312 ** And so forth.  This routine generates code to open those VDBE cursors
   4313 ** and sqlite3WhereEnd() generates the code to close them.
   4314 **
   4315 ** The code that sqlite3WhereBegin() generates leaves the cursors named
   4316 ** in pTabList pointing at their appropriate entries.  The [...] code
   4317 ** can use OP_Column and OP_Rowid opcodes on these cursors to extract
   4318 ** data from the various tables of the loop.
   4319 **
   4320 ** If the WHERE clause is empty, the foreach loops must each scan their
   4321 ** entire tables.  Thus a three-way join is an O(N^3) operation.  But if
   4322 ** the tables have indices and there are terms in the WHERE clause that
   4323 ** refer to those indices, a complete table scan can be avoided and the
   4324 ** code will run much faster.  Most of the work of this routine is checking
   4325 ** to see if there are indices that can be used to speed up the loop.
   4326 **
   4327 ** Terms of the WHERE clause are also used to limit which rows actually
   4328 ** make it to the "..." in the middle of the loop.  After each "foreach",
   4329 ** terms of the WHERE clause that use only terms in that loop and outer
   4330 ** loops are evaluated and if false a jump is made around all subsequent
   4331 ** inner loops (or around the "..." if the test occurs within the inner-
   4332 ** most loop)
   4333 **
   4334 ** OUTER JOINS
   4335 **
   4336 ** An outer join of tables t1 and t2 is conceptally coded as follows:
   4337 **
   4338 **    foreach row1 in t1 do
   4339 **      flag = 0
   4340 **      foreach row2 in t2 do
   4341 **        start:
   4342 **          ...
   4343 **          flag = 1
   4344 **      end
   4345 **      if flag==0 then
   4346 **        move the row2 cursor to a null row
   4347 **        goto start
   4348 **      fi
   4349 **    end
   4350 **
   4351 ** ORDER BY CLAUSE PROCESSING
   4352 **
   4353 ** *ppOrderBy is a pointer to the ORDER BY clause of a SELECT statement,
   4354 ** if there is one.  If there is no ORDER BY clause or if this routine
   4355 ** is called from an UPDATE or DELETE statement, then ppOrderBy is NULL.
   4356 **
   4357 ** If an index can be used so that the natural output order of the table
   4358 ** scan is correct for the ORDER BY clause, then that index is used and
   4359 ** *ppOrderBy is set to NULL.  This is an optimization that prevents an
   4360 ** unnecessary sort of the result set if an index appropriate for the
   4361 ** ORDER BY clause already exists.
   4362 **
   4363 ** If the where clause loops cannot be arranged to provide the correct
   4364 ** output order, then the *ppOrderBy is unchanged.
   4365 */
   4366 WhereInfo *sqlite3WhereBegin(
   4367   Parse *pParse,        /* The parser context */
   4368   SrcList *pTabList,    /* A list of all tables to be scanned */
   4369   Expr *pWhere,         /* The WHERE clause */
   4370   ExprList **ppOrderBy, /* An ORDER BY clause, or NULL */
   4371   u16 wctrlFlags        /* One of the WHERE_* flags defined in sqliteInt.h */
   4372 ){
   4373   int i;                     /* Loop counter */
   4374   int nByteWInfo;            /* Num. bytes allocated for WhereInfo struct */
   4375   int nTabList;              /* Number of elements in pTabList */
   4376   WhereInfo *pWInfo;         /* Will become the return value of this function */
   4377   Vdbe *v = pParse->pVdbe;   /* The virtual database engine */
   4378   Bitmask notReady;          /* Cursors that are not yet positioned */
   4379   WhereMaskSet *pMaskSet;    /* The expression mask set */
   4380   WhereClause *pWC;               /* Decomposition of the WHERE clause */
   4381   struct SrcList_item *pTabItem;  /* A single entry from pTabList */
   4382   WhereLevel *pLevel;             /* A single level in the pWInfo list */
   4383   int iFrom;                      /* First unused FROM clause element */
   4384   int andFlags;              /* AND-ed combination of all pWC->a[].wtFlags */
   4385   sqlite3 *db;               /* Database connection */
   4386 
   4387   /* The number of tables in the FROM clause is limited by the number of
   4388   ** bits in a Bitmask
   4389   */
   4390   testcase( pTabList->nSrc==BMS );
   4391   if( pTabList->nSrc>BMS ){
   4392     sqlite3ErrorMsg(pParse, "at most %d tables in a join", BMS);
   4393     return 0;
   4394   }
   4395 
   4396   /* This function normally generates a nested loop for all tables in
   4397   ** pTabList.  But if the WHERE_ONETABLE_ONLY flag is set, then we should
   4398   ** only generate code for the first table in pTabList and assume that
   4399   ** any cursors associated with subsequent tables are uninitialized.
   4400   */
   4401   nTabList = (wctrlFlags & WHERE_ONETABLE_ONLY) ? 1 : pTabList->nSrc;
   4402 
   4403   /* Allocate and initialize the WhereInfo structure that will become the
   4404   ** return value. A single allocation is used to store the WhereInfo
   4405   ** struct, the contents of WhereInfo.a[], the WhereClause structure
   4406   ** and the WhereMaskSet structure. Since WhereClause contains an 8-byte
   4407   ** field (type Bitmask) it must be aligned on an 8-byte boundary on
   4408   ** some architectures. Hence the ROUND8() below.
   4409   */
   4410   db = pParse->db;
   4411   nByteWInfo = ROUND8(sizeof(WhereInfo)+(nTabList-1)*sizeof(WhereLevel));
   4412   pWInfo = sqlite3DbMallocZero(db,
   4413       nByteWInfo +
   4414       sizeof(WhereClause) +
   4415       sizeof(WhereMaskSet)
   4416   );
   4417   if( db->mallocFailed ){
   4418     sqlite3DbFree(db, pWInfo);
   4419     pWInfo = 0;
   4420     goto whereBeginError;
   4421   }
   4422   pWInfo->nLevel = nTabList;
   4423   pWInfo->pParse = pParse;
   4424   pWInfo->pTabList = pTabList;
   4425   pWInfo->iBreak = sqlite3VdbeMakeLabel(v);
   4426   pWInfo->pWC = pWC = (WhereClause *)&((u8 *)pWInfo)[nByteWInfo];
   4427   pWInfo->wctrlFlags = wctrlFlags;
   4428   pWInfo->savedNQueryLoop = pParse->nQueryLoop;
   4429   pMaskSet = (WhereMaskSet*)&pWC[1];
   4430 
   4431   /* Split the WHERE clause into separate subexpressions where each
   4432   ** subexpression is separated by an AND operator.
   4433   */
   4434   initMaskSet(pMaskSet);
   4435   whereClauseInit(pWC, pParse, pMaskSet);
   4436   sqlite3ExprCodeConstants(pParse, pWhere);
   4437   whereSplit(pWC, pWhere, TK_AND);   /* IMP: R-15842-53296 */
   4438 
   4439   /* Special case: a WHERE clause that is constant.  Evaluate the
   4440   ** expression and either jump over all of the code or fall thru.
   4441   */
   4442   if( pWhere && (nTabList==0 || sqlite3ExprIsConstantNotJoin(pWhere)) ){
   4443     sqlite3ExprIfFalse(pParse, pWhere, pWInfo->iBreak, SQLITE_JUMPIFNULL);
   4444     pWhere = 0;
   4445   }
   4446 
   4447   /* Assign a bit from the bitmask to every term in the FROM clause.
   4448   **
   4449   ** When assigning bitmask values to FROM clause cursors, it must be
   4450   ** the case that if X is the bitmask for the N-th FROM clause term then
   4451   ** the bitmask for all FROM clause terms to the left of the N-th term
   4452   ** is (X-1).   An expression from the ON clause of a LEFT JOIN can use
   4453   ** its Expr.iRightJoinTable value to find the bitmask of the right table
   4454   ** of the join.  Subtracting one from the right table bitmask gives a
   4455   ** bitmask for all tables to the left of the join.  Knowing the bitmask
   4456   ** for all tables to the left of a left join is important.  Ticket #3015.
   4457   **
   4458   ** Configure the WhereClause.vmask variable so that bits that correspond
   4459   ** to virtual table cursors are set. This is used to selectively disable
   4460   ** the OR-to-IN transformation in exprAnalyzeOrTerm(). It is not helpful
   4461   ** with virtual tables.
   4462   **
   4463   ** Note that bitmasks are created for all pTabList->nSrc tables in
   4464   ** pTabList, not just the first nTabList tables.  nTabList is normally
   4465   ** equal to pTabList->nSrc but might be shortened to 1 if the
   4466   ** WHERE_ONETABLE_ONLY flag is set.
   4467   */
   4468   assert( pWC->vmask==0 && pMaskSet->n==0 );
   4469   for(i=0; i<pTabList->nSrc; i++){
   4470     createMask(pMaskSet, pTabList->a[i].iCursor);
   4471 #ifndef SQLITE_OMIT_VIRTUALTABLE
   4472     if( ALWAYS(pTabList->a[i].pTab) && IsVirtual(pTabList->a[i].pTab) ){
   4473       pWC->vmask |= ((Bitmask)1 << i);
   4474     }
   4475 #endif
   4476   }
   4477 #ifndef NDEBUG
   4478   {
   4479     Bitmask toTheLeft = 0;
   4480     for(i=0; i<pTabList->nSrc; i++){
   4481       Bitmask m = getMask(pMaskSet, pTabList->a[i].iCursor);
   4482       assert( (m-1)==toTheLeft );
   4483       toTheLeft |= m;
   4484     }
   4485   }
   4486 #endif
   4487 
   4488   /* Analyze all of the subexpressions.  Note that exprAnalyze() might
   4489   ** add new virtual terms onto the end of the WHERE clause.  We do not
   4490   ** want to analyze these virtual terms, so start analyzing at the end
   4491   ** and work forward so that the added virtual terms are never processed.
   4492   */
   4493   exprAnalyzeAll(pTabList, pWC);
   4494   if( db->mallocFailed ){
   4495     goto whereBeginError;
   4496   }
   4497 
   4498   /* Chose the best index to use for each table in the FROM clause.
   4499   **
   4500   ** This loop fills in the following fields:
   4501   **
   4502   **   pWInfo->a[].pIdx      The index to use for this level of the loop.
   4503   **   pWInfo->a[].wsFlags   WHERE_xxx flags associated with pIdx
   4504   **   pWInfo->a[].nEq       The number of == and IN constraints
   4505   **   pWInfo->a[].iFrom     Which term of the FROM clause is being coded
   4506   **   pWInfo->a[].iTabCur   The VDBE cursor for the database table
   4507   **   pWInfo->a[].iIdxCur   The VDBE cursor for the index
   4508   **   pWInfo->a[].pTerm     When wsFlags==WO_OR, the OR-clause term
   4509   **
   4510   ** This loop also figures out the nesting order of tables in the FROM
   4511   ** clause.
   4512   */
   4513   notReady = ~(Bitmask)0;
   4514   andFlags = ~0;
   4515   WHERETRACE(("*** Optimizer Start ***\n"));
   4516   for(i=iFrom=0, pLevel=pWInfo->a; i<nTabList; i++, pLevel++){
   4517     WhereCost bestPlan;         /* Most efficient plan seen so far */
   4518     Index *pIdx;                /* Index for FROM table at pTabItem */
   4519     int j;                      /* For looping over FROM tables */
   4520     int bestJ = -1;             /* The value of j */
   4521     Bitmask m;                  /* Bitmask value for j or bestJ */
   4522     int isOptimal;              /* Iterator for optimal/non-optimal search */
   4523     int nUnconstrained;         /* Number tables without INDEXED BY */
   4524     Bitmask notIndexed;         /* Mask of tables that cannot use an index */
   4525 
   4526     memset(&bestPlan, 0, sizeof(bestPlan));
   4527     bestPlan.rCost = SQLITE_BIG_DBL;
   4528     WHERETRACE(("*** Begin search for loop %d ***\n", i));
   4529 
   4530     /* Loop through the remaining entries in the FROM clause to find the
   4531     ** next nested loop. The loop tests all FROM clause entries
   4532     ** either once or twice.
   4533     **
   4534     ** The first test is always performed if there are two or more entries
   4535     ** remaining and never performed if there is only one FROM clause entry
   4536     ** to choose from.  The first test looks for an "optimal" scan.  In
   4537     ** this context an optimal scan is one that uses the same strategy
   4538     ** for the given FROM clause entry as would be selected if the entry
   4539     ** were used as the innermost nested loop.  In other words, a table
   4540     ** is chosen such that the cost of running that table cannot be reduced
   4541     ** by waiting for other tables to run first.  This "optimal" test works
   4542     ** by first assuming that the FROM clause is on the inner loop and finding
   4543     ** its query plan, then checking to see if that query plan uses any
   4544     ** other FROM clause terms that are notReady.  If no notReady terms are
   4545     ** used then the "optimal" query plan works.
   4546     **
   4547     ** Note that the WhereCost.nRow parameter for an optimal scan might
   4548     ** not be as small as it would be if the table really were the innermost
   4549     ** join.  The nRow value can be reduced by WHERE clause constraints
   4550     ** that do not use indices.  But this nRow reduction only happens if the
   4551     ** table really is the innermost join.
   4552     **
   4553     ** The second loop iteration is only performed if no optimal scan
   4554     ** strategies were found by the first iteration. This second iteration
   4555     ** is used to search for the lowest cost scan overall.
   4556     **
   4557     ** Previous versions of SQLite performed only the second iteration -
   4558     ** the next outermost loop was always that with the lowest overall
   4559     ** cost. However, this meant that SQLite could select the wrong plan
   4560     ** for scripts such as the following:
   4561     **
   4562     **   CREATE TABLE t1(a, b);
   4563     **   CREATE TABLE t2(c, d);
   4564     **   SELECT * FROM t2, t1 WHERE t2.rowid = t1.a;
   4565     **
   4566     ** The best strategy is to iterate through table t1 first. However it
   4567     ** is not possible to determine this with a simple greedy algorithm.
   4568     ** Since the cost of a linear scan through table t2 is the same
   4569     ** as the cost of a linear scan through table t1, a simple greedy
   4570     ** algorithm may choose to use t2 for the outer loop, which is a much
   4571     ** costlier approach.
   4572     */
   4573     nUnconstrained = 0;
   4574     notIndexed = 0;
   4575     for(isOptimal=(iFrom<nTabList-1); isOptimal>=0 && bestJ<0; isOptimal--){
   4576       Bitmask mask;             /* Mask of tables not yet ready */
   4577       for(j=iFrom, pTabItem=&pTabList->a[j]; j<nTabList; j++, pTabItem++){
   4578         int doNotReorder;    /* True if this table should not be reordered */
   4579         WhereCost sCost;     /* Cost information from best[Virtual]Index() */
   4580         ExprList *pOrderBy;  /* ORDER BY clause for index to optimize */
   4581 
   4582         doNotReorder =  (pTabItem->jointype & (JT_LEFT|JT_CROSS))!=0;
   4583         if( j!=iFrom && doNotReorder ) break;
   4584         m = getMask(pMaskSet, pTabItem->iCursor);
   4585         if( (m & notReady)==0 ){
   4586           if( j==iFrom ) iFrom++;
   4587           continue;
   4588         }
   4589         mask = (isOptimal ? m : notReady);
   4590         pOrderBy = ((i==0 && ppOrderBy )?*ppOrderBy:0);
   4591         if( pTabItem->pIndex==0 ) nUnconstrained++;
   4592 
   4593         WHERETRACE(("=== trying table %d with isOptimal=%d ===\n",
   4594                     j, isOptimal));
   4595         assert( pTabItem->pTab );
   4596 #ifndef SQLITE_OMIT_VIRTUALTABLE
   4597         if( IsVirtual(pTabItem->pTab) ){
   4598           sqlite3_index_info **pp = &pWInfo->a[j].pIdxInfo;
   4599           bestVirtualIndex(pParse, pWC, pTabItem, mask, notReady, pOrderBy,
   4600                            &sCost, pp);
   4601         }else
   4602 #endif
   4603         {
   4604           bestBtreeIndex(pParse, pWC, pTabItem, mask, notReady, pOrderBy,
   4605                          &sCost);
   4606         }
   4607         assert( isOptimal || (sCost.used&notReady)==0 );
   4608 
   4609         /* If an INDEXED BY clause is present, then the plan must use that
   4610         ** index if it uses any index at all */
   4611         assert( pTabItem->pIndex==0
   4612                   || (sCost.plan.wsFlags & WHERE_NOT_FULLSCAN)==0
   4613                   || sCost.plan.u.pIdx==pTabItem->pIndex );
   4614 
   4615         if( isOptimal && (sCost.plan.wsFlags & WHERE_NOT_FULLSCAN)==0 ){
   4616           notIndexed |= m;
   4617         }
   4618 
   4619         /* Conditions under which this table becomes the best so far:
   4620         **
   4621         **   (1) The table must not depend on other tables that have not
   4622         **       yet run.
   4623         **
   4624         **   (2) A full-table-scan plan cannot supercede indexed plan unless
   4625         **       the full-table-scan is an "optimal" plan as defined above.
   4626         **
   4627         **   (3) All tables have an INDEXED BY clause or this table lacks an
   4628         **       INDEXED BY clause or this table uses the specific
   4629         **       index specified by its INDEXED BY clause.  This rule ensures
   4630         **       that a best-so-far is always selected even if an impossible
   4631         **       combination of INDEXED BY clauses are given.  The error
   4632         **       will be detected and relayed back to the application later.
   4633         **       The NEVER() comes about because rule (2) above prevents
   4634         **       An indexable full-table-scan from reaching rule (3).
   4635         **
   4636         **   (4) The plan cost must be lower than prior plans or else the
   4637         **       cost must be the same and the number of rows must be lower.
   4638         */
   4639         if( (sCost.used&notReady)==0                       /* (1) */
   4640             && (bestJ<0 || (notIndexed&m)!=0               /* (2) */
   4641                 || (bestPlan.plan.wsFlags & WHERE_NOT_FULLSCAN)==0
   4642                 || (sCost.plan.wsFlags & WHERE_NOT_FULLSCAN)!=0)
   4643             && (nUnconstrained==0 || pTabItem->pIndex==0   /* (3) */
   4644                 || NEVER((sCost.plan.wsFlags & WHERE_NOT_FULLSCAN)!=0))
   4645             && (bestJ<0 || sCost.rCost<bestPlan.rCost      /* (4) */
   4646                 || (sCost.rCost<=bestPlan.rCost
   4647                  && sCost.plan.nRow<bestPlan.plan.nRow))
   4648         ){
   4649           WHERETRACE(("=== table %d is best so far"
   4650                       " with cost=%g and nRow=%g\n",
   4651                       j, sCost.rCost, sCost.plan.nRow));
   4652           bestPlan = sCost;
   4653           bestJ = j;
   4654         }
   4655         if( doNotReorder ) break;
   4656       }
   4657     }
   4658     assert( bestJ>=0 );
   4659     assert( notReady & getMask(pMaskSet, pTabList->a[bestJ].iCursor) );
   4660     WHERETRACE(("*** Optimizer selects table %d for loop %d"
   4661                 " with cost=%g and nRow=%g\n",
   4662                 bestJ, pLevel-pWInfo->a, bestPlan.rCost, bestPlan.plan.nRow));
   4663     if( (bestPlan.plan.wsFlags & WHERE_ORDERBY)!=0 ){
   4664       *ppOrderBy = 0;
   4665     }
   4666     andFlags &= bestPlan.plan.wsFlags;
   4667     pLevel->plan = bestPlan.plan;
   4668     testcase( bestPlan.plan.wsFlags & WHERE_INDEXED );
   4669     testcase( bestPlan.plan.wsFlags & WHERE_TEMP_INDEX );
   4670     if( bestPlan.plan.wsFlags & (WHERE_INDEXED|WHERE_TEMP_INDEX) ){
   4671       pLevel->iIdxCur = pParse->nTab++;
   4672     }else{
   4673       pLevel->iIdxCur = -1;
   4674     }
   4675     notReady &= ~getMask(pMaskSet, pTabList->a[bestJ].iCursor);
   4676     pLevel->iFrom = (u8)bestJ;
   4677     if( bestPlan.plan.nRow>=(double)1 ){
   4678       pParse->nQueryLoop *= bestPlan.plan.nRow;
   4679     }
   4680 
   4681     /* Check that if the table scanned by this loop iteration had an
   4682     ** INDEXED BY clause attached to it, that the named index is being
   4683     ** used for the scan. If not, then query compilation has failed.
   4684     ** Return an error.
   4685     */
   4686     pIdx = pTabList->a[bestJ].pIndex;
   4687     if( pIdx ){
   4688       if( (bestPlan.plan.wsFlags & WHERE_INDEXED)==0 ){
   4689         sqlite3ErrorMsg(pParse, "cannot use index: %s", pIdx->zName);
   4690         goto whereBeginError;
   4691       }else{
   4692         /* If an INDEXED BY clause is used, the bestIndex() function is
   4693         ** guaranteed to find the index specified in the INDEXED BY clause
   4694         ** if it find an index at all. */
   4695         assert( bestPlan.plan.u.pIdx==pIdx );
   4696       }
   4697     }
   4698   }
   4699   WHERETRACE(("*** Optimizer Finished ***\n"));
   4700   if( pParse->nErr || db->mallocFailed ){
   4701     goto whereBeginError;
   4702   }
   4703 
   4704   /* If the total query only selects a single row, then the ORDER BY
   4705   ** clause is irrelevant.
   4706   */
   4707   if( (andFlags & WHERE_UNIQUE)!=0 && ppOrderBy ){
   4708     *ppOrderBy = 0;
   4709   }
   4710 
   4711   /* If the caller is an UPDATE or DELETE statement that is requesting
   4712   ** to use a one-pass algorithm, determine if this is appropriate.
   4713   ** The one-pass algorithm only works if the WHERE clause constraints
   4714   ** the statement to update a single row.
   4715   */
   4716   assert( (wctrlFlags & WHERE_ONEPASS_DESIRED)==0 || pWInfo->nLevel==1 );
   4717   if( (wctrlFlags & WHERE_ONEPASS_DESIRED)!=0 && (andFlags & WHERE_UNIQUE)!=0 ){
   4718     pWInfo->okOnePass = 1;
   4719     pWInfo->a[0].plan.wsFlags &= ~WHERE_IDX_ONLY;
   4720   }
   4721 
   4722   /* Open all tables in the pTabList and any indices selected for
   4723   ** searching those tables.
   4724   */
   4725   sqlite3CodeVerifySchema(pParse, -1); /* Insert the cookie verifier Goto */
   4726   notReady = ~(Bitmask)0;
   4727   pWInfo->nRowOut = (double)1;
   4728   for(i=0, pLevel=pWInfo->a; i<nTabList; i++, pLevel++){
   4729     Table *pTab;     /* Table to open */
   4730     int iDb;         /* Index of database containing table/index */
   4731 
   4732     pTabItem = &pTabList->a[pLevel->iFrom];
   4733     pTab = pTabItem->pTab;
   4734     pLevel->iTabCur = pTabItem->iCursor;
   4735     pWInfo->nRowOut *= pLevel->plan.nRow;
   4736     iDb = sqlite3SchemaToIndex(db, pTab->pSchema);
   4737     if( (pTab->tabFlags & TF_Ephemeral)!=0 || pTab->pSelect ){
   4738       /* Do nothing */
   4739     }else
   4740 #ifndef SQLITE_OMIT_VIRTUALTABLE
   4741     if( (pLevel->plan.wsFlags & WHERE_VIRTUALTABLE)!=0 ){
   4742       const char *pVTab = (const char *)sqlite3GetVTable(db, pTab);
   4743       int iCur = pTabItem->iCursor;
   4744       sqlite3VdbeAddOp4(v, OP_VOpen, iCur, 0, 0, pVTab, P4_VTAB);
   4745     }else
   4746 #endif
   4747     if( (pLevel->plan.wsFlags & WHERE_IDX_ONLY)==0
   4748          && (wctrlFlags & WHERE_OMIT_OPEN)==0 ){
   4749       int op = pWInfo->okOnePass ? OP_OpenWrite : OP_OpenRead;
   4750       sqlite3OpenTable(pParse, pTabItem->iCursor, iDb, pTab, op);
   4751       testcase( pTab->nCol==BMS-1 );
   4752       testcase( pTab->nCol==BMS );
   4753       if( !pWInfo->okOnePass && pTab->nCol<BMS ){
   4754         Bitmask b = pTabItem->colUsed;
   4755         int n = 0;
   4756         for(; b; b=b>>1, n++){}
   4757         sqlite3VdbeChangeP4(v, sqlite3VdbeCurrentAddr(v)-1,
   4758                             SQLITE_INT_TO_PTR(n), P4_INT32);
   4759         assert( n<=pTab->nCol );
   4760       }
   4761     }else{
   4762       sqlite3TableLock(pParse, iDb, pTab->tnum, 0, pTab->zName);
   4763     }
   4764 #ifndef SQLITE_OMIT_AUTOMATIC_INDEX
   4765     if( (pLevel->plan.wsFlags & WHERE_TEMP_INDEX)!=0 ){
   4766       constructAutomaticIndex(pParse, pWC, pTabItem, notReady, pLevel);
   4767     }else
   4768 #endif
   4769     if( (pLevel->plan.wsFlags & WHERE_INDEXED)!=0 ){
   4770       Index *pIx = pLevel->plan.u.pIdx;
   4771       KeyInfo *pKey = sqlite3IndexKeyinfo(pParse, pIx);
   4772       int iIdxCur = pLevel->iIdxCur;
   4773       assert( pIx->pSchema==pTab->pSchema );
   4774       assert( iIdxCur>=0 );
   4775       sqlite3VdbeAddOp4(v, OP_OpenRead, iIdxCur, pIx->tnum, iDb,
   4776                         (char*)pKey, P4_KEYINFO_HANDOFF);
   4777       VdbeComment((v, "%s", pIx->zName));
   4778     }
   4779     sqlite3CodeVerifySchema(pParse, iDb);
   4780     notReady &= ~getMask(pWC->pMaskSet, pTabItem->iCursor);
   4781   }
   4782   pWInfo->iTop = sqlite3VdbeCurrentAddr(v);
   4783   if( db->mallocFailed ) goto whereBeginError;
   4784 
   4785   /* Generate the code to do the search.  Each iteration of the for
   4786   ** loop below generates code for a single nested loop of the VM
   4787   ** program.
   4788   */
   4789   notReady = ~(Bitmask)0;
   4790   for(i=0; i<nTabList; i++){
   4791     pLevel = &pWInfo->a[i];
   4792     explainOneScan(pParse, pTabList, pLevel, i, pLevel->iFrom, wctrlFlags);
   4793     notReady = codeOneLoopStart(pWInfo, i, wctrlFlags, notReady);
   4794     pWInfo->iContinue = pLevel->addrCont;
   4795   }
   4796 
   4797 #ifdef SQLITE_TEST  /* For testing and debugging use only */
   4798   /* Record in the query plan information about the current table
   4799   ** and the index used to access it (if any).  If the table itself
   4800   ** is not used, its name is just '{}'.  If no index is used
   4801   ** the index is listed as "{}".  If the primary key is used the
   4802   ** index name is '*'.
   4803   */
   4804   for(i=0; i<nTabList; i++){
   4805     char *z;
   4806     int n;
   4807     pLevel = &pWInfo->a[i];
   4808     pTabItem = &pTabList->a[pLevel->iFrom];
   4809     z = pTabItem->zAlias;
   4810     if( z==0 ) z = pTabItem->pTab->zName;
   4811     n = sqlite3Strlen30(z);
   4812     if( n+nQPlan < sizeof(sqlite3_query_plan)-10 ){
   4813       if( pLevel->plan.wsFlags & WHERE_IDX_ONLY ){
   4814         memcpy(&sqlite3_query_plan[nQPlan], "{}", 2);
   4815         nQPlan += 2;
   4816       }else{
   4817         memcpy(&sqlite3_query_plan[nQPlan], z, n);
   4818         nQPlan += n;
   4819       }
   4820       sqlite3_query_plan[nQPlan++] = ' ';
   4821     }
   4822     testcase( pLevel->plan.wsFlags & WHERE_ROWID_EQ );
   4823     testcase( pLevel->plan.wsFlags & WHERE_ROWID_RANGE );
   4824     if( pLevel->plan.wsFlags & (WHERE_ROWID_EQ|WHERE_ROWID_RANGE) ){
   4825       memcpy(&sqlite3_query_plan[nQPlan], "* ", 2);
   4826       nQPlan += 2;
   4827     }else if( (pLevel->plan.wsFlags & WHERE_INDEXED)!=0 ){
   4828       n = sqlite3Strlen30(pLevel->plan.u.pIdx->zName);
   4829       if( n+nQPlan < sizeof(sqlite3_query_plan)-2 ){
   4830         memcpy(&sqlite3_query_plan[nQPlan], pLevel->plan.u.pIdx->zName, n);
   4831         nQPlan += n;
   4832         sqlite3_query_plan[nQPlan++] = ' ';
   4833       }
   4834     }else{
   4835       memcpy(&sqlite3_query_plan[nQPlan], "{} ", 3);
   4836       nQPlan += 3;
   4837     }
   4838   }
   4839   while( nQPlan>0 && sqlite3_query_plan[nQPlan-1]==' ' ){
   4840     sqlite3_query_plan[--nQPlan] = 0;
   4841   }
   4842   sqlite3_query_plan[nQPlan] = 0;
   4843   nQPlan = 0;
   4844 #endif /* SQLITE_TEST // Testing and debugging use only */
   4845 
   4846   /* Record the continuation address in the WhereInfo structure.  Then
   4847   ** clean up and return.
   4848   */
   4849   return pWInfo;
   4850 
   4851   /* Jump here if malloc fails */
   4852 whereBeginError:
   4853   if( pWInfo ){
   4854     pParse->nQueryLoop = pWInfo->savedNQueryLoop;
   4855     whereInfoFree(db, pWInfo);
   4856   }
   4857   return 0;
   4858 }
   4859 
   4860 /*
   4861 ** Generate the end of the WHERE loop.  See comments on
   4862 ** sqlite3WhereBegin() for additional information.
   4863 */
   4864 void sqlite3WhereEnd(WhereInfo *pWInfo){
   4865   Parse *pParse = pWInfo->pParse;
   4866   Vdbe *v = pParse->pVdbe;
   4867   int i;
   4868   WhereLevel *pLevel;
   4869   SrcList *pTabList = pWInfo->pTabList;
   4870   sqlite3 *db = pParse->db;
   4871 
   4872   /* Generate loop termination code.
   4873   */
   4874   sqlite3ExprCacheClear(pParse);
   4875   for(i=pWInfo->nLevel-1; i>=0; i--){
   4876     pLevel = &pWInfo->a[i];
   4877     sqlite3VdbeResolveLabel(v, pLevel->addrCont);
   4878     if( pLevel->op!=OP_Noop ){
   4879       sqlite3VdbeAddOp2(v, pLevel->op, pLevel->p1, pLevel->p2);
   4880       sqlite3VdbeChangeP5(v, pLevel->p5);
   4881     }
   4882     if( pLevel->plan.wsFlags & WHERE_IN_ABLE && pLevel->u.in.nIn>0 ){
   4883       struct InLoop *pIn;
   4884       int j;
   4885       sqlite3VdbeResolveLabel(v, pLevel->addrNxt);
   4886       for(j=pLevel->u.in.nIn, pIn=&pLevel->u.in.aInLoop[j-1]; j>0; j--, pIn--){
   4887         sqlite3VdbeJumpHere(v, pIn->addrInTop+1);
   4888         sqlite3VdbeAddOp2(v, OP_Next, pIn->iCur, pIn->addrInTop);
   4889         sqlite3VdbeJumpHere(v, pIn->addrInTop-1);
   4890       }
   4891       sqlite3DbFree(db, pLevel->u.in.aInLoop);
   4892     }
   4893     sqlite3VdbeResolveLabel(v, pLevel->addrBrk);
   4894     if( pLevel->iLeftJoin ){
   4895       int addr;
   4896       addr = sqlite3VdbeAddOp1(v, OP_IfPos, pLevel->iLeftJoin);
   4897       assert( (pLevel->plan.wsFlags & WHERE_IDX_ONLY)==0
   4898            || (pLevel->plan.wsFlags & WHERE_INDEXED)!=0 );
   4899       if( (pLevel->plan.wsFlags & WHERE_IDX_ONLY)==0 ){
   4900         sqlite3VdbeAddOp1(v, OP_NullRow, pTabList->a[i].iCursor);
   4901       }
   4902       if( pLevel->iIdxCur>=0 ){
   4903         sqlite3VdbeAddOp1(v, OP_NullRow, pLevel->iIdxCur);
   4904       }
   4905       if( pLevel->op==OP_Return ){
   4906         sqlite3VdbeAddOp2(v, OP_Gosub, pLevel->p1, pLevel->addrFirst);
   4907       }else{
   4908         sqlite3VdbeAddOp2(v, OP_Goto, 0, pLevel->addrFirst);
   4909       }
   4910       sqlite3VdbeJumpHere(v, addr);
   4911     }
   4912   }
   4913 
   4914   /* The "break" point is here, just past the end of the outer loop.
   4915   ** Set it.
   4916   */
   4917   sqlite3VdbeResolveLabel(v, pWInfo->iBreak);
   4918 
   4919   /* Close all of the cursors that were opened by sqlite3WhereBegin.
   4920   */
   4921   assert( pWInfo->nLevel==1 || pWInfo->nLevel==pTabList->nSrc );
   4922   for(i=0, pLevel=pWInfo->a; i<pWInfo->nLevel; i++, pLevel++){
   4923     struct SrcList_item *pTabItem = &pTabList->a[pLevel->iFrom];
   4924     Table *pTab = pTabItem->pTab;
   4925     assert( pTab!=0 );
   4926     if( (pTab->tabFlags & TF_Ephemeral)==0
   4927      && pTab->pSelect==0
   4928      && (pWInfo->wctrlFlags & WHERE_OMIT_CLOSE)==0
   4929     ){
   4930       int ws = pLevel->plan.wsFlags;
   4931       if( !pWInfo->okOnePass && (ws & WHERE_IDX_ONLY)==0 ){
   4932         sqlite3VdbeAddOp1(v, OP_Close, pTabItem->iCursor);
   4933       }
   4934       if( (ws & WHERE_INDEXED)!=0 && (ws & WHERE_TEMP_INDEX)==0 ){
   4935         sqlite3VdbeAddOp1(v, OP_Close, pLevel->iIdxCur);
   4936       }
   4937     }
   4938 
   4939     /* If this scan uses an index, make code substitutions to read data
   4940     ** from the index in preference to the table. Sometimes, this means
   4941     ** the table need never be read from. This is a performance boost,
   4942     ** as the vdbe level waits until the table is read before actually
   4943     ** seeking the table cursor to the record corresponding to the current
   4944     ** position in the index.
   4945     **
   4946     ** Calls to the code generator in between sqlite3WhereBegin and
   4947     ** sqlite3WhereEnd will have created code that references the table
   4948     ** directly.  This loop scans all that code looking for opcodes
   4949     ** that reference the table and converts them into opcodes that
   4950     ** reference the index.
   4951     */
   4952     if( (pLevel->plan.wsFlags & WHERE_INDEXED)!=0 && !db->mallocFailed){
   4953       int k, j, last;
   4954       VdbeOp *pOp;
   4955       Index *pIdx = pLevel->plan.u.pIdx;
   4956 
   4957       assert( pIdx!=0 );
   4958       pOp = sqlite3VdbeGetOp(v, pWInfo->iTop);
   4959       last = sqlite3VdbeCurrentAddr(v);
   4960       for(k=pWInfo->iTop; k<last; k++, pOp++){
   4961         if( pOp->p1!=pLevel->iTabCur ) continue;
   4962         if( pOp->opcode==OP_Column ){
   4963           for(j=0; j<pIdx->nColumn; j++){
   4964             if( pOp->p2==pIdx->aiColumn[j] ){
   4965               pOp->p2 = j;
   4966               pOp->p1 = pLevel->iIdxCur;
   4967               break;
   4968             }
   4969           }
   4970           assert( (pLevel->plan.wsFlags & WHERE_IDX_ONLY)==0
   4971                || j<pIdx->nColumn );
   4972         }else if( pOp->opcode==OP_Rowid ){
   4973           pOp->p1 = pLevel->iIdxCur;
   4974           pOp->opcode = OP_IdxRowid;
   4975         }
   4976       }
   4977     }
   4978   }
   4979 
   4980   /* Final cleanup
   4981   */
   4982   pParse->nQueryLoop = pWInfo->savedNQueryLoop;
   4983   whereInfoFree(db, pWInfo);
   4984   return;
   4985 }
   4986