src/whereexpr.c

   1 /*
   2 ** 2015-06-08
   3 **
   4 ** The author disclaims copyright to this source code.  In place of
   5 ** a legal notice, here is a blessing:
   6 **
   7 **    May you do good and not evil.
   8 **    May you find forgiveness for yourself and forgive others.
   9 **    May you share freely, never taking more than you give.
  10 **
  11 *************************************************************************
  12 ** This module contains C code that generates VDBE code used to process
  13 ** the WHERE clause of SQL statements.
  14 **
  15 ** This file was originally part of where.c but was split out to improve
  16 ** readability and editabiliity.  This file contains utility routines for
  17 ** analyzing Expr objects in the WHERE clause.
  18 */
  19 #include "sqliteInt.h"
  20 #include "whereInt.h"
  21
  22 /* Forward declarations */
  23 static void exprAnalyze(SrcList*, WhereClause*, int);
  24
  25 /*
  26 ** Deallocate all memory associated with a WhereOrInfo object.
  27 */
  28 static void whereOrInfoDelete(sqlite3 *db, WhereOrInfo *p){
  29   sqlite3WhereClauseClear(&p->wc);
  30   sqlite3DbFree(db, p);
  31 }
  32
  33 /*
  34 ** Deallocate all memory associated with a WhereAndInfo object.
  35 */
  36 static void whereAndInfoDelete(sqlite3 *db, WhereAndInfo *p){
  37   sqlite3WhereClauseClear(&p->wc);
  38   sqlite3DbFree(db, p);
  39 }
  40
  41 /*
  42 ** Add a single new WhereTerm entry to the WhereClause object pWC.
  43 ** The new WhereTerm object is constructed from Expr p and with wtFlags.
  44 ** The index in pWC->a[] of the new WhereTerm is returned on success.
  45 ** 0 is returned if the new WhereTerm could not be added due to a memory
  46 ** allocation error.  The memory allocation failure will be recorded in
  47 ** the db->mallocFailed flag so that higher-level functions can detect it.
  48 **
  49 ** This routine will increase the size of the pWC->a[] array as necessary.
  50 **
  51 ** If the wtFlags argument includes TERM_DYNAMIC, then responsibility
  52 ** for freeing the expression p is assumed by the WhereClause object pWC.
  53 ** This is true even if this routine fails to allocate a new WhereTerm.
  54 **
  55 ** WARNING:  This routine might reallocate the space used to store
  56 ** WhereTerms.  All pointers to WhereTerms should be invalidated after
  57 ** calling this routine.  Such pointers may be reinitialized by referencing
  58 ** the pWC->a[] array.
  59 */
  60 static int whereClauseInsert(WhereClause *pWC, Expr *p, u16 wtFlags){
  61   WhereTerm *pTerm;
  62   int idx;
  63   testcase( wtFlags & TERM_VIRTUAL );
  64   if( pWC->nTerm>=pWC->nSlot ){
  65     WhereTerm *pOld = pWC->a;
  66     sqlite3 *db = pWC->pWInfo->pParse->db;
  67     pWC->a = sqlite3DbMallocRawNN(db, sizeof(pWC->a[0])*pWC->nSlot*2 );
  68     if( pWC->a==0 ){
  69       if( wtFlags & TERM_DYNAMIC ){
  70         sqlite3ExprDelete(db, p);
  71       }
  72       pWC->a = pOld;
  73       return 0;
  74     }
  75     memcpy(pWC->a, pOld, sizeof(pWC->a[0])*pWC->nTerm);
  76     if( pOld!=pWC->aStatic ){
  77       sqlite3DbFree(db, pOld);
  78     }
  79     pWC->nSlot = sqlite3DbMallocSize(db, pWC->a)/sizeof(pWC->a[0]);
  80   }
  81   pTerm = &pWC->a[idx = pWC->nTerm++];
  82   if( p && ExprHasProperty(p, EP_Unlikely) ){
  83     pTerm->truthProb = sqlite3LogEst(p->iTable) - 270;
  84   }else{
  85     pTerm->truthProb = 1;
  86   }
  87   pTerm->pExpr = sqlite3ExprSkipCollate(p);
  88   pTerm->wtFlags = wtFlags;
  89   pTerm->pWC = pWC;
  90   pTerm->iParent = -1;
  91   memset(&pTerm->eOperator, 0,
  92          sizeof(WhereTerm) - offsetof(WhereTerm,eOperator));
  93   return idx;
  94 }
  95
  96 /*
  97 ** Return TRUE if the given operator is one of the operators that is
  98 ** allowed for an indexable WHERE clause term.  The allowed operators are
  99 ** "=", "<", ">", "<=", ">=", "IN", "IS", and "IS NULL"
 100 */
 101 static int allowedOp(int op){
 102   assert( TK_GT>TK_EQ && TK_GT<TK_GE );
 103   assert( TK_LT>TK_EQ && TK_LT<TK_GE );
 104   assert( TK_LE>TK_EQ && TK_LE<TK_GE );
 105   assert( TK_GE==TK_EQ+4 );
 106   return op==TK_IN || (op>=TK_EQ && op<=TK_GE) || op==TK_ISNULL || op==TK_IS;
 107 }
 108
 109 /*
 110 ** Commute a comparison operator.  Expressions of the form "X op Y"
 111 ** are converted into "Y op X".
 112 **
 113 ** If left/right precedence rules come into play when determining the
 114 ** collating sequence, then COLLATE operators are adjusted to ensure
 115 ** that the collating sequence does not change.  For example:
 116 ** "Y collate NOCASE op X" becomes "X op Y" because any collation sequence on
 117 ** the left hand side of a comparison overrides any collation sequence
 118 ** attached to the right. For the same reason the EP_Collate flag
 119 ** is not commuted.
 120 */
 121 static void exprCommute(Parse *pParse, Expr *pExpr){
 122   u16 expRight = (pExpr->pRight->flags & EP_Collate);
 123   u16 expLeft = (pExpr->pLeft->flags & EP_Collate);
 124   assert( allowedOp(pExpr->op) && pExpr->op!=TK_IN );
 125   if( expRight==expLeft ){
 126     /* Either X and Y both have COLLATE operator or neither do */
 127     if( expRight ){
 128       /* Both X and Y have COLLATE operators.  Make sure X is always
 129       ** used by clearing the EP_Collate flag from Y. */
 130       pExpr->pRight->flags &= ~EP_Collate;
 131     }else if( sqlite3ExprCollSeq(pParse, pExpr->pLeft)!=0 ){
 132       /* Neither X nor Y have COLLATE operators, but X has a non-default
 133       ** collating sequence.  So add the EP_Collate marker on X to cause
 134       ** it to be searched first. */
 135       pExpr->pLeft->flags |= EP_Collate;
 136     }
 137   }
 138   SWAP(Expr*,pExpr->pRight,pExpr->pLeft);
 139   if( pExpr->op>=TK_GT ){
 140     assert( TK_LT==TK_GT+2 );
 141     assert( TK_GE==TK_LE+2 );
 142     assert( TK_GT>TK_EQ );
 143     assert( TK_GT<TK_LE );
 144     assert( pExpr->op>=TK_GT && pExpr->op<=TK_GE );
 145     pExpr->op = ((pExpr->op-TK_GT)^2)+TK_GT;
 146   }
 147 }
 148
 149 /*
 150 ** Translate from TK_xx operator to WO_xx bitmask.
 151 */
 152 static u16 operatorMask(int op){
 153   u16 c;
 154   assert( allowedOp(op) );
 155   if( op==TK_IN ){
 156     c = WO_IN;
 157   }else if( op==TK_ISNULL ){
 158     c = WO_ISNULL;
 159   }else if( op==TK_IS ){
 160     c = WO_IS;
 161   }else{
 162     assert( (WO_EQ<<(op-TK_EQ)) < 0x7fff );
 163     c = (u16)(WO_EQ<<(op-TK_EQ));
 164   }
 165   assert( op!=TK_ISNULL || c==WO_ISNULL );
 166   assert( op!=TK_IN || c==WO_IN );
 167   assert( op!=TK_EQ || c==WO_EQ );
 168   assert( op!=TK_LT || c==WO_LT );
 169   assert( op!=TK_LE || c==WO_LE );
 170   assert( op!=TK_GT || c==WO_GT );
 171   assert( op!=TK_GE || c==WO_GE );
 172   assert( op!=TK_IS || c==WO_IS );
 173   return c;
 174 }
 175
 176
 177 #ifndef SQLITE_OMIT_LIKE_OPTIMIZATION
 178 /*
 179 ** Check to see if the given expression is a LIKE or GLOB operator that
 180 ** can be optimized using inequality constraints.  Return TRUE if it is
 181 ** so and false if not.
 182 **
 183 ** In order for the operator to be optimizible, the RHS must be a string
 184 ** literal that does not begin with a wildcard.  The LHS must be a column
 185 ** that may only be NULL, a string, or a BLOB, never a number. (This means
 186 ** that virtual tables cannot participate in the LIKE optimization.)  The
 187 ** collating sequence for the column on the LHS must be appropriate for
 188 ** the operator.
 189 */
 190 static int isLikeOrGlob(
 191   Parse *pParse,    /* Parsing and code generating context */
 192   Expr *pExpr,      /* Test this expression */
 193   Expr **ppPrefix,  /* Pointer to TK_STRING expression with pattern prefix */
 194   int *pisComplete, /* True if the only wildcard is % in the last character */
 195   int *pnoCase      /* True if uppercase is equivalent to lowercase */
 196 ){
 197   const u8 *z = 0;         /* String on RHS of LIKE operator */
 198   Expr *pRight, *pLeft;      /* Right and left size of LIKE operator */
 199   ExprList *pList;           /* List of operands to the LIKE operator */
 200   int c;                     /* One character in z[] */
 201   int cnt;                   /* Number of non-wildcard prefix characters */
 202   char wc[4];                /* Wildcard characters */
 203   sqlite3 *db = pParse->db;  /* Database connection */
 204   sqlite3_value *pVal = 0;
 205   int op;                    /* Opcode of pRight */
 206   int rc;                    /* Result code to return */
 207
 208   if( !sqlite3IsLikeFunction(db, pExpr, pnoCase, wc) ){
 209     return 0;
 210   }
 211 #ifdef SQLITE_EBCDIC
 212   if( *pnoCase ) return 0;
 213 #endif
 214   pList = pExpr->x.pList;
 215   pLeft = pList->a[1].pExpr;
 216
 217   pRight = sqlite3ExprSkipCollate(pList->a[0].pExpr);
 218   op = pRight->op;
 219   if( op==TK_VARIABLE && (db->flags & SQLITE_EnableQPSG)==0 ){
 220     Vdbe *pReprepare = pParse->pReprepare;
 221     int iCol = pRight->iColumn;
 222     pVal = sqlite3VdbeGetBoundValue(pReprepare, iCol, SQLITE_AFF_BLOB);
 223     if( pVal && sqlite3_value_type(pVal)==SQLITE_TEXT ){
 224       z = sqlite3_value_text(pVal);
 225     }
 226     sqlite3VdbeSetVarmask(pParse->pVdbe, iCol);
 227     assert( pRight->op==TK_VARIABLE || pRight->op==TK_REGISTER );
 228   }else if( op==TK_STRING ){
 229     z = (u8*)pRight->u.zToken;
 230   }
 231   if( z ){
 232
 233     /* If the RHS begins with a digit or a minus sign, then the LHS must
 234     ** be an ordinary column (not a virtual table column) with TEXT affinity.
 235     ** Otherwise the LHS might be numeric and "lhs >= rhs" would be false
 236     ** even though "lhs LIKE rhs" is true.  But if the RHS does not start
 237     ** with a digit or '-', then "lhs LIKE rhs" will always be false if
 238     ** the LHS is numeric and so the optimization still works.
 239     */
 240     if( sqlite3Isdigit(z[0]) || z[0]=='-' ){
 241       if( pLeft->op!=TK_COLUMN
 242        || sqlite3ExprAffinity(pLeft)!=SQLITE_AFF_TEXT
 243        || IsVirtual(pLeft->pTab)  /* Value might be numeric */
 244       ){
 245         sqlite3ValueFree(pVal);
 246         return 0;
 247       }
 248     }
 249
 250     /* Count the number of prefix characters prior to the first wildcard */
 251     cnt = 0;
 252     while( (c=z[cnt])!=0 && c!=wc[0] && c!=wc[1] && c!=wc[2] ){
 253       cnt++;
 254       if( c==wc[3] && z[cnt]!=0 ) cnt++;
 255     }
 256
 257     /* The optimization is possible only if (1) the pattern does not begin
 258     ** with a wildcard and if (2) the non-wildcard prefix does not end with
 259     ** an (illegal 0xff) character.  The second condition is necessary so
 260     ** that we can increment the prefix key to find an upper bound for the
 261     ** range search.
 262     */
 263     if( cnt!=0 && 255!=(u8)z[cnt-1] ){
 264       Expr *pPrefix;
 265
 266       /* A "complete" match if the pattern ends with "*" or "%" */
 267       *pisComplete = c==wc[0] && z[cnt+1]==0;
 268
 269       /* Get the pattern prefix.  Remove all escapes from the prefix. */
 270       pPrefix = sqlite3Expr(db, TK_STRING, (char*)z);
 271       if( pPrefix ){
 272         int iFrom, iTo;
 273         char *zNew = pPrefix->u.zToken;
 274         zNew[cnt] = 0;
 275         for(iFrom=iTo=0; iFrom<cnt; iFrom++){
 276           if( zNew[iFrom]==wc[3] ) iFrom++;
 277           zNew[iTo++] = zNew[iFrom];
 278         }
 279         zNew[iTo] = 0;
 280       }
 281       *ppPrefix = pPrefix;
 282
 283       /* If the RHS pattern is a bound parameter, make arrangements to
 284       ** reprepare the statement when that parameter is rebound */
 285       if( op==TK_VARIABLE ){
 286         Vdbe *v = pParse->pVdbe;
 287         sqlite3VdbeSetVarmask(v, pRight->iColumn);
 288         if( *pisComplete && pRight->u.zToken[1] ){
 289           /* If the rhs of the LIKE expression is a variable, and the current
 290           ** value of the variable means there is no need to invoke the LIKE
 291           ** function, then no OP_Variable will be added to the program.
 292           ** This causes problems for the sqlite3_bind_parameter_name()
 293           ** API. To work around them, add a dummy OP_Variable here.
 294           */
 295           int r1 = sqlite3GetTempReg(pParse);
 296           sqlite3ExprCodeTarget(pParse, pRight, r1);
 297           sqlite3VdbeChangeP3(v, sqlite3VdbeCurrentAddr(v)-1, 0);
 298           sqlite3ReleaseTempReg(pParse, r1);
 299         }
 300       }
 301     }else{
 302       z = 0;
 303     }
 304   }
 305
 306   rc = (z!=0);
 307   sqlite3ValueFree(pVal);
 308   return rc;
 309 }
 310 #endif /* SQLITE_OMIT_LIKE_OPTIMIZATION */
 311
 312
 313 #ifndef SQLITE_OMIT_VIRTUALTABLE
 314 /*
 315 ** Check to see if the pExpr expression is a form that needs to be passed
 316 ** to the xBestIndex method of virtual tables.  Forms of interest include:
 317 **
 318 **          Expression                   Virtual Table Operator
 319 **          -----------------------      ---------------------------------
 320 **      1.  column MATCH expr            SQLITE_INDEX_CONSTRAINT_MATCH
 321 **      2.  column GLOB expr             SQLITE_INDEX_CONSTRAINT_GLOB
 322 **      3.  column LIKE expr             SQLITE_INDEX_CONSTRAINT_LIKE
 323 **      4.  column REGEXP expr           SQLITE_INDEX_CONSTRAINT_REGEXP
 324 **      5.  column != expr               SQLITE_INDEX_CONSTRAINT_NE
 325 **      6.  expr != column               SQLITE_INDEX_CONSTRAINT_NE
 326 **      7.  column IS NOT expr           SQLITE_INDEX_CONSTRAINT_ISNOT
 327 **      8.  expr IS NOT column           SQLITE_INDEX_CONSTRAINT_ISNOT
 328 **      9.  column IS NOT NULL           SQLITE_INDEX_CONSTRAINT_ISNOTNULL
 329 **
 330 ** In every case, "column" must be a column of a virtual table.  If there
 331 ** is a match, set *ppLeft to the "column" expression, set *ppRight to the
 332 ** "expr" expression (even though in forms (6) and (8) the column is on the
 333 ** right and the expression is on the left).  Also set *peOp2 to the
 334 ** appropriate virtual table operator.  The return value is 1 or 2 if there
 335 ** is a match.  The usual return is 1, but if the RHS is also a column
 336 ** of virtual table in forms (5) or (7) then return 2.
 337 **
 338 ** If the expression matches none of the patterns above, return 0.
 339 */
 340 static int isAuxiliaryVtabOperator(
 341   Expr *pExpr,                    /* Test this expression */
 342   unsigned char *peOp2,           /* OUT: 0 for MATCH, or else an op2 value */
 343   Expr **ppLeft,                  /* Column expression to left of MATCH/op2 */
 344   Expr **ppRight                  /* Expression to left of MATCH/op2 */
 345 ){
 346   if( pExpr->op==TK_FUNCTION ){
 347     static const struct Op2 {
 348       const char *zOp;
 349       unsigned char eOp2;
 350     } aOp[] = {
 351       { "match",  SQLITE_INDEX_CONSTRAINT_MATCH },
 352       { "glob",   SQLITE_INDEX_CONSTRAINT_GLOB },
 353       { "like",   SQLITE_INDEX_CONSTRAINT_LIKE },
 354       { "regexp", SQLITE_INDEX_CONSTRAINT_REGEXP }
 355     };
 356     ExprList *pList;
 357     Expr *pCol;                     /* Column reference */
 358     int i;
 359
 360     pList = pExpr->x.pList;
 361     if( pList==0 || pList->nExpr!=2 ){
 362       return 0;
 363     }
 364     pCol = pList->a[1].pExpr;
 365     if( pCol->op!=TK_COLUMN || !IsVirtual(pCol->pTab) ){
 366       return 0;
 367     }
 368     for(i=0; i<ArraySize(aOp); i++){
 369       if( sqlite3StrICmp(pExpr->u.zToken, aOp[i].zOp)==0 ){
 370         *peOp2 = aOp[i].eOp2;
 371         *ppRight = pList->a[0].pExpr;
 372         *ppLeft = pCol;
 373         return 1;
 374       }
 375     }
 376   }else if( pExpr->op==TK_NE || pExpr->op==TK_ISNOT || pExpr->op==TK_NOTNULL ){
 377     int res = 0;
 378     Expr *pLeft = pExpr->pLeft;
 379     Expr *pRight = pExpr->pRight;
 380     if( pLeft->op==TK_COLUMN && IsVirtual(pLeft->pTab) ){
 381       res++;
 382     }
 383     if( pRight && pRight->op==TK_COLUMN && IsVirtual(pRight->pTab) ){
 384       res++;
 385       SWAP(Expr*, pLeft, pRight);
 386     }
 387     *ppLeft = pLeft;
 388     *ppRight = pRight;
 389     if( pExpr->op==TK_NE ) *peOp2 = SQLITE_INDEX_CONSTRAINT_NE;
 390     if( pExpr->op==TK_ISNOT ) *peOp2 = SQLITE_INDEX_CONSTRAINT_ISNOT;
 391     if( pExpr->op==TK_NOTNULL ) *peOp2 = SQLITE_INDEX_CONSTRAINT_ISNOTNULL;
 392     return res;
 393   }
 394   return 0;
 395 }
 396 #endif /* SQLITE_OMIT_VIRTUALTABLE */
 397
 398 /*
 399 ** If the pBase expression originated in the ON or USING clause of
 400 ** a join, then transfer the appropriate markings over to derived.
 401 */
 402 static void transferJoinMarkings(Expr *pDerived, Expr *pBase){
 403   if( pDerived ){
 404     pDerived->flags |= pBase->flags & EP_FromJoin;
 405     pDerived->iRightJoinTable = pBase->iRightJoinTable;
 406   }
 407 }
 408
 409 /*
 410 ** Mark term iChild as being a child of term iParent
 411 */
 412 static void markTermAsChild(WhereClause *pWC, int iChild, int iParent){
 413   pWC->a[iChild].iParent = iParent;
 414   pWC->a[iChild].truthProb = pWC->a[iParent].truthProb;
 415   pWC->a[iParent].nChild++;
 416 }
 417
 418 /*
 419 ** Return the N-th AND-connected subterm of pTerm.  Or if pTerm is not
 420 ** a conjunction, then return just pTerm when N==0.  If N is exceeds
 421 ** the number of available subterms, return NULL.
 422 */
 423 static WhereTerm *whereNthSubterm(WhereTerm *pTerm, int N){
 424   if( pTerm->eOperator!=WO_AND ){
 425     return N==0 ? pTerm : 0;
 426   }
 427   if( N<pTerm->u.pAndInfo->wc.nTerm ){
 428     return &pTerm->u.pAndInfo->wc.a[N];
 429   }
 430   return 0;
 431 }
 432
 433 /*
 434 ** Subterms pOne and pTwo are contained within WHERE clause pWC.  The
 435 ** two subterms are in disjunction - they are OR-ed together.
 436 **
 437 ** If these two terms are both of the form:  "A op B" with the same
 438 ** A and B values but different operators and if the operators are
 439 ** compatible (if one is = and the other is <, for example) then
 440 ** add a new virtual AND term to pWC that is the combination of the
 441 ** two.
 442 **
 443 ** Some examples:
 444 **
 445 **    x<y OR x=y    -->     x<=y
 446 **    x=y OR x=y    -->     x=y
 447 **    x<=y OR x<y   -->     x<=y
 448 **
 449 ** The following is NOT generated:
 450 **
 451 **    x<y OR x>y    -->     x!=y
 452 */
 453 static void whereCombineDisjuncts(
 454   SrcList *pSrc,         /* the FROM clause */
 455   WhereClause *pWC,      /* The complete WHERE clause */
 456   WhereTerm *pOne,       /* First disjunct */
 457   WhereTerm *pTwo        /* Second disjunct */
 458 ){
 459   u16 eOp = pOne->eOperator | pTwo->eOperator;
 460   sqlite3 *db;           /* Database connection (for malloc) */
 461   Expr *pNew;            /* New virtual expression */
 462   int op;                /* Operator for the combined expression */
 463   int idxNew;            /* Index in pWC of the next virtual term */
 464
 465   if( (pOne->eOperator & (WO_EQ|WO_LT|WO_LE|WO_GT|WO_GE))==0 ) return;
 466   if( (pTwo->eOperator & (WO_EQ|WO_LT|WO_LE|WO_GT|WO_GE))==0 ) return;
 467   if( (eOp & (WO_EQ|WO_LT|WO_LE))!=eOp
 468    && (eOp & (WO_EQ|WO_GT|WO_GE))!=eOp ) return;
 469   assert( pOne->pExpr->pLeft!=0 && pOne->pExpr->pRight!=0 );
 470   assert( pTwo->pExpr->pLeft!=0 && pTwo->pExpr->pRight!=0 );
 471   if( sqlite3ExprCompare(0,pOne->pExpr->pLeft, pTwo->pExpr->pLeft, -1) ) return;
 472   if( sqlite3ExprCompare(0,pOne->pExpr->pRight, pTwo->pExpr->pRight,-1) )return;
 473   /* If we reach this point, it means the two subterms can be combined */
 474   if( (eOp & (eOp-1))!=0 ){
 475     if( eOp & (WO_LT|WO_LE) ){
 476       eOp = WO_LE;
 477     }else{
 478       assert( eOp & (WO_GT|WO_GE) );
 479       eOp = WO_GE;
 480     }
 481   }
 482   db = pWC->pWInfo->pParse->db;
 483   pNew = sqlite3ExprDup(db, pOne->pExpr, 0);
 484   if( pNew==0 ) return;
 485   for(op=TK_EQ; eOp!=(WO_EQ<<(op-TK_EQ)); op++){ assert( op<TK_GE ); }
 486   pNew->op = op;
 487   idxNew = whereClauseInsert(pWC, pNew, TERM_VIRTUAL|TERM_DYNAMIC);
 488   exprAnalyze(pSrc, pWC, idxNew);
 489 }
 490
 491 #if !defined(SQLITE_OMIT_OR_OPTIMIZATION) && !defined(SQLITE_OMIT_SUBQUERY)
 492 /*
 493 ** Analyze a term that consists of two or more OR-connected
 494 ** subterms.  So in:
 495 **
 496 **     ... WHERE  (a=5) AND (b=7 OR c=9 OR d=13) AND (d=13)
 497 **                          ^^^^^^^^^^^^^^^^^^^^
 498 **
 499 ** This routine analyzes terms such as the middle term in the above example.
 500 ** A WhereOrTerm object is computed and attached to the term under
 501 ** analysis, regardless of the outcome of the analysis.  Hence:
 502 **
 503 **     WhereTerm.wtFlags   |=  TERM_ORINFO
 504 **     WhereTerm.u.pOrInfo  =  a dynamically allocated WhereOrTerm object
 505 **
 506 ** The term being analyzed must have two or more of OR-connected subterms.
 507 ** A single subterm might be a set of AND-connected sub-subterms.
 508 ** Examples of terms under analysis:
 509 **
 510 **     (A)     t1.x=t2.y OR t1.x=t2.z OR t1.y=15 OR t1.z=t3.a+5
 511 **     (B)     x=expr1 OR expr2=x OR x=expr3
 512 **     (C)     t1.x=t2.y OR (t1.x=t2.z AND t1.y=15)
 513 **     (D)     x=expr1 OR (y>11 AND y<22 AND z LIKE '*hello*')
 514 **     (E)     (p.a=1 AND q.b=2 AND r.c=3) OR (p.x=4 AND q.y=5 AND r.z=6)
 515 **     (F)     x>A OR (x=A AND y>=B)
 516 **
 517 ** CASE 1:
 518 **
 519 ** If all subterms are of the form T.C=expr for some single column of C and
 520 ** a single table T (as shown in example B above) then create a new virtual
 521 ** term that is an equivalent IN expression.  In other words, if the term
 522 ** being analyzed is:
 523 **
 524 **      x = expr1  OR  expr2 = x  OR  x = expr3
 525 **
 526 ** then create a new virtual term like this:
 527 **
 528 **      x IN (expr1,expr2,expr3)
 529 **
 530 ** CASE 2:
 531 **
 532 ** If there are exactly two disjuncts and one side has x>A and the other side
 533 ** has x=A (for the same x and A) then add a new virtual conjunct term to the
 534 ** WHERE clause of the form "x>=A".  Example:
 535 **
 536 **      x>A OR (x=A AND y>B)    adds:    x>=A
 537 **
 538 ** The added conjunct can sometimes be helpful in query planning.
 539 **
 540 ** CASE 3:
 541 **
 542 ** If all subterms are indexable by a single table T, then set
 543 **
 544 **     WhereTerm.eOperator              =  WO_OR
 545 **     WhereTerm.u.pOrInfo->indexable  |=  the cursor number for table T
 546 **
 547 ** A subterm is "indexable" if it is of the form
 548 ** "T.C <op> <expr>" where C is any column of table T and
 549 ** <op> is one of "=", "<", "<=", ">", ">=", "IS NULL", or "IN".
 550 ** A subterm is also indexable if it is an AND of two or more
 551 ** subsubterms at least one of which is indexable.  Indexable AND
 552 ** subterms have their eOperator set to WO_AND and they have
 553 ** u.pAndInfo set to a dynamically allocated WhereAndTerm object.
 554 **
 555 ** From another point of view, "indexable" means that the subterm could
 556 ** potentially be used with an index if an appropriate index exists.
 557 ** This analysis does not consider whether or not the index exists; that
 558 ** is decided elsewhere.  This analysis only looks at whether subterms
 559 ** appropriate for indexing exist.
 560 **
 561 ** All examples A through E above satisfy case 3.  But if a term
 562 ** also satisfies case 1 (such as B) we know that the optimizer will
 563 ** always prefer case 1, so in that case we pretend that case 3 is not
 564 ** satisfied.
 565 **
 566 ** It might be the case that multiple tables are indexable.  For example,
 567 ** (E) above is indexable on tables P, Q, and R.
 568 **
 569 ** Terms that satisfy case 3 are candidates for lookup by using
 570 ** separate indices to find rowids for each subterm and composing
 571 ** the union of all rowids using a RowSet object.  This is similar
 572 ** to "bitmap indices" in other database engines.
 573 **
 574 ** OTHERWISE:
 575 **
 576 ** If none of cases 1, 2, or 3 apply, then leave the eOperator set to
 577 ** zero.  This term is not useful for search.
 578 */
 579 static void exprAnalyzeOrTerm(
 580   SrcList *pSrc,            /* the FROM clause */
 581   WhereClause *pWC,         /* the complete WHERE clause */
 582   int idxTerm               /* Index of the OR-term to be analyzed */
 583 ){
 584   WhereInfo *pWInfo = pWC->pWInfo;        /* WHERE clause processing context */
 585   Parse *pParse = pWInfo->pParse;         /* Parser context */
 586   sqlite3 *db = pParse->db;               /* Database connection */
 587   WhereTerm *pTerm = &pWC->a[idxTerm];    /* The term to be analyzed */
 588   Expr *pExpr = pTerm->pExpr;             /* The expression of the term */
 589   int i;                                  /* Loop counters */
 590   WhereClause *pOrWc;       /* Breakup of pTerm into subterms */
 591   WhereTerm *pOrTerm;       /* A Sub-term within the pOrWc */
 592   WhereOrInfo *pOrInfo;     /* Additional information associated with pTerm */
 593   Bitmask chngToIN;         /* Tables that might satisfy case 1 */
 594   Bitmask indexable;        /* Tables that are indexable, satisfying case 2 */
 595
 596   /*
 597   ** Break the OR clause into its separate subterms.  The subterms are
 598   ** stored in a WhereClause structure containing within the WhereOrInfo
 599   ** object that is attached to the original OR clause term.
 600   */
 601   assert( (pTerm->wtFlags & (TERM_DYNAMIC|TERM_ORINFO|TERM_ANDINFO))==0 );
 602   assert( pExpr->op==TK_OR );
 603   pTerm->u.pOrInfo = pOrInfo = sqlite3DbMallocZero(db, sizeof(*pOrInfo));
 604   if( pOrInfo==0 ) return;
 605   pTerm->wtFlags |= TERM_ORINFO;
 606   pOrWc = &pOrInfo->wc;
 607   memset(pOrWc->aStatic, 0, sizeof(pOrWc->aStatic));
 608   sqlite3WhereClauseInit(pOrWc, pWInfo);
 609   sqlite3WhereSplit(pOrWc, pExpr, TK_OR);
 610   sqlite3WhereExprAnalyze(pSrc, pOrWc);
 611   if( db->mallocFailed ) return;
 612   assert( pOrWc->nTerm>=2 );
 613
 614   /*
 615   ** Compute the set of tables that might satisfy cases 1 or 3.
 616   */
 617   indexable = ~(Bitmask)0;
 618   chngToIN = ~(Bitmask)0;
 619   for(i=pOrWc->nTerm-1, pOrTerm=pOrWc->a; i>=0 && indexable; i--, pOrTerm++){
 620     if( (pOrTerm->eOperator & WO_SINGLE)==0 ){
 621       WhereAndInfo *pAndInfo;
 622       assert( (pOrTerm->wtFlags & (TERM_ANDINFO|TERM_ORINFO))==0 );
 623       chngToIN = 0;
 624       pAndInfo = sqlite3DbMallocRawNN(db, sizeof(*pAndInfo));
 625       if( pAndInfo ){
 626         WhereClause *pAndWC;
 627         WhereTerm *pAndTerm;
 628         int j;
 629         Bitmask b = 0;
 630         pOrTerm->u.pAndInfo = pAndInfo;
 631         pOrTerm->wtFlags |= TERM_ANDINFO;
 632         pOrTerm->eOperator = WO_AND;
 633         pAndWC = &pAndInfo->wc;
 634         memset(pAndWC->aStatic, 0, sizeof(pAndWC->aStatic));
 635         sqlite3WhereClauseInit(pAndWC, pWC->pWInfo);
 636         sqlite3WhereSplit(pAndWC, pOrTerm->pExpr, TK_AND);
 637         sqlite3WhereExprAnalyze(pSrc, pAndWC);
 638         pAndWC->pOuter = pWC;
 639         if( !db->mallocFailed ){
 640           for(j=0, pAndTerm=pAndWC->a; j<pAndWC->nTerm; j++, pAndTerm++){
 641             assert( pAndTerm->pExpr );
 642             if( allowedOp(pAndTerm->pExpr->op)
 643              || pAndTerm->eOperator==WO_AUX
 644             ){
 645               b |= sqlite3WhereGetMask(&pWInfo->sMaskSet, pAndTerm->leftCursor);
 646             }
 647           }
 648         }
 649         indexable &= b;
 650       }
 651     }else if( pOrTerm->wtFlags & TERM_COPIED ){
 652       /* Skip this term for now.  We revisit it when we process the
 653       ** corresponding TERM_VIRTUAL term */
 654     }else{
 655       Bitmask b;
 656       b = sqlite3WhereGetMask(&pWInfo->sMaskSet, pOrTerm->leftCursor);
 657       if( pOrTerm->wtFlags & TERM_VIRTUAL ){
 658         WhereTerm *pOther = &pOrWc->a[pOrTerm->iParent];
 659         b |= sqlite3WhereGetMask(&pWInfo->sMaskSet, pOther->leftCursor);
 660       }
 661       indexable &= b;
 662       if( (pOrTerm->eOperator & WO_EQ)==0 ){
 663         chngToIN = 0;
 664       }else{
 665         chngToIN &= b;
 666       }
 667     }
 668   }
 669
 670   /*
 671   ** Record the set of tables that satisfy case 3.  The set might be
 672   ** empty.
 673   */
 674   pOrInfo->indexable = indexable;
 675   pTerm->eOperator = indexable==0 ? 0 : WO_OR;
 676
 677   /* For a two-way OR, attempt to implementation case 2.
 678   */
 679   if( indexable && pOrWc->nTerm==2 ){
 680     int iOne = 0;
 681     WhereTerm *pOne;
 682     while( (pOne = whereNthSubterm(&pOrWc->a[0],iOne++))!=0 ){
 683       int iTwo = 0;
 684       WhereTerm *pTwo;
 685       while( (pTwo = whereNthSubterm(&pOrWc->a[1],iTwo++))!=0 ){
 686         whereCombineDisjuncts(pSrc, pWC, pOne, pTwo);
 687       }
 688     }
 689   }
 690
 691   /*
 692   ** chngToIN holds a set of tables that *might* satisfy case 1.  But
 693   ** we have to do some additional checking to see if case 1 really
 694   ** is satisfied.
 695   **
 696   ** chngToIN will hold either 0, 1, or 2 bits.  The 0-bit case means
 697   ** that there is no possibility of transforming the OR clause into an
 698   ** IN operator because one or more terms in the OR clause contain
 699   ** something other than == on a column in the single table.  The 1-bit
 700   ** case means that every term of the OR clause is of the form
 701   ** "table.column=expr" for some single table.  The one bit that is set
 702   ** will correspond to the common table.  We still need to check to make
 703   ** sure the same column is used on all terms.  The 2-bit case is when
 704   ** the all terms are of the form "table1.column=table2.column".  It
 705   ** might be possible to form an IN operator with either table1.column
 706   ** or table2.column as the LHS if either is common to every term of
 707   ** the OR clause.
 708   **
 709   ** Note that terms of the form "table.column1=table.column2" (the
 710   ** same table on both sizes of the ==) cannot be optimized.
 711   */
 712   if( chngToIN ){
 713     int okToChngToIN = 0;     /* True if the conversion to IN is valid */
 714     int iColumn = -1;         /* Column index on lhs of IN operator */
 715     int iCursor = -1;         /* Table cursor common to all terms */
 716     int j = 0;                /* Loop counter */
 717
 718     /* Search for a table and column that appears on one side or the
 719     ** other of the == operator in every subterm.  That table and column
 720     ** will be recorded in iCursor and iColumn.  There might not be any
 721     ** such table and column.  Set okToChngToIN if an appropriate table
 722     ** and column is found but leave okToChngToIN false if not found.
 723     */
 724     for(j=0; j<2 && !okToChngToIN; j++){
 725       pOrTerm = pOrWc->a;
 726       for(i=pOrWc->nTerm-1; i>=0; i--, pOrTerm++){
 727         assert( pOrTerm->eOperator & WO_EQ );
 728         pOrTerm->wtFlags &= ~TERM_OR_OK;
 729         if( pOrTerm->leftCursor==iCursor ){
 730           /* This is the 2-bit case and we are on the second iteration and
 731           ** current term is from the first iteration.  So skip this term. */
 732           assert( j==1 );
 733           continue;
 734         }
 735         if( (chngToIN & sqlite3WhereGetMask(&pWInfo->sMaskSet,
 736                                             pOrTerm->leftCursor))==0 ){
 737           /* This term must be of the form t1.a==t2.b where t2 is in the
 738           ** chngToIN set but t1 is not.  This term will be either preceded
 739           ** or follwed by an inverted copy (t2.b==t1.a).  Skip this term
 740           ** and use its inversion. */
 741           testcase( pOrTerm->wtFlags & TERM_COPIED );
 742           testcase( pOrTerm->wtFlags & TERM_VIRTUAL );
 743           assert( pOrTerm->wtFlags & (TERM_COPIED|TERM_VIRTUAL) );
 744           continue;
 745         }
 746         iColumn = pOrTerm->u.leftColumn;
 747         iCursor = pOrTerm->leftCursor;
 748         break;
 749       }
 750       if( i<0 ){
 751         /* No candidate table+column was found.  This can only occur
 752         ** on the second iteration */
 753         assert( j==1 );
 754         assert( IsPowerOfTwo(chngToIN) );
 755         assert( chngToIN==sqlite3WhereGetMask(&pWInfo->sMaskSet, iCursor) );
 756         break;
 757       }
 758       testcase( j==1 );
 759
 760       /* We have found a candidate table and column.  Check to see if that
 761       ** table and column is common to every term in the OR clause */
 762       okToChngToIN = 1;
 763       for(; i>=0 && okToChngToIN; i--, pOrTerm++){
 764         assert( pOrTerm->eOperator & WO_EQ );
 765         if( pOrTerm->leftCursor!=iCursor ){
 766           pOrTerm->wtFlags &= ~TERM_OR_OK;
 767         }else if( pOrTerm->u.leftColumn!=iColumn ){
 768           okToChngToIN = 0;
 769         }else{
 770           int affLeft, affRight;
 771           /* If the right-hand side is also a column, then the affinities
 772           ** of both right and left sides must be such that no type
 773           ** conversions are required on the right.  (Ticket #2249)
 774           */
 775           affRight = sqlite3ExprAffinity(pOrTerm->pExpr->pRight);
 776           affLeft = sqlite3ExprAffinity(pOrTerm->pExpr->pLeft);
 777           if( affRight!=0 && affRight!=affLeft ){
 778             okToChngToIN = 0;
 779           }else{
 780             pOrTerm->wtFlags |= TERM_OR_OK;
 781           }
 782         }
 783       }
 784     }
 785
 786     /* At this point, okToChngToIN is true if original pTerm satisfies
 787     ** case 1.  In that case, construct a new virtual term that is
 788     ** pTerm converted into an IN operator.
 789     */
 790     if( okToChngToIN ){
 791       Expr *pDup;            /* A transient duplicate expression */
 792       ExprList *pList = 0;   /* The RHS of the IN operator */
 793       Expr *pLeft = 0;       /* The LHS of the IN operator */
 794       Expr *pNew;            /* The complete IN operator */
 795
 796       for(i=pOrWc->nTerm-1, pOrTerm=pOrWc->a; i>=0; i--, pOrTerm++){
 797         if( (pOrTerm->wtFlags & TERM_OR_OK)==0 ) continue;
 798         assert( pOrTerm->eOperator & WO_EQ );
 799         assert( pOrTerm->leftCursor==iCursor );
 800         assert( pOrTerm->u.leftColumn==iColumn );
 801         pDup = sqlite3ExprDup(db, pOrTerm->pExpr->pRight, 0);
 802         pList = sqlite3ExprListAppend(pWInfo->pParse, pList, pDup);
 803         pLeft = pOrTerm->pExpr->pLeft;
 804       }
 805       assert( pLeft!=0 );
 806       pDup = sqlite3ExprDup(db, pLeft, 0);
 807       pNew = sqlite3PExpr(pParse, TK_IN, pDup, 0);
 808       if( pNew ){
 809         int idxNew;
 810         transferJoinMarkings(pNew, pExpr);
 811         assert( !ExprHasProperty(pNew, EP_xIsSelect) );
 812         pNew->x.pList = pList;
 813         idxNew = whereClauseInsert(pWC, pNew, TERM_VIRTUAL|TERM_DYNAMIC);
 814         testcase( idxNew==0 );
 815         exprAnalyze(pSrc, pWC, idxNew);
 816         pTerm = &pWC->a[idxTerm];
 817         markTermAsChild(pWC, idxNew, idxTerm);
 818       }else{
 819         sqlite3ExprListDelete(db, pList);
 820       }
 821       pTerm->eOperator = WO_NOOP;  /* case 1 trumps case 3 */
 822     }
 823   }
 824 }
 825 #endif /* !SQLITE_OMIT_OR_OPTIMIZATION && !SQLITE_OMIT_SUBQUERY */
 826
 827 /*
 828 ** We already know that pExpr is a binary operator where both operands are
 829 ** column references.  This routine checks to see if pExpr is an equivalence
 830 ** relation:
 831 **   1.  The SQLITE_Transitive optimization must be enabled
 832 **   2.  Must be either an == or an IS operator
 833 **   3.  Not originating in the ON clause of an OUTER JOIN
 834 **   4.  The affinities of A and B must be compatible
 835 **   5a. Both operands use the same collating sequence OR
 836 **   5b. The overall collating sequence is BINARY
 837 ** If this routine returns TRUE, that means that the RHS can be substituted
 838 ** for the LHS anyplace else in the WHERE clause where the LHS column occurs.
 839 ** This is an optimization.  No harm comes from returning 0.  But if 1 is
 840 ** returned when it should not be, then incorrect answers might result.
 841 */
 842 static int termIsEquivalence(Parse *pParse, Expr *pExpr){
 843   char aff1, aff2;
 844   CollSeq *pColl;
 845   if( !OptimizationEnabled(pParse->db, SQLITE_Transitive) ) return 0;
 846   if( pExpr->op!=TK_EQ && pExpr->op!=TK_IS ) return 0;
 847   if( ExprHasProperty(pExpr, EP_FromJoin) ) return 0;
 848   aff1 = sqlite3ExprAffinity(pExpr->pLeft);
 849   aff2 = sqlite3ExprAffinity(pExpr->pRight);
 850   if( aff1!=aff2
 851    && (!sqlite3IsNumericAffinity(aff1) || !sqlite3IsNumericAffinity(aff2))
 852   ){
 853     return 0;
 854   }
 855   pColl = sqlite3BinaryCompareCollSeq(pParse, pExpr->pLeft, pExpr->pRight);
 856   if( pColl==0 || sqlite3StrICmp(pColl->zName, "BINARY")==0 ) return 1;
 857   return sqlite3ExprCollSeqMatch(pParse, pExpr->pLeft, pExpr->pRight);
 858 }
 859
 860 /*
 861 ** Recursively walk the expressions of a SELECT statement and generate
 862 ** a bitmask indicating which tables are used in that expression
 863 ** tree.
 864 */
 865 static Bitmask exprSelectUsage(WhereMaskSet *pMaskSet, Select *pS){
 866   Bitmask mask = 0;
 867   while( pS ){
 868     SrcList *pSrc = pS->pSrc;
 869     mask |= sqlite3WhereExprListUsage(pMaskSet, pS->pEList);
 870     mask |= sqlite3WhereExprListUsage(pMaskSet, pS->pGroupBy);
 871     mask |= sqlite3WhereExprListUsage(pMaskSet, pS->pOrderBy);
 872     mask |= sqlite3WhereExprUsage(pMaskSet, pS->pWhere);
 873     mask |= sqlite3WhereExprUsage(pMaskSet, pS->pHaving);
 874     if( ALWAYS(pSrc!=0) ){
 875       int i;
 876       for(i=0; i<pSrc->nSrc; i++){
 877         mask |= exprSelectUsage(pMaskSet, pSrc->a[i].pSelect);
 878         mask |= sqlite3WhereExprUsage(pMaskSet, pSrc->a[i].pOn);
 879         if( pSrc->a[i].fg.isTabFunc ){
 880           mask |= sqlite3WhereExprListUsage(pMaskSet, pSrc->a[i].u1.pFuncArg);
 881         }
 882       }
 883     }
 884     pS = pS->pPrior;
 885   }
 886   return mask;
 887 }
 888
 889 /*
 890 ** Expression pExpr is one operand of a comparison operator that might
 891 ** be useful for indexing.  This routine checks to see if pExpr appears
 892 ** in any index.  Return TRUE (1) if pExpr is an indexed term and return
 893 ** FALSE (0) if not.  If TRUE is returned, also set aiCurCol[0] to the cursor
 894 ** number of the table that is indexed and aiCurCol[1] to the column number
 895 ** of the column that is indexed, or XN_EXPR (-2) if an expression is being
 896 ** indexed.
 897 **
 898 ** If pExpr is a TK_COLUMN column reference, then this routine always returns
 899 ** true even if that particular column is not indexed, because the column
 900 ** might be added to an automatic index later.
 901 */
 902 static SQLITE_NOINLINE int exprMightBeIndexed2(
 903   SrcList *pFrom,        /* The FROM clause */
 904   Bitmask mPrereq,       /* Bitmask of FROM clause terms referenced by pExpr */
 905   int *aiCurCol,         /* Write the referenced table cursor and column here */
 906   Expr *pExpr            /* An operand of a comparison operator */
 907 ){
 908   Index *pIdx;
 909   int i;
 910   int iCur;
 911   for(i=0; mPrereq>1; i++, mPrereq>>=1){}
 912   iCur = pFrom->a[i].iCursor;
 913   for(pIdx=pFrom->a[i].pTab->pIndex; pIdx; pIdx=pIdx->pNext){
 914     if( pIdx->aColExpr==0 ) continue;
 915     for(i=0; i<pIdx->nKeyCol; i++){
 916       if( pIdx->aiColumn[i]!=XN_EXPR ) continue;
 917       if( sqlite3ExprCompareSkip(pExpr, pIdx->aColExpr->a[i].pExpr, iCur)==0 ){
 918         aiCurCol[0] = iCur;
 919         aiCurCol[1] = XN_EXPR;
 920         return 1;
 921       }
 922     }
 923   }
 924   return 0;
 925 }
 926 static int exprMightBeIndexed(
 927   SrcList *pFrom,        /* The FROM clause */
 928   Bitmask mPrereq,       /* Bitmask of FROM clause terms referenced by pExpr */
 929   int *aiCurCol,         /* Write the referenced table cursor & column here */
 930   Expr *pExpr,           /* An operand of a comparison operator */
 931   int op                 /* The specific comparison operator */
 932 ){
 933   /* If this expression is a vector to the left or right of a
 934   ** inequality constraint (>, <, >= or <=), perform the processing
 935   ** on the first element of the vector.  */
 936   assert( TK_GT+1==TK_LE && TK_GT+2==TK_LT && TK_GT+3==TK_GE );
 937   assert( TK_IS<TK_GE && TK_ISNULL<TK_GE && TK_IN<TK_GE );
 938   assert( op<=TK_GE );
 939   if( pExpr->op==TK_VECTOR && (op>=TK_GT && ALWAYS(op<=TK_GE)) ){
 940     pExpr = pExpr->x.pList->a[0].pExpr;
 941   }
 942
 943   if( pExpr->op==TK_COLUMN ){
 944     aiCurCol[0] = pExpr->iTable;
 945     aiCurCol[1] = pExpr->iColumn;
 946     return 1;
 947   }
 948   if( mPrereq==0 ) return 0;                 /* No table references */
 949   if( (mPrereq&(mPrereq-1))!=0 ) return 0;   /* Refs more than one table */
 950   return exprMightBeIndexed2(pFrom,mPrereq,aiCurCol,pExpr);
 951 }
 952
 953 /*
 954 ** The input to this routine is an WhereTerm structure with only the
 955 ** "pExpr" field filled in.  The job of this routine is to analyze the
 956 ** subexpression and populate all the other fields of the WhereTerm
 957 ** structure.
 958 **
 959 ** If the expression is of the form "<expr> <op> X" it gets commuted
 960 ** to the standard form of "X <op> <expr>".
 961 **
 962 ** If the expression is of the form "X <op> Y" where both X and Y are
 963 ** columns, then the original expression is unchanged and a new virtual
 964 ** term of the form "Y <op> X" is added to the WHERE clause and
 965 ** analyzed separately.  The original term is marked with TERM_COPIED
 966 ** and the new term is marked with TERM_DYNAMIC (because it's pExpr
 967 ** needs to be freed with the WhereClause) and TERM_VIRTUAL (because it
 968 ** is a commuted copy of a prior term.)  The original term has nChild=1
 969 ** and the copy has idxParent set to the index of the original term.
 970 */
 971 static void exprAnalyze(
 972   SrcList *pSrc,            /* the FROM clause */
 973   WhereClause *pWC,         /* the WHERE clause */
 974   int idxTerm               /* Index of the term to be analyzed */
 975 ){
 976   WhereInfo *pWInfo = pWC->pWInfo; /* WHERE clause processing context */
 977   WhereTerm *pTerm;                /* The term to be analyzed */
 978   WhereMaskSet *pMaskSet;          /* Set of table index masks */
 979   Expr *pExpr;                     /* The expression to be analyzed */
 980   Bitmask prereqLeft;              /* Prerequesites of the pExpr->pLeft */
 981   Bitmask prereqAll;               /* Prerequesites of pExpr */
 982   Bitmask extraRight = 0;          /* Extra dependencies on LEFT JOIN */
 983   Expr *pStr1 = 0;                 /* RHS of LIKE/GLOB operator */
 984   int isComplete = 0;              /* RHS of LIKE/GLOB ends with wildcard */
 985   int noCase = 0;                  /* uppercase equivalent to lowercase */
 986   int op;                          /* Top-level operator.  pExpr->op */
 987   Parse *pParse = pWInfo->pParse;  /* Parsing context */
 988   sqlite3 *db = pParse->db;        /* Database connection */
 989   unsigned char eOp2 = 0;          /* op2 value for LIKE/REGEXP/GLOB */
 990   int nLeft;                       /* Number of elements on left side vector */
 991
 992   if( db->mallocFailed ){
 993     return;
 994   }
 995   pTerm = &pWC->a[idxTerm];
 996   pMaskSet = &pWInfo->sMaskSet;
 997   pExpr = pTerm->pExpr;
 998   assert( pExpr->op!=TK_AS && pExpr->op!=TK_COLLATE );
 999   prereqLeft = sqlite3WhereExprUsage(pMaskSet, pExpr->pLeft);
1000   op = pExpr->op;
1001   if( op==TK_IN ){
1002     assert( pExpr->pRight==0 );
1003     if( sqlite3ExprCheckIN(pParse, pExpr) ) return;
1004     if( ExprHasProperty(pExpr, EP_xIsSelect) ){
1005       pTerm->prereqRight = exprSelectUsage(pMaskSet, pExpr->x.pSelect);
1006     }else{
1007       pTerm->prereqRight = sqlite3WhereExprListUsage(pMaskSet, pExpr->x.pList);
1008     }
1009   }else if( op==TK_ISNULL ){
1010     pTerm->prereqRight = 0;
1011   }else{
1012     pTerm->prereqRight = sqlite3WhereExprUsage(pMaskSet, pExpr->pRight);
1013   }
1014   pMaskSet->bVarSelect = 0;
1015   prereqAll = sqlite3WhereExprUsage(pMaskSet, pExpr);
1016   if( pMaskSet->bVarSelect ) pTerm->wtFlags |= TERM_VARSELECT;
1017   if( ExprHasProperty(pExpr, EP_FromJoin) ){
1018     Bitmask x = sqlite3WhereGetMask(pMaskSet, pExpr->iRightJoinTable);
1019     prereqAll |= x;
1020     extraRight = x-1;  /* ON clause terms may not be used with an index
1021                        ** on left table of a LEFT JOIN.  Ticket #3015 */
1022     if( (prereqAll>>1)>=x ){
1023       sqlite3ErrorMsg(pParse, "ON clause references tables to its right");
1024       return;
1025     }
1026   }
1027   pTerm->prereqAll = prereqAll;
1028   pTerm->leftCursor = -1;
1029   pTerm->iParent = -1;
1030   pTerm->eOperator = 0;
1031   if( allowedOp(op) ){
1032     int aiCurCol[2];
1033     Expr *pLeft = sqlite3ExprSkipCollate(pExpr->pLeft);
1034     Expr *pRight = sqlite3ExprSkipCollate(pExpr->pRight);
1035     u16 opMask = (pTerm->prereqRight & prereqLeft)==0 ? WO_ALL : WO_EQUIV;
1036
1037     if( pTerm->iField>0 ){
1038       assert( op==TK_IN );
1039       assert( pLeft->op==TK_VECTOR );
1040       pLeft = pLeft->x.pList->a[pTerm->iField-1].pExpr;
1041     }
1042
1043     if( exprMightBeIndexed(pSrc, prereqLeft, aiCurCol, pLeft, op) ){
1044       pTerm->leftCursor = aiCurCol[0];
1045       pTerm->u.leftColumn = aiCurCol[1];
1046       pTerm->eOperator = operatorMask(op) & opMask;
1047     }
1048     if( op==TK_IS ) pTerm->wtFlags |= TERM_IS;
1049     if( pRight
1050      && exprMightBeIndexed(pSrc, pTerm->prereqRight, aiCurCol, pRight, op)
1051     ){
1052       WhereTerm *pNew;
1053       Expr *pDup;
1054       u16 eExtraOp = 0;        /* Extra bits for pNew->eOperator */
1055       assert( pTerm->iField==0 );
1056       if( pTerm->leftCursor>=0 ){
1057         int idxNew;
1058         pDup = sqlite3ExprDup(db, pExpr, 0);
1059         if( db->mallocFailed ){
1060           sqlite3ExprDelete(db, pDup);
1061           return;
1062         }
1063         idxNew = whereClauseInsert(pWC, pDup, TERM_VIRTUAL|TERM_DYNAMIC);
1064         if( idxNew==0 ) return;
1065         pNew = &pWC->a[idxNew];
1066         markTermAsChild(pWC, idxNew, idxTerm);
1067         if( op==TK_IS ) pNew->wtFlags |= TERM_IS;
1068         pTerm = &pWC->a[idxTerm];
1069         pTerm->wtFlags |= TERM_COPIED;
1070
1071         if( termIsEquivalence(pParse, pDup) ){
1072           pTerm->eOperator |= WO_EQUIV;
1073           eExtraOp = WO_EQUIV;
1074         }
1075       }else{
1076         pDup = pExpr;
1077         pNew = pTerm;
1078       }
1079       exprCommute(pParse, pDup);
1080       pNew->leftCursor = aiCurCol[0];
1081       pNew->u.leftColumn = aiCurCol[1];
1082       testcase( (prereqLeft | extraRight) != prereqLeft );
1083       pNew->prereqRight = prereqLeft | extraRight;
1084       pNew->prereqAll = prereqAll;
1085       pNew->eOperator = (operatorMask(pDup->op) + eExtraOp) & opMask;
1086     }
1087   }
1088
1089 #ifndef SQLITE_OMIT_BETWEEN_OPTIMIZATION
1090   /* If a term is the BETWEEN operator, create two new virtual terms
1091   ** that define the range that the BETWEEN implements.  For example:
1092   **
1093   **      a BETWEEN b AND c
1094   **
1095   ** is converted into:
1096   **
1097   **      (a BETWEEN b AND c) AND (a>=b) AND (a<=c)
1098   **
1099   ** The two new terms are added onto the end of the WhereClause object.
1100   ** The new terms are "dynamic" and are children of the original BETWEEN
1101   ** term.  That means that if the BETWEEN term is coded, the children are
1102   ** skipped.  Or, if the children are satisfied by an index, the original
1103   ** BETWEEN term is skipped.
1104   */
1105   else if( pExpr->op==TK_BETWEEN && pWC->op==TK_AND ){
1106     ExprList *pList = pExpr->x.pList;
1107     int i;
1108     static const u8 ops[] = {TK_GE, TK_LE};
1109     assert( pList!=0 );
1110     assert( pList->nExpr==2 );
1111     for(i=0; i<2; i++){
1112       Expr *pNewExpr;
1113       int idxNew;
1114       pNewExpr = sqlite3PExpr(pParse, ops[i],
1115                              sqlite3ExprDup(db, pExpr->pLeft, 0),
1116                              sqlite3ExprDup(db, pList->a[i].pExpr, 0));
1117       transferJoinMarkings(pNewExpr, pExpr);
1118       idxNew = whereClauseInsert(pWC, pNewExpr, TERM_VIRTUAL|TERM_DYNAMIC);
1119       testcase( idxNew==0 );
1120       exprAnalyze(pSrc, pWC, idxNew);
1121       pTerm = &pWC->a[idxTerm];
1122       markTermAsChild(pWC, idxNew, idxTerm);
1123     }
1124   }
1125 #endif /* SQLITE_OMIT_BETWEEN_OPTIMIZATION */
1126
1127 #if !defined(SQLITE_OMIT_OR_OPTIMIZATION) && !defined(SQLITE_OMIT_SUBQUERY)
1128   /* Analyze a term that is composed of two or more subterms connected by
1129   ** an OR operator.
1130   */
1131   else if( pExpr->op==TK_OR ){
1132     assert( pWC->op==TK_AND );
1133     exprAnalyzeOrTerm(pSrc, pWC, idxTerm);
1134     pTerm = &pWC->a[idxTerm];
1135   }
1136 #endif /* SQLITE_OMIT_OR_OPTIMIZATION */
1137
1138 #ifndef SQLITE_OMIT_LIKE_OPTIMIZATION
1139   /* Add constraints to reduce the search space on a LIKE or GLOB
1140   ** operator.
1141   **
1142   ** A like pattern of the form "x LIKE 'aBc%'" is changed into constraints
1143   **
1144   **          x>='ABC' AND x<'abd' AND x LIKE 'aBc%'
1145   **
1146   ** The last character of the prefix "abc" is incremented to form the
1147   ** termination condition "abd".  If case is not significant (the default
1148   ** for LIKE) then the lower-bound is made all uppercase and the upper-
1149   ** bound is made all lowercase so that the bounds also work when comparing
1150   ** BLOBs.
1151   */
1152   if( pWC->op==TK_AND
1153    && isLikeOrGlob(pParse, pExpr, &pStr1, &isComplete, &noCase)
1154   ){
1155     Expr *pLeft;       /* LHS of LIKE/GLOB operator */
1156     Expr *pStr2;       /* Copy of pStr1 - RHS of LIKE/GLOB operator */
1157     Expr *pNewExpr1;
1158     Expr *pNewExpr2;
1159     int idxNew1;
1160     int idxNew2;
1161     const char *zCollSeqName;     /* Name of collating sequence */
1162     const u16 wtFlags = TERM_LIKEOPT | TERM_VIRTUAL | TERM_DYNAMIC;
1163
1164     pLeft = pExpr->x.pList->a[1].pExpr;
1165     pStr2 = sqlite3ExprDup(db, pStr1, 0);
1166
1167     /* Convert the lower bound to upper-case and the upper bound to
1168     ** lower-case (upper-case is less than lower-case in ASCII) so that
1169     ** the range constraints also work for BLOBs
1170     */
1171     if( noCase && !pParse->db->mallocFailed ){
1172       int i;
1173       char c;
1174       pTerm->wtFlags |= TERM_LIKE;
1175       for(i=0; (c = pStr1->u.zToken[i])!=0; i++){
1176         pStr1->u.zToken[i] = sqlite3Toupper(c);
1177         pStr2->u.zToken[i] = sqlite3Tolower(c);
1178       }
1179     }
1180
1181     if( !db->mallocFailed ){
1182       u8 c, *pC;       /* Last character before the first wildcard */
1183       pC = (u8*)&pStr2->u.zToken[sqlite3Strlen30(pStr2->u.zToken)-1];
1184       c = *pC;
1185       if( noCase ){
1186         /* The point is to increment the last character before the first
1187         ** wildcard.  But if we increment '@', that will push it into the
1188         ** alphabetic range where case conversions will mess up the
1189         ** inequality.  To avoid this, make sure to also run the full
1190         ** LIKE on all candidate expressions by clearing the isComplete flag
1191         */
1192         if( c=='A'-1 ) isComplete = 0;
1193         c = sqlite3UpperToLower[c];
1194       }
1195       *pC = c + 1;
1196     }
1197     zCollSeqName = noCase ? "NOCASE" : "BINARY";
1198     pNewExpr1 = sqlite3ExprDup(db, pLeft, 0);
1199     pNewExpr1 = sqlite3PExpr(pParse, TK_GE,
1200            sqlite3ExprAddCollateString(pParse,pNewExpr1,zCollSeqName),
1201            pStr1);
1202     transferJoinMarkings(pNewExpr1, pExpr);
1203     idxNew1 = whereClauseInsert(pWC, pNewExpr1, wtFlags);
1204     testcase( idxNew1==0 );
1205     exprAnalyze(pSrc, pWC, idxNew1);
1206     pNewExpr2 = sqlite3ExprDup(db, pLeft, 0);
1207     pNewExpr2 = sqlite3PExpr(pParse, TK_LT,
1208            sqlite3ExprAddCollateString(pParse,pNewExpr2,zCollSeqName),
1209            pStr2);
1210     transferJoinMarkings(pNewExpr2, pExpr);
1211     idxNew2 = whereClauseInsert(pWC, pNewExpr2, wtFlags);
1212     testcase( idxNew2==0 );
1213     exprAnalyze(pSrc, pWC, idxNew2);
1214     pTerm = &pWC->a[idxTerm];
1215     if( isComplete ){
1216       markTermAsChild(pWC, idxNew1, idxTerm);
1217       markTermAsChild(pWC, idxNew2, idxTerm);
1218     }
1219   }
1220 #endif /* SQLITE_OMIT_LIKE_OPTIMIZATION */
1221
1222 #ifndef SQLITE_OMIT_VIRTUALTABLE
1223   /* Add a WO_AUX auxiliary term to the constraint set if the
1224   ** current expression is of the form "column OP expr" where OP
1225   ** is an operator that gets passed into virtual tables but which is
1226   ** not normally optimized for ordinary tables.  In other words, OP
1227   ** is one of MATCH, LIKE, GLOB, REGEXP, !=, IS, IS NOT, or NOT NULL.
1228   ** This information is used by the xBestIndex methods of
1229   ** virtual tables.  The native query optimizer does not attempt
1230   ** to do anything with MATCH functions.
1231   */
1232   if( pWC->op==TK_AND ){
1233     Expr *pRight = 0, *pLeft = 0;
1234     int res = isAuxiliaryVtabOperator(pExpr, &eOp2, &pLeft, &pRight);
1235     while( res-- > 0 ){
1236       int idxNew;
1237       WhereTerm *pNewTerm;
1238       Bitmask prereqColumn, prereqExpr;
1239
1240       prereqExpr = sqlite3WhereExprUsage(pMaskSet, pRight);
1241       prereqColumn = sqlite3WhereExprUsage(pMaskSet, pLeft);
1242       if( (prereqExpr & prereqColumn)==0 ){
1243         Expr *pNewExpr;
1244         pNewExpr = sqlite3PExpr(pParse, TK_MATCH,
1245             0, sqlite3ExprDup(db, pRight, 0));
1246         if( ExprHasProperty(pExpr, EP_FromJoin) && pNewExpr ){
1247           ExprSetProperty(pNewExpr, EP_FromJoin);
1248         }
1249         idxNew = whereClauseInsert(pWC, pNewExpr, TERM_VIRTUAL|TERM_DYNAMIC);
1250         testcase( idxNew==0 );
1251         pNewTerm = &pWC->a[idxNew];
1252         pNewTerm->prereqRight = prereqExpr;
1253         pNewTerm->leftCursor = pLeft->iTable;
1254         pNewTerm->u.leftColumn = pLeft->iColumn;
1255         pNewTerm->eOperator = WO_AUX;
1256         pNewTerm->eMatchOp = eOp2;
1257         markTermAsChild(pWC, idxNew, idxTerm);
1258         pTerm = &pWC->a[idxTerm];
1259         pTerm->wtFlags |= TERM_COPIED;
1260         pNewTerm->prereqAll = pTerm->prereqAll;
1261       }
1262       SWAP(Expr*, pLeft, pRight);
1263     }
1264   }
1265 #endif /* SQLITE_OMIT_VIRTUALTABLE */
1266
1267   /* If there is a vector == or IS term - e.g. "(a, b) == (?, ?)" - create
1268   ** new terms for each component comparison - "a = ?" and "b = ?".  The
1269   ** new terms completely replace the original vector comparison, which is
1270   ** no longer used.
1271   **
1272   ** This is only required if at least one side of the comparison operation
1273   ** is not a sub-select.  */
1274   if( pWC->op==TK_AND
1275   && (pExpr->op==TK_EQ || pExpr->op==TK_IS)
1276   && (nLeft = sqlite3ExprVectorSize(pExpr->pLeft))>1
1277   && sqlite3ExprVectorSize(pExpr->pRight)==nLeft
1278   && ( (pExpr->pLeft->flags & EP_xIsSelect)==0
1279     || (pExpr->pRight->flags & EP_xIsSelect)==0)
1280   ){
1281     int i;
1282     for(i=0; i<nLeft; i++){
1283       int idxNew;
1284       Expr *pNew;
1285       Expr *pLeft = sqlite3ExprForVectorField(pParse, pExpr->pLeft, i);
1286       Expr *pRight = sqlite3ExprForVectorField(pParse, pExpr->pRight, i);
1287
1288       pNew = sqlite3PExpr(pParse, pExpr->op, pLeft, pRight);
1289       transferJoinMarkings(pNew, pExpr);
1290       idxNew = whereClauseInsert(pWC, pNew, TERM_DYNAMIC);
1291       exprAnalyze(pSrc, pWC, idxNew);
1292     }
1293     pTerm = &pWC->a[idxTerm];
1294     pTerm->wtFlags |= TERM_CODED|TERM_VIRTUAL;  /* Disable the original */
1295     pTerm->eOperator = 0;
1296   }
1297
1298   /* If there is a vector IN term - e.g. "(a, b) IN (SELECT ...)" - create
1299   ** a virtual term for each vector component. The expression object
1300   ** used by each such virtual term is pExpr (the full vector IN(...)
1301   ** expression). The WhereTerm.iField variable identifies the index within
1302   ** the vector on the LHS that the virtual term represents.
1303   **
1304   ** This only works if the RHS is a simple SELECT, not a compound
1305   */
1306   if( pWC->op==TK_AND && pExpr->op==TK_IN && pTerm->iField==0
1307    && pExpr->pLeft->op==TK_VECTOR
1308    && pExpr->x.pSelect->pPrior==0
1309   ){
1310     int i;
1311     for(i=0; i<sqlite3ExprVectorSize(pExpr->pLeft); i++){
1312       int idxNew;
1313       idxNew = whereClauseInsert(pWC, pExpr, TERM_VIRTUAL);
1314       pWC->a[idxNew].iField = i+1;
1315       exprAnalyze(pSrc, pWC, idxNew);
1316       markTermAsChild(pWC, idxNew, idxTerm);
1317     }
1318   }
1319
1320 #ifdef SQLITE_ENABLE_STAT3_OR_STAT4
1321   /* When sqlite_stat3 histogram data is available an operator of the
1322   ** form "x IS NOT NULL" can sometimes be evaluated more efficiently
1323   ** as "x>NULL" if x is not an INTEGER PRIMARY KEY.  So construct a
1324   ** virtual term of that form.
1325   **
1326   ** Note that the virtual term must be tagged with TERM_VNULL.
1327   */
1328   if( pExpr->op==TK_NOTNULL
1329    && pExpr->pLeft->op==TK_COLUMN
1330    && pExpr->pLeft->iColumn>=0
1331    && OptimizationEnabled(db, SQLITE_Stat34)
1332   ){
1333     Expr *pNewExpr;
1334     Expr *pLeft = pExpr->pLeft;
1335     int idxNew;
1336     WhereTerm *pNewTerm;
1337
1338     pNewExpr = sqlite3PExpr(pParse, TK_GT,
1339                             sqlite3ExprDup(db, pLeft, 0),
1340                             sqlite3ExprAlloc(db, TK_NULL, 0, 0));
1341
1342     idxNew = whereClauseInsert(pWC, pNewExpr,
1343                               TERM_VIRTUAL|TERM_DYNAMIC|TERM_VNULL);
1344     if( idxNew ){
1345       pNewTerm = &pWC->a[idxNew];
1346       pNewTerm->prereqRight = 0;
1347       pNewTerm->leftCursor = pLeft->iTable;
1348       pNewTerm->u.leftColumn = pLeft->iColumn;
1349       pNewTerm->eOperator = WO_GT;
1350       markTermAsChild(pWC, idxNew, idxTerm);
1351       pTerm = &pWC->a[idxTerm];
1352       pTerm->wtFlags |= TERM_COPIED;
1353       pNewTerm->prereqAll = pTerm->prereqAll;
1354     }
1355   }
1356 #endif /* SQLITE_ENABLE_STAT3_OR_STAT4 */
1357
1358   /* Prevent ON clause terms of a LEFT JOIN from being used to drive
1359   ** an index for tables to the left of the join.
1360   */
1361   testcase( pTerm!=&pWC->a[idxTerm] );
1362   pTerm = &pWC->a[idxTerm];
1363   pTerm->prereqRight |= extraRight;
1364 }
1365
1366 /***************************************************************************
1367 ** Routines with file scope above.  Interface to the rest of the where.c
1368 ** subsystem follows.
1369 ***************************************************************************/
1370
1371 /*
1372 ** This routine identifies subexpressions in the WHERE clause where
1373 ** each subexpression is separated by the AND operator or some other
1374 ** operator specified in the op parameter.  The WhereClause structure
1375 ** is filled with pointers to subexpressions.  For example:
1376 **
1377 **    WHERE  a=='hello' AND coalesce(b,11)<10 AND (c+12!=d OR c==22)
1378 **           \________/     \_______________/     \________________/
1379 **            slot[0]            slot[1]               slot[2]
1380 **
1381 ** The original WHERE clause in pExpr is unaltered.  All this routine
1382 ** does is make slot[] entries point to substructure within pExpr.
1383 **
1384 ** In the previous sentence and in the diagram, "slot[]" refers to
1385 ** the WhereClause.a[] array.  The slot[] array grows as needed to contain
1386 ** all terms of the WHERE clause.
1387 */
1388 void sqlite3WhereSplit(WhereClause *pWC, Expr *pExpr, u8 op){
1389   Expr *pE2 = sqlite3ExprSkipCollate(pExpr);
1390   pWC->op = op;
1391   if( pE2==0 ) return;
1392   if( pE2->op!=op ){
1393     whereClauseInsert(pWC, pExpr, 0);
1394   }else{
1395     sqlite3WhereSplit(pWC, pE2->pLeft, op);
1396     sqlite3WhereSplit(pWC, pE2->pRight, op);
1397   }
1398 }
1399
1400 /*
1401 ** Initialize a preallocated WhereClause structure.
1402 */
1403 void sqlite3WhereClauseInit(
1404   WhereClause *pWC,        /* The WhereClause to be initialized */
1405   WhereInfo *pWInfo        /* The WHERE processing context */
1406 ){
1407   pWC->pWInfo = pWInfo;
1408   pWC->pOuter = 0;
1409   pWC->nTerm = 0;
1410   pWC->nSlot = ArraySize(pWC->aStatic);
1411   pWC->a = pWC->aStatic;
1412 }
1413
1414 /*
1415 ** Deallocate a WhereClause structure.  The WhereClause structure
1416 ** itself is not freed.  This routine is the inverse of
1417 ** sqlite3WhereClauseInit().
1418 */
1419 void sqlite3WhereClauseClear(WhereClause *pWC){
1420   int i;
1421   WhereTerm *a;
1422   sqlite3 *db = pWC->pWInfo->pParse->db;
1423   for(i=pWC->nTerm-1, a=pWC->a; i>=0; i--, a++){
1424     if( a->wtFlags & TERM_DYNAMIC ){
1425       sqlite3ExprDelete(db, a->pExpr);
1426     }
1427     if( a->wtFlags & TERM_ORINFO ){
1428       whereOrInfoDelete(db, a->u.pOrInfo);
1429     }else if( a->wtFlags & TERM_ANDINFO ){
1430       whereAndInfoDelete(db, a->u.pAndInfo);
1431     }
1432   }
1433   if( pWC->a!=pWC->aStatic ){
1434     sqlite3DbFree(db, pWC->a);
1435   }
1436 }
1437
1438
1439 /*
1440 ** These routines walk (recursively) an expression tree and generate
1441 ** a bitmask indicating which tables are used in that expression
1442 ** tree.
1443 */
1444 Bitmask sqlite3WhereExprUsage(WhereMaskSet *pMaskSet, Expr *p){
1445   Bitmask mask;
1446   if( p==0 ) return 0;
1447   if( p->op==TK_COLUMN ){
1448     return sqlite3WhereGetMask(pMaskSet, p->iTable);
1449   }
1450   mask = (p->op==TK_IF_NULL_ROW) ? sqlite3WhereGetMask(pMaskSet, p->iTable) : 0;
1451   assert( !ExprHasProperty(p, EP_TokenOnly) );
1452   if( p->pLeft ) mask |= sqlite3WhereExprUsage(pMaskSet, p->pLeft);
1453   if( p->pRight ){
1454     mask |= sqlite3WhereExprUsage(pMaskSet, p->pRight);
1455     assert( p->x.pList==0 );
1456   }else if( ExprHasProperty(p, EP_xIsSelect) ){
1457     if( ExprHasProperty(p, EP_VarSelect) ) pMaskSet->bVarSelect = 1;
1458     mask |= exprSelectUsage(pMaskSet, p->x.pSelect);
1459   }else if( p->x.pList ){
1460     mask |= sqlite3WhereExprListUsage(pMaskSet, p->x.pList);
1461   }
1462   return mask;
1463 }
1464 Bitmask sqlite3WhereExprListUsage(WhereMaskSet *pMaskSet, ExprList *pList){
1465   int i;
1466   Bitmask mask = 0;
1467   if( pList ){
1468     for(i=0; i<pList->nExpr; i++){
1469       mask |= sqlite3WhereExprUsage(pMaskSet, pList->a[i].pExpr);
1470     }
1471   }
1472   return mask;
1473 }
1474
1475
1476 /*
1477 ** Call exprAnalyze on all terms in a WHERE clause.
1478 **
1479 ** Note that exprAnalyze() might add new virtual terms onto the
1480 ** end of the WHERE clause.  We do not want to analyze these new
1481 ** virtual terms, so start analyzing at the end and work forward
1482 ** so that the added virtual terms are never processed.
1483 */
1484 void sqlite3WhereExprAnalyze(
1485   SrcList *pTabList,       /* the FROM clause */
1486   WhereClause *pWC         /* the WHERE clause to be analyzed */
1487 ){
1488   int i;
1489   for(i=pWC->nTerm-1; i>=0; i--){
1490     exprAnalyze(pTabList, pWC, i);
1491   }
1492 }
1493
1494 /*
1495 ** For table-valued-functions, transform the function arguments into
1496 ** new WHERE clause terms.
1497 **
1498 ** Each function argument translates into an equality constraint against
1499 ** a HIDDEN column in the table.
1500 */
1501 void sqlite3WhereTabFuncArgs(
1502   Parse *pParse,                    /* Parsing context */
1503   struct SrcList_item *pItem,       /* The FROM clause term to process */
1504   WhereClause *pWC                  /* Xfer function arguments to here */
1505 ){
1506   Table *pTab;
1507   int j, k;
1508   ExprList *pArgs;
1509   Expr *pColRef;
1510   Expr *pTerm;
1511   if( pItem->fg.isTabFunc==0 ) return;
1512   pTab = pItem->pTab;
1513   assert( pTab!=0 );
1514   pArgs = pItem->u1.pFuncArg;
1515   if( pArgs==0 ) return;
1516   for(j=k=0; j<pArgs->nExpr; j++){
1517     while( k<pTab->nCol && (pTab->aCol[k].colFlags & COLFLAG_HIDDEN)==0 ){k++;}
1518     if( k>=pTab->nCol ){
1519       sqlite3ErrorMsg(pParse, "too many arguments on %s() - max %d",
1520                       pTab->zName, j);
1521       return;
1522     }
1523     pColRef = sqlite3ExprAlloc(pParse->db, TK_COLUMN, 0, 0);
1524     if( pColRef==0 ) return;
1525     pColRef->iTable = pItem->iCursor;
1526     pColRef->iColumn = k++;
1527     pColRef->pTab = pTab;
1528     pTerm = sqlite3PExpr(pParse, TK_EQ, pColRef,
1529                          sqlite3ExprDup(pParse->db, pArgs->a[j].pExpr, 0));
1530     whereClauseInsert(pWC, pTerm, TERM_DYNAMIC);
1531   }
1532 }