/ 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 Side-by-Side Diffs Ignore Whitespace Patch

Changes to src/select.c.

     8      8   **    May you find forgiveness for yourself and forgive others.
     9      9   **    May you share freely, never taking more than you give.
    10     10   **
    11     11   *************************************************************************
    12     12   ** This file contains C code routines that are called by the parser
    13     13   ** to handle SELECT statements in SQLite.
    14     14   **
    15         -** $Id: select.c,v 1.425 2008/04/01 05:07:15 drh Exp $
           15  +** $Id: select.c,v 1.426 2008/04/10 13:33:18 drh Exp $
    16     16   */
    17     17   #include "sqliteInt.h"
    18     18   
    19     19   
    20     20   /*
    21     21   ** Delete all the content of a Select structure but do not deallocate
    22     22   ** the select structure itself.
................................................................................
  2673   2673     sqlite3SelectDelete(pSub);
  2674   2674     return 1;
  2675   2675   }
  2676   2676   #endif /* SQLITE_OMIT_VIEW */
  2677   2677   
  2678   2678   /*
  2679   2679   ** Analyze the SELECT statement passed as an argument to see if it
  2680         -** is a min() or max() query. Return ORDERBY_MIN or ORDERBY_MAX if 
         2680  +** is a min() or max() query. Return WHERE_ORDERBY_MIN or WHERE_ORDERBY_MAX if 
  2681   2681   ** it is, or 0 otherwise. At present, a query is considered to be
  2682   2682   ** a min()/max() query if:
  2683   2683   **
  2684   2684   **   1. There is a single object in the FROM clause.
  2685   2685   **
  2686   2686   **   2. There is a single expression in the result set, and it is
  2687   2687   **      either min(x) or max(x), where x is a column reference.
  2688   2688   */
  2689   2689   static int minMaxQuery(Parse *pParse, Select *p){
  2690   2690     Expr *pExpr;
  2691   2691     ExprList *pEList = p->pEList;
  2692   2692   
  2693         -  if( pEList->nExpr!=1 ) return ORDERBY_NORMAL;
         2693  +  if( pEList->nExpr!=1 ) return WHERE_ORDERBY_NORMAL;
  2694   2694     pExpr = pEList->a[0].pExpr;
  2695   2695     pEList = pExpr->pList;
  2696   2696     if( pExpr->op!=TK_AGG_FUNCTION || pEList==0 || pEList->nExpr!=1 ) return 0;
  2697         -  if( pEList->a[0].pExpr->op!=TK_AGG_COLUMN ) return ORDERBY_NORMAL;
  2698         -  if( pExpr->token.n!=3 ) return ORDERBY_NORMAL;
         2697  +  if( pEList->a[0].pExpr->op!=TK_AGG_COLUMN ) return WHERE_ORDERBY_NORMAL;
         2698  +  if( pExpr->token.n!=3 ) return WHERE_ORDERBY_NORMAL;
  2699   2699     if( sqlite3StrNICmp((char*)pExpr->token.z,"min",3)==0 ){
  2700         -    return ORDERBY_MIN;
         2700  +    return WHERE_ORDERBY_MIN;
  2701   2701     }else if( sqlite3StrNICmp((char*)pExpr->token.z,"max",3)==0 ){
  2702         -    return ORDERBY_MAX;
         2702  +    return WHERE_ORDERBY_MAX;
  2703   2703     }
  2704         -  return ORDERBY_NORMAL;
         2704  +  return WHERE_ORDERBY_NORMAL;
  2705   2705   }
  2706   2706   
  2707   2707   /*
  2708   2708   ** This routine resolves any names used in the result set of the
  2709   2709   ** supplied SELECT statement. If the SELECT statement being resolved
  2710   2710   ** is a sub-select, then pOuterNC is a pointer to the NameContext 
  2711   2711   ** of the parent SELECT.
................................................................................
  3555   3555         **     satisfying the 'ORDER BY' clause than it does in other cases.
  3556   3556         **     Refer to code and comments in where.c for details.
  3557   3557         */
  3558   3558         flag = minMaxQuery(pParse, p);
  3559   3559         if( flag ){
  3560   3560           pDel = pMinMax = sqlite3ExprListDup(db, p->pEList->a[0].pExpr->pList);
  3561   3561           if( pMinMax && !db->mallocFailed ){
  3562         -          pMinMax->a[0].sortOrder = ((flag==ORDERBY_MIN)?0:1);
         3562  +          pMinMax->a[0].sortOrder = ((flag==WHERE_ORDERBY_MIN)?0:1);
  3563   3563             pMinMax->a[0].pExpr->op = TK_COLUMN;
  3564   3564           }
  3565   3565         }
  3566   3566   
  3567   3567         /* This case runs if the aggregate has no GROUP BY clause.  The
  3568   3568         ** processing is much simpler since there is only a single row
  3569   3569         ** of output.
................................................................................
  3573   3573         if( pWInfo==0 ){
  3574   3574           sqlite3ExprListDelete(pDel);
  3575   3575           goto select_end;
  3576   3576         }
  3577   3577         updateAccumulator(pParse, &sAggInfo);
  3578   3578         if( !pMinMax && flag ){
  3579   3579           sqlite3VdbeAddOp2(v, OP_Goto, 0, pWInfo->iBreak);
  3580         -        VdbeComment((v, "%s() by index", (flag==ORDERBY_MIN?"min":"max")));
         3580  +        VdbeComment((v, "%s() by index", (flag==WHERE_ORDERBY_MIN?"min":"max")));
  3581   3581         }
  3582   3582         sqlite3WhereEnd(pWInfo);
  3583   3583         finalizeAggFunctions(pParse, &sAggInfo);
  3584   3584         pOrderBy = 0;
  3585   3585         if( pHaving ){
  3586   3586           sqlite3ExprIfFalse(pParse, pHaving, addrEnd, SQLITE_JUMPIFNULL);
  3587   3587         }

Changes to src/sqliteInt.h.

     7      7   **    May you do good and not evil.
     8      8   **    May you find forgiveness for yourself and forgive others.
     9      9   **    May you share freely, never taking more than you give.
    10     10   **
    11     11   *************************************************************************
    12     12   ** Internal interface definitions for SQLite.
    13     13   **
    14         -** @(#) $Id: sqliteInt.h,v 1.689 2008/04/05 18:41:43 drh Exp $
           14  +** @(#) $Id: sqliteInt.h,v 1.690 2008/04/10 13:33:18 drh Exp $
    15     15   */
    16     16   #ifndef _SQLITEINT_H_
    17     17   #define _SQLITEINT_H_
    18     18   
    19     19   /*
    20     20   ** Include the configuration header output by 'configure' if it was run
    21     21   ** (otherwise we get an empty default).
................................................................................
  1307   1307     /* The following field is really not part of the current level.  But
  1308   1308     ** we need a place to cache index information for each table in the
  1309   1309     ** FROM clause and the WhereLevel structure is a convenient place.
  1310   1310     */
  1311   1311     sqlite3_index_info *pIdxInfo;  /* Index info for n-th source table */
  1312   1312   };
  1313   1313   
  1314         -#define ORDERBY_NORMAL 0
  1315         -#define ORDERBY_MIN    1
  1316         -#define ORDERBY_MAX    2
         1314  +/*
         1315  +** Flags appropriate for the wflags parameter of sqlite3WhereBegin().
         1316  +*/
         1317  +#define WHERE_ORDERBY_NORMAL     0   /* No-op */
         1318  +#define WHERE_ORDERBY_MIN        1   /* ORDER BY processing for min() func */
         1319  +#define WHERE_ORDERBY_MAX        2   /* ORDER BY processing for max() func */
         1320  +#define WHERE_ONEPASS_DESIRED    4   /* Want to do one-pass UPDATE/DELETE */
  1317   1321   
  1318   1322   /*
  1319   1323   ** The WHERE clause processing routine has two halves.  The
  1320   1324   ** first part does the start of the WHERE loop and the second
  1321   1325   ** half does the tail of the WHERE loop.  An instance of
  1322   1326   ** this structure is returned by the first half and passed
  1323   1327   ** into the second half to give some continuity.
  1324   1328   */
  1325   1329   struct WhereInfo {
  1326         -  Parse *pParse;
         1330  +  Parse *pParse;       /* Parsing and code generating context */
         1331  +  u8 okOnePass;        /* Ok to use one-pass algorithm for UPDATE or DELETE */
  1327   1332     SrcList *pTabList;   /* List of tables in the join */
  1328   1333     int iTop;            /* The very beginning of the WHERE loop */
  1329   1334     int iContinue;       /* Jump here to continue with next record */
  1330   1335     int iBreak;          /* Jump here to break out of the loop */
  1331   1336     int nLevel;          /* Number of nested loop */
  1332   1337     sqlite3_index_info **apInfo;  /* Array of pointers to index info structures */
  1333   1338     WhereLevel a[1];     /* Information about each nest loop in the WHERE */

Changes to src/update.c.

     8      8   **    May you find forgiveness for yourself and forgive others.
     9      9   **    May you share freely, never taking more than you give.
    10     10   **
    11     11   *************************************************************************
    12     12   ** This file contains C code routines that are called by the parser
    13     13   ** to handle UPDATE statements.
    14     14   **
    15         -** $Id: update.c,v 1.175 2008/04/01 05:07:15 drh Exp $
           15  +** $Id: update.c,v 1.176 2008/04/10 13:33:18 drh Exp $
    16     16   */
    17     17   #include "sqliteInt.h"
    18     18   
    19     19   #ifndef SQLITE_OMIT_VIRTUALTABLE
    20     20   /* Forward declaration */
    21     21   static void updateVirtualTable(
    22     22     Parse *pParse,       /* The parsing context */
................................................................................
    99     99     int chngRowid;         /* True if the record number is being changed */
   100    100     Expr *pRowidExpr = 0;  /* Expression defining the new record number */
   101    101     int openAll = 0;       /* True if all indices need to be opened */
   102    102     AuthContext sContext;  /* The authorization context */
   103    103     NameContext sNC;       /* The name-context to resolve expressions in */
   104    104     int iDb;               /* Database containing the table being updated */
   105    105     int j1;                /* Addresses of jump instructions */
          106  +  int okOnePass;         /* True for one-pass algorithm without the FIFO */
   106    107   
   107    108   #ifndef SQLITE_OMIT_TRIGGER
   108    109     int isView;                  /* Trying to update a view */
   109    110     int triggers_exist = 0;      /* True if any row triggers exist */
   110    111   #endif
   111    112     int iBeginAfterTrigger;      /* Address of after trigger program */
   112    113     int iEndAfterTrigger;        /* Exit of after trigger program */
................................................................................
   337    338     */
   338    339     if( sqlite3ExprResolveNames(&sNC, pWhere) ){
   339    340       goto update_cleanup;
   340    341     }
   341    342   
   342    343     /* Begin the database scan
   343    344     */
   344         -  pWInfo = sqlite3WhereBegin(pParse, pTabList, pWhere, 0, 0);
          345  +  sqlite3VdbeAddOp2(v, OP_Null, 0, regOldRowid);
          346  +  pWInfo = sqlite3WhereBegin(pParse, pTabList, pWhere, 0,
          347  +                             WHERE_ONEPASS_DESIRED);
   345    348     if( pWInfo==0 ) goto update_cleanup;
          349  +  okOnePass = pWInfo->okOnePass;
   346    350   
   347    351     /* Remember the rowid of every item to be updated.
   348    352     */
   349         -  sqlite3VdbeAddOp2(v, IsVirtual(pTab) ? OP_VRowid : OP_Rowid,iCur,regOldRowid);
   350         -  sqlite3VdbeAddOp2(v, OP_FifoWrite, regOldRowid, 0);
          353  +  sqlite3VdbeAddOp2(v, IsVirtual(pTab)?OP_VRowid:OP_Rowid, iCur, regOldRowid);
          354  +  if( !okOnePass ) sqlite3VdbeAddOp2(v, OP_FifoWrite, regOldRowid, 0);
   351    355   
   352    356     /* End the database scan loop.
   353    357     */
   354    358     sqlite3WhereEnd(pWInfo);
   355    359   
   356    360     /* Initialize the count of updated rows
   357    361     */
................................................................................
   363    367     if( !isView && !IsVirtual(pTab) ){
   364    368       /* 
   365    369       ** Open every index that needs updating.  Note that if any
   366    370       ** index could potentially invoke a REPLACE conflict resolution 
   367    371       ** action, then we need to open all indices because we might need
   368    372       ** to be deleting some records.
   369    373       */
   370         -    sqlite3OpenTable(pParse, iCur, iDb, pTab, OP_OpenWrite); 
          374  +    if( !okOnePass ) sqlite3OpenTable(pParse, iCur, iDb, pTab, OP_OpenWrite); 
   371    375       if( onError==OE_Replace ){
   372    376         openAll = 1;
   373    377       }else{
   374    378         openAll = 0;
   375    379         for(pIdx=pTab->pIndex; pIdx; pIdx=pIdx->pNext){
   376    380           if( pIdx->onError==OE_Replace ){
   377    381             openAll = 1;
................................................................................
   391    395     
   392    396     /* Jump back to this point if a trigger encounters an IGNORE constraint. */
   393    397     if( triggers_exist ){
   394    398       sqlite3VdbeResolveLabel(v, addr);
   395    399     }
   396    400   
   397    401     /* Top of the update loop */
   398         -  addr = sqlite3VdbeAddOp2(v, OP_FifoRead, regOldRowid, 0);
          402  +  if( okOnePass ){
          403  +    int a1 = sqlite3VdbeAddOp1(v, OP_NotNull, regOldRowid);
          404  +    addr = sqlite3VdbeAddOp0(v, OP_Goto);
          405  +    sqlite3VdbeJumpHere(v, a1);
          406  +  }else{
          407  +    addr = sqlite3VdbeAddOp2(v, OP_FifoRead, regOldRowid, 0);
          408  +  }
   399    409   
   400    410     if( triggers_exist ){
   401    411       int regRowid;
   402    412       int regRow;
   403    413       int regCols;
   404    414   
   405    415       /* Make cursor iCur point to the record that is being updated.

Changes to src/where.c.

    12     12   ** This module contains C code that generates VDBE code used to process
    13     13   ** the WHERE clause of SQL statements.  This module is reponsible for
    14     14   ** generating the code that loops through a table looking for applicable
    15     15   ** rows.  Indices are selected and used to speed the search when doing
    16     16   ** so is applicable.  Because this module is responsible for selecting
    17     17   ** indices, you might also think of this module as the "query optimizer".
    18     18   **
    19         -** $Id: where.c,v 1.297 2008/04/01 05:07:15 drh Exp $
           19  +** $Id: where.c,v 1.298 2008/04/10 13:33:18 drh Exp $
    20     20   */
    21     21   #include "sqliteInt.h"
    22     22   
    23     23   /*
    24     24   ** The number of bits in a Bitmask.  "BMS" means "BitMask Size".
    25     25   */
    26     26   #define BMS  (sizeof(Bitmask)*8)
................................................................................
  1998   1998   ** output order, then the *ppOrderBy is unchanged.
  1999   1999   */
  2000   2000   WhereInfo *sqlite3WhereBegin(
  2001   2001     Parse *pParse,        /* The parser context */
  2002   2002     SrcList *pTabList,    /* A list of all tables to be scanned */
  2003   2003     Expr *pWhere,         /* The WHERE clause */
  2004   2004     ExprList **ppOrderBy, /* An ORDER BY clause, or NULL */
  2005         -  u8 obflag             /* One of ORDERBY_MIN, ORDERBY_MAX or ORDERBY_NORMAL */
         2005  +  u8 wflags             /* One of the WHERE_* flags defined in sqliteInt.h */
  2006   2006   ){
  2007   2007     int i;                     /* Loop counter */
  2008   2008     WhereInfo *pWInfo;         /* Will become the return value of this function */
  2009   2009     Vdbe *v = pParse->pVdbe;   /* The virtual database engine */
  2010   2010     int brk, cont = 0;         /* Addresses used during code generation */
  2011   2011     Bitmask notReady;          /* Cursors that are not yet positioned */
  2012   2012     WhereTerm *pTerm;          /* A single term in the WHERE clause */
................................................................................
  2205   2205   
  2206   2206     /* If the total query only selects a single row, then the ORDER BY
  2207   2207     ** clause is irrelevant.
  2208   2208     */
  2209   2209     if( (andFlags & WHERE_UNIQUE)!=0 && ppOrderBy ){
  2210   2210       *ppOrderBy = 0;
  2211   2211     }
         2212  +
         2213  +  /* If the caller is an UPDATE or DELETE statement that is requesting
         2214  +  ** to use a one-pass algorithm, determine if this is appropriate.
         2215  +  ** The one-pass algorithm only works if the WHERE clause constraints
         2216  +  ** the statement to update a single row.
         2217  +  */
         2218  +  assert( (wflags & WHERE_ONEPASS_DESIRED)==0 || pWInfo->nLevel==1 );
         2219  +  if( (wflags & WHERE_ONEPASS_DESIRED)!=0 && (andFlags & WHERE_UNIQUE)!=0 ){
         2220  +    pWInfo->okOnePass = 1;
         2221  +    pWInfo->a[0].flags &= ~WHERE_IDX_ONLY;
         2222  +  }
  2212   2223   
  2213   2224     /* Open all tables in the pTabList and any indices selected for
  2214   2225     ** searching those tables.
  2215   2226     */
  2216   2227     sqlite3CodeVerifySchema(pParse, -1); /* Insert the cookie verifier Goto */
  2217   2228     for(i=0, pLevel=pWInfo->a; i<pTabList->nSrc; i++, pLevel++){
  2218   2229       Table *pTab;     /* Table to open */
................................................................................
  2254   2265       if( pLevel->pBestIdx ){
  2255   2266         int iCur = pTabItem->iCursor;
  2256   2267         sqlite3VdbeAddOp4(v, OP_VOpen, iCur, 0, 0,
  2257   2268                           (const char*)pTab->pVtab, P4_VTAB);
  2258   2269       }else
  2259   2270   #endif
  2260   2271       if( (pLevel->flags & WHERE_IDX_ONLY)==0 ){
  2261         -      sqlite3OpenTable(pParse, pTabItem->iCursor, iDb, pTab, OP_OpenRead);
  2262         -      if( pTab->nCol<(sizeof(Bitmask)*8) ){
         2272  +      int op = pWInfo->okOnePass ? OP_OpenWrite : OP_OpenRead;
         2273  +      sqlite3OpenTable(pParse, pTabItem->iCursor, iDb, pTab, op);
         2274  +      if( !pWInfo->okOnePass && pTab->nCol<(sizeof(Bitmask)*8) ){
  2263   2275           Bitmask b = pTabItem->colUsed;
  2264   2276           int n = 0;
  2265   2277           for(; b; b=b>>1, n++){}
  2266   2278           sqlite3VdbeChangeP2(v, sqlite3VdbeCurrentAddr(v)-2, n);
  2267   2279           assert( n<=pTab->nCol );
  2268   2280         }
  2269   2281       }else{
................................................................................
  2492   2504         ** was passed to this function to implement a "SELECT min(x) ..." 
  2493   2505         ** query, then the caller will only allow the loop to run for
  2494   2506         ** a single iteration. This means that the first row returned
  2495   2507         ** should not have a NULL value stored in 'x'. If column 'x' is
  2496   2508         ** the first one after the nEq equality constraints in the index,
  2497   2509         ** this requires some special handling.
  2498   2510         */
  2499         -      if( (obflag==ORDERBY_MIN)
         2511  +      if( (wflags&WHERE_ORDERBY_MIN)!=0
  2500   2512          && (pLevel->flags&WHERE_ORDERBY)
  2501   2513          && (pIdx->nColumn>nEq)
  2502   2514          && (pOrderBy->a[0].pExpr->iColumn==pIdx->aiColumn[nEq])
  2503   2515         ){
  2504   2516           isMinQuery = 1;
  2505   2517         }
  2506   2518   
................................................................................
  2631   2643   
  2632   2644         /* Generate code to evaluate all constraint terms using == or IN
  2633   2645         ** and leave the values of those terms on the stack.
  2634   2646         */
  2635   2647         regBase = codeAllEqualityTerms(pParse, pLevel, &wc, notReady, 1);
  2636   2648         nxt = pLevel->nxt;
  2637   2649   
  2638         -      if( (obflag==ORDERBY_MIN)
         2650  +      if( (wflags&WHERE_ORDERBY_MIN)!=0
  2639   2651          && (pLevel->flags&WHERE_ORDERBY) 
  2640   2652          && (pIdx->nColumn>nEq)
  2641   2653          && (pOrderBy->a[0].pExpr->iColumn==pIdx->aiColumn[nEq])
  2642   2654         ){
  2643   2655           isMinQuery = 1;
  2644   2656           buildIndexProbe(pParse, nEq, pIdx, regBase, pLevel->iMem);
  2645   2657           sqlite3VdbeAddOp2(v, OP_Null, 0, regBase+nEq);
................................................................................
  2849   2861     /* Close all of the cursors that were opened by sqlite3WhereBegin.
  2850   2862     */
  2851   2863     for(i=0, pLevel=pWInfo->a; i<pTabList->nSrc; i++, pLevel++){
  2852   2864       struct SrcList_item *pTabItem = &pTabList->a[pLevel->iFrom];
  2853   2865       Table *pTab = pTabItem->pTab;
  2854   2866       assert( pTab!=0 );
  2855   2867       if( pTab->isEphem || pTab->pSelect ) continue;
  2856         -    if( (pLevel->flags & WHERE_IDX_ONLY)==0 ){
         2868  +    if( !pWInfo->okOnePass && (pLevel->flags & WHERE_IDX_ONLY)==0 ){
  2857   2869         sqlite3VdbeAddOp1(v, OP_Close, pTabItem->iCursor);
  2858   2870       }
  2859   2871       if( pLevel->pIdx!=0 ){
  2860   2872         sqlite3VdbeAddOp1(v, OP_Close, pLevel->iIdxCur);
  2861   2873       }
  2862   2874   
  2863   2875       /* If this scan uses an index, make code substitutions to read data

Changes to test/veryquick.test.

     2      2   #    May you do good and not evil.
     3      3   #    May you find forgiveness for yourself and forgive others.
     4      4   #    May you share freely, never taking more than you give.
     5      5   #
     6      6   #***********************************************************************
     7      7   # This file runs all tests.
     8      8   #
     9         -# $Id: veryquick.test,v 1.1 2008/03/31 23:51:35 drh Exp $
            9  +# $Id: veryquick.test,v 1.2 2008/04/10 13:33:18 drh Exp $
    10     10   
    11     11   proc lshift {lvar} {
    12     12     upvar $lvar l
    13     13     set ret [lindex $l 0]
    14     14     set l [lrange $l 1 end]
    15     15     return $ret
    16     16   }
................................................................................
    91     91     speed1.test
    92     92     speed1p.test
    93     93     speed2.test
    94     94     speed3.test
    95     95     speed4.test
    96     96     speed4p.test
    97     97     sqllimits1.test
           98  +  vacuum3.test
    98     99   
    99    100     tkt2686.test
   100    101     thread001.test
   101    102     thread002.test
   102    103   
   103    104     incrvacuum_ioerr.test
   104    105     autovacuum_crash.test