/ Check-in [fba97f78]
Login

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

Overview
Comment:First cut at optimizing single-row updates to use a one-pass algorithm. (CVS 4973)
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1:fba97f7874d723111e873d1470fc1a95e64f922d
User & Date: drh 2008-04-10 13:33:18
Context
2008-04-10
13:38
Document the fast that the result flag combinations to sqlite3_open_v2() that are not defined in the documentation results in undefined behavior. Ticket #3037. (CVS 4974) check-in: b390e1f7 user: drh tags: trunk
13:33
First cut at optimizing single-row updates to use a one-pass algorithm. (CVS 4973) check-in: fba97f78 user: drh tags: trunk
13:32
Add three new test cases to speed4p.test. Two of the three do single-row updates based on rowid and on primary key. (CVS 4972) check-in: a2da7f9a user: drh tags: trunk
Changes
Hide Diffs Unified Diffs Ignore Whitespace Patch

Changes to src/select.c.

8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
....
2673
2674
2675
2676
2677
2678
2679
2680
2681
2682
2683
2684
2685
2686
2687
2688
2689
2690
2691
2692
2693
2694
2695
2696
2697
2698
2699
2700
2701
2702
2703
2704
2705
2706
2707
2708
2709
2710
2711
....
3555
3556
3557
3558
3559
3560
3561
3562
3563
3564
3565
3566
3567
3568
3569
....
3573
3574
3575
3576
3577
3578
3579
3580
3581
3582
3583
3584
3585
3586
3587
**    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.425 2008/04/01 05:07:15 drh Exp $
*/
#include "sqliteInt.h"


/*
** Delete all the content of a Select structure but do not deallocate
** the select structure itself.
................................................................................
  sqlite3SelectDelete(pSub);
  return 1;
}
#endif /* SQLITE_OMIT_VIEW */

/*
** Analyze the SELECT statement passed as an argument to see if it
** is a min() or max() query. Return ORDERBY_MIN or ORDERBY_MAX if 
** it is, or 0 otherwise. At present, a query is considered to be
** a min()/max() query if:
**
**   1. There is a single object in the FROM clause.
**
**   2. There is a single expression in the result set, and it is
**      either min(x) or max(x), where x is a column reference.
*/
static int minMaxQuery(Parse *pParse, Select *p){
  Expr *pExpr;
  ExprList *pEList = p->pEList;

  if( pEList->nExpr!=1 ) return ORDERBY_NORMAL;
  pExpr = pEList->a[0].pExpr;
  pEList = pExpr->pList;
  if( pExpr->op!=TK_AGG_FUNCTION || pEList==0 || pEList->nExpr!=1 ) return 0;
  if( pEList->a[0].pExpr->op!=TK_AGG_COLUMN ) return ORDERBY_NORMAL;
  if( pExpr->token.n!=3 ) return ORDERBY_NORMAL;
  if( sqlite3StrNICmp((char*)pExpr->token.z,"min",3)==0 ){
    return ORDERBY_MIN;
  }else if( sqlite3StrNICmp((char*)pExpr->token.z,"max",3)==0 ){
    return ORDERBY_MAX;
  }
  return ORDERBY_NORMAL;
}

/*
** This routine resolves any names used in the result set of the
** supplied SELECT statement. If the SELECT statement being resolved
** is a sub-select, then pOuterNC is a pointer to the NameContext 
** of the parent SELECT.
................................................................................
      **     satisfying the 'ORDER BY' clause than it does in other cases.
      **     Refer to code and comments in where.c for details.
      */
      flag = minMaxQuery(pParse, p);
      if( flag ){
        pDel = pMinMax = sqlite3ExprListDup(db, p->pEList->a[0].pExpr->pList);
        if( pMinMax && !db->mallocFailed ){
          pMinMax->a[0].sortOrder = ((flag==ORDERBY_MIN)?0:1);
          pMinMax->a[0].pExpr->op = TK_COLUMN;
        }
      }

      /* This case runs if the aggregate has no GROUP BY clause.  The
      ** processing is much simpler since there is only a single row
      ** of output.
................................................................................
      if( pWInfo==0 ){
        sqlite3ExprListDelete(pDel);
        goto select_end;
      }
      updateAccumulator(pParse, &sAggInfo);
      if( !pMinMax && flag ){
        sqlite3VdbeAddOp2(v, OP_Goto, 0, pWInfo->iBreak);
        VdbeComment((v, "%s() by index", (flag==ORDERBY_MIN?"min":"max")));
      }
      sqlite3WhereEnd(pWInfo);
      finalizeAggFunctions(pParse, &sAggInfo);
      pOrderBy = 0;
      if( pHaving ){
        sqlite3ExprIfFalse(pParse, pHaving, addrEnd, SQLITE_JUMPIFNULL);
      }







|







 







|












|



|
|

|

|

|







 







|







 







|







8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
....
2673
2674
2675
2676
2677
2678
2679
2680
2681
2682
2683
2684
2685
2686
2687
2688
2689
2690
2691
2692
2693
2694
2695
2696
2697
2698
2699
2700
2701
2702
2703
2704
2705
2706
2707
2708
2709
2710
2711
....
3555
3556
3557
3558
3559
3560
3561
3562
3563
3564
3565
3566
3567
3568
3569
....
3573
3574
3575
3576
3577
3578
3579
3580
3581
3582
3583
3584
3585
3586
3587
**    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.426 2008/04/10 13:33:18 drh Exp $
*/
#include "sqliteInt.h"


/*
** Delete all the content of a Select structure but do not deallocate
** the select structure itself.
................................................................................
  sqlite3SelectDelete(pSub);
  return 1;
}
#endif /* SQLITE_OMIT_VIEW */

/*
** Analyze the SELECT statement passed as an argument to see if it
** is a min() or max() query. Return WHERE_ORDERBY_MIN or WHERE_ORDERBY_MAX if 
** it is, or 0 otherwise. At present, a query is considered to be
** a min()/max() query if:
**
**   1. There is a single object in the FROM clause.
**
**   2. There is a single expression in the result set, and it is
**      either min(x) or max(x), where x is a column reference.
*/
static int minMaxQuery(Parse *pParse, Select *p){
  Expr *pExpr;
  ExprList *pEList = p->pEList;

  if( pEList->nExpr!=1 ) return WHERE_ORDERBY_NORMAL;
  pExpr = pEList->a[0].pExpr;
  pEList = pExpr->pList;
  if( pExpr->op!=TK_AGG_FUNCTION || pEList==0 || pEList->nExpr!=1 ) return 0;
  if( pEList->a[0].pExpr->op!=TK_AGG_COLUMN ) return WHERE_ORDERBY_NORMAL;
  if( pExpr->token.n!=3 ) return WHERE_ORDERBY_NORMAL;
  if( sqlite3StrNICmp((char*)pExpr->token.z,"min",3)==0 ){
    return WHERE_ORDERBY_MIN;
  }else if( sqlite3StrNICmp((char*)pExpr->token.z,"max",3)==0 ){
    return WHERE_ORDERBY_MAX;
  }
  return WHERE_ORDERBY_NORMAL;
}

/*
** This routine resolves any names used in the result set of the
** supplied SELECT statement. If the SELECT statement being resolved
** is a sub-select, then pOuterNC is a pointer to the NameContext 
** of the parent SELECT.
................................................................................
      **     satisfying the 'ORDER BY' clause than it does in other cases.
      **     Refer to code and comments in where.c for details.
      */
      flag = minMaxQuery(pParse, p);
      if( flag ){
        pDel = pMinMax = sqlite3ExprListDup(db, p->pEList->a[0].pExpr->pList);
        if( pMinMax && !db->mallocFailed ){
          pMinMax->a[0].sortOrder = ((flag==WHERE_ORDERBY_MIN)?0:1);
          pMinMax->a[0].pExpr->op = TK_COLUMN;
        }
      }

      /* This case runs if the aggregate has no GROUP BY clause.  The
      ** processing is much simpler since there is only a single row
      ** of output.
................................................................................
      if( pWInfo==0 ){
        sqlite3ExprListDelete(pDel);
        goto select_end;
      }
      updateAccumulator(pParse, &sAggInfo);
      if( !pMinMax && flag ){
        sqlite3VdbeAddOp2(v, OP_Goto, 0, pWInfo->iBreak);
        VdbeComment((v, "%s() by index", (flag==WHERE_ORDERBY_MIN?"min":"max")));
      }
      sqlite3WhereEnd(pWInfo);
      finalizeAggFunctions(pParse, &sAggInfo);
      pOrderBy = 0;
      if( pHaving ){
        sqlite3ExprIfFalse(pParse, pHaving, addrEnd, SQLITE_JUMPIFNULL);
      }

Changes to src/sqliteInt.h.

7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
....
1307
1308
1309
1310
1311
1312
1313
1314
1315
1316




1317
1318
1319
1320
1321
1322
1323
1324
1325
1326

1327
1328
1329
1330
1331
1332
1333
**    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.689 2008/04/05 18:41:43 drh Exp $
*/
#ifndef _SQLITEINT_H_
#define _SQLITEINT_H_

/*
** Include the configuration header output by 'configure' if it was run
** (otherwise we get an empty default).
................................................................................
  /* The following field is really not part of the current level.  But
  ** we need a place to cache index information for each table in the
  ** FROM clause and the WhereLevel structure is a convenient place.
  */
  sqlite3_index_info *pIdxInfo;  /* Index info for n-th source table */
};

#define ORDERBY_NORMAL 0
#define ORDERBY_MIN    1
#define ORDERBY_MAX    2





/*
** The WHERE clause processing routine has two halves.  The
** first part does the start of the WHERE loop and the second
** half does the tail of the WHERE loop.  An instance of
** this structure is returned by the first half and passed
** into the second half to give some continuity.
*/
struct WhereInfo {
  Parse *pParse;

  SrcList *pTabList;   /* List of tables in the join */
  int iTop;            /* The very beginning of the WHERE loop */
  int iContinue;       /* Jump here to continue with next record */
  int iBreak;          /* Jump here to break out of the loop */
  int nLevel;          /* Number of nested loop */
  sqlite3_index_info **apInfo;  /* Array of pointers to index info structures */
  WhereLevel a[1];     /* Information about each nest loop in the WHERE */







|







 







|
|
|
>
>
>
>









|
>







7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
....
1307
1308
1309
1310
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
**    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.690 2008/04/10 13:33:18 drh Exp $
*/
#ifndef _SQLITEINT_H_
#define _SQLITEINT_H_

/*
** Include the configuration header output by 'configure' if it was run
** (otherwise we get an empty default).
................................................................................
  /* The following field is really not part of the current level.  But
  ** we need a place to cache index information for each table in the
  ** FROM clause and the WhereLevel structure is a convenient place.
  */
  sqlite3_index_info *pIdxInfo;  /* Index info for n-th source table */
};

/*
** Flags appropriate for the wflags parameter of sqlite3WhereBegin().
*/
#define WHERE_ORDERBY_NORMAL     0   /* No-op */
#define WHERE_ORDERBY_MIN        1   /* ORDER BY processing for min() func */
#define WHERE_ORDERBY_MAX        2   /* ORDER BY processing for max() func */
#define WHERE_ONEPASS_DESIRED    4   /* Want to do one-pass UPDATE/DELETE */

/*
** The WHERE clause processing routine has two halves.  The
** first part does the start of the WHERE loop and the second
** half does the tail of the WHERE loop.  An instance of
** this structure is returned by the first half and passed
** into the second half to give some continuity.
*/
struct WhereInfo {
  Parse *pParse;       /* Parsing and code generating context */
  u8 okOnePass;        /* Ok to use one-pass algorithm for UPDATE or DELETE */
  SrcList *pTabList;   /* List of tables in the join */
  int iTop;            /* The very beginning of the WHERE loop */
  int iContinue;       /* Jump here to continue with next record */
  int iBreak;          /* Jump here to break out of the loop */
  int nLevel;          /* Number of nested loop */
  sqlite3_index_info **apInfo;  /* Array of pointers to index info structures */
  WhereLevel a[1];     /* Information about each nest loop in the WHERE */

Changes to src/update.c.

8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
..
99
100
101
102
103
104
105

106
107
108
109
110
111
112
...
337
338
339
340
341
342
343

344

345

346
347
348
349
350
351
352
353
354
355
356
357
...
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
...
391
392
393
394
395
396
397





398

399
400
401
402
403
404
405
**    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.175 2008/04/01 05:07:15 drh Exp $
*/
#include "sqliteInt.h"

#ifndef SQLITE_OMIT_VIRTUALTABLE
/* Forward declaration */
static void updateVirtualTable(
  Parse *pParse,       /* The parsing context */
................................................................................
  int chngRowid;         /* True if the record number is being changed */
  Expr *pRowidExpr = 0;  /* Expression defining the new record number */
  int openAll = 0;       /* True if all indices need to be opened */
  AuthContext sContext;  /* The authorization context */
  NameContext sNC;       /* The name-context to resolve expressions in */
  int iDb;               /* Database containing the table being updated */
  int j1;                /* Addresses of jump instructions */


#ifndef SQLITE_OMIT_TRIGGER
  int isView;                  /* Trying to update a view */
  int triggers_exist = 0;      /* True if any row triggers exist */
#endif
  int iBeginAfterTrigger;      /* Address of after trigger program */
  int iEndAfterTrigger;        /* Exit of after trigger program */
................................................................................
  */
  if( sqlite3ExprResolveNames(&sNC, pWhere) ){
    goto update_cleanup;
  }

  /* Begin the database scan
  */

  pWInfo = sqlite3WhereBegin(pParse, pTabList, pWhere, 0, 0);

  if( pWInfo==0 ) goto update_cleanup;


  /* Remember the rowid of every item to be updated.
  */
  sqlite3VdbeAddOp2(v, IsVirtual(pTab) ? OP_VRowid : OP_Rowid,iCur,regOldRowid);
  sqlite3VdbeAddOp2(v, OP_FifoWrite, regOldRowid, 0);

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

  /* Initialize the count of updated rows
  */
................................................................................
  if( !isView && !IsVirtual(pTab) ){
    /* 
    ** Open every index that needs updating.  Note that if any
    ** index could potentially invoke a REPLACE conflict resolution 
    ** action, then we need to open all indices because we might need
    ** to be deleting some records.
    */
    sqlite3OpenTable(pParse, iCur, iDb, pTab, OP_OpenWrite); 
    if( onError==OE_Replace ){
      openAll = 1;
    }else{
      openAll = 0;
      for(pIdx=pTab->pIndex; pIdx; pIdx=pIdx->pNext){
        if( pIdx->onError==OE_Replace ){
          openAll = 1;
................................................................................
  
  /* Jump back to this point if a trigger encounters an IGNORE constraint. */
  if( triggers_exist ){
    sqlite3VdbeResolveLabel(v, addr);
  }

  /* Top of the update loop */





  addr = sqlite3VdbeAddOp2(v, OP_FifoRead, regOldRowid, 0);


  if( triggers_exist ){
    int regRowid;
    int regRow;
    int regCols;

    /* Make cursor iCur point to the record that is being updated.







|







 







>







 







>
|
>

>



|
|







 







|







 







>
>
>
>
>
|
>







8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
..
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
...
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
...
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
...
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
**    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.176 2008/04/10 13:33:18 drh Exp $
*/
#include "sqliteInt.h"

#ifndef SQLITE_OMIT_VIRTUALTABLE
/* Forward declaration */
static void updateVirtualTable(
  Parse *pParse,       /* The parsing context */
................................................................................
  int chngRowid;         /* True if the record number is being changed */
  Expr *pRowidExpr = 0;  /* Expression defining the new record number */
  int openAll = 0;       /* True if all indices need to be opened */
  AuthContext sContext;  /* The authorization context */
  NameContext sNC;       /* The name-context to resolve expressions in */
  int iDb;               /* Database containing the table being updated */
  int j1;                /* Addresses of jump instructions */
  int okOnePass;         /* True for one-pass algorithm without the FIFO */

#ifndef SQLITE_OMIT_TRIGGER
  int isView;                  /* Trying to update a view */
  int triggers_exist = 0;      /* True if any row triggers exist */
#endif
  int iBeginAfterTrigger;      /* Address of after trigger program */
  int iEndAfterTrigger;        /* Exit of after trigger program */
................................................................................
  */
  if( sqlite3ExprResolveNames(&sNC, pWhere) ){
    goto update_cleanup;
  }

  /* Begin the database scan
  */
  sqlite3VdbeAddOp2(v, OP_Null, 0, regOldRowid);
  pWInfo = sqlite3WhereBegin(pParse, pTabList, pWhere, 0,
                             WHERE_ONEPASS_DESIRED);
  if( pWInfo==0 ) goto update_cleanup;
  okOnePass = pWInfo->okOnePass;

  /* Remember the rowid of every item to be updated.
  */
  sqlite3VdbeAddOp2(v, IsVirtual(pTab)?OP_VRowid:OP_Rowid, iCur, regOldRowid);
  if( !okOnePass ) sqlite3VdbeAddOp2(v, OP_FifoWrite, regOldRowid, 0);

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

  /* Initialize the count of updated rows
  */
................................................................................
  if( !isView && !IsVirtual(pTab) ){
    /* 
    ** Open every index that needs updating.  Note that if any
    ** index could potentially invoke a REPLACE conflict resolution 
    ** action, then we need to open all indices because we might need
    ** to be deleting some records.
    */
    if( !okOnePass ) sqlite3OpenTable(pParse, iCur, iDb, pTab, OP_OpenWrite); 
    if( onError==OE_Replace ){
      openAll = 1;
    }else{
      openAll = 0;
      for(pIdx=pTab->pIndex; pIdx; pIdx=pIdx->pNext){
        if( pIdx->onError==OE_Replace ){
          openAll = 1;
................................................................................
  
  /* Jump back to this point if a trigger encounters an IGNORE constraint. */
  if( triggers_exist ){
    sqlite3VdbeResolveLabel(v, addr);
  }

  /* Top of the update loop */
  if( okOnePass ){
    int a1 = sqlite3VdbeAddOp1(v, OP_NotNull, regOldRowid);
    addr = sqlite3VdbeAddOp0(v, OP_Goto);
    sqlite3VdbeJumpHere(v, a1);
  }else{
    addr = sqlite3VdbeAddOp2(v, OP_FifoRead, regOldRowid, 0);
  }

  if( triggers_exist ){
    int regRowid;
    int regRow;
    int regCols;

    /* Make cursor iCur point to the record that is being updated.

Changes to src/where.c.

12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
....
1998
1999
2000
2001
2002
2003
2004
2005
2006
2007
2008
2009
2010
2011
2012
....
2205
2206
2207
2208
2209
2210
2211











2212
2213
2214
2215
2216
2217
2218
....
2254
2255
2256
2257
2258
2259
2260

2261
2262
2263
2264
2265
2266
2267
2268
2269
....
2492
2493
2494
2495
2496
2497
2498
2499
2500
2501
2502
2503
2504
2505
2506
....
2631
2632
2633
2634
2635
2636
2637
2638
2639
2640
2641
2642
2643
2644
2645
....
2849
2850
2851
2852
2853
2854
2855
2856
2857
2858
2859
2860
2861
2862
2863
** 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.297 2008/04/01 05:07:15 drh Exp $
*/
#include "sqliteInt.h"

/*
** The number of bits in a Bitmask.  "BMS" means "BitMask Size".
*/
#define BMS  (sizeof(Bitmask)*8)
................................................................................
** 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 */
  u8 obflag             /* One of ORDERBY_MIN, ORDERBY_MAX or ORDERBY_NORMAL */
){
  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 */
  Bitmask notReady;          /* Cursors that are not yet positioned */
  WhereTerm *pTerm;          /* A single term in the WHERE clause */
................................................................................

  /* If the total query only selects a single row, then the ORDER BY
  ** clause is irrelevant.
  */
  if( (andFlags & WHERE_UNIQUE)!=0 && ppOrderBy ){
    *ppOrderBy = 0;
  }












  /* Open all tables in the pTabList and any indices selected for
  ** searching those tables.
  */
  sqlite3CodeVerifySchema(pParse, -1); /* Insert the cookie verifier Goto */
  for(i=0, pLevel=pWInfo->a; i<pTabList->nSrc; i++, pLevel++){
    Table *pTab;     /* Table to open */
................................................................................
    if( pLevel->pBestIdx ){
      int iCur = pTabItem->iCursor;
      sqlite3VdbeAddOp4(v, OP_VOpen, iCur, 0, 0,
                        (const char*)pTab->pVtab, P4_VTAB);
    }else
#endif
    if( (pLevel->flags & WHERE_IDX_ONLY)==0 ){

      sqlite3OpenTable(pParse, pTabItem->iCursor, iDb, pTab, OP_OpenRead);
      if( pTab->nCol<(sizeof(Bitmask)*8) ){
        Bitmask b = pTabItem->colUsed;
        int n = 0;
        for(; b; b=b>>1, n++){}
        sqlite3VdbeChangeP2(v, sqlite3VdbeCurrentAddr(v)-2, n);
        assert( n<=pTab->nCol );
      }
    }else{
................................................................................
      ** was passed to this function to implement a "SELECT min(x) ..." 
      ** query, then the caller will only allow the loop to run for
      ** a single iteration. This means that the first row returned
      ** should not have a NULL value stored in 'x'. If column 'x' is
      ** the first one after the nEq equality constraints in the index,
      ** this requires some special handling.
      */
      if( (obflag==ORDERBY_MIN)
       && (pLevel->flags&WHERE_ORDERBY)
       && (pIdx->nColumn>nEq)
       && (pOrderBy->a[0].pExpr->iColumn==pIdx->aiColumn[nEq])
      ){
        isMinQuery = 1;
      }

................................................................................

      /* Generate code to evaluate all constraint terms using == or IN
      ** and leave the values of those terms on the stack.
      */
      regBase = codeAllEqualityTerms(pParse, pLevel, &wc, notReady, 1);
      nxt = pLevel->nxt;

      if( (obflag==ORDERBY_MIN)
       && (pLevel->flags&WHERE_ORDERBY) 
       && (pIdx->nColumn>nEq)
       && (pOrderBy->a[0].pExpr->iColumn==pIdx->aiColumn[nEq])
      ){
        isMinQuery = 1;
        buildIndexProbe(pParse, nEq, pIdx, regBase, pLevel->iMem);
        sqlite3VdbeAddOp2(v, OP_Null, 0, regBase+nEq);
................................................................................
  /* Close all of the cursors that were opened by sqlite3WhereBegin.
  */
  for(i=0, pLevel=pWInfo->a; i<pTabList->nSrc; i++, pLevel++){
    struct SrcList_item *pTabItem = &pTabList->a[pLevel->iFrom];
    Table *pTab = pTabItem->pTab;
    assert( pTab!=0 );
    if( pTab->isEphem || pTab->pSelect ) continue;
    if( (pLevel->flags & WHERE_IDX_ONLY)==0 ){
      sqlite3VdbeAddOp1(v, OP_Close, pTabItem->iCursor);
    }
    if( pLevel->pIdx!=0 ){
      sqlite3VdbeAddOp1(v, OP_Close, pLevel->iIdxCur);
    }

    /* If this scan uses an index, make code substitutions to read data







|







 







|







 







>
>
>
>
>
>
>
>
>
>
>







 







>
|
|







 







|







 







|







 







|







12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
....
1998
1999
2000
2001
2002
2003
2004
2005
2006
2007
2008
2009
2010
2011
2012
....
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
....
2265
2266
2267
2268
2269
2270
2271
2272
2273
2274
2275
2276
2277
2278
2279
2280
2281
....
2504
2505
2506
2507
2508
2509
2510
2511
2512
2513
2514
2515
2516
2517
2518
....
2643
2644
2645
2646
2647
2648
2649
2650
2651
2652
2653
2654
2655
2656
2657
....
2861
2862
2863
2864
2865
2866
2867
2868
2869
2870
2871
2872
2873
2874
2875
** 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.298 2008/04/10 13:33:18 drh Exp $
*/
#include "sqliteInt.h"

/*
** The number of bits in a Bitmask.  "BMS" means "BitMask Size".
*/
#define BMS  (sizeof(Bitmask)*8)
................................................................................
** 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 */
  u8 wflags             /* One of the WHERE_* flags defined in sqliteInt.h */
){
  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 */
  Bitmask notReady;          /* Cursors that are not yet positioned */
  WhereTerm *pTerm;          /* A single term in the WHERE clause */
................................................................................

  /* If the total query only selects a single row, then the ORDER BY
  ** clause is irrelevant.
  */
  if( (andFlags & WHERE_UNIQUE)!=0 && ppOrderBy ){
    *ppOrderBy = 0;
  }

  /* If the caller is an UPDATE or DELETE statement that is requesting
  ** to use a one-pass algorithm, determine if this is appropriate.
  ** The one-pass algorithm only works if the WHERE clause constraints
  ** the statement to update a single row.
  */
  assert( (wflags & WHERE_ONEPASS_DESIRED)==0 || pWInfo->nLevel==1 );
  if( (wflags & WHERE_ONEPASS_DESIRED)!=0 && (andFlags & WHERE_UNIQUE)!=0 ){
    pWInfo->okOnePass = 1;
    pWInfo->a[0].flags &= ~WHERE_IDX_ONLY;
  }

  /* Open all tables in the pTabList and any indices selected for
  ** searching those tables.
  */
  sqlite3CodeVerifySchema(pParse, -1); /* Insert the cookie verifier Goto */
  for(i=0, pLevel=pWInfo->a; i<pTabList->nSrc; i++, pLevel++){
    Table *pTab;     /* Table to open */
................................................................................
    if( pLevel->pBestIdx ){
      int iCur = pTabItem->iCursor;
      sqlite3VdbeAddOp4(v, OP_VOpen, iCur, 0, 0,
                        (const char*)pTab->pVtab, P4_VTAB);
    }else
#endif
    if( (pLevel->flags & WHERE_IDX_ONLY)==0 ){
      int op = pWInfo->okOnePass ? OP_OpenWrite : OP_OpenRead;
      sqlite3OpenTable(pParse, pTabItem->iCursor, iDb, pTab, op);
      if( !pWInfo->okOnePass && pTab->nCol<(sizeof(Bitmask)*8) ){
        Bitmask b = pTabItem->colUsed;
        int n = 0;
        for(; b; b=b>>1, n++){}
        sqlite3VdbeChangeP2(v, sqlite3VdbeCurrentAddr(v)-2, n);
        assert( n<=pTab->nCol );
      }
    }else{
................................................................................
      ** was passed to this function to implement a "SELECT min(x) ..." 
      ** query, then the caller will only allow the loop to run for
      ** a single iteration. This means that the first row returned
      ** should not have a NULL value stored in 'x'. If column 'x' is
      ** the first one after the nEq equality constraints in the index,
      ** this requires some special handling.
      */
      if( (wflags&WHERE_ORDERBY_MIN)!=0
       && (pLevel->flags&WHERE_ORDERBY)
       && (pIdx->nColumn>nEq)
       && (pOrderBy->a[0].pExpr->iColumn==pIdx->aiColumn[nEq])
      ){
        isMinQuery = 1;
      }

................................................................................

      /* Generate code to evaluate all constraint terms using == or IN
      ** and leave the values of those terms on the stack.
      */
      regBase = codeAllEqualityTerms(pParse, pLevel, &wc, notReady, 1);
      nxt = pLevel->nxt;

      if( (wflags&WHERE_ORDERBY_MIN)!=0
       && (pLevel->flags&WHERE_ORDERBY) 
       && (pIdx->nColumn>nEq)
       && (pOrderBy->a[0].pExpr->iColumn==pIdx->aiColumn[nEq])
      ){
        isMinQuery = 1;
        buildIndexProbe(pParse, nEq, pIdx, regBase, pLevel->iMem);
        sqlite3VdbeAddOp2(v, OP_Null, 0, regBase+nEq);
................................................................................
  /* Close all of the cursors that were opened by sqlite3WhereBegin.
  */
  for(i=0, pLevel=pWInfo->a; i<pTabList->nSrc; i++, pLevel++){
    struct SrcList_item *pTabItem = &pTabList->a[pLevel->iFrom];
    Table *pTab = pTabItem->pTab;
    assert( pTab!=0 );
    if( pTab->isEphem || pTab->pSelect ) continue;
    if( !pWInfo->okOnePass && (pLevel->flags & WHERE_IDX_ONLY)==0 ){
      sqlite3VdbeAddOp1(v, OP_Close, pTabItem->iCursor);
    }
    if( pLevel->pIdx!=0 ){
      sqlite3VdbeAddOp1(v, OP_Close, pLevel->iIdxCur);
    }

    /* If this scan uses an index, make code substitutions to read data

Changes to test/veryquick.test.

2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
..
91
92
93
94
95
96
97

98
99
100
101
102
103
104
#    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 runs all tests.
#
# $Id: veryquick.test,v 1.1 2008/03/31 23:51:35 drh Exp $

proc lshift {lvar} {
  upvar $lvar l
  set ret [lindex $l 0]
  set l [lrange $l 1 end]
  return $ret
}
................................................................................
  speed1.test
  speed1p.test
  speed2.test
  speed3.test
  speed4.test
  speed4p.test
  sqllimits1.test


  tkt2686.test
  thread001.test
  thread002.test

  incrvacuum_ioerr.test
  autovacuum_crash.test







|







 







>







2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
..
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
#    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 runs all tests.
#
# $Id: veryquick.test,v 1.2 2008/04/10 13:33:18 drh Exp $

proc lshift {lvar} {
  upvar $lvar l
  set ret [lindex $l 0]
  set l [lrange $l 1 end]
  return $ret
}
................................................................................
  speed1.test
  speed1p.test
  speed2.test
  speed3.test
  speed4.test
  speed4p.test
  sqllimits1.test
  vacuum3.test

  tkt2686.test
  thread001.test
  thread002.test

  incrvacuum_ioerr.test
  autovacuum_crash.test