SQLite

Check-in [86ce56ccea]
Login

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

Overview
Comment:A new optimizer that breaks a lot of tests. But none of them critically, I think. Nevertheless, there is a lot of work ahead to stabilize the code. (CVS 2564)
Downloads: Tarball | ZIP archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1: 86ce56ccea8297b1fba2b9ee53b5f1a3f228662f
User & Date: drh 2005-07-23 22:59:56.000
Context
2005-07-27
20:41
More work on the new optimizer. Fewer tests fail now. (CVS 2565) (check-in: ee3a08e353 user: drh tags: trunk)
2005-07-23
22:59
A new optimizer that breaks a lot of tests. But none of them critically, I think. Nevertheless, there is a lot of work ahead to stabilize the code. (CVS 2564) (check-in: 86ce56ccea user: drh tags: trunk)
14:52
Store the total number of rows as part of the ANALYZE statistics. (CVS 2563) (check-in: 868279c78e user: drh tags: trunk)
Changes
Unified Diff Ignore Whitespace Patch
Changes to src/analyze.c.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/*
** 2005 July 8
**
** The author disclaims copyright to this source code.  In place of
** a legal notice, here is a blessing:
**
**    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.
**
*************************************************************************
** This file contains code associated with the ANALYZE command.
**
** @(#) $Id: analyze.c,v 1.5 2005/07/23 14:52:12 drh Exp $
*/
#ifndef SQLITE_OMIT_ANALYZE
#include "sqliteInt.h"

/*
** This routine generates code that opens the sqlite_stat1 table on cursor
** iStatCur.













|







1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/*
** 2005 July 8
**
** The author disclaims copyright to this source code.  In place of
** a legal notice, here is a blessing:
**
**    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.
**
*************************************************************************
** This file contains code associated with the ANALYZE command.
**
** @(#) $Id: analyze.c,v 1.6 2005/07/23 22:59:56 drh Exp $
*/
#ifndef SQLITE_OMIT_ANALYZE
#include "sqliteInt.h"

/*
** This routine generates code that opens the sqlite_stat1 table on cursor
** iStatCur.
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
  analysisInfo sInfo;
  HashElem *i;
  char *zSql;

  /* Clear any prior statistics */
  for(i=sqliteHashFirst(&db->aDb[iDb].idxHash); i; i=sqliteHashNext(i)){
    Index *pIdx = sqliteHashData(i);
    int j;
    for(j=0; j<=pIdx->nColumn; j++){
      pIdx->aiRowEst[j] = j<100 ? 1000*(100-j) : 100;
    }
  }

  /* Check to make sure the sqlite_stat1 table existss */
  sInfo.db = db;
  sInfo.zDatabase = db->aDb[iDb].zName;
  if( sqlite3FindTable(db, "sqlite_stat1", sInfo.zDatabase)==0 ){
     return;







<
<
|
<







360
361
362
363
364
365
366


367

368
369
370
371
372
373
374
  analysisInfo sInfo;
  HashElem *i;
  char *zSql;

  /* Clear any prior statistics */
  for(i=sqliteHashFirst(&db->aDb[iDb].idxHash); i; i=sqliteHashNext(i)){
    Index *pIdx = sqliteHashData(i);


    sqlite3DefaultRowEst(pIdx);

  }

  /* Check to make sure the sqlite_stat1 table existss */
  sInfo.db = db;
  sInfo.zDatabase = db->aDb[iDb].zName;
  if( sqlite3FindTable(db, "sqlite_stat1", sInfo.zDatabase)==0 ){
     return;
Changes to src/build.c.
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
**     CREATE INDEX
**     DROP INDEX
**     creating ID lists
**     BEGIN TRANSACTION
**     COMMIT
**     ROLLBACK
**
** $Id: build.c,v 1.335 2005/07/23 14:52:12 drh Exp $
*/
#include "sqliteInt.h"
#include <ctype.h>

/*
** This routine is called when a new SQL statement is beginning to
** be parsed.  Initialize the pParse structure as needed.







|







18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
**     CREATE INDEX
**     DROP INDEX
**     creating ID lists
**     BEGIN TRANSACTION
**     COMMIT
**     ROLLBACK
**
** $Id: build.c,v 1.336 2005/07/23 22:59:56 drh Exp $
*/
#include "sqliteInt.h"
#include <ctype.h>

/*
** This routine is called when a new SQL statement is beginning to
** be parsed.  Initialize the pParse structure as needed.
2202
2203
2204
2205
2206
2207
2208
2209
2210
2211
2212
2213
2214
2215
2216
2217
2218
2219
2220
2221
2222
2223

2224
2225
2226
2227
2228
2229
2230
    }
    if( j>=pTab->nCol ){
      sqlite3ErrorMsg(pParse, "table %s has no column named %s",
        pTab->zName, pList->a[i].zName);
      goto exit_create_index;
    }
    pIndex->aiColumn[i] = j;
    pIndex->aiRowEst[i] = 100;
    if( pList->a[i].pExpr ){
      assert( pList->a[i].pExpr->pColl );
      pIndex->keyInfo.aColl[i] = pList->a[i].pExpr->pColl;
    }else{
      pIndex->keyInfo.aColl[i] = pTab->aCol[j].pColl;
    }
    assert( pIndex->keyInfo.aColl[i] );
    if( !db->init.busy && 
        sqlite3CheckCollSeq(pParse, pIndex->keyInfo.aColl[i]) 
    ){
      goto exit_create_index;
    }
  }
  pIndex->keyInfo.nField = pList->nExpr;


  if( pTab==pParse->pNewTable ){
    /* This routine has been called to create an automatic index as a
    ** result of a PRIMARY KEY or UNIQUE clause on a column definition, or
    ** a PRIMARY KEY or UNIQUE clause following the column definitions.
    ** i.e. one of:
    **







<














>







2202
2203
2204
2205
2206
2207
2208

2209
2210
2211
2212
2213
2214
2215
2216
2217
2218
2219
2220
2221
2222
2223
2224
2225
2226
2227
2228
2229
2230
    }
    if( j>=pTab->nCol ){
      sqlite3ErrorMsg(pParse, "table %s has no column named %s",
        pTab->zName, pList->a[i].zName);
      goto exit_create_index;
    }
    pIndex->aiColumn[i] = j;

    if( pList->a[i].pExpr ){
      assert( pList->a[i].pExpr->pColl );
      pIndex->keyInfo.aColl[i] = pList->a[i].pExpr->pColl;
    }else{
      pIndex->keyInfo.aColl[i] = pTab->aCol[j].pColl;
    }
    assert( pIndex->keyInfo.aColl[i] );
    if( !db->init.busy && 
        sqlite3CheckCollSeq(pParse, pIndex->keyInfo.aColl[i]) 
    ){
      goto exit_create_index;
    }
  }
  pIndex->keyInfo.nField = pList->nExpr;
  sqlite3DefaultRowEst(pIndex);

  if( pTab==pParse->pNewTable ){
    /* This routine has been called to create an automatic index as a
    ** result of a PRIMARY KEY or UNIQUE clause on a column definition, or
    ** a PRIMARY KEY or UNIQUE clause following the column definitions.
    ** i.e. one of:
    **
2382
2383
2384
2385
2386
2387
2388















2389
2390
2391
2392
2393
2394
2395
    freeIndex(pIndex);
  }
  sqlite3ExprListDelete(pList);
  sqlite3SrcListDelete(pTblName);
  sqliteFree(zName);
  return;
}
















/*
** This routine will drop an existing named index.  This routine
** implements the DROP INDEX statement.
*/
void sqlite3DropIndex(Parse *pParse, SrcList *pName){
  Index *pIndex;







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







2382
2383
2384
2385
2386
2387
2388
2389
2390
2391
2392
2393
2394
2395
2396
2397
2398
2399
2400
2401
2402
2403
2404
2405
2406
2407
2408
2409
2410
    freeIndex(pIndex);
  }
  sqlite3ExprListDelete(pList);
  sqlite3SrcListDelete(pTblName);
  sqliteFree(zName);
  return;
}

/*
** Fill the Index.aiRowEst[] array with default information - information
** to be used when we have no ANALYZE command to run.
*/
void sqlite3DefaultRowEst(Index *pIdx){
  int i;
  int n = pIdx->nColumn;
  int j = 1000000;
  int f = (1000000-1-100*(pIdx->onError==OE_None))/n;
  for(i=0; i<=n; i++, j-=f){
    assert( j>0 );
    pIdx->aiRowEst[i] = j;
  }
}

/*
** This routine will drop an existing named index.  This routine
** implements the DROP INDEX statement.
*/
void sqlite3DropIndex(Parse *pParse, SrcList *pName){
  Index *pIndex;
Changes to src/sqliteInt.h.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/*
** 2001 September 15
**
** The author disclaims copyright to this source code.  In place of
** a legal notice, here is a blessing:
**
**    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.399 2005/07/23 03:18:40 drh Exp $
*/
#ifndef _SQLITEINT_H_
#define _SQLITEINT_H_

/*
** These #defines should enable >2GB file support on Posix if the
** underlying operating system supports it.  If the OS lacks













|







1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/*
** 2001 September 15
**
** The author disclaims copyright to this source code.  In place of
** a legal notice, here is a blessing:
**
**    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.400 2005/07/23 22:59:56 drh Exp $
*/
#ifndef _SQLITEINT_H_
#define _SQLITEINT_H_

/*
** These #defines should enable >2GB file support on Posix if the
** underlying operating system supports it.  If the OS lacks
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963

964
965
966
967
968
969
970
** structure contains a single instance of this structure.  This structure
** is intended to be private the the where.c module and should not be
** access or modified by other modules.
*/
struct WhereLevel {
  int iFrom;            /* Which entry in the FROM clause */
  int flags;            /* Flags associated with this level */
  int iMem;             /* Memory cell used by this level */
  int iLeftJoin;        /* Memory cell used to implement LEFT OUTER JOIN */
  Index *pIdx;          /* Index used.  NULL if no index */
  int iTabCur;          /* The VDBE cursor used to access the table */
  int iIdxCur;          /* The VDBE cursor used to acesss pIdx */
  int brk;              /* Jump here to break out of the loop */
  int cont;             /* Jump here to continue with the next loop cycle */
  int top;              /* First instruction of interior of the loop */
  int op, p1, p2;       /* Opcode used to terminate the loop */

  int nIn;              /* Number of IN operators constraining this loop */
  int *aInLoop;         /* Loop terminators for IN operators */
};

/*
** The WHERE clause processing routine has two halves.  The
** first part does the start of the WHERE loop and the second







|








>







948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
** structure contains a single instance of this structure.  This structure
** is intended to be private the the where.c module and should not be
** access or modified by other modules.
*/
struct WhereLevel {
  int iFrom;            /* Which entry in the FROM clause */
  int flags;            /* Flags associated with this level */
  int iMem;             /* First memory cell used by this level */
  int iLeftJoin;        /* Memory cell used to implement LEFT OUTER JOIN */
  Index *pIdx;          /* Index used.  NULL if no index */
  int iTabCur;          /* The VDBE cursor used to access the table */
  int iIdxCur;          /* The VDBE cursor used to acesss pIdx */
  int brk;              /* Jump here to break out of the loop */
  int cont;             /* Jump here to continue with the next loop cycle */
  int top;              /* First instruction of interior of the loop */
  int op, p1, p2;       /* Opcode used to terminate the loop */
  int nEq;              /* Number of == or IN constraints on this loop */
  int nIn;              /* Number of IN operators constraining this loop */
  int *aInLoop;         /* Loop terminators for IN operators */
};

/*
** The WHERE clause processing routine has two halves.  The
** first part does the start of the WHERE loop and the second
1568
1569
1570
1571
1572
1573
1574

1575
1576
1577
1578
1579
1580
const char *sqlite3TestErrorName(int);
CollSeq *sqlite3GetCollSeq(sqlite3*, CollSeq *, const char *, int);
char sqlite3AffinityType(const Token*);
void sqlite3Analyze(Parse*, Token*, Token*);
int sqlite3InvokeBusyHandler(BusyHandler*);
int sqlite3FindDb(sqlite3*, Token*);
void sqlite3AnalysisLoad(sqlite3*,int iDB);


#ifdef SQLITE_SSE
#include "sseInt.h"
#endif

#endif







>






1569
1570
1571
1572
1573
1574
1575
1576
1577
1578
1579
1580
1581
1582
const char *sqlite3TestErrorName(int);
CollSeq *sqlite3GetCollSeq(sqlite3*, CollSeq *, const char *, int);
char sqlite3AffinityType(const Token*);
void sqlite3Analyze(Parse*, Token*, Token*);
int sqlite3InvokeBusyHandler(BusyHandler*);
int sqlite3FindDb(sqlite3*, Token*);
void sqlite3AnalysisLoad(sqlite3*,int iDB);
void sqlite3DefaultRowEst(Index*);

#ifdef SQLITE_SSE
#include "sseInt.h"
#endif

#endif
Changes to src/test1.c.
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
**    May you share freely, never taking more than you give.
**
*************************************************************************
** Code for testing the printf() interface to SQLite.  This code
** is not included in the SQLite library.  It is used for automated
** testing of the SQLite library.
**
** $Id: test1.c,v 1.150 2005/07/20 14:31:53 drh Exp $
*/
#include "sqliteInt.h"
#include "tcl.h"
#include "os.h"
#include <stdlib.h>
#include <string.h>








|







9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
**    May you share freely, never taking more than you give.
**
*************************************************************************
** Code for testing the printf() interface to SQLite.  This code
** is not included in the SQLite library.  It is used for automated
** testing of the SQLite library.
**
** $Id: test1.c,v 1.151 2005/07/23 22:59:56 drh Exp $
*/
#include "sqliteInt.h"
#include "tcl.h"
#include "os.h"
#include <stdlib.h>
#include <string.h>

3087
3088
3089
3090
3091
3092
3093

3094
3095
3096
3097
3098
3099
3100
     { "sqlite3_crashparams",     sqlite3_crashparams, 0     },
     { "sqlite3_test_errstr",     test_errstr, 0             },
     { "tcl_variable_type",       tcl_variable_type, 0       },
  };
  static int bitmask_size = sizeof(Bitmask)*8;
  int i;
  extern int sqlite3_os_trace;

  extern int sqlite3_sync_count, sqlite3_fullsync_count;
  extern int sqlite3_opentemp_count;
  extern int sqlite3_memUsed;
  extern int sqlite3_memMax;
  extern char sqlite3_query_plan[];
  static char *query_plan = sqlite3_query_plan;








>







3087
3088
3089
3090
3091
3092
3093
3094
3095
3096
3097
3098
3099
3100
3101
     { "sqlite3_crashparams",     sqlite3_crashparams, 0     },
     { "sqlite3_test_errstr",     test_errstr, 0             },
     { "tcl_variable_type",       tcl_variable_type, 0       },
  };
  static int bitmask_size = sizeof(Bitmask)*8;
  int i;
  extern int sqlite3_os_trace;
  extern int sqlite3_where_trace;
  extern int sqlite3_sync_count, sqlite3_fullsync_count;
  extern int sqlite3_opentemp_count;
  extern int sqlite3_memUsed;
  extern int sqlite3_memMax;
  extern char sqlite3_query_plan[];
  static char *query_plan = sqlite3_query_plan;

3113
3114
3115
3116
3117
3118
3119


3120
3121
3122
3123
3124
3125
3126
      (char*)&sqlite3_interrupt_count, TCL_LINK_INT);
  Tcl_LinkVar(interp, "sqlite_open_file_count", 
      (char*)&sqlite3_open_file_count, TCL_LINK_INT);
  Tcl_LinkVar(interp, "sqlite_current_time", 
      (char*)&sqlite3_current_time, TCL_LINK_INT);
  Tcl_LinkVar(interp, "sqlite_os_trace",
      (char*)&sqlite3_os_trace, TCL_LINK_INT);


  Tcl_LinkVar(interp, "sqlite_memused",
      (char*)&sqlite3_memUsed, TCL_LINK_INT | TCL_LINK_READ_ONLY);
  Tcl_LinkVar(interp, "sqlite_memmax",
      (char*)&sqlite3_memMax, TCL_LINK_INT | TCL_LINK_READ_ONLY);
  Tcl_LinkVar(interp, "sqlite_query_plan",
      (char*)&query_plan, TCL_LINK_STRING|TCL_LINK_READ_ONLY);
#ifndef SQLITE_OMIT_DISKIO







>
>







3114
3115
3116
3117
3118
3119
3120
3121
3122
3123
3124
3125
3126
3127
3128
3129
      (char*)&sqlite3_interrupt_count, TCL_LINK_INT);
  Tcl_LinkVar(interp, "sqlite_open_file_count", 
      (char*)&sqlite3_open_file_count, TCL_LINK_INT);
  Tcl_LinkVar(interp, "sqlite_current_time", 
      (char*)&sqlite3_current_time, TCL_LINK_INT);
  Tcl_LinkVar(interp, "sqlite_os_trace",
      (char*)&sqlite3_os_trace, TCL_LINK_INT);
  Tcl_LinkVar(interp, "sqlite_where_trace",
      (char*)&sqlite3_where_trace, TCL_LINK_INT);
  Tcl_LinkVar(interp, "sqlite_memused",
      (char*)&sqlite3_memUsed, TCL_LINK_INT | TCL_LINK_READ_ONLY);
  Tcl_LinkVar(interp, "sqlite_memmax",
      (char*)&sqlite3_memMax, TCL_LINK_INT | TCL_LINK_READ_ONLY);
  Tcl_LinkVar(interp, "sqlite_query_plan",
      (char*)&query_plan, TCL_LINK_STRING|TCL_LINK_READ_ONLY);
#ifndef SQLITE_OMIT_DISKIO
Changes to src/where.c.
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
43
44
45
46
47
48
49
50
51
52
53



54
55
56
57
58
59
60
** This module contains C code that generates VDBE code used to process
** the WHERE clause of SQL statements.  This module is reponsible for
** generating the code that loops through a table looking for applicable
** rows.  Indices are selected and used to speed the search when doing
** so is applicable.  Because this module is responsible for selecting
** indices, you might also think of this module as the "query optimizer".
**
** $Id: where.c,v 1.151 2005/07/22 00:31:40 drh Exp $
*/
#include "sqliteInt.h"

/*
** The number of bits in a Bitmask.  "BMS" means "BitMask Size".
*/
#define BMS  (sizeof(Bitmask)*8)

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











/* Forward reference
*/
typedef struct WhereClause WhereClause;

/*
** 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.
**
** All WhereTerms are collected into a single WhereClause structure.  
** The following identity holds:
**
**        WhereTerm.pWC->a[WhereTerm.idx] == WhereTerm
**
** When a term is of the form:
**
**              X <op> <expr>
**
** where X is a column name and <op> is one of certain operators,
** then WhereTerm.leftCursor and WhereTerm.leftColumn record the
** cursor number and column number for X.  



**
** prereqRight and prereqAll record sets of cursor numbers,
** but they do so indirectly.  A single ExprMaskSet structure translates
** cursor number into bits and the translated bit is stored in the prereq
** fields.  The translation is used in order to maximize the number of
** bits that will fit in a Bitmask.  The VDBE cursor numbers might be
** spread out over the non-negative integers.  For example, the cursor







|













>
>
>
>
>
>
>
>
>
>




















|
>
>
>







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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
** This module contains C code that generates VDBE code used to process
** the WHERE clause of SQL statements.  This module is reponsible for
** generating the code that loops through a table looking for applicable
** rows.  Indices are selected and used to speed the search when doing
** so is applicable.  Because this module is responsible for selecting
** indices, you might also think of this module as the "query optimizer".
**
** $Id: where.c,v 1.152 2005/07/23 22:59:56 drh Exp $
*/
#include "sqliteInt.h"

/*
** The number of bits in a Bitmask.  "BMS" means "BitMask Size".
*/
#define BMS  (sizeof(Bitmask)*8)

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

/*
** Trace output macros
*/
#if defined(SQLITE_TEST) || defined(SQLITE_DEBUG)
int sqlite3_where_trace = 0;
# define TRACE(X)  if(sqlite3_where_trace) sqlite3DebugPrintf X
#else
# define TRACE(X)
#endif

/* Forward reference
*/
typedef struct WhereClause WhereClause;

/*
** 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.
**
** All WhereTerms are collected into a single WhereClause structure.  
** The following identity holds:
**
**        WhereTerm.pWC->a[WhereTerm.idx] == WhereTerm
**
** When a term is of the form:
**
**              X <op> <expr>
**
** where X is a column name and <op> is one of certain operators,
** then WhereTerm.leftCursor and WhereTerm.leftColumn record the
** cursor number and column number for X.  WhereTerm.operator records
** the <op> using a bitmask encoding defined by WO_xxx below.  The
** use of a bitmask encoding for the operator allows us to search
** quickly for terms that match any of several different operators.
**
** prereqRight and prereqAll record sets of cursor numbers,
** but they do so indirectly.  A single ExprMaskSet structure translates
** cursor number into bits and the translated bit is stored in the prereq
** fields.  The translation is used in order to maximize the number of
** bits that will fit in a Bitmask.  The VDBE cursor numbers might be
** spread out over the non-negative integers.  For example, the cursor
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
struct WhereTerm {
  Expr *pExpr;            /* Pointer to the subexpression */
  u16 idx;                /* Index of this term in pWC->a[] */
  i16 iPartner;           /* Disable pWC->a[iPartner] when this term disabled */
  u16 flags;              /* Bit flags.  See below */
  i16 leftCursor;         /* Cursor number of X in "X <op> <expr>" */
  i16 leftColumn;         /* Column number of X in "X <op> <expr>" */
  u8 operator;            /* A WO_xx value describing <op> */
  WhereClause *pWC;       /* The clause this term is part of */
  Bitmask prereqRight;    /* Bitmask of tables used by pRight */
  Bitmask prereqAll;      /* Bitmask of tables referenced by p */
};

/*
** Allowed values of WhereTerm.flags
*/
#define TERM_DYNAMIC    0x0001   /* Need to call sqlite3ExprDelete(p) */
#define TERM_VIRTUAL    0x0002   /* Added by the optimizer.  Do not code */
#define TERM_CODED      0x0004   /* This term is already coded */

/*
** An instance of the following structure holds all information about a
** WHERE clause.  Mostly this is a container for one or more WhereTerms.
*/
struct WhereClause {
  Parse *pParse;           /* The parser context */
  int nTerm;               /* Number of terms */
  int nSlot;               /* Number of entries in a[] */
  WhereTerm *a;            /* Pointer to an array of terms */
  WhereTerm aStatic[10];   /* Initial static space for the terms */
};

/*
** When WhereTerms are used to select elements from an index, we
** call those terms "constraints".  For example, consider the following
** SQL:
**
**       CREATE TABLE t1(a INTEGER PRIMARY KEY, b, c, d);
**       CREATE INDEX t1i1 ON t1(b,c);
**
**       SELECT * FROM t1 WHERE d=5 AND b=7 AND c>11;
**
** In the SELECT statement, the "b=7" and "c>11" terms are constraints
** because they can be used to choose rows out of the t1i1 index.  But
** the "d=5" term is not a constraint because it is not indexed.
**
** When generating code to access an index, we have to keep track of
** all of the constraints associated with that index.  This is done
** using an array of instanaces of the following structure.  There is
** one instance of this structure for each constraint on the index.
**
** Actually, we allocate the array of this structure based on the total
** number of terms in the entire WHERE clause (because the number of
** constraints can never be more than that) and reuse it when coding
** each index.
*/
typedef struct WhereConstraint WhereConstraint;
struct WhereConstraint {
  int iMem;            /* Mem cell used to hold <expr> part of constraint */
};

/*
** An instance of the following structure keeps track of a mapping
** between VDBE cursor numbers and bits of the bitmasks in WhereTerm.
**
** The VDBE cursor numbers are small integers contained in 







|








|











|
|
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<







81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110





























111
112
113
114
115
116
117
struct WhereTerm {
  Expr *pExpr;            /* Pointer to the subexpression */
  u16 idx;                /* Index of this term in pWC->a[] */
  i16 iPartner;           /* Disable pWC->a[iPartner] when this term disabled */
  u16 flags;              /* Bit flags.  See below */
  i16 leftCursor;         /* Cursor number of X in "X <op> <expr>" */
  i16 leftColumn;         /* Column number of X in "X <op> <expr>" */
  u16 operator;           /* A WO_xx value describing <op> */
  WhereClause *pWC;       /* The clause this term is part of */
  Bitmask prereqRight;    /* Bitmask of tables used by pRight */
  Bitmask prereqAll;      /* Bitmask of tables referenced by p */
};

/*
** Allowed values of WhereTerm.flags
*/
#define TERM_DYNAMIC    0x0001   /* Need to call sqlite3ExprDelete(pExpr) */
#define TERM_VIRTUAL    0x0002   /* Added by the optimizer.  Do not code */
#define TERM_CODED      0x0004   /* This term is already coded */

/*
** An instance of the following structure holds all information about a
** WHERE clause.  Mostly this is a container for one or more WhereTerms.
*/
struct WhereClause {
  Parse *pParse;           /* The parser context */
  int nTerm;               /* Number of terms */
  int nSlot;               /* Number of entries in a[] */
  WhereTerm *a;            /* Each a[] describes a term of the WHERE cluase */
  WhereTerm aStatic[10];   /* Initial static space for a[] */





























};

/*
** An instance of the following structure keeps track of a mapping
** between VDBE cursor numbers and bits of the bitmasks in WhereTerm.
**
** The VDBE cursor numbers are small integers contained in 
155
156
157
158
159
160
161




























162
163
164
165
166
167
168
typedef struct ExprMaskSet ExprMaskSet;
struct ExprMaskSet {
  int n;                        /* Number of assigned cursor values */
  int ix[sizeof(Bitmask)*8];    /* Cursor assigned to each bit */
};






























/*
** Initialize a preallocated WhereClause structure.
*/
static void whereClauseInit(WhereClause *pWC, Parse *pParse){
  pWC->pParse = pParse;
  pWC->nTerm = 0;
  pWC->nSlot = ARRAYSIZE(pWC->aStatic);







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







139
140
141
142
143
144
145
146
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
typedef struct ExprMaskSet ExprMaskSet;
struct ExprMaskSet {
  int n;                        /* Number of assigned cursor values */
  int ix[sizeof(Bitmask)*8];    /* Cursor assigned to each bit */
};


/*
** Bitmasks for the operators that indices are able to exploit.  An
** OR-ed combination of these values can be used when searching for
** terms in the where clause.
*/
#define WO_IN     1
#define WO_LIST   2
#define WO_SELECT 4
#define WO_EQ     8
#define WO_LT     (WO_EQ<<(TK_LT-TK_EQ))
#define WO_LE     (WO_EQ<<(TK_LE-TK_EQ))
#define WO_GT     (WO_EQ<<(TK_GT-TK_EQ))
#define WO_GE     (WO_EQ<<(TK_GE-TK_EQ))

/*
** Value for flags returned by bestIndex()
*/
#define WHERE_ROWID_EQ       0x0001   /* rowid=EXPR or rowid IN (...) */
#define WHERE_ROWID_RANGE    0x0002   /* rowid<EXPR and/or rowid>EXPR */
#define WHERE_COLUMN_EQ      0x0010   /* x=EXPR or x IN (...) */
#define WHERE_COLUMN_RANGE   0x0020   /* x<EXPR and/or x>EXPR */
#define WHERE_COLUMN_IN      0x0040   /* x IN (...) */
#define WHERE_TOP_LIMIT      0x0100   /* x<EXPR or x<=EXPR constraint */
#define WHERE_BTM_LIMIT      0x0200   /* x>EXPR or x>=EXPR constraint */
#define WHERE_IDX_ONLY       0x0800   /* Use index only - omit table */
#define WHERE_ORDERBY        0x1000   /* Output will appear in correct order */
#define WHERE_REVERSE        0x2000   /* Scan in reverse order */

/*
** Initialize a preallocated WhereClause structure.
*/
static void whereClauseInit(WhereClause *pWC, Parse *pParse){
  pWC->pParse = pParse;
  pWC->nTerm = 0;
  pWC->nSlot = ARRAYSIZE(pWC->aStatic);
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
** filled with pointers to the subexpressions.  For example:
**
**    WHERE  a=='hello' AND coalesce(b,11)<10 AND (c+12!=d OR c==22)
**           \________/     \_______________/     \________________/
**            slot[0]            slot[1]               slot[2]
**
** The original WHERE clause in pExpr is unaltered.  All this routine
** does is make aSlot[] entries point to substructure within pExpr.
**
** aSlot[] is an array of subexpressions structures.  There are nSlot
** spaces left in this array.  This routine finds as many AND-separated
** subexpressions as it can and puts pointers to those subexpressions
** into aSlot[] entries.  The return value is the number of slots filled.
*/
static void whereSplit(WhereClause *pWC, Expr *pExpr){
  if( pExpr==0 ) return;
  if( pExpr->op!=TK_AND ){
    whereClauseInsert(pWC, pExpr, 0);
  }else{
    whereSplit(pWC, pExpr->pLeft);







|

|
|
|
<







230
231
232
233
234
235
236
237
238
239
240
241

242
243
244
245
246
247
248
** filled with pointers to the subexpressions.  For example:
**
**    WHERE  a=='hello' AND coalesce(b,11)<10 AND (c+12!=d OR c==22)
**           \________/     \_______________/     \________________/
**            slot[0]            slot[1]               slot[2]
**
** The original WHERE clause in pExpr is unaltered.  All this routine
** does is make slot[] entries point to substructure within pExpr.
**
** In the previous sentence and in the diagram, "slot[]" refers to
** the WhereClause.a[] array.  This array grows as needed to contain
** all terms of the WHERE clause.

*/
static void whereSplit(WhereClause *pWC, Expr *pExpr){
  if( pExpr==0 ) return;
  if( pExpr->op!=TK_AND ){
    whereClauseInsert(pWC, pExpr, 0);
  }else{
    whereSplit(pWC, pExpr->pLeft);
277
278
279
280
281
282
283
284


285
286
287
288
289
290
291
** tree.
**
** In order for this routine to work, the calling function must have
** previously invoked sqlite3ExprResolveNames() on the expression.  See
** the header comment on that routine for additional information.
** The sqlite3ExprResolveNames() routines looks for column names and
** sets their opcodes to TK_COLUMN and their Expr.iTable fields to
** the VDBE cursor number of the table.


*/
static Bitmask exprListTableUsage(ExprMaskSet *, ExprList *);
static Bitmask exprTableUsage(ExprMaskSet *pMaskSet, Expr *p){
  Bitmask mask = 0;
  if( p==0 ) return 0;
  if( p->op==TK_COLUMN ){
    mask = getMask(pMaskSet, p->iTable);







|
>
>







288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
** tree.
**
** In order for this routine to work, the calling function must have
** previously invoked sqlite3ExprResolveNames() on the expression.  See
** the header comment on that routine for additional information.
** The sqlite3ExprResolveNames() routines looks for column names and
** sets their opcodes to TK_COLUMN and their Expr.iTable fields to
** the VDBE cursor number of the table.  This routine just has to
** translate the cursor numbers into bitmask values and OR all
** the bitmasks together.
*/
static Bitmask exprListTableUsage(ExprMaskSet *, ExprList *);
static Bitmask exprTableUsage(ExprMaskSet *pMaskSet, Expr *p){
  Bitmask mask = 0;
  if( p==0 ) return 0;
  if( p->op==TK_COLUMN ){
    mask = getMask(pMaskSet, p->iTable);
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
    assert( TK_GT>TK_EQ );
    assert( TK_GT<TK_LE );
    assert( pExpr->op>=TK_GT && pExpr->op<=TK_GE );
    pExpr->op = ((pExpr->op-TK_GT)^2)+TK_GT;
  }
}

/*
** Bitmasks for the operators that indices are able to exploit.  An
** OR-ed combination of these values can be used when searching for
** terms in the where clause.
*/
#define WO_IN  1
#define WO_EQ  2
#define WO_LT  (2<<(TK_LT-TK_EQ))
#define WO_LE  (2<<(TK_LE-TK_EQ))
#define WO_GT  (2<<(TK_GT-TK_EQ))
#define WO_GE  (2<<(TK_GE-TK_EQ))

/*
** Translate from TK_xx operator to WO_xx bitmask.
*/
static int operatorMask(int op){

  assert( allowedOp(op) );
  if( op==TK_IN ){
    return WO_IN;
  }else{
    return 1<<(op+1-TK_EQ);
  }







}

/*
** Search for a term in the WHERE clause that is of the form "X <op> <expr>"
** where X is a reference to the iColumn of table iCur and <op> is one of
** the WO_xx operator codes specified by the op parameter.
** Return a pointer to the term.  Return 0 if not found.
*/
static WhereTerm *findTerm(
  WhereClause *pWC,     /* The WHERE clause to be searched */
  int iCur,             /* Cursor number of LHS */
  int iColumn,          /* Column number of LHS */
  Bitmask notReady,     /* RHS must not overlap with this mask */
  u8 op,                /* Mask of WO_xx values describing operator */
  Index *pIdx           /* Must be compatible with this index, if not NULL */
){
  WhereTerm *pTerm;
  int k;
  for(pTerm=pWC->a, k=pWC->nTerm; k; k--, pTerm++){
    if( pTerm->leftCursor==iCur
       && (pTerm->prereqRight & notReady)==0







<
<
<
<
<
<
<
<
<
<
<
<




>


|

|

>
>
>
>
>
>
>













|







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
    assert( TK_GT>TK_EQ );
    assert( TK_GT<TK_LE );
    assert( pExpr->op>=TK_GT && pExpr->op<=TK_GE );
    pExpr->op = ((pExpr->op-TK_GT)^2)+TK_GT;
  }
}













/*
** Translate from TK_xx operator to WO_xx bitmask.
*/
static int operatorMask(int op){
  int c;
  assert( allowedOp(op) );
  if( op==TK_IN ){
    c = WO_IN;
  }else{
    c = WO_EQ<<(op-TK_EQ);
  }
  assert( op!=TK_IN || c==WO_IN );
  assert( op!=TK_EQ || c==WO_EQ );
  assert( op!=TK_LT || c==WO_LT );
  assert( op!=TK_LE || c==WO_LE );
  assert( op!=TK_GT || c==WO_GT );
  assert( op!=TK_GE || c==WO_GE );
  return c;
}

/*
** Search for a term in the WHERE clause that is of the form "X <op> <expr>"
** where X is a reference to the iColumn of table iCur and <op> is one of
** the WO_xx operator codes specified by the op parameter.
** Return a pointer to the term.  Return 0 if not found.
*/
static WhereTerm *findTerm(
  WhereClause *pWC,     /* The WHERE clause to be searched */
  int iCur,             /* Cursor number of LHS */
  int iColumn,          /* Column number of LHS */
  Bitmask notReady,     /* RHS must not overlap with this mask */
  u16 op,               /* Mask of WO_xx values describing operator */
  Index *pIdx           /* Must be compatible with this index, if not NULL */
){
  WhereTerm *pTerm;
  int k;
  for(pTerm=pWC->a, k=pWC->nTerm; k; k--, pTerm++){
    if( pTerm->leftCursor==iCur
       && (pTerm->prereqRight & notReady)==0
423
424
425
426
427
428
429
430
431
432






433
434
435
436
437
438
439
    }
  }
  return 0;
}

/*
** The input to this routine is an WhereTerm structure with only the
** "p" field filled in.  The job of this routine is to analyze the
** subexpression and populate all the other fields of the WhereTerm
** structure.






*/
static void exprAnalyze(
  SrcList *pSrc,            /* the FROM clause */
  ExprMaskSet *pMaskSet,    /* table masks */
  WhereTerm *pTerm          /* the WHERE clause term to be analyzed */
){
  Expr *pExpr = pTerm->pExpr;







|


>
>
>
>
>
>







432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
    }
  }
  return 0;
}

/*
** The input to this routine is an WhereTerm structure with only the
** "pExpr" field filled in.  The job of this routine is to analyze the
** subexpression and populate all the other fields of the WhereTerm
** structure.
**
** If the expression is of the form "<expr> <op> X" it gets commuted
** to the standard form of "X <op> <expr>".  If the expression is of
** the form "X <op> Y" where both X and Y are columns, then the original
** expression is unchanged and a new virtual expression of the form
** "Y <op> X" is added to the WHERE clause.  
*/
static void exprAnalyze(
  SrcList *pSrc,            /* the FROM clause */
  ExprMaskSet *pMaskSet,    /* table masks */
  WhereTerm *pTerm          /* the WHERE clause term to be analyzed */
){
  Expr *pExpr = pTerm->pExpr;
451
452
453
454
455
456
457







458
459
460
461
462
463
464
  if( allowedOp(pExpr->op) && (pTerm->prereqRight & prereqLeft)==0 ){
    Expr *pLeft = pExpr->pLeft;
    Expr *pRight = pExpr->pRight;
    if( pLeft->op==TK_COLUMN ){
      pTerm->leftCursor = pLeft->iTable;
      pTerm->leftColumn = pLeft->iColumn;
      pTerm->operator = operatorMask(pExpr->op);







    }
    if( pRight && pRight->op==TK_COLUMN ){
      WhereTerm *pNew;
      Expr *pDup;
      if( pTerm->leftCursor>=0 ){
        pDup = sqlite3ExprDup(pExpr);
        pNew = whereClauseInsert(pTerm->pWC, pDup, TERM_VIRTUAL|TERM_DYNAMIC);







>
>
>
>
>
>
>







466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
  if( allowedOp(pExpr->op) && (pTerm->prereqRight & prereqLeft)==0 ){
    Expr *pLeft = pExpr->pLeft;
    Expr *pRight = pExpr->pRight;
    if( pLeft->op==TK_COLUMN ){
      pTerm->leftCursor = pLeft->iTable;
      pTerm->leftColumn = pLeft->iColumn;
      pTerm->operator = operatorMask(pExpr->op);
      if( pTerm->operator==WO_IN ){
        if( pExpr->pSelect ){
          pTerm->operator |= WO_SELECT;
        }else if( pExpr->pList ){
          pTerm->operator |= WO_LIST;
        }
      }
    }
    if( pRight && pRight->op==TK_COLUMN ){
      WhereTerm *pNew;
      Expr *pDup;
      if( pTerm->leftCursor>=0 ){
        pDup = sqlite3ExprDup(pExpr);
        pNew = whereClauseInsert(pTerm->pWC, pDup, TERM_VIRTUAL|TERM_DYNAMIC);
594
595
596
597
598
599
600

601

602
603
604
605
606
607
608
609
610
611
612
613
614
615
616

617
618
619
620
621
622
623
624
625
626
627
628

629
630
631
632
633
634

635

636



637


638
639
640
641
642

643
644

645

646


647
648
649
650

651
652
653
654



655
656
657
658
659
660
661
662

663
664
665
666
667

668



669
670
671


672
673



674
675
676
677
678
679
680
681

682
683
684
685

686
687
688
689

690
691
692
693

694
695
696
697
698
699
700
701
702
703
704
705

706
707
708
709

710
711
712
713
714
715
716
717

718

719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739

740
741
742
743
744
745
746
747
748



749

750
751
752

753

754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769

770
771
772
773
774
775
776
777
778

779
780
781
782
783
784
785
786
787
788
789
790
791
792


793

794
795
796
797
798
799
800
801
    *pbRev = pOrderBy->a[0].sortOrder;
    return 1;
  }
  return 0;
}

/*

** Value for flags returned by bestIndex()

*/
#define WHERE_ROWID_EQ       0x0001   /* rowid=EXPR or rowid IN (...) */
#define WHERE_ROWID_RANGE    0x0002   /* rowid<EXPR and/or rowid>EXPR */
#define WHERE_COLUMN_EQ      0x0004   /* x=EXPR or x IN (...) */
#define WHERE_COLUMN_RANGE   0x0008   /* x<EXPR and/or x>EXPR */
#define WHERE_SCAN           0x0010   /* Do a full table scan */
#define WHERE_REVERSE        0x0020   /* Scan in reverse order */
#define WHERE_ORDERBY        0x0040   /* Output will appear in correct order */
#define WHERE_IDX_ONLY       0x0080   /* Use index only - omit table */
#define WHERE_TOP_LIMIT      0x0100   /* x<EXPR or x<=EXPR constraint */
#define WHERE_BTM_LIMIT      0x0200   /* x>EXPR or x>=EXPR constraint */
#define WHERE_USES_IN        0x0400   /* True if the IN operator is used */
#define WHERE_UNIQUE         0x0800   /* True if fully specifies a unique idx */

/*

** Find the best index for accessing a particular table.  Return the index,
** flags that describe how the index should be used, and the "score" for
** this index.
*/
static double bestIndex(
  Parse *pParse,              /* The parsing context */
  WhereClause *pWC,           /* The WHERE clause */
  struct SrcList_item *pSrc,  /* The FROM clause term to search */
  Bitmask notReady,           /* Mask of cursors that are not available */
  ExprList *pOrderBy,         /* The order by clause */
  Index **ppIndex,            /* Make *ppIndex point to the best index */
  int *pFlags                 /* Put flags describing this choice in *pFlags */

){
  WhereTerm *pTerm;
  Index *pProbe;
  Index *bestIdx = 0;
  double bestScore = 0.0;
  int bestFlags = 0;

  int iCur = pSrc->iCursor;

  int rev;






  /* Check for a rowid=EXPR or rowid IN (...) constraint
  */
  pTerm = findTerm(pWC, iCur, -1, notReady, WO_EQ|WO_IN, 0);
  if( pTerm ){
    *ppIndex = 0;

    if( pTerm->operator & WO_EQ ){
      *pFlags = WHERE_ROWID_EQ;

      if( pOrderBy ) *pFlags |= WHERE_ORDERBY;

      return 1.0e10;


    }else{
      *pFlags = WHERE_ROWID_EQ | WHERE_USES_IN;
      return 1.0e9;
    }

  }

  /* Check for constraints on a range of rowids
  */



  pTerm = findTerm(pWC, iCur, -1, notReady, WO_LT|WO_LE|WO_GT|WO_GE, 0);
  if( pTerm ){
    int flags;
    *ppIndex = 0;
    if( pTerm->operator & (WO_LT|WO_LE) ){
      flags = WHERE_ROWID_RANGE | WHERE_TOP_LIMIT;
      if( findTerm(pWC, iCur, -1, notReady, WO_GT|WO_GE, 0) ){
        flags |= WHERE_BTM_LIMIT;

      }
    }else{
      flags = WHERE_ROWID_RANGE | WHERE_BTM_LIMIT;
      if( findTerm(pWC, iCur, -1, notReady, WO_LT|WO_LE, 0) ){
        flags |= WHERE_TOP_LIMIT;

      }



    }
    if( pOrderBy && sortableByRowid(iCur, pOrderBy, &rev) ){
      flags |= WHERE_ORDERBY;


      if( rev ) flags |= WHERE_REVERSE;
    }



    bestScore = 99.0;
    bestFlags = flags;
  }

  /* Look at each index.
  */
  for(pProbe=pSrc->pTab->pIndex; pProbe; pProbe=pProbe->pNext){
    int i;

    int nEq;
    int usesIN = 0;
    int flags;
    double score = 0.0;


    /* Count the number of columns in the index that are satisfied
    ** by x=EXPR constraints or x IN (...) constraints.
    */

    for(i=0; i<pProbe->nColumn; i++){
      int j = pProbe->aiColumn[i];
      pTerm = findTerm(pWC, iCur, j, notReady, WO_EQ|WO_IN, pProbe);
      if( pTerm==0 ) break;

      if( pTerm->operator==WO_IN ){
        if( i==0 ) usesIN = 1;
        break;
      }
    }
    nEq = i + usesIN;
    score = i*100.0 + usesIN*50.0;

    /* The optimization type is RANGE if there are no == or IN constraints
    */
    if( usesIN ){
      flags = WHERE_COLUMN_EQ | WHERE_USES_IN;

    }else if( nEq ){
      flags = WHERE_COLUMN_EQ;
    }else{
      flags = WHERE_COLUMN_RANGE;

    }

    /* Check for a uniquely specified row
    */
#if 0
    if( nEq==pProbe->nColumn && pProbe->isUnique ){
      flags |= WHERE_UNIQUE;
    }

#endif


    /* Look for range constraints
    */
    if( !usesIN && nEq<pProbe->nColumn ){
      int j = pProbe->aiColumn[nEq];
      pTerm = findTerm(pWC, iCur, j, notReady, WO_LT|WO_LE|WO_GT|WO_GE, pProbe);
      if( pTerm ){
        score += 20.0;
        flags = WHERE_COLUMN_RANGE;
        if( pTerm->operator & (WO_LT|WO_LE) ){
          flags |= WHERE_TOP_LIMIT;
          if( findTerm(pWC, iCur, j, notReady, WO_GT|WO_GE, pProbe) ){
            flags |= WHERE_BTM_LIMIT;
            score += 20.0;
          }
        }else{
          flags |= WHERE_BTM_LIMIT;
          if( findTerm(pWC, iCur, j, notReady, WO_LT|WO_LE, pProbe) ){
            flags |= WHERE_TOP_LIMIT;
            score += 20;
          }

        }
      }
    }

    /* Add extra points if this index can be used to satisfy the ORDER BY
    ** clause
    */
    if( pOrderBy && !usesIN &&
        isSortingIndex(pParse, pProbe, pSrc->pTab, iCur, pOrderBy, nEq, &rev) ){



      flags |= WHERE_ORDERBY;

      score += 10.0;
      if( rev ) flags |= WHERE_REVERSE;
    }



    /* Check to see if we can get away with using just the index without
    ** ever reading the table.  If that is the case, then add one bonus
    ** point to the score.
    */
    if( score>0.0 && pSrc->colUsed < (((Bitmask)1)<<(BMS-1)) ){
      Bitmask m = pSrc->colUsed;
      int j;
      for(j=0; j<pProbe->nColumn; j++){
        int x = pProbe->aiColumn[j];
        if( x<BMS-1 ){
          m &= ~(((Bitmask)1)<<x);
        }
      }
      if( m==0 ){
        flags |= WHERE_IDX_ONLY;
        score += 5;

      }
    }

    /* If this index has achieved the best score so far, then use it.
    */
    if( score>bestScore ){
      bestIdx = pProbe;
      bestScore = score;
      bestFlags = flags;

    }
  }

  /* Disable sorting if we are coming out in rowid order
  */
  if( bestIdx==0 && pOrderBy && sortableByRowid(iCur, pOrderBy, &rev) ){
    bestFlags |= WHERE_ORDERBY;
    if( rev ) bestFlags |= WHERE_REVERSE;
  }


  /* Report the best result
  */
  *ppIndex = bestIdx;


  *pFlags = bestFlags;

  return bestScore;
}


/*
** Disable a term in the WHERE clause.  Except, do not disable the term
** if it controls a LEFT OUTER JOIN and it did not originate in the ON
** or USING clause of that join.







>
|
>
|
<
<
|
|
|
|
|
|
|
<
<
<
|
|
>
|
<
|








|
>


<
|
|
|
>
|
>
|
>
>
>

>
>
|




>


>

>
|
>
>

<
|

>


|

>
>
>


<
<
<
|
|
|
>
|
<
<
|
|
>
|
>
>
>
|
|
|
>
>
|

>
>
>
|





|
|
>
|
<
<
<
>




>




>
|
<
<
<
<
<
<
|
<
<
|
<
>
|
<
<
<
>
|
|
<
<
<
<
<

>
|
>



|



<

<
<
|
|
|
|
<
<
|
|
|
|
>
|
|
|
<
|
|

|

>
>
>

>
|
|
|
>
|
>

|
|

|










|
>



|

|

|
|
>
|
<
<
<
<
<
|
|
|
|




>
>

>
|







616
617
618
619
620
621
622
623
624
625
626


627
628
629
630
631
632
633



634
635
636
637

638
639
640
641
642
643
644
645
646
647
648
649
650

651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678

679
680
681
682
683
684
685
686
687
688
689
690



691
692
693
694
695


696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722



723
724
725
726
727
728
729
730
731
732
733
734






735


736

737
738



739
740
741





742
743
744
745
746
747
748
749
750
751
752

753


754
755
756
757


758
759
760
761
762
763
764
765

766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809





810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
    *pbRev = pOrderBy->a[0].sortOrder;
    return 1;
  }
  return 0;
}

/*
** Find the best index for accessing a particular table.  Return a pointer
** to the index, flags that describe how the index should be used, the
** number of equality constraints and the "cost" for this index.
**


** The lowest cost index wins.  The cost is an estimate of the amount of
** CPU and disk I/O need to process the request using the selected index.
** Factors that influence cost include:
**
**    *  The estimated number of rows that will be retrieved.  (The
**       fewer the better.)
**



**    *  Whether or not sorting must occur.
**
**    *  Whether or not there must be separate lookups in the
**       index and in the main table.

**
*/
static double bestIndex(
  Parse *pParse,              /* The parsing context */
  WhereClause *pWC,           /* The WHERE clause */
  struct SrcList_item *pSrc,  /* The FROM clause term to search */
  Bitmask notReady,           /* Mask of cursors that are not available */
  ExprList *pOrderBy,         /* The order by clause */
  Index **ppIndex,            /* Make *ppIndex point to the best index */
  int *pFlags,                /* Put flags describing this choice in *pFlags */
  int *pnEq                   /* Put the number of == or IN constraints here */
){
  WhereTerm *pTerm;

  Index *bestIdx = 0;         /* Index that gives the lowest cost */
  double lowestCost = 1.0e99; /* The cost of using bestIdx */
  int bestFlags = 0;          /* Flags associated with bestIdx */
  int bestNEq = 0;            /* Best value for nEq */
  int iCur = pSrc->iCursor;   /* The cursor of the table to be accessed */
  Index *pProbe;              /* An index we are evaluating */
  int rev;                    /* True to scan in reverse order */
  int flags;                  /* Flags associated with pProbe */
  int nEq;                    /* Number of == or IN constraints */
  double cost;                /* Cost of using pProbe */

  TRACE(("bestIndex: tbl=%s notReady=%x\n", pSrc->pTab->zName, notReady));

  /* Check for a rowid=EXPR or rowid IN (...) constraints
  */
  pTerm = findTerm(pWC, iCur, -1, notReady, WO_EQ|WO_IN, 0);
  if( pTerm ){
    *ppIndex = 0;
    bestFlags = WHERE_ROWID_EQ;
    if( pTerm->operator & WO_EQ ){
      *pFlags = WHERE_ROWID_EQ;
      *pnEq = 1;
      if( pOrderBy ) *pFlags |= WHERE_ORDERBY;
      TRACE(("... best is rowid\n"));
      return 0.0;
    }else if( pTerm->operator & WO_LIST ){
      lowestCost = pTerm->pExpr->pList->nExpr;
    }else{

      lowestCost = 100.0;
    }
    TRACE(("... rowid IN cost: %g\n", lowestCost));
  }

  /* Check for constraints on a range of rowids or a full table scan.
  */
  pProbe = pSrc->pTab->pIndex;
  cost = pProbe ? pProbe->aiRowEst[0] : 100000.0;
  TRACE(("... base cost: %g\n", cost));
  pTerm = findTerm(pWC, iCur, -1, notReady, WO_LT|WO_LE|WO_GT|WO_GE, 0);
  if( pTerm ){



    flags = WHERE_ROWID_RANGE;
    if( findTerm(pWC, iCur, -1, notReady, WO_LT|WO_LE, 0) ){
      flags |= WHERE_TOP_LIMIT;
      cost *= 0.25;  /* Guess that rowid<EXPR eliminates 75% of the search */
    }


    if( findTerm(pWC, iCur, -1, notReady, WO_GT|WO_GE, 0) ){
      flags |= WHERE_BTM_LIMIT;
      cost *= 0.25;  /* Guess that rowid>EXPR eliminates 75% of the search */
    }
    TRACE(("... rowid range cost: %g\n", cost));
  }else{
    flags = 0;
  }
  if( pOrderBy && sortableByRowid(iCur, pOrderBy, &rev) ){
    flags |= WHERE_ORDERBY|WHERE_ROWID_RANGE;
    cost *= 0.5;
    if( rev ){
      flags |= WHERE_REVERSE;
    }
    TRACE(("... order by reduces cost to %g\n", cost));
  }
  if( cost<lowestCost ){
    lowestCost = cost;
    bestFlags = flags;
  }

  /* Look at each index.
  */
  for(; pProbe; pProbe=pProbe->pNext){
    int i;                       /* Loop counter */
    double inMultiplier = 2.0;   /* Includes built-in index lookup penalty */




    TRACE(("... index %s:\n", pProbe->zName));

    /* Count the number of columns in the index that are satisfied
    ** by x=EXPR constraints or x IN (...) constraints.
    */
    flags = 0;
    for(i=0; i<pProbe->nColumn; i++){
      int j = pProbe->aiColumn[i];
      pTerm = findTerm(pWC, iCur, j, notReady, WO_EQ|WO_IN, pProbe);
      if( pTerm==0 ) break;
      flags |= WHERE_COLUMN_EQ;
      if( pTerm->operator & WO_IN ){






        flags |= WHERE_COLUMN_IN;


        if( pTerm->operator & WO_SELECT ){

          inMultiplier *= 100.0;
        }else if( pTerm->operator & WO_LIST ){



          inMultiplier *= pTerm->pExpr->pList->nExpr + 1.0;
        }
      }





    }
    cost = pProbe->aiRowEst[i] * inMultiplier;
    nEq = i;
    TRACE(("...... nEq=%d inMult=%g cost=%g\n", nEq, inMultiplier, cost));

    /* Look for range constraints
    */
    if( nEq<pProbe->nColumn ){
      int j = pProbe->aiColumn[nEq];
      pTerm = findTerm(pWC, iCur, j, notReady, WO_LT|WO_LE|WO_GT|WO_GE, pProbe);
      if( pTerm ){

        flags = WHERE_COLUMN_RANGE;


        if( findTerm(pWC, iCur, j, notReady, WO_LT|WO_LE, pProbe) ){
          flags |= WHERE_TOP_LIMIT;
          cost *= 0.5;
        }


        if( findTerm(pWC, iCur, j, notReady, WO_GT|WO_GE, pProbe) ){
          flags |= WHERE_BTM_LIMIT;
          cost *= 0.5;
        }
        TRACE(("...... range reduces cost to %g\n", cost));
      }
    }


    /* Reduce the cost substantially if this index can be used to satisfy
    ** the ORDER BY clause
    */
    if( pOrderBy && (flags & WHERE_COLUMN_IN)==0 &&
        isSortingIndex(pParse, pProbe, pSrc->pTab, iCur, pOrderBy, nEq, &rev) ){
      if( flags==0 ){
        flags = WHERE_COLUMN_RANGE;
      }
      flags |= WHERE_ORDERBY;
      cost *= 0.5;
      if( rev ){
        flags |= WHERE_REVERSE;
      }
      TRACE(("...... orderby reduces cost to %g\n", cost));
    }

    /* Check to see if we can get away with using just the index without
    ** ever reading the table.  If that is the case, then halve the
    ** cost of this index.
    */
    if( flags && pSrc->colUsed < (((Bitmask)1)<<(BMS-1)) ){
      Bitmask m = pSrc->colUsed;
      int j;
      for(j=0; j<pProbe->nColumn; j++){
        int x = pProbe->aiColumn[j];
        if( x<BMS-1 ){
          m &= ~(((Bitmask)1)<<x);
        }
      }
      if( m==0 ){
        flags |= WHERE_IDX_ONLY;
        cost *= 0.5;
        TRACE(("...... idx-only reduces cost to %g\n", cost));
      }
    }

    /* If this index has achieved the lowest cost so far, then use it.
    */
    if( cost < lowestCost ){
      bestIdx = pProbe;
      lowestCost = cost;
      if( flags==0 ){
        flags = WHERE_COLUMN_RANGE;
      }





      bestFlags = flags;
      bestNEq = nEq;
    }
  }

  /* Report the best result
  */
  *ppIndex = bestIdx;
  TRACE(("best index is %s, cost=%g, flags=%x, nEq=%d\n",
        bestIdx ? bestIdx->zName : "(none)", lowestCost, bestFlags, bestNEq));
  *pFlags = bestFlags;
  *pnEq = bestNEq;
  return lowestCost;
}


/*
** Disable a term in the WHERE clause.  Except, do not disable the term
** if it controls a LEFT OUTER JOIN and it did not originate in the ON
** or USING clause of that join.
846
847
848
849
850
851
852
853
854







855
856
857
858
859
860
861
  sqlite3VdbeAddOp(v, OP_Goto, 0, brk);
  sqlite3VdbeAddOp(v, OP_MakeRecord, nColumn, 0);
  sqlite3IndexAffinityStr(v, pIdx);
}


/*
** Generate code for an equality term of the WHERE clause.  An equality
** term can be either X=expr  or X IN (...).   pTerm is the X.  







*/
static void codeEqualityTerm(
  Parse *pParse,      /* The parsing context */
  WhereTerm *pTerm,   /* The term of the WHERE clause to be coded */
  int brk,            /* Jump here to abandon the loop */
  WhereLevel *pLevel  /* When level of the FROM clause we are working on */
){







|
|
>
>
>
>
>
>
>







874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
  sqlite3VdbeAddOp(v, OP_Goto, 0, brk);
  sqlite3VdbeAddOp(v, OP_MakeRecord, nColumn, 0);
  sqlite3IndexAffinityStr(v, pIdx);
}


/*
** Generate code for a single equality term of the WHERE clause.  An equality
** term can be either X=expr or X IN (...).   pTerm is the term to be 
** coded.
**
** The current value for the constraint is left on the top of the stack.
**
** For a constraint of the form X=expr, the expression is evaluated and its
** result is left on the stack.  For constraints of the form X IN (...)
** this routine sets up a loop that will iterate over all values of X.
*/
static void codeEqualityTerm(
  Parse *pParse,      /* The parsing context */
  WhereTerm *pTerm,   /* The term of the WHERE clause to be coded */
  int brk,            /* Jump here to abandon the loop */
  WhereLevel *pLevel  /* When level of the FROM clause we are working on */
){
882
883
884
885
886
887
888








































































889
890
891
892
893
894
895
      aIn[1] = iTab;
      aIn[2] = sqlite3VdbeAddOp(v, OP_Column, iTab, 0);
    }
#endif
  }
  disableTerm(pLevel, pTerm);
}









































































#ifdef SQLITE_TEST
/*
** The following variable holds a text description of query plan generated
** by the most recent call to sqlite3WhereBegin().  Each call to WhereBegin
** overwrites the previous.  This information is used for testing and
** analysis only.







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







917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
1001
1002
      aIn[1] = iTab;
      aIn[2] = sqlite3VdbeAddOp(v, OP_Column, iTab, 0);
    }
#endif
  }
  disableTerm(pLevel, pTerm);
}

/*
** Generate code that will evaluate all == and IN constraints for an
** index.  The values for all constraints are left on the stack.
**
** For example, consider table t1(a,b,c,d,e,f) with index i1(a,b,c).
** Suppose the WHERE clause is this:  a==5 AND b IN (1,2,3) AND c>5 AND c<10
** The index has as many as three equality constraints, but in this
** example, the third "c" value is an inequality.  So only two 
** constraints are coded.  This routine will generate code to evaluate
** a==5 and b IN (1,2,3).  The current values for a and b will be left
** on the stack - a is the deepest and b the shallowest.
**
** In the example above nEq==2.  But this subroutine works for any value
** of nEq including 0.  If nEq==0, this routine is nearly a no-op.
** The only thing it does is allocate the pLevel->iMem memory cell.
**
** This routine always allocates at least one memory cell and puts
** the address of that memory cell in pLevel->iMem.  The code that
** calls this routine will use pLevel->iMem to store the termination
** key value of the loop.  If one or more IN operators appear, then
** this routine allocates an additional nEq memory cells for internal
** use.
*/
static void codeAllEqualityTerms(
  Parse *pParse,        /* Parsing context */
  WhereLevel *pLevel,   /* Which nested loop of the FROM we are coding */
  WhereClause *pWC,     /* The WHERE clause */
  Bitmask notReady,     /* Which parts of FROM have not yet been coded */
  int brk               /* Jump here to end the loop */
){
  int nEq = pLevel->nEq;        /* The number of == or IN constraints to code */
  int termsInMem = 0;           /* If true, store value in mem[] cells */
  Vdbe *v = pParse->pVdbe;      /* The virtual machine under construction */
  Index *pIdx = pLevel->pIdx;   /* The index being used for this loop */
  int iCur = pLevel->iTabCur;   /* The cursor of the table */
  WhereTerm *pTerm;             /* A single constraint term */
  int j;                        /* Loop counter */

  /* Figure out how many memory cells we will need then allocate them.
  ** We always need at least one used to store the loop terminator
  ** value.  If there are IN operators we'll need one for each == or
  ** IN constraint.
  */
  pLevel->iMem = pParse->nMem++;
  if( pLevel->flags & WHERE_COLUMN_IN ){
    pParse->nMem += pLevel->nEq;
    termsInMem = 1;
  }

  /* Evaluate the equality constraints
  */
  for(j=0; 1; j++){
    int k = pIdx->aiColumn[j];
    pTerm = findTerm(pWC, iCur, k, notReady, WO_EQ|WO_IN, pIdx);
    if( pTerm==0 ) break;
    assert( (pTerm->flags & TERM_CODED)==0 );
    codeEqualityTerm(pParse, pTerm, brk, pLevel);
    if( termsInMem ){
      sqlite3VdbeAddOp(v, OP_MemStore, pLevel->iMem+j+1, 1);
    }
  }
  assert( j==nEq );

  /* Make sure all the constraint values are on the top of the stack
  */
  if( termsInMem ){
    for(j=0; j<nEq; j++){
      sqlite3VdbeAddOp(v, OP_MemLoad, pLevel->iMem+j+1, 0);
    }
  }
}

#ifdef SQLITE_TEST
/*
** The following variable holds a text description of query plan generated
** by the most recent call to sqlite3WhereBegin().  Each call to WhereBegin
** overwrites the previous.  This information is used for testing and
** analysis only.
925
926
927
928
929
930
931
932


933
934
935
936
937
938
939
**            ...
**          end                     \    Code generated
**        end                        |-- by sqlite3WhereEnd()
**      end                         /
**
** Note that the loops might not be nested in the order in which they
** appear in the FROM clause if a different order is better able to make
** use of indices.


**
** There are Btree cursors associated with each table.  t1 uses cursor
** number pTabList->a[0].iCursor.  t2 uses the cursor pTabList->a[1].iCursor.
** And so forth.  This routine generates code to open those VDBE cursors
** and sqlite3WhereEnd() generates the code to close them.
**
** The code that sqlite3WhereBegin() generates leaves the cursors named







|
>
>







1032
1033
1034
1035
1036
1037
1038
1039
1040
1041
1042
1043
1044
1045
1046
1047
1048
**            ...
**          end                     \    Code generated
**        end                        |-- by sqlite3WhereEnd()
**      end                         /
**
** Note that the loops might not be nested in the order in which they
** appear in the FROM clause if a different order is better able to make
** use of indices.  Note also that when the IN operator appears in
** the WHERE clause, it might result in additional nested loops for
** scanning through all values on the right-hand side of the IN.
**
** There are Btree cursors associated with each table.  t1 uses cursor
** number pTabList->a[0].iCursor.  t2 uses the cursor pTabList->a[1].iCursor.
** And so forth.  This routine generates code to open those VDBE cursors
** and sqlite3WhereEnd() generates the code to close them.
**
** The code that sqlite3WhereBegin() generates leaves the cursors named
1000
1001
1002
1003
1004
1005
1006
1007
1008
1009
1010
1011
1012
1013
1014
  Bitmask notReady;          /* Cursors that are not yet positioned */
  WhereTerm *pTerm;          /* A single term in the WHERE clause */
  ExprMaskSet maskSet;       /* The expression mask set */
  WhereClause wc;            /* The WHERE clause is divided into these terms */
  struct SrcList_item *pTabItem;  /* A single entry from pTabList */
  WhereLevel *pLevel;             /* A single level in the pWInfo list */
  int iFrom;                      /* First unused FROM clause element */
  WhereConstraint *aConstraint;   /* Information on constraints */

  /* The number of tables in the FROM clause is limited by the number of
  ** bits in a Bitmask 
  */
  if( pTabList->nSrc>BMS ){
    sqlite3ErrorMsg(pParse, "at most %d tables in a join", BMS);
    return 0;







<







1109
1110
1111
1112
1113
1114
1115

1116
1117
1118
1119
1120
1121
1122
  Bitmask notReady;          /* Cursors that are not yet positioned */
  WhereTerm *pTerm;          /* A single term in the WHERE clause */
  ExprMaskSet maskSet;       /* The expression mask set */
  WhereClause wc;            /* The WHERE clause is divided into these terms */
  struct SrcList_item *pTabItem;  /* A single entry from pTabList */
  WhereLevel *pLevel;             /* A single level in the pWInfo list */
  int iFrom;                      /* First unused FROM clause element */


  /* The number of tables in the FROM clause is limited by the number of
  ** bits in a Bitmask 
  */
  if( pTabList->nSrc>BMS ){
    sqlite3ErrorMsg(pParse, "at most %d tables in a join", BMS);
    return 0;
1047
1048
1049
1050
1051
1052
1053
1054
1055
1056
1057
1058
1059
1060
1061
1062
1063







1064
1065
1066
1067
1068
1069
1070
1071

1072
1073
1074
1075
1076

1077
1078
1079
1080
1081
1082
1083
1084
1085
1086
1087
1088
1089
1090
1091
1092

1093
1094
1095
1096
1097
1098
1099
1100
1101
1102
1103
1104
1105

1106
1107
1108
1109
1110
1111
1112
  */
  for(i=0; i<pTabList->nSrc; i++){
    createMask(&maskSet, pTabList->a[i].iCursor);
  }
  for(i=wc.nTerm-1; i>=0; i--){
    exprAnalyze(pTabList, &maskSet, &wc.a[i]);
  }
  aConstraint = sqliteMalloc( wc.nTerm*sizeof(aConstraint[0]) );
  if( aConstraint==0 && wc.nTerm>0 ){
    goto whereBeginNoMem;
  }

  /* Chose the best index to use for each table in the FROM clause.
  **
  ** This loop fills in the pWInfo->a[].pIdx and pWInfo->a[].flags fields
  ** with information
  ** Reorder tables if necessary in order to choose a good ordering.







  ** However, LEFT JOIN tables cannot be reordered.
  */
  notReady = ~(Bitmask)0;
  pTabItem = pTabList->a;
  pLevel = pWInfo->a;
  for(i=iFrom=0, pLevel=pWInfo->a; i<pTabList->nSrc; i++, pLevel++){
    Index *pIdx;                /* Index for FROM table at pTabItem */
    int flags;                  /* Flags asssociated with pIdx */

    double score;               /* The score for pIdx */
    int j;                      /* For looping over FROM tables */
    Index *pBest = 0;           /* The best index seen so far */
    int bestFlags = 0;          /* Flags associated with pBest */
    double bestScore = -1.0;    /* The score of pBest */

    int bestJ;                  /* The value of j */
    Bitmask m;                  /* Bitmask value for j or bestJ */

    for(j=iFrom, pTabItem=&pTabList->a[j]; j<pTabList->nSrc; j++, pTabItem++){
      m = getMask(&maskSet, pTabItem->iCursor);
      if( (m & notReady)==0 ){
        if( j==iFrom ) iFrom++;
        continue;
      }
      score = bestIndex(pParse, &wc, pTabItem, notReady,
                        (j==0 && ppOrderBy) ? *ppOrderBy : 0,
                        &pIdx, &flags);
      if( score>bestScore ){
        bestScore = score;
        pBest = pIdx;
        bestFlags = flags;

        bestJ = j;
      }
      if( (pTabItem->jointype & JT_LEFT)!=0
         || (j>0 && (pTabItem[-1].jointype & JT_LEFT)!=0)
      ){
        break;
      }
    }
    if( bestFlags & WHERE_ORDERBY ){
      *ppOrderBy = 0;
    }
    pLevel->flags = bestFlags;
    pLevel->pIdx = pBest;

    pLevel->aInLoop = 0;
    pLevel->nIn = 0;
    if( pBest ){
      pLevel->iIdxCur = pParse->nTab++;
    }else{
      pLevel->iIdxCur = -1;
    }







<
<
<
<



|
|
|
>
>
>
>
>
>
>
|







>
|



|
>









|
|
|
|
|


>













>







1155
1156
1157
1158
1159
1160
1161




1162
1163
1164
1165
1166
1167
1168
1169
1170
1171
1172
1173
1174
1175
1176
1177
1178
1179
1180
1181
1182
1183
1184
1185
1186
1187
1188
1189
1190
1191
1192
1193
1194
1195
1196
1197
1198
1199
1200
1201
1202
1203
1204
1205
1206
1207
1208
1209
1210
1211
1212
1213
1214
1215
1216
1217
1218
1219
1220
1221
1222
1223
1224
1225
1226
1227
  */
  for(i=0; i<pTabList->nSrc; i++){
    createMask(&maskSet, pTabList->a[i].iCursor);
  }
  for(i=wc.nTerm-1; i>=0; i--){
    exprAnalyze(pTabList, &maskSet, &wc.a[i]);
  }





  /* Chose the best index to use for each table in the FROM clause.
  **
  ** This loop fills in the following fields:
  **
  **   pWInfo->a[].pIdx      The index to use for this level of the loop.
  **   pWInfo->a[].flags     WHERE_xxx flags associated with pIdx
  **   pWInfo->a[].nEq       The number of == and IN constraints
  **   pWInfo->a[].iFrom     When term of the FROM clause is being coded
  **   pWInfo->a[].iTabCur   The VDBE cursor for the database table
  **   pWInfo->a[].iIdxCur   The VDBE cursor for the index
  **
  ** This loop also figures out the nesting order of tables in the FROM
  ** clause.
  */
  notReady = ~(Bitmask)0;
  pTabItem = pTabList->a;
  pLevel = pWInfo->a;
  for(i=iFrom=0, pLevel=pWInfo->a; i<pTabList->nSrc; i++, pLevel++){
    Index *pIdx;                /* Index for FROM table at pTabItem */
    int flags;                  /* Flags asssociated with pIdx */
    int nEq;                    /* Number of == or IN constraints */
    double cost;                /* The cost for pIdx */
    int j;                      /* For looping over FROM tables */
    Index *pBest = 0;           /* The best index seen so far */
    int bestFlags = 0;          /* Flags associated with pBest */
    int bestNEq = 0;            /* nEq associated with pBest */
    double lowestCost = 1.0e99; /* Cost of the pBest */
    int bestJ;                  /* The value of j */
    Bitmask m;                  /* Bitmask value for j or bestJ */

    for(j=iFrom, pTabItem=&pTabList->a[j]; j<pTabList->nSrc; j++, pTabItem++){
      m = getMask(&maskSet, pTabItem->iCursor);
      if( (m & notReady)==0 ){
        if( j==iFrom ) iFrom++;
        continue;
      }
      cost = bestIndex(pParse, &wc, pTabItem, notReady,
                       (j==0 && ppOrderBy) ? *ppOrderBy : 0,
                       &pIdx, &flags, &nEq);
      if( cost<lowestCost ){
        lowestCost = cost;
        pBest = pIdx;
        bestFlags = flags;
        bestNEq = nEq;
        bestJ = j;
      }
      if( (pTabItem->jointype & JT_LEFT)!=0
         || (j>0 && (pTabItem[-1].jointype & JT_LEFT)!=0)
      ){
        break;
      }
    }
    if( bestFlags & WHERE_ORDERBY ){
      *ppOrderBy = 0;
    }
    pLevel->flags = bestFlags;
    pLevel->pIdx = pBest;
    pLevel->nEq = bestNEq;
    pLevel->aInLoop = 0;
    pLevel->nIn = 0;
    if( pBest ){
      pLevel->iIdxCur = pParse->nTab++;
    }else{
      pLevel->iIdxCur = -1;
    }
1196
1197
1198
1199
1200
1201
1202
1203
1204
1205
1206
1207
1208
1209
1210
1211
1212
1213
1214
1215
1216
1217
1218
1219
1220
1221
1222
1223
1224
1225
1226
1227
1228
1229
1230
1231
1232
1233
1234
1235
1236
1237
1238
1239
1240
1241
1242
1243
1244
1245
1246
1247
1248
1249
1250
1251
1252
1253
1254
1255
1256
1257
1258
1259
1260
1261
1262
1263
1264
1265
1266
1267
1268
1269
1270
1271
1272
1273
1274
1275
1276
1277
1278
1279
1280
1281
1282
1283
      assert( pTerm->leftCursor==iCur );
      assert( omitTable==0 );
      codeEqualityTerm(pParse, pTerm, brk, pLevel);
      sqlite3VdbeAddOp(v, OP_MustBeInt, 1, brk);
      sqlite3VdbeAddOp(v, OP_NotExists, iCur, brk);
      VdbeComment((v, "pk"));
      pLevel->op = OP_Noop;
    }else if( pLevel->flags & WHERE_COLUMN_EQ ){
      /* Case 2:  There is an index and all terms of the WHERE clause that
      **          refer to the index using the "==" or "IN" operators.
      */
      int start;
      int nColumn;

      /* For each column of the index, find the term of the WHERE clause that
      ** constraints that column.  If the WHERE clause term is X=expr, then
      ** generate code to evaluate expr and leave the result on the stack */
      for(j=0; 1; j++){
        int k = pIdx->aiColumn[j];
        pTerm = findTerm(&wc, iCur, k, notReady, WO_EQ|WO_IN, pIdx);
        if( pTerm==0 ) break;
        if( pTerm->operator==WO_IN && j>0 ) break;
        assert( (pTerm->flags & TERM_CODED)==0 );
        codeEqualityTerm(pParse, pTerm, brk, pLevel);
        if( pTerm->operator==WO_IN ){
          j++;
          break;
        }
      }
      nColumn = j;
      pLevel->iMem = pParse->nMem++;
      buildIndexProbe(v, nColumn, brk, pIdx);
      sqlite3VdbeAddOp(v, OP_MemStore, pLevel->iMem, 0);

      /* Generate code (1) to move to the first matching element of the table.
      ** Then generate code (2) that jumps to "brk" after the cursor is past
      ** the last matching element of the table.  The code (1) is executed
      ** once to initialize the search, the code (2) is executed before each
      ** iteration of the scan to see if the scan has finished. */
      if( bRev ){
        /* Scan in reverse order */
        sqlite3VdbeAddOp(v, OP_MoveLe, iIdxCur, brk);
        start = sqlite3VdbeAddOp(v, OP_MemLoad, pLevel->iMem, 0);
        sqlite3VdbeAddOp(v, OP_IdxLT, iIdxCur, brk);
        pLevel->op = OP_Prev;
      }else{
        /* Scan in the forward order */
        sqlite3VdbeAddOp(v, OP_MoveGe, iIdxCur, brk);
        start = sqlite3VdbeAddOp(v, OP_MemLoad, pLevel->iMem, 0);
        sqlite3VdbeOp3(v, OP_IdxGE, iIdxCur, brk, "+", P3_STATIC);
        pLevel->op = OP_Next;
      }
      sqlite3VdbeAddOp(v, OP_RowKey, iIdxCur, 0);
      sqlite3VdbeAddOp(v, OP_IdxIsNull, nColumn, cont);
      if( !omitTable ){
        sqlite3VdbeAddOp(v, OP_IdxRowid, iIdxCur, 0);
        sqlite3VdbeAddOp(v, OP_MoveGe, iCur, 0);
      }
      pLevel->p1 = iIdxCur;
      pLevel->p2 = start;
    }else if( pLevel->flags & WHERE_ROWID_RANGE ){
      /* Case 3:  We have an inequality comparison against the ROWID field.
      */
      int testOp = OP_Noop;
      int start;
      WhereTerm *pStart, *pEnd;

      assert( omitTable==0 );
      if( pLevel->flags & WHERE_BTM_LIMIT ){
        pStart = findTerm(&wc, iCur, -1, notReady, WO_GT|WO_GE, 0);
        assert( pStart!=0 );
      }else{
        pStart = 0;
      }
      if( pLevel->flags & WHERE_TOP_LIMIT ){
        pEnd = findTerm(&wc, iCur, -1, notReady, WO_LT|WO_LE, 0);
        assert( pEnd!=0 );
      }else{
        pEnd = 0;
      }
      assert( pStart!=0 || pEnd!=0 );
      if( bRev ){
        pTerm = pStart;
        pStart = pEnd;
        pEnd = pTerm;
      }
      if( pStart ){
        Expr *pX;







<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<

|


















<







1311
1312
1313
1314
1315
1316
1317





















































1318
1319
1320
1321
1322
1323
1324
1325
1326
1327
1328
1329
1330
1331
1332
1333
1334
1335
1336
1337

1338
1339
1340
1341
1342
1343
1344
      assert( pTerm->leftCursor==iCur );
      assert( omitTable==0 );
      codeEqualityTerm(pParse, pTerm, brk, pLevel);
      sqlite3VdbeAddOp(v, OP_MustBeInt, 1, brk);
      sqlite3VdbeAddOp(v, OP_NotExists, iCur, brk);
      VdbeComment((v, "pk"));
      pLevel->op = OP_Noop;





















































    }else if( pLevel->flags & WHERE_ROWID_RANGE ){
      /* Case 2:  We have an inequality comparison against the ROWID field.
      */
      int testOp = OP_Noop;
      int start;
      WhereTerm *pStart, *pEnd;

      assert( omitTable==0 );
      if( pLevel->flags & WHERE_BTM_LIMIT ){
        pStart = findTerm(&wc, iCur, -1, notReady, WO_GT|WO_GE, 0);
        assert( pStart!=0 );
      }else{
        pStart = 0;
      }
      if( pLevel->flags & WHERE_TOP_LIMIT ){
        pEnd = findTerm(&wc, iCur, -1, notReady, WO_LT|WO_LE, 0);
        assert( pEnd!=0 );
      }else{
        pEnd = 0;
      }

      if( bRev ){
        pTerm = pStart;
        pStart = pEnd;
        pEnd = pTerm;
      }
      if( pStart ){
        Expr *pX;
1313
1314
1315
1316
1317
1318
1319
1320
1321
1322
1323
1324
1325
1326
1327
1328
1329
1330
1331
1332

1333
1334
1335
1336
1337
1338

1339
1340
1341
1342
1343
1344
1345
1346
1347
1348
1349
1350
1351
1352
1353
1354
1355
1356
1357
1358
1359
1360
1361
1362
      pLevel->p2 = start;
      if( testOp!=OP_Noop ){
        sqlite3VdbeAddOp(v, OP_Rowid, iCur, 0);
        sqlite3VdbeAddOp(v, OP_MemLoad, pLevel->iMem, 0);
        sqlite3VdbeAddOp(v, testOp, 'n', brk);
      }
    }else if( pLevel->flags & WHERE_COLUMN_RANGE ){
      /* Case 4: 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 nEqColumn;
      int start;

      int leFlag=0, geFlag=0;
      int testOp;
      int topLimit = (pLevel->flags & WHERE_TOP_LIMIT)!=0;
      int btmLimit = (pLevel->flags & WHERE_BTM_LIMIT)!=0;

      /* Evaluate the equality constraints

      */
      for(j=0; 1; j++){
        int k = pIdx->aiColumn[j];
        pTerm = findTerm(&wc, iCur, k, notReady, WO_EQ, pIdx);
        if( pTerm==0 ) break;
        assert( (pTerm->flags & TERM_CODED)==0 );
        sqlite3ExprCode(pParse, pTerm->pExpr->pRight);
        disableTerm(pLevel, pTerm);
      }
      nEqColumn = j;

      /* Duplicate the equality term values because they will all be
      ** used twice: once to make the termination key and once to make the
      ** start key.
      */
      for(j=0; j<nEqColumn; j++){
        sqlite3VdbeAddOp(v, OP_Dup, nEqColumn-1, 0);
      }

      /* Generate the termination key.  This is the key value that
      ** will end the search.  There is no termination key if there
      ** are no equality terms and no "X<..." term.
      **
      ** 2002-Dec-04: On a reverse-order scan, the so-called "termination"







|




|





<

>





|
>

<
<
<
<
<
|
<
<
<





|
|







1374
1375
1376
1377
1378
1379
1380
1381
1382
1383
1384
1385
1386
1387
1388
1389
1390
1391

1392
1393
1394
1395
1396
1397
1398
1399
1400
1401





1402



1403
1404
1405
1406
1407
1408
1409
1410
1411
1412
1413
1414
1415
1416
      pLevel->p2 = start;
      if( testOp!=OP_Noop ){
        sqlite3VdbeAddOp(v, OP_Rowid, iCur, 0);
        sqlite3VdbeAddOp(v, OP_MemLoad, pLevel->iMem, 0);
        sqlite3VdbeAddOp(v, testOp, 'n', brk);
      }
    }else if( pLevel->flags & WHERE_COLUMN_RANGE ){
      /* Case 3: 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 "==" and "IN" operators.
      **
      **         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 start;
      int nEq = pLevel->nEq;
      int leFlag=0, geFlag=0;
      int testOp;
      int topLimit = (pLevel->flags & WHERE_TOP_LIMIT)!=0;
      int btmLimit = (pLevel->flags & WHERE_BTM_LIMIT)!=0;

      /* Generate code to evaluate all constraint terms using == or IN
      ** and level the values of those terms on the stack.
      */





      codeAllEqualityTerms(pParse, pLevel, &wc, notReady, brk);




      /* Duplicate the equality term values because they will all be
      ** used twice: once to make the termination key and once to make the
      ** start key.
      */
      for(j=0; j<nEq; j++){
        sqlite3VdbeAddOp(v, OP_Dup, nEq-1, 0);
      }

      /* Generate the termination key.  This is the key value that
      ** will end the search.  There is no termination key if there
      ** are no equality terms and no "X<..." term.
      **
      ** 2002-Dec-04: On a reverse-order scan, the so-called "termination"
1370
1371
1372
1373
1374
1375
1376
1377
1378
1379
1380
1381
1382
1383
1384
1385
1386
1387
1388
        pX = pTerm->pExpr;
        assert( (pTerm->flags & TERM_CODED)==0 );
        sqlite3ExprCode(pParse, pX->pRight);
        leFlag = pX->op==TK_LE;
        disableTerm(pLevel, pTerm);
        testOp = OP_IdxGE;
      }else{
        testOp = nEqColumn>0 ? OP_IdxGE : OP_Noop;
        leFlag = 1;
      }
      if( testOp!=OP_Noop ){
        int nCol = nEqColumn + topLimit;
        pLevel->iMem = pParse->nMem++;
        buildIndexProbe(v, nCol, brk, pIdx);
        if( bRev ){
          int op = leFlag ? OP_MoveLe : OP_MoveLt;
          sqlite3VdbeAddOp(v, op, iIdxCur, brk);
        }else{
          sqlite3VdbeAddOp(v, OP_MemStore, pLevel->iMem, 1);







|



|







1424
1425
1426
1427
1428
1429
1430
1431
1432
1433
1434
1435
1436
1437
1438
1439
1440
1441
1442
        pX = pTerm->pExpr;
        assert( (pTerm->flags & TERM_CODED)==0 );
        sqlite3ExprCode(pParse, pX->pRight);
        leFlag = pX->op==TK_LE;
        disableTerm(pLevel, pTerm);
        testOp = OP_IdxGE;
      }else{
        testOp = nEq>0 ? OP_IdxGE : OP_Noop;
        leFlag = 1;
      }
      if( testOp!=OP_Noop ){
        int nCol = nEq + topLimit;
        pLevel->iMem = pParse->nMem++;
        buildIndexProbe(v, nCol, brk, pIdx);
        if( bRev ){
          int op = leFlag ? OP_MoveLe : OP_MoveLt;
          sqlite3VdbeAddOp(v, op, iIdxCur, brk);
        }else{
          sqlite3VdbeAddOp(v, OP_MemStore, pLevel->iMem, 1);
1409
1410
1411
1412
1413
1414
1415
1416
1417
1418
1419
1420
1421
1422
1423
1424
        assert( (pTerm->flags & TERM_CODED)==0 );
        sqlite3ExprCode(pParse, pX->pRight);
        geFlag = pX->op==TK_GE;
        disableTerm(pLevel, pTerm);
      }else{
        geFlag = 1;
      }
      if( nEqColumn>0 || btmLimit ){
        int nCol = nEqColumn + btmLimit;
        buildIndexProbe(v, nCol, brk, pIdx);
        if( bRev ){
          pLevel->iMem = pParse->nMem++;
          sqlite3VdbeAddOp(v, OP_MemStore, pLevel->iMem, 1);
          testOp = OP_IdxLT;
        }else{
          int op = geFlag ? OP_MoveGe : OP_MoveGt;







|
|







1463
1464
1465
1466
1467
1468
1469
1470
1471
1472
1473
1474
1475
1476
1477
1478
        assert( (pTerm->flags & TERM_CODED)==0 );
        sqlite3ExprCode(pParse, pX->pRight);
        geFlag = pX->op==TK_GE;
        disableTerm(pLevel, pTerm);
      }else{
        geFlag = 1;
      }
      if( nEq>0 || btmLimit ){
        int nCol = nEq + btmLimit;
        buildIndexProbe(v, nCol, brk, pIdx);
        if( bRev ){
          pLevel->iMem = pParse->nMem++;
          sqlite3VdbeAddOp(v, OP_MemStore, pLevel->iMem, 1);
          testOp = OP_IdxLT;
        }else{
          int op = geFlag ? OP_MoveGe : OP_MoveGt;
1439
1440
1441
1442
1443
1444
1445
1446
1447
1448
1449
1450
1451
1452
1453
1454












































1455
1456
1457
1458
1459
1460
1461
        sqlite3VdbeAddOp(v, OP_MemLoad, pLevel->iMem, 0);
        sqlite3VdbeAddOp(v, testOp, iIdxCur, brk);
        if( (leFlag && !bRev) || (!geFlag && bRev) ){
          sqlite3VdbeChangeP3(v, -1, "+", P3_STATIC);
        }
      }
      sqlite3VdbeAddOp(v, OP_RowKey, iIdxCur, 0);
      sqlite3VdbeAddOp(v, OP_IdxIsNull, nEqColumn + topLimit, cont);
      if( !omitTable ){
        sqlite3VdbeAddOp(v, OP_IdxRowid, iIdxCur, 0);
        sqlite3VdbeAddOp(v, OP_MoveGe, iCur, 0);
      }

      /* Record the instruction used to terminate the loop.
      */
      pLevel->op = bRev ? OP_Prev : OP_Next;












































      pLevel->p1 = iIdxCur;
      pLevel->p2 = start;
    }else{
      /* Case 5:  There is no usable index.  We must do a complete
      **          scan of the entire table.
      */
      int opRewind;







|








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







1493
1494
1495
1496
1497
1498
1499
1500
1501
1502
1503
1504
1505
1506
1507
1508
1509
1510
1511
1512
1513
1514
1515
1516
1517
1518
1519
1520
1521
1522
1523
1524
1525
1526
1527
1528
1529
1530
1531
1532
1533
1534
1535
1536
1537
1538
1539
1540
1541
1542
1543
1544
1545
1546
1547
1548
1549
1550
1551
1552
1553
1554
1555
1556
1557
1558
1559
        sqlite3VdbeAddOp(v, OP_MemLoad, pLevel->iMem, 0);
        sqlite3VdbeAddOp(v, testOp, iIdxCur, brk);
        if( (leFlag && !bRev) || (!geFlag && bRev) ){
          sqlite3VdbeChangeP3(v, -1, "+", P3_STATIC);
        }
      }
      sqlite3VdbeAddOp(v, OP_RowKey, iIdxCur, 0);
      sqlite3VdbeAddOp(v, OP_IdxIsNull, nEq + topLimit, cont);
      if( !omitTable ){
        sqlite3VdbeAddOp(v, OP_IdxRowid, iIdxCur, 0);
        sqlite3VdbeAddOp(v, OP_MoveGe, iCur, 0);
      }

      /* Record the instruction used to terminate the loop.
      */
      pLevel->op = bRev ? OP_Prev : OP_Next;
      pLevel->p1 = iIdxCur;
      pLevel->p2 = start;
    }else if( pLevel->flags & WHERE_COLUMN_EQ ){
      /* Case 4:  There is an index and all terms of the WHERE clause that
      **          refer to the index using the "==" or "IN" operators.
      */
      int start;
      int nEq = pLevel->nEq;

      /* Generate code to evaluate all constraint terms using == or IN
      ** and level the values of those terms on the stack.
      */
      codeAllEqualityTerms(pParse, pLevel, &wc, notReady, brk);

      /* Generate a single key that will be used to both start and terminate
      ** the search
      */
      buildIndexProbe(v, nEq, brk, pIdx);
      sqlite3VdbeAddOp(v, OP_MemStore, pLevel->iMem, 0);

      /* Generate code (1) to move to the first matching element of the table.
      ** Then generate code (2) that jumps to "brk" after the cursor is past
      ** the last matching element of the table.  The code (1) is executed
      ** once to initialize the search, the code (2) is executed before each
      ** iteration of the scan to see if the scan has finished. */
      if( bRev ){
        /* Scan in reverse order */
        sqlite3VdbeAddOp(v, OP_MoveLe, iIdxCur, brk);
        start = sqlite3VdbeAddOp(v, OP_MemLoad, pLevel->iMem, 0);
        sqlite3VdbeAddOp(v, OP_IdxLT, iIdxCur, brk);
        pLevel->op = OP_Prev;
      }else{
        /* Scan in the forward order */
        sqlite3VdbeAddOp(v, OP_MoveGe, iIdxCur, brk);
        start = sqlite3VdbeAddOp(v, OP_MemLoad, pLevel->iMem, 0);
        sqlite3VdbeOp3(v, OP_IdxGE, iIdxCur, brk, "+", P3_STATIC);
        pLevel->op = OP_Next;
      }
      sqlite3VdbeAddOp(v, OP_RowKey, iIdxCur, 0);
      sqlite3VdbeAddOp(v, OP_IdxIsNull, nEq, cont);
      if( !omitTable ){
        sqlite3VdbeAddOp(v, OP_IdxRowid, iIdxCur, 0);
        sqlite3VdbeAddOp(v, OP_MoveGe, iCur, 0);
      }
      pLevel->p1 = iIdxCur;
      pLevel->p2 = start;
    }else{
      /* Case 5:  There is no usable index.  We must do a complete
      **          scan of the entire table.
      */
      int opRewind;
1555
1556
1557
1558
1559
1560
1561
1562
1563
1564
1565
1566
1567
1568
1569
#endif /* SQLITE_TEST // Testing and debugging use only */

  /* Record the continuation address in the WhereInfo structure.  Then
  ** clean up and return.
  */
  pWInfo->iContinue = cont;
  whereClauseClear(&wc);
  sqliteFree(aConstraint);
  return pWInfo;

  /* Jump here if malloc fails */
whereBeginNoMem:
  whereClauseClear(&wc);
  sqliteFree(pWInfo);
  return 0;







<







1653
1654
1655
1656
1657
1658
1659

1660
1661
1662
1663
1664
1665
1666
#endif /* SQLITE_TEST // Testing and debugging use only */

  /* Record the continuation address in the WhereInfo structure.  Then
  ** clean up and return.
  */
  pWInfo->iContinue = cont;
  whereClauseClear(&wc);

  return pWInfo;

  /* Jump here if malloc fails */
whereBeginNoMem:
  whereClauseClear(&wc);
  sqliteFree(pWInfo);
  return 0;