Index: Makefile.in ================================================================== --- Makefile.in +++ Makefile.in @@ -773,11 +773,11 @@ libsqlite3.la $(LIBTCL) # Rules to build opcodes.c and opcodes.h # opcodes.c: opcodes.h $(TOP)/mkopcodec.awk - sort -n -b -k 3 opcodes.h | $(NAWK) -f $(TOP)/mkopcodec.awk >opcodes.c + $(NAWK) -f $(TOP)/mkopcodec.awk opcodes.h >opcodes.c opcodes.h: parse.h $(TOP)/src/vdbe.c $(TOP)/mkopcodeh.awk cat parse.h $(TOP)/src/vdbe.c | $(NAWK) -f $(TOP)/mkopcodeh.awk >opcodes.h # Rules to build parse.c and parse.h - the outputs of lemon. Index: Makefile.msc ================================================================== --- Makefile.msc +++ Makefile.msc @@ -807,11 +807,11 @@ /link $(LTLINKOPTS) /LIBPATH:$(TCLLIBDIR) libsqlite3.lib $(LIBTCL) # Rules to build opcodes.c and opcodes.h # opcodes.c: opcodes.h $(TOP)\mkopcodec.awk - $(NAWK) "/#define OP_/ { print }" opcodes.h | sort /+45 | $(NAWK) -f $(TOP)\mkopcodec.awk > opcodes.c + $(NAWK) -f $(TOP)\mkopcodec.awk opcodes.h > opcodes.c opcodes.h: parse.h $(TOP)\src\vdbe.c $(TOP)\mkopcodeh.awk type parse.h $(TOP)\src\vdbe.c | $(NAWK) -f $(TOP)\mkopcodeh.awk > opcodes.h # Rules to build parse.c and parse.h - the outputs of lemon. @@ -936,11 +936,11 @@ -DBUILD_sqlite -I$(TCLINCDIR) \ $(TESTFIXTURE_SRC) \ /link $(LTLINKOPTS) /LIBPATH:$(TCLLIBDIR) $(LIBTCL) $(TLIBS) clean: - del /Q *.lo *.lib *.obj sqlite3.exe libsqlite3.lib + del /Q *.lo *.ilk *.lib *.obj *.pdb sqlite3.exe libsqlite3.lib del /Q sqlite3.h opcodes.c opcodes.h del /Q lemon.exe lempar.c parse.* del /Q mkkeywordhash.exe keywordhash.h -rmdir /Q/S tsrc del /Q .target_source Index: Makefile.vxworks ================================================================== --- Makefile.vxworks +++ Makefile.vxworks @@ -515,11 +515,11 @@ # Rules to build opcodes.c and opcodes.h # opcodes.c: opcodes.h $(TOP)/mkopcodec.awk - sort -n -b -k 3 opcodes.h | $(NAWK) -f $(TOP)/mkopcodec.awk >opcodes.c + $(NAWK) -f $(TOP)/mkopcodec.awk opcodes.h >opcodes.c opcodes.h: parse.h $(TOP)/src/vdbe.c $(TOP)/mkopcodeh.awk cat parse.h $(TOP)/src/vdbe.c | \ $(NAWK) -f $(TOP)/mkopcodeh.awk >opcodes.h Index: main.mk ================================================================== --- main.mk +++ main.mk @@ -427,11 +427,11 @@ # Rules to build opcodes.c and opcodes.h # opcodes.c: opcodes.h $(TOP)/mkopcodec.awk - sort -n -b -k 3 opcodes.h | $(NAWK) -f $(TOP)/mkopcodec.awk >opcodes.c + $(NAWK) -f $(TOP)/mkopcodec.awk opcodes.h >opcodes.c opcodes.h: parse.h $(TOP)/src/vdbe.c $(TOP)/mkopcodeh.awk cat parse.h $(TOP)/src/vdbe.c | \ $(NAWK) -f $(TOP)/mkopcodeh.awk >opcodes.h Index: mkopcodec.awk ================================================================== --- mkopcodec.awk +++ mkopcodec.awk @@ -15,17 +15,22 @@ printf " || !defined(NDEBUG)" printf " || defined(VDBE_PROFILE)" print " || defined(SQLITE_DEBUG)" print "const char *sqlite3OpcodeName(int i){" print " static const char *const azName[] = { \"?\"," + mx = 0 } /define OP_/ { sub("OP_","",$2) - i++ - printf " /* %3d */ \"%s\",\n", $3, $2 + i = $3+0 + label[i] = $2 + if( mxpKeyInfo, (int)nKey, pKey, - aSpace, sizeof(aSpace)); + pIdxKey = sqlite3VdbeAllocUnpackedRecord( + pCur->pKeyInfo, aSpace, sizeof(aSpace), &pFree + ); if( pIdxKey==0 ) return SQLITE_NOMEM; + sqlite3VdbeRecordUnpack(pCur->pKeyInfo, nKey, pKey, pIdxKey); }else{ pIdxKey = 0; } rc = sqlite3BtreeMovetoUnpacked(pCur, pIdxKey, nKey, bias, pRes); - if( pKey ){ - sqlite3VdbeDeleteUnpackedRecord(pIdxKey); + if( pFree ){ + sqlite3DbFree(pCur->pKeyInfo->db, pFree); } return rc; } /* @@ -1732,26 +1735,15 @@ assert( (flags & BTREE_UNORDERED)==0 || (flags & BTREE_SINGLE)!=0 ); /* A BTREE_SINGLE database is always a temporary and/or ephemeral */ assert( (flags & BTREE_SINGLE)==0 || isTempDb ); - /* The BTREE_SORTER flag is only used if SQLITE_OMIT_MERGE_SORT is undef */ -#ifdef SQLITE_OMIT_MERGE_SORT - assert( (flags & BTREE_SORTER)==0 ); -#endif - - /* BTREE_SORTER is always on a BTREE_SINGLE, BTREE_OMIT_JOURNAL */ - assert( (flags & BTREE_SORTER)==0 || - (flags & (BTREE_SINGLE|BTREE_OMIT_JOURNAL)) - ==(BTREE_SINGLE|BTREE_OMIT_JOURNAL) ); - if( db->flags & SQLITE_NoReadlock ){ flags |= BTREE_NO_READLOCK; } if( isMemdb ){ flags |= BTREE_MEMORY; - flags &= ~BTREE_SORTER; } if( (vfsFlags & SQLITE_OPEN_MAIN_DB)!=0 && (isMemdb || isTempDb) ){ vfsFlags = (vfsFlags & ~SQLITE_OPEN_MAIN_DB) | SQLITE_OPEN_TEMP_DB; } p = sqlite3MallocZero(sizeof(Btree)); @@ -2752,15 +2744,16 @@ for(i=0; iaData+pPage->maskPage + && iFrom==get4byte(&pCell[info.iOverflow]) + ){ + put4byte(&pCell[info.iOverflow], iTo); + break; } }else{ if( get4byte(pCell)==iFrom ){ put4byte(pCell, iTo); break; @@ -3477,11 +3470,12 @@ if( NEVER(wrFlag && pBt->readOnly) ){ return SQLITE_READONLY; } if( iTable==1 && btreePagecount(pBt)==0 ){ - return SQLITE_EMPTY; + assert( wrFlag==0 ); + iTable = 0; } /* Now that no other errors can occur, finish filling in the BtCursor ** variables and link the cursor into the BtShared list. */ pCur->pgnoRoot = (Pgno)iTable; @@ -4231,10 +4225,13 @@ int i; for(i=1; i<=pCur->iPage; i++){ releasePage(pCur->apPage[i]); } pCur->iPage = 0; + }else if( pCur->pgnoRoot==0 ){ + pCur->eState = CURSOR_INVALID; + return SQLITE_OK; }else{ rc = getAndInitPage(pBt, pCur->pgnoRoot, &pCur->apPage[0]); if( rc!=SQLITE_OK ){ pCur->eState = CURSOR_INVALID; return rc; @@ -4340,11 +4337,11 @@ assert( cursorHoldsMutex(pCur) ); assert( sqlite3_mutex_held(pCur->pBtree->db->mutex) ); rc = moveToRoot(pCur); if( rc==SQLITE_OK ){ if( pCur->eState==CURSOR_INVALID ){ - assert( pCur->apPage[pCur->iPage]->nCell==0 ); + assert( pCur->pgnoRoot==0 || pCur->apPage[pCur->iPage]->nCell==0 ); *pRes = 1; }else{ assert( pCur->apPage[pCur->iPage]->nCell>0 ); *pRes = 0; rc = moveToLeftmost(pCur); @@ -4379,11 +4376,11 @@ } rc = moveToRoot(pCur); if( rc==SQLITE_OK ){ if( CURSOR_INVALID==pCur->eState ){ - assert( pCur->apPage[pCur->iPage]->nCell==0 ); + assert( pCur->pgnoRoot==0 || pCur->apPage[pCur->iPage]->nCell==0 ); *pRes = 1; }else{ assert( pCur->eState==CURSOR_VALID ); *pRes = 0; rc = moveToRightmost(pCur); @@ -4452,16 +4449,16 @@ rc = moveToRoot(pCur); if( rc ){ return rc; } - assert( pCur->apPage[pCur->iPage] ); - assert( pCur->apPage[pCur->iPage]->isInit ); - assert( pCur->apPage[pCur->iPage]->nCell>0 || pCur->eState==CURSOR_INVALID ); + assert( pCur->pgnoRoot==0 || pCur->apPage[pCur->iPage] ); + assert( pCur->pgnoRoot==0 || pCur->apPage[pCur->iPage]->isInit ); + assert( pCur->eState==CURSOR_INVALID || pCur->apPage[pCur->iPage]->nCell>0 ); if( pCur->eState==CURSOR_INVALID ){ *pRes = -1; - assert( pCur->apPage[pCur->iPage]->nCell==0 ); + assert( pCur->pgnoRoot==0 || pCur->apPage[pCur->iPage]->nCell==0 ); return SQLITE_OK; } assert( pCur->apPage[0]->intKey || pIdxKey ); for(;;){ int lwr, upr, idx; @@ -5184,10 +5181,13 @@ assert( sqlite3_mutex_held(pPage->pBt->mutex) ); btreeParseCellPtr(pPage, pCell, &info); if( info.iOverflow==0 ){ return SQLITE_OK; /* No overflow pages. Return without doing anything */ } + if( pCell+info.iOverflow+3 > pPage->aData+pPage->maskPage ){ + return SQLITE_CORRUPT; /* Cell extends past end of page */ + } ovflPgno = get4byte(&pCell[info.iOverflow]); assert( pBt->usableSize > 4 ); ovflPageSize = pBt->usableSize - 4; nOvfl = (info.nPayload - info.nLocal + ovflPageSize - 1)/ovflPageSize; assert( ovflPgno==0 || nOvfl>0 ); @@ -7286,20 +7286,13 @@ releasePage(pPage); } return rc; } int sqlite3BtreeDropTable(Btree *p, int iTable, int *piMoved){ - BtShared *pBt = p->pBt; int rc; sqlite3BtreeEnter(p); - if( (pBt->openFlags&BTREE_SINGLE) ){ - pBt->nPage = 0; - sqlite3PagerTruncateImage(pBt->pPager, 1); - rc = newDatabase(pBt); - }else{ - rc = btreeDropTable(p, iTable, piMoved); - } + rc = btreeDropTable(p, iTable, piMoved); sqlite3BtreeLeave(p); return rc; } @@ -7374,10 +7367,15 @@ ** corruption) an SQLite error code is returned. */ int sqlite3BtreeCount(BtCursor *pCur, i64 *pnEntry){ i64 nEntry = 0; /* Value to return in *pnEntry */ int rc; /* Return code */ + + if( pCur->pgnoRoot==0 ){ + *pnEntry = 0; + return SQLITE_OK; + } rc = moveToRoot(pCur); /* Unless an error occurs, the following loop runs one iteration for each ** page in the B-Tree structure (not including overflow pages). */ Index: src/btree.h ================================================================== --- src/btree.h +++ src/btree.h @@ -59,11 +59,10 @@ #define BTREE_OMIT_JOURNAL 1 /* Do not create or use a rollback journal */ #define BTREE_NO_READLOCK 2 /* Omit readlocks on readonly files */ #define BTREE_MEMORY 4 /* This is an in-memory DB */ #define BTREE_SINGLE 8 /* The file contains at most 1 b-tree */ #define BTREE_UNORDERED 16 /* Use of a hash implementation is OK */ -#define BTREE_SORTER 32 /* Used as accumulator in external merge sort */ int sqlite3BtreeClose(Btree*); int sqlite3BtreeSetCacheSize(Btree*,int); int sqlite3BtreeSetSafetyLevel(Btree*,int,int,int); int sqlite3BtreeSyncDisabled(Btree*); Index: src/build.c ================================================================== --- src/build.c +++ src/build.c @@ -2341,27 +2341,19 @@ 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 = iTab; /* Cursor opened by OpenSorter (if in use) */ int addr1; /* Address of top of loop */ + int addr2; /* Address to jump to for next iteration */ int tnum; /* Root page of index */ Vdbe *v; /* Generate code into this virtual machine */ KeyInfo *pKey; /* KeyInfo for index */ int regIdxKey; /* Registers containing the index key */ int regRecord; /* Register holding assemblied index record */ sqlite3 *db = pParse->db; /* The database connection */ int iDb = sqlite3SchemaToIndex(db, pIndex->pSchema); - /* Set bUseSorter to use OP_OpenSorter, or clear it to insert directly - ** into the index. The sorter is used unless either OMIT_MERGE_SORT is - ** defined or the system is configured to store temp files in-memory. */ -#ifdef SQLITE_OMIT_MERGE_SORT - static const int bUseSorter = 0; -#else - const int bUseSorter = !sqlite3TempInMemory(pParse->db); -#endif - #ifndef SQLITE_OMIT_AUTHORIZATION if( sqlite3AuthCheck(pParse, SQLITE_REINDEX, pIndex->zName, 0, db->aDb[iDb].zName ) ){ return; } @@ -2383,32 +2375,44 @@ (char *)pKey, P4_KEYINFO_HANDOFF); if( memRootPage>=0 ){ sqlite3VdbeChangeP5(v, 1); } +#ifndef SQLITE_OMIT_MERGE_SORT /* Open the sorter cursor if we are to use one. */ - if( bUseSorter ){ - iSorter = pParse->nTab++; - sqlite3VdbeAddOp4(v, OP_OpenSorter, iSorter, 0, 0, (char*)pKey, P4_KEYINFO); - sqlite3VdbeChangeP5(v, BTREE_SORTER); - } + iSorter = pParse->nTab++; + sqlite3VdbeAddOp4(v, OP_SorterOpen, iSorter, 0, 0, (char*)pKey, P4_KEYINFO); +#endif /* 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); + addr2 = addr1 + 1; regRecord = sqlite3GetTempReg(pParse); regIdxKey = sqlite3GenerateIndexKey(pParse, pIndex, iTab, regRecord, 1); - if( bUseSorter ){ - sqlite3VdbeAddOp2(v, OP_IdxInsert, iSorter, regRecord); - sqlite3VdbeAddOp2(v, OP_Next, iTab, addr1+1); - sqlite3VdbeJumpHere(v, addr1); - addr1 = sqlite3VdbeAddOp2(v, OP_Sort, iSorter, 0); - sqlite3VdbeAddOp2(v, OP_RowKey, iSorter, regRecord); - } - +#ifndef SQLITE_OMIT_MERGE_SORT + sqlite3VdbeAddOp2(v, OP_SorterInsert, iSorter, regRecord); + sqlite3VdbeAddOp2(v, OP_Next, iTab, addr1+1); + sqlite3VdbeJumpHere(v, addr1); + addr1 = sqlite3VdbeAddOp2(v, OP_SorterSort, iSorter, 0); + if( pIndex->onError!=OE_None ){ + int j2 = sqlite3VdbeCurrentAddr(v) + 3; + sqlite3VdbeAddOp2(v, OP_Goto, 0, j2); + addr2 = sqlite3VdbeCurrentAddr(v); + sqlite3VdbeAddOp3(v, OP_SorterCompare, iSorter, j2, regRecord); + sqlite3HaltConstraint( + pParse, OE_Abort, "indexed columns are not unique", P4_STATIC + ); + }else{ + addr2 = sqlite3VdbeCurrentAddr(v); + } + sqlite3VdbeAddOp2(v, OP_SorterData, iSorter, regRecord); + sqlite3VdbeAddOp3(v, OP_IdxInsert, iIdx, regRecord, 1); + sqlite3VdbeChangeP5(v, OPFLAG_USESEEKRESULT); +#else if( pIndex->onError!=OE_None ){ const int regRowid = regIdxKey + pIndex->nColumn; const int j2 = sqlite3VdbeCurrentAddr(v) + 2; void * const pRegKey = SQLITE_INT_TO_PTR(regIdxKey); @@ -2423,14 +2427,15 @@ */ sqlite3VdbeAddOp4(v, OP_IsUnique, iIdx, j2, regRowid, pRegKey, P4_INT32); sqlite3HaltConstraint( pParse, OE_Abort, "indexed columns are not unique", P4_STATIC); } - sqlite3VdbeAddOp3(v, OP_IdxInsert, iIdx, regRecord, bUseSorter); + sqlite3VdbeAddOp3(v, OP_IdxInsert, iIdx, regRecord, 0); sqlite3VdbeChangeP5(v, OPFLAG_USESEEKRESULT); +#endif sqlite3ReleaseTempReg(pParse, regRecord); - sqlite3VdbeAddOp2(v, OP_Next, iSorter, addr1+1); + sqlite3VdbeAddOp2(v, OP_SorterNext, iSorter, addr2); sqlite3VdbeJumpHere(v, addr1); sqlite3VdbeAddOp1(v, OP_Close, iTab); sqlite3VdbeAddOp1(v, OP_Close, iIdx); sqlite3VdbeAddOp1(v, OP_Close, iSorter); Index: src/ctime.c ================================================================== --- src/ctime.c +++ src/ctime.c @@ -145,10 +145,13 @@ "INT64_TYPE", #endif #ifdef SQLITE_LOCK_TRACE "LOCK_TRACE", #endif +#ifdef SQLITE_MAX_SCHEMA_RETRY + "MAX_SCHEMA_RETRY=" CTIMEOPT_VAL(SQLITE_MAX_SCHEMA_RETRY), +#endif #ifdef SQLITE_MEMDEBUG "MEMDEBUG", #endif #ifdef SQLITE_MIXED_ENDIAN_64BIT_FLOAT "MIXED_ENDIAN_64BIT_FLOAT", Index: src/expr.c ================================================================== --- src/expr.c +++ src/expr.c @@ -2285,11 +2285,11 @@ if( !pAggInfo->directMode ){ assert( pCol->iMem>0 ); inReg = pCol->iMem; break; }else if( pAggInfo->useSortingIdx ){ - sqlite3VdbeAddOp3(v, OP_Column, pAggInfo->sortingIdx, + sqlite3VdbeAddOp3(v, OP_Column, pAggInfo->sortingIdxPTab, pCol->iSorterColumn, target); break; } /* Otherwise, fall thru into the TK_COLUMN case */ } Index: src/os_common.h ================================================================== --- src/os_common.h +++ src/os_common.h @@ -27,11 +27,11 @@ */ #ifdef MEMORY_DEBUG # error "The MEMORY_DEBUG macro is obsolete. Use SQLITE_DEBUG instead." #endif -#ifdef SQLITE_DEBUG +#if defined(SQLITE_TEST) && defined(SQLITE_DEBUG) # ifndef SQLITE_DEBUG_OS_TRACE # define SQLITE_DEBUG_OS_TRACE 0 # endif int sqlite3OSTrace = SQLITE_DEBUG_OS_TRACE; # define OSTRACE(X) if( sqlite3OSTrace ) sqlite3DebugPrintf X Index: src/os_unix.c ================================================================== --- src/os_unix.c +++ src/os_unix.c @@ -2523,15 +2523,16 @@ */ static int afpCheckReservedLock(sqlite3_file *id, int *pResOut){ int rc = SQLITE_OK; int reserved = 0; unixFile *pFile = (unixFile*)id; + afpLockingContext *context; SimulateIOError( return SQLITE_IOERR_CHECKRESERVEDLOCK; ); assert( pFile ); - afpLockingContext *context = (afpLockingContext *) pFile->lockingContext; + context = (afpLockingContext *) pFile->lockingContext; if( context->reserved ){ *pResOut = 1; return SQLITE_OK; } unixEnterMutex(); /* Because pFile->pInode is shared across threads */ @@ -2667,11 +2668,11 @@ /* If control gets to this point, then actually go ahead and make ** operating system calls for the specified lock. */ if( eFileLock==SHARED_LOCK ){ - int lrc1, lrc2, lrc1Errno; + int lrc1, lrc2, lrc1Errno = 0; long lk, mask; assert( pInode->nShared==0 ); assert( pInode->eFileLock==0 ); @@ -3143,15 +3144,15 @@ int sqlite3_fullsync_count = 0; #endif /* ** We do not trust systems to provide a working fdatasync(). Some do. -** Others do no. To be safe, we will stick with the (slower) fsync(). -** If you know that your system does support fdatasync() correctly, +** Others do no. To be safe, we will stick with the (slightly slower) +** fsync(). If you know that your system does support fdatasync() correctly, ** then simply compile with -Dfdatasync=fdatasync */ -#if !defined(fdatasync) && !defined(__linux__) +#if !defined(fdatasync) # define fdatasync fsync #endif /* ** Define HAVE_FULLFSYNC to 0 or 1 depending on whether or not @@ -3437,30 +3438,22 @@ static int proxyFileControl(sqlite3_file*,int,void*); #endif /* ** This function is called to handle the SQLITE_FCNTL_SIZE_HINT -** file-control operation. -** -** If the user has configured a chunk-size for this file, it could be -** that the file needs to be extended at this point. Otherwise, the -** SQLITE_FCNTL_SIZE_HINT operation is a no-op for Unix. +** file-control operation. Enlarge the database to nBytes in size +** (rounded up to the next chunk-size). If the database is already +** nBytes or larger, this routine is a no-op. */ static int fcntlSizeHint(unixFile *pFile, i64 nByte){ - { /* preserve indentation of removed "if" */ + if( pFile->szChunk>0 ){ i64 nSize; /* Required file size */ - i64 szChunk; /* Chunk size */ struct stat buf; /* Used to hold return values of fstat() */ if( osFstat(pFile->h, &buf) ) return SQLITE_IOERR_FSTAT; - szChunk = pFile->szChunk; - if( szChunk==0 ){ - nSize = nByte; - }else{ - nSize = ((nByte+szChunk-1) / szChunk) * szChunk; - } + nSize = ((nByte+pFile->szChunk-1) / pFile->szChunk) * pFile->szChunk; if( nSize>(i64)buf.st_size ){ #if defined(HAVE_POSIX_FALLOCATE) && HAVE_POSIX_FALLOCATE /* The code below is handling the return value of osFallocate() ** correctly. posix_fallocate() is defined to "returns zero on success, @@ -3645,15 +3638,13 @@ */ struct unixShm { unixShmNode *pShmNode; /* The underlying unixShmNode object */ unixShm *pNext; /* Next unixShm with the same unixShmNode */ u8 hasMutex; /* True if holding the unixShmNode mutex */ + u8 id; /* Id of this connection within its unixShmNode */ u16 sharedMask; /* Mask of shared locks held */ u16 exclMask; /* Mask of exclusive locks held */ -#ifdef SQLITE_DEBUG - u8 id; /* Id of this connection within its unixShmNode */ -#endif }; /* ** Constants used for locking */ @@ -4955,10 +4946,13 @@ int isReadonly = (flags & SQLITE_OPEN_READONLY); int isReadWrite = (flags & SQLITE_OPEN_READWRITE); #if SQLITE_ENABLE_LOCKING_STYLE int isAutoProxy = (flags & SQLITE_OPEN_AUTOPROXY); #endif +#if defined(__APPLE__) || SQLITE_ENABLE_LOCKING_STYLE + struct statfs fsInfo; +#endif /* If creating a master or main-file journal, this function will open ** a file-descriptor on the directory too. The first time unixSync() ** is called the directory file descriptor will be fsync()ed and close()d. */ @@ -5087,11 +5081,10 @@ noLock = eType!=SQLITE_OPEN_MAIN_DB; #if defined(__APPLE__) || SQLITE_ENABLE_LOCKING_STYLE - struct statfs fsInfo; if( fstatfs(fd, &fsInfo) == -1 ){ ((unixFile*)pFile)->lastErrno = errno; robust_close(p, fd, __LINE__); return SQLITE_IOERR_ACCESS; } @@ -5111,11 +5104,10 @@ /* SQLITE_FORCE_PROXY_LOCKING==1 means force always use proxy, 0 means ** never use proxy, NULL means use proxy for non-local files only. */ if( envforce!=NULL ){ useProxy = atoi(envforce)>0; }else{ - struct statfs fsInfo; if( statfs(zPath, &fsInfo) == -1 ){ /* In theory, the close(fd) call is sub-optimal. If the file opened ** with fd is a database file, and there are other connections open ** on that file that are currently holding advisory locks on it, ** then the call to close() will cancel those locks. In practice, @@ -5852,10 +5844,12 @@ *pError = err; } return SQLITE_IOERR; } } +#else + UNUSED_PARAMETER(pError); #endif #ifdef SQLITE_TEST /* simulate multiple hosts by creating unique hostid file paths */ if( sqlite3_hostid_num != 0){ pHostID[0] = (char)(pHostID[0] + (char)(sqlite3_hostid_num & 0xFF)); @@ -5944,10 +5938,11 @@ unixFile *conchFile = pCtx->conchFile; int rc = SQLITE_OK; int nTries = 0; struct timespec conchModTime; + memset(&conchModTime, 0, sizeof(conchModTime)); do { rc = conchFile->pMethod->xLock((sqlite3_file*)conchFile, lockType); nTries ++; if( rc==SQLITE_BUSY ){ /* If the lock failed (busy): @@ -6175,15 +6170,16 @@ conchFile->pMethod->xUnlock((sqlite3_file*)conchFile, SHARED_LOCK); end_takeconch: OSTRACE(("TRANSPROXY: CLOSE %d\n", pFile->h)); if( rc==SQLITE_OK && pFile->openFlags ){ + int fd; if( pFile->h>=0 ){ robust_close(pFile, pFile->h, __LINE__); } pFile->h = -1; - int fd = robust_open(pCtx->dbPath, pFile->openFlags, + fd = robust_open(pCtx->dbPath, pFile->openFlags, SQLITE_DEFAULT_FILE_PERMISSIONS); OSTRACE(("TRANSPROXY: OPEN %d\n", fd)); if( fd>=0 ){ pFile->h = fd; }else{ Index: src/os_win.c ================================================================== --- src/os_win.c +++ src/os_win.c @@ -1214,11 +1214,11 @@ /* If the user has configured a chunk-size for this file, truncate the ** file so that it consists of an integer number of chunks (i.e. the ** actual file size after the operation may be larger than the requested ** size). */ - if( pFile->szChunk ){ + if( pFile->szChunk>0 ){ nByte = ((nByte + pFile->szChunk - 1)/pFile->szChunk) * pFile->szChunk; } /* SetEndOfFile() returns non-zero when successful, or zero when it fails. */ if( seekWinFile(pFile, nByte) ){ @@ -1601,22 +1601,24 @@ case SQLITE_FCNTL_CHUNK_SIZE: { pFile->szChunk = *(int *)pArg; return SQLITE_OK; } case SQLITE_FCNTL_SIZE_HINT: { - winFile *pFile = (winFile*)id; - sqlite3_int64 oldSz; - int rc = winFileSize(id, &oldSz); - if( rc==SQLITE_OK ){ - sqlite3_int64 newSz = *(sqlite3_int64*)pArg; - if( newSz>oldSz ){ - SimulateIOErrorBenign(1); - rc = winTruncate(id, newSz); - SimulateIOErrorBenign(0); - } - } - return rc; + if( pFile->szChunk>0 ){ + sqlite3_int64 oldSz; + int rc = winFileSize(id, &oldSz); + if( rc==SQLITE_OK ){ + sqlite3_int64 newSz = *(sqlite3_int64*)pArg; + if( newSz>oldSz ){ + SimulateIOErrorBenign(1); + rc = winTruncate(id, newSz); + SimulateIOErrorBenign(0); + } + } + return rc; + } + return SQLITE_OK; } case SQLITE_FCNTL_PERSIST_WAL: { int bPersist = *(int*)pArg; if( bPersist<0 ){ *(int*)pArg = pFile->bPersistWal; Index: src/pager.c ================================================================== --- src/pager.c +++ src/pager.c @@ -619,11 +619,10 @@ u8 syncFlags; /* SYNC_NORMAL or SYNC_FULL otherwise */ u8 tempFile; /* zFilename is a temporary file */ u8 readOnly; /* True for a read-only database */ u8 memDb; /* True to inhibit all file I/O */ u8 hasSeenStress; /* pagerStress() called one or more times */ - u8 isSorter; /* True for a PAGER_SORTER */ /************************************************************************** ** The following block contains those class members that change during ** routine opertion. Class members not in this block are either fixed ** when the pager is first created or else only change when there is a @@ -843,19 +842,10 @@ ); assert( p->eState!=PAGER_ERROR && p->eState!=PAGER_OPEN ); assert( pagerUseWal(p)==0 ); } - /* A sorter is a temp file that never spills to disk and always has - ** the doNotSpill flag set - */ - if( p->isSorter ){ - assert( p->tempFile ); - assert( p->doNotSpill ); - assert( p->fd->pMethods==0 ); - } - /* If changeCountDone is set, a RESERVED lock or greater must be held ** on the file. */ assert( pPager->changeCountDone==0 || pPager->eLock>=RESERVED_LOCK ); assert( p->eLock!=PENDING_LOCK ); @@ -4555,16 +4545,10 @@ } /* pPager->xBusyHandler = 0; */ /* pPager->pBusyHandlerArg = 0; */ pPager->xReiniter = xReinit; /* memset(pPager->aHash, 0, sizeof(pPager->aHash)); */ -#ifndef SQLITE_OMIT_MERGE_SORT - if( flags & PAGER_SORTER ){ - pPager->doNotSpill = 1; - pPager->isSorter = 1; - } -#endif *ppPager = pPager; return SQLITE_OK; } @@ -6105,21 +6089,10 @@ */ int sqlite3PagerIsMemdb(Pager *pPager){ return MEMDB; } -#ifndef SQLITE_OMIT_MERGE_SORT -/* -** Return true if the pager has seen a pagerStress callback. -*/ -int sqlite3PagerUnderStress(Pager *pPager){ - assert( pPager->isSorter ); - assert( pPager->doNotSpill ); - return pPager->hasSeenStress; -} -#endif - /* ** Check that there are at least nSavepoint savepoints open. If there are ** currently less than nSavepoints open, then open one or more savepoints ** to make up the difference. If the number of savepoints is already ** equal to nSavepoint, then this function is a no-op. Index: src/pager.h ================================================================== --- src/pager.h +++ src/pager.h @@ -154,13 +154,10 @@ sqlite3_file *sqlite3PagerFile(Pager*); const char *sqlite3PagerJournalname(Pager*); int sqlite3PagerNosync(Pager*); void *sqlite3PagerTempSpace(Pager*); int sqlite3PagerIsMemdb(Pager*); -#ifndef SQLITE_OMIT_MERGE_SORT -int sqlite3PagerUnderStress(Pager*); -#endif /* Functions used to truncate the database file. */ void sqlite3PagerTruncateImage(Pager*,Pgno); #if defined(SQLITE_HAS_CODEC) && !defined(SQLITE_OMIT_WAL) Index: src/select.c ================================================================== --- src/select.c +++ src/select.c @@ -417,16 +417,22 @@ ){ Vdbe *v = pParse->pVdbe; int nExpr = pOrderBy->nExpr; int regBase = sqlite3GetTempRange(pParse, nExpr+2); int regRecord = sqlite3GetTempReg(pParse); + int op; sqlite3ExprCacheClear(pParse); sqlite3ExprCodeExprList(pParse, pOrderBy, regBase, 0); sqlite3VdbeAddOp2(v, OP_Sequence, pOrderBy->iECursor, regBase+nExpr); sqlite3ExprCodeMove(pParse, regData, regBase+nExpr+1, 1); sqlite3VdbeAddOp3(v, OP_MakeRecord, regBase, nExpr + 2, regRecord); - sqlite3VdbeAddOp2(v, OP_IdxInsert, pOrderBy->iECursor, regRecord); + if( pSelect->selFlags & SF_UseSorter ){ + op = OP_SorterInsert; + }else{ + op = OP_IdxInsert; + } + sqlite3VdbeAddOp2(v, op, pOrderBy->iECursor, regRecord); sqlite3ReleaseTempReg(pParse, regRecord); sqlite3ReleaseTempRange(pParse, regBase, nExpr+2); if( pSelect->iLimit ){ int addr1, addr2; int iLimit; @@ -891,13 +897,24 @@ sqlite3VdbeAddOp3(v, OP_OpenPseudo, pseudoTab, regRow, nColumn); regRowid = 0; }else{ regRowid = sqlite3GetTempReg(pParse); } - addr = 1 + sqlite3VdbeAddOp2(v, OP_Sort, iTab, addrBreak); - codeOffset(v, p, addrContinue); - sqlite3VdbeAddOp3(v, OP_Column, iTab, pOrderBy->nExpr + 1, regRow); + if( p->selFlags & SF_UseSorter ){ + int regSortOut = ++pParse->nMem; + int ptab2 = pParse->nTab++; + sqlite3VdbeAddOp3(v, OP_OpenPseudo, ptab2, regSortOut, pOrderBy->nExpr+2); + addr = 1 + sqlite3VdbeAddOp2(v, OP_SorterSort, iTab, addrBreak); + codeOffset(v, p, addrContinue); + sqlite3VdbeAddOp2(v, OP_SorterData, iTab, regSortOut); + sqlite3VdbeAddOp3(v, OP_Column, ptab2, pOrderBy->nExpr+1, regRow); + sqlite3VdbeChangeP5(v, OPFLAG_CLEARCACHE); + }else{ + addr = 1 + sqlite3VdbeAddOp2(v, OP_Sort, iTab, addrBreak); + codeOffset(v, p, addrContinue); + sqlite3VdbeAddOp3(v, OP_Column, iTab, pOrderBy->nExpr+1, regRow); + } switch( eDest ){ case SRT_Table: case SRT_EphemTab: { testcase( eDest==SRT_Table ); testcase( eDest==SRT_EphemTab ); @@ -946,11 +963,15 @@ sqlite3ReleaseTempReg(pParse, regRowid); /* The bottom of the loop */ sqlite3VdbeResolveLabel(v, addrContinue); - sqlite3VdbeAddOp2(v, OP_Next, iTab, addr); + if( p->selFlags & SF_UseSorter ){ + sqlite3VdbeAddOp2(v, OP_SorterNext, iTab, addr); + }else{ + sqlite3VdbeAddOp2(v, OP_Next, iTab, addr); + } sqlite3VdbeResolveLabel(v, addrBreak); if( eDest==SRT_Output || eDest==SRT_Coroutine ){ sqlite3VdbeAddOp2(v, OP_Close, pseudoTab, 0); } } @@ -3912,10 +3933,14 @@ /* Set the limiter. */ iEnd = sqlite3VdbeMakeLabel(v); p->nSelectRow = (double)LARGEST_INT64; computeLimitRegisters(pParse, p, iEnd); + if( p->iLimit==0 && addrSortIndex>=0 ){ + sqlite3VdbeGetOp(v, addrSortIndex)->opcode = OP_SorterOpen; + p->selFlags |= SF_UseSorter; + } /* Open a virtual index to use for the distinct set. */ if( p->selFlags & SF_Distinct ){ KeyInfo *pKeyInfo; @@ -3947,11 +3972,11 @@ } if( pWInfo->eDistinct ){ VdbeOp *pOp; /* No longer required OpenEphemeral instr. */ - assert( addrDistinctIndex>0 ); + assert( addrDistinctIndex>=0 ); pOp = sqlite3VdbeGetOp(v, addrDistinctIndex); assert( isDistinct ); assert( pWInfo->eDistinct==WHERE_DISTINCT_ORDERED || pWInfo->eDistinct==WHERE_DISTINCT_UNIQUE @@ -4006,10 +4031,12 @@ ** one row of the input to the aggregator has been ** processed */ int iAbortFlag; /* Mem address which causes query abort if positive */ int groupBySort; /* Rows come from source in GROUP BY order */ int addrEnd; /* End of processing for this SELECT */ + int sortPTab = 0; /* Pseudotable used to decode sorting results */ + int sortOut = 0; /* Output register from the sorter */ /* Remove any and all aliases between the result set and the ** GROUP BY clause. */ if( pGroupBy ){ @@ -4067,16 +4094,16 @@ int addrReset; /* Subroutine for resetting the accumulator */ int regReset; /* Return address register for reset subroutine */ /* If there is a GROUP BY clause we might need a sorting index to ** implement it. Allocate that sorting index now. If it turns out - ** that we do not need it after all, the OpenEphemeral instruction + ** that we do not need it after all, the OP_SorterOpen instruction ** will be converted into a Noop. */ sAggInfo.sortingIdx = pParse->nTab++; pKeyInfo = keyInfoFromExprList(pParse, pGroupBy); - addrSortingIdx = sqlite3VdbeAddOp4(v, OP_OpenEphemeral, + addrSortingIdx = sqlite3VdbeAddOp4(v, OP_SorterOpen, sAggInfo.sortingIdx, sAggInfo.nSortingColumn, 0, (char*)pKeyInfo, P4_KEYINFO_HANDOFF); /* Initialize memory locations used by GROUP BY aggregate processing */ @@ -4153,15 +4180,18 @@ j++; } } regRecord = sqlite3GetTempReg(pParse); sqlite3VdbeAddOp3(v, OP_MakeRecord, regBase, nCol, regRecord); - sqlite3VdbeAddOp2(v, OP_IdxInsert, sAggInfo.sortingIdx, regRecord); + sqlite3VdbeAddOp2(v, OP_SorterInsert, sAggInfo.sortingIdx, regRecord); sqlite3ReleaseTempReg(pParse, regRecord); sqlite3ReleaseTempRange(pParse, regBase, nCol); sqlite3WhereEnd(pWInfo); - sqlite3VdbeAddOp2(v, OP_Sort, sAggInfo.sortingIdx, addrEnd); + sAggInfo.sortingIdxPTab = sortPTab = pParse->nTab++; + sortOut = sqlite3GetTempReg(pParse); + sqlite3VdbeAddOp3(v, OP_OpenPseudo, sortPTab, sortOut, nCol); + sqlite3VdbeAddOp2(v, OP_SorterSort, sAggInfo.sortingIdx, addrEnd); VdbeComment((v, "GROUP BY sort")); sAggInfo.useSortingIdx = 1; sqlite3ExprCacheClear(pParse); } @@ -4170,13 +4200,17 @@ ** Then compare the current GROUP BY terms against the GROUP BY terms ** from the previous row currently stored in a0, a1, a2... */ addrTopOfLoop = sqlite3VdbeCurrentAddr(v); sqlite3ExprCacheClear(pParse); + if( groupBySort ){ + sqlite3VdbeAddOp2(v, OP_SorterData, sAggInfo.sortingIdx, sortOut); + } for(j=0; jnExpr; j++){ if( groupBySort ){ - sqlite3VdbeAddOp3(v, OP_Column, sAggInfo.sortingIdx, j, iBMem+j); + sqlite3VdbeAddOp3(v, OP_Column, sortPTab, j, iBMem+j); + if( j==0 ) sqlite3VdbeChangeP5(v, OPFLAG_CLEARCACHE); }else{ sAggInfo.directMode = 1; sqlite3ExprCode(pParse, pGroupBy->a[j].pExpr, iBMem+j); } } @@ -4211,11 +4245,11 @@ VdbeComment((v, "indicate data in accumulator")); /* End of the loop */ if( groupBySort ){ - sqlite3VdbeAddOp2(v, OP_Next, sAggInfo.sortingIdx, addrTopOfLoop); + sqlite3VdbeAddOp2(v, OP_SorterNext, sAggInfo.sortingIdx, addrTopOfLoop); }else{ sqlite3WhereEnd(pWInfo); sqlite3VdbeChangeToNoop(v, addrSortingIdx, 1); } Index: src/sqliteInt.h ================================================================== --- src/sqliteInt.h +++ src/sqliteInt.h @@ -370,18 +370,10 @@ */ #ifndef SQLITE_TEMP_STORE # define SQLITE_TEMP_STORE 1 #endif -/* -** If all temporary storage is in-memory, then omit the external merge-sort -** logic since it is superfluous. -*/ -#if SQLITE_TEMP_STORE==3 && !defined(SQLITE_OMIT_MERGE_SORT) -# define SQLITE_OMIT_MERGE_SORT -#endif - /* ** GCC does not define the offsetof() macro so we'll have to do it ** ourselves. */ #ifndef offsetof @@ -1568,10 +1560,11 @@ u8 directMode; /* Direct rendering mode means take data directly ** from source tables rather than from accumulators */ u8 useSortingIdx; /* In direct mode, reference the sorting index rather ** than the source table */ int sortingIdx; /* Cursor number of the sorting index */ + int sortingIdxPTab; /* Cursor number of pseudo-table */ ExprList *pGroupBy; /* The group by clause */ int nSortingColumn; /* Number of columns in the sorting index */ struct AggInfo_col { /* For each column used in source tables */ Table *pTab; /* Source table */ int iTable; /* Cursor number of the source table */ @@ -2100,10 +2093,11 @@ #define SF_Resolved 0x0002 /* Identifiers have been resolved */ #define SF_Aggregate 0x0004 /* Contains aggregate functions */ #define SF_UsesEphemeral 0x0008 /* Uses the OpenEphemeral opcode */ #define SF_Expanded 0x0010 /* sqlite3SelectExpand() called on this */ #define SF_HasTypeInfo 0x0020 /* FROM subqueries have Table metadata */ +#define SF_UseSorter 0x0040 /* Sort using a sorter */ /* ** The results of a select can be distributed in several ways. The ** "SRT" prefix means "SELECT Result Type". Index: src/test1.c ================================================================== --- src/test1.c +++ src/test1.c @@ -4393,11 +4393,11 @@ ** Fill the stack with a known bitpattern. */ static void prepStack(void){ int i; u32 bigBuf[65536]; - for(i=0; i=4 ){ + const char *zKey; + int nKey; + zKey = Tcl_GetStringFromObj(objv[3], &nKey); + rc = sqlite3_key(db, zKey, nKey); + if( rc!=SQLITE_OK ){ + char *zErrMsg = sqlite3_mprintf("error %d: %s", rc, sqlite3_errmsg(db)); + sqlite3_close(db); + Tcl_AppendResult(interp, zErrMsg, (char*)0); + sqlite3_free(zErrMsg); + return TCL_ERROR; + } + } +#endif Md5_Register(db); sqlite3_busy_handler(db, xBusy, 0); if( sqlite3TestMakePointerStr(interp, zBuf, db) ) return TCL_ERROR; Tcl_AppendResult(interp, zBuf, 0); @@ -347,11 +362,11 @@ interp, objv[1], aSub, sizeof(aSub[0]), "sub-command", 0, &iIndex ); if( rc!=TCL_OK ) return rc; pSub = &aSub[iIndex]; - if( objc!=(pSub->nArg+2) ){ + if( objc<(pSub->nArg+2) ){ Tcl_WrongNumArgs(interp, 2, objv, pSub->zUsage); return TCL_ERROR; } return pSub->xProc(clientData, interp, objc, objv); Index: src/vdbe.c ================================================================== --- src/vdbe.c +++ src/vdbe.c @@ -671,11 +671,11 @@ if( pOp->opflags & OPFLG_OUT2_PRERELEASE ){ assert( pOp->p2>0 ); assert( pOp->p2<=p->nMem ); pOut = &aMem[pOp->p2]; memAboutToChange(p, pOut); - sqlite3VdbeMemReleaseExternal(pOut); + MemReleaseExt(pOut); pOut->flags = MEM_Int; } /* Sanity checking on other operands */ #ifdef SQLITE_DEBUG @@ -2116,10 +2116,11 @@ u8 *zEndHdr; /* Pointer to first byte after the header */ u32 offset; /* Offset into the data */ u32 szField; /* Number of bytes in the content of a field */ int szHdr; /* Size of the header size field at start of record */ int avail; /* Number of bytes of available data */ + u32 t; /* A type code from the record header */ Mem *pReg; /* PseudoTable input register */ p1 = pOp->p1; p2 = pOp->p2; @@ -2127,11 +2128,10 @@ memset(&sMem, 0, sizeof(sMem)); assert( p1nCursor ); assert( pOp->p3>0 && pOp->p3<=p->nMem ); pDest = &aMem[pOp->p3]; memAboutToChange(p, pDest); - MemSetTypeFlag(pDest, MEM_Null); zRec = 0; /* This block sets the variable payloadSize to be the total number of ** bytes in the record. ** @@ -2171,11 +2171,11 @@ }else{ assert( sqlite3BtreeCursorIsValid(pCrsr) ); rc = sqlite3BtreeDataSize(pCrsr, &payloadSize); assert( rc==SQLITE_OK ); /* DataSize() cannot fail */ } - }else if( pC->pseudoTableReg>0 ){ + }else if( ALWAYS(pC->pseudoTableReg>0) ){ pReg = &aMem[pC->pseudoTableReg]; assert( pReg->flags & MEM_Blob ); assert( memIsValid(pReg) ); payloadSize = pReg->n; zRec = pReg->z; @@ -2184,13 +2184,14 @@ }else{ /* Consider the row to be NULL */ payloadSize = 0; } - /* If payloadSize is 0, then just store a NULL */ + /* If payloadSize is 0, then just store a NULL. This can happen because of + ** nullRow or because of a corrupt database. */ if( payloadSize==0 ){ - assert( pDest->flags&MEM_Null ); + MemSetTypeFlag(pDest, MEM_Null); goto op_column_out; } assert( db->aLimit[SQLITE_LIMIT_LENGTH]>=0 ); if( payloadSize > (u32)db->aLimit[SQLITE_LIMIT_LENGTH] ){ goto too_big; @@ -2293,12 +2294,18 @@ ** of the record to the start of the data for the i-th column */ for(i=0; iisIndex, &sMem); @@ -2352,11 +2359,11 @@ pDest->enc = encoding; }else{ if( pOp->p4type==P4_MEM ){ sqlite3VdbeMemShallowCopy(pDest, pOp->p4.pMem, MEM_Static); }else{ - assert( pDest->flags&MEM_Null ); + MemSetTypeFlag(pDest, MEM_Null); } } /* If we dynamically allocated space to hold the data (in the ** sqlite3VdbeMemFromBtree() call above) then transfer control of that @@ -2548,11 +2555,11 @@ case OP_Count: { /* out2-prerelease */ i64 nEntry; BtCursor *pCrsr; pCrsr = p->apCsr[pOp->p1]->pCursor; - if( pCrsr ){ + if( ALWAYS(pCrsr) ){ rc = sqlite3BtreeCount(pCrsr, &nEntry); }else{ nEntry = 0; } pOut->u.i = nEntry; @@ -3110,19 +3117,13 @@ pCur->nullRow = 1; pCur->isOrdered = 1; rc = sqlite3BtreeCursor(pX, p2, wrFlag, pKeyInfo, pCur->pCursor); pCur->pKeyInfo = pKeyInfo; - /* Since it performs no memory allocation or IO, the only values that - ** sqlite3BtreeCursor() may return are SQLITE_EMPTY and SQLITE_OK. - ** SQLITE_EMPTY is only returned when attempting to open the table - ** rooted at page 1 of a zero-byte database. */ - assert( rc==SQLITE_EMPTY || rc==SQLITE_OK ); - if( rc==SQLITE_EMPTY ){ - pCur->pCursor = 0; - rc = SQLITE_OK; - } + /* Since it performs no memory allocation or IO, the only value that + ** sqlite3BtreeCursor() may return is SQLITE_OK. */ + assert( rc==SQLITE_OK ); /* Set the VdbeCursor.isTable and isIndex variables. Previous versions of ** SQLite used to check if the root-page flags were sane at this point ** and report database corruption if they were not, but this check has ** since moved into the btree layer. */ @@ -3159,17 +3160,10 @@ ** This opcode works the same as OP_OpenEphemeral. It has a ** different name to distinguish its use. Tables created using ** by this opcode will be used for automatically created transient ** indices in joins. */ -/* Opcode: OpenSorter P1 P2 * P4 * -** -** This opcode works like OP_OpenEphemeral except that it opens -** a transient index that is specifically designed to sort large -** tables using an external merge-sort algorithm. -*/ -case OP_OpenSorter: case OP_OpenAutoindex: case OP_OpenEphemeral: { VdbeCursor *pCx; static const int vfsFlags = SQLITE_OPEN_READWRITE | @@ -3177,11 +3171,10 @@ SQLITE_OPEN_EXCLUSIVE | SQLITE_OPEN_DELETEONCLOSE | SQLITE_OPEN_TRANSIENT_DB; assert( pOp->p1>=0 ); - assert( (pOp->opcode==OP_OpenSorter)==((pOp->p5 & BTREE_SORTER)!=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); @@ -3211,14 +3204,31 @@ pCx->isTable = 1; } } pCx->isOrdered = (pOp->p5!=BTREE_UNORDERED); pCx->isIndex = !pCx->isTable; + break; +} + +/* Opcode: OpenSorter P1 P2 * P4 * +** +** This opcode works like OP_OpenEphemeral except that it opens +** a transient index that is specifically designed to sort large +** tables using an external merge-sort algorithm. +*/ +case OP_SorterOpen: { + VdbeCursor *pCx; #ifndef SQLITE_OMIT_MERGE_SORT - if( rc==SQLITE_OK && pOp->opcode==OP_OpenSorter ){ - rc = sqlite3VdbeSorterInit(db, pCx); - } + pCx = allocateCursor(p, pOp->p1, pOp->p2, -1, 1); + if( pCx==0 ) goto no_mem; + pCx->pKeyInfo = pOp->p4.pKeyInfo; + pCx->pKeyInfo->enc = ENC(p->db); + pCx->isSorter = 1; + rc = sqlite3VdbeSorterInit(db, pCx); +#else + pOp->opcode = OP_OpenEphemeral; + pc--; #endif break; } /* Opcode: OpenPseudo P1 P2 P3 * * @@ -3331,11 +3341,11 @@ assert( pC->pseudoTableReg==0 ); assert( OP_SeekLe == OP_SeekLt+1 ); assert( OP_SeekGe == OP_SeekLt+2 ); assert( OP_SeekGt == OP_SeekLt+3 ); assert( pC->isOrdered ); - if( pC->pCursor!=0 ){ + if( ALWAYS(pC->pCursor!=0) ){ oc = pOp->opcode; pC->nullRow = 0; if( pC->isTable ){ /* The input value in P3 might be of any type: integer, real, string, ** blob, or NULL. But it needs to be an integer before we can do @@ -3519,10 +3529,11 @@ case OP_NotFound: /* jump, in3 */ case OP_Found: { /* jump, in3 */ int alreadyExists; VdbeCursor *pC; int res; + char *pFree; UnpackedRecord *pIdxKey; UnpackedRecord r; char aTempRec[ROUND8(sizeof(UnpackedRecord)) + sizeof(Mem)*3 + 7]; #ifdef SQLITE_TEST @@ -3546,22 +3557,22 @@ { int i; for(i=0; ipKeyInfo, aTempRec, sizeof(aTempRec), &pFree + ); + if( pIdxKey==0 ) goto no_mem; assert( pIn3->flags & MEM_Blob ); assert( (pIn3->flags & MEM_Zero)==0 ); /* zeroblobs already expanded */ - pIdxKey = sqlite3VdbeRecordUnpack(pC->pKeyInfo, pIn3->n, pIn3->z, - aTempRec, sizeof(aTempRec)); - if( pIdxKey==0 ){ - goto no_mem; - } + sqlite3VdbeRecordUnpack(pC->pKeyInfo, pIn3->n, pIn3->z, pIdxKey); pIdxKey->flags |= UNPACKED_PREFIX_MATCH; } rc = sqlite3BtreeMovetoUnpacked(pC->pCursor, pIdxKey, 0, 0, &res); if( pOp->p4.i==0 ){ - sqlite3VdbeDeleteUnpackedRecord(pIdxKey); + sqlite3DbFree(db, pFree); } if( rc!=SQLITE_OK ){ break; } alreadyExists = (res==0); @@ -3689,11 +3700,11 @@ pC = p->apCsr[pOp->p1]; assert( pC!=0 ); assert( pC->isTable ); assert( pC->pseudoTableReg==0 ); pCrsr = pC->pCursor; - if( pCrsr!=0 ){ + if( ALWAYS(pCrsr!=0) ){ res = 0; iKey = pIn3->u.i; rc = sqlite3BtreeMovetoUnpacked(pCrsr, 0, iKey, 0, &res); pC->lastRowid = pIn3->u.i; pC->rowidIsValid = res==0 ?1:0; @@ -4066,10 +4077,49 @@ case OP_ResetCount: { sqlite3VdbeSetChanges(db, p->nChange); p->nChange = 0; break; } + +/* Opcode: SorterCompare P1 P2 P3 +** +** P1 is a sorter cursor. This instruction compares the record blob in +** register P3 with the entry that the sorter cursor currently points to. +** If, excluding the rowid fields at the end, the two records are a match, +** fall through to the next instruction. Otherwise, jump to instruction P2. +*/ +case OP_SorterCompare: { + VdbeCursor *pC; + int res; + + pC = p->apCsr[pOp->p1]; + assert( isSorter(pC) ); + pIn3 = &aMem[pOp->p3]; + rc = sqlite3VdbeSorterCompare(pC, pIn3, &res); + if( res ){ + pc = pOp->p2-1; + } + break; +}; + +/* Opcode: SorterData P1 P2 * * * +** +** Write into register P2 the current sorter data for sorter cursor P1. +*/ +case OP_SorterData: { + VdbeCursor *pC; +#ifndef SQLITE_OMIT_MERGE_SORT + pOut = &aMem[pOp->p2]; + pC = p->apCsr[pOp->p1]; + assert( pC->isSorter ); + rc = sqlite3VdbeSorterRowkey(pC, pOut); +#else + pOp->opcode = OP_RowKey; + pc--; +#endif + break; +} /* Opcode: RowData P1 P2 * * * ** ** Write into register P2 the complete row data for cursor P1. ** There is no interpretation of the data. @@ -4100,22 +4150,17 @@ memAboutToChange(p, pOut); /* Note that RowKey and RowData are really exactly the same instruction */ assert( pOp->p1>=0 && pOp->p1nCursor ); pC = p->apCsr[pOp->p1]; - assert( pC->isTable || pOp->opcode==OP_RowKey ); + assert( pC->isSorter==0 ); + assert( pC->isTable || pOp->opcode!=OP_RowData ); assert( pC->isIndex || pOp->opcode==OP_RowData ); assert( pC!=0 ); assert( pC->nullRow==0 ); assert( pC->pseudoTableReg==0 ); - - if( isSorter(pC) ){ - assert( pOp->opcode==OP_RowKey ); - rc = sqlite3VdbeSorterRowkey(pC, pOut); - break; - } - + assert( !pC->isSorter ); assert( pC->pCursor!=0 ); pCrsr = pC->pCursor; assert( sqlite3BtreeCursorIsValid(pCrsr) ); /* The OP_RowKey and OP_RowData opcodes always follow OP_NotExists or @@ -4216,10 +4261,11 @@ assert( pOp->p1>=0 && pOp->p1nCursor ); pC = p->apCsr[pOp->p1]; assert( pC!=0 ); pC->nullRow = 1; pC->rowidIsValid = 0; + assert( pC->pCursor || pC->pVtabCursor ); if( pC->pCursor ){ sqlite3BtreeClearCursor(pC->pCursor); } break; } @@ -4239,11 +4285,11 @@ assert( pOp->p1>=0 && pOp->p1nCursor ); pC = p->apCsr[pOp->p1]; assert( pC!=0 ); pCrsr = pC->pCursor; - if( pCrsr==0 ){ + if( NEVER(pCrsr==0) ){ res = 1; }else{ rc = sqlite3BtreeLast(pCrsr, &res); } pC->nullRow = (u8)res; @@ -4267,10 +4313,14 @@ ** end. We use the OP_Sort opcode instead of OP_Rewind to do the ** rewinding so that the global variable will be incremented and ** regression tests can determine whether or not the optimizer is ** correctly optimizing out sorts. */ +case OP_SorterSort: /* jump */ +#ifdef SQLITE_OMIT_MERGE_SORT + pOp->opcode = OP_Sort; +#endif case OP_Sort: { /* jump */ #ifdef SQLITE_TEST sqlite3_sort_count++; sqlite3_search_count--; #endif @@ -4291,14 +4341,17 @@ int res; assert( pOp->p1>=0 && pOp->p1nCursor ); pC = p->apCsr[pOp->p1]; assert( pC!=0 ); + assert( pC->isSorter==(pOp->opcode==OP_SorterSort) ); res = 1; if( isSorter(pC) ){ rc = sqlite3VdbeSorterRewind(db, pC, &res); - }else if( (pCrsr = pC->pCursor)!=0 ){ + }else{ + pCrsr = pC->pCursor; + assert( pCrsr ); rc = sqlite3BtreeFirst(pCrsr, &res); pC->atFirst = res==0 ?1:0; pC->deferredMoveto = 0; pC->cacheStatus = CACHE_STALE; pC->rowidIsValid = 0; @@ -4309,18 +4362,21 @@ pc = pOp->p2 - 1; } break; } -/* Opcode: Next P1 P2 * * P5 +/* Opcode: Next P1 P2 * P4 P5 ** ** Advance cursor P1 so that it points to the next key/data pair in its ** table or index. If there are no more key/value pairs then fall through ** to the following instruction. But if the cursor advance was successful, ** jump immediately to P2. ** ** The P1 cursor must be for a real table, not a pseudo-table. +** +** P4 is always of type P4_ADVANCE. The function pointer points to +** sqlite3BtreeNext(). ** ** If P5 is positive and the jump is taken, then event counter ** number P5-1 in the prepared statement is incremented. ** ** See also: Prev @@ -4331,40 +4387,44 @@ ** table or index. If there is no previous key/value pairs then fall through ** to the following instruction. But if the cursor backup was successful, ** jump immediately to P2. ** ** The P1 cursor must be for a real table, not a pseudo-table. +** +** P4 is always of type P4_ADVANCE. The function pointer points to +** sqlite3BtreePrevious(). ** ** If P5 is positive and the jump is taken, then event counter ** number P5-1 in the prepared statement is incremented. */ +case OP_SorterNext: /* jump */ +#ifdef SQLITE_OMIT_MERGE_SORT + pOp->opcode = OP_Next; +#endif case OP_Prev: /* jump */ case OP_Next: { /* jump */ VdbeCursor *pC; - BtCursor *pCrsr; int res; CHECK_FOR_INTERRUPT; assert( pOp->p1>=0 && pOp->p1nCursor ); assert( pOp->p5<=ArraySize(p->aCounter) ); pC = p->apCsr[pOp->p1]; if( pC==0 ){ break; /* See ticket #2273 */ } + assert( pC->isSorter==(pOp->opcode==OP_SorterNext) ); if( isSorter(pC) ){ - assert( pOp->opcode==OP_Next ); + assert( pOp->opcode==OP_SorterNext ); 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); + assert( pC->pCursor ); + assert( pOp->opcode!=OP_Next || pOp->p4.xAdvance==sqlite3BtreeNext ); + assert( pOp->opcode!=OP_Prev || pOp->p4.xAdvance==sqlite3BtreePrevious ); + rc = pOp->p4.xAdvance(pC->pCursor, &res); } pC->nullRow = (u8)res; pC->cacheStatus = CACHE_STALE; if( res==0 ){ pc = pOp->p2 - 1; @@ -4387,36 +4447,42 @@ ** insert is likely to be an append. ** ** This instruction only works for indices. The equivalent instruction ** for tables is OP_Insert. */ +case OP_SorterInsert: /* in2 */ +#ifdef SQLITE_OMIT_MERGE_SORT + pOp->opcode = OP_IdxInsert; +#endif case OP_IdxInsert: { /* in2 */ VdbeCursor *pC; BtCursor *pCrsr; int nKey; const char *zKey; assert( pOp->p1>=0 && pOp->p1nCursor ); pC = p->apCsr[pOp->p1]; assert( pC!=0 ); + assert( pC->isSorter==(pOp->opcode==OP_SorterInsert) ); pIn2 = &aMem[pOp->p2]; assert( pIn2->flags & MEM_Blob ); pCrsr = pC->pCursor; if( ALWAYS(pCrsr!=0) ){ assert( pC->isTable==0 ); rc = ExpandBlob(pIn2); if( rc==SQLITE_OK ){ - nKey = pIn2->n; - zKey = pIn2->z; - rc = sqlite3VdbeSorterWrite(db, pC, nKey); - if( rc==SQLITE_OK ){ + if( isSorter(pC) ){ + rc = sqlite3VdbeSorterWrite(db, pC, pIn2); + }else{ + nKey = pIn2->n; + zKey = pIn2->z; rc = sqlite3BtreeInsert(pCrsr, zKey, nKey, "", 0, 0, pOp->p3, ((pOp->p5 & OPFLAG_USESEEKRESULT) ? pC->seekResult : 0) - ); + ); assert( pC->deferredMoveto==0 ); + pC->cacheStatus = CACHE_STALE; } - pC->cacheStatus = CACHE_STALE; } } break; } Index: src/vdbe.h ================================================================== --- src/vdbe.h +++ src/vdbe.h @@ -59,10 +59,11 @@ Mem *pMem; /* Used when p4type is P4_MEM */ VTable *pVtab; /* Used when p4type is P4_VTAB */ KeyInfo *pKeyInfo; /* Used when p4type is P4_KEYINFO */ int *ai; /* Used when p4type is P4_INTARRAY */ SubProgram *pProgram; /* Used when p4type is P4_SUBPROGRAM */ + int (*xAdvance)(BtCursor *, int *); } p4; #ifdef SQLITE_DEBUG char *zComment; /* Comment to improve readability */ #endif #ifdef VDBE_PROFILE @@ -114,10 +115,11 @@ #define P4_REAL (-12) /* P4 is a 64-bit floating point value */ #define P4_INT64 (-13) /* P4 is a 64-bit signed integer */ #define P4_INT32 (-14) /* P4 is a 32-bit signed integer */ #define P4_INTARRAY (-15) /* P4 is a vector of 32-bit integers */ #define P4_SUBPROGRAM (-18) /* P4 is a pointer to a SubProgram structure */ +#define P4_ADVANCE (-19) /* P4 is a pointer to BtreeNext() or BtreePrev() */ /* When adding a P4 argument using P4_KEYINFO, a copy of the KeyInfo structure ** is made. That copy is freed when the Vdbe is finalized. But if the ** argument is P4_KEYINFO_HANDOFF, the passed in pointer is used. It still ** gets freed when the Vdbe is finalized so it still should be obtained @@ -208,13 +210,13 @@ void sqlite3VdbeSetVarmask(Vdbe*, int); #ifndef SQLITE_OMIT_TRACE char *sqlite3VdbeExpandSql(Vdbe*, const char*); #endif -UnpackedRecord *sqlite3VdbeRecordUnpack(KeyInfo*,int,const void*,char*,int); -void sqlite3VdbeDeleteUnpackedRecord(UnpackedRecord*); +void sqlite3VdbeRecordUnpack(KeyInfo*,int,const void*,UnpackedRecord*); int sqlite3VdbeRecordCompare(int,const void*,UnpackedRecord*); +UnpackedRecord *sqlite3VdbeAllocUnpackedRecord(KeyInfo *, char *, int, char **); #ifndef SQLITE_OMIT_TRIGGER void sqlite3VdbeLinkSubProgram(Vdbe *, SubProgram *); #endif Index: src/vdbeInt.h ================================================================== --- src/vdbeInt.h +++ src/vdbeInt.h @@ -57,16 +57,17 @@ Bool nullRow; /* True if pointing to a row with no data */ Bool deferredMoveto; /* A call to sqlite3BtreeMoveto() is needed */ Bool isTable; /* True if a table requiring integer keys */ Bool isIndex; /* True if an index containing keys only - no data */ Bool isOrdered; /* True if the underlying table is BTREE_UNORDERED */ + Bool isSorter; /* True if a new-style sorter */ sqlite3_vtab_cursor *pVtabCursor; /* The cursor for a virtual table */ const sqlite3_module *pModule; /* Module for cursor pVtabCursor */ 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 */ + VdbeSorter *pSorter; /* Sorter object for OP_SorterOpen cursors */ /* Result of last sqlite3BtreeMoveto() done by an OP_NotExists or ** OP_IsUnique opcode on this cursor. */ int seekResult; @@ -382,10 +383,13 @@ int sqlite3VdbeMemRealify(Mem*); int sqlite3VdbeMemNumerify(Mem*); int sqlite3VdbeMemFromBtree(BtCursor*,int,int,int,Mem*); void sqlite3VdbeMemRelease(Mem *p); void sqlite3VdbeMemReleaseExternal(Mem *p); +#define MemReleaseExt(X) \ + if((X)->flags&(MEM_Agg|MEM_Dyn|MEM_RowSet|MEM_Frame)) \ + sqlite3VdbeMemReleaseExternal(X); int sqlite3VdbeMemFinalize(Mem*, FuncDef*); const char *sqlite3OpcodeName(int); int sqlite3VdbeMemGrow(Mem *pMem, int n, int preserve); int sqlite3VdbeCloseStatement(Vdbe *, int); void sqlite3VdbeFrameDelete(VdbeFrame*); @@ -397,17 +401,19 @@ # define sqlite3VdbeSorterWrite(X,Y,Z) SQLITE_OK # define sqlite3VdbeSorterClose(Y,Z) # define sqlite3VdbeSorterRowkey(Y,Z) SQLITE_OK # define sqlite3VdbeSorterRewind(X,Y,Z) SQLITE_OK # define sqlite3VdbeSorterNext(X,Y,Z) SQLITE_OK +# define sqlite3VdbeSorterCompare(X,Y,Z) SQLITE_OK #else int sqlite3VdbeSorterInit(sqlite3 *, VdbeCursor *); -int sqlite3VdbeSorterWrite(sqlite3 *, VdbeCursor *, int); void sqlite3VdbeSorterClose(sqlite3 *, VdbeCursor *); int sqlite3VdbeSorterRowkey(VdbeCursor *, Mem *); -int sqlite3VdbeSorterRewind(sqlite3 *, VdbeCursor *, int *); int sqlite3VdbeSorterNext(sqlite3 *, VdbeCursor *, int *); +int sqlite3VdbeSorterRewind(sqlite3 *, VdbeCursor *, int *); +int sqlite3VdbeSorterWrite(sqlite3 *, VdbeCursor *, Mem *); +int sqlite3VdbeSorterCompare(VdbeCursor *, Mem *, int *); #endif #if !defined(SQLITE_OMIT_SHARED_CACHE) && SQLITE_THREADSAFE>0 void sqlite3VdbeEnter(Vdbe*); void sqlite3VdbeLeave(Vdbe*); Index: src/vdbeaux.c ================================================================== --- src/vdbeaux.c +++ src/vdbeaux.c @@ -431,10 +431,16 @@ assert( p->nOp - i >= 3 ); assert( pOp[-1].opcode==OP_Integer ); n = pOp[-1].p1; if( n>nMaxArgs ) nMaxArgs = n; #endif + }else if( opcode==OP_Next || opcode==OP_SorterNext ){ + pOp->p4.xAdvance = sqlite3BtreeNext; + pOp->p4type = P4_ADVANCE; + }else if( opcode==OP_Prev ){ + pOp->p4.xAdvance = sqlite3BtreePrevious; + pOp->p4type = P4_ADVANCE; } if( (pOp->opflags & OPFLG_JUMP)!=0 && pOp->p2<0 ){ assert( -1-pOp->p2nLabel ); pOp->p2 = aLabel[-1-pOp->p2]; @@ -936,10 +942,14 @@ break; } case P4_SUBPROGRAM: { sqlite3_snprintf(nTemp, zTemp, "program"); break; + } + case P4_ADVANCE: { + zTemp[0] = 0; + break; } default: { zP4 = pOp->p4.z; if( zP4==0 ){ zP4 = zTemp; @@ -2818,61 +2828,74 @@ } } return 0; } - -/* -** Given the nKey-byte encoding of a record in pKey[], parse the -** record into a UnpackedRecord structure. Return a pointer to -** that structure. -** -** The calling function might provide szSpace bytes of memory -** space at pSpace. This space can be used to hold the returned -** VDbeParsedRecord structure if it is large enough. If it is -** not big enough, space is obtained from sqlite3_malloc(). -** -** The returned structure should be closed by a call to -** sqlite3VdbeDeleteUnpackedRecord(). -*/ -UnpackedRecord *sqlite3VdbeRecordUnpack( - KeyInfo *pKeyInfo, /* Information about the record format */ - int nKey, /* Size of the binary record */ - const void *pKey, /* The binary record */ - char *pSpace, /* Unaligned space available to hold the object */ - int szSpace /* Size of pSpace[] in bytes */ +/* +** This routine is used to allocate sufficient space for an UnpackedRecord +** structure large enough to be used with sqlite3VdbeRecordUnpack() if +** the first argument is a pointer to KeyInfo structure pKeyInfo. +** +** The space is either allocated using sqlite3DbMallocRaw() or from within +** the unaligned buffer passed via the second and third arguments (presumably +** stack space). If the former, then *ppFree is set to a pointer that should +** be eventually freed by the caller using sqlite3DbFree(). Or, if the +** allocation comes from the pSpace/szSpace buffer, *ppFree is set to NULL +** before returning. +** +** If an OOM error occurs, NULL is returned. +*/ +UnpackedRecord *sqlite3VdbeAllocUnpackedRecord( + KeyInfo *pKeyInfo, /* Description of the record */ + char *pSpace, /* Unaligned space available */ + int szSpace, /* Size of pSpace[] in bytes */ + char **ppFree /* OUT: Caller should free this pointer */ ){ - const unsigned char *aKey = (const unsigned char *)pKey; - UnpackedRecord *p; /* The unpacked record that we will return */ - int nByte; /* Memory space needed to hold p, in bytes */ - int d; - u32 idx; - u16 u; /* Unsigned loop counter */ - u32 szHdr; - Mem *pMem; - int nOff; /* Increase pSpace by this much to 8-byte align it */ - - /* - ** We want to shift the pointer pSpace up such that it is 8-byte aligned. + UnpackedRecord *p; /* Unpacked record to return */ + int nOff; /* Increment pSpace by nOff to align it */ + int nByte; /* Number of bytes required for *p */ + + /* We want to shift the pointer pSpace up such that it is 8-byte aligned. ** Thus, we need to calculate a value, nOff, between 0 and 7, to shift ** it by. If pSpace is already 8-byte aligned, nOff should be zero. */ nOff = (8 - (SQLITE_PTR_TO_INT(pSpace) & 7)) & 7; - pSpace += nOff; - szSpace -= nOff; nByte = ROUND8(sizeof(UnpackedRecord)) + sizeof(Mem)*(pKeyInfo->nField+1); - if( nByte>szSpace ){ - p = sqlite3DbMallocRaw(pKeyInfo->db, nByte); - if( p==0 ) return 0; - p->flags = UNPACKED_NEED_FREE | UNPACKED_NEED_DESTROY; + if( nByte>szSpace+nOff ){ + p = (UnpackedRecord *)sqlite3DbMallocRaw(pKeyInfo->db, nByte); + *ppFree = (char *)p; + if( !p ) return 0; }else{ - p = (UnpackedRecord*)pSpace; - p->flags = UNPACKED_NEED_DESTROY; + p = (UnpackedRecord*)&pSpace[nOff]; + *ppFree = 0; } + + p->aMem = (Mem*)&((char*)p)[ROUND8(sizeof(UnpackedRecord))]; p->pKeyInfo = pKeyInfo; p->nField = pKeyInfo->nField + 1; - p->aMem = pMem = (Mem*)&((char*)p)[ROUND8(sizeof(UnpackedRecord))]; + return p; +} + +/* +** Given the nKey-byte encoding of a record in pKey[], populate the +** UnpackedRecord structure indicated by the fourth argument with the +** contents of the decoded record. +*/ +void sqlite3VdbeRecordUnpack( + KeyInfo *pKeyInfo, /* Information about the record format */ + int nKey, /* Size of the binary record */ + const void *pKey, /* The binary record */ + UnpackedRecord *p /* Populate this structure before returning. */ +){ + const unsigned char *aKey = (const unsigned char *)pKey; + int d; + u32 idx; /* Offset in aKey[] to read from */ + u16 u; /* Unsigned loop counter */ + u32 szHdr; + Mem *pMem = p->aMem; + + p->flags = 0; assert( EIGHT_BYTE_ALIGNMENT(pMem) ); idx = getVarint32(aKey, szHdr); d = szHdr; u = 0; while( idxnField && d<=nKey ){ @@ -2887,35 +2910,10 @@ pMem++; u++; } assert( u<=pKeyInfo->nField + 1 ); p->nField = u; - return (void*)p; -} - -/* -** This routine destroys a UnpackedRecord object. -*/ -void sqlite3VdbeDeleteUnpackedRecord(UnpackedRecord *p){ -#ifdef SQLITE_DEBUG - int i; - Mem *pMem; - - assert( p!=0 ); - assert( p->flags & UNPACKED_NEED_DESTROY ); - for(i=0, pMem=p->aMem; inField; i++, pMem++){ - /* The unpacked record is always constructed by the - ** sqlite3VdbeUnpackRecord() function above, which makes all - ** strings and blobs static. And none of the elements are - ** ever transformed, so there is never anything to delete. - */ - if( NEVER(pMem->zMalloc) ) sqlite3VdbeMemRelease(pMem); - } -#endif - if( p->flags & UNPACKED_NEED_FREE ){ - sqlite3DbFree(p->pKeyInfo->db, p); - } } /* ** This function compares the two table rows or index records ** specified by {nKey1, pKey1} and pPKey2. It returns a negative, zero Index: src/vdbemem.c ================================================================== --- src/vdbemem.c +++ src/vdbemem.c @@ -269,38 +269,32 @@ ** invoking an external callback, free it now. Calling this function ** does not free any Mem.zMalloc buffer. */ void sqlite3VdbeMemReleaseExternal(Mem *p){ assert( p->db==0 || sqlite3_mutex_held(p->db->mutex) ); - testcase( p->flags & MEM_Agg ); - testcase( p->flags & MEM_Dyn ); - testcase( p->flags & MEM_RowSet ); - testcase( p->flags & MEM_Frame ); - if( p->flags&(MEM_Agg|MEM_Dyn|MEM_RowSet|MEM_Frame) ){ - if( p->flags&MEM_Agg ){ - sqlite3VdbeMemFinalize(p, p->u.pDef); - assert( (p->flags & MEM_Agg)==0 ); - sqlite3VdbeMemRelease(p); - }else if( p->flags&MEM_Dyn && p->xDel ){ - assert( (p->flags&MEM_RowSet)==0 ); - p->xDel((void *)p->z); - p->xDel = 0; - }else if( p->flags&MEM_RowSet ){ - sqlite3RowSetClear(p->u.pRowSet); - }else if( p->flags&MEM_Frame ){ - sqlite3VdbeMemSetNull(p); - } + if( p->flags&MEM_Agg ){ + sqlite3VdbeMemFinalize(p, p->u.pDef); + assert( (p->flags & MEM_Agg)==0 ); + sqlite3VdbeMemRelease(p); + }else if( p->flags&MEM_Dyn && p->xDel ){ + assert( (p->flags&MEM_RowSet)==0 ); + p->xDel((void *)p->z); + p->xDel = 0; + }else if( p->flags&MEM_RowSet ){ + sqlite3RowSetClear(p->u.pRowSet); + }else if( p->flags&MEM_Frame ){ + sqlite3VdbeMemSetNull(p); } } /* ** Release any memory held by the Mem. This may leave the Mem in an ** inconsistent state, for example with (Mem.z==0) and ** (Mem.type==SQLITE_TEXT). */ void sqlite3VdbeMemRelease(Mem *p){ - sqlite3VdbeMemReleaseExternal(p); + MemReleaseExt(p); sqlite3DbFree(p->db, p->zMalloc); p->z = 0; p->zMalloc = 0; p->xDel = 0; } @@ -618,11 +612,11 @@ ** pFrom->z is used, then pTo->z points to the same thing as pFrom->z ** and flags gets srcType (either MEM_Ephem or MEM_Static). */ void sqlite3VdbeMemShallowCopy(Mem *pTo, const Mem *pFrom, int srcType){ assert( (pFrom->flags & MEM_RowSet)==0 ); - sqlite3VdbeMemReleaseExternal(pTo); + MemReleaseExt(pTo); memcpy(pTo, pFrom, MEMCELLSIZE); pTo->xDel = 0; if( (pFrom->flags&MEM_Static)==0 ){ pTo->flags &= ~(MEM_Dyn|MEM_Static|MEM_Ephem); assert( srcType==MEM_Ephem || srcType==MEM_Static ); @@ -636,11 +630,11 @@ */ int sqlite3VdbeMemCopy(Mem *pTo, const Mem *pFrom){ int rc = SQLITE_OK; assert( (pFrom->flags & MEM_RowSet)==0 ); - sqlite3VdbeMemReleaseExternal(pTo); + MemReleaseExt(pTo); memcpy(pTo, pFrom, MEMCELLSIZE); pTo->flags &= ~MEM_Dyn; if( pTo->flags&(MEM_Str|MEM_Blob) ){ if( 0==(pFrom->flags&MEM_Static) ){ Index: src/vdbesort.c ================================================================== --- src/vdbesort.c +++ src/vdbesort.c @@ -19,10 +19,11 @@ #include "vdbeInt.h" #ifndef SQLITE_OMIT_MERGE_SORT typedef struct VdbeSorterIter VdbeSorterIter; +typedef struct SorterRecord SorterRecord; /* ** NOTES ON DATA STRUCTURE USED FOR N-WAY MERGES: ** ** As keys are added to the sorter, they are written to disk in a series @@ -90,19 +91,22 @@ ** In other words, each time we advance to the next sorter element, log2(N) ** key comparison operations are required, where N is the number of segments ** being merged (rounded up to the next power of 2). */ struct VdbeSorter { - int nWorking; /* Start a new b-tree after this many pages */ - int nBtree; /* Current size of b-tree contents as PMA */ + int nInMemory; /* Current size of pRecord list as PMA */ int nTree; /* Used size of aTree/aIter (power of 2) */ VdbeSorterIter *aIter; /* Array of iterators to merge */ int *aTree; /* Current state of incremental merge */ i64 iWriteOff; /* Current write offset within file pTemp1 */ i64 iReadOff; /* Current read offset within file pTemp1 */ sqlite3_file *pTemp1; /* PMA file 1 */ int nPMA; /* Number of PMAs stored in pTemp1 */ + SorterRecord *pRecord; /* Head of in-memory record list */ + int mnPmaSize; /* Minimum PMA size, in bytes */ + int mxPmaSize; /* Maximum PMA size, in bytes. 0==no limit */ + UnpackedRecord *pUnpacked; /* Used to unpack keys */ }; /* ** The following type is an iterator for a PMA. It caches the current key in ** variables nKey/aKey. If the iterator is at EOF, pFile==0. @@ -114,10 +118,21 @@ int nAlloc; /* Bytes of space at aAlloc */ u8 *aAlloc; /* Allocated space */ int nKey; /* Number of bytes in key */ u8 *aKey; /* Pointer to current key */ }; + +/* +** A structure to store a single record. All in-memory records are connected +** together into a linked list headed at VdbeSorter.pRecord using the +** SorterRecord.pNext pointer. +*/ +struct SorterRecord { + void *pVal; + int nVal; + SorterRecord *pNext; +}; /* Minimum allowable value for the VdbeSorter.nWorking variable */ #define SORTER_MIN_WORKING 10 /* Maximum number of segments to merge in a single pass. */ @@ -140,12 +155,12 @@ sqlite3 *db, /* Database handle (for sqlite3DbMalloc() ) */ VdbeSorterIter *pIter /* Iterator to advance */ ){ int rc; /* Return Code */ int nRead; /* Number of bytes read */ - int nRec; /* Size of record in bytes */ - int iOff; /* Size of serialized size varint in bytes */ + int nRec = 0; /* Size of record in bytes */ + int iOff = 0; /* Size of serialized size varint in bytes */ nRead = pIter->iEof - pIter->iReadOff; if( nRead>5 ) nRead = 5; if( nRead<=0 ){ /* This is an EOF condition */ @@ -152,29 +167,30 @@ vdbeSorterIterZero(db, pIter); return SQLITE_OK; } rc = sqlite3OsRead(pIter->pFile, pIter->aAlloc, nRead, pIter->iReadOff); - iOff = getVarint32(pIter->aAlloc, nRec); - - if( rc==SQLITE_OK && (iOff+nRec)>nRead ){ - int nRead2; /* Number of extra bytes to read */ - if( (iOff+nRec)>pIter->nAlloc ){ - int nNew = pIter->nAlloc*2; - while( (iOff+nRec)>nNew ) nNew = nNew*2; - pIter->aAlloc = sqlite3DbReallocOrFree(db, pIter->aAlloc, nNew); - if( !pIter->aAlloc ) return SQLITE_NOMEM; - pIter->nAlloc = nNew; - } - - nRead2 = iOff + nRec - nRead; - rc = sqlite3OsRead( - pIter->pFile, &pIter->aAlloc[nRead], nRead2, pIter->iReadOff+nRead - ); - } - - assert( nRec>0 || rc!=SQLITE_OK ); + if( rc==SQLITE_OK ){ + iOff = getVarint32(pIter->aAlloc, nRec); + if( (iOff+nRec)>nRead ){ + int nRead2; /* Number of extra bytes to read */ + if( (iOff+nRec)>pIter->nAlloc ){ + int nNew = pIter->nAlloc*2; + while( (iOff+nRec)>nNew ) nNew = nNew*2; + pIter->aAlloc = sqlite3DbReallocOrFree(db, pIter->aAlloc, nNew); + if( !pIter->aAlloc ) return SQLITE_NOMEM; + pIter->nAlloc = nNew; + } + + nRead2 = iOff + nRec - nRead; + rc = sqlite3OsRead( + pIter->pFile, &pIter->aAlloc[nRead], nRead2, pIter->iReadOff+nRead + ); + } + } + + assert( rc!=SQLITE_OK || nRec>0 ); pIter->iReadOff += iOff+nRec; pIter->nKey = nRec; pIter->aKey = &pIter->aAlloc[iOff]; return rc; } @@ -214,25 +230,18 @@ ** set to the integer value read. If an error occurs, the final values of ** both *piOffset and *piVal are undefined. */ static int vdbeSorterReadVarint( sqlite3_file *pFile, /* File to read from */ - i64 iEof, /* Total number of bytes in file */ i64 *piOffset, /* IN/OUT: Read offset in pFile */ i64 *piVal /* OUT: Value read from file */ ){ u8 aVarint[9]; /* Buffer large enough for a varint */ i64 iOff = *piOffset; /* Offset in file to read from */ - int nRead = 9; /* Number of bytes to read from file */ int rc; /* Return code */ - assert( iEof>iOff ); - if( (iEof-iOff)nAlloc = 128; pIter->aAlloc = (u8 *)sqlite3DbMallocRaw(db, pIter->nAlloc); if( !pIter->aAlloc ){ rc = SQLITE_NOMEM; }else{ - i64 iEof = pSorter->iWriteOff; /* EOF of file pSorter->pTemp1 */ i64 nByte; /* Total size of PMA in bytes */ - rc = vdbeSorterReadVarint(pSorter->pTemp1, iEof, &pIter->iReadOff, &nByte); + rc = vdbeSorterReadVarint(pSorter->pTemp1, &pIter->iReadOff, &nByte); *pnByte += nByte; pIter->iEof = pIter->iReadOff + nByte; } if( rc==SQLITE_OK ){ rc = vdbeSorterIterNext(db, pIter); } return rc; } + +/* +** Compare key1 (buffer pKey1, size nKey1 bytes) with key2 (buffer pKey2, +** size nKey2 bytes). Argument pKeyInfo supplies the collation functions +** used by the comparison. If an error occurs, return an SQLite error code. +** Otherwise, return SQLITE_OK and set *pRes to a negative, zero or positive +** value, depending on whether key1 is smaller, equal to or larger than key2. +** +** If the bOmitRowid argument is non-zero, assume both keys end in a rowid +** field. For the purposes of the comparison, ignore it. Also, if bOmitRowid +** is true and key1 contains even a single NULL value, it is considered to +** be less than key2. Even if key2 also contains NULL values. +** +** If pKey2 is passed a NULL pointer, then it is assumed that the pCsr->aSpace +** has been allocated and contains an unpacked record that is used as key2. +*/ +static int vdbeSorterCompare( + VdbeCursor *pCsr, /* Cursor object (for pKeyInfo) */ + int bOmitRowid, /* Ignore rowid field at end of keys */ + void *pKey1, int nKey1, /* Left side of comparison */ + void *pKey2, int nKey2, /* Right side of comparison */ + int *pRes /* OUT: Result of comparison */ +){ + KeyInfo *pKeyInfo = pCsr->pKeyInfo; + VdbeSorter *pSorter = pCsr->pSorter; + UnpackedRecord *r2 = pSorter->pUnpacked; + int i; + + if( pKey2 ){ + sqlite3VdbeRecordUnpack(pKeyInfo, nKey2, pKey2, r2); + } + + if( bOmitRowid ){ + r2->nField = pKeyInfo->nField; + assert( r2->nField>0 ); + for(i=0; inField; i++){ + if( r2->aMem[i].flags & MEM_Null ){ + *pRes = -1; + return SQLITE_OK; + } + } + r2->flags |= UNPACKED_PREFIX_MATCH; + } + + *pRes = sqlite3VdbeRecordCompare(nKey1, pKey1, r2); + return SQLITE_OK; +} + /* ** 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. */ @@ -303,24 +359,25 @@ if( p1->pFile==0 ){ iRes = i2; }else if( p2->pFile==0 ){ iRes = i1; }else{ - char aSpace[150]; - UnpackedRecord *r1; - - r1 = sqlite3VdbeRecordUnpack( - pCsr->pKeyInfo, p1->nKey, p1->aKey, aSpace, sizeof(aSpace) + int res; + int rc; + assert( pCsr->pSorter->pUnpacked!=0 ); /* allocated in vdbeSorterMerge() */ + rc = vdbeSorterCompare( + pCsr, 0, p1->aKey, p1->nKey, p2->aKey, p2->nKey, &res ); - if( r1==0 ) return SQLITE_NOMEM; + /* The vdbeSorterCompare() call cannot fail since pCsr->pSorter->pUnpacked + ** has already been allocated. */ + assert( rc==SQLITE_OK ); - if( sqlite3VdbeRecordCompare(p2->nKey, p2->aKey, r1)>=0 ){ + if( res<=0 ){ iRes = i1; }else{ iRes = i2; } - sqlite3VdbeDeleteUnpackedRecord(r1); } pSorter->aTree[iOut] = iRes; return SQLITE_OK; } @@ -327,13 +384,46 @@ /* ** Initialize the temporary index cursor just opened as a sorter cursor. */ int sqlite3VdbeSorterInit(sqlite3 *db, VdbeCursor *pCsr){ - assert( pCsr->pKeyInfo && pCsr->pBt ); - pCsr->pSorter = sqlite3DbMallocZero(db, sizeof(VdbeSorter)); - return (pCsr->pSorter ? SQLITE_OK : SQLITE_NOMEM); + int pgsz; /* Page size of main database */ + int mxCache; /* Cache size */ + VdbeSorter *pSorter; /* The new sorter */ + char *d; /* Dummy */ + + assert( pCsr->pKeyInfo && pCsr->pBt==0 ); + pCsr->pSorter = pSorter = sqlite3DbMallocZero(db, sizeof(VdbeSorter)); + if( pSorter==0 ){ + return SQLITE_NOMEM; + } + + pSorter->pUnpacked = sqlite3VdbeAllocUnpackedRecord(pCsr->pKeyInfo, 0, 0, &d); + if( pSorter->pUnpacked==0 ) return SQLITE_NOMEM; + assert( pSorter->pUnpacked==(UnpackedRecord *)d ); + + if( !sqlite3TempInMemory(db) ){ + pgsz = sqlite3BtreeGetPageSize(db->aDb[0].pBt); + pSorter->mnPmaSize = SORTER_MIN_WORKING * pgsz; + mxCache = db->aDb[0].pSchema->cache_size; + if( mxCachemxPmaSize = mxCache * pgsz; + } + + return SQLITE_OK; +} + +/* +** Free the list of sorted records starting at pRecord. +*/ +static void vdbeSorterRecordFree(sqlite3 *db, SorterRecord *pRecord){ + SorterRecord *p; + SorterRecord *pNext; + for(p=pRecord; p; p=pNext){ + pNext = p->pNext; + sqlite3DbFree(db, p); + } } /* ** Free any cursor components allocated by sqlite3VdbeSorterXXX routines. */ @@ -348,10 +438,12 @@ sqlite3DbFree(db, pSorter->aIter); } if( pSorter->pTemp1 ){ sqlite3OsCloseFree(pSorter->pTemp1); } + vdbeSorterRecordFree(db, pSorter->pRecord); + sqlite3DbFree(db, pSorter->pUnpacked); sqlite3DbFree(db, pSorter); pCsr->pSorter = 0; } } @@ -367,14 +459,107 @@ SQLITE_OPEN_READWRITE | SQLITE_OPEN_CREATE | SQLITE_OPEN_EXCLUSIVE | SQLITE_OPEN_DELETEONCLOSE, &dummy ); } +/* +** Attemp to merge the two sorted lists p1 and p2 into a single list. If no +** error occurs set *ppOut to the head of the new list and return SQLITE_OK. +*/ +static int vdbeSorterMerge( + sqlite3 *db, /* Database handle */ + VdbeCursor *pCsr, /* For pKeyInfo */ + SorterRecord *p1, /* First list to merge */ + SorterRecord *p2, /* Second list to merge */ + SorterRecord **ppOut /* OUT: Head of merged list */ +){ + int rc = SQLITE_OK; + SorterRecord *pFinal = 0; + SorterRecord **pp = &pFinal; + void *pVal2 = p2 ? p2->pVal : 0; + + while( p1 && p2 ){ + int res; + rc = vdbeSorterCompare(pCsr, 0, p1->pVal, p1->nVal, pVal2, p2->nVal, &res); + if( rc!=SQLITE_OK ){ + *pp = 0; + vdbeSorterRecordFree(db, p1); + vdbeSorterRecordFree(db, p2); + vdbeSorterRecordFree(db, pFinal); + *ppOut = 0; + return rc; + } + if( res<=0 ){ + *pp = p1; + pp = &p1->pNext; + p1 = p1->pNext; + pVal2 = 0; + }else{ + *pp = p2; + pp = &p2->pNext; + p2 = p2->pNext; + if( p2==0 ) break; + pVal2 = p2->pVal; + } + } + *pp = p1 ? p1 : p2; + + *ppOut = pFinal; + return SQLITE_OK; +} + +/* +** Sort the linked list of records headed at pCsr->pRecord. Return SQLITE_OK +** if successful, or an SQLite error code (i.e. SQLITE_NOMEM) if an error +** occurs. +*/ +static int vdbeSorterSort(sqlite3 *db, VdbeCursor *pCsr){ + int rc = SQLITE_OK; + int i; + SorterRecord **aSlot; + SorterRecord *p; + VdbeSorter *pSorter = pCsr->pSorter; + + aSlot = (SorterRecord **)sqlite3MallocZero(64 * sizeof(SorterRecord *)); + if( !aSlot ){ + return SQLITE_NOMEM; + } + + p = pSorter->pRecord; + while( p ){ + SorterRecord *pNext = p->pNext; + p->pNext = 0; + for(i=0; rc==SQLITE_OK && aSlot[i]; i++){ + rc = vdbeSorterMerge(db, pCsr, p, aSlot[i], &p); + aSlot[i] = 0; + } + if( rc!=SQLITE_OK ){ + vdbeSorterRecordFree(db, pNext); + break; + } + aSlot[i] = p; + p = pNext; + } + + p = 0; + for(i=0; i<64; i++){ + if( rc==SQLITE_OK ){ + rc = vdbeSorterMerge(db, pCsr, p, aSlot[i], &p); + }else{ + vdbeSorterRecordFree(db, aSlot[i]); + } + } + pSorter->pRecord = p; + + sqlite3_free(aSlot); + return rc; +} + /* -** Write the current contents of the b-tree to a PMA. Return SQLITE_OK -** if successful, or an SQLite error code otherwise. +** Write the current contents of the in-memory linked-list to a PMA. Return +** SQLITE_OK if successful, or an SQLite error code otherwise. ** ** The format of a PMA is: ** ** * A varint. This varint contains the total number of bytes of content ** in the PMA (not including the varint itself). @@ -381,153 +566,111 @@ ** ** * One or more records packed end-to-end in order of ascending keys. ** Each record consists of a varint followed by a blob of data (the ** key). The varint is the number of bytes in the blob of data. */ -static int vdbeSorterBtreeToPMA(sqlite3 *db, VdbeCursor *pCsr){ +static int vdbeSorterListToPMA(sqlite3 *db, VdbeCursor *pCsr){ int rc = SQLITE_OK; /* Return code */ VdbeSorter *pSorter = pCsr->pSorter; - int res = 0; + + if( pSorter->nInMemory==0 ){ + assert( pSorter->pRecord==0 ); + return rc; + } - /* sqlite3BtreeFirst() cannot fail because sorter btrees are always held - ** in memory and so an I/O error is not possible. */ - rc = sqlite3BtreeFirst(pCsr->pCursor, &res); - if( NEVER(rc!=SQLITE_OK) || res ) return rc; - assert( pSorter->nBtree>0 ); + rc = vdbeSorterSort(db, pCsr); /* If the first temporary PMA file has not been opened, open it now. */ - if( pSorter->pTemp1==0 ){ + if( rc==SQLITE_OK && pSorter->pTemp1==0 ){ rc = vdbeSorterOpenTempFile(db, &pSorter->pTemp1); assert( rc!=SQLITE_OK || pSorter->pTemp1 ); assert( pSorter->iWriteOff==0 ); assert( pSorter->nPMA==0 ); } if( rc==SQLITE_OK ){ - i64 iWriteOff = pSorter->iWriteOff; - void *aMalloc = 0; /* Array used to hold a single record */ - int nMalloc = 0; /* Allocated size of aMalloc[] in bytes */ + i64 iOff = pSorter->iWriteOff; + SorterRecord *p; + SorterRecord *pNext = 0; + static const char eightZeros[8] = { 0, 0, 0, 0, 0, 0, 0, 0 }; pSorter->nPMA++; - for( - rc = vdbeSorterWriteVarint(pSorter->pTemp1, pSorter->nBtree, &iWriteOff); - rc==SQLITE_OK && res==0; - rc = sqlite3BtreeNext(pCsr->pCursor, &res) - ){ - i64 nKey; /* Size of this key in bytes */ - - /* Write the size of the record in bytes to the output file */ - (void)sqlite3BtreeKeySize(pCsr->pCursor, &nKey); - rc = vdbeSorterWriteVarint(pSorter->pTemp1, nKey, &iWriteOff); - - /* Make sure the aMalloc[] buffer is large enough for the record */ - if( rc==SQLITE_OK && nKey>nMalloc ){ - aMalloc = sqlite3DbReallocOrFree(db, aMalloc, nKey); - if( !aMalloc ){ - rc = SQLITE_NOMEM; - }else{ - nMalloc = nKey; - } - } - - /* Write the record itself to the output file */ - if( rc==SQLITE_OK ){ - /* sqlite3BtreeKey() cannot fail because sorter btrees held in memory */ - rc = sqlite3BtreeKey(pCsr->pCursor, 0, nKey, aMalloc); - if( ALWAYS(rc==SQLITE_OK) ){ - rc = sqlite3OsWrite(pSorter->pTemp1, aMalloc, nKey, iWriteOff); - iWriteOff += nKey; - } - } - - if( rc!=SQLITE_OK ) break; + rc = vdbeSorterWriteVarint(pSorter->pTemp1, pSorter->nInMemory, &iOff); + for(p=pSorter->pRecord; rc==SQLITE_OK && p; p=pNext){ + pNext = p->pNext; + rc = vdbeSorterWriteVarint(pSorter->pTemp1, p->nVal, &iOff); + + if( rc==SQLITE_OK ){ + rc = sqlite3OsWrite(pSorter->pTemp1, p->pVal, p->nVal, iOff); + iOff += p->nVal; + } + + sqlite3DbFree(db, p); } /* This assert verifies that unless an error has occurred, the size of ** the PMA on disk is the same as the expected size stored in - ** pSorter->nBtree. */ - assert( rc!=SQLITE_OK || pSorter->nBtree==( - iWriteOff-pSorter->iWriteOff-sqlite3VarintLen(pSorter->nBtree) + ** pSorter->nInMemory. */ + assert( rc!=SQLITE_OK || pSorter->nInMemory==( + iOff-pSorter->iWriteOff-sqlite3VarintLen(pSorter->nInMemory) )); - pSorter->iWriteOff = iWriteOff; - sqlite3DbFree(db, aMalloc); + pSorter->iWriteOff = iOff; + if( rc==SQLITE_OK ){ + /* Terminate each file with 8 extra bytes so that from any offset + ** in the file we can always read 9 bytes without a SHORT_READ error */ + rc = sqlite3OsWrite(pSorter->pTemp1, eightZeros, 8, iOff); + } + pSorter->pRecord = p; } - pSorter->nBtree = 0; return rc; } /* -** This function is called on a sorter cursor by the VDBE before each row -** is inserted into VdbeCursor.pCsr. Argument nKey is the size of the key, in -** bytes, about to be inserted. -** -** If it is determined that the temporary b-tree accessed via VdbeCursor.pCsr -** is large enough, its contents are written to a sorted PMA on disk and the -** tree emptied. This prevents the b-tree (which must be small enough to -** fit entirely in the cache in order to support efficient inserts) from -** growing too large. -** -** An SQLite error code is returned if an error occurs. Otherwise, SQLITE_OK. +** Add a record to the sorter. */ -int sqlite3VdbeSorterWrite(sqlite3 *db, VdbeCursor *pCsr, int nKey){ - int rc = SQLITE_OK; /* Return code */ +int sqlite3VdbeSorterWrite( + sqlite3 *db, /* Database handle */ + VdbeCursor *pCsr, /* Sorter cursor */ + Mem *pVal /* Memory cell containing record */ +){ VdbeSorter *pSorter = pCsr->pSorter; - if( pSorter ){ - Pager *pPager = sqlite3BtreePager(pCsr->pBt); - int nPage; /* Current size of temporary file in pages */ - - /* Sorters never spill to disk */ - assert( sqlite3PagerFile(pPager)->pMethods==0 ); - - /* Determine how many pages the temporary b-tree has grown to */ - 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 && sqlite3PagerUnderStress(pPager) ){ - pSorter->nWorking = nPage-5; - if( pSorter->nWorkingnWorking = SORTER_MIN_WORKING; - } - } - - /* 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->nWorking ){ - BtCursor *p = pCsr->pCursor;/* Cursor structure to close and reopen */ - int iRoot; /* Root page of new tree */ - - /* Copy the current contents of the b-tree into a PMA in sorted order. - ** Close the currently open b-tree cursor. */ - rc = vdbeSorterBtreeToPMA(db, pCsr); - sqlite3BtreeCloseCursor(p); - - if( rc==SQLITE_OK ){ - rc = sqlite3BtreeDropTable(pCsr->pBt, 2, 0); -#ifdef SQLITE_DEBUG - sqlite3PagerPagecount(pPager, &nPage); - assert( rc!=SQLITE_OK || nPage==1 ); -#endif - } - if( rc==SQLITE_OK ){ - rc = sqlite3BtreeCreateTable(pCsr->pBt, &iRoot, BTREE_BLOBKEY); - } - if( rc==SQLITE_OK ){ - assert( iRoot==2 ); - rc = sqlite3BtreeCursor(pCsr->pBt, iRoot, 1, pCsr->pKeyInfo, p); - } - } - - pSorter->nBtree += sqlite3VarintLen(nKey) + nKey; - } + int rc = SQLITE_OK; /* Return Code */ + SorterRecord *pNew; /* New list element */ + + assert( pSorter ); + pSorter->nInMemory += sqlite3VarintLen(pVal->n) + pVal->n; + + pNew = (SorterRecord *)sqlite3DbMallocRaw(db, pVal->n + sizeof(SorterRecord)); + if( pNew==0 ){ + rc = SQLITE_NOMEM; + }else{ + pNew->pVal = (void *)&pNew[1]; + memcpy(pNew->pVal, pVal->z, pVal->n); + pNew->nVal = pVal->n; + pNew->pNext = pSorter->pRecord; + pSorter->pRecord = pNew; + } + + /* See if the contents of the sorter should now be written out. They + ** are written out when either of the following are true: + ** + ** * The total memory allocated for the in-memory list is greater + ** than (page-size * cache-size), or + ** + ** * The total memory allocated for the in-memory list is greater + ** than (page-size * 10) and sqlite3HeapNearlyFull() returns true. + */ + if( rc==SQLITE_OK && pSorter->mxPmaSize>0 && ( + (pSorter->nInMemory>pSorter->mxPmaSize) + || (pSorter->nInMemory>pSorter->mnPmaSize && sqlite3HeapNearlyFull()) + )){ + rc = vdbeSorterListToPMA(db, pCsr); + pSorter->nInMemory = 0; + } + return rc; } /* ** Helper function for sqlite3VdbeSorterRewind(). @@ -541,16 +684,16 @@ int rc = SQLITE_OK; /* Return code */ int i; /* Used to iterator through aIter[] */ i64 nByte = 0; /* Total bytes in all opened PMAs */ /* Initialize the iterators. */ - for(i=0; rc==SQLITE_OK && iaIter[i]; rc = vdbeSorterIterInit(db, pSorter, pSorter->iReadOff, pIter, &nByte); pSorter->iReadOff = pIter->iEof; - assert( pSorter->iReadOff<=pSorter->iWriteOff || rc!=SQLITE_OK ); - if( pSorter->iReadOff>=pSorter->iWriteOff ) break; + assert( rc!=SQLITE_OK || pSorter->iReadOff<=pSorter->iWriteOff ); + if( rc!=SQLITE_OK || pSorter->iReadOff>=pSorter->iWriteOff ) break; } /* Initialize the aTree[] array. */ for(i=pSorter->nTree-1; rc==SQLITE_OK && i>0; i--){ rc = vdbeSorterDoCompare(pCsr, i); @@ -573,18 +716,22 @@ int nByte; /* Bytes of space required for aIter/aTree */ int N = 2; /* Power of 2 >= nIter */ assert( pSorter ); - /* Write the current b-tree to a PMA. Close the b-tree cursor. */ - rc = vdbeSorterBtreeToPMA(db, pCsr); - sqlite3BtreeCloseCursor(pCsr->pCursor); - if( rc!=SQLITE_OK ) return rc; + /* If no data has been written to disk, then do not do so now. Instead, + ** sort the VdbeSorter.pRecord list. The vdbe layer will read data directly + ** from the in-memory list. */ if( pSorter->nPMA==0 ){ - *pbEof = 1; - return SQLITE_OK; + *pbEof = !pSorter->pRecord; + assert( pSorter->aTree==0 ); + return vdbeSorterSort(db, pCsr); } + + /* Write the current b-tree to a PMA. Close the b-tree cursor. */ + rc = vdbeSorterListToPMA(db, pCsr); + if( rc!=SQLITE_OK ) return rc; /* Allocate space for aIter[] and aTree[]. */ nIter = pSorter->nPMA; if( nIter>SORTER_MAX_MERGE_COUNT ) nIter = SORTER_MAX_MERGE_COUNT; assert( nIter>0 ); @@ -668,44 +815,93 @@ /* ** 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, &pSorter->aIter[iPrev]); - for(i=(pSorter->nTree+iPrev)/2; rc==SQLITE_OK && i>0; i=i/2){ - rc = vdbeSorterDoCompare(pCsr, i); - } + if( pSorter->aTree ){ + int iPrev = pSorter->aTree[1];/* Index of iterator to advance */ + int i; /* Index of aTree[] to recalculate */ + + rc = vdbeSorterIterNext(db, &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]].pFile==0); + *pbEof = (pSorter->aIter[pSorter->aTree[1]].pFile==0); + }else{ + SorterRecord *pFree = pSorter->pRecord; + pSorter->pRecord = pFree->pNext; + pFree->pNext = 0; + vdbeSorterRecordFree(db, pFree); + *pbEof = !pSorter->pRecord; + rc = SQLITE_OK; + } return rc; } + +/* +** Return a pointer to a buffer owned by the sorter that contains the +** current key. +*/ +static void *vdbeSorterRowkey( + VdbeSorter *pSorter, /* Sorter object */ + int *pnKey /* OUT: Size of current key in bytes */ +){ + void *pKey; + if( pSorter->aTree ){ + VdbeSorterIter *pIter; + pIter = &pSorter->aIter[ pSorter->aTree[1] ]; + *pnKey = pIter->nKey; + pKey = pIter->aKey; + }else{ + *pnKey = pSorter->pRecord->nVal; + pKey = pSorter->pRecord->pVal; + } + return pKey; +} /* ** Copy the current sorter key into the memory cell pOut. */ int sqlite3VdbeSorterRowkey(VdbeCursor *pCsr, Mem *pOut){ VdbeSorter *pSorter = pCsr->pSorter; - VdbeSorterIter *pIter; - - pIter = &pSorter->aIter[ pSorter->aTree[1] ]; - - /* Coverage testing note: As things are currently, this call will always - ** succeed. This is because the memory cell passed by the VDBE layer - ** happens to be the same one as was used to assemble the keys before they - ** were passed to the sorter - meaning it is always large enough for the - ** largest key. But this could change very easily, so we leave the call - ** to sqlite3VdbeMemGrow() in. */ - if( NEVER(sqlite3VdbeMemGrow(pOut, pIter->nKey, 0)) ){ + void *pKey; int nKey; /* Sorter key to copy into pOut */ + + pKey = vdbeSorterRowkey(pSorter, &nKey); + if( sqlite3VdbeMemGrow(pOut, nKey, 0) ){ return SQLITE_NOMEM; } - pOut->n = pIter->nKey; + pOut->n = nKey; MemSetTypeFlag(pOut, MEM_Blob); - memcpy(pOut->z, pIter->aKey, pIter->nKey); + memcpy(pOut->z, pKey, nKey); return SQLITE_OK; } + +/* +** Compare the key in memory cell pVal with the key that the sorter cursor +** passed as the first argument currently points to. For the purposes of +** the comparison, ignore the rowid field at the end of each record. +** +** If an error occurs, return an SQLite error code (i.e. SQLITE_NOMEM). +** Otherwise, set *pRes to a negative, zero or positive value if the +** key in pVal is smaller than, equal to or larger than the current sorter +** key. +*/ +int sqlite3VdbeSorterCompare( + VdbeCursor *pCsr, /* Sorter cursor */ + Mem *pVal, /* Value to compare to current sorter key */ + int *pRes /* OUT: Result of comparison */ +){ + int rc; + VdbeSorter *pSorter = pCsr->pSorter; + void *pKey; int nKey; /* Sorter key to compare pVal with */ + + pKey = vdbeSorterRowkey(pSorter, &nKey); + rc = vdbeSorterCompare(pCsr, 1, pVal->z, pVal->n, pKey, nKey, pRes); + assert( rc!=SQLITE_OK || pVal->db->mallocFailed || (*pRes)<=0 ); + return rc; +} #endif /* #ifndef SQLITE_OMIT_MERGE_SORT */ Index: test/distinct.test ================================================================== --- test/distinct.test +++ test/distinct.test @@ -43,11 +43,11 @@ proc do_temptables_test {tn sql temptables} { uplevel [list do_test $tn [subst -novar { set ret "" db eval "EXPLAIN [set sql]" { - if {$opcode == "OpenEphemeral"} { + if {$opcode == "OpenEphemeral" || $opcode == "SorterOpen"} { if {$p5 != "10" && $p5!="00"} { error "p5 = $p5" } if {$p5 == "10"} { lappend ret hash } else { lappend ret btree Index: test/index4.test ================================================================== --- test/index4.test +++ test/index4.test @@ -106,7 +106,21 @@ COMMIT; CREATE INDEX i1 ON t1(x); PRAGMA integrity_check } {ok} +do_execsql_test 2.1 { + BEGIN; + CREATE TABLE t2(x); + INSERT INTO t2 VALUES(14); + INSERT INTO t2 VALUES(35); + INSERT INTO t2 VALUES(15); + INSERT INTO t2 VALUES(35); + INSERT INTO t2 VALUES(16); + COMMIT; +} +do_catchsql_test 2.2 { + CREATE UNIQUE INDEX i3 ON t2(x); +} {1 {indexed columns are not unique}} + finish_test Index: test/misc3.test ================================================================== --- test/misc3.test +++ test/misc3.test @@ -268,11 +268,11 @@ c REAL DEFAULT 3.1415926 ); CREATE UNIQUE INDEX ex1i1 ON ex1(a); EXPLAIN REINDEX; }] - regexp { IsUnique \d+ \d+ \d+ \d+ } $x + regexp { SorterCompare \d+ \d+ \d+ } $x } {1} if {[regexp {16} [db one {PRAGMA encoding}]]} { do_test misc3-6.11-utf16 { set x [execsql { EXPLAIN SELECT a+123456789012, b*4.5678, c FROM ex1 ORDER BY +a, b DESC Index: test/pager1.test ================================================================== --- test/pager1.test +++ test/pager1.test @@ -2435,10 +2435,11 @@ sqlite3 db test.db execsql { BEGIN; INSERT INTO t1 VALUES(1, randomblob(10000)); } + file_control_chunksize_test db main 1024 file_control_sizehint_test db main 20971520; # 20MB execsql { PRAGMA cache_size = 10; INSERT INTO t1 VALUES(1, randomblob(10000)); INSERT INTO t1 VALUES(2, randomblob(10000)); Index: test/server1.test ================================================================== --- test/server1.test +++ test/server1.test @@ -27,11 +27,11 @@ } # The sample server implementation does not work right when memory # management is enabled. # -ifcapable memorymanage { +ifcapable (memorymanage||mutex_noop) { finish_test return } # Create some data to work with Index: test/thread001.test ================================================================== --- test/thread001.test +++ test/thread001.test @@ -40,11 +40,11 @@ do_test thread001.$tn.0 { db close sqlite3_enable_shared_cache $shared_cache sqlite3_enable_shared_cache $shared_cache } $shared_cache - sqlite3 db test.db -fullmutex 1 + sqlite3 db test.db -fullmutex 1 -key xyzzy set dbconfig "" if {$same_db} { set dbconfig [list set ::DB [sqlite3_connection_pointer db]] } @@ -75,11 +75,11 @@ set thread_program { #sqlthread parent {puts STARTING..} set needToClose 0 if {![info exists ::DB]} { - set ::DB [sqlthread open test.db] + set ::DB [sqlthread open test.db xyzzy] #sqlthread parent "puts \"OPEN $::DB\"" set needToClose 1 } for {set i 0} {$i < 100} {incr i} { Index: test/thread002.test ================================================================== --- test/thread002.test +++ test/thread002.test @@ -14,12 +14,14 @@ # # $Id: thread002.test,v 1.9 2009/03/26 14:48:07 danielk1977 Exp $ set testdir [file dirname $argv0] +set do_not_use_codec 1 source $testdir/tester.tcl if {[run_thread_tests]==0} { finish_test ; return } + db close set ::enable_shared_cache [sqlite3_enable_shared_cache 1] set ::NTHREAD 10 Index: test/thread003.test ================================================================== --- test/thread003.test +++ test/thread003.test @@ -78,11 +78,11 @@ puts "Starting thread003.2 (should run for ~$nSecond seconds)" do_test thread003.2 { foreach zFile {test.db test2.db} { set SCRIPT [format { set iEnd [expr {[clock_seconds] + %d}] - set ::DB [sqlthread open %s] + set ::DB [sqlthread open %s xyzzy] # Set the cache size to 15 pages per cache. 30 available globally. execsql { PRAGMA cache_size = 15 } while {[clock_seconds] < $iEnd} { @@ -115,11 +115,11 @@ do_test thread003.3 { foreach zFile {test.db test2.db} { set SCRIPT [format { set iStart [clock_seconds] set iEnd [expr {[clock_seconds] + %d}] - set ::DB [sqlthread open %s] + set ::DB [sqlthread open %s xyzzy] # Set the cache size to 15 pages per cache. 30 available globally. execsql { PRAGMA cache_size = 15 } while {[clock_seconds] < $iEnd} { @@ -154,11 +154,11 @@ unset -nocomplain finished(1) unset -nocomplain finished(2) do_test thread003.4 { thread_spawn finished(1) $thread_procs [format { set iEnd [expr {[clock_seconds] + %d}] - set ::DB [sqlthread open test.db] + set ::DB [sqlthread open test.db xyzzy] # Set the cache size to 15 pages per cache. 30 available globally. execsql { PRAGMA cache_size = 15 } while {[clock_seconds] < $iEnd} { Index: test/wal5.test ================================================================== --- test/wal5.test +++ test/wal5.test @@ -233,11 +233,11 @@ do_test 2.3.$tn.3 { sql2 { BEGIN; SELECT * FROM t1 } } {1 2} do_test 2.3.$tn.4 { sql1 { INSERT INTO t1 VALUES(3, 4) } } {} do_test 2.3.$tn.5 { sql1 { INSERT INTO t2 VALUES(3, 4) } } {} do_test 2.3.$tn.6 { file_page_counts } {1 7 1 7} do_test 2.3.$tn.7 { code1 { do_wal_checkpoint db -mode full } } {1 7 5} - do_test 2.3.$tn.8 { file_page_counts } {2 7 2 7} + do_test 2.3.$tn.8 { file_page_counts } {1 7 2 7} } # Check that checkpoints block on the correct locks. And respond correctly # if they cannot obtain those locks. There are three locks that a checkpoint # may block on (in the following order): @@ -341,5 +341,6 @@ } } finish_test + Index: tool/lemon.c ================================================================== --- tool/lemon.c +++ tool/lemon.c @@ -2520,17 +2520,19 @@ filebuf = (char *)malloc( filesize+1 ); if( filebuf==0 ){ ErrorMsg(ps.filename,0,"Can't allocate %d of memory to hold this file.", filesize+1); gp->errorcnt++; + fclose(fp); return; } if( fread(filebuf,1,filesize,fp)!=filesize ){ ErrorMsg(ps.filename,0,"Can't read in all %d bytes of this file.", filesize); free(filebuf); gp->errorcnt++; + fclose(fp); return; } fclose(fp); filebuf[filesize] = 0; Index: tool/spaceanal.tcl ================================================================== --- tool/spaceanal.tcl +++ tool/spaceanal.tcl @@ -39,12 +39,11 @@ # the tables and indices in the database being analyzed, adding a row for each # to an in-memory database (for which the schema is shown below). It then # queries the in-memory db to produce the space-analysis report. # sqlite3 mem :memory: -set tabledef\ -{CREATE TABLE space_used( +set tabledef {CREATE TABLE space_used( name clob, -- Name of a table or index in the database file tblname clob, -- Name of associated table is_index boolean, -- TRUE if it is an index, false for a table nentry int, -- Number of entries in the BTree leaf_entries int, -- Number of leaf entries @@ -291,20 +290,20 @@ } statline {Primary pages used} $leaf_pages statline {Overflow pages used} $ovfl_pages statline {Total pages used} $total_pages if {$int_unused>0} { - set int_unused_percent \ - [percent $int_unused [expr {$int_pages*$pageSize}] {of index space}] + set int_unused_percent [ + percent $int_unused [expr {$int_pages*$pageSize}] {of index space}] statline "Unused bytes on index pages" $int_unused $int_unused_percent } - statline "Unused bytes on primary pages" $leaf_unused \ - [percent $leaf_unused [expr {$leaf_pages*$pageSize}] {of primary space}] - statline "Unused bytes on overflow pages" $ovfl_unused \ - [percent $ovfl_unused [expr {$ovfl_pages*$pageSize}] {of overflow space}] - statline "Unused bytes on all pages" $total_unused \ - [percent $total_unused $storage {of all space}] + statline "Unused bytes on primary pages" $leaf_unused [ + percent $leaf_unused [expr {$leaf_pages*$pageSize}] {of primary space}] + statline "Unused bytes on overflow pages" $ovfl_unused [ + percent $ovfl_unused [expr {$ovfl_pages*$pageSize}] {of overflow space}] + statline "Unused bytes on all pages" $total_unused [ + percent $total_unused $storage {of all space}] return 1 } # Calculate the overhead in pages caused by auto-vacuum. # @@ -450,15 +449,13 @@ The number of bytes in a single page of the database file. Usually 1024. Number of pages in the whole file } -puts \ -" The number of $pageSize-byte pages that go into forming the complete +puts " The number of $pageSize-byte pages that go into forming the complete database" -puts \ -{ +puts { Pages that store data The number of pages that store data, either as primary B*Tree pages or as overflow pages. The number at the right is the data pages divided by the total number of pages in the file. Index: tool/tostr.awk ================================================================== --- tool/tostr.awk +++ tool/tostr.awk @@ -1,9 +1,8 @@ #!/usr/bin/awk # # Convert input text into a C string # { - gsub(/\\/,"\\\\"); gsub(/\"/,"\\\""); print "\"" $0 "\\n\""; }