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)

FossilOrigin-Name: ad4a6b1a91bcefd8a4c75e8dc99c1153c72c31a3

1 files changed, 29 insertions, 11 deletions

diff --git a/src/insert.c b/src/insert.c
index e69f9c85c..0d0bc0782 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.179 2007/03/29 00:08:25 drh Exp $
+** $Id: insert.c,v 1.180 2007/03/29 05:51:49 drh Exp $
 */
 #include "sqliteInt.h"
 
@@ -205,7 +205,7 @@ static void autoIncEnd(
     sqlite3VdbeOp3(v, OP_String8, 0, 0, pTab->zName, 0);
     sqlite3VdbeAddOp(v, OP_MemLoad, memId, 0);
     sqlite3VdbeAddOp(v, OP_MakeRecord, 2, 0);
-    sqlite3VdbeAddOp(v, OP_Insert, iCur, 0);
+    sqlite3VdbeAddOp(v, OP_Insert, iCur, OPFLAG_APPEND);
     sqlite3VdbeAddOp(v, OP_Close, iCur, 0);
   }
 }
@@ -346,6 +346,7 @@ void sqlite3Insert(
   int newIdx = -1;      /* Cursor for the NEW table */
   Db *pDb;              /* The database containing table being inserted into */
   int counterMem = 0;   /* Memory cell holding AUTOINCREMENT counter */
+  int appendFlag = 0;   /* True if the insert is likely to be an append */
   int iDb;
 
 #ifndef SQLITE_OMIT_TRIGGER
@@ -489,7 +490,7 @@ void sqlite3Insert(
       sqlite3VdbeAddOp(v, OP_MakeRecord, nColumn, 0);
       sqlite3VdbeAddOp(v, OP_NewRowid, srcTab, 0);
       sqlite3VdbeAddOp(v, OP_Pull, 1, 0);
-      sqlite3VdbeAddOp(v, OP_Insert, srcTab, 0);
+      sqlite3VdbeAddOp(v, OP_Insert, srcTab, OPFLAG_APPEND);
       sqlite3VdbeAddOp(v, OP_Return, 0, 0);
 
       /* The following code runs first because the GOTO at the very top
@@ -701,19 +702,30 @@ void sqlite3Insert(
       }else if( pSelect ){
         sqlite3VdbeAddOp(v, OP_Dup, nColumn - keyColumn - 1, 1);
       }else{
+        VdbeOp *pOp;
         sqlite3ExprCode(pParse, pList->a[keyColumn].pExpr);
+        pOp = sqlite3VdbeGetOp(v, sqlite3VdbeCurrentAddr(v) - 1);
+        if( pOp->opcode==OP_Null ){
+          appendFlag = 1;
+          pOp->opcode = OP_NewRowid;
+          pOp->p1 = base;
+          pOp->p2 = counterMem;
+        }
       }
       /* If the PRIMARY KEY expression is NULL, then use OP_NewRowid
       ** to generate a unique primary key value.
       */
-      sqlite3VdbeAddOp(v, OP_NotNull, -1, sqlite3VdbeCurrentAddr(v)+3);
-      sqlite3VdbeAddOp(v, OP_Pop, 1, 0);
-      sqlite3VdbeAddOp(v, OP_NewRowid, base, counterMem);
-      sqlite3VdbeAddOp(v, OP_MustBeInt, 0, 0);
+      if( !appendFlag ){
+        sqlite3VdbeAddOp(v, OP_NotNull, -1, sqlite3VdbeCurrentAddr(v)+3);
+        sqlite3VdbeAddOp(v, OP_Pop, 1, 0);
+        sqlite3VdbeAddOp(v, OP_NewRowid, base, counterMem);
+        sqlite3VdbeAddOp(v, OP_MustBeInt, 0, 0);
+      }
     }else if( IsVirtual(pTab) ){
       sqlite3VdbeAddOp(v, OP_Null, 0, 0);
     }else{
       sqlite3VdbeAddOp(v, OP_NewRowid, base, counterMem);
+      appendFlag = 1;
     }
     autoIncStep(pParse, counterMem);
 
@@ -761,7 +773,8 @@ void sqlite3Insert(
       sqlite3GenerateConstraintChecks(pParse, pTab, base, 0, keyColumn>=0,
                                      0, onError, endOfLoop);
       sqlite3CompleteInsertion(pParse, pTab, base, 0,0,0,
-                            (triggers_exist & TRIGGER_AFTER)!=0 ? newIdx : -1);
+                            (triggers_exist & TRIGGER_AFTER)!=0 ? newIdx : -1,
+                            appendFlag);
     }
   }
 
@@ -1172,7 +1185,8 @@ void sqlite3CompleteInsertion(
   char *aIdxUsed,     /* Which indices are used.  NULL means all are used */
   int rowidChng,      /* True if the record number will change */
   int isUpdate,       /* True for UPDATE, False for INSERT */
-  int newIdx          /* Index of NEW table for triggers.  -1 if none */
+  int newIdx,         /* Index of NEW table for triggers.  -1 if none */
+  int appendBias      /* True if this is likely to be an append */
 ){
   int i;
   Vdbe *v;
@@ -1203,6 +1217,9 @@ void sqlite3CompleteInsertion(
     pik_flags = OPFLAG_NCHANGE;
     pik_flags |= (isUpdate?OPFLAG_ISUPDATE:OPFLAG_LASTROWID);
   }
+  if( appendBias ){
+    pik_flags |= OPFLAG_APPEND;
+  }
   sqlite3VdbeAddOp(v, OP_Insert, base, pik_flags);
   if( !pParse->nested ){
     sqlite3VdbeChangeP3(v, -1, pTab->zName, P3_STATIC);
@@ -1515,7 +1532,8 @@ static int xferOptimization(
     addr1 = sqlite3VdbeAddOp(v, OP_Rowid, iSrc, 0);
   }
   sqlite3VdbeAddOp(v, OP_RowData, iSrc, 0);
-  sqlite3VdbeOp3(v, OP_Insert, iDest, OPFLAG_NCHANGE|OPFLAG_LASTROWID,
+  sqlite3VdbeOp3(v, OP_Insert, iDest,
+                    OPFLAG_NCHANGE|OPFLAG_LASTROWID|OPFLAG_APPEND,
                     pDest->zName, 0);
   sqlite3VdbeAddOp(v, OP_Next, iSrc, addr1);
   autoIncEnd(pParse, iDbDest, pDest, counterMem);
@@ -1545,7 +1563,7 @@ static int xferOptimization(
                     "UNIQUE constraint failed", P3_STATIC);
       sqlite3VdbeJumpHere(v, addr2);
     }
-    sqlite3VdbeAddOp(v, OP_IdxInsert, iDest, 0);
+    sqlite3VdbeAddOp(v, OP_IdxInsert, iDest, 1);
     sqlite3VdbeAddOp(v, OP_Next, iSrc, addr1+1);
     sqlite3VdbeJumpHere(v, addr1);
   }