/ Check-in [f09e19b4]
Login

Many hyperlinks are disabled.
Use anonymous login to enable hyperlinks.

Overview
Comment:The query optimizer now attempts to satisfy an ORDER BY clause using an index. Sorting is still used if there are no suitable indices. (CVS 628)
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1:f09e19b43ef61073713cf32282c90ea666229eba
User & Date: drh 2002-06-19 14:27:05
Context
2002-06-19
14:27
Version 2.5.1 (CVS 629) check-in: 5e8a3131 user: drh tags: trunk
14:27
The query optimizer now attempts to satisfy an ORDER BY clause using an index. Sorting is still used if there are no suitable indices. (CVS 628) check-in: f09e19b4 user: drh tags: trunk
2002-06-17
17:26
Version 2.5.0 (CVS 627) check-in: 9baef3e2 user: drh tags: trunk
Changes
Hide Diffs Unified Diffs Ignore Whitespace Patch

Changes to VERSION.

1
2.5.0
|
1
2.5.1

Changes to src/delete.c.

8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
...
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
**    May you find forgiveness for yourself and forgive others.
**    May you share freely, never taking more than you give.
**
*************************************************************************
** This file contains C code routines that are called by the parser
** to handle DELETE FROM statements.
**
** $Id: delete.c,v 1.37 2002/06/11 02:25:41 danielk1977 Exp $
*/
#include "sqliteInt.h"


/*
** Given a table name, find the corresponding table and make sure the
** table is writeable.  Generate an error and return NULL if not.  If
................................................................................

  /* The usual case: There is a WHERE clause so we have to scan through
  ** the table an pick which records to delete.
  */
  else{
    /* Begin the database scan
    */
    pWInfo = sqliteWhereBegin(pParse, base, pTabList, pWhere, 1);
    if( pWInfo==0 ) goto delete_from_cleanup;

    /* Remember the key of every item to be deleted.
    */
    sqliteVdbeAddOp(v, OP_ListWrite, 0, 0);
    if( db->flags & SQLITE_CountRows ){
      sqliteVdbeAddOp(v, OP_AddImm, 1, 0);







|







 







|







8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
...
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
**    May you find forgiveness for yourself and forgive others.
**    May you share freely, never taking more than you give.
**
*************************************************************************
** This file contains C code routines that are called by the parser
** to handle DELETE FROM statements.
**
** $Id: delete.c,v 1.38 2002/06/19 14:27:05 drh Exp $
*/
#include "sqliteInt.h"


/*
** Given a table name, find the corresponding table and make sure the
** table is writeable.  Generate an error and return NULL if not.  If
................................................................................

  /* The usual case: There is a WHERE clause so we have to scan through
  ** the table an pick which records to delete.
  */
  else{
    /* Begin the database scan
    */
    pWInfo = sqliteWhereBegin(pParse, base, pTabList, pWhere, 1, 0);
    if( pWInfo==0 ) goto delete_from_cleanup;

    /* Remember the key of every item to be deleted.
    */
    sqliteVdbeAddOp(v, OP_ListWrite, 0, 0);
    if( db->flags & SQLITE_CountRows ){
      sqliteVdbeAddOp(v, OP_AddImm, 1, 0);

Changes to src/select.c.

8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
....
1746
1747
1748
1749
1750
1751
1752
1753
1754
1755
1756
1757
1758
1759
1760
1761
1762
1763
1764
1765
1766
1767
1768
1769
1770
1771
1772
1773
**    May you find forgiveness for yourself and forgive others.
**    May you share freely, never taking more than you give.
**
*************************************************************************
** This file contains C code routines that are called by the parser
** to handle SELECT statements in SQLite.
**
** $Id: select.c,v 1.93 2002/06/14 22:38:42 drh Exp $
*/
#include "sqliteInt.h"

/*
** Allocate a new Select structure and return a pointer to that
** structure.
*/
................................................................................
    sqliteVdbeAddOp(v, OP_OpenTemp, distinct, 1);
  }else{
    distinct = -1;
  }

  /* Begin the database scan
  */
  pWInfo = sqliteWhereBegin(pParse, p->base, pTabList, pWhere, 0);
  if( pWInfo==0 ) goto select_end;

  /* Use the standard inner loop if we are not dealing with
  ** aggregates
  */
  if( !isAgg ){
    if( selectInnerLoop(pParse, p, pEList, 0, 0, pOrderBy, distinct, eDest,
                    iParm, pWInfo->iContinue, pWInfo->iBreak) ){
       goto select_end;
    }
  }

  /* If we are dealing with aggregates, then to the special aggregate
  ** processing.  
  */
  else{
    if( pGroupBy ){
      int lbl1;
      for(i=0; i<pGroupBy->nExpr; i++){
        sqliteExprCode(pParse, pGroupBy->a[i].pExpr);







|







 







|












|







8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
....
1746
1747
1748
1749
1750
1751
1752
1753
1754
1755
1756
1757
1758
1759
1760
1761
1762
1763
1764
1765
1766
1767
1768
1769
1770
1771
1772
1773
**    May you find forgiveness for yourself and forgive others.
**    May you share freely, never taking more than you give.
**
*************************************************************************
** This file contains C code routines that are called by the parser
** to handle SELECT statements in SQLite.
**
** $Id: select.c,v 1.94 2002/06/19 14:27:05 drh Exp $
*/
#include "sqliteInt.h"

/*
** Allocate a new Select structure and return a pointer to that
** structure.
*/
................................................................................
    sqliteVdbeAddOp(v, OP_OpenTemp, distinct, 1);
  }else{
    distinct = -1;
  }

  /* Begin the database scan
  */
  pWInfo = sqliteWhereBegin(pParse, p->base, pTabList, pWhere, 0, &pOrderBy);
  if( pWInfo==0 ) goto select_end;

  /* Use the standard inner loop if we are not dealing with
  ** aggregates
  */
  if( !isAgg ){
    if( selectInnerLoop(pParse, p, pEList, 0, 0, pOrderBy, distinct, eDest,
                    iParm, pWInfo->iContinue, pWInfo->iBreak) ){
       goto select_end;
    }
  }

  /* If we are dealing with aggregates, then do the special aggregate
  ** processing.  
  */
  else{
    if( pGroupBy ){
      int lbl1;
      for(i=0; i<pGroupBy->nExpr; i++){
        sqliteExprCode(pParse, pGroupBy->a[i].pExpr);

Changes to src/sqliteInt.h.

7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
...
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
**    May you do good and not evil.
**    May you find forgiveness for yourself and forgive others.
**    May you share freely, never taking more than you give.
**
*************************************************************************
** Internal interface definitions for SQLite.
**
** @(#) $Id: sqliteInt.h,v 1.125 2002/06/17 17:07:20 drh Exp $
*/
#include "sqlite.h"
#include "hash.h"
#include "vdbe.h"
#include "parse.h"
#include "btree.h"
#include <stdio.h>
................................................................................
                        int,int,int);
void sqliteSelectDelete(Select*);
void sqliteSelectUnbind(Select*);
Table *sqliteTableNameToTable(Parse*, const char*);
SrcList *sqliteTableTokenToSrcList(Parse*, Token*);
void sqliteDeleteFrom(Parse*, Token*, Expr*);
void sqliteUpdate(Parse*, Token*, ExprList*, Expr*, int);
WhereInfo *sqliteWhereBegin(Parse*, int, SrcList*, Expr*, int);
void sqliteWhereEnd(WhereInfo*);
void sqliteExprCode(Parse*, Expr*);
void sqliteExprIfTrue(Parse*, Expr*, int, int);
void sqliteExprIfFalse(Parse*, Expr*, int, int);
Table *sqliteFindTable(sqlite*,const char*);
Index *sqliteFindIndex(sqlite*,const char*);
void sqliteUnlinkAndDeleteIndex(sqlite*,Index*);







|







 







|







7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
...
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
**    May you do good and not evil.
**    May you find forgiveness for yourself and forgive others.
**    May you share freely, never taking more than you give.
**
*************************************************************************
** Internal interface definitions for SQLite.
**
** @(#) $Id: sqliteInt.h,v 1.126 2002/06/19 14:27:05 drh Exp $
*/
#include "sqlite.h"
#include "hash.h"
#include "vdbe.h"
#include "parse.h"
#include "btree.h"
#include <stdio.h>
................................................................................
                        int,int,int);
void sqliteSelectDelete(Select*);
void sqliteSelectUnbind(Select*);
Table *sqliteTableNameToTable(Parse*, const char*);
SrcList *sqliteTableTokenToSrcList(Parse*, Token*);
void sqliteDeleteFrom(Parse*, Token*, Expr*);
void sqliteUpdate(Parse*, Token*, ExprList*, Expr*, int);
WhereInfo *sqliteWhereBegin(Parse*, int, SrcList*, Expr*, int, ExprList**);
void sqliteWhereEnd(WhereInfo*);
void sqliteExprCode(Parse*, Expr*);
void sqliteExprIfTrue(Parse*, Expr*, int, int);
void sqliteExprIfFalse(Parse*, Expr*, int, int);
Table *sqliteFindTable(sqlite*,const char*);
Index *sqliteFindIndex(sqlite*,const char*);
void sqliteUnlinkAndDeleteIndex(sqlite*,Index*);

Changes to src/update.c.

8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
...
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
**    May you find forgiveness for yourself and forgive others.
**    May you share freely, never taking more than you give.
**
*************************************************************************
** This file contains C code routines that are called by the parser
** to handle UPDATE statements.
**
** $Id: update.c,v 1.44 2002/06/11 02:25:42 danielk1977 Exp $
*/
#include "sqliteInt.h"

/*
** Process an UPDATE statement.
*/
void sqliteUpdate(
................................................................................
  */
  v = sqliteGetVdbe(pParse);
  if( v==0 ) goto update_cleanup;
  sqliteBeginWriteOperation(pParse, 1);

  /* Begin the database scan
  */
  pWInfo = sqliteWhereBegin(pParse, base, pTabList, pWhere, 1);
  if( pWInfo==0 ) goto update_cleanup;

  /* Remember the index of every item to be updated.
  */
  sqliteVdbeAddOp(v, OP_ListWrite, 0, 0);

  /* End the database scan loop.







|







 







|







8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
...
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
**    May you find forgiveness for yourself and forgive others.
**    May you share freely, never taking more than you give.
**
*************************************************************************
** This file contains C code routines that are called by the parser
** to handle UPDATE statements.
**
** $Id: update.c,v 1.45 2002/06/19 14:27:06 drh Exp $
*/
#include "sqliteInt.h"

/*
** Process an UPDATE statement.
*/
void sqliteUpdate(
................................................................................
  */
  v = sqliteGetVdbe(pParse);
  if( v==0 ) goto update_cleanup;
  sqliteBeginWriteOperation(pParse, 1);

  /* Begin the database scan
  */
  pWInfo = sqliteWhereBegin(pParse, base, pTabList, pWhere, 1, 0);
  if( pWInfo==0 ) goto update_cleanup;

  /* Remember the index of every item to be updated.
  */
  sqliteVdbeAddOp(v, OP_ListWrite, 0, 0);

  /* End the database scan loop.

Changes to src/where.c.

9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
..
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80


81
82
83
84
85
86
87
...
145
146
147
148
149
150
151

























































152
153
154
155
156
157
158
159
...
200
201
202
203
204
205
206
207



208
209
210














211
212
213
214
215
216
217

218
219
220
221
222
223
224
...
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
...
491
492
493
494
495
496
497




































498
499
500
501
502
503
504
...
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
...
726
727
728
729
730
731
732




733
734
735
736
737
738
739
**    May you share freely, never taking more than you give.
**
*************************************************************************
** This module contains C code that generates VDBE code used to process
** the WHERE clause of SQL statements.  Also found here are subroutines
** to generate VDBE code to evaluate expressions.
**
** $Id: where.c,v 1.52 2002/06/14 22:38:43 drh Exp $
*/
#include "sqliteInt.h"

/*
** The query generator uses an array of instances of this structure to
** help it analyze the subexpressions of the WHERE clause.  Each WHERE
** clause subexpression is separated from the others by an AND operator.
*/
typedef struct ExprInfo ExprInfo;
struct ExprInfo {
  Expr *p;                /* Pointer to the subexpression */
  int indexable;          /* True if this subexprssion is usable by an index */
  int idxLeft;            /* p->pLeft is a column in this table number. -1 if
                          ** p->pLeft is not the column of any table */
  int idxRight;           /* p->pRight is a column in this table number. -1 if
                          ** p->pRight is not the column of any table */
  unsigned prereqLeft;    /* Tables referenced by p->pLeft */
  unsigned prereqRight;   /* Tables referenced by p->pRight */
  unsigned prereqAll;     /* Tables referenced by this expression in any way */
};

/*
** Determine the number of elements in an array.
*/
#define ARRAYSIZE(X)  (sizeof(X)/sizeof(X[0]))

................................................................................
  }
  return cnt;
}

/*
** This routine walks (recursively) an expression tree and generates
** a bitmask indicating which tables are used in that expression
** tree.  Bit 0 of the mask is set if table 0 is used.  But 1 is set
** if table 1 is used.  And so forth.
**
** In order for this routine to work, the calling function must have
** previously invoked sqliteExprResolveIds() on the expression.  See
** the header comment on that routine for additional information.
**
** "base" is the cursor number (the value of the iTable field) that
** corresponds to the first entry in the table list. 


*/
static int exprTableUsage(int base, Expr *p){
  unsigned int mask = 0;
  if( p==0 ) return 0;
  if( p->op==TK_COLUMN ){
    return 1<< (p->iTable - base);
  }
................................................................................
      pInfo->idxLeft = pExpr->pLeft->iTable - base;
      pInfo->indexable = 1;
    }
  }
}

/*

























































** Generating the beginning of the loop used for WHERE clause processing.
** The return value is a pointer to an (opaque) structure that contains
** information needed to terminate the loop.  Later, the calling routine
** should invoke sqliteWhereEnd() with the return value of this function
** in order to complete the WHERE clause processing.
**
** If an error occurs, this routine returns NULL.
**
................................................................................
**    foreach row1 in t1 do
**      flag = 0
**      foreach row2 in t2 do
**        start:
**          ...
**          flag = 1
**      end
**      if flag==0 goto start



**    end
**
** In words, if the right














*/
WhereInfo *sqliteWhereBegin(
  Parse *pParse,       /* The parser context */
  int base,            /* VDBE cursor index for left-most table in pTabList */
  SrcList *pTabList,   /* A list of all tables to be scanned */
  Expr *pWhere,        /* The WHERE clause */
  int pushKey          /* If TRUE, leave the table key on the stack */

){
  int i;                     /* Loop counter */
  WhereInfo *pWInfo;         /* Will become the return value of this function */
  Vdbe *v = pParse->pVdbe;   /* The virtual database engine */
  int brk, cont;             /* Addresses used during code generation */
  int *aOrder;         /* Order in which pTabList entries are searched */
  int nExpr;           /* Number of subexpressions in the WHERE clause */
................................................................................
  ExprInfo aExpr[50];  /* The WHERE clause is divided into these expressions */

  /* pushKey is only allowed if there is a single table (as in an INSERT or
  ** UPDATE statement)
  */
  assert( pushKey==0 || pTabList->nSrc==1 );
  
  /* Allocate space for aOrder[] and aiMem[]. */
  aOrder = sqliteMalloc( sizeof(int) * pTabList->nSrc );

  /* Allocate and initialize the WhereInfo structure that will become the
  ** return value.
  */
  pWInfo = sqliteMalloc( sizeof(WhereInfo) + pTabList->nSrc*sizeof(WhereLevel));
  if( sqlite_malloc_failed ){
................................................................................
    pWInfo->a[i].score = bestScore;
    loopMask |= 1<<idx;
    if( pBestIdx ){
      pWInfo->a[i].iCur = pParse->nTab++;
      pWInfo->peakNTab = pParse->nTab;
    }
  }





































  /* Open all tables in the pTabList and all indices used by those tables.
  */
  for(i=0; i<pTabList->nSrc; i++){
    int openOp;
    Table *pTab;

................................................................................
      }
      aExpr[k].p = 0;
      cont = pLevel->cont = sqliteVdbeMakeLabel(v);
      sqliteVdbeAddOp(v, OP_MustBeInt, 0, brk);
      haveKey = 0;
      sqliteVdbeAddOp(v, OP_NotExists, base+idx, brk);
      pLevel->op = OP_Noop;
    }else if( pIdx!=0 && pLevel->score%4==0 ){
      /* Case 2:  There is an index and all terms of the WHERE clause that
      **          refer to the index use the "==" or "IN" operators.
      */
      int start;
      int testOp;
      int nColumn = pLevel->score/4;
      brk = pLevel->brk = sqliteVdbeMakeLabel(v);
................................................................................
    }else{
      /* Case 5: The WHERE clause term that refers to the right-most
      **         column of the index is an inequality.  For example, if
      **         the index is on (x,y,z) and the WHERE clause is of the
      **         form "x=5 AND y<10" then this case is used.  Only the
      **         right-most column can be an inequality - the rest must
      **         use the "==" operator.




      */
      int score = pLevel->score;
      int nEqColumn = score/4;
      int start;
      int leFlag, geFlag;
      int testOp;








|











|
|

|

|
|
|







 







|
|






|
>
>







 







>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
|







 







|
>
>
>


<
>
>
>
>
>
>
>
>
>
>
>
>
>
>






|
>







 







|







 







>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>







 







|







 







>
>
>
>







9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
..
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
...
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
...
259
260
261
262
263
264
265
266
267
268
269
270
271

272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
...
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
...
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
...
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
...
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
**    May you share freely, never taking more than you give.
**
*************************************************************************
** This module contains C code that generates VDBE code used to process
** the WHERE clause of SQL statements.  Also found here are subroutines
** to generate VDBE code to evaluate expressions.
**
** $Id: where.c,v 1.53 2002/06/19 14:27:06 drh Exp $
*/
#include "sqliteInt.h"

/*
** The query generator uses an array of instances of this structure to
** help it analyze the subexpressions of the WHERE clause.  Each WHERE
** clause subexpression is separated from the others by an AND operator.
*/
typedef struct ExprInfo ExprInfo;
struct ExprInfo {
  Expr *p;                /* Pointer to the subexpression */
  u8 indexable;           /* True if this subexprssion is usable by an index */
  short int idxLeft;      /* p->pLeft is a column in this table number. -1 if
                          ** p->pLeft is not the column of any table */
  short int idxRight;     /* p->pRight is a column in this table number. -1 if
                          ** p->pRight is not the column of any table */
  unsigned prereqLeft;    /* Bitmask of tables referenced by p->pLeft */
  unsigned prereqRight;   /* Bitmask of tables referenced by p->pRight */
  unsigned prereqAll;     /* Bitmask of tables referenced by p */
};

/*
** Determine the number of elements in an array.
*/
#define ARRAYSIZE(X)  (sizeof(X)/sizeof(X[0]))

................................................................................
  }
  return cnt;
}

/*
** This routine walks (recursively) an expression tree and generates
** a bitmask indicating which tables are used in that expression
** tree.  Bit 0 of the mask is set if table base+0 is used.  Bit 1
** is set if table base+1 is used.  And so forth.
**
** In order for this routine to work, the calling function must have
** previously invoked sqliteExprResolveIds() on the expression.  See
** the header comment on that routine for additional information.
**
** "base" is the cursor number (the value of the iTable field) that
** corresponds to the first entry in the list of tables that appear
** in the FROM clause of a SELECT.  For UPDATE and DELETE statements
** there is just a single table with "base" as the cursor number.
*/
static int exprTableUsage(int base, Expr *p){
  unsigned int mask = 0;
  if( p==0 ) return 0;
  if( p->op==TK_COLUMN ){
    return 1<< (p->iTable - base);
  }
................................................................................
      pInfo->idxLeft = pExpr->pLeft->iTable - base;
      pInfo->indexable = 1;
    }
  }
}

/*
** pOrderBy is an ORDER BY clause from a SELECT statement.  pTab is the
** left-most table in the FROM clause of that same SELECT statement and
** the table has a cursor number of "base".
**
** This routine attempts to find an index for pTab that generates the
** correct record sequence for the given ORDER BY clause.  The return value
** is a pointer to an index that does the job.  NULL is returned if the
** table has no index that will generate the correct sort order.
**
** If there are two or more indices that generate the correct sort order
** and pPreferredIdx is one of those indices, then return pPreferredIdx.
*/
static Index *findSortingIndex(
  Table *pTab,            /* The table to be sorted */
  int base,               /* Cursor number for pTab */
  ExprList *pOrderBy,     /* The ORDER BY clause */
  Index *pPreferredIdx    /* Use this index, if possible and not NULL */
){
  int i;
  Index *pMatch;
  Index *pIdx;

  assert( pOrderBy!=0 );
  assert( pOrderBy->nExpr>0 );
  for(i=0; i<pOrderBy->nExpr; i++){
    Expr *p;
    if( (pOrderBy->a[i].sortOrder & SQLITE_SO_DIRMASK)!=SQLITE_SO_ASC ){
      /* Indices can only be used for ascending sort order */
      return 0;
    }
    p = pOrderBy->a[i].pExpr;
    if( p->op!=TK_COLUMN || p->iTable!=base ){
      /* Can not use an index sort on anything that is not a column in the
      ** left-most table of the FROM clause */
      return 0;
    }
  }

  /* If we get this far, it means the ORDER BY clause consists only of
  ** ascending columns in the left-most table of the FROM clause.  Now
  ** check for a matching index.
  */
  pMatch = 0;
  for(pIdx=pTab->pIndex; pIdx; pIdx=pIdx->pNext){
    if( pIdx->nColumn<pOrderBy->nExpr ) continue;
    for(i=0; i<pOrderBy->nExpr; i++){
      if( pOrderBy->a[i].pExpr->iColumn!=pIdx->aiColumn[i] ) break;
    }
    if( i>=pOrderBy->nExpr ){
      pMatch = pIdx;
      if( pIdx==pPreferredIdx ) break;
    }
  }
  return pMatch;
}

/*
** Generate the beginning of the loop used for WHERE clause processing.
** The return value is a pointer to an (opaque) structure that contains
** information needed to terminate the loop.  Later, the calling routine
** should invoke sqliteWhereEnd() with the return value of this function
** in order to complete the WHERE clause processing.
**
** If an error occurs, this routine returns NULL.
**
................................................................................
**    foreach row1 in t1 do
**      flag = 0
**      foreach row2 in t2 do
**        start:
**          ...
**          flag = 1
**      end
**      if flag==0 then
**        move the row2 cursor to a null row
**        goto start
**      fi
**    end
**

** ORDER BY CLAUSE PROCESSING
**
** *ppOrderBy is a pointer to the ORDER BY clause of a SELECT statement,
** if there is one.  If there is no ORDER BY clause or if this routine
** is called from an UPDATE or DELETE statement, then ppOrderBy is NULL.
**
** If an index can be used so that the natural output order of the table
** scan is correct for the ORDER BY clause, then that index is used and
** *ppOrderBy is set to NULL.  This is an optimization that prevents an
** unnecessary sort of the result set if an index appropriate for the
** ORDER BY clause already exists.
**
** If the where clause loops cannot be arranged to provide the correct
** output order, then the *ppOrderBy is unchanged.
*/
WhereInfo *sqliteWhereBegin(
  Parse *pParse,       /* The parser context */
  int base,            /* VDBE cursor index for left-most table in pTabList */
  SrcList *pTabList,   /* A list of all tables to be scanned */
  Expr *pWhere,        /* The WHERE clause */
  int pushKey,         /* If TRUE, leave the table key on the stack */
  ExprList **ppOrderBy /* An ORDER BY clause, or NULL */
){
  int i;                     /* Loop counter */
  WhereInfo *pWInfo;         /* Will become the return value of this function */
  Vdbe *v = pParse->pVdbe;   /* The virtual database engine */
  int brk, cont;             /* Addresses used during code generation */
  int *aOrder;         /* Order in which pTabList entries are searched */
  int nExpr;           /* Number of subexpressions in the WHERE clause */
................................................................................
  ExprInfo aExpr[50];  /* The WHERE clause is divided into these expressions */

  /* pushKey is only allowed if there is a single table (as in an INSERT or
  ** UPDATE statement)
  */
  assert( pushKey==0 || pTabList->nSrc==1 );
  
  /* Allocate space for aOrder[] */
  aOrder = sqliteMalloc( sizeof(int) * pTabList->nSrc );

  /* Allocate and initialize the WhereInfo structure that will become the
  ** return value.
  */
  pWInfo = sqliteMalloc( sizeof(WhereInfo) + pTabList->nSrc*sizeof(WhereLevel));
  if( sqlite_malloc_failed ){
................................................................................
    pWInfo->a[i].score = bestScore;
    loopMask |= 1<<idx;
    if( pBestIdx ){
      pWInfo->a[i].iCur = pParse->nTab++;
      pWInfo->peakNTab = pParse->nTab;
    }
  }

  /* Check to see if the ORDER BY clause is or can be satisfied by the
  ** use of an index on the first table.
  */
  if( ppOrderBy && *ppOrderBy && pTabList->nSrc>0 ){
     Index *pSortIdx;
     Index *pIdx;
     Table *pTab;

     pTab = pTabList->a[0].pTab;
     pIdx = pWInfo->a[0].pIdx;
     if( pIdx && pWInfo->a[0].score==4 ){
       /* If there is already an index on the left-most column and it is
       ** an equality index, then either sorting is not helpful, or the
       ** index is an IN operator, in which case the index does not give
       ** the correct sort order.  Either way, pretend that no suitable
       ** index is found.
       */
       pSortIdx = 0;
     }else if( iDirectEq[0]>=0 || iDirectLt[0]>=0 || iDirectGt[0]>=0 ){
       /* If the left-most column is accessed using its ROWID, then do
       ** not try to sort by index.
       */
       pSortIdx = 0;
     }else{
       pSortIdx = findSortingIndex(pTab, base, *ppOrderBy, pIdx);
     }
     if( pSortIdx && (pIdx==0 || pIdx==pSortIdx) ){
       if( pIdx==0 ){
         pWInfo->a[0].pIdx = pSortIdx;
         pWInfo->a[0].iCur = pParse->nTab++;
         pWInfo->peakNTab = pParse->nTab;
       }
       *ppOrderBy = 0;
     }
  }

  /* Open all tables in the pTabList and all indices used by those tables.
  */
  for(i=0; i<pTabList->nSrc; i++){
    int openOp;
    Table *pTab;

................................................................................
      }
      aExpr[k].p = 0;
      cont = pLevel->cont = sqliteVdbeMakeLabel(v);
      sqliteVdbeAddOp(v, OP_MustBeInt, 0, brk);
      haveKey = 0;
      sqliteVdbeAddOp(v, OP_NotExists, base+idx, brk);
      pLevel->op = OP_Noop;
    }else if( pIdx!=0 && pLevel->score>0 && pLevel->score%4==0 ){
      /* Case 2:  There is an index and all terms of the WHERE clause that
      **          refer to the index use the "==" or "IN" operators.
      */
      int start;
      int testOp;
      int nColumn = pLevel->score/4;
      brk = pLevel->brk = sqliteVdbeMakeLabel(v);
................................................................................
    }else{
      /* Case 5: The WHERE clause term that refers to the right-most
      **         column of the index is an inequality.  For example, if
      **         the index is on (x,y,z) and the WHERE clause is of the
      **         form "x=5 AND y<10" then this case is used.  Only the
      **         right-most column can be an inequality - the rest must
      **         use the "==" operator.
      **
      **         This case is also used when there are no WHERE clause
      **         constraints but an index is selected anyway, in order
      **         to force the output order to conform to an ORDER BY.
      */
      int score = pLevel->score;
      int nEqColumn = score/4;
      int start;
      int leFlag, geFlag;
      int testOp;

Changes to test/where.test.

7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
...
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
...
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
...
338
339
340
341
342
343
344




345






346


























































































347
#    May you find forgiveness for yourself and forgive others.
#    May you share freely, never taking more than you give.
#
#***********************************************************************
# This file implements regression tests for SQLite library.  The
# focus of this file is testing the use of indices in WHERE clases.
#
# $Id: where.test,v 1.8 2002/06/14 22:38:43 drh Exp $

set testdir [file dirname $argv0]
source $testdir/tester.tcl

# Build some test data
#
do_test where-1.0 {
................................................................................
  count {SELECT w FROM t1 WHERE w<3}
} {1 2 4}
do_test where-1.36 {
  count {SELECT w FROM t1 WHERE w<=3}
} {1 2 3 6}
do_test where-1.37 {
  count {SELECT w FROM t1 WHERE w+1<=4 ORDER BY w}
} {1 2 3 99}


# Do the same kind of thing except use a join as the data source.
#
do_test where-2.1 {
  count {
    SELECT w, p FROM t2, t1
................................................................................
    SELECT * FROM t1 WHERE rowid IN (1,2,3,1234) order by 1;
  }
} {1 0 4 2 1 9 3 1 16 0}
do_test where-5.2 {
  count {
    SELECT * FROM t1 WHERE rowid+0 IN (1,2,3,1234) order by 1;
  }
} {1 0 4 2 1 9 3 1 16 99}
do_test where-5.3 {
  count {
    SELECT * FROM t1 WHERE w IN (-1,1,2,3) order by 1;
  }
} {1 0 4 2 1 9 3 1 16 10}
do_test where-5.4 {
  count {
    SELECT * FROM t1 WHERE w+0 IN (-1,1,2,3) order by 1;
  }
} {1 0 4 2 1 9 3 1 16 99}
do_test where-5.5 {
  count {
    SELECT * FROM t1 WHERE rowid IN 
       (select rowid from t1 where rowid IN (-1,2,4))
    ORDER BY 1;
  }
} {2 1 9 4 2 25 1}
do_test where-5.6 {
  count {
    SELECT * FROM t1 WHERE rowid+0 IN 
       (select rowid from t1 where rowid IN (-1,2,4))
    ORDER BY 1;
  }
} {2 1 9 4 2 25 99}
do_test where-5.7 {
  count {
    SELECT * FROM t1 WHERE w IN 
       (select rowid from t1 where rowid IN (-1,2,4))
    ORDER BY 1;
  }
} {2 1 9 4 2 25 7}
do_test where-5.8 {
  count {
    SELECT * FROM t1 WHERE w+0 IN 
       (select rowid from t1 where rowid IN (-1,2,4))
    ORDER BY 1;
  }
} {2 1 9 4 2 25 99}
do_test where-5.9 {
  count {
    SELECT * FROM t1 WHERE x IN (1,7) ORDER BY 1;
  }
} {2 1 9 3 1 16 6}
do_test where-5.10 {
  count {
    SELECT * FROM t1 WHERE x+0 IN (1,7) ORDER BY 1;
  }
} {2 1 9 3 1 16 99}
do_test where-5.11 {
  count {
    SELECT * FROM t1 WHERE y IN (6400,8100) ORDER BY 1;
  }
} {79 6 6400 89 6 8100 99}
do_test where-5.12 {
  count {
    SELECT * FROM t1 WHERE x=6 AND y IN (6400,8100) ORDER BY 1;
  }
} {79 6 6400 89 6 8100 74}
do_test where-5.13 {
  count {
................................................................................
} {2 1 9 3 1 16 6}
do_test where-5.14 {
  count {
    SELECT * FROM t1 WHERE x IN (1,7) AND y IN (9,10) ORDER BY 1;
  }
} {2 1 9 6}







































































































finish_test







|







 







|







 







|









|













|













|









|




|







 







>
>
>
>
|
>
>
>
>
>
>
|
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>

7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
...
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
...
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
...
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
#    May you find forgiveness for yourself and forgive others.
#    May you share freely, never taking more than you give.
#
#***********************************************************************
# This file implements regression tests for SQLite library.  The
# focus of this file is testing the use of indices in WHERE clases.
#
# $Id: where.test,v 1.9 2002/06/19 14:27:06 drh Exp $

set testdir [file dirname $argv0]
source $testdir/tester.tcl

# Build some test data
#
do_test where-1.0 {
................................................................................
  count {SELECT w FROM t1 WHERE w<3}
} {1 2 4}
do_test where-1.36 {
  count {SELECT w FROM t1 WHERE w<=3}
} {1 2 3 6}
do_test where-1.37 {
  count {SELECT w FROM t1 WHERE w+1<=4 ORDER BY w}
} {1 2 3 199}


# Do the same kind of thing except use a join as the data source.
#
do_test where-2.1 {
  count {
    SELECT w, p FROM t2, t1
................................................................................
    SELECT * FROM t1 WHERE rowid IN (1,2,3,1234) order by 1;
  }
} {1 0 4 2 1 9 3 1 16 0}
do_test where-5.2 {
  count {
    SELECT * FROM t1 WHERE rowid+0 IN (1,2,3,1234) order by 1;
  }
} {1 0 4 2 1 9 3 1 16 199}
do_test where-5.3 {
  count {
    SELECT * FROM t1 WHERE w IN (-1,1,2,3) order by 1;
  }
} {1 0 4 2 1 9 3 1 16 10}
do_test where-5.4 {
  count {
    SELECT * FROM t1 WHERE w+0 IN (-1,1,2,3) order by 1;
  }
} {1 0 4 2 1 9 3 1 16 199}
do_test where-5.5 {
  count {
    SELECT * FROM t1 WHERE rowid IN 
       (select rowid from t1 where rowid IN (-1,2,4))
    ORDER BY 1;
  }
} {2 1 9 4 2 25 1}
do_test where-5.6 {
  count {
    SELECT * FROM t1 WHERE rowid+0 IN 
       (select rowid from t1 where rowid IN (-1,2,4))
    ORDER BY 1;
  }
} {2 1 9 4 2 25 199}
do_test where-5.7 {
  count {
    SELECT * FROM t1 WHERE w IN 
       (select rowid from t1 where rowid IN (-1,2,4))
    ORDER BY 1;
  }
} {2 1 9 4 2 25 7}
do_test where-5.8 {
  count {
    SELECT * FROM t1 WHERE w+0 IN 
       (select rowid from t1 where rowid IN (-1,2,4))
    ORDER BY 1;
  }
} {2 1 9 4 2 25 199}
do_test where-5.9 {
  count {
    SELECT * FROM t1 WHERE x IN (1,7) ORDER BY 1;
  }
} {2 1 9 3 1 16 6}
do_test where-5.10 {
  count {
    SELECT * FROM t1 WHERE x+0 IN (1,7) ORDER BY 1;
  }
} {2 1 9 3 1 16 199}
do_test where-5.11 {
  count {
    SELECT * FROM t1 WHERE y IN (6400,8100) ORDER BY 1;
  }
} {79 6 6400 89 6 8100 199}
do_test where-5.12 {
  count {
    SELECT * FROM t1 WHERE x=6 AND y IN (6400,8100) ORDER BY 1;
  }
} {79 6 6400 89 6 8100 74}
do_test where-5.13 {
  count {
................................................................................
} {2 1 9 3 1 16 6}
do_test where-5.14 {
  count {
    SELECT * FROM t1 WHERE x IN (1,7) AND y IN (9,10) ORDER BY 1;
  }
} {2 1 9 6}

# This procedure executes the SQL.  Then it checks the generated program
# for the SQL and appends a "nosort" to the result if the program contains the
# SortCallback opcode.  If the program does not contain the SortCallback
# opcode it appends "sort"
#
proc cksort {sql} {
  set data [execsql $sql]
  set prog [execsql "EXPLAIN $sql"]
  if {[regexp SortCallback $prog]} {set x sort} {set x nosort}
  lappend data $x
  return $data
}
# Check out the logic that attempts to implement the ORDER BY clause
# using an index rather than by sorting.
#
do_test where-6.1 {
  execsql {
    CREATE TABLE t3(a,b,c);
    CREATE INDEX t3a ON t3(a);
    CREATE INDEX t3bc ON t3(b,c);
    CREATE INDEX t3acb ON t3(a,c,b);
    INSERT INTO t3 SELECT w, 101-w, y FROM t1;
    SELECT count(*), sum(a), sum(b), sum(c) FROM t3;
  }
} {100 5050 5050 348550}
do_test where-6.2 {
  cksort {
    SELECT * FROM t3 ORDER BY a LIMIT 3
  }
} {1 100 4 2 99 9 3 98 16 nosort}
do_test where-6.3 {
  cksort {
    SELECT * FROM t3 ORDER BY a+1 LIMIT 3
  }
} {1 100 4 2 99 9 3 98 16 sort}
do_test where-6.4 {
  cksort {
    SELECT * FROM t3 WHERE a<10 ORDER BY a LIMIT 3
  }
} {1 100 4 2 99 9 3 98 16 nosort}
do_test where-6.5 {
  cksort {
    SELECT * FROM t3 WHERE a>0 AND a<10 ORDER BY a LIMIT 3
  }
} {1 100 4 2 99 9 3 98 16 nosort}
do_test where-6.6 {
  cksort {
    SELECT * FROM t3 WHERE a>0 ORDER BY a LIMIT 3
  }
} {1 100 4 2 99 9 3 98 16 nosort}
do_test where-6.7 {
  cksort {
    SELECT * FROM t3 WHERE b>0 ORDER BY a LIMIT 3
  }
} {1 100 4 2 99 9 3 98 16 sort}
do_test where-6.8 {
  cksort {
    SELECT * FROM t3 WHERE a IN (3,5,7,1,9,4,2) ORDER BY a LIMIT 3
  }
} {1 100 4 2 99 9 3 98 16 sort}
do_test where-6.9 {
  cksort {
    SELECT * FROM t3 WHERE a=1 AND c>0 ORDER BY a LIMIT 3
  }
} {1 100 4 nosort}
do_test where-6.10 {
  cksort {
    SELECT * FROM t3 WHERE a=1 AND c>0 ORDER BY a LIMIT 3
  }
} {1 100 4 nosort}
do_test where-6.11 {
  cksort {
    SELECT * FROM t3 WHERE a=1 AND c>0 ORDER BY a,c LIMIT 3
  }
} {1 100 4 nosort}
do_test where-6.12 {
  cksort {
    SELECT * FROM t3 WHERE a=1 AND c>0 ORDER BY a,c,b LIMIT 3
  }
} {1 100 4 nosort}
do_test where-6.13 {
  cksort {
    SELECT * FROM t3 WHERE a>0 ORDER BY a DESC LIMIT 3
  }
} {100 1 10201 99 2 10000 98 3 9801 sort}
do_test where-6.14 {
  cksort {
    SELECT * FROM t3 ORDER BY b LIMIT 3
  }
} {100 1 10201 99 2 10000 98 3 9801 nosort}
do_test where-6.15 {
  cksort {
    SELECT t3.a, t1.x FROM t3, t1 WHERE t3.a=t1.w ORDER BY t3.a LIMIT 3
  }
} {1 0 2 1 3 1 nosort}
do_test where-6.16 {
  cksort {
    SELECT t3.a, t1.x FROM t3, t1 WHERE t3.a=t1.w ORDER BY t1.x, t3.a LIMIT 3
  }
} {1 0 2 1 3 1 sort}


finish_test

Changes to www/changes.tcl.

20
21
22
23
24
25
26






27
28
29
30
31
32
33
}


proc chng {date desc} {
  puts "<DT><B>$date</B></DT>"
  puts "<DD><P><UL>$desc</UL></P></DD>"
}







chng {2002 Jun 17 (2.5.0)} {
<li>Added support for row triggers.</li>
<li>Added SQL-92 compliant handling of NULLs.</li>
<li>Add support for the full SQL-92 join syntax and LEFT OUTER JOINs.</li>
<li>Double-quoted strings interpreted as column names not text literals.</li>
<li>Parse (but do not implement) foreign keys.</li>







>
>
>
>
>
>







20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
}


proc chng {date desc} {
  puts "<DT><B>$date</B></DT>"
  puts "<DD><P><UL>$desc</UL></P></DD>"
}

chng {2002 Jun 19 (2.5.1)} {
<li>The query optimizer now attempts to implement the ORDER BY clause
    using an index.  Sorting is still used if not suitable index is
    available.</li>
}

chng {2002 Jun 17 (2.5.0)} {
<li>Added support for row triggers.</li>
<li>Added SQL-92 compliant handling of NULLs.</li>
<li>Add support for the full SQL-92 join syntax and LEFT OUTER JOINs.</li>
<li>Double-quoted strings interpreted as column names not text literals.</li>
<li>Parse (but do not implement) foreign keys.</li>