4 ** The author disclaims copyright to this source code. In place of
5 ** a legal notice, here is a blessing:
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.
11 *************************************************************************
12 ** This module contains C code that generates VDBE code used to process
13 ** the WHERE clause of SQL statements.
15 ** This file was originally part of where.c but was split out to improve
16 ** readability and editabiliity. This file contains utility routines for
17 ** analyzing Expr objects in the WHERE clause.
19 #include "sqliteInt.h"
22 /* Forward declarations */
23 static void exprAnalyze(SrcList
*, WhereClause
*, int);
26 ** Deallocate all memory associated with a WhereOrInfo object.
28 static void whereOrInfoDelete(sqlite3
*db
, WhereOrInfo
*p
){
29 sqlite3WhereClauseClear(&p
->wc
);
34 ** Deallocate all memory associated with a WhereAndInfo object.
36 static void whereAndInfoDelete(sqlite3
*db
, WhereAndInfo
*p
){
37 sqlite3WhereClauseClear(&p
->wc
);
42 ** Add a single new WhereTerm entry to the WhereClause object pWC.
43 ** The new WhereTerm object is constructed from Expr p and with wtFlags.
44 ** The index in pWC->a[] of the new WhereTerm is returned on success.
45 ** 0 is returned if the new WhereTerm could not be added due to a memory
46 ** allocation error. The memory allocation failure will be recorded in
47 ** the db->mallocFailed flag so that higher-level functions can detect it.
49 ** This routine will increase the size of the pWC->a[] array as necessary.
51 ** If the wtFlags argument includes TERM_DYNAMIC, then responsibility
52 ** for freeing the expression p is assumed by the WhereClause object pWC.
53 ** This is true even if this routine fails to allocate a new WhereTerm.
55 ** WARNING: This routine might reallocate the space used to store
56 ** WhereTerms. All pointers to WhereTerms should be invalidated after
57 ** calling this routine. Such pointers may be reinitialized by referencing
58 ** the pWC->a[] array.
60 static int whereClauseInsert(WhereClause
*pWC
, Expr
*p
, u16 wtFlags
){
63 testcase( wtFlags
& TERM_VIRTUAL
);
64 if( pWC
->nTerm
>=pWC
->nSlot
){
65 WhereTerm
*pOld
= pWC
->a
;
66 sqlite3
*db
= pWC
->pWInfo
->pParse
->db
;
67 pWC
->a
= sqlite3DbMallocRawNN(db
, sizeof(pWC
->a
[0])*pWC
->nSlot
*2 );
69 if( wtFlags
& TERM_DYNAMIC
){
70 sqlite3ExprDelete(db
, p
);
75 memcpy(pWC
->a
, pOld
, sizeof(pWC
->a
[0])*pWC
->nTerm
);
76 if( pOld
!=pWC
->aStatic
){
77 sqlite3DbFree(db
, pOld
);
79 pWC
->nSlot
= sqlite3DbMallocSize(db
, pWC
->a
)/sizeof(pWC
->a
[0]);
81 pTerm
= &pWC
->a
[idx
= pWC
->nTerm
++];
82 if( p
&& ExprHasProperty(p
, EP_Unlikely
) ){
83 pTerm
->truthProb
= sqlite3LogEst(p
->iTable
) - 270;
87 pTerm
->pExpr
= sqlite3ExprSkipCollate(p
);
88 pTerm
->wtFlags
= wtFlags
;
91 memset(&pTerm
->eOperator
, 0,
92 sizeof(WhereTerm
) - offsetof(WhereTerm
,eOperator
));
97 ** Return TRUE if the given operator is one of the operators that is
98 ** allowed for an indexable WHERE clause term. The allowed operators are
99 ** "=", "<", ">", "<=", ">=", "IN", "IS", and "IS NULL"
101 static int allowedOp(int op
){
102 assert( TK_GT
>TK_EQ
&& TK_GT
<TK_GE
);
103 assert( TK_LT
>TK_EQ
&& TK_LT
<TK_GE
);
104 assert( TK_LE
>TK_EQ
&& TK_LE
<TK_GE
);
105 assert( TK_GE
==TK_EQ
+4 );
106 return op
==TK_IN
|| (op
>=TK_EQ
&& op
<=TK_GE
) || op
==TK_ISNULL
|| op
==TK_IS
;
110 ** Commute a comparison operator. Expressions of the form "X op Y"
111 ** are converted into "Y op X".
113 ** If left/right precedence rules come into play when determining the
114 ** collating sequence, then COLLATE operators are adjusted to ensure
115 ** that the collating sequence does not change. For example:
116 ** "Y collate NOCASE op X" becomes "X op Y" because any collation sequence on
117 ** the left hand side of a comparison overrides any collation sequence
118 ** attached to the right. For the same reason the EP_Collate flag
121 static void exprCommute(Parse
*pParse
, Expr
*pExpr
){
122 u16 expRight
= (pExpr
->pRight
->flags
& EP_Collate
);
123 u16 expLeft
= (pExpr
->pLeft
->flags
& EP_Collate
);
124 assert( allowedOp(pExpr
->op
) && pExpr
->op
!=TK_IN
);
125 if( expRight
==expLeft
){
126 /* Either X and Y both have COLLATE operator or neither do */
128 /* Both X and Y have COLLATE operators. Make sure X is always
129 ** used by clearing the EP_Collate flag from Y. */
130 pExpr
->pRight
->flags
&= ~EP_Collate
;
131 }else if( sqlite3ExprCollSeq(pParse
, pExpr
->pLeft
)!=0 ){
132 /* Neither X nor Y have COLLATE operators, but X has a non-default
133 ** collating sequence. So add the EP_Collate marker on X to cause
134 ** it to be searched first. */
135 pExpr
->pLeft
->flags
|= EP_Collate
;
138 SWAP(Expr
*,pExpr
->pRight
,pExpr
->pLeft
);
139 if( pExpr
->op
>=TK_GT
){
140 assert( TK_LT
==TK_GT
+2 );
141 assert( TK_GE
==TK_LE
+2 );
142 assert( TK_GT
>TK_EQ
);
143 assert( TK_GT
<TK_LE
);
144 assert( pExpr
->op
>=TK_GT
&& pExpr
->op
<=TK_GE
);
145 pExpr
->op
= ((pExpr
->op
-TK_GT
)^2)+TK_GT
;
150 ** Translate from TK_xx operator to WO_xx bitmask.
152 static u16
operatorMask(int op
){
154 assert( allowedOp(op
) );
157 }else if( op
==TK_ISNULL
){
159 }else if( op
==TK_IS
){
162 assert( (WO_EQ
<<(op
-TK_EQ
)) < 0x7fff );
163 c
= (u16
)(WO_EQ
<<(op
-TK_EQ
));
165 assert( op
!=TK_ISNULL
|| c
==WO_ISNULL
);
166 assert( op
!=TK_IN
|| c
==WO_IN
);
167 assert( op
!=TK_EQ
|| c
==WO_EQ
);
168 assert( op
!=TK_LT
|| c
==WO_LT
);
169 assert( op
!=TK_LE
|| c
==WO_LE
);
170 assert( op
!=TK_GT
|| c
==WO_GT
);
171 assert( op
!=TK_GE
|| c
==WO_GE
);
172 assert( op
!=TK_IS
|| c
==WO_IS
);
177 #ifndef SQLITE_OMIT_LIKE_OPTIMIZATION
179 ** Check to see if the given expression is a LIKE or GLOB operator that
180 ** can be optimized using inequality constraints. Return TRUE if it is
181 ** so and false if not.
183 ** In order for the operator to be optimizible, the RHS must be a string
184 ** literal that does not begin with a wildcard. The LHS must be a column
185 ** that may only be NULL, a string, or a BLOB, never a number. (This means
186 ** that virtual tables cannot participate in the LIKE optimization.) The
187 ** collating sequence for the column on the LHS must be appropriate for
190 static int isLikeOrGlob(
191 Parse
*pParse
, /* Parsing and code generating context */
192 Expr
*pExpr
, /* Test this expression */
193 Expr
**ppPrefix
, /* Pointer to TK_STRING expression with pattern prefix */
194 int *pisComplete
, /* True if the only wildcard is % in the last character */
195 int *pnoCase
/* True if uppercase is equivalent to lowercase */
197 const u8
*z
= 0; /* String on RHS of LIKE operator */
198 Expr
*pRight
, *pLeft
; /* Right and left size of LIKE operator */
199 ExprList
*pList
; /* List of operands to the LIKE operator */
200 int c
; /* One character in z[] */
201 int cnt
; /* Number of non-wildcard prefix characters */
202 char wc
[4]; /* Wildcard characters */
203 sqlite3
*db
= pParse
->db
; /* Database connection */
204 sqlite3_value
*pVal
= 0;
205 int op
; /* Opcode of pRight */
206 int rc
; /* Result code to return */
208 if( !sqlite3IsLikeFunction(db
, pExpr
, pnoCase
, wc
) ){
212 if( *pnoCase
) return 0;
214 pList
= pExpr
->x
.pList
;
215 pLeft
= pList
->a
[1].pExpr
;
217 pRight
= sqlite3ExprSkipCollate(pList
->a
[0].pExpr
);
219 if( op
==TK_VARIABLE
&& (db
->flags
& SQLITE_EnableQPSG
)==0 ){
220 Vdbe
*pReprepare
= pParse
->pReprepare
;
221 int iCol
= pRight
->iColumn
;
222 pVal
= sqlite3VdbeGetBoundValue(pReprepare
, iCol
, SQLITE_AFF_BLOB
);
223 if( pVal
&& sqlite3_value_type(pVal
)==SQLITE_TEXT
){
224 z
= sqlite3_value_text(pVal
);
226 sqlite3VdbeSetVarmask(pParse
->pVdbe
, iCol
);
227 assert( pRight
->op
==TK_VARIABLE
|| pRight
->op
==TK_REGISTER
);
228 }else if( op
==TK_STRING
){
229 z
= (u8
*)pRight
->u
.zToken
;
233 /* If the RHS begins with a digit or a minus sign, then the LHS must
234 ** be an ordinary column (not a virtual table column) with TEXT affinity.
235 ** Otherwise the LHS might be numeric and "lhs >= rhs" would be false
236 ** even though "lhs LIKE rhs" is true. But if the RHS does not start
237 ** with a digit or '-', then "lhs LIKE rhs" will always be false if
238 ** the LHS is numeric and so the optimization still works.
240 if( sqlite3Isdigit(z
[0]) || z
[0]=='-' ){
241 if( pLeft
->op
!=TK_COLUMN
242 || sqlite3ExprAffinity(pLeft
)!=SQLITE_AFF_TEXT
243 || IsVirtual(pLeft
->pTab
) /* Value might be numeric */
245 sqlite3ValueFree(pVal
);
250 /* Count the number of prefix characters prior to the first wildcard */
252 while( (c
=z
[cnt
])!=0 && c
!=wc
[0] && c
!=wc
[1] && c
!=wc
[2] ){
254 if( c
==wc
[3] && z
[cnt
]!=0 ) cnt
++;
257 /* The optimization is possible only if (1) the pattern does not begin
258 ** with a wildcard and if (2) the non-wildcard prefix does not end with
259 ** an (illegal 0xff) character, or (3) the pattern does not consist of
260 ** a single escape character. The second condition is necessary so
261 ** that we can increment the prefix key to find an upper bound for the
262 ** range search. The third is because the caller assumes that the pattern
263 ** consists of at least one character after all escapes have been
265 if( cnt
!=0 && 255!=(u8
)z
[cnt
-1] && (cnt
>1 || z
[0]!=wc
[3]) ){
268 /* A "complete" match if the pattern ends with "*" or "%" */
269 *pisComplete
= c
==wc
[0] && z
[cnt
+1]==0;
271 /* Get the pattern prefix. Remove all escapes from the prefix. */
272 pPrefix
= sqlite3Expr(db
, TK_STRING
, (char*)z
);
275 char *zNew
= pPrefix
->u
.zToken
;
277 for(iFrom
=iTo
=0; iFrom
<cnt
; iFrom
++){
278 if( zNew
[iFrom
]==wc
[3] ) iFrom
++;
279 zNew
[iTo
++] = zNew
[iFrom
];
285 /* If the RHS pattern is a bound parameter, make arrangements to
286 ** reprepare the statement when that parameter is rebound */
287 if( op
==TK_VARIABLE
){
288 Vdbe
*v
= pParse
->pVdbe
;
289 sqlite3VdbeSetVarmask(v
, pRight
->iColumn
);
290 if( *pisComplete
&& pRight
->u
.zToken
[1] ){
291 /* If the rhs of the LIKE expression is a variable, and the current
292 ** value of the variable means there is no need to invoke the LIKE
293 ** function, then no OP_Variable will be added to the program.
294 ** This causes problems for the sqlite3_bind_parameter_name()
295 ** API. To work around them, add a dummy OP_Variable here.
297 int r1
= sqlite3GetTempReg(pParse
);
298 sqlite3ExprCodeTarget(pParse
, pRight
, r1
);
299 sqlite3VdbeChangeP3(v
, sqlite3VdbeCurrentAddr(v
)-1, 0);
300 sqlite3ReleaseTempReg(pParse
, r1
);
309 sqlite3ValueFree(pVal
);
312 #endif /* SQLITE_OMIT_LIKE_OPTIMIZATION */
315 #ifndef SQLITE_OMIT_VIRTUALTABLE
317 ** Check to see if the pExpr expression is a form that needs to be passed
318 ** to the xBestIndex method of virtual tables. Forms of interest include:
320 ** Expression Virtual Table Operator
321 ** ----------------------- ---------------------------------
322 ** 1. column MATCH expr SQLITE_INDEX_CONSTRAINT_MATCH
323 ** 2. column GLOB expr SQLITE_INDEX_CONSTRAINT_GLOB
324 ** 3. column LIKE expr SQLITE_INDEX_CONSTRAINT_LIKE
325 ** 4. column REGEXP expr SQLITE_INDEX_CONSTRAINT_REGEXP
326 ** 5. column != expr SQLITE_INDEX_CONSTRAINT_NE
327 ** 6. expr != column SQLITE_INDEX_CONSTRAINT_NE
328 ** 7. column IS NOT expr SQLITE_INDEX_CONSTRAINT_ISNOT
329 ** 8. expr IS NOT column SQLITE_INDEX_CONSTRAINT_ISNOT
330 ** 9. column IS NOT NULL SQLITE_INDEX_CONSTRAINT_ISNOTNULL
332 ** In every case, "column" must be a column of a virtual table. If there
333 ** is a match, set *ppLeft to the "column" expression, set *ppRight to the
334 ** "expr" expression (even though in forms (6) and (8) the column is on the
335 ** right and the expression is on the left). Also set *peOp2 to the
336 ** appropriate virtual table operator. The return value is 1 or 2 if there
337 ** is a match. The usual return is 1, but if the RHS is also a column
338 ** of virtual table in forms (5) or (7) then return 2.
340 ** If the expression matches none of the patterns above, return 0.
342 static int isAuxiliaryVtabOperator(
343 Expr
*pExpr
, /* Test this expression */
344 unsigned char *peOp2
, /* OUT: 0 for MATCH, or else an op2 value */
345 Expr
**ppLeft
, /* Column expression to left of MATCH/op2 */
346 Expr
**ppRight
/* Expression to left of MATCH/op2 */
348 if( pExpr
->op
==TK_FUNCTION
){
349 static const struct Op2
{
353 { "match", SQLITE_INDEX_CONSTRAINT_MATCH
},
354 { "glob", SQLITE_INDEX_CONSTRAINT_GLOB
},
355 { "like", SQLITE_INDEX_CONSTRAINT_LIKE
},
356 { "regexp", SQLITE_INDEX_CONSTRAINT_REGEXP
}
359 Expr
*pCol
; /* Column reference */
362 pList
= pExpr
->x
.pList
;
363 if( pList
==0 || pList
->nExpr
!=2 ){
366 pCol
= pList
->a
[1].pExpr
;
367 if( pCol
->op
!=TK_COLUMN
|| !IsVirtual(pCol
->pTab
) ){
370 for(i
=0; i
<ArraySize(aOp
); i
++){
371 if( sqlite3StrICmp(pExpr
->u
.zToken
, aOp
[i
].zOp
)==0 ){
372 *peOp2
= aOp
[i
].eOp2
;
373 *ppRight
= pList
->a
[0].pExpr
;
378 }else if( pExpr
->op
==TK_NE
|| pExpr
->op
==TK_ISNOT
|| pExpr
->op
==TK_NOTNULL
){
380 Expr
*pLeft
= pExpr
->pLeft
;
381 Expr
*pRight
= pExpr
->pRight
;
382 if( pLeft
->op
==TK_COLUMN
&& IsVirtual(pLeft
->pTab
) ){
385 if( pRight
&& pRight
->op
==TK_COLUMN
&& IsVirtual(pRight
->pTab
) ){
387 SWAP(Expr
*, pLeft
, pRight
);
391 if( pExpr
->op
==TK_NE
) *peOp2
= SQLITE_INDEX_CONSTRAINT_NE
;
392 if( pExpr
->op
==TK_ISNOT
) *peOp2
= SQLITE_INDEX_CONSTRAINT_ISNOT
;
393 if( pExpr
->op
==TK_NOTNULL
) *peOp2
= SQLITE_INDEX_CONSTRAINT_ISNOTNULL
;
398 #endif /* SQLITE_OMIT_VIRTUALTABLE */
401 ** If the pBase expression originated in the ON or USING clause of
402 ** a join, then transfer the appropriate markings over to derived.
404 static void transferJoinMarkings(Expr
*pDerived
, Expr
*pBase
){
406 pDerived
->flags
|= pBase
->flags
& EP_FromJoin
;
407 pDerived
->iRightJoinTable
= pBase
->iRightJoinTable
;
412 ** Mark term iChild as being a child of term iParent
414 static void markTermAsChild(WhereClause
*pWC
, int iChild
, int iParent
){
415 pWC
->a
[iChild
].iParent
= iParent
;
416 pWC
->a
[iChild
].truthProb
= pWC
->a
[iParent
].truthProb
;
417 pWC
->a
[iParent
].nChild
++;
421 ** Return the N-th AND-connected subterm of pTerm. Or if pTerm is not
422 ** a conjunction, then return just pTerm when N==0. If N is exceeds
423 ** the number of available subterms, return NULL.
425 static WhereTerm
*whereNthSubterm(WhereTerm
*pTerm
, int N
){
426 if( pTerm
->eOperator
!=WO_AND
){
427 return N
==0 ? pTerm
: 0;
429 if( N
<pTerm
->u
.pAndInfo
->wc
.nTerm
){
430 return &pTerm
->u
.pAndInfo
->wc
.a
[N
];
436 ** Subterms pOne and pTwo are contained within WHERE clause pWC. The
437 ** two subterms are in disjunction - they are OR-ed together.
439 ** If these two terms are both of the form: "A op B" with the same
440 ** A and B values but different operators and if the operators are
441 ** compatible (if one is = and the other is <, for example) then
442 ** add a new virtual AND term to pWC that is the combination of the
447 ** x<y OR x=y --> x<=y
448 ** x=y OR x=y --> x=y
449 ** x<=y OR x<y --> x<=y
451 ** The following is NOT generated:
453 ** x<y OR x>y --> x!=y
455 static void whereCombineDisjuncts(
456 SrcList
*pSrc
, /* the FROM clause */
457 WhereClause
*pWC
, /* The complete WHERE clause */
458 WhereTerm
*pOne
, /* First disjunct */
459 WhereTerm
*pTwo
/* Second disjunct */
461 u16 eOp
= pOne
->eOperator
| pTwo
->eOperator
;
462 sqlite3
*db
; /* Database connection (for malloc) */
463 Expr
*pNew
; /* New virtual expression */
464 int op
; /* Operator for the combined expression */
465 int idxNew
; /* Index in pWC of the next virtual term */
467 if( (pOne
->eOperator
& (WO_EQ
|WO_LT
|WO_LE
|WO_GT
|WO_GE
))==0 ) return;
468 if( (pTwo
->eOperator
& (WO_EQ
|WO_LT
|WO_LE
|WO_GT
|WO_GE
))==0 ) return;
469 if( (eOp
& (WO_EQ
|WO_LT
|WO_LE
))!=eOp
470 && (eOp
& (WO_EQ
|WO_GT
|WO_GE
))!=eOp
) return;
471 assert( pOne
->pExpr
->pLeft
!=0 && pOne
->pExpr
->pRight
!=0 );
472 assert( pTwo
->pExpr
->pLeft
!=0 && pTwo
->pExpr
->pRight
!=0 );
473 if( sqlite3ExprCompare(0,pOne
->pExpr
->pLeft
, pTwo
->pExpr
->pLeft
, -1) ) return;
474 if( sqlite3ExprCompare(0,pOne
->pExpr
->pRight
, pTwo
->pExpr
->pRight
,-1) )return;
475 /* If we reach this point, it means the two subterms can be combined */
476 if( (eOp
& (eOp
-1))!=0 ){
477 if( eOp
& (WO_LT
|WO_LE
) ){
480 assert( eOp
& (WO_GT
|WO_GE
) );
484 db
= pWC
->pWInfo
->pParse
->db
;
485 pNew
= sqlite3ExprDup(db
, pOne
->pExpr
, 0);
486 if( pNew
==0 ) return;
487 for(op
=TK_EQ
; eOp
!=(WO_EQ
<<(op
-TK_EQ
)); op
++){ assert( op
<TK_GE
); }
489 idxNew
= whereClauseInsert(pWC
, pNew
, TERM_VIRTUAL
|TERM_DYNAMIC
);
490 exprAnalyze(pSrc
, pWC
, idxNew
);
493 #if !defined(SQLITE_OMIT_OR_OPTIMIZATION) && !defined(SQLITE_OMIT_SUBQUERY)
495 ** Analyze a term that consists of two or more OR-connected
498 ** ... WHERE (a=5) AND (b=7 OR c=9 OR d=13) AND (d=13)
499 ** ^^^^^^^^^^^^^^^^^^^^
501 ** This routine analyzes terms such as the middle term in the above example.
502 ** A WhereOrTerm object is computed and attached to the term under
503 ** analysis, regardless of the outcome of the analysis. Hence:
505 ** WhereTerm.wtFlags |= TERM_ORINFO
506 ** WhereTerm.u.pOrInfo = a dynamically allocated WhereOrTerm object
508 ** The term being analyzed must have two or more of OR-connected subterms.
509 ** A single subterm might be a set of AND-connected sub-subterms.
510 ** Examples of terms under analysis:
512 ** (A) t1.x=t2.y OR t1.x=t2.z OR t1.y=15 OR t1.z=t3.a+5
513 ** (B) x=expr1 OR expr2=x OR x=expr3
514 ** (C) t1.x=t2.y OR (t1.x=t2.z AND t1.y=15)
515 ** (D) x=expr1 OR (y>11 AND y<22 AND z LIKE '*hello*')
516 ** (E) (p.a=1 AND q.b=2 AND r.c=3) OR (p.x=4 AND q.y=5 AND r.z=6)
517 ** (F) x>A OR (x=A AND y>=B)
521 ** If all subterms are of the form T.C=expr for some single column of C and
522 ** a single table T (as shown in example B above) then create a new virtual
523 ** term that is an equivalent IN expression. In other words, if the term
524 ** being analyzed is:
526 ** x = expr1 OR expr2 = x OR x = expr3
528 ** then create a new virtual term like this:
530 ** x IN (expr1,expr2,expr3)
534 ** If there are exactly two disjuncts and one side has x>A and the other side
535 ** has x=A (for the same x and A) then add a new virtual conjunct term to the
536 ** WHERE clause of the form "x>=A". Example:
538 ** x>A OR (x=A AND y>B) adds: x>=A
540 ** The added conjunct can sometimes be helpful in query planning.
544 ** If all subterms are indexable by a single table T, then set
546 ** WhereTerm.eOperator = WO_OR
547 ** WhereTerm.u.pOrInfo->indexable |= the cursor number for table T
549 ** A subterm is "indexable" if it is of the form
550 ** "T.C <op> <expr>" where C is any column of table T and
551 ** <op> is one of "=", "<", "<=", ">", ">=", "IS NULL", or "IN".
552 ** A subterm is also indexable if it is an AND of two or more
553 ** subsubterms at least one of which is indexable. Indexable AND
554 ** subterms have their eOperator set to WO_AND and they have
555 ** u.pAndInfo set to a dynamically allocated WhereAndTerm object.
557 ** From another point of view, "indexable" means that the subterm could
558 ** potentially be used with an index if an appropriate index exists.
559 ** This analysis does not consider whether or not the index exists; that
560 ** is decided elsewhere. This analysis only looks at whether subterms
561 ** appropriate for indexing exist.
563 ** All examples A through E above satisfy case 3. But if a term
564 ** also satisfies case 1 (such as B) we know that the optimizer will
565 ** always prefer case 1, so in that case we pretend that case 3 is not
568 ** It might be the case that multiple tables are indexable. For example,
569 ** (E) above is indexable on tables P, Q, and R.
571 ** Terms that satisfy case 3 are candidates for lookup by using
572 ** separate indices to find rowids for each subterm and composing
573 ** the union of all rowids using a RowSet object. This is similar
574 ** to "bitmap indices" in other database engines.
578 ** If none of cases 1, 2, or 3 apply, then leave the eOperator set to
579 ** zero. This term is not useful for search.
581 static void exprAnalyzeOrTerm(
582 SrcList
*pSrc
, /* the FROM clause */
583 WhereClause
*pWC
, /* the complete WHERE clause */
584 int idxTerm
/* Index of the OR-term to be analyzed */
586 WhereInfo
*pWInfo
= pWC
->pWInfo
; /* WHERE clause processing context */
587 Parse
*pParse
= pWInfo
->pParse
; /* Parser context */
588 sqlite3
*db
= pParse
->db
; /* Database connection */
589 WhereTerm
*pTerm
= &pWC
->a
[idxTerm
]; /* The term to be analyzed */
590 Expr
*pExpr
= pTerm
->pExpr
; /* The expression of the term */
591 int i
; /* Loop counters */
592 WhereClause
*pOrWc
; /* Breakup of pTerm into subterms */
593 WhereTerm
*pOrTerm
; /* A Sub-term within the pOrWc */
594 WhereOrInfo
*pOrInfo
; /* Additional information associated with pTerm */
595 Bitmask chngToIN
; /* Tables that might satisfy case 1 */
596 Bitmask indexable
; /* Tables that are indexable, satisfying case 2 */
599 ** Break the OR clause into its separate subterms. The subterms are
600 ** stored in a WhereClause structure containing within the WhereOrInfo
601 ** object that is attached to the original OR clause term.
603 assert( (pTerm
->wtFlags
& (TERM_DYNAMIC
|TERM_ORINFO
|TERM_ANDINFO
))==0 );
604 assert( pExpr
->op
==TK_OR
);
605 pTerm
->u
.pOrInfo
= pOrInfo
= sqlite3DbMallocZero(db
, sizeof(*pOrInfo
));
606 if( pOrInfo
==0 ) return;
607 pTerm
->wtFlags
|= TERM_ORINFO
;
608 pOrWc
= &pOrInfo
->wc
;
609 memset(pOrWc
->aStatic
, 0, sizeof(pOrWc
->aStatic
));
610 sqlite3WhereClauseInit(pOrWc
, pWInfo
);
611 sqlite3WhereSplit(pOrWc
, pExpr
, TK_OR
);
612 sqlite3WhereExprAnalyze(pSrc
, pOrWc
);
613 if( db
->mallocFailed
) return;
614 assert( pOrWc
->nTerm
>=2 );
617 ** Compute the set of tables that might satisfy cases 1 or 3.
619 indexable
= ~(Bitmask
)0;
620 chngToIN
= ~(Bitmask
)0;
621 for(i
=pOrWc
->nTerm
-1, pOrTerm
=pOrWc
->a
; i
>=0 && indexable
; i
--, pOrTerm
++){
622 if( (pOrTerm
->eOperator
& WO_SINGLE
)==0 ){
623 WhereAndInfo
*pAndInfo
;
624 assert( (pOrTerm
->wtFlags
& (TERM_ANDINFO
|TERM_ORINFO
))==0 );
626 pAndInfo
= sqlite3DbMallocRawNN(db
, sizeof(*pAndInfo
));
632 pOrTerm
->u
.pAndInfo
= pAndInfo
;
633 pOrTerm
->wtFlags
|= TERM_ANDINFO
;
634 pOrTerm
->eOperator
= WO_AND
;
635 pAndWC
= &pAndInfo
->wc
;
636 memset(pAndWC
->aStatic
, 0, sizeof(pAndWC
->aStatic
));
637 sqlite3WhereClauseInit(pAndWC
, pWC
->pWInfo
);
638 sqlite3WhereSplit(pAndWC
, pOrTerm
->pExpr
, TK_AND
);
639 sqlite3WhereExprAnalyze(pSrc
, pAndWC
);
640 pAndWC
->pOuter
= pWC
;
641 if( !db
->mallocFailed
){
642 for(j
=0, pAndTerm
=pAndWC
->a
; j
<pAndWC
->nTerm
; j
++, pAndTerm
++){
643 assert( pAndTerm
->pExpr
);
644 if( allowedOp(pAndTerm
->pExpr
->op
)
645 || pAndTerm
->eOperator
==WO_AUX
647 b
|= sqlite3WhereGetMask(&pWInfo
->sMaskSet
, pAndTerm
->leftCursor
);
653 }else if( pOrTerm
->wtFlags
& TERM_COPIED
){
654 /* Skip this term for now. We revisit it when we process the
655 ** corresponding TERM_VIRTUAL term */
658 b
= sqlite3WhereGetMask(&pWInfo
->sMaskSet
, pOrTerm
->leftCursor
);
659 if( pOrTerm
->wtFlags
& TERM_VIRTUAL
){
660 WhereTerm
*pOther
= &pOrWc
->a
[pOrTerm
->iParent
];
661 b
|= sqlite3WhereGetMask(&pWInfo
->sMaskSet
, pOther
->leftCursor
);
664 if( (pOrTerm
->eOperator
& WO_EQ
)==0 ){
673 ** Record the set of tables that satisfy case 3. The set might be
676 pOrInfo
->indexable
= indexable
;
678 pTerm
->eOperator
= WO_OR
;
681 pTerm
->eOperator
= WO_OR
;
684 /* For a two-way OR, attempt to implementation case 2.
686 if( indexable
&& pOrWc
->nTerm
==2 ){
689 while( (pOne
= whereNthSubterm(&pOrWc
->a
[0],iOne
++))!=0 ){
692 while( (pTwo
= whereNthSubterm(&pOrWc
->a
[1],iTwo
++))!=0 ){
693 whereCombineDisjuncts(pSrc
, pWC
, pOne
, pTwo
);
699 ** chngToIN holds a set of tables that *might* satisfy case 1. But
700 ** we have to do some additional checking to see if case 1 really
703 ** chngToIN will hold either 0, 1, or 2 bits. The 0-bit case means
704 ** that there is no possibility of transforming the OR clause into an
705 ** IN operator because one or more terms in the OR clause contain
706 ** something other than == on a column in the single table. The 1-bit
707 ** case means that every term of the OR clause is of the form
708 ** "table.column=expr" for some single table. The one bit that is set
709 ** will correspond to the common table. We still need to check to make
710 ** sure the same column is used on all terms. The 2-bit case is when
711 ** the all terms are of the form "table1.column=table2.column". It
712 ** might be possible to form an IN operator with either table1.column
713 ** or table2.column as the LHS if either is common to every term of
716 ** Note that terms of the form "table.column1=table.column2" (the
717 ** same table on both sizes of the ==) cannot be optimized.
720 int okToChngToIN
= 0; /* True if the conversion to IN is valid */
721 int iColumn
= -1; /* Column index on lhs of IN operator */
722 int iCursor
= -1; /* Table cursor common to all terms */
723 int j
= 0; /* Loop counter */
725 /* Search for a table and column that appears on one side or the
726 ** other of the == operator in every subterm. That table and column
727 ** will be recorded in iCursor and iColumn. There might not be any
728 ** such table and column. Set okToChngToIN if an appropriate table
729 ** and column is found but leave okToChngToIN false if not found.
731 for(j
=0; j
<2 && !okToChngToIN
; j
++){
733 for(i
=pOrWc
->nTerm
-1; i
>=0; i
--, pOrTerm
++){
734 assert( pOrTerm
->eOperator
& WO_EQ
);
735 pOrTerm
->wtFlags
&= ~TERM_OR_OK
;
736 if( pOrTerm
->leftCursor
==iCursor
){
737 /* This is the 2-bit case and we are on the second iteration and
738 ** current term is from the first iteration. So skip this term. */
742 if( (chngToIN
& sqlite3WhereGetMask(&pWInfo
->sMaskSet
,
743 pOrTerm
->leftCursor
))==0 ){
744 /* This term must be of the form t1.a==t2.b where t2 is in the
745 ** chngToIN set but t1 is not. This term will be either preceded
746 ** or follwed by an inverted copy (t2.b==t1.a). Skip this term
747 ** and use its inversion. */
748 testcase( pOrTerm
->wtFlags
& TERM_COPIED
);
749 testcase( pOrTerm
->wtFlags
& TERM_VIRTUAL
);
750 assert( pOrTerm
->wtFlags
& (TERM_COPIED
|TERM_VIRTUAL
) );
753 iColumn
= pOrTerm
->u
.leftColumn
;
754 iCursor
= pOrTerm
->leftCursor
;
758 /* No candidate table+column was found. This can only occur
759 ** on the second iteration */
761 assert( IsPowerOfTwo(chngToIN
) );
762 assert( chngToIN
==sqlite3WhereGetMask(&pWInfo
->sMaskSet
, iCursor
) );
767 /* We have found a candidate table and column. Check to see if that
768 ** table and column is common to every term in the OR clause */
770 for(; i
>=0 && okToChngToIN
; i
--, pOrTerm
++){
771 assert( pOrTerm
->eOperator
& WO_EQ
);
772 if( pOrTerm
->leftCursor
!=iCursor
){
773 pOrTerm
->wtFlags
&= ~TERM_OR_OK
;
774 }else if( pOrTerm
->u
.leftColumn
!=iColumn
){
777 int affLeft
, affRight
;
778 /* If the right-hand side is also a column, then the affinities
779 ** of both right and left sides must be such that no type
780 ** conversions are required on the right. (Ticket #2249)
782 affRight
= sqlite3ExprAffinity(pOrTerm
->pExpr
->pRight
);
783 affLeft
= sqlite3ExprAffinity(pOrTerm
->pExpr
->pLeft
);
784 if( affRight
!=0 && affRight
!=affLeft
){
787 pOrTerm
->wtFlags
|= TERM_OR_OK
;
793 /* At this point, okToChngToIN is true if original pTerm satisfies
794 ** case 1. In that case, construct a new virtual term that is
795 ** pTerm converted into an IN operator.
798 Expr
*pDup
; /* A transient duplicate expression */
799 ExprList
*pList
= 0; /* The RHS of the IN operator */
800 Expr
*pLeft
= 0; /* The LHS of the IN operator */
801 Expr
*pNew
; /* The complete IN operator */
803 for(i
=pOrWc
->nTerm
-1, pOrTerm
=pOrWc
->a
; i
>=0; i
--, pOrTerm
++){
804 if( (pOrTerm
->wtFlags
& TERM_OR_OK
)==0 ) continue;
805 assert( pOrTerm
->eOperator
& WO_EQ
);
806 assert( pOrTerm
->leftCursor
==iCursor
);
807 assert( pOrTerm
->u
.leftColumn
==iColumn
);
808 pDup
= sqlite3ExprDup(db
, pOrTerm
->pExpr
->pRight
, 0);
809 pList
= sqlite3ExprListAppend(pWInfo
->pParse
, pList
, pDup
);
810 pLeft
= pOrTerm
->pExpr
->pLeft
;
813 pDup
= sqlite3ExprDup(db
, pLeft
, 0);
814 pNew
= sqlite3PExpr(pParse
, TK_IN
, pDup
, 0);
817 transferJoinMarkings(pNew
, pExpr
);
818 assert( !ExprHasProperty(pNew
, EP_xIsSelect
) );
819 pNew
->x
.pList
= pList
;
820 idxNew
= whereClauseInsert(pWC
, pNew
, TERM_VIRTUAL
|TERM_DYNAMIC
);
821 testcase( idxNew
==0 );
822 exprAnalyze(pSrc
, pWC
, idxNew
);
823 pTerm
= &pWC
->a
[idxTerm
];
824 markTermAsChild(pWC
, idxNew
, idxTerm
);
826 sqlite3ExprListDelete(db
, pList
);
831 #endif /* !SQLITE_OMIT_OR_OPTIMIZATION && !SQLITE_OMIT_SUBQUERY */
834 ** We already know that pExpr is a binary operator where both operands are
835 ** column references. This routine checks to see if pExpr is an equivalence
837 ** 1. The SQLITE_Transitive optimization must be enabled
838 ** 2. Must be either an == or an IS operator
839 ** 3. Not originating in the ON clause of an OUTER JOIN
840 ** 4. The affinities of A and B must be compatible
841 ** 5a. Both operands use the same collating sequence OR
842 ** 5b. The overall collating sequence is BINARY
843 ** If this routine returns TRUE, that means that the RHS can be substituted
844 ** for the LHS anyplace else in the WHERE clause where the LHS column occurs.
845 ** This is an optimization. No harm comes from returning 0. But if 1 is
846 ** returned when it should not be, then incorrect answers might result.
848 static int termIsEquivalence(Parse
*pParse
, Expr
*pExpr
){
851 if( !OptimizationEnabled(pParse
->db
, SQLITE_Transitive
) ) return 0;
852 if( pExpr
->op
!=TK_EQ
&& pExpr
->op
!=TK_IS
) return 0;
853 if( ExprHasProperty(pExpr
, EP_FromJoin
) ) return 0;
854 aff1
= sqlite3ExprAffinity(pExpr
->pLeft
);
855 aff2
= sqlite3ExprAffinity(pExpr
->pRight
);
857 && (!sqlite3IsNumericAffinity(aff1
) || !sqlite3IsNumericAffinity(aff2
))
861 pColl
= sqlite3BinaryCompareCollSeq(pParse
, pExpr
->pLeft
, pExpr
->pRight
);
862 if( pColl
==0 || sqlite3StrICmp(pColl
->zName
, "BINARY")==0 ) return 1;
863 return sqlite3ExprCollSeqMatch(pParse
, pExpr
->pLeft
, pExpr
->pRight
);
867 ** Recursively walk the expressions of a SELECT statement and generate
868 ** a bitmask indicating which tables are used in that expression
871 static Bitmask
exprSelectUsage(WhereMaskSet
*pMaskSet
, Select
*pS
){
874 SrcList
*pSrc
= pS
->pSrc
;
875 mask
|= sqlite3WhereExprListUsage(pMaskSet
, pS
->pEList
);
876 mask
|= sqlite3WhereExprListUsage(pMaskSet
, pS
->pGroupBy
);
877 mask
|= sqlite3WhereExprListUsage(pMaskSet
, pS
->pOrderBy
);
878 mask
|= sqlite3WhereExprUsage(pMaskSet
, pS
->pWhere
);
879 mask
|= sqlite3WhereExprUsage(pMaskSet
, pS
->pHaving
);
880 if( ALWAYS(pSrc
!=0) ){
882 for(i
=0; i
<pSrc
->nSrc
; i
++){
883 mask
|= exprSelectUsage(pMaskSet
, pSrc
->a
[i
].pSelect
);
884 mask
|= sqlite3WhereExprUsage(pMaskSet
, pSrc
->a
[i
].pOn
);
885 if( pSrc
->a
[i
].fg
.isTabFunc
){
886 mask
|= sqlite3WhereExprListUsage(pMaskSet
, pSrc
->a
[i
].u1
.pFuncArg
);
896 ** Expression pExpr is one operand of a comparison operator that might
897 ** be useful for indexing. This routine checks to see if pExpr appears
898 ** in any index. Return TRUE (1) if pExpr is an indexed term and return
899 ** FALSE (0) if not. If TRUE is returned, also set aiCurCol[0] to the cursor
900 ** number of the table that is indexed and aiCurCol[1] to the column number
901 ** of the column that is indexed, or XN_EXPR (-2) if an expression is being
904 ** If pExpr is a TK_COLUMN column reference, then this routine always returns
905 ** true even if that particular column is not indexed, because the column
906 ** might be added to an automatic index later.
908 static SQLITE_NOINLINE
int exprMightBeIndexed2(
909 SrcList
*pFrom
, /* The FROM clause */
910 Bitmask mPrereq
, /* Bitmask of FROM clause terms referenced by pExpr */
911 int *aiCurCol
, /* Write the referenced table cursor and column here */
912 Expr
*pExpr
/* An operand of a comparison operator */
917 for(i
=0; mPrereq
>1; i
++, mPrereq
>>=1){}
918 iCur
= pFrom
->a
[i
].iCursor
;
919 for(pIdx
=pFrom
->a
[i
].pTab
->pIndex
; pIdx
; pIdx
=pIdx
->pNext
){
920 if( pIdx
->aColExpr
==0 ) continue;
921 for(i
=0; i
<pIdx
->nKeyCol
; i
++){
922 if( pIdx
->aiColumn
[i
]!=XN_EXPR
) continue;
923 if( sqlite3ExprCompareSkip(pExpr
, pIdx
->aColExpr
->a
[i
].pExpr
, iCur
)==0 ){
925 aiCurCol
[1] = XN_EXPR
;
932 static int exprMightBeIndexed(
933 SrcList
*pFrom
, /* The FROM clause */
934 Bitmask mPrereq
, /* Bitmask of FROM clause terms referenced by pExpr */
935 int *aiCurCol
, /* Write the referenced table cursor & column here */
936 Expr
*pExpr
, /* An operand of a comparison operator */
937 int op
/* The specific comparison operator */
939 /* If this expression is a vector to the left or right of a
940 ** inequality constraint (>, <, >= or <=), perform the processing
941 ** on the first element of the vector. */
942 assert( TK_GT
+1==TK_LE
&& TK_GT
+2==TK_LT
&& TK_GT
+3==TK_GE
);
943 assert( TK_IS
<TK_GE
&& TK_ISNULL
<TK_GE
&& TK_IN
<TK_GE
);
945 if( pExpr
->op
==TK_VECTOR
&& (op
>=TK_GT
&& ALWAYS(op
<=TK_GE
)) ){
946 pExpr
= pExpr
->x
.pList
->a
[0].pExpr
;
949 if( pExpr
->op
==TK_COLUMN
){
950 aiCurCol
[0] = pExpr
->iTable
;
951 aiCurCol
[1] = pExpr
->iColumn
;
954 if( mPrereq
==0 ) return 0; /* No table references */
955 if( (mPrereq
&(mPrereq
-1))!=0 ) return 0; /* Refs more than one table */
956 return exprMightBeIndexed2(pFrom
,mPrereq
,aiCurCol
,pExpr
);
960 ** The input to this routine is an WhereTerm structure with only the
961 ** "pExpr" field filled in. The job of this routine is to analyze the
962 ** subexpression and populate all the other fields of the WhereTerm
965 ** If the expression is of the form "<expr> <op> X" it gets commuted
966 ** to the standard form of "X <op> <expr>".
968 ** If the expression is of the form "X <op> Y" where both X and Y are
969 ** columns, then the original expression is unchanged and a new virtual
970 ** term of the form "Y <op> X" is added to the WHERE clause and
971 ** analyzed separately. The original term is marked with TERM_COPIED
972 ** and the new term is marked with TERM_DYNAMIC (because it's pExpr
973 ** needs to be freed with the WhereClause) and TERM_VIRTUAL (because it
974 ** is a commuted copy of a prior term.) The original term has nChild=1
975 ** and the copy has idxParent set to the index of the original term.
977 static void exprAnalyze(
978 SrcList
*pSrc
, /* the FROM clause */
979 WhereClause
*pWC
, /* the WHERE clause */
980 int idxTerm
/* Index of the term to be analyzed */
982 WhereInfo
*pWInfo
= pWC
->pWInfo
; /* WHERE clause processing context */
983 WhereTerm
*pTerm
; /* The term to be analyzed */
984 WhereMaskSet
*pMaskSet
; /* Set of table index masks */
985 Expr
*pExpr
; /* The expression to be analyzed */
986 Bitmask prereqLeft
; /* Prerequesites of the pExpr->pLeft */
987 Bitmask prereqAll
; /* Prerequesites of pExpr */
988 Bitmask extraRight
= 0; /* Extra dependencies on LEFT JOIN */
989 Expr
*pStr1
= 0; /* RHS of LIKE/GLOB operator */
990 int isComplete
= 0; /* RHS of LIKE/GLOB ends with wildcard */
991 int noCase
= 0; /* uppercase equivalent to lowercase */
992 int op
; /* Top-level operator. pExpr->op */
993 Parse
*pParse
= pWInfo
->pParse
; /* Parsing context */
994 sqlite3
*db
= pParse
->db
; /* Database connection */
995 unsigned char eOp2
= 0; /* op2 value for LIKE/REGEXP/GLOB */
996 int nLeft
; /* Number of elements on left side vector */
998 if( db
->mallocFailed
){
1001 pTerm
= &pWC
->a
[idxTerm
];
1002 pMaskSet
= &pWInfo
->sMaskSet
;
1003 pExpr
= pTerm
->pExpr
;
1004 assert( pExpr
->op
!=TK_AS
&& pExpr
->op
!=TK_COLLATE
);
1005 prereqLeft
= sqlite3WhereExprUsage(pMaskSet
, pExpr
->pLeft
);
1008 assert( pExpr
->pRight
==0 );
1009 if( sqlite3ExprCheckIN(pParse
, pExpr
) ) return;
1010 if( ExprHasProperty(pExpr
, EP_xIsSelect
) ){
1011 pTerm
->prereqRight
= exprSelectUsage(pMaskSet
, pExpr
->x
.pSelect
);
1013 pTerm
->prereqRight
= sqlite3WhereExprListUsage(pMaskSet
, pExpr
->x
.pList
);
1015 }else if( op
==TK_ISNULL
){
1016 pTerm
->prereqRight
= 0;
1018 pTerm
->prereqRight
= sqlite3WhereExprUsage(pMaskSet
, pExpr
->pRight
);
1020 pMaskSet
->bVarSelect
= 0;
1021 prereqAll
= sqlite3WhereExprUsageNN(pMaskSet
, pExpr
);
1022 if( pMaskSet
->bVarSelect
) pTerm
->wtFlags
|= TERM_VARSELECT
;
1023 if( ExprHasProperty(pExpr
, EP_FromJoin
) ){
1024 Bitmask x
= sqlite3WhereGetMask(pMaskSet
, pExpr
->iRightJoinTable
);
1026 extraRight
= x
-1; /* ON clause terms may not be used with an index
1027 ** on left table of a LEFT JOIN. Ticket #3015 */
1028 if( (prereqAll
>>1)>=x
){
1029 sqlite3ErrorMsg(pParse
, "ON clause references tables to its right");
1033 pTerm
->prereqAll
= prereqAll
;
1034 pTerm
->leftCursor
= -1;
1035 pTerm
->iParent
= -1;
1036 pTerm
->eOperator
= 0;
1037 if( allowedOp(op
) ){
1039 Expr
*pLeft
= sqlite3ExprSkipCollate(pExpr
->pLeft
);
1040 Expr
*pRight
= sqlite3ExprSkipCollate(pExpr
->pRight
);
1041 u16 opMask
= (pTerm
->prereqRight
& prereqLeft
)==0 ? WO_ALL
: WO_EQUIV
;
1043 if( pTerm
->iField
>0 ){
1044 assert( op
==TK_IN
);
1045 assert( pLeft
->op
==TK_VECTOR
);
1046 pLeft
= pLeft
->x
.pList
->a
[pTerm
->iField
-1].pExpr
;
1049 if( exprMightBeIndexed(pSrc
, prereqLeft
, aiCurCol
, pLeft
, op
) ){
1050 pTerm
->leftCursor
= aiCurCol
[0];
1051 pTerm
->u
.leftColumn
= aiCurCol
[1];
1052 pTerm
->eOperator
= operatorMask(op
) & opMask
;
1054 if( op
==TK_IS
) pTerm
->wtFlags
|= TERM_IS
;
1056 && exprMightBeIndexed(pSrc
, pTerm
->prereqRight
, aiCurCol
, pRight
, op
)
1060 u16 eExtraOp
= 0; /* Extra bits for pNew->eOperator */
1061 assert( pTerm
->iField
==0 );
1062 if( pTerm
->leftCursor
>=0 ){
1064 pDup
= sqlite3ExprDup(db
, pExpr
, 0);
1065 if( db
->mallocFailed
){
1066 sqlite3ExprDelete(db
, pDup
);
1069 idxNew
= whereClauseInsert(pWC
, pDup
, TERM_VIRTUAL
|TERM_DYNAMIC
);
1070 if( idxNew
==0 ) return;
1071 pNew
= &pWC
->a
[idxNew
];
1072 markTermAsChild(pWC
, idxNew
, idxTerm
);
1073 if( op
==TK_IS
) pNew
->wtFlags
|= TERM_IS
;
1074 pTerm
= &pWC
->a
[idxTerm
];
1075 pTerm
->wtFlags
|= TERM_COPIED
;
1077 if( termIsEquivalence(pParse
, pDup
) ){
1078 pTerm
->eOperator
|= WO_EQUIV
;
1079 eExtraOp
= WO_EQUIV
;
1085 exprCommute(pParse
, pDup
);
1086 pNew
->leftCursor
= aiCurCol
[0];
1087 pNew
->u
.leftColumn
= aiCurCol
[1];
1088 testcase( (prereqLeft
| extraRight
) != prereqLeft
);
1089 pNew
->prereqRight
= prereqLeft
| extraRight
;
1090 pNew
->prereqAll
= prereqAll
;
1091 pNew
->eOperator
= (operatorMask(pDup
->op
) + eExtraOp
) & opMask
;
1095 #ifndef SQLITE_OMIT_BETWEEN_OPTIMIZATION
1096 /* If a term is the BETWEEN operator, create two new virtual terms
1097 ** that define the range that the BETWEEN implements. For example:
1099 ** a BETWEEN b AND c
1101 ** is converted into:
1103 ** (a BETWEEN b AND c) AND (a>=b) AND (a<=c)
1105 ** The two new terms are added onto the end of the WhereClause object.
1106 ** The new terms are "dynamic" and are children of the original BETWEEN
1107 ** term. That means that if the BETWEEN term is coded, the children are
1108 ** skipped. Or, if the children are satisfied by an index, the original
1109 ** BETWEEN term is skipped.
1111 else if( pExpr
->op
==TK_BETWEEN
&& pWC
->op
==TK_AND
){
1112 ExprList
*pList
= pExpr
->x
.pList
;
1114 static const u8 ops
[] = {TK_GE
, TK_LE
};
1116 assert( pList
->nExpr
==2 );
1120 pNewExpr
= sqlite3PExpr(pParse
, ops
[i
],
1121 sqlite3ExprDup(db
, pExpr
->pLeft
, 0),
1122 sqlite3ExprDup(db
, pList
->a
[i
].pExpr
, 0));
1123 transferJoinMarkings(pNewExpr
, pExpr
);
1124 idxNew
= whereClauseInsert(pWC
, pNewExpr
, TERM_VIRTUAL
|TERM_DYNAMIC
);
1125 testcase( idxNew
==0 );
1126 exprAnalyze(pSrc
, pWC
, idxNew
);
1127 pTerm
= &pWC
->a
[idxTerm
];
1128 markTermAsChild(pWC
, idxNew
, idxTerm
);
1131 #endif /* SQLITE_OMIT_BETWEEN_OPTIMIZATION */
1133 #if !defined(SQLITE_OMIT_OR_OPTIMIZATION) && !defined(SQLITE_OMIT_SUBQUERY)
1134 /* Analyze a term that is composed of two or more subterms connected by
1137 else if( pExpr
->op
==TK_OR
){
1138 assert( pWC
->op
==TK_AND
);
1139 exprAnalyzeOrTerm(pSrc
, pWC
, idxTerm
);
1140 pTerm
= &pWC
->a
[idxTerm
];
1142 #endif /* SQLITE_OMIT_OR_OPTIMIZATION */
1144 #ifndef SQLITE_OMIT_LIKE_OPTIMIZATION
1145 /* Add constraints to reduce the search space on a LIKE or GLOB
1148 ** A like pattern of the form "x LIKE 'aBc%'" is changed into constraints
1150 ** x>='ABC' AND x<'abd' AND x LIKE 'aBc%'
1152 ** The last character of the prefix "abc" is incremented to form the
1153 ** termination condition "abd". If case is not significant (the default
1154 ** for LIKE) then the lower-bound is made all uppercase and the upper-
1155 ** bound is made all lowercase so that the bounds also work when comparing
1159 && isLikeOrGlob(pParse
, pExpr
, &pStr1
, &isComplete
, &noCase
)
1161 Expr
*pLeft
; /* LHS of LIKE/GLOB operator */
1162 Expr
*pStr2
; /* Copy of pStr1 - RHS of LIKE/GLOB operator */
1167 const char *zCollSeqName
; /* Name of collating sequence */
1168 const u16 wtFlags
= TERM_LIKEOPT
| TERM_VIRTUAL
| TERM_DYNAMIC
;
1170 pLeft
= pExpr
->x
.pList
->a
[1].pExpr
;
1171 pStr2
= sqlite3ExprDup(db
, pStr1
, 0);
1173 /* Convert the lower bound to upper-case and the upper bound to
1174 ** lower-case (upper-case is less than lower-case in ASCII) so that
1175 ** the range constraints also work for BLOBs
1177 if( noCase
&& !pParse
->db
->mallocFailed
){
1180 pTerm
->wtFlags
|= TERM_LIKE
;
1181 for(i
=0; (c
= pStr1
->u
.zToken
[i
])!=0; i
++){
1182 pStr1
->u
.zToken
[i
] = sqlite3Toupper(c
);
1183 pStr2
->u
.zToken
[i
] = sqlite3Tolower(c
);
1187 if( !db
->mallocFailed
){
1188 u8 c
, *pC
; /* Last character before the first wildcard */
1189 pC
= (u8
*)&pStr2
->u
.zToken
[sqlite3Strlen30(pStr2
->u
.zToken
)-1];
1192 /* The point is to increment the last character before the first
1193 ** wildcard. But if we increment '@', that will push it into the
1194 ** alphabetic range where case conversions will mess up the
1195 ** inequality. To avoid this, make sure to also run the full
1196 ** LIKE on all candidate expressions by clearing the isComplete flag
1198 if( c
=='A'-1 ) isComplete
= 0;
1199 c
= sqlite3UpperToLower
[c
];
1203 zCollSeqName
= noCase
? "NOCASE" : "BINARY";
1204 pNewExpr1
= sqlite3ExprDup(db
, pLeft
, 0);
1205 pNewExpr1
= sqlite3PExpr(pParse
, TK_GE
,
1206 sqlite3ExprAddCollateString(pParse
,pNewExpr1
,zCollSeqName
),
1208 transferJoinMarkings(pNewExpr1
, pExpr
);
1209 idxNew1
= whereClauseInsert(pWC
, pNewExpr1
, wtFlags
);
1210 testcase( idxNew1
==0 );
1211 exprAnalyze(pSrc
, pWC
, idxNew1
);
1212 pNewExpr2
= sqlite3ExprDup(db
, pLeft
, 0);
1213 pNewExpr2
= sqlite3PExpr(pParse
, TK_LT
,
1214 sqlite3ExprAddCollateString(pParse
,pNewExpr2
,zCollSeqName
),
1216 transferJoinMarkings(pNewExpr2
, pExpr
);
1217 idxNew2
= whereClauseInsert(pWC
, pNewExpr2
, wtFlags
);
1218 testcase( idxNew2
==0 );
1219 exprAnalyze(pSrc
, pWC
, idxNew2
);
1220 pTerm
= &pWC
->a
[idxTerm
];
1222 markTermAsChild(pWC
, idxNew1
, idxTerm
);
1223 markTermAsChild(pWC
, idxNew2
, idxTerm
);
1226 #endif /* SQLITE_OMIT_LIKE_OPTIMIZATION */
1228 #ifndef SQLITE_OMIT_VIRTUALTABLE
1229 /* Add a WO_AUX auxiliary term to the constraint set if the
1230 ** current expression is of the form "column OP expr" where OP
1231 ** is an operator that gets passed into virtual tables but which is
1232 ** not normally optimized for ordinary tables. In other words, OP
1233 ** is one of MATCH, LIKE, GLOB, REGEXP, !=, IS, IS NOT, or NOT NULL.
1234 ** This information is used by the xBestIndex methods of
1235 ** virtual tables. The native query optimizer does not attempt
1236 ** to do anything with MATCH functions.
1238 if( pWC
->op
==TK_AND
){
1239 Expr
*pRight
= 0, *pLeft
= 0;
1240 int res
= isAuxiliaryVtabOperator(pExpr
, &eOp2
, &pLeft
, &pRight
);
1243 WhereTerm
*pNewTerm
;
1244 Bitmask prereqColumn
, prereqExpr
;
1246 prereqExpr
= sqlite3WhereExprUsage(pMaskSet
, pRight
);
1247 prereqColumn
= sqlite3WhereExprUsage(pMaskSet
, pLeft
);
1248 if( (prereqExpr
& prereqColumn
)==0 ){
1250 pNewExpr
= sqlite3PExpr(pParse
, TK_MATCH
,
1251 0, sqlite3ExprDup(db
, pRight
, 0));
1252 if( ExprHasProperty(pExpr
, EP_FromJoin
) && pNewExpr
){
1253 ExprSetProperty(pNewExpr
, EP_FromJoin
);
1255 idxNew
= whereClauseInsert(pWC
, pNewExpr
, TERM_VIRTUAL
|TERM_DYNAMIC
);
1256 testcase( idxNew
==0 );
1257 pNewTerm
= &pWC
->a
[idxNew
];
1258 pNewTerm
->prereqRight
= prereqExpr
;
1259 pNewTerm
->leftCursor
= pLeft
->iTable
;
1260 pNewTerm
->u
.leftColumn
= pLeft
->iColumn
;
1261 pNewTerm
->eOperator
= WO_AUX
;
1262 pNewTerm
->eMatchOp
= eOp2
;
1263 markTermAsChild(pWC
, idxNew
, idxTerm
);
1264 pTerm
= &pWC
->a
[idxTerm
];
1265 pTerm
->wtFlags
|= TERM_COPIED
;
1266 pNewTerm
->prereqAll
= pTerm
->prereqAll
;
1268 SWAP(Expr
*, pLeft
, pRight
);
1271 #endif /* SQLITE_OMIT_VIRTUALTABLE */
1273 /* If there is a vector == or IS term - e.g. "(a, b) == (?, ?)" - create
1274 ** new terms for each component comparison - "a = ?" and "b = ?". The
1275 ** new terms completely replace the original vector comparison, which is
1278 ** This is only required if at least one side of the comparison operation
1279 ** is not a sub-select. */
1281 && (pExpr
->op
==TK_EQ
|| pExpr
->op
==TK_IS
)
1282 && (nLeft
= sqlite3ExprVectorSize(pExpr
->pLeft
))>1
1283 && sqlite3ExprVectorSize(pExpr
->pRight
)==nLeft
1284 && ( (pExpr
->pLeft
->flags
& EP_xIsSelect
)==0
1285 || (pExpr
->pRight
->flags
& EP_xIsSelect
)==0)
1288 for(i
=0; i
<nLeft
; i
++){
1291 Expr
*pLeft
= sqlite3ExprForVectorField(pParse
, pExpr
->pLeft
, i
);
1292 Expr
*pRight
= sqlite3ExprForVectorField(pParse
, pExpr
->pRight
, i
);
1294 pNew
= sqlite3PExpr(pParse
, pExpr
->op
, pLeft
, pRight
);
1295 transferJoinMarkings(pNew
, pExpr
);
1296 idxNew
= whereClauseInsert(pWC
, pNew
, TERM_DYNAMIC
);
1297 exprAnalyze(pSrc
, pWC
, idxNew
);
1299 pTerm
= &pWC
->a
[idxTerm
];
1300 pTerm
->wtFlags
|= TERM_CODED
|TERM_VIRTUAL
; /* Disable the original */
1301 pTerm
->eOperator
= 0;
1304 /* If there is a vector IN term - e.g. "(a, b) IN (SELECT ...)" - create
1305 ** a virtual term for each vector component. The expression object
1306 ** used by each such virtual term is pExpr (the full vector IN(...)
1307 ** expression). The WhereTerm.iField variable identifies the index within
1308 ** the vector on the LHS that the virtual term represents.
1310 ** This only works if the RHS is a simple SELECT, not a compound
1312 if( pWC
->op
==TK_AND
&& pExpr
->op
==TK_IN
&& pTerm
->iField
==0
1313 && pExpr
->pLeft
->op
==TK_VECTOR
1314 && pExpr
->x
.pSelect
->pPrior
==0
1317 for(i
=0; i
<sqlite3ExprVectorSize(pExpr
->pLeft
); i
++){
1319 idxNew
= whereClauseInsert(pWC
, pExpr
, TERM_VIRTUAL
);
1320 pWC
->a
[idxNew
].iField
= i
+1;
1321 exprAnalyze(pSrc
, pWC
, idxNew
);
1322 markTermAsChild(pWC
, idxNew
, idxTerm
);
1326 #ifdef SQLITE_ENABLE_STAT3_OR_STAT4
1327 /* When sqlite_stat3 histogram data is available an operator of the
1328 ** form "x IS NOT NULL" can sometimes be evaluated more efficiently
1329 ** as "x>NULL" if x is not an INTEGER PRIMARY KEY. So construct a
1330 ** virtual term of that form.
1332 ** Note that the virtual term must be tagged with TERM_VNULL.
1334 if( pExpr
->op
==TK_NOTNULL
1335 && pExpr
->pLeft
->op
==TK_COLUMN
1336 && pExpr
->pLeft
->iColumn
>=0
1337 && OptimizationEnabled(db
, SQLITE_Stat34
)
1340 Expr
*pLeft
= pExpr
->pLeft
;
1342 WhereTerm
*pNewTerm
;
1344 pNewExpr
= sqlite3PExpr(pParse
, TK_GT
,
1345 sqlite3ExprDup(db
, pLeft
, 0),
1346 sqlite3ExprAlloc(db
, TK_NULL
, 0, 0));
1348 idxNew
= whereClauseInsert(pWC
, pNewExpr
,
1349 TERM_VIRTUAL
|TERM_DYNAMIC
|TERM_VNULL
);
1351 pNewTerm
= &pWC
->a
[idxNew
];
1352 pNewTerm
->prereqRight
= 0;
1353 pNewTerm
->leftCursor
= pLeft
->iTable
;
1354 pNewTerm
->u
.leftColumn
= pLeft
->iColumn
;
1355 pNewTerm
->eOperator
= WO_GT
;
1356 markTermAsChild(pWC
, idxNew
, idxTerm
);
1357 pTerm
= &pWC
->a
[idxTerm
];
1358 pTerm
->wtFlags
|= TERM_COPIED
;
1359 pNewTerm
->prereqAll
= pTerm
->prereqAll
;
1362 #endif /* SQLITE_ENABLE_STAT3_OR_STAT4 */
1364 /* Prevent ON clause terms of a LEFT JOIN from being used to drive
1365 ** an index for tables to the left of the join.
1367 testcase( pTerm
!=&pWC
->a
[idxTerm
] );
1368 pTerm
= &pWC
->a
[idxTerm
];
1369 pTerm
->prereqRight
|= extraRight
;
1372 /***************************************************************************
1373 ** Routines with file scope above. Interface to the rest of the where.c
1374 ** subsystem follows.
1375 ***************************************************************************/
1378 ** This routine identifies subexpressions in the WHERE clause where
1379 ** each subexpression is separated by the AND operator or some other
1380 ** operator specified in the op parameter. The WhereClause structure
1381 ** is filled with pointers to subexpressions. For example:
1383 ** WHERE a=='hello' AND coalesce(b,11)<10 AND (c+12!=d OR c==22)
1384 ** \________/ \_______________/ \________________/
1385 ** slot[0] slot[1] slot[2]
1387 ** The original WHERE clause in pExpr is unaltered. All this routine
1388 ** does is make slot[] entries point to substructure within pExpr.
1390 ** In the previous sentence and in the diagram, "slot[]" refers to
1391 ** the WhereClause.a[] array. The slot[] array grows as needed to contain
1392 ** all terms of the WHERE clause.
1394 void sqlite3WhereSplit(WhereClause
*pWC
, Expr
*pExpr
, u8 op
){
1395 Expr
*pE2
= sqlite3ExprSkipCollate(pExpr
);
1397 if( pE2
==0 ) return;
1399 whereClauseInsert(pWC
, pExpr
, 0);
1401 sqlite3WhereSplit(pWC
, pE2
->pLeft
, op
);
1402 sqlite3WhereSplit(pWC
, pE2
->pRight
, op
);
1407 ** Initialize a preallocated WhereClause structure.
1409 void sqlite3WhereClauseInit(
1410 WhereClause
*pWC
, /* The WhereClause to be initialized */
1411 WhereInfo
*pWInfo
/* The WHERE processing context */
1413 pWC
->pWInfo
= pWInfo
;
1417 pWC
->nSlot
= ArraySize(pWC
->aStatic
);
1418 pWC
->a
= pWC
->aStatic
;
1422 ** Deallocate a WhereClause structure. The WhereClause structure
1423 ** itself is not freed. This routine is the inverse of
1424 ** sqlite3WhereClauseInit().
1426 void sqlite3WhereClauseClear(WhereClause
*pWC
){
1429 sqlite3
*db
= pWC
->pWInfo
->pParse
->db
;
1430 for(i
=pWC
->nTerm
-1, a
=pWC
->a
; i
>=0; i
--, a
++){
1431 if( a
->wtFlags
& TERM_DYNAMIC
){
1432 sqlite3ExprDelete(db
, a
->pExpr
);
1434 if( a
->wtFlags
& TERM_ORINFO
){
1435 whereOrInfoDelete(db
, a
->u
.pOrInfo
);
1436 }else if( a
->wtFlags
& TERM_ANDINFO
){
1437 whereAndInfoDelete(db
, a
->u
.pAndInfo
);
1440 if( pWC
->a
!=pWC
->aStatic
){
1441 sqlite3DbFree(db
, pWC
->a
);
1447 ** These routines walk (recursively) an expression tree and generate
1448 ** a bitmask indicating which tables are used in that expression
1451 Bitmask
sqlite3WhereExprUsageNN(WhereMaskSet
*pMaskSet
, Expr
*p
){
1453 if( p
->op
==TK_COLUMN
){
1454 return sqlite3WhereGetMask(pMaskSet
, p
->iTable
);
1455 }else if( ExprHasProperty(p
, EP_TokenOnly
|EP_Leaf
) ){
1456 assert( p
->op
!=TK_IF_NULL_ROW
);
1459 mask
= (p
->op
==TK_IF_NULL_ROW
) ? sqlite3WhereGetMask(pMaskSet
, p
->iTable
) : 0;
1460 if( p
->pLeft
) mask
|= sqlite3WhereExprUsageNN(pMaskSet
, p
->pLeft
);
1462 mask
|= sqlite3WhereExprUsageNN(pMaskSet
, p
->pRight
);
1463 assert( p
->x
.pList
==0 );
1464 }else if( ExprHasProperty(p
, EP_xIsSelect
) ){
1465 if( ExprHasProperty(p
, EP_VarSelect
) ) pMaskSet
->bVarSelect
= 1;
1466 mask
|= exprSelectUsage(pMaskSet
, p
->x
.pSelect
);
1467 }else if( p
->x
.pList
){
1468 mask
|= sqlite3WhereExprListUsage(pMaskSet
, p
->x
.pList
);
1472 Bitmask
sqlite3WhereExprUsage(WhereMaskSet
*pMaskSet
, Expr
*p
){
1473 return p
? sqlite3WhereExprUsageNN(pMaskSet
,p
) : 0;
1475 Bitmask
sqlite3WhereExprListUsage(WhereMaskSet
*pMaskSet
, ExprList
*pList
){
1479 for(i
=0; i
<pList
->nExpr
; i
++){
1480 mask
|= sqlite3WhereExprUsage(pMaskSet
, pList
->a
[i
].pExpr
);
1488 ** Call exprAnalyze on all terms in a WHERE clause.
1490 ** Note that exprAnalyze() might add new virtual terms onto the
1491 ** end of the WHERE clause. We do not want to analyze these new
1492 ** virtual terms, so start analyzing at the end and work forward
1493 ** so that the added virtual terms are never processed.
1495 void sqlite3WhereExprAnalyze(
1496 SrcList
*pTabList
, /* the FROM clause */
1497 WhereClause
*pWC
/* the WHERE clause to be analyzed */
1500 for(i
=pWC
->nTerm
-1; i
>=0; i
--){
1501 exprAnalyze(pTabList
, pWC
, i
);
1506 ** For table-valued-functions, transform the function arguments into
1507 ** new WHERE clause terms.
1509 ** Each function argument translates into an equality constraint against
1510 ** a HIDDEN column in the table.
1512 void sqlite3WhereTabFuncArgs(
1513 Parse
*pParse
, /* Parsing context */
1514 struct SrcList_item
*pItem
, /* The FROM clause term to process */
1515 WhereClause
*pWC
/* Xfer function arguments to here */
1522 if( pItem
->fg
.isTabFunc
==0 ) return;
1525 pArgs
= pItem
->u1
.pFuncArg
;
1526 if( pArgs
==0 ) return;
1527 for(j
=k
=0; j
<pArgs
->nExpr
; j
++){
1528 while( k
<pTab
->nCol
&& (pTab
->aCol
[k
].colFlags
& COLFLAG_HIDDEN
)==0 ){k
++;}
1529 if( k
>=pTab
->nCol
){
1530 sqlite3ErrorMsg(pParse
, "too many arguments on %s() - max %d",
1534 pColRef
= sqlite3ExprAlloc(pParse
->db
, TK_COLUMN
, 0, 0);
1535 if( pColRef
==0 ) return;
1536 pColRef
->iTable
= pItem
->iCursor
;
1537 pColRef
->iColumn
= k
++;
1538 pColRef
->pTab
= pTab
;
1539 pTerm
= sqlite3PExpr(pParse
, TK_EQ
, pColRef
,
1540 sqlite3ExprDup(pParse
->db
, pArgs
->a
[j
].pExpr
, 0));
1541 whereClauseInsert(pWC
, pTerm
, TERM_DYNAMIC
);