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