1 : /*
2 : ** 2001 September 15
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. This module is reponsible for
14 : ** generating the code that loops through a table looking for applicable
15 : ** rows. Indices are selected and used to speed the search when doing
16 : ** so is applicable. Because this module is responsible for selecting
17 : ** indices, you might also think of this module as the "query optimizer".
18 : **
19 : ** $Id$
20 : */
21 : #include "sqliteInt.h"
22 :
23 : /*
24 : ** The number of bits in a Bitmask. "BMS" means "BitMask Size".
25 : */
26 : #define BMS (sizeof(Bitmask)*8)
27 :
28 : /*
29 : ** Trace output macros
30 : */
31 : #if defined(SQLITE_TEST) || defined(SQLITE_DEBUG)
32 : int sqlite3_where_trace = 0;
33 : # define WHERETRACE(X) if(sqlite3_where_trace) sqlite3DebugPrintf X
34 : #else
35 : # define WHERETRACE(X)
36 : #endif
37 :
38 : /* Forward reference
39 : */
40 : typedef struct WhereClause WhereClause;
41 : typedef struct ExprMaskSet ExprMaskSet;
42 :
43 : /*
44 : ** The query generator uses an array of instances of this structure to
45 : ** help it analyze the subexpressions of the WHERE clause. Each WHERE
46 : ** clause subexpression is separated from the others by an AND operator.
47 : **
48 : ** All WhereTerms are collected into a single WhereClause structure.
49 : ** The following identity holds:
50 : **
51 : ** WhereTerm.pWC->a[WhereTerm.idx] == WhereTerm
52 : **
53 : ** When a term is of the form:
54 : **
55 : ** X <op> <expr>
56 : **
57 : ** where X is a column name and <op> is one of certain operators,
58 : ** then WhereTerm.leftCursor and WhereTerm.leftColumn record the
59 : ** cursor number and column number for X. WhereTerm.operator records
60 : ** the <op> using a bitmask encoding defined by WO_xxx below. The
61 : ** use of a bitmask encoding for the operator allows us to search
62 : ** quickly for terms that match any of several different operators.
63 : **
64 : ** prereqRight and prereqAll record sets of cursor numbers,
65 : ** but they do so indirectly. A single ExprMaskSet structure translates
66 : ** cursor number into bits and the translated bit is stored in the prereq
67 : ** fields. The translation is used in order to maximize the number of
68 : ** bits that will fit in a Bitmask. The VDBE cursor numbers might be
69 : ** spread out over the non-negative integers. For example, the cursor
70 : ** numbers might be 3, 8, 9, 10, 20, 23, 41, and 45. The ExprMaskSet
71 : ** translates these sparse cursor numbers into consecutive integers
72 : ** beginning with 0 in order to make the best possible use of the available
73 : ** bits in the Bitmask. So, in the example above, the cursor numbers
74 : ** would be mapped into integers 0 through 7.
75 : */
76 : typedef struct WhereTerm WhereTerm;
77 : struct WhereTerm {
78 : Expr *pExpr; /* Pointer to the subexpression */
79 : i16 iParent; /* Disable pWC->a[iParent] when this term disabled */
80 : i16 leftCursor; /* Cursor number of X in "X <op> <expr>" */
81 : i16 leftColumn; /* Column number of X in "X <op> <expr>" */
82 : u16 eOperator; /* A WO_xx value describing <op> */
83 : u8 flags; /* Bit flags. See below */
84 : u8 nChild; /* Number of children that must disable us */
85 : WhereClause *pWC; /* The clause this term is part of */
86 : Bitmask prereqRight; /* Bitmask of tables used by pRight */
87 : Bitmask prereqAll; /* Bitmask of tables referenced by p */
88 : };
89 :
90 : /*
91 : ** Allowed values of WhereTerm.flags
92 : */
93 : #define TERM_DYNAMIC 0x01 /* Need to call sqlite3ExprDelete(pExpr) */
94 : #define TERM_VIRTUAL 0x02 /* Added by the optimizer. Do not code */
95 : #define TERM_CODED 0x04 /* This term is already coded */
96 : #define TERM_COPIED 0x08 /* Has a child */
97 : #define TERM_OR_OK 0x10 /* Used during OR-clause processing */
98 :
99 : /*
100 : ** An instance of the following structure holds all information about a
101 : ** WHERE clause. Mostly this is a container for one or more WhereTerms.
102 : */
103 : struct WhereClause {
104 : Parse *pParse; /* The parser context */
105 : ExprMaskSet *pMaskSet; /* Mapping of table indices to bitmasks */
106 : int nTerm; /* Number of terms */
107 : int nSlot; /* Number of entries in a[] */
108 : WhereTerm *a; /* Each a[] describes a term of the WHERE cluase */
109 : WhereTerm aStatic[10]; /* Initial static space for a[] */
110 : };
111 :
112 : /*
113 : ** An instance of the following structure keeps track of a mapping
114 : ** between VDBE cursor numbers and bits of the bitmasks in WhereTerm.
115 : **
116 : ** The VDBE cursor numbers are small integers contained in
117 : ** SrcList_item.iCursor and Expr.iTable fields. For any given WHERE
118 : ** clause, the cursor numbers might not begin with 0 and they might
119 : ** contain gaps in the numbering sequence. But we want to make maximum
120 : ** use of the bits in our bitmasks. This structure provides a mapping
121 : ** from the sparse cursor numbers into consecutive integers beginning
122 : ** with 0.
123 : **
124 : ** If ExprMaskSet.ix[A]==B it means that The A-th bit of a Bitmask
125 : ** corresponds VDBE cursor number B. The A-th bit of a bitmask is 1<<A.
126 : **
127 : ** For example, if the WHERE clause expression used these VDBE
128 : ** cursors: 4, 5, 8, 29, 57, 73. Then the ExprMaskSet structure
129 : ** would map those cursor numbers into bits 0 through 5.
130 : **
131 : ** Note that the mapping is not necessarily ordered. In the example
132 : ** above, the mapping might go like this: 4->3, 5->1, 8->2, 29->0,
133 : ** 57->5, 73->4. Or one of 719 other combinations might be used. It
134 : ** does not really matter. What is important is that sparse cursor
135 : ** numbers all get mapped into bit numbers that begin with 0 and contain
136 : ** no gaps.
137 : */
138 : struct ExprMaskSet {
139 : int n; /* Number of assigned cursor values */
140 : int ix[sizeof(Bitmask)*8]; /* Cursor assigned to each bit */
141 : };
142 :
143 :
144 : /*
145 : ** Bitmasks for the operators that indices are able to exploit. An
146 : ** OR-ed combination of these values can be used when searching for
147 : ** terms in the where clause.
148 : */
149 : #define WO_IN 1
150 : #define WO_EQ 2
151 : #define WO_LT (WO_EQ<<(TK_LT-TK_EQ))
152 : #define WO_LE (WO_EQ<<(TK_LE-TK_EQ))
153 : #define WO_GT (WO_EQ<<(TK_GT-TK_EQ))
154 : #define WO_GE (WO_EQ<<(TK_GE-TK_EQ))
155 : #define WO_MATCH 64
156 : #define WO_ISNULL 128
157 :
158 : /*
159 : ** Value for flags returned by bestIndex().
160 : **
161 : ** The least significant byte is reserved as a mask for WO_ values above.
162 : ** The WhereLevel.flags field is usually set to WO_IN|WO_EQ|WO_ISNULL.
163 : ** But if the table is the right table of a left join, WhereLevel.flags
164 : ** is set to WO_IN|WO_EQ. The WhereLevel.flags field can then be used as
165 : ** the "op" parameter to findTerm when we are resolving equality constraints.
166 : ** ISNULL constraints will then not be used on the right table of a left
167 : ** join. Tickets #2177 and #2189.
168 : */
169 : #define WHERE_ROWID_EQ 0x000100 /* rowid=EXPR or rowid IN (...) */
170 : #define WHERE_ROWID_RANGE 0x000200 /* rowid<EXPR and/or rowid>EXPR */
171 : #define WHERE_COLUMN_EQ 0x001000 /* x=EXPR or x IN (...) */
172 : #define WHERE_COLUMN_RANGE 0x002000 /* x<EXPR and/or x>EXPR */
173 : #define WHERE_COLUMN_IN 0x004000 /* x IN (...) */
174 : #define WHERE_TOP_LIMIT 0x010000 /* x<EXPR or x<=EXPR constraint */
175 : #define WHERE_BTM_LIMIT 0x020000 /* x>EXPR or x>=EXPR constraint */
176 : #define WHERE_IDX_ONLY 0x080000 /* Use index only - omit table */
177 : #define WHERE_ORDERBY 0x100000 /* Output will appear in correct order */
178 : #define WHERE_REVERSE 0x200000 /* Scan in reverse order */
179 : #define WHERE_UNIQUE 0x400000 /* Selects no more than one row */
180 : #define WHERE_VIRTUALTABLE 0x800000 /* Use virtual-table processing */
181 :
182 : /*
183 : ** Initialize a preallocated WhereClause structure.
184 : */
185 : static void whereClauseInit(
186 : WhereClause *pWC, /* The WhereClause to be initialized */
187 : Parse *pParse, /* The parsing context */
188 : ExprMaskSet *pMaskSet /* Mapping from table indices to bitmasks */
189 223 : ){
190 223 : pWC->pParse = pParse;
191 223 : pWC->pMaskSet = pMaskSet;
192 223 : pWC->nTerm = 0;
193 223 : pWC->nSlot = ArraySize(pWC->aStatic);
194 223 : pWC->a = pWC->aStatic;
195 223 : }
196 :
197 : /*
198 : ** Deallocate a WhereClause structure. The WhereClause structure
199 : ** itself is not freed. This routine is the inverse of whereClauseInit().
200 : */
201 223 : static void whereClauseClear(WhereClause *pWC){
202 : int i;
203 : WhereTerm *a;
204 383 : for(i=pWC->nTerm-1, a=pWC->a; i>=0; i--, a++){
205 160 : if( a->flags & TERM_DYNAMIC ){
206 5 : sqlite3ExprDelete(a->pExpr);
207 : }
208 : }
209 223 : if( pWC->a!=pWC->aStatic ){
210 0 : sqliteFree(pWC->a);
211 : }
212 223 : }
213 :
214 : /*
215 : ** Add a new entries to the WhereClause structure. Increase the allocated
216 : ** space as necessary.
217 : **
218 : ** If the flags argument includes TERM_DYNAMIC, then responsibility
219 : ** for freeing the expression p is assumed by the WhereClause object.
220 : **
221 : ** WARNING: This routine might reallocate the space used to store
222 : ** WhereTerms. All pointers to WhereTerms should be invalided after
223 : ** calling this routine. Such pointers may be reinitialized by referencing
224 : ** the pWC->a[] array.
225 : */
226 160 : static int whereClauseInsert(WhereClause *pWC, Expr *p, int flags){
227 : WhereTerm *pTerm;
228 : int idx;
229 160 : if( pWC->nTerm>=pWC->nSlot ){
230 0 : WhereTerm *pOld = pWC->a;
231 0 : pWC->a = sqliteMalloc( sizeof(pWC->a[0])*pWC->nSlot*2 );
232 0 : if( pWC->a==0 ){
233 0 : if( flags & TERM_DYNAMIC ){
234 0 : sqlite3ExprDelete(p);
235 : }
236 0 : return 0;
237 : }
238 0 : memcpy(pWC->a, pOld, sizeof(pWC->a[0])*pWC->nTerm);
239 0 : if( pOld!=pWC->aStatic ){
240 0 : sqliteFree(pOld);
241 : }
242 0 : pWC->nSlot *= 2;
243 : }
244 160 : pTerm = &pWC->a[idx = pWC->nTerm];
245 160 : pWC->nTerm++;
246 160 : pTerm->pExpr = p;
247 160 : pTerm->flags = flags;
248 160 : pTerm->pWC = pWC;
249 160 : pTerm->iParent = -1;
250 160 : return idx;
251 : }
252 :
253 : /*
254 : ** This routine identifies subexpressions in the WHERE clause where
255 : ** each subexpression is separated by the AND operator or some other
256 : ** operator specified in the op parameter. The WhereClause structure
257 : ** is filled with pointers to subexpressions. For example:
258 : **
259 : ** WHERE a=='hello' AND coalesce(b,11)<10 AND (c+12!=d OR c==22)
260 : ** \________/ \_______________/ \________________/
261 : ** slot[0] slot[1] slot[2]
262 : **
263 : ** The original WHERE clause in pExpr is unaltered. All this routine
264 : ** does is make slot[] entries point to substructure within pExpr.
265 : **
266 : ** In the previous sentence and in the diagram, "slot[]" refers to
267 : ** the WhereClause.a[] array. This array grows as needed to contain
268 : ** all terms of the WHERE clause.
269 : */
270 251 : static void whereSplit(WhereClause *pWC, Expr *pExpr, int op){
271 251 : if( pExpr==0 ) return;
272 169 : if( pExpr->op!=op ){
273 155 : whereClauseInsert(pWC, pExpr, 0);
274 : }else{
275 14 : whereSplit(pWC, pExpr->pLeft, op);
276 14 : whereSplit(pWC, pExpr->pRight, op);
277 : }
278 : }
279 :
280 : /*
281 : ** Initialize an expression mask set
282 : */
283 : #define initMaskSet(P) memset(P, 0, sizeof(*P))
284 :
285 : /*
286 : ** Return the bitmask for the given cursor number. Return 0 if
287 : ** iCursor is not in the set.
288 : */
289 975 : static Bitmask getMask(ExprMaskSet *pMaskSet, int iCursor){
290 : int i;
291 1021 : for(i=0; i<pMaskSet->n; i++){
292 1021 : if( pMaskSet->ix[i]==iCursor ){
293 975 : return ((Bitmask)1)<<i;
294 : }
295 : }
296 0 : return 0;
297 : }
298 :
299 : /*
300 : ** Create a new mask for cursor iCursor.
301 : **
302 : ** There is one cursor per table in the FROM clause. The number of
303 : ** tables in the FROM clause is limited by a test early in the
304 : ** sqlite3WhereBegin() routine. So we know that the pMaskSet->ix[]
305 : ** array will never overflow.
306 : */
307 217 : static void createMask(ExprMaskSet *pMaskSet, int iCursor){
308 : assert( pMaskSet->n < ArraySize(pMaskSet->ix) );
309 217 : pMaskSet->ix[pMaskSet->n++] = iCursor;
310 217 : }
311 :
312 : /*
313 : ** This routine walks (recursively) an expression tree and generates
314 : ** a bitmask indicating which tables are used in that expression
315 : ** tree.
316 : **
317 : ** In order for this routine to work, the calling function must have
318 : ** previously invoked sqlite3ExprResolveNames() on the expression. See
319 : ** the header comment on that routine for additional information.
320 : ** The sqlite3ExprResolveNames() routines looks for column names and
321 : ** sets their opcodes to TK_COLUMN and their Expr.iTable fields to
322 : ** the VDBE cursor number of the table. This routine just has to
323 : ** translate the cursor numbers into bitmask values and OR all
324 : ** the bitmasks together.
325 : */
326 : static Bitmask exprListTableUsage(ExprMaskSet*, ExprList*);
327 : static Bitmask exprSelectTableUsage(ExprMaskSet*, Select*);
328 1361 : static Bitmask exprTableUsage(ExprMaskSet *pMaskSet, Expr *p){
329 1361 : Bitmask mask = 0;
330 1361 : if( p==0 ) return 0;
331 763 : if( p->op==TK_COLUMN ){
332 314 : mask = getMask(pMaskSet, p->iTable);
333 314 : return mask;
334 : }
335 449 : mask = exprTableUsage(pMaskSet, p->pRight);
336 449 : mask |= exprTableUsage(pMaskSet, p->pLeft);
337 449 : mask |= exprListTableUsage(pMaskSet, p->pList);
338 449 : mask |= exprSelectTableUsage(pMaskSet, p->pSelect);
339 449 : return mask;
340 : }
341 449 : static Bitmask exprListTableUsage(ExprMaskSet *pMaskSet, ExprList *pList){
342 : int i;
343 449 : Bitmask mask = 0;
344 449 : if( pList ){
345 0 : for(i=0; i<pList->nExpr; i++){
346 0 : mask |= exprTableUsage(pMaskSet, pList->a[i].pExpr);
347 : }
348 : }
349 449 : return mask;
350 : }
351 449 : static Bitmask exprSelectTableUsage(ExprMaskSet *pMaskSet, Select *pS){
352 : Bitmask mask;
353 449 : if( pS==0 ){
354 449 : mask = 0;
355 : }else{
356 0 : mask = exprListTableUsage(pMaskSet, pS->pEList);
357 0 : mask |= exprListTableUsage(pMaskSet, pS->pGroupBy);
358 0 : mask |= exprListTableUsage(pMaskSet, pS->pOrderBy);
359 0 : mask |= exprTableUsage(pMaskSet, pS->pWhere);
360 0 : mask |= exprTableUsage(pMaskSet, pS->pHaving);
361 : }
362 449 : return mask;
363 : }
364 :
365 : /*
366 : ** Return TRUE if the given operator is one of the operators that is
367 : ** allowed for an indexable WHERE clause term. The allowed operators are
368 : ** "=", "<", ">", "<=", ">=", and "IN".
369 : */
370 155 : static int allowedOp(int op){
371 : assert( TK_GT>TK_EQ && TK_GT<TK_GE );
372 : assert( TK_LT>TK_EQ && TK_LT<TK_GE );
373 : assert( TK_LE>TK_EQ && TK_LE<TK_GE );
374 : assert( TK_GE==TK_EQ+4 );
375 155 : return op==TK_IN || (op>=TK_EQ && op<=TK_GE) || op==TK_ISNULL;
376 : }
377 :
378 : /*
379 : ** Swap two objects of type T.
380 : */
381 : #define SWAP(TYPE,A,B) {TYPE t=A; A=B; B=t;}
382 :
383 : /*
384 : ** Commute a comparision operator. Expressions of the form "X op Y"
385 : ** are converted into "Y op X".
386 : */
387 5 : static void exprCommute(Expr *pExpr){
388 : assert( allowedOp(pExpr->op) && pExpr->op!=TK_IN );
389 5 : SWAP(CollSeq*,pExpr->pRight->pColl,pExpr->pLeft->pColl);
390 5 : SWAP(Expr*,pExpr->pRight,pExpr->pLeft);
391 5 : if( pExpr->op>=TK_GT ){
392 : assert( TK_LT==TK_GT+2 );
393 : assert( TK_GE==TK_LE+2 );
394 : assert( TK_GT>TK_EQ );
395 : assert( TK_GT<TK_LE );
396 : assert( pExpr->op>=TK_GT && pExpr->op<=TK_GE );
397 0 : pExpr->op = ((pExpr->op-TK_GT)^2)+TK_GT;
398 : }
399 5 : }
400 :
401 : /*
402 : ** Translate from TK_xx operator to WO_xx bitmask.
403 : */
404 148 : static int operatorMask(int op){
405 : int c;
406 : assert( allowedOp(op) );
407 148 : if( op==TK_IN ){
408 0 : c = WO_IN;
409 148 : }else if( op==TK_ISNULL ){
410 2 : c = WO_ISNULL;
411 : }else{
412 146 : c = WO_EQ<<(op-TK_EQ);
413 : }
414 : assert( op!=TK_ISNULL || c==WO_ISNULL );
415 : assert( op!=TK_IN || c==WO_IN );
416 : assert( op!=TK_EQ || c==WO_EQ );
417 : assert( op!=TK_LT || c==WO_LT );
418 : assert( op!=TK_LE || c==WO_LE );
419 : assert( op!=TK_GT || c==WO_GT );
420 : assert( op!=TK_GE || c==WO_GE );
421 148 : return c;
422 : }
423 :
424 : /*
425 : ** Search for a term in the WHERE clause that is of the form "X <op> <expr>"
426 : ** where X is a reference to the iColumn of table iCur and <op> is one of
427 : ** the WO_xx operator codes specified by the op parameter.
428 : ** Return a pointer to the term. Return 0 if not found.
429 : */
430 : static WhereTerm *findTerm(
431 : WhereClause *pWC, /* The WHERE clause to be searched */
432 : int iCur, /* Cursor number of LHS */
433 : int iColumn, /* Column number of LHS */
434 : Bitmask notReady, /* RHS must not overlap with this mask */
435 : u16 op, /* Mask of WO_xx values describing operator */
436 : Index *pIdx /* Must be compatible with this index, if not NULL */
437 547 : ){
438 : WhereTerm *pTerm;
439 : int k;
440 755 : for(pTerm=pWC->a, k=pWC->nTerm; k; k--, pTerm++){
441 400 : if( pTerm->leftCursor==iCur
442 : && (pTerm->prereqRight & notReady)==0
443 : && pTerm->leftColumn==iColumn
444 : && (pTerm->eOperator & op)!=0
445 : ){
446 192 : if( iCur>=0 && pIdx && pTerm->eOperator!=WO_ISNULL ){
447 18 : Expr *pX = pTerm->pExpr;
448 : CollSeq *pColl;
449 : char idxaff;
450 : int j;
451 18 : Parse *pParse = pWC->pParse;
452 :
453 18 : idxaff = pIdx->pTable->aCol[iColumn].affinity;
454 18 : if( !sqlite3IndexAffinityOk(pX, idxaff) ) continue;
455 18 : pColl = sqlite3ExprCollSeq(pParse, pX->pLeft);
456 18 : if( !pColl ){
457 0 : if( pX->pRight ){
458 0 : pColl = sqlite3ExprCollSeq(pParse, pX->pRight);
459 : }
460 0 : if( !pColl ){
461 0 : pColl = pParse->db->pDfltColl;
462 : }
463 : }
464 18 : for(j=0; j<pIdx->nColumn && pIdx->aiColumn[j]!=iColumn; j++){}
465 : assert( j<pIdx->nColumn );
466 18 : if( sqlite3StrICmp(pColl->zName, pIdx->azColl[j]) ) continue;
467 : }
468 192 : return pTerm;
469 : }
470 : }
471 355 : return 0;
472 : }
473 :
474 : /* Forward reference */
475 : static void exprAnalyze(SrcList*, WhereClause*, int);
476 :
477 : /*
478 : ** Call exprAnalyze on all terms in a WHERE clause.
479 : **
480 : **
481 : */
482 : static void exprAnalyzeAll(
483 : SrcList *pTabList, /* the FROM clause */
484 : WhereClause *pWC /* the WHERE clause to be analyzed */
485 223 : ){
486 : int i;
487 378 : for(i=pWC->nTerm-1; i>=0; i--){
488 155 : exprAnalyze(pTabList, pWC, i);
489 : }
490 223 : }
491 :
492 : #ifndef SQLITE_OMIT_LIKE_OPTIMIZATION
493 : /*
494 : ** Check to see if the given expression is a LIKE or GLOB operator that
495 : ** can be optimized using inequality constraints. Return TRUE if it is
496 : ** so and false if not.
497 : **
498 : ** In order for the operator to be optimizible, the RHS must be a string
499 : ** literal that does not begin with a wildcard.
500 : */
501 : static int isLikeOrGlob(
502 : sqlite3 *db, /* The database */
503 : Expr *pExpr, /* Test this expression */
504 : int *pnPattern, /* Number of non-wildcard prefix characters */
505 : int *pisComplete /* True if the only wildcard is % in the last character */
506 155 : ){
507 : const char *z;
508 : Expr *pRight, *pLeft;
509 : ExprList *pList;
510 : int c, cnt;
511 : int noCase;
512 : char wc[3];
513 : CollSeq *pColl;
514 :
515 155 : if( !sqlite3IsLikeFunction(db, pExpr, &noCase, wc) ){
516 155 : return 0;
517 : }
518 0 : pList = pExpr->pList;
519 0 : pRight = pList->a[0].pExpr;
520 0 : if( pRight->op!=TK_STRING ){
521 0 : return 0;
522 : }
523 0 : pLeft = pList->a[1].pExpr;
524 0 : if( pLeft->op!=TK_COLUMN ){
525 0 : return 0;
526 : }
527 0 : pColl = pLeft->pColl;
528 0 : if( pColl==0 ){
529 : /* TODO: Coverage testing doesn't get this case. Is it actually possible
530 : ** for an expression of type TK_COLUMN to not have an assigned collation
531 : ** sequence at this point?
532 : */
533 0 : pColl = db->pDfltColl;
534 : }
535 0 : if( (pColl->type!=SQLITE_COLL_BINARY || noCase) &&
536 : (pColl->type!=SQLITE_COLL_NOCASE || !noCase) ){
537 0 : return 0;
538 : }
539 0 : sqlite3DequoteExpr(pRight);
540 0 : z = (char *)pRight->token.z;
541 0 : for(cnt=0; (c=z[cnt])!=0 && c!=wc[0] && c!=wc[1] && c!=wc[2]; cnt++){}
542 0 : if( cnt==0 || 255==(u8)z[cnt] ){
543 0 : return 0;
544 : }
545 0 : *pisComplete = z[cnt]==wc[0] && z[cnt+1]==0;
546 0 : *pnPattern = cnt;
547 0 : return 1;
548 : }
549 : #endif /* SQLITE_OMIT_LIKE_OPTIMIZATION */
550 :
551 :
552 : #ifndef SQLITE_OMIT_VIRTUALTABLE
553 : /*
554 : ** Check to see if the given expression is of the form
555 : **
556 : ** column MATCH expr
557 : **
558 : ** If it is then return TRUE. If not, return FALSE.
559 : */
560 : static int isMatchOfColumn(
561 : Expr *pExpr /* Test this expression */
562 155 : ){
563 : ExprList *pList;
564 :
565 155 : if( pExpr->op!=TK_FUNCTION ){
566 155 : return 0;
567 : }
568 0 : if( pExpr->token.n!=5 ||
569 : sqlite3StrNICmp((const char*)pExpr->token.z,"match",5)!=0 ){
570 0 : return 0;
571 : }
572 0 : pList = pExpr->pList;
573 0 : if( pList->nExpr!=2 ){
574 0 : return 0;
575 : }
576 0 : if( pList->a[1].pExpr->op != TK_COLUMN ){
577 0 : return 0;
578 : }
579 0 : return 1;
580 : }
581 : #endif /* SQLITE_OMIT_VIRTUALTABLE */
582 :
583 : /*
584 : ** If the pBase expression originated in the ON or USING clause of
585 : ** a join, then transfer the appropriate markings over to derived.
586 : */
587 0 : static void transferJoinMarkings(Expr *pDerived, Expr *pBase){
588 0 : pDerived->flags |= pBase->flags & EP_FromJoin;
589 0 : pDerived->iRightJoinTable = pBase->iRightJoinTable;
590 0 : }
591 :
592 : #if !defined(SQLITE_OMIT_OR_OPTIMIZATION) && !defined(SQLITE_OMIT_SUBQUERY)
593 : /*
594 : ** Return TRUE if the given term of an OR clause can be converted
595 : ** into an IN clause. The iCursor and iColumn define the left-hand
596 : ** side of the IN clause.
597 : **
598 : ** The context is that we have multiple OR-connected equality terms
599 : ** like this:
600 : **
601 : ** a=<expr1> OR a=<expr2> OR b=<expr3> OR ...
602 : **
603 : ** The pOrTerm input to this routine corresponds to a single term of
604 : ** this OR clause. In order for the term to be a condidate for
605 : ** conversion to an IN operator, the following must be true:
606 : **
607 : ** * The left-hand side of the term must be the column which
608 : ** is identified by iCursor and iColumn.
609 : **
610 : ** * If the right-hand side is also a column, then the affinities
611 : ** of both right and left sides must be such that no type
612 : ** conversions are required on the right. (Ticket #2249)
613 : **
614 : ** If both of these conditions are true, then return true. Otherwise
615 : ** return false.
616 : */
617 0 : static int orTermIsOptCandidate(WhereTerm *pOrTerm, int iCursor, int iColumn){
618 : int affLeft, affRight;
619 : assert( pOrTerm->eOperator==WO_EQ );
620 0 : if( pOrTerm->leftCursor!=iCursor ){
621 0 : return 0;
622 : }
623 0 : if( pOrTerm->leftColumn!=iColumn ){
624 0 : return 0;
625 : }
626 0 : affRight = sqlite3ExprAffinity(pOrTerm->pExpr->pRight);
627 0 : if( affRight==0 ){
628 0 : return 1;
629 : }
630 0 : affLeft = sqlite3ExprAffinity(pOrTerm->pExpr->pLeft);
631 0 : if( affRight!=affLeft ){
632 0 : return 0;
633 : }
634 0 : return 1;
635 : }
636 :
637 : /*
638 : ** Return true if the given term of an OR clause can be ignored during
639 : ** a check to make sure all OR terms are candidates for optimization.
640 : ** In other words, return true if a call to the orTermIsOptCandidate()
641 : ** above returned false but it is not necessary to disqualify the
642 : ** optimization.
643 : **
644 : ** Suppose the original OR phrase was this:
645 : **
646 : ** a=4 OR a=11 OR a=b
647 : **
648 : ** During analysis, the third term gets flipped around and duplicate
649 : ** so that we are left with this:
650 : **
651 : ** a=4 OR a=11 OR a=b OR b=a
652 : **
653 : ** Since the last two terms are duplicates, only one of them
654 : ** has to qualify in order for the whole phrase to qualify. When
655 : ** this routine is called, we know that pOrTerm did not qualify.
656 : ** This routine merely checks to see if pOrTerm has a duplicate that
657 : ** might qualify. If there is a duplicate that has not yet been
658 : ** disqualified, then return true. If there are no duplicates, or
659 : ** the duplicate has also been disqualifed, return false.
660 : */
661 0 : static int orTermHasOkDuplicate(WhereClause *pOr, WhereTerm *pOrTerm){
662 0 : if( pOrTerm->flags & TERM_COPIED ){
663 : /* This is the original term. The duplicate is to the left had
664 : ** has not yet been analyzed and thus has not yet been disqualified. */
665 0 : return 1;
666 : }
667 0 : if( (pOrTerm->flags & TERM_VIRTUAL)!=0
668 : && (pOr->a[pOrTerm->iParent].flags & TERM_OR_OK)!=0 ){
669 : /* This is a duplicate term. The original qualified so this one
670 : ** does not have to. */
671 0 : return 1;
672 : }
673 : /* This is either a singleton term or else it is a duplicate for
674 : ** which the original did not qualify. Either way we are done for. */
675 0 : return 0;
676 : }
677 : #endif /* !SQLITE_OMIT_OR_OPTIMIZATION && !SQLITE_OMIT_SUBQUERY */
678 :
679 : /*
680 : ** The input to this routine is an WhereTerm structure with only the
681 : ** "pExpr" field filled in. The job of this routine is to analyze the
682 : ** subexpression and populate all the other fields of the WhereTerm
683 : ** structure.
684 : **
685 : ** If the expression is of the form "<expr> <op> X" it gets commuted
686 : ** to the standard form of "X <op> <expr>". If the expression is of
687 : ** the form "X <op> Y" where both X and Y are columns, then the original
688 : ** expression is unchanged and a new virtual expression of the form
689 : ** "Y <op> X" is added to the WHERE clause and analyzed separately.
690 : */
691 : static void exprAnalyze(
692 : SrcList *pSrc, /* the FROM clause */
693 : WhereClause *pWC, /* the WHERE clause */
694 : int idxTerm /* Index of the term to be analyzed */
695 155 : ){
696 155 : WhereTerm *pTerm = &pWC->a[idxTerm];
697 155 : ExprMaskSet *pMaskSet = pWC->pMaskSet;
698 155 : Expr *pExpr = pTerm->pExpr;
699 : Bitmask prereqLeft;
700 : Bitmask prereqAll;
701 : int nPattern;
702 : int isComplete;
703 : int op;
704 :
705 155 : if( sqlite3MallocFailed() ) return;
706 155 : prereqLeft = exprTableUsage(pMaskSet, pExpr->pLeft);
707 155 : op = pExpr->op;
708 155 : if( op==TK_IN ){
709 : assert( pExpr->pRight==0 );
710 0 : pTerm->prereqRight = exprListTableUsage(pMaskSet, pExpr->pList)
711 : | exprSelectTableUsage(pMaskSet, pExpr->pSelect);
712 155 : }else if( op==TK_ISNULL ){
713 2 : pTerm->prereqRight = 0;
714 : }else{
715 153 : pTerm->prereqRight = exprTableUsage(pMaskSet, pExpr->pRight);
716 : }
717 155 : prereqAll = exprTableUsage(pMaskSet, pExpr);
718 155 : if( ExprHasProperty(pExpr, EP_FromJoin) ){
719 5 : prereqAll |= getMask(pMaskSet, pExpr->iRightJoinTable);
720 : }
721 155 : pTerm->prereqAll = prereqAll;
722 155 : pTerm->leftCursor = -1;
723 155 : pTerm->iParent = -1;
724 155 : pTerm->eOperator = 0;
725 298 : if( allowedOp(op) && (pTerm->prereqRight & prereqLeft)==0 ){
726 143 : Expr *pLeft = pExpr->pLeft;
727 143 : Expr *pRight = pExpr->pRight;
728 143 : if( pLeft->op==TK_COLUMN ){
729 143 : pTerm->leftCursor = pLeft->iTable;
730 143 : pTerm->leftColumn = pLeft->iColumn;
731 143 : pTerm->eOperator = operatorMask(op);
732 : }
733 143 : if( pRight && pRight->op==TK_COLUMN ){
734 : WhereTerm *pNew;
735 : Expr *pDup;
736 5 : if( pTerm->leftCursor>=0 ){
737 : int idxNew;
738 5 : pDup = sqlite3ExprDup(pExpr);
739 5 : if( sqlite3MallocFailed() ){
740 0 : sqlite3ExprDelete(pDup);
741 0 : return;
742 : }
743 5 : idxNew = whereClauseInsert(pWC, pDup, TERM_VIRTUAL|TERM_DYNAMIC);
744 5 : if( idxNew==0 ) return;
745 5 : pNew = &pWC->a[idxNew];
746 5 : pNew->iParent = idxTerm;
747 5 : pTerm = &pWC->a[idxTerm];
748 5 : pTerm->nChild = 1;
749 5 : pTerm->flags |= TERM_COPIED;
750 : }else{
751 0 : pDup = pExpr;
752 0 : pNew = pTerm;
753 : }
754 5 : exprCommute(pDup);
755 5 : pLeft = pDup->pLeft;
756 5 : pNew->leftCursor = pLeft->iTable;
757 5 : pNew->leftColumn = pLeft->iColumn;
758 5 : pNew->prereqRight = prereqLeft;
759 5 : pNew->prereqAll = prereqAll;
760 5 : pNew->eOperator = operatorMask(pDup->op);
761 : }
762 : }
763 :
764 : #ifndef SQLITE_OMIT_BETWEEN_OPTIMIZATION
765 : /* If a term is the BETWEEN operator, create two new virtual terms
766 : ** that define the range that the BETWEEN implements.
767 : */
768 12 : else if( pExpr->op==TK_BETWEEN ){
769 0 : ExprList *pList = pExpr->pList;
770 : int i;
771 : static const u8 ops[] = {TK_GE, TK_LE};
772 : assert( pList!=0 );
773 : assert( pList->nExpr==2 );
774 0 : for(i=0; i<2; i++){
775 : Expr *pNewExpr;
776 : int idxNew;
777 0 : pNewExpr = sqlite3Expr(ops[i], sqlite3ExprDup(pExpr->pLeft),
778 : sqlite3ExprDup(pList->a[i].pExpr), 0);
779 0 : idxNew = whereClauseInsert(pWC, pNewExpr, TERM_VIRTUAL|TERM_DYNAMIC);
780 0 : exprAnalyze(pSrc, pWC, idxNew);
781 0 : pTerm = &pWC->a[idxTerm];
782 0 : pWC->a[idxNew].iParent = idxTerm;
783 : }
784 0 : pTerm->nChild = 2;
785 : }
786 : #endif /* SQLITE_OMIT_BETWEEN_OPTIMIZATION */
787 :
788 : #if !defined(SQLITE_OMIT_OR_OPTIMIZATION) && !defined(SQLITE_OMIT_SUBQUERY)
789 : /* Attempt to convert OR-connected terms into an IN operator so that
790 : ** they can make use of indices. Example:
791 : **
792 : ** x = expr1 OR expr2 = x OR x = expr3
793 : **
794 : ** is converted into
795 : **
796 : ** x IN (expr1,expr2,expr3)
797 : **
798 : ** This optimization must be omitted if OMIT_SUBQUERY is defined because
799 : ** the compiler for the the IN operator is part of sub-queries.
800 : */
801 12 : else if( pExpr->op==TK_OR ){
802 : int ok;
803 : int i, j;
804 : int iColumn, iCursor;
805 : WhereClause sOr;
806 : WhereTerm *pOrTerm;
807 :
808 : assert( (pTerm->flags & TERM_DYNAMIC)==0 );
809 2 : whereClauseInit(&sOr, pWC->pParse, pMaskSet);
810 2 : whereSplit(&sOr, pExpr, TK_OR);
811 2 : exprAnalyzeAll(pSrc, &sOr);
812 : assert( sOr.nTerm>=2 );
813 2 : j = 0;
814 : do{
815 : assert( j<sOr.nTerm );
816 2 : iColumn = sOr.a[j].leftColumn;
817 2 : iCursor = sOr.a[j].leftCursor;
818 2 : ok = iCursor>=0;
819 2 : for(i=sOr.nTerm-1, pOrTerm=sOr.a; i>=0 && ok; i--, pOrTerm++){
820 2 : if( pOrTerm->eOperator!=WO_EQ ){
821 2 : goto or_not_possible;
822 : }
823 0 : if( orTermIsOptCandidate(pOrTerm, iCursor, iColumn) ){
824 0 : pOrTerm->flags |= TERM_OR_OK;
825 0 : }else if( orTermHasOkDuplicate(&sOr, pOrTerm) ){
826 0 : pOrTerm->flags &= ~TERM_OR_OK;
827 : }else{
828 0 : ok = 0;
829 : }
830 : }
831 0 : }while( !ok && (sOr.a[j++].flags & TERM_COPIED)!=0 && j<2 );
832 0 : if( ok ){
833 0 : ExprList *pList = 0;
834 : Expr *pNew, *pDup;
835 0 : Expr *pLeft = 0;
836 0 : for(i=sOr.nTerm-1, pOrTerm=sOr.a; i>=0 && ok; i--, pOrTerm++){
837 0 : if( (pOrTerm->flags & TERM_OR_OK)==0 ) continue;
838 0 : pDup = sqlite3ExprDup(pOrTerm->pExpr->pRight);
839 0 : pList = sqlite3ExprListAppend(pList, pDup, 0);
840 0 : pLeft = pOrTerm->pExpr->pLeft;
841 : }
842 : assert( pLeft!=0 );
843 0 : pDup = sqlite3ExprDup(pLeft);
844 0 : pNew = sqlite3Expr(TK_IN, pDup, 0, 0);
845 0 : if( pNew ){
846 : int idxNew;
847 0 : transferJoinMarkings(pNew, pExpr);
848 0 : pNew->pList = pList;
849 0 : idxNew = whereClauseInsert(pWC, pNew, TERM_VIRTUAL|TERM_DYNAMIC);
850 0 : exprAnalyze(pSrc, pWC, idxNew);
851 0 : pTerm = &pWC->a[idxTerm];
852 0 : pWC->a[idxNew].iParent = idxTerm;
853 0 : pTerm->nChild = 1;
854 : }else{
855 0 : sqlite3ExprListDelete(pList);
856 : }
857 : }
858 2 : or_not_possible:
859 2 : whereClauseClear(&sOr);
860 : }
861 : #endif /* SQLITE_OMIT_OR_OPTIMIZATION */
862 :
863 : #ifndef SQLITE_OMIT_LIKE_OPTIMIZATION
864 : /* Add constraints to reduce the search space on a LIKE or GLOB
865 : ** operator.
866 : */
867 155 : if( isLikeOrGlob(pWC->pParse->db, pExpr, &nPattern, &isComplete) ){
868 : Expr *pLeft, *pRight;
869 : Expr *pStr1, *pStr2;
870 : Expr *pNewExpr1, *pNewExpr2;
871 : int idxNew1, idxNew2;
872 :
873 0 : pLeft = pExpr->pList->a[1].pExpr;
874 0 : pRight = pExpr->pList->a[0].pExpr;
875 0 : pStr1 = sqlite3Expr(TK_STRING, 0, 0, 0);
876 0 : if( pStr1 ){
877 0 : sqlite3TokenCopy(&pStr1->token, &pRight->token);
878 0 : pStr1->token.n = nPattern;
879 : }
880 0 : pStr2 = sqlite3ExprDup(pStr1);
881 0 : if( pStr2 ){
882 : assert( pStr2->token.dyn );
883 0 : ++*(u8*)&pStr2->token.z[nPattern-1];
884 : }
885 0 : pNewExpr1 = sqlite3Expr(TK_GE, sqlite3ExprDup(pLeft), pStr1, 0);
886 0 : idxNew1 = whereClauseInsert(pWC, pNewExpr1, TERM_VIRTUAL|TERM_DYNAMIC);
887 0 : exprAnalyze(pSrc, pWC, idxNew1);
888 0 : pNewExpr2 = sqlite3Expr(TK_LT, sqlite3ExprDup(pLeft), pStr2, 0);
889 0 : idxNew2 = whereClauseInsert(pWC, pNewExpr2, TERM_VIRTUAL|TERM_DYNAMIC);
890 0 : exprAnalyze(pSrc, pWC, idxNew2);
891 0 : pTerm = &pWC->a[idxTerm];
892 0 : if( isComplete ){
893 0 : pWC->a[idxNew1].iParent = idxTerm;
894 0 : pWC->a[idxNew2].iParent = idxTerm;
895 0 : pTerm->nChild = 2;
896 : }
897 : }
898 : #endif /* SQLITE_OMIT_LIKE_OPTIMIZATION */
899 :
900 : #ifndef SQLITE_OMIT_VIRTUALTABLE
901 : /* Add a WO_MATCH auxiliary term to the constraint set if the
902 : ** current expression is of the form: column MATCH expr.
903 : ** This information is used by the xBestIndex methods of
904 : ** virtual tables. The native query optimizer does not attempt
905 : ** to do anything with MATCH functions.
906 : */
907 155 : if( isMatchOfColumn(pExpr) ){
908 : int idxNew;
909 : Expr *pRight, *pLeft;
910 : WhereTerm *pNewTerm;
911 : Bitmask prereqColumn, prereqExpr;
912 :
913 0 : pRight = pExpr->pList->a[0].pExpr;
914 0 : pLeft = pExpr->pList->a[1].pExpr;
915 0 : prereqExpr = exprTableUsage(pMaskSet, pRight);
916 0 : prereqColumn = exprTableUsage(pMaskSet, pLeft);
917 0 : if( (prereqExpr & prereqColumn)==0 ){
918 : Expr *pNewExpr;
919 0 : pNewExpr = sqlite3Expr(TK_MATCH, 0, sqlite3ExprDup(pRight), 0);
920 0 : idxNew = whereClauseInsert(pWC, pNewExpr, TERM_VIRTUAL|TERM_DYNAMIC);
921 0 : pNewTerm = &pWC->a[idxNew];
922 0 : pNewTerm->prereqRight = prereqExpr;
923 0 : pNewTerm->leftCursor = pLeft->iTable;
924 0 : pNewTerm->leftColumn = pLeft->iColumn;
925 0 : pNewTerm->eOperator = WO_MATCH;
926 0 : pNewTerm->iParent = idxTerm;
927 0 : pTerm = &pWC->a[idxTerm];
928 0 : pTerm->nChild = 1;
929 0 : pTerm->flags |= TERM_COPIED;
930 0 : pNewTerm->prereqAll = pTerm->prereqAll;
931 : }
932 : }
933 : #endif /* SQLITE_OMIT_VIRTUALTABLE */
934 : }
935 :
936 : /*
937 : ** Return TRUE if any of the expressions in pList->a[iFirst...] contain
938 : ** a reference to any table other than the iBase table.
939 : */
940 : static int referencesOtherTables(
941 : ExprList *pList, /* Search expressions in ths list */
942 : ExprMaskSet *pMaskSet, /* Mapping from tables to bitmaps */
943 : int iFirst, /* Be searching with the iFirst-th expression */
944 : int iBase /* Ignore references to this table */
945 0 : ){
946 0 : Bitmask allowed = ~getMask(pMaskSet, iBase);
947 0 : while( iFirst<pList->nExpr ){
948 0 : if( (exprTableUsage(pMaskSet, pList->a[iFirst++].pExpr)&allowed)!=0 ){
949 0 : return 1;
950 : }
951 : }
952 0 : return 0;
953 : }
954 :
955 :
956 : /*
957 : ** This routine decides if pIdx can be used to satisfy the ORDER BY
958 : ** clause. If it can, it returns 1. If pIdx cannot satisfy the
959 : ** ORDER BY clause, this routine returns 0.
960 : **
961 : ** pOrderBy is an ORDER BY clause from a SELECT statement. pTab is the
962 : ** left-most table in the FROM clause of that same SELECT statement and
963 : ** the table has a cursor number of "base". pIdx is an index on pTab.
964 : **
965 : ** nEqCol is the number of columns of pIdx that are used as equality
966 : ** constraints. Any of these columns may be missing from the ORDER BY
967 : ** clause and the match can still be a success.
968 : **
969 : ** All terms of the ORDER BY that match against the index must be either
970 : ** ASC or DESC. (Terms of the ORDER BY clause past the end of a UNIQUE
971 : ** index do not need to satisfy this constraint.) The *pbRev value is
972 : ** set to 1 if the ORDER BY clause is all DESC and it is set to 0 if
973 : ** the ORDER BY clause is all ASC.
974 : */
975 : static int isSortingIndex(
976 : Parse *pParse, /* Parsing context */
977 : ExprMaskSet *pMaskSet, /* Mapping from table indices to bitmaps */
978 : Index *pIdx, /* The index we are testing */
979 : int base, /* Cursor number for the table to be sorted */
980 : ExprList *pOrderBy, /* The ORDER BY clause */
981 : int nEqCol, /* Number of index columns with == constraints */
982 : int *pbRev /* Set to 1 if ORDER BY is DESC */
983 5 : ){
984 : int i, j; /* Loop counters */
985 5 : int sortOrder = 0; /* XOR of index and ORDER BY sort direction */
986 : int nTerm; /* Number of ORDER BY terms */
987 : struct ExprList_item *pTerm; /* A term of the ORDER BY clause */
988 5 : sqlite3 *db = pParse->db;
989 :
990 : assert( pOrderBy!=0 );
991 5 : nTerm = pOrderBy->nExpr;
992 : assert( nTerm>0 );
993 :
994 : /* Match terms of the ORDER BY clause against columns of
995 : ** the index.
996 : **
997 : ** Note that indices have pIdx->nColumn regular columns plus
998 : ** one additional column containing the rowid. The rowid column
999 : ** of the index is also allowed to match against the ORDER BY
1000 : ** clause.
1001 : */
1002 9 : for(i=j=0, pTerm=pOrderBy->a; j<nTerm && i<=pIdx->nColumn; i++){
1003 : Expr *pExpr; /* The expression of the ORDER BY pTerm */
1004 : CollSeq *pColl; /* The collating sequence of pExpr */
1005 : int termSortOrder; /* Sort order for this term */
1006 : int iColumn; /* The i-th column of the index. -1 for rowid */
1007 : int iSortOrder; /* 1 for DESC, 0 for ASC on the i-th index term */
1008 : const char *zColl; /* Name of the collating sequence for i-th index term */
1009 :
1010 5 : pExpr = pTerm->pExpr;
1011 5 : if( pExpr->op!=TK_COLUMN || pExpr->iTable!=base ){
1012 : /* Can not use an index sort on anything that is not a column in the
1013 : ** left-most table of the FROM clause */
1014 : break;
1015 : }
1016 5 : pColl = sqlite3ExprCollSeq(pParse, pExpr);
1017 5 : if( !pColl ){
1018 0 : pColl = db->pDfltColl;
1019 : }
1020 5 : if( i<pIdx->nColumn ){
1021 5 : iColumn = pIdx->aiColumn[i];
1022 5 : if( iColumn==pIdx->pTable->iPKey ){
1023 0 : iColumn = -1;
1024 : }
1025 5 : iSortOrder = pIdx->aSortOrder[i];
1026 5 : zColl = pIdx->azColl[i];
1027 : }else{
1028 0 : iColumn = -1;
1029 0 : iSortOrder = 0;
1030 0 : zColl = pColl->zName;
1031 : }
1032 5 : if( pExpr->iColumn!=iColumn || sqlite3StrICmp(pColl->zName, zColl) ){
1033 : /* Term j of the ORDER BY clause does not match column i of the index */
1034 1 : if( i<nEqCol ){
1035 : /* If an index column that is constrained by == fails to match an
1036 : ** ORDER BY term, that is OK. Just ignore that column of the index
1037 : */
1038 0 : continue;
1039 : }else{
1040 : /* If an index column fails to match and is not constrained by ==
1041 : ** then the index cannot satisfy the ORDER BY constraint.
1042 : */
1043 1 : return 0;
1044 : }
1045 : }
1046 : assert( pIdx->aSortOrder!=0 );
1047 : assert( pTerm->sortOrder==0 || pTerm->sortOrder==1 );
1048 : assert( iSortOrder==0 || iSortOrder==1 );
1049 4 : termSortOrder = iSortOrder ^ pTerm->sortOrder;
1050 4 : if( i>nEqCol ){
1051 0 : if( termSortOrder!=sortOrder ){
1052 : /* Indices can only be used if all ORDER BY terms past the
1053 : ** equality constraints are all either DESC or ASC. */
1054 0 : return 0;
1055 : }
1056 : }else{
1057 4 : sortOrder = termSortOrder;
1058 : }
1059 4 : j++;
1060 4 : pTerm++;
1061 4 : if( iColumn<0 && !referencesOtherTables(pOrderBy, pMaskSet, j, base) ){
1062 : /* If the indexed column is the primary key and everything matches
1063 : ** so far and none of the ORDER BY terms to the right reference other
1064 : ** tables in the join, then we are assured that the index can be used
1065 : ** to sort because the primary key is unique and so none of the other
1066 : ** columns will make any difference
1067 : */
1068 0 : j = nTerm;
1069 : }
1070 : }
1071 :
1072 4 : *pbRev = sortOrder!=0;
1073 4 : if( j>=nTerm ){
1074 : /* All terms of the ORDER BY clause are covered by this index so
1075 : ** this index can be used for sorting. */
1076 4 : return 1;
1077 : }
1078 0 : if( pIdx->onError!=OE_None && i==pIdx->nColumn
1079 : && !referencesOtherTables(pOrderBy, pMaskSet, j, base) ){
1080 : /* All terms of this index match some prefix of the ORDER BY clause
1081 : ** and the index is UNIQUE and no terms on the tail of the ORDER BY
1082 : ** clause reference other tables in a join. If this is all true then
1083 : ** the order by clause is superfluous. */
1084 0 : return 1;
1085 : }
1086 0 : return 0;
1087 : }
1088 :
1089 : /*
1090 : ** Check table to see if the ORDER BY clause in pOrderBy can be satisfied
1091 : ** by sorting in order of ROWID. Return true if so and set *pbRev to be
1092 : ** true for reverse ROWID and false for forward ROWID order.
1093 : */
1094 : static int sortableByRowid(
1095 : int base, /* Cursor number for table to be sorted */
1096 : ExprList *pOrderBy, /* The ORDER BY clause */
1097 : ExprMaskSet *pMaskSet, /* Mapping from tables to bitmaps */
1098 : int *pbRev /* Set to 1 if ORDER BY is DESC */
1099 4 : ){
1100 : Expr *p;
1101 :
1102 : assert( pOrderBy!=0 );
1103 : assert( pOrderBy->nExpr>0 );
1104 4 : p = pOrderBy->a[0].pExpr;
1105 4 : if( p->op==TK_COLUMN && p->iTable==base && p->iColumn==-1
1106 : && !referencesOtherTables(pOrderBy, pMaskSet, 1, base) ){
1107 0 : *pbRev = pOrderBy->a[0].sortOrder;
1108 0 : return 1;
1109 : }
1110 4 : return 0;
1111 : }
1112 :
1113 : /*
1114 : ** Prepare a crude estimate of the logarithm of the input value.
1115 : ** The results need not be exact. This is only used for estimating
1116 : ** the total cost of performing operatings with O(logN) or O(NlogN)
1117 : ** complexity. Because N is just a guess, it is no great tragedy if
1118 : ** logN is a little off.
1119 : */
1120 79 : static double estLog(double N){
1121 79 : double logN = 1;
1122 79 : double x = 10;
1123 183 : while( N>x ){
1124 25 : logN += 1;
1125 25 : x *= 10;
1126 : }
1127 79 : return logN;
1128 : }
1129 :
1130 : /*
1131 : ** Two routines for printing the content of an sqlite3_index_info
1132 : ** structure. Used for testing and debugging only. If neither
1133 : ** SQLITE_TEST or SQLITE_DEBUG are defined, then these routines
1134 : ** are no-ops.
1135 : */
1136 : #if !defined(SQLITE_OMIT_VIRTUALTABLE) && defined(SQLITE_DEBUG)
1137 : static void TRACE_IDX_INPUTS(sqlite3_index_info *p){
1138 : int i;
1139 : if( !sqlite3_where_trace ) return;
1140 : for(i=0; i<p->nConstraint; i++){
1141 : sqlite3DebugPrintf(" constraint[%d]: col=%d termid=%d op=%d usabled=%d\n",
1142 : i,
1143 : p->aConstraint[i].iColumn,
1144 : p->aConstraint[i].iTermOffset,
1145 : p->aConstraint[i].op,
1146 : p->aConstraint[i].usable);
1147 : }
1148 : for(i=0; i<p->nOrderBy; i++){
1149 : sqlite3DebugPrintf(" orderby[%d]: col=%d desc=%d\n",
1150 : i,
1151 : p->aOrderBy[i].iColumn,
1152 : p->aOrderBy[i].desc);
1153 : }
1154 : }
1155 : static void TRACE_IDX_OUTPUTS(sqlite3_index_info *p){
1156 : int i;
1157 : if( !sqlite3_where_trace ) return;
1158 : for(i=0; i<p->nConstraint; i++){
1159 : sqlite3DebugPrintf(" usage[%d]: argvIdx=%d omit=%d\n",
1160 : i,
1161 : p->aConstraintUsage[i].argvIndex,
1162 : p->aConstraintUsage[i].omit);
1163 : }
1164 : sqlite3DebugPrintf(" idxNum=%d\n", p->idxNum);
1165 : sqlite3DebugPrintf(" idxStr=%s\n", p->idxStr);
1166 : sqlite3DebugPrintf(" orderByConsumed=%d\n", p->orderByConsumed);
1167 : sqlite3DebugPrintf(" estimatedCost=%g\n", p->estimatedCost);
1168 : }
1169 : #else
1170 : #define TRACE_IDX_INPUTS(A)
1171 : #define TRACE_IDX_OUTPUTS(A)
1172 : #endif
1173 :
1174 : #ifndef SQLITE_OMIT_VIRTUALTABLE
1175 : /*
1176 : ** Compute the best index for a virtual table.
1177 : **
1178 : ** The best index is computed by the xBestIndex method of the virtual
1179 : ** table module. This routine is really just a wrapper that sets up
1180 : ** the sqlite3_index_info structure that is used to communicate with
1181 : ** xBestIndex.
1182 : **
1183 : ** In a join, this routine might be called multiple times for the
1184 : ** same virtual table. The sqlite3_index_info structure is created
1185 : ** and initialized on the first invocation and reused on all subsequent
1186 : ** invocations. The sqlite3_index_info structure is also used when
1187 : ** code is generated to access the virtual table. The whereInfoDelete()
1188 : ** routine takes care of freeing the sqlite3_index_info structure after
1189 : ** everybody has finished with it.
1190 : */
1191 : static double bestVirtualIndex(
1192 : Parse *pParse, /* The parsing context */
1193 : WhereClause *pWC, /* The WHERE clause */
1194 : struct SrcList_item *pSrc, /* The FROM clause term to search */
1195 : Bitmask notReady, /* Mask of cursors that are not available */
1196 : ExprList *pOrderBy, /* The order by clause */
1197 : int orderByUsable, /* True if we can potential sort */
1198 : sqlite3_index_info **ppIdxInfo /* Index information passed to xBestIndex */
1199 0 : ){
1200 0 : Table *pTab = pSrc->pTab;
1201 : sqlite3_index_info *pIdxInfo;
1202 : struct sqlite3_index_constraint *pIdxCons;
1203 : struct sqlite3_index_orderby *pIdxOrderBy;
1204 : struct sqlite3_index_constraint_usage *pUsage;
1205 : WhereTerm *pTerm;
1206 : int i, j;
1207 : int nOrderBy;
1208 : int rc;
1209 :
1210 : /* If the sqlite3_index_info structure has not been previously
1211 : ** allocated and initialized for this virtual table, then allocate
1212 : ** and initialize it now
1213 : */
1214 0 : pIdxInfo = *ppIdxInfo;
1215 0 : if( pIdxInfo==0 ){
1216 : WhereTerm *pTerm;
1217 : int nTerm;
1218 : WHERETRACE(("Recomputing index info for %s...\n", pTab->zName));
1219 :
1220 : /* Count the number of possible WHERE clause constraints referring
1221 : ** to this virtual table */
1222 0 : for(i=nTerm=0, pTerm=pWC->a; i<pWC->nTerm; i++, pTerm++){
1223 0 : if( pTerm->leftCursor != pSrc->iCursor ) continue;
1224 0 : if( pTerm->eOperator==WO_IN ) continue;
1225 0 : nTerm++;
1226 : }
1227 :
1228 : /* If the ORDER BY clause contains only columns in the current
1229 : ** virtual table then allocate space for the aOrderBy part of
1230 : ** the sqlite3_index_info structure.
1231 : */
1232 0 : nOrderBy = 0;
1233 0 : if( pOrderBy ){
1234 0 : for(i=0; i<pOrderBy->nExpr; i++){
1235 0 : Expr *pExpr = pOrderBy->a[i].pExpr;
1236 0 : if( pExpr->op!=TK_COLUMN || pExpr->iTable!=pSrc->iCursor ) break;
1237 : }
1238 0 : if( i==pOrderBy->nExpr ){
1239 0 : nOrderBy = pOrderBy->nExpr;
1240 : }
1241 : }
1242 :
1243 : /* Allocate the sqlite3_index_info structure
1244 : */
1245 0 : pIdxInfo = sqliteMalloc( sizeof(*pIdxInfo)
1246 : + (sizeof(*pIdxCons) + sizeof(*pUsage))*nTerm
1247 : + sizeof(*pIdxOrderBy)*nOrderBy );
1248 0 : if( pIdxInfo==0 ){
1249 0 : sqlite3ErrorMsg(pParse, "out of memory");
1250 0 : return 0.0;
1251 : }
1252 0 : *ppIdxInfo = pIdxInfo;
1253 :
1254 : /* Initialize the structure. The sqlite3_index_info structure contains
1255 : ** many fields that are declared "const" to prevent xBestIndex from
1256 : ** changing them. We have to do some funky casting in order to
1257 : ** initialize those fields.
1258 : */
1259 0 : pIdxCons = (struct sqlite3_index_constraint*)&pIdxInfo[1];
1260 0 : pIdxOrderBy = (struct sqlite3_index_orderby*)&pIdxCons[nTerm];
1261 0 : pUsage = (struct sqlite3_index_constraint_usage*)&pIdxOrderBy[nOrderBy];
1262 0 : *(int*)&pIdxInfo->nConstraint = nTerm;
1263 0 : *(int*)&pIdxInfo->nOrderBy = nOrderBy;
1264 0 : *(struct sqlite3_index_constraint**)&pIdxInfo->aConstraint = pIdxCons;
1265 0 : *(struct sqlite3_index_orderby**)&pIdxInfo->aOrderBy = pIdxOrderBy;
1266 0 : *(struct sqlite3_index_constraint_usage**)&pIdxInfo->aConstraintUsage =
1267 : pUsage;
1268 :
1269 0 : for(i=j=0, pTerm=pWC->a; i<pWC->nTerm; i++, pTerm++){
1270 0 : if( pTerm->leftCursor != pSrc->iCursor ) continue;
1271 0 : if( pTerm->eOperator==WO_IN ) continue;
1272 0 : pIdxCons[j].iColumn = pTerm->leftColumn;
1273 0 : pIdxCons[j].iTermOffset = i;
1274 0 : pIdxCons[j].op = pTerm->eOperator;
1275 : /* The direct assignment in the previous line is possible only because
1276 : ** the WO_ and SQLITE_INDEX_CONSTRAINT_ codes are identical. The
1277 : ** following asserts verify this fact. */
1278 : assert( WO_EQ==SQLITE_INDEX_CONSTRAINT_EQ );
1279 : assert( WO_LT==SQLITE_INDEX_CONSTRAINT_LT );
1280 : assert( WO_LE==SQLITE_INDEX_CONSTRAINT_LE );
1281 : assert( WO_GT==SQLITE_INDEX_CONSTRAINT_GT );
1282 : assert( WO_GE==SQLITE_INDEX_CONSTRAINT_GE );
1283 : assert( WO_MATCH==SQLITE_INDEX_CONSTRAINT_MATCH );
1284 : assert( pTerm->eOperator & (WO_EQ|WO_LT|WO_LE|WO_GT|WO_GE|WO_MATCH) );
1285 0 : j++;
1286 : }
1287 0 : for(i=0; i<nOrderBy; i++){
1288 0 : Expr *pExpr = pOrderBy->a[i].pExpr;
1289 0 : pIdxOrderBy[i].iColumn = pExpr->iColumn;
1290 0 : pIdxOrderBy[i].desc = pOrderBy->a[i].sortOrder;
1291 : }
1292 : }
1293 :
1294 : /* At this point, the sqlite3_index_info structure that pIdxInfo points
1295 : ** to will have been initialized, either during the current invocation or
1296 : ** during some prior invocation. Now we just have to customize the
1297 : ** details of pIdxInfo for the current invocation and pass it to
1298 : ** xBestIndex.
1299 : */
1300 :
1301 : /* The module name must be defined. Also, by this point there must
1302 : ** be a pointer to an sqlite3_vtab structure. Otherwise
1303 : ** sqlite3ViewGetColumnNames() would have picked up the error.
1304 : */
1305 : assert( pTab->azModuleArg && pTab->azModuleArg[0] );
1306 : assert( pTab->pVtab );
1307 : #if 0
1308 : if( pTab->pVtab==0 ){
1309 : sqlite3ErrorMsg(pParse, "undefined module %s for table %s",
1310 : pTab->azModuleArg[0], pTab->zName);
1311 : return 0.0;
1312 : }
1313 : #endif
1314 :
1315 : /* Set the aConstraint[].usable fields and initialize all
1316 : ** output variables to zero.
1317 : **
1318 : ** aConstraint[].usable is true for constraints where the right-hand
1319 : ** side contains only references to tables to the left of the current
1320 : ** table. In other words, if the constraint is of the form:
1321 : **
1322 : ** column = expr
1323 : **
1324 : ** and we are evaluating a join, then the constraint on column is
1325 : ** only valid if all tables referenced in expr occur to the left
1326 : ** of the table containing column.
1327 : **
1328 : ** The aConstraints[] array contains entries for all constraints
1329 : ** on the current table. That way we only have to compute it once
1330 : ** even though we might try to pick the best index multiple times.
1331 : ** For each attempt at picking an index, the order of tables in the
1332 : ** join might be different so we have to recompute the usable flag
1333 : ** each time.
1334 : */
1335 0 : pIdxCons = *(struct sqlite3_index_constraint**)&pIdxInfo->aConstraint;
1336 0 : pUsage = pIdxInfo->aConstraintUsage;
1337 0 : for(i=0; i<pIdxInfo->nConstraint; i++, pIdxCons++){
1338 0 : j = pIdxCons->iTermOffset;
1339 0 : pTerm = &pWC->a[j];
1340 0 : pIdxCons->usable = (pTerm->prereqRight & notReady)==0;
1341 : }
1342 0 : memset(pUsage, 0, sizeof(pUsage[0])*pIdxInfo->nConstraint);
1343 0 : if( pIdxInfo->needToFreeIdxStr ){
1344 0 : sqlite3_free(pIdxInfo->idxStr);
1345 : }
1346 0 : pIdxInfo->idxStr = 0;
1347 0 : pIdxInfo->idxNum = 0;
1348 0 : pIdxInfo->needToFreeIdxStr = 0;
1349 0 : pIdxInfo->orderByConsumed = 0;
1350 0 : pIdxInfo->estimatedCost = SQLITE_BIG_DBL / 2.0;
1351 0 : nOrderBy = pIdxInfo->nOrderBy;
1352 0 : if( pIdxInfo->nOrderBy && !orderByUsable ){
1353 0 : *(int*)&pIdxInfo->nOrderBy = 0;
1354 : }
1355 :
1356 0 : sqlite3SafetyOff(pParse->db);
1357 : WHERETRACE(("xBestIndex for %s\n", pTab->zName));
1358 : TRACE_IDX_INPUTS(pIdxInfo);
1359 0 : rc = pTab->pVtab->pModule->xBestIndex(pTab->pVtab, pIdxInfo);
1360 : TRACE_IDX_OUTPUTS(pIdxInfo);
1361 0 : if( rc!=SQLITE_OK ){
1362 0 : if( rc==SQLITE_NOMEM ){
1363 0 : sqlite3FailedMalloc();
1364 : }else {
1365 0 : sqlite3ErrorMsg(pParse, "%s", sqlite3ErrStr(rc));
1366 : }
1367 0 : sqlite3SafetyOn(pParse->db);
1368 : }else{
1369 0 : rc = sqlite3SafetyOn(pParse->db);
1370 : }
1371 0 : *(int*)&pIdxInfo->nOrderBy = nOrderBy;
1372 :
1373 0 : return pIdxInfo->estimatedCost;
1374 : }
1375 : #endif /* SQLITE_OMIT_VIRTUALTABLE */
1376 :
1377 : /*
1378 : ** Find the best index for accessing a particular table. Return a pointer
1379 : ** to the index, flags that describe how the index should be used, the
1380 : ** number of equality constraints, and the "cost" for this index.
1381 : **
1382 : ** The lowest cost index wins. The cost is an estimate of the amount of
1383 : ** CPU and disk I/O need to process the request using the selected index.
1384 : ** Factors that influence cost include:
1385 : **
1386 : ** * The estimated number of rows that will be retrieved. (The
1387 : ** fewer the better.)
1388 : **
1389 : ** * Whether or not sorting must occur.
1390 : **
1391 : ** * Whether or not there must be separate lookups in the
1392 : ** index and in the main table.
1393 : **
1394 : */
1395 : static double bestIndex(
1396 : Parse *pParse, /* The parsing context */
1397 : WhereClause *pWC, /* The WHERE clause */
1398 : struct SrcList_item *pSrc, /* The FROM clause term to search */
1399 : Bitmask notReady, /* Mask of cursors that are not available */
1400 : ExprList *pOrderBy, /* The order by clause */
1401 : Index **ppIndex, /* Make *ppIndex point to the best index */
1402 : int *pFlags, /* Put flags describing this choice in *pFlags */
1403 : int *pnEq /* Put the number of == or IN constraints here */
1404 217 : ){
1405 : WhereTerm *pTerm;
1406 217 : Index *bestIdx = 0; /* Index that gives the lowest cost */
1407 : double lowestCost; /* The cost of using bestIdx */
1408 217 : int bestFlags = 0; /* Flags associated with bestIdx */
1409 217 : int bestNEq = 0; /* Best value for nEq */
1410 217 : int iCur = pSrc->iCursor; /* The cursor of the table to be accessed */
1411 : Index *pProbe; /* An index we are evaluating */
1412 : int rev; /* True to scan in reverse order */
1413 : int flags; /* Flags associated with pProbe */
1414 : int nEq; /* Number of == or IN constraints */
1415 : int eqTermMask; /* Mask of valid equality operators */
1416 : double cost; /* Cost of using pProbe */
1417 :
1418 : WHERETRACE(("bestIndex: tbl=%s notReady=%x\n", pSrc->pTab->zName, notReady));
1419 217 : lowestCost = SQLITE_BIG_DBL;
1420 217 : pProbe = pSrc->pTab->pIndex;
1421 :
1422 : /* If the table has no indices and there are no terms in the where
1423 : ** clause that refer to the ROWID, then we will never be able to do
1424 : ** anything other than a full table scan on this table. We might as
1425 : ** well put it first in the join order. That way, perhaps it can be
1426 : ** referenced by other tables in the join.
1427 : */
1428 217 : if( pProbe==0 &&
1429 : findTerm(pWC, iCur, -1, 0, WO_EQ|WO_IN|WO_LT|WO_LE|WO_GT|WO_GE,0)==0 &&
1430 : (pOrderBy==0 || !sortableByRowid(iCur, pOrderBy, pWC->pMaskSet, &rev)) ){
1431 93 : *pFlags = 0;
1432 93 : *ppIndex = 0;
1433 93 : *pnEq = 0;
1434 93 : return 0.0;
1435 : }
1436 :
1437 : /* Check for a rowid=EXPR or rowid IN (...) constraints
1438 : */
1439 124 : pTerm = findTerm(pWC, iCur, -1, notReady, WO_EQ|WO_IN, 0);
1440 124 : if( pTerm ){
1441 : Expr *pExpr;
1442 58 : *ppIndex = 0;
1443 58 : bestFlags = WHERE_ROWID_EQ;
1444 58 : if( pTerm->eOperator & WO_EQ ){
1445 : /* Rowid== is always the best pick. Look no further. Because only
1446 : ** a single row is generated, output is always in sorted order */
1447 58 : *pFlags = WHERE_ROWID_EQ | WHERE_UNIQUE;
1448 58 : *pnEq = 1;
1449 : WHERETRACE(("... best is rowid\n"));
1450 58 : return 0.0;
1451 0 : }else if( (pExpr = pTerm->pExpr)->pList!=0 ){
1452 : /* Rowid IN (LIST): cost is NlogN where N is the number of list
1453 : ** elements. */
1454 0 : lowestCost = pExpr->pList->nExpr;
1455 0 : lowestCost *= estLog(lowestCost);
1456 : }else{
1457 : /* Rowid IN (SELECT): cost is NlogN where N is the number of rows
1458 : ** in the result of the inner select. We have no way to estimate
1459 : ** that value so make a wild guess. */
1460 0 : lowestCost = 200;
1461 : }
1462 : WHERETRACE(("... rowid IN cost: %.9g\n", lowestCost));
1463 : }
1464 :
1465 : /* Estimate the cost of a table scan. If we do not know how many
1466 : ** entries are in the table, use 1 million as a guess.
1467 : */
1468 66 : cost = pProbe ? pProbe->aiRowEst[0] : 1000000;
1469 : WHERETRACE(("... table scan base cost: %.9g\n", cost));
1470 66 : flags = WHERE_ROWID_RANGE;
1471 :
1472 : /* Check for constraints on a range of rowids in a table scan.
1473 : */
1474 66 : pTerm = findTerm(pWC, iCur, -1, notReady, WO_LT|WO_LE|WO_GT|WO_GE, 0);
1475 66 : if( pTerm ){
1476 0 : if( findTerm(pWC, iCur, -1, notReady, WO_LT|WO_LE, 0) ){
1477 0 : flags |= WHERE_TOP_LIMIT;
1478 0 : cost /= 3; /* Guess that rowid<EXPR eliminates two-thirds or rows */
1479 : }
1480 0 : if( findTerm(pWC, iCur, -1, notReady, WO_GT|WO_GE, 0) ){
1481 0 : flags |= WHERE_BTM_LIMIT;
1482 0 : cost /= 3; /* Guess that rowid>EXPR eliminates two-thirds of rows */
1483 : }
1484 : WHERETRACE(("... rowid range reduces cost to %.9g\n", cost));
1485 : }else{
1486 66 : flags = 0;
1487 : }
1488 :
1489 : /* If the table scan does not satisfy the ORDER BY clause, increase
1490 : ** the cost by NlogN to cover the expense of sorting. */
1491 66 : if( pOrderBy ){
1492 4 : if( sortableByRowid(iCur, pOrderBy, pWC->pMaskSet, &rev) ){
1493 0 : flags |= WHERE_ORDERBY|WHERE_ROWID_RANGE;
1494 0 : if( rev ){
1495 0 : flags |= WHERE_REVERSE;
1496 : }
1497 : }else{
1498 4 : cost += cost*estLog(cost);
1499 : WHERETRACE(("... sorting increases cost to %.9g\n", cost));
1500 : }
1501 : }
1502 66 : if( cost<lowestCost ){
1503 66 : lowestCost = cost;
1504 66 : bestFlags = flags;
1505 : }
1506 :
1507 : /* If the pSrc table is the right table of a LEFT JOIN then we may not
1508 : ** use an index to satisfy IS NULL constraints on that table. This is
1509 : ** because columns might end up being NULL if the table does not match -
1510 : ** a circumstance which the index cannot help us discover. Ticket #2177.
1511 : */
1512 66 : if( (pSrc->jointype & JT_LEFT)!=0 ){
1513 5 : eqTermMask = WO_EQ|WO_IN;
1514 : }else{
1515 61 : eqTermMask = WO_EQ|WO_IN|WO_ISNULL;
1516 : }
1517 :
1518 : /* Look at each index.
1519 : */
1520 140 : for(; pProbe; pProbe=pProbe->pNext){
1521 : int i; /* Loop counter */
1522 74 : double inMultiplier = 1;
1523 :
1524 : WHERETRACE(("... index %s:\n", pProbe->zName));
1525 :
1526 : /* Count the number of columns in the index that are satisfied
1527 : ** by x=EXPR constraints or x IN (...) constraints.
1528 : */
1529 74 : flags = 0;
1530 83 : for(i=0; i<pProbe->nColumn; i++){
1531 74 : int j = pProbe->aiColumn[i];
1532 74 : pTerm = findTerm(pWC, iCur, j, notReady, eqTermMask, pProbe);
1533 74 : if( pTerm==0 ) break;
1534 9 : flags |= WHERE_COLUMN_EQ;
1535 9 : if( pTerm->eOperator & WO_IN ){
1536 0 : Expr *pExpr = pTerm->pExpr;
1537 0 : flags |= WHERE_COLUMN_IN;
1538 0 : if( pExpr->pSelect!=0 ){
1539 0 : inMultiplier *= 25;
1540 0 : }else if( pExpr->pList!=0 ){
1541 0 : inMultiplier *= pExpr->pList->nExpr + 1;
1542 : }
1543 : }
1544 : }
1545 74 : cost = pProbe->aiRowEst[i] * inMultiplier * estLog(inMultiplier);
1546 74 : nEq = i;
1547 74 : if( pProbe->onError!=OE_None && (flags & WHERE_COLUMN_IN)==0
1548 : && nEq==pProbe->nColumn ){
1549 9 : flags |= WHERE_UNIQUE;
1550 : }
1551 : WHERETRACE(("...... nEq=%d inMult=%.9g cost=%.9g\n", nEq, inMultiplier, cost));
1552 :
1553 : /* Look for range constraints
1554 : */
1555 74 : if( nEq<pProbe->nColumn ){
1556 65 : int j = pProbe->aiColumn[nEq];
1557 65 : pTerm = findTerm(pWC, iCur, j, notReady, WO_LT|WO_LE|WO_GT|WO_GE, pProbe);
1558 65 : if( pTerm ){
1559 0 : flags |= WHERE_COLUMN_RANGE;
1560 0 : if( findTerm(pWC, iCur, j, notReady, WO_LT|WO_LE, pProbe) ){
1561 0 : flags |= WHERE_TOP_LIMIT;
1562 0 : cost /= 3;
1563 : }
1564 0 : if( findTerm(pWC, iCur, j, notReady, WO_GT|WO_GE, pProbe) ){
1565 0 : flags |= WHERE_BTM_LIMIT;
1566 0 : cost /= 3;
1567 : }
1568 : WHERETRACE(("...... range reduces cost to %.9g\n", cost));
1569 : }
1570 : }
1571 :
1572 : /* Add the additional cost of sorting if that is a factor.
1573 : */
1574 74 : if( pOrderBy ){
1575 9 : if( (flags & WHERE_COLUMN_IN)==0 &&
1576 : isSortingIndex(pParse,pWC->pMaskSet,pProbe,iCur,pOrderBy,nEq,&rev) ){
1577 4 : if( flags==0 ){
1578 4 : flags = WHERE_COLUMN_RANGE;
1579 : }
1580 4 : flags |= WHERE_ORDERBY;
1581 4 : if( rev ){
1582 0 : flags |= WHERE_REVERSE;
1583 : }
1584 : }else{
1585 1 : cost += cost*estLog(cost);
1586 : WHERETRACE(("...... orderby increases cost to %.9g\n", cost));
1587 : }
1588 : }
1589 :
1590 : /* Check to see if we can get away with using just the index without
1591 : ** ever reading the table. If that is the case, then halve the
1592 : ** cost of this index.
1593 : */
1594 74 : if( flags && pSrc->colUsed < (((Bitmask)1)<<(BMS-1)) ){
1595 13 : Bitmask m = pSrc->colUsed;
1596 : int j;
1597 26 : for(j=0; j<pProbe->nColumn; j++){
1598 13 : int x = pProbe->aiColumn[j];
1599 13 : if( x<BMS-1 ){
1600 13 : m &= ~(((Bitmask)1)<<x);
1601 : }
1602 : }
1603 13 : if( m==0 ){
1604 2 : flags |= WHERE_IDX_ONLY;
1605 2 : cost /= 2;
1606 : WHERETRACE(("...... idx-only reduces cost to %.9g\n", cost));
1607 : }
1608 : }
1609 :
1610 : /* If this index has achieved the lowest cost so far, then use it.
1611 : */
1612 74 : if( cost < lowestCost ){
1613 13 : bestIdx = pProbe;
1614 13 : lowestCost = cost;
1615 : assert( flags!=0 );
1616 13 : bestFlags = flags;
1617 13 : bestNEq = nEq;
1618 : }
1619 : }
1620 :
1621 : /* Report the best result
1622 : */
1623 66 : *ppIndex = bestIdx;
1624 : WHERETRACE(("best index is %s, cost=%.9g, flags=%x, nEq=%d\n",
1625 : bestIdx ? bestIdx->zName : "(none)", lowestCost, bestFlags, bestNEq));
1626 66 : *pFlags = bestFlags | eqTermMask;
1627 66 : *pnEq = bestNEq;
1628 66 : return lowestCost;
1629 : }
1630 :
1631 :
1632 : /*
1633 : ** Disable a term in the WHERE clause. Except, do not disable the term
1634 : ** if it controls a LEFT OUTER JOIN and it did not originate in the ON
1635 : ** or USING clause of that join.
1636 : **
1637 : ** Consider the term t2.z='ok' in the following queries:
1638 : **
1639 : ** (1) SELECT * FROM t1 LEFT JOIN t2 ON t1.a=t2.x WHERE t2.z='ok'
1640 : ** (2) SELECT * FROM t1 LEFT JOIN t2 ON t1.a=t2.x AND t2.z='ok'
1641 : ** (3) SELECT * FROM t1, t2 WHERE t1.a=t2.x AND t2.z='ok'
1642 : **
1643 : ** The t2.z='ok' is disabled in the in (2) because it originates
1644 : ** in the ON clause. The term is disabled in (3) because it is not part
1645 : ** of a LEFT OUTER JOIN. In (1), the term is not disabled.
1646 : **
1647 : ** Disabling a term causes that term to not be tested in the inner loop
1648 : ** of the join. Disabling is an optimization. When terms are satisfied
1649 : ** by indices, we disable them to prevent redundant tests in the inner
1650 : ** loop. We would get the correct results if nothing were ever disabled,
1651 : ** but joins might run a little slower. The trick is to disable as much
1652 : ** as we can without disabling too much. If we disabled in (1), we'd get
1653 : ** the wrong answer. See ticket #813.
1654 : */
1655 72 : static void disableTerm(WhereLevel *pLevel, WhereTerm *pTerm){
1656 72 : if( pTerm
1657 : && (pTerm->flags & TERM_CODED)==0
1658 : && (pLevel->iLeftJoin==0 || ExprHasProperty(pTerm->pExpr, EP_FromJoin))
1659 : ){
1660 72 : pTerm->flags |= TERM_CODED;
1661 72 : if( pTerm->iParent>=0 ){
1662 5 : WhereTerm *pOther = &pTerm->pWC->a[pTerm->iParent];
1663 5 : if( (--pOther->nChild)==0 ){
1664 5 : disableTerm(pLevel, pOther);
1665 : }
1666 : }
1667 : }
1668 72 : }
1669 :
1670 : /*
1671 : ** Generate code that builds a probe for an index.
1672 : **
1673 : ** There should be nColumn values on the stack. The index
1674 : ** to be probed is pIdx. Pop the values from the stack and
1675 : ** replace them all with a single record that is the index
1676 : ** problem.
1677 : */
1678 : static void buildIndexProbe(
1679 : Vdbe *v, /* Generate code into this VM */
1680 : int nColumn, /* The number of columns to check for NULL */
1681 : Index *pIdx /* Index that we will be searching */
1682 9 : ){
1683 9 : sqlite3VdbeAddOp(v, OP_MakeRecord, nColumn, 0);
1684 9 : sqlite3IndexAffinityStr(v, pIdx);
1685 9 : }
1686 :
1687 :
1688 : /*
1689 : ** Generate code for a single equality term of the WHERE clause. An equality
1690 : ** term can be either X=expr or X IN (...). pTerm is the term to be
1691 : ** coded.
1692 : **
1693 : ** The current value for the constraint is left on the top of the stack.
1694 : **
1695 : ** For a constraint of the form X=expr, the expression is evaluated and its
1696 : ** result is left on the stack. For constraints of the form X IN (...)
1697 : ** this routine sets up a loop that will iterate over all values of X.
1698 : */
1699 : static void codeEqualityTerm(
1700 : Parse *pParse, /* The parsing context */
1701 : WhereTerm *pTerm, /* The term of the WHERE clause to be coded */
1702 : WhereLevel *pLevel /* When level of the FROM clause we are working on */
1703 67 : ){
1704 67 : Expr *pX = pTerm->pExpr;
1705 67 : Vdbe *v = pParse->pVdbe;
1706 67 : if( pX->op==TK_EQ ){
1707 67 : sqlite3ExprCode(pParse, pX->pRight);
1708 0 : }else if( pX->op==TK_ISNULL ){
1709 0 : sqlite3VdbeAddOp(v, OP_Null, 0, 0);
1710 : #ifndef SQLITE_OMIT_SUBQUERY
1711 : }else{
1712 : int iTab;
1713 : struct InLoop *pIn;
1714 :
1715 : assert( pX->op==TK_IN );
1716 0 : sqlite3CodeSubselect(pParse, pX);
1717 0 : iTab = pX->iTable;
1718 0 : sqlite3VdbeAddOp(v, OP_Rewind, iTab, 0);
1719 : VdbeComment((v, "# %.*s", pX->span.n, pX->span.z));
1720 0 : if( pLevel->nIn==0 ){
1721 0 : pLevel->nxt = sqlite3VdbeMakeLabel(v);
1722 : }
1723 0 : pLevel->nIn++;
1724 0 : pLevel->aInLoop = sqliteReallocOrFree(pLevel->aInLoop,
1725 : sizeof(pLevel->aInLoop[0])*pLevel->nIn);
1726 0 : pIn = pLevel->aInLoop;
1727 0 : if( pIn ){
1728 0 : pIn += pLevel->nIn - 1;
1729 0 : pIn->iCur = iTab;
1730 0 : pIn->topAddr = sqlite3VdbeAddOp(v, OP_Column, iTab, 0);
1731 0 : sqlite3VdbeAddOp(v, OP_IsNull, -1, 0);
1732 : }else{
1733 0 : pLevel->nIn = 0;
1734 : }
1735 : #endif
1736 : }
1737 67 : disableTerm(pLevel, pTerm);
1738 67 : }
1739 :
1740 : /*
1741 : ** Generate code that will evaluate all == and IN constraints for an
1742 : ** index. The values for all constraints are left on the stack.
1743 : **
1744 : ** For example, consider table t1(a,b,c,d,e,f) with index i1(a,b,c).
1745 : ** Suppose the WHERE clause is this: a==5 AND b IN (1,2,3) AND c>5 AND c<10
1746 : ** The index has as many as three equality constraints, but in this
1747 : ** example, the third "c" value is an inequality. So only two
1748 : ** constraints are coded. This routine will generate code to evaluate
1749 : ** a==5 and b IN (1,2,3). The current values for a and b will be left
1750 : ** on the stack - a is the deepest and b the shallowest.
1751 : **
1752 : ** In the example above nEq==2. But this subroutine works for any value
1753 : ** of nEq including 0. If nEq==0, this routine is nearly a no-op.
1754 : ** The only thing it does is allocate the pLevel->iMem memory cell.
1755 : **
1756 : ** This routine always allocates at least one memory cell and puts
1757 : ** the address of that memory cell in pLevel->iMem. The code that
1758 : ** calls this routine will use pLevel->iMem to store the termination
1759 : ** key value of the loop. If one or more IN operators appear, then
1760 : ** this routine allocates an additional nEq memory cells for internal
1761 : ** use.
1762 : */
1763 : static void codeAllEqualityTerms(
1764 : Parse *pParse, /* Parsing context */
1765 : WhereLevel *pLevel, /* Which nested loop of the FROM we are coding */
1766 : WhereClause *pWC, /* The WHERE clause */
1767 : Bitmask notReady /* Which parts of FROM have not yet been coded */
1768 13 : ){
1769 13 : int nEq = pLevel->nEq; /* The number of == or IN constraints to code */
1770 13 : int termsInMem = 0; /* If true, store value in mem[] cells */
1771 13 : Vdbe *v = pParse->pVdbe; /* The virtual machine under construction */
1772 13 : Index *pIdx = pLevel->pIdx; /* The index being used for this loop */
1773 13 : int iCur = pLevel->iTabCur; /* The cursor of the table */
1774 : WhereTerm *pTerm; /* A single constraint term */
1775 : int j; /* Loop counter */
1776 :
1777 : /* Figure out how many memory cells we will need then allocate them.
1778 : ** We always need at least one used to store the loop terminator
1779 : ** value. If there are IN operators we'll need one for each == or
1780 : ** IN constraint.
1781 : */
1782 13 : pLevel->iMem = pParse->nMem++;
1783 13 : if( pLevel->flags & WHERE_COLUMN_IN ){
1784 0 : pParse->nMem += pLevel->nEq;
1785 0 : termsInMem = 1;
1786 : }
1787 :
1788 : /* Evaluate the equality constraints
1789 : */
1790 : assert( pIdx->nColumn>=nEq );
1791 22 : for(j=0; j<nEq; j++){
1792 9 : int k = pIdx->aiColumn[j];
1793 9 : pTerm = findTerm(pWC, iCur, k, notReady, pLevel->flags, pIdx);
1794 9 : if( pTerm==0 ) break;
1795 : assert( (pTerm->flags & TERM_CODED)==0 );
1796 9 : codeEqualityTerm(pParse, pTerm, pLevel);
1797 9 : if( (pTerm->eOperator & (WO_ISNULL|WO_IN))==0 ){
1798 9 : sqlite3VdbeAddOp(v, OP_IsNull, termsInMem ? -1 : -(j+1), pLevel->brk);
1799 : }
1800 9 : if( termsInMem ){
1801 0 : sqlite3VdbeAddOp(v, OP_MemStore, pLevel->iMem+j+1, 1);
1802 : }
1803 : }
1804 :
1805 : /* Make sure all the constraint values are on the top of the stack
1806 : */
1807 13 : if( termsInMem ){
1808 0 : for(j=0; j<nEq; j++){
1809 0 : sqlite3VdbeAddOp(v, OP_MemLoad, pLevel->iMem+j+1, 0);
1810 : }
1811 : }
1812 13 : }
1813 :
1814 : #if defined(SQLITE_TEST)
1815 : /*
1816 : ** The following variable holds a text description of query plan generated
1817 : ** by the most recent call to sqlite3WhereBegin(). Each call to WhereBegin
1818 : ** overwrites the previous. This information is used for testing and
1819 : ** analysis only.
1820 : */
1821 : char sqlite3_query_plan[BMS*2*40]; /* Text of the join */
1822 : static int nQPlan = 0; /* Next free slow in _query_plan[] */
1823 :
1824 : #endif /* SQLITE_TEST */
1825 :
1826 :
1827 : /*
1828 : ** Free a WhereInfo structure
1829 : */
1830 221 : static void whereInfoFree(WhereInfo *pWInfo){
1831 221 : if( pWInfo ){
1832 : int i;
1833 438 : for(i=0; i<pWInfo->nLevel; i++){
1834 217 : sqlite3_index_info *pInfo = pWInfo->a[i].pIdxInfo;
1835 217 : if( pInfo ){
1836 0 : if( pInfo->needToFreeIdxStr ){
1837 : /* Coverage: Don't think this can be reached. By the time this
1838 : ** function is called, the index-strings have been passed
1839 : ** to the vdbe layer for deletion.
1840 : */
1841 0 : sqlite3_free(pInfo->idxStr);
1842 : }
1843 0 : sqliteFree(pInfo);
1844 : }
1845 : }
1846 221 : sqliteFree(pWInfo);
1847 : }
1848 221 : }
1849 :
1850 :
1851 : /*
1852 : ** Generate the beginning of the loop used for WHERE clause processing.
1853 : ** The return value is a pointer to an opaque structure that contains
1854 : ** information needed to terminate the loop. Later, the calling routine
1855 : ** should invoke sqlite3WhereEnd() with the return value of this function
1856 : ** in order to complete the WHERE clause processing.
1857 : **
1858 : ** If an error occurs, this routine returns NULL.
1859 : **
1860 : ** The basic idea is to do a nested loop, one loop for each table in
1861 : ** the FROM clause of a select. (INSERT and UPDATE statements are the
1862 : ** same as a SELECT with only a single table in the FROM clause.) For
1863 : ** example, if the SQL is this:
1864 : **
1865 : ** SELECT * FROM t1, t2, t3 WHERE ...;
1866 : **
1867 : ** Then the code generated is conceptually like the following:
1868 : **
1869 : ** foreach row1 in t1 do \ Code generated
1870 : ** foreach row2 in t2 do |-- by sqlite3WhereBegin()
1871 : ** foreach row3 in t3 do /
1872 : ** ...
1873 : ** end \ Code generated
1874 : ** end |-- by sqlite3WhereEnd()
1875 : ** end /
1876 : **
1877 : ** Note that the loops might not be nested in the order in which they
1878 : ** appear in the FROM clause if a different order is better able to make
1879 : ** use of indices. Note also that when the IN operator appears in
1880 : ** the WHERE clause, it might result in additional nested loops for
1881 : ** scanning through all values on the right-hand side of the IN.
1882 : **
1883 : ** There are Btree cursors associated with each table. t1 uses cursor
1884 : ** number pTabList->a[0].iCursor. t2 uses the cursor pTabList->a[1].iCursor.
1885 : ** And so forth. This routine generates code to open those VDBE cursors
1886 : ** and sqlite3WhereEnd() generates the code to close them.
1887 : **
1888 : ** The code that sqlite3WhereBegin() generates leaves the cursors named
1889 : ** in pTabList pointing at their appropriate entries. The [...] code
1890 : ** can use OP_Column and OP_Rowid opcodes on these cursors to extract
1891 : ** data from the various tables of the loop.
1892 : **
1893 : ** If the WHERE clause is empty, the foreach loops must each scan their
1894 : ** entire tables. Thus a three-way join is an O(N^3) operation. But if
1895 : ** the tables have indices and there are terms in the WHERE clause that
1896 : ** refer to those indices, a complete table scan can be avoided and the
1897 : ** code will run much faster. Most of the work of this routine is checking
1898 : ** to see if there are indices that can be used to speed up the loop.
1899 : **
1900 : ** Terms of the WHERE clause are also used to limit which rows actually
1901 : ** make it to the "..." in the middle of the loop. After each "foreach",
1902 : ** terms of the WHERE clause that use only terms in that loop and outer
1903 : ** loops are evaluated and if false a jump is made around all subsequent
1904 : ** inner loops (or around the "..." if the test occurs within the inner-
1905 : ** most loop)
1906 : **
1907 : ** OUTER JOINS
1908 : **
1909 : ** An outer join of tables t1 and t2 is conceptally coded as follows:
1910 : **
1911 : ** foreach row1 in t1 do
1912 : ** flag = 0
1913 : ** foreach row2 in t2 do
1914 : ** start:
1915 : ** ...
1916 : ** flag = 1
1917 : ** end
1918 : ** if flag==0 then
1919 : ** move the row2 cursor to a null row
1920 : ** goto start
1921 : ** fi
1922 : ** end
1923 : **
1924 : ** ORDER BY CLAUSE PROCESSING
1925 : **
1926 : ** *ppOrderBy is a pointer to the ORDER BY clause of a SELECT statement,
1927 : ** if there is one. If there is no ORDER BY clause or if this routine
1928 : ** is called from an UPDATE or DELETE statement, then ppOrderBy is NULL.
1929 : **
1930 : ** If an index can be used so that the natural output order of the table
1931 : ** scan is correct for the ORDER BY clause, then that index is used and
1932 : ** *ppOrderBy is set to NULL. This is an optimization that prevents an
1933 : ** unnecessary sort of the result set if an index appropriate for the
1934 : ** ORDER BY clause already exists.
1935 : **
1936 : ** If the where clause loops cannot be arranged to provide the correct
1937 : ** output order, then the *ppOrderBy is unchanged.
1938 : */
1939 : WhereInfo *sqlite3WhereBegin(
1940 : Parse *pParse, /* The parser context */
1941 : SrcList *pTabList, /* A list of all tables to be scanned */
1942 : Expr *pWhere, /* The WHERE clause */
1943 : ExprList **ppOrderBy /* An ORDER BY clause, or NULL */
1944 221 : ){
1945 : int i; /* Loop counter */
1946 : WhereInfo *pWInfo; /* Will become the return value of this function */
1947 221 : Vdbe *v = pParse->pVdbe; /* The virtual database engine */
1948 221 : int brk, cont = 0; /* Addresses used during code generation */
1949 : Bitmask notReady; /* Cursors that are not yet positioned */
1950 : WhereTerm *pTerm; /* A single term in the WHERE clause */
1951 : ExprMaskSet maskSet; /* The expression mask set */
1952 : WhereClause wc; /* The WHERE clause is divided into these terms */
1953 : struct SrcList_item *pTabItem; /* A single entry from pTabList */
1954 : WhereLevel *pLevel; /* A single level in the pWInfo list */
1955 : int iFrom; /* First unused FROM clause element */
1956 : int andFlags; /* AND-ed combination of all wc.a[].flags */
1957 :
1958 : /* The number of tables in the FROM clause is limited by the number of
1959 : ** bits in a Bitmask
1960 : */
1961 221 : if( pTabList->nSrc>BMS ){
1962 0 : sqlite3ErrorMsg(pParse, "at most %d tables in a join", BMS);
1963 0 : return 0;
1964 : }
1965 :
1966 : /* Split the WHERE clause into separate subexpressions where each
1967 : ** subexpression is separated by an AND operator.
1968 : */
1969 221 : initMaskSet(&maskSet);
1970 221 : whereClauseInit(&wc, pParse, &maskSet);
1971 221 : whereSplit(&wc, pWhere, TK_AND);
1972 :
1973 : /* Allocate and initialize the WhereInfo structure that will become the
1974 : ** return value.
1975 : */
1976 221 : pWInfo = sqliteMalloc( sizeof(WhereInfo) + pTabList->nSrc*sizeof(WhereLevel));
1977 221 : if( sqlite3MallocFailed() ){
1978 0 : goto whereBeginNoMem;
1979 : }
1980 221 : pWInfo->nLevel = pTabList->nSrc;
1981 221 : pWInfo->pParse = pParse;
1982 221 : pWInfo->pTabList = pTabList;
1983 221 : pWInfo->iBreak = sqlite3VdbeMakeLabel(v);
1984 :
1985 : /* Special case: a WHERE clause that is constant. Evaluate the
1986 : ** expression and either jump over all of the code or fall thru.
1987 : */
1988 221 : if( pWhere && (pTabList->nSrc==0 || sqlite3ExprIsConstant(pWhere)) ){
1989 0 : sqlite3ExprIfFalse(pParse, pWhere, pWInfo->iBreak, 1);
1990 0 : pWhere = 0;
1991 : }
1992 :
1993 : /* Analyze all of the subexpressions. Note that exprAnalyze() might
1994 : ** add new virtual terms onto the end of the WHERE clause. We do not
1995 : ** want to analyze these virtual terms, so start analyzing at the end
1996 : ** and work forward so that the added virtual terms are never processed.
1997 : */
1998 438 : for(i=0; i<pTabList->nSrc; i++){
1999 217 : createMask(&maskSet, pTabList->a[i].iCursor);
2000 : }
2001 221 : exprAnalyzeAll(pTabList, &wc);
2002 221 : if( sqlite3MallocFailed() ){
2003 0 : goto whereBeginNoMem;
2004 : }
2005 :
2006 : /* Chose the best index to use for each table in the FROM clause.
2007 : **
2008 : ** This loop fills in the following fields:
2009 : **
2010 : ** pWInfo->a[].pIdx The index to use for this level of the loop.
2011 : ** pWInfo->a[].flags WHERE_xxx flags associated with pIdx
2012 : ** pWInfo->a[].nEq The number of == and IN constraints
2013 : ** pWInfo->a[].iFrom When term of the FROM clause is being coded
2014 : ** pWInfo->a[].iTabCur The VDBE cursor for the database table
2015 : ** pWInfo->a[].iIdxCur The VDBE cursor for the index
2016 : **
2017 : ** This loop also figures out the nesting order of tables in the FROM
2018 : ** clause.
2019 : */
2020 221 : notReady = ~(Bitmask)0;
2021 221 : pTabItem = pTabList->a;
2022 221 : pLevel = pWInfo->a;
2023 221 : andFlags = ~0;
2024 : WHERETRACE(("*** Optimizer Start ***\n"));
2025 438 : for(i=iFrom=0, pLevel=pWInfo->a; i<pTabList->nSrc; i++, pLevel++){
2026 : Index *pIdx; /* Index for FROM table at pTabItem */
2027 : int flags; /* Flags asssociated with pIdx */
2028 : int nEq; /* Number of == or IN constraints */
2029 : double cost; /* The cost for pIdx */
2030 : int j; /* For looping over FROM tables */
2031 217 : Index *pBest = 0; /* The best index seen so far */
2032 217 : int bestFlags = 0; /* Flags associated with pBest */
2033 217 : int bestNEq = 0; /* nEq associated with pBest */
2034 : double lowestCost; /* Cost of the pBest */
2035 217 : int bestJ = 0; /* The value of j */
2036 : Bitmask m; /* Bitmask value for j or bestJ */
2037 217 : int once = 0; /* True when first table is seen */
2038 : sqlite3_index_info *pIndex; /* Current virtual index */
2039 :
2040 217 : lowestCost = SQLITE_BIG_DBL;
2041 434 : for(j=iFrom, pTabItem=&pTabList->a[j]; j<pTabList->nSrc; j++, pTabItem++){
2042 : int doNotReorder; /* True if this table should not be reordered */
2043 :
2044 227 : doNotReorder = (pTabItem->jointype & (JT_LEFT|JT_CROSS))!=0;
2045 227 : if( once && doNotReorder ) break;
2046 222 : m = getMask(&maskSet, pTabItem->iCursor);
2047 222 : if( (m & notReady)==0 ){
2048 5 : if( j==iFrom ) iFrom++;
2049 5 : continue;
2050 : }
2051 : assert( pTabItem->pTab );
2052 : #ifndef SQLITE_OMIT_VIRTUALTABLE
2053 217 : if( IsVirtual(pTabItem->pTab) ){
2054 0 : sqlite3_index_info **ppIdxInfo = &pWInfo->a[j].pIdxInfo;
2055 0 : cost = bestVirtualIndex(pParse, &wc, pTabItem, notReady,
2056 : ppOrderBy ? *ppOrderBy : 0, i==0,
2057 : ppIdxInfo);
2058 0 : flags = WHERE_VIRTUALTABLE;
2059 0 : pIndex = *ppIdxInfo;
2060 0 : if( pIndex && pIndex->orderByConsumed ){
2061 0 : flags = WHERE_VIRTUALTABLE | WHERE_ORDERBY;
2062 : }
2063 0 : pIdx = 0;
2064 0 : nEq = 0;
2065 0 : if( (SQLITE_BIG_DBL/2.0)<cost ){
2066 : /* The cost is not allowed to be larger than SQLITE_BIG_DBL (the
2067 : ** inital value of lowestCost in this loop. If it is, then
2068 : ** the (cost<lowestCost) test below will never be true and
2069 : ** pLevel->pBestIdx never set.
2070 : */
2071 0 : cost = (SQLITE_BIG_DBL/2.0);
2072 : }
2073 : }else
2074 : #endif
2075 : {
2076 217 : cost = bestIndex(pParse, &wc, pTabItem, notReady,
2077 : (i==0 && ppOrderBy) ? *ppOrderBy : 0,
2078 : &pIdx, &flags, &nEq);
2079 217 : pIndex = 0;
2080 : }
2081 217 : if( cost<lowestCost ){
2082 217 : once = 1;
2083 217 : lowestCost = cost;
2084 217 : pBest = pIdx;
2085 217 : bestFlags = flags;
2086 217 : bestNEq = nEq;
2087 217 : bestJ = j;
2088 217 : pLevel->pBestIdx = pIndex;
2089 : }
2090 217 : if( doNotReorder ) break;
2091 : }
2092 : WHERETRACE(("*** Optimizer choose table %d for loop %d\n", bestJ,
2093 : pLevel-pWInfo->a));
2094 217 : if( (bestFlags & WHERE_ORDERBY)!=0 ){
2095 4 : *ppOrderBy = 0;
2096 : }
2097 217 : andFlags &= bestFlags;
2098 217 : pLevel->flags = bestFlags;
2099 217 : pLevel->pIdx = pBest;
2100 217 : pLevel->nEq = bestNEq;
2101 217 : pLevel->aInLoop = 0;
2102 217 : pLevel->nIn = 0;
2103 217 : if( pBest ){
2104 13 : pLevel->iIdxCur = pParse->nTab++;
2105 : }else{
2106 204 : pLevel->iIdxCur = -1;
2107 : }
2108 217 : notReady &= ~getMask(&maskSet, pTabList->a[bestJ].iCursor);
2109 217 : pLevel->iFrom = bestJ;
2110 : }
2111 : WHERETRACE(("*** Optimizer Finished ***\n"));
2112 :
2113 : /* If the total query only selects a single row, then the ORDER BY
2114 : ** clause is irrelevant.
2115 : */
2116 221 : if( (andFlags & WHERE_UNIQUE)!=0 && ppOrderBy ){
2117 14 : *ppOrderBy = 0;
2118 : }
2119 :
2120 : /* Open all tables in the pTabList and any indices selected for
2121 : ** searching those tables.
2122 : */
2123 221 : sqlite3CodeVerifySchema(pParse, -1); /* Insert the cookie verifier Goto */
2124 438 : for(i=0, pLevel=pWInfo->a; i<pTabList->nSrc; i++, pLevel++){
2125 : Table *pTab; /* Table to open */
2126 : Index *pIx; /* Index used to access pTab (if any) */
2127 : int iDb; /* Index of database containing table/index */
2128 217 : int iIdxCur = pLevel->iIdxCur;
2129 :
2130 : #ifndef SQLITE_OMIT_EXPLAIN
2131 217 : if( pParse->explain==2 ){
2132 : char *zMsg;
2133 0 : struct SrcList_item *pItem = &pTabList->a[pLevel->iFrom];
2134 0 : zMsg = sqlite3MPrintf("TABLE %s", pItem->zName);
2135 0 : if( pItem->zAlias ){
2136 0 : zMsg = sqlite3MPrintf("%z AS %s", zMsg, pItem->zAlias);
2137 : }
2138 0 : if( (pIx = pLevel->pIdx)!=0 ){
2139 0 : zMsg = sqlite3MPrintf("%z WITH INDEX %s", zMsg, pIx->zName);
2140 0 : }else if( pLevel->flags & (WHERE_ROWID_EQ|WHERE_ROWID_RANGE) ){
2141 0 : zMsg = sqlite3MPrintf("%z USING PRIMARY KEY", zMsg);
2142 : }
2143 : #ifndef SQLITE_OMIT_VIRTUALTABLE
2144 0 : else if( pLevel->pBestIdx ){
2145 0 : sqlite3_index_info *pBestIdx = pLevel->pBestIdx;
2146 0 : zMsg = sqlite3MPrintf("%z VIRTUAL TABLE INDEX %d:%s", zMsg,
2147 : pBestIdx->idxNum, pBestIdx->idxStr);
2148 : }
2149 : #endif
2150 0 : if( pLevel->flags & WHERE_ORDERBY ){
2151 0 : zMsg = sqlite3MPrintf("%z ORDER BY", zMsg);
2152 : }
2153 0 : sqlite3VdbeOp3(v, OP_Explain, i, pLevel->iFrom, zMsg, P3_DYNAMIC);
2154 : }
2155 : #endif /* SQLITE_OMIT_EXPLAIN */
2156 217 : pTabItem = &pTabList->a[pLevel->iFrom];
2157 217 : pTab = pTabItem->pTab;
2158 217 : iDb = sqlite3SchemaToIndex(pParse->db, pTab->pSchema);
2159 217 : if( pTab->isEphem || pTab->pSelect ) continue;
2160 : #ifndef SQLITE_OMIT_VIRTUALTABLE
2161 217 : if( pLevel->pBestIdx ){
2162 0 : int iCur = pTabItem->iCursor;
2163 0 : sqlite3VdbeOp3(v, OP_VOpen, iCur, 0, (const char*)pTab->pVtab, P3_VTAB);
2164 : }else
2165 : #endif
2166 217 : if( (pLevel->flags & WHERE_IDX_ONLY)==0 ){
2167 215 : sqlite3OpenTable(pParse, pTabItem->iCursor, iDb, pTab, OP_OpenRead);
2168 215 : if( pTab->nCol<(sizeof(Bitmask)*8) ){
2169 215 : Bitmask b = pTabItem->colUsed;
2170 215 : int n = 0;
2171 215 : for(; b; b=b>>1, n++){}
2172 215 : sqlite3VdbeChangeP2(v, sqlite3VdbeCurrentAddr(v)-1, n);
2173 : assert( n<=pTab->nCol );
2174 : }
2175 : }else{
2176 2 : sqlite3TableLock(pParse, iDb, pTab->tnum, 0, pTab->zName);
2177 : }
2178 217 : pLevel->iTabCur = pTabItem->iCursor;
2179 217 : if( (pIx = pLevel->pIdx)!=0 ){
2180 13 : KeyInfo *pKey = sqlite3IndexKeyinfo(pParse, pIx);
2181 : assert( pIx->pSchema==pTab->pSchema );
2182 13 : sqlite3VdbeAddOp(v, OP_Integer, iDb, 0);
2183 : VdbeComment((v, "# %s", pIx->zName));
2184 13 : sqlite3VdbeOp3(v, OP_OpenRead, iIdxCur, pIx->tnum,
2185 : (char*)pKey, P3_KEYINFO_HANDOFF);
2186 : }
2187 217 : if( (pLevel->flags & (WHERE_IDX_ONLY|WHERE_COLUMN_RANGE))!=0 ){
2188 : /* Only call OP_SetNumColumns on the index if we might later use
2189 : ** OP_Column on the index. */
2190 6 : sqlite3VdbeAddOp(v, OP_SetNumColumns, iIdxCur, pIx->nColumn+1);
2191 : }
2192 217 : sqlite3CodeVerifySchema(pParse, iDb);
2193 : }
2194 221 : pWInfo->iTop = sqlite3VdbeCurrentAddr(v);
2195 :
2196 : /* Generate the code to do the search. Each iteration of the for
2197 : ** loop below generates code for a single nested loop of the VM
2198 : ** program.
2199 : */
2200 221 : notReady = ~(Bitmask)0;
2201 438 : for(i=0, pLevel=pWInfo->a; i<pTabList->nSrc; i++, pLevel++){
2202 : int j;
2203 217 : int iCur = pTabItem->iCursor; /* The VDBE cursor for the table */
2204 : Index *pIdx; /* The index we will be using */
2205 : int nxt; /* Where to jump to continue with the next IN case */
2206 : int iIdxCur; /* The VDBE cursor for the index */
2207 : int omitTable; /* True if we use the index only */
2208 : int bRev; /* True if we need to scan in reverse order */
2209 :
2210 217 : pTabItem = &pTabList->a[pLevel->iFrom];
2211 217 : iCur = pTabItem->iCursor;
2212 217 : pIdx = pLevel->pIdx;
2213 217 : iIdxCur = pLevel->iIdxCur;
2214 217 : bRev = (pLevel->flags & WHERE_REVERSE)!=0;
2215 217 : omitTable = (pLevel->flags & WHERE_IDX_ONLY)!=0;
2216 :
2217 : /* Create labels for the "break" and "continue" instructions
2218 : ** for the current loop. Jump to brk to break out of a loop.
2219 : ** Jump to cont to go immediately to the next iteration of the
2220 : ** loop.
2221 : **
2222 : ** When there is an IN operator, we also have a "nxt" label that
2223 : ** means to continue with the next IN value combination. When
2224 : ** there are no IN operators in the constraints, the "nxt" label
2225 : ** is the same as "brk".
2226 : */
2227 217 : brk = pLevel->brk = pLevel->nxt = sqlite3VdbeMakeLabel(v);
2228 217 : cont = pLevel->cont = sqlite3VdbeMakeLabel(v);
2229 :
2230 : /* If this is the right table of a LEFT OUTER JOIN, allocate and
2231 : ** initialize a memory cell that records if this table matches any
2232 : ** row of the left table of the join.
2233 : */
2234 217 : if( pLevel->iFrom>0 && (pTabItem[0].jointype & JT_LEFT)!=0 ){
2235 5 : if( !pParse->nMem ) pParse->nMem++;
2236 5 : pLevel->iLeftJoin = pParse->nMem++;
2237 5 : sqlite3VdbeAddOp(v, OP_MemInt, 0, pLevel->iLeftJoin);
2238 : VdbeComment((v, "# init LEFT JOIN no-match flag"));
2239 : }
2240 :
2241 : #ifndef SQLITE_OMIT_VIRTUALTABLE
2242 217 : if( pLevel->pBestIdx ){
2243 : /* Case 0: The table is a virtual-table. Use the VFilter and VNext
2244 : ** to access the data.
2245 : */
2246 : int j;
2247 0 : sqlite3_index_info *pBestIdx = pLevel->pBestIdx;
2248 0 : int nConstraint = pBestIdx->nConstraint;
2249 : struct sqlite3_index_constraint_usage *aUsage =
2250 0 : pBestIdx->aConstraintUsage;
2251 : const struct sqlite3_index_constraint *aConstraint =
2252 0 : pBestIdx->aConstraint;
2253 :
2254 0 : for(j=1; j<=nConstraint; j++){
2255 : int k;
2256 0 : for(k=0; k<nConstraint; k++){
2257 0 : if( aUsage[k].argvIndex==j ){
2258 0 : int iTerm = aConstraint[k].iTermOffset;
2259 0 : sqlite3ExprCode(pParse, wc.a[iTerm].pExpr->pRight);
2260 0 : break;
2261 : }
2262 : }
2263 0 : if( k==nConstraint ) break;
2264 : }
2265 0 : sqlite3VdbeAddOp(v, OP_Integer, j-1, 0);
2266 0 : sqlite3VdbeAddOp(v, OP_Integer, pBestIdx->idxNum, 0);
2267 0 : sqlite3VdbeOp3(v, OP_VFilter, iCur, brk, pBestIdx->idxStr,
2268 : pBestIdx->needToFreeIdxStr ? P3_MPRINTF : P3_STATIC);
2269 0 : pBestIdx->needToFreeIdxStr = 0;
2270 0 : for(j=0; j<pBestIdx->nConstraint; j++){
2271 0 : if( aUsage[j].omit ){
2272 0 : int iTerm = aConstraint[j].iTermOffset;
2273 0 : disableTerm(pLevel, &wc.a[iTerm]);
2274 : }
2275 : }
2276 0 : pLevel->op = OP_VNext;
2277 0 : pLevel->p1 = iCur;
2278 0 : pLevel->p2 = sqlite3VdbeCurrentAddr(v);
2279 : }else
2280 : #endif /* SQLITE_OMIT_VIRTUALTABLE */
2281 :
2282 217 : if( pLevel->flags & WHERE_ROWID_EQ ){
2283 : /* Case 1: We can directly reference a single row using an
2284 : ** equality comparison against the ROWID field. Or
2285 : ** we reference multiple rows using a "rowid IN (...)"
2286 : ** construct.
2287 : */
2288 58 : pTerm = findTerm(&wc, iCur, -1, notReady, WO_EQ|WO_IN, 0);
2289 : assert( pTerm!=0 );
2290 : assert( pTerm->pExpr!=0 );
2291 : assert( pTerm->leftCursor==iCur );
2292 : assert( omitTable==0 );
2293 58 : codeEqualityTerm(pParse, pTerm, pLevel);
2294 58 : nxt = pLevel->nxt;
2295 58 : sqlite3VdbeAddOp(v, OP_MustBeInt, 1, nxt);
2296 58 : sqlite3VdbeAddOp(v, OP_NotExists, iCur, nxt);
2297 : VdbeComment((v, "pk"));
2298 58 : pLevel->op = OP_Noop;
2299 159 : }else if( pLevel->flags & WHERE_ROWID_RANGE ){
2300 : /* Case 2: We have an inequality comparison against the ROWID field.
2301 : */
2302 0 : int testOp = OP_Noop;
2303 : int start;
2304 : WhereTerm *pStart, *pEnd;
2305 :
2306 : assert( omitTable==0 );
2307 0 : pStart = findTerm(&wc, iCur, -1, notReady, WO_GT|WO_GE, 0);
2308 0 : pEnd = findTerm(&wc, iCur, -1, notReady, WO_LT|WO_LE, 0);
2309 0 : if( bRev ){
2310 0 : pTerm = pStart;
2311 0 : pStart = pEnd;
2312 0 : pEnd = pTerm;
2313 : }
2314 0 : if( pStart ){
2315 : Expr *pX;
2316 0 : pX = pStart->pExpr;
2317 : assert( pX!=0 );
2318 : assert( pStart->leftCursor==iCur );
2319 0 : sqlite3ExprCode(pParse, pX->pRight);
2320 0 : sqlite3VdbeAddOp(v, OP_ForceInt, pX->op==TK_LE || pX->op==TK_GT, brk);
2321 0 : sqlite3VdbeAddOp(v, bRev ? OP_MoveLt : OP_MoveGe, iCur, brk);
2322 : VdbeComment((v, "pk"));
2323 0 : disableTerm(pLevel, pStart);
2324 : }else{
2325 0 : sqlite3VdbeAddOp(v, bRev ? OP_Last : OP_Rewind, iCur, brk);
2326 : }
2327 0 : if( pEnd ){
2328 : Expr *pX;
2329 0 : pX = pEnd->pExpr;
2330 : assert( pX!=0 );
2331 : assert( pEnd->leftCursor==iCur );
2332 0 : sqlite3ExprCode(pParse, pX->pRight);
2333 0 : pLevel->iMem = pParse->nMem++;
2334 0 : sqlite3VdbeAddOp(v, OP_MemStore, pLevel->iMem, 1);
2335 0 : if( pX->op==TK_LT || pX->op==TK_GT ){
2336 0 : testOp = bRev ? OP_Le : OP_Ge;
2337 : }else{
2338 0 : testOp = bRev ? OP_Lt : OP_Gt;
2339 : }
2340 0 : disableTerm(pLevel, pEnd);
2341 : }
2342 0 : start = sqlite3VdbeCurrentAddr(v);
2343 0 : pLevel->op = bRev ? OP_Prev : OP_Next;
2344 0 : pLevel->p1 = iCur;
2345 0 : pLevel->p2 = start;
2346 0 : if( testOp!=OP_Noop ){
2347 0 : sqlite3VdbeAddOp(v, OP_Rowid, iCur, 0);
2348 0 : sqlite3VdbeAddOp(v, OP_MemLoad, pLevel->iMem, 0);
2349 0 : sqlite3VdbeAddOp(v, testOp, SQLITE_AFF_NUMERIC, brk);
2350 : }
2351 159 : }else if( pLevel->flags & WHERE_COLUMN_RANGE ){
2352 : /* Case 3: The WHERE clause term that refers to the right-most
2353 : ** column of the index is an inequality. For example, if
2354 : ** the index is on (x,y,z) and the WHERE clause is of the
2355 : ** form "x=5 AND y<10" then this case is used. Only the
2356 : ** right-most column can be an inequality - the rest must
2357 : ** use the "==" and "IN" operators.
2358 : **
2359 : ** This case is also used when there are no WHERE clause
2360 : ** constraints but an index is selected anyway, in order
2361 : ** to force the output order to conform to an ORDER BY.
2362 : */
2363 : int start;
2364 4 : int nEq = pLevel->nEq;
2365 4 : int topEq=0; /* True if top limit uses ==. False is strictly < */
2366 4 : int btmEq=0; /* True if btm limit uses ==. False if strictly > */
2367 : int topOp, btmOp; /* Operators for the top and bottom search bounds */
2368 : int testOp;
2369 4 : int topLimit = (pLevel->flags & WHERE_TOP_LIMIT)!=0;
2370 4 : int btmLimit = (pLevel->flags & WHERE_BTM_LIMIT)!=0;
2371 :
2372 : /* Generate code to evaluate all constraint terms using == or IN
2373 : ** and level the values of those terms on the stack.
2374 : */
2375 4 : codeAllEqualityTerms(pParse, pLevel, &wc, notReady);
2376 :
2377 : /* Duplicate the equality term values because they will all be
2378 : ** used twice: once to make the termination key and once to make the
2379 : ** start key.
2380 : */
2381 4 : for(j=0; j<nEq; j++){
2382 0 : sqlite3VdbeAddOp(v, OP_Dup, nEq-1, 0);
2383 : }
2384 :
2385 : /* Figure out what comparison operators to use for top and bottom
2386 : ** search bounds. For an ascending index, the bottom bound is a > or >=
2387 : ** operator and the top bound is a < or <= operator. For a descending
2388 : ** index the operators are reversed.
2389 : */
2390 4 : if( pIdx->aSortOrder[nEq]==SQLITE_SO_ASC ){
2391 4 : topOp = WO_LT|WO_LE;
2392 4 : btmOp = WO_GT|WO_GE;
2393 : }else{
2394 0 : topOp = WO_GT|WO_GE;
2395 0 : btmOp = WO_LT|WO_LE;
2396 0 : SWAP(int, topLimit, btmLimit);
2397 : }
2398 :
2399 : /* Generate the termination key. This is the key value that
2400 : ** will end the search. There is no termination key if there
2401 : ** are no equality terms and no "X<..." term.
2402 : **
2403 : ** 2002-Dec-04: On a reverse-order scan, the so-called "termination"
2404 : ** key computed here really ends up being the start key.
2405 : */
2406 4 : nxt = pLevel->nxt;
2407 4 : if( topLimit ){
2408 : Expr *pX;
2409 0 : int k = pIdx->aiColumn[j];
2410 0 : pTerm = findTerm(&wc, iCur, k, notReady, topOp, pIdx);
2411 : assert( pTerm!=0 );
2412 0 : pX = pTerm->pExpr;
2413 : assert( (pTerm->flags & TERM_CODED)==0 );
2414 0 : sqlite3ExprCode(pParse, pX->pRight);
2415 0 : sqlite3VdbeAddOp(v, OP_IsNull, -(nEq+1), nxt);
2416 0 : topEq = pTerm->eOperator & (WO_LE|WO_GE);
2417 0 : disableTerm(pLevel, pTerm);
2418 0 : testOp = OP_IdxGE;
2419 : }else{
2420 4 : testOp = nEq>0 ? OP_IdxGE : OP_Noop;
2421 4 : topEq = 1;
2422 : }
2423 4 : if( testOp!=OP_Noop ){
2424 0 : int nCol = nEq + topLimit;
2425 0 : pLevel->iMem = pParse->nMem++;
2426 0 : buildIndexProbe(v, nCol, pIdx);
2427 0 : if( bRev ){
2428 0 : int op = topEq ? OP_MoveLe : OP_MoveLt;
2429 0 : sqlite3VdbeAddOp(v, op, iIdxCur, nxt);
2430 : }else{
2431 0 : sqlite3VdbeAddOp(v, OP_MemStore, pLevel->iMem, 1);
2432 : }
2433 4 : }else if( bRev ){
2434 0 : sqlite3VdbeAddOp(v, OP_Last, iIdxCur, brk);
2435 : }
2436 :
2437 : /* Generate the start key. This is the key that defines the lower
2438 : ** bound on the search. There is no start key if there are no
2439 : ** equality terms and if there is no "X>..." term. In
2440 : ** that case, generate a "Rewind" instruction in place of the
2441 : ** start key search.
2442 : **
2443 : ** 2002-Dec-04: In the case of a reverse-order search, the so-called
2444 : ** "start" key really ends up being used as the termination key.
2445 : */
2446 4 : if( btmLimit ){
2447 : Expr *pX;
2448 0 : int k = pIdx->aiColumn[j];
2449 0 : pTerm = findTerm(&wc, iCur, k, notReady, btmOp, pIdx);
2450 : assert( pTerm!=0 );
2451 0 : pX = pTerm->pExpr;
2452 : assert( (pTerm->flags & TERM_CODED)==0 );
2453 0 : sqlite3ExprCode(pParse, pX->pRight);
2454 0 : sqlite3VdbeAddOp(v, OP_IsNull, -(nEq+1), nxt);
2455 0 : btmEq = pTerm->eOperator & (WO_LE|WO_GE);
2456 0 : disableTerm(pLevel, pTerm);
2457 : }else{
2458 4 : btmEq = 1;
2459 : }
2460 4 : if( nEq>0 || btmLimit ){
2461 0 : int nCol = nEq + btmLimit;
2462 0 : buildIndexProbe(v, nCol, pIdx);
2463 0 : if( bRev ){
2464 0 : pLevel->iMem = pParse->nMem++;
2465 0 : sqlite3VdbeAddOp(v, OP_MemStore, pLevel->iMem, 1);
2466 0 : testOp = OP_IdxLT;
2467 : }else{
2468 0 : int op = btmEq ? OP_MoveGe : OP_MoveGt;
2469 0 : sqlite3VdbeAddOp(v, op, iIdxCur, nxt);
2470 : }
2471 4 : }else if( bRev ){
2472 0 : testOp = OP_Noop;
2473 : }else{
2474 4 : sqlite3VdbeAddOp(v, OP_Rewind, iIdxCur, brk);
2475 : }
2476 :
2477 : /* Generate the the top of the loop. If there is a termination
2478 : ** key we have to test for that key and abort at the top of the
2479 : ** loop.
2480 : */
2481 4 : start = sqlite3VdbeCurrentAddr(v);
2482 4 : if( testOp!=OP_Noop ){
2483 0 : sqlite3VdbeAddOp(v, OP_MemLoad, pLevel->iMem, 0);
2484 0 : sqlite3VdbeAddOp(v, testOp, iIdxCur, nxt);
2485 0 : if( (topEq && !bRev) || (!btmEq && bRev) ){
2486 0 : sqlite3VdbeChangeP3(v, -1, "+", P3_STATIC);
2487 : }
2488 : }
2489 4 : if( topLimit | btmLimit ){
2490 0 : sqlite3VdbeAddOp(v, OP_Column, iIdxCur, nEq);
2491 0 : sqlite3VdbeAddOp(v, OP_IsNull, 1, cont);
2492 : }
2493 4 : if( !omitTable ){
2494 4 : sqlite3VdbeAddOp(v, OP_IdxRowid, iIdxCur, 0);
2495 4 : sqlite3VdbeAddOp(v, OP_MoveGe, iCur, 0);
2496 : }
2497 :
2498 : /* Record the instruction used to terminate the loop.
2499 : */
2500 4 : pLevel->op = bRev ? OP_Prev : OP_Next;
2501 4 : pLevel->p1 = iIdxCur;
2502 4 : pLevel->p2 = start;
2503 155 : }else if( pLevel->flags & WHERE_COLUMN_EQ ){
2504 : /* Case 4: There is an index and all terms of the WHERE clause that
2505 : ** refer to the index using the "==" or "IN" operators.
2506 : */
2507 : int start;
2508 9 : int nEq = pLevel->nEq;
2509 :
2510 : /* Generate code to evaluate all constraint terms using == or IN
2511 : ** and leave the values of those terms on the stack.
2512 : */
2513 9 : codeAllEqualityTerms(pParse, pLevel, &wc, notReady);
2514 9 : nxt = pLevel->nxt;
2515 :
2516 : /* Generate a single key that will be used to both start and terminate
2517 : ** the search
2518 : */
2519 9 : buildIndexProbe(v, nEq, pIdx);
2520 9 : sqlite3VdbeAddOp(v, OP_MemStore, pLevel->iMem, 0);
2521 :
2522 : /* Generate code (1) to move to the first matching element of the table.
2523 : ** Then generate code (2) that jumps to "nxt" after the cursor is past
2524 : ** the last matching element of the table. The code (1) is executed
2525 : ** once to initialize the search, the code (2) is executed before each
2526 : ** iteration of the scan to see if the scan has finished. */
2527 9 : if( bRev ){
2528 : /* Scan in reverse order */
2529 0 : sqlite3VdbeAddOp(v, OP_MoveLe, iIdxCur, nxt);
2530 0 : start = sqlite3VdbeAddOp(v, OP_MemLoad, pLevel->iMem, 0);
2531 0 : sqlite3VdbeAddOp(v, OP_IdxLT, iIdxCur, nxt);
2532 0 : pLevel->op = OP_Prev;
2533 : }else{
2534 : /* Scan in the forward order */
2535 9 : sqlite3VdbeAddOp(v, OP_MoveGe, iIdxCur, nxt);
2536 9 : start = sqlite3VdbeAddOp(v, OP_MemLoad, pLevel->iMem, 0);
2537 9 : sqlite3VdbeOp3(v, OP_IdxGE, iIdxCur, nxt, "+", P3_STATIC);
2538 9 : pLevel->op = OP_Next;
2539 : }
2540 9 : if( !omitTable ){
2541 7 : sqlite3VdbeAddOp(v, OP_IdxRowid, iIdxCur, 0);
2542 7 : sqlite3VdbeAddOp(v, OP_MoveGe, iCur, 0);
2543 : }
2544 9 : pLevel->p1 = iIdxCur;
2545 9 : pLevel->p2 = start;
2546 : }else{
2547 : /* Case 5: There is no usable index. We must do a complete
2548 : ** scan of the entire table.
2549 : */
2550 : assert( omitTable==0 );
2551 : assert( bRev==0 );
2552 146 : pLevel->op = OP_Next;
2553 146 : pLevel->p1 = iCur;
2554 146 : pLevel->p2 = 1 + sqlite3VdbeAddOp(v, OP_Rewind, iCur, brk);
2555 : }
2556 217 : notReady &= ~getMask(&maskSet, iCur);
2557 :
2558 : /* Insert code to test every subexpression that can be completely
2559 : ** computed using the current set of tables.
2560 : */
2561 385 : for(pTerm=wc.a, j=wc.nTerm; j>0; j--, pTerm++){
2562 : Expr *pE;
2563 168 : if( pTerm->flags & (TERM_VIRTUAL|TERM_CODED) ) continue;
2564 91 : if( (pTerm->prereqAll & notReady)!=0 ) continue;
2565 84 : pE = pTerm->pExpr;
2566 : assert( pE!=0 );
2567 84 : if( pLevel->iLeftJoin && !ExprHasProperty(pE, EP_FromJoin) ){
2568 2 : continue;
2569 : }
2570 82 : sqlite3ExprIfFalse(pParse, pE, cont, 1);
2571 82 : pTerm->flags |= TERM_CODED;
2572 : }
2573 :
2574 : /* For a LEFT OUTER JOIN, generate code that will record the fact that
2575 : ** at least one row of the right table has matched the left table.
2576 : */
2577 217 : if( pLevel->iLeftJoin ){
2578 5 : pLevel->top = sqlite3VdbeCurrentAddr(v);
2579 5 : sqlite3VdbeAddOp(v, OP_MemInt, 1, pLevel->iLeftJoin);
2580 : VdbeComment((v, "# record LEFT JOIN hit"));
2581 17 : for(pTerm=wc.a, j=0; j<wc.nTerm; j++, pTerm++){
2582 12 : if( pTerm->flags & (TERM_VIRTUAL|TERM_CODED) ) continue;
2583 2 : if( (pTerm->prereqAll & notReady)!=0 ) continue;
2584 : assert( pTerm->pExpr );
2585 2 : sqlite3ExprIfFalse(pParse, pTerm->pExpr, cont, 1);
2586 2 : pTerm->flags |= TERM_CODED;
2587 : }
2588 : }
2589 : }
2590 :
2591 : #ifdef SQLITE_TEST /* For testing and debugging use only */
2592 : /* Record in the query plan information about the current table
2593 : ** and the index used to access it (if any). If the table itself
2594 : ** is not used, its name is just '{}'. If no index is used
2595 : ** the index is listed as "{}". If the primary key is used the
2596 : ** index name is '*'.
2597 : */
2598 : for(i=0; i<pTabList->nSrc; i++){
2599 : char *z;
2600 : int n;
2601 : pLevel = &pWInfo->a[i];
2602 : pTabItem = &pTabList->a[pLevel->iFrom];
2603 : z = pTabItem->zAlias;
2604 : if( z==0 ) z = pTabItem->pTab->zName;
2605 : n = strlen(z);
2606 : if( n+nQPlan < sizeof(sqlite3_query_plan)-10 ){
2607 : if( pLevel->flags & WHERE_IDX_ONLY ){
2608 : strcpy(&sqlite3_query_plan[nQPlan], "{}");
2609 : nQPlan += 2;
2610 : }else{
2611 : strcpy(&sqlite3_query_plan[nQPlan], z);
2612 : nQPlan += n;
2613 : }
2614 : sqlite3_query_plan[nQPlan++] = ' ';
2615 : }
2616 : if( pLevel->flags & (WHERE_ROWID_EQ|WHERE_ROWID_RANGE) ){
2617 : strcpy(&sqlite3_query_plan[nQPlan], "* ");
2618 : nQPlan += 2;
2619 : }else if( pLevel->pIdx==0 ){
2620 : strcpy(&sqlite3_query_plan[nQPlan], "{} ");
2621 : nQPlan += 3;
2622 : }else{
2623 : n = strlen(pLevel->pIdx->zName);
2624 : if( n+nQPlan < sizeof(sqlite3_query_plan)-2 ){
2625 : strcpy(&sqlite3_query_plan[nQPlan], pLevel->pIdx->zName);
2626 : nQPlan += n;
2627 : sqlite3_query_plan[nQPlan++] = ' ';
2628 : }
2629 : }
2630 : }
2631 : while( nQPlan>0 && sqlite3_query_plan[nQPlan-1]==' ' ){
2632 : sqlite3_query_plan[--nQPlan] = 0;
2633 : }
2634 : sqlite3_query_plan[nQPlan] = 0;
2635 : nQPlan = 0;
2636 : #endif /* SQLITE_TEST // Testing and debugging use only */
2637 :
2638 : /* Record the continuation address in the WhereInfo structure. Then
2639 : ** clean up and return.
2640 : */
2641 221 : pWInfo->iContinue = cont;
2642 221 : whereClauseClear(&wc);
2643 221 : return pWInfo;
2644 :
2645 : /* Jump here if malloc fails */
2646 0 : whereBeginNoMem:
2647 0 : whereClauseClear(&wc);
2648 0 : whereInfoFree(pWInfo);
2649 0 : return 0;
2650 : }
2651 :
2652 : /*
2653 : ** Generate the end of the WHERE loop. See comments on
2654 : ** sqlite3WhereBegin() for additional information.
2655 : */
2656 221 : void sqlite3WhereEnd(WhereInfo *pWInfo){
2657 221 : Vdbe *v = pWInfo->pParse->pVdbe;
2658 : int i;
2659 : WhereLevel *pLevel;
2660 221 : SrcList *pTabList = pWInfo->pTabList;
2661 :
2662 : /* Generate loop termination code.
2663 : */
2664 438 : for(i=pTabList->nSrc-1; i>=0; i--){
2665 217 : pLevel = &pWInfo->a[i];
2666 217 : sqlite3VdbeResolveLabel(v, pLevel->cont);
2667 217 : if( pLevel->op!=OP_Noop ){
2668 159 : sqlite3VdbeAddOp(v, pLevel->op, pLevel->p1, pLevel->p2);
2669 : }
2670 217 : if( pLevel->nIn ){
2671 : struct InLoop *pIn;
2672 : int j;
2673 0 : sqlite3VdbeResolveLabel(v, pLevel->nxt);
2674 0 : for(j=pLevel->nIn, pIn=&pLevel->aInLoop[j-1]; j>0; j--, pIn--){
2675 0 : sqlite3VdbeJumpHere(v, pIn->topAddr+1);
2676 0 : sqlite3VdbeAddOp(v, OP_Next, pIn->iCur, pIn->topAddr);
2677 0 : sqlite3VdbeJumpHere(v, pIn->topAddr-1);
2678 : }
2679 0 : sqliteFree(pLevel->aInLoop);
2680 : }
2681 217 : sqlite3VdbeResolveLabel(v, pLevel->brk);
2682 217 : if( pLevel->iLeftJoin ){
2683 : int addr;
2684 5 : addr = sqlite3VdbeAddOp(v, OP_IfMemPos, pLevel->iLeftJoin, 0);
2685 5 : sqlite3VdbeAddOp(v, OP_NullRow, pTabList->a[i].iCursor, 0);
2686 5 : if( pLevel->iIdxCur>=0 ){
2687 5 : sqlite3VdbeAddOp(v, OP_NullRow, pLevel->iIdxCur, 0);
2688 : }
2689 5 : sqlite3VdbeAddOp(v, OP_Goto, 0, pLevel->top);
2690 5 : sqlite3VdbeJumpHere(v, addr);
2691 : }
2692 : }
2693 :
2694 : /* The "break" point is here, just past the end of the outer loop.
2695 : ** Set it.
2696 : */
2697 221 : sqlite3VdbeResolveLabel(v, pWInfo->iBreak);
2698 :
2699 : /* Close all of the cursors that were opened by sqlite3WhereBegin.
2700 : */
2701 438 : for(i=0, pLevel=pWInfo->a; i<pTabList->nSrc; i++, pLevel++){
2702 217 : struct SrcList_item *pTabItem = &pTabList->a[pLevel->iFrom];
2703 217 : Table *pTab = pTabItem->pTab;
2704 : assert( pTab!=0 );
2705 217 : if( pTab->isEphem || pTab->pSelect ) continue;
2706 217 : if( (pLevel->flags & WHERE_IDX_ONLY)==0 ){
2707 215 : sqlite3VdbeAddOp(v, OP_Close, pTabItem->iCursor, 0);
2708 : }
2709 217 : if( pLevel->pIdx!=0 ){
2710 13 : sqlite3VdbeAddOp(v, OP_Close, pLevel->iIdxCur, 0);
2711 : }
2712 :
2713 : /* Make cursor substitutions for cases where we want to use
2714 : ** just the index and never reference the table.
2715 : **
2716 : ** Calls to the code generator in between sqlite3WhereBegin and
2717 : ** sqlite3WhereEnd will have created code that references the table
2718 : ** directly. This loop scans all that code looking for opcodes
2719 : ** that reference the table and converts them into opcodes that
2720 : ** reference the index.
2721 : */
2722 217 : if( pLevel->flags & WHERE_IDX_ONLY ){
2723 : int k, j, last;
2724 : VdbeOp *pOp;
2725 2 : Index *pIdx = pLevel->pIdx;
2726 :
2727 : assert( pIdx!=0 );
2728 2 : pOp = sqlite3VdbeGetOp(v, pWInfo->iTop);
2729 2 : last = sqlite3VdbeCurrentAddr(v);
2730 37 : for(k=pWInfo->iTop; k<last; k++, pOp++){
2731 35 : if( pOp->p1!=pLevel->iTabCur ) continue;
2732 10 : if( pOp->opcode==OP_Column ){
2733 3 : pOp->p1 = pLevel->iIdxCur;
2734 3 : for(j=0; j<pIdx->nColumn; j++){
2735 3 : if( pOp->p2==pIdx->aiColumn[j] ){
2736 3 : pOp->p2 = j;
2737 3 : break;
2738 : }
2739 : }
2740 7 : }else if( pOp->opcode==OP_Rowid ){
2741 0 : pOp->p1 = pLevel->iIdxCur;
2742 0 : pOp->opcode = OP_IdxRowid;
2743 7 : }else if( pOp->opcode==OP_NullRow ){
2744 1 : pOp->opcode = OP_Noop;
2745 : }
2746 : }
2747 : }
2748 : }
2749 :
2750 : /* Final cleanup
2751 : */
2752 221 : whereInfoFree(pWInfo);
2753 : return;
2754 : }
|
