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