Many hyperlinks are disabled.
Use anonymous login
to enable hyperlinks.
Overview
Comment: | Fix a problem in the code added by [707ea170b3] causing vdbesort.c to sort unstably. |
---|---|
Downloads: | Tarball | ZIP archive |
Timelines: | family | ancestors | descendants | both | orderby-planning |
Files: | files | file ages | folders |
SHA1: |
d3e640afe611b6ae0b7f2cff5b00900d |
User & Date: | dan 2014-03-25 17:07:48.821 |
Context
2014-03-25
| ||
18:29 | Merge enhancements and fixes from trunk. (check-in: e005f2d6dd user: drh tags: orderby-planning) | |
17:07 | Fix a problem in the code added by [707ea170b3] causing vdbesort.c to sort unstably. (check-in: d3e640afe6 user: dan tags: orderby-planning) | |
15:04 | Remove the sequence values from sorter records used by ORDER BY as well. (check-in: c3ae369783 user: dan tags: orderby-planning) | |
Changes
Changes to src/vdbesort.c.
︙ | ︙ | |||
558 559 560 561 562 563 564 565 566 567 568 569 570 571 | SQLITE_OPEN_EXCLUSIVE | SQLITE_OPEN_DELETEONCLOSE, &dummy ); } /* ** Merge the two sorted lists p1 and p2 into a single list. ** Set *ppOut to the head of the new list. */ static void vdbeSorterMerge( const VdbeCursor *pCsr, /* For pKeyInfo */ SorterRecord *p1, /* First list to merge */ SorterRecord *p2, /* Second list to merge */ SorterRecord **ppOut /* OUT: Head of merged list */ ){ | > > > | 558 559 560 561 562 563 564 565 566 567 568 569 570 571 572 573 574 | SQLITE_OPEN_EXCLUSIVE | SQLITE_OPEN_DELETEONCLOSE, &dummy ); } /* ** Merge the two sorted lists p1 and p2 into a single list. ** Set *ppOut to the head of the new list. ** ** In cases where key values are equal, keys from list p1 are considered ** to be smaller than list p2. */ static void vdbeSorterMerge( const VdbeCursor *pCsr, /* For pKeyInfo */ SorterRecord *p1, /* First list to merge */ SorterRecord *p2, /* Second list to merge */ SorterRecord **ppOut /* OUT: Head of merged list */ ){ |
︙ | ︙ | |||
593 594 595 596 597 598 599 600 601 602 603 604 605 606 | *ppOut = pFinal; } /* ** 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(const VdbeCursor *pCsr){ int i; SorterRecord **aSlot; SorterRecord *p; VdbeSorter *pSorter = pCsr->pSorter; | > > > > > | 596 597 598 599 600 601 602 603 604 605 606 607 608 609 610 611 612 613 614 | *ppOut = pFinal; } /* ** 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. ** ** The sort is required to be stable - if two elements compare as equal ** then the one added to the sorter first is considered the smaller. ** Currently, the list is sorted from newest to oldest - pSorter->pRecord ** points to the most recently added sort key. */ static int vdbeSorterSort(const VdbeCursor *pCsr){ int i; SorterRecord **aSlot; SorterRecord *p; VdbeSorter *pSorter = pCsr->pSorter; |
︙ | ︙ | |||
833 834 835 836 837 838 839 | i64 *pnByte /* Sum of bytes in all opened PMAs */ ){ VdbeSorter *pSorter = pCsr->pSorter; int rc = SQLITE_OK; /* Return code */ int i; /* Used to iterator through aIter[] */ i64 nByte = 0; /* Total bytes in all opened PMAs */ | | | 841 842 843 844 845 846 847 848 849 850 851 852 853 854 855 | i64 *pnByte /* Sum of bytes in all opened PMAs */ ){ VdbeSorter *pSorter = pCsr->pSorter; 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. Iterator 0 contains the oldest data. */ for(i=0; i<SORTER_MAX_MERGE_COUNT; i++){ VdbeSorterIter *pIter = &pSorter->aIter[i]; rc = vdbeSorterIterInit(db, pSorter, pSorter->iReadOff, pIter, &nByte); pSorter->iReadOff = pIter->iEof; assert( rc!=SQLITE_OK || pSorter->iReadOff<=pSorter->iWriteOff ); if( rc!=SQLITE_OK || pSorter->iReadOff>=pSorter->iWriteOff ) break; } |
︙ | ︙ | |||
1005 1006 1007 1008 1009 1010 1011 | ** case there is no cache of pIter2 in pSorter->pUnpacked, so set ** pKey2 to point to the record belonging to pIter2. ** ** Alternatively, if pIter2 contains the smaller of the two values, ** set aTree[i] to its index and update pIter1. If vdbeSorterCompare() ** was actually called above, then pSorter->pUnpacked now contains ** a value equivalent to pIter2. So set pKey2 to NULL to prevent | | > > > > > | < | 1013 1014 1015 1016 1017 1018 1019 1020 1021 1022 1023 1024 1025 1026 1027 1028 1029 1030 1031 1032 1033 1034 1035 1036 1037 1038 1039 1040 1041 | ** case there is no cache of pIter2 in pSorter->pUnpacked, so set ** pKey2 to point to the record belonging to pIter2. ** ** Alternatively, if pIter2 contains the smaller of the two values, ** set aTree[i] to its index and update pIter1. If vdbeSorterCompare() ** was actually called above, then pSorter->pUnpacked now contains ** a value equivalent to pIter2. So set pKey2 to NULL to prevent ** vdbeSorterCompare() from decoding pIter2 again. ** ** If the two values were equal, then the value from the oldest ** PMA should be considered smaller. The VdbeSorter.aIter[] array ** is sorted from oldest to newest, so pIter1 contains older values ** than pIter2 iff (pIter1<pIter2). */ if( iRes<0 || (iRes==0 && pIter1<pIter2) ){ pSorter->aTree[i] = (int)(pIter1 - pSorter->aIter); pIter2 = &pSorter->aIter[ pSorter->aTree[i ^ 0x0001] ]; pKey2 = pIter2->aKey; }else{ if( pIter1->pFile ) pKey2 = 0; pSorter->aTree[i] = (int)(pIter2 - pSorter->aIter); pIter1 = &pSorter->aIter[ pSorter->aTree[i ^ 0x0001] ]; } } *pbEof = (pSorter->aIter[pSorter->aTree[1]].pFile==0); } }else{ SorterRecord *pFree = pSorter->pRecord; pSorter->pRecord = pFree->pNext; pFree->pNext = 0; |
︙ | ︙ |
Changes to test/sort.test.
︙ | ︙ | |||
459 460 461 462 463 464 465 466 467 | insert into b values (2, 1, 'xxx'); insert into b values (1, 1, 'zzz'); insert into b values (3, 1, 'yyy'); select a.id, b.id, b.text from a join b on (a.id = b.aId) order by a.id, b.text; } } {1 2 xxx 1 3 yyy 1 1 zzz} finish_test | > > > > > > > > > > > > > > > > > > > > > > > | 459 460 461 462 463 464 465 466 467 468 469 470 471 472 473 474 475 476 477 478 479 480 481 482 483 484 485 486 487 488 489 490 | insert into b values (2, 1, 'xxx'); insert into b values (1, 1, 'zzz'); insert into b values (3, 1, 'yyy'); select a.id, b.id, b.text from a join b on (a.id = b.aId) order by a.id, b.text; } } {1 2 xxx 1 3 yyy 1 1 zzz} #------------------------------------------------------------------------- # Check that the sorter in vdbesort.c sorts in a stable fashion. # do_execsql_test sort-13.0 { CREATE TABLE t10(a, b); } do_test sort-13.1 { db transaction { for {set i 0} {$i < 100000} {incr i} { execsql { INSERT INTO t10 VALUES( $i/10, $i%10 ) } } } } {} do_execsql_test sort-13.2 { SELECT a, b FROM t10 ORDER BY a; } [db eval {SELECT a, b FROM t10 ORDER BY a, b}] do_execsql_test sort-13.3 { PRAGMA cache_size = 5; SELECT a, b FROM t10 ORDER BY a; } [db eval {SELECT a, b FROM t10 ORDER BY a, b}] finish_test |