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