Many hyperlinks are disabled.
Use anonymous login
to enable hyperlinks.
Overview
| Comment: | Improve the testability of the merge-sort logic. |
|---|---|
| Downloads: | Tarball | ZIP archive | SQL archive |
| Timelines: | family | ancestors | descendants | both | trunk |
| Files: | files | file ages | folders |
| SHA1: |
b5179baf87aa00ed5cecbdcaa65bee10 |
| User & Date: | drh 2011-09-04 01:11:46 |
Context
|
2011-09-04
| ||
| 01:27 | Fix a compiler warning about an unused parameter in the merge-sort code. check-in: 6b657ae7 user: drh tags: trunk | |
| 01:11 | Improve the testability of the merge-sort logic. check-in: b5179baf user: drh tags: trunk | |
|
2011-09-03
| ||
| 17:07 | Performance improvements to the external merge-sorter. Keep content on an in-memory linked lists rather than an ephemeral table prior to spilling to disk. Use the external merge-sorter to implement ORDER BY and GROUP BY in addition to CREATE INDEX. check-in: 4c43e8b2 user: drh tags: trunk | |
Changes
Changes to src/select.c.
896 897 898 899 900 901 902 903 904 905 906 907 908 909 910 |
pseudoTab = pParse->nTab++;
sqlite3VdbeAddOp3(v, OP_OpenPseudo, pseudoTab, regRow, nColumn);
regRowid = 0;
}else{
regRowid = sqlite3GetTempReg(pParse);
}
if( p->selFlags & SF_UseSorter ){
int regSortOut = sqlite3GetTempReg(pParse);
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);
|
| |
896 897 898 899 900 901 902 903 904 905 906 907 908 909 910 |
pseudoTab = pParse->nTab++;
sqlite3VdbeAddOp3(v, OP_OpenPseudo, pseudoTab, regRow, nColumn);
regRowid = 0;
}else{
regRowid = sqlite3GetTempReg(pParse);
}
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);
|
Changes to src/vdbesort.c.
235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 ... 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 ... 383 384 385 386 387 388 389 390 391 392 393 394 395 396 397 398 399 400 ... 602 603 604 605 606 607 608 609 610 611 612 613 614 615 ... 625 626 627 628 629 630 631 632 633 634 635 636 637 638 |
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)<nRead ){
nRead = iEof-iOff;
}
rc = sqlite3OsRead(pFile, aVarint, nRead, iOff);
if( rc==SQLITE_OK ){
*piOffset += getVarint(aVarint, (u64 *)piVal);
}
return rc;
}
................................................................................
pSorter->nSpace = nSpace;
}
if( pKey2 ){
/* This call cannot fail. As the memory is already allocated. */
r2 = sqlite3VdbeRecordUnpack(pKeyInfo, nKey2, pKey2, aSpace, nSpace);
assert( r2 && (r2->flags & UNPACKED_NEED_FREE)==0 );
assert( r2==aSpace );
}else{
r2 = (UnpackedRecord *)aSpace;
assert( !bOmitRowid );
}
if( bOmitRowid ){
for(i=0; i<r2->nField-1; i++){
................................................................................
if( p1->pFile==0 ){
iRes = i2;
}else if( p2->pFile==0 ){
iRes = i1;
}else{
int res;
int rc = vdbeSorterCompare(
pCsr, 0, p1->aKey, p1->nKey, p2->aKey, p2->nKey, &res
);
if( rc!=SQLITE_OK ) return rc;
if( res<=0 ){
iRes = i1;
}else{
iRes = i2;
}
}
................................................................................
assert( pSorter->nPMA==0 );
}
if( rc==SQLITE_OK ){
i64 iOff = pSorter->iWriteOff;
SorterRecord *p;
SorterRecord *pNext = 0;
pSorter->nPMA++;
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);
................................................................................
** the PMA on disk is the same as the expected size stored in
** pSorter->nInMemory. */
assert( rc!=SQLITE_OK || pSorter->nInMemory==(
iOff-pSorter->iWriteOff-sqlite3VarintLen(pSorter->nInMemory)
));
pSorter->iWriteOff = iOff;
pSorter->pRecord = p;
}
return rc;
}
/*
|
< < < < < | | > > | > > | > > > > > > > |
235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 ... 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 ... 378 379 380 381 382 383 384 385 386 387 388 389 390 391 392 393 394 395 396 397 398 399 400 ... 602 603 604 605 606 607 608 609 610 611 612 613 614 615 616 ... 626 627 628 629 630 631 632 633 634 635 636 637 638 639 640 641 642 643 644 |
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 rc; /* Return code */
assert( iEof>iOff );
rc = sqlite3OsRead(pFile, aVarint, 9, iOff);
if( rc==SQLITE_OK ){
*piOffset += getVarint(aVarint, (u64 *)piVal);
}
return rc;
}
................................................................................
pSorter->nSpace = nSpace;
}
if( pKey2 ){
/* This call cannot fail. As the memory is already allocated. */
r2 = sqlite3VdbeRecordUnpack(pKeyInfo, nKey2, pKey2, aSpace, nSpace);
assert( r2 && (r2->flags & UNPACKED_NEED_FREE)==0 );
assert( r2==(UnpackedRecord*)aSpace );
}else{
r2 = (UnpackedRecord *)aSpace;
assert( !bOmitRowid );
}
if( bOmitRowid ){
for(i=0; i<r2->nField-1; i++){
................................................................................
if( p1->pFile==0 ){
iRes = i2;
}else if( p2->pFile==0 ){
iRes = i1;
}else{
int res;
int rc;
assert( pCsr->pSorter->aSpace!=0 ); /* allocated in vdbeSorterMerge() */
rc = vdbeSorterCompare(
pCsr, 0, p1->aKey, p1->nKey, p2->aKey, p2->nKey, &res
);
/* The vdbeSorterCompare() call cannot fail since pCsr->pSorter->aSpace
** has already been allocated. */
assert( rc==SQLITE_OK );
if( res<=0 ){
iRes = i1;
}else{
iRes = i2;
}
}
................................................................................
assert( pSorter->nPMA==0 );
}
if( rc==SQLITE_OK ){
i64 iOff = pSorter->iWriteOff;
SorterRecord *p;
SorterRecord *pNext = 0;
static const char eightZeros[8] = { 0, 0, 0, 0, 0, 0, 0, 0 };
pSorter->nPMA++;
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);
................................................................................
** the PMA on disk is the same as the expected size stored in
** pSorter->nInMemory. */
assert( rc!=SQLITE_OK || pSorter->nInMemory==(
iOff-pSorter->iWriteOff-sqlite3VarintLen(pSorter->nInMemory)
));
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;
}
return rc;
}
/*
|