000001 /*
000002 ** 2015-06-08
000003 **
000004 ** The author disclaims copyright to this source code. In place of
000005 ** a legal notice, here is a blessing:
000006 **
000007 ** May you do good and not evil.
000008 ** May you find forgiveness for yourself and forgive others.
000009 ** May you share freely, never taking more than you give.
000010 **
000011 *************************************************************************
000012 ** This module contains C code that generates VDBE code used to process
000013 ** the WHERE clause of SQL statements.
000014 **
000015 ** This file was originally part of where.c but was split out to improve
000016 ** readability and editabiliity. This file contains utility routines for
000017 ** analyzing Expr objects in the WHERE clause.
000018 */
000019 #include "sqliteInt.h"
000020 #include "whereInt.h"
000021
000022 /* Forward declarations */
000023 static void exprAnalyze(SrcList*, WhereClause*, int);
000024
000025 /*
000026 ** Deallocate all memory associated with a WhereOrInfo object.
000027 */
000028 static void whereOrInfoDelete(sqlite3 *db, WhereOrInfo *p){
000029 sqlite3WhereClauseClear(&p->wc);
000030 sqlite3DbFree(db, p);
000031 }
000032
000033 /*
000034 ** Deallocate all memory associated with a WhereAndInfo object.
000035 */
000036 static void whereAndInfoDelete(sqlite3 *db, WhereAndInfo *p){
000037 sqlite3WhereClauseClear(&p->wc);
000038 sqlite3DbFree(db, p);
000039 }
000040
000041 /*
000042 ** Add a single new WhereTerm entry to the WhereClause object pWC.
000043 ** The new WhereTerm object is constructed from Expr p and with wtFlags.
000044 ** The index in pWC->a[] of the new WhereTerm is returned on success.
000045 ** 0 is returned if the new WhereTerm could not be added due to a memory
000046 ** allocation error. The memory allocation failure will be recorded in
000047 ** the db->mallocFailed flag so that higher-level functions can detect it.
000048 **
000049 ** This routine will increase the size of the pWC->a[] array as necessary.
000050 **
000051 ** If the wtFlags argument includes TERM_DYNAMIC, then responsibility
000052 ** for freeing the expression p is assumed by the WhereClause object pWC.
000053 ** This is true even if this routine fails to allocate a new WhereTerm.
000054 **
000055 ** WARNING: This routine might reallocate the space used to store
000056 ** WhereTerms. All pointers to WhereTerms should be invalidated after
000057 ** calling this routine. Such pointers may be reinitialized by referencing
000058 ** the pWC->a[] array.
000059 */
000060 static int whereClauseInsert(WhereClause *pWC, Expr *p, u16 wtFlags){
000061 WhereTerm *pTerm;
000062 int idx;
000063 testcase( wtFlags & TERM_VIRTUAL );
000064 if( pWC->nTerm>=pWC->nSlot ){
000065 WhereTerm *pOld = pWC->a;
000066 sqlite3 *db = pWC->pWInfo->pParse->db;
000067 pWC->a = sqlite3DbMallocRawNN(db, sizeof(pWC->a[0])*pWC->nSlot*2 );
000068 if( pWC->a==0 ){
000069 if( wtFlags & TERM_DYNAMIC ){
000070 sqlite3ExprDelete(db, p);
000071 }
000072 pWC->a = pOld;
000073 return 0;
000074 }
000075 memcpy(pWC->a, pOld, sizeof(pWC->a[0])*pWC->nTerm);
000076 if( pOld!=pWC->aStatic ){
000077 sqlite3DbFree(db, pOld);
000078 }
000079 pWC->nSlot = sqlite3DbMallocSize(db, pWC->a)/sizeof(pWC->a[0]);
000080 }
000081 pTerm = &pWC->a[idx = pWC->nTerm++];
000082 if( p && ExprHasProperty(p, EP_Unlikely) ){
000083 pTerm->truthProb = sqlite3LogEst(p->iTable) - 270;
000084 }else{
000085 pTerm->truthProb = 1;
000086 }
000087 pTerm->pExpr = sqlite3ExprSkipCollate(p);
000088 pTerm->wtFlags = wtFlags;
000089 pTerm->pWC = pWC;
000090 pTerm->iParent = -1;
000091 memset(&pTerm->eOperator, 0,
000092 sizeof(WhereTerm) - offsetof(WhereTerm,eOperator));
000093 return idx;
000094 }
000095
000096 /*
000097 ** Return TRUE if the given operator is one of the operators that is
000098 ** allowed for an indexable WHERE clause term. The allowed operators are
000099 ** "=", "<", ">", "<=", ">=", "IN", "IS", and "IS NULL"
000100 */
000101 static int allowedOp(int op){
000102 assert( TK_GT>TK_EQ && TK_GT<TK_GE );
000103 assert( TK_LT>TK_EQ && TK_LT<TK_GE );
000104 assert( TK_LE>TK_EQ && TK_LE<TK_GE );
000105 assert( TK_GE==TK_EQ+4 );
000106 return op==TK_IN || (op>=TK_EQ && op<=TK_GE) || op==TK_ISNULL || op==TK_IS;
000107 }
000108
000109 /*
000110 ** Commute a comparison operator. Expressions of the form "X op Y"
000111 ** are converted into "Y op X".
000112 **
000113 ** If left/right precedence rules come into play when determining the
000114 ** collating sequence, then COLLATE operators are adjusted to ensure
000115 ** that the collating sequence does not change. For example:
000116 ** "Y collate NOCASE op X" becomes "X op Y" because any collation sequence on
000117 ** the left hand side of a comparison overrides any collation sequence
000118 ** attached to the right. For the same reason the EP_Collate flag
000119 ** is not commuted.
000120 */
000121 static void exprCommute(Parse *pParse, Expr *pExpr){
000122 u16 expRight = (pExpr->pRight->flags & EP_Collate);
000123 u16 expLeft = (pExpr->pLeft->flags & EP_Collate);
000124 assert( allowedOp(pExpr->op) && pExpr->op!=TK_IN );
000125 if( expRight==expLeft ){
000126 /* Either X and Y both have COLLATE operator or neither do */
000127 if( expRight ){
000128 /* Both X and Y have COLLATE operators. Make sure X is always
000129 ** used by clearing the EP_Collate flag from Y. */
000130 pExpr->pRight->flags &= ~EP_Collate;
000131 }else if( sqlite3ExprCollSeq(pParse, pExpr->pLeft)!=0 ){
000132 /* Neither X nor Y have COLLATE operators, but X has a non-default
000133 ** collating sequence. So add the EP_Collate marker on X to cause
000134 ** it to be searched first. */
000135 pExpr->pLeft->flags |= EP_Collate;
000136 }
000137 }
000138 SWAP(Expr*,pExpr->pRight,pExpr->pLeft);
000139 if( pExpr->op>=TK_GT ){
000140 assert( TK_LT==TK_GT+2 );
000141 assert( TK_GE==TK_LE+2 );
000142 assert( TK_GT>TK_EQ );
000143 assert( TK_GT<TK_LE );
000144 assert( pExpr->op>=TK_GT && pExpr->op<=TK_GE );
000145 pExpr->op = ((pExpr->op-TK_GT)^2)+TK_GT;
000146 }
000147 }
000148
000149 /*
000150 ** Translate from TK_xx operator to WO_xx bitmask.
000151 */
000152 static u16 operatorMask(int op){
000153 u16 c;
000154 assert( allowedOp(op) );
000155 if( op==TK_IN ){
000156 c = WO_IN;
000157 }else if( op==TK_ISNULL ){
000158 c = WO_ISNULL;
000159 }else if( op==TK_IS ){
000160 c = WO_IS;
000161 }else{
000162 assert( (WO_EQ<<(op-TK_EQ)) < 0x7fff );
000163 c = (u16)(WO_EQ<<(op-TK_EQ));
000164 }
000165 assert( op!=TK_ISNULL || c==WO_ISNULL );
000166 assert( op!=TK_IN || c==WO_IN );
000167 assert( op!=TK_EQ || c==WO_EQ );
000168 assert( op!=TK_LT || c==WO_LT );
000169 assert( op!=TK_LE || c==WO_LE );
000170 assert( op!=TK_GT || c==WO_GT );
000171 assert( op!=TK_GE || c==WO_GE );
000172 assert( op!=TK_IS || c==WO_IS );
000173 return c;
000174 }
000175
000176
000177 #ifndef SQLITE_OMIT_LIKE_OPTIMIZATION
000178 /*
000179 ** Check to see if the given expression is a LIKE or GLOB operator that
000180 ** can be optimized using inequality constraints. Return TRUE if it is
000181 ** so and false if not.
000182 **
000183 ** In order for the operator to be optimizible, the RHS must be a string
000184 ** literal that does not begin with a wildcard. The LHS must be a column
000185 ** that may only be NULL, a string, or a BLOB, never a number. (This means
000186 ** that virtual tables cannot participate in the LIKE optimization.) The
000187 ** collating sequence for the column on the LHS must be appropriate for
000188 ** the operator.
000189 */
000190 static int isLikeOrGlob(
000191 Parse *pParse, /* Parsing and code generating context */
000192 Expr *pExpr, /* Test this expression */
000193 Expr **ppPrefix, /* Pointer to TK_STRING expression with pattern prefix */
000194 int *pisComplete, /* True if the only wildcard is % in the last character */
000195 int *pnoCase /* True if uppercase is equivalent to lowercase */
000196 ){
000197 const char *z = 0; /* String on RHS of LIKE operator */
000198 Expr *pRight, *pLeft; /* Right and left size of LIKE operator */
000199 ExprList *pList; /* List of operands to the LIKE operator */
000200 int c; /* One character in z[] */
000201 int cnt; /* Number of non-wildcard prefix characters */
000202 char wc[3]; /* Wildcard characters */
000203 sqlite3 *db = pParse->db; /* Database connection */
000204 sqlite3_value *pVal = 0;
000205 int op; /* Opcode of pRight */
000206 int rc; /* Result code to return */
000207
000208 if( !sqlite3IsLikeFunction(db, pExpr, pnoCase, wc) ){
000209 return 0;
000210 }
000211 #ifdef SQLITE_EBCDIC
000212 if( *pnoCase ) return 0;
000213 #endif
000214 pList = pExpr->x.pList;
000215 pLeft = pList->a[1].pExpr;
000216 if( pLeft->op!=TK_COLUMN
000217 || sqlite3ExprAffinity(pLeft)!=SQLITE_AFF_TEXT
000218 || IsVirtual(pLeft->pTab) /* Value might be numeric */
000219 ){
000220 /* IMP: R-02065-49465 The left-hand side of the LIKE or GLOB operator must
000221 ** be the name of an indexed column with TEXT affinity. */
000222 return 0;
000223 }
000224 assert( pLeft->iColumn!=(-1) ); /* Because IPK never has AFF_TEXT */
000225
000226 pRight = sqlite3ExprSkipCollate(pList->a[0].pExpr);
000227 op = pRight->op;
000228 if( op==TK_VARIABLE ){
000229 Vdbe *pReprepare = pParse->pReprepare;
000230 int iCol = pRight->iColumn;
000231 pVal = sqlite3VdbeGetBoundValue(pReprepare, iCol, SQLITE_AFF_BLOB);
000232 if( pVal && sqlite3_value_type(pVal)==SQLITE_TEXT ){
000233 z = (char *)sqlite3_value_text(pVal);
000234 }
000235 sqlite3VdbeSetVarmask(pParse->pVdbe, iCol);
000236 assert( pRight->op==TK_VARIABLE || pRight->op==TK_REGISTER );
000237 }else if( op==TK_STRING ){
000238 z = pRight->u.zToken;
000239 }
000240 if( z ){
000241 cnt = 0;
000242 while( (c=z[cnt])!=0 && c!=wc[0] && c!=wc[1] && c!=wc[2] ){
000243 cnt++;
000244 }
000245 if( cnt!=0 && 255!=(u8)z[cnt-1] ){
000246 Expr *pPrefix;
000247 *pisComplete = c==wc[0] && z[cnt+1]==0;
000248 pPrefix = sqlite3Expr(db, TK_STRING, z);
000249 if( pPrefix ) pPrefix->u.zToken[cnt] = 0;
000250 *ppPrefix = pPrefix;
000251 if( op==TK_VARIABLE ){
000252 Vdbe *v = pParse->pVdbe;
000253 sqlite3VdbeSetVarmask(v, pRight->iColumn);
000254 if( *pisComplete && pRight->u.zToken[1] ){
000255 /* If the rhs of the LIKE expression is a variable, and the current
000256 ** value of the variable means there is no need to invoke the LIKE
000257 ** function, then no OP_Variable will be added to the program.
000258 ** This causes problems for the sqlite3_bind_parameter_name()
000259 ** API. To work around them, add a dummy OP_Variable here.
000260 */
000261 int r1 = sqlite3GetTempReg(pParse);
000262 sqlite3ExprCodeTarget(pParse, pRight, r1);
000263 sqlite3VdbeChangeP3(v, sqlite3VdbeCurrentAddr(v)-1, 0);
000264 sqlite3ReleaseTempReg(pParse, r1);
000265 }
000266 }
000267 }else{
000268 z = 0;
000269 }
000270 }
000271
000272 rc = (z!=0);
000273 sqlite3ValueFree(pVal);
000274 return rc;
000275 }
000276 #endif /* SQLITE_OMIT_LIKE_OPTIMIZATION */
000277
000278
000279 #ifndef SQLITE_OMIT_VIRTUALTABLE
000280 /*
000281 ** Check to see if the given expression is of the form
000282 **
000283 ** column OP expr
000284 **
000285 ** where OP is one of MATCH, GLOB, LIKE or REGEXP and "column" is a
000286 ** column of a virtual table.
000287 **
000288 ** If it is then return TRUE. If not, return FALSE.
000289 */
000290 static int isMatchOfColumn(
000291 Expr *pExpr, /* Test this expression */
000292 unsigned char *peOp2 /* OUT: 0 for MATCH, or else an op2 value */
000293 ){
000294 static const struct Op2 {
000295 const char *zOp;
000296 unsigned char eOp2;
000297 } aOp[] = {
000298 { "match", SQLITE_INDEX_CONSTRAINT_MATCH },
000299 { "glob", SQLITE_INDEX_CONSTRAINT_GLOB },
000300 { "like", SQLITE_INDEX_CONSTRAINT_LIKE },
000301 { "regexp", SQLITE_INDEX_CONSTRAINT_REGEXP }
000302 };
000303 ExprList *pList;
000304 Expr *pCol; /* Column reference */
000305 int i;
000306
000307 if( pExpr->op!=TK_FUNCTION ){
000308 return 0;
000309 }
000310 pList = pExpr->x.pList;
000311 if( pList==0 || pList->nExpr!=2 ){
000312 return 0;
000313 }
000314 pCol = pList->a[1].pExpr;
000315 if( pCol->op!=TK_COLUMN || !IsVirtual(pCol->pTab) ){
000316 return 0;
000317 }
000318 for(i=0; i<ArraySize(aOp); i++){
000319 if( sqlite3StrICmp(pExpr->u.zToken, aOp[i].zOp)==0 ){
000320 *peOp2 = aOp[i].eOp2;
000321 return 1;
000322 }
000323 }
000324 return 0;
000325 }
000326 #endif /* SQLITE_OMIT_VIRTUALTABLE */
000327
000328 /*
000329 ** If the pBase expression originated in the ON or USING clause of
000330 ** a join, then transfer the appropriate markings over to derived.
000331 */
000332 static void transferJoinMarkings(Expr *pDerived, Expr *pBase){
000333 if( pDerived ){
000334 pDerived->flags |= pBase->flags & EP_FromJoin;
000335 pDerived->iRightJoinTable = pBase->iRightJoinTable;
000336 }
000337 }
000338
000339 /*
000340 ** Mark term iChild as being a child of term iParent
000341 */
000342 static void markTermAsChild(WhereClause *pWC, int iChild, int iParent){
000343 pWC->a[iChild].iParent = iParent;
000344 pWC->a[iChild].truthProb = pWC->a[iParent].truthProb;
000345 pWC->a[iParent].nChild++;
000346 }
000347
000348 /*
000349 ** Return the N-th AND-connected subterm of pTerm. Or if pTerm is not
000350 ** a conjunction, then return just pTerm when N==0. If N is exceeds
000351 ** the number of available subterms, return NULL.
000352 */
000353 static WhereTerm *whereNthSubterm(WhereTerm *pTerm, int N){
000354 if( pTerm->eOperator!=WO_AND ){
000355 return N==0 ? pTerm : 0;
000356 }
000357 if( N<pTerm->u.pAndInfo->wc.nTerm ){
000358 return &pTerm->u.pAndInfo->wc.a[N];
000359 }
000360 return 0;
000361 }
000362
000363 /*
000364 ** Subterms pOne and pTwo are contained within WHERE clause pWC. The
000365 ** two subterms are in disjunction - they are OR-ed together.
000366 **
000367 ** If these two terms are both of the form: "A op B" with the same
000368 ** A and B values but different operators and if the operators are
000369 ** compatible (if one is = and the other is <, for example) then
000370 ** add a new virtual AND term to pWC that is the combination of the
000371 ** two.
000372 **
000373 ** Some examples:
000374 **
000375 ** x<y OR x=y --> x<=y
000376 ** x=y OR x=y --> x=y
000377 ** x<=y OR x<y --> x<=y
000378 **
000379 ** The following is NOT generated:
000380 **
000381 ** x<y OR x>y --> x!=y
000382 */
000383 static void whereCombineDisjuncts(
000384 SrcList *pSrc, /* the FROM clause */
000385 WhereClause *pWC, /* The complete WHERE clause */
000386 WhereTerm *pOne, /* First disjunct */
000387 WhereTerm *pTwo /* Second disjunct */
000388 ){
000389 u16 eOp = pOne->eOperator | pTwo->eOperator;
000390 sqlite3 *db; /* Database connection (for malloc) */
000391 Expr *pNew; /* New virtual expression */
000392 int op; /* Operator for the combined expression */
000393 int idxNew; /* Index in pWC of the next virtual term */
000394
000395 if( (pOne->eOperator & (WO_EQ|WO_LT|WO_LE|WO_GT|WO_GE))==0 ) return;
000396 if( (pTwo->eOperator & (WO_EQ|WO_LT|WO_LE|WO_GT|WO_GE))==0 ) return;
000397 if( (eOp & (WO_EQ|WO_LT|WO_LE))!=eOp
000398 && (eOp & (WO_EQ|WO_GT|WO_GE))!=eOp ) return;
000399 assert( pOne->pExpr->pLeft!=0 && pOne->pExpr->pRight!=0 );
000400 assert( pTwo->pExpr->pLeft!=0 && pTwo->pExpr->pRight!=0 );
000401 if( sqlite3ExprCompare(pOne->pExpr->pLeft, pTwo->pExpr->pLeft, -1) ) return;
000402 if( sqlite3ExprCompare(pOne->pExpr->pRight, pTwo->pExpr->pRight, -1) )return;
000403 /* If we reach this point, it means the two subterms can be combined */
000404 if( (eOp & (eOp-1))!=0 ){
000405 if( eOp & (WO_LT|WO_LE) ){
000406 eOp = WO_LE;
000407 }else{
000408 assert( eOp & (WO_GT|WO_GE) );
000409 eOp = WO_GE;
000410 }
000411 }
000412 db = pWC->pWInfo->pParse->db;
000413 pNew = sqlite3ExprDup(db, pOne->pExpr, 0);
000414 if( pNew==0 ) return;
000415 for(op=TK_EQ; eOp!=(WO_EQ<<(op-TK_EQ)); op++){ assert( op<TK_GE ); }
000416 pNew->op = op;
000417 idxNew = whereClauseInsert(pWC, pNew, TERM_VIRTUAL|TERM_DYNAMIC);
000418 exprAnalyze(pSrc, pWC, idxNew);
000419 }
000420
000421 #if !defined(SQLITE_OMIT_OR_OPTIMIZATION) && !defined(SQLITE_OMIT_SUBQUERY)
000422 /*
000423 ** Analyze a term that consists of two or more OR-connected
000424 ** subterms. So in:
000425 **
000426 ** ... WHERE (a=5) AND (b=7 OR c=9 OR d=13) AND (d=13)
000427 ** ^^^^^^^^^^^^^^^^^^^^
000428 **
000429 ** This routine analyzes terms such as the middle term in the above example.
000430 ** A WhereOrTerm object is computed and attached to the term under
000431 ** analysis, regardless of the outcome of the analysis. Hence:
000432 **
000433 ** WhereTerm.wtFlags |= TERM_ORINFO
000434 ** WhereTerm.u.pOrInfo = a dynamically allocated WhereOrTerm object
000435 **
000436 ** The term being analyzed must have two or more of OR-connected subterms.
000437 ** A single subterm might be a set of AND-connected sub-subterms.
000438 ** Examples of terms under analysis:
000439 **
000440 ** (A) t1.x=t2.y OR t1.x=t2.z OR t1.y=15 OR t1.z=t3.a+5
000441 ** (B) x=expr1 OR expr2=x OR x=expr3
000442 ** (C) t1.x=t2.y OR (t1.x=t2.z AND t1.y=15)
000443 ** (D) x=expr1 OR (y>11 AND y<22 AND z LIKE '*hello*')
000444 ** (E) (p.a=1 AND q.b=2 AND r.c=3) OR (p.x=4 AND q.y=5 AND r.z=6)
000445 ** (F) x>A OR (x=A AND y>=B)
000446 **
000447 ** CASE 1:
000448 **
000449 ** If all subterms are of the form T.C=expr for some single column of C and
000450 ** a single table T (as shown in example B above) then create a new virtual
000451 ** term that is an equivalent IN expression. In other words, if the term
000452 ** being analyzed is:
000453 **
000454 ** x = expr1 OR expr2 = x OR x = expr3
000455 **
000456 ** then create a new virtual term like this:
000457 **
000458 ** x IN (expr1,expr2,expr3)
000459 **
000460 ** CASE 2:
000461 **
000462 ** If there are exactly two disjuncts and one side has x>A and the other side
000463 ** has x=A (for the same x and A) then add a new virtual conjunct term to the
000464 ** WHERE clause of the form "x>=A". Example:
000465 **
000466 ** x>A OR (x=A AND y>B) adds: x>=A
000467 **
000468 ** The added conjunct can sometimes be helpful in query planning.
000469 **
000470 ** CASE 3:
000471 **
000472 ** If all subterms are indexable by a single table T, then set
000473 **
000474 ** WhereTerm.eOperator = WO_OR
000475 ** WhereTerm.u.pOrInfo->indexable |= the cursor number for table T
000476 **
000477 ** A subterm is "indexable" if it is of the form
000478 ** "T.C <op> <expr>" where C is any column of table T and
000479 ** <op> is one of "=", "<", "<=", ">", ">=", "IS NULL", or "IN".
000480 ** A subterm is also indexable if it is an AND of two or more
000481 ** subsubterms at least one of which is indexable. Indexable AND
000482 ** subterms have their eOperator set to WO_AND and they have
000483 ** u.pAndInfo set to a dynamically allocated WhereAndTerm object.
000484 **
000485 ** From another point of view, "indexable" means that the subterm could
000486 ** potentially be used with an index if an appropriate index exists.
000487 ** This analysis does not consider whether or not the index exists; that
000488 ** is decided elsewhere. This analysis only looks at whether subterms
000489 ** appropriate for indexing exist.
000490 **
000491 ** All examples A through E above satisfy case 3. But if a term
000492 ** also satisfies case 1 (such as B) we know that the optimizer will
000493 ** always prefer case 1, so in that case we pretend that case 3 is not
000494 ** satisfied.
000495 **
000496 ** It might be the case that multiple tables are indexable. For example,
000497 ** (E) above is indexable on tables P, Q, and R.
000498 **
000499 ** Terms that satisfy case 3 are candidates for lookup by using
000500 ** separate indices to find rowids for each subterm and composing
000501 ** the union of all rowids using a RowSet object. This is similar
000502 ** to "bitmap indices" in other database engines.
000503 **
000504 ** OTHERWISE:
000505 **
000506 ** If none of cases 1, 2, or 3 apply, then leave the eOperator set to
000507 ** zero. This term is not useful for search.
000508 */
000509 static void exprAnalyzeOrTerm(
000510 SrcList *pSrc, /* the FROM clause */
000511 WhereClause *pWC, /* the complete WHERE clause */
000512 int idxTerm /* Index of the OR-term to be analyzed */
000513 ){
000514 WhereInfo *pWInfo = pWC->pWInfo; /* WHERE clause processing context */
000515 Parse *pParse = pWInfo->pParse; /* Parser context */
000516 sqlite3 *db = pParse->db; /* Database connection */
000517 WhereTerm *pTerm = &pWC->a[idxTerm]; /* The term to be analyzed */
000518 Expr *pExpr = pTerm->pExpr; /* The expression of the term */
000519 int i; /* Loop counters */
000520 WhereClause *pOrWc; /* Breakup of pTerm into subterms */
000521 WhereTerm *pOrTerm; /* A Sub-term within the pOrWc */
000522 WhereOrInfo *pOrInfo; /* Additional information associated with pTerm */
000523 Bitmask chngToIN; /* Tables that might satisfy case 1 */
000524 Bitmask indexable; /* Tables that are indexable, satisfying case 2 */
000525
000526 /*
000527 ** Break the OR clause into its separate subterms. The subterms are
000528 ** stored in a WhereClause structure containing within the WhereOrInfo
000529 ** object that is attached to the original OR clause term.
000530 */
000531 assert( (pTerm->wtFlags & (TERM_DYNAMIC|TERM_ORINFO|TERM_ANDINFO))==0 );
000532 assert( pExpr->op==TK_OR );
000533 pTerm->u.pOrInfo = pOrInfo = sqlite3DbMallocZero(db, sizeof(*pOrInfo));
000534 if( pOrInfo==0 ) return;
000535 pTerm->wtFlags |= TERM_ORINFO;
000536 pOrWc = &pOrInfo->wc;
000537 memset(pOrWc->aStatic, 0, sizeof(pOrWc->aStatic));
000538 sqlite3WhereClauseInit(pOrWc, pWInfo);
000539 sqlite3WhereSplit(pOrWc, pExpr, TK_OR);
000540 sqlite3WhereExprAnalyze(pSrc, pOrWc);
000541 if( db->mallocFailed ) return;
000542 assert( pOrWc->nTerm>=2 );
000543
000544 /*
000545 ** Compute the set of tables that might satisfy cases 1 or 3.
000546 */
000547 indexable = ~(Bitmask)0;
000548 chngToIN = ~(Bitmask)0;
000549 for(i=pOrWc->nTerm-1, pOrTerm=pOrWc->a; i>=0 && indexable; i--, pOrTerm++){
000550 if( (pOrTerm->eOperator & WO_SINGLE)==0 ){
000551 WhereAndInfo *pAndInfo;
000552 assert( (pOrTerm->wtFlags & (TERM_ANDINFO|TERM_ORINFO))==0 );
000553 chngToIN = 0;
000554 pAndInfo = sqlite3DbMallocRawNN(db, sizeof(*pAndInfo));
000555 if( pAndInfo ){
000556 WhereClause *pAndWC;
000557 WhereTerm *pAndTerm;
000558 int j;
000559 Bitmask b = 0;
000560 pOrTerm->u.pAndInfo = pAndInfo;
000561 pOrTerm->wtFlags |= TERM_ANDINFO;
000562 pOrTerm->eOperator = WO_AND;
000563 pAndWC = &pAndInfo->wc;
000564 memset(pAndWC->aStatic, 0, sizeof(pAndWC->aStatic));
000565 sqlite3WhereClauseInit(pAndWC, pWC->pWInfo);
000566 sqlite3WhereSplit(pAndWC, pOrTerm->pExpr, TK_AND);
000567 sqlite3WhereExprAnalyze(pSrc, pAndWC);
000568 pAndWC->pOuter = pWC;
000569 if( !db->mallocFailed ){
000570 for(j=0, pAndTerm=pAndWC->a; j<pAndWC->nTerm; j++, pAndTerm++){
000571 assert( pAndTerm->pExpr );
000572 if( allowedOp(pAndTerm->pExpr->op)
000573 || pAndTerm->eOperator==WO_MATCH
000574 ){
000575 b |= sqlite3WhereGetMask(&pWInfo->sMaskSet, pAndTerm->leftCursor);
000576 }
000577 }
000578 }
000579 indexable &= b;
000580 }
000581 }else if( pOrTerm->wtFlags & TERM_COPIED ){
000582 /* Skip this term for now. We revisit it when we process the
000583 ** corresponding TERM_VIRTUAL term */
000584 }else{
000585 Bitmask b;
000586 b = sqlite3WhereGetMask(&pWInfo->sMaskSet, pOrTerm->leftCursor);
000587 if( pOrTerm->wtFlags & TERM_VIRTUAL ){
000588 WhereTerm *pOther = &pOrWc->a[pOrTerm->iParent];
000589 b |= sqlite3WhereGetMask(&pWInfo->sMaskSet, pOther->leftCursor);
000590 }
000591 indexable &= b;
000592 if( (pOrTerm->eOperator & WO_EQ)==0 ){
000593 chngToIN = 0;
000594 }else{
000595 chngToIN &= b;
000596 }
000597 }
000598 }
000599
000600 /*
000601 ** Record the set of tables that satisfy case 3. The set might be
000602 ** empty.
000603 */
000604 pOrInfo->indexable = indexable;
000605 pTerm->eOperator = indexable==0 ? 0 : WO_OR;
000606
000607 /* For a two-way OR, attempt to implementation case 2.
000608 */
000609 if( indexable && pOrWc->nTerm==2 ){
000610 int iOne = 0;
000611 WhereTerm *pOne;
000612 while( (pOne = whereNthSubterm(&pOrWc->a[0],iOne++))!=0 ){
000613 int iTwo = 0;
000614 WhereTerm *pTwo;
000615 while( (pTwo = whereNthSubterm(&pOrWc->a[1],iTwo++))!=0 ){
000616 whereCombineDisjuncts(pSrc, pWC, pOne, pTwo);
000617 }
000618 }
000619 }
000620
000621 /*
000622 ** chngToIN holds a set of tables that *might* satisfy case 1. But
000623 ** we have to do some additional checking to see if case 1 really
000624 ** is satisfied.
000625 **
000626 ** chngToIN will hold either 0, 1, or 2 bits. The 0-bit case means
000627 ** that there is no possibility of transforming the OR clause into an
000628 ** IN operator because one or more terms in the OR clause contain
000629 ** something other than == on a column in the single table. The 1-bit
000630 ** case means that every term of the OR clause is of the form
000631 ** "table.column=expr" for some single table. The one bit that is set
000632 ** will correspond to the common table. We still need to check to make
000633 ** sure the same column is used on all terms. The 2-bit case is when
000634 ** the all terms are of the form "table1.column=table2.column". It
000635 ** might be possible to form an IN operator with either table1.column
000636 ** or table2.column as the LHS if either is common to every term of
000637 ** the OR clause.
000638 **
000639 ** Note that terms of the form "table.column1=table.column2" (the
000640 ** same table on both sizes of the ==) cannot be optimized.
000641 */
000642 if( chngToIN ){
000643 int okToChngToIN = 0; /* True if the conversion to IN is valid */
000644 int iColumn = -1; /* Column index on lhs of IN operator */
000645 int iCursor = -1; /* Table cursor common to all terms */
000646 int j = 0; /* Loop counter */
000647
000648 /* Search for a table and column that appears on one side or the
000649 ** other of the == operator in every subterm. That table and column
000650 ** will be recorded in iCursor and iColumn. There might not be any
000651 ** such table and column. Set okToChngToIN if an appropriate table
000652 ** and column is found but leave okToChngToIN false if not found.
000653 */
000654 for(j=0; j<2 && !okToChngToIN; j++){
000655 pOrTerm = pOrWc->a;
000656 for(i=pOrWc->nTerm-1; i>=0; i--, pOrTerm++){
000657 assert( pOrTerm->eOperator & WO_EQ );
000658 pOrTerm->wtFlags &= ~TERM_OR_OK;
000659 if( pOrTerm->leftCursor==iCursor ){
000660 /* This is the 2-bit case and we are on the second iteration and
000661 ** current term is from the first iteration. So skip this term. */
000662 assert( j==1 );
000663 continue;
000664 }
000665 if( (chngToIN & sqlite3WhereGetMask(&pWInfo->sMaskSet,
000666 pOrTerm->leftCursor))==0 ){
000667 /* This term must be of the form t1.a==t2.b where t2 is in the
000668 ** chngToIN set but t1 is not. This term will be either preceded
000669 ** or follwed by an inverted copy (t2.b==t1.a). Skip this term
000670 ** and use its inversion. */
000671 testcase( pOrTerm->wtFlags & TERM_COPIED );
000672 testcase( pOrTerm->wtFlags & TERM_VIRTUAL );
000673 assert( pOrTerm->wtFlags & (TERM_COPIED|TERM_VIRTUAL) );
000674 continue;
000675 }
000676 iColumn = pOrTerm->u.leftColumn;
000677 iCursor = pOrTerm->leftCursor;
000678 break;
000679 }
000680 if( i<0 ){
000681 /* No candidate table+column was found. This can only occur
000682 ** on the second iteration */
000683 assert( j==1 );
000684 assert( IsPowerOfTwo(chngToIN) );
000685 assert( chngToIN==sqlite3WhereGetMask(&pWInfo->sMaskSet, iCursor) );
000686 break;
000687 }
000688 testcase( j==1 );
000689
000690 /* We have found a candidate table and column. Check to see if that
000691 ** table and column is common to every term in the OR clause */
000692 okToChngToIN = 1;
000693 for(; i>=0 && okToChngToIN; i--, pOrTerm++){
000694 assert( pOrTerm->eOperator & WO_EQ );
000695 if( pOrTerm->leftCursor!=iCursor ){
000696 pOrTerm->wtFlags &= ~TERM_OR_OK;
000697 }else if( pOrTerm->u.leftColumn!=iColumn ){
000698 okToChngToIN = 0;
000699 }else{
000700 int affLeft, affRight;
000701 /* If the right-hand side is also a column, then the affinities
000702 ** of both right and left sides must be such that no type
000703 ** conversions are required on the right. (Ticket #2249)
000704 */
000705 affRight = sqlite3ExprAffinity(pOrTerm->pExpr->pRight);
000706 affLeft = sqlite3ExprAffinity(pOrTerm->pExpr->pLeft);
000707 if( affRight!=0 && affRight!=affLeft ){
000708 okToChngToIN = 0;
000709 }else{
000710 pOrTerm->wtFlags |= TERM_OR_OK;
000711 }
000712 }
000713 }
000714 }
000715
000716 /* At this point, okToChngToIN is true if original pTerm satisfies
000717 ** case 1. In that case, construct a new virtual term that is
000718 ** pTerm converted into an IN operator.
000719 */
000720 if( okToChngToIN ){
000721 Expr *pDup; /* A transient duplicate expression */
000722 ExprList *pList = 0; /* The RHS of the IN operator */
000723 Expr *pLeft = 0; /* The LHS of the IN operator */
000724 Expr *pNew; /* The complete IN operator */
000725
000726 for(i=pOrWc->nTerm-1, pOrTerm=pOrWc->a; i>=0; i--, pOrTerm++){
000727 if( (pOrTerm->wtFlags & TERM_OR_OK)==0 ) continue;
000728 assert( pOrTerm->eOperator & WO_EQ );
000729 assert( pOrTerm->leftCursor==iCursor );
000730 assert( pOrTerm->u.leftColumn==iColumn );
000731 pDup = sqlite3ExprDup(db, pOrTerm->pExpr->pRight, 0);
000732 pList = sqlite3ExprListAppend(pWInfo->pParse, pList, pDup);
000733 pLeft = pOrTerm->pExpr->pLeft;
000734 }
000735 assert( pLeft!=0 );
000736 pDup = sqlite3ExprDup(db, pLeft, 0);
000737 pNew = sqlite3PExpr(pParse, TK_IN, pDup, 0);
000738 if( pNew ){
000739 int idxNew;
000740 transferJoinMarkings(pNew, pExpr);
000741 assert( !ExprHasProperty(pNew, EP_xIsSelect) );
000742 pNew->x.pList = pList;
000743 idxNew = whereClauseInsert(pWC, pNew, TERM_VIRTUAL|TERM_DYNAMIC);
000744 testcase( idxNew==0 );
000745 exprAnalyze(pSrc, pWC, idxNew);
000746 pTerm = &pWC->a[idxTerm];
000747 markTermAsChild(pWC, idxNew, idxTerm);
000748 }else{
000749 sqlite3ExprListDelete(db, pList);
000750 }
000751 pTerm->eOperator = WO_NOOP; /* case 1 trumps case 3 */
000752 }
000753 }
000754 }
000755 #endif /* !SQLITE_OMIT_OR_OPTIMIZATION && !SQLITE_OMIT_SUBQUERY */
000756
000757 /*
000758 ** We already know that pExpr is a binary operator where both operands are
000759 ** column references. This routine checks to see if pExpr is an equivalence
000760 ** relation:
000761 ** 1. The SQLITE_Transitive optimization must be enabled
000762 ** 2. Must be either an == or an IS operator
000763 ** 3. Not originating in the ON clause of an OUTER JOIN
000764 ** 4. The affinities of A and B must be compatible
000765 ** 5a. Both operands use the same collating sequence OR
000766 ** 5b. The overall collating sequence is BINARY
000767 ** If this routine returns TRUE, that means that the RHS can be substituted
000768 ** for the LHS anyplace else in the WHERE clause where the LHS column occurs.
000769 ** This is an optimization. No harm comes from returning 0. But if 1 is
000770 ** returned when it should not be, then incorrect answers might result.
000771 */
000772 static int termIsEquivalence(Parse *pParse, Expr *pExpr){
000773 char aff1, aff2;
000774 CollSeq *pColl;
000775 const char *zColl1, *zColl2;
000776 if( !OptimizationEnabled(pParse->db, SQLITE_Transitive) ) return 0;
000777 if( pExpr->op!=TK_EQ && pExpr->op!=TK_IS ) return 0;
000778 if( ExprHasProperty(pExpr, EP_FromJoin) ) return 0;
000779 aff1 = sqlite3ExprAffinity(pExpr->pLeft);
000780 aff2 = sqlite3ExprAffinity(pExpr->pRight);
000781 if( aff1!=aff2
000782 && (!sqlite3IsNumericAffinity(aff1) || !sqlite3IsNumericAffinity(aff2))
000783 ){
000784 return 0;
000785 }
000786 pColl = sqlite3BinaryCompareCollSeq(pParse, pExpr->pLeft, pExpr->pRight);
000787 if( pColl==0 || sqlite3StrICmp(pColl->zName, "BINARY")==0 ) return 1;
000788 pColl = sqlite3ExprCollSeq(pParse, pExpr->pLeft);
000789 zColl1 = pColl ? pColl->zName : 0;
000790 pColl = sqlite3ExprCollSeq(pParse, pExpr->pRight);
000791 zColl2 = pColl ? pColl->zName : 0;
000792 return sqlite3_stricmp(zColl1, zColl2)==0;
000793 }
000794
000795 /*
000796 ** Recursively walk the expressions of a SELECT statement and generate
000797 ** a bitmask indicating which tables are used in that expression
000798 ** tree.
000799 */
000800 static Bitmask exprSelectUsage(WhereMaskSet *pMaskSet, Select *pS){
000801 Bitmask mask = 0;
000802 while( pS ){
000803 SrcList *pSrc = pS->pSrc;
000804 mask |= sqlite3WhereExprListUsage(pMaskSet, pS->pEList);
000805 mask |= sqlite3WhereExprListUsage(pMaskSet, pS->pGroupBy);
000806 mask |= sqlite3WhereExprListUsage(pMaskSet, pS->pOrderBy);
000807 mask |= sqlite3WhereExprUsage(pMaskSet, pS->pWhere);
000808 mask |= sqlite3WhereExprUsage(pMaskSet, pS->pHaving);
000809 if( ALWAYS(pSrc!=0) ){
000810 int i;
000811 for(i=0; i<pSrc->nSrc; i++){
000812 mask |= exprSelectUsage(pMaskSet, pSrc->a[i].pSelect);
000813 mask |= sqlite3WhereExprUsage(pMaskSet, pSrc->a[i].pOn);
000814 }
000815 }
000816 pS = pS->pPrior;
000817 }
000818 return mask;
000819 }
000820
000821 /*
000822 ** Expression pExpr is one operand of a comparison operator that might
000823 ** be useful for indexing. This routine checks to see if pExpr appears
000824 ** in any index. Return TRUE (1) if pExpr is an indexed term and return
000825 ** FALSE (0) if not. If TRUE is returned, also set *piCur to the cursor
000826 ** number of the table that is indexed and *piColumn to the column number
000827 ** of the column that is indexed, or XN_EXPR (-2) if an expression is being
000828 ** indexed.
000829 **
000830 ** If pExpr is a TK_COLUMN column reference, then this routine always returns
000831 ** true even if that particular column is not indexed, because the column
000832 ** might be added to an automatic index later.
000833 */
000834 static int exprMightBeIndexed(
000835 SrcList *pFrom, /* The FROM clause */
000836 int op, /* The specific comparison operator */
000837 Bitmask mPrereq, /* Bitmask of FROM clause terms referenced by pExpr */
000838 Expr *pExpr, /* An operand of a comparison operator */
000839 int *piCur, /* Write the referenced table cursor number here */
000840 int *piColumn /* Write the referenced table column number here */
000841 ){
000842 Index *pIdx;
000843 int i;
000844 int iCur;
000845
000846 /* If this expression is a vector to the left or right of a
000847 ** inequality constraint (>, <, >= or <=), perform the processing
000848 ** on the first element of the vector. */
000849 assert( TK_GT+1==TK_LE && TK_GT+2==TK_LT && TK_GT+3==TK_GE );
000850 assert( TK_IS<TK_GE && TK_ISNULL<TK_GE && TK_IN<TK_GE );
000851 assert( op<=TK_GE );
000852 if( pExpr->op==TK_VECTOR && (op>=TK_GT && ALWAYS(op<=TK_GE)) ){
000853 pExpr = pExpr->x.pList->a[0].pExpr;
000854 }
000855
000856 if( pExpr->op==TK_COLUMN ){
000857 *piCur = pExpr->iTable;
000858 *piColumn = pExpr->iColumn;
000859 return 1;
000860 }
000861 if( mPrereq==0 ) return 0; /* No table references */
000862 if( (mPrereq&(mPrereq-1))!=0 ) return 0; /* Refs more than one table */
000863 for(i=0; mPrereq>1; i++, mPrereq>>=1){}
000864 iCur = pFrom->a[i].iCursor;
000865 for(pIdx=pFrom->a[i].pTab->pIndex; pIdx; pIdx=pIdx->pNext){
000866 if( pIdx->aColExpr==0 ) continue;
000867 for(i=0; i<pIdx->nKeyCol; i++){
000868 if( pIdx->aiColumn[i]!=XN_EXPR ) continue;
000869 if( sqlite3ExprCompare(pExpr, pIdx->aColExpr->a[i].pExpr, iCur)==0 ){
000870 *piCur = iCur;
000871 *piColumn = XN_EXPR;
000872 return 1;
000873 }
000874 }
000875 }
000876 return 0;
000877 }
000878
000879 /*
000880 ** The input to this routine is an WhereTerm structure with only the
000881 ** "pExpr" field filled in. The job of this routine is to analyze the
000882 ** subexpression and populate all the other fields of the WhereTerm
000883 ** structure.
000884 **
000885 ** If the expression is of the form "<expr> <op> X" it gets commuted
000886 ** to the standard form of "X <op> <expr>".
000887 **
000888 ** If the expression is of the form "X <op> Y" where both X and Y are
000889 ** columns, then the original expression is unchanged and a new virtual
000890 ** term of the form "Y <op> X" is added to the WHERE clause and
000891 ** analyzed separately. The original term is marked with TERM_COPIED
000892 ** and the new term is marked with TERM_DYNAMIC (because it's pExpr
000893 ** needs to be freed with the WhereClause) and TERM_VIRTUAL (because it
000894 ** is a commuted copy of a prior term.) The original term has nChild=1
000895 ** and the copy has idxParent set to the index of the original term.
000896 */
000897 static void exprAnalyze(
000898 SrcList *pSrc, /* the FROM clause */
000899 WhereClause *pWC, /* the WHERE clause */
000900 int idxTerm /* Index of the term to be analyzed */
000901 ){
000902 WhereInfo *pWInfo = pWC->pWInfo; /* WHERE clause processing context */
000903 WhereTerm *pTerm; /* The term to be analyzed */
000904 WhereMaskSet *pMaskSet; /* Set of table index masks */
000905 Expr *pExpr; /* The expression to be analyzed */
000906 Bitmask prereqLeft; /* Prerequesites of the pExpr->pLeft */
000907 Bitmask prereqAll; /* Prerequesites of pExpr */
000908 Bitmask extraRight = 0; /* Extra dependencies on LEFT JOIN */
000909 Expr *pStr1 = 0; /* RHS of LIKE/GLOB operator */
000910 int isComplete = 0; /* RHS of LIKE/GLOB ends with wildcard */
000911 int noCase = 0; /* uppercase equivalent to lowercase */
000912 int op; /* Top-level operator. pExpr->op */
000913 Parse *pParse = pWInfo->pParse; /* Parsing context */
000914 sqlite3 *db = pParse->db; /* Database connection */
000915 unsigned char eOp2; /* op2 value for LIKE/REGEXP/GLOB */
000916
000917 if( db->mallocFailed ){
000918 return;
000919 }
000920 pTerm = &pWC->a[idxTerm];
000921 pMaskSet = &pWInfo->sMaskSet;
000922 pExpr = pTerm->pExpr;
000923 assert( pExpr->op!=TK_AS && pExpr->op!=TK_COLLATE );
000924 prereqLeft = sqlite3WhereExprUsage(pMaskSet, pExpr->pLeft);
000925 op = pExpr->op;
000926 if( op==TK_IN ){
000927 assert( pExpr->pRight==0 );
000928 if( sqlite3ExprCheckIN(pParse, pExpr) ) return;
000929 if( ExprHasProperty(pExpr, EP_xIsSelect) ){
000930 pTerm->prereqRight = exprSelectUsage(pMaskSet, pExpr->x.pSelect);
000931 }else{
000932 pTerm->prereqRight = sqlite3WhereExprListUsage(pMaskSet, pExpr->x.pList);
000933 }
000934 }else if( op==TK_ISNULL ){
000935 pTerm->prereqRight = 0;
000936 }else{
000937 pTerm->prereqRight = sqlite3WhereExprUsage(pMaskSet, pExpr->pRight);
000938 }
000939 prereqAll = sqlite3WhereExprUsage(pMaskSet, pExpr);
000940 if( ExprHasProperty(pExpr, EP_FromJoin) ){
000941 Bitmask x = sqlite3WhereGetMask(pMaskSet, pExpr->iRightJoinTable);
000942 prereqAll |= x;
000943 extraRight = x-1; /* ON clause terms may not be used with an index
000944 ** on left table of a LEFT JOIN. Ticket #3015 */
000945 }
000946 pTerm->prereqAll = prereqAll;
000947 pTerm->leftCursor = -1;
000948 pTerm->iParent = -1;
000949 pTerm->eOperator = 0;
000950 if( allowedOp(op) ){
000951 int iCur, iColumn;
000952 Expr *pLeft = sqlite3ExprSkipCollate(pExpr->pLeft);
000953 Expr *pRight = sqlite3ExprSkipCollate(pExpr->pRight);
000954 u16 opMask = (pTerm->prereqRight & prereqLeft)==0 ? WO_ALL : WO_EQUIV;
000955
000956 if( pTerm->iField>0 ){
000957 assert( op==TK_IN );
000958 assert( pLeft->op==TK_VECTOR );
000959 pLeft = pLeft->x.pList->a[pTerm->iField-1].pExpr;
000960 }
000961
000962 if( exprMightBeIndexed(pSrc, op, prereqLeft, pLeft, &iCur, &iColumn) ){
000963 pTerm->leftCursor = iCur;
000964 pTerm->u.leftColumn = iColumn;
000965 pTerm->eOperator = operatorMask(op) & opMask;
000966 }
000967 if( op==TK_IS ) pTerm->wtFlags |= TERM_IS;
000968 if( pRight
000969 && exprMightBeIndexed(pSrc, op, pTerm->prereqRight, pRight, &iCur,&iColumn)
000970 ){
000971 WhereTerm *pNew;
000972 Expr *pDup;
000973 u16 eExtraOp = 0; /* Extra bits for pNew->eOperator */
000974 assert( pTerm->iField==0 );
000975 if( pTerm->leftCursor>=0 ){
000976 int idxNew;
000977 pDup = sqlite3ExprDup(db, pExpr, 0);
000978 if( db->mallocFailed ){
000979 sqlite3ExprDelete(db, pDup);
000980 return;
000981 }
000982 idxNew = whereClauseInsert(pWC, pDup, TERM_VIRTUAL|TERM_DYNAMIC);
000983 if( idxNew==0 ) return;
000984 pNew = &pWC->a[idxNew];
000985 markTermAsChild(pWC, idxNew, idxTerm);
000986 if( op==TK_IS ) pNew->wtFlags |= TERM_IS;
000987 pTerm = &pWC->a[idxTerm];
000988 pTerm->wtFlags |= TERM_COPIED;
000989
000990 if( termIsEquivalence(pParse, pDup) ){
000991 pTerm->eOperator |= WO_EQUIV;
000992 eExtraOp = WO_EQUIV;
000993 }
000994 }else{
000995 pDup = pExpr;
000996 pNew = pTerm;
000997 }
000998 exprCommute(pParse, pDup);
000999 pNew->leftCursor = iCur;
001000 pNew->u.leftColumn = iColumn;
001001 testcase( (prereqLeft | extraRight) != prereqLeft );
001002 pNew->prereqRight = prereqLeft | extraRight;
001003 pNew->prereqAll = prereqAll;
001004 pNew->eOperator = (operatorMask(pDup->op) + eExtraOp) & opMask;
001005 }
001006 }
001007
001008 #ifndef SQLITE_OMIT_BETWEEN_OPTIMIZATION
001009 /* If a term is the BETWEEN operator, create two new virtual terms
001010 ** that define the range that the BETWEEN implements. For example:
001011 **
001012 ** a BETWEEN b AND c
001013 **
001014 ** is converted into:
001015 **
001016 ** (a BETWEEN b AND c) AND (a>=b) AND (a<=c)
001017 **
001018 ** The two new terms are added onto the end of the WhereClause object.
001019 ** The new terms are "dynamic" and are children of the original BETWEEN
001020 ** term. That means that if the BETWEEN term is coded, the children are
001021 ** skipped. Or, if the children are satisfied by an index, the original
001022 ** BETWEEN term is skipped.
001023 */
001024 else if( pExpr->op==TK_BETWEEN && pWC->op==TK_AND ){
001025 ExprList *pList = pExpr->x.pList;
001026 int i;
001027 static const u8 ops[] = {TK_GE, TK_LE};
001028 assert( pList!=0 );
001029 assert( pList->nExpr==2 );
001030 for(i=0; i<2; i++){
001031 Expr *pNewExpr;
001032 int idxNew;
001033 pNewExpr = sqlite3PExpr(pParse, ops[i],
001034 sqlite3ExprDup(db, pExpr->pLeft, 0),
001035 sqlite3ExprDup(db, pList->a[i].pExpr, 0));
001036 transferJoinMarkings(pNewExpr, pExpr);
001037 idxNew = whereClauseInsert(pWC, pNewExpr, TERM_VIRTUAL|TERM_DYNAMIC);
001038 testcase( idxNew==0 );
001039 exprAnalyze(pSrc, pWC, idxNew);
001040 pTerm = &pWC->a[idxTerm];
001041 markTermAsChild(pWC, idxNew, idxTerm);
001042 }
001043 }
001044 #endif /* SQLITE_OMIT_BETWEEN_OPTIMIZATION */
001045
001046 #if !defined(SQLITE_OMIT_OR_OPTIMIZATION) && !defined(SQLITE_OMIT_SUBQUERY)
001047 /* Analyze a term that is composed of two or more subterms connected by
001048 ** an OR operator.
001049 */
001050 else if( pExpr->op==TK_OR ){
001051 assert( pWC->op==TK_AND );
001052 exprAnalyzeOrTerm(pSrc, pWC, idxTerm);
001053 pTerm = &pWC->a[idxTerm];
001054 }
001055 #endif /* SQLITE_OMIT_OR_OPTIMIZATION */
001056
001057 #ifndef SQLITE_OMIT_LIKE_OPTIMIZATION
001058 /* Add constraints to reduce the search space on a LIKE or GLOB
001059 ** operator.
001060 **
001061 ** A like pattern of the form "x LIKE 'aBc%'" is changed into constraints
001062 **
001063 ** x>='ABC' AND x<'abd' AND x LIKE 'aBc%'
001064 **
001065 ** The last character of the prefix "abc" is incremented to form the
001066 ** termination condition "abd". If case is not significant (the default
001067 ** for LIKE) then the lower-bound is made all uppercase and the upper-
001068 ** bound is made all lowercase so that the bounds also work when comparing
001069 ** BLOBs.
001070 */
001071 if( pWC->op==TK_AND
001072 && isLikeOrGlob(pParse, pExpr, &pStr1, &isComplete, &noCase)
001073 ){
001074 Expr *pLeft; /* LHS of LIKE/GLOB operator */
001075 Expr *pStr2; /* Copy of pStr1 - RHS of LIKE/GLOB operator */
001076 Expr *pNewExpr1;
001077 Expr *pNewExpr2;
001078 int idxNew1;
001079 int idxNew2;
001080 const char *zCollSeqName; /* Name of collating sequence */
001081 const u16 wtFlags = TERM_LIKEOPT | TERM_VIRTUAL | TERM_DYNAMIC;
001082
001083 pLeft = pExpr->x.pList->a[1].pExpr;
001084 pStr2 = sqlite3ExprDup(db, pStr1, 0);
001085
001086 /* Convert the lower bound to upper-case and the upper bound to
001087 ** lower-case (upper-case is less than lower-case in ASCII) so that
001088 ** the range constraints also work for BLOBs
001089 */
001090 if( noCase && !pParse->db->mallocFailed ){
001091 int i;
001092 char c;
001093 pTerm->wtFlags |= TERM_LIKE;
001094 for(i=0; (c = pStr1->u.zToken[i])!=0; i++){
001095 pStr1->u.zToken[i] = sqlite3Toupper(c);
001096 pStr2->u.zToken[i] = sqlite3Tolower(c);
001097 }
001098 }
001099
001100 if( !db->mallocFailed ){
001101 u8 c, *pC; /* Last character before the first wildcard */
001102 pC = (u8*)&pStr2->u.zToken[sqlite3Strlen30(pStr2->u.zToken)-1];
001103 c = *pC;
001104 if( noCase ){
001105 /* The point is to increment the last character before the first
001106 ** wildcard. But if we increment '@', that will push it into the
001107 ** alphabetic range where case conversions will mess up the
001108 ** inequality. To avoid this, make sure to also run the full
001109 ** LIKE on all candidate expressions by clearing the isComplete flag
001110 */
001111 if( c=='A'-1 ) isComplete = 0;
001112 c = sqlite3UpperToLower[c];
001113 }
001114 *pC = c + 1;
001115 }
001116 zCollSeqName = noCase ? "NOCASE" : "BINARY";
001117 pNewExpr1 = sqlite3ExprDup(db, pLeft, 0);
001118 pNewExpr1 = sqlite3PExpr(pParse, TK_GE,
001119 sqlite3ExprAddCollateString(pParse,pNewExpr1,zCollSeqName),
001120 pStr1);
001121 transferJoinMarkings(pNewExpr1, pExpr);
001122 idxNew1 = whereClauseInsert(pWC, pNewExpr1, wtFlags);
001123 testcase( idxNew1==0 );
001124 exprAnalyze(pSrc, pWC, idxNew1);
001125 pNewExpr2 = sqlite3ExprDup(db, pLeft, 0);
001126 pNewExpr2 = sqlite3PExpr(pParse, TK_LT,
001127 sqlite3ExprAddCollateString(pParse,pNewExpr2,zCollSeqName),
001128 pStr2);
001129 transferJoinMarkings(pNewExpr2, pExpr);
001130 idxNew2 = whereClauseInsert(pWC, pNewExpr2, wtFlags);
001131 testcase( idxNew2==0 );
001132 exprAnalyze(pSrc, pWC, idxNew2);
001133 pTerm = &pWC->a[idxTerm];
001134 if( isComplete ){
001135 markTermAsChild(pWC, idxNew1, idxTerm);
001136 markTermAsChild(pWC, idxNew2, idxTerm);
001137 }
001138 }
001139 #endif /* SQLITE_OMIT_LIKE_OPTIMIZATION */
001140
001141 #ifndef SQLITE_OMIT_VIRTUALTABLE
001142 /* Add a WO_MATCH auxiliary term to the constraint set if the
001143 ** current expression is of the form: column MATCH expr.
001144 ** This information is used by the xBestIndex methods of
001145 ** virtual tables. The native query optimizer does not attempt
001146 ** to do anything with MATCH functions.
001147 */
001148 if( pWC->op==TK_AND && isMatchOfColumn(pExpr, &eOp2) ){
001149 int idxNew;
001150 Expr *pRight, *pLeft;
001151 WhereTerm *pNewTerm;
001152 Bitmask prereqColumn, prereqExpr;
001153
001154 pRight = pExpr->x.pList->a[0].pExpr;
001155 pLeft = pExpr->x.pList->a[1].pExpr;
001156 prereqExpr = sqlite3WhereExprUsage(pMaskSet, pRight);
001157 prereqColumn = sqlite3WhereExprUsage(pMaskSet, pLeft);
001158 if( (prereqExpr & prereqColumn)==0 ){
001159 Expr *pNewExpr;
001160 pNewExpr = sqlite3PExpr(pParse, TK_MATCH,
001161 0, sqlite3ExprDup(db, pRight, 0));
001162 idxNew = whereClauseInsert(pWC, pNewExpr, TERM_VIRTUAL|TERM_DYNAMIC);
001163 testcase( idxNew==0 );
001164 pNewTerm = &pWC->a[idxNew];
001165 pNewTerm->prereqRight = prereqExpr;
001166 pNewTerm->leftCursor = pLeft->iTable;
001167 pNewTerm->u.leftColumn = pLeft->iColumn;
001168 pNewTerm->eOperator = WO_MATCH;
001169 pNewTerm->eMatchOp = eOp2;
001170 markTermAsChild(pWC, idxNew, idxTerm);
001171 pTerm = &pWC->a[idxTerm];
001172 pTerm->wtFlags |= TERM_COPIED;
001173 pNewTerm->prereqAll = pTerm->prereqAll;
001174 }
001175 }
001176 #endif /* SQLITE_OMIT_VIRTUALTABLE */
001177
001178 /* If there is a vector == or IS term - e.g. "(a, b) == (?, ?)" - create
001179 ** new terms for each component comparison - "a = ?" and "b = ?". The
001180 ** new terms completely replace the original vector comparison, which is
001181 ** no longer used.
001182 **
001183 ** This is only required if at least one side of the comparison operation
001184 ** is not a sub-select. */
001185 if( pWC->op==TK_AND
001186 && (pExpr->op==TK_EQ || pExpr->op==TK_IS)
001187 && sqlite3ExprIsVector(pExpr->pLeft)
001188 && ( (pExpr->pLeft->flags & EP_xIsSelect)==0
001189 || (pExpr->pRight->flags & EP_xIsSelect)==0
001190 )){
001191 int nLeft = sqlite3ExprVectorSize(pExpr->pLeft);
001192 int i;
001193 assert( nLeft==sqlite3ExprVectorSize(pExpr->pRight) );
001194 for(i=0; i<nLeft; i++){
001195 int idxNew;
001196 Expr *pNew;
001197 Expr *pLeft = sqlite3ExprForVectorField(pParse, pExpr->pLeft, i);
001198 Expr *pRight = sqlite3ExprForVectorField(pParse, pExpr->pRight, i);
001199
001200 pNew = sqlite3PExpr(pParse, pExpr->op, pLeft, pRight);
001201 transferJoinMarkings(pNew, pExpr);
001202 idxNew = whereClauseInsert(pWC, pNew, TERM_DYNAMIC);
001203 exprAnalyze(pSrc, pWC, idxNew);
001204 }
001205 pTerm = &pWC->a[idxTerm];
001206 pTerm->wtFlags = TERM_CODED|TERM_VIRTUAL; /* Disable the original */
001207 pTerm->eOperator = 0;
001208 }
001209
001210 /* If there is a vector IN term - e.g. "(a, b) IN (SELECT ...)" - create
001211 ** a virtual term for each vector component. The expression object
001212 ** used by each such virtual term is pExpr (the full vector IN(...)
001213 ** expression). The WhereTerm.iField variable identifies the index within
001214 ** the vector on the LHS that the virtual term represents.
001215 **
001216 ** This only works if the RHS is a simple SELECT, not a compound
001217 */
001218 if( pWC->op==TK_AND && pExpr->op==TK_IN && pTerm->iField==0
001219 && pExpr->pLeft->op==TK_VECTOR
001220 && pExpr->x.pSelect->pPrior==0
001221 ){
001222 int i;
001223 for(i=0; i<sqlite3ExprVectorSize(pExpr->pLeft); i++){
001224 int idxNew;
001225 idxNew = whereClauseInsert(pWC, pExpr, TERM_VIRTUAL);
001226 pWC->a[idxNew].iField = i+1;
001227 exprAnalyze(pSrc, pWC, idxNew);
001228 markTermAsChild(pWC, idxNew, idxTerm);
001229 }
001230 }
001231
001232 #ifdef SQLITE_ENABLE_STAT3_OR_STAT4
001233 /* When sqlite_stat3 histogram data is available an operator of the
001234 ** form "x IS NOT NULL" can sometimes be evaluated more efficiently
001235 ** as "x>NULL" if x is not an INTEGER PRIMARY KEY. So construct a
001236 ** virtual term of that form.
001237 **
001238 ** Note that the virtual term must be tagged with TERM_VNULL.
001239 */
001240 if( pExpr->op==TK_NOTNULL
001241 && pExpr->pLeft->op==TK_COLUMN
001242 && pExpr->pLeft->iColumn>=0
001243 && OptimizationEnabled(db, SQLITE_Stat34)
001244 ){
001245 Expr *pNewExpr;
001246 Expr *pLeft = pExpr->pLeft;
001247 int idxNew;
001248 WhereTerm *pNewTerm;
001249
001250 pNewExpr = sqlite3PExpr(pParse, TK_GT,
001251 sqlite3ExprDup(db, pLeft, 0),
001252 sqlite3ExprAlloc(db, TK_NULL, 0, 0));
001253
001254 idxNew = whereClauseInsert(pWC, pNewExpr,
001255 TERM_VIRTUAL|TERM_DYNAMIC|TERM_VNULL);
001256 if( idxNew ){
001257 pNewTerm = &pWC->a[idxNew];
001258 pNewTerm->prereqRight = 0;
001259 pNewTerm->leftCursor = pLeft->iTable;
001260 pNewTerm->u.leftColumn = pLeft->iColumn;
001261 pNewTerm->eOperator = WO_GT;
001262 markTermAsChild(pWC, idxNew, idxTerm);
001263 pTerm = &pWC->a[idxTerm];
001264 pTerm->wtFlags |= TERM_COPIED;
001265 pNewTerm->prereqAll = pTerm->prereqAll;
001266 }
001267 }
001268 #endif /* SQLITE_ENABLE_STAT3_OR_STAT4 */
001269
001270 /* Prevent ON clause terms of a LEFT JOIN from being used to drive
001271 ** an index for tables to the left of the join.
001272 */
001273 testcase( pTerm!=&pWC->a[idxTerm] );
001274 pTerm = &pWC->a[idxTerm];
001275 pTerm->prereqRight |= extraRight;
001276 }
001277
001278 /***************************************************************************
001279 ** Routines with file scope above. Interface to the rest of the where.c
001280 ** subsystem follows.
001281 ***************************************************************************/
001282
001283 /*
001284 ** This routine identifies subexpressions in the WHERE clause where
001285 ** each subexpression is separated by the AND operator or some other
001286 ** operator specified in the op parameter. The WhereClause structure
001287 ** is filled with pointers to subexpressions. For example:
001288 **
001289 ** WHERE a=='hello' AND coalesce(b,11)<10 AND (c+12!=d OR c==22)
001290 ** \________/ \_______________/ \________________/
001291 ** slot[0] slot[1] slot[2]
001292 **
001293 ** The original WHERE clause in pExpr is unaltered. All this routine
001294 ** does is make slot[] entries point to substructure within pExpr.
001295 **
001296 ** In the previous sentence and in the diagram, "slot[]" refers to
001297 ** the WhereClause.a[] array. The slot[] array grows as needed to contain
001298 ** all terms of the WHERE clause.
001299 */
001300 void sqlite3WhereSplit(WhereClause *pWC, Expr *pExpr, u8 op){
001301 Expr *pE2 = sqlite3ExprSkipCollate(pExpr);
001302 pWC->op = op;
001303 if( pE2==0 ) return;
001304 if( pE2->op!=op ){
001305 whereClauseInsert(pWC, pExpr, 0);
001306 }else{
001307 sqlite3WhereSplit(pWC, pE2->pLeft, op);
001308 sqlite3WhereSplit(pWC, pE2->pRight, op);
001309 }
001310 }
001311
001312 /*
001313 ** Initialize a preallocated WhereClause structure.
001314 */
001315 void sqlite3WhereClauseInit(
001316 WhereClause *pWC, /* The WhereClause to be initialized */
001317 WhereInfo *pWInfo /* The WHERE processing context */
001318 ){
001319 pWC->pWInfo = pWInfo;
001320 pWC->pOuter = 0;
001321 pWC->nTerm = 0;
001322 pWC->nSlot = ArraySize(pWC->aStatic);
001323 pWC->a = pWC->aStatic;
001324 }
001325
001326 /*
001327 ** Deallocate a WhereClause structure. The WhereClause structure
001328 ** itself is not freed. This routine is the inverse of
001329 ** sqlite3WhereClauseInit().
001330 */
001331 void sqlite3WhereClauseClear(WhereClause *pWC){
001332 int i;
001333 WhereTerm *a;
001334 sqlite3 *db = pWC->pWInfo->pParse->db;
001335 for(i=pWC->nTerm-1, a=pWC->a; i>=0; i--, a++){
001336 if( a->wtFlags & TERM_DYNAMIC ){
001337 sqlite3ExprDelete(db, a->pExpr);
001338 }
001339 if( a->wtFlags & TERM_ORINFO ){
001340 whereOrInfoDelete(db, a->u.pOrInfo);
001341 }else if( a->wtFlags & TERM_ANDINFO ){
001342 whereAndInfoDelete(db, a->u.pAndInfo);
001343 }
001344 }
001345 if( pWC->a!=pWC->aStatic ){
001346 sqlite3DbFree(db, pWC->a);
001347 }
001348 }
001349
001350
001351 /*
001352 ** These routines walk (recursively) an expression tree and generate
001353 ** a bitmask indicating which tables are used in that expression
001354 ** tree.
001355 */
001356 Bitmask sqlite3WhereExprUsage(WhereMaskSet *pMaskSet, Expr *p){
001357 Bitmask mask;
001358 if( p==0 ) return 0;
001359 if( p->op==TK_COLUMN ){
001360 mask = sqlite3WhereGetMask(pMaskSet, p->iTable);
001361 return mask;
001362 }
001363 assert( !ExprHasProperty(p, EP_TokenOnly) );
001364 mask = p->pRight ? sqlite3WhereExprUsage(pMaskSet, p->pRight) : 0;
001365 if( p->pLeft ) mask |= sqlite3WhereExprUsage(pMaskSet, p->pLeft);
001366 if( ExprHasProperty(p, EP_xIsSelect) ){
001367 mask |= exprSelectUsage(pMaskSet, p->x.pSelect);
001368 }else if( p->x.pList ){
001369 mask |= sqlite3WhereExprListUsage(pMaskSet, p->x.pList);
001370 }
001371 return mask;
001372 }
001373 Bitmask sqlite3WhereExprListUsage(WhereMaskSet *pMaskSet, ExprList *pList){
001374 int i;
001375 Bitmask mask = 0;
001376 if( pList ){
001377 for(i=0; i<pList->nExpr; i++){
001378 mask |= sqlite3WhereExprUsage(pMaskSet, pList->a[i].pExpr);
001379 }
001380 }
001381 return mask;
001382 }
001383
001384
001385 /*
001386 ** Call exprAnalyze on all terms in a WHERE clause.
001387 **
001388 ** Note that exprAnalyze() might add new virtual terms onto the
001389 ** end of the WHERE clause. We do not want to analyze these new
001390 ** virtual terms, so start analyzing at the end and work forward
001391 ** so that the added virtual terms are never processed.
001392 */
001393 void sqlite3WhereExprAnalyze(
001394 SrcList *pTabList, /* the FROM clause */
001395 WhereClause *pWC /* the WHERE clause to be analyzed */
001396 ){
001397 int i;
001398 for(i=pWC->nTerm-1; i>=0; i--){
001399 exprAnalyze(pTabList, pWC, i);
001400 }
001401 }
001402
001403 /*
001404 ** For table-valued-functions, transform the function arguments into
001405 ** new WHERE clause terms.
001406 **
001407 ** Each function argument translates into an equality constraint against
001408 ** a HIDDEN column in the table.
001409 */
001410 void sqlite3WhereTabFuncArgs(
001411 Parse *pParse, /* Parsing context */
001412 struct SrcList_item *pItem, /* The FROM clause term to process */
001413 WhereClause *pWC /* Xfer function arguments to here */
001414 ){
001415 Table *pTab;
001416 int j, k;
001417 ExprList *pArgs;
001418 Expr *pColRef;
001419 Expr *pTerm;
001420 if( pItem->fg.isTabFunc==0 ) return;
001421 pTab = pItem->pTab;
001422 assert( pTab!=0 );
001423 pArgs = pItem->u1.pFuncArg;
001424 if( pArgs==0 ) return;
001425 for(j=k=0; j<pArgs->nExpr; j++){
001426 while( k<pTab->nCol && (pTab->aCol[k].colFlags & COLFLAG_HIDDEN)==0 ){k++;}
001427 if( k>=pTab->nCol ){
001428 sqlite3ErrorMsg(pParse, "too many arguments on %s() - max %d",
001429 pTab->zName, j);
001430 return;
001431 }
001432 pColRef = sqlite3ExprAlloc(pParse->db, TK_COLUMN, 0, 0);
001433 if( pColRef==0 ) return;
001434 pColRef->iTable = pItem->iCursor;
001435 pColRef->iColumn = k++;
001436 pColRef->pTab = pTab;
001437 pTerm = sqlite3PExpr(pParse, TK_EQ, pColRef,
001438 sqlite3ExprDup(pParse->db, pArgs->a[j].pExpr, 0));
001439 whereClauseInsert(pWC, pTerm, TERM_DYNAMIC);
001440 }
001441 }