/ Check-in [ad4a6b1a]
Login

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

Overview
Comment:Change BtreeMoveto so that it can be biased to the right or to the center. Use a right bias when appending and a center bias when searching. This gives about a 15% reduction in calls to sqlite3VdbeRecordCompare. (CVS 3741)
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1: ad4a6b1a91bcefd8a4c75e8dc99c1153c72c31a3
User & Date: drh 2007-03-29 05:51:49
Context
2007-03-29
12:19
Explicitly test some error cases that up until now have not been checked. (CVS 3742) check-in: f26b0141 user: danielk1977 tags: trunk
05:51
Change BtreeMoveto so that it can be biased to the right or to the center. Use a right bias when appending and a center bias when searching. This gives about a 15% reduction in calls to sqlite3VdbeRecordCompare. (CVS 3741) check-in: ad4a6b1a user: drh tags: trunk
04:43
Bias the b-tree binary search toward the high end. The common case is to append data and this heuristic makes append run much faster because there are fewer comparisons. (CVS 3740) check-in: a9877f61 user: drh tags: trunk
Changes
Hide Diffs Side-by-Side Diffs Ignore Whitespace Patch

Changes to src/analyze.c.

     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   ** This file contains code associated with the ANALYZE command.
    13     13   **
    14         -** @(#) $Id: analyze.c,v 1.16 2006/01/10 17:58:23 danielk1977 Exp $
           14  +** @(#) $Id: analyze.c,v 1.17 2007/03/29 05:51:49 drh Exp $
    15     15   */
    16     16   #ifndef SQLITE_OMIT_ANALYZE
    17     17   #include "sqliteInt.h"
    18     18   
    19     19   /*
    20     20   ** This routine generates code that opens the sqlite_stat1 table on cursor
    21     21   ** iStatCur.
................................................................................
   207    207         if( i==nCol-1 ){
   208    208           sqlite3VdbeAddOp(v, OP_Concat, nCol*2-1, 0);
   209    209         }else{
   210    210           sqlite3VdbeAddOp(v, OP_Dup, 1, 0);
   211    211         }
   212    212       }
   213    213       sqlite3VdbeOp3(v, OP_MakeRecord, 3, 0, "aaa", 0);
   214         -    sqlite3VdbeAddOp(v, OP_Insert, iStatCur, 0);
          214  +    sqlite3VdbeAddOp(v, OP_Insert, iStatCur, OPFLAG_APPEND);
   215    215       sqlite3VdbeJumpHere(v, addr);
   216    216     }
   217    217   }
   218    218   
   219    219   /*
   220    220   ** Generate code that will cause the most recent index analysis to
   221    221   ** be laoded into internal hash tables where is can be used.

Changes to src/btree.c.

     5      5   ** a legal notice, here is a blessing:
     6      6   **
     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         -** $Id: btree.c,v 1.344 2007/03/29 04:43:26 drh Exp $
           12  +** $Id: btree.c,v 1.345 2007/03/29 05:51:49 drh Exp $
    13     13   **
    14     14   ** This file implements a external (disk-based) database using BTrees.
    15     15   ** For a detailed discussion of BTrees, refer to
    16     16   **
    17     17   **     Donald E. Knuth, THE ART OF COMPUTER PROGRAMMING, Volume 3:
    18     18   **     "Sorting And Searching", pages 473-480. Addison-Wesley
    19     19   **     Publishing Company, Reading, Massachusetts.
................................................................................
   724    724   ** and the cursor state set to CURSOR_INVALID.
   725    725   */
   726    726   static int restoreOrClearCursorPositionX(BtCursor *pCur, int doSeek){
   727    727     int rc = SQLITE_OK;
   728    728     assert( pCur->eState==CURSOR_REQUIRESEEK );
   729    729     pCur->eState = CURSOR_INVALID;
   730    730     if( doSeek ){
   731         -    rc = sqlite3BtreeMoveto(pCur, pCur->pKey, pCur->nKey, &pCur->skip);
          731  +    rc = sqlite3BtreeMoveto(pCur, pCur->pKey, pCur->nKey, 0, &pCur->skip);
   732    732     }
   733    733     if( rc==SQLITE_OK ){
   734    734       sqliteFree(pCur->pKey);
   735    735       pCur->pKey = 0;
   736    736       assert( CURSOR_VALID==pCur->eState || CURSOR_INVALID==pCur->eState );
   737    737     }
   738    738     return rc;
................................................................................
  3299   3299   **
  3300   3300   **     *pRes==0     The cursor is left pointing at an entry that
  3301   3301   **                  exactly matches pKey.
  3302   3302   **
  3303   3303   **     *pRes>0      The cursor is left pointing at an entry that
  3304   3304   **                  is larger than pKey.
  3305   3305   */
  3306         -int sqlite3BtreeMoveto(BtCursor *pCur, const void *pKey, i64 nKey, int *pRes){
         3306  +int sqlite3BtreeMoveto(
         3307  +  BtCursor *pCur,        /* The cursor to be moved */
         3308  +  const void *pKey,      /* The key content for indices.  Not used by tables */
         3309  +  i64 nKey,              /* Size of pKey.  Or the key for tables */
         3310  +  int biasRight,         /* If true, bias the search to the high end */
         3311  +  int *pRes              /* Search result flag */
         3312  +){
  3307   3313     int rc;
  3308   3314     rc = moveToRoot(pCur);
  3309   3315     if( rc ) return rc;
  3310   3316     assert( pCur->pPage );
  3311   3317     assert( pCur->pPage->isInit );
  3312   3318     if( pCur->eState==CURSOR_INVALID ){
  3313   3319       *pRes = -1;
................................................................................
  3320   3326       MemPage *pPage = pCur->pPage;
  3321   3327       int c = -1;  /* pRes return if table is empty must be -1 */
  3322   3328       lwr = 0;
  3323   3329       upr = pPage->nCell-1;
  3324   3330       if( !pPage->intKey && pKey==0 ){
  3325   3331         return SQLITE_CORRUPT_BKPT;
  3326   3332       }
  3327         -    pCur->idx = upr;
         3333  +    if( biasRight ){
         3334  +      pCur->idx = upr;
         3335  +    }else{
         3336  +      pCur->idx = (upr+lwr)/2;
         3337  +    }
  3328   3338       if( lwr<=upr ) for(;;){
  3329   3339         void *pCellKey;
  3330   3340         i64 nCellKey;
  3331   3341         pCur->info.nSize = 0;
  3332   3342         if( pPage->intKey ){
  3333   3343           u8 *pCell;
  3334   3344           pCell = findCell(pPage, pCur->idx) + pPage->childPtrSize;
................................................................................
  5178   5188   **
  5179   5189   ** For an INTKEY table, only the nKey value of the key is used.  pKey is
  5180   5190   ** ignored.  For a ZERODATA table, the pData and nData are both ignored.
  5181   5191   */
  5182   5192   int sqlite3BtreeInsert(
  5183   5193     BtCursor *pCur,                /* Insert data into the table of this cursor */
  5184   5194     const void *pKey, i64 nKey,    /* The key of the new record */
  5185         -  const void *pData, int nData   /* The data of the new record */
         5195  +  const void *pData, int nData,  /* The data of the new record */
         5196  +  int appendBias                 /* True if this is likely an append */
  5186   5197   ){
  5187   5198     int rc;
  5188   5199     int loc;
  5189   5200     int szNew;
  5190   5201     MemPage *pPage;
  5191   5202     BtShared *pBt = pCur->pBtree->pBt;
  5192   5203     unsigned char *oldCell;
................................................................................
  5204   5215       return SQLITE_LOCKED; /* The table pCur points to has a read lock */
  5205   5216     }
  5206   5217   
  5207   5218     /* Save the positions of any other cursors open on this table */
  5208   5219     restoreOrClearCursorPosition(pCur, 0);
  5209   5220     if( 
  5210   5221       SQLITE_OK!=(rc = saveAllCursors(pBt, pCur->pgnoRoot, pCur)) ||
  5211         -    SQLITE_OK!=(rc = sqlite3BtreeMoveto(pCur, pKey, nKey, &loc))
         5222  +    SQLITE_OK!=(rc = sqlite3BtreeMoveto(pCur, pKey, nKey, appendBias, &loc))
  5212   5223     ){
  5213   5224       return rc;
  5214   5225     }
  5215   5226   
  5216   5227     pPage = pCur->pPage;
  5217   5228     assert( pPage->intKey || nKey>=0 );
  5218   5229     assert( pPage->leaf || !pPage->leafData );

Changes to src/btree.h.

     9      9   **    May you share freely, never taking more than you give.
    10     10   **
    11     11   *************************************************************************
    12     12   ** This header file defines the interface that the sqlite B-Tree file
    13     13   ** subsystem.  See comments in the source code for a detailed description
    14     14   ** of what each interface routine does.
    15     15   **
    16         -** @(#) $Id: btree.h,v 1.72 2007/01/27 02:24:55 drh Exp $
           16  +** @(#) $Id: btree.h,v 1.73 2007/03/29 05:51:49 drh Exp $
    17     17   */
    18     18   #ifndef _BTREE_H_
    19     19   #define _BTREE_H_
    20     20   
    21     21   /* TODO: This definition is just included so other modules compile. It
    22     22   ** needs to be revisited.
    23     23   */
................................................................................
   110    110   void sqlite3BtreeSetCompare(
   111    111     BtCursor *,
   112    112     int(*)(void*,int,const void*,int,const void*),
   113    113     void*
   114    114   );
   115    115   
   116    116   int sqlite3BtreeCloseCursor(BtCursor*);
   117         -int sqlite3BtreeMoveto(BtCursor*, const void *pKey, i64 nKey, int *pRes);
          117  +int sqlite3BtreeMoveto(BtCursor*,const void *pKey,i64 nKey,int bias,int *pRes);
   118    118   int sqlite3BtreeDelete(BtCursor*);
   119    119   int sqlite3BtreeInsert(BtCursor*, const void *pKey, i64 nKey,
   120         -                                  const void *pData, int nData);
          120  +                                  const void *pData, int nData, int bias);
   121    121   int sqlite3BtreeFirst(BtCursor*, int *pRes);
   122    122   int sqlite3BtreeLast(BtCursor*, int *pRes);
   123    123   int sqlite3BtreeNext(BtCursor*, int *pRes);
   124    124   int sqlite3BtreeEof(BtCursor*);
   125    125   int sqlite3BtreeFlags(BtCursor*);
   126    126   int sqlite3BtreePrevious(BtCursor*, int *pRes);
   127    127   int sqlite3BtreeKeySize(BtCursor*, i64 *pSize);

Changes to src/build.c.

    18     18   **     CREATE INDEX
    19     19   **     DROP INDEX
    20     20   **     creating ID lists
    21     21   **     BEGIN TRANSACTION
    22     22   **     COMMIT
    23     23   **     ROLLBACK
    24     24   **
    25         -** $Id: build.c,v 1.417 2007/03/27 13:36:37 drh Exp $
           25  +** $Id: build.c,v 1.418 2007/03/29 05:51:49 drh Exp $
    26     26   */
    27     27   #include "sqliteInt.h"
    28     28   #include <ctype.h>
    29     29   
    30     30   /*
    31     31   ** This routine is called when a new SQL statement is beginning to
    32     32   ** be parsed.  Initialize the pParse structure as needed.
................................................................................
   883    883       {
   884    884         sqlite3VdbeAddOp(v, OP_CreateTable, iDb, 0);
   885    885       }
   886    886       sqlite3OpenMasterTable(pParse, iDb);
   887    887       sqlite3VdbeAddOp(v, OP_NewRowid, 0, 0);
   888    888       sqlite3VdbeAddOp(v, OP_Dup, 0, 0);
   889    889       sqlite3VdbeAddOp(v, OP_Null, 0, 0);
   890         -    sqlite3VdbeAddOp(v, OP_Insert, 0, 0);
          890  +    sqlite3VdbeAddOp(v, OP_Insert, 0, OPFLAG_APPEND);
   891    891       sqlite3VdbeAddOp(v, OP_Close, 0, 0);
   892    892       sqlite3VdbeAddOp(v, OP_Pull, 1, 0);
   893    893     }
   894    894   
   895    895     /* Normal (non-error) return. */
   896    896     return;
   897    897   

Changes to src/insert.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 INSERT statements in SQLite.
    14     14   **
    15         -** $Id: insert.c,v 1.179 2007/03/29 00:08:25 drh Exp $
           15  +** $Id: insert.c,v 1.180 2007/03/29 05:51:49 drh Exp $
    16     16   */
    17     17   #include "sqliteInt.h"
    18     18   
    19     19   /*
    20     20   ** Set P3 of the most recently inserted opcode to a column affinity
    21     21   ** string for index pIdx. A column affinity string has one character
    22     22   ** for each column in the table, according to the affinity of the column:
................................................................................
   201    201       sqlite3VdbeAddOp(v, OP_MemLoad, memId-1, 0);
   202    202       sqlite3VdbeAddOp(v, OP_NotNull, -1, addr+7);
   203    203       sqlite3VdbeAddOp(v, OP_Pop, 1, 0);
   204    204       sqlite3VdbeAddOp(v, OP_NewRowid, iCur, 0);
   205    205       sqlite3VdbeOp3(v, OP_String8, 0, 0, pTab->zName, 0);
   206    206       sqlite3VdbeAddOp(v, OP_MemLoad, memId, 0);
   207    207       sqlite3VdbeAddOp(v, OP_MakeRecord, 2, 0);
   208         -    sqlite3VdbeAddOp(v, OP_Insert, iCur, 0);
          208  +    sqlite3VdbeAddOp(v, OP_Insert, iCur, OPFLAG_APPEND);
   209    209       sqlite3VdbeAddOp(v, OP_Close, iCur, 0);
   210    210     }
   211    211   }
   212    212   #else
   213    213   /*
   214    214   ** If SQLITE_OMIT_AUTOINCREMENT is defined, then the three routines
   215    215   ** above are all no-ops
................................................................................
   342    342     int iSelectLoop = 0;  /* Address of code that implements the SELECT */
   343    343     int iCleanup = 0;     /* Address of the cleanup code */
   344    344     int iInsertBlock = 0; /* Address of the subroutine used to insert data */
   345    345     int iCntMem = 0;      /* Memory cell used for the row counter */
   346    346     int newIdx = -1;      /* Cursor for the NEW table */
   347    347     Db *pDb;              /* The database containing table being inserted into */
   348    348     int counterMem = 0;   /* Memory cell holding AUTOINCREMENT counter */
          349  +  int appendFlag = 0;   /* True if the insert is likely to be an append */
   349    350     int iDb;
   350    351   
   351    352   #ifndef SQLITE_OMIT_TRIGGER
   352    353     int isView;                 /* True if attempting to insert into a view */
   353    354     int triggers_exist = 0;     /* True if there are FOR EACH ROW triggers */
   354    355   #endif
   355    356   
................................................................................
   485    486         ** the result.  Store the result in a temporary table
   486    487         */
   487    488         srcTab = pParse->nTab++;
   488    489         sqlite3VdbeResolveLabel(v, iInsertBlock);
   489    490         sqlite3VdbeAddOp(v, OP_MakeRecord, nColumn, 0);
   490    491         sqlite3VdbeAddOp(v, OP_NewRowid, srcTab, 0);
   491    492         sqlite3VdbeAddOp(v, OP_Pull, 1, 0);
   492         -      sqlite3VdbeAddOp(v, OP_Insert, srcTab, 0);
          493  +      sqlite3VdbeAddOp(v, OP_Insert, srcTab, OPFLAG_APPEND);
   493    494         sqlite3VdbeAddOp(v, OP_Return, 0, 0);
   494    495   
   495    496         /* The following code runs first because the GOTO at the very top
   496    497         ** of the program jumps to it.  Create the temporary table, then jump
   497    498         ** back up and execute the SELECT code above.
   498    499         */
   499    500         sqlite3VdbeJumpHere(v, iInitCode);
................................................................................
   697    698       }
   698    699       if( keyColumn>=0 ){
   699    700         if( useTempTable ){
   700    701           sqlite3VdbeAddOp(v, OP_Column, srcTab, keyColumn);
   701    702         }else if( pSelect ){
   702    703           sqlite3VdbeAddOp(v, OP_Dup, nColumn - keyColumn - 1, 1);
   703    704         }else{
          705  +        VdbeOp *pOp;
   704    706           sqlite3ExprCode(pParse, pList->a[keyColumn].pExpr);
          707  +        pOp = sqlite3VdbeGetOp(v, sqlite3VdbeCurrentAddr(v) - 1);
          708  +        if( pOp->opcode==OP_Null ){
          709  +          appendFlag = 1;
          710  +          pOp->opcode = OP_NewRowid;
          711  +          pOp->p1 = base;
          712  +          pOp->p2 = counterMem;
          713  +        }
   705    714         }
   706    715         /* If the PRIMARY KEY expression is NULL, then use OP_NewRowid
   707    716         ** to generate a unique primary key value.
   708    717         */
   709         -      sqlite3VdbeAddOp(v, OP_NotNull, -1, sqlite3VdbeCurrentAddr(v)+3);
   710         -      sqlite3VdbeAddOp(v, OP_Pop, 1, 0);
   711         -      sqlite3VdbeAddOp(v, OP_NewRowid, base, counterMem);
   712         -      sqlite3VdbeAddOp(v, OP_MustBeInt, 0, 0);
          718  +      if( !appendFlag ){
          719  +        sqlite3VdbeAddOp(v, OP_NotNull, -1, sqlite3VdbeCurrentAddr(v)+3);
          720  +        sqlite3VdbeAddOp(v, OP_Pop, 1, 0);
          721  +        sqlite3VdbeAddOp(v, OP_NewRowid, base, counterMem);
          722  +        sqlite3VdbeAddOp(v, OP_MustBeInt, 0, 0);
          723  +      }
   713    724       }else if( IsVirtual(pTab) ){
   714    725         sqlite3VdbeAddOp(v, OP_Null, 0, 0);
   715    726       }else{
   716    727         sqlite3VdbeAddOp(v, OP_NewRowid, base, counterMem);
          728  +      appendFlag = 1;
   717    729       }
   718    730       autoIncStep(pParse, counterMem);
   719    731   
   720    732       /* Push onto the stack, data for all columns of the new entry, beginning
   721    733       ** with the first column.
   722    734       */
   723    735       for(i=0; i<pTab->nCol; i++){
................................................................................
   757    769                        (const char*)pTab->pVtab, P3_VTAB);
   758    770       }else
   759    771   #endif
   760    772       {
   761    773         sqlite3GenerateConstraintChecks(pParse, pTab, base, 0, keyColumn>=0,
   762    774                                        0, onError, endOfLoop);
   763    775         sqlite3CompleteInsertion(pParse, pTab, base, 0,0,0,
   764         -                            (triggers_exist & TRIGGER_AFTER)!=0 ? newIdx : -1);
          776  +                            (triggers_exist & TRIGGER_AFTER)!=0 ? newIdx : -1,
          777  +                            appendFlag);
   765    778       }
   766    779     }
   767    780   
   768    781     /* Update the count of rows that are inserted
   769    782     */
   770    783     if( (db->flags & SQLITE_CountRows)!=0 ){
   771    784       sqlite3VdbeAddOp(v, OP_MemIncr, 1, iCntMem);
................................................................................
  1168   1181   void sqlite3CompleteInsertion(
  1169   1182     Parse *pParse,      /* The parser context */
  1170   1183     Table *pTab,        /* the table into which we are inserting */
  1171   1184     int base,           /* Index of a read/write cursor pointing at pTab */
  1172   1185     char *aIdxUsed,     /* Which indices are used.  NULL means all are used */
  1173   1186     int rowidChng,      /* True if the record number will change */
  1174   1187     int isUpdate,       /* True for UPDATE, False for INSERT */
  1175         -  int newIdx          /* Index of NEW table for triggers.  -1 if none */
         1188  +  int newIdx,         /* Index of NEW table for triggers.  -1 if none */
         1189  +  int appendBias      /* True if this is likely to be an append */
  1176   1190   ){
  1177   1191     int i;
  1178   1192     Vdbe *v;
  1179   1193     int nIdx;
  1180   1194     Index *pIdx;
  1181   1195     int pik_flags;
  1182   1196   
................................................................................
  1199   1213   #endif
  1200   1214     if( pParse->nested ){
  1201   1215       pik_flags = 0;
  1202   1216     }else{
  1203   1217       pik_flags = OPFLAG_NCHANGE;
  1204   1218       pik_flags |= (isUpdate?OPFLAG_ISUPDATE:OPFLAG_LASTROWID);
  1205   1219     }
         1220  +  if( appendBias ){
         1221  +    pik_flags |= OPFLAG_APPEND;
         1222  +  }
  1206   1223     sqlite3VdbeAddOp(v, OP_Insert, base, pik_flags);
  1207   1224     if( !pParse->nested ){
  1208   1225       sqlite3VdbeChangeP3(v, -1, pTab->zName, P3_STATIC);
  1209   1226     }
  1210   1227     
  1211   1228     if( isUpdate && rowidChng ){
  1212   1229       sqlite3VdbeAddOp(v, OP_Pop, 1, 0);
................................................................................
  1511   1528                         "PRIMARY KEY must be unique", P3_STATIC);
  1512   1529       sqlite3VdbeJumpHere(v, addr2);
  1513   1530       autoIncStep(pParse, counterMem);
  1514   1531     }else{
  1515   1532       addr1 = sqlite3VdbeAddOp(v, OP_Rowid, iSrc, 0);
  1516   1533     }
  1517   1534     sqlite3VdbeAddOp(v, OP_RowData, iSrc, 0);
  1518         -  sqlite3VdbeOp3(v, OP_Insert, iDest, OPFLAG_NCHANGE|OPFLAG_LASTROWID,
         1535  +  sqlite3VdbeOp3(v, OP_Insert, iDest,
         1536  +                    OPFLAG_NCHANGE|OPFLAG_LASTROWID|OPFLAG_APPEND,
  1519   1537                       pDest->zName, 0);
  1520   1538     sqlite3VdbeAddOp(v, OP_Next, iSrc, addr1);
  1521   1539     autoIncEnd(pParse, iDbDest, pDest, counterMem);
  1522   1540     for(pDestIdx=pDest->pIndex; pDestIdx; pDestIdx=pDestIdx->pNext){
  1523   1541       for(pSrcIdx=pSrc->pIndex; pSrcIdx; pSrcIdx=pSrcIdx->pNext){
  1524   1542         if( xferCompatibleIndex(pDestIdx, pSrcIdx) ) break;
  1525   1543       }
................................................................................
  1541   1559       if( pDestIdx->onError!=OE_None ){
  1542   1560         sqlite3VdbeAddOp(v, OP_MemLoad, memRowid, 0);
  1543   1561         addr2 = sqlite3VdbeAddOp(v, OP_IsUnique, iDest, 0);
  1544   1562         sqlite3VdbeOp3(v, OP_Halt, SQLITE_CONSTRAINT, onError, 
  1545   1563                       "UNIQUE constraint failed", P3_STATIC);
  1546   1564         sqlite3VdbeJumpHere(v, addr2);
  1547   1565       }
  1548         -    sqlite3VdbeAddOp(v, OP_IdxInsert, iDest, 0);
         1566  +    sqlite3VdbeAddOp(v, OP_IdxInsert, iDest, 1);
  1549   1567       sqlite3VdbeAddOp(v, OP_Next, iSrc, addr1+1);
  1550   1568       sqlite3VdbeJumpHere(v, addr1);
  1551   1569     }
  1552   1570     sqlite3VdbeJumpHere(v, emptySrcTest);
  1553   1571     sqlite3VdbeAddOp(v, OP_Close, iSrc, 0);
  1554   1572     sqlite3VdbeAddOp(v, OP_Close, iDest, 0);
  1555   1573     if( emptyDestTest ){

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.330 2007/03/02 07:27:00 danielk1977 Exp $
           15  +** $Id: select.c,v 1.331 2007/03/29 05:51:49 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.
................................................................................
   531    531       case SRT_EphemTab: {
   532    532         sqlite3VdbeAddOp(v, OP_MakeRecord, nColumn, 0);
   533    533         if( pOrderBy ){
   534    534           pushOntoSorter(pParse, pOrderBy, p);
   535    535         }else{
   536    536           sqlite3VdbeAddOp(v, OP_NewRowid, iParm, 0);
   537    537           sqlite3VdbeAddOp(v, OP_Pull, 1, 0);
   538         -        sqlite3VdbeAddOp(v, OP_Insert, iParm, 0);
          538  +        sqlite3VdbeAddOp(v, OP_Insert, iParm, OPFLAG_APPEND);
   539    539         }
   540    540         break;
   541    541       }
   542    542   
   543    543   #ifndef SQLITE_OMIT_SUBQUERY
   544    544       /* If we are creating a set for an "expr IN (SELECT ...)" construct,
   545    545       ** then there should be a single item on the stack.  Write this
................................................................................
   710    710     }
   711    711     sqlite3VdbeAddOp(v, OP_Column, iTab, pOrderBy->nExpr + 1);
   712    712     switch( eDest ){
   713    713       case SRT_Table:
   714    714       case SRT_EphemTab: {
   715    715         sqlite3VdbeAddOp(v, OP_NewRowid, iParm, 0);
   716    716         sqlite3VdbeAddOp(v, OP_Pull, 1, 0);
   717         -      sqlite3VdbeAddOp(v, OP_Insert, iParm, 0);
          717  +      sqlite3VdbeAddOp(v, OP_Insert, iParm, OPFLAG_APPEND);
   718    718         break;
   719    719       }
   720    720   #ifndef SQLITE_OMIT_SUBQUERY
   721    721       case SRT_Set: {
   722    722         assert( nColumn==1 );
   723    723         sqlite3VdbeAddOp(v, OP_NotNull, -1, sqlite3VdbeCurrentAddr(v)+3);
   724    724         sqlite3VdbeAddOp(v, OP_Pop, 1, 0);

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.546 2007/03/28 14:30:07 drh Exp $
           14  +** @(#) $Id: sqliteInt.h,v 1.547 2007/03/29 05:51:49 drh Exp $
    15     15   */
    16     16   #ifndef _SQLITEINT_H_
    17     17   #define _SQLITEINT_H_
    18     18   
    19     19   #if defined(SQLITE_TCL) || defined(TCLSH)
    20     20   # include <tcl.h>
    21     21   #endif
................................................................................
  1372   1372   
  1373   1373   /*
  1374   1374   ** Bitfield flags for P2 value in OP_Insert and OP_Delete
  1375   1375   */
  1376   1376   #define OPFLAG_NCHANGE   1    /* Set to update db->nChange */
  1377   1377   #define OPFLAG_LASTROWID 2    /* Set to update db->lastRowid */
  1378   1378   #define OPFLAG_ISUPDATE  4    /* This OP_Insert is an sql UPDATE */
         1379  +#define OPFLAG_APPEND    8    /* This is likely to be an append */
  1379   1380   
  1380   1381   /*
  1381   1382    * Each trigger present in the database schema is stored as an instance of
  1382   1383    * struct Trigger. 
  1383   1384    *
  1384   1385    * Pointers to instances of struct Trigger are stored in two ways.
  1385   1386    * 1. In the "trigHash" hash table (part of the sqlite3* that represents the 
................................................................................
  1688   1689   int sqlite3ExprIsConstantOrFunction(Expr*);
  1689   1690   int sqlite3ExprIsInteger(Expr*, int*);
  1690   1691   int sqlite3IsRowid(const char*);
  1691   1692   void sqlite3GenerateRowDelete(sqlite3*, Vdbe*, Table*, int, int);
  1692   1693   void sqlite3GenerateRowIndexDelete(Vdbe*, Table*, int, char*);
  1693   1694   void sqlite3GenerateIndexKey(Vdbe*, Index*, int);
  1694   1695   void sqlite3GenerateConstraintChecks(Parse*,Table*,int,char*,int,int,int,int);
  1695         -void sqlite3CompleteInsertion(Parse*, Table*, int, char*, int, int, int);
         1696  +void sqlite3CompleteInsertion(Parse*, Table*, int, char*, int, int, int, int);
  1696   1697   void sqlite3OpenTableAndIndices(Parse*, Table*, int, int);
  1697   1698   void sqlite3BeginWriteOperation(Parse*, int, int);
  1698   1699   Expr *sqlite3ExprDup(Expr*);
  1699   1700   void sqlite3TokenCopy(Token*, Token*);
  1700   1701   ExprList *sqlite3ExprListDup(ExprList*);
  1701   1702   SrcList *sqlite3SrcListDup(SrcList*);
  1702   1703   IdList *sqlite3IdListDup(IdList*);

Changes to src/test3.c.

     9      9   **    May you share freely, never taking more than you give.
    10     10   **
    11     11   *************************************************************************
    12     12   ** Code for testing the btree.c module in SQLite.  This code
    13     13   ** is not included in the SQLite library.  It is used for automated
    14     14   ** testing of the SQLite library.
    15     15   **
    16         -** $Id: test3.c,v 1.72 2007/03/26 22:05:02 drh Exp $
           16  +** $Id: test3.c,v 1.73 2007/03/29 05:51:49 drh Exp $
    17     17   */
    18     18   #include "sqliteInt.h"
    19     19   #include "pager.h"
    20     20   #include "btree.h"
    21     21   #include "tcl.h"
    22     22   #include <stdlib.h>
    23     23   #include <string.h>
................................................................................
   702    702          " ID KEY\"", 0);
   703    703       return TCL_ERROR;
   704    704     }
   705    705     pCur = sqlite3TextToPtr(argv[1]);
   706    706     if( sqlite3BtreeFlags(pCur) & BTREE_INTKEY ){
   707    707       int iKey;
   708    708       if( Tcl_GetInt(interp, argv[2], &iKey) ) return TCL_ERROR;
   709         -    rc = sqlite3BtreeMoveto(pCur, 0, iKey, &res);
          709  +    rc = sqlite3BtreeMoveto(pCur, 0, iKey, 0, &res);
   710    710     }else{
   711         -    rc = sqlite3BtreeMoveto(pCur, argv[2], strlen(argv[2]), &res);  
          711  +    rc = sqlite3BtreeMoveto(pCur, argv[2], strlen(argv[2]), 0, &res);  
   712    712     }
   713    713     if( rc ){
   714    714       Tcl_AppendResult(interp, errorName(rc), 0);
   715    715       return TCL_ERROR;
   716    716     }
   717    717     if( res<0 ) res = -1;
   718    718     if( res>0 ) res = 1;
................................................................................
   771    771     pCur = sqlite3TextToPtr(Tcl_GetString(objv[1]));
   772    772     if( sqlite3BtreeFlags(pCur) & BTREE_INTKEY ){
   773    773       i64 iKey;
   774    774       int len;
   775    775       unsigned char *pBuf;
   776    776       if( Tcl_GetWideIntFromObj(interp, objv[2], &iKey) ) return TCL_ERROR;
   777    777       pBuf = Tcl_GetByteArrayFromObj(objv[3], &len);
   778         -    rc = sqlite3BtreeInsert(pCur, 0, iKey, pBuf, len);
          778  +    rc = sqlite3BtreeInsert(pCur, 0, iKey, pBuf, len, 0);
   779    779     }else{
   780    780       int keylen;
   781    781       int dlen;
   782    782       unsigned char *pKBuf;
   783    783       unsigned char *pDBuf;
   784    784       pKBuf = Tcl_GetByteArrayFromObj(objv[2], &keylen);
   785    785       pDBuf = Tcl_GetByteArrayFromObj(objv[3], &dlen);
   786         -    rc = sqlite3BtreeInsert(pCur, pKBuf, keylen, pDBuf, dlen);
          786  +    rc = sqlite3BtreeInsert(pCur, pKBuf, keylen, pDBuf, dlen, 0);
   787    787     }
   788    788     if( rc ){
   789    789       Tcl_AppendResult(interp, errorName(rc), 0);
   790    790       return TCL_ERROR;
   791    791     }
   792    792     return SQLITE_OK;
   793    793   }

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.136 2007/02/21 17:04:04 danielk1977 Exp $
           15  +** $Id: update.c,v 1.137 2007/03/29 05:51:49 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 */
................................................................................
   461    461       */
   462    462       if( chngRowid ){
   463    463         sqlite3VdbeAddOp(v, OP_Delete, iCur, 0);
   464    464       }
   465    465   
   466    466       /* Create the new index entries and the new record.
   467    467       */
   468         -    sqlite3CompleteInsertion(pParse, pTab, iCur, aIdxUsed, chngRowid, 1, -1);
          468  +    sqlite3CompleteInsertion(pParse, pTab, iCur, aIdxUsed, chngRowid, 1, -1, 0);
   469    469     }
   470    470   
   471    471     /* Increment the row counter 
   472    472     */
   473    473     if( db->flags & SQLITE_CountRows && !pParse->trigStack){
   474    474       sqlite3VdbeAddOp(v, OP_MemIncr, 1, memCnt);
   475    475     }

Changes to src/vdbe.c.

    39     39   **
    40     40   ** Various scripts scan this source file in order to generate HTML
    41     41   ** documentation, headers files, or other derived files.  The formatting
    42     42   ** of the code in this file is, therefore, important.  See other comments
    43     43   ** in this file for details.  If in doubt, do not deviate from existing
    44     44   ** commenting and indentation practices when changing or adding code.
    45     45   **
    46         -** $Id: vdbe.c,v 1.595 2007/03/28 14:30:07 drh Exp $
           46  +** $Id: vdbe.c,v 1.596 2007/03/29 05:51:49 drh Exp $
    47     47   */
    48     48   #include "sqliteInt.h"
    49     49   #include "os.h"
    50     50   #include <ctype.h>
    51     51   #include "vdbeInt.h"
    52     52   
    53     53   /*
................................................................................
  2830   2830         if( pOp->p2==0 && pOp->opcode==OP_MoveGe ){
  2831   2831           pC->movetoTarget = iKey;
  2832   2832           pC->deferredMoveto = 1;
  2833   2833           assert( (pTos->flags & MEM_Dyn)==0 );
  2834   2834           pTos--;
  2835   2835           break;
  2836   2836         }
  2837         -      rc = sqlite3BtreeMoveto(pC->pCursor, 0, (u64)iKey, &res);
         2837  +      rc = sqlite3BtreeMoveto(pC->pCursor, 0, (u64)iKey, 0, &res);
  2838   2838         if( rc!=SQLITE_OK ){
  2839   2839           goto abort_due_to_error;
  2840   2840         }
  2841   2841         pC->lastRowid = pTos->i;
  2842   2842         pC->rowidIsValid = res==0;
  2843   2843       }else{
  2844   2844         assert( pTos->flags & MEM_Blob );
  2845   2845         /* Stringify(pTos, encoding); */
  2846         -      rc = sqlite3BtreeMoveto(pC->pCursor, pTos->z, pTos->n, &res);
         2846  +      rc = sqlite3BtreeMoveto(pC->pCursor, pTos->z, pTos->n, 0, &res);
  2847   2847         if( rc!=SQLITE_OK ){
  2848   2848           goto abort_due_to_error;
  2849   2849         }
  2850   2850         pC->rowidIsValid = 0;
  2851   2851       }
  2852   2852       pC->deferredMoveto = 0;
  2853   2853       pC->cacheStatus = CACHE_STALE;
................................................................................
  2946   2946     assert( pTos>=p->aStack );
  2947   2947     assert( i>=0 && i<p->nCursor );
  2948   2948     assert( p->apCsr[i]!=0 );
  2949   2949     if( (pC = p->apCsr[i])->pCursor!=0 ){
  2950   2950       int res, rx;
  2951   2951       assert( pC->isTable==0 );
  2952   2952       Stringify(pTos, encoding);
  2953         -    rx = sqlite3BtreeMoveto(pC->pCursor, pTos->z, pTos->n, &res);
         2953  +    rx = sqlite3BtreeMoveto(pC->pCursor, pTos->z, pTos->n, 0, &res);
  2954   2954       alreadyExists = rx==SQLITE_OK && res==0;
  2955   2955       pC->deferredMoveto = 0;
  2956   2956       pC->cacheStatus = CACHE_STALE;
  2957   2957     }
  2958   2958     if( pOp->opcode==OP_Found ){
  2959   2959       if( alreadyExists ) pc = pOp->p2 - 1;
  2960   2960     }else{
................................................................................
  3024   3024       len = nKey-szRowid;
  3025   3025   
  3026   3026       /* Search for an entry in P1 where all but the last four bytes match K.
  3027   3027       ** If there is no such entry, jump immediately to P2.
  3028   3028       */
  3029   3029       assert( pCx->deferredMoveto==0 );
  3030   3030       pCx->cacheStatus = CACHE_STALE;
  3031         -    rc = sqlite3BtreeMoveto(pCrsr, zKey, len, &res);
         3031  +    rc = sqlite3BtreeMoveto(pCrsr, zKey, len, 0, &res);
  3032   3032       if( rc!=SQLITE_OK ){
  3033   3033         goto abort_due_to_error;
  3034   3034       }
  3035   3035       if( res<0 ){
  3036   3036         rc = sqlite3BtreeNext(pCrsr, &res);
  3037   3037         if( res ){
  3038   3038           pc = pOp->p2 - 1;
................................................................................
  3094   3094     assert( p->apCsr[i]!=0 );
  3095   3095     if( (pCrsr = (pC = p->apCsr[i])->pCursor)!=0 ){
  3096   3096       int res;
  3097   3097       u64 iKey;
  3098   3098       assert( pTos->flags & MEM_Int );
  3099   3099       assert( p->apCsr[i]->isTable );
  3100   3100       iKey = intToKey(pTos->i);
  3101         -    rc = sqlite3BtreeMoveto(pCrsr, 0, iKey, &res);
         3101  +    rc = sqlite3BtreeMoveto(pCrsr, 0, iKey, 0,&res);
  3102   3102       pC->lastRowid = pTos->i;
  3103   3103       pC->rowidIsValid = res==0;
  3104   3104       pC->nullRow = 0;
  3105   3105       pC->cacheStatus = CACHE_STALE;
  3106   3106       /* res might be uninitialized if rc!=SQLITE_OK.  But if rc!=SQLITE_OK
  3107   3107       ** processing is about to abort so we really do not care whether or not
  3108   3108       ** the following jump is taken. */
................................................................................
  3266   3266           }else{
  3267   3267             unsigned char r;
  3268   3268             sqlite3Randomness(1, &r);
  3269   3269             v += r + 1;
  3270   3270           }
  3271   3271           if( v==0 ) continue;
  3272   3272           x = intToKey(v);
  3273         -        rx = sqlite3BtreeMoveto(pC->pCursor, 0, (u64)x, &res);
         3273  +        rx = sqlite3BtreeMoveto(pC->pCursor, 0, (u64)x, 0, &res);
  3274   3274           cnt++;
  3275   3275         }while( cnt<1000 && rx==SQLITE_OK && res==0 );
  3276   3276         db->priorNewRowid = v;
  3277   3277         if( rx==SQLITE_OK && res==0 ){
  3278   3278           rc = SQLITE_FULL;
  3279   3279           goto abort_due_to_error;
  3280   3280         }
................................................................................
  3346   3346           if( !pC->pData ) goto no_mem;
  3347   3347           memcpy(pC->pData, pTos->z, pC->nData);
  3348   3348           pC->pData[pC->nData] = 0;
  3349   3349           pC->pData[pC->nData+1] = 0;
  3350   3350         }
  3351   3351         pC->nullRow = 0;
  3352   3352       }else{
  3353         -      rc = sqlite3BtreeInsert(pC->pCursor, 0, iKey, pTos->z, pTos->n);
         3353  +      rc = sqlite3BtreeInsert(pC->pCursor, 0, iKey,
         3354  +                              pTos->z, pTos->n,
         3355  +                              pOp->p2 & OPFLAG_APPEND);
  3354   3356       }
  3355   3357       
  3356   3358       pC->rowidIsValid = 0;
  3357   3359       pC->deferredMoveto = 0;
  3358   3360       pC->cacheStatus = CACHE_STALE;
  3359   3361   
  3360   3362       /* Invoke the update-hook if required. */
................................................................................
  3700   3702     }else{
  3701   3703       pC->nullRow = 1;
  3702   3704     }
  3703   3705     pC->rowidIsValid = 0;
  3704   3706     break;
  3705   3707   }
  3706   3708   
  3707         -/* Opcode: IdxInsert P1 * *
         3709  +/* Opcode: IdxInsert P1 P2 *
  3708   3710   **
  3709   3711   ** The top of the stack holds a SQL index key made using either the
  3710   3712   ** MakeIdxRec or MakeRecord instructions.  This opcode writes that key
  3711   3713   ** into the index P1.  Data for the entry is nil.
         3714  +**
         3715  +** P2 is a flag that provides a hint to the b-tree layer that this
         3716  +** insert is likely to be an append.
  3712   3717   **
  3713   3718   ** This instruction only works for indices.  The equivalent instruction
  3714   3719   ** for tables is OP_Insert.
  3715   3720   */
  3716   3721   case OP_IdxInsert: {        /* no-push */
  3717   3722     int i = pOp->p1;
  3718   3723     Cursor *pC;
  3719   3724     BtCursor *pCrsr;
  3720   3725     assert( pTos>=p->aStack );
  3721   3726     assert( i>=0 && i<p->nCursor );
  3722   3727     assert( p->apCsr[i]!=0 );
  3723   3728     assert( pTos->flags & MEM_Blob );
  3724         -  assert( pOp->p2==0 );
  3725   3729     if( (pCrsr = (pC = p->apCsr[i])->pCursor)!=0 ){
  3726   3730       int nKey = pTos->n;
  3727   3731       const char *zKey = pTos->z;
  3728   3732       assert( pC->isTable==0 );
  3729         -    rc = sqlite3BtreeInsert(pCrsr, zKey, nKey, "", 0);
         3733  +    rc = sqlite3BtreeInsert(pCrsr, zKey, nKey, "", 0, pOp->p2);
  3730   3734       assert( pC->deferredMoveto==0 );
  3731   3735       pC->cacheStatus = CACHE_STALE;
  3732   3736     }
  3733   3737     Release(pTos);
  3734   3738     pTos--;
  3735   3739     break;
  3736   3740   }
................................................................................
  3747   3751     BtCursor *pCrsr;
  3748   3752     assert( pTos>=p->aStack );
  3749   3753     assert( pTos->flags & MEM_Blob );
  3750   3754     assert( i>=0 && i<p->nCursor );
  3751   3755     assert( p->apCsr[i]!=0 );
  3752   3756     if( (pCrsr = (pC = p->apCsr[i])->pCursor)!=0 ){
  3753   3757       int res;
  3754         -    rc = sqlite3BtreeMoveto(pCrsr, pTos->z, pTos->n, &res);
         3758  +    rc = sqlite3BtreeMoveto(pCrsr, pTos->z, pTos->n, 0, &res);
  3755   3759       if( rc==SQLITE_OK && res==0 ){
  3756   3760         rc = sqlite3BtreeDelete(pCrsr);
  3757   3761       }
  3758   3762       assert( pC->deferredMoveto==0 );
  3759   3763       pC->cacheStatus = CACHE_STALE;
  3760   3764     }
  3761   3765     Release(pTos);

Changes to src/vdbeaux.c.

  1659   1659     if( p->deferredMoveto ){
  1660   1660       int res, rc;
  1661   1661   #ifdef SQLITE_TEST
  1662   1662       extern int sqlite3_search_count;
  1663   1663   #endif
  1664   1664       assert( p->isTable );
  1665   1665       if( p->isTable ){
  1666         -      rc = sqlite3BtreeMoveto(p->pCursor, 0, p->movetoTarget, &res);
         1666  +      rc = sqlite3BtreeMoveto(p->pCursor, 0, p->movetoTarget, 0, &res);
  1667   1667       }else{
  1668   1668         rc = sqlite3BtreeMoveto(p->pCursor,(char*)&p->movetoTarget,
  1669         -                              sizeof(i64),&res);
         1669  +                              sizeof(i64), 0, &res);
  1670   1670       }
  1671   1671       if( rc ) return rc;
  1672   1672       *p->pIncrKey = 0;
  1673   1673       p->lastRowid = keyToInt(p->movetoTarget);
  1674   1674       p->rowidIsValid = res==0;
  1675   1675       if( res<0 ){
  1676   1676         rc = sqlite3BtreeNext(p->pCursor, &res);