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