Many hyperlinks are disabled.
Use anonymous login
to enable hyperlinks.
Changes In Branch threads-closed Excluding Merge-Ins
This is equivalent to a diff from 18d1b402 to 83a105c8
2014-03-31
| ||
19:57 | Add the SQLITE_MAX_WORKER_THREADS compile time option. And the SQLITE_CONFIG_WORKER_THREADS sqlite3_config() switch. (check-in: 2774710d user: dan tags: threads) | |
2014-03-29
| ||
19:48 | Changes to make the multi-threaded sorter sort stably. (Closed-Leaf check-in: 83a105c8 user: dan tags: threads-closed) | |
10:01 | Fix a broken assert() in vdbesort.c. (check-in: 18d1b402 user: dan tags: threads) | |
09:34 | Fix a problem in vdbesort.c causing spurious SQLITE_NOMEM errors when using memsys3 or memsys5. (check-in: a683c05f user: dan tags: threads) | |
Changes to src/vdbesort.c.
︙ | ︙ | |||
87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 | int pgsz; /* Main database page size */ u8 eWork; /* One of the SORTER_THREAD_* constants */ int nConsolidate; /* For THREAD_CONS, max final PMAs */ SorterRecord *pList; /* List of records for pThread to sort */ int nInMemory; /* Expected size of PMA based on pList */ u8 *aListMemory; /* Records memory (or NULL) */ int nPMA; /* Number of PMAs currently in pTemp1 */ i64 iTemp1Off; /* Offset to write to in pTemp1 */ sqlite3_file *pTemp1; /* File to write PMAs to, or NULL */ }; /* ** NOTES ON DATA STRUCTURE USED FOR N-WAY MERGES: | > > | 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 | int pgsz; /* Main database page size */ u8 eWork; /* One of the SORTER_THREAD_* constants */ int nConsolidate; /* For THREAD_CONS, max final PMAs */ SorterRecord *pList; /* List of records for pThread to sort */ int nInMemory; /* Expected size of PMA based on pList */ u8 *aListMemory; /* Records memory (or NULL) */ u32 iSeq; /* Sequence number for PMA */ int nPMA; /* Number of PMAs currently in pTemp1 */ int bEmbeddedSeq; /* True if pTemp1 contains embedded seq. */ i64 iTemp1Off; /* Offset to write to in pTemp1 */ sqlite3_file *pTemp1; /* File to write PMAs to, or NULL */ }; /* ** NOTES ON DATA STRUCTURE USED FOR N-WAY MERGES: |
︙ | ︙ | |||
183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 | int mxPmaSize; /* Maximum PMA size, in bytes. 0==no limit */ int bUsePMA; /* True if one or more PMAs created */ SorterRecord *pRecord; /* Head of in-memory record list */ SorterMerger *pMerger; /* For final merge of PMAs (by caller) */ u8 *aMemory; /* Block of memory to alloc records from */ int iMemory; /* Offset of first free byte in aMemory */ int nMemory; /* Size of aMemory allocation in bytes */ SorterThread aThread[SQLITE_MAX_SORTER_THREAD]; }; /* ** The following type is an iterator for a PMA. It caches the current key in ** variables nKey/aKey. If the iterator is at EOF, pFile==0. */ struct VdbeSorterIter { i64 iReadOff; /* Current read offset */ i64 iEof; /* 1 byte past EOF for this iterator */ int nAlloc; /* Bytes of space at aAlloc */ int nKey; /* Number of bytes in key */ sqlite3_file *pFile; /* File iterator is reading from */ u8 *aAlloc; /* Allocated space */ u8 *aKey; /* Pointer to current key */ u8 *aBuffer; /* Current read buffer */ int nBuffer; /* Size of read buffer in bytes */ | > > > | 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 | int mxPmaSize; /* Maximum PMA size, in bytes. 0==no limit */ int bUsePMA; /* True if one or more PMAs created */ SorterRecord *pRecord; /* Head of in-memory record list */ SorterMerger *pMerger; /* For final merge of PMAs (by caller) */ u8 *aMemory; /* Block of memory to alloc records from */ int iMemory; /* Offset of first free byte in aMemory */ int nMemory; /* Size of aMemory allocation in bytes */ u32 iNextSeq; /* Sequence number for next PMA */ SorterThread aThread[SQLITE_MAX_SORTER_THREAD]; }; /* ** The following type is an iterator for a PMA. It caches the current key in ** variables nKey/aKey. If the iterator is at EOF, pFile==0. */ struct VdbeSorterIter { i64 iReadOff; /* Current read offset */ i64 iEof; /* 1 byte past EOF for this iterator */ int bEmbeddedSeq; /* True if records have sequence values */ int iSeq; /* Current sequence value */ int nAlloc; /* Bytes of space at aAlloc */ int nKey; /* Number of bytes in key */ sqlite3_file *pFile; /* File iterator is reading from */ u8 *aAlloc; /* Allocated space */ u8 *aKey; /* Pointer to current key */ u8 *aBuffer; /* Current read buffer */ int nBuffer; /* Size of read buffer in bytes */ |
︙ | ︙ | |||
413 414 415 416 417 418 419 420 421 422 423 424 425 426 | if( pIter->iReadOff>=pIter->iEof ){ /* This is an EOF condition */ vdbeSorterIterZero(pIter); return SQLITE_OK; } rc = vdbeSorterIterVarint(pIter, &nRec); if( rc==SQLITE_OK ){ pIter->nKey = (int)nRec; rc = vdbeSorterIterRead(pIter, (int)nRec, &pIter->aKey); } return rc; } | > > > > > | 418 419 420 421 422 423 424 425 426 427 428 429 430 431 432 433 434 435 436 | if( pIter->iReadOff>=pIter->iEof ){ /* This is an EOF condition */ vdbeSorterIterZero(pIter); return SQLITE_OK; } rc = vdbeSorterIterVarint(pIter, &nRec); if( rc==SQLITE_OK && pIter->bEmbeddedSeq ){ u64 iSeq; rc = vdbeSorterIterVarint(pIter, &iSeq); pIter->iSeq = (int)iSeq; } if( rc==SQLITE_OK ){ pIter->nKey = (int)nRec; rc = vdbeSorterIterRead(pIter, (int)nRec, &pIter->aKey); } return rc; } |
︙ | ︙ | |||
444 445 446 447 448 449 450 451 452 453 454 455 456 457 | assert( pThread->iTemp1Off>iStart ); assert( pIter->aAlloc==0 ); assert( pIter->aBuffer==0 ); pIter->pFile = pThread->pTemp1; pIter->iReadOff = iStart; pIter->nAlloc = 128; pIter->aAlloc = (u8*)sqlite3Malloc(pIter->nAlloc); /* Try to xFetch() a mapping of the entire temp file. If this is possible, ** the PMA will be read via the mapping. Otherwise, use xRead(). */ rc = sqlite3OsFetch(pIter->pFile, 0, pThread->iTemp1Off, &pMap); if( rc==SQLITE_OK ){ if( pMap ){ | > | 454 455 456 457 458 459 460 461 462 463 464 465 466 467 468 | assert( pThread->iTemp1Off>iStart ); assert( pIter->aAlloc==0 ); assert( pIter->aBuffer==0 ); pIter->pFile = pThread->pTemp1; pIter->iReadOff = iStart; pIter->nAlloc = 128; pIter->aAlloc = (u8*)sqlite3Malloc(pIter->nAlloc); pIter->bEmbeddedSeq = pThread->bEmbeddedSeq; /* Try to xFetch() a mapping of the entire temp file. If this is possible, ** the PMA will be read via the mapping. Otherwise, use xRead(). */ rc = sqlite3OsFetch(pIter->pFile, 0, pThread->iTemp1Off, &pMap); if( rc==SQLITE_OK ){ if( pMap ){ |
︙ | ︙ | |||
466 467 468 469 470 471 472 | if( iBuf ){ int nRead = nBuf - iBuf; if( (iStart + nRead) > pThread->iTemp1Off ){ nRead = (int)(pThread->iTemp1Off - iStart); } rc = sqlite3OsRead( pThread->pTemp1, &pIter->aBuffer[iBuf], nRead, iStart | | > > > > > > > > > > | | | > | 477 478 479 480 481 482 483 484 485 486 487 488 489 490 491 492 493 494 495 496 497 498 499 500 501 502 503 504 505 506 507 508 509 510 511 512 513 514 | if( iBuf ){ int nRead = nBuf - iBuf; if( (iStart + nRead) > pThread->iTemp1Off ){ nRead = (int)(pThread->iTemp1Off - iStart); } rc = sqlite3OsRead( pThread->pTemp1, &pIter->aBuffer[iBuf], nRead, iStart ); assert( rc!=SQLITE_IOERR_SHORT_READ ); } } } } if( rc==SQLITE_OK ){ u64 nByte; /* Size of PMA in bytes */ pIter->iEof = pThread->iTemp1Off; if( pIter->bEmbeddedSeq==0 ){ u64 iSeq, nElem; rc = vdbeSorterIterVarint(pIter, &iSeq); pIter->iSeq = (int)iSeq; if( rc==SQLITE_OK ){ rc = vdbeSorterIterVarint(pIter, &nElem); *pnByte += (nElem * sqlite3VarintLen(iSeq)); } } if( rc==SQLITE_OK ){ rc = vdbeSorterIterVarint(pIter, &nByte); pIter->iEof = pIter->iReadOff + nByte; *pnByte += nByte; } } if( rc==SQLITE_OK ){ rc = vdbeSorterIterNext(pIter); } return rc; } |
︙ | ︙ | |||
747 748 749 750 751 752 753 754 755 756 757 758 759 760 | vdbeSorterRecordFree(0, pSorter->pRecord); } vdbeSorterMergerReset(pSorter->pMerger); pSorter->pRecord = 0; pSorter->nInMemory = 0; pSorter->bUsePMA = 0; pSorter->iMemory = 0; } /* ** Free any cursor components allocated by sqlite3VdbeSorterXXX routines. */ void sqlite3VdbeSorterClose(sqlite3 *db, VdbeCursor *pCsr){ VdbeSorter *pSorter = pCsr->pSorter; | > | 769 770 771 772 773 774 775 776 777 778 779 780 781 782 783 | vdbeSorterRecordFree(0, pSorter->pRecord); } vdbeSorterMergerReset(pSorter->pMerger); pSorter->pRecord = 0; pSorter->nInMemory = 0; pSorter->bUsePMA = 0; pSorter->iMemory = 0; pSorter->iNextSeq = 0; } /* ** Free any cursor components allocated by sqlite3VdbeSorterXXX routines. */ void sqlite3VdbeSorterClose(sqlite3 *db, VdbeCursor *pCsr){ VdbeSorter *pSorter = pCsr->pSorter; |
︙ | ︙ | |||
820 821 822 823 824 825 826 827 | *ppOut = pFinal; } /* ** Sort the linked list of records headed at pThread->pList. Return ** SQLITE_OK if successful, or an SQLite error code (i.e. SQLITE_NOMEM) if ** an error occurs. */ | > > > | > | 843 844 845 846 847 848 849 850 851 852 853 854 855 856 857 858 859 860 861 862 863 864 865 | *ppOut = pFinal; } /* ** Sort the linked list of records headed at pThread->pList. Return ** SQLITE_OK if successful, or an SQLite error code (i.e. SQLITE_NOMEM) if ** an error occurs. ** ** If the pnElem argument is not NULL and no error occurs, set *pnElem to ** the total number of elements in the list. */ static int vdbeSorterSort(SorterThread *pThread, i64 *pnElem){ int i; SorterRecord **aSlot; SorterRecord *p; i64 nElem = 0; aSlot = (SorterRecord **)sqlite3MallocZero(64 * sizeof(SorterRecord *)); if( !aSlot ){ return SQLITE_NOMEM; } p = pThread->pList; |
︙ | ︙ | |||
852 853 854 855 856 857 858 859 860 861 862 863 864 865 866 867 868 869 870 871 872 873 | p->u.pNext = 0; for(i=0; aSlot[i]; i++){ vdbeSorterMerge(pThread, p, aSlot[i], &p); aSlot[i] = 0; } aSlot[i] = p; p = pNext; } p = 0; for(i=0; i<64; i++){ vdbeSorterMerge(pThread, p, aSlot[i], &p); } pThread->pList = p; sqlite3_free(aSlot); return SQLITE_OK; } /* ** Initialize a file-writer object. */ | > > | 879 880 881 882 883 884 885 886 887 888 889 890 891 892 893 894 895 896 897 898 899 900 901 902 | p->u.pNext = 0; for(i=0; aSlot[i]; i++){ vdbeSorterMerge(pThread, p, aSlot[i], &p); aSlot[i] = 0; } aSlot[i] = p; p = pNext; nElem++; } p = 0; for(i=0; i<64; i++){ vdbeSorterMerge(pThread, p, aSlot[i], &p); } pThread->pList = p; *pnElem = nElem; sqlite3_free(aSlot); return SQLITE_OK; } /* ** Initialize a file-writer object. */ |
︙ | ︙ | |||
985 986 987 988 989 990 991 | ** * A varint. This varint contains the total number of bytes of content ** in the PMA (not including the varint itself). ** ** * One or more records packed end-to-end in order of ascending keys. ** Each record consists of a varint followed by a blob of data (the ** key). The varint is the number of bytes in the blob of data. */ | | > | > > | 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 1042 1043 1044 1045 1046 1047 1048 1049 1050 1051 1052 1053 1054 1055 1056 1057 1058 | ** * A varint. This varint contains the total number of bytes of content ** in the PMA (not including the varint itself). ** ** * One or more records packed end-to-end in order of ascending keys. ** Each record consists of a varint followed by a blob of data (the ** key). The varint is the number of bytes in the blob of data. */ static int vdbeSorterListToPMA(SorterThread *pThread, i64 nElem){ int rc = SQLITE_OK; /* Return code */ FileWriter writer; /* Object used to write to the file */ memset(&writer, 0, sizeof(FileWriter)); assert( pThread->nInMemory>0 ); /* If the first temporary PMA file has not been opened, open it now. */ if( pThread->pTemp1==0 ){ rc = vdbeSorterOpenTempFile(pThread->pVfs, &pThread->pTemp1); assert( rc!=SQLITE_OK || pThread->pTemp1 ); assert( pThread->iTemp1Off==0 ); assert( pThread->nPMA==0 ); assert( pThread->bEmbeddedSeq==0 ); } /* Try to get the file to memory map */ if( rc==SQLITE_OK ){ rc = vdbeSorterExtendFile( pThread->pTemp1, pThread->iTemp1Off + 9 + 9 + 9 + pThread->nInMemory ); } if( rc==SQLITE_OK ){ SorterRecord *p; SorterRecord *pNext = 0; fileWriterInit(pThread->pTemp1, &writer, pThread->pgsz, pThread->iTemp1Off); pThread->nPMA++; fileWriterWriteVarint(&writer, (u64)pThread->iSeq); fileWriterWriteVarint(&writer, (u64)nElem); fileWriterWriteVarint(&writer, pThread->nInMemory); for(p=pThread->pList; p; p=pNext){ pNext = p->u.pNext; fileWriterWriteVarint(&writer, p->nVal); fileWriterWrite(&writer, SRVAL(p), p->nVal); if( pThread->aListMemory==0 ) sqlite3_free(p); } |
︙ | ︙ | |||
1087 1088 1089 1090 1091 1092 1093 | ** 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). */ | | | 1119 1120 1121 1122 1123 1124 1125 1126 1127 1128 1129 1130 1131 1132 1133 | ** 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->iSeq < pIter2->iSeq) ){ pMerger->aTree[i] = (int)(pIter1 - pMerger->aIter); pIter2 = &pMerger->aIter[ pMerger->aTree[i ^ 0x0001] ]; pKey2 = pIter2->aKey; }else{ if( pIter1->pFile ) pKey2 = 0; pMerger->aTree[i] = (int)(pIter2 - pMerger->aIter); pIter1 = &pMerger->aIter[ pMerger->aTree[i ^ 0x0001] ]; |
︙ | ︙ | |||
1184 1185 1186 1187 1188 1189 1190 1191 1192 1193 1194 1195 1196 1197 1198 1199 1200 1201 1202 1203 1204 1205 | fileWriterInit(pTemp2, &writer, pThread->pgsz, iWriteOff); fileWriterWriteVarint(&writer, nOut); while( rc==SQLITE_OK && bEof==0 ){ VdbeSorterIter *pIter = &pMerger->aIter[ pMerger->aTree[1] ]; assert( pIter->pFile!=0 ); /* pIter is not at EOF */ fileWriterWriteVarint(&writer, pIter->nKey); fileWriterWrite(&writer, pIter->aKey, pIter->nKey); rc = vdbeSorterNext(pThread, pMerger, &bEof); } rc2 = fileWriterFinish(&writer, &iWriteOff); if( rc==SQLITE_OK ) rc = rc2; } vdbeSorterMergerFree(pMerger); sqlite3OsCloseFree(pThread->pTemp1); pThread->pTemp1 = pTemp2; pThread->nPMA = (i / SORTER_MAX_MERGE_COUNT); pThread->iTemp1Off = iWriteOff; } }else{ /* Sort the pThread->pList list */ | > > > > > | > > | | 1216 1217 1218 1219 1220 1221 1222 1223 1224 1225 1226 1227 1228 1229 1230 1231 1232 1233 1234 1235 1236 1237 1238 1239 1240 1241 1242 1243 1244 1245 1246 1247 1248 1249 1250 1251 1252 1253 1254 1255 1256 1257 1258 1259 1260 1261 | fileWriterInit(pTemp2, &writer, pThread->pgsz, iWriteOff); fileWriterWriteVarint(&writer, nOut); while( rc==SQLITE_OK && bEof==0 ){ VdbeSorterIter *pIter = &pMerger->aIter[ pMerger->aTree[1] ]; assert( pIter->pFile!=0 ); /* pIter is not at EOF */ fileWriterWriteVarint(&writer, pIter->nKey); fileWriterWriteVarint(&writer, (u64)pIter->iSeq); fileWriterWrite(&writer, pIter->aKey, pIter->nKey); rc = vdbeSorterNext(pThread, pMerger, &bEof); } rc2 = fileWriterFinish(&writer, &iWriteOff); if( rc==SQLITE_OK ) rc = rc2; } vdbeSorterMergerFree(pMerger); sqlite3OsCloseFree(pThread->pTemp1); pThread->pTemp1 = pTemp2; pThread->nPMA = (i / SORTER_MAX_MERGE_COUNT); pThread->iTemp1Off = iWriteOff; pThread->bEmbeddedSeq = 1; sqlite3OsUnfetch(pTemp2, 0, 0); } }else{ i64 nElem; /* Sort the pThread->pList list */ rc = vdbeSorterSort(pThread, &nElem); /* If required, write the list out to a PMA. */ if( rc==SQLITE_OK && pThread->eWork==SORTER_THREAD_TO_PMA ){ #ifdef SQLITE_DEBUG i64 nExpect = pThread->nInMemory + sqlite3VarintLen(pThread->nInMemory) + sqlite3VarintLen(pThread->iSeq) + sqlite3VarintLen(nElem) + pThread->iTemp1Off; #endif rc = vdbeSorterListToPMA(pThread, nElem); assert( rc!=SQLITE_OK || (nExpect==pThread->iTemp1Off) ); } } thread_out: pThread->bDone = 1; return SQLITE_INT_TO_PTR(rc); |
︙ | ︙ | |||
1264 1265 1266 1267 1268 1269 1270 1271 1272 1273 1274 1275 1276 1277 | if( rc==SQLITE_OK ){ int bUseFg = (bFg || i==(SQLITE_MAX_SORTER_THREAD-1)); assert( pThread->pThread==0 && pThread->bDone==0 ); pThread->eWork = SORTER_THREAD_TO_PMA; pThread->pList = pSorter->pRecord; pThread->nInMemory = pSorter->nInMemory; pSorter->nInMemory = 0; pSorter->pRecord = 0; if( pSorter->aMemory ){ u8 *aMem = pThread->aListMemory; pThread->aListMemory = pSorter->aMemory; pSorter->aMemory = aMem; | > | 1303 1304 1305 1306 1307 1308 1309 1310 1311 1312 1313 1314 1315 1316 1317 | if( rc==SQLITE_OK ){ int bUseFg = (bFg || i==(SQLITE_MAX_SORTER_THREAD-1)); assert( pThread->pThread==0 && pThread->bDone==0 ); pThread->eWork = SORTER_THREAD_TO_PMA; pThread->pList = pSorter->pRecord; pThread->nInMemory = pSorter->nInMemory; pThread->iSeq = pSorter->iNextSeq++; pSorter->nInMemory = 0; pSorter->pRecord = 0; if( pSorter->aMemory ){ u8 *aMem = pThread->aListMemory; pThread->aListMemory = pSorter->aMemory; pSorter->aMemory = aMem; |
︙ | ︙ |