Many hyperlinks are disabled.
Use anonymous login
to enable hyperlinks.
Overview
| Comment: | Improve the testability of the merge-sort logic. |
|---|---|
| Downloads: | Tarball | ZIP archive |
| Timelines: | family | ancestors | descendants | both | trunk |
| Files: | files | file ages | folders |
| SHA1: |
b5179baf87aa00ed5cecbdcaa65bee10 |
| User & Date: | drh 2011-09-04 01:11:46.977 |
Context
|
2011-09-04
| ||
| 01:27 | Fix a compiler warning about an unused parameter in the merge-sort code. (check-in: 6b657ae750 user: drh tags: trunk) | |
| 01:11 | Improve the testability of the merge-sort logic. (check-in: b5179baf87 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: 4c43e8b2d2 user: drh tags: trunk) | |
Changes
Changes to src/select.c.
| ︙ | ︙ | |||
896 897 898 899 900 901 902 |
pseudoTab = pParse->nTab++;
sqlite3VdbeAddOp3(v, OP_OpenPseudo, pseudoTab, regRow, nColumn);
regRowid = 0;
}else{
regRowid = sqlite3GetTempReg(pParse);
}
if( p->selFlags & SF_UseSorter ){
| | | 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 |
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 */
| < < < < < | | 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 |
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;
}
|
| ︙ | ︙ | |||
329 330 331 332 333 334 335 |
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 );
| | | 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 |
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++){
|
| ︙ | ︙ | |||
383 384 385 386 387 388 389 |
if( p1->pFile==0 ){
iRes = i2;
}else if( p2->pFile==0 ){
iRes = i1;
}else{
int res;
| > > | > > | > | 378 379 380 381 382 383 384 385 386 387 388 389 390 391 392 393 394 395 396 397 398 399 400 |
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;
}
}
|
| ︙ | ︙ | |||
602 603 604 605 606 607 608 609 610 611 612 613 614 615 |
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);
| > | 602 603 604 605 606 607 608 609 610 611 612 613 614 615 616 |
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);
|
| ︙ | ︙ | |||
625 626 627 628 629 630 631 632 633 634 635 636 637 638 |
** 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;
}
/*
| > > > > > | 626 627 628 629 630 631 632 633 634 635 636 637 638 639 640 641 642 643 644 |
** 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;
}
/*
|
| ︙ | ︙ |