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 editability. 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
= sqlite3WhereMalloc(pWC
->pWInfo
, 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 pWC
->nSlot
= pWC
->nSlot
*2;
78 pTerm
= &pWC
->a
[idx
= pWC
->nTerm
++];
79 if( (wtFlags
& TERM_VIRTUAL
)==0 ) pWC
->nBase
= pWC
->nTerm
;
80 if( p
&& ExprHasProperty(p
, EP_Unlikely
) ){
81 pTerm
->truthProb
= sqlite3LogEst(p
->iTable
) - 270;
85 pTerm
->pExpr
= sqlite3ExprSkipCollateAndLikely(p
);
86 pTerm
->wtFlags
= wtFlags
;
89 memset(&pTerm
->eOperator
, 0,
90 sizeof(WhereTerm
) - offsetof(WhereTerm
,eOperator
));
95 ** Return TRUE if the given operator is one of the operators that is
96 ** allowed for an indexable WHERE clause term. The allowed operators are
97 ** "=", "<", ">", "<=", ">=", "IN", "IS", and "IS NULL"
99 static int allowedOp(int op
){
100 assert( TK_GT
>TK_EQ
&& TK_GT
<TK_GE
);
101 assert( TK_LT
>TK_EQ
&& TK_LT
<TK_GE
);
102 assert( TK_LE
>TK_EQ
&& TK_LE
<TK_GE
);
103 assert( TK_GE
==TK_EQ
+4 );
104 assert( TK_IN
<TK_EQ
);
105 assert( TK_IS
<TK_EQ
);
106 assert( TK_ISNULL
<TK_EQ
);
107 if( op
>TK_GE
) return 0;
108 if( op
>=TK_EQ
) return 1;
109 return op
==TK_IN
|| op
==TK_ISNULL
|| op
==TK_IS
;
113 ** Commute a comparison operator. Expressions of the form "X op Y"
114 ** are converted into "Y op X".
116 static u16
exprCommute(Parse
*pParse
, Expr
*pExpr
){
117 if( pExpr
->pLeft
->op
==TK_VECTOR
118 || pExpr
->pRight
->op
==TK_VECTOR
119 || sqlite3BinaryCompareCollSeq(pParse
, pExpr
->pLeft
, pExpr
->pRight
) !=
120 sqlite3BinaryCompareCollSeq(pParse
, pExpr
->pRight
, pExpr
->pLeft
)
122 pExpr
->flags
^= EP_Commuted
;
124 SWAP(Expr
*,pExpr
->pRight
,pExpr
->pLeft
);
125 if( pExpr
->op
>=TK_GT
){
126 assert( TK_LT
==TK_GT
+2 );
127 assert( TK_GE
==TK_LE
+2 );
128 assert( TK_GT
>TK_EQ
);
129 assert( TK_GT
<TK_LE
);
130 assert( pExpr
->op
>=TK_GT
&& pExpr
->op
<=TK_GE
);
131 pExpr
->op
= ((pExpr
->op
-TK_GT
)^2)+TK_GT
;
137 ** Translate from TK_xx operator to WO_xx bitmask.
139 static u16
operatorMask(int op
){
141 assert( allowedOp(op
) );
143 assert( (WO_EQ
<<(op
-TK_EQ
)) < 0x7fff );
144 c
= (u16
)(WO_EQ
<<(op
-TK_EQ
));
145 }else if( op
==TK_IN
){
147 }else if( op
==TK_ISNULL
){
153 assert( op
!=TK_ISNULL
|| c
==WO_ISNULL
);
154 assert( op
!=TK_IN
|| c
==WO_IN
);
155 assert( op
!=TK_EQ
|| c
==WO_EQ
);
156 assert( op
!=TK_LT
|| c
==WO_LT
);
157 assert( op
!=TK_LE
|| c
==WO_LE
);
158 assert( op
!=TK_GT
|| c
==WO_GT
);
159 assert( op
!=TK_GE
|| c
==WO_GE
);
160 assert( op
!=TK_IS
|| c
==WO_IS
);
165 #ifndef SQLITE_OMIT_LIKE_OPTIMIZATION
167 ** Check to see if the given expression is a LIKE or GLOB operator that
168 ** can be optimized using inequality constraints. Return TRUE if it is
169 ** so and false if not.
171 ** In order for the operator to be optimizible, the RHS must be a string
172 ** literal that does not begin with a wildcard. The LHS must be a column
173 ** that may only be NULL, a string, or a BLOB, never a number. (This means
174 ** that virtual tables cannot participate in the LIKE optimization.) The
175 ** collating sequence for the column on the LHS must be appropriate for
178 static int isLikeOrGlob(
179 Parse
*pParse
, /* Parsing and code generating context */
180 Expr
*pExpr
, /* Test this expression */
181 Expr
**ppPrefix
, /* Pointer to TK_STRING expression with pattern prefix */
182 int *pisComplete
, /* True if the only wildcard is % in the last character */
183 int *pnoCase
/* True if uppercase is equivalent to lowercase */
185 const u8
*z
= 0; /* String on RHS of LIKE operator */
186 Expr
*pRight
, *pLeft
; /* Right and left size of LIKE operator */
187 ExprList
*pList
; /* List of operands to the LIKE operator */
188 u8 c
; /* One character in z[] */
189 int cnt
; /* Number of non-wildcard prefix characters */
190 u8 wc
[4]; /* Wildcard characters */
191 sqlite3
*db
= pParse
->db
; /* Database connection */
192 sqlite3_value
*pVal
= 0;
193 int op
; /* Opcode of pRight */
194 int rc
; /* Result code to return */
196 if( !sqlite3IsLikeFunction(db
, pExpr
, pnoCase
, (char*)wc
) ){
200 if( *pnoCase
) return 0;
202 assert( ExprUseXList(pExpr
) );
203 pList
= pExpr
->x
.pList
;
204 pLeft
= pList
->a
[1].pExpr
;
206 pRight
= sqlite3ExprSkipCollate(pList
->a
[0].pExpr
);
208 if( op
==TK_VARIABLE
&& (db
->flags
& SQLITE_EnableQPSG
)==0 ){
209 Vdbe
*pReprepare
= pParse
->pReprepare
;
210 int iCol
= pRight
->iColumn
;
211 pVal
= sqlite3VdbeGetBoundValue(pReprepare
, iCol
, SQLITE_AFF_BLOB
);
212 if( pVal
&& sqlite3_value_type(pVal
)==SQLITE_TEXT
){
213 z
= sqlite3_value_text(pVal
);
215 sqlite3VdbeSetVarmask(pParse
->pVdbe
, iCol
);
216 assert( pRight
->op
==TK_VARIABLE
|| pRight
->op
==TK_REGISTER
);
217 }else if( op
==TK_STRING
){
218 assert( !ExprHasProperty(pRight
, EP_IntValue
) );
219 z
= (u8
*)pRight
->u
.zToken
;
223 /* Count the number of prefix characters prior to the first wildcard.
224 ** If the underlying database has a UTF16LE encoding, then only consider
225 ** ASCII characters. Note that the encoding of z[] is UTF8 - we are
226 ** dealing with only UTF8 here in this code, but the database engine
227 ** itself might be processing content using a different encoding. */
229 while( (c
=z
[cnt
])!=0 && c
!=wc
[0] && c
!=wc
[1] && c
!=wc
[2] ){
231 if( c
==wc
[3] && z
[cnt
]!=0 ){
233 }else if( c
>=0x80 && ENC(db
)==SQLITE_UTF16LE
){
239 /* The optimization is possible only if (1) the pattern does not begin
240 ** with a wildcard and if (2) the non-wildcard prefix does not end with
241 ** an (illegal 0xff) character, or (3) the pattern does not consist of
242 ** a single escape character. The second condition is necessary so
243 ** that we can increment the prefix key to find an upper bound for the
244 ** range search. The third is because the caller assumes that the pattern
245 ** consists of at least one character after all escapes have been
247 if( (cnt
>1 || (cnt
>0 && z
[0]!=wc
[3])) && 255!=(u8
)z
[cnt
-1] ){
250 /* A "complete" match if the pattern ends with "*" or "%" */
251 *pisComplete
= c
==wc
[0] && z
[cnt
+1]==0 && ENC(db
)!=SQLITE_UTF16LE
;
253 /* Get the pattern prefix. Remove all escapes from the prefix. */
254 pPrefix
= sqlite3Expr(db
, TK_STRING
, (char*)z
);
258 assert( !ExprHasProperty(pPrefix
, EP_IntValue
) );
259 zNew
= pPrefix
->u
.zToken
;
261 for(iFrom
=iTo
=0; iFrom
<cnt
; iFrom
++){
262 if( zNew
[iFrom
]==wc
[3] ) iFrom
++;
263 zNew
[iTo
++] = zNew
[iFrom
];
268 /* If the LHS is not an ordinary column with TEXT affinity, then the
269 ** pattern prefix boundaries (both the start and end boundaries) must
270 ** not look like a number. Otherwise the pattern might be treated as
271 ** a number, which will invalidate the LIKE optimization.
273 ** Getting this right has been a persistent source of bugs in the
274 ** LIKE optimization. See, for example:
275 ** 2018-09-10 https://sqlite.org/src/info/c94369cae9b561b1
276 ** 2019-05-02 https://sqlite.org/src/info/b043a54c3de54b28
277 ** 2019-06-10 https://sqlite.org/src/info/fd76310a5e843e07
278 ** 2019-06-14 https://sqlite.org/src/info/ce8717f0885af975
279 ** 2019-09-03 https://sqlite.org/src/info/0f0428096f17252a
281 if( pLeft
->op
!=TK_COLUMN
282 || sqlite3ExprAffinity(pLeft
)!=SQLITE_AFF_TEXT
283 || (ALWAYS( ExprUseYTab(pLeft
) )
284 && ALWAYS(pLeft
->y
.pTab
)
285 && IsVirtual(pLeft
->y
.pTab
)) /* Might be numeric */
289 isNum
= sqlite3AtoF(zNew
, &rDummy
, iTo
, SQLITE_UTF8
);
291 if( iTo
==1 && zNew
[0]=='-' ){
295 isNum
= sqlite3AtoF(zNew
, &rDummy
, iTo
, SQLITE_UTF8
);
300 sqlite3ExprDelete(db
, pPrefix
);
301 sqlite3ValueFree(pVal
);
308 /* If the RHS pattern is a bound parameter, make arrangements to
309 ** reprepare the statement when that parameter is rebound */
310 if( op
==TK_VARIABLE
){
311 Vdbe
*v
= pParse
->pVdbe
;
312 sqlite3VdbeSetVarmask(v
, pRight
->iColumn
);
313 assert( !ExprHasProperty(pRight
, EP_IntValue
) );
314 if( *pisComplete
&& pRight
->u
.zToken
[1] ){
315 /* If the rhs of the LIKE expression is a variable, and the current
316 ** value of the variable means there is no need to invoke the LIKE
317 ** function, then no OP_Variable will be added to the program.
318 ** This causes problems for the sqlite3_bind_parameter_name()
319 ** API. To work around them, add a dummy OP_Variable here.
321 int r1
= sqlite3GetTempReg(pParse
);
322 sqlite3ExprCodeTarget(pParse
, pRight
, r1
);
323 sqlite3VdbeChangeP3(v
, sqlite3VdbeCurrentAddr(v
)-1, 0);
324 sqlite3ReleaseTempReg(pParse
, r1
);
333 sqlite3ValueFree(pVal
);
336 #endif /* SQLITE_OMIT_LIKE_OPTIMIZATION */
339 #ifndef SQLITE_OMIT_VIRTUALTABLE
341 ** Check to see if the pExpr expression is a form that needs to be passed
342 ** to the xBestIndex method of virtual tables. Forms of interest include:
344 ** Expression Virtual Table Operator
345 ** ----------------------- ---------------------------------
346 ** 1. column MATCH expr SQLITE_INDEX_CONSTRAINT_MATCH
347 ** 2. column GLOB expr SQLITE_INDEX_CONSTRAINT_GLOB
348 ** 3. column LIKE expr SQLITE_INDEX_CONSTRAINT_LIKE
349 ** 4. column REGEXP expr SQLITE_INDEX_CONSTRAINT_REGEXP
350 ** 5. column != expr SQLITE_INDEX_CONSTRAINT_NE
351 ** 6. expr != column SQLITE_INDEX_CONSTRAINT_NE
352 ** 7. column IS NOT expr SQLITE_INDEX_CONSTRAINT_ISNOT
353 ** 8. expr IS NOT column SQLITE_INDEX_CONSTRAINT_ISNOT
354 ** 9. column IS NOT NULL SQLITE_INDEX_CONSTRAINT_ISNOTNULL
356 ** In every case, "column" must be a column of a virtual table. If there
357 ** is a match, set *ppLeft to the "column" expression, set *ppRight to the
358 ** "expr" expression (even though in forms (6) and (8) the column is on the
359 ** right and the expression is on the left). Also set *peOp2 to the
360 ** appropriate virtual table operator. The return value is 1 or 2 if there
361 ** is a match. The usual return is 1, but if the RHS is also a column
362 ** of virtual table in forms (5) or (7) then return 2.
364 ** If the expression matches none of the patterns above, return 0.
366 static int isAuxiliaryVtabOperator(
367 sqlite3
*db
, /* Parsing context */
368 Expr
*pExpr
, /* Test this expression */
369 unsigned char *peOp2
, /* OUT: 0 for MATCH, or else an op2 value */
370 Expr
**ppLeft
, /* Column expression to left of MATCH/op2 */
371 Expr
**ppRight
/* Expression to left of MATCH/op2 */
373 if( pExpr
->op
==TK_FUNCTION
){
374 static const struct Op2
{
378 { "match", SQLITE_INDEX_CONSTRAINT_MATCH
},
379 { "glob", SQLITE_INDEX_CONSTRAINT_GLOB
},
380 { "like", SQLITE_INDEX_CONSTRAINT_LIKE
},
381 { "regexp", SQLITE_INDEX_CONSTRAINT_REGEXP
}
384 Expr
*pCol
; /* Column reference */
387 assert( ExprUseXList(pExpr
) );
388 pList
= pExpr
->x
.pList
;
389 if( pList
==0 || pList
->nExpr
!=2 ){
393 /* Built-in operators MATCH, GLOB, LIKE, and REGEXP attach to a
394 ** virtual table on their second argument, which is the same as
395 ** the left-hand side operand in their in-fix form.
397 ** vtab_column MATCH expression
398 ** MATCH(expression,vtab_column)
400 pCol
= pList
->a
[1].pExpr
;
401 assert( pCol
->op
!=TK_COLUMN
|| (ExprUseYTab(pCol
) && pCol
->y
.pTab
!=0) );
402 if( ExprIsVtab(pCol
) ){
403 for(i
=0; i
<ArraySize(aOp
); i
++){
404 assert( !ExprHasProperty(pExpr
, EP_IntValue
) );
405 if( sqlite3StrICmp(pExpr
->u
.zToken
, aOp
[i
].zOp
)==0 ){
406 *peOp2
= aOp
[i
].eOp2
;
407 *ppRight
= pList
->a
[0].pExpr
;
414 /* We can also match against the first column of overloaded
415 ** functions where xFindFunction returns a value of at least
416 ** SQLITE_INDEX_CONSTRAINT_FUNCTION.
418 ** OVERLOADED(vtab_column,expression)
420 ** Historically, xFindFunction expected to see lower-case function
421 ** names. But for this use case, xFindFunction is expected to deal
422 ** with function names in an arbitrary case.
424 pCol
= pList
->a
[0].pExpr
;
425 assert( pCol
->op
!=TK_COLUMN
|| ExprUseYTab(pCol
) );
426 assert( pCol
->op
!=TK_COLUMN
|| (ExprUseYTab(pCol
) && pCol
->y
.pTab
!=0) );
427 if( ExprIsVtab(pCol
) ){
429 sqlite3_module
*pMod
;
430 void (*xNotUsed
)(sqlite3_context
*,int,sqlite3_value
**);
432 pVtab
= sqlite3GetVTable(db
, pCol
->y
.pTab
)->pVtab
;
434 assert( pVtab
->pModule
!=0 );
435 assert( !ExprHasProperty(pExpr
, EP_IntValue
) );
436 pMod
= (sqlite3_module
*)pVtab
->pModule
;
437 if( pMod
->xFindFunction
!=0 ){
438 i
= pMod
->xFindFunction(pVtab
,2, pExpr
->u
.zToken
, &xNotUsed
, &pNotUsed
);
439 if( i
>=SQLITE_INDEX_CONSTRAINT_FUNCTION
){
441 *ppRight
= pList
->a
[1].pExpr
;
447 }else if( pExpr
->op
>=TK_EQ
){
448 /* Comparison operators are a common case. Save a few comparisons for
449 ** that common case by terminating early. */
450 assert( TK_NE
< TK_EQ
);
451 assert( TK_ISNOT
< TK_EQ
);
452 assert( TK_NOTNULL
< TK_EQ
);
454 }else if( pExpr
->op
==TK_NE
|| pExpr
->op
==TK_ISNOT
|| pExpr
->op
==TK_NOTNULL
){
456 Expr
*pLeft
= pExpr
->pLeft
;
457 Expr
*pRight
= pExpr
->pRight
;
458 assert( pLeft
->op
!=TK_COLUMN
|| (ExprUseYTab(pLeft
) && pLeft
->y
.pTab
!=0) );
459 if( ExprIsVtab(pLeft
) ){
462 assert( pRight
==0 || pRight
->op
!=TK_COLUMN
463 || (ExprUseYTab(pRight
) && pRight
->y
.pTab
!=0) );
464 if( pRight
&& ExprIsVtab(pRight
) ){
466 SWAP(Expr
*, pLeft
, pRight
);
470 if( pExpr
->op
==TK_NE
) *peOp2
= SQLITE_INDEX_CONSTRAINT_NE
;
471 if( pExpr
->op
==TK_ISNOT
) *peOp2
= SQLITE_INDEX_CONSTRAINT_ISNOT
;
472 if( pExpr
->op
==TK_NOTNULL
) *peOp2
= SQLITE_INDEX_CONSTRAINT_ISNOTNULL
;
477 #endif /* SQLITE_OMIT_VIRTUALTABLE */
480 ** If the pBase expression originated in the ON or USING clause of
481 ** a join, then transfer the appropriate markings over to derived.
483 static void transferJoinMarkings(Expr
*pDerived
, Expr
*pBase
){
484 if( pDerived
&& ExprHasProperty(pBase
, EP_OuterON
|EP_InnerON
) ){
485 pDerived
->flags
|= pBase
->flags
& (EP_OuterON
|EP_InnerON
);
486 pDerived
->w
.iJoin
= pBase
->w
.iJoin
;
491 ** Mark term iChild as being a child of term iParent
493 static void markTermAsChild(WhereClause
*pWC
, int iChild
, int iParent
){
494 pWC
->a
[iChild
].iParent
= iParent
;
495 pWC
->a
[iChild
].truthProb
= pWC
->a
[iParent
].truthProb
;
496 pWC
->a
[iParent
].nChild
++;
500 ** Return the N-th AND-connected subterm of pTerm. Or if pTerm is not
501 ** a conjunction, then return just pTerm when N==0. If N is exceeds
502 ** the number of available subterms, return NULL.
504 static WhereTerm
*whereNthSubterm(WhereTerm
*pTerm
, int N
){
505 if( pTerm
->eOperator
!=WO_AND
){
506 return N
==0 ? pTerm
: 0;
508 if( N
<pTerm
->u
.pAndInfo
->wc
.nTerm
){
509 return &pTerm
->u
.pAndInfo
->wc
.a
[N
];
515 ** Subterms pOne and pTwo are contained within WHERE clause pWC. The
516 ** two subterms are in disjunction - they are OR-ed together.
518 ** If these two terms are both of the form: "A op B" with the same
519 ** A and B values but different operators and if the operators are
520 ** compatible (if one is = and the other is <, for example) then
521 ** add a new virtual AND term to pWC that is the combination of the
526 ** x<y OR x=y --> x<=y
527 ** x=y OR x=y --> x=y
528 ** x<=y OR x<y --> x<=y
530 ** The following is NOT generated:
532 ** x<y OR x>y --> x!=y
534 static void whereCombineDisjuncts(
535 SrcList
*pSrc
, /* the FROM clause */
536 WhereClause
*pWC
, /* The complete WHERE clause */
537 WhereTerm
*pOne
, /* First disjunct */
538 WhereTerm
*pTwo
/* Second disjunct */
540 u16 eOp
= pOne
->eOperator
| pTwo
->eOperator
;
541 sqlite3
*db
; /* Database connection (for malloc) */
542 Expr
*pNew
; /* New virtual expression */
543 int op
; /* Operator for the combined expression */
544 int idxNew
; /* Index in pWC of the next virtual term */
546 if( (pOne
->wtFlags
| pTwo
->wtFlags
) & TERM_VNULL
) return;
547 if( (pOne
->eOperator
& (WO_EQ
|WO_LT
|WO_LE
|WO_GT
|WO_GE
))==0 ) return;
548 if( (pTwo
->eOperator
& (WO_EQ
|WO_LT
|WO_LE
|WO_GT
|WO_GE
))==0 ) return;
549 if( (eOp
& (WO_EQ
|WO_LT
|WO_LE
))!=eOp
550 && (eOp
& (WO_EQ
|WO_GT
|WO_GE
))!=eOp
) return;
551 assert( pOne
->pExpr
->pLeft
!=0 && pOne
->pExpr
->pRight
!=0 );
552 assert( pTwo
->pExpr
->pLeft
!=0 && pTwo
->pExpr
->pRight
!=0 );
553 if( sqlite3ExprCompare(0,pOne
->pExpr
->pLeft
, pTwo
->pExpr
->pLeft
, -1) ) return;
554 if( sqlite3ExprCompare(0,pOne
->pExpr
->pRight
, pTwo
->pExpr
->pRight
,-1) )return;
555 /* If we reach this point, it means the two subterms can be combined */
556 if( (eOp
& (eOp
-1))!=0 ){
557 if( eOp
& (WO_LT
|WO_LE
) ){
560 assert( eOp
& (WO_GT
|WO_GE
) );
564 db
= pWC
->pWInfo
->pParse
->db
;
565 pNew
= sqlite3ExprDup(db
, pOne
->pExpr
, 0);
566 if( pNew
==0 ) return;
567 for(op
=TK_EQ
; eOp
!=(WO_EQ
<<(op
-TK_EQ
)); op
++){ assert( op
<TK_GE
); }
569 idxNew
= whereClauseInsert(pWC
, pNew
, TERM_VIRTUAL
|TERM_DYNAMIC
);
570 exprAnalyze(pSrc
, pWC
, idxNew
);
573 #if !defined(SQLITE_OMIT_OR_OPTIMIZATION) && !defined(SQLITE_OMIT_SUBQUERY)
575 ** Analyze a term that consists of two or more OR-connected
578 ** ... WHERE (a=5) AND (b=7 OR c=9 OR d=13) AND (d=13)
579 ** ^^^^^^^^^^^^^^^^^^^^
581 ** This routine analyzes terms such as the middle term in the above example.
582 ** A WhereOrTerm object is computed and attached to the term under
583 ** analysis, regardless of the outcome of the analysis. Hence:
585 ** WhereTerm.wtFlags |= TERM_ORINFO
586 ** WhereTerm.u.pOrInfo = a dynamically allocated WhereOrTerm object
588 ** The term being analyzed must have two or more of OR-connected subterms.
589 ** A single subterm might be a set of AND-connected sub-subterms.
590 ** Examples of terms under analysis:
592 ** (A) t1.x=t2.y OR t1.x=t2.z OR t1.y=15 OR t1.z=t3.a+5
593 ** (B) x=expr1 OR expr2=x OR x=expr3
594 ** (C) t1.x=t2.y OR (t1.x=t2.z AND t1.y=15)
595 ** (D) x=expr1 OR (y>11 AND y<22 AND z LIKE '*hello*')
596 ** (E) (p.a=1 AND q.b=2 AND r.c=3) OR (p.x=4 AND q.y=5 AND r.z=6)
597 ** (F) x>A OR (x=A AND y>=B)
601 ** If all subterms are of the form T.C=expr for some single column of C and
602 ** a single table T (as shown in example B above) then create a new virtual
603 ** term that is an equivalent IN expression. In other words, if the term
604 ** being analyzed is:
606 ** x = expr1 OR expr2 = x OR x = expr3
608 ** then create a new virtual term like this:
610 ** x IN (expr1,expr2,expr3)
614 ** If there are exactly two disjuncts and one side has x>A and the other side
615 ** has x=A (for the same x and A) then add a new virtual conjunct term to the
616 ** WHERE clause of the form "x>=A". Example:
618 ** x>A OR (x=A AND y>B) adds: x>=A
620 ** The added conjunct can sometimes be helpful in query planning.
624 ** If all subterms are indexable by a single table T, then set
626 ** WhereTerm.eOperator = WO_OR
627 ** WhereTerm.u.pOrInfo->indexable |= the cursor number for table T
629 ** A subterm is "indexable" if it is of the form
630 ** "T.C <op> <expr>" where C is any column of table T and
631 ** <op> is one of "=", "<", "<=", ">", ">=", "IS NULL", or "IN".
632 ** A subterm is also indexable if it is an AND of two or more
633 ** subsubterms at least one of which is indexable. Indexable AND
634 ** subterms have their eOperator set to WO_AND and they have
635 ** u.pAndInfo set to a dynamically allocated WhereAndTerm object.
637 ** From another point of view, "indexable" means that the subterm could
638 ** potentially be used with an index if an appropriate index exists.
639 ** This analysis does not consider whether or not the index exists; that
640 ** is decided elsewhere. This analysis only looks at whether subterms
641 ** appropriate for indexing exist.
643 ** All examples A through E above satisfy case 3. But if a term
644 ** also satisfies case 1 (such as B) we know that the optimizer will
645 ** always prefer case 1, so in that case we pretend that case 3 is not
648 ** It might be the case that multiple tables are indexable. For example,
649 ** (E) above is indexable on tables P, Q, and R.
651 ** Terms that satisfy case 3 are candidates for lookup by using
652 ** separate indices to find rowids for each subterm and composing
653 ** the union of all rowids using a RowSet object. This is similar
654 ** to "bitmap indices" in other database engines.
658 ** If none of cases 1, 2, or 3 apply, then leave the eOperator set to
659 ** zero. This term is not useful for search.
661 static void exprAnalyzeOrTerm(
662 SrcList
*pSrc
, /* the FROM clause */
663 WhereClause
*pWC
, /* the complete WHERE clause */
664 int idxTerm
/* Index of the OR-term to be analyzed */
666 WhereInfo
*pWInfo
= pWC
->pWInfo
; /* WHERE clause processing context */
667 Parse
*pParse
= pWInfo
->pParse
; /* Parser context */
668 sqlite3
*db
= pParse
->db
; /* Database connection */
669 WhereTerm
*pTerm
= &pWC
->a
[idxTerm
]; /* The term to be analyzed */
670 Expr
*pExpr
= pTerm
->pExpr
; /* The expression of the term */
671 int i
; /* Loop counters */
672 WhereClause
*pOrWc
; /* Breakup of pTerm into subterms */
673 WhereTerm
*pOrTerm
; /* A Sub-term within the pOrWc */
674 WhereOrInfo
*pOrInfo
; /* Additional information associated with pTerm */
675 Bitmask chngToIN
; /* Tables that might satisfy case 1 */
676 Bitmask indexable
; /* Tables that are indexable, satisfying case 2 */
679 ** Break the OR clause into its separate subterms. The subterms are
680 ** stored in a WhereClause structure containing within the WhereOrInfo
681 ** object that is attached to the original OR clause term.
683 assert( (pTerm
->wtFlags
& (TERM_DYNAMIC
|TERM_ORINFO
|TERM_ANDINFO
))==0 );
684 assert( pExpr
->op
==TK_OR
);
685 pTerm
->u
.pOrInfo
= pOrInfo
= sqlite3DbMallocZero(db
, sizeof(*pOrInfo
));
686 if( pOrInfo
==0 ) return;
687 pTerm
->wtFlags
|= TERM_ORINFO
;
688 pOrWc
= &pOrInfo
->wc
;
689 memset(pOrWc
->aStatic
, 0, sizeof(pOrWc
->aStatic
));
690 sqlite3WhereClauseInit(pOrWc
, pWInfo
);
691 sqlite3WhereSplit(pOrWc
, pExpr
, TK_OR
);
692 sqlite3WhereExprAnalyze(pSrc
, pOrWc
);
693 if( db
->mallocFailed
) return;
694 assert( pOrWc
->nTerm
>=2 );
697 ** Compute the set of tables that might satisfy cases 1 or 3.
699 indexable
= ~(Bitmask
)0;
700 chngToIN
= ~(Bitmask
)0;
701 for(i
=pOrWc
->nTerm
-1, pOrTerm
=pOrWc
->a
; i
>=0 && indexable
; i
--, pOrTerm
++){
702 if( (pOrTerm
->eOperator
& WO_SINGLE
)==0 ){
703 WhereAndInfo
*pAndInfo
;
704 assert( (pOrTerm
->wtFlags
& (TERM_ANDINFO
|TERM_ORINFO
))==0 );
706 pAndInfo
= sqlite3DbMallocRawNN(db
, sizeof(*pAndInfo
));
712 pOrTerm
->u
.pAndInfo
= pAndInfo
;
713 pOrTerm
->wtFlags
|= TERM_ANDINFO
;
714 pOrTerm
->eOperator
= WO_AND
;
715 pOrTerm
->leftCursor
= -1;
716 pAndWC
= &pAndInfo
->wc
;
717 memset(pAndWC
->aStatic
, 0, sizeof(pAndWC
->aStatic
));
718 sqlite3WhereClauseInit(pAndWC
, pWC
->pWInfo
);
719 sqlite3WhereSplit(pAndWC
, pOrTerm
->pExpr
, TK_AND
);
720 sqlite3WhereExprAnalyze(pSrc
, pAndWC
);
721 pAndWC
->pOuter
= pWC
;
722 if( !db
->mallocFailed
){
723 for(j
=0, pAndTerm
=pAndWC
->a
; j
<pAndWC
->nTerm
; j
++, pAndTerm
++){
724 assert( pAndTerm
->pExpr
);
725 if( allowedOp(pAndTerm
->pExpr
->op
)
726 || pAndTerm
->eOperator
==WO_AUX
728 b
|= sqlite3WhereGetMask(&pWInfo
->sMaskSet
, pAndTerm
->leftCursor
);
734 }else if( pOrTerm
->wtFlags
& TERM_COPIED
){
735 /* Skip this term for now. We revisit it when we process the
736 ** corresponding TERM_VIRTUAL term */
739 b
= sqlite3WhereGetMask(&pWInfo
->sMaskSet
, pOrTerm
->leftCursor
);
740 if( pOrTerm
->wtFlags
& TERM_VIRTUAL
){
741 WhereTerm
*pOther
= &pOrWc
->a
[pOrTerm
->iParent
];
742 b
|= sqlite3WhereGetMask(&pWInfo
->sMaskSet
, pOther
->leftCursor
);
745 if( (pOrTerm
->eOperator
& WO_EQ
)==0 ){
754 ** Record the set of tables that satisfy case 3. The set might be
757 pOrInfo
->indexable
= indexable
;
758 pTerm
->eOperator
= WO_OR
;
759 pTerm
->leftCursor
= -1;
764 /* For a two-way OR, attempt to implementation case 2.
766 if( indexable
&& pOrWc
->nTerm
==2 ){
769 while( (pOne
= whereNthSubterm(&pOrWc
->a
[0],iOne
++))!=0 ){
772 while( (pTwo
= whereNthSubterm(&pOrWc
->a
[1],iTwo
++))!=0 ){
773 whereCombineDisjuncts(pSrc
, pWC
, pOne
, pTwo
);
779 ** chngToIN holds a set of tables that *might* satisfy case 1. But
780 ** we have to do some additional checking to see if case 1 really
783 ** chngToIN will hold either 0, 1, or 2 bits. The 0-bit case means
784 ** that there is no possibility of transforming the OR clause into an
785 ** IN operator because one or more terms in the OR clause contain
786 ** something other than == on a column in the single table. The 1-bit
787 ** case means that every term of the OR clause is of the form
788 ** "table.column=expr" for some single table. The one bit that is set
789 ** will correspond to the common table. We still need to check to make
790 ** sure the same column is used on all terms. The 2-bit case is when
791 ** the all terms are of the form "table1.column=table2.column". It
792 ** might be possible to form an IN operator with either table1.column
793 ** or table2.column as the LHS if either is common to every term of
796 ** Note that terms of the form "table.column1=table.column2" (the
797 ** same table on both sizes of the ==) cannot be optimized.
800 int okToChngToIN
= 0; /* True if the conversion to IN is valid */
801 int iColumn
= -1; /* Column index on lhs of IN operator */
802 int iCursor
= -1; /* Table cursor common to all terms */
803 int j
= 0; /* Loop counter */
805 /* Search for a table and column that appears on one side or the
806 ** other of the == operator in every subterm. That table and column
807 ** will be recorded in iCursor and iColumn. There might not be any
808 ** such table and column. Set okToChngToIN if an appropriate table
809 ** and column is found but leave okToChngToIN false if not found.
811 for(j
=0; j
<2 && !okToChngToIN
; j
++){
814 for(i
=pOrWc
->nTerm
-1; i
>=0; i
--, pOrTerm
++){
815 assert( pOrTerm
->eOperator
& WO_EQ
);
816 pOrTerm
->wtFlags
&= ~TERM_OK
;
817 if( pOrTerm
->leftCursor
==iCursor
){
818 /* This is the 2-bit case and we are on the second iteration and
819 ** current term is from the first iteration. So skip this term. */
823 if( (chngToIN
& sqlite3WhereGetMask(&pWInfo
->sMaskSet
,
824 pOrTerm
->leftCursor
))==0 ){
825 /* This term must be of the form t1.a==t2.b where t2 is in the
826 ** chngToIN set but t1 is not. This term will be either preceded
827 ** or followed by an inverted copy (t2.b==t1.a). Skip this term
828 ** and use its inversion. */
829 testcase( pOrTerm
->wtFlags
& TERM_COPIED
);
830 testcase( pOrTerm
->wtFlags
& TERM_VIRTUAL
);
831 assert( pOrTerm
->wtFlags
& (TERM_COPIED
|TERM_VIRTUAL
) );
834 assert( (pOrTerm
->eOperator
& (WO_OR
|WO_AND
))==0 );
835 iColumn
= pOrTerm
->u
.x
.leftColumn
;
836 iCursor
= pOrTerm
->leftCursor
;
837 pLeft
= pOrTerm
->pExpr
->pLeft
;
841 /* No candidate table+column was found. This can only occur
842 ** on the second iteration */
844 assert( IsPowerOfTwo(chngToIN
) );
845 assert( chngToIN
==sqlite3WhereGetMask(&pWInfo
->sMaskSet
, iCursor
) );
850 /* We have found a candidate table and column. Check to see if that
851 ** table and column is common to every term in the OR clause */
853 for(; i
>=0 && okToChngToIN
; i
--, pOrTerm
++){
854 assert( pOrTerm
->eOperator
& WO_EQ
);
855 assert( (pOrTerm
->eOperator
& (WO_OR
|WO_AND
))==0 );
856 if( pOrTerm
->leftCursor
!=iCursor
){
857 pOrTerm
->wtFlags
&= ~TERM_OK
;
858 }else if( pOrTerm
->u
.x
.leftColumn
!=iColumn
|| (iColumn
==XN_EXPR
859 && sqlite3ExprCompare(pParse
, pOrTerm
->pExpr
->pLeft
, pLeft
, -1)
863 int affLeft
, affRight
;
864 /* If the right-hand side is also a column, then the affinities
865 ** of both right and left sides must be such that no type
866 ** conversions are required on the right. (Ticket #2249)
868 affRight
= sqlite3ExprAffinity(pOrTerm
->pExpr
->pRight
);
869 affLeft
= sqlite3ExprAffinity(pOrTerm
->pExpr
->pLeft
);
870 if( affRight
!=0 && affRight
!=affLeft
){
873 pOrTerm
->wtFlags
|= TERM_OK
;
879 /* At this point, okToChngToIN is true if original pTerm satisfies
880 ** case 1. In that case, construct a new virtual term that is
881 ** pTerm converted into an IN operator.
884 Expr
*pDup
; /* A transient duplicate expression */
885 ExprList
*pList
= 0; /* The RHS of the IN operator */
886 Expr
*pLeft
= 0; /* The LHS of the IN operator */
887 Expr
*pNew
; /* The complete IN operator */
889 for(i
=pOrWc
->nTerm
-1, pOrTerm
=pOrWc
->a
; i
>=0; i
--, pOrTerm
++){
890 if( (pOrTerm
->wtFlags
& TERM_OK
)==0 ) continue;
891 assert( pOrTerm
->eOperator
& WO_EQ
);
892 assert( (pOrTerm
->eOperator
& (WO_OR
|WO_AND
))==0 );
893 assert( pOrTerm
->leftCursor
==iCursor
);
894 assert( pOrTerm
->u
.x
.leftColumn
==iColumn
);
895 pDup
= sqlite3ExprDup(db
, pOrTerm
->pExpr
->pRight
, 0);
896 pList
= sqlite3ExprListAppend(pWInfo
->pParse
, pList
, pDup
);
897 pLeft
= pOrTerm
->pExpr
->pLeft
;
900 pDup
= sqlite3ExprDup(db
, pLeft
, 0);
901 pNew
= sqlite3PExpr(pParse
, TK_IN
, pDup
, 0);
904 transferJoinMarkings(pNew
, pExpr
);
905 assert( ExprUseXList(pNew
) );
906 pNew
->x
.pList
= pList
;
907 idxNew
= whereClauseInsert(pWC
, pNew
, TERM_VIRTUAL
|TERM_DYNAMIC
);
908 testcase( idxNew
==0 );
909 exprAnalyze(pSrc
, pWC
, idxNew
);
910 /* pTerm = &pWC->a[idxTerm]; // would be needed if pTerm where reused */
911 markTermAsChild(pWC
, idxNew
, idxTerm
);
913 sqlite3ExprListDelete(db
, pList
);
918 #endif /* !SQLITE_OMIT_OR_OPTIMIZATION && !SQLITE_OMIT_SUBQUERY */
921 ** We already know that pExpr is a binary operator where both operands are
922 ** column references. This routine checks to see if pExpr is an equivalence
924 ** 1. The SQLITE_Transitive optimization must be enabled
925 ** 2. Must be either an == or an IS operator
926 ** 3. Not originating in the ON clause of an OUTER JOIN
927 ** 4. The affinities of A and B must be compatible
928 ** 5a. Both operands use the same collating sequence OR
929 ** 5b. The overall collating sequence is BINARY
930 ** If this routine returns TRUE, that means that the RHS can be substituted
931 ** for the LHS anyplace else in the WHERE clause where the LHS column occurs.
932 ** This is an optimization. No harm comes from returning 0. But if 1 is
933 ** returned when it should not be, then incorrect answers might result.
935 static int termIsEquivalence(Parse
*pParse
, Expr
*pExpr
){
938 if( !OptimizationEnabled(pParse
->db
, SQLITE_Transitive
) ) return 0;
939 if( pExpr
->op
!=TK_EQ
&& pExpr
->op
!=TK_IS
) return 0;
940 if( ExprHasProperty(pExpr
, EP_OuterON
) ) return 0;
941 aff1
= sqlite3ExprAffinity(pExpr
->pLeft
);
942 aff2
= sqlite3ExprAffinity(pExpr
->pRight
);
944 && (!sqlite3IsNumericAffinity(aff1
) || !sqlite3IsNumericAffinity(aff2
))
948 pColl
= sqlite3ExprCompareCollSeq(pParse
, pExpr
);
949 if( sqlite3IsBinary(pColl
) ) return 1;
950 return sqlite3ExprCollSeqMatch(pParse
, pExpr
->pLeft
, pExpr
->pRight
);
954 ** Recursively walk the expressions of a SELECT statement and generate
955 ** a bitmask indicating which tables are used in that expression
958 static Bitmask
exprSelectUsage(WhereMaskSet
*pMaskSet
, Select
*pS
){
961 SrcList
*pSrc
= pS
->pSrc
;
962 mask
|= sqlite3WhereExprListUsage(pMaskSet
, pS
->pEList
);
963 mask
|= sqlite3WhereExprListUsage(pMaskSet
, pS
->pGroupBy
);
964 mask
|= sqlite3WhereExprListUsage(pMaskSet
, pS
->pOrderBy
);
965 mask
|= sqlite3WhereExprUsage(pMaskSet
, pS
->pWhere
);
966 mask
|= sqlite3WhereExprUsage(pMaskSet
, pS
->pHaving
);
967 if( ALWAYS(pSrc
!=0) ){
969 for(i
=0; i
<pSrc
->nSrc
; i
++){
970 if( pSrc
->a
[i
].fg
.isSubquery
){
971 mask
|= exprSelectUsage(pMaskSet
, pSrc
->a
[i
].u4
.pSubq
->pSelect
);
973 if( pSrc
->a
[i
].fg
.isUsing
==0 ){
974 mask
|= sqlite3WhereExprUsage(pMaskSet
, pSrc
->a
[i
].u3
.pOn
);
976 if( pSrc
->a
[i
].fg
.isTabFunc
){
977 mask
|= sqlite3WhereExprListUsage(pMaskSet
, pSrc
->a
[i
].u1
.pFuncArg
);
987 ** Expression pExpr is one operand of a comparison operator that might
988 ** be useful for indexing. This routine checks to see if pExpr appears
989 ** in any index. Return TRUE (1) if pExpr is an indexed term and return
990 ** FALSE (0) if not. If TRUE is returned, also set aiCurCol[0] to the cursor
991 ** number of the table that is indexed and aiCurCol[1] to the column number
992 ** of the column that is indexed, or XN_EXPR (-2) if an expression is being
995 ** If pExpr is a TK_COLUMN column reference, then this routine always returns
996 ** true even if that particular column is not indexed, because the column
997 ** might be added to an automatic index later.
999 static SQLITE_NOINLINE
int exprMightBeIndexed2(
1000 SrcList
*pFrom
, /* The FROM clause */
1001 int *aiCurCol
, /* Write the referenced table cursor and column here */
1002 Expr
*pExpr
, /* An operand of a comparison operator */
1003 int j
/* Start looking with the j-th pFrom entry */
1009 iCur
= pFrom
->a
[j
].iCursor
;
1010 for(pIdx
=pFrom
->a
[j
].pSTab
->pIndex
; pIdx
; pIdx
=pIdx
->pNext
){
1011 if( pIdx
->aColExpr
==0 ) continue;
1012 for(i
=0; i
<pIdx
->nKeyCol
; i
++){
1013 if( pIdx
->aiColumn
[i
]!=XN_EXPR
) continue;
1014 assert( pIdx
->bHasExpr
);
1015 if( sqlite3ExprCompareSkip(pExpr
,pIdx
->aColExpr
->a
[i
].pExpr
,iCur
)==0
1016 && !sqlite3ExprIsConstant(0,pIdx
->aColExpr
->a
[i
].pExpr
)
1019 aiCurCol
[1] = XN_EXPR
;
1024 }while( ++j
< pFrom
->nSrc
);
1027 static int exprMightBeIndexed(
1028 SrcList
*pFrom
, /* The FROM clause */
1029 int *aiCurCol
, /* Write the referenced table cursor & column here */
1030 Expr
*pExpr
, /* An operand of a comparison operator */
1031 int op
/* The specific comparison operator */
1035 /* If this expression is a vector to the left or right of a
1036 ** inequality constraint (>, <, >= or <=), perform the processing
1037 ** on the first element of the vector. */
1038 assert( TK_GT
+1==TK_LE
&& TK_GT
+2==TK_LT
&& TK_GT
+3==TK_GE
);
1039 assert( TK_IS
<TK_GE
&& TK_ISNULL
<TK_GE
&& TK_IN
<TK_GE
);
1040 assert( op
<=TK_GE
);
1041 if( pExpr
->op
==TK_VECTOR
&& (op
>=TK_GT
&& ALWAYS(op
<=TK_GE
)) ){
1042 assert( ExprUseXList(pExpr
) );
1043 pExpr
= pExpr
->x
.pList
->a
[0].pExpr
;
1046 if( pExpr
->op
==TK_COLUMN
){
1047 aiCurCol
[0] = pExpr
->iTable
;
1048 aiCurCol
[1] = pExpr
->iColumn
;
1052 for(i
=0; i
<pFrom
->nSrc
; i
++){
1054 for(pIdx
=pFrom
->a
[i
].pSTab
->pIndex
; pIdx
; pIdx
=pIdx
->pNext
){
1055 if( pIdx
->aColExpr
){
1056 return exprMightBeIndexed2(pFrom
,aiCurCol
,pExpr
,i
);
1065 ** The input to this routine is an WhereTerm structure with only the
1066 ** "pExpr" field filled in. The job of this routine is to analyze the
1067 ** subexpression and populate all the other fields of the WhereTerm
1070 ** If the expression is of the form "<expr> <op> X" it gets commuted
1071 ** to the standard form of "X <op> <expr>".
1073 ** If the expression is of the form "X <op> Y" where both X and Y are
1074 ** columns, then the original expression is unchanged and a new virtual
1075 ** term of the form "Y <op> X" is added to the WHERE clause and
1076 ** analyzed separately. The original term is marked with TERM_COPIED
1077 ** and the new term is marked with TERM_DYNAMIC (because it's pExpr
1078 ** needs to be freed with the WhereClause) and TERM_VIRTUAL (because it
1079 ** is a commuted copy of a prior term.) The original term has nChild=1
1080 ** and the copy has idxParent set to the index of the original term.
1082 static void exprAnalyze(
1083 SrcList
*pSrc
, /* the FROM clause */
1084 WhereClause
*pWC
, /* the WHERE clause */
1085 int idxTerm
/* Index of the term to be analyzed */
1087 WhereInfo
*pWInfo
= pWC
->pWInfo
; /* WHERE clause processing context */
1088 WhereTerm
*pTerm
; /* The term to be analyzed */
1089 WhereMaskSet
*pMaskSet
; /* Set of table index masks */
1090 Expr
*pExpr
; /* The expression to be analyzed */
1091 Bitmask prereqLeft
; /* Prerequisites of the pExpr->pLeft */
1092 Bitmask prereqAll
; /* Prerequisites of pExpr */
1093 Bitmask extraRight
= 0; /* Extra dependencies on LEFT JOIN */
1094 Expr
*pStr1
= 0; /* RHS of LIKE/GLOB operator */
1095 int isComplete
= 0; /* RHS of LIKE/GLOB ends with wildcard */
1096 int noCase
= 0; /* uppercase equivalent to lowercase */
1097 int op
; /* Top-level operator. pExpr->op */
1098 Parse
*pParse
= pWInfo
->pParse
; /* Parsing context */
1099 sqlite3
*db
= pParse
->db
; /* Database connection */
1100 unsigned char eOp2
= 0; /* op2 value for LIKE/REGEXP/GLOB */
1101 int nLeft
; /* Number of elements on left side vector */
1103 if( db
->mallocFailed
){
1106 assert( pWC
->nTerm
> idxTerm
);
1107 pTerm
= &pWC
->a
[idxTerm
];
1108 pMaskSet
= &pWInfo
->sMaskSet
;
1109 pExpr
= pTerm
->pExpr
;
1110 assert( pExpr
!=0 ); /* Because malloc() has not failed */
1111 assert( pExpr
->op
!=TK_AS
&& pExpr
->op
!=TK_COLLATE
);
1112 pMaskSet
->bVarSelect
= 0;
1113 prereqLeft
= sqlite3WhereExprUsage(pMaskSet
, pExpr
->pLeft
);
1116 assert( pExpr
->pRight
==0 );
1117 if( sqlite3ExprCheckIN(pParse
, pExpr
) ) return;
1118 if( ExprUseXSelect(pExpr
) ){
1119 pTerm
->prereqRight
= exprSelectUsage(pMaskSet
, pExpr
->x
.pSelect
);
1121 pTerm
->prereqRight
= sqlite3WhereExprListUsage(pMaskSet
, pExpr
->x
.pList
);
1123 prereqAll
= prereqLeft
| pTerm
->prereqRight
;
1125 pTerm
->prereqRight
= sqlite3WhereExprUsage(pMaskSet
, pExpr
->pRight
);
1127 || ExprHasProperty(pExpr
, EP_xIsSelect
|EP_IfNullRow
)
1128 || pExpr
->x
.pList
!=0
1130 prereqAll
= sqlite3WhereExprUsageNN(pMaskSet
, pExpr
);
1132 prereqAll
= prereqLeft
| pTerm
->prereqRight
;
1135 if( pMaskSet
->bVarSelect
) pTerm
->wtFlags
|= TERM_VARSELECT
;
1138 if( prereqAll
!=sqlite3WhereExprUsageNN(pMaskSet
, pExpr
) ){
1139 printf("\n*** Incorrect prereqAll computed for:\n");
1140 sqlite3TreeViewExpr(0,pExpr
,0);
1145 if( ExprHasProperty(pExpr
, EP_OuterON
|EP_InnerON
) ){
1146 Bitmask x
= sqlite3WhereGetMask(pMaskSet
, pExpr
->w
.iJoin
);
1147 if( ExprHasProperty(pExpr
, EP_OuterON
) ){
1149 extraRight
= x
-1; /* ON clause terms may not be used with an index
1150 ** on left table of a LEFT JOIN. Ticket #3015 */
1151 if( (prereqAll
>>1)>=x
){
1152 sqlite3ErrorMsg(pParse
, "ON clause references tables to its right");
1155 }else if( (prereqAll
>>1)>=x
){
1156 /* The ON clause of an INNER JOIN references a table to its right.
1157 ** Most other SQL database engines raise an error. But SQLite versions
1158 ** 3.0 through 3.38 just put the ON clause constraint into the WHERE
1159 ** clause and carried on. Beginning with 3.39, raise an error only
1160 ** if there is a RIGHT or FULL JOIN in the query. This makes SQLite
1161 ** more like other systems, and also preserves legacy. */
1162 if( ALWAYS(pSrc
->nSrc
>0) && (pSrc
->a
[0].fg
.jointype
& JT_LTORJ
)!=0 ){
1163 sqlite3ErrorMsg(pParse
, "ON clause references tables to its right");
1166 ExprClearProperty(pExpr
, EP_InnerON
);
1169 pTerm
->prereqAll
= prereqAll
;
1170 pTerm
->leftCursor
= -1;
1171 pTerm
->iParent
= -1;
1172 pTerm
->eOperator
= 0;
1173 if( allowedOp(op
) ){
1175 Expr
*pLeft
= sqlite3ExprSkipCollate(pExpr
->pLeft
);
1176 Expr
*pRight
= sqlite3ExprSkipCollate(pExpr
->pRight
);
1177 u16 opMask
= (pTerm
->prereqRight
& prereqLeft
)==0 ? WO_ALL
: WO_EQUIV
;
1179 if( pTerm
->u
.x
.iField
>0 ){
1180 assert( op
==TK_IN
);
1181 assert( pLeft
->op
==TK_VECTOR
);
1182 assert( ExprUseXList(pLeft
) );
1183 pLeft
= pLeft
->x
.pList
->a
[pTerm
->u
.x
.iField
-1].pExpr
;
1186 if( exprMightBeIndexed(pSrc
, aiCurCol
, pLeft
, op
) ){
1187 pTerm
->leftCursor
= aiCurCol
[0];
1188 assert( (pTerm
->eOperator
& (WO_OR
|WO_AND
))==0 );
1189 pTerm
->u
.x
.leftColumn
= aiCurCol
[1];
1190 pTerm
->eOperator
= operatorMask(op
) & opMask
;
1192 if( op
==TK_IS
) pTerm
->wtFlags
|= TERM_IS
;
1194 && exprMightBeIndexed(pSrc
, aiCurCol
, pRight
, op
)
1195 && !ExprHasProperty(pRight
, EP_FixedCol
)
1199 u16 eExtraOp
= 0; /* Extra bits for pNew->eOperator */
1200 assert( pTerm
->u
.x
.iField
==0 );
1201 if( pTerm
->leftCursor
>=0 ){
1203 pDup
= sqlite3ExprDup(db
, pExpr
, 0);
1204 if( db
->mallocFailed
){
1205 sqlite3ExprDelete(db
, pDup
);
1208 idxNew
= whereClauseInsert(pWC
, pDup
, TERM_VIRTUAL
|TERM_DYNAMIC
);
1209 if( idxNew
==0 ) return;
1210 pNew
= &pWC
->a
[idxNew
];
1211 markTermAsChild(pWC
, idxNew
, idxTerm
);
1212 if( op
==TK_IS
) pNew
->wtFlags
|= TERM_IS
;
1213 pTerm
= &pWC
->a
[idxTerm
];
1214 pTerm
->wtFlags
|= TERM_COPIED
;
1216 if( termIsEquivalence(pParse
, pDup
) ){
1217 pTerm
->eOperator
|= WO_EQUIV
;
1218 eExtraOp
= WO_EQUIV
;
1224 pNew
->wtFlags
|= exprCommute(pParse
, pDup
);
1225 pNew
->leftCursor
= aiCurCol
[0];
1226 assert( (pTerm
->eOperator
& (WO_OR
|WO_AND
))==0 );
1227 pNew
->u
.x
.leftColumn
= aiCurCol
[1];
1228 testcase( (prereqLeft
| extraRight
) != prereqLeft
);
1229 pNew
->prereqRight
= prereqLeft
| extraRight
;
1230 pNew
->prereqAll
= prereqAll
;
1231 pNew
->eOperator
= (operatorMask(pDup
->op
) + eExtraOp
) & opMask
;
1234 && !ExprHasProperty(pExpr
,EP_OuterON
)
1235 && 0==sqlite3ExprCanBeNull(pLeft
)
1237 assert( !ExprHasProperty(pExpr
, EP_IntValue
) );
1238 pExpr
->op
= TK_TRUEFALSE
; /* See tag-20230504-1 */
1239 pExpr
->u
.zToken
= "false";
1240 ExprSetProperty(pExpr
, EP_IsFalse
);
1241 pTerm
->prereqAll
= 0;
1242 pTerm
->eOperator
= 0;
1246 #ifndef SQLITE_OMIT_BETWEEN_OPTIMIZATION
1247 /* If a term is the BETWEEN operator, create two new virtual terms
1248 ** that define the range that the BETWEEN implements. For example:
1250 ** a BETWEEN b AND c
1252 ** is converted into:
1254 ** (a BETWEEN b AND c) AND (a>=b) AND (a<=c)
1256 ** The two new terms are added onto the end of the WhereClause object.
1257 ** The new terms are "dynamic" and are children of the original BETWEEN
1258 ** term. That means that if the BETWEEN term is coded, the children are
1259 ** skipped. Or, if the children are satisfied by an index, the original
1260 ** BETWEEN term is skipped.
1262 else if( pExpr
->op
==TK_BETWEEN
&& pWC
->op
==TK_AND
){
1265 static const u8 ops
[] = {TK_GE
, TK_LE
};
1266 assert( ExprUseXList(pExpr
) );
1267 pList
= pExpr
->x
.pList
;
1269 assert( pList
->nExpr
==2 );
1273 pNewExpr
= sqlite3PExpr(pParse
, ops
[i
],
1274 sqlite3ExprDup(db
, pExpr
->pLeft
, 0),
1275 sqlite3ExprDup(db
, pList
->a
[i
].pExpr
, 0));
1276 transferJoinMarkings(pNewExpr
, pExpr
);
1277 idxNew
= whereClauseInsert(pWC
, pNewExpr
, TERM_VIRTUAL
|TERM_DYNAMIC
);
1278 testcase( idxNew
==0 );
1279 exprAnalyze(pSrc
, pWC
, idxNew
);
1280 pTerm
= &pWC
->a
[idxTerm
];
1281 markTermAsChild(pWC
, idxNew
, idxTerm
);
1284 #endif /* SQLITE_OMIT_BETWEEN_OPTIMIZATION */
1286 #if !defined(SQLITE_OMIT_OR_OPTIMIZATION) && !defined(SQLITE_OMIT_SUBQUERY)
1287 /* Analyze a term that is composed of two or more subterms connected by
1290 else if( pExpr
->op
==TK_OR
){
1291 assert( pWC
->op
==TK_AND
);
1292 exprAnalyzeOrTerm(pSrc
, pWC
, idxTerm
);
1293 pTerm
= &pWC
->a
[idxTerm
];
1295 #endif /* SQLITE_OMIT_OR_OPTIMIZATION */
1296 /* The form "x IS NOT NULL" can sometimes be evaluated more efficiently
1297 ** as "x>NULL" if x is not an INTEGER PRIMARY KEY. So construct a
1298 ** virtual term of that form.
1300 ** The virtual term must be tagged with TERM_VNULL.
1302 else if( pExpr
->op
==TK_NOTNULL
){
1303 if( pExpr
->pLeft
->op
==TK_COLUMN
1304 && pExpr
->pLeft
->iColumn
>=0
1305 && !ExprHasProperty(pExpr
, EP_OuterON
)
1308 Expr
*pLeft
= pExpr
->pLeft
;
1310 WhereTerm
*pNewTerm
;
1312 pNewExpr
= sqlite3PExpr(pParse
, TK_GT
,
1313 sqlite3ExprDup(db
, pLeft
, 0),
1314 sqlite3ExprAlloc(db
, TK_NULL
, 0, 0));
1316 idxNew
= whereClauseInsert(pWC
, pNewExpr
,
1317 TERM_VIRTUAL
|TERM_DYNAMIC
|TERM_VNULL
);
1319 pNewTerm
= &pWC
->a
[idxNew
];
1320 pNewTerm
->prereqRight
= 0;
1321 pNewTerm
->leftCursor
= pLeft
->iTable
;
1322 pNewTerm
->u
.x
.leftColumn
= pLeft
->iColumn
;
1323 pNewTerm
->eOperator
= WO_GT
;
1324 markTermAsChild(pWC
, idxNew
, idxTerm
);
1325 pTerm
= &pWC
->a
[idxTerm
];
1326 pTerm
->wtFlags
|= TERM_COPIED
;
1327 pNewTerm
->prereqAll
= pTerm
->prereqAll
;
1333 #ifndef SQLITE_OMIT_LIKE_OPTIMIZATION
1334 /* Add constraints to reduce the search space on a LIKE or GLOB
1337 ** A like pattern of the form "x LIKE 'aBc%'" is changed into constraints
1339 ** x>='ABC' AND x<'abd' AND x LIKE 'aBc%'
1341 ** The last character of the prefix "abc" is incremented to form the
1342 ** termination condition "abd". If case is not significant (the default
1343 ** for LIKE) then the lower-bound is made all uppercase and the upper-
1344 ** bound is made all lowercase so that the bounds also work when comparing
1347 else if( pExpr
->op
==TK_FUNCTION
1349 && isLikeOrGlob(pParse
, pExpr
, &pStr1
, &isComplete
, &noCase
)
1351 Expr
*pLeft
; /* LHS of LIKE/GLOB operator */
1352 Expr
*pStr2
; /* Copy of pStr1 - RHS of LIKE/GLOB operator */
1357 const char *zCollSeqName
; /* Name of collating sequence */
1358 const u16 wtFlags
= TERM_LIKEOPT
| TERM_VIRTUAL
| TERM_DYNAMIC
;
1360 assert( ExprUseXList(pExpr
) );
1361 pLeft
= pExpr
->x
.pList
->a
[1].pExpr
;
1362 pStr2
= sqlite3ExprDup(db
, pStr1
, 0);
1363 assert( pStr1
==0 || !ExprHasProperty(pStr1
, EP_IntValue
) );
1364 assert( pStr2
==0 || !ExprHasProperty(pStr2
, EP_IntValue
) );
1367 /* Convert the lower bound to upper-case and the upper bound to
1368 ** lower-case (upper-case is less than lower-case in ASCII) so that
1369 ** the range constraints also work for BLOBs
1371 if( noCase
&& !pParse
->db
->mallocFailed
){
1374 pTerm
->wtFlags
|= TERM_LIKE
;
1375 for(i
=0; (c
= pStr1
->u
.zToken
[i
])!=0; i
++){
1376 pStr1
->u
.zToken
[i
] = sqlite3Toupper(c
);
1377 pStr2
->u
.zToken
[i
] = sqlite3Tolower(c
);
1381 if( !db
->mallocFailed
){
1382 u8 c
, *pC
; /* Last character before the first wildcard */
1383 pC
= (u8
*)&pStr2
->u
.zToken
[sqlite3Strlen30(pStr2
->u
.zToken
)-1];
1386 /* The point is to increment the last character before the first
1387 ** wildcard. But if we increment '@', that will push it into the
1388 ** alphabetic range where case conversions will mess up the
1389 ** inequality. To avoid this, make sure to also run the full
1390 ** LIKE on all candidate expressions by clearing the isComplete flag
1392 if( c
=='A'-1 ) isComplete
= 0;
1393 c
= sqlite3UpperToLower
[c
];
1397 zCollSeqName
= noCase
? "NOCASE" : sqlite3StrBINARY
;
1398 pNewExpr1
= sqlite3ExprDup(db
, pLeft
, 0);
1399 pNewExpr1
= sqlite3PExpr(pParse
, TK_GE
,
1400 sqlite3ExprAddCollateString(pParse
,pNewExpr1
,zCollSeqName
),
1402 transferJoinMarkings(pNewExpr1
, pExpr
);
1403 idxNew1
= whereClauseInsert(pWC
, pNewExpr1
, wtFlags
);
1404 testcase( idxNew1
==0 );
1405 pNewExpr2
= sqlite3ExprDup(db
, pLeft
, 0);
1406 pNewExpr2
= sqlite3PExpr(pParse
, TK_LT
,
1407 sqlite3ExprAddCollateString(pParse
,pNewExpr2
,zCollSeqName
),
1409 transferJoinMarkings(pNewExpr2
, pExpr
);
1410 idxNew2
= whereClauseInsert(pWC
, pNewExpr2
, wtFlags
);
1411 testcase( idxNew2
==0 );
1412 exprAnalyze(pSrc
, pWC
, idxNew1
);
1413 exprAnalyze(pSrc
, pWC
, idxNew2
);
1414 pTerm
= &pWC
->a
[idxTerm
];
1416 markTermAsChild(pWC
, idxNew1
, idxTerm
);
1417 markTermAsChild(pWC
, idxNew2
, idxTerm
);
1420 #endif /* SQLITE_OMIT_LIKE_OPTIMIZATION */
1422 /* If there is a vector == or IS term - e.g. "(a, b) == (?, ?)" - create
1423 ** new terms for each component comparison - "a = ?" and "b = ?". The
1424 ** new terms completely replace the original vector comparison, which is
1427 ** This is only required if at least one side of the comparison operation
1428 ** is not a sub-select.
1432 if( (pExpr
->op
==TK_EQ
|| pExpr
->op
==TK_IS
)
1433 && (nLeft
= sqlite3ExprVectorSize(pExpr
->pLeft
))>1
1434 && sqlite3ExprVectorSize(pExpr
->pRight
)==nLeft
1435 && ( (pExpr
->pLeft
->flags
& EP_xIsSelect
)==0
1436 || (pExpr
->pRight
->flags
& EP_xIsSelect
)==0)
1440 for(i
=0; i
<nLeft
; i
++){
1443 Expr
*pLeft
= sqlite3ExprForVectorField(pParse
, pExpr
->pLeft
, i
, nLeft
);
1444 Expr
*pRight
= sqlite3ExprForVectorField(pParse
, pExpr
->pRight
, i
, nLeft
);
1446 pNew
= sqlite3PExpr(pParse
, pExpr
->op
, pLeft
, pRight
);
1447 transferJoinMarkings(pNew
, pExpr
);
1448 idxNew
= whereClauseInsert(pWC
, pNew
, TERM_DYNAMIC
|TERM_SLICE
);
1449 exprAnalyze(pSrc
, pWC
, idxNew
);
1451 pTerm
= &pWC
->a
[idxTerm
];
1452 pTerm
->wtFlags
|= TERM_CODED
|TERM_VIRTUAL
; /* Disable the original */
1453 pTerm
->eOperator
= WO_ROWVAL
;
1456 /* If there is a vector IN term - e.g. "(a, b) IN (SELECT ...)" - create
1457 ** a virtual term for each vector component. The expression object
1458 ** used by each such virtual term is pExpr (the full vector IN(...)
1459 ** expression). The WhereTerm.u.x.iField variable identifies the index within
1460 ** the vector on the LHS that the virtual term represents.
1462 ** This only works if the RHS is a simple SELECT (not a compound) that does
1463 ** not use window functions.
1465 else if( pExpr
->op
==TK_IN
1466 && pTerm
->u
.x
.iField
==0
1467 && pExpr
->pLeft
->op
==TK_VECTOR
1468 && ALWAYS( ExprUseXSelect(pExpr
) )
1469 && (pExpr
->x
.pSelect
->pPrior
==0 || (pExpr
->x
.pSelect
->selFlags
& SF_Values
))
1470 #ifndef SQLITE_OMIT_WINDOWFUNC
1471 && pExpr
->x
.pSelect
->pWin
==0
1476 for(i
=0; i
<sqlite3ExprVectorSize(pExpr
->pLeft
); i
++){
1478 idxNew
= whereClauseInsert(pWC
, pExpr
, TERM_VIRTUAL
|TERM_SLICE
);
1479 pWC
->a
[idxNew
].u
.x
.iField
= i
+1;
1480 exprAnalyze(pSrc
, pWC
, idxNew
);
1481 markTermAsChild(pWC
, idxNew
, idxTerm
);
1485 #ifndef SQLITE_OMIT_VIRTUALTABLE
1486 /* Add a WO_AUX auxiliary term to the constraint set if the
1487 ** current expression is of the form "column OP expr" where OP
1488 ** is an operator that gets passed into virtual tables but which is
1489 ** not normally optimized for ordinary tables. In other words, OP
1490 ** is one of MATCH, LIKE, GLOB, REGEXP, !=, IS, IS NOT, or NOT NULL.
1491 ** This information is used by the xBestIndex methods of
1492 ** virtual tables. The native query optimizer does not attempt
1493 ** to do anything with MATCH functions.
1495 else if( pWC
->op
==TK_AND
){
1496 Expr
*pRight
= 0, *pLeft
= 0;
1497 int res
= isAuxiliaryVtabOperator(db
, pExpr
, &eOp2
, &pLeft
, &pRight
);
1500 WhereTerm
*pNewTerm
;
1501 Bitmask prereqColumn
, prereqExpr
;
1503 prereqExpr
= sqlite3WhereExprUsage(pMaskSet
, pRight
);
1504 prereqColumn
= sqlite3WhereExprUsage(pMaskSet
, pLeft
);
1505 if( (prereqExpr
& prereqColumn
)==0 ){
1507 pNewExpr
= sqlite3PExpr(pParse
, TK_MATCH
,
1508 0, sqlite3ExprDup(db
, pRight
, 0));
1509 if( ExprHasProperty(pExpr
, EP_OuterON
) && pNewExpr
){
1510 ExprSetProperty(pNewExpr
, EP_OuterON
);
1511 pNewExpr
->w
.iJoin
= pExpr
->w
.iJoin
;
1513 idxNew
= whereClauseInsert(pWC
, pNewExpr
, TERM_VIRTUAL
|TERM_DYNAMIC
);
1514 testcase( idxNew
==0 );
1515 pNewTerm
= &pWC
->a
[idxNew
];
1516 pNewTerm
->prereqRight
= prereqExpr
;
1517 pNewTerm
->leftCursor
= pLeft
->iTable
;
1518 pNewTerm
->u
.x
.leftColumn
= pLeft
->iColumn
;
1519 pNewTerm
->eOperator
= WO_AUX
;
1520 pNewTerm
->eMatchOp
= eOp2
;
1521 markTermAsChild(pWC
, idxNew
, idxTerm
);
1522 pTerm
= &pWC
->a
[idxTerm
];
1523 pTerm
->wtFlags
|= TERM_COPIED
;
1524 pNewTerm
->prereqAll
= pTerm
->prereqAll
;
1526 SWAP(Expr
*, pLeft
, pRight
);
1529 #endif /* SQLITE_OMIT_VIRTUALTABLE */
1531 /* Prevent ON clause terms of a LEFT JOIN from being used to drive
1532 ** an index for tables to the left of the join.
1534 testcase( pTerm
!=&pWC
->a
[idxTerm
] );
1535 pTerm
= &pWC
->a
[idxTerm
];
1536 pTerm
->prereqRight
|= extraRight
;
1539 /***************************************************************************
1540 ** Routines with file scope above. Interface to the rest of the where.c
1541 ** subsystem follows.
1542 ***************************************************************************/
1545 ** This routine identifies subexpressions in the WHERE clause where
1546 ** each subexpression is separated by the AND operator or some other
1547 ** operator specified in the op parameter. The WhereClause structure
1548 ** is filled with pointers to subexpressions. For example:
1550 ** WHERE a=='hello' AND coalesce(b,11)<10 AND (c+12!=d OR c==22)
1551 ** \________/ \_______________/ \________________/
1552 ** slot[0] slot[1] slot[2]
1554 ** The original WHERE clause in pExpr is unaltered. All this routine
1555 ** does is make slot[] entries point to substructure within pExpr.
1557 ** In the previous sentence and in the diagram, "slot[]" refers to
1558 ** the WhereClause.a[] array. The slot[] array grows as needed to contain
1559 ** all terms of the WHERE clause.
1561 void sqlite3WhereSplit(WhereClause
*pWC
, Expr
*pExpr
, u8 op
){
1562 Expr
*pE2
= sqlite3ExprSkipCollateAndLikely(pExpr
);
1564 assert( pE2
!=0 || pExpr
==0 );
1565 if( pE2
==0 ) return;
1567 whereClauseInsert(pWC
, pExpr
, 0);
1569 sqlite3WhereSplit(pWC
, pE2
->pLeft
, op
);
1570 sqlite3WhereSplit(pWC
, pE2
->pRight
, op
);
1575 ** Add either a LIMIT (if eMatchOp==SQLITE_INDEX_CONSTRAINT_LIMIT) or
1576 ** OFFSET (if eMatchOp==SQLITE_INDEX_CONSTRAINT_OFFSET) term to the
1577 ** where-clause passed as the first argument. The value for the term
1578 ** is found in register iReg.
1580 ** In the common case where the value is a simple integer
1581 ** (example: "LIMIT 5 OFFSET 10") then the expression codes as a
1582 ** TK_INTEGER so that it will be available to sqlite3_vtab_rhs_value().
1583 ** If not, then it codes as a TK_REGISTER expression.
1585 static void whereAddLimitExpr(
1586 WhereClause
*pWC
, /* Add the constraint to this WHERE clause */
1587 int iReg
, /* Register that will hold value of the limit/offset */
1588 Expr
*pExpr
, /* Expression that defines the limit/offset */
1589 int iCsr
, /* Cursor to which the constraint applies */
1590 int eMatchOp
/* SQLITE_INDEX_CONSTRAINT_LIMIT or _OFFSET */
1592 Parse
*pParse
= pWC
->pWInfo
->pParse
;
1593 sqlite3
*db
= pParse
->db
;
1597 if( sqlite3ExprIsInteger(pExpr
, &iVal
, pParse
) && iVal
>=0 ){
1598 Expr
*pVal
= sqlite3Expr(db
, TK_INTEGER
, 0);
1599 if( pVal
==0 ) return;
1600 ExprSetProperty(pVal
, EP_IntValue
);
1601 pVal
->u
.iValue
= iVal
;
1602 pNew
= sqlite3PExpr(pParse
, TK_MATCH
, 0, pVal
);
1604 Expr
*pVal
= sqlite3Expr(db
, TK_REGISTER
, 0);
1605 if( pVal
==0 ) return;
1606 pVal
->iTable
= iReg
;
1607 pNew
= sqlite3PExpr(pParse
, TK_MATCH
, 0, pVal
);
1612 idx
= whereClauseInsert(pWC
, pNew
, TERM_DYNAMIC
|TERM_VIRTUAL
);
1613 pTerm
= &pWC
->a
[idx
];
1614 pTerm
->leftCursor
= iCsr
;
1615 pTerm
->eOperator
= WO_AUX
;
1616 pTerm
->eMatchOp
= eMatchOp
;
1621 ** Possibly add terms corresponding to the LIMIT and OFFSET clauses of the
1622 ** SELECT statement passed as the second argument. These terms are only
1625 ** 1. The SELECT statement has a LIMIT clause, and
1626 ** 2. The SELECT statement is not an aggregate or DISTINCT query, and
1627 ** 3. The SELECT statement has exactly one object in its from clause, and
1628 ** that object is a virtual table, and
1629 ** 4. There are no terms in the WHERE clause that will not be passed
1630 ** to the virtual table xBestIndex method.
1631 ** 5. The ORDER BY clause, if any, will be made available to the xBestIndex
1634 ** LIMIT and OFFSET terms are ignored by most of the planner code. They
1635 ** exist only so that they may be passed to the xBestIndex method of the
1636 ** single virtual table in the FROM clause of the SELECT.
1638 void SQLITE_NOINLINE
sqlite3WhereAddLimit(WhereClause
*pWC
, Select
*p
){
1639 assert( p
!=0 && p
->pLimit
!=0 ); /* 1 -- checked by caller */
1641 && (p
->selFlags
& (SF_Distinct
|SF_Aggregate
))==0 /* 2 */
1642 && (p
->pSrc
->nSrc
==1 && IsVirtual(p
->pSrc
->a
[0].pSTab
)) /* 3 */
1644 ExprList
*pOrderBy
= p
->pOrderBy
;
1645 int iCsr
= p
->pSrc
->a
[0].iCursor
;
1648 /* Check condition (4). Return early if it is not met. */
1649 for(ii
=0; ii
<pWC
->nTerm
; ii
++){
1650 if( pWC
->a
[ii
].wtFlags
& TERM_CODED
){
1651 /* This term is a vector operation that has been decomposed into
1652 ** other, subsequent terms. It can be ignored. See tag-20220128a */
1653 assert( pWC
->a
[ii
].wtFlags
& TERM_VIRTUAL
);
1654 assert( pWC
->a
[ii
].eOperator
==WO_ROWVAL
);
1657 if( pWC
->a
[ii
].nChild
){
1658 /* If this term has child terms, then they are also part of the
1659 ** pWC->a[] array. So this term can be ignored, as a LIMIT clause
1660 ** will only be added if each of the child terms passes the
1661 ** (leftCursor==iCsr) test below. */
1664 if( pWC
->a
[ii
].leftCursor
!=iCsr
) return;
1665 if( pWC
->a
[ii
].prereqRight
!=0 ) return;
1668 /* Check condition (5). Return early if it is not met. */
1670 for(ii
=0; ii
<pOrderBy
->nExpr
; ii
++){
1671 Expr
*pExpr
= pOrderBy
->a
[ii
].pExpr
;
1672 if( pExpr
->op
!=TK_COLUMN
) return;
1673 if( pExpr
->iTable
!=iCsr
) return;
1674 if( pOrderBy
->a
[ii
].fg
.sortFlags
& KEYINFO_ORDER_BIGNULL
) return;
1678 /* All conditions are met. Add the terms to the where-clause object. */
1679 assert( p
->pLimit
->op
==TK_LIMIT
);
1680 if( p
->iOffset
!=0 && (p
->selFlags
& SF_Compound
)==0 ){
1681 whereAddLimitExpr(pWC
, p
->iOffset
, p
->pLimit
->pRight
,
1682 iCsr
, SQLITE_INDEX_CONSTRAINT_OFFSET
);
1684 if( p
->iOffset
==0 || (p
->selFlags
& SF_Compound
)==0 ){
1685 whereAddLimitExpr(pWC
, p
->iLimit
, p
->pLimit
->pLeft
,
1686 iCsr
, SQLITE_INDEX_CONSTRAINT_LIMIT
);
1692 ** Initialize a preallocated WhereClause structure.
1694 void sqlite3WhereClauseInit(
1695 WhereClause
*pWC
, /* The WhereClause to be initialized */
1696 WhereInfo
*pWInfo
/* The WHERE processing context */
1698 pWC
->pWInfo
= pWInfo
;
1703 pWC
->nSlot
= ArraySize(pWC
->aStatic
);
1704 pWC
->a
= pWC
->aStatic
;
1708 ** Deallocate a WhereClause structure. The WhereClause structure
1709 ** itself is not freed. This routine is the inverse of
1710 ** sqlite3WhereClauseInit().
1712 void sqlite3WhereClauseClear(WhereClause
*pWC
){
1713 sqlite3
*db
= pWC
->pWInfo
->pParse
->db
;
1714 assert( pWC
->nTerm
>=pWC
->nBase
);
1716 WhereTerm
*a
= pWC
->a
;
1717 WhereTerm
*aLast
= &pWC
->a
[pWC
->nTerm
-1];
1720 /* Verify that every term past pWC->nBase is virtual */
1721 for(i
=pWC
->nBase
; i
<pWC
->nTerm
; i
++){
1722 assert( (pWC
->a
[i
].wtFlags
& TERM_VIRTUAL
)!=0 );
1726 assert( a
->eMatchOp
==0 || a
->eOperator
==WO_AUX
);
1727 if( a
->wtFlags
& TERM_DYNAMIC
){
1728 sqlite3ExprDelete(db
, a
->pExpr
);
1730 if( a
->wtFlags
& (TERM_ORINFO
|TERM_ANDINFO
) ){
1731 if( a
->wtFlags
& TERM_ORINFO
){
1732 assert( (a
->wtFlags
& TERM_ANDINFO
)==0 );
1733 whereOrInfoDelete(db
, a
->u
.pOrInfo
);
1735 assert( (a
->wtFlags
& TERM_ANDINFO
)!=0 );
1736 whereAndInfoDelete(db
, a
->u
.pAndInfo
);
1739 if( a
==aLast
) break;
1747 ** These routines walk (recursively) an expression tree and generate
1748 ** a bitmask indicating which tables are used in that expression
1751 ** sqlite3WhereExprUsage(MaskSet, Expr) ->
1753 ** Return a Bitmask of all tables referenced by Expr. Expr can be
1754 ** be NULL, in which case 0 is returned.
1756 ** sqlite3WhereExprUsageNN(MaskSet, Expr) ->
1758 ** Same as sqlite3WhereExprUsage() except that Expr must not be
1759 ** NULL. The "NN" suffix on the name stands for "Not Null".
1761 ** sqlite3WhereExprListUsage(MaskSet, ExprList) ->
1763 ** Return a Bitmask of all tables referenced by every expression
1764 ** in the expression list ExprList. ExprList can be NULL, in which
1765 ** case 0 is returned.
1767 ** sqlite3WhereExprUsageFull(MaskSet, ExprList) ->
1769 ** Internal use only. Called only by sqlite3WhereExprUsageNN() for
1770 ** complex expressions that require pushing register values onto
1771 ** the stack. Many calls to sqlite3WhereExprUsageNN() do not need
1772 ** the more complex analysis done by this routine. Hence, the
1773 ** computations done by this routine are broken out into a separate
1774 ** "no-inline" function to avoid the stack push overhead in the
1775 ** common case where it is not needed.
1777 static SQLITE_NOINLINE Bitmask
sqlite3WhereExprUsageFull(
1778 WhereMaskSet
*pMaskSet
,
1782 mask
= (p
->op
==TK_IF_NULL_ROW
) ? sqlite3WhereGetMask(pMaskSet
, p
->iTable
) : 0;
1783 if( p
->pLeft
) mask
|= sqlite3WhereExprUsageNN(pMaskSet
, p
->pLeft
);
1785 mask
|= sqlite3WhereExprUsageNN(pMaskSet
, p
->pRight
);
1786 assert( p
->x
.pList
==0 );
1787 }else if( ExprUseXSelect(p
) ){
1788 if( ExprHasProperty(p
, EP_VarSelect
) ) pMaskSet
->bVarSelect
= 1;
1789 mask
|= exprSelectUsage(pMaskSet
, p
->x
.pSelect
);
1790 }else if( p
->x
.pList
){
1791 mask
|= sqlite3WhereExprListUsage(pMaskSet
, p
->x
.pList
);
1793 #ifndef SQLITE_OMIT_WINDOWFUNC
1794 if( (p
->op
==TK_FUNCTION
|| p
->op
==TK_AGG_FUNCTION
) && ExprUseYWin(p
) ){
1795 assert( p
->y
.pWin
!=0 );
1796 mask
|= sqlite3WhereExprListUsage(pMaskSet
, p
->y
.pWin
->pPartition
);
1797 mask
|= sqlite3WhereExprListUsage(pMaskSet
, p
->y
.pWin
->pOrderBy
);
1798 mask
|= sqlite3WhereExprUsage(pMaskSet
, p
->y
.pWin
->pFilter
);
1803 Bitmask
sqlite3WhereExprUsageNN(WhereMaskSet
*pMaskSet
, Expr
*p
){
1804 if( p
->op
==TK_COLUMN
&& !ExprHasProperty(p
, EP_FixedCol
) ){
1805 return sqlite3WhereGetMask(pMaskSet
, p
->iTable
);
1806 }else if( ExprHasProperty(p
, EP_TokenOnly
|EP_Leaf
) ){
1807 assert( p
->op
!=TK_IF_NULL_ROW
);
1810 return sqlite3WhereExprUsageFull(pMaskSet
, p
);
1812 Bitmask
sqlite3WhereExprUsage(WhereMaskSet
*pMaskSet
, Expr
*p
){
1813 return p
? sqlite3WhereExprUsageNN(pMaskSet
,p
) : 0;
1815 Bitmask
sqlite3WhereExprListUsage(WhereMaskSet
*pMaskSet
, ExprList
*pList
){
1819 for(i
=0; i
<pList
->nExpr
; i
++){
1820 mask
|= sqlite3WhereExprUsage(pMaskSet
, pList
->a
[i
].pExpr
);
1828 ** Call exprAnalyze on all terms in a WHERE clause.
1830 ** Note that exprAnalyze() might add new virtual terms onto the
1831 ** end of the WHERE clause. We do not want to analyze these new
1832 ** virtual terms, so start analyzing at the end and work forward
1833 ** so that the added virtual terms are never processed.
1835 void sqlite3WhereExprAnalyze(
1836 SrcList
*pTabList
, /* the FROM clause */
1837 WhereClause
*pWC
/* the WHERE clause to be analyzed */
1840 for(i
=pWC
->nTerm
-1; i
>=0; i
--){
1841 exprAnalyze(pTabList
, pWC
, i
);
1846 ** For table-valued-functions, transform the function arguments into
1847 ** new WHERE clause terms.
1849 ** Each function argument translates into an equality constraint against
1850 ** a HIDDEN column in the table.
1852 void sqlite3WhereTabFuncArgs(
1853 Parse
*pParse
, /* Parsing context */
1854 SrcItem
*pItem
, /* The FROM clause term to process */
1855 WhereClause
*pWC
/* Xfer function arguments to here */
1862 if( pItem
->fg
.isTabFunc
==0 ) return;
1863 pTab
= pItem
->pSTab
;
1865 pArgs
= pItem
->u1
.pFuncArg
;
1866 if( pArgs
==0 ) return;
1867 for(j
=k
=0; j
<pArgs
->nExpr
; j
++){
1870 while( k
<pTab
->nCol
&& (pTab
->aCol
[k
].colFlags
& COLFLAG_HIDDEN
)==0 ){k
++;}
1871 if( k
>=pTab
->nCol
){
1872 sqlite3ErrorMsg(pParse
, "too many arguments on %s() - max %d",
1876 pColRef
= sqlite3ExprAlloc(pParse
->db
, TK_COLUMN
, 0, 0);
1877 if( pColRef
==0 ) return;
1878 pColRef
->iTable
= pItem
->iCursor
;
1879 pColRef
->iColumn
= k
++;
1880 assert( ExprUseYTab(pColRef
) );
1881 pColRef
->y
.pTab
= pTab
;
1882 pItem
->colUsed
|= sqlite3ExprColUsed(pColRef
);
1883 pRhs
= sqlite3PExpr(pParse
, TK_UPLUS
,
1884 sqlite3ExprDup(pParse
->db
, pArgs
->a
[j
].pExpr
, 0), 0);
1885 pTerm
= sqlite3PExpr(pParse
, TK_EQ
, pColRef
, pRhs
);
1886 if( pItem
->fg
.jointype
& (JT_LEFT
|JT_RIGHT
) ){
1887 testcase( pItem
->fg
.jointype
& JT_LEFT
); /* testtag-20230227a */
1888 testcase( pItem
->fg
.jointype
& JT_RIGHT
); /* testtag-20230227b */
1889 joinType
= EP_OuterON
;
1891 testcase( pItem
->fg
.jointype
& JT_LTORJ
); /* testtag-20230227c */
1892 joinType
= EP_InnerON
;
1894 sqlite3SetJoinExpr(pTerm
, pItem
->iCursor
, joinType
);
1895 whereClauseInsert(pWC
, pTerm
, TERM_DYNAMIC
);