Many hyperlinks are disabled.
Use anonymous login
to enable hyperlinks.
Overview
Comment: | Optimize cases where all the sorter is sorting a set of records that all begin with integer values, or that all begin with text values to be compared using BINARY. |
---|---|
Downloads: | Tarball | ZIP archive |
Timelines: | family | ancestors | descendants | both | sorter-opt |
Files: | files | file ages | folders |
SHA1: |
ce5ad17c25cf2f8274ce304c51e4421f |
User & Date: | dan 2015-03-26 11:55:03.488 |
Context
2015-03-28
| ||
19:56 | Further optimizations for sorting records that begin with integer or text values. (check-in: 24fe9f25d6 user: dan tags: sorter-opt) | |
2015-03-26
| ||
12:38 | Merge sorter optimization into this branch. (check-in: aeb8e9a9f2 user: dan tags: insert-select-opt) | |
11:55 | Optimize cases where all the sorter is sorting a set of records that all begin with integer values, or that all begin with text values to be compared using BINARY. (check-in: ce5ad17c25 user: dan tags: sorter-opt) | |
2015-03-25
| ||
18:29 | Change an unreachable branch into an assert(). (check-in: fb076b28c3 user: drh tags: trunk) | |
Changes
Changes to src/vdbesort.c.
︙ | ︙ | |||
294 295 296 297 298 299 300 301 302 303 304 305 306 307 | struct SortSubtask { SQLiteThread *pThread; /* Background thread, if any */ int bDone; /* Set if thread is finished but not joined */ VdbeSorter *pSorter; /* Sorter that owns this sub-task */ UnpackedRecord *pUnpacked; /* Space to unpack a record */ SorterList list; /* List for thread to write to a PMA */ int nPMA; /* Number of PMAs currently in file */ SorterFile file; /* Temp file for level-0 PMAs */ SorterFile file2; /* Space for other PMAs */ }; /* ** Main sorter structure. A single instance of this is allocated for each ** sorter cursor created by the VDBE. | > | 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 | struct SortSubtask { SQLiteThread *pThread; /* Background thread, if any */ int bDone; /* Set if thread is finished but not joined */ VdbeSorter *pSorter; /* Sorter that owns this sub-task */ UnpackedRecord *pUnpacked; /* Space to unpack a record */ SorterList list; /* List for thread to write to a PMA */ int nPMA; /* Number of PMAs currently in file */ RecordCompare xCompare; /* Compare function to use */ SorterFile file; /* Temp file for level-0 PMAs */ SorterFile file2; /* Space for other PMAs */ }; /* ** Main sorter structure. A single instance of this is allocated for each ** sorter cursor created by the VDBE. |
︙ | ︙ | |||
324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 | SorterList list; /* List of in-memory records */ int iMemory; /* Offset of free space in list.aMemory */ int nMemory; /* Size of list.aMemory allocation in bytes */ u8 bUsePMA; /* True if one or more PMAs created */ u8 bUseThreads; /* True to use background threads */ u8 iPrev; /* Previous thread used to flush PMA */ u8 nTask; /* Size of aTask[] array */ SortSubtask aTask[1]; /* One or more subtasks */ }; /* ** An instance of the following object is used to read records out of a ** PMA, in sorted order. The next key to be read is cached in nKey/aKey. ** aKey might point into aMap or into aBuffer. If neither of those locations ** contain a contiguous representation of the key, then aAlloc is allocated ** and the key is copied into aAlloc and aKey is made to poitn to aAlloc. | > > > > | 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 | SorterList list; /* List of in-memory records */ int iMemory; /* Offset of free space in list.aMemory */ int nMemory; /* Size of list.aMemory allocation in bytes */ u8 bUsePMA; /* True if one or more PMAs created */ u8 bUseThreads; /* True to use background threads */ u8 iPrev; /* Previous thread used to flush PMA */ u8 nTask; /* Size of aTask[] array */ u8 typeMask; SortSubtask aTask[1]; /* One or more subtasks */ }; #define SORTER_TYPE_INTEGER 0x01 #define SORTER_TYPE_TEXT 0x02 /* ** An instance of the following object is used to read records out of a ** PMA, in sorted order. The next key to be read is cached in nKey/aKey. ** aKey might point into aMap or into aBuffer. If neither of those locations ** contain a contiguous representation of the key, then aAlloc is allocated ** and the key is copied into aAlloc and aKey is made to poitn to aAlloc. |
︙ | ︙ | |||
761 762 763 764 765 766 767 | const void *pKey1, int nKey1, /* Left side of comparison */ const void *pKey2, int nKey2 /* Right side of comparison */ ){ UnpackedRecord *r2 = pTask->pUnpacked; if( pKey2 ){ sqlite3VdbeRecordUnpack(pTask->pSorter->pKeyInfo, nKey2, pKey2, r2); } | | | 766 767 768 769 770 771 772 773 774 775 776 777 778 779 780 | const void *pKey1, int nKey1, /* Left side of comparison */ const void *pKey2, int nKey2 /* Right side of comparison */ ){ UnpackedRecord *r2 = pTask->pUnpacked; if( pKey2 ){ sqlite3VdbeRecordUnpack(pTask->pSorter->pKeyInfo, nKey2, pKey2, r2); } return pTask->xCompare(nKey1, pKey1, r2); } /* ** Initialize the temporary index cursor just opened as a sorter cursor. ** ** Usually, the sorter module uses the value of (pCsr->pKeyInfo->nField) ** to determine the number of fields that should be compared from the |
︙ | ︙ | |||
831 832 833 834 835 836 837 | pCsr->pSorter = pSorter; if( pSorter==0 ){ rc = SQLITE_NOMEM; }else{ pSorter->pKeyInfo = pKeyInfo = (KeyInfo*)((u8*)pSorter + sz); memcpy(pKeyInfo, pCsr->pKeyInfo, szKeyInfo); pKeyInfo->db = 0; | | > > > > | 836 837 838 839 840 841 842 843 844 845 846 847 848 849 850 851 852 853 854 855 856 | pCsr->pSorter = pSorter; if( pSorter==0 ){ rc = SQLITE_NOMEM; }else{ pSorter->pKeyInfo = pKeyInfo = (KeyInfo*)((u8*)pSorter + sz); memcpy(pKeyInfo, pCsr->pKeyInfo, szKeyInfo); pKeyInfo->db = 0; if( nField && nWorker==0 ){ pKeyInfo->nXField += (pKeyInfo->nField - nField); pKeyInfo->nField = nField; } pSorter->pgsz = pgsz = sqlite3BtreeGetPageSize(db->aDb[0].pBt); pSorter->nTask = nWorker + 1; pSorter->iPrev = nWorker-1; pSorter->bUseThreads = (pSorter->nTask>1); pSorter->db = db; for(i=0; i<pSorter->nTask; i++){ SortSubtask *pTask = &pSorter->aTask[i]; pTask->pSorter = pSorter; } |
︙ | ︙ | |||
859 860 861 862 863 864 865 866 867 868 869 870 871 872 | if( sqlite3GlobalConfig.pScratch==0 ){ assert( pSorter->iMemory==0 ); pSorter->nMemory = pgsz; pSorter->list.aMemory = (u8*)sqlite3Malloc(pgsz); if( !pSorter->list.aMemory ) rc = SQLITE_NOMEM; } } } return rc; } #undef nWorker /* Defined at the top of this function */ /* | > > > > | 868 869 870 871 872 873 874 875 876 877 878 879 880 881 882 883 884 885 | if( sqlite3GlobalConfig.pScratch==0 ){ assert( pSorter->iMemory==0 ); pSorter->nMemory = pgsz; pSorter->list.aMemory = (u8*)sqlite3Malloc(pgsz); if( !pSorter->list.aMemory ) rc = SQLITE_NOMEM; } } if( (pKeyInfo->nField+pKeyInfo->nXField)<13 && pKeyInfo->aColl[0]==0 ){ pSorter->typeMask = SORTER_TYPE_INTEGER | SORTER_TYPE_TEXT; } } return rc; } #undef nWorker /* Defined at the top of this function */ /* |
︙ | ︙ | |||
1178 1179 1180 1181 1182 1183 1184 1185 1186 1187 1188 1189 1190 1191 | pTask->pUnpacked = sqlite3VdbeAllocUnpackedRecord( pTask->pSorter->pKeyInfo, 0, 0, &pFree ); assert( pTask->pUnpacked==(UnpackedRecord*)pFree ); if( pFree==0 ) return SQLITE_NOMEM; pTask->pUnpacked->nField = pTask->pSorter->pKeyInfo->nField; pTask->pUnpacked->errCode = 0; } return SQLITE_OK; } /* ** Merge the two sorted lists p1 and p2 into a single list. | > > > > > > > | 1191 1192 1193 1194 1195 1196 1197 1198 1199 1200 1201 1202 1203 1204 1205 1206 1207 1208 1209 1210 1211 | pTask->pUnpacked = sqlite3VdbeAllocUnpackedRecord( pTask->pSorter->pKeyInfo, 0, 0, &pFree ); assert( pTask->pUnpacked==(UnpackedRecord*)pFree ); if( pFree==0 ) return SQLITE_NOMEM; pTask->pUnpacked->nField = pTask->pSorter->pKeyInfo->nField; pTask->pUnpacked->errCode = 0; if( pTask->pSorter->pKeyInfo->aSortOrder[0] ){ pTask->pUnpacked->r1 = 1; pTask->pUnpacked->r2 = -1; }else{ pTask->pUnpacked->r1 = -1; pTask->pUnpacked->r2 = 1; } } return SQLITE_OK; } /* ** Merge the two sorted lists p1 and p2 into a single list. |
︙ | ︙ | |||
1230 1231 1232 1233 1234 1235 1236 1237 1238 1239 1240 1241 1242 | int i; SorterRecord **aSlot; SorterRecord *p; int rc; rc = vdbeSortAllocUnpacked(pTask); if( rc!=SQLITE_OK ) return rc; aSlot = (SorterRecord **)sqlite3MallocZero(64 * sizeof(SorterRecord *)); if( !aSlot ){ return SQLITE_NOMEM; } | > > > > > > > > > < | 1250 1251 1252 1253 1254 1255 1256 1257 1258 1259 1260 1261 1262 1263 1264 1265 1266 1267 1268 1269 1270 1271 1272 1273 1274 1275 1276 1277 1278 | int i; SorterRecord **aSlot; SorterRecord *p; int rc; rc = vdbeSortAllocUnpacked(pTask); if( rc!=SQLITE_OK ) return rc; p = pList->pList; if( pTask->pSorter->typeMask==0 ){ pTask->xCompare = sqlite3VdbeRecordCompare; }else{ UnpackedRecord *pRec = pTask->pUnpacked; sqlite3VdbeRecordUnpack(pTask->pSorter->pKeyInfo, p->nVal, SRVAL(p), pRec); pTask->xCompare = sqlite3VdbeFindCompare(pRec); } aSlot = (SorterRecord **)sqlite3MallocZero(64 * sizeof(SorterRecord *)); if( !aSlot ){ return SQLITE_NOMEM; } while( p ){ SorterRecord *pNext; if( pList->aMemory ){ if( (u8*)p==pList->aMemory ){ pNext = 0; }else{ assert( p->u.iNext<sqlite3MallocSize(pList->aMemory) ); |
︙ | ︙ | |||
1598 1599 1600 1601 1602 1603 1604 1605 1606 1607 1608 1609 1610 1611 | VdbeSorter *pSorter = pCsr->pSorter; int rc = SQLITE_OK; /* Return Code */ SorterRecord *pNew; /* New list element */ int bFlush; /* True to flush contents of memory to PMA */ int nReq; /* Bytes of memory required */ int nPMA; /* Bytes of PMA space required */ assert( pSorter ); /* Figure out whether or not the current contents of memory should be ** flushed to a PMA before continuing. If so, do so. ** ** If using the single large allocation mode (pSorter->aMemory!=0), then | > > > > > > > > > > | 1626 1627 1628 1629 1630 1631 1632 1633 1634 1635 1636 1637 1638 1639 1640 1641 1642 1643 1644 1645 1646 1647 1648 1649 | VdbeSorter *pSorter = pCsr->pSorter; int rc = SQLITE_OK; /* Return Code */ SorterRecord *pNew; /* New list element */ int bFlush; /* True to flush contents of memory to PMA */ int nReq; /* Bytes of memory required */ int nPMA; /* Bytes of PMA space required */ int t; /* serial type of first record field */ getVarint32((const u8*)&pVal->z[1], t); if( t>0 && t<10 && t!=7 ){ pSorter->typeMask &= SORTER_TYPE_INTEGER; }else if( t & 0x01 ){ pSorter->typeMask &= SORTER_TYPE_TEXT; }else{ pSorter->typeMask = 0; } assert( pSorter ); /* Figure out whether or not the current contents of memory should be ** flushed to a PMA before continuing. If so, do so. ** ** If using the single large allocation mode (pSorter->aMemory!=0), then |
︙ | ︙ | |||
2284 2285 2286 2287 2288 2289 2290 2291 2292 2293 2294 2295 2296 2297 | */ static int vdbeSorterSetupMerge(VdbeSorter *pSorter){ int rc; /* Return code */ SortSubtask *pTask0 = &pSorter->aTask[0]; MergeEngine *pMain = 0; #if SQLITE_MAX_WORKER_THREADS sqlite3 *db = pTask0->pSorter->db; #endif rc = vdbeSorterMergeTreeBuild(pSorter, &pMain); if( rc==SQLITE_OK ){ #if SQLITE_MAX_WORKER_THREADS assert( pSorter->bUseThreads==0 || pSorter->nTask>1 ); if( pSorter->bUseThreads ){ | > > > > > > > | 2322 2323 2324 2325 2326 2327 2328 2329 2330 2331 2332 2333 2334 2335 2336 2337 2338 2339 2340 2341 2342 | */ static int vdbeSorterSetupMerge(VdbeSorter *pSorter){ int rc; /* Return code */ SortSubtask *pTask0 = &pSorter->aTask[0]; MergeEngine *pMain = 0; #if SQLITE_MAX_WORKER_THREADS sqlite3 *db = pTask0->pSorter->db; RecordCompare xCompare = (pSorter->typeMask==0 ? sqlite3VdbeRecordCompare : pSorter->aTask[0].xCompare ); int i; for(i=0; i<pSorter->nTask; i++){ pSorter->aTask[i].xCompare = xCompare; } #endif rc = vdbeSorterMergeTreeBuild(pSorter, &pMain); if( rc==SQLITE_OK ){ #if SQLITE_MAX_WORKER_THREADS assert( pSorter->bUseThreads==0 || pSorter->nTask>1 ); if( pSorter->bUseThreads ){ |
︙ | ︙ |