From a20fde64ebdcfa64ef75f5259b429615b0d217ed Mon Sep 17 00:00:00 2001 From: dan Date: Tue, 12 Jul 2011 14:28:05 +0000 Subject: [PATCH] Experimental support for speeding up CREATE INDEX commands using an offline merge sort. FossilOrigin-Name: 30dbf0feab0323250404e0741ac2716bcb6b0cbe --- main.mk | 5 +- manifest | 27 ++- manifest.uuid | 2 +- src/build.c | 21 +- src/vdbe.c | 46 ++-- src/vdbeInt.h | 8 + src/vdbeaux.c | 1 + src/vdbesort.c | 533 +++++++++++++++++++++++++++++++++++++++++++++++ test/index4.test | 70 +++++++ 9 files changed, 685 insertions(+), 28 deletions(-) create mode 100644 src/vdbesort.c create mode 100644 test/index4.test diff --git a/main.mk b/main.mk index 16bb7115c9..58b0c98769 100644 --- a/main.mk +++ b/main.mk @@ -65,8 +65,8 @@ LIBOBJ+= alter.o analyze.o attach.o auth.o \ random.o resolve.o rowset.o rtree.o select.o status.o \ table.o tokenize.o trigger.o \ update.o util.o vacuum.o \ - vdbe.o vdbeapi.o vdbeaux.o vdbeblob.o vdbemem.o vdbetrace.o \ - wal.o walker.o where.o utf.o vtab.o + vdbe.o vdbeapi.o vdbeaux.o vdbeblob.o vdbemem.o vdbesort.o \ + vdbetrace.o wal.o walker.o where.o utf.o vtab.o @@ -155,6 +155,7 @@ SRC = \ $(TOP)/src/vdbeaux.c \ $(TOP)/src/vdbeblob.c \ $(TOP)/src/vdbemem.c \ + $(TOP)/src/vdbesort.c \ $(TOP)/src/vdbetrace.c \ $(TOP)/src/vdbeInt.h \ $(TOP)/src/vtab.c \ diff --git a/manifest b/manifest index e631fa3a74..cf17e497ce 100644 --- a/manifest +++ b/manifest @@ -1,5 +1,5 @@ -C Update\sthe\sTCL\scommands\sfor\ssetting\swindows\smanditory\slocks.\nAdd\stest\scases\sfor\smanditory\slock\sdelays\sunder\swindows. -D 2011-07-11T23:45:44.051 +C Experimental\ssupport\sfor\sspeeding\sup\sCREATE\sINDEX\scommands\susing\san\soffline\smerge\ssort. +D 2011-07-12T14:28:05.335 F Makefile.arm-wince-mingw32ce-gcc d6df77f1f48d690bd73162294bbba7f59507c72f F Makefile.in c1d7a7f4fd8da6b1815032efca950e3d5125407e F Makefile.linux-gcc 91d710bdc4998cb015f39edf3cb314ec4f4d7e23 @@ -104,7 +104,7 @@ F ext/rtree/tkt3363.test 142ab96eded44a3615ec79fba98c7bde7d0f96de F ext/rtree/viewrtree.tcl eea6224b3553599ae665b239bd827e182b466024 F install-sh 9d4de14ab9fb0facae2f48780b874848cbf2f895 x F ltmain.sh 3ff0879076df340d2e23ae905484d8c15d5fdea8 -F main.mk d81d86f0f70444f3abc241eccf5ace4a79ff9b69 +F main.mk df1e47e4bc886f556b39a8cdb9dc3f6fb6810d64 F mkdll.sh 7d09b23c05d56532e9d44a50868eb4b12ff4f74a F mkextu.sh 416f9b7089d80e5590a29692c9d9280a10dbad9f F mkextw.sh 4123480947681d9b434a5e7b1ee08135abe409ac @@ -127,7 +127,7 @@ F src/btmutex.c 976f45a12e37293e32cae0281b15a21d48a8aaa7 F src/btree.c 8c46f0ab69ad9549c75a3a91fed87abdaa743e2f F src/btree.h f5d775cd6cfc7ac32a2535b70e8d2af48ef5f2ce F src/btreeInt.h 67978c014fa4f7cc874032dd3aacadd8db656bc3 -F src/build.c 5e614e586d9f8a81c16c80b545b9e1747f96c1bb +F src/build.c 8aca0539bac544caf3ecb2baac1e7bdc1bfc80e6 F src/callback.c 0425c6320730e6d3981acfb9202c1bed9016ad1a F src/complete.c dc1d136c0feee03c2f7550bafc0d29075e36deac F src/ctime.c 7deec4534f3b5a0c3b4a4cbadf809d321f64f9c4 @@ -238,13 +238,14 @@ F src/update.c 74a6cfb34e9732c1e2a86278b229913b4b51eeec F src/utf.c c53eb7404b3eb5c1cbb5655c6a7a0e0ce6bd50f0 F src/util.c 0f33bbbdfcc4a2d8cf20c3b2a16ffc3b57c58a70 F src/vacuum.c 05513dca036a1e7848fe18d5ed1265ac0b32365e -F src/vdbe.c a9ced64f380bbd8b04da3a1c3a9602d3942704b5 +F src/vdbe.c 88a7068472bafb29db500a167eef533d5f709cdc F src/vdbe.h 5cf09e7ee8a3f7d93bc51f196a96550786afe7a1 -F src/vdbeInt.h ad84226cc0adcb1185c22b70696b235a1678bb45 +F src/vdbeInt.h fb6c86006de1c0f249ea9dc14263ad0c357cfc24 F src/vdbeapi.c 11dc47987abacb76ad016dcf5abc0dc422482a98 -F src/vdbeaux.c 4d100407e3c72e163854aff8903d19d5ecdf46c0 +F src/vdbeaux.c 8fb978eb73a97b34d352dd3ef3bff35b1b3fa7e9 F src/vdbeblob.c f024f0bf420f36b070143c32b15cc7287341ffd3 F src/vdbemem.c 0498796b6ffbe45e32960d6a1f5adfb6e419883b +F src/vdbesort.c f07d526dfb0606e51f7588b26c9d401092318c39 F src/vdbetrace.c 5d0dc3d5fd54878cc8d6d28eb41deb8d5885b114 F src/vtab.c 901791a47318c0562cd0c676a2c6ff1bc530e582 F src/wal.c 0c70ad7b1cac6005fa5e2cbefd23ee05e391c290 @@ -510,6 +511,7 @@ F test/incrvacuum_ioerr.test 57d2f5777ab13fa03b87b262a4ea1bad5cfc0291 F test/index.test b5429732b3b983fa810e3ac867d7ca85dae35097 F test/index2.test ee83c6b5e3173a3d7137140d945d9a5d4fdfb9d6 F test/index3.test 423a25c789fc8cc51aaf2a4370bbdde2d9e9eed7 +F test/index4.test 8d737e87536cba23d4567096b6432116e2ba896f F test/indexedby.test be501e381b82b2f8ab406309ba7aac46e221f4ad F test/init.test 15c823093fdabbf7b531fe22cf037134d09587a7 F test/insert.test aef273dd1cee84cc92407469e6bd1b3cdcb76908 @@ -952,7 +954,10 @@ F tool/symbols.sh caaf6ccc7300fd43353318b44524853e222557d5 F tool/tostr.awk 11760e1b94a5d3dcd42378f3cc18544c06cfa576 F tool/vdbe-compress.tcl d70ea6d8a19e3571d7ab8c9b75cba86d1173ff0f F tool/warnings.sh 2ebae31e1eb352696f3c2f7706a34c084b28c262 -P c20aca06610407c197ea50ea77c2591aacf2252a -R 4c1b031b9c10734fc2cbb78ed1f104dd -U drh -Z 4f5517f8772eb0c19d9bc59edbaff4cc +P 03af4c175c6ba303ec0a5be25fd42771e38f7347 +R 55fa78a5c4888948b8391ce686e6076d +T *branch * experimental +T *sym-experimental * +T -sym-trunk * +U dan +Z 97a803d50902eb873dfd6c6b8aa1a07e diff --git a/manifest.uuid b/manifest.uuid index 688cc99f9e..fcc2554fd0 100644 --- a/manifest.uuid +++ b/manifest.uuid @@ -1 +1 @@ -03af4c175c6ba303ec0a5be25fd42771e38f7347 \ No newline at end of file +30dbf0feab0323250404e0741ac2716bcb6b0cbe \ No newline at end of file diff --git a/src/build.c b/src/build.c index 455b35b56e..7152ab8eb4 100644 --- a/src/build.c +++ b/src/build.c @@ -2308,6 +2308,7 @@ static void sqlite3RefillIndex(Parse *pParse, Index *pIndex, int memRootPage){ Table *pTab = pIndex->pTable; /* The table that is indexed */ int iTab = pParse->nTab++; /* Btree cursor used for pTab */ int iIdx = pParse->nTab++; /* Btree cursor used for pIndex */ + int iSorter = pParse->nTab++; /* Btree cursor used for sorting */ int addr1; /* Address of top of loop */ int tnum; /* Root page of index */ Vdbe *v; /* Generate code into this virtual machine */ @@ -2341,10 +2342,24 @@ static void sqlite3RefillIndex(Parse *pParse, Index *pIndex, int memRootPage){ if( memRootPage>=0 ){ sqlite3VdbeChangeP5(v, 1); } + + /* Open the sorter cursor. */ + sqlite3VdbeAddOp4(v, OP_OpenSorter, iSorter, 0, 0, (char*)pKey, P4_KEYINFO); + + /* Open the table. Loop through all rows of the table, inserting index + ** records into the sorter. */ sqlite3OpenTable(pParse, iTab, iDb, pTab, OP_OpenRead); addr1 = sqlite3VdbeAddOp2(v, OP_Rewind, iTab, 0); regRecord = sqlite3GetTempReg(pParse); regIdxKey = sqlite3GenerateIndexKey(pParse, pIndex, iTab, regRecord, 1); + sqlite3VdbeAddOp2(v, OP_IdxInsert, iSorter, regRecord); + sqlite3VdbeAddOp2(v, OP_Next, iTab, addr1+1); + sqlite3VdbeJumpHere(v, addr1); + + /* Rewind the sorter. Loop through index records in sorted order. */ + addr1 = sqlite3VdbeAddOp2(v, OP_Rewind, iSorter, 0); + sqlite3VdbeAddOp2(v, OP_RowKey, iSorter, regRecord); + if( pIndex->onError!=OE_None ){ const int regRowid = regIdxKey + pIndex->nColumn; const int j2 = sqlite3VdbeCurrentAddr(v) + 2; @@ -2363,12 +2378,14 @@ static void sqlite3RefillIndex(Parse *pParse, Index *pIndex, int memRootPage){ sqlite3HaltConstraint( pParse, OE_Abort, "indexed columns are not unique", P4_STATIC); } - sqlite3VdbeAddOp2(v, OP_IdxInsert, iIdx, regRecord); + sqlite3VdbeAddOp3(v, OP_IdxInsert, iIdx, regRecord, 1); sqlite3VdbeChangeP5(v, OPFLAG_USESEEKRESULT); sqlite3ReleaseTempReg(pParse, regRecord); - sqlite3VdbeAddOp2(v, OP_Next, iTab, addr1+1); + sqlite3VdbeAddOp2(v, OP_Next, iSorter, addr1+1); sqlite3VdbeJumpHere(v, addr1); + sqlite3VdbeAddOp1(v, OP_Close, iTab); + sqlite3VdbeAddOp1(v, OP_Close, iSorter); sqlite3VdbeAddOp1(v, OP_Close, iIdx); } diff --git a/src/vdbe.c b/src/vdbe.c index bec422a988..7cd90f5248 100644 --- a/src/vdbe.c +++ b/src/vdbe.c @@ -3144,6 +3144,7 @@ case OP_OpenWrite: { ** by this opcode will be used for automatically created transient ** indices in joins. */ +case OP_OpenSorter: case OP_OpenAutoindex: case OP_OpenEphemeral: { VdbeCursor *pCx; @@ -3154,12 +3155,14 @@ case OP_OpenEphemeral: { SQLITE_OPEN_DELETEONCLOSE | SQLITE_OPEN_TRANSIENT_DB; + int btflags = BTREE_OMIT_JOURNAL | pOp->p5; + if( pOp->opcode!=OP_OpenSorter ) btflags |= BTREE_SINGLE; + assert( pOp->p1>=0 ); pCx = allocateCursor(p, pOp->p1, pOp->p2, -1, 1); if( pCx==0 ) goto no_mem; pCx->nullRow = 1; - rc = sqlite3BtreeOpen(db->pVfs, 0, db, &pCx->pBt, - BTREE_OMIT_JOURNAL | BTREE_SINGLE | pOp->p5, vfsFlags); + rc = sqlite3BtreeOpen(db->pVfs, 0, db, &pCx->pBt, btflags, vfsFlags); if( rc==SQLITE_OK ){ rc = sqlite3BtreeBeginTrans(pCx->pBt, 1); } @@ -3178,7 +3181,7 @@ case OP_OpenEphemeral: { rc = sqlite3BtreeCursor(pCx->pBt, pgno, 1, (KeyInfo*)pOp->p4.z, pCx->pCursor); pCx->pKeyInfo = pOp->p4.pKeyInfo; - pCx->pKeyInfo->enc = ENC(p->db); + pCx->pKeyInfo->enc = ENC(db); } pCx->isTable = 0; }else{ @@ -3188,6 +3191,9 @@ case OP_OpenEphemeral: { } pCx->isOrdered = (pOp->p5!=BTREE_UNORDERED); pCx->isIndex = !pCx->isTable; + if( rc==SQLITE_OK && pOp->opcode==OP_OpenSorter ){ + rc = sqlite3VdbeSorterInit(db, pCx); + } break; } @@ -4077,6 +4083,12 @@ case OP_RowData: { assert( pC!=0 ); assert( pC->nullRow==0 ); assert( pC->pseudoTableReg==0 ); + + if( pC->pSorter ){ + rc = sqlite3VdbeSorterRowkey(db, pC, pOut); + break; + } + assert( pC->pCursor!=0 ); pCrsr = pC->pCursor; assert( sqlite3BtreeCursorIsValid(pCrsr) ); @@ -4257,7 +4269,9 @@ case OP_Rewind: { /* jump */ pC = p->apCsr[pOp->p1]; assert( pC!=0 ); res = 1; - if( (pCrsr = pC->pCursor)!=0 ){ + if( pC->pSorter ){ + rc = sqlite3VdbeSorterRewind(db, pC, &res); + }else if( (pCrsr = pC->pCursor)!=0 ){ rc = sqlite3BtreeFirst(pCrsr, &res); pC->atFirst = res==0 ?1:0; pC->deferredMoveto = 0; @@ -4311,17 +4325,23 @@ case OP_Next: { /* jump */ if( pC==0 ){ break; /* See ticket #2273 */ } - pCrsr = pC->pCursor; - if( pCrsr==0 ){ - pC->nullRow = 1; - break; + if( pC->pSorter ){ + assert( pOp->opcode==OP_Next ); + rc = sqlite3VdbeSorterNext(db, pC, &res); + }else{ + pCrsr = pC->pCursor; + if( pCrsr==0 ){ + pC->nullRow = 1; + break; + } + res = 1; + assert( pC->deferredMoveto==0 ); + rc = pOp->opcode==OP_Next ? sqlite3BtreeNext(pCrsr, &res) : + sqlite3BtreePrevious(pCrsr, &res); } - res = 1; - assert( pC->deferredMoveto==0 ); - rc = pOp->opcode==OP_Next ? sqlite3BtreeNext(pCrsr, &res) : - sqlite3BtreePrevious(pCrsr, &res); pC->nullRow = (u8)res; pC->cacheStatus = CACHE_STALE; + if( res==0 ){ pc = pOp->p2 - 1; if( pOp->p5 ) p->aCounter[pOp->p5-1]++; @@ -4354,6 +4374,8 @@ case OP_IdxInsert: { /* in2 */ assert( pOp->p1>=0 && pOp->p1nCursor ); pC = p->apCsr[pOp->p1]; assert( pC!=0 ); + rc = sqlite3VdbeSorterWrite(db, pC); + if( rc!=SQLITE_OK ) goto abort_due_to_error; pIn2 = &aMem[pOp->p2]; assert( pIn2->flags & MEM_Blob ); pCrsr = pC->pCursor; diff --git a/src/vdbeInt.h b/src/vdbeInt.h index 0aeb3af7a9..4d404967b5 100644 --- a/src/vdbeInt.h +++ b/src/vdbeInt.h @@ -30,6 +30,9 @@ typedef struct VdbeOp Op; */ typedef unsigned char Bool; +/* Opaque type used by code in vdbesort.c */ +typedef struct VdbeSorter VdbeSorter; + /* ** A cursor is a pointer into a single BTree within a database file. ** The cursor can seek to a BTree entry with a particular key, or @@ -61,6 +64,7 @@ struct VdbeCursor { i64 seqCount; /* Sequence counter */ i64 movetoTarget; /* Argument to the deferred sqlite3BtreeMoveto() */ i64 lastRowid; /* Last rowid from a Next or NextIdx operation */ + VdbeSorter *pSorter; /* Sorter object for OP_OpenSorter cursors */ /* Result of last sqlite3BtreeMoveto() done by an OP_NotExists or ** OP_IsUnique opcode on this cursor. */ @@ -388,6 +392,10 @@ void sqlite3VdbeFrameDelete(VdbeFrame*); int sqlite3VdbeFrameRestore(VdbeFrame *); void sqlite3VdbeMemStoreType(Mem *pMem); +int sqlite3VdbeSorterInit(sqlite3 *, VdbeCursor *); +int sqlite3VdbeSorterWrite(sqlite3 *, VdbeCursor *); +void sqlite3VdbeSorterClose(sqlite3 *, VdbeCursor *); + #if !defined(SQLITE_OMIT_SHARED_CACHE) && SQLITE_THREADSAFE>0 void sqlite3VdbeEnter(Vdbe*); void sqlite3VdbeLeave(Vdbe*); diff --git a/src/vdbeaux.c b/src/vdbeaux.c index 989a8003d3..95c65181e2 100644 --- a/src/vdbeaux.c +++ b/src/vdbeaux.c @@ -1565,6 +1565,7 @@ void sqlite3VdbeFreeCursor(Vdbe *p, VdbeCursor *pCx){ if( pCx==0 ){ return; } + sqlite3VdbeSorterClose(p->db, pCx); if( pCx->pBt ){ sqlite3BtreeClose(pCx->pBt); /* The pCx->pCursor will be close automatically, if it exists, by diff --git a/src/vdbesort.c b/src/vdbesort.c new file mode 100644 index 0000000000..fc6591789d --- /dev/null +++ b/src/vdbesort.c @@ -0,0 +1,533 @@ +/* +** 2011 July 9 +** +** The author disclaims copyright to this source code. In place of +** a legal notice, here is a blessing: +** +** May you do good and not evil. +** May you find forgiveness for yourself and forgive others. +** May you share freely, never taking more than you give. +** +************************************************************************* +** This file contains code for the VdbeSorter object, used in concert with +** a VdbeCursor to sort large numbers of keys (as may be required, for +** example, by CREATE INDEX statements on tables too large to fit in main +** memory). +*/ + +#include "sqliteInt.h" +#include "vdbeInt.h" + +typedef struct VdbeSorterIter VdbeSorterIter; + +/* +** The aIter[] and aTree[] arrays are used to iterate through the sorter +** contents after it has been populated. To iterate through the sorter +** contents, the contents of the nRoot b-trees must be incrementally merged. +** +** The first nRoot elements of the aIter[] array contain cursors open +** on each of the b-trees. An aIter[] element either points to a valid +** key or else is at EOF. For the purposes of the paragraphs below, we +** assume that the array is actually N elements in size, where N is the +** smallest power of 2 greater to or equal to nRoot. The extra aIter[] +** elements are treated as if they are empty trees (always at EOF). +** +** The aTree[] array is N elements in size. The value of N is stored in +** the VdbeSorter.nTree variable. +** +** The final (N/2) elements of aTree[] contain the results of comparing +** pairs of iterator keys together. Element i contains the result of +** comparing aIter[2*i-N] and aIter[2*i-N+1]. Whichever key is smaller, the +** aTree element is set to the index of it. +** +** For the purposes of this comparison, EOF is considered greater than any +** other key value. If the keys are equal (only possible with two EOF +** values), it doesn't matter which index is stored. +** +** The (N/4) elements of aTree[] that preceed the final (N/2) described +** above contains the index of the smallest of each block of 4 iterators. +** And so on. So that aTree[1] contains the index of the iterator that +** currently points to the smallest key value. aTree[0] is unused. +** +** Example: +** +** aIter[0] -> Banana +** aIter[1] -> Feijoa +** aIter[2] -> Elderberry +** aIter[3] -> Currant +** aIter[4] -> Grapefruit +** aIter[5] -> Apple +** aIter[6] -> Durian +** aIter[7] -> EOF +** +** aTree[] = { X, 5 0, 5 0, 3, 5, 6 } +** +** The current element is "Apple" (the value of the key indicated by +** iterator 5). When the Next() operation is invoked, iterator 5 will +** be advanced to the next key in its segment. Say the next key is +** "Eggplant": +** +** aIter[5] -> Eggplant +** +** The contents of aTree[] are updated first by comparing the new iterator +** 5 key to the current key of iterator 4 (still "Grapefruit"). The iterator +** 5 value is still smaller, so aTree[6] is set to 5. And so on up the tree. +** The value of iterator 6 - "Durian" - is now smaller than that of iterator +** 5, so aTree[3] is set to 6. Key 0 is smaller than key 6 (BananaaRoot, (p->nRoot+1)*sizeof(int)); + if( !aNew ) return SQLITE_NOMEM; + aNew[p->nRoot] = iRoot; + p->nRoot++; + p->aRoot = aNew; + return SQLITE_OK; +} + +/* +** Close any cursor and free all memory belonging to the VdbeSorterIter +** object passed as the second argument. All structure fields are set +** to zero before returning. +*/ +static void vdbeSorterIterZero(sqlite3 *db, VdbeSorterIter *pIter){ + if( pIter->bFree ){ + sqlite3DbFree(db, pIter->aKey); + } + if( pIter->pCsr ){ + sqlite3BtreeCloseCursor(pIter->pCsr); + sqlite3DbFree(db, pIter->pCsr); + } + memset(pIter, 0, sizeof(VdbeSorterIter)); +} + +/* +** Fetch the current key pointed to by the b-tree cursor managed by pIter +** into variables VdbeSorterIter.aKey and VdbeSorterIter.nKey. Return +** SQLITE_OK if no error occurs, or an SQLite error code otherwise. +*/ +static int vdbeSorterIterLoadkey(sqlite3 *db, VdbeSorterIter *pIter){ + int rc = SQLITE_OK; + assert( pIter->pCsr ); + if( sqlite3BtreeEof(pIter->pCsr) ){ + vdbeSorterIterZero(db, pIter); + }else{ + i64 nByte64; + sqlite3BtreeKeySize(pIter->pCsr, &nByte64); + + if( pIter->bFree ){ + sqlite3DbFree(db, pIter->aKey); + pIter->aKey = 0; + } + + pIter->nKey = nByte64; + pIter->aKey = sqlite3DbMallocRaw(db, pIter->nKey); + pIter->bFree = 1; + if( pIter->aKey==0 ){ + rc = SQLITE_NOMEM; + }else{ + rc = sqlite3BtreeKey(pIter->pCsr, 0, pIter->nKey, pIter->aKey); + } + + } + return rc; +} + +/* +** Initialize iterator pIter to scan through the b-tree with root page +** iRoot. This function leaves the iterator pointing to the first key +** in the b-tree (or EOF if the b-tree is empty). +*/ +static int vdbeSorterIterInit( + sqlite3 *db, /* Database handle */ + VdbeCursor *pCsr, /* Vdbe cursor handle */ + int iRoot, /* Root page of b-tree to iterate */ + VdbeSorterIter *pIter /* Pointer to iterator to initialize */ +){ + VdbeSorter *pSorter = pCsr->pSorter; + int rc; + + pIter->pCsr = (BtCursor *)sqlite3DbMallocZero(db, sqlite3BtreeCursorSize()); + if( !pIter->pCsr ){ + rc = SQLITE_NOMEM; + }else{ + rc = sqlite3BtreeCursor(pCsr->pBt, iRoot, 1, pCsr->pKeyInfo, pIter->pCsr); + } + if( rc==SQLITE_OK ){ + int bDummy; + rc = sqlite3BtreeFirst(pIter->pCsr, &bDummy); + } + if( rc==SQLITE_OK ){ + rc = vdbeSorterIterLoadkey(db, pIter); + } + + return rc; +} + +/* +** Advance iterator pIter to the next key in its b-tree. +*/ +static int vdbeSorterIterNext( + sqlite3 *db, + VdbeCursor *pCsr, + VdbeSorterIter *pIter +){ + int rc; + int bDummy; + VdbeSorter *pSorter = pCsr->pSorter; + + rc = sqlite3BtreeNext(pIter->pCsr, &bDummy); + if( rc==SQLITE_OK ){ + rc = vdbeSorterIterLoadkey(db, pIter); + } + + return rc; +} + +/* +** This function is called to compare two iterator keys when merging +** multiple b-tree segments. Parameter iOut is the index of the aTree[] +** value to recalculate. +*/ +static int vdbeSorterDoCompare(VdbeCursor *pCsr, int iOut){ + VdbeSorter *pSorter = pCsr->pSorter; + int i1; + int i2; + int iRes; + VdbeSorterIter *p1; + VdbeSorterIter *p2; + + assert( iOutnTree && iOut>0 ); + + if( iOut>=(pSorter->nTree/2) ){ + i1 = (iOut - pSorter->nTree/2) * 2; + i2 = i1 + 1; + }else{ + i1 = pSorter->aTree[iOut*2]; + i2 = pSorter->aTree[iOut*2+1]; + } + + p1 = &pSorter->aIter[i1]; + p2 = &pSorter->aIter[i2]; + + if( p1->pCsr==0 ){ + iRes = i2; + }else if( p2->pCsr==0 ){ + iRes = i1; + }else{ + char aSpace[150]; + UnpackedRecord *r1; + + r1 = sqlite3VdbeRecordUnpack( + pCsr->pKeyInfo, p1->nKey, p1->aKey, aSpace, sizeof(aSpace) + ); + if( r1==0 ) return SQLITE_NOMEM; + + if( sqlite3VdbeRecordCompare(p2->nKey, p2->aKey, r1)>=0 ){ + iRes = i1; + }else{ + iRes = i2; + } + sqlite3VdbeDeleteUnpackedRecord(r1); + } + + pSorter->aTree[iOut] = iRes; + return SQLITE_OK; +} + +/* +** Initialize the temporary index cursor just opened as a sorter cursor. +*/ +int sqlite3VdbeSorterInit(sqlite3 *db, VdbeCursor *pCsr){ + int rc; /* Return code */ + VdbeSorter *pSorter; /* Allocated sorter object */ + + /* Cursor must be a temp cursor and not open on an intkey table */ + assert( pCsr->pKeyInfo && pCsr->pBt ); + + pSorter = sqlite3DbMallocZero(db, sizeof(VdbeSorter)); + if( !pSorter ) return SQLITE_NOMEM; + pCsr->pSorter = pSorter; + + rc = vdbeSorterAppendRoot(db, pSorter, 2); + if( rc!=SQLITE_OK ){ + sqlite3VdbeSorterClose(db, pCsr); + } + return rc; +} + +/* +** Free any cursor components allocated by sqlite3VdbeSorterXXX routines. +*/ +void sqlite3VdbeSorterClose(sqlite3 *db, VdbeCursor *pCsr){ + VdbeSorter *pSorter = pCsr->pSorter; + if( pSorter ){ + sqlite3DbFree(db, pSorter->aRoot); + if( pSorter->aIter ){ + int i; + for(i=0; inRoot; i++){ + vdbeSorterIterZero(db, &pSorter->aIter[i]); + } + sqlite3DbFree(db, pSorter->aIter); + sqlite3DbFree(db, pSorter->aTree); + } + sqlite3DbFree(db, pSorter); + pCsr->pSorter = 0; + } +} + +/* +** This function is called on a sorter cursor before each row is inserted. +** If the current b-tree being constructed is already considered "full", +** a new tree is started. +*/ +int sqlite3VdbeSorterWrite(sqlite3 *db, VdbeCursor *pCsr){ + int rc = SQLITE_OK; /* Return code */ + VdbeSorter *pSorter = pCsr->pSorter; + if( pSorter ){ + Pager *pPager = sqlite3BtreePager(pCsr->pBt); + int nPage; /* Current size of temporary file in pages */ + + sqlite3PagerPagecount(pPager, &nPage); + + /* If pSorter->nWorking is still zero, but the temporary file has been + ** created in the file-system, then the most recent insert into the + ** current b-tree segment probably caused the cache to overflow (it is + ** also possible that sqlite3_release_memory() was called). So set the + ** size of the working set to a little less than the current size of the + ** file in pages. */ + if( pSorter->nWorking==0 && sqlite3PagerFile(pPager)->pMethods ){ + pSorter->nWorking = nPage-5; + if( pSorter->nWorkingnWorking = SORTER_MIN_SEGMENT_SIZE; + } + } + + /* If the number of pages used by the current b-tree segment is greater + ** than the size of the working set (VdbeSorter.nWorking), start a new + ** segment b-tree. */ + if( pSorter->nWorking && nPage>=(pSorter->nPage + pSorter->nWorking) ){ + BtCursor *p = pCsr->pCursor;/* Cursor structure to close and reopen */ + int iRoot; /* Root page of new tree */ + sqlite3BtreeCloseCursor(p); + rc = sqlite3BtreeCreateTable(pCsr->pBt, &iRoot, BTREE_BLOBKEY); + if( rc==SQLITE_OK ){ + rc = vdbeSorterAppendRoot(db, pSorter, iRoot); + } + if( rc==SQLITE_OK ){ + rc = sqlite3BtreeCursor(pCsr->pBt, iRoot, 1, pCsr->pKeyInfo, p); + } + pSorter->nPage = nPage; + } + } + return rc; +} + +/* +** Extend the pSorter->aIter[] and pSorter->aTree[] arrays using DbRealloc(). +** Return SQLITE_OK if successful, or SQLITE_NOMEM otherwise. +*/ +static int vdbeSorterGrowArrays(sqlite3* db, VdbeSorter *pSorter){ + int *aTree; /* New aTree[] allocation */ + VdbeSorterIter *aIter; /* New aIter[] allocation */ + int nOld = pSorter->nAlloc; /* Current size of arrays */ + int nNew = (nOld?nOld*2:64); /* Size of arrays after reallocation */ + + /* Realloc aTree[]. */ + aTree = sqlite3DbRealloc(db, pSorter->aTree, sizeof(int)*nNew); + if( !aTree ) return SQLITE_NOMEM; + memset(&aTree[nOld], 0, (nNew-nOld) * sizeof(int)); + pSorter->aTree = aTree; + + /* Realloc aIter[]. */ + aIter = sqlite3DbRealloc(db, pSorter->aIter, sizeof(VdbeSorterIter)*nNew); + if( !aIter ) return SQLITE_NOMEM; + memset(&aIter[nOld], 0, (nNew-nOld) * sizeof(VdbeSorterIter)); + pSorter->aIter = aIter; + + /* Set VdbeSorter.nAlloc to the new size of the arrays and return OK. */ + pSorter->nAlloc = nNew; + return SQLITE_OK; +} + +/* +** Helper function for sqlite3VdbeSorterRewind(). +*/ +static int vdbeSorterInitMerge( + sqlite3 *db, + VdbeCursor *pCsr, + int iFirst, + int *piNext +){ + Pager *pPager = sqlite3BtreePager(pCsr->pBt); + VdbeSorter *pSorter = pCsr->pSorter; + int rc = SQLITE_OK; + int i; + int nMaxRef = (pSorter->nWorking * 9/10); + int N = 2; + + /* Initialize as many iterators as possible. */ + for(i=iFirst; rc==SQLITE_OK && inRoot; i++){ + int iIter = i - iFirst; + + assert( iIter<=pSorter->nAlloc ); + if( iIter==pSorter->nAlloc ){ + rc = vdbeSorterGrowArrays(db, pSorter); + } + + if( rc==SQLITE_OK ){ + VdbeSorterIter *pIter = &pSorter->aIter[iIter]; + rc = vdbeSorterIterInit(db, pCsr, pSorter->aRoot[i], pIter); + if( i>iFirst+1 ){ + int nRef = sqlite3PagerRefcount(pPager) + (i+1-iFirst); + if( nRef>=nMaxRef ){ + i++; + break; + } + } + } + } + *piNext = i; + + while( (i-iFirst)>N ) N += N; + pSorter->nTree = N; + + /* Populate the aTree[] array. */ + for(i=N-1; rc==SQLITE_OK && i>0; i--){ + rc = vdbeSorterDoCompare(pCsr, i); + } + + return rc; +} + +/* +** Once the sorter has been populated, this function is called to prepare +** for iterating through its contents in sorted order. +*/ +int sqlite3VdbeSorterRewind(sqlite3 *db, VdbeCursor *pCsr, int *pbEof){ + int rc = SQLITE_OK; /* Return code */ + int N; + int i; + + VdbeSorter *pSorter = pCsr->pSorter; + BtCursor *p = pCsr->pCursor; /* Cursor structure */ + + assert( pSorter ); + sqlite3BtreeCloseCursor(p); + + while( rc==SQLITE_OK ){ + int iNext = 0; /* Index of next segment to open */ + int iRoot = 0; /* aRoot[] slot if merging to a new segment */ + + do { + rc = vdbeSorterInitMerge(db, pCsr, iNext, &iNext); + + if( rc==SQLITE_OK && (iRoot>0 || iNextnRoot) ){ + int pgno; + int bEof = 0; + rc = sqlite3BtreeCreateTable(pCsr->pBt, &pgno, BTREE_BLOBKEY); + if( rc==SQLITE_OK ){ + pSorter->aRoot[iRoot] = pgno; + rc = sqlite3BtreeCursor(pCsr->pBt, pgno, 1, pCsr->pKeyInfo, p); + } + + while( rc==SQLITE_OK && bEof==0 ){ + VdbeSorterIter *pIter = &pSorter->aIter[ pSorter->aTree[1] ]; + rc = sqlite3BtreeInsert(p, pIter->aKey, pIter->nKey, 0, 0, 0, 1, 0); + if( rc==SQLITE_OK ){ + rc = sqlite3VdbeSorterNext(db, pCsr, &bEof); + } + } + sqlite3BtreeCloseCursor(p); + iRoot++; + } + } while( rc==SQLITE_OK && iNextnRoot ); + + if( iRoot==0 ) break; + pSorter->nRoot = iRoot; + } + + *pbEof = (pSorter->aIter[pSorter->aTree[1]].pCsr==0); + return rc; +} + +/* +** Advance to the next element in the sorter. +*/ +int sqlite3VdbeSorterNext(sqlite3 *db, VdbeCursor *pCsr, int *pbEof){ + VdbeSorter *pSorter = pCsr->pSorter; + int iPrev = pSorter->aTree[1]; /* Index of iterator to advance */ + int i; /* Index of aTree[] to recalculate */ + int rc; /* Return code */ + + rc = vdbeSorterIterNext(db, pCsr, &pSorter->aIter[iPrev]); + for(i=(pSorter->nTree+iPrev)/2; rc==SQLITE_OK && i>0; i=i/2){ + rc = vdbeSorterDoCompare(pCsr, i); + } + + *pbEof = (pSorter->aIter[pSorter->aTree[1]].pCsr==0); + return rc; +} + +/* +** Copy the current sorter key into the memory cell pOut. +*/ +int sqlite3VdbeSorterRowkey(sqlite3 *db, VdbeCursor *pCsr, Mem *pOut){ + VdbeSorter *pSorter = pCsr->pSorter; + VdbeSorterIter *pIter; + + pIter = &pSorter->aIter[ pSorter->aTree[1] ]; + if( sqlite3VdbeMemGrow(pOut, pIter->nKey, 0) ){ + return SQLITE_NOMEM; + } + pOut->n = pIter->nKey; + MemSetTypeFlag(pOut, MEM_Blob); + memcpy(pOut->z, pIter->aKey, pIter->nKey); + + return SQLITE_OK; +} + diff --git a/test/index4.test b/test/index4.test new file mode 100644 index 0000000000..9bacf84eb8 --- /dev/null +++ b/test/index4.test @@ -0,0 +1,70 @@ +# 2011 July 9 +# +# The author disclaims copyright to this source code. In place of +# a legal notice, here is a blessing: +# +# May you do good and not evil. +# May you find forgiveness for yourself and forgive others. +# May you share freely, never taking more than you give. +# +#*********************************************************************** +# This file implements regression tests for SQLite library. The +# focus of this file is testing the CREATE INDEX statement. +# + +set testdir [file dirname $argv0] +source $testdir/tester.tcl + +set testprefix index4 + +do_execsql_test 1.1 { + BEGIN; + CREATE TABLE t1(x); + INSERT INTO t1 VALUES(randomblob(102)); + INSERT INTO t1 SELECT randomblob(102) FROM t1; -- 2 + INSERT INTO t1 SELECT randomblob(102) FROM t1; -- 4 + INSERT INTO t1 SELECT randomblob(102) FROM t1; -- 8 + INSERT INTO t1 SELECT randomblob(102) FROM t1; -- 16 + INSERT INTO t1 SELECT randomblob(102) FROM t1; -- 32 + INSERT INTO t1 SELECT randomblob(102) FROM t1; -- 64 + INSERT INTO t1 SELECT randomblob(102) FROM t1; -- 128 + INSERT INTO t1 SELECT randomblob(102) FROM t1; -- 256 + INSERT INTO t1 SELECT randomblob(102) FROM t1; -- 512 + INSERT INTO t1 SELECT randomblob(102) FROM t1; -- 1024 + INSERT INTO t1 SELECT randomblob(102) FROM t1; -- 2048 + INSERT INTO t1 SELECT randomblob(102) FROM t1; -- 4096 + INSERT INTO t1 SELECT randomblob(102) FROM t1; -- 8192 + INSERT INTO t1 SELECT randomblob(102) FROM t1; -- 16384 + INSERT INTO t1 SELECT randomblob(102) FROM t1; -- 32768 + INSERT INTO t1 SELECT randomblob(102) FROM t1; -- 65536 + COMMIT; +} + +do_execsql_test 1.2 { + CREATE INDEX i1 ON t1(x); +} +do_execsql_test 1.3 { + PRAGMA integrity_check +} {ok} + +# The same test again - this time with limited memory. +# +ifcapable memorymanage { + set soft_limit [sqlite3_soft_heap_limit 50000] + + db close + sqlite3 db test.db + + do_execsql_test 1.4 { + PRAGMA cache_size = 10; + CREATE INDEX i2 ON t1(x); + } + do_execsql_test 1.5 { + PRAGMA integrity_check + } {ok} + + sqlite3_soft_heap_limit $soft_limit +} + + +finish_test -- 2.47.2