/ Check-in [5fd1f471]
Login

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

Overview
Comment:Fix ticket #1046 by removing code and simplifying the query optimizer. Remarkably, this simplification also makes the optimizer do a better job. Ticket #1051 was fixed as a side-effect. (CVS 2172)
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1: 5fd1f4711885e3dd6fb2c2700287f78bb0ea178a
User & Date: drh 2004-12-25 01:03:14
Context
2005-01-03
01:27
Fix comment typos. no code changes. (CVS 2173) check-in: 4165217e user: drh tags: trunk
2004-12-25
01:03
Fix ticket #1046 by removing code and simplifying the query optimizer. Remarkably, this simplification also makes the optimizer do a better job. Ticket #1051 was fixed as a side-effect. (CVS 2172) check-in: 5fd1f471 user: drh tags: trunk
2004-12-20
19:01
Add PRAGMA 'temp_store_directory'. Added os_*.c function sqlite3OsIsDirWritable(), split pragma.c changeTempStorage() function into invalidateTempStorage(). (CVS 2171) check-in: 772e22cb user: tpoindex tags: trunk
Changes
Hide Diffs Unified Diffs Ignore Whitespace Patch

Changes to src/delete.c.

8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
...
221
222
223
224
225
226
227
228
229
230
231
232

233
234
235
236
237
238
239
**    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
** in order to generate code for DELETE FROM statements.
**
** $Id: delete.c,v 1.93 2004/12/14 03:34:34 drh Exp $
*/
#include "sqliteInt.h"

/*
** Look up every table that is named in pSrc.  If any table is not found,
** add an error message to pParse->zErrMsg and return NULL.  If all tables
** are found, return a pointer to the last table.
................................................................................
      if( sqlite3CheckIndexCollSeq(pParse, pIdx) ){
        goto delete_from_cleanup;
      }
    }

    /* Begin the database scan
    */
    pWInfo = sqlite3WhereBegin(pParse, pTabList, pWhere, 1, 0, 0);
    if( pWInfo==0 ) goto delete_from_cleanup;

    /* Remember the key of every item to be deleted.
    */

    sqlite3VdbeAddOp(v, OP_ListWrite, 0, 0);
    if( db->flags & SQLITE_CountRows ){
      sqlite3VdbeAddOp(v, OP_AddImm, 1, 0);
    }

    /* End the database scan loop.
    */







|







 







|


|

>







8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
...
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
**    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
** in order to generate code for DELETE FROM statements.
**
** $Id: delete.c,v 1.94 2004/12/25 01:03:14 drh Exp $
*/
#include "sqliteInt.h"

/*
** Look up every table that is named in pSrc.  If any table is not found,
** add an error message to pParse->zErrMsg and return NULL.  If all tables
** are found, return a pointer to the last table.
................................................................................
      if( sqlite3CheckIndexCollSeq(pParse, pIdx) ){
        goto delete_from_cleanup;
      }
    }

    /* Begin the database scan
    */
    pWInfo = sqlite3WhereBegin(pParse, pTabList, pWhere, 0, 0);
    if( pWInfo==0 ) goto delete_from_cleanup;

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

    /* End the database scan loop.
    */

Changes to src/pragma.c.

7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
...
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
**    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 used to implement the PRAGMA command.
**
** $Id: pragma.c,v 1.80 2004/12/20 19:01:33 tpoindex Exp $
*/
#include "sqliteInt.h"
#include <ctype.h>

/* Ignore this whole file if pragmas are disabled
*/
#ifndef SQLITE_OMIT_PRAGMA
................................................................................
        }
        sqlite3_temp_directory = 0;
      }else{
        /* check if previous directory defined, free and alloc if needed */
        if( sqlite3_temp_directory ){
          if( strlen(sqlite3_temp_directory) < strlen(zRight) + 1){
            sqlite3FreeX(sqlite3_temp_directory);
            sqlite3_temp_directory = sqlite3Malloc( strlen(zRight) + 1 );
            if( sqlite3_temp_directory==0 ){
              goto pragma_out;
            }
            sqlite3_temp_directory[0] = '\0';
          }
        }else{
          sqlite3_temp_directory = sqlite3Malloc( strlen(zRight) + 1 );
          if( sqlite3_temp_directory==0 ){
            goto pragma_out;
          }
          sqlite3_temp_directory[0] = '\0';
        }
        /* check that directory exists and is writable */
        if( sqlite3OsIsDirWritable( zRight ) ){







|







 







|






|







7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
...
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
**    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 used to implement the PRAGMA command.
**
** $Id: pragma.c,v 1.81 2004/12/25 01:03:14 drh Exp $
*/
#include "sqliteInt.h"
#include <ctype.h>

/* Ignore this whole file if pragmas are disabled
*/
#ifndef SQLITE_OMIT_PRAGMA
................................................................................
        }
        sqlite3_temp_directory = 0;
      }else{
        /* check if previous directory defined, free and alloc if needed */
        if( sqlite3_temp_directory ){
          if( strlen(sqlite3_temp_directory) < strlen(zRight) + 1){
            sqlite3FreeX(sqlite3_temp_directory);
            sqlite3_temp_directory = sqliteMalloc( strlen(zRight) + 1 );
            if( sqlite3_temp_directory==0 ){
              goto pragma_out;
            }
            sqlite3_temp_directory[0] = '\0';
          }
        }else{
          sqlite3_temp_directory = sqliteMalloc( strlen(zRight) + 1 );
          if( sqlite3_temp_directory==0 ){
            goto pragma_out;
          }
          sqlite3_temp_directory[0] = '\0';
        }
        /* check that directory exists and is writable */
        if( sqlite3OsIsDirWritable( zRight ) ){

Changes to src/select.c.

8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
....
2545
2546
2547
2548
2549
2550
2551
2552
2553
2554
2555
2556
2557
2558
2559
**    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.218 2004/12/16 21:09:17 drh Exp $
*/
#include "sqliteInt.h"


/*
** Allocate a new Select structure and return a pointer to that
** structure.
................................................................................
    openTempIndex(pParse, p, distinct, 0);
  }else{
    distinct = -1;
  }

  /* Begin the database scan
  */
  pWInfo = sqlite3WhereBegin(pParse, pTabList, pWhere, 0,
                             pGroupBy ? 0 : &pOrderBy, p->pFetch);
  if( pWInfo==0 ) goto select_end;

  /* Use the standard inner loop if we are not dealing with
  ** aggregates
  */
  if( !isAgg ){







|







 







|







8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
....
2545
2546
2547
2548
2549
2550
2551
2552
2553
2554
2555
2556
2557
2558
2559
**    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.219 2004/12/25 01:03:14 drh Exp $
*/
#include "sqliteInt.h"


/*
** Allocate a new Select structure and return a pointer to that
** structure.
................................................................................
    openTempIndex(pParse, p, distinct, 0);
  }else{
    distinct = -1;
  }

  /* Begin the database scan
  */
  pWInfo = sqlite3WhereBegin(pParse, pTabList, pWhere,
                             pGroupBy ? 0 : &pOrderBy, p->pFetch);
  if( pWInfo==0 ) goto select_end;

  /* Use the standard inner loop if we are not dealing with
  ** aggregates
  */
  if( !isAgg ){

Changes to src/sqliteInt.h.

7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
....
1355
1356
1357
1358
1359
1360
1361
1362
1363
1364
1365
1366
1367
1368
1369
**    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.348 2004/12/19 00:11:35 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
................................................................................
void sqlite3SelectUnbind(Select*);
Table *sqlite3SrcListLookup(Parse*, SrcList*);
int sqlite3IsReadOnly(Parse*, Table*, int);
void sqlite3OpenTableForReading(Vdbe*, int iCur, Table*);
void sqlite3OpenTable(Vdbe*, int iCur, Table*, int);
void sqlite3DeleteFrom(Parse*, SrcList*, Expr*);
void sqlite3Update(Parse*, SrcList*, ExprList*, Expr*, int);
WhereInfo *sqlite3WhereBegin(Parse*, SrcList*, Expr*, int, ExprList**, Fetch*);
void sqlite3WhereEnd(WhereInfo*);
void sqlite3ExprCode(Parse*, Expr*);
void sqlite3ExprCodeAndCache(Parse*, Expr*);
int sqlite3ExprCodeExprList(Parse*, ExprList*);
void sqlite3ExprIfTrue(Parse*, Expr*, int, int);
void sqlite3ExprIfFalse(Parse*, Expr*, int, int);
void sqlite3NextedParse(Parse*, const char*, ...);







|







 







|







7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
....
1355
1356
1357
1358
1359
1360
1361
1362
1363
1364
1365
1366
1367
1368
1369
**    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.349 2004/12/25 01:03:14 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
................................................................................
void sqlite3SelectUnbind(Select*);
Table *sqlite3SrcListLookup(Parse*, SrcList*);
int sqlite3IsReadOnly(Parse*, Table*, int);
void sqlite3OpenTableForReading(Vdbe*, int iCur, Table*);
void sqlite3OpenTable(Vdbe*, int iCur, Table*, int);
void sqlite3DeleteFrom(Parse*, SrcList*, Expr*);
void sqlite3Update(Parse*, SrcList*, ExprList*, Expr*, int);
WhereInfo *sqlite3WhereBegin(Parse*, SrcList*, Expr*, ExprList**, Fetch*);
void sqlite3WhereEnd(WhereInfo*);
void sqlite3ExprCode(Parse*, Expr*);
void sqlite3ExprCodeAndCache(Parse*, Expr*);
int sqlite3ExprCodeExprList(Parse*, ExprList*);
void sqlite3ExprIfTrue(Parse*, Expr*, int, int);
void sqlite3ExprIfFalse(Parse*, Expr*, int, int);
void sqlite3NextedParse(Parse*, const char*, ...);

Changes to src/update.c.

8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
...
223
224
225
226
227
228
229
230
231
232
233
234

235
236
237
238
239
240
241
**    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.99 2004/12/07 15:41:49 drh Exp $
*/
#include "sqliteInt.h"

/*
** Process an UPDATE statement.
**
**   UPDATE OR IGNORE table_wxyz SET a=b, c=d WHERE e<5 AND f NOT NULL;
................................................................................
    pView = sqlite3SelectDup(pTab->pSelect);
    sqlite3Select(pParse, pView, SRT_TempTable, iCur, 0, 0, 0, 0);
    sqlite3SelectDelete(pView);
  }

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

  /* Remember the index of every item to be updated.
  */

  sqlite3VdbeAddOp(v, OP_ListWrite, 0, 0);

  /* End the database scan loop.
  */
  sqlite3WhereEnd(pWInfo);

  /* Initialize the count of updated rows







|







 







|




>







8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
...
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
**    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.100 2004/12/25 01:03:14 drh Exp $
*/
#include "sqliteInt.h"

/*
** Process an UPDATE statement.
**
**   UPDATE OR IGNORE table_wxyz SET a=b, c=d WHERE e<5 AND f NOT NULL;
................................................................................
    pView = sqlite3SelectDup(pTab->pSelect);
    sqlite3Select(pParse, pView, SRT_TempTable, iCur, 0, 0, 0, 0);
    sqlite3SelectDelete(pView);
  }

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

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

  /* End the database scan loop.
  */
  sqlite3WhereEnd(pWInfo);

  /* Initialize the count of updated rows

Changes to src/util.c.

10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
...
868
869
870
871
872
873
874

875
876
877
878
879
880
881
882
883
884












885
886
887
888
889
890
891
**
*************************************************************************
** Utility functions used throughout sqlite.
**
** This file contains functions for allocating memory, comparing
** strings, and stuff like that.
**
** $Id: util.c,v 1.122 2004/11/20 19:18:01 drh Exp $
*/
#include "sqliteInt.h"
#include <stdarg.h>
#include <ctype.h>

#if SQLITE_DEBUG>2 && defined(__GLIBC__)
#include <execinfo.h>
................................................................................
** Read a 32-bit variable-length integer from memory starting at p[0].
** Return the number of bytes read.  The value is stored in *v.
*/
int sqlite3GetVarint32(const unsigned char *p, u32 *v){
  u32 x;
  int n;
  unsigned char c;

  if( ((c = p[0]) & 0x80)==0 ){
    *v = c;
    return 1;
  }
  x = c & 0x7f;
  if( ((c = p[1]) & 0x80)==0 ){
    *v = (x<<7) | c;
    return 2;
  }
  x = (x<<7) | (c & 0x7f);












  n = 2;
  do{
    x = (x<<7) | ((c = p[n++])&0x7f);
  }while( (c & 0x80)!=0 && n<9 );
  *v = x;
  return n;
}







|







 







>










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







10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
...
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
**
*************************************************************************
** Utility functions used throughout sqlite.
**
** This file contains functions for allocating memory, comparing
** strings, and stuff like that.
**
** $Id: util.c,v 1.123 2004/12/25 01:03:14 drh Exp $
*/
#include "sqliteInt.h"
#include <stdarg.h>
#include <ctype.h>

#if SQLITE_DEBUG>2 && defined(__GLIBC__)
#include <execinfo.h>
................................................................................
** Read a 32-bit variable-length integer from memory starting at p[0].
** Return the number of bytes read.  The value is stored in *v.
*/
int sqlite3GetVarint32(const unsigned char *p, u32 *v){
  u32 x;
  int n;
  unsigned char c;
#if 0
  if( ((c = p[0]) & 0x80)==0 ){
    *v = c;
    return 1;
  }
  x = c & 0x7f;
  if( ((c = p[1]) & 0x80)==0 ){
    *v = (x<<7) | c;
    return 2;
  }
  x = (x<<7) | (c & 0x7f);
#else
  if( ((signed char*)p)[0]>=0 ){
    *v = p[0];
    return 1;
  }
  x = p[0] & 0x7f;
  if( ((signed char*)p)[1]>=0 ){
    *v = (x<<7) | p[1];
    return 2;
  }
  x = (x<<7) | (p[1] & 0x7f);
#endif
  n = 2;
  do{
    x = (x<<7) | ((c = p[n++])&0x7f);
  }while( (c & 0x80)!=0 && n<9 );
  *v = x;
  return n;
}

Changes to src/vdbe.c.

39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
...
637
638
639
640
641
642
643



644
645
646
647
648
649
650
....
1096
1097
1098
1099
1100
1101
1102
1103
1104
1105
1106
1107
1108
1109
1110
**
** Various scripts scan this source file in order to generate HTML
** documentation, headers files, or other derived files.  The formatting
** of the code in this file is, therefore, important.  See other comments
** in this file for details.  If in doubt, do not deviate from existing
** commenting and indentation practices when changing or adding code.
**
** $Id: vdbe.c,v 1.434 2004/12/19 00:11:35 drh Exp $
*/
#include "sqliteInt.h"
#include "os.h"
#include <ctype.h>
#include "vdbeInt.h"

/*
................................................................................
}

/* Opcode: Integer P1 * P3
**
** The integer value P1 is pushed onto the stack.  If P3 is not zero
** then it is assumed to be a string representation of the same integer.
** If P1 is zero and P3 is not zero, then the value is derived from P3.



*/
case OP_Integer: {
  pTos++;
  if( pOp->p3==0 ){
    pTos->flags = MEM_Int;
    pTos->i = pOp->p1;
  }else{
................................................................................
}

/* Opcode: CollSeq * * P3
**
** P3 is a pointer to a CollSeq struct. If the next call to a user function
** or aggregate calls sqlite3GetFuncCollSeq(), this collation sequence will
** be returned. This is used by the built-in min(), max() and nullif()
** built-in functions.
**
** The interface used by the implementation of the aforementioned functions
** to retrieve the collation sequence set by this opcode is not available
** publicly, only to user functions defined in func.c.
*/
case OP_CollSeq: {
  assert( pOp->p3type==P3_COLLSEQ );







|







 







>
>
>







 







|







39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
...
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
....
1099
1100
1101
1102
1103
1104
1105
1106
1107
1108
1109
1110
1111
1112
1113
**
** Various scripts scan this source file in order to generate HTML
** documentation, headers files, or other derived files.  The formatting
** of the code in this file is, therefore, important.  See other comments
** in this file for details.  If in doubt, do not deviate from existing
** commenting and indentation practices when changing or adding code.
**
** $Id: vdbe.c,v 1.435 2004/12/25 01:03:14 drh Exp $
*/
#include "sqliteInt.h"
#include "os.h"
#include <ctype.h>
#include "vdbeInt.h"

/*
................................................................................
}

/* Opcode: Integer P1 * P3
**
** The integer value P1 is pushed onto the stack.  If P3 is not zero
** then it is assumed to be a string representation of the same integer.
** If P1 is zero and P3 is not zero, then the value is derived from P3.
**
** If the value cannot be represented as a 32-bits then its value
** will be in P3.
*/
case OP_Integer: {
  pTos++;
  if( pOp->p3==0 ){
    pTos->flags = MEM_Int;
    pTos->i = pOp->p1;
  }else{
................................................................................
}

/* Opcode: CollSeq * * P3
**
** P3 is a pointer to a CollSeq struct. If the next call to a user function
** or aggregate calls sqlite3GetFuncCollSeq(), this collation sequence will
** be returned. This is used by the built-in min(), max() and nullif()
** functions.
**
** The interface used by the implementation of the aforementioned functions
** to retrieve the collation sequence set by this opcode is not available
** publicly, only to user functions defined in func.c.
*/
case OP_CollSeq: {
  assert( pOp->p3type==P3_COLLSEQ );

Changes to src/where.c.

12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
...
520
521
522
523
524
525
526





527
528
529
530
531
532
533
...
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
...
992
993
994
995
996
997
998
999
1000
1001
1002
1003
1004
1005
1006
....
1046
1047
1048
1049
1050
1051
1052
1053
1054
1055
1056
1057

1058
1059
1060
1061
1062
1063
1064
....
1111
1112
1113
1114
1115
1116
1117
1118
1119
1120
1121
1122
1123
1124
1125
....
1133
1134
1135
1136
1137
1138
1139
1140
1141
1142
1143
1144
1145
1146
1147
....
1283
1284
1285
1286
1287
1288
1289
1290
1291
1292
1293
1294

1295
1296
1297
1298
1299
1300
1301
....
1307
1308
1309
1310
1311
1312
1313
1314
1315
1316
1317
1318
1319
1320
1321
1322
1323
1324
1325
1326
1327
1328
....
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
1363
1364
1365
1366
1367
1368
1369
1370
1371
** 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.123 2004/12/19 00:11:35 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.
................................................................................
**        end                        |-- by sqlite3WhereEnd()
**      end                         /
**
** 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.





**
** If the WHERE clause is empty, the foreach loops must each scan their
** entire tables.  Thus a three-way join is an O(N^3) operation.  But if
** the tables have indices and there are terms in the WHERE clause that
** refer to those indices, a complete table scan can be avoided and the
** code will run much faster.  Most of the work of this routine is checking
** to see if there are indices that can be used to speed up the loop.
................................................................................
** If the where clause loops cannot be arranged to provide the correct
** output order, then the *ppOrderBy is unchanged.
*/
WhereInfo *sqlite3WhereBegin(
  Parse *pParse,        /* The parser context */
  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 */
  Fetch *pFetch         /* Initial location of cursors.  NULL otherwise */
){
  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 = 0;         /* Addresses used during code generation */
  int nExpr;           /* Number of subexpressions in the WHERE clause */
  Bitmask loopMask;    /* One bit set for each outer loop */
  int haveRowid = 0;   /* True if the ROWID is on the stack */
  ExprInfo *pTerm;     /* A single term in the WHERE clause; ptr to aExpr[] */
  ExprMaskSet maskSet; /* The expression mask set */
  int iDirectEq[BMS];  /* Term of the form ROWID==X for the N-th table */
  int iDirectLt[BMS];  /* Term of the form ROWID<X or ROWID<=X */
  int iDirectGt[BMS];  /* Term of the form ROWID>X or ROWID>=X */
  ExprInfo aExpr[101]; /* 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 */

  /* pushKey is only allowed if there is a single table (as in an INSERT or
  ** UPDATE statement)
  */
  assert( pushKey==0 || pTabList->nSrc==1 );

  /* Split the WHERE clause into separate subexpressions where each
  ** subexpression is separated by an AND operator.  If the aExpr[]
  ** array fills up, the last entry might point to an expression which
  ** contains additional unfactored AND operators.
  */
  initMaskSet(&maskSet);
  memset(aExpr, 0, sizeof(aExpr));
................................................................................
      assert( pTerm->idxLeft==iCur );
      assert( omitTable==0 );
      brk = pLevel->brk = sqlite3VdbeMakeLabel(v);
      codeEqualityTerm(pParse, pTerm, brk, pLevel);
      cont = pLevel->cont = sqlite3VdbeMakeLabel(v);
      sqlite3VdbeAddOp(v, OP_MustBeInt, 1, brk);
      sqlite3VdbeAddOp(v, OP_NotExists, iCur, brk);
      haveRowid = 0;
      pLevel->op = OP_Noop;
    }else if( pIdx!=0 && pLevel->score>3 && (pLevel->score&0x0c)==0 ){
      /* 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 = (pLevel->score+16)/32;
................................................................................
        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 ){
        haveRowid = 0;
      }else{
        sqlite3VdbeAddOp(v, OP_IdxRecno, iIdxCur, 0);
        haveRowid = 1;

      }
      pLevel->p1 = iIdxCur;
      pLevel->p2 = start;
    }else if( i<ARRAYSIZE(iDirectLt) && (iDirectLt[i]>=0 || iDirectGt[i]>=0) ){
      /* Case 3:  We have an inequality comparison against the ROWID field.
      */
      int testOp = OP_Noop;
................................................................................
      pLevel->p1 = iCur;
      pLevel->p2 = start;
      if( testOp!=OP_Noop ){
        sqlite3VdbeAddOp(v, OP_Recno, iCur, 0);
        sqlite3VdbeAddOp(v, OP_MemLoad, pLevel->iMem, 0);
        sqlite3VdbeAddOp(v, testOp, 0, brk);
      }
      haveRowid = 0;
    }else if( pIdx==0 ){
      /* Case 4:  There is no usable index.  We must do a complete
      **          scan of the entire database table.
      */
      int start;
      int opRewind;

................................................................................
        opRewind = OP_Rewind;
        pLevel->op = OP_Next;
      }
      sqlite3VdbeAddOp(v, opRewind, iCur, brk);
      start = sqlite3VdbeCurrentAddr(v);
      pLevel->p1 = iCur;
      pLevel->p2 = start;
      haveRowid = 0;
    }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.
................................................................................
        sqlite3VdbeAddOp(v, testOp, iIdxCur, brk);
        if( (leFlag && !pLevel->bRev) || (!geFlag && pLevel->bRev) ){
          sqlite3VdbeChangeP3(v, -1, "+", P3_STATIC);
        }
      }
      sqlite3VdbeAddOp(v, OP_RowKey, iIdxCur, 0);
      sqlite3VdbeAddOp(v, OP_IdxIsNull, nEqColumn + ((score&4)!=0), cont);
      if( omitTable ){
        haveRowid = 0;
      }else{
        sqlite3VdbeAddOp(v, OP_IdxRecno, iIdxCur, 0);
        haveRowid = 1;

      }

      /* Record the instruction used to terminate the loop.
      */
      pLevel->op = pLevel->bRev ? OP_Prev : OP_Next;
      pLevel->p1 = iIdxCur;
      pLevel->p2 = start;
................................................................................
    */
    for(pTerm=aExpr, j=0; j<nExpr; j++, pTerm++){
      if( pTerm->p==0 ) continue;
      if( (pTerm->prereqAll & loopMask)!=pTerm->prereqAll ) continue;
      if( pLevel->iLeftJoin && !ExprHasProperty(pTerm->p,EP_FromJoin) ){
        continue;
      }
      if( haveRowid ){
        haveRowid = 0;
        if( omitTable ){
          sqlite3VdbeAddOp(v, OP_Pop, 1, 0);
        }else{
          sqlite3VdbeAddOp(v, OP_MoveGe, iCur, 0);
        }
      }
      sqlite3ExprIfFalse(pParse, pTerm->p, cont, 1);
      pTerm->p = 0;
    }
    brk = cont;

    /* For a LEFT OUTER JOIN, generate code that will record the fact that
    ** at least one row of the right table has matched the left table.  
................................................................................
      pLevel->top = sqlite3VdbeCurrentAddr(v);
      sqlite3VdbeAddOp(v, OP_Integer, 1, 0);
      sqlite3VdbeAddOp(v, OP_MemStore, pLevel->iLeftJoin, 1);
      VdbeComment((v, "# record LEFT JOIN hit"));
      for(pTerm=aExpr, j=0; j<nExpr; j++, pTerm++){
        if( pTerm->p==0 ) continue;
        if( (pTerm->prereqAll & loopMask)!=pTerm->prereqAll ) continue;
        if( haveRowid ){
          /* Cannot happen.  "haveRowid" can only be true if pushKey is true
          ** an pushKey can only be true for DELETE and UPDATE and there are
          ** no outer joins with DELETE and UPDATE.
          */
          assert( 0 );
          haveRowid = 0;
          sqlite3VdbeAddOp(v, OP_MoveGe, iCur, 0);
        }
        sqlite3ExprIfFalse(pParse, pTerm->p, cont, 1);
        pTerm->p = 0;
      }
    }

    if( haveRowid && (i<pTabList->nSrc-1 || !pushKey) ){
      haveRowid = 0;
      if( omitTable ){
        sqlite3VdbeAddOp(v, OP_Pop, 1, 0);
      }else{
        sqlite3VdbeAddOp(v, OP_MoveGe, iCur, 0);
      }
    }    
  }
  pWInfo->iContinue = cont;
  if( pushKey && !haveRowid ){
    sqlite3VdbeAddOp(v, OP_Recno, pTabList->a[0].iCursor, 0);
  }
  freeMaskSet(&maskSet);
  return pWInfo;
}

/*
** Generate the end of the WHERE loop.  See comments on 
** sqlite3WhereBegin() for additional information.







|







 







>
>
>
>
>







 







<









<









<
<
<
<
<







 







<







 







|
<
<

<
>







 







<







 







<







 







|
<
<

<
>







 







<
<
<
<
<
<
<
<







 







<
<
<
<
<
<
<
<
<




|
<
<
<
<
<
<
<
<
<

<
<
<







12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
...
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
...
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
...
990
991
992
993
994
995
996

997
998
999
1000
1001
1002
1003
....
1043
1044
1045
1046
1047
1048
1049
1050


1051

1052
1053
1054
1055
1056
1057
1058
1059
....
1106
1107
1108
1109
1110
1111
1112

1113
1114
1115
1116
1117
1118
1119
....
1127
1128
1129
1130
1131
1132
1133

1134
1135
1136
1137
1138
1139
1140
....
1276
1277
1278
1279
1280
1281
1282
1283


1284

1285
1286
1287
1288
1289
1290
1291
1292
....
1298
1299
1300
1301
1302
1303
1304








1305
1306
1307
1308
1309
1310
1311
....
1314
1315
1316
1317
1318
1319
1320









1321
1322
1323
1324
1325









1326



1327
1328
1329
1330
1331
1332
1333
** 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.124 2004/12/25 01:03:14 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.
................................................................................
**        end                        |-- by sqlite3WhereEnd()
**      end                         /
**
** 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
** in pTabList pointing at their appropriate entries.  The [...] code
** can use OP_Column and OP_Recno opcodes on these cursors to extra
** data from the various tables of the loop.
**
** If the WHERE clause is empty, the foreach loops must each scan their
** entire tables.  Thus a three-way join is an O(N^3) operation.  But if
** the tables have indices and there are terms in the WHERE clause that
** refer to those indices, a complete table scan can be avoided and the
** code will run much faster.  Most of the work of this routine is checking
** to see if there are indices that can be used to speed up the loop.
................................................................................
** If the where clause loops cannot be arranged to provide the correct
** output order, then the *ppOrderBy is unchanged.
*/
WhereInfo *sqlite3WhereBegin(
  Parse *pParse,        /* The parser context */
  SrcList *pTabList,    /* A list of all tables to be scanned */
  Expr *pWhere,         /* The WHERE clause */

  ExprList **ppOrderBy, /* An ORDER BY clause, or NULL */
  Fetch *pFetch         /* Initial location of cursors.  NULL otherwise */
){
  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 = 0;         /* Addresses used during code generation */
  int nExpr;           /* Number of subexpressions in the WHERE clause */
  Bitmask loopMask;    /* One bit set for each outer loop */

  ExprInfo *pTerm;     /* A single term in the WHERE clause; ptr to aExpr[] */
  ExprMaskSet maskSet; /* The expression mask set */
  int iDirectEq[BMS];  /* Term of the form ROWID==X for the N-th table */
  int iDirectLt[BMS];  /* Term of the form ROWID<X or ROWID<=X */
  int iDirectGt[BMS];  /* Term of the form ROWID>X or ROWID>=X */
  ExprInfo aExpr[101]; /* 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 */






  /* Split the WHERE clause into separate subexpressions where each
  ** subexpression is separated by an AND operator.  If the aExpr[]
  ** array fills up, the last entry might point to an expression which
  ** contains additional unfactored AND operators.
  */
  initMaskSet(&maskSet);
  memset(aExpr, 0, sizeof(aExpr));
................................................................................
      assert( pTerm->idxLeft==iCur );
      assert( omitTable==0 );
      brk = pLevel->brk = sqlite3VdbeMakeLabel(v);
      codeEqualityTerm(pParse, pTerm, brk, pLevel);
      cont = pLevel->cont = sqlite3VdbeMakeLabel(v);
      sqlite3VdbeAddOp(v, OP_MustBeInt, 1, brk);
      sqlite3VdbeAddOp(v, OP_NotExists, iCur, brk);

      pLevel->op = OP_Noop;
    }else if( pIdx!=0 && pLevel->score>3 && (pLevel->score&0x0c)==0 ){
      /* 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 = (pLevel->score+16)/32;
................................................................................
        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_IdxRecno, iIdxCur, 0);

        sqlite3VdbeAddOp(v, OP_MoveGe, iCur, 0);
      }
      pLevel->p1 = iIdxCur;
      pLevel->p2 = start;
    }else if( i<ARRAYSIZE(iDirectLt) && (iDirectLt[i]>=0 || iDirectGt[i]>=0) ){
      /* Case 3:  We have an inequality comparison against the ROWID field.
      */
      int testOp = OP_Noop;
................................................................................
      pLevel->p1 = iCur;
      pLevel->p2 = start;
      if( testOp!=OP_Noop ){
        sqlite3VdbeAddOp(v, OP_Recno, iCur, 0);
        sqlite3VdbeAddOp(v, OP_MemLoad, pLevel->iMem, 0);
        sqlite3VdbeAddOp(v, testOp, 0, brk);
      }

    }else if( pIdx==0 ){
      /* Case 4:  There is no usable index.  We must do a complete
      **          scan of the entire database table.
      */
      int start;
      int opRewind;

................................................................................
        opRewind = OP_Rewind;
        pLevel->op = OP_Next;
      }
      sqlite3VdbeAddOp(v, opRewind, iCur, brk);
      start = sqlite3VdbeCurrentAddr(v);
      pLevel->p1 = iCur;
      pLevel->p2 = start;

    }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.
................................................................................
        sqlite3VdbeAddOp(v, testOp, iIdxCur, brk);
        if( (leFlag && !pLevel->bRev) || (!geFlag && pLevel->bRev) ){
          sqlite3VdbeChangeP3(v, -1, "+", P3_STATIC);
        }
      }
      sqlite3VdbeAddOp(v, OP_RowKey, iIdxCur, 0);
      sqlite3VdbeAddOp(v, OP_IdxIsNull, nEqColumn + ((score&4)!=0), cont);
      if( !omitTable ){


        sqlite3VdbeAddOp(v, OP_IdxRecno, iIdxCur, 0);

        sqlite3VdbeAddOp(v, OP_MoveGe, iCur, 0);
      }

      /* Record the instruction used to terminate the loop.
      */
      pLevel->op = pLevel->bRev ? OP_Prev : OP_Next;
      pLevel->p1 = iIdxCur;
      pLevel->p2 = start;
................................................................................
    */
    for(pTerm=aExpr, j=0; j<nExpr; j++, pTerm++){
      if( pTerm->p==0 ) continue;
      if( (pTerm->prereqAll & loopMask)!=pTerm->prereqAll ) continue;
      if( pLevel->iLeftJoin && !ExprHasProperty(pTerm->p,EP_FromJoin) ){
        continue;
      }








      sqlite3ExprIfFalse(pParse, pTerm->p, cont, 1);
      pTerm->p = 0;
    }
    brk = cont;

    /* For a LEFT OUTER JOIN, generate code that will record the fact that
    ** at least one row of the right table has matched the left table.  
................................................................................
      pLevel->top = sqlite3VdbeCurrentAddr(v);
      sqlite3VdbeAddOp(v, OP_Integer, 1, 0);
      sqlite3VdbeAddOp(v, OP_MemStore, pLevel->iLeftJoin, 1);
      VdbeComment((v, "# record LEFT JOIN hit"));
      for(pTerm=aExpr, j=0; j<nExpr; j++, pTerm++){
        if( pTerm->p==0 ) continue;
        if( (pTerm->prereqAll & loopMask)!=pTerm->prereqAll ) continue;









        sqlite3ExprIfFalse(pParse, pTerm->p, cont, 1);
        pTerm->p = 0;
      }
    }
  }









  pWInfo->iContinue = cont;



  freeMaskSet(&maskSet);
  return pWInfo;
}

/*
** Generate the end of the WHERE loop.  See comments on 
** sqlite3WhereBegin() for additional information.