blob: 6bbc4af39b889aa909da786003d0f4fa63f90951 [file] [log] [blame]
drh75897232000-05-29 14:26:00 +00001/*
drhb19a2bc2001-09-16 00:13:26 +00002** 2001 September 15
drh75897232000-05-29 14:26:00 +00003**
drhb19a2bc2001-09-16 00:13:26 +00004** The author disclaims copyright to this source code. In place of
5** a legal notice, here is a blessing:
drh75897232000-05-29 14:26:00 +00006**
drhb19a2bc2001-09-16 00:13:26 +00007** 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.
drh75897232000-05-29 14:26:00 +000010**
11*************************************************************************
12** This module contains C code that generates VDBE code used to process
drh909626d2008-05-30 14:58:37 +000013** the WHERE clause of SQL statements. This module is responsible for
drh51669862004-12-18 18:40:26 +000014** 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".
drh75897232000-05-29 14:26:00 +000018**
danielk1977e672c8e2009-05-22 15:43:26 +000019** $Id: where.c,v 1.397 2009/05/22 15:43:27 danielk1977 Exp $
drh75897232000-05-29 14:26:00 +000020*/
21#include "sqliteInt.h"
22
23/*
drh51147ba2005-07-23 22:59:55 +000024** Trace output macros
25*/
26#if defined(SQLITE_TEST) || defined(SQLITE_DEBUG)
mlcreech3a00f902008-03-04 17:45:01 +000027int sqlite3WhereTrace = 0;
drhe8f52c52008-07-12 14:52:20 +000028#endif
drh85799a42009-04-07 13:48:11 +000029#if defined(SQLITE_TEST) && defined(SQLITE_DEBUG)
mlcreech3a00f902008-03-04 17:45:01 +000030# define WHERETRACE(X) if(sqlite3WhereTrace) sqlite3DebugPrintf X
drh51147ba2005-07-23 22:59:55 +000031#else
drh4f0c5872007-03-26 22:05:01 +000032# define WHERETRACE(X)
drh51147ba2005-07-23 22:59:55 +000033#endif
34
drh0fcef5e2005-07-19 17:38:22 +000035/* Forward reference
36*/
37typedef struct WhereClause WhereClause;
drh111a6a72008-12-21 03:51:16 +000038typedef struct WhereMaskSet WhereMaskSet;
drh700a2262008-12-17 19:22:15 +000039typedef struct WhereOrInfo WhereOrInfo;
40typedef struct WhereAndInfo WhereAndInfo;
drh111a6a72008-12-21 03:51:16 +000041typedef struct WhereCost WhereCost;
drh0aa74ed2005-07-16 13:33:20 +000042
43/*
drh75897232000-05-29 14:26:00 +000044** The query generator uses an array of instances of this structure to
45** help it analyze the subexpressions of the WHERE clause. Each WHERE
drh61495262009-04-22 15:32:59 +000046** clause subexpression is separated from the others by AND operators,
47** usually, or sometimes subexpressions separated by OR.
drh51669862004-12-18 18:40:26 +000048**
drh0fcef5e2005-07-19 17:38:22 +000049** All WhereTerms are collected into a single WhereClause structure.
50** The following identity holds:
drh51669862004-12-18 18:40:26 +000051**
drh0fcef5e2005-07-19 17:38:22 +000052** WhereTerm.pWC->a[WhereTerm.idx] == WhereTerm
drh51669862004-12-18 18:40:26 +000053**
drh0fcef5e2005-07-19 17:38:22 +000054** When a term is of the form:
55**
56** X <op> <expr>
57**
58** where X is a column name and <op> is one of certain operators,
drh700a2262008-12-17 19:22:15 +000059** then WhereTerm.leftCursor and WhereTerm.u.leftColumn record the
60** cursor number and column number for X. WhereTerm.eOperator records
drh51147ba2005-07-23 22:59:55 +000061** the <op> using a bitmask encoding defined by WO_xxx below. The
62** use of a bitmask encoding for the operator allows us to search
63** quickly for terms that match any of several different operators.
drh0fcef5e2005-07-19 17:38:22 +000064**
drh700a2262008-12-17 19:22:15 +000065** A WhereTerm might also be two or more subterms connected by OR:
66**
67** (t1.X <op> <expr>) OR (t1.Y <op> <expr>) OR ....
68**
69** In this second case, wtFlag as the TERM_ORINFO set and eOperator==WO_OR
70** and the WhereTerm.u.pOrInfo field points to auxiliary information that
71** is collected about the
72**
73** If a term in the WHERE clause does not match either of the two previous
74** categories, then eOperator==0. The WhereTerm.pExpr field is still set
75** to the original subexpression content and wtFlags is set up appropriately
76** but no other fields in the WhereTerm object are meaningful.
77**
78** When eOperator!=0, prereqRight and prereqAll record sets of cursor numbers,
drh111a6a72008-12-21 03:51:16 +000079** but they do so indirectly. A single WhereMaskSet structure translates
drh51669862004-12-18 18:40:26 +000080** cursor number into bits and the translated bit is stored in the prereq
81** fields. The translation is used in order to maximize the number of
82** bits that will fit in a Bitmask. The VDBE cursor numbers might be
83** spread out over the non-negative integers. For example, the cursor
drh111a6a72008-12-21 03:51:16 +000084** numbers might be 3, 8, 9, 10, 20, 23, 41, and 45. The WhereMaskSet
drh51669862004-12-18 18:40:26 +000085** translates these sparse cursor numbers into consecutive integers
86** beginning with 0 in order to make the best possible use of the available
87** bits in the Bitmask. So, in the example above, the cursor numbers
88** would be mapped into integers 0 through 7.
drh6a1e0712008-12-05 15:24:15 +000089**
90** The number of terms in a join is limited by the number of bits
91** in prereqRight and prereqAll. The default is 64 bits, hence SQLite
92** is only able to process joins with 64 or fewer tables.
drh75897232000-05-29 14:26:00 +000093*/
drh0aa74ed2005-07-16 13:33:20 +000094typedef struct WhereTerm WhereTerm;
95struct WhereTerm {
drh165be382008-12-05 02:36:33 +000096 Expr *pExpr; /* Pointer to the subexpression that is this term */
drhec1724e2008-12-09 01:32:03 +000097 int iParent; /* Disable pWC->a[iParent] when this term disabled */
98 int leftCursor; /* Cursor number of X in "X <op> <expr>" */
drh700a2262008-12-17 19:22:15 +000099 union {
100 int leftColumn; /* Column number of X in "X <op> <expr>" */
101 WhereOrInfo *pOrInfo; /* Extra information if eOperator==WO_OR */
102 WhereAndInfo *pAndInfo; /* Extra information if eOperator==WO_AND */
103 } u;
drhb52076c2006-01-23 13:22:09 +0000104 u16 eOperator; /* A WO_xx value describing <op> */
drh165be382008-12-05 02:36:33 +0000105 u8 wtFlags; /* TERM_xxx bit flags. See below */
drh45b1ee42005-08-02 17:48:22 +0000106 u8 nChild; /* Number of children that must disable us */
drh0fcef5e2005-07-19 17:38:22 +0000107 WhereClause *pWC; /* The clause this term is part of */
drh165be382008-12-05 02:36:33 +0000108 Bitmask prereqRight; /* Bitmask of tables used by pExpr->pRight */
109 Bitmask prereqAll; /* Bitmask of tables referenced by pExpr */
drh75897232000-05-29 14:26:00 +0000110};
111
112/*
drh165be382008-12-05 02:36:33 +0000113** Allowed values of WhereTerm.wtFlags
drh0aa74ed2005-07-16 13:33:20 +0000114*/
drh633e6d52008-07-28 19:34:53 +0000115#define TERM_DYNAMIC 0x01 /* Need to call sqlite3ExprDelete(db, pExpr) */
drh6c30be82005-07-29 15:10:17 +0000116#define TERM_VIRTUAL 0x02 /* Added by the optimizer. Do not code */
117#define TERM_CODED 0x04 /* This term is already coded */
drh45b1ee42005-08-02 17:48:22 +0000118#define TERM_COPIED 0x08 /* Has a child */
drh700a2262008-12-17 19:22:15 +0000119#define TERM_ORINFO 0x10 /* Need to free the WhereTerm.u.pOrInfo object */
120#define TERM_ANDINFO 0x20 /* Need to free the WhereTerm.u.pAndInfo obj */
121#define TERM_OR_OK 0x40 /* Used during OR-clause processing */
drh0aa74ed2005-07-16 13:33:20 +0000122
123/*
124** An instance of the following structure holds all information about a
125** WHERE clause. Mostly this is a container for one or more WhereTerms.
126*/
drh0aa74ed2005-07-16 13:33:20 +0000127struct WhereClause {
drhfe05af82005-07-21 03:14:59 +0000128 Parse *pParse; /* The parser context */
drh111a6a72008-12-21 03:51:16 +0000129 WhereMaskSet *pMaskSet; /* Mapping of table cursor numbers to bitmasks */
danielk1977e672c8e2009-05-22 15:43:26 +0000130 Bitmask vmask; /* Bitmask identifying virtual table cursors */
drh29435252008-12-28 18:35:08 +0000131 u8 op; /* Split operator. TK_AND or TK_OR */
drh0aa74ed2005-07-16 13:33:20 +0000132 int nTerm; /* Number of terms */
133 int nSlot; /* Number of entries in a[] */
drh51147ba2005-07-23 22:59:55 +0000134 WhereTerm *a; /* Each a[] describes a term of the WHERE cluase */
drhec1724e2008-12-09 01:32:03 +0000135 WhereTerm aStatic[4]; /* Initial static space for a[] */
drhe23399f2005-07-22 00:31:39 +0000136};
137
138/*
drh700a2262008-12-17 19:22:15 +0000139** A WhereTerm with eOperator==WO_OR has its u.pOrInfo pointer set to
140** a dynamically allocated instance of the following structure.
141*/
142struct WhereOrInfo {
drh111a6a72008-12-21 03:51:16 +0000143 WhereClause wc; /* Decomposition into subterms */
drh1a58fe02008-12-20 02:06:13 +0000144 Bitmask indexable; /* Bitmask of all indexable tables in the clause */
drh700a2262008-12-17 19:22:15 +0000145};
146
147/*
148** A WhereTerm with eOperator==WO_AND has its u.pAndInfo pointer set to
149** a dynamically allocated instance of the following structure.
150*/
151struct WhereAndInfo {
drh29435252008-12-28 18:35:08 +0000152 WhereClause wc; /* The subexpression broken out */
drh700a2262008-12-17 19:22:15 +0000153};
154
155/*
drh6a3ea0e2003-05-02 14:32:12 +0000156** An instance of the following structure keeps track of a mapping
drh0aa74ed2005-07-16 13:33:20 +0000157** between VDBE cursor numbers and bits of the bitmasks in WhereTerm.
drh51669862004-12-18 18:40:26 +0000158**
159** The VDBE cursor numbers are small integers contained in
160** SrcList_item.iCursor and Expr.iTable fields. For any given WHERE
161** clause, the cursor numbers might not begin with 0 and they might
162** contain gaps in the numbering sequence. But we want to make maximum
163** use of the bits in our bitmasks. This structure provides a mapping
164** from the sparse cursor numbers into consecutive integers beginning
165** with 0.
166**
drh111a6a72008-12-21 03:51:16 +0000167** If WhereMaskSet.ix[A]==B it means that The A-th bit of a Bitmask
drh51669862004-12-18 18:40:26 +0000168** corresponds VDBE cursor number B. The A-th bit of a bitmask is 1<<A.
169**
170** For example, if the WHERE clause expression used these VDBE
drh111a6a72008-12-21 03:51:16 +0000171** cursors: 4, 5, 8, 29, 57, 73. Then the WhereMaskSet structure
drh51669862004-12-18 18:40:26 +0000172** would map those cursor numbers into bits 0 through 5.
173**
174** Note that the mapping is not necessarily ordered. In the example
175** above, the mapping might go like this: 4->3, 5->1, 8->2, 29->0,
176** 57->5, 73->4. Or one of 719 other combinations might be used. It
177** does not really matter. What is important is that sparse cursor
178** numbers all get mapped into bit numbers that begin with 0 and contain
179** no gaps.
drh6a3ea0e2003-05-02 14:32:12 +0000180*/
drh111a6a72008-12-21 03:51:16 +0000181struct WhereMaskSet {
drh1398ad32005-01-19 23:24:50 +0000182 int n; /* Number of assigned cursor values */
danielk197723432972008-11-17 16:42:00 +0000183 int ix[BMS]; /* Cursor assigned to each bit */
drh6a3ea0e2003-05-02 14:32:12 +0000184};
185
drh111a6a72008-12-21 03:51:16 +0000186/*
187** A WhereCost object records a lookup strategy and the estimated
188** cost of pursuing that strategy.
189*/
190struct WhereCost {
191 WherePlan plan; /* The lookup strategy */
192 double rCost; /* Overall cost of pursuing this search strategy */
193 double nRow; /* Estimated number of output rows */
194};
drh0aa74ed2005-07-16 13:33:20 +0000195
drh6a3ea0e2003-05-02 14:32:12 +0000196/*
drh51147ba2005-07-23 22:59:55 +0000197** Bitmasks for the operators that indices are able to exploit. An
198** OR-ed combination of these values can be used when searching for
199** terms in the where clause.
200*/
drh165be382008-12-05 02:36:33 +0000201#define WO_IN 0x001
202#define WO_EQ 0x002
drh51147ba2005-07-23 22:59:55 +0000203#define WO_LT (WO_EQ<<(TK_LT-TK_EQ))
204#define WO_LE (WO_EQ<<(TK_LE-TK_EQ))
205#define WO_GT (WO_EQ<<(TK_GT-TK_EQ))
206#define WO_GE (WO_EQ<<(TK_GE-TK_EQ))
drh165be382008-12-05 02:36:33 +0000207#define WO_MATCH 0x040
208#define WO_ISNULL 0x080
drh700a2262008-12-17 19:22:15 +0000209#define WO_OR 0x100 /* Two or more OR-connected terms */
210#define WO_AND 0x200 /* Two or more AND-connected terms */
drh51147ba2005-07-23 22:59:55 +0000211
drhec1724e2008-12-09 01:32:03 +0000212#define WO_ALL 0xfff /* Mask of all possible WO_* values */
drh1a58fe02008-12-20 02:06:13 +0000213#define WO_SINGLE 0x0ff /* Mask of all non-compound WO_* values */
drhec1724e2008-12-09 01:32:03 +0000214
drh51147ba2005-07-23 22:59:55 +0000215/*
drh700a2262008-12-17 19:22:15 +0000216** Value for wsFlags returned by bestIndex() and stored in
217** WhereLevel.wsFlags. These flags determine which search
218** strategies are appropriate.
drhf2d315d2007-01-25 16:56:06 +0000219**
drh165be382008-12-05 02:36:33 +0000220** The least significant 12 bits is reserved as a mask for WO_ values above.
drh700a2262008-12-17 19:22:15 +0000221** The WhereLevel.wsFlags field is usually set to WO_IN|WO_EQ|WO_ISNULL.
222** But if the table is the right table of a left join, WhereLevel.wsFlags
223** is set to WO_IN|WO_EQ. The WhereLevel.wsFlags field can then be used as
drhf2d315d2007-01-25 16:56:06 +0000224** the "op" parameter to findTerm when we are resolving equality constraints.
225** ISNULL constraints will then not be used on the right table of a left
226** join. Tickets #2177 and #2189.
drh51147ba2005-07-23 22:59:55 +0000227*/
drh165be382008-12-05 02:36:33 +0000228#define WHERE_ROWID_EQ 0x00001000 /* rowid=EXPR or rowid IN (...) */
229#define WHERE_ROWID_RANGE 0x00002000 /* rowid<EXPR and/or rowid>EXPR */
drh46619d62009-04-24 14:51:42 +0000230#define WHERE_COLUMN_EQ 0x00010000 /* x=EXPR or x IN (...) or x IS NULL */
drh165be382008-12-05 02:36:33 +0000231#define WHERE_COLUMN_RANGE 0x00020000 /* x<EXPR and/or x>EXPR */
232#define WHERE_COLUMN_IN 0x00040000 /* x IN (...) */
drh46619d62009-04-24 14:51:42 +0000233#define WHERE_COLUMN_NULL 0x00080000 /* x IS NULL */
234#define WHERE_INDEXED 0x000f0000 /* Anything that uses an index */
235#define WHERE_IN_ABLE 0x000f1000 /* Able to support an IN operator */
drh165be382008-12-05 02:36:33 +0000236#define WHERE_TOP_LIMIT 0x00100000 /* x<EXPR or x<=EXPR constraint */
237#define WHERE_BTM_LIMIT 0x00200000 /* x>EXPR or x>=EXPR constraint */
238#define WHERE_IDX_ONLY 0x00800000 /* Use index only - omit table */
239#define WHERE_ORDERBY 0x01000000 /* Output will appear in correct order */
240#define WHERE_REVERSE 0x02000000 /* Scan in reverse order */
241#define WHERE_UNIQUE 0x04000000 /* Selects no more than one row */
242#define WHERE_VIRTUALTABLE 0x08000000 /* Use virtual-table processing */
243#define WHERE_MULTI_OR 0x10000000 /* OR using multiple indices */
drh51147ba2005-07-23 22:59:55 +0000244
245/*
drh0aa74ed2005-07-16 13:33:20 +0000246** Initialize a preallocated WhereClause structure.
drh75897232000-05-29 14:26:00 +0000247*/
drh7b4fc6a2007-02-06 13:26:32 +0000248static void whereClauseInit(
249 WhereClause *pWC, /* The WhereClause to be initialized */
250 Parse *pParse, /* The parsing context */
drh111a6a72008-12-21 03:51:16 +0000251 WhereMaskSet *pMaskSet /* Mapping from table cursor numbers to bitmasks */
drh7b4fc6a2007-02-06 13:26:32 +0000252){
drhfe05af82005-07-21 03:14:59 +0000253 pWC->pParse = pParse;
drh7b4fc6a2007-02-06 13:26:32 +0000254 pWC->pMaskSet = pMaskSet;
drh0aa74ed2005-07-16 13:33:20 +0000255 pWC->nTerm = 0;
drhcad651e2007-04-20 12:22:01 +0000256 pWC->nSlot = ArraySize(pWC->aStatic);
drh0aa74ed2005-07-16 13:33:20 +0000257 pWC->a = pWC->aStatic;
danielk1977e672c8e2009-05-22 15:43:26 +0000258 pWC->vmask = 0;
drh0aa74ed2005-07-16 13:33:20 +0000259}
260
drh700a2262008-12-17 19:22:15 +0000261/* Forward reference */
262static void whereClauseClear(WhereClause*);
263
264/*
265** Deallocate all memory associated with a WhereOrInfo object.
266*/
267static void whereOrInfoDelete(sqlite3 *db, WhereOrInfo *p){
drh5bd98ae2009-01-07 18:24:03 +0000268 whereClauseClear(&p->wc);
269 sqlite3DbFree(db, p);
drh700a2262008-12-17 19:22:15 +0000270}
271
272/*
273** Deallocate all memory associated with a WhereAndInfo object.
274*/
275static void whereAndInfoDelete(sqlite3 *db, WhereAndInfo *p){
drh5bd98ae2009-01-07 18:24:03 +0000276 whereClauseClear(&p->wc);
277 sqlite3DbFree(db, p);
drh700a2262008-12-17 19:22:15 +0000278}
279
drh0aa74ed2005-07-16 13:33:20 +0000280/*
281** Deallocate a WhereClause structure. The WhereClause structure
282** itself is not freed. This routine is the inverse of whereClauseInit().
283*/
284static void whereClauseClear(WhereClause *pWC){
285 int i;
286 WhereTerm *a;
drh633e6d52008-07-28 19:34:53 +0000287 sqlite3 *db = pWC->pParse->db;
drh0aa74ed2005-07-16 13:33:20 +0000288 for(i=pWC->nTerm-1, a=pWC->a; i>=0; i--, a++){
drh165be382008-12-05 02:36:33 +0000289 if( a->wtFlags & TERM_DYNAMIC ){
drh633e6d52008-07-28 19:34:53 +0000290 sqlite3ExprDelete(db, a->pExpr);
drh0aa74ed2005-07-16 13:33:20 +0000291 }
drh700a2262008-12-17 19:22:15 +0000292 if( a->wtFlags & TERM_ORINFO ){
293 whereOrInfoDelete(db, a->u.pOrInfo);
294 }else if( a->wtFlags & TERM_ANDINFO ){
295 whereAndInfoDelete(db, a->u.pAndInfo);
296 }
drh0aa74ed2005-07-16 13:33:20 +0000297 }
298 if( pWC->a!=pWC->aStatic ){
drh633e6d52008-07-28 19:34:53 +0000299 sqlite3DbFree(db, pWC->a);
drh0aa74ed2005-07-16 13:33:20 +0000300 }
301}
302
303/*
drh6a1e0712008-12-05 15:24:15 +0000304** Add a single new WhereTerm entry to the WhereClause object pWC.
305** The new WhereTerm object is constructed from Expr p and with wtFlags.
306** The index in pWC->a[] of the new WhereTerm is returned on success.
307** 0 is returned if the new WhereTerm could not be added due to a memory
308** allocation error. The memory allocation failure will be recorded in
309** the db->mallocFailed flag so that higher-level functions can detect it.
310**
311** This routine will increase the size of the pWC->a[] array as necessary.
drh9eb20282005-08-24 03:52:18 +0000312**
drh165be382008-12-05 02:36:33 +0000313** If the wtFlags argument includes TERM_DYNAMIC, then responsibility
drh6a1e0712008-12-05 15:24:15 +0000314** for freeing the expression p is assumed by the WhereClause object pWC.
315** This is true even if this routine fails to allocate a new WhereTerm.
drhb63a53d2007-03-31 01:34:44 +0000316**
drh9eb20282005-08-24 03:52:18 +0000317** WARNING: This routine might reallocate the space used to store
drh909626d2008-05-30 14:58:37 +0000318** WhereTerms. All pointers to WhereTerms should be invalidated after
drh9eb20282005-08-24 03:52:18 +0000319** calling this routine. Such pointers may be reinitialized by referencing
320** the pWC->a[] array.
drh0aa74ed2005-07-16 13:33:20 +0000321*/
drhec1724e2008-12-09 01:32:03 +0000322static int whereClauseInsert(WhereClause *pWC, Expr *p, u8 wtFlags){
drh0aa74ed2005-07-16 13:33:20 +0000323 WhereTerm *pTerm;
drh9eb20282005-08-24 03:52:18 +0000324 int idx;
drh0aa74ed2005-07-16 13:33:20 +0000325 if( pWC->nTerm>=pWC->nSlot ){
326 WhereTerm *pOld = pWC->a;
drh633e6d52008-07-28 19:34:53 +0000327 sqlite3 *db = pWC->pParse->db;
328 pWC->a = sqlite3DbMallocRaw(db, sizeof(pWC->a[0])*pWC->nSlot*2 );
drhb63a53d2007-03-31 01:34:44 +0000329 if( pWC->a==0 ){
drh165be382008-12-05 02:36:33 +0000330 if( wtFlags & TERM_DYNAMIC ){
drh633e6d52008-07-28 19:34:53 +0000331 sqlite3ExprDelete(db, p);
drhb63a53d2007-03-31 01:34:44 +0000332 }
drhf998b732007-11-26 13:36:00 +0000333 pWC->a = pOld;
drhb63a53d2007-03-31 01:34:44 +0000334 return 0;
335 }
drh0aa74ed2005-07-16 13:33:20 +0000336 memcpy(pWC->a, pOld, sizeof(pWC->a[0])*pWC->nTerm);
337 if( pOld!=pWC->aStatic ){
drh633e6d52008-07-28 19:34:53 +0000338 sqlite3DbFree(db, pOld);
drh0aa74ed2005-07-16 13:33:20 +0000339 }
drh6a1e0712008-12-05 15:24:15 +0000340 pWC->nSlot = sqlite3DbMallocSize(db, pWC->a)/sizeof(pWC->a[0]);
drh0aa74ed2005-07-16 13:33:20 +0000341 }
drh6a1e0712008-12-05 15:24:15 +0000342 pTerm = &pWC->a[idx = pWC->nTerm++];
drh0fcef5e2005-07-19 17:38:22 +0000343 pTerm->pExpr = p;
drh165be382008-12-05 02:36:33 +0000344 pTerm->wtFlags = wtFlags;
drh0fcef5e2005-07-19 17:38:22 +0000345 pTerm->pWC = pWC;
drh45b1ee42005-08-02 17:48:22 +0000346 pTerm->iParent = -1;
drh9eb20282005-08-24 03:52:18 +0000347 return idx;
drh0aa74ed2005-07-16 13:33:20 +0000348}
drh75897232000-05-29 14:26:00 +0000349
350/*
drh51669862004-12-18 18:40:26 +0000351** This routine identifies subexpressions in the WHERE clause where
drhb6fb62d2005-09-20 08:47:20 +0000352** each subexpression is separated by the AND operator or some other
drh6c30be82005-07-29 15:10:17 +0000353** operator specified in the op parameter. The WhereClause structure
354** is filled with pointers to subexpressions. For example:
drh75897232000-05-29 14:26:00 +0000355**
drh51669862004-12-18 18:40:26 +0000356** WHERE a=='hello' AND coalesce(b,11)<10 AND (c+12!=d OR c==22)
357** \________/ \_______________/ \________________/
358** slot[0] slot[1] slot[2]
359**
360** The original WHERE clause in pExpr is unaltered. All this routine
drh51147ba2005-07-23 22:59:55 +0000361** does is make slot[] entries point to substructure within pExpr.
drh51669862004-12-18 18:40:26 +0000362**
drh51147ba2005-07-23 22:59:55 +0000363** In the previous sentence and in the diagram, "slot[]" refers to
drh902b9ee2008-12-05 17:17:07 +0000364** the WhereClause.a[] array. The slot[] array grows as needed to contain
drh51147ba2005-07-23 22:59:55 +0000365** all terms of the WHERE clause.
drh75897232000-05-29 14:26:00 +0000366*/
drh6c30be82005-07-29 15:10:17 +0000367static void whereSplit(WhereClause *pWC, Expr *pExpr, int op){
drh29435252008-12-28 18:35:08 +0000368 pWC->op = (u8)op;
drh0aa74ed2005-07-16 13:33:20 +0000369 if( pExpr==0 ) return;
drh6c30be82005-07-29 15:10:17 +0000370 if( pExpr->op!=op ){
drh0aa74ed2005-07-16 13:33:20 +0000371 whereClauseInsert(pWC, pExpr, 0);
drh75897232000-05-29 14:26:00 +0000372 }else{
drh6c30be82005-07-29 15:10:17 +0000373 whereSplit(pWC, pExpr->pLeft, op);
374 whereSplit(pWC, pExpr->pRight, op);
drh75897232000-05-29 14:26:00 +0000375 }
drh75897232000-05-29 14:26:00 +0000376}
377
378/*
drh61495262009-04-22 15:32:59 +0000379** Initialize an expression mask set (a WhereMaskSet object)
drh6a3ea0e2003-05-02 14:32:12 +0000380*/
381#define initMaskSet(P) memset(P, 0, sizeof(*P))
382
383/*
drh1398ad32005-01-19 23:24:50 +0000384** Return the bitmask for the given cursor number. Return 0 if
385** iCursor is not in the set.
drh6a3ea0e2003-05-02 14:32:12 +0000386*/
drh111a6a72008-12-21 03:51:16 +0000387static Bitmask getMask(WhereMaskSet *pMaskSet, int iCursor){
drh6a3ea0e2003-05-02 14:32:12 +0000388 int i;
drh3500ed62009-05-05 15:46:43 +0000389 assert( pMaskSet->n<=sizeof(Bitmask)*8 );
drh6a3ea0e2003-05-02 14:32:12 +0000390 for(i=0; i<pMaskSet->n; i++){
drh51669862004-12-18 18:40:26 +0000391 if( pMaskSet->ix[i]==iCursor ){
392 return ((Bitmask)1)<<i;
393 }
drh6a3ea0e2003-05-02 14:32:12 +0000394 }
drh6a3ea0e2003-05-02 14:32:12 +0000395 return 0;
396}
397
398/*
drh1398ad32005-01-19 23:24:50 +0000399** Create a new mask for cursor iCursor.
drh0fcef5e2005-07-19 17:38:22 +0000400**
401** There is one cursor per table in the FROM clause. The number of
402** tables in the FROM clause is limited by a test early in the
drhb6fb62d2005-09-20 08:47:20 +0000403** sqlite3WhereBegin() routine. So we know that the pMaskSet->ix[]
drh0fcef5e2005-07-19 17:38:22 +0000404** array will never overflow.
drh1398ad32005-01-19 23:24:50 +0000405*/
drh111a6a72008-12-21 03:51:16 +0000406static void createMask(WhereMaskSet *pMaskSet, int iCursor){
drhcad651e2007-04-20 12:22:01 +0000407 assert( pMaskSet->n < ArraySize(pMaskSet->ix) );
drh0fcef5e2005-07-19 17:38:22 +0000408 pMaskSet->ix[pMaskSet->n++] = iCursor;
drh1398ad32005-01-19 23:24:50 +0000409}
410
411/*
drh75897232000-05-29 14:26:00 +0000412** This routine walks (recursively) an expression tree and generates
413** a bitmask indicating which tables are used in that expression
drh6a3ea0e2003-05-02 14:32:12 +0000414** tree.
drh75897232000-05-29 14:26:00 +0000415**
416** In order for this routine to work, the calling function must have
drh7d10d5a2008-08-20 16:35:10 +0000417** previously invoked sqlite3ResolveExprNames() on the expression. See
drh75897232000-05-29 14:26:00 +0000418** the header comment on that routine for additional information.
drh7d10d5a2008-08-20 16:35:10 +0000419** The sqlite3ResolveExprNames() routines looks for column names and
drh6a3ea0e2003-05-02 14:32:12 +0000420** sets their opcodes to TK_COLUMN and their Expr.iTable fields to
drh51147ba2005-07-23 22:59:55 +0000421** the VDBE cursor number of the table. This routine just has to
422** translate the cursor numbers into bitmask values and OR all
423** the bitmasks together.
drh75897232000-05-29 14:26:00 +0000424*/
drh111a6a72008-12-21 03:51:16 +0000425static Bitmask exprListTableUsage(WhereMaskSet*, ExprList*);
426static Bitmask exprSelectTableUsage(WhereMaskSet*, Select*);
427static Bitmask exprTableUsage(WhereMaskSet *pMaskSet, Expr *p){
drh51669862004-12-18 18:40:26 +0000428 Bitmask mask = 0;
drh75897232000-05-29 14:26:00 +0000429 if( p==0 ) return 0;
drh967e8b72000-06-21 13:59:10 +0000430 if( p->op==TK_COLUMN ){
drh8feb4b12004-07-19 02:12:14 +0000431 mask = getMask(pMaskSet, p->iTable);
drh8feb4b12004-07-19 02:12:14 +0000432 return mask;
drh75897232000-05-29 14:26:00 +0000433 }
danielk1977b3bce662005-01-29 08:32:43 +0000434 mask = exprTableUsage(pMaskSet, p->pRight);
435 mask |= exprTableUsage(pMaskSet, p->pLeft);
danielk19776ab3a2e2009-02-19 14:39:25 +0000436 if( ExprHasProperty(p, EP_xIsSelect) ){
437 mask |= exprSelectTableUsage(pMaskSet, p->x.pSelect);
438 }else{
439 mask |= exprListTableUsage(pMaskSet, p->x.pList);
440 }
danielk1977b3bce662005-01-29 08:32:43 +0000441 return mask;
442}
drh111a6a72008-12-21 03:51:16 +0000443static Bitmask exprListTableUsage(WhereMaskSet *pMaskSet, ExprList *pList){
danielk1977b3bce662005-01-29 08:32:43 +0000444 int i;
445 Bitmask mask = 0;
446 if( pList ){
447 for(i=0; i<pList->nExpr; i++){
448 mask |= exprTableUsage(pMaskSet, pList->a[i].pExpr);
drhdd579122002-04-02 01:58:57 +0000449 }
450 }
drh75897232000-05-29 14:26:00 +0000451 return mask;
452}
drh111a6a72008-12-21 03:51:16 +0000453static Bitmask exprSelectTableUsage(WhereMaskSet *pMaskSet, Select *pS){
drha430ae82007-09-12 15:41:01 +0000454 Bitmask mask = 0;
455 while( pS ){
456 mask |= exprListTableUsage(pMaskSet, pS->pEList);
drhf5b11382005-09-17 13:07:13 +0000457 mask |= exprListTableUsage(pMaskSet, pS->pGroupBy);
458 mask |= exprListTableUsage(pMaskSet, pS->pOrderBy);
459 mask |= exprTableUsage(pMaskSet, pS->pWhere);
460 mask |= exprTableUsage(pMaskSet, pS->pHaving);
drha430ae82007-09-12 15:41:01 +0000461 pS = pS->pPrior;
drhf5b11382005-09-17 13:07:13 +0000462 }
463 return mask;
464}
drh75897232000-05-29 14:26:00 +0000465
466/*
drh487ab3c2001-11-08 00:45:21 +0000467** Return TRUE if the given operator is one of the operators that is
drh51669862004-12-18 18:40:26 +0000468** allowed for an indexable WHERE clause term. The allowed operators are
drhc27a1ce2002-06-14 20:58:45 +0000469** "=", "<", ">", "<=", ">=", and "IN".
drh487ab3c2001-11-08 00:45:21 +0000470*/
471static int allowedOp(int op){
drhfe05af82005-07-21 03:14:59 +0000472 assert( TK_GT>TK_EQ && TK_GT<TK_GE );
473 assert( TK_LT>TK_EQ && TK_LT<TK_GE );
474 assert( TK_LE>TK_EQ && TK_LE<TK_GE );
475 assert( TK_GE==TK_EQ+4 );
drh50b39962006-10-28 00:28:09 +0000476 return op==TK_IN || (op>=TK_EQ && op<=TK_GE) || op==TK_ISNULL;
drh487ab3c2001-11-08 00:45:21 +0000477}
478
479/*
drh902b9ee2008-12-05 17:17:07 +0000480** Swap two objects of type TYPE.
drh193bd772004-07-20 18:23:14 +0000481*/
482#define SWAP(TYPE,A,B) {TYPE t=A; A=B; B=t;}
483
484/*
drh909626d2008-05-30 14:58:37 +0000485** Commute a comparison operator. Expressions of the form "X op Y"
drh0fcef5e2005-07-19 17:38:22 +0000486** are converted into "Y op X".
danielk1977eb5453d2007-07-30 14:40:48 +0000487**
488** If a collation sequence is associated with either the left or right
489** side of the comparison, it remains associated with the same side after
490** the commutation. So "Y collate NOCASE op X" becomes
491** "X collate NOCASE op Y". This is because any collation sequence on
492** the left hand side of a comparison overrides any collation sequence
493** attached to the right. For the same reason the EP_ExpCollate flag
494** is not commuted.
drh193bd772004-07-20 18:23:14 +0000495*/
drh7d10d5a2008-08-20 16:35:10 +0000496static void exprCommute(Parse *pParse, Expr *pExpr){
danielk1977eb5453d2007-07-30 14:40:48 +0000497 u16 expRight = (pExpr->pRight->flags & EP_ExpCollate);
498 u16 expLeft = (pExpr->pLeft->flags & EP_ExpCollate);
drhfe05af82005-07-21 03:14:59 +0000499 assert( allowedOp(pExpr->op) && pExpr->op!=TK_IN );
drh7d10d5a2008-08-20 16:35:10 +0000500 pExpr->pRight->pColl = sqlite3ExprCollSeq(pParse, pExpr->pRight);
501 pExpr->pLeft->pColl = sqlite3ExprCollSeq(pParse, pExpr->pLeft);
drh0fcef5e2005-07-19 17:38:22 +0000502 SWAP(CollSeq*,pExpr->pRight->pColl,pExpr->pLeft->pColl);
danielk1977eb5453d2007-07-30 14:40:48 +0000503 pExpr->pRight->flags = (pExpr->pRight->flags & ~EP_ExpCollate) | expLeft;
504 pExpr->pLeft->flags = (pExpr->pLeft->flags & ~EP_ExpCollate) | expRight;
drh0fcef5e2005-07-19 17:38:22 +0000505 SWAP(Expr*,pExpr->pRight,pExpr->pLeft);
506 if( pExpr->op>=TK_GT ){
507 assert( TK_LT==TK_GT+2 );
508 assert( TK_GE==TK_LE+2 );
509 assert( TK_GT>TK_EQ );
510 assert( TK_GT<TK_LE );
511 assert( pExpr->op>=TK_GT && pExpr->op<=TK_GE );
512 pExpr->op = ((pExpr->op-TK_GT)^2)+TK_GT;
drh193bd772004-07-20 18:23:14 +0000513 }
drh193bd772004-07-20 18:23:14 +0000514}
515
516/*
drhfe05af82005-07-21 03:14:59 +0000517** Translate from TK_xx operator to WO_xx bitmask.
518*/
drhec1724e2008-12-09 01:32:03 +0000519static u16 operatorMask(int op){
520 u16 c;
drhfe05af82005-07-21 03:14:59 +0000521 assert( allowedOp(op) );
522 if( op==TK_IN ){
drh51147ba2005-07-23 22:59:55 +0000523 c = WO_IN;
drh50b39962006-10-28 00:28:09 +0000524 }else if( op==TK_ISNULL ){
525 c = WO_ISNULL;
drhfe05af82005-07-21 03:14:59 +0000526 }else{
drhec1724e2008-12-09 01:32:03 +0000527 assert( (WO_EQ<<(op-TK_EQ)) < 0x7fff );
528 c = (u16)(WO_EQ<<(op-TK_EQ));
drhfe05af82005-07-21 03:14:59 +0000529 }
drh50b39962006-10-28 00:28:09 +0000530 assert( op!=TK_ISNULL || c==WO_ISNULL );
drh51147ba2005-07-23 22:59:55 +0000531 assert( op!=TK_IN || c==WO_IN );
532 assert( op!=TK_EQ || c==WO_EQ );
533 assert( op!=TK_LT || c==WO_LT );
534 assert( op!=TK_LE || c==WO_LE );
535 assert( op!=TK_GT || c==WO_GT );
536 assert( op!=TK_GE || c==WO_GE );
537 return c;
drhfe05af82005-07-21 03:14:59 +0000538}
539
540/*
541** Search for a term in the WHERE clause that is of the form "X <op> <expr>"
542** where X is a reference to the iColumn of table iCur and <op> is one of
543** the WO_xx operator codes specified by the op parameter.
544** Return a pointer to the term. Return 0 if not found.
545*/
546static WhereTerm *findTerm(
547 WhereClause *pWC, /* The WHERE clause to be searched */
548 int iCur, /* Cursor number of LHS */
549 int iColumn, /* Column number of LHS */
550 Bitmask notReady, /* RHS must not overlap with this mask */
drhec1724e2008-12-09 01:32:03 +0000551 u32 op, /* Mask of WO_xx values describing operator */
drhfe05af82005-07-21 03:14:59 +0000552 Index *pIdx /* Must be compatible with this index, if not NULL */
553){
554 WhereTerm *pTerm;
555 int k;
drh22c24032008-07-09 13:28:53 +0000556 assert( iCur>=0 );
drhec1724e2008-12-09 01:32:03 +0000557 op &= WO_ALL;
drhfe05af82005-07-21 03:14:59 +0000558 for(pTerm=pWC->a, k=pWC->nTerm; k; k--, pTerm++){
559 if( pTerm->leftCursor==iCur
560 && (pTerm->prereqRight & notReady)==0
drh700a2262008-12-17 19:22:15 +0000561 && pTerm->u.leftColumn==iColumn
drhb52076c2006-01-23 13:22:09 +0000562 && (pTerm->eOperator & op)!=0
drhfe05af82005-07-21 03:14:59 +0000563 ){
drh22c24032008-07-09 13:28:53 +0000564 if( pIdx && pTerm->eOperator!=WO_ISNULL ){
drhfe05af82005-07-21 03:14:59 +0000565 Expr *pX = pTerm->pExpr;
566 CollSeq *pColl;
567 char idxaff;
danielk1977f0113002006-01-24 12:09:17 +0000568 int j;
drhfe05af82005-07-21 03:14:59 +0000569 Parse *pParse = pWC->pParse;
570
571 idxaff = pIdx->pTable->aCol[iColumn].affinity;
572 if( !sqlite3IndexAffinityOk(pX, idxaff) ) continue;
danielk1977bcbb04e2007-05-29 12:11:29 +0000573
574 /* Figure out the collation sequence required from an index for
575 ** it to be useful for optimising expression pX. Store this
576 ** value in variable pColl.
577 */
578 assert(pX->pLeft);
579 pColl = sqlite3BinaryCompareCollSeq(pParse, pX->pLeft, pX->pRight);
danielk197793574162008-12-30 15:26:29 +0000580 assert(pColl || pParse->nErr);
danielk1977bcbb04e2007-05-29 12:11:29 +0000581
drh22c24032008-07-09 13:28:53 +0000582 for(j=0; pIdx->aiColumn[j]!=iColumn; j++){
drh34004ce2008-07-11 16:15:17 +0000583 if( NEVER(j>=pIdx->nColumn) ) return 0;
drh22c24032008-07-09 13:28:53 +0000584 }
danielk197793574162008-12-30 15:26:29 +0000585 if( pColl && sqlite3StrICmp(pColl->zName, pIdx->azColl[j]) ) continue;
drhfe05af82005-07-21 03:14:59 +0000586 }
587 return pTerm;
588 }
589 }
590 return 0;
591}
592
drh6c30be82005-07-29 15:10:17 +0000593/* Forward reference */
drh7b4fc6a2007-02-06 13:26:32 +0000594static void exprAnalyze(SrcList*, WhereClause*, int);
drh6c30be82005-07-29 15:10:17 +0000595
596/*
597** Call exprAnalyze on all terms in a WHERE clause.
598**
599**
600*/
601static void exprAnalyzeAll(
602 SrcList *pTabList, /* the FROM clause */
drh6c30be82005-07-29 15:10:17 +0000603 WhereClause *pWC /* the WHERE clause to be analyzed */
604){
drh6c30be82005-07-29 15:10:17 +0000605 int i;
drh9eb20282005-08-24 03:52:18 +0000606 for(i=pWC->nTerm-1; i>=0; i--){
drh7b4fc6a2007-02-06 13:26:32 +0000607 exprAnalyze(pTabList, pWC, i);
drh6c30be82005-07-29 15:10:17 +0000608 }
609}
610
drhd2687b72005-08-12 22:56:09 +0000611#ifndef SQLITE_OMIT_LIKE_OPTIMIZATION
612/*
613** Check to see if the given expression is a LIKE or GLOB operator that
614** can be optimized using inequality constraints. Return TRUE if it is
615** so and false if not.
616**
617** In order for the operator to be optimizible, the RHS must be a string
618** literal that does not begin with a wildcard.
619*/
620static int isLikeOrGlob(
drh7d10d5a2008-08-20 16:35:10 +0000621 Parse *pParse, /* Parsing and code generating context */
drhd2687b72005-08-12 22:56:09 +0000622 Expr *pExpr, /* Test this expression */
623 int *pnPattern, /* Number of non-wildcard prefix characters */
drh9f504ea2008-02-23 21:55:39 +0000624 int *pisComplete, /* True if the only wildcard is % in the last character */
625 int *pnoCase /* True if uppercase is equivalent to lowercase */
drhd2687b72005-08-12 22:56:09 +0000626){
drh5bd98ae2009-01-07 18:24:03 +0000627 const char *z; /* String on RHS of LIKE operator */
628 Expr *pRight, *pLeft; /* Right and left size of LIKE operator */
629 ExprList *pList; /* List of operands to the LIKE operator */
630 int c; /* One character in z[] */
drh24fb6272009-05-01 21:13:36 +0000631 int n; /* Length of string z[] */
drh5bd98ae2009-01-07 18:24:03 +0000632 int cnt; /* Number of non-wildcard prefix characters */
633 char wc[3]; /* Wildcard characters */
634 CollSeq *pColl; /* Collating sequence for LHS */
635 sqlite3 *db = pParse->db; /* Database connection */
drhd64fe2f2005-08-28 17:00:23 +0000636
drh9f504ea2008-02-23 21:55:39 +0000637 if( !sqlite3IsLikeFunction(db, pExpr, pnoCase, wc) ){
drhd2687b72005-08-12 22:56:09 +0000638 return 0;
639 }
drh9f504ea2008-02-23 21:55:39 +0000640#ifdef SQLITE_EBCDIC
641 if( *pnoCase ) return 0;
642#endif
danielk19776ab3a2e2009-02-19 14:39:25 +0000643 pList = pExpr->x.pList;
drh55ef4d92005-08-14 01:20:37 +0000644 pRight = pList->a[0].pExpr;
drh5bd98ae2009-01-07 18:24:03 +0000645 if( pRight->op!=TK_STRING ){
drhd2687b72005-08-12 22:56:09 +0000646 return 0;
647 }
drh55ef4d92005-08-14 01:20:37 +0000648 pLeft = pList->a[1].pExpr;
drhd2687b72005-08-12 22:56:09 +0000649 if( pLeft->op!=TK_COLUMN ){
650 return 0;
651 }
drh7d10d5a2008-08-20 16:35:10 +0000652 pColl = sqlite3ExprCollSeq(pParse, pLeft);
drh01495b92008-01-23 12:52:40 +0000653 assert( pColl!=0 || pLeft->iColumn==-1 );
drhd64fe2f2005-08-28 17:00:23 +0000654 if( pColl==0 ){
drh01495b92008-01-23 12:52:40 +0000655 /* No collation is defined for the ROWID. Use the default. */
drhd64fe2f2005-08-28 17:00:23 +0000656 pColl = db->pDfltColl;
657 }
drh9f504ea2008-02-23 21:55:39 +0000658 if( (pColl->type!=SQLITE_COLL_BINARY || *pnoCase) &&
659 (pColl->type!=SQLITE_COLL_NOCASE || !*pnoCase) ){
drhd64fe2f2005-08-28 17:00:23 +0000660 return 0;
661 }
drh24fb6272009-05-01 21:13:36 +0000662 z = (const char*)pRight->token.z;
drhf998b732007-11-26 13:36:00 +0000663 cnt = 0;
664 if( z ){
drh24fb6272009-05-01 21:13:36 +0000665 n = pRight->token.n;
666 while( cnt<n && (c=z[cnt])!=0 && c!=wc[0] && c!=wc[1] && c!=wc[2] ){
667 cnt++;
668 }
drhf998b732007-11-26 13:36:00 +0000669 }
drh5bd98ae2009-01-07 18:24:03 +0000670 if( cnt==0 || 255==(u8)z[cnt-1] ){
drhd2687b72005-08-12 22:56:09 +0000671 return 0;
672 }
drh55ef4d92005-08-14 01:20:37 +0000673 *pisComplete = z[cnt]==wc[0] && z[cnt+1]==0;
drhd2687b72005-08-12 22:56:09 +0000674 *pnPattern = cnt;
675 return 1;
676}
677#endif /* SQLITE_OMIT_LIKE_OPTIMIZATION */
678
drhedb193b2006-06-27 13:20:21 +0000679
680#ifndef SQLITE_OMIT_VIRTUALTABLE
drhfe05af82005-07-21 03:14:59 +0000681/*
drh7f375902006-06-13 17:38:59 +0000682** Check to see if the given expression is of the form
683**
684** column MATCH expr
685**
686** If it is then return TRUE. If not, return FALSE.
687*/
688static int isMatchOfColumn(
689 Expr *pExpr /* Test this expression */
690){
691 ExprList *pList;
692
693 if( pExpr->op!=TK_FUNCTION ){
694 return 0;
695 }
drhedb193b2006-06-27 13:20:21 +0000696 if( pExpr->token.n!=5 ||
697 sqlite3StrNICmp((const char*)pExpr->token.z,"match",5)!=0 ){
drh7f375902006-06-13 17:38:59 +0000698 return 0;
699 }
danielk19776ab3a2e2009-02-19 14:39:25 +0000700 pList = pExpr->x.pList;
drh7f375902006-06-13 17:38:59 +0000701 if( pList->nExpr!=2 ){
702 return 0;
703 }
704 if( pList->a[1].pExpr->op != TK_COLUMN ){
705 return 0;
706 }
707 return 1;
708}
drhedb193b2006-06-27 13:20:21 +0000709#endif /* SQLITE_OMIT_VIRTUALTABLE */
drh7f375902006-06-13 17:38:59 +0000710
711/*
drh54a167d2005-11-26 14:08:07 +0000712** If the pBase expression originated in the ON or USING clause of
713** a join, then transfer the appropriate markings over to derived.
714*/
715static void transferJoinMarkings(Expr *pDerived, Expr *pBase){
716 pDerived->flags |= pBase->flags & EP_FromJoin;
717 pDerived->iRightJoinTable = pBase->iRightJoinTable;
718}
719
drh3e355802007-02-23 23:13:33 +0000720#if !defined(SQLITE_OMIT_OR_OPTIMIZATION) && !defined(SQLITE_OMIT_SUBQUERY)
721/*
drh1a58fe02008-12-20 02:06:13 +0000722** Analyze a term that consists of two or more OR-connected
723** subterms. So in:
drh3e355802007-02-23 23:13:33 +0000724**
drh1a58fe02008-12-20 02:06:13 +0000725** ... WHERE (a=5) AND (b=7 OR c=9 OR d=13) AND (d=13)
726** ^^^^^^^^^^^^^^^^^^^^
drh3e355802007-02-23 23:13:33 +0000727**
drh1a58fe02008-12-20 02:06:13 +0000728** This routine analyzes terms such as the middle term in the above example.
729** A WhereOrTerm object is computed and attached to the term under
730** analysis, regardless of the outcome of the analysis. Hence:
drh3e355802007-02-23 23:13:33 +0000731**
drh1a58fe02008-12-20 02:06:13 +0000732** WhereTerm.wtFlags |= TERM_ORINFO
733** WhereTerm.u.pOrInfo = a dynamically allocated WhereOrTerm object
drh3e355802007-02-23 23:13:33 +0000734**
drh1a58fe02008-12-20 02:06:13 +0000735** The term being analyzed must have two or more of OR-connected subterms.
danielk1977fdc40192008-12-29 18:33:32 +0000736** A single subterm might be a set of AND-connected sub-subterms.
drh1a58fe02008-12-20 02:06:13 +0000737** Examples of terms under analysis:
drh3e355802007-02-23 23:13:33 +0000738**
drh1a58fe02008-12-20 02:06:13 +0000739** (A) t1.x=t2.y OR t1.x=t2.z OR t1.y=15 OR t1.z=t3.a+5
740** (B) x=expr1 OR expr2=x OR x=expr3
741** (C) t1.x=t2.y OR (t1.x=t2.z AND t1.y=15)
742** (D) x=expr1 OR (y>11 AND y<22 AND z LIKE '*hello*')
743** (E) (p.a=1 AND q.b=2 AND r.c=3) OR (p.x=4 AND q.y=5 AND r.z=6)
drh3e355802007-02-23 23:13:33 +0000744**
drh1a58fe02008-12-20 02:06:13 +0000745** CASE 1:
746**
747** If all subterms are of the form T.C=expr for some single column of C
748** a single table T (as shown in example B above) then create a new virtual
749** term that is an equivalent IN expression. In other words, if the term
750** being analyzed is:
751**
752** x = expr1 OR expr2 = x OR x = expr3
753**
754** then create a new virtual term like this:
755**
756** x IN (expr1,expr2,expr3)
757**
758** CASE 2:
759**
760** If all subterms are indexable by a single table T, then set
761**
762** WhereTerm.eOperator = WO_OR
763** WhereTerm.u.pOrInfo->indexable |= the cursor number for table T
764**
765** A subterm is "indexable" if it is of the form
766** "T.C <op> <expr>" where C is any column of table T and
767** <op> is one of "=", "<", "<=", ">", ">=", "IS NULL", or "IN".
768** A subterm is also indexable if it is an AND of two or more
769** subsubterms at least one of which is indexable. Indexable AND
770** subterms have their eOperator set to WO_AND and they have
771** u.pAndInfo set to a dynamically allocated WhereAndTerm object.
772**
773** From another point of view, "indexable" means that the subterm could
774** potentially be used with an index if an appropriate index exists.
775** This analysis does not consider whether or not the index exists; that
776** is something the bestIndex() routine will determine. This analysis
777** only looks at whether subterms appropriate for indexing exist.
778**
779** All examples A through E above all satisfy case 2. But if a term
780** also statisfies case 1 (such as B) we know that the optimizer will
781** always prefer case 1, so in that case we pretend that case 2 is not
782** satisfied.
783**
784** It might be the case that multiple tables are indexable. For example,
785** (E) above is indexable on tables P, Q, and R.
786**
787** Terms that satisfy case 2 are candidates for lookup by using
788** separate indices to find rowids for each subterm and composing
789** the union of all rowids using a RowSet object. This is similar
790** to "bitmap indices" in other database engines.
791**
792** OTHERWISE:
793**
794** If neither case 1 nor case 2 apply, then leave the eOperator set to
795** zero. This term is not useful for search.
drh3e355802007-02-23 23:13:33 +0000796*/
drh1a58fe02008-12-20 02:06:13 +0000797static void exprAnalyzeOrTerm(
798 SrcList *pSrc, /* the FROM clause */
799 WhereClause *pWC, /* the complete WHERE clause */
800 int idxTerm /* Index of the OR-term to be analyzed */
801){
802 Parse *pParse = pWC->pParse; /* Parser context */
803 sqlite3 *db = pParse->db; /* Database connection */
804 WhereTerm *pTerm = &pWC->a[idxTerm]; /* The term to be analyzed */
805 Expr *pExpr = pTerm->pExpr; /* The expression of the term */
drh111a6a72008-12-21 03:51:16 +0000806 WhereMaskSet *pMaskSet = pWC->pMaskSet; /* Table use masks */
drh1a58fe02008-12-20 02:06:13 +0000807 int i; /* Loop counters */
808 WhereClause *pOrWc; /* Breakup of pTerm into subterms */
809 WhereTerm *pOrTerm; /* A Sub-term within the pOrWc */
810 WhereOrInfo *pOrInfo; /* Additional information associated with pTerm */
811 Bitmask chngToIN; /* Tables that might satisfy case 1 */
812 Bitmask indexable; /* Tables that are indexable, satisfying case 2 */
drh3e355802007-02-23 23:13:33 +0000813
drh1a58fe02008-12-20 02:06:13 +0000814 /*
815 ** Break the OR clause into its separate subterms. The subterms are
816 ** stored in a WhereClause structure containing within the WhereOrInfo
817 ** object that is attached to the original OR clause term.
818 */
819 assert( (pTerm->wtFlags & (TERM_DYNAMIC|TERM_ORINFO|TERM_ANDINFO))==0 );
820 assert( pExpr->op==TK_OR );
drh954701a2008-12-29 23:45:07 +0000821 pTerm->u.pOrInfo = pOrInfo = sqlite3DbMallocZero(db, sizeof(*pOrInfo));
drh1a58fe02008-12-20 02:06:13 +0000822 if( pOrInfo==0 ) return;
823 pTerm->wtFlags |= TERM_ORINFO;
824 pOrWc = &pOrInfo->wc;
825 whereClauseInit(pOrWc, pWC->pParse, pMaskSet);
826 whereSplit(pOrWc, pExpr, TK_OR);
827 exprAnalyzeAll(pSrc, pOrWc);
828 if( db->mallocFailed ) return;
829 assert( pOrWc->nTerm>=2 );
830
831 /*
832 ** Compute the set of tables that might satisfy cases 1 or 2.
833 */
danielk1977e672c8e2009-05-22 15:43:26 +0000834 indexable = ~(Bitmask)0;
835 chngToIN = ~(pWC->vmask);
drh1a58fe02008-12-20 02:06:13 +0000836 for(i=pOrWc->nTerm-1, pOrTerm=pOrWc->a; i>=0 && indexable; i--, pOrTerm++){
837 if( (pOrTerm->eOperator & WO_SINGLE)==0 ){
drh29435252008-12-28 18:35:08 +0000838 WhereAndInfo *pAndInfo;
839 assert( pOrTerm->eOperator==0 );
840 assert( (pOrTerm->wtFlags & (TERM_ANDINFO|TERM_ORINFO))==0 );
drh1a58fe02008-12-20 02:06:13 +0000841 chngToIN = 0;
drh29435252008-12-28 18:35:08 +0000842 pAndInfo = sqlite3DbMallocRaw(db, sizeof(*pAndInfo));
843 if( pAndInfo ){
844 WhereClause *pAndWC;
845 WhereTerm *pAndTerm;
846 int j;
847 Bitmask b = 0;
848 pOrTerm->u.pAndInfo = pAndInfo;
849 pOrTerm->wtFlags |= TERM_ANDINFO;
850 pOrTerm->eOperator = WO_AND;
851 pAndWC = &pAndInfo->wc;
852 whereClauseInit(pAndWC, pWC->pParse, pMaskSet);
853 whereSplit(pAndWC, pOrTerm->pExpr, TK_AND);
854 exprAnalyzeAll(pSrc, pAndWC);
drh7c2fbde2009-01-07 20:58:57 +0000855 testcase( db->mallocFailed );
drh96c7a7d2009-01-10 15:34:12 +0000856 if( !db->mallocFailed ){
857 for(j=0, pAndTerm=pAndWC->a; j<pAndWC->nTerm; j++, pAndTerm++){
858 assert( pAndTerm->pExpr );
859 if( allowedOp(pAndTerm->pExpr->op) ){
860 b |= getMask(pMaskSet, pAndTerm->leftCursor);
861 }
drh29435252008-12-28 18:35:08 +0000862 }
863 }
864 indexable &= b;
865 }
drh1a58fe02008-12-20 02:06:13 +0000866 }else if( pOrTerm->wtFlags & TERM_COPIED ){
867 /* Skip this term for now. We revisit it when we process the
868 ** corresponding TERM_VIRTUAL term */
869 }else{
870 Bitmask b;
871 b = getMask(pMaskSet, pOrTerm->leftCursor);
872 if( pOrTerm->wtFlags & TERM_VIRTUAL ){
873 WhereTerm *pOther = &pOrWc->a[pOrTerm->iParent];
874 b |= getMask(pMaskSet, pOther->leftCursor);
875 }
876 indexable &= b;
877 if( pOrTerm->eOperator!=WO_EQ ){
878 chngToIN = 0;
879 }else{
880 chngToIN &= b;
881 }
882 }
drh3e355802007-02-23 23:13:33 +0000883 }
drh1a58fe02008-12-20 02:06:13 +0000884
885 /*
886 ** Record the set of tables that satisfy case 2. The set might be
drh111a6a72008-12-21 03:51:16 +0000887 ** empty.
drh1a58fe02008-12-20 02:06:13 +0000888 */
889 pOrInfo->indexable = indexable;
drh111a6a72008-12-21 03:51:16 +0000890 pTerm->eOperator = indexable==0 ? 0 : WO_OR;
drh1a58fe02008-12-20 02:06:13 +0000891
892 /*
893 ** chngToIN holds a set of tables that *might* satisfy case 1. But
894 ** we have to do some additional checking to see if case 1 really
895 ** is satisfied.
896 */
897 if( chngToIN ){
898 int okToChngToIN = 0; /* True if the conversion to IN is valid */
899 int iColumn = -1; /* Column index on lhs of IN operator */
shane63207ab2009-02-04 01:49:30 +0000900 int iCursor = -1; /* Table cursor common to all terms */
drh1a58fe02008-12-20 02:06:13 +0000901 int j = 0; /* Loop counter */
902
903 /* Search for a table and column that appears on one side or the
904 ** other of the == operator in every subterm. That table and column
905 ** will be recorded in iCursor and iColumn. There might not be any
906 ** such table and column. Set okToChngToIN if an appropriate table
907 ** and column is found but leave okToChngToIN false if not found.
908 */
909 for(j=0; j<2 && !okToChngToIN; j++){
910 pOrTerm = pOrWc->a;
911 for(i=pOrWc->nTerm-1; i>=0; i--, pOrTerm++){
912 assert( pOrTerm->eOperator==WO_EQ );
913 pOrTerm->wtFlags &= ~TERM_OR_OK;
914 if( pOrTerm->leftCursor==iColumn ) continue;
915 if( (chngToIN & getMask(pMaskSet, pOrTerm->leftCursor))==0 ) continue;
916 iColumn = pOrTerm->u.leftColumn;
917 iCursor = pOrTerm->leftCursor;
918 break;
919 }
920 if( i<0 ){
921 assert( j==1 );
922 assert( (chngToIN&(chngToIN-1))==0 );
923 assert( chngToIN==getMask(pMaskSet, iColumn) );
924 break;
925 }
926 okToChngToIN = 1;
927 for(; i>=0 && okToChngToIN; i--, pOrTerm++){
928 assert( pOrTerm->eOperator==WO_EQ );
929 if( pOrTerm->leftCursor!=iCursor ){
930 pOrTerm->wtFlags &= ~TERM_OR_OK;
931 }else if( pOrTerm->u.leftColumn!=iColumn ){
932 okToChngToIN = 0;
933 }else{
934 int affLeft, affRight;
935 /* If the right-hand side is also a column, then the affinities
936 ** of both right and left sides must be such that no type
937 ** conversions are required on the right. (Ticket #2249)
938 */
939 affRight = sqlite3ExprAffinity(pOrTerm->pExpr->pRight);
940 affLeft = sqlite3ExprAffinity(pOrTerm->pExpr->pLeft);
941 if( affRight!=0 && affRight!=affLeft ){
942 okToChngToIN = 0;
943 }else{
944 pOrTerm->wtFlags |= TERM_OR_OK;
945 }
946 }
947 }
948 }
949
950 /* At this point, okToChngToIN is true if original pTerm satisfies
951 ** case 1. In that case, construct a new virtual term that is
952 ** pTerm converted into an IN operator.
953 */
954 if( okToChngToIN ){
955 Expr *pDup; /* A transient duplicate expression */
956 ExprList *pList = 0; /* The RHS of the IN operator */
957 Expr *pLeft = 0; /* The LHS of the IN operator */
958 Expr *pNew; /* The complete IN operator */
959
960 for(i=pOrWc->nTerm-1, pOrTerm=pOrWc->a; i>=0; i--, pOrTerm++){
961 if( (pOrTerm->wtFlags & TERM_OR_OK)==0 ) continue;
962 assert( pOrTerm->eOperator==WO_EQ );
963 assert( pOrTerm->leftCursor==iCursor );
964 assert( pOrTerm->u.leftColumn==iColumn );
danielk19776ab3a2e2009-02-19 14:39:25 +0000965 pDup = sqlite3ExprDup(db, pOrTerm->pExpr->pRight, 0);
drh1a58fe02008-12-20 02:06:13 +0000966 pList = sqlite3ExprListAppend(pWC->pParse, pList, pDup, 0);
967 pLeft = pOrTerm->pExpr->pLeft;
968 }
969 assert( pLeft!=0 );
danielk19776ab3a2e2009-02-19 14:39:25 +0000970 pDup = sqlite3ExprDup(db, pLeft, 0);
drh1a58fe02008-12-20 02:06:13 +0000971 pNew = sqlite3Expr(db, TK_IN, pDup, 0, 0);
972 if( pNew ){
973 int idxNew;
974 transferJoinMarkings(pNew, pExpr);
danielk19776ab3a2e2009-02-19 14:39:25 +0000975 assert( !ExprHasProperty(pNew, EP_xIsSelect) );
976 pNew->x.pList = pList;
drh1a58fe02008-12-20 02:06:13 +0000977 idxNew = whereClauseInsert(pWC, pNew, TERM_VIRTUAL|TERM_DYNAMIC);
978 testcase( idxNew==0 );
979 exprAnalyze(pSrc, pWC, idxNew);
980 pTerm = &pWC->a[idxTerm];
981 pWC->a[idxNew].iParent = idxTerm;
982 pTerm->nChild = 1;
983 }else{
984 sqlite3ExprListDelete(db, pList);
985 }
986 pTerm->eOperator = 0; /* case 1 trumps case 2 */
987 }
drh3e355802007-02-23 23:13:33 +0000988 }
drh3e355802007-02-23 23:13:33 +0000989}
990#endif /* !SQLITE_OMIT_OR_OPTIMIZATION && !SQLITE_OMIT_SUBQUERY */
drh54a167d2005-11-26 14:08:07 +0000991
drh1a58fe02008-12-20 02:06:13 +0000992
drh54a167d2005-11-26 14:08:07 +0000993/*
drh0aa74ed2005-07-16 13:33:20 +0000994** The input to this routine is an WhereTerm structure with only the
drh51147ba2005-07-23 22:59:55 +0000995** "pExpr" field filled in. The job of this routine is to analyze the
drh0aa74ed2005-07-16 13:33:20 +0000996** subexpression and populate all the other fields of the WhereTerm
drh75897232000-05-29 14:26:00 +0000997** structure.
drh51147ba2005-07-23 22:59:55 +0000998**
999** If the expression is of the form "<expr> <op> X" it gets commuted
drh1a58fe02008-12-20 02:06:13 +00001000** to the standard form of "X <op> <expr>".
1001**
1002** If the expression is of the form "X <op> Y" where both X and Y are
1003** columns, then the original expression is unchanged and a new virtual
1004** term of the form "Y <op> X" is added to the WHERE clause and
1005** analyzed separately. The original term is marked with TERM_COPIED
1006** and the new term is marked with TERM_DYNAMIC (because it's pExpr
1007** needs to be freed with the WhereClause) and TERM_VIRTUAL (because it
1008** is a commuted copy of a prior term.) The original term has nChild=1
1009** and the copy has idxParent set to the index of the original term.
drh75897232000-05-29 14:26:00 +00001010*/
drh0fcef5e2005-07-19 17:38:22 +00001011static void exprAnalyze(
1012 SrcList *pSrc, /* the FROM clause */
drh9eb20282005-08-24 03:52:18 +00001013 WhereClause *pWC, /* the WHERE clause */
1014 int idxTerm /* Index of the term to be analyzed */
drh0fcef5e2005-07-19 17:38:22 +00001015){
drh1a58fe02008-12-20 02:06:13 +00001016 WhereTerm *pTerm; /* The term to be analyzed */
drh111a6a72008-12-21 03:51:16 +00001017 WhereMaskSet *pMaskSet; /* Set of table index masks */
drh1a58fe02008-12-20 02:06:13 +00001018 Expr *pExpr; /* The expression to be analyzed */
1019 Bitmask prereqLeft; /* Prerequesites of the pExpr->pLeft */
1020 Bitmask prereqAll; /* Prerequesites of pExpr */
drhdafc0ce2008-04-17 19:14:02 +00001021 Bitmask extraRight = 0;
drhd2687b72005-08-12 22:56:09 +00001022 int nPattern;
1023 int isComplete;
drh9f504ea2008-02-23 21:55:39 +00001024 int noCase;
drh1a58fe02008-12-20 02:06:13 +00001025 int op; /* Top-level operator. pExpr->op */
1026 Parse *pParse = pWC->pParse; /* Parsing context */
1027 sqlite3 *db = pParse->db; /* Database connection */
drh0fcef5e2005-07-19 17:38:22 +00001028
drhf998b732007-11-26 13:36:00 +00001029 if( db->mallocFailed ){
1030 return;
1031 }
1032 pTerm = &pWC->a[idxTerm];
1033 pMaskSet = pWC->pMaskSet;
1034 pExpr = pTerm->pExpr;
drh0fcef5e2005-07-19 17:38:22 +00001035 prereqLeft = exprTableUsage(pMaskSet, pExpr->pLeft);
drh50b39962006-10-28 00:28:09 +00001036 op = pExpr->op;
1037 if( op==TK_IN ){
drhf5b11382005-09-17 13:07:13 +00001038 assert( pExpr->pRight==0 );
danielk19776ab3a2e2009-02-19 14:39:25 +00001039 if( ExprHasProperty(pExpr, EP_xIsSelect) ){
1040 pTerm->prereqRight = exprSelectTableUsage(pMaskSet, pExpr->x.pSelect);
1041 }else{
1042 pTerm->prereqRight = exprListTableUsage(pMaskSet, pExpr->x.pList);
1043 }
drh50b39962006-10-28 00:28:09 +00001044 }else if( op==TK_ISNULL ){
1045 pTerm->prereqRight = 0;
drhf5b11382005-09-17 13:07:13 +00001046 }else{
1047 pTerm->prereqRight = exprTableUsage(pMaskSet, pExpr->pRight);
1048 }
drh22d6a532005-09-19 21:05:48 +00001049 prereqAll = exprTableUsage(pMaskSet, pExpr);
1050 if( ExprHasProperty(pExpr, EP_FromJoin) ){
drh42165be2008-03-26 14:56:34 +00001051 Bitmask x = getMask(pMaskSet, pExpr->iRightJoinTable);
1052 prereqAll |= x;
drhdafc0ce2008-04-17 19:14:02 +00001053 extraRight = x-1; /* ON clause terms may not be used with an index
1054 ** on left table of a LEFT JOIN. Ticket #3015 */
drh22d6a532005-09-19 21:05:48 +00001055 }
1056 pTerm->prereqAll = prereqAll;
drh0fcef5e2005-07-19 17:38:22 +00001057 pTerm->leftCursor = -1;
drh45b1ee42005-08-02 17:48:22 +00001058 pTerm->iParent = -1;
drhb52076c2006-01-23 13:22:09 +00001059 pTerm->eOperator = 0;
drh50b39962006-10-28 00:28:09 +00001060 if( allowedOp(op) && (pTerm->prereqRight & prereqLeft)==0 ){
drh0fcef5e2005-07-19 17:38:22 +00001061 Expr *pLeft = pExpr->pLeft;
1062 Expr *pRight = pExpr->pRight;
1063 if( pLeft->op==TK_COLUMN ){
1064 pTerm->leftCursor = pLeft->iTable;
drh700a2262008-12-17 19:22:15 +00001065 pTerm->u.leftColumn = pLeft->iColumn;
drh50b39962006-10-28 00:28:09 +00001066 pTerm->eOperator = operatorMask(op);
drh75897232000-05-29 14:26:00 +00001067 }
drh0fcef5e2005-07-19 17:38:22 +00001068 if( pRight && pRight->op==TK_COLUMN ){
1069 WhereTerm *pNew;
1070 Expr *pDup;
1071 if( pTerm->leftCursor>=0 ){
drh9eb20282005-08-24 03:52:18 +00001072 int idxNew;
danielk19776ab3a2e2009-02-19 14:39:25 +00001073 pDup = sqlite3ExprDup(db, pExpr, 0);
drh17435752007-08-16 04:30:38 +00001074 if( db->mallocFailed ){
drh633e6d52008-07-28 19:34:53 +00001075 sqlite3ExprDelete(db, pDup);
drh28f45912006-10-18 23:26:38 +00001076 return;
1077 }
drh9eb20282005-08-24 03:52:18 +00001078 idxNew = whereClauseInsert(pWC, pDup, TERM_VIRTUAL|TERM_DYNAMIC);
1079 if( idxNew==0 ) return;
1080 pNew = &pWC->a[idxNew];
1081 pNew->iParent = idxTerm;
1082 pTerm = &pWC->a[idxTerm];
drh45b1ee42005-08-02 17:48:22 +00001083 pTerm->nChild = 1;
drh165be382008-12-05 02:36:33 +00001084 pTerm->wtFlags |= TERM_COPIED;
drh0fcef5e2005-07-19 17:38:22 +00001085 }else{
1086 pDup = pExpr;
1087 pNew = pTerm;
1088 }
drh7d10d5a2008-08-20 16:35:10 +00001089 exprCommute(pParse, pDup);
drh0fcef5e2005-07-19 17:38:22 +00001090 pLeft = pDup->pLeft;
1091 pNew->leftCursor = pLeft->iTable;
drh700a2262008-12-17 19:22:15 +00001092 pNew->u.leftColumn = pLeft->iColumn;
drh0fcef5e2005-07-19 17:38:22 +00001093 pNew->prereqRight = prereqLeft;
1094 pNew->prereqAll = prereqAll;
drhb52076c2006-01-23 13:22:09 +00001095 pNew->eOperator = operatorMask(pDup->op);
drh75897232000-05-29 14:26:00 +00001096 }
1097 }
drhed378002005-07-28 23:12:08 +00001098
drhd2687b72005-08-12 22:56:09 +00001099#ifndef SQLITE_OMIT_BETWEEN_OPTIMIZATION
drhed378002005-07-28 23:12:08 +00001100 /* If a term is the BETWEEN operator, create two new virtual terms
drh1a58fe02008-12-20 02:06:13 +00001101 ** that define the range that the BETWEEN implements. For example:
1102 **
1103 ** a BETWEEN b AND c
1104 **
1105 ** is converted into:
1106 **
1107 ** (a BETWEEN b AND c) AND (a>=b) AND (a<=c)
1108 **
1109 ** The two new terms are added onto the end of the WhereClause object.
1110 ** The new terms are "dynamic" and are children of the original BETWEEN
1111 ** term. That means that if the BETWEEN term is coded, the children are
1112 ** skipped. Or, if the children are satisfied by an index, the original
1113 ** BETWEEN term is skipped.
drhed378002005-07-28 23:12:08 +00001114 */
drh29435252008-12-28 18:35:08 +00001115 else if( pExpr->op==TK_BETWEEN && pWC->op==TK_AND ){
danielk19776ab3a2e2009-02-19 14:39:25 +00001116 ExprList *pList = pExpr->x.pList;
drhed378002005-07-28 23:12:08 +00001117 int i;
1118 static const u8 ops[] = {TK_GE, TK_LE};
1119 assert( pList!=0 );
1120 assert( pList->nExpr==2 );
1121 for(i=0; i<2; i++){
1122 Expr *pNewExpr;
drh9eb20282005-08-24 03:52:18 +00001123 int idxNew;
danielk19776ab3a2e2009-02-19 14:39:25 +00001124 pNewExpr = sqlite3Expr(db, ops[i], sqlite3ExprDup(db, pExpr->pLeft, 0),
1125 sqlite3ExprDup(db, pList->a[i].pExpr, 0), 0);
drh9eb20282005-08-24 03:52:18 +00001126 idxNew = whereClauseInsert(pWC, pNewExpr, TERM_VIRTUAL|TERM_DYNAMIC);
drh6a1e0712008-12-05 15:24:15 +00001127 testcase( idxNew==0 );
drh7b4fc6a2007-02-06 13:26:32 +00001128 exprAnalyze(pSrc, pWC, idxNew);
drh9eb20282005-08-24 03:52:18 +00001129 pTerm = &pWC->a[idxTerm];
1130 pWC->a[idxNew].iParent = idxTerm;
drhed378002005-07-28 23:12:08 +00001131 }
drh45b1ee42005-08-02 17:48:22 +00001132 pTerm->nChild = 2;
drhed378002005-07-28 23:12:08 +00001133 }
drhd2687b72005-08-12 22:56:09 +00001134#endif /* SQLITE_OMIT_BETWEEN_OPTIMIZATION */
drhed378002005-07-28 23:12:08 +00001135
danielk19771576cd92006-01-14 08:02:28 +00001136#if !defined(SQLITE_OMIT_OR_OPTIMIZATION) && !defined(SQLITE_OMIT_SUBQUERY)
drh1a58fe02008-12-20 02:06:13 +00001137 /* Analyze a term that is composed of two or more subterms connected by
1138 ** an OR operator.
drh6c30be82005-07-29 15:10:17 +00001139 */
1140 else if( pExpr->op==TK_OR ){
drh29435252008-12-28 18:35:08 +00001141 assert( pWC->op==TK_AND );
drh1a58fe02008-12-20 02:06:13 +00001142 exprAnalyzeOrTerm(pSrc, pWC, idxTerm);
drh6c30be82005-07-29 15:10:17 +00001143 }
drhd2687b72005-08-12 22:56:09 +00001144#endif /* SQLITE_OMIT_OR_OPTIMIZATION */
1145
1146#ifndef SQLITE_OMIT_LIKE_OPTIMIZATION
1147 /* Add constraints to reduce the search space on a LIKE or GLOB
1148 ** operator.
drh9f504ea2008-02-23 21:55:39 +00001149 **
1150 ** A like pattern of the form "x LIKE 'abc%'" is changed into constraints
1151 **
1152 ** x>='abc' AND x<'abd' AND x LIKE 'abc%'
1153 **
1154 ** The last character of the prefix "abc" is incremented to form the
shane7bc71e52008-05-28 18:01:44 +00001155 ** termination condition "abd".
drhd2687b72005-08-12 22:56:09 +00001156 */
drh29435252008-12-28 18:35:08 +00001157 if( isLikeOrGlob(pParse, pExpr, &nPattern, &isComplete, &noCase)
1158 && pWC->op==TK_AND ){
drhd2687b72005-08-12 22:56:09 +00001159 Expr *pLeft, *pRight;
1160 Expr *pStr1, *pStr2;
1161 Expr *pNewExpr1, *pNewExpr2;
drh9eb20282005-08-24 03:52:18 +00001162 int idxNew1, idxNew2;
1163
danielk19776ab3a2e2009-02-19 14:39:25 +00001164 pLeft = pExpr->x.pList->a[1].pExpr;
1165 pRight = pExpr->x.pList->a[0].pExpr;
drh17435752007-08-16 04:30:38 +00001166 pStr1 = sqlite3PExpr(pParse, TK_STRING, 0, 0, 0);
drhd2687b72005-08-12 22:56:09 +00001167 if( pStr1 ){
drh17435752007-08-16 04:30:38 +00001168 sqlite3TokenCopy(db, &pStr1->token, &pRight->token);
drhd2687b72005-08-12 22:56:09 +00001169 pStr1->token.n = nPattern;
1170 }
danielk19776ab3a2e2009-02-19 14:39:25 +00001171 pStr2 = sqlite3ExprDup(db, pStr1, 0);
drhf998b732007-11-26 13:36:00 +00001172 if( !db->mallocFailed ){
drh9f504ea2008-02-23 21:55:39 +00001173 u8 c, *pC;
danielk19776ab3a2e2009-02-19 14:39:25 +00001174 /* assert( pStr2->token.dyn ); */
drh9f504ea2008-02-23 21:55:39 +00001175 pC = (u8*)&pStr2->token.z[nPattern-1];
1176 c = *pC;
drh02a50b72008-05-26 18:33:40 +00001177 if( noCase ){
1178 if( c=='@' ) isComplete = 0;
1179 c = sqlite3UpperToLower[c];
1180 }
drh9f504ea2008-02-23 21:55:39 +00001181 *pC = c + 1;
drhd2687b72005-08-12 22:56:09 +00001182 }
danielk19776ab3a2e2009-02-19 14:39:25 +00001183 pNewExpr1 = sqlite3PExpr(pParse, TK_GE, sqlite3ExprDup(db,pLeft,0),pStr1,0);
drh9eb20282005-08-24 03:52:18 +00001184 idxNew1 = whereClauseInsert(pWC, pNewExpr1, TERM_VIRTUAL|TERM_DYNAMIC);
drh6a1e0712008-12-05 15:24:15 +00001185 testcase( idxNew1==0 );
drh7b4fc6a2007-02-06 13:26:32 +00001186 exprAnalyze(pSrc, pWC, idxNew1);
danielk19776ab3a2e2009-02-19 14:39:25 +00001187 pNewExpr2 = sqlite3PExpr(pParse, TK_LT, sqlite3ExprDup(db,pLeft,0),pStr2,0);
drh9eb20282005-08-24 03:52:18 +00001188 idxNew2 = whereClauseInsert(pWC, pNewExpr2, TERM_VIRTUAL|TERM_DYNAMIC);
drh6a1e0712008-12-05 15:24:15 +00001189 testcase( idxNew2==0 );
drh7b4fc6a2007-02-06 13:26:32 +00001190 exprAnalyze(pSrc, pWC, idxNew2);
drh9eb20282005-08-24 03:52:18 +00001191 pTerm = &pWC->a[idxTerm];
drhd2687b72005-08-12 22:56:09 +00001192 if( isComplete ){
drh9eb20282005-08-24 03:52:18 +00001193 pWC->a[idxNew1].iParent = idxTerm;
1194 pWC->a[idxNew2].iParent = idxTerm;
drhd2687b72005-08-12 22:56:09 +00001195 pTerm->nChild = 2;
1196 }
1197 }
1198#endif /* SQLITE_OMIT_LIKE_OPTIMIZATION */
drh7f375902006-06-13 17:38:59 +00001199
1200#ifndef SQLITE_OMIT_VIRTUALTABLE
1201 /* Add a WO_MATCH auxiliary term to the constraint set if the
1202 ** current expression is of the form: column MATCH expr.
1203 ** This information is used by the xBestIndex methods of
1204 ** virtual tables. The native query optimizer does not attempt
1205 ** to do anything with MATCH functions.
1206 */
1207 if( isMatchOfColumn(pExpr) ){
1208 int idxNew;
1209 Expr *pRight, *pLeft;
1210 WhereTerm *pNewTerm;
1211 Bitmask prereqColumn, prereqExpr;
1212
danielk19776ab3a2e2009-02-19 14:39:25 +00001213 pRight = pExpr->x.pList->a[0].pExpr;
1214 pLeft = pExpr->x.pList->a[1].pExpr;
drh7f375902006-06-13 17:38:59 +00001215 prereqExpr = exprTableUsage(pMaskSet, pRight);
1216 prereqColumn = exprTableUsage(pMaskSet, pLeft);
1217 if( (prereqExpr & prereqColumn)==0 ){
drh1a90e092006-06-14 22:07:10 +00001218 Expr *pNewExpr;
danielk19776ab3a2e2009-02-19 14:39:25 +00001219 pNewExpr = sqlite3Expr(db, TK_MATCH, 0, sqlite3ExprDup(db, pRight, 0), 0);
drh1a90e092006-06-14 22:07:10 +00001220 idxNew = whereClauseInsert(pWC, pNewExpr, TERM_VIRTUAL|TERM_DYNAMIC);
drh6a1e0712008-12-05 15:24:15 +00001221 testcase( idxNew==0 );
drh7f375902006-06-13 17:38:59 +00001222 pNewTerm = &pWC->a[idxNew];
1223 pNewTerm->prereqRight = prereqExpr;
1224 pNewTerm->leftCursor = pLeft->iTable;
drh700a2262008-12-17 19:22:15 +00001225 pNewTerm->u.leftColumn = pLeft->iColumn;
drh7f375902006-06-13 17:38:59 +00001226 pNewTerm->eOperator = WO_MATCH;
1227 pNewTerm->iParent = idxTerm;
drhd2ca60d2006-06-27 02:36:58 +00001228 pTerm = &pWC->a[idxTerm];
drh7f375902006-06-13 17:38:59 +00001229 pTerm->nChild = 1;
drh165be382008-12-05 02:36:33 +00001230 pTerm->wtFlags |= TERM_COPIED;
drh7f375902006-06-13 17:38:59 +00001231 pNewTerm->prereqAll = pTerm->prereqAll;
1232 }
1233 }
1234#endif /* SQLITE_OMIT_VIRTUALTABLE */
drhdafc0ce2008-04-17 19:14:02 +00001235
1236 /* Prevent ON clause terms of a LEFT JOIN from being used to drive
1237 ** an index for tables to the left of the join.
1238 */
1239 pTerm->prereqRight |= extraRight;
drh75897232000-05-29 14:26:00 +00001240}
1241
drh7b4fc6a2007-02-06 13:26:32 +00001242/*
1243** Return TRUE if any of the expressions in pList->a[iFirst...] contain
1244** a reference to any table other than the iBase table.
1245*/
1246static int referencesOtherTables(
1247 ExprList *pList, /* Search expressions in ths list */
drh111a6a72008-12-21 03:51:16 +00001248 WhereMaskSet *pMaskSet, /* Mapping from tables to bitmaps */
drh7b4fc6a2007-02-06 13:26:32 +00001249 int iFirst, /* Be searching with the iFirst-th expression */
1250 int iBase /* Ignore references to this table */
1251){
1252 Bitmask allowed = ~getMask(pMaskSet, iBase);
1253 while( iFirst<pList->nExpr ){
1254 if( (exprTableUsage(pMaskSet, pList->a[iFirst++].pExpr)&allowed)!=0 ){
1255 return 1;
1256 }
1257 }
1258 return 0;
1259}
1260
drh0fcef5e2005-07-19 17:38:22 +00001261
drh75897232000-05-29 14:26:00 +00001262/*
drh51669862004-12-18 18:40:26 +00001263** This routine decides if pIdx can be used to satisfy the ORDER BY
1264** clause. If it can, it returns 1. If pIdx cannot satisfy the
1265** ORDER BY clause, this routine returns 0.
1266**
1267** pOrderBy is an ORDER BY clause from a SELECT statement. pTab is the
1268** left-most table in the FROM clause of that same SELECT statement and
1269** the table has a cursor number of "base". pIdx is an index on pTab.
1270**
1271** nEqCol is the number of columns of pIdx that are used as equality
1272** constraints. Any of these columns may be missing from the ORDER BY
1273** clause and the match can still be a success.
1274**
drh51669862004-12-18 18:40:26 +00001275** All terms of the ORDER BY that match against the index must be either
1276** ASC or DESC. (Terms of the ORDER BY clause past the end of a UNIQUE
1277** index do not need to satisfy this constraint.) The *pbRev value is
1278** set to 1 if the ORDER BY clause is all DESC and it is set to 0 if
1279** the ORDER BY clause is all ASC.
1280*/
1281static int isSortingIndex(
1282 Parse *pParse, /* Parsing context */
drh111a6a72008-12-21 03:51:16 +00001283 WhereMaskSet *pMaskSet, /* Mapping from table cursor numbers to bitmaps */
drh51669862004-12-18 18:40:26 +00001284 Index *pIdx, /* The index we are testing */
drh74161702006-02-24 02:53:49 +00001285 int base, /* Cursor number for the table to be sorted */
drh51669862004-12-18 18:40:26 +00001286 ExprList *pOrderBy, /* The ORDER BY clause */
1287 int nEqCol, /* Number of index columns with == constraints */
1288 int *pbRev /* Set to 1 if ORDER BY is DESC */
1289){
drhb46b5772005-08-29 16:40:52 +00001290 int i, j; /* Loop counters */
drh85eeb692005-12-21 03:16:42 +00001291 int sortOrder = 0; /* XOR of index and ORDER BY sort direction */
drhb46b5772005-08-29 16:40:52 +00001292 int nTerm; /* Number of ORDER BY terms */
1293 struct ExprList_item *pTerm; /* A term of the ORDER BY clause */
drh51669862004-12-18 18:40:26 +00001294 sqlite3 *db = pParse->db;
1295
1296 assert( pOrderBy!=0 );
1297 nTerm = pOrderBy->nExpr;
1298 assert( nTerm>0 );
1299
1300 /* Match terms of the ORDER BY clause against columns of
1301 ** the index.
drhcc192542006-12-20 03:24:19 +00001302 **
1303 ** Note that indices have pIdx->nColumn regular columns plus
1304 ** one additional column containing the rowid. The rowid column
1305 ** of the index is also allowed to match against the ORDER BY
1306 ** clause.
drh51669862004-12-18 18:40:26 +00001307 */
drhcc192542006-12-20 03:24:19 +00001308 for(i=j=0, pTerm=pOrderBy->a; j<nTerm && i<=pIdx->nColumn; i++){
drh51669862004-12-18 18:40:26 +00001309 Expr *pExpr; /* The expression of the ORDER BY pTerm */
1310 CollSeq *pColl; /* The collating sequence of pExpr */
drh85eeb692005-12-21 03:16:42 +00001311 int termSortOrder; /* Sort order for this term */
drhcc192542006-12-20 03:24:19 +00001312 int iColumn; /* The i-th column of the index. -1 for rowid */
1313 int iSortOrder; /* 1 for DESC, 0 for ASC on the i-th index term */
1314 const char *zColl; /* Name of the collating sequence for i-th index term */
drh51669862004-12-18 18:40:26 +00001315
1316 pExpr = pTerm->pExpr;
1317 if( pExpr->op!=TK_COLUMN || pExpr->iTable!=base ){
1318 /* Can not use an index sort on anything that is not a column in the
1319 ** left-most table of the FROM clause */
drh7b4fc6a2007-02-06 13:26:32 +00001320 break;
drh51669862004-12-18 18:40:26 +00001321 }
1322 pColl = sqlite3ExprCollSeq(pParse, pExpr);
drhcc192542006-12-20 03:24:19 +00001323 if( !pColl ){
1324 pColl = db->pDfltColl;
1325 }
1326 if( i<pIdx->nColumn ){
1327 iColumn = pIdx->aiColumn[i];
1328 if( iColumn==pIdx->pTable->iPKey ){
1329 iColumn = -1;
1330 }
1331 iSortOrder = pIdx->aSortOrder[i];
1332 zColl = pIdx->azColl[i];
1333 }else{
1334 iColumn = -1;
1335 iSortOrder = 0;
1336 zColl = pColl->zName;
1337 }
1338 if( pExpr->iColumn!=iColumn || sqlite3StrICmp(pColl->zName, zColl) ){
drh9012bcb2004-12-19 00:11:35 +00001339 /* Term j of the ORDER BY clause does not match column i of the index */
1340 if( i<nEqCol ){
drh51669862004-12-18 18:40:26 +00001341 /* If an index column that is constrained by == fails to match an
1342 ** ORDER BY term, that is OK. Just ignore that column of the index
1343 */
1344 continue;
drhff354e92008-06-25 02:47:57 +00001345 }else if( i==pIdx->nColumn ){
1346 /* Index column i is the rowid. All other terms match. */
1347 break;
drh51669862004-12-18 18:40:26 +00001348 }else{
1349 /* If an index column fails to match and is not constrained by ==
1350 ** then the index cannot satisfy the ORDER BY constraint.
1351 */
1352 return 0;
1353 }
1354 }
danielk1977b3bf5562006-01-10 17:58:23 +00001355 assert( pIdx->aSortOrder!=0 );
drh85eeb692005-12-21 03:16:42 +00001356 assert( pTerm->sortOrder==0 || pTerm->sortOrder==1 );
drhcc192542006-12-20 03:24:19 +00001357 assert( iSortOrder==0 || iSortOrder==1 );
1358 termSortOrder = iSortOrder ^ pTerm->sortOrder;
drh51669862004-12-18 18:40:26 +00001359 if( i>nEqCol ){
drh85eeb692005-12-21 03:16:42 +00001360 if( termSortOrder!=sortOrder ){
drh51669862004-12-18 18:40:26 +00001361 /* Indices can only be used if all ORDER BY terms past the
1362 ** equality constraints are all either DESC or ASC. */
1363 return 0;
1364 }
1365 }else{
drh85eeb692005-12-21 03:16:42 +00001366 sortOrder = termSortOrder;
drh51669862004-12-18 18:40:26 +00001367 }
1368 j++;
1369 pTerm++;
drh7b4fc6a2007-02-06 13:26:32 +00001370 if( iColumn<0 && !referencesOtherTables(pOrderBy, pMaskSet, j, base) ){
drhcc192542006-12-20 03:24:19 +00001371 /* If the indexed column is the primary key and everything matches
drh7b4fc6a2007-02-06 13:26:32 +00001372 ** so far and none of the ORDER BY terms to the right reference other
1373 ** tables in the join, then we are assured that the index can be used
1374 ** to sort because the primary key is unique and so none of the other
1375 ** columns will make any difference
drhcc192542006-12-20 03:24:19 +00001376 */
1377 j = nTerm;
1378 }
drh51669862004-12-18 18:40:26 +00001379 }
1380
drhcc192542006-12-20 03:24:19 +00001381 *pbRev = sortOrder!=0;
drh8718f522005-08-13 16:13:04 +00001382 if( j>=nTerm ){
drhcc192542006-12-20 03:24:19 +00001383 /* All terms of the ORDER BY clause are covered by this index so
1384 ** this index can be used for sorting. */
1385 return 1;
1386 }
drh7b4fc6a2007-02-06 13:26:32 +00001387 if( pIdx->onError!=OE_None && i==pIdx->nColumn
1388 && !referencesOtherTables(pOrderBy, pMaskSet, j, base) ){
drhcc192542006-12-20 03:24:19 +00001389 /* All terms of this index match some prefix of the ORDER BY clause
drh7b4fc6a2007-02-06 13:26:32 +00001390 ** and the index is UNIQUE and no terms on the tail of the ORDER BY
1391 ** clause reference other tables in a join. If this is all true then
1392 ** the order by clause is superfluous. */
drh51669862004-12-18 18:40:26 +00001393 return 1;
1394 }
1395 return 0;
1396}
1397
1398/*
drhb6c29892004-11-22 19:12:19 +00001399** Check table to see if the ORDER BY clause in pOrderBy can be satisfied
1400** by sorting in order of ROWID. Return true if so and set *pbRev to be
1401** true for reverse ROWID and false for forward ROWID order.
1402*/
1403static int sortableByRowid(
1404 int base, /* Cursor number for table to be sorted */
1405 ExprList *pOrderBy, /* The ORDER BY clause */
drh111a6a72008-12-21 03:51:16 +00001406 WhereMaskSet *pMaskSet, /* Mapping from table cursors to bitmaps */
drhb6c29892004-11-22 19:12:19 +00001407 int *pbRev /* Set to 1 if ORDER BY is DESC */
1408){
1409 Expr *p;
1410
1411 assert( pOrderBy!=0 );
1412 assert( pOrderBy->nExpr>0 );
1413 p = pOrderBy->a[0].pExpr;
drh7b4fc6a2007-02-06 13:26:32 +00001414 if( p->op==TK_COLUMN && p->iTable==base && p->iColumn==-1
1415 && !referencesOtherTables(pOrderBy, pMaskSet, 1, base) ){
drhb6c29892004-11-22 19:12:19 +00001416 *pbRev = pOrderBy->a[0].sortOrder;
1417 return 1;
1418 }
1419 return 0;
1420}
1421
drhfe05af82005-07-21 03:14:59 +00001422/*
drhb6fb62d2005-09-20 08:47:20 +00001423** Prepare a crude estimate of the logarithm of the input value.
drh28c4cf42005-07-27 20:41:43 +00001424** The results need not be exact. This is only used for estimating
drh909626d2008-05-30 14:58:37 +00001425** the total cost of performing operations with O(logN) or O(NlogN)
drh28c4cf42005-07-27 20:41:43 +00001426** complexity. Because N is just a guess, it is no great tragedy if
1427** logN is a little off.
drh28c4cf42005-07-27 20:41:43 +00001428*/
1429static double estLog(double N){
drhb37df7b2005-10-13 02:09:49 +00001430 double logN = 1;
1431 double x = 10;
drh28c4cf42005-07-27 20:41:43 +00001432 while( N>x ){
drhb37df7b2005-10-13 02:09:49 +00001433 logN += 1;
drh28c4cf42005-07-27 20:41:43 +00001434 x *= 10;
1435 }
1436 return logN;
1437}
1438
drh6d209d82006-06-27 01:54:26 +00001439/*
1440** Two routines for printing the content of an sqlite3_index_info
1441** structure. Used for testing and debugging only. If neither
1442** SQLITE_TEST or SQLITE_DEBUG are defined, then these routines
1443** are no-ops.
1444*/
drh77a2a5e2007-04-06 01:04:39 +00001445#if !defined(SQLITE_OMIT_VIRTUALTABLE) && defined(SQLITE_DEBUG)
drh6d209d82006-06-27 01:54:26 +00001446static void TRACE_IDX_INPUTS(sqlite3_index_info *p){
1447 int i;
mlcreech3a00f902008-03-04 17:45:01 +00001448 if( !sqlite3WhereTrace ) return;
drh6d209d82006-06-27 01:54:26 +00001449 for(i=0; i<p->nConstraint; i++){
1450 sqlite3DebugPrintf(" constraint[%d]: col=%d termid=%d op=%d usabled=%d\n",
1451 i,
1452 p->aConstraint[i].iColumn,
1453 p->aConstraint[i].iTermOffset,
1454 p->aConstraint[i].op,
1455 p->aConstraint[i].usable);
1456 }
1457 for(i=0; i<p->nOrderBy; i++){
1458 sqlite3DebugPrintf(" orderby[%d]: col=%d desc=%d\n",
1459 i,
1460 p->aOrderBy[i].iColumn,
1461 p->aOrderBy[i].desc);
1462 }
1463}
1464static void TRACE_IDX_OUTPUTS(sqlite3_index_info *p){
1465 int i;
mlcreech3a00f902008-03-04 17:45:01 +00001466 if( !sqlite3WhereTrace ) return;
drh6d209d82006-06-27 01:54:26 +00001467 for(i=0; i<p->nConstraint; i++){
1468 sqlite3DebugPrintf(" usage[%d]: argvIdx=%d omit=%d\n",
1469 i,
1470 p->aConstraintUsage[i].argvIndex,
1471 p->aConstraintUsage[i].omit);
1472 }
1473 sqlite3DebugPrintf(" idxNum=%d\n", p->idxNum);
1474 sqlite3DebugPrintf(" idxStr=%s\n", p->idxStr);
1475 sqlite3DebugPrintf(" orderByConsumed=%d\n", p->orderByConsumed);
1476 sqlite3DebugPrintf(" estimatedCost=%g\n", p->estimatedCost);
1477}
1478#else
1479#define TRACE_IDX_INPUTS(A)
1480#define TRACE_IDX_OUTPUTS(A)
1481#endif
1482
danielk19771d461462009-04-21 09:02:45 +00001483/*
1484** Required because bestIndex() is called by bestOrClauseIndex()
1485*/
1486static void bestIndex(
1487 Parse*, WhereClause*, struct SrcList_item*, Bitmask, ExprList*, WhereCost*);
1488
1489/*
1490** This routine attempts to find an scanning strategy that can be used
1491** to optimize an 'OR' expression that is part of a WHERE clause.
1492**
1493** The table associated with FROM clause term pSrc may be either a
1494** regular B-Tree table or a virtual table.
1495*/
1496static void bestOrClauseIndex(
1497 Parse *pParse, /* The parsing context */
1498 WhereClause *pWC, /* The WHERE clause */
1499 struct SrcList_item *pSrc, /* The FROM clause term to search */
1500 Bitmask notReady, /* Mask of cursors that are not available */
1501 ExprList *pOrderBy, /* The ORDER BY clause */
1502 WhereCost *pCost /* Lowest cost query plan */
1503){
1504#ifndef SQLITE_OMIT_OR_OPTIMIZATION
1505 const int iCur = pSrc->iCursor; /* The cursor of the table to be accessed */
1506 const Bitmask maskSrc = getMask(pWC->pMaskSet, iCur); /* Bitmask for pSrc */
1507 WhereTerm * const pWCEnd = &pWC->a[pWC->nTerm]; /* End of pWC->a[] */
1508 WhereTerm *pTerm; /* A single term of the WHERE clause */
1509
1510 /* Search the WHERE clause terms for a usable WO_OR term. */
1511 for(pTerm=pWC->a; pTerm<pWCEnd; pTerm++){
1512 if( pTerm->eOperator==WO_OR
1513 && ((pTerm->prereqAll & ~maskSrc) & notReady)==0
1514 && (pTerm->u.pOrInfo->indexable & maskSrc)!=0
1515 ){
1516 WhereClause * const pOrWC = &pTerm->u.pOrInfo->wc;
1517 WhereTerm * const pOrWCEnd = &pOrWC->a[pOrWC->nTerm];
1518 WhereTerm *pOrTerm;
1519 int flags = WHERE_MULTI_OR;
1520 double rTotal = 0;
1521 double nRow = 0;
1522
1523 for(pOrTerm=pOrWC->a; pOrTerm<pOrWCEnd; pOrTerm++){
1524 WhereCost sTermCost;
1525 WHERETRACE(("... Multi-index OR testing for term %d of %d....\n",
1526 (pOrTerm - pOrWC->a), (pTerm - pWC->a)
1527 ));
1528 if( pOrTerm->eOperator==WO_AND ){
1529 WhereClause *pAndWC = &pOrTerm->u.pAndInfo->wc;
1530 bestIndex(pParse, pAndWC, pSrc, notReady, 0, &sTermCost);
1531 }else if( pOrTerm->leftCursor==iCur ){
1532 WhereClause tempWC;
1533 tempWC.pParse = pWC->pParse;
1534 tempWC.pMaskSet = pWC->pMaskSet;
1535 tempWC.op = TK_AND;
1536 tempWC.a = pOrTerm;
1537 tempWC.nTerm = 1;
1538 bestIndex(pParse, &tempWC, pSrc, notReady, 0, &sTermCost);
1539 }else{
1540 continue;
1541 }
1542 rTotal += sTermCost.rCost;
1543 nRow += sTermCost.nRow;
1544 if( rTotal>=pCost->rCost ) break;
1545 }
1546
1547 /* If there is an ORDER BY clause, increase the scan cost to account
1548 ** for the cost of the sort. */
1549 if( pOrderBy!=0 ){
1550 rTotal += nRow*estLog(nRow);
1551 WHERETRACE(("... sorting increases OR cost to %.9g\n", rTotal));
1552 }
1553
1554 /* If the cost of scanning using this OR term for optimization is
1555 ** less than the current cost stored in pCost, replace the contents
1556 ** of pCost. */
1557 WHERETRACE(("... multi-index OR cost=%.9g nrow=%.9g\n", rTotal, nRow));
1558 if( rTotal<pCost->rCost ){
1559 pCost->rCost = rTotal;
1560 pCost->nRow = nRow;
1561 pCost->plan.wsFlags = flags;
1562 pCost->plan.u.pTerm = pTerm;
1563 }
1564 }
1565 }
1566#endif /* SQLITE_OMIT_OR_OPTIMIZATION */
1567}
1568
drh9eff6162006-06-12 21:59:13 +00001569#ifndef SQLITE_OMIT_VIRTUALTABLE
1570/*
danielk19771d461462009-04-21 09:02:45 +00001571** Allocate and populate an sqlite3_index_info structure. It is the
1572** responsibility of the caller to eventually release the structure
1573** by passing the pointer returned by this function to sqlite3_free().
1574*/
1575static sqlite3_index_info *allocateIndexInfo(
1576 Parse *pParse,
1577 WhereClause *pWC,
1578 struct SrcList_item *pSrc,
1579 ExprList *pOrderBy
1580){
1581 int i, j;
1582 int nTerm;
1583 struct sqlite3_index_constraint *pIdxCons;
1584 struct sqlite3_index_orderby *pIdxOrderBy;
1585 struct sqlite3_index_constraint_usage *pUsage;
1586 WhereTerm *pTerm;
1587 int nOrderBy;
1588 sqlite3_index_info *pIdxInfo;
1589
1590 WHERETRACE(("Recomputing index info for %s...\n", pSrc->pTab->zName));
1591
1592 /* Count the number of possible WHERE clause constraints referring
1593 ** to this virtual table */
1594 for(i=nTerm=0, pTerm=pWC->a; i<pWC->nTerm; i++, pTerm++){
1595 if( pTerm->leftCursor != pSrc->iCursor ) continue;
1596 assert( (pTerm->eOperator&(pTerm->eOperator-1))==0 );
1597 testcase( pTerm->eOperator==WO_IN );
1598 testcase( pTerm->eOperator==WO_ISNULL );
1599 if( pTerm->eOperator & (WO_IN|WO_ISNULL) ) continue;
1600 nTerm++;
1601 }
1602
1603 /* If the ORDER BY clause contains only columns in the current
1604 ** virtual table then allocate space for the aOrderBy part of
1605 ** the sqlite3_index_info structure.
1606 */
1607 nOrderBy = 0;
1608 if( pOrderBy ){
1609 for(i=0; i<pOrderBy->nExpr; i++){
1610 Expr *pExpr = pOrderBy->a[i].pExpr;
1611 if( pExpr->op!=TK_COLUMN || pExpr->iTable!=pSrc->iCursor ) break;
1612 }
1613 if( i==pOrderBy->nExpr ){
1614 nOrderBy = pOrderBy->nExpr;
1615 }
1616 }
1617
1618 /* Allocate the sqlite3_index_info structure
1619 */
1620 pIdxInfo = sqlite3DbMallocZero(pParse->db, sizeof(*pIdxInfo)
1621 + (sizeof(*pIdxCons) + sizeof(*pUsage))*nTerm
1622 + sizeof(*pIdxOrderBy)*nOrderBy );
1623 if( pIdxInfo==0 ){
1624 sqlite3ErrorMsg(pParse, "out of memory");
1625 /* (double)0 In case of SQLITE_OMIT_FLOATING_POINT... */
1626 return 0;
1627 }
1628
1629 /* Initialize the structure. The sqlite3_index_info structure contains
1630 ** many fields that are declared "const" to prevent xBestIndex from
1631 ** changing them. We have to do some funky casting in order to
1632 ** initialize those fields.
1633 */
1634 pIdxCons = (struct sqlite3_index_constraint*)&pIdxInfo[1];
1635 pIdxOrderBy = (struct sqlite3_index_orderby*)&pIdxCons[nTerm];
1636 pUsage = (struct sqlite3_index_constraint_usage*)&pIdxOrderBy[nOrderBy];
1637 *(int*)&pIdxInfo->nConstraint = nTerm;
1638 *(int*)&pIdxInfo->nOrderBy = nOrderBy;
1639 *(struct sqlite3_index_constraint**)&pIdxInfo->aConstraint = pIdxCons;
1640 *(struct sqlite3_index_orderby**)&pIdxInfo->aOrderBy = pIdxOrderBy;
1641 *(struct sqlite3_index_constraint_usage**)&pIdxInfo->aConstraintUsage =
1642 pUsage;
1643
1644 for(i=j=0, pTerm=pWC->a; i<pWC->nTerm; i++, pTerm++){
1645 if( pTerm->leftCursor != pSrc->iCursor ) continue;
1646 assert( (pTerm->eOperator&(pTerm->eOperator-1))==0 );
1647 testcase( pTerm->eOperator==WO_IN );
1648 testcase( pTerm->eOperator==WO_ISNULL );
1649 if( pTerm->eOperator & (WO_IN|WO_ISNULL) ) continue;
1650 pIdxCons[j].iColumn = pTerm->u.leftColumn;
1651 pIdxCons[j].iTermOffset = i;
1652 pIdxCons[j].op = (u8)pTerm->eOperator;
1653 /* The direct assignment in the previous line is possible only because
1654 ** the WO_ and SQLITE_INDEX_CONSTRAINT_ codes are identical. The
1655 ** following asserts verify this fact. */
1656 assert( WO_EQ==SQLITE_INDEX_CONSTRAINT_EQ );
1657 assert( WO_LT==SQLITE_INDEX_CONSTRAINT_LT );
1658 assert( WO_LE==SQLITE_INDEX_CONSTRAINT_LE );
1659 assert( WO_GT==SQLITE_INDEX_CONSTRAINT_GT );
1660 assert( WO_GE==SQLITE_INDEX_CONSTRAINT_GE );
1661 assert( WO_MATCH==SQLITE_INDEX_CONSTRAINT_MATCH );
1662 assert( pTerm->eOperator & (WO_EQ|WO_LT|WO_LE|WO_GT|WO_GE|WO_MATCH) );
1663 j++;
1664 }
1665 for(i=0; i<nOrderBy; i++){
1666 Expr *pExpr = pOrderBy->a[i].pExpr;
1667 pIdxOrderBy[i].iColumn = pExpr->iColumn;
1668 pIdxOrderBy[i].desc = pOrderBy->a[i].sortOrder;
1669 }
1670
1671 return pIdxInfo;
1672}
1673
1674/*
1675** The table object reference passed as the second argument to this function
1676** must represent a virtual table. This function invokes the xBestIndex()
1677** method of the virtual table with the sqlite3_index_info pointer passed
1678** as the argument.
1679**
1680** If an error occurs, pParse is populated with an error message and a
1681** non-zero value is returned. Otherwise, 0 is returned and the output
1682** part of the sqlite3_index_info structure is left populated.
1683**
1684** Whether or not an error is returned, it is the responsibility of the
1685** caller to eventually free p->idxStr if p->needToFreeIdxStr indicates
1686** that this is required.
1687*/
1688static int vtabBestIndex(Parse *pParse, Table *pTab, sqlite3_index_info *p){
1689 sqlite3_vtab *pVtab = pTab->pVtab;
1690 int i;
1691 int rc;
1692
1693 (void)sqlite3SafetyOff(pParse->db);
1694 WHERETRACE(("xBestIndex for %s\n", pTab->zName));
1695 TRACE_IDX_INPUTS(p);
1696 rc = pVtab->pModule->xBestIndex(pVtab, p);
1697 TRACE_IDX_OUTPUTS(p);
1698 (void)sqlite3SafetyOn(pParse->db);
1699
1700 if( rc!=SQLITE_OK ){
1701 if( rc==SQLITE_NOMEM ){
1702 pParse->db->mallocFailed = 1;
1703 }else if( !pVtab->zErrMsg ){
1704 sqlite3ErrorMsg(pParse, "%s", sqlite3ErrStr(rc));
1705 }else{
1706 sqlite3ErrorMsg(pParse, "%s", pVtab->zErrMsg);
1707 }
1708 }
1709 sqlite3DbFree(pParse->db, pVtab->zErrMsg);
1710 pVtab->zErrMsg = 0;
1711
1712 for(i=0; i<p->nConstraint; i++){
1713 if( !p->aConstraint[i].usable && p->aConstraintUsage[i].argvIndex>0 ){
1714 sqlite3ErrorMsg(pParse,
1715 "table %s: xBestIndex returned an invalid plan", pTab->zName);
1716 }
1717 }
1718
1719 return pParse->nErr;
1720}
1721
1722
1723/*
drh7f375902006-06-13 17:38:59 +00001724** Compute the best index for a virtual table.
1725**
1726** The best index is computed by the xBestIndex method of the virtual
1727** table module. This routine is really just a wrapper that sets up
1728** the sqlite3_index_info structure that is used to communicate with
1729** xBestIndex.
1730**
1731** In a join, this routine might be called multiple times for the
1732** same virtual table. The sqlite3_index_info structure is created
1733** and initialized on the first invocation and reused on all subsequent
1734** invocations. The sqlite3_index_info structure is also used when
1735** code is generated to access the virtual table. The whereInfoDelete()
1736** routine takes care of freeing the sqlite3_index_info structure after
1737** everybody has finished with it.
drh9eff6162006-06-12 21:59:13 +00001738*/
danielk19771d461462009-04-21 09:02:45 +00001739static void bestVirtualIndex(
1740 Parse *pParse, /* The parsing context */
1741 WhereClause *pWC, /* The WHERE clause */
1742 struct SrcList_item *pSrc, /* The FROM clause term to search */
1743 Bitmask notReady, /* Mask of cursors that are not available */
1744 ExprList *pOrderBy, /* The order by clause */
1745 WhereCost *pCost, /* Lowest cost query plan */
1746 sqlite3_index_info **ppIdxInfo /* Index information passed to xBestIndex */
drh9eff6162006-06-12 21:59:13 +00001747){
1748 Table *pTab = pSrc->pTab;
1749 sqlite3_index_info *pIdxInfo;
1750 struct sqlite3_index_constraint *pIdxCons;
drh9eff6162006-06-12 21:59:13 +00001751 struct sqlite3_index_constraint_usage *pUsage;
1752 WhereTerm *pTerm;
1753 int i, j;
1754 int nOrderBy;
1755
danielk19776eacd282009-04-29 11:50:53 +00001756 /* Make sure wsFlags is initialized to some sane value. Otherwise, if the
1757 ** malloc in allocateIndexInfo() fails and this function returns leaving
1758 ** wsFlags in an uninitialized state, the caller may behave unpredictably.
1759 */
drh6a863cd2009-05-06 18:42:21 +00001760 memset(pCost, 0, sizeof(*pCost));
danielk19776eacd282009-04-29 11:50:53 +00001761 pCost->plan.wsFlags = WHERE_VIRTUALTABLE;
1762
drh9eff6162006-06-12 21:59:13 +00001763 /* If the sqlite3_index_info structure has not been previously
danielk19771d461462009-04-21 09:02:45 +00001764 ** allocated and initialized, then allocate and initialize it now.
drh9eff6162006-06-12 21:59:13 +00001765 */
1766 pIdxInfo = *ppIdxInfo;
1767 if( pIdxInfo==0 ){
danielk19771d461462009-04-21 09:02:45 +00001768 *ppIdxInfo = pIdxInfo = allocateIndexInfo(pParse, pWC, pSrc, pOrderBy);
drh9eff6162006-06-12 21:59:13 +00001769 }
danielk1977732dc552009-04-21 17:23:04 +00001770 if( pIdxInfo==0 ){
1771 return;
1772 }
drh9eff6162006-06-12 21:59:13 +00001773
drh7f375902006-06-13 17:38:59 +00001774 /* At this point, the sqlite3_index_info structure that pIdxInfo points
1775 ** to will have been initialized, either during the current invocation or
1776 ** during some prior invocation. Now we just have to customize the
1777 ** details of pIdxInfo for the current invocation and pass it to
1778 ** xBestIndex.
1779 */
1780
danielk1977935ed5e2007-03-30 09:13:13 +00001781 /* The module name must be defined. Also, by this point there must
1782 ** be a pointer to an sqlite3_vtab structure. Otherwise
1783 ** sqlite3ViewGetColumnNames() would have picked up the error.
1784 */
drh9eff6162006-06-12 21:59:13 +00001785 assert( pTab->azModuleArg && pTab->azModuleArg[0] );
danielk19771d461462009-04-21 09:02:45 +00001786 assert( pTab->pVtab );
drh9eff6162006-06-12 21:59:13 +00001787
1788 /* Set the aConstraint[].usable fields and initialize all
drh7f375902006-06-13 17:38:59 +00001789 ** output variables to zero.
1790 **
1791 ** aConstraint[].usable is true for constraints where the right-hand
1792 ** side contains only references to tables to the left of the current
1793 ** table. In other words, if the constraint is of the form:
1794 **
1795 ** column = expr
1796 **
1797 ** and we are evaluating a join, then the constraint on column is
1798 ** only valid if all tables referenced in expr occur to the left
1799 ** of the table containing column.
1800 **
1801 ** The aConstraints[] array contains entries for all constraints
1802 ** on the current table. That way we only have to compute it once
1803 ** even though we might try to pick the best index multiple times.
1804 ** For each attempt at picking an index, the order of tables in the
1805 ** join might be different so we have to recompute the usable flag
1806 ** each time.
drh9eff6162006-06-12 21:59:13 +00001807 */
1808 pIdxCons = *(struct sqlite3_index_constraint**)&pIdxInfo->aConstraint;
1809 pUsage = pIdxInfo->aConstraintUsage;
1810 for(i=0; i<pIdxInfo->nConstraint; i++, pIdxCons++){
1811 j = pIdxCons->iTermOffset;
1812 pTerm = &pWC->a[j];
drhec1724e2008-12-09 01:32:03 +00001813 pIdxCons->usable = (pTerm->prereqRight & notReady)==0 ?1:0;
drh9eff6162006-06-12 21:59:13 +00001814 }
1815 memset(pUsage, 0, sizeof(pUsage[0])*pIdxInfo->nConstraint);
drh4be8b512006-06-13 23:51:34 +00001816 if( pIdxInfo->needToFreeIdxStr ){
1817 sqlite3_free(pIdxInfo->idxStr);
1818 }
1819 pIdxInfo->idxStr = 0;
1820 pIdxInfo->idxNum = 0;
1821 pIdxInfo->needToFreeIdxStr = 0;
drh9eff6162006-06-12 21:59:13 +00001822 pIdxInfo->orderByConsumed = 0;
shanefbd60f82009-02-04 03:59:25 +00001823 /* ((double)2) In case of SQLITE_OMIT_FLOATING_POINT... */
1824 pIdxInfo->estimatedCost = SQLITE_BIG_DBL / ((double)2);
drh9eff6162006-06-12 21:59:13 +00001825 nOrderBy = pIdxInfo->nOrderBy;
danielk19771d461462009-04-21 09:02:45 +00001826 if( !pOrderBy ){
1827 pIdxInfo->nOrderBy = 0;
drh9eff6162006-06-12 21:59:13 +00001828 }
danielk197774cdba42006-06-19 12:02:58 +00001829
danielk19771d461462009-04-21 09:02:45 +00001830 if( vtabBestIndex(pParse, pTab, pIdxInfo) ){
1831 return;
danielk197739359dc2008-03-17 09:36:44 +00001832 }
1833
danielk19771d461462009-04-21 09:02:45 +00001834 /* The cost is not allowed to be larger than SQLITE_BIG_DBL (the
1835 ** inital value of lowestCost in this loop. If it is, then the
1836 ** (cost<lowestCost) test below will never be true.
1837 **
1838 ** Use "(double)2" instead of "2.0" in case OMIT_FLOATING_POINT
1839 ** is defined.
1840 */
1841 if( (SQLITE_BIG_DBL/((double)2))<pIdxInfo->estimatedCost ){
1842 pCost->rCost = (SQLITE_BIG_DBL/((double)2));
1843 }else{
1844 pCost->rCost = pIdxInfo->estimatedCost;
1845 }
danielk19771d461462009-04-21 09:02:45 +00001846 pCost->plan.u.pVtabIdx = pIdxInfo;
1847 if( pIdxInfo && pIdxInfo->orderByConsumed ){
1848 pCost->plan.wsFlags |= WHERE_ORDERBY;
1849 }
1850 pCost->plan.nEq = 0;
1851 pIdxInfo->nOrderBy = nOrderBy;
1852
1853 /* Try to find a more efficient access pattern by using multiple indexes
1854 ** to optimize an OR expression within the WHERE clause.
1855 */
1856 bestOrClauseIndex(pParse, pWC, pSrc, notReady, pOrderBy, pCost);
drh9eff6162006-06-12 21:59:13 +00001857}
1858#endif /* SQLITE_OMIT_VIRTUALTABLE */
1859
drh28c4cf42005-07-27 20:41:43 +00001860/*
drh111a6a72008-12-21 03:51:16 +00001861** Find the query plan for accessing a particular table. Write the
1862** best query plan and its cost into the WhereCost object supplied as the
1863** last parameter.
drh51147ba2005-07-23 22:59:55 +00001864**
drh111a6a72008-12-21 03:51:16 +00001865** The lowest cost plan wins. The cost is an estimate of the amount of
1866** CPU and disk I/O need to process the request using the selected plan.
drh51147ba2005-07-23 22:59:55 +00001867** Factors that influence cost include:
1868**
1869** * The estimated number of rows that will be retrieved. (The
1870** fewer the better.)
1871**
1872** * Whether or not sorting must occur.
1873**
1874** * Whether or not there must be separate lookups in the
1875** index and in the main table.
1876**
danielk1977e2d7b242009-02-23 17:33:49 +00001877** If there was an INDEXED BY clause (pSrc->pIndex) attached to the table in
1878** the SQL statement, then this function only considers plans using the
drh296a4832009-03-22 20:36:18 +00001879** named index. If no such plan is found, then the returned cost is
1880** SQLITE_BIG_DBL. If a plan is found that uses the named index,
danielk197785574e32008-10-06 05:32:18 +00001881** then the cost is calculated in the usual way.
1882**
danielk1977e2d7b242009-02-23 17:33:49 +00001883** If a NOT INDEXED clause (pSrc->notIndexed!=0) was attached to the table
1884** in the SELECT statement, then no indexes are considered. However, the
1885** selected plan may still take advantage of the tables built-in rowid
danielk197785574e32008-10-06 05:32:18 +00001886** index.
drhfe05af82005-07-21 03:14:59 +00001887*/
danielk19771d461462009-04-21 09:02:45 +00001888static void bestBtreeIndex(
drhfe05af82005-07-21 03:14:59 +00001889 Parse *pParse, /* The parsing context */
1890 WhereClause *pWC, /* The WHERE clause */
1891 struct SrcList_item *pSrc, /* The FROM clause term to search */
1892 Bitmask notReady, /* Mask of cursors that are not available */
drh111a6a72008-12-21 03:51:16 +00001893 ExprList *pOrderBy, /* The ORDER BY clause */
1894 WhereCost *pCost /* Lowest cost query plan */
drhfe05af82005-07-21 03:14:59 +00001895){
drh111a6a72008-12-21 03:51:16 +00001896 WhereTerm *pTerm; /* A single term of the WHERE clause */
drh51147ba2005-07-23 22:59:55 +00001897 int iCur = pSrc->iCursor; /* The cursor of the table to be accessed */
1898 Index *pProbe; /* An index we are evaluating */
1899 int rev; /* True to scan in reverse order */
drh165be382008-12-05 02:36:33 +00001900 int wsFlags; /* Flags associated with pProbe */
drh51147ba2005-07-23 22:59:55 +00001901 int nEq; /* Number of == or IN constraints */
drhc49de5d2007-01-19 01:06:01 +00001902 int eqTermMask; /* Mask of valid equality operators */
drh51147ba2005-07-23 22:59:55 +00001903 double cost; /* Cost of using pProbe */
drh111a6a72008-12-21 03:51:16 +00001904 double nRow; /* Estimated number of rows in result set */
drhdd5f5a62008-12-23 13:35:23 +00001905 int i; /* Loop counter */
drhfe05af82005-07-21 03:14:59 +00001906
drh165be382008-12-05 02:36:33 +00001907 WHERETRACE(("bestIndex: tbl=%s notReady=%llx\n", pSrc->pTab->zName,notReady));
drh4dd238a2006-03-28 23:55:57 +00001908 pProbe = pSrc->pTab->pIndex;
danielk197785574e32008-10-06 05:32:18 +00001909 if( pSrc->notIndexed ){
1910 pProbe = 0;
1911 }
drh4dd238a2006-03-28 23:55:57 +00001912
1913 /* If the table has no indices and there are no terms in the where
1914 ** clause that refer to the ROWID, then we will never be able to do
1915 ** anything other than a full table scan on this table. We might as
1916 ** well put it first in the join order. That way, perhaps it can be
1917 ** referenced by other tables in the join.
1918 */
drh111a6a72008-12-21 03:51:16 +00001919 memset(pCost, 0, sizeof(*pCost));
drh4dd238a2006-03-28 23:55:57 +00001920 if( pProbe==0 &&
1921 findTerm(pWC, iCur, -1, 0, WO_EQ|WO_IN|WO_LT|WO_LE|WO_GT|WO_GE,0)==0 &&
drh7b4fc6a2007-02-06 13:26:32 +00001922 (pOrderBy==0 || !sortableByRowid(iCur, pOrderBy, pWC->pMaskSet, &rev)) ){
drh69a442e2009-04-06 12:26:57 +00001923 if( pParse->db->flags & SQLITE_ReverseOrder ){
1924 /* For application testing, randomly reverse the output order for
1925 ** SELECT statements that omit the ORDER BY clause. This will help
1926 ** to find cases where
1927 */
1928 pCost->plan.wsFlags |= WHERE_REVERSE;
1929 }
drh111a6a72008-12-21 03:51:16 +00001930 return;
drh4dd238a2006-03-28 23:55:57 +00001931 }
drh111a6a72008-12-21 03:51:16 +00001932 pCost->rCost = SQLITE_BIG_DBL;
drh51147ba2005-07-23 22:59:55 +00001933
danielk197785574e32008-10-06 05:32:18 +00001934 /* Check for a rowid=EXPR or rowid IN (...) constraints. If there was
1935 ** an INDEXED BY clause attached to this table, skip this step.
drhfe05af82005-07-21 03:14:59 +00001936 */
danielk197785574e32008-10-06 05:32:18 +00001937 if( !pSrc->pIndex ){
1938 pTerm = findTerm(pWC, iCur, -1, notReady, WO_EQ|WO_IN, 0);
1939 if( pTerm ){
1940 Expr *pExpr;
drh111a6a72008-12-21 03:51:16 +00001941 pCost->plan.wsFlags = WHERE_ROWID_EQ;
danielk197785574e32008-10-06 05:32:18 +00001942 if( pTerm->eOperator & WO_EQ ){
1943 /* Rowid== is always the best pick. Look no further. Because only
1944 ** a single row is generated, output is always in sorted order */
drh111a6a72008-12-21 03:51:16 +00001945 pCost->plan.wsFlags = WHERE_ROWID_EQ | WHERE_UNIQUE;
1946 pCost->plan.nEq = 1;
danielk197785574e32008-10-06 05:32:18 +00001947 WHERETRACE(("... best is rowid\n"));
drh111a6a72008-12-21 03:51:16 +00001948 pCost->rCost = 0;
1949 pCost->nRow = 1;
1950 return;
danielk19776ab3a2e2009-02-19 14:39:25 +00001951 }else if( !ExprHasProperty((pExpr = pTerm->pExpr), EP_xIsSelect)
1952 && pExpr->x.pList
1953 ){
danielk197785574e32008-10-06 05:32:18 +00001954 /* Rowid IN (LIST): cost is NlogN where N is the number of list
1955 ** elements. */
danielk19776ab3a2e2009-02-19 14:39:25 +00001956 pCost->rCost = pCost->nRow = pExpr->x.pList->nExpr;
drh111a6a72008-12-21 03:51:16 +00001957 pCost->rCost *= estLog(pCost->rCost);
danielk197785574e32008-10-06 05:32:18 +00001958 }else{
1959 /* Rowid IN (SELECT): cost is NlogN where N is the number of rows
1960 ** in the result of the inner select. We have no way to estimate
1961 ** that value so make a wild guess. */
drh111a6a72008-12-21 03:51:16 +00001962 pCost->nRow = 100;
1963 pCost->rCost = 200;
drh28c4cf42005-07-27 20:41:43 +00001964 }
drh111a6a72008-12-21 03:51:16 +00001965 WHERETRACE(("... rowid IN cost: %.9g\n", pCost->rCost));
drh51147ba2005-07-23 22:59:55 +00001966 }
danielk197785574e32008-10-06 05:32:18 +00001967
1968 /* Estimate the cost of a table scan. If we do not know how many
1969 ** entries are in the table, use 1 million as a guess.
1970 */
1971 cost = pProbe ? pProbe->aiRowEst[0] : 1000000;
1972 WHERETRACE(("... table scan base cost: %.9g\n", cost));
drh165be382008-12-05 02:36:33 +00001973 wsFlags = WHERE_ROWID_RANGE;
danielk197785574e32008-10-06 05:32:18 +00001974
1975 /* Check for constraints on a range of rowids in a table scan.
1976 */
1977 pTerm = findTerm(pWC, iCur, -1, notReady, WO_LT|WO_LE|WO_GT|WO_GE, 0);
1978 if( pTerm ){
1979 if( findTerm(pWC, iCur, -1, notReady, WO_LT|WO_LE, 0) ){
drh165be382008-12-05 02:36:33 +00001980 wsFlags |= WHERE_TOP_LIMIT;
drh700a2262008-12-17 19:22:15 +00001981 cost /= 3; /* Guess that rowid<EXPR eliminates two-thirds of rows */
danielk197785574e32008-10-06 05:32:18 +00001982 }
1983 if( findTerm(pWC, iCur, -1, notReady, WO_GT|WO_GE, 0) ){
drh165be382008-12-05 02:36:33 +00001984 wsFlags |= WHERE_BTM_LIMIT;
danielk197785574e32008-10-06 05:32:18 +00001985 cost /= 3; /* Guess that rowid>EXPR eliminates two-thirds of rows */
1986 }
1987 WHERETRACE(("... rowid range reduces cost to %.9g\n", cost));
1988 }else{
drh165be382008-12-05 02:36:33 +00001989 wsFlags = 0;
danielk197785574e32008-10-06 05:32:18 +00001990 }
drh111a6a72008-12-21 03:51:16 +00001991 nRow = cost;
danielk197785574e32008-10-06 05:32:18 +00001992
1993 /* If the table scan does not satisfy the ORDER BY clause, increase
1994 ** the cost by NlogN to cover the expense of sorting. */
1995 if( pOrderBy ){
1996 if( sortableByRowid(iCur, pOrderBy, pWC->pMaskSet, &rev) ){
drh165be382008-12-05 02:36:33 +00001997 wsFlags |= WHERE_ORDERBY|WHERE_ROWID_RANGE;
danielk197785574e32008-10-06 05:32:18 +00001998 if( rev ){
drh165be382008-12-05 02:36:33 +00001999 wsFlags |= WHERE_REVERSE;
danielk197785574e32008-10-06 05:32:18 +00002000 }
2001 }else{
2002 cost += cost*estLog(cost);
2003 WHERETRACE(("... sorting increases cost to %.9g\n", cost));
2004 }
drh699b3d42009-02-23 16:52:07 +00002005 }else if( pParse->db->flags & SQLITE_ReverseOrder ){
2006 /* For application testing, randomly reverse the output order for
2007 ** SELECT statements that omit the ORDER BY clause. This will help
2008 ** to find cases where
2009 */
2010 wsFlags |= WHERE_REVERSE;
danielk197785574e32008-10-06 05:32:18 +00002011 }
drh699b3d42009-02-23 16:52:07 +00002012
2013 /* Remember this case if it is the best so far */
drh111a6a72008-12-21 03:51:16 +00002014 if( cost<pCost->rCost ){
2015 pCost->rCost = cost;
2016 pCost->nRow = nRow;
2017 pCost->plan.wsFlags = wsFlags;
danielk197785574e32008-10-06 05:32:18 +00002018 }
drhfe05af82005-07-21 03:14:59 +00002019 }
2020
danielk19771d461462009-04-21 09:02:45 +00002021 bestOrClauseIndex(pParse, pWC, pSrc, notReady, pOrderBy, pCost);
drhdd5f5a62008-12-23 13:35:23 +00002022
drhc49de5d2007-01-19 01:06:01 +00002023 /* If the pSrc table is the right table of a LEFT JOIN then we may not
2024 ** use an index to satisfy IS NULL constraints on that table. This is
2025 ** because columns might end up being NULL if the table does not match -
2026 ** a circumstance which the index cannot help us discover. Ticket #2177.
2027 */
2028 if( (pSrc->jointype & JT_LEFT)!=0 ){
2029 eqTermMask = WO_EQ|WO_IN;
2030 }else{
2031 eqTermMask = WO_EQ|WO_IN|WO_ISNULL;
2032 }
2033
drhfe05af82005-07-21 03:14:59 +00002034 /* Look at each index.
2035 */
danielk197785574e32008-10-06 05:32:18 +00002036 if( pSrc->pIndex ){
2037 pProbe = pSrc->pIndex;
2038 }
2039 for(; pProbe; pProbe=(pSrc->pIndex ? 0 : pProbe->pNext)){
drh75572e92009-03-29 00:13:03 +00002040 double inMultiplier = 1; /* Number of equality look-ups needed */
2041 int inMultIsEst = 0; /* True if inMultiplier is an estimate */
drh51147ba2005-07-23 22:59:55 +00002042
drh4f0c5872007-03-26 22:05:01 +00002043 WHERETRACE(("... index %s:\n", pProbe->zName));
drhfe05af82005-07-21 03:14:59 +00002044
2045 /* Count the number of columns in the index that are satisfied
drh46619d62009-04-24 14:51:42 +00002046 ** by x=EXPR or x IS NULL constraints or x IN (...) constraints.
2047 ** For a term of the form x=EXPR or x IS NULL we only have to do
2048 ** a single binary search. But for x IN (...) we have to do a
2049 ** number of binary searched
drh75572e92009-03-29 00:13:03 +00002050 ** equal to the number of entries on the RHS of the IN operator.
2051 ** The inMultipler variable with try to estimate the number of
2052 ** binary searches needed.
drhfe05af82005-07-21 03:14:59 +00002053 */
drh165be382008-12-05 02:36:33 +00002054 wsFlags = 0;
drhfe05af82005-07-21 03:14:59 +00002055 for(i=0; i<pProbe->nColumn; i++){
2056 int j = pProbe->aiColumn[i];
drhc49de5d2007-01-19 01:06:01 +00002057 pTerm = findTerm(pWC, iCur, j, notReady, eqTermMask, pProbe);
drhfe05af82005-07-21 03:14:59 +00002058 if( pTerm==0 ) break;
drh165be382008-12-05 02:36:33 +00002059 wsFlags |= WHERE_COLUMN_EQ;
drhb52076c2006-01-23 13:22:09 +00002060 if( pTerm->eOperator & WO_IN ){
drha6110402005-07-28 20:51:19 +00002061 Expr *pExpr = pTerm->pExpr;
drh165be382008-12-05 02:36:33 +00002062 wsFlags |= WHERE_COLUMN_IN;
danielk19776ab3a2e2009-02-19 14:39:25 +00002063 if( ExprHasProperty(pExpr, EP_xIsSelect) ){
drhffe0f892006-05-11 13:26:25 +00002064 inMultiplier *= 25;
drh75572e92009-03-29 00:13:03 +00002065 inMultIsEst = 1;
danielk19776ab3a2e2009-02-19 14:39:25 +00002066 }else if( pExpr->x.pList ){
2067 inMultiplier *= pExpr->x.pList->nExpr + 1;
drhfe05af82005-07-21 03:14:59 +00002068 }
drh46619d62009-04-24 14:51:42 +00002069 }else if( pTerm->eOperator & WO_ISNULL ){
2070 wsFlags |= WHERE_COLUMN_NULL;
drhfe05af82005-07-21 03:14:59 +00002071 }
2072 }
drh111a6a72008-12-21 03:51:16 +00002073 nRow = pProbe->aiRowEst[i] * inMultiplier;
drh75572e92009-03-29 00:13:03 +00002074 /* If inMultiplier is an estimate and that estimate results in an
2075 ** nRow it that is more than half number of rows in the table,
2076 ** then reduce inMultipler */
2077 if( inMultIsEst && nRow*2 > pProbe->aiRowEst[0] ){
2078 nRow = pProbe->aiRowEst[0]/2;
2079 inMultiplier = nRow/pProbe->aiRowEst[i];
2080 }
2081 cost = nRow + inMultiplier*estLog(pProbe->aiRowEst[0]);
drh51147ba2005-07-23 22:59:55 +00002082 nEq = i;
drh46619d62009-04-24 14:51:42 +00002083 if( pProbe->onError!=OE_None && nEq==pProbe->nColumn ){
2084 testcase( wsFlags & WHERE_COLUMN_IN );
2085 testcase( wsFlags & WHERE_COLUMN_NULL );
2086 if( (wsFlags & (WHERE_COLUMN_IN|WHERE_COLUMN_NULL))==0 ){
2087 wsFlags |= WHERE_UNIQUE;
2088 }
drh943af3c2005-07-29 19:43:58 +00002089 }
drh75572e92009-03-29 00:13:03 +00002090 WHERETRACE(("...... nEq=%d inMult=%.9g nRow=%.9g cost=%.9g\n",
2091 nEq, inMultiplier, nRow, cost));
drhfe05af82005-07-21 03:14:59 +00002092
drh75572e92009-03-29 00:13:03 +00002093 /* Look for range constraints. Assume that each range constraint
2094 ** makes the search space 1/3rd smaller.
drhfe05af82005-07-21 03:14:59 +00002095 */
drh51147ba2005-07-23 22:59:55 +00002096 if( nEq<pProbe->nColumn ){
2097 int j = pProbe->aiColumn[nEq];
2098 pTerm = findTerm(pWC, iCur, j, notReady, WO_LT|WO_LE|WO_GT|WO_GE, pProbe);
2099 if( pTerm ){
drh165be382008-12-05 02:36:33 +00002100 wsFlags |= WHERE_COLUMN_RANGE;
drh51147ba2005-07-23 22:59:55 +00002101 if( findTerm(pWC, iCur, j, notReady, WO_LT|WO_LE, pProbe) ){
drh165be382008-12-05 02:36:33 +00002102 wsFlags |= WHERE_TOP_LIMIT;
drhb37df7b2005-10-13 02:09:49 +00002103 cost /= 3;
drh111a6a72008-12-21 03:51:16 +00002104 nRow /= 3;
drh51147ba2005-07-23 22:59:55 +00002105 }
2106 if( findTerm(pWC, iCur, j, notReady, WO_GT|WO_GE, pProbe) ){
drh165be382008-12-05 02:36:33 +00002107 wsFlags |= WHERE_BTM_LIMIT;
drhb37df7b2005-10-13 02:09:49 +00002108 cost /= 3;
drh111a6a72008-12-21 03:51:16 +00002109 nRow /= 3;
drh51147ba2005-07-23 22:59:55 +00002110 }
drh75572e92009-03-29 00:13:03 +00002111 WHERETRACE(("...... range reduces nRow to %.9g and cost to %.9g\n",
2112 nRow, cost));
drh51147ba2005-07-23 22:59:55 +00002113 }
2114 }
2115
drh28c4cf42005-07-27 20:41:43 +00002116 /* Add the additional cost of sorting if that is a factor.
drh51147ba2005-07-23 22:59:55 +00002117 */
drh28c4cf42005-07-27 20:41:43 +00002118 if( pOrderBy ){
drh46619d62009-04-24 14:51:42 +00002119 if( (wsFlags & (WHERE_COLUMN_IN|WHERE_COLUMN_NULL))==0
2120 && isSortingIndex(pParse,pWC->pMaskSet,pProbe,iCur,pOrderBy,nEq,&rev)
2121 ){
drh165be382008-12-05 02:36:33 +00002122 if( wsFlags==0 ){
2123 wsFlags = WHERE_COLUMN_RANGE;
drh28c4cf42005-07-27 20:41:43 +00002124 }
drh165be382008-12-05 02:36:33 +00002125 wsFlags |= WHERE_ORDERBY;
drh28c4cf42005-07-27 20:41:43 +00002126 if( rev ){
drh165be382008-12-05 02:36:33 +00002127 wsFlags |= WHERE_REVERSE;
drh28c4cf42005-07-27 20:41:43 +00002128 }
2129 }else{
2130 cost += cost*estLog(cost);
drh4f0c5872007-03-26 22:05:01 +00002131 WHERETRACE(("...... orderby increases cost to %.9g\n", cost));
drh51147ba2005-07-23 22:59:55 +00002132 }
drh699b3d42009-02-23 16:52:07 +00002133 }else if( pParse->db->flags & SQLITE_ReverseOrder ){
2134 /* For application testing, randomly reverse the output order for
2135 ** SELECT statements that omit the ORDER BY clause. This will help
2136 ** to find cases where
2137 */
2138 wsFlags |= WHERE_REVERSE;
drhfe05af82005-07-21 03:14:59 +00002139 }
2140
2141 /* Check to see if we can get away with using just the index without
drh51147ba2005-07-23 22:59:55 +00002142 ** ever reading the table. If that is the case, then halve the
2143 ** cost of this index.
drhfe05af82005-07-21 03:14:59 +00002144 */
drh165be382008-12-05 02:36:33 +00002145 if( wsFlags && pSrc->colUsed < (((Bitmask)1)<<(BMS-1)) ){
drhfe05af82005-07-21 03:14:59 +00002146 Bitmask m = pSrc->colUsed;
2147 int j;
2148 for(j=0; j<pProbe->nColumn; j++){
2149 int x = pProbe->aiColumn[j];
2150 if( x<BMS-1 ){
2151 m &= ~(((Bitmask)1)<<x);
2152 }
2153 }
2154 if( m==0 ){
drh165be382008-12-05 02:36:33 +00002155 wsFlags |= WHERE_IDX_ONLY;
drhb37df7b2005-10-13 02:09:49 +00002156 cost /= 2;
drh4f0c5872007-03-26 22:05:01 +00002157 WHERETRACE(("...... idx-only reduces cost to %.9g\n", cost));
drhfe05af82005-07-21 03:14:59 +00002158 }
2159 }
2160
drh51147ba2005-07-23 22:59:55 +00002161 /* If this index has achieved the lowest cost so far, then use it.
drhfe05af82005-07-21 03:14:59 +00002162 */
drh111a6a72008-12-21 03:51:16 +00002163 if( wsFlags!=0 && cost < pCost->rCost ){
2164 pCost->rCost = cost;
2165 pCost->nRow = nRow;
2166 pCost->plan.wsFlags = wsFlags;
2167 pCost->plan.nEq = nEq;
2168 assert( pCost->plan.wsFlags & WHERE_INDEXED );
2169 pCost->plan.u.pIdx = pProbe;
drhfe05af82005-07-21 03:14:59 +00002170 }
2171 }
2172
drhfe05af82005-07-21 03:14:59 +00002173 /* Report the best result
2174 */
drh111a6a72008-12-21 03:51:16 +00002175 pCost->plan.wsFlags |= eqTermMask;
2176 WHERETRACE(("best index is %s, cost=%.9g, nrow=%.9g, wsFlags=%x, nEq=%d\n",
2177 (pCost->plan.wsFlags & WHERE_INDEXED)!=0 ?
2178 pCost->plan.u.pIdx->zName : "(none)", pCost->nRow,
2179 pCost->rCost, pCost->plan.wsFlags, pCost->plan.nEq));
drhfe05af82005-07-21 03:14:59 +00002180}
2181
danielk19771d461462009-04-21 09:02:45 +00002182/*
2183** Find the query plan for accessing table pSrc->pTab. Write the
2184** best query plan and its cost into the WhereCost object supplied
2185** as the last parameter. This function may calculate the cost of
2186** both real and virtual table scans.
2187*/
2188static void bestIndex(
2189 Parse *pParse, /* The parsing context */
2190 WhereClause *pWC, /* The WHERE clause */
2191 struct SrcList_item *pSrc, /* The FROM clause term to search */
2192 Bitmask notReady, /* Mask of cursors that are not available */
2193 ExprList *pOrderBy, /* The ORDER BY clause */
2194 WhereCost *pCost /* Lowest cost query plan */
2195){
2196 if( IsVirtual(pSrc->pTab) ){
2197 sqlite3_index_info *p = 0;
2198 bestVirtualIndex(pParse, pWC, pSrc, notReady, pOrderBy, pCost, &p);
2199 if( p->needToFreeIdxStr ){
2200 sqlite3_free(p->idxStr);
2201 }
2202 sqlite3DbFree(pParse->db, p);
2203 }else{
2204 bestBtreeIndex(pParse, pWC, pSrc, notReady, pOrderBy, pCost);
2205 }
2206}
drhb6c29892004-11-22 19:12:19 +00002207
2208/*
drh2ffb1182004-07-19 19:14:01 +00002209** Disable a term in the WHERE clause. Except, do not disable the term
2210** if it controls a LEFT OUTER JOIN and it did not originate in the ON
2211** or USING clause of that join.
2212**
2213** Consider the term t2.z='ok' in the following queries:
2214**
2215** (1) SELECT * FROM t1 LEFT JOIN t2 ON t1.a=t2.x WHERE t2.z='ok'
2216** (2) SELECT * FROM t1 LEFT JOIN t2 ON t1.a=t2.x AND t2.z='ok'
2217** (3) SELECT * FROM t1, t2 WHERE t1.a=t2.x AND t2.z='ok'
2218**
drh23bf66d2004-12-14 03:34:34 +00002219** The t2.z='ok' is disabled in the in (2) because it originates
drh2ffb1182004-07-19 19:14:01 +00002220** in the ON clause. The term is disabled in (3) because it is not part
2221** of a LEFT OUTER JOIN. In (1), the term is not disabled.
2222**
2223** Disabling a term causes that term to not be tested in the inner loop
drhb6fb62d2005-09-20 08:47:20 +00002224** of the join. Disabling is an optimization. When terms are satisfied
2225** by indices, we disable them to prevent redundant tests in the inner
2226** loop. We would get the correct results if nothing were ever disabled,
2227** but joins might run a little slower. The trick is to disable as much
2228** as we can without disabling too much. If we disabled in (1), we'd get
2229** the wrong answer. See ticket #813.
drh2ffb1182004-07-19 19:14:01 +00002230*/
drh0fcef5e2005-07-19 17:38:22 +00002231static void disableTerm(WhereLevel *pLevel, WhereTerm *pTerm){
2232 if( pTerm
drh165be382008-12-05 02:36:33 +00002233 && ALWAYS((pTerm->wtFlags & TERM_CODED)==0)
drh0fcef5e2005-07-19 17:38:22 +00002234 && (pLevel->iLeftJoin==0 || ExprHasProperty(pTerm->pExpr, EP_FromJoin))
2235 ){
drh165be382008-12-05 02:36:33 +00002236 pTerm->wtFlags |= TERM_CODED;
drh45b1ee42005-08-02 17:48:22 +00002237 if( pTerm->iParent>=0 ){
2238 WhereTerm *pOther = &pTerm->pWC->a[pTerm->iParent];
2239 if( (--pOther->nChild)==0 ){
drhed378002005-07-28 23:12:08 +00002240 disableTerm(pLevel, pOther);
2241 }
drh0fcef5e2005-07-19 17:38:22 +00002242 }
drh2ffb1182004-07-19 19:14:01 +00002243 }
2244}
2245
2246/*
danielk1977b790c6c2008-04-18 10:25:24 +00002247** Apply the affinities associated with the first n columns of index
2248** pIdx to the values in the n registers starting at base.
drh94a11212004-09-25 13:12:14 +00002249*/
danielk1977b790c6c2008-04-18 10:25:24 +00002250static void codeApplyAffinity(Parse *pParse, int base, int n, Index *pIdx){
2251 if( n>0 ){
2252 Vdbe *v = pParse->pVdbe;
2253 assert( v!=0 );
2254 sqlite3VdbeAddOp2(v, OP_Affinity, base, n);
2255 sqlite3IndexAffinityStr(v, pIdx);
2256 sqlite3ExprCacheAffinityChange(pParse, base, n);
2257 }
drh94a11212004-09-25 13:12:14 +00002258}
2259
drhe8b97272005-07-19 22:22:12 +00002260
2261/*
drh51147ba2005-07-23 22:59:55 +00002262** Generate code for a single equality term of the WHERE clause. An equality
2263** term can be either X=expr or X IN (...). pTerm is the term to be
2264** coded.
2265**
drh1db639c2008-01-17 02:36:28 +00002266** The current value for the constraint is left in register iReg.
drh51147ba2005-07-23 22:59:55 +00002267**
2268** For a constraint of the form X=expr, the expression is evaluated and its
2269** result is left on the stack. For constraints of the form X IN (...)
2270** this routine sets up a loop that will iterate over all values of X.
drh94a11212004-09-25 13:12:14 +00002271*/
drh678ccce2008-03-31 18:19:54 +00002272static int codeEqualityTerm(
drh94a11212004-09-25 13:12:14 +00002273 Parse *pParse, /* The parsing context */
drhe23399f2005-07-22 00:31:39 +00002274 WhereTerm *pTerm, /* The term of the WHERE clause to be coded */
drh1db639c2008-01-17 02:36:28 +00002275 WhereLevel *pLevel, /* When level of the FROM clause we are working on */
drh678ccce2008-03-31 18:19:54 +00002276 int iTarget /* Attempt to leave results in this register */
drh94a11212004-09-25 13:12:14 +00002277){
drh0fcef5e2005-07-19 17:38:22 +00002278 Expr *pX = pTerm->pExpr;
drh50b39962006-10-28 00:28:09 +00002279 Vdbe *v = pParse->pVdbe;
drh678ccce2008-03-31 18:19:54 +00002280 int iReg; /* Register holding results */
drh1db639c2008-01-17 02:36:28 +00002281
danielk19772d605492008-10-01 08:43:03 +00002282 assert( iTarget>0 );
drh50b39962006-10-28 00:28:09 +00002283 if( pX->op==TK_EQ ){
drh678ccce2008-03-31 18:19:54 +00002284 iReg = sqlite3ExprCodeTarget(pParse, pX->pRight, iTarget);
drh50b39962006-10-28 00:28:09 +00002285 }else if( pX->op==TK_ISNULL ){
drh678ccce2008-03-31 18:19:54 +00002286 iReg = iTarget;
drh1db639c2008-01-17 02:36:28 +00002287 sqlite3VdbeAddOp2(v, OP_Null, 0, iReg);
danielk1977b3bce662005-01-29 08:32:43 +00002288#ifndef SQLITE_OMIT_SUBQUERY
drh94a11212004-09-25 13:12:14 +00002289 }else{
danielk19779a96b662007-11-29 17:05:18 +00002290 int eType;
danielk1977b3bce662005-01-29 08:32:43 +00002291 int iTab;
drh72e8fa42007-03-28 14:30:06 +00002292 struct InLoop *pIn;
danielk1977b3bce662005-01-29 08:32:43 +00002293
drh50b39962006-10-28 00:28:09 +00002294 assert( pX->op==TK_IN );
drh678ccce2008-03-31 18:19:54 +00002295 iReg = iTarget;
danielk19770cdc0222008-06-26 18:04:03 +00002296 eType = sqlite3FindInIndex(pParse, pX, 0);
danielk1977b3bce662005-01-29 08:32:43 +00002297 iTab = pX->iTable;
drh66a51672008-01-03 00:01:23 +00002298 sqlite3VdbeAddOp2(v, OP_Rewind, iTab, 0);
drhd4e70eb2008-01-02 00:34:36 +00002299 VdbeComment((v, "%.*s", pX->span.n, pX->span.z));
drh111a6a72008-12-21 03:51:16 +00002300 assert( pLevel->plan.wsFlags & WHERE_IN_ABLE );
2301 if( pLevel->u.in.nIn==0 ){
drhb3190c12008-12-08 21:37:14 +00002302 pLevel->addrNxt = sqlite3VdbeMakeLabel(v);
drh72e8fa42007-03-28 14:30:06 +00002303 }
drh111a6a72008-12-21 03:51:16 +00002304 pLevel->u.in.nIn++;
2305 pLevel->u.in.aInLoop =
2306 sqlite3DbReallocOrFree(pParse->db, pLevel->u.in.aInLoop,
2307 sizeof(pLevel->u.in.aInLoop[0])*pLevel->u.in.nIn);
2308 pIn = pLevel->u.in.aInLoop;
drh72e8fa42007-03-28 14:30:06 +00002309 if( pIn ){
drh111a6a72008-12-21 03:51:16 +00002310 pIn += pLevel->u.in.nIn - 1;
drh72e8fa42007-03-28 14:30:06 +00002311 pIn->iCur = iTab;
drh1db639c2008-01-17 02:36:28 +00002312 if( eType==IN_INDEX_ROWID ){
drhb3190c12008-12-08 21:37:14 +00002313 pIn->addrInTop = sqlite3VdbeAddOp2(v, OP_Rowid, iTab, iReg);
drh1db639c2008-01-17 02:36:28 +00002314 }else{
drhb3190c12008-12-08 21:37:14 +00002315 pIn->addrInTop = sqlite3VdbeAddOp3(v, OP_Column, iTab, 0, iReg);
drh1db639c2008-01-17 02:36:28 +00002316 }
2317 sqlite3VdbeAddOp1(v, OP_IsNull, iReg);
drha6110402005-07-28 20:51:19 +00002318 }else{
drh111a6a72008-12-21 03:51:16 +00002319 pLevel->u.in.nIn = 0;
drhe23399f2005-07-22 00:31:39 +00002320 }
danielk1977b3bce662005-01-29 08:32:43 +00002321#endif
drh94a11212004-09-25 13:12:14 +00002322 }
drh0fcef5e2005-07-19 17:38:22 +00002323 disableTerm(pLevel, pTerm);
drh678ccce2008-03-31 18:19:54 +00002324 return iReg;
drh94a11212004-09-25 13:12:14 +00002325}
2326
drh51147ba2005-07-23 22:59:55 +00002327/*
2328** Generate code that will evaluate all == and IN constraints for an
2329** index. The values for all constraints are left on the stack.
2330**
2331** For example, consider table t1(a,b,c,d,e,f) with index i1(a,b,c).
2332** Suppose the WHERE clause is this: a==5 AND b IN (1,2,3) AND c>5 AND c<10
2333** The index has as many as three equality constraints, but in this
2334** example, the third "c" value is an inequality. So only two
2335** constraints are coded. This routine will generate code to evaluate
drh6df2acd2008-12-28 16:55:25 +00002336** a==5 and b IN (1,2,3). The current values for a and b will be stored
2337** in consecutive registers and the index of the first register is returned.
drh51147ba2005-07-23 22:59:55 +00002338**
2339** In the example above nEq==2. But this subroutine works for any value
2340** of nEq including 0. If nEq==0, this routine is nearly a no-op.
2341** The only thing it does is allocate the pLevel->iMem memory cell.
2342**
drh700a2262008-12-17 19:22:15 +00002343** This routine always allocates at least one memory cell and returns
2344** the index of that memory cell. The code that
2345** calls this routine will use that memory cell to store the termination
drh51147ba2005-07-23 22:59:55 +00002346** key value of the loop. If one or more IN operators appear, then
2347** this routine allocates an additional nEq memory cells for internal
2348** use.
2349*/
drh1db639c2008-01-17 02:36:28 +00002350static int codeAllEqualityTerms(
drh51147ba2005-07-23 22:59:55 +00002351 Parse *pParse, /* Parsing context */
2352 WhereLevel *pLevel, /* Which nested loop of the FROM we are coding */
2353 WhereClause *pWC, /* The WHERE clause */
drh1db639c2008-01-17 02:36:28 +00002354 Bitmask notReady, /* Which parts of FROM have not yet been coded */
2355 int nExtraReg /* Number of extra registers to allocate */
drh51147ba2005-07-23 22:59:55 +00002356){
drh111a6a72008-12-21 03:51:16 +00002357 int nEq = pLevel->plan.nEq; /* The number of == or IN constraints to code */
2358 Vdbe *v = pParse->pVdbe; /* The vm under construction */
2359 Index *pIdx; /* The index being used for this loop */
drh51147ba2005-07-23 22:59:55 +00002360 int iCur = pLevel->iTabCur; /* The cursor of the table */
2361 WhereTerm *pTerm; /* A single constraint term */
2362 int j; /* Loop counter */
drh1db639c2008-01-17 02:36:28 +00002363 int regBase; /* Base register */
drh6df2acd2008-12-28 16:55:25 +00002364 int nReg; /* Number of registers to allocate */
drh51147ba2005-07-23 22:59:55 +00002365
drh111a6a72008-12-21 03:51:16 +00002366 /* This module is only called on query plans that use an index. */
2367 assert( pLevel->plan.wsFlags & WHERE_INDEXED );
2368 pIdx = pLevel->plan.u.pIdx;
2369
drh51147ba2005-07-23 22:59:55 +00002370 /* Figure out how many memory cells we will need then allocate them.
drh51147ba2005-07-23 22:59:55 +00002371 */
drh700a2262008-12-17 19:22:15 +00002372 regBase = pParse->nMem + 1;
drh6df2acd2008-12-28 16:55:25 +00002373 nReg = pLevel->plan.nEq + nExtraReg;
2374 pParse->nMem += nReg;
drh51147ba2005-07-23 22:59:55 +00002375
2376 /* Evaluate the equality constraints
2377 */
drhc49de5d2007-01-19 01:06:01 +00002378 assert( pIdx->nColumn>=nEq );
2379 for(j=0; j<nEq; j++){
drh678ccce2008-03-31 18:19:54 +00002380 int r1;
drh51147ba2005-07-23 22:59:55 +00002381 int k = pIdx->aiColumn[j];
drh111a6a72008-12-21 03:51:16 +00002382 pTerm = findTerm(pWC, iCur, k, notReady, pLevel->plan.wsFlags, pIdx);
drh34004ce2008-07-11 16:15:17 +00002383 if( NEVER(pTerm==0) ) break;
drh165be382008-12-05 02:36:33 +00002384 assert( (pTerm->wtFlags & TERM_CODED)==0 );
drh678ccce2008-03-31 18:19:54 +00002385 r1 = codeEqualityTerm(pParse, pTerm, pLevel, regBase+j);
2386 if( r1!=regBase+j ){
drh6df2acd2008-12-28 16:55:25 +00002387 if( nReg==1 ){
2388 sqlite3ReleaseTempReg(pParse, regBase);
2389 regBase = r1;
2390 }else{
2391 sqlite3VdbeAddOp2(v, OP_SCopy, r1, regBase+j);
2392 }
drh678ccce2008-03-31 18:19:54 +00002393 }
drh981642f2008-04-19 14:40:43 +00002394 testcase( pTerm->eOperator & WO_ISNULL );
2395 testcase( pTerm->eOperator & WO_IN );
drh72e8fa42007-03-28 14:30:06 +00002396 if( (pTerm->eOperator & (WO_ISNULL|WO_IN))==0 ){
drhb3190c12008-12-08 21:37:14 +00002397 sqlite3VdbeAddOp2(v, OP_IsNull, regBase+j, pLevel->addrBrk);
drh51147ba2005-07-23 22:59:55 +00002398 }
2399 }
drh1db639c2008-01-17 02:36:28 +00002400 return regBase;
drh51147ba2005-07-23 22:59:55 +00002401}
2402
drh111a6a72008-12-21 03:51:16 +00002403/*
2404** Generate code for the start of the iLevel-th loop in the WHERE clause
2405** implementation described by pWInfo.
2406*/
2407static Bitmask codeOneLoopStart(
2408 WhereInfo *pWInfo, /* Complete information about the WHERE clause */
2409 int iLevel, /* Which level of pWInfo->a[] should be coded */
drh336a5302009-04-24 15:46:21 +00002410 u16 wctrlFlags, /* One of the WHERE_* flags defined in sqliteInt.h */
drh111a6a72008-12-21 03:51:16 +00002411 Bitmask notReady /* Which tables are currently available */
2412){
2413 int j, k; /* Loop counters */
2414 int iCur; /* The VDBE cursor for the table */
2415 int addrNxt; /* Where to jump to continue with the next IN case */
2416 int omitTable; /* True if we use the index only */
2417 int bRev; /* True if we need to scan in reverse order */
2418 WhereLevel *pLevel; /* The where level to be coded */
2419 WhereClause *pWC; /* Decomposition of the entire WHERE clause */
2420 WhereTerm *pTerm; /* A WHERE clause term */
2421 Parse *pParse; /* Parsing context */
2422 Vdbe *v; /* The prepared stmt under constructions */
2423 struct SrcList_item *pTabItem; /* FROM clause term being coded */
drh23d04d52008-12-23 23:56:22 +00002424 int addrBrk; /* Jump here to break out of the loop */
2425 int addrCont; /* Jump here to continue with next cycle */
drh61495262009-04-22 15:32:59 +00002426 int iRowidReg = 0; /* Rowid is stored in this register, if not zero */
2427 int iReleaseReg = 0; /* Temp register to free before returning */
drh111a6a72008-12-21 03:51:16 +00002428
2429 pParse = pWInfo->pParse;
2430 v = pParse->pVdbe;
2431 pWC = pWInfo->pWC;
2432 pLevel = &pWInfo->a[iLevel];
2433 pTabItem = &pWInfo->pTabList->a[pLevel->iFrom];
2434 iCur = pTabItem->iCursor;
2435 bRev = (pLevel->plan.wsFlags & WHERE_REVERSE)!=0;
danielk19771d461462009-04-21 09:02:45 +00002436 omitTable = (pLevel->plan.wsFlags & WHERE_IDX_ONLY)!=0
drh336a5302009-04-24 15:46:21 +00002437 && (wctrlFlags & WHERE_FORCE_TABLE)==0;
drh111a6a72008-12-21 03:51:16 +00002438
2439 /* Create labels for the "break" and "continue" instructions
2440 ** for the current loop. Jump to addrBrk to break out of a loop.
2441 ** Jump to cont to go immediately to the next iteration of the
2442 ** loop.
2443 **
2444 ** When there is an IN operator, we also have a "addrNxt" label that
2445 ** means to continue with the next IN value combination. When
2446 ** there are no IN operators in the constraints, the "addrNxt" label
2447 ** is the same as "addrBrk".
2448 */
2449 addrBrk = pLevel->addrBrk = pLevel->addrNxt = sqlite3VdbeMakeLabel(v);
2450 addrCont = pLevel->addrCont = sqlite3VdbeMakeLabel(v);
2451
2452 /* If this is the right table of a LEFT OUTER JOIN, allocate and
2453 ** initialize a memory cell that records if this table matches any
2454 ** row of the left table of the join.
2455 */
2456 if( pLevel->iFrom>0 && (pTabItem[0].jointype & JT_LEFT)!=0 ){
2457 pLevel->iLeftJoin = ++pParse->nMem;
2458 sqlite3VdbeAddOp2(v, OP_Integer, 0, pLevel->iLeftJoin);
2459 VdbeComment((v, "init LEFT JOIN no-match flag"));
2460 }
2461
2462#ifndef SQLITE_OMIT_VIRTUALTABLE
2463 if( (pLevel->plan.wsFlags & WHERE_VIRTUALTABLE)!=0 ){
2464 /* Case 0: The table is a virtual-table. Use the VFilter and VNext
2465 ** to access the data.
2466 */
2467 int iReg; /* P3 Value for OP_VFilter */
2468 sqlite3_index_info *pVtabIdx = pLevel->plan.u.pVtabIdx;
2469 int nConstraint = pVtabIdx->nConstraint;
2470 struct sqlite3_index_constraint_usage *aUsage =
2471 pVtabIdx->aConstraintUsage;
2472 const struct sqlite3_index_constraint *aConstraint =
2473 pVtabIdx->aConstraint;
2474
2475 iReg = sqlite3GetTempRange(pParse, nConstraint+2);
drh111a6a72008-12-21 03:51:16 +00002476 for(j=1; j<=nConstraint; j++){
2477 for(k=0; k<nConstraint; k++){
2478 if( aUsage[k].argvIndex==j ){
2479 int iTerm = aConstraint[k].iTermOffset;
drh111a6a72008-12-21 03:51:16 +00002480 sqlite3ExprCode(pParse, pWC->a[iTerm].pExpr->pRight, iReg+j+1);
2481 break;
2482 }
2483 }
2484 if( k==nConstraint ) break;
2485 }
drh111a6a72008-12-21 03:51:16 +00002486 sqlite3VdbeAddOp2(v, OP_Integer, pVtabIdx->idxNum, iReg);
2487 sqlite3VdbeAddOp2(v, OP_Integer, j-1, iReg+1);
2488 sqlite3VdbeAddOp4(v, OP_VFilter, iCur, addrBrk, iReg, pVtabIdx->idxStr,
2489 pVtabIdx->needToFreeIdxStr ? P4_MPRINTF : P4_STATIC);
drh111a6a72008-12-21 03:51:16 +00002490 pVtabIdx->needToFreeIdxStr = 0;
2491 for(j=0; j<nConstraint; j++){
2492 if( aUsage[j].omit ){
2493 int iTerm = aConstraint[j].iTermOffset;
2494 disableTerm(pLevel, &pWC->a[iTerm]);
2495 }
2496 }
2497 pLevel->op = OP_VNext;
2498 pLevel->p1 = iCur;
2499 pLevel->p2 = sqlite3VdbeCurrentAddr(v);
drh23d04d52008-12-23 23:56:22 +00002500 sqlite3ReleaseTempRange(pParse, iReg, nConstraint+2);
drh111a6a72008-12-21 03:51:16 +00002501 }else
2502#endif /* SQLITE_OMIT_VIRTUALTABLE */
2503
2504 if( pLevel->plan.wsFlags & WHERE_ROWID_EQ ){
2505 /* Case 1: We can directly reference a single row using an
2506 ** equality comparison against the ROWID field. Or
2507 ** we reference multiple rows using a "rowid IN (...)"
2508 ** construct.
2509 */
danielk19771d461462009-04-21 09:02:45 +00002510 iReleaseReg = sqlite3GetTempReg(pParse);
drh111a6a72008-12-21 03:51:16 +00002511 pTerm = findTerm(pWC, iCur, -1, notReady, WO_EQ|WO_IN, 0);
2512 assert( pTerm!=0 );
2513 assert( pTerm->pExpr!=0 );
2514 assert( pTerm->leftCursor==iCur );
2515 assert( omitTable==0 );
danielk19771d461462009-04-21 09:02:45 +00002516 iRowidReg = codeEqualityTerm(pParse, pTerm, pLevel, iReleaseReg);
drh111a6a72008-12-21 03:51:16 +00002517 addrNxt = pLevel->addrNxt;
danielk19771d461462009-04-21 09:02:45 +00002518 sqlite3VdbeAddOp2(v, OP_MustBeInt, iRowidReg, addrNxt);
2519 sqlite3VdbeAddOp3(v, OP_NotExists, iCur, addrNxt, iRowidReg);
drhceea3322009-04-23 13:22:42 +00002520 sqlite3ExprCacheStore(pParse, iCur, -1, iRowidReg);
drh111a6a72008-12-21 03:51:16 +00002521 VdbeComment((v, "pk"));
2522 pLevel->op = OP_Noop;
2523 }else if( pLevel->plan.wsFlags & WHERE_ROWID_RANGE ){
2524 /* Case 2: We have an inequality comparison against the ROWID field.
2525 */
2526 int testOp = OP_Noop;
2527 int start;
2528 int memEndValue = 0;
2529 WhereTerm *pStart, *pEnd;
2530
2531 assert( omitTable==0 );
2532 pStart = findTerm(pWC, iCur, -1, notReady, WO_GT|WO_GE, 0);
2533 pEnd = findTerm(pWC, iCur, -1, notReady, WO_LT|WO_LE, 0);
2534 if( bRev ){
2535 pTerm = pStart;
2536 pStart = pEnd;
2537 pEnd = pTerm;
2538 }
2539 if( pStart ){
2540 Expr *pX; /* The expression that defines the start bound */
2541 int r1, rTemp; /* Registers for holding the start boundary */
2542
2543 /* The following constant maps TK_xx codes into corresponding
2544 ** seek opcodes. It depends on a particular ordering of TK_xx
2545 */
2546 const u8 aMoveOp[] = {
2547 /* TK_GT */ OP_SeekGt,
2548 /* TK_LE */ OP_SeekLe,
2549 /* TK_LT */ OP_SeekLt,
2550 /* TK_GE */ OP_SeekGe
2551 };
2552 assert( TK_LE==TK_GT+1 ); /* Make sure the ordering.. */
2553 assert( TK_LT==TK_GT+2 ); /* ... of the TK_xx values... */
2554 assert( TK_GE==TK_GT+3 ); /* ... is correcct. */
2555
2556 pX = pStart->pExpr;
2557 assert( pX!=0 );
2558 assert( pStart->leftCursor==iCur );
2559 r1 = sqlite3ExprCodeTemp(pParse, pX->pRight, &rTemp);
2560 sqlite3VdbeAddOp3(v, aMoveOp[pX->op-TK_GT], iCur, addrBrk, r1);
2561 VdbeComment((v, "pk"));
2562 sqlite3ExprCacheAffinityChange(pParse, r1, 1);
2563 sqlite3ReleaseTempReg(pParse, rTemp);
2564 disableTerm(pLevel, pStart);
2565 }else{
2566 sqlite3VdbeAddOp2(v, bRev ? OP_Last : OP_Rewind, iCur, addrBrk);
2567 }
2568 if( pEnd ){
2569 Expr *pX;
2570 pX = pEnd->pExpr;
2571 assert( pX!=0 );
2572 assert( pEnd->leftCursor==iCur );
2573 memEndValue = ++pParse->nMem;
2574 sqlite3ExprCode(pParse, pX->pRight, memEndValue);
2575 if( pX->op==TK_LT || pX->op==TK_GT ){
2576 testOp = bRev ? OP_Le : OP_Ge;
2577 }else{
2578 testOp = bRev ? OP_Lt : OP_Gt;
2579 }
2580 disableTerm(pLevel, pEnd);
2581 }
2582 start = sqlite3VdbeCurrentAddr(v);
2583 pLevel->op = bRev ? OP_Prev : OP_Next;
2584 pLevel->p1 = iCur;
2585 pLevel->p2 = start;
drhca8c4662008-12-28 20:47:02 +00002586 pLevel->p5 = (pStart==0 && pEnd==0) ?1:0;
danielk19771d461462009-04-21 09:02:45 +00002587 if( testOp!=OP_Noop ){
2588 iRowidReg = iReleaseReg = sqlite3GetTempReg(pParse);
2589 sqlite3VdbeAddOp2(v, OP_Rowid, iCur, iRowidReg);
drhceea3322009-04-23 13:22:42 +00002590 sqlite3ExprCacheStore(pParse, iCur, -1, iRowidReg);
danielk19771d461462009-04-21 09:02:45 +00002591 sqlite3VdbeAddOp3(v, testOp, memEndValue, addrBrk, iRowidReg);
2592 sqlite3VdbeChangeP5(v, SQLITE_AFF_NUMERIC | SQLITE_JUMPIFNULL);
drh111a6a72008-12-21 03:51:16 +00002593 }
2594 }else if( pLevel->plan.wsFlags & (WHERE_COLUMN_RANGE|WHERE_COLUMN_EQ) ){
2595 /* Case 3: A scan using an index.
2596 **
2597 ** The WHERE clause may contain zero or more equality
2598 ** terms ("==" or "IN" operators) that refer to the N
2599 ** left-most columns of the index. It may also contain
2600 ** inequality constraints (>, <, >= or <=) on the indexed
2601 ** column that immediately follows the N equalities. Only
2602 ** the right-most column can be an inequality - the rest must
2603 ** use the "==" and "IN" operators. For example, if the
2604 ** index is on (x,y,z), then the following clauses are all
2605 ** optimized:
2606 **
2607 ** x=5
2608 ** x=5 AND y=10
2609 ** x=5 AND y<10
2610 ** x=5 AND y>5 AND y<10
2611 ** x=5 AND y=5 AND z<=10
2612 **
2613 ** The z<10 term of the following cannot be used, only
2614 ** the x=5 term:
2615 **
2616 ** x=5 AND z<10
2617 **
2618 ** N may be zero if there are inequality constraints.
2619 ** If there are no inequality constraints, then N is at
2620 ** least one.
2621 **
2622 ** This case is also used when there are no WHERE clause
2623 ** constraints but an index is selected anyway, in order
2624 ** to force the output order to conform to an ORDER BY.
2625 */
2626 int aStartOp[] = {
2627 0,
2628 0,
2629 OP_Rewind, /* 2: (!start_constraints && startEq && !bRev) */
2630 OP_Last, /* 3: (!start_constraints && startEq && bRev) */
2631 OP_SeekGt, /* 4: (start_constraints && !startEq && !bRev) */
2632 OP_SeekLt, /* 5: (start_constraints && !startEq && bRev) */
2633 OP_SeekGe, /* 6: (start_constraints && startEq && !bRev) */
2634 OP_SeekLe /* 7: (start_constraints && startEq && bRev) */
2635 };
2636 int aEndOp[] = {
2637 OP_Noop, /* 0: (!end_constraints) */
2638 OP_IdxGE, /* 1: (end_constraints && !bRev) */
2639 OP_IdxLT /* 2: (end_constraints && bRev) */
2640 };
2641 int nEq = pLevel->plan.nEq;
2642 int isMinQuery = 0; /* If this is an optimized SELECT min(x).. */
2643 int regBase; /* Base register holding constraint values */
2644 int r1; /* Temp register */
2645 WhereTerm *pRangeStart = 0; /* Inequality constraint at range start */
2646 WhereTerm *pRangeEnd = 0; /* Inequality constraint at range end */
2647 int startEq; /* True if range start uses ==, >= or <= */
2648 int endEq; /* True if range end uses ==, >= or <= */
2649 int start_constraints; /* Start of range is constrained */
2650 int nConstraint; /* Number of constraint terms */
2651 Index *pIdx; /* The index we will be using */
2652 int iIdxCur; /* The VDBE cursor for the index */
drh6df2acd2008-12-28 16:55:25 +00002653 int nExtraReg = 0; /* Number of extra registers needed */
2654 int op; /* Instruction opcode */
drh111a6a72008-12-21 03:51:16 +00002655
2656 pIdx = pLevel->plan.u.pIdx;
2657 iIdxCur = pLevel->iIdxCur;
2658 k = pIdx->aiColumn[nEq]; /* Column for inequality constraints */
2659
drh111a6a72008-12-21 03:51:16 +00002660 /* If this loop satisfies a sort order (pOrderBy) request that
2661 ** was passed to this function to implement a "SELECT min(x) ..."
2662 ** query, then the caller will only allow the loop to run for
2663 ** a single iteration. This means that the first row returned
2664 ** should not have a NULL value stored in 'x'. If column 'x' is
2665 ** the first one after the nEq equality constraints in the index,
2666 ** this requires some special handling.
2667 */
2668 if( (wctrlFlags&WHERE_ORDERBY_MIN)!=0
2669 && (pLevel->plan.wsFlags&WHERE_ORDERBY)
2670 && (pIdx->nColumn>nEq)
2671 ){
2672 /* assert( pOrderBy->nExpr==1 ); */
2673 /* assert( pOrderBy->a[0].pExpr->iColumn==pIdx->aiColumn[nEq] ); */
2674 isMinQuery = 1;
drh6df2acd2008-12-28 16:55:25 +00002675 nExtraReg = 1;
drh111a6a72008-12-21 03:51:16 +00002676 }
2677
2678 /* Find any inequality constraint terms for the start and end
2679 ** of the range.
2680 */
2681 if( pLevel->plan.wsFlags & WHERE_TOP_LIMIT ){
2682 pRangeEnd = findTerm(pWC, iCur, k, notReady, (WO_LT|WO_LE), pIdx);
drh6df2acd2008-12-28 16:55:25 +00002683 nExtraReg = 1;
drh111a6a72008-12-21 03:51:16 +00002684 }
2685 if( pLevel->plan.wsFlags & WHERE_BTM_LIMIT ){
2686 pRangeStart = findTerm(pWC, iCur, k, notReady, (WO_GT|WO_GE), pIdx);
drh6df2acd2008-12-28 16:55:25 +00002687 nExtraReg = 1;
drh111a6a72008-12-21 03:51:16 +00002688 }
2689
drh6df2acd2008-12-28 16:55:25 +00002690 /* Generate code to evaluate all constraint terms using == or IN
2691 ** and store the values of those terms in an array of registers
2692 ** starting at regBase.
2693 */
2694 regBase = codeAllEqualityTerms(pParse, pLevel, pWC, notReady, nExtraReg);
2695 addrNxt = pLevel->addrNxt;
2696
2697
drh111a6a72008-12-21 03:51:16 +00002698 /* If we are doing a reverse order scan on an ascending index, or
2699 ** a forward order scan on a descending index, interchange the
2700 ** start and end terms (pRangeStart and pRangeEnd).
2701 */
2702 if( bRev==(pIdx->aSortOrder[nEq]==SQLITE_SO_ASC) ){
2703 SWAP(WhereTerm *, pRangeEnd, pRangeStart);
2704 }
2705
2706 testcase( pRangeStart && pRangeStart->eOperator & WO_LE );
2707 testcase( pRangeStart && pRangeStart->eOperator & WO_GE );
2708 testcase( pRangeEnd && pRangeEnd->eOperator & WO_LE );
2709 testcase( pRangeEnd && pRangeEnd->eOperator & WO_GE );
2710 startEq = !pRangeStart || pRangeStart->eOperator & (WO_LE|WO_GE);
2711 endEq = !pRangeEnd || pRangeEnd->eOperator & (WO_LE|WO_GE);
2712 start_constraints = pRangeStart || nEq>0;
2713
2714 /* Seek the index cursor to the start of the range. */
2715 nConstraint = nEq;
2716 if( pRangeStart ){
drh111a6a72008-12-21 03:51:16 +00002717 sqlite3ExprCode(pParse, pRangeStart->pExpr->pRight, regBase+nEq);
drh111a6a72008-12-21 03:51:16 +00002718 sqlite3VdbeAddOp2(v, OP_IsNull, regBase+nEq, addrNxt);
2719 nConstraint++;
2720 }else if( isMinQuery ){
2721 sqlite3VdbeAddOp2(v, OP_Null, 0, regBase+nEq);
2722 nConstraint++;
2723 startEq = 0;
2724 start_constraints = 1;
2725 }
2726 codeApplyAffinity(pParse, regBase, nConstraint, pIdx);
2727 op = aStartOp[(start_constraints<<2) + (startEq<<1) + bRev];
2728 assert( op!=0 );
2729 testcase( op==OP_Rewind );
2730 testcase( op==OP_Last );
2731 testcase( op==OP_SeekGt );
2732 testcase( op==OP_SeekGe );
2733 testcase( op==OP_SeekLe );
2734 testcase( op==OP_SeekLt );
2735 sqlite3VdbeAddOp4(v, op, iIdxCur, addrNxt, regBase,
2736 SQLITE_INT_TO_PTR(nConstraint), P4_INT32);
2737
2738 /* Load the value for the inequality constraint at the end of the
2739 ** range (if any).
2740 */
2741 nConstraint = nEq;
2742 if( pRangeEnd ){
drhceea3322009-04-23 13:22:42 +00002743 sqlite3ExprCacheRemove(pParse, regBase+nEq);
drh111a6a72008-12-21 03:51:16 +00002744 sqlite3ExprCode(pParse, pRangeEnd->pExpr->pRight, regBase+nEq);
2745 sqlite3VdbeAddOp2(v, OP_IsNull, regBase+nEq, addrNxt);
2746 codeApplyAffinity(pParse, regBase, nEq+1, pIdx);
2747 nConstraint++;
2748 }
2749
2750 /* Top of the loop body */
2751 pLevel->p2 = sqlite3VdbeCurrentAddr(v);
2752
2753 /* Check if the index cursor is past the end of the range. */
2754 op = aEndOp[(pRangeEnd || nEq) * (1 + bRev)];
2755 testcase( op==OP_Noop );
2756 testcase( op==OP_IdxGE );
2757 testcase( op==OP_IdxLT );
drh6df2acd2008-12-28 16:55:25 +00002758 if( op!=OP_Noop ){
2759 sqlite3VdbeAddOp4(v, op, iIdxCur, addrNxt, regBase,
2760 SQLITE_INT_TO_PTR(nConstraint), P4_INT32);
2761 sqlite3VdbeChangeP5(v, endEq!=bRev ?1:0);
2762 }
drh111a6a72008-12-21 03:51:16 +00002763
2764 /* If there are inequality constraints, check that the value
2765 ** of the table column that the inequality contrains is not NULL.
2766 ** If it is, jump to the next iteration of the loop.
2767 */
2768 r1 = sqlite3GetTempReg(pParse);
2769 testcase( pLevel->plan.wsFlags & WHERE_BTM_LIMIT );
2770 testcase( pLevel->plan.wsFlags & WHERE_TOP_LIMIT );
2771 if( pLevel->plan.wsFlags & (WHERE_BTM_LIMIT|WHERE_TOP_LIMIT) ){
2772 sqlite3VdbeAddOp3(v, OP_Column, iIdxCur, nEq, r1);
2773 sqlite3VdbeAddOp2(v, OP_IsNull, r1, addrCont);
2774 }
danielk19771d461462009-04-21 09:02:45 +00002775 sqlite3ReleaseTempReg(pParse, r1);
drh111a6a72008-12-21 03:51:16 +00002776
2777 /* Seek the table cursor, if required */
drh23d04d52008-12-23 23:56:22 +00002778 disableTerm(pLevel, pRangeStart);
2779 disableTerm(pLevel, pRangeEnd);
danielk19771d461462009-04-21 09:02:45 +00002780 if( !omitTable ){
2781 iRowidReg = iReleaseReg = sqlite3GetTempReg(pParse);
2782 sqlite3VdbeAddOp2(v, OP_IdxRowid, iIdxCur, iRowidReg);
drhceea3322009-04-23 13:22:42 +00002783 sqlite3ExprCacheStore(pParse, iCur, -1, iRowidReg);
danielk19771d461462009-04-21 09:02:45 +00002784 sqlite3VdbeAddOp2(v, OP_Seek, iCur, iRowidReg); /* Deferred seek */
drh111a6a72008-12-21 03:51:16 +00002785 }
drh111a6a72008-12-21 03:51:16 +00002786
2787 /* Record the instruction used to terminate the loop. Disable
2788 ** WHERE clause terms made redundant by the index range scan.
2789 */
2790 pLevel->op = bRev ? OP_Prev : OP_Next;
2791 pLevel->p1 = iIdxCur;
drhdd5f5a62008-12-23 13:35:23 +00002792 }else
2793
drh23d04d52008-12-23 23:56:22 +00002794#ifndef SQLITE_OMIT_OR_OPTIMIZATION
drhdd5f5a62008-12-23 13:35:23 +00002795 if( pLevel->plan.wsFlags & WHERE_MULTI_OR ){
drh111a6a72008-12-21 03:51:16 +00002796 /* Case 4: Two or more separately indexed terms connected by OR
2797 **
2798 ** Example:
2799 **
2800 ** CREATE TABLE t1(a,b,c,d);
2801 ** CREATE INDEX i1 ON t1(a);
2802 ** CREATE INDEX i2 ON t1(b);
2803 ** CREATE INDEX i3 ON t1(c);
2804 **
2805 ** SELECT * FROM t1 WHERE a=5 OR b=7 OR (c=11 AND d=13)
2806 **
2807 ** In the example, there are three indexed terms connected by OR.
danielk19771d461462009-04-21 09:02:45 +00002808 ** The top of the loop looks like this:
drh111a6a72008-12-21 03:51:16 +00002809 **
drh1b26c7c2009-04-22 02:15:47 +00002810 ** Null 1 # Zero the rowset in reg 1
drh111a6a72008-12-21 03:51:16 +00002811 **
danielk19771d461462009-04-21 09:02:45 +00002812 ** Then, for each indexed term, the following. The arguments to
drh1b26c7c2009-04-22 02:15:47 +00002813 ** RowSetTest are such that the rowid of the current row is inserted
2814 ** into the RowSet. If it is already present, control skips the
danielk19771d461462009-04-21 09:02:45 +00002815 ** Gosub opcode and jumps straight to the code generated by WhereEnd().
drh111a6a72008-12-21 03:51:16 +00002816 **
danielk19771d461462009-04-21 09:02:45 +00002817 ** sqlite3WhereBegin(<term>)
drh1b26c7c2009-04-22 02:15:47 +00002818 ** RowSetTest # Insert rowid into rowset
danielk19771d461462009-04-21 09:02:45 +00002819 ** Gosub 2 A
2820 ** sqlite3WhereEnd()
2821 **
2822 ** Following the above, code to terminate the loop. Label A, the target
2823 ** of the Gosub above, jumps to the instruction right after the Goto.
2824 **
drh1b26c7c2009-04-22 02:15:47 +00002825 ** Null 1 # Zero the rowset in reg 1
danielk19771d461462009-04-21 09:02:45 +00002826 ** Goto B # The loop is finished.
2827 **
2828 ** A: <loop body> # Return data, whatever.
2829 **
2830 ** Return 2 # Jump back to the Gosub
2831 **
2832 ** B: <after the loop>
2833 **
drh111a6a72008-12-21 03:51:16 +00002834 */
drh111a6a72008-12-21 03:51:16 +00002835 WhereClause *pOrWc; /* The OR-clause broken out into subterms */
danielk19771d461462009-04-21 09:02:45 +00002836 WhereTerm *pFinal; /* Final subterm within the OR-clause. */
drhdd5f5a62008-12-23 13:35:23 +00002837 SrcList oneTab; /* Shortened table list */
danielk19771d461462009-04-21 09:02:45 +00002838
2839 int regReturn = ++pParse->nMem; /* Register used with OP_Gosub */
drh336a5302009-04-24 15:46:21 +00002840 int regRowset; /* Register for RowSet object */
2841 int regRowid; /* Register holding rowid */
danielk19771d461462009-04-21 09:02:45 +00002842 int iLoopBody = sqlite3VdbeMakeLabel(v); /* Start of loop body */
2843 int iRetInit; /* Address of regReturn init */
2844 int ii;
drh111a6a72008-12-21 03:51:16 +00002845
2846 pTerm = pLevel->plan.u.pTerm;
2847 assert( pTerm!=0 );
2848 assert( pTerm->eOperator==WO_OR );
2849 assert( (pTerm->wtFlags & TERM_ORINFO)!=0 );
2850 pOrWc = &pTerm->u.pOrInfo->wc;
danielk19771d461462009-04-21 09:02:45 +00002851 pFinal = &pOrWc->a[pOrWc->nTerm-1];
drh23d04d52008-12-23 23:56:22 +00002852
danielk19771d461462009-04-21 09:02:45 +00002853 /* Set up a SrcList containing just the table being scanned by this loop. */
drhdd5f5a62008-12-23 13:35:23 +00002854 oneTab.nSrc = 1;
2855 oneTab.nAlloc = 1;
2856 oneTab.a[0] = *pTabItem;
danielk19771d461462009-04-21 09:02:45 +00002857
drh1b26c7c2009-04-22 02:15:47 +00002858 /* Initialize the rowset register to contain NULL. An SQL NULL is
2859 ** equivalent to an empty rowset.
danielk19771d461462009-04-21 09:02:45 +00002860 **
2861 ** Also initialize regReturn to contain the address of the instruction
2862 ** immediately following the OP_Return at the bottom of the loop. This
2863 ** is required in a few obscure LEFT JOIN cases where control jumps
2864 ** over the top of the loop into the body of it. In this case the
2865 ** correct response for the end-of-loop code (the OP_Return) is to
2866 ** fall through to the next instruction, just as an OP_Next does if
2867 ** called on an uninitialized cursor.
2868 */
drh336a5302009-04-24 15:46:21 +00002869 if( (wctrlFlags & WHERE_DUPLICATES_OK)==0 ){
2870 regRowset = ++pParse->nMem;
2871 regRowid = ++pParse->nMem;
2872 sqlite3VdbeAddOp2(v, OP_Null, 0, regRowset);
2873 }
danielk19771d461462009-04-21 09:02:45 +00002874 iRetInit = sqlite3VdbeAddOp2(v, OP_Integer, 0, regReturn);
2875
danielk19771d461462009-04-21 09:02:45 +00002876 for(ii=0; ii<pOrWc->nTerm; ii++){
2877 WhereTerm *pOrTerm = &pOrWc->a[ii];
2878 if( pOrTerm->leftCursor==iCur || pOrTerm->eOperator==WO_AND ){
2879 WhereInfo *pSubWInfo; /* Info for single OR-term scan */
2880
2881 /* Loop through table entries that match term pOrTerm. */
drh336a5302009-04-24 15:46:21 +00002882 pSubWInfo = sqlite3WhereBegin(pParse, &oneTab, pOrTerm->pExpr, 0,
2883 WHERE_OMIT_OPEN | WHERE_OMIT_CLOSE | WHERE_FORCE_TABLE);
danielk19771d461462009-04-21 09:02:45 +00002884 if( pSubWInfo ){
drh336a5302009-04-24 15:46:21 +00002885 if( (wctrlFlags & WHERE_DUPLICATES_OK)==0 ){
2886 int iSet = ((ii==pOrWc->nTerm-1)?-1:ii);
2887 int r;
2888 r = sqlite3ExprCodeGetColumn(pParse, pTabItem->pTab, -1, iCur,
2889 regRowid, 0);
2890 sqlite3VdbeAddOp4(v, OP_RowSetTest, regRowset,
shane60a4b532009-05-06 18:57:09 +00002891 sqlite3VdbeCurrentAddr(v)+2,
2892 r, SQLITE_INT_TO_PTR(iSet), P4_INT32);
drh336a5302009-04-24 15:46:21 +00002893 }
danielk19771d461462009-04-21 09:02:45 +00002894 sqlite3VdbeAddOp2(v, OP_Gosub, regReturn, iLoopBody);
2895
2896 /* Finish the loop through table entries that match term pOrTerm. */
2897 sqlite3WhereEnd(pSubWInfo);
2898 }
drhdd5f5a62008-12-23 13:35:23 +00002899 }
2900 }
danielk19771d461462009-04-21 09:02:45 +00002901 sqlite3VdbeChangeP1(v, iRetInit, sqlite3VdbeCurrentAddr(v));
drh336a5302009-04-24 15:46:21 +00002902 /* sqlite3VdbeAddOp2(v, OP_Null, 0, regRowset); */
danielk19771d461462009-04-21 09:02:45 +00002903 sqlite3VdbeAddOp2(v, OP_Goto, 0, pLevel->addrBrk);
2904 sqlite3VdbeResolveLabel(v, iLoopBody);
2905
2906 pLevel->op = OP_Return;
2907 pLevel->p1 = regReturn;
drh23d04d52008-12-23 23:56:22 +00002908 disableTerm(pLevel, pTerm);
drhdd5f5a62008-12-23 13:35:23 +00002909 }else
drh23d04d52008-12-23 23:56:22 +00002910#endif /* SQLITE_OMIT_OR_OPTIMIZATION */
drhdd5f5a62008-12-23 13:35:23 +00002911
2912 {
drh111a6a72008-12-21 03:51:16 +00002913 /* Case 5: There is no usable index. We must do a complete
2914 ** scan of the entire table.
2915 */
drh699b3d42009-02-23 16:52:07 +00002916 static const u8 aStep[] = { OP_Next, OP_Prev };
2917 static const u8 aStart[] = { OP_Rewind, OP_Last };
2918 assert( bRev==0 || bRev==1 );
drh111a6a72008-12-21 03:51:16 +00002919 assert( omitTable==0 );
drh699b3d42009-02-23 16:52:07 +00002920 pLevel->op = aStep[bRev];
drh111a6a72008-12-21 03:51:16 +00002921 pLevel->p1 = iCur;
drh699b3d42009-02-23 16:52:07 +00002922 pLevel->p2 = 1 + sqlite3VdbeAddOp2(v, aStart[bRev], iCur, addrBrk);
drh111a6a72008-12-21 03:51:16 +00002923 pLevel->p5 = SQLITE_STMTSTATUS_FULLSCAN_STEP;
2924 }
2925 notReady &= ~getMask(pWC->pMaskSet, iCur);
2926
2927 /* Insert code to test every subexpression that can be completely
2928 ** computed using the current set of tables.
2929 */
2930 k = 0;
2931 for(pTerm=pWC->a, j=pWC->nTerm; j>0; j--, pTerm++){
2932 Expr *pE;
2933 testcase( pTerm->wtFlags & TERM_VIRTUAL );
2934 testcase( pTerm->wtFlags & TERM_CODED );
2935 if( pTerm->wtFlags & (TERM_VIRTUAL|TERM_CODED) ) continue;
2936 if( (pTerm->prereqAll & notReady)!=0 ) continue;
2937 pE = pTerm->pExpr;
2938 assert( pE!=0 );
2939 if( pLevel->iLeftJoin && !ExprHasProperty(pE, EP_FromJoin) ){
2940 continue;
2941 }
drh111a6a72008-12-21 03:51:16 +00002942 sqlite3ExprIfFalse(pParse, pE, addrCont, SQLITE_JUMPIFNULL);
drh111a6a72008-12-21 03:51:16 +00002943 k = 1;
2944 pTerm->wtFlags |= TERM_CODED;
2945 }
2946
2947 /* For a LEFT OUTER JOIN, generate code that will record the fact that
2948 ** at least one row of the right table has matched the left table.
2949 */
2950 if( pLevel->iLeftJoin ){
2951 pLevel->addrFirst = sqlite3VdbeCurrentAddr(v);
2952 sqlite3VdbeAddOp2(v, OP_Integer, 1, pLevel->iLeftJoin);
2953 VdbeComment((v, "record LEFT JOIN hit"));
drhceea3322009-04-23 13:22:42 +00002954 sqlite3ExprCacheClear(pParse);
drh111a6a72008-12-21 03:51:16 +00002955 for(pTerm=pWC->a, j=0; j<pWC->nTerm; j++, pTerm++){
2956 testcase( pTerm->wtFlags & TERM_VIRTUAL );
2957 testcase( pTerm->wtFlags & TERM_CODED );
2958 if( pTerm->wtFlags & (TERM_VIRTUAL|TERM_CODED) ) continue;
2959 if( (pTerm->prereqAll & notReady)!=0 ) continue;
2960 assert( pTerm->pExpr );
2961 sqlite3ExprIfFalse(pParse, pTerm->pExpr, addrCont, SQLITE_JUMPIFNULL);
2962 pTerm->wtFlags |= TERM_CODED;
2963 }
2964 }
danielk19771d461462009-04-21 09:02:45 +00002965 sqlite3ReleaseTempReg(pParse, iReleaseReg);
drh23d04d52008-12-23 23:56:22 +00002966
drh111a6a72008-12-21 03:51:16 +00002967 return notReady;
2968}
2969
drh549c8b62005-09-19 13:15:23 +00002970#if defined(SQLITE_TEST)
drh84bfda42005-07-15 13:05:21 +00002971/*
2972** The following variable holds a text description of query plan generated
2973** by the most recent call to sqlite3WhereBegin(). Each call to WhereBegin
2974** overwrites the previous. This information is used for testing and
2975** analysis only.
2976*/
2977char sqlite3_query_plan[BMS*2*40]; /* Text of the join */
2978static int nQPlan = 0; /* Next free slow in _query_plan[] */
2979
2980#endif /* SQLITE_TEST */
2981
2982
drh9eff6162006-06-12 21:59:13 +00002983/*
2984** Free a WhereInfo structure
2985*/
drh10fe8402008-10-11 16:47:35 +00002986static void whereInfoFree(sqlite3 *db, WhereInfo *pWInfo){
drh9eff6162006-06-12 21:59:13 +00002987 if( pWInfo ){
2988 int i;
2989 for(i=0; i<pWInfo->nLevel; i++){
drh4be8b512006-06-13 23:51:34 +00002990 sqlite3_index_info *pInfo = pWInfo->a[i].pIdxInfo;
2991 if( pInfo ){
danielk19771d461462009-04-21 09:02:45 +00002992 /* assert( pInfo->needToFreeIdxStr==0 || db->mallocFailed ); */
danielk197780442942008-12-24 11:25:39 +00002993 if( pInfo->needToFreeIdxStr ){
2994 sqlite3_free(pInfo->idxStr);
danielk1977be229652009-03-20 14:18:51 +00002995 }
drh633e6d52008-07-28 19:34:53 +00002996 sqlite3DbFree(db, pInfo);
danielk1977be8a7832006-06-13 15:00:54 +00002997 }
drh9eff6162006-06-12 21:59:13 +00002998 }
drh111a6a72008-12-21 03:51:16 +00002999 whereClauseClear(pWInfo->pWC);
drh633e6d52008-07-28 19:34:53 +00003000 sqlite3DbFree(db, pWInfo);
drh9eff6162006-06-12 21:59:13 +00003001 }
3002}
3003
drh94a11212004-09-25 13:12:14 +00003004
3005/*
drhe3184742002-06-19 14:27:05 +00003006** Generate the beginning of the loop used for WHERE clause processing.
drhacf3b982005-01-03 01:27:18 +00003007** The return value is a pointer to an opaque structure that contains
drh75897232000-05-29 14:26:00 +00003008** information needed to terminate the loop. Later, the calling routine
danielk19774adee202004-05-08 08:23:19 +00003009** should invoke sqlite3WhereEnd() with the return value of this function
drh75897232000-05-29 14:26:00 +00003010** in order to complete the WHERE clause processing.
3011**
3012** If an error occurs, this routine returns NULL.
drhc27a1ce2002-06-14 20:58:45 +00003013**
3014** The basic idea is to do a nested loop, one loop for each table in
3015** the FROM clause of a select. (INSERT and UPDATE statements are the
3016** same as a SELECT with only a single table in the FROM clause.) For
3017** example, if the SQL is this:
3018**
3019** SELECT * FROM t1, t2, t3 WHERE ...;
3020**
3021** Then the code generated is conceptually like the following:
3022**
3023** foreach row1 in t1 do \ Code generated
danielk19774adee202004-05-08 08:23:19 +00003024** foreach row2 in t2 do |-- by sqlite3WhereBegin()
drhc27a1ce2002-06-14 20:58:45 +00003025** foreach row3 in t3 do /
3026** ...
3027** end \ Code generated
danielk19774adee202004-05-08 08:23:19 +00003028** end |-- by sqlite3WhereEnd()
drhc27a1ce2002-06-14 20:58:45 +00003029** end /
3030**
drh29dda4a2005-07-21 18:23:20 +00003031** Note that the loops might not be nested in the order in which they
3032** appear in the FROM clause if a different order is better able to make
drh51147ba2005-07-23 22:59:55 +00003033** use of indices. Note also that when the IN operator appears in
3034** the WHERE clause, it might result in additional nested loops for
3035** scanning through all values on the right-hand side of the IN.
drh29dda4a2005-07-21 18:23:20 +00003036**
drhc27a1ce2002-06-14 20:58:45 +00003037** There are Btree cursors associated with each table. t1 uses cursor
drh6a3ea0e2003-05-02 14:32:12 +00003038** number pTabList->a[0].iCursor. t2 uses the cursor pTabList->a[1].iCursor.
3039** And so forth. This routine generates code to open those VDBE cursors
danielk19774adee202004-05-08 08:23:19 +00003040** and sqlite3WhereEnd() generates the code to close them.
drhc27a1ce2002-06-14 20:58:45 +00003041**
drhe6f85e72004-12-25 01:03:13 +00003042** The code that sqlite3WhereBegin() generates leaves the cursors named
3043** in pTabList pointing at their appropriate entries. The [...] code
drhf0863fe2005-06-12 21:35:51 +00003044** can use OP_Column and OP_Rowid opcodes on these cursors to extract
drhe6f85e72004-12-25 01:03:13 +00003045** data from the various tables of the loop.
3046**
drhc27a1ce2002-06-14 20:58:45 +00003047** If the WHERE clause is empty, the foreach loops must each scan their
3048** entire tables. Thus a three-way join is an O(N^3) operation. But if
3049** the tables have indices and there are terms in the WHERE clause that
3050** refer to those indices, a complete table scan can be avoided and the
3051** code will run much faster. Most of the work of this routine is checking
3052** to see if there are indices that can be used to speed up the loop.
3053**
3054** Terms of the WHERE clause are also used to limit which rows actually
3055** make it to the "..." in the middle of the loop. After each "foreach",
3056** terms of the WHERE clause that use only terms in that loop and outer
3057** loops are evaluated and if false a jump is made around all subsequent
3058** inner loops (or around the "..." if the test occurs within the inner-
3059** most loop)
3060**
3061** OUTER JOINS
3062**
3063** An outer join of tables t1 and t2 is conceptally coded as follows:
3064**
3065** foreach row1 in t1 do
3066** flag = 0
3067** foreach row2 in t2 do
3068** start:
3069** ...
3070** flag = 1
3071** end
drhe3184742002-06-19 14:27:05 +00003072** if flag==0 then
3073** move the row2 cursor to a null row
3074** goto start
3075** fi
drhc27a1ce2002-06-14 20:58:45 +00003076** end
3077**
drhe3184742002-06-19 14:27:05 +00003078** ORDER BY CLAUSE PROCESSING
3079**
3080** *ppOrderBy is a pointer to the ORDER BY clause of a SELECT statement,
3081** if there is one. If there is no ORDER BY clause or if this routine
3082** is called from an UPDATE or DELETE statement, then ppOrderBy is NULL.
3083**
3084** If an index can be used so that the natural output order of the table
3085** scan is correct for the ORDER BY clause, then that index is used and
3086** *ppOrderBy is set to NULL. This is an optimization that prevents an
3087** unnecessary sort of the result set if an index appropriate for the
3088** ORDER BY clause already exists.
3089**
3090** If the where clause loops cannot be arranged to provide the correct
3091** output order, then the *ppOrderBy is unchanged.
drh75897232000-05-29 14:26:00 +00003092*/
danielk19774adee202004-05-08 08:23:19 +00003093WhereInfo *sqlite3WhereBegin(
danielk1977ed326d72004-11-16 15:50:19 +00003094 Parse *pParse, /* The parser context */
3095 SrcList *pTabList, /* A list of all tables to be scanned */
3096 Expr *pWhere, /* The WHERE clause */
danielk1977a9d1ccb2008-01-05 17:39:29 +00003097 ExprList **ppOrderBy, /* An ORDER BY clause, or NULL */
drh336a5302009-04-24 15:46:21 +00003098 u16 wctrlFlags /* One of the WHERE_* flags defined in sqliteInt.h */
drh75897232000-05-29 14:26:00 +00003099){
3100 int i; /* Loop counter */
danielk1977be229652009-03-20 14:18:51 +00003101 int nByteWInfo; /* Num. bytes allocated for WhereInfo struct */
drh75897232000-05-29 14:26:00 +00003102 WhereInfo *pWInfo; /* Will become the return value of this function */
3103 Vdbe *v = pParse->pVdbe; /* The virtual database engine */
drhfe05af82005-07-21 03:14:59 +00003104 Bitmask notReady; /* Cursors that are not yet positioned */
drh111a6a72008-12-21 03:51:16 +00003105 WhereMaskSet *pMaskSet; /* The expression mask set */
drh111a6a72008-12-21 03:51:16 +00003106 WhereClause *pWC; /* Decomposition of the WHERE clause */
drh9012bcb2004-12-19 00:11:35 +00003107 struct SrcList_item *pTabItem; /* A single entry from pTabList */
3108 WhereLevel *pLevel; /* A single level in the pWInfo list */
drh29dda4a2005-07-21 18:23:20 +00003109 int iFrom; /* First unused FROM clause element */
drh111a6a72008-12-21 03:51:16 +00003110 int andFlags; /* AND-ed combination of all pWC->a[].wtFlags */
drh17435752007-08-16 04:30:38 +00003111 sqlite3 *db; /* Database connection */
drh75897232000-05-29 14:26:00 +00003112
drh29dda4a2005-07-21 18:23:20 +00003113 /* The number of tables in the FROM clause is limited by the number of
drh1398ad32005-01-19 23:24:50 +00003114 ** bits in a Bitmask
3115 */
drh29dda4a2005-07-21 18:23:20 +00003116 if( pTabList->nSrc>BMS ){
3117 sqlite3ErrorMsg(pParse, "at most %d tables in a join", BMS);
drh1398ad32005-01-19 23:24:50 +00003118 return 0;
3119 }
3120
drh75897232000-05-29 14:26:00 +00003121 /* Allocate and initialize the WhereInfo structure that will become the
danielk1977be229652009-03-20 14:18:51 +00003122 ** return value. A single allocation is used to store the WhereInfo
3123 ** struct, the contents of WhereInfo.a[], the WhereClause structure
3124 ** and the WhereMaskSet structure. Since WhereClause contains an 8-byte
3125 ** field (type Bitmask) it must be aligned on an 8-byte boundary on
3126 ** some architectures. Hence the ROUND8() below.
drh75897232000-05-29 14:26:00 +00003127 */
drh17435752007-08-16 04:30:38 +00003128 db = pParse->db;
danielk1977be229652009-03-20 14:18:51 +00003129 nByteWInfo = ROUND8(sizeof(WhereInfo)+(pTabList->nSrc-1)*sizeof(WhereLevel));
3130 pWInfo = sqlite3DbMallocZero(db,
3131 nByteWInfo +
3132 sizeof(WhereClause) +
3133 sizeof(WhereMaskSet)
3134 );
drh17435752007-08-16 04:30:38 +00003135 if( db->mallocFailed ){
danielk197785574e32008-10-06 05:32:18 +00003136 goto whereBeginError;
drh75897232000-05-29 14:26:00 +00003137 }
danielk197770b6d572006-06-19 04:49:34 +00003138 pWInfo->nLevel = pTabList->nSrc;
drh75897232000-05-29 14:26:00 +00003139 pWInfo->pParse = pParse;
3140 pWInfo->pTabList = pTabList;
danielk19774adee202004-05-08 08:23:19 +00003141 pWInfo->iBreak = sqlite3VdbeMakeLabel(v);
danielk1977be229652009-03-20 14:18:51 +00003142 pWInfo->pWC = pWC = (WhereClause *)&((u8 *)pWInfo)[nByteWInfo];
drh6df2acd2008-12-28 16:55:25 +00003143 pWInfo->wctrlFlags = wctrlFlags;
drh111a6a72008-12-21 03:51:16 +00003144 pMaskSet = (WhereMaskSet*)&pWC[1];
drh08192d52002-04-30 19:20:28 +00003145
drh111a6a72008-12-21 03:51:16 +00003146 /* Split the WHERE clause into separate subexpressions where each
3147 ** subexpression is separated by an AND operator.
3148 */
3149 initMaskSet(pMaskSet);
3150 whereClauseInit(pWC, pParse, pMaskSet);
3151 sqlite3ExprCodeConstants(pParse, pWhere);
3152 whereSplit(pWC, pWhere, TK_AND);
3153
drh08192d52002-04-30 19:20:28 +00003154 /* Special case: a WHERE clause that is constant. Evaluate the
3155 ** expression and either jump over all of the code or fall thru.
3156 */
drh0a168372007-06-08 00:20:47 +00003157 if( pWhere && (pTabList->nSrc==0 || sqlite3ExprIsConstantNotJoin(pWhere)) ){
drh35573352008-01-08 23:54:25 +00003158 sqlite3ExprIfFalse(pParse, pWhere, pWInfo->iBreak, SQLITE_JUMPIFNULL);
drhdf199a22002-06-14 22:38:41 +00003159 pWhere = 0;
drh08192d52002-04-30 19:20:28 +00003160 }
drh75897232000-05-29 14:26:00 +00003161
drh42165be2008-03-26 14:56:34 +00003162 /* Assign a bit from the bitmask to every term in the FROM clause.
3163 **
3164 ** When assigning bitmask values to FROM clause cursors, it must be
3165 ** the case that if X is the bitmask for the N-th FROM clause term then
3166 ** the bitmask for all FROM clause terms to the left of the N-th term
3167 ** is (X-1). An expression from the ON clause of a LEFT JOIN can use
3168 ** its Expr.iRightJoinTable value to find the bitmask of the right table
3169 ** of the join. Subtracting one from the right table bitmask gives a
3170 ** bitmask for all tables to the left of the join. Knowing the bitmask
3171 ** for all tables to the left of a left join is important. Ticket #3015.
danielk1977e672c8e2009-05-22 15:43:26 +00003172 **
3173 ** Configure the WhereClause.vmask variable so that bits that correspond
3174 ** to virtual table cursors are set. This is used to selectively disable
3175 ** the OR-to-IN transformation in exprAnalyzeOrTerm(). It is not helpful
3176 ** with virtual tables.
drh42165be2008-03-26 14:56:34 +00003177 */
danielk1977e672c8e2009-05-22 15:43:26 +00003178 assert( pWC->vmask==0 && pMaskSet->n==0 );
drh42165be2008-03-26 14:56:34 +00003179 for(i=0; i<pTabList->nSrc; i++){
drh111a6a72008-12-21 03:51:16 +00003180 createMask(pMaskSet, pTabList->a[i].iCursor);
danielk1977e672c8e2009-05-22 15:43:26 +00003181 if( pTabList->a[i].pTab && IsVirtual(pTabList->a[i].pTab) ){
3182 pWC->vmask |= ((Bitmask)1 << i);
3183 }
drh42165be2008-03-26 14:56:34 +00003184 }
3185#ifndef NDEBUG
3186 {
3187 Bitmask toTheLeft = 0;
3188 for(i=0; i<pTabList->nSrc; i++){
drh111a6a72008-12-21 03:51:16 +00003189 Bitmask m = getMask(pMaskSet, pTabList->a[i].iCursor);
drh42165be2008-03-26 14:56:34 +00003190 assert( (m-1)==toTheLeft );
3191 toTheLeft |= m;
3192 }
3193 }
3194#endif
3195
drh29dda4a2005-07-21 18:23:20 +00003196 /* Analyze all of the subexpressions. Note that exprAnalyze() might
3197 ** add new virtual terms onto the end of the WHERE clause. We do not
3198 ** want to analyze these virtual terms, so start analyzing at the end
drhb6fb62d2005-09-20 08:47:20 +00003199 ** and work forward so that the added virtual terms are never processed.
drh75897232000-05-29 14:26:00 +00003200 */
drh111a6a72008-12-21 03:51:16 +00003201 exprAnalyzeAll(pTabList, pWC);
drh17435752007-08-16 04:30:38 +00003202 if( db->mallocFailed ){
danielk197785574e32008-10-06 05:32:18 +00003203 goto whereBeginError;
drh0bbaa1b2005-08-19 19:14:12 +00003204 }
drh75897232000-05-29 14:26:00 +00003205
drh29dda4a2005-07-21 18:23:20 +00003206 /* Chose the best index to use for each table in the FROM clause.
3207 **
drh51147ba2005-07-23 22:59:55 +00003208 ** This loop fills in the following fields:
3209 **
3210 ** pWInfo->a[].pIdx The index to use for this level of the loop.
drh165be382008-12-05 02:36:33 +00003211 ** pWInfo->a[].wsFlags WHERE_xxx flags associated with pIdx
drh51147ba2005-07-23 22:59:55 +00003212 ** pWInfo->a[].nEq The number of == and IN constraints
danielk197785574e32008-10-06 05:32:18 +00003213 ** pWInfo->a[].iFrom Which term of the FROM clause is being coded
drh51147ba2005-07-23 22:59:55 +00003214 ** pWInfo->a[].iTabCur The VDBE cursor for the database table
3215 ** pWInfo->a[].iIdxCur The VDBE cursor for the index
drh111a6a72008-12-21 03:51:16 +00003216 ** pWInfo->a[].pTerm When wsFlags==WO_OR, the OR-clause term
drh51147ba2005-07-23 22:59:55 +00003217 **
3218 ** This loop also figures out the nesting order of tables in the FROM
3219 ** clause.
drh75897232000-05-29 14:26:00 +00003220 */
drhfe05af82005-07-21 03:14:59 +00003221 notReady = ~(Bitmask)0;
drh9012bcb2004-12-19 00:11:35 +00003222 pTabItem = pTabList->a;
3223 pLevel = pWInfo->a;
drh943af3c2005-07-29 19:43:58 +00003224 andFlags = ~0;
drh4f0c5872007-03-26 22:05:01 +00003225 WHERETRACE(("*** Optimizer Start ***\n"));
drh29dda4a2005-07-21 18:23:20 +00003226 for(i=iFrom=0, pLevel=pWInfo->a; i<pTabList->nSrc; i++, pLevel++){
drh111a6a72008-12-21 03:51:16 +00003227 WhereCost bestPlan; /* Most efficient plan seen so far */
drh29dda4a2005-07-21 18:23:20 +00003228 Index *pIdx; /* Index for FROM table at pTabItem */
drh29dda4a2005-07-21 18:23:20 +00003229 int j; /* For looping over FROM tables */
drh02afc862006-01-20 18:10:57 +00003230 int bestJ = 0; /* The value of j */
drh29dda4a2005-07-21 18:23:20 +00003231 Bitmask m; /* Bitmask value for j or bestJ */
drh570b9352006-02-01 02:45:02 +00003232 int once = 0; /* True when first table is seen */
drh29dda4a2005-07-21 18:23:20 +00003233
drh111a6a72008-12-21 03:51:16 +00003234 memset(&bestPlan, 0, sizeof(bestPlan));
3235 bestPlan.rCost = SQLITE_BIG_DBL;
drh29dda4a2005-07-21 18:23:20 +00003236 for(j=iFrom, pTabItem=&pTabList->a[j]; j<pTabList->nSrc; j++, pTabItem++){
danielk19771d461462009-04-21 09:02:45 +00003237 int doNotReorder; /* True if this table should not be reordered */
3238 WhereCost sCost; /* Cost information from best[Virtual]Index() */
3239 ExprList *pOrderBy; /* ORDER BY clause for index to optimize */
drhdf26fd52006-06-06 11:45:54 +00003240
drh61dfc312006-12-16 16:25:15 +00003241 doNotReorder = (pTabItem->jointype & (JT_LEFT|JT_CROSS))!=0;
drhdf26fd52006-06-06 11:45:54 +00003242 if( once && doNotReorder ) break;
drh111a6a72008-12-21 03:51:16 +00003243 m = getMask(pMaskSet, pTabItem->iCursor);
drh29dda4a2005-07-21 18:23:20 +00003244 if( (m & notReady)==0 ){
3245 if( j==iFrom ) iFrom++;
3246 continue;
3247 }
danielk19771d461462009-04-21 09:02:45 +00003248 pOrderBy = ((i==0 && ppOrderBy )?*ppOrderBy:0);
3249
drh9eff6162006-06-12 21:59:13 +00003250 assert( pTabItem->pTab );
3251#ifndef SQLITE_OMIT_VIRTUALTABLE
drh4cbdda92006-06-14 19:00:20 +00003252 if( IsVirtual(pTabItem->pTab) ){
danielk19771d461462009-04-21 09:02:45 +00003253 sqlite3_index_info **pp = &pWInfo->a[j].pIdxInfo;
3254 bestVirtualIndex(pParse, pWC, pTabItem, notReady, pOrderBy, &sCost, pp);
drh9eff6162006-06-12 21:59:13 +00003255 }else
3256#endif
3257 {
danielk19771d461462009-04-21 09:02:45 +00003258 bestBtreeIndex(pParse, pWC, pTabItem, notReady, pOrderBy, &sCost);
drh9eff6162006-06-12 21:59:13 +00003259 }
danielk1977992347f2008-12-30 09:45:45 +00003260 if( once==0 || sCost.rCost<bestPlan.rCost ){
drh570b9352006-02-01 02:45:02 +00003261 once = 1;
drh111a6a72008-12-21 03:51:16 +00003262 bestPlan = sCost;
drh29dda4a2005-07-21 18:23:20 +00003263 bestJ = j;
3264 }
drhdf26fd52006-06-06 11:45:54 +00003265 if( doNotReorder ) break;
drh29dda4a2005-07-21 18:23:20 +00003266 }
danielk1977992347f2008-12-30 09:45:45 +00003267 assert( once );
3268 assert( notReady & getMask(pMaskSet, pTabList->a[bestJ].iCursor) );
drhcb041342008-06-12 00:07:29 +00003269 WHERETRACE(("*** Optimizer selects table %d for loop %d\n", bestJ,
drh3dec2232005-09-10 15:28:09 +00003270 pLevel-pWInfo->a));
drh111a6a72008-12-21 03:51:16 +00003271 if( (bestPlan.plan.wsFlags & WHERE_ORDERBY)!=0 ){
drhfe05af82005-07-21 03:14:59 +00003272 *ppOrderBy = 0;
drhc4a3c772001-04-04 11:48:57 +00003273 }
drh111a6a72008-12-21 03:51:16 +00003274 andFlags &= bestPlan.plan.wsFlags;
3275 pLevel->plan = bestPlan.plan;
3276 if( bestPlan.plan.wsFlags & WHERE_INDEXED ){
drh9012bcb2004-12-19 00:11:35 +00003277 pLevel->iIdxCur = pParse->nTab++;
drhfe05af82005-07-21 03:14:59 +00003278 }else{
3279 pLevel->iIdxCur = -1;
drh6b563442001-11-07 16:48:26 +00003280 }
drh111a6a72008-12-21 03:51:16 +00003281 notReady &= ~getMask(pMaskSet, pTabList->a[bestJ].iCursor);
shaned87897d2009-01-30 05:40:27 +00003282 pLevel->iFrom = (u8)bestJ;
danielk197785574e32008-10-06 05:32:18 +00003283
3284 /* Check that if the table scanned by this loop iteration had an
3285 ** INDEXED BY clause attached to it, that the named index is being
3286 ** used for the scan. If not, then query compilation has failed.
3287 ** Return an error.
3288 */
3289 pIdx = pTabList->a[bestJ].pIndex;
drh171256c2009-01-08 03:11:19 +00003290 if( pIdx ){
3291 if( (bestPlan.plan.wsFlags & WHERE_INDEXED)==0 ){
3292 sqlite3ErrorMsg(pParse, "cannot use index: %s", pIdx->zName);
3293 goto whereBeginError;
3294 }else{
3295 /* If an INDEXED BY clause is used, the bestIndex() function is
3296 ** guaranteed to find the index specified in the INDEXED BY clause
3297 ** if it find an index at all. */
3298 assert( bestPlan.plan.u.pIdx==pIdx );
3299 }
danielk197785574e32008-10-06 05:32:18 +00003300 }
drh75897232000-05-29 14:26:00 +00003301 }
drh4f0c5872007-03-26 22:05:01 +00003302 WHERETRACE(("*** Optimizer Finished ***\n"));
danielk19771d461462009-04-21 09:02:45 +00003303 if( pParse->nErr || db->mallocFailed ){
danielk197780442942008-12-24 11:25:39 +00003304 goto whereBeginError;
3305 }
drh75897232000-05-29 14:26:00 +00003306
drh943af3c2005-07-29 19:43:58 +00003307 /* If the total query only selects a single row, then the ORDER BY
3308 ** clause is irrelevant.
3309 */
3310 if( (andFlags & WHERE_UNIQUE)!=0 && ppOrderBy ){
3311 *ppOrderBy = 0;
3312 }
3313
drh08c88eb2008-04-10 13:33:18 +00003314 /* If the caller is an UPDATE or DELETE statement that is requesting
3315 ** to use a one-pass algorithm, determine if this is appropriate.
3316 ** The one-pass algorithm only works if the WHERE clause constraints
3317 ** the statement to update a single row.
3318 */
drh165be382008-12-05 02:36:33 +00003319 assert( (wctrlFlags & WHERE_ONEPASS_DESIRED)==0 || pWInfo->nLevel==1 );
3320 if( (wctrlFlags & WHERE_ONEPASS_DESIRED)!=0 && (andFlags & WHERE_UNIQUE)!=0 ){
drh08c88eb2008-04-10 13:33:18 +00003321 pWInfo->okOnePass = 1;
drh111a6a72008-12-21 03:51:16 +00003322 pWInfo->a[0].plan.wsFlags &= ~WHERE_IDX_ONLY;
drh08c88eb2008-04-10 13:33:18 +00003323 }
3324
drh9012bcb2004-12-19 00:11:35 +00003325 /* Open all tables in the pTabList and any indices selected for
3326 ** searching those tables.
3327 */
3328 sqlite3CodeVerifySchema(pParse, -1); /* Insert the cookie verifier Goto */
drh29dda4a2005-07-21 18:23:20 +00003329 for(i=0, pLevel=pWInfo->a; i<pTabList->nSrc; i++, pLevel++){
danielk1977da184232006-01-05 11:34:32 +00003330 Table *pTab; /* Table to open */
danielk1977da184232006-01-05 11:34:32 +00003331 int iDb; /* Index of database containing table/index */
drh9012bcb2004-12-19 00:11:35 +00003332
drhecc92422005-09-10 16:46:12 +00003333#ifndef SQLITE_OMIT_EXPLAIN
3334 if( pParse->explain==2 ){
3335 char *zMsg;
3336 struct SrcList_item *pItem = &pTabList->a[pLevel->iFrom];
danielk19771e536952007-08-16 10:09:01 +00003337 zMsg = sqlite3MPrintf(db, "TABLE %s", pItem->zName);
drhecc92422005-09-10 16:46:12 +00003338 if( pItem->zAlias ){
drh633e6d52008-07-28 19:34:53 +00003339 zMsg = sqlite3MAppendf(db, zMsg, "%s AS %s", zMsg, pItem->zAlias);
drhecc92422005-09-10 16:46:12 +00003340 }
drh111a6a72008-12-21 03:51:16 +00003341 if( (pLevel->plan.wsFlags & WHERE_INDEXED)!=0 ){
3342 zMsg = sqlite3MAppendf(db, zMsg, "%s WITH INDEX %s",
3343 zMsg, pLevel->plan.u.pIdx->zName);
drh46129af2008-12-30 16:18:47 +00003344 }else if( pLevel->plan.wsFlags & WHERE_MULTI_OR ){
3345 zMsg = sqlite3MAppendf(db, zMsg, "%s VIA MULTI-INDEX UNION", zMsg);
drh111a6a72008-12-21 03:51:16 +00003346 }else if( pLevel->plan.wsFlags & (WHERE_ROWID_EQ|WHERE_ROWID_RANGE) ){
drh633e6d52008-07-28 19:34:53 +00003347 zMsg = sqlite3MAppendf(db, zMsg, "%s USING PRIMARY KEY", zMsg);
drhecc92422005-09-10 16:46:12 +00003348 }
drh9eff6162006-06-12 21:59:13 +00003349#ifndef SQLITE_OMIT_VIRTUALTABLE
drh111a6a72008-12-21 03:51:16 +00003350 else if( (pLevel->plan.wsFlags & WHERE_VIRTUALTABLE)!=0 ){
3351 sqlite3_index_info *pVtabIdx = pLevel->plan.u.pVtabIdx;
drh633e6d52008-07-28 19:34:53 +00003352 zMsg = sqlite3MAppendf(db, zMsg, "%s VIRTUAL TABLE INDEX %d:%s", zMsg,
drh111a6a72008-12-21 03:51:16 +00003353 pVtabIdx->idxNum, pVtabIdx->idxStr);
drh9eff6162006-06-12 21:59:13 +00003354 }
3355#endif
drh111a6a72008-12-21 03:51:16 +00003356 if( pLevel->plan.wsFlags & WHERE_ORDERBY ){
drh633e6d52008-07-28 19:34:53 +00003357 zMsg = sqlite3MAppendf(db, zMsg, "%s ORDER BY", zMsg);
drhe2b39092006-04-21 09:38:36 +00003358 }
drh66a51672008-01-03 00:01:23 +00003359 sqlite3VdbeAddOp4(v, OP_Explain, i, pLevel->iFrom, 0, zMsg, P4_DYNAMIC);
drhecc92422005-09-10 16:46:12 +00003360 }
3361#endif /* SQLITE_OMIT_EXPLAIN */
drh29dda4a2005-07-21 18:23:20 +00003362 pTabItem = &pTabList->a[pLevel->iFrom];
drh9012bcb2004-12-19 00:11:35 +00003363 pTab = pTabItem->pTab;
danielk1977da184232006-01-05 11:34:32 +00003364 iDb = sqlite3SchemaToIndex(pParse->db, pTab->pSchema);
drh7d10d5a2008-08-20 16:35:10 +00003365 if( (pTab->tabFlags & TF_Ephemeral)!=0 || pTab->pSelect ) continue;
drh9eff6162006-06-12 21:59:13 +00003366#ifndef SQLITE_OMIT_VIRTUALTABLE
drh111a6a72008-12-21 03:51:16 +00003367 if( (pLevel->plan.wsFlags & WHERE_VIRTUALTABLE)!=0 ){
danielk197793626f42006-06-20 13:07:27 +00003368 int iCur = pTabItem->iCursor;
drh66a51672008-01-03 00:01:23 +00003369 sqlite3VdbeAddOp4(v, OP_VOpen, iCur, 0, 0,
3370 (const char*)pTab->pVtab, P4_VTAB);
drh9eff6162006-06-12 21:59:13 +00003371 }else
3372#endif
drh6df2acd2008-12-28 16:55:25 +00003373 if( (pLevel->plan.wsFlags & WHERE_IDX_ONLY)==0
3374 && (wctrlFlags & WHERE_OMIT_OPEN)==0 ){
drh08c88eb2008-04-10 13:33:18 +00003375 int op = pWInfo->okOnePass ? OP_OpenWrite : OP_OpenRead;
3376 sqlite3OpenTable(pParse, pTabItem->iCursor, iDb, pTab, op);
danielk197723432972008-11-17 16:42:00 +00003377 if( !pWInfo->okOnePass && pTab->nCol<BMS ){
danielk19779792eef2006-01-13 15:58:43 +00003378 Bitmask b = pTabItem->colUsed;
3379 int n = 0;
drh74161702006-02-24 02:53:49 +00003380 for(; b; b=b>>1, n++){}
shanec0688ea2009-03-05 03:48:06 +00003381 sqlite3VdbeChangeP4(v, sqlite3VdbeCurrentAddr(v)-1, SQLITE_INT_TO_PTR(n), P4_INT32);
danielk19779792eef2006-01-13 15:58:43 +00003382 assert( n<=pTab->nCol );
3383 }
danielk1977c00da102006-01-07 13:21:04 +00003384 }else{
3385 sqlite3TableLock(pParse, iDb, pTab->tnum, 0, pTab->zName);
drh9012bcb2004-12-19 00:11:35 +00003386 }
3387 pLevel->iTabCur = pTabItem->iCursor;
drh111a6a72008-12-21 03:51:16 +00003388 if( (pLevel->plan.wsFlags & WHERE_INDEXED)!=0 ){
3389 Index *pIx = pLevel->plan.u.pIdx;
danielk1977b3bf5562006-01-10 17:58:23 +00003390 KeyInfo *pKey = sqlite3IndexKeyinfo(pParse, pIx);
drh111a6a72008-12-21 03:51:16 +00003391 int iIdxCur = pLevel->iIdxCur;
danielk1977da184232006-01-05 11:34:32 +00003392 assert( pIx->pSchema==pTab->pSchema );
drh111a6a72008-12-21 03:51:16 +00003393 assert( iIdxCur>=0 );
danielk1977207872a2008-01-03 07:54:23 +00003394 sqlite3VdbeAddOp4(v, OP_OpenRead, iIdxCur, pIx->tnum, iDb,
drh66a51672008-01-03 00:01:23 +00003395 (char*)pKey, P4_KEYINFO_HANDOFF);
danielk1977207872a2008-01-03 07:54:23 +00003396 VdbeComment((v, "%s", pIx->zName));
drh9012bcb2004-12-19 00:11:35 +00003397 }
danielk1977da184232006-01-05 11:34:32 +00003398 sqlite3CodeVerifySchema(pParse, iDb);
drh9012bcb2004-12-19 00:11:35 +00003399 }
3400 pWInfo->iTop = sqlite3VdbeCurrentAddr(v);
3401
drh29dda4a2005-07-21 18:23:20 +00003402 /* Generate the code to do the search. Each iteration of the for
3403 ** loop below generates code for a single nested loop of the VM
3404 ** program.
drh75897232000-05-29 14:26:00 +00003405 */
drhfe05af82005-07-21 03:14:59 +00003406 notReady = ~(Bitmask)0;
drh111a6a72008-12-21 03:51:16 +00003407 for(i=0; i<pTabList->nSrc; i++){
3408 notReady = codeOneLoopStart(pWInfo, i, wctrlFlags, notReady);
drh813f31e2009-01-06 00:08:02 +00003409 pWInfo->iContinue = pWInfo->a[i].addrCont;
drh75897232000-05-29 14:26:00 +00003410 }
drh7ec764a2005-07-21 03:48:20 +00003411
3412#ifdef SQLITE_TEST /* For testing and debugging use only */
3413 /* Record in the query plan information about the current table
3414 ** and the index used to access it (if any). If the table itself
3415 ** is not used, its name is just '{}'. If no index is used
3416 ** the index is listed as "{}". If the primary key is used the
3417 ** index name is '*'.
3418 */
3419 for(i=0; i<pTabList->nSrc; i++){
3420 char *z;
3421 int n;
drh7ec764a2005-07-21 03:48:20 +00003422 pLevel = &pWInfo->a[i];
drh29dda4a2005-07-21 18:23:20 +00003423 pTabItem = &pTabList->a[pLevel->iFrom];
drh7ec764a2005-07-21 03:48:20 +00003424 z = pTabItem->zAlias;
3425 if( z==0 ) z = pTabItem->pTab->zName;
drhea678832008-12-10 19:26:22 +00003426 n = sqlite3Strlen30(z);
drh7ec764a2005-07-21 03:48:20 +00003427 if( n+nQPlan < sizeof(sqlite3_query_plan)-10 ){
drh111a6a72008-12-21 03:51:16 +00003428 if( pLevel->plan.wsFlags & WHERE_IDX_ONLY ){
drh5bb3eb92007-05-04 13:15:55 +00003429 memcpy(&sqlite3_query_plan[nQPlan], "{}", 2);
drh7ec764a2005-07-21 03:48:20 +00003430 nQPlan += 2;
3431 }else{
drh5bb3eb92007-05-04 13:15:55 +00003432 memcpy(&sqlite3_query_plan[nQPlan], z, n);
drh7ec764a2005-07-21 03:48:20 +00003433 nQPlan += n;
3434 }
3435 sqlite3_query_plan[nQPlan++] = ' ';
3436 }
drh111a6a72008-12-21 03:51:16 +00003437 testcase( pLevel->plan.wsFlags & WHERE_ROWID_EQ );
3438 testcase( pLevel->plan.wsFlags & WHERE_ROWID_RANGE );
3439 if( pLevel->plan.wsFlags & (WHERE_ROWID_EQ|WHERE_ROWID_RANGE) ){
drh5bb3eb92007-05-04 13:15:55 +00003440 memcpy(&sqlite3_query_plan[nQPlan], "* ", 2);
drh7ec764a2005-07-21 03:48:20 +00003441 nQPlan += 2;
drh111a6a72008-12-21 03:51:16 +00003442 }else if( (pLevel->plan.wsFlags & WHERE_INDEXED)!=0 ){
3443 n = sqlite3Strlen30(pLevel->plan.u.pIdx->zName);
drh7ec764a2005-07-21 03:48:20 +00003444 if( n+nQPlan < sizeof(sqlite3_query_plan)-2 ){
drh111a6a72008-12-21 03:51:16 +00003445 memcpy(&sqlite3_query_plan[nQPlan], pLevel->plan.u.pIdx->zName, n);
drh7ec764a2005-07-21 03:48:20 +00003446 nQPlan += n;
3447 sqlite3_query_plan[nQPlan++] = ' ';
3448 }
drh111a6a72008-12-21 03:51:16 +00003449 }else{
3450 memcpy(&sqlite3_query_plan[nQPlan], "{} ", 3);
3451 nQPlan += 3;
drh7ec764a2005-07-21 03:48:20 +00003452 }
3453 }
3454 while( nQPlan>0 && sqlite3_query_plan[nQPlan-1]==' ' ){
3455 sqlite3_query_plan[--nQPlan] = 0;
3456 }
3457 sqlite3_query_plan[nQPlan] = 0;
3458 nQPlan = 0;
3459#endif /* SQLITE_TEST // Testing and debugging use only */
3460
drh29dda4a2005-07-21 18:23:20 +00003461 /* Record the continuation address in the WhereInfo structure. Then
3462 ** clean up and return.
3463 */
drh75897232000-05-29 14:26:00 +00003464 return pWInfo;
drhe23399f2005-07-22 00:31:39 +00003465
3466 /* Jump here if malloc fails */
danielk197785574e32008-10-06 05:32:18 +00003467whereBeginError:
drh10fe8402008-10-11 16:47:35 +00003468 whereInfoFree(db, pWInfo);
drhe23399f2005-07-22 00:31:39 +00003469 return 0;
drh75897232000-05-29 14:26:00 +00003470}
3471
3472/*
drhc27a1ce2002-06-14 20:58:45 +00003473** Generate the end of the WHERE loop. See comments on
danielk19774adee202004-05-08 08:23:19 +00003474** sqlite3WhereBegin() for additional information.
drh75897232000-05-29 14:26:00 +00003475*/
danielk19774adee202004-05-08 08:23:19 +00003476void sqlite3WhereEnd(WhereInfo *pWInfo){
drh633e6d52008-07-28 19:34:53 +00003477 Parse *pParse = pWInfo->pParse;
3478 Vdbe *v = pParse->pVdbe;
drh19a775c2000-06-05 18:54:46 +00003479 int i;
drh6b563442001-11-07 16:48:26 +00003480 WhereLevel *pLevel;
drhad3cab52002-05-24 02:04:32 +00003481 SrcList *pTabList = pWInfo->pTabList;
drh633e6d52008-07-28 19:34:53 +00003482 sqlite3 *db = pParse->db;
drh19a775c2000-06-05 18:54:46 +00003483
drh9012bcb2004-12-19 00:11:35 +00003484 /* Generate loop termination code.
3485 */
drhceea3322009-04-23 13:22:42 +00003486 sqlite3ExprCacheClear(pParse);
drhad3cab52002-05-24 02:04:32 +00003487 for(i=pTabList->nSrc-1; i>=0; i--){
drh6b563442001-11-07 16:48:26 +00003488 pLevel = &pWInfo->a[i];
drhb3190c12008-12-08 21:37:14 +00003489 sqlite3VdbeResolveLabel(v, pLevel->addrCont);
drh6b563442001-11-07 16:48:26 +00003490 if( pLevel->op!=OP_Noop ){
drh66a51672008-01-03 00:01:23 +00003491 sqlite3VdbeAddOp2(v, pLevel->op, pLevel->p1, pLevel->p2);
drhd1d38482008-10-07 23:46:38 +00003492 sqlite3VdbeChangeP5(v, pLevel->p5);
drh19a775c2000-06-05 18:54:46 +00003493 }
drh111a6a72008-12-21 03:51:16 +00003494 if( pLevel->plan.wsFlags & WHERE_IN_ABLE && pLevel->u.in.nIn>0 ){
drh72e8fa42007-03-28 14:30:06 +00003495 struct InLoop *pIn;
drhe23399f2005-07-22 00:31:39 +00003496 int j;
drhb3190c12008-12-08 21:37:14 +00003497 sqlite3VdbeResolveLabel(v, pLevel->addrNxt);
drh111a6a72008-12-21 03:51:16 +00003498 for(j=pLevel->u.in.nIn, pIn=&pLevel->u.in.aInLoop[j-1]; j>0; j--, pIn--){
drhb3190c12008-12-08 21:37:14 +00003499 sqlite3VdbeJumpHere(v, pIn->addrInTop+1);
3500 sqlite3VdbeAddOp2(v, OP_Next, pIn->iCur, pIn->addrInTop);
3501 sqlite3VdbeJumpHere(v, pIn->addrInTop-1);
drhe23399f2005-07-22 00:31:39 +00003502 }
drh111a6a72008-12-21 03:51:16 +00003503 sqlite3DbFree(db, pLevel->u.in.aInLoop);
drhd99f7062002-06-08 23:25:08 +00003504 }
drhb3190c12008-12-08 21:37:14 +00003505 sqlite3VdbeResolveLabel(v, pLevel->addrBrk);
drhad2d8302002-05-24 20:31:36 +00003506 if( pLevel->iLeftJoin ){
3507 int addr;
drh3c84ddf2008-01-09 02:15:38 +00003508 addr = sqlite3VdbeAddOp1(v, OP_IfPos, pLevel->iLeftJoin);
3509 sqlite3VdbeAddOp1(v, OP_NullRow, pTabList->a[i].iCursor);
drh9012bcb2004-12-19 00:11:35 +00003510 if( pLevel->iIdxCur>=0 ){
drh3c84ddf2008-01-09 02:15:38 +00003511 sqlite3VdbeAddOp1(v, OP_NullRow, pLevel->iIdxCur);
drh7f09b3e2002-08-13 13:15:49 +00003512 }
drh336a5302009-04-24 15:46:21 +00003513 if( pLevel->op==OP_Return ){
3514 sqlite3VdbeAddOp2(v, OP_Gosub, pLevel->p1, pLevel->addrFirst);
3515 }else{
3516 sqlite3VdbeAddOp2(v, OP_Goto, 0, pLevel->addrFirst);
3517 }
drhd654be82005-09-20 17:42:23 +00003518 sqlite3VdbeJumpHere(v, addr);
drhad2d8302002-05-24 20:31:36 +00003519 }
drh19a775c2000-06-05 18:54:46 +00003520 }
drh9012bcb2004-12-19 00:11:35 +00003521
3522 /* The "break" point is here, just past the end of the outer loop.
3523 ** Set it.
3524 */
danielk19774adee202004-05-08 08:23:19 +00003525 sqlite3VdbeResolveLabel(v, pWInfo->iBreak);
drh9012bcb2004-12-19 00:11:35 +00003526
drh29dda4a2005-07-21 18:23:20 +00003527 /* Close all of the cursors that were opened by sqlite3WhereBegin.
drh9012bcb2004-12-19 00:11:35 +00003528 */
drh29dda4a2005-07-21 18:23:20 +00003529 for(i=0, pLevel=pWInfo->a; i<pTabList->nSrc; i++, pLevel++){
3530 struct SrcList_item *pTabItem = &pTabList->a[pLevel->iFrom];
drh9012bcb2004-12-19 00:11:35 +00003531 Table *pTab = pTabItem->pTab;
drh5cf590c2003-04-24 01:45:04 +00003532 assert( pTab!=0 );
drh7d10d5a2008-08-20 16:35:10 +00003533 if( (pTab->tabFlags & TF_Ephemeral)!=0 || pTab->pSelect ) continue;
drh6df2acd2008-12-28 16:55:25 +00003534 if( (pWInfo->wctrlFlags & WHERE_OMIT_CLOSE)==0 ){
3535 if( !pWInfo->okOnePass && (pLevel->plan.wsFlags & WHERE_IDX_ONLY)==0 ){
3536 sqlite3VdbeAddOp1(v, OP_Close, pTabItem->iCursor);
3537 }
3538 if( (pLevel->plan.wsFlags & WHERE_INDEXED)!=0 ){
3539 sqlite3VdbeAddOp1(v, OP_Close, pLevel->iIdxCur);
3540 }
drh9012bcb2004-12-19 00:11:35 +00003541 }
3542
danielk197721de2e72007-11-29 17:43:27 +00003543 /* If this scan uses an index, make code substitutions to read data
3544 ** from the index in preference to the table. Sometimes, this means
3545 ** the table need never be read from. This is a performance boost,
3546 ** as the vdbe level waits until the table is read before actually
3547 ** seeking the table cursor to the record corresponding to the current
3548 ** position in the index.
drh9012bcb2004-12-19 00:11:35 +00003549 **
3550 ** Calls to the code generator in between sqlite3WhereBegin and
3551 ** sqlite3WhereEnd will have created code that references the table
3552 ** directly. This loop scans all that code looking for opcodes
3553 ** that reference the table and converts them into opcodes that
3554 ** reference the index.
3555 */
drh111a6a72008-12-21 03:51:16 +00003556 if( (pLevel->plan.wsFlags & WHERE_INDEXED)!=0 ){
danielk1977f0113002006-01-24 12:09:17 +00003557 int k, j, last;
drh9012bcb2004-12-19 00:11:35 +00003558 VdbeOp *pOp;
drh111a6a72008-12-21 03:51:16 +00003559 Index *pIdx = pLevel->plan.u.pIdx;
3560 int useIndexOnly = pLevel->plan.wsFlags & WHERE_IDX_ONLY;
drh9012bcb2004-12-19 00:11:35 +00003561
3562 assert( pIdx!=0 );
3563 pOp = sqlite3VdbeGetOp(v, pWInfo->iTop);
3564 last = sqlite3VdbeCurrentAddr(v);
danielk1977f0113002006-01-24 12:09:17 +00003565 for(k=pWInfo->iTop; k<last; k++, pOp++){
drh9012bcb2004-12-19 00:11:35 +00003566 if( pOp->p1!=pLevel->iTabCur ) continue;
3567 if( pOp->opcode==OP_Column ){
drh9012bcb2004-12-19 00:11:35 +00003568 for(j=0; j<pIdx->nColumn; j++){
3569 if( pOp->p2==pIdx->aiColumn[j] ){
3570 pOp->p2 = j;
danielk197721de2e72007-11-29 17:43:27 +00003571 pOp->p1 = pLevel->iIdxCur;
drh9012bcb2004-12-19 00:11:35 +00003572 break;
3573 }
3574 }
danielk197721de2e72007-11-29 17:43:27 +00003575 assert(!useIndexOnly || j<pIdx->nColumn);
drhf0863fe2005-06-12 21:35:51 +00003576 }else if( pOp->opcode==OP_Rowid ){
drh9012bcb2004-12-19 00:11:35 +00003577 pOp->p1 = pLevel->iIdxCur;
drhf0863fe2005-06-12 21:35:51 +00003578 pOp->opcode = OP_IdxRowid;
danielk197721de2e72007-11-29 17:43:27 +00003579 }else if( pOp->opcode==OP_NullRow && useIndexOnly ){
danielk19776c18b6e2005-01-30 09:17:58 +00003580 pOp->opcode = OP_Noop;
drh9012bcb2004-12-19 00:11:35 +00003581 }
3582 }
drh6b563442001-11-07 16:48:26 +00003583 }
drh19a775c2000-06-05 18:54:46 +00003584 }
drh9012bcb2004-12-19 00:11:35 +00003585
3586 /* Final cleanup
3587 */
drh10fe8402008-10-11 16:47:35 +00003588 whereInfoFree(db, pWInfo);
drh75897232000-05-29 14:26:00 +00003589 return;
3590}