Many hyperlinks are disabled.
Use anonymous login
to enable hyperlinks.
| Comment: | Remove an unused parameter from a function in vdbesort.c. Fix some comments and other details in the same file. |
|---|---|
| Downloads: | Tarball | ZIP archive | SQL archive |
| Timelines: | family | ancestors | descendants | both | experimental |
| Files: | files | file ages | folders |
| SHA1: |
1a8498d8037a1b93e56951bbdbb76291 |
| User & Date: | dan 2011-08-12 16:11:43 |
|
2011-08-12
| ||
| 16:30 | Merge latest trunk changes into experimental branch. (check-in: 7e515055 user: dan tags: experimental) | |
| 16:11 | Remove an unused parameter from a function in vdbesort.c. Fix some comments and other details in the same file. (check-in: 1a8498d8 user: dan tags: experimental) | |
| 15:02 | Add the SQLITE_OMIT_MERGE_SORT pre-processor directive. To omit the code in vdbesort.c. (check-in: 4ced2394 user: dan tags: experimental) | |
Changes to src/vdbe.c.
4089 4089 assert( pC->isIndex || pOp->opcode==OP_RowData ); 4090 4090 assert( pC!=0 ); 4091 4091 assert( pC->nullRow==0 ); 4092 4092 assert( pC->pseudoTableReg==0 ); 4093 4093 4094 4094 if( isSorter(pC) ){ 4095 4095 assert( pOp->opcode==OP_RowKey ); 4096 - rc = sqlite3VdbeSorterRowkey(db, pC, pOut); 4096 + rc = sqlite3VdbeSorterRowkey(pC, pOut); 4097 4097 break; 4098 4098 } 4099 4099 4100 4100 assert( pC->pCursor!=0 ); 4101 4101 pCrsr = pC->pCursor; 4102 4102 assert( sqlite3BtreeCursorIsValid(pCrsr) ); 4103 4103
Changes to src/vdbeInt.h.
392 392 int sqlite3VdbeFrameRestore(VdbeFrame *); 393 393 void sqlite3VdbeMemStoreType(Mem *pMem); 394 394 395 395 #ifdef SQLITE_OMIT_MERGE_SORT 396 396 # define sqlite3VdbeSorterInit(Y,Z) SQLITE_OK 397 397 # define sqlite3VdbeSorterWrite(X,Y,Z) SQLITE_OK 398 398 # define sqlite3VdbeSorterClose(Y,Z) 399 -# define sqlite3VdbeSorterRowkey(X,Y,Z) SQLITE_OK 399 +# define sqlite3VdbeSorterRowkey(Y,Z) SQLITE_OK 400 400 # define sqlite3VdbeSorterRewind(X,Y,Z) SQLITE_OK 401 401 # define sqlite3VdbeSorterNext(X,Y,Z) SQLITE_OK 402 402 #else 403 403 int sqlite3VdbeSorterInit(sqlite3 *, VdbeCursor *); 404 404 int sqlite3VdbeSorterWrite(sqlite3 *, VdbeCursor *, int); 405 405 void sqlite3VdbeSorterClose(sqlite3 *, VdbeCursor *); 406 -int sqlite3VdbeSorterRowkey(sqlite3 *, VdbeCursor *, Mem *); 406 +int sqlite3VdbeSorterRowkey(VdbeCursor *, Mem *); 407 407 int sqlite3VdbeSorterRewind(sqlite3 *, VdbeCursor *, int *); 408 408 int sqlite3VdbeSorterNext(sqlite3 *, VdbeCursor *, int *); 409 409 #endif 410 410 411 411 #if !defined(SQLITE_OMIT_SHARED_CACHE) && SQLITE_THREADSAFE>0 412 412 void sqlite3VdbeEnter(Vdbe*); 413 413 void sqlite3VdbeLeave(Vdbe*);
Changes to src/vdbesort.c.
19 19 #include "vdbeInt.h" 20 20 21 21 #ifndef SQLITE_OMIT_MERGE_SORT 22 22 23 23 typedef struct VdbeSorterIter VdbeSorterIter; 24 24 25 25 /* 26 +** NOTES ON DATA STRUCTURE USED FOR N-WAY MERGES: 27 +** 26 28 ** As keys are added to the sorter, they are written to disk in a series 27 29 ** of sorted packed-memory-arrays (PMAs). The size of each PMA is roughly 28 30 ** the same as the cache-size allowed for temporary databases. In order 29 31 ** to allow the caller to extract keys from the sorter in sorted order, 30 32 ** all PMAs currently stored on disk must be merged together. This comment 31 33 ** describes the data structure used to do so. The structure supports 32 34 ** merging any number of arrays in a single pass with no redundant comparison ................................................................................ 112 114 int nAlloc; /* Bytes of space at aAlloc */ 113 115 u8 *aAlloc; /* Allocated space */ 114 116 int nKey; /* Number of bytes in key */ 115 117 u8 *aKey; /* Pointer to current key */ 116 118 }; 117 119 118 120 /* Minimum allowable value for the VdbeSorter.nWorking variable */ 119 -#define SORTER_MIN_SEGMENT_SIZE 10 121 +#define SORTER_MIN_WORKING 10 120 122 121 123 /* Maximum number of segments to merge in a single pass. */ 122 124 #define SORTER_MAX_MERGE_COUNT 16 123 125 124 126 /* 125 127 ** Free all memory belonging to the VdbeSorterIter object passed as the second 126 128 ** argument. All structure fields are set to zero before returning. ................................................................................ 127 129 */ 128 130 static void vdbeSorterIterZero(sqlite3 *db, VdbeSorterIter *pIter){ 129 131 sqlite3DbFree(db, pIter->aAlloc); 130 132 memset(pIter, 0, sizeof(VdbeSorterIter)); 131 133 } 132 134 133 135 /* 134 -** Advance iterator pIter to the next key in its PMA. 136 +** Advance iterator pIter to the next key in its PMA. Return SQLITE_OK if 137 +** no error occurs, or an SQLite error code if one does. 135 138 */ 136 139 static int vdbeSorterIterNext( 137 140 sqlite3 *db, /* Database handle (for sqlite3DbMalloc() ) */ 138 141 VdbeSorterIter *pIter /* Iterator to advance */ 139 142 ){ 140 - int rc; 141 - int nRead; 142 - int nRec; 143 - int iOff; 143 + int rc; /* Return Code */ 144 + int nRead; /* Number of bytes read */ 145 + int nRec; /* Size of record in bytes */ 146 + int iOff; /* Size of serialized size varint in bytes */ 144 147 145 148 nRead = pIter->iEof - pIter->iReadOff; 146 149 if( nRead>5 ) nRead = 5; 147 150 if( nRead<=0 ){ 151 + /* This is an EOF condition */ 148 152 vdbeSorterIterZero(db, pIter); 149 153 return SQLITE_OK; 150 154 } 151 155 152 156 rc = sqlite3OsRead(pIter->pFile, pIter->aAlloc, nRead, pIter->iReadOff); 153 157 iOff = getVarint32(pIter->aAlloc, nRec); 154 158 155 159 if( rc==SQLITE_OK && (iOff+nRec)>nRead ){ 156 - int nRead2; 160 + int nRead2; /* Number of extra bytes to read */ 157 161 if( (iOff+nRec)>pIter->nAlloc ){ 158 162 int nNew = pIter->nAlloc*2; 159 163 while( (iOff+nRec)>nNew ) nNew = nNew*2; 160 164 pIter->aAlloc = sqlite3DbReallocOrFree(db, pIter->aAlloc, nNew); 161 165 if( !pIter->aAlloc ) return SQLITE_NOMEM; 162 166 pIter->nAlloc = nNew; 163 167 } ................................................................................ 165 169 nRead2 = iOff + nRec - nRead; 166 170 rc = sqlite3OsRead( 167 171 pIter->pFile, &pIter->aAlloc[nRead], nRead2, pIter->iReadOff+nRead 168 172 ); 169 173 } 170 174 171 175 assert( nRec>0 || rc!=SQLITE_OK ); 172 - 173 176 pIter->iReadOff += iOff+nRec; 174 177 pIter->nKey = nRec; 175 178 pIter->aKey = &pIter->aAlloc[iOff]; 176 179 return rc; 177 180 } 178 181 179 182 /* ................................................................................ 181 184 ** SQLITE_OK if successful, or an SQLite error code if some error occurs. 182 185 ** 183 186 ** The value of *piOffset when this function is called is used as the byte 184 187 ** offset in file pFile to write to. Before returning, *piOffset is 185 188 ** incremented by the number of bytes written. 186 189 */ 187 190 static int vdbeSorterWriteVarint( 188 - sqlite3_file *pFile, 189 - i64 iVal, 190 - i64 *piOffset 191 + sqlite3_file *pFile, /* File to write to */ 192 + i64 iVal, /* Value to write as a varint */ 193 + i64 *piOffset /* IN/OUT: Write offset in file pFile */ 191 194 ){ 192 195 u8 aVarint[9]; /* Buffer large enough for a varint */ 193 196 int nVarint; /* Number of used bytes in varint */ 194 197 int rc; /* Result of write() call */ 195 198 196 199 nVarint = sqlite3PutVarint(aVarint, iVal); 197 200 rc = sqlite3OsWrite(pFile, aVarint, nVarint, *piOffset); ................................................................................ 208 211 ** byte offset in file pFile from whence to read the varint. If successful 209 212 ** (i.e. if no IO error occurs), then *piOffset is set to the offset of 210 213 ** the first byte past the end of the varint before returning. *piVal is 211 214 ** set to the integer value read. If an error occurs, the final values of 212 215 ** both *piOffset and *piVal are undefined. 213 216 */ 214 217 static int vdbeSorterReadVarint( 215 - sqlite3_file *pFile, 218 + sqlite3_file *pFile, /* File to read from */ 216 219 i64 iEof, /* Total number of bytes in file */ 217 - i64 *piOffset, /* IN/OUT: Read offset */ 220 + i64 *piOffset, /* IN/OUT: Read offset in pFile */ 218 221 i64 *piVal /* OUT: Value read from file */ 219 222 ){ 220 223 u8 aVarint[9]; /* Buffer large enough for a varint */ 221 224 i64 iOff = *piOffset; /* Offset in file to read from */ 222 225 int nRead = 9; /* Number of bytes to read from file */ 223 226 int rc; /* Return code */ 224 227 ................................................................................ 245 248 sqlite3 *db, /* Database handle */ 246 249 VdbeSorter *pSorter, /* Sorter object */ 247 250 i64 iStart, /* Start offset in pFile */ 248 251 VdbeSorterIter *pIter, /* Iterator to populate */ 249 252 i64 *pnByte /* IN/OUT: Increment this value by PMA size */ 250 253 ){ 251 254 int rc; 252 - i64 iEof = pSorter->iWriteOff; 253 255 254 - assert( iEof>iStart ); 256 + assert( pSorter->iWriteOff>iStart ); 255 257 assert( pIter->aAlloc==0 ); 256 258 pIter->pFile = pSorter->pTemp1; 257 259 pIter->iReadOff = iStart; 258 260 pIter->nAlloc = 128; 259 261 pIter->aAlloc = (u8 *)sqlite3DbMallocRaw(db, pIter->nAlloc); 260 262 if( !pIter->aAlloc ){ 261 263 rc = SQLITE_NOMEM; 262 264 }else{ 263 - i64 nByte; 265 + i64 iEof = pSorter->iWriteOff; /* EOF of file pSorter->pTemp1 */ 266 + i64 nByte; /* Total size of PMA in bytes */ 264 267 rc = vdbeSorterReadVarint(pSorter->pTemp1, iEof, &pIter->iReadOff, &nByte); 265 268 *pnByte += nByte; 266 269 pIter->iEof = pIter->iReadOff + nByte; 267 270 } 268 271 if( rc==SQLITE_OK ){ 269 272 rc = vdbeSorterIterNext(db, pIter); 270 273 } ................................................................................ 322 325 return SQLITE_OK; 323 326 } 324 327 325 328 /* 326 329 ** Initialize the temporary index cursor just opened as a sorter cursor. 327 330 */ 328 331 int sqlite3VdbeSorterInit(sqlite3 *db, VdbeCursor *pCsr){ 329 - VdbeSorter *pSorter; /* Allocated sorter object */ 330 - 331 - /* Cursor must be a temp cursor and not open on an intkey table */ 332 332 assert( pCsr->pKeyInfo && pCsr->pBt ); 333 - 334 - pSorter = sqlite3DbMallocZero(db, sizeof(VdbeSorter)); 335 - if( !pSorter ) return SQLITE_NOMEM; 336 - pCsr->pSorter = pSorter; 337 - return SQLITE_OK; 333 + pCsr->pSorter = sqlite3DbMallocZero(db, sizeof(VdbeSorter)); 334 + return (pCsr->pSorter ? SQLITE_NOMEM : SQLITE_OK); 338 335 } 339 336 340 337 /* 341 338 ** Free any cursor components allocated by sqlite3VdbeSorterXXX routines. 342 339 */ 343 340 void sqlite3VdbeSorterClose(sqlite3 *db, VdbeCursor *pCsr){ 344 341 VdbeSorter *pSorter = pCsr->pSorter; ................................................................................ 372 369 ); 373 370 } 374 371 375 372 376 373 /* 377 374 ** Write the current contents of the b-tree to a PMA. Return SQLITE_OK 378 375 ** if successful, or an SQLite error code otherwise. 376 +** 377 +** The format of a PMA is: 378 +** 379 +** * A varint. This varint contains the total number of bytes of content 380 +** in the PMA (not including the varint itself). 381 +** 382 +** * One or more records packed end-to-end in order of ascending keys. 383 +** Each record consists of a varint followed by a blob of data (the 384 +** key). The varint is the number of bytes in the blob of data. 379 385 */ 380 386 static int vdbeSorterBtreeToPMA(sqlite3 *db, VdbeCursor *pCsr){ 381 387 int rc = SQLITE_OK; /* Return code */ 382 388 VdbeSorter *pSorter = pCsr->pSorter; 383 - i64 iWriteOff = pSorter->iWriteOff; 384 389 int res = 0; 385 - void *aMalloc = 0; 386 - int nMalloc = 0; 387 390 388 391 rc = sqlite3BtreeFirst(pCsr->pCursor, &res); 389 392 if( rc!=SQLITE_OK || res ) return rc; 393 + assert( pSorter->nBtree>0 ); 390 394 391 395 /* If the first temporary PMA file has not been opened, open it now. */ 392 396 if( pSorter->pTemp1==0 ){ 393 397 rc = vdbeSorterOpenTempFile(db, &pSorter->pTemp1); 394 398 assert( rc!=SQLITE_OK || pSorter->pTemp1 ); 395 399 assert( pSorter->iWriteOff==0 ); 396 400 assert( pSorter->nPMA==0 ); 397 401 } 398 402 399 403 if( rc==SQLITE_OK ){ 404 + i64 iWriteOff = pSorter->iWriteOff; 405 + void *aMalloc = 0; /* Array used to hold a single record */ 406 + int nMalloc = 0; /* Allocated size of aMalloc[] in bytes */ 400 407 401 408 pSorter->nPMA++; 402 - 403 - /* Write a varint containg the size of the PMA in bytes into the file. */ 404 - assert( pSorter->nBtree>0 ); 405 - 406 409 for( 407 410 rc = vdbeSorterWriteVarint(pSorter->pTemp1, pSorter->nBtree, &iWriteOff); 408 411 rc==SQLITE_OK && res==0; 409 412 rc = sqlite3BtreeNext(pCsr->pCursor, &res) 410 413 ){ 411 414 i64 nKey; /* Size of this key in bytes */ 412 415 ................................................................................ 432 435 iWriteOff += nKey; 433 436 } 434 437 } 435 438 436 439 if( rc!=SQLITE_OK ) break; 437 440 } 438 441 442 + /* This assert verifies that unless an error has occurred, the size of 443 + ** the PMA on disk is the same as the expected size stored in 444 + ** pSorter->nBtree. */ 439 445 assert( rc!=SQLITE_OK || pSorter->nBtree==( 440 446 iWriteOff-pSorter->iWriteOff-sqlite3VarintLen(pSorter->nBtree) 441 447 )); 448 + 442 449 pSorter->iWriteOff = iWriteOff; 443 450 sqlite3DbFree(db, aMalloc); 444 451 } 445 452 446 453 pSorter->nBtree = 0; 447 454 return rc; 448 455 } 449 456 450 457 /* 451 -** This function is called on a sorter cursor before each row is inserted. 452 -** If the current b-tree being constructed is already considered "full", 453 -** a new tree is started. 458 +** This function is called on a sorter cursor by the VDBE before each row 459 +** is inserted into VdbeCursor.pCsr. Argument nKey is the size of the key, in 460 +** bytes, about to be inserted. 461 +** 462 +** If it is determined that the temporary b-tree accessed via VdbeCursor.pCsr 463 +** is large enough, its contents are written to a sorted PMA on disk and the 464 +** tree emptied. This prevents the b-tree (which must be small enough to 465 +** fit entirely in the cache in order to support efficient inserts) from 466 +** growing too large. 467 +** 468 +** An SQLite error code is returned if an error occurs. Otherwise, SQLITE_OK. 454 469 */ 455 470 int sqlite3VdbeSorterWrite(sqlite3 *db, VdbeCursor *pCsr, int nKey){ 456 471 int rc = SQLITE_OK; /* Return code */ 457 472 VdbeSorter *pSorter = pCsr->pSorter; 458 473 if( pSorter ){ 459 474 Pager *pPager = sqlite3BtreePager(pCsr->pBt); 460 475 int nPage; /* Current size of temporary file in pages */ 461 476 477 + /* Determine how many pages the temporary b-tree has grown to */ 462 478 sqlite3PagerPagecount(pPager, &nPage); 463 479 464 480 /* If pSorter->nWorking is still zero, but the temporary file has been 465 481 ** created in the file-system, then the most recent insert into the 466 482 ** current b-tree segment probably caused the cache to overflow (it is 467 483 ** also possible that sqlite3_release_memory() was called). So set the 468 484 ** size of the working set to a little less than the current size of the 469 485 ** file in pages. */ 470 486 if( pSorter->nWorking==0 && sqlite3PagerFile(pPager)->pMethods ){ 471 487 pSorter->nWorking = nPage-5; 472 - if( pSorter->nWorking<SORTER_MIN_SEGMENT_SIZE ){ 473 - pSorter->nWorking = SORTER_MIN_SEGMENT_SIZE; 488 + if( pSorter->nWorking<SORTER_MIN_WORKING ){ 489 + pSorter->nWorking = SORTER_MIN_WORKING; 474 490 } 475 491 } 476 492 477 493 /* If the number of pages used by the current b-tree segment is greater 478 494 ** than the size of the working set (VdbeSorter.nWorking), start a new 479 495 ** segment b-tree. */ 480 496 if( pSorter->nWorking && nPage>=pSorter->nWorking ){ ................................................................................ 660 676 *pbEof = (pSorter->aIter[pSorter->aTree[1]].pFile==0); 661 677 return rc; 662 678 } 663 679 664 680 /* 665 681 ** Copy the current sorter key into the memory cell pOut. 666 682 */ 667 -int sqlite3VdbeSorterRowkey(sqlite3 *db, VdbeCursor *pCsr, Mem *pOut){ 683 +int sqlite3VdbeSorterRowkey(VdbeCursor *pCsr, Mem *pOut){ 668 684 VdbeSorter *pSorter = pCsr->pSorter; 669 685 VdbeSorterIter *pIter; 670 686 671 687 pIter = &pSorter->aIter[ pSorter->aTree[1] ]; 672 688 673 689 /* Coverage testing note: As things are currently, this call will always 674 690 ** succeed. This is because the memory cell passed by the VDBE layer