Many hyperlinks are disabled.
Use anonymous login
to enable hyperlinks.
Overview
Comment: | The build works again with -DSQLITE_OMIT_MERGE_SORT. The merge-sorter now avoids spilling to disk (letting the in-memory linked list grow without bound) if PRAGMA temp_store=3. |
---|---|
Downloads: | Tarball | ZIP archive |
Timelines: | family | ancestors | descendants | both | merge-sort |
Files: | files | file ages | folders |
SHA1: |
68e26c4487696d194ee85370380e4b0e |
User & Date: | drh 2011-09-03 00:17:51.023 |
Context
2011-09-03
| ||
14:36 | Reduce the number of VdbeRecordUnpack() calls made in vdbesort.c. (check-in: 666c2c3cff user: dan tags: merge-sort) | |
00:17 | The build works again with -DSQLITE_OMIT_MERGE_SORT. The merge-sorter now avoids spilling to disk (letting the in-memory linked list grow without bound) if PRAGMA temp_store=3. (check-in: 68e26c4487 user: drh tags: merge-sort) | |
2011-09-02
| ||
21:42 | Remove some dead code. Fix a faulty assert(). Improve some variable names. (check-in: a9a64592cf user: drh tags: merge-sort) | |
Changes
Changes to src/build.c.
︙ | ︙ | |||
2331 2332 2333 2334 2335 2336 2337 | Vdbe *v; /* Generate code into this virtual machine */ KeyInfo *pKey; /* KeyInfo for index */ int regIdxKey; /* Registers containing the index key */ int regRecord; /* Register holding assemblied index record */ sqlite3 *db = pParse->db; /* The database connection */ int iDb = sqlite3SchemaToIndex(db, pIndex->pSchema); | < < < < < < < < < | 2331 2332 2333 2334 2335 2336 2337 2338 2339 2340 2341 2342 2343 2344 | Vdbe *v; /* Generate code into this virtual machine */ KeyInfo *pKey; /* KeyInfo for index */ int regIdxKey; /* Registers containing the index key */ int regRecord; /* Register holding assemblied index record */ sqlite3 *db = pParse->db; /* The database connection */ int iDb = sqlite3SchemaToIndex(db, pIndex->pSchema); #ifndef SQLITE_OMIT_AUTHORIZATION if( sqlite3AuthCheck(pParse, SQLITE_REINDEX, pIndex->zName, 0, db->aDb[iDb].zName ) ){ return; } #endif |
︙ | ︙ | |||
2365 2366 2367 2368 2369 2370 2371 2372 | pKey = sqlite3IndexKeyinfo(pParse, pIndex); sqlite3VdbeAddOp4(v, OP_OpenWrite, iIdx, tnum, iDb, (char *)pKey, P4_KEYINFO_HANDOFF); if( memRootPage>=0 ){ sqlite3VdbeChangeP5(v, 1); } /* Open the sorter cursor if we are to use one. */ | > < | | < > | | | | | | | | | | | | | | | | | > > > | | > | | 2356 2357 2358 2359 2360 2361 2362 2363 2364 2365 2366 2367 2368 2369 2370 2371 2372 2373 2374 2375 2376 2377 2378 2379 2380 2381 2382 2383 2384 2385 2386 2387 2388 2389 2390 2391 2392 2393 2394 2395 2396 2397 2398 2399 2400 2401 2402 2403 2404 2405 2406 2407 2408 2409 2410 2411 2412 2413 2414 2415 2416 2417 2418 2419 2420 2421 2422 2423 2424 2425 2426 | pKey = sqlite3IndexKeyinfo(pParse, pIndex); sqlite3VdbeAddOp4(v, OP_OpenWrite, iIdx, tnum, iDb, (char *)pKey, P4_KEYINFO_HANDOFF); if( memRootPage>=0 ){ sqlite3VdbeChangeP5(v, 1); } #ifndef SQLITE_OMIT_MERGE_SORT /* Open the sorter cursor if we are to use one. */ iSorter = pParse->nTab++; sqlite3VdbeAddOp4(v, OP_SorterOpen, iSorter, 0, 0, (char*)pKey, P4_KEYINFO); #endif /* Open the table. Loop through all rows of the table, inserting index ** records into the sorter. */ sqlite3OpenTable(pParse, iTab, iDb, pTab, OP_OpenRead); addr1 = sqlite3VdbeAddOp2(v, OP_Rewind, iTab, 0); addr2 = addr1 + 1; regRecord = sqlite3GetTempReg(pParse); regIdxKey = sqlite3GenerateIndexKey(pParse, pIndex, iTab, regRecord, 1); #ifndef SQLITE_OMIT_MERGE_SORT sqlite3VdbeAddOp2(v, OP_SorterInsert, iSorter, regRecord); sqlite3VdbeAddOp2(v, OP_Next, iTab, addr1+1); sqlite3VdbeJumpHere(v, addr1); addr1 = sqlite3VdbeAddOp2(v, OP_SorterSort, iSorter, 0); if( pIndex->onError!=OE_None ){ int j2 = sqlite3VdbeCurrentAddr(v) + 3; sqlite3VdbeAddOp2(v, OP_Goto, 0, j2); addr2 = sqlite3VdbeCurrentAddr(v); sqlite3VdbeAddOp3(v, OP_SorterCompare, iSorter, j2, regRecord); sqlite3HaltConstraint( pParse, OE_Abort, "indexed columns are not unique", P4_STATIC ); }else{ addr2 = sqlite3VdbeCurrentAddr(v); } sqlite3VdbeAddOp2(v, OP_SorterData, iSorter, regRecord); sqlite3VdbeAddOp3(v, OP_IdxInsert, iIdx, regRecord, 1); sqlite3VdbeChangeP5(v, OPFLAG_USESEEKRESULT); #else if( pIndex->onError!=OE_None ){ const int regRowid = regIdxKey + pIndex->nColumn; const int j2 = sqlite3VdbeCurrentAddr(v) + 2; void * const pRegKey = SQLITE_INT_TO_PTR(regIdxKey); /* The registers accessed by the OP_IsUnique opcode were allocated ** using sqlite3GetTempRange() inside of the sqlite3GenerateIndexKey() ** call above. Just before that function was freed they were released ** (made available to the compiler for reuse) using ** sqlite3ReleaseTempRange(). So in some ways having the OP_IsUnique ** opcode use the values stored within seems dangerous. However, since ** we can be sure that no other temp registers have been allocated ** since sqlite3ReleaseTempRange() was called, it is safe to do so. */ sqlite3VdbeAddOp4(v, OP_IsUnique, iIdx, j2, regRowid, pRegKey, P4_INT32); sqlite3HaltConstraint( pParse, OE_Abort, "indexed columns are not unique", P4_STATIC); } sqlite3VdbeAddOp3(v, OP_IdxInsert, iIdx, regRecord, 0); sqlite3VdbeChangeP5(v, OPFLAG_USESEEKRESULT); #endif sqlite3ReleaseTempReg(pParse, regRecord); sqlite3VdbeAddOp2(v, OP_SorterNext, iSorter, addr2); sqlite3VdbeJumpHere(v, addr1); sqlite3VdbeAddOp1(v, OP_Close, iTab); sqlite3VdbeAddOp1(v, OP_Close, iIdx); sqlite3VdbeAddOp1(v, OP_Close, iSorter); } |
︙ | ︙ |
Changes to src/sqliteInt.h.
︙ | ︙ | |||
368 369 370 371 372 373 374 | ** Provide a default value for SQLITE_TEMP_STORE in case it is not specified ** on the command-line */ #ifndef SQLITE_TEMP_STORE # define SQLITE_TEMP_STORE 1 #endif | < < < < < < < < | 368 369 370 371 372 373 374 375 376 377 378 379 380 381 | ** Provide a default value for SQLITE_TEMP_STORE in case it is not specified ** on the command-line */ #ifndef SQLITE_TEMP_STORE # define SQLITE_TEMP_STORE 1 #endif /* ** GCC does not define the offsetof() macro so we'll have to do it ** ourselves. */ #ifndef offsetof #define offsetof(STRUCTURE,FIELD) ((int)((char*)&((STRUCTURE*)0)->FIELD)) #endif |
︙ | ︙ |
Changes to src/vdbe.c.
︙ | ︙ | |||
3211 3212 3213 3214 3215 3216 3217 | /* Opcode: OpenSorter P1 P2 * P4 * ** ** This opcode works like OP_OpenEphemeral except that it opens ** a transient index that is specifically designed to sort large ** tables using an external merge-sort algorithm. */ | | < > > > > > | 3211 3212 3213 3214 3215 3216 3217 3218 3219 3220 3221 3222 3223 3224 3225 3226 3227 3228 3229 3230 3231 3232 3233 3234 3235 3236 3237 | /* Opcode: OpenSorter P1 P2 * P4 * ** ** This opcode works like OP_OpenEphemeral except that it opens ** a transient index that is specifically designed to sort large ** tables using an external merge-sort algorithm. */ case OP_SorterOpen: { VdbeCursor *pCx; #ifndef SQLITE_OMIT_MERGE_SORT pCx = allocateCursor(p, pOp->p1, pOp->p2, -1, 1); if( pCx==0 ) goto no_mem; pCx->pKeyInfo = pOp->p4.pKeyInfo; pCx->pKeyInfo->enc = ENC(p->db); pCx->isSorter = 1; rc = sqlite3VdbeSorterInit(db, pCx); #else pOp->opcode = OP_OpenEphemeral; pc--; #endif break; } /* Opcode: OpenPseudo P1 P2 P3 * * ** ** Open a new cursor that points to a fake table that contains a single ** row of data. The content of that one row in the content of memory |
︙ | ︙ | |||
4098 4099 4100 4101 4102 4103 4104 4105 4106 4107 4108 4109 4110 4111 4112 4113 4114 4115 | /* Opcode: SorterData P1 P2 * * * ** ** Write into register P2 the current sorter data for sorter cursor P1. */ case OP_SorterData: { VdbeCursor *pC; pOut = &aMem[pOp->p2]; pC = p->apCsr[pOp->p1]; assert( pC->isSorter ); rc = sqlite3VdbeSorterRowkey(pC, pOut); break; } /* Opcode: RowData P1 P2 * * * ** ** Write into register P2 the complete row data for cursor P1. ** There is no interpretation of the data. | > > > > > | 4102 4103 4104 4105 4106 4107 4108 4109 4110 4111 4112 4113 4114 4115 4116 4117 4118 4119 4120 4121 4122 4123 4124 | /* Opcode: SorterData P1 P2 * * * ** ** Write into register P2 the current sorter data for sorter cursor P1. */ case OP_SorterData: { VdbeCursor *pC; #ifndef SQLITE_OMIT_MERGE_SORT pOut = &aMem[pOp->p2]; pC = p->apCsr[pOp->p1]; assert( pC->isSorter ); rc = sqlite3VdbeSorterRowkey(pC, pOut); #else pOp->opcode = OP_RowKey; pc--; #endif break; } /* Opcode: RowData P1 P2 * * * ** ** Write into register P2 the complete row data for cursor P1. ** There is no interpretation of the data. |
︙ | ︙ | |||
4144 4145 4146 4147 4148 4149 4150 | pC = p->apCsr[pOp->p1]; assert( pC->isSorter==0 ); assert( pC->isTable || pOp->opcode!=OP_RowData ); assert( pC->isIndex || pOp->opcode==OP_RowData ); assert( pC!=0 ); assert( pC->nullRow==0 ); assert( pC->pseudoTableReg==0 ); | < | | 4153 4154 4155 4156 4157 4158 4159 4160 4161 4162 4163 4164 4165 4166 4167 | pC = p->apCsr[pOp->p1]; assert( pC->isSorter==0 ); assert( pC->isTable || pOp->opcode!=OP_RowData ); assert( pC->isIndex || pOp->opcode==OP_RowData ); assert( pC!=0 ); assert( pC->nullRow==0 ); assert( pC->pseudoTableReg==0 ); assert( !pC->isSorter ); assert( pC->pCursor!=0 ); pCrsr = pC->pCursor; assert( sqlite3BtreeCursorIsValid(pCrsr) ); /* The OP_RowKey and OP_RowData opcodes always follow OP_NotExists or ** OP_Rewind/Op_Next with no intervening instructions that might invalidate ** the cursor. Hence the following sqlite3VdbeCursorMoveto() call is always |
︙ | ︙ | |||
4303 4304 4305 4306 4307 4308 4309 4310 4311 4312 4313 4314 4315 4316 | ** then rewinding that index and playing it back from beginning to ** end. We use the OP_Sort opcode instead of OP_Rewind to do the ** rewinding so that the global variable will be incremented and ** regression tests can determine whether or not the optimizer is ** correctly optimizing out sorts. */ case OP_SorterSort: /* jump */ case OP_Sort: { /* jump */ #ifdef SQLITE_TEST sqlite3_sort_count++; sqlite3_search_count--; #endif p->aCounter[SQLITE_STMTSTATUS_SORT-1]++; /* Fall through into OP_Rewind */ | > > > | 4311 4312 4313 4314 4315 4316 4317 4318 4319 4320 4321 4322 4323 4324 4325 4326 4327 | ** then rewinding that index and playing it back from beginning to ** end. We use the OP_Sort opcode instead of OP_Rewind to do the ** rewinding so that the global variable will be incremented and ** regression tests can determine whether or not the optimizer is ** correctly optimizing out sorts. */ case OP_SorterSort: /* jump */ #ifdef SQLITE_OMIT_MERGE_SORT pOp->opcode = OP_Sort; #endif case OP_Sort: { /* jump */ #ifdef SQLITE_TEST sqlite3_sort_count++; sqlite3_search_count--; #endif p->aCounter[SQLITE_STMTSTATUS_SORT-1]++; /* Fall through into OP_Rewind */ |
︙ | ︙ | |||
4381 4382 4383 4384 4385 4386 4387 4388 4389 4390 4391 4392 4393 4394 | ** P4 is always of type P4_ADVANCE. The function pointer points to ** sqlite3BtreePrevious(). ** ** If P5 is positive and the jump is taken, then event counter ** number P5-1 in the prepared statement is incremented. */ case OP_SorterNext: /* jump */ case OP_Prev: /* jump */ case OP_Next: { /* jump */ VdbeCursor *pC; int res; CHECK_FOR_INTERRUPT; assert( pOp->p1>=0 && pOp->p1<p->nCursor ); | > > > | 4392 4393 4394 4395 4396 4397 4398 4399 4400 4401 4402 4403 4404 4405 4406 4407 4408 | ** P4 is always of type P4_ADVANCE. The function pointer points to ** sqlite3BtreePrevious(). ** ** If P5 is positive and the jump is taken, then event counter ** number P5-1 in the prepared statement is incremented. */ case OP_SorterNext: /* jump */ #ifdef SQLITE_OMIT_MERGE_SORT pOp->opcode = OP_Next; #endif case OP_Prev: /* jump */ case OP_Next: { /* jump */ VdbeCursor *pC; int res; CHECK_FOR_INTERRUPT; assert( pOp->p1>=0 && pOp->p1<p->nCursor ); |
︙ | ︙ | |||
4430 4431 4432 4433 4434 4435 4436 | ** ** P3 is a flag that provides a hint to the b-tree layer that this ** insert is likely to be an append. ** ** This instruction only works for indices. The equivalent instruction ** for tables is OP_Insert. */ | | > > > | 4444 4445 4446 4447 4448 4449 4450 4451 4452 4453 4454 4455 4456 4457 4458 4459 4460 4461 | ** ** P3 is a flag that provides a hint to the b-tree layer that this ** insert is likely to be an append. ** ** This instruction only works for indices. The equivalent instruction ** for tables is OP_Insert. */ case OP_SorterInsert: /* in2 */ #ifdef SQLITE_OMIT_MERGE_SORT pOp->opcode = OP_IdxInsert; #endif case OP_IdxInsert: { /* in2 */ VdbeCursor *pC; BtCursor *pCrsr; int nKey; const char *zKey; assert( pOp->p1>=0 && pOp->p1<p->nCursor ); |
︙ | ︙ |
Changes to src/vdbeInt.h.
︙ | ︙ | |||
61 62 63 64 65 66 67 | Bool isOrdered; /* True if the underlying table is BTREE_UNORDERED */ Bool isSorter; /* True if a new-style sorter */ sqlite3_vtab_cursor *pVtabCursor; /* The cursor for a virtual table */ const sqlite3_module *pModule; /* Module for cursor pVtabCursor */ i64 seqCount; /* Sequence counter */ i64 movetoTarget; /* Argument to the deferred sqlite3BtreeMoveto() */ i64 lastRowid; /* Last rowid from a Next or NextIdx operation */ | | | 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 | Bool isOrdered; /* True if the underlying table is BTREE_UNORDERED */ Bool isSorter; /* True if a new-style sorter */ sqlite3_vtab_cursor *pVtabCursor; /* The cursor for a virtual table */ const sqlite3_module *pModule; /* Module for cursor pVtabCursor */ i64 seqCount; /* Sequence counter */ i64 movetoTarget; /* Argument to the deferred sqlite3BtreeMoveto() */ i64 lastRowid; /* Last rowid from a Next or NextIdx operation */ VdbeSorter *pSorter; /* Sorter object for OP_SorterOpen cursors */ /* Result of last sqlite3BtreeMoveto() done by an OP_NotExists or ** OP_IsUnique opcode on this cursor. */ int seekResult; /* Cached information about the header for the data record that the ** cursor is currently pointing to. Only valid if cacheStatus matches |
︙ | ︙ |
Changes to src/vdbesort.c.
︙ | ︙ | |||
405 406 407 408 409 410 411 | assert( pCsr->pKeyInfo && pCsr->pBt==0 ); pCsr->pSorter = pSorter = sqlite3DbMallocZero(db, sizeof(VdbeSorter)); if( pSorter==0 ){ return SQLITE_NOMEM; } | > | | | | | > | 405 406 407 408 409 410 411 412 413 414 415 416 417 418 419 420 421 422 423 424 425 | assert( pCsr->pKeyInfo && pCsr->pBt==0 ); pCsr->pSorter = pSorter = sqlite3DbMallocZero(db, sizeof(VdbeSorter)); if( pSorter==0 ){ return SQLITE_NOMEM; } if( !sqlite3TempInMemory(db) ){ pgsz = sqlite3BtreeGetPageSize(db->aDb[0].pBt); pSorter->mnPmaSize = SORTER_MIN_WORKING * pgsz; mxCache = db->aDb[0].pSchema->cache_size; if( mxCache<SORTER_MIN_WORKING ) mxCache = SORTER_MIN_WORKING; pSorter->mxPmaSize = mxCache * pgsz; } return SQLITE_OK; } /* ** Free the list of sorted records starting at pRecord. */ |
︙ | ︙ | |||
662 663 664 665 666 667 668 | ** ** * The total memory allocated for the in-memory list is greater ** than (page-size * cache-size), or ** ** * The total memory allocated for the in-memory list is greater ** than (page-size * 10) and sqlite3HeapNearlyFull() returns true. */ | | | 664 665 666 667 668 669 670 671 672 673 674 675 676 677 678 | ** ** * The total memory allocated for the in-memory list is greater ** than (page-size * cache-size), or ** ** * The total memory allocated for the in-memory list is greater ** than (page-size * 10) and sqlite3HeapNearlyFull() returns true. */ if( rc==SQLITE_OK && pSorter->mxPmaSize>0 && ( (pSorter->nInMemory>pSorter->mxPmaSize) || (pSorter->nInMemory>pSorter->mnPmaSize && sqlite3HeapNearlyFull()) )){ rc = vdbeSorterListToPMA(db, pCsr); pSorter->nInMemory = 0; } |
︙ | ︙ |