Many hyperlinks are disabled.
Use anonymous login
to enable hyperlinks.
Overview
Comment: | If all data being sorted fits in memory, avoid writing any data out to temporary files in vdbesort.c. |
---|---|
Downloads: | Tarball | ZIP archive |
Timelines: | family | ancestors | descendants | both | merge-sort |
Files: | files | file ages | folders |
SHA1: |
71075673c625f243969c3f34c73f28f3 |
User & Date: | dan 2011-09-02 11:45:31.600 |
Context
2011-09-02
| ||
15:41 | Reduce the number of malloc() calls made when creating an index on more than 2 columns. (check-in: 065b0c9858 user: dan tags: merge-sort) | |
11:45 | If all data being sorted fits in memory, avoid writing any data out to temporary files in vdbesort.c. (check-in: 71075673c6 user: dan tags: merge-sort) | |
10:31 | Instead of a temporary b-tree, use a linked-list and merge-sort to sort records in main memory in vdbesort.c. (check-in: 7769fb988d user: dan tags: merge-sort) | |
Changes
Changes to src/vdbesort.c.
︙ | ︙ | |||
727 728 729 730 731 732 733 734 735 736 737 | sqlite3_file *pTemp2 = 0; /* Second temp file to use */ i64 iWrite2 = 0; /* Write offset for pTemp2 */ int nIter; /* Number of iterators used */ 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 = vdbeSorterListToPMA(db, pCsr); if( rc!=SQLITE_OK ) return rc; | > > > > > > > > > < < < < | 727 728 729 730 731 732 733 734 735 736 737 738 739 740 741 742 743 744 745 746 747 748 749 750 751 752 753 | sqlite3_file *pTemp2 = 0; /* Second temp file to use */ i64 iWrite2 = 0; /* Write offset for pTemp2 */ int nIter; /* Number of iterators used */ int nByte; /* Bytes of space required for aIter/aTree */ int N = 2; /* Power of 2 >= nIter */ assert( pSorter ); /* 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 = !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 ); while( N<nIter ) N += N; nByte = N * (sizeof(int) + sizeof(VdbeSorterIter)); |
︙ | ︙ | |||
822 823 824 825 826 827 828 | } /* ** Advance to the next element in the sorter. */ int sqlite3VdbeSorterNext(sqlite3 *db, VdbeCursor *pCsr, int *pbEof){ VdbeSorter *pSorter = pCsr->pSorter; | > > > | | < | | | | | > > > > > > > > > > > > > > > > > > > > > > > > > > > > > | | | | | | 827 828 829 830 831 832 833 834 835 836 837 838 839 840 841 842 843 844 845 846 847 848 849 850 851 852 853 854 855 856 857 858 859 860 861 862 863 864 865 866 867 868 869 870 871 872 873 874 875 876 877 878 879 880 881 882 883 884 885 886 887 888 889 890 891 892 893 894 895 896 897 898 | } /* ** Advance to the next element in the sorter. */ int sqlite3VdbeSorterNext(sqlite3 *db, VdbeCursor *pCsr, int *pbEof){ VdbeSorter *pSorter = pCsr->pSorter; int rc; /* Return code */ 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); }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; void *pKey; int nKey; /* Sorter key to copy into pOut */ pKey = vdbeSorterRowkey(pSorter, &nKey); if( sqlite3VdbeMemGrow(pOut, nKey, 0) ){ return SQLITE_NOMEM; } pOut->n = nKey; MemSetTypeFlag(pOut, MEM_Blob); 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 |
︙ | ︙ | |||
870 871 872 873 874 875 876 | 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; | > | | | < < | 906 907 908 909 910 911 912 913 914 915 916 917 918 919 920 921 | 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->pKeyInfo, 1, pVal->z, pVal->n, pKey, nKey, pRes); assert( rc!=SQLITE_OK || *pRes<=0 ); return rc; } #endif /* #ifndef SQLITE_OMIT_MERGE_SORT */ |