1 | /* |
2 | ** 2013-11-12 |
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 | ** |
13 | ** This file contains structure and macro definitions for the query |
14 | ** planner logic in "where.c". These definitions are broken out into |
15 | ** a separate source file for easier editing. |
16 | */ |
17 | #ifndef SQLITE_WHEREINT_H |
18 | #define SQLITE_WHEREINT_H |
19 | |
20 | |
21 | /* Forward references |
22 | */ |
23 | typedef struct WhereClause WhereClause; |
24 | typedef struct WhereMaskSet WhereMaskSet; |
25 | typedef struct WhereOrInfo WhereOrInfo; |
26 | typedef struct WhereAndInfo WhereAndInfo; |
27 | typedef struct WhereLevel WhereLevel; |
28 | typedef struct WhereLoop WhereLoop; |
29 | typedef struct WherePath WherePath; |
30 | typedef struct WhereTerm WhereTerm; |
31 | typedef struct WhereLoopBuilder WhereLoopBuilder; |
32 | typedef struct WhereScan WhereScan; |
33 | typedef struct WhereOrCost WhereOrCost; |
34 | typedef struct WhereOrSet WhereOrSet; |
35 | typedef struct WhereMemBlock WhereMemBlock; |
36 | typedef struct WhereRightJoin WhereRightJoin; |
37 | |
38 | /* |
39 | ** This object is a header on a block of allocated memory that will be |
40 | ** automatically freed when its WInfo oject is destructed. |
41 | */ |
42 | struct WhereMemBlock { |
43 | WhereMemBlock *pNext; /* Next block in the chain */ |
44 | u64 sz; /* Bytes of space */ |
45 | }; |
46 | |
47 | /* |
48 | ** Extra information attached to a WhereLevel that is a RIGHT JOIN. |
49 | */ |
50 | struct WhereRightJoin { |
51 | int iMatch; /* Cursor used to determine prior matched rows */ |
52 | int regBloom; /* Bloom filter for iRJMatch */ |
53 | int regReturn; /* Return register for the interior subroutine */ |
54 | int addrSubrtn; /* Starting address for the interior subroutine */ |
55 | int endSubrtn; /* The last opcode in the interior subroutine */ |
56 | }; |
57 | |
58 | /* |
59 | ** This object contains information needed to implement a single nested |
60 | ** loop in WHERE clause. |
61 | ** |
62 | ** Contrast this object with WhereLoop. This object describes the |
63 | ** implementation of the loop. WhereLoop describes the algorithm. |
64 | ** This object contains a pointer to the WhereLoop algorithm as one of |
65 | ** its elements. |
66 | ** |
67 | ** The WhereInfo object contains a single instance of this object for |
68 | ** each term in the FROM clause (which is to say, for each of the |
69 | ** nested loops as implemented). The order of WhereLevel objects determines |
70 | ** the loop nested order, with WhereInfo.a[0] being the outer loop and |
71 | ** WhereInfo.a[WhereInfo.nLevel-1] being the inner loop. |
72 | */ |
73 | struct WhereLevel { |
74 | int iLeftJoin; /* Memory cell used to implement LEFT OUTER JOIN */ |
75 | int iTabCur; /* The VDBE cursor used to access the table */ |
76 | int iIdxCur; /* The VDBE cursor used to access pIdx */ |
77 | int addrBrk; /* Jump here to break out of the loop */ |
78 | int addrNxt; /* Jump here to start the next IN combination */ |
79 | int addrSkip; /* Jump here for next iteration of skip-scan */ |
80 | int addrCont; /* Jump here to continue with the next loop cycle */ |
81 | int addrFirst; /* First instruction of interior of the loop */ |
82 | int addrBody; /* Beginning of the body of this loop */ |
83 | int regBignull; /* big-null flag reg. True if a NULL-scan is needed */ |
84 | int addrBignull; /* Jump here for next part of big-null scan */ |
85 | #ifndef SQLITE_LIKE_DOESNT_MATCH_BLOBS |
86 | u32 iLikeRepCntr; /* LIKE range processing counter register (times 2) */ |
87 | int addrLikeRep; /* LIKE range processing address */ |
88 | #endif |
89 | int regFilter; /* Bloom filter */ |
90 | WhereRightJoin *pRJ; /* Extra information for RIGHT JOIN */ |
91 | u8 iFrom; /* Which entry in the FROM clause */ |
92 | u8 op, p3, p5; /* Opcode, P3 & P5 of the opcode that ends the loop */ |
93 | int p1, p2; /* Operands of the opcode used to end the loop */ |
94 | union { /* Information that depends on pWLoop->wsFlags */ |
95 | struct { |
96 | int nIn; /* Number of entries in aInLoop[] */ |
97 | struct InLoop { |
98 | int iCur; /* The VDBE cursor used by this IN operator */ |
99 | int addrInTop; /* Top of the IN loop */ |
100 | int iBase; /* Base register of multi-key index record */ |
101 | int nPrefix; /* Number of prior entires in the key */ |
102 | u8 eEndLoopOp; /* IN Loop terminator. OP_Next or OP_Prev */ |
103 | } *aInLoop; /* Information about each nested IN operator */ |
104 | } in; /* Used when pWLoop->wsFlags&WHERE_IN_ABLE */ |
105 | Index *pCoveringIdx; /* Possible covering index for WHERE_MULTI_OR */ |
106 | } u; |
107 | struct WhereLoop *pWLoop; /* The selected WhereLoop object */ |
108 | Bitmask notReady; /* FROM entries not usable at this level */ |
109 | #ifdef SQLITE_ENABLE_STMT_SCANSTATUS |
110 | int addrVisit; /* Address at which row is visited */ |
111 | #endif |
112 | }; |
113 | |
114 | /* |
115 | ** Each instance of this object represents an algorithm for evaluating one |
116 | ** term of a join. Every term of the FROM clause will have at least |
117 | ** one corresponding WhereLoop object (unless INDEXED BY constraints |
118 | ** prevent a query solution - which is an error) and many terms of the |
119 | ** FROM clause will have multiple WhereLoop objects, each describing a |
120 | ** potential way of implementing that FROM-clause term, together with |
121 | ** dependencies and cost estimates for using the chosen algorithm. |
122 | ** |
123 | ** Query planning consists of building up a collection of these WhereLoop |
124 | ** objects, then computing a particular sequence of WhereLoop objects, with |
125 | ** one WhereLoop object per FROM clause term, that satisfy all dependencies |
126 | ** and that minimize the overall cost. |
127 | */ |
128 | struct WhereLoop { |
129 | Bitmask prereq; /* Bitmask of other loops that must run first */ |
130 | Bitmask maskSelf; /* Bitmask identifying table iTab */ |
131 | #ifdef SQLITE_DEBUG |
132 | char cId; /* Symbolic ID of this loop for debugging use */ |
133 | #endif |
134 | u8 iTab; /* Position in FROM clause of table for this loop */ |
135 | u8 iSortIdx; /* Sorting index number. 0==None */ |
136 | LogEst rSetup; /* One-time setup cost (ex: create transient index) */ |
137 | LogEst rRun; /* Cost of running each loop */ |
138 | LogEst nOut; /* Estimated number of output rows */ |
139 | union { |
140 | struct { /* Information for internal btree tables */ |
141 | u16 nEq; /* Number of equality constraints */ |
142 | u16 nBtm; /* Size of BTM vector */ |
143 | u16 nTop; /* Size of TOP vector */ |
144 | u16 nDistinctCol; /* Index columns used to sort for DISTINCT */ |
145 | Index *pIndex; /* Index used, or NULL */ |
146 | } btree; |
147 | struct { /* Information for virtual tables */ |
148 | int idxNum; /* Index number */ |
149 | u32 needFree : 1; /* True if sqlite3_free(idxStr) is needed */ |
150 | u32 bOmitOffset : 1; /* True to let virtual table handle offset */ |
151 | i8 isOrdered; /* True if satisfies ORDER BY */ |
152 | u16 omitMask; /* Terms that may be omitted */ |
153 | char *idxStr; /* Index identifier string */ |
154 | u32 mHandleIn; /* Terms to handle as IN(...) instead of == */ |
155 | } vtab; |
156 | } u; |
157 | u32 wsFlags; /* WHERE_* flags describing the plan */ |
158 | u16 nLTerm; /* Number of entries in aLTerm[] */ |
159 | u16 nSkip; /* Number of NULL aLTerm[] entries */ |
160 | /**** whereLoopXfer() copies fields above ***********************/ |
161 | # define WHERE_LOOP_XFER_SZ offsetof(WhereLoop,nLSlot) |
162 | u16 nLSlot; /* Number of slots allocated for aLTerm[] */ |
163 | WhereTerm **aLTerm; /* WhereTerms used */ |
164 | WhereLoop *pNextLoop; /* Next WhereLoop object in the WhereClause */ |
165 | WhereTerm *aLTermSpace[3]; /* Initial aLTerm[] space */ |
166 | }; |
167 | |
168 | /* This object holds the prerequisites and the cost of running a |
169 | ** subquery on one operand of an OR operator in the WHERE clause. |
170 | ** See WhereOrSet for additional information |
171 | */ |
172 | struct WhereOrCost { |
173 | Bitmask prereq; /* Prerequisites */ |
174 | LogEst rRun; /* Cost of running this subquery */ |
175 | LogEst nOut; /* Number of outputs for this subquery */ |
176 | }; |
177 | |
178 | /* The WhereOrSet object holds a set of possible WhereOrCosts that |
179 | ** correspond to the subquery(s) of OR-clause processing. Only the |
180 | ** best N_OR_COST elements are retained. |
181 | */ |
182 | #define N_OR_COST 3 |
183 | struct WhereOrSet { |
184 | u16 n; /* Number of valid a[] entries */ |
185 | WhereOrCost a[N_OR_COST]; /* Set of best costs */ |
186 | }; |
187 | |
188 | /* |
189 | ** Each instance of this object holds a sequence of WhereLoop objects |
190 | ** that implement some or all of a query plan. |
191 | ** |
192 | ** Think of each WhereLoop object as a node in a graph with arcs |
193 | ** showing dependencies and costs for travelling between nodes. (That is |
194 | ** not a completely accurate description because WhereLoop costs are a |
195 | ** vector, not a scalar, and because dependencies are many-to-one, not |
196 | ** one-to-one as are graph nodes. But it is a useful visualization aid.) |
197 | ** Then a WherePath object is a path through the graph that visits some |
198 | ** or all of the WhereLoop objects once. |
199 | ** |
200 | ** The "solver" works by creating the N best WherePath objects of length |
201 | ** 1. Then using those as a basis to compute the N best WherePath objects |
202 | ** of length 2. And so forth until the length of WherePaths equals the |
203 | ** number of nodes in the FROM clause. The best (lowest cost) WherePath |
204 | ** at the end is the chosen query plan. |
205 | */ |
206 | struct WherePath { |
207 | Bitmask maskLoop; /* Bitmask of all WhereLoop objects in this path */ |
208 | Bitmask revLoop; /* aLoop[]s that should be reversed for ORDER BY */ |
209 | LogEst nRow; /* Estimated number of rows generated by this path */ |
210 | LogEst rCost; /* Total cost of this path */ |
211 | LogEst rUnsorted; /* Total cost of this path ignoring sorting costs */ |
212 | i8 isOrdered; /* No. of ORDER BY terms satisfied. -1 for unknown */ |
213 | WhereLoop **aLoop; /* Array of WhereLoop objects implementing this path */ |
214 | }; |
215 | |
216 | /* |
217 | ** The query generator uses an array of instances of this structure to |
218 | ** help it analyze the subexpressions of the WHERE clause. Each WHERE |
219 | ** clause subexpression is separated from the others by AND operators, |
220 | ** usually, or sometimes subexpressions separated by OR. |
221 | ** |
222 | ** All WhereTerms are collected into a single WhereClause structure. |
223 | ** The following identity holds: |
224 | ** |
225 | ** WhereTerm.pWC->a[WhereTerm.idx] == WhereTerm |
226 | ** |
227 | ** When a term is of the form: |
228 | ** |
229 | ** X <op> <expr> |
230 | ** |
231 | ** where X is a column name and <op> is one of certain operators, |
232 | ** then WhereTerm.leftCursor and WhereTerm.u.leftColumn record the |
233 | ** cursor number and column number for X. WhereTerm.eOperator records |
234 | ** the <op> using a bitmask encoding defined by WO_xxx below. The |
235 | ** use of a bitmask encoding for the operator allows us to search |
236 | ** quickly for terms that match any of several different operators. |
237 | ** |
238 | ** A WhereTerm might also be two or more subterms connected by OR: |
239 | ** |
240 | ** (t1.X <op> <expr>) OR (t1.Y <op> <expr>) OR .... |
241 | ** |
242 | ** In this second case, wtFlag has the TERM_ORINFO bit set and eOperator==WO_OR |
243 | ** and the WhereTerm.u.pOrInfo field points to auxiliary information that |
244 | ** is collected about the OR clause. |
245 | ** |
246 | ** If a term in the WHERE clause does not match either of the two previous |
247 | ** categories, then eOperator==0. The WhereTerm.pExpr field is still set |
248 | ** to the original subexpression content and wtFlags is set up appropriately |
249 | ** but no other fields in the WhereTerm object are meaningful. |
250 | ** |
251 | ** When eOperator!=0, prereqRight and prereqAll record sets of cursor numbers, |
252 | ** but they do so indirectly. A single WhereMaskSet structure translates |
253 | ** cursor number into bits and the translated bit is stored in the prereq |
254 | ** fields. The translation is used in order to maximize the number of |
255 | ** bits that will fit in a Bitmask. The VDBE cursor numbers might be |
256 | ** spread out over the non-negative integers. For example, the cursor |
257 | ** numbers might be 3, 8, 9, 10, 20, 23, 41, and 45. The WhereMaskSet |
258 | ** translates these sparse cursor numbers into consecutive integers |
259 | ** beginning with 0 in order to make the best possible use of the available |
260 | ** bits in the Bitmask. So, in the example above, the cursor numbers |
261 | ** would be mapped into integers 0 through 7. |
262 | ** |
263 | ** The number of terms in a join is limited by the number of bits |
264 | ** in prereqRight and prereqAll. The default is 64 bits, hence SQLite |
265 | ** is only able to process joins with 64 or fewer tables. |
266 | */ |
267 | struct WhereTerm { |
268 | Expr *pExpr; /* Pointer to the subexpression that is this term */ |
269 | WhereClause *pWC; /* The clause this term is part of */ |
270 | LogEst truthProb; /* Probability of truth for this expression */ |
271 | u16 wtFlags; /* TERM_xxx bit flags. See below */ |
272 | u16 eOperator; /* A WO_xx value describing <op> */ |
273 | u8 nChild; /* Number of children that must disable us */ |
274 | u8 eMatchOp; /* Op for vtab MATCH/LIKE/GLOB/REGEXP terms */ |
275 | int iParent; /* Disable pWC->a[iParent] when this term disabled */ |
276 | int leftCursor; /* Cursor number of X in "X <op> <expr>" */ |
277 | union { |
278 | struct { |
279 | int leftColumn; /* Column number of X in "X <op> <expr>" */ |
280 | int iField; /* Field in (?,?,?) IN (SELECT...) vector */ |
281 | } x; /* Opcode other than OP_OR or OP_AND */ |
282 | WhereOrInfo *pOrInfo; /* Extra information if (eOperator & WO_OR)!=0 */ |
283 | WhereAndInfo *pAndInfo; /* Extra information if (eOperator& WO_AND)!=0 */ |
284 | } u; |
285 | Bitmask prereqRight; /* Bitmask of tables used by pExpr->pRight */ |
286 | Bitmask prereqAll; /* Bitmask of tables referenced by pExpr */ |
287 | }; |
288 | |
289 | /* |
290 | ** Allowed values of WhereTerm.wtFlags |
291 | */ |
292 | #define TERM_DYNAMIC 0x0001 /* Need to call sqlite3ExprDelete(db, pExpr) */ |
293 | #define TERM_VIRTUAL 0x0002 /* Added by the optimizer. Do not code */ |
294 | #define TERM_CODED 0x0004 /* This term is already coded */ |
295 | #define TERM_COPIED 0x0008 /* Has a child */ |
296 | #define TERM_ORINFO 0x0010 /* Need to free the WhereTerm.u.pOrInfo object */ |
297 | #define TERM_ANDINFO 0x0020 /* Need to free the WhereTerm.u.pAndInfo obj */ |
298 | #define TERM_OK 0x0040 /* Used during OR-clause processing */ |
299 | #define TERM_VNULL 0x0080 /* Manufactured x>NULL or x<=NULL term */ |
300 | #define TERM_LIKEOPT 0x0100 /* Virtual terms from the LIKE optimization */ |
301 | #define TERM_LIKECOND 0x0200 /* Conditionally this LIKE operator term */ |
302 | #define TERM_LIKE 0x0400 /* The original LIKE operator */ |
303 | #define TERM_IS 0x0800 /* Term.pExpr is an IS operator */ |
304 | #define TERM_VARSELECT 0x1000 /* Term.pExpr contains a correlated sub-query */ |
305 | #define TERM_HEURTRUTH 0x2000 /* Heuristic truthProb used */ |
306 | #ifdef SQLITE_ENABLE_STAT4 |
307 | # define TERM_HIGHTRUTH 0x4000 /* Term excludes few rows */ |
308 | #else |
309 | # define TERM_HIGHTRUTH 0 /* Only used with STAT4 */ |
310 | #endif |
311 | #define TERM_SLICE 0x8000 /* One slice of a row-value/vector comparison */ |
312 | |
313 | /* |
314 | ** An instance of the WhereScan object is used as an iterator for locating |
315 | ** terms in the WHERE clause that are useful to the query planner. |
316 | */ |
317 | struct WhereScan { |
318 | WhereClause *pOrigWC; /* Original, innermost WhereClause */ |
319 | WhereClause *pWC; /* WhereClause currently being scanned */ |
320 | const char *zCollName; /* Required collating sequence, if not NULL */ |
321 | Expr *pIdxExpr; /* Search for this index expression */ |
322 | int k; /* Resume scanning at this->pWC->a[this->k] */ |
323 | u32 opMask; /* Acceptable operators */ |
324 | char idxaff; /* Must match this affinity, if zCollName!=NULL */ |
325 | unsigned char iEquiv; /* Current slot in aiCur[] and aiColumn[] */ |
326 | unsigned char nEquiv; /* Number of entries in aiCur[] and aiColumn[] */ |
327 | int aiCur[11]; /* Cursors in the equivalence class */ |
328 | i16 aiColumn[11]; /* Corresponding column number in the eq-class */ |
329 | }; |
330 | |
331 | /* |
332 | ** An instance of the following structure holds all information about a |
333 | ** WHERE clause. Mostly this is a container for one or more WhereTerms. |
334 | ** |
335 | ** Explanation of pOuter: For a WHERE clause of the form |
336 | ** |
337 | ** a AND ((b AND c) OR (d AND e)) AND f |
338 | ** |
339 | ** There are separate WhereClause objects for the whole clause and for |
340 | ** the subclauses "(b AND c)" and "(d AND e)". The pOuter field of the |
341 | ** subclauses points to the WhereClause object for the whole clause. |
342 | */ |
343 | struct WhereClause { |
344 | WhereInfo *pWInfo; /* WHERE clause processing context */ |
345 | WhereClause *pOuter; /* Outer conjunction */ |
346 | u8 op; /* Split operator. TK_AND or TK_OR */ |
347 | u8 hasOr; /* True if any a[].eOperator is WO_OR */ |
348 | int nTerm; /* Number of terms */ |
349 | int nSlot; /* Number of entries in a[] */ |
350 | int nBase; /* Number of terms through the last non-Virtual */ |
351 | WhereTerm *a; /* Each a[] describes a term of the WHERE cluase */ |
352 | #if defined(SQLITE_SMALL_STACK) |
353 | WhereTerm aStatic[1]; /* Initial static space for a[] */ |
354 | #else |
355 | WhereTerm aStatic[8]; /* Initial static space for a[] */ |
356 | #endif |
357 | }; |
358 | |
359 | /* |
360 | ** A WhereTerm with eOperator==WO_OR has its u.pOrInfo pointer set to |
361 | ** a dynamically allocated instance of the following structure. |
362 | */ |
363 | struct WhereOrInfo { |
364 | WhereClause wc; /* Decomposition into subterms */ |
365 | Bitmask indexable; /* Bitmask of all indexable tables in the clause */ |
366 | }; |
367 | |
368 | /* |
369 | ** A WhereTerm with eOperator==WO_AND has its u.pAndInfo pointer set to |
370 | ** a dynamically allocated instance of the following structure. |
371 | */ |
372 | struct WhereAndInfo { |
373 | WhereClause wc; /* The subexpression broken out */ |
374 | }; |
375 | |
376 | /* |
377 | ** An instance of the following structure keeps track of a mapping |
378 | ** between VDBE cursor numbers and bits of the bitmasks in WhereTerm. |
379 | ** |
380 | ** The VDBE cursor numbers are small integers contained in |
381 | ** SrcItem.iCursor and Expr.iTable fields. For any given WHERE |
382 | ** clause, the cursor numbers might not begin with 0 and they might |
383 | ** contain gaps in the numbering sequence. But we want to make maximum |
384 | ** use of the bits in our bitmasks. This structure provides a mapping |
385 | ** from the sparse cursor numbers into consecutive integers beginning |
386 | ** with 0. |
387 | ** |
388 | ** If WhereMaskSet.ix[A]==B it means that The A-th bit of a Bitmask |
389 | ** corresponds VDBE cursor number B. The A-th bit of a bitmask is 1<<A. |
390 | ** |
391 | ** For example, if the WHERE clause expression used these VDBE |
392 | ** cursors: 4, 5, 8, 29, 57, 73. Then the WhereMaskSet structure |
393 | ** would map those cursor numbers into bits 0 through 5. |
394 | ** |
395 | ** Note that the mapping is not necessarily ordered. In the example |
396 | ** above, the mapping might go like this: 4->3, 5->1, 8->2, 29->0, |
397 | ** 57->5, 73->4. Or one of 719 other combinations might be used. It |
398 | ** does not really matter. What is important is that sparse cursor |
399 | ** numbers all get mapped into bit numbers that begin with 0 and contain |
400 | ** no gaps. |
401 | */ |
402 | struct WhereMaskSet { |
403 | int bVarSelect; /* Used by sqlite3WhereExprUsage() */ |
404 | int n; /* Number of assigned cursor values */ |
405 | int ix[BMS]; /* Cursor assigned to each bit */ |
406 | }; |
407 | |
408 | /* |
409 | ** This object is a convenience wrapper holding all information needed |
410 | ** to construct WhereLoop objects for a particular query. |
411 | */ |
412 | struct WhereLoopBuilder { |
413 | WhereInfo *pWInfo; /* Information about this WHERE */ |
414 | WhereClause *pWC; /* WHERE clause terms */ |
415 | WhereLoop *pNew; /* Template WhereLoop */ |
416 | WhereOrSet *pOrSet; /* Record best loops here, if not NULL */ |
417 | #ifdef SQLITE_ENABLE_STAT4 |
418 | UnpackedRecord *pRec; /* Probe for stat4 (if required) */ |
419 | int nRecValid; /* Number of valid fields currently in pRec */ |
420 | #endif |
421 | unsigned char bldFlags1; /* First set of SQLITE_BLDF_* flags */ |
422 | unsigned char bldFlags2; /* Second set of SQLITE_BLDF_* flags */ |
423 | unsigned int iPlanLimit; /* Search limiter */ |
424 | }; |
425 | |
426 | /* Allowed values for WhereLoopBuider.bldFlags */ |
427 | #define SQLITE_BLDF1_INDEXED 0x0001 /* An index is used */ |
428 | #define SQLITE_BLDF1_UNIQUE 0x0002 /* All keys of a UNIQUE index used */ |
429 | |
430 | #define SQLITE_BLDF2_2NDPASS 0x0004 /* Second builder pass needed */ |
431 | |
432 | /* The WhereLoopBuilder.iPlanLimit is used to limit the number of |
433 | ** index+constraint combinations the query planner will consider for a |
434 | ** particular query. If this parameter is unlimited, then certain |
435 | ** pathological queries can spend excess time in the sqlite3WhereBegin() |
436 | ** routine. The limit is high enough that is should not impact real-world |
437 | ** queries. |
438 | ** |
439 | ** SQLITE_QUERY_PLANNER_LIMIT is the baseline limit. The limit is |
440 | ** increased by SQLITE_QUERY_PLANNER_LIMIT_INCR before each term of the FROM |
441 | ** clause is processed, so that every table in a join is guaranteed to be |
442 | ** able to propose a some index+constraint combinations even if the initial |
443 | ** baseline limit was exhausted by prior tables of the join. |
444 | */ |
445 | #ifndef SQLITE_QUERY_PLANNER_LIMIT |
446 | # define SQLITE_QUERY_PLANNER_LIMIT 20000 |
447 | #endif |
448 | #ifndef SQLITE_QUERY_PLANNER_LIMIT_INCR |
449 | # define SQLITE_QUERY_PLANNER_LIMIT_INCR 1000 |
450 | #endif |
451 | |
452 | /* |
453 | ** The WHERE clause processing routine has two halves. The |
454 | ** first part does the start of the WHERE loop and the second |
455 | ** half does the tail of the WHERE loop. An instance of |
456 | ** this structure is returned by the first half and passed |
457 | ** into the second half to give some continuity. |
458 | ** |
459 | ** An instance of this object holds the complete state of the query |
460 | ** planner. |
461 | */ |
462 | struct WhereInfo { |
463 | Parse *pParse; /* Parsing and code generating context */ |
464 | SrcList *pTabList; /* List of tables in the join */ |
465 | ExprList *pOrderBy; /* The ORDER BY clause or NULL */ |
466 | ExprList *pResultSet; /* Result set of the query */ |
467 | #if WHERETRACE_ENABLED |
468 | Expr *pWhere; /* The complete WHERE clause */ |
469 | #endif |
470 | Select *pSelect; /* The entire SELECT statement containing WHERE */ |
471 | int aiCurOnePass[2]; /* OP_OpenWrite cursors for the ONEPASS opt */ |
472 | int iContinue; /* Jump here to continue with next record */ |
473 | int iBreak; /* Jump here to break out of the loop */ |
474 | int savedNQueryLoop; /* pParse->nQueryLoop outside the WHERE loop */ |
475 | u16 wctrlFlags; /* Flags originally passed to sqlite3WhereBegin() */ |
476 | LogEst iLimit; /* LIMIT if wctrlFlags has WHERE_USE_LIMIT */ |
477 | u8 nLevel; /* Number of nested loop */ |
478 | i8 nOBSat; /* Number of ORDER BY terms satisfied by indices */ |
479 | u8 eOnePass; /* ONEPASS_OFF, or _SINGLE, or _MULTI */ |
480 | u8 eDistinct; /* One of the WHERE_DISTINCT_* values */ |
481 | unsigned bDeferredSeek :1; /* Uses OP_DeferredSeek */ |
482 | unsigned untestedTerms :1; /* Not all WHERE terms resolved by outer loop */ |
483 | unsigned bOrderedInnerLoop:1;/* True if only the inner-most loop is ordered */ |
484 | unsigned sorted :1; /* True if really sorted (not just grouped) */ |
485 | LogEst nRowOut; /* Estimated number of output rows */ |
486 | int iTop; /* The very beginning of the WHERE loop */ |
487 | int iEndWhere; /* End of the WHERE clause itself */ |
488 | WhereLoop *pLoops; /* List of all WhereLoop objects */ |
489 | WhereMemBlock *pMemToFree;/* Memory to free when this object destroyed */ |
490 | Bitmask revMask; /* Mask of ORDER BY terms that need reversing */ |
491 | WhereClause sWC; /* Decomposition of the WHERE clause */ |
492 | WhereMaskSet sMaskSet; /* Map cursor numbers to bitmasks */ |
493 | WhereLevel a[1]; /* Information about each nest loop in WHERE */ |
494 | }; |
495 | |
496 | /* |
497 | ** Private interfaces - callable only by other where.c routines. |
498 | ** |
499 | ** where.c: |
500 | */ |
501 | Bitmask sqlite3WhereGetMask(WhereMaskSet*,int); |
502 | #ifdef WHERETRACE_ENABLED |
503 | void sqlite3WhereClausePrint(WhereClause *pWC); |
504 | void sqlite3WhereTermPrint(WhereTerm *pTerm, int iTerm); |
505 | void sqlite3WhereLoopPrint(WhereLoop *p, WhereClause *pWC); |
506 | #endif |
507 | WhereTerm *sqlite3WhereFindTerm( |
508 | WhereClause *pWC, /* The WHERE clause to be searched */ |
509 | int iCur, /* Cursor number of LHS */ |
510 | int iColumn, /* Column number of LHS */ |
511 | Bitmask notReady, /* RHS must not overlap with this mask */ |
512 | u32 op, /* Mask of WO_xx values describing operator */ |
513 | Index *pIdx /* Must be compatible with this index, if not NULL */ |
514 | ); |
515 | void *sqlite3WhereMalloc(WhereInfo *pWInfo, u64 nByte); |
516 | void *sqlite3WhereRealloc(WhereInfo *pWInfo, void *pOld, u64 nByte); |
517 | |
518 | /* wherecode.c: */ |
519 | #ifndef SQLITE_OMIT_EXPLAIN |
520 | int sqlite3WhereExplainOneScan( |
521 | Parse *pParse, /* Parse context */ |
522 | SrcList *pTabList, /* Table list this loop refers to */ |
523 | WhereLevel *pLevel, /* Scan to write OP_Explain opcode for */ |
524 | u16 wctrlFlags /* Flags passed to sqlite3WhereBegin() */ |
525 | ); |
526 | int sqlite3WhereExplainBloomFilter( |
527 | const Parse *pParse, /* Parse context */ |
528 | const WhereInfo *pWInfo, /* WHERE clause */ |
529 | const WhereLevel *pLevel /* Bloom filter on this level */ |
530 | ); |
531 | #else |
532 | # define sqlite3WhereExplainOneScan(u,v,w,x) 0 |
533 | # define sqlite3WhereExplainBloomFilter(u,v,w) 0 |
534 | #endif /* SQLITE_OMIT_EXPLAIN */ |
535 | #ifdef SQLITE_ENABLE_STMT_SCANSTATUS |
536 | void sqlite3WhereAddScanStatus( |
537 | Vdbe *v, /* Vdbe to add scanstatus entry to */ |
538 | SrcList *pSrclist, /* FROM clause pLvl reads data from */ |
539 | WhereLevel *pLvl, /* Level to add scanstatus() entry for */ |
540 | int addrExplain /* Address of OP_Explain (or 0) */ |
541 | ); |
542 | #else |
543 | # define sqlite3WhereAddScanStatus(a, b, c, d) ((void)d) |
544 | #endif |
545 | Bitmask sqlite3WhereCodeOneLoopStart( |
546 | Parse *pParse, /* Parsing context */ |
547 | Vdbe *v, /* Prepared statement under construction */ |
548 | WhereInfo *pWInfo, /* Complete information about the WHERE clause */ |
549 | int iLevel, /* Which level of pWInfo->a[] should be coded */ |
550 | WhereLevel *pLevel, /* The current level pointer */ |
551 | Bitmask notReady /* Which tables are currently available */ |
552 | ); |
553 | SQLITE_NOINLINE void sqlite3WhereRightJoinLoop( |
554 | WhereInfo *pWInfo, |
555 | int iLevel, |
556 | WhereLevel *pLevel |
557 | ); |
558 | |
559 | /* whereexpr.c: */ |
560 | void sqlite3WhereClauseInit(WhereClause*,WhereInfo*); |
561 | void sqlite3WhereClauseClear(WhereClause*); |
562 | void sqlite3WhereSplit(WhereClause*,Expr*,u8); |
563 | void sqlite3WhereAddLimit(WhereClause*, Select*); |
564 | Bitmask sqlite3WhereExprUsage(WhereMaskSet*, Expr*); |
565 | Bitmask sqlite3WhereExprUsageNN(WhereMaskSet*, Expr*); |
566 | Bitmask sqlite3WhereExprListUsage(WhereMaskSet*, ExprList*); |
567 | void sqlite3WhereExprAnalyze(SrcList*, WhereClause*); |
568 | void sqlite3WhereTabFuncArgs(Parse*, SrcItem*, WhereClause*); |
569 | |
570 | |
571 | |
572 | |
573 | |
574 | /* |
575 | ** Bitmasks for the operators on WhereTerm objects. These are all |
576 | ** operators that are of interest to the query planner. An |
577 | ** OR-ed combination of these values can be used when searching for |
578 | ** particular WhereTerms within a WhereClause. |
579 | ** |
580 | ** Value constraints: |
581 | ** WO_EQ == SQLITE_INDEX_CONSTRAINT_EQ |
582 | ** WO_LT == SQLITE_INDEX_CONSTRAINT_LT |
583 | ** WO_LE == SQLITE_INDEX_CONSTRAINT_LE |
584 | ** WO_GT == SQLITE_INDEX_CONSTRAINT_GT |
585 | ** WO_GE == SQLITE_INDEX_CONSTRAINT_GE |
586 | */ |
587 | #define WO_IN 0x0001 |
588 | #define WO_EQ 0x0002 |
589 | #define WO_LT (WO_EQ<<(TK_LT-TK_EQ)) |
590 | #define WO_LE (WO_EQ<<(TK_LE-TK_EQ)) |
591 | #define WO_GT (WO_EQ<<(TK_GT-TK_EQ)) |
592 | #define WO_GE (WO_EQ<<(TK_GE-TK_EQ)) |
593 | #define WO_AUX 0x0040 /* Op useful to virtual tables only */ |
594 | #define WO_IS 0x0080 |
595 | #define WO_ISNULL 0x0100 |
596 | #define WO_OR 0x0200 /* Two or more OR-connected terms */ |
597 | #define WO_AND 0x0400 /* Two or more AND-connected terms */ |
598 | #define WO_EQUIV 0x0800 /* Of the form A==B, both columns */ |
599 | #define WO_NOOP 0x1000 /* This term does not restrict search space */ |
600 | #define WO_ROWVAL 0x2000 /* A row-value term */ |
601 | |
602 | #define WO_ALL 0x3fff /* Mask of all possible WO_* values */ |
603 | #define WO_SINGLE 0x01ff /* Mask of all non-compound WO_* values */ |
604 | |
605 | /* |
606 | ** These are definitions of bits in the WhereLoop.wsFlags field. |
607 | ** The particular combination of bits in each WhereLoop help to |
608 | ** determine the algorithm that WhereLoop represents. |
609 | */ |
610 | #define WHERE_COLUMN_EQ 0x00000001 /* x=EXPR */ |
611 | #define WHERE_COLUMN_RANGE 0x00000002 /* x<EXPR and/or x>EXPR */ |
612 | #define WHERE_COLUMN_IN 0x00000004 /* x IN (...) */ |
613 | #define WHERE_COLUMN_NULL 0x00000008 /* x IS NULL */ |
614 | #define WHERE_CONSTRAINT 0x0000000f /* Any of the WHERE_COLUMN_xxx values */ |
615 | #define WHERE_TOP_LIMIT 0x00000010 /* x<EXPR or x<=EXPR constraint */ |
616 | #define WHERE_BTM_LIMIT 0x00000020 /* x>EXPR or x>=EXPR constraint */ |
617 | #define WHERE_BOTH_LIMIT 0x00000030 /* Both x>EXPR and x<EXPR */ |
618 | #define WHERE_IDX_ONLY 0x00000040 /* Use index only - omit table */ |
619 | #define WHERE_IPK 0x00000100 /* x is the INTEGER PRIMARY KEY */ |
620 | #define WHERE_INDEXED 0x00000200 /* WhereLoop.u.btree.pIndex is valid */ |
621 | #define WHERE_VIRTUALTABLE 0x00000400 /* WhereLoop.u.vtab is valid */ |
622 | #define WHERE_IN_ABLE 0x00000800 /* Able to support an IN operator */ |
623 | #define WHERE_ONEROW 0x00001000 /* Selects no more than one row */ |
624 | #define WHERE_MULTI_OR 0x00002000 /* OR using multiple indices */ |
625 | #define WHERE_AUTO_INDEX 0x00004000 /* Uses an ephemeral index */ |
626 | #define WHERE_SKIPSCAN 0x00008000 /* Uses the skip-scan algorithm */ |
627 | #define WHERE_UNQ_WANTED 0x00010000 /* WHERE_ONEROW would have been helpful*/ |
628 | #define WHERE_PARTIALIDX 0x00020000 /* The automatic index is partial */ |
629 | #define WHERE_IN_EARLYOUT 0x00040000 /* Perhaps quit IN loops early */ |
630 | #define WHERE_BIGNULL_SORT 0x00080000 /* Column nEq of index is BIGNULL */ |
631 | #define WHERE_IN_SEEKSCAN 0x00100000 /* Seek-scan optimization for IN */ |
632 | #define WHERE_TRANSCONS 0x00200000 /* Uses a transitive constraint */ |
633 | #define WHERE_BLOOMFILTER 0x00400000 /* Consider using a Bloom-filter */ |
634 | #define WHERE_SELFCULL 0x00800000 /* nOut reduced by extra WHERE terms */ |
635 | #define WHERE_OMIT_OFFSET 0x01000000 /* Set offset counter to zero */ |
636 | #define WHERE_VIEWSCAN 0x02000000 /* A full-scan of a VIEW or subquery */ |
637 | |
638 | #endif /* !defined(SQLITE_WHEREINT_H) */ |
639 | |