AryaWu/sqlite
0
1/*2** 2015-06-083**4** The author disclaims copyright to this source code. In place of5** 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 process13** the WHERE clause of SQL statements.14**15** This file was originally part of where.c but was split out to improve16** readability and editability. This file contains utility routines for17** analyzing Expr objects in the WHERE clause.18*/19#include "sqliteInt.h"20#include "whereInt.h"21 22/* Forward declarations */23static void exprAnalyze(SrcList*, WhereClause*, int);24 25/*26** Deallocate all memory associated with a WhereOrInfo object.27*/28static 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*/36static 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 memory46** allocation error. The memory allocation failure will be recorded in47** 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 responsibility52** 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 store56** WhereTerms. All pointers to WhereTerms should be invalidated after57** calling this routine. Such pointers may be reinitialized by referencing58** the pWC->a[] array.59*/60static 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 is96** allowed for an indexable WHERE clause term. The allowed operators are97** "=", "<", ">", "<=", ">=", "IN", "IS", and "IS NULL"98*/99static int allowedOp(int op){100 assert( TK_GT>TK_EQ && TK_GT<TK_GE );101 assert( TK_LT>TK_EQ && TK_LT<TK_GE );102 assert( TK_LE>TK_EQ && TK_LE<TK_GE );103 assert( TK_GE==TK_EQ+4 );104 assert( TK_IN<TK_EQ );105 assert( TK_IS<TK_EQ );106 assert( TK_ISNULL<TK_EQ );107 if( op>TK_GE ) return 0;108 if( op>=TK_EQ ) return 1;109 return op==TK_IN || op==TK_ISNULL || op==TK_IS;110}111 112/*113** Commute a comparison operator. Expressions of the form "X op Y"114** are converted into "Y op X".115*/116static u16 exprCommute(Parse *pParse, Expr *pExpr){117 if( pExpr->pLeft->op==TK_VECTOR118 || pExpr->pRight->op==TK_VECTOR119 || sqlite3BinaryCompareCollSeq(pParse, pExpr->pLeft, pExpr->pRight) !=120 sqlite3BinaryCompareCollSeq(pParse, pExpr->pRight, pExpr->pLeft)121 ){122 pExpr->flags ^= EP_Commuted;123 }124 SWAP(Expr*,pExpr->pRight,pExpr->pLeft);125 if( pExpr->op>=TK_GT ){126 assert( TK_LT==TK_GT+2 );127 assert( TK_GE==TK_LE+2 );128 assert( TK_GT>TK_EQ );129 assert( TK_GT<TK_LE );130 assert( pExpr->op>=TK_GT && pExpr->op<=TK_GE );131 pExpr->op = ((pExpr->op-TK_GT)^2)+TK_GT;132 }133 return 0;134}135 136/*137** Translate from TK_xx operator to WO_xx bitmask.138*/139static u16 operatorMask(int op){140 u16 c;141 assert( allowedOp(op) );142 if( op>=TK_EQ ){143 assert( (WO_EQ<<(op-TK_EQ)) < 0x7fff );144 c = (u16)(WO_EQ<<(op-TK_EQ));145 }else if( op==TK_IN ){146 c = WO_IN;147 }else if( op==TK_ISNULL ){148 c = WO_ISNULL;149 }else{150 assert( op==TK_IS );151 c = WO_IS;152 }153 assert( op!=TK_ISNULL || c==WO_ISNULL );154 assert( op!=TK_IN || c==WO_IN );155 assert( op!=TK_EQ || c==WO_EQ );156 assert( op!=TK_LT || c==WO_LT );157 assert( op!=TK_LE || c==WO_LE );158 assert( op!=TK_GT || c==WO_GT );159 assert( op!=TK_GE || c==WO_GE );160 assert( op!=TK_IS || c==WO_IS );161 return c;162}163 164 165#ifndef SQLITE_OMIT_LIKE_OPTIMIZATION166/*167** Check to see if the given expression is a LIKE or GLOB operator that168** can be optimized using inequality constraints. Return TRUE if it is169** so and false if not.170**171** In order for the operator to be optimizible, the RHS must be a string172** literal that does not begin with a wildcard. The LHS must be a column173** that may only be NULL, a string, or a BLOB, never a number. (This means174** that virtual tables cannot participate in the LIKE optimization.) The175** collating sequence for the column on the LHS must be appropriate for176** the operator.177*/178static int isLikeOrGlob(179 Parse *pParse, /* Parsing and code generating context */180 Expr *pExpr, /* Test this expression */181 Expr **ppPrefix, /* Pointer to TK_STRING expression with pattern prefix */182 int *pisComplete, /* True if the only wildcard is % in the last character */183 int *pnoCase /* True if uppercase is equivalent to lowercase */184){185 const u8 *z = 0; /* String on RHS of LIKE operator */186 Expr *pRight, *pLeft; /* Right and left size of LIKE operator */187 ExprList *pList; /* List of operands to the LIKE operator */188 u8 c; /* One character in z[] */189 int cnt; /* Number of non-wildcard prefix characters */190 u8 wc[4]; /* Wildcard characters */191 sqlite3 *db = pParse->db; /* Database connection */192 sqlite3_value *pVal = 0;193 int op; /* Opcode of pRight */194 int rc; /* Result code to return */195 196 if( !sqlite3IsLikeFunction(db, pExpr, pnoCase, (char*)wc) ){197 return 0;198 }199#ifdef SQLITE_EBCDIC200 if( *pnoCase ) return 0;201#endif202 assert( ExprUseXList(pExpr) );203 pList = pExpr->x.pList;204 pLeft = pList->a[1].pExpr;205 206 pRight = sqlite3ExprSkipCollate(pList->a[0].pExpr);207 op = pRight->op;208 if( op==TK_VARIABLE && (db->flags & SQLITE_EnableQPSG)==0 ){209 Vdbe *pReprepare = pParse->pReprepare;210 int iCol = pRight->iColumn;211 pVal = sqlite3VdbeGetBoundValue(pReprepare, iCol, SQLITE_AFF_BLOB);212 if( pVal && sqlite3_value_type(pVal)==SQLITE_TEXT ){213 z = sqlite3_value_text(pVal);214 }215 sqlite3VdbeSetVarmask(pParse->pVdbe, iCol);216 assert( pRight->op==TK_VARIABLE || pRight->op==TK_REGISTER );217 }else if( op==TK_STRING ){218 assert( !ExprHasProperty(pRight, EP_IntValue) );219 z = (u8*)pRight->u.zToken;220 }221 if( z ){222 /* Count the number of prefix bytes prior to the first wildcard,223 ** U+fffd character, or malformed utf-8. If the underlying database224 ** has a UTF16LE encoding, then only consider ASCII characters. Note that225 ** the encoding of z[] is UTF8 - we are dealing with only UTF8 here in this226 ** code, but the database engine itself might be processing content using a227 ** different encoding. */228 cnt = 0;229 while( (c=z[cnt])!=0 && c!=wc[0] && c!=wc[1] && c!=wc[2] ){230 cnt++;231 if( c==wc[3] && z[cnt]>0 && z[cnt]<0x80 ){232 cnt++;233 }else if( c>=0x80 ){234 const u8 *z2 = z+cnt-1;235 if( c==0xff || sqlite3Utf8Read(&z2)==0xfffd /* bad utf-8 */236 || ENC(db)==SQLITE_UTF16LE 237 ){238 cnt--;239 break;240 }else{241 cnt = (int)(z2-z);242 }243 }244 }245 246 /* The optimization is possible only if (1) the pattern does not begin247 ** with a wildcard and if (2) the non-wildcard prefix does not end with248 ** an (illegal 0xff) character, or (3) the pattern does not consist of249 ** a single escape character. The second condition is necessary so250 ** that we can increment the prefix key to find an upper bound for the251 ** range search. The third is because the caller assumes that the pattern252 ** consists of at least one character after all escapes have been253 ** removed. */254 if( (cnt>1 || (cnt>0 && z[0]!=wc[3])) && ALWAYS(255!=(u8)z[cnt-1]) ){255 Expr *pPrefix;256 257 /* A "complete" match if the pattern ends with "*" or "%" */258 *pisComplete = c==wc[0] && z[cnt+1]==0 && ENC(db)!=SQLITE_UTF16LE;259 260 /* Get the pattern prefix. Remove all escapes from the prefix. */261 pPrefix = sqlite3Expr(db, TK_STRING, (char*)z);262 if( pPrefix ){263 int iFrom, iTo;264 char *zNew;265 assert( !ExprHasProperty(pPrefix, EP_IntValue) );266 zNew = pPrefix->u.zToken;267 zNew[cnt] = 0;268 for(iFrom=iTo=0; iFrom<cnt; iFrom++){269 if( zNew[iFrom]==wc[3] ) iFrom++;270 zNew[iTo++] = zNew[iFrom];271 }272 zNew[iTo] = 0;273 assert( iTo>0 );274 275 /* If the LHS is not an ordinary column with TEXT affinity, then the276 ** pattern prefix boundaries (both the start and end boundaries) must277 ** not look like a number. Otherwise the pattern might be treated as278 ** a number, which will invalidate the LIKE optimization.279 **280 ** Getting this right has been a persistent source of bugs in the281 ** LIKE optimization. See, for example:282 ** 2018-09-10 https://sqlite.org/src/info/c94369cae9b561b1283 ** 2019-05-02 https://sqlite.org/src/info/b043a54c3de54b28284 ** 2019-06-10 https://sqlite.org/src/info/fd76310a5e843e07285 ** 2019-06-14 https://sqlite.org/src/info/ce8717f0885af975286 ** 2019-09-03 https://sqlite.org/src/info/0f0428096f17252a287 */288 if( pLeft->op!=TK_COLUMN289 || sqlite3ExprAffinity(pLeft)!=SQLITE_AFF_TEXT290 || (ALWAYS( ExprUseYTab(pLeft) )291 && ALWAYS(pLeft->y.pTab)292 && IsVirtual(pLeft->y.pTab)) /* Might be numeric */293 ){294 int isNum;295 double rDummy;296 isNum = sqlite3AtoF(zNew, &rDummy, iTo, SQLITE_UTF8);297 if( isNum<=0 ){298 if( iTo==1 && zNew[0]=='-' ){299 isNum = +1;300 }else{301 zNew[iTo-1]++;302 isNum = sqlite3AtoF(zNew, &rDummy, iTo, SQLITE_UTF8);303 zNew[iTo-1]--;304 }305 }306 if( isNum>0 ){307 sqlite3ExprDelete(db, pPrefix);308 sqlite3ValueFree(pVal);309 return 0;310 }311 }312 }313 *ppPrefix = pPrefix;314 315 /* If the RHS pattern is a bound parameter, make arrangements to316 ** reprepare the statement when that parameter is rebound */317 if( op==TK_VARIABLE ){318 Vdbe *v = pParse->pVdbe;319 sqlite3VdbeSetVarmask(v, pRight->iColumn);320 assert( !ExprHasProperty(pRight, EP_IntValue) );321 if( *pisComplete && pRight->u.zToken[1] ){322 /* If the rhs of the LIKE expression is a variable, and the current323 ** value of the variable means there is no need to invoke the LIKE324 ** function, then no OP_Variable will be added to the program.325 ** This causes problems for the sqlite3_bind_parameter_name()326 ** API. To work around them, add a dummy OP_Variable here.327 */328 int r1 = sqlite3GetTempReg(pParse);329 sqlite3ExprCodeTarget(pParse, pRight, r1);330 sqlite3VdbeChangeP3(v, sqlite3VdbeCurrentAddr(v)-1, 0);331 sqlite3ReleaseTempReg(pParse, r1);332 }333 }334 }else{335 z = 0;336 }337 }338 339 rc = (z!=0);340 sqlite3ValueFree(pVal);341 return rc;342}343#endif /* SQLITE_OMIT_LIKE_OPTIMIZATION */344 345 346#ifndef SQLITE_OMIT_VIRTUALTABLE347/*348** Check to see if the pExpr expression is a form that needs to be passed349** to the xBestIndex method of virtual tables. Forms of interest include:350**351** Expression Virtual Table Operator352** ----------------------- ---------------------------------353** 1. column MATCH expr SQLITE_INDEX_CONSTRAINT_MATCH354** 2. column GLOB expr SQLITE_INDEX_CONSTRAINT_GLOB355** 3. column LIKE expr SQLITE_INDEX_CONSTRAINT_LIKE356** 4. column REGEXP expr SQLITE_INDEX_CONSTRAINT_REGEXP357** 5. column != expr SQLITE_INDEX_CONSTRAINT_NE358** 6. expr != column SQLITE_INDEX_CONSTRAINT_NE359** 7. column IS NOT expr SQLITE_INDEX_CONSTRAINT_ISNOT360** 8. expr IS NOT column SQLITE_INDEX_CONSTRAINT_ISNOT361** 9. column IS NOT NULL SQLITE_INDEX_CONSTRAINT_ISNOTNULL362**363** In every case, "column" must be a column of a virtual table. If there364** is a match, set *ppLeft to the "column" expression, set *ppRight to the365** "expr" expression (even though in forms (6) and (8) the column is on the366** right and the expression is on the left). Also set *peOp2 to the367** appropriate virtual table operator. The return value is 1 or 2 if there368** is a match. The usual return is 1, but if the RHS is also a column369** of virtual table in forms (5) or (7) then return 2.370**371** If the expression matches none of the patterns above, return 0.372*/373static int isAuxiliaryVtabOperator(374 sqlite3 *db, /* Parsing context */375 Expr *pExpr, /* Test this expression */376 unsigned char *peOp2, /* OUT: 0 for MATCH, or else an op2 value */377 Expr **ppLeft, /* Column expression to left of MATCH/op2 */378 Expr **ppRight /* Expression to left of MATCH/op2 */379){380 if( pExpr->op==TK_FUNCTION ){381 static const struct Op2 {382 const char *zOp;383 unsigned char eOp2;384 } aOp[] = {385 { "match", SQLITE_INDEX_CONSTRAINT_MATCH },386 { "glob", SQLITE_INDEX_CONSTRAINT_GLOB },387 { "like", SQLITE_INDEX_CONSTRAINT_LIKE },388 { "regexp", SQLITE_INDEX_CONSTRAINT_REGEXP }389 };390 ExprList *pList;391 Expr *pCol; /* Column reference */392 int i;393 394 assert( ExprUseXList(pExpr) );395 pList = pExpr->x.pList;396 if( pList==0 || pList->nExpr!=2 ){397 return 0;398 }399 400 /* Built-in operators MATCH, GLOB, LIKE, and REGEXP attach to a401 ** virtual table on their second argument, which is the same as402 ** the left-hand side operand in their in-fix form.403 **404 ** vtab_column MATCH expression405 ** MATCH(expression,vtab_column)406 */407 pCol = pList->a[1].pExpr;408 assert( pCol->op!=TK_COLUMN || (ExprUseYTab(pCol) && pCol->y.pTab!=0) );409 if( ExprIsVtab(pCol) ){410 for(i=0; i<ArraySize(aOp); i++){411 assert( !ExprHasProperty(pExpr, EP_IntValue) );412 if( sqlite3StrICmp(pExpr->u.zToken, aOp[i].zOp)==0 ){413 *peOp2 = aOp[i].eOp2;414 *ppRight = pList->a[0].pExpr;415 *ppLeft = pCol;416 return 1;417 }418 }419 }420 421 /* We can also match against the first column of overloaded422 ** functions where xFindFunction returns a value of at least423 ** SQLITE_INDEX_CONSTRAINT_FUNCTION.424 **425 ** OVERLOADED(vtab_column,expression)426 **427 ** Historically, xFindFunction expected to see lower-case function428 ** names. But for this use case, xFindFunction is expected to deal429 ** with function names in an arbitrary case.430 */431 pCol = pList->a[0].pExpr;432 assert( pCol->op!=TK_COLUMN || ExprUseYTab(pCol) );433 assert( pCol->op!=TK_COLUMN || (ExprUseYTab(pCol) && pCol->y.pTab!=0) );434 if( ExprIsVtab(pCol) ){435 sqlite3_vtab *pVtab;436 sqlite3_module *pMod;437 void (*xNotUsed)(sqlite3_context*,int,sqlite3_value**);438 void *pNotUsed;439 pVtab = sqlite3GetVTable(db, pCol->y.pTab)->pVtab;440 assert( pVtab!=0 );441 assert( pVtab->pModule!=0 );442 assert( !ExprHasProperty(pExpr, EP_IntValue) );443 pMod = (sqlite3_module *)pVtab->pModule;444 if( pMod->xFindFunction!=0 ){445 i = pMod->xFindFunction(pVtab,2, pExpr->u.zToken, &xNotUsed, &pNotUsed);446 if( i>=SQLITE_INDEX_CONSTRAINT_FUNCTION ){447 *peOp2 = i;448 *ppRight = pList->a[1].pExpr;449 *ppLeft = pCol;450 return 1;451 }452 }453 }454 }else if( pExpr->op>=TK_EQ ){455 /* Comparison operators are a common case. Save a few comparisons for456 ** that common case by terminating early. */457 assert( TK_NE < TK_EQ );458 assert( TK_ISNOT < TK_EQ );459 assert( TK_NOTNULL < TK_EQ );460 return 0;461 }else if( pExpr->op==TK_NE || pExpr->op==TK_ISNOT || pExpr->op==TK_NOTNULL ){462 int res = 0;463 Expr *pLeft = pExpr->pLeft;464 Expr *pRight = pExpr->pRight;465 assert( pLeft->op!=TK_COLUMN || (ExprUseYTab(pLeft) && pLeft->y.pTab!=0) );466 if( ExprIsVtab(pLeft) ){467 res++;468 }469 assert( pRight==0 || pRight->op!=TK_COLUMN470 || (ExprUseYTab(pRight) && pRight->y.pTab!=0) );471 if( pRight && ExprIsVtab(pRight) ){472 res++;473 SWAP(Expr*, pLeft, pRight);474 }475 *ppLeft = pLeft;476 *ppRight = pRight;477 if( pExpr->op==TK_NE ) *peOp2 = SQLITE_INDEX_CONSTRAINT_NE;478 if( pExpr->op==TK_ISNOT ) *peOp2 = SQLITE_INDEX_CONSTRAINT_ISNOT;479 if( pExpr->op==TK_NOTNULL ) *peOp2 = SQLITE_INDEX_CONSTRAINT_ISNOTNULL;480 return res;481 }482 return 0;483}484#endif /* SQLITE_OMIT_VIRTUALTABLE */485 486/*487** If the pBase expression originated in the ON or USING clause of488** a join, then transfer the appropriate markings over to derived.489*/490static void transferJoinMarkings(Expr *pDerived, Expr *pBase){491 if( pDerived && ExprHasProperty(pBase, EP_OuterON|EP_InnerON) ){492 pDerived->flags |= pBase->flags & (EP_OuterON|EP_InnerON);493 pDerived->w.iJoin = pBase->w.iJoin;494 }495}496 497/*498** Mark term iChild as being a child of term iParent499*/500static void markTermAsChild(WhereClause *pWC, int iChild, int iParent){501 pWC->a[iChild].iParent = iParent;502 pWC->a[iChild].truthProb = pWC->a[iParent].truthProb;503 pWC->a[iParent].nChild++;504}505 506/*507** Return the N-th AND-connected subterm of pTerm. Or if pTerm is not508** a conjunction, then return just pTerm when N==0. If N is exceeds509** the number of available subterms, return NULL.510*/511static WhereTerm *whereNthSubterm(WhereTerm *pTerm, int N){512 if( pTerm->eOperator!=WO_AND ){513 return N==0 ? pTerm : 0;514 }515 if( N<pTerm->u.pAndInfo->wc.nTerm ){516 return &pTerm->u.pAndInfo->wc.a[N];517 }518 return 0;519}520 521/*522** Subterms pOne and pTwo are contained within WHERE clause pWC. The523** two subterms are in disjunction - they are OR-ed together.524**525** If these two terms are both of the form: "A op B" with the same526** A and B values but different operators and if the operators are527** compatible (if one is = and the other is <, for example) then528** add a new virtual AND term to pWC that is the combination of the529** two.530**531** Some examples:532**533** x<y OR x=y --> x<=y534** x=y OR x=y --> x=y535** x<=y OR x<y --> x<=y536**537** The following is NOT generated:538**539** x<y OR x>y --> x!=y 540*/541static void whereCombineDisjuncts(542 SrcList *pSrc, /* the FROM clause */543 WhereClause *pWC, /* The complete WHERE clause */544 WhereTerm *pOne, /* First disjunct */545 WhereTerm *pTwo /* Second disjunct */546){547 u16 eOp = pOne->eOperator | pTwo->eOperator;548 sqlite3 *db; /* Database connection (for malloc) */549 Expr *pNew; /* New virtual expression */550 int op; /* Operator for the combined expression */551 int idxNew; /* Index in pWC of the next virtual term */552 553 if( (pOne->wtFlags | pTwo->wtFlags) & TERM_VNULL ) return;554 if( (pOne->eOperator & (WO_EQ|WO_LT|WO_LE|WO_GT|WO_GE))==0 ) return;555 if( (pTwo->eOperator & (WO_EQ|WO_LT|WO_LE|WO_GT|WO_GE))==0 ) return;556 if( (eOp & (WO_EQ|WO_LT|WO_LE))!=eOp557 && (eOp & (WO_EQ|WO_GT|WO_GE))!=eOp ) return;558 assert( pOne->pExpr->pLeft!=0 && pOne->pExpr->pRight!=0 );559 assert( pTwo->pExpr->pLeft!=0 && pTwo->pExpr->pRight!=0 );560 if( sqlite3ExprCompare(0,pOne->pExpr->pLeft, pTwo->pExpr->pLeft, -1) ) return;561 if( sqlite3ExprCompare(0,pOne->pExpr->pRight, pTwo->pExpr->pRight,-1) )return;562 /* If we reach this point, it means the two subterms can be combined */563 if( (eOp & (eOp-1))!=0 ){564 if( eOp & (WO_LT|WO_LE) ){565 eOp = WO_LE;566 }else{567 assert( eOp & (WO_GT|WO_GE) );568 eOp = WO_GE;569 }570 }571 db = pWC->pWInfo->pParse->db;572 pNew = sqlite3ExprDup(db, pOne->pExpr, 0);573 if( pNew==0 ) return;574 for(op=TK_EQ; eOp!=(WO_EQ<<(op-TK_EQ)); op++){ assert( op<TK_GE ); }575 pNew->op = op;576 idxNew = whereClauseInsert(pWC, pNew, TERM_VIRTUAL|TERM_DYNAMIC);577 exprAnalyze(pSrc, pWC, idxNew);578}579 580#if !defined(SQLITE_OMIT_OR_OPTIMIZATION) && !defined(SQLITE_OMIT_SUBQUERY)581/*582** Analyze a term that consists of two or more OR-connected583** subterms. So in:584**585** ... WHERE (a=5) AND (b=7 OR c=9 OR d=13) AND (d=13)586** ^^^^^^^^^^^^^^^^^^^^587**588** This routine analyzes terms such as the middle term in the above example.589** A WhereOrTerm object is computed and attached to the term under590** analysis, regardless of the outcome of the analysis. Hence:591**592** WhereTerm.wtFlags |= TERM_ORINFO593** WhereTerm.u.pOrInfo = a dynamically allocated WhereOrTerm object594**595** The term being analyzed must have two or more of OR-connected subterms.596** A single subterm might be a set of AND-connected sub-subterms.597** Examples of terms under analysis:598**599** (A) t1.x=t2.y OR t1.x=t2.z OR t1.y=15 OR t1.z=t3.a+5600** (B) x=expr1 OR expr2=x OR x=expr3601** (C) t1.x=t2.y OR (t1.x=t2.z AND t1.y=15)602** (D) x=expr1 OR (y>11 AND y<22 AND z LIKE '*hello*')603** (E) (p.a=1 AND q.b=2 AND r.c=3) OR (p.x=4 AND q.y=5 AND r.z=6)604** (F) x>A OR (x=A AND y>=B)605**606** CASE 1:607**608** If all subterms are of the form T.C=expr for some single column of C and609** a single table T (as shown in example B above) then create a new virtual610** term that is an equivalent IN expression. In other words, if the term611** being analyzed is:612**613** x = expr1 OR expr2 = x OR x = expr3614**615** then create a new virtual term like this:616**617** x IN (expr1,expr2,expr3)618**619** CASE 2:620**621** If there are exactly two disjuncts and one side has x>A and the other side622** has x=A (for the same x and A) then add a new virtual conjunct term to the623** WHERE clause of the form "x>=A". Example:624**625** x>A OR (x=A AND y>B) adds: x>=A626**627** The added conjunct can sometimes be helpful in query planning.628**629** CASE 3:630**631** If all subterms are indexable by a single table T, then set632**633** WhereTerm.eOperator = WO_OR634** WhereTerm.u.pOrInfo->indexable |= the cursor number for table T635**636** A subterm is "indexable" if it is of the form637** "T.C <op> <expr>" where C is any column of table T and638** <op> is one of "=", "<", "<=", ">", ">=", "IS NULL", or "IN".639** A subterm is also indexable if it is an AND of two or more640** subsubterms at least one of which is indexable. Indexable AND641** subterms have their eOperator set to WO_AND and they have642** u.pAndInfo set to a dynamically allocated WhereAndTerm object.643**644** From another point of view, "indexable" means that the subterm could645** potentially be used with an index if an appropriate index exists.646** This analysis does not consider whether or not the index exists; that647** is decided elsewhere. This analysis only looks at whether subterms648** appropriate for indexing exist.649**650** All examples A through E above satisfy case 3. But if a term651** also satisfies case 1 (such as B) we know that the optimizer will652** always prefer case 1, so in that case we pretend that case 3 is not653** satisfied.654**655** It might be the case that multiple tables are indexable. For example,656** (E) above is indexable on tables P, Q, and R.657**658** Terms that satisfy case 3 are candidates for lookup by using659** separate indices to find rowids for each subterm and composing660** the union of all rowids using a RowSet object. This is similar661** to "bitmap indices" in other database engines.662**663** OTHERWISE:664**665** If none of cases 1, 2, or 3 apply, then leave the eOperator set to666** zero. This term is not useful for search.667*/668static void exprAnalyzeOrTerm(669 SrcList *pSrc, /* the FROM clause */670 WhereClause *pWC, /* the complete WHERE clause */671 int idxTerm /* Index of the OR-term to be analyzed */672){673 WhereInfo *pWInfo = pWC->pWInfo; /* WHERE clause processing context */674 Parse *pParse = pWInfo->pParse; /* Parser context */675 sqlite3 *db = pParse->db; /* Database connection */676 WhereTerm *pTerm = &pWC->a[idxTerm]; /* The term to be analyzed */677 Expr *pExpr = pTerm->pExpr; /* The expression of the term */678 int i; /* Loop counters */679 WhereClause *pOrWc; /* Breakup of pTerm into subterms */680 WhereTerm *pOrTerm; /* A Sub-term within the pOrWc */681 WhereOrInfo *pOrInfo; /* Additional information associated with pTerm */682 Bitmask chngToIN; /* Tables that might satisfy case 1 */683 Bitmask indexable; /* Tables that are indexable, satisfying case 2 */684 685 /*686 ** Break the OR clause into its separate subterms. The subterms are687 ** stored in a WhereClause structure containing within the WhereOrInfo688 ** object that is attached to the original OR clause term.689 */690 assert( (pTerm->wtFlags & (TERM_DYNAMIC|TERM_ORINFO|TERM_ANDINFO))==0 );691 assert( pExpr->op==TK_OR );692 pTerm->u.pOrInfo = pOrInfo = sqlite3DbMallocZero(db, sizeof(*pOrInfo));693 if( pOrInfo==0 ) return;694 pTerm->wtFlags |= TERM_ORINFO;695 pOrWc = &pOrInfo->wc;696 memset(pOrWc->aStatic, 0, sizeof(pOrWc->aStatic));697 sqlite3WhereClauseInit(pOrWc, pWInfo);698 sqlite3WhereSplit(pOrWc, pExpr, TK_OR);699 sqlite3WhereExprAnalyze(pSrc, pOrWc);700 if( db->mallocFailed ) return;701 assert( pOrWc->nTerm>=2 );702 703 /*704 ** Compute the set of tables that might satisfy cases 1 or 3.705 */706 indexable = ~(Bitmask)0;707 chngToIN = ~(Bitmask)0;708 for(i=pOrWc->nTerm-1, pOrTerm=pOrWc->a; i>=0 && indexable; i--, pOrTerm++){709 if( (pOrTerm->eOperator & WO_SINGLE)==0 ){710 WhereAndInfo *pAndInfo;711 assert( (pOrTerm->wtFlags & (TERM_ANDINFO|TERM_ORINFO))==0 );712 chngToIN = 0;713 pAndInfo = sqlite3DbMallocRawNN(db, sizeof(*pAndInfo));714 if( pAndInfo ){715 WhereClause *pAndWC;716 WhereTerm *pAndTerm;717 int j;718 Bitmask b = 0;719 pOrTerm->u.pAndInfo = pAndInfo;720 pOrTerm->wtFlags |= TERM_ANDINFO;721 pOrTerm->eOperator = WO_AND;722 pOrTerm->leftCursor = -1;723 pAndWC = &pAndInfo->wc;724 memset(pAndWC->aStatic, 0, sizeof(pAndWC->aStatic));725 sqlite3WhereClauseInit(pAndWC, pWC->pWInfo);726 sqlite3WhereSplit(pAndWC, pOrTerm->pExpr, TK_AND);727 sqlite3WhereExprAnalyze(pSrc, pAndWC);728 pAndWC->pOuter = pWC;729 if( !db->mallocFailed ){730 for(j=0, pAndTerm=pAndWC->a; j<pAndWC->nTerm; j++, pAndTerm++){731 assert( pAndTerm->pExpr );732 if( allowedOp(pAndTerm->pExpr->op)733 || pAndTerm->eOperator==WO_AUX734 ){735 b |= sqlite3WhereGetMask(&pWInfo->sMaskSet, pAndTerm->leftCursor);736 }737 }738 }739 indexable &= b;740 }741 }else if( pOrTerm->wtFlags & TERM_COPIED ){742 /* Skip this term for now. We revisit it when we process the743 ** corresponding TERM_VIRTUAL term */744 }else{745 Bitmask b;746 b = sqlite3WhereGetMask(&pWInfo->sMaskSet, pOrTerm->leftCursor);747 if( pOrTerm->wtFlags & TERM_VIRTUAL ){748 WhereTerm *pOther = &pOrWc->a[pOrTerm->iParent];749 b |= sqlite3WhereGetMask(&pWInfo->sMaskSet, pOther->leftCursor);750 }751 indexable &= b;752 if( (pOrTerm->eOperator & WO_EQ)==0 ){753 chngToIN = 0;754 }else{755 chngToIN &= b;756 }757 }758 }759 760 /*761 ** Record the set of tables that satisfy case 3. The set might be762 ** empty.763 */764 pOrInfo->indexable = indexable;765 pTerm->eOperator = WO_OR;766 pTerm->leftCursor = -1;767 if( indexable ){768 pWC->hasOr = 1;769 }770 771 /* For a two-way OR, attempt to implementation case 2.772 */773 if( indexable && pOrWc->nTerm==2 ){774 int iOne = 0;775 WhereTerm *pOne;776 while( (pOne = whereNthSubterm(&pOrWc->a[0],iOne++))!=0 ){777 int iTwo = 0;778 WhereTerm *pTwo;779 while( (pTwo = whereNthSubterm(&pOrWc->a[1],iTwo++))!=0 ){780 whereCombineDisjuncts(pSrc, pWC, pOne, pTwo);781 }782 }783 }784 785 /*786 ** chngToIN holds a set of tables that *might* satisfy case 1. But787 ** we have to do some additional checking to see if case 1 really788 ** is satisfied.789 **790 ** chngToIN will hold either 0, 1, or 2 bits. The 0-bit case means791 ** that there is no possibility of transforming the OR clause into an792 ** IN operator because one or more terms in the OR clause contain793 ** something other than == on a column in the single table. The 1-bit794 ** case means that every term of the OR clause is of the form795 ** "table.column=expr" for some single table. The one bit that is set796 ** will correspond to the common table. We still need to check to make797 ** sure the same column is used on all terms. The 2-bit case is when798 ** the all terms are of the form "table1.column=table2.column". It799 ** might be possible to form an IN operator with either table1.column800 ** or table2.column as the LHS if either is common to every term of801 ** the OR clause.802 **803 ** Note that terms of the form "table.column1=table.column2" (the804 ** same table on both sizes of the ==) cannot be optimized.805 */806 if( chngToIN ){807 int okToChngToIN = 0; /* True if the conversion to IN is valid */808 int iColumn = -1; /* Column index on lhs of IN operator */809 int iCursor = -1; /* Table cursor common to all terms */810 int j = 0; /* Loop counter */811 812 /* Search for a table and column that appears on one side or the813 ** other of the == operator in every subterm. That table and column814 ** will be recorded in iCursor and iColumn. There might not be any815 ** such table and column. Set okToChngToIN if an appropriate table816 ** and column is found but leave okToChngToIN false if not found.817 */818 for(j=0; j<2 && !okToChngToIN; j++){819 Expr *pLeft = 0;820 pOrTerm = pOrWc->a;821 for(i=pOrWc->nTerm-1; i>=0; i--, pOrTerm++){822 assert( pOrTerm->eOperator & WO_EQ );823 pOrTerm->wtFlags &= ~TERM_OK;824 if( pOrTerm->leftCursor==iCursor ){825 /* This is the 2-bit case and we are on the second iteration and826 ** current term is from the first iteration. So skip this term. */827 assert( j==1 );828 continue;829 }830 if( (chngToIN & sqlite3WhereGetMask(&pWInfo->sMaskSet,831 pOrTerm->leftCursor))==0 ){832 /* This term must be of the form t1.a==t2.b where t2 is in the833 ** chngToIN set but t1 is not. This term will be either preceded834 ** or followed by an inverted copy (t2.b==t1.a). Skip this term835 ** and use its inversion. */836 testcase( pOrTerm->wtFlags & TERM_COPIED );837 testcase( pOrTerm->wtFlags & TERM_VIRTUAL );838 assert( pOrTerm->wtFlags & (TERM_COPIED|TERM_VIRTUAL) );839 continue;840 }841 assert( (pOrTerm->eOperator & (WO_OR|WO_AND))==0 );842 iColumn = pOrTerm->u.x.leftColumn;843 iCursor = pOrTerm->leftCursor;844 pLeft = pOrTerm->pExpr->pLeft;845 break;846 }847 if( i<0 ){848 /* No candidate table+column was found. This can only occur849 ** on the second iteration */850 assert( j==1 );851 assert( IsPowerOfTwo(chngToIN) );852 assert( chngToIN==sqlite3WhereGetMask(&pWInfo->sMaskSet, iCursor) );853 break;854 }855 testcase( j==1 );856 857 /* We have found a candidate table and column. Check to see if that858 ** table and column is common to every term in the OR clause */859 okToChngToIN = 1;860 for(; i>=0 && okToChngToIN; i--, pOrTerm++){861 assert( pOrTerm->eOperator & WO_EQ );862 assert( (pOrTerm->eOperator & (WO_OR|WO_AND))==0 );863 if( pOrTerm->leftCursor!=iCursor ){864 pOrTerm->wtFlags &= ~TERM_OK;865 }else if( pOrTerm->u.x.leftColumn!=iColumn || (iColumn==XN_EXPR866 && sqlite3ExprCompare(pParse, pOrTerm->pExpr->pLeft, pLeft, -1)867 )){868 okToChngToIN = 0;869 }else{870 int affLeft, affRight;871 /* If the right-hand side is also a column, then the affinities872 ** of both right and left sides must be such that no type873 ** conversions are required on the right. (Ticket #2249)874 */875 affRight = sqlite3ExprAffinity(pOrTerm->pExpr->pRight);876 affLeft = sqlite3ExprAffinity(pOrTerm->pExpr->pLeft);877 if( affRight!=0 && affRight!=affLeft ){878 okToChngToIN = 0;879 }else{880 pOrTerm->wtFlags |= TERM_OK;881 }882 }883 }884 }885 886 /* At this point, okToChngToIN is true if original pTerm satisfies887 ** case 1. In that case, construct a new virtual term that is888 ** pTerm converted into an IN operator.889 */890 if( okToChngToIN ){891 Expr *pDup; /* A transient duplicate expression */892 ExprList *pList = 0; /* The RHS of the IN operator */893 Expr *pLeft = 0; /* The LHS of the IN operator */894 Expr *pNew; /* The complete IN operator */895 896 for(i=pOrWc->nTerm-1, pOrTerm=pOrWc->a; i>=0; i--, pOrTerm++){897 if( (pOrTerm->wtFlags & TERM_OK)==0 ) continue;898 assert( pOrTerm->eOperator & WO_EQ );899 assert( (pOrTerm->eOperator & (WO_OR|WO_AND))==0 );900 assert( pOrTerm->leftCursor==iCursor );901 assert( pOrTerm->u.x.leftColumn==iColumn );902 pDup = sqlite3ExprDup(db, pOrTerm->pExpr->pRight, 0);903 pList = sqlite3ExprListAppend(pWInfo->pParse, pList, pDup);904 pLeft = pOrTerm->pExpr->pLeft;905 }906 assert( pLeft!=0 );907 pDup = sqlite3ExprDup(db, pLeft, 0);908 pNew = sqlite3PExpr(pParse, TK_IN, pDup, 0);909 if( pNew ){910 int idxNew;911 transferJoinMarkings(pNew, pExpr);912 assert( ExprUseXList(pNew) );913 pNew->x.pList = pList;914 idxNew = whereClauseInsert(pWC, pNew, TERM_VIRTUAL|TERM_DYNAMIC);915 testcase( idxNew==0 );916 exprAnalyze(pSrc, pWC, idxNew);917 /* pTerm = &pWC->a[idxTerm]; // would be needed if pTerm where reused */918 markTermAsChild(pWC, idxNew, idxTerm);919 }else{920 sqlite3ExprListDelete(db, pList);921 }922 }923 }924}925#endif /* !SQLITE_OMIT_OR_OPTIMIZATION && !SQLITE_OMIT_SUBQUERY */926 927/*928** We already know that pExpr is a binary operator where both operands are929** column references. This routine checks to see if pExpr is an equivalence930** relation:931** 1. The SQLITE_Transitive optimization must be enabled932** 2. Must be either an == or an IS operator933** 3. Not originating in the ON clause of an OUTER JOIN934** 4. The operator is not IS or else the query does not contain RIGHT JOIN935** 5. The affinities of A and B must be compatible936** 6a. Both operands use the same collating sequence OR937** 6b. The overall collating sequence is BINARY938** If this routine returns TRUE, that means that the RHS can be substituted939** for the LHS anyplace else in the WHERE clause where the LHS column occurs.940** This is an optimization. No harm comes from returning 0. But if 1 is941** returned when it should not be, then incorrect answers might result.942*/943static int termIsEquivalence(Parse *pParse, Expr *pExpr, SrcList *pSrc){944 char aff1, aff2;945 CollSeq *pColl;946 if( !OptimizationEnabled(pParse->db, SQLITE_Transitive) ) return 0; /* (1) */947 if( pExpr->op!=TK_EQ && pExpr->op!=TK_IS ) return 0; /* (2) */948 if( ExprHasProperty(pExpr, EP_OuterON) ) return 0; /* (3) */949 assert( pSrc!=0 );950 if( pExpr->op==TK_IS951 && pSrc->nSrc>=2952 && (pSrc->a[0].fg.jointype & JT_LTORJ)!=0953 ){954 return 0; /* (4) */955 }956 aff1 = sqlite3ExprAffinity(pExpr->pLeft);957 aff2 = sqlite3ExprAffinity(pExpr->pRight);958 if( aff1!=aff2959 && (!sqlite3IsNumericAffinity(aff1) || !sqlite3IsNumericAffinity(aff2))960 ){961 return 0; /* (5) */962 }963 pColl = sqlite3ExprCompareCollSeq(pParse, pExpr);964 if( !sqlite3IsBinary(pColl)965 && !sqlite3ExprCollSeqMatch(pParse, pExpr->pLeft, pExpr->pRight)966 ){967 return 0; /* (6) */968 }969 return 1;970}971 972/*973** Recursively walk the expressions of a SELECT statement and generate974** a bitmask indicating which tables are used in that expression975** tree.976*/977static Bitmask exprSelectUsage(WhereMaskSet *pMaskSet, Select *pS){978 Bitmask mask = 0;979 while( pS ){980 SrcList *pSrc = pS->pSrc;981 mask |= sqlite3WhereExprListUsage(pMaskSet, pS->pEList);982 mask |= sqlite3WhereExprListUsage(pMaskSet, pS->pGroupBy);983 mask |= sqlite3WhereExprListUsage(pMaskSet, pS->pOrderBy);984 mask |= sqlite3WhereExprUsage(pMaskSet, pS->pWhere);985 mask |= sqlite3WhereExprUsage(pMaskSet, pS->pHaving);986 if( ALWAYS(pSrc!=0) ){987 int i;988 for(i=0; i<pSrc->nSrc; i++){989 if( pSrc->a[i].fg.isSubquery ){990 mask |= exprSelectUsage(pMaskSet, pSrc->a[i].u4.pSubq->pSelect);991 }992 if( pSrc->a[i].fg.isUsing==0 ){993 mask |= sqlite3WhereExprUsage(pMaskSet, pSrc->a[i].u3.pOn);994 }995 if( pSrc->a[i].fg.isTabFunc ){996 mask |= sqlite3WhereExprListUsage(pMaskSet, pSrc->a[i].u1.pFuncArg);997 }998 }999 }1000 pS = pS->pPrior;1001 }1002 return mask;1003}1004 1005/*1006** Expression pExpr is one operand of a comparison operator that might1007** be useful for indexing. This routine checks to see if pExpr appears1008** in any index. Return TRUE (1) if pExpr is an indexed term and return1009** FALSE (0) if not. If TRUE is returned, also set aiCurCol[0] to the cursor1010** number of the table that is indexed and aiCurCol[1] to the column number1011** of the column that is indexed, or XN_EXPR (-2) if an expression is being1012** indexed.1013**1014** If pExpr is a TK_COLUMN column reference, then this routine always returns1015** true even if that particular column is not indexed, because the column1016** might be added to an automatic index later.1017*/1018static SQLITE_NOINLINE int exprMightBeIndexed2(1019 SrcList *pFrom, /* The FROM clause */1020 int *aiCurCol, /* Write the referenced table cursor and column here */1021 Expr *pExpr, /* An operand of a comparison operator */1022 int j /* Start looking with the j-th pFrom entry */1023){1024 Index *pIdx;1025 int i;1026 int iCur;1027 do{1028 iCur = pFrom->a[j].iCursor;1029 for(pIdx=pFrom->a[j].pSTab->pIndex; pIdx; pIdx=pIdx->pNext){1030 if( pIdx->aColExpr==0 ) continue;1031 for(i=0; i<pIdx->nKeyCol; i++){1032 if( pIdx->aiColumn[i]!=XN_EXPR ) continue;1033 assert( pIdx->bHasExpr );1034 if( sqlite3ExprCompareSkip(pExpr,pIdx->aColExpr->a[i].pExpr,iCur)==01035 && !sqlite3ExprIsConstant(0,pIdx->aColExpr->a[i].pExpr)1036 ){1037 aiCurCol[0] = iCur;1038 aiCurCol[1] = XN_EXPR;1039 return 1;1040 }1041 }1042 }1043 }while( ++j < pFrom->nSrc );1044 return 0;1045}1046static int exprMightBeIndexed(1047 SrcList *pFrom, /* The FROM clause */1048 int *aiCurCol, /* Write the referenced table cursor & column here */1049 Expr *pExpr, /* An operand of a comparison operator */1050 int op /* The specific comparison operator */1051){1052 int i;1053 1054 /* If this expression is a vector to the left or right of a1055 ** inequality constraint (>, <, >= or <=), perform the processing1056 ** on the first element of the vector. */1057 assert( TK_GT+1==TK_LE && TK_GT+2==TK_LT && TK_GT+3==TK_GE );1058 assert( TK_IS<TK_GE && TK_ISNULL<TK_GE && TK_IN<TK_GE );1059 assert( op<=TK_GE );1060 if( pExpr->op==TK_VECTOR && (op>=TK_GT && ALWAYS(op<=TK_GE)) ){1061 assert( ExprUseXList(pExpr) );1062 pExpr = pExpr->x.pList->a[0].pExpr;1063 }1064 1065 if( pExpr->op==TK_COLUMN ){1066 aiCurCol[0] = pExpr->iTable;1067 aiCurCol[1] = pExpr->iColumn;1068 return 1;1069 }1070 1071 for(i=0; i<pFrom->nSrc; i++){1072 Index *pIdx;1073 for(pIdx=pFrom->a[i].pSTab->pIndex; pIdx; pIdx=pIdx->pNext){1074 if( pIdx->aColExpr ){1075 return exprMightBeIndexed2(pFrom,aiCurCol,pExpr,i);1076 }1077 }1078 }1079 return 0;1080}1081 1082 1083/*1084** The input to this routine is an WhereTerm structure with only the1085** "pExpr" field filled in. The job of this routine is to analyze the1086** subexpression and populate all the other fields of the WhereTerm1087** structure.1088**1089** If the expression is of the form "<expr> <op> X" it gets commuted1090** to the standard form of "X <op> <expr>".1091**1092** If the expression is of the form "X <op> Y" where both X and Y are1093** columns, then the original expression is unchanged and a new virtual1094** term of the form "Y <op> X" is added to the WHERE clause and1095** analyzed separately. The original term is marked with TERM_COPIED1096** and the new term is marked with TERM_DYNAMIC (because it's pExpr1097** needs to be freed with the WhereClause) and TERM_VIRTUAL (because it1098** is a commuted copy of a prior term.) The original term has nChild=11099** and the copy has idxParent set to the index of the original term.1100*/1101static void exprAnalyze(1102 SrcList *pSrc, /* the FROM clause */1103 WhereClause *pWC, /* the WHERE clause */1104 int idxTerm /* Index of the term to be analyzed */1105){1106 WhereInfo *pWInfo = pWC->pWInfo; /* WHERE clause processing context */1107 WhereTerm *pTerm; /* The term to be analyzed */1108 WhereMaskSet *pMaskSet; /* Set of table index masks */1109 Expr *pExpr; /* The expression to be analyzed */1110 Bitmask prereqLeft; /* Prerequisites of the pExpr->pLeft */1111 Bitmask prereqAll; /* Prerequisites of pExpr */1112 Bitmask extraRight = 0; /* Extra dependencies on LEFT JOIN */1113 Expr *pStr1 = 0; /* RHS of LIKE/GLOB operator */1114 int isComplete = 0; /* RHS of LIKE/GLOB ends with wildcard */1115 int noCase = 0; /* uppercase equivalent to lowercase */1116 int op; /* Top-level operator. pExpr->op */1117 Parse *pParse = pWInfo->pParse; /* Parsing context */1118 sqlite3 *db = pParse->db; /* Database connection */1119 unsigned char eOp2 = 0; /* op2 value for LIKE/REGEXP/GLOB */1120 int nLeft; /* Number of elements on left side vector */1121 1122 if( db->mallocFailed ){1123 return;1124 }1125 assert( pWC->nTerm > idxTerm );1126 pTerm = &pWC->a[idxTerm];1127#ifdef SQLITE_DEBUG1128 pTerm->iTerm = idxTerm;1129#endif1130 pMaskSet = &pWInfo->sMaskSet;1131 pExpr = pTerm->pExpr;1132 assert( pExpr!=0 ); /* Because malloc() has not failed */1133 assert( pExpr->op!=TK_AS && pExpr->op!=TK_COLLATE );1134 pMaskSet->bVarSelect = 0;1135 prereqLeft = sqlite3WhereExprUsage(pMaskSet, pExpr->pLeft);1136 op = pExpr->op;1137 if( op==TK_IN ){1138 assert( pExpr->pRight==0 );1139 if( sqlite3ExprCheckIN(pParse, pExpr) ) return;1140 if( ExprUseXSelect(pExpr) ){1141 pTerm->prereqRight = exprSelectUsage(pMaskSet, pExpr->x.pSelect);1142 }else{1143 pTerm->prereqRight = sqlite3WhereExprListUsage(pMaskSet, pExpr->x.pList);1144 }1145 prereqAll = prereqLeft | pTerm->prereqRight;1146 }else{1147 pTerm->prereqRight = sqlite3WhereExprUsage(pMaskSet, pExpr->pRight);1148 if( pExpr->pLeft==01149 || ExprHasProperty(pExpr, EP_xIsSelect|EP_IfNullRow)1150 || pExpr->x.pList!=01151 ){1152 prereqAll = sqlite3WhereExprUsageNN(pMaskSet, pExpr);1153 }else{1154 prereqAll = prereqLeft | pTerm->prereqRight;1155 }1156 }1157 if( pMaskSet->bVarSelect ) pTerm->wtFlags |= TERM_VARSELECT;1158 1159#ifdef SQLITE_DEBUG1160 if( prereqAll!=sqlite3WhereExprUsageNN(pMaskSet, pExpr) ){1161 printf("\n*** Incorrect prereqAll computed for:\n");1162 sqlite3TreeViewExpr(0,pExpr,0);1163 assert( 0 );1164 }1165#endif1166 1167 if( ExprHasProperty(pExpr, EP_OuterON|EP_InnerON) ){1168 Bitmask x = sqlite3WhereGetMask(pMaskSet, pExpr->w.iJoin);1169 if( ExprHasProperty(pExpr, EP_OuterON) ){1170 prereqAll |= x;1171 extraRight = x-1; /* ON clause terms may not be used with an index1172 ** on left table of a LEFT JOIN. Ticket #3015 */1173 }else if( (prereqAll>>1)>=x ){1174 ExprClearProperty(pExpr, EP_InnerON);1175 }1176 }1177 pTerm->prereqAll = prereqAll;1178 pTerm->leftCursor = -1;1179 pTerm->iParent = -1;1180 pTerm->eOperator = 0;1181 if( allowedOp(op) ){1182 int aiCurCol[2];1183 Expr *pLeft = sqlite3ExprSkipCollate(pExpr->pLeft);1184 Expr *pRight = sqlite3ExprSkipCollate(pExpr->pRight);1185 u16 opMask = (pTerm->prereqRight & prereqLeft)==0 ? WO_ALL : WO_EQUIV;1186 1187 if( pTerm->u.x.iField>0 ){1188 assert( op==TK_IN );1189 assert( pLeft->op==TK_VECTOR );1190 assert( ExprUseXList(pLeft) );1191 pLeft = pLeft->x.pList->a[pTerm->u.x.iField-1].pExpr;1192 }1193 1194 if( exprMightBeIndexed(pSrc, aiCurCol, pLeft, op) ){1195 pTerm->leftCursor = aiCurCol[0];1196 assert( (pTerm->eOperator & (WO_OR|WO_AND))==0 );1197 pTerm->u.x.leftColumn = aiCurCol[1];1198 pTerm->eOperator = operatorMask(op) & opMask;1199 }1200 if( op==TK_IS ) pTerm->wtFlags |= TERM_IS;