When reusing pages as part of creating a new index, allocate the leaves from each free-list trunk page in ascending order, instead of trying to maximize localization for each individual allocation. This increases the chance that pages will be written to disk in ascending order by a large CREATE INDEX statement, improving overall performance.

FossilOrigin-Name: d045f8b2d44e388d8c4549ff02d4ca7eff4e2038

8 files changed, 35 insertions, 11 deletions

diff --git a/src/analyze.c b/src/analyze.c
index 810ed54d8..632fdc1ac 100644
--- a/src/analyze.c
+++ b/src/analyze.c
@@ -176,7 +176,7 @@ static void openStatTable(
           "CREATE TABLE %Q.%s(%s)", pDb->zName, zTab, aTable[i].zCols
       );
       aRoot[i] = pParse->regRoot;
-      aCreateTbl[i] = 1;
+      aCreateTbl[i] = OPFLAG_P2ISREG;
     }else{
       /* The table already exists. If zWhere is not NULL, delete all entries 
       ** associated with the table zWhere. If zWhere is NULL, delete the
diff --git a/src/btree.c b/src/btree.c
index c16eca5f6..7f1fd7e14 100644
--- a/src/btree.c
+++ b/src/btree.c
@@ -5926,7 +5926,8 @@ static int balance_nonroot(
   MemPage *pParent,               /* Parent page of siblings being balanced */
   int iParentIdx,                 /* Index of "the page" in pParent */
   u8 *aOvflSpace,                 /* page-size bytes of space for parent ovfl */
-  int isRoot                      /* True if pParent is a root-page */
+  int isRoot,                     /* True if pParent is a root-page */
+  int bBulk                       /* True if this call is part of a bulk load */
 ){
   BtShared *pBt;               /* The whole database */
   int nCell = 0;               /* Number of cells in apCell[] */
@@ -6257,7 +6258,7 @@ static int balance_nonroot(
       if( rc ) goto balance_cleanup;
     }else{
       assert( i>0 );
-      rc = allocateBtreePage(pBt, &pNew, &pgno, pgno, 0);
+      rc = allocateBtreePage(pBt, &pNew, &pgno, (bBulk ? 1 : pgno), 0);
       if( rc ) goto balance_cleanup;
       apNew[i] = pNew;
       nNew++;
@@ -6707,7 +6708,7 @@ static int balance(BtCursor *pCur){
           ** pSpace buffer passed to the latter call to balance_nonroot().
           */
           u8 *pSpace = sqlite3PageMalloc(pCur->pBt->pageSize);
-          rc = balance_nonroot(pParent, iIdx, pSpace, iPage==1);
+          rc = balance_nonroot(pParent, iIdx, pSpace, iPage==1, pCur->hints);
           if( pFree ){
             /* If pFree is not NULL, it points to the pSpace buffer used 
             ** by a previous call to balance_nonroot(). Its contents are
@@ -8294,3 +8295,13 @@ int sqlite3BtreeSetVersion(Btree *pBtree, int iVersion){
   pBt->btsFlags &= ~BTS_NO_WAL;
   return rc;
 }
+
+/*
+** set the mask of hint flags for cursor pCsr. Currently the only valid
+** values are 0 and BTREE_BULKLOAD.
+*/
+void sqlite3BtreeCursorHints(BtCursor *pCsr, unsigned int mask){
+  assert( mask==BTREE_BULKLOAD || mask==0 );
+  pCsr->hints = mask;
+}
+
diff --git a/src/btree.h b/src/btree.h
index 9832001b7..95897d566 100644
--- a/src/btree.h
+++ b/src/btree.h
@@ -135,6 +135,12 @@ int sqlite3BtreeUpdateMeta(Btree*, int idx, u32 value);
 #define BTREE_USER_VERSION        6
 #define BTREE_INCR_VACUUM         7
 
+/*
+** Values that may be OR'd together to form the second argument of an
+** sqlite3BtreeCursorHints() call.
+*/
+#define BTREE_BULKLOAD 0x00000001
+
 int sqlite3BtreeCursor(
   Btree*,                              /* BTree containing table to open */
   int iTable,                          /* Index of root page */
@@ -178,8 +184,8 @@ struct Pager *sqlite3BtreePager(Btree*);
 int sqlite3BtreePutData(BtCursor*, u32 offset, u32 amt, void*);
 void sqlite3BtreeCacheOverflow(BtCursor *);
 void sqlite3BtreeClearCursor(BtCursor *);
-
 int sqlite3BtreeSetVersion(Btree *pBt, int iVersion);
+void sqlite3BtreeCursorHints(BtCursor *, unsigned int mask);
 
 #ifndef NDEBUG
 int sqlite3BtreeCursorIsValid(BtCursor*);
diff --git a/src/btreeInt.h b/src/btreeInt.h
index 0d2149796..b157decec 100644
--- a/src/btreeInt.h
+++ b/src/btreeInt.h
@@ -510,6 +510,7 @@ struct BtCursor {
 #ifndef SQLITE_OMIT_INCRBLOB
   u8 isIncrblobHandle;      /* True if this cursor is an incr. io handle */
 #endif
+  u8 hints;                             /* As configured by CursorSetHints() */
   i16 iPage;                            /* Index of current page in apPage */
   u16 aiIdx[BTCURSOR_MAX_DEPTH];        /* Current index in apPage[i] */
   MemPage *apPage[BTCURSOR_MAX_DEPTH];  /* Pages from root to current page */
diff --git a/src/build.c b/src/build.c
index 9f13b7b11..776ffa4db 100644
--- a/src/build.c
+++ b/src/build.c
@@ -1581,7 +1581,7 @@ void sqlite3EndTable(
 
       assert(pParse->nTab==1);
       sqlite3VdbeAddOp3(v, OP_OpenWrite, 1, pParse->regRoot, iDb);
-      sqlite3VdbeChangeP5(v, 1);
+      sqlite3VdbeChangeP5(v, OPFLAG_P2ISREG);
       pParse->nTab = 2;
       sqlite3SelectDestInit(&dest, SRT_Table, 1);
       sqlite3Select(pParse, pSelect, &dest);
@@ -2397,9 +2397,7 @@ static void sqlite3RefillIndex(Parse *pParse, Index *pIndex, int memRootPage){
   pKey = sqlite3IndexKeyinfo(pParse, pIndex);
   sqlite3VdbeAddOp4(v, OP_OpenWrite, iIdx, tnum, iDb, 
                     (char *)pKey, P4_KEYINFO_HANDOFF);
-  if( memRootPage>=0 ){
-    sqlite3VdbeChangeP5(v, 1);
-  }
+  sqlite3VdbeChangeP5(v, OPFLAG_BULKCSR|((memRootPage>=0)?OPFLAG_P2ISREG:0));
 
 #ifndef SQLITE_OMIT_MERGE_SORT
   /* Open the sorter cursor if we are to use one. */
diff --git a/src/sqliteInt.h b/src/sqliteInt.h
index c525ebd16..b3cdb2363 100644
--- a/src/sqliteInt.h
+++ b/src/sqliteInt.h
@@ -2317,6 +2317,8 @@ struct AuthContext {
 #define OPFLAG_CLEARCACHE    0x20    /* Clear pseudo-table cache in OP_Column */
 #define OPFLAG_LENGTHARG     0x40    /* OP_Column only used for length() */
 #define OPFLAG_TYPEOFARG     0x80    /* OP_Column only used for typeof() */
+#define OPFLAG_BULKCSR       0x01    /* OP_Open** used to open bulk cursor */
+#define OPFLAG_P2ISREG       0x02    /* P2 to OP_Open** is a register number */
 
 /*
  * Each trigger present in the database schema is stored as an instance of
diff --git a/src/test_vfs.c b/src/test_vfs.c
index fd2aa9fb0..93c556b56 100644
--- a/src/test_vfs.c
+++ b/src/test_vfs.c
@@ -361,7 +361,8 @@ static int tvfsWrite(
 
   if( p->pScript && p->mask&TESTVFS_WRITE_MASK ){
     tvfsExecTcl(p, "xWrite", 
-        Tcl_NewStringObj(pFd->zFilename, -1), pFd->pShmId, 0
+        Tcl_NewStringObj(pFd->zFilename, -1), pFd->pShmId, 
+        Tcl_NewWideIntObj(iOfst)
     );
     tvfsResultCode(p, &rc);
   }
diff --git a/src/vdbe.c b/src/vdbe.c
index 19c0255b8..12e732514 100644
--- a/src/vdbe.c
+++ b/src/vdbe.c
@@ -3120,6 +3120,9 @@ case OP_OpenWrite: {
   VdbeCursor *pCur;
   Db *pDb;
 
+  assert( (pOp->p5&(OPFLAG_P2ISREG|OPFLAG_BULKCSR))==pOp->p5 );
+  assert( pOp->opcode==OP_OpenWrite || pOp->p5==0 );
+
   if( p->expired ){
     rc = SQLITE_ABORT;
     break;
@@ -3143,7 +3146,7 @@ case OP_OpenWrite: {
   }else{
     wrFlag = 0;
   }
-  if( pOp->p5 ){
+  if( pOp->p5 & OPFLAG_P2ISREG ){
     assert( p2>0 );
     assert( p2<=p->nMem );
     pIn2 = &aMem[p2];
@@ -3174,6 +3177,8 @@ case OP_OpenWrite: {
   pCur->isOrdered = 1;
   rc = sqlite3BtreeCursor(pX, p2, wrFlag, pKeyInfo, pCur->pCursor);
   pCur->pKeyInfo = pKeyInfo;
+  assert( OPFLAG_BULKCSR==BTREE_BULKLOAD );
+  sqlite3BtreeCursorHints(pCur->pCursor, (pOp->p5 & OPFLAG_BULKCSR));
 
   /* Since it performs no memory allocation or IO, the only value that
   ** sqlite3BtreeCursor() may return is SQLITE_OK. */