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