blob: 2ccc6ec0648e95afbbb851581ff700ed6a2c9098 [file] [log] [blame]
drhe54df422013-11-12 18:37:25 +00001/*
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
18/*
19** Trace output macros
20*/
21#if defined(SQLITE_TEST) || defined(SQLITE_DEBUG)
22/***/ int sqlite3WhereTrace = 0;
23#endif
24#if defined(SQLITE_DEBUG) \
25 && (defined(SQLITE_TEST) || defined(SQLITE_ENABLE_WHERETRACE))
26# define WHERETRACE(K,X) if(sqlite3WhereTrace&(K)) sqlite3DebugPrintf X
27# define WHERETRACE_ENABLED 1
28#else
29# define WHERETRACE(K,X)
30#endif
31
32/* Forward references
33*/
34typedef struct WhereClause WhereClause;
35typedef struct WhereMaskSet WhereMaskSet;
36typedef struct WhereOrInfo WhereOrInfo;
37typedef struct WhereAndInfo WhereAndInfo;
38typedef struct WhereLevel WhereLevel;
39typedef struct WhereLoop WhereLoop;
40typedef struct WherePath WherePath;
41typedef struct WhereTerm WhereTerm;
42typedef struct WhereLoopBuilder WhereLoopBuilder;
43typedef struct WhereScan WhereScan;
44typedef struct WhereOrCost WhereOrCost;
45typedef struct WhereOrSet WhereOrSet;
46
47/*
48** This object contains information needed to implement a single nested
49** loop in WHERE clause.
50**
51** Contrast this object with WhereLoop. This object describes the
52** implementation of the loop. WhereLoop describes the algorithm.
53** This object contains a pointer to the WhereLoop algorithm as one of
54** its elements.
55**
56** The WhereInfo object contains a single instance of this object for
57** each term in the FROM clause (which is to say, for each of the
58** nested loops as implemented). The order of WhereLevel objects determines
59** the loop nested order, with WhereInfo.a[0] being the outer loop and
60** WhereInfo.a[WhereInfo.nLevel-1] being the inner loop.
61*/
62struct WhereLevel {
63 int iLeftJoin; /* Memory cell used to implement LEFT OUTER JOIN */
64 int iTabCur; /* The VDBE cursor used to access the table */
65 int iIdxCur; /* The VDBE cursor used to access pIdx */
66 int addrBrk; /* Jump here to break out of the loop */
67 int addrNxt; /* Jump here to start the next IN combination */
drhcd8629e2013-11-13 12:27:25 +000068 int addrSkip; /* Jump here for next iteration of skip-scan */
drhe54df422013-11-12 18:37:25 +000069 int addrCont; /* Jump here to continue with the next loop cycle */
70 int addrFirst; /* First instruction of interior of the loop */
71 int addrBody; /* Beginning of the body of this loop */
72 u8 iFrom; /* Which entry in the FROM clause */
drhe39a7322014-02-03 14:04:11 +000073 u8 op, p3, p5; /* Opcode, P3 & P5 of the opcode that ends the loop */
drhe54df422013-11-12 18:37:25 +000074 int p1, p2; /* Operands of the opcode used to ends the loop */
75 union { /* Information that depends on pWLoop->wsFlags */
76 struct {
77 int nIn; /* Number of entries in aInLoop[] */
78 struct InLoop {
79 int iCur; /* The VDBE cursor used by this IN operator */
80 int addrInTop; /* Top of the IN loop */
81 u8 eEndLoopOp; /* IN Loop terminator. OP_Next or OP_Prev */
82 } *aInLoop; /* Information about each nested IN operator */
83 } in; /* Used when pWLoop->wsFlags&WHERE_IN_ABLE */
84 Index *pCovidx; /* Possible covering index for WHERE_MULTI_OR */
85 } u;
86 struct WhereLoop *pWLoop; /* The selected WhereLoop object */
87 Bitmask notReady; /* FROM entries not usable at this level */
dan6f9702e2014-11-01 20:38:06 +000088#ifdef SQLITE_ENABLE_STMT_SCANSTATUS
89 int addrVisit; /* Address at which row is visited */
90#endif
drhe54df422013-11-12 18:37:25 +000091};
92
93/*
94** Each instance of this object represents an algorithm for evaluating one
95** term of a join. Every term of the FROM clause will have at least
96** one corresponding WhereLoop object (unless INDEXED BY constraints
97** prevent a query solution - which is an error) and many terms of the
98** FROM clause will have multiple WhereLoop objects, each describing a
99** potential way of implementing that FROM-clause term, together with
100** dependencies and cost estimates for using the chosen algorithm.
101**
102** Query planning consists of building up a collection of these WhereLoop
103** objects, then computing a particular sequence of WhereLoop objects, with
104** one WhereLoop object per FROM clause term, that satisfy all dependencies
105** and that minimize the overall cost.
106*/
107struct WhereLoop {
108 Bitmask prereq; /* Bitmask of other loops that must run first */
109 Bitmask maskSelf; /* Bitmask identifying table iTab */
110#ifdef SQLITE_DEBUG
111 char cId; /* Symbolic ID of this loop for debugging use */
112#endif
113 u8 iTab; /* Position in FROM clause of table for this loop */
114 u8 iSortIdx; /* Sorting index number. 0==None */
115 LogEst rSetup; /* One-time setup cost (ex: create transient index) */
116 LogEst rRun; /* Cost of running each loop */
117 LogEst nOut; /* Estimated number of output rows */
118 union {
119 struct { /* Information for internal btree tables */
drh5e6790c2013-11-12 20:18:14 +0000120 u16 nEq; /* Number of equality constraints */
drhe54df422013-11-12 18:37:25 +0000121 Index *pIndex; /* Index used, or NULL */
122 } btree;
123 struct { /* Information for virtual tables */
124 int idxNum; /* Index number */
125 u8 needFree; /* True if sqlite3_free(idxStr) is needed */
drh0401ace2014-03-18 15:30:27 +0000126 i8 isOrdered; /* True if satisfies ORDER BY */
drhe54df422013-11-12 18:37:25 +0000127 u16 omitMask; /* Terms that may be omitted */
128 char *idxStr; /* Index identifier string */
129 } vtab;
130 } u;
131 u32 wsFlags; /* WHERE_* flags describing the plan */
132 u16 nLTerm; /* Number of entries in aLTerm[] */
drhc8bbce12014-10-21 01:05:09 +0000133 u16 nSkip; /* Number of NULL aLTerm[] entries */
drhe54df422013-11-12 18:37:25 +0000134 /**** whereLoopXfer() copies fields above ***********************/
135# define WHERE_LOOP_XFER_SZ offsetof(WhereLoop,nLSlot)
136 u16 nLSlot; /* Number of slots allocated for aLTerm[] */
137 WhereTerm **aLTerm; /* WhereTerms used */
138 WhereLoop *pNextLoop; /* Next WhereLoop object in the WhereClause */
drhc8bbce12014-10-21 01:05:09 +0000139 WhereTerm *aLTermSpace[3]; /* Initial aLTerm[] space */
drhe54df422013-11-12 18:37:25 +0000140};
141
142/* This object holds the prerequisites and the cost of running a
143** subquery on one operand of an OR operator in the WHERE clause.
144** See WhereOrSet for additional information
145*/
146struct WhereOrCost {
147 Bitmask prereq; /* Prerequisites */
148 LogEst rRun; /* Cost of running this subquery */
149 LogEst nOut; /* Number of outputs for this subquery */
150};
151
152/* The WhereOrSet object holds a set of possible WhereOrCosts that
153** correspond to the subquery(s) of OR-clause processing. Only the
154** best N_OR_COST elements are retained.
155*/
156#define N_OR_COST 3
157struct WhereOrSet {
158 u16 n; /* Number of valid a[] entries */
159 WhereOrCost a[N_OR_COST]; /* Set of best costs */
160};
161
162
163/* Forward declaration of methods */
164static int whereLoopResize(sqlite3*, WhereLoop*, int);
165
166/*
167** Each instance of this object holds a sequence of WhereLoop objects
168** that implement some or all of a query plan.
169**
170** Think of each WhereLoop object as a node in a graph with arcs
171** showing dependencies and costs for travelling between nodes. (That is
172** not a completely accurate description because WhereLoop costs are a
173** vector, not a scalar, and because dependencies are many-to-one, not
174** one-to-one as are graph nodes. But it is a useful visualization aid.)
175** Then a WherePath object is a path through the graph that visits some
176** or all of the WhereLoop objects once.
177**
178** The "solver" works by creating the N best WherePath objects of length
179** 1. Then using those as a basis to compute the N best WherePath objects
180** of length 2. And so forth until the length of WherePaths equals the
181** number of nodes in the FROM clause. The best (lowest cost) WherePath
peter.d.reid60ec9142014-09-06 16:39:46 +0000182** at the end is the chosen query plan.
drhe54df422013-11-12 18:37:25 +0000183*/
184struct WherePath {
185 Bitmask maskLoop; /* Bitmask of all WhereLoop objects in this path */
186 Bitmask revLoop; /* aLoop[]s that should be reversed for ORDER BY */
187 LogEst nRow; /* Estimated number of rows generated by this path */
188 LogEst rCost; /* Total cost of this path */
dan50ae31e2014-08-08 16:52:28 +0000189 LogEst rUnsorted; /* Total cost of this path ignoring sorting costs */
drh0401ace2014-03-18 15:30:27 +0000190 i8 isOrdered; /* No. of ORDER BY terms satisfied. -1 for unknown */
drhe54df422013-11-12 18:37:25 +0000191 WhereLoop **aLoop; /* Array of WhereLoop objects implementing this path */
192};
193
194/*
195** The query generator uses an array of instances of this structure to
196** help it analyze the subexpressions of the WHERE clause. Each WHERE
197** clause subexpression is separated from the others by AND operators,
198** usually, or sometimes subexpressions separated by OR.
199**
200** All WhereTerms are collected into a single WhereClause structure.
201** The following identity holds:
202**
203** WhereTerm.pWC->a[WhereTerm.idx] == WhereTerm
204**
205** When a term is of the form:
206**
207** X <op> <expr>
208**
209** where X is a column name and <op> is one of certain operators,
210** then WhereTerm.leftCursor and WhereTerm.u.leftColumn record the
211** cursor number and column number for X. WhereTerm.eOperator records
212** the <op> using a bitmask encoding defined by WO_xxx below. The
213** use of a bitmask encoding for the operator allows us to search
214** quickly for terms that match any of several different operators.
215**
216** A WhereTerm might also be two or more subterms connected by OR:
217**
218** (t1.X <op> <expr>) OR (t1.Y <op> <expr>) OR ....
219**
220** In this second case, wtFlag has the TERM_ORINFO bit set and eOperator==WO_OR
221** and the WhereTerm.u.pOrInfo field points to auxiliary information that
222** is collected about the OR clause.
223**
224** If a term in the WHERE clause does not match either of the two previous
225** categories, then eOperator==0. The WhereTerm.pExpr field is still set
226** to the original subexpression content and wtFlags is set up appropriately
227** but no other fields in the WhereTerm object are meaningful.
228**
229** When eOperator!=0, prereqRight and prereqAll record sets of cursor numbers,
230** but they do so indirectly. A single WhereMaskSet structure translates
231** cursor number into bits and the translated bit is stored in the prereq
232** fields. The translation is used in order to maximize the number of
233** bits that will fit in a Bitmask. The VDBE cursor numbers might be
234** spread out over the non-negative integers. For example, the cursor
235** numbers might be 3, 8, 9, 10, 20, 23, 41, and 45. The WhereMaskSet
236** translates these sparse cursor numbers into consecutive integers
237** beginning with 0 in order to make the best possible use of the available
238** bits in the Bitmask. So, in the example above, the cursor numbers
239** would be mapped into integers 0 through 7.
240**
241** The number of terms in a join is limited by the number of bits
242** in prereqRight and prereqAll. The default is 64 bits, hence SQLite
243** is only able to process joins with 64 or fewer tables.
244*/
245struct WhereTerm {
246 Expr *pExpr; /* Pointer to the subexpression that is this term */
247 int iParent; /* Disable pWC->a[iParent] when this term disabled */
248 int leftCursor; /* Cursor number of X in "X <op> <expr>" */
249 union {
250 int leftColumn; /* Column number of X in "X <op> <expr>" */
251 WhereOrInfo *pOrInfo; /* Extra information if (eOperator & WO_OR)!=0 */
252 WhereAndInfo *pAndInfo; /* Extra information if (eOperator& WO_AND)!=0 */
253 } u;
254 LogEst truthProb; /* Probability of truth for this expression */
255 u16 eOperator; /* A WO_xx value describing <op> */
256 u8 wtFlags; /* TERM_xxx bit flags. See below */
257 u8 nChild; /* Number of children that must disable us */
258 WhereClause *pWC; /* The clause this term is part of */
259 Bitmask prereqRight; /* Bitmask of tables used by pExpr->pRight */
260 Bitmask prereqAll; /* Bitmask of tables referenced by pExpr */
261};
262
263/*
264** Allowed values of WhereTerm.wtFlags
265*/
266#define TERM_DYNAMIC 0x01 /* Need to call sqlite3ExprDelete(db, pExpr) */
267#define TERM_VIRTUAL 0x02 /* Added by the optimizer. Do not code */
268#define TERM_CODED 0x04 /* This term is already coded */
269#define TERM_COPIED 0x08 /* Has a child */
270#define TERM_ORINFO 0x10 /* Need to free the WhereTerm.u.pOrInfo object */
271#define TERM_ANDINFO 0x20 /* Need to free the WhereTerm.u.pAndInfo obj */
272#define TERM_OR_OK 0x40 /* Used during OR-clause processing */
273#ifdef SQLITE_ENABLE_STAT3_OR_STAT4
274# define TERM_VNULL 0x80 /* Manufactured x>NULL or x<=NULL term */
275#else
276# define TERM_VNULL 0x00 /* Disabled if not using stat3 */
277#endif
278
279/*
280** An instance of the WhereScan object is used as an iterator for locating
281** terms in the WHERE clause that are useful to the query planner.
282*/
283struct WhereScan {
284 WhereClause *pOrigWC; /* Original, innermost WhereClause */
285 WhereClause *pWC; /* WhereClause currently being scanned */
286 char *zCollName; /* Required collating sequence, if not NULL */
287 char idxaff; /* Must match this affinity, if zCollName!=NULL */
288 unsigned char nEquiv; /* Number of entries in aEquiv[] */
289 unsigned char iEquiv; /* Next unused slot in aEquiv[] */
290 u32 opMask; /* Acceptable operators */
291 int k; /* Resume scanning at this->pWC->a[this->k] */
292 int aEquiv[22]; /* Cursor,Column pairs for equivalence classes */
293};
294
295/*
296** An instance of the following structure holds all information about a
297** WHERE clause. Mostly this is a container for one or more WhereTerms.
298**
299** Explanation of pOuter: For a WHERE clause of the form
300**
301** a AND ((b AND c) OR (d AND e)) AND f
302**
303** There are separate WhereClause objects for the whole clause and for
304** the subclauses "(b AND c)" and "(d AND e)". The pOuter field of the
305** subclauses points to the WhereClause object for the whole clause.
306*/
307struct WhereClause {
308 WhereInfo *pWInfo; /* WHERE clause processing context */
309 WhereClause *pOuter; /* Outer conjunction */
310 u8 op; /* Split operator. TK_AND or TK_OR */
311 int nTerm; /* Number of terms */
312 int nSlot; /* Number of entries in a[] */
313 WhereTerm *a; /* Each a[] describes a term of the WHERE cluase */
314#if defined(SQLITE_SMALL_STACK)
315 WhereTerm aStatic[1]; /* Initial static space for a[] */
316#else
317 WhereTerm aStatic[8]; /* Initial static space for a[] */
318#endif
319};
320
321/*
322** A WhereTerm with eOperator==WO_OR has its u.pOrInfo pointer set to
323** a dynamically allocated instance of the following structure.
324*/
325struct WhereOrInfo {
326 WhereClause wc; /* Decomposition into subterms */
327 Bitmask indexable; /* Bitmask of all indexable tables in the clause */
328};
329
330/*
331** A WhereTerm with eOperator==WO_AND has its u.pAndInfo pointer set to
332** a dynamically allocated instance of the following structure.
333*/
334struct WhereAndInfo {
335 WhereClause wc; /* The subexpression broken out */
336};
337
338/*
339** An instance of the following structure keeps track of a mapping
340** between VDBE cursor numbers and bits of the bitmasks in WhereTerm.
341**
342** The VDBE cursor numbers are small integers contained in
343** SrcList_item.iCursor and Expr.iTable fields. For any given WHERE
344** clause, the cursor numbers might not begin with 0 and they might
345** contain gaps in the numbering sequence. But we want to make maximum
346** use of the bits in our bitmasks. This structure provides a mapping
347** from the sparse cursor numbers into consecutive integers beginning
348** with 0.
349**
350** If WhereMaskSet.ix[A]==B it means that The A-th bit of a Bitmask
351** corresponds VDBE cursor number B. The A-th bit of a bitmask is 1<<A.
352**
353** For example, if the WHERE clause expression used these VDBE
354** cursors: 4, 5, 8, 29, 57, 73. Then the WhereMaskSet structure
355** would map those cursor numbers into bits 0 through 5.
356**
357** Note that the mapping is not necessarily ordered. In the example
358** above, the mapping might go like this: 4->3, 5->1, 8->2, 29->0,
359** 57->5, 73->4. Or one of 719 other combinations might be used. It
360** does not really matter. What is important is that sparse cursor
361** numbers all get mapped into bit numbers that begin with 0 and contain
362** no gaps.
363*/
364struct WhereMaskSet {
365 int n; /* Number of assigned cursor values */
366 int ix[BMS]; /* Cursor assigned to each bit */
367};
368
369/*
370** This object is a convenience wrapper holding all information needed
371** to construct WhereLoop objects for a particular query.
372*/
373struct WhereLoopBuilder {
374 WhereInfo *pWInfo; /* Information about this WHERE */
375 WhereClause *pWC; /* WHERE clause terms */
376 ExprList *pOrderBy; /* ORDER BY clause */
377 WhereLoop *pNew; /* Template WhereLoop */
378 WhereOrSet *pOrSet; /* Record best loops here, if not NULL */
379#ifdef SQLITE_ENABLE_STAT3_OR_STAT4
380 UnpackedRecord *pRec; /* Probe for stat4 (if required) */
381 int nRecValid; /* Number of valid fields currently in pRec */
382#endif
383};
384
385/*
386** The WHERE clause processing routine has two halves. The
387** first part does the start of the WHERE loop and the second
388** half does the tail of the WHERE loop. An instance of
389** this structure is returned by the first half and passed
390** into the second half to give some continuity.
391**
392** An instance of this object holds the complete state of the query
393** planner.
394*/
395struct WhereInfo {
396 Parse *pParse; /* Parsing and code generating context */
397 SrcList *pTabList; /* List of tables in the join */
398 ExprList *pOrderBy; /* The ORDER BY clause or NULL */
399 ExprList *pResultSet; /* Result set. DISTINCT operates on these */
400 WhereLoop *pLoops; /* List of all WhereLoop objects */
401 Bitmask revMask; /* Mask of ORDER BY terms that need reversing */
402 LogEst nRowOut; /* Estimated number of output rows */
403 u16 wctrlFlags; /* Flags originally passed to sqlite3WhereBegin() */
drhddba0c22014-03-18 20:33:42 +0000404 i8 nOBSat; /* Number of ORDER BY terms satisfied by indices */
dan374cd782014-04-21 13:21:56 +0000405 u8 sorted; /* True if really sorted (not just grouped) */
drhe54df422013-11-12 18:37:25 +0000406 u8 okOnePass; /* Ok to use one-pass algorithm for UPDATE/DELETE */
407 u8 untestedTerms; /* Not all WHERE terms resolved by outer loop */
408 u8 eDistinct; /* One of the WHERE_DISTINCT_* values below */
409 u8 nLevel; /* Number of nested loop */
410 int iTop; /* The very beginning of the WHERE loop */
411 int iContinue; /* Jump here to continue with next record */
412 int iBreak; /* Jump here to break out of the loop */
413 int savedNQueryLoop; /* pParse->nQueryLoop outside the WHERE loop */
414 int aiCurOnePass[2]; /* OP_OpenWrite cursors for the ONEPASS opt */
415 WhereMaskSet sMaskSet; /* Map cursor numbers to bitmasks */
416 WhereClause sWC; /* Decomposition of the WHERE clause */
417 WhereLevel a[1]; /* Information about each nest loop in WHERE */
418};
419
420/*
421** Bitmasks for the operators on WhereTerm objects. These are all
422** operators that are of interest to the query planner. An
423** OR-ed combination of these values can be used when searching for
424** particular WhereTerms within a WhereClause.
425*/
426#define WO_IN 0x001
427#define WO_EQ 0x002
428#define WO_LT (WO_EQ<<(TK_LT-TK_EQ))
429#define WO_LE (WO_EQ<<(TK_LE-TK_EQ))
430#define WO_GT (WO_EQ<<(TK_GT-TK_EQ))
431#define WO_GE (WO_EQ<<(TK_GE-TK_EQ))
432#define WO_MATCH 0x040
433#define WO_ISNULL 0x080
434#define WO_OR 0x100 /* Two or more OR-connected terms */
435#define WO_AND 0x200 /* Two or more AND-connected terms */
436#define WO_EQUIV 0x400 /* Of the form A==B, both columns */
437#define WO_NOOP 0x800 /* This term does not restrict search space */
438
439#define WO_ALL 0xfff /* Mask of all possible WO_* values */
440#define WO_SINGLE 0x0ff /* Mask of all non-compound WO_* values */
441
442/*
443** These are definitions of bits in the WhereLoop.wsFlags field.
444** The particular combination of bits in each WhereLoop help to
445** determine the algorithm that WhereLoop represents.
446*/
447#define WHERE_COLUMN_EQ 0x00000001 /* x=EXPR */
448#define WHERE_COLUMN_RANGE 0x00000002 /* x<EXPR and/or x>EXPR */
449#define WHERE_COLUMN_IN 0x00000004 /* x IN (...) */
450#define WHERE_COLUMN_NULL 0x00000008 /* x IS NULL */
451#define WHERE_CONSTRAINT 0x0000000f /* Any of the WHERE_COLUMN_xxx values */
452#define WHERE_TOP_LIMIT 0x00000010 /* x<EXPR or x<=EXPR constraint */
453#define WHERE_BTM_LIMIT 0x00000020 /* x>EXPR or x>=EXPR constraint */
454#define WHERE_BOTH_LIMIT 0x00000030 /* Both x>EXPR and x<EXPR */
455#define WHERE_IDX_ONLY 0x00000040 /* Use index only - omit table */
456#define WHERE_IPK 0x00000100 /* x is the INTEGER PRIMARY KEY */
457#define WHERE_INDEXED 0x00000200 /* WhereLoop.u.btree.pIndex is valid */
458#define WHERE_VIRTUALTABLE 0x00000400 /* WhereLoop.u.vtab is valid */
459#define WHERE_IN_ABLE 0x00000800 /* Able to support an IN operator */
460#define WHERE_ONEROW 0x00001000 /* Selects no more than one row */
461#define WHERE_MULTI_OR 0x00002000 /* OR using multiple indices */
462#define WHERE_AUTO_INDEX 0x00004000 /* Uses an ephemeral index */
drh2e5ef4e2013-11-13 16:58:54 +0000463#define WHERE_SKIPSCAN 0x00008000 /* Uses the skip-scan algorithm */
drhe39a7322014-02-03 14:04:11 +0000464#define WHERE_UNQ_WANTED 0x00010000 /* WHERE_ONEROW would have been helpful*/
drh051575c2014-10-25 12:28:25 +0000465#define WHERE_PARTIALIDX 0x00020000 /* The automatic index is partial */