blob: 47a0123b64d26497d6c3100d763ae3faf861a927 [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
drh51669862004-12-18 18:40:26 +000013** the WHERE clause of SQL statements. This module is reponsible for
14** generating the code that loops through a table looking for applicable
15** rows. Indices are selected and used to speed the search when doing
16** so is applicable. Because this module is responsible for selecting
17** indices, you might also think of this module as the "query optimizer".
drh75897232000-05-29 14:26:00 +000018**
drh51669862004-12-18 18:40:26 +000019** $Id: where.c,v 1.122 2004/12/18 18:40:27 drh Exp $
drh75897232000-05-29 14:26:00 +000020*/
21#include "sqliteInt.h"
22
23/*
24** The query generator uses an array of instances of this structure to
25** help it analyze the subexpressions of the WHERE clause. Each WHERE
26** clause subexpression is separated from the others by an AND operator.
drh51669862004-12-18 18:40:26 +000027**
28** The idxLeft and idxRight fields are the VDBE cursor numbers for the
29** table that contains the column that appears on the left-hand and
30** right-hand side of ExprInfo.p. If either side of ExprInfo.p is
31** something other than a simple column reference, then idxLeft or
32** idxRight are -1.
33**
34** It is the VDBE cursor number is the value stored in Expr.iTable
35** when Expr.op==TK_COLUMN and the value stored in SrcList.a[].iCursor.
36**
37** prereqLeft, prereqRight, and prereqAll record sets of cursor numbers,
38** but they do so indirectly. A single ExprMaskSet structure translates
39** cursor number into bits and the translated bit is stored in the prereq
40** fields. The translation is used in order to maximize the number of
41** bits that will fit in a Bitmask. The VDBE cursor numbers might be
42** spread out over the non-negative integers. For example, the cursor
43** numbers might be 3, 8, 9, 10, 20, 23, 41, and 45. The ExprMaskSet
44** translates these sparse cursor numbers into consecutive integers
45** beginning with 0 in order to make the best possible use of the available
46** bits in the Bitmask. So, in the example above, the cursor numbers
47** would be mapped into integers 0 through 7.
48**
49** prereqLeft tells us every VDBE cursor that is referenced on the
50** left-hand side of ExprInfo.p. prereqRight does the same for the
51** right-hand side of the expression. The following identity always
52** holds:
53**
54** prereqAll = prereqLeft | prereqRight
55**
56** The ExprInfo.indexable field is true if the ExprInfo.p expression
57** is of a form that might control an index. Indexable expressions
58** look like this:
59**
60** <column> <op> <expr>
61**
62** Where <column> is a simple column name and <op> is on of the operators
63** that allowedOp() recognizes.
drh75897232000-05-29 14:26:00 +000064*/
65typedef struct ExprInfo ExprInfo;
66struct ExprInfo {
67 Expr *p; /* Pointer to the subexpression */
drhe3184742002-06-19 14:27:05 +000068 u8 indexable; /* True if this subexprssion is usable by an index */
69 short int idxLeft; /* p->pLeft is a column in this table number. -1 if
drh967e8b72000-06-21 13:59:10 +000070 ** p->pLeft is not the column of any table */
drhe3184742002-06-19 14:27:05 +000071 short int idxRight; /* p->pRight is a column in this table number. -1 if
drh967e8b72000-06-21 13:59:10 +000072 ** p->pRight is not the column of any table */
drh51669862004-12-18 18:40:26 +000073 Bitmask prereqLeft; /* Bitmask of tables referenced by p->pLeft */
74 Bitmask prereqRight; /* Bitmask of tables referenced by p->pRight */
75 Bitmask prereqAll; /* Bitmask of tables referenced by p */
drh75897232000-05-29 14:26:00 +000076};
77
78/*
drh6a3ea0e2003-05-02 14:32:12 +000079** An instance of the following structure keeps track of a mapping
drh51669862004-12-18 18:40:26 +000080** between VDBE cursor numbers and bits of the bitmasks in ExprInfo.
81**
82** The VDBE cursor numbers are small integers contained in
83** SrcList_item.iCursor and Expr.iTable fields. For any given WHERE
84** clause, the cursor numbers might not begin with 0 and they might
85** contain gaps in the numbering sequence. But we want to make maximum
86** use of the bits in our bitmasks. This structure provides a mapping
87** from the sparse cursor numbers into consecutive integers beginning
88** with 0.
89**
90** If ExprMaskSet.ix[A]==B it means that The A-th bit of a Bitmask
91** corresponds VDBE cursor number B. The A-th bit of a bitmask is 1<<A.
92**
93** For example, if the WHERE clause expression used these VDBE
94** cursors: 4, 5, 8, 29, 57, 73. Then the ExprMaskSet structure
95** would map those cursor numbers into bits 0 through 5.
96**
97** Note that the mapping is not necessarily ordered. In the example
98** above, the mapping might go like this: 4->3, 5->1, 8->2, 29->0,
99** 57->5, 73->4. Or one of 719 other combinations might be used. It
100** does not really matter. What is important is that sparse cursor
101** numbers all get mapped into bit numbers that begin with 0 and contain
102** no gaps.
drh6a3ea0e2003-05-02 14:32:12 +0000103*/
104typedef struct ExprMaskSet ExprMaskSet;
105struct ExprMaskSet {
drh51669862004-12-18 18:40:26 +0000106 int n; /* Number of assigned cursor values */
107 int ix[sizeof(Bitmask)*8-1]; /* Cursor assigned to each bit */
drh6a3ea0e2003-05-02 14:32:12 +0000108};
109
110/*
drh75897232000-05-29 14:26:00 +0000111** Determine the number of elements in an array.
112*/
113#define ARRAYSIZE(X) (sizeof(X)/sizeof(X[0]))
114
115/*
drh51669862004-12-18 18:40:26 +0000116** This routine identifies subexpressions in the WHERE clause where
117** each subexpression is separate by the AND operator. aSlot is
118** filled with pointers to the subexpressions. For example:
drh75897232000-05-29 14:26:00 +0000119**
drh51669862004-12-18 18:40:26 +0000120** WHERE a=='hello' AND coalesce(b,11)<10 AND (c+12!=d OR c==22)
121** \________/ \_______________/ \________________/
122** slot[0] slot[1] slot[2]
123**
124** The original WHERE clause in pExpr is unaltered. All this routine
125** does is make aSlot[] entries point to substructure within pExpr.
126**
127** aSlot[] is an array of subexpressions structures. There are nSlot
128** spaces left in this array. This routine finds as many AND-separated
129** subexpressions as it can and puts pointers to those subexpressions
130** into aSlot[] entries. The return value is the number of slots filled.
drh75897232000-05-29 14:26:00 +0000131*/
132static int exprSplit(int nSlot, ExprInfo *aSlot, Expr *pExpr){
133 int cnt = 0;
134 if( pExpr==0 || nSlot<1 ) return 0;
135 if( nSlot==1 || pExpr->op!=TK_AND ){
136 aSlot[0].p = pExpr;
137 return 1;
138 }
139 if( pExpr->pLeft->op!=TK_AND ){
140 aSlot[0].p = pExpr->pLeft;
141 cnt = 1 + exprSplit(nSlot-1, &aSlot[1], pExpr->pRight);
142 }else{
drhdcd997e2003-01-31 17:21:49 +0000143 cnt = exprSplit(nSlot, aSlot, pExpr->pLeft);
144 cnt += exprSplit(nSlot-cnt, &aSlot[cnt], pExpr->pRight);
drh75897232000-05-29 14:26:00 +0000145 }
146 return cnt;
147}
148
149/*
drh6a3ea0e2003-05-02 14:32:12 +0000150** Initialize an expression mask set
151*/
152#define initMaskSet(P) memset(P, 0, sizeof(*P))
153
154/*
drh51669862004-12-18 18:40:26 +0000155** Return the bitmask for the given cursor number. Assign a new bitmask
drh6a3ea0e2003-05-02 14:32:12 +0000156** if this is the first time the cursor has been seen.
157*/
drh51669862004-12-18 18:40:26 +0000158static Bitmask getMask(ExprMaskSet *pMaskSet, int iCursor){
drh6a3ea0e2003-05-02 14:32:12 +0000159 int i;
160 for(i=0; i<pMaskSet->n; i++){
drh51669862004-12-18 18:40:26 +0000161 if( pMaskSet->ix[i]==iCursor ){
162 return ((Bitmask)1)<<i;
163 }
drh6a3ea0e2003-05-02 14:32:12 +0000164 }
165 if( i==pMaskSet->n && i<ARRAYSIZE(pMaskSet->ix) ){
166 pMaskSet->n++;
167 pMaskSet->ix[i] = iCursor;
drh51669862004-12-18 18:40:26 +0000168 return ((Bitmask)1)<<i;
drh6a3ea0e2003-05-02 14:32:12 +0000169 }
170 return 0;
171}
172
173/*
174** Destroy an expression mask set
175*/
176#define freeMaskSet(P) /* NO-OP */
177
178/*
drh75897232000-05-29 14:26:00 +0000179** This routine walks (recursively) an expression tree and generates
180** a bitmask indicating which tables are used in that expression
drh6a3ea0e2003-05-02 14:32:12 +0000181** tree.
drh75897232000-05-29 14:26:00 +0000182**
183** In order for this routine to work, the calling function must have
danielk19774adee202004-05-08 08:23:19 +0000184** previously invoked sqlite3ExprResolveIds() on the expression. See
drh75897232000-05-29 14:26:00 +0000185** the header comment on that routine for additional information.
danielk19774adee202004-05-08 08:23:19 +0000186** The sqlite3ExprResolveIds() routines looks for column names and
drh6a3ea0e2003-05-02 14:32:12 +0000187** sets their opcodes to TK_COLUMN and their Expr.iTable fields to
188** the VDBE cursor number of the table.
drh75897232000-05-29 14:26:00 +0000189*/
drh51669862004-12-18 18:40:26 +0000190static Bitmask exprTableUsage(ExprMaskSet *pMaskSet, Expr *p){
191 Bitmask mask = 0;
drh75897232000-05-29 14:26:00 +0000192 if( p==0 ) return 0;
drh967e8b72000-06-21 13:59:10 +0000193 if( p->op==TK_COLUMN ){
drh8feb4b12004-07-19 02:12:14 +0000194 mask = getMask(pMaskSet, p->iTable);
195 if( mask==0 ) mask = -1;
196 return mask;
drh75897232000-05-29 14:26:00 +0000197 }
198 if( p->pRight ){
drh6a3ea0e2003-05-02 14:32:12 +0000199 mask = exprTableUsage(pMaskSet, p->pRight);
drh75897232000-05-29 14:26:00 +0000200 }
201 if( p->pLeft ){
drh6a3ea0e2003-05-02 14:32:12 +0000202 mask |= exprTableUsage(pMaskSet, p->pLeft);
drh75897232000-05-29 14:26:00 +0000203 }
drhdd579122002-04-02 01:58:57 +0000204 if( p->pList ){
205 int i;
206 for(i=0; i<p->pList->nExpr; i++){
drh6a3ea0e2003-05-02 14:32:12 +0000207 mask |= exprTableUsage(pMaskSet, p->pList->a[i].pExpr);
drhdd579122002-04-02 01:58:57 +0000208 }
209 }
drh75897232000-05-29 14:26:00 +0000210 return mask;
211}
212
213/*
drh487ab3c2001-11-08 00:45:21 +0000214** Return TRUE if the given operator is one of the operators that is
drh51669862004-12-18 18:40:26 +0000215** allowed for an indexable WHERE clause term. The allowed operators are
drhc27a1ce2002-06-14 20:58:45 +0000216** "=", "<", ">", "<=", ">=", and "IN".
drh487ab3c2001-11-08 00:45:21 +0000217*/
218static int allowedOp(int op){
drh9a432672004-10-04 13:38:09 +0000219 assert( TK_GT==TK_LE-1 && TK_LE==TK_LT-1 && TK_LT==TK_GE-1 && TK_EQ==TK_GT-1);
220 return op==TK_IN || (op>=TK_EQ && op<=TK_GE);
drh487ab3c2001-11-08 00:45:21 +0000221}
222
223/*
drh51669862004-12-18 18:40:26 +0000224** Swap two objects of type T.
drh193bd772004-07-20 18:23:14 +0000225*/
226#define SWAP(TYPE,A,B) {TYPE t=A; A=B; B=t;}
227
228/*
229** Return the index in the SrcList that uses cursor iCur. If iCur is
230** used by the first entry in SrcList return 0. If iCur is used by
231** the second entry return 1. And so forth.
232**
233** SrcList is the set of tables in the FROM clause in the order that
234** they will be processed. The value returned here gives us an index
235** of which tables will be processed first.
236*/
237static int tableOrder(SrcList *pList, int iCur){
238 int i;
drh51669862004-12-18 18:40:26 +0000239 struct SrcList_item *pItem;
240 for(i=0, pItem=pList->a; i<pList->nSrc; i++, pItem++){
241 if( pItem->iCursor==iCur ) return i;
drh193bd772004-07-20 18:23:14 +0000242 }
243 return -1;
244}
245
246/*
drh75897232000-05-29 14:26:00 +0000247** The input to this routine is an ExprInfo structure with only the
248** "p" field filled in. The job of this routine is to analyze the
249** subexpression and populate all the other fields of the ExprInfo
250** structure.
251*/
drh193bd772004-07-20 18:23:14 +0000252static void exprAnalyze(SrcList *pSrc, ExprMaskSet *pMaskSet, ExprInfo *pInfo){
drh75897232000-05-29 14:26:00 +0000253 Expr *pExpr = pInfo->p;
drh6a3ea0e2003-05-02 14:32:12 +0000254 pInfo->prereqLeft = exprTableUsage(pMaskSet, pExpr->pLeft);
255 pInfo->prereqRight = exprTableUsage(pMaskSet, pExpr->pRight);
256 pInfo->prereqAll = exprTableUsage(pMaskSet, pExpr);
drh75897232000-05-29 14:26:00 +0000257 pInfo->indexable = 0;
258 pInfo->idxLeft = -1;
259 pInfo->idxRight = -1;
drh487ab3c2001-11-08 00:45:21 +0000260 if( allowedOp(pExpr->op) && (pInfo->prereqRight & pInfo->prereqLeft)==0 ){
drhd99f7062002-06-08 23:25:08 +0000261 if( pExpr->pRight && pExpr->pRight->op==TK_COLUMN ){
drh6a3ea0e2003-05-02 14:32:12 +0000262 pInfo->idxRight = pExpr->pRight->iTable;
drh75897232000-05-29 14:26:00 +0000263 pInfo->indexable = 1;
264 }
drh967e8b72000-06-21 13:59:10 +0000265 if( pExpr->pLeft->op==TK_COLUMN ){
drh6a3ea0e2003-05-02 14:32:12 +0000266 pInfo->idxLeft = pExpr->pLeft->iTable;
drh75897232000-05-29 14:26:00 +0000267 pInfo->indexable = 1;
268 }
269 }
drh193bd772004-07-20 18:23:14 +0000270 if( pInfo->indexable ){
271 assert( pInfo->idxLeft!=pInfo->idxRight );
272
273 /* We want the expression to be of the form "X = expr", not "expr = X".
274 ** So flip it over if necessary. If the expression is "X = Y", then
275 ** we want Y to come from an earlier table than X.
276 **
277 ** The collating sequence rule is to always choose the left expression.
278 ** So if we do a flip, we also have to move the collating sequence.
279 */
280 if( tableOrder(pSrc,pInfo->idxLeft)<tableOrder(pSrc,pInfo->idxRight) ){
281 assert( pExpr->op!=TK_IN );
282 SWAP(CollSeq*,pExpr->pRight->pColl,pExpr->pLeft->pColl);
283 SWAP(Expr*,pExpr->pRight,pExpr->pLeft);
drh9a432672004-10-04 13:38:09 +0000284 if( pExpr->op>=TK_GT ){
285 assert( TK_LT==TK_GT+2 );
286 assert( TK_GE==TK_LE+2 );
287 assert( TK_GT>TK_EQ );
288 assert( TK_GT<TK_LE );
289 assert( pExpr->op>=TK_GT && pExpr->op<=TK_GE );
290 pExpr->op = ((pExpr->op-TK_GT)^2)+TK_GT;
drh193bd772004-07-20 18:23:14 +0000291 }
292 SWAP(unsigned, pInfo->prereqLeft, pInfo->prereqRight);
293 SWAP(short int, pInfo->idxLeft, pInfo->idxRight);
294 }
295 }
296
drh75897232000-05-29 14:26:00 +0000297}
298
299/*
drhe3184742002-06-19 14:27:05 +0000300** pOrderBy is an ORDER BY clause from a SELECT statement. pTab is the
301** left-most table in the FROM clause of that same SELECT statement and
302** the table has a cursor number of "base".
303**
304** This routine attempts to find an index for pTab that generates the
305** correct record sequence for the given ORDER BY clause. The return value
306** is a pointer to an index that does the job. NULL is returned if the
307** table has no index that will generate the correct sort order.
308**
309** If there are two or more indices that generate the correct sort order
310** and pPreferredIdx is one of those indices, then return pPreferredIdx.
drhdd4852c2002-12-04 21:50:16 +0000311**
312** nEqCol is the number of columns of pPreferredIdx that are used as
313** equality constraints. Any index returned must have exactly this same
314** set of columns. The ORDER BY clause only matches index columns beyond the
315** the first nEqCol columns.
316**
317** All terms of the ORDER BY clause must be either ASC or DESC. The
318** *pbRev value is set to 1 if the ORDER BY clause is all DESC and it is
319** set to 0 if the ORDER BY clause is all ASC.
drhb6c29892004-11-22 19:12:19 +0000320**
321** TODO: If earlier terms of an ORDER BY clause match all terms of a
322** UNIQUE index, then subsequent terms of the ORDER BY can be ignored.
323** This optimization needs to be implemented.
drhe3184742002-06-19 14:27:05 +0000324*/
325static Index *findSortingIndex(
drhb6c29892004-11-22 19:12:19 +0000326 Parse *pParse, /* Parsing context */
drhe3184742002-06-19 14:27:05 +0000327 Table *pTab, /* The table to be sorted */
328 int base, /* Cursor number for pTab */
329 ExprList *pOrderBy, /* The ORDER BY clause */
drhc045ec52002-12-04 20:01:06 +0000330 Index *pPreferredIdx, /* Use this index, if possible and not NULL */
drhdd4852c2002-12-04 21:50:16 +0000331 int nEqCol, /* Number of index columns used with == constraints */
drhc045ec52002-12-04 20:01:06 +0000332 int *pbRev /* Set to 1 if ORDER BY is DESC */
drhe3184742002-06-19 14:27:05 +0000333){
drhb6c29892004-11-22 19:12:19 +0000334 int i, j; /* Loop counters */
335 Index *pMatch; /* Best matching index so far */
336 Index *pIdx; /* Current index */
337 int sortOrder; /* Which direction we are sorting */
drh9bb575f2004-09-06 17:24:11 +0000338 sqlite3 *db = pParse->db;
drhe3184742002-06-19 14:27:05 +0000339
340 assert( pOrderBy!=0 );
341 assert( pOrderBy->nExpr>0 );
drhb6c29892004-11-22 19:12:19 +0000342 assert( pPreferredIdx!=0 || nEqCol==0 );
drhd3d39e92004-05-20 22:16:29 +0000343 sortOrder = pOrderBy->a[0].sortOrder;
drhe3184742002-06-19 14:27:05 +0000344 for(i=0; i<pOrderBy->nExpr; i++){
345 Expr *p;
drhd3d39e92004-05-20 22:16:29 +0000346 if( pOrderBy->a[i].sortOrder!=sortOrder ){
drhc045ec52002-12-04 20:01:06 +0000347 /* Indices can only be used if all ORDER BY terms are either
348 ** DESC or ASC. Indices cannot be used on a mixture. */
drhe3184742002-06-19 14:27:05 +0000349 return 0;
350 }
351 p = pOrderBy->a[i].pExpr;
352 if( p->op!=TK_COLUMN || p->iTable!=base ){
353 /* Can not use an index sort on anything that is not a column in the
354 ** left-most table of the FROM clause */
355 return 0;
356 }
357 }
danielk19770202b292004-06-09 09:55:16 +0000358
drhb6c29892004-11-22 19:12:19 +0000359 /* If we get this far, it means the ORDER BY clause consists of columns
360 ** that are all either ascending or descending and which refer only to
361 ** the left-most table of the FROM clause. Find the index that is best
362 ** used for sorting.
drhe3184742002-06-19 14:27:05 +0000363 */
364 pMatch = 0;
365 for(pIdx=pTab->pIndex; pIdx; pIdx=pIdx->pNext){
drhdd4852c2002-12-04 21:50:16 +0000366 int nExpr = pOrderBy->nExpr;
367 if( pIdx->nColumn < nEqCol || pIdx->nColumn < nExpr ) continue;
368 for(i=j=0; i<nEqCol; i++){
danielk1977d2b65b92004-06-10 10:51:47 +0000369 CollSeq *pColl = sqlite3ExprCollSeq(pParse, pOrderBy->a[j].pExpr);
danielk19770202b292004-06-09 09:55:16 +0000370 if( !pColl ) pColl = db->pDfltColl;
drhdd4852c2002-12-04 21:50:16 +0000371 if( pPreferredIdx->aiColumn[i]!=pIdx->aiColumn[i] ) break;
danielk19770202b292004-06-09 09:55:16 +0000372 if( pPreferredIdx->keyInfo.aColl[i]!=pIdx->keyInfo.aColl[i] ) break;
373 if( j<nExpr &&
374 pOrderBy->a[j].pExpr->iColumn==pIdx->aiColumn[i] &&
375 pColl==pIdx->keyInfo.aColl[i]
376 ){
377 j++;
378 }
drhe3184742002-06-19 14:27:05 +0000379 }
drhdd4852c2002-12-04 21:50:16 +0000380 if( i<nEqCol ) continue;
381 for(i=0; i+j<nExpr; i++){
danielk1977d2b65b92004-06-10 10:51:47 +0000382 CollSeq *pColl = sqlite3ExprCollSeq(pParse, pOrderBy->a[i+j].pExpr);
danielk19770202b292004-06-09 09:55:16 +0000383 if( !pColl ) pColl = db->pDfltColl;
384 if( pOrderBy->a[i+j].pExpr->iColumn!=pIdx->aiColumn[i+nEqCol] ||
385 pColl!=pIdx->keyInfo.aColl[i+nEqCol] ) break;
drhdd4852c2002-12-04 21:50:16 +0000386 }
387 if( i+j>=nExpr ){
drhe3184742002-06-19 14:27:05 +0000388 pMatch = pIdx;
389 if( pIdx==pPreferredIdx ) break;
390 }
391 }
drhb6c29892004-11-22 19:12:19 +0000392 *pbRev = sortOrder==SQLITE_SO_DESC;
drhe3184742002-06-19 14:27:05 +0000393 return pMatch;
394}
395
396/*
drh51669862004-12-18 18:40:26 +0000397** This routine decides if pIdx can be used to satisfy the ORDER BY
398** clause. If it can, it returns 1. If pIdx cannot satisfy the
399** ORDER BY clause, this routine returns 0.
400**
401** pOrderBy is an ORDER BY clause from a SELECT statement. pTab is the
402** left-most table in the FROM clause of that same SELECT statement and
403** the table has a cursor number of "base". pIdx is an index on pTab.
404**
405** nEqCol is the number of columns of pIdx that are used as equality
406** constraints. Any of these columns may be missing from the ORDER BY
407** clause and the match can still be a success.
408**
409** If the index is UNIQUE, then the ORDER BY clause is allowed to have
410** additional terms past the end of the index and the match will still
411** be a success.
412**
413** All terms of the ORDER BY that match against the index must be either
414** ASC or DESC. (Terms of the ORDER BY clause past the end of a UNIQUE
415** index do not need to satisfy this constraint.) The *pbRev value is
416** set to 1 if the ORDER BY clause is all DESC and it is set to 0 if
417** the ORDER BY clause is all ASC.
418*/
419static int isSortingIndex(
420 Parse *pParse, /* Parsing context */
421 Index *pIdx, /* The index we are testing */
422 Table *pTab, /* The table to be sorted */
423 int base, /* Cursor number for pTab */
424 ExprList *pOrderBy, /* The ORDER BY clause */
425 int nEqCol, /* Number of index columns with == constraints */
426 int *pbRev /* Set to 1 if ORDER BY is DESC */
427){
428 int i, j; /* Loop counters */
429 int sortOrder; /* Which direction we are sorting */
430 int nTerm; /* Number of ORDER BY terms */
431 struct ExprList_item *pTerm; /* A term of the ORDER BY clause */
432 sqlite3 *db = pParse->db;
433
434 assert( pOrderBy!=0 );
435 nTerm = pOrderBy->nExpr;
436 assert( nTerm>0 );
437
438 /* Match terms of the ORDER BY clause against columns of
439 ** the index.
440 */
441 for(i=j=0, pTerm=pOrderBy->a; j<nTerm && i<pIdx->nColumn; i++){
442 Expr *pExpr; /* The expression of the ORDER BY pTerm */
443 CollSeq *pColl; /* The collating sequence of pExpr */
444
445 pExpr = pTerm->pExpr;
446 if( pExpr->op!=TK_COLUMN || pExpr->iTable!=base ){
447 /* Can not use an index sort on anything that is not a column in the
448 ** left-most table of the FROM clause */
449 return 0;
450 }
451 pColl = sqlite3ExprCollSeq(pParse, pExpr);
452 if( !pColl ) pColl = db->pDfltColl;
453 if( pExpr->iColumn!=pIdx->aiColumn[i] && pColl!=pIdx->keyInfo.aColl[i] ){
454 if( i<=nEqCol ){
455 /* If an index column that is constrained by == fails to match an
456 ** ORDER BY term, that is OK. Just ignore that column of the index
457 */
458 continue;
459 }else{
460 /* If an index column fails to match and is not constrained by ==
461 ** then the index cannot satisfy the ORDER BY constraint.
462 */
463 return 0;
464 }
465 }
466 if( i>nEqCol ){
467 if( pTerm->sortOrder!=sortOrder ){
468 /* Indices can only be used if all ORDER BY terms past the
469 ** equality constraints are all either DESC or ASC. */
470 return 0;
471 }
472 }else{
473 sortOrder = pTerm->sortOrder;
474 }
475 j++;
476 pTerm++;
477 }
478
479 /* The index can be used for sorting if all terms of the ORDER BY clause
480 ** or covered or if we ran out of index columns and the it is a UNIQUE
481 ** index.
482 */
483 if( j>=nTerm || (i>=pIdx->nColumn && pIdx->onError!=OE_None) ){
484 *pbRev = sortOrder==SQLITE_SO_DESC;
485 return 1;
486 }
487 return 0;
488}
489
490/*
drhb6c29892004-11-22 19:12:19 +0000491** Check table to see if the ORDER BY clause in pOrderBy can be satisfied
492** by sorting in order of ROWID. Return true if so and set *pbRev to be
493** true for reverse ROWID and false for forward ROWID order.
494*/
495static int sortableByRowid(
496 int base, /* Cursor number for table to be sorted */
497 ExprList *pOrderBy, /* The ORDER BY clause */
498 int *pbRev /* Set to 1 if ORDER BY is DESC */
499){
500 Expr *p;
501
502 assert( pOrderBy!=0 );
503 assert( pOrderBy->nExpr>0 );
504 p = pOrderBy->a[0].pExpr;
505 if( p->op==TK_COLUMN && p->iTable==base && p->iColumn==-1 ){
506 *pbRev = pOrderBy->a[0].sortOrder;
507 return 1;
508 }
509 return 0;
510}
511
512
513/*
drh2ffb1182004-07-19 19:14:01 +0000514** Disable a term in the WHERE clause. Except, do not disable the term
515** if it controls a LEFT OUTER JOIN and it did not originate in the ON
516** or USING clause of that join.
517**
518** Consider the term t2.z='ok' in the following queries:
519**
520** (1) SELECT * FROM t1 LEFT JOIN t2 ON t1.a=t2.x WHERE t2.z='ok'
521** (2) SELECT * FROM t1 LEFT JOIN t2 ON t1.a=t2.x AND t2.z='ok'
522** (3) SELECT * FROM t1, t2 WHERE t1.a=t2.x AND t2.z='ok'
523**
drh23bf66d2004-12-14 03:34:34 +0000524** The t2.z='ok' is disabled in the in (2) because it originates
drh2ffb1182004-07-19 19:14:01 +0000525** in the ON clause. The term is disabled in (3) because it is not part
526** of a LEFT OUTER JOIN. In (1), the term is not disabled.
527**
528** Disabling a term causes that term to not be tested in the inner loop
529** of the join. Disabling is an optimization. We would get the correct
530** results if nothing were ever disabled, but joins might run a little
531** slower. The trick is to disable as much as we can without disabling
532** too much. If we disabled in (1), we'd get the wrong answer.
533** See ticket #813.
534*/
535static void disableTerm(WhereLevel *pLevel, Expr **ppExpr){
536 Expr *pExpr = *ppExpr;
537 if( pLevel->iLeftJoin==0 || ExprHasProperty(pExpr, EP_FromJoin) ){
538 *ppExpr = 0;
539 }
540}
541
542/*
drh94a11212004-09-25 13:12:14 +0000543** Generate code that builds a probe for an index. Details:
544**
545** * Check the top nColumn entries on the stack. If any
546** of those entries are NULL, jump immediately to brk,
547** which is the loop exit, since no index entry will match
548** if any part of the key is NULL.
549**
550** * Construct a probe entry from the top nColumn entries in
551** the stack with affinities appropriate for index pIdx.
552*/
553static void buildIndexProbe(Vdbe *v, int nColumn, int brk, Index *pIdx){
554 sqlite3VdbeAddOp(v, OP_NotNull, -nColumn, sqlite3VdbeCurrentAddr(v)+3);
555 sqlite3VdbeAddOp(v, OP_Pop, nColumn, 0);
556 sqlite3VdbeAddOp(v, OP_Goto, 0, brk);
557 sqlite3VdbeAddOp(v, OP_MakeRecord, nColumn, 0);
558 sqlite3IndexAffinityStr(v, pIdx);
559}
560
561/*
562** Generate code for an equality term of the WHERE clause. An equality
563** term can be either X=expr or X IN (...). pTerm is the X.
564*/
565static void codeEqualityTerm(
566 Parse *pParse, /* The parsing context */
567 ExprInfo *pTerm, /* The term of the WHERE clause to be coded */
568 int brk, /* Jump here to abandon the loop */
569 WhereLevel *pLevel /* When level of the FROM clause we are working on */
570){
571 Expr *pX = pTerm->p;
572 if( pX->op!=TK_IN ){
573 assert( pX->op==TK_EQ );
574 sqlite3ExprCode(pParse, pX->pRight);
575 }else{
576 int iTab = pX->iTable;
577 Vdbe *v = pParse->pVdbe;
578 sqlite3VdbeAddOp(v, OP_Rewind, iTab, brk);
579 sqlite3VdbeAddOp(v, OP_KeyAsData, iTab, 1);
580 pLevel->inP2 = sqlite3VdbeAddOp(v, OP_IdxColumn, iTab, 0);
581 pLevel->inOp = OP_Next;
582 pLevel->inP1 = iTab;
583 }
584 disableTerm(pLevel, &pTerm->p);
585}
586
drh51669862004-12-18 18:40:26 +0000587/*
588** The number of bits in a Bitmask
589*/
590#define BMS (sizeof(Bitmask)*8-1)
591
drh94a11212004-09-25 13:12:14 +0000592
593/*
drhe3184742002-06-19 14:27:05 +0000594** Generate the beginning of the loop used for WHERE clause processing.
drh75897232000-05-29 14:26:00 +0000595** The return value is a pointer to an (opaque) structure that contains
596** information needed to terminate the loop. Later, the calling routine
danielk19774adee202004-05-08 08:23:19 +0000597** should invoke sqlite3WhereEnd() with the return value of this function
drh75897232000-05-29 14:26:00 +0000598** in order to complete the WHERE clause processing.
599**
600** If an error occurs, this routine returns NULL.
drhc27a1ce2002-06-14 20:58:45 +0000601**
602** The basic idea is to do a nested loop, one loop for each table in
603** the FROM clause of a select. (INSERT and UPDATE statements are the
604** same as a SELECT with only a single table in the FROM clause.) For
605** example, if the SQL is this:
606**
607** SELECT * FROM t1, t2, t3 WHERE ...;
608**
609** Then the code generated is conceptually like the following:
610**
611** foreach row1 in t1 do \ Code generated
danielk19774adee202004-05-08 08:23:19 +0000612** foreach row2 in t2 do |-- by sqlite3WhereBegin()
drhc27a1ce2002-06-14 20:58:45 +0000613** foreach row3 in t3 do /
614** ...
615** end \ Code generated
danielk19774adee202004-05-08 08:23:19 +0000616** end |-- by sqlite3WhereEnd()
drhc27a1ce2002-06-14 20:58:45 +0000617** end /
618**
619** There are Btree cursors associated with each table. t1 uses cursor
drh6a3ea0e2003-05-02 14:32:12 +0000620** number pTabList->a[0].iCursor. t2 uses the cursor pTabList->a[1].iCursor.
621** And so forth. This routine generates code to open those VDBE cursors
danielk19774adee202004-05-08 08:23:19 +0000622** and sqlite3WhereEnd() generates the code to close them.
drhc27a1ce2002-06-14 20:58:45 +0000623**
624** If the WHERE clause is empty, the foreach loops must each scan their
625** entire tables. Thus a three-way join is an O(N^3) operation. But if
626** the tables have indices and there are terms in the WHERE clause that
627** refer to those indices, a complete table scan can be avoided and the
628** code will run much faster. Most of the work of this routine is checking
629** to see if there are indices that can be used to speed up the loop.
630**
631** Terms of the WHERE clause are also used to limit which rows actually
632** make it to the "..." in the middle of the loop. After each "foreach",
633** terms of the WHERE clause that use only terms in that loop and outer
634** loops are evaluated and if false a jump is made around all subsequent
635** inner loops (or around the "..." if the test occurs within the inner-
636** most loop)
637**
638** OUTER JOINS
639**
640** An outer join of tables t1 and t2 is conceptally coded as follows:
641**
642** foreach row1 in t1 do
643** flag = 0
644** foreach row2 in t2 do
645** start:
646** ...
647** flag = 1
648** end
drhe3184742002-06-19 14:27:05 +0000649** if flag==0 then
650** move the row2 cursor to a null row
651** goto start
652** fi
drhc27a1ce2002-06-14 20:58:45 +0000653** end
654**
drhe3184742002-06-19 14:27:05 +0000655** ORDER BY CLAUSE PROCESSING
656**
657** *ppOrderBy is a pointer to the ORDER BY clause of a SELECT statement,
658** if there is one. If there is no ORDER BY clause or if this routine
659** is called from an UPDATE or DELETE statement, then ppOrderBy is NULL.
660**
661** If an index can be used so that the natural output order of the table
662** scan is correct for the ORDER BY clause, then that index is used and
663** *ppOrderBy is set to NULL. This is an optimization that prevents an
664** unnecessary sort of the result set if an index appropriate for the
665** ORDER BY clause already exists.
666**
667** If the where clause loops cannot be arranged to provide the correct
668** output order, then the *ppOrderBy is unchanged.
drh75897232000-05-29 14:26:00 +0000669*/
danielk19774adee202004-05-08 08:23:19 +0000670WhereInfo *sqlite3WhereBegin(
danielk1977ed326d72004-11-16 15:50:19 +0000671 Parse *pParse, /* The parser context */
672 SrcList *pTabList, /* A list of all tables to be scanned */
673 Expr *pWhere, /* The WHERE clause */
674 int pushKey, /* If TRUE, leave the table key on the stack */
drhe4e72072004-11-23 01:47:30 +0000675 ExprList **ppOrderBy, /* An ORDER BY clause, or NULL */
676 Fetch *pFetch /* Initial location of cursors. NULL otherwise */
drh75897232000-05-29 14:26:00 +0000677){
678 int i; /* Loop counter */
679 WhereInfo *pWInfo; /* Will become the return value of this function */
680 Vdbe *v = pParse->pVdbe; /* The virtual database engine */
drhd4f5ee22003-07-16 00:54:31 +0000681 int brk, cont = 0; /* Addresses used during code generation */
drh75897232000-05-29 14:26:00 +0000682 int nExpr; /* Number of subexpressions in the WHERE clause */
drh51669862004-12-18 18:40:26 +0000683 Bitmask loopMask; /* One bit set for each outer loop */
danielk1977f7df9cc2004-06-16 12:02:47 +0000684 int haveKey = 0; /* True if KEY is on the stack */
drh193bd772004-07-20 18:23:14 +0000685 ExprInfo *pTerm; /* A single term in the WHERE clause; ptr to aExpr[] */
drh6a3ea0e2003-05-02 14:32:12 +0000686 ExprMaskSet maskSet; /* The expression mask set */
drh51669862004-12-18 18:40:26 +0000687 int iDirectEq[BMS]; /* Term of the form ROWID==X for the N-th table */
688 int iDirectLt[BMS]; /* Term of the form ROWID<X or ROWID<=X */
689 int iDirectGt[BMS]; /* Term of the form ROWID>X or ROWID>=X */
drh193bd772004-07-20 18:23:14 +0000690 ExprInfo aExpr[101]; /* The WHERE clause is divided into these terms */
drh75897232000-05-29 14:26:00 +0000691
drhc27a1ce2002-06-14 20:58:45 +0000692 /* pushKey is only allowed if there is a single table (as in an INSERT or
693 ** UPDATE statement)
694 */
695 assert( pushKey==0 || pTabList->nSrc==1 );
drh83dcb1a2002-06-28 01:02:38 +0000696
697 /* Split the WHERE clause into separate subexpressions where each
698 ** subexpression is separated by an AND operator. If the aExpr[]
699 ** array fills up, the last entry might point to an expression which
700 ** contains additional unfactored AND operators.
701 */
drh6a3ea0e2003-05-02 14:32:12 +0000702 initMaskSet(&maskSet);
drh83dcb1a2002-06-28 01:02:38 +0000703 memset(aExpr, 0, sizeof(aExpr));
704 nExpr = exprSplit(ARRAYSIZE(aExpr), aExpr, pWhere);
705 if( nExpr==ARRAYSIZE(aExpr) ){
danielk19774adee202004-05-08 08:23:19 +0000706 sqlite3ErrorMsg(pParse, "WHERE clause too complex - no more "
drhf7a9e1a2004-02-22 18:40:56 +0000707 "than %d terms allowed", (int)ARRAYSIZE(aExpr)-1);
drh83dcb1a2002-06-28 01:02:38 +0000708 return 0;
709 }
drhc27a1ce2002-06-14 20:58:45 +0000710
drh75897232000-05-29 14:26:00 +0000711 /* Allocate and initialize the WhereInfo structure that will become the
712 ** return value.
713 */
drhad3cab52002-05-24 02:04:32 +0000714 pWInfo = sqliteMalloc( sizeof(WhereInfo) + pTabList->nSrc*sizeof(WhereLevel));
danielk1977132872b2004-05-10 10:37:18 +0000715 if( sqlite3_malloc_failed ){
drh193bd772004-07-20 18:23:14 +0000716 /* sqliteFree(pWInfo); // Leak memory when malloc fails */
drh75897232000-05-29 14:26:00 +0000717 return 0;
718 }
719 pWInfo->pParse = pParse;
720 pWInfo->pTabList = pTabList;
danielk19774adee202004-05-08 08:23:19 +0000721 pWInfo->iBreak = sqlite3VdbeMakeLabel(v);
drh08192d52002-04-30 19:20:28 +0000722
723 /* Special case: a WHERE clause that is constant. Evaluate the
724 ** expression and either jump over all of the code or fall thru.
725 */
danielk19774adee202004-05-08 08:23:19 +0000726 if( pWhere && (pTabList->nSrc==0 || sqlite3ExprIsConstant(pWhere)) ){
727 sqlite3ExprIfFalse(pParse, pWhere, pWInfo->iBreak, 1);
drhdf199a22002-06-14 22:38:41 +0000728 pWhere = 0;
drh08192d52002-04-30 19:20:28 +0000729 }
drh75897232000-05-29 14:26:00 +0000730
drh75897232000-05-29 14:26:00 +0000731 /* Analyze all of the subexpressions.
732 */
drh193bd772004-07-20 18:23:14 +0000733 for(pTerm=aExpr, i=0; i<nExpr; i++, pTerm++){
734 TriggerStack *pStack;
735 exprAnalyze(pTabList, &maskSet, pTerm);
drh1d1f3052002-05-21 13:18:25 +0000736
737 /* If we are executing a trigger body, remove all references to
738 ** new.* and old.* tables from the prerequisite masks.
739 */
drh193bd772004-07-20 18:23:14 +0000740 if( (pStack = pParse->trigStack)!=0 ){
drh1d1f3052002-05-21 13:18:25 +0000741 int x;
drh193bd772004-07-20 18:23:14 +0000742 if( (x=pStack->newIdx) >= 0 ){
drh51669862004-12-18 18:40:26 +0000743 Bitmask mask = ~getMask(&maskSet, x);
drh193bd772004-07-20 18:23:14 +0000744 pTerm->prereqRight &= mask;
745 pTerm->prereqLeft &= mask;
746 pTerm->prereqAll &= mask;
drh1d1f3052002-05-21 13:18:25 +0000747 }
drh193bd772004-07-20 18:23:14 +0000748 if( (x=pStack->oldIdx) >= 0 ){
drh51669862004-12-18 18:40:26 +0000749 Bitmask mask = ~getMask(&maskSet, x);
drh193bd772004-07-20 18:23:14 +0000750 pTerm->prereqRight &= mask;
751 pTerm->prereqLeft &= mask;
752 pTerm->prereqAll &= mask;
drh1d1f3052002-05-21 13:18:25 +0000753 }
danielk1977c3f9bad2002-05-15 08:30:12 +0000754 }
drh75897232000-05-29 14:26:00 +0000755 }
756
drh75897232000-05-29 14:26:00 +0000757 /* Figure out what index to use (if any) for each nested loop.
drh6b563442001-11-07 16:48:26 +0000758 ** Make pWInfo->a[i].pIdx point to the index to use for the i-th nested
drhad3cab52002-05-24 02:04:32 +0000759 ** loop where i==0 is the outer loop and i==pTabList->nSrc-1 is the inner
drh8aff1012001-12-22 14:49:24 +0000760 ** loop.
761 **
762 ** If terms exist that use the ROWID of any table, then set the
763 ** iDirectEq[], iDirectLt[], or iDirectGt[] elements for that table
764 ** to the index of the term containing the ROWID. We always prefer
765 ** to use a ROWID which can directly access a table rather than an
drh0a36c572002-02-18 22:49:59 +0000766 ** index which requires reading an index first to get the rowid then
767 ** doing a second read of the actual database table.
drh75897232000-05-29 14:26:00 +0000768 **
769 ** Actually, if there are more than 32 tables in the join, only the
drh0a36c572002-02-18 22:49:59 +0000770 ** first 32 tables are candidates for indices. This is (again) due
771 ** to the limit of 32 bits in an integer bitmask.
drh75897232000-05-29 14:26:00 +0000772 */
773 loopMask = 0;
drhcb485882002-08-15 13:50:48 +0000774 for(i=0; i<pTabList->nSrc && i<ARRAYSIZE(iDirectEq); i++){
drhc4a3c772001-04-04 11:48:57 +0000775 int j;
drh94a11212004-09-25 13:12:14 +0000776 WhereLevel *pLevel = &pWInfo->a[i];
drh51669862004-12-18 18:40:26 +0000777 int iCur = pTabList->a[i].iCursor; /* The cursor for this table */
778 Bitmask mask = getMask(&maskSet, iCur); /* Cursor mask for this table */
drh6a3ea0e2003-05-02 14:32:12 +0000779 Table *pTab = pTabList->a[i].pTab;
drh75897232000-05-29 14:26:00 +0000780 Index *pIdx;
781 Index *pBestIdx = 0;
drh487ab3c2001-11-08 00:45:21 +0000782 int bestScore = 0;
drh51669862004-12-18 18:40:26 +0000783 int bestRev = 0;
drh75897232000-05-29 14:26:00 +0000784
drhc4a3c772001-04-04 11:48:57 +0000785 /* Check to see if there is an expression that uses only the
drh8aff1012001-12-22 14:49:24 +0000786 ** ROWID field of this table. For terms of the form ROWID==expr
787 ** set iDirectEq[i] to the index of the term. For terms of the
788 ** form ROWID<expr or ROWID<=expr set iDirectLt[i] to the term index.
789 ** For terms like ROWID>expr or ROWID>=expr set iDirectGt[i].
drh174b6192002-12-03 02:22:52 +0000790 **
791 ** (Added:) Treat ROWID IN expr like ROWID=expr.
drhc4a3c772001-04-04 11:48:57 +0000792 */
drh94a11212004-09-25 13:12:14 +0000793 pLevel->iCur = -1;
drh8aff1012001-12-22 14:49:24 +0000794 iDirectEq[i] = -1;
795 iDirectLt[i] = -1;
796 iDirectGt[i] = -1;
drh193bd772004-07-20 18:23:14 +0000797 for(pTerm=aExpr, j=0; j<nExpr; j++, pTerm++){
798 Expr *pX = pTerm->p;
799 if( pTerm->idxLeft==iCur && pX->pLeft->iColumn<0
800 && (pTerm->prereqRight & loopMask)==pTerm->prereqRight ){
801 switch( pX->op ){
drhd99f7062002-06-08 23:25:08 +0000802 case TK_IN:
drh8aff1012001-12-22 14:49:24 +0000803 case TK_EQ: iDirectEq[i] = j; break;
804 case TK_LE:
805 case TK_LT: iDirectLt[i] = j; break;
806 case TK_GE:
807 case TK_GT: iDirectGt[i] = j; break;
808 }
drhc4a3c772001-04-04 11:48:57 +0000809 }
drhc4a3c772001-04-04 11:48:57 +0000810 }
drhb6c29892004-11-22 19:12:19 +0000811
812 /* If we found a term that tests ROWID with == or IN, that term
813 ** will be used to locate the rows in the database table. There
814 ** is not need to continue into the code below that looks for
815 ** an index. We will always use the ROWID over an index.
816 */
drh8aff1012001-12-22 14:49:24 +0000817 if( iDirectEq[i]>=0 ){
drh6a3ea0e2003-05-02 14:32:12 +0000818 loopMask |= mask;
drh94a11212004-09-25 13:12:14 +0000819 pLevel->pIdx = 0;
drhc4a3c772001-04-04 11:48:57 +0000820 continue;
821 }
822
drh75897232000-05-29 14:26:00 +0000823 /* Do a search for usable indices. Leave pBestIdx pointing to
drh487ab3c2001-11-08 00:45:21 +0000824 ** the "best" index. pBestIdx is left set to NULL if no indices
825 ** are usable.
drh75897232000-05-29 14:26:00 +0000826 **
drh487ab3c2001-11-08 00:45:21 +0000827 ** The best index is determined as follows. For each of the
828 ** left-most terms that is fixed by an equality operator, add
drh51669862004-12-18 18:40:26 +0000829 ** 32 to the score. The right-most term of the index may be
830 ** constrained by an inequality. Add 4 if for an "x<..." constraint
831 ** and add 8 for an "x>..." constraint. If both constraints
832 ** are present, add 12.
833 **
834 ** If the left-most term of the index uses an IN operator
835 ** (ex: "x IN (...)") then add 16 to the score.
836 **
837 ** If an index can be used for sorting, add 2 to the score.
838 ** If an index contains all the terms of a table that are ever
839 ** used by any expression in the SQL statement, then add 1 to
840 ** the score.
drh487ab3c2001-11-08 00:45:21 +0000841 **
842 ** This scoring system is designed so that the score can later be
drh51669862004-12-18 18:40:26 +0000843 ** used to determine how the index is used. If the score&0x1c is 0
844 ** then all constraints are equalities. If score&0x4 is not 0 then
drh487ab3c2001-11-08 00:45:21 +0000845 ** there is an inequality used as a termination key. (ex: "x<...")
drh51669862004-12-18 18:40:26 +0000846 ** If score&0x8 is not 0 then there is an inequality used as the
847 ** start key. (ex: "x>..."). A score or 0x10 is the special case
drhc045ec52002-12-04 20:01:06 +0000848 ** of an IN operator constraint. (ex: "x IN ...").
drhd99f7062002-06-08 23:25:08 +0000849 **
drhc27a1ce2002-06-14 20:58:45 +0000850 ** The IN operator (as in "<expr> IN (...)") is treated the same as
851 ** an equality comparison except that it can only be used on the
852 ** left-most column of an index and other terms of the WHERE clause
853 ** cannot be used in conjunction with the IN operator to help satisfy
854 ** other columns of the index.
drh75897232000-05-29 14:26:00 +0000855 */
856 for(pIdx=pTab->pIndex; pIdx; pIdx=pIdx->pNext){
drh51669862004-12-18 18:40:26 +0000857 Bitmask eqMask = 0; /* Index columns covered by an x=... term */
858 Bitmask ltMask = 0; /* Index columns covered by an x<... term */
859 Bitmask gtMask = 0; /* Index columns covered by an x>... term */
860 Bitmask inMask = 0; /* Index columns covered by an x IN .. term */
861 Bitmask m;
862 int nEq, score, bRev = 0;
drh75897232000-05-29 14:26:00 +0000863
drh51669862004-12-18 18:40:26 +0000864 if( pIdx->nColumn>sizeof(eqMask)*8 ){
865 continue; /* Ignore indices with too many columns to analyze */
866 }
drh193bd772004-07-20 18:23:14 +0000867 for(pTerm=aExpr, j=0; j<nExpr; j++, pTerm++){
drh193bd772004-07-20 18:23:14 +0000868 Expr *pX = pTerm->p;
drh94a11212004-09-25 13:12:14 +0000869 CollSeq *pColl = sqlite3ExprCollSeq(pParse, pX->pLeft);
drh193bd772004-07-20 18:23:14 +0000870 if( !pColl && pX->pRight ){
871 pColl = sqlite3ExprCollSeq(pParse, pX->pRight);
danielk19770202b292004-06-09 09:55:16 +0000872 }
873 if( !pColl ){
874 pColl = pParse->db->pDfltColl;
875 }
drh193bd772004-07-20 18:23:14 +0000876 if( pTerm->idxLeft==iCur
877 && (pTerm->prereqRight & loopMask)==pTerm->prereqRight ){
878 int iColumn = pX->pLeft->iColumn;
drh75897232000-05-29 14:26:00 +0000879 int k;
danielk1977e014a832004-05-17 10:48:57 +0000880 char idxaff = pIdx->pTable->aCol[iColumn].affinity;
drh967e8b72000-06-21 13:59:10 +0000881 for(k=0; k<pIdx->nColumn; k++){
danielk19770202b292004-06-09 09:55:16 +0000882 /* If the collating sequences or affinities don't match,
883 ** ignore this index. */
884 if( pColl!=pIdx->keyInfo.aColl[k] ) continue;
drh193bd772004-07-20 18:23:14 +0000885 if( !sqlite3IndexAffinityOk(pX, idxaff) ) continue;
danielk19770202b292004-06-09 09:55:16 +0000886 if( pIdx->aiColumn[k]==iColumn ){
drh193bd772004-07-20 18:23:14 +0000887 switch( pX->op ){
drh48185c12002-06-09 01:55:20 +0000888 case TK_IN: {
889 if( k==0 ) inMask |= 1;
890 break;
891 }
drh487ab3c2001-11-08 00:45:21 +0000892 case TK_EQ: {
drh51669862004-12-18 18:40:26 +0000893 eqMask |= ((Bitmask)1)<<k;
drh487ab3c2001-11-08 00:45:21 +0000894 break;
895 }
896 case TK_LE:
897 case TK_LT: {
drh51669862004-12-18 18:40:26 +0000898 ltMask |= ((Bitmask)1)<<k;
drh487ab3c2001-11-08 00:45:21 +0000899 break;
900 }
901 case TK_GE:
902 case TK_GT: {
drh51669862004-12-18 18:40:26 +0000903 gtMask |= ((Bitmask)1)<<k;
drh487ab3c2001-11-08 00:45:21 +0000904 break;
905 }
906 default: {
907 /* CANT_HAPPEN */
908 assert( 0 );
909 break;
910 }
911 }
drh75897232000-05-29 14:26:00 +0000912 break;
913 }
914 }
915 }
drh75897232000-05-29 14:26:00 +0000916 }
drhc045ec52002-12-04 20:01:06 +0000917
918 /* The following loop ends with nEq set to the number of columns
919 ** on the left of the index with == constraints.
920 */
drh487ab3c2001-11-08 00:45:21 +0000921 for(nEq=0; nEq<pIdx->nColumn; nEq++){
drh51669862004-12-18 18:40:26 +0000922 m = (((Bitmask)1)<<(nEq+1))-1;
drh487ab3c2001-11-08 00:45:21 +0000923 if( (m & eqMask)!=m ) break;
924 }
drh51669862004-12-18 18:40:26 +0000925
926 /* Begin assemblying the score
927 */
928 score = nEq*32; /* Base score is 32 times number of == constraints */
929 m = ((Bitmask)1)<<nEq;
930 if( m & ltMask ) score+=4; /* Increase score for a < constraint */
931 if( m & gtMask ) score+=8; /* Increase score for a > constraint */
932 if( score==0 && inMask ) score = 16; /* Default score for IN constraint */
933
934 /* Give bonus points if this index can be used for sorting
935 */
936 if( i==0 && score>0 && ppOrderBy && *ppOrderBy ){
937 int base = pTabList->a[0].iCursor;
938 if( isSortingIndex(pParse, pIdx, pTab, base, *ppOrderBy, nEq, &bRev) ){
939 score += 2;
940 }
941 }
942
943 /* If the score for this index is the best we have seen so far, then
944 ** save it
945 */
drh487ab3c2001-11-08 00:45:21 +0000946 if( score>bestScore ){
947 pBestIdx = pIdx;
948 bestScore = score;
drh51669862004-12-18 18:40:26 +0000949 bestRev = bRev;
drh75897232000-05-29 14:26:00 +0000950 }
951 }
drh94a11212004-09-25 13:12:14 +0000952 pLevel->pIdx = pBestIdx;
953 pLevel->score = bestScore;
drh51669862004-12-18 18:40:26 +0000954 pLevel->bRev = bestRev;
drh6a3ea0e2003-05-02 14:32:12 +0000955 loopMask |= mask;
drh6b563442001-11-07 16:48:26 +0000956 if( pBestIdx ){
drh94a11212004-09-25 13:12:14 +0000957 pLevel->iCur = pParse->nTab++;
drh6b563442001-11-07 16:48:26 +0000958 }
drh75897232000-05-29 14:26:00 +0000959 }
960
drhe3184742002-06-19 14:27:05 +0000961 /* Check to see if the ORDER BY clause is or can be satisfied by the
962 ** use of an index on the first table.
963 */
964 if( ppOrderBy && *ppOrderBy && pTabList->nSrc>0 ){
drhb6c29892004-11-22 19:12:19 +0000965 Index *pSortIdx = 0; /* Index that satisfies the ORDER BY clause */
966 Index *pIdx; /* Index derived from the WHERE clause */
967 Table *pTab; /* Left-most table in the FROM clause */
968 int bRev = 0; /* True to reverse the output order */
969 int iCur; /* Btree-cursor that will be used by pTab */
970 WhereLevel *pLevel0 = &pWInfo->a[0];
drhe3184742002-06-19 14:27:05 +0000971
972 pTab = pTabList->a[0].pTab;
drhb6c29892004-11-22 19:12:19 +0000973 pIdx = pLevel0->pIdx;
974 iCur = pTabList->a[0].iCursor;
975 if( pIdx==0 && sortableByRowid(iCur, *ppOrderBy, &bRev) ){
976 /* The ORDER BY clause specifies ROWID order, which is what we
977 ** were going to be doing anyway...
978 */
979 *ppOrderBy = 0;
980 pLevel0->bRev = bRev;
drh51669862004-12-18 18:40:26 +0000981 }else if( pLevel0->score==16 ){
drhc045ec52002-12-04 20:01:06 +0000982 /* If there is already an IN index on the left-most table,
983 ** it will not give the correct sort order.
984 ** So, pretend that no suitable index is found.
drhe3184742002-06-19 14:27:05 +0000985 */
drhe3184742002-06-19 14:27:05 +0000986 }else if( iDirectEq[0]>=0 || iDirectLt[0]>=0 || iDirectGt[0]>=0 ){
987 /* If the left-most column is accessed using its ROWID, then do
drhb6c29892004-11-22 19:12:19 +0000988 ** not try to sort by index. But do delete the ORDER BY clause
989 ** if it is redundant.
drhe3184742002-06-19 14:27:05 +0000990 */
drhe3184742002-06-19 14:27:05 +0000991 }else{
drh51669862004-12-18 18:40:26 +0000992 int nEqCol = (pLevel0->score+16)/32;
drhb6c29892004-11-22 19:12:19 +0000993 pSortIdx = findSortingIndex(pParse, pTab, iCur,
drh6a3ea0e2003-05-02 14:32:12 +0000994 *ppOrderBy, pIdx, nEqCol, &bRev);
drhe3184742002-06-19 14:27:05 +0000995 }
996 if( pSortIdx && (pIdx==0 || pIdx==pSortIdx) ){
997 if( pIdx==0 ){
drhb6c29892004-11-22 19:12:19 +0000998 pLevel0->pIdx = pSortIdx;
999 pLevel0->iCur = pParse->nTab++;
drhe3184742002-06-19 14:27:05 +00001000 }
drhb6c29892004-11-22 19:12:19 +00001001 pLevel0->bRev = bRev;
drhe3184742002-06-19 14:27:05 +00001002 *ppOrderBy = 0;
1003 }
1004 }
1005
drh6b563442001-11-07 16:48:26 +00001006 /* Open all tables in the pTabList and all indices used by those tables.
drh75897232000-05-29 14:26:00 +00001007 */
drhc275b4e2004-07-19 17:25:24 +00001008 sqlite3CodeVerifySchema(pParse, -1); /* Insert the cookie verifier Goto */
drhad3cab52002-05-24 02:04:32 +00001009 for(i=0; i<pTabList->nSrc; i++){
drhf57b3392001-10-08 13:22:32 +00001010 Table *pTab;
drh701a0ae2004-02-22 20:05:00 +00001011 Index *pIx;
drhf57b3392001-10-08 13:22:32 +00001012
1013 pTab = pTabList->a[i].pTab;
drha76b5df2002-02-23 02:32:10 +00001014 if( pTab->isTransient || pTab->pSelect ) continue;
danielk1977299b1872004-11-22 10:02:10 +00001015 sqlite3OpenTableForReading(v, pTabList->a[i].iCursor, pTab);
danielk1977f9d19a62004-06-14 08:26:35 +00001016 sqlite3CodeVerifySchema(pParse, pTab->iDb);
drh701a0ae2004-02-22 20:05:00 +00001017 if( (pIx = pWInfo->a[i].pIdx)!=0 ){
danielk19774adee202004-05-08 08:23:19 +00001018 sqlite3VdbeAddOp(v, OP_Integer, pIx->iDb, 0);
drhd3d39e92004-05-20 22:16:29 +00001019 sqlite3VdbeOp3(v, OP_OpenRead, pWInfo->a[i].iCur, pIx->tnum,
1020 (char*)&pIx->keyInfo, P3_KEYINFO);
drh75897232000-05-29 14:26:00 +00001021 }
1022 }
1023
1024 /* Generate the code to do the search
1025 */
drh75897232000-05-29 14:26:00 +00001026 loopMask = 0;
drhad3cab52002-05-24 02:04:32 +00001027 for(i=0; i<pTabList->nSrc; i++){
drh75897232000-05-29 14:26:00 +00001028 int j, k;
drh6a3ea0e2003-05-02 14:32:12 +00001029 int iCur = pTabList->a[i].iCursor;
drhc4a3c772001-04-04 11:48:57 +00001030 Index *pIdx;
drh6b563442001-11-07 16:48:26 +00001031 WhereLevel *pLevel = &pWInfo->a[i];
drh75897232000-05-29 14:26:00 +00001032
drhad2d8302002-05-24 20:31:36 +00001033 /* If this is the right table of a LEFT OUTER JOIN, allocate and
drh174b6192002-12-03 02:22:52 +00001034 ** initialize a memory cell that records if this table matches any
drhc27a1ce2002-06-14 20:58:45 +00001035 ** row of the left table of the join.
drhad2d8302002-05-24 20:31:36 +00001036 */
1037 if( i>0 && (pTabList->a[i-1].jointype & JT_LEFT)!=0 ){
1038 if( !pParse->nMem ) pParse->nMem++;
1039 pLevel->iLeftJoin = pParse->nMem++;
danielk19770f69c1e2004-05-29 11:24:50 +00001040 sqlite3VdbeAddOp(v, OP_String8, 0, 0);
danielk19774adee202004-05-08 08:23:19 +00001041 sqlite3VdbeAddOp(v, OP_MemStore, pLevel->iLeftJoin, 1);
drhad6d9462004-09-19 02:15:24 +00001042 VdbeComment((v, "# init LEFT JOIN no-match flag"));
drhad2d8302002-05-24 20:31:36 +00001043 }
1044
drh8aff1012001-12-22 14:49:24 +00001045 pIdx = pLevel->pIdx;
drhd99f7062002-06-08 23:25:08 +00001046 pLevel->inOp = OP_Noop;
drh94a11212004-09-25 13:12:14 +00001047 if( i<ARRAYSIZE(iDirectEq) && (k = iDirectEq[i])>=0 ){
drh8aff1012001-12-22 14:49:24 +00001048 /* Case 1: We can directly reference a single row using an
drhc27a1ce2002-06-14 20:58:45 +00001049 ** equality comparison against the ROWID field. Or
1050 ** we reference multiple rows using a "rowid IN (...)"
1051 ** construct.
drhc4a3c772001-04-04 11:48:57 +00001052 */
drh8aff1012001-12-22 14:49:24 +00001053 assert( k<nExpr );
drh193bd772004-07-20 18:23:14 +00001054 pTerm = &aExpr[k];
1055 assert( pTerm->p!=0 );
drh193bd772004-07-20 18:23:14 +00001056 assert( pTerm->idxLeft==iCur );
drh94a11212004-09-25 13:12:14 +00001057 brk = pLevel->brk = sqlite3VdbeMakeLabel(v);
1058 codeEqualityTerm(pParse, pTerm, brk, pLevel);
danielk19774adee202004-05-08 08:23:19 +00001059 cont = pLevel->cont = sqlite3VdbeMakeLabel(v);
1060 sqlite3VdbeAddOp(v, OP_MustBeInt, 1, brk);
drhd99f7062002-06-08 23:25:08 +00001061 haveKey = 0;
danielk19774adee202004-05-08 08:23:19 +00001062 sqlite3VdbeAddOp(v, OP_NotExists, iCur, brk);
drh6b563442001-11-07 16:48:26 +00001063 pLevel->op = OP_Noop;
drh51669862004-12-18 18:40:26 +00001064 }else if( pIdx!=0 && pLevel->score>0 && (pLevel->score&0x0c)==0 ){
drhc27a1ce2002-06-14 20:58:45 +00001065 /* Case 2: There is an index and all terms of the WHERE clause that
drhb6c29892004-11-22 19:12:19 +00001066 ** refer to the index using the "==" or "IN" operators.
drh75897232000-05-29 14:26:00 +00001067 */
drh6b563442001-11-07 16:48:26 +00001068 int start;
drh51669862004-12-18 18:40:26 +00001069 int nColumn = (pLevel->score+16)/32;
danielk19774adee202004-05-08 08:23:19 +00001070 brk = pLevel->brk = sqlite3VdbeMakeLabel(v);
drh772ae622004-05-19 13:13:08 +00001071
1072 /* For each column of the index, find the term of the WHERE clause that
1073 ** constraints that column. If the WHERE clause term is X=expr, then
1074 ** evaluation expr and leave the result on the stack */
drh487ab3c2001-11-08 00:45:21 +00001075 for(j=0; j<nColumn; j++){
drh193bd772004-07-20 18:23:14 +00001076 for(pTerm=aExpr, k=0; k<nExpr; k++, pTerm++){
1077 Expr *pX = pTerm->p;
drhd99f7062002-06-08 23:25:08 +00001078 if( pX==0 ) continue;
drh193bd772004-07-20 18:23:14 +00001079 if( pTerm->idxLeft==iCur
1080 && (pTerm->prereqRight & loopMask)==pTerm->prereqRight
drhd99f7062002-06-08 23:25:08 +00001081 && pX->pLeft->iColumn==pIdx->aiColumn[j]
drh75897232000-05-29 14:26:00 +00001082 ){
danielk1977e014a832004-05-17 10:48:57 +00001083 char idxaff = pIdx->pTable->aCol[pX->pLeft->iColumn].affinity;
drh94a11212004-09-25 13:12:14 +00001084 if( sqlite3IndexAffinityOk(pX, idxaff) ){
1085 codeEqualityTerm(pParse, pTerm, brk, pLevel);
1086 break;
drhd99f7062002-06-08 23:25:08 +00001087 }
drh75897232000-05-29 14:26:00 +00001088 }
drh75897232000-05-29 14:26:00 +00001089 }
1090 }
drh6b563442001-11-07 16:48:26 +00001091 pLevel->iMem = pParse->nMem++;
danielk19774adee202004-05-08 08:23:19 +00001092 cont = pLevel->cont = sqlite3VdbeMakeLabel(v);
drh94a11212004-09-25 13:12:14 +00001093 buildIndexProbe(v, nColumn, brk, pIdx);
danielk19773d1bfea2004-05-14 11:00:53 +00001094 sqlite3VdbeAddOp(v, OP_MemStore, pLevel->iMem, 0);
drh772ae622004-05-19 13:13:08 +00001095
drh772ae622004-05-19 13:13:08 +00001096 /* Generate code (1) to move to the first matching element of the table.
1097 ** Then generate code (2) that jumps to "brk" after the cursor is past
1098 ** the last matching element of the table. The code (1) is executed
1099 ** once to initialize the search, the code (2) is executed before each
1100 ** iteration of the scan to see if the scan has finished. */
drhc045ec52002-12-04 20:01:06 +00001101 if( pLevel->bRev ){
1102 /* Scan in reverse order */
drh7cf6e4d2004-05-19 14:56:55 +00001103 sqlite3VdbeAddOp(v, OP_MoveLe, pLevel->iCur, brk);
danielk19774adee202004-05-08 08:23:19 +00001104 start = sqlite3VdbeAddOp(v, OP_MemLoad, pLevel->iMem, 0);
1105 sqlite3VdbeAddOp(v, OP_IdxLT, pLevel->iCur, brk);
drhc045ec52002-12-04 20:01:06 +00001106 pLevel->op = OP_Prev;
1107 }else{
1108 /* Scan in the forward order */
drh7cf6e4d2004-05-19 14:56:55 +00001109 sqlite3VdbeAddOp(v, OP_MoveGe, pLevel->iCur, brk);
danielk19774adee202004-05-08 08:23:19 +00001110 start = sqlite3VdbeAddOp(v, OP_MemLoad, pLevel->iMem, 0);
drhfec19aa2004-05-19 20:41:03 +00001111 sqlite3VdbeOp3(v, OP_IdxGE, pLevel->iCur, brk, "+", P3_STATIC);
drhc045ec52002-12-04 20:01:06 +00001112 pLevel->op = OP_Next;
1113 }
danielk19774adee202004-05-08 08:23:19 +00001114 sqlite3VdbeAddOp(v, OP_RowKey, pLevel->iCur, 0);
1115 sqlite3VdbeAddOp(v, OP_IdxIsNull, nColumn, cont);
1116 sqlite3VdbeAddOp(v, OP_IdxRecno, pLevel->iCur, 0);
drhad3cab52002-05-24 02:04:32 +00001117 if( i==pTabList->nSrc-1 && pushKey ){
drh75897232000-05-29 14:26:00 +00001118 haveKey = 1;
1119 }else{
drh7cf6e4d2004-05-19 14:56:55 +00001120 sqlite3VdbeAddOp(v, OP_MoveGe, iCur, 0);
drh75897232000-05-29 14:26:00 +00001121 haveKey = 0;
1122 }
drh6b563442001-11-07 16:48:26 +00001123 pLevel->p1 = pLevel->iCur;
1124 pLevel->p2 = start;
drh8aff1012001-12-22 14:49:24 +00001125 }else if( i<ARRAYSIZE(iDirectLt) && (iDirectLt[i]>=0 || iDirectGt[i]>=0) ){
1126 /* Case 3: We have an inequality comparison against the ROWID field.
1127 */
1128 int testOp = OP_Noop;
1129 int start;
drhb6c29892004-11-22 19:12:19 +00001130 int bRev = pLevel->bRev;
drh8aff1012001-12-22 14:49:24 +00001131
danielk19774adee202004-05-08 08:23:19 +00001132 brk = pLevel->brk = sqlite3VdbeMakeLabel(v);
1133 cont = pLevel->cont = sqlite3VdbeMakeLabel(v);
drhb6c29892004-11-22 19:12:19 +00001134 if( bRev ){
1135 int t = iDirectGt[i];
1136 iDirectGt[i] = iDirectLt[i];
1137 iDirectLt[i] = t;
1138 }
drh8aff1012001-12-22 14:49:24 +00001139 if( iDirectGt[i]>=0 ){
drh94a11212004-09-25 13:12:14 +00001140 Expr *pX;
drh8aff1012001-12-22 14:49:24 +00001141 k = iDirectGt[i];
1142 assert( k<nExpr );
drh193bd772004-07-20 18:23:14 +00001143 pTerm = &aExpr[k];
drh94a11212004-09-25 13:12:14 +00001144 pX = pTerm->p;
1145 assert( pX!=0 );
drh193bd772004-07-20 18:23:14 +00001146 assert( pTerm->idxLeft==iCur );
drh94a11212004-09-25 13:12:14 +00001147 sqlite3ExprCode(pParse, pX->pRight);
1148 sqlite3VdbeAddOp(v, OP_ForceInt, pX->op==TK_LT || pX->op==TK_GT, brk);
drhb6c29892004-11-22 19:12:19 +00001149 sqlite3VdbeAddOp(v, bRev ? OP_MoveLt : OP_MoveGe, iCur, brk);
drh193bd772004-07-20 18:23:14 +00001150 disableTerm(pLevel, &pTerm->p);
drh8aff1012001-12-22 14:49:24 +00001151 }else{
drhb6c29892004-11-22 19:12:19 +00001152 sqlite3VdbeAddOp(v, bRev ? OP_Last : OP_Rewind, iCur, brk);
drh8aff1012001-12-22 14:49:24 +00001153 }
1154 if( iDirectLt[i]>=0 ){
drh94a11212004-09-25 13:12:14 +00001155 Expr *pX;
drh8aff1012001-12-22 14:49:24 +00001156 k = iDirectLt[i];
1157 assert( k<nExpr );
drh193bd772004-07-20 18:23:14 +00001158 pTerm = &aExpr[k];
drh94a11212004-09-25 13:12:14 +00001159 pX = pTerm->p;
1160 assert( pX!=0 );
drh193bd772004-07-20 18:23:14 +00001161 assert( pTerm->idxLeft==iCur );
drh94a11212004-09-25 13:12:14 +00001162 sqlite3ExprCode(pParse, pX->pRight);
drh8aff1012001-12-22 14:49:24 +00001163 pLevel->iMem = pParse->nMem++;
danielk19774adee202004-05-08 08:23:19 +00001164 sqlite3VdbeAddOp(v, OP_MemStore, pLevel->iMem, 1);
drh94a11212004-09-25 13:12:14 +00001165 if( pX->op==TK_LT || pX->op==TK_GT ){
drhb6c29892004-11-22 19:12:19 +00001166 testOp = bRev ? OP_Le : OP_Ge;
drh8aff1012001-12-22 14:49:24 +00001167 }else{
drhb6c29892004-11-22 19:12:19 +00001168 testOp = bRev ? OP_Lt : OP_Gt;
drh8aff1012001-12-22 14:49:24 +00001169 }
drh193bd772004-07-20 18:23:14 +00001170 disableTerm(pLevel, &pTerm->p);
drh8aff1012001-12-22 14:49:24 +00001171 }
danielk19774adee202004-05-08 08:23:19 +00001172 start = sqlite3VdbeCurrentAddr(v);
drhb6c29892004-11-22 19:12:19 +00001173 pLevel->op = bRev ? OP_Prev : OP_Next;
drh6a3ea0e2003-05-02 14:32:12 +00001174 pLevel->p1 = iCur;
drh8aff1012001-12-22 14:49:24 +00001175 pLevel->p2 = start;
1176 if( testOp!=OP_Noop ){
danielk19774adee202004-05-08 08:23:19 +00001177 sqlite3VdbeAddOp(v, OP_Recno, iCur, 0);
1178 sqlite3VdbeAddOp(v, OP_MemLoad, pLevel->iMem, 0);
1179 sqlite3VdbeAddOp(v, testOp, 0, brk);
drh8aff1012001-12-22 14:49:24 +00001180 }
1181 haveKey = 0;
1182 }else if( pIdx==0 ){
drhc27a1ce2002-06-14 20:58:45 +00001183 /* Case 4: There is no usable index. We must do a complete
drh8aff1012001-12-22 14:49:24 +00001184 ** scan of the entire database table.
1185 */
1186 int start;
drhb6c29892004-11-22 19:12:19 +00001187 int opRewind;
drh8aff1012001-12-22 14:49:24 +00001188
danielk19774adee202004-05-08 08:23:19 +00001189 brk = pLevel->brk = sqlite3VdbeMakeLabel(v);
1190 cont = pLevel->cont = sqlite3VdbeMakeLabel(v);
drhb6c29892004-11-22 19:12:19 +00001191 if( pLevel->bRev ){
1192 opRewind = OP_Last;
1193 pLevel->op = OP_Prev;
1194 }else{
1195 opRewind = OP_Rewind;
1196 pLevel->op = OP_Next;
1197 }
1198 sqlite3VdbeAddOp(v, opRewind, iCur, brk);
danielk19774adee202004-05-08 08:23:19 +00001199 start = sqlite3VdbeCurrentAddr(v);
drh6a3ea0e2003-05-02 14:32:12 +00001200 pLevel->p1 = iCur;
drh8aff1012001-12-22 14:49:24 +00001201 pLevel->p2 = start;
1202 haveKey = 0;
drh487ab3c2001-11-08 00:45:21 +00001203 }else{
drhc27a1ce2002-06-14 20:58:45 +00001204 /* Case 5: The WHERE clause term that refers to the right-most
1205 ** column of the index is an inequality. For example, if
1206 ** the index is on (x,y,z) and the WHERE clause is of the
1207 ** form "x=5 AND y<10" then this case is used. Only the
1208 ** right-most column can be an inequality - the rest must
1209 ** use the "==" operator.
drhe3184742002-06-19 14:27:05 +00001210 **
1211 ** This case is also used when there are no WHERE clause
1212 ** constraints but an index is selected anyway, in order
1213 ** to force the output order to conform to an ORDER BY.
drh487ab3c2001-11-08 00:45:21 +00001214 */
1215 int score = pLevel->score;
drh51669862004-12-18 18:40:26 +00001216 int nEqColumn = score/32;
drh487ab3c2001-11-08 00:45:21 +00001217 int start;
danielk1977f7df9cc2004-06-16 12:02:47 +00001218 int leFlag=0, geFlag=0;
drh487ab3c2001-11-08 00:45:21 +00001219 int testOp;
1220
1221 /* Evaluate the equality constraints
1222 */
1223 for(j=0; j<nEqColumn; j++){
drh94a11212004-09-25 13:12:14 +00001224 int iIdxCol = pIdx->aiColumn[j];
drh193bd772004-07-20 18:23:14 +00001225 for(pTerm=aExpr, k=0; k<nExpr; k++, pTerm++){
drh94a11212004-09-25 13:12:14 +00001226 Expr *pX = pTerm->p;
1227 if( pX==0 ) continue;
drh193bd772004-07-20 18:23:14 +00001228 if( pTerm->idxLeft==iCur
drh94a11212004-09-25 13:12:14 +00001229 && pX->op==TK_EQ
drh193bd772004-07-20 18:23:14 +00001230 && (pTerm->prereqRight & loopMask)==pTerm->prereqRight
drh94a11212004-09-25 13:12:14 +00001231 && pX->pLeft->iColumn==iIdxCol
drh487ab3c2001-11-08 00:45:21 +00001232 ){
drh94a11212004-09-25 13:12:14 +00001233 sqlite3ExprCode(pParse, pX->pRight);
drh193bd772004-07-20 18:23:14 +00001234 disableTerm(pLevel, &pTerm->p);
drh487ab3c2001-11-08 00:45:21 +00001235 break;
1236 }
1237 }
1238 }
1239
drhc27a1ce2002-06-14 20:58:45 +00001240 /* Duplicate the equality term values because they will all be
drh487ab3c2001-11-08 00:45:21 +00001241 ** used twice: once to make the termination key and once to make the
1242 ** start key.
1243 */
1244 for(j=0; j<nEqColumn; j++){
danielk19774adee202004-05-08 08:23:19 +00001245 sqlite3VdbeAddOp(v, OP_Dup, nEqColumn-1, 0);
drh487ab3c2001-11-08 00:45:21 +00001246 }
1247
drhc045ec52002-12-04 20:01:06 +00001248 /* Labels for the beginning and end of the loop
1249 */
danielk19774adee202004-05-08 08:23:19 +00001250 cont = pLevel->cont = sqlite3VdbeMakeLabel(v);
1251 brk = pLevel->brk = sqlite3VdbeMakeLabel(v);
drhc045ec52002-12-04 20:01:06 +00001252
drh487ab3c2001-11-08 00:45:21 +00001253 /* Generate the termination key. This is the key value that
1254 ** will end the search. There is no termination key if there
drhc27a1ce2002-06-14 20:58:45 +00001255 ** are no equality terms and no "X<..." term.
drhc045ec52002-12-04 20:01:06 +00001256 **
1257 ** 2002-Dec-04: On a reverse-order scan, the so-called "termination"
1258 ** key computed here really ends up being the start key.
drh487ab3c2001-11-08 00:45:21 +00001259 */
drh51669862004-12-18 18:40:26 +00001260 if( (score & 4)!=0 ){
drh193bd772004-07-20 18:23:14 +00001261 for(pTerm=aExpr, k=0; k<nExpr; k++, pTerm++){
drh94a11212004-09-25 13:12:14 +00001262 Expr *pX = pTerm->p;
1263 if( pX==0 ) continue;
drh193bd772004-07-20 18:23:14 +00001264 if( pTerm->idxLeft==iCur
drh94a11212004-09-25 13:12:14 +00001265 && (pX->op==TK_LT || pX->op==TK_LE)
drh193bd772004-07-20 18:23:14 +00001266 && (pTerm->prereqRight & loopMask)==pTerm->prereqRight
drh94a11212004-09-25 13:12:14 +00001267 && pX->pLeft->iColumn==pIdx->aiColumn[j]
drh487ab3c2001-11-08 00:45:21 +00001268 ){
drh94a11212004-09-25 13:12:14 +00001269 sqlite3ExprCode(pParse, pX->pRight);
1270 leFlag = pX->op==TK_LE;
drh193bd772004-07-20 18:23:14 +00001271 disableTerm(pLevel, &pTerm->p);
drh487ab3c2001-11-08 00:45:21 +00001272 break;
1273 }
1274 }
1275 testOp = OP_IdxGE;
1276 }else{
1277 testOp = nEqColumn>0 ? OP_IdxGE : OP_Noop;
1278 leFlag = 1;
1279 }
1280 if( testOp!=OP_Noop ){
drh51669862004-12-18 18:40:26 +00001281 int nCol = nEqColumn + ((score & 4)!=0);
drh487ab3c2001-11-08 00:45:21 +00001282 pLevel->iMem = pParse->nMem++;
drh94a11212004-09-25 13:12:14 +00001283 buildIndexProbe(v, nCol, brk, pIdx);
drhc045ec52002-12-04 20:01:06 +00001284 if( pLevel->bRev ){
drh7cf6e4d2004-05-19 14:56:55 +00001285 int op = leFlag ? OP_MoveLe : OP_MoveLt;
1286 sqlite3VdbeAddOp(v, op, pLevel->iCur, brk);
drhc045ec52002-12-04 20:01:06 +00001287 }else{
danielk19774adee202004-05-08 08:23:19 +00001288 sqlite3VdbeAddOp(v, OP_MemStore, pLevel->iMem, 1);
drhc045ec52002-12-04 20:01:06 +00001289 }
1290 }else if( pLevel->bRev ){
danielk19774adee202004-05-08 08:23:19 +00001291 sqlite3VdbeAddOp(v, OP_Last, pLevel->iCur, brk);
drh487ab3c2001-11-08 00:45:21 +00001292 }
1293
1294 /* Generate the start key. This is the key that defines the lower
drhc27a1ce2002-06-14 20:58:45 +00001295 ** bound on the search. There is no start key if there are no
1296 ** equality terms and if there is no "X>..." term. In
drh487ab3c2001-11-08 00:45:21 +00001297 ** that case, generate a "Rewind" instruction in place of the
1298 ** start key search.
drhc045ec52002-12-04 20:01:06 +00001299 **
1300 ** 2002-Dec-04: In the case of a reverse-order search, the so-called
1301 ** "start" key really ends up being used as the termination key.
drh487ab3c2001-11-08 00:45:21 +00001302 */
drh51669862004-12-18 18:40:26 +00001303 if( (score & 8)!=0 ){
drh193bd772004-07-20 18:23:14 +00001304 for(pTerm=aExpr, k=0; k<nExpr; k++, pTerm++){
drh94a11212004-09-25 13:12:14 +00001305 Expr *pX = pTerm->p;
1306 if( pX==0 ) continue;
drh193bd772004-07-20 18:23:14 +00001307 if( pTerm->idxLeft==iCur
drh94a11212004-09-25 13:12:14 +00001308 && (pX->op==TK_GT || pX->op==TK_GE)
drh193bd772004-07-20 18:23:14 +00001309 && (pTerm->prereqRight & loopMask)==pTerm->prereqRight
drh94a11212004-09-25 13:12:14 +00001310 && pX->pLeft->iColumn==pIdx->aiColumn[j]
drh487ab3c2001-11-08 00:45:21 +00001311 ){
drh94a11212004-09-25 13:12:14 +00001312 sqlite3ExprCode(pParse, pX->pRight);
1313 geFlag = pX->op==TK_GE;
drh193bd772004-07-20 18:23:14 +00001314 disableTerm(pLevel, &pTerm->p);
drh487ab3c2001-11-08 00:45:21 +00001315 break;
1316 }
1317 }
drh7900ead2001-11-12 13:51:43 +00001318 }else{
1319 geFlag = 1;
drh487ab3c2001-11-08 00:45:21 +00001320 }
drh51669862004-12-18 18:40:26 +00001321 if( nEqColumn>0 || (score&8)!=0 ){
1322 int nCol = nEqColumn + ((score&8)!=0);
drh94a11212004-09-25 13:12:14 +00001323 buildIndexProbe(v, nCol, brk, pIdx);
drhc045ec52002-12-04 20:01:06 +00001324 if( pLevel->bRev ){
1325 pLevel->iMem = pParse->nMem++;
danielk19774adee202004-05-08 08:23:19 +00001326 sqlite3VdbeAddOp(v, OP_MemStore, pLevel->iMem, 1);
drhc045ec52002-12-04 20:01:06 +00001327 testOp = OP_IdxLT;
1328 }else{
drh7cf6e4d2004-05-19 14:56:55 +00001329 int op = geFlag ? OP_MoveGe : OP_MoveGt;
1330 sqlite3VdbeAddOp(v, op, pLevel->iCur, brk);
drhc045ec52002-12-04 20:01:06 +00001331 }
1332 }else if( pLevel->bRev ){
1333 testOp = OP_Noop;
drh487ab3c2001-11-08 00:45:21 +00001334 }else{
danielk19774adee202004-05-08 08:23:19 +00001335 sqlite3VdbeAddOp(v, OP_Rewind, pLevel->iCur, brk);
drh487ab3c2001-11-08 00:45:21 +00001336 }
1337
1338 /* Generate the the top of the loop. If there is a termination
1339 ** key we have to test for that key and abort at the top of the
1340 ** loop.
1341 */
danielk19774adee202004-05-08 08:23:19 +00001342 start = sqlite3VdbeCurrentAddr(v);
drh487ab3c2001-11-08 00:45:21 +00001343 if( testOp!=OP_Noop ){
danielk19774adee202004-05-08 08:23:19 +00001344 sqlite3VdbeAddOp(v, OP_MemLoad, pLevel->iMem, 0);
1345 sqlite3VdbeAddOp(v, testOp, pLevel->iCur, brk);
danielk19773d1bfea2004-05-14 11:00:53 +00001346 if( (leFlag && !pLevel->bRev) || (!geFlag && pLevel->bRev) ){
1347 sqlite3VdbeChangeP3(v, -1, "+", P3_STATIC);
1348 }
drh487ab3c2001-11-08 00:45:21 +00001349 }
danielk19774adee202004-05-08 08:23:19 +00001350 sqlite3VdbeAddOp(v, OP_RowKey, pLevel->iCur, 0);
drh51669862004-12-18 18:40:26 +00001351 sqlite3VdbeAddOp(v, OP_IdxIsNull, nEqColumn + ((score&4)!=0), cont);
danielk19774adee202004-05-08 08:23:19 +00001352 sqlite3VdbeAddOp(v, OP_IdxRecno, pLevel->iCur, 0);
drhad3cab52002-05-24 02:04:32 +00001353 if( i==pTabList->nSrc-1 && pushKey ){
drh487ab3c2001-11-08 00:45:21 +00001354 haveKey = 1;
1355 }else{
drh7cf6e4d2004-05-19 14:56:55 +00001356 sqlite3VdbeAddOp(v, OP_MoveGe, iCur, 0);
drh487ab3c2001-11-08 00:45:21 +00001357 haveKey = 0;
1358 }
1359
1360 /* Record the instruction used to terminate the loop.
1361 */
drhc045ec52002-12-04 20:01:06 +00001362 pLevel->op = pLevel->bRev ? OP_Prev : OP_Next;
drh487ab3c2001-11-08 00:45:21 +00001363 pLevel->p1 = pLevel->iCur;
1364 pLevel->p2 = start;
drh75897232000-05-29 14:26:00 +00001365 }
drh6a3ea0e2003-05-02 14:32:12 +00001366 loopMask |= getMask(&maskSet, iCur);
drh75897232000-05-29 14:26:00 +00001367
1368 /* Insert code to test every subexpression that can be completely
1369 ** computed using the current set of tables.
1370 */
drh193bd772004-07-20 18:23:14 +00001371 for(pTerm=aExpr, j=0; j<nExpr; j++, pTerm++){
1372 if( pTerm->p==0 ) continue;
1373 if( (pTerm->prereqAll & loopMask)!=pTerm->prereqAll ) continue;
1374 if( pLevel->iLeftJoin && !ExprHasProperty(pTerm->p,EP_FromJoin) ){
drh1f162302002-10-27 19:35:33 +00001375 continue;
1376 }
drh75897232000-05-29 14:26:00 +00001377 if( haveKey ){
drh573bd272001-02-19 23:23:38 +00001378 haveKey = 0;
drh7cf6e4d2004-05-19 14:56:55 +00001379 sqlite3VdbeAddOp(v, OP_MoveGe, iCur, 0);
drh75897232000-05-29 14:26:00 +00001380 }
drh193bd772004-07-20 18:23:14 +00001381 sqlite3ExprIfFalse(pParse, pTerm->p, cont, 1);
1382 pTerm->p = 0;
drh75897232000-05-29 14:26:00 +00001383 }
1384 brk = cont;
drhad2d8302002-05-24 20:31:36 +00001385
1386 /* For a LEFT OUTER JOIN, generate code that will record the fact that
1387 ** at least one row of the right table has matched the left table.
1388 */
1389 if( pLevel->iLeftJoin ){
danielk19774adee202004-05-08 08:23:19 +00001390 pLevel->top = sqlite3VdbeCurrentAddr(v);
1391 sqlite3VdbeAddOp(v, OP_Integer, 1, 0);
1392 sqlite3VdbeAddOp(v, OP_MemStore, pLevel->iLeftJoin, 1);
drhad6d9462004-09-19 02:15:24 +00001393 VdbeComment((v, "# record LEFT JOIN hit"));
drh193bd772004-07-20 18:23:14 +00001394 for(pTerm=aExpr, j=0; j<nExpr; j++, pTerm++){
1395 if( pTerm->p==0 ) continue;
1396 if( (pTerm->prereqAll & loopMask)!=pTerm->prereqAll ) continue;
drh1cc093c2002-06-24 22:01:57 +00001397 if( haveKey ){
drh3b167c72002-06-28 12:18:47 +00001398 /* Cannot happen. "haveKey" can only be true if pushKey is true
1399 ** an pushKey can only be true for DELETE and UPDATE and there are
1400 ** no outer joins with DELETE and UPDATE.
1401 */
drh1cc093c2002-06-24 22:01:57 +00001402 haveKey = 0;
drh7cf6e4d2004-05-19 14:56:55 +00001403 sqlite3VdbeAddOp(v, OP_MoveGe, iCur, 0);
drh1cc093c2002-06-24 22:01:57 +00001404 }
drh193bd772004-07-20 18:23:14 +00001405 sqlite3ExprIfFalse(pParse, pTerm->p, cont, 1);
1406 pTerm->p = 0;
drh1cc093c2002-06-24 22:01:57 +00001407 }
drhad2d8302002-05-24 20:31:36 +00001408 }
drh75897232000-05-29 14:26:00 +00001409 }
1410 pWInfo->iContinue = cont;
1411 if( pushKey && !haveKey ){
danielk19774adee202004-05-08 08:23:19 +00001412 sqlite3VdbeAddOp(v, OP_Recno, pTabList->a[0].iCursor, 0);
drh75897232000-05-29 14:26:00 +00001413 }
drh6a3ea0e2003-05-02 14:32:12 +00001414 freeMaskSet(&maskSet);
drh75897232000-05-29 14:26:00 +00001415 return pWInfo;
1416}
1417
1418/*
drhc27a1ce2002-06-14 20:58:45 +00001419** Generate the end of the WHERE loop. See comments on
danielk19774adee202004-05-08 08:23:19 +00001420** sqlite3WhereBegin() for additional information.
drh75897232000-05-29 14:26:00 +00001421*/
danielk19774adee202004-05-08 08:23:19 +00001422void sqlite3WhereEnd(WhereInfo *pWInfo){
drh75897232000-05-29 14:26:00 +00001423 Vdbe *v = pWInfo->pParse->pVdbe;
drh19a775c2000-06-05 18:54:46 +00001424 int i;
drh6b563442001-11-07 16:48:26 +00001425 WhereLevel *pLevel;
drhad3cab52002-05-24 02:04:32 +00001426 SrcList *pTabList = pWInfo->pTabList;
drh19a775c2000-06-05 18:54:46 +00001427
drhad3cab52002-05-24 02:04:32 +00001428 for(i=pTabList->nSrc-1; i>=0; i--){
drh6b563442001-11-07 16:48:26 +00001429 pLevel = &pWInfo->a[i];
danielk19774adee202004-05-08 08:23:19 +00001430 sqlite3VdbeResolveLabel(v, pLevel->cont);
drh6b563442001-11-07 16:48:26 +00001431 if( pLevel->op!=OP_Noop ){
danielk19774adee202004-05-08 08:23:19 +00001432 sqlite3VdbeAddOp(v, pLevel->op, pLevel->p1, pLevel->p2);
drh19a775c2000-06-05 18:54:46 +00001433 }
danielk19774adee202004-05-08 08:23:19 +00001434 sqlite3VdbeResolveLabel(v, pLevel->brk);
drhd99f7062002-06-08 23:25:08 +00001435 if( pLevel->inOp!=OP_Noop ){
danielk19774adee202004-05-08 08:23:19 +00001436 sqlite3VdbeAddOp(v, pLevel->inOp, pLevel->inP1, pLevel->inP2);
drhd99f7062002-06-08 23:25:08 +00001437 }
drhad2d8302002-05-24 20:31:36 +00001438 if( pLevel->iLeftJoin ){
1439 int addr;
danielk19774adee202004-05-08 08:23:19 +00001440 addr = sqlite3VdbeAddOp(v, OP_MemLoad, pLevel->iLeftJoin, 0);
1441 sqlite3VdbeAddOp(v, OP_NotNull, 1, addr+4 + (pLevel->iCur>=0));
1442 sqlite3VdbeAddOp(v, OP_NullRow, pTabList->a[i].iCursor, 0);
drh7f09b3e2002-08-13 13:15:49 +00001443 if( pLevel->iCur>=0 ){
danielk19774adee202004-05-08 08:23:19 +00001444 sqlite3VdbeAddOp(v, OP_NullRow, pLevel->iCur, 0);
drh7f09b3e2002-08-13 13:15:49 +00001445 }
danielk19774adee202004-05-08 08:23:19 +00001446 sqlite3VdbeAddOp(v, OP_Goto, 0, pLevel->top);
drhad2d8302002-05-24 20:31:36 +00001447 }
drh19a775c2000-06-05 18:54:46 +00001448 }
danielk19774adee202004-05-08 08:23:19 +00001449 sqlite3VdbeResolveLabel(v, pWInfo->iBreak);
drhad3cab52002-05-24 02:04:32 +00001450 for(i=0; i<pTabList->nSrc; i++){
drh5cf590c2003-04-24 01:45:04 +00001451 Table *pTab = pTabList->a[i].pTab;
1452 assert( pTab!=0 );
1453 if( pTab->isTransient || pTab->pSelect ) continue;
drh6b563442001-11-07 16:48:26 +00001454 pLevel = &pWInfo->a[i];
danielk19774adee202004-05-08 08:23:19 +00001455 sqlite3VdbeAddOp(v, OP_Close, pTabList->a[i].iCursor, 0);
drh6b563442001-11-07 16:48:26 +00001456 if( pLevel->pIdx!=0 ){
danielk19774adee202004-05-08 08:23:19 +00001457 sqlite3VdbeAddOp(v, OP_Close, pLevel->iCur, 0);
drh6b563442001-11-07 16:48:26 +00001458 }
drh19a775c2000-06-05 18:54:46 +00001459 }
drh75897232000-05-29 14:26:00 +00001460 sqliteFree(pWInfo);
1461 return;
1462}