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