blob: a0b431ac49005e5c9c90879c0556080fda5674ea [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**
drh4e8be3b2009-06-08 17:11:08 +000019** $Id: where.c,v 1.403 2009/06/08 17:11:08 drh 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 */
drh50d654d2009-06-03 01:24:54 +0000135#if defined(SQLITE_SMALL_STACK)
136 WhereTerm aStatic[1]; /* Initial static space for a[] */
137#else
138 WhereTerm aStatic[8]; /* Initial static space for a[] */
139#endif
drhe23399f2005-07-22 00:31:39 +0000140};
141
142/*
drh700a2262008-12-17 19:22:15 +0000143** A WhereTerm with eOperator==WO_OR has its u.pOrInfo pointer set to
144** a dynamically allocated instance of the following structure.
145*/
146struct WhereOrInfo {
drh111a6a72008-12-21 03:51:16 +0000147 WhereClause wc; /* Decomposition into subterms */
drh1a58fe02008-12-20 02:06:13 +0000148 Bitmask indexable; /* Bitmask of all indexable tables in the clause */
drh700a2262008-12-17 19:22:15 +0000149};
150
151/*
152** A WhereTerm with eOperator==WO_AND has its u.pAndInfo pointer set to
153** a dynamically allocated instance of the following structure.
154*/
155struct WhereAndInfo {
drh29435252008-12-28 18:35:08 +0000156 WhereClause wc; /* The subexpression broken out */
drh700a2262008-12-17 19:22:15 +0000157};
158
159/*
drh6a3ea0e2003-05-02 14:32:12 +0000160** An instance of the following structure keeps track of a mapping
drh0aa74ed2005-07-16 13:33:20 +0000161** between VDBE cursor numbers and bits of the bitmasks in WhereTerm.
drh51669862004-12-18 18:40:26 +0000162**
163** The VDBE cursor numbers are small integers contained in
164** SrcList_item.iCursor and Expr.iTable fields. For any given WHERE
165** clause, the cursor numbers might not begin with 0 and they might
166** contain gaps in the numbering sequence. But we want to make maximum
167** use of the bits in our bitmasks. This structure provides a mapping
168** from the sparse cursor numbers into consecutive integers beginning
169** with 0.
170**
drh111a6a72008-12-21 03:51:16 +0000171** If WhereMaskSet.ix[A]==B it means that The A-th bit of a Bitmask
drh51669862004-12-18 18:40:26 +0000172** corresponds VDBE cursor number B. The A-th bit of a bitmask is 1<<A.
173**
174** For example, if the WHERE clause expression used these VDBE
drh111a6a72008-12-21 03:51:16 +0000175** cursors: 4, 5, 8, 29, 57, 73. Then the WhereMaskSet structure
drh51669862004-12-18 18:40:26 +0000176** would map those cursor numbers into bits 0 through 5.
177**
178** Note that the mapping is not necessarily ordered. In the example
179** above, the mapping might go like this: 4->3, 5->1, 8->2, 29->0,
180** 57->5, 73->4. Or one of 719 other combinations might be used. It
181** does not really matter. What is important is that sparse cursor
182** numbers all get mapped into bit numbers that begin with 0 and contain
183** no gaps.
drh6a3ea0e2003-05-02 14:32:12 +0000184*/
drh111a6a72008-12-21 03:51:16 +0000185struct WhereMaskSet {
drh1398ad32005-01-19 23:24:50 +0000186 int n; /* Number of assigned cursor values */
danielk197723432972008-11-17 16:42:00 +0000187 int ix[BMS]; /* Cursor assigned to each bit */
drh6a3ea0e2003-05-02 14:32:12 +0000188};
189
drh111a6a72008-12-21 03:51:16 +0000190/*
191** A WhereCost object records a lookup strategy and the estimated
192** cost of pursuing that strategy.
193*/
194struct WhereCost {
195 WherePlan plan; /* The lookup strategy */
196 double rCost; /* Overall cost of pursuing this search strategy */
197 double nRow; /* Estimated number of output rows */
198};
drh0aa74ed2005-07-16 13:33:20 +0000199
drh6a3ea0e2003-05-02 14:32:12 +0000200/*
drh51147ba2005-07-23 22:59:55 +0000201** Bitmasks for the operators that indices are able to exploit. An
202** OR-ed combination of these values can be used when searching for
203** terms in the where clause.
204*/
drh165be382008-12-05 02:36:33 +0000205#define WO_IN 0x001
206#define WO_EQ 0x002
drh51147ba2005-07-23 22:59:55 +0000207#define WO_LT (WO_EQ<<(TK_LT-TK_EQ))
208#define WO_LE (WO_EQ<<(TK_LE-TK_EQ))
209#define WO_GT (WO_EQ<<(TK_GT-TK_EQ))
210#define WO_GE (WO_EQ<<(TK_GE-TK_EQ))
drh165be382008-12-05 02:36:33 +0000211#define WO_MATCH 0x040
212#define WO_ISNULL 0x080
drh700a2262008-12-17 19:22:15 +0000213#define WO_OR 0x100 /* Two or more OR-connected terms */
214#define WO_AND 0x200 /* Two or more AND-connected terms */
drh51147ba2005-07-23 22:59:55 +0000215
drhec1724e2008-12-09 01:32:03 +0000216#define WO_ALL 0xfff /* Mask of all possible WO_* values */
drh1a58fe02008-12-20 02:06:13 +0000217#define WO_SINGLE 0x0ff /* Mask of all non-compound WO_* values */
drhec1724e2008-12-09 01:32:03 +0000218
drh51147ba2005-07-23 22:59:55 +0000219/*
drh700a2262008-12-17 19:22:15 +0000220** Value for wsFlags returned by bestIndex() and stored in
221** WhereLevel.wsFlags. These flags determine which search
222** strategies are appropriate.
drhf2d315d2007-01-25 16:56:06 +0000223**
drh165be382008-12-05 02:36:33 +0000224** The least significant 12 bits is reserved as a mask for WO_ values above.
drh700a2262008-12-17 19:22:15 +0000225** The WhereLevel.wsFlags field is usually set to WO_IN|WO_EQ|WO_ISNULL.
226** But if the table is the right table of a left join, WhereLevel.wsFlags
227** is set to WO_IN|WO_EQ. The WhereLevel.wsFlags field can then be used as
drhf2d315d2007-01-25 16:56:06 +0000228** the "op" parameter to findTerm when we are resolving equality constraints.
229** ISNULL constraints will then not be used on the right table of a left
230** join. Tickets #2177 and #2189.
drh51147ba2005-07-23 22:59:55 +0000231*/
drh165be382008-12-05 02:36:33 +0000232#define WHERE_ROWID_EQ 0x00001000 /* rowid=EXPR or rowid IN (...) */
233#define WHERE_ROWID_RANGE 0x00002000 /* rowid<EXPR and/or rowid>EXPR */
drh46619d62009-04-24 14:51:42 +0000234#define WHERE_COLUMN_EQ 0x00010000 /* x=EXPR or x IN (...) or x IS NULL */
drh165be382008-12-05 02:36:33 +0000235#define WHERE_COLUMN_RANGE 0x00020000 /* x<EXPR and/or x>EXPR */
236#define WHERE_COLUMN_IN 0x00040000 /* x IN (...) */
drh46619d62009-04-24 14:51:42 +0000237#define WHERE_COLUMN_NULL 0x00080000 /* x IS NULL */
238#define WHERE_INDEXED 0x000f0000 /* Anything that uses an index */
239#define WHERE_IN_ABLE 0x000f1000 /* Able to support an IN operator */
drh165be382008-12-05 02:36:33 +0000240#define WHERE_TOP_LIMIT 0x00100000 /* x<EXPR or x<=EXPR constraint */
241#define WHERE_BTM_LIMIT 0x00200000 /* x>EXPR or x>=EXPR constraint */
242#define WHERE_IDX_ONLY 0x00800000 /* Use index only - omit table */
243#define WHERE_ORDERBY 0x01000000 /* Output will appear in correct order */
244#define WHERE_REVERSE 0x02000000 /* Scan in reverse order */
245#define WHERE_UNIQUE 0x04000000 /* Selects no more than one row */
246#define WHERE_VIRTUALTABLE 0x08000000 /* Use virtual-table processing */
247#define WHERE_MULTI_OR 0x10000000 /* OR using multiple indices */
drh51147ba2005-07-23 22:59:55 +0000248
249/*
drh0aa74ed2005-07-16 13:33:20 +0000250** Initialize a preallocated WhereClause structure.
drh75897232000-05-29 14:26:00 +0000251*/
drh7b4fc6a2007-02-06 13:26:32 +0000252static void whereClauseInit(
253 WhereClause *pWC, /* The WhereClause to be initialized */
254 Parse *pParse, /* The parsing context */
drh111a6a72008-12-21 03:51:16 +0000255 WhereMaskSet *pMaskSet /* Mapping from table cursor numbers to bitmasks */
drh7b4fc6a2007-02-06 13:26:32 +0000256){
drhfe05af82005-07-21 03:14:59 +0000257 pWC->pParse = pParse;
drh7b4fc6a2007-02-06 13:26:32 +0000258 pWC->pMaskSet = pMaskSet;
drh0aa74ed2005-07-16 13:33:20 +0000259 pWC->nTerm = 0;
drhcad651e2007-04-20 12:22:01 +0000260 pWC->nSlot = ArraySize(pWC->aStatic);
drh0aa74ed2005-07-16 13:33:20 +0000261 pWC->a = pWC->aStatic;
danielk1977e672c8e2009-05-22 15:43:26 +0000262 pWC->vmask = 0;
drh0aa74ed2005-07-16 13:33:20 +0000263}
264
drh700a2262008-12-17 19:22:15 +0000265/* Forward reference */
266static void whereClauseClear(WhereClause*);
267
268/*
269** Deallocate all memory associated with a WhereOrInfo object.
270*/
271static void whereOrInfoDelete(sqlite3 *db, WhereOrInfo *p){
drh5bd98ae2009-01-07 18:24:03 +0000272 whereClauseClear(&p->wc);
273 sqlite3DbFree(db, p);
drh700a2262008-12-17 19:22:15 +0000274}
275
276/*
277** Deallocate all memory associated with a WhereAndInfo object.
278*/
279static void whereAndInfoDelete(sqlite3 *db, WhereAndInfo *p){
drh5bd98ae2009-01-07 18:24:03 +0000280 whereClauseClear(&p->wc);
281 sqlite3DbFree(db, p);
drh700a2262008-12-17 19:22:15 +0000282}
283
drh0aa74ed2005-07-16 13:33:20 +0000284/*
285** Deallocate a WhereClause structure. The WhereClause structure
286** itself is not freed. This routine is the inverse of whereClauseInit().
287*/
288static void whereClauseClear(WhereClause *pWC){
289 int i;
290 WhereTerm *a;
drh633e6d52008-07-28 19:34:53 +0000291 sqlite3 *db = pWC->pParse->db;
drh0aa74ed2005-07-16 13:33:20 +0000292 for(i=pWC->nTerm-1, a=pWC->a; i>=0; i--, a++){
drh165be382008-12-05 02:36:33 +0000293 if( a->wtFlags & TERM_DYNAMIC ){
drh633e6d52008-07-28 19:34:53 +0000294 sqlite3ExprDelete(db, a->pExpr);
drh0aa74ed2005-07-16 13:33:20 +0000295 }
drh700a2262008-12-17 19:22:15 +0000296 if( a->wtFlags & TERM_ORINFO ){
297 whereOrInfoDelete(db, a->u.pOrInfo);
298 }else if( a->wtFlags & TERM_ANDINFO ){
299 whereAndInfoDelete(db, a->u.pAndInfo);
300 }
drh0aa74ed2005-07-16 13:33:20 +0000301 }
302 if( pWC->a!=pWC->aStatic ){
drh633e6d52008-07-28 19:34:53 +0000303 sqlite3DbFree(db, pWC->a);
drh0aa74ed2005-07-16 13:33:20 +0000304 }
305}
306
307/*
drh6a1e0712008-12-05 15:24:15 +0000308** Add a single new WhereTerm entry to the WhereClause object pWC.
309** The new WhereTerm object is constructed from Expr p and with wtFlags.
310** The index in pWC->a[] of the new WhereTerm is returned on success.
311** 0 is returned if the new WhereTerm could not be added due to a memory
312** allocation error. The memory allocation failure will be recorded in
313** the db->mallocFailed flag so that higher-level functions can detect it.
314**
315** This routine will increase the size of the pWC->a[] array as necessary.
drh9eb20282005-08-24 03:52:18 +0000316**
drh165be382008-12-05 02:36:33 +0000317** If the wtFlags argument includes TERM_DYNAMIC, then responsibility
drh6a1e0712008-12-05 15:24:15 +0000318** for freeing the expression p is assumed by the WhereClause object pWC.
319** This is true even if this routine fails to allocate a new WhereTerm.
drhb63a53d2007-03-31 01:34:44 +0000320**
drh9eb20282005-08-24 03:52:18 +0000321** WARNING: This routine might reallocate the space used to store
drh909626d2008-05-30 14:58:37 +0000322** WhereTerms. All pointers to WhereTerms should be invalidated after
drh9eb20282005-08-24 03:52:18 +0000323** calling this routine. Such pointers may be reinitialized by referencing
324** the pWC->a[] array.
drh0aa74ed2005-07-16 13:33:20 +0000325*/
drhec1724e2008-12-09 01:32:03 +0000326static int whereClauseInsert(WhereClause *pWC, Expr *p, u8 wtFlags){
drh0aa74ed2005-07-16 13:33:20 +0000327 WhereTerm *pTerm;
drh9eb20282005-08-24 03:52:18 +0000328 int idx;
drh0aa74ed2005-07-16 13:33:20 +0000329 if( pWC->nTerm>=pWC->nSlot ){
330 WhereTerm *pOld = pWC->a;
drh633e6d52008-07-28 19:34:53 +0000331 sqlite3 *db = pWC->pParse->db;
332 pWC->a = sqlite3DbMallocRaw(db, sizeof(pWC->a[0])*pWC->nSlot*2 );
drhb63a53d2007-03-31 01:34:44 +0000333 if( pWC->a==0 ){
drh165be382008-12-05 02:36:33 +0000334 if( wtFlags & TERM_DYNAMIC ){
drh633e6d52008-07-28 19:34:53 +0000335 sqlite3ExprDelete(db, p);
drhb63a53d2007-03-31 01:34:44 +0000336 }
drhf998b732007-11-26 13:36:00 +0000337 pWC->a = pOld;
drhb63a53d2007-03-31 01:34:44 +0000338 return 0;
339 }
drh0aa74ed2005-07-16 13:33:20 +0000340 memcpy(pWC->a, pOld, sizeof(pWC->a[0])*pWC->nTerm);
341 if( pOld!=pWC->aStatic ){
drh633e6d52008-07-28 19:34:53 +0000342 sqlite3DbFree(db, pOld);
drh0aa74ed2005-07-16 13:33:20 +0000343 }
drh6a1e0712008-12-05 15:24:15 +0000344 pWC->nSlot = sqlite3DbMallocSize(db, pWC->a)/sizeof(pWC->a[0]);
drh0aa74ed2005-07-16 13:33:20 +0000345 }
drh6a1e0712008-12-05 15:24:15 +0000346 pTerm = &pWC->a[idx = pWC->nTerm++];
drh0fcef5e2005-07-19 17:38:22 +0000347 pTerm->pExpr = p;
drh165be382008-12-05 02:36:33 +0000348 pTerm->wtFlags = wtFlags;
drh0fcef5e2005-07-19 17:38:22 +0000349 pTerm->pWC = pWC;
drh45b1ee42005-08-02 17:48:22 +0000350 pTerm->iParent = -1;
drh9eb20282005-08-24 03:52:18 +0000351 return idx;
drh0aa74ed2005-07-16 13:33:20 +0000352}
drh75897232000-05-29 14:26:00 +0000353
354/*
drh51669862004-12-18 18:40:26 +0000355** This routine identifies subexpressions in the WHERE clause where
drhb6fb62d2005-09-20 08:47:20 +0000356** each subexpression is separated by the AND operator or some other
drh6c30be82005-07-29 15:10:17 +0000357** operator specified in the op parameter. The WhereClause structure
358** is filled with pointers to subexpressions. For example:
drh75897232000-05-29 14:26:00 +0000359**
drh51669862004-12-18 18:40:26 +0000360** WHERE a=='hello' AND coalesce(b,11)<10 AND (c+12!=d OR c==22)
361** \________/ \_______________/ \________________/
362** slot[0] slot[1] slot[2]
363**
364** The original WHERE clause in pExpr is unaltered. All this routine
drh51147ba2005-07-23 22:59:55 +0000365** does is make slot[] entries point to substructure within pExpr.
drh51669862004-12-18 18:40:26 +0000366**
drh51147ba2005-07-23 22:59:55 +0000367** In the previous sentence and in the diagram, "slot[]" refers to
drh902b9ee2008-12-05 17:17:07 +0000368** the WhereClause.a[] array. The slot[] array grows as needed to contain
drh51147ba2005-07-23 22:59:55 +0000369** all terms of the WHERE clause.
drh75897232000-05-29 14:26:00 +0000370*/
drh6c30be82005-07-29 15:10:17 +0000371static void whereSplit(WhereClause *pWC, Expr *pExpr, int op){
drh29435252008-12-28 18:35:08 +0000372 pWC->op = (u8)op;
drh0aa74ed2005-07-16 13:33:20 +0000373 if( pExpr==0 ) return;
drh6c30be82005-07-29 15:10:17 +0000374 if( pExpr->op!=op ){
drh0aa74ed2005-07-16 13:33:20 +0000375 whereClauseInsert(pWC, pExpr, 0);
drh75897232000-05-29 14:26:00 +0000376 }else{
drh6c30be82005-07-29 15:10:17 +0000377 whereSplit(pWC, pExpr->pLeft, op);
378 whereSplit(pWC, pExpr->pRight, op);
drh75897232000-05-29 14:26:00 +0000379 }
drh75897232000-05-29 14:26:00 +0000380}
381
382/*
drh61495262009-04-22 15:32:59 +0000383** Initialize an expression mask set (a WhereMaskSet object)
drh6a3ea0e2003-05-02 14:32:12 +0000384*/
385#define initMaskSet(P) memset(P, 0, sizeof(*P))
386
387/*
drh1398ad32005-01-19 23:24:50 +0000388** Return the bitmask for the given cursor number. Return 0 if
389** iCursor is not in the set.
drh6a3ea0e2003-05-02 14:32:12 +0000390*/
drh111a6a72008-12-21 03:51:16 +0000391static Bitmask getMask(WhereMaskSet *pMaskSet, int iCursor){
drh6a3ea0e2003-05-02 14:32:12 +0000392 int i;
drh3500ed62009-05-05 15:46:43 +0000393 assert( pMaskSet->n<=sizeof(Bitmask)*8 );
drh6a3ea0e2003-05-02 14:32:12 +0000394 for(i=0; i<pMaskSet->n; i++){
drh51669862004-12-18 18:40:26 +0000395 if( pMaskSet->ix[i]==iCursor ){
396 return ((Bitmask)1)<<i;
397 }
drh6a3ea0e2003-05-02 14:32:12 +0000398 }
drh6a3ea0e2003-05-02 14:32:12 +0000399 return 0;
400}
401
402/*
drh1398ad32005-01-19 23:24:50 +0000403** Create a new mask for cursor iCursor.
drh0fcef5e2005-07-19 17:38:22 +0000404**
405** There is one cursor per table in the FROM clause. The number of
406** tables in the FROM clause is limited by a test early in the
drhb6fb62d2005-09-20 08:47:20 +0000407** sqlite3WhereBegin() routine. So we know that the pMaskSet->ix[]
drh0fcef5e2005-07-19 17:38:22 +0000408** array will never overflow.
drh1398ad32005-01-19 23:24:50 +0000409*/
drh111a6a72008-12-21 03:51:16 +0000410static void createMask(WhereMaskSet *pMaskSet, int iCursor){
drhcad651e2007-04-20 12:22:01 +0000411 assert( pMaskSet->n < ArraySize(pMaskSet->ix) );
drh0fcef5e2005-07-19 17:38:22 +0000412 pMaskSet->ix[pMaskSet->n++] = iCursor;
drh1398ad32005-01-19 23:24:50 +0000413}
414
415/*
drh75897232000-05-29 14:26:00 +0000416** This routine walks (recursively) an expression tree and generates
417** a bitmask indicating which tables are used in that expression
drh6a3ea0e2003-05-02 14:32:12 +0000418** tree.
drh75897232000-05-29 14:26:00 +0000419**
420** In order for this routine to work, the calling function must have
drh7d10d5a2008-08-20 16:35:10 +0000421** previously invoked sqlite3ResolveExprNames() on the expression. See
drh75897232000-05-29 14:26:00 +0000422** the header comment on that routine for additional information.
drh7d10d5a2008-08-20 16:35:10 +0000423** The sqlite3ResolveExprNames() routines looks for column names and
drh6a3ea0e2003-05-02 14:32:12 +0000424** sets their opcodes to TK_COLUMN and their Expr.iTable fields to
drh51147ba2005-07-23 22:59:55 +0000425** the VDBE cursor number of the table. This routine just has to
426** translate the cursor numbers into bitmask values and OR all
427** the bitmasks together.
drh75897232000-05-29 14:26:00 +0000428*/
drh111a6a72008-12-21 03:51:16 +0000429static Bitmask exprListTableUsage(WhereMaskSet*, ExprList*);
430static Bitmask exprSelectTableUsage(WhereMaskSet*, Select*);
431static Bitmask exprTableUsage(WhereMaskSet *pMaskSet, Expr *p){
drh51669862004-12-18 18:40:26 +0000432 Bitmask mask = 0;
drh75897232000-05-29 14:26:00 +0000433 if( p==0 ) return 0;
drh967e8b72000-06-21 13:59:10 +0000434 if( p->op==TK_COLUMN ){
drh8feb4b12004-07-19 02:12:14 +0000435 mask = getMask(pMaskSet, p->iTable);
drh8feb4b12004-07-19 02:12:14 +0000436 return mask;
drh75897232000-05-29 14:26:00 +0000437 }
danielk1977b3bce662005-01-29 08:32:43 +0000438 mask = exprTableUsage(pMaskSet, p->pRight);
439 mask |= exprTableUsage(pMaskSet, p->pLeft);
danielk19776ab3a2e2009-02-19 14:39:25 +0000440 if( ExprHasProperty(p, EP_xIsSelect) ){
441 mask |= exprSelectTableUsage(pMaskSet, p->x.pSelect);
442 }else{
443 mask |= exprListTableUsage(pMaskSet, p->x.pList);
444 }
danielk1977b3bce662005-01-29 08:32:43 +0000445 return mask;
446}
drh111a6a72008-12-21 03:51:16 +0000447static Bitmask exprListTableUsage(WhereMaskSet *pMaskSet, ExprList *pList){
danielk1977b3bce662005-01-29 08:32:43 +0000448 int i;
449 Bitmask mask = 0;
450 if( pList ){
451 for(i=0; i<pList->nExpr; i++){
452 mask |= exprTableUsage(pMaskSet, pList->a[i].pExpr);
drhdd579122002-04-02 01:58:57 +0000453 }
454 }
drh75897232000-05-29 14:26:00 +0000455 return mask;
456}
drh111a6a72008-12-21 03:51:16 +0000457static Bitmask exprSelectTableUsage(WhereMaskSet *pMaskSet, Select *pS){
drha430ae82007-09-12 15:41:01 +0000458 Bitmask mask = 0;
459 while( pS ){
460 mask |= exprListTableUsage(pMaskSet, pS->pEList);
drhf5b11382005-09-17 13:07:13 +0000461 mask |= exprListTableUsage(pMaskSet, pS->pGroupBy);
462 mask |= exprListTableUsage(pMaskSet, pS->pOrderBy);
463 mask |= exprTableUsage(pMaskSet, pS->pWhere);
464 mask |= exprTableUsage(pMaskSet, pS->pHaving);
drha430ae82007-09-12 15:41:01 +0000465 pS = pS->pPrior;
drhf5b11382005-09-17 13:07:13 +0000466 }
467 return mask;
468}
drh75897232000-05-29 14:26:00 +0000469
470/*
drh487ab3c2001-11-08 00:45:21 +0000471** Return TRUE if the given operator is one of the operators that is
drh51669862004-12-18 18:40:26 +0000472** allowed for an indexable WHERE clause term. The allowed operators are
drhc27a1ce2002-06-14 20:58:45 +0000473** "=", "<", ">", "<=", ">=", and "IN".
drh487ab3c2001-11-08 00:45:21 +0000474*/
475static int allowedOp(int op){
drhfe05af82005-07-21 03:14:59 +0000476 assert( TK_GT>TK_EQ && TK_GT<TK_GE );
477 assert( TK_LT>TK_EQ && TK_LT<TK_GE );
478 assert( TK_LE>TK_EQ && TK_LE<TK_GE );
479 assert( TK_GE==TK_EQ+4 );
drh50b39962006-10-28 00:28:09 +0000480 return op==TK_IN || (op>=TK_EQ && op<=TK_GE) || op==TK_ISNULL;
drh487ab3c2001-11-08 00:45:21 +0000481}
482
483/*
drh902b9ee2008-12-05 17:17:07 +0000484** Swap two objects of type TYPE.
drh193bd772004-07-20 18:23:14 +0000485*/
486#define SWAP(TYPE,A,B) {TYPE t=A; A=B; B=t;}
487
488/*
drh909626d2008-05-30 14:58:37 +0000489** Commute a comparison operator. Expressions of the form "X op Y"
drh0fcef5e2005-07-19 17:38:22 +0000490** are converted into "Y op X".
danielk1977eb5453d2007-07-30 14:40:48 +0000491**
492** If a collation sequence is associated with either the left or right
493** side of the comparison, it remains associated with the same side after
494** the commutation. So "Y collate NOCASE op X" becomes
495** "X collate NOCASE op Y". This is because any collation sequence on
496** the left hand side of a comparison overrides any collation sequence
497** attached to the right. For the same reason the EP_ExpCollate flag
498** is not commuted.
drh193bd772004-07-20 18:23:14 +0000499*/
drh7d10d5a2008-08-20 16:35:10 +0000500static void exprCommute(Parse *pParse, Expr *pExpr){
danielk1977eb5453d2007-07-30 14:40:48 +0000501 u16 expRight = (pExpr->pRight->flags & EP_ExpCollate);
502 u16 expLeft = (pExpr->pLeft->flags & EP_ExpCollate);
drhfe05af82005-07-21 03:14:59 +0000503 assert( allowedOp(pExpr->op) && pExpr->op!=TK_IN );
drh7d10d5a2008-08-20 16:35:10 +0000504 pExpr->pRight->pColl = sqlite3ExprCollSeq(pParse, pExpr->pRight);
505 pExpr->pLeft->pColl = sqlite3ExprCollSeq(pParse, pExpr->pLeft);
drh0fcef5e2005-07-19 17:38:22 +0000506 SWAP(CollSeq*,pExpr->pRight->pColl,pExpr->pLeft->pColl);
danielk1977eb5453d2007-07-30 14:40:48 +0000507 pExpr->pRight->flags = (pExpr->pRight->flags & ~EP_ExpCollate) | expLeft;
508 pExpr->pLeft->flags = (pExpr->pLeft->flags & ~EP_ExpCollate) | expRight;
drh0fcef5e2005-07-19 17:38:22 +0000509 SWAP(Expr*,pExpr->pRight,pExpr->pLeft);
510 if( pExpr->op>=TK_GT ){
511 assert( TK_LT==TK_GT+2 );
512 assert( TK_GE==TK_LE+2 );
513 assert( TK_GT>TK_EQ );
514 assert( TK_GT<TK_LE );
515 assert( pExpr->op>=TK_GT && pExpr->op<=TK_GE );
516 pExpr->op = ((pExpr->op-TK_GT)^2)+TK_GT;
drh193bd772004-07-20 18:23:14 +0000517 }
drh193bd772004-07-20 18:23:14 +0000518}
519
520/*
drhfe05af82005-07-21 03:14:59 +0000521** Translate from TK_xx operator to WO_xx bitmask.
522*/
drhec1724e2008-12-09 01:32:03 +0000523static u16 operatorMask(int op){
524 u16 c;
drhfe05af82005-07-21 03:14:59 +0000525 assert( allowedOp(op) );
526 if( op==TK_IN ){
drh51147ba2005-07-23 22:59:55 +0000527 c = WO_IN;
drh50b39962006-10-28 00:28:09 +0000528 }else if( op==TK_ISNULL ){
529 c = WO_ISNULL;
drhfe05af82005-07-21 03:14:59 +0000530 }else{
drhec1724e2008-12-09 01:32:03 +0000531 assert( (WO_EQ<<(op-TK_EQ)) < 0x7fff );
532 c = (u16)(WO_EQ<<(op-TK_EQ));
drhfe05af82005-07-21 03:14:59 +0000533 }
drh50b39962006-10-28 00:28:09 +0000534 assert( op!=TK_ISNULL || c==WO_ISNULL );
drh51147ba2005-07-23 22:59:55 +0000535 assert( op!=TK_IN || c==WO_IN );
536 assert( op!=TK_EQ || c==WO_EQ );
537 assert( op!=TK_LT || c==WO_LT );
538 assert( op!=TK_LE || c==WO_LE );
539 assert( op!=TK_GT || c==WO_GT );
540 assert( op!=TK_GE || c==WO_GE );
541 return c;
drhfe05af82005-07-21 03:14:59 +0000542}
543
544/*
545** Search for a term in the WHERE clause that is of the form "X <op> <expr>"
546** where X is a reference to the iColumn of table iCur and <op> is one of
547** the WO_xx operator codes specified by the op parameter.
548** Return a pointer to the term. Return 0 if not found.
549*/
550static WhereTerm *findTerm(
551 WhereClause *pWC, /* The WHERE clause to be searched */
552 int iCur, /* Cursor number of LHS */
553 int iColumn, /* Column number of LHS */
554 Bitmask notReady, /* RHS must not overlap with this mask */
drhec1724e2008-12-09 01:32:03 +0000555 u32 op, /* Mask of WO_xx values describing operator */
drhfe05af82005-07-21 03:14:59 +0000556 Index *pIdx /* Must be compatible with this index, if not NULL */
557){
558 WhereTerm *pTerm;
559 int k;
drh22c24032008-07-09 13:28:53 +0000560 assert( iCur>=0 );
drhec1724e2008-12-09 01:32:03 +0000561 op &= WO_ALL;
drhfe05af82005-07-21 03:14:59 +0000562 for(pTerm=pWC->a, k=pWC->nTerm; k; k--, pTerm++){
563 if( pTerm->leftCursor==iCur
564 && (pTerm->prereqRight & notReady)==0
drh700a2262008-12-17 19:22:15 +0000565 && pTerm->u.leftColumn==iColumn
drhb52076c2006-01-23 13:22:09 +0000566 && (pTerm->eOperator & op)!=0
drhfe05af82005-07-21 03:14:59 +0000567 ){
drh22c24032008-07-09 13:28:53 +0000568 if( pIdx && pTerm->eOperator!=WO_ISNULL ){
drhfe05af82005-07-21 03:14:59 +0000569 Expr *pX = pTerm->pExpr;
570 CollSeq *pColl;
571 char idxaff;
danielk1977f0113002006-01-24 12:09:17 +0000572 int j;
drhfe05af82005-07-21 03:14:59 +0000573 Parse *pParse = pWC->pParse;
574
575 idxaff = pIdx->pTable->aCol[iColumn].affinity;
576 if( !sqlite3IndexAffinityOk(pX, idxaff) ) continue;
danielk1977bcbb04e2007-05-29 12:11:29 +0000577
578 /* Figure out the collation sequence required from an index for
579 ** it to be useful for optimising expression pX. Store this
580 ** value in variable pColl.
581 */
582 assert(pX->pLeft);
583 pColl = sqlite3BinaryCompareCollSeq(pParse, pX->pLeft, pX->pRight);
danielk197793574162008-12-30 15:26:29 +0000584 assert(pColl || pParse->nErr);
danielk1977bcbb04e2007-05-29 12:11:29 +0000585
drh22c24032008-07-09 13:28:53 +0000586 for(j=0; pIdx->aiColumn[j]!=iColumn; j++){
drh34004ce2008-07-11 16:15:17 +0000587 if( NEVER(j>=pIdx->nColumn) ) return 0;
drh22c24032008-07-09 13:28:53 +0000588 }
danielk197793574162008-12-30 15:26:29 +0000589 if( pColl && sqlite3StrICmp(pColl->zName, pIdx->azColl[j]) ) continue;
drhfe05af82005-07-21 03:14:59 +0000590 }
591 return pTerm;
592 }
593 }
594 return 0;
595}
596
drh6c30be82005-07-29 15:10:17 +0000597/* Forward reference */
drh7b4fc6a2007-02-06 13:26:32 +0000598static void exprAnalyze(SrcList*, WhereClause*, int);
drh6c30be82005-07-29 15:10:17 +0000599
600/*
601** Call exprAnalyze on all terms in a WHERE clause.
602**
603**
604*/
605static void exprAnalyzeAll(
606 SrcList *pTabList, /* the FROM clause */
drh6c30be82005-07-29 15:10:17 +0000607 WhereClause *pWC /* the WHERE clause to be analyzed */
608){
drh6c30be82005-07-29 15:10:17 +0000609 int i;
drh9eb20282005-08-24 03:52:18 +0000610 for(i=pWC->nTerm-1; i>=0; i--){
drh7b4fc6a2007-02-06 13:26:32 +0000611 exprAnalyze(pTabList, pWC, i);
drh6c30be82005-07-29 15:10:17 +0000612 }
613}
614
drhd2687b72005-08-12 22:56:09 +0000615#ifndef SQLITE_OMIT_LIKE_OPTIMIZATION
616/*
617** Check to see if the given expression is a LIKE or GLOB operator that
618** can be optimized using inequality constraints. Return TRUE if it is
619** so and false if not.
620**
621** In order for the operator to be optimizible, the RHS must be a string
622** literal that does not begin with a wildcard.
623*/
624static int isLikeOrGlob(
drh7d10d5a2008-08-20 16:35:10 +0000625 Parse *pParse, /* Parsing and code generating context */
drhd2687b72005-08-12 22:56:09 +0000626 Expr *pExpr, /* Test this expression */
627 int *pnPattern, /* Number of non-wildcard prefix characters */
drh9f504ea2008-02-23 21:55:39 +0000628 int *pisComplete, /* True if the only wildcard is % in the last character */
629 int *pnoCase /* True if uppercase is equivalent to lowercase */
drhd2687b72005-08-12 22:56:09 +0000630){
drh5bd98ae2009-01-07 18:24:03 +0000631 const char *z; /* String on RHS of LIKE operator */
632 Expr *pRight, *pLeft; /* Right and left size of LIKE operator */
633 ExprList *pList; /* List of operands to the LIKE operator */
634 int c; /* One character in z[] */
635 int cnt; /* Number of non-wildcard prefix characters */
636 char wc[3]; /* Wildcard characters */
637 CollSeq *pColl; /* Collating sequence for LHS */
638 sqlite3 *db = pParse->db; /* Database connection */
drhd64fe2f2005-08-28 17:00:23 +0000639
drh9f504ea2008-02-23 21:55:39 +0000640 if( !sqlite3IsLikeFunction(db, pExpr, pnoCase, wc) ){
drhd2687b72005-08-12 22:56:09 +0000641 return 0;
642 }
drh9f504ea2008-02-23 21:55:39 +0000643#ifdef SQLITE_EBCDIC
644 if( *pnoCase ) return 0;
645#endif
danielk19776ab3a2e2009-02-19 14:39:25 +0000646 pList = pExpr->x.pList;
drh55ef4d92005-08-14 01:20:37 +0000647 pRight = pList->a[0].pExpr;
drh5bd98ae2009-01-07 18:24:03 +0000648 if( pRight->op!=TK_STRING ){
drhd2687b72005-08-12 22:56:09 +0000649 return 0;
650 }
drh55ef4d92005-08-14 01:20:37 +0000651 pLeft = pList->a[1].pExpr;
drhd2687b72005-08-12 22:56:09 +0000652 if( pLeft->op!=TK_COLUMN ){
653 return 0;
654 }
drh7d10d5a2008-08-20 16:35:10 +0000655 pColl = sqlite3ExprCollSeq(pParse, pLeft);
drh01495b92008-01-23 12:52:40 +0000656 assert( pColl!=0 || pLeft->iColumn==-1 );
drhc4ac22e2009-06-07 23:45:10 +0000657 if( pColl==0 ) return 0;
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 }
drhc4ac22e2009-06-07 23:45:10 +0000662 if( sqlite3ExprAffinity(pLeft)!=SQLITE_AFF_TEXT ) return 0;
drh33e619f2009-05-28 01:00:55 +0000663 z = pRight->u.zToken;
drhf998b732007-11-26 13:36:00 +0000664 cnt = 0;
drhc4ac22e2009-06-07 23:45:10 +0000665 if( ALWAYS(z) ){
drhb7916a72009-05-27 10:31:29 +0000666 while( (c=z[cnt])!=0 && c!=wc[0] && c!=wc[1] && c!=wc[2] ){
drh24fb6272009-05-01 21:13:36 +0000667 cnt++;
668 }
drhf998b732007-11-26 13:36:00 +0000669 }
drhb7916a72009-05-27 10:31:29 +0000670 if( cnt==0 || c==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 }
drh33e619f2009-05-28 01:00:55 +0000696 if( sqlite3StrICmp(pExpr->u.zToken,"match")!=0 ){
drh7f375902006-06-13 17:38:59 +0000697 return 0;
698 }
danielk19776ab3a2e2009-02-19 14:39:25 +0000699 pList = pExpr->x.pList;
drh7f375902006-06-13 17:38:59 +0000700 if( pList->nExpr!=2 ){
701 return 0;
702 }
703 if( pList->a[1].pExpr->op != TK_COLUMN ){
704 return 0;
705 }
706 return 1;
707}
drhedb193b2006-06-27 13:20:21 +0000708#endif /* SQLITE_OMIT_VIRTUALTABLE */
drh7f375902006-06-13 17:38:59 +0000709
710/*
drh54a167d2005-11-26 14:08:07 +0000711** If the pBase expression originated in the ON or USING clause of
712** a join, then transfer the appropriate markings over to derived.
713*/
714static void transferJoinMarkings(Expr *pDerived, Expr *pBase){
715 pDerived->flags |= pBase->flags & EP_FromJoin;
716 pDerived->iRightJoinTable = pBase->iRightJoinTable;
717}
718
drh3e355802007-02-23 23:13:33 +0000719#if !defined(SQLITE_OMIT_OR_OPTIMIZATION) && !defined(SQLITE_OMIT_SUBQUERY)
720/*
drh1a58fe02008-12-20 02:06:13 +0000721** Analyze a term that consists of two or more OR-connected
722** subterms. So in:
drh3e355802007-02-23 23:13:33 +0000723**
drh1a58fe02008-12-20 02:06:13 +0000724** ... WHERE (a=5) AND (b=7 OR c=9 OR d=13) AND (d=13)
725** ^^^^^^^^^^^^^^^^^^^^
drh3e355802007-02-23 23:13:33 +0000726**
drh1a58fe02008-12-20 02:06:13 +0000727** This routine analyzes terms such as the middle term in the above example.
728** A WhereOrTerm object is computed and attached to the term under
729** analysis, regardless of the outcome of the analysis. Hence:
drh3e355802007-02-23 23:13:33 +0000730**
drh1a58fe02008-12-20 02:06:13 +0000731** WhereTerm.wtFlags |= TERM_ORINFO
732** WhereTerm.u.pOrInfo = a dynamically allocated WhereOrTerm object
drh3e355802007-02-23 23:13:33 +0000733**
drh1a58fe02008-12-20 02:06:13 +0000734** The term being analyzed must have two or more of OR-connected subterms.
danielk1977fdc40192008-12-29 18:33:32 +0000735** A single subterm might be a set of AND-connected sub-subterms.
drh1a58fe02008-12-20 02:06:13 +0000736** Examples of terms under analysis:
drh3e355802007-02-23 23:13:33 +0000737**
drh1a58fe02008-12-20 02:06:13 +0000738** (A) t1.x=t2.y OR t1.x=t2.z OR t1.y=15 OR t1.z=t3.a+5
739** (B) x=expr1 OR expr2=x OR x=expr3
740** (C) t1.x=t2.y OR (t1.x=t2.z AND t1.y=15)
741** (D) x=expr1 OR (y>11 AND y<22 AND z LIKE '*hello*')
742** (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 +0000743**
drh1a58fe02008-12-20 02:06:13 +0000744** CASE 1:
745**
746** If all subterms are of the form T.C=expr for some single column of C
747** a single table T (as shown in example B above) then create a new virtual
748** term that is an equivalent IN expression. In other words, if the term
749** being analyzed is:
750**
751** x = expr1 OR expr2 = x OR x = expr3
752**
753** then create a new virtual term like this:
754**
755** x IN (expr1,expr2,expr3)
756**
757** CASE 2:
758**
759** If all subterms are indexable by a single table T, then set
760**
761** WhereTerm.eOperator = WO_OR
762** WhereTerm.u.pOrInfo->indexable |= the cursor number for table T
763**
764** A subterm is "indexable" if it is of the form
765** "T.C <op> <expr>" where C is any column of table T and
766** <op> is one of "=", "<", "<=", ">", ">=", "IS NULL", or "IN".
767** A subterm is also indexable if it is an AND of two or more
768** subsubterms at least one of which is indexable. Indexable AND
769** subterms have their eOperator set to WO_AND and they have
770** u.pAndInfo set to a dynamically allocated WhereAndTerm object.
771**
772** From another point of view, "indexable" means that the subterm could
773** potentially be used with an index if an appropriate index exists.
774** This analysis does not consider whether or not the index exists; that
775** is something the bestIndex() routine will determine. This analysis
776** only looks at whether subterms appropriate for indexing exist.
777**
778** All examples A through E above all satisfy case 2. But if a term
779** also statisfies case 1 (such as B) we know that the optimizer will
780** always prefer case 1, so in that case we pretend that case 2 is not
781** satisfied.
782**
783** It might be the case that multiple tables are indexable. For example,
784** (E) above is indexable on tables P, Q, and R.
785**
786** Terms that satisfy case 2 are candidates for lookup by using
787** separate indices to find rowids for each subterm and composing
788** the union of all rowids using a RowSet object. This is similar
789** to "bitmap indices" in other database engines.
790**
791** OTHERWISE:
792**
793** If neither case 1 nor case 2 apply, then leave the eOperator set to
794** zero. This term is not useful for search.
drh3e355802007-02-23 23:13:33 +0000795*/
drh1a58fe02008-12-20 02:06:13 +0000796static void exprAnalyzeOrTerm(
797 SrcList *pSrc, /* the FROM clause */
798 WhereClause *pWC, /* the complete WHERE clause */
799 int idxTerm /* Index of the OR-term to be analyzed */
800){
801 Parse *pParse = pWC->pParse; /* Parser context */
802 sqlite3 *db = pParse->db; /* Database connection */
803 WhereTerm *pTerm = &pWC->a[idxTerm]; /* The term to be analyzed */
804 Expr *pExpr = pTerm->pExpr; /* The expression of the term */
drh111a6a72008-12-21 03:51:16 +0000805 WhereMaskSet *pMaskSet = pWC->pMaskSet; /* Table use masks */
drh1a58fe02008-12-20 02:06:13 +0000806 int i; /* Loop counters */
807 WhereClause *pOrWc; /* Breakup of pTerm into subterms */
808 WhereTerm *pOrTerm; /* A Sub-term within the pOrWc */
809 WhereOrInfo *pOrInfo; /* Additional information associated with pTerm */
810 Bitmask chngToIN; /* Tables that might satisfy case 1 */
811 Bitmask indexable; /* Tables that are indexable, satisfying case 2 */
drh3e355802007-02-23 23:13:33 +0000812
drh1a58fe02008-12-20 02:06:13 +0000813 /*
814 ** Break the OR clause into its separate subterms. The subterms are
815 ** stored in a WhereClause structure containing within the WhereOrInfo
816 ** object that is attached to the original OR clause term.
817 */
818 assert( (pTerm->wtFlags & (TERM_DYNAMIC|TERM_ORINFO|TERM_ANDINFO))==0 );
819 assert( pExpr->op==TK_OR );
drh954701a2008-12-29 23:45:07 +0000820 pTerm->u.pOrInfo = pOrInfo = sqlite3DbMallocZero(db, sizeof(*pOrInfo));
drh1a58fe02008-12-20 02:06:13 +0000821 if( pOrInfo==0 ) return;
822 pTerm->wtFlags |= TERM_ORINFO;
823 pOrWc = &pOrInfo->wc;
824 whereClauseInit(pOrWc, pWC->pParse, pMaskSet);
825 whereSplit(pOrWc, pExpr, TK_OR);
826 exprAnalyzeAll(pSrc, pOrWc);
827 if( db->mallocFailed ) return;
828 assert( pOrWc->nTerm>=2 );
829
830 /*
831 ** Compute the set of tables that might satisfy cases 1 or 2.
832 */
danielk1977e672c8e2009-05-22 15:43:26 +0000833 indexable = ~(Bitmask)0;
834 chngToIN = ~(pWC->vmask);
drh1a58fe02008-12-20 02:06:13 +0000835 for(i=pOrWc->nTerm-1, pOrTerm=pOrWc->a; i>=0 && indexable; i--, pOrTerm++){
836 if( (pOrTerm->eOperator & WO_SINGLE)==0 ){
drh29435252008-12-28 18:35:08 +0000837 WhereAndInfo *pAndInfo;
838 assert( pOrTerm->eOperator==0 );
839 assert( (pOrTerm->wtFlags & (TERM_ANDINFO|TERM_ORINFO))==0 );
drh1a58fe02008-12-20 02:06:13 +0000840 chngToIN = 0;
drh29435252008-12-28 18:35:08 +0000841 pAndInfo = sqlite3DbMallocRaw(db, sizeof(*pAndInfo));
842 if( pAndInfo ){
843 WhereClause *pAndWC;
844 WhereTerm *pAndTerm;
845 int j;
846 Bitmask b = 0;
847 pOrTerm->u.pAndInfo = pAndInfo;
848 pOrTerm->wtFlags |= TERM_ANDINFO;
849 pOrTerm->eOperator = WO_AND;
850 pAndWC = &pAndInfo->wc;
851 whereClauseInit(pAndWC, pWC->pParse, pMaskSet);
852 whereSplit(pAndWC, pOrTerm->pExpr, TK_AND);
853 exprAnalyzeAll(pSrc, pAndWC);
drh7c2fbde2009-01-07 20:58:57 +0000854 testcase( db->mallocFailed );
drh96c7a7d2009-01-10 15:34:12 +0000855 if( !db->mallocFailed ){
856 for(j=0, pAndTerm=pAndWC->a; j<pAndWC->nTerm; j++, pAndTerm++){
857 assert( pAndTerm->pExpr );
858 if( allowedOp(pAndTerm->pExpr->op) ){
859 b |= getMask(pMaskSet, pAndTerm->leftCursor);
860 }
drh29435252008-12-28 18:35:08 +0000861 }
862 }
863 indexable &= b;
864 }
drh1a58fe02008-12-20 02:06:13 +0000865 }else if( pOrTerm->wtFlags & TERM_COPIED ){
866 /* Skip this term for now. We revisit it when we process the
867 ** corresponding TERM_VIRTUAL term */
868 }else{
869 Bitmask b;
870 b = getMask(pMaskSet, pOrTerm->leftCursor);
871 if( pOrTerm->wtFlags & TERM_VIRTUAL ){
872 WhereTerm *pOther = &pOrWc->a[pOrTerm->iParent];
873 b |= getMask(pMaskSet, pOther->leftCursor);
874 }
875 indexable &= b;
876 if( pOrTerm->eOperator!=WO_EQ ){
877 chngToIN = 0;
878 }else{
879 chngToIN &= b;
880 }
881 }
drh3e355802007-02-23 23:13:33 +0000882 }
drh1a58fe02008-12-20 02:06:13 +0000883
884 /*
885 ** Record the set of tables that satisfy case 2. The set might be
drh111a6a72008-12-21 03:51:16 +0000886 ** empty.
drh1a58fe02008-12-20 02:06:13 +0000887 */
888 pOrInfo->indexable = indexable;
drh111a6a72008-12-21 03:51:16 +0000889 pTerm->eOperator = indexable==0 ? 0 : WO_OR;
drh1a58fe02008-12-20 02:06:13 +0000890
891 /*
892 ** chngToIN holds a set of tables that *might* satisfy case 1. But
893 ** we have to do some additional checking to see if case 1 really
894 ** is satisfied.
drh4e8be3b2009-06-08 17:11:08 +0000895 **
896 ** chngToIN will hold either 0, 1, or 2 bits. The 0-bit case means
897 ** that there is no possibility of transforming the OR clause into an
898 ** IN operator because one or more terms in the OR clause contain
899 ** something other than == on a column in the single table. The 1-bit
900 ** case means that every term of the OR clause is of the form
901 ** "table.column=expr" for some single table. The one bit that is set
902 ** will correspond to the common table. We still need to check to make
903 ** sure the same column is used on all terms. The 2-bit case is when
904 ** the all terms are of the form "table1.column=table2.column". It
905 ** might be possible to form an IN operator with either table1.column
906 ** or table2.column as the LHS if either is common to every term of
907 ** the OR clause.
908 **
909 ** Note that terms of the form "table.column1=table.column2" (the
910 ** same table on both sizes of the ==) cannot be optimized.
drh1a58fe02008-12-20 02:06:13 +0000911 */
912 if( chngToIN ){
913 int okToChngToIN = 0; /* True if the conversion to IN is valid */
914 int iColumn = -1; /* Column index on lhs of IN operator */
shane63207ab2009-02-04 01:49:30 +0000915 int iCursor = -1; /* Table cursor common to all terms */
drh1a58fe02008-12-20 02:06:13 +0000916 int j = 0; /* Loop counter */
917
918 /* Search for a table and column that appears on one side or the
919 ** other of the == operator in every subterm. That table and column
920 ** will be recorded in iCursor and iColumn. There might not be any
921 ** such table and column. Set okToChngToIN if an appropriate table
922 ** and column is found but leave okToChngToIN false if not found.
923 */
924 for(j=0; j<2 && !okToChngToIN; j++){
925 pOrTerm = pOrWc->a;
926 for(i=pOrWc->nTerm-1; i>=0; i--, pOrTerm++){
927 assert( pOrTerm->eOperator==WO_EQ );
928 pOrTerm->wtFlags &= ~TERM_OR_OK;
drh4e8be3b2009-06-08 17:11:08 +0000929 if( pOrTerm->leftCursor==iCursor ){
930 /* This is the 2-bit case and we are on the second iteration and
931 ** current term is from the first iteration. So skip this term. */
932 assert( j==1 );
933 continue;
934 }
935 if( (chngToIN & getMask(pMaskSet, pOrTerm->leftCursor))==0 ){
936 /* This term must be of the form t1.a==t2.b where t2 is in the
937 ** chngToIN set but t1 is not. This term will be either preceeded
938 ** or follwed by an inverted copy (t2.b==t1.a). Skip this term
939 ** and use its inversion. */
940 testcase( pOrTerm->wtFlags & TERM_COPIED );
941 testcase( pOrTerm->wtFlags & TERM_VIRTUAL );
942 assert( pOrTerm->wtFlags & (TERM_COPIED|TERM_VIRTUAL) );
943 continue;
944 }
drh1a58fe02008-12-20 02:06:13 +0000945 iColumn = pOrTerm->u.leftColumn;
946 iCursor = pOrTerm->leftCursor;
947 break;
948 }
949 if( i<0 ){
drh4e8be3b2009-06-08 17:11:08 +0000950 /* No candidate table+column was found. This can only occur
951 ** on the second iteration */
drh1a58fe02008-12-20 02:06:13 +0000952 assert( j==1 );
953 assert( (chngToIN&(chngToIN-1))==0 );
drh4e8be3b2009-06-08 17:11:08 +0000954 assert( chngToIN==getMask(pMaskSet, iCursor) );
drh1a58fe02008-12-20 02:06:13 +0000955 break;
956 }
drh4e8be3b2009-06-08 17:11:08 +0000957 testcase( j==1 );
958
959 /* We have found a candidate table and column. Check to see if that
960 ** table and column is common to every term in the OR clause */
drh1a58fe02008-12-20 02:06:13 +0000961 okToChngToIN = 1;
962 for(; i>=0 && okToChngToIN; i--, pOrTerm++){
963 assert( pOrTerm->eOperator==WO_EQ );
964 if( pOrTerm->leftCursor!=iCursor ){
965 pOrTerm->wtFlags &= ~TERM_OR_OK;
966 }else if( pOrTerm->u.leftColumn!=iColumn ){
967 okToChngToIN = 0;
968 }else{
969 int affLeft, affRight;
970 /* If the right-hand side is also a column, then the affinities
971 ** of both right and left sides must be such that no type
972 ** conversions are required on the right. (Ticket #2249)
973 */
974 affRight = sqlite3ExprAffinity(pOrTerm->pExpr->pRight);
975 affLeft = sqlite3ExprAffinity(pOrTerm->pExpr->pLeft);
976 if( affRight!=0 && affRight!=affLeft ){
977 okToChngToIN = 0;
978 }else{
979 pOrTerm->wtFlags |= TERM_OR_OK;
980 }
981 }
982 }
983 }
984
985 /* At this point, okToChngToIN is true if original pTerm satisfies
986 ** case 1. In that case, construct a new virtual term that is
987 ** pTerm converted into an IN operator.
988 */
989 if( okToChngToIN ){
990 Expr *pDup; /* A transient duplicate expression */
991 ExprList *pList = 0; /* The RHS of the IN operator */
992 Expr *pLeft = 0; /* The LHS of the IN operator */
993 Expr *pNew; /* The complete IN operator */
994
995 for(i=pOrWc->nTerm-1, pOrTerm=pOrWc->a; i>=0; i--, pOrTerm++){
996 if( (pOrTerm->wtFlags & TERM_OR_OK)==0 ) continue;
997 assert( pOrTerm->eOperator==WO_EQ );
998 assert( pOrTerm->leftCursor==iCursor );
999 assert( pOrTerm->u.leftColumn==iColumn );
danielk19776ab3a2e2009-02-19 14:39:25 +00001000 pDup = sqlite3ExprDup(db, pOrTerm->pExpr->pRight, 0);
drhb7916a72009-05-27 10:31:29 +00001001 pList = sqlite3ExprListAppend(pWC->pParse, pList, pDup);
drh1a58fe02008-12-20 02:06:13 +00001002 pLeft = pOrTerm->pExpr->pLeft;
1003 }
1004 assert( pLeft!=0 );
danielk19776ab3a2e2009-02-19 14:39:25 +00001005 pDup = sqlite3ExprDup(db, pLeft, 0);
drhb7916a72009-05-27 10:31:29 +00001006 pNew = sqlite3PExpr(pParse, TK_IN, pDup, 0, 0);
drh1a58fe02008-12-20 02:06:13 +00001007 if( pNew ){
1008 int idxNew;
1009 transferJoinMarkings(pNew, pExpr);
danielk19776ab3a2e2009-02-19 14:39:25 +00001010 assert( !ExprHasProperty(pNew, EP_xIsSelect) );
1011 pNew->x.pList = pList;
drh1a58fe02008-12-20 02:06:13 +00001012 idxNew = whereClauseInsert(pWC, pNew, TERM_VIRTUAL|TERM_DYNAMIC);
1013 testcase( idxNew==0 );
1014 exprAnalyze(pSrc, pWC, idxNew);
1015 pTerm = &pWC->a[idxTerm];
1016 pWC->a[idxNew].iParent = idxTerm;
1017 pTerm->nChild = 1;
1018 }else{
1019 sqlite3ExprListDelete(db, pList);
1020 }
1021 pTerm->eOperator = 0; /* case 1 trumps case 2 */
1022 }
drh3e355802007-02-23 23:13:33 +00001023 }
drh3e355802007-02-23 23:13:33 +00001024}
1025#endif /* !SQLITE_OMIT_OR_OPTIMIZATION && !SQLITE_OMIT_SUBQUERY */
drh54a167d2005-11-26 14:08:07 +00001026
drh1a58fe02008-12-20 02:06:13 +00001027
drh54a167d2005-11-26 14:08:07 +00001028/*
drh0aa74ed2005-07-16 13:33:20 +00001029** The input to this routine is an WhereTerm structure with only the
drh51147ba2005-07-23 22:59:55 +00001030** "pExpr" field filled in. The job of this routine is to analyze the
drh0aa74ed2005-07-16 13:33:20 +00001031** subexpression and populate all the other fields of the WhereTerm
drh75897232000-05-29 14:26:00 +00001032** structure.
drh51147ba2005-07-23 22:59:55 +00001033**
1034** If the expression is of the form "<expr> <op> X" it gets commuted
drh1a58fe02008-12-20 02:06:13 +00001035** to the standard form of "X <op> <expr>".
1036**
1037** If the expression is of the form "X <op> Y" where both X and Y are
1038** columns, then the original expression is unchanged and a new virtual
1039** term of the form "Y <op> X" is added to the WHERE clause and
1040** analyzed separately. The original term is marked with TERM_COPIED
1041** and the new term is marked with TERM_DYNAMIC (because it's pExpr
1042** needs to be freed with the WhereClause) and TERM_VIRTUAL (because it
1043** is a commuted copy of a prior term.) The original term has nChild=1
1044** and the copy has idxParent set to the index of the original term.
drh75897232000-05-29 14:26:00 +00001045*/
drh0fcef5e2005-07-19 17:38:22 +00001046static void exprAnalyze(
1047 SrcList *pSrc, /* the FROM clause */
drh9eb20282005-08-24 03:52:18 +00001048 WhereClause *pWC, /* the WHERE clause */
1049 int idxTerm /* Index of the term to be analyzed */
drh0fcef5e2005-07-19 17:38:22 +00001050){
drh1a58fe02008-12-20 02:06:13 +00001051 WhereTerm *pTerm; /* The term to be analyzed */
drh111a6a72008-12-21 03:51:16 +00001052 WhereMaskSet *pMaskSet; /* Set of table index masks */
drh1a58fe02008-12-20 02:06:13 +00001053 Expr *pExpr; /* The expression to be analyzed */
1054 Bitmask prereqLeft; /* Prerequesites of the pExpr->pLeft */
1055 Bitmask prereqAll; /* Prerequesites of pExpr */
drhdafc0ce2008-04-17 19:14:02 +00001056 Bitmask extraRight = 0;
drhd2687b72005-08-12 22:56:09 +00001057 int nPattern;
1058 int isComplete;
drh9f504ea2008-02-23 21:55:39 +00001059 int noCase;
drh1a58fe02008-12-20 02:06:13 +00001060 int op; /* Top-level operator. pExpr->op */
1061 Parse *pParse = pWC->pParse; /* Parsing context */
1062 sqlite3 *db = pParse->db; /* Database connection */
drh0fcef5e2005-07-19 17:38:22 +00001063
drhf998b732007-11-26 13:36:00 +00001064 if( db->mallocFailed ){
1065 return;
1066 }
1067 pTerm = &pWC->a[idxTerm];
1068 pMaskSet = pWC->pMaskSet;
1069 pExpr = pTerm->pExpr;
drh0fcef5e2005-07-19 17:38:22 +00001070 prereqLeft = exprTableUsage(pMaskSet, pExpr->pLeft);
drh50b39962006-10-28 00:28:09 +00001071 op = pExpr->op;
1072 if( op==TK_IN ){
drhf5b11382005-09-17 13:07:13 +00001073 assert( pExpr->pRight==0 );
danielk19776ab3a2e2009-02-19 14:39:25 +00001074 if( ExprHasProperty(pExpr, EP_xIsSelect) ){
1075 pTerm->prereqRight = exprSelectTableUsage(pMaskSet, pExpr->x.pSelect);
1076 }else{
1077 pTerm->prereqRight = exprListTableUsage(pMaskSet, pExpr->x.pList);
1078 }
drh50b39962006-10-28 00:28:09 +00001079 }else if( op==TK_ISNULL ){
1080 pTerm->prereqRight = 0;
drhf5b11382005-09-17 13:07:13 +00001081 }else{
1082 pTerm->prereqRight = exprTableUsage(pMaskSet, pExpr->pRight);
1083 }
drh22d6a532005-09-19 21:05:48 +00001084 prereqAll = exprTableUsage(pMaskSet, pExpr);
1085 if( ExprHasProperty(pExpr, EP_FromJoin) ){
drh42165be2008-03-26 14:56:34 +00001086 Bitmask x = getMask(pMaskSet, pExpr->iRightJoinTable);
1087 prereqAll |= x;
drhdafc0ce2008-04-17 19:14:02 +00001088 extraRight = x-1; /* ON clause terms may not be used with an index
1089 ** on left table of a LEFT JOIN. Ticket #3015 */
drh22d6a532005-09-19 21:05:48 +00001090 }
1091 pTerm->prereqAll = prereqAll;
drh0fcef5e2005-07-19 17:38:22 +00001092 pTerm->leftCursor = -1;
drh45b1ee42005-08-02 17:48:22 +00001093 pTerm->iParent = -1;
drhb52076c2006-01-23 13:22:09 +00001094 pTerm->eOperator = 0;
drh50b39962006-10-28 00:28:09 +00001095 if( allowedOp(op) && (pTerm->prereqRight & prereqLeft)==0 ){
drh0fcef5e2005-07-19 17:38:22 +00001096 Expr *pLeft = pExpr->pLeft;
1097 Expr *pRight = pExpr->pRight;
1098 if( pLeft->op==TK_COLUMN ){
1099 pTerm->leftCursor = pLeft->iTable;
drh700a2262008-12-17 19:22:15 +00001100 pTerm->u.leftColumn = pLeft->iColumn;
drh50b39962006-10-28 00:28:09 +00001101 pTerm->eOperator = operatorMask(op);
drh75897232000-05-29 14:26:00 +00001102 }
drh0fcef5e2005-07-19 17:38:22 +00001103 if( pRight && pRight->op==TK_COLUMN ){
1104 WhereTerm *pNew;
1105 Expr *pDup;
1106 if( pTerm->leftCursor>=0 ){
drh9eb20282005-08-24 03:52:18 +00001107 int idxNew;
danielk19776ab3a2e2009-02-19 14:39:25 +00001108 pDup = sqlite3ExprDup(db, pExpr, 0);
drh17435752007-08-16 04:30:38 +00001109 if( db->mallocFailed ){
drh633e6d52008-07-28 19:34:53 +00001110 sqlite3ExprDelete(db, pDup);
drh28f45912006-10-18 23:26:38 +00001111 return;
1112 }
drh9eb20282005-08-24 03:52:18 +00001113 idxNew = whereClauseInsert(pWC, pDup, TERM_VIRTUAL|TERM_DYNAMIC);
1114 if( idxNew==0 ) return;
1115 pNew = &pWC->a[idxNew];
1116 pNew->iParent = idxTerm;
1117 pTerm = &pWC->a[idxTerm];
drh45b1ee42005-08-02 17:48:22 +00001118 pTerm->nChild = 1;
drh165be382008-12-05 02:36:33 +00001119 pTerm->wtFlags |= TERM_COPIED;
drh0fcef5e2005-07-19 17:38:22 +00001120 }else{
1121 pDup = pExpr;
1122 pNew = pTerm;
1123 }
drh7d10d5a2008-08-20 16:35:10 +00001124 exprCommute(pParse, pDup);
drh0fcef5e2005-07-19 17:38:22 +00001125 pLeft = pDup->pLeft;
1126 pNew->leftCursor = pLeft->iTable;
drh700a2262008-12-17 19:22:15 +00001127 pNew->u.leftColumn = pLeft->iColumn;
drh0fcef5e2005-07-19 17:38:22 +00001128 pNew->prereqRight = prereqLeft;
1129 pNew->prereqAll = prereqAll;
drhb52076c2006-01-23 13:22:09 +00001130 pNew->eOperator = operatorMask(pDup->op);
drh75897232000-05-29 14:26:00 +00001131 }
1132 }
drhed378002005-07-28 23:12:08 +00001133
drhd2687b72005-08-12 22:56:09 +00001134#ifndef SQLITE_OMIT_BETWEEN_OPTIMIZATION
drhed378002005-07-28 23:12:08 +00001135 /* If a term is the BETWEEN operator, create two new virtual terms
drh1a58fe02008-12-20 02:06:13 +00001136 ** that define the range that the BETWEEN implements. For example:
1137 **
1138 ** a BETWEEN b AND c
1139 **
1140 ** is converted into:
1141 **
1142 ** (a BETWEEN b AND c) AND (a>=b) AND (a<=c)
1143 **
1144 ** The two new terms are added onto the end of the WhereClause object.
1145 ** The new terms are "dynamic" and are children of the original BETWEEN
1146 ** term. That means that if the BETWEEN term is coded, the children are
1147 ** skipped. Or, if the children are satisfied by an index, the original
1148 ** BETWEEN term is skipped.
drhed378002005-07-28 23:12:08 +00001149 */
drh29435252008-12-28 18:35:08 +00001150 else if( pExpr->op==TK_BETWEEN && pWC->op==TK_AND ){
danielk19776ab3a2e2009-02-19 14:39:25 +00001151 ExprList *pList = pExpr->x.pList;
drhed378002005-07-28 23:12:08 +00001152 int i;
1153 static const u8 ops[] = {TK_GE, TK_LE};
1154 assert( pList!=0 );
1155 assert( pList->nExpr==2 );
1156 for(i=0; i<2; i++){
1157 Expr *pNewExpr;
drh9eb20282005-08-24 03:52:18 +00001158 int idxNew;
drhb7916a72009-05-27 10:31:29 +00001159 pNewExpr = sqlite3PExpr(pParse, ops[i],
1160 sqlite3ExprDup(db, pExpr->pLeft, 0),
danielk19776ab3a2e2009-02-19 14:39:25 +00001161 sqlite3ExprDup(db, pList->a[i].pExpr, 0), 0);
drh9eb20282005-08-24 03:52:18 +00001162 idxNew = whereClauseInsert(pWC, pNewExpr, TERM_VIRTUAL|TERM_DYNAMIC);
drh6a1e0712008-12-05 15:24:15 +00001163 testcase( idxNew==0 );
drh7b4fc6a2007-02-06 13:26:32 +00001164 exprAnalyze(pSrc, pWC, idxNew);
drh9eb20282005-08-24 03:52:18 +00001165 pTerm = &pWC->a[idxTerm];
1166 pWC->a[idxNew].iParent = idxTerm;
drhed378002005-07-28 23:12:08 +00001167 }
drh45b1ee42005-08-02 17:48:22 +00001168 pTerm->nChild = 2;
drhed378002005-07-28 23:12:08 +00001169 }
drhd2687b72005-08-12 22:56:09 +00001170#endif /* SQLITE_OMIT_BETWEEN_OPTIMIZATION */
drhed378002005-07-28 23:12:08 +00001171
danielk19771576cd92006-01-14 08:02:28 +00001172#if !defined(SQLITE_OMIT_OR_OPTIMIZATION) && !defined(SQLITE_OMIT_SUBQUERY)
drh1a58fe02008-12-20 02:06:13 +00001173 /* Analyze a term that is composed of two or more subterms connected by
1174 ** an OR operator.
drh6c30be82005-07-29 15:10:17 +00001175 */
1176 else if( pExpr->op==TK_OR ){
drh29435252008-12-28 18:35:08 +00001177 assert( pWC->op==TK_AND );
drh1a58fe02008-12-20 02:06:13 +00001178 exprAnalyzeOrTerm(pSrc, pWC, idxTerm);
drh6c30be82005-07-29 15:10:17 +00001179 }
drhd2687b72005-08-12 22:56:09 +00001180#endif /* SQLITE_OMIT_OR_OPTIMIZATION */
1181
1182#ifndef SQLITE_OMIT_LIKE_OPTIMIZATION
1183 /* Add constraints to reduce the search space on a LIKE or GLOB
1184 ** operator.
drh9f504ea2008-02-23 21:55:39 +00001185 **
1186 ** A like pattern of the form "x LIKE 'abc%'" is changed into constraints
1187 **
1188 ** x>='abc' AND x<'abd' AND x LIKE 'abc%'
1189 **
1190 ** The last character of the prefix "abc" is incremented to form the
shane7bc71e52008-05-28 18:01:44 +00001191 ** termination condition "abd".
drhd2687b72005-08-12 22:56:09 +00001192 */
drh29435252008-12-28 18:35:08 +00001193 if( isLikeOrGlob(pParse, pExpr, &nPattern, &isComplete, &noCase)
1194 && pWC->op==TK_AND ){
drhd2687b72005-08-12 22:56:09 +00001195 Expr *pLeft, *pRight;
1196 Expr *pStr1, *pStr2;
1197 Expr *pNewExpr1, *pNewExpr2;
drh9eb20282005-08-24 03:52:18 +00001198 int idxNew1, idxNew2;
1199
danielk19776ab3a2e2009-02-19 14:39:25 +00001200 pLeft = pExpr->x.pList->a[1].pExpr;
1201 pRight = pExpr->x.pList->a[0].pExpr;
drh33e619f2009-05-28 01:00:55 +00001202 pStr1 = sqlite3Expr(db, TK_STRING, pRight->u.zToken);
1203 if( pStr1 ) pStr1->u.zToken[nPattern] = 0;
danielk19776ab3a2e2009-02-19 14:39:25 +00001204 pStr2 = sqlite3ExprDup(db, pStr1, 0);
drhf998b732007-11-26 13:36:00 +00001205 if( !db->mallocFailed ){
drh9f504ea2008-02-23 21:55:39 +00001206 u8 c, *pC;
drh33e619f2009-05-28 01:00:55 +00001207 pC = (u8*)&pStr2->u.zToken[nPattern-1];
drh9f504ea2008-02-23 21:55:39 +00001208 c = *pC;
drh02a50b72008-05-26 18:33:40 +00001209 if( noCase ){
1210 if( c=='@' ) isComplete = 0;
1211 c = sqlite3UpperToLower[c];
1212 }
drh9f504ea2008-02-23 21:55:39 +00001213 *pC = c + 1;
drhd2687b72005-08-12 22:56:09 +00001214 }
danielk19776ab3a2e2009-02-19 14:39:25 +00001215 pNewExpr1 = sqlite3PExpr(pParse, TK_GE, sqlite3ExprDup(db,pLeft,0),pStr1,0);
drh9eb20282005-08-24 03:52:18 +00001216 idxNew1 = whereClauseInsert(pWC, pNewExpr1, TERM_VIRTUAL|TERM_DYNAMIC);
drh6a1e0712008-12-05 15:24:15 +00001217 testcase( idxNew1==0 );
drh7b4fc6a2007-02-06 13:26:32 +00001218 exprAnalyze(pSrc, pWC, idxNew1);
danielk19776ab3a2e2009-02-19 14:39:25 +00001219 pNewExpr2 = sqlite3PExpr(pParse, TK_LT, sqlite3ExprDup(db,pLeft,0),pStr2,0);
drh9eb20282005-08-24 03:52:18 +00001220 idxNew2 = whereClauseInsert(pWC, pNewExpr2, TERM_VIRTUAL|TERM_DYNAMIC);
drh6a1e0712008-12-05 15:24:15 +00001221 testcase( idxNew2==0 );
drh7b4fc6a2007-02-06 13:26:32 +00001222 exprAnalyze(pSrc, pWC, idxNew2);
drh9eb20282005-08-24 03:52:18 +00001223 pTerm = &pWC->a[idxTerm];
drhd2687b72005-08-12 22:56:09 +00001224 if( isComplete ){
drh9eb20282005-08-24 03:52:18 +00001225 pWC->a[idxNew1].iParent = idxTerm;
1226 pWC->a[idxNew2].iParent = idxTerm;
drhd2687b72005-08-12 22:56:09 +00001227 pTerm->nChild = 2;
1228 }
1229 }
1230#endif /* SQLITE_OMIT_LIKE_OPTIMIZATION */
drh7f375902006-06-13 17:38:59 +00001231
1232#ifndef SQLITE_OMIT_VIRTUALTABLE
1233 /* Add a WO_MATCH auxiliary term to the constraint set if the
1234 ** current expression is of the form: column MATCH expr.
1235 ** This information is used by the xBestIndex methods of
1236 ** virtual tables. The native query optimizer does not attempt
1237 ** to do anything with MATCH functions.
1238 */
1239 if( isMatchOfColumn(pExpr) ){
1240 int idxNew;
1241 Expr *pRight, *pLeft;
1242 WhereTerm *pNewTerm;
1243 Bitmask prereqColumn, prereqExpr;
1244
danielk19776ab3a2e2009-02-19 14:39:25 +00001245 pRight = pExpr->x.pList->a[0].pExpr;
1246 pLeft = pExpr->x.pList->a[1].pExpr;
drh7f375902006-06-13 17:38:59 +00001247 prereqExpr = exprTableUsage(pMaskSet, pRight);
1248 prereqColumn = exprTableUsage(pMaskSet, pLeft);
1249 if( (prereqExpr & prereqColumn)==0 ){
drh1a90e092006-06-14 22:07:10 +00001250 Expr *pNewExpr;
drhb7916a72009-05-27 10:31:29 +00001251 pNewExpr = sqlite3PExpr(pParse, TK_MATCH,
1252 0, sqlite3ExprDup(db, pRight, 0), 0);
drh1a90e092006-06-14 22:07:10 +00001253 idxNew = whereClauseInsert(pWC, pNewExpr, TERM_VIRTUAL|TERM_DYNAMIC);
drh6a1e0712008-12-05 15:24:15 +00001254 testcase( idxNew==0 );
drh7f375902006-06-13 17:38:59 +00001255 pNewTerm = &pWC->a[idxNew];
1256 pNewTerm->prereqRight = prereqExpr;
1257 pNewTerm->leftCursor = pLeft->iTable;
drh700a2262008-12-17 19:22:15 +00001258 pNewTerm->u.leftColumn = pLeft->iColumn;
drh7f375902006-06-13 17:38:59 +00001259 pNewTerm->eOperator = WO_MATCH;
1260 pNewTerm->iParent = idxTerm;
drhd2ca60d2006-06-27 02:36:58 +00001261 pTerm = &pWC->a[idxTerm];
drh7f375902006-06-13 17:38:59 +00001262 pTerm->nChild = 1;
drh165be382008-12-05 02:36:33 +00001263 pTerm->wtFlags |= TERM_COPIED;
drh7f375902006-06-13 17:38:59 +00001264 pNewTerm->prereqAll = pTerm->prereqAll;
1265 }
1266 }
1267#endif /* SQLITE_OMIT_VIRTUALTABLE */
drhdafc0ce2008-04-17 19:14:02 +00001268
1269 /* Prevent ON clause terms of a LEFT JOIN from being used to drive
1270 ** an index for tables to the left of the join.
1271 */
1272 pTerm->prereqRight |= extraRight;
drh75897232000-05-29 14:26:00 +00001273}
1274
drh7b4fc6a2007-02-06 13:26:32 +00001275/*
1276** Return TRUE if any of the expressions in pList->a[iFirst...] contain
1277** a reference to any table other than the iBase table.
1278*/
1279static int referencesOtherTables(
1280 ExprList *pList, /* Search expressions in ths list */
drh111a6a72008-12-21 03:51:16 +00001281 WhereMaskSet *pMaskSet, /* Mapping from tables to bitmaps */
drh7b4fc6a2007-02-06 13:26:32 +00001282 int iFirst, /* Be searching with the iFirst-th expression */
1283 int iBase /* Ignore references to this table */
1284){
1285 Bitmask allowed = ~getMask(pMaskSet, iBase);
1286 while( iFirst<pList->nExpr ){
1287 if( (exprTableUsage(pMaskSet, pList->a[iFirst++].pExpr)&allowed)!=0 ){
1288 return 1;
1289 }
1290 }
1291 return 0;
1292}
1293
drh0fcef5e2005-07-19 17:38:22 +00001294
drh75897232000-05-29 14:26:00 +00001295/*
drh51669862004-12-18 18:40:26 +00001296** This routine decides if pIdx can be used to satisfy the ORDER BY
1297** clause. If it can, it returns 1. If pIdx cannot satisfy the
1298** ORDER BY clause, this routine returns 0.
1299**
1300** pOrderBy is an ORDER BY clause from a SELECT statement. pTab is the
1301** left-most table in the FROM clause of that same SELECT statement and
1302** the table has a cursor number of "base". pIdx is an index on pTab.
1303**
1304** nEqCol is the number of columns of pIdx that are used as equality
1305** constraints. Any of these columns may be missing from the ORDER BY
1306** clause and the match can still be a success.
1307**
drh51669862004-12-18 18:40:26 +00001308** All terms of the ORDER BY that match against the index must be either
1309** ASC or DESC. (Terms of the ORDER BY clause past the end of a UNIQUE
1310** index do not need to satisfy this constraint.) The *pbRev value is
1311** set to 1 if the ORDER BY clause is all DESC and it is set to 0 if
1312** the ORDER BY clause is all ASC.
1313*/
1314static int isSortingIndex(
1315 Parse *pParse, /* Parsing context */
drh111a6a72008-12-21 03:51:16 +00001316 WhereMaskSet *pMaskSet, /* Mapping from table cursor numbers to bitmaps */
drh51669862004-12-18 18:40:26 +00001317 Index *pIdx, /* The index we are testing */
drh74161702006-02-24 02:53:49 +00001318 int base, /* Cursor number for the table to be sorted */
drh51669862004-12-18 18:40:26 +00001319 ExprList *pOrderBy, /* The ORDER BY clause */
1320 int nEqCol, /* Number of index columns with == constraints */
1321 int *pbRev /* Set to 1 if ORDER BY is DESC */
1322){
drhb46b5772005-08-29 16:40:52 +00001323 int i, j; /* Loop counters */
drh85eeb692005-12-21 03:16:42 +00001324 int sortOrder = 0; /* XOR of index and ORDER BY sort direction */
drhb46b5772005-08-29 16:40:52 +00001325 int nTerm; /* Number of ORDER BY terms */
1326 struct ExprList_item *pTerm; /* A term of the ORDER BY clause */
drh51669862004-12-18 18:40:26 +00001327 sqlite3 *db = pParse->db;
1328
1329 assert( pOrderBy!=0 );
1330 nTerm = pOrderBy->nExpr;
1331 assert( nTerm>0 );
1332
1333 /* Match terms of the ORDER BY clause against columns of
1334 ** the index.
drhcc192542006-12-20 03:24:19 +00001335 **
1336 ** Note that indices have pIdx->nColumn regular columns plus
1337 ** one additional column containing the rowid. The rowid column
1338 ** of the index is also allowed to match against the ORDER BY
1339 ** clause.
drh51669862004-12-18 18:40:26 +00001340 */
drhcc192542006-12-20 03:24:19 +00001341 for(i=j=0, pTerm=pOrderBy->a; j<nTerm && i<=pIdx->nColumn; i++){
drh51669862004-12-18 18:40:26 +00001342 Expr *pExpr; /* The expression of the ORDER BY pTerm */
1343 CollSeq *pColl; /* The collating sequence of pExpr */
drh85eeb692005-12-21 03:16:42 +00001344 int termSortOrder; /* Sort order for this term */
drhcc192542006-12-20 03:24:19 +00001345 int iColumn; /* The i-th column of the index. -1 for rowid */
1346 int iSortOrder; /* 1 for DESC, 0 for ASC on the i-th index term */
1347 const char *zColl; /* Name of the collating sequence for i-th index term */
drh51669862004-12-18 18:40:26 +00001348
1349 pExpr = pTerm->pExpr;
1350 if( pExpr->op!=TK_COLUMN || pExpr->iTable!=base ){
1351 /* Can not use an index sort on anything that is not a column in the
1352 ** left-most table of the FROM clause */
drh7b4fc6a2007-02-06 13:26:32 +00001353 break;
drh51669862004-12-18 18:40:26 +00001354 }
1355 pColl = sqlite3ExprCollSeq(pParse, pExpr);
drhcc192542006-12-20 03:24:19 +00001356 if( !pColl ){
1357 pColl = db->pDfltColl;
1358 }
1359 if( i<pIdx->nColumn ){
1360 iColumn = pIdx->aiColumn[i];
1361 if( iColumn==pIdx->pTable->iPKey ){
1362 iColumn = -1;
1363 }
1364 iSortOrder = pIdx->aSortOrder[i];
1365 zColl = pIdx->azColl[i];
1366 }else{
1367 iColumn = -1;
1368 iSortOrder = 0;
1369 zColl = pColl->zName;
1370 }
1371 if( pExpr->iColumn!=iColumn || sqlite3StrICmp(pColl->zName, zColl) ){
drh9012bcb2004-12-19 00:11:35 +00001372 /* Term j of the ORDER BY clause does not match column i of the index */
1373 if( i<nEqCol ){
drh51669862004-12-18 18:40:26 +00001374 /* If an index column that is constrained by == fails to match an
1375 ** ORDER BY term, that is OK. Just ignore that column of the index
1376 */
1377 continue;
drhff354e92008-06-25 02:47:57 +00001378 }else if( i==pIdx->nColumn ){
1379 /* Index column i is the rowid. All other terms match. */
1380 break;
drh51669862004-12-18 18:40:26 +00001381 }else{
1382 /* If an index column fails to match and is not constrained by ==
1383 ** then the index cannot satisfy the ORDER BY constraint.
1384 */
1385 return 0;
1386 }
1387 }
danielk1977b3bf5562006-01-10 17:58:23 +00001388 assert( pIdx->aSortOrder!=0 );
drh85eeb692005-12-21 03:16:42 +00001389 assert( pTerm->sortOrder==0 || pTerm->sortOrder==1 );
drhcc192542006-12-20 03:24:19 +00001390 assert( iSortOrder==0 || iSortOrder==1 );
1391 termSortOrder = iSortOrder ^ pTerm->sortOrder;
drh51669862004-12-18 18:40:26 +00001392 if( i>nEqCol ){
drh85eeb692005-12-21 03:16:42 +00001393 if( termSortOrder!=sortOrder ){
drh51669862004-12-18 18:40:26 +00001394 /* Indices can only be used if all ORDER BY terms past the
1395 ** equality constraints are all either DESC or ASC. */
1396 return 0;
1397 }
1398 }else{
drh85eeb692005-12-21 03:16:42 +00001399 sortOrder = termSortOrder;
drh51669862004-12-18 18:40:26 +00001400 }
1401 j++;
1402 pTerm++;
drh7b4fc6a2007-02-06 13:26:32 +00001403 if( iColumn<0 && !referencesOtherTables(pOrderBy, pMaskSet, j, base) ){
drhcc192542006-12-20 03:24:19 +00001404 /* If the indexed column is the primary key and everything matches
drh7b4fc6a2007-02-06 13:26:32 +00001405 ** so far and none of the ORDER BY terms to the right reference other
1406 ** tables in the join, then we are assured that the index can be used
1407 ** to sort because the primary key is unique and so none of the other
1408 ** columns will make any difference
drhcc192542006-12-20 03:24:19 +00001409 */
1410 j = nTerm;
1411 }
drh51669862004-12-18 18:40:26 +00001412 }
1413
drhcc192542006-12-20 03:24:19 +00001414 *pbRev = sortOrder!=0;
drh8718f522005-08-13 16:13:04 +00001415 if( j>=nTerm ){
drhcc192542006-12-20 03:24:19 +00001416 /* All terms of the ORDER BY clause are covered by this index so
1417 ** this index can be used for sorting. */
1418 return 1;
1419 }
drh7b4fc6a2007-02-06 13:26:32 +00001420 if( pIdx->onError!=OE_None && i==pIdx->nColumn
1421 && !referencesOtherTables(pOrderBy, pMaskSet, j, base) ){
drhcc192542006-12-20 03:24:19 +00001422 /* All terms of this index match some prefix of the ORDER BY clause
drh7b4fc6a2007-02-06 13:26:32 +00001423 ** and the index is UNIQUE and no terms on the tail of the ORDER BY
1424 ** clause reference other tables in a join. If this is all true then
1425 ** the order by clause is superfluous. */
drh51669862004-12-18 18:40:26 +00001426 return 1;
1427 }
1428 return 0;
1429}
1430
1431/*
drhb6c29892004-11-22 19:12:19 +00001432** Check table to see if the ORDER BY clause in pOrderBy can be satisfied
1433** by sorting in order of ROWID. Return true if so and set *pbRev to be
1434** true for reverse ROWID and false for forward ROWID order.
1435*/
1436static int sortableByRowid(
1437 int base, /* Cursor number for table to be sorted */
1438 ExprList *pOrderBy, /* The ORDER BY clause */
drh111a6a72008-12-21 03:51:16 +00001439 WhereMaskSet *pMaskSet, /* Mapping from table cursors to bitmaps */
drhb6c29892004-11-22 19:12:19 +00001440 int *pbRev /* Set to 1 if ORDER BY is DESC */
1441){
1442 Expr *p;
1443
1444 assert( pOrderBy!=0 );
1445 assert( pOrderBy->nExpr>0 );
1446 p = pOrderBy->a[0].pExpr;
drh7b4fc6a2007-02-06 13:26:32 +00001447 if( p->op==TK_COLUMN && p->iTable==base && p->iColumn==-1
1448 && !referencesOtherTables(pOrderBy, pMaskSet, 1, base) ){
drhb6c29892004-11-22 19:12:19 +00001449 *pbRev = pOrderBy->a[0].sortOrder;
1450 return 1;
1451 }
1452 return 0;
1453}
1454
drhfe05af82005-07-21 03:14:59 +00001455/*
drhb6fb62d2005-09-20 08:47:20 +00001456** Prepare a crude estimate of the logarithm of the input value.
drh28c4cf42005-07-27 20:41:43 +00001457** The results need not be exact. This is only used for estimating
drh909626d2008-05-30 14:58:37 +00001458** the total cost of performing operations with O(logN) or O(NlogN)
drh28c4cf42005-07-27 20:41:43 +00001459** complexity. Because N is just a guess, it is no great tragedy if
1460** logN is a little off.
drh28c4cf42005-07-27 20:41:43 +00001461*/
1462static double estLog(double N){
drhb37df7b2005-10-13 02:09:49 +00001463 double logN = 1;
1464 double x = 10;
drh28c4cf42005-07-27 20:41:43 +00001465 while( N>x ){
drhb37df7b2005-10-13 02:09:49 +00001466 logN += 1;
drh28c4cf42005-07-27 20:41:43 +00001467 x *= 10;
1468 }
1469 return logN;
1470}
1471
drh6d209d82006-06-27 01:54:26 +00001472/*
1473** Two routines for printing the content of an sqlite3_index_info
1474** structure. Used for testing and debugging only. If neither
1475** SQLITE_TEST or SQLITE_DEBUG are defined, then these routines
1476** are no-ops.
1477*/
drh77a2a5e2007-04-06 01:04:39 +00001478#if !defined(SQLITE_OMIT_VIRTUALTABLE) && defined(SQLITE_DEBUG)
drh6d209d82006-06-27 01:54:26 +00001479static void TRACE_IDX_INPUTS(sqlite3_index_info *p){
1480 int i;
mlcreech3a00f902008-03-04 17:45:01 +00001481 if( !sqlite3WhereTrace ) return;
drh6d209d82006-06-27 01:54:26 +00001482 for(i=0; i<p->nConstraint; i++){
1483 sqlite3DebugPrintf(" constraint[%d]: col=%d termid=%d op=%d usabled=%d\n",
1484 i,
1485 p->aConstraint[i].iColumn,
1486 p->aConstraint[i].iTermOffset,
1487 p->aConstraint[i].op,
1488 p->aConstraint[i].usable);
1489 }
1490 for(i=0; i<p->nOrderBy; i++){
1491 sqlite3DebugPrintf(" orderby[%d]: col=%d desc=%d\n",
1492 i,
1493 p->aOrderBy[i].iColumn,
1494 p->aOrderBy[i].desc);
1495 }
1496}
1497static void TRACE_IDX_OUTPUTS(sqlite3_index_info *p){
1498 int i;
mlcreech3a00f902008-03-04 17:45:01 +00001499 if( !sqlite3WhereTrace ) return;
drh6d209d82006-06-27 01:54:26 +00001500 for(i=0; i<p->nConstraint; i++){
1501 sqlite3DebugPrintf(" usage[%d]: argvIdx=%d omit=%d\n",
1502 i,
1503 p->aConstraintUsage[i].argvIndex,
1504 p->aConstraintUsage[i].omit);
1505 }
1506 sqlite3DebugPrintf(" idxNum=%d\n", p->idxNum);
1507 sqlite3DebugPrintf(" idxStr=%s\n", p->idxStr);
1508 sqlite3DebugPrintf(" orderByConsumed=%d\n", p->orderByConsumed);
1509 sqlite3DebugPrintf(" estimatedCost=%g\n", p->estimatedCost);
1510}
1511#else
1512#define TRACE_IDX_INPUTS(A)
1513#define TRACE_IDX_OUTPUTS(A)
1514#endif
1515
danielk19771d461462009-04-21 09:02:45 +00001516/*
1517** Required because bestIndex() is called by bestOrClauseIndex()
1518*/
1519static void bestIndex(
1520 Parse*, WhereClause*, struct SrcList_item*, Bitmask, ExprList*, WhereCost*);
1521
1522/*
1523** This routine attempts to find an scanning strategy that can be used
1524** to optimize an 'OR' expression that is part of a WHERE clause.
1525**
1526** The table associated with FROM clause term pSrc may be either a
1527** regular B-Tree table or a virtual table.
1528*/
1529static void bestOrClauseIndex(
1530 Parse *pParse, /* The parsing context */
1531 WhereClause *pWC, /* The WHERE clause */
1532 struct SrcList_item *pSrc, /* The FROM clause term to search */
1533 Bitmask notReady, /* Mask of cursors that are not available */
1534 ExprList *pOrderBy, /* The ORDER BY clause */
1535 WhereCost *pCost /* Lowest cost query plan */
1536){
1537#ifndef SQLITE_OMIT_OR_OPTIMIZATION
1538 const int iCur = pSrc->iCursor; /* The cursor of the table to be accessed */
1539 const Bitmask maskSrc = getMask(pWC->pMaskSet, iCur); /* Bitmask for pSrc */
1540 WhereTerm * const pWCEnd = &pWC->a[pWC->nTerm]; /* End of pWC->a[] */
1541 WhereTerm *pTerm; /* A single term of the WHERE clause */
1542
1543 /* Search the WHERE clause terms for a usable WO_OR term. */
1544 for(pTerm=pWC->a; pTerm<pWCEnd; pTerm++){
1545 if( pTerm->eOperator==WO_OR
1546 && ((pTerm->prereqAll & ~maskSrc) & notReady)==0
1547 && (pTerm->u.pOrInfo->indexable & maskSrc)!=0
1548 ){
1549 WhereClause * const pOrWC = &pTerm->u.pOrInfo->wc;
1550 WhereTerm * const pOrWCEnd = &pOrWC->a[pOrWC->nTerm];
1551 WhereTerm *pOrTerm;
1552 int flags = WHERE_MULTI_OR;
1553 double rTotal = 0;
1554 double nRow = 0;
1555
1556 for(pOrTerm=pOrWC->a; pOrTerm<pOrWCEnd; pOrTerm++){
1557 WhereCost sTermCost;
1558 WHERETRACE(("... Multi-index OR testing for term %d of %d....\n",
1559 (pOrTerm - pOrWC->a), (pTerm - pWC->a)
1560 ));
1561 if( pOrTerm->eOperator==WO_AND ){
1562 WhereClause *pAndWC = &pOrTerm->u.pAndInfo->wc;
1563 bestIndex(pParse, pAndWC, pSrc, notReady, 0, &sTermCost);
1564 }else if( pOrTerm->leftCursor==iCur ){
1565 WhereClause tempWC;
1566 tempWC.pParse = pWC->pParse;
1567 tempWC.pMaskSet = pWC->pMaskSet;
1568 tempWC.op = TK_AND;
1569 tempWC.a = pOrTerm;
1570 tempWC.nTerm = 1;
1571 bestIndex(pParse, &tempWC, pSrc, notReady, 0, &sTermCost);
1572 }else{
1573 continue;
1574 }
1575 rTotal += sTermCost.rCost;
1576 nRow += sTermCost.nRow;
1577 if( rTotal>=pCost->rCost ) break;
1578 }
1579
1580 /* If there is an ORDER BY clause, increase the scan cost to account
1581 ** for the cost of the sort. */
1582 if( pOrderBy!=0 ){
1583 rTotal += nRow*estLog(nRow);
1584 WHERETRACE(("... sorting increases OR cost to %.9g\n", rTotal));
1585 }
1586
1587 /* If the cost of scanning using this OR term for optimization is
1588 ** less than the current cost stored in pCost, replace the contents
1589 ** of pCost. */
1590 WHERETRACE(("... multi-index OR cost=%.9g nrow=%.9g\n", rTotal, nRow));
1591 if( rTotal<pCost->rCost ){
1592 pCost->rCost = rTotal;
1593 pCost->nRow = nRow;
1594 pCost->plan.wsFlags = flags;
1595 pCost->plan.u.pTerm = pTerm;
1596 }
1597 }
1598 }
1599#endif /* SQLITE_OMIT_OR_OPTIMIZATION */
1600}
1601
drh9eff6162006-06-12 21:59:13 +00001602#ifndef SQLITE_OMIT_VIRTUALTABLE
1603/*
danielk19771d461462009-04-21 09:02:45 +00001604** Allocate and populate an sqlite3_index_info structure. It is the
1605** responsibility of the caller to eventually release the structure
1606** by passing the pointer returned by this function to sqlite3_free().
1607*/
1608static sqlite3_index_info *allocateIndexInfo(
1609 Parse *pParse,
1610 WhereClause *pWC,
1611 struct SrcList_item *pSrc,
1612 ExprList *pOrderBy
1613){
1614 int i, j;
1615 int nTerm;
1616 struct sqlite3_index_constraint *pIdxCons;
1617 struct sqlite3_index_orderby *pIdxOrderBy;
1618 struct sqlite3_index_constraint_usage *pUsage;
1619 WhereTerm *pTerm;
1620 int nOrderBy;
1621 sqlite3_index_info *pIdxInfo;
1622
1623 WHERETRACE(("Recomputing index info for %s...\n", pSrc->pTab->zName));
1624
1625 /* Count the number of possible WHERE clause constraints referring
1626 ** to this virtual table */
1627 for(i=nTerm=0, pTerm=pWC->a; i<pWC->nTerm; i++, pTerm++){
1628 if( pTerm->leftCursor != pSrc->iCursor ) continue;
1629 assert( (pTerm->eOperator&(pTerm->eOperator-1))==0 );
1630 testcase( pTerm->eOperator==WO_IN );
1631 testcase( pTerm->eOperator==WO_ISNULL );
1632 if( pTerm->eOperator & (WO_IN|WO_ISNULL) ) continue;
1633 nTerm++;
1634 }
1635
1636 /* If the ORDER BY clause contains only columns in the current
1637 ** virtual table then allocate space for the aOrderBy part of
1638 ** the sqlite3_index_info structure.
1639 */
1640 nOrderBy = 0;
1641 if( pOrderBy ){
1642 for(i=0; i<pOrderBy->nExpr; i++){
1643 Expr *pExpr = pOrderBy->a[i].pExpr;
1644 if( pExpr->op!=TK_COLUMN || pExpr->iTable!=pSrc->iCursor ) break;
1645 }
1646 if( i==pOrderBy->nExpr ){
1647 nOrderBy = pOrderBy->nExpr;
1648 }
1649 }
1650
1651 /* Allocate the sqlite3_index_info structure
1652 */
1653 pIdxInfo = sqlite3DbMallocZero(pParse->db, sizeof(*pIdxInfo)
1654 + (sizeof(*pIdxCons) + sizeof(*pUsage))*nTerm
1655 + sizeof(*pIdxOrderBy)*nOrderBy );
1656 if( pIdxInfo==0 ){
1657 sqlite3ErrorMsg(pParse, "out of memory");
1658 /* (double)0 In case of SQLITE_OMIT_FLOATING_POINT... */
1659 return 0;
1660 }
1661
1662 /* Initialize the structure. The sqlite3_index_info structure contains
1663 ** many fields that are declared "const" to prevent xBestIndex from
1664 ** changing them. We have to do some funky casting in order to
1665 ** initialize those fields.
1666 */
1667 pIdxCons = (struct sqlite3_index_constraint*)&pIdxInfo[1];
1668 pIdxOrderBy = (struct sqlite3_index_orderby*)&pIdxCons[nTerm];
1669 pUsage = (struct sqlite3_index_constraint_usage*)&pIdxOrderBy[nOrderBy];
1670 *(int*)&pIdxInfo->nConstraint = nTerm;
1671 *(int*)&pIdxInfo->nOrderBy = nOrderBy;
1672 *(struct sqlite3_index_constraint**)&pIdxInfo->aConstraint = pIdxCons;
1673 *(struct sqlite3_index_orderby**)&pIdxInfo->aOrderBy = pIdxOrderBy;
1674 *(struct sqlite3_index_constraint_usage**)&pIdxInfo->aConstraintUsage =
1675 pUsage;
1676
1677 for(i=j=0, pTerm=pWC->a; i<pWC->nTerm; i++, pTerm++){
1678 if( pTerm->leftCursor != pSrc->iCursor ) continue;
1679 assert( (pTerm->eOperator&(pTerm->eOperator-1))==0 );
1680 testcase( pTerm->eOperator==WO_IN );
1681 testcase( pTerm->eOperator==WO_ISNULL );
1682 if( pTerm->eOperator & (WO_IN|WO_ISNULL) ) continue;
1683 pIdxCons[j].iColumn = pTerm->u.leftColumn;
1684 pIdxCons[j].iTermOffset = i;
1685 pIdxCons[j].op = (u8)pTerm->eOperator;
1686 /* The direct assignment in the previous line is possible only because
1687 ** the WO_ and SQLITE_INDEX_CONSTRAINT_ codes are identical. The
1688 ** following asserts verify this fact. */
1689 assert( WO_EQ==SQLITE_INDEX_CONSTRAINT_EQ );
1690 assert( WO_LT==SQLITE_INDEX_CONSTRAINT_LT );
1691 assert( WO_LE==SQLITE_INDEX_CONSTRAINT_LE );
1692 assert( WO_GT==SQLITE_INDEX_CONSTRAINT_GT );
1693 assert( WO_GE==SQLITE_INDEX_CONSTRAINT_GE );
1694 assert( WO_MATCH==SQLITE_INDEX_CONSTRAINT_MATCH );
1695 assert( pTerm->eOperator & (WO_EQ|WO_LT|WO_LE|WO_GT|WO_GE|WO_MATCH) );
1696 j++;
1697 }
1698 for(i=0; i<nOrderBy; i++){
1699 Expr *pExpr = pOrderBy->a[i].pExpr;
1700 pIdxOrderBy[i].iColumn = pExpr->iColumn;
1701 pIdxOrderBy[i].desc = pOrderBy->a[i].sortOrder;
1702 }
1703
1704 return pIdxInfo;
1705}
1706
1707/*
1708** The table object reference passed as the second argument to this function
1709** must represent a virtual table. This function invokes the xBestIndex()
1710** method of the virtual table with the sqlite3_index_info pointer passed
1711** as the argument.
1712**
1713** If an error occurs, pParse is populated with an error message and a
1714** non-zero value is returned. Otherwise, 0 is returned and the output
1715** part of the sqlite3_index_info structure is left populated.
1716**
1717** Whether or not an error is returned, it is the responsibility of the
1718** caller to eventually free p->idxStr if p->needToFreeIdxStr indicates
1719** that this is required.
1720*/
1721static int vtabBestIndex(Parse *pParse, Table *pTab, sqlite3_index_info *p){
1722 sqlite3_vtab *pVtab = pTab->pVtab;
1723 int i;
1724 int rc;
1725
1726 (void)sqlite3SafetyOff(pParse->db);
1727 WHERETRACE(("xBestIndex for %s\n", pTab->zName));
1728 TRACE_IDX_INPUTS(p);
1729 rc = pVtab->pModule->xBestIndex(pVtab, p);
1730 TRACE_IDX_OUTPUTS(p);
1731 (void)sqlite3SafetyOn(pParse->db);
1732
1733 if( rc!=SQLITE_OK ){
1734 if( rc==SQLITE_NOMEM ){
1735 pParse->db->mallocFailed = 1;
1736 }else if( !pVtab->zErrMsg ){
1737 sqlite3ErrorMsg(pParse, "%s", sqlite3ErrStr(rc));
1738 }else{
1739 sqlite3ErrorMsg(pParse, "%s", pVtab->zErrMsg);
1740 }
1741 }
1742 sqlite3DbFree(pParse->db, pVtab->zErrMsg);
1743 pVtab->zErrMsg = 0;
1744
1745 for(i=0; i<p->nConstraint; i++){
1746 if( !p->aConstraint[i].usable && p->aConstraintUsage[i].argvIndex>0 ){
1747 sqlite3ErrorMsg(pParse,
1748 "table %s: xBestIndex returned an invalid plan", pTab->zName);
1749 }
1750 }
1751
1752 return pParse->nErr;
1753}
1754
1755
1756/*
drh7f375902006-06-13 17:38:59 +00001757** Compute the best index for a virtual table.
1758**
1759** The best index is computed by the xBestIndex method of the virtual
1760** table module. This routine is really just a wrapper that sets up
1761** the sqlite3_index_info structure that is used to communicate with
1762** xBestIndex.
1763**
1764** In a join, this routine might be called multiple times for the
1765** same virtual table. The sqlite3_index_info structure is created
1766** and initialized on the first invocation and reused on all subsequent
1767** invocations. The sqlite3_index_info structure is also used when
1768** code is generated to access the virtual table. The whereInfoDelete()
1769** routine takes care of freeing the sqlite3_index_info structure after
1770** everybody has finished with it.
drh9eff6162006-06-12 21:59:13 +00001771*/
danielk19771d461462009-04-21 09:02:45 +00001772static void bestVirtualIndex(
1773 Parse *pParse, /* The parsing context */
1774 WhereClause *pWC, /* The WHERE clause */
1775 struct SrcList_item *pSrc, /* The FROM clause term to search */
1776 Bitmask notReady, /* Mask of cursors that are not available */
1777 ExprList *pOrderBy, /* The order by clause */
1778 WhereCost *pCost, /* Lowest cost query plan */
1779 sqlite3_index_info **ppIdxInfo /* Index information passed to xBestIndex */
drh9eff6162006-06-12 21:59:13 +00001780){
1781 Table *pTab = pSrc->pTab;
1782 sqlite3_index_info *pIdxInfo;
1783 struct sqlite3_index_constraint *pIdxCons;
drh9eff6162006-06-12 21:59:13 +00001784 struct sqlite3_index_constraint_usage *pUsage;
1785 WhereTerm *pTerm;
1786 int i, j;
1787 int nOrderBy;
1788
danielk19776eacd282009-04-29 11:50:53 +00001789 /* Make sure wsFlags is initialized to some sane value. Otherwise, if the
1790 ** malloc in allocateIndexInfo() fails and this function returns leaving
1791 ** wsFlags in an uninitialized state, the caller may behave unpredictably.
1792 */
drh6a863cd2009-05-06 18:42:21 +00001793 memset(pCost, 0, sizeof(*pCost));
danielk19776eacd282009-04-29 11:50:53 +00001794 pCost->plan.wsFlags = WHERE_VIRTUALTABLE;
1795
drh9eff6162006-06-12 21:59:13 +00001796 /* If the sqlite3_index_info structure has not been previously
danielk19771d461462009-04-21 09:02:45 +00001797 ** allocated and initialized, then allocate and initialize it now.
drh9eff6162006-06-12 21:59:13 +00001798 */
1799 pIdxInfo = *ppIdxInfo;
1800 if( pIdxInfo==0 ){
danielk19771d461462009-04-21 09:02:45 +00001801 *ppIdxInfo = pIdxInfo = allocateIndexInfo(pParse, pWC, pSrc, pOrderBy);
drh9eff6162006-06-12 21:59:13 +00001802 }
danielk1977732dc552009-04-21 17:23:04 +00001803 if( pIdxInfo==0 ){
1804 return;
1805 }
drh9eff6162006-06-12 21:59:13 +00001806
drh7f375902006-06-13 17:38:59 +00001807 /* At this point, the sqlite3_index_info structure that pIdxInfo points
1808 ** to will have been initialized, either during the current invocation or
1809 ** during some prior invocation. Now we just have to customize the
1810 ** details of pIdxInfo for the current invocation and pass it to
1811 ** xBestIndex.
1812 */
1813
danielk1977935ed5e2007-03-30 09:13:13 +00001814 /* The module name must be defined. Also, by this point there must
1815 ** be a pointer to an sqlite3_vtab structure. Otherwise
1816 ** sqlite3ViewGetColumnNames() would have picked up the error.
1817 */
drh9eff6162006-06-12 21:59:13 +00001818 assert( pTab->azModuleArg && pTab->azModuleArg[0] );
danielk19771d461462009-04-21 09:02:45 +00001819 assert( pTab->pVtab );
drh9eff6162006-06-12 21:59:13 +00001820
1821 /* Set the aConstraint[].usable fields and initialize all
drh7f375902006-06-13 17:38:59 +00001822 ** output variables to zero.
1823 **
1824 ** aConstraint[].usable is true for constraints where the right-hand
1825 ** side contains only references to tables to the left of the current
1826 ** table. In other words, if the constraint is of the form:
1827 **
1828 ** column = expr
1829 **
1830 ** and we are evaluating a join, then the constraint on column is
1831 ** only valid if all tables referenced in expr occur to the left
1832 ** of the table containing column.
1833 **
1834 ** The aConstraints[] array contains entries for all constraints
1835 ** on the current table. That way we only have to compute it once
1836 ** even though we might try to pick the best index multiple times.
1837 ** For each attempt at picking an index, the order of tables in the
1838 ** join might be different so we have to recompute the usable flag
1839 ** each time.
drh9eff6162006-06-12 21:59:13 +00001840 */
1841 pIdxCons = *(struct sqlite3_index_constraint**)&pIdxInfo->aConstraint;
1842 pUsage = pIdxInfo->aConstraintUsage;
1843 for(i=0; i<pIdxInfo->nConstraint; i++, pIdxCons++){
1844 j = pIdxCons->iTermOffset;
1845 pTerm = &pWC->a[j];
drhec1724e2008-12-09 01:32:03 +00001846 pIdxCons->usable = (pTerm->prereqRight & notReady)==0 ?1:0;
drh9eff6162006-06-12 21:59:13 +00001847 }
1848 memset(pUsage, 0, sizeof(pUsage[0])*pIdxInfo->nConstraint);
drh4be8b512006-06-13 23:51:34 +00001849 if( pIdxInfo->needToFreeIdxStr ){
1850 sqlite3_free(pIdxInfo->idxStr);
1851 }
1852 pIdxInfo->idxStr = 0;
1853 pIdxInfo->idxNum = 0;
1854 pIdxInfo->needToFreeIdxStr = 0;
drh9eff6162006-06-12 21:59:13 +00001855 pIdxInfo->orderByConsumed = 0;
shanefbd60f82009-02-04 03:59:25 +00001856 /* ((double)2) In case of SQLITE_OMIT_FLOATING_POINT... */
1857 pIdxInfo->estimatedCost = SQLITE_BIG_DBL / ((double)2);
drh9eff6162006-06-12 21:59:13 +00001858 nOrderBy = pIdxInfo->nOrderBy;
danielk19771d461462009-04-21 09:02:45 +00001859 if( !pOrderBy ){
1860 pIdxInfo->nOrderBy = 0;
drh9eff6162006-06-12 21:59:13 +00001861 }
danielk197774cdba42006-06-19 12:02:58 +00001862
danielk19771d461462009-04-21 09:02:45 +00001863 if( vtabBestIndex(pParse, pTab, pIdxInfo) ){
1864 return;
danielk197739359dc2008-03-17 09:36:44 +00001865 }
1866
danielk19771d461462009-04-21 09:02:45 +00001867 /* The cost is not allowed to be larger than SQLITE_BIG_DBL (the
1868 ** inital value of lowestCost in this loop. If it is, then the
1869 ** (cost<lowestCost) test below will never be true.
1870 **
1871 ** Use "(double)2" instead of "2.0" in case OMIT_FLOATING_POINT
1872 ** is defined.
1873 */
1874 if( (SQLITE_BIG_DBL/((double)2))<pIdxInfo->estimatedCost ){
1875 pCost->rCost = (SQLITE_BIG_DBL/((double)2));
1876 }else{
1877 pCost->rCost = pIdxInfo->estimatedCost;
1878 }
danielk19771d461462009-04-21 09:02:45 +00001879 pCost->plan.u.pVtabIdx = pIdxInfo;
1880 if( pIdxInfo && pIdxInfo->orderByConsumed ){
1881 pCost->plan.wsFlags |= WHERE_ORDERBY;
1882 }
1883 pCost->plan.nEq = 0;
1884 pIdxInfo->nOrderBy = nOrderBy;
1885
1886 /* Try to find a more efficient access pattern by using multiple indexes
1887 ** to optimize an OR expression within the WHERE clause.
1888 */
1889 bestOrClauseIndex(pParse, pWC, pSrc, notReady, pOrderBy, pCost);
drh9eff6162006-06-12 21:59:13 +00001890}
1891#endif /* SQLITE_OMIT_VIRTUALTABLE */
1892
drh28c4cf42005-07-27 20:41:43 +00001893/*
drh111a6a72008-12-21 03:51:16 +00001894** Find the query plan for accessing a particular table. Write the
1895** best query plan and its cost into the WhereCost object supplied as the
1896** last parameter.
drh51147ba2005-07-23 22:59:55 +00001897**
drh111a6a72008-12-21 03:51:16 +00001898** The lowest cost plan wins. The cost is an estimate of the amount of
1899** CPU and disk I/O need to process the request using the selected plan.
drh51147ba2005-07-23 22:59:55 +00001900** Factors that influence cost include:
1901**
1902** * The estimated number of rows that will be retrieved. (The
1903** fewer the better.)
1904**
1905** * Whether or not sorting must occur.
1906**
1907** * Whether or not there must be separate lookups in the
1908** index and in the main table.
1909**
danielk1977e2d7b242009-02-23 17:33:49 +00001910** If there was an INDEXED BY clause (pSrc->pIndex) attached to the table in
1911** the SQL statement, then this function only considers plans using the
drh296a4832009-03-22 20:36:18 +00001912** named index. If no such plan is found, then the returned cost is
1913** SQLITE_BIG_DBL. If a plan is found that uses the named index,
danielk197785574e32008-10-06 05:32:18 +00001914** then the cost is calculated in the usual way.
1915**
danielk1977e2d7b242009-02-23 17:33:49 +00001916** If a NOT INDEXED clause (pSrc->notIndexed!=0) was attached to the table
1917** in the SELECT statement, then no indexes are considered. However, the
1918** selected plan may still take advantage of the tables built-in rowid
danielk197785574e32008-10-06 05:32:18 +00001919** index.
drhfe05af82005-07-21 03:14:59 +00001920*/
danielk19771d461462009-04-21 09:02:45 +00001921static void bestBtreeIndex(
drhfe05af82005-07-21 03:14:59 +00001922 Parse *pParse, /* The parsing context */
1923 WhereClause *pWC, /* The WHERE clause */
1924 struct SrcList_item *pSrc, /* The FROM clause term to search */
1925 Bitmask notReady, /* Mask of cursors that are not available */
drh111a6a72008-12-21 03:51:16 +00001926 ExprList *pOrderBy, /* The ORDER BY clause */
1927 WhereCost *pCost /* Lowest cost query plan */
drhfe05af82005-07-21 03:14:59 +00001928){
drh111a6a72008-12-21 03:51:16 +00001929 WhereTerm *pTerm; /* A single term of the WHERE clause */
drh51147ba2005-07-23 22:59:55 +00001930 int iCur = pSrc->iCursor; /* The cursor of the table to be accessed */
1931 Index *pProbe; /* An index we are evaluating */
1932 int rev; /* True to scan in reverse order */
drh165be382008-12-05 02:36:33 +00001933 int wsFlags; /* Flags associated with pProbe */
drh51147ba2005-07-23 22:59:55 +00001934 int nEq; /* Number of == or IN constraints */
drhc49de5d2007-01-19 01:06:01 +00001935 int eqTermMask; /* Mask of valid equality operators */
drh51147ba2005-07-23 22:59:55 +00001936 double cost; /* Cost of using pProbe */
drh111a6a72008-12-21 03:51:16 +00001937 double nRow; /* Estimated number of rows in result set */
drhdd5f5a62008-12-23 13:35:23 +00001938 int i; /* Loop counter */
drhfe05af82005-07-21 03:14:59 +00001939
drh165be382008-12-05 02:36:33 +00001940 WHERETRACE(("bestIndex: tbl=%s notReady=%llx\n", pSrc->pTab->zName,notReady));
drh4dd238a2006-03-28 23:55:57 +00001941 pProbe = pSrc->pTab->pIndex;
danielk197785574e32008-10-06 05:32:18 +00001942 if( pSrc->notIndexed ){
1943 pProbe = 0;
1944 }
drh4dd238a2006-03-28 23:55:57 +00001945
1946 /* If the table has no indices and there are no terms in the where
1947 ** clause that refer to the ROWID, then we will never be able to do
1948 ** anything other than a full table scan on this table. We might as
1949 ** well put it first in the join order. That way, perhaps it can be
1950 ** referenced by other tables in the join.
1951 */
drh111a6a72008-12-21 03:51:16 +00001952 memset(pCost, 0, sizeof(*pCost));
drh4dd238a2006-03-28 23:55:57 +00001953 if( pProbe==0 &&
1954 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 +00001955 (pOrderBy==0 || !sortableByRowid(iCur, pOrderBy, pWC->pMaskSet, &rev)) ){
drh69a442e2009-04-06 12:26:57 +00001956 if( pParse->db->flags & SQLITE_ReverseOrder ){
1957 /* For application testing, randomly reverse the output order for
1958 ** SELECT statements that omit the ORDER BY clause. This will help
1959 ** to find cases where
1960 */
1961 pCost->plan.wsFlags |= WHERE_REVERSE;
1962 }
drh111a6a72008-12-21 03:51:16 +00001963 return;
drh4dd238a2006-03-28 23:55:57 +00001964 }
drh111a6a72008-12-21 03:51:16 +00001965 pCost->rCost = SQLITE_BIG_DBL;
drh51147ba2005-07-23 22:59:55 +00001966
danielk197785574e32008-10-06 05:32:18 +00001967 /* Check for a rowid=EXPR or rowid IN (...) constraints. If there was
1968 ** an INDEXED BY clause attached to this table, skip this step.
drhfe05af82005-07-21 03:14:59 +00001969 */
danielk197785574e32008-10-06 05:32:18 +00001970 if( !pSrc->pIndex ){
1971 pTerm = findTerm(pWC, iCur, -1, notReady, WO_EQ|WO_IN, 0);
1972 if( pTerm ){
1973 Expr *pExpr;
drh111a6a72008-12-21 03:51:16 +00001974 pCost->plan.wsFlags = WHERE_ROWID_EQ;
danielk197785574e32008-10-06 05:32:18 +00001975 if( pTerm->eOperator & WO_EQ ){
1976 /* Rowid== is always the best pick. Look no further. Because only
1977 ** a single row is generated, output is always in sorted order */
drh111a6a72008-12-21 03:51:16 +00001978 pCost->plan.wsFlags = WHERE_ROWID_EQ | WHERE_UNIQUE;
1979 pCost->plan.nEq = 1;
danielk197785574e32008-10-06 05:32:18 +00001980 WHERETRACE(("... best is rowid\n"));
drh111a6a72008-12-21 03:51:16 +00001981 pCost->rCost = 0;
1982 pCost->nRow = 1;
1983 return;
danielk19776ab3a2e2009-02-19 14:39:25 +00001984 }else if( !ExprHasProperty((pExpr = pTerm->pExpr), EP_xIsSelect)
1985 && pExpr->x.pList
1986 ){
danielk197785574e32008-10-06 05:32:18 +00001987 /* Rowid IN (LIST): cost is NlogN where N is the number of list
1988 ** elements. */
danielk19776ab3a2e2009-02-19 14:39:25 +00001989 pCost->rCost = pCost->nRow = pExpr->x.pList->nExpr;
drh111a6a72008-12-21 03:51:16 +00001990 pCost->rCost *= estLog(pCost->rCost);
danielk197785574e32008-10-06 05:32:18 +00001991 }else{
1992 /* Rowid IN (SELECT): cost is NlogN where N is the number of rows
1993 ** in the result of the inner select. We have no way to estimate
1994 ** that value so make a wild guess. */
drh111a6a72008-12-21 03:51:16 +00001995 pCost->nRow = 100;
1996 pCost->rCost = 200;
drh28c4cf42005-07-27 20:41:43 +00001997 }
drh111a6a72008-12-21 03:51:16 +00001998 WHERETRACE(("... rowid IN cost: %.9g\n", pCost->rCost));
drh51147ba2005-07-23 22:59:55 +00001999 }
danielk197785574e32008-10-06 05:32:18 +00002000
2001 /* Estimate the cost of a table scan. If we do not know how many
2002 ** entries are in the table, use 1 million as a guess.
2003 */
2004 cost = pProbe ? pProbe->aiRowEst[0] : 1000000;
2005 WHERETRACE(("... table scan base cost: %.9g\n", cost));
drh165be382008-12-05 02:36:33 +00002006 wsFlags = WHERE_ROWID_RANGE;
danielk197785574e32008-10-06 05:32:18 +00002007
2008 /* Check for constraints on a range of rowids in a table scan.
2009 */
2010 pTerm = findTerm(pWC, iCur, -1, notReady, WO_LT|WO_LE|WO_GT|WO_GE, 0);
2011 if( pTerm ){
2012 if( findTerm(pWC, iCur, -1, notReady, WO_LT|WO_LE, 0) ){
drh165be382008-12-05 02:36:33 +00002013 wsFlags |= WHERE_TOP_LIMIT;
drh700a2262008-12-17 19:22:15 +00002014 cost /= 3; /* Guess that rowid<EXPR eliminates two-thirds of rows */
danielk197785574e32008-10-06 05:32:18 +00002015 }
2016 if( findTerm(pWC, iCur, -1, notReady, WO_GT|WO_GE, 0) ){
drh165be382008-12-05 02:36:33 +00002017 wsFlags |= WHERE_BTM_LIMIT;
danielk197785574e32008-10-06 05:32:18 +00002018 cost /= 3; /* Guess that rowid>EXPR eliminates two-thirds of rows */
2019 }
2020 WHERETRACE(("... rowid range reduces cost to %.9g\n", cost));
2021 }else{
drh165be382008-12-05 02:36:33 +00002022 wsFlags = 0;
danielk197785574e32008-10-06 05:32:18 +00002023 }
drh111a6a72008-12-21 03:51:16 +00002024 nRow = cost;
danielk197785574e32008-10-06 05:32:18 +00002025
2026 /* If the table scan does not satisfy the ORDER BY clause, increase
2027 ** the cost by NlogN to cover the expense of sorting. */
2028 if( pOrderBy ){
2029 if( sortableByRowid(iCur, pOrderBy, pWC->pMaskSet, &rev) ){
drh165be382008-12-05 02:36:33 +00002030 wsFlags |= WHERE_ORDERBY|WHERE_ROWID_RANGE;
danielk197785574e32008-10-06 05:32:18 +00002031 if( rev ){
drh165be382008-12-05 02:36:33 +00002032 wsFlags |= WHERE_REVERSE;
danielk197785574e32008-10-06 05:32:18 +00002033 }
2034 }else{
2035 cost += cost*estLog(cost);
2036 WHERETRACE(("... sorting increases cost to %.9g\n", cost));
2037 }
drh699b3d42009-02-23 16:52:07 +00002038 }else if( pParse->db->flags & SQLITE_ReverseOrder ){
2039 /* For application testing, randomly reverse the output order for
2040 ** SELECT statements that omit the ORDER BY clause. This will help
2041 ** to find cases where
2042 */
2043 wsFlags |= WHERE_REVERSE;
danielk197785574e32008-10-06 05:32:18 +00002044 }
drh699b3d42009-02-23 16:52:07 +00002045
2046 /* Remember this case if it is the best so far */
drh111a6a72008-12-21 03:51:16 +00002047 if( cost<pCost->rCost ){
2048 pCost->rCost = cost;
2049 pCost->nRow = nRow;
2050 pCost->plan.wsFlags = wsFlags;
danielk197785574e32008-10-06 05:32:18 +00002051 }
drhfe05af82005-07-21 03:14:59 +00002052 }
2053
danielk19771d461462009-04-21 09:02:45 +00002054 bestOrClauseIndex(pParse, pWC, pSrc, notReady, pOrderBy, pCost);
drhdd5f5a62008-12-23 13:35:23 +00002055
drhc49de5d2007-01-19 01:06:01 +00002056 /* If the pSrc table is the right table of a LEFT JOIN then we may not
2057 ** use an index to satisfy IS NULL constraints on that table. This is
2058 ** because columns might end up being NULL if the table does not match -
2059 ** a circumstance which the index cannot help us discover. Ticket #2177.
2060 */
2061 if( (pSrc->jointype & JT_LEFT)!=0 ){
2062 eqTermMask = WO_EQ|WO_IN;
2063 }else{
2064 eqTermMask = WO_EQ|WO_IN|WO_ISNULL;
2065 }
2066
drhfe05af82005-07-21 03:14:59 +00002067 /* Look at each index.
2068 */
danielk197785574e32008-10-06 05:32:18 +00002069 if( pSrc->pIndex ){
2070 pProbe = pSrc->pIndex;
2071 }
2072 for(; pProbe; pProbe=(pSrc->pIndex ? 0 : pProbe->pNext)){
drh75572e92009-03-29 00:13:03 +00002073 double inMultiplier = 1; /* Number of equality look-ups needed */
2074 int inMultIsEst = 0; /* True if inMultiplier is an estimate */
drh51147ba2005-07-23 22:59:55 +00002075
drh4f0c5872007-03-26 22:05:01 +00002076 WHERETRACE(("... index %s:\n", pProbe->zName));
drhfe05af82005-07-21 03:14:59 +00002077
2078 /* Count the number of columns in the index that are satisfied
drh46619d62009-04-24 14:51:42 +00002079 ** by x=EXPR or x IS NULL constraints or x IN (...) constraints.
2080 ** For a term of the form x=EXPR or x IS NULL we only have to do
2081 ** a single binary search. But for x IN (...) we have to do a
2082 ** number of binary searched
drh75572e92009-03-29 00:13:03 +00002083 ** equal to the number of entries on the RHS of the IN operator.
2084 ** The inMultipler variable with try to estimate the number of
2085 ** binary searches needed.
drhfe05af82005-07-21 03:14:59 +00002086 */
drh165be382008-12-05 02:36:33 +00002087 wsFlags = 0;
drhfe05af82005-07-21 03:14:59 +00002088 for(i=0; i<pProbe->nColumn; i++){
2089 int j = pProbe->aiColumn[i];
drhc49de5d2007-01-19 01:06:01 +00002090 pTerm = findTerm(pWC, iCur, j, notReady, eqTermMask, pProbe);
drhfe05af82005-07-21 03:14:59 +00002091 if( pTerm==0 ) break;
drh165be382008-12-05 02:36:33 +00002092 wsFlags |= WHERE_COLUMN_EQ;
drhb52076c2006-01-23 13:22:09 +00002093 if( pTerm->eOperator & WO_IN ){
drha6110402005-07-28 20:51:19 +00002094 Expr *pExpr = pTerm->pExpr;
drh165be382008-12-05 02:36:33 +00002095 wsFlags |= WHERE_COLUMN_IN;
danielk19776ab3a2e2009-02-19 14:39:25 +00002096 if( ExprHasProperty(pExpr, EP_xIsSelect) ){
drhffe0f892006-05-11 13:26:25 +00002097 inMultiplier *= 25;
drh75572e92009-03-29 00:13:03 +00002098 inMultIsEst = 1;
danielk19776ab3a2e2009-02-19 14:39:25 +00002099 }else if( pExpr->x.pList ){
2100 inMultiplier *= pExpr->x.pList->nExpr + 1;
drhfe05af82005-07-21 03:14:59 +00002101 }
drh46619d62009-04-24 14:51:42 +00002102 }else if( pTerm->eOperator & WO_ISNULL ){
2103 wsFlags |= WHERE_COLUMN_NULL;
drhfe05af82005-07-21 03:14:59 +00002104 }
2105 }
drh111a6a72008-12-21 03:51:16 +00002106 nRow = pProbe->aiRowEst[i] * inMultiplier;
drh75572e92009-03-29 00:13:03 +00002107 /* If inMultiplier is an estimate and that estimate results in an
2108 ** nRow it that is more than half number of rows in the table,
2109 ** then reduce inMultipler */
2110 if( inMultIsEst && nRow*2 > pProbe->aiRowEst[0] ){
2111 nRow = pProbe->aiRowEst[0]/2;
2112 inMultiplier = nRow/pProbe->aiRowEst[i];
2113 }
2114 cost = nRow + inMultiplier*estLog(pProbe->aiRowEst[0]);
drh51147ba2005-07-23 22:59:55 +00002115 nEq = i;
drh46619d62009-04-24 14:51:42 +00002116 if( pProbe->onError!=OE_None && nEq==pProbe->nColumn ){
2117 testcase( wsFlags & WHERE_COLUMN_IN );
2118 testcase( wsFlags & WHERE_COLUMN_NULL );
2119 if( (wsFlags & (WHERE_COLUMN_IN|WHERE_COLUMN_NULL))==0 ){
2120 wsFlags |= WHERE_UNIQUE;
2121 }
drh943af3c2005-07-29 19:43:58 +00002122 }
drh75572e92009-03-29 00:13:03 +00002123 WHERETRACE(("...... nEq=%d inMult=%.9g nRow=%.9g cost=%.9g\n",
2124 nEq, inMultiplier, nRow, cost));
drhfe05af82005-07-21 03:14:59 +00002125
drh75572e92009-03-29 00:13:03 +00002126 /* Look for range constraints. Assume that each range constraint
2127 ** makes the search space 1/3rd smaller.
drhfe05af82005-07-21 03:14:59 +00002128 */
drh51147ba2005-07-23 22:59:55 +00002129 if( nEq<pProbe->nColumn ){
2130 int j = pProbe->aiColumn[nEq];
2131 pTerm = findTerm(pWC, iCur, j, notReady, WO_LT|WO_LE|WO_GT|WO_GE, pProbe);
2132 if( pTerm ){
drh165be382008-12-05 02:36:33 +00002133 wsFlags |= WHERE_COLUMN_RANGE;
drh51147ba2005-07-23 22:59:55 +00002134 if( findTerm(pWC, iCur, j, notReady, WO_LT|WO_LE, pProbe) ){
drh165be382008-12-05 02:36:33 +00002135 wsFlags |= WHERE_TOP_LIMIT;
drhb37df7b2005-10-13 02:09:49 +00002136 cost /= 3;
drh111a6a72008-12-21 03:51:16 +00002137 nRow /= 3;
drh51147ba2005-07-23 22:59:55 +00002138 }
2139 if( findTerm(pWC, iCur, j, notReady, WO_GT|WO_GE, pProbe) ){
drh165be382008-12-05 02:36:33 +00002140 wsFlags |= WHERE_BTM_LIMIT;
drhb37df7b2005-10-13 02:09:49 +00002141 cost /= 3;
drh111a6a72008-12-21 03:51:16 +00002142 nRow /= 3;
drh51147ba2005-07-23 22:59:55 +00002143 }
drh75572e92009-03-29 00:13:03 +00002144 WHERETRACE(("...... range reduces nRow to %.9g and cost to %.9g\n",
2145 nRow, cost));
drh51147ba2005-07-23 22:59:55 +00002146 }
2147 }
2148
drh28c4cf42005-07-27 20:41:43 +00002149 /* Add the additional cost of sorting if that is a factor.
drh51147ba2005-07-23 22:59:55 +00002150 */
drh28c4cf42005-07-27 20:41:43 +00002151 if( pOrderBy ){
drh46619d62009-04-24 14:51:42 +00002152 if( (wsFlags & (WHERE_COLUMN_IN|WHERE_COLUMN_NULL))==0
2153 && isSortingIndex(pParse,pWC->pMaskSet,pProbe,iCur,pOrderBy,nEq,&rev)
2154 ){
drh165be382008-12-05 02:36:33 +00002155 if( wsFlags==0 ){
2156 wsFlags = WHERE_COLUMN_RANGE;
drh28c4cf42005-07-27 20:41:43 +00002157 }
drh165be382008-12-05 02:36:33 +00002158 wsFlags |= WHERE_ORDERBY;
drh28c4cf42005-07-27 20:41:43 +00002159 if( rev ){
drh165be382008-12-05 02:36:33 +00002160 wsFlags |= WHERE_REVERSE;
drh28c4cf42005-07-27 20:41:43 +00002161 }
2162 }else{
2163 cost += cost*estLog(cost);
drh4f0c5872007-03-26 22:05:01 +00002164 WHERETRACE(("...... orderby increases cost to %.9g\n", cost));
drh51147ba2005-07-23 22:59:55 +00002165 }
drh699b3d42009-02-23 16:52:07 +00002166 }else if( pParse->db->flags & SQLITE_ReverseOrder ){
2167 /* For application testing, randomly reverse the output order for
2168 ** SELECT statements that omit the ORDER BY clause. This will help
2169 ** to find cases where
2170 */
2171 wsFlags |= WHERE_REVERSE;
drhfe05af82005-07-21 03:14:59 +00002172 }
2173
2174 /* Check to see if we can get away with using just the index without
drh51147ba2005-07-23 22:59:55 +00002175 ** ever reading the table. If that is the case, then halve the
2176 ** cost of this index.
drhfe05af82005-07-21 03:14:59 +00002177 */
drh165be382008-12-05 02:36:33 +00002178 if( wsFlags && pSrc->colUsed < (((Bitmask)1)<<(BMS-1)) ){
drhfe05af82005-07-21 03:14:59 +00002179 Bitmask m = pSrc->colUsed;
2180 int j;
2181 for(j=0; j<pProbe->nColumn; j++){
2182 int x = pProbe->aiColumn[j];
2183 if( x<BMS-1 ){
2184 m &= ~(((Bitmask)1)<<x);
2185 }
2186 }
2187 if( m==0 ){
drh165be382008-12-05 02:36:33 +00002188 wsFlags |= WHERE_IDX_ONLY;
drhb37df7b2005-10-13 02:09:49 +00002189 cost /= 2;
drh4f0c5872007-03-26 22:05:01 +00002190 WHERETRACE(("...... idx-only reduces cost to %.9g\n", cost));
drhfe05af82005-07-21 03:14:59 +00002191 }
2192 }
2193
drh51147ba2005-07-23 22:59:55 +00002194 /* If this index has achieved the lowest cost so far, then use it.
drhfe05af82005-07-21 03:14:59 +00002195 */
drh111a6a72008-12-21 03:51:16 +00002196 if( wsFlags!=0 && cost < pCost->rCost ){
2197 pCost->rCost = cost;
2198 pCost->nRow = nRow;
2199 pCost->plan.wsFlags = wsFlags;
2200 pCost->plan.nEq = nEq;
2201 assert( pCost->plan.wsFlags & WHERE_INDEXED );
2202 pCost->plan.u.pIdx = pProbe;
drhfe05af82005-07-21 03:14:59 +00002203 }
2204 }
2205
drhfe05af82005-07-21 03:14:59 +00002206 /* Report the best result
2207 */
drh111a6a72008-12-21 03:51:16 +00002208 pCost->plan.wsFlags |= eqTermMask;
2209 WHERETRACE(("best index is %s, cost=%.9g, nrow=%.9g, wsFlags=%x, nEq=%d\n",
2210 (pCost->plan.wsFlags & WHERE_INDEXED)!=0 ?
2211 pCost->plan.u.pIdx->zName : "(none)", pCost->nRow,
2212 pCost->rCost, pCost->plan.wsFlags, pCost->plan.nEq));
drhfe05af82005-07-21 03:14:59 +00002213}
2214
danielk19771d461462009-04-21 09:02:45 +00002215/*
2216** Find the query plan for accessing table pSrc->pTab. Write the
2217** best query plan and its cost into the WhereCost object supplied
2218** as the last parameter. This function may calculate the cost of
2219** both real and virtual table scans.
2220*/
2221static void bestIndex(
2222 Parse *pParse, /* The parsing context */
2223 WhereClause *pWC, /* The WHERE clause */
2224 struct SrcList_item *pSrc, /* The FROM clause term to search */
2225 Bitmask notReady, /* Mask of cursors that are not available */
2226 ExprList *pOrderBy, /* The ORDER BY clause */
2227 WhereCost *pCost /* Lowest cost query plan */
2228){
2229 if( IsVirtual(pSrc->pTab) ){
2230 sqlite3_index_info *p = 0;
2231 bestVirtualIndex(pParse, pWC, pSrc, notReady, pOrderBy, pCost, &p);
2232 if( p->needToFreeIdxStr ){
2233 sqlite3_free(p->idxStr);
2234 }
2235 sqlite3DbFree(pParse->db, p);
2236 }else{
2237 bestBtreeIndex(pParse, pWC, pSrc, notReady, pOrderBy, pCost);
2238 }
2239}
drhb6c29892004-11-22 19:12:19 +00002240
2241/*
drh2ffb1182004-07-19 19:14:01 +00002242** Disable a term in the WHERE clause. Except, do not disable the term
2243** if it controls a LEFT OUTER JOIN and it did not originate in the ON
2244** or USING clause of that join.
2245**
2246** Consider the term t2.z='ok' in the following queries:
2247**
2248** (1) SELECT * FROM t1 LEFT JOIN t2 ON t1.a=t2.x WHERE t2.z='ok'
2249** (2) SELECT * FROM t1 LEFT JOIN t2 ON t1.a=t2.x AND t2.z='ok'
2250** (3) SELECT * FROM t1, t2 WHERE t1.a=t2.x AND t2.z='ok'
2251**
drh23bf66d2004-12-14 03:34:34 +00002252** The t2.z='ok' is disabled in the in (2) because it originates
drh2ffb1182004-07-19 19:14:01 +00002253** in the ON clause. The term is disabled in (3) because it is not part
2254** of a LEFT OUTER JOIN. In (1), the term is not disabled.
2255**
2256** Disabling a term causes that term to not be tested in the inner loop
drhb6fb62d2005-09-20 08:47:20 +00002257** of the join. Disabling is an optimization. When terms are satisfied
2258** by indices, we disable them to prevent redundant tests in the inner
2259** loop. We would get the correct results if nothing were ever disabled,
2260** but joins might run a little slower. The trick is to disable as much
2261** as we can without disabling too much. If we disabled in (1), we'd get
2262** the wrong answer. See ticket #813.
drh2ffb1182004-07-19 19:14:01 +00002263*/
drh0fcef5e2005-07-19 17:38:22 +00002264static void disableTerm(WhereLevel *pLevel, WhereTerm *pTerm){
2265 if( pTerm
drh165be382008-12-05 02:36:33 +00002266 && ALWAYS((pTerm->wtFlags & TERM_CODED)==0)
drh0fcef5e2005-07-19 17:38:22 +00002267 && (pLevel->iLeftJoin==0 || ExprHasProperty(pTerm->pExpr, EP_FromJoin))
2268 ){
drh165be382008-12-05 02:36:33 +00002269 pTerm->wtFlags |= TERM_CODED;
drh45b1ee42005-08-02 17:48:22 +00002270 if( pTerm->iParent>=0 ){
2271 WhereTerm *pOther = &pTerm->pWC->a[pTerm->iParent];
2272 if( (--pOther->nChild)==0 ){
drhed378002005-07-28 23:12:08 +00002273 disableTerm(pLevel, pOther);
2274 }
drh0fcef5e2005-07-19 17:38:22 +00002275 }
drh2ffb1182004-07-19 19:14:01 +00002276 }
2277}
2278
2279/*
danielk1977b790c6c2008-04-18 10:25:24 +00002280** Apply the affinities associated with the first n columns of index
2281** pIdx to the values in the n registers starting at base.
drh94a11212004-09-25 13:12:14 +00002282*/
danielk1977b790c6c2008-04-18 10:25:24 +00002283static void codeApplyAffinity(Parse *pParse, int base, int n, Index *pIdx){
2284 if( n>0 ){
2285 Vdbe *v = pParse->pVdbe;
2286 assert( v!=0 );
2287 sqlite3VdbeAddOp2(v, OP_Affinity, base, n);
2288 sqlite3IndexAffinityStr(v, pIdx);
2289 sqlite3ExprCacheAffinityChange(pParse, base, n);
2290 }
drh94a11212004-09-25 13:12:14 +00002291}
2292
drhe8b97272005-07-19 22:22:12 +00002293
2294/*
drh51147ba2005-07-23 22:59:55 +00002295** Generate code for a single equality term of the WHERE clause. An equality
2296** term can be either X=expr or X IN (...). pTerm is the term to be
2297** coded.
2298**
drh1db639c2008-01-17 02:36:28 +00002299** The current value for the constraint is left in register iReg.
drh51147ba2005-07-23 22:59:55 +00002300**
2301** For a constraint of the form X=expr, the expression is evaluated and its
2302** result is left on the stack. For constraints of the form X IN (...)
2303** this routine sets up a loop that will iterate over all values of X.
drh94a11212004-09-25 13:12:14 +00002304*/
drh678ccce2008-03-31 18:19:54 +00002305static int codeEqualityTerm(
drh94a11212004-09-25 13:12:14 +00002306 Parse *pParse, /* The parsing context */
drhe23399f2005-07-22 00:31:39 +00002307 WhereTerm *pTerm, /* The term of the WHERE clause to be coded */
drh1db639c2008-01-17 02:36:28 +00002308 WhereLevel *pLevel, /* When level of the FROM clause we are working on */
drh678ccce2008-03-31 18:19:54 +00002309 int iTarget /* Attempt to leave results in this register */
drh94a11212004-09-25 13:12:14 +00002310){
drh0fcef5e2005-07-19 17:38:22 +00002311 Expr *pX = pTerm->pExpr;
drh50b39962006-10-28 00:28:09 +00002312 Vdbe *v = pParse->pVdbe;
drh678ccce2008-03-31 18:19:54 +00002313 int iReg; /* Register holding results */
drh1db639c2008-01-17 02:36:28 +00002314
danielk19772d605492008-10-01 08:43:03 +00002315 assert( iTarget>0 );
drh50b39962006-10-28 00:28:09 +00002316 if( pX->op==TK_EQ ){
drh678ccce2008-03-31 18:19:54 +00002317 iReg = sqlite3ExprCodeTarget(pParse, pX->pRight, iTarget);
drh50b39962006-10-28 00:28:09 +00002318 }else if( pX->op==TK_ISNULL ){
drh678ccce2008-03-31 18:19:54 +00002319 iReg = iTarget;
drh1db639c2008-01-17 02:36:28 +00002320 sqlite3VdbeAddOp2(v, OP_Null, 0, iReg);
danielk1977b3bce662005-01-29 08:32:43 +00002321#ifndef SQLITE_OMIT_SUBQUERY
drh94a11212004-09-25 13:12:14 +00002322 }else{
danielk19779a96b662007-11-29 17:05:18 +00002323 int eType;
danielk1977b3bce662005-01-29 08:32:43 +00002324 int iTab;
drh72e8fa42007-03-28 14:30:06 +00002325 struct InLoop *pIn;
danielk1977b3bce662005-01-29 08:32:43 +00002326
drh50b39962006-10-28 00:28:09 +00002327 assert( pX->op==TK_IN );
drh678ccce2008-03-31 18:19:54 +00002328 iReg = iTarget;
danielk19770cdc0222008-06-26 18:04:03 +00002329 eType = sqlite3FindInIndex(pParse, pX, 0);
danielk1977b3bce662005-01-29 08:32:43 +00002330 iTab = pX->iTable;
drh66a51672008-01-03 00:01:23 +00002331 sqlite3VdbeAddOp2(v, OP_Rewind, iTab, 0);
drh111a6a72008-12-21 03:51:16 +00002332 assert( pLevel->plan.wsFlags & WHERE_IN_ABLE );
2333 if( pLevel->u.in.nIn==0 ){
drhb3190c12008-12-08 21:37:14 +00002334 pLevel->addrNxt = sqlite3VdbeMakeLabel(v);
drh72e8fa42007-03-28 14:30:06 +00002335 }
drh111a6a72008-12-21 03:51:16 +00002336 pLevel->u.in.nIn++;
2337 pLevel->u.in.aInLoop =
2338 sqlite3DbReallocOrFree(pParse->db, pLevel->u.in.aInLoop,
2339 sizeof(pLevel->u.in.aInLoop[0])*pLevel->u.in.nIn);
2340 pIn = pLevel->u.in.aInLoop;
drh72e8fa42007-03-28 14:30:06 +00002341 if( pIn ){
drh111a6a72008-12-21 03:51:16 +00002342 pIn += pLevel->u.in.nIn - 1;
drh72e8fa42007-03-28 14:30:06 +00002343 pIn->iCur = iTab;
drh1db639c2008-01-17 02:36:28 +00002344 if( eType==IN_INDEX_ROWID ){
drhb3190c12008-12-08 21:37:14 +00002345 pIn->addrInTop = sqlite3VdbeAddOp2(v, OP_Rowid, iTab, iReg);
drh1db639c2008-01-17 02:36:28 +00002346 }else{
drhb3190c12008-12-08 21:37:14 +00002347 pIn->addrInTop = sqlite3VdbeAddOp3(v, OP_Column, iTab, 0, iReg);
drh1db639c2008-01-17 02:36:28 +00002348 }
2349 sqlite3VdbeAddOp1(v, OP_IsNull, iReg);
drha6110402005-07-28 20:51:19 +00002350 }else{
drh111a6a72008-12-21 03:51:16 +00002351 pLevel->u.in.nIn = 0;
drhe23399f2005-07-22 00:31:39 +00002352 }
danielk1977b3bce662005-01-29 08:32:43 +00002353#endif
drh94a11212004-09-25 13:12:14 +00002354 }
drh0fcef5e2005-07-19 17:38:22 +00002355 disableTerm(pLevel, pTerm);
drh678ccce2008-03-31 18:19:54 +00002356 return iReg;
drh94a11212004-09-25 13:12:14 +00002357}
2358
drh51147ba2005-07-23 22:59:55 +00002359/*
2360** Generate code that will evaluate all == and IN constraints for an
2361** index. The values for all constraints are left on the stack.
2362**
2363** For example, consider table t1(a,b,c,d,e,f) with index i1(a,b,c).
2364** Suppose the WHERE clause is this: a==5 AND b IN (1,2,3) AND c>5 AND c<10
2365** The index has as many as three equality constraints, but in this
2366** example, the third "c" value is an inequality. So only two
2367** constraints are coded. This routine will generate code to evaluate
drh6df2acd2008-12-28 16:55:25 +00002368** a==5 and b IN (1,2,3). The current values for a and b will be stored
2369** in consecutive registers and the index of the first register is returned.
drh51147ba2005-07-23 22:59:55 +00002370**
2371** In the example above nEq==2. But this subroutine works for any value
2372** of nEq including 0. If nEq==0, this routine is nearly a no-op.
2373** The only thing it does is allocate the pLevel->iMem memory cell.
2374**
drh700a2262008-12-17 19:22:15 +00002375** This routine always allocates at least one memory cell and returns
2376** the index of that memory cell. The code that
2377** calls this routine will use that memory cell to store the termination
drh51147ba2005-07-23 22:59:55 +00002378** key value of the loop. If one or more IN operators appear, then
2379** this routine allocates an additional nEq memory cells for internal
2380** use.
2381*/
drh1db639c2008-01-17 02:36:28 +00002382static int codeAllEqualityTerms(
drh51147ba2005-07-23 22:59:55 +00002383 Parse *pParse, /* Parsing context */
2384 WhereLevel *pLevel, /* Which nested loop of the FROM we are coding */
2385 WhereClause *pWC, /* The WHERE clause */
drh1db639c2008-01-17 02:36:28 +00002386 Bitmask notReady, /* Which parts of FROM have not yet been coded */
2387 int nExtraReg /* Number of extra registers to allocate */
drh51147ba2005-07-23 22:59:55 +00002388){
drh111a6a72008-12-21 03:51:16 +00002389 int nEq = pLevel->plan.nEq; /* The number of == or IN constraints to code */
2390 Vdbe *v = pParse->pVdbe; /* The vm under construction */
2391 Index *pIdx; /* The index being used for this loop */
drh51147ba2005-07-23 22:59:55 +00002392 int iCur = pLevel->iTabCur; /* The cursor of the table */
2393 WhereTerm *pTerm; /* A single constraint term */
2394 int j; /* Loop counter */
drh1db639c2008-01-17 02:36:28 +00002395 int regBase; /* Base register */
drh6df2acd2008-12-28 16:55:25 +00002396 int nReg; /* Number of registers to allocate */
drh51147ba2005-07-23 22:59:55 +00002397
drh111a6a72008-12-21 03:51:16 +00002398 /* This module is only called on query plans that use an index. */
2399 assert( pLevel->plan.wsFlags & WHERE_INDEXED );
2400 pIdx = pLevel->plan.u.pIdx;
2401
drh51147ba2005-07-23 22:59:55 +00002402 /* Figure out how many memory cells we will need then allocate them.
drh51147ba2005-07-23 22:59:55 +00002403 */
drh700a2262008-12-17 19:22:15 +00002404 regBase = pParse->nMem + 1;
drh6df2acd2008-12-28 16:55:25 +00002405 nReg = pLevel->plan.nEq + nExtraReg;
2406 pParse->nMem += nReg;
drh51147ba2005-07-23 22:59:55 +00002407
2408 /* Evaluate the equality constraints
2409 */
drhc49de5d2007-01-19 01:06:01 +00002410 assert( pIdx->nColumn>=nEq );
2411 for(j=0; j<nEq; j++){
drh678ccce2008-03-31 18:19:54 +00002412 int r1;
drh51147ba2005-07-23 22:59:55 +00002413 int k = pIdx->aiColumn[j];
drh111a6a72008-12-21 03:51:16 +00002414 pTerm = findTerm(pWC, iCur, k, notReady, pLevel->plan.wsFlags, pIdx);
drh34004ce2008-07-11 16:15:17 +00002415 if( NEVER(pTerm==0) ) break;
drh165be382008-12-05 02:36:33 +00002416 assert( (pTerm->wtFlags & TERM_CODED)==0 );
drh678ccce2008-03-31 18:19:54 +00002417 r1 = codeEqualityTerm(pParse, pTerm, pLevel, regBase+j);
2418 if( r1!=regBase+j ){
drh6df2acd2008-12-28 16:55:25 +00002419 if( nReg==1 ){
2420 sqlite3ReleaseTempReg(pParse, regBase);
2421 regBase = r1;
2422 }else{
2423 sqlite3VdbeAddOp2(v, OP_SCopy, r1, regBase+j);
2424 }
drh678ccce2008-03-31 18:19:54 +00002425 }
drh981642f2008-04-19 14:40:43 +00002426 testcase( pTerm->eOperator & WO_ISNULL );
2427 testcase( pTerm->eOperator & WO_IN );
drh72e8fa42007-03-28 14:30:06 +00002428 if( (pTerm->eOperator & (WO_ISNULL|WO_IN))==0 ){
drhb3190c12008-12-08 21:37:14 +00002429 sqlite3VdbeAddOp2(v, OP_IsNull, regBase+j, pLevel->addrBrk);
drh51147ba2005-07-23 22:59:55 +00002430 }
2431 }
drh1db639c2008-01-17 02:36:28 +00002432 return regBase;
drh51147ba2005-07-23 22:59:55 +00002433}
2434
drh111a6a72008-12-21 03:51:16 +00002435/*
2436** Generate code for the start of the iLevel-th loop in the WHERE clause
2437** implementation described by pWInfo.
2438*/
2439static Bitmask codeOneLoopStart(
2440 WhereInfo *pWInfo, /* Complete information about the WHERE clause */
2441 int iLevel, /* Which level of pWInfo->a[] should be coded */
drh336a5302009-04-24 15:46:21 +00002442 u16 wctrlFlags, /* One of the WHERE_* flags defined in sqliteInt.h */
drh111a6a72008-12-21 03:51:16 +00002443 Bitmask notReady /* Which tables are currently available */
2444){
2445 int j, k; /* Loop counters */
2446 int iCur; /* The VDBE cursor for the table */
2447 int addrNxt; /* Where to jump to continue with the next IN case */
2448 int omitTable; /* True if we use the index only */
2449 int bRev; /* True if we need to scan in reverse order */
2450 WhereLevel *pLevel; /* The where level to be coded */
2451 WhereClause *pWC; /* Decomposition of the entire WHERE clause */
2452 WhereTerm *pTerm; /* A WHERE clause term */
2453 Parse *pParse; /* Parsing context */
2454 Vdbe *v; /* The prepared stmt under constructions */
2455 struct SrcList_item *pTabItem; /* FROM clause term being coded */
drh23d04d52008-12-23 23:56:22 +00002456 int addrBrk; /* Jump here to break out of the loop */
2457 int addrCont; /* Jump here to continue with next cycle */
drh61495262009-04-22 15:32:59 +00002458 int iRowidReg = 0; /* Rowid is stored in this register, if not zero */
2459 int iReleaseReg = 0; /* Temp register to free before returning */
drh111a6a72008-12-21 03:51:16 +00002460
2461 pParse = pWInfo->pParse;
2462 v = pParse->pVdbe;
2463 pWC = pWInfo->pWC;
2464 pLevel = &pWInfo->a[iLevel];
2465 pTabItem = &pWInfo->pTabList->a[pLevel->iFrom];
2466 iCur = pTabItem->iCursor;
2467 bRev = (pLevel->plan.wsFlags & WHERE_REVERSE)!=0;
danielk19771d461462009-04-21 09:02:45 +00002468 omitTable = (pLevel->plan.wsFlags & WHERE_IDX_ONLY)!=0
drh336a5302009-04-24 15:46:21 +00002469 && (wctrlFlags & WHERE_FORCE_TABLE)==0;
drh111a6a72008-12-21 03:51:16 +00002470
2471 /* Create labels for the "break" and "continue" instructions
2472 ** for the current loop. Jump to addrBrk to break out of a loop.
2473 ** Jump to cont to go immediately to the next iteration of the
2474 ** loop.
2475 **
2476 ** When there is an IN operator, we also have a "addrNxt" label that
2477 ** means to continue with the next IN value combination. When
2478 ** there are no IN operators in the constraints, the "addrNxt" label
2479 ** is the same as "addrBrk".
2480 */
2481 addrBrk = pLevel->addrBrk = pLevel->addrNxt = sqlite3VdbeMakeLabel(v);
2482 addrCont = pLevel->addrCont = sqlite3VdbeMakeLabel(v);
2483
2484 /* If this is the right table of a LEFT OUTER JOIN, allocate and
2485 ** initialize a memory cell that records if this table matches any
2486 ** row of the left table of the join.
2487 */
2488 if( pLevel->iFrom>0 && (pTabItem[0].jointype & JT_LEFT)!=0 ){
2489 pLevel->iLeftJoin = ++pParse->nMem;
2490 sqlite3VdbeAddOp2(v, OP_Integer, 0, pLevel->iLeftJoin);
2491 VdbeComment((v, "init LEFT JOIN no-match flag"));
2492 }
2493
2494#ifndef SQLITE_OMIT_VIRTUALTABLE
2495 if( (pLevel->plan.wsFlags & WHERE_VIRTUALTABLE)!=0 ){
2496 /* Case 0: The table is a virtual-table. Use the VFilter and VNext
2497 ** to access the data.
2498 */
2499 int iReg; /* P3 Value for OP_VFilter */
2500 sqlite3_index_info *pVtabIdx = pLevel->plan.u.pVtabIdx;
2501 int nConstraint = pVtabIdx->nConstraint;
2502 struct sqlite3_index_constraint_usage *aUsage =
2503 pVtabIdx->aConstraintUsage;
2504 const struct sqlite3_index_constraint *aConstraint =
2505 pVtabIdx->aConstraint;
2506
2507 iReg = sqlite3GetTempRange(pParse, nConstraint+2);
drh111a6a72008-12-21 03:51:16 +00002508 for(j=1; j<=nConstraint; j++){
2509 for(k=0; k<nConstraint; k++){
2510 if( aUsage[k].argvIndex==j ){
2511 int iTerm = aConstraint[k].iTermOffset;
drh111a6a72008-12-21 03:51:16 +00002512 sqlite3ExprCode(pParse, pWC->a[iTerm].pExpr->pRight, iReg+j+1);
2513 break;
2514 }
2515 }
2516 if( k==nConstraint ) break;
2517 }
drh111a6a72008-12-21 03:51:16 +00002518 sqlite3VdbeAddOp2(v, OP_Integer, pVtabIdx->idxNum, iReg);
2519 sqlite3VdbeAddOp2(v, OP_Integer, j-1, iReg+1);
2520 sqlite3VdbeAddOp4(v, OP_VFilter, iCur, addrBrk, iReg, pVtabIdx->idxStr,
2521 pVtabIdx->needToFreeIdxStr ? P4_MPRINTF : P4_STATIC);
drh111a6a72008-12-21 03:51:16 +00002522 pVtabIdx->needToFreeIdxStr = 0;
2523 for(j=0; j<nConstraint; j++){
2524 if( aUsage[j].omit ){
2525 int iTerm = aConstraint[j].iTermOffset;
2526 disableTerm(pLevel, &pWC->a[iTerm]);
2527 }
2528 }
2529 pLevel->op = OP_VNext;
2530 pLevel->p1 = iCur;
2531 pLevel->p2 = sqlite3VdbeCurrentAddr(v);
drh23d04d52008-12-23 23:56:22 +00002532 sqlite3ReleaseTempRange(pParse, iReg, nConstraint+2);
drh111a6a72008-12-21 03:51:16 +00002533 }else
2534#endif /* SQLITE_OMIT_VIRTUALTABLE */
2535
2536 if( pLevel->plan.wsFlags & WHERE_ROWID_EQ ){
2537 /* Case 1: We can directly reference a single row using an
2538 ** equality comparison against the ROWID field. Or
2539 ** we reference multiple rows using a "rowid IN (...)"
2540 ** construct.
2541 */
danielk19771d461462009-04-21 09:02:45 +00002542 iReleaseReg = sqlite3GetTempReg(pParse);
drh111a6a72008-12-21 03:51:16 +00002543 pTerm = findTerm(pWC, iCur, -1, notReady, WO_EQ|WO_IN, 0);
2544 assert( pTerm!=0 );
2545 assert( pTerm->pExpr!=0 );
2546 assert( pTerm->leftCursor==iCur );
2547 assert( omitTable==0 );
danielk19771d461462009-04-21 09:02:45 +00002548 iRowidReg = codeEqualityTerm(pParse, pTerm, pLevel, iReleaseReg);
drh111a6a72008-12-21 03:51:16 +00002549 addrNxt = pLevel->addrNxt;
danielk19771d461462009-04-21 09:02:45 +00002550 sqlite3VdbeAddOp2(v, OP_MustBeInt, iRowidReg, addrNxt);
2551 sqlite3VdbeAddOp3(v, OP_NotExists, iCur, addrNxt, iRowidReg);
drhceea3322009-04-23 13:22:42 +00002552 sqlite3ExprCacheStore(pParse, iCur, -1, iRowidReg);
drh111a6a72008-12-21 03:51:16 +00002553 VdbeComment((v, "pk"));
2554 pLevel->op = OP_Noop;
2555 }else if( pLevel->plan.wsFlags & WHERE_ROWID_RANGE ){
2556 /* Case 2: We have an inequality comparison against the ROWID field.
2557 */
2558 int testOp = OP_Noop;
2559 int start;
2560 int memEndValue = 0;
2561 WhereTerm *pStart, *pEnd;
2562
2563 assert( omitTable==0 );
2564 pStart = findTerm(pWC, iCur, -1, notReady, WO_GT|WO_GE, 0);
2565 pEnd = findTerm(pWC, iCur, -1, notReady, WO_LT|WO_LE, 0);
2566 if( bRev ){
2567 pTerm = pStart;
2568 pStart = pEnd;
2569 pEnd = pTerm;
2570 }
2571 if( pStart ){
2572 Expr *pX; /* The expression that defines the start bound */
2573 int r1, rTemp; /* Registers for holding the start boundary */
2574
2575 /* The following constant maps TK_xx codes into corresponding
2576 ** seek opcodes. It depends on a particular ordering of TK_xx
2577 */
2578 const u8 aMoveOp[] = {
2579 /* TK_GT */ OP_SeekGt,
2580 /* TK_LE */ OP_SeekLe,
2581 /* TK_LT */ OP_SeekLt,
2582 /* TK_GE */ OP_SeekGe
2583 };
2584 assert( TK_LE==TK_GT+1 ); /* Make sure the ordering.. */
2585 assert( TK_LT==TK_GT+2 ); /* ... of the TK_xx values... */
2586 assert( TK_GE==TK_GT+3 ); /* ... is correcct. */
2587
2588 pX = pStart->pExpr;
2589 assert( pX!=0 );
2590 assert( pStart->leftCursor==iCur );
2591 r1 = sqlite3ExprCodeTemp(pParse, pX->pRight, &rTemp);
2592 sqlite3VdbeAddOp3(v, aMoveOp[pX->op-TK_GT], iCur, addrBrk, r1);
2593 VdbeComment((v, "pk"));
2594 sqlite3ExprCacheAffinityChange(pParse, r1, 1);
2595 sqlite3ReleaseTempReg(pParse, rTemp);
2596 disableTerm(pLevel, pStart);
2597 }else{
2598 sqlite3VdbeAddOp2(v, bRev ? OP_Last : OP_Rewind, iCur, addrBrk);
2599 }
2600 if( pEnd ){
2601 Expr *pX;
2602 pX = pEnd->pExpr;
2603 assert( pX!=0 );
2604 assert( pEnd->leftCursor==iCur );
2605 memEndValue = ++pParse->nMem;
2606 sqlite3ExprCode(pParse, pX->pRight, memEndValue);
2607 if( pX->op==TK_LT || pX->op==TK_GT ){
2608 testOp = bRev ? OP_Le : OP_Ge;
2609 }else{
2610 testOp = bRev ? OP_Lt : OP_Gt;
2611 }
2612 disableTerm(pLevel, pEnd);
2613 }
2614 start = sqlite3VdbeCurrentAddr(v);
2615 pLevel->op = bRev ? OP_Prev : OP_Next;
2616 pLevel->p1 = iCur;
2617 pLevel->p2 = start;
drhca8c4662008-12-28 20:47:02 +00002618 pLevel->p5 = (pStart==0 && pEnd==0) ?1:0;
danielk19771d461462009-04-21 09:02:45 +00002619 if( testOp!=OP_Noop ){
2620 iRowidReg = iReleaseReg = sqlite3GetTempReg(pParse);
2621 sqlite3VdbeAddOp2(v, OP_Rowid, iCur, iRowidReg);
drhceea3322009-04-23 13:22:42 +00002622 sqlite3ExprCacheStore(pParse, iCur, -1, iRowidReg);
danielk19771d461462009-04-21 09:02:45 +00002623 sqlite3VdbeAddOp3(v, testOp, memEndValue, addrBrk, iRowidReg);
2624 sqlite3VdbeChangeP5(v, SQLITE_AFF_NUMERIC | SQLITE_JUMPIFNULL);
drh111a6a72008-12-21 03:51:16 +00002625 }
2626 }else if( pLevel->plan.wsFlags & (WHERE_COLUMN_RANGE|WHERE_COLUMN_EQ) ){
2627 /* Case 3: A scan using an index.
2628 **
2629 ** The WHERE clause may contain zero or more equality
2630 ** terms ("==" or "IN" operators) that refer to the N
2631 ** left-most columns of the index. It may also contain
2632 ** inequality constraints (>, <, >= or <=) on the indexed
2633 ** column that immediately follows the N equalities. Only
2634 ** the right-most column can be an inequality - the rest must
2635 ** use the "==" and "IN" operators. For example, if the
2636 ** index is on (x,y,z), then the following clauses are all
2637 ** optimized:
2638 **
2639 ** x=5
2640 ** x=5 AND y=10
2641 ** x=5 AND y<10
2642 ** x=5 AND y>5 AND y<10
2643 ** x=5 AND y=5 AND z<=10
2644 **
2645 ** The z<10 term of the following cannot be used, only
2646 ** the x=5 term:
2647 **
2648 ** x=5 AND z<10
2649 **
2650 ** N may be zero if there are inequality constraints.
2651 ** If there are no inequality constraints, then N is at
2652 ** least one.
2653 **
2654 ** This case is also used when there are no WHERE clause
2655 ** constraints but an index is selected anyway, in order
2656 ** to force the output order to conform to an ORDER BY.
2657 */
2658 int aStartOp[] = {
2659 0,
2660 0,
2661 OP_Rewind, /* 2: (!start_constraints && startEq && !bRev) */
2662 OP_Last, /* 3: (!start_constraints && startEq && bRev) */
2663 OP_SeekGt, /* 4: (start_constraints && !startEq && !bRev) */
2664 OP_SeekLt, /* 5: (start_constraints && !startEq && bRev) */
2665 OP_SeekGe, /* 6: (start_constraints && startEq && !bRev) */
2666 OP_SeekLe /* 7: (start_constraints && startEq && bRev) */
2667 };
2668 int aEndOp[] = {
2669 OP_Noop, /* 0: (!end_constraints) */
2670 OP_IdxGE, /* 1: (end_constraints && !bRev) */
2671 OP_IdxLT /* 2: (end_constraints && bRev) */
2672 };
2673 int nEq = pLevel->plan.nEq;
2674 int isMinQuery = 0; /* If this is an optimized SELECT min(x).. */
2675 int regBase; /* Base register holding constraint values */
2676 int r1; /* Temp register */
2677 WhereTerm *pRangeStart = 0; /* Inequality constraint at range start */
2678 WhereTerm *pRangeEnd = 0; /* Inequality constraint at range end */
2679 int startEq; /* True if range start uses ==, >= or <= */
2680 int endEq; /* True if range end uses ==, >= or <= */
2681 int start_constraints; /* Start of range is constrained */
2682 int nConstraint; /* Number of constraint terms */
2683 Index *pIdx; /* The index we will be using */
2684 int iIdxCur; /* The VDBE cursor for the index */
drh6df2acd2008-12-28 16:55:25 +00002685 int nExtraReg = 0; /* Number of extra registers needed */
2686 int op; /* Instruction opcode */
drh111a6a72008-12-21 03:51:16 +00002687
2688 pIdx = pLevel->plan.u.pIdx;
2689 iIdxCur = pLevel->iIdxCur;
2690 k = pIdx->aiColumn[nEq]; /* Column for inequality constraints */
2691
drh111a6a72008-12-21 03:51:16 +00002692 /* If this loop satisfies a sort order (pOrderBy) request that
2693 ** was passed to this function to implement a "SELECT min(x) ..."
2694 ** query, then the caller will only allow the loop to run for
2695 ** a single iteration. This means that the first row returned
2696 ** should not have a NULL value stored in 'x'. If column 'x' is
2697 ** the first one after the nEq equality constraints in the index,
2698 ** this requires some special handling.
2699 */
2700 if( (wctrlFlags&WHERE_ORDERBY_MIN)!=0
2701 && (pLevel->plan.wsFlags&WHERE_ORDERBY)
2702 && (pIdx->nColumn>nEq)
2703 ){
2704 /* assert( pOrderBy->nExpr==1 ); */
2705 /* assert( pOrderBy->a[0].pExpr->iColumn==pIdx->aiColumn[nEq] ); */
2706 isMinQuery = 1;
drh6df2acd2008-12-28 16:55:25 +00002707 nExtraReg = 1;
drh111a6a72008-12-21 03:51:16 +00002708 }
2709
2710 /* Find any inequality constraint terms for the start and end
2711 ** of the range.
2712 */
2713 if( pLevel->plan.wsFlags & WHERE_TOP_LIMIT ){
2714 pRangeEnd = findTerm(pWC, iCur, k, notReady, (WO_LT|WO_LE), pIdx);
drh6df2acd2008-12-28 16:55:25 +00002715 nExtraReg = 1;
drh111a6a72008-12-21 03:51:16 +00002716 }
2717 if( pLevel->plan.wsFlags & WHERE_BTM_LIMIT ){
2718 pRangeStart = findTerm(pWC, iCur, k, notReady, (WO_GT|WO_GE), pIdx);
drh6df2acd2008-12-28 16:55:25 +00002719 nExtraReg = 1;
drh111a6a72008-12-21 03:51:16 +00002720 }
2721
drh6df2acd2008-12-28 16:55:25 +00002722 /* Generate code to evaluate all constraint terms using == or IN
2723 ** and store the values of those terms in an array of registers
2724 ** starting at regBase.
2725 */
2726 regBase = codeAllEqualityTerms(pParse, pLevel, pWC, notReady, nExtraReg);
2727 addrNxt = pLevel->addrNxt;
2728
2729
drh111a6a72008-12-21 03:51:16 +00002730 /* If we are doing a reverse order scan on an ascending index, or
2731 ** a forward order scan on a descending index, interchange the
2732 ** start and end terms (pRangeStart and pRangeEnd).
2733 */
2734 if( bRev==(pIdx->aSortOrder[nEq]==SQLITE_SO_ASC) ){
2735 SWAP(WhereTerm *, pRangeEnd, pRangeStart);
2736 }
2737
2738 testcase( pRangeStart && pRangeStart->eOperator & WO_LE );
2739 testcase( pRangeStart && pRangeStart->eOperator & WO_GE );
2740 testcase( pRangeEnd && pRangeEnd->eOperator & WO_LE );
2741 testcase( pRangeEnd && pRangeEnd->eOperator & WO_GE );
2742 startEq = !pRangeStart || pRangeStart->eOperator & (WO_LE|WO_GE);
2743 endEq = !pRangeEnd || pRangeEnd->eOperator & (WO_LE|WO_GE);
2744 start_constraints = pRangeStart || nEq>0;
2745
2746 /* Seek the index cursor to the start of the range. */
2747 nConstraint = nEq;
2748 if( pRangeStart ){
drh111a6a72008-12-21 03:51:16 +00002749 sqlite3ExprCode(pParse, pRangeStart->pExpr->pRight, regBase+nEq);
drh111a6a72008-12-21 03:51:16 +00002750 sqlite3VdbeAddOp2(v, OP_IsNull, regBase+nEq, addrNxt);
2751 nConstraint++;
2752 }else if( isMinQuery ){
2753 sqlite3VdbeAddOp2(v, OP_Null, 0, regBase+nEq);
2754 nConstraint++;
2755 startEq = 0;
2756 start_constraints = 1;
2757 }
2758 codeApplyAffinity(pParse, regBase, nConstraint, pIdx);
2759 op = aStartOp[(start_constraints<<2) + (startEq<<1) + bRev];
2760 assert( op!=0 );
2761 testcase( op==OP_Rewind );
2762 testcase( op==OP_Last );
2763 testcase( op==OP_SeekGt );
2764 testcase( op==OP_SeekGe );
2765 testcase( op==OP_SeekLe );
2766 testcase( op==OP_SeekLt );
2767 sqlite3VdbeAddOp4(v, op, iIdxCur, addrNxt, regBase,
2768 SQLITE_INT_TO_PTR(nConstraint), P4_INT32);
2769
2770 /* Load the value for the inequality constraint at the end of the
2771 ** range (if any).
2772 */
2773 nConstraint = nEq;
2774 if( pRangeEnd ){
drhceea3322009-04-23 13:22:42 +00002775 sqlite3ExprCacheRemove(pParse, regBase+nEq);
drh111a6a72008-12-21 03:51:16 +00002776 sqlite3ExprCode(pParse, pRangeEnd->pExpr->pRight, regBase+nEq);
2777 sqlite3VdbeAddOp2(v, OP_IsNull, regBase+nEq, addrNxt);
2778 codeApplyAffinity(pParse, regBase, nEq+1, pIdx);
2779 nConstraint++;
2780 }
2781
2782 /* Top of the loop body */
2783 pLevel->p2 = sqlite3VdbeCurrentAddr(v);
2784
2785 /* Check if the index cursor is past the end of the range. */
2786 op = aEndOp[(pRangeEnd || nEq) * (1 + bRev)];
2787 testcase( op==OP_Noop );
2788 testcase( op==OP_IdxGE );
2789 testcase( op==OP_IdxLT );
drh6df2acd2008-12-28 16:55:25 +00002790 if( op!=OP_Noop ){
2791 sqlite3VdbeAddOp4(v, op, iIdxCur, addrNxt, regBase,
2792 SQLITE_INT_TO_PTR(nConstraint), P4_INT32);
2793 sqlite3VdbeChangeP5(v, endEq!=bRev ?1:0);
2794 }
drh111a6a72008-12-21 03:51:16 +00002795
2796 /* If there are inequality constraints, check that the value
2797 ** of the table column that the inequality contrains is not NULL.
2798 ** If it is, jump to the next iteration of the loop.
2799 */
2800 r1 = sqlite3GetTempReg(pParse);
2801 testcase( pLevel->plan.wsFlags & WHERE_BTM_LIMIT );
2802 testcase( pLevel->plan.wsFlags & WHERE_TOP_LIMIT );
2803 if( pLevel->plan.wsFlags & (WHERE_BTM_LIMIT|WHERE_TOP_LIMIT) ){
2804 sqlite3VdbeAddOp3(v, OP_Column, iIdxCur, nEq, r1);
2805 sqlite3VdbeAddOp2(v, OP_IsNull, r1, addrCont);
2806 }
danielk19771d461462009-04-21 09:02:45 +00002807 sqlite3ReleaseTempReg(pParse, r1);
drh111a6a72008-12-21 03:51:16 +00002808
2809 /* Seek the table cursor, if required */
drh23d04d52008-12-23 23:56:22 +00002810 disableTerm(pLevel, pRangeStart);
2811 disableTerm(pLevel, pRangeEnd);
danielk19771d461462009-04-21 09:02:45 +00002812 if( !omitTable ){
2813 iRowidReg = iReleaseReg = sqlite3GetTempReg(pParse);
2814 sqlite3VdbeAddOp2(v, OP_IdxRowid, iIdxCur, iRowidReg);
drhceea3322009-04-23 13:22:42 +00002815 sqlite3ExprCacheStore(pParse, iCur, -1, iRowidReg);
danielk19771d461462009-04-21 09:02:45 +00002816 sqlite3VdbeAddOp2(v, OP_Seek, iCur, iRowidReg); /* Deferred seek */
drh111a6a72008-12-21 03:51:16 +00002817 }
drh111a6a72008-12-21 03:51:16 +00002818
2819 /* Record the instruction used to terminate the loop. Disable
2820 ** WHERE clause terms made redundant by the index range scan.
2821 */
2822 pLevel->op = bRev ? OP_Prev : OP_Next;
2823 pLevel->p1 = iIdxCur;
drhdd5f5a62008-12-23 13:35:23 +00002824 }else
2825
drh23d04d52008-12-23 23:56:22 +00002826#ifndef SQLITE_OMIT_OR_OPTIMIZATION
drhdd5f5a62008-12-23 13:35:23 +00002827 if( pLevel->plan.wsFlags & WHERE_MULTI_OR ){
drh111a6a72008-12-21 03:51:16 +00002828 /* Case 4: Two or more separately indexed terms connected by OR
2829 **
2830 ** Example:
2831 **
2832 ** CREATE TABLE t1(a,b,c,d);
2833 ** CREATE INDEX i1 ON t1(a);
2834 ** CREATE INDEX i2 ON t1(b);
2835 ** CREATE INDEX i3 ON t1(c);
2836 **
2837 ** SELECT * FROM t1 WHERE a=5 OR b=7 OR (c=11 AND d=13)
2838 **
2839 ** In the example, there are three indexed terms connected by OR.
danielk19771d461462009-04-21 09:02:45 +00002840 ** The top of the loop looks like this:
drh111a6a72008-12-21 03:51:16 +00002841 **
drh1b26c7c2009-04-22 02:15:47 +00002842 ** Null 1 # Zero the rowset in reg 1
drh111a6a72008-12-21 03:51:16 +00002843 **
danielk19771d461462009-04-21 09:02:45 +00002844 ** Then, for each indexed term, the following. The arguments to
drh1b26c7c2009-04-22 02:15:47 +00002845 ** RowSetTest are such that the rowid of the current row is inserted
2846 ** into the RowSet. If it is already present, control skips the
danielk19771d461462009-04-21 09:02:45 +00002847 ** Gosub opcode and jumps straight to the code generated by WhereEnd().
drh111a6a72008-12-21 03:51:16 +00002848 **
danielk19771d461462009-04-21 09:02:45 +00002849 ** sqlite3WhereBegin(<term>)
drh1b26c7c2009-04-22 02:15:47 +00002850 ** RowSetTest # Insert rowid into rowset
danielk19771d461462009-04-21 09:02:45 +00002851 ** Gosub 2 A
2852 ** sqlite3WhereEnd()
2853 **
2854 ** Following the above, code to terminate the loop. Label A, the target
2855 ** of the Gosub above, jumps to the instruction right after the Goto.
2856 **
drh1b26c7c2009-04-22 02:15:47 +00002857 ** Null 1 # Zero the rowset in reg 1
danielk19771d461462009-04-21 09:02:45 +00002858 ** Goto B # The loop is finished.
2859 **
2860 ** A: <loop body> # Return data, whatever.
2861 **
2862 ** Return 2 # Jump back to the Gosub
2863 **
2864 ** B: <after the loop>
2865 **
drh111a6a72008-12-21 03:51:16 +00002866 */
drh111a6a72008-12-21 03:51:16 +00002867 WhereClause *pOrWc; /* The OR-clause broken out into subterms */
danielk19771d461462009-04-21 09:02:45 +00002868 WhereTerm *pFinal; /* Final subterm within the OR-clause. */
drhdd5f5a62008-12-23 13:35:23 +00002869 SrcList oneTab; /* Shortened table list */
danielk19771d461462009-04-21 09:02:45 +00002870
2871 int regReturn = ++pParse->nMem; /* Register used with OP_Gosub */
drh336a5302009-04-24 15:46:21 +00002872 int regRowset; /* Register for RowSet object */
2873 int regRowid; /* Register holding rowid */
danielk19771d461462009-04-21 09:02:45 +00002874 int iLoopBody = sqlite3VdbeMakeLabel(v); /* Start of loop body */
2875 int iRetInit; /* Address of regReturn init */
2876 int ii;
drh111a6a72008-12-21 03:51:16 +00002877
2878 pTerm = pLevel->plan.u.pTerm;
2879 assert( pTerm!=0 );
2880 assert( pTerm->eOperator==WO_OR );
2881 assert( (pTerm->wtFlags & TERM_ORINFO)!=0 );
2882 pOrWc = &pTerm->u.pOrInfo->wc;
danielk19771d461462009-04-21 09:02:45 +00002883 pFinal = &pOrWc->a[pOrWc->nTerm-1];
drh23d04d52008-12-23 23:56:22 +00002884
danielk19771d461462009-04-21 09:02:45 +00002885 /* Set up a SrcList containing just the table being scanned by this loop. */
drhdd5f5a62008-12-23 13:35:23 +00002886 oneTab.nSrc = 1;
2887 oneTab.nAlloc = 1;
2888 oneTab.a[0] = *pTabItem;
danielk19771d461462009-04-21 09:02:45 +00002889
drh1b26c7c2009-04-22 02:15:47 +00002890 /* Initialize the rowset register to contain NULL. An SQL NULL is
2891 ** equivalent to an empty rowset.
danielk19771d461462009-04-21 09:02:45 +00002892 **
2893 ** Also initialize regReturn to contain the address of the instruction
2894 ** immediately following the OP_Return at the bottom of the loop. This
2895 ** is required in a few obscure LEFT JOIN cases where control jumps
2896 ** over the top of the loop into the body of it. In this case the
2897 ** correct response for the end-of-loop code (the OP_Return) is to
2898 ** fall through to the next instruction, just as an OP_Next does if
2899 ** called on an uninitialized cursor.
2900 */
drh336a5302009-04-24 15:46:21 +00002901 if( (wctrlFlags & WHERE_DUPLICATES_OK)==0 ){
2902 regRowset = ++pParse->nMem;
2903 regRowid = ++pParse->nMem;
2904 sqlite3VdbeAddOp2(v, OP_Null, 0, regRowset);
2905 }
danielk19771d461462009-04-21 09:02:45 +00002906 iRetInit = sqlite3VdbeAddOp2(v, OP_Integer, 0, regReturn);
2907
danielk19771d461462009-04-21 09:02:45 +00002908 for(ii=0; ii<pOrWc->nTerm; ii++){
2909 WhereTerm *pOrTerm = &pOrWc->a[ii];
2910 if( pOrTerm->leftCursor==iCur || pOrTerm->eOperator==WO_AND ){
2911 WhereInfo *pSubWInfo; /* Info for single OR-term scan */
2912
2913 /* Loop through table entries that match term pOrTerm. */
drh336a5302009-04-24 15:46:21 +00002914 pSubWInfo = sqlite3WhereBegin(pParse, &oneTab, pOrTerm->pExpr, 0,
2915 WHERE_OMIT_OPEN | WHERE_OMIT_CLOSE | WHERE_FORCE_TABLE);
danielk19771d461462009-04-21 09:02:45 +00002916 if( pSubWInfo ){
drh336a5302009-04-24 15:46:21 +00002917 if( (wctrlFlags & WHERE_DUPLICATES_OK)==0 ){
2918 int iSet = ((ii==pOrWc->nTerm-1)?-1:ii);
2919 int r;
2920 r = sqlite3ExprCodeGetColumn(pParse, pTabItem->pTab, -1, iCur,
2921 regRowid, 0);
2922 sqlite3VdbeAddOp4(v, OP_RowSetTest, regRowset,
shane60a4b532009-05-06 18:57:09 +00002923 sqlite3VdbeCurrentAddr(v)+2,
2924 r, SQLITE_INT_TO_PTR(iSet), P4_INT32);
drh336a5302009-04-24 15:46:21 +00002925 }
danielk19771d461462009-04-21 09:02:45 +00002926 sqlite3VdbeAddOp2(v, OP_Gosub, regReturn, iLoopBody);
2927
2928 /* Finish the loop through table entries that match term pOrTerm. */
2929 sqlite3WhereEnd(pSubWInfo);
2930 }
drhdd5f5a62008-12-23 13:35:23 +00002931 }
2932 }
danielk19771d461462009-04-21 09:02:45 +00002933 sqlite3VdbeChangeP1(v, iRetInit, sqlite3VdbeCurrentAddr(v));
drh336a5302009-04-24 15:46:21 +00002934 /* sqlite3VdbeAddOp2(v, OP_Null, 0, regRowset); */
danielk19771d461462009-04-21 09:02:45 +00002935 sqlite3VdbeAddOp2(v, OP_Goto, 0, pLevel->addrBrk);
2936 sqlite3VdbeResolveLabel(v, iLoopBody);
2937
2938 pLevel->op = OP_Return;
2939 pLevel->p1 = regReturn;
drh23d04d52008-12-23 23:56:22 +00002940 disableTerm(pLevel, pTerm);
drhdd5f5a62008-12-23 13:35:23 +00002941 }else
drh23d04d52008-12-23 23:56:22 +00002942#endif /* SQLITE_OMIT_OR_OPTIMIZATION */
drhdd5f5a62008-12-23 13:35:23 +00002943
2944 {
drh111a6a72008-12-21 03:51:16 +00002945 /* Case 5: There is no usable index. We must do a complete
2946 ** scan of the entire table.
2947 */
drh699b3d42009-02-23 16:52:07 +00002948 static const u8 aStep[] = { OP_Next, OP_Prev };
2949 static const u8 aStart[] = { OP_Rewind, OP_Last };
2950 assert( bRev==0 || bRev==1 );
drh111a6a72008-12-21 03:51:16 +00002951 assert( omitTable==0 );
drh699b3d42009-02-23 16:52:07 +00002952 pLevel->op = aStep[bRev];
drh111a6a72008-12-21 03:51:16 +00002953 pLevel->p1 = iCur;
drh699b3d42009-02-23 16:52:07 +00002954 pLevel->p2 = 1 + sqlite3VdbeAddOp2(v, aStart[bRev], iCur, addrBrk);
drh111a6a72008-12-21 03:51:16 +00002955 pLevel->p5 = SQLITE_STMTSTATUS_FULLSCAN_STEP;
2956 }
2957 notReady &= ~getMask(pWC->pMaskSet, iCur);
2958
2959 /* Insert code to test every subexpression that can be completely
2960 ** computed using the current set of tables.
2961 */
2962 k = 0;
2963 for(pTerm=pWC->a, j=pWC->nTerm; j>0; j--, pTerm++){
2964 Expr *pE;
2965 testcase( pTerm->wtFlags & TERM_VIRTUAL );
2966 testcase( pTerm->wtFlags & TERM_CODED );
2967 if( pTerm->wtFlags & (TERM_VIRTUAL|TERM_CODED) ) continue;
2968 if( (pTerm->prereqAll & notReady)!=0 ) continue;
2969 pE = pTerm->pExpr;
2970 assert( pE!=0 );
2971 if( pLevel->iLeftJoin && !ExprHasProperty(pE, EP_FromJoin) ){
2972 continue;
2973 }
drh111a6a72008-12-21 03:51:16 +00002974 sqlite3ExprIfFalse(pParse, pE, addrCont, SQLITE_JUMPIFNULL);
drh111a6a72008-12-21 03:51:16 +00002975 k = 1;
2976 pTerm->wtFlags |= TERM_CODED;
2977 }
2978
2979 /* For a LEFT OUTER JOIN, generate code that will record the fact that
2980 ** at least one row of the right table has matched the left table.
2981 */
2982 if( pLevel->iLeftJoin ){
2983 pLevel->addrFirst = sqlite3VdbeCurrentAddr(v);
2984 sqlite3VdbeAddOp2(v, OP_Integer, 1, pLevel->iLeftJoin);
2985 VdbeComment((v, "record LEFT JOIN hit"));
drhceea3322009-04-23 13:22:42 +00002986 sqlite3ExprCacheClear(pParse);
drh111a6a72008-12-21 03:51:16 +00002987 for(pTerm=pWC->a, j=0; j<pWC->nTerm; j++, pTerm++){
2988 testcase( pTerm->wtFlags & TERM_VIRTUAL );
2989 testcase( pTerm->wtFlags & TERM_CODED );
2990 if( pTerm->wtFlags & (TERM_VIRTUAL|TERM_CODED) ) continue;
2991 if( (pTerm->prereqAll & notReady)!=0 ) continue;
2992 assert( pTerm->pExpr );
2993 sqlite3ExprIfFalse(pParse, pTerm->pExpr, addrCont, SQLITE_JUMPIFNULL);
2994 pTerm->wtFlags |= TERM_CODED;
2995 }
2996 }
danielk19771d461462009-04-21 09:02:45 +00002997 sqlite3ReleaseTempReg(pParse, iReleaseReg);
drh23d04d52008-12-23 23:56:22 +00002998
drh111a6a72008-12-21 03:51:16 +00002999 return notReady;
3000}
3001
drh549c8b62005-09-19 13:15:23 +00003002#if defined(SQLITE_TEST)
drh84bfda42005-07-15 13:05:21 +00003003/*
3004** The following variable holds a text description of query plan generated
3005** by the most recent call to sqlite3WhereBegin(). Each call to WhereBegin
3006** overwrites the previous. This information is used for testing and
3007** analysis only.
3008*/
3009char sqlite3_query_plan[BMS*2*40]; /* Text of the join */
3010static int nQPlan = 0; /* Next free slow in _query_plan[] */
3011
3012#endif /* SQLITE_TEST */
3013
3014
drh9eff6162006-06-12 21:59:13 +00003015/*
3016** Free a WhereInfo structure
3017*/
drh10fe8402008-10-11 16:47:35 +00003018static void whereInfoFree(sqlite3 *db, WhereInfo *pWInfo){
drh9eff6162006-06-12 21:59:13 +00003019 if( pWInfo ){
3020 int i;
3021 for(i=0; i<pWInfo->nLevel; i++){
drh4be8b512006-06-13 23:51:34 +00003022 sqlite3_index_info *pInfo = pWInfo->a[i].pIdxInfo;
3023 if( pInfo ){
danielk19771d461462009-04-21 09:02:45 +00003024 /* assert( pInfo->needToFreeIdxStr==0 || db->mallocFailed ); */
danielk197780442942008-12-24 11:25:39 +00003025 if( pInfo->needToFreeIdxStr ){
3026 sqlite3_free(pInfo->idxStr);
danielk1977be229652009-03-20 14:18:51 +00003027 }
drh633e6d52008-07-28 19:34:53 +00003028 sqlite3DbFree(db, pInfo);
danielk1977be8a7832006-06-13 15:00:54 +00003029 }
drh9eff6162006-06-12 21:59:13 +00003030 }
drh111a6a72008-12-21 03:51:16 +00003031 whereClauseClear(pWInfo->pWC);
drh633e6d52008-07-28 19:34:53 +00003032 sqlite3DbFree(db, pWInfo);
drh9eff6162006-06-12 21:59:13 +00003033 }
3034}
3035
drh94a11212004-09-25 13:12:14 +00003036
3037/*
drhe3184742002-06-19 14:27:05 +00003038** Generate the beginning of the loop used for WHERE clause processing.
drhacf3b982005-01-03 01:27:18 +00003039** The return value is a pointer to an opaque structure that contains
drh75897232000-05-29 14:26:00 +00003040** information needed to terminate the loop. Later, the calling routine
danielk19774adee202004-05-08 08:23:19 +00003041** should invoke sqlite3WhereEnd() with the return value of this function
drh75897232000-05-29 14:26:00 +00003042** in order to complete the WHERE clause processing.
3043**
3044** If an error occurs, this routine returns NULL.
drhc27a1ce2002-06-14 20:58:45 +00003045**
3046** The basic idea is to do a nested loop, one loop for each table in
3047** the FROM clause of a select. (INSERT and UPDATE statements are the
3048** same as a SELECT with only a single table in the FROM clause.) For
3049** example, if the SQL is this:
3050**
3051** SELECT * FROM t1, t2, t3 WHERE ...;
3052**
3053** Then the code generated is conceptually like the following:
3054**
3055** foreach row1 in t1 do \ Code generated
danielk19774adee202004-05-08 08:23:19 +00003056** foreach row2 in t2 do |-- by sqlite3WhereBegin()
drhc27a1ce2002-06-14 20:58:45 +00003057** foreach row3 in t3 do /
3058** ...
3059** end \ Code generated
danielk19774adee202004-05-08 08:23:19 +00003060** end |-- by sqlite3WhereEnd()
drhc27a1ce2002-06-14 20:58:45 +00003061** end /
3062**
drh29dda4a2005-07-21 18:23:20 +00003063** Note that the loops might not be nested in the order in which they
3064** appear in the FROM clause if a different order is better able to make
drh51147ba2005-07-23 22:59:55 +00003065** use of indices. Note also that when the IN operator appears in
3066** the WHERE clause, it might result in additional nested loops for
3067** scanning through all values on the right-hand side of the IN.
drh29dda4a2005-07-21 18:23:20 +00003068**
drhc27a1ce2002-06-14 20:58:45 +00003069** There are Btree cursors associated with each table. t1 uses cursor
drh6a3ea0e2003-05-02 14:32:12 +00003070** number pTabList->a[0].iCursor. t2 uses the cursor pTabList->a[1].iCursor.
3071** And so forth. This routine generates code to open those VDBE cursors
danielk19774adee202004-05-08 08:23:19 +00003072** and sqlite3WhereEnd() generates the code to close them.
drhc27a1ce2002-06-14 20:58:45 +00003073**
drhe6f85e72004-12-25 01:03:13 +00003074** The code that sqlite3WhereBegin() generates leaves the cursors named
3075** in pTabList pointing at their appropriate entries. The [...] code
drhf0863fe2005-06-12 21:35:51 +00003076** can use OP_Column and OP_Rowid opcodes on these cursors to extract
drhe6f85e72004-12-25 01:03:13 +00003077** data from the various tables of the loop.
3078**
drhc27a1ce2002-06-14 20:58:45 +00003079** If the WHERE clause is empty, the foreach loops must each scan their
3080** entire tables. Thus a three-way join is an O(N^3) operation. But if
3081** the tables have indices and there are terms in the WHERE clause that
3082** refer to those indices, a complete table scan can be avoided and the
3083** code will run much faster. Most of the work of this routine is checking
3084** to see if there are indices that can be used to speed up the loop.
3085**
3086** Terms of the WHERE clause are also used to limit which rows actually
3087** make it to the "..." in the middle of the loop. After each "foreach",
3088** terms of the WHERE clause that use only terms in that loop and outer
3089** loops are evaluated and if false a jump is made around all subsequent
3090** inner loops (or around the "..." if the test occurs within the inner-
3091** most loop)
3092**
3093** OUTER JOINS
3094**
3095** An outer join of tables t1 and t2 is conceptally coded as follows:
3096**
3097** foreach row1 in t1 do
3098** flag = 0
3099** foreach row2 in t2 do
3100** start:
3101** ...
3102** flag = 1
3103** end
drhe3184742002-06-19 14:27:05 +00003104** if flag==0 then
3105** move the row2 cursor to a null row
3106** goto start
3107** fi
drhc27a1ce2002-06-14 20:58:45 +00003108** end
3109**
drhe3184742002-06-19 14:27:05 +00003110** ORDER BY CLAUSE PROCESSING
3111**
3112** *ppOrderBy is a pointer to the ORDER BY clause of a SELECT statement,
3113** if there is one. If there is no ORDER BY clause or if this routine
3114** is called from an UPDATE or DELETE statement, then ppOrderBy is NULL.
3115**
3116** If an index can be used so that the natural output order of the table
3117** scan is correct for the ORDER BY clause, then that index is used and
3118** *ppOrderBy is set to NULL. This is an optimization that prevents an
3119** unnecessary sort of the result set if an index appropriate for the
3120** ORDER BY clause already exists.
3121**
3122** If the where clause loops cannot be arranged to provide the correct
3123** output order, then the *ppOrderBy is unchanged.
drh75897232000-05-29 14:26:00 +00003124*/
danielk19774adee202004-05-08 08:23:19 +00003125WhereInfo *sqlite3WhereBegin(
danielk1977ed326d72004-11-16 15:50:19 +00003126 Parse *pParse, /* The parser context */
3127 SrcList *pTabList, /* A list of all tables to be scanned */
3128 Expr *pWhere, /* The WHERE clause */
danielk1977a9d1ccb2008-01-05 17:39:29 +00003129 ExprList **ppOrderBy, /* An ORDER BY clause, or NULL */
drh336a5302009-04-24 15:46:21 +00003130 u16 wctrlFlags /* One of the WHERE_* flags defined in sqliteInt.h */
drh75897232000-05-29 14:26:00 +00003131){
3132 int i; /* Loop counter */
danielk1977be229652009-03-20 14:18:51 +00003133 int nByteWInfo; /* Num. bytes allocated for WhereInfo struct */
drh75897232000-05-29 14:26:00 +00003134 WhereInfo *pWInfo; /* Will become the return value of this function */
3135 Vdbe *v = pParse->pVdbe; /* The virtual database engine */
drhfe05af82005-07-21 03:14:59 +00003136 Bitmask notReady; /* Cursors that are not yet positioned */
drh111a6a72008-12-21 03:51:16 +00003137 WhereMaskSet *pMaskSet; /* The expression mask set */
drh111a6a72008-12-21 03:51:16 +00003138 WhereClause *pWC; /* Decomposition of the WHERE clause */
drh9012bcb2004-12-19 00:11:35 +00003139 struct SrcList_item *pTabItem; /* A single entry from pTabList */
3140 WhereLevel *pLevel; /* A single level in the pWInfo list */
drh29dda4a2005-07-21 18:23:20 +00003141 int iFrom; /* First unused FROM clause element */
drh111a6a72008-12-21 03:51:16 +00003142 int andFlags; /* AND-ed combination of all pWC->a[].wtFlags */
drh17435752007-08-16 04:30:38 +00003143 sqlite3 *db; /* Database connection */
drh75897232000-05-29 14:26:00 +00003144
drh29dda4a2005-07-21 18:23:20 +00003145 /* The number of tables in the FROM clause is limited by the number of
drh1398ad32005-01-19 23:24:50 +00003146 ** bits in a Bitmask
3147 */
drh29dda4a2005-07-21 18:23:20 +00003148 if( pTabList->nSrc>BMS ){
3149 sqlite3ErrorMsg(pParse, "at most %d tables in a join", BMS);
drh1398ad32005-01-19 23:24:50 +00003150 return 0;
3151 }
3152
drh75897232000-05-29 14:26:00 +00003153 /* Allocate and initialize the WhereInfo structure that will become the
danielk1977be229652009-03-20 14:18:51 +00003154 ** return value. A single allocation is used to store the WhereInfo
3155 ** struct, the contents of WhereInfo.a[], the WhereClause structure
3156 ** and the WhereMaskSet structure. Since WhereClause contains an 8-byte
3157 ** field (type Bitmask) it must be aligned on an 8-byte boundary on
3158 ** some architectures. Hence the ROUND8() below.
drh75897232000-05-29 14:26:00 +00003159 */
drh17435752007-08-16 04:30:38 +00003160 db = pParse->db;
danielk1977be229652009-03-20 14:18:51 +00003161 nByteWInfo = ROUND8(sizeof(WhereInfo)+(pTabList->nSrc-1)*sizeof(WhereLevel));
3162 pWInfo = sqlite3DbMallocZero(db,
3163 nByteWInfo +
3164 sizeof(WhereClause) +
3165 sizeof(WhereMaskSet)
3166 );
drh17435752007-08-16 04:30:38 +00003167 if( db->mallocFailed ){
danielk197785574e32008-10-06 05:32:18 +00003168 goto whereBeginError;
drh75897232000-05-29 14:26:00 +00003169 }
danielk197770b6d572006-06-19 04:49:34 +00003170 pWInfo->nLevel = pTabList->nSrc;
drh75897232000-05-29 14:26:00 +00003171 pWInfo->pParse = pParse;
3172 pWInfo->pTabList = pTabList;
danielk19774adee202004-05-08 08:23:19 +00003173 pWInfo->iBreak = sqlite3VdbeMakeLabel(v);
danielk1977be229652009-03-20 14:18:51 +00003174 pWInfo->pWC = pWC = (WhereClause *)&((u8 *)pWInfo)[nByteWInfo];
drh6df2acd2008-12-28 16:55:25 +00003175 pWInfo->wctrlFlags = wctrlFlags;
drh111a6a72008-12-21 03:51:16 +00003176 pMaskSet = (WhereMaskSet*)&pWC[1];
drh08192d52002-04-30 19:20:28 +00003177
drh111a6a72008-12-21 03:51:16 +00003178 /* Split the WHERE clause into separate subexpressions where each
3179 ** subexpression is separated by an AND operator.
3180 */
3181 initMaskSet(pMaskSet);
3182 whereClauseInit(pWC, pParse, pMaskSet);
3183 sqlite3ExprCodeConstants(pParse, pWhere);
3184 whereSplit(pWC, pWhere, TK_AND);
3185
drh08192d52002-04-30 19:20:28 +00003186 /* Special case: a WHERE clause that is constant. Evaluate the
3187 ** expression and either jump over all of the code or fall thru.
3188 */
drh0a168372007-06-08 00:20:47 +00003189 if( pWhere && (pTabList->nSrc==0 || sqlite3ExprIsConstantNotJoin(pWhere)) ){
drh35573352008-01-08 23:54:25 +00003190 sqlite3ExprIfFalse(pParse, pWhere, pWInfo->iBreak, SQLITE_JUMPIFNULL);
drhdf199a22002-06-14 22:38:41 +00003191 pWhere = 0;
drh08192d52002-04-30 19:20:28 +00003192 }
drh75897232000-05-29 14:26:00 +00003193
drh42165be2008-03-26 14:56:34 +00003194 /* Assign a bit from the bitmask to every term in the FROM clause.
3195 **
3196 ** When assigning bitmask values to FROM clause cursors, it must be
3197 ** the case that if X is the bitmask for the N-th FROM clause term then
3198 ** the bitmask for all FROM clause terms to the left of the N-th term
3199 ** is (X-1). An expression from the ON clause of a LEFT JOIN can use
3200 ** its Expr.iRightJoinTable value to find the bitmask of the right table
3201 ** of the join. Subtracting one from the right table bitmask gives a
3202 ** bitmask for all tables to the left of the join. Knowing the bitmask
3203 ** for all tables to the left of a left join is important. Ticket #3015.
danielk1977e672c8e2009-05-22 15:43:26 +00003204 **
3205 ** Configure the WhereClause.vmask variable so that bits that correspond
3206 ** to virtual table cursors are set. This is used to selectively disable
3207 ** the OR-to-IN transformation in exprAnalyzeOrTerm(). It is not helpful
3208 ** with virtual tables.
drh42165be2008-03-26 14:56:34 +00003209 */
danielk1977e672c8e2009-05-22 15:43:26 +00003210 assert( pWC->vmask==0 && pMaskSet->n==0 );
drh42165be2008-03-26 14:56:34 +00003211 for(i=0; i<pTabList->nSrc; i++){
drh111a6a72008-12-21 03:51:16 +00003212 createMask(pMaskSet, pTabList->a[i].iCursor);
danielk1977e672c8e2009-05-22 15:43:26 +00003213 if( pTabList->a[i].pTab && IsVirtual(pTabList->a[i].pTab) ){
3214 pWC->vmask |= ((Bitmask)1 << i);
3215 }
drh42165be2008-03-26 14:56:34 +00003216 }
3217#ifndef NDEBUG
3218 {
3219 Bitmask toTheLeft = 0;
3220 for(i=0; i<pTabList->nSrc; i++){
drh111a6a72008-12-21 03:51:16 +00003221 Bitmask m = getMask(pMaskSet, pTabList->a[i].iCursor);
drh42165be2008-03-26 14:56:34 +00003222 assert( (m-1)==toTheLeft );
3223 toTheLeft |= m;
3224 }
3225 }
3226#endif
3227
drh29dda4a2005-07-21 18:23:20 +00003228 /* Analyze all of the subexpressions. Note that exprAnalyze() might
3229 ** add new virtual terms onto the end of the WHERE clause. We do not
3230 ** want to analyze these virtual terms, so start analyzing at the end
drhb6fb62d2005-09-20 08:47:20 +00003231 ** and work forward so that the added virtual terms are never processed.
drh75897232000-05-29 14:26:00 +00003232 */
drh111a6a72008-12-21 03:51:16 +00003233 exprAnalyzeAll(pTabList, pWC);
drh17435752007-08-16 04:30:38 +00003234 if( db->mallocFailed ){
danielk197785574e32008-10-06 05:32:18 +00003235 goto whereBeginError;
drh0bbaa1b2005-08-19 19:14:12 +00003236 }
drh75897232000-05-29 14:26:00 +00003237
drh29dda4a2005-07-21 18:23:20 +00003238 /* Chose the best index to use for each table in the FROM clause.
3239 **
drh51147ba2005-07-23 22:59:55 +00003240 ** This loop fills in the following fields:
3241 **
3242 ** pWInfo->a[].pIdx The index to use for this level of the loop.
drh165be382008-12-05 02:36:33 +00003243 ** pWInfo->a[].wsFlags WHERE_xxx flags associated with pIdx
drh51147ba2005-07-23 22:59:55 +00003244 ** pWInfo->a[].nEq The number of == and IN constraints
danielk197785574e32008-10-06 05:32:18 +00003245 ** pWInfo->a[].iFrom Which term of the FROM clause is being coded
drh51147ba2005-07-23 22:59:55 +00003246 ** pWInfo->a[].iTabCur The VDBE cursor for the database table
3247 ** pWInfo->a[].iIdxCur The VDBE cursor for the index
drh111a6a72008-12-21 03:51:16 +00003248 ** pWInfo->a[].pTerm When wsFlags==WO_OR, the OR-clause term
drh51147ba2005-07-23 22:59:55 +00003249 **
3250 ** This loop also figures out the nesting order of tables in the FROM
3251 ** clause.
drh75897232000-05-29 14:26:00 +00003252 */
drhfe05af82005-07-21 03:14:59 +00003253 notReady = ~(Bitmask)0;
drh9012bcb2004-12-19 00:11:35 +00003254 pTabItem = pTabList->a;
3255 pLevel = pWInfo->a;
drh943af3c2005-07-29 19:43:58 +00003256 andFlags = ~0;
drh4f0c5872007-03-26 22:05:01 +00003257 WHERETRACE(("*** Optimizer Start ***\n"));
drh29dda4a2005-07-21 18:23:20 +00003258 for(i=iFrom=0, pLevel=pWInfo->a; i<pTabList->nSrc; i++, pLevel++){
drh111a6a72008-12-21 03:51:16 +00003259 WhereCost bestPlan; /* Most efficient plan seen so far */
drh29dda4a2005-07-21 18:23:20 +00003260 Index *pIdx; /* Index for FROM table at pTabItem */
drh29dda4a2005-07-21 18:23:20 +00003261 int j; /* For looping over FROM tables */
drh02afc862006-01-20 18:10:57 +00003262 int bestJ = 0; /* The value of j */
drh29dda4a2005-07-21 18:23:20 +00003263 Bitmask m; /* Bitmask value for j or bestJ */
drh570b9352006-02-01 02:45:02 +00003264 int once = 0; /* True when first table is seen */
drh29dda4a2005-07-21 18:23:20 +00003265
drh111a6a72008-12-21 03:51:16 +00003266 memset(&bestPlan, 0, sizeof(bestPlan));
3267 bestPlan.rCost = SQLITE_BIG_DBL;
drh29dda4a2005-07-21 18:23:20 +00003268 for(j=iFrom, pTabItem=&pTabList->a[j]; j<pTabList->nSrc; j++, pTabItem++){
danielk19771d461462009-04-21 09:02:45 +00003269 int doNotReorder; /* True if this table should not be reordered */
3270 WhereCost sCost; /* Cost information from best[Virtual]Index() */
3271 ExprList *pOrderBy; /* ORDER BY clause for index to optimize */
drhdf26fd52006-06-06 11:45:54 +00003272
drh61dfc312006-12-16 16:25:15 +00003273 doNotReorder = (pTabItem->jointype & (JT_LEFT|JT_CROSS))!=0;
drhdf26fd52006-06-06 11:45:54 +00003274 if( once && doNotReorder ) break;
drh111a6a72008-12-21 03:51:16 +00003275 m = getMask(pMaskSet, pTabItem->iCursor);
drh29dda4a2005-07-21 18:23:20 +00003276 if( (m & notReady)==0 ){
3277 if( j==iFrom ) iFrom++;
3278 continue;
3279 }
danielk19771d461462009-04-21 09:02:45 +00003280 pOrderBy = ((i==0 && ppOrderBy )?*ppOrderBy:0);
3281
drh9eff6162006-06-12 21:59:13 +00003282 assert( pTabItem->pTab );
3283#ifndef SQLITE_OMIT_VIRTUALTABLE
drh4cbdda92006-06-14 19:00:20 +00003284 if( IsVirtual(pTabItem->pTab) ){
danielk19771d461462009-04-21 09:02:45 +00003285 sqlite3_index_info **pp = &pWInfo->a[j].pIdxInfo;
3286 bestVirtualIndex(pParse, pWC, pTabItem, notReady, pOrderBy, &sCost, pp);
drh9eff6162006-06-12 21:59:13 +00003287 }else
3288#endif
3289 {
danielk19771d461462009-04-21 09:02:45 +00003290 bestBtreeIndex(pParse, pWC, pTabItem, notReady, pOrderBy, &sCost);
drh9eff6162006-06-12 21:59:13 +00003291 }
danielk1977992347f2008-12-30 09:45:45 +00003292 if( once==0 || sCost.rCost<bestPlan.rCost ){
drh570b9352006-02-01 02:45:02 +00003293 once = 1;
drh111a6a72008-12-21 03:51:16 +00003294 bestPlan = sCost;
drh29dda4a2005-07-21 18:23:20 +00003295 bestJ = j;
3296 }
drhdf26fd52006-06-06 11:45:54 +00003297 if( doNotReorder ) break;
drh29dda4a2005-07-21 18:23:20 +00003298 }
danielk1977992347f2008-12-30 09:45:45 +00003299 assert( once );
3300 assert( notReady & getMask(pMaskSet, pTabList->a[bestJ].iCursor) );
drhcb041342008-06-12 00:07:29 +00003301 WHERETRACE(("*** Optimizer selects table %d for loop %d\n", bestJ,
drh3dec2232005-09-10 15:28:09 +00003302 pLevel-pWInfo->a));
drh111a6a72008-12-21 03:51:16 +00003303 if( (bestPlan.plan.wsFlags & WHERE_ORDERBY)!=0 ){
drhfe05af82005-07-21 03:14:59 +00003304 *ppOrderBy = 0;
drhc4a3c772001-04-04 11:48:57 +00003305 }
drh111a6a72008-12-21 03:51:16 +00003306 andFlags &= bestPlan.plan.wsFlags;
3307 pLevel->plan = bestPlan.plan;
3308 if( bestPlan.plan.wsFlags & WHERE_INDEXED ){
drh9012bcb2004-12-19 00:11:35 +00003309 pLevel->iIdxCur = pParse->nTab++;
drhfe05af82005-07-21 03:14:59 +00003310 }else{
3311 pLevel->iIdxCur = -1;
drh6b563442001-11-07 16:48:26 +00003312 }
drh111a6a72008-12-21 03:51:16 +00003313 notReady &= ~getMask(pMaskSet, pTabList->a[bestJ].iCursor);
shaned87897d2009-01-30 05:40:27 +00003314 pLevel->iFrom = (u8)bestJ;
danielk197785574e32008-10-06 05:32:18 +00003315
3316 /* Check that if the table scanned by this loop iteration had an
3317 ** INDEXED BY clause attached to it, that the named index is being
3318 ** used for the scan. If not, then query compilation has failed.
3319 ** Return an error.
3320 */
3321 pIdx = pTabList->a[bestJ].pIndex;
drh171256c2009-01-08 03:11:19 +00003322 if( pIdx ){
3323 if( (bestPlan.plan.wsFlags & WHERE_INDEXED)==0 ){
3324 sqlite3ErrorMsg(pParse, "cannot use index: %s", pIdx->zName);
3325 goto whereBeginError;
3326 }else{
3327 /* If an INDEXED BY clause is used, the bestIndex() function is
3328 ** guaranteed to find the index specified in the INDEXED BY clause
3329 ** if it find an index at all. */
3330 assert( bestPlan.plan.u.pIdx==pIdx );
3331 }
danielk197785574e32008-10-06 05:32:18 +00003332 }
drh75897232000-05-29 14:26:00 +00003333 }
drh4f0c5872007-03-26 22:05:01 +00003334 WHERETRACE(("*** Optimizer Finished ***\n"));
danielk19771d461462009-04-21 09:02:45 +00003335 if( pParse->nErr || db->mallocFailed ){
danielk197780442942008-12-24 11:25:39 +00003336 goto whereBeginError;
3337 }
drh75897232000-05-29 14:26:00 +00003338
drh943af3c2005-07-29 19:43:58 +00003339 /* If the total query only selects a single row, then the ORDER BY
3340 ** clause is irrelevant.
3341 */
3342 if( (andFlags & WHERE_UNIQUE)!=0 && ppOrderBy ){
3343 *ppOrderBy = 0;
3344 }
3345
drh08c88eb2008-04-10 13:33:18 +00003346 /* If the caller is an UPDATE or DELETE statement that is requesting
3347 ** to use a one-pass algorithm, determine if this is appropriate.
3348 ** The one-pass algorithm only works if the WHERE clause constraints
3349 ** the statement to update a single row.
3350 */
drh165be382008-12-05 02:36:33 +00003351 assert( (wctrlFlags & WHERE_ONEPASS_DESIRED)==0 || pWInfo->nLevel==1 );
3352 if( (wctrlFlags & WHERE_ONEPASS_DESIRED)!=0 && (andFlags & WHERE_UNIQUE)!=0 ){
drh08c88eb2008-04-10 13:33:18 +00003353 pWInfo->okOnePass = 1;
drh111a6a72008-12-21 03:51:16 +00003354 pWInfo->a[0].plan.wsFlags &= ~WHERE_IDX_ONLY;
drh08c88eb2008-04-10 13:33:18 +00003355 }
3356
drh9012bcb2004-12-19 00:11:35 +00003357 /* Open all tables in the pTabList and any indices selected for
3358 ** searching those tables.
3359 */
3360 sqlite3CodeVerifySchema(pParse, -1); /* Insert the cookie verifier Goto */
drh29dda4a2005-07-21 18:23:20 +00003361 for(i=0, pLevel=pWInfo->a; i<pTabList->nSrc; i++, pLevel++){
danielk1977da184232006-01-05 11:34:32 +00003362 Table *pTab; /* Table to open */
danielk1977da184232006-01-05 11:34:32 +00003363 int iDb; /* Index of database containing table/index */
drh9012bcb2004-12-19 00:11:35 +00003364
drhecc92422005-09-10 16:46:12 +00003365#ifndef SQLITE_OMIT_EXPLAIN
3366 if( pParse->explain==2 ){
3367 char *zMsg;
3368 struct SrcList_item *pItem = &pTabList->a[pLevel->iFrom];
danielk19771e536952007-08-16 10:09:01 +00003369 zMsg = sqlite3MPrintf(db, "TABLE %s", pItem->zName);
drhecc92422005-09-10 16:46:12 +00003370 if( pItem->zAlias ){
drh633e6d52008-07-28 19:34:53 +00003371 zMsg = sqlite3MAppendf(db, zMsg, "%s AS %s", zMsg, pItem->zAlias);
drhecc92422005-09-10 16:46:12 +00003372 }
drh111a6a72008-12-21 03:51:16 +00003373 if( (pLevel->plan.wsFlags & WHERE_INDEXED)!=0 ){
3374 zMsg = sqlite3MAppendf(db, zMsg, "%s WITH INDEX %s",
3375 zMsg, pLevel->plan.u.pIdx->zName);
drh46129af2008-12-30 16:18:47 +00003376 }else if( pLevel->plan.wsFlags & WHERE_MULTI_OR ){
3377 zMsg = sqlite3MAppendf(db, zMsg, "%s VIA MULTI-INDEX UNION", zMsg);
drh111a6a72008-12-21 03:51:16 +00003378 }else if( pLevel->plan.wsFlags & (WHERE_ROWID_EQ|WHERE_ROWID_RANGE) ){
drh633e6d52008-07-28 19:34:53 +00003379 zMsg = sqlite3MAppendf(db, zMsg, "%s USING PRIMARY KEY", zMsg);
drhecc92422005-09-10 16:46:12 +00003380 }
drh9eff6162006-06-12 21:59:13 +00003381#ifndef SQLITE_OMIT_VIRTUALTABLE
drh111a6a72008-12-21 03:51:16 +00003382 else if( (pLevel->plan.wsFlags & WHERE_VIRTUALTABLE)!=0 ){
3383 sqlite3_index_info *pVtabIdx = pLevel->plan.u.pVtabIdx;
drh633e6d52008-07-28 19:34:53 +00003384 zMsg = sqlite3MAppendf(db, zMsg, "%s VIRTUAL TABLE INDEX %d:%s", zMsg,
drh111a6a72008-12-21 03:51:16 +00003385 pVtabIdx->idxNum, pVtabIdx->idxStr);
drh9eff6162006-06-12 21:59:13 +00003386 }
3387#endif
drh111a6a72008-12-21 03:51:16 +00003388 if( pLevel->plan.wsFlags & WHERE_ORDERBY ){
drh633e6d52008-07-28 19:34:53 +00003389 zMsg = sqlite3MAppendf(db, zMsg, "%s ORDER BY", zMsg);
drhe2b39092006-04-21 09:38:36 +00003390 }
drh66a51672008-01-03 00:01:23 +00003391 sqlite3VdbeAddOp4(v, OP_Explain, i, pLevel->iFrom, 0, zMsg, P4_DYNAMIC);
drhecc92422005-09-10 16:46:12 +00003392 }
3393#endif /* SQLITE_OMIT_EXPLAIN */
drh29dda4a2005-07-21 18:23:20 +00003394 pTabItem = &pTabList->a[pLevel->iFrom];
drh9012bcb2004-12-19 00:11:35 +00003395 pTab = pTabItem->pTab;
danielk1977da184232006-01-05 11:34:32 +00003396 iDb = sqlite3SchemaToIndex(pParse->db, pTab->pSchema);
drh7d10d5a2008-08-20 16:35:10 +00003397 if( (pTab->tabFlags & TF_Ephemeral)!=0 || pTab->pSelect ) continue;
drh9eff6162006-06-12 21:59:13 +00003398#ifndef SQLITE_OMIT_VIRTUALTABLE
drh111a6a72008-12-21 03:51:16 +00003399 if( (pLevel->plan.wsFlags & WHERE_VIRTUALTABLE)!=0 ){
danielk197793626f42006-06-20 13:07:27 +00003400 int iCur = pTabItem->iCursor;
drh66a51672008-01-03 00:01:23 +00003401 sqlite3VdbeAddOp4(v, OP_VOpen, iCur, 0, 0,
3402 (const char*)pTab->pVtab, P4_VTAB);
drh9eff6162006-06-12 21:59:13 +00003403 }else
3404#endif
drh6df2acd2008-12-28 16:55:25 +00003405 if( (pLevel->plan.wsFlags & WHERE_IDX_ONLY)==0
3406 && (wctrlFlags & WHERE_OMIT_OPEN)==0 ){
drh08c88eb2008-04-10 13:33:18 +00003407 int op = pWInfo->okOnePass ? OP_OpenWrite : OP_OpenRead;
3408 sqlite3OpenTable(pParse, pTabItem->iCursor, iDb, pTab, op);
danielk197723432972008-11-17 16:42:00 +00003409 if( !pWInfo->okOnePass && pTab->nCol<BMS ){
danielk19779792eef2006-01-13 15:58:43 +00003410 Bitmask b = pTabItem->colUsed;
3411 int n = 0;
drh74161702006-02-24 02:53:49 +00003412 for(; b; b=b>>1, n++){}
shanec0688ea2009-03-05 03:48:06 +00003413 sqlite3VdbeChangeP4(v, sqlite3VdbeCurrentAddr(v)-1, SQLITE_INT_TO_PTR(n), P4_INT32);
danielk19779792eef2006-01-13 15:58:43 +00003414 assert( n<=pTab->nCol );
3415 }
danielk1977c00da102006-01-07 13:21:04 +00003416 }else{
3417 sqlite3TableLock(pParse, iDb, pTab->tnum, 0, pTab->zName);
drh9012bcb2004-12-19 00:11:35 +00003418 }
3419 pLevel->iTabCur = pTabItem->iCursor;
drh111a6a72008-12-21 03:51:16 +00003420 if( (pLevel->plan.wsFlags & WHERE_INDEXED)!=0 ){
3421 Index *pIx = pLevel->plan.u.pIdx;
danielk1977b3bf5562006-01-10 17:58:23 +00003422 KeyInfo *pKey = sqlite3IndexKeyinfo(pParse, pIx);
drh111a6a72008-12-21 03:51:16 +00003423 int iIdxCur = pLevel->iIdxCur;
danielk1977da184232006-01-05 11:34:32 +00003424 assert( pIx->pSchema==pTab->pSchema );
drh111a6a72008-12-21 03:51:16 +00003425 assert( iIdxCur>=0 );
danielk1977207872a2008-01-03 07:54:23 +00003426 sqlite3VdbeAddOp4(v, OP_OpenRead, iIdxCur, pIx->tnum, iDb,
drh66a51672008-01-03 00:01:23 +00003427 (char*)pKey, P4_KEYINFO_HANDOFF);
danielk1977207872a2008-01-03 07:54:23 +00003428 VdbeComment((v, "%s", pIx->zName));
drh9012bcb2004-12-19 00:11:35 +00003429 }
danielk1977da184232006-01-05 11:34:32 +00003430 sqlite3CodeVerifySchema(pParse, iDb);
drh9012bcb2004-12-19 00:11:35 +00003431 }
3432 pWInfo->iTop = sqlite3VdbeCurrentAddr(v);
3433
drh29dda4a2005-07-21 18:23:20 +00003434 /* Generate the code to do the search. Each iteration of the for
3435 ** loop below generates code for a single nested loop of the VM
3436 ** program.
drh75897232000-05-29 14:26:00 +00003437 */
drhfe05af82005-07-21 03:14:59 +00003438 notReady = ~(Bitmask)0;
drh111a6a72008-12-21 03:51:16 +00003439 for(i=0; i<pTabList->nSrc; i++){
3440 notReady = codeOneLoopStart(pWInfo, i, wctrlFlags, notReady);
drh813f31e2009-01-06 00:08:02 +00003441 pWInfo->iContinue = pWInfo->a[i].addrCont;
drh75897232000-05-29 14:26:00 +00003442 }
drh7ec764a2005-07-21 03:48:20 +00003443
3444#ifdef SQLITE_TEST /* For testing and debugging use only */
3445 /* Record in the query plan information about the current table
3446 ** and the index used to access it (if any). If the table itself
3447 ** is not used, its name is just '{}'. If no index is used
3448 ** the index is listed as "{}". If the primary key is used the
3449 ** index name is '*'.
3450 */
3451 for(i=0; i<pTabList->nSrc; i++){
3452 char *z;
3453 int n;
drh7ec764a2005-07-21 03:48:20 +00003454 pLevel = &pWInfo->a[i];
drh29dda4a2005-07-21 18:23:20 +00003455 pTabItem = &pTabList->a[pLevel->iFrom];
drh7ec764a2005-07-21 03:48:20 +00003456 z = pTabItem->zAlias;
3457 if( z==0 ) z = pTabItem->pTab->zName;
drhea678832008-12-10 19:26:22 +00003458 n = sqlite3Strlen30(z);
drh7ec764a2005-07-21 03:48:20 +00003459 if( n+nQPlan < sizeof(sqlite3_query_plan)-10 ){
drh111a6a72008-12-21 03:51:16 +00003460 if( pLevel->plan.wsFlags & WHERE_IDX_ONLY ){
drh5bb3eb92007-05-04 13:15:55 +00003461 memcpy(&sqlite3_query_plan[nQPlan], "{}", 2);
drh7ec764a2005-07-21 03:48:20 +00003462 nQPlan += 2;
3463 }else{
drh5bb3eb92007-05-04 13:15:55 +00003464 memcpy(&sqlite3_query_plan[nQPlan], z, n);
drh7ec764a2005-07-21 03:48:20 +00003465 nQPlan += n;
3466 }
3467 sqlite3_query_plan[nQPlan++] = ' ';
3468 }
drh111a6a72008-12-21 03:51:16 +00003469 testcase( pLevel->plan.wsFlags & WHERE_ROWID_EQ );
3470 testcase( pLevel->plan.wsFlags & WHERE_ROWID_RANGE );
3471 if( pLevel->plan.wsFlags & (WHERE_ROWID_EQ|WHERE_ROWID_RANGE) ){
drh5bb3eb92007-05-04 13:15:55 +00003472 memcpy(&sqlite3_query_plan[nQPlan], "* ", 2);
drh7ec764a2005-07-21 03:48:20 +00003473 nQPlan += 2;
drh111a6a72008-12-21 03:51:16 +00003474 }else if( (pLevel->plan.wsFlags & WHERE_INDEXED)!=0 ){
3475 n = sqlite3Strlen30(pLevel->plan.u.pIdx->zName);
drh7ec764a2005-07-21 03:48:20 +00003476 if( n+nQPlan < sizeof(sqlite3_query_plan)-2 ){
drh111a6a72008-12-21 03:51:16 +00003477 memcpy(&sqlite3_query_plan[nQPlan], pLevel->plan.u.pIdx->zName, n);
drh7ec764a2005-07-21 03:48:20 +00003478 nQPlan += n;
3479 sqlite3_query_plan[nQPlan++] = ' ';
3480 }
drh111a6a72008-12-21 03:51:16 +00003481 }else{
3482 memcpy(&sqlite3_query_plan[nQPlan], "{} ", 3);
3483 nQPlan += 3;
drh7ec764a2005-07-21 03:48:20 +00003484 }
3485 }
3486 while( nQPlan>0 && sqlite3_query_plan[nQPlan-1]==' ' ){
3487 sqlite3_query_plan[--nQPlan] = 0;
3488 }
3489 sqlite3_query_plan[nQPlan] = 0;
3490 nQPlan = 0;
3491#endif /* SQLITE_TEST // Testing and debugging use only */
3492
drh29dda4a2005-07-21 18:23:20 +00003493 /* Record the continuation address in the WhereInfo structure. Then
3494 ** clean up and return.
3495 */
drh75897232000-05-29 14:26:00 +00003496 return pWInfo;
drhe23399f2005-07-22 00:31:39 +00003497
3498 /* Jump here if malloc fails */
danielk197785574e32008-10-06 05:32:18 +00003499whereBeginError:
drh10fe8402008-10-11 16:47:35 +00003500 whereInfoFree(db, pWInfo);
drhe23399f2005-07-22 00:31:39 +00003501 return 0;
drh75897232000-05-29 14:26:00 +00003502}
3503
3504/*
drhc27a1ce2002-06-14 20:58:45 +00003505** Generate the end of the WHERE loop. See comments on
danielk19774adee202004-05-08 08:23:19 +00003506** sqlite3WhereBegin() for additional information.
drh75897232000-05-29 14:26:00 +00003507*/
danielk19774adee202004-05-08 08:23:19 +00003508void sqlite3WhereEnd(WhereInfo *pWInfo){
drh633e6d52008-07-28 19:34:53 +00003509 Parse *pParse = pWInfo->pParse;
3510 Vdbe *v = pParse->pVdbe;
drh19a775c2000-06-05 18:54:46 +00003511 int i;
drh6b563442001-11-07 16:48:26 +00003512 WhereLevel *pLevel;
drhad3cab52002-05-24 02:04:32 +00003513 SrcList *pTabList = pWInfo->pTabList;
drh633e6d52008-07-28 19:34:53 +00003514 sqlite3 *db = pParse->db;
drh19a775c2000-06-05 18:54:46 +00003515
drh9012bcb2004-12-19 00:11:35 +00003516 /* Generate loop termination code.
3517 */
drhceea3322009-04-23 13:22:42 +00003518 sqlite3ExprCacheClear(pParse);
drhad3cab52002-05-24 02:04:32 +00003519 for(i=pTabList->nSrc-1; i>=0; i--){
drh6b563442001-11-07 16:48:26 +00003520 pLevel = &pWInfo->a[i];
drhb3190c12008-12-08 21:37:14 +00003521 sqlite3VdbeResolveLabel(v, pLevel->addrCont);
drh6b563442001-11-07 16:48:26 +00003522 if( pLevel->op!=OP_Noop ){
drh66a51672008-01-03 00:01:23 +00003523 sqlite3VdbeAddOp2(v, pLevel->op, pLevel->p1, pLevel->p2);
drhd1d38482008-10-07 23:46:38 +00003524 sqlite3VdbeChangeP5(v, pLevel->p5);
drh19a775c2000-06-05 18:54:46 +00003525 }
drh111a6a72008-12-21 03:51:16 +00003526 if( pLevel->plan.wsFlags & WHERE_IN_ABLE && pLevel->u.in.nIn>0 ){
drh72e8fa42007-03-28 14:30:06 +00003527 struct InLoop *pIn;
drhe23399f2005-07-22 00:31:39 +00003528 int j;
drhb3190c12008-12-08 21:37:14 +00003529 sqlite3VdbeResolveLabel(v, pLevel->addrNxt);
drh111a6a72008-12-21 03:51:16 +00003530 for(j=pLevel->u.in.nIn, pIn=&pLevel->u.in.aInLoop[j-1]; j>0; j--, pIn--){
drhb3190c12008-12-08 21:37:14 +00003531 sqlite3VdbeJumpHere(v, pIn->addrInTop+1);
3532 sqlite3VdbeAddOp2(v, OP_Next, pIn->iCur, pIn->addrInTop);
3533 sqlite3VdbeJumpHere(v, pIn->addrInTop-1);
drhe23399f2005-07-22 00:31:39 +00003534 }
drh111a6a72008-12-21 03:51:16 +00003535 sqlite3DbFree(db, pLevel->u.in.aInLoop);
drhd99f7062002-06-08 23:25:08 +00003536 }
drhb3190c12008-12-08 21:37:14 +00003537 sqlite3VdbeResolveLabel(v, pLevel->addrBrk);
drhad2d8302002-05-24 20:31:36 +00003538 if( pLevel->iLeftJoin ){
3539 int addr;
drh3c84ddf2008-01-09 02:15:38 +00003540 addr = sqlite3VdbeAddOp1(v, OP_IfPos, pLevel->iLeftJoin);
3541 sqlite3VdbeAddOp1(v, OP_NullRow, pTabList->a[i].iCursor);
drh9012bcb2004-12-19 00:11:35 +00003542 if( pLevel->iIdxCur>=0 ){
drh3c84ddf2008-01-09 02:15:38 +00003543 sqlite3VdbeAddOp1(v, OP_NullRow, pLevel->iIdxCur);
drh7f09b3e2002-08-13 13:15:49 +00003544 }
drh336a5302009-04-24 15:46:21 +00003545 if( pLevel->op==OP_Return ){
3546 sqlite3VdbeAddOp2(v, OP_Gosub, pLevel->p1, pLevel->addrFirst);
3547 }else{
3548 sqlite3VdbeAddOp2(v, OP_Goto, 0, pLevel->addrFirst);
3549 }
drhd654be82005-09-20 17:42:23 +00003550 sqlite3VdbeJumpHere(v, addr);
drhad2d8302002-05-24 20:31:36 +00003551 }
drh19a775c2000-06-05 18:54:46 +00003552 }
drh9012bcb2004-12-19 00:11:35 +00003553
3554 /* The "break" point is here, just past the end of the outer loop.
3555 ** Set it.
3556 */
danielk19774adee202004-05-08 08:23:19 +00003557 sqlite3VdbeResolveLabel(v, pWInfo->iBreak);
drh9012bcb2004-12-19 00:11:35 +00003558
drh29dda4a2005-07-21 18:23:20 +00003559 /* Close all of the cursors that were opened by sqlite3WhereBegin.
drh9012bcb2004-12-19 00:11:35 +00003560 */
drh29dda4a2005-07-21 18:23:20 +00003561 for(i=0, pLevel=pWInfo->a; i<pTabList->nSrc; i++, pLevel++){
3562 struct SrcList_item *pTabItem = &pTabList->a[pLevel->iFrom];
drh9012bcb2004-12-19 00:11:35 +00003563 Table *pTab = pTabItem->pTab;
drh5cf590c2003-04-24 01:45:04 +00003564 assert( pTab!=0 );
drh7d10d5a2008-08-20 16:35:10 +00003565 if( (pTab->tabFlags & TF_Ephemeral)!=0 || pTab->pSelect ) continue;
drh6df2acd2008-12-28 16:55:25 +00003566 if( (pWInfo->wctrlFlags & WHERE_OMIT_CLOSE)==0 ){
3567 if( !pWInfo->okOnePass && (pLevel->plan.wsFlags & WHERE_IDX_ONLY)==0 ){
3568 sqlite3VdbeAddOp1(v, OP_Close, pTabItem->iCursor);
3569 }
3570 if( (pLevel->plan.wsFlags & WHERE_INDEXED)!=0 ){
3571 sqlite3VdbeAddOp1(v, OP_Close, pLevel->iIdxCur);
3572 }
drh9012bcb2004-12-19 00:11:35 +00003573 }
3574
danielk197721de2e72007-11-29 17:43:27 +00003575 /* If this scan uses an index, make code substitutions to read data
3576 ** from the index in preference to the table. Sometimes, this means
3577 ** the table need never be read from. This is a performance boost,
3578 ** as the vdbe level waits until the table is read before actually
3579 ** seeking the table cursor to the record corresponding to the current
3580 ** position in the index.
drh9012bcb2004-12-19 00:11:35 +00003581 **
3582 ** Calls to the code generator in between sqlite3WhereBegin and
3583 ** sqlite3WhereEnd will have created code that references the table
3584 ** directly. This loop scans all that code looking for opcodes
3585 ** that reference the table and converts them into opcodes that
3586 ** reference the index.
3587 */
drh125feff2009-06-06 15:17:27 +00003588 if( (pLevel->plan.wsFlags & WHERE_INDEXED)!=0 && !db->mallocFailed){
danielk1977f0113002006-01-24 12:09:17 +00003589 int k, j, last;
drh9012bcb2004-12-19 00:11:35 +00003590 VdbeOp *pOp;
drh111a6a72008-12-21 03:51:16 +00003591 Index *pIdx = pLevel->plan.u.pIdx;
3592 int useIndexOnly = pLevel->plan.wsFlags & WHERE_IDX_ONLY;
drh9012bcb2004-12-19 00:11:35 +00003593
3594 assert( pIdx!=0 );
3595 pOp = sqlite3VdbeGetOp(v, pWInfo->iTop);
3596 last = sqlite3VdbeCurrentAddr(v);
danielk1977f0113002006-01-24 12:09:17 +00003597 for(k=pWInfo->iTop; k<last; k++, pOp++){
drh9012bcb2004-12-19 00:11:35 +00003598 if( pOp->p1!=pLevel->iTabCur ) continue;
3599 if( pOp->opcode==OP_Column ){
drh9012bcb2004-12-19 00:11:35 +00003600 for(j=0; j<pIdx->nColumn; j++){
3601 if( pOp->p2==pIdx->aiColumn[j] ){
3602 pOp->p2 = j;
danielk197721de2e72007-11-29 17:43:27 +00003603 pOp->p1 = pLevel->iIdxCur;
drh9012bcb2004-12-19 00:11:35 +00003604 break;
3605 }
3606 }
danielk197721de2e72007-11-29 17:43:27 +00003607 assert(!useIndexOnly || j<pIdx->nColumn);
drhf0863fe2005-06-12 21:35:51 +00003608 }else if( pOp->opcode==OP_Rowid ){
drh9012bcb2004-12-19 00:11:35 +00003609 pOp->p1 = pLevel->iIdxCur;
drhf0863fe2005-06-12 21:35:51 +00003610 pOp->opcode = OP_IdxRowid;
danielk197721de2e72007-11-29 17:43:27 +00003611 }else if( pOp->opcode==OP_NullRow && useIndexOnly ){
danielk19776c18b6e2005-01-30 09:17:58 +00003612 pOp->opcode = OP_Noop;
drh9012bcb2004-12-19 00:11:35 +00003613 }
3614 }
drh6b563442001-11-07 16:48:26 +00003615 }
drh19a775c2000-06-05 18:54:46 +00003616 }
drh9012bcb2004-12-19 00:11:35 +00003617
3618 /* Final cleanup
3619 */
drh10fe8402008-10-11 16:47:35 +00003620 whereInfoFree(db, pWInfo);
drh75897232000-05-29 14:26:00 +00003621 return;
3622}