Speed up INSERT operations that add data to UNIQUE or PRIMARY KEY indexes by rationalizing duplicate seek operations. (CVS 6599)

FossilOrigin-Name: cac4f3d812f0a02ca5c1fa78d366f694403929a8

11 files changed, 169 insertions, 147 deletions

diff --git a/src/btree.c b/src/btree.c
index 2692539a5..48e4c59a9 100644
--- a/src/btree.c
+++ b/src/btree.c
@@ -9,7 +9,7 @@
 **    May you share freely, never taking more than you give.
 **
 *************************************************************************
-** $Id: btree.c,v 1.605 2009/05/02 10:03:09 danielk1977 Exp $
+** $Id: btree.c,v 1.606 2009/05/04 11:42:30 danielk1977 Exp $
 **
 ** This file implements a external (disk-based) database using BTrees.
 ** See the header comment on "btreeInt.h" for additional information.
@@ -6134,16 +6134,28 @@ static int checkForReadConflicts(
 **
 ** For an INTKEY table, only the nKey value of the key is used.  pKey is
 ** ignored.  For a ZERODATA table, the pData and nData are both ignored.
+**
+** If the seekResult parameter is non-zero, then a successful call to
+** sqlite3BtreeMoveto() to seek cursor pCur to (pKey, nKey) has already
+** been performed. seekResult is the search result returned (a negative
+** number if pCur points at an entry that is smaller than (pKey, nKey), or
+** a positive value if pCur points at an etry that is larger than 
+** (pKey, nKey)). 
+**
+** If the seekResult parameter is 0, then cursor pCur may point to any 
+** entry or to no entry at all. In this case this function has to seek
+** the cursor before the new key can be inserted.
 */
 int sqlite3BtreeInsert(
   BtCursor *pCur,                /* Insert data into the table of this cursor */
   const void *pKey, i64 nKey,    /* The key of the new record */
   const void *pData, int nData,  /* The data of the new record */
   int nZero,                     /* Number of extra 0 bytes to append to data */
-  int appendBias                 /* True if this is likely an append */
+  int appendBias,                /* True if this is likely an append */
+  int seekResult                 /* Result of prior sqlite3BtreeMoveto() call */
 ){
   int rc;
-  int loc;
+  int loc = seekResult;
   int szNew;
   int idx;
   MemPage *pPage;
@@ -6177,10 +6189,10 @@ int sqlite3BtreeInsert(
   ** doing any work. To avoid thwarting these optimizations, it is important
   ** not to clear the cursor here.
   */
-  if( 
-    SQLITE_OK!=(rc = saveAllCursors(pBt, pCur->pgnoRoot, pCur)) ||
+  if(
+    SQLITE_OK!=(rc = saveAllCursors(pBt, pCur->pgnoRoot, pCur)) || (!loc &&
     SQLITE_OK!=(rc = sqlite3BtreeMoveto(pCur, pKey, nKey, appendBias, &loc))
-  ){
+  )){
     return rc;
   }
 
diff --git a/src/btree.h b/src/btree.h
index 378c9892c..b4b7e0d19 100644
--- a/src/btree.h
+++ b/src/btree.h
@@ -13,7 +13,7 @@
 ** subsystem.  See comments in the source code for a detailed description
 ** of what each interface routine does.
 **
-** @(#) $Id: btree.h,v 1.113 2009/04/10 12:55:17 danielk1977 Exp $
+** @(#) $Id: btree.h,v 1.114 2009/05/04 11:42:30 danielk1977 Exp $
 */
 #ifndef _BTREE_H_
 #define _BTREE_H_
@@ -148,7 +148,7 @@ int sqlite3BtreeCursorHasMoved(BtCursor*, int*);
 int sqlite3BtreeDelete(BtCursor*);
 int sqlite3BtreeInsert(BtCursor*, const void *pKey, i64 nKey,
                                   const void *pData, int nData,
-                                  int nZero, int bias);
+                                  int nZero, int bias, int seekResult);
 int sqlite3BtreeFirst(BtCursor*, int *pRes);
 int sqlite3BtreeLast(BtCursor*, int *pRes);
 int sqlite3BtreeNext(BtCursor*, int *pRes);
diff --git a/src/build.c b/src/build.c
index 065ef5305..ddfd0cb49 100644
--- a/src/build.c
+++ b/src/build.c
@@ -22,7 +22,7 @@
 **     COMMIT
 **     ROLLBACK
 **
-** $Id: build.c,v 1.535 2009/05/03 20:23:53 drh Exp $
+** $Id: build.c,v 1.536 2009/05/04 11:42:30 danielk1977 Exp $
 */
 #include "sqliteInt.h"
 
@@ -2355,19 +2355,25 @@ static void sqlite3RefillIndex(Parse *pParse, Index *pIndex, int memRootPage){
   regRecord = sqlite3GetTempReg(pParse);
   regIdxKey = sqlite3GenerateIndexKey(pParse, pIndex, iTab, regRecord, 1);
   if( pIndex->onError!=OE_None ){
-    int j1, j2;
-    int regRowid;
-
-    regRowid = regIdxKey + pIndex->nColumn;
-    j1 = sqlite3VdbeAddOp3(v, OP_IsNull, regIdxKey, 0, pIndex->nColumn);
-    j2 = sqlite3VdbeAddOp4(v, OP_IsUnique, iIdx,
-                           0, regRowid, SQLITE_INT_TO_PTR(regRecord), P4_INT32);
+    const int regRowid = regIdxKey + pIndex->nColumn;
+    const int j2 = sqlite3VdbeCurrentAddr(v) + 2;
+    void * const pRegKey = SQLITE_INT_TO_PTR(regIdxKey);
+
+    /* The registers accessed by the OP_IsUnique opcode were allocated
+    ** using sqlite3GetTempRange() inside of the sqlite3GenerateIndexKey()
+    ** call above. Just before that function was freed they were released
+    ** (made available to the compiler for reuse) using 
+    ** sqlite3ReleaseTempRange(). So in some ways having the OP_IsUnique
+    ** opcode use the values stored within seems dangerous. However, since
+    ** we can be sure that no other temp registers have been allocated
+    ** since sqlite3ReleaseTempRange() was called, it is safe to do so.
+    */
+    sqlite3VdbeAddOp4(v, OP_IsUnique, iIdx, j2, regRowid, pRegKey, P4_INT32);
     sqlite3VdbeAddOp4(v, OP_Halt, SQLITE_CONSTRAINT, OE_Abort, 0,
                     "indexed columns are not unique", P4_STATIC);
-    sqlite3VdbeJumpHere(v, j1);
-    sqlite3VdbeJumpHere(v, j2);
   }
   sqlite3VdbeAddOp2(v, OP_IdxInsert, iIdx, regRecord);
+  sqlite3VdbeChangeP5(v, OPFLAG_USESEEKRESULT);
   sqlite3ReleaseTempReg(pParse, regRecord);
   sqlite3VdbeAddOp2(v, OP_Next, iTab, addr1+1);
   sqlite3VdbeJumpHere(v, addr1);
diff --git a/src/insert.c b/src/insert.c
index 84ca95d6a..89c5df6b4 100644
--- a/src/insert.c
+++ b/src/insert.c
@@ -12,7 +12,7 @@
 ** This file contains C code routines that are called by the parser
 ** to handle INSERT statements in SQLite.
 **
-** $Id: insert.c,v 1.266 2009/05/03 01:01:00 drh Exp $
+** $Id: insert.c,v 1.267 2009/05/04 11:42:30 danielk1977 Exp $
 */
 #include "sqliteInt.h"
 
@@ -943,27 +943,14 @@ void sqlite3Insert(
     }else
 #endif
     {
-      sqlite3GenerateConstraintChecks(
-          pParse,
-          pTab,
-          baseCur,
-          regIns,
-          aRegIdx,
-          keyColumn>=0,
-          0,
-          onError,
-          endOfLoop
+      int isReplace;    /* Set to true if constraints may cause a replace */
+      sqlite3GenerateConstraintChecks(pParse, pTab, baseCur, regIns, aRegIdx,
+          keyColumn>=0, 0, onError, endOfLoop, &isReplace
       );
       sqlite3CompleteInsertion(
-          pParse,
-          pTab,
-          baseCur,
-          regIns,
-          aRegIdx,
-          0,
-          (tmask&TRIGGER_AFTER) ? newIdx : -1,
-          appendFlag
-       );
+          pParse, pTab, baseCur, regIns, aRegIdx, 0,
+          (tmask&TRIGGER_AFTER) ? newIdx : -1, appendFlag, isReplace==0
+      );
     }
   }
 
@@ -1113,7 +1100,8 @@ void sqlite3GenerateConstraintChecks(
   int rowidChng,      /* True if the rowid might collide with existing entry */
   int isUpdate,       /* True for UPDATE, False for INSERT */
   int overrideError,  /* Override onError to this if not OE_Default */
-  int ignoreDest      /* Jump to this label on an OE_Ignore resolution */
+  int ignoreDest,     /* Jump to this label on an OE_Ignore resolution */
+  int *pbMayReplace   /* OUT: Set to true if constraint may cause a replace */
 ){
   int i;              /* loop counter */
   Vdbe *v;            /* VDBE under constrution */
@@ -1266,11 +1254,13 @@ void sqlite3GenerateConstraintChecks(
     sqlite3VdbeAddOp3(v, OP_MakeRecord, regIdx, pIdx->nColumn+1, aRegIdx[iCur]);
     sqlite3IndexAffinityStr(v, pIdx);
     sqlite3ExprCacheAffinityChange(pParse, regIdx, pIdx->nColumn+1);
-    sqlite3ReleaseTempRange(pParse, regIdx, pIdx->nColumn+1);
 
     /* Find out what action to take in case there is an indexing conflict */
     onError = pIdx->onError;
-    if( onError==OE_None ) continue;  /* pIdx is not a UNIQUE index */
+    if( onError==OE_None ){ 
+      sqlite3ReleaseTempRange(pParse, regIdx, pIdx->nColumn+1);
+      continue;  /* pIdx is not a UNIQUE index */
+    }
     if( overrideError!=OE_Default ){
       onError = overrideError;
     }else if( onError==OE_Default ){
@@ -1283,12 +1273,12 @@ void sqlite3GenerateConstraintChecks(
     
 
     /* Check to see if the new index entry will be unique */
-    j2 = sqlite3VdbeAddOp3(v, OP_IsNull, regIdx, 0, pIdx->nColumn);
     regR = sqlite3GetTempReg(pParse);
     sqlite3VdbeAddOp2(v, OP_SCopy, regRowid-hasTwoRowids, regR);
     j3 = sqlite3VdbeAddOp4(v, OP_IsUnique, baseCur+iCur+1, 0,
-                           regR, SQLITE_INT_TO_PTR(aRegIdx[iCur]),
+                           regR, SQLITE_INT_TO_PTR(regIdx),
                            P4_INT32);
+    sqlite3ReleaseTempRange(pParse, regIdx, pIdx->nColumn+1);
 
     /* Generate code that executes if the new index entry is not unique */
     assert( onError==OE_Rollback || onError==OE_Abort || onError==OE_Fail
@@ -1330,10 +1320,13 @@ void sqlite3GenerateConstraintChecks(
         break;
       }
     }
-    sqlite3VdbeJumpHere(v, j2);
     sqlite3VdbeJumpHere(v, j3);
     sqlite3ReleaseTempReg(pParse, regR);
   }
+
+  if( pbMayReplace ){
+    *pbMayReplace = seenReplace;
+  }
 }
 
 /*
@@ -1353,7 +1346,8 @@ void sqlite3CompleteInsertion(
   int *aRegIdx,       /* Register used by each index.  0 for unused indices */
   int isUpdate,       /* True for UPDATE, False for INSERT */
   int newIdx,         /* Index of NEW table for triggers.  -1 if none */
-  int appendBias      /* True if this is likely to be an append */
+  int appendBias,     /* True if this is likely to be an append */
+  int useSeekResult   /* True to set the USESEEKRESULT flag on OP_[Idx]Insert */
 ){
   int i;
   Vdbe *v;
@@ -1370,6 +1364,9 @@ void sqlite3CompleteInsertion(
   for(i=nIdx-1; i>=0; i--){
     if( aRegIdx[i]==0 ) continue;
     sqlite3VdbeAddOp2(v, OP_IdxInsert, baseCur+i+1, aRegIdx[i]);
+    if( useSeekResult ){
+      sqlite3VdbeChangeP5(v, OPFLAG_USESEEKRESULT);
+    }
   }
   regData = regRowid + 1;
   regRec = sqlite3GetTempReg(pParse);
@@ -1390,6 +1387,9 @@ void sqlite3CompleteInsertion(
   if( appendBias ){
     pik_flags |= OPFLAG_APPEND;
   }
+  if( useSeekResult ){
+    pik_flags |= OPFLAG_USESEEKRESULT;
+  }
   sqlite3VdbeAddOp3(v, OP_Insert, baseCur, regRec, regRowid);
   if( !pParse->nested ){
     sqlite3VdbeChangeP4(v, -1, pTab->zName, P4_STATIC);
diff --git a/src/memjournal.c b/src/memjournal.c
index 15665a013..df770b44e 100644
--- a/src/memjournal.c
+++ b/src/memjournal.c
@@ -14,7 +14,7 @@
 ** The in-memory rollback journal is used to journal transactions for
 ** ":memory:" databases and when the journal_mode=MEMORY pragma is used.
 **
-** @(#) $Id: memjournal.c,v 1.11 2009/04/05 12:22:09 drh Exp $
+** @(#) $Id: memjournal.c,v 1.12 2009/05/04 11:42:30 danielk1977 Exp $
 */
 #include "sqliteInt.h"
 
@@ -129,7 +129,7 @@ static int memjrnlWrite(
   /* An in-memory journal file should only ever be appended to. Random
   ** access writes are not required by sqlite.
   */
-  assert(iOfst==p->endpoint.iOffset);
+  assert( iOfst==p->endpoint.iOffset );
   UNUSED_PARAMETER(iOfst);
 
   while( nWrite>0 ){
diff --git a/src/sqliteInt.h b/src/sqliteInt.h
index c5282b340..82330f9d5 100644
--- a/src/sqliteInt.h
+++ b/src/sqliteInt.h
@@ -11,7 +11,7 @@
 *************************************************************************
 ** Internal interface definitions for SQLite.
 **
-** @(#) $Id: sqliteInt.h,v 1.867 2009/05/03 20:23:54 drh Exp $
+** @(#) $Id: sqliteInt.h,v 1.868 2009/05/04 11:42:30 danielk1977 Exp $
 */
 #ifndef _SQLITEINT_H_
 #define _SQLITEINT_H_
@@ -1282,6 +1282,7 @@ struct UnpackedRecord {
   KeyInfo *pKeyInfo;  /* Collation and sort-order information */
   u16 nField;         /* Number of entries in apMem[] */
   u16 flags;          /* Boolean settings.  UNPACKED_... below */
+  i64 rowid;          /* Used by UNPACKED_PREFIX_SEARCH */
   Mem *aMem;          /* Values */
 };
 
@@ -1293,6 +1294,7 @@ struct UnpackedRecord {
 #define UNPACKED_IGNORE_ROWID  0x0004  /* Ignore trailing rowid on key1 */
 #define UNPACKED_INCRKEY       0x0008  /* Make this key an epsilon larger */
 #define UNPACKED_PREFIX_MATCH  0x0010  /* A prefix match is considered OK */
+#define UNPACKED_PREFIX_SEARCH 0x0020  /* A prefix match is considered OK */
 
 /*
 ** Each SQL index is represented in memory by an
@@ -1998,12 +2000,13 @@ struct AuthContext {
 };
 
 /*
-** Bitfield flags for P2 value in OP_Insert and OP_Delete
+** Bitfield flags for P5 value in OP_Insert and OP_Delete
 */
-#define OPFLAG_NCHANGE   1    /* Set to update db->nChange */
-#define OPFLAG_LASTROWID 2    /* Set to update db->lastRowid */
-#define OPFLAG_ISUPDATE  4    /* This OP_Insert is an sql UPDATE */
-#define OPFLAG_APPEND    8    /* This is likely to be an append */
+#define OPFLAG_NCHANGE    1    /* Set to update db->nChange */
+#define OPFLAG_LASTROWID  2    /* Set to update db->lastRowid */
+#define OPFLAG_ISUPDATE   4    /* This OP_Insert is an sql UPDATE */
+#define OPFLAG_APPEND     8    /* This is likely to be an append */
+#define OPFLAG_USESEEKRESULT 16    /* Try to avoid a seek in BtreeInsert() */
 
 /*
  * Each trigger present in the database schema is stored as an instance of
@@ -2494,8 +2497,8 @@ void sqlite3GenerateRowDelete(Parse*, Table*, int, int, int);
 void sqlite3GenerateRowIndexDelete(Parse*, Table*, int, int*);
 int sqlite3GenerateIndexKey(Parse*, Index*, int, int, int);
 void sqlite3GenerateConstraintChecks(Parse*,Table*,int,int,
-                                     int*,int,int,int,int);
-void sqlite3CompleteInsertion(Parse*, Table*, int, int, int*, int, int, int);
+                                     int*,int,int,int,int,int*);
+void sqlite3CompleteInsertion(Parse*, Table*, int, int, int*, int, int,int,int);
 int sqlite3OpenTableAndIndices(Parse*, Table*, int, int);
 void sqlite3BeginWriteOperation(Parse*, int, int);
 Expr *sqlite3ExprDup(sqlite3*,Expr*,int);
diff --git a/src/test3.c b/src/test3.c
index 0f1044799..3a795b704 100644
--- a/src/test3.c
+++ b/src/test3.c
@@ -13,7 +13,7 @@
 ** is not included in the SQLite library.  It is used for automated
 ** testing of the SQLite library.
 **
-** $Id: test3.c,v 1.103 2009/03/18 10:33:02 danielk1977 Exp $
+** $Id: test3.c,v 1.104 2009/05/04 11:42:30 danielk1977 Exp $
 */
 #include "sqliteInt.h"
 #include "btreeInt.h"
@@ -782,7 +782,7 @@ static int btree_insert(
       return TCL_ERROR;
     }
     pBuf = Tcl_GetByteArrayFromObj(objv[3], &len);
-    rc = sqlite3BtreeInsert(pCur, 0, iKey, pBuf, len, nZero, 0);
+    rc = sqlite3BtreeInsert(pCur, 0, iKey, pBuf, len, nZero, 0, 0);
   }else{
     int keylen;
     int dlen;
@@ -790,7 +790,7 @@ static int btree_insert(
     unsigned char *pDBuf;
     pKBuf = Tcl_GetByteArrayFromObj(objv[2], &keylen);
     pDBuf = Tcl_GetByteArrayFromObj(objv[3], &dlen);
-    rc = sqlite3BtreeInsert(pCur, pKBuf, keylen, pDBuf, dlen, nZero, 0);
+    rc = sqlite3BtreeInsert(pCur, pKBuf, keylen, pDBuf, dlen, nZero, 0, 0);
   }
   sqlite3BtreeLeave(pCur->pBtree);
   if( rc ){
diff --git a/src/update.c b/src/update.c
index 3d5332413..36704856c 100644
--- a/src/update.c
+++ b/src/update.c
@@ -12,7 +12,7 @@
 ** This file contains C code routines that are called by the parser
 ** to handle UPDATE statements.
 **
-** $Id: update.c,v 1.198 2009/04/24 15:46:22 drh Exp $
+** $Id: update.c,v 1.199 2009/05/04 11:42:30 danielk1977 Exp $
 */
 #include "sqliteInt.h"
 
@@ -511,7 +511,7 @@ void sqlite3Update(
     */
     sqlite3GenerateConstraintChecks(pParse, pTab, iCur, regNewRowid,
                                     aRegIdx, chngRowid, 1,
-                                    onError, addr);
+                                    onError, addr, 0);
 
     /* Delete the old indices for the current record.
     */
@@ -528,7 +528,7 @@ void sqlite3Update(
     /* Create the new index entries and the new record.
     */
     sqlite3CompleteInsertion(pParse, pTab, iCur, regNewRowid, 
-                             aRegIdx, 1, -1, 0);
+                             aRegIdx, 1, -1, 0, 0);
   }
 
   /* Increment the row counter 
diff --git a/src/vdbe.c b/src/vdbe.c
index f7bf172d6..ec2c235db 100644
--- a/src/vdbe.c
+++ b/src/vdbe.c
@@ -43,7 +43,7 @@
 ** in this file for details.  If in doubt, do not deviate from existing
 ** commenting and indentation practices when changing or adding code.
 **
-** $Id: vdbe.c,v 1.840 2009/04/30 09:10:38 danielk1977 Exp $
+** $Id: vdbe.c,v 1.841 2009/05/04 11:42:30 danielk1977 Exp $
 */
 #include "sqliteInt.h"
 #include "vdbeInt.h"
@@ -3338,103 +3338,82 @@ case OP_Found: {        /* jump, in3 */
 
 /* Opcode: IsUnique P1 P2 P3 P4 *
 **
-** The P3 register contains an integer record number.  Call this
-** record number R.  The P4 register contains an index key created
-** using MakeRecord.  Call it K.
-**
-** P1 is an index.  So it has no data and its key consists of a
-** record generated by OP_MakeRecord where the last field is the 
+** Cursor P1 is open on an index.  So it has no data and its key consists 
+** of a record generated by OP_MakeRecord where the last field is the 
 ** rowid of the entry that the index refers to.
-** 
-** This instruction asks if there is an entry in P1 where the
-** fields matches K but the rowid is different from R.
-** If there is no such entry, then there is an immediate
-** jump to P2.  If any entry does exist where the index string
-** matches K but the record number is not R, then the record
-** number for that entry is written into P3 and control
-** falls through to the next instruction.
+**
+** The P3 register contains an integer record number. Call this record 
+** number R. Register P4 is the first in a set of N contiguous registers
+** that make up an unpacked index key that can be used with cursor P1.
+** The value of N can be inferred from the cursor. N includes the rowid
+** value appended to the end of the index record. This rowid value may
+** or may not be the same as R.
+**
+** If any of the N registers beginning with register P4 contains a NULL
+** value, jump immediately to P2.
+**
+** Otherwise, this instruction checks if cursor P1 contains an entry
+** where the first (N-1) fields match but the rowid value at the end
+** of the index entry is not R. If there is no such entry, control jumps
+** to instruction P2. Otherwise, the rowid of the conflicting index
+** entry is copied to register P3 and control falls through to the next
+** instruction.
 **
 ** See also: NotFound, NotExists, Found
 */
 case OP_IsUnique: {        /* jump, in3 */
-  int i = pOp->p1;
+  int ii;
   VdbeCursor *pCx;
   BtCursor *pCrsr;
-  Mem *pK;
-  i64 R;
+  int nField;
+  Mem *aMem = &p->aMem[pOp->p4.i];
 
-  /* Pop the value R off the top of the stack
-  */
+  /* Assert that the values of parameters P1 and P4 are in range. */
   assert( pOp->p4type==P4_INT32 );
   assert( pOp->p4.i>0 && pOp->p4.i<=p->nMem );
-  pK = &p->aMem[pOp->p4.i];
-  sqlite3VdbeMemIntegerify(pIn3);
-  R = pIn3->u.i;
-  assert( i>=0 && i<p->nCursor );
-  pCx = p->apCsr[i];
-  assert( pCx!=0 );
-  pCrsr = pCx->pCursor;
-  if( pCrsr!=0 ){
-    int res;
-    i64 v;                     /* The record number that matches K */
-    UnpackedRecord *pIdxKey;   /* Unpacked version of P4 */
+  assert( pOp->p1>=0 && pOp->p1<p->nCursor );
 
-    /* Make sure K is a string and make zKey point to K
-    */
-    assert( pK->flags & MEM_Blob );
-    pIdxKey = sqlite3VdbeRecordUnpack(pCx->pKeyInfo, pK->n, pK->z,
-                                      aTempRec, sizeof(aTempRec));
-    if( pIdxKey==0 ){
-      goto no_mem;
-    }
-    pIdxKey->flags |= UNPACKED_IGNORE_ROWID;
+  /* Find the index cursor. */
+  pCx = p->apCsr[pOp->p1];
+  assert( pCx->deferredMoveto==0 );
+  pCx->seekResult = 0;
+  pCx->cacheStatus = CACHE_STALE;
+  pCrsr = pCx->pCursor;
 
-    /* Search for an entry in P1 where all but the last rowid match K
-    ** If there is no such entry, jump immediately to P2.
-    */
-    assert( pCx->deferredMoveto==0 );
-    pCx->cacheStatus = CACHE_STALE;
-    rc = sqlite3BtreeMovetoUnpacked(pCrsr, pIdxKey, 0, 0, &res);
-    if( rc!=SQLITE_OK ){
-      sqlite3VdbeDeleteUnpackedRecord(pIdxKey);
-      goto abort_due_to_error;
-    }
-    if( res<0 ){
-      rc = sqlite3BtreeNext(pCrsr, &res);
-      if( res ){
-        pc = pOp->p2 - 1;
-        sqlite3VdbeDeleteUnpackedRecord(pIdxKey);
-        break;
-      }
-    }
-    rc = sqlite3VdbeIdxKeyCompare(pCx, pIdxKey, &res); 
-    sqlite3VdbeDeleteUnpackedRecord(pIdxKey);
-    if( rc!=SQLITE_OK ) goto abort_due_to_error;
-    if( res>0 ){
+  /* If any of the values are NULL, take the jump. */
+  nField = pCx->pKeyInfo->nField;
+  for(ii=0; ii<nField; ii++){
+    if( aMem[ii].flags & MEM_Null ){
       pc = pOp->p2 - 1;
+      pCrsr = 0;
       break;
     }
+  }
+  assert( (aMem[nField].flags & MEM_Null)==0 );
 
-    /* At this point, pCrsr is pointing to an entry in P1 where all but
-    ** the final entry (the rowid) matches K.  Check to see if the
-    ** final rowid column is different from R.  If it equals R then jump
-    ** immediately to P2.
-    */
-    rc = sqlite3VdbeIdxRowid(pCrsr, &v);
-    if( rc!=SQLITE_OK ){
-      goto abort_due_to_error;
-    }
-    if( v==R ){
+  if( pCrsr!=0 ){
+    UnpackedRecord r;                  /* B-Tree index search key */
+    i64 R;                             /* Rowid stored in register P3 */
+
+    /* Populate the index search key. */
+    r.pKeyInfo = pCx->pKeyInfo;
+    r.nField = nField + 1;
+    r.flags = UNPACKED_PREFIX_SEARCH;
+    r.aMem = aMem;
+
+    /* Extract the value of R from register P3. */
+    sqlite3VdbeMemIntegerify(pIn3);
+    R = pIn3->u.i;
+
+    /* Search the B-Tree index. If no conflicting record is found, jump
+    ** to P2. Otherwise, copy the rowid of the conflicting record to
+    ** register P3 and fall through to the next instruction.  */
+    rc = sqlite3BtreeMovetoUnpacked(pCrsr, &r, 0, 0, &pCx->seekResult);
+    if( (r.flags & UNPACKED_PREFIX_SEARCH) || r.rowid==R ){
       pc = pOp->p2 - 1;
-      break;
+    }else{
+      pIn3->u.i = r.rowid;
     }
-
-    /* The final varint of the key is different from R.  Store it back
-    ** into register R3.  (The record number of an entry that violates
-    ** a UNIQUE constraint.)
-    */
-    pIn3->u.i = v;
-    assert( pIn3->flags&MEM_Int );
   }
   break;
 }
@@ -3465,7 +3444,7 @@ case OP_NotExists: {        /* jump, in3 */
     assert( pIn3->flags & MEM_Int );
     assert( p->apCsr[i]->isTable );
     iKey = intToKey(pIn3->u.i);
-    rc = sqlite3BtreeMovetoUnpacked(pCrsr, 0, iKey, 0,&res);
+    rc = sqlite3BtreeMovetoUnpacked(pCrsr, 0, iKey, 0, &res);
     pC->lastRowid = pIn3->u.i;
     pC->rowidIsValid = res==0 ?1:0;
     pC->nullRow = 0;
@@ -3475,6 +3454,7 @@ case OP_NotExists: {        /* jump, in3 */
       pc = pOp->p2 - 1;
       assert( pC->rowidIsValid==0 );
     }
+    pC->seekResult = res;
   }else if( !pC->pseudoTable ){
     /* This happens when an attempt to open a read cursor on the 
     ** sqlite_master table returns SQLITE_EMPTY.
@@ -3482,6 +3462,7 @@ case OP_NotExists: {        /* jump, in3 */
     assert( pC->isTable );
     pc = pOp->p2 - 1;
     assert( pC->rowidIsValid==0 );
+    pC->seekResult = 0;
   }
   break;
 }
@@ -3724,6 +3705,7 @@ case OP_Insert: {
     pC->nullRow = 0;
   }else{
     int nZero;
+    int seekResult = ((pOp->p5 & OPFLAG_USESEEKRESULT) ? pC->seekResult : 0);
     if( pData->flags & MEM_Zero ){
       nZero = pData->u.nZero;
     }else{
@@ -3732,7 +3714,8 @@ case OP_Insert: {
     sqlite3BtreeSetCachedRowid(pC->pCursor, 0);
     rc = sqlite3BtreeInsert(pC->pCursor, 0, iKey,
                             pData->z, pData->n, nZero,
-                            pOp->p5 & OPFLAG_APPEND);
+                            pOp->p5 & OPFLAG_APPEND, seekResult
+    );
   }
   
   pC->rowidIsValid = 0;
@@ -4103,7 +4086,7 @@ case OP_Next: {        /* jump */
   break;
 }
 
-/* Opcode: IdxInsert P1 P2 P3 * *
+/* Opcode: IdxInsert P1 P2 P3 * P5
 **
 ** Register P2 holds a SQL index key made using the
 ** MakeRecord instructions.  This opcode writes that key
@@ -4128,7 +4111,9 @@ case OP_IdxInsert: {        /* in2 */
     if( rc==SQLITE_OK ){
       int nKey = pIn2->n;
       const char *zKey = pIn2->z;
-      rc = sqlite3BtreeInsert(pCrsr, zKey, nKey, "", 0, 0, pOp->p3);
+      rc = sqlite3BtreeInsert(pCrsr, zKey, nKey, "", 0, 0, pOp->p3, 
+          ((pOp->p5 & OPFLAG_USESEEKRESULT) ? pC->seekResult : 0)
+      );
       assert( pC->deferredMoveto==0 );
       pC->cacheStatus = CACHE_STALE;
     }
diff --git a/src/vdbeInt.h b/src/vdbeInt.h
index cbf867dd0..a86ed6922 100644
--- a/src/vdbeInt.h
+++ b/src/vdbeInt.h
@@ -15,7 +15,7 @@
 ** 6000 lines long) it was split up into several smaller files and
 ** this header information was factored out.
 **
-** $Id: vdbeInt.h,v 1.169 2009/04/22 02:15:48 drh Exp $
+** $Id: vdbeInt.h,v 1.170 2009/05/04 11:42:30 danielk1977 Exp $
 */
 #ifndef _VDBEINT_H_
 #define _VDBEINT_H_
@@ -80,6 +80,10 @@ struct VdbeCursor {
   sqlite3_vtab_cursor *pVtabCursor;  /* The cursor for a virtual table */
   const sqlite3_module *pModule;     /* Module for cursor pVtabCursor */
 
+  /* Result of last sqlite3BtreeMoveto() done by an OP_NotExists or 
+  ** OP_IsUnique opcode on this cursor. */
+  int seekResult;
+
   /* Cached information about the header for the data record that the
   ** cursor is currently pointing to.  Only valid if cacheValid is true.
   ** aRow might point to (ephemeral) data for the current row, or it might
diff --git a/src/vdbeaux.c b/src/vdbeaux.c
index 4bf842672..3e5232258 100644
--- a/src/vdbeaux.c
+++ b/src/vdbeaux.c
@@ -14,7 +14,7 @@
 ** to version 2.8.7, all this code was combined into the vdbe.c source file.
 ** But that file was getting too big so this subroutines were split out.
 **
-** $Id: vdbeaux.c,v 1.454 2009/04/22 15:32:59 drh Exp $
+** $Id: vdbeaux.c,v 1.455 2009/05/04 11:42:30 danielk1977 Exp $
 */
 #include "sqliteInt.h"
 #include "vdbeInt.h"
@@ -2496,6 +2496,18 @@ int sqlite3VdbeRecordCompare(
   }
   if( mem1.zMalloc ) sqlite3VdbeMemRelease(&mem1);
 
+  /* If the PREFIX_SEARCH flag is set and all fields except the final
+  ** rowid field were equal, then clear the PREFIX_SEARCH flag and set 
+  ** pPKey2->rowid to the value of the rowid field in (pKey1, nKey1).
+  ** This is used by the OP_IsUnique opcode.
+  */
+  if( (pPKey2->flags & UNPACKED_PREFIX_SEARCH) && i==(pPKey2->nField-1) ){
+    assert( idx1==szHdr1 && rc );
+    assert( mem1.flags & MEM_Int );
+    pPKey2->flags &= ~UNPACKED_PREFIX_SEARCH;
+    pPKey2->rowid = mem1.u.i;
+  }
+
   if( rc==0 ){
     /* rc==0 here means that one of the keys ran out of fields and
     ** all the fields up to that point were equal. If the UNPACKED_INCRKEY